Struct nb_tree::prelude::Tree

pub struct Tree<N, B>
where
    N: Debug + PartialEq,
    B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,
{ /* private fields */ }

Tree structure with generic node and branch data Each node is linked to its children via branches.

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)
assert_eq!(tree.insert(&"/".into(), 0), Ok(None));
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("/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);

[insert_extend] returns the old value if any. If the node did not exist, it returns the default value of the node type.

Removing data

Subtrees can be removed from a tree. [remove_sub_tree] removes the subtree whom root is pointed at by 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);
tree.remove_sub_tree(&"/a".into());
assert_eq!(tree.values().len(), 1);

[remove_sub_tree_trim] also trims out parent nodes containing the default value

use nb_tree::prelude::Tree;
let mut tree: Tree<Option<usize>, String> = Tree::new();
tree.insert(&"a".into(), Some(1));
tree.insert_extend(&"/a/b/c/i/j/k/x/y/z".into(), Some(1000000));
// [remove_sub_tree] only removes the subtree
tree.remove_sub_tree(&"/a/b/c/i/j/k".into());
assert_eq!(tree.values().len(), 7);
// [remove_sub_tree_trim] also removes the parent nodes containing `None`
tree.remove_sub_tree_trim(&"/a/b/c".into());
// Only the node at "/a" remains, containing non default data
assert_eq!(tree.values().len(), 1);

Diffing and applying Diffs

Tree differentials can be applied to a tree via [apply] and [apply_extend]. Differentials (diffs) contain the difference between two trees. This can be useful to save differences between two trees and use them as patches for instance.

Diffs are trees with for each node a potential Before and Now value, representing the values of two Before and Now trees compared against each other. Their type is Tree<(Option<N>, Option<N>), B> where each Before and Now N values are wrapped in an Option to represent the potential absence of an equivalent node in the other tree. They form a tuple wrapped in an other Option which allows for diffs together in a tuple

Examples

Data structure

Implementations

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

where B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash, N: Debug + PartialEq,

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

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

where B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash, N: Debug + Default + PartialEq,

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 overwrite_extend(&mut self, diff: DiffTree<N, B>)

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

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

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

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

where N: Debug + Clone + PartialEq, B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,

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

pub fn mirror_sub_tree_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: Debug + PartialEq, B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,

pub fn rev(&mut self)

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

where N: Debug + PartialEq, B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,

pub fn new() -> Self

Creates a new empty tree

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]

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

pub fn insert(&mut self, path: &Path<B>, value: N) -> Result<Option<N>, 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("/a".into()));

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

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

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

Removes the sub tree 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<_, 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_sub_tree(&"/c".into());
assert_eq!(tree1, tree2);

pub fn flat<'a>(&'a self) -> Option<(&'a N, Vec<TreeTraversalNode<'a, N, B>>)>

Returns a vector of all values and their position relative to each other The first value of the tuple is the root item’s, followed by a vector of [TreeTraversal] items. Each one of the vector’s items contains the value of the described node as well as its position relative to the previous node.

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

Applies the differential to the tree if it is valid

pub fn is_empty(&self) -> bool

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

where N: Debug + Clone + PartialEq, B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + 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>

Trait Implementations

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

where N: Clone + Debug + PartialEq, B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

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

where N: Debug + PartialEq + Debug, B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash + Debug,

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

Formats the value using the given formatter.

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

where N: Debug + PartialEq + Default, B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash + Default,

fn default() -> Tree<N, B>

Returns the “default value” for a type.

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

where N: Debug + PartialEq, B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,

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>

where N: Debug + PartialEq, B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,

type Item = (Path<B>, &'a N)

The type of the elements being iterated over.

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

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 N: Debug + PartialEq + Default, B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,

type Item = (Path<B>, N)

The type of the elements being iterated over.

type IntoIter = IntoIter<N, B>

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: Debug + PartialEq, B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,

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

This method tests for self and other values to be equal, and is used by ==.

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

This method 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: Debug + PartialEq + Eq, B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,