voxgig_struct/
ordered_map.rs

1// Minimal in-tree insertion-ordered map.
2//
3// Rust's `std::collections::HashMap` doesn't preserve insertion order, and
4// the canonical contract requires that JSON object key order survive every
5// operation. Other ports either get this for free (Python 3.7+ dict,
6// Ruby Hash, PHP array, JS object), or hand-roll an OrderedMap
7// (C / C++ / Zig). This is the Rust equivalent — keeps the port
8// dependency-free.
9//
10// Only the operations the rest of voxgig-struct uses are implemented:
11// `new`, `insert`, `get`, `contains_key`, `shift_remove`, `iter`,
12// `iter_mut`, `keys`, `values`, `len`, `is_empty`, indexing by `&str`,
13// `Clone`, `IntoIterator` and `FromIterator`.
14//
15// Parallel keys + values vectors preserve insertion order; a separate
16// `HashMap<String, usize>` indexes key -> position for O(1) lookup.
17// `shift_remove` is O(n) on a vec-shift plus an O(n) index rebuild; the
18// corpus's map sizes are modest so this is the right complexity trade.
19
20use std::collections::HashMap;
21use std::ops::Index;
22
23#[derive(Clone, Default)]
24pub struct OrderedMap<V> {
25    keys: Vec<String>,
26    values: Vec<V>,
27    index: HashMap<String, usize>,
28}
29
30impl<V> OrderedMap<V> {
31    pub fn new() -> Self {
32        OrderedMap {
33            keys: Vec::new(),
34            values: Vec::new(),
35            index: HashMap::new(),
36        }
37    }
38
39    pub fn len(&self) -> usize {
40        self.keys.len()
41    }
42    pub fn is_empty(&self) -> bool {
43        self.keys.is_empty()
44    }
45
46    pub fn contains_key(&self, key: &str) -> bool {
47        self.index.contains_key(key)
48    }
49
50    pub fn get(&self, key: &str) -> Option<&V> {
51        self.index.get(key).map(|&i| &self.values[i])
52    }
53
54    pub fn get_mut(&mut self, key: &str) -> Option<&mut V> {
55        if let Some(&i) = self.index.get(key) {
56            Some(&mut self.values[i])
57        } else {
58            None
59        }
60    }
61
62    pub fn insert(&mut self, key: String, value: V) -> Option<V> {
63        if let Some(&i) = self.index.get(&key) {
64            return Some(std::mem::replace(&mut self.values[i], value));
65        }
66        self.index.insert(key.clone(), self.keys.len());
67        self.keys.push(key);
68        self.values.push(value);
69        None
70    }
71
72    /// Remove an entry, shifting later entries left to preserve order.
73    pub fn shift_remove(&mut self, key: &str) -> Option<V> {
74        let i = self.index.remove(key)?;
75        self.keys.remove(i);
76        let v = self.values.remove(i);
77        // Re-index every entry whose position changed.
78        for (k, idx) in self.index.iter_mut() {
79            if *idx > i {
80                *idx -= 1;
81            }
82            // Defensive — the removed key is gone from `index` already.
83            let _ = k;
84        }
85        Some(v)
86    }
87
88    pub fn keys(&self) -> std::slice::Iter<'_, String> {
89        self.keys.iter()
90    }
91    pub fn values(&self) -> std::slice::Iter<'_, V> {
92        self.values.iter()
93    }
94
95    pub fn iter(&self) -> OrderedMapIter<'_, V> {
96        OrderedMapIter {
97            keys: &self.keys,
98            values: &self.values,
99            i: 0,
100        }
101    }
102
103    pub fn iter_mut(&mut self) -> impl Iterator<Item = (&String, &mut V)> {
104        self.keys.iter().zip(self.values.iter_mut())
105    }
106}
107
108pub struct OrderedMapIter<'a, V> {
109    keys: &'a [String],
110    values: &'a [V],
111    i: usize,
112}
113
114impl<'a, V> Iterator for OrderedMapIter<'a, V> {
115    type Item = (&'a String, &'a V);
116    fn next(&mut self) -> Option<Self::Item> {
117        if self.i >= self.keys.len() {
118            return None;
119        }
120        let r = (&self.keys[self.i], &self.values[self.i]);
121        self.i += 1;
122        Some(r)
123    }
124}
125
126impl<V> Index<&str> for OrderedMap<V> {
127    type Output = V;
128    fn index(&self, key: &str) -> &V {
129        self.get(key).expect("OrderedMap: missing key")
130    }
131}
132
133impl<V> FromIterator<(String, V)> for OrderedMap<V> {
134    fn from_iter<I: IntoIterator<Item = (String, V)>>(iter: I) -> Self {
135        let mut m = OrderedMap::new();
136        for (k, v) in iter {
137            m.insert(k, v);
138        }
139        m
140    }
141}
142
143impl<'a, V> IntoIterator for &'a OrderedMap<V> {
144    type Item = (&'a String, &'a V);
145    type IntoIter = OrderedMapIter<'a, V>;
146    fn into_iter(self) -> Self::IntoIter {
147        self.iter()
148    }
149}
150
151impl<V: std::fmt::Debug> std::fmt::Debug for OrderedMap<V> {
152    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
153        let mut m = f.debug_map();
154        for (k, v) in self.iter() {
155            m.entry(k, v);
156        }
157        m.finish()
158    }
159}
voxgig_struct/ordered_map.rs

voxgig_struct/
ordered_map.rs
