Struct Tree

pub struct Tree<TP: TreeProperties> { /* private fields */ }

Tree is a binary tree with path-shortening.

Nodes are either inner nodes with two child nodes, or leaf nodes. Both node types carry keys and values, leaf nodes an additional leaf value (of different type).

Implementations

impl<TP: TreeProperties> Tree<TP>

pub const fn new() -> Self

New (empty) tree.

pub fn set_leaf_value(&mut self, key: TP::Key, value: TP::LeafValue)

Set a new prefix => value mapping.

Leaf values are designed to split all values into prefixes that either have a leaf value or no leaf value set.

Sibling prefixes that share the same leaf value are merged.

pub fn root(&self) -> Option<&Node<TP>>

Get reference to root node

pub fn root_mut(&mut self) -> Option<&mut Node<TP>>

Get mutable reference to root node

pub fn get<'r>(&'r self, key: &TP::Key) -> Option<&'r Node<TP>>

Get reference to node with exact key

pub fn get_mut<'r>(&'r mut self, key: &TP::Key) -> Option<&'r mut Node<TP>>

Get mutable reference to node with exact key

pub fn goto_insert<'r>( &'r self, key: &TP::Key, ) -> Option<InsertPositionWith<&'r Node<TP>>>

Goto insert position for given key

pub fn goto_mut_insert<'r>( &'r mut self, key: &TP::Key, ) -> Option<InsertPositionWith<&'r mut Node<TP>>>

Goto mutable insert position for given key

pub fn get_longest_prefix_with<'r, F>( &'r self, key: &TP::Key, callback: F, ) -> Option<&'r Node<TP>>

where F: FnMut(&Node<TP>) -> bool,

Get a reference to the node with the longest prefix satisfying callback of the target key

pub fn get_longest_prefix_mut_with<'r, F>( &'r mut self, key: &TP::Key, callback: F, ) -> Option<&'r mut Node<TP>>

where F: FnMut(&mut Node<TP>) -> bool,

Get a reference to the node with the longest prefix satisfying callback of the target key

pub fn get_most_specific<'r>(&'r self, key: &TP::Key) -> Option<&'r Node<TP>>

Get a reference to the node with the longest prefix of the target key

pub fn get_most_specific_mut<'r>( &'r mut self, key: &TP::Key, ) -> Option<&'r mut Node<TP>>

Get a mutable reference to the node with the longest prefix of the target key

pub fn walk<D, A>(&self) -> Walk<'_, TP, D, A>

Walk tree

pub fn iter_path(&self, key: TP::Key) -> IterPath<'_, TP>

Iterate over nodes of tree that are a prefix of target key

pub fn iter_pre_order(&self) -> IterPreOrder<'_, TP>

Iterate over nodes of tree depth-first pre-order

pub fn iter_in_order(&self) -> IterInOrder<'_, TP>

Iterate over nodes of tree depth-first in-order

pub fn iter_post_order(&self) -> IterPostOrder<'_, TP>

Iterate over nodes of tree depth-first post-order

pub fn iter_leaf(&self) -> IterLeaf<'_, TP>

Iterate over nodes and leaf values of tree in-order

pub fn iter_leaf_full(&self) -> IterLeafFull<'_, TP>

Iterate over nodes and leaf values and uncovered keys of tree in-order

pub fn walk_mut<D, A>(&mut self) -> WalkMutOwned<'_, TP, D, A>

Walk mutable tree

pub fn iter_mut_path(&mut self, key: TP::Key) -> MutPath<'_, TP>

Iterate over keys and mutable values of tree that are a prefix of target key

pub fn iter_mut_pre_order(&mut self) -> IterMutOwnedPreOrder<'_, TP>

Iterate over keys and mutable values of tree depth-first pre-order

pub fn iter_mut_in_order(&mut self) -> IterMutOwnedInOrder<'_, TP>

Iterate over keys and mutable values of tree depth-first in-order

pub fn iter_mut_post_order(&mut self) -> IterMutOwnedPostOrder<'_, TP>

Iterate over keys and mutable values of tree depth-first post-order

pub fn iter_mut_leaf(&mut self) -> IterMutOwnedLeaf<'_, TP>

Iterate over keys and mutable leaf values of tree in-order

pub fn iter_mut_leaf_full(&mut self) -> IterMutOwnedLeafFull<'_, TP>

Iterate over keys and mutable leaf values and uncovered keys of tree in-order

Trait Implementations

impl<TP> Clone for Tree<TP>

where TP: TreeProperties, TP::Value: Clone,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<TP> Debug for Tree<TP>

where TP: TreeProperties, TP::Key: Debug, TP::Value: Debug, TP::LeafValue: Debug,

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

Formats the value using the given formatter.

impl<TP: TreeProperties> Default for Tree<TP>

fn default() -> Self

Returns the “default value” for a type.