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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
//! 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>`](crate::map::BTreeIndexMap) — each key maps to exactly one value.
//! - [`BTreeIndexMultiMap<K, V>`](crate::multi_map::BTreeIndexMultiMap) — each key may map to multiple values.
//! - [`BTreeIndexSet<T>`](crate::set::BTreeIndexSet) — each value is stored at most once.
//! - [`BTreeIndexMultiSet<T>`](crate::multi_set::BTreeIndexMultiSet) — 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);
//! ```
pub use Comparable;
pub use r#