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 = "none", 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()`]: Iterator::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`]: Iterator::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 advance_by(&mut self, n: usize) -> Result<(), usize> {
129 self.iter.advance_back_by(n)
133 fn nth(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
134 self.iter.nth_back(n)
137 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
140 F: FnMut(B, Self::Item) -> R,
143 self.iter.try_rfold(init, f)
146 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
148 F: FnMut(Acc, Self::Item) -> Acc,
150 self.iter.rfold(init, f)
154 fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
156 P: FnMut(&Self::Item) -> bool,
158 self.iter.rfind(predicate)
162 #[stable(feature = "rust1", since = "1.0.0")]
163 impl<I> DoubleEndedIterator for Rev<I>
165 I: DoubleEndedIterator,
168 fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
173 fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
174 self.iter.advance_by(n)
178 fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
182 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
185 F: FnMut(B, Self::Item) -> R,
188 self.iter.try_fold(init, f)
191 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
193 F: FnMut(Acc, Self::Item) -> Acc,
195 self.iter.fold(init, f)
198 fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
200 P: FnMut(&Self::Item) -> bool,
202 self.iter.find(predicate)
206 #[stable(feature = "rust1", since = "1.0.0")]
207 impl<I> ExactSizeIterator for Rev<I>
209 I: ExactSizeIterator + DoubleEndedIterator,
211 fn len(&self) -> usize {
215 fn is_empty(&self) -> bool {
220 #[stable(feature = "fused", since = "1.26.0")]
221 impl<I> FusedIterator for Rev<I> where I: FusedIterator + DoubleEndedIterator {}
223 #[unstable(feature = "trusted_len", issue = "37572")]
224 unsafe impl<I> TrustedLen for Rev<I> where I: TrustedLen + DoubleEndedIterator {}
226 /// An iterator that copies the elements of an underlying iterator.
228 /// This `struct` is created by the [`copied`] method on [`Iterator`]. See its
229 /// documentation for more.
231 /// [`copied`]: Iterator::copied
232 /// [`Iterator`]: trait.Iterator.html
233 #[stable(feature = "iter_copied", since = "1.36.0")]
234 #[must_use = "iterators are lazy and do nothing unless consumed"]
235 #[derive(Clone, Debug)]
236 pub struct Copied<I> {
241 pub(super) fn new(it: I) -> Copied<I> {
246 fn copy_fold<T: Copy, Acc>(mut f: impl FnMut(Acc, T) -> Acc) -> impl FnMut(Acc, &T) -> Acc {
247 move |acc, &elt| f(acc, elt)
250 fn copy_try_fold<T: Copy, Acc, R>(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R {
251 move |acc, &elt| f(acc, elt)
254 #[stable(feature = "iter_copied", since = "1.36.0")]
255 impl<'a, I, T: 'a> Iterator for Copied<I>
257 I: Iterator<Item = &'a T>,
262 fn next(&mut self) -> Option<T> {
263 self.it.next().copied()
266 fn size_hint(&self) -> (usize, Option<usize>) {
270 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
273 F: FnMut(B, Self::Item) -> R,
276 self.it.try_fold(init, copy_try_fold(f))
279 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
281 F: FnMut(Acc, Self::Item) -> Acc,
283 self.it.fold(init, copy_fold(f))
286 fn nth(&mut self, n: usize) -> Option<T> {
287 self.it.nth(n).copied()
290 fn last(self) -> Option<T> {
291 self.it.last().copied()
294 fn count(self) -> usize {
298 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> T
300 Self: TrustedRandomAccess,
302 // SAFETY: the caller must uphold the contract for
303 // `Iterator::__iterator_get_unchecked`.
304 *unsafe { try_get_unchecked(&mut self.it, idx) }
308 #[stable(feature = "iter_copied", since = "1.36.0")]
309 impl<'a, I, T: 'a> DoubleEndedIterator for Copied<I>
311 I: DoubleEndedIterator<Item = &'a T>,
314 fn next_back(&mut self) -> Option<T> {
315 self.it.next_back().copied()
318 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
321 F: FnMut(B, Self::Item) -> R,
324 self.it.try_rfold(init, copy_try_fold(f))
327 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
329 F: FnMut(Acc, Self::Item) -> Acc,
331 self.it.rfold(init, copy_fold(f))
335 #[stable(feature = "iter_copied", since = "1.36.0")]
336 impl<'a, I, T: 'a> ExactSizeIterator for Copied<I>
338 I: ExactSizeIterator<Item = &'a T>,
341 fn len(&self) -> usize {
345 fn is_empty(&self) -> bool {
350 #[stable(feature = "iter_copied", since = "1.36.0")]
351 impl<'a, I, T: 'a> FusedIterator for Copied<I>
353 I: FusedIterator<Item = &'a T>,
359 #[unstable(feature = "trusted_random_access", issue = "none")]
360 unsafe impl<I> TrustedRandomAccess for Copied<I>
362 I: TrustedRandomAccess,
365 fn may_have_side_effect() -> bool {
366 I::may_have_side_effect()
370 #[stable(feature = "iter_copied", since = "1.36.0")]
371 unsafe impl<'a, I, T: 'a> TrustedLen for Copied<I>
373 I: TrustedLen<Item = &'a T>,
378 /// An iterator that clones the elements of an underlying iterator.
380 /// This `struct` is created by the [`cloned`] method on [`Iterator`]. See its
381 /// documentation for more.
383 /// [`cloned`]: Iterator::cloned
384 /// [`Iterator`]: trait.Iterator.html
385 #[stable(feature = "iter_cloned", since = "1.1.0")]
386 #[must_use = "iterators are lazy and do nothing unless consumed"]
387 #[derive(Clone, Debug)]
388 pub struct Cloned<I> {
392 pub(super) fn new(it: I) -> Cloned<I> {
397 fn clone_try_fold<T: Clone, Acc, R>(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R {
398 move |acc, elt| f(acc, elt.clone())
401 #[stable(feature = "iter_cloned", since = "1.1.0")]
402 impl<'a, I, T: 'a> Iterator for Cloned<I>
404 I: Iterator<Item = &'a T>,
409 fn next(&mut self) -> Option<T> {
410 self.it.next().cloned()
413 fn size_hint(&self) -> (usize, Option<usize>) {
417 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
420 F: FnMut(B, Self::Item) -> R,
423 self.it.try_fold(init, clone_try_fold(f))
426 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
428 F: FnMut(Acc, Self::Item) -> Acc,
430 self.it.map(T::clone).fold(init, f)
433 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> T
435 Self: TrustedRandomAccess,
437 // SAFETY: the caller must uphold the contract for
438 // `Iterator::__iterator_get_unchecked`.
439 unsafe { try_get_unchecked(&mut self.it, idx).clone() }
443 #[stable(feature = "iter_cloned", since = "1.1.0")]
444 impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
446 I: DoubleEndedIterator<Item = &'a T>,
449 fn next_back(&mut self) -> Option<T> {
450 self.it.next_back().cloned()
453 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
456 F: FnMut(B, Self::Item) -> R,
459 self.it.try_rfold(init, clone_try_fold(f))
462 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
464 F: FnMut(Acc, Self::Item) -> Acc,
466 self.it.map(T::clone).rfold(init, f)
470 #[stable(feature = "iter_cloned", since = "1.1.0")]
471 impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
473 I: ExactSizeIterator<Item = &'a T>,
476 fn len(&self) -> usize {
480 fn is_empty(&self) -> bool {
485 #[stable(feature = "fused", since = "1.26.0")]
486 impl<'a, I, T: 'a> FusedIterator for Cloned<I>
488 I: FusedIterator<Item = &'a T>,
494 #[unstable(feature = "trusted_random_access", issue = "none")]
495 unsafe impl<I> TrustedRandomAccess for Cloned<I>
497 I: TrustedRandomAccess,
500 fn may_have_side_effect() -> bool {
505 #[unstable(feature = "trusted_len", issue = "37572")]
506 unsafe impl<'a, I, T: 'a> TrustedLen for Cloned<I>
508 I: TrustedLen<Item = &'a T>,
513 /// An iterator that repeats endlessly.
515 /// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its
516 /// documentation for more.
518 /// [`cycle`]: Iterator::cycle
519 /// [`Iterator`]: trait.Iterator.html
520 #[derive(Clone, Debug)]
521 #[must_use = "iterators are lazy and do nothing unless consumed"]
522 #[stable(feature = "rust1", since = "1.0.0")]
523 pub struct Cycle<I> {
527 impl<I: Clone> Cycle<I> {
528 pub(super) fn new(iter: I) -> Cycle<I> {
529 Cycle { orig: iter.clone(), iter }
533 #[stable(feature = "rust1", since = "1.0.0")]
534 impl<I> Iterator for Cycle<I>
538 type Item = <I as Iterator>::Item;
541 fn next(&mut self) -> Option<<I as Iterator>::Item> {
542 match self.iter.next() {
544 self.iter = self.orig.clone();
552 fn size_hint(&self) -> (usize, Option<usize>) {
553 // the cycle iterator is either empty or infinite
554 match self.orig.size_hint() {
555 sz @ (0, Some(0)) => sz,
557 _ => (usize::MAX, None),
562 fn try_fold<Acc, F, R>(&mut self, mut acc: Acc, mut f: F) -> R
564 F: FnMut(Acc, Self::Item) -> R,
567 // fully iterate the current iterator. this is necessary because
568 // `self.iter` may be empty even when `self.orig` isn't
569 acc = self.iter.try_fold(acc, &mut f)?;
570 self.iter = self.orig.clone();
572 // complete a full cycle, keeping track of whether the cycled
573 // iterator is empty or not. we need to return early in case
574 // of an empty iterator to prevent an infinite loop
575 let mut is_empty = true;
576 acc = self.iter.try_fold(acc, |acc, x| {
586 self.iter = self.orig.clone();
587 acc = self.iter.try_fold(acc, &mut f)?;
591 // No `fold` override, because `fold` doesn't make much sense for `Cycle`,
592 // and we can't do anything better than the default.
595 #[stable(feature = "fused", since = "1.26.0")]
596 impl<I> FusedIterator for Cycle<I> where I: Clone + Iterator {}
598 /// An iterator for stepping iterators by a custom amount.
600 /// This `struct` is created by the [`step_by`] method on [`Iterator`]. See
601 /// its documentation for more.
603 /// [`step_by`]: Iterator::step_by
604 /// [`Iterator`]: trait.Iterator.html
605 #[must_use = "iterators are lazy and do nothing unless consumed"]
606 #[stable(feature = "iterator_step_by", since = "1.28.0")]
607 #[derive(Clone, Debug)]
608 pub struct StepBy<I> {
614 pub(super) fn new(iter: I, step: usize) -> StepBy<I> {
616 StepBy { iter, step: step - 1, first_take: true }
620 #[stable(feature = "iterator_step_by", since = "1.28.0")]
621 impl<I> Iterator for StepBy<I>
628 fn next(&mut self) -> Option<Self::Item> {
630 self.first_take = false;
633 self.iter.nth(self.step)
638 fn size_hint(&self) -> (usize, Option<usize>) {
640 fn first_size(step: usize) -> impl Fn(usize) -> usize {
641 move |n| if n == 0 { 0 } else { 1 + (n - 1) / (step + 1) }
645 fn other_size(step: usize) -> impl Fn(usize) -> usize {
646 move |n| n / (step + 1)
649 let (low, high) = self.iter.size_hint();
652 let f = first_size(self.step);
653 (f(low), high.map(f))
655 let f = other_size(self.step);
656 (f(low), high.map(f))
661 fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
663 self.first_take = false;
664 let first = self.iter.next();
670 // n and self.step are indices, we need to add 1 to get the amount of elements
671 // When calling `.nth`, we need to subtract 1 again to convert back to an index
672 // step + 1 can't overflow because `.step_by` sets `self.step` to `step - 1`
673 let mut step = self.step + 1;
674 // n + 1 could overflow
675 // thus, if n is usize::MAX, instead of adding one, we call .nth(step)
677 self.iter.nth(step - 1);
684 let mul = n.checked_mul(step);
686 if intrinsics::likely(mul.is_some()) {
687 return self.iter.nth(mul.unwrap() - 1);
690 let div_n = usize::MAX / n;
691 let div_step = usize::MAX / step;
692 let nth_n = div_n * n;
693 let nth_step = div_step * step;
694 let nth = if nth_n > nth_step {
701 self.iter.nth(nth - 1);
705 fn try_fold<Acc, F, R>(&mut self, mut acc: Acc, mut f: F) -> R
707 F: FnMut(Acc, Self::Item) -> R,
711 fn nth<I: Iterator>(iter: &mut I, step: usize) -> impl FnMut() -> Option<I::Item> + '_ {
712 move || iter.nth(step)
716 self.first_take = false;
717 match self.iter.next() {
718 None => return try { acc },
719 Some(x) => acc = f(acc, x)?,
722 from_fn(nth(&mut self.iter, self.step)).try_fold(acc, f)
725 fn fold<Acc, F>(mut self, mut acc: Acc, mut f: F) -> Acc
727 F: FnMut(Acc, Self::Item) -> Acc,
730 fn nth<I: Iterator>(iter: &mut I, step: usize) -> impl FnMut() -> Option<I::Item> + '_ {
731 move || iter.nth(step)
735 self.first_take = false;
736 match self.iter.next() {
738 Some(x) => acc = f(acc, x),
741 from_fn(nth(&mut self.iter, self.step)).fold(acc, f)
747 I: ExactSizeIterator,
749 // The zero-based index starting from the end of the iterator of the
750 // last element. Used in the `DoubleEndedIterator` implementation.
751 fn next_back_index(&self) -> usize {
752 let rem = self.iter.len() % (self.step + 1);
754 if rem == 0 { self.step } else { rem - 1 }
761 #[stable(feature = "double_ended_step_by_iterator", since = "1.38.0")]
762 impl<I> DoubleEndedIterator for StepBy<I>
764 I: DoubleEndedIterator + ExactSizeIterator,
767 fn next_back(&mut self) -> Option<Self::Item> {
768 self.iter.nth_back(self.next_back_index())
772 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
773 // `self.iter.nth_back(usize::MAX)` does the right thing here when `n`
774 // is out of bounds because the length of `self.iter` does not exceed
775 // `usize::MAX` (because `I: ExactSizeIterator`) and `nth_back` is
777 let n = n.saturating_mul(self.step + 1).saturating_add(self.next_back_index());
778 self.iter.nth_back(n)
781 fn try_rfold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R
783 F: FnMut(Acc, Self::Item) -> R,
787 fn nth_back<I: DoubleEndedIterator>(
790 ) -> impl FnMut() -> Option<I::Item> + '_ {
791 move || iter.nth_back(step)
794 match self.next_back() {
795 None => try { init },
797 let acc = f(init, x)?;
798 from_fn(nth_back(&mut self.iter, self.step)).try_fold(acc, f)
804 fn rfold<Acc, F>(mut self, init: Acc, mut f: F) -> Acc
807 F: FnMut(Acc, Self::Item) -> Acc,
810 fn nth_back<I: DoubleEndedIterator>(
813 ) -> impl FnMut() -> Option<I::Item> + '_ {
814 move || iter.nth_back(step)
817 match self.next_back() {
820 let acc = f(init, x);
821 from_fn(nth_back(&mut self.iter, self.step)).fold(acc, f)
827 // StepBy can only make the iterator shorter, so the len will still fit.
828 #[stable(feature = "iterator_step_by", since = "1.28.0")]
829 impl<I> ExactSizeIterator for StepBy<I> where I: ExactSizeIterator {}
831 /// An iterator that maps the values of `iter` with `f`.
833 /// This `struct` is created by the [`map`] method on [`Iterator`]. See its
834 /// documentation for more.
836 /// [`map`]: Iterator::map
837 /// [`Iterator`]: trait.Iterator.html
839 /// # Notes about side effects
841 /// The [`map`] iterator implements [`DoubleEndedIterator`], meaning that
842 /// you can also [`map`] backwards:
845 /// let v: Vec<i32> = vec![1, 2, 3].into_iter().map(|x| x + 1).rev().collect();
847 /// assert_eq!(v, [4, 3, 2]);
850 /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
852 /// But if your closure has state, iterating backwards may act in a way you do
853 /// not expect. Let's go through an example. First, in the forward direction:
858 /// for pair in vec!['a', 'b', 'c'].into_iter()
859 /// .map(|letter| { c += 1; (letter, c) }) {
860 /// println!("{:?}", pair);
864 /// This will print "('a', 1), ('b', 2), ('c', 3)".
866 /// Now consider this twist where we add a call to `rev`. This version will
867 /// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed,
868 /// but the values of the counter still go in order. This is because `map()` is
869 /// still being called lazily on each item, but we are popping items off the
870 /// back of the vector now, instead of shifting them from the front.
875 /// for pair in vec!['a', 'b', 'c'].into_iter()
876 /// .map(|letter| { c += 1; (letter, c) })
878 /// println!("{:?}", pair);
881 #[must_use = "iterators are lazy and do nothing unless consumed"]
882 #[stable(feature = "rust1", since = "1.0.0")]
884 pub struct Map<I, F> {
888 impl<I, F> Map<I, F> {
889 pub(super) fn new(iter: I, f: F) -> Map<I, F> {
894 #[stable(feature = "core_impl_debug", since = "1.9.0")]
895 impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> {
896 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
897 f.debug_struct("Map").field("iter", &self.iter).finish()
901 fn map_fold<T, B, Acc>(
902 mut f: impl FnMut(T) -> B,
903 mut g: impl FnMut(Acc, B) -> Acc,
904 ) -> impl FnMut(Acc, T) -> Acc {
905 move |acc, elt| g(acc, f(elt))
908 fn map_try_fold<'a, T, B, Acc, R>(
909 f: &'a mut impl FnMut(T) -> B,
910 mut g: impl FnMut(Acc, B) -> R + 'a,
911 ) -> impl FnMut(Acc, T) -> R + 'a {
912 move |acc, elt| g(acc, f(elt))
915 #[stable(feature = "rust1", since = "1.0.0")]
916 impl<B, I: Iterator, F> Iterator for Map<I, F>
918 F: FnMut(I::Item) -> B,
923 fn next(&mut self) -> Option<B> {
924 self.iter.next().map(&mut self.f)
928 fn size_hint(&self) -> (usize, Option<usize>) {
929 self.iter.size_hint()
932 fn try_fold<Acc, G, R>(&mut self, init: Acc, g: G) -> R
935 G: FnMut(Acc, Self::Item) -> R,
938 self.iter.try_fold(init, map_try_fold(&mut self.f, g))
941 fn fold<Acc, G>(self, init: Acc, g: G) -> Acc
943 G: FnMut(Acc, Self::Item) -> Acc,
945 self.iter.fold(init, map_fold(self.f, g))
948 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> B
950 Self: TrustedRandomAccess,
952 // SAFETY: the caller must uphold the contract for
953 // `Iterator::__iterator_get_unchecked`.
954 unsafe { (self.f)(try_get_unchecked(&mut self.iter, idx)) }
958 #[stable(feature = "rust1", since = "1.0.0")]
959 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F>
961 F: FnMut(I::Item) -> B,
964 fn next_back(&mut self) -> Option<B> {
965 self.iter.next_back().map(&mut self.f)
968 fn try_rfold<Acc, G, R>(&mut self, init: Acc, g: G) -> R
971 G: FnMut(Acc, Self::Item) -> R,
974 self.iter.try_rfold(init, map_try_fold(&mut self.f, g))
977 fn rfold<Acc, G>(self, init: Acc, g: G) -> Acc
979 G: FnMut(Acc, Self::Item) -> Acc,
981 self.iter.rfold(init, map_fold(self.f, g))
985 #[stable(feature = "rust1", since = "1.0.0")]
986 impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F>
988 F: FnMut(I::Item) -> B,
990 fn len(&self) -> usize {
994 fn is_empty(&self) -> bool {
999 #[stable(feature = "fused", since = "1.26.0")]
1000 impl<B, I: FusedIterator, F> FusedIterator for Map<I, F> where F: FnMut(I::Item) -> B {}
1002 #[unstable(feature = "trusted_len", issue = "37572")]
1003 unsafe impl<B, I, F> TrustedLen for Map<I, F>
1006 F: FnMut(I::Item) -> B,
1011 #[unstable(feature = "trusted_random_access", issue = "none")]
1012 unsafe impl<I, F> TrustedRandomAccess for Map<I, F>
1014 I: TrustedRandomAccess,
1017 fn may_have_side_effect() -> bool {
1022 #[unstable(issue = "none", feature = "inplace_iteration")]
1023 unsafe impl<S: Iterator, B, I: Iterator, F> SourceIter for Map<I, F>
1025 F: FnMut(I::Item) -> B,
1026 I: SourceIter<Source = S>,
1031 unsafe fn as_inner(&mut self) -> &mut S {
1032 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
1033 unsafe { SourceIter::as_inner(&mut self.iter) }
1037 #[unstable(issue = "none", feature = "inplace_iteration")]
1038 unsafe impl<B, I: InPlaceIterable, F> InPlaceIterable for Map<I, F> where F: FnMut(I::Item) -> B {}
1040 /// An iterator that filters the elements of `iter` with `predicate`.
1042 /// This `struct` is created by the [`filter`] method on [`Iterator`]. See its
1043 /// documentation for more.
1045 /// [`filter`]: Iterator::filter
1046 /// [`Iterator`]: trait.Iterator.html
1047 #[must_use = "iterators are lazy and do nothing unless consumed"]
1048 #[stable(feature = "rust1", since = "1.0.0")]
1050 pub struct Filter<I, P> {
1054 impl<I, P> Filter<I, P> {
1055 pub(super) fn new(iter: I, predicate: P) -> Filter<I, P> {
1056 Filter { iter, predicate }
1060 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1061 impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
1062 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1063 f.debug_struct("Filter").field("iter", &self.iter).finish()
1067 fn filter_fold<T, Acc>(
1068 mut predicate: impl FnMut(&T) -> bool,
1069 mut fold: impl FnMut(Acc, T) -> Acc,
1070 ) -> impl FnMut(Acc, T) -> Acc {
1071 move |acc, item| if predicate(&item) { fold(acc, item) } else { acc }
1074 fn filter_try_fold<'a, T, Acc, R: Try<Ok = Acc>>(
1075 predicate: &'a mut impl FnMut(&T) -> bool,
1076 mut fold: impl FnMut(Acc, T) -> R + 'a,
1077 ) -> impl FnMut(Acc, T) -> R + 'a {
1078 move |acc, item| if predicate(&item) { fold(acc, item) } else { try { acc } }
1081 #[stable(feature = "rust1", since = "1.0.0")]
1082 impl<I: Iterator, P> Iterator for Filter<I, P>
1084 P: FnMut(&I::Item) -> bool,
1086 type Item = I::Item;
1089 fn next(&mut self) -> Option<I::Item> {
1090 self.iter.find(&mut self.predicate)
1094 fn size_hint(&self) -> (usize, Option<usize>) {
1095 let (_, upper) = self.iter.size_hint();
1096 (0, upper) // can't know a lower bound, due to the predicate
1099 // this special case allows the compiler to make `.filter(_).count()`
1100 // branchless. Barring perfect branch prediction (which is unattainable in
1101 // the general case), this will be much faster in >90% of cases (containing
1102 // virtually all real workloads) and only a tiny bit slower in the rest.
1104 // Having this specialization thus allows us to write `.filter(p).count()`
1105 // where we would otherwise write `.map(|x| p(x) as usize).sum()`, which is
1106 // less readable and also less backwards-compatible to Rust before 1.10.
1108 // Using the branchless version will also simplify the LLVM byte code, thus
1109 // leaving more budget for LLVM optimizations.
1111 fn count(self) -> usize {
1113 fn to_usize<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut(T) -> usize {
1114 move |x| predicate(&x) as usize
1117 self.iter.map(to_usize(self.predicate)).sum()
1121 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1124 Fold: FnMut(Acc, Self::Item) -> R,
1127 self.iter.try_fold(init, filter_try_fold(&mut self.predicate, fold))
1131 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1133 Fold: FnMut(Acc, Self::Item) -> Acc,
1135 self.iter.fold(init, filter_fold(self.predicate, fold))
1139 #[stable(feature = "rust1", since = "1.0.0")]
1140 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
1142 P: FnMut(&I::Item) -> bool,
1145 fn next_back(&mut self) -> Option<I::Item> {
1146 self.iter.rfind(&mut self.predicate)
1150 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1153 Fold: FnMut(Acc, Self::Item) -> R,
1156 self.iter.try_rfold(init, filter_try_fold(&mut self.predicate, fold))
1160 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1162 Fold: FnMut(Acc, Self::Item) -> Acc,
1164 self.iter.rfold(init, filter_fold(self.predicate, fold))
1168 #[stable(feature = "fused", since = "1.26.0")]
1169 impl<I: FusedIterator, P> FusedIterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {}
1171 #[unstable(issue = "none", feature = "inplace_iteration")]
1172 unsafe impl<S: Iterator, P, I: Iterator> SourceIter for Filter<I, P>
1174 P: FnMut(&I::Item) -> bool,
1175 I: SourceIter<Source = S>,
1180 unsafe fn as_inner(&mut self) -> &mut S {
1181 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
1182 unsafe { SourceIter::as_inner(&mut self.iter) }
1186 #[unstable(issue = "none", feature = "inplace_iteration")]
1187 unsafe impl<I: InPlaceIterable, P> InPlaceIterable for Filter<I, P> where P: FnMut(&I::Item) -> bool {}
1189 /// An iterator that uses `f` to both filter and map elements from `iter`.
1191 /// This `struct` is created by the [`filter_map`] method on [`Iterator`]. See its
1192 /// documentation for more.
1194 /// [`filter_map`]: Iterator::filter_map
1195 /// [`Iterator`]: trait.Iterator.html
1196 #[must_use = "iterators are lazy and do nothing unless consumed"]
1197 #[stable(feature = "rust1", since = "1.0.0")]
1199 pub struct FilterMap<I, F> {
1203 impl<I, F> FilterMap<I, F> {
1204 pub(super) fn new(iter: I, f: F) -> FilterMap<I, F> {
1205 FilterMap { iter, f }
1209 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1210 impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> {
1211 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1212 f.debug_struct("FilterMap").field("iter", &self.iter).finish()
1216 fn filter_map_fold<T, B, Acc>(
1217 mut f: impl FnMut(T) -> Option<B>,
1218 mut fold: impl FnMut(Acc, B) -> Acc,
1219 ) -> impl FnMut(Acc, T) -> Acc {
1220 move |acc, item| match f(item) {
1221 Some(x) => fold(acc, x),
1226 fn filter_map_try_fold<'a, T, B, Acc, R: Try<Ok = Acc>>(
1227 f: &'a mut impl FnMut(T) -> Option<B>,
1228 mut fold: impl FnMut(Acc, B) -> R + 'a,
1229 ) -> impl FnMut(Acc, T) -> R + 'a {
1230 move |acc, item| match f(item) {
1231 Some(x) => fold(acc, x),
1232 None => try { acc },
1236 #[stable(feature = "rust1", since = "1.0.0")]
1237 impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
1239 F: FnMut(I::Item) -> Option<B>,
1244 fn next(&mut self) -> Option<B> {
1245 self.iter.find_map(&mut self.f)
1249 fn size_hint(&self) -> (usize, Option<usize>) {
1250 let (_, upper) = self.iter.size_hint();
1251 (0, upper) // can't know a lower bound, due to the predicate
1255 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1258 Fold: FnMut(Acc, Self::Item) -> R,
1261 self.iter.try_fold(init, filter_map_try_fold(&mut self.f, fold))
1265 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1267 Fold: FnMut(Acc, Self::Item) -> Acc,
1269 self.iter.fold(init, filter_map_fold(self.f, fold))
1273 #[stable(feature = "rust1", since = "1.0.0")]
1274 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
1276 F: FnMut(I::Item) -> Option<B>,
1279 fn next_back(&mut self) -> Option<B> {
1282 f: &mut impl FnMut(T) -> Option<B>,
1283 ) -> impl FnMut((), T) -> ControlFlow<B> + '_ {
1284 move |(), x| match f(x) {
1285 Some(x) => ControlFlow::Break(x),
1286 None => ControlFlow::CONTINUE,
1290 self.iter.try_rfold((), find(&mut self.f)).break_value()
1294 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1297 Fold: FnMut(Acc, Self::Item) -> R,
1300 self.iter.try_rfold(init, filter_map_try_fold(&mut self.f, fold))
1304 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1306 Fold: FnMut(Acc, Self::Item) -> Acc,
1308 self.iter.rfold(init, filter_map_fold(self.f, fold))
1312 #[stable(feature = "fused", since = "1.26.0")]
1313 impl<B, I: FusedIterator, F> FusedIterator for FilterMap<I, F> where F: FnMut(I::Item) -> Option<B> {}
1315 #[unstable(issue = "none", feature = "inplace_iteration")]
1316 unsafe impl<S: Iterator, B, I: Iterator, F> SourceIter for FilterMap<I, F>
1318 F: FnMut(I::Item) -> Option<B>,
1319 I: SourceIter<Source = S>,
1324 unsafe fn as_inner(&mut self) -> &mut S {
1325 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
1326 unsafe { SourceIter::as_inner(&mut self.iter) }
1330 #[unstable(issue = "none", feature = "inplace_iteration")]
1331 unsafe impl<B, I: InPlaceIterable, F> InPlaceIterable for FilterMap<I, F> where
1332 F: FnMut(I::Item) -> Option<B>
1336 /// An iterator that yields the current count and the element during iteration.
1338 /// This `struct` is created by the [`enumerate`] method on [`Iterator`]. See its
1339 /// documentation for more.
1341 /// [`enumerate`]: Iterator::enumerate
1342 /// [`Iterator`]: trait.Iterator.html
1343 #[derive(Clone, Debug)]
1344 #[must_use = "iterators are lazy and do nothing unless consumed"]
1345 #[stable(feature = "rust1", since = "1.0.0")]
1346 pub struct Enumerate<I> {
1350 impl<I> Enumerate<I> {
1351 pub(super) fn new(iter: I) -> Enumerate<I> {
1352 Enumerate { iter, count: 0 }
1356 #[stable(feature = "rust1", since = "1.0.0")]
1357 impl<I> Iterator for Enumerate<I>
1361 type Item = (usize, <I as Iterator>::Item);
1363 /// # Overflow Behavior
1365 /// The method does no guarding against overflows, so enumerating more than
1366 /// `usize::MAX` elements either produces the wrong result or panics. If
1367 /// debug assertions are enabled, a panic is guaranteed.
1371 /// Might panic if the index of the element overflows a `usize`.
1373 fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1374 let a = self.iter.next()?;
1376 // Possible undefined overflow.
1377 AddAssign::add_assign(&mut self.count, 1);
1382 fn size_hint(&self) -> (usize, Option<usize>) {
1383 self.iter.size_hint()
1387 fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
1388 let a = self.iter.nth(n)?;
1389 // Possible undefined overflow.
1390 let i = Add::add(self.count, n);
1391 self.count = Add::add(i, 1);
1396 fn count(self) -> usize {
1401 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1404 Fold: FnMut(Acc, Self::Item) -> R,
1408 fn enumerate<'a, T, Acc, R>(
1409 count: &'a mut usize,
1410 mut fold: impl FnMut(Acc, (usize, T)) -> R + 'a,
1411 ) -> impl FnMut(Acc, T) -> R + 'a {
1413 let acc = fold(acc, (*count, item));
1414 // Possible undefined overflow.
1415 AddAssign::add_assign(count, 1);
1420 self.iter.try_fold(init, enumerate(&mut self.count, fold))
1424 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1426 Fold: FnMut(Acc, Self::Item) -> Acc,
1429 fn enumerate<T, Acc>(
1431 mut fold: impl FnMut(Acc, (usize, T)) -> Acc,
1432 ) -> impl FnMut(Acc, T) -> Acc {
1434 let acc = fold(acc, (count, item));
1435 // Possible undefined overflow.
1436 AddAssign::add_assign(&mut count, 1);
1441 self.iter.fold(init, enumerate(self.count, fold))
1444 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item
1446 Self: TrustedRandomAccess,
1448 // SAFETY: the caller must uphold the contract for
1449 // `Iterator::__iterator_get_unchecked`.
1450 let value = unsafe { try_get_unchecked(&mut self.iter, idx) };
1451 (Add::add(self.count, idx), value)
1455 #[stable(feature = "rust1", since = "1.0.0")]
1456 impl<I> DoubleEndedIterator for Enumerate<I>
1458 I: ExactSizeIterator + DoubleEndedIterator,
1461 fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1462 let a = self.iter.next_back()?;
1463 let len = self.iter.len();
1464 // Can safely add, `ExactSizeIterator` promises that the number of
1465 // elements fits into a `usize`.
1466 Some((self.count + len, a))
1470 fn nth_back(&mut self, n: usize) -> Option<(usize, <I as Iterator>::Item)> {
1471 let a = self.iter.nth_back(n)?;
1472 let len = self.iter.len();
1473 // Can safely add, `ExactSizeIterator` promises that the number of
1474 // elements fits into a `usize`.
1475 Some((self.count + len, a))
1479 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1482 Fold: FnMut(Acc, Self::Item) -> R,
1485 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1486 // that the number of elements fits into a `usize`.
1487 fn enumerate<T, Acc, R>(
1489 mut fold: impl FnMut(Acc, (usize, T)) -> R,
1490 ) -> impl FnMut(Acc, T) -> R {
1493 fold(acc, (count, item))
1497 let count = self.count + self.iter.len();
1498 self.iter.try_rfold(init, enumerate(count, fold))
1502 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1504 Fold: FnMut(Acc, Self::Item) -> Acc,
1506 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1507 // that the number of elements fits into a `usize`.
1508 fn enumerate<T, Acc>(
1510 mut fold: impl FnMut(Acc, (usize, T)) -> Acc,
1511 ) -> impl FnMut(Acc, T) -> Acc {
1514 fold(acc, (count, item))
1518 let count = self.count + self.iter.len();
1519 self.iter.rfold(init, enumerate(count, fold))
1523 #[stable(feature = "rust1", since = "1.0.0")]
1524 impl<I> ExactSizeIterator for Enumerate<I>
1526 I: ExactSizeIterator,
1528 fn len(&self) -> usize {
1532 fn is_empty(&self) -> bool {
1533 self.iter.is_empty()
1538 #[unstable(feature = "trusted_random_access", issue = "none")]
1539 unsafe impl<I> TrustedRandomAccess for Enumerate<I>
1541 I: TrustedRandomAccess,
1543 fn may_have_side_effect() -> bool {
1544 I::may_have_side_effect()
1548 #[stable(feature = "fused", since = "1.26.0")]
1549 impl<I> FusedIterator for Enumerate<I> where I: FusedIterator {}
1551 #[unstable(feature = "trusted_len", issue = "37572")]
1552 unsafe impl<I> TrustedLen for Enumerate<I> where I: TrustedLen {}
1554 #[unstable(issue = "none", feature = "inplace_iteration")]
1555 unsafe impl<S: Iterator, I: Iterator> SourceIter for Enumerate<I>
1557 I: SourceIter<Source = S>,
1562 unsafe fn as_inner(&mut self) -> &mut S {
1563 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
1564 unsafe { SourceIter::as_inner(&mut self.iter) }
1568 #[unstable(issue = "none", feature = "inplace_iteration")]
1569 unsafe impl<I: InPlaceIterable> InPlaceIterable for Enumerate<I> {}
1571 /// An iterator with a `peek()` that returns an optional reference to the next
1574 /// This `struct` is created by the [`peekable`] method on [`Iterator`]. See its
1575 /// documentation for more.
1577 /// [`peekable`]: Iterator::peekable
1578 /// [`Iterator`]: trait.Iterator.html
1579 #[derive(Clone, Debug)]
1580 #[must_use = "iterators are lazy and do nothing unless consumed"]
1581 #[stable(feature = "rust1", since = "1.0.0")]
1582 pub struct Peekable<I: Iterator> {
1584 /// Remember a peeked value, even if it was None.
1585 peeked: Option<Option<I::Item>>,
1587 impl<I: Iterator> Peekable<I> {
1588 pub(super) fn new(iter: I) -> Peekable<I> {
1589 Peekable { iter, peeked: None }
1593 // Peekable must remember if a None has been seen in the `.peek()` method.
1594 // It ensures that `.peek(); .peek();` or `.peek(); .next();` only advances the
1595 // underlying iterator at most once. This does not by itself make the iterator
1597 #[stable(feature = "rust1", since = "1.0.0")]
1598 impl<I: Iterator> Iterator for Peekable<I> {
1599 type Item = I::Item;
1602 fn next(&mut self) -> Option<I::Item> {
1603 match self.peeked.take() {
1605 None => self.iter.next(),
1610 #[rustc_inherit_overflow_checks]
1611 fn count(mut self) -> usize {
1612 match self.peeked.take() {
1614 Some(Some(_)) => 1 + self.iter.count(),
1615 None => self.iter.count(),
1620 fn nth(&mut self, n: usize) -> Option<I::Item> {
1621 match self.peeked.take() {
1623 Some(v @ Some(_)) if n == 0 => v,
1624 Some(Some(_)) => self.iter.nth(n - 1),
1625 None => self.iter.nth(n),
1630 fn last(mut self) -> Option<I::Item> {
1631 let peek_opt = match self.peeked.take() {
1632 Some(None) => return None,
1636 self.iter.last().or(peek_opt)
1640 fn size_hint(&self) -> (usize, Option<usize>) {
1641 let peek_len = match self.peeked {
1642 Some(None) => return (0, Some(0)),
1646 let (lo, hi) = self.iter.size_hint();
1647 let lo = lo.saturating_add(peek_len);
1649 Some(x) => x.checked_add(peek_len),
1656 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
1659 F: FnMut(B, Self::Item) -> R,
1662 let acc = match self.peeked.take() {
1663 Some(None) => return try { init },
1664 Some(Some(v)) => f(init, v)?,
1667 self.iter.try_fold(acc, f)
1671 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1673 Fold: FnMut(Acc, Self::Item) -> Acc,
1675 let acc = match self.peeked {
1676 Some(None) => return init,
1677 Some(Some(v)) => fold(init, v),
1680 self.iter.fold(acc, fold)
1684 #[stable(feature = "double_ended_peek_iterator", since = "1.38.0")]
1685 impl<I> DoubleEndedIterator for Peekable<I>
1687 I: DoubleEndedIterator,
1690 fn next_back(&mut self) -> Option<Self::Item> {
1691 match self.peeked.as_mut() {
1692 Some(v @ Some(_)) => self.iter.next_back().or_else(|| v.take()),
1694 None => self.iter.next_back(),
1699 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
1702 F: FnMut(B, Self::Item) -> R,
1705 match self.peeked.take() {
1706 Some(None) => try { init },
1707 Some(Some(v)) => match self.iter.try_rfold(init, &mut f).into_result() {
1708 Ok(acc) => f(acc, v),
1710 self.peeked = Some(Some(v));
1714 None => self.iter.try_rfold(init, f),
1719 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1721 Fold: FnMut(Acc, Self::Item) -> Acc,
1726 let acc = self.iter.rfold(init, &mut fold);
1729 None => self.iter.rfold(init, fold),
1734 #[stable(feature = "rust1", since = "1.0.0")]
1735 impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
1737 #[stable(feature = "fused", since = "1.26.0")]
1738 impl<I: FusedIterator> FusedIterator for Peekable<I> {}
1740 impl<I: Iterator> Peekable<I> {
1741 /// Returns a reference to the next() value without advancing the iterator.
1743 /// Like [`next`], if there is a value, it is wrapped in a `Some(T)`.
1744 /// But if the iteration is over, `None` is returned.
1746 /// [`next`]: Iterator::next
1748 /// Because `peek()` returns a reference, and many iterators iterate over
1749 /// references, there can be a possibly confusing situation where the
1750 /// return value is a double reference. You can see this effect in the
1758 /// let xs = [1, 2, 3];
1760 /// let mut iter = xs.iter().peekable();
1762 /// // peek() lets us see into the future
1763 /// assert_eq!(iter.peek(), Some(&&1));
1764 /// assert_eq!(iter.next(), Some(&1));
1766 /// assert_eq!(iter.next(), Some(&2));
1768 /// // The iterator does not advance even if we `peek` multiple times
1769 /// assert_eq!(iter.peek(), Some(&&3));
1770 /// assert_eq!(iter.peek(), Some(&&3));
1772 /// assert_eq!(iter.next(), Some(&3));
1774 /// // After the iterator is finished, so is `peek()`
1775 /// assert_eq!(iter.peek(), None);
1776 /// assert_eq!(iter.next(), None);
1779 #[stable(feature = "rust1", since = "1.0.0")]
1780 pub fn peek(&mut self) -> Option<&I::Item> {
1781 let iter = &mut self.iter;
1782 self.peeked.get_or_insert_with(|| iter.next()).as_ref()
1785 /// Consume and return the next value of this iterator if a condition is true.
1787 /// If `func` returns `true` for the next value of this iterator, consume and return it.
1788 /// Otherwise, return `None`.
1791 /// Consume a number if it's equal to 0.
1793 /// #![feature(peekable_next_if)]
1794 /// let mut iter = (0..5).peekable();
1795 /// // The first item of the iterator is 0; consume it.
1796 /// assert_eq!(iter.next_if(|&x| x == 0), Some(0));
1797 /// // The next item returned is now 1, so `consume` will return `false`.
1798 /// assert_eq!(iter.next_if(|&x| x == 0), None);
1799 /// // `next_if` saves the value of the next item if it was not equal to `expected`.
1800 /// assert_eq!(iter.next(), Some(1));
1803 /// Consume any number less than 10.
1805 /// #![feature(peekable_next_if)]
1806 /// let mut iter = (1..20).peekable();
1807 /// // Consume all numbers less than 10
1808 /// while iter.next_if(|&x| x < 10).is_some() {}
1809 /// // The next value returned will be 10
1810 /// assert_eq!(iter.next(), Some(10));
1812 #[unstable(feature = "peekable_next_if", issue = "72480")]
1813 pub fn next_if(&mut self, func: impl FnOnce(&I::Item) -> bool) -> Option<I::Item> {
1815 Some(matched) if func(&matched) => Some(matched),
1817 // Since we called `self.next()`, we consumed `self.peeked`.
1818 assert!(self.peeked.is_none());
1819 self.peeked = Some(other);
1825 /// Consume and return the next item if it is equal to `expected`.
1828 /// Consume a number if it's equal to 0.
1830 /// #![feature(peekable_next_if)]
1831 /// let mut iter = (0..5).peekable();
1832 /// // The first item of the iterator is 0; consume it.
1833 /// assert_eq!(iter.next_if_eq(&0), Some(0));
1834 /// // The next item returned is now 1, so `consume` will return `false`.
1835 /// assert_eq!(iter.next_if_eq(&0), None);
1836 /// // `next_if_eq` saves the value of the next item if it was not equal to `expected`.
1837 /// assert_eq!(iter.next(), Some(1));
1839 #[unstable(feature = "peekable_next_if", issue = "72480")]
1840 pub fn next_if_eq<T>(&mut self, expected: &T) -> Option<I::Item>
1843 I::Item: PartialEq<T>,
1845 self.next_if(|next| next == expected)
1849 #[unstable(feature = "trusted_len", issue = "37572")]
1850 unsafe impl<I> TrustedLen for Peekable<I> where I: TrustedLen {}
1852 #[unstable(issue = "none", feature = "inplace_iteration")]
1853 unsafe impl<S: Iterator, I: Iterator> SourceIter for Peekable<I>
1855 I: SourceIter<Source = S>,
1860 unsafe fn as_inner(&mut self) -> &mut S {
1861 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
1862 unsafe { SourceIter::as_inner(&mut self.iter) }
1866 #[unstable(issue = "none", feature = "inplace_iteration")]
1867 unsafe impl<I: InPlaceIterable> InPlaceIterable for Peekable<I> {}
1869 /// An iterator that rejects elements while `predicate` returns `true`.
1871 /// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its
1872 /// documentation for more.
1874 /// [`skip_while`]: Iterator::skip_while
1875 /// [`Iterator`]: trait.Iterator.html
1876 #[must_use = "iterators are lazy and do nothing unless consumed"]
1877 #[stable(feature = "rust1", since = "1.0.0")]
1879 pub struct SkipWhile<I, P> {
1884 impl<I, P> SkipWhile<I, P> {
1885 pub(super) fn new(iter: I, predicate: P) -> SkipWhile<I, P> {
1886 SkipWhile { iter, flag: false, predicate }
1890 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1891 impl<I: fmt::Debug, P> fmt::Debug for SkipWhile<I, P> {
1892 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1893 f.debug_struct("SkipWhile").field("iter", &self.iter).field("flag", &self.flag).finish()
1897 #[stable(feature = "rust1", since = "1.0.0")]
1898 impl<I: Iterator, P> Iterator for SkipWhile<I, P>
1900 P: FnMut(&I::Item) -> bool,
1902 type Item = I::Item;
1905 fn next(&mut self) -> Option<I::Item> {
1908 pred: &'a mut impl FnMut(&T) -> bool,
1909 ) -> impl FnMut(&T) -> bool + 'a {
1911 if *flag || !pred(x) {
1920 let flag = &mut self.flag;
1921 let pred = &mut self.predicate;
1922 self.iter.find(check(flag, pred))
1926 fn size_hint(&self) -> (usize, Option<usize>) {
1927 let (_, upper) = self.iter.size_hint();
1928 (0, upper) // can't know a lower bound, due to the predicate
1932 fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
1935 Fold: FnMut(Acc, Self::Item) -> R,
1940 Some(v) => init = fold(init, v)?,
1941 None => return try { init },
1944 self.iter.try_fold(init, fold)
1948 fn fold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
1950 Fold: FnMut(Acc, Self::Item) -> Acc,
1954 Some(v) => init = fold(init, v),
1955 None => return init,
1958 self.iter.fold(init, fold)
1962 #[stable(feature = "fused", since = "1.26.0")]
1963 impl<I, P> FusedIterator for SkipWhile<I, P>
1966 P: FnMut(&I::Item) -> bool,
1970 #[unstable(issue = "none", feature = "inplace_iteration")]
1971 unsafe impl<S: Iterator, P, I: Iterator> SourceIter for SkipWhile<I, P>
1973 P: FnMut(&I::Item) -> bool,
1974 I: SourceIter<Source = S>,
1979 unsafe fn as_inner(&mut self) -> &mut S {
1980 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
1981 unsafe { SourceIter::as_inner(&mut self.iter) }
1985 #[unstable(issue = "none", feature = "inplace_iteration")]
1986 unsafe impl<I: InPlaceIterable, F> InPlaceIterable for SkipWhile<I, F> where
1987 F: FnMut(&I::Item) -> bool
1991 /// An iterator that only accepts elements while `predicate` returns `true`.
1993 /// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its
1994 /// documentation for more.
1996 /// [`take_while`]: Iterator::take_while
1997 /// [`Iterator`]: trait.Iterator.html
1998 #[must_use = "iterators are lazy and do nothing unless consumed"]
1999 #[stable(feature = "rust1", since = "1.0.0")]
2001 pub struct TakeWhile<I, P> {
2006 impl<I, P> TakeWhile<I, P> {
2007 pub(super) fn new(iter: I, predicate: P) -> TakeWhile<I, P> {
2008 TakeWhile { iter, flag: false, predicate }
2012 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2013 impl<I: fmt::Debug, P> fmt::Debug for TakeWhile<I, P> {
2014 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2015 f.debug_struct("TakeWhile").field("iter", &self.iter).field("flag", &self.flag).finish()
2019 #[stable(feature = "rust1", since = "1.0.0")]
2020 impl<I: Iterator, P> Iterator for TakeWhile<I, P>
2022 P: FnMut(&I::Item) -> bool,
2024 type Item = I::Item;
2027 fn next(&mut self) -> Option<I::Item> {
2031 let x = self.iter.next()?;
2032 if (self.predicate)(&x) {
2042 fn size_hint(&self) -> (usize, Option<usize>) {
2046 let (_, upper) = self.iter.size_hint();
2047 (0, upper) // can't know a lower bound, due to the predicate
2052 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2055 Fold: FnMut(Acc, Self::Item) -> R,
2058 fn check<'a, T, Acc, R: Try<Ok = Acc>>(
2060 p: &'a mut impl FnMut(&T) -> bool,
2061 mut fold: impl FnMut(Acc, T) -> R + 'a,
2062 ) -> impl FnMut(Acc, T) -> ControlFlow<R, Acc> + 'a {
2065 ControlFlow::from_try(fold(acc, x))
2068 ControlFlow::Break(try { acc })
2076 let flag = &mut self.flag;
2077 let p = &mut self.predicate;
2078 self.iter.try_fold(init, check(flag, p, fold)).into_try()
2083 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2086 Fold: FnMut(Acc, Self::Item) -> Acc,
2089 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2090 move |acc, x| Ok(f(acc, x))
2093 self.try_fold(init, ok(fold)).unwrap()
2097 #[stable(feature = "fused", since = "1.26.0")]
2098 impl<I, P> FusedIterator for TakeWhile<I, P>
2101 P: FnMut(&I::Item) -> bool,
2105 #[unstable(issue = "none", feature = "inplace_iteration")]
2106 unsafe impl<S: Iterator, P, I: Iterator> SourceIter for TakeWhile<I, P>
2108 P: FnMut(&I::Item) -> bool,
2109 I: SourceIter<Source = S>,
2114 unsafe fn as_inner(&mut self) -> &mut S {
2115 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
2116 unsafe { SourceIter::as_inner(&mut self.iter) }
2120 #[unstable(issue = "none", feature = "inplace_iteration")]
2121 unsafe impl<I: InPlaceIterable, F> InPlaceIterable for TakeWhile<I, F> where
2122 F: FnMut(&I::Item) -> bool
2126 /// An iterator that only accepts elements while `predicate` returns `Some(_)`.
2128 /// This `struct` is created by the [`map_while`] method on [`Iterator`]. See its
2129 /// documentation for more.
2131 /// [`map_while`]: Iterator::map_while
2132 /// [`Iterator`]: trait.Iterator.html
2133 #[must_use = "iterators are lazy and do nothing unless consumed"]
2134 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
2136 pub struct MapWhile<I, P> {
2141 impl<I, P> MapWhile<I, P> {
2142 pub(super) fn new(iter: I, predicate: P) -> MapWhile<I, P> {
2143 MapWhile { iter, predicate }
2147 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
2148 impl<I: fmt::Debug, P> fmt::Debug for MapWhile<I, P> {
2149 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2150 f.debug_struct("MapWhile").field("iter", &self.iter).finish()
2154 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
2155 impl<B, I: Iterator, P> Iterator for MapWhile<I, P>
2157 P: FnMut(I::Item) -> Option<B>,
2162 fn next(&mut self) -> Option<B> {
2163 let x = self.iter.next()?;
2168 fn size_hint(&self) -> (usize, Option<usize>) {
2169 let (_, upper) = self.iter.size_hint();
2170 (0, upper) // can't know a lower bound, due to the predicate
2174 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R
2177 Fold: FnMut(Acc, Self::Item) -> R,
2180 let Self { iter, predicate } = self;
2181 iter.try_fold(init, |acc, x| match predicate(x) {
2182 Some(item) => ControlFlow::from_try(fold(acc, item)),
2183 None => ControlFlow::Break(try { acc }),
2189 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2192 Fold: FnMut(Acc, Self::Item) -> Acc,
2195 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2196 move |acc, x| Ok(f(acc, x))
2199 self.try_fold(init, ok(fold)).unwrap()
2203 #[unstable(issue = "none", feature = "inplace_iteration")]
2204 unsafe impl<S: Iterator, B, I: Iterator, P> SourceIter for MapWhile<I, P>
2206 P: FnMut(I::Item) -> Option<B>,
2207 I: SourceIter<Source = S>,
2212 unsafe fn as_inner(&mut self) -> &mut S {
2213 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
2214 unsafe { SourceIter::as_inner(&mut self.iter) }
2218 #[unstable(issue = "none", feature = "inplace_iteration")]
2219 unsafe impl<B, I: InPlaceIterable, P> InPlaceIterable for MapWhile<I, P> where
2220 P: FnMut(I::Item) -> Option<B>
2224 /// An iterator that skips over `n` elements of `iter`.
2226 /// This `struct` is created by the [`skip`] method on [`Iterator`]. See its
2227 /// documentation for more.
2229 /// [`skip`]: Iterator::skip
2230 /// [`Iterator`]: trait.Iterator.html
2231 #[derive(Clone, Debug)]
2232 #[must_use = "iterators are lazy and do nothing unless consumed"]
2233 #[stable(feature = "rust1", since = "1.0.0")]
2234 pub struct Skip<I> {
2239 pub(super) fn new(iter: I, n: usize) -> Skip<I> {
2244 #[stable(feature = "rust1", since = "1.0.0")]
2245 impl<I> Iterator for Skip<I>
2249 type Item = <I as Iterator>::Item;
2252 fn next(&mut self) -> Option<I::Item> {
2258 self.iter.nth(old_n)
2263 fn nth(&mut self, n: usize) -> Option<I::Item> {
2264 // Can't just add n + self.n due to overflow.
2266 let to_skip = self.n;
2269 self.iter.nth(to_skip - 1)?;
2275 fn count(mut self) -> usize {
2278 if self.iter.nth(self.n - 1).is_none() {
2286 fn last(mut self) -> Option<I::Item> {
2289 self.iter.nth(self.n - 1)?;
2295 fn size_hint(&self) -> (usize, Option<usize>) {
2296 let (lower, upper) = self.iter.size_hint();
2298 let lower = lower.saturating_sub(self.n);
2299 let upper = match upper {
2300 Some(x) => Some(x.saturating_sub(self.n)),
2308 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2311 Fold: FnMut(Acc, Self::Item) -> R,
2318 if self.iter.nth(n - 1).is_none() {
2319 return try { init };
2322 self.iter.try_fold(init, fold)
2326 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2328 Fold: FnMut(Acc, Self::Item) -> Acc,
2332 if self.iter.nth(self.n - 1).is_none() {
2336 self.iter.fold(init, fold)
2340 #[stable(feature = "rust1", since = "1.0.0")]
2341 impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
2343 #[stable(feature = "double_ended_skip_iterator", since = "1.9.0")]
2344 impl<I> DoubleEndedIterator for Skip<I>
2346 I: DoubleEndedIterator + ExactSizeIterator,
2348 fn next_back(&mut self) -> Option<Self::Item> {
2349 if self.len() > 0 { self.iter.next_back() } else { None }
2353 fn nth_back(&mut self, n: usize) -> Option<I::Item> {
2354 let len = self.len();
2356 self.iter.nth_back(n)
2359 // consume the original iterator
2360 self.iter.nth_back(len - 1);
2366 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2369 Fold: FnMut(Acc, Self::Item) -> R,
2372 fn check<T, Acc, R: Try<Ok = Acc>>(
2374 mut fold: impl FnMut(Acc, T) -> R,
2375 ) -> impl FnMut(Acc, T) -> ControlFlow<R, Acc> {
2378 let r = fold(acc, x);
2379 if n == 0 { ControlFlow::Break(r) } else { ControlFlow::from_try(r) }
2384 if n == 0 { try { init } } else { self.iter.try_rfold(init, check(n, fold)).into_try() }
2387 fn rfold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2389 Fold: FnMut(Acc, Self::Item) -> Acc,
2392 fn ok<Acc, T>(mut f: impl FnMut(Acc, T) -> Acc) -> impl FnMut(Acc, T) -> Result<Acc, !> {
2393 move |acc, x| Ok(f(acc, x))
2396 self.try_rfold(init, ok(fold)).unwrap()
2400 #[stable(feature = "fused", since = "1.26.0")]
2401 impl<I> FusedIterator for Skip<I> where I: FusedIterator {}
2403 #[unstable(issue = "none", feature = "inplace_iteration")]
2404 unsafe impl<S: Iterator, I: Iterator> SourceIter for Skip<I>
2406 I: SourceIter<Source = S>,
2411 unsafe fn as_inner(&mut self) -> &mut S {
2412 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
2413 unsafe { SourceIter::as_inner(&mut self.iter) }
2417 #[unstable(issue = "none", feature = "inplace_iteration")]
2418 unsafe impl<I: InPlaceIterable> InPlaceIterable for Skip<I> {}
2420 /// An iterator that only iterates over the first `n` iterations of `iter`.
2422 /// This `struct` is created by the [`take`] method on [`Iterator`]. See its
2423 /// documentation for more.
2425 /// [`take`]: Iterator::take
2426 /// [`Iterator`]: trait.Iterator.html
2427 #[derive(Clone, Debug)]
2428 #[must_use = "iterators are lazy and do nothing unless consumed"]
2429 #[stable(feature = "rust1", since = "1.0.0")]
2430 pub struct Take<I> {
2432 pub(super) n: usize,
2435 pub(super) fn new(iter: I, n: usize) -> Take<I> {
2440 #[stable(feature = "rust1", since = "1.0.0")]
2441 impl<I> Iterator for Take<I>
2445 type Item = <I as Iterator>::Item;
2448 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2458 fn nth(&mut self, n: usize) -> Option<I::Item> {
2464 self.iter.nth(self.n - 1);
2472 fn size_hint(&self) -> (usize, Option<usize>) {
2474 return (0, Some(0));
2477 let (lower, upper) = self.iter.size_hint();
2479 let lower = cmp::min(lower, self.n);
2481 let upper = match upper {
2482 Some(x) if x < self.n => Some(x),
2490 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2493 Fold: FnMut(Acc, Self::Item) -> R,
2496 fn check<'a, T, Acc, R: Try<Ok = Acc>>(
2498 mut fold: impl FnMut(Acc, T) -> R + 'a,
2499 ) -> impl FnMut(Acc, T) -> ControlFlow<R, Acc> + 'a {
2502 let r = fold(acc, x);
2503 if *n == 0 { ControlFlow::Break(r) } else { ControlFlow::from_try(r) }
2510 let n = &mut self.n;
2511 self.iter.try_fold(init, check(n, fold)).into_try()
2516 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2519 Fold: FnMut(Acc, Self::Item) -> Acc,
2522 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2523 move |acc, x| Ok(f(acc, x))
2526 self.try_fold(init, ok(fold)).unwrap()
2530 #[unstable(issue = "none", feature = "inplace_iteration")]
2531 unsafe impl<S: Iterator, I: Iterator> SourceIter for Take<I>
2533 I: SourceIter<Source = S>,
2538 unsafe fn as_inner(&mut self) -> &mut S {
2539 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
2540 unsafe { SourceIter::as_inner(&mut self.iter) }
2544 #[unstable(issue = "none", feature = "inplace_iteration")]
2545 unsafe impl<I: InPlaceIterable> InPlaceIterable for Take<I> {}
2547 #[stable(feature = "double_ended_take_iterator", since = "1.38.0")]
2548 impl<I> DoubleEndedIterator for Take<I>
2550 I: DoubleEndedIterator + ExactSizeIterator,
2553 fn next_back(&mut self) -> Option<Self::Item> {
2559 self.iter.nth_back(self.iter.len().saturating_sub(n))
2564 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2565 let len = self.iter.len();
2567 let m = len.saturating_sub(self.n) + n;
2569 self.iter.nth_back(m)
2572 self.iter.nth_back(len - 1);
2579 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2582 Fold: FnMut(Acc, Self::Item) -> R,
2588 let len = self.iter.len();
2589 if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() {
2592 self.iter.try_rfold(init, fold)
2598 fn rfold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2601 Fold: FnMut(Acc, Self::Item) -> Acc,
2606 let len = self.iter.len();
2607 if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() {
2610 self.iter.rfold(init, fold)
2616 #[stable(feature = "rust1", since = "1.0.0")]
2617 impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
2619 #[stable(feature = "fused", since = "1.26.0")]
2620 impl<I> FusedIterator for Take<I> where I: FusedIterator {}
2622 #[unstable(feature = "trusted_len", issue = "37572")]
2623 unsafe impl<I: TrustedLen> TrustedLen for Take<I> {}
2625 /// An iterator to maintain state while iterating another iterator.
2627 /// This `struct` is created by the [`scan`] method on [`Iterator`]. See its
2628 /// documentation for more.
2630 /// [`scan`]: Iterator::scan
2631 /// [`Iterator`]: trait.Iterator.html
2632 #[must_use = "iterators are lazy and do nothing unless consumed"]
2633 #[stable(feature = "rust1", since = "1.0.0")]
2635 pub struct Scan<I, St, F> {
2640 impl<I, St, F> Scan<I, St, F> {
2641 pub(super) fn new(iter: I, state: St, f: F) -> Scan<I, St, F> {
2642 Scan { iter, state, f }
2646 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2647 impl<I: fmt::Debug, St: fmt::Debug, F> fmt::Debug for Scan<I, St, F> {
2648 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2649 f.debug_struct("Scan").field("iter", &self.iter).field("state", &self.state).finish()
2653 #[stable(feature = "rust1", since = "1.0.0")]
2654 impl<B, I, St, F> Iterator for Scan<I, St, F>
2657 F: FnMut(&mut St, I::Item) -> Option<B>,
2662 fn next(&mut self) -> Option<B> {
2663 let a = self.iter.next()?;
2664 (self.f)(&mut self.state, a)
2668 fn size_hint(&self) -> (usize, Option<usize>) {
2669 let (_, upper) = self.iter.size_hint();
2670 (0, upper) // can't know a lower bound, due to the scan function
2674 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2677 Fold: FnMut(Acc, Self::Item) -> R,
2680 fn scan<'a, T, St, B, Acc, R: Try<Ok = Acc>>(
2682 f: &'a mut impl FnMut(&mut St, T) -> Option<B>,
2683 mut fold: impl FnMut(Acc, B) -> R + 'a,
2684 ) -> impl FnMut(Acc, T) -> ControlFlow<R, Acc> + 'a {
2685 move |acc, x| match f(state, x) {
2686 None => ControlFlow::Break(try { acc }),
2687 Some(x) => ControlFlow::from_try(fold(acc, x)),
2691 let state = &mut self.state;
2692 let f = &mut self.f;
2693 self.iter.try_fold(init, scan(state, f, fold)).into_try()
2697 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2700 Fold: FnMut(Acc, Self::Item) -> Acc,
2703 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2704 move |acc, x| Ok(f(acc, x))
2707 self.try_fold(init, ok(fold)).unwrap()
2711 #[unstable(issue = "none", feature = "inplace_iteration")]
2712 unsafe impl<St, F, B, S: Iterator, I: Iterator> SourceIter for Scan<I, St, F>
2714 I: SourceIter<Source = S>,
2715 F: FnMut(&mut St, I::Item) -> Option<B>,
2720 unsafe fn as_inner(&mut self) -> &mut S {
2721 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
2722 unsafe { SourceIter::as_inner(&mut self.iter) }
2726 #[unstable(issue = "none", feature = "inplace_iteration")]
2727 unsafe impl<St, F, B, I: InPlaceIterable> InPlaceIterable for Scan<I, St, F> where
2728 F: FnMut(&mut St, I::Item) -> Option<B>
2732 /// An iterator that calls a function with a reference to each element before
2735 /// This `struct` is created by the [`inspect`] method on [`Iterator`]. See its
2736 /// documentation for more.
2738 /// [`inspect`]: Iterator::inspect
2739 /// [`Iterator`]: trait.Iterator.html
2740 #[must_use = "iterators are lazy and do nothing unless consumed"]
2741 #[stable(feature = "rust1", since = "1.0.0")]
2743 pub struct Inspect<I, F> {
2747 impl<I, F> Inspect<I, F> {
2748 pub(super) fn new(iter: I, f: F) -> Inspect<I, F> {
2753 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2754 impl<I: fmt::Debug, F> fmt::Debug for Inspect<I, F> {
2755 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2756 f.debug_struct("Inspect").field("iter", &self.iter).finish()
2760 impl<I: Iterator, F> Inspect<I, F>
2765 fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
2766 if let Some(ref a) = elt {
2774 fn inspect_fold<T, Acc>(
2775 mut f: impl FnMut(&T),
2776 mut fold: impl FnMut(Acc, T) -> Acc,
2777 ) -> impl FnMut(Acc, T) -> Acc {
2784 fn inspect_try_fold<'a, T, Acc, R>(
2785 f: &'a mut impl FnMut(&T),
2786 mut fold: impl FnMut(Acc, T) -> R + 'a,
2787 ) -> impl FnMut(Acc, T) -> R + 'a {
2794 #[stable(feature = "rust1", since = "1.0.0")]
2795 impl<I: Iterator, F> Iterator for Inspect<I, F>
2799 type Item = I::Item;
2802 fn next(&mut self) -> Option<I::Item> {
2803 let next = self.iter.next();
2804 self.do_inspect(next)
2808 fn size_hint(&self) -> (usize, Option<usize>) {
2809 self.iter.size_hint()
2813 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2816 Fold: FnMut(Acc, Self::Item) -> R,
2819 self.iter.try_fold(init, inspect_try_fold(&mut self.f, fold))
2823 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2825 Fold: FnMut(Acc, Self::Item) -> Acc,
2827 self.iter.fold(init, inspect_fold(self.f, fold))
2831 #[stable(feature = "rust1", since = "1.0.0")]
2832 impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
2837 fn next_back(&mut self) -> Option<I::Item> {
2838 let next = self.iter.next_back();
2839 self.do_inspect(next)
2843 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2846 Fold: FnMut(Acc, Self::Item) -> R,
2849 self.iter.try_rfold(init, inspect_try_fold(&mut self.f, fold))
2853 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2855 Fold: FnMut(Acc, Self::Item) -> Acc,
2857 self.iter.rfold(init, inspect_fold(self.f, fold))
2861 #[stable(feature = "rust1", since = "1.0.0")]
2862 impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F>
2866 fn len(&self) -> usize {
2870 fn is_empty(&self) -> bool {
2871 self.iter.is_empty()
2875 #[stable(feature = "fused", since = "1.26.0")]
2876 impl<I: FusedIterator, F> FusedIterator for Inspect<I, F> where F: FnMut(&I::Item) {}
2878 #[unstable(issue = "none", feature = "inplace_iteration")]
2879 unsafe impl<S: Iterator, I: Iterator, F> SourceIter for Inspect<I, F>
2882 I: SourceIter<Source = S>,
2887 unsafe fn as_inner(&mut self) -> &mut S {
2888 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
2889 unsafe { SourceIter::as_inner(&mut self.iter) }
2893 #[unstable(issue = "none", feature = "inplace_iteration")]
2894 unsafe impl<I: InPlaceIterable, F> InPlaceIterable for Inspect<I, F> where F: FnMut(&I::Item) {}
2896 /// An iterator adapter that produces output as long as the underlying
2897 /// iterator produces `Result::Ok` values.
2899 /// If an error is encountered, the iterator stops and the error is
2901 pub(crate) struct ResultShunt<'a, I, E> {
2903 error: &'a mut Result<(), E>,
2906 /// Process the given iterator as if it yielded a `T` instead of a
2907 /// `Result<T, _>`. Any errors will stop the inner iterator and
2908 /// the overall result will be an error.
2909 pub(crate) fn process_results<I, T, E, F, U>(iter: I, mut f: F) -> Result<U, E>
2911 I: Iterator<Item = Result<T, E>>,
2912 for<'a> F: FnMut(ResultShunt<'a, I, E>) -> U,
2914 let mut error = Ok(());
2915 let shunt = ResultShunt { iter, error: &mut error };
2916 let value = f(shunt);
2917 error.map(|()| value)
2920 impl<I, T, E> Iterator for ResultShunt<'_, I, E>
2922 I: Iterator<Item = Result<T, E>>,
2926 fn next(&mut self) -> Option<Self::Item> {
2930 fn size_hint(&self) -> (usize, Option<usize>) {
2931 if self.error.is_err() {
2934 let (_, upper) = self.iter.size_hint();
2939 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
2941 F: FnMut(B, Self::Item) -> R,
2944 let error = &mut *self.error;
2946 .try_fold(init, |acc, x| match x {
2947 Ok(x) => ControlFlow::from_try(f(acc, x)),
2950 ControlFlow::Break(try { acc })
2956 fn fold<B, F>(mut self, init: B, fold: F) -> B
2959 F: FnMut(B, Self::Item) -> B,
2962 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2963 move |acc, x| Ok(f(acc, x))
2966 self.try_fold(init, ok(fold)).unwrap()