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

indexmap_amortized/
map.rs
