Expand description
Structures to build and manipulate Trees.
§Tree
A tree structure.
§Data Structure
The nb_tree crate provides a Tree<N, B> type
generic over node and branch data.
Trees have an O(n) indexing. More precisely, it retrieves every node on the path from the tree root to the targetted node. Insertion and removal take a Path to target a node, binding their complexity to the one of indexing, thus O(n). Entries can be used to insert or remove at the Entry’s position in the tree, which only takes O(1).
Trees can be built, navigated and modified, diffed, combined and iterated on amongst other operations.
§Building trees
Trees can be built in several ways using (chainable) insertion methods.
§Inserting data
Data can be added or overwritten at a specified location via [insert].
use nb_tree::prelude::Tree;
let mut tree: Tree<usize, String> = Tree::new();
// Insert at root
// (None reflects the creation of a new node
// there is no previous value to return)
assert_eq!(tree.insert(&"/".into(), 0), Ok(None));
// Insert at various given Paths
assert_eq!(tree.insert(&"/a".into(), 1), Ok(None));
assert_eq!(tree.insert(&"/b".into(), 2), Ok(None));
assert_eq!(tree.insert(&"/b/c".into(), 3), Ok(None));
// One can't insert below an inexistent node with `insert`
// Use `insert_extend` for this
assert_eq!(tree.insert(&"/a/x/z".into(), 12), Err(Some("/a".into())));A shorthand exists for chaining insertions
use nb_tree::prelude::Tree;
let mut tree: Tree<usize, String> = Tree::new();
tree.i("/", 0)
.i("/a", 1)
.i("/a/b", 2)
.i("/a/c", 3)
.i("/d", 4);Note that [i] panics if the insertion fails.
For node data types that are Default, [insert_extend] can be used to build intermediary nodes with default data between the last existing node of the given [Path] in the [Tree] and the one to insert
use nb_tree::prelude::Tree;
let mut tree: Tree<usize, String> = Tree::new();
tree.insert_extend(&"/a/b/c/x/y/z".into(), 1000000);
assert_eq!(tree.values().len(), 7);
// A shorthand for `insert_extend` also exists and can be chained
tree.ix("/a/b/i/j/k", 101010)
.ix("/a/u/v/w/i/j/k", 222);
assert_eq!(tree.values().len(), 16);[insert_extend] returns the old value if any.
If the node did not exist, it returns the default value of the node type.
§Builder
[TreeBuilder] is a Tree wrapping each node data in an Option.
Trees with Option<N> node data have a [try_build()] method to build
a Tree<N> from it.
use nb_tree::prelude::{Tree, TreeBuilder};
let mut tree: TreeBuilder<usize, String> = TreeBuilder::new();
tree.ix("/a/b/c", Some(3))
.ix("/a/b", Some(2));
// The tree can't be built because there are empty nodes ("/" and "/a") left
assert_eq!(tree.is_buildable(), false);
tree.ix("/", Some(0))
.ix("/a", Some(1));
// The tree is now buildable
assert_eq!(tree.is_buildable(), true);
let mut tree_cmp: Tree<usize, String> = Tree::new();
tree_cmp.i("/", 0).i("/a", 1).i("/a/b", 2).i("/a/b/c", 3);
assert_eq!(tree.build(), tree_cmp);§Removing data
Subtrees can be removed from a tree: [remove_subtree] removes the subtree starting at the given [Path].
use nb_tree::prelude::Tree;
let mut tree: Tree<usize, String> = Tree::new();
tree.i("/", 0)
.i("/a", 1)
.i("/a/b", 2)
.i("/a/c", 3);
// Removes the subtree at /a
tree.remove_subtree(&"/a".into());
// Only the root node (of value 0) now remains
assert_eq!(tree.values().len(), 1);[remove_subtree_trim] also trims out parent nodes containing the default value:
use nb_tree::prelude::Tree;
let mut tree: Tree<Option<usize>, String> = Tree::new();
assert!(tree.insert(&"/".into(), Some(0)).is_ok());
assert!(tree.insert(&"/a".into(), Some(1)).is_ok());
tree.insert_extend(&"/a/b/c/i/j/k/x/y/z".into(), Some(1000000));
// `remove_subtree` only removes the subtree
tree.remove_subtree(&"/a/b/c/i/j/k".into());
assert_eq!(tree.len(), 6);
// `remove_subtree_trim` also removes the parent nodes containing `None`
tree.remove_subtree_trim(&"/a/b/c".into());
// Only the root node and the node at "/a" containing non default data remain
assert_eq!(tree.len(), 2);§Navigation and manipulation
Entries allow for tree navigation and mutation, similarly to HashMaps’ entry system. It represents an entry at a given Path. It may lead to a defined node or not.
use nb_tree::prelude::Tree;
let mut tree: Tree<usize, String> = Tree::new();
tree.i("/", 0)
.i("/a", 1)
.i("/a/b", 2)
.i("/c", 3)
.i("/f", 4);
let mut entry = tree.entry_mut(&"/a".into());
// Insert only if there isn't a value already defined
// (won't do anything since /a is already set)
entry.or_insert(10);
// Move down to an other node
entry.move_down("/b/w".into());
// inserts 12 at /b/w
entry.or_insert(12);
// `or_insert_extend` is only available if N is Default
let mut tree2: Tree<Option<usize>, String> = Tree::new();
let mut entry2 = tree2.entry_mut(&"/i/j/k".into());
entry2.or_insert_extend(Some(12));
assert_eq!(tree2.len(), 4);and_modify only applies the given function to the node’s value if it is defined.
let mut entry = tree.entry_mut(&"/a/b".into());
entry.and_modify(|mut n| *n += 1);The previous methods like insert and remove_subtree are also available
for inserting and removing data at entry position.
§Differentials
§Diffing
Trees can be compared via [diff], producing a [DiffTree] containing
all differing nodes between the compared trees.
[DiffTree]s are Trees with DiffNodes which have the type (Option(N), Option(N)).
The Options signal the presence (or absence thereof) of the node in the compared trees.
The DiffTree produced by diff only contains data for nodes differing,
so the diff tree will be extended with empty nodes ((None, None)) to build the tree.
use nb_tree::prelude::{Tree, DiffTree};
let mut tree1: Tree<usize, String> = Tree::new();
tree1.i("/", 0)
.i("/a", 1)
.i("/a/b", 2)
.i("/c", 3)
.i("/f", 4);
let mut tree2: Tree<usize, String> = Tree::new();
tree2.i("/", 9)
.i("/a", 2)
.i("/a/b", 1)
.i("/c", 3)
.i("/c/d", 4);
// Create a DiffTree containing the differences between `tree1` and `tree2`
let diff = tree1.diff(&tree2);
let mut diff_cmp: DiffTree<usize, String> = DiffTree::new();
diff_cmp.i("/", (Some(0), Some(9)))
.i("/a", (Some(1), Some(2)))
.i("/a/b", (Some(2), Some(1)))
.i("/f", (Some(4), None))
.ix("/c/d", (None, Some(4)));
// "/c/d" node insertion needs a node at "/c"
// `ix` will extend the tree with an empty node (`(None, None)`) to allow for that
assert_eq!(diff, diff_cmp);[zip] will combine both trees into a [DiffTree].
§Applying diffs
[DiffTree]s can be applied to a tree via [apply] and [apply_extend].
// … taking back `tree1`, `tree2` and `diff` from the previous example
let tree1_orig = tree1.clone();
// Apply the differential between `tree1` and `tree2`
tree1.apply(diff.clone());
// They are both equal now
assert_eq!(tree1, tree2);
// Applying the reversed diff will restore tree1
diff.rev();
tree1.apply(diff);
assert_eq!(tree1, tree1_orig);Single diff data can be applied via the apply_diff method which takes a
Path and a DiffNode and applies it to the tree.
These diffs can be gathered into a DiffMap that too can be applied
via apply_map.
use nb_tree::prelude::{Tree, DiffMap};
use std::collections::HashMap;
let mut tree: Tree<usize, String> = Tree::new();
tree.i("/", 0)
.i("/a", 1)
.i("/a/b", 2)
.i("/c", 3)
.i("/f", 4);
// Changes the value of the node at /c from 3 to 7
tree.apply_diff("/c".into(), (Some(3), Some(7)));
// Removes the node at /a that had the value 1 and the subtree below it
tree.apply_diff("/a".into(), (Some(1), None));
// Changes /f from 4 to 0, creates /f/z with value 5
let map = HashMap::from([
("/f".into(), (Some(4), Some(0))),
("/f/z".into(),
(None, Some(5)))]).into();
let mut tree_cmp: Tree<usize, String> = Tree::new();
tree.apply_map(map);
tree_cmp.i("/", 0)
.i("/c", 7)
.i("/f", 0)
.i("/f/z", 5);
assert_eq!(tree, tree_cmp);§Combining
Combining trees can be done through the combine() method.
Data present in both trees can be chosen from either tree,
data only present in one of them can be kept or discarded.
CombinationMode::Union and CombinationMode::Intersection are available,
as well as a CombinationMode::Free mode which lets freely select
the data to keep during the combination.
use nb_tree::prelude::{Tree, CombinationMode};
let mut tree1: Tree<usize, String> = Tree::new();
tree1.i("/", 0)
.i("/a", 1)
.i("/a/b", 11)
.i("/c", 2)
.i("/f", 3);
let mut tree2: Tree<usize, String> = Tree::new();
tree2.i("/", 500) // |- overlaping data
.i("/a", 900) // |
.i("/a/w", 910)// |- new data
.i("/x", 100) // |
.i("/x/y", 110)// |
.i("/z", 300); // |
// tree1 is combined with tree2, keeping tree1's nodes absent from tree2,
// growing tree1 with tree2's nodes absent from tree1
// and overwriting tree1's data with tree2's for nodes common to both trees.
tree1.combine(tree2, CombinationMode::Free{keep: true, grow: true, overwrite: true});
// (this is the same as `CombinationMode::Union(true)`)
let mut tree_comb: Tree<usize, String> = Tree::new();
tree_comb.i("/", 500) // |- common nodes with tree2's data (overwrite)
.i("/a", 900) // |
.i("/a/b", 11) // |- tree1's nodes (keep)
.i("/c", 2) // |
.i("/f", 3) // |
.i("/a/w", 910)// |- tree2's nodes (grow)
.i("/x", 100) // |
.i("/x/y", 110)// |
.i("/z", 300); // |
assert_eq!(tree1, tree_comb);§Iterating
The default iteration method is depth first (width first is not yet available)
use nb_tree::prelude::{Tree, DiffMap};
let mut tree1: Tree<usize, String> = Tree::new();
tree1.i("/", 0)
.i("/a", 1)
.i("/a/b", 12)
.i("/c", 3)
.i("/f", 4);
// Prints each node's branch and value
for iter_node in tree1 {
println!("{} at {:?}", iter_node.data(), iter_node.branch());
}iter and into_iter are implemented (iter_mut is not yet available).
The iteration nodes contain information about the position in the tree
relative to the previous node.
The path to the current node can be built by applying these relative movements to it.
let mut path = Path::new();
for iter_node in tree1 {
path.apply(&iter_node);
println!("{} at {}", iter_node.data(), path);
}The usual iterator operations are available as well as absolute and skip_below.
absolute returns the next value with its Path.
use itertools::Itertools;
use crate::nb_tree::tree::iter::{TreeIterTools, TraversalNode};
assert_eq!(
tree1.into_iter().absolute().map(|n| n.path).sorted().collect::<Vec<Path<String>>>(),
vec!["/".into(), "/a".into(), "/a/b".into(), "/c".into(), "/f".into()]
);skip_below takes a predicate and skips all nodes at and below the current path.
use nb_tree::prelude::{Tree, DiffMap};
let mut tree1: Tree<usize, String> = Tree::new();
tree1.i("/", 0)
.i("/a", 1)
.i("/a/b", 12)
.i("/a/b/z", 6)
.i("/c", 3)
.i("/c/d", 7)
.i("/c/d/y", 5)
.i("/f", 11)
.i("/g", 10)
.i("/h", 11)
.i("/i", 19)
.i("/i/w", 18)
.i("/i/w/n", 8)
.i("/k", 15);
use itertools::Itertools;
use nb_tree::prelude::Path;
use crate::nb_tree::tree::iter::TreeIterTools;
assert_eq!(
tree1.into_iter().skip_below(|item| {
*item.data() >= 10
}).map(|n| n.data().clone()).sorted().collect::<Vec<usize>>(),
vec![0, 1, 3, 5, 7]
);Modules§
Structs§
Enums§
- Combination
Mode - Description of how two trees will be combinedthe way the way
- Position
- Descripion of a position in a tree
Type Aliases§
- Diff
Node - Representation of a node differential
- Diff
Tree - A tree containing DiffNodes as nodes
- Tree
Builder - A tree with optional data for each node