cjc_data/detcoll/
tiny_det_map.rs

1//! `TinyDetMap<K, V>` — small map backed by a sorted `Vec`.
2//!
3//! Optimized for ≤ ~16 entries. Linear scan beats `BTreeMap` at this
4//! size (no node allocation, contiguous memory, branch predictor wins).
5//! Iteration order is sorted by `K`, so output is canonical.
6//!
7//! Use for: small parser keyword tables, tiny schema metadata, short
8//! enum/member lists, anywhere `BTreeMap` would feel like overkill but
9//! you still want sorted iteration.
10
11use std::cmp::Ordering;
12
13#[derive(Debug, Clone)]
14pub struct TinyDetMap<K: Ord, V> {
15    /// Sorted by `K`. Linear scan beats binary search up to ~16 entries
16    /// because of cache locality and branch predictor friendliness.
17    entries: Vec<(K, V)>,
18}
19
20impl<K: Ord, V> Default for TinyDetMap<K, V> {
21    fn default() -> Self {
22        Self::new()
23    }
24}
25
26impl<K: Ord, V> TinyDetMap<K, V> {
27    pub fn new() -> Self {
28        Self {
29            entries: Vec::new(),
30        }
31    }
32
33    pub fn with_capacity(cap: usize) -> Self {
34        Self {
35            entries: Vec::with_capacity(cap),
36        }
37    }
38
39    pub fn len(&self) -> usize {
40        self.entries.len()
41    }
42
43    pub fn is_empty(&self) -> bool {
44        self.entries.is_empty()
45    }
46
47    /// Insert or update. Returns the previous value if the key existed.
48    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
49        match self.entries.binary_search_by(|(k, _)| k.cmp(&key)) {
50            Ok(i) => Some(std::mem::replace(&mut self.entries[i].1, value)),
51            Err(i) => {
52                self.entries.insert(i, (key, value));
53                None
54            }
55        }
56    }
57
58    pub fn get(&self, key: &K) -> Option<&V> {
59        // Linear scan with branch on key cmp.
60        for (k, v) in &self.entries {
61            match k.cmp(key) {
62                Ordering::Less => continue,
63                Ordering::Equal => return Some(v),
64                Ordering::Greater => return None,
65            }
66        }
67        None
68    }
69
70    pub fn contains_key(&self, key: &K) -> bool {
71        self.get(key).is_some()
72    }
73
74    pub fn remove(&mut self, key: &K) -> Option<V> {
75        match self.entries.binary_search_by(|(k, _)| k.cmp(key)) {
76            Ok(i) => Some(self.entries.remove(i).1),
77            Err(_) => None,
78        }
79    }
80
81    /// Iterate sorted `(K, V)` pairs.
82    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> + '_ {
83        self.entries.iter().map(|(k, v)| (k, v))
84    }
85}
86
87impl<K: Ord + Clone, V: Clone> FromIterator<(K, V)> for TinyDetMap<K, V> {
88    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
89        let mut m = Self::new();
90        for (k, v) in iter {
91            m.insert(k, v);
92        }
93        m
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100
101    #[test]
102    fn insert_and_get_basic() {
103        let mut m = TinyDetMap::new();
104        assert!(m.insert("apple", 1).is_none());
105        assert!(m.insert("banana", 2).is_none());
106        assert!(m.insert("cherry", 3).is_none());
107        assert_eq!(m.get(&"apple"), Some(&1));
108        assert_eq!(m.get(&"banana"), Some(&2));
109        assert_eq!(m.get(&"cherry"), Some(&3));
110        assert_eq!(m.get(&"date"), None);
111    }
112
113    #[test]
114    fn insert_overwrites_returns_old() {
115        let mut m = TinyDetMap::new();
116        m.insert("k", 1);
117        let prev = m.insert("k", 2);
118        assert_eq!(prev, Some(1));
119        assert_eq!(m.get(&"k"), Some(&2));
120    }
121
122    #[test]
123    fn iter_is_sorted_regardless_of_insertion_order() {
124        let mut m = TinyDetMap::new();
125        for &k in &["zebra", "apple", "mango", "banana"] {
126            m.insert(k, 0);
127        }
128        let keys: Vec<&&str> = m.iter().map(|(k, _)| k).collect();
129        assert_eq!(keys, vec![&"apple", &"banana", &"mango", &"zebra"]);
130    }
131
132    #[test]
133    fn remove_works() {
134        let mut m = TinyDetMap::new();
135        m.insert(1, "a");
136        m.insert(2, "b");
137        m.insert(3, "c");
138        assert_eq!(m.remove(&2), Some("b"));
139        assert_eq!(m.get(&2), None);
140        assert_eq!(m.len(), 2);
141    }
142
143    #[test]
144    fn deterministic_under_permutation() {
145        let mut a = TinyDetMap::new();
146        let mut b = TinyDetMap::new();
147        for &(k, v) in &[(1, "a"), (2, "b"), (3, "c"), (4, "d")] {
148            a.insert(k, v);
149        }
150        for &(k, v) in &[(4, "d"), (1, "a"), (3, "c"), (2, "b")] {
151            b.insert(k, v);
152        }
153        let av: Vec<_> = a.iter().collect();
154        let bv: Vec<_> = b.iter().collect();
155        assert_eq!(av, bv);
156    }
157}
cjc_data/detcoll/tiny_det_map.rs

cjc_data/detcoll/
tiny_det_map.rs
