Struct containers::collections::b_tree::BTree [−][src]
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.
Methods
impl<K, T, Rel: TotalOrderRelation<K>, A: Alloc + Default> BTree<K, T, Rel, A>
[src]
impl<K, T, Rel: TotalOrderRelation<K>, A: Alloc + Default> BTree<K, T, Rel, A>
impl<K, T, Rel: TotalOrderRelation<K>, A: Alloc> BTree<K, T, Rel, A>
[src]
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>
[src]
pub fn new_in(rel: Rel, a: A, b: usize) -> Option<Self>
pub fn size(&self) -> usize
[src]
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>,
[src]
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>,
[src]
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)>
[src]
pub fn min(&self) -> Option<(&K, &T)>
Find value with minimum key.
Return None
if tree empty.
pub fn max(&self) -> Option<(&K, &T)>
[src]
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)>
[src]
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)>
[src]
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)>
[src]
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)>
[src]
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>,
[src]
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>,
[src]
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)>
[src]
pub fn delete_min(&mut self) -> Option<(K, T)>
pub fn delete_max(&mut self) -> Option<(K, T)>
[src]
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
[src]
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
[src]
pub fn foldr_with_key<Z, F: FnMut(Z, &K, &T) -> Z>(&self, z0: Z, f: F) -> Z
Fold elements in backward order.
Trait Implementations
impl<K: Send, T: Send, Rel: TotalOrderRelation<K>, A: Alloc + Send> Send for BTree<K, T, Rel, A>
[src]
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>
[src]
impl<K: Sync, T: Sync, Rel: TotalOrderRelation<K>, A: Alloc + Sync> Sync for BTree<K, T, Rel, A>
impl<K, T, Rel: TotalOrderRelation<K>, A: Alloc> Drop for BTree<K, T, Rel, A>
[src]
impl<K, T, Rel: TotalOrderRelation<K>, A: Alloc> Drop for BTree<K, T, Rel, A>
impl<K: Debug, T: Debug, Rel: TotalOrderRelation<K>, A: Alloc> Debug for BTree<K, T, Rel, A>
[src]
impl<K: Debug, T: Debug, Rel: TotalOrderRelation<K>, A: Alloc> Debug for BTree<K, T, Rel, A>