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)]
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 /// 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,853 pub fn filter_ok<I, F, T, E>(iter: I, f: F) -> FilterOk<I, F>
854 where I: Iterator<Item = Result<T, E>>,
855 F: FnMut(&T) -> bool,
856 {
857 FilterOk {
858 iter,
859 f,
860 }
861 }
862
863 impl<I, F, T, E> Iterator for FilterOk<I, F>
864 where I: Iterator<Item = Result<T, E>>,
865 F: FnMut(&T) -> bool,
866 {
867 type Item = Result<T, E>;
868
next(&mut self) -> Option<Self::Item>869 fn next(&mut self) -> Option<Self::Item> {
870 loop {
871 match self.iter.next() {
872 Some(Ok(v)) => {
873 if (self.f)(&v) {
874 return Some(Ok(v));
875 }
876 },
877 Some(Err(e)) => return Some(Err(e)),
878 None => return None,
879 }
880 }
881 }
882
size_hint(&self) -> (usize, Option<usize>)883 fn size_hint(&self) -> (usize, Option<usize>) {
884 (0, self.iter.size_hint().1)
885 }
886
fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc where Fold: FnMut(Acc, Self::Item) -> Acc,887 fn fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc
888 where Fold: FnMut(Acc, Self::Item) -> Acc,
889 {
890 let mut f = self.f;
891 self.iter.filter(|v| {
892 v.as_ref().map(&mut f).unwrap_or(true)
893 }).fold(init, fold_f)
894 }
895
collect<C>(self) -> C where C: FromIterator<Self::Item>896 fn collect<C>(self) -> C
897 where C: FromIterator<Self::Item>
898 {
899 let mut f = self.f;
900 self.iter.filter(|v| {
901 v.as_ref().map(&mut f).unwrap_or(true)
902 }).collect()
903 }
904 }
905
906 impl<I, F, T, E> FusedIterator for FilterOk<I, F>
907 where I: FusedIterator<Item = Result<T, E>>,
908 F: FnMut(&T) -> bool,
909 {}
910
911 /// An iterator adapter to filter and apply a transformation on values within a nested `Result::Ok`.
912 ///
913 /// See [`.filter_map_ok()`](crate::Itertools::filter_map_ok) for more information.
914 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
915 pub struct FilterMapOk<I, F> {
916 iter: I,
917 f: F
918 }
919
transpose_result<T, E>(result: Result<Option<T>, E>) -> Option<Result<T, E>>920 fn transpose_result<T, E>(result: Result<Option<T>, E>) -> Option<Result<T, E>> {
921 match result {
922 Ok(Some(v)) => Some(Ok(v)),
923 Ok(None) => None,
924 Err(e) => Some(Err(e)),
925 }
926 }
927
928 /// 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>,929 pub fn filter_map_ok<I, F, T, U, E>(iter: I, f: F) -> FilterMapOk<I, F>
930 where I: Iterator<Item = Result<T, E>>,
931 F: FnMut(T) -> Option<U>,
932 {
933 FilterMapOk {
934 iter,
935 f,
936 }
937 }
938
939 impl<I, F, T, U, E> Iterator for FilterMapOk<I, F>
940 where I: Iterator<Item = Result<T, E>>,
941 F: FnMut(T) -> Option<U>,
942 {
943 type Item = Result<U, E>;
944
next(&mut self) -> Option<Self::Item>945 fn next(&mut self) -> Option<Self::Item> {
946 loop {
947 match self.iter.next() {
948 Some(Ok(v)) => {
949 if let Some(v) = (self.f)(v) {
950 return Some(Ok(v));
951 }
952 },
953 Some(Err(e)) => return Some(Err(e)),
954 None => return None,
955 }
956 }
957 }
958
size_hint(&self) -> (usize, Option<usize>)959 fn size_hint(&self) -> (usize, Option<usize>) {
960 (0, self.iter.size_hint().1)
961 }
962
fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc where Fold: FnMut(Acc, Self::Item) -> Acc,963 fn fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc
964 where Fold: FnMut(Acc, Self::Item) -> Acc,
965 {
966 let mut f = self.f;
967 self.iter.filter_map(|v| {
968 transpose_result(v.map(&mut f))
969 }).fold(init, fold_f)
970 }
971
collect<C>(self) -> C where C: FromIterator<Self::Item>972 fn collect<C>(self) -> C
973 where C: FromIterator<Self::Item>
974 {
975 let mut f = self.f;
976 self.iter.filter_map(|v| {
977 transpose_result(v.map(&mut f))
978 }).collect()
979 }
980 }
981
982 impl<I, F, T, U, E> FusedIterator for FilterMapOk<I, F>
983 where I: FusedIterator<Item = Result<T, E>>,
984 F: FnMut(T) -> Option<U>,
985 {}
986
987 /// An iterator adapter to get the positions of each element that matches a predicate.
988 ///
989 /// See [`.positions()`](crate::Itertools::positions) for more information.
990 #[derive(Clone)]
991 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
992 pub struct Positions<I, F> {
993 iter: I,
994 f: F,
995 count: usize,
996 }
997
998 /// Create a new `Positions` iterator.
positions<I, F>(iter: I, f: F) -> Positions<I, F> where I: Iterator, F: FnMut(I::Item) -> bool,999 pub fn positions<I, F>(iter: I, f: F) -> Positions<I, F>
1000 where I: Iterator,
1001 F: FnMut(I::Item) -> bool,
1002 {
1003 Positions {
1004 iter,
1005 f,
1006 count: 0
1007 }
1008 }
1009
1010 impl<I, F> Iterator for Positions<I, F>
1011 where I: Iterator,
1012 F: FnMut(I::Item) -> bool,
1013 {
1014 type Item = usize;
1015
next(&mut self) -> Option<Self::Item>1016 fn next(&mut self) -> Option<Self::Item> {
1017 while let Some(v) = self.iter.next() {
1018 let i = self.count;
1019 self.count = i + 1;
1020 if (self.f)(v) {
1021 return Some(i);
1022 }
1023 }
1024 None
1025 }
1026
size_hint(&self) -> (usize, Option<usize>)1027 fn size_hint(&self) -> (usize, Option<usize>) {
1028 (0, self.iter.size_hint().1)
1029 }
1030 }
1031
1032 impl<I, F> DoubleEndedIterator for Positions<I, F>
1033 where I: DoubleEndedIterator + ExactSizeIterator,
1034 F: FnMut(I::Item) -> bool,
1035 {
next_back(&mut self) -> Option<Self::Item>1036 fn next_back(&mut self) -> Option<Self::Item> {
1037 while let Some(v) = self.iter.next_back() {
1038 if (self.f)(v) {
1039 return Some(self.count + self.iter.len())
1040 }
1041 }
1042 None
1043 }
1044 }
1045
1046 impl<I, F> FusedIterator for Positions<I, F>
1047 where I: FusedIterator,
1048 F: FnMut(I::Item) -> bool,
1049 {}
1050
1051 /// An iterator adapter to apply a mutating function to each element before yielding it.
1052 ///
1053 /// See [`.update()`](crate::Itertools::update) for more information.
1054 #[derive(Clone)]
1055 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1056 pub struct Update<I, F> {
1057 iter: I,
1058 f: F,
1059 }
1060
1061 /// Create a new `Update` iterator.
update<I, F>(iter: I, f: F) -> Update<I, F> where I: Iterator, F: FnMut(&mut I::Item),1062 pub fn update<I, F>(iter: I, f: F) -> Update<I, F>
1063 where
1064 I: Iterator,
1065 F: FnMut(&mut I::Item),
1066 {
1067 Update { iter, f }
1068 }
1069
1070 impl<I, F> Iterator for Update<I, F>
1071 where
1072 I: Iterator,
1073 F: FnMut(&mut I::Item),
1074 {
1075 type Item = I::Item;
1076
next(&mut self) -> Option<Self::Item>1077 fn next(&mut self) -> Option<Self::Item> {
1078 if let Some(mut v) = self.iter.next() {
1079 (self.f)(&mut v);
1080 Some(v)
1081 } else {
1082 None
1083 }
1084 }
1085
size_hint(&self) -> (usize, Option<usize>)1086 fn size_hint(&self) -> (usize, Option<usize>) {
1087 self.iter.size_hint()
1088 }
1089
fold<Acc, G>(self, init: Acc, mut g: G) -> Acc where G: FnMut(Acc, Self::Item) -> Acc,1090 fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc
1091 where G: FnMut(Acc, Self::Item) -> Acc,
1092 {
1093 let mut f = self.f;
1094 self.iter.fold(init, move |acc, mut v| { f(&mut v); g(acc, v) })
1095 }
1096
1097 // if possible, re-use inner iterator specializations in collect
collect<C>(self) -> C where C: FromIterator<Self::Item>1098 fn collect<C>(self) -> C
1099 where C: FromIterator<Self::Item>
1100 {
1101 let mut f = self.f;
1102 self.iter.map(move |mut v| { f(&mut v); v }).collect()
1103 }
1104 }
1105
1106 impl<I, F> ExactSizeIterator for Update<I, F>
1107 where
1108 I: ExactSizeIterator,
1109 F: FnMut(&mut I::Item),
1110 {}
1111
1112 impl<I, F> DoubleEndedIterator for Update<I, F>
1113 where
1114 I: DoubleEndedIterator,
1115 F: FnMut(&mut I::Item),
1116 {
next_back(&mut self) -> Option<Self::Item>1117 fn next_back(&mut self) -> Option<Self::Item> {
1118 if let Some(mut v) = self.iter.next_back() {
1119 (self.f)(&mut v);
1120 Some(v)
1121 } else {
1122 None
1123 }
1124 }
1125 }
1126
1127 impl<I, F> FusedIterator for Update<I, F>
1128 where
1129 I: FusedIterator,
1130 F: FnMut(&mut I::Item),
1131 {}
1132