parry3d/utils/
vec_map.rs

1// Copyright 2012-2024 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11/*
12 * NOTE: this is copied from https://github.com/contain-rs/vec-map/blob/master/src/lib.rs
13 *       (currently under passive maintenance) with the following modifications:
14 *       - Removal of the allocator type parameter.
15 *       - Implement rkyv serialization/deserialization.
16 *       - no-std support.
17 */
18
19#![forbid(unsafe_code)]
20#![deny(missing_docs)]
21#![warn(rust_2018_idioms)]
22#![allow(clippy::type_complexity)]
23
24//! # Description
25//!
26//! A simple map based on a vector for small integer keys. Space requirements
27//! are **O(highest integer key)**.
28
29use self::Entry::*;
30
31use alloc::vec::{self, Vec};
32use core::cmp::{max, Ordering};
33use core::fmt;
34use core::hash::{Hash, Hasher};
35use core::iter::{Enumerate, FilterMap, FromIterator};
36use core::mem::swap;
37use core::ops::{Index, IndexMut};
38use core::slice;
39
40/// A map optimized for small integer keys.
41///
42/// # Examples
43///
44/// ```ignore
45/// use parry::utils::VecMap;
46///
47/// let mut months = VecMap::new();
48/// months.insert(1, "Jan");
49/// months.insert(2, "Feb");
50/// months.insert(3, "Mar");
51///
52/// if !months.contains_key(12) {
53///     println!("The end is near!");
54/// }
55///
56/// assert_eq!(months.get(1), Some(&"Jan"));
57///
58/// if let Some(value) = months.get_mut(3) {
59///     *value = "Venus";
60/// }
61///
62/// assert_eq!(months.get(3), Some(&"Venus"));
63///
64/// // Print out all months
65/// for (key, value) in &months {
66///     println!("month {} is {}", key, value);
67/// }
68///
69/// months.clear();
70/// assert!(months.is_empty());
71/// ```
72#[cfg_attr(
73    feature = "serde-serialize",
74    derive(serde::Serialize, serde::Deserialize),
75    serde(bound(
76        deserialize = "V: serde::Deserialize<'de>",
77        serialize = "V: serde::Serialize"
78    ))
79)]
80#[cfg_attr(
81    feature = "rkyv",
82    derive(rkyv::Archive, rkyv::Deserialize, rkyv::Serialize),
83    archive(check_bytes)
84)]
85pub struct VecMap<V> {
86    n: usize,
87    v: Vec<Option<V>>,
88}
89
90/// A view into a single entry in a map, which may either be vacant or occupied.
91pub enum Entry<'a, V> {
92    /// A vacant `Entry`
93    Vacant(VacantEntry<'a, V>),
94
95    /// An occupied `Entry`
96    Occupied(OccupiedEntry<'a, V>),
97}
98
99/// A vacant `Entry`.
100pub struct VacantEntry<'a, V> {
101    map: &'a mut VecMap<V>,
102    index: usize,
103}
104
105/// An occupied `Entry`.
106pub struct OccupiedEntry<'a, V> {
107    map: &'a mut VecMap<V>,
108    index: usize,
109}
110
111impl<V> Default for VecMap<V> {
112    #[inline]
113    fn default() -> Self {
114        Self::new()
115    }
116}
117
118impl<V: Hash> Hash for VecMap<V> {
119    fn hash<H: Hasher>(&self, state: &mut H) {
120        // In order to not traverse the `VecMap` twice, count the elements
121        // during iteration.
122        let mut count: usize = 0;
123        for elt in self {
124            elt.hash(state);
125            count += 1;
126        }
127        count.hash(state);
128    }
129}
130
131impl<V> VecMap<V> {
132    /// Creates an empty `VecMap`.
133    ///
134    /// # Examples
135    ///
136    /// ```ignore
137    /// use parry::utils::VecMap;
138    /// let mut map: VecMap<&str> = VecMap::new();
139    /// ```
140    pub fn new() -> Self {
141        VecMap {
142            n: 0,
143            v: Vec::new(),
144        }
145    }
146
147    /// Creates an empty `VecMap` with space for at least `capacity`
148    /// elements before resizing.
149    ///
150    /// # Examples
151    ///
152    /// ```ignore
153    /// use parry::utils::VecMap;
154    /// let mut map: VecMap<&str> = VecMap::with_capacity(10);
155    /// ```
156    pub fn with_capacity(capacity: usize) -> Self {
157        VecMap {
158            n: 0,
159            v: Vec::with_capacity(capacity),
160        }
161    }
162}
163
164impl<V> VecMap<V> {
165    /// Returns the number of elements the `VecMap` can hold without
166    /// reallocating.
167    ///
168    /// # Examples
169    ///
170    /// ```ignore
171    /// use parry::utils::VecMap;
172    /// let map: VecMap<String> = VecMap::with_capacity(10);
173    /// assert!(map.capacity() >= 10);
174    /// ```
175    #[inline]
176    pub fn capacity(&self) -> usize {
177        self.v.capacity()
178    }
179
180    /// Reserves capacity for the given `VecMap` to contain `len` distinct keys.
181    /// In the case of `VecMap` this means reallocations will not occur as long
182    /// as all inserted keys are less than `len`.
183    ///
184    /// The collection may reserve more space to avoid frequent reallocations.
185    ///
186    /// # Examples
187    ///
188    /// ```ignore
189    /// use parry::utils::VecMap;
190    /// let mut map: VecMap<&str> = VecMap::new();
191    /// map.reserve_len(10);
192    /// assert!(map.capacity() >= 10);
193    /// ```
194    pub fn reserve_len(&mut self, len: usize) {
195        let cur_len = self.v.len();
196        if len >= cur_len {
197            self.v.reserve(len - cur_len);
198        }
199    }
200
201    /// Reserves the minimum capacity for the given `VecMap` to contain `len` distinct keys.
202    /// In the case of `VecMap` this means reallocations will not occur as long as all inserted
203    /// keys are less than `len`.
204    ///
205    /// Note that the allocator may give the collection more space than it requests.
206    /// Therefore capacity cannot be relied upon to be precisely minimal.  Prefer
207    /// `reserve_len` if future insertions are expected.
208    ///
209    /// # Examples
210    ///
211    /// ```ignore
212    /// use parry::utils::VecMap;
213    /// let mut map: VecMap<&str> = VecMap::new();
214    /// map.reserve_len_exact(10);
215    /// assert!(map.capacity() >= 10);
216    /// ```
217    pub fn reserve_len_exact(&mut self, len: usize) {
218        let cur_len = self.v.len();
219        if len >= cur_len {
220            self.v.reserve_exact(len - cur_len);
221        }
222    }
223
224    /// Trims the `VecMap` of any excess capacity.
225    ///
226    /// The collection may reserve more space to avoid frequent reallocations.
227    ///
228    /// # Examples
229    ///
230    /// ```ignore
231    /// use parry::utils::VecMap;
232    /// let mut map: VecMap<&str> = VecMap::with_capacity(10);
233    /// map.shrink_to_fit();
234    /// assert_eq!(map.capacity(), 0);
235    /// ```
236    pub fn shrink_to_fit(&mut self) {
237        // strip off trailing `None`s
238        if let Some(idx) = self.v.iter().rposition(Option::is_some) {
239            self.v.truncate(idx + 1);
240        } else {
241            self.v.clear();
242        }
243
244        self.v.shrink_to_fit()
245    }
246
247    /// Returns an iterator visiting all keys in ascending order of the keys.
248    /// The iterator's element type is `usize`.
249    pub fn keys(&self) -> Keys<'_, V> {
250        Keys { iter: self.iter() }
251    }
252
253    /// Returns an iterator visiting all values in ascending order of the keys.
254    /// The iterator's element type is `&'r V`.
255    pub fn values(&self) -> Values<'_, V> {
256        Values { iter: self.iter() }
257    }
258
259    /// Returns an iterator visiting all values in ascending order of the keys.
260    /// The iterator's element type is `&'r mut V`.
261    pub fn values_mut(&mut self) -> ValuesMut<'_, V> {
262        ValuesMut {
263            iter_mut: self.iter_mut(),
264        }
265    }
266
267    /// Returns an iterator visiting all key-value pairs in ascending order of the keys.
268    /// The iterator's element type is `(usize, &'r V)`.
269    ///
270    /// # Examples
271    ///
272    /// ```ignore
273    /// use parry::utils::VecMap;
274    ///
275    /// let mut map = VecMap::new();
276    /// map.insert(1, "a");
277    /// map.insert(3, "c");
278    /// map.insert(2, "b");
279    ///
280    /// // Print `1: a` then `2: b` then `3: c`
281    /// for (key, value) in map.iter() {
282    ///     println!("{}: {}", key, value);
283    /// }
284    /// ```
285    pub fn iter(&self) -> Iter<'_, V> {
286        Iter {
287            front: 0,
288            back: self.v.len(),
289            n: self.n,
290            yielded: 0,
291            iter: self.v.iter(),
292        }
293    }
294
295    /// Returns an iterator visiting all key-value pairs in ascending order of the keys,
296    /// with mutable references to the values.
297    /// The iterator's element type is `(usize, &'r mut V)`.
298    ///
299    /// # Examples
300    ///
301    /// ```ignore
302    /// use parry::utils::VecMap;
303    ///
304    /// let mut map = VecMap::new();
305    /// map.insert(1, "a");
306    /// map.insert(2, "b");
307    /// map.insert(3, "c");
308    ///
309    /// for (key, value) in map.iter_mut() {
310    ///     *value = "x";
311    /// }
312    ///
313    /// for (key, value) in &map {
314    ///     assert_eq!(value, &"x");
315    /// }
316    /// ```
317    pub fn iter_mut(&mut self) -> IterMut<'_, V> {
318        IterMut {
319            front: 0,
320            back: self.v.len(),
321            n: self.n,
322            yielded: 0,
323            iter: self.v.iter_mut(),
324        }
325    }
326
327    /// Moves all elements from `other` into the map while overwriting existing keys.
328    ///
329    /// # Examples
330    ///
331    /// ```ignore
332    /// use parry::utils::VecMap;
333    ///
334    /// let mut a = VecMap::new();
335    /// a.insert(1, "a");
336    /// a.insert(2, "b");
337    ///
338    /// let mut b = VecMap::new();
339    /// b.insert(3, "c");
340    /// b.insert(4, "d");
341    ///
342    /// a.append(&mut b);
343    ///
344    /// assert_eq!(a.len(), 4);
345    /// assert_eq!(b.len(), 0);
346    /// assert_eq!(a[1], "a");
347    /// assert_eq!(a[2], "b");
348    /// assert_eq!(a[3], "c");
349    /// assert_eq!(a[4], "d");
350    /// ```
351    pub fn append(&mut self, other: &mut Self) {
352        self.extend(other.drain());
353    }
354
355    /// Splits the collection into two at the given key.
356    ///
357    /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`,
358    /// and the returned `Self` contains elements `[at, max_key)`.
359    ///
360    /// Note that the capacity of `self` does not change.
361    ///
362    /// # Examples
363    ///
364    /// ```ignore
365    /// use parry::utils::VecMap;
366    ///
367    /// let mut a = VecMap::new();
368    /// a.insert(1, "a");
369    /// a.insert(2, "b");
370    /// a.insert(3, "c");
371    /// a.insert(4, "d");
372    ///
373    /// let b = a.split_off(3);
374    ///
375    /// assert_eq!(a[1], "a");
376    /// assert_eq!(a[2], "b");
377    ///
378    /// assert_eq!(b[3], "c");
379    /// assert_eq!(b[4], "d");
380    /// ```
381    pub fn split_off(&mut self, at: usize) -> Self {
382        let mut other = VecMap::new();
383
384        if at == 0 {
385            // Move all elements to other
386            // The swap will also fix .n
387            swap(self, &mut other);
388            return other;
389        } else if at >= self.v.len() {
390            // No elements to copy
391            return other;
392        }
393
394        // Look up the index of the first non-None item
395        let first_index = self.v.iter().position(|el| el.is_some());
396        let start_index = match first_index {
397            Some(index) => max(at, index),
398            None => {
399                // self has no elements
400                return other;
401            }
402        };
403
404        // Fill the new VecMap with `None`s until `start_index`
405        other.v.extend((0..start_index).map(|_| None));
406
407        // Move elements beginning with `start_index` from `self` into `other`
408        let mut taken = 0;
409        other.v.extend(self.v[start_index..].iter_mut().map(|el| {
410            let el = el.take();
411            if el.is_some() {
412                taken += 1;
413            }
414            el
415        }));
416        other.n = taken;
417        self.n -= taken;
418
419        other
420    }
421
422    /// Returns an iterator visiting all key-value pairs in ascending order of
423    /// the keys, emptying (but not consuming) the original `VecMap`.
424    /// The iterator's element type is `(usize, &'r V)`. Keeps the allocated memory for reuse.
425    ///
426    /// # Examples
427    ///
428    /// ```ignore
429    /// use parry::utils::VecMap;
430    ///
431    /// let mut map = VecMap::new();
432    /// map.insert(1, "a");
433    /// map.insert(3, "c");
434    /// map.insert(2, "b");
435    ///
436    /// let vec: Vec<(usize, &str)> = map.drain().collect();
437    ///
438    /// assert_eq!(vec, [(1, "a"), (2, "b"), (3, "c")]);
439    /// ```
440    pub fn drain(&mut self) -> Drain<'_, V> {
441        fn filter<A>((i, v): (usize, Option<A>)) -> Option<(usize, A)> {
442            v.map(|v| (i, v))
443        }
444        let filter: fn((usize, Option<V>)) -> Option<(usize, V)> = filter; // coerce to fn ptr
445
446        self.n = 0;
447        Drain {
448            iter: self.v.drain(..).enumerate().filter_map(filter),
449        }
450    }
451
452    /// Returns the number of elements in the map.
453    ///
454    /// # Examples
455    ///
456    /// ```ignore
457    /// use parry::utils::VecMap;
458    ///
459    /// let mut a = VecMap::new();
460    /// assert_eq!(a.len(), 0);
461    /// a.insert(1, "a");
462    /// assert_eq!(a.len(), 1);
463    /// ```
464    pub fn len(&self) -> usize {
465        self.n
466    }
467
468    /// Returns true if the map contains no elements.
469    ///
470    /// # Examples
471    ///
472    /// ```ignore
473    /// use parry::utils::VecMap;
474    ///
475    /// let mut a = VecMap::new();
476    /// assert!(a.is_empty());
477    /// a.insert(1, "a");
478    /// assert!(!a.is_empty());
479    /// ```
480    pub fn is_empty(&self) -> bool {
481        self.n == 0
482    }
483
484    /// Clears the map, removing all key-value pairs.
485    ///
486    /// # Examples
487    ///
488    /// ```ignore
489    /// use parry::utils::VecMap;
490    ///
491    /// let mut a = VecMap::new();
492    /// a.insert(1, "a");
493    /// a.clear();
494    /// assert!(a.is_empty());
495    /// ```
496    pub fn clear(&mut self) {
497        self.n = 0;
498        self.v.clear()
499    }
500
501    /// Returns a reference to the value corresponding to the key.
502    ///
503    /// # Examples
504    ///
505    /// ```ignore
506    /// use parry::utils::VecMap;
507    ///
508    /// let mut map = VecMap::new();
509    /// map.insert(1, "a");
510    /// assert_eq!(map.get(1), Some(&"a"));
511    /// assert_eq!(map.get(2), None);
512    /// ```
513    pub fn get(&self, key: usize) -> Option<&V> {
514        if key < self.v.len() {
515            self.v[key].as_ref()
516        } else {
517            None
518        }
519    }
520
521    /// Returns true if the map contains a value for the specified key.
522    ///
523    /// # Examples
524    ///
525    /// ```ignore
526    /// use parry::utils::VecMap;
527    ///
528    /// let mut map = VecMap::new();
529    /// map.insert(1, "a");
530    /// assert_eq!(map.contains_key(1), true);
531    /// assert_eq!(map.contains_key(2), false);
532    /// ```
533    #[inline]
534    pub fn contains_key(&self, key: usize) -> bool {
535        self.get(key).is_some()
536    }
537
538    /// Returns a mutable reference to the value corresponding to the key.
539    ///
540    /// # Examples
541    ///
542    /// ```ignore
543    /// use parry::utils::VecMap;
544    ///
545    /// let mut map = VecMap::new();
546    /// map.insert(1, "a");
547    /// if let Some(x) = map.get_mut(1) {
548    ///     *x = "b";
549    /// }
550    /// assert_eq!(map[1], "b");
551    /// ```
552    pub fn get_mut(&mut self, key: usize) -> Option<&mut V> {
553        if key < self.v.len() {
554            self.v[key].as_mut()
555        } else {
556            None
557        }
558    }
559
560    /// Inserts a key-value pair into the map. If the key already had a value
561    /// present in the map, that value is returned. Otherwise, `None` is returned.
562    ///
563    /// *WARNING*: You should only use trusted values as keys in VecMap. Otherwise, a
564    /// denial-of-service vulnerability may occur that deplets memory with a large key value.
565    ///
566    /// # Examples
567    ///
568    /// ```ignore
569    /// use parry::utils::VecMap;
570    ///
571    /// let mut map = VecMap::new();
572    /// assert_eq!(map.insert(37, "a"), None);
573    /// assert_eq!(map.is_empty(), false);
574    ///
575    /// map.insert(37, "b");
576    /// assert_eq!(map.insert(37, "c"), Some("b"));
577    /// assert_eq!(map[37], "c");
578    /// ```
579    pub fn insert(&mut self, key: usize, value: V) -> Option<V> {
580        let len = self.v.len();
581        if len <= key {
582            self.v.extend((0..key - len + 1).map(|_| None));
583        }
584        let was = self.v[key].replace(value);
585        if was.is_none() {
586            self.n += 1;
587        }
588        was
589    }
590
591    /// Removes a key from the map, returning the value at the key if the key
592    /// was previously in the map.
593    ///
594    /// # Examples
595    ///
596    /// ```ignore
597    /// use parry::utils::VecMap;
598    ///
599    /// let mut map = VecMap::new();
600    /// map.insert(1, "a");
601    /// assert_eq!(map.remove(1), Some("a"));
602    /// assert_eq!(map.remove(1), None);
603    /// ```
604    pub fn remove(&mut self, key: usize) -> Option<V> {
605        if key >= self.v.len() {
606            return None;
607        }
608        let result = &mut self.v[key];
609        let was = result.take();
610        if was.is_some() {
611            self.n -= 1;
612        }
613        was
614    }
615
616    /// Gets the given key's corresponding entry in the map for in-place manipulation.
617    ///
618    /// # Examples
619    ///
620    /// ```ignore
621    /// use parry::utils::VecMap;
622    ///
623    /// let mut count: VecMap<u32> = VecMap::new();
624    ///
625    /// // count the number of occurrences of numbers in the vec
626    /// for x in vec![1, 2, 1, 2, 3, 4, 1, 2, 4] {
627    ///     *count.entry(x).or_insert(0) += 1;
628    /// }
629    ///
630    /// assert_eq!(count[1], 3);
631    /// ```
632    pub fn entry(&mut self, key: usize) -> Entry<'_, V> {
633        // FIXME(Gankro): this is basically the dumbest implementation of
634        // entry possible, because weird non-lexical borrows issues make it
635        // completely insane to do any other way. That said, Entry is a border-line
636        // useless construct on VecMap, so it's hardly a big loss.
637        if self.contains_key(key) {
638            Occupied(OccupiedEntry {
639                map: self,
640                index: key,
641            })
642        } else {
643            Vacant(VacantEntry {
644                map: self,
645                index: key,
646            })
647        }
648    }
649
650    /// Retains only the elements specified by the predicate.
651    ///
652    /// In other words, remove all pairs `(k, v)` such that `f(&k, &mut v)` returns `false`.
653    ///
654    /// # Examples
655    ///
656    /// ```ignore
657    /// use parry::utils::VecMap;
658    ///
659    /// let mut map: VecMap<usize> = (0..8).map(|x|(x, x*10)).collect();
660    /// map.retain(|k, _| k % 2 == 0);
661    /// assert_eq!(map.len(), 4);
662    /// ```
663    pub fn retain<F>(&mut self, mut f: F)
664    where
665        F: FnMut(usize, &mut V) -> bool,
666    {
667        for (i, e) in self.v.iter_mut().enumerate() {
668            let remove = match *e {
669                Some(ref mut value) => !f(i, value),
670                None => false,
671            };
672            if remove {
673                *e = None;
674                self.n -= 1;
675            }
676        }
677    }
678}
679
680impl<'a, V> Entry<'a, V> {
681    /// Ensures a value is in the entry by inserting the default if empty, and
682    /// returns a mutable reference to the value in the entry.
683    pub fn or_insert(self, default: V) -> &'a mut V {
684        match self {
685            Occupied(entry) => entry.into_mut(),
686            Vacant(entry) => entry.insert(default),
687        }
688    }
689
690    /// Ensures a value is in the entry by inserting the result of the default
691    /// function if empty, and returns a mutable reference to the value in the
692    /// entry.
693    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
694        match self {
695            Occupied(entry) => entry.into_mut(),
696            Vacant(entry) => entry.insert(default()),
697        }
698    }
699}
700
701impl<'a, V> VacantEntry<'a, V> {
702    /// Sets the value of the entry with the `VacantEntry`'s key,
703    /// and returns a mutable reference to it.
704    pub fn insert(self, value: V) -> &'a mut V {
705        let index = self.index;
706        let _ = self.map.insert(index, value);
707        &mut self.map[index]
708    }
709}
710
711impl<'a, V> OccupiedEntry<'a, V> {
712    /// Gets a reference to the value in the entry.
713    pub fn get(&self) -> &V {
714        let index = self.index;
715        &self.map[index]
716    }
717
718    /// Gets a mutable reference to the value in the entry.
719    pub fn get_mut(&mut self) -> &mut V {
720        let index = self.index;
721        &mut self.map[index]
722    }
723
724    /// Converts the entry into a mutable reference to its value.
725    pub fn into_mut(self) -> &'a mut V {
726        let index = self.index;
727        &mut self.map[index]
728    }
729
730    /// Sets the value of the entry with the `OccupiedEntry`'s key,
731    /// and returns the entry's old value.
732    pub fn insert(&mut self, value: V) -> V {
733        let index = self.index;
734        self.map.insert(index, value).unwrap()
735    }
736
737    /// Takes the value of the entry out of the map, and returns it.
738    pub fn remove(self) -> V {
739        let index = self.index;
740        self.map.remove(index).unwrap()
741    }
742}
743
744impl<V: Clone> Clone for VecMap<V> {
745    #[inline]
746    fn clone(&self) -> Self {
747        VecMap {
748            n: self.n,
749            v: self.v.clone(),
750        }
751    }
752
753    #[inline]
754    fn clone_from(&mut self, source: &Self) {
755        self.v.clone_from(&source.v);
756        self.n = source.n;
757    }
758}
759
760impl<V, W> PartialEq<VecMap<W>> for VecMap<V>
761where
762    V: PartialEq<W>,
763{
764    fn eq(&self, other: &VecMap<W>) -> bool {
765        self.n == other.n
766            && self
767                .iter()
768                .zip(other.iter())
769                .all(|((i, x), (j, y))| i == j && x == y)
770    }
771}
772
773impl<V: Eq> Eq for VecMap<V> {}
774
775impl<V> PartialOrd<VecMap<V>> for VecMap<V>
776where
777    V: PartialOrd,
778{
779    #[inline]
780    fn partial_cmp(&self, other: &VecMap<V>) -> Option<Ordering> {
781        self.iter().partial_cmp(other.iter())
782    }
783}
784
785impl<V: Ord> Ord for VecMap<V> {
786    #[inline]
787    fn cmp(&self, other: &Self) -> Ordering {
788        self.iter().cmp(other.iter())
789    }
790}
791
792impl<V: fmt::Debug> fmt::Debug for VecMap<V> {
793    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
794        f.debug_map().entries(self).finish()
795    }
796}
797
798impl<V> FromIterator<(usize, V)> for VecMap<V> {
799    fn from_iter<I: IntoIterator<Item = (usize, V)>>(iter: I) -> Self {
800        let mut map = Self::new();
801        map.extend(iter);
802        map
803    }
804}
805
806impl<T> IntoIterator for VecMap<T> {
807    type Item = (usize, T);
808    type IntoIter = IntoIter<T>;
809
810    /// Returns an iterator visiting all key-value pairs in ascending order of
811    /// the keys, consuming the original `VecMap`.
812    /// The iterator's element type is `(usize, &'r V)`.
813    ///
814    /// # Examples
815    ///
816    /// ```ignore
817    /// use parry::utils::VecMap;
818    ///
819    /// let mut map = VecMap::new();
820    /// map.insert(1, "a");
821    /// map.insert(3, "c");
822    /// map.insert(2, "b");
823    ///
824    /// let vec: Vec<(usize, &str)> = map.into_iter().collect();
825    ///
826    /// assert_eq!(vec, [(1, "a"), (2, "b"), (3, "c")]);
827    /// ```
828    fn into_iter(self) -> IntoIter<T> {
829        IntoIter {
830            n: self.n,
831            yielded: 0,
832            iter: self.v.into_iter().enumerate(),
833        }
834    }
835}
836
837impl<'a, T> IntoIterator for &'a VecMap<T> {
838    type Item = (usize, &'a T);
839    type IntoIter = Iter<'a, T>;
840
841    fn into_iter(self) -> Iter<'a, T> {
842        self.iter()
843    }
844}
845
846impl<'a, T> IntoIterator for &'a mut VecMap<T> {
847    type Item = (usize, &'a mut T);
848    type IntoIter = IterMut<'a, T>;
849
850    fn into_iter(self) -> IterMut<'a, T> {
851        self.iter_mut()
852    }
853}
854
855impl<V> Extend<(usize, V)> for VecMap<V> {
856    fn extend<I: IntoIterator<Item = (usize, V)>>(&mut self, iter: I) {
857        for (k, v) in iter {
858            let _ = self.insert(k, v);
859        }
860    }
861}
862
863impl<'a, V: Copy> Extend<(usize, &'a V)> for VecMap<V> {
864    fn extend<I: IntoIterator<Item = (usize, &'a V)>>(&mut self, iter: I) {
865        self.extend(iter.into_iter().map(|(key, &value)| (key, value)));
866    }
867}
868
869impl<V> Index<usize> for VecMap<V> {
870    type Output = V;
871
872    #[inline]
873    fn index(&self, i: usize) -> &V {
874        self.get(i).expect("key not present")
875    }
876}
877
878impl<V> Index<&usize> for VecMap<V> {
879    type Output = V;
880
881    #[inline]
882    fn index(&self, i: &usize) -> &V {
883        self.get(*i).expect("key not present")
884    }
885}
886
887impl<V> IndexMut<usize> for VecMap<V> {
888    #[inline]
889    fn index_mut(&mut self, i: usize) -> &mut V {
890        self.get_mut(i).expect("key not present")
891    }
892}
893
894impl<V> IndexMut<&usize> for VecMap<V> {
895    #[inline]
896    fn index_mut(&mut self, i: &usize) -> &mut V {
897        self.get_mut(*i).expect("key not present")
898    }
899}
900
901macro_rules! iterator {
902    (impl $name:ident -> $elem:ty, $($getter:ident),+) => {
903        impl<'a, V> Iterator for $name<'a, V> {
904            type Item = $elem;
905
906            #[inline]
907            fn next(&mut self) -> Option<$elem> {
908                while self.front < self.back {
909                    if let Some(elem) = self.iter.next() {
910                        if let Some(x) = elem$(. $getter ())+ {
911                            let index = self.front;
912                            self.front += 1;
913                            self.yielded += 1;
914                            return Some((index, x));
915                        }
916                    }
917                    self.front += 1;
918                }
919                None
920            }
921
922            #[inline]
923            fn size_hint(&self) -> (usize, Option<usize>) {
924                (self.n - self.yielded, Some(self.n - self.yielded))
925            }
926        }
927    }
928}
929
930macro_rules! double_ended_iterator {
931    (impl $name:ident -> $elem:ty, $($getter:ident),+) => {
932        impl<'a, V> DoubleEndedIterator for $name<'a, V> {
933            #[inline]
934            fn next_back(&mut self) -> Option<$elem> {
935                while self.front < self.back {
936                    if let Some(elem) = self.iter.next_back() {
937                        if let Some(x) = elem$(. $getter ())+ {
938                            self.back -= 1;
939                            return Some((self.back, x));
940                        }
941                    }
942                    self.back -= 1;
943                }
944                None
945            }
946        }
947    }
948}
949
950/// An iterator over the key-value pairs of a map.
951#[derive(Clone)]
952pub struct Iter<'a, V> {
953    front: usize,
954    back: usize,
955    n: usize,
956    yielded: usize,
957    iter: slice::Iter<'a, Option<V>>,
958}
959
960iterator! { impl Iter -> (usize, &'a V), as_ref }
961impl<'a, V> ExactSizeIterator for Iter<'a, V> {}
962double_ended_iterator! { impl Iter -> (usize, &'a V), as_ref }
963
964/// An iterator over the key-value pairs of a map, with the
965/// values being mutable.
966pub struct IterMut<'a, V> {
967    front: usize,
968    back: usize,
969    n: usize,
970    yielded: usize,
971    iter: slice::IterMut<'a, Option<V>>,
972}
973
974iterator! { impl IterMut -> (usize, &'a mut V), as_mut }
975impl<'a, V> ExactSizeIterator for IterMut<'a, V> {}
976double_ended_iterator! { impl IterMut -> (usize, &'a mut V), as_mut }
977
978/// An iterator over the keys of a map.
979#[derive(Clone)]
980pub struct Keys<'a, V> {
981    iter: Iter<'a, V>,
982}
983
984/// An iterator over the values of a map.
985#[derive(Clone)]
986pub struct Values<'a, V> {
987    iter: Iter<'a, V>,
988}
989
990/// An iterator over the values of a map.
991pub struct ValuesMut<'a, V> {
992    iter_mut: IterMut<'a, V>,
993}
994
995/// A consuming iterator over the key-value pairs of a map.
996pub struct IntoIter<V> {
997    n: usize,
998    yielded: usize,
999    iter: Enumerate<vec::IntoIter<Option<V>>>,
1000}
1001
1002/// A draining iterator over the key-value pairs of a map.
1003pub struct Drain<'a, V> {
1004    iter: FilterMap<
1005        Enumerate<vec::Drain<'a, Option<V>>>,
1006        fn((usize, Option<V>)) -> Option<(usize, V)>,
1007    >,
1008}
1009
1010impl<'a, V> Iterator for Drain<'a, V> {
1011    type Item = (usize, V);
1012
1013    fn next(&mut self) -> Option<(usize, V)> {
1014        self.iter.next()
1015    }
1016    fn size_hint(&self) -> (usize, Option<usize>) {
1017        self.iter.size_hint()
1018    }
1019}
1020
1021impl<'a, V> ExactSizeIterator for Drain<'a, V> {}
1022
1023impl<'a, V> DoubleEndedIterator for Drain<'a, V> {
1024    fn next_back(&mut self) -> Option<(usize, V)> {
1025        self.iter.next_back()
1026    }
1027}
1028
1029impl<'a, V> Iterator for Keys<'a, V> {
1030    type Item = usize;
1031
1032    fn next(&mut self) -> Option<usize> {
1033        self.iter.next().map(|e| e.0)
1034    }
1035    fn size_hint(&self) -> (usize, Option<usize>) {
1036        self.iter.size_hint()
1037    }
1038}
1039
1040impl<'a, V> ExactSizeIterator for Keys<'a, V> {}
1041
1042impl<'a, V> DoubleEndedIterator for Keys<'a, V> {
1043    fn next_back(&mut self) -> Option<usize> {
1044        self.iter.next_back().map(|e| e.0)
1045    }
1046}
1047
1048impl<'a, V> Iterator for Values<'a, V> {
1049    type Item = &'a V;
1050
1051    fn next(&mut self) -> Option<&'a V> {
1052        self.iter.next().map(|e| e.1)
1053    }
1054    fn size_hint(&self) -> (usize, Option<usize>) {
1055        self.iter.size_hint()
1056    }
1057}
1058
1059impl<'a, V> ExactSizeIterator for Values<'a, V> {}
1060
1061impl<'a, V> DoubleEndedIterator for Values<'a, V> {
1062    fn next_back(&mut self) -> Option<&'a V> {
1063        self.iter.next_back().map(|e| e.1)
1064    }
1065}
1066
1067impl<'a, V> Iterator for ValuesMut<'a, V> {
1068    type Item = &'a mut V;
1069
1070    fn next(&mut self) -> Option<&'a mut V> {
1071        self.iter_mut.next().map(|e| e.1)
1072    }
1073    fn size_hint(&self) -> (usize, Option<usize>) {
1074        self.iter_mut.size_hint()
1075    }
1076}
1077
1078impl<'a, V> ExactSizeIterator for ValuesMut<'a, V> {}
1079
1080impl<'a, V> DoubleEndedIterator for ValuesMut<'a, V> {
1081    fn next_back(&mut self) -> Option<&'a mut V> {
1082        self.iter_mut.next_back().map(|e| e.1)
1083    }
1084}
1085
1086impl<V> Iterator for IntoIter<V> {
1087    type Item = (usize, V);
1088
1089    fn next(&mut self) -> Option<(usize, V)> {
1090        loop {
1091            match self.iter.next() {
1092                None => return None,
1093                Some((i, Some(value))) => {
1094                    self.yielded += 1;
1095                    return Some((i, value));
1096                }
1097                _ => {}
1098            }
1099        }
1100    }
1101
1102    fn size_hint(&self) -> (usize, Option<usize>) {
1103        (self.n - self.yielded, Some(self.n - self.yielded))
1104    }
1105}
1106
1107impl<V> ExactSizeIterator for IntoIter<V> {}
1108
1109impl<V> DoubleEndedIterator for IntoIter<V> {
1110    fn next_back(&mut self) -> Option<(usize, V)> {
1111        loop {
1112            match self.iter.next_back() {
1113                None => return None,
1114                Some((i, Some(value))) => return Some((i, value)),
1115                _ => {}
1116            }
1117        }
1118    }
1119}
1120
1121#[allow(dead_code)]
1122fn assert_properties() {
1123    fn vec_map_covariant<'a, T>(map: VecMap<&'static T>) -> VecMap<&'a T> {
1124        map
1125    }
1126
1127    fn into_iter_covariant<'a, T>(iter: IntoIter<&'static T>) -> IntoIter<&'a T> {
1128        iter
1129    }
1130
1131    fn iter_covariant<'i, 'a, T>(iter: Iter<'i, &'static T>) -> Iter<'i, &'a T> {
1132        iter
1133    }
1134
1135    fn keys_covariant<'i, 'a, T>(iter: Keys<'i, &'static T>) -> Keys<'i, &'a T> {
1136        iter
1137    }
1138
1139    fn values_covariant<'i, 'a, T>(iter: Values<'i, &'static T>) -> Values<'i, &'a T> {
1140        iter
1141    }
1142}
1143
1144#[cfg(test)]
1145mod test {
1146    use super::Entry::{Occupied, Vacant};
1147    use super::VecMap;
1148    use std::boxed::Box;
1149    use std::collections::hash_map::DefaultHasher;
1150    use std::hash::{Hash, Hasher};
1151    use std::vec::Vec;
1152
1153    #[test]
1154    fn test_get_mut() {
1155        let mut m = VecMap::new();
1156        assert!(m.insert(1, 12).is_none());
1157        assert!(m.insert(2, 8).is_none());
1158        assert!(m.insert(5, 14).is_none());
1159        let new = 100;
1160        match m.get_mut(5) {
1161            None => panic!(),
1162            Some(x) => *x = new,
1163        }
1164        assert_eq!(m.get(5), Some(&new));
1165    }
1166
1167    #[test]
1168    fn test_len() {
1169        let mut map = VecMap::new();
1170        assert_eq!(map.len(), 0);
1171        assert!(map.is_empty());
1172        assert!(map.insert(5, 20).is_none());
1173        assert_eq!(map.len(), 1);
1174        assert!(!map.is_empty());
1175        assert!(map.insert(11, 12).is_none());
1176        assert_eq!(map.len(), 2);
1177        assert!(!map.is_empty());
1178        assert!(map.insert(14, 22).is_none());
1179        assert_eq!(map.len(), 3);
1180        assert!(!map.is_empty());
1181    }
1182
1183    #[test]
1184    fn test_clear() {
1185        let mut map = VecMap::new();
1186        assert!(map.insert(5, 20).is_none());
1187        assert!(map.insert(11, 12).is_none());
1188        assert!(map.insert(14, 22).is_none());
1189        map.clear();
1190        assert!(map.is_empty());
1191        assert!(map.get(5).is_none());
1192        assert!(map.get(11).is_none());
1193        assert!(map.get(14).is_none());
1194    }
1195
1196    #[test]
1197    fn test_insert() {
1198        let mut m = VecMap::new();
1199        assert_eq!(m.insert(1, 2), None);
1200        assert_eq!(m.insert(1, 3), Some(2));
1201        assert_eq!(m.insert(1, 4), Some(3));
1202    }
1203
1204    #[test]
1205    fn test_remove() {
1206        let mut m = VecMap::new();
1207        let _ = m.insert(1, 2);
1208        assert_eq!(m.remove(1), Some(2));
1209        assert_eq!(m.remove(1), None);
1210    }
1211
1212    #[test]
1213    fn test_keys() {
1214        let mut map = VecMap::new();
1215        let _ = map.insert(1, 'a');
1216        let _ = map.insert(2, 'b');
1217        let _ = map.insert(3, 'c');
1218        let keys: Vec<_> = map.keys().collect();
1219        assert_eq!(keys.len(), 3);
1220        assert!(keys.contains(&1));
1221        assert!(keys.contains(&2));
1222        assert!(keys.contains(&3));
1223    }
1224
1225    #[test]
1226    fn test_values() {
1227        let mut map = VecMap::new();
1228        let _ = map.insert(1, 'a');
1229        let _ = map.insert(2, 'b');
1230        let _ = map.insert(3, 'c');
1231        let values: Vec<_> = map.values().cloned().collect();
1232        assert_eq!(values.len(), 3);
1233        assert!(values.contains(&'a'));
1234        assert!(values.contains(&'b'));
1235        assert!(values.contains(&'c'));
1236    }
1237
1238    #[test]
1239    fn test_iterator() {
1240        let mut m = VecMap::new();
1241
1242        assert!(m.insert(0, 1).is_none());
1243        assert!(m.insert(1, 2).is_none());
1244        assert!(m.insert(3, 5).is_none());
1245        assert!(m.insert(6, 10).is_none());
1246        assert!(m.insert(10, 11).is_none());
1247
1248        let mut it = m.iter();
1249        assert_eq!(it.size_hint(), (5, Some(5)));
1250        assert_eq!(it.next().unwrap(), (0, &1));
1251        assert_eq!(it.size_hint(), (4, Some(4)));
1252        assert_eq!(it.next().unwrap(), (1, &2));
1253        assert_eq!(it.size_hint(), (3, Some(3)));
1254        assert_eq!(it.next().unwrap(), (3, &5));
1255        assert_eq!(it.size_hint(), (2, Some(2)));
1256        assert_eq!(it.next().unwrap(), (6, &10));
1257        assert_eq!(it.size_hint(), (1, Some(1)));
1258        assert_eq!(it.next().unwrap(), (10, &11));
1259        assert_eq!(it.size_hint(), (0, Some(0)));
1260        assert!(it.next().is_none());
1261    }
1262
1263    #[test]
1264    fn test_iterator_size_hints() {
1265        let mut m = VecMap::new();
1266
1267        assert!(m.insert(0, 1).is_none());
1268        assert!(m.insert(1, 2).is_none());
1269        assert!(m.insert(3, 5).is_none());
1270        assert!(m.insert(6, 10).is_none());
1271        assert!(m.insert(10, 11).is_none());
1272
1273        assert_eq!(m.iter().size_hint(), (5, Some(5)));
1274        assert_eq!(m.iter().rev().size_hint(), (5, Some(5)));
1275        assert_eq!(m.iter_mut().size_hint(), (5, Some(5)));
1276        assert_eq!(m.iter_mut().rev().size_hint(), (5, Some(5)));
1277    }
1278
1279    #[test]
1280    fn test_mut_iterator() {
1281        let mut m = VecMap::new();
1282
1283        assert!(m.insert(0, 1).is_none());
1284        assert!(m.insert(1, 2).is_none());
1285        assert!(m.insert(3, 5).is_none());
1286        assert!(m.insert(6, 10).is_none());
1287        assert!(m.insert(10, 11).is_none());
1288
1289        for (k, v) in &mut m {
1290            *v += k as isize;
1291        }
1292
1293        let mut it = m.iter();
1294        assert_eq!(it.next().unwrap(), (0, &1));
1295        assert_eq!(it.next().unwrap(), (1, &3));
1296        assert_eq!(it.next().unwrap(), (3, &8));
1297        assert_eq!(it.next().unwrap(), (6, &16));
1298        assert_eq!(it.next().unwrap(), (10, &21));
1299        assert!(it.next().is_none());
1300    }
1301
1302    #[test]
1303    fn test_rev_iterator() {
1304        let mut m = VecMap::new();
1305
1306        assert!(m.insert(0, 1).is_none());
1307        assert!(m.insert(1, 2).is_none());
1308        assert!(m.insert(3, 5).is_none());
1309        assert!(m.insert(6, 10).is_none());
1310        assert!(m.insert(10, 11).is_none());
1311
1312        let mut it = m.iter().rev();
1313        assert_eq!(it.next().unwrap(), (10, &11));
1314        assert_eq!(it.next().unwrap(), (6, &10));
1315        assert_eq!(it.next().unwrap(), (3, &5));
1316        assert_eq!(it.next().unwrap(), (1, &2));
1317        assert_eq!(it.next().unwrap(), (0, &1));
1318        assert!(it.next().is_none());
1319    }
1320
1321    #[test]
1322    fn test_mut_rev_iterator() {
1323        let mut m = VecMap::new();
1324
1325        assert!(m.insert(0, 1).is_none());
1326        assert!(m.insert(1, 2).is_none());
1327        assert!(m.insert(3, 5).is_none());
1328        assert!(m.insert(6, 10).is_none());
1329        assert!(m.insert(10, 11).is_none());
1330
1331        for (k, v) in m.iter_mut().rev() {
1332            *v += k as isize;
1333        }
1334
1335        let mut it = m.iter();
1336        assert_eq!(it.next().unwrap(), (0, &1));
1337        assert_eq!(it.next().unwrap(), (1, &3));
1338        assert_eq!(it.next().unwrap(), (3, &8));
1339        assert_eq!(it.next().unwrap(), (6, &16));
1340        assert_eq!(it.next().unwrap(), (10, &21));
1341        assert!(it.next().is_none());
1342    }
1343
1344    #[test]
1345    fn test_move_iter() {
1346        let mut m: VecMap<Box<_>> = VecMap::new();
1347        let _ = m.insert(1, Box::new(2));
1348        let mut called = false;
1349        for (k, v) in m {
1350            assert!(!called);
1351            called = true;
1352            assert_eq!(k, 1);
1353            assert_eq!(v, Box::new(2));
1354        }
1355        assert!(called);
1356    }
1357
1358    #[test]
1359    fn test_drain_iterator() {
1360        let mut map = VecMap::new();
1361        let _ = map.insert(1, "a");
1362        let _ = map.insert(3, "c");
1363        let _ = map.insert(2, "b");
1364
1365        let vec: Vec<_> = map.drain().collect();
1366
1367        assert_eq!(vec, [(1, "a"), (2, "b"), (3, "c")]);
1368        assert_eq!(map.len(), 0);
1369    }
1370
1371    #[test]
1372    fn test_append() {
1373        let mut a = VecMap::new();
1374        let _ = a.insert(1, "a");
1375        let _ = a.insert(2, "b");
1376        let _ = a.insert(3, "c");
1377
1378        let mut b = VecMap::new();
1379        let _ = b.insert(3, "d"); // Overwrite element from a
1380        let _ = b.insert(4, "e");
1381        let _ = b.insert(5, "f");
1382
1383        a.append(&mut b);
1384
1385        assert_eq!(a.len(), 5);
1386        assert_eq!(b.len(), 0);
1387        // Capacity shouldn't change for possible reuse
1388        assert!(b.capacity() >= 4);
1389
1390        assert_eq!(a[1], "a");
1391        assert_eq!(a[2], "b");
1392        assert_eq!(a[3], "d");
1393        assert_eq!(a[4], "e");
1394        assert_eq!(a[5], "f");
1395    }
1396
1397    #[test]
1398    fn test_split_off() {
1399        // Split within the key range
1400        let mut a = VecMap::new();
1401        let _ = a.insert(1, "a");
1402        let _ = a.insert(2, "b");
1403        let _ = a.insert(3, "c");
1404        let _ = a.insert(4, "d");
1405
1406        let b = a.split_off(3);
1407
1408        assert_eq!(a.len(), 2);
1409        assert_eq!(b.len(), 2);
1410
1411        assert_eq!(a[1], "a");
1412        assert_eq!(a[2], "b");
1413
1414        assert_eq!(b[3], "c");
1415        assert_eq!(b[4], "d");
1416
1417        // Split at 0
1418        a.clear();
1419        let _ = a.insert(1, "a");
1420        let _ = a.insert(2, "b");
1421        let _ = a.insert(3, "c");
1422        let _ = a.insert(4, "d");
1423
1424        let b = a.split_off(0);
1425
1426        assert_eq!(a.len(), 0);
1427        assert_eq!(b.len(), 4);
1428        assert_eq!(b[1], "a");
1429        assert_eq!(b[2], "b");
1430        assert_eq!(b[3], "c");
1431        assert_eq!(b[4], "d");
1432
1433        // Split behind max_key
1434        a.clear();
1435        let _ = a.insert(1, "a");
1436        let _ = a.insert(2, "b");
1437        let _ = a.insert(3, "c");
1438        let _ = a.insert(4, "d");
1439
1440        let b = a.split_off(5);
1441
1442        assert_eq!(a.len(), 4);
1443        assert_eq!(b.len(), 0);
1444        assert_eq!(a[1], "a");
1445        assert_eq!(a[2], "b");
1446        assert_eq!(a[3], "c");
1447        assert_eq!(a[4], "d");
1448    }
1449
1450    #[test]
1451    fn test_show() {
1452        let mut map = VecMap::new();
1453        let empty = VecMap::<i32>::new();
1454
1455        let _ = map.insert(1, 2);
1456        let _ = map.insert(3, 4);
1457
1458        let map_str = format!("{:?}", map);
1459        assert!(map_str == "{1: 2, 3: 4}" || map_str == "{3: 4, 1: 2}");
1460        assert_eq!(format!("{:?}", empty), "{}");
1461    }
1462
1463    #[test]
1464    fn test_clone() {
1465        let mut a = VecMap::new();
1466
1467        let _ = a.insert(1, 'x');
1468        let _ = a.insert(4, 'y');
1469        let _ = a.insert(6, 'z');
1470
1471        assert_eq!(
1472            a.clone().iter().collect::<Vec<_>>(),
1473            [(1, &'x'), (4, &'y'), (6, &'z')]
1474        );
1475    }
1476
1477    #[test]
1478    fn test_eq() {
1479        let mut a = VecMap::new();
1480        let mut b = VecMap::new();
1481
1482        assert!(a == b);
1483        assert!(a.insert(0, 5).is_none());
1484        assert!(a != b);
1485        assert!(b.insert(0, 4).is_none());
1486        assert!(a != b);
1487        assert!(a.insert(5, 19).is_none());
1488        assert!(a != b);
1489        assert!(b.insert(0, 5).is_some());
1490        assert!(a != b);
1491        assert!(b.insert(5, 19).is_none());
1492        assert!(a == b);
1493
1494        a = VecMap::new();
1495        b = VecMap::with_capacity(1);
1496        assert!(a == b);
1497    }
1498
1499    #[test]
1500    fn test_lt() {
1501        let mut a = VecMap::new();
1502        let mut b = VecMap::new();
1503
1504        assert!(a >= b && b >= a);
1505        assert!(b.insert(2, 5).is_none());
1506        assert!(a < b);
1507        assert!(a.insert(2, 7).is_none());
1508        assert!(a >= b && b < a);
1509        assert!(b.insert(1, 0).is_none());
1510        assert!(b < a);
1511        assert!(a.insert(0, 6).is_none());
1512        assert!(a < b);
1513        assert!(a.insert(6, 2).is_none());
1514        assert!(a < b && b >= a);
1515    }
1516
1517    #[test]
1518    fn test_ord() {
1519        let mut a = VecMap::new();
1520        let mut b = VecMap::new();
1521
1522        assert!(a == b);
1523        assert!(a.insert(1, 1).is_none());
1524        assert!(a > b && a >= b);
1525        assert!(b < a && b <= a);
1526        assert!(b.insert(2, 2).is_none());
1527        assert!(b > a && b >= a);
1528        assert!(a < b && a <= b);
1529    }
1530
1531    #[test]
1532    fn test_hash() {
1533        fn hash<T: Hash>(t: &T) -> u64 {
1534            let mut s = DefaultHasher::new();
1535            t.hash(&mut s);
1536            s.finish()
1537        }
1538
1539        let mut x = VecMap::new();
1540        let mut y = VecMap::new();
1541
1542        assert!(hash(&x) == hash(&y));
1543        let _ = x.insert(1, 'a');
1544        let _ = x.insert(2, 'b');
1545        let _ = x.insert(3, 'c');
1546
1547        let _ = y.insert(3, 'c');
1548        let _ = y.insert(2, 'b');
1549        let _ = y.insert(1, 'a');
1550
1551        assert!(hash(&x) == hash(&y));
1552
1553        let _ = x.insert(1000, 'd');
1554        let _ = x.remove(1000);
1555
1556        assert!(hash(&x) == hash(&y));
1557    }
1558
1559    #[test]
1560    fn test_from_iter() {
1561        let xs = [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e')];
1562
1563        let map: VecMap<_> = xs.iter().cloned().collect();
1564
1565        for &(k, v) in &xs {
1566            assert_eq!(map.get(k), Some(&v));
1567        }
1568    }
1569
1570    #[test]
1571    fn test_index() {
1572        let mut map = VecMap::new();
1573
1574        let _ = map.insert(1, 2);
1575        let _ = map.insert(2, 1);
1576        let _ = map.insert(3, 4);
1577
1578        assert_eq!(map[3], 4);
1579    }
1580
1581    #[test]
1582    #[should_panic]
1583    fn test_index_nonexistent() {
1584        let mut map = VecMap::new();
1585
1586        let _ = map.insert(1, 2);
1587        let _ = map.insert(2, 1);
1588        let _ = map.insert(3, 4);
1589
1590        let _ = map[4];
1591    }
1592
1593    #[test]
1594    fn test_entry() {
1595        let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1596
1597        let mut map: VecMap<_> = xs.iter().cloned().collect();
1598
1599        // Existing key (insert)
1600        match map.entry(1) {
1601            Vacant(_) => unreachable!(),
1602            Occupied(mut view) => {
1603                assert_eq!(view.get(), &10);
1604                assert_eq!(view.insert(100), 10);
1605            }
1606        }
1607
1608        assert_eq!(map.get(1).unwrap(), &100);
1609        assert_eq!(map.len(), 6);
1610
1611        // Existing key (update)
1612        match map.entry(2) {
1613            Vacant(_) => unreachable!(),
1614            Occupied(mut view) => {
1615                let v = view.get_mut();
1616                *v *= 10;
1617            }
1618        }
1619
1620        assert_eq!(map.get(2).unwrap(), &200);
1621        assert_eq!(map.len(), 6);
1622
1623        // Existing key (take)
1624        match map.entry(3) {
1625            Vacant(_) => unreachable!(),
1626            Occupied(view) => {
1627                assert_eq!(view.remove(), 30);
1628            }
1629        }
1630
1631        assert_eq!(map.get(3), None);
1632        assert_eq!(map.len(), 5);
1633
1634        // Inexistent key (insert)
1635        match map.entry(10) {
1636            Occupied(_) => unreachable!(),
1637            Vacant(view) => {
1638                assert_eq!(*view.insert(1000), 1000);
1639            }
1640        }
1641
1642        assert_eq!(map.get(10).unwrap(), &1000);
1643        assert_eq!(map.len(), 6);
1644    }
1645
1646    #[test]
1647    fn test_extend_ref() {
1648        let mut a = VecMap::new();
1649        let _ = a.insert(1, "one");
1650        let mut b = VecMap::new();
1651        let _ = b.insert(2, "two");
1652        let _ = b.insert(3, "three");
1653
1654        a.extend(&b);
1655
1656        assert_eq!(a.len(), 3);
1657        assert_eq!(a[&1], "one");
1658        assert_eq!(a[&2], "two");
1659        assert_eq!(a[&3], "three");
1660    }
1661
1662    #[test]
1663    #[cfg(feature = "serde")]
1664    fn test_serde() {
1665        use serde::{Deserialize, Serialize};
1666        fn impls_serde_traits<'de, S: Serialize + Deserialize<'de>>() {}
1667
1668        impls_serde_traits::<VecMap<u32>>();
1669    }
1670
1671    #[test]
1672    fn test_retain() {
1673        let mut map = VecMap::new();
1674        let _ = map.insert(1, "one");
1675        let _ = map.insert(2, "two");
1676        let _ = map.insert(3, "three");
1677        map.retain(|k, v| match k {
1678            1 => false,
1679            2 => {
1680                *v = "two changed";
1681                true
1682            }
1683            3 => false,
1684            _ => panic!(),
1685        });
1686
1687        assert_eq!(map.len(), 1);
1688        assert_eq!(map.get(1), None);
1689        assert_eq!(map[2], "two changed");
1690        assert_eq!(map.get(3), None);
1691    }
1692}
parry3d/utils/vec_map.rs

parry3d/utils/
vec_map.rs
