Traversing lazily-growing tree

1

I've got infinitely-large tree which I need to traverse in specific order (like in A*). The tree has to be built lazily, and there needs to be a queue for nodes yet to be traversed, and this creates a tricky case that I don't think RefCell can solve.

  • The tree is infinitely large, so I have to create nodes lazily. I could use RefCell for that, but
  • I need to store nodes to be traversed in BinaryHeap queue, so lifetime of RefCell borrow is too short for that
  • Creation of nodes is very expensive, and I have to conserve memory, so I can't use solutions that clone/recreate nodes on the fly.

I've tried:

struct Node {
    children: RefCell<Option<(&Node, &Node)>>;
}

impl Node {
    fn traverse(&self, queue: &mut BinaryHeap) {
        if nodes not created {
           // Mutably create here
        }
        queue.push(self.children);
    }
}

while let Some(node) = queue.pop() {
    traverse(node, &mut queue);
}

How can I make it work?

1 Like
2

Does the usual solution of storing nodes in a single Vec and using indices in children and queue work?

3

Hm, I think there is an even simpler solution. You can implement a LazyCell, which is a write once RefCell without Ref: http://doc.crates.io/src/cargo/src/cargo/util/lazy_cell.rs.html#13-15

2 Likes
4

Thank you for suggestions.

The Vec solution would work for me currently, but long term I hoped to be also able to prune items from the tree, and then I'd end up with a compacting GC in a Vec :wink:

LazyCell looks perfect!

5

You could also just use Rc.