I'm trying to design a tree container that will respect the following API:
pub type NodePtr<T> = Rc<RefCell<Node<T>>>;
pub type TreePtr<T> = Rc<RefCell<Tree<T>>>;
let tree: TreePtr<String> = Tree::new();
let node_A: NodePtr<String> = Node::new("A".to_owned())
.add_to(tree.clone())
.unwrap();
let node_B: NodePtr<String> = Node::new("B".to_owned())
.with_parent(node_A.clone())
.with_distance(1.2)
.add_to(tree.clone())
.unwrap();
More precisely:
- There should be a
Tree
struct to provide access to a tree as a whole. - There should be a
Node
struct to provide access to each individual node. - Once a node is create via
Node::new()
, it should be immediately registered with some tree, thus, there is anadd_to
method at the end of builder chain.
I expect both top-down and bottom-up types of construction, thus, the API should be flexible, allwoing to both set a parent and add a child:
let node_C: NodePtr<String> = Node::new("C".to_owned())
.add_to(tree.clone())
.unwrap();
let node_D: NodePtr<String> = Node::new("D".to_owned())
.add_to(tree.clone())
.unwrap();
node_A.add_child(node_C.clone());
node_D.set_parent(node_A.clone());
The strategy that I chose consists in the following.
- When registering a node in a tree, I generate a node ID. Using this node ID, I then keep track of children and parents. This reduces the number of borrowing issues a lot.
pub struct Tree<T> where T: Hash + Clone + PartialEq + Eq + ToString
{
root : Option<usize>,
nodes : HashMap<usize, NodePtr<T>>,
parents : HashMap<usize, usize>,
children : HashMap<usize, Vec<usize>>,
name_to_id : HashMap<T, usize>,
curr_id : usize,
}
- The structure of the tree is being stored inside
Tree
. Thus, what remains for theNode
are node related data and a link (reference) to a tree which it belongs to.
pub struct Node<T> where T: Hash + Clone + PartialEq + Eq + ToString
{
id : usize,
name : T,
tree : TreePtr<T>,
distance : Option<f64>,
}
- Thus, each time we query
Node
to interact with other nodes, we're redirecting our query to the corresponding tree throughself.tree
. For example, when setting a parent or adding a child:
pub fn set_parent(&mut self, parent: NodePtr<T>) -> Result<(),String>
{
if parent.borrow().tree.as_ptr() != self.tree.as_ptr()
{
return Err(String::from("tree is different from parent tree"));
}
self.tree.borrow_mut().add_parent_child_edge(&parent.borrow(), &self)
}
pub fn add_child(&mut self, child: NodePtr<T>) -> Result<(),String>
{
if child.borrow().tree.as_ptr() != self.tree.as_ptr()
{
return Err(String::from("tree is different from parent tree"));
}
self.tree.borrow_mut().add_parent_child_edge(&self, &child.borrow())
}
However, when trying to return an iterator over child node via node.children()
pub fn children(&self) -> ChildrenIterator<T>
{
self.tree.borrow().children(self.id)
}
I get an error returns a reference to data owned by the current function
.
The iterator struct has some reference to the fields of the Tree
struct, namely, to the HashMap of nodes and to Vec of node ids that are children of the current node:
pub struct ChildrenIterator<'a, T> where T: Hash + Clone + PartialEq + Eq + ToString
{
index : usize,
node_ids : &'a Vec<usize>,
nodes : &'a HashMap<usize, NodePtr<T>>,
}
impl<'a, T> Iterator for ChildrenIterator<'a, T> where T: Hash + Clone + PartialEq + Eq + ToString
{
type Item = NodePtr<T>;
fn next(&mut self) -> Option<Self::Item>
{
if self.index < self.node_ids.len()
{
let node_id = self.node_ids[self.index];
let node = self.nodes.get(&node_id).unwrap().clone();
self.index += 1;
Some(node)
}
else { None }
}
}
The full code is here: Rust Playground
My questions are:
- How to fix the issue with the iterator?
- Using
NodePtr
(i.e.Rc<RefCell<Node>>
) almost everywhere simplifies borrowing, however, adds overhead. Should I change the strategy to storing nodes in a HashMap directly, i.e.,HashMap<usize, Node<T>>
and using&Node
everywhere instead? I can't foresee all the Rust-specific implications of using either of these strategies, thus, I would like to enquire on the pros and cons associated with each of them.