Path of references on a tree structure

Question

I'm trying to build a tree structure and maintain a path while traversing the tree.

Here's some code:

use std::collections::VecDeque;

struct Node {
    children: VecDeque<Node>,
}

struct Cursor<'a> {
    path: VecDeque<&'a mut Node>,
}

impl<'a> Cursor<'a> {
    fn new(n: &mut Node) -> Cursor {
        let mut v = VecDeque::new();
        v.push_front(n);
        Cursor { path: v }
    }

    fn go_down(&'a mut self, idx: usize) -> bool {
        let n = match self.path[0].children.get_mut(idx) {
            None => return false,
            Some(x) => x
        };
        self.path.push_front(n);
        true
    }
}

I have two questions. First, the lifetime specifier in go_down() self argument was suggested by the compiler, but I'm not sure why it fixes the reported issue.

Even with this change, however, the above code will not compile because self.path is borrowed two times. Is there a way to maintain a path of tree nodes without writing "unsafe" code?

I would like to modify the nodes.I only need to modify the node on the top of the stack, though, but I wasn't sure how to express this. I could have a mutable reference to the current node and a stack with immutable references for the path, but then I wouldn't be able to create a mutable reference from the immutable ones when going up the tree. — ynimous, Jun 10 '16 at 14:38

score 1 · Accepted Answer · edited May 23 '17 at 12:31

I ended up following the approach from this answer to Recursive Data Structures in Rust. The idea is that you operate with owned objects instead of references, and you deconstruct and reconstruct the tree as you traverse it.

Here's the code I ended up with:

use std::collections::VecDeque;

enum Child { Placeholder, Node(Node) }

struct Node {
    children: Vec<Child>,
}

impl Node {
    fn swap_child(&mut self, idx: usize, c: Child) -> Option<Child> {
        match self.children.get(idx) {
            None => None,
            Some(_) => {
                self.children.push(c);
                Some(self.children.swap_remove(idx))
            }
        }
    }
}

struct Cursor {
    node: Node,
    parents: VecDeque<(Node, usize /* index in parent */)>,
}

enum DescendRes { OK(Cursor), Fail(Cursor) }
enum AscendRes  { Done(Node), Cursor(Cursor) }

impl Cursor {
    fn new(n: Node) -> Cursor {
        Cursor { node: n, parents: VecDeque::new() }
    }

    fn descent(mut self, idx: usize) -> DescendRes {
        match self.node.swap_child(idx, Child::Placeholder) {
            None => DescendRes::Fail(self),
            Some(Child::Placeholder) => panic!("This should not happen"),
            Some(Child::Node(child)) => {
                let mut v = self.parents;
                v.push_front((self.node, idx));
                DescendRes::OK(
                    Cursor { node: child, parents: v }
                )
            }
        }
    }

    fn ascend(mut self) -> AscendRes {
        match self.parents.pop_front() {
            None => AscendRes::Done(self.node),
            Some((mut parent, parent_idx)) => {
                match parent.swap_child(parent_idx, Child::Node(self.node)) {
                    Some(Child::Placeholder) => {
                        AscendRes::Cursor(
                            Cursor { node: parent, parents: self.parents }
                        )
                    },
                    _ => panic!("This should not happen")
                }
            }
        }
    }
}

Path of references on a tree structure

1 Answers1