Struct Tree

pub struct Tree<N, B> { /* private fields */ }

Tree structure with generic node and branch data.

For more information about Trees and their usage, see the module level documentation.

Each node aside from the root node has a parent to which it is linked via a branch. Nodes as well as branches have a value, which allows for giving names and wheights to branches.

Examples

A quick way to build a tree is by using the chainable version of insert() called i()

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/b/z", 6)
    .i("/c", 3)
    .i("/c/d", 7);

The resulting tree looks like this:

╱┬→ 0
 ├a┬→ 1
 │ └b┬→ 2
 │   └z─→ 6
 └c┬→ 3
   └d─→ 7

Data management

Removing a node from the tree also removes its children recursively. Removal is done in constant time, since the nodes are only unlinked from their parent and marked as removed. Since the nodes are stored in a Vec, shifting the ones succeeding the removed node would be costful and removing the whole subtree would take O(n) given n the number of nodes in that subtree.

Implementations

impl<N, B> Tree<N, B>

where N: Clone + Default + Eq, B: Clone + Default + Eq + Hash,

pub fn diff(&mut self, other: &Tree<N, B>) -> DiffTree<N, B>

pub fn zip(&mut self, other: &Tree<N, B>) -> DiffTree<N, B>

impl<N, B> Tree<N, B>

where N: Default, B: Default + Eq + Hash + Clone,

pub fn insert_extend(&mut self, path: &Path<B>, value: N) -> N

Inserts the value at the given path, extending the tree if necessary

pub fn ix(&mut self, path: impl Into<Path<B>>, value: N) -> &mut Self

Chainable insertion with extension.

Calls insert_extend and returns a mutable reference to self

pub fn force_apply_extend(&mut self, diff: DiffTree<N, B>) -> bool

Apply diff without checking its validity beforehand The tree will grow to include changes outside it. All invalid changes will be ignored (see DiffTree::validate() for more information).

impl<N, B> Tree<N, B>

where N: Default + Eq, B: Default + Eq + Hash + Clone,

pub fn combine_extend( &mut self, tree: Tree<N, B>, mode: CombinationMode, ) -> bool

pub fn trim_default(&mut self)

Removes trailing default nodes

impl<N, B> Tree<N, B>

where N: Default + Eq, B: Default + Eq + Hash + Clone,

pub fn apply_extend( &mut self, diff: DiffTree<N, B>, ) -> Result<bool, DiffApplyError<B>>

pub fn apply_diff_extend( &mut self, path: Path<B>, diff: DiffNode<N>, ) -> Result<(), DiffApplyError<B>>

pub fn apply_map_extend(&mut self, map: DiffMap<N, B>) -> bool

pub fn remove_subtree_trim( &mut self, path: &Path<B>, ) -> Result<(), Option<Path<B>>>

Fails if the diff is invalid

impl<N, B> Tree<Option<N>, B>

where N: Default, B: Default + Eq + Hash + Clone,

pub fn is_buildable(&self) -> bool

pub fn build(self) -> Tree<N, B>

impl<N, B> Tree<(Option<N>, Option<N>), B>

where B: Clone,

pub fn rev(&mut self)

pub fn validate(&self) -> Result<(), Path<B>>

impl<N, B> Tree<(Option<N>, Option<N>), B>

where N: Clone, B: Clone + Eq + Hash,

pub fn mirror_subtree_rec( &mut self, tree: &Tree<N, B>, idx_s: usize, idx_t: usize, now: bool, )

impl<N, B> Tree<(Option<N>, Option<N>), B>

where N: Clone + Default, B: Clone + Eq + Hash + Default,

pub fn mirror_subtree(&mut self, tree: &Tree<N, B>, path: &Path<B>, now: bool)

impl<N, B> Tree<(Option<N>, Option<N>), B>

where N: Default + Eq, B: Default + Eq + Hash + Clone,

pub fn is_applicable_extend( &self, tree: &Tree<N, B>, ) -> Result<(), DiffApplyError<B>>

impl<N, B> Tree<(Option<N>, Option<N>), B>

where N: Eq, B: Eq + Hash + Clone,

pub fn is_applicable(&self, tree: &Tree<N, B>) -> Result<(), DiffApplyError<B>>

impl<N, B> Tree<N, B>

pub fn new() -> Self

Creates a new empty generic tree over node data (N) and branch data (B) types.

Examples

use nb_tree::prelude::Tree;
let tree: Tree<usize, String> = Tree::new();

pub fn with_capacity(capacity: usize) -> Self

Creates a new empty tree with at least the given capacity.

pub fn reserve(&mut self, additional: usize)

Reserves space for at least the given additional amount of nodes in the tree.

pub fn get_root(&self) -> Option<&N>

Returns the value of the root node if there is one, returns None otherwise.

Examples

use nb_tree::prelude::Tree;
let mut tree: Tree<String, String> = Tree::new();
// The tree is empty
assert_eq!(tree.get_root(), None);
tree.i("/", "a".to_string());

assert_eq!(tree.get_root(), Some(&"a".to_string()));

pub fn insert_root(&mut self, value: N) -> Option<N>

Inserts a value at the root and returns the previous value if there is one.

Examples

use nb_tree::prelude::Tree;
let mut tree: Tree<String, String> = Tree::new();
assert_eq!(tree.insert_root("a".to_string()), None);
assert_eq!(tree.insert_root("b".to_string()), Some("a".to_string()));

pub fn is_empty(&self) -> bool

Returns true is the tree has no nodes.

Examples

use nb_tree::prelude::Tree;
let mut tree: Tree<String, String> = Tree::new();
assert!(tree.is_empty());
tree.insert_root("a".to_string());
assert!(!tree.is_empty());

pub fn len(&self) -> usize

Return the number of nodes in the tree.

Examples

use nb_tree::prelude::Tree;
let mut tree: Tree<usize, String> = Tree::new();
assert_eq!(tree.len(), 0);
tree.i("/", 10);
assert_eq!(tree.len(), 1);
tree.i("/a", 20)
    .i("/a/b", 30)
    .i("/a/b/z", 40)
    .i("/c", 50)
    .i("/c/d", 60);
assert_eq!(tree.len(), 6);

pub fn values(&self) -> Vec<&N>

Returns a vector of references to the tree’s node values in arbitrary order.

Examples

use std::collections::HashSet;
use std::iter::FromIterator;
use nb_tree::prelude::Tree;

let mut tree: Tree<usize, String> = Tree::new();
tree.i("/", 0)
    .i("/a", 1)
    .i("/a/b", 2);
let values: HashSet<usize> = HashSet::from_iter(vec![0,1,2].into_iter());
let tree_values: HashSet<usize> = HashSet::from_iter(tree.values().into_iter().cloned());
assert_eq!(
    tree_values,
    values);

pub fn iter(&self) -> Iter<'_, N, B, &N>

Returns an depth first iterator over the tree’s node data relatively to one another.

The iterator returns Traversals containing the associated node data. If the tree is not empty, the first item is a [Root] node containing a reference to the root node’s data. All subsequent items are Nodes containing their position relative to the previous item and a reference to the node’s data.

Examples

use nb_tree::prelude::{iter::depth::Traversal, Path, Tree};
let mut tree: Tree<usize, String> = Tree::new();
tree.i("/", 0)
    .i("/a", 1)
    .i("/a/B", 10)
    .i("/a/B/i", 100)
    .i("/a/B/j", 200)
    .i("/a/C", 11)
    .i("/a/C/x", 111)
    .i("/a/C/y", 222);
let mut iter = tree.iter();
if let Traversal::Start(data) = iter.next().expect("Root node expected") {
    // The root node's data is 0
    assert_eq!(*data, 0);
} else {
    panic!("Expected a Root node");
}
if let Traversal::Step { up, branch, data } =
    iter.next().expect("Root child Node expected")
{
    // The node is below the root node
    assert_eq!(up, 0);
    // The node is at branch "a"
    assert_eq!(*branch, "a");
    // The node's data is 1
    assert_eq!(*data, 1);
} else {
    panic!("Expected a non Root node");
}
let mut path = Path::new();
for iter_node in tree {
    // Move up the path
    if iter_node.up() > 0 {
        for _ in 0..iter_node.up() {
            path.pop_last();
        }
        //
        println!(
            "{}╭{}┘ up",
            " ".repeat(path.to_string().len()),
            "──".repeat(iter_node.up()-1)
        );
    }
    // Get the branch if any (there is none for the Root)
    if let Some(branch) = iter_node.branch() {
        path.push_last(branch.clone());
    }
    // Get the data
    println!("{}: {}", path, iter_node.data());
}

One possible output would be:

    /: 0
    /a: 1
    /a/B: 10
    /a/B/i: 100
        ╭┘ up
    /a/B/j: 200
      ╭──┘ up
    /a/C: 11
    /a/C/x: 111
        ╭┘ up
    /a/C/y: 222

As the iteration order of children of a node is unknown, “/a/C” can be visited before “/a/B”, as can “/a/B/j” and “/a/B/i” as well as “/a/C/y” and “/a/C/x”.

impl<N, B> Tree<N, B>

where B: Eq + Hash + Clone,

pub fn get(&self, path: &Path<B>) -> Result<&N, Option<Path<B>>>

Returns a reference to the value of the node at the given path. If the path leaves the tree, the path to the last node in the tree on the given path is returned, or None if the tree is empty.

Examples

use nb_tree::prelude::Tree;
let mut tree: Tree<usize, String> = Tree::new();
// Can't get any node from an empty node
assert_eq!(tree.get(&"/a/b/w".into()), Err(None));
tree.i("/", 0)
    .i("/a", 1)
    .i("/a/b", 2)
    .i("/c", 3);
// Get a reference to the node data at "/a"
assert_eq!(tree.get(&"/a".into()), Ok(&1));
// "/a/b/w" is out of the tree, "/a/b" being the last node in the tree of the path
assert_eq!(tree.get(&"/a/b/w".into()), Err(Some("/a/b".into())));

pub fn get_mut(&mut self, path: &Path<B>) -> Result<&mut N, Option<Path<B>>>

Returns a mutable reference to the value of the node at the given path. If the path leaves the tree, the path to the last node in the tree on the given path is returned, or None if the tree is empty.

Examples

use nb_tree::prelude::Tree;
let mut tree: Tree<usize, String> = Tree::new();
// Can't get any node from an empty node
assert_eq!(tree.get(&"/a/b/w".into()), Err(None));
tree.i("/", 0)
    .i("/a", 1)
    .i("/a/b", 2)
    .i("/c", 3);
// Get a reference to the node data at "/a"
assert_eq!(tree.get_mut(&"/a".into()), Ok(&mut 1));
// "/a/b/w" is out of the tree, "/a/b" being the last node in the tree of the path
assert_eq!(tree.get_mut(&"/a/b/w".into()), Err(Some("/a/b".into())));

pub fn root_entry(&self) -> Entry<&Self, N, B, TREEBOUND>

Returns an Entry with read only access to the root node’s position.

Examples

use nb_tree::prelude::Tree;
let mut tree: Tree<usize, String> = Tree::new();
let entry = tree.root_entry();
assert!(!entry.is_node());
tree.i("/", 7)
    .i("/c1", 1);
let mut entry = tree.root_entry();
assert_eq!(entry.value(), Some(&7));
entry.move_down_branch("c1".into());
assert_eq!(entry.value(), Some(&1));

pub fn root_entry_mut(&mut self) -> Entry<&mut Self, N, B, TREEBOUND>

Returns an Entry with mutable access to the root node’s position.

Examples

use nb_tree::prelude::Tree;
let mut tree: Tree<usize, String> = Tree::new();
let mut entry = tree.root_entry_mut();
assert!(!entry.is_node());
assert_eq!(entry.or_insert(5), &mut 5);
entry.move_down_branch("c1".into());
assert_eq!(entry.or_insert(1), &mut 1);

pub fn entry(&self, path: &Path<B>) -> Entry<&Self, N, B, TREEBOUND>

Returns an Entry with read only access to the given position in the tree.

Examples

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);
let entry = tree.entry(&"/a/b".into());
assert_eq!(entry.value(), Some(&2));

pub fn entry_mut(&mut self, path: &Path<B>) -> Entry<&mut Self, N, B, TREEBOUND>

Returns an Entry with mutable access to the given position in the tree.

Examples

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);
let mut entry = tree.entry_mut(&"/a/b/d".into());
assert_eq!(entry.or_insert(4), &mut 4);

pub fn insert( &mut self, path: &Path<B>, value: N, ) -> Result<Option<N>, Option<Path<B>>>

Inserts a value at the given path. Returns the existing value if any. Insertions can be done on any existing node (path points to an existing node) or on children of existing nodes (path points to an inexistent immediate child of an existing node). Insertions cannot be done if path points to a node further away from the existing tree as it cannot close the gap between the last existing node and the new one to insert. In this case the operation will fail and the Path to the closest existing node will be returned.

Examples

use nb_tree::prelude::Tree;
let mut tree: Tree<_, String> = Tree::new();
// Set root
assert_eq!(tree.insert(&"/".into(), 0), Ok(None));
// Append node
assert_eq!(tree.insert(&"/a".into(), 1), Ok(None));
// Overwrite existing node
assert_eq!(tree.insert(&"/a".into(), 2), Ok(Some(1)));
// Leave tree
assert_eq!(tree.insert(&"/a/b/c".into(), 2), Err(Some("/a".into())));

pub fn remove_subtree(&mut self, path: &Path<B>) -> Result<(), Option<Path<B>>>

Removes the subtree at the given path from the tree If the root node is not found, it returns the path to the closest existing node, or None if the tree is empty.

Examples

use nb_tree::prelude::Tree;
let mut tree1: Tree<usize, String> = Tree::new();
tree1.insert(&"/".into(), 0);
tree1.insert(&"/a".into(), 1);
tree1.insert(&"/a".into(), 2);
tree1.insert(&"/b".into(), 3);
let mut tree2 = tree1.clone();

// Add a branch to tree2
tree2.insert(&"/c".into(), 4);
tree2.insert(&"/c/d".into(), 5);

// Remove the branch
tree2.remove_subtree(&"/c".into());
assert_eq!(tree1, tree2);

pub fn force_apply(&mut self, diff: DiffTree<N, B>) -> bool

Applies the differential to the tree without checking its validity beforehand

Nodes that can’t be added or removed are skipped.

Examples

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);
let mut diff: DiffTree<usize, String> = DiffTree::new();
diff.i("/", (Some(0), Some(9)))
    .i("/a", (Some(1), Some(2)))
    .i("/a/w", (Some(2), Some(100)))
    .i("/x", (Some(40), None))
    .i("/z", (None, Some(200)))
    .i("/c", (None, Some(4)));
tree1.force_apply(diff);

let mut tree_applied: Tree<usize, String> = Tree::new();
tree_applied.i("/", 9)
    .i("/a", 2)
    .i("/a/b", 2)
    .i("/a/w", 100)
    .i("/z", 200)
    .i("/c", 4);
assert_eq!(tree1, tree_applied);

pub fn force_apply_with<'a>( &'a mut self, diff: DiffTree<N, B>, insert: fn(&mut Entry<&'a mut Tree<N, B>, N, B, BND>, N) -> bool, delete: fn(&mut Entry<&'a mut Tree<N, B>, N, B, BND>) -> bool, ) -> bool

pub fn combine(&mut self, tree: Tree<N, B>, mode: CombinationMode) -> bool

Combines two trees together following a given mode

The mode specifies whether to : - keep the nodes only present in the initial tree - grow the tree with nodes only present in the other tree - overwrite the nodes’ data with the ones of the other tree

Examples

use nb_tree::prelude::Tree;
use nb_tree::tree::CombinationMode;
let mut tree1: Tree<usize, String> = Tree::new();
tree1.i("/", 0)
    .i("/a", 1)
    .i("/a/b", 2)
    .i("/c", 3);

let mut tree2: Tree<usize, String> = Tree::new();
tree2.i("/", 10)
     .i("/a", 11)
     .i("/a/d", 7);

tree1.combine(tree2, CombinationMode::Free{keep: true, grow: true, overwrite: true});
let mut tree_res = Tree::new();
tree_res.i("/", 10)
        .i("/a", 11)
        .i("/a/d", 7)
        .i("/a/b", 2)
        .i("/c", 3);

assert_eq!(tree1, tree_res);

impl<N, B> Tree<N, B>

where B: Eq + Hash + Clone + Dbg,

pub fn i(&mut self, path: impl Into<Path<B>>, value: N) -> &mut Self

Chainable insertion Calls insert and returns a mutable reference to self

Panics

Panics if the insertion fails

impl<N, B> Tree<N, B>

where N: Eq, B: Eq + Hash + Clone,

pub fn apply(&mut self, diff: DiffTree<N, B>) -> Result<bool, DiffApplyError<B>>

Applies the differential to the tree if it is valid

Examples

use nb_tree::prelude::Tree;
let mut tree1: Tree<usize, String> = Tree::new();
tree1.i("/", 0)
    .i("/a", 1)
    .i("/a/b", 2)
    .i("/c", 3)
    .i("/f", 4)
    .i("/f/d", 5);
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)
    .i("/c/d/e", 2);
let mut diff = tree1.diff(&tree2);
// 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()).unwrap();
// They are both equal now
assert_eq!(tree1, tree2, "Both trees are not equal");
// Applying the reversed diff will restore tree1
diff.rev();
tree1.apply(diff).unwrap();
assert_eq!(tree1, tree1_orig);

pub fn apply_diff( &mut self, path: Path<B>, diff: DiffNode<N>, ) -> Result<(), DiffApplyError<B>>

Applies a DiffNode at the given Path in the tree

Examples

use nb_tree::prelude::Tree;
let mut tree1: Tree<usize, String> = Tree::new();
tree1.i("/", 0)
    .i("/a", 1)
    .i("/a/b", 2)
    .i("/c", 3);
let mut tree2 = tree1.clone();
tree2.i("/a/b/d", 7);
tree1.apply_diff("/a/b/d".into(), (None, Some(7)));
assert_eq!(tree1, tree2);

pub fn apply_map(&mut self, map: DiffMap<N, B>) -> bool

Applies a DiffMap to the tree

Returns true if all diffs have been applied, and false otherwise

Trait Implementations

impl<N: Clone, B: Clone> Clone for Tree<N, B>

fn clone(&self) -> Tree<N, B>

Returns a duplicate of the value.

const fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<N: Debug, B: Debug> Debug for Tree<N, B>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<N, B> Default for Tree<N, B>

fn default() -> Self

Returns the “default value” for a type.

impl<N, B> Index<&Path<B>> for Tree<N, B>

where B: Eq + Hash + Clone,

type Output = N

The returned type after indexing.

fn index(&self, index: &Path<B>) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<'a, N, B> IntoIterator for &'a Tree<N, B>

type Item = Traversal<&'a N, &'a B>

The type of the elements being iterated over.

type IntoIter = Iter<'a, N, B, &'a N>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<N, B> IntoIterator for Tree<N, B>

where B: Clone,

type Item = Traversal<N, B>

The type of the elements being iterated over.

type IntoIter = IntoIter<N, B, N>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<N, B> PartialEq for Tree<N, B>

where N: Eq, B: Eq + Hash,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

const fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<N, B> Eq for Tree<N, B>

where N: Eq, B: Eq + Hash,