Struct Tree 

pub struct Tree<T> { /* private fields */ }

Rooted multi-way tree with O(1) id lookup.

Every node has a unique auto-incrementing u64 id (root = 0). An internal HashMap<u64, Vec<usize>> maps each id to its path (sequence of child indices from the root), so find and find_path_to are O(1) amortised.

Implementations

impl<T> Tree<T>

pub fn new(root_value: T) -> Self

Create a tree with a single root node (id = 0).

pub fn root(&self) -> &Node<T>

Reference to the root node.

pub fn root_mut(&mut self) -> &mut Node<T>

Mutable reference to the root node.

pub fn next_id(&self) -> u64

The id that will be assigned to the next inserted node.

pub fn push_child( &mut self, parent_id: u64, value: T, ) -> Result<u64, ParentNotFound>

Append a child to the node identified by parent_id.

Returns the newly assigned id, or ParentNotFound when parent_id does not exist in the tree.

pub fn find(&self, id: u64) -> Option<&Node<T>>

Look up a node by id. O(1) amortised.

pub fn find_mut(&mut self, id: u64) -> Option<&mut Node<T>>

Mutable look up by id. O(1) amortised.

pub fn find_path_to(&self, id: u64) -> Option<Vec<usize>>

Return the index path from the root to the given id. O(1) amortised.

pub fn dfs(&self) -> DfsIter<'_, T>

Depth-first iterator yielding (depth, &Node<T>) pairs.

pub fn flatten(&self) -> Vec<(usize, &Node<T>)>

Collect dfs into a Vec.

pub fn remove_subtree(&mut self, id: u64) -> Option<Node<T>>

Remove a subtree rooted at id and return its root node.

Returns None when id is the tree root (cannot remove) or does not exist. Remaining sibling indices are compacted and the internal index is rebuilt.

pub fn prune(&mut self, policy: PrunePolicy)

Apply a pruning policy to the entire tree.

The internal index is rebuilt after pruning. No nodes are protected: if you need to preserve a specific path (e.g. the current cursor), use CursoredTree::prune which automatically repairs the cursor.

Trait Implementations

impl<T: Clone> Clone for Tree<T>

fn clone(&self) -> Tree<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for Tree<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.