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