vector_map/
lib.rs

1#![cfg_attr(feature = "nightly", feature(test))]
2#[cfg(feature = "nightly")]
3extern crate test;
4
5#[cfg(feature = "serde_impl")]
6pub mod serde;
7pub mod set;
8
9use contracts::*;
10use std::{
11    iter::FromIterator,
12    ops::{Index, IndexMut},
13};
14
15/// A std::vec::Vec based Map, motivated by the fact that, for some key types,
16/// iterating over a vector can be faster than other methods for small maps.
17///
18/// Most of the operations on this map implementation work in O(n), including
19/// some of the ones that are O(1) in HashMap. However, optimizers can work magic with
20/// contiguous arrays like Vec, and so for small sets (up to 256 elements for integer keys,
21/// for example), iterating through a vector actually yields better performance than the
22/// less branch- and cache-predictable hash maps.
23///
24/// To keep item removal fast, this container doesn't form guaranties on item ordering,
25/// nor on the stability of the ordering.
26///
27/// The good news about that is that you're free to mutate keys if your use-case requires that,
28/// though I wouldn't recommend it: the underlying vector can be accessed through the unsafe part
29/// of the API, in hopes to discourage you from using it.
30///
31/// Checking equality between maps is defined as "both maps are the same set", and performs worst
32/// for maps that are permutations of each other.
33#[derive(Clone, Default)]
34pub struct VecMap<K, V> {
35    keys: Vec<K>,
36    values: Vec<V>,
37}
38
39// #[invariant(self.keys.len() == self.values.len())]
40impl<K, V> VecMap<K, V> {
41    #[post(ret.len() == 0)]
42    pub fn new() -> Self
43    where
44        K: PartialEq,
45    {
46        Self::with_capacity(0)
47    }
48
49    #[post(ret.len() == 0)]
50    pub fn with_capacity(capacity: usize) -> Self
51    where
52        K: PartialEq,
53    {
54        VecMap {
55            keys: Vec::with_capacity(capacity),
56            values: Vec::with_capacity(capacity),
57        }
58    }
59
60    pub fn len(&self) -> usize {
61        self.keys.len()
62    }
63
64    pub fn is_empty(&self) -> bool {
65        self.len() == 0
66    }
67
68    pub fn capacity(&self) -> usize {
69        self.keys.capacity().min(self.values.capacity())
70    }
71
72    // #[post(self.len() == 0)]
73    pub fn clear(&mut self) {
74        self.keys.clear();
75        self.values.clear();
76    }
77
78    #[inline]
79    fn position<Q: PartialEq<K>>(&self, key: &Q) -> Option<usize> {
80        self.keys.iter().position(|k| key == k)
81    }
82
83    pub fn contains_key<Q: PartialEq<K>>(&self, key: &Q) -> bool {
84        self.position(key).is_some()
85    }
86
87    #[post(!self.contains_key(key) -> ret.is_none())]
88    #[post(self.contains_key(key) -> ret.is_some())]
89    pub fn get<'l, Q: PartialEq<K>>(&'l self, key: &Q) -> Option<&'l V> {
90        self.position(key).map(|p| &self.values[p])
91    }
92
93    #[post(!old(self.contains_key(key)) -> ret.is_none())]
94    #[post(old(self.contains_key(key)) -> ret.is_some())]
95    pub fn get_mut<'l, Q: PartialEq<K>>(&'l mut self, key: &Q) -> Option<&'l mut V> {
96        self.position(key).map(move |p| &mut self.values[p])
97    }
98
99    #[post(!old(self.contains_key(&key)) -> ret.is_none())]
100    #[post(old(self.contains_key(&key)) -> ret.is_some())]
101    pub fn insert(&mut self, key: K, mut value: V) -> Option<V>
102    where
103        K: PartialEq,
104    {
105        if let Some(position) = self.position(&key) {
106            std::mem::swap(&mut value, &mut self.values[position]);
107            Some(value)
108        } else {
109            self.keys.push(key);
110            self.values.push(value);
111            None
112        }
113    }
114
115    pub fn drain<'l>(&'l mut self) -> Drain<'l, K, V> {
116        Drain {
117            iter: self.keys.drain(..).zip(self.values.drain(..)),
118        }
119    }
120
121    pub fn reserve(&mut self, additional: usize) {
122        self.keys.reserve(additional);
123        self.values.reserve(additional);
124    }
125
126    pub fn shrink_to_fit(&mut self) {
127        self.keys.shrink_to_fit();
128        self.values.shrink_to_fit();
129    }
130
131    #[post(!self.contains_key(key) -> ret.is_none())]
132    #[post(self.contains_key(key) -> ret.is_some())]
133    pub fn get_key_value<'l, Q: PartialEq<K>>(&'l self, key: &Q) -> Option<(&'l K, &'l V)> {
134        self.position(key).map(|p| (&self.keys[p], &self.values[p]))
135    }
136
137    #[post(!old(self.contains_key(key)) -> ret.is_none())]
138    #[post(old(self.contains_key(key)) -> ret.is_some())]
139    #[post(self.contains_key(key) == false)]
140    pub fn remove<Q: PartialEq<K>>(&mut self, key: &Q) -> Option<V> {
141        if let Some(index) = self.position(key) {
142            self.keys.swap_remove(index);
143            Some(self.values.swap_remove(index))
144        } else {
145            None
146        }
147    }
148
149    #[post(!old(self.contains_key(key)) -> ret.is_none())]
150    #[post(old(self.contains_key(key)) -> ret.is_some())]
151    #[post(self.contains_key(key) == false)]
152    pub fn remove_entry<Q: PartialEq<K>>(&mut self, key: &Q) -> Option<(K, V)> {
153        if let Some(index) = self.position(key) {
154            Some((self.keys.swap_remove(index), self.values.swap_remove(index)))
155        } else {
156            None
157        }
158    }
159
160    pub fn retain<F: FnMut(&K, &mut V) -> bool>(&mut self, mut f: F) {
161        for i in (0..self.len()).rev() {
162            if !f(&self.keys[i], &mut self.values[i]) {
163                self.keys.swap_remove(i);
164                self.values.swap_remove(i);
165            }
166        }
167    }
168
169    pub fn iter<'a>(&'a self) -> Iter<'a, K, V> {
170        Iter {
171            iter: self.keys.iter().zip(self.values.iter()),
172        }
173    }
174
175    pub fn iter_mut<'a>(&'a mut self) -> IterMut<'a, K, V> {
176        IterMut {
177            iter: self.keys.iter().zip(self.values.iter_mut()),
178        }
179    }
180
181    pub fn sort(&mut self)
182    where
183        K: Ord,
184    {
185        let mut indices: Vec<usize> = (0..self.len()).collect();
186        indices.sort_unstable_by_key(|i| &self.keys[*i]);
187        reorder_vec(&mut self.keys, indices.iter().copied());
188        reorder_vec(&mut self.values, indices.iter().copied());
189    }
190
191    /// Much faster than `self == other`, but will return false if the order of the data isn't identical.
192    /// Note that for the order of data with two `VecMap`s to be identical, they must either have been both sorted,
193    /// or they must have undergone the insertion and removal of keys in the same order.
194    pub unsafe fn identical(&self, other: &Self) -> bool
195    where
196        K: PartialEq,
197        V: PartialEq,
198    {
199        self.keys == other.keys && self.values == other.values
200    }
201
202    pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
203        Keys {
204            iter: self.keys.iter(),
205            _phantom: Default::default(),
206        }
207    }
208
209    pub fn values<'a>(&'a self) -> Values<'a, K, V> {
210        Values {
211            iter: self.values.iter(),
212            _phantom: Default::default(),
213        }
214    }
215}
216
217impl<K: std::fmt::Debug, V: std::fmt::Debug> std::fmt::Debug for VecMap<K, V> {
218    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
219        f.debug_map().entries(self.iter()).finish()
220    }
221}
222
223fn reorder_vec<T>(vec: &mut Vec<T>, order: impl Iterator<Item = usize>) {
224    use std::mem::MaybeUninit;
225    let mut buffer: Vec<MaybeUninit<T>> = vec.iter().map(|_| MaybeUninit::uninit()).collect();
226    for (from, to) in order.enumerate() {
227        std::mem::swap(&mut vec[to], unsafe { &mut *(buffer[from].as_mut_ptr()) });
228    }
229    for i in 0..vec.len() {
230        std::mem::swap(&mut vec[i], unsafe { &mut *(buffer[i].as_mut_ptr()) });
231    }
232}
233
234impl<K: PartialEq, V: PartialEq> PartialEq for VecMap<K, V> {
235    fn eq(&self, other: &Self) -> bool {
236        if self.len() != other.len() {
237            return false;
238        }
239        for (key, value) in self.iter() {
240            match other.get(key) {
241                Some(v) if value == v => {}
242                _ => return false,
243            }
244        }
245        true
246    }
247}
248
249impl<'a, K: PartialEq + Copy + 'a, V: Copy + 'a> Extend<(&'a K, &'a V)> for VecMap<K, V> {
250    fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
251        for (key, value) in iter.into_iter() {
252            self.insert(*key, *value);
253        }
254    }
255}
256
257impl<'a, K: PartialEq, V> Extend<(K, V)> for VecMap<K, V> {
258    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
259        for (key, value) in iter.into_iter() {
260            self.insert(key, value);
261        }
262    }
263}
264
265impl<K: PartialEq, V> FromIterator<(K, V)> for VecMap<K, V> {
266    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
267        let iterator = iter.into_iter();
268        let lower = iterator.size_hint().0;
269        let mut this = Self::with_capacity(lower);
270        this.extend(iterator);
271        this
272    }
273}
274
275impl<'a, Q: PartialEq<K>, K, V> Index<&'a Q> for VecMap<K, V> {
276    type Output = V;
277    fn index(&self, key: &'a Q) -> &Self::Output {
278        self.get(key).unwrap()
279    }
280}
281
282impl<'a, Q: PartialEq<K>, K, V> IndexMut<&'a Q> for VecMap<K, V> {
283    fn index_mut(&mut self, key: &'a Q) -> &mut Self::Output {
284        self.get_mut(key).unwrap()
285    }
286}
287
288impl<'a, K, V> IntoIterator for &'a VecMap<K, V> {
289    type Item = (&'a K, &'a V);
290    type IntoIter = Iter<'a, K, V>;
291    fn into_iter(self) -> Self::IntoIter {
292        self.iter()
293    }
294}
295
296impl<'a, K, V> IntoIterator for &'a mut VecMap<K, V> {
297    type Item = (&'a K, &'a mut V);
298    type IntoIter = IterMut<'a, K, V>;
299    fn into_iter(self) -> Self::IntoIter {
300        self.iter_mut()
301    }
302}
303
304impl<K, V> IntoIterator for VecMap<K, V> {
305    type Item = (K, V);
306    type IntoIter = IntoIter<K, V>;
307    fn into_iter(self) -> Self::IntoIter {
308        IntoIter {
309            iter: self.keys.into_iter().zip(self.values.into_iter()),
310        }
311    }
312}
313
314#[derive(Clone)]
315pub struct IntoIter<K, V> {
316    iter: std::iter::Zip<std::vec::IntoIter<K>, std::vec::IntoIter<V>>,
317}
318
319impl<K, V> Iterator for IntoIter<K, V> {
320    type Item = (K, V);
321
322    fn next(&mut self) -> Option<(K, V)> {
323        self.iter.next()
324    }
325
326    fn size_hint(&self) -> (usize, Option<usize>) {
327        self.iter.size_hint()
328    }
329}
330
331impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
332    fn next_back(&mut self) -> Option<(K, V)> {
333        self.iter.next_back()
334    }
335}
336
337impl<K, V> ExactSizeIterator for IntoIter<K, V> {
338    fn len(&self) -> usize {
339        self.iter.len()
340    }
341}
342
343/// A view into a single occupied location in a `VecMap`.
344///
345/// See [`VecMap::entry`](struct.VecMap.html#method.entry) for details.
346pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
347    map: &'a mut VecMap<K, V>,
348    index: usize,
349}
350
351/// A view into a single vacant location in a `VecMap`.
352///
353/// See [`VecMap::entry`](struct.VecMap.html#method.entry) for details.
354pub struct VacantEntry<'a, K: 'a, V: 'a> {
355    map: &'a mut VecMap<K, V>,
356    key: K,
357}
358
359/// A view into a single entry in a `VecMap`.
360///
361/// See [`VecMap::entry`](struct.VecMap.html#method.entry) for details.
362pub enum Entry<'a, K: 'a, V: 'a> {
363    /// An occupied entry.
364    Occupied(OccupiedEntry<'a, K, V>),
365
366    /// A vacant entry.
367    Vacant(VacantEntry<'a, K, V>),
368}
369use Entry::*;
370impl<'a, K, V> Entry<'a, K, V> {
371    /// Ensures that the entry is occupied by inserting the given value if it is vacant.
372    ///
373    /// Returns a mutable reference to the entry's value.
374    pub fn or_insert(self, default: V) -> &'a mut V {
375        match self {
376            Occupied(entry) => entry.into_mut(),
377            Vacant(entry) => entry.insert(default),
378        }
379    }
380
381    /// Ensures that the entry is occupied by inserting the the result of the given function if it
382    /// is vacant.
383    ///
384    /// Returns a mutable reference to the entry's value.
385    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
386        match self {
387            Occupied(entry) => entry.into_mut(),
388            Vacant(entry) => entry.insert(default()),
389        }
390    }
391}
392
393impl<'a, K, V> OccupiedEntry<'a, K, V> {
394    /// Returns a reference to the entry's value.
395    pub fn get(&self) -> &V {
396        &self.map.values[self.index]
397    }
398
399    /// Returns a mutable reference to the entry's value.
400    pub fn get_mut(&mut self) -> &mut V {
401        &mut self.map.values[self.index]
402    }
403
404    /// Returns a mutable reference to the entry's value with the same lifetime as the map.
405    pub fn into_mut(self) -> &'a mut V {
406        &mut self.map.values[self.index]
407    }
408
409    /// Replaces the entry's value with the given one and returns the previous value.
410    pub fn insert(&mut self, value: V) -> V {
411        std::mem::replace(self.get_mut(), value)
412    }
413
414    /// Removes the entry from the map and returns its value.
415    pub fn remove(self) -> V {
416        self.map.keys.swap_remove(self.index);
417        self.map.values.swap_remove(self.index)
418    }
419}
420
421impl<'a, K, V> VacantEntry<'a, K, V> {
422    /// Inserts the entry into the map with the given value.
423    ///
424    /// Returns a mutable reference to the entry's value with the same lifetime as the map.
425    pub fn insert(self, value: V) -> &'a mut V {
426        self.map.keys.push(self.key);
427        self.map.values.push(value);
428        self.map.values.last_mut().unwrap()
429    }
430}
431
432/// A draining iterator over a `VecMap`.
433///
434/// See [`VecMap::drain`](struct.VecMap.html#method.drain) for details.
435pub struct Drain<'a, K: 'a, V: 'a> {
436    iter: std::iter::Zip<std::vec::Drain<'a, K>, std::vec::Drain<'a, V>>,
437}
438
439/// An iterator yielding references to a `VecMap`'s keys and their corresponding values.
440///
441/// See [`VecMap::iter`](struct.VecMap.html#method.iter) for details.
442#[derive(Clone)]
443pub struct Iter<'a, K: 'a, V: 'a> {
444    iter: std::iter::Zip<std::slice::Iter<'a, K>, std::slice::Iter<'a, V>>,
445}
446
447/// An iterator yielding references to a `VecMap`'s keys and mutable references to their
448/// corresponding values.
449///
450/// See [`VecMap::iter_mut`](struct.VecMap.html#method.iter_mut) for details.
451pub struct IterMut<'a, K: 'a, V: 'a> {
452    iter: std::iter::Zip<std::slice::Iter<'a, K>, std::slice::IterMut<'a, V>>,
453}
454
455/// An iterator yielding references to a `VecMap`'s keys in arbitrary order.
456///
457/// See [`VecMap::keys`](struct.VecMap.html#method.keys) for details.
458pub struct Keys<'a, K: 'a, V> {
459    iter: std::slice::Iter<'a, K>,
460    _phantom: std::marker::PhantomData<V>,
461}
462
463impl<'a, K, V> Clone for Keys<'a, K, V> {
464    fn clone(&self) -> Self {
465        Keys {
466            iter: self.iter.clone(),
467            _phantom: Default::default(),
468        }
469    }
470}
471
472/// An iterator yielding references to a `VecMap`'s values in arbitrary order.
473///
474/// See [`VecMap::values`](struct.VecMap.html#method.values) for details.
475pub struct Values<'a, K, V: 'a> {
476    iter: std::slice::Iter<'a, V>,
477    _phantom: std::marker::PhantomData<K>,
478}
479
480impl<'a, K, V> Clone for Values<'a, K, V> {
481    fn clone(&self) -> Self {
482        Values {
483            iter: self.iter.clone(),
484            _phantom: Default::default(),
485        }
486    }
487}
488
489macro_rules! impl_iter {
490    ($typ:ty, $item:ty) => {
491        impl<'a, K, V> Iterator for $typ {
492            type Item = $item;
493
494            fn next(&mut self) -> Option<Self::Item> {
495                self.iter.next()
496            }
497
498            fn size_hint(&self) -> (usize, Option<usize>) {
499                self.iter.size_hint()
500            }
501        }
502
503        impl<'a, K, V> DoubleEndedIterator for $typ {
504            fn next_back(&mut self) -> Option<Self::Item> {
505                self.iter.next_back()
506            }
507        }
508
509        impl<'a, K, V> ExactSizeIterator for $typ {
510            fn len(&self) -> usize {
511                self.iter.len()
512            }
513        }
514    };
515}
516impl_iter! {Drain<'a,K,V>,  (K,V)}
517impl_iter! {Iter<'a,K,V>,  (&'a K, &'a V)}
518impl_iter! {IterMut<'a,K,V>,  (&'a K, &'a mut V)}
519impl_iter! {Keys<'a,K,V>,  &'a K}
520impl_iter! {Values<'a,K,V>,  &'a V}
521
522#[test]
523fn reorder() {
524    let n = 128;
525    let m = 128;
526    let expected: Vec<usize> = (0..n).collect();
527    let mut test = expected.clone();
528    for i in 0..m {
529        let rands: Vec<usize> = test.iter().map(|_| rand::random()).collect();
530        test.sort_by_key(|x| rands[*x]);
531        let mut indices: Vec<usize> = (0..test.len()).collect();
532        indices.sort_unstable_by_key(|i| test[*i]);
533        reorder_vec(&mut test, indices.into_iter());
534        assert_eq!(test, expected);
535    }
536    for i in 0..m {
537        let mut map: VecMap<usize, f32> = VecMap::with_capacity(n);
538        for n in 0..n {
539            map.insert(rand::random(), rand::random());
540        }
541        let clone = map.clone();
542        map.sort();
543        let mut map_iter = map.iter();
544        let first = *map_iter.by_ref().take(1).next().unwrap().0;
545        assert!(map_iter
546            .fold(Some(first), |acc, (k, _v)| {
547                let k = *k;
548                match acc {
549                    Some(v) if v < k => Some(k),
550                    _ => None,
551                }
552            })
553            .is_some());
554        assert_eq!(map, clone);
555    }
556}
vector_map/lib.rs

vector_map/
lib.rs
