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