Struct containers::collections::b_tree::BTree

pub struct BTree<K, T, Rel: TotalOrderRelation<K> = Core, A: Alloc = NullAllocator> { /* fields omitted */ }

A B-node has m key-value pairs, and m+1 children if it is a stem, with the keys between the children so each key is greater than all keys in its left subtree and less than all keys in its right subtree. A node other than the root has b-1 ≤ m ≤ 2b-1, where b is the branching parametre of the tree; the root may have fewer.

Implementations

impl<K, T, Rel: TotalOrderRelation<K>, A: Alloc + Default> BTree<K, T, Rel, A>

pub fn new(rel: Rel, b: usize) -> Option<Self>

Make a new tree.

Failures

Returns None if allocation fails.

impl<K, T, Rel: TotalOrderRelation<K>, A: Alloc> BTree<K, T, Rel, A>

pub fn new_in(rel: Rel, a: A, b: usize) -> Option<Self>

Make a new tree.

Failures

Returns None if allocation fails.

pub fn size(&self) -> usize

Return number of elements.

pub fn find<Q: ?Sized>(&self, k: &Q) -> Option<&T> where
    K: Borrow<Q>,
    Rel: TotalOrderRelation<Q>, 

Find value with given key k.

pub fn find_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut T> where
    K: Borrow<Q>,
    Rel: TotalOrderRelation<Q>, 

Find value with given key k.

pub fn min(&self) -> Option<(&K, &T)>

Find value with minimum key. Return None if tree empty.

pub fn max(&self) -> Option<(&K, &T)>

Find value with maximum key. Return None if tree empty.

pub fn min_mut(&mut self) -> Option<(&K, &mut T)>

Find value with minimum key. Return None if tree empty.

pub fn max_mut(&mut self) -> Option<(&K, &mut T)>

Find value with maximum key. Return None if tree empty.

pub fn insert_with<F: FnOnce(Option<T>) -> T>(
    &mut self,
    k: K,
    f: F
) -> Result<(), (K, F)>

Seek k; if not found, insert f(None) there; if found, modify the value there from x to f(Some(x)).

Failures

Returns Err if allocation fails.

pub fn insert(&mut self, k: K, x: T) -> Result<Option<T>, (K, T)>

Insert x at k and return Some(x) if there was already a value x there.

Failures

Returns Err if allocation fails.

pub fn delete_which<Q: ?Sized>(&mut self, which: Which<&Q>) -> Option<(K, T)> where
    K: Borrow<Q>,
    Rel: TotalOrderRelation<Q>, 

Seek which; if found, delete it and value x there and return Some((k, x)).

pub fn delete<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, T)> where
    K: Borrow<Q>,
    Rel: TotalOrderRelation<Q>, 

Seek k; if found, delete it and value x there and return Some((k, x)).

pub fn delete_min(&mut self) -> Option<(K, T)>

pub fn delete_max(&mut self) -> Option<(K, T)>

pub fn foldl_with_key<Z, F: FnMut(Z, &K, &T) -> Z>(&self, z0: Z, f: F) -> Z

Fold elements in forward order.

pub fn foldr_with_key<Z, F: FnMut(Z, &K, &T) -> Z>(&self, z0: Z, f: F) -> Z

Fold elements in backward order.

pub unsafe fn alloc_mut(&mut self) -> &mut A

Trait Implementations

impl<K: Debug, T: Debug, Rel: TotalOrderRelation<K>, A: Alloc> Debug for BTree<K, T, Rel, A>

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

Formats the value using the given formatter.

impl<K, T, Rel: TotalOrderRelation<K>, A: Alloc> Drop for BTree<K, T, Rel, A>

fn drop(&mut self)

Executes the destructor for this type.

impl<K: Send, T: Send, Rel: TotalOrderRelation<K>, A: Alloc + Send> Send for BTree<K, T, Rel, A>

impl<K: Sync, T: Sync, Rel: TotalOrderRelation<K>, A: Alloc + Sync> Sync for BTree<K, T, Rel, A>