Struct BTreeMap 

pub struct BTreeMap<K, V, C> { /* private fields */ }

A map based on a B-Tree.

This offers an alternative over the standard implementation of B-Trees where nodes are allocated in a contiguous array of Nodes, reducing the cost of tree nodes allocations. In addition the crate provides advanced functions to iterate through and update the map efficiently.

Basic usage

Basic usage is similar to the map data structures offered by the standard library.

use btree_slab::BTreeMap;

// type inference lets us omit an explicit type signature (which
// would be `BTreeMap<&str, &str>` in this example).
let mut movie_reviews = BTreeMap::new();

// review some movies.
movie_reviews.insert("Office Space",       "Deals with real issues in the workplace.");
movie_reviews.insert("Pulp Fiction",       "Masterpiece.");
movie_reviews.insert("The Godfather",      "Very enjoyable.");
movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot.");

// check for a specific one.
if !movie_reviews.contains_key("Les Misérables") {
    println!("We've got {} reviews, but Les Misérables ain't one.",
             movie_reviews.len());
}

// oops, this review has a lot of spelling mistakes, let's delete it.
movie_reviews.remove("The Blues Brothers");

// look up the values associated with some keys.
let to_find = ["Up!", "Office Space"];
for movie in &to_find {
    match movie_reviews.get(movie) {
       Some(review) => println!("{}: {}", movie, review),
       None => println!("{} is unreviewed.", movie)
    }
}

// Look up the value for a key (will panic if the key is not found).
println!("Movie review: {}", movie_reviews["Office Space"]);

// iterate over everything.
for (movie, review) in &movie_reviews {
    println!("{}: \"{}\"", movie, review);
}

Advanced usage

Entry API

This crate also reproduces the Entry API defined by the standard library, which allows for more complex methods of getting, setting, updating and removing keys and their values:

use btree_slab::BTreeMap;

// type inference lets us omit an explicit type signature (which
// would be `BTreeMap<&str, u8>` in this example).
let mut player_stats: BTreeMap<&str, u8> = BTreeMap::new();

fn random_stat_buff() -> u8 {
    // could actually return some random value here - let's just return
    // some fixed value for now
    42
}

// insert a key only if it doesn't already exist
player_stats.entry("health").or_insert(100);

// insert a key using a function that provides a new value only if it
// doesn't already exist
player_stats.entry("defence").or_insert_with(random_stat_buff);

// update a key, guarding against the key possibly not being set
let stat = player_stats.entry("attack").or_insert(100);
*stat += random_stat_buff();

Mutable iterators

This type provides two iterators providing mutable references to the entries:

• IterMut is a double-ended iterator following the standard std::collections::btree_map::IterMut implementation.
• EntriesMut is a single-ended iterator that allows, in addition, insertion and deletion of entries at the current iterator’s position in the map. An example is given below.

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("d", 4);

let mut entries = map.entries_mut();
entries.next();
entries.next();
entries.insert("c", 3); // the inserted key must preserve the order of the map.

let entries: Vec<_> = map.into_iter().collect();
assert_eq!(entries, vec![("a", 1), ("b", 2), ("c", 3), ("d", 4)]);

Custom allocation

This data structure is built on top of a slab data structure, but is agnostic of the actual slab implementation which is taken as parameter (C). If the slab feature is enabled, the slab::Slab implementation is used by default by reexporting BTreeMap<K, V, slab::Slab<_>> at the root of the crate. Any container implementing “slab-like” functionalities can be used.

Extended API

This crate provides the two traits BTreeExt and BTreeExtMut that can be imported to expose low-level operations on BTreeMap. The extended API allows the caller to directly navigate and access the entries of the tree using their Address. These functions are not intended to be directly called by the users, but can be used to extend the data structure with new functionalities.

Correctness

It is a logic error for a key to be modified in such a way that the key’s ordering relative to any other key, as determined by the Ord trait, changes while it is in the map. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code.

Implementations

impl<K, V, C> BTreeMap<K, V, C>

pub fn new() -> BTreeMap<K, V, C>

where C: Default,

Create a new empty B-tree.

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

Example

use btree_slab::BTreeMap;

let mut a = BTreeMap::new();
assert!(a.is_empty());
a.insert(1, "a");
assert!(!a.is_empty());

pub fn len(&self) -> usize

Returns the number of elements in the map.

Example

use btree_slab::BTreeMap;

let mut a = BTreeMap::new();
assert_eq!(a.len(), 0);
a.insert(1, "a");
assert_eq!(a.len(), 1);

impl<K, V, C> BTreeMap<K, V, C>

where C: SimpleCollectionRef + Slab<Node<K, V>>,

pub fn get<Q>(&self, key: &Q) -> Option<&V>

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

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

The supplied key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.

Example

use btree_slab::BTreeMap;

let mut map: BTreeMap<i32, &str> = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
assert_eq!(map.get_key_value(&2), None);

pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)>

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

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

The supplied key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.

Examples

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
assert_eq!(map.get_key_value(&2), None);

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.

Example

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
assert_eq!(map.first_key_value(), None);
map.insert(1, "b");
map.insert(2, "a");
assert_eq!(map.first_key_value(), Some((&1, &"b")));

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.

Examples

Basic usage:

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "b");
map.insert(2, "a");
assert_eq!(map.last_key_value(), Some((&2, &"a")));

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

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

Example

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
map.insert(3, "c");
map.insert(2, "b");
map.insert(1, "a");

for (key, value) in map.iter() {
    println!("{}: {}", key, value);
}

let (first_key, first_value) = map.iter().next().unwrap();
assert_eq!((*first_key, *first_value), (1, "a"));

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

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

Example

use btree_slab::BTreeMap;

let mut a = BTreeMap::new();
a.insert(2, "b");
a.insert(1, "a");

let keys: Vec<_> = a.keys().cloned().collect();
assert_eq!(keys, [1, 2]);

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

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

Example

use btree_slab::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, "hello");
a.insert(2, "goodbye");

let values: Vec<&str> = a.values().cloned().collect();
assert_eq!(values, ["hello", "goodbye"]);

pub fn range<T, R>(&self, range: R) -> Range<'_, K, V, C>

where T: Ord + ?Sized, K: Borrow<T>, R: RangeBounds<T>,

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.

Panics

Panics if range start > end. Panics if range start == end and both bounds are Excluded.

Example

use btree_slab::BTreeMap;
use std::ops::Bound::Included;

let mut map = BTreeMap::new();
map.insert(3, "a");
map.insert(5, "b");
map.insert(8, "c");
for (&key, &value) in map.range((Included(&4), Included(&8))) {
    println!("{}: {}", key, value);
}
assert_eq!(Some((&5, &"b")), map.range(4..).next());

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

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

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

The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.

Example

use btree_slab::BTreeMap;

let mut map: BTreeMap<i32, &str> = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.contains_key(&1), true);
assert_eq!(map.contains_key(&2), false);

impl<K, V, C> BTreeMap<K, V, C>

where C: SimpleCollectionRef + SimpleCollectionMut + SlabMut<Node<K, V>>,

pub fn clear(&mut self)

where C: Clear,

Clears the map, removing all elements.

Example

use btree_slab::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, "a");
a.clear();
assert!(a.is_empty());

pub fn get_mut(&mut self, key: &K) -> Option<&mut V>

where K: Ord,

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

The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.

Example

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
if let Some(x) = map.get_mut(&1) {
    *x = "b";
}
assert_eq!(map[&1], "b");

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

where K: Ord,

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

Example

use btree_slab::BTreeMap;

let mut letters = BTreeMap::new();

for ch in "a short treatise on fungi".chars() {
    let counter = letters.entry(ch).or_insert(0);
    *counter += 1;
}

assert_eq!(letters[&'s'], 2);
assert_eq!(letters[&'t'], 3);
assert_eq!(letters[&'u'], 1);
assert_eq!(letters.get(&'y'), None);

pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, C>>

Returns the first entry in the map for in-place manipulation. The key of this entry is the minimum key in the map.

Example

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
map.insert(2, "b");
if let Some(mut entry) = map.first_entry() {
    if *entry.key() > 0 {
        entry.insert("first");
    }
}
assert_eq!(*map.get(&1).unwrap(), "first");
assert_eq!(*map.get(&2).unwrap(), "b");

pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, C>>

Returns the last entry in the map for in-place manipulation. The key of this entry is the maximum key in the map.

Example

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
map.insert(2, "b");
if let Some(mut entry) = map.last_entry() {
    if *entry.key() > 0 {
        entry.insert("last");
    }
}
assert_eq!(*map.get(&1).unwrap(), "a");
assert_eq!(*map.get(&2).unwrap(), "last");

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

where K: Ord,

Insert a key-value pair in the tree.

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

where K: Ord,

Replace a key-value pair in the tree.

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.

Example

Draining elements in ascending order, while keeping a usable map each iteration.

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
map.insert(2, "b");
while let Some((key, _val)) = map.pop_first() {
    assert!(map.iter().all(|(k, _v)| *k > key));
}
assert!(map.is_empty());

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.

Example

Draining elements in descending order, while keeping a usable map each iteration.

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
map.insert(2, "b");
while let Some((key, _val)) = map.pop_last() {
    assert!(map.iter().all(|(k, _v)| *k < key));
}
assert!(map.is_empty());

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>

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

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

The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.

Example

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.remove(&1), Some("a"));
assert_eq!(map.remove(&1), None);

pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>

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

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

The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.

Example

Basic usage:

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.remove_entry(&1), Some((1, "a")));
assert_eq!(map.remove_entry(&1), None);

pub fn take<Q>(&mut self, key: &Q) -> Option<(K, V)>

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

Removes and returns the binding in the map, if any, of which key matches the given one.

pub fn update<T, F>(&mut self, key: K, action: F) -> T

where K: Ord, F: FnOnce(Option<V>) -> (Option<V>, T),

General-purpose update function.

This can be used to insert, compare, replace or remove the value associated to the given key in the tree. The action to perform is specified by the action function. This function is called once with:

• Some(value) when value is aready associated to key or
• None when the key is not associated to any value.

The action function must return a pair (new_value, result) where new_value is the new value to be associated to key (if it is None any previous binding is removed) and result is the value returned by the entire update function call.

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

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

Example

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);

// add 10 to the value if the key isn't "a"
for (key, value) in map.iter_mut() {
    if key != &"a" {
        *value += 10;
    }
}

pub fn entries_mut(&mut self) -> EntriesMut<'_, K, V, C>

Gets a mutable iterator over the entries of the map, sorted by key, that allows insertion and deletion of the iterated entries.

Correctness

It is safe to insert any key-value pair while iterating, however this might break the well-formedness of the underlying tree, which relies on several invariants. To preserve these invariants, the inserted key must be strictly greater than the previous visited item’s key, and strictly less than the next visited item (which you can retrive through EntriesMut::peek without moving the iterator). If this rule is not respected, the data structure will become unusable (invalidate the specification of every method of the API).

Example

use btree_slab::BTreeMap;

let mut map = BTreeMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("d", 4);

let mut entries = map.entries_mut();
entries.next();
entries.next();
entries.insert("c", 3);

let entries: Vec<_> = map.into_iter().collect();
assert_eq!(entries, vec![("a", 1), ("b", 2), ("c", 3), ("d", 4)]);

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

where T: Ord + ?Sized, K: Borrow<T>, R: RangeBounds<T>,

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(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.

Panics

Panics if range start > end. Panics if range start == end and both bounds are Excluded.

Example

use btree_slab::BTreeMap;

let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"]
    .iter()
    .map(|&s| (s, 0))
    .collect();
for (_, balance) in map.range_mut("B".."Cheryl") {
    *balance += 100;
}
for (name, balance) in &map {
    println!("{} => {}", name, balance);
}

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

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

Example

use btree_slab::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, String::from("hello"));
a.insert(2, String::from("goodbye"));

for value in a.values_mut() {
    value.push_str("!");
}

let values: Vec<String> = a.values().cloned().collect();
assert_eq!(values, [String::from("hello!"),
                    String::from("goodbye!")]);

pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, K, V, C, F>

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

Creates an iterator which 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.

Note that drain_filter lets you mutate every value in the filter 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 will still be subjected to the closure and removed and dropped if it returns true.

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.

Example

Splitting a map into even and odd keys, reusing the original map:

use btree_slab::BTreeMap;

let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
let evens: BTreeMap<_, _> = map.drain_filter(|k, _v| k % 2 == 0).collect();
let odds = map;
assert_eq!(evens.keys().copied().collect::<Vec<_>>(), vec![0, 2, 4, 6]);
assert_eq!(odds.keys().copied().collect::<Vec<_>>(), vec![1, 3, 5, 7]);

pub 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) such that f(&k, &mut v) returns false.

Example

use btree_slab::BTreeMap;

let mut map: BTreeMap<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: Ord, C: Default,

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

Example

use btree_slab::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, "a");
a.insert(2, "b");
a.insert(3, "c");

let mut b = BTreeMap::new();
b.insert(3, "d");
b.insert(4, "e");
b.insert(5, "f");

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");
assert_eq!(a[&4], "e");
assert_eq!(a[&5], "f");

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

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.

Example

use btree_slab::BTreeMap;

let mut a = BTreeMap::new();
a.insert(2, "b");
a.insert(1, "a");

let keys: Vec<i32> = a.into_keys().collect();
assert_eq!(keys, [1, 2]);

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

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.

Example

use btree_slab::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, "hello");
a.insert(2, "goodbye");

let values: Vec<&str> = a.into_values().collect();
assert_eq!(values, ["hello", "goodbye"]);

Trait Implementations

impl<K, V, C> BTreeExt<K, V> for BTreeMap<K, V, C>

where C: SimpleCollectionRef + Slab<Node<K, V>>,

fn previous_item_address(&self, addr: Address) -> Option<Address>

Get the address of the item located before this address.

fn next_item_address(&self, addr: Address) -> Option<Address>

Get the address of the item located after this address if any.

fn validate_node( &self, id: usize, parent: Option<usize>, min: Option<&K>, max: Option<&K>, ) -> usize

where K: Ord,

Validate the given node and returns the depth of the node.

fn root_id(&self) -> Option<usize>

Get the root node id.

fn node(&self, id: usize) -> &Node<K, V>

Get the node associated to the given id.

fn get_in<Q>(&self, key: &Q, id: usize) -> Option<&V>

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

Get a reference to the value associated to the given key in the node id, if any.

fn item(&self, addr: Address) -> Option<&Item<K, V>>

Get a reference to the item located at the given address.

fn first_item_address(&self) -> Option<Address>

Get the first item address, if any.

fn first_back_address(&self) -> Address

Get the first back address.

fn last_item_address(&self) -> Option<Address>

Get the last item address, if any.

fn last_valid_address(&self) -> Address

Get the last valid address in the tree.

fn normalize(&self, addr: Address) -> Option<Address>

Normalizes the given item address so that an out-of-node-bounds address points to the next item.

fn leaf_address(&self, addr: Address) -> Address

Returns the greatest valid leaf address that directly precedes the given address.

fn previous_front_address(&self, addr: Address) -> Option<Address>

Get the previous front address.

fn next_back_address(&self, addr: Address) -> Option<Address>

Get the next back address.

fn next_item_or_back_address(&self, addr: Address) -> Option<Address>

Get the next item address if any, or the next back address otherwise.

fn address_of<Q>(&self, key: &Q) -> Result<Address, Address>

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

Get the address of the given key.

fn address_in<Q>(&self, id: usize, key: &Q) -> Result<Address, Address>

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

Search for the address of the given key from the given node id.

fn validate(&self)

where K: Ord,

Validate the tree.

impl<K, V, C> BTreeExtMut<K, V> for BTreeMap<K, V, C>

where C: SimpleCollectionRef + SimpleCollectionMut + SlabMut<Node<K, V>>,

fn set_len(&mut self, new_len: usize)

Set the new known number of items in the tree.

fn set_root_id(&mut self, id: Option<usize>)

Set the root node identifier.

fn node_mut(&mut self, id: usize) -> &mut Node<K, V>

Get the node associated to the given id mutably.

fn get_mut_in<'a>(&'a mut self, key: &K, id: usize) -> Option<&'a mut V>

where K: Ord,

Get a mutable reference to the value associated to the given key in the node id, if any.

fn item_mut(&mut self, addr: Address) -> Option<&mut Item<K, V>>

Get a mutable reference to the item located at the given address.

fn insert_at(&mut self, addr: Address, item: Item<K, V>) -> Address

Insert an item at the given address.

fn insert_exactly_at( &mut self, addr: Address, item: Item<K, V>, opt_right_id: Option<usize>, ) -> Address

Insert an item at the given address.

fn replace_at(&mut self, addr: Address, key: K, value: V) -> (K, V)

Replaces the key-value binding at the given address.

fn replace_value_at(&mut self, addr: Address, value: V) -> V

Replaces the value at the given address.

fn remove_at(&mut self, addr: Address) -> Option<(Item<K, V>, Address)>

Removes the item at the given address, if any.

fn update_in<T, F>(&mut self, id: usize, key: K, action: F) -> T

where K: Ord, F: FnOnce(Option<V>) -> (Option<V>, T),

Update a value in the given node node_id.

fn update_at<T, F>(&mut self, addr: Address, action: F) -> T

where K: Ord, F: FnOnce(V) -> (Option<V>, T),

Update a valud at the given address.

fn rebalance(&mut self, id: usize, addr: Address) -> Address

Rebalance a node, if necessary.

fn remove_rightmost_leaf_of(&mut self, id: usize) -> (Item<K, V>, usize)

Take the right-most leaf value in the given node.

fn allocate_node(&mut self, node: Node<K, V>) -> usize

Allocate a free identifier for the given node.

fn release_node(&mut self, id: usize) -> Node<K, V>

Release the given node identifier and return the node it used to identify.

impl<K: Clone, V: Clone, C: Clone> Clone for BTreeMap<K, V, C>

fn clone(&self) -> BTreeMap<K, V, C>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K, V, C: Default> Default for BTreeMap<K, V, C>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, K: Ord + Copy, V: Copy, C> Extend<(&'a K, &'a V)> for BTreeMap<K, V, C>

where C: SimpleCollectionRef + SimpleCollectionMut + SlabMut<Node<K, V>>,

fn extend<T>(&mut self, iter: T)

where T: IntoIterator<Item = (&'a K, &'a V)>,

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: Ord, V, C> Extend<(K, V)> for BTreeMap<K, V, C>

where C: SimpleCollectionRef + SimpleCollectionMut + SlabMut<Node<K, V>>,

fn extend<T>(&mut self, iter: T)

where T: IntoIterator<Item = (K, V)>,

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: Ord, V, C> FromIterator<(K, V)> for BTreeMap<K, V, C>

where C: SimpleCollectionRef + SimpleCollectionMut + SlabMut<Node<K, V>> + Default,

fn from_iter<T>(iter: T) -> BTreeMap<K, V, C>

where T: IntoIterator<Item = (K, V)>,

Creates a value from an iterator.

impl<K: Hash, V: Hash, C> Hash for BTreeMap<K, V, C>

where C: SimpleCollectionRef + Slab<Node<K, V>>,

fn hash<H: Hasher>(&self, h: &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<K, Q, V, C> Index<&Q> for BTreeMap<K, V, C>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized, C: SimpleCollectionRef + Slab<Node<K, V>>,

fn index(&self, key: &Q) -> &V

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

Panics

Panics if the key is not present in the BTreeMap.

type Output = V

The returned type after indexing.

impl<'a, K, V, C> IntoIterator for &'a BTreeMap<K, V, C>

where C: SimpleCollectionRef + Slab<Node<K, V>>,

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

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) -> Iter<'a, K, V, C>

Creates an iterator from a value.

impl<K, V, C> IntoIterator for BTreeMap<K, V, C>

where C: SimpleCollectionRef + SimpleCollectionMut + SlabMut<Node<K, V>>,

type IntoIter = IntoIter<K, V, C>

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) -> IntoIter<K, V, C>

Creates an iterator from a value.

impl<K: Ord, V: Ord, C> Ord for BTreeMap<K, V, C>

where C: SimpleCollectionRef + Slab<Node<K, V>>,

fn cmp(&self, other: &BTreeMap<K, V, C>) -> 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, L: PartialEq<K>, V, W: PartialEq<V>, C, D> PartialEq<BTreeMap<L, W, D>> for BTreeMap<K, V, C>

where C: SimpleCollectionRef + Slab<Node<K, V>>, D: SimpleCollectionRef + Slab<Node<L, W>>,

fn eq(&self, other: &BTreeMap<L, W, D>) -> 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, L: PartialOrd<K>, V, W: PartialOrd<V>, C, D> PartialOrd<BTreeMap<L, W, D>> for BTreeMap<K, V, C>

where C: SimpleCollectionRef + Slab<Node<K, V>>, D: SimpleCollectionRef + Slab<Node<L, W>>,

fn partial_cmp(&self, other: &BTreeMap<L, W, D>) -> 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: Eq, V: Eq, C> Eq for BTreeMap<K, V, C>

where C: SimpleCollectionRef + Slab<Node<K, V>>,