Struct blart::TreeMap

pub struct TreeMap<K, V> {
    num_entries: usize,
    root: Option<OpaqueNodePtr<K, V>>,
}

An ordered map based on an adaptive radix tree.

Fields

num_entries: usize

The number of entries present in the tree.

root: Option<OpaqueNodePtr<K, V>>

A pointer to the tree root, if present.

Implementations

impl<K, V> TreeMap<K, V>

pub fn new() -> Self

Create a new, empty TreeMap.

This function will not pre-allocate anything.

Examples

use blart::TreeMap;

let map = TreeMap::<Box<[u8]>, ()>::new();
assert_eq!(map, TreeMap::new());
assert!(map.is_empty());

pub fn into_raw(self) -> Option<OpaqueNodePtr<K, V>>

Convert tree into a pointer to pointer to the root node.

If there are no elements in the tree, then returns None.

Examples

use blart::{TreeMap, deallocate_tree};

let mut map = TreeMap::<Box<[u8]>, char>::new();
map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();

let root = map.into_raw().unwrap();

// SAFETY: No other operation are access or mutating tree while dealloc happens
unsafe { deallocate_tree(root) }

pub unsafe fn from_raw(root: Option<OpaqueNodePtr<K, V>>) -> Self

Constructs a tree from a pointer to the root node.

If None is passed, it constructs an empty tree.

Safety

The pointer passed to this function must not be used in a second call to from_raw, otherwise multiple safety issues could occur.

Similarly, no other function can mutate the content of the tree under root while this function executes.

Examples

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();

let root = map.into_raw();
// SAFETY: The tree root came from previous `into_raw` call
let map2 = unsafe { TreeMap::from_raw(root) };

assert_eq!(map2[[1, 2, 3].as_ref()], 'a');

pub fn clear(&mut self)

Clear the map, removing all elements.

Examples

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();
assert_eq!(map.len(), 1);

map.clear();
assert!(map.is_empty());
assert!(map.get([1, 2, 3].as_ref()).is_none());

pub fn get<Q>(&self, key: &Q) -> Option<&V>where K: Borrow<Q> + AsBytes, Q: AsBytes + ?Sized,

Returns a reference to the value corresponding to the key.

Examples

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();
assert_eq!(*map.get([1, 2, 3].as_ref()).unwrap(), 'a');

pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>where K: Borrow<Q> + AsBytes, Q: AsBytes + ?Sized,

Returns the key-value pair corresponding to the supplied key.

Examples

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();
assert_eq!(map.get_key_value([1, 2, 3].as_ref()).unwrap(), (&Box::from([1, 2, 3]), &'a'));

pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>where K: Borrow<Q> + AsBytes, Q: AsBytes + ?Sized,

Returns a mutable reference to the value corresponding to the key.

Examples

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();
assert_eq!(map[[1, 2, 3].as_ref()], 'a');

*map.get_mut([1, 2, 3].as_ref()).unwrap() = 'b';
assert_eq!(map[[1, 2, 3].as_ref()], 'b');

While an element from the tree is mutably referenced, no other operation on the tree can happen.

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();


let value = map.get_mut(&[1, 2, 3]).unwrap();
assert_eq!(*value, 'a');

assert_eq!(*map[[1, 2, 3].as_ref()], 'a');

*value = 'b';
drop(value);

pub fn contains_key<Q>(&self, key: &Q) -> boolwhere K: Borrow<Q> + AsBytes, Q: AsBytes + ?Sized,

Returns true if the map contains a value for the specified key.

Examples

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();

assert!(map.contains_key([1, 2, 3].as_ref()));

pub fn first_key_value(&self) -> Option<(&K, &V)>

Returns the first key-value pair in the map. The key in this pair is the minimum key in the map.

If the tree is empty, returns None.

Examples

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();

assert_eq!(map.first_key_value().unwrap(), (&[1, 2, 3].into(), &'a'));

pub fn pop_first(&mut self) -> Option<(K, V)>

Removes and returns the first element in the map. The key of this element is the minimum key that was in the map.

If the tree is empty, returns None.

Examples

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();

assert_eq!(map.pop_first().unwrap(), (Box::from([1, 2, 3]), 'a'));

pub fn last_key_value(&self) -> Option<(&K, &V)>

Returns the last key-value pair in the map. The key in this pair is the maximum key in the map.

If the tree is empty, returns None.

Examples

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();
map.try_insert(Box::new([2, 3, 4]), 'b').unwrap();

assert_eq!(map.last_key_value().unwrap(), (&Box::from([2, 3, 4]), &'b'));

pub fn pop_last(&mut self) -> Option<(K, V)>

Removes and returns the last element in the map. The key of this element is the maximum key that was in the map.

If the tree is empty, returns None.

Examples

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();
map.try_insert(Box::new([2, 3, 4]), 'b').unwrap();

assert_eq!(map.pop_last().unwrap(), (Box::from([2, 3, 4]), 'b'));

pub fn insert(&mut self, key: K, value: V) -> Option<V>where K: NoPrefixesBytes,

Insert a key-value pair into the map.

If the map did not have this key present, Ok(None) is returned.

If the map did have this key present, the value is updated, and the old value is returned.

Unlike try_insert, this function will not return an error, because the contract of the NoPrefixesBytes ensures that the given key type will never be a prefix of an existing value.

Examples

use blart::TreeMap;

let mut map = TreeMap::<u128, char>::new();

assert!(map.insert(123, 'a').is_none());
assert!(map.insert(234, 'b').is_none());
assert_eq!(map.insert(234, 'c'), Some('b'));

assert_eq!(map.len(), 2);

pub fn try_insert( &mut self, key: K, value: V ) -> Result<Option<V>, InsertPrefixError>where K: AsBytes,

Inserts a key-value pair into the map.

If the map did not have this key present, Ok(None) is returned.

If the map did have this key present, the value is updated, and the old value is returned.

Errors

• If the map has an existing key, such that the new key is a prefix of the existing key or vice versa, then it returns an error.

Examples

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

assert!(map.try_insert(Box::new([1, 2, 3]), 'a').unwrap().is_none());
assert!(map.try_insert(Box::new([2, 3, 4]), 'b').unwrap().is_none());
// This function call errors because the key is a prefix of the existing key
assert!(map.try_insert(Box::new([2, 3, 4, 5]), 'c').is_err());
assert_eq!(map.try_insert(Box::new([2, 3, 4]), 'd').unwrap(), Some('b'));

assert_eq!(map.len(), 2);

pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>where K: Borrow<Q> + AsBytes, Q: AsBytes + ?Sized,

Removes a key from the map, returning the stored key and value if the key was previously in the map.

Examples

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();
map.try_insert(Box::new([2, 3, 4]), 'b').unwrap();

assert_eq!(map.remove_entry([2, 3, 4].as_ref()).unwrap(), (Box::from([2, 3, 4]), 'b'))

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>where K: Borrow<Q> + AsBytes, Q: AsBytes + ?Sized,

Removes a key from the map, returning the value at the key if the key was previously in the map.

Examples

use blart::TreeMap;

let mut map = TreeMap::<Box<[u8]>, char>::new();

map.try_insert(Box::new([1, 2, 3]), 'a').unwrap();
map.try_insert(Box::new([2, 3, 4]), 'b').unwrap();

assert_eq!(map.remove([2, 3, 4].as_ref()).unwrap(), 'b');
assert_eq!(map.remove([2, 3, 4].as_ref()), None);

pub(crate) fn retain<F>(&mut self, f: F)where F: FnMut(&K, &mut V) -> bool,

Retains only the elements specified by the predicate.

In other words, remove all pairs (k, v) for which f(&k, &mut v) returns false. The elements are visited in ascending key order.

pub(crate) fn append(&mut self, other: &mut TreeMap<K, V>)where K: NoPrefixesBytes,

Moves all elements from other into self, leaving other empty.

pub(crate) fn range<Q, R>(&self, _range: R) -> Range<'_, K, V> where Q: AsBytes + ?Sized, K: Borrow<Q> + AsBytes, R: RangeBounds<Q>,

Constructs a double-ended iterator over a sub-range of elements in the map.

The simplest way is to use the range syntax min..max, thus range(min..max) will yield elements from min (inclusive) to max (exclusive). The range may also be entered as (Bound<T>, Bound<T>), so for example range((Excluded(4), Included(10))) will yield a left-exclusive, right-inclusive range from 4 to 10.

pub(crate) fn range_mut<Q, R>(&mut self, _range: R) -> RangeMut<'_, K, V> where Q: AsBytes + ?Sized, K: Borrow<Q> + AsBytes, R: RangeBounds<Q>,

Constructs a mutable double-ended iterator over a sub-range of elements in the map.

The simplest way is to use the range syntax min..max, thus range+_mut(min..max) will yield elements from min (inclusive) to max (exclusive). The range may also be entered as (Bound<T>, Bound<T>), so for example range_mut((Excluded(4), Included(10))) will yield a left-exclusive, right-inclusive range from 4 to 10.

pub(crate) fn split_off<Q>(&mut self, split_key: &Q) -> TreeMap<K, V>where K: Borrow<Q> + AsBytes, Q: AsBytes + ?Sized,

Splits the collection into two at the given key. Returns everything after the given key, including the key.

pub(crate) fn drain_filter<F>(&mut self, _pred: F) -> DrainFilter<K, V> where F: FnMut(&K, &mut V) -> bool,

Creates an iterator that visits all elements (key-value pairs) in ascending key order and uses a closure to determine if an element should be removed.

If the closure returns true, the element is removed from the map and yielded. If the closure returns false, or panics, the element remains in the map and will not be yielded.

The iterator also lets you mutate the value of each element in the closure, regardless of whether you choose to keep or remove it.

If the iterator is only partially consumed or not consumed at all, each of the remaining elements is still subjected to the closure, which may change its value and, by returning true, have the element removed and dropped.

It is unspecified how many more elements will be subjected to the closure if a panic occurs in the closure, or a panic occurs while dropping an element, or if the DrainFilter value is leaked.

pub fn into_keys(self) -> IntoKeys<K, V>

Creates a consuming iterator visiting all the keys, in sorted order. The map cannot be used after calling this. The iterator element type is K.

Examples

use blart::TreeMap;

let map: TreeMap<_, char> = ['d', 'c', 'b', 'a', 'z'].into_iter()
    .enumerate()
    .collect();

let mut iter = map.into_keys();

assert_eq!(iter.next().unwrap(), 0);
assert_eq!(iter.next().unwrap(), 1);
assert_eq!(iter.next().unwrap(), 2);
assert_eq!(iter.next().unwrap(), 3);
assert_eq!(iter.next().unwrap(), 4);
assert_eq!(iter.next(), None);

pub fn into_values(self) -> IntoValues<K, V>

Creates a consuming iterator visiting all the values, in order by key. The map cannot be used after calling this. The iterator element type is V.

Examples

use blart::TreeMap;

let map: TreeMap<_, char> = ['d', 'c', 'b', 'a', 'z'].into_iter()
    .enumerate()
    .collect();

let mut iter = map.into_values();

assert_eq!(iter.next().unwrap(), 'd');
assert_eq!(iter.next().unwrap(), 'c');
assert_eq!(iter.next().unwrap(), 'b');
assert_eq!(iter.next().unwrap(), 'a');
assert_eq!(iter.next().unwrap(), 'z');
assert_eq!(iter.next(), None);

pub fn iter(&self) -> Iter<'_, K, V>

Gets an iterator over the entries of the map, sorted by key.

Examples

use blart::TreeMap;

let map: TreeMap<_, char> = ['d', 'c', 'b', 'a', 'z'].into_iter()
    .enumerate()
    .collect();

let mut iter = map.iter();

assert_eq!(iter.next().unwrap(), (&0, &'d'));
assert_eq!(iter.next().unwrap(), (&1, &'c'));
assert_eq!(iter.next().unwrap(), (&2, &'b'));
assert_eq!(iter.next().unwrap(), (&3, &'a'));
assert_eq!(iter.next().unwrap(), (&4, &'z'));
assert_eq!(iter.next(), None);

pub fn iter_mut(&mut self) -> IterMut<'_, K, V>

Gets a mutable iterator over the entries of the map, sorted by key.

Examples

use blart::TreeMap;

let mut map: TreeMap<_, char> = ['d', 'c', 'b', 'a', 'z'].into_iter()
    .enumerate()
    .collect();

for (_key, value) in map.iter_mut() {
    value.make_ascii_uppercase();
}

assert_eq!(map[&0], 'D');
assert_eq!(map[&1], 'C');
assert_eq!(map[&2], 'B');
assert_eq!(map[&3], 'A');
assert_eq!(map[&4], 'Z');

pub fn keys(&self) -> Keys<'_, K, V>

Gets an iterator over the keys of the map, in sorted order.

Examples

use blart::TreeMap;

let map: TreeMap<_, char> = ['d', 'c', 'b', 'a', 'z'].into_iter()
    .enumerate()
    .collect();

let mut iter = map.keys();

assert_eq!(iter.next().unwrap(), &0);
assert_eq!(iter.next().unwrap(), &1);
assert_eq!(iter.next().unwrap(), &2);
assert_eq!(iter.next().unwrap(), &3);
assert_eq!(iter.next().unwrap(), &4);
assert_eq!(iter.next(), None);

pub fn values(&self) -> Values<'_, K, V>

Gets an iterator over the values of the map, in order by key.

Examples

use blart::TreeMap;

let map: TreeMap<_, char> = ['d', 'c', 'b', 'a', 'z'].into_iter()
    .enumerate()
    .collect();

let mut iter = map.values();

assert_eq!(iter.next().unwrap(), &'d');
assert_eq!(iter.next().unwrap(), &'c');
assert_eq!(iter.next().unwrap(), &'b');
assert_eq!(iter.next().unwrap(), &'a');
assert_eq!(iter.next().unwrap(), &'z');
assert_eq!(iter.next(), None);

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V>

Gets a mutable iterator over the values of the map, in order by key.

Examples

use blart::TreeMap;

let mut map: TreeMap<_, char> = ['d', 'c', 'b', 'a', 'z'].into_iter()
    .enumerate()
    .collect();

for value in map.values_mut() {
    value.make_ascii_uppercase();
}

assert_eq!(map[&0], 'D');
assert_eq!(map[&1], 'C');
assert_eq!(map[&2], 'B');
assert_eq!(map[&3], 'A');
assert_eq!(map[&4], 'Z');

pub fn len(&self) -> usize

Returns the number of elements in the map.

Examples

use blart::TreeMap;

let map: TreeMap<_, char> = ['d', 'c', 'b', 'a', 'z'].into_iter()
    .enumerate()
    .collect();

assert_eq!(map.len(), 5);

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

Examples

use blart::TreeMap;

let map = TreeMap::<Box<[u8]>, ()>::new();
assert!(map.is_empty());

Trait Implementations

impl<K, V> Clone for TreeMap<K, V>where K: Clone + AsBytes, V: Clone,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K, V> Debug for TreeMap<K, V>where K: Debug, V: Debug,

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

Formats the value using the given formatter.

impl<K, V> Default for TreeMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> Drop for TreeMap<K, V>

fn drop(&mut self)

Executes the destructor for this type.

impl<'a, K, V> Extend<(&'a K, &'a V)> for TreeMap<K, V>where K: Copy + NoPrefixesBytes, V: Copy,

fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V> Extend<(K, V)> for TreeMap<K, V>where K: NoPrefixesBytes,

fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V, const N: usize> From<[(K, V); N]> for TreeMap<K, V>where K: NoPrefixesBytes,

fn from(arr: [(K, V); N]) -> Self

Converts to this type from the input type.

impl<K, V> FromIterator<(K, V)> for TreeMap<K, V>where K: NoPrefixesBytes,

fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self

Creates a value from an iterator.

impl<K, V> Hash for TreeMap<K, V>where K: Hash, V: Hash,

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<Q, K, V> Index<&Q> for TreeMap<K, V>where K: Borrow<Q> + AsBytes, Q: AsBytes + ?Sized,

type Output = V

The returned type after indexing.

fn index(&self, index: &Q) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<'a, K, V> IntoIterator for &'a TreeMap<K, V>

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V> IntoIterator for &'a mut TreeMap<K, V>

type IntoIter = IterMut<'a, K, V>

Which kind of iterator are we turning this into?

type Item = (&'a K, &'a mut V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V> IntoIterator for TreeMap<K, V>

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

type Item = (K, V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V> Ord for TreeMap<K, V>where K: Ord, V: Ord,

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Selfwhere Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Selfwhere Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Selfwhere Self: Sized + PartialOrd<Self>,

Restrict a value to a certain interval.

impl<K, V> PartialEq<TreeMap<K, V>> for TreeMap<K, V>where K: PartialEq, V: PartialEq,

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<K, V> PartialOrd<TreeMap<K, V>> for TreeMap<K, V>where K: PartialOrd, V: PartialOrd,

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

This method tests less than (for self and other) and is used by the < operator.

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

This method tests less than or equal to (for self and other) and is used by the <= operator.

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

This method tests greater than (for self and other) and is used by the > operator.

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

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<K, V> Eq for TreeMap<K, V>where K: Eq, V: Eq,