diff options
Diffstat (limited to 'third_party/rust/itertools-0.8.0/src/adaptors/mod.rs')
| -rw-r--r-- | third_party/rust/itertools-0.8.0/src/adaptors/mod.rs | 1278 |
1 files changed, 1278 insertions, 0 deletions
diff --git a/third_party/rust/itertools-0.8.0/src/adaptors/mod.rs b/third_party/rust/itertools-0.8.0/src/adaptors/mod.rs new file mode 100644 index 0000000000..59aebfaf06 --- /dev/null +++ b/third_party/rust/itertools-0.8.0/src/adaptors/mod.rs @@ -0,0 +1,1278 @@ +//! Licensed under the Apache License, Version 2.0 +//! http://www.apache.org/licenses/LICENSE-2.0 or the MIT license +//! http://opensource.org/licenses/MIT, at your +//! option. This file may not be copied, modified, or distributed +//! except according to those terms. + +mod multi_product; +#[cfg(feature = "use_std")] +pub use self::multi_product::*; + +use std::fmt; +use std::mem::replace; +use std::iter::{Fuse, Peekable, FromIterator}; +use std::marker::PhantomData; +use size_hint; + +macro_rules! clone_fields { + ($name:ident, $base:expr, $($field:ident),+) => ( + $name { + $( + $field : $base . $field .clone() + ),* + } + ); +} + +/// An iterator adaptor that alternates elements from two iterators until both +/// run out. +/// +/// This iterator is *fused*. +/// +/// See [`.interleave()`](../trait.Itertools.html#method.interleave) for more information. +#[derive(Clone, Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Interleave<I, J> { + a: Fuse<I>, + b: Fuse<J>, + flag: bool, +} + +/// Create an iterator that interleaves elements in `i` and `j`. +/// +/// `IntoIterator` enabled version of `i.interleave(j)`. +/// +/// ``` +/// use itertools::interleave; +/// +/// for elt in interleave(&[1, 2, 3], &[2, 3, 4]) { +/// /* loop body */ +/// } +/// ``` +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(), + b: j.into_iter().fuse(), + flag: false, + } +} + +impl<I, J> Iterator for Interleave<I, J> + where I: Iterator, + J: Iterator<Item = I::Item> +{ + type Item = I::Item; + #[inline] + fn next(&mut self) -> Option<I::Item> { + 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<usize>) { + size_hint::add(self.a.size_hint(), self.b.size_hint()) + } +} + +/// An iterator adaptor that alternates elements from the two iterators until +/// one of them runs out. +/// +/// This iterator is *fused*. +/// +/// See [`.interleave_shortest()`](../trait.Itertools.html#method.interleave_shortest) +/// for more information. +#[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> +{ + it0: I, + it1: J, + phase: bool, // false ==> it0, true ==> it1 +} + +/// 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> +{ + InterleaveShortest { + it0: a, + it1: b, + phase: false, + } +} + +impl<I, J> Iterator for InterleaveShortest<I, J> + where I: Iterator, + J: Iterator<Item = I::Item> +{ + type Item = I::Item; + + #[inline] + fn next(&mut self) -> Option<I::Item> { + match self.phase { + false => match self.it0.next() { + None => None, + e => { + self.phase = true; + e + } + }, + true => match self.it1.next() { + None => None, + e => { + self.phase = false; + e + } + }, + } + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + 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) + } +} + +#[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<I> + where I: Iterator +{ + top: Option<I::Item>, + iter: 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 +{ + PutBack { + top: None, + iter: iterable.into_iter(), + } +} + +impl<I> PutBack<I> + 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::Item>, 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<I> Iterator for PutBack<I> + where I: Iterator +{ + type Item = I::Item; + #[inline] + fn next(&mut self) -> Option<I::Item> { + match self.top { + None => self.iter.next(), + ref mut some => some.take(), + } + } + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + // Not ExactSizeIterator because size may be larger than usize + size_hint::add_scalar(self.iter.size_hint(), self.top.is_some() as usize) + } + + fn all<G>(&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<Acc, G>(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()`](../trait.Itertools.html#method.cartesian_product) for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Product<I, J> + where I: Iterator +{ + a: I, + a_cur: Option<I::Item>, + b: J, + b_orig: 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 +{ + Product { + a_cur: i.next(), + a: i, + b: j.clone(), + b_orig: j, + } +} + + +impl<I, J> Iterator for Product<I, J> + where I: Iterator, + J: Clone + Iterator, + I::Item: Clone +{ + type Item = (I::Item, J::Item); + fn next(&mut self) -> Option<(I::Item, J::Item)> { + 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 + }; + match self.a_cur { + None => None, + Some(ref a) => { + Some((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))) + } + + fn fold<Acc, G>(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 + } +} + +/// 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\<X\>*. +/// +/// See [`.batching()`](../trait.Itertools.html#method.batching) for more information. +#[derive(Clone)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Batching<I, F> { + f: F, + iter: I, +} + +impl<I, F> fmt::Debug for Batching<I, F> where I: fmt::Debug { + debug_fmt_fields!(Batching, iter); +} + +/// Create a new Batching iterator. +pub fn batching<I, F>(iter: I, f: F) -> Batching<I, F> { + Batching { f: f, iter: iter } +} + +impl<B, F, I> Iterator for Batching<I, F> + where I: Iterator, + F: FnMut(&mut I) -> Option<B> +{ + type Item = B; + #[inline] + fn next(&mut self) -> Option<B> { + (self.f)(&mut self.iter) + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + // No information about closue behavior + (0, None) + } +} + +/// 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()`](../trait.Itertools.html#method.step) for more information. +#[deprecated(note="Use std .step_by() instead", since="0.8")] +#[allow(deprecated)] +#[derive(Clone, Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Step<I> { + iter: Fuse<I>, + skip: usize, +} + +/// Create a `Step` iterator. +/// +/// **Panics** if the step is 0. +#[allow(deprecated)] +pub fn step<I>(iter: I, step: usize) -> Step<I> + where I: Iterator +{ + assert!(step != 0); + Step { + iter: iter.fuse(), + skip: step - 1, + } +} + +#[allow(deprecated)] +impl<I> Iterator for Step<I> + where I: Iterator +{ + type Item = I::Item; + #[inline] + fn next(&mut self) -> Option<I::Item> { + let elt = self.iter.next(); + if self.skip > 0 { + self.iter.nth(self.skip - 1); + } + elt + } + + fn size_hint(&self) -> (usize, Option<usize>) { + 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<I> ExactSizeIterator for Step<I> + where I: ExactSizeIterator +{} + + +struct MergeCore<I, J> + where I: Iterator, + J: Iterator<Item = I::Item> +{ + a: Peekable<I>, + b: Peekable<J>, + fused: Option<bool>, +} + + +impl<I, J> Clone for MergeCore<I, J> + where I: Iterator, + J: Iterator<Item = I::Item>, + Peekable<I>: Clone, + Peekable<J>: Clone +{ + fn clone(&self) -> Self { + clone_fields!(MergeCore, self, a, b, fused) + } +} + +impl<I, J> MergeCore<I, J> + where I: Iterator, + J: Iterator<Item = I::Item> +{ + fn next_with<F>(&mut self, mut less_than: F) -> Option<I::Item> + where F: FnMut(&I::Item, &I::Item) -> bool + { + let less_than = match self.fused { + Some(lt) => lt, + None => match (self.a.peek(), self.b.peek()) { + (Some(a), Some(b)) => less_than(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()) + } +} + +/// 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()`](../trait.Itertools.html#method.merge_by) for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Merge<I, J> + where I: Iterator, + J: Iterator<Item = I::Item> +{ + merge: MergeCore<I, J>, +} + +impl<I, J> Clone for Merge<I, J> + where I: Iterator, + J: Iterator<Item = I::Item>, + Peekable<I>: Clone, + Peekable<J>: Clone +{ + fn clone(&self) -> Self { + clone_fields!(Merge, self, merge) + } +} + +impl<I, J> fmt::Debug for Merge<I, J> + where I: Iterator + fmt::Debug, J: Iterator<Item = I::Item> + fmt::Debug, + I::Item: fmt::Debug, +{ + debug_fmt_fields!(Merge, merge.a, merge.b); +} + +/// Create an iterator that merges elements in `i` and `j`. +/// +/// `IntoIterator` enabled version of `i.merge(j)`. +/// +/// ``` +/// 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 { + merge: MergeCore { + a: i.into_iter().peekable(), + b: j.into_iter().peekable(), + fused: None, + }, + } +} + +impl<I, J> Iterator for Merge<I, J> + where I: Iterator, + J: Iterator<Item = I::Item>, + I::Item: PartialOrd +{ + type Item = I::Item; + + fn next(&mut self) -> Option<I::Item> { + self.merge.next_with(|a, b| a <= b) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.merge.size_hint() + } +} + +/// 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()`](../trait.Itertools.html#method.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> +{ + merge: MergeCore<I, J>, + 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, merge.a, merge.b); +} + +/// Create a `MergeBy` iterator. +pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I, J, F> + where I: Iterator, + J: Iterator<Item = I::Item> +{ + MergeBy { + merge: MergeCore { + a: a.peekable(), + b: b.peekable(), + fused: None, + }, + cmp: 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 +{ + fn clone(&self) -> Self { + clone_fields!(MergeBy, self, merge, cmp) + } +} + +impl<I, J, F> Iterator for MergeBy<I, J, F> + where I: Iterator, + J: Iterator<Item = I::Item>, + F: FnMut(&I::Item, &I::Item) -> bool +{ + type Item = I::Item; + + fn next(&mut self) -> Option<I::Item> { + self.merge.next_with(&mut self.cmp) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.merge.size_hint() + } +} + +#[derive(Clone, Debug)] +pub struct CoalesceCore<I> + where I: Iterator +{ + iter: I, + last: Option<I::Item>, +} + +impl<I> CoalesceCore<I> + where I: Iterator +{ + fn next_with<F>(&mut self, mut f: F) -> Option<I::Item> + where F: FnMut(I::Item, I::Item) -> Result<I::Item, (I::Item, I::Item)> + { + // this fuses the iterator + let mut last = match self.last.take() { + None => return None, + Some(x) => x, + }; + for next in &mut self.iter { + match f(last, next) { + Ok(joined) => last = joined, + Err((last_, next_)) => { + self.last = Some(next_); + return Some(last_); + } + } + } + + Some(last) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let (low, hi) = size_hint::add_scalar(self.iter.size_hint(), + self.last.is_some() as usize); + ((low > 0) as usize, hi) + } +} + +/// An iterator adaptor that may join together adjacent elements. +/// +/// See [`.coalesce()`](../trait.Itertools.html#method.coalesce) for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Coalesce<I, F> + where I: Iterator +{ + iter: CoalesceCore<I>, + f: F, +} + +impl<I: Clone, F: Clone> Clone for Coalesce<I, F> + where I: Iterator, + I::Item: Clone +{ + fn clone(&self) -> Self { + clone_fields!(Coalesce, self, iter, f) + } +} + +impl<I, F> fmt::Debug for Coalesce<I, F> + where I: Iterator + fmt::Debug, + I::Item: fmt::Debug, +{ + debug_fmt_fields!(Coalesce, iter); +} + +/// Create a new `Coalesce`. +pub fn coalesce<I, F>(mut iter: I, f: F) -> Coalesce<I, F> + where I: Iterator +{ + Coalesce { + iter: CoalesceCore { + last: iter.next(), + iter: iter, + }, + f: f, + } +} + +impl<I, F> Iterator for Coalesce<I, F> + where I: Iterator, + F: FnMut(I::Item, I::Item) -> Result<I::Item, (I::Item, I::Item)> +{ + type Item = I::Item; + + fn next(&mut self) -> Option<I::Item> { + self.iter.next_with(&mut self.f) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +/// An iterator adaptor that removes repeated duplicates. +/// +/// See [`.dedup()`](../trait.Itertools.html#method.dedup) for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Dedup<I> + where I: Iterator +{ + iter: CoalesceCore<I>, +} + +impl<I: Clone> Clone for Dedup<I> + where I: Iterator, + I::Item: Clone +{ + fn clone(&self) -> Self { + clone_fields!(Dedup, self, iter) + } +} + +/// Create a new `Dedup`. +pub fn dedup<I>(mut iter: I) -> Dedup<I> + where I: Iterator +{ + Dedup { + iter: CoalesceCore { + last: iter.next(), + iter: iter, + }, + } +} + +impl<I> fmt::Debug for Dedup<I> + where I: Iterator + fmt::Debug, + I::Item: fmt::Debug, +{ + debug_fmt_fields!(Dedup, iter); +} + +impl<I> Iterator for Dedup<I> + where I: Iterator, + I::Item: PartialEq +{ + type Item = I::Item; + + fn next(&mut self) -> Option<I::Item> { + self.iter.next_with(|x, y| { + if x == y { Ok(x) } else { Err((x, y)) } + }) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } + + fn fold<Acc, G>(self, mut accum: Acc, mut f: G) -> Acc + where G: FnMut(Acc, Self::Item) -> Acc, + { + if let Some(mut last) = self.iter.last { + accum = self.iter.iter.fold(accum, |acc, elt| { + if elt == last { + acc + } else { + f(acc, replace(&mut last, elt)) + } + }); + f(accum, last) + } else { + accum + } + } +} + +/// An iterator adaptor that borrows from a `Clone`-able iterator +/// to only pick off elements while the predicate returns `true`. +/// +/// See [`.take_while_ref()`](../trait.Itertools.html#method.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<I, F>(iter: &mut I, f: F) -> TakeWhileRef<I, F> + where I: Iterator + Clone +{ + TakeWhileRef { iter: iter, f: 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<I::Item> { + 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<usize>) { + let (_, hi) = self.iter.size_hint(); + (0, hi) + } +} + +/// An iterator adaptor that filters `Option<A>` iterator elements +/// and produces `A`. Stops on the first `None` encountered. +/// +/// See [`.while_some()`](../trait.Itertools.html#method.while_some) for more information. +#[derive(Clone, Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct WhileSome<I> { + iter: I, +} + +/// Create a new `WhileSome<I>`. +pub fn while_some<I>(iter: I) -> WhileSome<I> { + WhileSome { iter: iter } +} + +impl<I, A> Iterator for WhileSome<I> + where I: Iterator<Item = Option<A>> +{ + type Item = A; + + fn next(&mut self) -> Option<A> { + match self.iter.next() { + None | Some(None) => None, + Some(elt) => elt, + } + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let sh = self.iter.size_hint(); + (0, sh.1) + } +} + +/// An iterator to iterate through all combinations in a `Clone`-able iterator that produces tuples +/// of a specific size. +/// +/// See [`.tuple_combinations()`](../trait.Itertools.html#method.tuple_combinations) for more +/// information. +#[derive(Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct TupleCombinations<I, T> + where I: Iterator, + T: HasCombination<I> +{ + iter: T::Combination, + _mi: PhantomData<I>, + _mt: PhantomData<T> +} + +pub trait HasCombination<I>: Sized { + type Combination: From<I> + Iterator<Item = Self>; +} + +/// 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>, +{ + TupleCombinations { + iter: T::Combination::from(iter), + _mi: PhantomData, + _mt: PhantomData, + } +} + +impl<I, T> Iterator for TupleCombinations<I, T> + where I: Iterator, + T: HasCombination<I>, +{ + type Item = T; + + fn next(&mut self) -> Option<Self::Item> { + self.iter.next() + } +} + +#[derive(Debug)] +pub struct Tuple1Combination<I> { + iter: I, +} + +impl<I> From<I> for Tuple1Combination<I> { + fn from(iter: I) -> Self { + Tuple1Combination { iter: iter } + } +} + +impl<I: Iterator> Iterator for Tuple1Combination<I> { + type Item = (I::Item,); + + fn next(&mut self) -> Option<Self::Item> { + self.iter.next().map(|x| (x,)) + } +} + +impl<I: Iterator> HasCombination<I> for (I::Item,) { + type Combination = Tuple1Combination<I>; +} + +macro_rules! impl_tuple_combination { + ($C:ident $P:ident ; $A:ident, $($I:ident),* ; $($X:ident)*) => ( + #[derive(Debug)] + pub struct $C<I: Iterator> { + item: Option<I::Item>, + iter: I, + c: $P<I>, + } + + impl<I: Iterator + Clone> From<I> for $C<I> { + fn from(mut iter: I) -> Self { + $C { + item: iter.next(), + iter: iter.clone(), + c: $P::from(iter), + } + } + } + + impl<I: Iterator + Clone> From<I> for $C<Fuse<I>> { + fn from(iter: I) -> Self { + let mut iter = iter.fuse(); + $C { + item: iter.next(), + iter: iter.clone(), + c: $P::from(iter), + } + } + } + + impl<I, $A> Iterator for $C<I> + where I: Iterator<Item = $A> + Clone, + I::Item: Clone + { + type Item = ($($I),*); + + fn next(&mut self) -> Option<Self::Item> { + 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 = $P::from(self.iter.clone()); + self.c.next().map(|($($X),*,)| (z, $($X),*)) + }) + } + } + } + + impl<I, $A> HasCombination<I> for ($($I),*) + where I: Iterator<Item = $A> + Clone, + I::Item: Clone + { + type Combination = $C<Fuse<I>>; + } + ) +} + +impl_tuple_combination!(Tuple2Combination Tuple1Combination ; A, A, A ; a); +impl_tuple_combination!(Tuple3Combination Tuple2Combination ; A, A, A, A ; a b); +impl_tuple_combination!(Tuple4Combination Tuple3Combination ; A, A, A, A, A; a b c); + +/// An iterator adapter to apply `Into` conversion to each element. +/// +/// See [`.map_into()`](../trait.Itertools.html#method.map_into) for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct MapInto<I, R> { + iter: I, + _res: PhantomData<fn() -> R>, +} + +/// Create a new [`MapInto`](struct.MapInto.html) iterator. +pub fn map_into<I, R>(iter: I) -> MapInto<I, R> { + MapInto { + iter: iter, + _res: PhantomData, + } +} + +impl<I, R> Iterator for MapInto<I, R> + where I: Iterator, + I::Item: Into<R>, +{ + type Item = R; + + fn next(&mut self) -> Option<R> { + self.iter + .next() + .map(|i| i.into()) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } + + fn fold<Acc, Fold>(self, init: Acc, mut fold_f: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + self.iter.fold(init, move |acc, v| fold_f(acc, v.into())) + } +} + +impl<I, R> DoubleEndedIterator for MapInto<I, R> + where I: DoubleEndedIterator, + I::Item: Into<R>, +{ + fn next_back(&mut self) -> Option<Self::Item> { + self.iter + .next_back() + .map(|i| i.into()) + } +} + +impl<I, R> ExactSizeIterator for MapInto<I, R> +where + I: ExactSizeIterator, + I::Item: Into<R>, +{} + +/// An iterator adapter to apply a transformation within a nested `Result`. +/// +/// See [`.map_results()`](../trait.Itertools.html#method.map_results) for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct MapResults<I, F> { + iter: I, + f: F +} + +/// Create a new `MapResults` iterator. +pub fn map_results<I, F, T, U, E>(iter: I, f: F) -> MapResults<I, F> + where I: Iterator<Item = Result<T, E>>, + F: FnMut(T) -> U, +{ + MapResults { + iter: iter, + f: f, + } +} + +impl<I, F, T, U, E> Iterator for MapResults<I, F> + where I: Iterator<Item = Result<T, E>>, + F: FnMut(T) -> U, +{ + type Item = Result<U, E>; + + fn next(&mut self) -> Option<Self::Item> { + self.iter.next().map(|v| v.map(&mut self.f)) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } + + fn fold<Acc, 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, v.map(&mut f))) + } + + fn collect<C>(self) -> C + where C: FromIterator<Self::Item> + { + let mut f = self.f; + self.iter.map(move |v| v.map(&mut f)).collect() + } +} + +/// An iterator adapter to get the positions of each element that matches a predicate. +/// +/// See [`.positions()`](../trait.Itertools.html#method.positions) for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Positions<I, F> { + iter: I, + f: F, + count: usize, +} + +/// 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, +{ + Positions { + iter: iter, + f: f, + count: 0 + } +} + +impl<I, F> Iterator for Positions<I, F> + where I: Iterator, + F: FnMut(I::Item) -> bool, +{ + type Item = usize; + + fn next(&mut self) -> Option<Self::Item> { + 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<usize>) { + (0, self.iter.size_hint().1) + } +} + +impl<I, F> DoubleEndedIterator for Positions<I, F> + 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()) + } + } + None + } +} + +/// An iterator adapter to apply a mutating function to each element before yielding it. +/// +/// See [`.update()`](../trait.Itertools.html#method.update) for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Update<I, F> { + iter: I, + f: F, +} + +/// Create a new `Update` iterator. +pub fn update<I, F>(iter: I, f: F) -> Update<I, F> +where + I: Iterator, + F: FnMut(&mut I::Item), +{ + Update { iter: iter, f: f } +} + +impl<I, F> Iterator for Update<I, F> +where + I: Iterator, + F: FnMut(&mut I::Item), +{ + type Item = I::Item; + + fn next(&mut self) -> Option<Self::Item> { + if let Some(mut v) = self.iter.next() { + (self.f)(&mut v); + Some(v) + } else { + None + } + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } + + fn fold<Acc, G>(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<C>(self) -> C + where C: FromIterator<Self::Item> + { + let mut f = self.f; + self.iter.map(move |mut v| { f(&mut v); v }).collect() + } +} + +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 + I: DoubleEndedIterator, + F: FnMut(&mut I::Item), +{ + fn next_back(&mut self) -> Option<Self::Item> { + if let Some(mut v) = self.iter.next_back() { + (self.f)(&mut v); + Some(v) + } else { + None + } + } +} |