From ef24de24a82fe681581cc130f342363c47c0969a Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 7 Jun 2024 07:48:48 +0200 Subject: Merging upstream version 1.75.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/itertools-0.10.5/src/adaptors/coalesce.rs | 235 ++++ vendor/itertools-0.10.5/src/adaptors/map.rs | 124 +++ vendor/itertools-0.10.5/src/adaptors/mod.rs | 1151 ++++++++++++++++++++ .../itertools-0.10.5/src/adaptors/multi_product.rs | 230 ++++ 4 files changed, 1740 insertions(+) create mode 100644 vendor/itertools-0.10.5/src/adaptors/coalesce.rs create mode 100644 vendor/itertools-0.10.5/src/adaptors/map.rs create mode 100644 vendor/itertools-0.10.5/src/adaptors/mod.rs create mode 100644 vendor/itertools-0.10.5/src/adaptors/multi_product.rs (limited to 'vendor/itertools-0.10.5/src/adaptors') diff --git a/vendor/itertools-0.10.5/src/adaptors/coalesce.rs b/vendor/itertools-0.10.5/src/adaptors/coalesce.rs new file mode 100644 index 000000000..3df7cc582 --- /dev/null +++ b/vendor/itertools-0.10.5/src/adaptors/coalesce.rs @@ -0,0 +1,235 @@ +use std::fmt; +use std::iter::FusedIterator; + +use crate::size_hint; + +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct CoalesceBy +where + I: Iterator, +{ + iter: I, + last: Option, + f: F, +} + +impl Clone for CoalesceBy +where + I: Iterator, +{ + clone_fields!(last, iter, f); +} + +impl fmt::Debug for CoalesceBy +where + I: Iterator + fmt::Debug, + T: fmt::Debug, +{ + debug_fmt_fields!(CoalesceBy, iter); +} + +pub trait CoalescePredicate { + fn coalesce_pair(&mut self, t: T, item: Item) -> Result; +} + +impl Iterator for CoalesceBy +where + I: Iterator, + F: CoalescePredicate, +{ + type Item = T; + + fn next(&mut self) -> Option { + // this fuses the iterator + let last = self.last.take()?; + + let self_last = &mut self.last; + let self_f = &mut self.f; + Some( + self.iter + .try_fold(last, |last, next| match self_f.coalesce_pair(last, next) { + Ok(joined) => Ok(joined), + Err((last_, next_)) => { + *self_last = Some(next_); + Err(last_) + } + }) + .unwrap_or_else(|x| x), + ) + } + + fn size_hint(&self) -> (usize, Option) { + let (low, hi) = size_hint::add_scalar(self.iter.size_hint(), self.last.is_some() as usize); + ((low > 0) as usize, hi) + } + + fn fold(self, acc: Acc, mut fn_acc: FnAcc) -> Acc + where + FnAcc: FnMut(Acc, Self::Item) -> Acc, + { + if let Some(last) = self.last { + let mut f = self.f; + let (last, acc) = self.iter.fold((last, acc), |(last, acc), elt| { + match f.coalesce_pair(last, elt) { + Ok(joined) => (joined, acc), + Err((last_, next_)) => (next_, fn_acc(acc, last_)), + } + }); + fn_acc(acc, last) + } else { + acc + } + } +} + +impl, T> FusedIterator for CoalesceBy {} + +/// An iterator adaptor that may join together adjacent elements. +/// +/// See [`.coalesce()`](crate::Itertools::coalesce) for more information. +pub type Coalesce = CoalesceBy::Item>; + +impl CoalescePredicate for F +where + F: FnMut(T, Item) -> Result, +{ + fn coalesce_pair(&mut self, t: T, item: Item) -> Result { + self(t, item) + } +} + +/// Create a new `Coalesce`. +pub fn coalesce(mut iter: I, f: F) -> Coalesce +where + I: Iterator, +{ + Coalesce { + last: iter.next(), + iter, + f, + } +} + +/// An iterator adaptor that removes repeated duplicates, determining equality using a comparison function. +/// +/// See [`.dedup_by()`](crate::Itertools::dedup_by) or [`.dedup()`](crate::Itertools::dedup) for more information. +pub type DedupBy = CoalesceBy, ::Item>; + +#[derive(Clone)] +pub struct DedupPred2CoalescePred(DP); + +impl fmt::Debug for DedupPred2CoalescePred { + debug_fmt_fields!(DedupPred2CoalescePred,); +} + +pub trait DedupPredicate { + // TODO replace by Fn(&T, &T)->bool once Rust supports it + fn dedup_pair(&mut self, a: &T, b: &T) -> bool; +} + +impl CoalescePredicate for DedupPred2CoalescePred +where + DP: DedupPredicate, +{ + fn coalesce_pair(&mut self, t: T, item: T) -> Result { + if self.0.dedup_pair(&t, &item) { + Ok(t) + } else { + Err((t, item)) + } + } +} + +#[derive(Clone, Debug)] +pub struct DedupEq; + +impl DedupPredicate for DedupEq { + fn dedup_pair(&mut self, a: &T, b: &T) -> bool { + a == b + } +} + +impl bool> DedupPredicate for F { + fn dedup_pair(&mut self, a: &T, b: &T) -> bool { + self(a, b) + } +} + +/// Create a new `DedupBy`. +pub fn dedup_by(mut iter: I, dedup_pred: Pred) -> DedupBy +where + I: Iterator, +{ + DedupBy { + last: iter.next(), + iter, + f: DedupPred2CoalescePred(dedup_pred), + } +} + +/// An iterator adaptor that removes repeated duplicates. +/// +/// See [`.dedup()`](crate::Itertools::dedup) for more information. +pub type Dedup = DedupBy; + +/// Create a new `Dedup`. +pub fn dedup(iter: I) -> Dedup +where + I: Iterator, +{ + dedup_by(iter, DedupEq) +} + +/// An iterator adaptor that removes repeated duplicates, while keeping a count of how many +/// repeated elements were present. This will determine equality using a comparison function. +/// +/// See [`.dedup_by_with_count()`](crate::Itertools::dedup_by_with_count) or +/// [`.dedup_with_count()`](crate::Itertools::dedup_with_count) for more information. +pub type DedupByWithCount = + CoalesceBy, (usize, ::Item)>; + +#[derive(Clone, Debug)] +pub struct DedupPredWithCount2CoalescePred(DP); + +impl CoalescePredicate for DedupPredWithCount2CoalescePred +where + DP: DedupPredicate, +{ + fn coalesce_pair( + &mut self, + (c, t): (usize, T), + item: T, + ) -> Result<(usize, T), ((usize, T), (usize, T))> { + if self.0.dedup_pair(&t, &item) { + Ok((c + 1, t)) + } else { + Err(((c, t), (1, item))) + } + } +} + +/// An iterator adaptor that removes repeated duplicates, while keeping a count of how many +/// repeated elements were present. +/// +/// See [`.dedup_with_count()`](crate::Itertools::dedup_with_count) for more information. +pub type DedupWithCount = DedupByWithCount; + +/// Create a new `DedupByWithCount`. +pub fn dedup_by_with_count(mut iter: I, dedup_pred: Pred) -> DedupByWithCount +where + I: Iterator, +{ + DedupByWithCount { + last: iter.next().map(|v| (1, v)), + iter, + f: DedupPredWithCount2CoalescePred(dedup_pred), + } +} + +/// Create a new `DedupWithCount`. +pub fn dedup_with_count(iter: I) -> DedupWithCount +where + I: Iterator, +{ + dedup_by_with_count(iter, DedupEq) +} diff --git a/vendor/itertools-0.10.5/src/adaptors/map.rs b/vendor/itertools-0.10.5/src/adaptors/map.rs new file mode 100644 index 000000000..cf5e5a00d --- /dev/null +++ b/vendor/itertools-0.10.5/src/adaptors/map.rs @@ -0,0 +1,124 @@ +use std::iter::FromIterator; +use std::marker::PhantomData; + +#[derive(Clone, Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct MapSpecialCase { + iter: I, + f: F, +} + +pub trait MapSpecialCaseFn { + type Out; + fn call(&mut self, t: T) -> Self::Out; +} + +impl Iterator for MapSpecialCase +where + I: Iterator, + R: MapSpecialCaseFn, +{ + type Item = R::Out; + + fn next(&mut self) -> Option { + self.iter.next().map(|i| self.f.call(i)) + } + + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + fn fold(self, init: Acc, mut fold_f: Fold) -> Acc + where + Fold: FnMut(Acc, Self::Item) -> Acc, + { + let mut f = self.f; + self.iter.fold(init, move |acc, v| fold_f(acc, f.call(v))) + } + + fn collect(self) -> C + where + C: FromIterator, + { + let mut f = self.f; + self.iter.map(move |v| f.call(v)).collect() + } +} + +impl DoubleEndedIterator for MapSpecialCase +where + I: DoubleEndedIterator, + R: MapSpecialCaseFn, +{ + fn next_back(&mut self) -> Option { + self.iter.next_back().map(|i| self.f.call(i)) + } +} + +impl ExactSizeIterator for MapSpecialCase +where + I: ExactSizeIterator, + R: MapSpecialCaseFn, +{ +} + +/// An iterator adapter to apply a transformation within a nested `Result::Ok`. +/// +/// See [`.map_ok()`](crate::Itertools::map_ok) for more information. +pub type MapOk = MapSpecialCase>; + +/// See [`MapOk`]. +#[deprecated(note = "Use MapOk instead", since = "0.10.0")] +pub type MapResults = MapOk; + +impl MapSpecialCaseFn> for MapSpecialCaseFnOk +where + F: FnMut(T) -> U, +{ + type Out = Result; + fn call(&mut self, t: Result) -> Self::Out { + t.map(|v| self.0(v)) + } +} + +#[derive(Clone)] +pub struct MapSpecialCaseFnOk(F); + +impl std::fmt::Debug for MapSpecialCaseFnOk { + debug_fmt_fields!(MapSpecialCaseFnOk,); +} + +/// Create a new `MapOk` iterator. +pub fn map_ok(iter: I, f: F) -> MapOk +where + I: Iterator>, + F: FnMut(T) -> U, +{ + MapSpecialCase { + iter, + f: MapSpecialCaseFnOk(f), + } +} + +/// An iterator adapter to apply `Into` conversion to each element. +/// +/// See [`.map_into()`](crate::Itertools::map_into) for more information. +pub type MapInto = MapSpecialCase>; + +impl, U> MapSpecialCaseFn for MapSpecialCaseFnInto { + type Out = U; + fn call(&mut self, t: T) -> Self::Out { + t.into() + } +} + +#[derive(Clone, Debug)] +pub struct MapSpecialCaseFnInto(PhantomData); + +/// Create a new [`MapInto`] iterator. +pub fn map_into(iter: I) -> MapInto { + MapSpecialCase { + iter, + f: MapSpecialCaseFnInto(PhantomData), + } +} diff --git a/vendor/itertools-0.10.5/src/adaptors/mod.rs b/vendor/itertools-0.10.5/src/adaptors/mod.rs new file mode 100644 index 000000000..1695bbd65 --- /dev/null +++ b/vendor/itertools-0.10.5/src/adaptors/mod.rs @@ -0,0 +1,1151 @@ +//! Licensed under the Apache License, Version 2.0 +//! or the MIT license +//! , at your +//! option. This file may not be copied, modified, or distributed +//! except according to those terms. + +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; +#[cfg(feature = "use_alloc")] +pub use self::multi_product::*; + +use std::fmt; +use std::iter::{Fuse, Peekable, FromIterator, FusedIterator}; +use std::marker::PhantomData; +use crate::size_hint; + +/// An iterator adaptor that alternates elements from two iterators until both +/// run out. +/// +/// This iterator is *fused*. +/// +/// See [`.interleave()`](crate::Itertools::interleave) for more information. +#[derive(Clone, Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Interleave { + a: Fuse, + b: Fuse, + flag: bool, +} + +/// Create an iterator that interleaves elements in `i` and `j`. +/// +/// [`IntoIterator`] enabled version of `[Itertools::interleave]`. +pub fn interleave(i: I, j: J) -> Interleave<::IntoIter, ::IntoIter> + where I: IntoIterator, + J: IntoIterator +{ + Interleave { + a: i.into_iter().fuse(), + b: j.into_iter().fuse(), + flag: false, + } +} + +impl Iterator for Interleave + where I: Iterator, + J: Iterator +{ + type Item = I::Item; + #[inline] + fn next(&mut self) -> Option { + self.flag = !self.flag; + if self.flag { + match self.a.next() { + None => self.b.next(), + r => r, + } + } else { + match self.b.next() { + None => self.a.next(), + r => r, + } + } + } + + fn size_hint(&self) -> (usize, Option) { + size_hint::add(self.a.size_hint(), self.b.size_hint()) + } +} + +impl FusedIterator for Interleave + where I: Iterator, + J: Iterator +{} + +/// An iterator adaptor that alternates elements from the two iterators until +/// one of them runs out. +/// +/// This iterator is *fused*. +/// +/// See [`.interleave_shortest()`](crate::Itertools::interleave_shortest) +/// for more information. +#[derive(Clone, Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct InterleaveShortest + where I: Iterator, + J: Iterator +{ + it0: I, + it1: J, + phase: bool, // false ==> it0, true ==> it1 +} + +/// Create a new `InterleaveShortest` iterator. +pub fn interleave_shortest(a: I, b: J) -> InterleaveShortest + where I: Iterator, + J: Iterator +{ + InterleaveShortest { + it0: a, + it1: b, + phase: false, + } +} + +impl Iterator for InterleaveShortest + where I: Iterator, + J: Iterator +{ + type Item = I::Item; + + #[inline] + fn next(&mut self) -> Option { + let e = if self.phase { self.it1.next() } else { self.it0.next() }; + if e.is_some() { + self.phase = !self.phase; + } + e + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + let (curr_hint, next_hint) = { + let it0_hint = self.it0.size_hint(); + let it1_hint = self.it1.size_hint(); + if self.phase { + (it1_hint, it0_hint) + } else { + (it0_hint, it1_hint) + } + }; + let (curr_lower, curr_upper) = curr_hint; + 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 upper = { + let extra_elem = match (curr_upper, next_upper) { + (_, None) => false, + (None, Some(_)) => true, + (Some(curr_max), Some(next_max)) => curr_max > next_max, + }; + if extra_elem { + combined_upper.and_then(|x| x.checked_add(1)) + } else { + combined_upper + } + }; + (lower, upper) + } +} + +impl FusedIterator for InterleaveShortest + where I: FusedIterator, + J: FusedIterator +{} + +#[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`. +pub struct PutBack + where I: Iterator +{ + top: Option, + iter: I, +} + +/// Create an iterator where you can put back a single item +pub fn put_back(iterable: I) -> PutBack + where I: IntoIterator +{ + PutBack { + top: None, + iter: iterable.into_iter(), + } +} + +impl PutBack + where I: Iterator +{ + /// put back value `value` (builder method) + pub fn with_value(mut self, value: I::Item) -> Self { + self.put_back(value); + self + } + + /// Split the `PutBack` into its parts. + #[inline] + pub fn into_parts(self) -> (Option, I) { + let PutBack{top, iter} = self; + (top, iter) + } + + /// Put back a single value to the front of the iterator. + /// + /// If a value is already in the put back slot, it is overwritten. + #[inline] + pub fn put_back(&mut self, x: I::Item) { + self.top = Some(x); + } +} + +impl Iterator for PutBack + where I: Iterator +{ + type Item = I::Item; + #[inline] + fn next(&mut self) -> Option { + match self.top { + None => self.iter.next(), + ref mut some => some.take(), + } + } + #[inline] + fn size_hint(&self) -> (usize, Option) { + // Not ExactSizeIterator because size may be larger than usize + size_hint::add_scalar(self.iter.size_hint(), self.top.is_some() as usize) + } + + fn count(self) -> usize { + self.iter.count() + (self.top.is_some() as usize) + } + + fn last(self) -> Option { + self.iter.last().or(self.top) + } + + fn nth(&mut self, n: usize) -> Option { + match self.top { + None => self.iter.nth(n), + ref mut some => { + if n == 0 { + some.take() + } else { + *some = None; + self.iter.nth(n - 1) + } + } + } + } + + fn all(&mut self, mut f: G) -> bool + where G: FnMut(Self::Item) -> bool + { + if let Some(elt) = self.top.take() { + if !f(elt) { + return false; + } + } + self.iter.all(f) + } + + fn fold(mut self, init: Acc, mut f: G) -> Acc + where G: FnMut(Acc, Self::Item) -> Acc, + { + let mut accum = init; + if let Some(elt) = self.top.take() { + accum = f(accum, elt); + } + self.iter.fold(accum, f) + } +} + +#[derive(Debug, Clone)] +/// An iterator adaptor that iterates over the cartesian product of +/// the element sets of two iterators `I` and `J`. +/// +/// Iterator element type is `(I::Item, J::Item)`. +/// +/// See [`.cartesian_product()`](crate::Itertools::cartesian_product) for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Product + where I: Iterator +{ + a: I, + a_cur: Option, + b: J, + b_orig: J, +} + +/// Create a new cartesian product iterator +/// +/// Iterator element type is `(I::Item, J::Item)`. +pub fn cartesian_product(mut i: I, j: J) -> Product + where I: Iterator, + J: Clone + Iterator, + I::Item: Clone +{ + Product { + a_cur: i.next(), + a: i, + b: j.clone(), + b_orig: j, + } +} + +impl Iterator for Product + where I: Iterator, + J: Clone + Iterator, + I::Item: Clone +{ + type Item = (I::Item, J::Item); + + fn next(&mut self) -> Option { + let elt_b = match self.b.next() { + None => { + self.b = self.b_orig.clone(); + match self.b.next() { + None => return None, + Some(x) => { + self.a_cur = self.a.next(); + x + } + } + } + Some(x) => x + }; + self.a_cur.as_ref().map(|a| (a.clone(), elt_b)) + } + + fn size_hint(&self) -> (usize, Option) { + 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))) + } + + fn fold(mut 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; + loop { + accum = b.fold(accum, |acc, elt| f(acc, (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; + } else { + break; + } + } + } + accum + } +} + +impl FusedIterator for Product + 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. +/// +/// Iterator element type is *X*, if the return type of `F` is *Option\*. +/// +/// See [`.batching()`](crate::Itertools::batching) for more information. +#[derive(Clone)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Batching { + f: F, + iter: I, +} + +impl fmt::Debug for Batching where I: fmt::Debug { + debug_fmt_fields!(Batching, iter); +} + +/// Create a new Batching iterator. +pub fn batching(iter: I, f: F) -> Batching { + Batching { f, iter } +} + +impl Iterator for Batching + where I: Iterator, + F: FnMut(&mut I) -> Option +{ + type Item = B; + #[inline] + fn next(&mut self) -> Option { + (self.f)(&mut self.iter) + } +} + +/// An iterator adaptor that steps a number elements in the base iterator +/// for each iteration. +/// +/// The iterator steps by yielding the next element from the base iterator, +/// 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")] +#[allow(deprecated)] +#[derive(Clone, Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Step { + iter: Fuse, + skip: usize, +} + +/// Create a `Step` iterator. +/// +/// **Panics** if the step is 0. +#[allow(deprecated)] +pub fn step(iter: I, step: usize) -> Step + where I: Iterator +{ + assert!(step != 0); + Step { + iter: iter.fuse(), + skip: step - 1, + } +} + +#[allow(deprecated)] +impl Iterator for Step + where I: Iterator +{ + type Item = I::Item; + #[inline] + fn next(&mut self) -> Option { + let elt = self.iter.next(); + if self.skip > 0 { + self.iter.nth(self.skip - 1); + } + elt + } + + fn size_hint(&self) -> (usize, Option) { + let (low, high) = self.iter.size_hint(); + let div = |x: usize| { + if x == 0 { + 0 + } else { + 1 + (x - 1) / (self.skip + 1) + } + }; + (div(low), high.map(div)) + } +} + +// known size +#[allow(deprecated)] +impl ExactSizeIterator for Step + where I: ExactSizeIterator +{} + +pub trait MergePredicate { + fn merge_pred(&mut self, a: &T, b: &T) -> bool; +} + +#[derive(Clone, Debug)] +pub struct MergeLte; + +impl MergePredicate 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 = MergeBy; + +/// 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: I, j: J) -> Merge<::IntoIter, ::IntoIter> + where I: IntoIterator, + J: IntoIterator, + 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 + where I: Iterator, + J: Iterator +{ + a: Peekable, + b: Peekable, + fused: Option, + cmp: F, +} + +impl fmt::Debug for MergeBy + where I: Iterator + fmt::Debug, J: Iterator + fmt::Debug, + I::Item: fmt::Debug, +{ + debug_fmt_fields!(MergeBy, a, b); +} + +implbool> MergePredicate for F { + fn merge_pred(&mut self, a: &T, b: &T) -> bool { + self(a, b) + } +} + +/// Create a `MergeBy` iterator. +pub fn merge_by_new(a: I, b: J, cmp: F) -> MergeBy + where I: IntoIterator, + J: IntoIterator, + F: MergePredicate, +{ + MergeBy { + a: a.into_iter().peekable(), + b: b.into_iter().peekable(), + fused: None, + cmp, + } +} + +impl Clone for MergeBy + where I: Iterator, + J: Iterator, + Peekable: Clone, + Peekable: Clone, + F: Clone +{ + clone_fields!(a, b, fused, cmp); +} + +impl Iterator for MergeBy + where I: Iterator, + J: Iterator, + F: MergePredicate +{ + type Item = I::Item; + + fn next(&mut self) -> Option { + 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) { + // Not ExactSizeIterator because size may be larger than usize + size_hint::add(self.a.size_hint(), self.b.size_hint()) + } +} + +impl FusedIterator for MergeBy + where I: FusedIterator, + J: FusedIterator, + F: MergePredicate +{} + +/// An iterator adaptor that borrows from a `Clone`-able iterator +/// to only pick off elements while the predicate returns `true`. +/// +/// See [`.take_while_ref()`](crate::Itertools::take_while_ref) for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct TakeWhileRef<'a, I: 'a, F> { + iter: &'a mut I, + f: F, +} + +impl<'a, I, F> fmt::Debug for TakeWhileRef<'a, I, F> + 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(iter: &mut I, f: F) -> TakeWhileRef + 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 +{ + type Item = I::Item; + + fn next(&mut self) -> Option { + let old = self.iter.clone(); + match self.iter.next() { + None => None, + Some(elt) => { + if (self.f)(&elt) { + Some(elt) + } else { + *self.iter = old; + None + } + } + } + } + + fn size_hint(&self) -> (usize, Option) { + (0, self.iter.size_hint().1) + } +} + +/// An iterator adaptor that filters `Option` iterator elements +/// and produces `A`. Stops on the first `None` encountered. +/// +/// See [`.while_some()`](crate::Itertools::while_some) for more information. +#[derive(Clone, Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct WhileSome { + iter: I, +} + +/// Create a new `WhileSome`. +pub fn while_some(iter: I) -> WhileSome { + WhileSome { iter } +} + +impl Iterator for WhileSome + where I: Iterator> +{ + type Item = A; + + fn next(&mut self) -> Option { + match self.iter.next() { + None | Some(None) => None, + Some(elt) => elt, + } + } + + fn size_hint(&self) -> (usize, Option) { + (0, self.iter.size_hint().1) + } +} + +/// An iterator to iterate through all combinations in a `Clone`-able iterator that produces tuples +/// of a specific size. +/// +/// See [`.tuple_combinations()`](crate::Itertools::tuple_combinations) for more +/// information. +#[derive(Clone, Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct TupleCombinations + where I: Iterator, + T: HasCombination +{ + iter: T::Combination, + _mi: PhantomData, +} + +pub trait HasCombination: Sized { + type Combination: From + Iterator; +} + +/// Create a new `TupleCombinations` from a clonable iterator. +pub fn tuple_combinations(iter: I) -> TupleCombinations + where I: Iterator + Clone, + I::Item: Clone, + T: HasCombination, +{ + TupleCombinations { + iter: T::Combination::from(iter), + _mi: PhantomData, + } +} + +impl Iterator for TupleCombinations + where I: Iterator, + T: HasCombination, +{ + type Item = T; + + fn next(&mut self) -> Option { + self.iter.next() + } +} + +impl FusedIterator for TupleCombinations + where I: FusedIterator, + T: HasCombination, +{} + +#[derive(Clone, Debug)] +pub struct Tuple1Combination { + iter: I, +} + +impl From for Tuple1Combination { + fn from(iter: I) -> Self { + Tuple1Combination { iter } + } +} + +impl Iterator for Tuple1Combination { + type Item = (I::Item,); + + fn next(&mut self) -> Option { + self.iter.next().map(|x| (x,)) + } +} + +impl HasCombination for (I::Item,) { + type Combination = Tuple1Combination; +} + +macro_rules! impl_tuple_combination { + ($C:ident $P:ident ; $($X:ident)*) => ( + #[derive(Clone, Debug)] + pub struct $C { + item: Option, + iter: I, + c: $P, + } + + impl From for $C { + fn from(mut iter: I) -> Self { + Self { + item: iter.next(), + iter: iter.clone(), + c: iter.into(), + } + } + } + + impl From for $C> { + fn from(iter: I) -> Self { + Self::from(iter.fuse()) + } + } + + impl Iterator for $C + where I: Iterator + Clone, + I::Item: Clone + { + type Item = (A, $(ignore_ident!($X, A)),*); + + fn next(&mut self) -> Option { + 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),*)) + }) + } + } + } + + impl HasCombination for (A, $(ignore_ident!($X, A)),*) + where I: Iterator + Clone, + I::Item: Clone + { + type Combination = $C>; + } + ) +} + +// This snippet generates the twelve `impl_tuple_combination!` invocations: +// use core::iter; +// use itertools::Itertools; +// +// for i in 2..=12 { +// println!("impl_tuple_combination!(Tuple{arity}Combination Tuple{prev}Combination; {idents});", +// arity = i, +// prev = i - 1, +// idents = ('a'..'z').take(i - 1).join(" "), +// ); +// } +// It could probably be replaced by a bit more macro cleverness. +impl_tuple_combination!(Tuple2Combination Tuple1Combination; a); +impl_tuple_combination!(Tuple3Combination Tuple2Combination; a b); +impl_tuple_combination!(Tuple4Combination Tuple3Combination; a b c); +impl_tuple_combination!(Tuple5Combination Tuple4Combination; a b c d); +impl_tuple_combination!(Tuple6Combination Tuple5Combination; a b c d e); +impl_tuple_combination!(Tuple7Combination Tuple6Combination; a b c d e f); +impl_tuple_combination!(Tuple8Combination Tuple7Combination; a b c d e f g); +impl_tuple_combination!(Tuple9Combination Tuple8Combination; a b c d e f g h); +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); + +/// An iterator adapter to filter values within a nested `Result::Ok`. +/// +/// See [`.filter_ok()`](crate::Itertools::filter_ok) for more information. +#[derive(Clone)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct FilterOk { + iter: I, + f: F +} + +impl fmt::Debug for FilterOk +where + I: fmt::Debug, +{ + debug_fmt_fields!(FilterOk, iter); +} + +/// Create a new `FilterOk` iterator. +pub fn filter_ok(iter: I, f: F) -> FilterOk + where I: Iterator>, + F: FnMut(&T) -> bool, +{ + FilterOk { + iter, + f, + } +} + +impl Iterator for FilterOk + where I: Iterator>, + F: FnMut(&T) -> bool, +{ + type Item = Result; + + fn next(&mut self) -> Option { + loop { + match self.iter.next() { + Some(Ok(v)) => { + if (self.f)(&v) { + return Some(Ok(v)); + } + }, + Some(Err(e)) => return Some(Err(e)), + None => return None, + } + } + } + + fn size_hint(&self) -> (usize, Option) { + (0, self.iter.size_hint().1) + } + + fn fold(self, init: Acc, fold_f: Fold) -> 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) + } + + fn collect(self) -> C + where C: FromIterator + { + let mut f = self.f; + self.iter.filter(|v| { + v.as_ref().map(&mut f).unwrap_or(true) + }).collect() + } +} + +impl FusedIterator for FilterOk + where I: FusedIterator>, + 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"] +pub struct FilterMapOk { + iter: I, + f: F +} + +impl fmt::Debug for FilterMapOk +where + I: fmt::Debug, +{ + debug_fmt_fields!(FilterMapOk, iter); +} + +fn transpose_result(result: Result, E>) -> Option> { + match result { + Ok(Some(v)) => Some(Ok(v)), + Ok(None) => None, + Err(e) => Some(Err(e)), + } +} + +/// Create a new `FilterOk` iterator. +pub fn filter_map_ok(iter: I, f: F) -> FilterMapOk + where I: Iterator>, + F: FnMut(T) -> Option, +{ + FilterMapOk { + iter, + f, + } +} + +impl Iterator for FilterMapOk + where I: Iterator>, + F: FnMut(T) -> Option, +{ + type Item = Result; + + fn next(&mut self) -> Option { + loop { + match self.iter.next() { + Some(Ok(v)) => { + if let Some(v) = (self.f)(v) { + return Some(Ok(v)); + } + }, + Some(Err(e)) => return Some(Err(e)), + None => return None, + } + } + } + + fn size_hint(&self) -> (usize, Option) { + (0, self.iter.size_hint().1) + } + + fn fold(self, init: Acc, fold_f: Fold) -> 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) + } + + fn collect(self) -> C + where C: FromIterator + { + let mut f = self.f; + self.iter.filter_map(|v| { + transpose_result(v.map(&mut f)) + }).collect() + } +} + +impl FusedIterator for FilterMapOk + where I: FusedIterator>, + F: FnMut(T) -> Option, +{} + +/// An iterator adapter to get the positions of each element that matches a predicate. +/// +/// See [`.positions()`](crate::Itertools::positions) for more information. +#[derive(Clone)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Positions { + iter: I, + f: F, + count: usize, +} + +impl fmt::Debug for Positions +where + I: fmt::Debug, +{ + debug_fmt_fields!(Positions, iter, count); +} + +/// Create a new `Positions` iterator. +pub fn positions(iter: I, f: F) -> Positions + where I: Iterator, + F: FnMut(I::Item) -> bool, +{ + Positions { + iter, + f, + count: 0 + } +} + +impl Iterator for Positions + where I: Iterator, + F: FnMut(I::Item) -> bool, +{ + type Item = usize; + + fn next(&mut self) -> Option { + while let Some(v) = self.iter.next() { + let i = self.count; + self.count = i + 1; + if (self.f)(v) { + return Some(i); + } + } + None + } + + fn size_hint(&self) -> (usize, Option) { + (0, self.iter.size_hint().1) + } +} + +impl DoubleEndedIterator for Positions + where I: DoubleEndedIterator + ExactSizeIterator, + F: FnMut(I::Item) -> bool, +{ + fn next_back(&mut self) -> Option { + while let Some(v) = self.iter.next_back() { + if (self.f)(v) { + return Some(self.count + self.iter.len()) + } + } + None + } +} + +impl FusedIterator for Positions + where I: FusedIterator, + F: FnMut(I::Item) -> bool, +{} + +/// An iterator adapter to apply a mutating function to each element before yielding it. +/// +/// See [`.update()`](crate::Itertools::update) for more information. +#[derive(Clone)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Update { + iter: I, + f: F, +} + +impl fmt::Debug for Update +where + I: fmt::Debug, +{ + debug_fmt_fields!(Update, iter); +} + +/// Create a new `Update` iterator. +pub fn update(iter: I, f: F) -> Update +where + I: Iterator, + F: FnMut(&mut I::Item), +{ + Update { iter, f } +} + +impl Iterator for Update +where + I: Iterator, + F: FnMut(&mut I::Item), +{ + type Item = I::Item; + + fn next(&mut self) -> Option { + if let Some(mut v) = self.iter.next() { + (self.f)(&mut v); + Some(v) + } else { + None + } + } + + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + fn fold(self, init: Acc, mut g: G) -> 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) }) + } + + // if possible, re-use inner iterator specializations in collect + fn collect(self) -> C + where C: FromIterator + { + let mut f = self.f; + self.iter.map(move |mut v| { f(&mut v); v }).collect() + } +} + +impl ExactSizeIterator for Update +where + I: ExactSizeIterator, + F: FnMut(&mut I::Item), +{} + +impl DoubleEndedIterator for Update +where + I: DoubleEndedIterator, + F: FnMut(&mut I::Item), +{ + fn next_back(&mut self) -> Option { + if let Some(mut v) = self.iter.next_back() { + (self.f)(&mut v); + Some(v) + } else { + None + } + } +} + +impl FusedIterator for Update +where + I: FusedIterator, + F: FnMut(&mut I::Item), +{} diff --git a/vendor/itertools-0.10.5/src/adaptors/multi_product.rs b/vendor/itertools-0.10.5/src/adaptors/multi_product.rs new file mode 100644 index 000000000..0b3840698 --- /dev/null +++ b/vendor/itertools-0.10.5/src/adaptors/multi_product.rs @@ -0,0 +1,230 @@ +#![cfg(feature = "use_alloc")] + +use crate::size_hint; +use crate::Itertools; + +use alloc::vec::Vec; + +#[derive(Clone)] +/// An iterator adaptor that iterates over the cartesian product of +/// multiple iterators of type `I`. +/// +/// An iterator element type is `Vec`. +/// +/// See [`.multi_cartesian_product()`](crate::Itertools::multi_cartesian_product) +/// for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct MultiProduct(Vec>) + where I: Iterator + Clone, + I::Item: Clone; + +impl std::fmt::Debug for MultiProduct +where + I: Iterator + Clone + std::fmt::Debug, + I::Item: Clone + std::fmt::Debug, +{ + debug_fmt_fields!(CoalesceBy, 0); +} + +/// Create a new cartesian product iterator over an arbitrary number +/// of iterators of the same type. +/// +/// Iterator element is of type `Vec`. +pub fn multi_cartesian_product(iters: H) -> MultiProduct<::IntoIter> + where H: Iterator, + H::Item: IntoIterator, + ::IntoIter: Clone, + ::Item: Clone +{ + 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 + where I: Iterator + Clone, + I::Item: Clone +{ + cur: Option, + iter: I, + iter_orig: I, +} + +/// Holds the current state during an iteration of a `MultiProduct`. +#[derive(Debug)] +enum MultiProductIterState { + StartOfIter, + MidIter { on_first_iter: bool }, +} + +impl MultiProduct + where I: Iterator + Clone, + I::Item: Clone +{ + /// Iterates the rightmost iterator, then recursively iterates iterators + /// to the left if necessary. + /// + /// Returns true if the iteration succeeded, else false. + fn iterate_last( + multi_iters: &mut [MultiProductIter], + mut state: MultiProductIterState + ) -> bool { + use self::MultiProductIterState::*; + + if let Some((last, rest)) = multi_iters.split_last_mut() { + let on_first_iter = match state { + StartOfIter => { + let on_first_iter = !last.in_progress(); + state = MidIter { on_first_iter }; + on_first_iter + }, + MidIter { on_first_iter } => on_first_iter + }; + + if !on_first_iter { + last.iterate(); + } + + if last.in_progress() { + true + } else if MultiProduct::iterate_last(rest, state) { + last.reset(); + last.iterate(); + // If iterator is None twice consecutively, then iterator is + // empty; whole product is empty. + last.in_progress() + } else { + false + } + } else { + // Reached end of iterator list. On initialisation, return true. + // At end of iteration (final iterator finishes), finish. + match state { + StartOfIter => false, + MidIter { on_first_iter } => on_first_iter + } + } + } + + /// Returns the unwrapped value of the next iteration. + fn curr_iterator(&self) -> Vec { + self.0.iter().map(|multi_iter| { + multi_iter.cur.clone().unwrap() + }).collect() + } + + /// Returns true if iteration has started and has not yet finished; false + /// otherwise. + fn in_progress(&self) -> bool { + if let Some(last) = self.0.last() { + last.in_progress() + } else { + false + } + } +} + +impl MultiProductIter + where I: Iterator + Clone, + I::Item: Clone +{ + fn new(iter: I) -> Self { + MultiProductIter { + cur: None, + iter: iter.clone(), + iter_orig: iter + } + } + + /// Iterate the managed iterator. + fn iterate(&mut self) { + self.cur = self.iter.next(); + } + + /// Reset the managed iterator. + fn reset(&mut self) { + self.iter = self.iter_orig.clone(); + } + + /// Returns true if the current iterator has been started and has not yet + /// finished; false otherwise. + fn in_progress(&self) -> bool { + self.cur.is_some() + } +} + +impl Iterator for MultiProduct + where I: Iterator + Clone, + I::Item: Clone +{ + type Item = Vec; + + fn next(&mut self) -> Option { + if MultiProduct::iterate_last( + &mut self.0, + MultiProductIterState::StartOfIter + ) { + Some(self.curr_iterator()) + } else { + None + } + } + + fn count(self) -> usize { + if self.0.is_empty() { + return 0; + } + + if !self.in_progress() { + 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: _ }| { + let total_count = iter_orig.count(); + let cur_count = iter.count(); + acc * total_count + cur_count + } + ) + } + + fn size_hint(&self) -> (usize, Option) { + // Not ExactSizeIterator because size may be larger than usize + if self.0.is_empty() { + return (0, Some(0)); + } + + if !self.in_progress() { + return self.0.iter().fold((1, Some(1)), |acc, multi_iter| { + size_hint::mul(acc, multi_iter.iter.size_hint()) + }); + } + + self.0.iter().fold( + (0, Some(0)), + |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 { + let iter_count = self.0.len(); + + let lasts: Self::Item = self.0.into_iter() + .map(|multi_iter| multi_iter.iter.last()) + .while_some() + .collect(); + + if lasts.len() == iter_count { + Some(lasts) + } else { + None + } + } +} -- cgit v1.2.3