1use std::collections::HashMap;
5use std::fmt;
6
7const INDEX_THRESHOLD: usize = 16;
10
11#[derive(Clone)]
19pub struct OrderedMap<V> {
20 keys: Keys,
21 values: Vec<V>,
22}
23
24#[derive(Clone, Default)]
27pub(crate) struct Keys {
28 pub(crate) names: Vec<String>,
29 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 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 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 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 pub fn get_index(&self, index: usize) -> Option<(&String, &V)> {
127 Some((self.keys.names.get(index)?, &self.values[index]))
128 }
129
130 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 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 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 pub fn remove(&mut self, key: &str) -> Option<V> {
168 self.remove_full(key).map(|(_, v)| v)
169 }
170
171 pub fn iter(&self) -> Iter<'_, V> {
173 Iter::new(&self.keys.names, &self.values)
174 }
175
176 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 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#[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 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
249pub struct IntoIter<V>(std::iter::Zip<std::vec::IntoIter<String>, std::vec::IntoIter<V>>);
251
252impl<V> IntoIter<V> {
253 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 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}