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

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.

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

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.

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

@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.

That makes sense.

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