From 20431706a863f92cb37dc512fef6e48d192aaf2c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:11:38 +0200 Subject: Merging upstream version 1.66.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/itertools/src/lib.rs | 230 ++++++++++++++++++++++++++++++++++++++------ 1 file changed, 203 insertions(+), 27 deletions(-) (limited to 'vendor/itertools/src/lib.rs') diff --git a/vendor/itertools/src/lib.rs b/vendor/itertools/src/lib.rs index df95e19ba..f91968870 100644 --- a/vendor/itertools/src/lib.rs +++ b/vendor/itertools/src/lib.rs @@ -197,6 +197,8 @@ mod combinations_with_replacement; mod exactly_one_err; mod diff; mod flatten_ok; +#[cfg(feature = "use_std")] +mod extrema_set; mod format; #[cfg(feature = "use_std")] mod grouping_map; @@ -387,7 +389,7 @@ macro_rules! izip { /// let with_macro: Chain, Take>>, slice::Iter<_>> = /// chain![once(&0), repeat(&1).take(2), &[2, 3, 5],]; /// -/// // ...is equivalant to this: +/// // ...is equivalent to this: /// let with_method: Chain, Take>>, slice::Iter<_>> = /// once(&0) /// .chain(repeat(&1).take(2)) @@ -778,7 +780,7 @@ pub trait Itertools : Iterator { /// the original iterator. /// /// **Note:** If the iterator is clonable, prefer using that instead - /// of using this method. It is likely to be more efficient. + /// of using this method. Cloning is likely to be more efficient. /// /// Iterator element type is `Self::Item`. /// @@ -904,7 +906,7 @@ pub trait Itertools : Iterator { /// a series of `Result::Ok` values. `Result::Err` values are unchanged. /// /// This is useful when you have some common error type for your crate and - /// need to propogate it upwards, but the `Result::Ok` case needs to be flattened. + /// need to propagate it upwards, but the `Result::Ok` case needs to be flattened. /// /// ``` /// use itertools::Itertools; @@ -913,7 +915,7 @@ pub trait Itertools : Iterator { /// let it = input.iter().cloned().flatten_ok(); /// itertools::assert_equal(it.clone(), vec![Ok(0), Ok(1), Err(false), Ok(2), Ok(3)]); /// - /// // This can also be used to propogate errors when collecting. + /// // This can also be used to propagate errors when collecting. /// let output_result: Result, bool> = it.collect(); /// assert_eq!(output_result, Err(false)); /// ``` @@ -1109,7 +1111,7 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn multi_cartesian_product(self) -> MultiProduct<::IntoIter> - where Self: Iterator + Sized, + where Self: Sized, Self::Item: IntoIterator, ::IntoIter: Clone, ::Item: Clone @@ -1746,12 +1748,10 @@ pub trait Itertools : Iterator { fn find_position

(&mut self, mut pred: P) -> Option<(usize, Self::Item)> where P: FnMut(&Self::Item) -> bool { - let mut index = 0usize; - for elt in self { + for (index, elt) in self.enumerate() { if pred(&elt) { return Some((index, elt)); } - index += 1; } None } @@ -1795,7 +1795,7 @@ pub trait Itertools : Iterator { Some(if predicate(&first) { first } else { - self.find(|x| predicate(&x)).unwrap_or(first) + self.find(|x| predicate(x)).unwrap_or(first) }) } /// Returns `true` if the given item is present in this iterator. @@ -1953,7 +1953,7 @@ pub trait Itertools : Iterator { where F: FnMut(Self::Item), Self: Sized, { - self.for_each(f) + self.for_each(f); } /// Combine all an iterator's elements into one element by using [`Extend`]. @@ -2271,7 +2271,7 @@ pub trait Itertools : Iterator { /// ``` /// /// Which, for non-associative functions, will typically produce a different - /// result than the linear call tree used by `fold1`: + /// result than the linear call tree used by [`Iterator::reduce`]: /// /// ```text /// 1 2 3 4 5 6 7 @@ -2279,7 +2279,7 @@ pub trait Itertools : Iterator { /// └─f─f─f─f─f─f /// ``` /// - /// If `f` is associative, prefer the normal `fold1` instead. + /// If `f` is associative, prefer the normal [`Iterator::reduce`] instead. /// /// ``` /// use itertools::Itertools; @@ -2692,7 +2692,6 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(oldest_people_first, /// vec!["Jill", "Jack", "Jane", "John"]); /// ``` - /// ``` #[cfg(feature = "use_alloc")] fn sorted_by_cached_key(self, f: F) -> VecIntoIter where @@ -2902,6 +2901,194 @@ pub trait Itertools : Iterator { grouping_map::new(grouping_map::MapForGrouping::new(self, key_mapper)) } + /// Return all minimum elements of an iterator. + /// + /// # Examples + /// + /// ``` + /// use itertools::Itertools; + /// + /// let a: [i32; 0] = []; + /// assert_eq!(a.iter().min_set(), Vec::<&i32>::new()); + /// + /// let a = [1]; + /// assert_eq!(a.iter().min_set(), vec![&1]); + /// + /// let a = [1, 2, 3, 4, 5]; + /// assert_eq!(a.iter().min_set(), vec![&1]); + /// + /// let a = [1, 1, 1, 1]; + /// assert_eq!(a.iter().min_set(), vec![&1, &1, &1, &1]); + /// ``` + /// + /// The elements can be floats but no particular result is guaranteed + /// if an element is NaN. + #[cfg(feature = "use_std")] + fn min_set(self) -> Vec + where Self: Sized, Self::Item: Ord + { + extrema_set::min_set_impl(self, |_| (), |x, y, _, _| x.cmp(y)) + } + + /// Return all minimum elements of an iterator, as determined by + /// the specified function. + /// + /// # Examples + /// + /// ``` + /// # use std::cmp::Ordering; + /// use itertools::Itertools; + /// + /// let a: [(i32, i32); 0] = []; + /// assert_eq!(a.iter().min_set_by(|_, _| Ordering::Equal), Vec::<&(i32, i32)>::new()); + /// + /// let a = [(1, 2)]; + /// assert_eq!(a.iter().min_set_by(|&&(k1,_), &&(k2, _)| k1.cmp(&k2)), vec![&(1, 2)]); + /// + /// let a = [(1, 2), (2, 2), (3, 9), (4, 8), (5, 9)]; + /// assert_eq!(a.iter().min_set_by(|&&(_,k1), &&(_,k2)| k1.cmp(&k2)), vec![&(1, 2), &(2, 2)]); + /// + /// let a = [(1, 2), (1, 3), (1, 4), (1, 5)]; + /// assert_eq!(a.iter().min_set_by(|&&(k1,_), &&(k2, _)| k1.cmp(&k2)), vec![&(1, 2), &(1, 3), &(1, 4), &(1, 5)]); + /// ``` + /// + /// The elements can be floats but no particular result is guaranteed + /// if an element is NaN. + #[cfg(feature = "use_std")] + fn min_set_by(self, mut compare: F) -> Vec + where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering + { + extrema_set::min_set_impl( + self, + |_| (), + |x, y, _, _| compare(x, y) + ) + } + + /// Return all minimum elements of an iterator, as determined by + /// the specified function. + /// + /// # Examples + /// + /// ``` + /// use itertools::Itertools; + /// + /// let a: [(i32, i32); 0] = []; + /// assert_eq!(a.iter().min_set_by_key(|_| ()), Vec::<&(i32, i32)>::new()); + /// + /// let a = [(1, 2)]; + /// assert_eq!(a.iter().min_set_by_key(|&&(k,_)| k), vec![&(1, 2)]); + /// + /// let a = [(1, 2), (2, 2), (3, 9), (4, 8), (5, 9)]; + /// assert_eq!(a.iter().min_set_by_key(|&&(_, k)| k), vec![&(1, 2), &(2, 2)]); + /// + /// let a = [(1, 2), (1, 3), (1, 4), (1, 5)]; + /// assert_eq!(a.iter().min_set_by_key(|&&(k, _)| k), vec![&(1, 2), &(1, 3), &(1, 4), &(1, 5)]); + /// ``` + /// + /// The elements can be floats but no particular result is guaranteed + /// if an element is NaN. + #[cfg(feature = "use_std")] + fn min_set_by_key(self, key: F) -> Vec + where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K + { + extrema_set::min_set_impl(self, key, |_, _, kx, ky| kx.cmp(ky)) + } + + /// Return all maximum elements of an iterator. + /// + /// # Examples + /// + /// ``` + /// use itertools::Itertools; + /// + /// let a: [i32; 0] = []; + /// assert_eq!(a.iter().max_set(), Vec::<&i32>::new()); + /// + /// let a = [1]; + /// assert_eq!(a.iter().max_set(), vec![&1]); + /// + /// let a = [1, 2, 3, 4, 5]; + /// assert_eq!(a.iter().max_set(), vec![&5]); + /// + /// let a = [1, 1, 1, 1]; + /// assert_eq!(a.iter().max_set(), vec![&1, &1, &1, &1]); + /// ``` + /// + /// The elements can be floats but no particular result is guaranteed + /// if an element is NaN. + #[cfg(feature = "use_std")] + fn max_set(self) -> Vec + where Self: Sized, Self::Item: Ord + { + extrema_set::max_set_impl(self, |_| (), |x, y, _, _| x.cmp(y)) + } + + /// Return all maximum elements of an iterator, as determined by + /// the specified function. + /// + /// # Examples + /// + /// ``` + /// # use std::cmp::Ordering; + /// use itertools::Itertools; + /// + /// let a: [(i32, i32); 0] = []; + /// assert_eq!(a.iter().max_set_by(|_, _| Ordering::Equal), Vec::<&(i32, i32)>::new()); + /// + /// let a = [(1, 2)]; + /// assert_eq!(a.iter().max_set_by(|&&(k1,_), &&(k2, _)| k1.cmp(&k2)), vec![&(1, 2)]); + /// + /// let a = [(1, 2), (2, 2), (3, 9), (4, 8), (5, 9)]; + /// assert_eq!(a.iter().max_set_by(|&&(_,k1), &&(_,k2)| k1.cmp(&k2)), vec![&(3, 9), &(5, 9)]); + /// + /// let a = [(1, 2), (1, 3), (1, 4), (1, 5)]; + /// assert_eq!(a.iter().max_set_by(|&&(k1,_), &&(k2, _)| k1.cmp(&k2)), vec![&(1, 2), &(1, 3), &(1, 4), &(1, 5)]); + /// ``` + /// + /// The elements can be floats but no particular result is guaranteed + /// if an element is NaN. + #[cfg(feature = "use_std")] + fn max_set_by(self, mut compare: F) -> Vec + where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering + { + extrema_set::max_set_impl( + self, + |_| (), + |x, y, _, _| compare(x, y) + ) + } + + /// Return all minimum elements of an iterator, as determined by + /// the specified function. + /// + /// # Examples + /// + /// ``` + /// use itertools::Itertools; + /// + /// let a: [(i32, i32); 0] = []; + /// assert_eq!(a.iter().max_set_by_key(|_| ()), Vec::<&(i32, i32)>::new()); + /// + /// let a = [(1, 2)]; + /// assert_eq!(a.iter().max_set_by_key(|&&(k,_)| k), vec![&(1, 2)]); + /// + /// let a = [(1, 2), (2, 2), (3, 9), (4, 8), (5, 9)]; + /// assert_eq!(a.iter().max_set_by_key(|&&(_, k)| k), vec![&(3, 9), &(5, 9)]); + /// + /// let a = [(1, 2), (1, 3), (1, 4), (1, 5)]; + /// assert_eq!(a.iter().max_set_by_key(|&&(k, _)| k), vec![&(1, 2), &(1, 3), &(1, 4), &(1, 5)]); + /// ``` + /// + /// The elements can be floats but no particular result is guaranteed + /// if an element is NaN. + #[cfg(feature = "use_std")] + fn max_set_by_key(self, key: F) -> Vec + where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K + { + extrema_set::max_set_impl(self, key, |_, _, kx, ky| kx.cmp(ky)) + } + /// Return the minimum and maximum elements in the iterator. /// /// The return type `MinMaxResult` is an enum of three variants: @@ -3157,7 +3344,7 @@ pub trait Itertools : Iterator { /// be equal to `ypos`. /// /// On an iterator of length `n`, `position_minmax` does `1.5 * n` - /// comparisons, and so is faster than calling `positon_min` and + /// comparisons, and so is faster than calling `position_min` and /// `position_max` separately which does `2 * n` comparisons. /// /// For the minimum, if several elements are equally minimum, the @@ -3478,8 +3665,7 @@ impl Itertools for T where T: Iterator { } /// (elements pairwise equal and sequences of the same length), /// `false` otherwise. /// -/// This is an [`IntoIterator`] enabled function that is similar to the standard -/// library method [`Iterator::eq`]. +/// [`IntoIterator`] enabled version of [`Iterator::eq`]. /// /// ``` /// assert!(itertools::equal(vec![1, 2, 3], 1..4)); @@ -3490,17 +3676,7 @@ pub fn equal(a: I, b: J) -> bool J: IntoIterator, I::Item: PartialEq { - let mut ia = a.into_iter(); - let mut ib = b.into_iter(); - loop { - match ia.next() { - Some(x) => match ib.next() { - Some(y) => if x != y { return false; }, - None => return false, - }, - None => return ib.next().is_none() - } - } + a.into_iter().eq(b) } /// Assert that two iterables produce equal sequences, with the same -- cgit v1.2.3