Random access to tree-structured data

help
1

I've been thinking about an interesting problem, which is how to provide fast random access to tree-structured data, where each parent owns its children.

The problem is that given a type Tree containing Nodes, each of which has an Id, to provide a type RandomAccessTree that has two access modes:

  • you can access the root (including mutably, so given a &mut RandomAccessTree you can get a &mut Tree), or
  • you can lookup a node in the tree by id (including mutably, so given a &mut RandomAccessTree and an Id you can get a &mut Node).

This is a lot like the problem that owning_ref is solving, but allows Tree to take ownership of Node objects.

The solution I came up with looks a bit like owning_ref, and a bit like josephine (no suprise there). A link to the playground; Rust Playground

So, am I just reinventing the wheel here? Is there some horrible unsafety that I'm not seeing? Other thoughts?

1 Like
2

PS: Oh yes, and this ICEs the compiler. @eddyb and I are good at doing that.

3

Given that a Tree is just a specialized DAG, you could also use petgraph and its direct indexing.

4

The tree structure is significant: if a node owns its child nodes through a Vec, we can use rayon’s par_iter_mut for data parallelism because sub-trees are known to be disjoint from each other.

5

Good point, I should have added that part of the idea is to avoid dynamic checks like interior mutability, when going from mutable access to a parent to mutable access of the children.