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