diff options
Diffstat (limited to 'vendor/indexmap/src/set.rs')
| -rw-r--r-- | vendor/indexmap/src/set.rs | 1121 |
1 files changed, 110 insertions, 1011 deletions
diff --git a/vendor/indexmap/src/set.rs b/vendor/indexmap/src/set.rs index 372894742..dbee481f1 100644 --- a/vendor/indexmap/src/set.rs +++ b/vendor/indexmap/src/set.rs @@ -1,18 +1,28 @@ //! A hash set implemented using `IndexMap` +mod iter; +mod slice; + +#[cfg(test)] +mod tests; + +pub use self::iter::{Difference, Drain, Intersection, IntoIter, Iter, SymmetricDifference, Union}; +pub use self::slice::Slice; + #[cfg(feature = "rayon")] pub use crate::rayon::set as rayon; +use crate::TryReserveError; -#[cfg(has_std)] +#[cfg(feature = "std")] use std::collections::hash_map::RandomState; -use crate::vec::{self, Vec}; +use crate::util::try_simplify_range; +use alloc::boxed::Box; +use alloc::vec::Vec; use core::cmp::Ordering; use core::fmt; use core::hash::{BuildHasher, Hash}; -use core::iter::{Chain, FusedIterator}; use core::ops::{BitAnd, BitOr, BitXor, Index, RangeBounds, Sub}; -use core::slice; use super::{Entries, Equivalent, IndexMap}; @@ -59,11 +69,11 @@ type Bucket<T> = super::Bucket<T, ()>; /// assert!(letters.contains(&'u')); /// assert!(!letters.contains(&'y')); /// ``` -#[cfg(has_std)] +#[cfg(feature = "std")] pub struct IndexSet<T, S = RandomState> { pub(crate) map: IndexMap<T, (), S>, } -#[cfg(not(has_std))] +#[cfg(not(feature = "std"))] pub struct IndexSet<T, S> { pub(crate) map: IndexMap<T, (), S>, } @@ -124,7 +134,8 @@ where } } -#[cfg(has_std)] +#[cfg(feature = "std")] +#[cfg_attr(docsrs, doc(cfg(feature = "std")))] impl<T> IndexSet<T> { /// Create a new set. (Does not allocate.) pub fn new() -> Self { @@ -165,6 +176,11 @@ impl<T, S> IndexSet<T, S> { } } + /// Return the number of elements the set can hold without reallocating. + /// + /// This number is a lower bound; the set 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.map.capacity() @@ -191,9 +207,7 @@ impl<T, S> IndexSet<T, S> { /// Return an iterator over the values of the set, in their order pub fn iter(&self) -> Iter<'_, T> { - Iter { - iter: self.map.as_entries().iter(), - } + Iter::new(self.as_entries()) } /// Remove all elements in the set, while preserving its capacity. @@ -227,9 +241,7 @@ impl<T, S> IndexSet<T, S> { where R: RangeBounds<usize>, { - Drain { - iter: self.map.drain(range).iter, - } + Drain::new(self.map.core.drain(range)) } /// Splits the collection into two at the given index. @@ -261,6 +273,37 @@ where self.map.reserve(additional); } + /// Reserve capacity for `additional` more values, 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.map.reserve_exact(additional); + } + + /// Try to reserve capacity for `additional` more values. + /// + /// Computes in **O(n)** time. + pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.map.try_reserve(additional) + } + + /// Try to reserve capacity for `additional` more values, 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.map.try_reserve_exact(additional) + } + /// Shrink the capacity of the set as much as possible. /// /// Computes in **O(n)** time. @@ -297,16 +340,8 @@ where /// /// Computes in **O(1)** time (amortized average). pub fn insert_full(&mut self, value: T) -> (usize, bool) { - use super::map::Entry::*; - - match self.map.entry(value) { - Occupied(e) => (e.index(), false), - Vacant(e) => { - let index = e.index(); - e.insert(()); - (index, true) - } - } + let (index, existing) = self.map.insert_full(value, ()); + (index, existing.is_none()) } /// Return an iterator over the values that are in `self` but not `other`. @@ -316,10 +351,7 @@ where where S2: BuildHasher, { - Difference { - iter: self.iter(), - other, - } + Difference::new(self, other) } /// Return an iterator over the values that are in `self` or `other`, @@ -334,9 +366,7 @@ where where S2: BuildHasher, { - SymmetricDifference { - iter: self.difference(other).chain(other.difference(self)), - } + SymmetricDifference::new(self, other) } /// Return an iterator over the values that are in both `self` and `other`. @@ -346,10 +376,7 @@ where where S2: BuildHasher, { - Intersection { - iter: self.iter(), - other, - } + Intersection::new(self, other) } /// Return an iterator over all values that are in `self` or `other`. @@ -360,9 +387,7 @@ where where S2: BuildHasher, { - Union { - iter: self.iter().chain(other.difference(self)), - } + Union::new(self, other) } /// Return `true` if an equivalent to `value` exists in the set. @@ -604,9 +629,7 @@ where { let mut entries = self.into_entries(); entries.sort_by(move |a, b| cmp(&a.key, &b.key)); - IntoIter { - iter: entries.into_iter(), - } + IntoIter::new(entries) } /// Sort the set's values by their default ordering. @@ -619,7 +642,7 @@ where self.map.sort_unstable_keys() } - /// Sort the set's values in place using the comparison funtion `cmp`. + /// Sort the set's values in place using the comparison function `cmp`. /// /// Computes in **O(n log n)** time. The sort is unstable. pub fn sort_unstable_by<F>(&mut self, mut cmp: F) @@ -637,9 +660,25 @@ where { let mut entries = self.into_entries(); entries.sort_unstable_by(move |a, b| cmp(&a.key, &b.key)); - IntoIter { - iter: entries.into_iter(), - } + IntoIter::new(entries) + } + + /// Sort the set’s values in place using a 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<K, F>(&mut self, mut sort_key: F) + where + K: Ord, + F: FnMut(&T) -> K, + { + self.with_entries(move |entries| { + entries.sort_by_cached_key(move |a| sort_key(&a.key)); + }); } /// Reverses the order of the set’s values in place. @@ -651,6 +690,20 @@ where } impl<T, S> IndexSet<T, S> { + /// Returns a slice of all the values in the set. + /// + /// Computes in **O(1)** time. + pub fn as_slice(&self) -> &Slice<T> { + Slice::from_slice(self.as_entries()) + } + + /// Converts into a boxed slice of all the values in the set. + /// + /// Note that this will drop the inner hash table and any excess capacity. + pub fn into_boxed_slice(self) -> Box<Slice<T>> { + Slice::from_boxed(self.into_entries().into_boxed_slice()) + } + /// Get a value by index /// /// Valid indices are *0 <= index < self.len()* @@ -660,6 +713,17 @@ impl<T, S> IndexSet<T, S> { self.as_entries().get(index).map(Bucket::key_ref) } + /// Returns a slice of values 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<T>> { + let entries = self.as_entries(); + let range = try_simplify_range(range, entries.len())?; + entries.get(range).map(Slice::from_slice) + } + /// Get the first value /// /// Computes in **O(1)** time. @@ -761,141 +825,6 @@ impl<T, S> Index<usize> for IndexSet<T, S> { } } -/// An owning iterator over the items of a `IndexSet`. -/// -/// This `struct` is created by the [`into_iter`] method on [`IndexSet`] -/// (provided by the `IntoIterator` trait). See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`into_iter`]: struct.IndexSet.html#method.into_iter -pub struct IntoIter<T> { - iter: vec::IntoIter<Bucket<T>>, -} - -impl<T> Iterator for IntoIter<T> { - type Item = T; - - iterator_methods!(Bucket::key); -} - -impl<T> DoubleEndedIterator for IntoIter<T> { - double_ended_iterator_methods!(Bucket::key); -} - -impl<T> ExactSizeIterator for IntoIter<T> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<T> FusedIterator for IntoIter<T> {} - -impl<T: fmt::Debug> fmt::Debug for IntoIter<T> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.iter.as_slice().iter().map(Bucket::key_ref); - f.debug_list().entries(iter).finish() - } -} - -/// An iterator over the items of a `IndexSet`. -/// -/// This `struct` is created by the [`iter`] method on [`IndexSet`]. -/// See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`iter`]: struct.IndexSet.html#method.iter -pub struct Iter<'a, T> { - iter: slice::Iter<'a, Bucket<T>>, -} - -impl<'a, T> Iterator for Iter<'a, T> { - type Item = &'a T; - - iterator_methods!(Bucket::key_ref); -} - -impl<T> DoubleEndedIterator for Iter<'_, T> { - double_ended_iterator_methods!(Bucket::key_ref); -} - -impl<T> ExactSizeIterator for Iter<'_, T> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<T> FusedIterator for Iter<'_, T> {} - -impl<T> Clone for Iter<'_, T> { - fn clone(&self) -> Self { - Iter { - iter: self.iter.clone(), - } - } -} - -impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.clone()).finish() - } -} - -/// A draining iterator over the items of a `IndexSet`. -/// -/// This `struct` is created by the [`drain`] method on [`IndexSet`]. -/// See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`drain`]: struct.IndexSet.html#method.drain -pub struct Drain<'a, T> { - iter: vec::Drain<'a, Bucket<T>>, -} - -impl<T> Iterator for Drain<'_, T> { - type Item = T; - - iterator_methods!(Bucket::key); -} - -impl<T> DoubleEndedIterator for Drain<'_, T> { - double_ended_iterator_methods!(Bucket::key); -} - -impl<T> ExactSizeIterator for Drain<'_, T> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<T> FusedIterator for Drain<'_, T> {} - -impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.iter.as_slice().iter().map(Bucket::key_ref); - f.debug_list().entries(iter).finish() - } -} - -impl<'a, T, S> IntoIterator for &'a IndexSet<T, S> { - type Item = &'a T; - type IntoIter = Iter<'a, T>; - - fn into_iter(self) -> Self::IntoIter { - self.iter() - } -} - -impl<T, S> IntoIterator for IndexSet<T, S> { - type Item = T; - type IntoIter = IntoIter<T>; - - fn into_iter(self) -> Self::IntoIter { - IntoIter { - iter: self.into_entries().into_iter(), - } - } -} - impl<T, S> FromIterator<T> for IndexSet<T, S> where T: Hash + Eq, @@ -909,7 +838,8 @@ where } } -#[cfg(has_std)] +#[cfg(feature = "std")] +#[cfg_attr(docsrs, doc(cfg(feature = "std")))] impl<T, const N: usize> From<[T; N]> for IndexSet<T, RandomState> where T: Eq + Hash, @@ -1014,310 +944,6 @@ where } } -/// A lazy iterator producing elements in the difference of `IndexSet`s. -/// -/// This `struct` is created by the [`difference`] method on [`IndexSet`]. -/// See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`difference`]: struct.IndexSet.html#method.difference -pub struct Difference<'a, T, S> { - iter: Iter<'a, T>, - other: &'a IndexSet<T, S>, -} - -impl<'a, T, S> Iterator for Difference<'a, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ - type Item = &'a T; - - fn next(&mut self) -> Option<Self::Item> { - while let Some(item) = self.iter.next() { - if !self.other.contains(item) { - return Some(item); - } - } - None - } - - fn size_hint(&self) -> (usize, Option<usize>) { - (0, self.iter.size_hint().1) - } -} - -impl<T, S> DoubleEndedIterator for Difference<'_, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ - fn next_back(&mut self) -> Option<Self::Item> { - while let Some(item) = self.iter.next_back() { - if !self.other.contains(item) { - return Some(item); - } - } - None - } -} - -impl<T, S> FusedIterator for Difference<'_, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ -} - -impl<T, S> Clone for Difference<'_, T, S> { - fn clone(&self) -> Self { - Difference { - iter: self.iter.clone(), - ..*self - } - } -} - -impl<T, S> fmt::Debug for Difference<'_, T, S> -where - T: fmt::Debug + Eq + Hash, - S: BuildHasher, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.clone()).finish() - } -} - -/// A lazy iterator producing elements in the intersection of `IndexSet`s. -/// -/// This `struct` is created by the [`intersection`] method on [`IndexSet`]. -/// See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`intersection`]: struct.IndexSet.html#method.intersection -pub struct Intersection<'a, T, S> { - iter: Iter<'a, T>, - other: &'a IndexSet<T, S>, -} - -impl<'a, T, S> Iterator for Intersection<'a, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ - type Item = &'a T; - - fn next(&mut self) -> Option<Self::Item> { - while let Some(item) = self.iter.next() { - if self.other.contains(item) { - return Some(item); - } - } - None - } - - fn size_hint(&self) -> (usize, Option<usize>) { - (0, self.iter.size_hint().1) - } -} - -impl<T, S> DoubleEndedIterator for Intersection<'_, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ - fn next_back(&mut self) -> Option<Self::Item> { - while let Some(item) = self.iter.next_back() { - if self.other.contains(item) { - return Some(item); - } - } - None - } -} - -impl<T, S> FusedIterator for Intersection<'_, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ -} - -impl<T, S> Clone for Intersection<'_, T, S> { - fn clone(&self) -> Self { - Intersection { - iter: self.iter.clone(), - ..*self - } - } -} - -impl<T, S> fmt::Debug for Intersection<'_, T, S> -where - T: fmt::Debug + Eq + Hash, - S: BuildHasher, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.clone()).finish() - } -} - -/// A lazy iterator producing elements in the symmetric difference of `IndexSet`s. -/// -/// This `struct` is created by the [`symmetric_difference`] method on -/// [`IndexSet`]. See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`symmetric_difference`]: struct.IndexSet.html#method.symmetric_difference -pub struct SymmetricDifference<'a, T, S1, S2> { - iter: Chain<Difference<'a, T, S2>, Difference<'a, T, S1>>, -} - -impl<'a, T, S1, S2> Iterator for SymmetricDifference<'a, T, S1, S2> -where - T: Eq + Hash, - S1: BuildHasher, - S2: BuildHasher, -{ - type Item = &'a T; - - fn next(&mut self) -> Option<Self::Item> { - self.iter.next() - } - - fn size_hint(&self) -> (usize, Option<usize>) { - self.iter.size_hint() - } - - fn fold<B, F>(self, init: B, f: F) -> B - where - F: FnMut(B, Self::Item) -> B, - { - self.iter.fold(init, f) - } -} - -impl<T, S1, S2> DoubleEndedIterator for SymmetricDifference<'_, T, S1, S2> -where - T: Eq + Hash, - S1: BuildHasher, - S2: BuildHasher, -{ - fn next_back(&mut self) -> Option<Self::Item> { - self.iter.next_back() - } - - fn rfold<B, F>(self, init: B, f: F) -> B - where - F: FnMut(B, Self::Item) -> B, - { - self.iter.rfold(init, f) - } -} - -impl<T, S1, S2> FusedIterator for SymmetricDifference<'_, T, S1, S2> -where - T: Eq + Hash, - S1: BuildHasher, - S2: BuildHasher, -{ -} - -impl<T, S1, S2> Clone for SymmetricDifference<'_, T, S1, S2> { - fn clone(&self) -> Self { - SymmetricDifference { - iter: self.iter.clone(), - } - } -} - -impl<T, S1, S2> fmt::Debug for SymmetricDifference<'_, T, S1, S2> -where - T: fmt::Debug + Eq + Hash, - S1: BuildHasher, - S2: BuildHasher, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.clone()).finish() - } -} - -/// A lazy iterator producing elements in the union of `IndexSet`s. -/// -/// This `struct` is created by the [`union`] method on [`IndexSet`]. -/// See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`union`]: struct.IndexSet.html#method.union -pub struct Union<'a, T, S> { - iter: Chain<Iter<'a, T>, Difference<'a, T, S>>, -} - -impl<'a, T, S> Iterator for Union<'a, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ - type Item = &'a T; - - fn next(&mut self) -> Option<Self::Item> { - self.iter.next() - } - - fn size_hint(&self) -> (usize, Option<usize>) { - self.iter.size_hint() - } - - fn fold<B, F>(self, init: B, f: F) -> B - where - F: FnMut(B, Self::Item) -> B, - { - self.iter.fold(init, f) - } -} - -impl<T, S> DoubleEndedIterator for Union<'_, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ - fn next_back(&mut self) -> Option<Self::Item> { - self.iter.next_back() - } - - fn rfold<B, F>(self, init: B, f: F) -> B - where - F: FnMut(B, Self::Item) -> B, - { - self.iter.rfold(init, f) - } -} - -impl<T, S> FusedIterator for Union<'_, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ -} - -impl<T, S> Clone for Union<'_, T, S> { - fn clone(&self) -> Self { - Union { - iter: self.iter.clone(), - } - } -} - -impl<T, S> fmt::Debug for Union<'_, T, S> -where - T: fmt::Debug + Eq + Hash, - S: BuildHasher, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.clone()).finish() - } -} - impl<T, S1, S2> BitAnd<&IndexSet<T, S2>> for &IndexSet<T, S1> where T: Eq + Hash + Clone, @@ -1383,530 +1009,3 @@ where self.difference(other).cloned().collect() } } - -#[cfg(test)] -mod tests { - use super::*; - use std::string::String; - - #[test] - fn it_works() { - let mut set = IndexSet::new(); - assert_eq!(set.is_empty(), true); - set.insert(1); - set.insert(1); - assert_eq!(set.len(), 1); - assert!(set.get(&1).is_some()); - assert_eq!(set.is_empty(), false); - } - - #[test] - fn new() { - let set = IndexSet::<String>::new(); - println!("{:?}", set); - assert_eq!(set.capacity(), 0); - assert_eq!(set.len(), 0); - assert_eq!(set.is_empty(), true); - } - - #[test] - fn insert() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5]; - let not_present = [1, 3, 6, 9, 10]; - let mut set = IndexSet::with_capacity(insert.len()); - - for (i, &elt) in insert.iter().enumerate() { - assert_eq!(set.len(), i); - set.insert(elt); - assert_eq!(set.len(), i + 1); - assert_eq!(set.get(&elt), Some(&elt)); - } - println!("{:?}", set); - - for &elt in ¬_present { - assert!(set.get(&elt).is_none()); - } - } - - #[test] - fn insert_full() { - let insert = vec![9, 2, 7, 1, 4, 6, 13]; - let present = vec![1, 6, 2]; - let mut set = IndexSet::with_capacity(insert.len()); - - for (i, &elt) in insert.iter().enumerate() { - assert_eq!(set.len(), i); - let (index, success) = set.insert_full(elt); - assert!(success); - assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); - assert_eq!(set.len(), i + 1); - } - - let len = set.len(); - for &elt in &present { - let (index, success) = set.insert_full(elt); - assert!(!success); - assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); - assert_eq!(set.len(), len); - } - } - - #[test] - fn insert_2() { - let mut set = IndexSet::with_capacity(16); - - let mut values = vec![]; - values.extend(0..16); - values.extend(if cfg!(miri) { 32..64 } else { 128..267 }); - - for &i in &values { - let old_set = set.clone(); - set.insert(i); - for value in old_set.iter() { - if set.get(value).is_none() { - println!("old_set: {:?}", old_set); - println!("set: {:?}", set); - panic!("did not find {} in set", value); - } - } - } - - for &i in &values { - assert!(set.get(&i).is_some(), "did not find {}", i); - } - } - - #[test] - fn insert_dup() { - let mut elements = vec![0, 2, 4, 6, 8]; - let mut set: IndexSet<u8> = elements.drain(..).collect(); - { - let (i, v) = set.get_full(&0).unwrap(); - assert_eq!(set.len(), 5); - assert_eq!(i, 0); - assert_eq!(*v, 0); - } - { - let inserted = set.insert(0); - let (i, v) = set.get_full(&0).unwrap(); - assert_eq!(set.len(), 5); - assert_eq!(inserted, false); - assert_eq!(i, 0); - assert_eq!(*v, 0); - } - } - - #[test] - fn insert_order() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; - let mut set = IndexSet::new(); - - for &elt in &insert { - set.insert(elt); - } - - assert_eq!(set.iter().count(), set.len()); - assert_eq!(set.iter().count(), insert.len()); - for (a, b) in insert.iter().zip(set.iter()) { - assert_eq!(a, b); - } - for (i, v) in (0..insert.len()).zip(set.iter()) { - assert_eq!(set.get_index(i).unwrap(), v); - } - } - - #[test] - fn replace() { - let replace = [0, 4, 2, 12, 8, 7, 11, 5]; - let not_present = [1, 3, 6, 9, 10]; - let mut set = IndexSet::with_capacity(replace.len()); - - for (i, &elt) in replace.iter().enumerate() { - assert_eq!(set.len(), i); - set.replace(elt); - assert_eq!(set.len(), i + 1); - assert_eq!(set.get(&elt), Some(&elt)); - } - println!("{:?}", set); - - for &elt in ¬_present { - assert!(set.get(&elt).is_none()); - } - } - - #[test] - fn replace_full() { - let replace = vec![9, 2, 7, 1, 4, 6, 13]; - let present = vec![1, 6, 2]; - let mut set = IndexSet::with_capacity(replace.len()); - - for (i, &elt) in replace.iter().enumerate() { - assert_eq!(set.len(), i); - let (index, replaced) = set.replace_full(elt); - assert!(replaced.is_none()); - assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); - assert_eq!(set.len(), i + 1); - } - - let len = set.len(); - for &elt in &present { - let (index, replaced) = set.replace_full(elt); - assert_eq!(Some(elt), replaced); - assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); - assert_eq!(set.len(), len); - } - } - - #[test] - fn replace_2() { - let mut set = IndexSet::with_capacity(16); - - let mut values = vec![]; - values.extend(0..16); - values.extend(if cfg!(miri) { 32..64 } else { 128..267 }); - - for &i in &values { - let old_set = set.clone(); - set.replace(i); - for value in old_set.iter() { - if set.get(value).is_none() { - println!("old_set: {:?}", old_set); - println!("set: {:?}", set); - panic!("did not find {} in set", value); - } - } - } - - for &i in &values { - assert!(set.get(&i).is_some(), "did not find {}", i); - } - } - - #[test] - fn replace_dup() { - let mut elements = vec![0, 2, 4, 6, 8]; - let mut set: IndexSet<u8> = elements.drain(..).collect(); - { - let (i, v) = set.get_full(&0).unwrap(); - assert_eq!(set.len(), 5); - assert_eq!(i, 0); - assert_eq!(*v, 0); - } - { - let replaced = set.replace(0); - let (i, v) = set.get_full(&0).unwrap(); - assert_eq!(set.len(), 5); - assert_eq!(replaced, Some(0)); - assert_eq!(i, 0); - assert_eq!(*v, 0); - } - } - - #[test] - fn replace_order() { - let replace = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; - let mut set = IndexSet::new(); - - for &elt in &replace { - set.replace(elt); - } - - assert_eq!(set.iter().count(), set.len()); - assert_eq!(set.iter().count(), replace.len()); - for (a, b) in replace.iter().zip(set.iter()) { - assert_eq!(a, b); - } - for (i, v) in (0..replace.len()).zip(set.iter()) { - assert_eq!(set.get_index(i).unwrap(), v); - } - } - - #[test] - fn grow() { - let insert = [0, 4, 2, 12, 8, 7, 11]; - let not_present = [1, 3, 6, 9, 10]; - let mut set = IndexSet::with_capacity(insert.len()); - - for (i, &elt) in insert.iter().enumerate() { - assert_eq!(set.len(), i); - set.insert(elt); - assert_eq!(set.len(), i + 1); - assert_eq!(set.get(&elt), Some(&elt)); - } - - println!("{:?}", set); - for &elt in &insert { - set.insert(elt * 10); - } - for &elt in &insert { - set.insert(elt * 100); - } - for (i, &elt) in insert.iter().cycle().enumerate().take(100) { - set.insert(elt * 100 + i as i32); - } - println!("{:?}", set); - for &elt in ¬_present { - assert!(set.get(&elt).is_none()); - } - } - - #[test] - fn reserve() { - let mut set = IndexSet::<usize>::new(); - assert_eq!(set.capacity(), 0); - set.reserve(100); - let capacity = set.capacity(); - assert!(capacity >= 100); - for i in 0..capacity { - assert_eq!(set.len(), i); - set.insert(i); - assert_eq!(set.len(), i + 1); - assert_eq!(set.capacity(), capacity); - assert_eq!(set.get(&i), Some(&i)); - } - set.insert(capacity); - assert_eq!(set.len(), capacity + 1); - assert!(set.capacity() > capacity); - assert_eq!(set.get(&capacity), Some(&capacity)); - } - - #[test] - fn shrink_to_fit() { - let mut set = IndexSet::<usize>::new(); - assert_eq!(set.capacity(), 0); - for i in 0..100 { - assert_eq!(set.len(), i); - set.insert(i); - assert_eq!(set.len(), i + 1); - assert!(set.capacity() >= i + 1); - assert_eq!(set.get(&i), Some(&i)); - set.shrink_to_fit(); - assert_eq!(set.len(), i + 1); - assert_eq!(set.capacity(), i + 1); - assert_eq!(set.get(&i), Some(&i)); - } - } - - #[test] - fn remove() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; - let mut set = IndexSet::new(); - - for &elt in &insert { - set.insert(elt); - } - - assert_eq!(set.iter().count(), set.len()); - assert_eq!(set.iter().count(), insert.len()); - for (a, b) in insert.iter().zip(set.iter()) { - assert_eq!(a, b); - } - - let remove_fail = [99, 77]; - let remove = [4, 12, 8, 7]; - - for &value in &remove_fail { - assert!(set.swap_remove_full(&value).is_none()); - } - println!("{:?}", set); - for &value in &remove { - //println!("{:?}", set); - let index = set.get_full(&value).unwrap().0; - assert_eq!(set.swap_remove_full(&value), Some((index, value))); - } - println!("{:?}", set); - - for value in &insert { - assert_eq!(set.get(value).is_some(), !remove.contains(value)); - } - assert_eq!(set.len(), insert.len() - remove.len()); - assert_eq!(set.iter().count(), insert.len() - remove.len()); - } - - #[test] - fn swap_remove_index() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; - let mut set = IndexSet::new(); - - for &elt in &insert { - set.insert(elt); - } - - let mut vector = insert.to_vec(); - let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1]; - - // check that the same swap remove sequence on vec and set - // have the same result. - for &rm in remove_sequence { - let out_vec = vector.swap_remove(rm); - let out_set = set.swap_remove_index(rm).unwrap(); - assert_eq!(out_vec, out_set); - } - assert_eq!(vector.len(), set.len()); - for (a, b) in vector.iter().zip(set.iter()) { - assert_eq!(a, b); - } - } - - #[test] - fn partial_eq_and_eq() { - let mut set_a = IndexSet::new(); - set_a.insert(1); - set_a.insert(2); - let mut set_b = set_a.clone(); - assert_eq!(set_a, set_b); - set_b.swap_remove(&1); - assert_ne!(set_a, set_b); - - let set_c: IndexSet<_> = set_b.into_iter().collect(); - assert_ne!(set_a, set_c); - assert_ne!(set_c, set_a); - } - - #[test] - fn extend() { - let mut set = IndexSet::new(); - set.extend(vec![&1, &2, &3, &4]); - set.extend(vec![5, 6]); - assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6]); - } - - #[test] - fn comparisons() { - let set_a: IndexSet<_> = (0..3).collect(); - let set_b: IndexSet<_> = (3..6).collect(); - let set_c: IndexSet<_> = (0..6).collect(); - let set_d: IndexSet<_> = (3..9).collect(); - - assert!(!set_a.is_disjoint(&set_a)); - assert!(set_a.is_subset(&set_a)); - assert!(set_a.is_superset(&set_a)); - - assert!(set_a.is_disjoint(&set_b)); - assert!(set_b.is_disjoint(&set_a)); - assert!(!set_a.is_subset(&set_b)); - assert!(!set_b.is_subset(&set_a)); - assert!(!set_a.is_superset(&set_b)); - assert!(!set_b.is_superset(&set_a)); - - assert!(!set_a.is_disjoint(&set_c)); - assert!(!set_c.is_disjoint(&set_a)); - assert!(set_a.is_subset(&set_c)); - assert!(!set_c.is_subset(&set_a)); - assert!(!set_a.is_superset(&set_c)); - assert!(set_c.is_superset(&set_a)); - - assert!(!set_c.is_disjoint(&set_d)); - assert!(!set_d.is_disjoint(&set_c)); - assert!(!set_c.is_subset(&set_d)); - assert!(!set_d.is_subset(&set_c)); - assert!(!set_c.is_superset(&set_d)); - assert!(!set_d.is_superset(&set_c)); - } - - #[test] - fn iter_comparisons() { - use std::iter::empty; - - fn check<'a, I1, I2>(iter1: I1, iter2: I2) - where - I1: Iterator<Item = &'a i32>, - I2: Iterator<Item = i32>, - { - assert!(iter1.copied().eq(iter2)); - } - - let set_a: IndexSet<_> = (0..3).collect(); - let set_b: IndexSet<_> = (3..6).collect(); - let set_c: IndexSet<_> = (0..6).collect(); - let set_d: IndexSet<_> = (3..9).rev().collect(); - - check(set_a.difference(&set_a), empty()); - check(set_a.symmetric_difference(&set_a), empty()); - check(set_a.intersection(&set_a), 0..3); - check(set_a.union(&set_a), 0..3); - - check(set_a.difference(&set_b), 0..3); - check(set_b.difference(&set_a), 3..6); - check(set_a.symmetric_difference(&set_b), 0..6); - check(set_b.symmetric_difference(&set_a), (3..6).chain(0..3)); - check(set_a.intersection(&set_b), empty()); - check(set_b.intersection(&set_a), empty()); - check(set_a.union(&set_b), 0..6); - check(set_b.union(&set_a), (3..6).chain(0..3)); - - check(set_a.difference(&set_c), empty()); - check(set_c.difference(&set_a), 3..6); - check(set_a.symmetric_difference(&set_c), 3..6); - check(set_c.symmetric_difference(&set_a), 3..6); - check(set_a.intersection(&set_c), 0..3); - check(set_c.intersection(&set_a), 0..3); - check(set_a.union(&set_c), 0..6); - check(set_c.union(&set_a), 0..6); - - check(set_c.difference(&set_d), 0..3); - check(set_d.difference(&set_c), (6..9).rev()); - check( - set_c.symmetric_difference(&set_d), - (0..3).chain((6..9).rev()), - ); - check(set_d.symmetric_difference(&set_c), (6..9).rev().chain(0..3)); - check(set_c.intersection(&set_d), 3..6); - check(set_d.intersection(&set_c), (3..6).rev()); - check(set_c.union(&set_d), (0..6).chain((6..9).rev())); - check(set_d.union(&set_c), (3..9).rev().chain(0..3)); - } - - #[test] - fn ops() { - let empty = IndexSet::<i32>::new(); - let set_a: IndexSet<_> = (0..3).collect(); - let set_b: IndexSet<_> = (3..6).collect(); - let set_c: IndexSet<_> = (0..6).collect(); - let set_d: IndexSet<_> = (3..9).rev().collect(); - - #[allow(clippy::eq_op)] - { - assert_eq!(&set_a & &set_a, set_a); - assert_eq!(&set_a | &set_a, set_a); - assert_eq!(&set_a ^ &set_a, empty); - assert_eq!(&set_a - &set_a, empty); - } - - assert_eq!(&set_a & &set_b, empty); - assert_eq!(&set_b & &set_a, empty); - assert_eq!(&set_a | &set_b, set_c); - assert_eq!(&set_b | &set_a, set_c); - assert_eq!(&set_a ^ &set_b, set_c); - assert_eq!(&set_b ^ &set_a, set_c); - assert_eq!(&set_a - &set_b, set_a); - assert_eq!(&set_b - &set_a, set_b); - - assert_eq!(&set_a & &set_c, set_a); - assert_eq!(&set_c & &set_a, set_a); - assert_eq!(&set_a | &set_c, set_c); - assert_eq!(&set_c | &set_a, set_c); - assert_eq!(&set_a ^ &set_c, set_b); - assert_eq!(&set_c ^ &set_a, set_b); - assert_eq!(&set_a - &set_c, empty); - assert_eq!(&set_c - &set_a, set_b); - - assert_eq!(&set_c & &set_d, set_b); - assert_eq!(&set_d & &set_c, set_b); - assert_eq!(&set_c | &set_d, &set_a | &set_d); - assert_eq!(&set_d | &set_c, &set_a | &set_d); - assert_eq!(&set_c ^ &set_d, &set_a | &(&set_d - &set_b)); - assert_eq!(&set_d ^ &set_c, &set_a | &(&set_d - &set_b)); - assert_eq!(&set_c - &set_d, set_a); - assert_eq!(&set_d - &set_c, &set_d - &set_b); - } - - #[test] - #[cfg(has_std)] - fn from_array() { - let set1 = IndexSet::from([1, 2, 3, 4]); - let set2: IndexSet<_> = [1, 2, 3, 4].into(); - - assert_eq!(set1, set2); - } -} |