indextree Documentation

indextree is an arena-based tree structure implementation. Instead of using reference-counted pointers (like Rc or Arc), it uses a single Vec and numerical identifiers (indices in the vector) to represent nodes.

Key Benefits:

• Idiomatic Mutability: It avoids RefCell by handling mutability through unique (&mut) access to the Arena.
• Thread Safety: Because the tree is backed by a Vec, it can be sent or shared across threads, enabling parallel tree traversals.
• Performance: Using indices instead of pointers reduces overhead associated with reference counting.

When a node is removed from an Arena, its slot may eventually be reused for a new node. To prevent logic errors where a NodeId from a previous lifecycle is used to access a new node, use is_removed.

NodeId::is_removed(arena) returns true if the NodeId points to a node that has been removed or if the underlying slot has been reused for a different node.

use indextree::Arena;

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

// Assume n1 is removed via some arena method
// (Note: actual removal logic is in Arena, not NodeId)
// If n1 is removed:
if n1.is_removed(&arena) {
    println!("This reference is no longer valid!");
}

A NodeId is a lightweight handle used to reference a Node within an Arena. Most tree operations (appending, removing, traversing) are implemented as methods on NodeId and require a reference to the Arena they belong to.

Key capabilities include:

• Navigation: Access parents, ancestors, descendants, and siblings.
• Tree Modification: Append children, prepend children, insert siblings, or detach nodes.
• Safety: NodeId includes a NodeStamp to detect if a node has been removed and its slot reused, preventing stale reference bugs.

use indextree::Arena;

let mut arena = Arena::new();
let n1 = arena.new_node("root");
let n1_1 = n1.append_value("child", &mut arena);

// Use NodeId to navigate
if let Some(parent) = n1_1.parent(&arena) {
    println!("Parent ID: {}", parent);
}

Methods that modify the tree structure provide two variants:

1. Panicking variants: (e.g., NodeId::append) These call .expect() internally and will panic on failure.
2. Checked variants: (e.g., NodeId::checked_append) These return a Result<T, NodeError>, allowing you to handle errors gracefully.

Common errors include NodeError::AppendSelf when attempting to append a node to itself.

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)
));

You can build hierarchical structures like file systems using append_value. To retrieve data from the nodes during traversal, use the descendants iterator and access the node's value via the arena index.

use indextree::Arena;

let arena = &mut Arena::new();
let root = arena.new_node("/");
let etc = root.append_value("etc/", arena);
let usr = root.append_value("usr/", arena);

etc.append_value("hosts", arena);
etc.append_value("resolv.conf", arena);

let bin = usr.append_value("bin/", arena);
bin.append_value("rustc", arena);

// Traverse and collect paths
let descendants: Vec<_> = root
    .descendants(arena)
    .map(|id| *arena[id].get())
    .collect();
assert_eq!(
    descendants,
    vec!["/", "etc/", "hosts", "resolv.conf", "usr/", "bin/", "rustc"]
);

To use indextree, you primarily interact with the Arena to create nodes and manage their relationships. Nodes are manipulated by passing a mutable reference to the Arena to methods like append or ancestors.

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);

If the macros feature is enabled, you can use the tree! macro to construct complex tree structures using a declarative syntax. The macro takes the arena as its first argument, followed by key-value pairs representing node values and their children.

use indextree::{Arena, macros::tree};

let arena = &mut Arena::new();
let root = tree!(arena, "root" => {
    "child_1" => {
        "grandchild_1",
        "grandchild_2",
    },
    "child_2",
    "child_3",
});

assert_eq!(root.child_count(arena), 3);
assert_eq!(root.descendants(arena).count(), 6);

By enabling the par_iter feature, you can use rayon to perform parallel operations across the entire arena. The arena.par_iter() method provides a parallel iterator over all nodes in the arena.

use indextree::Arena;
use rayon::prelude::*;

let arena = &mut Arena::new();
let root = arena.new_node(0);
for i in 1..=1000 {
    root.append_value(i, arena);
}

let sum: i64 = arena.par_iter().map(|node| *node.get()).sum();
assert_eq!(sum, 500500);

indextree provides several optional features that can be enabled in your Cargo.toml:

The debug_pretty_print method returns a DebugPrettyPrint proxy object used for visualizing the tree structure in a human-readable format. This is primarily intended for debugging.

Supported Formats:

• {:?}: Produces a tree-like string representation using characters like |-- and `--.
• {:#?}: Produces an alternate, more expanded debug format.
• {:#}: Produces a plain string representation without the debug symbols.

# use indextree::Arena;
let mut arena = Arena::new();
let root = arena.new_node("root");
let child = arena.new_node("child");
root.append(child, &mut arena);

let printable = root.debug_pretty_print(&arena);
println!("{:?}", printable);
// Output:
// "root"
// |-- "child"