Module tree

Defines core data structures and traits for representing forests (collections of trees).

This module provides multiple ways to store tree node relationships, each with different trade-offs in terms of memory usage and traversal performance:

• ParentPointerStore: Each node stores only its data and a pointer to its parent. Memory efficient, fast upward traversal, slow downward traversal (finding children).
• ParentChildStore: Uses a first-child, next-sibling representation with cyclic sibling links. Balances memory and allows efficient child/sibling iteration.
• ChildVecStore: Each node stores its parent, data, and an explicit Vec of its children. Simple child iteration, potentially higher memory usage for nodes with many children.

The core components are:

• Forest<R, N>: The main struct representing a collection of trees. It stores root data (R) and uses a specific node storage strategy (N) that implements ForestNodeStore.
• ForestNodeStore trait: Defines the basic interface for node storage (adding nodes, accessing data/parent, mapping data).
• ForestNodeStoreDown trait: Extends ForestNodeStore with methods for downward traversal (iterating children and leaves).
• TreeNodeId, RootId, ParentId: Typed identifiers for nodes, roots, and parent links.

Conversions between the different store types are provided via From implementations.

Modules

child_pointer

Implements a tree structure using a first-child, next-sibling representation. Each node stores its parent, data, a pointer to its first child, and pointers to its left and right siblings using a cyclic doubly linked list for siblings.

child_vec

iterato

Helper iterator implementations used by different ForestNodeStore types.

parent_pointer

Implements a tree structure where each node only stores a pointer to its parent.

Structs

Forest

Represents a forest (a collection of disjoint trees).

NodeIdIter

RootData

Internal data associated with the root of a tree in the Forest.

RootId

A type-safe identifier for a tree within a Forest. Wraps a usize index into the Forest’s roots vector.

TreeNodeId

A type-safe identifier for a node within a Forest. Wraps a usize index into the underlying node storage vector.

Enums

ForestError

Errors that can occur during forest operations.

Traits

ForestNodeStore

The core trait defining the interface for node storage within a Forest. Requires Index and IndexMut support for accessing node data and ParentId.

ForestNodeStoreAncestors

Trait for stores supporting ancestor iteration (upward traversal).

ForestNodeStoreBfs

Trait for stores supporting breadth-first traversal.

ForestNodeStoreDown

Trait extension for ForestNodeStore providing downward traversal capabilities.

ForestNodeStorePreorder

Trait for stores supporting pre-order traversal.

ForestNodeStoreRootLeaves

Trait for stores supporting iteration over leaves belonging to a specific root.