more_collections/vec_map/
mod.rs

1#![warn(missing_docs, missing_debug_implementations)]
2//! [`VecMap`] is a [`Vec`]-backed map, for faster random access.
3mod iter;
4
5use std::cmp::Ordering;
6use std::fmt;
7use std::marker::PhantomData;
8use std::ops::Index;
9use std::ops::IndexMut;
10
11pub use crate::vec_map::iter::*;
12
13/// A key that can be used in a map without needing a hasher.
14///
15/// There needs to be a 1:1 correspondence between `IndexKey` and it's index.
16/// Typically this is used with a newtype. A blanket implementation exists for
17/// types that implement `From<usize>`, `Into<usize>`, and `Copy`. By using a
18/// crate such as [derive_more](https://docs.rs/derive_more/latest/derive_more/)
19/// these traits can be derived.
20pub trait IndexKey: Copy {
21    /// Returns the unique index that this key is associated with.
22    fn as_index(&self) -> usize;
23
24    /// Converts the index back to the key.
25    fn from_index(index: usize) -> Self;
26}
27
28impl<T> IndexKey for T
29where
30    T: From<usize> + Into<usize> + Copy,
31{
32    fn as_index(&self) -> usize {
33        (*self).into()
34    }
35
36    fn from_index(index: usize) -> Self {
37        index.into()
38    }
39}
40
41/// A [`Vec`]-backed map.
42///
43/// It has faster random access performance and slower iteration speed compared
44/// to other maps. Makes most sense for relatively dense maps or if iteration is
45/// needed significantly less than random access. In case of doubt, benchmark it
46/// for your usecase.
47///
48/// # Performance
49///
50/// `VecMap` outperforms `HashMap`, `IndexMap`, and `BTreeMap` for random access
51/// (such as `get()`) and random modifications (such as `insert()`). For
52/// modifications this is only true **iff `VecMap` does not need to do any
53/// resizing**. Therefore, if performance is essential, it is strongly
54/// recommended to initialize `VecMap` with `with_capacity()`.
55///
56/// Iteration order follows the natural ordering of [`IndexKey::as_index()`].
57///
58/// # Serialization and deserialization
59///
60/// An optional feature that can be unlocked with the `serde` feature. `VecMap`s
61/// are serialized and deserialized as `Vec<Option<V>>`.
62#[derive(Clone)]
63#[cfg_attr(
64    feature = "serde",
65    derive(serde::Deserialize),
66    serde(from = "Vec<Option<V>>")
67)]
68pub struct VecMap<K, V> {
69    data: Vec<Option<V>>,
70    len: usize,
71    _marker: PhantomData<K>,
72}
73
74impl<K: IndexKey, V> VecMap<K, V> {
75    /// Initializes an empty [`VecMap`].
76    ///
77    /// For performance reasons it's almost always better to avoid dynamic
78    /// resizing by using [`Self::with_capacity()`] instead.
79    #[must_use]
80    pub const fn new() -> Self {
81        Self {
82            data: vec![],
83            len: 0,
84            _marker: PhantomData,
85        }
86    }
87
88    /// Returns the number of elements the map can hold without reallocating.
89    ///
90    /// The index range of items that the map can hold without reallocating is
91    /// `0..capacity`.
92    #[must_use]
93    pub fn capacity(&self) -> usize {
94        self.data.len()
95    }
96
97    /// Initializes [`VecMap`] with capacity to hold exactly `n` elements in the
98    /// index range of `0..n`.
99    #[must_use]
100    pub fn with_capacity(n: usize) -> Self {
101        let mut data = Vec::with_capacity(n);
102        data.resize_with(n, || None);
103        Self {
104            data,
105            len: 0,
106            _marker: PhantomData,
107        }
108    }
109
110    /// Initializes [`VecMap`] with `n` occurences of `elem`.
111    pub fn from_elem(elem: V, n: usize) -> Self
112    where
113        V: Clone,
114    {
115        Self {
116            data: vec![Some(elem); n],
117            len: n,
118            _marker: PhantomData,
119        }
120    }
121
122    /// Clears all data from the [`VecMap`] without changing the capacity.
123    pub fn clear(&mut self) {
124        self.len = 0;
125        let capacity = self.data.len();
126        self.data.clear();
127        self.data.resize_with(capacity, || None);
128    }
129
130    /// Reserve capacity for `additional` key-value pairs.
131    pub fn reserve(&mut self, additional: usize) {
132        self.data.resize_with(self.data.len() + additional, || None);
133    }
134
135    /// Inserts a key-value pair into the map.
136    ///
137    /// If the key is present in the map, the value is updated and the old value
138    /// is returned. Otherwise, [`None`] is returned.
139    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
140        let index = key.as_index();
141        if index >= self.capacity() {
142            self.data
143                .extend((0..=(index - self.data.len())).map(|_| None));
144        }
145
146        let existing = self.data[index].replace(value);
147        if existing.is_none() {
148            self.len += 1;
149        }
150        existing
151    }
152
153    /// Removes the key-value pair indicated by `key`.
154    ///
155    /// If the key was present, it is returned. Otherwise [`None`] is returned.
156    pub fn remove(&mut self, key: K) -> Option<V> {
157        let index = key.as_index();
158        if index >= self.data.len() {
159            None
160        } else {
161            let existing = self.data[index].take();
162            if existing.is_some() {
163                self.len -= 1;
164            }
165            existing
166        }
167    }
168
169    /// Removes the last key-value pair.
170    ///
171    /// Worst case performance is O(n) in case the value is at the first index,
172    /// where n = the capacity.
173    pub fn pop(&mut self) -> Option<(K, V)> {
174        if self.is_empty() {
175            None
176        } else {
177            self.data.iter_mut().enumerate().rev().find_map(|(i, x)| {
178                x.take().map(|x| {
179                    self.len -= 1;
180                    (K::from_index(i), x)
181                })
182            })
183        }
184    }
185
186    /// Iterates over each key-value pair in the map and keep those where the
187    /// closure `keep` returns `true`.
188    ///
189    /// The elements are visited in order.
190    pub fn retain<F>(&mut self, mut keep: F)
191    where
192        F: FnMut(K, &mut V) -> bool,
193    {
194        if !self.is_empty() {
195            self.data
196                .iter_mut()
197                .enumerate()
198                .for_each(|(i, value_option)| {
199                    if let Some(value) = value_option.as_mut() {
200                        if !keep(K::from_index(i), value) {
201                            self.len -= 1;
202                            value_option.take();
203                        }
204                    }
205                });
206        }
207    }
208
209    /// Get the given key's entry in the map for insertion and/or in-place
210    /// manipulation.
211    pub fn entry(&mut self, key: K) -> Entry<K, V> {
212        let index = key.as_index();
213        if index >= self.data.len() {
214            Entry::Vacant(key, self)
215        } else {
216            if self.data[index].is_some() {
217                return Entry::Occupied(self.data[index].as_mut().unwrap());
218            }
219            return Entry::Vacant(key, self);
220        }
221    }
222
223    /// Returns a reference to the value associated with `key` if it exists,
224    /// otherwise returns `None`.
225    pub fn get(&self, key: K) -> Option<&V> {
226        let index = key.as_index();
227        if index >= self.data.len() {
228            None
229        } else {
230            self.data[index].as_ref()
231        }
232    }
233
234    /// Returns a mutable reference to the value associated with `key` if it
235    /// exists, otherwise returns `None`.
236    pub fn get_mut(&mut self, key: K) -> Option<&mut V> {
237        let index = key.as_index();
238        if index >= self.data.len() {
239            None
240        } else {
241            self.data[index].as_mut()
242        }
243    }
244
245    /// Return the number of key-value pairs in the map.
246    #[must_use]
247    pub const fn len(&self) -> usize {
248        self.len
249    }
250
251    /// Returns `true` if the map contains no elements.
252    #[must_use]
253    pub const fn is_empty(&self) -> bool {
254        self.len() == 0
255    }
256
257    /// Returns `true` if the map contains an item with the specified `key`.
258    pub fn contains_key(&self, key: K) -> bool {
259        self.get(key).is_some()
260    }
261
262    /// Returns an iterator over the key-value pairs of the map, following the
263    /// natural order of the keys.
264    #[must_use]
265    pub fn iter(&self) -> Iter<'_, K, V> {
266        Iter {
267            inner: self.data.iter().enumerate(),
268            len: self.len,
269            _marker: PhantomData,
270        }
271    }
272
273    /// Returns an iterator over the key-value pairs of the map, with the values
274    /// being mutable, following the natural order of the keys.
275    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
276        IterMut {
277            inner: self.data.iter_mut().enumerate(),
278            len: self.len,
279            _marker: PhantomData,
280        }
281    }
282
283    /// Returns an iterator over the keys of the map following the natural order
284    /// of the keys.
285    #[must_use]
286    pub fn keys(&self) -> Keys<'_, K, V> {
287        Keys {
288            inner: self.data.iter().enumerate(),
289            len: self.len,
290            _marker: PhantomData,
291        }
292    }
293
294    /// Returns an iterator over the values of the map following the natural
295    /// order of the keys.
296    #[must_use]
297    pub fn values(&self) -> Values<'_, V> {
298        Values {
299            inner: self.data.iter(),
300            len: self.len,
301        }
302    }
303}
304
305impl<K: IndexKey, V> Default for VecMap<K, V> {
306    fn default() -> Self {
307        Self::new()
308    }
309}
310
311impl<K, V: PartialEq> PartialEq for VecMap<K, V> {
312    fn eq(&self, other: &Self) -> bool {
313        if self.len != other.len {
314            return false;
315        }
316
317        let shared_capacity = self.data.len().min(other.data.len());
318        if self.data[..shared_capacity] != other.data[..shared_capacity] {
319            return false;
320        }
321
322        match self.data.len().cmp(&other.data.len()) {
323            Ordering::Less => other.data[shared_capacity..].iter().all(Option::is_none),
324            Ordering::Equal => true,
325            Ordering::Greater => self.data[shared_capacity..].iter().all(Option::is_none),
326        }
327    }
328}
329
330impl<K, V: Eq> Eq for VecMap<K, V> {}
331
332impl<K: IndexKey, V> Index<K> for VecMap<K, V> {
333    type Output = V;
334
335    fn index(&self, key: K) -> &Self::Output {
336        let index = key.as_index();
337        if index >= self.data.len() {
338            panic!("{index} is out of bounds");
339        } else {
340            self.data[index]
341                .as_ref()
342                .unwrap_or_else(|| panic!("There is no item at index {index}"))
343        }
344    }
345}
346
347impl<K: IndexKey, V> IndexMut<K> for VecMap<K, V> {
348    fn index_mut(&mut self, key: K) -> &mut Self::Output {
349        let index = key.as_index();
350        if index >= self.data.len() {
351            panic!("{index} is out of bounds");
352        } else {
353            self.data[index]
354                .as_mut()
355                .unwrap_or_else(|| panic!("There is no item at index {index}"))
356        }
357    }
358}
359
360/// Entry for an existing key-value pair or a vacant location to insert one.
361pub enum Entry<'a, K: IndexKey, V> {
362    /// Vacant slot (i.e. the key does not exist in the map).
363    Vacant(K, &'a mut VecMap<K, V>),
364    /// Occupied slot.
365    Occupied(&'a mut V),
366}
367
368impl<'a, K: IndexKey, V> Entry<'a, K, V> {
369    /// Inserts the given default value in the entry if it is vacant.
370    ///
371    /// Returns a mutable reference to the existing value if it is occupied, or
372    /// a mutable reference to the newly added value if it is vacant.
373    pub fn or_insert(self, default: V) -> &'a mut V {
374        match self {
375            Entry::Occupied(entry) => entry,
376            Entry::Vacant(key, map) => {
377                map.insert(key, default);
378                map.get_mut(key).unwrap()
379            }
380        }
381    }
382
383    /// Inserts the result of the `creator` function in the entry if it is
384    /// vacant.
385    ///
386    /// Returns a mutable reference to the existing value if it is occupied, or
387    /// a mutable reference to the newly added value if it is vacant.
388    pub fn or_insert_with<F>(self, creator: F) -> &'a mut V
389    where
390        F: FnOnce() -> V,
391    {
392        match self {
393            Entry::Occupied(entry) => entry,
394            Entry::Vacant(key, map) => {
395                map.insert(key, creator());
396                map.get_mut(key).unwrap()
397            }
398        }
399    }
400
401    /// Inserts the default value in the entry if it is vacant.
402    ///
403    /// Returns a mutable reference to the existing value if it is occupied, or
404    /// a mutable reference to the newly added value if it is vacant.
405    pub fn or_default(self) -> &'a mut V
406    where
407        V: Default,
408    {
409        match self {
410            Entry::Occupied(entry) => entry,
411            Entry::Vacant(key, map) => {
412                map.insert(key, V::default());
413                map.get_mut(key).unwrap()
414            }
415        }
416    }
417
418    /// Modifies the entry if it is occupied.
419    #[expect(
420        clippy::return_self_not_must_use,
421        reason = "no need to use entry after this operation"
422    )]
423    pub fn and_modify<F>(self, f: F) -> Self
424    where
425        F: FnOnce(&mut V),
426    {
427        match self {
428            Entry::Occupied(o) => {
429                f(o);
430                Entry::Occupied(o)
431            }
432            x @ Entry::Vacant(_, _) => x,
433        }
434    }
435}
436
437impl<K: IndexKey + fmt::Debug, V: fmt::Debug> fmt::Debug for Entry<'_, K, V> {
438    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
439        match *self {
440            Entry::Occupied(ref value) => f.debug_tuple(stringify!(Entry)).field(value).finish(),
441            Entry::Vacant(ref key, _) => f.debug_tuple(stringify!(Entry)).field(key).finish(),
442        }
443    }
444}
445
446impl<K: IndexKey, V> FromIterator<(K, V)> for VecMap<K, V> {
447    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
448        let iter = iter.into_iter();
449        let (lower_bound, _) = iter.size_hint();
450
451        let mut map = VecMap::with_capacity(lower_bound);
452        for (key, value) in iter {
453            map.insert(key, value);
454        }
455        map
456    }
457}
458
459impl<K: IndexKey, V> Extend<(K, V)> for VecMap<K, V> {
460    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
461        // extend does not attempt to reserve additional space because the space needed
462        // is dependent on the keys that are added
463        iter.into_iter().for_each(|(key, value)| {
464            self.insert(key, value);
465        });
466    }
467}
468
469impl<K: IndexKey + fmt::Debug, V: fmt::Debug> fmt::Debug for VecMap<K, V> {
470    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
471        f.debug_map().entries(self.iter()).finish()
472    }
473}
474
475impl<K, V> From<Vec<Option<V>>> for VecMap<K, V> {
476    fn from(value: Vec<Option<V>>) -> Self {
477        Self {
478            len: value.iter().filter(|x| x.is_some()).count(),
479            data: value,
480            _marker: PhantomData,
481        }
482    }
483}
484
485#[cfg(feature = "serde")]
486impl<K, V> serde::Serialize for VecMap<K, V>
487where
488    K: IndexKey,
489    V: serde::Serialize,
490{
491    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
492    where
493        S: serde::Serializer,
494    {
495        serializer.collect_seq(self.data.iter())
496    }
497}
498
499/// Create a `VecMap` containing the arguments.
500///
501/// There are two forms of this macro:
502///
503/// - Create a [`VecMap`] containing a give list of key-value pairs:
504///
505/// ```
506/// # use more_collections::vecmap;
507/// let map = vecmap! {
508///     1usize => "a",
509///     2 => "b",
510/// };
511/// assert_eq!(map[1], "a");
512/// assert_eq!(map[2], "b");
513/// assert_eq!(map.get(3), None);
514///
515/// // 1 is the first key
516/// assert_eq!(map.keys().next(), Some(1));
517/// ```
518/// - Create a [`VecMap`] from a given element and size:
519/// ```
520/// # use more_collections::vecmap;
521/// # use more_collections::VecMap;
522/// let counters: VecMap<usize, usize> = vecmap! { 0; 3 };
523///
524/// assert_eq!(
525///     vec![0, 0, 0],
526///     counters.values().copied().collect::<Vec<_>>()
527/// );
528/// assert_eq!(3, counters.len());
529/// assert_eq!(3, counters.capacity());
530/// ```
531#[macro_export]
532macro_rules! vecmap {
533    (@single $($x:tt)*) => (());
534    (@count $($rest:expr),*) => (<[()]>::len(&[$($crate::vecmap!(@single $rest)),*]));
535
536    ($elem:expr; $n:expr) => (
537        $crate::vec_map::VecMap::from_elem($elem, $n);
538    );
539
540    ($($key:expr => $value:expr,)+) => { $crate::vecmap!($($key => $value),+) };
541    ($($key:expr => $value:expr),*) => {
542        {
543            let _cap = $crate::vecmap!(@count $($key),*);
544            let mut _map = $crate::vec_map::VecMap::with_capacity(_cap);
545            $(
546                _map.insert($key, $value);
547            )*
548            _map
549        }
550    };
551}
552
553#[cfg(test)]
554mod test {
555    use derive_more::From;
556    use derive_more::Into;
557
558    use super::*;
559
560    #[derive(Into, From, Copy, Clone, Debug)]
561    pub(in crate::vec_map) struct MyKey(pub(crate) usize);
562
563    #[test]
564    fn test_with_capacity() {
565        let map: VecMap<usize, usize> = VecMap::with_capacity(3);
566
567        assert_eq!(3, map.data.len());
568        assert_eq!(vec![None, None, None], map.data);
569        assert!(map.is_empty());
570    }
571
572    #[test]
573    fn test_new() {
574        let map: VecMap<usize, usize> = VecMap::new();
575        assert!(map.is_empty());
576        assert!(map.data.is_empty());
577    }
578
579    #[test]
580    fn test_insert() {
581        let mut map = VecMap::new();
582
583        // insert in unallocated space
584        assert_eq!(None, map.insert(3usize, "hi"));
585        assert_eq!(vec![None, None, None, Some("hi")], map.data);
586
587        // insert in allocated space
588        assert_eq!(None, map.insert(1, "hello"));
589        assert_eq!(vec![None, Some("hello"), None, Some("hi")], map.data);
590
591        // overwrite existing item
592        assert_eq!(Some("hi"), map.insert(3, "bye"));
593        assert_eq!(vec![None, Some("hello"), None, Some("bye")], map.data);
594    }
595
596    #[test]
597    fn test_remove() {
598        let mut map = vecmap! { 9usize => "nine", 17 => "seventeen", 2 => "two"};
599        assert_eq!(vec![2, 9, 17], map.keys().collect::<Vec<_>>());
600        assert_eq!(3, map.len());
601
602        // removing a non-existent key-value pair has no effect
603        assert_eq!(None, map.remove(10));
604        assert_eq!(3, map.len());
605        assert_eq!(vec![2, 9, 17], map.keys().collect::<Vec<_>>());
606
607        // removing an existing key-value pair correctly updates the map
608        assert_eq!(Some("seventeen"), map.remove(17));
609        assert_eq!(2, map.len());
610        assert_eq!(vec![2, 9], map.keys().collect::<Vec<_>>());
611    }
612
613    #[test]
614    fn test_pop() {
615        let mut map = vecmap! { 9usize => "nine", 17 => "seventeen", 2 => "two"};
616        assert_eq!(18, map.capacity());
617        assert_eq!(3, map.len());
618        assert_eq!(Some((17, "seventeen")), map.pop());
619        assert_eq!(18, map.capacity());
620        assert_eq!(2, map.len());
621        assert_eq!(Some((9, "nine")), map.pop());
622        assert_eq!(18, map.capacity());
623        assert_eq!(1, map.len());
624        assert_eq!(Some((2, "two")), map.pop());
625        assert_eq!(18, map.capacity());
626        assert_eq!(0, map.len());
627        assert_eq!(None, map.pop());
628        assert_eq!(18, map.capacity());
629        assert_eq!(0, map.len());
630    }
631
632    #[test]
633    fn test_retain_by_key() {
634        let mut map = vecmap! { 9usize => "nine".to_string(), 17 => "seventeen".to_string(), 2 => "two".to_string()};
635        map.retain(|k, _| k < 9);
636        assert_eq!(1, map.len());
637        assert_eq!(
638            vec![(2, "two".to_string())],
639            map.into_iter().collect::<Vec<_>>()
640        );
641    }
642
643    #[test]
644    fn test_retain_by_value() {
645        let mut map = vecmap! { 9usize => "nine".to_string(), 17 => "seventeen".to_string(), 2 => "two".to_string()};
646        map.retain(|_, s| s.len() > 8);
647        assert_eq!(1, map.len());
648        assert_eq!(
649            vec![(17, "seventeen".to_string())],
650            map.into_iter().collect::<Vec<_>>()
651        );
652    }
653
654    #[test]
655    fn test_retain_mut_value() {
656        let mut map = vecmap! { 9usize => "nine".to_string(), 17 => "seventeen".to_string(), 2 => "two".to_string()};
657        map.retain(|_, s| {
658            if s.len() < 8 {
659                s.push_str("-yes");
660            }
661            true
662        });
663        assert_eq!(3, map.len());
664        assert_eq!(
665            vec![
666                (2, "two-yes".to_string()),
667                (9, "nine-yes".to_string()),
668                (17, "seventeen".to_string())
669            ],
670            map.into_iter().collect::<Vec<_>>()
671        );
672    }
673
674    #[test]
675    fn test_entry_or_insert() {
676        let mut map = VecMap::new();
677
678        // non existing
679        let return_value = map.entry(MyKey(2)).or_insert("hello");
680        assert_eq!("hello", *return_value);
681        assert_eq!(vecmap! { MyKey(2) => "hello" }, map);
682
683        // already existing
684        let return_value = map.entry(MyKey(2)).or_insert("bye");
685        assert_eq!("hello", *return_value);
686        assert_eq!(vecmap! { MyKey(2) => "hello" }, map);
687
688        // overwrite through reference
689        let result = map.entry(MyKey(2)).or_insert("this is ignored");
690        *result = "bye";
691        assert_eq!(vecmap! { MyKey(2) => "bye" }, map);
692    }
693
694    #[test]
695    fn test_entry_or_insert_with() {
696        let mut map = VecMap::new();
697
698        // non existing
699        let return_value = map.entry(MyKey(2)).or_insert_with(|| "hello");
700        assert_eq!("hello", *return_value);
701        assert_eq!(vecmap! { MyKey(2) => "hello" }, map);
702
703        // already existing
704        let return_value = map.entry(MyKey(2)).or_insert_with(|| "bye");
705        assert_eq!("hello", *return_value);
706        assert_eq!(vecmap! { MyKey(2) => "hello" }, map);
707
708        // overwrite through reference
709        let result = map.entry(MyKey(2)).or_insert_with(|| "this is ignored");
710        *result = "bye";
711        assert_eq!(vecmap! { MyKey(2) => "bye" }, map);
712    }
713
714    #[test]
715    fn test_entry_or_default() {
716        let mut map = VecMap::new();
717
718        // non existing
719        let return_value = map.entry(MyKey(2)).or_default();
720        assert_eq!("", *return_value);
721        assert_eq!(vecmap! { MyKey(2) => "" }, map);
722
723        // already existing
724        map.insert(MyKey(4), "hello");
725        let return_value = map.entry(MyKey(4)).or_default();
726        assert_eq!("hello", *return_value);
727        assert_eq!(vecmap! { MyKey(2) => "", MyKey(4) => "hello" }, map);
728
729        // overwrite through reference
730        let result = map.entry(MyKey(4)).or_default();
731        *result = "bye";
732        assert_eq!(vecmap! {MyKey(2) => "", MyKey(4) => "bye"}, map);
733    }
734
735    #[test]
736    fn test_entry_and_modify() {
737        let mut map: VecMap<usize, usize> = VecMap::new();
738
739        // empty entry, closure should not get called
740        map.entry(2)
741            .and_modify(|_| panic!("should not be called"))
742            .or_default();
743
744        // occupied entry, closure should get called
745        map.entry(2).and_modify(|num| {
746            *num = 10;
747        });
748        assert_eq!(vecmap! {2=> 10}, map);
749    }
750
751    #[test]
752    fn test_get() {
753        let map = vecmap! { MyKey(9) => "nine", MyKey(17) => "seventeen", MyKey(2) => "two"};
754        assert_eq!(Some(&"nine"), map.get(MyKey(9)));
755        assert_eq!(None, map.get(MyKey(10)));
756        assert_eq!(None, map.get(MyKey(10000)));
757    }
758
759    #[test]
760    fn test_get_mut() {
761        let mut map = vecmap! { MyKey(9) => "nine", MyKey(17) => "seventeen", MyKey(2) => "two"};
762        assert_eq!(Some(&mut "nine"), map.get_mut(MyKey(9)));
763        *map.get_mut(MyKey(9)).unwrap() = "negen";
764        assert_eq!(Some(&"negen"), map.get(MyKey(9)));
765
766        assert_eq!(None, map.get_mut(MyKey(10)));
767        assert_eq!(None, map.get_mut(MyKey(10000)));
768    }
769
770    #[test]
771    fn test_len_and_is_empty() {
772        let numbers = [3, 9, 0, 15, 24, 2, 17, 7, 4];
773        let mut map = vecmap! {};
774        assert_eq!(0, map.len());
775        assert!(map.is_empty());
776        for (i, num) in numbers.into_iter().enumerate() {
777            map.insert(MyKey(num), format!("number {num}"));
778            assert_eq!(i + 1, map.len());
779            assert!(!map.is_empty());
780        }
781    }
782
783    #[test]
784    fn test_contains_key() {
785        let map = vecmap! { MyKey(9) => "nine", MyKey(17) => "seventeen", MyKey(2) => "two"};
786
787        assert!(!map.contains_key(MyKey(3)));
788        assert!(!map.contains_key(MyKey(300)));
789
790        assert!(map.contains_key(MyKey(9)));
791        assert!(map.contains_key(MyKey(17)));
792        assert!(map.contains_key(MyKey(2)));
793    }
794
795    #[test]
796    fn test_enum() {
797        #[derive(Copy, Clone, Eq, PartialEq, Debug)]
798        enum TestEnum {
799            A,
800            B,
801        }
802
803        impl IndexKey for TestEnum {
804            fn as_index(&self) -> usize {
805                match self {
806                    Self::A => 0,
807                    Self::B => 1,
808                }
809            }
810
811            fn from_index(index: usize) -> Self {
812                match index {
813                    0 => Self::A,
814                    1 => Self::B,
815                    _ => panic!(),
816                }
817            }
818        }
819        use TestEnum::A;
820        use TestEnum::B;
821        let mut map: VecMap<TestEnum, usize> = VecMap::with_capacity(40);
822        map.insert(B, 20);
823        map.insert(A, 17);
824
825        assert_eq!(vec![(A, &17), (B, &20)], map.iter().collect::<Vec<_>>());
826    }
827
828    #[test]
829    fn test_new_type() {
830        #[derive(Copy, Clone, Eq, PartialEq, Debug)]
831        struct MyNewType(u8);
832
833        impl IndexKey for MyNewType {
834            fn as_index(&self) -> usize {
835                self.0 as usize
836            }
837
838            fn from_index(index: usize) -> Self {
839                Self(u8::try_from(index).unwrap())
840            }
841        }
842        let mut map: VecMap<MyNewType, ()> = VecMap::with_capacity(40);
843        map.insert(MyNewType(39), ());
844        map.insert(MyNewType(20), ());
845        map.insert(MyNewType(10), ());
846
847        assert_eq!(
848            vec![MyNewType(10), MyNewType(20), MyNewType(39)],
849            map.keys().collect::<Vec<_>>()
850        );
851    }
852
853    #[test]
854    fn test_capacity() {
855        let mut map: VecMap<usize, ()> = VecMap::new();
856        assert_eq!(0, map.capacity());
857        assert!(map.is_empty());
858
859        map.insert(0, ());
860        assert_eq!(1, map.len());
861        assert_eq!(1, map.capacity());
862
863        map.insert(100, ());
864        assert_eq!(2, map.len());
865        assert_eq!(101, map.capacity());
866
867        let mut map: VecMap<usize, ()> = VecMap::with_capacity(20);
868        assert_eq!(20, map.capacity());
869        assert!(map.is_empty());
870
871        map.insert(0, ());
872        assert_eq!(1, map.len());
873        assert_eq!(20, map.capacity());
874
875        map.insert(100, ());
876        assert_eq!(2, map.len());
877        assert_eq!(101, map.capacity());
878    }
879
880    #[test]
881    fn test_index_and_index_mut() {
882        let immutable_map =
883            vecmap! { MyKey(8) => "august", MyKey(13) => "thirteen", MyKey(22) => "twentytwo"};
884        assert_eq!("august", immutable_map[MyKey(8)]);
885        assert_eq!("thirteen", immutable_map[MyKey(13)]);
886        assert_eq!("twentytwo", immutable_map[MyKey(22)]);
887
888        let mut map =
889            vecmap! { MyKey(8) => "august", MyKey(13) => "thirteen", MyKey(22) => "twentytwo"};
890        assert_eq!("august", map[MyKey(8)]);
891        assert_eq!("thirteen", map[MyKey(13)]);
892        assert_eq!("twentytwo", map[MyKey(22)]);
893
894        map[MyKey(8)] = "eight";
895        assert_eq!("eight", map[MyKey(8)]);
896    }
897
898    #[test]
899    #[should_panic(expected = "100 is out of bounds")]
900    fn test_index_out_of_bounds_panics() {
901        let immutable_map =
902            vecmap! { MyKey(8) => "august", MyKey(13) => "thirteen", MyKey(22) => "twentytwo"};
903        let _ = immutable_map[MyKey(100)];
904    }
905
906    #[test]
907    #[should_panic(expected = "There is no item at index 1")]
908    fn test_index_non_existing_panics() {
909        let immutable_map =
910            vecmap! { MyKey(8) => "august", MyKey(13) => "thirteen", MyKey(22) => "twentytwo"};
911        let _ = immutable_map[MyKey(1)];
912    }
913
914    #[test]
915    #[should_panic(expected = "100 is out of bounds")]
916    fn test_index_mut_out_of_bounds_panics() {
917        let mut map =
918            vecmap! { MyKey(8) => "august", MyKey(13) => "thirteen", MyKey(22) => "twentytwo"};
919        let _ = &mut map[MyKey(100)];
920    }
921
922    #[test]
923    #[should_panic(expected = "There is no item at index 1")]
924    fn test_index_mut_non_existing_panics() {
925        let mut map =
926            vecmap! { MyKey(8) => "august", MyKey(13) => "thirteen", MyKey(22) => "twentytwo"};
927        let _ = &mut map[MyKey(1)];
928    }
929
930    #[test]
931    fn test_clear() {
932        let mut map =
933            vecmap! { MyKey(8) => "august", MyKey(13) => "thirteen", MyKey(22) => "twentytwo"};
934        assert_eq!(23, map.capacity());
935        assert_eq!(3, map.len());
936        map.clear();
937        assert_eq!(23, map.capacity());
938        assert_eq!(0, map.len());
939    }
940
941    #[test]
942    fn test_reserve() {
943        let mut map: VecMap<MyKey, ()> = vecmap! {};
944        assert_eq!(0, map.capacity());
945        assert!(map.is_empty());
946
947        map.reserve(7);
948        assert_eq!(7, map.capacity());
949        assert!(map.is_empty());
950
951        map.reserve(7);
952        assert_eq!(14, map.capacity());
953        assert!(map.is_empty());
954    }
955
956    #[test]
957    fn test_extend() {
958        let mut map: VecMap<MyKey, ()> = vecmap! {};
959        assert_eq!(0, map.capacity());
960        assert!(map.is_empty());
961
962        map.extend([(MyKey(7), ()), (MyKey(2), ())]);
963        assert_eq!(8, map.capacity());
964        assert_eq!(2, map.len());
965    }
966
967    #[test]
968    fn test_eq_with_different_capacities() {
969        let map1 = VecMap {
970            data: vec![None, Some(1)],
971            len: 1,
972            _marker: PhantomData::<MyKey>,
973        };
974        let map2 = VecMap {
975            data: vec![None, Some(1), None, None],
976            len: 1,
977            _marker: PhantomData::<MyKey>,
978        };
979        assert_eq!(map1, map2);
980    }
981
982    #[cfg(feature = "serde")]
983    mod serde {
984        use super::*;
985
986        #[test]
987        fn test_serde() {
988            let input = vecmap! {MyKey(2)=> "hi", MyKey(4) => "four"};
989
990            let serialized_str = serde_json::to_string(&input).unwrap();
991            assert_eq!("[null,null,\"hi\",null,\"four\"]", serialized_str);
992
993            let deserialized =
994                serde_json::from_str::<VecMap<MyKey, &str>>(&serialized_str).unwrap();
995            assert_eq!(input, deserialized);
996            assert_eq!(2, deserialized.len());
997            assert_eq!(5, deserialized.capacity());
998
999            // trailing null is ignored
1000            let deserialized =
1001                serde_json::from_str::<VecMap<MyKey, &str>>("[\"test\",null]").unwrap();
1002            assert_eq!(vecmap! {MyKey(0)=> "test"}, deserialized);
1003            assert_eq!(1, deserialized.len());
1004            assert_eq!(2, deserialized.capacity());
1005
1006            // empty
1007            let input: VecMap<MyKey, &str> = VecMap::new();
1008            let serialized_str = serde_json::to_string(&input).unwrap();
1009            assert_eq!("[]", serialized_str);
1010
1011            let deserialized =
1012                serde_json::from_str::<VecMap<MyKey, &str>>(&serialized_str).unwrap();
1013            assert!(deserialized.is_empty());
1014            assert_eq!(0, deserialized.capacity());
1015        }
1016    }
1017}
more_collections/vec_map/mod.rs

more_collections/vec_map/
mod.rs
