Module charcoal::freeform_tree

This is supported on crate feature freeform_tree only.

Freeform trees, ones which don’t impose any restrictions on the number of child nodes that a branch node can have.

Those can be used to build almost any other tree structure with ease, including some that are intentionally not implemented by Charcoal because they are just freeform trees with a specific type of key, such as the trie.

Example

use charcoal::freeform_tree::{FreeformTree, NodeRef};

// Create the tree. The only thing we need for that is the data payload for the root node. The
// turbofish there is needed to state that we are using the default storage method instead of
// asking the compiler to infer it, which would be impossible.
let mut tree = FreeformTree::<_>::new(451);

// Let's now try to access the structure of the tree and look around.
let root = tree.root();
// We have never added any nodes to the tree, so the root does not have any children, hence:
assert!(root.is_leaf());

// Let's replace our reference to the root with a mutable one, to mutate the tree!
let mut root = tree.root_mut();
// First things first, we want to change our root's data payload:
*(root.value_mut().into_inner()) = 120;
// While we're at it, let's add some child nodes:
let my_numbers = [
    2014, 1987, 1983,
];
root.make_branch(my_numbers.iter().copied()).unwrap();

// Let's return to an immutable reference and look at our tree.
let root = NodeRef::from(root); // Conversion from a mutable to an immutable reference
assert_eq!(root.value().into_inner(), &120);
let children = {
    let mut children_ref_iter = root.children().unwrap();
    let mut get_val = |x| {
        // Type inference decided to abandon us here
        let x: NodeRef<'_, _, _, _> = children_ref_iter.next().unwrap();
        *x.value().into_inner()
    };
    [ get_val(0), get_val(1), get_val(2) ]
};
assert_eq!(children, my_numbers);

Structs

FreeformTree	A freeform tree.
Node	A node of a freeform tree.
NodeRef	Since this type does not point to the node directly, but rather the tree the node is in and the key of the node in the storage, it can be used to traverse the tree.
NodeRefMut	A mutable reference to a node in a freeform tree.
NodeSiblingKeysIter	An iterator over keys of the siblings of a freeform tree node.
NodeSiblingsIter	An iterator over references to the siblings of a freeform tree node.
TryPushError	The error type produced by try_push_back and try_push_front, indicating that the node was a leaf node before.

Type Definitions

NodeChildKeysIter	An iterator over keys of the children of a freeform tree node.
NodeChildrenIter	An iterator over references to the children of a freeform tree node.
SparseVecFreeformTree	alloc A freeform tree which uses a sparse Vec as backing storage.
VecFreeformTree	alloc A freeform tree which uses a Vec as backing storage.