7 use super::{Iterator, DoubleEndedIterator, ExactSizeIterator, FusedIterator, 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::zip::Zip;
18 pub(crate) use self::zip::TrustedRandomAccess;
20 /// A double-ended iterator with the direction inverted.
22 /// This `struct` is created by the [`rev`] method on [`Iterator`]. See its
23 /// documentation for more.
25 /// [`rev`]: trait.Iterator.html#method.rev
26 /// [`Iterator`]: trait.Iterator.html
27 #[derive(Clone, Debug)]
28 #[must_use = "iterators are lazy and do nothing unless consumed"]
29 #[stable(feature = "rust1", since = "1.0.0")]
34 pub(super) fn new(iter: T) -> Rev<T> {
39 #[stable(feature = "rust1", since = "1.0.0")]
40 impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
41 type Item = <I as Iterator>::Item;
44 fn next(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next_back() }
46 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
49 fn nth(&mut self, n: usize) -> Option<<I as Iterator>::Item> { self.iter.nth_back(n) }
51 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R where
52 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
54 self.iter.try_rfold(init, f)
57 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
58 where F: FnMut(Acc, Self::Item) -> Acc,
60 self.iter.rfold(init, f)
64 fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
65 where P: FnMut(&Self::Item) -> bool
67 self.iter.rfind(predicate)
71 fn rposition<P>(&mut self, predicate: P) -> Option<usize> where
72 P: FnMut(Self::Item) -> bool
74 self.iter.position(predicate)
78 #[stable(feature = "rust1", since = "1.0.0")]
79 impl<I> DoubleEndedIterator for Rev<I> where I: DoubleEndedIterator {
81 fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next() }
84 fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> { self.iter.nth(n) }
86 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R where
87 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
89 self.iter.try_fold(init, f)
92 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
93 where F: FnMut(Acc, Self::Item) -> Acc,
95 self.iter.fold(init, f)
98 fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
99 where P: FnMut(&Self::Item) -> bool
101 self.iter.find(predicate)
105 #[stable(feature = "rust1", since = "1.0.0")]
106 impl<I> ExactSizeIterator for Rev<I>
107 where I: ExactSizeIterator + DoubleEndedIterator
109 fn len(&self) -> usize {
113 fn is_empty(&self) -> bool {
118 #[stable(feature = "fused", since = "1.26.0")]
119 impl<I> FusedIterator for Rev<I>
120 where I: FusedIterator + DoubleEndedIterator {}
122 #[unstable(feature = "trusted_len", issue = "37572")]
123 unsafe impl<I> TrustedLen for Rev<I>
124 where I: TrustedLen + DoubleEndedIterator {}
126 /// An iterator that copies the elements of an underlying iterator.
128 /// This `struct` is created by the [`copied`] method on [`Iterator`]. See its
129 /// documentation for more.
131 /// [`copied`]: trait.Iterator.html#method.copied
132 /// [`Iterator`]: trait.Iterator.html
133 #[stable(feature = "iter_copied", since = "1.36.0")]
134 #[must_use = "iterators are lazy and do nothing unless consumed"]
135 #[derive(Clone, Debug)]
136 pub struct Copied<I> {
141 pub(super) fn new(it: I) -> Copied<I> {
146 #[stable(feature = "iter_copied", since = "1.36.0")]
147 impl<'a, I, T: 'a> Iterator for Copied<I>
148 where I: Iterator<Item=&'a T>, T: Copy
152 fn next(&mut self) -> Option<T> {
153 self.it.next().copied()
156 fn size_hint(&self) -> (usize, Option<usize>) {
160 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
161 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
163 self.it.try_fold(init, move |acc, &elt| f(acc, elt))
166 fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc
167 where F: FnMut(Acc, Self::Item) -> Acc,
169 self.it.fold(init, move |acc, &elt| f(acc, elt))
173 #[stable(feature = "iter_copied", since = "1.36.0")]
174 impl<'a, I, T: 'a> DoubleEndedIterator for Copied<I>
175 where I: DoubleEndedIterator<Item=&'a T>, T: Copy
177 fn next_back(&mut self) -> Option<T> {
178 self.it.next_back().copied()
181 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
182 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
184 self.it.try_rfold(init, move |acc, &elt| f(acc, elt))
187 fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc
188 where F: FnMut(Acc, Self::Item) -> Acc,
190 self.it.rfold(init, move |acc, &elt| f(acc, elt))
194 #[stable(feature = "iter_copied", since = "1.36.0")]
195 impl<'a, I, T: 'a> ExactSizeIterator for Copied<I>
196 where I: ExactSizeIterator<Item=&'a T>, T: Copy
198 fn len(&self) -> usize {
202 fn is_empty(&self) -> bool {
207 #[stable(feature = "iter_copied", since = "1.36.0")]
208 impl<'a, I, T: 'a> FusedIterator for Copied<I>
209 where I: FusedIterator<Item=&'a T>, T: Copy
213 unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Copied<I>
214 where I: TrustedRandomAccess<Item=&'a T>, T: Copy
216 unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
217 *self.it.get_unchecked(i)
221 fn may_have_side_effect() -> bool {
222 I::may_have_side_effect()
226 #[stable(feature = "iter_copied", since = "1.36.0")]
227 unsafe impl<'a, I, T: 'a> TrustedLen for Copied<I>
228 where I: TrustedLen<Item=&'a T>,
232 /// An iterator that clones the elements of an underlying iterator.
234 /// This `struct` is created by the [`cloned`] method on [`Iterator`]. See its
235 /// documentation for more.
237 /// [`cloned`]: trait.Iterator.html#method.cloned
238 /// [`Iterator`]: trait.Iterator.html
239 #[stable(feature = "iter_cloned", since = "1.1.0")]
240 #[must_use = "iterators are lazy and do nothing unless consumed"]
241 #[derive(Clone, Debug)]
242 pub struct Cloned<I> {
246 pub(super) fn new(it: I) -> Cloned<I> {
251 #[stable(feature = "iter_cloned", since = "1.1.0")]
252 impl<'a, I, T: 'a> Iterator for Cloned<I>
253 where I: Iterator<Item=&'a T>, T: Clone
257 fn next(&mut self) -> Option<T> {
258 self.it.next().cloned()
261 fn size_hint(&self) -> (usize, Option<usize>) {
265 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
266 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
268 self.it.try_fold(init, move |acc, elt| f(acc, elt.clone()))
271 fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc
272 where F: FnMut(Acc, Self::Item) -> Acc,
274 self.it.fold(init, move |acc, elt| f(acc, elt.clone()))
278 #[stable(feature = "iter_cloned", since = "1.1.0")]
279 impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
280 where I: DoubleEndedIterator<Item=&'a T>, T: Clone
282 fn next_back(&mut self) -> Option<T> {
283 self.it.next_back().cloned()
286 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
287 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
289 self.it.try_rfold(init, move |acc, elt| f(acc, elt.clone()))
292 fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc
293 where F: FnMut(Acc, Self::Item) -> Acc,
295 self.it.rfold(init, move |acc, elt| f(acc, elt.clone()))
299 #[stable(feature = "iter_cloned", since = "1.1.0")]
300 impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
301 where I: ExactSizeIterator<Item=&'a T>, T: Clone
303 fn len(&self) -> usize {
307 fn is_empty(&self) -> bool {
312 #[stable(feature = "fused", since = "1.26.0")]
313 impl<'a, I, T: 'a> FusedIterator for Cloned<I>
314 where I: FusedIterator<Item=&'a T>, T: Clone
318 unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
319 where I: TrustedRandomAccess<Item=&'a T>, T: Clone
321 default unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
322 self.it.get_unchecked(i).clone()
326 default fn may_have_side_effect() -> bool { true }
330 unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
331 where I: TrustedRandomAccess<Item=&'a T>, T: Copy
333 unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
334 *self.it.get_unchecked(i)
338 fn may_have_side_effect() -> bool {
339 I::may_have_side_effect()
343 #[unstable(feature = "trusted_len", issue = "37572")]
344 unsafe impl<'a, I, T: 'a> TrustedLen for Cloned<I>
345 where I: TrustedLen<Item=&'a T>,
349 /// An iterator that repeats endlessly.
351 /// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its
352 /// documentation for more.
354 /// [`cycle`]: trait.Iterator.html#method.cycle
355 /// [`Iterator`]: trait.Iterator.html
356 #[derive(Clone, Debug)]
357 #[must_use = "iterators are lazy and do nothing unless consumed"]
358 #[stable(feature = "rust1", since = "1.0.0")]
359 pub struct Cycle<I> {
363 impl<I: Clone> Cycle<I> {
364 pub(super) fn new(iter: I) -> Cycle<I> {
365 Cycle { orig: iter.clone(), iter }
369 #[stable(feature = "rust1", since = "1.0.0")]
370 impl<I> Iterator for Cycle<I> where I: Clone + Iterator {
371 type Item = <I as Iterator>::Item;
374 fn next(&mut self) -> Option<<I as Iterator>::Item> {
375 match self.iter.next() {
376 None => { self.iter = self.orig.clone(); self.iter.next() }
382 fn size_hint(&self) -> (usize, Option<usize>) {
383 // the cycle iterator is either empty or infinite
384 match self.orig.size_hint() {
385 sz @ (0, Some(0)) => sz,
387 _ => (usize::MAX, None)
392 #[stable(feature = "fused", since = "1.26.0")]
393 impl<I> FusedIterator for Cycle<I> where I: Clone + Iterator {}
395 /// An iterator for stepping iterators by a custom amount.
397 /// This `struct` is created by the [`step_by`] method on [`Iterator`]. See
398 /// its documentation for more.
400 /// [`step_by`]: trait.Iterator.html#method.step_by
401 /// [`Iterator`]: trait.Iterator.html
402 #[must_use = "iterators are lazy and do nothing unless consumed"]
403 #[stable(feature = "iterator_step_by", since = "1.28.0")]
404 #[derive(Clone, Debug)]
405 pub struct StepBy<I> {
411 pub(super) fn new(iter: I, step: usize) -> StepBy<I> {
413 StepBy { iter, step: step - 1, first_take: true }
417 #[stable(feature = "iterator_step_by", since = "1.28.0")]
418 impl<I> Iterator for StepBy<I> where I: Iterator {
422 fn next(&mut self) -> Option<Self::Item> {
424 self.first_take = false;
427 self.iter.nth(self.step)
432 fn size_hint(&self) -> (usize, Option<usize>) {
433 let inner_hint = self.iter.size_hint();
436 let f = |n| if n == 0 { 0 } else { 1 + (n-1)/(self.step+1) };
437 (f(inner_hint.0), inner_hint.1.map(f))
439 let f = |n| n / (self.step+1);
440 (f(inner_hint.0), inner_hint.1.map(f))
445 fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
447 self.first_take = false;
448 let first = self.iter.next();
454 // n and self.step are indices, we need to add 1 to get the amount of elements
455 // When calling `.nth`, we need to subtract 1 again to convert back to an index
456 // step + 1 can't overflow because `.step_by` sets `self.step` to `step - 1`
457 let mut step = self.step + 1;
458 // n + 1 could overflow
459 // thus, if n is usize::MAX, instead of adding one, we call .nth(step)
461 self.iter.nth(step - 1);
468 let mul = n.checked_mul(step);
469 if unsafe { intrinsics::likely(mul.is_some()) } {
470 return self.iter.nth(mul.unwrap() - 1);
472 let div_n = usize::MAX / n;
473 let div_step = usize::MAX / step;
474 let nth_n = div_n * n;
475 let nth_step = div_step * step;
476 let nth = if nth_n > nth_step {
483 self.iter.nth(nth - 1);
488 impl<I> StepBy<I> where I: ExactSizeIterator {
489 // The zero-based index starting from the end of the iterator of the
490 // last element. Used in the `DoubleEndedIterator` implementation.
491 fn next_back_index(&self) -> usize {
492 let rem = self.iter.len() % (self.step + 1);
494 if rem == 0 { self.step } else { rem - 1 }
501 #[stable(feature = "double_ended_step_by_iterator", since = "1.38.0")]
502 impl<I> DoubleEndedIterator for StepBy<I> where I: DoubleEndedIterator + ExactSizeIterator {
504 fn next_back(&mut self) -> Option<Self::Item> {
505 self.iter.nth_back(self.next_back_index())
509 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
510 // `self.iter.nth_back(usize::MAX)` does the right thing here when `n`
511 // is out of bounds because the length of `self.iter` does not exceed
512 // `usize::MAX` (because `I: ExactSizeIterator`) and `nth_back` is
515 .saturating_mul(self.step + 1)
516 .saturating_add(self.next_back_index());
517 self.iter.nth_back(n)
521 // StepBy can only make the iterator shorter, so the len will still fit.
522 #[stable(feature = "iterator_step_by", since = "1.28.0")]
523 impl<I> ExactSizeIterator for StepBy<I> where I: ExactSizeIterator {}
525 /// An iterator that maps the values of `iter` with `f`.
527 /// This `struct` is created by the [`map`] method on [`Iterator`]. See its
528 /// documentation for more.
530 /// [`map`]: trait.Iterator.html#method.map
531 /// [`Iterator`]: trait.Iterator.html
533 /// # Notes about side effects
535 /// The [`map`] iterator implements [`DoubleEndedIterator`], meaning that
536 /// you can also [`map`] backwards:
539 /// let v: Vec<i32> = vec![1, 2, 3].into_iter().map(|x| x + 1).rev().collect();
541 /// assert_eq!(v, [4, 3, 2]);
544 /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
546 /// But if your closure has state, iterating backwards may act in a way you do
547 /// not expect. Let's go through an example. First, in the forward direction:
552 /// for pair in vec!['a', 'b', 'c'].into_iter()
553 /// .map(|letter| { c += 1; (letter, c) }) {
554 /// println!("{:?}", pair);
558 /// This will print "('a', 1), ('b', 2), ('c', 3)".
560 /// Now consider this twist where we add a call to `rev`. This version will
561 /// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed,
562 /// but the values of the counter still go in order. This is because `map()` is
563 /// still being called lazily on each item, but we are popping items off the
564 /// back of the vector now, instead of shifting them from the front.
569 /// for pair in vec!['a', 'b', 'c'].into_iter()
570 /// .map(|letter| { c += 1; (letter, c) })
572 /// println!("{:?}", pair);
575 #[must_use = "iterators are lazy and do nothing unless consumed"]
576 #[stable(feature = "rust1", since = "1.0.0")]
578 pub struct Map<I, F> {
582 impl<I, F> Map<I, F> {
583 pub(super) fn new(iter: I, f: F) -> Map<I, F> {
588 #[stable(feature = "core_impl_debug", since = "1.9.0")]
589 impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> {
590 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
591 f.debug_struct("Map")
592 .field("iter", &self.iter)
597 #[stable(feature = "rust1", since = "1.0.0")]
598 impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
602 fn next(&mut self) -> Option<B> {
603 self.iter.next().map(&mut self.f)
607 fn size_hint(&self) -> (usize, Option<usize>) {
608 self.iter.size_hint()
611 fn try_fold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where
612 Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
615 self.iter.try_fold(init, move |acc, elt| g(acc, f(elt)))
618 fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc
619 where G: FnMut(Acc, Self::Item) -> Acc,
622 self.iter.fold(init, move |acc, elt| g(acc, f(elt)))
626 #[stable(feature = "rust1", since = "1.0.0")]
627 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where
628 F: FnMut(I::Item) -> B,
631 fn next_back(&mut self) -> Option<B> {
632 self.iter.next_back().map(&mut self.f)
635 fn try_rfold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where
636 Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
639 self.iter.try_rfold(init, move |acc, elt| g(acc, f(elt)))
642 fn rfold<Acc, G>(self, init: Acc, mut g: G) -> Acc
643 where G: FnMut(Acc, Self::Item) -> Acc,
646 self.iter.rfold(init, move |acc, elt| g(acc, f(elt)))
650 #[stable(feature = "rust1", since = "1.0.0")]
651 impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F>
652 where F: FnMut(I::Item) -> B
654 fn len(&self) -> usize {
658 fn is_empty(&self) -> bool {
663 #[stable(feature = "fused", since = "1.26.0")]
664 impl<B, I: FusedIterator, F> FusedIterator for Map<I, F>
665 where F: FnMut(I::Item) -> B {}
667 #[unstable(feature = "trusted_len", issue = "37572")]
668 unsafe impl<B, I, F> TrustedLen for Map<I, F>
670 F: FnMut(I::Item) -> B {}
673 unsafe impl<B, I, F> TrustedRandomAccess for Map<I, F>
674 where I: TrustedRandomAccess,
675 F: FnMut(I::Item) -> B,
677 unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
678 (self.f)(self.iter.get_unchecked(i))
681 fn may_have_side_effect() -> bool { true }
684 /// An iterator that filters the elements of `iter` with `predicate`.
686 /// This `struct` is created by the [`filter`] method on [`Iterator`]. See its
687 /// documentation for more.
689 /// [`filter`]: trait.Iterator.html#method.filter
690 /// [`Iterator`]: trait.Iterator.html
691 #[must_use = "iterators are lazy and do nothing unless consumed"]
692 #[stable(feature = "rust1", since = "1.0.0")]
694 pub struct Filter<I, P> {
698 impl<I, P> Filter<I, P> {
699 pub(super) fn new(iter: I, predicate: P) -> Filter<I, P> {
700 Filter { iter, predicate }
704 #[stable(feature = "core_impl_debug", since = "1.9.0")]
705 impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
706 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
707 f.debug_struct("Filter")
708 .field("iter", &self.iter)
713 #[stable(feature = "rust1", since = "1.0.0")]
714 impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {
718 fn next(&mut self) -> Option<I::Item> {
719 self.try_for_each(Err).err()
723 fn size_hint(&self) -> (usize, Option<usize>) {
724 let (_, upper) = self.iter.size_hint();
725 (0, upper) // can't know a lower bound, due to the predicate
728 // this special case allows the compiler to make `.filter(_).count()`
729 // branchless. Barring perfect branch prediction (which is unattainable in
730 // the general case), this will be much faster in >90% of cases (containing
731 // virtually all real workloads) and only a tiny bit slower in the rest.
733 // Having this specialization thus allows us to write `.filter(p).count()`
734 // where we would otherwise write `.map(|x| p(x) as usize).sum()`, which is
735 // less readable and also less backwards-compatible to Rust before 1.10.
737 // Using the branchless version will also simplify the LLVM byte code, thus
738 // leaving more budget for LLVM optimizations.
740 fn count(self) -> usize {
741 let mut predicate = self.predicate;
742 self.iter.map(|x| predicate(&x) as usize).sum()
746 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
747 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
749 let predicate = &mut self.predicate;
750 self.iter.try_fold(init, move |acc, item| if predicate(&item) {
758 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
759 where Fold: FnMut(Acc, Self::Item) -> Acc,
761 let mut predicate = self.predicate;
762 self.iter.fold(init, move |acc, item| if predicate(&item) {
770 #[stable(feature = "rust1", since = "1.0.0")]
771 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
772 where P: FnMut(&I::Item) -> bool,
775 fn next_back(&mut self) -> Option<I::Item> {
776 self.try_rfold((), |_, x| Err(x)).err()
780 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
781 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
783 let predicate = &mut self.predicate;
784 self.iter.try_rfold(init, move |acc, item| if predicate(&item) {
792 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
793 where Fold: FnMut(Acc, Self::Item) -> Acc,
795 let mut predicate = self.predicate;
796 self.iter.rfold(init, move |acc, item| if predicate(&item) {
804 #[stable(feature = "fused", since = "1.26.0")]
805 impl<I: FusedIterator, P> FusedIterator for Filter<I, P>
806 where P: FnMut(&I::Item) -> bool {}
808 /// An iterator that uses `f` to both filter and map elements from `iter`.
810 /// This `struct` is created by the [`filter_map`] method on [`Iterator`]. See its
811 /// documentation for more.
813 /// [`filter_map`]: trait.Iterator.html#method.filter_map
814 /// [`Iterator`]: trait.Iterator.html
815 #[must_use = "iterators are lazy and do nothing unless consumed"]
816 #[stable(feature = "rust1", since = "1.0.0")]
818 pub struct FilterMap<I, F> {
822 impl<I, F> FilterMap<I, F> {
823 pub(super) fn new(iter: I, f: F) -> FilterMap<I, F> {
824 FilterMap { iter, f }
828 #[stable(feature = "core_impl_debug", since = "1.9.0")]
829 impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> {
830 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
831 f.debug_struct("FilterMap")
832 .field("iter", &self.iter)
837 #[stable(feature = "rust1", since = "1.0.0")]
838 impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
839 where F: FnMut(I::Item) -> Option<B>,
844 fn next(&mut self) -> Option<B> {
845 self.try_for_each(Err).err()
849 fn size_hint(&self) -> (usize, Option<usize>) {
850 let (_, upper) = self.iter.size_hint();
851 (0, upper) // can't know a lower bound, due to the predicate
855 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
856 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
859 self.iter.try_fold(init, move |acc, item| match f(item) {
860 Some(x) => fold(acc, x),
861 None => Try::from_ok(acc),
866 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
867 where Fold: FnMut(Acc, Self::Item) -> Acc,
870 self.iter.fold(init, move |acc, item| match f(item) {
871 Some(x) => fold(acc, x),
877 #[stable(feature = "rust1", since = "1.0.0")]
878 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
879 where F: FnMut(I::Item) -> Option<B>,
882 fn next_back(&mut self) -> Option<B> {
883 self.try_rfold((), |_, x| Err(x)).err()
887 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
888 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
891 self.iter.try_rfold(init, move |acc, item| match f(item) {
892 Some(x) => fold(acc, x),
893 None => Try::from_ok(acc),
898 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
899 where Fold: FnMut(Acc, Self::Item) -> Acc,
902 self.iter.rfold(init, move |acc, item| match f(item) {
903 Some(x) => fold(acc, x),
909 #[stable(feature = "fused", since = "1.26.0")]
910 impl<B, I: FusedIterator, F> FusedIterator for FilterMap<I, F>
911 where F: FnMut(I::Item) -> Option<B> {}
913 /// An iterator that yields the current count and the element during iteration.
915 /// This `struct` is created by the [`enumerate`] method on [`Iterator`]. See its
916 /// documentation for more.
918 /// [`enumerate`]: trait.Iterator.html#method.enumerate
919 /// [`Iterator`]: trait.Iterator.html
920 #[derive(Clone, Debug)]
921 #[must_use = "iterators are lazy and do nothing unless consumed"]
922 #[stable(feature = "rust1", since = "1.0.0")]
923 pub struct Enumerate<I> {
927 impl<I> Enumerate<I> {
928 pub(super) fn new(iter: I) -> Enumerate<I> {
929 Enumerate { iter, count: 0 }
933 #[stable(feature = "rust1", since = "1.0.0")]
934 impl<I> Iterator for Enumerate<I> where I: Iterator {
935 type Item = (usize, <I as Iterator>::Item);
937 /// # Overflow Behavior
939 /// The method does no guarding against overflows, so enumerating more than
940 /// `usize::MAX` elements either produces the wrong result or panics. If
941 /// debug assertions are enabled, a panic is guaranteed.
945 /// Might panic if the index of the element overflows a `usize`.
947 #[rustc_inherit_overflow_checks]
948 fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
949 self.iter.next().map(|a| {
950 let ret = (self.count, a);
951 // Possible undefined overflow.
958 fn size_hint(&self) -> (usize, Option<usize>) {
959 self.iter.size_hint()
963 #[rustc_inherit_overflow_checks]
964 fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
965 self.iter.nth(n).map(|a| {
966 let i = self.count + n;
973 fn count(self) -> usize {
978 #[rustc_inherit_overflow_checks]
979 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
980 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
982 let count = &mut self.count;
983 self.iter.try_fold(init, move |acc, item| {
984 let acc = fold(acc, (*count, item));
991 #[rustc_inherit_overflow_checks]
992 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
993 where Fold: FnMut(Acc, Self::Item) -> Acc,
995 let mut count = self.count;
996 self.iter.fold(init, move |acc, item| {
997 let acc = fold(acc, (count, item));
1004 #[stable(feature = "rust1", since = "1.0.0")]
1005 impl<I> DoubleEndedIterator for Enumerate<I> where
1006 I: ExactSizeIterator + DoubleEndedIterator
1009 fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1010 self.iter.next_back().map(|a| {
1011 let len = self.iter.len();
1012 // Can safely add, `ExactSizeIterator` promises that the number of
1013 // elements fits into a `usize`.
1014 (self.count + len, a)
1019 fn nth_back(&mut self, n: usize) -> Option<(usize, <I as Iterator>::Item)> {
1020 self.iter.nth_back(n).map(|a| {
1021 let len = self.iter.len();
1022 // Can safely add, `ExactSizeIterator` promises that the number of
1023 // elements fits into a `usize`.
1024 (self.count + len, a)
1029 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1030 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1032 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1033 // that the number of elements fits into a `usize`.
1034 let mut count = self.count + self.iter.len();
1035 self.iter.try_rfold(init, move |acc, item| {
1037 fold(acc, (count, item))
1042 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1043 where Fold: FnMut(Acc, Self::Item) -> Acc,
1045 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1046 // that the number of elements fits into a `usize`.
1047 let mut count = self.count + self.iter.len();
1048 self.iter.rfold(init, move |acc, item| {
1050 fold(acc, (count, item))
1055 #[stable(feature = "rust1", since = "1.0.0")]
1056 impl<I> ExactSizeIterator for Enumerate<I> where I: ExactSizeIterator {
1057 fn len(&self) -> usize {
1061 fn is_empty(&self) -> bool {
1062 self.iter.is_empty()
1067 unsafe impl<I> TrustedRandomAccess for Enumerate<I>
1068 where I: TrustedRandomAccess
1070 unsafe fn get_unchecked(&mut self, i: usize) -> (usize, I::Item) {
1071 (self.count + i, self.iter.get_unchecked(i))
1074 fn may_have_side_effect() -> bool {
1075 I::may_have_side_effect()
1079 #[stable(feature = "fused", since = "1.26.0")]
1080 impl<I> FusedIterator for Enumerate<I> where I: FusedIterator {}
1082 #[unstable(feature = "trusted_len", issue = "37572")]
1083 unsafe impl<I> TrustedLen for Enumerate<I>
1084 where I: TrustedLen,
1088 /// An iterator with a `peek()` that returns an optional reference to the next
1091 /// This `struct` is created by the [`peekable`] method on [`Iterator`]. See its
1092 /// documentation for more.
1094 /// [`peekable`]: trait.Iterator.html#method.peekable
1095 /// [`Iterator`]: trait.Iterator.html
1096 #[derive(Clone, Debug)]
1097 #[must_use = "iterators are lazy and do nothing unless consumed"]
1098 #[stable(feature = "rust1", since = "1.0.0")]
1099 pub struct Peekable<I: Iterator> {
1101 /// Remember a peeked value, even if it was None.
1102 peeked: Option<Option<I::Item>>,
1104 impl<I: Iterator> Peekable<I> {
1105 pub(super) fn new(iter: I) -> Peekable<I> {
1106 Peekable { iter, peeked: None }
1110 // Peekable must remember if a None has been seen in the `.peek()` method.
1111 // It ensures that `.peek(); .peek();` or `.peek(); .next();` only advances the
1112 // underlying iterator at most once. This does not by itself make the iterator
1114 #[stable(feature = "rust1", since = "1.0.0")]
1115 impl<I: Iterator> Iterator for Peekable<I> {
1116 type Item = I::Item;
1119 fn next(&mut self) -> Option<I::Item> {
1120 match self.peeked.take() {
1122 None => self.iter.next(),
1127 #[rustc_inherit_overflow_checks]
1128 fn count(mut self) -> usize {
1129 match self.peeked.take() {
1131 Some(Some(_)) => 1 + self.iter.count(),
1132 None => self.iter.count(),
1137 fn nth(&mut self, n: usize) -> Option<I::Item> {
1138 match self.peeked.take() {
1140 Some(v @ Some(_)) if n == 0 => v,
1141 Some(Some(_)) => self.iter.nth(n - 1),
1142 None => self.iter.nth(n),
1147 fn last(mut self) -> Option<I::Item> {
1148 let peek_opt = match self.peeked.take() {
1149 Some(None) => return None,
1153 self.iter.last().or(peek_opt)
1157 fn size_hint(&self) -> (usize, Option<usize>) {
1158 let peek_len = match self.peeked {
1159 Some(None) => return (0, Some(0)),
1163 let (lo, hi) = self.iter.size_hint();
1164 let lo = lo.saturating_add(peek_len);
1165 let hi = hi.and_then(|x| x.checked_add(peek_len));
1170 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
1171 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
1173 let acc = match self.peeked.take() {
1174 Some(None) => return Try::from_ok(init),
1175 Some(Some(v)) => f(init, v)?,
1178 self.iter.try_fold(acc, f)
1182 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1183 where Fold: FnMut(Acc, Self::Item) -> Acc,
1185 let acc = match self.peeked {
1186 Some(None) => return init,
1187 Some(Some(v)) => fold(init, v),
1190 self.iter.fold(acc, fold)
1194 #[stable(feature = "double_ended_peek_iterator", since = "1.38.0")]
1195 impl<I> DoubleEndedIterator for Peekable<I> where I: DoubleEndedIterator {
1197 fn next_back(&mut self) -> Option<Self::Item> {
1198 self.iter.next_back().or_else(|| self.peeked.take().and_then(|x| x))
1202 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
1203 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
1205 match self.peeked.take() {
1206 Some(None) => return Try::from_ok(init),
1207 Some(Some(v)) => match self.iter.try_rfold(init, &mut f).into_result() {
1208 Ok(acc) => f(acc, v),
1210 self.peeked = Some(Some(v));
1214 None => self.iter.try_rfold(init, f),
1219 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1220 where Fold: FnMut(Acc, Self::Item) -> Acc,
1223 Some(None) => return init,
1225 let acc = self.iter.rfold(init, &mut fold);
1228 None => self.iter.rfold(init, fold),
1233 #[stable(feature = "rust1", since = "1.0.0")]
1234 impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
1236 #[stable(feature = "fused", since = "1.26.0")]
1237 impl<I: FusedIterator> FusedIterator for Peekable<I> {}
1239 impl<I: Iterator> Peekable<I> {
1240 /// Returns a reference to the next() value without advancing the iterator.
1242 /// Like [`next`], if there is a value, it is wrapped in a `Some(T)`.
1243 /// But if the iteration is over, `None` is returned.
1245 /// [`next`]: trait.Iterator.html#tymethod.next
1247 /// Because `peek()` returns a reference, and many iterators iterate over
1248 /// references, there can be a possibly confusing situation where the
1249 /// return value is a double reference. You can see this effect in the
1257 /// let xs = [1, 2, 3];
1259 /// let mut iter = xs.iter().peekable();
1261 /// // peek() lets us see into the future
1262 /// assert_eq!(iter.peek(), Some(&&1));
1263 /// assert_eq!(iter.next(), Some(&1));
1265 /// assert_eq!(iter.next(), Some(&2));
1267 /// // The iterator does not advance even if we `peek` multiple times
1268 /// assert_eq!(iter.peek(), Some(&&3));
1269 /// assert_eq!(iter.peek(), Some(&&3));
1271 /// assert_eq!(iter.next(), Some(&3));
1273 /// // After the iterator is finished, so is `peek()`
1274 /// assert_eq!(iter.peek(), None);
1275 /// assert_eq!(iter.next(), None);
1278 #[stable(feature = "rust1", since = "1.0.0")]
1279 pub fn peek(&mut self) -> Option<&I::Item> {
1280 let iter = &mut self.iter;
1281 self.peeked.get_or_insert_with(|| iter.next()).as_ref()
1285 /// An iterator that rejects elements while `predicate` returns `true`.
1287 /// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its
1288 /// documentation for more.
1290 /// [`skip_while`]: trait.Iterator.html#method.skip_while
1291 /// [`Iterator`]: trait.Iterator.html
1292 #[must_use = "iterators are lazy and do nothing unless consumed"]
1293 #[stable(feature = "rust1", since = "1.0.0")]
1295 pub struct SkipWhile<I, P> {
1300 impl<I, P> SkipWhile<I, P> {
1301 pub(super) fn new(iter: I, predicate: P) -> SkipWhile<I, P> {
1302 SkipWhile { iter, flag: false, predicate }
1306 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1307 impl<I: fmt::Debug, P> fmt::Debug for SkipWhile<I, P> {
1308 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1309 f.debug_struct("SkipWhile")
1310 .field("iter", &self.iter)
1311 .field("flag", &self.flag)
1316 #[stable(feature = "rust1", since = "1.0.0")]
1317 impl<I: Iterator, P> Iterator for SkipWhile<I, P>
1318 where P: FnMut(&I::Item) -> bool
1320 type Item = I::Item;
1323 fn next(&mut self) -> Option<I::Item> {
1324 let flag = &mut self.flag;
1325 let pred = &mut self.predicate;
1326 self.iter.find(move |x| {
1327 if *flag || !pred(x) {
1337 fn size_hint(&self) -> (usize, Option<usize>) {
1338 let (_, upper) = self.iter.size_hint();
1339 (0, upper) // can't know a lower bound, due to the predicate
1343 fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where
1344 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1348 Some(v) => init = fold(init, v)?,
1349 None => return Try::from_ok(init),
1352 self.iter.try_fold(init, fold)
1356 fn fold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
1357 where Fold: FnMut(Acc, Self::Item) -> Acc,
1361 Some(v) => init = fold(init, v),
1362 None => return init,
1365 self.iter.fold(init, fold)
1369 #[stable(feature = "fused", since = "1.26.0")]
1370 impl<I, P> FusedIterator for SkipWhile<I, P>
1371 where I: FusedIterator, P: FnMut(&I::Item) -> bool {}
1373 /// An iterator that only accepts elements while `predicate` returns `true`.
1375 /// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its
1376 /// documentation for more.
1378 /// [`take_while`]: trait.Iterator.html#method.take_while
1379 /// [`Iterator`]: trait.Iterator.html
1380 #[must_use = "iterators are lazy and do nothing unless consumed"]
1381 #[stable(feature = "rust1", since = "1.0.0")]
1383 pub struct TakeWhile<I, P> {
1388 impl<I, P> TakeWhile<I, P> {
1389 pub(super) fn new(iter: I, predicate: P) -> TakeWhile<I, P> {
1390 TakeWhile { iter, flag: false, predicate }
1394 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1395 impl<I: fmt::Debug, P> fmt::Debug for TakeWhile<I, P> {
1396 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1397 f.debug_struct("TakeWhile")
1398 .field("iter", &self.iter)
1399 .field("flag", &self.flag)
1404 #[stable(feature = "rust1", since = "1.0.0")]
1405 impl<I: Iterator, P> Iterator for TakeWhile<I, P>
1406 where P: FnMut(&I::Item) -> bool
1408 type Item = I::Item;
1411 fn next(&mut self) -> Option<I::Item> {
1415 self.iter.next().and_then(|x| {
1416 if (self.predicate)(&x) {
1427 fn size_hint(&self) -> (usize, Option<usize>) {
1431 let (_, upper) = self.iter.size_hint();
1432 (0, upper) // can't know a lower bound, due to the predicate
1437 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1438 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1443 let flag = &mut self.flag;
1444 let p = &mut self.predicate;
1445 self.iter.try_fold(init, move |acc, x|{
1447 LoopState::from_try(fold(acc, x))
1450 LoopState::Break(Try::from_ok(acc))
1457 #[stable(feature = "fused", since = "1.26.0")]
1458 impl<I, P> FusedIterator for TakeWhile<I, P>
1459 where I: FusedIterator, P: FnMut(&I::Item) -> bool {}
1461 /// An iterator that skips over `n` elements of `iter`.
1463 /// This `struct` is created by the [`skip`] method on [`Iterator`]. See its
1464 /// documentation for more.
1466 /// [`skip`]: trait.Iterator.html#method.skip
1467 /// [`Iterator`]: trait.Iterator.html
1468 #[derive(Clone, Debug)]
1469 #[must_use = "iterators are lazy and do nothing unless consumed"]
1470 #[stable(feature = "rust1", since = "1.0.0")]
1471 pub struct Skip<I> {
1476 pub(super) fn new(iter: I, n: usize) -> Skip<I> {
1481 #[stable(feature = "rust1", since = "1.0.0")]
1482 impl<I> Iterator for Skip<I> where I: Iterator {
1483 type Item = <I as Iterator>::Item;
1486 fn next(&mut self) -> Option<I::Item> {
1492 self.iter.nth(old_n)
1497 fn nth(&mut self, n: usize) -> Option<I::Item> {
1498 // Can't just add n + self.n due to overflow.
1502 let to_skip = self.n;
1505 if self.iter.nth(to_skip-1).is_none() {
1513 fn count(self) -> usize {
1514 self.iter.count().saturating_sub(self.n)
1518 fn last(mut self) -> Option<I::Item> {
1522 let next = self.next();
1524 // recurse. n should be 0.
1525 self.last().or(next)
1533 fn size_hint(&self) -> (usize, Option<usize>) {
1534 let (lower, upper) = self.iter.size_hint();
1536 let lower = lower.saturating_sub(self.n);
1537 let upper = upper.map(|x| x.saturating_sub(self.n));
1543 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
1544 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1550 if self.iter.nth(n - 1).is_none() {
1551 return Try::from_ok(init);
1554 self.iter.try_fold(init, fold)
1558 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
1559 where Fold: FnMut(Acc, Self::Item) -> Acc,
1563 if self.iter.nth(self.n - 1).is_none() {
1567 self.iter.fold(init, fold)
1571 #[stable(feature = "rust1", since = "1.0.0")]
1572 impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
1574 #[stable(feature = "double_ended_skip_iterator", since = "1.9.0")]
1575 impl<I> DoubleEndedIterator for Skip<I> where I: DoubleEndedIterator + ExactSizeIterator {
1576 fn next_back(&mut self) -> Option<Self::Item> {
1578 self.iter.next_back()
1585 fn nth_back(&mut self, n: usize) -> Option<I::Item> {
1586 let len = self.len();
1588 self.iter.nth_back(n)
1591 // consume the original iterator
1592 self.iter.nth_back(len-1);
1598 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1599 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1601 let mut n = self.len();
1605 self.iter.try_rfold(init, move |acc, x| {
1607 let r = fold(acc, x);
1608 if n == 0 { LoopState::Break(r) }
1609 else { LoopState::from_try(r) }
1615 #[stable(feature = "fused", since = "1.26.0")]
1616 impl<I> FusedIterator for Skip<I> where I: FusedIterator {}
1618 /// An iterator that only iterates over the first `n` iterations of `iter`.
1620 /// This `struct` is created by the [`take`] method on [`Iterator`]. See its
1621 /// documentation for more.
1623 /// [`take`]: trait.Iterator.html#method.take
1624 /// [`Iterator`]: trait.Iterator.html
1625 #[derive(Clone, Debug)]
1626 #[must_use = "iterators are lazy and do nothing unless consumed"]
1627 #[stable(feature = "rust1", since = "1.0.0")]
1628 pub struct Take<I> {
1633 pub(super) fn new(iter: I, n: usize) -> Take<I> {
1638 #[stable(feature = "rust1", since = "1.0.0")]
1639 impl<I> Iterator for Take<I> where I: Iterator{
1640 type Item = <I as Iterator>::Item;
1643 fn next(&mut self) -> Option<<I as Iterator>::Item> {
1653 fn nth(&mut self, n: usize) -> Option<I::Item> {
1659 self.iter.nth(self.n - 1);
1667 fn size_hint(&self) -> (usize, Option<usize>) {
1669 return (0, Some(0));
1672 let (lower, upper) = self.iter.size_hint();
1674 let lower = cmp::min(lower, self.n);
1676 let upper = match upper {
1677 Some(x) if x < self.n => Some(x),
1685 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1686 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1691 let n = &mut self.n;
1692 self.iter.try_fold(init, move |acc, x| {
1694 let r = fold(acc, x);
1695 if *n == 0 { LoopState::Break(r) }
1696 else { LoopState::from_try(r) }
1702 #[stable(feature = "double_ended_take_iterator", since = "1.38.0")]
1703 impl<I> DoubleEndedIterator for Take<I> where I: DoubleEndedIterator + ExactSizeIterator {
1705 fn next_back(&mut self) -> Option<Self::Item> {
1711 self.iter.nth_back(self.iter.len().saturating_sub(n))
1716 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1717 let len = self.iter.len();
1719 let m = len.saturating_sub(self.n) + n;
1721 self.iter.nth_back(m)
1724 self.iter.nth_back(len - 1);
1731 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
1732 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok = Acc>
1737 let len = self.iter.len();
1738 if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() {
1741 self.iter.try_rfold(init, fold)
1747 #[stable(feature = "rust1", since = "1.0.0")]
1748 impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
1750 #[stable(feature = "fused", since = "1.26.0")]
1751 impl<I> FusedIterator for Take<I> where I: FusedIterator {}
1753 #[unstable(feature = "trusted_len", issue = "37572")]
1754 unsafe impl<I: TrustedLen> TrustedLen for Take<I> {}
1756 /// An iterator to maintain state while iterating another iterator.
1758 /// This `struct` is created by the [`scan`] method on [`Iterator`]. See its
1759 /// documentation for more.
1761 /// [`scan`]: trait.Iterator.html#method.scan
1762 /// [`Iterator`]: trait.Iterator.html
1763 #[must_use = "iterators are lazy and do nothing unless consumed"]
1764 #[stable(feature = "rust1", since = "1.0.0")]
1766 pub struct Scan<I, St, F> {
1771 impl<I, St, F> Scan<I, St, F> {
1772 pub(super) fn new(iter: I, state: St, f: F) -> Scan<I, St, F> {
1773 Scan { iter, state, f }
1777 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1778 impl<I: fmt::Debug, St: fmt::Debug, F> fmt::Debug for Scan<I, St, F> {
1779 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1780 f.debug_struct("Scan")
1781 .field("iter", &self.iter)
1782 .field("state", &self.state)
1787 #[stable(feature = "rust1", since = "1.0.0")]
1788 impl<B, I, St, F> Iterator for Scan<I, St, F> where
1790 F: FnMut(&mut St, I::Item) -> Option<B>,
1795 fn next(&mut self) -> Option<B> {
1796 self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
1800 fn size_hint(&self) -> (usize, Option<usize>) {
1801 let (_, upper) = self.iter.size_hint();
1802 (0, upper) // can't know a lower bound, due to the scan function
1806 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1807 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1809 let state = &mut self.state;
1810 let f = &mut self.f;
1811 self.iter.try_fold(init, move |acc, x| {
1813 None => LoopState::Break(Try::from_ok(acc)),
1814 Some(x) => LoopState::from_try(fold(acc, x)),
1820 /// An iterator that yields `None` forever after the underlying iterator
1821 /// yields `None` once.
1823 /// This `struct` is created by the [`fuse`] method on [`Iterator`]. See its
1824 /// documentation for more.
1826 /// [`fuse`]: trait.Iterator.html#method.fuse
1827 /// [`Iterator`]: trait.Iterator.html
1828 #[derive(Clone, Debug)]
1829 #[must_use = "iterators are lazy and do nothing unless consumed"]
1830 #[stable(feature = "rust1", since = "1.0.0")]
1831 pub struct Fuse<I> {
1836 pub(super) fn new(iter: I) -> Fuse<I> {
1837 Fuse { iter, done: false }
1841 #[stable(feature = "fused", since = "1.26.0")]
1842 impl<I> FusedIterator for Fuse<I> where I: Iterator {}
1844 #[stable(feature = "rust1", since = "1.0.0")]
1845 impl<I> Iterator for Fuse<I> where I: Iterator {
1846 type Item = <I as Iterator>::Item;
1849 default fn next(&mut self) -> Option<<I as Iterator>::Item> {
1853 let next = self.iter.next();
1854 self.done = next.is_none();
1860 default fn nth(&mut self, n: usize) -> Option<I::Item> {
1864 let nth = self.iter.nth(n);
1865 self.done = nth.is_none();
1871 default fn last(self) -> Option<I::Item> {
1880 default fn count(self) -> usize {
1889 default fn size_hint(&self) -> (usize, Option<usize>) {
1893 self.iter.size_hint()
1898 default fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
1899 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1904 let acc = self.iter.try_fold(init, fold)?;
1911 default fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1912 where Fold: FnMut(Acc, Self::Item) -> Acc,
1917 self.iter.fold(init, fold)
1922 #[stable(feature = "rust1", since = "1.0.0")]
1923 impl<I> DoubleEndedIterator for Fuse<I> where I: DoubleEndedIterator {
1925 default fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
1929 let next = self.iter.next_back();
1930 self.done = next.is_none();
1936 default fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
1940 let nth = self.iter.nth_back(n);
1941 self.done = nth.is_none();
1947 default fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
1948 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1953 let acc = self.iter.try_rfold(init, fold)?;
1960 default fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1961 where Fold: FnMut(Acc, Self::Item) -> Acc,
1966 self.iter.rfold(init, fold)
1971 unsafe impl<I> TrustedRandomAccess for Fuse<I>
1972 where I: TrustedRandomAccess,
1974 unsafe fn get_unchecked(&mut self, i: usize) -> I::Item {
1975 self.iter.get_unchecked(i)
1978 fn may_have_side_effect() -> bool {
1979 I::may_have_side_effect()
1983 #[stable(feature = "fused", since = "1.26.0")]
1984 impl<I> Iterator for Fuse<I> where I: FusedIterator {
1986 fn next(&mut self) -> Option<<I as Iterator>::Item> {
1991 fn nth(&mut self, n: usize) -> Option<I::Item> {
1996 fn last(self) -> Option<I::Item> {
2001 fn count(self) -> usize {
2006 fn size_hint(&self) -> (usize, Option<usize>) {
2007 self.iter.size_hint()
2011 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2012 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2014 self.iter.try_fold(init, fold)
2018 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2019 where Fold: FnMut(Acc, Self::Item) -> Acc,
2021 self.iter.fold(init, fold)
2025 #[stable(feature = "fused", since = "1.26.0")]
2026 impl<I> DoubleEndedIterator for Fuse<I>
2027 where I: DoubleEndedIterator + FusedIterator
2030 fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
2031 self.iter.next_back()
2035 fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
2036 self.iter.nth_back(n)
2040 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2041 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2043 self.iter.try_rfold(init, fold)
2047 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2048 where Fold: FnMut(Acc, Self::Item) -> Acc,
2050 self.iter.rfold(init, fold)
2055 #[stable(feature = "rust1", since = "1.0.0")]
2056 impl<I> ExactSizeIterator for Fuse<I> where I: ExactSizeIterator {
2057 fn len(&self) -> usize {
2061 fn is_empty(&self) -> bool {
2062 self.iter.is_empty()
2066 /// An iterator that calls a function with a reference to each element before
2069 /// This `struct` is created by the [`inspect`] method on [`Iterator`]. See its
2070 /// documentation for more.
2072 /// [`inspect`]: trait.Iterator.html#method.inspect
2073 /// [`Iterator`]: trait.Iterator.html
2074 #[must_use = "iterators are lazy and do nothing unless consumed"]
2075 #[stable(feature = "rust1", since = "1.0.0")]
2077 pub struct Inspect<I, F> {
2081 impl<I, F> Inspect<I, F> {
2082 pub(super) fn new(iter: I, f: F) -> Inspect<I, F> {
2087 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2088 impl<I: fmt::Debug, F> fmt::Debug for Inspect<I, F> {
2089 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2090 f.debug_struct("Inspect")
2091 .field("iter", &self.iter)
2096 impl<I: Iterator, F> Inspect<I, F> where F: FnMut(&I::Item) {
2098 fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
2099 if let Some(ref a) = elt {
2107 #[stable(feature = "rust1", since = "1.0.0")]
2108 impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) {
2109 type Item = I::Item;
2112 fn next(&mut self) -> Option<I::Item> {
2113 let next = self.iter.next();
2114 self.do_inspect(next)
2118 fn size_hint(&self) -> (usize, Option<usize>) {
2119 self.iter.size_hint()
2123 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
2124 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2126 let f = &mut self.f;
2127 self.iter.try_fold(init, move |acc, item| { f(&item); fold(acc, item) })
2131 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
2132 where Fold: FnMut(Acc, Self::Item) -> Acc,
2135 self.iter.fold(init, move |acc, item| { f(&item); fold(acc, item) })
2139 #[stable(feature = "rust1", since = "1.0.0")]
2140 impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
2141 where F: FnMut(&I::Item),
2144 fn next_back(&mut self) -> Option<I::Item> {
2145 let next = self.iter.next_back();
2146 self.do_inspect(next)
2150 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
2151 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2153 let f = &mut self.f;
2154 self.iter.try_rfold(init, move |acc, item| { f(&item); fold(acc, item) })
2158 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
2159 where Fold: FnMut(Acc, Self::Item) -> Acc,
2162 self.iter.rfold(init, move |acc, item| { f(&item); fold(acc, item) })
2166 #[stable(feature = "rust1", since = "1.0.0")]
2167 impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F>
2168 where F: FnMut(&I::Item)
2170 fn len(&self) -> usize {
2174 fn is_empty(&self) -> bool {
2175 self.iter.is_empty()
2179 #[stable(feature = "fused", since = "1.26.0")]
2180 impl<I: FusedIterator, F> FusedIterator for Inspect<I, F>
2181 where F: FnMut(&I::Item) {}
2183 /// An iterator adapter that produces output as long as the underlying
2184 /// iterator produces `Option::Some` values.
2185 pub(crate) struct OptionShunt<I> {
2190 impl<I, T> OptionShunt<I>
2192 I: Iterator<Item = Option<T>>,
2194 /// Process the given iterator as if it yielded a `T` instead of a
2195 /// `Option<T>`. Any `None` value will stop the inner iterator and
2196 /// the overall result will be a `None`.
2197 pub fn process<F, U>(iter: I, mut f: F) -> Option<U>
2199 F: FnMut(&mut Self) -> U,
2201 let mut shunt = OptionShunt::new(iter);
2202 let value = f(shunt.by_ref());
2203 shunt.reconstruct(value)
2206 fn new(iter: I) -> Self {
2209 exited_early: false,
2213 /// Consume the adapter and rebuild a `Option` value.
2214 fn reconstruct<U>(self, val: U) -> Option<U> {
2215 if self.exited_early {
2223 impl<I, T> Iterator for OptionShunt<I>
2225 I: Iterator<Item = Option<T>>,
2229 fn next(&mut self) -> Option<Self::Item> {
2230 match self.iter.next() {
2231 Some(Some(v)) => Some(v),
2233 self.exited_early = true;
2240 fn size_hint(&self) -> (usize, Option<usize>) {
2241 if self.exited_early {
2244 let (_, upper) = self.iter.size_hint();
2250 /// An iterator adapter that produces output as long as the underlying
2251 /// iterator produces `Result::Ok` values.
2253 /// If an error is encountered, the iterator stops and the error is
2254 /// stored. The error may be recovered later via `reconstruct`.
2255 pub(crate) struct ResultShunt<I, E> {
2260 impl<I, T, E> ResultShunt<I, E>
2261 where I: Iterator<Item = Result<T, E>>
2263 /// Process the given iterator as if it yielded a `T` instead of a
2264 /// `Result<T, _>`. Any errors will stop the inner iterator and
2265 /// the overall result will be an error.
2266 pub fn process<F, U>(iter: I, mut f: F) -> Result<U, E>
2267 where F: FnMut(&mut Self) -> U
2269 let mut shunt = ResultShunt::new(iter);
2270 let value = f(shunt.by_ref());
2271 shunt.reconstruct(value)
2274 fn new(iter: I) -> Self {
2281 /// Consume the adapter and rebuild a `Result` value. This should
2282 /// *always* be called, otherwise any potential error would be
2284 fn reconstruct<U>(self, val: U) -> Result<U, E> {
2292 impl<I, T, E> Iterator for ResultShunt<I, E>
2293 where I: Iterator<Item = Result<T, E>>
2297 fn next(&mut self) -> Option<Self::Item> {
2298 match self.iter.next() {
2299 Some(Ok(v)) => Some(v),
2301 self.error = Some(e);
2308 fn size_hint(&self) -> (usize, Option<usize>) {
2309 if self.error.is_some() {
2312 let (_, upper) = self.iter.size_hint();