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