From 8dd16259287f58f9273002717ec4d27e97127719 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 12 Jun 2024 07:43:14 +0200 Subject: Merging upstream version 127.0. Signed-off-by: Daniel Baumann --- third_party/rust/indexmap/src/set/iter.rs | 626 +++++++++++++++++++++++ third_party/rust/indexmap/src/set/mutable.rs | 86 ++++ third_party/rust/indexmap/src/set/slice.rs | 340 +++++++++++++ third_party/rust/indexmap/src/set/tests.rs | 723 +++++++++++++++++++++++++++ 4 files changed, 1775 insertions(+) create mode 100644 third_party/rust/indexmap/src/set/iter.rs create mode 100644 third_party/rust/indexmap/src/set/mutable.rs create mode 100644 third_party/rust/indexmap/src/set/slice.rs create mode 100644 third_party/rust/indexmap/src/set/tests.rs (limited to 'third_party/rust/indexmap/src/set') diff --git a/third_party/rust/indexmap/src/set/iter.rs b/third_party/rust/indexmap/src/set/iter.rs new file mode 100644 index 0000000000..3f8033c2db --- /dev/null +++ b/third_party/rust/indexmap/src/set/iter.rs @@ -0,0 +1,626 @@ +use super::{Bucket, Entries, IndexSet, Slice}; + +use alloc::vec::{self, Vec}; +use core::fmt; +use core::hash::{BuildHasher, Hash}; +use core::iter::{Chain, FusedIterator}; +use core::ops::RangeBounds; +use core::slice::Iter as SliceIter; + +impl<'a, T, S> IntoIterator for &'a IndexSet { + type Item = &'a T; + type IntoIter = Iter<'a, T>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl IntoIterator for IndexSet { + type Item = T; + type IntoIter = IntoIter; + + fn into_iter(self) -> Self::IntoIter { + IntoIter::new(self.into_entries()) + } +} + +/// An iterator over the items of an [`IndexSet`]. +/// +/// This `struct` is created by the [`IndexSet::iter`] method. +/// See its documentation for more. +pub struct Iter<'a, T> { + iter: SliceIter<'a, Bucket>, +} + +impl<'a, T> Iter<'a, T> { + pub(super) fn new(entries: &'a [Bucket]) -> Self { + Self { + iter: entries.iter(), + } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &'a Slice { + Slice::from_slice(self.iter.as_slice()) + } +} + +impl<'a, T> Iterator for Iter<'a, T> { + type Item = &'a T; + + iterator_methods!(Bucket::key_ref); +} + +impl DoubleEndedIterator for Iter<'_, T> { + double_ended_iterator_methods!(Bucket::key_ref); +} + +impl ExactSizeIterator for Iter<'_, T> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for Iter<'_, T> {} + +impl Clone for Iter<'_, T> { + fn clone(&self) -> Self { + Iter { + iter: self.iter.clone(), + } + } +} + +impl fmt::Debug for Iter<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl Default for Iter<'_, T> { + fn default() -> Self { + Self { iter: [].iter() } + } +} + +/// An owning iterator over the items of an [`IndexSet`]. +/// +/// This `struct` is created by the [`IndexSet::into_iter`] method +/// (provided by the [`IntoIterator`] trait). See its documentation for more. +pub struct IntoIter { + iter: vec::IntoIter>, +} + +impl IntoIter { + pub(super) fn new(entries: Vec>) -> Self { + Self { + iter: entries.into_iter(), + } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &Slice { + Slice::from_slice(self.iter.as_slice()) + } +} + +impl Iterator for IntoIter { + type Item = T; + + iterator_methods!(Bucket::key); +} + +impl DoubleEndedIterator for IntoIter { + double_ended_iterator_methods!(Bucket::key); +} + +impl ExactSizeIterator for IntoIter { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for IntoIter {} + +impl fmt::Debug for IntoIter { + 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 Default for IntoIter { + fn default() -> Self { + Self { + iter: Vec::new().into_iter(), + } + } +} + +/// A draining iterator over the items of an [`IndexSet`]. +/// +/// This `struct` is created by the [`IndexSet::drain`] method. +/// See its documentation for more. +pub struct Drain<'a, T> { + iter: vec::Drain<'a, Bucket>, +} + +impl<'a, T> Drain<'a, T> { + pub(super) fn new(iter: vec::Drain<'a, Bucket>) -> Self { + Self { iter } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &Slice { + Slice::from_slice(self.iter.as_slice()) + } +} + +impl Iterator for Drain<'_, T> { + type Item = T; + + iterator_methods!(Bucket::key); +} + +impl DoubleEndedIterator for Drain<'_, T> { + double_ended_iterator_methods!(Bucket::key); +} + +impl ExactSizeIterator for Drain<'_, T> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for Drain<'_, T> {} + +impl 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() + } +} + +/// A lazy iterator producing elements in the difference of [`IndexSet`]s. +/// +/// This `struct` is created by the [`IndexSet::difference`] method. +/// See its documentation for more. +pub struct Difference<'a, T, S> { + iter: Iter<'a, T>, + other: &'a IndexSet, +} + +impl<'a, T, S> Difference<'a, T, S> { + pub(super) fn new(set: &'a IndexSet, other: &'a IndexSet) -> Self { + Self { + iter: set.iter(), + other, + } + } +} + +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 { + while let Some(item) = self.iter.next() { + if !self.other.contains(item) { + return Some(item); + } + } + None + } + + fn size_hint(&self) -> (usize, Option) { + (0, self.iter.size_hint().1) + } +} + +impl DoubleEndedIterator for Difference<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + fn next_back(&mut self) -> Option { + while let Some(item) = self.iter.next_back() { + if !self.other.contains(item) { + return Some(item); + } + } + None + } +} + +impl FusedIterator for Difference<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ +} + +impl Clone for Difference<'_, T, S> { + fn clone(&self) -> Self { + Difference { + iter: self.iter.clone(), + ..*self + } + } +} + +impl 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 [`IndexSet::intersection`] method. +/// See its documentation for more. +pub struct Intersection<'a, T, S> { + iter: Iter<'a, T>, + other: &'a IndexSet, +} + +impl<'a, T, S> Intersection<'a, T, S> { + pub(super) fn new(set: &'a IndexSet, other: &'a IndexSet) -> Self { + Self { + iter: set.iter(), + other, + } + } +} + +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 { + while let Some(item) = self.iter.next() { + if self.other.contains(item) { + return Some(item); + } + } + None + } + + fn size_hint(&self) -> (usize, Option) { + (0, self.iter.size_hint().1) + } +} + +impl DoubleEndedIterator for Intersection<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + fn next_back(&mut self) -> Option { + while let Some(item) = self.iter.next_back() { + if self.other.contains(item) { + return Some(item); + } + } + None + } +} + +impl FusedIterator for Intersection<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ +} + +impl Clone for Intersection<'_, T, S> { + fn clone(&self) -> Self { + Intersection { + iter: self.iter.clone(), + ..*self + } + } +} + +impl 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 [`IndexSet::symmetric_difference`] method. +/// See its documentation for more. +pub struct SymmetricDifference<'a, T, S1, S2> { + iter: Chain, Difference<'a, T, S1>>, +} + +impl<'a, T, S1, S2> SymmetricDifference<'a, T, S1, S2> +where + T: Eq + Hash, + S1: BuildHasher, + S2: BuildHasher, +{ + pub(super) fn new(set1: &'a IndexSet, set2: &'a IndexSet) -> Self { + let diff1 = set1.difference(set2); + let diff2 = set2.difference(set1); + Self { + iter: diff1.chain(diff2), + } + } +} + +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.iter.next() + } + + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + fn fold(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, f) + } +} + +impl DoubleEndedIterator for SymmetricDifference<'_, T, S1, S2> +where + T: Eq + Hash, + S1: BuildHasher, + S2: BuildHasher, +{ + fn next_back(&mut self) -> Option { + self.iter.next_back() + } + + fn rfold(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.rfold(init, f) + } +} + +impl FusedIterator for SymmetricDifference<'_, T, S1, S2> +where + T: Eq + Hash, + S1: BuildHasher, + S2: BuildHasher, +{ +} + +impl Clone for SymmetricDifference<'_, T, S1, S2> { + fn clone(&self) -> Self { + SymmetricDifference { + iter: self.iter.clone(), + } + } +} + +impl 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 [`IndexSet::union`] method. +/// See its documentation for more. +pub struct Union<'a, T, S> { + iter: Chain, Difference<'a, T, S>>, +} + +impl<'a, T, S> Union<'a, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + pub(super) fn new(set1: &'a IndexSet, set2: &'a IndexSet) -> Self + where + S2: BuildHasher, + { + Self { + iter: set1.iter().chain(set2.difference(set1)), + } + } +} + +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.iter.next() + } + + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + fn fold(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, f) + } +} + +impl DoubleEndedIterator for Union<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + fn next_back(&mut self) -> Option { + self.iter.next_back() + } + + fn rfold(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.rfold(init, f) + } +} + +impl FusedIterator for Union<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ +} + +impl Clone for Union<'_, T, S> { + fn clone(&self) -> Self { + Union { + iter: self.iter.clone(), + } + } +} + +impl 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() + } +} + +/// A splicing iterator for `IndexSet`. +/// +/// This `struct` is created by [`IndexSet::splice()`]. +/// See its documentation for more. +pub struct Splice<'a, I, T, S> +where + I: Iterator, + T: Hash + Eq, + S: BuildHasher, +{ + iter: crate::map::Splice<'a, UnitValue, T, (), S>, +} + +impl<'a, I, T, S> Splice<'a, I, T, S> +where + I: Iterator, + T: Hash + Eq, + S: BuildHasher, +{ + pub(super) fn new(set: &'a mut IndexSet, range: R, replace_with: I) -> Self + where + R: RangeBounds, + { + Self { + iter: set.map.splice(range, UnitValue(replace_with)), + } + } +} + +impl Iterator for Splice<'_, I, T, S> +where + I: Iterator, + T: Hash + Eq, + S: BuildHasher, +{ + type Item = T; + + fn next(&mut self) -> Option { + Some(self.iter.next()?.0) + } + + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } +} + +impl DoubleEndedIterator for Splice<'_, I, T, S> +where + I: Iterator, + T: Hash + Eq, + S: BuildHasher, +{ + fn next_back(&mut self) -> Option { + Some(self.iter.next_back()?.0) + } +} + +impl ExactSizeIterator for Splice<'_, I, T, S> +where + I: Iterator, + T: Hash + Eq, + S: BuildHasher, +{ + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for Splice<'_, I, T, S> +where + I: Iterator, + T: Hash + Eq, + S: BuildHasher, +{ +} + +struct UnitValue(I); + +impl Iterator for UnitValue { + type Item = (I::Item, ()); + + fn next(&mut self) -> Option { + self.0.next().map(|x| (x, ())) + } +} + +impl<'a, I, T, S> fmt::Debug for Splice<'a, I, T, S> +where + I: fmt::Debug + Iterator, + T: fmt::Debug + Hash + Eq, + S: BuildHasher, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Debug::fmt(&self.iter, f) + } +} + +impl fmt::Debug for UnitValue { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Debug::fmt(&self.0, f) + } +} diff --git a/third_party/rust/indexmap/src/set/mutable.rs b/third_party/rust/indexmap/src/set/mutable.rs new file mode 100644 index 0000000000..20eaa11221 --- /dev/null +++ b/third_party/rust/indexmap/src/set/mutable.rs @@ -0,0 +1,86 @@ +use core::hash::{BuildHasher, Hash}; + +use super::{Equivalent, IndexSet}; +use crate::map::MutableKeys; + +/// Opt-in mutable access to [`IndexSet`] values. +/// +/// These methods expose `&mut T`, mutable references to the value as it is stored +/// in the set. +/// You are allowed to modify the values in the set **if the modification +/// does not change the value’s hash and equality**. +/// +/// If values are modified erroneously, you can no longer look them up. +/// This is sound (memory safe) but a logical error hazard (just like +/// implementing `PartialEq`, `Eq`, or `Hash` incorrectly would be). +/// +/// `use` this trait to enable its methods for `IndexSet`. +/// +/// This trait is sealed and cannot be implemented for types outside this crate. +pub trait MutableValues: private::Sealed { + type Value; + + /// Return item index and mutable reference to the value + /// + /// Computes in **O(1)** time (average). + fn get_full_mut2(&mut self, value: &Q) -> Option<(usize, &mut Self::Value)> + where + Q: ?Sized + Hash + Equivalent; + + /// Return mutable reference to the value at an index. + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Computes in **O(1)** time. + fn get_index_mut2(&mut self, index: usize) -> Option<&mut Self::Value>; + + /// Scan through each value in the set and keep those where the + /// closure `keep` returns `true`. + /// + /// The values are visited in order, and remaining values keep their order. + /// + /// Computes in **O(n)** time (average). + fn retain2(&mut self, keep: F) + where + F: FnMut(&mut Self::Value) -> bool; +} + +/// Opt-in mutable access to [`IndexSet`] values. +/// +/// See [`MutableValues`] for more information. +impl MutableValues for IndexSet +where + S: BuildHasher, +{ + type Value = T; + + fn get_full_mut2(&mut self, value: &Q) -> Option<(usize, &mut T)> + where + Q: ?Sized + Hash + Equivalent, + { + match self.map.get_full_mut2(value) { + Some((index, value, ())) => Some((index, value)), + None => None, + } + } + + fn get_index_mut2(&mut self, index: usize) -> Option<&mut T> { + match self.map.get_index_mut2(index) { + Some((value, ())) => Some(value), + None => None, + } + } + + fn retain2(&mut self, mut keep: F) + where + F: FnMut(&mut T) -> bool, + { + self.map.retain2(move |value, ()| keep(value)); + } +} + +mod private { + pub trait Sealed {} + + impl Sealed for super::IndexSet {} +} diff --git a/third_party/rust/indexmap/src/set/slice.rs b/third_party/rust/indexmap/src/set/slice.rs new file mode 100644 index 0000000000..9fc208c706 --- /dev/null +++ b/third_party/rust/indexmap/src/set/slice.rs @@ -0,0 +1,340 @@ +use super::{Bucket, Entries, IndexSet, IntoIter, Iter}; +use crate::util::try_simplify_range; + +use alloc::boxed::Box; +use alloc::vec::Vec; +use core::cmp::Ordering; +use core::fmt; +use core::hash::{Hash, Hasher}; +use core::ops::{self, Bound, Index, RangeBounds}; + +/// A dynamically-sized slice of values in an [`IndexSet`]. +/// +/// This supports indexed operations much like a `[T]` slice, +/// but not any hashed operations on the values. +/// +/// Unlike `IndexSet`, `Slice` does consider the order for [`PartialEq`] +/// and [`Eq`], and it also implements [`PartialOrd`], [`Ord`], and [`Hash`]. +#[repr(transparent)] +pub struct Slice { + pub(crate) entries: [Bucket], +} + +// SAFETY: `Slice` is a transparent wrapper around `[Bucket]`, +// and reference lifetimes are bound together in function signatures. +#[allow(unsafe_code)] +impl Slice { + pub(super) const fn from_slice(entries: &[Bucket]) -> &Self { + unsafe { &*(entries as *const [Bucket] as *const Self) } + } + + pub(super) fn from_boxed(entries: Box<[Bucket]>) -> Box { + unsafe { Box::from_raw(Box::into_raw(entries) as *mut Self) } + } + + fn into_boxed(self: Box) -> Box<[Bucket]> { + unsafe { Box::from_raw(Box::into_raw(self) as *mut [Bucket]) } + } +} + +impl Slice { + pub(crate) fn into_entries(self: Box) -> Vec> { + self.into_boxed().into_vec() + } + + /// Returns an empty slice. + pub const fn new<'a>() -> &'a Self { + Self::from_slice(&[]) + } + + /// Return the number of elements in the set slice. + pub const fn len(&self) -> usize { + self.entries.len() + } + + /// Returns true if the set slice contains no elements. + pub const fn is_empty(&self) -> bool { + self.entries.is_empty() + } + + /// Get a value by index. + /// + /// Valid indices are *0 <= index < self.len()* + pub fn get_index(&self, index: usize) -> Option<&T> { + self.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()* + pub fn get_range>(&self, range: R) -> Option<&Self> { + let range = try_simplify_range(range, self.entries.len())?; + self.entries.get(range).map(Self::from_slice) + } + + /// Get the first value. + pub fn first(&self) -> Option<&T> { + self.entries.first().map(Bucket::key_ref) + } + + /// Get the last value. + pub fn last(&self) -> Option<&T> { + self.entries.last().map(Bucket::key_ref) + } + + /// Divides one slice into two at an index. + /// + /// ***Panics*** if `index > len`. + pub fn split_at(&self, index: usize) -> (&Self, &Self) { + let (first, second) = self.entries.split_at(index); + (Self::from_slice(first), Self::from_slice(second)) + } + + /// Returns the first value and the rest of the slice, + /// or `None` if it is empty. + pub fn split_first(&self) -> Option<(&T, &Self)> { + if let [first, rest @ ..] = &self.entries { + Some((&first.key, Self::from_slice(rest))) + } else { + None + } + } + + /// Returns the last value and the rest of the slice, + /// or `None` if it is empty. + pub fn split_last(&self) -> Option<(&T, &Self)> { + if let [rest @ .., last] = &self.entries { + Some((&last.key, Self::from_slice(rest))) + } else { + None + } + } + + /// Return an iterator over the values of the set slice. + pub fn iter(&self) -> Iter<'_, T> { + Iter::new(&self.entries) + } + + /// Search over a sorted set for a value. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search`] for more details. + /// + /// Computes in **O(log(n))** time, which is notably less scalable than looking the value up in + /// the set this is a slice from using [`IndexSet::get_index_of`], but this can also position + /// missing values. + pub fn binary_search(&self, x: &T) -> Result + where + T: Ord, + { + self.binary_search_by(|p| p.cmp(x)) + } + + /// Search over a sorted set with a comparator function. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search_by`] for more details. + /// + /// Computes in **O(log(n))** time. + #[inline] + pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result + where + F: FnMut(&'a T) -> Ordering, + { + self.entries.binary_search_by(move |a| f(&a.key)) + } + + /// Search over a sorted set with an extraction function. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search_by_key`] for more details. + /// + /// Computes in **O(log(n))** time. + #[inline] + pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result + where + F: FnMut(&'a T) -> B, + B: Ord, + { + self.binary_search_by(|k| f(k).cmp(b)) + } + + /// Returns the index of the partition point of a sorted set according to the given predicate + /// (the index of the first element of the second partition). + /// + /// See [`slice::partition_point`] for more details. + /// + /// Computes in **O(log(n))** time. + #[must_use] + pub fn partition_point

(&self, mut pred: P) -> usize + where + P: FnMut(&T) -> bool, + { + self.entries.partition_point(move |a| pred(&a.key)) + } +} + +impl<'a, T> IntoIterator for &'a Slice { + type IntoIter = Iter<'a, T>; + type Item = &'a T; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl IntoIterator for Box> { + type IntoIter = IntoIter; + type Item = T; + + fn into_iter(self) -> Self::IntoIter { + IntoIter::new(self.into_entries()) + } +} + +impl Default for &'_ Slice { + fn default() -> Self { + Slice::from_slice(&[]) + } +} + +impl Default for Box> { + fn default() -> Self { + Slice::from_boxed(Box::default()) + } +} + +impl Clone for Box> { + fn clone(&self) -> Self { + Slice::from_boxed(self.entries.to_vec().into_boxed_slice()) + } +} + +impl From<&Slice> for Box> { + fn from(slice: &Slice) -> Self { + Slice::from_boxed(Box::from(&slice.entries)) + } +} + +impl fmt::Debug for Slice { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self).finish() + } +} + +impl PartialEq for Slice { + fn eq(&self, other: &Self) -> bool { + self.len() == other.len() && self.iter().eq(other) + } +} + +impl Eq for Slice {} + +impl PartialOrd for Slice { + fn partial_cmp(&self, other: &Self) -> Option { + self.iter().partial_cmp(other) + } +} + +impl Ord for Slice { + fn cmp(&self, other: &Self) -> Ordering { + self.iter().cmp(other) + } +} + +impl Hash for Slice { + fn hash(&self, state: &mut H) { + self.len().hash(state); + for value in self { + value.hash(state); + } + } +} + +impl Index for Slice { + type Output = T; + + fn index(&self, index: usize) -> &Self::Output { + &self.entries[index].key + } +} + +// We can't have `impl> Index` because that conflicts with `Index`. +// Instead, we repeat the implementations for all the core range types. +macro_rules! impl_index { + ($($range:ty),*) => {$( + impl Index<$range> for IndexSet { + type Output = Slice; + + fn index(&self, range: $range) -> &Self::Output { + Slice::from_slice(&self.as_entries()[range]) + } + } + + impl Index<$range> for Slice { + type Output = Self; + + fn index(&self, range: $range) -> &Self::Output { + Slice::from_slice(&self.entries[range]) + } + } + )*} +} +impl_index!( + ops::Range, + ops::RangeFrom, + ops::RangeFull, + ops::RangeInclusive, + ops::RangeTo, + ops::RangeToInclusive, + (Bound, Bound) +); + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn slice_index() { + fn check(vec_slice: &[i32], set_slice: &Slice, sub_slice: &Slice) { + assert_eq!(set_slice as *const _, sub_slice as *const _); + itertools::assert_equal(vec_slice, set_slice); + } + + let vec: Vec = (0..10).map(|i| i * i).collect(); + let set: IndexSet = vec.iter().cloned().collect(); + let slice = set.as_slice(); + + // RangeFull + check(&vec[..], &set[..], &slice[..]); + + for i in 0usize..10 { + // Index + assert_eq!(vec[i], set[i]); + assert_eq!(vec[i], slice[i]); + + // RangeFrom + check(&vec[i..], &set[i..], &slice[i..]); + + // RangeTo + check(&vec[..i], &set[..i], &slice[..i]); + + // RangeToInclusive + check(&vec[..=i], &set[..=i], &slice[..=i]); + + // (Bound, Bound) + let bounds = (Bound::Excluded(i), Bound::Unbounded); + check(&vec[i + 1..], &set[bounds], &slice[bounds]); + + for j in i..=10 { + // Range + check(&vec[i..j], &set[i..j], &slice[i..j]); + } + + for j in i..10 { + // RangeInclusive + check(&vec[i..=j], &set[i..=j], &slice[i..=j]); + } + } + } +} diff --git a/third_party/rust/indexmap/src/set/tests.rs b/third_party/rust/indexmap/src/set/tests.rs new file mode 100644 index 0000000000..35a076e8de --- /dev/null +++ b/third_party/rust/indexmap/src/set/tests.rs @@ -0,0 +1,723 @@ +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::::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 = 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 shift_insert() { + 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.shift_insert(0, elt); + } + + assert_eq!(set.iter().count(), set.len()); + assert_eq!(set.iter().count(), insert.len()); + for (a, b) in insert.iter().rev().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); + } + + // "insert" that moves an existing entry + set.shift_insert(0, insert[0]); + assert_eq!(set.iter().count(), insert.len()); + assert_eq!(insert[0], set[0]); + for (a, b) in insert[1..].iter().rev().zip(set.iter().skip(1)) { + assert_eq!(a, b); + } +} + +#[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 = 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 replace_change() { + // Check pointers to make sure it really changes + let mut set = indexset!(vec![42]); + let old_ptr = set[0].as_ptr(); + let new = set[0].clone(); + let new_ptr = new.as_ptr(); + assert_ne!(old_ptr, new_ptr); + let replaced = set.replace(new).unwrap(); + assert_eq!(replaced.as_ptr(), old_ptr); +} + +#[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::::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 try_reserve() { + let mut set = IndexSet::::new(); + assert_eq!(set.capacity(), 0); + assert_eq!(set.try_reserve(100), Ok(())); + assert!(set.capacity() >= 100); + assert!(set.try_reserve(usize::MAX).is_err()); +} + +#[test] +fn shrink_to_fit() { + let mut set = IndexSet::::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![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, + I2: Iterator, + { + 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::::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(feature = "std")] +fn from_array() { + let set1 = IndexSet::from([1, 2, 3, 4]); + let set2: IndexSet<_> = [1, 2, 3, 4].into(); + + assert_eq!(set1, set2); +} + +#[test] +fn iter_default() { + struct Item; + fn assert_default() + where + T: Default + Iterator, + { + assert!(T::default().next().is_none()); + } + assert_default::>(); + assert_default::>(); +} + +#[test] +fn test_binary_search_by() { + // adapted from std's test for binary_search + let b: IndexSet = [].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&5)), Err(0)); + + let b: IndexSet = [4].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&3)), Err(0)); + assert_eq!(b.binary_search_by(|x| x.cmp(&4)), Ok(0)); + assert_eq!(b.binary_search_by(|x| x.cmp(&5)), Err(1)); + + let b: IndexSet = [1, 2, 4, 6, 8, 9].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&5)), Err(3)); + assert_eq!(b.binary_search_by(|x| x.cmp(&6)), Ok(3)); + assert_eq!(b.binary_search_by(|x| x.cmp(&7)), Err(4)); + assert_eq!(b.binary_search_by(|x| x.cmp(&8)), Ok(4)); + + let b: IndexSet = [1, 2, 4, 5, 6, 8].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&9)), Err(6)); + + let b: IndexSet = [1, 2, 4, 6, 7, 8, 9].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&6)), Ok(3)); + assert_eq!(b.binary_search_by(|x| x.cmp(&5)), Err(3)); + assert_eq!(b.binary_search_by(|x| x.cmp(&8)), Ok(5)); + + let b: IndexSet = [1, 2, 4, 5, 6, 8, 9].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&7)), Err(5)); + assert_eq!(b.binary_search_by(|x| x.cmp(&0)), Err(0)); + + let b: IndexSet = [1, 3, 3, 3, 7].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&0)), Err(0)); + assert_eq!(b.binary_search_by(|x| x.cmp(&1)), Ok(0)); + assert_eq!(b.binary_search_by(|x| x.cmp(&2)), Err(1)); + // diff from std as set merges the duplicate keys + assert!(match b.binary_search_by(|x| x.cmp(&3)) { + Ok(1..=2) => true, + _ => false, + }); + assert!(match b.binary_search_by(|x| x.cmp(&3)) { + Ok(1..=2) => true, + _ => false, + }); + assert_eq!(b.binary_search_by(|x| x.cmp(&4)), Err(2)); + assert_eq!(b.binary_search_by(|x| x.cmp(&5)), Err(2)); + assert_eq!(b.binary_search_by(|x| x.cmp(&6)), Err(2)); + assert_eq!(b.binary_search_by(|x| x.cmp(&7)), Ok(2)); + assert_eq!(b.binary_search_by(|x| x.cmp(&8)), Err(3)); +} + +#[test] +fn test_binary_search_by_key() { + // adapted from std's test for binary_search + let b: IndexSet = [].into(); + assert_eq!(b.binary_search_by_key(&5, |&x| x), Err(0)); + + let b: IndexSet = [4].into(); + assert_eq!(b.binary_search_by_key(&3, |&x| x), Err(0)); + assert_eq!(b.binary_search_by_key(&4, |&x| x), Ok(0)); + assert_eq!(b.binary_search_by_key(&5, |&x| x), Err(1)); + + let b: IndexSet = [1, 2, 4, 6, 8, 9].into(); + assert_eq!(b.binary_search_by_key(&5, |&x| x), Err(3)); + assert_eq!(b.binary_search_by_key(&6, |&x| x), Ok(3)); + assert_eq!(b.binary_search_by_key(&7, |&x| x), Err(4)); + assert_eq!(b.binary_search_by_key(&8, |&x| x), Ok(4)); + + let b: IndexSet = [1, 2, 4, 5, 6, 8].into(); + assert_eq!(b.binary_search_by_key(&9, |&x| x), Err(6)); + + let b: IndexSet = [1, 2, 4, 6, 7, 8, 9].into(); + assert_eq!(b.binary_search_by_key(&6, |&x| x), Ok(3)); + assert_eq!(b.binary_search_by_key(&5, |&x| x), Err(3)); + assert_eq!(b.binary_search_by_key(&8, |&x| x), Ok(5)); + + let b: IndexSet = [1, 2, 4, 5, 6, 8, 9].into(); + assert_eq!(b.binary_search_by_key(&7, |&x| x), Err(5)); + assert_eq!(b.binary_search_by_key(&0, |&x| x), Err(0)); + + let b: IndexSet = [1, 3, 3, 3, 7].into(); + assert_eq!(b.binary_search_by_key(&0, |&x| x), Err(0)); + assert_eq!(b.binary_search_by_key(&1, |&x| x), Ok(0)); + assert_eq!(b.binary_search_by_key(&2, |&x| x), Err(1)); + // diff from std as set merges the duplicate keys + assert!(match b.binary_search_by_key(&3, |&x| x) { + Ok(1..=2) => true, + _ => false, + }); + assert!(match b.binary_search_by_key(&3, |&x| x) { + Ok(1..=2) => true, + _ => false, + }); + assert_eq!(b.binary_search_by_key(&4, |&x| x), Err(2)); + assert_eq!(b.binary_search_by_key(&5, |&x| x), Err(2)); + assert_eq!(b.binary_search_by_key(&6, |&x| x), Err(2)); + assert_eq!(b.binary_search_by_key(&7, |&x| x), Ok(2)); + assert_eq!(b.binary_search_by_key(&8, |&x| x), Err(3)); +} + +#[test] +fn test_partition_point() { + // adapted from std's test for partition_point + let b: IndexSet = [].into(); + assert_eq!(b.partition_point(|&x| x < 5), 0); + + let b: IndexSet<_> = [4].into(); + assert_eq!(b.partition_point(|&x| x < 3), 0); + assert_eq!(b.partition_point(|&x| x < 4), 0); + assert_eq!(b.partition_point(|&x| x < 5), 1); + + let b: IndexSet<_> = [1, 2, 4, 6, 8, 9].into(); + assert_eq!(b.partition_point(|&x| x < 5), 3); + assert_eq!(b.partition_point(|&x| x < 6), 3); + assert_eq!(b.partition_point(|&x| x < 7), 4); + assert_eq!(b.partition_point(|&x| x < 8), 4); + + let b: IndexSet<_> = [1, 2, 4, 5, 6, 8].into(); + assert_eq!(b.partition_point(|&x| x < 9), 6); + + let b: IndexSet<_> = [1, 2, 4, 6, 7, 8, 9].into(); + assert_eq!(b.partition_point(|&x| x < 6), 3); + assert_eq!(b.partition_point(|&x| x < 5), 3); + assert_eq!(b.partition_point(|&x| x < 8), 5); + + let b: IndexSet<_> = [1, 2, 4, 5, 6, 8, 9].into(); + assert_eq!(b.partition_point(|&x| x < 7), 5); + assert_eq!(b.partition_point(|&x| x < 0), 0); + + let b: IndexSet<_> = [1, 3, 3, 3, 7].into(); + assert_eq!(b.partition_point(|&x| x < 0), 0); + assert_eq!(b.partition_point(|&x| x < 1), 0); + assert_eq!(b.partition_point(|&x| x < 2), 1); + assert_eq!(b.partition_point(|&x| x < 3), 1); + assert_eq!(b.partition_point(|&x| x < 4), 2); // diff from std as set merges the duplicate keys + assert_eq!(b.partition_point(|&x| x < 5), 2); + assert_eq!(b.partition_point(|&x| x < 6), 2); + assert_eq!(b.partition_point(|&x| x < 7), 2); + assert_eq!(b.partition_point(|&x| x < 8), 3); +} -- cgit v1.2.3