Crate indextree 

Arena based tree data structure

This arena tree structure is using just a single Vec and numerical identifiers (indices in the vector) instead of reference counted pointers. This means there is no RefCell and mutability is handled in a way much more idiomatic to Rust through unique (&mut) access to the arena. The tree can be sent or shared across threads like a Vec. This enables general multiprocessing support like parallel tree traversals.

Features

• std (default) - Enable standard library support. Disable for no_std environments (requires alloc).
• macros (default) - Enable the tree! macro for declarative tree construction.
• deser - Enable serde serialization and deserialization for Arena, Node, and NodeId.
• par_iter - Enable parallel iteration via Arena::par_iter() using rayon.

Node removal and reuse

Calling NodeId::remove does not deallocate the node slot. Instead, it marks the slot for reuse via an internal generation counter (stamp). Future calls to Arena::new_node may recycle freed slots. Stale NodeId references are detected through NodeId::is_removed, which compares the ID’s stamp against the current slot stamp.

Example usage

use indextree::Arena;

// Create a new arena
let arena = &mut Arena::new();

// Add some new nodes to the arena
let a = arena.new_node(1);
let b = arena.new_node(2);

// Append b to a
a.append(b, arena);
assert_eq!(b.ancestors(arena).count(), 2);

Error handling

Methods that modify the tree come in panicking and checked variants. The checked variants (e.g. NodeId::checked_append) return a Result with a NodeError on failure, while the panicking variants (e.g. NodeId::append) call .expect() internally.

use indextree::{Arena, NodeError};

let mut arena = Arena::new();
let root = arena.new_node("root");

// Cannot append a node to itself
assert!(matches!(
    root.checked_append(root, &mut arena),
    Err(NodeError::AppendSelf)
));

Re-exports

pub use indextree_macros as macros;

Structs

Ancestors

An iterator of the IDs of the ancestors of a given node.

Arena

An Arena structure containing certain Nodes.

Children

An iterator of the IDs of the children of a given node, in insertion order.

DebugPrettyPrint

Tree printer for debugging.

Descendants

An iterator of the IDs of a given node and its descendants, as a pre-order depth-first search where children are visited in insertion order.

FollowingSiblings

An iterator of the IDs of the siblings after a given node.

Node

A node within a particular Arena.

NodeId

A node identifier within a particular Arena.

PrecedingSiblings

An iterator of the IDs of the siblings before a given node.

Predecessors

An iterator of the IDs of the predecessors of a given node.

ReverseTraverse

An iterator of the “sides” of a node visited during a depth-first pre-order traversal, where nodes are visited end to start and children are visited in reverse insertion order.

Traverse

An iterator of the “sides” of a node visited during a depth-first pre-order traversal, where node sides are visited start to end and children are visited in insertion order.

Enums

NodeEdge

Indicator if the node is at a start or endpoint of the tree

NodeError

Errors returned by checked tree mutation methods.