4 use crate::ops::{Add, AddAssign, Try};
6 use super::{from_fn, LoopState};
7 use super::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator, TrustedLen};
14 pub use self::chain::Chain;
15 #[stable(feature = "rust1", since = "1.0.0")]
16 pub use self::flatten::{FlatMap, Flatten};
17 pub use self::fuse::Fuse;
18 use self::zip::try_get_unchecked;
19 pub(crate) use self::zip::TrustedRandomAccess;
20 pub use self::zip::Zip;
22 /// A double-ended iterator with the direction inverted.
24 /// This `struct` is created by the [`rev`] method on [`Iterator`]. See its
25 /// documentation for more.
27 /// [`rev`]: trait.Iterator.html#method.rev
28 /// [`Iterator`]: trait.Iterator.html
29 #[derive(Clone, Debug)]
30 #[must_use = "iterators are lazy and do nothing unless consumed"]
31 #[stable(feature = "rust1", since = "1.0.0")]
36 pub(super) fn new(iter: T) -> Rev<T> {
41 #[stable(feature = "rust1", since = "1.0.0")]
42 impl<I> Iterator for Rev<I>
44 I: DoubleEndedIterator,
46 type Item = <I as Iterator>::Item;
49 fn next(&mut self) -> Option<<I as Iterator>::Item> {
53 fn size_hint(&self) -> (usize, Option<usize>) {
58 fn nth(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
62 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
65 F: FnMut(B, Self::Item) -> R,
68 self.iter.try_rfold(init, f)
71 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
73 F: FnMut(Acc, Self::Item) -> Acc,
75 self.iter.rfold(init, f)
79 fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
81 P: FnMut(&Self::Item) -> bool,
83 self.iter.rfind(predicate)
87 #[stable(feature = "rust1", since = "1.0.0")]
88 impl<I> DoubleEndedIterator for Rev<I>
90 I: DoubleEndedIterator,
93 fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
98 fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
102 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
105 F: FnMut(B, Self::Item) -> R,
108 self.iter.try_fold(init, f)
111 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
113 F: FnMut(Acc, Self::Item) -> Acc,
115 self.iter.fold(init, f)
118 fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
120 P: FnMut(&Self::Item) -> bool,
122 self.iter.find(predicate)
126 #[stable(feature = "rust1", since = "1.0.0")]
127 impl<I> ExactSizeIterator for Rev<I>
129 I: ExactSizeIterator + DoubleEndedIterator,
131 fn len(&self) -> usize {
135 fn is_empty(&self) -> bool {
140 #[stable(feature = "fused", since = "1.26.0")]
141 impl<I> FusedIterator for Rev<I> where I: FusedIterator + DoubleEndedIterator {}
143 #[unstable(feature = "trusted_len", issue = "37572")]
144 unsafe impl<I> TrustedLen for Rev<I> where I: TrustedLen + DoubleEndedIterator {}
146 /// An iterator that copies the elements of an underlying iterator.
148 /// This `struct` is created by the [`copied`] method on [`Iterator`]. See its
149 /// documentation for more.
151 /// [`copied`]: trait.Iterator.html#method.copied
152 /// [`Iterator`]: trait.Iterator.html
153 #[stable(feature = "iter_copied", since = "1.36.0")]
154 #[must_use = "iterators are lazy and do nothing unless consumed"]
155 #[derive(Clone, Debug)]
156 pub struct Copied<I> {
161 pub(super) fn new(it: I) -> Copied<I> {
166 fn copy_fold<T: Copy, Acc>(mut f: impl FnMut(Acc, T) -> Acc) -> impl FnMut(Acc, &T) -> Acc {
167 move |acc, &elt| f(acc, elt)
170 fn copy_try_fold<T: Copy, Acc, R>(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R {
171 move |acc, &elt| f(acc, elt)
174 #[stable(feature = "iter_copied", since = "1.36.0")]
175 impl<'a, I, T: 'a> Iterator for Copied<I>
177 I: Iterator<Item = &'a T>,
182 fn next(&mut self) -> Option<T> {
183 self.it.next().copied()
186 fn size_hint(&self) -> (usize, Option<usize>) {
190 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
193 F: FnMut(B, Self::Item) -> R,
196 self.it.try_fold(init, copy_try_fold(f))
199 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
201 F: FnMut(Acc, Self::Item) -> Acc,
203 self.it.fold(init, copy_fold(f))
206 fn nth(&mut self, n: usize) -> Option<T> {
207 self.it.nth(n).copied()
210 fn last(self) -> Option<T> {
211 self.it.last().copied()
214 fn count(self) -> usize {
218 unsafe fn get_unchecked(&mut self, idx: usize) -> T
220 Self: TrustedRandomAccess,
222 // SAFETY: the caller must uphold the contract for
223 // `Iterator::get_unchecked`.
224 *unsafe { try_get_unchecked(&mut self.it, idx) }
228 #[stable(feature = "iter_copied", since = "1.36.0")]
229 impl<'a, I, T: 'a> DoubleEndedIterator for Copied<I>
231 I: DoubleEndedIterator<Item = &'a T>,
234 fn next_back(&mut self) -> Option<T> {
235 self.it.next_back().copied()
238 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
241 F: FnMut(B, Self::Item) -> R,
244 self.it.try_rfold(init, copy_try_fold(f))
247 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
249 F: FnMut(Acc, Self::Item) -> Acc,
251 self.it.rfold(init, copy_fold(f))
255 #[stable(feature = "iter_copied", since = "1.36.0")]
256 impl<'a, I, T: 'a> ExactSizeIterator for Copied<I>
258 I: ExactSizeIterator<Item = &'a T>,
261 fn len(&self) -> usize {
265 fn is_empty(&self) -> bool {
270 #[stable(feature = "iter_copied", since = "1.36.0")]
271 impl<'a, I, T: 'a> FusedIterator for Copied<I>
273 I: FusedIterator<Item = &'a T>,
279 #[unstable(feature = "trusted_random_access", issue = "none")]
280 unsafe impl<I> TrustedRandomAccess for Copied<I>
282 I: TrustedRandomAccess,
285 fn may_have_side_effect() -> bool {
286 I::may_have_side_effect()
290 #[stable(feature = "iter_copied", since = "1.36.0")]
291 unsafe impl<'a, I, T: 'a> TrustedLen for Copied<I>
293 I: TrustedLen<Item = &'a T>,
298 /// An iterator that clones the elements of an underlying iterator.
300 /// This `struct` is created by the [`cloned`] method on [`Iterator`]. See its
301 /// documentation for more.
303 /// [`cloned`]: trait.Iterator.html#method.cloned
304 /// [`Iterator`]: trait.Iterator.html
305 #[stable(feature = "iter_cloned", since = "1.1.0")]
306 #[must_use = "iterators are lazy and do nothing unless consumed"]
307 #[derive(Clone, Debug)]
308 pub struct Cloned<I> {
312 pub(super) fn new(it: I) -> Cloned<I> {
317 fn clone_try_fold<T: Clone, Acc, R>(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R {
318 move |acc, elt| f(acc, elt.clone())
321 #[stable(feature = "iter_cloned", since = "1.1.0")]
322 impl<'a, I, T: 'a> Iterator for Cloned<I>
324 I: Iterator<Item = &'a T>,
329 fn next(&mut self) -> Option<T> {
330 self.it.next().cloned()
333 fn size_hint(&self) -> (usize, Option<usize>) {
337 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
340 F: FnMut(B, Self::Item) -> R,
343 self.it.try_fold(init, clone_try_fold(f))
346 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
348 F: FnMut(Acc, Self::Item) -> Acc,
350 self.it.map(T::clone).fold(init, f)
353 unsafe fn get_unchecked(&mut self, idx: usize) -> T
355 Self: TrustedRandomAccess,
357 // SAFETY: the caller must uphold the contract for
358 // `Iterator::get_unchecked`.
359 unsafe { try_get_unchecked(&mut self.it, idx).clone() }
363 #[stable(feature = "iter_cloned", since = "1.1.0")]
364 impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
366 I: DoubleEndedIterator<Item = &'a T>,
369 fn next_back(&mut self) -> Option<T> {
370 self.it.next_back().cloned()
373 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
376 F: FnMut(B, Self::Item) -> R,
379 self.it.try_rfold(init, clone_try_fold(f))
382 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
384 F: FnMut(Acc, Self::Item) -> Acc,
386 self.it.map(T::clone).rfold(init, f)
390 #[stable(feature = "iter_cloned", since = "1.1.0")]
391 impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
393 I: ExactSizeIterator<Item = &'a T>,
396 fn len(&self) -> usize {
400 fn is_empty(&self) -> bool {
405 #[stable(feature = "fused", since = "1.26.0")]
406 impl<'a, I, T: 'a> FusedIterator for Cloned<I>
408 I: FusedIterator<Item = &'a T>,
414 #[unstable(feature = "trusted_random_access", issue = "none")]
415 unsafe impl<I> TrustedRandomAccess for Cloned<I>
417 I: TrustedRandomAccess,
420 fn may_have_side_effect() -> bool {
425 #[unstable(feature = "trusted_len", issue = "37572")]
426 unsafe impl<'a, I, T: 'a> TrustedLen for Cloned<I>
428 I: TrustedLen<Item = &'a T>,
433 /// An iterator that repeats endlessly.
435 /// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its
436 /// documentation for more.
438 /// [`cycle`]: trait.Iterator.html#method.cycle
439 /// [`Iterator`]: trait.Iterator.html
440 #[derive(Clone, Debug)]
441 #[must_use = "iterators are lazy and do nothing unless consumed"]
442 #[stable(feature = "rust1", since = "1.0.0")]
443 pub struct Cycle<I> {
447 impl<I: Clone> Cycle<I> {
448 pub(super) fn new(iter: I) -> Cycle<I> {
449 Cycle { orig: iter.clone(), iter }
453 #[stable(feature = "rust1", since = "1.0.0")]
454 impl<I> Iterator for Cycle<I>
458 type Item = <I as Iterator>::Item;
461 fn next(&mut self) -> Option<<I as Iterator>::Item> {
462 match self.iter.next() {
464 self.iter = self.orig.clone();
472 fn size_hint(&self) -> (usize, Option<usize>) {
473 // the cycle iterator is either empty or infinite
474 match self.orig.size_hint() {
475 sz @ (0, Some(0)) => sz,
477 _ => (usize::MAX, None),
482 fn try_fold<Acc, F, R>(&mut self, mut acc: Acc, mut f: F) -> R
484 F: FnMut(Acc, Self::Item) -> R,
487 // fully iterate the current iterator. this is necessary because
488 // `self.iter` may be empty even when `self.orig` isn't
489 acc = self.iter.try_fold(acc, &mut f)?;
490 self.iter = self.orig.clone();
492 // complete a full cycle, keeping track of whether the cycled
493 // iterator is empty or not. we need to return early in case
494 // of an empty iterator to prevent an infinite loop
495 let mut is_empty = true;
496 acc = self.iter.try_fold(acc, |acc, x| {
502 return Try::from_ok(acc);
506 self.iter = self.orig.clone();
507 acc = self.iter.try_fold(acc, &mut f)?;
511 // No `fold` override, because `fold` doesn't make much sense for `Cycle`,
512 // and we can't do anything better than the default.
515 #[stable(feature = "fused", since = "1.26.0")]
516 impl<I> FusedIterator for Cycle<I> where I: Clone + Iterator {}
518 /// An iterator for stepping iterators by a custom amount.
520 /// This `struct` is created by the [`step_by`] method on [`Iterator`]. See
521 /// its documentation for more.
523 /// [`step_by`]: trait.Iterator.html#method.step_by
524 /// [`Iterator`]: trait.Iterator.html
525 #[must_use = "iterators are lazy and do nothing unless consumed"]
526 #[stable(feature = "iterator_step_by", since = "1.28.0")]
527 #[derive(Clone, Debug)]
528 pub struct StepBy<I> {
534 pub(super) fn new(iter: I, step: usize) -> StepBy<I> {
536 StepBy { iter, step: step - 1, first_take: true }
540 #[stable(feature = "iterator_step_by", since = "1.28.0")]
541 impl<I> Iterator for StepBy<I>
548 fn next(&mut self) -> Option<Self::Item> {
550 self.first_take = false;
553 self.iter.nth(self.step)
558 fn size_hint(&self) -> (usize, Option<usize>) {
560 fn first_size(step: usize) -> impl Fn(usize) -> usize {
561 move |n| if n == 0 { 0 } else { 1 + (n - 1) / (step + 1) }
565 fn other_size(step: usize) -> impl Fn(usize) -> usize {
566 move |n| n / (step + 1)
569 let (low, high) = self.iter.size_hint();
572 let f = first_size(self.step);
573 (f(low), high.map(f))
575 let f = other_size(self.step);
576 (f(low), high.map(f))
581 fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
583 self.first_take = false;
584 let first = self.iter.next();
590 // n and self.step are indices, we need to add 1 to get the amount of elements
591 // When calling `.nth`, we need to subtract 1 again to convert back to an index
592 // step + 1 can't overflow because `.step_by` sets `self.step` to `step - 1`
593 let mut step = self.step + 1;
594 // n + 1 could overflow
595 // thus, if n is usize::MAX, instead of adding one, we call .nth(step)
597 self.iter.nth(step - 1);
604 let mul = n.checked_mul(step);
606 if intrinsics::likely(mul.is_some()) {
607 return self.iter.nth(mul.unwrap() - 1);
610 let div_n = usize::MAX / n;
611 let div_step = usize::MAX / step;
612 let nth_n = div_n * n;
613 let nth_step = div_step * step;
614 let nth = if nth_n > nth_step {
621 self.iter.nth(nth - 1);
625 fn try_fold<Acc, F, R>(&mut self, mut acc: Acc, mut f: F) -> R
627 F: FnMut(Acc, Self::Item) -> R,
631 fn nth<I: Iterator>(iter: &mut I, step: usize) -> impl FnMut() -> Option<I::Item> + '_ {
632 move || iter.nth(step)
636 self.first_take = false;
637 match self.iter.next() {
638 None => return Try::from_ok(acc),
639 Some(x) => acc = f(acc, x)?,
642 from_fn(nth(&mut self.iter, self.step)).try_fold(acc, f)
645 fn fold<Acc, F>(mut self, mut acc: Acc, mut f: F) -> Acc
647 F: FnMut(Acc, Self::Item) -> Acc,
650 fn nth<I: Iterator>(iter: &mut I, step: usize) -> impl FnMut() -> Option<I::Item> + '_ {
651 move || iter.nth(step)
655 self.first_take = false;
656 match self.iter.next() {
658 Some(x) => acc = f(acc, x),
661 from_fn(nth(&mut self.iter, self.step)).fold(acc, f)
667 I: ExactSizeIterator,
669 // The zero-based index starting from the end of the iterator of the
670 // last element. Used in the `DoubleEndedIterator` implementation.
671 fn next_back_index(&self) -> usize {
672 let rem = self.iter.len() % (self.step + 1);
674 if rem == 0 { self.step } else { rem - 1 }
681 #[stable(feature = "double_ended_step_by_iterator", since = "1.38.0")]
682 impl<I> DoubleEndedIterator for StepBy<I>
684 I: DoubleEndedIterator + ExactSizeIterator,
687 fn next_back(&mut self) -> Option<Self::Item> {
688 self.iter.nth_back(self.next_back_index())
692 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
693 // `self.iter.nth_back(usize::MAX)` does the right thing here when `n`
694 // is out of bounds because the length of `self.iter` does not exceed
695 // `usize::MAX` (because `I: ExactSizeIterator`) and `nth_back` is
697 let n = n.saturating_mul(self.step + 1).saturating_add(self.next_back_index());
698 self.iter.nth_back(n)
701 fn try_rfold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R
703 F: FnMut(Acc, Self::Item) -> R,
707 fn nth_back<I: DoubleEndedIterator>(
710 ) -> impl FnMut() -> Option<I::Item> + '_ {
711 move || iter.nth_back(step)
714 match self.next_back() {
715 None => Try::from_ok(init),
717 let acc = f(init, x)?;
718 from_fn(nth_back(&mut self.iter, self.step)).try_fold(acc, f)
724 fn rfold<Acc, F>(mut self, init: Acc, mut f: F) -> Acc
727 F: FnMut(Acc, Self::Item) -> Acc,
730 fn nth_back<I: DoubleEndedIterator>(
733 ) -> impl FnMut() -> Option<I::Item> + '_ {
734 move || iter.nth_back(step)
737 match self.next_back() {
740 let acc = f(init, x);
741 from_fn(nth_back(&mut self.iter, self.step)).fold(acc, f)
747 // StepBy can only make the iterator shorter, so the len will still fit.
748 #[stable(feature = "iterator_step_by", since = "1.28.0")]
749 impl<I> ExactSizeIterator for StepBy<I> where I: ExactSizeIterator {}
751 /// An iterator that maps the values of `iter` with `f`.
753 /// This `struct` is created by the [`map`] method on [`Iterator`]. See its
754 /// documentation for more.
756 /// [`map`]: trait.Iterator.html#method.map
757 /// [`Iterator`]: trait.Iterator.html
759 /// # Notes about side effects
761 /// The [`map`] iterator implements [`DoubleEndedIterator`], meaning that
762 /// you can also [`map`] backwards:
765 /// let v: Vec<i32> = vec![1, 2, 3].into_iter().map(|x| x + 1).rev().collect();
767 /// assert_eq!(v, [4, 3, 2]);
770 /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
772 /// But if your closure has state, iterating backwards may act in a way you do
773 /// not expect. Let's go through an example. First, in the forward direction:
778 /// for pair in vec!['a', 'b', 'c'].into_iter()
779 /// .map(|letter| { c += 1; (letter, c) }) {
780 /// println!("{:?}", pair);
784 /// This will print "('a', 1), ('b', 2), ('c', 3)".
786 /// Now consider this twist where we add a call to `rev`. This version will
787 /// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed,
788 /// but the values of the counter still go in order. This is because `map()` is
789 /// still being called lazily on each item, but we are popping items off the
790 /// back of the vector now, instead of shifting them from the front.
795 /// for pair in vec!['a', 'b', 'c'].into_iter()
796 /// .map(|letter| { c += 1; (letter, c) })
798 /// println!("{:?}", pair);
801 #[must_use = "iterators are lazy and do nothing unless consumed"]
802 #[stable(feature = "rust1", since = "1.0.0")]
804 pub struct Map<I, F> {
808 impl<I, F> Map<I, F> {
809 pub(super) fn new(iter: I, f: F) -> Map<I, F> {
814 #[stable(feature = "core_impl_debug", since = "1.9.0")]
815 impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> {
816 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
817 f.debug_struct("Map").field("iter", &self.iter).finish()
821 fn map_fold<T, B, Acc>(
822 mut f: impl FnMut(T) -> B,
823 mut g: impl FnMut(Acc, B) -> Acc,
824 ) -> impl FnMut(Acc, T) -> Acc {
825 move |acc, elt| g(acc, f(elt))
828 fn map_try_fold<'a, T, B, Acc, R>(
829 f: &'a mut impl FnMut(T) -> B,
830 mut g: impl FnMut(Acc, B) -> R + 'a,
831 ) -> impl FnMut(Acc, T) -> R + 'a {
832 move |acc, elt| g(acc, f(elt))
835 #[stable(feature = "rust1", since = "1.0.0")]
836 impl<B, I: Iterator, F> Iterator for Map<I, F>
838 F: FnMut(I::Item) -> B,
843 fn next(&mut self) -> Option<B> {
844 self.iter.next().map(&mut self.f)
848 fn size_hint(&self) -> (usize, Option<usize>) {
849 self.iter.size_hint()
852 fn try_fold<Acc, G, R>(&mut self, init: Acc, g: G) -> R
855 G: FnMut(Acc, Self::Item) -> R,
858 self.iter.try_fold(init, map_try_fold(&mut self.f, g))
861 fn fold<Acc, G>(self, init: Acc, g: G) -> Acc
863 G: FnMut(Acc, Self::Item) -> Acc,
865 self.iter.fold(init, map_fold(self.f, g))
868 unsafe fn get_unchecked(&mut self, idx: usize) -> B
870 Self: TrustedRandomAccess,
872 // SAFETY: the caller must uphold the contract for
873 // `Iterator::get_unchecked`.
874 unsafe { (self.f)(try_get_unchecked(&mut self.iter, idx)) }
878 #[stable(feature = "rust1", since = "1.0.0")]
879 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F>
881 F: FnMut(I::Item) -> B,
884 fn next_back(&mut self) -> Option<B> {
885 self.iter.next_back().map(&mut self.f)
888 fn try_rfold<Acc, G, R>(&mut self, init: Acc, g: G) -> R
891 G: FnMut(Acc, Self::Item) -> R,
894 self.iter.try_rfold(init, map_try_fold(&mut self.f, g))
897 fn rfold<Acc, G>(self, init: Acc, g: G) -> Acc
899 G: FnMut(Acc, Self::Item) -> Acc,
901 self.iter.rfold(init, map_fold(self.f, g))
905 #[stable(feature = "rust1", since = "1.0.0")]
906 impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F>
908 F: FnMut(I::Item) -> B,
910 fn len(&self) -> usize {
914 fn is_empty(&self) -> bool {
919 #[stable(feature = "fused", since = "1.26.0")]
920 impl<B, I: FusedIterator, F> FusedIterator for Map<I, F> where F: FnMut(I::Item) -> B {}
922 #[unstable(feature = "trusted_len", issue = "37572")]
923 unsafe impl<B, I, F> TrustedLen for Map<I, F>
926 F: FnMut(I::Item) -> B,
931 #[unstable(feature = "trusted_random_access", issue = "none")]
932 unsafe impl<I, F> TrustedRandomAccess for Map<I, F>
934 I: TrustedRandomAccess,
937 fn may_have_side_effect() -> bool {
942 /// An iterator that filters the elements of `iter` with `predicate`.
944 /// This `struct` is created by the [`filter`] method on [`Iterator`]. See its
945 /// documentation for more.
947 /// [`filter`]: trait.Iterator.html#method.filter
948 /// [`Iterator`]: trait.Iterator.html
949 #[must_use = "iterators are lazy and do nothing unless consumed"]
950 #[stable(feature = "rust1", since = "1.0.0")]
952 pub struct Filter<I, P> {
956 impl<I, P> Filter<I, P> {
957 pub(super) fn new(iter: I, predicate: P) -> Filter<I, P> {
958 Filter { iter, predicate }
962 #[stable(feature = "core_impl_debug", since = "1.9.0")]
963 impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
964 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
965 f.debug_struct("Filter").field("iter", &self.iter).finish()
969 fn filter_fold<T, Acc>(
970 mut predicate: impl FnMut(&T) -> bool,
971 mut fold: impl FnMut(Acc, T) -> Acc,
972 ) -> impl FnMut(Acc, T) -> Acc {
973 move |acc, item| if predicate(&item) { fold(acc, item) } else { acc }
976 fn filter_try_fold<'a, T, Acc, R: Try<Ok = Acc>>(
977 predicate: &'a mut impl FnMut(&T) -> bool,
978 mut fold: impl FnMut(Acc, T) -> R + 'a,
979 ) -> impl FnMut(Acc, T) -> R + 'a {
980 move |acc, item| if predicate(&item) { fold(acc, item) } else { R::from_ok(acc) }
983 #[stable(feature = "rust1", since = "1.0.0")]
984 impl<I: Iterator, P> Iterator for Filter<I, P>
986 P: FnMut(&I::Item) -> bool,
991 fn next(&mut self) -> Option<I::Item> {
992 self.iter.find(&mut self.predicate)
996 fn size_hint(&self) -> (usize, Option<usize>) {
997 let (_, upper) = self.iter.size_hint();
998 (0, upper) // can't know a lower bound, due to the predicate
1001 // this special case allows the compiler to make `.filter(_).count()`
1002 // branchless. Barring perfect branch prediction (which is unattainable in
1003 // the general case), this will be much faster in >90% of cases (containing
1004 // virtually all real workloads) and only a tiny bit slower in the rest.
1006 // Having this specialization thus allows us to write `.filter(p).count()`
1007 // where we would otherwise write `.map(|x| p(x) as usize).sum()`, which is
1008 // less readable and also less backwards-compatible to Rust before 1.10.
1010 // Using the branchless version will also simplify the LLVM byte code, thus
1011 // leaving more budget for LLVM optimizations.
1013 fn count(self) -> usize {
1015 fn to_usize<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut(T) -> usize {
1016 move |x| predicate(&x) as usize
1019 self.iter.map(to_usize(self.predicate)).sum()
1023 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1026 Fold: FnMut(Acc, Self::Item) -> R,
1029 self.iter.try_fold(init, filter_try_fold(&mut self.predicate, fold))
1033 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1035 Fold: FnMut(Acc, Self::Item) -> Acc,
1037 self.iter.fold(init, filter_fold(self.predicate, fold))
1041 #[stable(feature = "rust1", since = "1.0.0")]
1042 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
1044 P: FnMut(&I::Item) -> bool,
1047 fn next_back(&mut self) -> Option<I::Item> {
1048 self.iter.rfind(&mut self.predicate)
1052 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1055 Fold: FnMut(Acc, Self::Item) -> R,
1058 self.iter.try_rfold(init, filter_try_fold(&mut self.predicate, fold))
1062 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1064 Fold: FnMut(Acc, Self::Item) -> Acc,
1066 self.iter.rfold(init, filter_fold(self.predicate, fold))
1070 #[stable(feature = "fused", since = "1.26.0")]
1071 impl<I: FusedIterator, P> FusedIterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {}
1073 /// An iterator that uses `f` to both filter and map elements from `iter`.
1075 /// This `struct` is created by the [`filter_map`] method on [`Iterator`]. See its
1076 /// documentation for more.
1078 /// [`filter_map`]: trait.Iterator.html#method.filter_map
1079 /// [`Iterator`]: trait.Iterator.html
1080 #[must_use = "iterators are lazy and do nothing unless consumed"]
1081 #[stable(feature = "rust1", since = "1.0.0")]
1083 pub struct FilterMap<I, F> {
1087 impl<I, F> FilterMap<I, F> {
1088 pub(super) fn new(iter: I, f: F) -> FilterMap<I, F> {
1089 FilterMap { iter, f }
1093 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1094 impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> {
1095 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1096 f.debug_struct("FilterMap").field("iter", &self.iter).finish()
1100 fn filter_map_fold<T, B, Acc>(
1101 mut f: impl FnMut(T) -> Option<B>,
1102 mut fold: impl FnMut(Acc, B) -> Acc,
1103 ) -> impl FnMut(Acc, T) -> Acc {
1104 move |acc, item| match f(item) {
1105 Some(x) => fold(acc, x),
1110 fn filter_map_try_fold<'a, T, B, Acc, R: Try<Ok = Acc>>(
1111 f: &'a mut impl FnMut(T) -> Option<B>,
1112 mut fold: impl FnMut(Acc, B) -> R + 'a,
1113 ) -> impl FnMut(Acc, T) -> R + 'a {
1114 move |acc, item| match f(item) {
1115 Some(x) => fold(acc, x),
1116 None => R::from_ok(acc),
1120 #[stable(feature = "rust1", since = "1.0.0")]
1121 impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
1123 F: FnMut(I::Item) -> Option<B>,
1128 fn next(&mut self) -> Option<B> {
1129 self.iter.find_map(&mut self.f)
1133 fn size_hint(&self) -> (usize, Option<usize>) {
1134 let (_, upper) = self.iter.size_hint();
1135 (0, upper) // can't know a lower bound, due to the predicate
1139 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1142 Fold: FnMut(Acc, Self::Item) -> R,
1145 self.iter.try_fold(init, filter_map_try_fold(&mut self.f, fold))
1149 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1151 Fold: FnMut(Acc, Self::Item) -> Acc,
1153 self.iter.fold(init, filter_map_fold(self.f, fold))
1157 #[stable(feature = "rust1", since = "1.0.0")]
1158 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
1160 F: FnMut(I::Item) -> Option<B>,
1163 fn next_back(&mut self) -> Option<B> {
1166 f: &mut impl FnMut(T) -> Option<B>,
1167 ) -> impl FnMut((), T) -> LoopState<(), B> + '_ {
1168 move |(), x| match f(x) {
1169 Some(x) => LoopState::Break(x),
1170 None => LoopState::Continue(()),
1174 self.iter.try_rfold((), find(&mut self.f)).break_value()
1178 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1181 Fold: FnMut(Acc, Self::Item) -> R,
1184 self.iter.try_rfold(init, filter_map_try_fold(&mut self.f, fold))
1188 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1190 Fold: FnMut(Acc, Self::Item) -> Acc,
1192 self.iter.rfold(init, filter_map_fold(self.f, fold))
1196 #[stable(feature = "fused", since = "1.26.0")]
1197 impl<B, I: FusedIterator, F> FusedIterator for FilterMap<I, F> where F: FnMut(I::Item) -> Option<B> {}
1199 /// An iterator that yields the current count and the element during iteration.
1201 /// This `struct` is created by the [`enumerate`] method on [`Iterator`]. See its
1202 /// documentation for more.
1204 /// [`enumerate`]: trait.Iterator.html#method.enumerate
1205 /// [`Iterator`]: trait.Iterator.html
1206 #[derive(Clone, Debug)]
1207 #[must_use = "iterators are lazy and do nothing unless consumed"]
1208 #[stable(feature = "rust1", since = "1.0.0")]
1209 pub struct Enumerate<I> {
1213 impl<I> Enumerate<I> {
1214 pub(super) fn new(iter: I) -> Enumerate<I> {
1215 Enumerate { iter, count: 0 }
1219 #[stable(feature = "rust1", since = "1.0.0")]
1220 impl<I> Iterator for Enumerate<I>
1224 type Item = (usize, <I as Iterator>::Item);
1226 /// # Overflow Behavior
1228 /// The method does no guarding against overflows, so enumerating more than
1229 /// `usize::MAX` elements either produces the wrong result or panics. If
1230 /// debug assertions are enabled, a panic is guaranteed.
1234 /// Might panic if the index of the element overflows a `usize`.
1236 fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1237 let a = self.iter.next()?;
1239 // Possible undefined overflow.
1240 AddAssign::add_assign(&mut self.count, 1);
1245 fn size_hint(&self) -> (usize, Option<usize>) {
1246 self.iter.size_hint()
1250 fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
1251 let a = self.iter.nth(n)?;
1252 // Possible undefined overflow.
1253 let i = Add::add(self.count, n);
1254 self.count = Add::add(i, 1);
1259 fn count(self) -> usize {
1264 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1267 Fold: FnMut(Acc, Self::Item) -> R,
1271 fn enumerate<'a, T, Acc, R>(
1272 count: &'a mut usize,
1273 mut fold: impl FnMut(Acc, (usize, T)) -> R + 'a,
1274 ) -> impl FnMut(Acc, T) -> R + 'a {
1276 let acc = fold(acc, (*count, item));
1277 // Possible undefined overflow.
1278 AddAssign::add_assign(count, 1);
1283 self.iter.try_fold(init, enumerate(&mut self.count, fold))
1287 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1289 Fold: FnMut(Acc, Self::Item) -> Acc,
1292 fn enumerate<T, Acc>(
1294 mut fold: impl FnMut(Acc, (usize, T)) -> Acc,
1295 ) -> impl FnMut(Acc, T) -> Acc {
1297 let acc = fold(acc, (count, item));
1298 // Possible undefined overflow.
1299 AddAssign::add_assign(&mut count, 1);
1304 self.iter.fold(init, enumerate(self.count, fold))
1307 unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item
1309 Self: TrustedRandomAccess,
1311 // SAFETY: the caller must uphold the contract for
1312 // `Iterator::get_unchecked`.
1313 let value = unsafe { try_get_unchecked(&mut self.iter, idx) };
1314 (Add::add(self.count, idx), value)
1318 #[stable(feature = "rust1", since = "1.0.0")]
1319 impl<I> DoubleEndedIterator for Enumerate<I>
1321 I: ExactSizeIterator + DoubleEndedIterator,
1324 fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1325 let a = self.iter.next_back()?;
1326 let len = self.iter.len();
1327 // Can safely add, `ExactSizeIterator` promises that the number of
1328 // elements fits into a `usize`.
1329 Some((self.count + len, a))
1333 fn nth_back(&mut self, n: usize) -> Option<(usize, <I as Iterator>::Item)> {
1334 let a = self.iter.nth_back(n)?;
1335 let len = self.iter.len();
1336 // Can safely add, `ExactSizeIterator` promises that the number of
1337 // elements fits into a `usize`.
1338 Some((self.count + len, a))
1342 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1345 Fold: FnMut(Acc, Self::Item) -> R,
1348 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1349 // that the number of elements fits into a `usize`.
1350 fn enumerate<T, Acc, R>(
1352 mut fold: impl FnMut(Acc, (usize, T)) -> R,
1353 ) -> impl FnMut(Acc, T) -> R {
1356 fold(acc, (count, item))
1360 let count = self.count + self.iter.len();
1361 self.iter.try_rfold(init, enumerate(count, fold))
1365 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1367 Fold: FnMut(Acc, Self::Item) -> Acc,
1369 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1370 // that the number of elements fits into a `usize`.
1371 fn enumerate<T, Acc>(
1373 mut fold: impl FnMut(Acc, (usize, T)) -> Acc,
1374 ) -> impl FnMut(Acc, T) -> Acc {
1377 fold(acc, (count, item))
1381 let count = self.count + self.iter.len();
1382 self.iter.rfold(init, enumerate(count, fold))
1386 #[stable(feature = "rust1", since = "1.0.0")]
1387 impl<I> ExactSizeIterator for Enumerate<I>
1389 I: ExactSizeIterator,
1391 fn len(&self) -> usize {
1395 fn is_empty(&self) -> bool {
1396 self.iter.is_empty()
1401 #[unstable(feature = "trusted_random_access", issue = "none")]
1402 unsafe impl<I> TrustedRandomAccess for Enumerate<I>
1404 I: TrustedRandomAccess,
1406 fn may_have_side_effect() -> bool {
1407 I::may_have_side_effect()
1411 #[stable(feature = "fused", since = "1.26.0")]
1412 impl<I> FusedIterator for Enumerate<I> where I: FusedIterator {}
1414 #[unstable(feature = "trusted_len", issue = "37572")]
1415 unsafe impl<I> TrustedLen for Enumerate<I> where I: TrustedLen {}
1417 /// An iterator with a `peek()` that returns an optional reference to the next
1420 /// This `struct` is created by the [`peekable`] method on [`Iterator`]. See its
1421 /// documentation for more.
1423 /// [`peekable`]: trait.Iterator.html#method.peekable
1424 /// [`Iterator`]: trait.Iterator.html
1425 #[derive(Clone, Debug)]
1426 #[must_use = "iterators are lazy and do nothing unless consumed"]
1427 #[stable(feature = "rust1", since = "1.0.0")]
1428 pub struct Peekable<I: Iterator> {
1430 /// Remember a peeked value, even if it was None.
1431 peeked: Option<Option<I::Item>>,
1433 impl<I: Iterator> Peekable<I> {
1434 pub(super) fn new(iter: I) -> Peekable<I> {
1435 Peekable { iter, peeked: None }
1439 // Peekable must remember if a None has been seen in the `.peek()` method.
1440 // It ensures that `.peek(); .peek();` or `.peek(); .next();` only advances the
1441 // underlying iterator at most once. This does not by itself make the iterator
1443 #[stable(feature = "rust1", since = "1.0.0")]
1444 impl<I: Iterator> Iterator for Peekable<I> {
1445 type Item = I::Item;
1448 fn next(&mut self) -> Option<I::Item> {
1449 match self.peeked.take() {
1451 None => self.iter.next(),
1456 #[rustc_inherit_overflow_checks]
1457 fn count(mut self) -> usize {
1458 match self.peeked.take() {
1460 Some(Some(_)) => 1 + self.iter.count(),
1461 None => self.iter.count(),
1466 fn nth(&mut self, n: usize) -> Option<I::Item> {
1467 match self.peeked.take() {
1469 Some(v @ Some(_)) if n == 0 => v,
1470 Some(Some(_)) => self.iter.nth(n - 1),
1471 None => self.iter.nth(n),
1476 fn last(mut self) -> Option<I::Item> {
1477 let peek_opt = match self.peeked.take() {
1478 Some(None) => return None,
1482 self.iter.last().or(peek_opt)
1486 fn size_hint(&self) -> (usize, Option<usize>) {
1487 let peek_len = match self.peeked {
1488 Some(None) => return (0, Some(0)),
1492 let (lo, hi) = self.iter.size_hint();
1493 let lo = lo.saturating_add(peek_len);
1495 Some(x) => x.checked_add(peek_len),
1502 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
1505 F: FnMut(B, Self::Item) -> R,
1508 let acc = match self.peeked.take() {
1509 Some(None) => return Try::from_ok(init),
1510 Some(Some(v)) => f(init, v)?,
1513 self.iter.try_fold(acc, f)
1517 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1519 Fold: FnMut(Acc, Self::Item) -> Acc,
1521 let acc = match self.peeked {
1522 Some(None) => return init,
1523 Some(Some(v)) => fold(init, v),
1526 self.iter.fold(acc, fold)
1530 #[stable(feature = "double_ended_peek_iterator", since = "1.38.0")]
1531 impl<I> DoubleEndedIterator for Peekable<I>
1533 I: DoubleEndedIterator,
1536 fn next_back(&mut self) -> Option<Self::Item> {
1537 match self.peeked.as_mut() {
1538 Some(v @ Some(_)) => self.iter.next_back().or_else(|| v.take()),
1540 None => self.iter.next_back(),
1545 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
1548 F: FnMut(B, Self::Item) -> R,
1551 match self.peeked.take() {
1552 Some(None) => Try::from_ok(init),
1553 Some(Some(v)) => match self.iter.try_rfold(init, &mut f).into_result() {
1554 Ok(acc) => f(acc, v),
1556 self.peeked = Some(Some(v));
1560 None => self.iter.try_rfold(init, f),
1565 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1567 Fold: FnMut(Acc, Self::Item) -> Acc,
1572 let acc = self.iter.rfold(init, &mut fold);
1575 None => self.iter.rfold(init, fold),
1580 #[stable(feature = "rust1", since = "1.0.0")]
1581 impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
1583 #[stable(feature = "fused", since = "1.26.0")]
1584 impl<I: FusedIterator> FusedIterator for Peekable<I> {}
1586 impl<I: Iterator> Peekable<I> {
1587 /// Returns a reference to the next() value without advancing the iterator.
1589 /// Like [`next`], if there is a value, it is wrapped in a `Some(T)`.
1590 /// But if the iteration is over, `None` is returned.
1592 /// [`next`]: trait.Iterator.html#tymethod.next
1594 /// Because `peek()` returns a reference, and many iterators iterate over
1595 /// references, there can be a possibly confusing situation where the
1596 /// return value is a double reference. You can see this effect in the
1604 /// let xs = [1, 2, 3];
1606 /// let mut iter = xs.iter().peekable();
1608 /// // peek() lets us see into the future
1609 /// assert_eq!(iter.peek(), Some(&&1));
1610 /// assert_eq!(iter.next(), Some(&1));
1612 /// assert_eq!(iter.next(), Some(&2));
1614 /// // The iterator does not advance even if we `peek` multiple times
1615 /// assert_eq!(iter.peek(), Some(&&3));
1616 /// assert_eq!(iter.peek(), Some(&&3));
1618 /// assert_eq!(iter.next(), Some(&3));
1620 /// // After the iterator is finished, so is `peek()`
1621 /// assert_eq!(iter.peek(), None);
1622 /// assert_eq!(iter.next(), None);
1625 #[stable(feature = "rust1", since = "1.0.0")]
1626 pub fn peek(&mut self) -> Option<&I::Item> {
1627 let iter = &mut self.iter;
1628 self.peeked.get_or_insert_with(|| iter.next()).as_ref()
1631 /// Consume the next value of this iterator if a condition is true.
1633 /// If `func` returns `true` for the next value of this iterator, consume and return it.
1634 /// Otherwise, return `None`.
1637 /// Consume a number if it's equal to 0.
1639 /// #![feature(peekable_next_if)]
1640 /// let mut iter = (0..5).peekable();
1641 /// // The first item of the iterator is 0; consume it.
1642 /// assert_eq!(iter.next_if(|&x| x == 0), Some(0));
1643 /// // The next item returned is now 1, so `consume` will return `false`.
1644 /// assert_eq!(iter.next_if(|&x| x == 0), None);
1645 /// // `next_if` saves the value of the next item if it was not equal to `expected`.
1646 /// assert_eq!(iter.next(), Some(1));
1649 /// Consume any number less than 10.
1651 /// #![feature(peekable_next_if)]
1652 /// let mut iter = (1..20).peekable();
1653 /// // Consume all numbers less than 10
1654 /// while iter.next_if(|&x| x < 10).is_some() {}
1655 /// // The next value returned will be 10
1656 /// assert_eq!(iter.next(), Some(10));
1658 #[unstable(feature = "peekable_next_if", issue = "72480")]
1659 pub fn next_if(&mut self, func: impl FnOnce(&I::Item) -> bool) -> Option<I::Item> {
1661 Some(matched) if func(&matched) => Some(matched),
1663 // Since we called `self.next()`, we consumed `self.peeked`.
1664 assert!(self.peeked.is_none());
1665 self.peeked = Some(other);
1671 /// Consume the next item if it is equal to `expected`.
1674 /// Consume a number if it's equal to 0.
1676 /// #![feature(peekable_next_if)]
1677 /// let mut iter = (0..5).peekable();
1678 /// // The first item of the iterator is 0; consume it.
1679 /// assert_eq!(iter.next_if_eq(&0), Some(0));
1680 /// // The next item returned is now 1, so `consume` will return `false`.
1681 /// assert_eq!(iter.next_if_eq(&0), None);
1682 /// // `next_if_eq` saves the value of the next item if it was not equal to `expected`.
1683 /// assert_eq!(iter.next(), Some(1));
1685 #[unstable(feature = "peekable_next_if", issue = "72480")]
1686 pub fn next_if_eq<R>(&mut self, expected: &R) -> Option<I::Item>
1689 I::Item: PartialEq<R>,
1691 self.next_if(|next| next == expected)
1695 /// An iterator that rejects elements while `predicate` returns `true`.
1697 /// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its
1698 /// documentation for more.
1700 /// [`skip_while`]: trait.Iterator.html#method.skip_while
1701 /// [`Iterator`]: trait.Iterator.html
1702 #[must_use = "iterators are lazy and do nothing unless consumed"]
1703 #[stable(feature = "rust1", since = "1.0.0")]
1705 pub struct SkipWhile<I, P> {
1710 impl<I, P> SkipWhile<I, P> {
1711 pub(super) fn new(iter: I, predicate: P) -> SkipWhile<I, P> {
1712 SkipWhile { iter, flag: false, predicate }
1716 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1717 impl<I: fmt::Debug, P> fmt::Debug for SkipWhile<I, P> {
1718 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1719 f.debug_struct("SkipWhile").field("iter", &self.iter).field("flag", &self.flag).finish()
1723 #[stable(feature = "rust1", since = "1.0.0")]
1724 impl<I: Iterator, P> Iterator for SkipWhile<I, P>
1726 P: FnMut(&I::Item) -> bool,
1728 type Item = I::Item;
1731 fn next(&mut self) -> Option<I::Item> {
1734 pred: &'a mut impl FnMut(&T) -> bool,
1735 ) -> impl FnMut(&T) -> bool + 'a {
1737 if *flag || !pred(x) {
1746 let flag = &mut self.flag;
1747 let pred = &mut self.predicate;
1748 self.iter.find(check(flag, pred))
1752 fn size_hint(&self) -> (usize, Option<usize>) {
1753 let (_, upper) = self.iter.size_hint();
1754 (0, upper) // can't know a lower bound, due to the predicate
1758 fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
1761 Fold: FnMut(Acc, Self::Item) -> R,
1766 Some(v) => init = fold(init, v)?,
1767 None => return Try::from_ok(init),
1770 self.iter.try_fold(init, fold)
1774 fn fold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
1776 Fold: FnMut(Acc, Self::Item) -> Acc,
1780 Some(v) => init = fold(init, v),
1781 None => return init,
1784 self.iter.fold(init, fold)
1788 #[stable(feature = "fused", since = "1.26.0")]
1789 impl<I, P> FusedIterator for SkipWhile<I, P>
1792 P: FnMut(&I::Item) -> bool,
1796 /// An iterator that only accepts elements while `predicate` returns `true`.
1798 /// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its
1799 /// documentation for more.
1801 /// [`take_while`]: trait.Iterator.html#method.take_while
1802 /// [`Iterator`]: trait.Iterator.html
1803 #[must_use = "iterators are lazy and do nothing unless consumed"]
1804 #[stable(feature = "rust1", since = "1.0.0")]
1806 pub struct TakeWhile<I, P> {
1811 impl<I, P> TakeWhile<I, P> {
1812 pub(super) fn new(iter: I, predicate: P) -> TakeWhile<I, P> {
1813 TakeWhile { iter, flag: false, predicate }
1817 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1818 impl<I: fmt::Debug, P> fmt::Debug for TakeWhile<I, P> {
1819 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1820 f.debug_struct("TakeWhile").field("iter", &self.iter).field("flag", &self.flag).finish()
1824 #[stable(feature = "rust1", since = "1.0.0")]
1825 impl<I: Iterator, P> Iterator for TakeWhile<I, P>
1827 P: FnMut(&I::Item) -> bool,
1829 type Item = I::Item;
1832 fn next(&mut self) -> Option<I::Item> {
1836 let x = self.iter.next()?;
1837 if (self.predicate)(&x) {
1847 fn size_hint(&self) -> (usize, Option<usize>) {
1851 let (_, upper) = self.iter.size_hint();
1852 (0, upper) // can't know a lower bound, due to the predicate
1857 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1860 Fold: FnMut(Acc, Self::Item) -> R,
1863 fn check<'a, T, Acc, R: Try<Ok = Acc>>(
1865 p: &'a mut impl FnMut(&T) -> bool,
1866 mut fold: impl FnMut(Acc, T) -> R + 'a,
1867 ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> + 'a {
1870 LoopState::from_try(fold(acc, x))
1873 LoopState::Break(Try::from_ok(acc))
1881 let flag = &mut self.flag;
1882 let p = &mut self.predicate;
1883 self.iter.try_fold(init, check(flag, p, fold)).into_try()
1888 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
1891 Fold: FnMut(Acc, Self::Item) -> Acc,
1894 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
1895 move |acc, x| Ok(f(acc, x))
1898 self.try_fold(init, ok(fold)).unwrap()
1902 #[stable(feature = "fused", since = "1.26.0")]
1903 impl<I, P> FusedIterator for TakeWhile<I, P>
1906 P: FnMut(&I::Item) -> bool,
1910 /// An iterator that only accepts elements while `predicate` returns `Some(_)`.
1912 /// This `struct` is created by the [`map_while`] method on [`Iterator`]. See its
1913 /// documentation for more.
1915 /// [`map_while`]: trait.Iterator.html#method.map_while
1916 /// [`Iterator`]: trait.Iterator.html
1917 #[must_use = "iterators are lazy and do nothing unless consumed"]
1918 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
1920 pub struct MapWhile<I, P> {
1925 impl<I, P> MapWhile<I, P> {
1926 pub(super) fn new(iter: I, predicate: P) -> MapWhile<I, P> {
1927 MapWhile { iter, predicate }
1931 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
1932 impl<I: fmt::Debug, P> fmt::Debug for MapWhile<I, P> {
1933 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1934 f.debug_struct("MapWhile").field("iter", &self.iter).finish()
1938 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
1939 impl<B, I: Iterator, P> Iterator for MapWhile<I, P>
1941 P: FnMut(I::Item) -> Option<B>,
1946 fn next(&mut self) -> Option<B> {
1947 let x = self.iter.next()?;
1952 fn size_hint(&self) -> (usize, Option<usize>) {
1953 let (_, upper) = self.iter.size_hint();
1954 (0, upper) // can't know a lower bound, due to the predicate
1958 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R
1961 Fold: FnMut(Acc, Self::Item) -> R,
1964 let Self { iter, predicate } = self;
1965 iter.try_fold(init, |acc, x| match predicate(x) {
1966 Some(item) => LoopState::from_try(fold(acc, item)),
1967 None => LoopState::Break(Try::from_ok(acc)),
1973 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
1976 Fold: FnMut(Acc, Self::Item) -> Acc,
1979 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
1980 move |acc, x| Ok(f(acc, x))
1983 self.try_fold(init, ok(fold)).unwrap()
1987 /// An iterator that skips over `n` elements of `iter`.
1989 /// This `struct` is created by the [`skip`] method on [`Iterator`]. See its
1990 /// documentation for more.
1992 /// [`skip`]: trait.Iterator.html#method.skip
1993 /// [`Iterator`]: trait.Iterator.html
1994 #[derive(Clone, Debug)]
1995 #[must_use = "iterators are lazy and do nothing unless consumed"]
1996 #[stable(feature = "rust1", since = "1.0.0")]
1997 pub struct Skip<I> {
2002 pub(super) fn new(iter: I, n: usize) -> Skip<I> {
2007 #[stable(feature = "rust1", since = "1.0.0")]
2008 impl<I> Iterator for Skip<I>
2012 type Item = <I as Iterator>::Item;
2015 fn next(&mut self) -> Option<I::Item> {
2021 self.iter.nth(old_n)
2026 fn nth(&mut self, n: usize) -> Option<I::Item> {
2027 // Can't just add n + self.n due to overflow.
2029 let to_skip = self.n;
2032 self.iter.nth(to_skip - 1)?;
2038 fn count(mut self) -> usize {
2041 if self.iter.nth(self.n - 1).is_none() {
2049 fn last(mut self) -> Option<I::Item> {
2052 self.iter.nth(self.n - 1)?;
2058 fn size_hint(&self) -> (usize, Option<usize>) {
2059 let (lower, upper) = self.iter.size_hint();
2061 let lower = lower.saturating_sub(self.n);
2062 let upper = match upper {
2063 Some(x) => Some(x.saturating_sub(self.n)),
2071 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2074 Fold: FnMut(Acc, Self::Item) -> R,
2081 if self.iter.nth(n - 1).is_none() {
2082 return Try::from_ok(init);
2085 self.iter.try_fold(init, fold)
2089 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2091 Fold: FnMut(Acc, Self::Item) -> Acc,
2095 if self.iter.nth(self.n - 1).is_none() {
2099 self.iter.fold(init, fold)
2103 #[stable(feature = "rust1", since = "1.0.0")]
2104 impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
2106 #[stable(feature = "double_ended_skip_iterator", since = "1.9.0")]
2107 impl<I> DoubleEndedIterator for Skip<I>
2109 I: DoubleEndedIterator + ExactSizeIterator,
2111 fn next_back(&mut self) -> Option<Self::Item> {
2112 if self.len() > 0 { self.iter.next_back() } else { None }
2116 fn nth_back(&mut self, n: usize) -> Option<I::Item> {
2117 let len = self.len();
2119 self.iter.nth_back(n)
2122 // consume the original iterator
2123 self.iter.nth_back(len - 1);
2129 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2132 Fold: FnMut(Acc, Self::Item) -> R,
2135 fn check<T, Acc, R: Try<Ok = Acc>>(
2137 mut fold: impl FnMut(Acc, T) -> R,
2138 ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> {
2141 let r = fold(acc, x);
2142 if n == 0 { LoopState::Break(r) } else { LoopState::from_try(r) }
2150 self.iter.try_rfold(init, check(n, fold)).into_try()
2154 fn rfold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2156 Fold: FnMut(Acc, Self::Item) -> Acc,
2159 fn ok<Acc, T>(mut f: impl FnMut(Acc, T) -> Acc) -> impl FnMut(Acc, T) -> Result<Acc, !> {
2160 move |acc, x| Ok(f(acc, x))
2163 self.try_rfold(init, ok(fold)).unwrap()
2167 #[stable(feature = "fused", since = "1.26.0")]
2168 impl<I> FusedIterator for Skip<I> where I: FusedIterator {}
2170 /// An iterator that only iterates over the first `n` iterations of `iter`.
2172 /// This `struct` is created by the [`take`] method on [`Iterator`]. See its
2173 /// documentation for more.
2175 /// [`take`]: trait.Iterator.html#method.take
2176 /// [`Iterator`]: trait.Iterator.html
2177 #[derive(Clone, Debug)]
2178 #[must_use = "iterators are lazy and do nothing unless consumed"]
2179 #[stable(feature = "rust1", since = "1.0.0")]
2180 pub struct Take<I> {
2182 pub(super) n: usize,
2185 pub(super) fn new(iter: I, n: usize) -> Take<I> {
2190 #[stable(feature = "rust1", since = "1.0.0")]
2191 impl<I> Iterator for Take<I>
2195 type Item = <I as Iterator>::Item;
2198 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2208 fn nth(&mut self, n: usize) -> Option<I::Item> {
2214 self.iter.nth(self.n - 1);
2222 fn size_hint(&self) -> (usize, Option<usize>) {
2224 return (0, Some(0));
2227 let (lower, upper) = self.iter.size_hint();
2229 let lower = cmp::min(lower, self.n);
2231 let upper = match upper {
2232 Some(x) if x < self.n => Some(x),
2240 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2243 Fold: FnMut(Acc, Self::Item) -> R,
2246 fn check<'a, T, Acc, R: Try<Ok = Acc>>(
2248 mut fold: impl FnMut(Acc, T) -> R + 'a,
2249 ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> + 'a {
2252 let r = fold(acc, x);
2253 if *n == 0 { LoopState::Break(r) } else { LoopState::from_try(r) }
2260 let n = &mut self.n;
2261 self.iter.try_fold(init, check(n, fold)).into_try()
2266 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2269 Fold: FnMut(Acc, Self::Item) -> Acc,
2272 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2273 move |acc, x| Ok(f(acc, x))
2276 self.try_fold(init, ok(fold)).unwrap()
2280 #[stable(feature = "double_ended_take_iterator", since = "1.38.0")]
2281 impl<I> DoubleEndedIterator for Take<I>
2283 I: DoubleEndedIterator + ExactSizeIterator,
2286 fn next_back(&mut self) -> Option<Self::Item> {
2292 self.iter.nth_back(self.iter.len().saturating_sub(n))
2297 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2298 let len = self.iter.len();
2300 let m = len.saturating_sub(self.n) + n;
2302 self.iter.nth_back(m)
2305 self.iter.nth_back(len - 1);
2312 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2315 Fold: FnMut(Acc, Self::Item) -> R,
2321 let len = self.iter.len();
2322 if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() {
2325 self.iter.try_rfold(init, fold)
2331 fn rfold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2334 Fold: FnMut(Acc, Self::Item) -> Acc,
2339 let len = self.iter.len();
2340 if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() {
2343 self.iter.rfold(init, fold)
2349 #[stable(feature = "rust1", since = "1.0.0")]
2350 impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
2352 #[stable(feature = "fused", since = "1.26.0")]
2353 impl<I> FusedIterator for Take<I> where I: FusedIterator {}
2355 #[unstable(feature = "trusted_len", issue = "37572")]
2356 unsafe impl<I: TrustedLen> TrustedLen for Take<I> {}
2358 /// An iterator to maintain state while iterating another iterator.
2360 /// This `struct` is created by the [`scan`] method on [`Iterator`]. See its
2361 /// documentation for more.
2363 /// [`scan`]: trait.Iterator.html#method.scan
2364 /// [`Iterator`]: trait.Iterator.html
2365 #[must_use = "iterators are lazy and do nothing unless consumed"]
2366 #[stable(feature = "rust1", since = "1.0.0")]
2368 pub struct Scan<I, St, F> {
2373 impl<I, St, F> Scan<I, St, F> {
2374 pub(super) fn new(iter: I, state: St, f: F) -> Scan<I, St, F> {
2375 Scan { iter, state, f }
2379 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2380 impl<I: fmt::Debug, St: fmt::Debug, F> fmt::Debug for Scan<I, St, F> {
2381 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2382 f.debug_struct("Scan").field("iter", &self.iter).field("state", &self.state).finish()
2386 #[stable(feature = "rust1", since = "1.0.0")]
2387 impl<B, I, St, F> Iterator for Scan<I, St, F>
2390 F: FnMut(&mut St, I::Item) -> Option<B>,
2395 fn next(&mut self) -> Option<B> {
2396 let a = self.iter.next()?;
2397 (self.f)(&mut self.state, a)
2401 fn size_hint(&self) -> (usize, Option<usize>) {
2402 let (_, upper) = self.iter.size_hint();
2403 (0, upper) // can't know a lower bound, due to the scan function
2407 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2410 Fold: FnMut(Acc, Self::Item) -> R,
2413 fn scan<'a, T, St, B, Acc, R: Try<Ok = Acc>>(
2415 f: &'a mut impl FnMut(&mut St, T) -> Option<B>,
2416 mut fold: impl FnMut(Acc, B) -> R + 'a,
2417 ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> + 'a {
2418 move |acc, x| match f(state, x) {
2419 None => LoopState::Break(Try::from_ok(acc)),
2420 Some(x) => LoopState::from_try(fold(acc, x)),
2424 let state = &mut self.state;
2425 let f = &mut self.f;
2426 self.iter.try_fold(init, scan(state, f, fold)).into_try()
2430 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2433 Fold: FnMut(Acc, Self::Item) -> Acc,
2436 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2437 move |acc, x| Ok(f(acc, x))
2440 self.try_fold(init, ok(fold)).unwrap()
2444 /// An iterator that calls a function with a reference to each element before
2447 /// This `struct` is created by the [`inspect`] method on [`Iterator`]. See its
2448 /// documentation for more.
2450 /// [`inspect`]: trait.Iterator.html#method.inspect
2451 /// [`Iterator`]: trait.Iterator.html
2452 #[must_use = "iterators are lazy and do nothing unless consumed"]
2453 #[stable(feature = "rust1", since = "1.0.0")]
2455 pub struct Inspect<I, F> {
2459 impl<I, F> Inspect<I, F> {
2460 pub(super) fn new(iter: I, f: F) -> Inspect<I, F> {
2465 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2466 impl<I: fmt::Debug, F> fmt::Debug for Inspect<I, F> {
2467 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2468 f.debug_struct("Inspect").field("iter", &self.iter).finish()
2472 impl<I: Iterator, F> Inspect<I, F>
2477 fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
2478 if let Some(ref a) = elt {
2486 fn inspect_fold<T, Acc>(
2487 mut f: impl FnMut(&T),
2488 mut fold: impl FnMut(Acc, T) -> Acc,
2489 ) -> impl FnMut(Acc, T) -> Acc {
2496 fn inspect_try_fold<'a, T, Acc, R>(
2497 f: &'a mut impl FnMut(&T),
2498 mut fold: impl FnMut(Acc, T) -> R + 'a,
2499 ) -> impl FnMut(Acc, T) -> R + 'a {
2506 #[stable(feature = "rust1", since = "1.0.0")]
2507 impl<I: Iterator, F> Iterator for Inspect<I, F>
2511 type Item = I::Item;
2514 fn next(&mut self) -> Option<I::Item> {
2515 let next = self.iter.next();
2516 self.do_inspect(next)
2520 fn size_hint(&self) -> (usize, Option<usize>) {
2521 self.iter.size_hint()
2525 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2528 Fold: FnMut(Acc, Self::Item) -> R,
2531 self.iter.try_fold(init, inspect_try_fold(&mut self.f, fold))
2535 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2537 Fold: FnMut(Acc, Self::Item) -> Acc,
2539 self.iter.fold(init, inspect_fold(self.f, fold))
2543 #[stable(feature = "rust1", since = "1.0.0")]
2544 impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
2549 fn next_back(&mut self) -> Option<I::Item> {
2550 let next = self.iter.next_back();
2551 self.do_inspect(next)
2555 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2558 Fold: FnMut(Acc, Self::Item) -> R,
2561 self.iter.try_rfold(init, inspect_try_fold(&mut self.f, fold))
2565 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2567 Fold: FnMut(Acc, Self::Item) -> Acc,
2569 self.iter.rfold(init, inspect_fold(self.f, fold))
2573 #[stable(feature = "rust1", since = "1.0.0")]
2574 impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F>
2578 fn len(&self) -> usize {
2582 fn is_empty(&self) -> bool {
2583 self.iter.is_empty()
2587 #[stable(feature = "fused", since = "1.26.0")]
2588 impl<I: FusedIterator, F> FusedIterator for Inspect<I, F> where F: FnMut(&I::Item) {}
2590 /// An iterator adapter that produces output as long as the underlying
2591 /// iterator produces `Result::Ok` values.
2593 /// If an error is encountered, the iterator stops and the error is
2595 pub(crate) struct ResultShunt<'a, I, E> {
2597 error: &'a mut Result<(), E>,
2600 /// Process the given iterator as if it yielded a `T` instead of a
2601 /// `Result<T, _>`. Any errors will stop the inner iterator and
2602 /// the overall result will be an error.
2603 pub(crate) fn process_results<I, T, E, F, U>(iter: I, mut f: F) -> Result<U, E>
2605 I: Iterator<Item = Result<T, E>>,
2606 for<'a> F: FnMut(ResultShunt<'a, I, E>) -> U,
2608 let mut error = Ok(());
2609 let shunt = ResultShunt { iter, error: &mut error };
2610 let value = f(shunt);
2611 error.map(|()| value)
2614 impl<I, T, E> Iterator for ResultShunt<'_, I, E>
2616 I: Iterator<Item = Result<T, E>>,
2620 fn next(&mut self) -> Option<Self::Item> {
2624 fn size_hint(&self) -> (usize, Option<usize>) {
2625 if self.error.is_err() {
2628 let (_, upper) = self.iter.size_hint();
2633 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
2635 F: FnMut(B, Self::Item) -> R,
2638 let error = &mut *self.error;
2640 .try_fold(init, |acc, x| match x {
2641 Ok(x) => LoopState::from_try(f(acc, x)),
2644 LoopState::Break(Try::from_ok(acc))
2650 fn fold<B, F>(mut self, init: B, fold: F) -> B
2653 F: FnMut(B, Self::Item) -> B,
2656 fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
2657 move |acc, x| Ok(f(acc, x))
2660 self.try_fold(init, ok(fold)).unwrap()