itertools/adaptors/
mod.rs

1//! Licensed under the Apache License, Version 2.0
2//! <https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
3//! <https://opensource.org/licenses/MIT>, at your
4//! option. This file may not be copied, modified, or distributed
5//! except according to those terms.
6
7mod coalesce;
8mod map;
9mod multi_product;
10pub use self::coalesce::*;
11pub use self::map::{map_into, map_ok, MapInto, MapOk};
12#[allow(deprecated)]
13pub use self::map::MapResults;
14#[cfg(feature = "use_alloc")]
15pub use self::multi_product::*;
16
17use std::fmt;
18use std::iter::{Fuse, Peekable, FromIterator, FusedIterator};
19use std::marker::PhantomData;
20use crate::size_hint;
21
22/// An iterator adaptor that alternates elements from two iterators until both
23/// run out.
24///
25/// This iterator is *fused*.
26///
27/// See [`.interleave()`](crate::Itertools::interleave) for more information.
28#[derive(Clone, Debug)]
29#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
30pub struct Interleave<I, J> {
31    a: Fuse<I>,
32    b: Fuse<J>,
33    flag: bool,
34}
35
36/// Create an iterator that interleaves elements in `i` and `j`.
37///
38/// [`IntoIterator`] enabled version of `[Itertools::interleave]`.
39pub fn interleave<I, J>(i: I, j: J) -> Interleave<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter>
40    where I: IntoIterator,
41          J: IntoIterator<Item = I::Item>
42{
43    Interleave {
44        a: i.into_iter().fuse(),
45        b: j.into_iter().fuse(),
46        flag: false,
47    }
48}
49
50impl<I, J> Iterator for Interleave<I, J>
51    where I: Iterator,
52          J: Iterator<Item = I::Item>
53{
54    type Item = I::Item;
55    #[inline]
56    fn next(&mut self) -> Option<Self::Item> {
57        self.flag = !self.flag;
58        if self.flag {
59            match self.a.next() {
60                None => self.b.next(),
61                r => r,
62            }
63        } else {
64            match self.b.next() {
65                None => self.a.next(),
66                r => r,
67            }
68        }
69    }
70
71    fn size_hint(&self) -> (usize, Option<usize>) {
72        size_hint::add(self.a.size_hint(), self.b.size_hint())
73    }
74}
75
76impl<I, J> FusedIterator for Interleave<I, J>
77    where I: Iterator,
78          J: Iterator<Item = I::Item>
79{}
80
81/// An iterator adaptor that alternates elements from the two iterators until
82/// one of them runs out.
83///
84/// This iterator is *fused*.
85///
86/// See [`.interleave_shortest()`](crate::Itertools::interleave_shortest)
87/// for more information.
88#[derive(Clone, Debug)]
89#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
90pub struct InterleaveShortest<I, J>
91    where I: Iterator,
92          J: Iterator<Item = I::Item>
93{
94    it0: I,
95    it1: J,
96    phase: bool, // false ==> it0, true ==> it1
97}
98
99/// Create a new `InterleaveShortest` iterator.
100pub fn interleave_shortest<I, J>(a: I, b: J) -> InterleaveShortest<I, J>
101    where I: Iterator,
102          J: Iterator<Item = I::Item>
103{
104    InterleaveShortest {
105        it0: a,
106        it1: b,
107        phase: false,
108    }
109}
110
111impl<I, J> Iterator for InterleaveShortest<I, J>
112    where I: Iterator,
113          J: Iterator<Item = I::Item>
114{
115    type Item = I::Item;
116
117    #[inline]
118    fn next(&mut self) -> Option<Self::Item> {
119        let e = if self.phase { self.it1.next() } else { self.it0.next() };
120        if e.is_some() {
121            self.phase = !self.phase;
122        }
123        e
124    }
125
126    #[inline]
127    fn size_hint(&self) -> (usize, Option<usize>) {
128        let (curr_hint, next_hint) = {
129            let it0_hint = self.it0.size_hint();
130            let it1_hint = self.it1.size_hint();
131            if self.phase {
132                (it1_hint, it0_hint)
133            } else {
134                (it0_hint, it1_hint)
135            }
136        };
137        let (curr_lower, curr_upper) = curr_hint;
138        let (next_lower, next_upper) = next_hint;
139        let (combined_lower, combined_upper) =
140            size_hint::mul_scalar(size_hint::min(curr_hint, next_hint), 2);
141        let lower =
142            if curr_lower > next_lower {
143                combined_lower + 1
144            } else {
145                combined_lower
146            };
147        let upper = {
148            let extra_elem = match (curr_upper, next_upper) {
149                (_, None) => false,
150                (None, Some(_)) => true,
151                (Some(curr_max), Some(next_max)) => curr_max > next_max,
152            };
153            if extra_elem {
154                combined_upper.and_then(|x| x.checked_add(1))
155            } else {
156                combined_upper
157            }
158        };
159        (lower, upper)
160    }
161}
162
163impl<I, J> FusedIterator for InterleaveShortest<I, J>
164    where I: FusedIterator,
165          J: FusedIterator<Item = I::Item>
166{}
167
168#[derive(Clone, Debug)]
169/// An iterator adaptor that allows putting back a single
170/// item to the front of the iterator.
171///
172/// Iterator element type is `I::Item`.
173pub struct PutBack<I>
174    where I: Iterator
175{
176    top: Option<I::Item>,
177    iter: I,
178}
179
180/// Create an iterator where you can put back a single item
181pub fn put_back<I>(iterable: I) -> PutBack<I::IntoIter>
182    where I: IntoIterator
183{
184    PutBack {
185        top: None,
186        iter: iterable.into_iter(),
187    }
188}
189
190impl<I> PutBack<I>
191    where I: Iterator
192{
193    /// put back value `value` (builder method)
194    pub fn with_value(mut self, value: I::Item) -> Self {
195        self.put_back(value);
196        self
197    }
198
199    /// Split the `PutBack` into its parts.
200    #[inline]
201    pub fn into_parts(self) -> (Option<I::Item>, I) {
202        let PutBack{top, iter} = self;
203        (top, iter)
204    }
205
206    /// Put back a single value to the front of the iterator.
207    ///
208    /// If a value is already in the put back slot, it is overwritten.
209    #[inline]
210    pub fn put_back(&mut self, x: I::Item) {
211        self.top = Some(x);
212    }
213}
214
215impl<I> Iterator for PutBack<I>
216    where I: Iterator
217{
218    type Item = I::Item;
219    #[inline]
220    fn next(&mut self) -> Option<Self::Item> {
221        match self.top {
222            None => self.iter.next(),
223            ref mut some => some.take(),
224        }
225    }
226    #[inline]
227    fn size_hint(&self) -> (usize, Option<usize>) {
228        // Not ExactSizeIterator because size may be larger than usize
229        size_hint::add_scalar(self.iter.size_hint(), self.top.is_some() as usize)
230    }
231
232    fn count(self) -> usize {
233        self.iter.count() + (self.top.is_some() as usize)
234    }
235
236    fn last(self) -> Option<Self::Item> {
237        self.iter.last().or(self.top)
238    }
239
240    fn nth(&mut self, n: usize) -> Option<Self::Item> {
241        match self.top {
242            None => self.iter.nth(n),
243            ref mut some => {
244                if n == 0 {
245                    some.take()
246                } else {
247                    *some = None;
248                    self.iter.nth(n - 1)
249                }
250            }
251        }
252    }
253
254    fn all<G>(&mut self, mut f: G) -> bool
255        where G: FnMut(Self::Item) -> bool
256    {
257        if let Some(elt) = self.top.take() {
258            if !f(elt) {
259                return false;
260            }
261        }
262        self.iter.all(f)
263    }
264
265    fn fold<Acc, G>(mut self, init: Acc, mut f: G) -> Acc
266        where G: FnMut(Acc, Self::Item) -> Acc,
267    {
268        let mut accum = init;
269        if let Some(elt) = self.top.take() {
270            accum = f(accum, elt);
271        }
272        self.iter.fold(accum, f)
273    }
274}
275
276#[derive(Debug, Clone)]
277/// An iterator adaptor that iterates over the cartesian product of
278/// the element sets of two iterators `I` and `J`.
279///
280/// Iterator element type is `(I::Item, J::Item)`.
281///
282/// See [`.cartesian_product()`](crate::Itertools::cartesian_product) for more information.
283#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
284pub struct Product<I, J>
285    where I: Iterator
286{
287    a: I,
288    a_cur: Option<I::Item>,
289    b: J,
290    b_orig: J,
291}
292
293/// Create a new cartesian product iterator
294///
295/// Iterator element type is `(I::Item, J::Item)`.
296pub fn cartesian_product<I, J>(mut i: I, j: J) -> Product<I, J>
297    where I: Iterator,
298          J: Clone + Iterator,
299          I::Item: Clone
300{
301    Product {
302        a_cur: i.next(),
303        a: i,
304        b: j.clone(),
305        b_orig: j,
306    }
307}
308
309impl<I, J> Iterator for Product<I, J>
310    where I: Iterator,
311          J: Clone + Iterator,
312          I::Item: Clone
313{
314    type Item = (I::Item, J::Item);
315
316    fn next(&mut self) -> Option<Self::Item> {
317        let elt_b = match self.b.next() {
318            None => {
319                self.b = self.b_orig.clone();
320                match self.b.next() {
321                    None => return None,
322                    Some(x) => {
323                        self.a_cur = self.a.next();
324                        x
325                    }
326                }
327            }
328            Some(x) => x
329        };
330        self.a_cur.as_ref().map(|a| (a.clone(), elt_b))
331    }
332
333    fn size_hint(&self) -> (usize, Option<usize>) {
334        let has_cur = self.a_cur.is_some() as usize;
335        // Not ExactSizeIterator because size may be larger than usize
336        let (b_min, b_max) = self.b.size_hint();
337
338        // Compute a * b_orig + b for both lower and upper bound
339        size_hint::add(
340            size_hint::mul(self.a.size_hint(), self.b_orig.size_hint()),
341            (b_min * has_cur, b_max.map(move |x| x * has_cur)))
342    }
343
344    fn fold<Acc, G>(mut self, mut accum: Acc, mut f: G) -> Acc
345        where G: FnMut(Acc, Self::Item) -> Acc,
346    {
347        // use a split loop to handle the loose a_cur as well as avoiding to
348        // clone b_orig at the end.
349        if let Some(mut a) = self.a_cur.take() {
350            let mut b = self.b;
351            loop {
352                accum = b.fold(accum, |acc, elt| f(acc, (a.clone(), elt)));
353
354                // we can only continue iterating a if we had a first element;
355                if let Some(next_a) = self.a.next() {
356                    b = self.b_orig.clone();
357                    a = next_a;
358                } else {
359                    break;
360                }
361            }
362        }
363        accum
364    }
365}
366
367impl<I, J> FusedIterator for Product<I, J>
368    where I: FusedIterator,
369          J: Clone + FusedIterator,
370          I::Item: Clone
371{}
372
373/// A “meta iterator adaptor”. Its closure receives a reference to the iterator
374/// and may pick off as many elements as it likes, to produce the next iterator element.
375///
376/// Iterator element type is *X*, if the return type of `F` is *Option\<X\>*.
377///
378/// See [`.batching()`](crate::Itertools::batching) for more information.
379#[derive(Clone)]
380#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
381pub struct Batching<I, F> {
382    f: F,
383    iter: I,
384}
385
386impl<I, F> fmt::Debug for Batching<I, F> where I: fmt::Debug {
387    debug_fmt_fields!(Batching, iter);
388}
389
390/// Create a new Batching iterator.
391pub fn batching<I, F>(iter: I, f: F) -> Batching<I, F> {
392    Batching { f, iter }
393}
394
395impl<B, F, I> Iterator for Batching<I, F>
396    where I: Iterator,
397          F: FnMut(&mut I) -> Option<B>
398{
399    type Item = B;
400    #[inline]
401    fn next(&mut self) -> Option<Self::Item> {
402        (self.f)(&mut self.iter)
403    }
404}
405
406/// An iterator adaptor that steps a number elements in the base iterator
407/// for each iteration.
408///
409/// The iterator steps by yielding the next element from the base iterator,
410/// then skipping forward *n-1* elements.
411///
412/// See [`.step()`](crate::Itertools::step) for more information.
413#[deprecated(note="Use std .step_by() instead", since="0.8.0")]
414#[allow(deprecated)]
415#[derive(Clone, Debug)]
416#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
417pub struct Step<I> {
418    iter: Fuse<I>,
419    skip: usize,
420}
421
422/// Create a `Step` iterator.
423///
424/// **Panics** if the step is 0.
425#[allow(deprecated)]
426pub fn step<I>(iter: I, step: usize) -> Step<I>
427    where I: Iterator
428{
429    assert!(step != 0);
430    Step {
431        iter: iter.fuse(),
432        skip: step - 1,
433    }
434}
435
436#[allow(deprecated)]
437impl<I> Iterator for Step<I>
438    where I: Iterator
439{
440    type Item = I::Item;
441    #[inline]
442    fn next(&mut self) -> Option<Self::Item> {
443        let elt = self.iter.next();
444        if self.skip > 0 {
445            self.iter.nth(self.skip - 1);
446        }
447        elt
448    }
449
450    fn size_hint(&self) -> (usize, Option<usize>) {
451        let (low, high) = self.iter.size_hint();
452        let div = |x: usize| {
453            if x == 0 {
454                0
455            } else {
456                1 + (x - 1) / (self.skip + 1)
457            }
458        };
459        (div(low), high.map(div))
460    }
461}
462
463// known size
464#[allow(deprecated)]
465impl<I> ExactSizeIterator for Step<I>
466    where I: ExactSizeIterator
467{}
468
469pub trait MergePredicate<T> {
470    fn merge_pred(&mut self, a: &T, b: &T) -> bool;
471}
472
473#[derive(Clone, Debug)]
474pub struct MergeLte;
475
476impl<T: PartialOrd> MergePredicate<T> for MergeLte {
477    fn merge_pred(&mut self, a: &T, b: &T) -> bool {
478        a <= b
479    }
480}
481
482/// An iterator adaptor that merges the two base iterators in ascending order.
483/// If both base iterators are sorted (ascending), the result is sorted.
484///
485/// Iterator element type is `I::Item`.
486///
487/// See [`.merge()`](crate::Itertools::merge_by) for more information.
488pub type Merge<I, J> = MergeBy<I, J, MergeLte>;
489
490/// Create an iterator that merges elements in `i` and `j`.
491///
492/// [`IntoIterator`] enabled version of [`Itertools::merge`](crate::Itertools::merge).
493///
494/// ```
495/// use itertools::merge;
496///
497/// for elt in merge(&[1, 2, 3], &[2, 3, 4]) {
498///     /* loop body */
499/// }
500/// ```
501pub fn merge<I, J>(i: I, j: J) -> Merge<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter>
502    where I: IntoIterator,
503          J: IntoIterator<Item = I::Item>,
504          I::Item: PartialOrd
505{
506    merge_by_new(i, j, MergeLte)
507}
508
509/// An iterator adaptor that merges the two base iterators in ascending order.
510/// If both base iterators are sorted (ascending), the result is sorted.
511///
512/// Iterator element type is `I::Item`.
513///
514/// See [`.merge_by()`](crate::Itertools::merge_by) for more information.
515#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
516pub struct MergeBy<I, J, F>
517    where I: Iterator,
518          J: Iterator<Item = I::Item>
519{
520    a: Peekable<I>,
521    b: Peekable<J>,
522    fused: Option<bool>,
523    cmp: F,
524}
525
526impl<I, J, F> fmt::Debug for MergeBy<I, J, F>
527    where I: Iterator + fmt::Debug, J: Iterator<Item = I::Item> + fmt::Debug,
528          I::Item: fmt::Debug,
529{
530    debug_fmt_fields!(MergeBy, a, b);
531}
532
533impl<T, F: FnMut(&T, &T)->bool> MergePredicate<T> for F {
534    fn merge_pred(&mut self, a: &T, b: &T) -> bool {
535        self(a, b)
536    }
537}
538
539/// Create a `MergeBy` iterator.
540pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I::IntoIter, J::IntoIter, F>
541    where I: IntoIterator,
542          J: IntoIterator<Item = I::Item>,
543          F: MergePredicate<I::Item>,
544{
545    MergeBy {
546        a: a.into_iter().peekable(),
547        b: b.into_iter().peekable(),
548        fused: None,
549        cmp,
550    }
551}
552
553impl<I, J, F> Clone for MergeBy<I, J, F>
554    where I: Iterator,
555          J: Iterator<Item = I::Item>,
556          Peekable<I>: Clone,
557          Peekable<J>: Clone,
558          F: Clone
559{
560    clone_fields!(a, b, fused, cmp);
561}
562
563impl<I, J, F> Iterator for MergeBy<I, J, F>
564    where I: Iterator,
565          J: Iterator<Item = I::Item>,
566          F: MergePredicate<I::Item>
567{
568    type Item = I::Item;
569
570    fn next(&mut self) -> Option<Self::Item> {
571        let less_than = match self.fused {
572            Some(lt) => lt,
573            None => match (self.a.peek(), self.b.peek()) {
574                (Some(a), Some(b)) => self.cmp.merge_pred(a, b),
575                (Some(_), None) => {
576                    self.fused = Some(true);
577                    true
578                }
579                (None, Some(_)) => {
580                    self.fused = Some(false);
581                    false
582                }
583                (None, None) => return None,
584            }
585        };
586        if less_than {
587            self.a.next()
588        } else {
589            self.b.next()
590        }
591    }
592
593    fn size_hint(&self) -> (usize, Option<usize>) {
594        // Not ExactSizeIterator because size may be larger than usize
595        size_hint::add(self.a.size_hint(), self.b.size_hint())
596    }
597}
598
599impl<I, J, F> FusedIterator for MergeBy<I, J, F>
600    where I: FusedIterator,
601          J: FusedIterator<Item = I::Item>,
602          F: MergePredicate<I::Item>
603{}
604
605/// An iterator adaptor that borrows from a `Clone`-able iterator
606/// to only pick off elements while the predicate returns `true`.
607///
608/// See [`.take_while_ref()`](crate::Itertools::take_while_ref) for more information.
609#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
610pub struct TakeWhileRef<'a, I: 'a, F> {
611    iter: &'a mut I,
612    f: F,
613}
614
615impl<'a, I, F> fmt::Debug for TakeWhileRef<'a, I, F>
616    where I: Iterator + fmt::Debug,
617{
618    debug_fmt_fields!(TakeWhileRef, iter);
619}
620
621/// Create a new `TakeWhileRef` from a reference to clonable iterator.
622pub fn take_while_ref<I, F>(iter: &mut I, f: F) -> TakeWhileRef<I, F>
623    where I: Iterator + Clone
624{
625    TakeWhileRef { iter, f }
626}
627
628impl<'a, I, F> Iterator for TakeWhileRef<'a, I, F>
629    where I: Iterator + Clone,
630          F: FnMut(&I::Item) -> bool
631{
632    type Item = I::Item;
633
634    fn next(&mut self) -> Option<Self::Item> {
635        let old = self.iter.clone();
636        match self.iter.next() {
637            None => None,
638            Some(elt) => {
639                if (self.f)(&elt) {
640                    Some(elt)
641                } else {
642                    *self.iter = old;
643                    None
644                }
645            }
646        }
647    }
648
649    fn size_hint(&self) -> (usize, Option<usize>) {
650        (0, self.iter.size_hint().1)
651    }
652}
653
654/// An iterator adaptor that filters `Option<A>` iterator elements
655/// and produces `A`. Stops on the first `None` encountered.
656///
657/// See [`.while_some()`](crate::Itertools::while_some) for more information.
658#[derive(Clone, Debug)]
659#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
660pub struct WhileSome<I> {
661    iter: I,
662}
663
664/// Create a new `WhileSome<I>`.
665pub fn while_some<I>(iter: I) -> WhileSome<I> {
666    WhileSome { iter }
667}
668
669impl<I, A> Iterator for WhileSome<I>
670    where I: Iterator<Item = Option<A>>
671{
672    type Item = A;
673
674    fn next(&mut self) -> Option<Self::Item> {
675        match self.iter.next() {
676            None | Some(None) => None,
677            Some(elt) => elt,
678        }
679    }
680
681    fn size_hint(&self) -> (usize, Option<usize>) {
682        (0, self.iter.size_hint().1)
683    }
684}
685
686/// An iterator to iterate through all combinations in a `Clone`-able iterator that produces tuples
687/// of a specific size.
688///
689/// See [`.tuple_combinations()`](crate::Itertools::tuple_combinations) for more
690/// information.
691#[derive(Clone, Debug)]
692#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
693pub struct TupleCombinations<I, T>
694    where I: Iterator,
695          T: HasCombination<I>
696{
697    iter: T::Combination,
698    _mi: PhantomData<I>,
699}
700
701pub trait HasCombination<I>: Sized {
702    type Combination: From<I> + Iterator<Item = Self>;
703}
704
705/// Create a new `TupleCombinations` from a clonable iterator.
706pub fn tuple_combinations<T, I>(iter: I) -> TupleCombinations<I, T>
707    where I: Iterator + Clone,
708          I::Item: Clone,
709          T: HasCombination<I>,
710{
711    TupleCombinations {
712        iter: T::Combination::from(iter),
713        _mi: PhantomData,
714    }
715}
716
717impl<I, T> Iterator for TupleCombinations<I, T>
718    where I: Iterator,
719          T: HasCombination<I>,
720{
721    type Item = T;
722
723    fn next(&mut self) -> Option<Self::Item> {
724        self.iter.next()
725    }
726}
727
728impl<I, T> FusedIterator for TupleCombinations<I, T>
729    where I: FusedIterator,
730          T: HasCombination<I>,
731{}
732
733#[derive(Clone, Debug)]
734pub struct Tuple1Combination<I> {
735    iter: I,
736}
737
738impl<I> From<I> for Tuple1Combination<I> {
739    fn from(iter: I) -> Self {
740        Tuple1Combination { iter }
741    }
742}
743
744impl<I: Iterator> Iterator for Tuple1Combination<I> {
745    type Item = (I::Item,);
746
747    fn next(&mut self) -> Option<Self::Item> {
748        self.iter.next().map(|x| (x,))
749    }
750}
751
752impl<I: Iterator> HasCombination<I> for (I::Item,) {
753    type Combination = Tuple1Combination<I>;
754}
755
756macro_rules! impl_tuple_combination {
757    ($C:ident $P:ident ; $($X:ident)*) => (
758        #[derive(Clone, Debug)]
759        pub struct $C<I: Iterator> {
760            item: Option<I::Item>,
761            iter: I,
762            c: $P<I>,
763        }
764
765        impl<I: Iterator + Clone> From<I> for $C<I> {
766            fn from(mut iter: I) -> Self {
767                Self {
768                    item: iter.next(),
769                    iter: iter.clone(),
770                    c: iter.into(),
771                }
772            }
773        }
774
775        impl<I: Iterator + Clone> From<I> for $C<Fuse<I>> {
776            fn from(iter: I) -> Self {
777                Self::from(iter.fuse())
778            }
779        }
780
781        impl<I, A> Iterator for $C<I>
782            where I: Iterator<Item = A> + Clone,
783                  I::Item: Clone
784        {
785            type Item = (A, $(ignore_ident!($X, A)),*);
786
787            fn next(&mut self) -> Option<Self::Item> {
788                if let Some(($($X),*,)) = self.c.next() {
789                    let z = self.item.clone().unwrap();
790                    Some((z, $($X),*))
791                } else {
792                    self.item = self.iter.next();
793                    self.item.clone().and_then(|z| {
794                        self.c = self.iter.clone().into();
795                        self.c.next().map(|($($X),*,)| (z, $($X),*))
796                    })
797                }
798            }
799        }
800
801        impl<I, A> HasCombination<I> for (A, $(ignore_ident!($X, A)),*)
802            where I: Iterator<Item = A> + Clone,
803                  I::Item: Clone
804        {
805            type Combination = $C<Fuse<I>>;
806        }
807    )
808}
809
810// This snippet generates the twelve `impl_tuple_combination!` invocations:
811//    use core::iter;
812//    use itertools::Itertools;
813//
814//    for i in 2..=12 {
815//        println!("impl_tuple_combination!(Tuple{arity}Combination Tuple{prev}Combination; {idents});",
816//            arity = i,
817//            prev = i - 1,
818//            idents = ('a'..'z').take(i - 1).join(" "),
819//        );
820//    }
821// It could probably be replaced by a bit more macro cleverness.
822impl_tuple_combination!(Tuple2Combination Tuple1Combination; a);
823impl_tuple_combination!(Tuple3Combination Tuple2Combination; a b);
824impl_tuple_combination!(Tuple4Combination Tuple3Combination; a b c);
825impl_tuple_combination!(Tuple5Combination Tuple4Combination; a b c d);
826impl_tuple_combination!(Tuple6Combination Tuple5Combination; a b c d e);
827impl_tuple_combination!(Tuple7Combination Tuple6Combination; a b c d e f);
828impl_tuple_combination!(Tuple8Combination Tuple7Combination; a b c d e f g);
829impl_tuple_combination!(Tuple9Combination Tuple8Combination; a b c d e f g h);
830impl_tuple_combination!(Tuple10Combination Tuple9Combination; a b c d e f g h i);
831impl_tuple_combination!(Tuple11Combination Tuple10Combination; a b c d e f g h i j);
832impl_tuple_combination!(Tuple12Combination Tuple11Combination; a b c d e f g h i j k);
833
834/// An iterator adapter to filter values within a nested `Result::Ok`.
835///
836/// See [`.filter_ok()`](crate::Itertools::filter_ok) for more information.
837#[derive(Clone)]
838#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
839pub struct FilterOk<I, F> {
840    iter: I,
841    f: F
842}
843
844impl<I, F> fmt::Debug for FilterOk<I, F>
845where
846    I: fmt::Debug,
847{
848    debug_fmt_fields!(FilterOk, iter);
849}
850
851/// Create a new `FilterOk` iterator.
852pub fn filter_ok<I, F, T, E>(iter: I, f: F) -> FilterOk<I, F>
853    where I: Iterator<Item = Result<T, E>>,
854          F: FnMut(&T) -> bool,
855{
856    FilterOk {
857        iter,
858        f,
859    }
860}
861
862impl<I, F, T, E> Iterator for FilterOk<I, F>
863    where I: Iterator<Item = Result<T, E>>,
864          F: FnMut(&T) -> bool,
865{
866    type Item = Result<T, E>;
867
868    fn next(&mut self) -> Option<Self::Item> {
869        loop {
870            match self.iter.next() {
871                Some(Ok(v)) => {
872                    if (self.f)(&v) {
873                        return Some(Ok(v));
874                    }
875                },
876                Some(Err(e)) => return Some(Err(e)),
877                None => return None,
878            }
879        }
880    }
881
882    fn size_hint(&self) -> (usize, Option<usize>) {
883        (0, self.iter.size_hint().1)
884    }
885
886    fn fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc
887        where Fold: FnMut(Acc, Self::Item) -> Acc,
888    {
889        let mut f = self.f;
890        self.iter.filter(|v| {
891            v.as_ref().map(&mut f).unwrap_or(true)
892        }).fold(init, fold_f)
893    }
894
895    fn collect<C>(self) -> C
896        where C: FromIterator<Self::Item>
897    {
898        let mut f = self.f;
899        self.iter.filter(|v| {
900            v.as_ref().map(&mut f).unwrap_or(true)
901        }).collect()
902    }
903}
904
905impl<I, F, T, E> FusedIterator for FilterOk<I, F>
906    where I: FusedIterator<Item = Result<T, E>>,
907          F: FnMut(&T) -> bool,
908{}
909
910/// An iterator adapter to filter and apply a transformation on values within a nested `Result::Ok`.
911///
912/// See [`.filter_map_ok()`](crate::Itertools::filter_map_ok) for more information.
913#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
914pub struct FilterMapOk<I, F> {
915    iter: I,
916    f: F
917}
918
919impl<I, F> fmt::Debug for FilterMapOk<I, F>
920where
921    I: fmt::Debug,
922{
923    debug_fmt_fields!(FilterMapOk, iter);
924}
925
926fn transpose_result<T, E>(result: Result<Option<T>, E>) -> Option<Result<T, E>> {
927    match result {
928        Ok(Some(v)) => Some(Ok(v)),
929        Ok(None) => None,
930        Err(e) => Some(Err(e)),
931    }
932}
933
934/// Create a new `FilterOk` iterator.
935pub fn filter_map_ok<I, F, T, U, E>(iter: I, f: F) -> FilterMapOk<I, F>
936    where I: Iterator<Item = Result<T, E>>,
937          F: FnMut(T) -> Option<U>,
938{
939    FilterMapOk {
940        iter,
941        f,
942    }
943}
944
945impl<I, F, T, U, E> Iterator for FilterMapOk<I, F>
946    where I: Iterator<Item = Result<T, E>>,
947          F: FnMut(T) -> Option<U>,
948{
949    type Item = Result<U, E>;
950
951    fn next(&mut self) -> Option<Self::Item> {
952        loop {
953            match self.iter.next() {
954                Some(Ok(v)) => {
955                    if let Some(v) = (self.f)(v) {
956                        return Some(Ok(v));
957                    }
958                },
959                Some(Err(e)) => return Some(Err(e)),
960                None => return None,
961            }
962        }
963    }
964
965    fn size_hint(&self) -> (usize, Option<usize>) {
966        (0, self.iter.size_hint().1)
967    }
968
969    fn fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc
970        where Fold: FnMut(Acc, Self::Item) -> Acc,
971    {
972        let mut f = self.f;
973        self.iter.filter_map(|v| {
974            transpose_result(v.map(&mut f))
975        }).fold(init, fold_f)
976    }
977
978    fn collect<C>(self) -> C
979        where C: FromIterator<Self::Item>
980    {
981        let mut f = self.f;
982        self.iter.filter_map(|v| {
983            transpose_result(v.map(&mut f))
984        }).collect()
985    }
986}
987
988impl<I, F, T, U, E> FusedIterator for FilterMapOk<I, F>
989    where I: FusedIterator<Item = Result<T, E>>,
990          F: FnMut(T) -> Option<U>,
991{}
992
993/// An iterator adapter to get the positions of each element that matches a predicate.
994///
995/// See [`.positions()`](crate::Itertools::positions) for more information.
996#[derive(Clone)]
997#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
998pub struct Positions<I, F> {
999    iter: I,
1000    f: F,
1001    count: usize,
1002}
1003
1004impl<I, F> fmt::Debug for Positions<I, F>
1005where
1006    I: fmt::Debug,
1007{
1008    debug_fmt_fields!(Positions, iter, count);
1009}
1010
1011/// Create a new `Positions` iterator.
1012pub fn positions<I, F>(iter: I, f: F) -> Positions<I, F>
1013    where I: Iterator,
1014          F: FnMut(I::Item) -> bool,
1015{
1016    Positions {
1017        iter,
1018        f,
1019        count: 0
1020    }
1021}
1022
1023impl<I, F> Iterator for Positions<I, F>
1024    where I: Iterator,
1025          F: FnMut(I::Item) -> bool,
1026{
1027    type Item = usize;
1028
1029    fn next(&mut self) -> Option<Self::Item> {
1030        while let Some(v) = self.iter.next() {
1031            let i = self.count;
1032            self.count = i + 1;
1033            if (self.f)(v) {
1034                return Some(i);
1035            }
1036        }
1037        None
1038    }
1039
1040    fn size_hint(&self) -> (usize, Option<usize>) {
1041        (0, self.iter.size_hint().1)
1042    }
1043}
1044
1045impl<I, F> DoubleEndedIterator for Positions<I, F>
1046    where I: DoubleEndedIterator + ExactSizeIterator,
1047          F: FnMut(I::Item) -> bool,
1048{
1049    fn next_back(&mut self) -> Option<Self::Item> {
1050        while let Some(v) = self.iter.next_back() {
1051            if (self.f)(v) {
1052                return Some(self.count + self.iter.len())
1053            }
1054        }
1055        None
1056    }
1057}
1058
1059impl<I, F> FusedIterator for Positions<I, F>
1060    where I: FusedIterator,
1061          F: FnMut(I::Item) -> bool,
1062{}
1063
1064/// An iterator adapter to apply a mutating function to each element before yielding it.
1065///
1066/// See [`.update()`](crate::Itertools::update) for more information.
1067#[derive(Clone)]
1068#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1069pub struct Update<I, F> {
1070    iter: I,
1071    f: F,
1072}
1073
1074impl<I, F> fmt::Debug for Update<I, F>
1075where
1076    I: fmt::Debug,
1077{
1078    debug_fmt_fields!(Update, iter);
1079}
1080
1081/// Create a new `Update` iterator.
1082pub fn update<I, F>(iter: I, f: F) -> Update<I, F>
1083where
1084    I: Iterator,
1085    F: FnMut(&mut I::Item),
1086{
1087    Update { iter, f }
1088}
1089
1090impl<I, F> Iterator for Update<I, F>
1091where
1092    I: Iterator,
1093    F: FnMut(&mut I::Item),
1094{
1095    type Item = I::Item;
1096
1097    fn next(&mut self) -> Option<Self::Item> {
1098        if let Some(mut v) = self.iter.next() {
1099            (self.f)(&mut v);
1100            Some(v)
1101        } else {
1102            None
1103        }
1104    }
1105
1106    fn size_hint(&self) -> (usize, Option<usize>) {
1107        self.iter.size_hint()
1108    }
1109
1110    fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc
1111        where G: FnMut(Acc, Self::Item) -> Acc,
1112    {
1113        let mut f = self.f;
1114        self.iter.fold(init, move |acc, mut v| { f(&mut v); g(acc, v) })
1115    }
1116
1117    // if possible, re-use inner iterator specializations in collect
1118    fn collect<C>(self) -> C
1119        where C: FromIterator<Self::Item>
1120    {
1121        let mut f = self.f;
1122        self.iter.map(move |mut v| { f(&mut v); v }).collect()
1123    }
1124}
1125
1126impl<I, F> ExactSizeIterator for Update<I, F>
1127where
1128    I: ExactSizeIterator,
1129    F: FnMut(&mut I::Item),
1130{}
1131
1132impl<I, F> DoubleEndedIterator for Update<I, F>
1133where
1134    I: DoubleEndedIterator,
1135    F: FnMut(&mut I::Item),
1136{
1137    fn next_back(&mut self) -> Option<Self::Item> {
1138        if let Some(mut v) = self.iter.next_back() {
1139            (self.f)(&mut v);
1140            Some(v)
1141        } else {
1142            None
1143        }
1144    }
1145}
1146
1147impl<I, F> FusedIterator for Update<I, F>
1148where
1149    I: FusedIterator,
1150    F: FnMut(&mut I::Item),
1151{}
itertools/adaptors/mod.rs

itertools/adaptors/
mod.rs
