BTree Index-map

BTree-based maps and sets with stable entry indices.

This crate provides ordered map and set types that combine the sorted-key lookup of a B-tree with stable integer indices backed by a contiguous Vec:

• BTreeIndexMap<K, V> — each key maps to exactly one value.
• BTreeIndexMultiMap<K, V> — each key may map to multiple values.
• BTreeIndexSet<T> — each value is stored at most once.
• BTreeIndexMultiSet<T> — each value may occur any number of times.

The set types are thin wrappers around their map counterparts (BTreeIndexMap<T, ()> and BTreeIndexMultiMap<T, ()> respectively).

Entries are stored in a Vec and assigned a stable index equal to their position in that Vec. The index of an entry does not change as long as no entry is removed. A B-tree over the keys provides O(log n) lookup, insertion, and removal, while the Vec backing allows O(1) random access by index.

Usage

BTreeIndexMap

use btree_indexmap::BTreeIndexMap;

let mut map = BTreeIndexMap::new();

// Entries are stored in insertion order and assigned a stable index.
map.insert("banana", 3);
map.insert("apple", 5);

// O(1) access by index (insertion order).
assert_eq!(map.as_entries()[0], ("banana", 3));
assert_eq!(map.as_entries()[1], ("apple", 5));

// O(log n) lookup by key, returning the stable index alongside the value.
assert_eq!(map.get_full("apple"), Some((1, &"apple", &5)));

// Iterate in insertion order.
let by_insertion: Vec<_> = map.iter().map(|(&k, &v)| (k, v)).collect();
assert_eq!(by_insertion, [("banana", 3), ("apple", 5)]);

// Iterate in sorted key order.
let by_key: Vec<_> = map.iter_sorted().map(|(&k, &v)| (k, v)).collect();
assert_eq!(by_key, [("apple", 5), ("banana", 3)]);

BTreeIndexMultiMap

use btree_indexmap::BTreeIndexMultiMap;

let mut map = BTreeIndexMultiMap::new();

// Multiple values per key, each with its own stable index.
map.push_back("fruit", "apple");
map.push_back("veggie", "carrot");
map.push_back("fruit", "banana");

assert_eq!(map.key_occurences("fruit"), 2);

let fruits: Vec<_> = map.get("fruit").copied().collect();
assert_eq!(fruits, ["apple", "banana"]);

// Iterate in sorted key order, values in position order within each key.
let by_key: Vec<_> = map.iter_sorted().map(|(&k, &v)| (k, v)).collect();
assert_eq!(by_key, [
    ("fruit", "apple"),
    ("fruit", "banana"),
    ("veggie", "carrot"),
]);

BTreeIndexSet

use btree_indexmap::BTreeIndexSet;

let mut set = BTreeIndexSet::new();

// Values are stored in insertion order and assigned a stable index.
set.insert("banana");
set.insert("apple");

// O(1) access by index (insertion order).
assert_eq!(set.as_slice(), ["banana", "apple"]);

// O(log n) lookup, returning the stable index alongside the value.
assert_eq!(set.get_full("apple"), Some((1, &"apple")));

BTreeIndexMultiSet

use btree_indexmap::BTreeIndexMultiSet;

let mut set = BTreeIndexMultiSet::new();

// Multiple occurrences of the same value, each with its own stable
// index.
set.push_back("apple");
set.push_back("carrot");
set.push_back("apple");

assert_eq!(set.count("apple"), 2);

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.