diff options
Diffstat (limited to 'vendor/itertools/src/adaptors')
-rw-r--r-- | vendor/itertools/src/adaptors/mod.rs | 644 | ||||
-rw-r--r-- | vendor/itertools/src/adaptors/multi_product.rs | 91 |
2 files changed, 406 insertions, 329 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(); |