Struct TreeMap

pub struct TreeMap<K, V, const PREFIX_LEN: usize = DEFAULT_PREFIX_LEN, A: Allocator = Global> { /* private fields */ }

An ordered map based on an adaptive radix tree.

Implementations

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

pub fn new() -> Self

Create a new, empty TreeMap with the default number of prefix bytes (16).

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());

impl<K, V, A: Allocator> TreeMap<K, V, DEFAULT_PREFIX_LEN, A>

pub fn new_in(alloc: A) -> Self

Create a new, empty TreeMap with the default number of prefix bytes (16), which will allocate tree nodes using the given allocator.

This function will not pre-allocate anything.

impl<K, V, const PREFIX_LEN: usize> TreeMap<K, V, PREFIX_LEN>

pub fn with_prefix_len() -> Self

Create a new, empty TreeMap with a non-default node prefix length.

This function will not pre-allocate anything. The prefix length is inferred as a const-generic parameter on the type.

Examples

use blart::TreeMap;

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

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

where K: AsBytes,

Constructs a TreeMap from a raw node pointer.

Safety

• The raw pointer must have been previously returned by a call to TreeMap::into_raw_with_allocator or TreeMap::into_raw.
  • The allocator of the previous tree must have been the “default” allocator named Global.
• The given root pointer must be unique and there are no other pointers into the tree.

Errors

This function runs a series of checks to ensure that the returned tree is well-formed. See WellFormedChecker for details on the requirements.

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);

let root = TreeMap::into_raw(map);
assert!(root.is_some());

// SAFETY: The root pointer came directly from the `into_raw` result.
let _map = unsafe { TreeMap::from_raw(root) }.unwrap();

impl<K, V, const PREFIX_LEN: usize, A: Allocator> TreeMap<K, V, PREFIX_LEN, A>

pub fn allocator(&self) -> &A

Returns a reference to the underlying allocator.

pub fn with_prefix_len_in(alloc: A) -> Self

Create a new, empty TreeMap with a non-default node prefix length, and the given allocator for allocating tree nodes.

This function will not pre-allocate anything. The prefix length is inferred as a const-generic parameter on the type.

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 into_raw(tree: Self) -> Option<OpaqueNodePtr<K, V, PREFIX_LEN>>

Consume the tree, returning a raw pointer to the root node.

If the results is None, this means the tree is empty.

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);

let root = TreeMap::into_raw(map);
assert!(root.is_some());

// SAFETY: The root pointer came directly from the `into_raw` result.
let _map = unsafe { TreeMap::from_raw(root) }.unwrap();

pub fn into_raw_with_allocator( tree: Self, ) -> (Option<OpaqueNodePtr<K, V, PREFIX_LEN>>, A)

Consume the tree, returning a raw pointer to the root node and the allocator of the tree.

If the results is None, this means the tree is empty.

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);

let (root, alloc) = TreeMap::into_raw_with_allocator(map);
assert!(root.is_some());

// SAFETY: The root pointer came directly from the `into_raw` result.
let _map = unsafe { TreeMap::from_raw_in(root, alloc) }.unwrap();

pub unsafe fn from_raw_in( root: Option<OpaqueNodePtr<K, V, PREFIX_LEN>>, alloc: A, ) -> Result<Self, MalformedTreeError<K, V, PREFIX_LEN>>

where K: AsBytes,

Constructs a TreeMap from a raw node pointer and the given allocator.

Safety

• The raw pointer must have been previously returned by a call to TreeMap::into_raw_with_allocator or TreeMap::into_raw with a known allocator.
• The given root pointer must be unique and there are no other pointers into the tree.
• The given alloc must have been used to allocate all of the nodes referenced by the given root pointer.

Errors

This function runs a series of checks to ensure that the returned tree is well-formed. See WellFormedChecker for details on the requirements.

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 get_prefix<Q>(&self, key: &Q) -> Option<&V>

where K: Borrow<Q> + AsBytes, Q: AsBytes + ?Sized,

Returns a reference to the value corresponding to the leaf that prefixes the given 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_prefix([1, 2, 3, 4, 5].as_ref()).unwrap(), 'a');

pub fn get_prefix_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 value of the leaf that prefixes the given 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_prefix_key_value([1, 2, 3, 4, 5].as_ref()).map(|(k, v)| (k.as_ref(), v)),
    Some(([1, 2, 3].as_ref(), &'a'))
);

pub fn get_prefix_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 leaf that prefixes the given key.

Examples

use blart::TreeMap;

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

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

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

pub fn fuzzy<'a, 'b, Q>( &'a self, key: &'b Q, max_edit_dist: usize, ) -> Fuzzy<'a, 'b, K, V, PREFIX_LEN, A>

where K: Borrow<Q> + AsBytes, Q: AsBytes + ?Sized,

Makes a fuzzy search in the tree by key, returning all keys and values that are less than or equal to max_edit_dist.

This is done by using Levenshtein distance

Examples

use blart::TreeMap;

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

map.insert(c"abc", 0);
map.insert(c"abd", 1);
map.insert(c"abdefg", 2);

let fuzzy: Vec<_> = map.fuzzy(c"ab", 2).collect();
assert_eq!(fuzzy, vec![(&c"abd", &1), (&c"abc", &0)]);

pub fn fuzzy_mut<'a, 'b, Q>( &'a mut self, key: &'b Q, max_edit_dist: usize, ) -> FuzzyMut<'a, 'b, K, V, PREFIX_LEN, A>

where K: Borrow<Q> + AsBytes, Q: AsBytes + ?Sized,

Makes a fuzzy search in the tree by key, returning all keys and values that are less than or equal to max_edit_dist.

This is done by using Levenshtein distance

Examples

use blart::TreeMap;

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

map.insert(c"abc", 0);
map.insert(c"abd", 1);
map.insert(c"abdefg", 2);

let fuzzy: Vec<_> = map.fuzzy_mut(c"ab", 2).collect();
assert_eq!(fuzzy, vec![(&c"abd", &mut 1), (&c"abc", &mut 0)]);

pub fn contains_key<Q>(&self, key: &Q) -> bool

where 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 force_insert(&mut self, key: K, value: V)

where K: AsBytes,

Force inserts a key-value pair into the map.

If the given key is not a prefix of any keys in the tree, this function behaves just like Self::try_insert. If the given key is a prefix of some keys in the tree, or the other way around, all these key value pairs are removed and this key value pair is inserted in their place.

See also: Self::get_prefix and friends.

Examples

use blart::TreeMap;

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

map.force_insert(Box::new([1, 2, 3]), 'a');
map.force_insert(Box::new([2, 3, 4, 5]), 'b');
map.force_insert(Box::new([2, 3, 4, 6]), 'b');
// [2, 3, 4, 5] and [2, 3, 4, 6] are removed and ([2, 3, 4], 'c') is inserted.
map.force_insert(Box::new([2, 3, 4]), 'c');
assert!(map.get([2, 3, 4, 5].as_ref()).is_none());
assert!(map.get([2, 3, 4, 6].as_ref()).is_none());
// ([1, 2, 3], 'a') is replaced by ([1, 2], 'd')
map.force_insert(Box::new([1, 2]), 'd');
assert!(map.get([1, 2, 3].as_ref()).is_none());
assert_eq!(map.get([1, 2].as_ref()), Some(&'d'));

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 fn retain<F>(&mut self, f: F)

where F: FnMut(&K, &mut V) -> bool, K: AsBytes,

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.

Examples

use blart::TreeMap;

let mut map: TreeMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
// Keep only the elements with even-numbered keys.
map.retain(|&k, _| k % 2 == 0);
assert!(map.into_iter().eq(vec![(0, 0), (2, 20), (4, 40), (6, 60)]));

pub fn append(&mut self, other: &mut Self)

where K: NoPrefixesBytes,

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

Examples

use blart::TreeMap;

let mut a = TreeMap::<u128, _>::new();
a.try_insert(1, "a").unwrap();
a.try_insert(2, "b").unwrap();
a.try_insert(3, "c").unwrap(); // Note: Key (3) also present in b.

let mut b = TreeMap::<u128, _>::new();
b.try_insert(3, "d").unwrap(); // Note: Key (3) also present in a.
b.try_insert(4, "e").unwrap();
b.try_insert(5, "f").unwrap();

a.append(&mut b);

assert_eq!(a.len(), 5);
assert_eq!(b.len(), 0);

assert_eq!(a[&1], "a");
assert_eq!(a[&2], "b");
assert_eq!(a[&3], "d"); // Note: "c" has been overwritten.
assert_eq!(a[&4], "e");
assert_eq!(a[&5], "f");

pub fn range<Q, R>(&self, range: R) -> Range<'_, K, V, PREFIX_LEN, A>

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.

Examples

use blart::TreeMap;
use std::ops::Bound::Included;

let mut map = TreeMap::<u8, _>::new();
map.try_insert(3, "a").unwrap();
map.try_insert(5, "b").unwrap();
map.try_insert(8, "c").unwrap();

for (key, &value) in map.range((Included(&4), Included(&8))) {
    println!("{key:?}: {value}");
}
assert_eq!(map.range(&4..).next(), Some((&5, &"b")));

pub fn range_mut<Q, R>(&mut self, range: R) -> RangeMut<'_, K, V, PREFIX_LEN, A>

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.

Examples

use blart::TreeMap;

let mut map: TreeMap<_, i32> = TreeMap::new();

for (key, value) in [("Alice", 0), ("Bob", 0), ("Carol", 0), ("Cheryl", 0)] {
    let _ = map.try_insert(key, value).unwrap();
}

for (name, balance) in map.range_mut("B"..="Cheryl") {
    *balance += 100;

    if name.starts_with('C') {
        *balance *= 2;
    }
}

for (name, balance) in &map {
    println!("{name} => {balance}");
}

assert_eq!(map["Alice"], 0);
assert_eq!(map["Bob"], 100);
assert_eq!(map["Carol"], 200);
assert_eq!(map["Cheryl"], 200);

pub fn split_off<Q>(&mut self, split_key: &Q) -> TreeMap<K, V, PREFIX_LEN, A>

where K: Borrow<Q> + AsBytes, Q: AsBytes + ?Sized, A: Clone,

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

Examples

use blart::TreeMap;

let mut a = TreeMap::new();
a.try_insert(1, "a").unwrap();
a.try_insert(2, "b").unwrap();
a.try_insert(3, "c").unwrap();
a.try_insert(17, "d").unwrap();
a.try_insert(41, "e").unwrap();

let b = a.split_off(&3);

assert_eq!(a.len(), 2);
assert_eq!(b.len(), 3);

assert_eq!(a[&1], "a");
assert_eq!(a[&2], "b");

assert_eq!(b[&3], "c");
assert_eq!(b[&17], "d");
assert_eq!(b[&41], "e");

pub fn extract_if<R, F>( &mut self, range: R, pred: F, ) -> ExtractIf<'_, K, V, F, PREFIX_LEN, A>

where K: AsBytes, R: RangeBounds<K>, F: FnMut(&K, &mut V) -> bool,

Creates an iterator that visits elements (key-value pairs) in the specified range 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 returned ExtractIf is not exhausted, e.g. because it is dropped without iterating or the iteration short-circuits, then the remaining elements will be retained. Use retain with a negated predicate if you do not need the returned iterator.

Examples

use blart::TreeMap;

// Splitting a map into even and odd keys, reusing the original map:
let mut map: TreeMap<u8, u8> = (0..8).map(|x| (x, x)).collect();
let evens: TreeMap<_, _> = map.extract_if(.., |k, _v| k % 2 == 0).collect();
let odds = map;
assert_eq!(evens.keys().copied().collect::<Vec<_>>(), [0, 2, 4, 6]);
assert_eq!(odds.keys().copied().collect::<Vec<_>>(), [1, 3, 5, 7]);

// Splitting a map into low and high halves, reusing the original map:
let mut map: TreeMap<u8, u8> = (0..8).map(|x| (x, x)).collect();
let low: TreeMap<_, _> = map.extract_if(0..4, |_k, _v| true).collect();
let high = map;
assert_eq!(low.keys().copied().collect::<Vec<_>>(), [0, 1, 2, 3]);
assert_eq!(high.keys().copied().collect::<Vec<_>>(), [4, 5, 6, 7]);

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

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, PREFIX_LEN, A>

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, PREFIX_LEN, A>

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, PREFIX_LEN, A>

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, PREFIX_LEN, A>

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, PREFIX_LEN, A>

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, PREFIX_LEN, A>

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 prefix(&self, prefix: &[u8]) -> Prefix<'_, K, V, PREFIX_LEN, A>

where K: AsBytes,

Gets an iterator over the entries of the map that start with prefix

Examples

use blart::TreeMap;

let mut map = TreeMap::new();
map.insert(c"abcde", 0);
map.insert(c"abcdexxx", 0);
map.insert(c"abcdexxy", 0);
map.insert(c"abcdx", 0);
map.insert(c"abcx", 0);
map.insert(c"bx", 0);

let p: Vec<_> = map.prefix(c"abcde".to_bytes()).collect();

assert_eq!(p, vec![(&c"abcde", &0), (&c"abcdexxx", &0), (&c"abcdexxy", &0)]);

pub fn prefix_mut( &mut self, prefix: &[u8], ) -> PrefixMut<'_, K, V, PREFIX_LEN, A>

where K: AsBytes,

Gets a mutable iterator over the entries of the map that start with prefix

Examples

use blart::TreeMap;

let mut map = TreeMap::new();
map.insert(c"abcde", 0);
map.insert(c"abcdexxx", 0);
map.insert(c"abcdexxy", 0);
map.insert(c"abcdx", 0);
map.insert(c"abcx", 0);
map.insert(c"bx", 0);

let p: Vec<_> = map.prefix_mut(c"abcde".to_bytes()).collect();

assert_eq!(p, vec![(&c"abcde", &mut 0), (&c"abcdexxx", &mut 0), (&c"abcdexxy", &mut 0)]);

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());

impl<K, V, const PREFIX_LEN: usize, A: Allocator> TreeMap<K, V, PREFIX_LEN, A>

pub fn try_entry( &mut self, key: K, ) -> Result<Entry<'_, K, V, PREFIX_LEN, A>, InsertPrefixError>

where K: AsBytes,

Tries to get the given key’s corresponding entry in the map for in-place manipulation.

pub fn entry(&mut self, key: K) -> Entry<'_, K, V, PREFIX_LEN, A>

where K: NoPrefixesBytes,

Gets the given key’s corresponding entry in the map for in-place manipulation.

Trait Implementations

impl<K, V, A, const PREFIX_LEN: usize> Clone for TreeMap<K, V, PREFIX_LEN, A>

where K: Clone + AsBytes, V: Clone, A: Allocator + Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K, V, A, const PREFIX_LEN: usize> Debug for TreeMap<K, V, PREFIX_LEN, A>

where K: Debug, V: Debug, A: Allocator,

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

Formats the value using the given formatter.

impl<K, V, const PREFIX_LEN: usize> Default for TreeMap<K, V, PREFIX_LEN>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V, const PREFIX_LEN: usize, A: Allocator> Drop for TreeMap<K, V, PREFIX_LEN, A>

fn drop(&mut self)

Executes the destructor for this type.

impl<'a, K, V, A, const PREFIX_LEN: usize> Extend<(&'a K, &'a V)> for TreeMap<K, V, PREFIX_LEN, A>

where K: Copy + NoPrefixesBytes, V: Copy, A: Allocator,

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, A, const PREFIX_LEN: usize> Extend<(K, V)> for TreeMap<K, V, PREFIX_LEN, A>

where K: NoPrefixesBytes, A: Allocator,

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 PREFIX_LEN: usize, const N: usize> From<[(K, V); N]> for TreeMap<K, V, PREFIX_LEN>

where K: NoPrefixesBytes,

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

Converts to this type from the input type.

impl<K, V, const PREFIX_LEN: usize> FromIterator<(K, V)> for TreeMap<K, V, PREFIX_LEN>

where K: NoPrefixesBytes,

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

Creates a value from an iterator.

impl<K, V, A, const PREFIX_LEN: usize> Hash for TreeMap<K, V, PREFIX_LEN, A>

where K: Hash, V: Hash, A: Allocator,

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, A, const PREFIX_LEN: usize> Index<&Q> for TreeMap<K, V, PREFIX_LEN, A>

where K: Borrow<Q> + AsBytes, Q: AsBytes + ?Sized, A: Allocator,

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, const PREFIX_LEN: usize, A: Allocator> IntoIterator for &'a TreeMap<K, V, PREFIX_LEN, A>

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

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, const PREFIX_LEN: usize, A: Allocator> IntoIterator for &'a mut TreeMap<K, V, PREFIX_LEN, A>

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

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, const PREFIX_LEN: usize, A: Allocator> IntoIterator for TreeMap<K, V, PREFIX_LEN, A>

type IntoIter = IntoIter<K, V, PREFIX_LEN, A>

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, A, const PREFIX_LEN: usize> Ord for TreeMap<K, V, PREFIX_LEN, A>

where K: Ord, V: Ord, A: Allocator,

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

This method returns an Ordering between self and other.

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

where Self: Sized,

Compares and returns the maximum of two values.

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

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<K, V, A, const PREFIX_LEN: usize> PartialEq for TreeMap<K, V, PREFIX_LEN, A>

where K: PartialEq, V: PartialEq, A: Allocator,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K, V, A, const PREFIX_LEN: usize> PartialOrd for TreeMap<K, V, PREFIX_LEN, A>

where K: PartialOrd, V: PartialOrd, A: Allocator,

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

Tests less than (for self and other) and is used by the < operator.

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

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

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

Tests greater than (for self and other) and is used by the > operator.

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

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

impl<K, V, A, const PREFIX_LEN: usize> Eq for TreeMap<K, V, PREFIX_LEN, A>

where K: Eq, V: Eq, A: Allocator,

impl<K, V, A, const PREFIX_LEN: usize> Send for TreeMap<K, V, PREFIX_LEN, A>

where K: Send, V: Send, A: Send + Allocator,

impl<K, V, A, const PREFIX_LEN: usize> Sync for TreeMap<K, V, PREFIX_LEN, A>

where K: Sync, V: Sync, A: Sync + Allocator,