Module tree

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