4 use crate::ops::{Add, AddAssign, Try};
6 use super::{from_fn, LoopState};
7 use super::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator, TrustedLen};
14 pub use self::chain::Chain;
15 #[stable(feature = "rust1", since = "1.0.0")]
16 pub use self::flatten::{FlatMap, Flatten};
17 pub use self::fuse::Fuse;
18 pub(crate) use self::zip::TrustedRandomAccess;
19 pub use self::zip::Zip;
21 /// A double-ended iterator with the direction inverted.
23 /// This `struct` is created by the [`rev`] method on [`Iterator`]. See its
24 /// documentation for more.
26 /// [`rev`]: trait.Iterator.html#method.rev
27 /// [`Iterator`]: trait.Iterator.html
28 #[derive(Clone, Debug)]
29 #[must_use = "iterators are lazy and do nothing unless consumed"]
30 #[stable(feature = "rust1", since = "1.0.0")]
35 pub(super) fn new(iter: T) -> Rev<T> {
40 #[stable(feature = "rust1", since = "1.0.0")]
41 impl<I> Iterator for Rev<I>
43 I: DoubleEndedIterator,
45 type Item = <I as Iterator>::Item;
48 fn next(&mut self) -> Option<<I as Iterator>::Item> {
52 fn size_hint(&self) -> (usize, Option<usize>) {
57 fn nth(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
61 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
64 F: FnMut(B, Self::Item) -> R,
67 self.iter.try_rfold(init, f)
70 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
72 F: FnMut(Acc, Self::Item) -> Acc,
74 self.iter.rfold(init, f)
78 fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
80 P: FnMut(&Self::Item) -> bool,
82 self.iter.rfind(predicate)
86 #[stable(feature = "rust1", since = "1.0.0")]
87 impl<I> DoubleEndedIterator for Rev<I>
89 I: DoubleEndedIterator,
92 fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
97 fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
101 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
104 F: FnMut(B, Self::Item) -> R,
107 self.iter.try_fold(init, f)
110 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
112 F: FnMut(Acc, Self::Item) -> Acc,
114 self.iter.fold(init, f)
117 fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
119 P: FnMut(&Self::Item) -> bool,
121 self.iter.find(predicate)
125 #[stable(feature = "rust1", since = "1.0.0")]
126 impl<I> ExactSizeIterator for Rev<I>
128 I: ExactSizeIterator + DoubleEndedIterator,
130 fn len(&self) -> usize {
134 fn is_empty(&self) -> bool {
139 #[stable(feature = "fused", since = "1.26.0")]
140 impl<I> FusedIterator for Rev<I> where I: FusedIterator + DoubleEndedIterator {}
142 #[unstable(feature = "trusted_len", issue = "37572")]
143 unsafe impl<I> TrustedLen for Rev<I> where I: TrustedLen + DoubleEndedIterator {}
145 /// An iterator that copies the elements of an underlying iterator.
147 /// This `struct` is created by the [`copied`] method on [`Iterator`]. See its
148 /// documentation for more.
150 /// [`copied`]: trait.Iterator.html#method.copied
151 /// [`Iterator`]: trait.Iterator.html
152 #[stable(feature = "iter_copied", since = "1.36.0")]
153 #[must_use = "iterators are lazy and do nothing unless consumed"]
154 #[derive(Clone, Debug)]
155 pub struct Copied<I> {
160 pub(super) fn new(it: I) -> Copied<I> {
165 fn copy_fold<T: Copy, Acc>(mut f: impl FnMut(Acc, T) -> Acc) -> impl FnMut(Acc, &T) -> Acc {
166 move |acc, &elt| f(acc, elt)
169 fn copy_try_fold<T: Copy, Acc, R>(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R {
170 move |acc, &elt| f(acc, elt)
173 #[stable(feature = "iter_copied", since = "1.36.0")]
174 impl<'a, I, T: 'a> Iterator for Copied<I>
176 I: Iterator<Item = &'a T>,
181 fn next(&mut self) -> Option<T> {
182 self.it.next().copied()
185 fn size_hint(&self) -> (usize, Option<usize>) {
189 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
192 F: FnMut(B, Self::Item) -> R,
195 self.it.try_fold(init, copy_try_fold(f))
198 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
200 F: FnMut(Acc, Self::Item) -> Acc,
202 self.it.fold(init, copy_fold(f))
205 fn nth(&mut self, n: usize) -> Option<T> {
206 self.it.nth(n).copied()
209 fn last(self) -> Option<T> {
210 self.it.last().copied()
213 fn count(self) -> usize {
218 #[stable(feature = "iter_copied", since = "1.36.0")]
219 impl<'a, I, T: 'a> DoubleEndedIterator for Copied<I>
221 I: DoubleEndedIterator<Item = &'a T>,
224 fn next_back(&mut self) -> Option<T> {
225 self.it.next_back().copied()
228 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
231 F: FnMut(B, Self::Item) -> R,
234 self.it.try_rfold(init, copy_try_fold(f))
237 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
239 F: FnMut(Acc, Self::Item) -> Acc,
241 self.it.rfold(init, copy_fold(f))
245 #[stable(feature = "iter_copied", since = "1.36.0")]
246 impl<'a, I, T: 'a> ExactSizeIterator for Copied<I>
248 I: ExactSizeIterator<Item = &'a T>,
251 fn len(&self) -> usize {
255 fn is_empty(&self) -> bool {
260 #[stable(feature = "iter_copied", since = "1.36.0")]
261 impl<'a, I, T: 'a> FusedIterator for Copied<I>
263 I: FusedIterator<Item = &'a T>,
269 unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Copied<I>
271 I: TrustedRandomAccess<Item = &'a T>,
274 unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
275 // SAFETY: the caller must uphold the contract for `TrustedRandomAccess::get_unchecked`.
276 unsafe { *self.it.get_unchecked(i) }
280 fn may_have_side_effect() -> bool {
281 I::may_have_side_effect()
285 #[stable(feature = "iter_copied", since = "1.36.0")]
286 unsafe impl<'a, I, T: 'a> TrustedLen for Copied<I>
288 I: TrustedLen<Item = &'a T>,
293 /// An iterator that clones the elements of an underlying iterator.
295 /// This `struct` is created by the [`cloned`] method on [`Iterator`]. See its
296 /// documentation for more.
298 /// [`cloned`]: trait.Iterator.html#method.cloned
299 /// [`Iterator`]: trait.Iterator.html
300 #[stable(feature = "iter_cloned", since = "1.1.0")]
301 #[must_use = "iterators are lazy and do nothing unless consumed"]
302 #[derive(Clone, Debug)]
303 pub struct Cloned<I> {
307 pub(super) fn new(it: I) -> Cloned<I> {
312 fn clone_try_fold<T: Clone, Acc, R>(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R {
313 move |acc, elt| f(acc, elt.clone())
316 #[stable(feature = "iter_cloned", since = "1.1.0")]
317 impl<'a, I, T: 'a> Iterator for Cloned<I>
319 I: Iterator<Item = &'a T>,
324 fn next(&mut self) -> Option<T> {
325 self.it.next().cloned()
328 fn size_hint(&self) -> (usize, Option<usize>) {
332 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
335 F: FnMut(B, Self::Item) -> R,
338 self.it.try_fold(init, clone_try_fold(f))
341 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
343 F: FnMut(Acc, Self::Item) -> Acc,
345 self.it.map(T::clone).fold(init, f)
349 #[stable(feature = "iter_cloned", since = "1.1.0")]
350 impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
352 I: DoubleEndedIterator<Item = &'a T>,
355 fn next_back(&mut self) -> Option<T> {
356 self.it.next_back().cloned()
359 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
362 F: FnMut(B, Self::Item) -> R,
365 self.it.try_rfold(init, clone_try_fold(f))
368 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
370 F: FnMut(Acc, Self::Item) -> Acc,
372 self.it.map(T::clone).rfold(init, f)
376 #[stable(feature = "iter_cloned", since = "1.1.0")]
377 impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
379 I: ExactSizeIterator<Item = &'a T>,
382 fn len(&self) -> usize {
386 fn is_empty(&self) -> bool {
391 #[stable(feature = "fused", since = "1.26.0")]
392 impl<'a, I, T: 'a> FusedIterator for Cloned<I>
394 I: FusedIterator<Item = &'a T>,
400 unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
402 I: TrustedRandomAccess<Item = &'a T>,
405 default unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
406 // SAFETY: the caller must uphold the contract for `TrustedRandomAccess::get_unchecked`.
407 unsafe { self.it.get_unchecked(i) }.clone()
411 default fn may_have_side_effect() -> bool {
417 unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
419 I: TrustedRandomAccess<Item = &'a T>,
422 unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
423 // SAFETY: the caller must uphold the contract for `TrustedRandomAccess::get_unchecked`.
424 unsafe { *self.it.get_unchecked(i) }
428 fn may_have_side_effect() -> bool {
429 I::may_have_side_effect()
433 #[unstable(feature = "trusted_len", issue = "37572")]
434 unsafe impl<'a, I, T: 'a> TrustedLen for Cloned<I>
436 I: TrustedLen<Item = &'a T>,
441 /// An iterator that repeats endlessly.
443 /// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its
444 /// documentation for more.
446 /// [`cycle`]: trait.Iterator.html#method.cycle
447 /// [`Iterator`]: trait.Iterator.html
448 #[derive(Clone, Debug)]
449 #[must_use = "iterators are lazy and do nothing unless consumed"]
450 #[stable(feature = "rust1", since = "1.0.0")]
451 pub struct Cycle<I> {
455 impl<I: Clone> Cycle<I> {
456 pub(super) fn new(iter: I) -> Cycle<I> {
457 Cycle { orig: iter.clone(), iter }
461 #[stable(feature = "rust1", since = "1.0.0")]
462 impl<I> Iterator for Cycle<I>
466 type Item = <I as Iterator>::Item;
469 fn next(&mut self) -> Option<<I as Iterator>::Item> {
470 match self.iter.next() {
472 self.iter = self.orig.clone();
480 fn size_hint(&self) -> (usize, Option<usize>) {
481 // the cycle iterator is either empty or infinite
482 match self.orig.size_hint() {
483 sz @ (0, Some(0)) => sz,
485 _ => (usize::MAX, None),
490 fn try_fold<Acc, F, R>(&mut self, mut acc: Acc, mut f: F) -> R
492 F: FnMut(Acc, Self::Item) -> R,
495 // fully iterate the current iterator. this is necessary because
496 // `self.iter` may be empty even when `self.orig` isn't
497 acc = self.iter.try_fold(acc, &mut f)?;
498 self.iter = self.orig.clone();
500 // complete a full cycle, keeping track of whether the cycled
501 // iterator is empty or not. we need to return early in case
502 // of an empty iterator to prevent an infinite loop
503 let mut is_empty = true;
504 acc = self.iter.try_fold(acc, |acc, x| {
510 return Try::from_ok(acc);
514 self.iter = self.orig.clone();
515 acc = self.iter.try_fold(acc, &mut f)?;
519 // No `fold` override, because `fold` doesn't make much sense for `Cycle`,
520 // and we can't do anything better than the default.
523 #[stable(feature = "fused", since = "1.26.0")]
524 impl<I> FusedIterator for Cycle<I> where I: Clone + Iterator {}
526 /// An iterator for stepping iterators by a custom amount.
528 /// This `struct` is created by the [`step_by`] method on [`Iterator`]. See
529 /// its documentation for more.
531 /// [`step_by`]: trait.Iterator.html#method.step_by
532 /// [`Iterator`]: trait.Iterator.html
533 #[must_use = "iterators are lazy and do nothing unless consumed"]
534 #[stable(feature = "iterator_step_by", since = "1.28.0")]
535 #[derive(Clone, Debug)]
536 pub struct StepBy<I> {
542 pub(super) fn new(iter: I, step: usize) -> StepBy<I> {
544 StepBy { iter, step: step - 1, first_take: true }
548 #[stable(feature = "iterator_step_by", since = "1.28.0")]
549 impl<I> Iterator for StepBy<I>
556 fn next(&mut self) -> Option<Self::Item> {
558 self.first_take = false;
561 self.iter.nth(self.step)
566 fn size_hint(&self) -> (usize, Option<usize>) {
568 fn first_size(step: usize) -> impl Fn(usize) -> usize {
569 move |n| if n == 0 { 0 } else { 1 + (n - 1) / (step + 1) }
573 fn other_size(step: usize) -> impl Fn(usize) -> usize {
574 move |n| n / (step + 1)
577 let (low, high) = self.iter.size_hint();
580 let f = first_size(self.step);
581 (f(low), high.map(f))
583 let f = other_size(self.step);
584 (f(low), high.map(f))
589 fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
591 self.first_take = false;
592 let first = self.iter.next();
598 // n and self.step are indices, we need to add 1 to get the amount of elements
599 // When calling `.nth`, we need to subtract 1 again to convert back to an index
600 // step + 1 can't overflow because `.step_by` sets `self.step` to `step - 1`
601 let mut step = self.step + 1;
602 // n + 1 could overflow
603 // thus, if n is usize::MAX, instead of adding one, we call .nth(step)
605 self.iter.nth(step - 1);
612 let mul = n.checked_mul(step);
614 if intrinsics::likely(mul.is_some()) {
615 return self.iter.nth(mul.unwrap() - 1);
618 let div_n = usize::MAX / n;
619 let div_step = usize::MAX / step;
620 let nth_n = div_n * n;
621 let nth_step = div_step * step;
622 let nth = if nth_n > nth_step {
629 self.iter.nth(nth - 1);
633 fn try_fold<Acc, F, R>(&mut self, mut acc: Acc, mut f: F) -> R
635 F: FnMut(Acc, Self::Item) -> R,
639 fn nth<I: Iterator>(iter: &mut I, step: usize) -> impl FnMut() -> Option<I::Item> + '_ {
640 move || iter.nth(step)
644 self.first_take = false;
645 match self.iter.next() {
646 None => return Try::from_ok(acc),
647 Some(x) => acc = f(acc, x)?,
650 from_fn(nth(&mut self.iter, self.step)).try_fold(acc, f)
653 fn fold<Acc, F>(mut self, mut acc: Acc, mut f: F) -> Acc
655 F: FnMut(Acc, Self::Item) -> Acc,
658 fn nth<I: Iterator>(iter: &mut I, step: usize) -> impl FnMut() -> Option<I::Item> + '_ {
659 move || iter.nth(step)
663 self.first_take = false;
664 match self.iter.next() {
666 Some(x) => acc = f(acc, x),
669 from_fn(nth(&mut self.iter, self.step)).fold(acc, f)
675 I: ExactSizeIterator,
677 // The zero-based index starting from the end of the iterator of the
678 // last element. Used in the `DoubleEndedIterator` implementation.
679 fn next_back_index(&self) -> usize {
680 let rem = self.iter.len() % (self.step + 1);
682 if rem == 0 { self.step } else { rem - 1 }
689 #[stable(feature = "double_ended_step_by_iterator", since = "1.38.0")]
690 impl<I> DoubleEndedIterator for StepBy<I>
692 I: DoubleEndedIterator + ExactSizeIterator,
695 fn next_back(&mut self) -> Option<Self::Item> {
696 self.iter.nth_back(self.next_back_index())
700 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
701 // `self.iter.nth_back(usize::MAX)` does the right thing here when `n`
702 // is out of bounds because the length of `self.iter` does not exceed
703 // `usize::MAX` (because `I: ExactSizeIterator`) and `nth_back` is
705 let n = n.saturating_mul(self.step + 1).saturating_add(self.next_back_index());
706 self.iter.nth_back(n)
709 fn try_rfold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R
711 F: FnMut(Acc, Self::Item) -> R,
715 fn nth_back<I: DoubleEndedIterator>(
718 ) -> impl FnMut() -> Option<I::Item> + '_ {
719 move || iter.nth_back(step)
722 match self.next_back() {
723 None => Try::from_ok(init),
725 let acc = f(init, x)?;
726 from_fn(nth_back(&mut self.iter, self.step)).try_fold(acc, f)
732 fn rfold<Acc, F>(mut self, init: Acc, mut f: F) -> Acc
735 F: FnMut(Acc, Self::Item) -> Acc,
738 fn nth_back<I: DoubleEndedIterator>(
741 ) -> impl FnMut() -> Option<I::Item> + '_ {
742 move || iter.nth_back(step)
745 match self.next_back() {
748 let acc = f(init, x);
749 from_fn(nth_back(&mut self.iter, self.step)).fold(acc, f)
755 // StepBy can only make the iterator shorter, so the len will still fit.
756 #[stable(feature = "iterator_step_by", since = "1.28.0")]
757 impl<I> ExactSizeIterator for StepBy<I> where I: ExactSizeIterator {}
759 /// An iterator that maps the values of `iter` with `f`.
761 /// This `struct` is created by the [`map`] method on [`Iterator`]. See its
762 /// documentation for more.
764 /// [`map`]: trait.Iterator.html#method.map
765 /// [`Iterator`]: trait.Iterator.html
767 /// # Notes about side effects
769 /// The [`map`] iterator implements [`DoubleEndedIterator`], meaning that
770 /// you can also [`map`] backwards:
773 /// let v: Vec<i32> = vec![1, 2, 3].into_iter().map(|x| x + 1).rev().collect();
775 /// assert_eq!(v, [4, 3, 2]);
778 /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
780 /// But if your closure has state, iterating backwards may act in a way you do
781 /// not expect. Let's go through an example. First, in the forward direction:
786 /// for pair in vec!['a', 'b', 'c'].into_iter()
787 /// .map(|letter| { c += 1; (letter, c) }) {
788 /// println!("{:?}", pair);
792 /// This will print "('a', 1), ('b', 2), ('c', 3)".
794 /// Now consider this twist where we add a call to `rev`. This version will
795 /// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed,
796 /// but the values of the counter still go in order. This is because `map()` is
797 /// still being called lazily on each item, but we are popping items off the
798 /// back of the vector now, instead of shifting them from the front.
803 /// for pair in vec!['a', 'b', 'c'].into_iter()
804 /// .map(|letter| { c += 1; (letter, c) })
806 /// println!("{:?}", pair);
809 #[must_use = "iterators are lazy and do nothing unless consumed"]
810 #[stable(feature = "rust1", since = "1.0.0")]
812 pub struct Map<I, F> {
816 impl<I, F> Map<I, F> {
817 pub(super) fn new(iter: I, f: F) -> Map<I, F> {
822 #[stable(feature = "core_impl_debug", since = "1.9.0")]
823 impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> {
824 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
825 f.debug_struct("Map").field("iter", &self.iter).finish()
829 fn map_fold<T, B, Acc>(
830 mut f: impl FnMut(T) -> B,
831 mut g: impl FnMut(Acc, B) -> Acc,
832 ) -> impl FnMut(Acc, T) -> Acc {
833 move |acc, elt| g(acc, f(elt))
836 fn map_try_fold<'a, T, B, Acc, R>(
837 f: &'a mut impl FnMut(T) -> B,
838 mut g: impl FnMut(Acc, B) -> R + 'a,
839 ) -> impl FnMut(Acc, T) -> R + 'a {
840 move |acc, elt| g(acc, f(elt))
843 #[stable(feature = "rust1", since = "1.0.0")]
844 impl<B, I: Iterator, F> Iterator for Map<I, F>
846 F: FnMut(I::Item) -> B,
851 fn next(&mut self) -> Option<B> {
852 self.iter.next().map(&mut self.f)
856 fn size_hint(&self) -> (usize, Option<usize>) {
857 self.iter.size_hint()
860 fn try_fold<Acc, G, R>(&mut self, init: Acc, g: G) -> R
863 G: FnMut(Acc, Self::Item) -> R,
866 self.iter.try_fold(init, map_try_fold(&mut self.f, g))
869 fn fold<Acc, G>(self, init: Acc, g: G) -> Acc
871 G: FnMut(Acc, Self::Item) -> Acc,
873 self.iter.fold(init, map_fold(self.f, g))
877 #[stable(feature = "rust1", since = "1.0.0")]
878 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F>
880 F: FnMut(I::Item) -> B,
883 fn next_back(&mut self) -> Option<B> {
884 self.iter.next_back().map(&mut self.f)
887 fn try_rfold<Acc, G, R>(&mut self, init: Acc, g: G) -> R
890 G: FnMut(Acc, Self::Item) -> R,
893 self.iter.try_rfold(init, map_try_fold(&mut self.f, g))
896 fn rfold<Acc, G>(self, init: Acc, g: G) -> Acc
898 G: FnMut(Acc, Self::Item) -> Acc,
900 self.iter.rfold(init, map_fold(self.f, g))
904 #[stable(feature = "rust1", since = "1.0.0")]
905 impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F>
907 F: FnMut(I::Item) -> B,
909 fn len(&self) -> usize {
913 fn is_empty(&self) -> bool {
918 #[stable(feature = "fused", since = "1.26.0")]
919 impl<B, I: FusedIterator, F> FusedIterator for Map<I, F> where F: FnMut(I::Item) -> B {}
921 #[unstable(feature = "trusted_len", issue = "37572")]
922 unsafe impl<B, I, F> TrustedLen for Map<I, F>
925 F: FnMut(I::Item) -> B,
930 unsafe impl<B, I, F> TrustedRandomAccess for Map<I, F>
932 I: TrustedRandomAccess,
933 F: FnMut(I::Item) -> B,
935 unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
936 // SAFETY: the caller must uphold the contract for `TrustedRandomAccess::get_unchecked`.
937 (self.f)(unsafe { self.iter.get_unchecked(i) })
940 fn may_have_side_effect() -> bool {
945 /// An iterator that filters the elements of `iter` with `predicate`.
947 /// This `struct` is created by the [`filter`] method on [`Iterator`]. See its
948 /// documentation for more.
950 /// [`filter`]: trait.Iterator.html#method.filter
951 /// [`Iterator`]: trait.Iterator.html
952 #[must_use = "iterators are lazy and do nothing unless consumed"]
953 #[stable(feature = "rust1", since = "1.0.0")]
955 pub struct Filter<I, P> {
959 impl<I, P> Filter<I, P> {
960 pub(super) fn new(iter: I, predicate: P) -> Filter<I, P> {
961 Filter { iter, predicate }
965 #[stable(feature = "core_impl_debug", since = "1.9.0")]
966 impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
967 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
968 f.debug_struct("Filter").field("iter", &self.iter).finish()
972 fn filter_fold<T, Acc>(
973 mut predicate: impl FnMut(&T) -> bool,
974 mut fold: impl FnMut(Acc, T) -> Acc,
975 ) -> impl FnMut(Acc, T) -> Acc {
976 move |acc, item| if predicate(&item) { fold(acc, item) } else { acc }
979 fn filter_try_fold<'a, T, Acc, R: Try<Ok = Acc>>(
980 predicate: &'a mut impl FnMut(&T) -> bool,
981 mut fold: impl FnMut(Acc, T) -> R + 'a,
982 ) -> impl FnMut(Acc, T) -> R + 'a {
983 move |acc, item| if predicate(&item) { fold(acc, item) } else { R::from_ok(acc) }
986 #[stable(feature = "rust1", since = "1.0.0")]
987 impl<I: Iterator, P> Iterator for Filter<I, P>
989 P: FnMut(&I::Item) -> bool,
994 fn next(&mut self) -> Option<I::Item> {
995 self.iter.find(&mut self.predicate)
999 fn size_hint(&self) -> (usize, Option<usize>) {
1000 let (_, upper) = self.iter.size_hint();
1001 (0, upper) // can't know a lower bound, due to the predicate
1004 // this special case allows the compiler to make `.filter(_).count()`
1005 // branchless. Barring perfect branch prediction (which is unattainable in
1006 // the general case), this will be much faster in >90% of cases (containing
1007 // virtually all real workloads) and only a tiny bit slower in the rest.
1009 // Having this specialization thus allows us to write `.filter(p).count()`
1010 // where we would otherwise write `.map(|x| p(x) as usize).sum()`, which is
1011 // less readable and also less backwards-compatible to Rust before 1.10.
1013 // Using the branchless version will also simplify the LLVM byte code, thus
1014 // leaving more budget for LLVM optimizations.
1016 fn count(self) -> usize {
1018 fn to_usize<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut(T) -> usize {
1019 move |x| predicate(&x) as usize
1022 self.iter.map(to_usize(self.predicate)).sum()
1026 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1029 Fold: FnMut(Acc, Self::Item) -> R,
1032 self.iter.try_fold(init, filter_try_fold(&mut self.predicate, fold))
1036 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1038 Fold: FnMut(Acc, Self::Item) -> Acc,
1040 self.iter.fold(init, filter_fold(self.predicate, fold))
1044 #[stable(feature = "rust1", since = "1.0.0")]
1045 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
1047 P: FnMut(&I::Item) -> bool,
1050 fn next_back(&mut self) -> Option<I::Item> {
1051 self.iter.rfind(&mut self.predicate)
1055 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1058 Fold: FnMut(Acc, Self::Item) -> R,
1061 self.iter.try_rfold(init, filter_try_fold(&mut self.predicate, fold))
1065 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1067 Fold: FnMut(Acc, Self::Item) -> Acc,
1069 self.iter.rfold(init, filter_fold(self.predicate, fold))
1073 #[stable(feature = "fused", since = "1.26.0")]
1074 impl<I: FusedIterator, P> FusedIterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {}
1076 /// An iterator that uses `f` to both filter and map elements from `iter`.
1078 /// This `struct` is created by the [`filter_map`] method on [`Iterator`]. See its
1079 /// documentation for more.
1081 /// [`filter_map`]: trait.Iterator.html#method.filter_map
1082 /// [`Iterator`]: trait.Iterator.html
1083 #[must_use = "iterators are lazy and do nothing unless consumed"]
1084 #[stable(feature = "rust1", since = "1.0.0")]
1086 pub struct FilterMap<I, F> {
1090 impl<I, F> FilterMap<I, F> {
1091 pub(super) fn new(iter: I, f: F) -> FilterMap<I, F> {
1092 FilterMap { iter, f }
1096 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1097 impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> {
1098 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1099 f.debug_struct("FilterMap").field("iter", &self.iter).finish()
1103 fn filter_map_fold<T, B, Acc>(
1104 mut f: impl FnMut(T) -> Option<B>,
1105 mut fold: impl FnMut(Acc, B) -> Acc,
1106 ) -> impl FnMut(Acc, T) -> Acc {
1107 move |acc, item| match f(item) {
1108 Some(x) => fold(acc, x),
1113 fn filter_map_try_fold<'a, T, B, Acc, R: Try<Ok = Acc>>(
1114 f: &'a mut impl FnMut(T) -> Option<B>,
1115 mut fold: impl FnMut(Acc, B) -> R + 'a,
1116 ) -> impl FnMut(Acc, T) -> R + 'a {
1117 move |acc, item| match f(item) {
1118 Some(x) => fold(acc, x),
1119 None => R::from_ok(acc),
1123 #[stable(feature = "rust1", since = "1.0.0")]
1124 impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
1126 F: FnMut(I::Item) -> Option<B>,
1131 fn next(&mut self) -> Option<B> {
1132 self.iter.find_map(&mut self.f)
1136 fn size_hint(&self) -> (usize, Option<usize>) {
1137 let (_, upper) = self.iter.size_hint();
1138 (0, upper) // can't know a lower bound, due to the predicate
1142 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1145 Fold: FnMut(Acc, Self::Item) -> R,
1148 self.iter.try_fold(init, filter_map_try_fold(&mut self.f, fold))
1152 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1154 Fold: FnMut(Acc, Self::Item) -> Acc,
1156 self.iter.fold(init, filter_map_fold(self.f, fold))
1160 #[stable(feature = "rust1", since = "1.0.0")]
1161 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
1163 F: FnMut(I::Item) -> Option<B>,
1166 fn next_back(&mut self) -> Option<B> {
1169 f: &mut impl FnMut(T) -> Option<B>,
1170 ) -> impl FnMut((), T) -> LoopState<(), B> + '_ {
1171 move |(), x| match f(x) {
1172 Some(x) => LoopState::Break(x),
1173 None => LoopState::Continue(()),
1177 self.iter.try_rfold((), find(&mut self.f)).break_value()
1181 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1184 Fold: FnMut(Acc, Self::Item) -> R,
1187 self.iter.try_rfold(init, filter_map_try_fold(&mut self.f, fold))
1191 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1193 Fold: FnMut(Acc, Self::Item) -> Acc,
1195 self.iter.rfold(init, filter_map_fold(self.f, fold))
1199 #[stable(feature = "fused", since = "1.26.0")]
1200 impl<B, I: FusedIterator, F> FusedIterator for FilterMap<I, F> where F: FnMut(I::Item) -> Option<B> {}
1202 /// An iterator that yields the current count and the element during iteration.
1204 /// This `struct` is created by the [`enumerate`] method on [`Iterator`]. See its
1205 /// documentation for more.
1207 /// [`enumerate`]: trait.Iterator.html#method.enumerate
1208 /// [`Iterator`]: trait.Iterator.html
1209 #[derive(Clone, Debug)]
1210 #[must_use = "iterators are lazy and do nothing unless consumed"]
1211 #[stable(feature = "rust1", since = "1.0.0")]
1212 pub struct Enumerate<I> {
1216 impl<I> Enumerate<I> {
1217 pub(super) fn new(iter: I) -> Enumerate<I> {
1218 Enumerate { iter, count: 0 }
1222 #[stable(feature = "rust1", since = "1.0.0")]
1223 impl<I> Iterator for Enumerate<I>
1227 type Item = (usize, <I as Iterator>::Item);
1229 /// # Overflow Behavior
1231 /// The method does no guarding against overflows, so enumerating more than
1232 /// `usize::MAX` elements either produces the wrong result or panics. If
1233 /// debug assertions are enabled, a panic is guaranteed.
1237 /// Might panic if the index of the element overflows a `usize`.
1239 fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1240 let a = self.iter.next()?;
1242 // Possible undefined overflow.
1243 AddAssign::add_assign(&mut self.count, 1);
1248 fn size_hint(&self) -> (usize, Option<usize>) {
1249 self.iter.size_hint()
1253 fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
1254 let a = self.iter.nth(n)?;
1255 // Possible undefined overflow.
1256 let i = Add::add(self.count, n);
1257 self.count = Add::add(i, 1);
1262 fn count(self) -> usize {
1267 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1270 Fold: FnMut(Acc, Self::Item) -> R,
1274 fn enumerate<'a, T, Acc, R>(
1275 count: &'a mut usize,
1276 mut fold: impl FnMut(Acc, (usize, T)) -> R + 'a,
1277 ) -> impl FnMut(Acc, T) -> R + 'a {
1279 let acc = fold(acc, (*count, item));
1280 // Possible undefined overflow.
1281 AddAssign::add_assign(count, 1);
1286 self.iter.try_fold(init, enumerate(&mut self.count, fold))
1290 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1292 Fold: FnMut(Acc, Self::Item) -> Acc,
1295 fn enumerate<T, Acc>(
1297 mut fold: impl FnMut(Acc, (usize, T)) -> Acc,
1298 ) -> impl FnMut(Acc, T) -> Acc {
1300 let acc = fold(acc, (count, item));
1301 // Possible undefined overflow.
1302 AddAssign::add_assign(&mut count, 1);
1307 self.iter.fold(init, enumerate(self.count, fold))
1311 #[stable(feature = "rust1", since = "1.0.0")]
1312 impl<I> DoubleEndedIterator for Enumerate<I>
1314 I: ExactSizeIterator + DoubleEndedIterator,
1317 fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1318 let a = self.iter.next_back()?;
1319 let len = self.iter.len();
1320 // Can safely add, `ExactSizeIterator` promises that the number of
1321 // elements fits into a `usize`.
1322 Some((self.count + len, a))
1326 fn nth_back(&mut self, n: usize) -> Option<(usize, <I as Iterator>::Item)> {
1327 let a = self.iter.nth_back(n)?;
1328 let len = self.iter.len();
1329 // Can safely add, `ExactSizeIterator` promises that the number of
1330 // elements fits into a `usize`.
1331 Some((self.count + len, a))
1335 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1338 Fold: FnMut(Acc, Self::Item) -> R,
1341 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1342 // that the number of elements fits into a `usize`.
1343 fn enumerate<T, Acc, R>(
1345 mut fold: impl FnMut(Acc, (usize, T)) -> R,
1346 ) -> impl FnMut(Acc, T) -> R {
1349 fold(acc, (count, item))
1353 let count = self.count + self.iter.len();
1354 self.iter.try_rfold(init, enumerate(count, fold))
1358 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1360 Fold: FnMut(Acc, Self::Item) -> Acc,
1362 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1363 // that the number of elements fits into a `usize`.
1364 fn enumerate<T, Acc>(
1366 mut fold: impl FnMut(Acc, (usize, T)) -> Acc,
1367 ) -> impl FnMut(Acc, T) -> Acc {
1370 fold(acc, (count, item))
1374 let count = self.count + self.iter.len();
1375 self.iter.rfold(init, enumerate(count, fold))
1379 #[stable(feature = "rust1", since = "1.0.0")]
1380 impl<I> ExactSizeIterator for Enumerate<I>
1382 I: ExactSizeIterator,
1384 fn len(&self) -> usize {
1388 fn is_empty(&self) -> bool {
1389 self.iter.is_empty()
1394 unsafe impl<I> TrustedRandomAccess for Enumerate<I>
1396 I: TrustedRandomAccess,
1398 unsafe fn get_unchecked(&mut self, i: usize) -> (usize, I::Item) {
1399 // SAFETY: the caller must uphold the contract for `TrustedRandomAccess::get_unchecked`.
1400 (self.count + i, unsafe { self.iter.get_unchecked(i) })
1403 fn may_have_side_effect() -> bool {
1404 I::may_have_side_effect()
1408 #[stable(feature = "fused", since = "1.26.0")]
1409 impl<I> FusedIterator for Enumerate<I> where I: FusedIterator {}
1411 #[unstable(feature = "trusted_len", issue = "37572")]
1412 unsafe impl<I> TrustedLen for Enumerate<I> where I: TrustedLen {}
1414 /// An iterator with a `peek()` that returns an optional reference to the next
1417 /// This `struct` is created by the [`peekable`] method on [`Iterator`]. See its
1418 /// documentation for more.
1420 /// [`peekable`]: trait.Iterator.html#method.peekable
1421 /// [`Iterator`]: trait.Iterator.html
1422 #[derive(Clone, Debug)]
1423 #[must_use = "iterators are lazy and do nothing unless consumed"]
1424 #[stable(feature = "rust1", since = "1.0.0")]
1425 pub struct Peekable<I: Iterator> {
1427 /// Remember a peeked value, even if it was None.
1428 peeked: Option<Option<I::Item>>,
1430 impl<I: Iterator> Peekable<I> {
1431 pub(super) fn new(iter: I) -> Peekable<I> {
1432 Peekable { iter, peeked: None }
1436 // Peekable must remember if a None has been seen in the `.peek()` method.
1437 // It ensures that `.peek(); .peek();` or `.peek(); .next();` only advances the
1438 // underlying iterator at most once. This does not by itself make the iterator
1440 #[stable(feature = "rust1", since = "1.0.0")]
1441 impl<I: Iterator> Iterator for Peekable<I> {
1442 type Item = I::Item;
1445 fn next(&mut self) -> Option<I::Item> {
1446 match self.peeked.take() {
1448 None => self.iter.next(),
1453 #[rustc_inherit_overflow_checks]
1454 fn count(mut self) -> usize {
1455 match self.peeked.take() {
1457 Some(Some(_)) => 1 + self.iter.count(),
1458 None => self.iter.count(),
1463 fn nth(&mut self, n: usize) -> Option<I::Item> {
1464 match self.peeked.take() {
1466 Some(v @ Some(_)) if n == 0 => v,
1467 Some(Some(_)) => self.iter.nth(n - 1),
1468 None => self.iter.nth(n),
1473 fn last(mut self) -> Option<I::Item> {
1474 let peek_opt = match self.peeked.take() {
1475 Some(None) => return None,
1479 self.iter.last().or(peek_opt)
1483 fn size_hint(&self) -> (usize, Option<usize>) {
1484 let peek_len = match self.peeked {
1485 Some(None) => return (0, Some(0)),
1489 let (lo, hi) = self.iter.size_hint();
1490 let lo = lo.saturating_add(peek_len);
1492 Some(x) => x.checked_add(peek_len),
1499 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
1502 F: FnMut(B, Self::Item) -> R,
1505 let acc = match self.peeked.take() {
1506 Some(None) => return Try::from_ok(init),
1507 Some(Some(v)) => f(init, v)?,
1510 self.iter.try_fold(acc, f)
1514 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1516 Fold: FnMut(Acc, Self::Item) -> Acc,
1518 let acc = match self.peeked {
1519 Some(None) => return init,
1520 Some(Some(v)) => fold(init, v),
1523 self.iter.fold(acc, fold)
1527 #[stable(feature = "double_ended_peek_iterator", since = "1.38.0")]
1528 impl<I> DoubleEndedIterator for Peekable<I>
1530 I: DoubleEndedIterator,
1533 fn next_back(&mut self) -> Option<Self::Item> {
1534 match self.peeked.as_mut() {
1535 Some(v @ Some(_)) => self.iter.next_back().or_else(|| v.take()),
1537 None => self.iter.next_back(),
1542 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
1545 F: FnMut(B, Self::Item) -> R,
1548 match self.peeked.take() {
1549 Some(None) => Try::from_ok(init),
1550 Some(Some(v)) => match self.iter.try_rfold(init, &mut f).into_result() {
1551 Ok(acc) => f(acc, v),
1553 self.peeked = Some(Some(v));
1557 None => self.iter.try_rfold(init, f),
1562 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1564 Fold: FnMut(Acc, Self::Item) -> Acc,
1569 let acc = self.iter.rfold(init, &mut fold);
1572 None => self.iter.rfold(init, fold),
1577 #[stable(feature = "rust1", since = "1.0.0")]
1578 impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
1580 #[stable(feature = "fused", since = "1.26.0")]
1581 impl<I: FusedIterator> FusedIterator for Peekable<I> {}
1583 impl<I: Iterator> Peekable<I> {
1584 /// Returns a reference to the next() value without advancing the iterator.
1586 /// Like [`next`], if there is a value, it is wrapped in a `Some(T)`.
1587 /// But if the iteration is over, `None` is returned.
1589 /// [`next`]: trait.Iterator.html#tymethod.next
1591 /// Because `peek()` returns a reference, and many iterators iterate over
1592 /// references, there can be a possibly confusing situation where the
1593 /// return value is a double reference. You can see this effect in the
1601 /// let xs = [1, 2, 3];
1603 /// let mut iter = xs.iter().peekable();
1605 /// // peek() lets us see into the future
1606 /// assert_eq!(iter.peek(), Some(&&1));
1607 /// assert_eq!(iter.next(), Some(&1));
1609 /// assert_eq!(iter.next(), Some(&2));
1611 /// // The iterator does not advance even if we `peek` multiple times
1612 /// assert_eq!(iter.peek(), Some(&&3));
1613 /// assert_eq!(iter.peek(), Some(&&3));
1615 /// assert_eq!(iter.next(), Some(&3));
1617 /// // After the iterator is finished, so is `peek()`
1618 /// assert_eq!(iter.peek(), None);
1619 /// assert_eq!(iter.next(), None);
1622 #[stable(feature = "rust1", since = "1.0.0")]
1623 pub fn peek(&mut self) -> Option<&I::Item> {
1624 let iter = &mut self.iter;
1625 self.peeked.get_or_insert_with(|| iter.next()).as_ref()
1628 /// Consume the next value of this iterator if a condition is true.
1630 /// If `func` returns `true` for the next value of this iterator, consume and return it.
1631 /// Otherwise, return `None`.
1634 /// Consume a number if it's equal to 0.
1636 /// #![feature(peekable_next_if)]
1637 /// let mut iter = (0..5).peekable();
1638 /// // The first item of the iterator is 0; consume it.
1639 /// assert_eq!(iter.next_if(|&x| x == 0), Some(0));
1640 /// // The next item returned is now 1, so `consume` will return `false`.
1641 /// assert_eq!(iter.next_if(|&x| x == 0), None);
1642 /// // `next_if` saves the value of the next item if it was not equal to `expected`.
1643 /// assert_eq!(iter.next(), Some(1));
1646 /// Consume any number less than 10.
1648 /// #![feature(peekable_next_if)]
1649 /// let mut iter = (1..20).peekable();
1650 /// // Consume all numbers less than 10
1651 /// while iter.next_if(|&x| x < 10).is_some() {}
1652 /// // The next value returned will be 10
1653 /// assert_eq!(iter.next(), Some(10));
1655 #[unstable(feature = "peekable_next_if", issue = "72480")]
1656 pub fn next_if(&mut self, func: impl FnOnce(&I::Item) -> bool) -> Option<I::Item> {
1658 Some(matched) if func(&matched) => Some(matched),
1660 // Since we called `self.next()`, we consumed `self.peeked`.
1661 assert!(self.peeked.is_none());
1662 self.peeked = Some(other);
1668 /// Consume the next item if it is equal to `expected`.
1671 /// Consume a number if it's equal to 0.
1673 /// #![feature(peekable_next_if)]
1674 /// let mut iter = (0..5).peekable();
1675 /// // The first item of the iterator is 0; consume it.
1676 /// assert_eq!(iter.next_if_eq(&0), Some(0));
1677 /// // The next item returned is now 1, so `consume` will return `false`.
1678 /// assert_eq!(iter.next_if_eq(&0), None);
1679 /// // `next_if_eq` saves the value of the next item if it was not equal to `expected`.
1680 /// assert_eq!(iter.next(), Some(1));
1682 #[unstable(feature = "peekable_next_if", issue = "72480")]
1683 pub fn next_if_eq<R>(&mut self, expected: &R) -> Option<I::Item>
1686 I::Item: PartialEq<R>,
1688 self.next_if(|next| next == expected)
1692 /// An iterator that rejects elements while `predicate` returns `true`.
1694 /// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its
1695 /// documentation for more.
1697 /// [`skip_while`]: trait.Iterator.html#method.skip_while
1698 /// [`Iterator`]: trait.Iterator.html
1699 #[must_use = "iterators are lazy and do nothing unless consumed"]
1700 #[stable(feature = "rust1", since = "1.0.0")]
1702 pub struct SkipWhile<I, P> {
1707 impl<I, P> SkipWhile<I, P> {
1708 pub(super) fn new(iter: I, predicate: P) -> SkipWhile<I, P> {
1709 SkipWhile { iter, flag: false, predicate }
1713 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1714 impl<I: fmt::Debug, P> fmt::Debug for SkipWhile<I, P> {
1715 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1716 f.debug_struct("SkipWhile").field("iter", &self.iter).field("flag", &self.flag).finish()
1720 #[stable(feature = "rust1", since = "1.0.0")]
1721 impl<I: Iterator, P> Iterator for SkipWhile<I, P>
1723 P: FnMut(&I::Item) -> bool,
1725 type Item = I::Item;
1728 fn next(&mut self) -> Option<I::Item> {
1731 pred: &'a mut impl FnMut(&T) -> bool,
1732 ) -> impl FnMut(&T) -> bool + 'a {
1734 if *flag || !pred(x) {
1743 let flag = &mut self.flag;
1744 let pred = &mut self.predicate;
1745 self.iter.find(check(flag, pred))
1749 fn size_hint(&self) -> (usize, Option<usize>) {
1750 let (_, upper) = self.iter.size_hint();
1751 (0, upper) // can't know a lower bound, due to the predicate
1755 fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
1758 Fold: FnMut(Acc, Self::Item) -> R,
1763 Some(v) => init = fold(init, v)?,
1764 None => return Try::from_ok(init),
1767 self.iter.try_fold(init, fold)
1771 fn fold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
1773 Fold: FnMut(Acc, Self::Item) -> Acc,
1777 Some(v) => init = fold(init, v),
1778 None => return init,
1781 self.iter.fold(init, fold)
1785 #[stable(feature = "fused", since = "1.26.0")]
1786 impl<I, P> FusedIterator for SkipWhile<I, P>
1789 P: FnMut(&I::Item) -> bool,
1793 /// An iterator that only accepts elements while `predicate` returns `true`.
1795 /// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its
1796 /// documentation for more.
1798 /// [`take_while`]: trait.Iterator.html#method.take_while
1799 /// [`Iterator`]: trait.Iterator.html
1800 #[must_use = "iterators are lazy and do nothing unless consumed"]
1801 #[stable(feature = "rust1", since = "1.0.0")]
1803 pub struct TakeWhile<I, P> {
1808 impl<I, P> TakeWhile<I, P> {
1809 pub(super) fn new(iter: I, predicate: P) -> TakeWhile<I, P> {
1810 TakeWhile { iter, flag: false, predicate }
1814 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1815 impl<I: fmt::Debug, P> fmt::Debug for TakeWhile<I, P> {
1816 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1817 f.debug_struct("TakeWhile").field("iter", &self.iter).field("flag", &self.flag).finish()
1821 #[stable(feature = "rust1", since = "1.0.0")]
1822 impl<I: Iterator, P> Iterator for TakeWhile<I, P>
1824 P: FnMut(&I::Item) -> bool,
1826 type Item = I::Item;
1829 fn next(&mut self) -> Option<I::Item> {
1833 let x = self.iter.next()?;
1834 if (self.predicate)(&x) {
1844 fn size_hint(&self) -> (usize, Option<usize>) {
1848 let (_, upper) = self.iter.size_hint();
1849 (0, upper) // can't know a lower bound, due to the predicate
1854 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1857 Fold: FnMut(Acc, Self::Item) -> R,
1860 fn check<'a, T, Acc, R: Try<Ok = Acc>>(
1862 p: &'a mut impl FnMut(&T) -> bool,
1863 mut fold: impl FnMut(Acc, T) -> R + 'a,
1864 ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> + 'a {
1867 LoopState::from_try(fold(acc, x))
1870 LoopState::Break(Try::from_ok(acc))
1878 let flag = &mut self.flag;
1879 let p = &mut self.predicate;
1880 self.iter.try_fold(init, check(flag, p, fold)).into_try()
1885 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
1888 Fold: FnMut(Acc, Self::Item) -> Acc,
1891 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
1892 move |acc, x| Ok(f(acc, x))
1895 self.try_fold(init, ok(fold)).unwrap()
1899 #[stable(feature = "fused", since = "1.26.0")]
1900 impl<I, P> FusedIterator for TakeWhile<I, P>
1903 P: FnMut(&I::Item) -> bool,
1907 /// An iterator that only accepts elements while `predicate` returns `Some(_)`.
1909 /// This `struct` is created by the [`map_while`] method on [`Iterator`]. See its
1910 /// documentation for more.
1912 /// [`map_while`]: trait.Iterator.html#method.map_while
1913 /// [`Iterator`]: trait.Iterator.html
1914 #[must_use = "iterators are lazy and do nothing unless consumed"]
1915 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
1917 pub struct MapWhile<I, P> {
1922 impl<I, P> MapWhile<I, P> {
1923 pub(super) fn new(iter: I, predicate: P) -> MapWhile<I, P> {
1924 MapWhile { iter, predicate }
1928 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
1929 impl<I: fmt::Debug, P> fmt::Debug for MapWhile<I, P> {
1930 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1931 f.debug_struct("MapWhile").field("iter", &self.iter).finish()
1935 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
1936 impl<B, I: Iterator, P> Iterator for MapWhile<I, P>
1938 P: FnMut(I::Item) -> Option<B>,
1943 fn next(&mut self) -> Option<B> {
1944 let x = self.iter.next()?;
1949 fn size_hint(&self) -> (usize, Option<usize>) {
1950 let (_, upper) = self.iter.size_hint();
1951 (0, upper) // can't know a lower bound, due to the predicate
1955 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R
1958 Fold: FnMut(Acc, Self::Item) -> R,
1961 let Self { iter, predicate } = self;
1962 iter.try_fold(init, |acc, x| match predicate(x) {
1963 Some(item) => LoopState::from_try(fold(acc, item)),
1964 None => LoopState::Break(Try::from_ok(acc)),
1970 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
1973 Fold: FnMut(Acc, Self::Item) -> Acc,
1976 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
1977 move |acc, x| Ok(f(acc, x))
1980 self.try_fold(init, ok(fold)).unwrap()
1984 /// An iterator that skips over `n` elements of `iter`.
1986 /// This `struct` is created by the [`skip`] method on [`Iterator`]. See its
1987 /// documentation for more.
1989 /// [`skip`]: trait.Iterator.html#method.skip
1990 /// [`Iterator`]: trait.Iterator.html
1991 #[derive(Clone, Debug)]
1992 #[must_use = "iterators are lazy and do nothing unless consumed"]
1993 #[stable(feature = "rust1", since = "1.0.0")]
1994 pub struct Skip<I> {
1999 pub(super) fn new(iter: I, n: usize) -> Skip<I> {
2004 #[stable(feature = "rust1", since = "1.0.0")]
2005 impl<I> Iterator for Skip<I>
2009 type Item = <I as Iterator>::Item;
2012 fn next(&mut self) -> Option<I::Item> {
2018 self.iter.nth(old_n)
2023 fn nth(&mut self, n: usize) -> Option<I::Item> {
2024 // Can't just add n + self.n due to overflow.
2026 let to_skip = self.n;
2029 self.iter.nth(to_skip - 1)?;
2035 fn count(mut self) -> usize {
2038 if self.iter.nth(self.n - 1).is_none() {
2046 fn last(mut self) -> Option<I::Item> {
2049 self.iter.nth(self.n - 1)?;
2055 fn size_hint(&self) -> (usize, Option<usize>) {
2056 let (lower, upper) = self.iter.size_hint();
2058 let lower = lower.saturating_sub(self.n);
2059 let upper = match upper {
2060 Some(x) => Some(x.saturating_sub(self.n)),
2068 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2071 Fold: FnMut(Acc, Self::Item) -> R,
2078 if self.iter.nth(n - 1).is_none() {
2079 return Try::from_ok(init);
2082 self.iter.try_fold(init, fold)
2086 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2088 Fold: FnMut(Acc, Self::Item) -> Acc,
2092 if self.iter.nth(self.n - 1).is_none() {
2096 self.iter.fold(init, fold)
2100 #[stable(feature = "rust1", since = "1.0.0")]
2101 impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
2103 #[stable(feature = "double_ended_skip_iterator", since = "1.9.0")]
2104 impl<I> DoubleEndedIterator for Skip<I>
2106 I: DoubleEndedIterator + ExactSizeIterator,
2108 fn next_back(&mut self) -> Option<Self::Item> {
2109 if self.len() > 0 { self.iter.next_back() } else { None }
2113 fn nth_back(&mut self, n: usize) -> Option<I::Item> {
2114 let len = self.len();
2116 self.iter.nth_back(n)
2119 // consume the original iterator
2120 self.iter.nth_back(len - 1);
2126 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2129 Fold: FnMut(Acc, Self::Item) -> R,
2132 fn check<T, Acc, R: Try<Ok = Acc>>(
2134 mut fold: impl FnMut(Acc, T) -> R,
2135 ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> {
2138 let r = fold(acc, x);
2139 if n == 0 { LoopState::Break(r) } else { LoopState::from_try(r) }
2147 self.iter.try_rfold(init, check(n, fold)).into_try()
2151 fn rfold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2153 Fold: FnMut(Acc, Self::Item) -> Acc,
2156 fn ok<Acc, T>(mut f: impl FnMut(Acc, T) -> Acc) -> impl FnMut(Acc, T) -> Result<Acc, !> {
2157 move |acc, x| Ok(f(acc, x))
2160 self.try_rfold(init, ok(fold)).unwrap()
2164 #[stable(feature = "fused", since = "1.26.0")]
2165 impl<I> FusedIterator for Skip<I> where I: FusedIterator {}
2167 /// An iterator that only iterates over the first `n` iterations of `iter`.
2169 /// This `struct` is created by the [`take`] method on [`Iterator`]. See its
2170 /// documentation for more.
2172 /// [`take`]: trait.Iterator.html#method.take
2173 /// [`Iterator`]: trait.Iterator.html
2174 #[derive(Clone, Debug)]
2175 #[must_use = "iterators are lazy and do nothing unless consumed"]
2176 #[stable(feature = "rust1", since = "1.0.0")]
2177 pub struct Take<I> {
2179 pub(super) n: usize,
2182 pub(super) fn new(iter: I, n: usize) -> Take<I> {
2187 #[stable(feature = "rust1", since = "1.0.0")]
2188 impl<I> Iterator for Take<I>
2192 type Item = <I as Iterator>::Item;
2195 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2205 fn nth(&mut self, n: usize) -> Option<I::Item> {
2211 self.iter.nth(self.n - 1);
2219 fn size_hint(&self) -> (usize, Option<usize>) {
2221 return (0, Some(0));
2224 let (lower, upper) = self.iter.size_hint();
2226 let lower = cmp::min(lower, self.n);
2228 let upper = match upper {
2229 Some(x) if x < self.n => Some(x),
2237 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2240 Fold: FnMut(Acc, Self::Item) -> R,
2243 fn check<'a, T, Acc, R: Try<Ok = Acc>>(
2245 mut fold: impl FnMut(Acc, T) -> R + 'a,
2246 ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> + 'a {
2249 let r = fold(acc, x);
2250 if *n == 0 { LoopState::Break(r) } else { LoopState::from_try(r) }
2257 let n = &mut self.n;
2258 self.iter.try_fold(init, check(n, fold)).into_try()
2263 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2266 Fold: FnMut(Acc, Self::Item) -> Acc,
2269 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2270 move |acc, x| Ok(f(acc, x))
2273 self.try_fold(init, ok(fold)).unwrap()
2277 #[stable(feature = "double_ended_take_iterator", since = "1.38.0")]
2278 impl<I> DoubleEndedIterator for Take<I>
2280 I: DoubleEndedIterator + ExactSizeIterator,
2283 fn next_back(&mut self) -> Option<Self::Item> {
2289 self.iter.nth_back(self.iter.len().saturating_sub(n))
2294 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2295 let len = self.iter.len();
2297 let m = len.saturating_sub(self.n) + n;
2299 self.iter.nth_back(m)
2302 self.iter.nth_back(len - 1);
2309 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2312 Fold: FnMut(Acc, Self::Item) -> R,
2318 let len = self.iter.len();
2319 if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() {
2322 self.iter.try_rfold(init, fold)
2328 fn rfold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2331 Fold: FnMut(Acc, Self::Item) -> Acc,
2336 let len = self.iter.len();
2337 if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() {
2340 self.iter.rfold(init, fold)
2346 #[stable(feature = "rust1", since = "1.0.0")]
2347 impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
2349 #[stable(feature = "fused", since = "1.26.0")]
2350 impl<I> FusedIterator for Take<I> where I: FusedIterator {}
2352 #[unstable(feature = "trusted_len", issue = "37572")]
2353 unsafe impl<I: TrustedLen> TrustedLen for Take<I> {}
2355 /// An iterator to maintain state while iterating another iterator.
2357 /// This `struct` is created by the [`scan`] method on [`Iterator`]. See its
2358 /// documentation for more.
2360 /// [`scan`]: trait.Iterator.html#method.scan
2361 /// [`Iterator`]: trait.Iterator.html
2362 #[must_use = "iterators are lazy and do nothing unless consumed"]
2363 #[stable(feature = "rust1", since = "1.0.0")]
2365 pub struct Scan<I, St, F> {
2370 impl<I, St, F> Scan<I, St, F> {
2371 pub(super) fn new(iter: I, state: St, f: F) -> Scan<I, St, F> {
2372 Scan { iter, state, f }
2376 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2377 impl<I: fmt::Debug, St: fmt::Debug, F> fmt::Debug for Scan<I, St, F> {
2378 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2379 f.debug_struct("Scan").field("iter", &self.iter).field("state", &self.state).finish()
2383 #[stable(feature = "rust1", since = "1.0.0")]
2384 impl<B, I, St, F> Iterator for Scan<I, St, F>
2387 F: FnMut(&mut St, I::Item) -> Option<B>,
2392 fn next(&mut self) -> Option<B> {
2393 let a = self.iter.next()?;
2394 (self.f)(&mut self.state, a)
2398 fn size_hint(&self) -> (usize, Option<usize>) {
2399 let (_, upper) = self.iter.size_hint();
2400 (0, upper) // can't know a lower bound, due to the scan function
2404 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2407 Fold: FnMut(Acc, Self::Item) -> R,
2410 fn scan<'a, T, St, B, Acc, R: Try<Ok = Acc>>(
2412 f: &'a mut impl FnMut(&mut St, T) -> Option<B>,
2413 mut fold: impl FnMut(Acc, B) -> R + 'a,
2414 ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> + 'a {
2415 move |acc, x| match f(state, x) {
2416 None => LoopState::Break(Try::from_ok(acc)),
2417 Some(x) => LoopState::from_try(fold(acc, x)),
2421 let state = &mut self.state;
2422 let f = &mut self.f;
2423 self.iter.try_fold(init, scan(state, f, fold)).into_try()
2427 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2430 Fold: FnMut(Acc, Self::Item) -> Acc,
2433 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2434 move |acc, x| Ok(f(acc, x))
2437 self.try_fold(init, ok(fold)).unwrap()
2441 /// An iterator that calls a function with a reference to each element before
2444 /// This `struct` is created by the [`inspect`] method on [`Iterator`]. See its
2445 /// documentation for more.
2447 /// [`inspect`]: trait.Iterator.html#method.inspect
2448 /// [`Iterator`]: trait.Iterator.html
2449 #[must_use = "iterators are lazy and do nothing unless consumed"]
2450 #[stable(feature = "rust1", since = "1.0.0")]
2452 pub struct Inspect<I, F> {
2456 impl<I, F> Inspect<I, F> {
2457 pub(super) fn new(iter: I, f: F) -> Inspect<I, F> {
2462 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2463 impl<I: fmt::Debug, F> fmt::Debug for Inspect<I, F> {
2464 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2465 f.debug_struct("Inspect").field("iter", &self.iter).finish()
2469 impl<I: Iterator, F> Inspect<I, F>
2474 fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
2475 if let Some(ref a) = elt {
2483 fn inspect_fold<T, Acc>(
2484 mut f: impl FnMut(&T),
2485 mut fold: impl FnMut(Acc, T) -> Acc,
2486 ) -> impl FnMut(Acc, T) -> Acc {
2493 fn inspect_try_fold<'a, T, Acc, R>(
2494 f: &'a mut impl FnMut(&T),
2495 mut fold: impl FnMut(Acc, T) -> R + 'a,
2496 ) -> impl FnMut(Acc, T) -> R + 'a {
2503 #[stable(feature = "rust1", since = "1.0.0")]
2504 impl<I: Iterator, F> Iterator for Inspect<I, F>
2508 type Item = I::Item;
2511 fn next(&mut self) -> Option<I::Item> {
2512 let next = self.iter.next();
2513 self.do_inspect(next)
2517 fn size_hint(&self) -> (usize, Option<usize>) {
2518 self.iter.size_hint()
2522 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2525 Fold: FnMut(Acc, Self::Item) -> R,
2528 self.iter.try_fold(init, inspect_try_fold(&mut self.f, fold))
2532 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2534 Fold: FnMut(Acc, Self::Item) -> Acc,
2536 self.iter.fold(init, inspect_fold(self.f, fold))
2540 #[stable(feature = "rust1", since = "1.0.0")]
2541 impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
2546 fn next_back(&mut self) -> Option<I::Item> {
2547 let next = self.iter.next_back();
2548 self.do_inspect(next)
2552 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2555 Fold: FnMut(Acc, Self::Item) -> R,
2558 self.iter.try_rfold(init, inspect_try_fold(&mut self.f, fold))
2562 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2564 Fold: FnMut(Acc, Self::Item) -> Acc,
2566 self.iter.rfold(init, inspect_fold(self.f, fold))
2570 #[stable(feature = "rust1", since = "1.0.0")]
2571 impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F>
2575 fn len(&self) -> usize {
2579 fn is_empty(&self) -> bool {
2580 self.iter.is_empty()
2584 #[stable(feature = "fused", since = "1.26.0")]
2585 impl<I: FusedIterator, F> FusedIterator for Inspect<I, F> where F: FnMut(&I::Item) {}
2587 /// An iterator adapter that produces output as long as the underlying
2588 /// iterator produces `Result::Ok` values.
2590 /// If an error is encountered, the iterator stops and the error is
2592 pub(crate) struct ResultShunt<'a, I, E> {
2594 error: &'a mut Result<(), E>,
2597 /// Process the given iterator as if it yielded a `T` instead of a
2598 /// `Result<T, _>`. Any errors will stop the inner iterator and
2599 /// the overall result will be an error.
2600 pub(crate) fn process_results<I, T, E, F, U>(iter: I, mut f: F) -> Result<U, E>
2602 I: Iterator<Item = Result<T, E>>,
2603 for<'a> F: FnMut(ResultShunt<'a, I, E>) -> U,
2605 let mut error = Ok(());
2606 let shunt = ResultShunt { iter, error: &mut error };
2607 let value = f(shunt);
2608 error.map(|()| value)
2611 impl<I, T, E> Iterator for ResultShunt<'_, I, E>
2613 I: Iterator<Item = Result<T, E>>,
2617 fn next(&mut self) -> Option<Self::Item> {
2621 fn size_hint(&self) -> (usize, Option<usize>) {
2622 if self.error.is_err() {
2625 let (_, upper) = self.iter.size_hint();
2630 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
2632 F: FnMut(B, Self::Item) -> R,
2635 let error = &mut *self.error;
2637 .try_fold(init, |acc, x| match x {
2638 Ok(x) => LoopState::from_try(f(acc, x)),
2641 LoopState::Break(Try::from_ok(acc))
2647 fn fold<B, F>(mut self, init: B, fold: F) -> B
2650 F: FnMut(B, Self::Item) -> B,
2653 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2654 move |acc, x| Ok(f(acc, x))
2657 self.try_fold(init, ok(fold)).unwrap()