ordered_hashmap/lib.rs
1use std::collections::HashMap;
2use std::hash::Hash;
3use std::marker::PhantomData;
4use std::vec::IntoIter;
5
6/// A custom `VecHashMap` struct that maintains the order of keys.
7/// It wraps a `Vec` to store keys and a `HashMap` to store key-value pairs.
8#[derive(Clone, Debug, PartialEq)]
9pub struct VecHashMap<K: Eq + Hash + Clone, V> {
10 pub values: Vec<(K, V)>,
11 pub map: HashMap<K, usize>,
12}
13
14impl<K: Eq + Hash + Clone, V> VecHashMap<K, V> {
15 /// Creates a new empty `VecHashMap`.
16 ///
17 /// # Examples
18 ///
19 /// ```
20 /// use ordered_hashmap::VecHashMap;
21 /// let ordered_map: VecHashMap<String, i32> = VecHashMap::new();
22 /// ```
23 pub fn new() -> Self {
24 VecHashMap {
25 values: Vec::new(),
26 map: HashMap::new(),
27 }
28 }
29
30 /// Returns `true` if the map contains a value for the specified key.
31 ///
32 /// # Examples
33 ///
34 /// ```
35 /// use ordered_hashmap::VecHashMap;
36 /// let mut ordered_map = VecHashMap::new();
37 /// ordered_map.insert("key1".to_string(), 42);
38 /// assert!(ordered_map.contains_key(&"key1".to_string()));
39 /// ```
40 pub fn contains_key(&self, k: &K) -> bool {
41 self.map.contains_key(k)
42 }
43
44 /// Inserts a key-value pair into the map. If the map did not have this key present, `None` is returned.
45 /// If the map did have this key present, the value is updated, and the old value is returned.
46 ///
47 /// # Examples
48 ///
49 /// ```
50 /// use ordered_hashmap::VecHashMap;
51 /// let mut ordered_map = VecHashMap::new();
52 /// ordered_map.insert("key1".to_string(), 99);
53 /// assert_eq!(ordered_map.get(&"key1".to_string()), Some(&99));
54 /// ```
55 pub fn insert(&mut self, key: K, value: V) {
56 if !self.map.contains_key(&key) {
57 let idx = self.values.len();
58 self.values.push((key.clone(), value));
59 self.map.insert(key, idx);
60 return;
61 }
62
63 let idx = self.map.get(&key).unwrap();
64 self.values[*idx] = (key, value);
65 }
66
67 /// Removes a key from the map, returning the value at the key if the key was previously in the map.
68 ///
69 /// # Examples
70 ///
71 /// ```
72 /// use ordered_hashmap::VecHashMap;
73 /// let mut ordered_map = VecHashMap::new();
74 /// ordered_map.insert("key1".to_string(), 42);
75 /// assert_eq!(ordered_map.remove(&"key1".to_string()), Some(42));
76 /// ```
77 pub fn remove(&mut self, key: &K) -> Option<V> {
78 if let Some(idx) = self.map.remove(&key) {
79 let (_, v) = self.values.remove(idx);
80 // Shifting Indices to left
81 for (_, cidx) in self.map.iter_mut() {
82 if *cidx > idx {
83 *cidx -= 1
84 }
85 }
86 return Some(v);
87 }
88 None
89 }
90
91 /// Gets the value of the specified key.
92 ///
93 /// # Examples
94 ///
95 /// ```
96 /// use ordered_hashmap::VecHashMap;
97 /// let mut ordered_map = VecHashMap::new();
98 /// ordered_map.insert("key1".to_string(), 42);
99 /// assert_eq!(ordered_map.get(&"key1".to_string()), Some(&42));
100 /// ```
101 pub fn get(&self, key: &K) -> Option<&V> {
102 if let Some(idx) = self.map.get(key) {
103 return Some(&self.values[*idx].1);
104 }
105
106 None
107 }
108
109 /// Gets a mutable reference to the value of the specified key.
110 //////
111
112 /// # Examples
113 ///
114 /// ```
115 /// use ordered_hashmap::VecHashMap;
116 /// let mut ordered_map = VecHashMap::new();
117 /// ordered_map.insert("key1".to_string(), 42);
118 /// *ordered_map.get_mut(&"key1".to_string()).unwrap() += 1;
119 /// assert_eq!(ordered_map.get(&"key1".to_string()), Some(&43));
120 /// ```
121 pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
122 if let Some(idx) = self.map.get(key) {
123 if let Some(val) = self.values.get_mut(*idx) {
124 return Some(&mut val.1);
125 }
126 return None;
127 }
128
129 None
130 }
131
132 /// Returns an iterator over the values in the ordered hash map.
133 ///
134 /// # Examples
135 ///
136 /// ```
137 /// use ordered_hashmap::VecHashMap;
138 /// let mut ordered_map = VecHashMap::new();
139 /// ordered_map.insert("key1".to_string(), 42);
140 /// ordered_map.insert("key2".to_string(), 24);
141 /// let values: Vec<_> = ordered_map.values().collect();
142 /// assert_eq!(values, vec![&42, &24]);
143 /// ```
144 pub fn values(&self) -> impl Iterator<Item=&V> {
145 return VecHashMapValuesIter {
146 index: 0,
147 vec: &self.values,
148 };
149 }
150
151 /// Returns a mutable iterator over the values in the ordered hash map.
152 ///
153 /// # Examples
154 ///
155 /// ```
156 /// use ordered_hashmap::VecHashMap;
157 /// let mut ordered_map = VecHashMap::new();
158 /// ordered_map.insert("key1".to_string(), 42);
159 /// ordered_map.insert("key2".to_string(), 24);
160 /// ordered_map.values_mut().for_each(|value| *value += 1);
161 /// assert_eq!(ordered_map.get(&"key1".to_string()), Some(&43));
162 /// assert_eq!(ordered_map.get(&"key2".to_string()), Some(&25));
163 /// ```
164 pub fn values_mut(&mut self) -> impl Iterator<Item=&mut V> {
165 return VecHashMapValuesMutIter {
166 index: 0,
167 vec: &mut self.values as *mut Vec<(K, V)>,
168 _marker: PhantomData,
169 };
170 }
171
172 /// Returns an iterator over the keys in the ordered hash map.
173 ///
174 /// # Examples
175 ///
176 /// ```
177 /// use ordered_hashmap::VecHashMap;
178 /// let mut ordered_map = VecHashMap::new();
179 /// ordered_map.insert("key1".to_string(), 42);
180 /// ordered_map.insert("key2".to_string(), 24);
181 /// let keys: Vec<_> = ordered_map.keys().collect();
182 /// assert_eq!(keys, vec![&"key1".to_string(), &"key2".to_string()]);
183 /// ```
184 pub fn keys(&self) -> impl Iterator<Item=&K> {
185 return VecHashMapKeysIter {
186 index: 0,
187 vec: &self.values,
188 };
189 }
190
191 /// Returns an iterator over the key-value pairs in the ordered hash map.
192 ///
193 /// # Examples
194 ///
195 /// ```
196 /// use ordered_hashmap::VecHashMap;
197 /// let mut ordered_map = VecHashMap::new();
198 /// ordered_map.insert("key1".to_string(), 42);
199 /// ordered_map.insert("key2".to_string(), 24);
200 /// let pairs: Vec<_> = ordered_map.iter().collect();
201 /// assert_eq!(pairs, vec![&("key1".to_string(), 42), &("key2".to_string(), 24)]);
202 /// ```
203 pub fn iter(&self) -> impl Iterator<Item=&(K, V)> {
204 self.values.iter()
205 }
206
207 /// Returns an into iterator of the key-value pairs in the map, in the order corresponding to their keys.
208 ///
209 /// # Examples
210 ///
211 /// ```
212 /// use ordered_hashmap::VecHashMap;
213 /// let mut ordered_map = VecHashMap::new();
214 /// ordered_map.insert("key1".to_string(), 42);
215 /// ordered_map.insert("key2".to_string(), 24);
216 /// let pairs: Vec<_> = ordered_map.iter().collect();
217 /// assert_eq!(pairs, vec![&("key1".to_string(), 42), &("key2".to_string(), 24)]);
218 /// ```
219 pub fn into_iter(self) -> IntoIter<(K, V)> {
220 self.values.into_iter()
221 }
222
223
224 /// Returns a mutable iterator over the key-value pairs in the ordered hash map.
225 ///
226 /// # Examples
227 ///
228 /// ```
229 /// use ordered_hashmap::VecHashMap;
230 /// let mut ordered_map = VecHashMap::new();
231 /// ordered_map.insert("key1".to_string(), 42);
232 /// ordered_map.insert("key2".to_string(), 24);
233 /// ordered_map.iter_mut().for_each(|(key, value)| *value += 1);
234 /// assert_eq!(ordered_map.get(&"key1".to_string()), Some(&43));
235 /// assert_eq!(ordered_map.get(&"key2".to_string()), Some(&25));
236 /// ```
237 pub fn iter_mut(&mut self) -> impl Iterator<Item=&mut (K, V)> {
238 self.values.iter_mut()
239 }
240
241
242 /// Returns a vector of the values in the map, in the order corresponding to their keys.
243 ///
244 /// # Examples
245 ///
246 /// ```
247 /// use ordered_hashmap::VecHashMap;
248 ///
249 /// let mut map = VecHashMap::new();
250 /// map.insert(1, "one");
251 /// map.insert(2, "two");
252 /// map.insert(3, "three");
253 ///
254 /// let values: Vec<_> = map.into_values().collect();
255 /// assert_eq!(values, vec!["one", "two", "three"]);
256 /// ```
257 pub fn into_values(self) -> VecHashMapIntoValuesIter<K, V> {
258 VecHashMapIntoValuesIter {
259 vec: self.values.into_iter()
260 }
261 }
262
263
264 /// Adds all key-value pairs from another `VecHashMap` to this one, without replacing any existing pairs.
265 ///
266 /// # Examples
267 ///
268 /// ```
269 /// use ordered_hashmap::VecHashMap;
270 ///
271 /// let mut map1 = VecHashMap::new();
272 /// map1.insert(1, "one");
273 ///
274 /// let mut map2 = VecHashMap::new();
275 /// map2.insert(2, "two");
276 ///
277 /// map1.extend(map2);
278 ///
279 /// assert_eq!(map1.get(&1), Some(&"one"));
280 /// assert_eq!(map1.get(&2), Some(&"two"));
281 /// ```
282 pub fn extend(&mut self, slice: VecHashMap<K, V>) {
283 slice.values.into_iter().for_each(|k| {
284 if !self.map.contains_key(&k.0) {
285 let idx = self.values.len();
286 self.map.insert(k.0.clone(), idx.clone());
287 self.values.push(k);
288 } else {
289 let idx = self.map[&k.0];
290 self.values[idx] = k;
291 }
292 });
293 }
294
295 /// Returns the number of key-value pairs in the map.
296 ///
297 /// # Examples
298 ///
299 /// ```
300 /// use ordered_hashmap::VecHashMap;
301 ///
302 /// let mut map = VecHashMap::new();
303 /// assert_eq!(map.len(), 0);
304 ///
305 /// map.insert(1, "one");
306 /// assert_eq!(map.len(), 1);
307 ///
308 /// map.insert(2, "two");
309 /// assert_eq!(map.len(), 2);
310 /// ```
311 pub fn len(&self) -> usize {
312 self.values.len()
313 }
314}
315
316pub struct VecHashMapIntoValuesIter<K: Eq + Hash + Clone, V> {
317 vec: IntoIter<(K, V)>,
318}
319
320impl<K: Eq + Hash + Clone, V> Iterator for VecHashMapIntoValuesIter<K, V> {
321 type Item = V;
322
323 fn next(&mut self) -> Option<Self::Item> {
324 if let Some(val) = self.vec.next() {
325 return Some(val.1);
326 }
327
328 None
329 }
330}
331
332pub struct VecHashMapKeysIter<'a, K: Eq + Hash + Clone, V> {
333 index: usize,
334 vec: &'a Vec<(K, V)>,
335}
336
337impl<'a, K: Eq + Hash + Clone, V> Iterator for VecHashMapKeysIter<'a, K, V> {
338 type Item = &'a K;
339
340 fn next(&mut self) -> Option<Self::Item> {
341 if self.index < self.vec.len() {
342 let item = Some(&self.vec[self.index].0);
343 self.index += 1;
344 return item;
345 }
346
347 None
348 }
349}
350
351pub struct VecHashMapValuesIter<'a, K: Eq + Hash + Clone, V> {
352 index: usize,
353 vec: &'a Vec<(K, V)>,
354}
355
356impl<'a, K: Eq + Hash + Clone, V> Iterator for VecHashMapValuesIter<'a, K, V> {
357 type Item = &'a V;
358
359 fn next(&mut self) -> Option<Self::Item> {
360 if self.index < self.vec.len() {
361 let item = Some(&self.vec[self.index].1);
362 self.index += 1;
363 return item;
364 }
365
366 None
367 }
368}
369
370pub struct VecHashMapValuesMutIter<'a, K: Eq + Hash + Clone, V> {
371 index: usize,
372 vec: *mut Vec<(K, V)>,
373 _marker: PhantomData<&'a mut Vec<(K, V)>>,
374}
375
376impl<'a, K: Eq + Hash + Clone, V: 'a> Iterator for VecHashMapValuesMutIter<'a, K, V> {
377 type Item = &'a mut V;
378
379 fn next(&mut self) -> Option<Self::Item> {
380 unsafe {
381 if self.index < (*self.vec).len() {
382 if let Some(val) = (*self.vec).get_mut(self.index) {
383 let item = Some(&mut val.1);
384 self.index += 1;
385 return item;
386 }
387 }
388 }
389
390 None
391 }
392}