btree_indexmap/
lib.rs

1//! BTree-based maps and sets with stable entry indices.
2//!
3//! This crate provides ordered map and set types that combine the
4//! sorted-key lookup of a B-tree with stable integer indices backed by a
5//! contiguous [`Vec`]:
6//!
7//! - [`BTreeIndexMap<K, V>`](crate::map::BTreeIndexMap) — each key maps to exactly one value.
8//! - [`BTreeIndexMultiMap<K, V>`](crate::multi_map::BTreeIndexMultiMap) — each key may map to multiple values.
9//! - [`BTreeIndexSet<T>`](crate::set::BTreeIndexSet) — each value is stored at most once.
10//! - [`BTreeIndexMultiSet<T>`](crate::multi_set::BTreeIndexMultiSet) — each value may occur any number of times.
11//!
12//! The set types are thin wrappers around their map counterparts
13//! (`BTreeIndexMap<T, ()>` and `BTreeIndexMultiMap<T, ()>` respectively).
14//!
15//! Entries are stored in a `Vec` and assigned a *stable index* equal to
16//! their position in that `Vec`. The index of an entry does not change as
17//! long as no entry is removed. A B-tree over the keys provides O(log n)
18//! lookup, insertion, and removal, while the `Vec` backing allows O(1)
19//! random access by index.
20//!
21//! # Usage
22//!
23//! ## `BTreeIndexMap`
24//!
25//! ```
26//! use btree_indexmap::BTreeIndexMap;
27//!
28//! let mut map = BTreeIndexMap::new();
29//!
30//! // Entries are stored in insertion order and assigned a stable index.
31//! map.insert("banana", 3);
32//! map.insert("apple", 5);
33//!
34//! // O(1) access by index (insertion order).
35//! assert_eq!(map.as_entries()[0], ("banana", 3));
36//! assert_eq!(map.as_entries()[1], ("apple", 5));
37//!
38//! // O(log n) lookup by key, returning the stable index alongside the value.
39//! assert_eq!(map.get_full("apple"), Some((1, &"apple", &5)));
40//!
41//! // Iterate in insertion order.
42//! let by_insertion: Vec<_> = map.iter().map(|(&k, &v)| (k, v)).collect();
43//! assert_eq!(by_insertion, [("banana", 3), ("apple", 5)]);
44//!
45//! // Iterate in sorted key order.
46//! let by_key: Vec<_> = map.iter_sorted().map(|(&k, &v)| (k, v)).collect();
47//! assert_eq!(by_key, [("apple", 5), ("banana", 3)]);
48//! ```
49//!
50//! ## `BTreeIndexMultiMap`
51//!
52//! ```
53//! use btree_indexmap::BTreeIndexMultiMap;
54//!
55//! let mut map = BTreeIndexMultiMap::new();
56//!
57//! // Multiple values per key, each with its own stable index.
58//! map.push_back("fruit", "apple");
59//! map.push_back("veggie", "carrot");
60//! map.push_back("fruit", "banana");
61//!
62//! assert_eq!(map.key_occurences("fruit"), 2);
63//!
64//! let fruits: Vec<_> = map.get("fruit").copied().collect();
65//! assert_eq!(fruits, ["apple", "banana"]);
66//!
67//! // Iterate in sorted key order, values in position order within each key.
68//! let by_key: Vec<_> = map.iter_sorted().map(|(&k, &v)| (k, v)).collect();
69//! assert_eq!(by_key, [
70//!     ("fruit", "apple"),
71//!     ("fruit", "banana"),
72//!     ("veggie", "carrot"),
73//! ]);
74//! ```
75//!
76//! ## `BTreeIndexSet`
77//!
78//! ```
79//! use btree_indexmap::BTreeIndexSet;
80//!
81//! let mut set = BTreeIndexSet::new();
82//!
83//! // Values are stored in insertion order and assigned a stable index.
84//! set.insert("banana");
85//! set.insert("apple");
86//!
87//! // O(1) access by index (insertion order).
88//! assert_eq!(set.as_slice(), ["banana", "apple"]);
89//!
90//! // O(log n) lookup, returning the stable index alongside the value.
91//! assert_eq!(set.get_full("apple"), Some((1, &"apple")));
92//! ```
93//!
94//! ## `BTreeIndexMultiSet`
95//!
96//! ```
97//! use btree_indexmap::BTreeIndexMultiSet;
98//!
99//! let mut set = BTreeIndexMultiSet::new();
100//!
101//! // Multiple occurrences of the same value, each with its own stable
102//! // index.
103//! set.push_back("apple");
104//! set.push_back("carrot");
105//! set.push_back("apple");
106//!
107//! assert_eq!(set.count("apple"), 2);
108//! ```
109pub use equivalent::{Comparable, Equivalent};
110
111mod r#impl;
112pub mod map;
113pub mod multi_map;
114pub mod multi_set;
115pub mod set;
116mod util;
117
118#[allow(unused_imports)]
119pub use r#impl::*;
120pub use map::BTreeIndexMap;
121pub use multi_map::BTreeIndexMultiMap;
122pub use multi_set::BTreeIndexMultiSet;
123pub use set::BTreeIndexSet;
btree_indexmap/lib.rs

btree_indexmap/
lib.rs
