bitstring_trees::tree

Struct Tree

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

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§

source§

impl<TP: TreeProperties> Tree<TP>

source

pub const fn new() -> Self

New (empty) tree.

source

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.

source

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

Get reference to root node

source

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

Get mutable reference to root node

source

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

Get reference to node with exact key

source

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

Get mutable reference to node with exact key

source

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

Goto insert position for given key

source

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

source

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

source

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

source

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

source

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

source

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

Walk tree

source

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

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

source

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

Iterate over nodes of tree depth-first pre-order

source

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

Iterate over nodes of tree depth-first in-order

source

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

Iterate over nodes of tree depth-first post-order

source

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

Iterate over nodes and leaf values of tree in-order

source

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

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

source

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

Walk mutable tree

source

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

source

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

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

source

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

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

source

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

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

source

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

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

source

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§

source§

impl<TP> Clone for Tree<TP>
where TP: TreeProperties, TP::Value: Clone,

source§

fn clone(&self) -> Self

Returns a copy of the value. Read more
1.6.0 · source§

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

Performs copy-assignment from source. Read more
source§

impl<TP> Debug for Tree<TP>
where TP: TreeProperties, TP::Key: Debug, TP::Value: Debug, TP::LeafValue: Debug,

source§

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

Formats the value using the given formatter. Read more
source§

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

source§

fn default() -> Self

Returns the “default value” for a type. Read more

Auto Trait Implementations§

§

impl<TP> Freeze for Tree<TP>

§

impl<TP> RefUnwindSafe for Tree<TP>

§

impl<TP> Send for Tree<TP>

§

impl<TP> Sync for Tree<TP>

§

impl<TP> Unpin for Tree<TP>

§

impl<TP> UnwindSafe for Tree<TP>

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> CloneToUninit for T
where T: Clone,

source§

unsafe fn clone_to_uninit(&self, dst: *mut T)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for T
where T: Clone,

source§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

source§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.