Need help implementing a tree with stack based traversal

[billconan]

I'm tying to create a tree and initialize the tree by duplicating another tree with a stack.

but I ran into issues with Box, Rc and RefCell

both the Tree node and stack need to hold mutable ref to tree nodes.

I can't use Box due to single ownership. I can't use Rc, because I need mutability. How can I do it.

The following cpp code describes what I want to do. in the code, AnotherTree is from another library. I'm forced to use its tree traversal interface using a cursor.

struct Tree {
std::string name;
std::vector<Tree *> children;
};

Tree *root = new Tree();

std::vector<Tree*> stack;
stack.push_back(root);

TreeCursor cursor = AnotherTree.getCursor();

while (true) {
       Tree *node = new Tree(cursor);
       stack.last().children.push_back(node);
                
        if (cursor.goto_first_child()) {
            stack.push(node);
            continue;
        } else if (cursor.goto_next_sibling()) {
            continue;
        }

        bool retracing = true;
        while (retracing) {
            if (!cursor.goto_parent()) {
                retracing = false;
                reached_root = true;
            }
            else{
                stack.pop_back();
            }

            if (cursor.goto_next_sibling()) {
                retracing = false;
            }
        }
}

[erelde]

You can use both ref counting and interior mutability : Rc<RefCell<T>>

Learn Rust With Entirely Too Many Linked Lists

[2e71828]

The simplest approach is to use the function call stack, so that the compiler can understand how the various references relate to each other:

struct Tree {
    name: String,
    children: Vec<Tree>
}

struct Cursor<'a>(&'a mut Tree);

impl<'a> Cursor<'a> {
    fn node(&mut self)->&mut Tree { unimplemented!() }
    fn goto_first_child(&mut self)->bool { unimplemented!() }
    fn goto_next_sibling(&mut self)->bool { unimplemented!() }
    fn goto_parent(&mut self)->bool { unimplemented!() }
}

impl Tree {
    pub fn from_cursor(cursor: &mut Cursor)->Self {
        let mut result = Tree {
            name: cursor.node().name.clone(),
            children: vec![]
        };
        
        if cursor.goto_first_child() {
            result.children.push(Tree::from_cursor(cursor));
            while cursor.goto_next_sibling() {
                result.children.push(Tree::from_cursor(cursor));
            }
            cursor.goto_parent();
        }
        
        result
    }
}

[billconan]

Thank you very much,

using Rc<RefCell> with

let last = stack.last().unwrap();
last.borrow_mut().children.push(c);

indeed solved my problem!