diff options
Diffstat (limited to '')
| -rw-r--r-- | vendor/indexmap/src/map.rs | 1223 |
1 files changed, 1223 insertions, 0 deletions
diff --git a/vendor/indexmap/src/map.rs b/vendor/indexmap/src/map.rs new file mode 100644 index 0000000..cb405ca --- /dev/null +++ b/vendor/indexmap/src/map.rs @@ -0,0 +1,1223 @@ +//! `IndexMap` is a hash table where the iteration order of the key-value +//! pairs is independent of the hash values of the keys. + +mod core; +mod iter; +mod slice; + +#[cfg(feature = "serde")] +#[cfg_attr(docsrs, doc(cfg(feature = "serde")))] +pub mod serde_seq; + +#[cfg(test)] +mod tests; + +pub use self::core::{Entry, OccupiedEntry, VacantEntry}; +pub use self::iter::{ + Drain, IntoIter, IntoKeys, IntoValues, Iter, IterMut, Keys, Values, ValuesMut, +}; +pub use self::slice::Slice; +pub use crate::mutable_keys::MutableKeys; + +#[cfg(feature = "rayon")] +pub use crate::rayon::map as rayon; + +use ::core::cmp::Ordering; +use ::core::fmt; +use ::core::hash::{BuildHasher, Hash, Hasher}; +use ::core::ops::{Index, IndexMut, RangeBounds}; +use alloc::boxed::Box; +use alloc::vec::Vec; + +#[cfg(feature = "std")] +use std::collections::hash_map::RandomState; + +use self::core::IndexMapCore; +use crate::util::{third, try_simplify_range}; +use crate::{Bucket, Entries, Equivalent, HashValue, TryReserveError}; + +/// A hash table where the iteration order of the key-value pairs is independent +/// of the hash values of the keys. +/// +/// The interface is closely compatible with the standard `HashMap`, but also +/// has additional features. +/// +/// # Order +/// +/// The key-value pairs have a consistent order that is determined by +/// the sequence of insertion and removal calls on the map. The order does +/// not depend on the keys or the hash function at all. +/// +/// All iterators traverse the map in *the order*. +/// +/// The insertion order is preserved, with **notable exceptions** like the +/// `.remove()` or `.swap_remove()` methods. Methods such as `.sort_by()` of +/// course result in a new order, depending on the sorting order. +/// +/// # Indices +/// +/// The key-value pairs are indexed in a compact range without holes in the +/// range `0..self.len()`. For example, the method `.get_full` looks up the +/// index for a key, and the method `.get_index` looks up the key-value pair by +/// index. +/// +/// # Examples +/// +/// ``` +/// use indexmap::IndexMap; +/// +/// // count the frequency of each letter in a sentence. +/// let mut letters = IndexMap::new(); +/// for ch in "a short treatise on fungi".chars() { +/// *letters.entry(ch).or_insert(0) += 1; +/// } +/// +/// assert_eq!(letters[&'s'], 2); +/// assert_eq!(letters[&'t'], 3); +/// assert_eq!(letters[&'u'], 1); +/// assert_eq!(letters.get(&'y'), None); +/// ``` +#[cfg(feature = "std")] +pub struct IndexMap<K, V, S = RandomState> { + pub(crate) core: IndexMapCore<K, V>, + hash_builder: S, +} +#[cfg(not(feature = "std"))] +pub struct IndexMap<K, V, S> { + pub(crate) core: IndexMapCore<K, V>, + hash_builder: S, +} + +impl<K, V, S> Clone for IndexMap<K, V, S> +where + K: Clone, + V: Clone, + S: Clone, +{ + fn clone(&self) -> Self { + IndexMap { + core: self.core.clone(), + hash_builder: self.hash_builder.clone(), + } + } + + fn clone_from(&mut self, other: &Self) { + self.core.clone_from(&other.core); + self.hash_builder.clone_from(&other.hash_builder); + } +} + +impl<K, V, S> Entries for IndexMap<K, V, S> { + type Entry = Bucket<K, V>; + + #[inline] + fn into_entries(self) -> Vec<Self::Entry> { + self.core.into_entries() + } + + #[inline] + fn as_entries(&self) -> &[Self::Entry] { + self.core.as_entries() + } + + #[inline] + fn as_entries_mut(&mut self) -> &mut [Self::Entry] { + self.core.as_entries_mut() + } + + fn with_entries<F>(&mut self, f: F) + where + F: FnOnce(&mut [Self::Entry]), + { + self.core.with_entries(f); + } +} + +impl<K, V, S> fmt::Debug for IndexMap<K, V, S> +where + K: fmt::Debug, + V: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + if cfg!(not(feature = "test_debug")) { + f.debug_map().entries(self.iter()).finish() + } else { + // Let the inner `IndexMapCore` print all of its details + f.debug_struct("IndexMap") + .field("core", &self.core) + .finish() + } + } +} + +#[cfg(feature = "std")] +#[cfg_attr(docsrs, doc(cfg(feature = "std")))] +impl<K, V> IndexMap<K, V> { + /// Create a new map. (Does not allocate.) + #[inline] + pub fn new() -> Self { + Self::with_capacity(0) + } + + /// Create a new map with capacity for `n` key-value pairs. (Does not + /// allocate if `n` is zero.) + /// + /// Computes in **O(n)** time. + #[inline] + pub fn with_capacity(n: usize) -> Self { + Self::with_capacity_and_hasher(n, <_>::default()) + } +} + +impl<K, V, S> IndexMap<K, V, S> { + /// Create a new map with capacity for `n` key-value pairs. (Does not + /// allocate if `n` is zero.) + /// + /// Computes in **O(n)** time. + #[inline] + pub fn with_capacity_and_hasher(n: usize, hash_builder: S) -> Self { + if n == 0 { + Self::with_hasher(hash_builder) + } else { + IndexMap { + core: IndexMapCore::with_capacity(n), + hash_builder, + } + } + } + + /// Create a new map with `hash_builder`. + /// + /// This function is `const`, so it + /// can be called in `static` contexts. + pub const fn with_hasher(hash_builder: S) -> Self { + IndexMap { + core: IndexMapCore::new(), + hash_builder, + } + } + + /// Return the number of elements the map can hold without reallocating. + /// + /// This number is a lower bound; the map might be able to hold more, + /// but is guaranteed to be able to hold at least this many. + /// + /// Computes in **O(1)** time. + pub fn capacity(&self) -> usize { + self.core.capacity() + } + + /// Return a reference to the map's `BuildHasher`. + pub fn hasher(&self) -> &S { + &self.hash_builder + } + + /// Return the number of key-value pairs in the map. + /// + /// Computes in **O(1)** time. + #[inline] + pub fn len(&self) -> usize { + self.core.len() + } + + /// Returns true if the map contains no elements. + /// + /// Computes in **O(1)** time. + #[inline] + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// Return an iterator over the key-value pairs of the map, in their order + pub fn iter(&self) -> Iter<'_, K, V> { + Iter::new(self.as_entries()) + } + + /// Return an iterator over the key-value pairs of the map, in their order + pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { + IterMut::new(self.as_entries_mut()) + } + + /// Return an iterator over the keys of the map, in their order + pub fn keys(&self) -> Keys<'_, K, V> { + Keys::new(self.as_entries()) + } + + /// Return an owning iterator over the keys of the map, in their order + pub fn into_keys(self) -> IntoKeys<K, V> { + IntoKeys::new(self.into_entries()) + } + + /// Return an iterator over the values of the map, in their order + pub fn values(&self) -> Values<'_, K, V> { + Values::new(self.as_entries()) + } + + /// Return an iterator over mutable references to the values of the map, + /// in their order + pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> { + ValuesMut::new(self.as_entries_mut()) + } + + /// Return an owning iterator over the values of the map, in their order + pub fn into_values(self) -> IntoValues<K, V> { + IntoValues::new(self.into_entries()) + } + + /// Remove all key-value pairs in the map, while preserving its capacity. + /// + /// Computes in **O(n)** time. + pub fn clear(&mut self) { + self.core.clear(); + } + + /// Shortens the map, keeping the first `len` elements and dropping the rest. + /// + /// If `len` is greater than the map's current length, this has no effect. + pub fn truncate(&mut self, len: usize) { + self.core.truncate(len); + } + + /// Clears the `IndexMap` in the given index range, returning those + /// key-value pairs as a drain iterator. + /// + /// The range may be any type that implements `RangeBounds<usize>`, + /// including all of the `std::ops::Range*` types, or even a tuple pair of + /// `Bound` start and end values. To drain the map entirely, use `RangeFull` + /// like `map.drain(..)`. + /// + /// This shifts down all entries following the drained range to fill the + /// gap, and keeps the allocated memory for reuse. + /// + /// ***Panics*** if the starting point is greater than the end point or if + /// the end point is greater than the length of the map. + pub fn drain<R>(&mut self, range: R) -> Drain<'_, K, V> + where + R: RangeBounds<usize>, + { + Drain::new(self.core.drain(range)) + } + + /// Splits the collection into two at the given index. + /// + /// Returns a newly allocated map containing the elements in the range + /// `[at, len)`. After the call, the original map will be left containing + /// the elements `[0, at)` with its previous capacity unchanged. + /// + /// ***Panics*** if `at > len`. + pub fn split_off(&mut self, at: usize) -> Self + where + S: Clone, + { + Self { + core: self.core.split_off(at), + hash_builder: self.hash_builder.clone(), + } + } +} + +impl<K, V, S> IndexMap<K, V, S> +where + K: Hash + Eq, + S: BuildHasher, +{ + /// Reserve capacity for `additional` more key-value pairs. + /// + /// Computes in **O(n)** time. + pub fn reserve(&mut self, additional: usize) { + self.core.reserve(additional); + } + + /// Reserve capacity for `additional` more key-value pairs, without over-allocating. + /// + /// Unlike `reserve`, this does not deliberately over-allocate the entry capacity to avoid + /// frequent re-allocations. However, the underlying data structures may still have internal + /// capacity requirements, and the allocator itself may give more space than requested, so this + /// cannot be relied upon to be precisely minimal. + /// + /// Computes in **O(n)** time. + pub fn reserve_exact(&mut self, additional: usize) { + self.core.reserve_exact(additional); + } + + /// Try to reserve capacity for `additional` more key-value pairs. + /// + /// Computes in **O(n)** time. + pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.core.try_reserve(additional) + } + + /// Try to reserve capacity for `additional` more key-value pairs, without over-allocating. + /// + /// Unlike `try_reserve`, this does not deliberately over-allocate the entry capacity to avoid + /// frequent re-allocations. However, the underlying data structures may still have internal + /// capacity requirements, and the allocator itself may give more space than requested, so this + /// cannot be relied upon to be precisely minimal. + /// + /// Computes in **O(n)** time. + pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.core.try_reserve_exact(additional) + } + + /// Shrink the capacity of the map as much as possible. + /// + /// Computes in **O(n)** time. + pub fn shrink_to_fit(&mut self) { + self.core.shrink_to(0); + } + + /// Shrink the capacity of the map with a lower limit. + /// + /// Computes in **O(n)** time. + pub fn shrink_to(&mut self, min_capacity: usize) { + self.core.shrink_to(min_capacity); + } + + fn hash<Q: ?Sized + Hash>(&self, key: &Q) -> HashValue { + let mut h = self.hash_builder.build_hasher(); + key.hash(&mut h); + HashValue(h.finish() as usize) + } + + /// Insert a key-value pair in the map. + /// + /// If an equivalent key already exists in the map: the key remains and + /// retains in its place in the order, its corresponding value is updated + /// with `value` and the older value is returned inside `Some(_)`. + /// + /// If no equivalent key existed in the map: the new key-value pair is + /// inserted, last in order, and `None` is returned. + /// + /// Computes in **O(1)** time (amortized average). + /// + /// See also [`entry`](#method.entry) if you you want to insert *or* modify + /// or if you need to get the index of the corresponding key-value pair. + pub fn insert(&mut self, key: K, value: V) -> Option<V> { + self.insert_full(key, value).1 + } + + /// Insert a key-value pair in the map, and get their index. + /// + /// If an equivalent key already exists in the map: the key remains and + /// retains in its place in the order, its corresponding value is updated + /// with `value` and the older value is returned inside `(index, Some(_))`. + /// + /// If no equivalent key existed in the map: the new key-value pair is + /// inserted, last in order, and `(index, None)` is returned. + /// + /// Computes in **O(1)** time (amortized average). + /// + /// See also [`entry`](#method.entry) if you you want to insert *or* modify + /// or if you need to get the index of the corresponding key-value pair. + pub fn insert_full(&mut self, key: K, value: V) -> (usize, Option<V>) { + let hash = self.hash(&key); + self.core.insert_full(hash, key, value) + } + + /// Get the given key’s corresponding entry in the map for insertion and/or + /// in-place manipulation. + /// + /// Computes in **O(1)** time (amortized average). + pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { + let hash = self.hash(&key); + self.core.entry(hash, key) + } + + /// Return `true` if an equivalent to `key` exists in the map. + /// + /// Computes in **O(1)** time (average). + pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool + where + Q: Hash + Equivalent<K>, + { + self.get_index_of(key).is_some() + } + + /// Return a reference to the value stored for `key`, if it is present, + /// else `None`. + /// + /// Computes in **O(1)** time (average). + pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> + where + Q: Hash + Equivalent<K>, + { + if let Some(i) = self.get_index_of(key) { + let entry = &self.as_entries()[i]; + Some(&entry.value) + } else { + None + } + } + + /// Return references to the key-value pair stored for `key`, + /// if it is present, else `None`. + /// + /// Computes in **O(1)** time (average). + pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)> + where + Q: Hash + Equivalent<K>, + { + if let Some(i) = self.get_index_of(key) { + let entry = &self.as_entries()[i]; + Some((&entry.key, &entry.value)) + } else { + None + } + } + + /// Return item index, key and value + pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)> + where + Q: Hash + Equivalent<K>, + { + if let Some(i) = self.get_index_of(key) { + let entry = &self.as_entries()[i]; + Some((i, &entry.key, &entry.value)) + } else { + None + } + } + + /// Return item index, if it exists in the map + /// + /// Computes in **O(1)** time (average). + pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize> + where + Q: Hash + Equivalent<K>, + { + if self.is_empty() { + None + } else { + let hash = self.hash(key); + self.core.get_index_of(hash, key) + } + } + + pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> + where + Q: Hash + Equivalent<K>, + { + if let Some(i) = self.get_index_of(key) { + let entry = &mut self.as_entries_mut()[i]; + Some(&mut entry.value) + } else { + None + } + } + + pub fn get_full_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &K, &mut V)> + where + Q: Hash + Equivalent<K>, + { + if let Some(i) = self.get_index_of(key) { + let entry = &mut self.as_entries_mut()[i]; + Some((i, &entry.key, &mut entry.value)) + } else { + None + } + } + + /// Remove the key-value pair equivalent to `key` and return + /// its value. + /// + /// **NOTE:** This is equivalent to `.swap_remove(key)`, if you need to + /// preserve the order of the keys in the map, use `.shift_remove(key)` + /// instead. + /// + /// Computes in **O(1)** time (average). + pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> + where + Q: Hash + Equivalent<K>, + { + self.swap_remove(key) + } + + /// Remove and return the key-value pair equivalent to `key`. + /// + /// **NOTE:** This is equivalent to `.swap_remove_entry(key)`, if you need to + /// preserve the order of the keys in the map, use `.shift_remove_entry(key)` + /// instead. + /// + /// Computes in **O(1)** time (average). + pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> + where + Q: Hash + Equivalent<K>, + { + self.swap_remove_entry(key) + } + + /// Remove the key-value pair equivalent to `key` and return + /// its value. + /// + /// Like `Vec::swap_remove`, the pair is removed by swapping it with the + /// last element of the map and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Return `None` if `key` is not in map. + /// + /// Computes in **O(1)** time (average). + pub fn swap_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> + where + Q: Hash + Equivalent<K>, + { + self.swap_remove_full(key).map(third) + } + + /// Remove and return the key-value pair equivalent to `key`. + /// + /// Like `Vec::swap_remove`, the pair is removed by swapping it with the + /// last element of the map and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Return `None` if `key` is not in map. + /// + /// Computes in **O(1)** time (average). + pub fn swap_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> + where + Q: Hash + Equivalent<K>, + { + match self.swap_remove_full(key) { + Some((_, key, value)) => Some((key, value)), + None => None, + } + } + + /// Remove the key-value pair equivalent to `key` and return it and + /// the index it had. + /// + /// Like `Vec::swap_remove`, the pair is removed by swapping it with the + /// last element of the map and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Return `None` if `key` is not in map. + /// + /// Computes in **O(1)** time (average). + pub fn swap_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> + where + Q: Hash + Equivalent<K>, + { + if self.is_empty() { + return None; + } + let hash = self.hash(key); + self.core.swap_remove_full(hash, key) + } + + /// Remove the key-value pair equivalent to `key` and return + /// its value. + /// + /// Like `Vec::remove`, the pair is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Return `None` if `key` is not in map. + /// + /// Computes in **O(n)** time (average). + pub fn shift_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> + where + Q: Hash + Equivalent<K>, + { + self.shift_remove_full(key).map(third) + } + + /// Remove and return the key-value pair equivalent to `key`. + /// + /// Like `Vec::remove`, the pair is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Return `None` if `key` is not in map. + /// + /// Computes in **O(n)** time (average). + pub fn shift_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> + where + Q: Hash + Equivalent<K>, + { + match self.shift_remove_full(key) { + Some((_, key, value)) => Some((key, value)), + None => None, + } + } + + /// Remove the key-value pair equivalent to `key` and return it and + /// the index it had. + /// + /// Like `Vec::remove`, the pair is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Return `None` if `key` is not in map. + /// + /// Computes in **O(n)** time (average). + pub fn shift_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> + where + Q: Hash + Equivalent<K>, + { + if self.is_empty() { + return None; + } + let hash = self.hash(key); + self.core.shift_remove_full(hash, key) + } + + /// Remove the last key-value pair + /// + /// This preserves the order of the remaining elements. + /// + /// Computes in **O(1)** time (average). + pub fn pop(&mut self) -> Option<(K, V)> { + self.core.pop() + } + + /// Scan through each key-value pair in the map and keep those where the + /// closure `keep` returns `true`. + /// + /// The elements are visited in order, and remaining elements keep their + /// order. + /// + /// Computes in **O(n)** time (average). + pub fn retain<F>(&mut self, mut keep: F) + where + F: FnMut(&K, &mut V) -> bool, + { + self.core.retain_in_order(move |k, v| keep(k, v)); + } + + pub(crate) fn retain_mut<F>(&mut self, keep: F) + where + F: FnMut(&mut K, &mut V) -> bool, + { + self.core.retain_in_order(keep); + } + + /// Sort the map’s key-value pairs by the default ordering of the keys. + /// + /// See [`sort_by`](Self::sort_by) for details. + pub fn sort_keys(&mut self) + where + K: Ord, + { + self.with_entries(move |entries| { + entries.sort_by(move |a, b| K::cmp(&a.key, &b.key)); + }); + } + + /// Sort the map’s key-value pairs in place using the comparison + /// function `cmp`. + /// + /// The comparison function receives two key and value pairs to compare (you + /// can sort by keys or values or their combination as needed). + /// + /// Computes in **O(n log n + c)** time and **O(n)** space where *n* is + /// the length of the map and *c* the capacity. The sort is stable. + pub fn sort_by<F>(&mut self, mut cmp: F) + where + F: FnMut(&K, &V, &K, &V) -> Ordering, + { + self.with_entries(move |entries| { + entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); + }); + } + + /// Sort the key-value pairs of the map and return a by-value iterator of + /// the key-value pairs with the result. + /// + /// The sort is stable. + pub fn sorted_by<F>(self, mut cmp: F) -> IntoIter<K, V> + where + F: FnMut(&K, &V, &K, &V) -> Ordering, + { + let mut entries = self.into_entries(); + entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); + IntoIter::new(entries) + } + + /// Sort the map's key-value pairs by the default ordering of the keys, but + /// may not preserve the order of equal elements. + /// + /// See [`sort_unstable_by`](Self::sort_unstable_by) for details. + pub fn sort_unstable_keys(&mut self) + where + K: Ord, + { + self.with_entries(move |entries| { + entries.sort_unstable_by(move |a, b| K::cmp(&a.key, &b.key)); + }); + } + + /// Sort the map's key-value pairs in place using the comparison function `cmp`, but + /// may not preserve the order of equal elements. + /// + /// The comparison function receives two key and value pairs to compare (you + /// can sort by keys or values or their combination as needed). + /// + /// Computes in **O(n log n + c)** time where *n* is + /// the length of the map and *c* is the capacity. The sort is unstable. + pub fn sort_unstable_by<F>(&mut self, mut cmp: F) + where + F: FnMut(&K, &V, &K, &V) -> Ordering, + { + self.with_entries(move |entries| { + entries.sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); + }); + } + + /// Sort the key-value pairs of the map and return a by-value iterator of + /// the key-value pairs with the result. + /// + /// The sort is unstable. + #[inline] + pub fn sorted_unstable_by<F>(self, mut cmp: F) -> IntoIter<K, V> + where + F: FnMut(&K, &V, &K, &V) -> Ordering, + { + let mut entries = self.into_entries(); + entries.sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); + IntoIter::new(entries) + } + + /// Sort the map’s key-value pairs in place using a sort-key extraction function. + /// + /// During sorting, the function is called at most once per entry, by using temporary storage + /// to remember the results of its evaluation. The order of calls to the function is + /// unspecified and may change between versions of `indexmap` or the standard library. + /// + /// Computes in **O(m n + n log n + c)** time () and **O(n)** space, where the function is + /// **O(m)**, *n* is the length of the map, and *c* the capacity. The sort is stable. + pub fn sort_by_cached_key<T, F>(&mut self, mut sort_key: F) + where + T: Ord, + F: FnMut(&K, &V) -> T, + { + self.with_entries(move |entries| { + entries.sort_by_cached_key(move |a| sort_key(&a.key, &a.value)); + }); + } + + /// Reverses the order of the map’s key-value pairs in place. + /// + /// Computes in **O(n)** time and **O(1)** space. + pub fn reverse(&mut self) { + self.core.reverse() + } +} + +impl<K, V, S> IndexMap<K, V, S> { + /// Returns a slice of all the key-value pairs in the map. + /// + /// Computes in **O(1)** time. + pub fn as_slice(&self) -> &Slice<K, V> { + Slice::from_slice(self.as_entries()) + } + + /// Returns a mutable slice of all the key-value pairs in the map. + /// + /// Computes in **O(1)** time. + pub fn as_mut_slice(&mut self) -> &mut Slice<K, V> { + Slice::from_mut_slice(self.as_entries_mut()) + } + + /// Converts into a boxed slice of all the key-value pairs in the map. + /// + /// Note that this will drop the inner hash table and any excess capacity. + pub fn into_boxed_slice(self) -> Box<Slice<K, V>> { + Slice::from_boxed(self.into_entries().into_boxed_slice()) + } + + /// Get a key-value pair by index + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Computes in **O(1)** time. + pub fn get_index(&self, index: usize) -> Option<(&K, &V)> { + self.as_entries().get(index).map(Bucket::refs) + } + + /// Get a key-value pair by index + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Computes in **O(1)** time. + pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> { + self.as_entries_mut().get_mut(index).map(Bucket::ref_mut) + } + + /// Returns a slice of key-value pairs in the given range of indices. + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Computes in **O(1)** time. + pub fn get_range<R: RangeBounds<usize>>(&self, range: R) -> Option<&Slice<K, V>> { + let entries = self.as_entries(); + let range = try_simplify_range(range, entries.len())?; + entries.get(range).map(Slice::from_slice) + } + + /// Returns a mutable slice of key-value pairs in the given range of indices. + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Computes in **O(1)** time. + pub fn get_range_mut<R: RangeBounds<usize>>(&mut self, range: R) -> Option<&mut Slice<K, V>> { + let entries = self.as_entries_mut(); + let range = try_simplify_range(range, entries.len())?; + entries.get_mut(range).map(Slice::from_mut_slice) + } + + /// Get the first key-value pair + /// + /// Computes in **O(1)** time. + pub fn first(&self) -> Option<(&K, &V)> { + self.as_entries().first().map(Bucket::refs) + } + + /// Get the first key-value pair, with mutable access to the value + /// + /// Computes in **O(1)** time. + pub fn first_mut(&mut self) -> Option<(&K, &mut V)> { + self.as_entries_mut().first_mut().map(Bucket::ref_mut) + } + + /// Get the last key-value pair + /// + /// Computes in **O(1)** time. + pub fn last(&self) -> Option<(&K, &V)> { + self.as_entries().last().map(Bucket::refs) + } + + /// Get the last key-value pair, with mutable access to the value + /// + /// Computes in **O(1)** time. + pub fn last_mut(&mut self) -> Option<(&K, &mut V)> { + self.as_entries_mut().last_mut().map(Bucket::ref_mut) + } + + /// Remove the key-value pair by index + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Like `Vec::swap_remove`, the pair is removed by swapping it with the + /// last element of the map and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Computes in **O(1)** time (average). + pub fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> { + self.core.swap_remove_index(index) + } + + /// Remove the key-value pair by index + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Like `Vec::remove`, the pair is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Computes in **O(n)** time (average). + pub fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> { + self.core.shift_remove_index(index) + } + + /// Moves the position of a key-value pair from one index to another + /// by shifting all other pairs in-between. + /// + /// * If `from < to`, the other pairs will shift down while the targeted pair moves up. + /// * If `from > to`, the other pairs will shift up while the targeted pair moves down. + /// + /// ***Panics*** if `from` or `to` are out of bounds. + /// + /// Computes in **O(n)** time (average). + pub fn move_index(&mut self, from: usize, to: usize) { + self.core.move_index(from, to) + } + + /// Swaps the position of two key-value pairs in the map. + /// + /// ***Panics*** if `a` or `b` are out of bounds. + pub fn swap_indices(&mut self, a: usize, b: usize) { + self.core.swap_indices(a, b) + } +} + +/// Access `IndexMap` values corresponding to a key. +/// +/// # Examples +/// +/// ``` +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// for word in "Lorem ipsum dolor sit amet".split_whitespace() { +/// map.insert(word.to_lowercase(), word.to_uppercase()); +/// } +/// assert_eq!(map["lorem"], "LOREM"); +/// assert_eq!(map["ipsum"], "IPSUM"); +/// ``` +/// +/// ```should_panic +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// map.insert("foo", 1); +/// println!("{:?}", map["bar"]); // panics! +/// ``` +impl<K, V, Q: ?Sized, S> Index<&Q> for IndexMap<K, V, S> +where + Q: Hash + Equivalent<K>, + K: Hash + Eq, + S: BuildHasher, +{ + type Output = V; + + /// Returns a reference to the value corresponding to the supplied `key`. + /// + /// ***Panics*** if `key` is not present in the map. + fn index(&self, key: &Q) -> &V { + self.get(key).expect("IndexMap: key not found") + } +} + +/// Access `IndexMap` values corresponding to a key. +/// +/// Mutable indexing allows changing / updating values of key-value +/// pairs that are already present. +/// +/// You can **not** insert new pairs with index syntax, use `.insert()`. +/// +/// # Examples +/// +/// ``` +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// for word in "Lorem ipsum dolor sit amet".split_whitespace() { +/// map.insert(word.to_lowercase(), word.to_string()); +/// } +/// let lorem = &mut map["lorem"]; +/// assert_eq!(lorem, "Lorem"); +/// lorem.retain(char::is_lowercase); +/// assert_eq!(map["lorem"], "orem"); +/// ``` +/// +/// ```should_panic +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// map.insert("foo", 1); +/// map["bar"] = 1; // panics! +/// ``` +impl<K, V, Q: ?Sized, S> IndexMut<&Q> for IndexMap<K, V, S> +where + Q: Hash + Equivalent<K>, + K: Hash + Eq, + S: BuildHasher, +{ + /// Returns a mutable reference to the value corresponding to the supplied `key`. + /// + /// ***Panics*** if `key` is not present in the map. + fn index_mut(&mut self, key: &Q) -> &mut V { + self.get_mut(key).expect("IndexMap: key not found") + } +} + +/// Access `IndexMap` values at indexed positions. +/// +/// # Examples +/// +/// ``` +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// for word in "Lorem ipsum dolor sit amet".split_whitespace() { +/// map.insert(word.to_lowercase(), word.to_uppercase()); +/// } +/// assert_eq!(map[0], "LOREM"); +/// assert_eq!(map[1], "IPSUM"); +/// map.reverse(); +/// assert_eq!(map[0], "AMET"); +/// assert_eq!(map[1], "SIT"); +/// map.sort_keys(); +/// assert_eq!(map[0], "AMET"); +/// assert_eq!(map[1], "DOLOR"); +/// ``` +/// +/// ```should_panic +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// map.insert("foo", 1); +/// println!("{:?}", map[10]); // panics! +/// ``` +impl<K, V, S> Index<usize> for IndexMap<K, V, S> { + type Output = V; + + /// Returns a reference to the value at the supplied `index`. + /// + /// ***Panics*** if `index` is out of bounds. + fn index(&self, index: usize) -> &V { + self.get_index(index) + .expect("IndexMap: index out of bounds") + .1 + } +} + +/// Access `IndexMap` values at indexed positions. +/// +/// Mutable indexing allows changing / updating indexed values +/// that are already present. +/// +/// You can **not** insert new values with index syntax, use `.insert()`. +/// +/// # Examples +/// +/// ``` +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// for word in "Lorem ipsum dolor sit amet".split_whitespace() { +/// map.insert(word.to_lowercase(), word.to_string()); +/// } +/// let lorem = &mut map[0]; +/// assert_eq!(lorem, "Lorem"); +/// lorem.retain(char::is_lowercase); +/// assert_eq!(map["lorem"], "orem"); +/// ``` +/// +/// ```should_panic +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// map.insert("foo", 1); +/// map[10] = 1; // panics! +/// ``` +impl<K, V, S> IndexMut<usize> for IndexMap<K, V, S> { + /// Returns a mutable reference to the value at the supplied `index`. + /// + /// ***Panics*** if `index` is out of bounds. + fn index_mut(&mut self, index: usize) -> &mut V { + self.get_index_mut(index) + .expect("IndexMap: index out of bounds") + .1 + } +} + +impl<K, V, S> FromIterator<(K, V)> for IndexMap<K, V, S> +where + K: Hash + Eq, + S: BuildHasher + Default, +{ + /// Create an `IndexMap` from the sequence of key-value pairs in the + /// iterable. + /// + /// `from_iter` uses the same logic as `extend`. See + /// [`extend`](#method.extend) for more details. + fn from_iter<I: IntoIterator<Item = (K, V)>>(iterable: I) -> Self { + let iter = iterable.into_iter(); + let (low, _) = iter.size_hint(); + let mut map = Self::with_capacity_and_hasher(low, <_>::default()); + map.extend(iter); + map + } +} + +#[cfg(feature = "std")] +#[cfg_attr(docsrs, doc(cfg(feature = "std")))] +impl<K, V, const N: usize> From<[(K, V); N]> for IndexMap<K, V, RandomState> +where + K: Hash + Eq, +{ + /// # Examples + /// + /// ``` + /// use indexmap::IndexMap; + /// + /// let map1 = IndexMap::from([(1, 2), (3, 4)]); + /// let map2: IndexMap<_, _> = [(1, 2), (3, 4)].into(); + /// assert_eq!(map1, map2); + /// ``` + fn from(arr: [(K, V); N]) -> Self { + Self::from_iter(arr) + } +} + +impl<K, V, S> Extend<(K, V)> for IndexMap<K, V, S> +where + K: Hash + Eq, + S: BuildHasher, +{ + /// Extend the map with all key-value pairs in the iterable. + /// + /// This is equivalent to calling [`insert`](#method.insert) for each of + /// them in order, which means that for keys that already existed + /// in the map, their value is updated but it keeps the existing order. + /// + /// New keys are inserted in the order they appear in the sequence. If + /// equivalents of a key occur more than once, the last corresponding value + /// prevails. + fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iterable: I) { + // (Note: this is a copy of `std`/`hashbrown`'s reservation logic.) + // Keys may be already present or show multiple times in the iterator. + // Reserve the entire hint lower bound if the map is empty. + // Otherwise reserve half the hint (rounded up), so the map + // will only resize twice in the worst case. + let iter = iterable.into_iter(); + let reserve = if self.is_empty() { + iter.size_hint().0 + } else { + (iter.size_hint().0 + 1) / 2 + }; + self.reserve(reserve); + iter.for_each(move |(k, v)| { + self.insert(k, v); + }); + } +} + +impl<'a, K, V, S> Extend<(&'a K, &'a V)> for IndexMap<K, V, S> +where + K: Hash + Eq + Copy, + V: Copy, + S: BuildHasher, +{ + /// Extend the map with all key-value pairs in the iterable. + /// + /// See the first extend method for more details. + fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iterable: I) { + self.extend(iterable.into_iter().map(|(&key, &value)| (key, value))); + } +} + +impl<K, V, S> Default for IndexMap<K, V, S> +where + S: Default, +{ + /// Return an empty `IndexMap` + fn default() -> Self { + Self::with_capacity_and_hasher(0, S::default()) + } +} + +impl<K, V1, S1, V2, S2> PartialEq<IndexMap<K, V2, S2>> for IndexMap<K, V1, S1> +where + K: Hash + Eq, + V1: PartialEq<V2>, + S1: BuildHasher, + S2: BuildHasher, +{ + fn eq(&self, other: &IndexMap<K, V2, S2>) -> bool { + if self.len() != other.len() { + return false; + } + + self.iter() + .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v)) + } +} + +impl<K, V, S> Eq for IndexMap<K, V, S> +where + K: Eq + Hash, + V: Eq, + S: BuildHasher, +{ +} |