Data structure help: tree w/ pointers to nodes & updates

1

We can define a tree by speciying a enum for the Nodes as follows:

pub struct Node(Rc<NodeBase>);

pub enum NodeBase {
  String(String),
  Int(i32),
  Foo(Node),
  Bar(Node, Node),
  Cat(Node, Node),
  Dog(Vec<Node>),
  Wolf(Vec<Node>),
}

This is a tree where each Node is either a Terminal (Sgtring, Int), has a fixed number of children (Foo, Bar, Cat), or an arbitrary number of children (Dog, Wolf),

This works fine if all I need is to:

  • point at root of tree
  • recursively map over entire tree

However, as much as we hate shared mutable state, I need a way to point at individual nodes & modify that node to update the tree.

What is the best way to do this?

Pre-emptive questions:

  • Can the structure be a DAG, or is it guaranteed to be a tree?

It's guaranteed to be a tree.

  • What is an update causes a loop?

Undefined behaviour. Programmer's fault.

2

You can modify the nodes already with Rc::make_mut(). If you'd like to have modifications in place, then use Rc<RefCell<NodeBase>>.

1 Like
3

GitHub - SimonSapin/rust-forest: A tree of reference-counted nodes, with `RefCell` for mutability is also useful, with it's descriptions of rctree, arena-tree, and idtree.

4

Why Rc rather than Box? If you used box your type would guarantee that it's not a DAG. Mutability would also be simpler.

1 Like
5

@droundy : This is a great question. The structure is a tree, but I also want to be able to point to subtrees and thus the Rc instead of Box.

6

That makes sense.

7

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.