1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//! BTree-based maps with stable entry indices.
//!
//! This crate provides two ordered map types that combine the sorted-key
//! lookup of a B-tree with stable integer indices backed by a contiguous
//! [`Vec`](::alloc::vec::Vec):
//!
//! - [`BTreeIndexMap<K, V>`](crate::map::BTreeIndexMap) — each key maps to exactly one value.
//! - [`BTreeIndexMultiMap<K, V>`](crate::multi_map::BTreeIndexMultiMap) — each key may map to multiple values.
//!
//! 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"),
//! ]);
//! ```
pub use Comparable;
pub use BTreeIndexMap;
pub use BTreeIndexMultiMap;
pub use r#