1use std::collections::HashMap;
5use std::fmt;
6
7const INDEX_THRESHOLD: usize = 16;
10
11#[derive(Clone)]
19pub struct OrderedMap<V> {
20 entries: Vec<(String, V)>,
21 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 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 pub fn get_index(&self, index: usize) -> Option<(&String, &V)> {
77 self.entries.get(index).map(|(k, v)| (k, v))
78 }
79
80 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 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 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 pub fn remove(&mut self, key: &str) -> Option<V> {
139 self.remove_full(key).map(|(_, v)| v)
140 }
141
142 pub fn iter(&self) -> Iter<'_, V> {
144 Iter(self.entries.iter())
145 }
146
147 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 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#[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
213pub 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 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}