4 use crate::ops::{Add, AddAssign, ControlFlow, Try};
8 DoubleEndedIterator, ExactSizeIterator, FusedIterator, InPlaceIterable, Iterator, TrustedLen,
16 pub use self::chain::Chain;
17 #[stable(feature = "rust1", since = "1.0.0")]
18 pub use self::flatten::{FlatMap, Flatten};
19 pub use self::fuse::Fuse;
20 use self::zip::try_get_unchecked;
21 #[unstable(feature = "trusted_random_access", issue = "none")]
22 pub use self::zip::TrustedRandomAccess;
23 pub use self::zip::Zip;
25 /// This trait provides transitive access to source-stage in an interator-adapter pipeline
26 /// under the conditions that
27 /// * the iterator source `S` itself implements `SourceIter<Source = S>`
28 /// * there is a delegating implementation of this trait for each adapter in the pipeline between
29 /// the source and the pipeline consumer.
31 /// When the source is an owning iterator struct (commonly called `IntoIter`) then
32 /// this can be useful for specializing [`FromIterator`] implementations or recovering the
33 /// remaining elements after an iterator has been partially exhausted.
35 /// Note that implementations do not necessarily have to provide access to the inner-most
36 /// source of a pipeline. A stateful intermediate adapter might eagerly evaluate a part
37 /// of the pipeline and expose its internal storage as source.
39 /// The trait is unsafe because implementers must uphold additional safety properties.
40 /// See [`as_inner`] for details.
44 /// Retrieving a partially consumed source:
47 /// # #![feature(inplace_iteration)]
48 /// # use std::iter::SourceIter;
50 /// let mut iter = vec![9, 9, 9].into_iter().map(|i| i * i);
51 /// let _ = iter.next();
52 /// let mut remainder = std::mem::replace(unsafe { iter.as_inner() }, Vec::new().into_iter());
53 /// println!("n = {} elements remaining", remainder.len());
56 /// [`FromIterator`]: crate::iter::FromIterator
57 /// [`as_inner`]: SourceIter::as_inner
58 #[unstable(issue = "0", feature = "inplace_iteration")]
59 pub unsafe trait SourceIter {
60 /// A source stage in an iterator pipeline.
61 type Source: Iterator;
63 /// Retrieve the source of an iterator pipeline.
67 /// Implementations of must return the same mutable reference for their lifetime, unless
68 /// replaced by a caller.
69 /// Callers may only replace the reference when they stopped iteration and drop the
70 /// iterator pipeline after extracting the source.
72 /// This means iterator adapters can rely on the source not changing during
73 /// iteration but they cannot rely on it in their Drop implementations.
75 /// Implementing this method means adapters relinquish private-only access to their
76 /// source and can only rely on guarantees made based on method receiver types.
77 /// The lack of restricted access also requires that adapters must uphold the source's
78 /// public API even when they have access to its internals.
80 /// Callers in turn must expect the source to be in any state that is consistent with
81 /// its public API since adapters sitting between it and the source have the same
82 /// access. In particular an adapter may have consumed more elements than strictly necessary.
84 /// The overall goal of these requirements is to let the consumer of a pipeline use
85 /// * whatever remains in the source after iteration has stopped
86 /// * the memory that has become unused by advancing a consuming iterator
88 /// [`next()`]: trait.Iterator.html#method.next
89 unsafe fn as_inner(&mut self) -> &mut Self::Source;
92 /// A double-ended iterator with the direction inverted.
94 /// This `struct` is created by the [`rev`] method on [`Iterator`]. See its
95 /// documentation for more.
97 /// [`rev`]: trait.Iterator.html#method.rev
98 /// [`Iterator`]: trait.Iterator.html
99 #[derive(Clone, Debug)]
100 #[must_use = "iterators are lazy and do nothing unless consumed"]
101 #[stable(feature = "rust1", since = "1.0.0")]
106 pub(super) fn new(iter: T) -> Rev<T> {
111 #[stable(feature = "rust1", since = "1.0.0")]
112 impl<I> Iterator for Rev<I>
114 I: DoubleEndedIterator,
116 type Item = <I as Iterator>::Item;
119 fn next(&mut self) -> Option<<I as Iterator>::Item> {
120 self.iter.next_back()
123 fn size_hint(&self) -> (usize, Option<usize>) {
124 self.iter.size_hint()
128 fn nth(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
129 self.iter.nth_back(n)
132 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
135 F: FnMut(B, Self::Item) -> R,
138 self.iter.try_rfold(init, f)
141 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
143 F: FnMut(Acc, Self::Item) -> Acc,
145 self.iter.rfold(init, f)
149 fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
151 P: FnMut(&Self::Item) -> bool,
153 self.iter.rfind(predicate)
157 #[stable(feature = "rust1", since = "1.0.0")]
158 impl<I> DoubleEndedIterator for Rev<I>
160 I: DoubleEndedIterator,
163 fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
168 fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
172 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
175 F: FnMut(B, Self::Item) -> R,
178 self.iter.try_fold(init, f)
181 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
183 F: FnMut(Acc, Self::Item) -> Acc,
185 self.iter.fold(init, f)
188 fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
190 P: FnMut(&Self::Item) -> bool,
192 self.iter.find(predicate)
196 #[stable(feature = "rust1", since = "1.0.0")]
197 impl<I> ExactSizeIterator for Rev<I>
199 I: ExactSizeIterator + DoubleEndedIterator,
201 fn len(&self) -> usize {
205 fn is_empty(&self) -> bool {
210 #[stable(feature = "fused", since = "1.26.0")]
211 impl<I> FusedIterator for Rev<I> where I: FusedIterator + DoubleEndedIterator {}
213 #[unstable(feature = "trusted_len", issue = "37572")]
214 unsafe impl<I> TrustedLen for Rev<I> where I: TrustedLen + DoubleEndedIterator {}
216 /// An iterator that copies the elements of an underlying iterator.
218 /// This `struct` is created by the [`copied`] method on [`Iterator`]. See its
219 /// documentation for more.
221 /// [`copied`]: trait.Iterator.html#method.copied
222 /// [`Iterator`]: trait.Iterator.html
223 #[stable(feature = "iter_copied", since = "1.36.0")]
224 #[must_use = "iterators are lazy and do nothing unless consumed"]
225 #[derive(Clone, Debug)]
226 pub struct Copied<I> {
231 pub(super) fn new(it: I) -> Copied<I> {
236 fn copy_fold<T: Copy, Acc>(mut f: impl FnMut(Acc, T) -> Acc) -> impl FnMut(Acc, &T) -> Acc {
237 move |acc, &elt| f(acc, elt)
240 fn copy_try_fold<T: Copy, Acc, R>(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R {
241 move |acc, &elt| f(acc, elt)
244 #[stable(feature = "iter_copied", since = "1.36.0")]
245 impl<'a, I, T: 'a> Iterator for Copied<I>
247 I: Iterator<Item = &'a T>,
252 fn next(&mut self) -> Option<T> {
253 self.it.next().copied()
256 fn size_hint(&self) -> (usize, Option<usize>) {
260 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
263 F: FnMut(B, Self::Item) -> R,
266 self.it.try_fold(init, copy_try_fold(f))
269 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
271 F: FnMut(Acc, Self::Item) -> Acc,
273 self.it.fold(init, copy_fold(f))
276 fn nth(&mut self, n: usize) -> Option<T> {
277 self.it.nth(n).copied()
280 fn last(self) -> Option<T> {
281 self.it.last().copied()
284 fn count(self) -> usize {
288 unsafe fn get_unchecked(&mut self, idx: usize) -> T
290 Self: TrustedRandomAccess,
292 // SAFETY: the caller must uphold the contract for
293 // `Iterator::get_unchecked`.
294 *unsafe { try_get_unchecked(&mut self.it, idx) }
298 #[stable(feature = "iter_copied", since = "1.36.0")]
299 impl<'a, I, T: 'a> DoubleEndedIterator for Copied<I>
301 I: DoubleEndedIterator<Item = &'a T>,
304 fn next_back(&mut self) -> Option<T> {
305 self.it.next_back().copied()
308 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
311 F: FnMut(B, Self::Item) -> R,
314 self.it.try_rfold(init, copy_try_fold(f))
317 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
319 F: FnMut(Acc, Self::Item) -> Acc,
321 self.it.rfold(init, copy_fold(f))
325 #[stable(feature = "iter_copied", since = "1.36.0")]
326 impl<'a, I, T: 'a> ExactSizeIterator for Copied<I>
328 I: ExactSizeIterator<Item = &'a T>,
331 fn len(&self) -> usize {
335 fn is_empty(&self) -> bool {
340 #[stable(feature = "iter_copied", since = "1.36.0")]
341 impl<'a, I, T: 'a> FusedIterator for Copied<I>
343 I: FusedIterator<Item = &'a T>,
349 #[unstable(feature = "trusted_random_access", issue = "none")]
350 unsafe impl<I> TrustedRandomAccess for Copied<I>
352 I: TrustedRandomAccess,
355 fn may_have_side_effect() -> bool {
356 I::may_have_side_effect()
360 #[stable(feature = "iter_copied", since = "1.36.0")]
361 unsafe impl<'a, I, T: 'a> TrustedLen for Copied<I>
363 I: TrustedLen<Item = &'a T>,
368 /// An iterator that clones the elements of an underlying iterator.
370 /// This `struct` is created by the [`cloned`] method on [`Iterator`]. See its
371 /// documentation for more.
373 /// [`cloned`]: trait.Iterator.html#method.cloned
374 /// [`Iterator`]: trait.Iterator.html
375 #[stable(feature = "iter_cloned", since = "1.1.0")]
376 #[must_use = "iterators are lazy and do nothing unless consumed"]
377 #[derive(Clone, Debug)]
378 pub struct Cloned<I> {
382 pub(super) fn new(it: I) -> Cloned<I> {
387 fn clone_try_fold<T: Clone, Acc, R>(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R {
388 move |acc, elt| f(acc, elt.clone())
391 #[stable(feature = "iter_cloned", since = "1.1.0")]
392 impl<'a, I, T: 'a> Iterator for Cloned<I>
394 I: Iterator<Item = &'a T>,
399 fn next(&mut self) -> Option<T> {
400 self.it.next().cloned()
403 fn size_hint(&self) -> (usize, Option<usize>) {
407 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
410 F: FnMut(B, Self::Item) -> R,
413 self.it.try_fold(init, clone_try_fold(f))
416 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
418 F: FnMut(Acc, Self::Item) -> Acc,
420 self.it.map(T::clone).fold(init, f)
423 unsafe fn get_unchecked(&mut self, idx: usize) -> T
425 Self: TrustedRandomAccess,
427 // SAFETY: the caller must uphold the contract for
428 // `Iterator::get_unchecked`.
429 unsafe { try_get_unchecked(&mut self.it, idx).clone() }
433 #[stable(feature = "iter_cloned", since = "1.1.0")]
434 impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
436 I: DoubleEndedIterator<Item = &'a T>,
439 fn next_back(&mut self) -> Option<T> {
440 self.it.next_back().cloned()
443 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
446 F: FnMut(B, Self::Item) -> R,
449 self.it.try_rfold(init, clone_try_fold(f))
452 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
454 F: FnMut(Acc, Self::Item) -> Acc,
456 self.it.map(T::clone).rfold(init, f)
460 #[stable(feature = "iter_cloned", since = "1.1.0")]
461 impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
463 I: ExactSizeIterator<Item = &'a T>,
466 fn len(&self) -> usize {
470 fn is_empty(&self) -> bool {
475 #[stable(feature = "fused", since = "1.26.0")]
476 impl<'a, I, T: 'a> FusedIterator for Cloned<I>
478 I: FusedIterator<Item = &'a T>,
484 #[unstable(feature = "trusted_random_access", issue = "none")]
485 unsafe impl<I> TrustedRandomAccess for Cloned<I>
487 I: TrustedRandomAccess,
491 fn may_have_side_effect() -> bool {
496 #[unstable(feature = "trusted_len", issue = "37572")]
497 unsafe impl<'a, I, T: 'a> TrustedLen for Cloned<I>
499 I: TrustedLen<Item = &'a T>,
504 /// An iterator that repeats endlessly.
506 /// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its
507 /// documentation for more.
509 /// [`cycle`]: trait.Iterator.html#method.cycle
510 /// [`Iterator`]: trait.Iterator.html
511 #[derive(Clone, Debug)]
512 #[must_use = "iterators are lazy and do nothing unless consumed"]
513 #[stable(feature = "rust1", since = "1.0.0")]
514 pub struct Cycle<I> {
518 impl<I: Clone> Cycle<I> {
519 pub(super) fn new(iter: I) -> Cycle<I> {
520 Cycle { orig: iter.clone(), iter }
524 #[stable(feature = "rust1", since = "1.0.0")]
525 impl<I> Iterator for Cycle<I>
529 type Item = <I as Iterator>::Item;
532 fn next(&mut self) -> Option<<I as Iterator>::Item> {
533 match self.iter.next() {
535 self.iter = self.orig.clone();
543 fn size_hint(&self) -> (usize, Option<usize>) {
544 // the cycle iterator is either empty or infinite
545 match self.orig.size_hint() {
546 sz @ (0, Some(0)) => sz,
548 _ => (usize::MAX, None),
553 fn try_fold<Acc, F, R>(&mut self, mut acc: Acc, mut f: F) -> R
555 F: FnMut(Acc, Self::Item) -> R,
558 // fully iterate the current iterator. this is necessary because
559 // `self.iter` may be empty even when `self.orig` isn't
560 acc = self.iter.try_fold(acc, &mut f)?;
561 self.iter = self.orig.clone();
563 // complete a full cycle, keeping track of whether the cycled
564 // iterator is empty or not. we need to return early in case
565 // of an empty iterator to prevent an infinite loop
566 let mut is_empty = true;
567 acc = self.iter.try_fold(acc, |acc, x| {
573 return Try::from_ok(acc);
577 self.iter = self.orig.clone();
578 acc = self.iter.try_fold(acc, &mut f)?;
582 // No `fold` override, because `fold` doesn't make much sense for `Cycle`,
583 // and we can't do anything better than the default.
586 #[stable(feature = "fused", since = "1.26.0")]
587 impl<I> FusedIterator for Cycle<I> where I: Clone + Iterator {}
589 /// An iterator for stepping iterators by a custom amount.
591 /// This `struct` is created by the [`step_by`] method on [`Iterator`]. See
592 /// its documentation for more.
594 /// [`step_by`]: trait.Iterator.html#method.step_by
595 /// [`Iterator`]: trait.Iterator.html
596 #[must_use = "iterators are lazy and do nothing unless consumed"]
597 #[stable(feature = "iterator_step_by", since = "1.28.0")]
598 #[derive(Clone, Debug)]
599 pub struct StepBy<I> {
605 pub(super) fn new(iter: I, step: usize) -> StepBy<I> {
607 StepBy { iter, step: step - 1, first_take: true }
611 #[stable(feature = "iterator_step_by", since = "1.28.0")]
612 impl<I> Iterator for StepBy<I>
619 fn next(&mut self) -> Option<Self::Item> {
621 self.first_take = false;
624 self.iter.nth(self.step)
629 fn size_hint(&self) -> (usize, Option<usize>) {
631 fn first_size(step: usize) -> impl Fn(usize) -> usize {
632 move |n| if n == 0 { 0 } else { 1 + (n - 1) / (step + 1) }
636 fn other_size(step: usize) -> impl Fn(usize) -> usize {
637 move |n| n / (step + 1)
640 let (low, high) = self.iter.size_hint();
643 let f = first_size(self.step);
644 (f(low), high.map(f))
646 let f = other_size(self.step);
647 (f(low), high.map(f))
652 fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
654 self.first_take = false;
655 let first = self.iter.next();
661 // n and self.step are indices, we need to add 1 to get the amount of elements
662 // When calling `.nth`, we need to subtract 1 again to convert back to an index
663 // step + 1 can't overflow because `.step_by` sets `self.step` to `step - 1`
664 let mut step = self.step + 1;
665 // n + 1 could overflow
666 // thus, if n is usize::MAX, instead of adding one, we call .nth(step)
668 self.iter.nth(step - 1);
675 let mul = n.checked_mul(step);
677 if intrinsics::likely(mul.is_some()) {
678 return self.iter.nth(mul.unwrap() - 1);
681 let div_n = usize::MAX / n;
682 let div_step = usize::MAX / step;
683 let nth_n = div_n * n;
684 let nth_step = div_step * step;
685 let nth = if nth_n > nth_step {
692 self.iter.nth(nth - 1);
696 fn try_fold<Acc, F, R>(&mut self, mut acc: Acc, mut f: F) -> R
698 F: FnMut(Acc, Self::Item) -> R,
702 fn nth<I: Iterator>(iter: &mut I, step: usize) -> impl FnMut() -> Option<I::Item> + '_ {
703 move || iter.nth(step)
707 self.first_take = false;
708 match self.iter.next() {
709 None => return Try::from_ok(acc),
710 Some(x) => acc = f(acc, x)?,
713 from_fn(nth(&mut self.iter, self.step)).try_fold(acc, f)
716 fn fold<Acc, F>(mut self, mut acc: Acc, mut f: F) -> Acc
718 F: FnMut(Acc, Self::Item) -> Acc,
721 fn nth<I: Iterator>(iter: &mut I, step: usize) -> impl FnMut() -> Option<I::Item> + '_ {
722 move || iter.nth(step)
726 self.first_take = false;
727 match self.iter.next() {
729 Some(x) => acc = f(acc, x),
732 from_fn(nth(&mut self.iter, self.step)).fold(acc, f)
738 I: ExactSizeIterator,
740 // The zero-based index starting from the end of the iterator of the
741 // last element. Used in the `DoubleEndedIterator` implementation.
742 fn next_back_index(&self) -> usize {
743 let rem = self.iter.len() % (self.step + 1);
745 if rem == 0 { self.step } else { rem - 1 }
752 #[stable(feature = "double_ended_step_by_iterator", since = "1.38.0")]
753 impl<I> DoubleEndedIterator for StepBy<I>
755 I: DoubleEndedIterator + ExactSizeIterator,
758 fn next_back(&mut self) -> Option<Self::Item> {
759 self.iter.nth_back(self.next_back_index())
763 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
764 // `self.iter.nth_back(usize::MAX)` does the right thing here when `n`
765 // is out of bounds because the length of `self.iter` does not exceed
766 // `usize::MAX` (because `I: ExactSizeIterator`) and `nth_back` is
768 let n = n.saturating_mul(self.step + 1).saturating_add(self.next_back_index());
769 self.iter.nth_back(n)
772 fn try_rfold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R
774 F: FnMut(Acc, Self::Item) -> R,
778 fn nth_back<I: DoubleEndedIterator>(
781 ) -> impl FnMut() -> Option<I::Item> + '_ {
782 move || iter.nth_back(step)
785 match self.next_back() {
786 None => Try::from_ok(init),
788 let acc = f(init, x)?;
789 from_fn(nth_back(&mut self.iter, self.step)).try_fold(acc, f)
795 fn rfold<Acc, F>(mut self, init: Acc, mut f: F) -> Acc
798 F: FnMut(Acc, Self::Item) -> Acc,
801 fn nth_back<I: DoubleEndedIterator>(
804 ) -> impl FnMut() -> Option<I::Item> + '_ {
805 move || iter.nth_back(step)
808 match self.next_back() {
811 let acc = f(init, x);
812 from_fn(nth_back(&mut self.iter, self.step)).fold(acc, f)
818 // StepBy can only make the iterator shorter, so the len will still fit.
819 #[stable(feature = "iterator_step_by", since = "1.28.0")]
820 impl<I> ExactSizeIterator for StepBy<I> where I: ExactSizeIterator {}
822 /// An iterator that maps the values of `iter` with `f`.
824 /// This `struct` is created by the [`map`] method on [`Iterator`]. See its
825 /// documentation for more.
827 /// [`map`]: trait.Iterator.html#method.map
828 /// [`Iterator`]: trait.Iterator.html
830 /// # Notes about side effects
832 /// The [`map`] iterator implements [`DoubleEndedIterator`], meaning that
833 /// you can also [`map`] backwards:
836 /// let v: Vec<i32> = vec![1, 2, 3].into_iter().map(|x| x + 1).rev().collect();
838 /// assert_eq!(v, [4, 3, 2]);
841 /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
843 /// But if your closure has state, iterating backwards may act in a way you do
844 /// not expect. Let's go through an example. First, in the forward direction:
849 /// for pair in vec!['a', 'b', 'c'].into_iter()
850 /// .map(|letter| { c += 1; (letter, c) }) {
851 /// println!("{:?}", pair);
855 /// This will print "('a', 1), ('b', 2), ('c', 3)".
857 /// Now consider this twist where we add a call to `rev`. This version will
858 /// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed,
859 /// but the values of the counter still go in order. This is because `map()` is
860 /// still being called lazily on each item, but we are popping items off the
861 /// back of the vector now, instead of shifting them from the front.
866 /// for pair in vec!['a', 'b', 'c'].into_iter()
867 /// .map(|letter| { c += 1; (letter, c) })
869 /// println!("{:?}", pair);
872 #[must_use = "iterators are lazy and do nothing unless consumed"]
873 #[stable(feature = "rust1", since = "1.0.0")]
875 pub struct Map<I, F> {
879 impl<I, F> Map<I, F> {
880 pub(super) fn new(iter: I, f: F) -> Map<I, F> {
885 #[stable(feature = "core_impl_debug", since = "1.9.0")]
886 impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> {
887 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
888 f.debug_struct("Map").field("iter", &self.iter).finish()
892 fn map_fold<T, B, Acc>(
893 mut f: impl FnMut(T) -> B,
894 mut g: impl FnMut(Acc, B) -> Acc,
895 ) -> impl FnMut(Acc, T) -> Acc {
896 move |acc, elt| g(acc, f(elt))
899 fn map_try_fold<'a, T, B, Acc, R>(
900 f: &'a mut impl FnMut(T) -> B,
901 mut g: impl FnMut(Acc, B) -> R + 'a,
902 ) -> impl FnMut(Acc, T) -> R + 'a {
903 move |acc, elt| g(acc, f(elt))
906 #[stable(feature = "rust1", since = "1.0.0")]
907 impl<B, I: Iterator, F> Iterator for Map<I, F>
909 F: FnMut(I::Item) -> B,
914 fn next(&mut self) -> Option<B> {
915 self.iter.next().map(&mut self.f)
919 fn size_hint(&self) -> (usize, Option<usize>) {
920 self.iter.size_hint()
923 fn try_fold<Acc, G, R>(&mut self, init: Acc, g: G) -> R
926 G: FnMut(Acc, Self::Item) -> R,
929 self.iter.try_fold(init, map_try_fold(&mut self.f, g))
932 fn fold<Acc, G>(self, init: Acc, g: G) -> Acc
934 G: FnMut(Acc, Self::Item) -> Acc,
936 self.iter.fold(init, map_fold(self.f, g))
939 unsafe fn get_unchecked(&mut self, idx: usize) -> B
941 Self: TrustedRandomAccess,
943 // SAFETY: the caller must uphold the contract for
944 // `Iterator::get_unchecked`.
945 unsafe { (self.f)(try_get_unchecked(&mut self.iter, idx)) }
949 #[stable(feature = "rust1", since = "1.0.0")]
950 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F>
952 F: FnMut(I::Item) -> B,
955 fn next_back(&mut self) -> Option<B> {
956 self.iter.next_back().map(&mut self.f)
959 fn try_rfold<Acc, G, R>(&mut self, init: Acc, g: G) -> R
962 G: FnMut(Acc, Self::Item) -> R,
965 self.iter.try_rfold(init, map_try_fold(&mut self.f, g))
968 fn rfold<Acc, G>(self, init: Acc, g: G) -> Acc
970 G: FnMut(Acc, Self::Item) -> Acc,
972 self.iter.rfold(init, map_fold(self.f, g))
976 #[stable(feature = "rust1", since = "1.0.0")]
977 impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F>
979 F: FnMut(I::Item) -> B,
981 fn len(&self) -> usize {
985 fn is_empty(&self) -> bool {
990 #[stable(feature = "fused", since = "1.26.0")]
991 impl<B, I: FusedIterator, F> FusedIterator for Map<I, F> where F: FnMut(I::Item) -> B {}
993 #[unstable(feature = "trusted_len", issue = "37572")]
994 unsafe impl<B, I, F> TrustedLen for Map<I, F>
997 F: FnMut(I::Item) -> B,
1002 #[unstable(feature = "trusted_random_access", issue = "none")]
1003 unsafe impl<I, F> TrustedRandomAccess for Map<I, F>
1005 I: TrustedRandomAccess,
1008 fn may_have_side_effect() -> bool {
1013 #[unstable(issue = "0", feature = "inplace_iteration")]
1014 unsafe impl<S: Iterator, B, I: Iterator, F> SourceIter for Map<I, F>
1016 F: FnMut(I::Item) -> B,
1017 I: SourceIter<Source = S>,
1022 unsafe fn as_inner(&mut self) -> &mut S {
1023 // Safety: unsafe function forwarding to unsafe function with the same requirements
1024 unsafe { SourceIter::as_inner(&mut self.iter) }
1028 #[unstable(issue = "0", feature = "inplace_iteration")]
1029 unsafe impl<B, I: InPlaceIterable, F> InPlaceIterable for Map<I, F> where F: FnMut(I::Item) -> B {}
1031 /// An iterator that filters the elements of `iter` with `predicate`.
1033 /// This `struct` is created by the [`filter`] method on [`Iterator`]. See its
1034 /// documentation for more.
1036 /// [`filter`]: trait.Iterator.html#method.filter
1037 /// [`Iterator`]: trait.Iterator.html
1038 #[must_use = "iterators are lazy and do nothing unless consumed"]
1039 #[stable(feature = "rust1", since = "1.0.0")]
1041 pub struct Filter<I, P> {
1045 impl<I, P> Filter<I, P> {
1046 pub(super) fn new(iter: I, predicate: P) -> Filter<I, P> {
1047 Filter { iter, predicate }
1051 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1052 impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
1053 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1054 f.debug_struct("Filter").field("iter", &self.iter).finish()
1058 fn filter_fold<T, Acc>(
1059 mut predicate: impl FnMut(&T) -> bool,
1060 mut fold: impl FnMut(Acc, T) -> Acc,
1061 ) -> impl FnMut(Acc, T) -> Acc {
1062 move |acc, item| if predicate(&item) { fold(acc, item) } else { acc }
1065 fn filter_try_fold<'a, T, Acc, R: Try<Ok = Acc>>(
1066 predicate: &'a mut impl FnMut(&T) -> bool,
1067 mut fold: impl FnMut(Acc, T) -> R + 'a,
1068 ) -> impl FnMut(Acc, T) -> R + 'a {
1069 move |acc, item| if predicate(&item) { fold(acc, item) } else { R::from_ok(acc) }
1072 #[stable(feature = "rust1", since = "1.0.0")]
1073 impl<I: Iterator, P> Iterator for Filter<I, P>
1075 P: FnMut(&I::Item) -> bool,
1077 type Item = I::Item;
1080 fn next(&mut self) -> Option<I::Item> {
1081 self.iter.find(&mut self.predicate)
1085 fn size_hint(&self) -> (usize, Option<usize>) {
1086 let (_, upper) = self.iter.size_hint();
1087 (0, upper) // can't know a lower bound, due to the predicate
1090 // this special case allows the compiler to make `.filter(_).count()`
1091 // branchless. Barring perfect branch prediction (which is unattainable in
1092 // the general case), this will be much faster in >90% of cases (containing
1093 // virtually all real workloads) and only a tiny bit slower in the rest.
1095 // Having this specialization thus allows us to write `.filter(p).count()`
1096 // where we would otherwise write `.map(|x| p(x) as usize).sum()`, which is
1097 // less readable and also less backwards-compatible to Rust before 1.10.
1099 // Using the branchless version will also simplify the LLVM byte code, thus
1100 // leaving more budget for LLVM optimizations.
1102 fn count(self) -> usize {
1104 fn to_usize<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut(T) -> usize {
1105 move |x| predicate(&x) as usize
1108 self.iter.map(to_usize(self.predicate)).sum()
1112 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1115 Fold: FnMut(Acc, Self::Item) -> R,
1118 self.iter.try_fold(init, filter_try_fold(&mut self.predicate, fold))
1122 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1124 Fold: FnMut(Acc, Self::Item) -> Acc,
1126 self.iter.fold(init, filter_fold(self.predicate, fold))
1130 #[stable(feature = "rust1", since = "1.0.0")]
1131 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
1133 P: FnMut(&I::Item) -> bool,
1136 fn next_back(&mut self) -> Option<I::Item> {
1137 self.iter.rfind(&mut self.predicate)
1141 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1144 Fold: FnMut(Acc, Self::Item) -> R,
1147 self.iter.try_rfold(init, filter_try_fold(&mut self.predicate, fold))
1151 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1153 Fold: FnMut(Acc, Self::Item) -> Acc,
1155 self.iter.rfold(init, filter_fold(self.predicate, fold))
1159 #[stable(feature = "fused", since = "1.26.0")]
1160 impl<I: FusedIterator, P> FusedIterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {}
1162 #[unstable(issue = "0", feature = "inplace_iteration")]
1163 unsafe impl<S: Iterator, P, I: Iterator> SourceIter for Filter<I, P> where
1164 P: FnMut(&I::Item) -> bool,
1165 I: SourceIter<Source = S>
1170 unsafe fn as_inner(&mut self) -> &mut S {
1171 // Safety: unsafe function forwarding to unsafe function with the same requirements
1172 unsafe { SourceIter::as_inner(&mut self.iter) }
1176 #[unstable(issue = "0", feature = "inplace_iteration")]
1177 unsafe impl<I: InPlaceIterable, P> InPlaceIterable for Filter<I, P>
1178 where P: FnMut(&I::Item) -> bool {}
1180 /// An iterator that uses `f` to both filter and map elements from `iter`.
1182 /// This `struct` is created by the [`filter_map`] method on [`Iterator`]. See its
1183 /// documentation for more.
1185 /// [`filter_map`]: trait.Iterator.html#method.filter_map
1186 /// [`Iterator`]: trait.Iterator.html
1187 #[must_use = "iterators are lazy and do nothing unless consumed"]
1188 #[stable(feature = "rust1", since = "1.0.0")]
1190 pub struct FilterMap<I, F> {
1194 impl<I, F> FilterMap<I, F> {
1195 pub(super) fn new(iter: I, f: F) -> FilterMap<I, F> {
1196 FilterMap { iter, f }
1200 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1201 impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> {
1202 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1203 f.debug_struct("FilterMap").field("iter", &self.iter).finish()
1207 fn filter_map_fold<T, B, Acc>(
1208 mut f: impl FnMut(T) -> Option<B>,
1209 mut fold: impl FnMut(Acc, B) -> Acc,
1210 ) -> impl FnMut(Acc, T) -> Acc {
1211 move |acc, item| match f(item) {
1212 Some(x) => fold(acc, x),
1217 fn filter_map_try_fold<'a, T, B, Acc, R: Try<Ok = Acc>>(
1218 f: &'a mut impl FnMut(T) -> Option<B>,
1219 mut fold: impl FnMut(Acc, B) -> R + 'a,
1220 ) -> impl FnMut(Acc, T) -> R + 'a {
1221 move |acc, item| match f(item) {
1222 Some(x) => fold(acc, x),
1223 None => R::from_ok(acc),
1227 #[stable(feature = "rust1", since = "1.0.0")]
1228 impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
1230 F: FnMut(I::Item) -> Option<B>,
1235 fn next(&mut self) -> Option<B> {
1236 self.iter.find_map(&mut self.f)
1240 fn size_hint(&self) -> (usize, Option<usize>) {
1241 let (_, upper) = self.iter.size_hint();
1242 (0, upper) // can't know a lower bound, due to the predicate
1246 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1249 Fold: FnMut(Acc, Self::Item) -> R,
1252 self.iter.try_fold(init, filter_map_try_fold(&mut self.f, fold))
1256 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1258 Fold: FnMut(Acc, Self::Item) -> Acc,
1260 self.iter.fold(init, filter_map_fold(self.f, fold))
1264 #[stable(feature = "rust1", since = "1.0.0")]
1265 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
1267 F: FnMut(I::Item) -> Option<B>,
1270 fn next_back(&mut self) -> Option<B> {
1273 f: &mut impl FnMut(T) -> Option<B>,
1274 ) -> impl FnMut((), T) -> ControlFlow<(), B> + '_ {
1275 move |(), x| match f(x) {
1276 Some(x) => ControlFlow::Break(x),
1277 None => ControlFlow::Continue(()),
1281 self.iter.try_rfold((), find(&mut self.f)).break_value()
1285 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1288 Fold: FnMut(Acc, Self::Item) -> R,
1291 self.iter.try_rfold(init, filter_map_try_fold(&mut self.f, fold))
1295 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1297 Fold: FnMut(Acc, Self::Item) -> Acc,
1299 self.iter.rfold(init, filter_map_fold(self.f, fold))
1303 #[stable(feature = "fused", since = "1.26.0")]
1304 impl<B, I: FusedIterator, F> FusedIterator for FilterMap<I, F> where F: FnMut(I::Item) -> Option<B> {}
1306 #[unstable(issue = "0", feature = "inplace_iteration")]
1307 unsafe impl<S: Iterator, B, I: Iterator, F> SourceIter for FilterMap<I, F> where
1308 F: FnMut(I::Item) -> Option<B>,
1309 I: SourceIter<Source = S>
1314 unsafe fn as_inner(&mut self) -> &mut S {
1315 // Safety: unsafe function forwarding to unsafe function with the same requirements
1316 unsafe { SourceIter::as_inner(&mut self.iter) }
1320 #[unstable(issue = "0", feature = "inplace_iteration")]
1321 unsafe impl<B, I: InPlaceIterable, F> InPlaceIterable for FilterMap<I, F>
1322 where F: FnMut(I::Item) -> Option<B> {}
1325 /// An iterator that yields the current count and the element during iteration.
1327 /// This `struct` is created by the [`enumerate`] method on [`Iterator`]. See its
1328 /// documentation for more.
1330 /// [`enumerate`]: trait.Iterator.html#method.enumerate
1331 /// [`Iterator`]: trait.Iterator.html
1332 #[derive(Clone, Debug)]
1333 #[must_use = "iterators are lazy and do nothing unless consumed"]
1334 #[stable(feature = "rust1", since = "1.0.0")]
1335 pub struct Enumerate<I> {
1339 impl<I> Enumerate<I> {
1340 pub(super) fn new(iter: I) -> Enumerate<I> {
1341 Enumerate { iter, count: 0 }
1345 #[stable(feature = "rust1", since = "1.0.0")]
1346 impl<I> Iterator for Enumerate<I>
1350 type Item = (usize, <I as Iterator>::Item);
1352 /// # Overflow Behavior
1354 /// The method does no guarding against overflows, so enumerating more than
1355 /// `usize::MAX` elements either produces the wrong result or panics. If
1356 /// debug assertions are enabled, a panic is guaranteed.
1360 /// Might panic if the index of the element overflows a `usize`.
1362 fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1363 let a = self.iter.next()?;
1365 // Possible undefined overflow.
1366 AddAssign::add_assign(&mut self.count, 1);
1371 fn size_hint(&self) -> (usize, Option<usize>) {
1372 self.iter.size_hint()
1376 fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
1377 let a = self.iter.nth(n)?;
1378 // Possible undefined overflow.
1379 let i = Add::add(self.count, n);
1380 self.count = Add::add(i, 1);
1385 fn count(self) -> usize {
1390 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1393 Fold: FnMut(Acc, Self::Item) -> R,
1397 fn enumerate<'a, T, Acc, R>(
1398 count: &'a mut usize,
1399 mut fold: impl FnMut(Acc, (usize, T)) -> R + 'a,
1400 ) -> impl FnMut(Acc, T) -> R + 'a {
1402 let acc = fold(acc, (*count, item));
1403 // Possible undefined overflow.
1404 AddAssign::add_assign(count, 1);
1409 self.iter.try_fold(init, enumerate(&mut self.count, fold))
1413 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1415 Fold: FnMut(Acc, Self::Item) -> Acc,
1418 fn enumerate<T, Acc>(
1420 mut fold: impl FnMut(Acc, (usize, T)) -> Acc,
1421 ) -> impl FnMut(Acc, T) -> Acc {
1423 let acc = fold(acc, (count, item));
1424 // Possible undefined overflow.
1425 AddAssign::add_assign(&mut count, 1);
1430 self.iter.fold(init, enumerate(self.count, fold))
1433 unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item
1435 Self: TrustedRandomAccess,
1437 // SAFETY: the caller must uphold the contract for
1438 // `Iterator::get_unchecked`.
1439 let value = unsafe { try_get_unchecked(&mut self.iter, idx) };
1440 (Add::add(self.count, idx), value)
1444 #[stable(feature = "rust1", since = "1.0.0")]
1445 impl<I> DoubleEndedIterator for Enumerate<I>
1447 I: ExactSizeIterator + DoubleEndedIterator,
1450 fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1451 let a = self.iter.next_back()?;
1452 let len = self.iter.len();
1453 // Can safely add, `ExactSizeIterator` promises that the number of
1454 // elements fits into a `usize`.
1455 Some((self.count + len, a))
1459 fn nth_back(&mut self, n: usize) -> Option<(usize, <I as Iterator>::Item)> {
1460 let a = self.iter.nth_back(n)?;
1461 let len = self.iter.len();
1462 // Can safely add, `ExactSizeIterator` promises that the number of
1463 // elements fits into a `usize`.
1464 Some((self.count + len, a))
1468 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1471 Fold: FnMut(Acc, Self::Item) -> R,
1474 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1475 // that the number of elements fits into a `usize`.
1476 fn enumerate<T, Acc, R>(
1478 mut fold: impl FnMut(Acc, (usize, T)) -> R,
1479 ) -> impl FnMut(Acc, T) -> R {
1482 fold(acc, (count, item))
1486 let count = self.count + self.iter.len();
1487 self.iter.try_rfold(init, enumerate(count, fold))
1491 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1493 Fold: FnMut(Acc, Self::Item) -> Acc,
1495 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1496 // that the number of elements fits into a `usize`.
1497 fn enumerate<T, Acc>(
1499 mut fold: impl FnMut(Acc, (usize, T)) -> Acc,
1500 ) -> impl FnMut(Acc, T) -> Acc {
1503 fold(acc, (count, item))
1507 let count = self.count + self.iter.len();
1508 self.iter.rfold(init, enumerate(count, fold))
1512 #[stable(feature = "rust1", since = "1.0.0")]
1513 impl<I> ExactSizeIterator for Enumerate<I>
1515 I: ExactSizeIterator,
1517 fn len(&self) -> usize {
1521 fn is_empty(&self) -> bool {
1522 self.iter.is_empty()
1527 #[unstable(feature = "trusted_random_access", issue = "none")]
1528 unsafe impl<I> TrustedRandomAccess for Enumerate<I>
1530 I: TrustedRandomAccess,
1532 fn may_have_side_effect() -> bool {
1533 I::may_have_side_effect()
1537 #[stable(feature = "fused", since = "1.26.0")]
1538 impl<I> FusedIterator for Enumerate<I> where I: FusedIterator {}
1540 #[unstable(feature = "trusted_len", issue = "37572")]
1541 unsafe impl<I> TrustedLen for Enumerate<I> where I: TrustedLen {}
1543 #[unstable(issue = "0", feature = "inplace_iteration")]
1544 unsafe impl<S: Iterator, I: Iterator> SourceIter for Enumerate<I>
1546 I: SourceIter<Source = S>,
1551 unsafe fn as_inner(&mut self) -> &mut S {
1552 // Safety: unsafe function forwarding to unsafe function with the same requirements
1553 unsafe { SourceIter::as_inner(&mut self.iter) }
1557 #[unstable(issue = "0", feature = "inplace_iteration")]
1558 unsafe impl<I: InPlaceIterable> InPlaceIterable for Enumerate<I> {}
1560 /// An iterator with a `peek()` that returns an optional reference to the next
1563 /// This `struct` is created by the [`peekable`] method on [`Iterator`]. See its
1564 /// documentation for more.
1566 /// [`peekable`]: trait.Iterator.html#method.peekable
1567 /// [`Iterator`]: trait.Iterator.html
1568 #[derive(Clone, Debug)]
1569 #[must_use = "iterators are lazy and do nothing unless consumed"]
1570 #[stable(feature = "rust1", since = "1.0.0")]
1571 pub struct Peekable<I: Iterator> {
1573 /// Remember a peeked value, even if it was None.
1574 peeked: Option<Option<I::Item>>,
1576 impl<I: Iterator> Peekable<I> {
1577 pub(super) fn new(iter: I) -> Peekable<I> {
1578 Peekable { iter, peeked: None }
1582 // Peekable must remember if a None has been seen in the `.peek()` method.
1583 // It ensures that `.peek(); .peek();` or `.peek(); .next();` only advances the
1584 // underlying iterator at most once. This does not by itself make the iterator
1586 #[stable(feature = "rust1", since = "1.0.0")]
1587 impl<I: Iterator> Iterator for Peekable<I> {
1588 type Item = I::Item;
1591 fn next(&mut self) -> Option<I::Item> {
1592 match self.peeked.take() {
1594 None => self.iter.next(),
1599 #[rustc_inherit_overflow_checks]
1600 fn count(mut self) -> usize {
1601 match self.peeked.take() {
1603 Some(Some(_)) => 1 + self.iter.count(),
1604 None => self.iter.count(),
1609 fn nth(&mut self, n: usize) -> Option<I::Item> {
1610 match self.peeked.take() {
1612 Some(v @ Some(_)) if n == 0 => v,
1613 Some(Some(_)) => self.iter.nth(n - 1),
1614 None => self.iter.nth(n),
1619 fn last(mut self) -> Option<I::Item> {
1620 let peek_opt = match self.peeked.take() {
1621 Some(None) => return None,
1625 self.iter.last().or(peek_opt)
1629 fn size_hint(&self) -> (usize, Option<usize>) {
1630 let peek_len = match self.peeked {
1631 Some(None) => return (0, Some(0)),
1635 let (lo, hi) = self.iter.size_hint();
1636 let lo = lo.saturating_add(peek_len);
1638 Some(x) => x.checked_add(peek_len),
1645 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
1648 F: FnMut(B, Self::Item) -> R,
1651 let acc = match self.peeked.take() {
1652 Some(None) => return Try::from_ok(init),
1653 Some(Some(v)) => f(init, v)?,
1656 self.iter.try_fold(acc, f)
1660 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1662 Fold: FnMut(Acc, Self::Item) -> Acc,
1664 let acc = match self.peeked {
1665 Some(None) => return init,
1666 Some(Some(v)) => fold(init, v),
1669 self.iter.fold(acc, fold)
1673 #[stable(feature = "double_ended_peek_iterator", since = "1.38.0")]
1674 impl<I> DoubleEndedIterator for Peekable<I>
1676 I: DoubleEndedIterator,
1679 fn next_back(&mut self) -> Option<Self::Item> {
1680 match self.peeked.as_mut() {
1681 Some(v @ Some(_)) => self.iter.next_back().or_else(|| v.take()),
1683 None => self.iter.next_back(),
1688 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
1691 F: FnMut(B, Self::Item) -> R,
1694 match self.peeked.take() {
1695 Some(None) => Try::from_ok(init),
1696 Some(Some(v)) => match self.iter.try_rfold(init, &mut f).into_result() {
1697 Ok(acc) => f(acc, v),
1699 self.peeked = Some(Some(v));
1703 None => self.iter.try_rfold(init, f),
1708 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1710 Fold: FnMut(Acc, Self::Item) -> Acc,
1715 let acc = self.iter.rfold(init, &mut fold);
1718 None => self.iter.rfold(init, fold),
1723 #[stable(feature = "rust1", since = "1.0.0")]
1724 impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
1726 #[stable(feature = "fused", since = "1.26.0")]
1727 impl<I: FusedIterator> FusedIterator for Peekable<I> {}
1729 impl<I: Iterator> Peekable<I> {
1730 /// Returns a reference to the next() value without advancing the iterator.
1732 /// Like [`next`], if there is a value, it is wrapped in a `Some(T)`.
1733 /// But if the iteration is over, `None` is returned.
1735 /// [`next`]: trait.Iterator.html#tymethod.next
1737 /// Because `peek()` returns a reference, and many iterators iterate over
1738 /// references, there can be a possibly confusing situation where the
1739 /// return value is a double reference. You can see this effect in the
1747 /// let xs = [1, 2, 3];
1749 /// let mut iter = xs.iter().peekable();
1751 /// // peek() lets us see into the future
1752 /// assert_eq!(iter.peek(), Some(&&1));
1753 /// assert_eq!(iter.next(), Some(&1));
1755 /// assert_eq!(iter.next(), Some(&2));
1757 /// // The iterator does not advance even if we `peek` multiple times
1758 /// assert_eq!(iter.peek(), Some(&&3));
1759 /// assert_eq!(iter.peek(), Some(&&3));
1761 /// assert_eq!(iter.next(), Some(&3));
1763 /// // After the iterator is finished, so is `peek()`
1764 /// assert_eq!(iter.peek(), None);
1765 /// assert_eq!(iter.next(), None);
1768 #[stable(feature = "rust1", since = "1.0.0")]
1769 pub fn peek(&mut self) -> Option<&I::Item> {
1770 let iter = &mut self.iter;
1771 self.peeked.get_or_insert_with(|| iter.next()).as_ref()
1774 /// Consume the next value of this iterator if a condition is true.
1776 /// If `func` returns `true` for the next value of this iterator, consume and return it.
1777 /// Otherwise, return `None`.
1780 /// Consume a number if it's equal to 0.
1782 /// #![feature(peekable_next_if)]
1783 /// let mut iter = (0..5).peekable();
1784 /// // The first item of the iterator is 0; consume it.
1785 /// assert_eq!(iter.next_if(|&x| x == 0), Some(0));
1786 /// // The next item returned is now 1, so `consume` will return `false`.
1787 /// assert_eq!(iter.next_if(|&x| x == 0), None);
1788 /// // `next_if` saves the value of the next item if it was not equal to `expected`.
1789 /// assert_eq!(iter.next(), Some(1));
1792 /// Consume any number less than 10.
1794 /// #![feature(peekable_next_if)]
1795 /// let mut iter = (1..20).peekable();
1796 /// // Consume all numbers less than 10
1797 /// while iter.next_if(|&x| x < 10).is_some() {}
1798 /// // The next value returned will be 10
1799 /// assert_eq!(iter.next(), Some(10));
1801 #[unstable(feature = "peekable_next_if", issue = "72480")]
1802 pub fn next_if(&mut self, func: impl FnOnce(&I::Item) -> bool) -> Option<I::Item> {
1804 Some(matched) if func(&matched) => Some(matched),
1806 // Since we called `self.next()`, we consumed `self.peeked`.
1807 assert!(self.peeked.is_none());
1808 self.peeked = Some(other);
1814 /// Consume the next item if it is equal to `expected`.
1817 /// Consume a number if it's equal to 0.
1819 /// #![feature(peekable_next_if)]
1820 /// let mut iter = (0..5).peekable();
1821 /// // The first item of the iterator is 0; consume it.
1822 /// assert_eq!(iter.next_if_eq(&0), Some(0));
1823 /// // The next item returned is now 1, so `consume` will return `false`.
1824 /// assert_eq!(iter.next_if_eq(&0), None);
1825 /// // `next_if_eq` saves the value of the next item if it was not equal to `expected`.
1826 /// assert_eq!(iter.next(), Some(1));
1828 #[unstable(feature = "peekable_next_if", issue = "72480")]
1829 pub fn next_if_eq<R>(&mut self, expected: &R) -> Option<I::Item>
1832 I::Item: PartialEq<R>,
1834 self.next_if(|next| next == expected)
1838 #[unstable(feature = "trusted_len", issue = "37572")]
1839 unsafe impl<I> TrustedLen for Peekable<I> where I: TrustedLen {}
1841 #[unstable(issue = "0", feature = "inplace_iteration")]
1842 unsafe impl<S: Iterator, I: Iterator> SourceIter for Peekable<I>
1844 I: SourceIter<Source = S>,
1849 unsafe fn as_inner(&mut self) -> &mut S {
1850 // Safety: unsafe function forwarding to unsafe function with the same requirements
1851 unsafe { SourceIter::as_inner(&mut self.iter) }
1855 #[unstable(issue = "0", feature = "inplace_iteration")]
1856 unsafe impl<I: InPlaceIterable> InPlaceIterable for Peekable<I> {}
1858 /// An iterator that rejects elements while `predicate` returns `true`.
1860 /// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its
1861 /// documentation for more.
1863 /// [`skip_while`]: trait.Iterator.html#method.skip_while
1864 /// [`Iterator`]: trait.Iterator.html
1865 #[must_use = "iterators are lazy and do nothing unless consumed"]
1866 #[stable(feature = "rust1", since = "1.0.0")]
1868 pub struct SkipWhile<I, P> {
1873 impl<I, P> SkipWhile<I, P> {
1874 pub(super) fn new(iter: I, predicate: P) -> SkipWhile<I, P> {
1875 SkipWhile { iter, flag: false, predicate }
1879 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1880 impl<I: fmt::Debug, P> fmt::Debug for SkipWhile<I, P> {
1881 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1882 f.debug_struct("SkipWhile").field("iter", &self.iter).field("flag", &self.flag).finish()
1886 #[stable(feature = "rust1", since = "1.0.0")]
1887 impl<I: Iterator, P> Iterator for SkipWhile<I, P>
1889 P: FnMut(&I::Item) -> bool,
1891 type Item = I::Item;
1894 fn next(&mut self) -> Option<I::Item> {
1897 pred: &'a mut impl FnMut(&T) -> bool,
1898 ) -> impl FnMut(&T) -> bool + 'a {
1900 if *flag || !pred(x) {
1909 let flag = &mut self.flag;
1910 let pred = &mut self.predicate;
1911 self.iter.find(check(flag, pred))
1915 fn size_hint(&self) -> (usize, Option<usize>) {
1916 let (_, upper) = self.iter.size_hint();
1917 (0, upper) // can't know a lower bound, due to the predicate
1921 fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
1924 Fold: FnMut(Acc, Self::Item) -> R,
1929 Some(v) => init = fold(init, v)?,
1930 None => return Try::from_ok(init),
1933 self.iter.try_fold(init, fold)
1937 fn fold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
1939 Fold: FnMut(Acc, Self::Item) -> Acc,
1943 Some(v) => init = fold(init, v),
1944 None => return init,
1947 self.iter.fold(init, fold)
1951 #[stable(feature = "fused", since = "1.26.0")]
1952 impl<I, P> FusedIterator for SkipWhile<I, P>
1955 P: FnMut(&I::Item) -> bool,
1959 #[unstable(issue = "0", feature = "inplace_iteration")]
1960 unsafe impl<S: Iterator, P, I: Iterator> SourceIter for SkipWhile<I, P> where
1961 P: FnMut(&I::Item) -> bool,
1962 I: SourceIter<Source = S>
1967 unsafe fn as_inner(&mut self) -> &mut S {
1968 // Safety: unsafe function forwarding to unsafe function with the same requirements
1969 unsafe { SourceIter::as_inner(&mut self.iter) }
1973 #[unstable(issue = "0", feature = "inplace_iteration")]
1974 unsafe impl<I: InPlaceIterable, F> InPlaceIterable for SkipWhile<I, F>
1975 where F: FnMut(&I::Item) -> bool {}
1977 /// An iterator that only accepts elements while `predicate` returns `true`.
1979 /// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its
1980 /// documentation for more.
1982 /// [`take_while`]: trait.Iterator.html#method.take_while
1983 /// [`Iterator`]: trait.Iterator.html
1984 #[must_use = "iterators are lazy and do nothing unless consumed"]
1985 #[stable(feature = "rust1", since = "1.0.0")]
1987 pub struct TakeWhile<I, P> {
1992 impl<I, P> TakeWhile<I, P> {
1993 pub(super) fn new(iter: I, predicate: P) -> TakeWhile<I, P> {
1994 TakeWhile { iter, flag: false, predicate }
1998 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1999 impl<I: fmt::Debug, P> fmt::Debug for TakeWhile<I, P> {
2000 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2001 f.debug_struct("TakeWhile").field("iter", &self.iter).field("flag", &self.flag).finish()
2005 #[stable(feature = "rust1", since = "1.0.0")]
2006 impl<I: Iterator, P> Iterator for TakeWhile<I, P>
2008 P: FnMut(&I::Item) -> bool,
2010 type Item = I::Item;
2013 fn next(&mut self) -> Option<I::Item> {
2017 let x = self.iter.next()?;
2018 if (self.predicate)(&x) {
2028 fn size_hint(&self) -> (usize, Option<usize>) {
2032 let (_, upper) = self.iter.size_hint();
2033 (0, upper) // can't know a lower bound, due to the predicate
2038 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2041 Fold: FnMut(Acc, Self::Item) -> R,
2044 fn check<'a, T, Acc, R: Try<Ok = Acc>>(
2046 p: &'a mut impl FnMut(&T) -> bool,
2047 mut fold: impl FnMut(Acc, T) -> R + 'a,
2048 ) -> impl FnMut(Acc, T) -> ControlFlow<Acc, R> + 'a {
2051 ControlFlow::from_try(fold(acc, x))
2054 ControlFlow::Break(Try::from_ok(acc))
2062 let flag = &mut self.flag;
2063 let p = &mut self.predicate;
2064 self.iter.try_fold(init, check(flag, p, fold)).into_try()
2069 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2072 Fold: FnMut(Acc, Self::Item) -> Acc,
2075 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2076 move |acc, x| Ok(f(acc, x))
2079 self.try_fold(init, ok(fold)).unwrap()
2083 #[stable(feature = "fused", since = "1.26.0")]
2084 impl<I, P> FusedIterator for TakeWhile<I, P>
2087 P: FnMut(&I::Item) -> bool,
2091 /// An iterator that only accepts elements while `predicate` returns `Some(_)`.
2093 /// This `struct` is created by the [`map_while`] method on [`Iterator`]. See its
2094 /// documentation for more.
2096 /// [`map_while`]: trait.Iterator.html#method.map_while
2097 /// [`Iterator`]: trait.Iterator.html
2098 #[must_use = "iterators are lazy and do nothing unless consumed"]
2099 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
2101 pub struct MapWhile<I, P> {
2106 impl<I, P> MapWhile<I, P> {
2107 pub(super) fn new(iter: I, predicate: P) -> MapWhile<I, P> {
2108 MapWhile { iter, predicate }
2112 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
2113 impl<I: fmt::Debug, P> fmt::Debug for MapWhile<I, P> {
2114 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2115 f.debug_struct("MapWhile").field("iter", &self.iter).finish()
2119 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
2120 impl<B, I: Iterator, P> Iterator for MapWhile<I, P>
2122 P: FnMut(I::Item) -> Option<B>,
2127 fn next(&mut self) -> Option<B> {
2128 let x = self.iter.next()?;
2133 fn size_hint(&self) -> (usize, Option<usize>) {
2134 let (_, upper) = self.iter.size_hint();
2135 (0, upper) // can't know a lower bound, due to the predicate
2139 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R
2142 Fold: FnMut(Acc, Self::Item) -> R,
2145 let Self { iter, predicate } = self;
2146 iter.try_fold(init, |acc, x| match predicate(x) {
2147 Some(item) => ControlFlow::from_try(fold(acc, item)),
2148 None => ControlFlow::Break(Try::from_ok(acc)),
2154 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2157 Fold: FnMut(Acc, Self::Item) -> Acc,
2160 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2161 move |acc, x| Ok(f(acc, x))
2164 self.try_fold(init, ok(fold)).unwrap()
2168 #[unstable(issue = "0", feature = "inplace_iteration")]
2169 unsafe impl<S: Iterator, P, I: Iterator> SourceIter for TakeWhile<I, P> where
2170 P: FnMut(&I::Item) -> bool,
2171 I: SourceIter<Source = S>
2176 unsafe fn as_inner(&mut self) -> &mut S {
2177 // Safety: unsafe function forwarding to unsafe function with the same requirements
2178 unsafe { SourceIter::as_inner(&mut self.iter) }
2182 #[unstable(issue = "0", feature = "inplace_iteration")]
2183 unsafe impl<I: InPlaceIterable, F> InPlaceIterable for TakeWhile<I, F>
2184 where F: FnMut(&I::Item) -> bool {}
2187 /// An iterator that skips over `n` elements of `iter`.
2189 /// This `struct` is created by the [`skip`] method on [`Iterator`]. See its
2190 /// documentation for more.
2192 /// [`skip`]: trait.Iterator.html#method.skip
2193 /// [`Iterator`]: trait.Iterator.html
2194 #[derive(Clone, Debug)]
2195 #[must_use = "iterators are lazy and do nothing unless consumed"]
2196 #[stable(feature = "rust1", since = "1.0.0")]
2197 pub struct Skip<I> {
2202 pub(super) fn new(iter: I, n: usize) -> Skip<I> {
2207 #[stable(feature = "rust1", since = "1.0.0")]
2208 impl<I> Iterator for Skip<I>
2212 type Item = <I as Iterator>::Item;
2215 fn next(&mut self) -> Option<I::Item> {
2221 self.iter.nth(old_n)
2226 fn nth(&mut self, n: usize) -> Option<I::Item> {
2227 // Can't just add n + self.n due to overflow.
2229 let to_skip = self.n;
2232 self.iter.nth(to_skip - 1)?;
2238 fn count(mut self) -> usize {
2241 if self.iter.nth(self.n - 1).is_none() {
2249 fn last(mut self) -> Option<I::Item> {
2252 self.iter.nth(self.n - 1)?;
2258 fn size_hint(&self) -> (usize, Option<usize>) {
2259 let (lower, upper) = self.iter.size_hint();
2261 let lower = lower.saturating_sub(self.n);
2262 let upper = match upper {
2263 Some(x) => Some(x.saturating_sub(self.n)),
2271 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2274 Fold: FnMut(Acc, Self::Item) -> R,
2281 if self.iter.nth(n - 1).is_none() {
2282 return Try::from_ok(init);
2285 self.iter.try_fold(init, fold)
2289 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2291 Fold: FnMut(Acc, Self::Item) -> Acc,
2295 if self.iter.nth(self.n - 1).is_none() {
2299 self.iter.fold(init, fold)
2303 #[stable(feature = "rust1", since = "1.0.0")]
2304 impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
2306 #[stable(feature = "double_ended_skip_iterator", since = "1.9.0")]
2307 impl<I> DoubleEndedIterator for Skip<I>
2309 I: DoubleEndedIterator + ExactSizeIterator,
2311 fn next_back(&mut self) -> Option<Self::Item> {
2312 if self.len() > 0 { self.iter.next_back() } else { None }
2316 fn nth_back(&mut self, n: usize) -> Option<I::Item> {
2317 let len = self.len();
2319 self.iter.nth_back(n)
2322 // consume the original iterator
2323 self.iter.nth_back(len - 1);
2329 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2332 Fold: FnMut(Acc, Self::Item) -> R,
2335 fn check<T, Acc, R: Try<Ok = Acc>>(
2337 mut fold: impl FnMut(Acc, T) -> R,
2338 ) -> impl FnMut(Acc, T) -> ControlFlow<Acc, R> {
2341 let r = fold(acc, x);
2342 if n == 0 { ControlFlow::Break(r) } else { ControlFlow::from_try(r) }
2350 self.iter.try_rfold(init, check(n, fold)).into_try()
2354 fn rfold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2356 Fold: FnMut(Acc, Self::Item) -> Acc,
2359 fn ok<Acc, T>(mut f: impl FnMut(Acc, T) -> Acc) -> impl FnMut(Acc, T) -> Result<Acc, !> {
2360 move |acc, x| Ok(f(acc, x))
2363 self.try_rfold(init, ok(fold)).unwrap()
2367 #[stable(feature = "fused", since = "1.26.0")]
2368 impl<I> FusedIterator for Skip<I> where I: FusedIterator {}
2370 #[unstable(issue = "0", feature = "inplace_iteration")]
2371 unsafe impl<S: Iterator, I: Iterator> SourceIter for Skip<I>
2373 I: SourceIter<Source = S>,
2378 unsafe fn as_inner(&mut self) -> &mut S {
2379 // Safety: unsafe function forwarding to unsafe function with the same requirements
2380 unsafe { SourceIter::as_inner(&mut self.iter) }
2384 #[unstable(issue = "0", feature = "inplace_iteration")]
2385 unsafe impl<I: InPlaceIterable> InPlaceIterable for Skip<I> {}
2387 /// An iterator that only iterates over the first `n` iterations of `iter`.
2389 /// This `struct` is created by the [`take`] method on [`Iterator`]. See its
2390 /// documentation for more.
2392 /// [`take`]: trait.Iterator.html#method.take
2393 /// [`Iterator`]: trait.Iterator.html
2394 #[derive(Clone, Debug)]
2395 #[must_use = "iterators are lazy and do nothing unless consumed"]
2396 #[stable(feature = "rust1", since = "1.0.0")]
2397 pub struct Take<I> {
2399 pub(super) n: usize,
2402 pub(super) fn new(iter: I, n: usize) -> Take<I> {
2407 #[stable(feature = "rust1", since = "1.0.0")]
2408 impl<I> Iterator for Take<I>
2412 type Item = <I as Iterator>::Item;
2415 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2425 fn nth(&mut self, n: usize) -> Option<I::Item> {
2431 self.iter.nth(self.n - 1);
2439 fn size_hint(&self) -> (usize, Option<usize>) {
2441 return (0, Some(0));
2444 let (lower, upper) = self.iter.size_hint();
2446 let lower = cmp::min(lower, self.n);
2448 let upper = match upper {
2449 Some(x) if x < self.n => Some(x),
2457 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2460 Fold: FnMut(Acc, Self::Item) -> R,
2463 fn check<'a, T, Acc, R: Try<Ok = Acc>>(
2465 mut fold: impl FnMut(Acc, T) -> R + 'a,
2466 ) -> impl FnMut(Acc, T) -> ControlFlow<Acc, R> + 'a {
2469 let r = fold(acc, x);
2470 if *n == 0 { ControlFlow::Break(r) } else { ControlFlow::from_try(r) }
2477 let n = &mut self.n;
2478 self.iter.try_fold(init, check(n, fold)).into_try()
2483 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2486 Fold: FnMut(Acc, Self::Item) -> Acc,
2489 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2490 move |acc, x| Ok(f(acc, x))
2493 self.try_fold(init, ok(fold)).unwrap()
2497 #[unstable(issue = "0", feature = "inplace_iteration")]
2498 unsafe impl<S: Iterator, I: Iterator> SourceIter for Take<I> where I: SourceIter<Source = S> {
2502 unsafe fn as_inner(&mut self) -> &mut S {
2503 // Safety: unsafe function forwarding to unsafe function with the same requirements
2504 unsafe { SourceIter::as_inner(&mut self.iter) }
2508 #[unstable(issue = "0", feature = "inplace_iteration")]
2509 unsafe impl<I: InPlaceIterable> InPlaceIterable for Take<I> {}
2511 #[stable(feature = "double_ended_take_iterator", since = "1.38.0")]
2512 impl<I> DoubleEndedIterator for Take<I>
2514 I: DoubleEndedIterator + ExactSizeIterator,
2517 fn next_back(&mut self) -> Option<Self::Item> {
2523 self.iter.nth_back(self.iter.len().saturating_sub(n))
2528 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2529 let len = self.iter.len();
2531 let m = len.saturating_sub(self.n) + n;
2533 self.iter.nth_back(m)
2536 self.iter.nth_back(len - 1);
2543 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2546 Fold: FnMut(Acc, Self::Item) -> R,
2552 let len = self.iter.len();
2553 if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() {
2556 self.iter.try_rfold(init, fold)
2562 fn rfold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2565 Fold: FnMut(Acc, Self::Item) -> Acc,
2570 let len = self.iter.len();
2571 if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() {
2574 self.iter.rfold(init, fold)
2580 #[stable(feature = "rust1", since = "1.0.0")]
2581 impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
2583 #[stable(feature = "fused", since = "1.26.0")]
2584 impl<I> FusedIterator for Take<I> where I: FusedIterator {}
2586 #[unstable(feature = "trusted_len", issue = "37572")]
2587 unsafe impl<I: TrustedLen> TrustedLen for Take<I> {}
2589 /// An iterator to maintain state while iterating another iterator.
2591 /// This `struct` is created by the [`scan`] method on [`Iterator`]. See its
2592 /// documentation for more.
2594 /// [`scan`]: trait.Iterator.html#method.scan
2595 /// [`Iterator`]: trait.Iterator.html
2596 #[must_use = "iterators are lazy and do nothing unless consumed"]
2597 #[stable(feature = "rust1", since = "1.0.0")]
2599 pub struct Scan<I, St, F> {
2604 impl<I, St, F> Scan<I, St, F> {
2605 pub(super) fn new(iter: I, state: St, f: F) -> Scan<I, St, F> {
2606 Scan { iter, state, f }
2610 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2611 impl<I: fmt::Debug, St: fmt::Debug, F> fmt::Debug for Scan<I, St, F> {
2612 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2613 f.debug_struct("Scan").field("iter", &self.iter).field("state", &self.state).finish()
2617 #[stable(feature = "rust1", since = "1.0.0")]
2618 impl<B, I, St, F> Iterator for Scan<I, St, F>
2621 F: FnMut(&mut St, I::Item) -> Option<B>,
2626 fn next(&mut self) -> Option<B> {
2627 let a = self.iter.next()?;
2628 (self.f)(&mut self.state, a)
2632 fn size_hint(&self) -> (usize, Option<usize>) {
2633 let (_, upper) = self.iter.size_hint();
2634 (0, upper) // can't know a lower bound, due to the scan function
2638 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2641 Fold: FnMut(Acc, Self::Item) -> R,
2644 fn scan<'a, T, St, B, Acc, R: Try<Ok = Acc>>(
2646 f: &'a mut impl FnMut(&mut St, T) -> Option<B>,
2647 mut fold: impl FnMut(Acc, B) -> R + 'a,
2648 ) -> impl FnMut(Acc, T) -> ControlFlow<Acc, R> + 'a {
2649 move |acc, x| match f(state, x) {
2650 None => ControlFlow::Break(Try::from_ok(acc)),
2651 Some(x) => ControlFlow::from_try(fold(acc, x)),
2655 let state = &mut self.state;
2656 let f = &mut self.f;
2657 self.iter.try_fold(init, scan(state, f, fold)).into_try()
2661 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2664 Fold: FnMut(Acc, Self::Item) -> Acc,
2667 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2668 move |acc, x| Ok(f(acc, x))
2671 self.try_fold(init, ok(fold)).unwrap()
2675 #[unstable(issue = "0", feature = "inplace_iteration")]
2676 unsafe impl<St, F, B, S: Iterator, I: Iterator> SourceIter for Scan<I, St, F>
2677 where I: SourceIter<Source = S>,
2678 F: FnMut(&mut St, I::Item) -> Option<B>,
2683 unsafe fn as_inner(&mut self) -> &mut S {
2684 // Safety: unsafe function forwarding to unsafe function with the same requirements
2685 unsafe { SourceIter::as_inner(&mut self.iter) }
2689 #[unstable(issue = "0", feature = "inplace_iteration")]
2690 unsafe impl<St, F, B, I: InPlaceIterable> InPlaceIterable for Scan<I, St, F>
2691 where F: FnMut(&mut St, I::Item) -> Option<B>,
2694 /// An iterator that calls a function with a reference to each element before
2697 /// This `struct` is created by the [`inspect`] method on [`Iterator`]. See its
2698 /// documentation for more.
2700 /// [`inspect`]: trait.Iterator.html#method.inspect
2701 /// [`Iterator`]: trait.Iterator.html
2702 #[must_use = "iterators are lazy and do nothing unless consumed"]
2703 #[stable(feature = "rust1", since = "1.0.0")]
2705 pub struct Inspect<I, F> {
2709 impl<I, F> Inspect<I, F> {
2710 pub(super) fn new(iter: I, f: F) -> Inspect<I, F> {
2715 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2716 impl<I: fmt::Debug, F> fmt::Debug for Inspect<I, F> {
2717 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2718 f.debug_struct("Inspect").field("iter", &self.iter).finish()
2722 impl<I: Iterator, F> Inspect<I, F>
2727 fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
2728 if let Some(ref a) = elt {
2736 fn inspect_fold<T, Acc>(
2737 mut f: impl FnMut(&T),
2738 mut fold: impl FnMut(Acc, T) -> Acc,
2739 ) -> impl FnMut(Acc, T) -> Acc {
2746 fn inspect_try_fold<'a, T, Acc, R>(
2747 f: &'a mut impl FnMut(&T),
2748 mut fold: impl FnMut(Acc, T) -> R + 'a,
2749 ) -> impl FnMut(Acc, T) -> R + 'a {
2756 #[stable(feature = "rust1", since = "1.0.0")]
2757 impl<I: Iterator, F> Iterator for Inspect<I, F>
2761 type Item = I::Item;
2764 fn next(&mut self) -> Option<I::Item> {
2765 let next = self.iter.next();
2766 self.do_inspect(next)
2770 fn size_hint(&self) -> (usize, Option<usize>) {
2771 self.iter.size_hint()
2775 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2778 Fold: FnMut(Acc, Self::Item) -> R,
2781 self.iter.try_fold(init, inspect_try_fold(&mut self.f, fold))
2785 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2787 Fold: FnMut(Acc, Self::Item) -> Acc,
2789 self.iter.fold(init, inspect_fold(self.f, fold))
2793 #[stable(feature = "rust1", since = "1.0.0")]
2794 impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
2799 fn next_back(&mut self) -> Option<I::Item> {
2800 let next = self.iter.next_back();
2801 self.do_inspect(next)
2805 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2808 Fold: FnMut(Acc, Self::Item) -> R,
2811 self.iter.try_rfold(init, inspect_try_fold(&mut self.f, fold))
2815 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2817 Fold: FnMut(Acc, Self::Item) -> Acc,
2819 self.iter.rfold(init, inspect_fold(self.f, fold))
2823 #[stable(feature = "rust1", since = "1.0.0")]
2824 impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F>
2828 fn len(&self) -> usize {
2832 fn is_empty(&self) -> bool {
2833 self.iter.is_empty()
2837 #[stable(feature = "fused", since = "1.26.0")]
2838 impl<I: FusedIterator, F> FusedIterator for Inspect<I, F> where F: FnMut(&I::Item) {}
2840 #[unstable(issue = "0", feature = "inplace_iteration")]
2841 unsafe impl<S: Iterator, I: Iterator, F> SourceIter for Inspect<I, F> where
2843 I: SourceIter<Source = S>
2848 unsafe fn as_inner(&mut self) -> &mut S {
2849 // Safety: unsafe function forwarding to unsafe function with the same requirements
2850 unsafe { SourceIter::as_inner(&mut self.iter) }
2854 #[unstable(issue = "0", feature = "inplace_iteration")]
2855 unsafe impl<I: InPlaceIterable, F> InPlaceIterable for Inspect<I, F> where F: FnMut(&I::Item) {}
2857 /// An iterator adapter that produces output as long as the underlying
2858 /// iterator produces `Result::Ok` values.
2860 /// If an error is encountered, the iterator stops and the error is
2862 pub(crate) struct ResultShunt<'a, I, E> {
2864 error: &'a mut Result<(), E>,
2867 /// Process the given iterator as if it yielded a `T` instead of a
2868 /// `Result<T, _>`. Any errors will stop the inner iterator and
2869 /// the overall result will be an error.
2870 pub(crate) fn process_results<I, T, E, F, U>(iter: I, mut f: F) -> Result<U, E>
2872 I: Iterator<Item = Result<T, E>>,
2873 for<'a> F: FnMut(ResultShunt<'a, I, E>) -> U,
2875 let mut error = Ok(());
2876 let shunt = ResultShunt { iter, error: &mut error };
2877 let value = f(shunt);
2878 error.map(|()| value)
2881 impl<I, T, E> Iterator for ResultShunt<'_, I, E>
2883 I: Iterator<Item = Result<T, E>>,
2887 fn next(&mut self) -> Option<Self::Item> {
2891 fn size_hint(&self) -> (usize, Option<usize>) {
2892 if self.error.is_err() {
2895 let (_, upper) = self.iter.size_hint();
2900 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
2902 F: FnMut(B, Self::Item) -> R,
2905 let error = &mut *self.error;
2907 .try_fold(init, |acc, x| match x {
2908 Ok(x) => ControlFlow::from_try(f(acc, x)),
2911 ControlFlow::Break(Try::from_ok(acc))
2917 fn fold<B, F>(mut self, init: B, fold: F) -> B
2920 F: FnMut(B, Self::Item) -> B,
2923 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2924 move |acc, x| Ok(f(acc, x))
2927 self.try_fold(init, ok(fold)).unwrap()