Merging upstream version 1.66.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 203 insertions, 27 deletions

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<Chain<Once<_>, Take<Repeat<_>>>, slice::Iter<_>> =
 ///     chain![once(&0), repeat(&1).take(2), &[2, 3, 5],];
 ///
-/// // ...is equivalant to this:
+/// // ...is equivalent to this:
 /// let with_method: Chain<Chain<Once<_>, Take<Repeat<_>>>, 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<Vec<i32>, 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<<Self::Item as IntoIterator>::IntoIter>
-        where Self: Iterator + Sized,
+        where Self: Sized,
               Self::Item: IntoIterator,
               <Self::Item as IntoIterator>::IntoIter: Clone,
               <Self::Item as IntoIterator>::Item: Clone
@@ -1746,12 +1748,10 @@ pub trait Itertools : Iterator {
     fn find_position<P>(&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<K, F>(self, f: F) -> VecIntoIter<Self::Item>
     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<Self::Item>
+        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<F>(self, mut compare: F) -> Vec<Self::Item>
+        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<K, F>(self, key: F) -> Vec<Self::Item>
+        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<Self::Item>
+        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<F>(self, mut compare: F) -> Vec<Self::Item>
+        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<K, F>(self, key: F) -> Vec<Self::Item>
+        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<T: ?Sized> 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<I, J>(a: I, b: J) -> bool
           J: IntoIterator,
           I::Item: PartialEq<J::Item>
 {
-    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