A vec-backed tree structure with tree-specific generational indexes.
This library provides a
Tree<T> struct which allows the creation and manipulation of in-memory trees.
The tree itself is backed by a vector and the tree's node relationships are managed by tree-specific
generational indexes called
NodeIds (more below). In addition, "views" of tree nodes are handed out
which are either immutable (
NodeRef) or mutable (
NodeMut) instead of handing out references
directly. Most tree mutations are achieved by modifying
NodeMuts instead of talking to the tree
Trees in this crate are "just" trees. They do not allow cycles, and they do not allow arbitrary
graph structures to be created. Each node in the tree can have an arbitrary number of children, and
there is no weight associated with edges between the nodes in the tree.
Please Note: this crate does not support comparison-based data insertion. In other words, this is not a binary search tree (or any other kind of search tree) crate. It is purely a crate for storing data in a hierarchical manner. The caller must know the structure that they wish to build and then use this crate to do so; this library will not make those structural decisions for you.
This crate uses
#![forbid(unsafe_code)] to prevent any and all
unsafe code usage.
use slab_tree::*; // "hello" // / \ // "world" "trees" // | // "are" // | // "cool" let mut tree = TreeBuilder::new().with_root("hello").build(); let root_id = tree.root_id().expect("root doesn't exist?"); let mut hello = tree.get_mut(root_id).unwrap(); hello.append("world"); hello .append("trees") .append("are") .append("cool");
NodeIds are tree-specific generational indexes. Using generational indexes means that we can re-use
space inside the tree (after nodes have been removed) without also having to re-use the same tree
indexes which could potentially cause confusion and bugs. The "tree-specific" part means that indexes
from one tree cannot be confused for indexes for another tree. This is because each index contains a
process-unique-id which is shared by the tree from which that index originated.
- Allow caller control of as many allocations as possible (through pre-allocation)
- Fast and Ergonomic Node insertion and removal
- Arbitrary Tree structure creation and manipulation
- Arbitrary Graph structure creation and manipulation
- Comparison-based node insertion of any kind
An identifier used to differentiate between Nodes and tie them to a specific tree.
A mutable reference to a given
An immutable reference to a given