Expand description
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 explicitVec
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 implementsForestNodeStore
.ForestNodeStore
trait: Defines the basic interface for node storage (adding nodes, accessing data/parent, mapping data).ForestNodeStoreDown
trait: ExtendsForestNodeStore
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).
- Node
IdIter - Root
Data - Internal data associated with the root of a tree in the
Forest
. - RootId
- A type-safe identifier for a tree within a
Forest
. Wraps ausize
index into theForest
’s roots vector. - Tree
Node Id - A type-safe identifier for a node within a
Forest
. Wraps ausize
index into the underlying node storage vector.
Enums§
- Forest
Error - Errors that can occur during forest operations.
Traits§
- Forest
Node Store - The core trait defining the interface for node storage within a
Forest
. Requires Index and IndexMut support for accessing node data and ParentId. - Forest
Node Store Ancestors - Trait for stores supporting ancestor iteration (upward traversal).
- Forest
Node Store Bfs - Trait for stores supporting breadth-first traversal.
- Forest
Node Store Down - Trait extension for
ForestNodeStore
providing downward traversal capabilities. - Forest
Node Store Preorder - Trait for stores supporting pre-order traversal.
- Forest
Node Store Root Leaves - Trait for stores supporting iteration over leaves belonging to a specific root.