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

parry2d/utils/
vec_map.rs
