Skip to main content

zero_client/
map.rs

1//! [`OrderedMap`]: a map with string keys that keeps them in insertion order,
2//! so the crate needs no third-party map.
3
4use std::collections::HashMap;
5use std::fmt;
6
7/// Maps up to this many keys are searched linearly, which beats hashing for
8/// the few columns of a row; larger ones keep a hash index.
9const INDEX_THRESHOLD: usize = 16;
10
11/// A map from strings to `V` that keeps its keys in the order they were
12/// inserted. Lookups are O(1): small maps scan their few entries, and larger
13/// ones keep a hash index of positions. Inserting or removing at a position
14/// shifts the entries after it, in O(n).
15///
16/// Two maps are equal when they have the same keys with equal values, in
17/// any order.
18#[derive(Clone)]
19pub struct OrderedMap<V> {
20    entries: Vec<(String, V)>,
21    /// Each key's position in `entries`, once there are more than
22    /// `INDEX_THRESHOLD`.
23    index: Option<HashMap<String, usize>>,
24}
25
26impl<V> Default for OrderedMap<V> {
27    fn default() -> Self {
28        OrderedMap {
29            entries: Vec::new(),
30            index: None,
31        }
32    }
33}
34
35impl<V> OrderedMap<V> {
36    pub fn new() -> Self {
37        Self::default()
38    }
39
40    pub fn with_capacity(capacity: usize) -> Self {
41        OrderedMap {
42            entries: Vec::with_capacity(capacity),
43            index: None,
44        }
45    }
46
47    pub fn len(&self) -> usize {
48        self.entries.len()
49    }
50
51    pub fn is_empty(&self) -> bool {
52        self.entries.is_empty()
53    }
54
55    /// The position of `key`.
56    pub fn position(&self, key: &str) -> Option<usize> {
57        match &self.index {
58            Some(index) => index.get(key).copied(),
59            None => self.entries.iter().position(|(k, _)| k == key),
60        }
61    }
62
63    pub fn get(&self, key: &str) -> Option<&V> {
64        self.position(key).map(|i| &self.entries[i].1)
65    }
66
67    pub fn get_mut(&mut self, key: &str) -> Option<&mut V> {
68        self.position(key).map(|i| &mut self.entries[i].1)
69    }
70
71    pub fn contains_key(&self, key: &str) -> bool {
72        self.position(key).is_some()
73    }
74
75    /// The entry at `index`, in order.
76    pub fn get_index(&self, index: usize) -> Option<(&String, &V)> {
77        self.entries.get(index).map(|(k, v)| (k, v))
78    }
79
80    /// Sets `key` to `value`, returning the value it replaced. A new key goes
81    /// last; an existing one keeps its place.
82    pub fn insert(&mut self, key: impl Into<String>, value: V) -> Option<V> {
83        let key = key.into();
84        if let Some(i) = self.position(&key) {
85            return Some(std::mem::replace(&mut self.entries[i].1, value));
86        }
87        let at = self.entries.len();
88        self.insert_new(at, key, value);
89        None
90    }
91
92    /// Inserts `key`, which must not be present yet, at position `at`,
93    /// shifting the entries after it.
94    pub fn insert_at(&mut self, at: usize, key: impl Into<String>, value: V) {
95        let key = key.into();
96        assert!(
97            !self.contains_key(&key),
98            "OrderedMap::insert_at: key present"
99        );
100        self.insert_new(at, key, value);
101    }
102
103    fn insert_new(&mut self, at: usize, key: String, value: V) {
104        if let Some(index) = &mut self.index {
105            if at < self.entries.len() {
106                for i in index.values_mut().filter(|i| **i >= at) {
107                    *i += 1;
108                }
109            }
110            index.insert(key.clone(), at);
111        }
112        self.entries.insert(at, (key, value));
113        if self.index.is_none() && self.entries.len() > INDEX_THRESHOLD {
114            self.index = Some(
115                self.entries
116                    .iter()
117                    .enumerate()
118                    .map(|(i, (k, _))| (k.clone(), i))
119                    .collect(),
120            );
121        }
122    }
123
124    /// Removes `key`, returning its position and value. The other keys keep
125    /// their order.
126    pub fn remove_full(&mut self, key: &str) -> Option<(usize, V)> {
127        let at = self.position(key)?;
128        if let Some(index) = &mut self.index {
129            index.remove(key);
130            for i in index.values_mut().filter(|i| **i > at) {
131                *i -= 1;
132            }
133        }
134        Some((at, self.entries.remove(at).1))
135    }
136
137    /// Removes `key`, returning its value. The other keys keep their order.
138    pub fn remove(&mut self, key: &str) -> Option<V> {
139        self.remove_full(key).map(|(_, v)| v)
140    }
141
142    /// The entries, in order.
143    pub fn iter(&self) -> Iter<'_, V> {
144        Iter(self.entries.iter())
145    }
146
147    /// The entries, in order, with mutable values.
148    pub fn iter_mut(&mut self) -> impl ExactSizeIterator<Item = (&String, &mut V)> {
149        self.entries.iter_mut().map(|(k, v)| (&*k, v))
150    }
151
152    pub fn keys(&self) -> impl DoubleEndedIterator<Item = &String> + ExactSizeIterator + Clone {
153        self.entries.iter().map(|(k, _)| k)
154    }
155
156    pub fn values(&self) -> impl DoubleEndedIterator<Item = &V> + ExactSizeIterator + Clone {
157        self.entries.iter().map(|(_, v)| v)
158    }
159
160    pub fn values_mut(&mut self) -> impl ExactSizeIterator<Item = &mut V> {
161        self.entries.iter_mut().map(|(_, v)| v)
162    }
163}
164
165impl<V: PartialEq> PartialEq for OrderedMap<V> {
166    fn eq(&self, other: &Self) -> bool {
167        self.len() == other.len() && self.iter().all(|(k, v)| other.get(k) == Some(v))
168    }
169}
170
171impl<V: fmt::Debug> fmt::Debug for OrderedMap<V> {
172    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
173        f.debug_map().entries(self.iter()).finish()
174    }
175}
176
177impl<K: Into<String>, V> FromIterator<(K, V)> for OrderedMap<V> {
178    /// A key that repeats keeps its first place and its last value.
179    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
180        let iter = iter.into_iter();
181        let mut map = OrderedMap::with_capacity(iter.size_hint().0);
182        for (k, v) in iter {
183            map.insert(k, v);
184        }
185        map
186    }
187}
188
189/// The entries of an [`OrderedMap`], in order.
190#[derive(Clone)]
191pub struct Iter<'a, V>(std::slice::Iter<'a, (String, V)>);
192
193impl<'a, V> Iterator for Iter<'a, V> {
194    type Item = (&'a String, &'a V);
195
196    fn next(&mut self) -> Option<Self::Item> {
197        self.0.next().map(|(k, v)| (k, v))
198    }
199
200    fn size_hint(&self) -> (usize, Option<usize>) {
201        self.0.size_hint()
202    }
203}
204
205impl<V> DoubleEndedIterator for Iter<'_, V> {
206    fn next_back(&mut self) -> Option<Self::Item> {
207        self.0.next_back().map(|(k, v)| (k, v))
208    }
209}
210
211impl<V> ExactSizeIterator for Iter<'_, V> {}
212
213/// The entries of an [`OrderedMap`], in order, by value.
214pub struct IntoIter<V>(std::vec::IntoIter<(String, V)>);
215
216impl<V> Iterator for IntoIter<V> {
217    type Item = (String, V);
218
219    fn next(&mut self) -> Option<Self::Item> {
220        self.0.next()
221    }
222
223    fn size_hint(&self) -> (usize, Option<usize>) {
224        self.0.size_hint()
225    }
226}
227
228impl<V> DoubleEndedIterator for IntoIter<V> {
229    fn next_back(&mut self) -> Option<Self::Item> {
230        self.0.next_back()
231    }
232}
233
234impl<V> ExactSizeIterator for IntoIter<V> {}
235
236impl<'a, V> IntoIterator for &'a OrderedMap<V> {
237    type Item = (&'a String, &'a V);
238    type IntoIter = Iter<'a, V>;
239
240    fn into_iter(self) -> Iter<'a, V> {
241        self.iter()
242    }
243}
244
245impl<V> IntoIterator for OrderedMap<V> {
246    type Item = (String, V);
247    type IntoIter = IntoIter<V>;
248
249    fn into_iter(self) -> IntoIter<V> {
250        IntoIter(self.entries.into_iter())
251    }
252}
253
254#[cfg(test)]
255mod tests {
256    use super::*;
257
258    /// Checks every lookup against the entries' own order, across the size
259    /// where the hash index starts.
260    fn check(map: &OrderedMap<usize>) {
261        for (i, (k, v)) in map.iter().enumerate() {
262            assert_eq!(map.position(k), Some(i), "{k}");
263            assert_eq!(map.get(k), Some(v));
264        }
265        assert_eq!(map.get("missing"), None);
266    }
267
268    #[test]
269    fn keeps_order_and_positions_through_inserts_and_removes() {
270        let mut map = OrderedMap::new();
271        for i in 0..20 {
272            map.insert(format!("k{i}"), i);
273            check(&map);
274        }
275        assert_eq!(map.insert("k3", 30), Some(3));
276        map.insert_at(0, "first", 100);
277        map.insert_at(5, "middle", 101);
278        check(&map);
279        assert_eq!(map.remove_full("k0"), Some((1, 0)));
280        assert_eq!(map.remove("middle"), Some(101));
281        check(&map);
282        for i in 1..20 {
283            map.remove(&format!("k{i}"));
284            check(&map);
285        }
286        assert_eq!(map.keys().collect::<Vec<_>>(), ["first"]);
287        map.insert("again", 1);
288        check(&map);
289    }
290
291    #[test]
292    fn equality_ignores_order() {
293        let a: OrderedMap<i32> = [("x", 1), ("y", 2)].into_iter().collect();
294        let b: OrderedMap<i32> = [("y", 2), ("x", 1)].into_iter().collect();
295        let c: OrderedMap<i32> = [("y", 2), ("x", 3)].into_iter().collect();
296        assert_eq!(a, b);
297        assert_ne!(a, c);
298    }
299}