diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-06-19 09:26:03 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-06-19 09:26:03 +0000 |
commit | 9918693037dce8aa4bb6f08741b6812923486c18 (patch) | |
tree | 21d2b40bec7e6a7ea664acee056eb3d08e15a1cf /vendor/itertools/src | |
parent | Releasing progress-linux version 1.75.0+dfsg1-5~progress7.99u1. (diff) | |
download | rustc-9918693037dce8aa4bb6f08741b6812923486c18.tar.xz rustc-9918693037dce8aa4bb6f08741b6812923486c18.zip |
Merging upstream version 1.76.0+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/itertools/src')
44 files changed, 2604 insertions, 1754 deletions
diff --git a/vendor/itertools/src/adaptors/mod.rs b/vendor/itertools/src/adaptors/mod.rs index 1695bbd65..e925db51d 100644 --- a/vendor/itertools/src/adaptors/mod.rs +++ b/vendor/itertools/src/adaptors/mod.rs @@ -8,16 +8,16 @@ mod coalesce; mod map; mod multi_product; pub use self::coalesce::*; -pub use self::map::{map_into, map_ok, MapInto, MapOk}; #[allow(deprecated)] pub use self::map::MapResults; +pub use self::map::{map_into, map_ok, MapInto, MapOk}; #[cfg(feature = "use_alloc")] pub use self::multi_product::*; +use crate::size_hint::{self, SizeHint}; use std::fmt; -use std::iter::{Fuse, Peekable, FromIterator, FusedIterator}; +use std::iter::{FromIterator, Fuse, FusedIterator}; use std::marker::PhantomData; -use crate::size_hint; /// An iterator adaptor that alternates elements from two iterators until both /// run out. @@ -36,9 +36,13 @@ pub struct Interleave<I, J> { /// Create an iterator that interleaves elements in `i` and `j`. /// /// [`IntoIterator`] enabled version of `[Itertools::interleave]`. -pub fn interleave<I, J>(i: I, j: J) -> Interleave<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter> - where I: IntoIterator, - J: IntoIterator<Item = I::Item> +pub fn interleave<I, J>( + i: I, + j: J, +) -> Interleave<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter> +where + I: IntoIterator, + J: IntoIterator<Item = I::Item>, { Interleave { a: i.into_iter().fuse(), @@ -48,8 +52,9 @@ pub fn interleave<I, J>(i: I, j: J) -> Interleave<<I as IntoIterator>::IntoIter, } impl<I, J> Iterator for Interleave<I, J> - where I: Iterator, - J: Iterator<Item = I::Item> +where + I: Iterator, + J: Iterator<Item = I::Item>, { type Item = I::Item; #[inline] @@ -74,9 +79,11 @@ impl<I, J> Iterator for Interleave<I, J> } impl<I, J> FusedIterator for Interleave<I, J> - where I: Iterator, - J: Iterator<Item = I::Item> -{} +where + I: Iterator, + J: Iterator<Item = I::Item>, +{ +} /// An iterator adaptor that alternates elements from the two iterators until /// one of them runs out. @@ -88,8 +95,9 @@ impl<I, J> FusedIterator for Interleave<I, J> #[derive(Clone, Debug)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct InterleaveShortest<I, J> - where I: Iterator, - J: Iterator<Item = I::Item> +where + I: Iterator, + J: Iterator<Item = I::Item>, { it0: I, it1: J, @@ -98,8 +106,9 @@ pub struct InterleaveShortest<I, J> /// Create a new `InterleaveShortest` iterator. pub fn interleave_shortest<I, J>(a: I, b: J) -> InterleaveShortest<I, J> - where I: Iterator, - J: Iterator<Item = I::Item> +where + I: Iterator, + J: Iterator<Item = I::Item>, { InterleaveShortest { it0: a, @@ -109,14 +118,19 @@ pub fn interleave_shortest<I, J>(a: I, b: J) -> InterleaveShortest<I, J> } impl<I, J> Iterator for InterleaveShortest<I, J> - where I: Iterator, - J: Iterator<Item = I::Item> +where + I: Iterator, + J: Iterator<Item = I::Item>, { type Item = I::Item; #[inline] fn next(&mut self) -> Option<Self::Item> { - let e = if self.phase { self.it1.next() } else { self.it0.next() }; + let e = if self.phase { + self.it1.next() + } else { + self.it0.next() + }; if e.is_some() { self.phase = !self.phase; } @@ -138,12 +152,11 @@ impl<I, J> Iterator for InterleaveShortest<I, J> let (next_lower, next_upper) = next_hint; let (combined_lower, combined_upper) = size_hint::mul_scalar(size_hint::min(curr_hint, next_hint), 2); - let lower = - if curr_lower > next_lower { - combined_lower + 1 - } else { - combined_lower - }; + let lower = if curr_lower > next_lower { + combined_lower + 1 + } else { + combined_lower + }; let upper = { let extra_elem = match (curr_upper, next_upper) { (_, None) => false, @@ -161,17 +174,21 @@ impl<I, J> Iterator for InterleaveShortest<I, J> } impl<I, J> FusedIterator for InterleaveShortest<I, J> - where I: FusedIterator, - J: FusedIterator<Item = I::Item> -{} +where + I: FusedIterator, + J: FusedIterator<Item = I::Item>, +{ +} #[derive(Clone, Debug)] /// An iterator adaptor that allows putting back a single /// item to the front of the iterator. /// /// Iterator element type is `I::Item`. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct PutBack<I> - where I: Iterator +where + I: Iterator, { top: Option<I::Item>, iter: I, @@ -179,7 +196,8 @@ pub struct PutBack<I> /// Create an iterator where you can put back a single item pub fn put_back<I>(iterable: I) -> PutBack<I::IntoIter> - where I: IntoIterator +where + I: IntoIterator, { PutBack { top: None, @@ -188,7 +206,8 @@ pub fn put_back<I>(iterable: I) -> PutBack<I::IntoIter> } impl<I> PutBack<I> - where I: Iterator +where + I: Iterator, { /// put back value `value` (builder method) pub fn with_value(mut self, value: I::Item) -> Self { @@ -199,7 +218,7 @@ impl<I> PutBack<I> /// Split the `PutBack` into its parts. #[inline] pub fn into_parts(self) -> (Option<I::Item>, I) { - let PutBack{top, iter} = self; + let PutBack { top, iter } = self; (top, iter) } @@ -213,7 +232,8 @@ impl<I> PutBack<I> } impl<I> Iterator for PutBack<I> - where I: Iterator +where + I: Iterator, { type Item = I::Item; #[inline] @@ -252,7 +272,8 @@ impl<I> Iterator for PutBack<I> } fn all<G>(&mut self, mut f: G) -> bool - where G: FnMut(Self::Item) -> bool + where + G: FnMut(Self::Item) -> bool, { if let Some(elt) = self.top.take() { if !f(elt) { @@ -263,7 +284,8 @@ impl<I> Iterator for PutBack<I> } fn fold<Acc, G>(mut self, init: Acc, mut f: G) -> Acc - where G: FnMut(Acc, Self::Item) -> Acc, + where + G: FnMut(Acc, Self::Item) -> Acc, { let mut accum = init; if let Some(elt) = self.top.take() { @@ -282,10 +304,14 @@ impl<I> Iterator for PutBack<I> /// See [`.cartesian_product()`](crate::Itertools::cartesian_product) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Product<I, J> - where I: Iterator +where + I: Iterator, { a: I, - a_cur: Option<I::Item>, + /// `a_cur` is `None` while no item have been taken out of `a` (at definition). + /// Then `a_cur` will be `Some(Some(item))` until `a` is exhausted, + /// in which case `a_cur` will be `Some(None)`. + a_cur: Option<Option<I::Item>>, b: J, b_orig: J, } @@ -293,13 +319,14 @@ pub struct Product<I, J> /// Create a new cartesian product iterator /// /// Iterator element type is `(I::Item, J::Item)`. -pub fn cartesian_product<I, J>(mut i: I, j: J) -> Product<I, J> - where I: Iterator, - J: Clone + Iterator, - I::Item: Clone +pub fn cartesian_product<I, J>(i: I, j: J) -> Product<I, J> +where + I: Iterator, + J: Clone + Iterator, + I::Item: Clone, { Product { - a_cur: i.next(), + a_cur: None, a: i, b: j.clone(), b_orig: j, @@ -307,54 +334,69 @@ pub fn cartesian_product<I, J>(mut i: I, j: J) -> Product<I, J> } impl<I, J> Iterator for Product<I, J> - where I: Iterator, - J: Clone + Iterator, - I::Item: Clone +where + I: Iterator, + J: Clone + Iterator, + I::Item: Clone, { type Item = (I::Item, J::Item); fn next(&mut self) -> Option<Self::Item> { - let elt_b = match self.b.next() { + let Self { + a, + a_cur, + b, + b_orig, + } = self; + let elt_b = match b.next() { None => { - self.b = self.b_orig.clone(); - match self.b.next() { + *b = b_orig.clone(); + match b.next() { None => return None, Some(x) => { - self.a_cur = self.a.next(); + *a_cur = Some(a.next()); x } } } - Some(x) => x + Some(x) => x, }; - self.a_cur.as_ref().map(|a| (a.clone(), elt_b)) + a_cur + .get_or_insert_with(|| a.next()) + .as_ref() + .map(|a| (a.clone(), elt_b)) } fn size_hint(&self) -> (usize, Option<usize>) { - let has_cur = self.a_cur.is_some() as usize; // Not ExactSizeIterator because size may be larger than usize - let (b_min, b_max) = self.b.size_hint(); - // Compute a * b_orig + b for both lower and upper bound - size_hint::add( - size_hint::mul(self.a.size_hint(), self.b_orig.size_hint()), - (b_min * has_cur, b_max.map(move |x| x * has_cur))) + let mut sh = size_hint::mul(self.a.size_hint(), self.b_orig.size_hint()); + if matches!(self.a_cur, Some(Some(_))) { + sh = size_hint::add(sh, self.b.size_hint()); + } + sh } - fn fold<Acc, G>(mut self, mut accum: Acc, mut f: G) -> Acc - where G: FnMut(Acc, Self::Item) -> Acc, + fn fold<Acc, G>(self, mut accum: Acc, mut f: G) -> Acc + where + G: FnMut(Acc, Self::Item) -> Acc, { // use a split loop to handle the loose a_cur as well as avoiding to // clone b_orig at the end. - if let Some(mut a) = self.a_cur.take() { - let mut b = self.b; + let Self { + mut a, + a_cur, + mut b, + b_orig, + } = self; + if let Some(mut elt_a) = a_cur.unwrap_or_else(|| a.next()) { loop { - accum = b.fold(accum, |acc, elt| f(acc, (a.clone(), elt))); + accum = b.fold(accum, |acc, elt| f(acc, (elt_a.clone(), elt))); // we can only continue iterating a if we had a first element; - if let Some(next_a) = self.a.next() { - b = self.b_orig.clone(); - a = next_a; + if let Some(next_elt_a) = a.next() { + b = b_orig.clone(); + elt_a = next_elt_a; } else { break; } @@ -365,10 +407,12 @@ impl<I, J> Iterator for Product<I, J> } impl<I, J> FusedIterator for Product<I, J> - where I: FusedIterator, - J: Clone + FusedIterator, - I::Item: Clone -{} +where + I: FusedIterator, + J: Clone + FusedIterator, + I::Item: Clone, +{ +} /// A “meta iterator adaptor”. Its closure receives a reference to the iterator /// and may pick off as many elements as it likes, to produce the next iterator element. @@ -383,7 +427,10 @@ pub struct Batching<I, F> { iter: I, } -impl<I, F> fmt::Debug for Batching<I, F> where I: fmt::Debug { +impl<I, F> fmt::Debug for Batching<I, F> +where + I: fmt::Debug, +{ debug_fmt_fields!(Batching, iter); } @@ -393,8 +440,9 @@ pub fn batching<I, F>(iter: I, f: F) -> Batching<I, F> { } impl<B, F, I> Iterator for Batching<I, F> - where I: Iterator, - F: FnMut(&mut I) -> Option<B> +where + I: Iterator, + F: FnMut(&mut I) -> Option<B>, { type Item = B; #[inline] @@ -410,7 +458,7 @@ impl<B, F, I> Iterator for Batching<I, F> /// then skipping forward *n-1* elements. /// /// See [`.step()`](crate::Itertools::step) for more information. -#[deprecated(note="Use std .step_by() instead", since="0.8.0")] +#[deprecated(note = "Use std .step_by() instead", since = "0.8.0")] #[allow(deprecated)] #[derive(Clone, Debug)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] @@ -424,7 +472,8 @@ pub struct Step<I> { /// **Panics** if the step is 0. #[allow(deprecated)] pub fn step<I>(iter: I, step: usize) -> Step<I> - where I: Iterator +where + I: Iterator, { assert!(step != 0); Step { @@ -435,7 +484,8 @@ pub fn step<I>(iter: I, step: usize) -> Step<I> #[allow(deprecated)] impl<I> Iterator for Step<I> - where I: Iterator +where + I: Iterator, { type Item = I::Item; #[inline] @@ -462,145 +512,7 @@ impl<I> Iterator for Step<I> // known size #[allow(deprecated)] -impl<I> ExactSizeIterator for Step<I> - where I: ExactSizeIterator -{} - -pub trait MergePredicate<T> { - fn merge_pred(&mut self, a: &T, b: &T) -> bool; -} - -#[derive(Clone, Debug)] -pub struct MergeLte; - -impl<T: PartialOrd> MergePredicate<T> for MergeLte { - fn merge_pred(&mut self, a: &T, b: &T) -> bool { - a <= b - } -} - -/// An iterator adaptor that merges the two base iterators in ascending order. -/// If both base iterators are sorted (ascending), the result is sorted. -/// -/// Iterator element type is `I::Item`. -/// -/// See [`.merge()`](crate::Itertools::merge_by) for more information. -pub type Merge<I, J> = MergeBy<I, J, MergeLte>; - -/// Create an iterator that merges elements in `i` and `j`. -/// -/// [`IntoIterator`] enabled version of [`Itertools::merge`](crate::Itertools::merge). -/// -/// ``` -/// use itertools::merge; -/// -/// for elt in merge(&[1, 2, 3], &[2, 3, 4]) { -/// /* loop body */ -/// } -/// ``` -pub fn merge<I, J>(i: I, j: J) -> Merge<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter> - where I: IntoIterator, - J: IntoIterator<Item = I::Item>, - I::Item: PartialOrd -{ - merge_by_new(i, j, MergeLte) -} - -/// An iterator adaptor that merges the two base iterators in ascending order. -/// If both base iterators are sorted (ascending), the result is sorted. -/// -/// Iterator element type is `I::Item`. -/// -/// See [`.merge_by()`](crate::Itertools::merge_by) for more information. -#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] -pub struct MergeBy<I, J, F> - where I: Iterator, - J: Iterator<Item = I::Item> -{ - a: Peekable<I>, - b: Peekable<J>, - fused: Option<bool>, - cmp: F, -} - -impl<I, J, F> fmt::Debug for MergeBy<I, J, F> - where I: Iterator + fmt::Debug, J: Iterator<Item = I::Item> + fmt::Debug, - I::Item: fmt::Debug, -{ - debug_fmt_fields!(MergeBy, a, b); -} - -impl<T, F: FnMut(&T, &T)->bool> MergePredicate<T> for F { - fn merge_pred(&mut self, a: &T, b: &T) -> bool { - self(a, b) - } -} - -/// Create a `MergeBy` iterator. -pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I::IntoIter, J::IntoIter, F> - where I: IntoIterator, - J: IntoIterator<Item = I::Item>, - F: MergePredicate<I::Item>, -{ - MergeBy { - a: a.into_iter().peekable(), - b: b.into_iter().peekable(), - fused: None, - cmp, - } -} - -impl<I, J, F> Clone for MergeBy<I, J, F> - where I: Iterator, - J: Iterator<Item = I::Item>, - Peekable<I>: Clone, - Peekable<J>: Clone, - F: Clone -{ - clone_fields!(a, b, fused, cmp); -} - -impl<I, J, F> Iterator for MergeBy<I, J, F> - where I: Iterator, - J: Iterator<Item = I::Item>, - F: MergePredicate<I::Item> -{ - type Item = I::Item; - - fn next(&mut self) -> Option<Self::Item> { - let less_than = match self.fused { - Some(lt) => lt, - None => match (self.a.peek(), self.b.peek()) { - (Some(a), Some(b)) => self.cmp.merge_pred(a, b), - (Some(_), None) => { - self.fused = Some(true); - true - } - (None, Some(_)) => { - self.fused = Some(false); - false - } - (None, None) => return None, - } - }; - if less_than { - self.a.next() - } else { - self.b.next() - } - } - - fn size_hint(&self) -> (usize, Option<usize>) { - // Not ExactSizeIterator because size may be larger than usize - size_hint::add(self.a.size_hint(), self.b.size_hint()) - } -} - -impl<I, J, F> FusedIterator for MergeBy<I, J, F> - where I: FusedIterator, - J: FusedIterator<Item = I::Item>, - F: MergePredicate<I::Item> -{} +impl<I> ExactSizeIterator for Step<I> where I: ExactSizeIterator {} /// An iterator adaptor that borrows from a `Clone`-able iterator /// to only pick off elements while the predicate returns `true`. @@ -613,21 +525,24 @@ pub struct TakeWhileRef<'a, I: 'a, F> { } impl<'a, I, F> fmt::Debug for TakeWhileRef<'a, I, F> - where I: Iterator + fmt::Debug, +where + I: Iterator + fmt::Debug, { debug_fmt_fields!(TakeWhileRef, iter); } /// Create a new `TakeWhileRef` from a reference to clonable iterator. pub fn take_while_ref<I, F>(iter: &mut I, f: F) -> TakeWhileRef<I, F> - where I: Iterator + Clone +where + I: Iterator + Clone, { TakeWhileRef { iter, f } } impl<'a, I, F> Iterator for TakeWhileRef<'a, I, F> - where I: Iterator + Clone, - F: FnMut(&I::Item) -> bool +where + I: Iterator + Clone, + F: FnMut(&I::Item) -> bool, { type Item = I::Item; @@ -667,7 +582,8 @@ pub fn while_some<I>(iter: I) -> WhileSome<I> { } impl<I, A> Iterator for WhileSome<I> - where I: Iterator<Item = Option<A>> +where + I: Iterator<Item = Option<A>>, { type Item = A; @@ -681,6 +597,22 @@ impl<I, A> Iterator for WhileSome<I> fn size_hint(&self) -> (usize, Option<usize>) { (0, self.iter.size_hint().1) } + + fn fold<B, F>(mut self, acc: B, mut f: F) -> B + where + Self: Sized, + F: FnMut(B, Self::Item) -> B, + { + let res = self.iter.try_fold(acc, |acc, item| match item { + Some(item) => Ok(f(acc, item)), + None => Err(acc), + }); + let res = match res { + Ok(val) => val, + Err(val) => val, + }; + res + } } /// An iterator to iterate through all combinations in a `Clone`-able iterator that produces tuples @@ -691,8 +623,9 @@ impl<I, A> Iterator for WhileSome<I> #[derive(Clone, Debug)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct TupleCombinations<I, T> - where I: Iterator, - T: HasCombination<I> +where + I: Iterator, + T: HasCombination<I>, { iter: T::Combination, _mi: PhantomData<I>, @@ -704,9 +637,10 @@ pub trait HasCombination<I>: Sized { /// Create a new `TupleCombinations` from a clonable iterator. pub fn tuple_combinations<T, I>(iter: I) -> TupleCombinations<I, T> - where I: Iterator + Clone, - I::Item: Clone, - T: HasCombination<I>, +where + I: Iterator + Clone, + I::Item: Clone, + T: HasCombination<I>, { TupleCombinations { iter: T::Combination::from(iter), @@ -715,20 +649,38 @@ pub fn tuple_combinations<T, I>(iter: I) -> TupleCombinations<I, T> } impl<I, T> Iterator for TupleCombinations<I, T> - where I: Iterator, - T: HasCombination<I>, +where + I: Iterator, + T: HasCombination<I>, { type Item = T; fn next(&mut self) -> Option<Self::Item> { self.iter.next() } + + fn size_hint(&self) -> SizeHint { + self.iter.size_hint() + } + + fn count(self) -> usize { + self.iter.count() + } + + fn fold<B, F>(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, f) + } } impl<I, T> FusedIterator for TupleCombinations<I, T> - where I: FusedIterator, - T: HasCombination<I>, -{} +where + I: FusedIterator, + T: HasCombination<I>, +{ +} #[derive(Clone, Debug)] pub struct Tuple1Combination<I> { @@ -747,6 +699,21 @@ impl<I: Iterator> Iterator for Tuple1Combination<I> { fn next(&mut self) -> Option<Self::Item> { self.iter.next().map(|x| (x,)) } + + fn size_hint(&self) -> SizeHint { + self.iter.size_hint() + } + + fn count(self) -> usize { + self.iter.count() + } + + fn fold<B, F>(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.map(|x| (x,)).fold(init, f) + } } impl<I: Iterator> HasCombination<I> for (I::Item,) { @@ -780,22 +747,55 @@ macro_rules! impl_tuple_combination { impl<I, A> Iterator for $C<I> where I: Iterator<Item = A> + Clone, - I::Item: Clone + A: Clone, { type Item = (A, $(ignore_ident!($X, A)),*); fn next(&mut self) -> Option<Self::Item> { - if let Some(($($X),*,)) = self.c.next() { + if let Some(($($X,)*)) = self.c.next() { let z = self.item.clone().unwrap(); Some((z, $($X),*)) } else { self.item = self.iter.next(); self.item.clone().and_then(|z| { self.c = self.iter.clone().into(); - self.c.next().map(|($($X),*,)| (z, $($X),*)) + self.c.next().map(|($($X,)*)| (z, $($X),*)) }) } } + + fn size_hint(&self) -> SizeHint { + const K: usize = 1 + count_ident!($($X)*); + let (mut n_min, mut n_max) = self.iter.size_hint(); + n_min = checked_binomial(n_min, K).unwrap_or(usize::MAX); + n_max = n_max.and_then(|n| checked_binomial(n, K)); + size_hint::add(self.c.size_hint(), (n_min, n_max)) + } + + fn count(self) -> usize { + const K: usize = 1 + count_ident!($($X)*); + let n = self.iter.count(); + checked_binomial(n, K).unwrap() + self.c.count() + } + + fn fold<B, F>(self, mut init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + let Self { c, item, mut iter } = self; + if let Some(z) = item.as_ref() { + init = c + .map(|($($X,)*)| (z.clone(), $($X),*)) + .fold(init, &mut f); + } + while let Some(z) = iter.next() { + let c: $P<I> = iter.clone().into(); + init = c + .map(|($($X,)*)| (z.clone(), $($X),*)) + .fold(init, &mut f); + } + init + } } impl<I, A> HasCombination<I> for (A, $(ignore_ident!($X, A)),*) @@ -831,6 +831,42 @@ impl_tuple_combination!(Tuple10Combination Tuple9Combination; a b c d e f g h i) impl_tuple_combination!(Tuple11Combination Tuple10Combination; a b c d e f g h i j); impl_tuple_combination!(Tuple12Combination Tuple11Combination; a b c d e f g h i j k); +// https://en.wikipedia.org/wiki/Binomial_coefficient#In_programming_languages +pub(crate) fn checked_binomial(mut n: usize, mut k: usize) -> Option<usize> { + if n < k { + return Some(0); + } + // `factorial(n) / factorial(n - k) / factorial(k)` but trying to avoid it overflows: + k = (n - k).min(k); // symmetry + let mut c = 1; + for i in 1..=k { + c = (c / i) + .checked_mul(n)? + .checked_add((c % i).checked_mul(n)? / i)?; + n -= 1; + } + Some(c) +} + +#[test] +fn test_checked_binomial() { + // With the first row: [1, 0, 0, ...] and the first column full of 1s, we check + // row by row the recurrence relation of binomials (which is an equivalent definition). + // For n >= 1 and k >= 1 we have: + // binomial(n, k) == binomial(n - 1, k - 1) + binomial(n - 1, k) + const LIMIT: usize = 500; + let mut row = vec![Some(0); LIMIT + 1]; + row[0] = Some(1); + for n in 0..=LIMIT { + for k in 0..=LIMIT { + assert_eq!(row[k], checked_binomial(n, k)); + } + row = std::iter::once(Some(1)) + .chain((1..=LIMIT).map(|k| row[k - 1]?.checked_add(row[k]?))) + .collect(); + } +} + /// An iterator adapter to filter values within a nested `Result::Ok`. /// /// See [`.filter_ok()`](crate::Itertools::filter_ok) for more information. @@ -838,7 +874,7 @@ impl_tuple_combination!(Tuple12Combination Tuple11Combination; a b c d e f g h i #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct FilterOk<I, F> { iter: I, - f: F + f: F, } impl<I, F> fmt::Debug for FilterOk<I, F> @@ -850,18 +886,17 @@ where /// Create a new `FilterOk` iterator. pub fn filter_ok<I, F, T, E>(iter: I, f: F) -> FilterOk<I, F> - where I: Iterator<Item = Result<T, E>>, - F: FnMut(&T) -> bool, +where + I: Iterator<Item = Result<T, E>>, + F: FnMut(&T) -> bool, { - FilterOk { - iter, - f, - } + FilterOk { iter, f } } impl<I, F, T, E> Iterator for FilterOk<I, F> - where I: Iterator<Item = Result<T, E>>, - F: FnMut(&T) -> bool, +where + I: Iterator<Item = Result<T, E>>, + F: FnMut(&T) -> bool, { type Item = Result<T, E>; @@ -872,7 +907,7 @@ impl<I, F, T, E> Iterator for FilterOk<I, F> if (self.f)(&v) { return Some(Ok(v)); } - }, + } Some(Err(e)) => return Some(Err(e)), None => return None, } @@ -884,36 +919,41 @@ impl<I, F, T, E> Iterator for FilterOk<I, F> } fn fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc - where Fold: FnMut(Acc, Self::Item) -> Acc, + where + Fold: FnMut(Acc, Self::Item) -> Acc, { let mut f = self.f; - self.iter.filter(|v| { - v.as_ref().map(&mut f).unwrap_or(true) - }).fold(init, fold_f) + self.iter + .filter(|v| v.as_ref().map(&mut f).unwrap_or(true)) + .fold(init, fold_f) } fn collect<C>(self) -> C - where C: FromIterator<Self::Item> + where + C: FromIterator<Self::Item>, { let mut f = self.f; - self.iter.filter(|v| { - v.as_ref().map(&mut f).unwrap_or(true) - }).collect() + self.iter + .filter(|v| v.as_ref().map(&mut f).unwrap_or(true)) + .collect() } } impl<I, F, T, E> FusedIterator for FilterOk<I, F> - where I: FusedIterator<Item = Result<T, E>>, - F: FnMut(&T) -> bool, -{} +where + I: FusedIterator<Item = Result<T, E>>, + F: FnMut(&T) -> bool, +{ +} /// An iterator adapter to filter and apply a transformation on values within a nested `Result::Ok`. /// /// See [`.filter_map_ok()`](crate::Itertools::filter_map_ok) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +#[derive(Clone)] pub struct FilterMapOk<I, F> { iter: I, - f: F + f: F, } impl<I, F> fmt::Debug for FilterMapOk<I, F> @@ -933,18 +973,17 @@ fn transpose_result<T, E>(result: Result<Option<T>, E>) -> Option<Result<T, E>> /// Create a new `FilterOk` iterator. pub fn filter_map_ok<I, F, T, U, E>(iter: I, f: F) -> FilterMapOk<I, F> - where I: Iterator<Item = Result<T, E>>, - F: FnMut(T) -> Option<U>, +where + I: Iterator<Item = Result<T, E>>, + F: FnMut(T) -> Option<U>, { - FilterMapOk { - iter, - f, - } + FilterMapOk { iter, f } } impl<I, F, T, U, E> Iterator for FilterMapOk<I, F> - where I: Iterator<Item = Result<T, E>>, - F: FnMut(T) -> Option<U>, +where + I: Iterator<Item = Result<T, E>>, + F: FnMut(T) -> Option<U>, { type Item = Result<U, E>; @@ -955,7 +994,7 @@ impl<I, F, T, U, E> Iterator for FilterMapOk<I, F> if let Some(v) = (self.f)(v) { return Some(Ok(v)); } - }, + } Some(Err(e)) => return Some(Err(e)), None => return None, } @@ -967,28 +1006,32 @@ impl<I, F, T, U, E> Iterator for FilterMapOk<I, F> } fn fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc - where Fold: FnMut(Acc, Self::Item) -> Acc, + where + Fold: FnMut(Acc, Self::Item) -> Acc, { let mut f = self.f; - self.iter.filter_map(|v| { - transpose_result(v.map(&mut f)) - }).fold(init, fold_f) + self.iter + .filter_map(|v| transpose_result(v.map(&mut f))) + .fold(init, fold_f) } fn collect<C>(self) -> C - where C: FromIterator<Self::Item> + where + C: FromIterator<Self::Item>, { let mut f = self.f; - self.iter.filter_map(|v| { - transpose_result(v.map(&mut f)) - }).collect() + self.iter + .filter_map(|v| transpose_result(v.map(&mut f))) + .collect() } } impl<I, F, T, U, E> FusedIterator for FilterMapOk<I, F> - where I: FusedIterator<Item = Result<T, E>>, - F: FnMut(T) -> Option<U>, -{} +where + I: FusedIterator<Item = Result<T, E>>, + F: FnMut(T) -> Option<U>, +{ +} /// An iterator adapter to get the positions of each element that matches a predicate. /// @@ -1010,19 +1053,17 @@ where /// Create a new `Positions` iterator. pub fn positions<I, F>(iter: I, f: F) -> Positions<I, F> - where I: Iterator, - F: FnMut(I::Item) -> bool, +where + I: Iterator, + F: FnMut(I::Item) -> bool, { - Positions { - iter, - f, - count: 0 - } + Positions { iter, f, count: 0 } } impl<I, F> Iterator for Positions<I, F> - where I: Iterator, - F: FnMut(I::Item) -> bool, +where + I: Iterator, + F: FnMut(I::Item) -> bool, { type Item = usize; @@ -1043,13 +1084,14 @@ impl<I, F> Iterator for Positions<I, F> } impl<I, F> DoubleEndedIterator for Positions<I, F> - where I: DoubleEndedIterator + ExactSizeIterator, - F: FnMut(I::Item) -> bool, +where + I: DoubleEndedIterator + ExactSizeIterator, + F: FnMut(I::Item) -> bool, { fn next_back(&mut self) -> Option<Self::Item> { while let Some(v) = self.iter.next_back() { if (self.f)(v) { - return Some(self.count + self.iter.len()) + return Some(self.count + self.iter.len()); } } None @@ -1057,9 +1099,11 @@ impl<I, F> DoubleEndedIterator for Positions<I, F> } impl<I, F> FusedIterator for Positions<I, F> - where I: FusedIterator, - F: FnMut(I::Item) -> bool, -{} +where + I: FusedIterator, + F: FnMut(I::Item) -> bool, +{ +} /// An iterator adapter to apply a mutating function to each element before yielding it. /// @@ -1108,18 +1152,28 @@ where } fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc - where G: FnMut(Acc, Self::Item) -> Acc, + where + G: FnMut(Acc, Self::Item) -> Acc, { let mut f = self.f; - self.iter.fold(init, move |acc, mut v| { f(&mut v); g(acc, v) }) + self.iter.fold(init, move |acc, mut v| { + f(&mut v); + g(acc, v) + }) } // if possible, re-use inner iterator specializations in collect fn collect<C>(self) -> C - where C: FromIterator<Self::Item> + where + C: FromIterator<Self::Item>, { let mut f = self.f; - self.iter.map(move |mut v| { f(&mut v); v }).collect() + self.iter + .map(move |mut v| { + f(&mut v); + v + }) + .collect() } } @@ -1127,7 +1181,8 @@ impl<I, F> ExactSizeIterator for Update<I, F> where I: ExactSizeIterator, F: FnMut(&mut I::Item), -{} +{ +} impl<I, F> DoubleEndedIterator for Update<I, F> where @@ -1148,4 +1203,5 @@ impl<I, F> FusedIterator for Update<I, F> where I: FusedIterator, F: FnMut(&mut I::Item), -{} +{ +} diff --git a/vendor/itertools/src/adaptors/multi_product.rs b/vendor/itertools/src/adaptors/multi_product.rs index 0b3840698..ef7fadba8 100644 --- a/vendor/itertools/src/adaptors/multi_product.rs +++ b/vendor/itertools/src/adaptors/multi_product.rs @@ -15,8 +15,9 @@ use alloc::vec::Vec; /// for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct MultiProduct<I>(Vec<MultiProductIter<I>>) - where I: Iterator + Clone, - I::Item: Clone; +where + I: Iterator + Clone, + I::Item: Clone; impl<I> std::fmt::Debug for MultiProduct<I> where @@ -31,19 +32,25 @@ where /// /// Iterator element is of type `Vec<H::Item::Item>`. pub fn multi_cartesian_product<H>(iters: H) -> MultiProduct<<H::Item as IntoIterator>::IntoIter> - where H: Iterator, - H::Item: IntoIterator, - <H::Item as IntoIterator>::IntoIter: Clone, - <H::Item as IntoIterator>::Item: Clone +where + H: Iterator, + H::Item: IntoIterator, + <H::Item as IntoIterator>::IntoIter: Clone, + <H::Item as IntoIterator>::Item: Clone, { - MultiProduct(iters.map(|i| MultiProductIter::new(i.into_iter())).collect()) + MultiProduct( + iters + .map(|i| MultiProductIter::new(i.into_iter())) + .collect(), + ) } #[derive(Clone, Debug)] /// Holds the state of a single iterator within a `MultiProduct`. struct MultiProductIter<I> - where I: Iterator + Clone, - I::Item: Clone +where + I: Iterator + Clone, + I::Item: Clone, { cur: Option<I::Item>, iter: I, @@ -58,8 +65,9 @@ enum MultiProductIterState { } impl<I> MultiProduct<I> - where I: Iterator + Clone, - I::Item: Clone +where + I: Iterator + Clone, + I::Item: Clone, { /// Iterates the rightmost iterator, then recursively iterates iterators /// to the left if necessary. @@ -67,7 +75,7 @@ impl<I> MultiProduct<I> /// Returns true if the iteration succeeded, else false. fn iterate_last( multi_iters: &mut [MultiProductIter<I>], - mut state: MultiProductIterState + mut state: MultiProductIterState, ) -> bool { use self::MultiProductIterState::*; @@ -77,8 +85,8 @@ impl<I> MultiProduct<I> let on_first_iter = !last.in_progress(); state = MidIter { on_first_iter }; on_first_iter - }, - MidIter { on_first_iter } => on_first_iter + } + MidIter { on_first_iter } => on_first_iter, }; if !on_first_iter { @@ -101,16 +109,17 @@ impl<I> MultiProduct<I> // At end of iteration (final iterator finishes), finish. match state { StartOfIter => false, - MidIter { on_first_iter } => on_first_iter + MidIter { on_first_iter } => on_first_iter, } } } /// Returns the unwrapped value of the next iteration. fn curr_iterator(&self) -> Vec<I::Item> { - self.0.iter().map(|multi_iter| { - multi_iter.cur.clone().unwrap() - }).collect() + self.0 + .iter() + .map(|multi_iter| multi_iter.cur.clone().unwrap()) + .collect() } /// Returns true if iteration has started and has not yet finished; false @@ -125,14 +134,15 @@ impl<I> MultiProduct<I> } impl<I> MultiProductIter<I> - where I: Iterator + Clone, - I::Item: Clone +where + I: Iterator + Clone, + I::Item: Clone, { fn new(iter: I) -> Self { MultiProductIter { cur: None, iter: iter.clone(), - iter_orig: iter + iter_orig: iter, } } @@ -154,16 +164,14 @@ impl<I> MultiProductIter<I> } impl<I> Iterator for MultiProduct<I> - where I: Iterator + Clone, - I::Item: Clone +where + I: Iterator + Clone, + I::Item: Clone, { type Item = Vec<I::Item>; fn next(&mut self) -> Option<Self::Item> { - if MultiProduct::iterate_last( - &mut self.0, - MultiProductIterState::StartOfIter - ) { + if MultiProduct::iterate_last(&mut self.0, MultiProductIterState::StartOfIter) { Some(self.curr_iterator()) } else { None @@ -176,18 +184,24 @@ impl<I> Iterator for MultiProduct<I> } if !self.in_progress() { - return self.0.into_iter().fold(1, |acc, multi_iter| { - acc * multi_iter.iter.count() - }); + return self + .0 + .into_iter() + .fold(1, |acc, multi_iter| acc * multi_iter.iter.count()); } self.0.into_iter().fold( 0, - |acc, MultiProductIter { iter, iter_orig, cur: _ }| { + |acc, + MultiProductIter { + iter, + iter_orig, + cur: _, + }| { let total_count = iter_orig.count(); let cur_count = iter.count(); acc * total_count + cur_count - } + }, ) } @@ -205,18 +219,25 @@ impl<I> Iterator for MultiProduct<I> self.0.iter().fold( (0, Some(0)), - |acc, &MultiProductIter { ref iter, ref iter_orig, cur: _ }| { + |acc, + &MultiProductIter { + ref iter, + ref iter_orig, + cur: _, + }| { let cur_size = iter.size_hint(); let total_size = iter_orig.size_hint(); size_hint::add(size_hint::mul(acc, total_size), cur_size) - } + }, ) } fn last(self) -> Option<Self::Item> { let iter_count = self.0.len(); - let lasts: Self::Item = self.0.into_iter() + let lasts: Self::Item = self + .0 + .into_iter() .map(|multi_iter| multi_iter.iter.last()) .while_some() .collect(); diff --git a/vendor/itertools/src/combinations.rs b/vendor/itertools/src/combinations.rs index 68a59c5e4..d8b5351ec 100644 --- a/vendor/itertools/src/combinations.rs +++ b/vendor/itertools/src/combinations.rs @@ -4,6 +4,8 @@ use std::iter::FusedIterator; use super::lazy_buffer::LazyBuffer; use alloc::vec::Vec; +use crate::adaptors::checked_binomial; + /// An iterator to iterate through all the `k`-length combinations in an iterator. /// /// See [`.combinations()`](crate::Itertools::combinations) for more information. @@ -15,29 +17,29 @@ pub struct Combinations<I: Iterator> { } impl<I> Clone for Combinations<I> - where I: Clone + Iterator, - I::Item: Clone, +where + I: Clone + Iterator, + I::Item: Clone, { clone_fields!(indices, pool, first); } impl<I> fmt::Debug for Combinations<I> - where I: Iterator + fmt::Debug, - I::Item: fmt::Debug, +where + I: Iterator + fmt::Debug, + I::Item: fmt::Debug, { debug_fmt_fields!(Combinations, indices, pool, first); } /// Create a new `Combinations` from a clonable iterator. pub fn combinations<I>(iter: I, k: usize) -> Combinations<I> - where I: Iterator +where + I: Iterator, { - let mut pool = LazyBuffer::new(iter); - pool.prefill(k); - Combinations { indices: (0..k).collect(), - pool, + pool: LazyBuffer::new(iter), first: true, } } @@ -45,16 +47,22 @@ pub fn combinations<I>(iter: I, k: usize) -> Combinations<I> impl<I: Iterator> Combinations<I> { /// Returns the length of a combination produced by this iterator. #[inline] - pub fn k(&self) -> usize { self.indices.len() } + pub fn k(&self) -> usize { + self.indices.len() + } /// Returns the (current) length of the pool from which combination elements are /// selected. This value can change between invocations of [`next`](Combinations::next). #[inline] - pub fn n(&self) -> usize { self.pool.len() } + pub fn n(&self) -> usize { + self.pool.len() + } - /// Returns a reference to the source iterator. + /// Returns a reference to the source pool. #[inline] - pub(crate) fn src(&self) -> &I { &self.pool.it } + pub(crate) fn src(&self) -> &LazyBuffer<I> { + &self.pool + } /// Resets this `Combinations` back to an initial state for combinations of length /// `k` over the same pool data source. If `k` is larger than the current length @@ -68,7 +76,6 @@ impl<I: Iterator> Combinations<I> { for i in 0..k { self.indices[i] = i; } - } else { for i in 0..self.indices.len() { self.indices[i] = i; @@ -77,15 +84,27 @@ impl<I: Iterator> Combinations<I> { self.pool.prefill(k); } } + + pub(crate) fn n_and_count(self) -> (usize, usize) { + let Self { + indices, + pool, + first, + } = self; + let n = pool.count(); + (n, remaining_for(n, first, &indices).unwrap()) + } } impl<I> Iterator for Combinations<I> - where I: Iterator, - I::Item: Clone +where + I: Iterator, + I::Item: Clone, { type Item = Vec<I::Item>; fn next(&mut self) -> Option<Self::Item> { if self.first { + self.pool.prefill(self.k()); if self.k() > self.n() { return None; } @@ -112,7 +131,7 @@ impl<I> Iterator for Combinations<I> // Increment index, and reset the ones to its right self.indices[i] += 1; - for j in i+1..self.indices.len() { + for j in i + 1..self.indices.len() { self.indices[j] = self.indices[j - 1] + 1; } } @@ -120,9 +139,55 @@ impl<I> Iterator for Combinations<I> // Create result vector based on the indices Some(self.indices.iter().map(|i| self.pool[*i].clone()).collect()) } + + fn size_hint(&self) -> (usize, Option<usize>) { + let (mut low, mut upp) = self.pool.size_hint(); + low = remaining_for(low, self.first, &self.indices).unwrap_or(usize::MAX); + upp = upp.and_then(|upp| remaining_for(upp, self.first, &self.indices)); + (low, upp) + } + + #[inline] + fn count(self) -> usize { + self.n_and_count().1 + } } impl<I> FusedIterator for Combinations<I> - where I: Iterator, - I::Item: Clone -{} +where + I: Iterator, + I::Item: Clone, +{ +} + +/// For a given size `n`, return the count of remaining combinations or None if it would overflow. +fn remaining_for(n: usize, first: bool, indices: &[usize]) -> Option<usize> { + let k = indices.len(); + if n < k { + Some(0) + } else if first { + checked_binomial(n, k) + } else { + // https://en.wikipedia.org/wiki/Combinatorial_number_system + // http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf + + // The combinations generated after the current one can be counted by counting as follows: + // - The subsequent combinations that differ in indices[0]: + // If subsequent combinations differ in indices[0], then their value for indices[0] + // must be at least 1 greater than the current indices[0]. + // As indices is strictly monotonically sorted, this means we can effectively choose k values + // from (n - 1 - indices[0]), leading to binomial(n - 1 - indices[0], k) possibilities. + // - The subsequent combinations with same indices[0], but differing indices[1]: + // Here we can choose k - 1 values from (n - 1 - indices[1]) values, + // leading to binomial(n - 1 - indices[1], k - 1) possibilities. + // - (...) + // - The subsequent combinations with same indices[0..=i], but differing indices[i]: + // Here we can choose k - i values from (n - 1 - indices[i]) values: binomial(n - 1 - indices[i], k - i). + // Since subsequent combinations can in any index, we must sum up the aforementioned binomial coefficients. + + // Below, `n0` resembles indices[i]. + indices.iter().enumerate().try_fold(0usize, |sum, (i, n0)| { + sum.checked_add(checked_binomial(n - 1 - *n0, k - i)?) + }) + } +} diff --git a/vendor/itertools/src/combinations_with_replacement.rs b/vendor/itertools/src/combinations_with_replacement.rs index 0fec9671a..88d858b5f 100644 --- a/vendor/itertools/src/combinations_with_replacement.rs +++ b/vendor/itertools/src/combinations_with_replacement.rs @@ -3,12 +3,14 @@ use std::fmt; use std::iter::FusedIterator; use super::lazy_buffer::LazyBuffer; +use crate::adaptors::checked_binomial; /// An iterator to iterate through all the `n`-length combinations in an iterator, with replacement. /// /// See [`.combinations_with_replacement()`](crate::Itertools::combinations_with_replacement) /// for more information. #[derive(Clone)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct CombinationsWithReplacement<I> where I: Iterator, @@ -24,7 +26,7 @@ where I: Iterator + fmt::Debug, I::Item: fmt::Debug + Clone, { - debug_fmt_fields!(Combinations, indices, pool, first); + debug_fmt_fields!(CombinationsWithReplacement, indices, pool, first); } impl<I> CombinationsWithReplacement<I> @@ -80,7 +82,7 @@ where // Work out where we need to update our indices let mut increment: Option<(usize, usize)> = None; for (i, indices_int) in self.indices.iter().enumerate().rev() { - if *indices_int < self.pool.len()-1 { + if *indices_int < self.pool.len() - 1 { increment = Some((i, indices_int + 1)); break; } @@ -100,10 +102,70 @@ where None => None, } } + + fn size_hint(&self) -> (usize, Option<usize>) { + let (mut low, mut upp) = self.pool.size_hint(); + low = remaining_for(low, self.first, &self.indices).unwrap_or(usize::MAX); + upp = upp.and_then(|upp| remaining_for(upp, self.first, &self.indices)); + (low, upp) + } + + fn count(self) -> usize { + let Self { + indices, + pool, + first, + } = self; + let n = pool.count(); + remaining_for(n, first, &indices).unwrap() + } } impl<I> FusedIterator for CombinationsWithReplacement<I> where I: Iterator, I::Item: Clone, -{} +{ +} + +/// For a given size `n`, return the count of remaining combinations with replacement or None if it would overflow. +fn remaining_for(n: usize, first: bool, indices: &[usize]) -> Option<usize> { + // With a "stars and bars" representation, choose k values with replacement from n values is + // like choosing k out of k + n − 1 positions (hence binomial(k + n - 1, k) possibilities) + // to place k stars and therefore n - 1 bars. + // Example (n=4, k=6): ***|*||** represents [0,0,0,1,3,3]. + let count = |n: usize, k: usize| { + let positions = if n == 0 { + k.saturating_sub(1) + } else { + (n - 1).checked_add(k)? + }; + checked_binomial(positions, k) + }; + let k = indices.len(); + if first { + count(n, k) + } else { + // The algorithm is similar to the one for combinations *without replacement*, + // except we choose values *with replacement* and indices are *non-strictly* monotonically sorted. + + // The combinations generated after the current one can be counted by counting as follows: + // - The subsequent combinations that differ in indices[0]: + // If subsequent combinations differ in indices[0], then their value for indices[0] + // must be at least 1 greater than the current indices[0]. + // As indices is monotonically sorted, this means we can effectively choose k values with + // replacement from (n - 1 - indices[0]), leading to count(n - 1 - indices[0], k) possibilities. + // - The subsequent combinations with same indices[0], but differing indices[1]: + // Here we can choose k - 1 values with replacement from (n - 1 - indices[1]) values, + // leading to count(n - 1 - indices[1], k - 1) possibilities. + // - (...) + // - The subsequent combinations with same indices[0..=i], but differing indices[i]: + // Here we can choose k - i values with replacement from (n - 1 - indices[i]) values: count(n - 1 - indices[i], k - i). + // Since subsequent combinations can in any index, we must sum up the aforementioned binomial coefficients. + + // Below, `n0` resembles indices[i]. + indices.iter().enumerate().try_fold(0usize, |sum, (i, n0)| { + sum.checked_add(count(n - 1 - *n0, k - i)?) + }) + } +} diff --git a/vendor/itertools/src/concat_impl.rs b/vendor/itertools/src/concat_impl.rs index f022ec90a..ec7b91c60 100644 --- a/vendor/itertools/src/concat_impl.rs +++ b/vendor/itertools/src/concat_impl.rs @@ -10,14 +10,21 @@ use crate::Itertools; /// /// ```rust /// use itertools::concat; -/// +/// /// let input = vec![vec![1], vec![2, 3], vec![4, 5, 6]]; /// assert_eq!(concat(input), vec![1, 2, 3, 4, 5, 6]); /// ``` pub fn concat<I>(iterable: I) -> I::Item - where I: IntoIterator, - I::Item: Extend<<<I as IntoIterator>::Item as IntoIterator>::Item> + IntoIterator + Default +where + I: IntoIterator, + I::Item: Extend<<<I as IntoIterator>::Item as IntoIterator>::Item> + IntoIterator + Default, { #[allow(deprecated)] //TODO: once msrv hits 1.51. replace `fold1` with `reduce` - iterable.into_iter().fold1(|mut a, b| { a.extend(b); a }).unwrap_or_default() + iterable + .into_iter() + .fold1(|mut a, b| { + a.extend(b); + a + }) + .unwrap_or_default() } diff --git a/vendor/itertools/src/cons_tuples_impl.rs b/vendor/itertools/src/cons_tuples_impl.rs index ae0f48f34..3cae0b06e 100644 --- a/vendor/itertools/src/cons_tuples_impl.rs +++ b/vendor/itertools/src/cons_tuples_impl.rs @@ -1,4 +1,3 @@ - macro_rules! impl_cons_iter( ($_A:ident, $_B:ident, ) => (); // stop @@ -44,13 +43,15 @@ impl_cons_iter!(A, B, C, D, E, F, G, H, I, J, K, L,); #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] #[derive(Debug)] pub struct ConsTuples<I, J> - where I: Iterator<Item=J>, +where + I: Iterator<Item = J>, { iter: I, } impl<I, J> Clone for ConsTuples<I, J> - where I: Clone + Iterator<Item=J>, +where + I: Clone + Iterator<Item = J>, { clone_fields!(iter); } @@ -58,7 +59,10 @@ impl<I, J> Clone for ConsTuples<I, J> /// Create an iterator that maps for example iterators of /// `((A, B), C)` to `(A, B, C)`. pub fn cons_tuples<I, J>(iterable: I) -> ConsTuples<I::IntoIter, J> - where I: IntoIterator<Item=J> +where + I: IntoIterator<Item = J>, { - ConsTuples { iter: iterable.into_iter() } + ConsTuples { + iter: iterable.into_iter(), + } } diff --git a/vendor/itertools/src/diff.rs b/vendor/itertools/src/diff.rs index 1731f0639..0d3d358b5 100644 --- a/vendor/itertools/src/diff.rs +++ b/vendor/itertools/src/diff.rs @@ -13,8 +13,9 @@ use crate::structs::PutBack; /// `Diff` represents the way in which the elements yielded by the iterator `I` differ to some /// iterator `J`. pub enum Diff<I, J> - where I: Iterator, - J: Iterator +where + I: Iterator, + J: Iterator, { /// The index of the first non-matching element along with both iterator's remaining elements /// starting with the first mis-match. @@ -37,11 +38,11 @@ pub enum Diff<I, J> /// /// If `i` becomes exhausted before `j` becomes exhausted, the number of elements in `i` along with /// the remaining `j` elements will be returned as `Diff::Longer`. -pub fn diff_with<I, J, F>(i: I, j: J, is_equal: F) - -> Option<Diff<I::IntoIter, J::IntoIter>> - where I: IntoIterator, - J: IntoIterator, - F: Fn(&I::Item, &J::Item) -> bool +pub fn diff_with<I, J, F>(i: I, j: J, is_equal: F) -> Option<Diff<I::IntoIter, J::IntoIter>> +where + I: IntoIterator, + J: IntoIterator, + F: Fn(&I::Item, &J::Item) -> bool, { let mut i = i.into_iter(); let mut j = j.into_iter(); @@ -49,13 +50,16 @@ pub fn diff_with<I, J, F>(i: I, j: J, is_equal: F) while let Some(i_elem) = i.next() { match j.next() { None => return Some(Diff::Shorter(idx, put_back(i).with_value(i_elem))), - Some(j_elem) => if !is_equal(&i_elem, &j_elem) { - let remaining_i = put_back(i).with_value(i_elem); - let remaining_j = put_back(j).with_value(j_elem); - return Some(Diff::FirstMismatch(idx, remaining_i, remaining_j)); - }, + Some(j_elem) => { + if !is_equal(&i_elem, &j_elem) { + let remaining_i = put_back(i).with_value(i_elem); + let remaining_j = put_back(j).with_value(j_elem); + return Some(Diff::FirstMismatch(idx, remaining_i, remaining_j)); + } + } } idx += 1; } - j.next().map(|j_elem| Diff::Longer(idx, put_back(j).with_value(j_elem))) + j.next() + .map(|j_elem| Diff::Longer(idx, put_back(j).with_value(j_elem))) } diff --git a/vendor/itertools/src/duplicates_impl.rs b/vendor/itertools/src/duplicates_impl.rs index 28eda44a9..71ed21841 100644 --- a/vendor/itertools/src/duplicates_impl.rs +++ b/vendor/itertools/src/duplicates_impl.rs @@ -2,8 +2,8 @@ use std::hash::Hash; mod private { use std::collections::HashMap; - use std::hash::Hash; use std::fmt; + use std::hash::Hash; #[derive(Clone)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] @@ -122,7 +122,7 @@ mod private { } /// Apply the identity function to elements before checking them for equality. - #[derive(Debug)] + #[derive(Debug, Clone)] pub struct ById; impl<V> KeyMethod<V, V> for ById { type Container = JustValue<V>; @@ -133,6 +133,7 @@ mod private { } /// Apply a user-supplied function to elements before checking them for equality. + #[derive(Clone)] pub struct ByFn<F>(pub(crate) F); impl<F> fmt::Debug for ByFn<F> { debug_fmt_fields!(ByFn,); @@ -213,4 +214,3 @@ where { Duplicates::new(iter, private::ById) } - diff --git a/vendor/itertools/src/either_or_both.rs b/vendor/itertools/src/either_or_both.rs index cf65fe788..9dbc880d3 100644 --- a/vendor/itertools/src/either_or_both.rs +++ b/vendor/itertools/src/either_or_both.rs @@ -6,7 +6,7 @@ use either::Either; /// Value that either holds a single A or B, or both. #[derive(Clone, PartialEq, Eq, Hash, Debug)] -pub enum EitherOrBoth<A, B> { +pub enum EitherOrBoth<A, B = A> { /// Both values are present. Both(A, B), /// Only the left value of type `A` is present. @@ -65,6 +65,14 @@ impl<A, B> EitherOrBoth<A, B> { } } + /// Return tuple of options corresponding to the left and right value respectively + /// + /// If `Left` return `(Some(..), None)`, if `Right` return `(None,Some(..))`, else return + /// `(Some(..),Some(..))` + pub fn left_and_right(self) -> (Option<A>, Option<B>) { + self.map_any(Some, Some).or_default() + } + /// If `Left`, return `Some` with the left value. If `Right` or `Both`, return `None`. /// /// # Examples @@ -464,13 +472,21 @@ impl<A, B> EitherOrBoth<A, B> { impl<T> EitherOrBoth<T, T> { /// Return either value of left, right, or apply a function `f` to both values if both are present. /// The input function has to return the same type as both Right and Left carry. - /// + /// + /// This function can be used to preferrably extract the left resp. right value, + /// but fall back to the other (i.e. right resp. left) if the preferred one is not present. + /// /// # Examples /// ``` /// # use itertools::EitherOrBoth; /// assert_eq!(EitherOrBoth::Both(3, 7).reduce(u32::max), 7); /// assert_eq!(EitherOrBoth::Left(3).reduce(u32::max), 3); /// assert_eq!(EitherOrBoth::Right(7).reduce(u32::max), 7); + /// + /// // Extract the left value if present, fall back to the right otherwise. + /// assert_eq!(EitherOrBoth::Left("left").reduce(|l, _r| l), "left"); + /// assert_eq!(EitherOrBoth::Right("right").reduce(|l, _r| l), "right"); + /// assert_eq!(EitherOrBoth::Both("left", "right").reduce(|l, _r| l), "left"); /// ``` pub fn reduce<F>(self, f: F) -> T where @@ -493,3 +509,12 @@ impl<A, B> Into<Option<Either<A, B>>> for EitherOrBoth<A, B> { } } } + +impl<A, B> From<Either<A, B>> for EitherOrBoth<A, B> { + fn from(either: Either<A, B>) -> Self { + match either { + Either::Left(l) => EitherOrBoth::Left(l), + Either::Right(l) => EitherOrBoth::Right(l), + } + } +} diff --git a/vendor/itertools/src/exactly_one_err.rs b/vendor/itertools/src/exactly_one_err.rs index c54ae77ca..e24d33fc5 100644 --- a/vendor/itertools/src/exactly_one_err.rs +++ b/vendor/itertools/src/exactly_one_err.rs @@ -54,13 +54,9 @@ where Some(Either::Left([first, second])) => { self.first_two = Some(Either::Right(second)); Some(first) - }, - Some(Either::Right(second)) => { - Some(second) - } - None => { - self.inner.next() } + Some(Either::Right(second)) => Some(second), + None => self.inner.next(), } } @@ -69,11 +65,11 @@ where } } - impl<I> ExactSizeIterator for ExactlyOneError<I> where I: ExactSizeIterator {} -impl<I> Display for ExactlyOneError<I> - where I: Iterator, +impl<I> Display for ExactlyOneError<I> +where + I: Iterator, { fn fmt(&self, f: &mut Formatter) -> FmtResult { let additional = self.additional_len(); @@ -85,17 +81,26 @@ impl<I> Display for ExactlyOneError<I> } } -impl<I> Debug for ExactlyOneError<I> - where I: Iterator + Debug, - I::Item: Debug, +impl<I> Debug for ExactlyOneError<I> +where + I: Iterator + Debug, + I::Item: Debug, { fn fmt(&self, f: &mut Formatter) -> FmtResult { match &self.first_two { Some(Either::Left([first, second])) => { - write!(f, "ExactlyOneError[First: {:?}, Second: {:?}, RemainingIter: {:?}]", first, second, self.inner) - }, + write!( + f, + "ExactlyOneError[First: {:?}, Second: {:?}, RemainingIter: {:?}]", + first, second, self.inner + ) + } Some(Either::Right(second)) => { - write!(f, "ExactlyOneError[Second: {:?}, RemainingIter: {:?}]", second, self.inner) + write!( + f, + "ExactlyOneError[Second: {:?}, RemainingIter: {:?}]", + second, self.inner + ) } None => { write!(f, "ExactlyOneError[RemainingIter: {:?}]", self.inner) @@ -105,6 +110,9 @@ impl<I> Debug for ExactlyOneError<I> } #[cfg(feature = "use_std")] -impl<I> Error for ExactlyOneError<I> where I: Iterator + Debug, I::Item: Debug, {} - - +impl<I> Error for ExactlyOneError<I> +where + I: Iterator + Debug, + I::Item: Debug, +{ +} diff --git a/vendor/itertools/src/extrema_set.rs b/vendor/itertools/src/extrema_set.rs index ae128364c..d24114c6d 100644 --- a/vendor/itertools/src/extrema_set.rs +++ b/vendor/itertools/src/extrema_set.rs @@ -1,3 +1,5 @@ +#![cfg(feature = "use_alloc")] +use alloc::{vec, vec::Vec}; use std::cmp::Ordering; /// Implementation guts for `min_set`, `min_set_by`, and `min_set_by_key`. diff --git a/vendor/itertools/src/free.rs b/vendor/itertools/src/free.rs index 19e3e2869..5ce1b49b3 100644 --- a/vendor/itertools/src/free.rs +++ b/vendor/itertools/src/free.rs @@ -10,30 +10,24 @@ use std::iter::{self, Zip}; type VecIntoIter<T> = alloc::vec::IntoIter<T>; #[cfg(feature = "use_alloc")] -use alloc::{ - string::String, -}; +use alloc::string::String; -use crate::Itertools; use crate::intersperse::{Intersperse, IntersperseWith}; +use crate::Itertools; -pub use crate::adaptors::{ - interleave, - merge, - put_back, -}; +pub use crate::adaptors::{interleave, put_back}; #[cfg(feature = "use_alloc")] -pub use crate::put_back_n_impl::put_back_n; +pub use crate::kmerge_impl::kmerge; +pub use crate::merge_join::{merge, merge_join_by}; #[cfg(feature = "use_alloc")] pub use crate::multipeek_impl::multipeek; #[cfg(feature = "use_alloc")] pub use crate::peek_nth::peek_nth; #[cfg(feature = "use_alloc")] -pub use crate::kmerge_impl::kmerge; -pub use crate::zip_eq_impl::zip_eq; -pub use crate::merge_join::merge_join_by; +pub use crate::put_back_n_impl::put_back_n; #[cfg(feature = "use_alloc")] pub use crate::rciter_impl::rciter; +pub use crate::zip_eq_impl::zip_eq; /// Iterate `iterable` with a particular value inserted between each element. /// @@ -45,8 +39,9 @@ pub use crate::rciter_impl::rciter; /// itertools::assert_equal(intersperse((0..3), 8), vec![0, 8, 1, 8, 2]); /// ``` pub fn intersperse<I>(iterable: I, element: I::Item) -> Intersperse<I::IntoIter> - where I: IntoIterator, - <I as IntoIterator>::Item: Clone +where + I: IntoIterator, + <I as IntoIterator>::Item: Clone, { Itertools::intersperse(iterable.into_iter(), element) } @@ -64,8 +59,9 @@ pub fn intersperse<I>(iterable: I, element: I::Item) -> Intersperse<I::IntoIter> /// assert_eq!(i, 8); /// ``` pub fn intersperse_with<I, F>(iterable: I, element: F) -> IntersperseWith<I::IntoIter, F> - where I: IntoIterator, - F: FnMut() -> I::Item +where + I: IntoIterator, + F: FnMut() -> I::Item, { Itertools::intersperse_with(iterable.into_iter(), element) } @@ -82,7 +78,8 @@ pub fn intersperse_with<I, F>(iterable: I, element: F) -> IntersperseWith<I::Int /// } /// ``` pub fn enumerate<I>(iterable: I) -> iter::Enumerate<I::IntoIter> - where I: IntoIterator +where + I: IntoIterator, { iterable.into_iter().enumerate() } @@ -99,8 +96,9 @@ pub fn enumerate<I>(iterable: I) -> iter::Enumerate<I::IntoIter> /// } /// ``` pub fn rev<I>(iterable: I) -> iter::Rev<I::IntoIter> - where I: IntoIterator, - I::IntoIter: DoubleEndedIterator +where + I: IntoIterator, + I::IntoIter: DoubleEndedIterator, { iterable.into_iter().rev() } @@ -108,7 +106,7 @@ pub fn rev<I>(iterable: I) -> iter::Rev<I::IntoIter> /// Converts the arguments to iterators and zips them. /// /// [`IntoIterator`] enabled version of [`Iterator::zip`]. -/// +/// /// ## Example /// /// ``` @@ -121,23 +119,26 @@ pub fn rev<I>(iterable: I) -> iter::Rev<I::IntoIter> /// } /// assert_eq!(result, vec![(1, 'a'),(2, 'b'),(3, 'c')]); /// ``` -#[deprecated(note="Use [std::iter::zip](https://doc.rust-lang.org/std/iter/fn.zip.html) instead", since="0.10.4")] +#[deprecated( + note = "Use [std::iter::zip](https://doc.rust-lang.org/std/iter/fn.zip.html) instead", + since = "0.10.4" +)] pub fn zip<I, J>(i: I, j: J) -> Zip<I::IntoIter, J::IntoIter> - where I: IntoIterator, - J: IntoIterator +where + I: IntoIterator, + J: IntoIterator, { i.into_iter().zip(j) } - -/// Takes two iterables and creates a new iterator over both in sequence. +/// Takes two iterables and creates a new iterator over both in sequence. /// /// [`IntoIterator`] enabled version of [`Iterator::chain`]. /// /// ## Example /// ``` /// use itertools::chain; -/// +/// /// let mut result:Vec<i32> = Vec::new(); /// /// for element in chain(&[1, 2, 3], &[4]) { @@ -145,9 +146,13 @@ pub fn zip<I, J>(i: I, j: J) -> Zip<I::IntoIter, J::IntoIter> /// } /// assert_eq!(result, vec![1, 2, 3, 4]); /// ``` -pub fn chain<I, J>(i: I, j: J) -> iter::Chain<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter> - where I: IntoIterator, - J: IntoIterator<Item = I::Item> +pub fn chain<I, J>( + i: I, + j: J, +) -> iter::Chain<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter> +where + I: IntoIterator, + J: IntoIterator<Item = I::Item>, { i.into_iter().chain(j) } @@ -162,8 +167,9 @@ pub fn chain<I, J>(i: I, j: J) -> iter::Chain<<I as IntoIterator>::IntoIter, <J /// assert_eq!(cloned(b"abc").next(), Some(b'a')); /// ``` pub fn cloned<'a, I, T: 'a>(iterable: I) -> iter::Cloned<I::IntoIter> - where I: IntoIterator<Item=&'a T>, - T: Clone, +where + I: IntoIterator<Item = &'a T>, + T: Clone, { iterable.into_iter().cloned() } @@ -178,8 +184,9 @@ pub fn cloned<'a, I, T: 'a>(iterable: I) -> iter::Cloned<I::IntoIter> /// assert_eq!(fold(&[1., 2., 3.], 0., |a, &b| f32::max(a, b)), 3.); /// ``` pub fn fold<I, B, F>(iterable: I, init: B, f: F) -> B - where I: IntoIterator, - F: FnMut(B, I::Item) -> B +where + I: IntoIterator, + F: FnMut(B, I::Item) -> B, { iterable.into_iter().fold(init, f) } @@ -194,8 +201,9 @@ pub fn fold<I, B, F>(iterable: I, init: B, f: F) -> B /// assert!(all(&[1, 2, 3], |elt| *elt > 0)); /// ``` pub fn all<I, F>(iterable: I, f: F) -> bool - where I: IntoIterator, - F: FnMut(I::Item) -> bool +where + I: IntoIterator, + F: FnMut(I::Item) -> bool, { iterable.into_iter().all(f) } @@ -210,8 +218,9 @@ pub fn all<I, F>(iterable: I, f: F) -> bool /// assert!(any(&[0, -1, 2], |elt| *elt > 0)); /// ``` pub fn any<I, F>(iterable: I, f: F) -> bool - where I: IntoIterator, - F: FnMut(I::Item) -> bool +where + I: IntoIterator, + F: FnMut(I::Item) -> bool, { iterable.into_iter().any(f) } @@ -226,8 +235,9 @@ pub fn any<I, F>(iterable: I, f: F) -> bool /// assert_eq!(max(0..10), Some(9)); /// ``` pub fn max<I>(iterable: I) -> Option<I::Item> - where I: IntoIterator, - I::Item: Ord +where + I: IntoIterator, + I::Item: Ord, { iterable.into_iter().max() } @@ -242,13 +252,13 @@ pub fn max<I>(iterable: I) -> Option<I::Item> /// assert_eq!(min(0..10), Some(0)); /// ``` pub fn min<I>(iterable: I) -> Option<I::Item> - where I: IntoIterator, - I::Item: Ord +where + I: IntoIterator, + I::Item: Ord, { iterable.into_iter().min() } - /// Combine all iterator elements into one String, separated by `sep`. /// /// [`IntoIterator`] enabled version of [`Itertools::join`]. @@ -260,8 +270,9 @@ pub fn min<I>(iterable: I) -> Option<I::Item> /// ``` #[cfg(feature = "use_alloc")] pub fn join<I>(iterable: I, sep: &str) -> String - where I: IntoIterator, - I::Item: Display +where + I: IntoIterator, + I::Item: Display, { iterable.into_iter().join(sep) } @@ -278,9 +289,28 @@ pub fn join<I>(iterable: I, sep: &str) -> String /// ``` #[cfg(feature = "use_alloc")] pub fn sorted<I>(iterable: I) -> VecIntoIter<I::Item> - where I: IntoIterator, - I::Item: Ord +where + I: IntoIterator, + I::Item: Ord, { iterable.into_iter().sorted() } +/// Sort all iterator elements into a new iterator in ascending order. +/// This sort is unstable (i.e., may reorder equal elements). +/// [`IntoIterator`] enabled version of [`Itertools::sorted_unstable`]. +/// +/// ``` +/// use itertools::sorted_unstable; +/// use itertools::assert_equal; +/// +/// assert_equal(sorted_unstable("rust".chars()), "rstu".chars()); +/// ``` +#[cfg(feature = "use_alloc")] +pub fn sorted_unstable<I>(iterable: I) -> VecIntoIter<I::Item> +where + I: IntoIterator, + I::Item: Ord, +{ + iterable.into_iter().sorted_unstable() +} diff --git a/vendor/itertools/src/group_map.rs b/vendor/itertools/src/group_map.rs index a2d0ebb2a..8891f95ac 100644 --- a/vendor/itertools/src/group_map.rs +++ b/vendor/itertools/src/group_map.rs @@ -9,8 +9,9 @@ use std::iter::Iterator; /// See [`.into_group_map()`](crate::Itertools::into_group_map) /// for more information. pub fn into_group_map<I, K, V>(iter: I) -> HashMap<K, Vec<V>> - where I: Iterator<Item=(K, V)>, - K: Hash + Eq, +where + I: Iterator<Item = (K, V)>, + K: Hash + Eq, { let mut lookup = HashMap::new(); @@ -22,11 +23,9 @@ pub fn into_group_map<I, K, V>(iter: I) -> HashMap<K, Vec<V>> } pub fn into_group_map_by<I, K, V>(iter: I, f: impl Fn(&V) -> K) -> HashMap<K, Vec<V>> - where - I: Iterator<Item=V>, - K: Hash + Eq, +where + I: Iterator<Item = V>, + K: Hash + Eq, { - into_group_map( - iter.map(|v| (f(&v), v)) - ) + into_group_map(iter.map(|v| (f(&v), v))) } diff --git a/vendor/itertools/src/groupbylazy.rs b/vendor/itertools/src/groupbylazy.rs index 80c6f09f3..6cf33838c 100644 --- a/vendor/itertools/src/groupbylazy.rs +++ b/vendor/itertools/src/groupbylazy.rs @@ -1,5 +1,5 @@ -use std::cell::{Cell, RefCell}; use alloc::vec::{self, Vec}; +use std::cell::{Cell, RefCell}; /// A trait to unify `FnMut` for `GroupBy` with the chunk key in `IntoChunks` trait KeyFunction<A> { @@ -8,7 +8,8 @@ trait KeyFunction<A> { } impl<A, K, F: ?Sized> KeyFunction<A> for F - where F: FnMut(A) -> K +where + F: FnMut(A) -> K, { type Key = K; #[inline] @@ -17,7 +18,6 @@ impl<A, K, F: ?Sized> KeyFunction<A> for F } } - /// `ChunkIndex` acts like the grouping key function for `IntoChunks` #[derive(Debug, Clone)] struct ChunkIndex { @@ -52,7 +52,8 @@ impl<A> KeyFunction<A> for ChunkIndex { #[derive(Clone)] struct GroupInner<K, I, F> - where I: Iterator +where + I: Iterator, { key: F, iter: I, @@ -75,9 +76,10 @@ struct GroupInner<K, I, F> } impl<K, I, F> GroupInner<K, I, F> - where I: Iterator, - F: for<'a> KeyFunction<&'a I::Item, Key=K>, - K: PartialEq, +where + I: Iterator, + F: for<'a> KeyFunction<&'a I::Item, Key = K>, + K: PartialEq, { /// `client`: Index of group that requests next element #[inline(always)] @@ -90,9 +92,8 @@ impl<K, I, F> GroupInner<K, I, F> */ if client < self.oldest_buffered_group { None - } else if client < self.top_group || - (client == self.top_group && - self.buffer.len() > self.top_group - self.bottom_group) + } else if client < self.top_group + || (client == self.top_group && self.buffer.len() > self.top_group - self.bottom_group) { self.lookup_buffer(client) } else if self.done { @@ -118,8 +119,10 @@ impl<K, I, F> GroupInner<K, I, F> // `bottom_group..oldest_buffered_group` is unused, and if it's large enough, erase it. self.oldest_buffered_group += 1; // skip forward further empty queues too - while self.buffer.get(self.oldest_buffered_group - self.bottom_group) - .map_or(false, |buf| buf.len() == 0) + while self + .buffer + .get(self.oldest_buffered_group - self.bottom_group) + .map_or(false, |buf| buf.len() == 0) { self.oldest_buffered_group += 1; } @@ -144,12 +147,14 @@ impl<K, I, F> GroupInner<K, I, F> fn next_element(&mut self) -> Option<I::Item> { debug_assert!(!self.done); match self.iter.next() { - None => { self.done = true; None } + None => { + self.done = true; + None + } otherwise => otherwise, } } - #[inline(never)] fn step_buffering(&mut self, client: usize) -> Option<I::Item> { // requested a later group -- walk through the current group up to @@ -171,11 +176,13 @@ impl<K, I, F> GroupInner<K, I, F> let key = self.key.call_mut(&elt); match self.current_key.take() { None => {} - Some(old_key) => if old_key != key { - self.current_key = Some(key); - first_elt = Some(elt); - break; - }, + Some(old_key) => { + if old_key != key { + self.current_key = Some(key); + first_elt = Some(elt); + break; + } + } } self.current_key = Some(key); if self.top_group != self.dropped_group { @@ -220,12 +227,14 @@ impl<K, I, F> GroupInner<K, I, F> let key = self.key.call_mut(&elt); match self.current_key.take() { None => {} - Some(old_key) => if old_key != key { - self.current_key = Some(key); - self.current_elt = Some(elt); - self.top_group += 1; - return None; - }, + Some(old_key) => { + if old_key != key { + self.current_key = Some(key); + self.current_elt = Some(elt); + self.top_group += 1; + return None; + } + } } self.current_key = Some(key); Some(elt) @@ -261,7 +270,8 @@ impl<K, I, F> GroupInner<K, I, F> } impl<K, I, F> GroupInner<K, I, F> - where I: Iterator, +where + I: Iterator, { /// Called when a group is dropped fn drop_group(&mut self, client: usize) { @@ -287,7 +297,8 @@ impl<K, I, F> GroupInner<K, I, F> /// See [`.group_by()`](crate::Itertools::group_by) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct GroupBy<K, I, F> - where I: Iterator, +where + I: Iterator, { inner: RefCell<GroupInner<K, I, F>>, // the group iterator's current index. Keep this in the main value @@ -297,8 +308,9 @@ pub struct GroupBy<K, I, F> /// Create a new pub fn new<K, J, F>(iter: J, f: F) -> GroupBy<K, J::IntoIter, F> - where J: IntoIterator, - F: FnMut(&J::Item) -> K, +where + J: IntoIterator, + F: FnMut(&J::Item) -> K, { GroupBy { inner: RefCell::new(GroupInner { @@ -318,12 +330,14 @@ pub fn new<K, J, F>(iter: J, f: F) -> GroupBy<K, J::IntoIter, F> } impl<K, I, F> GroupBy<K, I, F> - where I: Iterator, +where + I: Iterator, { /// `client`: Index of group that requests next element fn step(&self, client: usize) -> Option<I::Item> - where F: FnMut(&I::Item) -> K, - K: PartialEq, + where + F: FnMut(&I::Item) -> K, + K: PartialEq, { self.inner.borrow_mut().step(client) } @@ -335,10 +349,11 @@ impl<K, I, F> GroupBy<K, I, F> } impl<'a, K, I, F> IntoIterator for &'a GroupBy<K, I, F> - where I: Iterator, - I::Item: 'a, - F: FnMut(&I::Item) -> K, - K: PartialEq +where + I: Iterator, + I::Item: 'a, + F: FnMut(&I::Item) -> K, + K: PartialEq, { type Item = (K, Group<'a, K, I, F>); type IntoIter = Groups<'a, K, I, F>; @@ -348,7 +363,6 @@ impl<'a, K, I, F> IntoIterator for &'a GroupBy<K, I, F> } } - /// An iterator that yields the Group iterators. /// /// Iterator element type is `(K, Group)`: @@ -357,17 +371,19 @@ impl<'a, K, I, F> IntoIterator for &'a GroupBy<K, I, F> /// See [`.group_by()`](crate::Itertools::group_by) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Groups<'a, K: 'a, I: 'a, F: 'a> - where I: Iterator, - I::Item: 'a +where + I: Iterator, + I::Item: 'a, { parent: &'a GroupBy<K, I, F>, } impl<'a, K, I, F> Iterator for Groups<'a, K, I, F> - where I: Iterator, - I::Item: 'a, - F: FnMut(&I::Item) -> K, - K: PartialEq +where + I: Iterator, + I::Item: 'a, + F: FnMut(&I::Item) -> K, + K: PartialEq, { type Item = (K, Group<'a, K, I, F>); @@ -378,11 +394,14 @@ impl<'a, K, I, F> Iterator for Groups<'a, K, I, F> let inner = &mut *self.parent.inner.borrow_mut(); inner.step(index).map(|elt| { let key = inner.group_key(index); - (key, Group { - parent: self.parent, - index, - first: Some(elt), - }) + ( + key, + Group { + parent: self.parent, + index, + first: Some(elt), + }, + ) }) } } @@ -391,8 +410,9 @@ impl<'a, K, I, F> Iterator for Groups<'a, K, I, F> /// /// Iterator element type is `I::Item`. pub struct Group<'a, K: 'a, I: 'a, F: 'a> - where I: Iterator, - I::Item: 'a, +where + I: Iterator, + I::Item: 'a, { parent: &'a GroupBy<K, I, F>, index: usize, @@ -400,8 +420,9 @@ pub struct Group<'a, K: 'a, I: 'a, F: 'a> } impl<'a, K, I, F> Drop for Group<'a, K, I, F> - where I: Iterator, - I::Item: 'a, +where + I: Iterator, + I::Item: 'a, { fn drop(&mut self) { self.parent.drop_group(self.index); @@ -409,10 +430,11 @@ impl<'a, K, I, F> Drop for Group<'a, K, I, F> } impl<'a, K, I, F> Iterator for Group<'a, K, I, F> - where I: Iterator, - I::Item: 'a, - F: FnMut(&I::Item) -> K, - K: PartialEq, +where + I: Iterator, + I::Item: 'a, + F: FnMut(&I::Item) -> K, + K: PartialEq, { type Item = I::Item; #[inline] @@ -428,7 +450,8 @@ impl<'a, K, I, F> Iterator for Group<'a, K, I, F> /// Create a new pub fn new_chunks<J>(iter: J, size: usize) -> IntoChunks<J::IntoIter> - where J: IntoIterator, +where + J: IntoIterator, { IntoChunks { inner: RefCell::new(GroupInner { @@ -447,7 +470,6 @@ pub fn new_chunks<J>(iter: J, size: usize) -> IntoChunks<J::IntoIter> } } - /// `ChunkLazy` is the storage for a lazy chunking operation. /// /// `IntoChunks` behaves just like `GroupBy`: it is iterable, and @@ -463,7 +485,8 @@ pub fn new_chunks<J>(iter: J, size: usize) -> IntoChunks<J::IntoIter> /// See [`.chunks()`](crate::Itertools::chunks) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct IntoChunks<I> - where I: Iterator, +where + I: Iterator, { inner: RefCell<GroupInner<usize, I, ChunkIndex>>, // the chunk iterator's current index. Keep this in the main value @@ -472,15 +495,16 @@ pub struct IntoChunks<I> } impl<I> Clone for IntoChunks<I> - where I: Clone + Iterator, - I::Item: Clone, +where + I: Clone + Iterator, + I::Item: Clone, { clone_fields!(inner, index); } - impl<I> IntoChunks<I> - where I: Iterator, +where + I: Iterator, { /// `client`: Index of chunk that requests next element fn step(&self, client: usize) -> Option<I::Item> { @@ -494,20 +518,18 @@ impl<I> IntoChunks<I> } impl<'a, I> IntoIterator for &'a IntoChunks<I> - where I: Iterator, - I::Item: 'a, +where + I: Iterator, + I::Item: 'a, { type Item = Chunk<'a, I>; type IntoIter = Chunks<'a, I>; fn into_iter(self) -> Self::IntoIter { - Chunks { - parent: self, - } + Chunks { parent: self } } } - /// An iterator that yields the Chunk iterators. /// /// Iterator element type is `Chunk`. @@ -516,15 +538,17 @@ impl<'a, I> IntoIterator for &'a IntoChunks<I> #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] #[derive(Clone)] pub struct Chunks<'a, I: 'a> - where I: Iterator, - I::Item: 'a, +where + I: Iterator, + I::Item: 'a, { parent: &'a IntoChunks<I>, } impl<'a, I> Iterator for Chunks<'a, I> - where I: Iterator, - I::Item: 'a, +where + I: Iterator, + I::Item: 'a, { type Item = Chunk<'a, I>; @@ -533,12 +557,10 @@ impl<'a, I> Iterator for Chunks<'a, I> let index = self.parent.index.get(); self.parent.index.set(index + 1); let inner = &mut *self.parent.inner.borrow_mut(); - inner.step(index).map(|elt| { - Chunk { - parent: self.parent, - index, - first: Some(elt), - } + inner.step(index).map(|elt| Chunk { + parent: self.parent, + index, + first: Some(elt), }) } } @@ -547,8 +569,9 @@ impl<'a, I> Iterator for Chunks<'a, I> /// /// Iterator element type is `I::Item`. pub struct Chunk<'a, I: 'a> - where I: Iterator, - I::Item: 'a, +where + I: Iterator, + I::Item: 'a, { parent: &'a IntoChunks<I>, index: usize, @@ -556,8 +579,9 @@ pub struct Chunk<'a, I: 'a> } impl<'a, I> Drop for Chunk<'a, I> - where I: Iterator, - I::Item: 'a, +where + I: Iterator, + I::Item: 'a, { fn drop(&mut self) { self.parent.drop_group(self.index); @@ -565,8 +589,9 @@ impl<'a, I> Drop for Chunk<'a, I> } impl<'a, I> Iterator for Chunk<'a, I> - where I: Iterator, - I::Item: 'a, +where + I: Iterator, + I::Item: 'a, { type Item = I::Item; #[inline] diff --git a/vendor/itertools/src/grouping_map.rs b/vendor/itertools/src/grouping_map.rs index bb5b582c9..aeb86f1b2 100644 --- a/vendor/itertools/src/grouping_map.rs +++ b/vendor/itertools/src/grouping_map.rs @@ -1,8 +1,8 @@ #![cfg(feature = "use_std")] use crate::MinMaxResult; -use std::collections::HashMap; use std::cmp::Ordering; +use std::collections::HashMap; use std::hash::Hash; use std::iter::Iterator; use std::ops::{Add, Mul}; @@ -18,9 +18,10 @@ impl<I, F> MapForGrouping<I, F> { } impl<K, V, I, F> Iterator for MapForGrouping<I, F> - where I: Iterator<Item = V>, - K: Hash + Eq, - F: FnMut(&V) -> K, +where + I: Iterator<Item = V>, + K: Hash + Eq, + F: FnMut(&V) -> K, { type Item = (K, V); fn next(&mut self) -> Option<Self::Item> { @@ -30,21 +31,22 @@ impl<K, V, I, F> Iterator for MapForGrouping<I, F> /// Creates a new `GroupingMap` from `iter` pub fn new<I, K, V>(iter: I) -> GroupingMap<I> - where I: Iterator<Item = (K, V)>, - K: Hash + Eq, +where + I: Iterator<Item = (K, V)>, + K: Hash + Eq, { GroupingMap { iter } } /// `GroupingMapBy` is an intermediate struct for efficient group-and-fold operations. -/// +/// /// See [`GroupingMap`] for more informations. pub type GroupingMapBy<I, F> = GroupingMap<MapForGrouping<I, F>>; /// `GroupingMap` is an intermediate struct for efficient group-and-fold operations. /// It groups elements by their key and at the same time fold each group /// using some aggregating operation. -/// +/// /// No method on this struct performs temporary allocations. #[derive(Clone, Debug)] #[must_use = "GroupingMap is lazy and do nothing unless consumed"] @@ -53,13 +55,14 @@ pub struct GroupingMap<I> { } impl<I, K, V> GroupingMap<I> - where I: Iterator<Item = (K, V)>, - K: Hash + Eq, +where + I: Iterator<Item = (K, V)>, + K: Hash + Eq, { /// This is the generic way to perform any operation on a `GroupingMap`. /// It's suggested to use this method only to implement custom operations /// when the already provided ones are not enough. - /// + /// /// Groups elements from the `GroupingMap` source by key and applies `operation` to the elements /// of each group sequentially, passing the previously accumulated value, a reference to the key /// and the current element as arguments, and stores the results in an `HashMap`. @@ -68,17 +71,17 @@ impl<I, K, V> GroupingMap<I> /// - the current value of the accumulator of the group if there is currently one; /// - a reference to the key of the group this element belongs to; /// - the element from the source being aggregated; - /// + /// /// If `operation` returns `Some(element)` then the accumulator is updated with `element`, /// otherwise the previous accumulation is discarded. /// /// Return a `HashMap` associating the key of each group with the result of aggregation of /// that group's elements. If the aggregation of the last element of a group discards the /// accumulator then there won't be an entry associated to that group's key. - /// + /// /// ``` /// use itertools::Itertools; - /// + /// /// let data = vec![2, 8, 5, 7, 9, 0, 4, 10]; /// let lookup = data.into_iter() /// .into_grouping_map_by(|&n| n % 4) @@ -89,7 +92,7 @@ impl<I, K, V> GroupingMap<I> /// Some(acc.unwrap_or(0) + val) /// } /// }); - /// + /// /// assert_eq!(lookup[&0], 4); // 0 resets the accumulator so only 4 is summed /// assert_eq!(lookup[&1], 5 + 9); /// assert_eq!(lookup.get(&2), None); // 10 resets the accumulator and nothing is summed afterward @@ -97,7 +100,8 @@ impl<I, K, V> GroupingMap<I> /// assert_eq!(lookup.len(), 3); // The final keys are only 0, 1 and 2 /// ``` pub fn aggregate<FO, R>(self, mut operation: FO) -> HashMap<K, R> - where FO: FnMut(Option<R>, &K, V) -> Option<R>, + where + FO: FnMut(Option<R>, &K, V) -> Option<R>, { let mut destination_map = HashMap::new(); @@ -115,6 +119,50 @@ impl<I, K, V> GroupingMap<I> /// of each group sequentially, passing the previously accumulated value, a reference to the key /// and the current element as arguments, and stores the results in a new map. /// + /// `init` is called to obtain the initial value of each accumulator. + /// + /// `operation` is a function that is invoked on each element with the following parameters: + /// - the current value of the accumulator of the group; + /// - a reference to the key of the group this element belongs to; + /// - the element from the source being accumulated. + /// + /// Return a `HashMap` associating the key of each group with the result of folding that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// + /// #[derive(Debug, Default)] + /// struct Accumulator { + /// acc: usize, + /// } + /// + /// let lookup = (1..=7) + /// .into_grouping_map_by(|&n| n % 3) + /// .fold_with(|_key, _val| Default::default(), |Accumulator { acc }, _key, val| { + /// let acc = acc + val; + /// Accumulator { acc } + /// }); + /// + /// assert_eq!(lookup[&0].acc, 3 + 6); + /// assert_eq!(lookup[&1].acc, 1 + 4 + 7); + /// assert_eq!(lookup[&2].acc, 2 + 5); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn fold_with<FI, FO, R>(self, mut init: FI, mut operation: FO) -> HashMap<K, R> + where + FI: FnMut(&K, &V) -> R, + FO: FnMut(R, &K, V) -> R, + { + self.aggregate(|acc, key, val| { + let acc = acc.unwrap_or_else(|| init(key, &val)); + Some(operation(acc, key, val)) + }) + } + + /// Groups elements from the `GroupingMap` source by key and applies `operation` to the elements + /// of each group sequentially, passing the previously accumulated value, a reference to the key + /// and the current element as arguments, and stores the results in a new map. + /// /// `init` is the value from which will be cloned the initial value of each accumulator. /// /// `operation` is a function that is invoked on each element with the following parameters: @@ -123,27 +171,25 @@ impl<I, K, V> GroupingMap<I> /// - the element from the source being accumulated. /// /// Return a `HashMap` associating the key of each group with the result of folding that group's elements. - /// + /// /// ``` /// use itertools::Itertools; - /// + /// /// let lookup = (1..=7) /// .into_grouping_map_by(|&n| n % 3) /// .fold(0, |acc, _key, val| acc + val); - /// + /// /// assert_eq!(lookup[&0], 3 + 6); /// assert_eq!(lookup[&1], 1 + 4 + 7); /// assert_eq!(lookup[&2], 2 + 5); /// assert_eq!(lookup.len(), 3); /// ``` - pub fn fold<FO, R>(self, init: R, mut operation: FO) -> HashMap<K, R> - where R: Clone, - FO: FnMut(R, &K, V) -> R, + pub fn fold<FO, R>(self, init: R, operation: FO) -> HashMap<K, R> + where + R: Clone, + FO: FnMut(R, &K, V) -> R, { - self.aggregate(|acc, key, val| { - let acc = acc.unwrap_or_else(|| init.clone()); - Some(operation(acc, key, val)) - }) + self.fold_with(|_, _| init.clone(), operation) } /// Groups elements from the `GroupingMap` source by key and applies `operation` to the elements @@ -158,23 +204,24 @@ impl<I, K, V> GroupingMap<I> /// - the element from the source being accumulated. /// /// Return a `HashMap` associating the key of each group with the result of folding that group's elements. - /// + /// /// [`fold`]: GroupingMap::fold - /// + /// /// ``` /// use itertools::Itertools; - /// + /// /// let lookup = (1..=7) /// .into_grouping_map_by(|&n| n % 3) /// .fold_first(|acc, _key, val| acc + val); - /// + /// /// assert_eq!(lookup[&0], 3 + 6); /// assert_eq!(lookup[&1], 1 + 4 + 7); /// assert_eq!(lookup[&2], 2 + 5); /// assert_eq!(lookup.len(), 3); /// ``` pub fn fold_first<FO>(self, mut operation: FO) -> HashMap<K, V> - where FO: FnMut(V, &K, V) -> V, + where + FO: FnMut(V, &K, V) -> V, { self.aggregate(|acc, key, val| { Some(match acc { @@ -185,249 +232,261 @@ impl<I, K, V> GroupingMap<I> } /// Groups elements from the `GroupingMap` source by key and collects the elements of each group in - /// an instance of `C`. The iteration order is preserved when inserting elements. - /// + /// an instance of `C`. The iteration order is preserved when inserting elements. + /// /// Return a `HashMap` associating the key of each group with the collection containing that group's elements. - /// + /// /// ``` /// use itertools::Itertools; /// use std::collections::HashSet; - /// + /// /// let lookup = vec![0, 1, 2, 3, 4, 5, 6, 2, 3, 6].into_iter() /// .into_grouping_map_by(|&n| n % 3) /// .collect::<HashSet<_>>(); - /// + /// /// assert_eq!(lookup[&0], vec![0, 3, 6].into_iter().collect::<HashSet<_>>()); /// assert_eq!(lookup[&1], vec![1, 4].into_iter().collect::<HashSet<_>>()); /// assert_eq!(lookup[&2], vec![2, 5].into_iter().collect::<HashSet<_>>()); /// assert_eq!(lookup.len(), 3); /// ``` pub fn collect<C>(self) -> HashMap<K, C> - where C: Default + Extend<V>, + where + C: Default + Extend<V>, { let mut destination_map = HashMap::new(); self.iter.for_each(|(key, val)| { - destination_map.entry(key).or_insert_with(C::default).extend(Some(val)); + destination_map + .entry(key) + .or_insert_with(C::default) + .extend(Some(val)); }); destination_map } /// Groups elements from the `GroupingMap` source by key and finds the maximum of each group. - /// + /// /// If several elements are equally maximum, the last element is picked. - /// + /// /// Returns a `HashMap` associating the key of each group with the maximum of that group's elements. - /// + /// /// ``` /// use itertools::Itertools; - /// + /// /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() /// .into_grouping_map_by(|&n| n % 3) /// .max(); - /// + /// /// assert_eq!(lookup[&0], 12); /// assert_eq!(lookup[&1], 7); /// assert_eq!(lookup[&2], 8); /// assert_eq!(lookup.len(), 3); /// ``` pub fn max(self) -> HashMap<K, V> - where V: Ord, + where + V: Ord, { self.max_by(|_, v1, v2| V::cmp(v1, v2)) } /// Groups elements from the `GroupingMap` source by key and finds the maximum of each group /// with respect to the specified comparison function. - /// + /// /// If several elements are equally maximum, the last element is picked. - /// + /// /// Returns a `HashMap` associating the key of each group with the maximum of that group's elements. - /// + /// /// ``` /// use itertools::Itertools; - /// + /// /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() /// .into_grouping_map_by(|&n| n % 3) /// .max_by(|_key, x, y| y.cmp(x)); - /// + /// /// assert_eq!(lookup[&0], 3); /// assert_eq!(lookup[&1], 1); /// assert_eq!(lookup[&2], 5); /// assert_eq!(lookup.len(), 3); /// ``` pub fn max_by<F>(self, mut compare: F) -> HashMap<K, V> - where F: FnMut(&K, &V, &V) -> Ordering, + where + F: FnMut(&K, &V, &V) -> Ordering, { self.fold_first(|acc, key, val| match compare(key, &acc, &val) { Ordering::Less | Ordering::Equal => val, - Ordering::Greater => acc + Ordering::Greater => acc, }) } /// Groups elements from the `GroupingMap` source by key and finds the element of each group /// that gives the maximum from the specified function. - /// + /// /// If several elements are equally maximum, the last element is picked. - /// + /// /// Returns a `HashMap` associating the key of each group with the maximum of that group's elements. - /// + /// /// ``` /// use itertools::Itertools; - /// + /// /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() /// .into_grouping_map_by(|&n| n % 3) /// .max_by_key(|_key, &val| val % 4); - /// + /// /// assert_eq!(lookup[&0], 3); /// assert_eq!(lookup[&1], 7); /// assert_eq!(lookup[&2], 5); /// assert_eq!(lookup.len(), 3); /// ``` pub fn max_by_key<F, CK>(self, mut f: F) -> HashMap<K, V> - where F: FnMut(&K, &V) -> CK, - CK: Ord, + where + F: FnMut(&K, &V) -> CK, + CK: Ord, { self.max_by(|key, v1, v2| f(key, v1).cmp(&f(key, v2))) } /// Groups elements from the `GroupingMap` source by key and finds the minimum of each group. - /// + /// /// If several elements are equally minimum, the first element is picked. - /// + /// /// Returns a `HashMap` associating the key of each group with the minimum of that group's elements. - /// + /// /// ``` /// use itertools::Itertools; - /// + /// /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() /// .into_grouping_map_by(|&n| n % 3) /// .min(); - /// + /// /// assert_eq!(lookup[&0], 3); /// assert_eq!(lookup[&1], 1); /// assert_eq!(lookup[&2], 5); /// assert_eq!(lookup.len(), 3); /// ``` pub fn min(self) -> HashMap<K, V> - where V: Ord, + where + V: Ord, { self.min_by(|_, v1, v2| V::cmp(v1, v2)) } /// Groups elements from the `GroupingMap` source by key and finds the minimum of each group /// with respect to the specified comparison function. - /// + /// /// If several elements are equally minimum, the first element is picked. - /// + /// /// Returns a `HashMap` associating the key of each group with the minimum of that group's elements. - /// + /// /// ``` /// use itertools::Itertools; - /// + /// /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() /// .into_grouping_map_by(|&n| n % 3) /// .min_by(|_key, x, y| y.cmp(x)); - /// + /// /// assert_eq!(lookup[&0], 12); /// assert_eq!(lookup[&1], 7); /// assert_eq!(lookup[&2], 8); /// assert_eq!(lookup.len(), 3); /// ``` pub fn min_by<F>(self, mut compare: F) -> HashMap<K, V> - where F: FnMut(&K, &V, &V) -> Ordering, + where + F: FnMut(&K, &V, &V) -> Ordering, { self.fold_first(|acc, key, val| match compare(key, &acc, &val) { Ordering::Less | Ordering::Equal => acc, - Ordering::Greater => val + Ordering::Greater => val, }) } /// Groups elements from the `GroupingMap` source by key and finds the element of each group /// that gives the minimum from the specified function. - /// + /// /// If several elements are equally minimum, the first element is picked. - /// + /// /// Returns a `HashMap` associating the key of each group with the minimum of that group's elements. - /// + /// /// ``` /// use itertools::Itertools; - /// + /// /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() /// .into_grouping_map_by(|&n| n % 3) /// .min_by_key(|_key, &val| val % 4); - /// + /// /// assert_eq!(lookup[&0], 12); /// assert_eq!(lookup[&1], 4); /// assert_eq!(lookup[&2], 8); /// assert_eq!(lookup.len(), 3); /// ``` pub fn min_by_key<F, CK>(self, mut f: F) -> HashMap<K, V> - where F: FnMut(&K, &V) -> CK, - CK: Ord, + where + F: FnMut(&K, &V) -> CK, + CK: Ord, { self.min_by(|key, v1, v2| f(key, v1).cmp(&f(key, v2))) } /// Groups elements from the `GroupingMap` source by key and find the maximum and minimum of /// each group. - /// + /// /// If several elements are equally maximum, the last element is picked. /// If several elements are equally minimum, the first element is picked. - /// + /// /// See [.minmax()](crate::Itertools::minmax) for the non-grouping version. - /// + /// /// Differences from the non grouping version: /// - It never produces a `MinMaxResult::NoElements` /// - It doesn't have any speedup - /// + /// /// Returns a `HashMap` associating the key of each group with the minimum and maximum of that group's elements. - /// + /// /// ``` /// use itertools::Itertools; /// use itertools::MinMaxResult::{OneElement, MinMax}; - /// + /// /// let lookup = vec![1, 3, 4, 5, 7, 9, 12].into_iter() /// .into_grouping_map_by(|&n| n % 3) /// .minmax(); - /// + /// /// assert_eq!(lookup[&0], MinMax(3, 12)); /// assert_eq!(lookup[&1], MinMax(1, 7)); /// assert_eq!(lookup[&2], OneElement(5)); /// assert_eq!(lookup.len(), 3); /// ``` pub fn minmax(self) -> HashMap<K, MinMaxResult<V>> - where V: Ord, + where + V: Ord, { self.minmax_by(|_, v1, v2| V::cmp(v1, v2)) } /// Groups elements from the `GroupingMap` source by key and find the maximum and minimum of /// each group with respect to the specified comparison function. - /// + /// /// If several elements are equally maximum, the last element is picked. /// If several elements are equally minimum, the first element is picked. - /// + /// /// It has the same differences from the non-grouping version as `minmax`. - /// + /// /// Returns a `HashMap` associating the key of each group with the minimum and maximum of that group's elements. - /// + /// /// ``` /// use itertools::Itertools; /// use itertools::MinMaxResult::{OneElement, MinMax}; - /// + /// /// let lookup = vec![1, 3, 4, 5, 7, 9, 12].into_iter() /// .into_grouping_map_by(|&n| n % 3) /// .minmax_by(|_key, x, y| y.cmp(x)); - /// + /// /// assert_eq!(lookup[&0], MinMax(12, 3)); /// assert_eq!(lookup[&1], MinMax(7, 1)); /// assert_eq!(lookup[&2], OneElement(5)); /// assert_eq!(lookup.len(), 3); /// ``` pub fn minmax_by<F>(self, mut compare: F) -> HashMap<K, MinMaxResult<V>> - where F: FnMut(&K, &V, &V) -> Ordering, + where + F: FnMut(&K, &V, &V) -> Ordering, { self.aggregate(|acc, key, val| { Some(match acc { @@ -455,80 +514,83 @@ impl<I, K, V> GroupingMap<I> /// Groups elements from the `GroupingMap` source by key and find the elements of each group /// that gives the minimum and maximum from the specified function. - /// + /// /// If several elements are equally maximum, the last element is picked. /// If several elements are equally minimum, the first element is picked. - /// + /// /// It has the same differences from the non-grouping version as `minmax`. - /// + /// /// Returns a `HashMap` associating the key of each group with the minimum and maximum of that group's elements. - /// + /// /// ``` /// use itertools::Itertools; /// use itertools::MinMaxResult::{OneElement, MinMax}; - /// + /// /// let lookup = vec![1, 3, 4, 5, 7, 9, 12].into_iter() /// .into_grouping_map_by(|&n| n % 3) /// .minmax_by_key(|_key, &val| val % 4); - /// + /// /// assert_eq!(lookup[&0], MinMax(12, 3)); /// assert_eq!(lookup[&1], MinMax(4, 7)); /// assert_eq!(lookup[&2], OneElement(5)); /// assert_eq!(lookup.len(), 3); /// ``` pub fn minmax_by_key<F, CK>(self, mut f: F) -> HashMap<K, MinMaxResult<V>> - where F: FnMut(&K, &V) -> CK, - CK: Ord, + where + F: FnMut(&K, &V) -> CK, + CK: Ord, { self.minmax_by(|key, v1, v2| f(key, v1).cmp(&f(key, v2))) } - + /// Groups elements from the `GroupingMap` source by key and sums them. - /// + /// /// This is just a shorthand for `self.fold_first(|acc, _, val| acc + val)`. /// It is more limited than `Iterator::sum` since it doesn't use the `Sum` trait. - /// + /// /// Returns a `HashMap` associating the key of each group with the sum of that group's elements. - /// + /// /// ``` /// use itertools::Itertools; - /// + /// /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() /// .into_grouping_map_by(|&n| n % 3) /// .sum(); - /// + /// /// assert_eq!(lookup[&0], 3 + 9 + 12); /// assert_eq!(lookup[&1], 1 + 4 + 7); /// assert_eq!(lookup[&2], 5 + 8); /// assert_eq!(lookup.len(), 3); /// ``` pub fn sum(self) -> HashMap<K, V> - where V: Add<V, Output = V> + where + V: Add<V, Output = V>, { self.fold_first(|acc, _, val| acc + val) } /// Groups elements from the `GroupingMap` source by key and multiply them. - /// + /// /// This is just a shorthand for `self.fold_first(|acc, _, val| acc * val)`. /// It is more limited than `Iterator::product` since it doesn't use the `Product` trait. - /// + /// /// Returns a `HashMap` associating the key of each group with the product of that group's elements. - /// + /// /// ``` /// use itertools::Itertools; - /// + /// /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() /// .into_grouping_map_by(|&n| n % 3) /// .product(); - /// + /// /// assert_eq!(lookup[&0], 3 * 9 * 12); /// assert_eq!(lookup[&1], 1 * 4 * 7); /// assert_eq!(lookup[&2], 5 * 8); /// assert_eq!(lookup.len(), 3); /// ``` pub fn product(self) -> HashMap<K, V> - where V: Mul<V, Output = V>, + where + V: Mul<V, Output = V>, { self.fold_first(|acc, _, val| acc * val) } diff --git a/vendor/itertools/src/impl_macros.rs b/vendor/itertools/src/impl_macros.rs index a029843b0..3db5ba021 100644 --- a/vendor/itertools/src/impl_macros.rs +++ b/vendor/itertools/src/impl_macros.rs @@ -1,4 +1,4 @@ -//! +//! //! Implementation's internal macros macro_rules! debug_fmt_fields { @@ -27,3 +27,8 @@ macro_rules! clone_fields { macro_rules! ignore_ident{ ($id:ident, $($t:tt)*) => {$($t)*}; } + +macro_rules! count_ident { + () => {0}; + ($i0:ident $($i:ident)*) => {1 + count_ident!($($i)*)}; +} diff --git a/vendor/itertools/src/intersperse.rs b/vendor/itertools/src/intersperse.rs index 10a3a5389..5f4f7938a 100644 --- a/vendor/itertools/src/intersperse.rs +++ b/vendor/itertools/src/intersperse.rs @@ -1,5 +1,5 @@ -use std::iter::{Fuse, FusedIterator}; use super::size_hint; +use std::iter::{Fuse, FusedIterator}; pub trait IntersperseElement<Item> { fn generate(&mut self) -> Item; @@ -26,12 +26,13 @@ pub type Intersperse<I> = IntersperseWith<I, IntersperseElementSimple<<I as Iter /// Create a new Intersperse iterator pub fn intersperse<I>(iter: I, elt: I::Item) -> Intersperse<I> - where I: Iterator, +where + I: Iterator, { intersperse_with(iter, IntersperseElementSimple(elt)) } -impl<Item, F: FnMut()->Item> IntersperseElement<Item> for F { +impl<Item, F: FnMut() -> Item> IntersperseElement<Item> for F { fn generate(&mut self) -> Item { self() } @@ -48,71 +49,94 @@ impl<Item, F: FnMut()->Item> IntersperseElement<Item> for F { #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] #[derive(Clone, Debug)] pub struct IntersperseWith<I, ElemF> - where I: Iterator, +where + I: Iterator, { element: ElemF, iter: Fuse<I>, - peek: Option<I::Item>, + /// `peek` is None while no item have been taken out of `iter` (at definition). + /// Then `peek` will alternatively be `Some(None)` and `Some(Some(item))`, + /// where `None` indicates it's time to generate from `element` (unless `iter` is empty). + peek: Option<Option<I::Item>>, } /// Create a new `IntersperseWith` iterator pub fn intersperse_with<I, ElemF>(iter: I, elt: ElemF) -> IntersperseWith<I, ElemF> - where I: Iterator, +where + I: Iterator, { - let mut iter = iter.fuse(); IntersperseWith { - peek: iter.next(), - iter, + peek: None, + iter: iter.fuse(), element: elt, } } impl<I, ElemF> Iterator for IntersperseWith<I, ElemF> - where I: Iterator, - ElemF: IntersperseElement<I::Item> +where + I: Iterator, + ElemF: IntersperseElement<I::Item>, { type Item = I::Item; #[inline] fn next(&mut self) -> Option<Self::Item> { - if self.peek.is_some() { - self.peek.take() - } else { - self.peek = self.iter.next(); - if self.peek.is_some() { - Some(self.element.generate()) - } else { - None + let Self { + element, + iter, + peek, + } = self; + match peek { + Some(item @ Some(_)) => item.take(), + Some(None) => match iter.next() { + new @ Some(_) => { + *peek = Some(new); + Some(element.generate()) + } + None => None, + }, + None => { + *peek = Some(None); + iter.next() } } } fn size_hint(&self) -> (usize, Option<usize>) { - // 2 * SH + { 1 or 0 } - let has_peek = self.peek.is_some() as usize; - let sh = self.iter.size_hint(); - size_hint::add_scalar(size_hint::add(sh, sh), has_peek) + let mut sh = self.iter.size_hint(); + sh = size_hint::add(sh, sh); + match self.peek { + Some(Some(_)) => size_hint::add_scalar(sh, 1), + Some(None) => sh, + None => size_hint::sub_scalar(sh, 1), + } } - fn fold<B, F>(mut self, init: B, mut f: F) -> B where - Self: Sized, F: FnMut(B, Self::Item) -> B, + fn fold<B, F>(self, init: B, mut f: F) -> B + where + Self: Sized, + F: FnMut(B, Self::Item) -> B, { + let Self { + mut element, + mut iter, + peek, + } = self; let mut accum = init; - if let Some(x) = self.peek.take() { + if let Some(x) = peek.unwrap_or_else(|| iter.next()) { accum = f(accum, x); } - let element = &mut self.element; - - self.iter.fold(accum, - |accum, x| { - let accum = f(accum, element.generate()); - f(accum, x) + iter.fold(accum, |accum, x| { + let accum = f(accum, element.generate()); + f(accum, x) }) } } impl<I, ElemF> FusedIterator for IntersperseWith<I, ElemF> - where I: Iterator, - ElemF: IntersperseElement<I::Item> -{} +where + I: Iterator, + ElemF: IntersperseElement<I::Item>, +{ +} diff --git a/vendor/itertools/src/k_smallest.rs b/vendor/itertools/src/k_smallest.rs index acaea5941..6af66cfaf 100644 --- a/vendor/itertools/src/k_smallest.rs +++ b/vendor/itertools/src/k_smallest.rs @@ -2,7 +2,9 @@ use alloc::collections::BinaryHeap; use core::cmp::Ord; pub(crate) fn k_smallest<T: Ord, I: Iterator<Item = T>>(mut iter: I, k: usize) -> BinaryHeap<T> { - if k == 0 { return BinaryHeap::new(); } + if k == 0 { + return BinaryHeap::new(); + } let mut heap = iter.by_ref().take(k).collect::<BinaryHeap<_>>(); diff --git a/vendor/itertools/src/kmerge_impl.rs b/vendor/itertools/src/kmerge_impl.rs index 509d5fc6a..c077cdda1 100644 --- a/vendor/itertools/src/kmerge_impl.rs +++ b/vendor/itertools/src/kmerge_impl.rs @@ -2,9 +2,9 @@ use crate::size_hint; use crate::Itertools; use alloc::vec::Vec; +use std::fmt; use std::iter::FusedIterator; use std::mem::replace; -use std::fmt; /// Head element and Tail iterator pair /// @@ -15,24 +15,21 @@ use std::fmt; /// `KMerge` into a min-heap. #[derive(Debug)] struct HeadTail<I> - where I: Iterator +where + I: Iterator, { head: I::Item, tail: I, } impl<I> HeadTail<I> - where I: Iterator +where + I: Iterator, { /// Constructs a `HeadTail` from an `Iterator`. Returns `None` if the `Iterator` is empty. fn new(mut it: I) -> Option<HeadTail<I>> { let head = it.next(); - head.map(|h| { - HeadTail { - head: h, - tail: it, - } - }) + head.map(|h| HeadTail { head: h, tail: it }) } /// Get the next element and update `head`, returning the old head in `Some`. @@ -53,15 +50,17 @@ impl<I> HeadTail<I> } impl<I> Clone for HeadTail<I> - where I: Iterator + Clone, - I::Item: Clone +where + I: Iterator + Clone, + I::Item: Clone, { clone_fields!(head, tail); } /// Make `data` a heap (min-heap w.r.t the sorting). fn heapify<T, S>(data: &mut [T], mut less_than: S) - where S: FnMut(&T, &T) -> bool +where + S: FnMut(&T, &T) -> bool, { for i in (0..data.len() / 2).rev() { sift_down(data, i, &mut less_than); @@ -70,7 +69,8 @@ fn heapify<T, S>(data: &mut [T], mut less_than: S) /// Sift down element at `index` (`heap` is a min-heap wrt the ordering) fn sift_down<T, S>(heap: &mut [T], index: usize, mut less_than: S) - where S: FnMut(&T, &T) -> bool +where + S: FnMut(&T, &T) -> bool, { debug_assert!(index <= heap.len()); let mut pos = index; @@ -81,7 +81,7 @@ fn sift_down<T, S>(heap: &mut [T], index: usize, mut less_than: S) while child + 1 < heap.len() { // pick the smaller of the two children // use arithmetic to avoid an unpredictable branch - child += less_than(&heap[child+1], &heap[child]) as usize; + child += less_than(&heap[child + 1], &heap[child]) as usize; // sift down is done if we are already in order if !less_than(&heap[child], &heap[pos]) { @@ -119,7 +119,7 @@ impl<T: PartialOrd> KMergePredicate<T> for KMergeByLt { } } -impl<T, F: FnMut(&T, &T)->bool> KMergePredicate<T> for F { +impl<T, F: FnMut(&T, &T) -> bool> KMergePredicate<T> for F { fn kmerge_pred(&mut self, a: &T, b: &T) -> bool { self(a, b) } @@ -138,9 +138,10 @@ impl<T, F: FnMut(&T, &T)->bool> KMergePredicate<T> for F { /// } /// ``` pub fn kmerge<I>(iterable: I) -> KMerge<<I::Item as IntoIterator>::IntoIter> - where I: IntoIterator, - I::Item: IntoIterator, - <<I as IntoIterator>::Item as IntoIterator>::Item: PartialOrd +where + I: IntoIterator, + I::Item: IntoIterator, + <<I as IntoIterator>::Item as IntoIterator>::Item: PartialOrd, { kmerge_by(iterable, KMergeByLt) } @@ -154,15 +155,17 @@ pub fn kmerge<I>(iterable: I) -> KMerge<<I::Item as IntoIterator>::IntoIter> /// information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct KMergeBy<I, F> - where I: Iterator, +where + I: Iterator, { heap: Vec<HeadTail<I>>, less_than: F, } impl<I, F> fmt::Debug for KMergeBy<I, F> - where I: Iterator + fmt::Debug, - I::Item: fmt::Debug, +where + I: Iterator + fmt::Debug, + I::Item: fmt::Debug, { debug_fmt_fields!(KMergeBy, heap); } @@ -170,11 +173,14 @@ impl<I, F> fmt::Debug for KMergeBy<I, F> /// Create an iterator that merges elements of the contained iterators. /// /// [`IntoIterator`] enabled version of [`Itertools::kmerge_by`]. -pub fn kmerge_by<I, F>(iterable: I, mut less_than: F) - -> KMergeBy<<I::Item as IntoIterator>::IntoIter, F> - where I: IntoIterator, - I::Item: IntoIterator, - F: KMergePredicate<<<I as IntoIterator>::Item as IntoIterator>::Item>, +pub fn kmerge_by<I, F>( + iterable: I, + mut less_than: F, +) -> KMergeBy<<I::Item as IntoIterator>::IntoIter, F> +where + I: IntoIterator, + I::Item: IntoIterator, + F: KMergePredicate<<<I as IntoIterator>::Item as IntoIterator>::Item>, { let iter = iterable.into_iter(); let (lower, _) = iter.size_hint(); @@ -185,16 +191,18 @@ pub fn kmerge_by<I, F>(iterable: I, mut less_than: F) } impl<I, F> Clone for KMergeBy<I, F> - where I: Iterator + Clone, - I::Item: Clone, - F: Clone, +where + I: Iterator + Clone, + I::Item: Clone, + F: Clone, { clone_fields!(heap, less_than); } impl<I, F> Iterator for KMergeBy<I, F> - where I: Iterator, - F: KMergePredicate<I::Item> +where + I: Iterator, + F: KMergePredicate<I::Item>, { type Item = I::Item; @@ -208,20 +216,25 @@ impl<I, F> Iterator for KMergeBy<I, F> self.heap.swap_remove(0).head }; let less_than = &mut self.less_than; - sift_down(&mut self.heap, 0, |a, b| less_than.kmerge_pred(&a.head, &b.head)); + sift_down(&mut self.heap, 0, |a, b| { + less_than.kmerge_pred(&a.head, &b.head) + }); Some(result) } fn size_hint(&self) -> (usize, Option<usize>) { #[allow(deprecated)] //TODO: once msrv hits 1.51. replace `fold1` with `reduce` - self.heap.iter() - .map(|i| i.size_hint()) - .fold1(size_hint::add) - .unwrap_or((0, Some(0))) + self.heap + .iter() + .map(|i| i.size_hint()) + .fold1(size_hint::add) + .unwrap_or((0, Some(0))) } } impl<I, F> FusedIterator for KMergeBy<I, F> - where I: Iterator, - F: KMergePredicate<I::Item> -{} +where + I: Iterator, + F: KMergePredicate<I::Item>, +{ +} diff --git a/vendor/itertools/src/lazy_buffer.rs b/vendor/itertools/src/lazy_buffer.rs index ca24062aa..38c7d405b 100644 --- a/vendor/itertools/src/lazy_buffer.rs +++ b/vendor/itertools/src/lazy_buffer.rs @@ -1,10 +1,12 @@ -use std::ops::Index; use alloc::vec::Vec; +use std::iter::Fuse; +use std::ops::Index; + +use crate::size_hint::{self, SizeHint}; #[derive(Debug, Clone)] pub struct LazyBuffer<I: Iterator> { - pub it: I, - done: bool, + it: Fuse<I>, buffer: Vec<I::Item>, } @@ -14,8 +16,7 @@ where { pub fn new(it: I) -> LazyBuffer<I> { LazyBuffer { - it, - done: false, + it: it.fuse(), buffer: Vec::new(), } } @@ -24,27 +25,28 @@ where self.buffer.len() } + pub fn size_hint(&self) -> SizeHint { + size_hint::add_scalar(self.it.size_hint(), self.len()) + } + + pub fn count(self) -> usize { + self.len() + self.it.count() + } + pub fn get_next(&mut self) -> bool { - if self.done { - return false; - } if let Some(x) = self.it.next() { self.buffer.push(x); true } else { - self.done = true; false } } pub fn prefill(&mut self, len: usize) { let buffer_len = self.buffer.len(); - - if !self.done && len > buffer_len { + if len > buffer_len { let delta = len - buffer_len; - self.buffer.extend(self.it.by_ref().take(delta)); - self.done = self.buffer.len() < len; } } } @@ -53,7 +55,7 @@ impl<I, J> Index<J> for LazyBuffer<I> where I: Iterator, I::Item: Sized, - Vec<I::Item>: Index<J> + Vec<I::Item>: Index<J>, { type Output = <Vec<I::Item> as Index<J>>::Output; diff --git a/vendor/itertools/src/lib.rs b/vendor/itertools/src/lib.rs index c23a65db5..11b624d48 100644 --- a/vendor/itertools/src/lib.rs +++ b/vendor/itertools/src/lib.rs @@ -1,5 +1,5 @@ #![warn(missing_docs)] -#![crate_name="itertools"] +#![crate_name = "itertools"] #![cfg_attr(not(feature = "use_std"), no_std)] //! Extra iterator adaptors, functions and macros. @@ -42,8 +42,8 @@ //! //! ## Rust Version //! -//! This version of itertools requires Rust 1.32 or later. -#![doc(html_root_url="https://docs.rs/itertools/0.8/")] +//! This version of itertools requires Rust 1.43.1 or later. +#![doc(html_root_url = "https://docs.rs/itertools/0.11/")] #[cfg(not(feature = "use_std"))] extern crate core as std; @@ -52,28 +52,24 @@ extern crate core as std; extern crate alloc; #[cfg(feature = "use_alloc")] -use alloc::{ - string::String, - vec::Vec, -}; +use alloc::{string::String, vec::Vec}; pub use either::Either; use core::borrow::Borrow; +use std::cmp::Ordering; #[cfg(feature = "use_std")] use std::collections::HashMap; -use std::iter::{IntoIterator, once}; -use std::cmp::Ordering; -use std::fmt; #[cfg(feature = "use_std")] use std::collections::HashSet; -#[cfg(feature = "use_std")] -use std::hash::Hash; +use std::fmt; #[cfg(feature = "use_alloc")] use std::fmt::Write; +#[cfg(feature = "use_std")] +use std::hash::Hash; +use std::iter::{once, IntoIterator}; #[cfg(feature = "use_alloc")] type VecIntoIter<T> = alloc::vec::IntoIter<T>; -#[cfg(feature = "use_alloc")] use std::iter::FromIterator; #[macro_use] @@ -85,73 +81,55 @@ pub use std::iter as __std_iter; /// The concrete iterator types. pub mod structs { + #[cfg(feature = "use_alloc")] + pub use crate::adaptors::MultiProduct; pub use crate::adaptors::{ - Dedup, - DedupBy, - DedupWithCount, - DedupByWithCount, - Interleave, - InterleaveShortest, - FilterMapOk, - FilterOk, - Product, - PutBack, - Batching, - MapInto, - MapOk, - Merge, - MergeBy, - TakeWhileRef, - WhileSome, - Coalesce, - TupleCombinations, - Positions, - Update, + Batching, Coalesce, Dedup, DedupBy, DedupByWithCount, DedupWithCount, FilterMapOk, + FilterOk, Interleave, InterleaveShortest, MapInto, MapOk, Positions, Product, PutBack, + TakeWhileRef, TupleCombinations, Update, WhileSome, }; #[allow(deprecated)] pub use crate::adaptors::{MapResults, Step}; #[cfg(feature = "use_alloc")] - pub use crate::adaptors::MultiProduct; - #[cfg(feature = "use_alloc")] pub use crate::combinations::Combinations; #[cfg(feature = "use_alloc")] pub use crate::combinations_with_replacement::CombinationsWithReplacement; pub use crate::cons_tuples_impl::ConsTuples; + #[cfg(feature = "use_std")] + pub use crate::duplicates_impl::{Duplicates, DuplicatesBy}; pub use crate::exactly_one_err::ExactlyOneError; - pub use crate::format::{Format, FormatWith}; pub use crate::flatten_ok::FlattenOk; + pub use crate::format::{Format, FormatWith}; + #[cfg(feature = "use_alloc")] + pub use crate::groupbylazy::{Chunk, Chunks, Group, GroupBy, Groups, IntoChunks}; #[cfg(feature = "use_std")] pub use crate::grouping_map::{GroupingMap, GroupingMapBy}; - #[cfg(feature = "use_alloc")] - pub use crate::groupbylazy::{IntoChunks, Chunk, Chunks, GroupBy, Group, Groups}; pub use crate::intersperse::{Intersperse, IntersperseWith}; #[cfg(feature = "use_alloc")] pub use crate::kmerge_impl::{KMerge, KMergeBy}; - pub use crate::merge_join::MergeJoinBy; + pub use crate::merge_join::{Merge, MergeBy, MergeJoinBy}; #[cfg(feature = "use_alloc")] pub use crate::multipeek_impl::MultiPeek; + pub use crate::pad_tail::PadUsing; #[cfg(feature = "use_alloc")] pub use crate::peek_nth::PeekNth; - pub use crate::pad_tail::PadUsing; pub use crate::peeking_take_while::PeekingTakeWhile; #[cfg(feature = "use_alloc")] pub use crate::permutations::Permutations; - pub use crate::process_results_impl::ProcessResults; #[cfg(feature = "use_alloc")] pub use crate::powerset::Powerset; + pub use crate::process_results_impl::ProcessResults; #[cfg(feature = "use_alloc")] pub use crate::put_back_n_impl::PutBackN; #[cfg(feature = "use_alloc")] pub use crate::rciter_impl::RcIter; pub use crate::repeatn::RepeatN; #[allow(deprecated)] - pub use crate::sources::{RepeatCall, Unfold, Iterate}; + pub use crate::sources::{Iterate, RepeatCall, Unfold}; pub use crate::take_while_inclusive::TakeWhileInclusive; #[cfg(feature = "use_alloc")] pub use crate::tee::Tee; - pub use crate::tuple_impl::{TupleBuffer, TupleWindows, CircularTupleWindows, Tuples}; - #[cfg(feature = "use_std")] - pub use crate::duplicates_impl::{Duplicates, DuplicatesBy}; + pub use crate::tuple_impl::{CircularTupleWindows, TupleBuffer, TupleWindows, Tuples}; #[cfg(feature = "use_std")] pub use crate::unique_impl::{Unique, UniqueBy}; pub use crate::with_position::WithPosition; @@ -165,22 +143,22 @@ pub mod traits { pub use crate::tuple_impl::HomogeneousTuple; } -#[allow(deprecated)] -pub use crate::structs::*; pub use crate::concat_impl::concat; pub use crate::cons_tuples_impl::cons_tuples; pub use crate::diff::diff_with; pub use crate::diff::Diff; #[cfg(feature = "use_alloc")] -pub use crate::kmerge_impl::{kmerge_by}; +pub use crate::kmerge_impl::kmerge_by; pub use crate::minmax::MinMaxResult; pub use crate::peeking_take_while::PeekingNext; pub use crate::process_results_impl::process_results; pub use crate::repeatn::repeat_n; #[allow(deprecated)] -pub use crate::sources::{repeat_call, unfold, iterate}; -pub use crate::with_position::Position; +pub use crate::sources::{iterate, repeat_call, unfold}; +#[allow(deprecated)] +pub use crate::structs::*; pub use crate::unziptuple::{multiunzip, MultiUnzip}; +pub use crate::with_position::Position; pub use crate::ziptuple::multizip; mod adaptors; mod either_or_both; @@ -189,24 +167,26 @@ pub use crate::either_or_both::EitherOrBoth; pub mod free; #[doc(inline)] pub use crate::free::*; -mod concat_impl; -mod cons_tuples_impl; #[cfg(feature = "use_alloc")] mod combinations; #[cfg(feature = "use_alloc")] mod combinations_with_replacement; -mod exactly_one_err; +mod concat_impl; +mod cons_tuples_impl; mod diff; -mod flatten_ok; #[cfg(feature = "use_std")] +mod duplicates_impl; +mod exactly_one_err; +#[cfg(feature = "use_alloc")] mod extrema_set; +mod flatten_ok; mod format; -#[cfg(feature = "use_std")] -mod grouping_map; #[cfg(feature = "use_alloc")] mod group_map; #[cfg(feature = "use_alloc")] mod groupbylazy; +#[cfg(feature = "use_std")] +mod grouping_map; mod intersperse; #[cfg(feature = "use_alloc")] mod k_smallest; @@ -239,8 +219,6 @@ mod take_while_inclusive; mod tee; mod tuple_impl; #[cfg(feature = "use_std")] -mod duplicates_impl; -#[cfg(feature = "use_std")] mod unique_impl; mod unziptuple; mod with_position; @@ -430,7 +408,7 @@ macro_rules! chain { /// return a regular value of some other kind. /// [`.next_tuple()`](Itertools::next_tuple) is an example and the first regular /// method in the list. -pub trait Itertools : Iterator { +pub trait Itertools: Iterator { // adaptors /// Alternate elements from two iterators until both have run out. @@ -446,8 +424,9 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![1, -1, 2, -2, 3, 4, 5, 6]); /// ``` fn interleave<J>(self, other: J) -> Interleave<Self, J::IntoIter> - where J: IntoIterator<Item = Self::Item>, - Self: Sized + where + J: IntoIterator<Item = Self::Item>, + Self: Sized, { interleave(self, other) } @@ -464,8 +443,9 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![1, -1, 2, -2, 3]); /// ``` fn interleave_shortest<J>(self, other: J) -> InterleaveShortest<Self, J::IntoIter> - where J: IntoIterator<Item = Self::Item>, - Self: Sized + where + J: IntoIterator<Item = Self::Item>, + Self: Sized, { adaptors::interleave_shortest(self, other.into_iter()) } @@ -483,8 +463,9 @@ pub trait Itertools : Iterator { /// itertools::assert_equal((0..3).intersperse(8), vec![0, 8, 1, 8, 2]); /// ``` fn intersperse(self, element: Self::Item) -> Intersperse<Self> - where Self: Sized, - Self::Item: Clone + where + Self: Sized, + Self::Item: Clone, { intersperse::intersperse(self, element) } @@ -504,8 +485,9 @@ pub trait Itertools : Iterator { /// assert_eq!(i, 8); /// ``` fn intersperse_with<F>(self, element: F) -> IntersperseWith<Self, F> - where Self: Sized, - F: FnMut() -> Self::Item + where + Self: Sized, + F: FnMut() -> Self::Item, { intersperse::intersperse_with(self, element) } @@ -538,8 +520,9 @@ pub trait Itertools : Iterator { /// ``` #[inline] fn zip_longest<J>(self, other: J) -> ZipLongest<Self, J::IntoIter> - where J: IntoIterator, - Self: Sized + where + J: IntoIterator, + Self: Sized, { zip_longest::zip_longest(self, other.into_iter()) } @@ -551,8 +534,9 @@ pub trait Itertools : Iterator { /// lengths. #[inline] fn zip_eq<J>(self, other: J) -> ZipEq<Self, J::IntoIter> - where J: IntoIterator, - Self: Sized + where + J: IntoIterator, + Self: Sized, { zip_eq(self, other) } @@ -581,8 +565,9 @@ pub trait Itertools : Iterator { /// ``` /// fn batching<B, F>(self, f: F) -> Batching<Self, F> - where F: FnMut(&mut Self) -> Option<B>, - Self: Sized + where + F: FnMut(&mut Self) -> Option<B>, + Self: Sized, { adaptors::batching(self, f) } @@ -623,9 +608,10 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn group_by<K, F>(self, key: F) -> GroupBy<K, Self, F> - where Self: Sized, - F: FnMut(&Self::Item) -> K, - K: PartialEq, + where + Self: Sized, + F: FnMut(&Self::Item) -> K, + K: PartialEq, { groupbylazy::new(self, key) } @@ -659,7 +645,8 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn chunks(self, size: usize) -> IntoChunks<Self> - where Self: Sized, + where + Self: Sized, { assert!(size != 0); groupbylazy::new_chunks(self, size) @@ -699,9 +686,10 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![(1, 2, 3), (2, 3, 4)]); /// ``` fn tuple_windows<T>(self) -> TupleWindows<Self, T> - where Self: Sized + Iterator<Item = T::Item>, - T: traits::HomogeneousTuple, - T::Item: Clone + where + Self: Sized + Iterator<Item = T::Item>, + T: traits::HomogeneousTuple, + T::Item: Clone, { tuple_impl::tuple_windows(self) } @@ -734,9 +722,10 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![(1, 2, 3), (2, 3, 4), (3, 4, 1), (4, 1, 2)]); /// ``` fn circular_tuple_windows<T>(self) -> CircularTupleWindows<Self, T> - where Self: Sized + Clone + Iterator<Item = T::Item> + ExactSizeIterator, - T: tuple_impl::TupleCollect + Clone, - T::Item: Clone + where + Self: Sized + Clone + Iterator<Item = T::Item> + ExactSizeIterator, + T: tuple_impl::TupleCollect + Clone, + T::Item: Clone, { tuple_impl::circular_tuple_windows(self) } @@ -772,8 +761,9 @@ pub trait Itertools : Iterator { /// /// See also [`Tuples::into_buffer`]. fn tuples<T>(self) -> Tuples<Self, T> - where Self: Sized + Iterator<Item = T::Item>, - T: traits::HomogeneousTuple + where + Self: Sized + Iterator<Item = T::Item>, + T: traits::HomogeneousTuple, { tuple_impl::tuples(self) } @@ -797,8 +787,9 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn tee(self) -> (Tee<Self>, Tee<Self>) - where Self: Sized, - Self::Item: Clone + where + Self: Sized, + Self::Item: Clone, { tee::new(self) } @@ -819,10 +810,11 @@ pub trait Itertools : Iterator { /// let it = (0..8).step(3); /// itertools::assert_equal(it, vec![0, 3, 6]); /// ``` - #[deprecated(note="Use std .step_by() instead", since="0.8.0")] + #[deprecated(note = "Use std .step_by() instead", since = "0.8.0")] #[allow(deprecated)] fn step(self, n: usize) -> Step<Self> - where Self: Sized + where + Self: Sized, { adaptors::step(self, n) } @@ -835,17 +827,19 @@ pub trait Itertools : Iterator { /// (1i32..42i32).map_into::<f64>().collect_vec(); /// ``` fn map_into<R>(self) -> MapInto<Self, R> - where Self: Sized, - Self::Item: Into<R>, + where + Self: Sized, + Self::Item: Into<R>, { adaptors::map_into(self) } /// See [`.map_ok()`](Itertools::map_ok). - #[deprecated(note="Use .map_ok() instead", since="0.10.0")] + #[deprecated(note = "Use .map_ok() instead", since = "0.10.0")] fn map_results<F, T, U, E>(self, f: F) -> MapOk<Self, F> - where Self: Iterator<Item = Result<T, E>> + Sized, - F: FnMut(T) -> U, + where + Self: Iterator<Item = Result<T, E>> + Sized, + F: FnMut(T) -> U, { self.map_ok(f) } @@ -862,8 +856,9 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![Ok(42), Err(false), Ok(12)]); /// ``` fn map_ok<F, T, U, E>(self, f: F) -> MapOk<Self, F> - where Self: Iterator<Item = Result<T, E>> + Sized, - F: FnMut(T) -> U, + where + Self: Iterator<Item = Result<T, E>> + Sized, + F: FnMut(T) -> U, { adaptors::map_ok(self, f) } @@ -880,8 +875,9 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![Ok(22), Err(false)]); /// ``` fn filter_ok<F, T, E>(self, f: F) -> FilterOk<Self, F> - where Self: Iterator<Item = Result<T, E>> + Sized, - F: FnMut(&T) -> bool, + where + Self: Iterator<Item = Result<T, E>> + Sized, + F: FnMut(&T) -> bool, { adaptors::filter_ok(self, f) } @@ -898,8 +894,9 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![Ok(44), Err(false)]); /// ``` fn filter_map_ok<F, T, U, E>(self, f: F) -> FilterMapOk<Self, F> - where Self: Iterator<Item = Result<T, E>> + Sized, - F: FnMut(T) -> Option<U>, + where + Self: Iterator<Item = Result<T, E>> + Sized, + F: FnMut(T) -> Option<U>, { adaptors::filter_map_ok(self, f) } @@ -922,8 +919,9 @@ pub trait Itertools : Iterator { /// assert_eq!(output_result, Err(false)); /// ``` fn flatten_ok<T, E>(self) -> FlattenOk<Self, T, E> - where Self: Iterator<Item = Result<T, E>> + Sized, - T: IntoIterator + where + Self: Iterator<Item = Result<T, E>> + Sized, + T: IntoIterator, { flatten_ok::flatten_ok(self) } @@ -959,8 +957,9 @@ pub trait Itertools : Iterator { /// assert!(second_max.is_err()); /// ``` fn process_results<F, T, E, R>(self, processor: F) -> Result<R, E> - where Self: Iterator<Item = Result<T, E>> + Sized, - F: FnOnce(ProcessResults<Self, E>) -> R + where + Self: Iterator<Item = Result<T, E>> + Sized, + F: FnOnce(ProcessResults<Self, E>) -> R, { process_results(self, processor) } @@ -980,9 +979,10 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![0, 0, 3, 5, 6, 9, 10]); /// ``` fn merge<J>(self, other: J) -> Merge<Self, J::IntoIter> - where Self: Sized, - Self::Item: PartialOrd, - J: IntoIterator<Item = Self::Item> + where + Self: Sized, + Self::Item: PartialOrd, + J: IntoIterator<Item = Self::Item>, { merge(self, other) } @@ -1004,11 +1004,12 @@ pub trait Itertools : Iterator { /// ``` fn merge_by<J, F>(self, other: J, is_first: F) -> MergeBy<Self, J::IntoIter, F> - where Self: Sized, - J: IntoIterator<Item = Self::Item>, - F: FnMut(&Self::Item, &Self::Item) -> bool + where + Self: Sized, + J: IntoIterator<Item = Self::Item>, + F: FnMut(&Self::Item, &Self::Item) -> bool, { - adaptors::merge_by_new(self, other.into_iter(), is_first) + merge_join::merge_by_new(self, other.into_iter(), is_first) } /// Create an iterator that merges items from both this and the specified @@ -1070,10 +1071,10 @@ pub trait Itertools : Iterator { /// ``` #[inline] fn merge_join_by<J, F, T>(self, other: J, cmp_fn: F) -> MergeJoinBy<Self, J::IntoIter, F> - where J: IntoIterator, - F: FnMut(&Self::Item, &J::Item) -> T, - T: merge_join::OrderingOrBool<Self::Item, J::Item>, - Self: Sized + where + J: IntoIterator, + F: FnMut(&Self::Item, &J::Item) -> T, + Self: Sized, { merge_join_by(self, other, cmp_fn) } @@ -1096,9 +1097,10 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn kmerge(self) -> KMerge<<Self::Item as IntoIterator>::IntoIter> - where Self: Sized, - Self::Item: IntoIterator, - <Self::Item as IntoIterator>::Item: PartialOrd, + where + Self: Sized, + Self::Item: IntoIterator, + <Self::Item as IntoIterator>::Item: PartialOrd, { kmerge(self) } @@ -1124,12 +1126,11 @@ pub trait Itertools : Iterator { /// assert_eq!(it.last(), Some(-7.)); /// ``` #[cfg(feature = "use_alloc")] - fn kmerge_by<F>(self, first: F) - -> KMergeBy<<Self::Item as IntoIterator>::IntoIter, F> - where Self: Sized, - Self::Item: IntoIterator, - F: FnMut(&<Self::Item as IntoIterator>::Item, - &<Self::Item as IntoIterator>::Item) -> bool + fn kmerge_by<F>(self, first: F) -> KMergeBy<<Self::Item as IntoIterator>::IntoIter, F> + where + Self: Sized, + Self::Item: IntoIterator, + F: FnMut(&<Self::Item as IntoIterator>::Item, &<Self::Item as IntoIterator>::Item) -> bool, { kmerge_by(self, first) } @@ -1146,10 +1147,11 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![(0, 'α'), (0, 'β'), (1, 'α'), (1, 'β')]); /// ``` fn cartesian_product<J>(self, other: J) -> Product<Self, J::IntoIter> - where Self: Sized, - Self::Item: Clone, - J: IntoIterator, - J::IntoIter: Clone + where + Self: Sized, + Self::Item: Clone, + J: IntoIterator, + J::IntoIter: Clone, { adaptors::cartesian_product(self, other.into_iter()) } @@ -1181,10 +1183,11 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn multi_cartesian_product(self) -> MultiProduct<<Self::Item as IntoIterator>::IntoIter> - where Self: Sized, - Self::Item: IntoIterator, - <Self::Item as IntoIterator>::IntoIter: Clone, - <Self::Item as IntoIterator>::Item: Clone + where + Self: Sized, + Self::Item: IntoIterator, + <Self::Item as IntoIterator>::IntoIter: Clone, + <Self::Item as IntoIterator>::Item: Clone, { adaptors::multi_cartesian_product(self) } @@ -1218,9 +1221,9 @@ pub trait Itertools : Iterator { /// vec![-6., 4., -1.]); /// ``` fn coalesce<F>(self, f: F) -> Coalesce<Self, F> - where Self: Sized, - F: FnMut(Self::Item, Self::Item) - -> Result<Self::Item, (Self::Item, Self::Item)> + where + Self: Sized, + F: FnMut(Self::Item, Self::Item) -> Result<Self::Item, (Self::Item, Self::Item)>, { adaptors::coalesce(self, f) } @@ -1240,8 +1243,9 @@ pub trait Itertools : Iterator { /// vec![1., 2., 3., 2.]); /// ``` fn dedup(self) -> Dedup<Self> - where Self: Sized, - Self::Item: PartialEq, + where + Self: Sized, + Self::Item: PartialEq, { adaptors::dedup(self) } @@ -1262,8 +1266,9 @@ pub trait Itertools : Iterator { /// vec![(0, 1.), (0, 2.), (0, 3.), (1, 2.)]); /// ``` fn dedup_by<Cmp>(self, cmp: Cmp) -> DedupBy<Self, Cmp> - where Self: Sized, - Cmp: FnMut(&Self::Item, &Self::Item)->bool, + where + Self: Sized, + Cmp: FnMut(&Self::Item, &Self::Item) -> bool, { adaptors::dedup_by(self, cmp) } @@ -1330,8 +1335,9 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_std")] fn duplicates(self) -> Duplicates<Self> - where Self: Sized, - Self::Item: Eq + Hash + where + Self: Sized, + Self::Item: Eq + Hash, { duplicates_impl::duplicates(self) } @@ -1355,9 +1361,10 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_std")] fn duplicates_by<V, F>(self, f: F) -> DuplicatesBy<Self, V, F> - where Self: Sized, - V: Eq + Hash, - F: FnMut(&Self::Item) -> V + where + Self: Sized, + V: Eq + Hash, + F: FnMut(&Self::Item) -> V, { duplicates_impl::duplicates_by(self, f) } @@ -1382,8 +1389,9 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_std")] fn unique(self) -> Unique<Self> - where Self: Sized, - Self::Item: Clone + Eq + Hash + where + Self: Sized, + Self::Item: Clone + Eq + Hash, { unique_impl::unique(self) } @@ -1408,9 +1416,10 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_std")] fn unique_by<V, F>(self, f: F) -> UniqueBy<Self, V, F> - where Self: Sized, - V: Eq + Hash, - F: FnMut(&Self::Item) -> V + where + Self: Sized, + V: Eq + Hash, + F: FnMut(&Self::Item) -> V, { unique_impl::unique_by(self, f) } @@ -1428,8 +1437,9 @@ pub trait Itertools : Iterator { /// See also [`.take_while_ref()`](Itertools::take_while_ref) /// which is a similar adaptor. fn peeking_take_while<F>(&mut self, accept: F) -> PeekingTakeWhile<Self, F> - where Self: Sized + PeekingNext, - F: FnMut(&Self::Item) -> bool, + where + Self: Sized + PeekingNext, + F: FnMut(&Self::Item) -> bool, { peeking_take_while::peeking_take_while(self, accept) } @@ -1453,8 +1463,9 @@ pub trait Itertools : Iterator { /// /// ``` fn take_while_ref<F>(&mut self, accept: F) -> TakeWhileRef<Self, F> - where Self: Clone, - F: FnMut(&Self::Item) -> bool + where + Self: Clone, + F: FnMut(&Self::Item) -> bool, { adaptors::take_while_ref(self, accept) } @@ -1519,7 +1530,7 @@ pub trait Itertools : Iterator { /// .collect(); /// let expected: Vec<_> = vec![1, 2, 3].into_iter().map(NoCloneImpl).collect(); /// assert_eq!(filtered, expected); - fn take_while_inclusive<F>(&mut self, accept: F) -> TakeWhileInclusive<Self, F> + fn take_while_inclusive<F>(self, accept: F) -> TakeWhileInclusive<Self, F> where Self: Sized, F: FnMut(&Self::Item) -> bool, @@ -1542,7 +1553,8 @@ pub trait Itertools : Iterator { /// /// ``` fn while_some<A>(self) -> WhileSome<Self> - where Self: Sized + Iterator<Item = Option<A>> + where + Self: Sized + Iterator<Item = Option<A>>, { adaptors::while_some(self) } @@ -1581,9 +1593,10 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]); /// ``` fn tuple_combinations<T>(self) -> TupleCombinations<Self, T> - where Self: Sized + Clone, - Self::Item: Clone, - T: adaptors::HasCombination<Self>, + where + Self: Sized + Clone, + Self::Item: Clone, + T: adaptors::HasCombination<Self>, { adaptors::tuple_combinations(self) } @@ -1619,8 +1632,9 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn combinations(self, k: usize) -> Combinations<Self> - where Self: Sized, - Self::Item: Clone + where + Self: Sized, + Self::Item: Clone, { combinations::combinations(self, k) } @@ -1662,6 +1676,9 @@ pub trait Itertools : Iterator { /// If `k` is greater than the length of the input iterator, the resultant /// iterator adaptor will be empty. /// + /// If you are looking for permutations with replacements, + /// use `repeat_n(iter, k).multi_cartesian_product()` instead. + /// /// ``` /// use itertools::Itertools; /// @@ -1692,8 +1709,9 @@ pub trait Itertools : Iterator { /// re-iterated if the permutations adaptor is completed and re-iterated. #[cfg(feature = "use_alloc")] fn permutations(self, k: usize) -> Permutations<Self> - where Self: Sized, - Self::Item: Clone + where + Self: Sized, + Self::Item: Clone, { permutations::permutations(self, k) } @@ -1728,8 +1746,9 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn powerset(self) -> Powerset<Self> - where Self: Sized, - Self::Item: Clone, + where + Self: Sized, + Self::Item: Clone, { powerset::powerset(self) } @@ -1752,8 +1771,9 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![18, 16, 14, 12, 10, 4, 3, 2, 1, 0]); /// ``` fn pad_using<F>(self, min: usize, f: F) -> PadUsing<Self, F> - where Self: Sized, - F: FnMut(usize) -> Self::Item + where + Self: Sized, + F: FnMut(usize) -> Self::Item, { pad_tail::pad_using(self, min, f) } @@ -1778,7 +1798,8 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![(Position::Only, 0)]); /// ``` fn with_position(self) -> WithPosition<Self> - where Self: Sized, + where + Self: Sized, { with_position::with_position(self) } @@ -1797,8 +1818,9 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(data.iter().positions(|v| v % 2 == 1).rev(), vec![7, 6, 3, 2, 0]); /// ``` fn positions<P>(self, predicate: P) -> Positions<Self, P> - where Self: Sized, - P: FnMut(Self::Item) -> bool, + where + Self: Sized, + P: FnMut(Self::Item) -> bool, { adaptors::positions(self, predicate) } @@ -1814,8 +1836,9 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![vec![1, 0], vec![3, 2, 1, 0]]); /// ``` fn update<F>(self, updater: F) -> Update<Self, F> - where Self: Sized, - F: FnMut(&mut Self::Item), + where + Self: Sized, + F: FnMut(&mut Self::Item), { adaptors::update(self, updater) } @@ -1835,8 +1858,9 @@ pub trait Itertools : Iterator { /// assert_eq!(Some((1, 2)), iter.next_tuple()); /// ``` fn next_tuple<T>(&mut self) -> Option<T> - where Self: Sized + Iterator<Item = T::Item>, - T: traits::HomogeneousTuple + where + Self: Sized + Iterator<Item = T::Item>, + T: traits::HomogeneousTuple, { T::collect_from_iter_no_buf(self) } @@ -1860,19 +1884,19 @@ pub trait Itertools : Iterator { /// } /// ``` fn collect_tuple<T>(mut self) -> Option<T> - where Self: Sized + Iterator<Item = T::Item>, - T: traits::HomogeneousTuple + where + Self: Sized + Iterator<Item = T::Item>, + T: traits::HomogeneousTuple, { match self.next_tuple() { elt @ Some(_) => match self.next() { Some(_) => None, None => elt, }, - _ => None + _ => None, } } - /// Find the position and value of the first element satisfying a predicate. /// /// The iterator is not advanced past the first element found. @@ -1884,7 +1908,8 @@ pub trait Itertools : Iterator { /// assert_eq!(text.chars().find_position(|ch| ch.is_lowercase()), Some((1, 'α'))); /// ``` fn find_position<P>(&mut self, mut pred: P) -> Option<(usize, Self::Item)> - where P: FnMut(&Self::Item) -> bool + where + P: FnMut(&Self::Item) -> bool, { for (index, elt) in self.enumerate() { if pred(&elt) { @@ -1906,12 +1931,20 @@ pub trait Itertools : Iterator { /// assert_eq!(std::iter::empty::<i32>().find_or_last(|&x| x > 5), None); /// ``` fn find_or_last<P>(mut self, mut predicate: P) -> Option<Self::Item> - where Self: Sized, - P: FnMut(&Self::Item) -> bool, + where + Self: Sized, + P: FnMut(&Self::Item) -> bool, { let mut prev = None; - self.find_map(|x| if predicate(&x) { Some(x) } else { prev = Some(x); None }) - .or(prev) + self.find_map(|x| { + if predicate(&x) { + Some(x) + } else { + prev = Some(x); + None + } + }) + .or(prev) } /// Find the value of the first element satisfying a predicate or return the first element, if any. /// @@ -1926,8 +1959,9 @@ pub trait Itertools : Iterator { /// assert_eq!(std::iter::empty::<i32>().find_or_first(|&x| x > 5), None); /// ``` fn find_or_first<P>(mut self, mut predicate: P) -> Option<Self::Item> - where Self: Sized, - P: FnMut(&Self::Item) -> bool, + where + Self: Sized, + P: FnMut(&Self::Item) -> bool, { let first = self.next()?; Some(if predicate(&first) { @@ -1987,8 +2021,9 @@ pub trait Itertools : Iterator { /// assert!(data.into_iter().all_equal()); /// ``` fn all_equal(&mut self) -> bool - where Self: Sized, - Self::Item: PartialEq, + where + Self: Sized, + Self::Item: PartialEq, { match self.next() { None => true, @@ -2014,9 +2049,9 @@ pub trait Itertools : Iterator { /// assert_eq!(data.into_iter().all_equal_value(), Err(None)); /// ``` fn all_equal_value(&mut self) -> Result<Self::Item, Option<(Self::Item, Self::Item)>> - where - Self: Sized, - Self::Item: PartialEq + where + Self: Sized, + Self::Item: PartialEq, { let first = self.next().ok_or(None)?; let other = self.find(|x| x != &first); @@ -2044,8 +2079,9 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_std")] fn all_unique(&mut self) -> bool - where Self: Sized, - Self::Item: Eq + Hash + where + Self: Sized, + Self::Item: Eq + Hash, { let mut used = HashSet::new(); self.all(move |elt| used.insert(elt)) @@ -2067,7 +2103,8 @@ pub trait Itertools : Iterator { /// *Fusing notes: if the iterator is exhausted by dropping, /// the result of calling `.next()` again depends on the iterator implementation.* fn dropping(mut self, n: usize) -> Self - where Self: Sized + where + Self: Sized, { if n > 0 { self.nth(n - 1); @@ -2091,8 +2128,9 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(init, vec![0, 3, 6]); /// ``` fn dropping_back(mut self, n: usize) -> Self - where Self: Sized, - Self: DoubleEndedIterator + where + Self: Sized, + Self: DoubleEndedIterator, { if n > 0 { (&mut self).rev().nth(n - 1); @@ -2117,10 +2155,11 @@ pub trait Itertools : Iterator { /// /// itertools::assert_equal(rx.iter(), vec![1, 3, 5, 7, 9]); /// ``` - #[deprecated(note="Use .for_each() instead", since="0.8.0")] + #[deprecated(note = "Use .for_each() instead", since = "0.8.0")] fn foreach<F>(self, f: F) - where F: FnMut(Self::Item), - Self: Sized, + where + F: FnMut(Self::Item), + Self: Sized, { self.for_each(f); } @@ -2139,8 +2178,10 @@ pub trait Itertools : Iterator { /// vec![1, 2, 3, 4, 5, 6]); /// ``` fn concat(self) -> Self::Item - where Self: Sized, - Self::Item: Extend<<<Self as Iterator>::Item as IntoIterator>::Item> + IntoIterator + Default + where + Self: Sized, + Self::Item: + Extend<<<Self as Iterator>::Item as IntoIterator>::Item> + IntoIterator + Default, { concat(self) } @@ -2149,7 +2190,8 @@ pub trait Itertools : Iterator { /// for convenience. #[cfg(feature = "use_alloc")] fn collect_vec(self) -> Vec<Self::Item> - where Self: Sized + where + Self: Sized, { self.collect() } @@ -2174,7 +2216,6 @@ pub trait Itertools : Iterator { /// Ok(()) /// } /// ``` - #[cfg(feature = "use_alloc")] fn try_collect<T, U, E>(self) -> Result<U, E> where Self: Sized + Iterator<Item = Result<T, E>>, @@ -2200,8 +2241,9 @@ pub trait Itertools : Iterator { /// ``` #[inline] fn set_from<'a, A: 'a, J>(&mut self, from: J) -> usize - where Self: Iterator<Item = &'a mut A>, - J: IntoIterator<Item = A> + where + Self: Iterator<Item = &'a mut A>, + J: IntoIterator<Item = A>, { let mut count = 0; for elt in from { @@ -2226,7 +2268,8 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn join(&mut self, sep: &str) -> String - where Self::Item: std::fmt::Display + where + Self::Item: std::fmt::Display, { match self.next() { None => String::new(), @@ -2260,7 +2303,8 @@ pub trait Itertools : Iterator { /// "1.10, 2.72, -3.00"); /// ``` fn format(self, sep: &str) -> Format<Self> - where Self: Sized, + where + Self: Sized, { format::new_format_default(self, sep) } @@ -2298,17 +2342,19 @@ pub trait Itertools : Iterator { /// /// ``` fn format_with<F>(self, sep: &str, format: F) -> FormatWith<Self, F> - where Self: Sized, - F: FnMut(Self::Item, &mut dyn FnMut(&dyn fmt::Display) -> fmt::Result) -> fmt::Result, + where + Self: Sized, + F: FnMut(Self::Item, &mut dyn FnMut(&dyn fmt::Display) -> fmt::Result) -> fmt::Result, { format::new_format(self, sep, format) } /// See [`.fold_ok()`](Itertools::fold_ok). - #[deprecated(note="Use .fold_ok() instead", since="0.10.0")] + #[deprecated(note = "Use .fold_ok() instead", since = "0.10.0")] fn fold_results<A, E, B, F>(&mut self, start: B, f: F) -> Result<B, E> - where Self: Iterator<Item = Result<A, E>>, - F: FnMut(B, A) -> B + where + Self: Iterator<Item = Result<A, E>>, + F: FnMut(B, A) -> B, { self.fold_ok(start, f) } @@ -2327,7 +2373,9 @@ pub trait Itertools : Iterator { /// For example the sequence *Ok(1), Ok(2), Ok(3)* will result in a /// computation like this: /// - /// ```ignore + /// ```no_run + /// # let start = 0; + /// # let f = |x, y| x + y; /// let mut accum = start; /// accum = f(accum, 1); /// accum = f(accum, 2); @@ -2356,8 +2404,9 @@ pub trait Itertools : Iterator { /// ); /// ``` fn fold_ok<A, E, B, F>(&mut self, mut start: B, mut f: F) -> Result<B, E> - where Self: Iterator<Item = Result<A, E>>, - F: FnMut(B, A) -> B + where + Self: Iterator<Item = Result<A, E>>, + F: FnMut(B, A) -> B, { for elt in self { match elt { @@ -2388,8 +2437,9 @@ pub trait Itertools : Iterator { /// assert_eq!(more_values.next().unwrap(), Some(0)); /// ``` fn fold_options<A, B, F>(&mut self, mut start: B, mut f: F) -> Option<B> - where Self: Iterator<Item = Option<A>>, - F: FnMut(B, A) -> B + where + Self: Iterator<Item = Option<A>>, + F: FnMut(B, A) -> B, { for elt in self { match elt { @@ -2414,8 +2464,9 @@ pub trait Itertools : Iterator { /// ``` #[deprecated(since = "0.10.2", note = "Use `Iterator::reduce` instead")] fn fold1<F>(mut self, f: F) -> Option<Self::Item> - where F: FnMut(Self::Item, Self::Item) -> Self::Item, - Self: Sized, + where + F: FnMut(Self::Item, Self::Item) -> Self::Item, + Self: Sized, { self.next().map(move |x| self.fold(x, f)) } @@ -2448,7 +2499,18 @@ pub trait Itertools : Iterator { /// └─f─f─f─f─f─f /// ``` /// - /// If `f` is associative, prefer the normal [`Iterator::reduce`] instead. + /// If `f` is associative you should also decide carefully: + /// + /// - if `f` is a trivial operation like `u32::wrapping_add`, prefer the normal + /// [`Iterator::reduce`] instead since it will most likely result in the generation of simpler + /// code because the compiler is able to optimize it + /// - otherwise if `f` is non-trivial like `format!`, you should use `tree_fold1` since it + /// reduces the number of operations from `O(n)` to `O(ln(n))` + /// + /// Here "non-trivial" means: + /// + /// - any allocating operation + /// - any function that is a composition of many operations /// /// ``` /// use itertools::Itertools; @@ -2469,44 +2531,48 @@ pub trait Itertools : Iterator { /// (0..10).fold1(|x, y| x - y)); /// ``` fn tree_fold1<F>(mut self, mut f: F) -> Option<Self::Item> - where F: FnMut(Self::Item, Self::Item) -> Self::Item, - Self: Sized, + where + F: FnMut(Self::Item, Self::Item) -> Self::Item, + Self: Sized, { type State<T> = Result<T, Option<T>>; fn inner0<T, II, FF>(it: &mut II, f: &mut FF) -> State<T> - where - II: Iterator<Item = T>, - FF: FnMut(T, T) -> T + where + II: Iterator<Item = T>, + FF: FnMut(T, T) -> T, { // This function could be replaced with `it.next().ok_or(None)`, // but half the useful tree_fold1 work is combining adjacent items, // so put that in a form that LLVM is more likely to optimize well. - let a = - if let Some(v) = it.next() { v } - else { return Err(None) }; - let b = - if let Some(v) = it.next() { v } - else { return Err(Some(a)) }; + let a = if let Some(v) = it.next() { + v + } else { + return Err(None); + }; + let b = if let Some(v) = it.next() { + v + } else { + return Err(Some(a)); + }; Ok(f(a, b)) } fn inner<T, II, FF>(stop: usize, it: &mut II, f: &mut FF) -> State<T> - where - II: Iterator<Item = T>, - FF: FnMut(T, T) -> T + where + II: Iterator<Item = T>, + FF: FnMut(T, T) -> T, { let mut x = inner0(it, f)?; for height in 0..stop { // Try to get another tree the same size with which to combine it, // creating a new tree that's twice as big for next time around. - let next = - if height == 0 { - inner0(it, f) - } else { - inner(height, it, f) - }; + let next = if height == 0 { + inner0(it, f) + } else { + inner(height, it, f) + }; match next { Ok(y) => x = f(x, y), @@ -2567,19 +2633,19 @@ pub trait Itertools : Iterator { /// `fold()` called the provided closure for every item of the callee iterator, /// `fold_while()` actually stopped iterating as soon as it encountered `Fold::Done(_)`. fn fold_while<B, F>(&mut self, init: B, mut f: F) -> FoldWhile<B> - where Self: Sized, - F: FnMut(B, Self::Item) -> FoldWhile<B> - { - use Result::{ - Ok as Continue, - Err as Break, - }; - - let result = self.try_fold(init, #[inline(always)] |acc, v| - match f(acc, v) { - FoldWhile::Continue(acc) => Continue(acc), - FoldWhile::Done(acc) => Break(acc), - } + where + Self: Sized, + F: FnMut(B, Self::Item) -> FoldWhile<B>, + { + use Result::{Err as Break, Ok as Continue}; + + let result = self.try_fold( + init, + #[inline(always)] + |acc, v| match f(acc, v) { + FoldWhile::Continue(acc) => Continue(acc), + FoldWhile::Done(acc) => Break(acc), + }, ); match result { @@ -2610,11 +2676,11 @@ pub trait Itertools : Iterator { /// assert_eq!(nonempty_sum, Some(55)); /// ``` fn sum1<S>(mut self) -> Option<S> - where Self: Sized, - S: std::iter::Sum<Self::Item>, + where + Self: Sized, + S: std::iter::Sum<Self::Item>, { - self.next() - .map(|first| once(first).chain(self).sum()) + self.next().map(|first| once(first).chain(self).sum()) } /// Iterate over the entire iterator and multiply all the elements. @@ -2638,11 +2704,11 @@ pub trait Itertools : Iterator { /// assert_eq!(nonempty_product, Some(3628800)); /// ``` fn product1<P>(mut self) -> Option<P> - where Self: Sized, - P: std::iter::Product<Self::Item>, + where + Self: Sized, + P: std::iter::Product<Self::Item>, { - self.next() - .map(|first| once(first).chain(self).product()) + self.next().map(|first| once(first).chain(self).product()) } /// Sort all iterator elements into a new iterator in ascending order. @@ -2650,7 +2716,7 @@ pub trait Itertools : Iterator { /// **Note:** This consumes the entire iterator, uses the /// [`slice::sort_unstable`] method and returns the result as a new /// iterator that owns its elements. - /// + /// /// This sort is unstable (i.e., may reorder equal elements). /// /// The sorted iterator, if directly collected to a `Vec`, is converted @@ -2666,8 +2732,9 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn sorted_unstable(self) -> VecIntoIter<Self::Item> - where Self: Sized, - Self::Item: Ord + where + Self: Sized, + Self::Item: Ord, { // Use .sort_unstable() directly since it is not quite identical with // .sort_by(Ord::cmp) @@ -2681,7 +2748,7 @@ pub trait Itertools : Iterator { /// **Note:** This consumes the entire iterator, uses the /// [`slice::sort_unstable_by`] method and returns the result as a new /// iterator that owns its elements. - /// + /// /// This sort is unstable (i.e., may reorder equal elements). /// /// The sorted iterator, if directly collected to a `Vec`, is converted @@ -2703,8 +2770,9 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn sorted_unstable_by<F>(self, cmp: F) -> VecIntoIter<Self::Item> - where Self: Sized, - F: FnMut(&Self::Item, &Self::Item) -> Ordering, + where + Self: Sized, + F: FnMut(&Self::Item, &Self::Item) -> Ordering, { let mut v = Vec::from_iter(self); v.sort_unstable_by(cmp); @@ -2716,7 +2784,7 @@ pub trait Itertools : Iterator { /// **Note:** This consumes the entire iterator, uses the /// [`slice::sort_unstable_by_key`] method and returns the result as a new /// iterator that owns its elements. - /// + /// /// This sort is unstable (i.e., may reorder equal elements). /// /// The sorted iterator, if directly collected to a `Vec`, is converted @@ -2738,9 +2806,10 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn sorted_unstable_by_key<K, F>(self, f: F) -> VecIntoIter<Self::Item> - where Self: Sized, - K: Ord, - F: FnMut(&Self::Item) -> K, + where + Self: Sized, + K: Ord, + F: FnMut(&Self::Item) -> K, { let mut v = Vec::from_iter(self); v.sort_unstable_by_key(f); @@ -2752,7 +2821,7 @@ pub trait Itertools : Iterator { /// **Note:** This consumes the entire iterator, uses the /// [`slice::sort`] method and returns the result as a new /// iterator that owns its elements. - /// + /// /// This sort is stable (i.e., does not reorder equal elements). /// /// The sorted iterator, if directly collected to a `Vec`, is converted @@ -2768,8 +2837,9 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn sorted(self) -> VecIntoIter<Self::Item> - where Self: Sized, - Self::Item: Ord + where + Self: Sized, + Self::Item: Ord, { // Use .sort() directly since it is not quite identical with // .sort_by(Ord::cmp) @@ -2783,7 +2853,7 @@ pub trait Itertools : Iterator { /// **Note:** This consumes the entire iterator, uses the /// [`slice::sort_by`] method and returns the result as a new /// iterator that owns its elements. - /// + /// /// This sort is stable (i.e., does not reorder equal elements). /// /// The sorted iterator, if directly collected to a `Vec`, is converted @@ -2805,8 +2875,9 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn sorted_by<F>(self, cmp: F) -> VecIntoIter<Self::Item> - where Self: Sized, - F: FnMut(&Self::Item, &Self::Item) -> Ordering, + where + Self: Sized, + F: FnMut(&Self::Item, &Self::Item) -> Ordering, { let mut v = Vec::from_iter(self); v.sort_by(cmp); @@ -2818,7 +2889,7 @@ pub trait Itertools : Iterator { /// **Note:** This consumes the entire iterator, uses the /// [`slice::sort_by_key`] method and returns the result as a new /// iterator that owns its elements. - /// + /// /// This sort is stable (i.e., does not reorder equal elements). /// /// The sorted iterator, if directly collected to a `Vec`, is converted @@ -2840,9 +2911,10 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn sorted_by_key<K, F>(self, f: F) -> VecIntoIter<Self::Item> - where Self: Sized, - K: Ord, - F: FnMut(&Self::Item) -> K, + where + Self: Sized, + K: Ord, + F: FnMut(&Self::Item) -> K, { let mut v = Vec::from_iter(self); v.sort_by_key(f); @@ -2855,7 +2927,7 @@ pub trait Itertools : Iterator { /// **Note:** This consumes the entire iterator, uses the /// [`slice::sort_by_cached_key`] method and returns the result as a new /// iterator that owns its elements. - /// + /// /// This sort is stable (i.e., does not reorder equal elements). /// /// The sorted iterator, if directly collected to a `Vec`, is converted @@ -2916,8 +2988,9 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_alloc")] fn k_smallest(self, k: usize) -> VecIntoIter<Self::Item> - where Self: Sized, - Self::Item: Ord + where + Self: Sized, + Self::Item: Ord, { crate::k_smallest::k_smallest(self, k) .into_sorted_vec() @@ -2946,10 +3019,11 @@ pub trait Itertools : Iterator { /// assert_eq!(failures, [false, true]); /// ``` fn partition_map<A, B, F, L, R>(self, mut predicate: F) -> (A, B) - where Self: Sized, - F: FnMut(Self::Item) -> Either<L, R>, - A: Default + Extend<L>, - B: Default + Extend<R>, + where + Self: Sized, + F: FnMut(Self::Item) -> Either<L, R>, + A: Default + Extend<L>, + B: Default + Extend<R>, { let mut left = A::default(); let mut right = B::default(); @@ -2978,10 +3052,10 @@ pub trait Itertools : Iterator { /// assert_eq!(failures, [false, true]); /// ``` fn partition_result<A, B, T, E>(self) -> (A, B) - where - Self: Iterator<Item = Result<T, E>> + Sized, - A: Default + Extend<T>, - B: Default + Extend<E>, + where + Self: Iterator<Item = Result<T, E>> + Sized, + A: Default + Extend<T>, + B: Default + Extend<E>, { self.partition_map(|r| match r { Ok(v) => Either::Left(v), @@ -3007,8 +3081,9 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_std")] fn into_group_map<K, V>(self) -> HashMap<K, Vec<V>> - where Self: Iterator<Item=(K, V)> + Sized, - K: Hash + Eq, + where + Self: Iterator<Item = (K, V)> + Sized, + K: Hash + Eq, { group_map::into_group_map(self) } @@ -3042,10 +3117,10 @@ pub trait Itertools : Iterator { /// ``` #[cfg(feature = "use_std")] fn into_group_map_by<K, V, F>(self, f: F) -> HashMap<K, Vec<V>> - where - Self: Iterator<Item=V> + Sized, - K: Hash + Eq, - F: Fn(&V) -> K, + where + Self: Iterator<Item = V> + Sized, + K: Hash + Eq, + F: Fn(&V) -> K, { group_map::into_group_map_by(self, f) } @@ -3061,8 +3136,9 @@ pub trait Itertools : Iterator { /// on what operations are available. #[cfg(feature = "use_std")] fn into_grouping_map<K, V>(self) -> GroupingMap<Self> - where Self: Iterator<Item=(K, V)> + Sized, - K: Hash + Eq, + where + Self: Iterator<Item = (K, V)> + Sized, + K: Hash + Eq, { grouping_map::new(self) } @@ -3077,9 +3153,10 @@ pub trait Itertools : Iterator { /// on what operations are available. #[cfg(feature = "use_std")] fn into_grouping_map_by<K, V, F>(self, key_mapper: F) -> GroupingMapBy<Self, F> - where Self: Iterator<Item=V> + Sized, - K: Hash + Eq, - F: FnMut(&V) -> K + where + Self: Iterator<Item = V> + Sized, + K: Hash + Eq, + F: FnMut(&V) -> K, { grouping_map::new(grouping_map::MapForGrouping::new(self, key_mapper)) } @@ -3106,9 +3183,11 @@ pub trait Itertools : Iterator { /// /// The elements can be floats but no particular result is guaranteed /// if an element is NaN. - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn min_set(self) -> Vec<Self::Item> - where Self: Sized, Self::Item: Ord + where + Self: Sized, + Self::Item: Ord, { extrema_set::min_set_impl(self, |_| (), |x, y, _, _| x.cmp(y)) } @@ -3137,15 +3216,13 @@ pub trait Itertools : Iterator { /// /// The elements can be floats but no particular result is guaranteed /// if an element is NaN. - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn min_set_by<F>(self, mut compare: F) -> Vec<Self::Item> - where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering + where + Self: Sized, + F: FnMut(&Self::Item, &Self::Item) -> Ordering, { - extrema_set::min_set_impl( - self, - |_| (), - |x, y, _, _| compare(x, y) - ) + extrema_set::min_set_impl(self, |_| (), |x, y, _, _| compare(x, y)) } /// Return all minimum elements of an iterator, as determined by @@ -3171,9 +3248,12 @@ pub trait Itertools : Iterator { /// /// The elements can be floats but no particular result is guaranteed /// if an element is NaN. - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn min_set_by_key<K, F>(self, key: F) -> Vec<Self::Item> - where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K + where + Self: Sized, + K: Ord, + F: FnMut(&Self::Item) -> K, { extrema_set::min_set_impl(self, key, |_, _, kx, ky| kx.cmp(ky)) } @@ -3200,9 +3280,11 @@ pub trait Itertools : Iterator { /// /// The elements can be floats but no particular result is guaranteed /// if an element is NaN. - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn max_set(self) -> Vec<Self::Item> - where Self: Sized, Self::Item: Ord + where + Self: Sized, + Self::Item: Ord, { extrema_set::max_set_impl(self, |_| (), |x, y, _, _| x.cmp(y)) } @@ -3231,15 +3313,13 @@ pub trait Itertools : Iterator { /// /// The elements can be floats but no particular result is guaranteed /// if an element is NaN. - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn max_set_by<F>(self, mut compare: F) -> Vec<Self::Item> - where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering + where + Self: Sized, + F: FnMut(&Self::Item, &Self::Item) -> Ordering, { - extrema_set::max_set_impl( - self, - |_| (), - |x, y, _, _| compare(x, y) - ) + extrema_set::max_set_impl(self, |_| (), |x, y, _, _| compare(x, y)) } /// Return all maximum elements of an iterator, as determined by @@ -3265,9 +3345,12 @@ pub trait Itertools : Iterator { /// /// The elements can be floats but no particular result is guaranteed /// if an element is NaN. - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn max_set_by_key<K, F>(self, key: F) -> Vec<Self::Item> - where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K + where + Self: Sized, + K: Ord, + F: FnMut(&Self::Item) -> K, { extrema_set::max_set_impl(self, key, |_, _, kx, ky| kx.cmp(ky)) } @@ -3308,7 +3391,9 @@ pub trait Itertools : Iterator { /// The elements can be floats but no particular result is guaranteed /// if an element is NaN. fn minmax(self) -> MinMaxResult<Self::Item> - where Self: Sized, Self::Item: PartialOrd + where + Self: Sized, + Self::Item: PartialOrd, { minmax::minmax_impl(self, |_| (), |x, y, _, _| x < y) } @@ -3325,7 +3410,10 @@ pub trait Itertools : Iterator { /// The keys can be floats but no particular result is guaranteed /// if a key is NaN. fn minmax_by_key<K, F>(self, key: F) -> MinMaxResult<Self::Item> - where Self: Sized, K: PartialOrd, F: FnMut(&Self::Item) -> K + where + Self: Sized, + K: PartialOrd, + F: FnMut(&Self::Item) -> K, { minmax::minmax_impl(self, key, |_, _, xk, yk| xk < yk) } @@ -3339,13 +3427,11 @@ pub trait Itertools : Iterator { /// the last maximal element wins. This matches the behavior of the standard /// [`Iterator::min`] and [`Iterator::max`] methods. fn minmax_by<F>(self, mut compare: F) -> MinMaxResult<Self::Item> - where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering + where + Self: Sized, + F: FnMut(&Self::Item, &Self::Item) -> Ordering, { - minmax::minmax_impl( - self, - |_| (), - |x, y, _, _| Ordering::Less == compare(x, y) - ) + minmax::minmax_impl(self, |_| (), |x, y, _, _| Ordering::Less == compare(x, y)) } /// Return the position of the maximum element in the iterator. @@ -3368,7 +3454,9 @@ pub trait Itertools : Iterator { /// assert_eq!(a.iter().position_max(), Some(1)); /// ``` fn position_max(self) -> Option<usize> - where Self: Sized, Self::Item: Ord + where + Self: Sized, + Self::Item: Ord, { self.enumerate() .max_by(|x, y| Ord::cmp(&x.1, &y.1)) @@ -3396,7 +3484,10 @@ pub trait Itertools : Iterator { /// assert_eq!(a.iter().position_max_by_key(|x| x.abs()), Some(3)); /// ``` fn position_max_by_key<K, F>(self, mut key: F) -> Option<usize> - where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K + where + Self: Sized, + K: Ord, + F: FnMut(&Self::Item) -> K, { self.enumerate() .max_by(|x, y| Ord::cmp(&key(&x.1), &key(&y.1))) @@ -3424,7 +3515,9 @@ pub trait Itertools : Iterator { /// assert_eq!(a.iter().position_max_by(|x, y| x.cmp(y)), Some(1)); /// ``` fn position_max_by<F>(self, mut compare: F) -> Option<usize> - where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering + where + Self: Sized, + F: FnMut(&Self::Item, &Self::Item) -> Ordering, { self.enumerate() .max_by(|x, y| compare(&x.1, &y.1)) @@ -3451,7 +3544,9 @@ pub trait Itertools : Iterator { /// assert_eq!(a.iter().position_min(), Some(2)); /// ``` fn position_min(self) -> Option<usize> - where Self: Sized, Self::Item: Ord + where + Self: Sized, + Self::Item: Ord, { self.enumerate() .min_by(|x, y| Ord::cmp(&x.1, &y.1)) @@ -3479,7 +3574,10 @@ pub trait Itertools : Iterator { /// assert_eq!(a.iter().position_min_by_key(|x| x.abs()), Some(0)); /// ``` fn position_min_by_key<K, F>(self, mut key: F) -> Option<usize> - where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K + where + Self: Sized, + K: Ord, + F: FnMut(&Self::Item) -> K, { self.enumerate() .min_by(|x, y| Ord::cmp(&key(&x.1), &key(&y.1))) @@ -3507,7 +3605,9 @@ pub trait Itertools : Iterator { /// assert_eq!(a.iter().position_min_by(|x, y| x.cmp(y)), Some(2)); /// ``` fn position_min_by<F>(self, mut compare: F) -> Option<usize> - where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering + where + Self: Sized, + F: FnMut(&Self::Item, &Self::Item) -> Ordering, { self.enumerate() .min_by(|x, y| compare(&x.1, &y.1)) @@ -3557,9 +3657,11 @@ pub trait Itertools : Iterator { /// assert_eq!(a.iter().position_minmax(), MinMax(2, 1)); /// ``` fn position_minmax(self) -> MinMaxResult<usize> - where Self: Sized, Self::Item: PartialOrd + where + Self: Sized, + Self::Item: PartialOrd, { - use crate::MinMaxResult::{NoElements, OneElement, MinMax}; + use crate::MinMaxResult::{MinMax, NoElements, OneElement}; match minmax::minmax_impl(self.enumerate(), |_| (), |x, y, _, _| x.1 < y.1) { NoElements => NoElements, OneElement(x) => OneElement(x.0), @@ -3602,9 +3704,12 @@ pub trait Itertools : Iterator { /// /// [`position_minmax`]: Self::position_minmax fn position_minmax_by_key<K, F>(self, mut key: F) -> MinMaxResult<usize> - where Self: Sized, K: PartialOrd, F: FnMut(&Self::Item) -> K + where + Self: Sized, + K: PartialOrd, + F: FnMut(&Self::Item) -> K, { - use crate::MinMaxResult::{NoElements, OneElement, MinMax}; + use crate::MinMaxResult::{MinMax, NoElements, OneElement}; match self.enumerate().minmax_by_key(|e| key(&e.1)) { NoElements => NoElements, OneElement(x) => OneElement(x.0), @@ -3644,9 +3749,11 @@ pub trait Itertools : Iterator { /// /// [`position_minmax`]: Self::position_minmax fn position_minmax_by<F>(self, mut compare: F) -> MinMaxResult<usize> - where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering + where + Self: Sized, + F: FnMut(&Self::Item, &Self::Item) -> Ordering, { - use crate::MinMaxResult::{NoElements, OneElement, MinMax}; + use crate::MinMaxResult::{MinMax, NoElements, OneElement}; match self.enumerate().minmax_by(|x, y| compare(&x.1, &y.1)) { NoElements => NoElements, OneElement(x) => OneElement(x.0), @@ -3676,16 +3783,13 @@ pub trait Itertools : Iterator { Self: Sized, { match self.next() { - Some(first) => { - match self.next() { - Some(second) => { - Err(ExactlyOneError::new(Some(Either::Left([first, second])), self)) - } - None => { - Ok(first) - } - } - } + Some(first) => match self.next() { + Some(second) => Err(ExactlyOneError::new( + Some(Either::Left([first, second])), + self, + )), + None => Ok(first), + }, None => Err(ExactlyOneError::new(None, self)), } } @@ -3712,16 +3816,13 @@ pub trait Itertools : Iterator { Self: Sized, { match self.next() { - Some(first) => { - match self.next() { - Some(second) => { - Err(ExactlyOneError::new(Some(Either::Left([first, second])), self)) - } - None => { - Ok(Some(first)) - } - } - } + Some(first) => match self.next() { + Some(second) => Err(ExactlyOneError::new( + Some(Either::Left([first, second])), + self, + )), + None => Ok(Some(first)), + }, None => Ok(None), } } @@ -3840,9 +3941,33 @@ pub trait Itertools : Iterator { { MultiUnzip::multiunzip(self) } + + /// Returns the length of the iterator if one exists. + /// Otherwise return `self.size_hint()`. + /// + /// Fallible [`ExactSizeIterator::len`]. + /// + /// Inherits guarantees and restrictions from [`Iterator::size_hint`]. + /// + /// ``` + /// use itertools::Itertools; + /// + /// assert_eq!([0; 10].iter().try_len(), Ok(10)); + /// assert_eq!((10..15).try_len(), Ok(5)); + /// assert_eq!((15..10).try_len(), Ok(0)); + /// assert_eq!((10..).try_len(), Err((usize::MAX, None))); + /// assert_eq!((10..15).filter(|x| x % 2 == 0).try_len(), Err((0, Some(5)))); + /// ``` + fn try_len(&self) -> Result<usize, size_hint::SizeHint> { + let sh = self.size_hint(); + match sh { + (lo, Some(hi)) if lo == hi => Ok(lo), + _ => Err(sh), + } + } } -impl<T: ?Sized> Itertools for T where T: Iterator { } +impl<T: ?Sized> Itertools for T where T: Iterator {} /// Return `true` if both iterables produce equal sequences /// (elements pairwise equal and sequences of the same length), @@ -3855,9 +3980,10 @@ impl<T: ?Sized> Itertools for T where T: Iterator { } /// assert!(!itertools::equal(&[0, 0], &[0, 0, 0])); /// ``` pub fn equal<I, J>(a: I, b: J) -> bool - where I: IntoIterator, - J: IntoIterator, - I::Item: PartialEq<J::Item> +where + I: IntoIterator, + J: IntoIterator, + I::Item: PartialEq<J::Item>, { a.into_iter().eq(b) } @@ -3868,15 +3994,17 @@ pub fn equal<I, J>(a: I, b: J) -> bool /// **Panics** on assertion failure with a message that shows the /// two iteration elements. /// -/// ```ignore +/// ```should_panic +/// # use itertools::assert_equal; /// assert_equal("exceed".split('c'), "excess".split('c')); -/// // ^PANIC: panicked at 'Failed assertion Some("eed") == Some("ess") for iteration 1', +/// // ^PANIC: panicked at 'Failed assertion Some("eed") == Some("ess") for iteration 1'. /// ``` pub fn assert_equal<I, J>(a: I, b: J) - where I: IntoIterator, - J: IntoIterator, - I::Item: fmt::Debug + PartialEq<J::Item>, - J::Item: fmt::Debug, +where + I: IntoIterator, + J: IntoIterator, + I::Item: fmt::Debug + PartialEq<J::Item>, + J::Item: fmt::Debug, { let mut ia = a.into_iter(); let mut ib = b.into_iter(); @@ -3889,8 +4017,13 @@ pub fn assert_equal<I, J>(a: I, b: J) (&Some(ref a), &Some(ref b)) => a == b, _ => false, }; - assert!(equal, "Failed assertion {a:?} == {b:?} for iteration {i}", - i=i, a=a, b=b); + assert!( + equal, + "Failed assertion {a:?} == {b:?} for iteration {i}", + i = i, + a = a, + b = b + ); i += 1; } } @@ -3915,9 +4048,10 @@ pub fn assert_equal<I, J>(a: I, b: J) /// assert_eq!(split_index, 3); /// ``` pub fn partition<'a, A: 'a, I, F>(iter: I, mut pred: F) -> usize - where I: IntoIterator<Item = &'a mut A>, - I::IntoIter: DoubleEndedIterator, - F: FnMut(&A) -> bool +where + I: IntoIterator<Item = &'a mut A>, + I::IntoIter: DoubleEndedIterator, + F: FnMut(&A) -> bool, { let mut split_index = 0; let mut iter = iter.into_iter(); @@ -3925,10 +4059,12 @@ pub fn partition<'a, A: 'a, I, F>(iter: I, mut pred: F) -> usize if !pred(front) { loop { match iter.next_back() { - Some(back) => if pred(back) { - std::mem::swap(front, back); - break; - }, + Some(back) => { + if pred(back) { + std::mem::swap(front, back); + break; + } + } None => break 'main, } } diff --git a/vendor/itertools/src/merge_join.rs b/vendor/itertools/src/merge_join.rs index 84f7d0333..c83159186 100644 --- a/vendor/itertools/src/merge_join.rs +++ b/vendor/itertools/src/merge_join.rs @@ -1,40 +1,111 @@ use std::cmp::Ordering; -use std::iter::Fuse; use std::fmt; +use std::iter::{Fuse, FusedIterator}; +use std::marker::PhantomData; use either::Either; -use super::adaptors::{PutBack, put_back}; +use super::adaptors::{put_back, PutBack}; use crate::either_or_both::EitherOrBoth; use crate::size_hint::{self, SizeHint}; #[cfg(doc)] use crate::Itertools; +#[derive(Clone, Debug)] +pub struct MergeLte; + +/// An iterator adaptor that merges the two base iterators in ascending order. +/// If both base iterators are sorted (ascending), the result is sorted. +/// +/// Iterator element type is `I::Item`. +/// +/// See [`.merge()`](crate::Itertools::merge_by) for more information. +pub type Merge<I, J> = MergeBy<I, J, MergeLte>; + +/// Create an iterator that merges elements in `i` and `j`. +/// +/// [`IntoIterator`] enabled version of [`Itertools::merge`](crate::Itertools::merge). +/// +/// ``` +/// use itertools::merge; +/// +/// for elt in merge(&[1, 2, 3], &[2, 3, 4]) { +/// /* loop body */ +/// } +/// ``` +pub fn merge<I, J>( + i: I, + j: J, +) -> Merge<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter> +where + I: IntoIterator, + J: IntoIterator<Item = I::Item>, + I::Item: PartialOrd, +{ + merge_by_new(i, j, MergeLte) +} + +/// An iterator adaptor that merges the two base iterators in ascending order. +/// If both base iterators are sorted (ascending), the result is sorted. +/// +/// Iterator element type is `I::Item`. +/// +/// See [`.merge_by()`](crate::Itertools::merge_by) for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct MergeBy<I: Iterator, J: Iterator, F> { + left: PutBack<Fuse<I>>, + right: PutBack<Fuse<J>>, + cmp_fn: F, +} + +/// Create a `MergeBy` iterator. +pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I::IntoIter, J::IntoIter, F> +where + I: IntoIterator, + J: IntoIterator<Item = I::Item>, +{ + MergeBy { + left: put_back(a.into_iter().fuse()), + right: put_back(b.into_iter().fuse()), + cmp_fn: cmp, + } +} + /// Return an iterator adaptor that merge-joins items from the two base iterators in ascending order. /// /// [`IntoIterator`] enabled version of [`Itertools::merge_join_by`]. -pub fn merge_join_by<I, J, F, T>(left: I, right: J, cmp_fn: F) - -> MergeJoinBy<I::IntoIter, J::IntoIter, F> - where I: IntoIterator, - J: IntoIterator, - F: FnMut(&I::Item, &J::Item) -> T, - T: OrderingOrBool<I::Item, J::Item>, +pub fn merge_join_by<I, J, F, T>( + left: I, + right: J, + cmp_fn: F, +) -> MergeJoinBy<I::IntoIter, J::IntoIter, F> +where + I: IntoIterator, + J: IntoIterator, + F: FnMut(&I::Item, &J::Item) -> T, { - MergeJoinBy { + MergeBy { left: put_back(left.into_iter().fuse()), right: put_back(right.into_iter().fuse()), - cmp_fn, + cmp_fn: MergeFuncLR(cmp_fn, PhantomData), } } /// An iterator adaptor that merge-joins items from the two base iterators in ascending order. /// /// See [`.merge_join_by()`](crate::Itertools::merge_join_by) for more information. -#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] -pub struct MergeJoinBy<I: Iterator, J: Iterator, F> { - left: PutBack<Fuse<I>>, - right: PutBack<Fuse<J>>, - cmp_fn: F, +pub type MergeJoinBy<I, J, F> = + MergeBy<I, J, MergeFuncLR<F, <F as FuncLR<<I as Iterator>::Item, <J as Iterator>::Item>>::T>>; + +#[derive(Clone, Debug)] +pub struct MergeFuncLR<F, T>(F, PhantomData<T>); + +pub trait FuncLR<L, R> { + type T; +} + +impl<L, R, T, F: FnMut(&L, &R) -> T> FuncLR<L, R> for F { + type T = T; } pub trait OrderingOrBool<L, R> { @@ -44,11 +115,11 @@ pub trait OrderingOrBool<L, R> { // "merge" never returns (Some(...), Some(...), ...) so Option<Either<I::Item, J::Item>> // is appealing but it is always followed by two put_backs, so we think the compiler is // smart enough to optimize it. Or we could move put_backs into "merge". - fn merge(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult); + fn merge(&mut self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult); fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint; } -impl<L, R> OrderingOrBool<L, R> for Ordering { +impl<L, R, F: FnMut(&L, &R) -> Ordering> OrderingOrBool<L, R> for MergeFuncLR<F, Ordering> { type MergeResult = EitherOrBoth<L, R>; fn left(left: L) -> Self::MergeResult { EitherOrBoth::Left(left) @@ -56,8 +127,8 @@ impl<L, R> OrderingOrBool<L, R> for Ordering { fn right(right: R) -> Self::MergeResult { EitherOrBoth::Right(right) } - fn merge(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) { - match self { + fn merge(&mut self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) { + match self.0(&left, &right) { Ordering::Equal => (None, None, EitherOrBoth::Both(left, right)), Ordering::Less => (None, Some(right), EitherOrBoth::Left(left)), Ordering::Greater => (Some(left), None, EitherOrBoth::Right(right)), @@ -75,7 +146,7 @@ impl<L, R> OrderingOrBool<L, R> for Ordering { } } -impl<L, R> OrderingOrBool<L, R> for bool { +impl<L, R, F: FnMut(&L, &R) -> bool> OrderingOrBool<L, R> for MergeFuncLR<F, bool> { type MergeResult = Either<L, R>; fn left(left: L) -> Self::MergeResult { Either::Left(left) @@ -83,8 +154,8 @@ impl<L, R> OrderingOrBool<L, R> for bool { fn right(right: R) -> Self::MergeResult { Either::Right(right) } - fn merge(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) { - if self { + fn merge(&mut self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) { + if self.0(&left, &right) { (None, Some(right), Either::Left(left)) } else { (Some(left), None, Either::Right(right)) @@ -96,40 +167,84 @@ impl<L, R> OrderingOrBool<L, R> for bool { } } -impl<I, J, F> Clone for MergeJoinBy<I, J, F> - where I: Iterator, - J: Iterator, - PutBack<Fuse<I>>: Clone, - PutBack<Fuse<J>>: Clone, - F: Clone, +impl<T, F: FnMut(&T, &T) -> bool> OrderingOrBool<T, T> for F { + type MergeResult = T; + fn left(left: T) -> Self::MergeResult { + left + } + fn right(right: T) -> Self::MergeResult { + right + } + fn merge(&mut self, left: T, right: T) -> (Option<T>, Option<T>, Self::MergeResult) { + if self(&left, &right) { + (None, Some(right), left) + } else { + (Some(left), None, right) + } + } + fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint { + // Not ExactSizeIterator because size may be larger than usize + size_hint::add(left, right) + } +} + +impl<T: PartialOrd> OrderingOrBool<T, T> for MergeLte { + type MergeResult = T; + fn left(left: T) -> Self::MergeResult { + left + } + fn right(right: T) -> Self::MergeResult { + right + } + fn merge(&mut self, left: T, right: T) -> (Option<T>, Option<T>, Self::MergeResult) { + if left <= right { + (None, Some(right), left) + } else { + (Some(left), None, right) + } + } + fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint { + // Not ExactSizeIterator because size may be larger than usize + size_hint::add(left, right) + } +} + +impl<I, J, F> Clone for MergeBy<I, J, F> +where + I: Iterator, + J: Iterator, + PutBack<Fuse<I>>: Clone, + PutBack<Fuse<J>>: Clone, + F: Clone, { clone_fields!(left, right, cmp_fn); } -impl<I, J, F> fmt::Debug for MergeJoinBy<I, J, F> - where I: Iterator + fmt::Debug, - I::Item: fmt::Debug, - J: Iterator + fmt::Debug, - J::Item: fmt::Debug, +impl<I, J, F> fmt::Debug for MergeBy<I, J, F> +where + I: Iterator + fmt::Debug, + I::Item: fmt::Debug, + J: Iterator + fmt::Debug, + J::Item: fmt::Debug, { - debug_fmt_fields!(MergeJoinBy, left, right); + debug_fmt_fields!(MergeBy, left, right); } -impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F> - where I: Iterator, - J: Iterator, - F: FnMut(&I::Item, &J::Item) -> T, - T: OrderingOrBool<I::Item, J::Item>, +impl<I, J, F> Iterator for MergeBy<I, J, F> +where + I: Iterator, + J: Iterator, + F: OrderingOrBool<I::Item, J::Item>, { - type Item = T::MergeResult; + type Item = F::MergeResult; fn next(&mut self) -> Option<Self::Item> { match (self.left.next(), self.right.next()) { (None, None) => None, - (Some(left), None) => Some(T::left(left)), - (None, Some(right)) => Some(T::right(right)), + (Some(left), None) => Some(F::left(left)), + (None, Some(right)) => Some(F::right(right)), (Some(left), Some(right)) => { - let (left, right, next) = (self.cmp_fn)(&left, &right).merge(left, right); + let (left, right, next) = self.cmp_fn.merge(left, right); if let Some(left) = left { self.left.put_back(left); } @@ -142,7 +257,7 @@ impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F> } fn size_hint(&self) -> SizeHint { - T::size_hint(self.left.size_hint(), self.right.size_hint()) + F::size_hint(self.left.size_hint(), self.right.size_hint()) } fn count(mut self) -> usize { @@ -154,7 +269,7 @@ impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F> (None, Some(_right)) => break count + 1 + self.right.into_parts().1.count(), (Some(left), Some(right)) => { count += 1; - let (left, right, _) = (self.cmp_fn)(&left, &right).merge(left, right); + let (left, right, _) = self.cmp_fn.merge(left, right); if let Some(left) = left { self.left.put_back(left); } @@ -172,17 +287,13 @@ impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F> match (self.left.next(), self.right.next()) { (None, None) => break previous_element, (Some(left), None) => { - break Some(T::left( - self.left.into_parts().1.last().unwrap_or(left), - )) + break Some(F::left(self.left.into_parts().1.last().unwrap_or(left))) } (None, Some(right)) => { - break Some(T::right( - self.right.into_parts().1.last().unwrap_or(right), - )) + break Some(F::right(self.right.into_parts().1.last().unwrap_or(right))) } (Some(left), Some(right)) => { - let (left, right, elem) = (self.cmp_fn)(&left, &right).merge(left, right); + let (left, right, elem) = self.cmp_fn.merge(left, right); if let Some(left) = left { self.left.put_back(left); } @@ -203,10 +314,10 @@ impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F> n -= 1; match (self.left.next(), self.right.next()) { (None, None) => break None, - (Some(_left), None) => break self.left.nth(n).map(T::left), - (None, Some(_right)) => break self.right.nth(n).map(T::right), + (Some(_left), None) => break self.left.nth(n).map(F::left), + (None, Some(_right)) => break self.right.nth(n).map(F::right), (Some(left), Some(right)) => { - let (left, right, _) = (self.cmp_fn)(&left, &right).merge(left, right); + let (left, right, _) = self.cmp_fn.merge(left, right); if let Some(left) = left { self.left.put_back(left); } @@ -218,3 +329,11 @@ impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F> } } } + +impl<I, J, F> FusedIterator for MergeBy<I, J, F> +where + I: Iterator, + J: Iterator, + F: OrderingOrBool<I::Item, J::Item>, +{ +} diff --git a/vendor/itertools/src/minmax.rs b/vendor/itertools/src/minmax.rs index 52b2f115d..f04e5adba 100644 --- a/vendor/itertools/src/minmax.rs +++ b/vendor/itertools/src/minmax.rs @@ -1,4 +1,3 @@ - /// `MinMaxResult` is an enum returned by `minmax`. /// /// See [`.minmax()`](crate::Itertools::minmax) for more detail. @@ -12,7 +11,7 @@ pub enum MinMaxResult<T> { /// More than one element in the iterator, the first element is not larger /// than the second - MinMax(T, T) + MinMax(T, T), } impl<T: Clone> MinMaxResult<T> { @@ -36,34 +35,36 @@ impl<T: Clone> MinMaxResult<T> { /// let r = MinMax(1, 2); /// assert_eq!(r.into_option(), Some((1, 2))); /// ``` - pub fn into_option(self) -> Option<(T,T)> { + pub fn into_option(self) -> Option<(T, T)> { match self { MinMaxResult::NoElements => None, MinMaxResult::OneElement(x) => Some((x.clone(), x)), - MinMaxResult::MinMax(x, y) => Some((x, y)) + MinMaxResult::MinMax(x, y) => Some((x, y)), } } } /// Implementation guts for `minmax` and `minmax_by_key`. -pub fn minmax_impl<I, K, F, L>(mut it: I, mut key_for: F, - mut lt: L) -> MinMaxResult<I::Item> - where I: Iterator, - F: FnMut(&I::Item) -> K, - L: FnMut(&I::Item, &I::Item, &K, &K) -> bool, +pub fn minmax_impl<I, K, F, L>(mut it: I, mut key_for: F, mut lt: L) -> MinMaxResult<I::Item> +where + I: Iterator, + F: FnMut(&I::Item) -> K, + L: FnMut(&I::Item, &I::Item, &K, &K) -> bool, { let (mut min, mut max, mut min_key, mut max_key) = match it.next() { None => return MinMaxResult::NoElements, - Some(x) => { - match it.next() { - None => return MinMaxResult::OneElement(x), - Some(y) => { - let xk = key_for(&x); - let yk = key_for(&y); - if !lt(&y, &x, &yk, &xk) {(x, y, xk, yk)} else {(y, x, yk, xk)} + Some(x) => match it.next() { + None => return MinMaxResult::OneElement(x), + Some(y) => { + let xk = key_for(&x); + let yk = key_for(&y); + if !lt(&y, &x, &yk, &xk) { + (x, y, xk, yk) + } else { + (y, x, yk, xk) } } - } + }, }; loop { @@ -74,7 +75,7 @@ pub fn minmax_impl<I, K, F, L>(mut it: I, mut key_for: F, // for 2 elements. let first = match it.next() { None => break, - Some(x) => x + Some(x) => x, }; let second = match it.next() { None => { @@ -86,7 +87,7 @@ pub fn minmax_impl<I, K, F, L>(mut it: I, mut key_for: F, } break; } - Some(x) => x + Some(x) => x, }; let first_key = key_for(&first); let second_key = key_for(&second); diff --git a/vendor/itertools/src/multipeek_impl.rs b/vendor/itertools/src/multipeek_impl.rs index 8b49c695e..00c5d4ea7 100644 --- a/vendor/itertools/src/multipeek_impl.rs +++ b/vendor/itertools/src/multipeek_impl.rs @@ -1,14 +1,16 @@ -use std::iter::Fuse; -use alloc::collections::VecDeque; use crate::size_hint; -use crate::PeekingNext; #[cfg(doc)] use crate::Itertools; +use crate::PeekingNext; +use alloc::collections::VecDeque; +use std::iter::Fuse; /// See [`multipeek()`] for more information. #[derive(Clone, Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct MultiPeek<I> - where I: Iterator +where + I: Iterator, { iter: Fuse<I>, buf: VecDeque<I::Item>, @@ -20,7 +22,8 @@ pub struct MultiPeek<I> /// /// [`IntoIterator`] enabled version of [`Itertools::multipeek`]. pub fn multipeek<I>(iterable: I) -> MultiPeek<I::IntoIter> - where I: IntoIterator +where + I: IntoIterator, { MultiPeek { iter: iterable.into_iter().fuse(), @@ -30,7 +33,8 @@ pub fn multipeek<I>(iterable: I) -> MultiPeek<I::IntoIter> } impl<I> MultiPeek<I> - where I: Iterator +where + I: Iterator, { /// Reset the peeking “cursor” pub fn reset_peek(&mut self) { @@ -62,24 +66,31 @@ impl<I: Iterator> MultiPeek<I> { } impl<I> PeekingNext for MultiPeek<I> - where I: Iterator, +where + I: Iterator, { fn peeking_next<F>(&mut self, accept: F) -> Option<Self::Item> - where F: FnOnce(&Self::Item) -> bool + where + F: FnOnce(&Self::Item) -> bool, { if self.buf.is_empty() { if let Some(r) = self.peek() { - if !accept(r) { return None } + if !accept(r) { + return None; + } } } else if let Some(r) = self.buf.get(0) { - if !accept(r) { return None } + if !accept(r) { + return None; + } } self.next() } } impl<I> Iterator for MultiPeek<I> - where I: Iterator +where + I: Iterator, { type Item = I::Item; @@ -94,8 +105,4 @@ impl<I> Iterator for MultiPeek<I> } // Same size -impl<I> ExactSizeIterator for MultiPeek<I> - where I: ExactSizeIterator -{} - - +impl<I> ExactSizeIterator for MultiPeek<I> where I: ExactSizeIterator {} diff --git a/vendor/itertools/src/pad_tail.rs b/vendor/itertools/src/pad_tail.rs index 248a43243..47e62b2cf 100644 --- a/vendor/itertools/src/pad_tail.rs +++ b/vendor/itertools/src/pad_tail.rs @@ -1,5 +1,5 @@ -use std::iter::{Fuse, FusedIterator}; use crate::size_hint; +use std::iter::{Fuse, FusedIterator}; /// An iterator adaptor that pads a sequence to a minimum length by filling /// missing elements using a closure. @@ -25,8 +25,9 @@ where /// Create a new `PadUsing` iterator. pub fn pad_using<I, F>(iter: I, min: usize, filler: F) -> PadUsing<I, F> - where I: Iterator, - F: FnMut(usize) -> I::Item +where + I: Iterator, + F: FnMut(usize) -> I::Item, { PadUsing { iter: iter.fuse(), @@ -37,8 +38,9 @@ pub fn pad_using<I, F>(iter: I, min: usize, filler: F) -> PadUsing<I, F> } impl<I, F> Iterator for PadUsing<I, F> - where I: Iterator, - F: FnMut(usize) -> I::Item +where + I: Iterator, + F: FnMut(usize) -> I::Item, { type Item = I::Item; @@ -53,7 +55,7 @@ impl<I, F> Iterator for PadUsing<I, F> } else { None } - }, + } e => { self.pos += 1; e @@ -68,8 +70,9 @@ impl<I, F> Iterator for PadUsing<I, F> } impl<I, F> DoubleEndedIterator for PadUsing<I, F> - where I: DoubleEndedIterator + ExactSizeIterator, - F: FnMut(usize) -> I::Item +where + I: DoubleEndedIterator + ExactSizeIterator, + F: FnMut(usize) -> I::Item, { fn next_back(&mut self) -> Option<Self::Item> { if self.min == 0 { @@ -85,12 +88,15 @@ impl<I, F> DoubleEndedIterator for PadUsing<I, F> } impl<I, F> ExactSizeIterator for PadUsing<I, F> - where I: ExactSizeIterator, - F: FnMut(usize) -> I::Item -{} - +where + I: ExactSizeIterator, + F: FnMut(usize) -> I::Item, +{ +} impl<I, F> FusedIterator for PadUsing<I, F> - where I: FusedIterator, - F: FnMut(usize) -> I::Item -{} +where + I: FusedIterator, + F: FnMut(usize) -> I::Item, +{ +} diff --git a/vendor/itertools/src/peek_nth.rs b/vendor/itertools/src/peek_nth.rs index bcca45838..e8546030d 100644 --- a/vendor/itertools/src/peek_nth.rs +++ b/vendor/itertools/src/peek_nth.rs @@ -5,6 +5,7 @@ use std::iter::Fuse; /// See [`peek_nth()`] for more information. #[derive(Clone, Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct PeekNth<I> where I: Iterator, @@ -39,25 +40,30 @@ where self.peek_nth(0) } + /// Works exactly like the `peek_mut` method in `std::iter::Peekable` + pub fn peek_mut(&mut self) -> Option<&mut I::Item> { + self.peek_nth_mut(0) + } + /// Returns a reference to the `nth` value without advancing the iterator. /// /// # Examples /// /// Basic usage: /// - /// ```rust + /// ``` /// use itertools::peek_nth; /// - /// let xs = vec![1,2,3]; - /// let mut iter = peek_nth(xs.iter()); + /// let xs = vec![1, 2, 3]; + /// let mut iter = peek_nth(xs.into_iter()); /// - /// assert_eq!(iter.peek_nth(0), Some(&&1)); - /// assert_eq!(iter.next(), Some(&1)); + /// assert_eq!(iter.peek_nth(0), Some(&1)); + /// assert_eq!(iter.next(), Some(1)); /// /// // The iterator does not advance even if we call `peek_nth` multiple times - /// assert_eq!(iter.peek_nth(0), Some(&&2)); - /// assert_eq!(iter.peek_nth(1), Some(&&3)); - /// assert_eq!(iter.next(), Some(&2)); + /// assert_eq!(iter.peek_nth(0), Some(&2)); + /// assert_eq!(iter.peek_nth(1), Some(&3)); + /// assert_eq!(iter.next(), Some(2)); /// /// // Calling `peek_nth` past the end of the iterator will return `None` /// assert_eq!(iter.peek_nth(1), None); @@ -69,6 +75,68 @@ where self.buf.get(n) } + + /// Returns a mutable reference to the `nth` value without advancing the iterator. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use itertools::peek_nth; + /// + /// let xs = vec![1, 2, 3, 4, 5]; + /// let mut iter = peek_nth(xs.into_iter()); + /// + /// assert_eq!(iter.peek_nth_mut(0), Some(&mut 1)); + /// assert_eq!(iter.next(), Some(1)); + /// + /// // The iterator does not advance even if we call `peek_nth_mut` multiple times + /// assert_eq!(iter.peek_nth_mut(0), Some(&mut 2)); + /// assert_eq!(iter.peek_nth_mut(1), Some(&mut 3)); + /// assert_eq!(iter.next(), Some(2)); + /// + /// // Peek into the iterator and set the value behind the mutable reference. + /// if let Some(p) = iter.peek_nth_mut(1) { + /// assert_eq!(*p, 4); + /// *p = 9; + /// } + /// + /// // The value we put in reappears as the iterator continues. + /// assert_eq!(iter.next(), Some(3)); + /// assert_eq!(iter.next(), Some(9)); + /// + /// // Calling `peek_nth_mut` past the end of the iterator will return `None` + /// assert_eq!(iter.peek_nth_mut(1), None); + /// ``` + pub fn peek_nth_mut(&mut self, n: usize) -> Option<&mut I::Item> { + let unbuffered_items = (n + 1).saturating_sub(self.buf.len()); + + self.buf.extend(self.iter.by_ref().take(unbuffered_items)); + + self.buf.get_mut(n) + } + + /// Works exactly like the `next_if` method in `std::iter::Peekable` + pub fn next_if(&mut self, func: impl FnOnce(&I::Item) -> bool) -> Option<I::Item> { + match self.next() { + Some(item) if func(&item) => Some(item), + Some(item) => { + self.buf.push_front(item); + None + } + _ => None, + } + } + + /// Works exactly like the `next_if_eq` method in `std::iter::Peekable` + pub fn next_if_eq<T>(&mut self, expected: &T) -> Option<I::Item> + where + T: ?Sized, + I::Item: PartialEq<T>, + { + self.next_if(|next| next == expected) + } } impl<I> Iterator for PeekNth<I> diff --git a/vendor/itertools/src/peeking_take_while.rs b/vendor/itertools/src/peeking_take_while.rs index 3a3722812..b08794a8d 100644 --- a/vendor/itertools/src/peeking_take_while.rs +++ b/vendor/itertools/src/peeking_take_while.rs @@ -1,7 +1,7 @@ -use std::iter::Peekable; use crate::PutBack; #[cfg(feature = "use_alloc")] use crate::PutBackN; +use std::iter::Peekable; /// An iterator that allows peeking at an element before deciding to accept it. /// @@ -11,30 +11,35 @@ use crate::PutBackN; /// This is implemented by peeking adaptors like peekable and put back, /// but also by a few iterators that can be peeked natively, like the slice’s /// by reference iterator (`std::slice::Iter`). -pub trait PeekingNext : Iterator { +pub trait PeekingNext: Iterator { /// Pass a reference to the next iterator element to the closure `accept`; /// if `accept` returns true, return it as the next element, /// else None. fn peeking_next<F>(&mut self, accept: F) -> Option<Self::Item> - where Self: Sized, - F: FnOnce(&Self::Item) -> bool; + where + Self: Sized, + F: FnOnce(&Self::Item) -> bool; } impl<'a, I> PeekingNext for &'a mut I - where I: PeekingNext, +where + I: PeekingNext, { fn peeking_next<F>(&mut self, accept: F) -> Option<Self::Item> - where F: FnOnce(&Self::Item) -> bool + where + F: FnOnce(&Self::Item) -> bool, { (*self).peeking_next(accept) } } impl<I> PeekingNext for Peekable<I> - where I: Iterator, +where + I: Iterator, { fn peeking_next<F>(&mut self, accept: F) -> Option<Self::Item> - where F: FnOnce(&Self::Item) -> bool + where + F: FnOnce(&Self::Item) -> bool, { if let Some(r) = self.peek() { if !accept(r) { @@ -46,10 +51,12 @@ impl<I> PeekingNext for Peekable<I> } impl<I> PeekingNext for PutBack<I> - where I: Iterator, +where + I: Iterator, { fn peeking_next<F>(&mut self, accept: F) -> Option<Self::Item> - where F: FnOnce(&Self::Item) -> bool + where + F: FnOnce(&Self::Item) -> bool, { if let Some(r) = self.next() { if !accept(&r) { @@ -65,10 +72,12 @@ impl<I> PeekingNext for PutBack<I> #[cfg(feature = "use_alloc")] impl<I> PeekingNext for PutBackN<I> - where I: Iterator, +where + I: Iterator, { fn peeking_next<F>(&mut self, accept: F) -> Option<Self::Item> - where F: FnOnce(&Self::Item) -> bool + where + F: FnOnce(&Self::Item) -> bool, { if let Some(r) = self.next() { if !accept(&r) { @@ -88,7 +97,8 @@ impl<I> PeekingNext for PutBackN<I> /// for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct PeekingTakeWhile<'a, I: 'a, F> - where I: Iterator, +where + I: Iterator, { iter: &'a mut I, f: F, @@ -103,18 +113,16 @@ where /// Create a `PeekingTakeWhile` pub fn peeking_take_while<I, F>(iter: &mut I, f: F) -> PeekingTakeWhile<I, F> - where I: Iterator, +where + I: Iterator, { - PeekingTakeWhile { - iter, - f, - } + PeekingTakeWhile { iter, f } } impl<'a, I, F> Iterator for PeekingTakeWhile<'a, I, F> - where I: PeekingNext, - F: FnMut(&I::Item) -> bool, - +where + I: PeekingNext, + F: FnMut(&I::Item) -> bool, { type Item = I::Item; fn next(&mut self) -> Option<Self::Item> { @@ -127,11 +135,13 @@ impl<'a, I, F> Iterator for PeekingTakeWhile<'a, I, F> } impl<'a, I, F> PeekingNext for PeekingTakeWhile<'a, I, F> - where I: PeekingNext, - F: FnMut(&I::Item) -> bool, +where + I: PeekingNext, + F: FnMut(&I::Item) -> bool, { fn peeking_next<G>(&mut self, g: G) -> Option<Self::Item> - where G: FnOnce(&Self::Item) -> bool, + where + G: FnOnce(&Self::Item) -> bool, { let f = &mut self.f; self.iter.peeking_next(|r| f(r) && g(r)) @@ -174,4 +184,4 @@ peeking_next_by_clone! { ['a, T] alloc::collections::vec_deque::Iter<'a, T> } // cloning a Rev has no extra overhead; peekable and put backs are never DEI. peeking_next_by_clone! { [I: Clone + PeekingNext + DoubleEndedIterator] - ::std::iter::Rev<I> } +::std::iter::Rev<I> } diff --git a/vendor/itertools/src/permutations.rs b/vendor/itertools/src/permutations.rs index d03b85262..534ca59c9 100644 --- a/vendor/itertools/src/permutations.rs +++ b/vendor/itertools/src/permutations.rs @@ -1,8 +1,10 @@ use alloc::vec::Vec; use std::fmt; use std::iter::once; +use std::iter::FusedIterator; use super::lazy_buffer::LazyBuffer; +use crate::size_hint::{self, SizeHint}; /// An iterator adaptor that iterates through all the `k`-permutations of the /// elements from an iterator. @@ -16,262 +18,168 @@ pub struct Permutations<I: Iterator> { } impl<I> Clone for Permutations<I> - where I: Clone + Iterator, - I::Item: Clone, +where + I: Clone + Iterator, + I::Item: Clone, { clone_fields!(vals, state); } #[derive(Clone, Debug)] enum PermutationState { - StartUnknownLen { - k: usize, - }, - OngoingUnknownLen { - k: usize, - min_n: usize, - }, - Complete(CompleteState), - Empty, -} - -#[derive(Clone, Debug)] -enum CompleteState { - Start { - n: usize, - k: usize, - }, - Ongoing { + /// No permutation generated yet. + Start { k: usize }, + /// Values from the iterator are not fully loaded yet so `n` is still unknown. + Buffered { k: usize, min_n: usize }, + /// All values from the iterator are known so `n` is known. + Loaded { indices: Vec<usize>, cycles: Vec<usize>, - } -} - -enum CompleteStateRemaining { - Known(usize), - Overflow, + }, + /// No permutation left to generate. + End, } impl<I> fmt::Debug for Permutations<I> - where I: Iterator + fmt::Debug, - I::Item: fmt::Debug, +where + I: Iterator + fmt::Debug, + I::Item: fmt::Debug, { debug_fmt_fields!(Permutations, vals, state); } pub fn permutations<I: Iterator>(iter: I, k: usize) -> Permutations<I> { - let mut vals = LazyBuffer::new(iter); - - if k == 0 { - // Special case, yields single empty vec; `n` is irrelevant - let state = PermutationState::Complete(CompleteState::Start { n: 0, k: 0 }); - - return Permutations { - vals, - state - }; - } - - let mut enough_vals = true; - - while vals.len() < k { - if !vals.get_next() { - enough_vals = false; - break; - } - } - - let state = if enough_vals { - PermutationState::StartUnknownLen { k } - } else { - PermutationState::Empty - }; - Permutations { - vals, - state + vals: LazyBuffer::new(iter), + state: PermutationState::Start { k }, } } impl<I> Iterator for Permutations<I> where I: Iterator, - I::Item: Clone + I::Item: Clone, { type Item = Vec<I::Item>; fn next(&mut self) -> Option<Self::Item> { - self.advance(); - - let &mut Permutations { ref vals, ref state } = self; - - match *state { - PermutationState::StartUnknownLen { .. } => panic!("unexpected iterator state"), - PermutationState::OngoingUnknownLen { k, min_n } => { - let latest_idx = min_n - 1; - let indices = (0..(k - 1)).chain(once(latest_idx)); - - Some(indices.map(|i| vals[i].clone()).collect()) + let Self { vals, state } = self; + match state { + PermutationState::Start { k: 0 } => { + *state = PermutationState::End; + Some(Vec::new()) + } + &mut PermutationState::Start { k } => { + vals.prefill(k); + if vals.len() != k { + *state = PermutationState::End; + return None; + } + *state = PermutationState::Buffered { k, min_n: k }; + Some(vals[0..k].to_vec()) + } + PermutationState::Buffered { ref k, min_n } => { + if vals.get_next() { + let item = (0..*k - 1) + .chain(once(*min_n)) + .map(|i| vals[i].clone()) + .collect(); + *min_n += 1; + Some(item) + } else { + let n = *min_n; + let prev_iteration_count = n - *k + 1; + let mut indices: Vec<_> = (0..n).collect(); + let mut cycles: Vec<_> = (n - k..n).rev().collect(); + // Advance the state to the correct point. + for _ in 0..prev_iteration_count { + if advance(&mut indices, &mut cycles) { + *state = PermutationState::End; + return None; + } + } + let item = indices[0..*k].iter().map(|&i| vals[i].clone()).collect(); + *state = PermutationState::Loaded { indices, cycles }; + Some(item) + } } - PermutationState::Complete(CompleteState::Ongoing { ref indices, ref cycles }) => { + PermutationState::Loaded { indices, cycles } => { + if advance(indices, cycles) { + *state = PermutationState::End; + return None; + } let k = cycles.len(); Some(indices[0..k].iter().map(|&i| vals[i].clone()).collect()) - }, - PermutationState::Complete(CompleteState::Start { .. }) | PermutationState::Empty => None + } + PermutationState::End => None, } } fn count(self) -> usize { - fn from_complete(complete_state: CompleteState) -> usize { - match complete_state.remaining() { - CompleteStateRemaining::Known(count) => count, - CompleteStateRemaining::Overflow => { - panic!("Iterator count greater than usize::MAX"); - } - } - } - - let Permutations { vals, state } = self; - match state { - PermutationState::StartUnknownLen { k } => { - let n = vals.len() + vals.it.count(); - let complete_state = CompleteState::Start { n, k }; - - from_complete(complete_state) - } - PermutationState::OngoingUnknownLen { k, min_n } => { - let prev_iteration_count = min_n - k + 1; - let n = vals.len() + vals.it.count(); - let complete_state = CompleteState::Start { n, k }; - - from_complete(complete_state) - prev_iteration_count - }, - PermutationState::Complete(state) => from_complete(state), - PermutationState::Empty => 0 - } + let Self { vals, state } = self; + let n = vals.count(); + state.size_hint_for(n).1.unwrap() } - fn size_hint(&self) -> (usize, Option<usize>) { - match self.state { - PermutationState::StartUnknownLen { .. } | - PermutationState::OngoingUnknownLen { .. } => (0, None), // TODO can we improve this lower bound? - PermutationState::Complete(ref state) => match state.remaining() { - CompleteStateRemaining::Known(count) => (count, Some(count)), - CompleteStateRemaining::Overflow => (::std::usize::MAX, None) - } - PermutationState::Empty => (0, Some(0)) - } + fn size_hint(&self) -> SizeHint { + let (mut low, mut upp) = self.vals.size_hint(); + low = self.state.size_hint_for(low).0; + upp = upp.and_then(|n| self.state.size_hint_for(n).1); + (low, upp) } } -impl<I> Permutations<I> +impl<I> FusedIterator for Permutations<I> where I: Iterator, - I::Item: Clone + I::Item: Clone, { - fn advance(&mut self) { - let &mut Permutations { ref mut vals, ref mut state } = self; - - *state = match *state { - PermutationState::StartUnknownLen { k } => { - PermutationState::OngoingUnknownLen { k, min_n: k } - } - PermutationState::OngoingUnknownLen { k, min_n } => { - if vals.get_next() { - PermutationState::OngoingUnknownLen { k, min_n: min_n + 1 } - } else { - let n = min_n; - let prev_iteration_count = n - k + 1; - let mut complete_state = CompleteState::Start { n, k }; - - // Advance the complete-state iterator to the correct point - for _ in 0..(prev_iteration_count + 1) { - complete_state.advance(); - } - - PermutationState::Complete(complete_state) - } - } - PermutationState::Complete(ref mut state) => { - state.advance(); - - return; - } - PermutationState::Empty => { return; } - }; - } } -impl CompleteState { - fn advance(&mut self) { - *self = match *self { - CompleteState::Start { n, k } => { - let indices = (0..n).collect(); - let cycles = ((n - k)..n).rev().collect(); - - CompleteState::Ongoing { - cycles, - indices - } - }, - CompleteState::Ongoing { ref mut indices, ref mut cycles } => { - let n = indices.len(); - let k = cycles.len(); - - for i in (0..k).rev() { - if cycles[i] == 0 { - cycles[i] = n - i - 1; - - let to_push = indices.remove(i); - indices.push(to_push); - } else { - let swap_index = n - cycles[i]; - indices.swap(i, swap_index); - - cycles[i] -= 1; - return; - } - } - - CompleteState::Start { n, k } - } +fn advance(indices: &mut [usize], cycles: &mut [usize]) -> bool { + let n = indices.len(); + let k = cycles.len(); + // NOTE: if `cycles` are only zeros, then we reached the last permutation. + for i in (0..k).rev() { + if cycles[i] == 0 { + cycles[i] = n - i - 1; + indices[i..].rotate_left(1); + } else { + let swap_index = n - cycles[i]; + indices.swap(i, swap_index); + cycles[i] -= 1; + return false; } } + true +} - fn remaining(&self) -> CompleteStateRemaining { - use self::CompleteStateRemaining::{Known, Overflow}; - +impl PermutationState { + fn size_hint_for(&self, n: usize) -> SizeHint { + // At the beginning, there are `n!/(n-k)!` items to come. + let at_start = |n, k| { + debug_assert!(n >= k); + let total = (n - k + 1..=n).try_fold(1usize, |acc, i| acc.checked_mul(i)); + (total.unwrap_or(usize::MAX), total) + }; match *self { - CompleteState::Start { n, k } => { - if n < k { - return Known(0); - } - - let count: Option<usize> = (n - k + 1..n + 1).fold(Some(1), |acc, i| { - acc.and_then(|acc| acc.checked_mul(i)) - }); - - match count { - Some(count) => Known(count), - None => Overflow - } + Self::Start { k } if n < k => (0, Some(0)), + Self::Start { k } => at_start(n, k), + Self::Buffered { k, min_n } => { + // Same as `Start` minus the previously generated items. + size_hint::sub_scalar(at_start(n, k), min_n - k + 1) } - CompleteState::Ongoing { ref indices, ref cycles } => { - let mut count: usize = 0; - - for (i, &c) in cycles.iter().enumerate() { - let radix = indices.len() - i; - let next_count = count.checked_mul(radix) - .and_then(|count| count.checked_add(c)); - - count = match next_count { - Some(count) => count, - None => { return Overflow; } - }; - } - - Known(count) + Self::Loaded { + ref indices, + ref cycles, + } => { + let count = cycles.iter().enumerate().try_fold(0usize, |acc, (i, &c)| { + acc.checked_mul(indices.len() - i) + .and_then(|count| count.checked_add(c)) + }); + (count.unwrap_or(usize::MAX), count) } + Self::End => (0, Some(0)), } } } diff --git a/vendor/itertools/src/powerset.rs b/vendor/itertools/src/powerset.rs index 4d7685b12..9a7131a3e 100644 --- a/vendor/itertools/src/powerset.rs +++ b/vendor/itertools/src/powerset.rs @@ -1,10 +1,11 @@ +use alloc::vec::Vec; use std::fmt; use std::iter::FusedIterator; use std::usize; -use alloc::vec::Vec; -use super::combinations::{Combinations, combinations}; -use super::size_hint; +use super::combinations::{combinations, Combinations}; +use crate::adaptors::checked_binomial; +use crate::size_hint::{self, SizeHint}; /// An iterator to iterate through the powerset of the elements from an iterator. /// @@ -13,78 +14,94 @@ use super::size_hint; #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Powerset<I: Iterator> { combs: Combinations<I>, - // Iterator `position` (equal to count of yielded elements). - pos: usize, } impl<I> Clone for Powerset<I> - where I: Clone + Iterator, - I::Item: Clone, +where + I: Clone + Iterator, + I::Item: Clone, { - clone_fields!(combs, pos); + clone_fields!(combs); } impl<I> fmt::Debug for Powerset<I> - where I: Iterator + fmt::Debug, - I::Item: fmt::Debug, +where + I: Iterator + fmt::Debug, + I::Item: fmt::Debug, { - debug_fmt_fields!(Powerset, combs, pos); + debug_fmt_fields!(Powerset, combs); } /// Create a new `Powerset` from a clonable iterator. pub fn powerset<I>(src: I) -> Powerset<I> - where I: Iterator, - I::Item: Clone, +where + I: Iterator, + I::Item: Clone, { Powerset { combs: combinations(src, 0), - pos: 0, } } impl<I> Iterator for Powerset<I> - where - I: Iterator, - I::Item: Clone, +where + I: Iterator, + I::Item: Clone, { type Item = Vec<I::Item>; fn next(&mut self) -> Option<Self::Item> { if let Some(elt) = self.combs.next() { - self.pos = self.pos.saturating_add(1); Some(elt) - } else if self.combs.k() < self.combs.n() - || self.combs.k() == 0 - { + } else if self.combs.k() < self.combs.n() || self.combs.k() == 0 { self.combs.reset(self.combs.k() + 1); - self.combs.next().map(|elt| { - self.pos = self.pos.saturating_add(1); - elt - }) + self.combs.next() } else { None } } - fn size_hint(&self) -> (usize, Option<usize>) { + fn size_hint(&self) -> SizeHint { + let k = self.combs.k(); // Total bounds for source iterator. - let src_total = size_hint::add_scalar(self.combs.src().size_hint(), self.combs.n()); + let (n_min, n_max) = self.combs.src().size_hint(); + let low = remaining_for(n_min, k).unwrap_or(usize::MAX); + let upp = n_max.and_then(|n| remaining_for(n, k)); + size_hint::add(self.combs.size_hint(), (low, upp)) + } - // Total bounds for self ( length(powerset(set) == 2 ^ length(set) ) - let self_total = size_hint::pow_scalar_base(2, src_total); + fn count(self) -> usize { + let k = self.combs.k(); + let (n, combs_count) = self.combs.n_and_count(); + combs_count + remaining_for(n, k).unwrap() + } - if self.pos < usize::MAX { - // Subtract count of elements already yielded from total. - size_hint::sub_scalar(self_total, self.pos) - } else { - // Fallback: self.pos is saturated and no longer reliable. - (0, self_total.1) + fn fold<B, F>(self, mut init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + let mut it = self.combs; + if it.k() == 0 { + init = it.by_ref().fold(init, &mut f); + it.reset(1); } + init = it.by_ref().fold(init, &mut f); + // n is now known for sure because k >= 1 and all k-combinations have been generated. + for k in it.k() + 1..=it.n() { + it.reset(k); + init = it.by_ref().fold(init, &mut f); + } + init } } impl<I> FusedIterator for Powerset<I> - where - I: Iterator, - I::Item: Clone, -{} +where + I: Iterator, + I::Item: Clone, +{ +} + +fn remaining_for(n: usize, k: usize) -> Option<usize> { + (k + 1..=n).try_fold(0usize, |sum, i| sum.checked_add(checked_binomial(n, i)?)) +} diff --git a/vendor/itertools/src/process_results_impl.rs b/vendor/itertools/src/process_results_impl.rs index 713db4551..7b40cc015 100644 --- a/vendor/itertools/src/process_results_impl.rs +++ b/vendor/itertools/src/process_results_impl.rs @@ -14,7 +14,8 @@ pub struct ProcessResults<'a, I, E: 'a> { } impl<'a, I, T, E> Iterator for ProcessResults<'a, I, E> - where I: Iterator<Item = Result<T, E>> +where + I: Iterator<Item = Result<T, E>>, { type Item = T; @@ -56,13 +57,17 @@ impl<'a, I, T, E> Iterator for ProcessResults<'a, I, E> /// /// [`IntoIterator`] enabled version of [`Itertools::process_results`]. pub fn process_results<I, F, T, E, R>(iterable: I, processor: F) -> Result<R, E> - where I: IntoIterator<Item = Result<T, E>>, - F: FnOnce(ProcessResults<I::IntoIter, E>) -> R +where + I: IntoIterator<Item = Result<T, E>>, + F: FnOnce(ProcessResults<I::IntoIter, E>) -> R, { let iter = iterable.into_iter(); let mut error = Ok(()); - let result = processor(ProcessResults { error: &mut error, iter }); + let result = processor(ProcessResults { + error: &mut error, + iter, + }); error.map(|_| result) } diff --git a/vendor/itertools/src/put_back_n_impl.rs b/vendor/itertools/src/put_back_n_impl.rs index 60ea8e649..9b23fa7d5 100644 --- a/vendor/itertools/src/put_back_n_impl.rs +++ b/vendor/itertools/src/put_back_n_impl.rs @@ -7,6 +7,7 @@ use crate::size_hint; /// /// Iterator element type is `I::Item`. #[derive(Debug, Clone)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct PutBackN<I: Iterator> { top: Vec<I::Item>, iter: I, @@ -17,7 +18,8 @@ pub struct PutBackN<I: Iterator> { /// /// Iterator element type is `I::Item`. pub fn put_back_n<I>(iterable: I) -> PutBackN<I::IntoIter> - where I: IntoIterator +where + I: IntoIterator, { PutBackN { top: Vec::new(), @@ -58,4 +60,3 @@ impl<I: Iterator> Iterator for PutBackN<I> { size_hint::add_scalar(self.iter.size_hint(), self.top.len()) } } - diff --git a/vendor/itertools/src/rciter_impl.rs b/vendor/itertools/src/rciter_impl.rs index 7298350a8..e3b753206 100644 --- a/vendor/itertools/src/rciter_impl.rs +++ b/vendor/itertools/src/rciter_impl.rs @@ -1,10 +1,10 @@ - -use std::iter::{FusedIterator, IntoIterator}; use alloc::rc::Rc; use std::cell::RefCell; +use std::iter::{FusedIterator, IntoIterator}; /// A wrapper for `Rc<RefCell<I>>`, that implements the `Iterator` trait. #[derive(Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct RcIter<I> { /// The boxed iterator. pub rciter: Rc<RefCell<I>>, @@ -45,9 +45,12 @@ pub struct RcIter<I> { /// `.next()`, i.e. if it somehow participates in an “iterator knot” /// where it is an adaptor of itself. pub fn rciter<I>(iterable: I) -> RcIter<I::IntoIter> - where I: IntoIterator +where + I: IntoIterator, { - RcIter { rciter: Rc::new(RefCell::new(iterable.into_iter())) } + RcIter { + rciter: Rc::new(RefCell::new(iterable.into_iter())), + } } impl<I> Clone for RcIter<I> { @@ -55,7 +58,8 @@ impl<I> Clone for RcIter<I> { } impl<A, I> Iterator for RcIter<I> - where I: Iterator<Item = A> +where + I: Iterator<Item = A>, { type Item = A; #[inline] @@ -73,7 +77,8 @@ impl<A, I> Iterator for RcIter<I> } impl<I> DoubleEndedIterator for RcIter<I> - where I: DoubleEndedIterator +where + I: DoubleEndedIterator, { #[inline] fn next_back(&mut self) -> Option<Self::Item> { @@ -83,7 +88,8 @@ impl<I> DoubleEndedIterator for RcIter<I> /// Return an iterator from `&RcIter<I>` (by simply cloning it). impl<'a, I> IntoIterator for &'a RcIter<I> - where I: Iterator +where + I: Iterator, { type Item = I::Item; type IntoIter = RcIter<I>; @@ -93,7 +99,4 @@ impl<'a, I> IntoIterator for &'a RcIter<I> } } - -impl<A, I> FusedIterator for RcIter<I> - where I: FusedIterator<Item = A> -{} +impl<A, I> FusedIterator for RcIter<I> where I: FusedIterator<Item = A> {} diff --git a/vendor/itertools/src/repeatn.rs b/vendor/itertools/src/repeatn.rs index e025f6f6a..512d057f3 100644 --- a/vendor/itertools/src/repeatn.rs +++ b/vendor/itertools/src/repeatn.rs @@ -12,17 +12,22 @@ pub struct RepeatN<A> { /// Create an iterator that produces `n` repetitions of `element`. pub fn repeat_n<A>(element: A, n: usize) -> RepeatN<A> - where A: Clone, +where + A: Clone, { if n == 0 { - RepeatN { elt: None, n, } + RepeatN { elt: None, n } } else { - RepeatN { elt: Some(element), n, } + RepeatN { + elt: Some(element), + n, + } } } impl<A> Iterator for RepeatN<A> - where A: Clone +where + A: Clone, { type Item = A; @@ -42,7 +47,8 @@ impl<A> Iterator for RepeatN<A> } impl<A> DoubleEndedIterator for RepeatN<A> - where A: Clone +where + A: Clone, { #[inline] fn next_back(&mut self) -> Option<Self::Item> { @@ -50,10 +56,6 @@ impl<A> DoubleEndedIterator for RepeatN<A> } } -impl<A> ExactSizeIterator for RepeatN<A> - where A: Clone -{} +impl<A> ExactSizeIterator for RepeatN<A> where A: Clone {} -impl<A> FusedIterator for RepeatN<A> - where A: Clone -{} +impl<A> FusedIterator for RepeatN<A> where A: Clone {} diff --git a/vendor/itertools/src/size_hint.rs b/vendor/itertools/src/size_hint.rs index 71ea1412b..857e0c4c6 100644 --- a/vendor/itertools/src/size_hint.rs +++ b/vendor/itertools/src/size_hint.rs @@ -1,9 +1,8 @@ //! Arithmetic on `Iterator.size_hint()` values. //! -use std::usize; use std::cmp; -use std::u32; +use std::usize; /// `SizeHint` is the return type of `Iterator::size_hint()`. pub type SizeHint = (usize, Option<usize>); @@ -31,7 +30,6 @@ pub fn add_scalar(sh: SizeHint, x: usize) -> SizeHint { /// Subtract `x` correctly from a `SizeHint`. #[inline] -#[allow(dead_code)] pub fn sub_scalar(sh: SizeHint, x: usize) -> SizeHint { let (mut low, mut hi) = sh; low = low.saturating_sub(x); @@ -39,22 +37,7 @@ pub fn sub_scalar(sh: SizeHint, x: usize) -> SizeHint { (low, hi) } - /// Multiply `SizeHint` correctly -/// -/// ```ignore -/// use std::usize; -/// use itertools::size_hint; -/// -/// assert_eq!(size_hint::mul((3, Some(4)), (3, Some(4))), -/// (9, Some(16))); -/// -/// assert_eq!(size_hint::mul((3, Some(4)), (usize::MAX, None)), -/// (usize::MAX, None)); -/// -/// assert_eq!(size_hint::mul((3, None), (0, Some(0))), -/// (0, Some(0))); -/// ``` #[inline] pub fn mul(a: SizeHint, b: SizeHint) -> SizeHint { let low = a.0.saturating_mul(b.0); @@ -75,20 +58,6 @@ pub fn mul_scalar(sh: SizeHint, x: usize) -> SizeHint { (low, hi) } -/// Raise `base` correctly by a `SizeHint` exponent. -#[inline] -pub fn pow_scalar_base(base: usize, exp: SizeHint) -> SizeHint { - let exp_low = cmp::min(exp.0, u32::MAX as usize) as u32; - let low = base.saturating_pow(exp_low); - - let hi = exp.1.and_then(|exp| { - let exp_hi = cmp::min(exp, u32::MAX as usize) as u32; - base.checked_pow(exp_hi) - }); - - (low, hi) -} - /// Return the maximum #[inline] pub fn max(a: SizeHint, b: SizeHint) -> SizeHint { @@ -117,3 +86,10 @@ pub fn min(a: SizeHint, b: SizeHint) -> SizeHint { }; (lower, upper) } + +#[test] +fn mul_size_hints() { + assert_eq!(mul((3, Some(4)), (3, Some(4))), (9, Some(16))); + assert_eq!(mul((3, Some(4)), (usize::MAX, None)), (usize::MAX, None)); + assert_eq!(mul((3, None), (0, Some(0))), (0, Some(0))); +} diff --git a/vendor/itertools/src/sources.rs b/vendor/itertools/src/sources.rs index 3877ce3c8..bd520c21d 100644 --- a/vendor/itertools/src/sources.rs +++ b/vendor/itertools/src/sources.rs @@ -7,14 +7,13 @@ use std::mem; /// See [`repeat_call`](crate::repeat_call) for more information. #[derive(Clone)] -#[deprecated(note="Use std repeat_with() instead", since="0.8.0")] +#[deprecated(note = "Use std repeat_with() instead", since = "0.8.0")] pub struct RepeatCall<F> { f: F, } -impl<F> fmt::Debug for RepeatCall<F> -{ - debug_fmt_fields!(RepeatCall, ); +impl<F> fmt::Debug for RepeatCall<F> { + debug_fmt_fields!(RepeatCall,); } /// An iterator source that produces elements indefinitely by calling @@ -39,15 +38,17 @@ impl<F> fmt::Debug for RepeatCall<F> /// vec![1, 1, 1, 1, 1] /// ); /// ``` -#[deprecated(note="Use std repeat_with() instead", since="0.8.0")] +#[deprecated(note = "Use std repeat_with() instead", since = "0.8.0")] pub fn repeat_call<F, A>(function: F) -> RepeatCall<F> - where F: FnMut() -> A +where + F: FnMut() -> A, { RepeatCall { f: function } } impl<A, F> Iterator for RepeatCall<F> - where F: FnMut() -> A +where + F: FnMut() -> A, { type Item = A; @@ -98,7 +99,8 @@ impl<A, F> Iterator for RepeatCall<F> /// assert_eq!(fibonacci.last(), Some(2_971_215_073)) /// ``` pub fn unfold<A, St, F>(initial_state: St, f: F) -> Unfold<St, F> - where F: FnMut(&mut St) -> Option<A> +where + F: FnMut(&mut St) -> Option<A>, { Unfold { f, @@ -107,7 +109,8 @@ pub fn unfold<A, St, F>(initial_state: St, f: F) -> Unfold<St, F> } impl<St, F> fmt::Debug for Unfold<St, F> - where St: fmt::Debug, +where + St: fmt::Debug, { debug_fmt_fields!(Unfold, state); } @@ -122,7 +125,8 @@ pub struct Unfold<St, F> { } impl<A, St, F> Iterator for Unfold<St, F> - where F: FnMut(&mut St) -> Option<A> +where + F: FnMut(&mut St) -> Option<A>, { type Item = A; @@ -144,13 +148,15 @@ pub struct Iterate<St, F> { } impl<St, F> fmt::Debug for Iterate<St, F> - where St: fmt::Debug, +where + St: fmt::Debug, { debug_fmt_fields!(Iterate, state); } impl<St, F> Iterator for Iterate<St, F> - where F: FnMut(&St) -> St +where + F: FnMut(&St) -> St, { type Item = St; @@ -174,7 +180,8 @@ impl<St, F> Iterator for Iterate<St, F> /// itertools::assert_equal(iterate(1, |&i| i * 3).take(5), vec![1, 3, 9, 27, 81]); /// ``` pub fn iterate<St, F>(initial_value: St, f: F) -> Iterate<St, F> - where F: FnMut(&St) -> St +where + F: FnMut(&St) -> St, { Iterate { state: initial_value, diff --git a/vendor/itertools/src/take_while_inclusive.rs b/vendor/itertools/src/take_while_inclusive.rs index e2a7479e0..5207d8a01 100644 --- a/vendor/itertools/src/take_while_inclusive.rs +++ b/vendor/itertools/src/take_while_inclusive.rs @@ -8,33 +8,39 @@ use std::fmt; /// See [`.take_while_inclusive()`](crate::Itertools::take_while_inclusive) /// for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] -pub struct TakeWhileInclusive<'a, I: 'a, F> { - iter: &'a mut I, +#[derive(Clone)] +pub struct TakeWhileInclusive<I, F> { + iter: I, predicate: F, done: bool, } -impl<'a, I, F> TakeWhileInclusive<'a, I, F> +impl<I, F> TakeWhileInclusive<I, F> where I: Iterator, F: FnMut(&I::Item) -> bool, { /// Create a new [`TakeWhileInclusive`] from an iterator and a predicate. - pub fn new(iter: &'a mut I, predicate: F) -> Self { - Self { iter, predicate, done: false} + pub fn new(iter: I, predicate: F) -> Self { + Self { + iter, + predicate, + done: false, + } } } -impl<'a, I, F> fmt::Debug for TakeWhileInclusive<'a, I, F> - where I: Iterator + fmt::Debug, +impl<I, F> fmt::Debug for TakeWhileInclusive<I, F> +where + I: Iterator + fmt::Debug, { debug_fmt_fields!(TakeWhileInclusive, iter); } -impl<'a, I, F> Iterator for TakeWhileInclusive<'a, I, F> +impl<I, F> Iterator for TakeWhileInclusive<I, F> where I: Iterator, - F: FnMut(&I::Item) -> bool + F: FnMut(&I::Item) -> bool, { type Item = I::Item; @@ -60,9 +66,9 @@ where } } -impl<I, F> FusedIterator for TakeWhileInclusive<'_, I, F> +impl<I, F> FusedIterator for TakeWhileInclusive<I, F> where I: Iterator, - F: FnMut(&I::Item) -> bool + F: FnMut(&I::Item) -> bool, { -}
\ No newline at end of file +} diff --git a/vendor/itertools/src/tee.rs b/vendor/itertools/src/tee.rs index ea4752906..0984c5de9 100644 --- a/vendor/itertools/src/tee.rs +++ b/vendor/itertools/src/tee.rs @@ -1,8 +1,8 @@ use super::size_hint; -use std::cell::RefCell; use alloc::collections::VecDeque; use alloc::rc::Rc; +use std::cell::RefCell; /// Common buffer object for the two tee halves #[derive(Debug)] @@ -19,24 +19,37 @@ struct TeeBuffer<A, I> { #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] #[derive(Debug)] pub struct Tee<I> - where I: Iterator +where + I: Iterator, { rcbuffer: Rc<RefCell<TeeBuffer<I::Item, I>>>, id: bool, } pub fn new<I>(iter: I) -> (Tee<I>, Tee<I>) - where I: Iterator +where + I: Iterator, { - let buffer = TeeBuffer{backlog: VecDeque::new(), iter, owner: false}; - let t1 = Tee{rcbuffer: Rc::new(RefCell::new(buffer)), id: true}; - let t2 = Tee{rcbuffer: t1.rcbuffer.clone(), id: false}; + let buffer = TeeBuffer { + backlog: VecDeque::new(), + iter, + owner: false, + }; + let t1 = Tee { + rcbuffer: Rc::new(RefCell::new(buffer)), + id: true, + }; + let t2 = Tee { + rcbuffer: t1.rcbuffer.clone(), + id: false, + }; (t1, t2) } impl<I> Iterator for Tee<I> - where I: Iterator, - I::Item: Clone +where + I: Iterator, + I::Item: Clone, { type Item = I::Item; fn next(&mut self) -> Option<Self::Item> { @@ -73,6 +86,8 @@ impl<I> Iterator for Tee<I> } impl<I> ExactSizeIterator for Tee<I> - where I: ExactSizeIterator, - I::Item: Clone -{} +where + I: ExactSizeIterator, + I::Item: Clone, +{ +} diff --git a/vendor/itertools/src/tuple_impl.rs b/vendor/itertools/src/tuple_impl.rs index fdf086585..2bd9a0413 100644 --- a/vendor/itertools/src/tuple_impl.rs +++ b/vendor/itertools/src/tuple_impl.rs @@ -1,20 +1,19 @@ //! Some iterator that produces tuples +use std::iter::Cycle; use std::iter::Fuse; use std::iter::FusedIterator; -use std::iter::Take; -use std::iter::Cycle; use std::marker::PhantomData; +use crate::size_hint; + // `HomogeneousTuple` is a public facade for `TupleCollect`, allowing // tuple-related methods to be used by clients in generic contexts, while // hiding the implementation details of `TupleCollect`. // See https://github.com/rust-itertools/itertools/issues/387 /// Implemented for homogeneous tuples of size up to 12. -pub trait HomogeneousTuple - : TupleCollect -{} +pub trait HomogeneousTuple: TupleCollect {} impl<T: TupleCollect> HomogeneousTuple for T {} @@ -24,25 +23,25 @@ impl<T: TupleCollect> HomogeneousTuple for T {} /// [`Tuples::into_buffer()`]. #[derive(Clone, Debug)] pub struct TupleBuffer<T> - where T: HomogeneousTuple +where + T: HomogeneousTuple, { cur: usize, buf: T::Buffer, } impl<T> TupleBuffer<T> - where T: HomogeneousTuple +where + T: HomogeneousTuple, { fn new(buf: T::Buffer) -> Self { - TupleBuffer { - cur: 0, - buf, - } + TupleBuffer { cur: 0, buf } } } impl<T> Iterator for TupleBuffer<T> - where T: HomogeneousTuple +where + T: HomogeneousTuple, { type Item = T::Item; @@ -61,18 +60,16 @@ impl<T> Iterator for TupleBuffer<T> let len = if buffer.is_empty() { 0 } else { - buffer.iter() - .position(|x| x.is_none()) - .unwrap_or_else(|| buffer.len()) + buffer + .iter() + .position(|x| x.is_none()) + .unwrap_or_else(|| buffer.len()) }; (len, Some(len)) } } -impl<T> ExactSizeIterator for TupleBuffer<T> - where T: HomogeneousTuple -{ -} +impl<T> ExactSizeIterator for TupleBuffer<T> where T: HomogeneousTuple {} /// An iterator that groups the items in tuples of a specific size. /// @@ -80,8 +77,9 @@ impl<T> ExactSizeIterator for TupleBuffer<T> #[derive(Clone, Debug)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Tuples<I, T> - where I: Iterator<Item = T::Item>, - T: HomogeneousTuple +where + I: Iterator<Item = T::Item>, + T: HomogeneousTuple, { iter: Fuse<I>, buf: T::Buffer, @@ -89,8 +87,9 @@ pub struct Tuples<I, T> /// Create a new tuples iterator. pub fn tuples<I, T>(iter: I) -> Tuples<I, T> - where I: Iterator<Item = T::Item>, - T: HomogeneousTuple +where + I: Iterator<Item = T::Item>, + T: HomogeneousTuple, { Tuples { iter: iter.fuse(), @@ -99,19 +98,50 @@ pub fn tuples<I, T>(iter: I) -> Tuples<I, T> } impl<I, T> Iterator for Tuples<I, T> - where I: Iterator<Item = T::Item>, - T: HomogeneousTuple +where + I: Iterator<Item = T::Item>, + T: HomogeneousTuple, { type Item = T; fn next(&mut self) -> Option<Self::Item> { T::collect_from_iter(&mut self.iter, &mut self.buf) } + + fn size_hint(&self) -> (usize, Option<usize>) { + // The number of elts we've drawn from the underlying iterator, but have + // not yet produced as a tuple. + let buffered = T::buffer_len(&self.buf); + // To that, we must add the size estimates of the underlying iterator. + let (unbuffered_lo, unbuffered_hi) = self.iter.size_hint(); + // The total low estimate is the sum of the already-buffered elements, + // plus the low estimate of remaining unbuffered elements, divided by + // the tuple size. + let total_lo = add_then_div(unbuffered_lo, buffered, T::num_items()).unwrap_or(usize::MAX); + // And likewise for the total high estimate, but using the high estimate + // of the remaining unbuffered elements. + let total_hi = unbuffered_hi.and_then(|hi| add_then_div(hi, buffered, T::num_items())); + (total_lo, total_hi) + } +} + +/// `(n + a) / d` avoiding overflow when possible, returns `None` if it overflows. +fn add_then_div(n: usize, a: usize, d: usize) -> Option<usize> { + debug_assert_ne!(d, 0); + (n / d).checked_add(a / d)?.checked_add((n % d + a % d) / d) +} + +impl<I, T> ExactSizeIterator for Tuples<I, T> +where + I: ExactSizeIterator<Item = T::Item>, + T: HomogeneousTuple, +{ } impl<I, T> Tuples<I, T> - where I: Iterator<Item = T::Item>, - T: HomogeneousTuple +where + I: Iterator<Item = T::Item>, + T: HomogeneousTuple, { /// Return a buffer with the produced items that was not enough to be grouped in a tuple. /// @@ -128,7 +158,6 @@ impl<I, T> Tuples<I, T> } } - /// An iterator over all contiguous windows that produces tuples of a specific size. /// /// See [`.tuple_windows()`](crate::Itertools::tuple_windows) for more @@ -136,63 +165,77 @@ impl<I, T> Tuples<I, T> #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] #[derive(Clone, Debug)] pub struct TupleWindows<I, T> - where I: Iterator<Item = T::Item>, - T: HomogeneousTuple +where + I: Iterator<Item = T::Item>, + T: HomogeneousTuple, { iter: I, last: Option<T>, } /// Create a new tuple windows iterator. -pub fn tuple_windows<I, T>(mut iter: I) -> TupleWindows<I, T> - where I: Iterator<Item = T::Item>, - T: HomogeneousTuple, - T::Item: Clone +pub fn tuple_windows<I, T>(iter: I) -> TupleWindows<I, T> +where + I: Iterator<Item = T::Item>, + T: HomogeneousTuple, + T::Item: Clone, { - use std::iter::once; - - let mut last = None; - if T::num_items() != 1 { - // put in a duplicate item in front of the tuple; this simplifies - // .next() function. - if let Some(item) = iter.next() { - let iter = once(item.clone()).chain(once(item)).chain(&mut iter); - last = T::collect_from_iter_no_buf(iter); - } - } - - TupleWindows { - iter, - last, - } + TupleWindows { last: None, iter } } impl<I, T> Iterator for TupleWindows<I, T> - where I: Iterator<Item = T::Item>, - T: HomogeneousTuple + Clone, - T::Item: Clone +where + I: Iterator<Item = T::Item>, + T: HomogeneousTuple + Clone, + T::Item: Clone, { type Item = T; fn next(&mut self) -> Option<Self::Item> { if T::num_items() == 1 { - return T::collect_from_iter_no_buf(&mut self.iter) + return T::collect_from_iter_no_buf(&mut self.iter); } - if let Some(ref mut last) = self.last { - if let Some(new) = self.iter.next() { + if let Some(new) = self.iter.next() { + if let Some(ref mut last) = self.last { last.left_shift_push(new); - return Some(last.clone()); + Some(last.clone()) + } else { + use std::iter::once; + let iter = once(new).chain(&mut self.iter); + self.last = T::collect_from_iter_no_buf(iter); + self.last.clone() } + } else { + None + } + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let mut sh = self.iter.size_hint(); + // Adjust the size hint at the beginning + // OR when `num_items == 1` (but it does not change the size hint). + if self.last.is_none() { + sh = size_hint::sub_scalar(sh, T::num_items() - 1); } - None + sh } } +impl<I, T> ExactSizeIterator for TupleWindows<I, T> +where + I: ExactSizeIterator<Item = T::Item>, + T: HomogeneousTuple + Clone, + T::Item: Clone, +{ +} + impl<I, T> FusedIterator for TupleWindows<I, T> - where I: FusedIterator<Item = T::Item>, - T: HomogeneousTuple + Clone, - T::Item: Clone -{} +where + I: FusedIterator<Item = T::Item>, + T: HomogeneousTuple + Clone, + T::Item: Clone, +{ +} /// An iterator over all windows, wrapping back to the first elements when the /// window would otherwise exceed the length of the iterator, producing tuples @@ -203,58 +246,91 @@ impl<I, T> FusedIterator for TupleWindows<I, T> #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] #[derive(Debug, Clone)] pub struct CircularTupleWindows<I, T: Clone> - where I: Iterator<Item = T::Item> + Clone, - T: TupleCollect + Clone +where + I: Iterator<Item = T::Item> + Clone, + T: TupleCollect + Clone, { - iter: Take<TupleWindows<Cycle<I>, T>>, - phantom_data: PhantomData<T> + iter: TupleWindows<Cycle<I>, T>, + len: usize, + phantom_data: PhantomData<T>, } pub fn circular_tuple_windows<I, T>(iter: I) -> CircularTupleWindows<I, T> - where I: Iterator<Item = T::Item> + Clone + ExactSizeIterator, - T: TupleCollect + Clone, - T::Item: Clone +where + I: Iterator<Item = T::Item> + Clone + ExactSizeIterator, + T: TupleCollect + Clone, + T::Item: Clone, { let len = iter.len(); - let iter = tuple_windows(iter.cycle()).take(len); + let iter = tuple_windows(iter.cycle()); CircularTupleWindows { iter, - phantom_data: PhantomData{} + len, + phantom_data: PhantomData {}, } } impl<I, T> Iterator for CircularTupleWindows<I, T> - where I: Iterator<Item = T::Item> + Clone, - T: TupleCollect + Clone, - T::Item: Clone +where + I: Iterator<Item = T::Item> + Clone, + T: TupleCollect + Clone, + T::Item: Clone, { type Item = T; fn next(&mut self) -> Option<Self::Item> { - self.iter.next() + if self.len != 0 { + self.len -= 1; + self.iter.next() + } else { + None + } } + + fn size_hint(&self) -> (usize, Option<usize>) { + (self.len, Some(self.len)) + } +} + +impl<I, T> ExactSizeIterator for CircularTupleWindows<I, T> +where + I: Iterator<Item = T::Item> + Clone, + T: TupleCollect + Clone, + T::Item: Clone, +{ +} + +impl<I, T> FusedIterator for CircularTupleWindows<I, T> +where + I: Iterator<Item = T::Item> + Clone, + T: TupleCollect + Clone, + T::Item: Clone, +{ } pub trait TupleCollect: Sized { type Item; type Buffer: Default + AsRef<[Option<Self::Item>]> + AsMut<[Option<Self::Item>]>; + fn buffer_len(buf: &Self::Buffer) -> usize { + let s = buf.as_ref(); + s.iter().position(Option::is_none).unwrap_or(s.len()) + } + fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self> - where I: IntoIterator<Item = Self::Item>; + where + I: IntoIterator<Item = Self::Item>; fn collect_from_iter_no_buf<I>(iter: I) -> Option<Self> - where I: IntoIterator<Item = Self::Item>; + where + I: IntoIterator<Item = Self::Item>; fn num_items() -> usize; fn left_shift_push(&mut self, item: Self::Item); } -macro_rules! count_ident{ - () => {0}; - ($i0:ident, $($i:ident,)*) => {1 + count_ident!($($i,)*)}; -} macro_rules! rev_for_each_ident{ ($m:ident, ) => {}; ($m:ident, $i0:ident, $($i:ident,)*) => { @@ -269,7 +345,7 @@ macro_rules! impl_tuple_collect { impl_tuple_collect!($($Y,)*); impl<A> TupleCollect for ($(ignore_ident!($Y, A),)*) { type Item = A; - type Buffer = [Option<A>; count_ident!($($Y,)*) - 1]; + type Buffer = [Option<A>; count_ident!($($Y)*) - 1]; #[allow(unused_assignments, unused_mut)] fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self> @@ -312,7 +388,7 @@ macro_rules! impl_tuple_collect { } fn num_items() -> usize { - count_ident!($($Y,)*) + count_ident!($($Y)*) } fn left_shift_push(&mut self, mut item: A) { diff --git a/vendor/itertools/src/unique_impl.rs b/vendor/itertools/src/unique_impl.rs index 4e81e78ec..9b103a075 100644 --- a/vendor/itertools/src/unique_impl.rs +++ b/vendor/itertools/src/unique_impl.rs @@ -1,7 +1,7 @@ -use std::collections::HashMap; use std::collections::hash_map::Entry; -use std::hash::Hash; +use std::collections::HashMap; use std::fmt; +use std::hash::Hash; use std::iter::FusedIterator; /// An iterator adapter to filter out duplicate elements. @@ -19,17 +19,19 @@ pub struct UniqueBy<I: Iterator, V, F> { } impl<I, V, F> fmt::Debug for UniqueBy<I, V, F> - where I: Iterator + fmt::Debug, - V: fmt::Debug + Hash + Eq, +where + I: Iterator + fmt::Debug, + V: fmt::Debug + Hash + Eq, { debug_fmt_fields!(UniqueBy, iter, used); } /// Create a new `UniqueBy` iterator. pub fn unique_by<I, V, F>(iter: I, f: F) -> UniqueBy<I, V, F> - where V: Eq + Hash, - F: FnMut(&I::Item) -> V, - I: Iterator, +where + V: Eq + Hash, + F: FnMut(&I::Item) -> V, + I: Iterator, { UniqueBy { iter, @@ -40,8 +42,9 @@ pub fn unique_by<I, V, F>(iter: I, f: F) -> UniqueBy<I, V, F> // count the number of new unique keys in iterable (`used` is the set already seen) fn count_new_keys<I, K>(mut used: HashMap<K, ()>, iterable: I) -> usize - where I: IntoIterator<Item=K>, - K: Hash + Eq, +where + I: IntoIterator<Item = K>, + K: Hash + Eq, { let iter = iterable.into_iter(); let current_used = used.len(); @@ -50,9 +53,10 @@ fn count_new_keys<I, K>(mut used: HashMap<K, ()>, iterable: I) -> usize } impl<I, V, F> Iterator for UniqueBy<I, V, F> - where I: Iterator, - V: Eq + Hash, - F: FnMut(&I::Item) -> V +where + I: Iterator, + V: Eq + Hash, + F: FnMut(&I::Item) -> V, { type Item = I::Item; @@ -79,9 +83,10 @@ impl<I, V, F> Iterator for UniqueBy<I, V, F> } impl<I, V, F> DoubleEndedIterator for UniqueBy<I, V, F> - where I: DoubleEndedIterator, - V: Eq + Hash, - F: FnMut(&I::Item) -> V +where + I: DoubleEndedIterator, + V: Eq + Hash, + F: FnMut(&I::Item) -> V, { fn next_back(&mut self) -> Option<Self::Item> { while let Some(v) = self.iter.next_back() { @@ -95,14 +100,17 @@ impl<I, V, F> DoubleEndedIterator for UniqueBy<I, V, F> } impl<I, V, F> FusedIterator for UniqueBy<I, V, F> - where I: FusedIterator, - V: Eq + Hash, - F: FnMut(&I::Item) -> V -{} +where + I: FusedIterator, + V: Eq + Hash, + F: FnMut(&I::Item) -> V, +{ +} impl<I> Iterator for Unique<I> - where I: Iterator, - I::Item: Eq + Hash + Clone +where + I: Iterator, + I::Item: Eq + Hash + Clone, { type Item = I::Item; @@ -129,8 +137,9 @@ impl<I> Iterator for Unique<I> } impl<I> DoubleEndedIterator for Unique<I> - where I: DoubleEndedIterator, - I::Item: Eq + Hash + Clone +where + I: DoubleEndedIterator, + I::Item: Eq + Hash + Clone, { fn next_back(&mut self) -> Option<Self::Item> { while let Some(v) = self.iter.iter.next_back() { @@ -145,35 +154,43 @@ impl<I> DoubleEndedIterator for Unique<I> } impl<I> FusedIterator for Unique<I> - where I: FusedIterator, - I::Item: Eq + Hash + Clone -{} +where + I: FusedIterator, + I::Item: Eq + Hash + Clone, +{ +} /// An iterator adapter to filter out duplicate elements. /// /// See [`.unique()`](crate::Itertools::unique) for more information. #[derive(Clone)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] -pub struct Unique<I: Iterator> { +pub struct Unique<I> +where + I: Iterator, + I::Item: Eq + Hash + Clone, +{ iter: UniqueBy<I, I::Item, ()>, } impl<I> fmt::Debug for Unique<I> - where I: Iterator + fmt::Debug, - I::Item: Hash + Eq + fmt::Debug, +where + I: Iterator + fmt::Debug, + I::Item: Hash + Eq + fmt::Debug + Clone, { debug_fmt_fields!(Unique, iter); } pub fn unique<I>(iter: I) -> Unique<I> - where I: Iterator, - I::Item: Eq + Hash, +where + I: Iterator, + I::Item: Eq + Hash + Clone, { Unique { iter: UniqueBy { iter, used: HashMap::new(), f: (), - } + }, } } diff --git a/vendor/itertools/src/unziptuple.rs b/vendor/itertools/src/unziptuple.rs index 7af29ec4a..2c79c2d84 100644 --- a/vendor/itertools/src/unziptuple.rs +++ b/vendor/itertools/src/unziptuple.rs @@ -1,6 +1,6 @@ /// Converts an iterator of tuples into a tuple of containers. /// -/// `unzip()` consumes an entire iterator of n-ary tuples, producing `n` collections, one for each +/// `multiunzip()` consumes an entire iterator of n-ary tuples, producing `n` collections, one for each /// column. /// /// This function is, in some sense, the opposite of [`multizip`]. diff --git a/vendor/itertools/src/with_position.rs b/vendor/itertools/src/with_position.rs index dda9b25dc..89cddeb8a 100644 --- a/vendor/itertools/src/with_position.rs +++ b/vendor/itertools/src/with_position.rs @@ -1,4 +1,4 @@ -use std::iter::{Fuse,Peekable, FusedIterator}; +use std::iter::{Fuse, FusedIterator, Peekable}; /// An iterator adaptor that wraps each element in an [`Position`]. /// @@ -7,22 +7,25 @@ use std::iter::{Fuse,Peekable, FusedIterator}; /// See [`.with_position()`](crate::Itertools::with_position) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct WithPosition<I> - where I: Iterator, +where + I: Iterator, { handled_first: bool, peekable: Peekable<Fuse<I>>, } impl<I> Clone for WithPosition<I> - where I: Clone + Iterator, - I::Item: Clone, +where + I: Clone + Iterator, + I::Item: Clone, { clone_fields!(handled_first, peekable); } /// Create a new `WithPosition` iterator. pub fn with_position<I>(iter: I) -> WithPosition<I> - where I: Iterator, +where + I: Iterator, { WithPosition { handled_first: false, @@ -34,7 +37,7 @@ pub fn with_position<I>(iter: I) -> WithPosition<I> /// Indicates the position of this element in the iterator results. /// /// See [`.with_position()`](crate::Itertools::with_position) for more information. -#[derive(Copy, Clone, Debug, PartialEq)] +#[derive(Copy, Clone, Debug, PartialEq, Eq)] pub enum Position { /// This is the first element. First, @@ -78,11 +81,35 @@ impl<I: Iterator> Iterator for WithPosition<I> { fn size_hint(&self) -> (usize, Option<usize>) { self.peekable.size_hint() } + + fn fold<B, F>(mut self, mut init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + if let Some(mut head) = self.peekable.next() { + if !self.handled_first { + // The current head is `First` or `Only`, + // it depends if there is another item or not. + match self.peekable.next() { + Some(second) => { + let first = std::mem::replace(&mut head, second); + init = f(init, (Position::First, first)); + } + None => return f(init, (Position::Only, head)), + } + } + // Have seen the first item, and there's something left. + init = self.peekable.fold(init, |acc, mut item| { + std::mem::swap(&mut head, &mut item); + f(acc, (Position::Middle, item)) + }); + // The "head" is now the last item. + init = f(init, (Position::Last, head)); + } + init + } } -impl<I> ExactSizeIterator for WithPosition<I> - where I: ExactSizeIterator, -{ } +impl<I> ExactSizeIterator for WithPosition<I> where I: ExactSizeIterator {} -impl<I: Iterator> FusedIterator for WithPosition<I> -{} +impl<I: Iterator> FusedIterator for WithPosition<I> {} diff --git a/vendor/itertools/src/zip_eq_impl.rs b/vendor/itertools/src/zip_eq_impl.rs index a079b326a..09bc6988c 100644 --- a/vendor/itertools/src/zip_eq_impl.rs +++ b/vendor/itertools/src/zip_eq_impl.rs @@ -25,8 +25,9 @@ pub struct ZipEq<I, J> { /// } /// ``` pub fn zip_eq<I, J>(i: I, j: J) -> ZipEq<I::IntoIter, J::IntoIter> - where I: IntoIterator, - J: IntoIterator +where + I: IntoIterator, + J: IntoIterator, { ZipEq { a: i.into_iter(), @@ -35,8 +36,9 @@ pub fn zip_eq<I, J>(i: I, j: J) -> ZipEq<I::IntoIter, J::IntoIter> } impl<I, J> Iterator for ZipEq<I, J> - where I: Iterator, - J: Iterator +where + I: Iterator, + J: Iterator, { type Item = (I::Item, J::Item); @@ -44,8 +46,9 @@ impl<I, J> Iterator for ZipEq<I, J> match (self.a.next(), self.b.next()) { (None, None) => None, (Some(a), Some(b)) => Some((a, b)), - (None, Some(_)) | (Some(_), None) => - panic!("itertools: .zip_eq() reached end of one iterator before the other") + (None, Some(_)) | (Some(_), None) => { + panic!("itertools: .zip_eq() reached end of one iterator before the other") + } } } @@ -55,6 +58,8 @@ impl<I, J> Iterator for ZipEq<I, J> } impl<I, J> ExactSizeIterator for ZipEq<I, J> - where I: ExactSizeIterator, - J: ExactSizeIterator -{} +where + I: ExactSizeIterator, + J: ExactSizeIterator, +{ +} diff --git a/vendor/itertools/src/zip_longest.rs b/vendor/itertools/src/zip_longest.rs index cb9a7bacb..27d9f3ab6 100644 --- a/vendor/itertools/src/zip_longest.rs +++ b/vendor/itertools/src/zip_longest.rs @@ -1,5 +1,5 @@ -use std::cmp::Ordering::{Equal, Greater, Less}; use super::size_hint; +use std::cmp::Ordering::{Equal, Greater, Less}; use std::iter::{Fuse, FusedIterator}; use crate::either_or_both::EitherOrBoth; @@ -21,8 +21,9 @@ pub struct ZipLongest<T, U> { /// Create a new `ZipLongest` iterator. pub fn zip_longest<T, U>(a: T, b: U) -> ZipLongest<T, U> - where T: Iterator, - U: Iterator +where + T: Iterator, + U: Iterator, { ZipLongest { a: a.fuse(), @@ -31,8 +32,9 @@ pub fn zip_longest<T, U>(a: T, b: U) -> ZipLongest<T, U> } impl<T, U> Iterator for ZipLongest<T, U> - where T: Iterator, - U: Iterator +where + T: Iterator, + U: Iterator, { type Item = EitherOrBoth<T::Item, U::Item>; @@ -50,11 +52,26 @@ impl<T, U> Iterator for ZipLongest<T, U> fn size_hint(&self) -> (usize, Option<usize>) { size_hint::max(self.a.size_hint(), self.b.size_hint()) } + + #[inline] + fn fold<B, F>(self, mut init: B, mut f: F) -> B + where + Self: Sized, + F: FnMut(B, Self::Item) -> B, + { + let ZipLongest { a, mut b } = self; + init = a.fold(init, |init, a| match b.next() { + Some(b) => f(init, EitherOrBoth::Both(a, b)), + None => f(init, EitherOrBoth::Left(a)), + }); + b.fold(init, |init, b| f(init, EitherOrBoth::Right(b))) + } } impl<T, U> DoubleEndedIterator for ZipLongest<T, U> - where T: DoubleEndedIterator + ExactSizeIterator, - U: DoubleEndedIterator + ExactSizeIterator +where + T: DoubleEndedIterator + ExactSizeIterator, + U: DoubleEndedIterator + ExactSizeIterator, { #[inline] fn next_back(&mut self) -> Option<Self::Item> { @@ -73,11 +90,15 @@ impl<T, U> DoubleEndedIterator for ZipLongest<T, U> } impl<T, U> ExactSizeIterator for ZipLongest<T, U> - where T: ExactSizeIterator, - U: ExactSizeIterator -{} +where + T: ExactSizeIterator, + U: ExactSizeIterator, +{ +} impl<T, U> FusedIterator for ZipLongest<T, U> - where T: Iterator, - U: Iterator -{} +where + T: Iterator, + U: Iterator, +{ +} diff --git a/vendor/itertools/src/ziptuple.rs b/vendor/itertools/src/ziptuple.rs index 6d3a584c4..82760ae8f 100644 --- a/vendor/itertools/src/ziptuple.rs +++ b/vendor/itertools/src/ziptuple.rs @@ -38,8 +38,9 @@ pub struct Zip<T> { /// ``` /// [`izip!()`]: crate::izip pub fn multizip<T, U>(t: U) -> Zip<T> - where Zip<T>: From<U>, - Zip<T>: Iterator, +where + Zip<T>: From<U>, + Zip<T>: Iterator, { Zip::from(t) } |