indexmap/
map.rs

1//! `IndexMap` is a hash table where the iteration order of the key-value
2//! pairs is independent of the hash values of the keys.
3
4mod core;
5
6pub use crate::mutable_keys::MutableKeys;
7
8#[cfg(feature = "rayon")]
9pub use crate::rayon::map as rayon;
10
11use crate::vec::{self, Vec};
12use ::core::cmp::Ordering;
13use ::core::fmt;
14use ::core::hash::{BuildHasher, Hash, Hasher};
15use ::core::iter::FromIterator;
16use ::core::ops::{Index, IndexMut, RangeBounds};
17use ::core::slice::{Iter as SliceIter, IterMut as SliceIterMut};
18
19#[cfg(feature = "std")]
20use std::collections::hash_map::RandomState;
21
22use self::core::IndexMapCore;
23use crate::equivalent::Equivalent;
24use crate::util::third;
25use crate::{Bucket, Entries, HashValue};
26
27pub use self::core::{Entry, OccupiedEntry, VacantEntry};
28
29/// A hash table where the iteration order of the key-value pairs is independent
30/// of the hash values of the keys.
31///
32/// The interface is closely compatible with the standard `HashMap`, but also
33/// has additional features.
34///
35/// # Order
36///
37/// The key-value pairs have a consistent order that is determined by
38/// the sequence of insertion and removal calls on the map. The order does
39/// not depend on the keys or the hash function at all.
40///
41/// All iterators traverse the map in *the order*.
42///
43/// The insertion order is preserved, with **notable exceptions** like the
44/// `.remove()` or `.swap_remove()` methods. Methods such as `.sort_by()` of
45/// course result in a new order, depending on the sorting order.
46///
47/// # Indices
48///
49/// The key-value pairs are indexed in a compact range without holes in the
50/// range `0..self.len()`. For example, the method `.get_full` looks up the
51/// index for a key, and the method `.get_index` looks up the key-value pair by
52/// index.
53///
54/// # Examples
55///
56/// ```
57/// use indexmap::IndexMap;
58///
59/// // count the frequency of each letter in a sentence.
60/// let mut letters = IndexMap::new();
61/// for ch in "a short treatise on fungi".chars() {
62///     *letters.entry(ch).or_insert(0) += 1;
63/// }
64///
65/// assert_eq!(letters[&'s'], 2);
66/// assert_eq!(letters[&'t'], 3);
67/// assert_eq!(letters[&'u'], 1);
68/// assert_eq!(letters.get(&'y'), None);
69/// ```
70#[cfg(feature = "std")]
71pub struct IndexMap<K, V, S = RandomState> {
72    core: IndexMapCore<K, V>,
73    hash_builder: S,
74}
75#[cfg(not(feature = "std"))]
76pub struct IndexMap<K, V, S> {
77    core: IndexMapCore<K, V>,
78    hash_builder: S,
79}
80
81impl<K, V, S> Clone for IndexMap<K, V, S>
82where
83    K: Clone,
84    V: Clone,
85    S: Clone,
86{
87    fn clone(&self) -> Self {
88        IndexMap {
89            core: self.core.clone(),
90            hash_builder: self.hash_builder.clone(),
91        }
92    }
93
94    fn clone_from(&mut self, other: &Self) {
95        self.core.clone_from(&other.core);
96        self.hash_builder.clone_from(&other.hash_builder);
97    }
98}
99
100impl<K, V, S> Entries for IndexMap<K, V, S> {
101    type Entry = Bucket<K, V>;
102
103    #[inline]
104    fn into_entries(self) -> Vec<Self::Entry> {
105        self.core.into_entries()
106    }
107
108    #[inline]
109    fn as_entries(&self) -> &[Self::Entry] {
110        self.core.as_entries()
111    }
112
113    #[inline]
114    fn as_entries_mut(&mut self) -> &mut [Self::Entry] {
115        self.core.as_entries_mut()
116    }
117
118    fn with_entries<F>(&mut self, f: F)
119    where
120        F: FnOnce(&mut [Self::Entry]),
121    {
122        self.core.with_entries(f);
123    }
124}
125
126impl<K, V, S> fmt::Debug for IndexMap<K, V, S>
127where
128    K: fmt::Debug,
129    V: fmt::Debug,
130{
131    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
132        if cfg!(not(feature = "test_debug")) {
133            f.debug_map().entries(self.iter()).finish()
134        } else {
135            // Let the inner `IndexMapCore` print all of its details
136            f.debug_struct("IndexMap")
137                .field("core", &self.core)
138                .finish()
139        }
140    }
141}
142
143#[cfg(feature = "std")]
144impl<K, V> IndexMap<K, V> {
145    /// Create a new map. (Does not allocate.)
146    #[inline]
147    pub fn new() -> Self {
148        Self::with_capacity(0)
149    }
150
151    /// Create a new map with capacity for `n` key-value pairs. (Does not
152    /// allocate if `n` is zero.)
153    ///
154    /// Computes in **O(n)** time.
155    #[inline]
156    pub fn with_capacity(n: usize) -> Self {
157        Self::with_capacity_and_hasher(n, <_>::default())
158    }
159}
160
161impl<K, V, S> IndexMap<K, V, S> {
162    /// Create a new map with capacity for `n` key-value pairs. (Does not
163    /// allocate if `n` is zero.)
164    ///
165    /// Computes in **O(n)** time.
166    #[inline]
167    pub fn with_capacity_and_hasher(n: usize, hash_builder: S) -> Self {
168        if n == 0 {
169            IndexMap {
170                core: IndexMapCore::new(),
171                hash_builder,
172            }
173        } else {
174            IndexMap {
175                core: IndexMapCore::with_capacity(n),
176                hash_builder,
177            }
178        }
179    }
180
181    /// Create a new map with `hash_builder`
182    pub fn with_hasher(hash_builder: S) -> Self {
183        Self::with_capacity_and_hasher(0, hash_builder)
184    }
185
186    /// Computes in **O(1)** time.
187    pub fn capacity(&self) -> usize {
188        self.core.capacity()
189    }
190
191    /// Return a reference to the map's `BuildHasher`.
192    pub fn hasher(&self) -> &S {
193        &self.hash_builder
194    }
195
196    /// Return the number of key-value pairs in the map.
197    ///
198    /// Computes in **O(1)** time.
199    #[inline]
200    pub fn len(&self) -> usize {
201        self.core.len()
202    }
203
204    /// Returns true if the map contains no elements.
205    ///
206    /// Computes in **O(1)** time.
207    #[inline]
208    pub fn is_empty(&self) -> bool {
209        self.len() == 0
210    }
211
212    /// Return an iterator over the key-value pairs of the map, in their order
213    pub fn iter(&self) -> Iter<'_, K, V> {
214        Iter {
215            iter: self.as_entries().iter(),
216        }
217    }
218
219    /// Return an iterator over the key-value pairs of the map, in their order
220    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
221        IterMut {
222            iter: self.as_entries_mut().iter_mut(),
223        }
224    }
225
226    /// Return an iterator over the keys of the map, in their order
227    pub fn keys(&self) -> Keys<'_, K, V> {
228        Keys {
229            iter: self.as_entries().iter(),
230        }
231    }
232
233    /// Return an iterator over the values of the map, in their order
234    pub fn values(&self) -> Values<'_, K, V> {
235        Values {
236            iter: self.as_entries().iter(),
237        }
238    }
239
240    /// Return an iterator over mutable references to the the values of the map,
241    /// in their order
242    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
243        ValuesMut {
244            iter: self.as_entries_mut().iter_mut(),
245        }
246    }
247
248    /// Remove all key-value pairs in the map, while preserving its capacity.
249    ///
250    /// Computes in **O(n)** time.
251    pub fn clear(&mut self) {
252        self.core.clear();
253    }
254
255    /// Shortens the map, keeping the first `len` elements and dropping the rest.
256    ///
257    /// If `len` is greater than the map's current length, this has no effect.
258    pub fn truncate(&mut self, len: usize) {
259        self.core.truncate(len);
260    }
261
262    /// Clears the `IndexMap` in the given index range, returning those
263    /// key-value pairs as a drain iterator.
264    ///
265    /// The range may be any type that implements `RangeBounds<usize>`,
266    /// including all of the `std::ops::Range*` types, or even a tuple pair of
267    /// `Bound` start and end values. To drain the map entirely, use `RangeFull`
268    /// like `map.drain(..)`.
269    ///
270    /// This shifts down all entries following the drained range to fill the
271    /// gap, and keeps the allocated memory for reuse.
272    ///
273    /// ***Panics*** if the starting point is greater than the end point or if
274    /// the end point is greater than the length of the map.
275    pub fn drain<R>(&mut self, range: R) -> Drain<'_, K, V>
276    where
277        R: RangeBounds<usize>,
278    {
279        Drain {
280            iter: self.core.drain(range),
281        }
282    }
283
284    /// Splits the collection into two at the given index.
285    ///
286    /// Returns a newly allocated map containing the elements in the range
287    /// `[at, len)`. After the call, the original map will be left containing
288    /// the elements `[0, at)` with its previous capacity unchanged.
289    ///
290    /// ***Panics*** if `at > len`.
291    pub fn split_off(&mut self, at: usize) -> Self
292    where
293        S: Clone,
294    {
295        Self {
296            core: self.core.split_off(at),
297            hash_builder: self.hash_builder.clone(),
298        }
299    }
300}
301
302impl<K, V, S> IndexMap<K, V, S>
303where
304    K: Hash + Eq,
305    S: BuildHasher,
306{
307    /// Reserve capacity for `additional` more key-value pairs.
308    ///
309    /// Computes in **O(n)** time.
310    pub fn reserve(&mut self, additional: usize) {
311        self.core.reserve(additional);
312    }
313
314    /// Shrink the capacity of the map as much as possible.
315    ///
316    /// Computes in **O(n)** time.
317    pub fn shrink_to_fit(&mut self) {
318        self.core.shrink_to_fit();
319    }
320
321    fn hash<Q: ?Sized + Hash>(&self, key: &Q) -> HashValue {
322        let mut h = self.hash_builder.build_hasher();
323        key.hash(&mut h);
324        HashValue(h.finish() as usize)
325    }
326
327    /// Insert a key-value pair in the map.
328    ///
329    /// If an equivalent key already exists in the map: the key remains and
330    /// retains in its place in the order, its corresponding value is updated
331    /// with `value` and the older value is returned inside `Some(_)`.
332    ///
333    /// If no equivalent key existed in the map: the new key-value pair is
334    /// inserted, last in order, and `None` is returned.
335    ///
336    /// Computes in **O(1)** time (amortized average).
337    ///
338    /// See also [`entry`](#method.entry) if you you want to insert *or* modify
339    /// or if you need to get the index of the corresponding key-value pair.
340    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
341        self.insert_full(key, value).1
342    }
343
344    /// Insert a key-value pair in the map, and get their index.
345    ///
346    /// If an equivalent key already exists in the map: the key remains and
347    /// retains in its place in the order, its corresponding value is updated
348    /// with `value` and the older value is returned inside `(index, Some(_))`.
349    ///
350    /// If no equivalent key existed in the map: the new key-value pair is
351    /// inserted, last in order, and `(index, None)` is returned.
352    ///
353    /// Computes in **O(1)** time (amortized average).
354    ///
355    /// See also [`entry`](#method.entry) if you you want to insert *or* modify
356    /// or if you need to get the index of the corresponding key-value pair.
357    pub fn insert_full(&mut self, key: K, value: V) -> (usize, Option<V>) {
358        let hash = self.hash(&key);
359        self.core.insert_full(hash, key, value)
360    }
361
362    /// Get the given key’s corresponding entry in the map for insertion and/or
363    /// in-place manipulation.
364    ///
365    /// Computes in **O(1)** time (amortized average).
366    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
367        let hash = self.hash(&key);
368        self.core.entry(hash, key)
369    }
370
371    /// Return `true` if an equivalent to `key` exists in the map.
372    ///
373    /// Computes in **O(1)** time (average).
374    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
375    where
376        Q: Hash + Equivalent<K>,
377    {
378        self.get_index_of(key).is_some()
379    }
380
381    /// Return a reference to the value stored for `key`, if it is present,
382    /// else `None`.
383    ///
384    /// Computes in **O(1)** time (average).
385    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
386    where
387        Q: Hash + Equivalent<K>,
388    {
389        if let Some(i) = self.get_index_of(key) {
390            let entry = &self.as_entries()[i];
391            Some(&entry.value)
392        } else {
393            None
394        }
395    }
396
397    /// Return references to the key-value pair stored for `key`,
398    /// if it is present, else `None`.
399    ///
400    /// Computes in **O(1)** time (average).
401    pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
402    where
403        Q: Hash + Equivalent<K>,
404    {
405        if let Some(i) = self.get_index_of(key) {
406            let entry = &self.as_entries()[i];
407            Some((&entry.key, &entry.value))
408        } else {
409            None
410        }
411    }
412
413    /// Return item index, key and value
414    pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)>
415    where
416        Q: Hash + Equivalent<K>,
417    {
418        if let Some(i) = self.get_index_of(key) {
419            let entry = &self.as_entries()[i];
420            Some((i, &entry.key, &entry.value))
421        } else {
422            None
423        }
424    }
425
426    /// Return item index, if it exists in the map
427    pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize>
428    where
429        Q: Hash + Equivalent<K>,
430    {
431        if self.is_empty() {
432            None
433        } else {
434            let hash = self.hash(key);
435            self.core.get_index_of(hash, key)
436        }
437    }
438
439    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
440    where
441        Q: Hash + Equivalent<K>,
442    {
443        if let Some(i) = self.get_index_of(key) {
444            let entry = &mut self.as_entries_mut()[i];
445            Some(&mut entry.value)
446        } else {
447            None
448        }
449    }
450
451    pub fn get_full_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &K, &mut V)>
452    where
453        Q: Hash + Equivalent<K>,
454    {
455        if let Some(i) = self.get_index_of(key) {
456            let entry = &mut self.as_entries_mut()[i];
457            Some((i, &entry.key, &mut entry.value))
458        } else {
459            None
460        }
461    }
462
463    pub(crate) fn get_full_mut2_impl<Q: ?Sized>(
464        &mut self,
465        key: &Q,
466    ) -> Option<(usize, &mut K, &mut V)>
467    where
468        Q: Hash + Equivalent<K>,
469    {
470        if let Some(i) = self.get_index_of(key) {
471            let entry = &mut self.as_entries_mut()[i];
472            Some((i, &mut entry.key, &mut entry.value))
473        } else {
474            None
475        }
476    }
477
478    /// Remove the key-value pair equivalent to `key` and return
479    /// its value.
480    ///
481    /// **NOTE:** This is equivalent to `.swap_remove(key)`, if you need to
482    /// preserve the order of the keys in the map, use `.shift_remove(key)`
483    /// instead.
484    ///
485    /// Computes in **O(1)** time (average).
486    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
487    where
488        Q: Hash + Equivalent<K>,
489    {
490        self.swap_remove(key)
491    }
492
493    /// Remove and return the key-value pair equivalent to `key`.
494    ///
495    /// **NOTE:** This is equivalent to `.swap_remove_entry(key)`, if you need to
496    /// preserve the order of the keys in the map, use `.shift_remove_entry(key)`
497    /// instead.
498    ///
499    /// Computes in **O(1)** time (average).
500    pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
501    where
502        Q: Hash + Equivalent<K>,
503    {
504        self.swap_remove_entry(key)
505    }
506
507    /// Remove the key-value pair equivalent to `key` and return
508    /// its value.
509    ///
510    /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
511    /// last element of the map and popping it off. **This perturbs
512    /// the position of what used to be the last element!**
513    ///
514    /// Return `None` if `key` is not in map.
515    ///
516    /// Computes in **O(1)** time (average).
517    pub fn swap_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
518    where
519        Q: Hash + Equivalent<K>,
520    {
521        self.swap_remove_full(key).map(third)
522    }
523
524    /// Remove and return the key-value pair equivalent to `key`.
525    ///
526    /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
527    /// last element of the map and popping it off. **This perturbs
528    /// the position of what used to be the last element!**
529    ///
530    /// Return `None` if `key` is not in map.
531    ///
532    /// Computes in **O(1)** time (average).
533    pub fn swap_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
534    where
535        Q: Hash + Equivalent<K>,
536    {
537        match self.swap_remove_full(key) {
538            Some((_, key, value)) => Some((key, value)),
539            None => None,
540        }
541    }
542
543    /// Remove the key-value pair equivalent to `key` and return it and
544    /// the index it had.
545    ///
546    /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
547    /// last element of the map and popping it off. **This perturbs
548    /// the position of what used to be the last element!**
549    ///
550    /// Return `None` if `key` is not in map.
551    ///
552    /// Computes in **O(1)** time (average).
553    pub fn swap_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)>
554    where
555        Q: Hash + Equivalent<K>,
556    {
557        if self.is_empty() {
558            return None;
559        }
560        let hash = self.hash(key);
561        self.core.swap_remove_full(hash, key)
562    }
563
564    /// Remove the key-value pair equivalent to `key` and return
565    /// its value.
566    ///
567    /// Like `Vec::remove`, the pair is removed by shifting all of the
568    /// elements that follow it, preserving their relative order.
569    /// **This perturbs the index of all of those elements!**
570    ///
571    /// Return `None` if `key` is not in map.
572    ///
573    /// Computes in **O(n)** time (average).
574    pub fn shift_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
575    where
576        Q: Hash + Equivalent<K>,
577    {
578        self.shift_remove_full(key).map(third)
579    }
580
581    /// Remove and return the key-value pair equivalent to `key`.
582    ///
583    /// Like `Vec::remove`, the pair is removed by shifting all of the
584    /// elements that follow it, preserving their relative order.
585    /// **This perturbs the index of all of those elements!**
586    ///
587    /// Return `None` if `key` is not in map.
588    ///
589    /// Computes in **O(n)** time (average).
590    pub fn shift_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
591    where
592        Q: Hash + Equivalent<K>,
593    {
594        match self.shift_remove_full(key) {
595            Some((_, key, value)) => Some((key, value)),
596            None => None,
597        }
598    }
599
600    /// Remove the key-value pair equivalent to `key` and return it and
601    /// the index it had.
602    ///
603    /// Like `Vec::remove`, the pair is removed by shifting all of the
604    /// elements that follow it, preserving their relative order.
605    /// **This perturbs the index of all of those elements!**
606    ///
607    /// Return `None` if `key` is not in map.
608    ///
609    /// Computes in **O(n)** time (average).
610    pub fn shift_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)>
611    where
612        Q: Hash + Equivalent<K>,
613    {
614        if self.is_empty() {
615            return None;
616        }
617        let hash = self.hash(key);
618        self.core.shift_remove_full(hash, key)
619    }
620
621    /// Remove the last key-value pair
622    ///
623    /// Computes in **O(1)** time (average).
624    pub fn pop(&mut self) -> Option<(K, V)> {
625        self.core.pop()
626    }
627
628    /// Scan through each key-value pair in the map and keep those where the
629    /// closure `keep` returns `true`.
630    ///
631    /// The elements are visited in order, and remaining elements keep their
632    /// order.
633    ///
634    /// Computes in **O(n)** time (average).
635    pub fn retain<F>(&mut self, mut keep: F)
636    where
637        F: FnMut(&K, &mut V) -> bool,
638    {
639        self.core.retain_in_order(move |k, v| keep(k, v));
640    }
641
642    pub(crate) fn retain_mut<F>(&mut self, keep: F)
643    where
644        F: FnMut(&mut K, &mut V) -> bool,
645    {
646        self.core.retain_in_order(keep);
647    }
648
649    /// Sort the map’s key-value pairs by the default ordering of the keys.
650    ///
651    /// See `sort_by` for details.
652    pub fn sort_keys(&mut self)
653    where
654        K: Ord,
655    {
656        self.with_entries(|entries| {
657            entries.sort_by(|a, b| Ord::cmp(&a.key, &b.key));
658        });
659    }
660
661    /// Sort the map’s key-value pairs in place using the comparison
662    /// function `compare`.
663    ///
664    /// The comparison function receives two key and value pairs to compare (you
665    /// can sort by keys or values or their combination as needed).
666    ///
667    /// Computes in **O(n log n + c)** time and **O(n)** space where *n* is
668    /// the length of the map and *c* the capacity. The sort is stable.
669    pub fn sort_by<F>(&mut self, mut cmp: F)
670    where
671        F: FnMut(&K, &V, &K, &V) -> Ordering,
672    {
673        self.with_entries(move |entries| {
674            entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
675        });
676    }
677
678    /// Sort the key-value pairs of the map and return a by value iterator of
679    /// the key-value pairs with the result.
680    ///
681    /// The sort is stable.
682    pub fn sorted_by<F>(self, mut cmp: F) -> IntoIter<K, V>
683    where
684        F: FnMut(&K, &V, &K, &V) -> Ordering,
685    {
686        let mut entries = self.into_entries();
687        entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
688        IntoIter {
689            iter: entries.into_iter(),
690        }
691    }
692
693    /// Reverses the order of the map’s key-value pairs in place.
694    ///
695    /// Computes in **O(n)** time and **O(1)** space.
696    pub fn reverse(&mut self) {
697        self.core.reverse()
698    }
699}
700
701impl<K, V, S> IndexMap<K, V, S> {
702    /// Get a key-value pair by index
703    ///
704    /// Valid indices are *0 <= index < self.len()*
705    ///
706    /// Computes in **O(1)** time.
707    pub fn get_index(&self, index: usize) -> Option<(&K, &V)> {
708        self.as_entries().get(index).map(Bucket::refs)
709    }
710
711    /// Get a key-value pair by index
712    ///
713    /// Valid indices are *0 <= index < self.len()*
714    ///
715    /// Computes in **O(1)** time.
716    pub fn get_index_mut(&mut self, index: usize) -> Option<(&mut K, &mut V)> {
717        self.as_entries_mut().get_mut(index).map(Bucket::muts)
718    }
719
720    /// Get the first key-value pair
721    ///
722    /// Computes in **O(1)** time.
723    pub fn first(&self) -> Option<(&K, &V)> {
724        self.as_entries().first().map(Bucket::refs)
725    }
726
727    /// Get the first key-value pair, with mutable access to the value
728    ///
729    /// Computes in **O(1)** time.
730    pub fn first_mut(&mut self) -> Option<(&K, &mut V)> {
731        self.as_entries_mut().first_mut().map(Bucket::ref_mut)
732    }
733
734    /// Get the last key-value pair
735    ///
736    /// Computes in **O(1)** time.
737    pub fn last(&self) -> Option<(&K, &V)> {
738        self.as_entries().last().map(Bucket::refs)
739    }
740
741    /// Get the last key-value pair, with mutable access to the value
742    ///
743    /// Computes in **O(1)** time.
744    pub fn last_mut(&mut self) -> Option<(&K, &mut V)> {
745        self.as_entries_mut().last_mut().map(Bucket::ref_mut)
746    }
747
748    /// Remove the key-value pair by index
749    ///
750    /// Valid indices are *0 <= index < self.len()*
751    ///
752    /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
753    /// last element of the map and popping it off. **This perturbs
754    /// the position of what used to be the last element!**
755    ///
756    /// Computes in **O(1)** time (average).
757    pub fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> {
758        self.core.swap_remove_index(index)
759    }
760
761    /// Remove the key-value pair by index
762    ///
763    /// Valid indices are *0 <= index < self.len()*
764    ///
765    /// Like `Vec::remove`, the pair is removed by shifting all of the
766    /// elements that follow it, preserving their relative order.
767    /// **This perturbs the index of all of those elements!**
768    ///
769    /// Computes in **O(n)** time (average).
770    pub fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> {
771        self.core.shift_remove_index(index)
772    }
773
774    /// Swaps the position of two key-value pairs in the map.
775    ///
776    /// ***Panics*** if `a` or `b` are out of bounds.
777    pub fn swap_indices(&mut self, a: usize, b: usize) {
778        self.core.swap_indices(a, b)
779    }
780}
781
782/// An iterator over the keys of a `IndexMap`.
783///
784/// This `struct` is created by the [`keys`] method on [`IndexMap`]. See its
785/// documentation for more.
786///
787/// [`keys`]: struct.IndexMap.html#method.keys
788/// [`IndexMap`]: struct.IndexMap.html
789pub struct Keys<'a, K, V> {
790    pub(crate) iter: SliceIter<'a, Bucket<K, V>>,
791}
792
793impl<'a, K, V> Iterator for Keys<'a, K, V> {
794    type Item = &'a K;
795
796    iterator_methods!(Bucket::key_ref);
797}
798
799impl<K, V> DoubleEndedIterator for Keys<'_, K, V> {
800    fn next_back(&mut self) -> Option<Self::Item> {
801        self.iter.next_back().map(Bucket::key_ref)
802    }
803}
804
805impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
806    fn len(&self) -> usize {
807        self.iter.len()
808    }
809}
810
811// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
812impl<K, V> Clone for Keys<'_, K, V> {
813    fn clone(&self) -> Self {
814        Keys {
815            iter: self.iter.clone(),
816        }
817    }
818}
819
820impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
821    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
822        f.debug_list().entries(self.clone()).finish()
823    }
824}
825
826/// An iterator over the values of a `IndexMap`.
827///
828/// This `struct` is created by the [`values`] method on [`IndexMap`]. See its
829/// documentation for more.
830///
831/// [`values`]: struct.IndexMap.html#method.values
832/// [`IndexMap`]: struct.IndexMap.html
833pub struct Values<'a, K, V> {
834    iter: SliceIter<'a, Bucket<K, V>>,
835}
836
837impl<'a, K, V> Iterator for Values<'a, K, V> {
838    type Item = &'a V;
839
840    iterator_methods!(Bucket::value_ref);
841}
842
843impl<K, V> DoubleEndedIterator for Values<'_, K, V> {
844    fn next_back(&mut self) -> Option<Self::Item> {
845        self.iter.next_back().map(Bucket::value_ref)
846    }
847}
848
849impl<K, V> ExactSizeIterator for Values<'_, K, V> {
850    fn len(&self) -> usize {
851        self.iter.len()
852    }
853}
854
855// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
856impl<K, V> Clone for Values<'_, K, V> {
857    fn clone(&self) -> Self {
858        Values {
859            iter: self.iter.clone(),
860        }
861    }
862}
863
864impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
865    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
866        f.debug_list().entries(self.clone()).finish()
867    }
868}
869
870/// A mutable iterator over the values of a `IndexMap`.
871///
872/// This `struct` is created by the [`values_mut`] method on [`IndexMap`]. See its
873/// documentation for more.
874///
875/// [`values_mut`]: struct.IndexMap.html#method.values_mut
876/// [`IndexMap`]: struct.IndexMap.html
877pub struct ValuesMut<'a, K, V> {
878    iter: SliceIterMut<'a, Bucket<K, V>>,
879}
880
881impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
882    type Item = &'a mut V;
883
884    iterator_methods!(Bucket::value_mut);
885}
886
887impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> {
888    fn next_back(&mut self) -> Option<Self::Item> {
889        self.iter.next_back().map(Bucket::value_mut)
890    }
891}
892
893impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
894    fn len(&self) -> usize {
895        self.iter.len()
896    }
897}
898
899/// An iterator over the entries of a `IndexMap`.
900///
901/// This `struct` is created by the [`iter`] method on [`IndexMap`]. See its
902/// documentation for more.
903///
904/// [`iter`]: struct.IndexMap.html#method.iter
905/// [`IndexMap`]: struct.IndexMap.html
906pub struct Iter<'a, K, V> {
907    iter: SliceIter<'a, Bucket<K, V>>,
908}
909
910impl<'a, K, V> Iterator for Iter<'a, K, V> {
911    type Item = (&'a K, &'a V);
912
913    iterator_methods!(Bucket::refs);
914}
915
916impl<K, V> DoubleEndedIterator for Iter<'_, K, V> {
917    fn next_back(&mut self) -> Option<Self::Item> {
918        self.iter.next_back().map(Bucket::refs)
919    }
920}
921
922impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
923    fn len(&self) -> usize {
924        self.iter.len()
925    }
926}
927
928// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
929impl<K, V> Clone for Iter<'_, K, V> {
930    fn clone(&self) -> Self {
931        Iter {
932            iter: self.iter.clone(),
933        }
934    }
935}
936
937impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
938    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
939        f.debug_list().entries(self.clone()).finish()
940    }
941}
942
943/// A mutable iterator over the entries of a `IndexMap`.
944///
945/// This `struct` is created by the [`iter_mut`] method on [`IndexMap`]. See its
946/// documentation for more.
947///
948/// [`iter_mut`]: struct.IndexMap.html#method.iter_mut
949/// [`IndexMap`]: struct.IndexMap.html
950pub struct IterMut<'a, K, V> {
951    iter: SliceIterMut<'a, Bucket<K, V>>,
952}
953
954impl<'a, K, V> Iterator for IterMut<'a, K, V> {
955    type Item = (&'a K, &'a mut V);
956
957    iterator_methods!(Bucket::ref_mut);
958}
959
960impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> {
961    fn next_back(&mut self) -> Option<Self::Item> {
962        self.iter.next_back().map(Bucket::ref_mut)
963    }
964}
965
966impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
967    fn len(&self) -> usize {
968        self.iter.len()
969    }
970}
971
972/// An owning iterator over the entries of a `IndexMap`.
973///
974/// This `struct` is created by the [`into_iter`] method on [`IndexMap`]
975/// (provided by the `IntoIterator` trait). See its documentation for more.
976///
977/// [`into_iter`]: struct.IndexMap.html#method.into_iter
978/// [`IndexMap`]: struct.IndexMap.html
979pub struct IntoIter<K, V> {
980    pub(crate) iter: vec::IntoIter<Bucket<K, V>>,
981}
982
983impl<K, V> Iterator for IntoIter<K, V> {
984    type Item = (K, V);
985
986    iterator_methods!(Bucket::key_value);
987}
988
989impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
990    fn next_back(&mut self) -> Option<Self::Item> {
991        self.iter.next_back().map(Bucket::key_value)
992    }
993}
994
995impl<K, V> ExactSizeIterator for IntoIter<K, V> {
996    fn len(&self) -> usize {
997        self.iter.len()
998    }
999}
1000
1001impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
1002    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1003        let iter = self.iter.as_slice().iter().map(Bucket::refs);
1004        f.debug_list().entries(iter).finish()
1005    }
1006}
1007
1008/// A draining iterator over the entries of a `IndexMap`.
1009///
1010/// This `struct` is created by the [`drain`] method on [`IndexMap`]. See its
1011/// documentation for more.
1012///
1013/// [`drain`]: struct.IndexMap.html#method.drain
1014/// [`IndexMap`]: struct.IndexMap.html
1015pub struct Drain<'a, K, V> {
1016    pub(crate) iter: vec::Drain<'a, Bucket<K, V>>,
1017}
1018
1019impl<K, V> Iterator for Drain<'_, K, V> {
1020    type Item = (K, V);
1021
1022    iterator_methods!(Bucket::key_value);
1023}
1024
1025impl<K, V> DoubleEndedIterator for Drain<'_, K, V> {
1026    double_ended_iterator_methods!(Bucket::key_value);
1027}
1028
1029impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> {
1030    type Item = (&'a K, &'a V);
1031    type IntoIter = Iter<'a, K, V>;
1032    fn into_iter(self) -> Self::IntoIter {
1033        self.iter()
1034    }
1035}
1036
1037impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> {
1038    type Item = (&'a K, &'a mut V);
1039    type IntoIter = IterMut<'a, K, V>;
1040    fn into_iter(self) -> Self::IntoIter {
1041        self.iter_mut()
1042    }
1043}
1044
1045impl<K, V, S> IntoIterator for IndexMap<K, V, S> {
1046    type Item = (K, V);
1047    type IntoIter = IntoIter<K, V>;
1048    fn into_iter(self) -> Self::IntoIter {
1049        IntoIter {
1050            iter: self.into_entries().into_iter(),
1051        }
1052    }
1053}
1054
1055/// Access `IndexMap` values corresponding to a key.
1056///
1057/// # Examples
1058///
1059/// ```
1060/// use indexmap::IndexMap;
1061///
1062/// let mut map = IndexMap::new();
1063/// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
1064///     map.insert(word.to_lowercase(), word.to_uppercase());
1065/// }
1066/// assert_eq!(map["lorem"], "LOREM");
1067/// assert_eq!(map["ipsum"], "IPSUM");
1068/// ```
1069///
1070/// ```should_panic
1071/// use indexmap::IndexMap;
1072///
1073/// let mut map = IndexMap::new();
1074/// map.insert("foo", 1);
1075/// println!("{:?}", map["bar"]); // panics!
1076/// ```
1077impl<K, V, Q: ?Sized, S> Index<&Q> for IndexMap<K, V, S>
1078where
1079    Q: Hash + Equivalent<K>,
1080    K: Hash + Eq,
1081    S: BuildHasher,
1082{
1083    type Output = V;
1084
1085    /// Returns a reference to the value corresponding to the supplied `key`.
1086    ///
1087    /// ***Panics*** if `key` is not present in the map.
1088    fn index(&self, key: &Q) -> &V {
1089        self.get(key).expect("IndexMap: key not found")
1090    }
1091}
1092
1093/// Access `IndexMap` values corresponding to a key.
1094///
1095/// Mutable indexing allows changing / updating values of key-value
1096/// pairs that are already present.
1097///
1098/// You can **not** insert new pairs with index syntax, use `.insert()`.
1099///
1100/// # Examples
1101///
1102/// ```
1103/// use indexmap::IndexMap;
1104///
1105/// let mut map = IndexMap::new();
1106/// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
1107///     map.insert(word.to_lowercase(), word.to_string());
1108/// }
1109/// let lorem = &mut map["lorem"];
1110/// assert_eq!(lorem, "Lorem");
1111/// lorem.retain(char::is_lowercase);
1112/// assert_eq!(map["lorem"], "orem");
1113/// ```
1114///
1115/// ```should_panic
1116/// use indexmap::IndexMap;
1117///
1118/// let mut map = IndexMap::new();
1119/// map.insert("foo", 1);
1120/// map["bar"] = 1; // panics!
1121/// ```
1122impl<K, V, Q: ?Sized, S> IndexMut<&Q> for IndexMap<K, V, S>
1123where
1124    Q: Hash + Equivalent<K>,
1125    K: Hash + Eq,
1126    S: BuildHasher,
1127{
1128    /// Returns a mutable reference to the value corresponding to the supplied `key`.
1129    ///
1130    /// ***Panics*** if `key` is not present in the map.
1131    fn index_mut(&mut self, key: &Q) -> &mut V {
1132        self.get_mut(key).expect("IndexMap: key not found")
1133    }
1134}
1135
1136/// Access `IndexMap` values at indexed positions.
1137///
1138/// # Examples
1139///
1140/// ```
1141/// use indexmap::IndexMap;
1142///
1143/// let mut map = IndexMap::new();
1144/// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
1145///     map.insert(word.to_lowercase(), word.to_uppercase());
1146/// }
1147/// assert_eq!(map[0], "LOREM");
1148/// assert_eq!(map[1], "IPSUM");
1149/// map.reverse();
1150/// assert_eq!(map[0], "AMET");
1151/// assert_eq!(map[1], "SIT");
1152/// map.sort_keys();
1153/// assert_eq!(map[0], "AMET");
1154/// assert_eq!(map[1], "DOLOR");
1155/// ```
1156///
1157/// ```should_panic
1158/// use indexmap::IndexMap;
1159///
1160/// let mut map = IndexMap::new();
1161/// map.insert("foo", 1);
1162/// println!("{:?}", map[10]); // panics!
1163/// ```
1164impl<K, V, S> Index<usize> for IndexMap<K, V, S> {
1165    type Output = V;
1166
1167    /// Returns a reference to the value at the supplied `index`.
1168    ///
1169    /// ***Panics*** if `index` is out of bounds.
1170    fn index(&self, index: usize) -> &V {
1171        self.get_index(index)
1172            .expect("IndexMap: index out of bounds")
1173            .1
1174    }
1175}
1176
1177/// Access `IndexMap` values at indexed positions.
1178///
1179/// Mutable indexing allows changing / updating indexed values
1180/// that are already present.
1181///
1182/// You can **not** insert new values with index syntax, use `.insert()`.
1183///
1184/// # Examples
1185///
1186/// ```
1187/// use indexmap::IndexMap;
1188///
1189/// let mut map = IndexMap::new();
1190/// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
1191///     map.insert(word.to_lowercase(), word.to_string());
1192/// }
1193/// let lorem = &mut map[0];
1194/// assert_eq!(lorem, "Lorem");
1195/// lorem.retain(char::is_lowercase);
1196/// assert_eq!(map["lorem"], "orem");
1197/// ```
1198///
1199/// ```should_panic
1200/// use indexmap::IndexMap;
1201///
1202/// let mut map = IndexMap::new();
1203/// map.insert("foo", 1);
1204/// map[10] = 1; // panics!
1205/// ```
1206impl<K, V, S> IndexMut<usize> for IndexMap<K, V, S> {
1207    /// Returns a mutable reference to the value at the supplied `index`.
1208    ///
1209    /// ***Panics*** if `index` is out of bounds.
1210    fn index_mut(&mut self, index: usize) -> &mut V {
1211        self.get_index_mut(index)
1212            .expect("IndexMap: index out of bounds")
1213            .1
1214    }
1215}
1216
1217impl<K, V, S> FromIterator<(K, V)> for IndexMap<K, V, S>
1218where
1219    K: Hash + Eq,
1220    S: BuildHasher + Default,
1221{
1222    /// Create an `IndexMap` from the sequence of key-value pairs in the
1223    /// iterable.
1224    ///
1225    /// `from_iter` uses the same logic as `extend`. See
1226    /// [`extend`](#method.extend) for more details.
1227    fn from_iter<I: IntoIterator<Item = (K, V)>>(iterable: I) -> Self {
1228        let iter = iterable.into_iter();
1229        let (low, _) = iter.size_hint();
1230        let mut map = Self::with_capacity_and_hasher(low, <_>::default());
1231        map.extend(iter);
1232        map
1233    }
1234}
1235
1236impl<K, V, S> Extend<(K, V)> for IndexMap<K, V, S>
1237where
1238    K: Hash + Eq,
1239    S: BuildHasher,
1240{
1241    /// Extend the map with all key-value pairs in the iterable.
1242    ///
1243    /// This is equivalent to calling [`insert`](#method.insert) for each of
1244    /// them in order, which means that for keys that already existed
1245    /// in the map, their value is updated but it keeps the existing order.
1246    ///
1247    /// New keys are inserted in the order they appear in the sequence. If
1248    /// equivalents of a key occur more than once, the last corresponding value
1249    /// prevails.
1250    fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iterable: I) {
1251        // (Note: this is a copy of `std`/`hashbrown`'s reservation logic.)
1252        // Keys may be already present or show multiple times in the iterator.
1253        // Reserve the entire hint lower bound if the map is empty.
1254        // Otherwise reserve half the hint (rounded up), so the map
1255        // will only resize twice in the worst case.
1256        let iter = iterable.into_iter();
1257        let reserve = if self.is_empty() {
1258            iter.size_hint().0
1259        } else {
1260            (iter.size_hint().0 + 1) / 2
1261        };
1262        self.reserve(reserve);
1263        iter.for_each(move |(k, v)| {
1264            self.insert(k, v);
1265        });
1266    }
1267}
1268
1269impl<'a, K, V, S> Extend<(&'a K, &'a V)> for IndexMap<K, V, S>
1270where
1271    K: Hash + Eq + Copy,
1272    V: Copy,
1273    S: BuildHasher,
1274{
1275    /// Extend the map with all key-value pairs in the iterable.
1276    ///
1277    /// See the first extend method for more details.
1278    fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iterable: I) {
1279        self.extend(iterable.into_iter().map(|(&key, &value)| (key, value)));
1280    }
1281}
1282
1283impl<K, V, S> Default for IndexMap<K, V, S>
1284where
1285    S: Default,
1286{
1287    /// Return an empty `IndexMap`
1288    fn default() -> Self {
1289        Self::with_capacity_and_hasher(0, S::default())
1290    }
1291}
1292
1293impl<K, V1, S1, V2, S2> PartialEq<IndexMap<K, V2, S2>> for IndexMap<K, V1, S1>
1294where
1295    K: Hash + Eq,
1296    V1: PartialEq<V2>,
1297    S1: BuildHasher,
1298    S2: BuildHasher,
1299{
1300    fn eq(&self, other: &IndexMap<K, V2, S2>) -> bool {
1301        if self.len() != other.len() {
1302            return false;
1303        }
1304
1305        self.iter()
1306            .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
1307    }
1308}
1309
1310impl<K, V, S> Eq for IndexMap<K, V, S>
1311where
1312    K: Eq + Hash,
1313    V: Eq,
1314    S: BuildHasher,
1315{
1316}
1317
1318#[cfg(test)]
1319mod tests {
1320    use super::*;
1321    use crate::util::enumerate;
1322    use std::string::String;
1323
1324    #[test]
1325    fn it_works() {
1326        let mut map = IndexMap::new();
1327        assert_eq!(map.is_empty(), true);
1328        map.insert(1, ());
1329        map.insert(1, ());
1330        assert_eq!(map.len(), 1);
1331        assert!(map.get(&1).is_some());
1332        assert_eq!(map.is_empty(), false);
1333    }
1334
1335    #[test]
1336    fn new() {
1337        let map = IndexMap::<String, String>::new();
1338        println!("{:?}", map);
1339        assert_eq!(map.capacity(), 0);
1340        assert_eq!(map.len(), 0);
1341        assert_eq!(map.is_empty(), true);
1342    }
1343
1344    #[test]
1345    fn insert() {
1346        let insert = [0, 4, 2, 12, 8, 7, 11, 5];
1347        let not_present = [1, 3, 6, 9, 10];
1348        let mut map = IndexMap::with_capacity(insert.len());
1349
1350        for (i, &elt) in enumerate(&insert) {
1351            assert_eq!(map.len(), i);
1352            map.insert(elt, elt);
1353            assert_eq!(map.len(), i + 1);
1354            assert_eq!(map.get(&elt), Some(&elt));
1355            assert_eq!(map[&elt], elt);
1356        }
1357        println!("{:?}", map);
1358
1359        for &elt in &not_present {
1360            assert!(map.get(&elt).is_none());
1361        }
1362    }
1363
1364    #[test]
1365    fn insert_full() {
1366        let insert = vec![9, 2, 7, 1, 4, 6, 13];
1367        let present = vec![1, 6, 2];
1368        let mut map = IndexMap::with_capacity(insert.len());
1369
1370        for (i, &elt) in enumerate(&insert) {
1371            assert_eq!(map.len(), i);
1372            let (index, existing) = map.insert_full(elt, elt);
1373            assert_eq!(existing, None);
1374            assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0));
1375            assert_eq!(map.len(), i + 1);
1376        }
1377
1378        let len = map.len();
1379        for &elt in &present {
1380            let (index, existing) = map.insert_full(elt, elt);
1381            assert_eq!(existing, Some(elt));
1382            assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0));
1383            assert_eq!(map.len(), len);
1384        }
1385    }
1386
1387    #[test]
1388    fn insert_2() {
1389        let mut map = IndexMap::with_capacity(16);
1390
1391        let mut keys = vec![];
1392        keys.extend(0..16);
1393        keys.extend(128..267);
1394
1395        for &i in &keys {
1396            let old_map = map.clone();
1397            map.insert(i, ());
1398            for key in old_map.keys() {
1399                if map.get(key).is_none() {
1400                    println!("old_map: {:?}", old_map);
1401                    println!("map: {:?}", map);
1402                    panic!("did not find {} in map", key);
1403                }
1404            }
1405        }
1406
1407        for &i in &keys {
1408            assert!(map.get(&i).is_some(), "did not find {}", i);
1409        }
1410    }
1411
1412    #[test]
1413    fn insert_order() {
1414        let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
1415        let mut map = IndexMap::new();
1416
1417        for &elt in &insert {
1418            map.insert(elt, ());
1419        }
1420
1421        assert_eq!(map.keys().count(), map.len());
1422        assert_eq!(map.keys().count(), insert.len());
1423        for (a, b) in insert.iter().zip(map.keys()) {
1424            assert_eq!(a, b);
1425        }
1426        for (i, k) in (0..insert.len()).zip(map.keys()) {
1427            assert_eq!(map.get_index(i).unwrap().0, k);
1428        }
1429    }
1430
1431    #[test]
1432    fn grow() {
1433        let insert = [0, 4, 2, 12, 8, 7, 11];
1434        let not_present = [1, 3, 6, 9, 10];
1435        let mut map = IndexMap::with_capacity(insert.len());
1436
1437        for (i, &elt) in enumerate(&insert) {
1438            assert_eq!(map.len(), i);
1439            map.insert(elt, elt);
1440            assert_eq!(map.len(), i + 1);
1441            assert_eq!(map.get(&elt), Some(&elt));
1442            assert_eq!(map[&elt], elt);
1443        }
1444
1445        println!("{:?}", map);
1446        for &elt in &insert {
1447            map.insert(elt * 10, elt);
1448        }
1449        for &elt in &insert {
1450            map.insert(elt * 100, elt);
1451        }
1452        for (i, &elt) in insert.iter().cycle().enumerate().take(100) {
1453            map.insert(elt * 100 + i as i32, elt);
1454        }
1455        println!("{:?}", map);
1456        for &elt in &not_present {
1457            assert!(map.get(&elt).is_none());
1458        }
1459    }
1460
1461    #[test]
1462    fn reserve() {
1463        let mut map = IndexMap::<usize, usize>::new();
1464        assert_eq!(map.capacity(), 0);
1465        map.reserve(100);
1466        let capacity = map.capacity();
1467        assert!(capacity >= 100);
1468        for i in 0..capacity {
1469            assert_eq!(map.len(), i);
1470            map.insert(i, i * i);
1471            assert_eq!(map.len(), i + 1);
1472            assert_eq!(map.capacity(), capacity);
1473            assert_eq!(map.get(&i), Some(&(i * i)));
1474        }
1475        map.insert(capacity, std::usize::MAX);
1476        assert_eq!(map.len(), capacity + 1);
1477        assert!(map.capacity() > capacity);
1478        assert_eq!(map.get(&capacity), Some(&std::usize::MAX));
1479    }
1480
1481    #[test]
1482    fn shrink_to_fit() {
1483        let mut map = IndexMap::<usize, usize>::new();
1484        assert_eq!(map.capacity(), 0);
1485        for i in 0..100 {
1486            assert_eq!(map.len(), i);
1487            map.insert(i, i * i);
1488            assert_eq!(map.len(), i + 1);
1489            assert!(map.capacity() >= i + 1);
1490            assert_eq!(map.get(&i), Some(&(i * i)));
1491            map.shrink_to_fit();
1492            assert_eq!(map.len(), i + 1);
1493            assert_eq!(map.capacity(), i + 1);
1494            assert_eq!(map.get(&i), Some(&(i * i)));
1495        }
1496    }
1497
1498    #[test]
1499    fn remove() {
1500        let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
1501        let mut map = IndexMap::new();
1502
1503        for &elt in &insert {
1504            map.insert(elt, elt);
1505        }
1506
1507        assert_eq!(map.keys().count(), map.len());
1508        assert_eq!(map.keys().count(), insert.len());
1509        for (a, b) in insert.iter().zip(map.keys()) {
1510            assert_eq!(a, b);
1511        }
1512
1513        let remove_fail = [99, 77];
1514        let remove = [4, 12, 8, 7];
1515
1516        for &key in &remove_fail {
1517            assert!(map.swap_remove_full(&key).is_none());
1518        }
1519        println!("{:?}", map);
1520        for &key in &remove {
1521            //println!("{:?}", map);
1522            let index = map.get_full(&key).unwrap().0;
1523            assert_eq!(map.swap_remove_full(&key), Some((index, key, key)));
1524        }
1525        println!("{:?}", map);
1526
1527        for key in &insert {
1528            assert_eq!(map.get(key).is_some(), !remove.contains(key));
1529        }
1530        assert_eq!(map.len(), insert.len() - remove.len());
1531        assert_eq!(map.keys().count(), insert.len() - remove.len());
1532    }
1533
1534    #[test]
1535    fn remove_to_empty() {
1536        let mut map = indexmap! { 0 => 0, 4 => 4, 5 => 5 };
1537        map.swap_remove(&5).unwrap();
1538        map.swap_remove(&4).unwrap();
1539        map.swap_remove(&0).unwrap();
1540        assert!(map.is_empty());
1541    }
1542
1543    #[test]
1544    fn swap_remove_index() {
1545        let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
1546        let mut map = IndexMap::new();
1547
1548        for &elt in &insert {
1549            map.insert(elt, elt * 2);
1550        }
1551
1552        let mut vector = insert.to_vec();
1553        let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1];
1554
1555        // check that the same swap remove sequence on vec and map
1556        // have the same result.
1557        for &rm in remove_sequence {
1558            let out_vec = vector.swap_remove(rm);
1559            let (out_map, _) = map.swap_remove_index(rm).unwrap();
1560            assert_eq!(out_vec, out_map);
1561        }
1562        assert_eq!(vector.len(), map.len());
1563        for (a, b) in vector.iter().zip(map.keys()) {
1564            assert_eq!(a, b);
1565        }
1566    }
1567
1568    #[test]
1569    fn partial_eq_and_eq() {
1570        let mut map_a = IndexMap::new();
1571        map_a.insert(1, "1");
1572        map_a.insert(2, "2");
1573        let mut map_b = map_a.clone();
1574        assert_eq!(map_a, map_b);
1575        map_b.swap_remove(&1);
1576        assert_ne!(map_a, map_b);
1577
1578        let map_c: IndexMap<_, String> = map_b.into_iter().map(|(k, v)| (k, v.into())).collect();
1579        assert_ne!(map_a, map_c);
1580        assert_ne!(map_c, map_a);
1581    }
1582
1583    #[test]
1584    fn extend() {
1585        let mut map = IndexMap::new();
1586        map.extend(vec![(&1, &2), (&3, &4)]);
1587        map.extend(vec![(5, 6)]);
1588        assert_eq!(
1589            map.into_iter().collect::<Vec<_>>(),
1590            vec![(1, 2), (3, 4), (5, 6)]
1591        );
1592    }
1593
1594    #[test]
1595    fn entry() {
1596        let mut map = IndexMap::new();
1597
1598        map.insert(1, "1");
1599        map.insert(2, "2");
1600        {
1601            let e = map.entry(3);
1602            assert_eq!(e.index(), 2);
1603            let e = e.or_insert("3");
1604            assert_eq!(e, &"3");
1605        }
1606
1607        let e = map.entry(2);
1608        assert_eq!(e.index(), 1);
1609        assert_eq!(e.key(), &2);
1610        match e {
1611            Entry::Occupied(ref e) => assert_eq!(e.get(), &"2"),
1612            Entry::Vacant(_) => panic!(),
1613        }
1614        assert_eq!(e.or_insert("4"), &"2");
1615    }
1616
1617    #[test]
1618    fn entry_and_modify() {
1619        let mut map = IndexMap::new();
1620
1621        map.insert(1, "1");
1622        map.entry(1).and_modify(|x| *x = "2");
1623        assert_eq!(Some(&"2"), map.get(&1));
1624
1625        map.entry(2).and_modify(|x| *x = "doesn't exist");
1626        assert_eq!(None, map.get(&2));
1627    }
1628
1629    #[test]
1630    fn entry_or_default() {
1631        let mut map = IndexMap::new();
1632
1633        #[derive(Debug, PartialEq)]
1634        enum TestEnum {
1635            DefaultValue,
1636            NonDefaultValue,
1637        }
1638
1639        impl Default for TestEnum {
1640            fn default() -> Self {
1641                TestEnum::DefaultValue
1642            }
1643        }
1644
1645        map.insert(1, TestEnum::NonDefaultValue);
1646        assert_eq!(&mut TestEnum::NonDefaultValue, map.entry(1).or_default());
1647
1648        assert_eq!(&mut TestEnum::DefaultValue, map.entry(2).or_default());
1649    }
1650
1651    #[test]
1652    fn keys() {
1653        let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1654        let map: IndexMap<_, _> = vec.into_iter().collect();
1655        let keys: Vec<_> = map.keys().cloned().collect();
1656        assert_eq!(keys.len(), 3);
1657        assert!(keys.contains(&1));
1658        assert!(keys.contains(&2));
1659        assert!(keys.contains(&3));
1660    }
1661
1662    #[test]
1663    fn values() {
1664        let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1665        let map: IndexMap<_, _> = vec.into_iter().collect();
1666        let values: Vec<_> = map.values().cloned().collect();
1667        assert_eq!(values.len(), 3);
1668        assert!(values.contains(&'a'));
1669        assert!(values.contains(&'b'));
1670        assert!(values.contains(&'c'));
1671    }
1672
1673    #[test]
1674    fn values_mut() {
1675        let vec = vec![(1, 1), (2, 2), (3, 3)];
1676        let mut map: IndexMap<_, _> = vec.into_iter().collect();
1677        for value in map.values_mut() {
1678            *value *= 2
1679        }
1680        let values: Vec<_> = map.values().cloned().collect();
1681        assert_eq!(values.len(), 3);
1682        assert!(values.contains(&2));
1683        assert!(values.contains(&4));
1684        assert!(values.contains(&6));
1685    }
1686}
indexmap/map.rs

indexmap/
map.rs
