4 use crate::ops
::{Add, AddAssign, ControlFlow, Try}
;
8 DoubleEndedIterator
, ExactSizeIterator
, FusedIterator
, InPlaceIterable
, Iterator
, TrustedLen
,
16 pub use self::chain
::Chain
;
17 #[stable(feature = "rust1", since = "1.0.0")]
18 pub use self::flatten
::{FlatMap, Flatten}
;
19 pub use self::fuse
::Fuse
;
20 use self::zip
::try_get_unchecked
;
21 #[unstable(feature = "trusted_random_access", issue = "none")]
22 pub use self::zip
::TrustedRandomAccess
;
23 pub use self::zip
::Zip
;
25 /// This trait provides transitive access to source-stage in an interator-adapter pipeline
26 /// under the conditions that
27 /// * the iterator source `S` itself implements `SourceIter<Source = S>`
28 /// * there is a delegating implementation of this trait for each adapter in the pipeline between
29 /// the source and the pipeline consumer.
31 /// When the source is an owning iterator struct (commonly called `IntoIter`) then
32 /// this can be useful for specializing [`FromIterator`] implementations or recovering the
33 /// remaining elements after an iterator has been partially exhausted.
35 /// Note that implementations do not necessarily have to provide access to the inner-most
36 /// source of a pipeline. A stateful intermediate adapter might eagerly evaluate a part
37 /// of the pipeline and expose its internal storage as source.
39 /// The trait is unsafe because implementers must uphold additional safety properties.
40 /// See [`as_inner`] for details.
44 /// Retrieving a partially consumed source:
47 /// # #![feature(inplace_iteration)]
48 /// # use std::iter::SourceIter;
50 /// let mut iter = vec![9, 9, 9].into_iter().map(|i| i * i);
51 /// let _ = iter.next();
52 /// let mut remainder = std::mem::replace(unsafe { iter.as_inner() }, Vec::new().into_iter());
53 /// println!("n = {} elements remaining", remainder.len());
56 /// [`FromIterator`]: crate::iter::FromIterator
57 /// [`as_inner`]: SourceIter::as_inner
58 #[unstable(issue = "none", feature = "inplace_iteration")]
59 pub unsafe trait SourceIter
{
60 /// A source stage in an iterator pipeline.
61 type Source
: Iterator
;
63 /// Retrieve the source of an iterator pipeline.
67 /// Implementations of must return the same mutable reference for their lifetime, unless
68 /// replaced by a caller.
69 /// Callers may only replace the reference when they stopped iteration and drop the
70 /// iterator pipeline after extracting the source.
72 /// This means iterator adapters can rely on the source not changing during
73 /// iteration but they cannot rely on it in their Drop implementations.
75 /// Implementing this method means adapters relinquish private-only access to their
76 /// source and can only rely on guarantees made based on method receiver types.
77 /// The lack of restricted access also requires that adapters must uphold the source's
78 /// public API even when they have access to its internals.
80 /// Callers in turn must expect the source to be in any state that is consistent with
81 /// its public API since adapters sitting between it and the source have the same
82 /// access. In particular an adapter may have consumed more elements than strictly necessary.
84 /// The overall goal of these requirements is to let the consumer of a pipeline use
85 /// * whatever remains in the source after iteration has stopped
86 /// * the memory that has become unused by advancing a consuming iterator
88 /// [`next()`]: trait.Iterator.html#method.next
89 unsafe fn as_inner(&mut self) -> &mut Self::Source
;
92 /// A double-ended iterator with the direction inverted.
94 /// This `struct` is created by the [`rev`] method on [`Iterator`]. See its
95 /// documentation for more.
97 /// [`rev`]: trait.Iterator.html#method.rev
98 /// [`Iterator`]: trait.Iterator.html
99 #[derive(Clone, Debug)]
100 #[must_use = "iterators are lazy and do nothing unless consumed"]
101 #[stable(feature = "rust1", since = "1.0.0")]
106 pub(super) fn new(iter
: T
) -> Rev
<T
> {
111 #[stable(feature = "rust1", since = "1.0.0")]
112 impl<I
> Iterator
for Rev
<I
>
114 I
: DoubleEndedIterator
,
116 type Item
= <I
as Iterator
>::Item
;
119 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> {
120 self.iter
.next_back()
123 fn size_hint(&self) -> (usize, Option
<usize>) {
124 self.iter
.size_hint()
128 fn advance_by(&mut self, n
: usize) -> Result
<(), usize> {
129 self.iter
.advance_back_by(n
)
133 fn nth(&mut self, n
: usize) -> Option
<<I
as Iterator
>::Item
> {
134 self.iter
.nth_back(n
)
137 fn try_fold
<B
, F
, R
>(&mut self, init
: B
, f
: F
) -> R
140 F
: FnMut(B
, Self::Item
) -> R
,
143 self.iter
.try_rfold(init
, f
)
146 fn fold
<Acc
, F
>(self, init
: Acc
, f
: F
) -> Acc
148 F
: FnMut(Acc
, Self::Item
) -> Acc
,
150 self.iter
.rfold(init
, f
)
154 fn find
<P
>(&mut self, predicate
: P
) -> Option
<Self::Item
>
156 P
: FnMut(&Self::Item
) -> bool
,
158 self.iter
.rfind(predicate
)
162 #[stable(feature = "rust1", since = "1.0.0")]
163 impl<I
> DoubleEndedIterator
for Rev
<I
>
165 I
: DoubleEndedIterator
,
168 fn next_back(&mut self) -> Option
<<I
as Iterator
>::Item
> {
173 fn advance_back_by(&mut self, n
: usize) -> Result
<(), usize> {
174 self.iter
.advance_by(n
)
178 fn nth_back(&mut self, n
: usize) -> Option
<<I
as Iterator
>::Item
> {
182 fn try_rfold
<B
, F
, R
>(&mut self, init
: B
, f
: F
) -> R
185 F
: FnMut(B
, Self::Item
) -> R
,
188 self.iter
.try_fold(init
, f
)
191 fn rfold
<Acc
, F
>(self, init
: Acc
, f
: F
) -> Acc
193 F
: FnMut(Acc
, Self::Item
) -> Acc
,
195 self.iter
.fold(init
, f
)
198 fn rfind
<P
>(&mut self, predicate
: P
) -> Option
<Self::Item
>
200 P
: FnMut(&Self::Item
) -> bool
,
202 self.iter
.find(predicate
)
206 #[stable(feature = "rust1", since = "1.0.0")]
207 impl<I
> ExactSizeIterator
for Rev
<I
>
209 I
: ExactSizeIterator
+ DoubleEndedIterator
,
211 fn len(&self) -> usize {
215 fn is_empty(&self) -> bool
{
220 #[stable(feature = "fused", since = "1.26.0")]
221 impl<I
> FusedIterator
for Rev
<I
> where I
: FusedIterator
+ DoubleEndedIterator {}
223 #[unstable(feature = "trusted_len", issue = "37572")]
224 unsafe impl<I
> TrustedLen
for Rev
<I
> where I
: TrustedLen
+ DoubleEndedIterator {}
226 /// An iterator that copies the elements of an underlying iterator.
228 /// This `struct` is created by the [`copied`] method on [`Iterator`]. See its
229 /// documentation for more.
231 /// [`copied`]: trait.Iterator.html#method.copied
232 /// [`Iterator`]: trait.Iterator.html
233 #[stable(feature = "iter_copied", since = "1.36.0")]
234 #[must_use = "iterators are lazy and do nothing unless consumed"]
235 #[derive(Clone, Debug)]
236 pub struct Copied
<I
> {
241 pub(super) fn new(it
: I
) -> Copied
<I
> {
246 fn copy_fold
<T
: Copy
, Acc
>(mut f
: impl FnMut(Acc
, T
) -> Acc
) -> impl FnMut(Acc
, &T
) -> Acc
{
247 move |acc
, &elt
| f(acc
, elt
)
250 fn copy_try_fold
<T
: Copy
, Acc
, R
>(mut f
: impl FnMut(Acc
, T
) -> R
) -> impl FnMut(Acc
, &T
) -> R
{
251 move |acc
, &elt
| f(acc
, elt
)
254 #[stable(feature = "iter_copied", since = "1.36.0")]
255 impl<'a
, I
, T
: 'a
> Iterator
for Copied
<I
>
257 I
: Iterator
<Item
= &'a T
>,
262 fn next(&mut self) -> Option
<T
> {
263 self.it
.next().copied()
266 fn size_hint(&self) -> (usize, Option
<usize>) {
270 fn try_fold
<B
, F
, R
>(&mut self, init
: B
, f
: F
) -> R
273 F
: FnMut(B
, Self::Item
) -> R
,
276 self.it
.try_fold(init
, copy_try_fold(f
))
279 fn fold
<Acc
, F
>(self, init
: Acc
, f
: F
) -> Acc
281 F
: FnMut(Acc
, Self::Item
) -> Acc
,
283 self.it
.fold(init
, copy_fold(f
))
286 fn nth(&mut self, n
: usize) -> Option
<T
> {
287 self.it
.nth(n
).copied()
290 fn last(self) -> Option
<T
> {
291 self.it
.last().copied()
294 fn count(self) -> usize {
298 unsafe fn __iterator_get_unchecked(&mut self, idx
: usize) -> T
300 Self: TrustedRandomAccess
,
302 // SAFETY: the caller must uphold the contract for
303 // `Iterator::__iterator_get_unchecked`.
304 *unsafe { try_get_unchecked(&mut self.it, idx) }
308 #[stable(feature = "iter_copied", since = "1.36.0")]
309 impl<'a
, I
, T
: 'a
> DoubleEndedIterator
for Copied
<I
>
311 I
: DoubleEndedIterator
<Item
= &'a T
>,
314 fn next_back(&mut self) -> Option
<T
> {
315 self.it
.next_back().copied()
318 fn try_rfold
<B
, F
, R
>(&mut self, init
: B
, f
: F
) -> R
321 F
: FnMut(B
, Self::Item
) -> R
,
324 self.it
.try_rfold(init
, copy_try_fold(f
))
327 fn rfold
<Acc
, F
>(self, init
: Acc
, f
: F
) -> Acc
329 F
: FnMut(Acc
, Self::Item
) -> Acc
,
331 self.it
.rfold(init
, copy_fold(f
))
335 #[stable(feature = "iter_copied", since = "1.36.0")]
336 impl<'a
, I
, T
: 'a
> ExactSizeIterator
for Copied
<I
>
338 I
: ExactSizeIterator
<Item
= &'a T
>,
341 fn len(&self) -> usize {
345 fn is_empty(&self) -> bool
{
350 #[stable(feature = "iter_copied", since = "1.36.0")]
351 impl<'a
, I
, T
: 'a
> FusedIterator
for Copied
<I
>
353 I
: FusedIterator
<Item
= &'a T
>,
359 #[unstable(feature = "trusted_random_access", issue = "none")]
360 unsafe impl<I
> TrustedRandomAccess
for Copied
<I
>
362 I
: TrustedRandomAccess
,
365 fn may_have_side_effect() -> bool
{
366 I
::may_have_side_effect()
370 #[stable(feature = "iter_copied", since = "1.36.0")]
371 unsafe impl<'a
, I
, T
: 'a
> TrustedLen
for Copied
<I
>
373 I
: TrustedLen
<Item
= &'a T
>,
378 /// An iterator that clones the elements of an underlying iterator.
380 /// This `struct` is created by the [`cloned`] method on [`Iterator`]. See its
381 /// documentation for more.
383 /// [`cloned`]: trait.Iterator.html#method.cloned
384 /// [`Iterator`]: trait.Iterator.html
385 #[stable(feature = "iter_cloned", since = "1.1.0")]
386 #[must_use = "iterators are lazy and do nothing unless consumed"]
387 #[derive(Clone, Debug)]
388 pub struct Cloned
<I
> {
392 pub(super) fn new(it
: I
) -> Cloned
<I
> {
397 fn clone_try_fold
<T
: Clone
, Acc
, R
>(mut f
: impl FnMut(Acc
, T
) -> R
) -> impl FnMut(Acc
, &T
) -> R
{
398 move |acc
, elt
| f(acc
, elt
.clone())
401 #[stable(feature = "iter_cloned", since = "1.1.0")]
402 impl<'a
, I
, T
: 'a
> Iterator
for Cloned
<I
>
404 I
: Iterator
<Item
= &'a T
>,
409 fn next(&mut self) -> Option
<T
> {
410 self.it
.next().cloned()
413 fn size_hint(&self) -> (usize, Option
<usize>) {
417 fn try_fold
<B
, F
, R
>(&mut self, init
: B
, f
: F
) -> R
420 F
: FnMut(B
, Self::Item
) -> R
,
423 self.it
.try_fold(init
, clone_try_fold(f
))
426 fn fold
<Acc
, F
>(self, init
: Acc
, f
: F
) -> Acc
428 F
: FnMut(Acc
, Self::Item
) -> Acc
,
430 self.it
.map(T
::clone
).fold(init
, f
)
433 unsafe fn __iterator_get_unchecked(&mut self, idx
: usize) -> T
435 Self: TrustedRandomAccess
,
437 // SAFETY: the caller must uphold the contract for
438 // `Iterator::__iterator_get_unchecked`.
439 unsafe { try_get_unchecked(&mut self.it, idx).clone() }
443 #[stable(feature = "iter_cloned", since = "1.1.0")]
444 impl<'a
, I
, T
: 'a
> DoubleEndedIterator
for Cloned
<I
>
446 I
: DoubleEndedIterator
<Item
= &'a T
>,
449 fn next_back(&mut self) -> Option
<T
> {
450 self.it
.next_back().cloned()
453 fn try_rfold
<B
, F
, R
>(&mut self, init
: B
, f
: F
) -> R
456 F
: FnMut(B
, Self::Item
) -> R
,
459 self.it
.try_rfold(init
, clone_try_fold(f
))
462 fn rfold
<Acc
, F
>(self, init
: Acc
, f
: F
) -> Acc
464 F
: FnMut(Acc
, Self::Item
) -> Acc
,
466 self.it
.map(T
::clone
).rfold(init
, f
)
470 #[stable(feature = "iter_cloned", since = "1.1.0")]
471 impl<'a
, I
, T
: 'a
> ExactSizeIterator
for Cloned
<I
>
473 I
: ExactSizeIterator
<Item
= &'a T
>,
476 fn len(&self) -> usize {
480 fn is_empty(&self) -> bool
{
485 #[stable(feature = "fused", since = "1.26.0")]
486 impl<'a
, I
, T
: 'a
> FusedIterator
for Cloned
<I
>
488 I
: FusedIterator
<Item
= &'a T
>,
494 #[unstable(feature = "trusted_random_access", issue = "none")]
495 unsafe impl<I
> TrustedRandomAccess
for Cloned
<I
>
497 I
: TrustedRandomAccess
,
500 fn may_have_side_effect() -> bool
{
505 #[unstable(feature = "trusted_len", issue = "37572")]
506 unsafe impl<'a
, I
, T
: 'a
> TrustedLen
for Cloned
<I
>
508 I
: TrustedLen
<Item
= &'a T
>,
513 /// An iterator that repeats endlessly.
515 /// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its
516 /// documentation for more.
518 /// [`cycle`]: trait.Iterator.html#method.cycle
519 /// [`Iterator`]: trait.Iterator.html
520 #[derive(Clone, Debug)]
521 #[must_use = "iterators are lazy and do nothing unless consumed"]
522 #[stable(feature = "rust1", since = "1.0.0")]
523 pub struct Cycle
<I
> {
527 impl<I
: Clone
> Cycle
<I
> {
528 pub(super) fn new(iter
: I
) -> Cycle
<I
> {
529 Cycle { orig: iter.clone(), iter }
533 #[stable(feature = "rust1", since = "1.0.0")]
534 impl<I
> Iterator
for Cycle
<I
>
538 type Item
= <I
as Iterator
>::Item
;
541 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> {
542 match self.iter
.next() {
544 self.iter
= self.orig
.clone();
552 fn size_hint(&self) -> (usize, Option
<usize>) {
553 // the cycle iterator is either empty or infinite
554 match self.orig
.size_hint() {
555 sz @
(0, Some(0)) => sz
,
557 _
=> (usize::MAX
, None
),
562 fn try_fold
<Acc
, F
, R
>(&mut self, mut acc
: Acc
, mut f
: F
) -> R
564 F
: FnMut(Acc
, Self::Item
) -> R
,
567 // fully iterate the current iterator. this is necessary because
568 // `self.iter` may be empty even when `self.orig` isn't
569 acc
= self.iter
.try_fold(acc
, &mut f
)?
;
570 self.iter
= self.orig
.clone();
572 // complete a full cycle, keeping track of whether the cycled
573 // iterator is empty or not. we need to return early in case
574 // of an empty iterator to prevent an infinite loop
575 let mut is_empty
= true;
576 acc
= self.iter
.try_fold(acc
, |acc
, x
| {
582 return Try
::from_ok(acc
);
586 self.iter
= self.orig
.clone();
587 acc
= self.iter
.try_fold(acc
, &mut f
)?
;
591 // No `fold` override, because `fold` doesn't make much sense for `Cycle`,
592 // and we can't do anything better than the default.
595 #[stable(feature = "fused", since = "1.26.0")]
596 impl<I
> FusedIterator
for Cycle
<I
> where I
: Clone
+ Iterator {}
598 /// An iterator for stepping iterators by a custom amount.
600 /// This `struct` is created by the [`step_by`] method on [`Iterator`]. See
601 /// its documentation for more.
603 /// [`step_by`]: trait.Iterator.html#method.step_by
604 /// [`Iterator`]: trait.Iterator.html
605 #[must_use = "iterators are lazy and do nothing unless consumed"]
606 #[stable(feature = "iterator_step_by", since = "1.28.0")]
607 #[derive(Clone, Debug)]
608 pub struct StepBy
<I
> {
614 pub(super) fn new(iter
: I
, step
: usize) -> StepBy
<I
> {
616 StepBy { iter, step: step - 1, first_take: true }
620 #[stable(feature = "iterator_step_by", since = "1.28.0")]
621 impl<I
> Iterator
for StepBy
<I
>
628 fn next(&mut self) -> Option
<Self::Item
> {
630 self.first_take
= false;
633 self.iter
.nth(self.step
)
638 fn size_hint(&self) -> (usize, Option
<usize>) {
640 fn first_size(step
: usize) -> impl Fn(usize) -> usize {
641 move |n
| if n
== 0 { 0 }
else { 1 + (n - 1) / (step + 1) }
645 fn other_size(step
: usize) -> impl Fn(usize) -> usize {
646 move |n
| n
/ (step
+ 1)
649 let (low
, high
) = self.iter
.size_hint();
652 let f
= first_size(self.step
);
653 (f(low
), high
.map(f
))
655 let f
= other_size(self.step
);
656 (f(low
), high
.map(f
))
661 fn nth(&mut self, mut n
: usize) -> Option
<Self::Item
> {
663 self.first_take
= false;
664 let first
= self.iter
.next();
670 // n and self.step are indices, we need to add 1 to get the amount of elements
671 // When calling `.nth`, we need to subtract 1 again to convert back to an index
672 // step + 1 can't overflow because `.step_by` sets `self.step` to `step - 1`
673 let mut step
= self.step
+ 1;
674 // n + 1 could overflow
675 // thus, if n is usize::MAX, instead of adding one, we call .nth(step)
677 self.iter
.nth(step
- 1);
684 let mul
= n
.checked_mul(step
);
686 if intrinsics
::likely(mul
.is_some()) {
687 return self.iter
.nth(mul
.unwrap() - 1);
690 let div_n
= usize::MAX
/ n
;
691 let div_step
= usize::MAX
/ step
;
692 let nth_n
= div_n
* n
;
693 let nth_step
= div_step
* step
;
694 let nth
= if nth_n
> nth_step
{
701 self.iter
.nth(nth
- 1);
705 fn try_fold
<Acc
, F
, R
>(&mut self, mut acc
: Acc
, mut f
: F
) -> R
707 F
: FnMut(Acc
, Self::Item
) -> R
,
711 fn nth
<I
: Iterator
>(iter
: &mut I
, step
: usize) -> impl FnMut() -> Option
<I
::Item
> + '_
{
712 move || iter
.nth(step
)
716 self.first_take
= false;
717 match self.iter
.next() {
718 None
=> return Try
::from_ok(acc
),
719 Some(x
) => acc
= f(acc
, x
)?
,
722 from_fn(nth(&mut self.iter
, self.step
)).try_fold(acc
, f
)
725 fn fold
<Acc
, F
>(mut self, mut acc
: Acc
, mut f
: F
) -> Acc
727 F
: FnMut(Acc
, Self::Item
) -> Acc
,
730 fn nth
<I
: Iterator
>(iter
: &mut I
, step
: usize) -> impl FnMut() -> Option
<I
::Item
> + '_
{
731 move || iter
.nth(step
)
735 self.first_take
= false;
736 match self.iter
.next() {
738 Some(x
) => acc
= f(acc
, x
),
741 from_fn(nth(&mut self.iter
, self.step
)).fold(acc
, f
)
747 I
: ExactSizeIterator
,
749 // The zero-based index starting from the end of the iterator of the
750 // last element. Used in the `DoubleEndedIterator` implementation.
751 fn next_back_index(&self) -> usize {
752 let rem
= self.iter
.len() % (self.step
+ 1);
754 if rem
== 0 { self.step }
else { rem - 1 }
761 #[stable(feature = "double_ended_step_by_iterator", since = "1.38.0")]
762 impl<I
> DoubleEndedIterator
for StepBy
<I
>
764 I
: DoubleEndedIterator
+ ExactSizeIterator
,
767 fn next_back(&mut self) -> Option
<Self::Item
> {
768 self.iter
.nth_back(self.next_back_index())
772 fn nth_back(&mut self, n
: usize) -> Option
<Self::Item
> {
773 // `self.iter.nth_back(usize::MAX)` does the right thing here when `n`
774 // is out of bounds because the length of `self.iter` does not exceed
775 // `usize::MAX` (because `I: ExactSizeIterator`) and `nth_back` is
777 let n
= n
.saturating_mul(self.step
+ 1).saturating_add(self.next_back_index());
778 self.iter
.nth_back(n
)
781 fn try_rfold
<Acc
, F
, R
>(&mut self, init
: Acc
, mut f
: F
) -> R
783 F
: FnMut(Acc
, Self::Item
) -> R
,
787 fn nth_back
<I
: DoubleEndedIterator
>(
790 ) -> impl FnMut() -> Option
<I
::Item
> + '_
{
791 move || iter
.nth_back(step
)
794 match self.next_back() {
795 None
=> Try
::from_ok(init
),
797 let acc
= f(init
, x
)?
;
798 from_fn(nth_back(&mut self.iter
, self.step
)).try_fold(acc
, f
)
804 fn rfold
<Acc
, F
>(mut self, init
: Acc
, mut f
: F
) -> Acc
807 F
: FnMut(Acc
, Self::Item
) -> Acc
,
810 fn nth_back
<I
: DoubleEndedIterator
>(
813 ) -> impl FnMut() -> Option
<I
::Item
> + '_
{
814 move || iter
.nth_back(step
)
817 match self.next_back() {
820 let acc
= f(init
, x
);
821 from_fn(nth_back(&mut self.iter
, self.step
)).fold(acc
, f
)
827 // StepBy can only make the iterator shorter, so the len will still fit.
828 #[stable(feature = "iterator_step_by", since = "1.28.0")]
829 impl<I
> ExactSizeIterator
for StepBy
<I
> where I
: ExactSizeIterator {}
831 /// An iterator that maps the values of `iter` with `f`.
833 /// This `struct` is created by the [`map`] method on [`Iterator`]. See its
834 /// documentation for more.
836 /// [`map`]: trait.Iterator.html#method.map
837 /// [`Iterator`]: trait.Iterator.html
839 /// # Notes about side effects
841 /// The [`map`] iterator implements [`DoubleEndedIterator`], meaning that
842 /// you can also [`map`] backwards:
845 /// let v: Vec<i32> = vec![1, 2, 3].into_iter().map(|x| x + 1).rev().collect();
847 /// assert_eq!(v, [4, 3, 2]);
850 /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
852 /// But if your closure has state, iterating backwards may act in a way you do
853 /// not expect. Let's go through an example. First, in the forward direction:
858 /// for pair in vec!['a', 'b', 'c'].into_iter()
859 /// .map(|letter| { c += 1; (letter, c) }) {
860 /// println!("{:?}", pair);
864 /// This will print "('a', 1), ('b', 2), ('c', 3)".
866 /// Now consider this twist where we add a call to `rev`. This version will
867 /// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed,
868 /// but the values of the counter still go in order. This is because `map()` is
869 /// still being called lazily on each item, but we are popping items off the
870 /// back of the vector now, instead of shifting them from the front.
875 /// for pair in vec!['a', 'b', 'c'].into_iter()
876 /// .map(|letter| { c += 1; (letter, c) })
878 /// println!("{:?}", pair);
881 #[must_use = "iterators are lazy and do nothing unless consumed"]
882 #[stable(feature = "rust1", since = "1.0.0")]
884 pub struct Map
<I
, F
> {
888 impl<I
, F
> Map
<I
, F
> {
889 pub(super) fn new(iter
: I
, f
: F
) -> Map
<I
, F
> {
894 #[stable(feature = "core_impl_debug", since = "1.9.0")]
895 impl<I
: fmt
::Debug
, F
> fmt
::Debug
for Map
<I
, F
> {
896 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
897 f
.debug_struct("Map").field("iter", &self.iter
).finish()
901 fn map_fold
<T
, B
, Acc
>(
902 mut f
: impl FnMut(T
) -> B
,
903 mut g
: impl FnMut(Acc
, B
) -> Acc
,
904 ) -> impl FnMut(Acc
, T
) -> Acc
{
905 move |acc
, elt
| g(acc
, f(elt
))
908 fn map_try_fold
<'a
, T
, B
, Acc
, R
>(
909 f
: &'a
mut impl FnMut(T
) -> B
,
910 mut g
: impl FnMut(Acc
, B
) -> R
+ 'a
,
911 ) -> impl FnMut(Acc
, T
) -> R
+ 'a
{
912 move |acc
, elt
| g(acc
, f(elt
))
915 #[stable(feature = "rust1", since = "1.0.0")]
916 impl<B
, I
: Iterator
, F
> Iterator
for Map
<I
, F
>
918 F
: FnMut(I
::Item
) -> B
,
923 fn next(&mut self) -> Option
<B
> {
924 self.iter
.next().map(&mut self.f
)
928 fn size_hint(&self) -> (usize, Option
<usize>) {
929 self.iter
.size_hint()
932 fn try_fold
<Acc
, G
, R
>(&mut self, init
: Acc
, g
: G
) -> R
935 G
: FnMut(Acc
, Self::Item
) -> R
,
938 self.iter
.try_fold(init
, map_try_fold(&mut self.f
, g
))
941 fn fold
<Acc
, G
>(self, init
: Acc
, g
: G
) -> Acc
943 G
: FnMut(Acc
, Self::Item
) -> Acc
,
945 self.iter
.fold(init
, map_fold(self.f
, g
))
948 unsafe fn __iterator_get_unchecked(&mut self, idx
: usize) -> B
950 Self: TrustedRandomAccess
,
952 // SAFETY: the caller must uphold the contract for
953 // `Iterator::__iterator_get_unchecked`.
954 unsafe { (self.f)(try_get_unchecked(&mut self.iter, idx)) }
958 #[stable(feature = "rust1", since = "1.0.0")]
959 impl<B
, I
: DoubleEndedIterator
, F
> DoubleEndedIterator
for Map
<I
, F
>
961 F
: FnMut(I
::Item
) -> B
,
964 fn next_back(&mut self) -> Option
<B
> {
965 self.iter
.next_back().map(&mut self.f
)
968 fn try_rfold
<Acc
, G
, R
>(&mut self, init
: Acc
, g
: G
) -> R
971 G
: FnMut(Acc
, Self::Item
) -> R
,
974 self.iter
.try_rfold(init
, map_try_fold(&mut self.f
, g
))
977 fn rfold
<Acc
, G
>(self, init
: Acc
, g
: G
) -> Acc
979 G
: FnMut(Acc
, Self::Item
) -> Acc
,
981 self.iter
.rfold(init
, map_fold(self.f
, g
))
985 #[stable(feature = "rust1", since = "1.0.0")]
986 impl<B
, I
: ExactSizeIterator
, F
> ExactSizeIterator
for Map
<I
, F
>
988 F
: FnMut(I
::Item
) -> B
,
990 fn len(&self) -> usize {
994 fn is_empty(&self) -> bool
{
999 #[stable(feature = "fused", since = "1.26.0")]
1000 impl<B
, I
: FusedIterator
, F
> FusedIterator
for Map
<I
, F
> where F
: FnMut(I
::Item
) -> B {}
1002 #[unstable(feature = "trusted_len", issue = "37572")]
1003 unsafe impl<B
, I
, F
> TrustedLen
for Map
<I
, F
>
1006 F
: FnMut(I
::Item
) -> B
,
1011 #[unstable(feature = "trusted_random_access", issue = "none")]
1012 unsafe impl<I
, F
> TrustedRandomAccess
for Map
<I
, F
>
1014 I
: TrustedRandomAccess
,
1017 fn may_have_side_effect() -> bool
{
1022 #[unstable(issue = "none", feature = "inplace_iteration")]
1023 unsafe impl<S
: Iterator
, B
, I
: Iterator
, F
> SourceIter
for Map
<I
, F
>
1025 F
: FnMut(I
::Item
) -> B
,
1026 I
: SourceIter
<Source
= S
>,
1031 unsafe fn as_inner(&mut self) -> &mut S
{
1032 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
1033 unsafe { SourceIter::as_inner(&mut self.iter) }
1037 #[unstable(issue = "none", feature = "inplace_iteration")]
1038 unsafe impl<B
, I
: InPlaceIterable
, F
> InPlaceIterable
for Map
<I
, F
> where F
: FnMut(I
::Item
) -> B {}
1040 /// An iterator that filters the elements of `iter` with `predicate`.
1042 /// This `struct` is created by the [`filter`] method on [`Iterator`]. See its
1043 /// documentation for more.
1045 /// [`filter`]: trait.Iterator.html#method.filter
1046 /// [`Iterator`]: trait.Iterator.html
1047 #[must_use = "iterators are lazy and do nothing unless consumed"]
1048 #[stable(feature = "rust1", since = "1.0.0")]
1050 pub struct Filter
<I
, P
> {
1054 impl<I
, P
> Filter
<I
, P
> {
1055 pub(super) fn new(iter
: I
, predicate
: P
) -> Filter
<I
, P
> {
1056 Filter { iter, predicate }
1060 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1061 impl<I
: fmt
::Debug
, P
> fmt
::Debug
for Filter
<I
, P
> {
1062 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1063 f
.debug_struct("Filter").field("iter", &self.iter
).finish()
1067 fn filter_fold
<T
, Acc
>(
1068 mut predicate
: impl FnMut(&T
) -> bool
,
1069 mut fold
: impl FnMut(Acc
, T
) -> Acc
,
1070 ) -> impl FnMut(Acc
, T
) -> Acc
{
1071 move |acc
, item
| if predicate(&item
) { fold(acc, item) }
else { acc }
1074 fn filter_try_fold
<'a
, T
, Acc
, R
: Try
<Ok
= Acc
>>(
1075 predicate
: &'a
mut impl FnMut(&T
) -> bool
,
1076 mut fold
: impl FnMut(Acc
, T
) -> R
+ 'a
,
1077 ) -> impl FnMut(Acc
, T
) -> R
+ 'a
{
1078 move |acc
, item
| if predicate(&item
) { fold(acc, item) }
else { R::from_ok(acc) }
1081 #[stable(feature = "rust1", since = "1.0.0")]
1082 impl<I
: Iterator
, P
> Iterator
for Filter
<I
, P
>
1084 P
: FnMut(&I
::Item
) -> bool
,
1086 type Item
= I
::Item
;
1089 fn next(&mut self) -> Option
<I
::Item
> {
1090 self.iter
.find(&mut self.predicate
)
1094 fn size_hint(&self) -> (usize, Option
<usize>) {
1095 let (_
, upper
) = self.iter
.size_hint();
1096 (0, upper
) // can't know a lower bound, due to the predicate
1099 // this special case allows the compiler to make `.filter(_).count()`
1100 // branchless. Barring perfect branch prediction (which is unattainable in
1101 // the general case), this will be much faster in >90% of cases (containing
1102 // virtually all real workloads) and only a tiny bit slower in the rest.
1104 // Having this specialization thus allows us to write `.filter(p).count()`
1105 // where we would otherwise write `.map(|x| p(x) as usize).sum()`, which is
1106 // less readable and also less backwards-compatible to Rust before 1.10.
1108 // Using the branchless version will also simplify the LLVM byte code, thus
1109 // leaving more budget for LLVM optimizations.
1111 fn count(self) -> usize {
1113 fn to_usize
<T
>(mut predicate
: impl FnMut(&T
) -> bool
) -> impl FnMut(T
) -> usize {
1114 move |x
| predicate(&x
) as usize
1117 self.iter
.map(to_usize(self.predicate
)).sum()
1121 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
1124 Fold
: FnMut(Acc
, Self::Item
) -> R
,
1127 self.iter
.try_fold(init
, filter_try_fold(&mut self.predicate
, fold
))
1131 fn fold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
1133 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
1135 self.iter
.fold(init
, filter_fold(self.predicate
, fold
))
1139 #[stable(feature = "rust1", since = "1.0.0")]
1140 impl<I
: DoubleEndedIterator
, P
> DoubleEndedIterator
for Filter
<I
, P
>
1142 P
: FnMut(&I
::Item
) -> bool
,
1145 fn next_back(&mut self) -> Option
<I
::Item
> {
1146 self.iter
.rfind(&mut self.predicate
)
1150 fn try_rfold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
1153 Fold
: FnMut(Acc
, Self::Item
) -> R
,
1156 self.iter
.try_rfold(init
, filter_try_fold(&mut self.predicate
, fold
))
1160 fn rfold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
1162 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
1164 self.iter
.rfold(init
, filter_fold(self.predicate
, fold
))
1168 #[stable(feature = "fused", since = "1.26.0")]
1169 impl<I
: FusedIterator
, P
> FusedIterator
for Filter
<I
, P
> where P
: FnMut(&I
::Item
) -> bool {}
1171 #[unstable(issue = "none", feature = "inplace_iteration")]
1172 unsafe impl<S
: Iterator
, P
, I
: Iterator
> SourceIter
for Filter
<I
, P
>
1174 P
: FnMut(&I
::Item
) -> bool
,
1175 I
: SourceIter
<Source
= S
>,
1180 unsafe fn as_inner(&mut self) -> &mut S
{
1181 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
1182 unsafe { SourceIter::as_inner(&mut self.iter) }
1186 #[unstable(issue = "none", feature = "inplace_iteration")]
1187 unsafe impl<I
: InPlaceIterable
, P
> InPlaceIterable
for Filter
<I
, P
> where P
: FnMut(&I
::Item
) -> bool {}
1189 /// An iterator that uses `f` to both filter and map elements from `iter`.
1191 /// This `struct` is created by the [`filter_map`] method on [`Iterator`]. See its
1192 /// documentation for more.
1194 /// [`filter_map`]: trait.Iterator.html#method.filter_map
1195 /// [`Iterator`]: trait.Iterator.html
1196 #[must_use = "iterators are lazy and do nothing unless consumed"]
1197 #[stable(feature = "rust1", since = "1.0.0")]
1199 pub struct FilterMap
<I
, F
> {
1203 impl<I
, F
> FilterMap
<I
, F
> {
1204 pub(super) fn new(iter
: I
, f
: F
) -> FilterMap
<I
, F
> {
1205 FilterMap { iter, f }
1209 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1210 impl<I
: fmt
::Debug
, F
> fmt
::Debug
for FilterMap
<I
, F
> {
1211 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1212 f
.debug_struct("FilterMap").field("iter", &self.iter
).finish()
1216 fn filter_map_fold
<T
, B
, Acc
>(
1217 mut f
: impl FnMut(T
) -> Option
<B
>,
1218 mut fold
: impl FnMut(Acc
, B
) -> Acc
,
1219 ) -> impl FnMut(Acc
, T
) -> Acc
{
1220 move |acc
, item
| match f(item
) {
1221 Some(x
) => fold(acc
, x
),
1226 fn filter_map_try_fold
<'a
, T
, B
, Acc
, R
: Try
<Ok
= Acc
>>(
1227 f
: &'a
mut impl FnMut(T
) -> Option
<B
>,
1228 mut fold
: impl FnMut(Acc
, B
) -> R
+ 'a
,
1229 ) -> impl FnMut(Acc
, T
) -> R
+ 'a
{
1230 move |acc
, item
| match f(item
) {
1231 Some(x
) => fold(acc
, x
),
1232 None
=> R
::from_ok(acc
),
1236 #[stable(feature = "rust1", since = "1.0.0")]
1237 impl<B
, I
: Iterator
, F
> Iterator
for FilterMap
<I
, F
>
1239 F
: FnMut(I
::Item
) -> Option
<B
>,
1244 fn next(&mut self) -> Option
<B
> {
1245 self.iter
.find_map(&mut self.f
)
1249 fn size_hint(&self) -> (usize, Option
<usize>) {
1250 let (_
, upper
) = self.iter
.size_hint();
1251 (0, upper
) // can't know a lower bound, due to the predicate
1255 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
1258 Fold
: FnMut(Acc
, Self::Item
) -> R
,
1261 self.iter
.try_fold(init
, filter_map_try_fold(&mut self.f
, fold
))
1265 fn fold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
1267 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
1269 self.iter
.fold(init
, filter_map_fold(self.f
, fold
))
1273 #[stable(feature = "rust1", since = "1.0.0")]
1274 impl<B
, I
: DoubleEndedIterator
, F
> DoubleEndedIterator
for FilterMap
<I
, F
>
1276 F
: FnMut(I
::Item
) -> Option
<B
>,
1279 fn next_back(&mut self) -> Option
<B
> {
1282 f
: &mut impl FnMut(T
) -> Option
<B
>,
1283 ) -> impl FnMut((), T
) -> ControlFlow
<(), B
> + '_
{
1284 move |(), x
| match f(x
) {
1285 Some(x
) => ControlFlow
::Break(x
),
1286 None
=> ControlFlow
::CONTINUE
,
1290 self.iter
.try_rfold((), find(&mut self.f
)).break_value()
1294 fn try_rfold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
1297 Fold
: FnMut(Acc
, Self::Item
) -> R
,
1300 self.iter
.try_rfold(init
, filter_map_try_fold(&mut self.f
, fold
))
1304 fn rfold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
1306 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
1308 self.iter
.rfold(init
, filter_map_fold(self.f
, fold
))
1312 #[stable(feature = "fused", since = "1.26.0")]
1313 impl<B
, I
: FusedIterator
, F
> FusedIterator
for FilterMap
<I
, F
> where F
: FnMut(I
::Item
) -> Option
<B
> {}
1315 #[unstable(issue = "none", feature = "inplace_iteration")]
1316 unsafe impl<S
: Iterator
, B
, I
: Iterator
, F
> SourceIter
for FilterMap
<I
, F
>
1318 F
: FnMut(I
::Item
) -> Option
<B
>,
1319 I
: SourceIter
<Source
= S
>,
1324 unsafe fn as_inner(&mut self) -> &mut S
{
1325 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
1326 unsafe { SourceIter::as_inner(&mut self.iter) }
1330 #[unstable(issue = "none", feature = "inplace_iteration")]
1331 unsafe impl<B
, I
: InPlaceIterable
, F
> InPlaceIterable
for FilterMap
<I
, F
> where
1332 F
: FnMut(I
::Item
) -> Option
<B
>
1336 /// An iterator that yields the current count and the element during iteration.
1338 /// This `struct` is created by the [`enumerate`] method on [`Iterator`]. See its
1339 /// documentation for more.
1341 /// [`enumerate`]: trait.Iterator.html#method.enumerate
1342 /// [`Iterator`]: trait.Iterator.html
1343 #[derive(Clone, Debug)]
1344 #[must_use = "iterators are lazy and do nothing unless consumed"]
1345 #[stable(feature = "rust1", since = "1.0.0")]
1346 pub struct Enumerate
<I
> {
1350 impl<I
> Enumerate
<I
> {
1351 pub(super) fn new(iter
: I
) -> Enumerate
<I
> {
1352 Enumerate { iter, count: 0 }
1356 #[stable(feature = "rust1", since = "1.0.0")]
1357 impl<I
> Iterator
for Enumerate
<I
>
1361 type Item
= (usize, <I
as Iterator
>::Item
);
1363 /// # Overflow Behavior
1365 /// The method does no guarding against overflows, so enumerating more than
1366 /// `usize::MAX` elements either produces the wrong result or panics. If
1367 /// debug assertions are enabled, a panic is guaranteed.
1371 /// Might panic if the index of the element overflows a `usize`.
1373 fn next(&mut self) -> Option
<(usize, <I
as Iterator
>::Item
)> {
1374 let a
= self.iter
.next()?
;
1376 // Possible undefined overflow.
1377 AddAssign
::add_assign(&mut self.count
, 1);
1382 fn size_hint(&self) -> (usize, Option
<usize>) {
1383 self.iter
.size_hint()
1387 fn nth(&mut self, n
: usize) -> Option
<(usize, I
::Item
)> {
1388 let a
= self.iter
.nth(n
)?
;
1389 // Possible undefined overflow.
1390 let i
= Add
::add(self.count
, n
);
1391 self.count
= Add
::add(i
, 1);
1396 fn count(self) -> usize {
1401 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
1404 Fold
: FnMut(Acc
, Self::Item
) -> R
,
1408 fn enumerate
<'a
, T
, Acc
, R
>(
1409 count
: &'a
mut usize,
1410 mut fold
: impl FnMut(Acc
, (usize, T
)) -> R
+ 'a
,
1411 ) -> impl FnMut(Acc
, T
) -> R
+ 'a
{
1413 let acc
= fold(acc
, (*count
, item
));
1414 // Possible undefined overflow.
1415 AddAssign
::add_assign(count
, 1);
1420 self.iter
.try_fold(init
, enumerate(&mut self.count
, fold
))
1424 fn fold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
1426 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
1429 fn enumerate
<T
, Acc
>(
1431 mut fold
: impl FnMut(Acc
, (usize, T
)) -> Acc
,
1432 ) -> impl FnMut(Acc
, T
) -> Acc
{
1434 let acc
= fold(acc
, (count
, item
));
1435 // Possible undefined overflow.
1436 AddAssign
::add_assign(&mut count
, 1);
1441 self.iter
.fold(init
, enumerate(self.count
, fold
))
1444 unsafe fn __iterator_get_unchecked(&mut self, idx
: usize) -> <Self as Iterator
>::Item
1446 Self: TrustedRandomAccess
,
1448 // SAFETY: the caller must uphold the contract for
1449 // `Iterator::__iterator_get_unchecked`.
1450 let value
= unsafe { try_get_unchecked(&mut self.iter, idx) }
;
1451 (Add
::add(self.count
, idx
), value
)
1455 #[stable(feature = "rust1", since = "1.0.0")]
1456 impl<I
> DoubleEndedIterator
for Enumerate
<I
>
1458 I
: ExactSizeIterator
+ DoubleEndedIterator
,
1461 fn next_back(&mut self) -> Option
<(usize, <I
as Iterator
>::Item
)> {
1462 let a
= self.iter
.next_back()?
;
1463 let len
= self.iter
.len();
1464 // Can safely add, `ExactSizeIterator` promises that the number of
1465 // elements fits into a `usize`.
1466 Some((self.count
+ len
, a
))
1470 fn nth_back(&mut self, n
: usize) -> Option
<(usize, <I
as Iterator
>::Item
)> {
1471 let a
= self.iter
.nth_back(n
)?
;
1472 let len
= self.iter
.len();
1473 // Can safely add, `ExactSizeIterator` promises that the number of
1474 // elements fits into a `usize`.
1475 Some((self.count
+ len
, a
))
1479 fn try_rfold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
1482 Fold
: FnMut(Acc
, Self::Item
) -> R
,
1485 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1486 // that the number of elements fits into a `usize`.
1487 fn enumerate
<T
, Acc
, R
>(
1489 mut fold
: impl FnMut(Acc
, (usize, T
)) -> R
,
1490 ) -> impl FnMut(Acc
, T
) -> R
{
1493 fold(acc
, (count
, item
))
1497 let count
= self.count
+ self.iter
.len();
1498 self.iter
.try_rfold(init
, enumerate(count
, fold
))
1502 fn rfold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
1504 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
1506 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1507 // that the number of elements fits into a `usize`.
1508 fn enumerate
<T
, Acc
>(
1510 mut fold
: impl FnMut(Acc
, (usize, T
)) -> Acc
,
1511 ) -> impl FnMut(Acc
, T
) -> Acc
{
1514 fold(acc
, (count
, item
))
1518 let count
= self.count
+ self.iter
.len();
1519 self.iter
.rfold(init
, enumerate(count
, fold
))
1523 #[stable(feature = "rust1", since = "1.0.0")]
1524 impl<I
> ExactSizeIterator
for Enumerate
<I
>
1526 I
: ExactSizeIterator
,
1528 fn len(&self) -> usize {
1532 fn is_empty(&self) -> bool
{
1533 self.iter
.is_empty()
1538 #[unstable(feature = "trusted_random_access", issue = "none")]
1539 unsafe impl<I
> TrustedRandomAccess
for Enumerate
<I
>
1541 I
: TrustedRandomAccess
,
1543 fn may_have_side_effect() -> bool
{
1544 I
::may_have_side_effect()
1548 #[stable(feature = "fused", since = "1.26.0")]
1549 impl<I
> FusedIterator
for Enumerate
<I
> where I
: FusedIterator {}
1551 #[unstable(feature = "trusted_len", issue = "37572")]
1552 unsafe impl<I
> TrustedLen
for Enumerate
<I
> where I
: TrustedLen {}
1554 #[unstable(issue = "none", feature = "inplace_iteration")]
1555 unsafe impl<S
: Iterator
, I
: Iterator
> SourceIter
for Enumerate
<I
>
1557 I
: SourceIter
<Source
= S
>,
1562 unsafe fn as_inner(&mut self) -> &mut S
{
1563 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
1564 unsafe { SourceIter::as_inner(&mut self.iter) }
1568 #[unstable(issue = "none", feature = "inplace_iteration")]
1569 unsafe impl<I
: InPlaceIterable
> InPlaceIterable
for Enumerate
<I
> {}
1571 /// An iterator with a `peek()` that returns an optional reference to the next
1574 /// This `struct` is created by the [`peekable`] method on [`Iterator`]. See its
1575 /// documentation for more.
1577 /// [`peekable`]: trait.Iterator.html#method.peekable
1578 /// [`Iterator`]: trait.Iterator.html
1579 #[derive(Clone, Debug)]
1580 #[must_use = "iterators are lazy and do nothing unless consumed"]
1581 #[stable(feature = "rust1", since = "1.0.0")]
1582 pub struct Peekable
<I
: Iterator
> {
1584 /// Remember a peeked value, even if it was None.
1585 peeked
: Option
<Option
<I
::Item
>>,
1587 impl<I
: Iterator
> Peekable
<I
> {
1588 pub(super) fn new(iter
: I
) -> Peekable
<I
> {
1589 Peekable { iter, peeked: None }
1593 // Peekable must remember if a None has been seen in the `.peek()` method.
1594 // It ensures that `.peek(); .peek();` or `.peek(); .next();` only advances the
1595 // underlying iterator at most once. This does not by itself make the iterator
1597 #[stable(feature = "rust1", since = "1.0.0")]
1598 impl<I
: Iterator
> Iterator
for Peekable
<I
> {
1599 type Item
= I
::Item
;
1602 fn next(&mut self) -> Option
<I
::Item
> {
1603 match self.peeked
.take() {
1605 None
=> self.iter
.next(),
1610 #[rustc_inherit_overflow_checks]
1611 fn count(mut self) -> usize {
1612 match self.peeked
.take() {
1614 Some(Some(_
)) => 1 + self.iter
.count(),
1615 None
=> self.iter
.count(),
1620 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
1621 match self.peeked
.take() {
1623 Some(v @
Some(_
)) if n
== 0 => v
,
1624 Some(Some(_
)) => self.iter
.nth(n
- 1),
1625 None
=> self.iter
.nth(n
),
1630 fn last(mut self) -> Option
<I
::Item
> {
1631 let peek_opt
= match self.peeked
.take() {
1632 Some(None
) => return None
,
1636 self.iter
.last().or(peek_opt
)
1640 fn size_hint(&self) -> (usize, Option
<usize>) {
1641 let peek_len
= match self.peeked
{
1642 Some(None
) => return (0, Some(0)),
1646 let (lo
, hi
) = self.iter
.size_hint();
1647 let lo
= lo
.saturating_add(peek_len
);
1649 Some(x
) => x
.checked_add(peek_len
),
1656 fn try_fold
<B
, F
, R
>(&mut self, init
: B
, mut f
: F
) -> R
1659 F
: FnMut(B
, Self::Item
) -> R
,
1662 let acc
= match self.peeked
.take() {
1663 Some(None
) => return Try
::from_ok(init
),
1664 Some(Some(v
)) => f(init
, v
)?
,
1667 self.iter
.try_fold(acc
, f
)
1671 fn fold
<Acc
, Fold
>(self, init
: Acc
, mut fold
: Fold
) -> Acc
1673 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
1675 let acc
= match self.peeked
{
1676 Some(None
) => return init
,
1677 Some(Some(v
)) => fold(init
, v
),
1680 self.iter
.fold(acc
, fold
)
1684 #[stable(feature = "double_ended_peek_iterator", since = "1.38.0")]
1685 impl<I
> DoubleEndedIterator
for Peekable
<I
>
1687 I
: DoubleEndedIterator
,
1690 fn next_back(&mut self) -> Option
<Self::Item
> {
1691 match self.peeked
.as_mut() {
1692 Some(v @
Some(_
)) => self.iter
.next_back().or_else(|| v
.take()),
1694 None
=> self.iter
.next_back(),
1699 fn try_rfold
<B
, F
, R
>(&mut self, init
: B
, mut f
: F
) -> R
1702 F
: FnMut(B
, Self::Item
) -> R
,
1705 match self.peeked
.take() {
1706 Some(None
) => Try
::from_ok(init
),
1707 Some(Some(v
)) => match self.iter
.try_rfold(init
, &mut f
).into_result() {
1708 Ok(acc
) => f(acc
, v
),
1710 self.peeked
= Some(Some(v
));
1714 None
=> self.iter
.try_rfold(init
, f
),
1719 fn rfold
<Acc
, Fold
>(self, init
: Acc
, mut fold
: Fold
) -> Acc
1721 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
1726 let acc
= self.iter
.rfold(init
, &mut fold
);
1729 None
=> self.iter
.rfold(init
, fold
),
1734 #[stable(feature = "rust1", since = "1.0.0")]
1735 impl<I
: ExactSizeIterator
> ExactSizeIterator
for Peekable
<I
> {}
1737 #[stable(feature = "fused", since = "1.26.0")]
1738 impl<I
: FusedIterator
> FusedIterator
for Peekable
<I
> {}
1740 impl<I
: Iterator
> Peekable
<I
> {
1741 /// Returns a reference to the next() value without advancing the iterator.
1743 /// Like [`next`], if there is a value, it is wrapped in a `Some(T)`.
1744 /// But if the iteration is over, `None` is returned.
1746 /// [`next`]: trait.Iterator.html#tymethod.next
1748 /// Because `peek()` returns a reference, and many iterators iterate over
1749 /// references, there can be a possibly confusing situation where the
1750 /// return value is a double reference. You can see this effect in the
1758 /// let xs = [1, 2, 3];
1760 /// let mut iter = xs.iter().peekable();
1762 /// // peek() lets us see into the future
1763 /// assert_eq!(iter.peek(), Some(&&1));
1764 /// assert_eq!(iter.next(), Some(&1));
1766 /// assert_eq!(iter.next(), Some(&2));
1768 /// // The iterator does not advance even if we `peek` multiple times
1769 /// assert_eq!(iter.peek(), Some(&&3));
1770 /// assert_eq!(iter.peek(), Some(&&3));
1772 /// assert_eq!(iter.next(), Some(&3));
1774 /// // After the iterator is finished, so is `peek()`
1775 /// assert_eq!(iter.peek(), None);
1776 /// assert_eq!(iter.next(), None);
1779 #[stable(feature = "rust1", since = "1.0.0")]
1780 pub fn peek(&mut self) -> Option
<&I
::Item
> {
1781 let iter
= &mut self.iter
;
1782 self.peeked
.get_or_insert_with(|| iter
.next()).as_ref()
1785 /// Consume and return the next value of this iterator if a condition is true.
1787 /// If `func` returns `true` for the next value of this iterator, consume and return it.
1788 /// Otherwise, return `None`.
1791 /// Consume a number if it's equal to 0.
1793 /// #![feature(peekable_next_if)]
1794 /// let mut iter = (0..5).peekable();
1795 /// // The first item of the iterator is 0; consume it.
1796 /// assert_eq!(iter.next_if(|&x| x == 0), Some(0));
1797 /// // The next item returned is now 1, so `consume` will return `false`.
1798 /// assert_eq!(iter.next_if(|&x| x == 0), None);
1799 /// // `next_if` saves the value of the next item if it was not equal to `expected`.
1800 /// assert_eq!(iter.next(), Some(1));
1803 /// Consume any number less than 10.
1805 /// #![feature(peekable_next_if)]
1806 /// let mut iter = (1..20).peekable();
1807 /// // Consume all numbers less than 10
1808 /// while iter.next_if(|&x| x < 10).is_some() {}
1809 /// // The next value returned will be 10
1810 /// assert_eq!(iter.next(), Some(10));
1812 #[unstable(feature = "peekable_next_if", issue = "72480")]
1813 pub fn next_if(&mut self, func
: impl FnOnce(&I
::Item
) -> bool
) -> Option
<I
::Item
> {
1815 Some(matched
) if func(&matched
) => Some(matched
),
1817 // Since we called `self.next()`, we consumed `self.peeked`.
1818 assert
!(self.peeked
.is_none());
1819 self.peeked
= Some(other
);
1825 /// Consume and return the next item if it is equal to `expected`.
1828 /// Consume a number if it's equal to 0.
1830 /// #![feature(peekable_next_if)]
1831 /// let mut iter = (0..5).peekable();
1832 /// // The first item of the iterator is 0; consume it.
1833 /// assert_eq!(iter.next_if_eq(&0), Some(0));
1834 /// // The next item returned is now 1, so `consume` will return `false`.
1835 /// assert_eq!(iter.next_if_eq(&0), None);
1836 /// // `next_if_eq` saves the value of the next item if it was not equal to `expected`.
1837 /// assert_eq!(iter.next(), Some(1));
1839 #[unstable(feature = "peekable_next_if", issue = "72480")]
1840 pub fn next_if_eq
<T
>(&mut self, expected
: &T
) -> Option
<I
::Item
>
1843 I
::Item
: PartialEq
<T
>,
1845 self.next_if(|next
| next
== expected
)
1849 #[unstable(feature = "trusted_len", issue = "37572")]
1850 unsafe impl<I
> TrustedLen
for Peekable
<I
> where I
: TrustedLen {}
1852 #[unstable(issue = "none", feature = "inplace_iteration")]
1853 unsafe impl<S
: Iterator
, I
: Iterator
> SourceIter
for Peekable
<I
>
1855 I
: SourceIter
<Source
= S
>,
1860 unsafe fn as_inner(&mut self) -> &mut S
{
1861 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
1862 unsafe { SourceIter::as_inner(&mut self.iter) }
1866 #[unstable(issue = "none", feature = "inplace_iteration")]
1867 unsafe impl<I
: InPlaceIterable
> InPlaceIterable
for Peekable
<I
> {}
1869 /// An iterator that rejects elements while `predicate` returns `true`.
1871 /// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its
1872 /// documentation for more.
1874 /// [`skip_while`]: trait.Iterator.html#method.skip_while
1875 /// [`Iterator`]: trait.Iterator.html
1876 #[must_use = "iterators are lazy and do nothing unless consumed"]
1877 #[stable(feature = "rust1", since = "1.0.0")]
1879 pub struct SkipWhile
<I
, P
> {
1884 impl<I
, P
> SkipWhile
<I
, P
> {
1885 pub(super) fn new(iter
: I
, predicate
: P
) -> SkipWhile
<I
, P
> {
1886 SkipWhile { iter, flag: false, predicate }
1890 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1891 impl<I
: fmt
::Debug
, P
> fmt
::Debug
for SkipWhile
<I
, P
> {
1892 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1893 f
.debug_struct("SkipWhile").field("iter", &self.iter
).field("flag", &self.flag
).finish()
1897 #[stable(feature = "rust1", since = "1.0.0")]
1898 impl<I
: Iterator
, P
> Iterator
for SkipWhile
<I
, P
>
1900 P
: FnMut(&I
::Item
) -> bool
,
1902 type Item
= I
::Item
;
1905 fn next(&mut self) -> Option
<I
::Item
> {
1908 pred
: &'a
mut impl FnMut(&T
) -> bool
,
1909 ) -> impl FnMut(&T
) -> bool
+ 'a
{
1911 if *flag
|| !pred(x
) {
1920 let flag
= &mut self.flag
;
1921 let pred
= &mut self.predicate
;
1922 self.iter
.find(check(flag
, pred
))
1926 fn size_hint(&self) -> (usize, Option
<usize>) {
1927 let (_
, upper
) = self.iter
.size_hint();
1928 (0, upper
) // can't know a lower bound, due to the predicate
1932 fn try_fold
<Acc
, Fold
, R
>(&mut self, mut init
: Acc
, mut fold
: Fold
) -> R
1935 Fold
: FnMut(Acc
, Self::Item
) -> R
,
1940 Some(v
) => init
= fold(init
, v
)?
,
1941 None
=> return Try
::from_ok(init
),
1944 self.iter
.try_fold(init
, fold
)
1948 fn fold
<Acc
, Fold
>(mut self, mut init
: Acc
, mut fold
: Fold
) -> Acc
1950 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
1954 Some(v
) => init
= fold(init
, v
),
1955 None
=> return init
,
1958 self.iter
.fold(init
, fold
)
1962 #[stable(feature = "fused", since = "1.26.0")]
1963 impl<I
, P
> FusedIterator
for SkipWhile
<I
, P
>
1966 P
: FnMut(&I
::Item
) -> bool
,
1970 #[unstable(issue = "none", feature = "inplace_iteration")]
1971 unsafe impl<S
: Iterator
, P
, I
: Iterator
> SourceIter
for SkipWhile
<I
, P
>
1973 P
: FnMut(&I
::Item
) -> bool
,
1974 I
: SourceIter
<Source
= S
>,
1979 unsafe fn as_inner(&mut self) -> &mut S
{
1980 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
1981 unsafe { SourceIter::as_inner(&mut self.iter) }
1985 #[unstable(issue = "none", feature = "inplace_iteration")]
1986 unsafe impl<I
: InPlaceIterable
, F
> InPlaceIterable
for SkipWhile
<I
, F
> where
1987 F
: FnMut(&I
::Item
) -> bool
1991 /// An iterator that only accepts elements while `predicate` returns `true`.
1993 /// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its
1994 /// documentation for more.
1996 /// [`take_while`]: trait.Iterator.html#method.take_while
1997 /// [`Iterator`]: trait.Iterator.html
1998 #[must_use = "iterators are lazy and do nothing unless consumed"]
1999 #[stable(feature = "rust1", since = "1.0.0")]
2001 pub struct TakeWhile
<I
, P
> {
2006 impl<I
, P
> TakeWhile
<I
, P
> {
2007 pub(super) fn new(iter
: I
, predicate
: P
) -> TakeWhile
<I
, P
> {
2008 TakeWhile { iter, flag: false, predicate }
2012 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2013 impl<I
: fmt
::Debug
, P
> fmt
::Debug
for TakeWhile
<I
, P
> {
2014 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2015 f
.debug_struct("TakeWhile").field("iter", &self.iter
).field("flag", &self.flag
).finish()
2019 #[stable(feature = "rust1", since = "1.0.0")]
2020 impl<I
: Iterator
, P
> Iterator
for TakeWhile
<I
, P
>
2022 P
: FnMut(&I
::Item
) -> bool
,
2024 type Item
= I
::Item
;
2027 fn next(&mut self) -> Option
<I
::Item
> {
2031 let x
= self.iter
.next()?
;
2032 if (self.predicate
)(&x
) {
2042 fn size_hint(&self) -> (usize, Option
<usize>) {
2046 let (_
, upper
) = self.iter
.size_hint();
2047 (0, upper
) // can't know a lower bound, due to the predicate
2052 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
2055 Fold
: FnMut(Acc
, Self::Item
) -> R
,
2058 fn check
<'a
, T
, Acc
, R
: Try
<Ok
= Acc
>>(
2060 p
: &'a
mut impl FnMut(&T
) -> bool
,
2061 mut fold
: impl FnMut(Acc
, T
) -> R
+ 'a
,
2062 ) -> impl FnMut(Acc
, T
) -> ControlFlow
<Acc
, R
> + 'a
{
2065 ControlFlow
::from_try(fold(acc
, x
))
2068 ControlFlow
::Break(Try
::from_ok(acc
))
2076 let flag
= &mut self.flag
;
2077 let p
= &mut self.predicate
;
2078 self.iter
.try_fold(init
, check(flag
, p
, fold
)).into_try()
2083 fn fold
<Acc
, Fold
>(mut self, init
: Acc
, fold
: Fold
) -> Acc
2086 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
2089 fn ok
<B
, T
>(mut f
: impl FnMut(B
, T
) -> B
) -> impl FnMut(B
, T
) -> Result
<B
, !> {
2090 move |acc
, x
| Ok(f(acc
, x
))
2093 self.try_fold(init
, ok(fold
)).unwrap()
2097 #[stable(feature = "fused", since = "1.26.0")]
2098 impl<I
, P
> FusedIterator
for TakeWhile
<I
, P
>
2101 P
: FnMut(&I
::Item
) -> bool
,
2105 #[unstable(issue = "none", feature = "inplace_iteration")]
2106 unsafe impl<S
: Iterator
, P
, I
: Iterator
> SourceIter
for TakeWhile
<I
, P
>
2108 P
: FnMut(&I
::Item
) -> bool
,
2109 I
: SourceIter
<Source
= S
>,
2114 unsafe fn as_inner(&mut self) -> &mut S
{
2115 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
2116 unsafe { SourceIter::as_inner(&mut self.iter) }
2120 #[unstable(issue = "none", feature = "inplace_iteration")]
2121 unsafe impl<I
: InPlaceIterable
, F
> InPlaceIterable
for TakeWhile
<I
, F
> where
2122 F
: FnMut(&I
::Item
) -> bool
2126 /// An iterator that only accepts elements while `predicate` returns `Some(_)`.
2128 /// This `struct` is created by the [`map_while`] method on [`Iterator`]. See its
2129 /// documentation for more.
2131 /// [`map_while`]: trait.Iterator.html#method.map_while
2132 /// [`Iterator`]: trait.Iterator.html
2133 #[must_use = "iterators are lazy and do nothing unless consumed"]
2134 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
2136 pub struct MapWhile
<I
, P
> {
2141 impl<I
, P
> MapWhile
<I
, P
> {
2142 pub(super) fn new(iter
: I
, predicate
: P
) -> MapWhile
<I
, P
> {
2143 MapWhile { iter, predicate }
2147 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
2148 impl<I
: fmt
::Debug
, P
> fmt
::Debug
for MapWhile
<I
, P
> {
2149 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2150 f
.debug_struct("MapWhile").field("iter", &self.iter
).finish()
2154 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
2155 impl<B
, I
: Iterator
, P
> Iterator
for MapWhile
<I
, P
>
2157 P
: FnMut(I
::Item
) -> Option
<B
>,
2162 fn next(&mut self) -> Option
<B
> {
2163 let x
= self.iter
.next()?
;
2168 fn size_hint(&self) -> (usize, Option
<usize>) {
2169 let (_
, upper
) = self.iter
.size_hint();
2170 (0, upper
) // can't know a lower bound, due to the predicate
2174 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, mut fold
: Fold
) -> R
2177 Fold
: FnMut(Acc
, Self::Item
) -> R
,
2180 let Self { iter, predicate }
= self;
2181 iter
.try_fold(init
, |acc
, x
| match predicate(x
) {
2182 Some(item
) => ControlFlow
::from_try(fold(acc
, item
)),
2183 None
=> ControlFlow
::Break(Try
::from_ok(acc
)),
2189 fn fold
<Acc
, Fold
>(mut self, init
: Acc
, fold
: Fold
) -> Acc
2192 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
2195 fn ok
<B
, T
>(mut f
: impl FnMut(B
, T
) -> B
) -> impl FnMut(B
, T
) -> Result
<B
, !> {
2196 move |acc
, x
| Ok(f(acc
, x
))
2199 self.try_fold(init
, ok(fold
)).unwrap()
2203 #[unstable(issue = "none", feature = "inplace_iteration")]
2204 unsafe impl<S
: Iterator
, B
, I
: Iterator
, P
> SourceIter
for MapWhile
<I
, P
>
2206 P
: FnMut(I
::Item
) -> Option
<B
>,
2207 I
: SourceIter
<Source
= S
>,
2212 unsafe fn as_inner(&mut self) -> &mut S
{
2213 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
2214 unsafe { SourceIter::as_inner(&mut self.iter) }
2218 #[unstable(issue = "none", feature = "inplace_iteration")]
2219 unsafe impl<B
, I
: InPlaceIterable
, P
> InPlaceIterable
for MapWhile
<I
, P
> where
2220 P
: FnMut(I
::Item
) -> Option
<B
>
2224 /// An iterator that skips over `n` elements of `iter`.
2226 /// This `struct` is created by the [`skip`] method on [`Iterator`]. See its
2227 /// documentation for more.
2229 /// [`skip`]: trait.Iterator.html#method.skip
2230 /// [`Iterator`]: trait.Iterator.html
2231 #[derive(Clone, Debug)]
2232 #[must_use = "iterators are lazy and do nothing unless consumed"]
2233 #[stable(feature = "rust1", since = "1.0.0")]
2234 pub struct Skip
<I
> {
2239 pub(super) fn new(iter
: I
, n
: usize) -> Skip
<I
> {
2244 #[stable(feature = "rust1", since = "1.0.0")]
2245 impl<I
> Iterator
for Skip
<I
>
2249 type Item
= <I
as Iterator
>::Item
;
2252 fn next(&mut self) -> Option
<I
::Item
> {
2258 self.iter
.nth(old_n
)
2263 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
2264 // Can't just add n + self.n due to overflow.
2266 let to_skip
= self.n
;
2269 self.iter
.nth(to_skip
- 1)?
;
2275 fn count(mut self) -> usize {
2278 if self.iter
.nth(self.n
- 1).is_none() {
2286 fn last(mut self) -> Option
<I
::Item
> {
2289 self.iter
.nth(self.n
- 1)?
;
2295 fn size_hint(&self) -> (usize, Option
<usize>) {
2296 let (lower
, upper
) = self.iter
.size_hint();
2298 let lower
= lower
.saturating_sub(self.n
);
2299 let upper
= match upper
{
2300 Some(x
) => Some(x
.saturating_sub(self.n
)),
2308 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
2311 Fold
: FnMut(Acc
, Self::Item
) -> R
,
2318 if self.iter
.nth(n
- 1).is_none() {
2319 return Try
::from_ok(init
);
2322 self.iter
.try_fold(init
, fold
)
2326 fn fold
<Acc
, Fold
>(mut self, init
: Acc
, fold
: Fold
) -> Acc
2328 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
2332 if self.iter
.nth(self.n
- 1).is_none() {
2336 self.iter
.fold(init
, fold
)
2340 #[stable(feature = "rust1", since = "1.0.0")]
2341 impl<I
> ExactSizeIterator
for Skip
<I
> where I
: ExactSizeIterator {}
2343 #[stable(feature = "double_ended_skip_iterator", since = "1.9.0")]
2344 impl<I
> DoubleEndedIterator
for Skip
<I
>
2346 I
: DoubleEndedIterator
+ ExactSizeIterator
,
2348 fn next_back(&mut self) -> Option
<Self::Item
> {
2349 if self.len() > 0 { self.iter.next_back() }
else { None }
2353 fn nth_back(&mut self, n
: usize) -> Option
<I
::Item
> {
2354 let len
= self.len();
2356 self.iter
.nth_back(n
)
2359 // consume the original iterator
2360 self.iter
.nth_back(len
- 1);
2366 fn try_rfold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
2369 Fold
: FnMut(Acc
, Self::Item
) -> R
,
2372 fn check
<T
, Acc
, R
: Try
<Ok
= Acc
>>(
2374 mut fold
: impl FnMut(Acc
, T
) -> R
,
2375 ) -> impl FnMut(Acc
, T
) -> ControlFlow
<Acc
, R
> {
2378 let r
= fold(acc
, x
);
2379 if n
== 0 { ControlFlow::Break(r) }
else { ControlFlow::from_try(r) }
2387 self.iter
.try_rfold(init
, check(n
, fold
)).into_try()
2391 fn rfold
<Acc
, Fold
>(mut self, init
: Acc
, fold
: Fold
) -> Acc
2393 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
2396 fn ok
<Acc
, T
>(mut f
: impl FnMut(Acc
, T
) -> Acc
) -> impl FnMut(Acc
, T
) -> Result
<Acc
, !> {
2397 move |acc
, x
| Ok(f(acc
, x
))
2400 self.try_rfold(init
, ok(fold
)).unwrap()
2404 #[stable(feature = "fused", since = "1.26.0")]
2405 impl<I
> FusedIterator
for Skip
<I
> where I
: FusedIterator {}
2407 #[unstable(issue = "none", feature = "inplace_iteration")]
2408 unsafe impl<S
: Iterator
, I
: Iterator
> SourceIter
for Skip
<I
>
2410 I
: SourceIter
<Source
= S
>,
2415 unsafe fn as_inner(&mut self) -> &mut S
{
2416 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
2417 unsafe { SourceIter::as_inner(&mut self.iter) }
2421 #[unstable(issue = "none", feature = "inplace_iteration")]
2422 unsafe impl<I
: InPlaceIterable
> InPlaceIterable
for Skip
<I
> {}
2424 /// An iterator that only iterates over the first `n` iterations of `iter`.
2426 /// This `struct` is created by the [`take`] method on [`Iterator`]. See its
2427 /// documentation for more.
2429 /// [`take`]: trait.Iterator.html#method.take
2430 /// [`Iterator`]: trait.Iterator.html
2431 #[derive(Clone, Debug)]
2432 #[must_use = "iterators are lazy and do nothing unless consumed"]
2433 #[stable(feature = "rust1", since = "1.0.0")]
2434 pub struct Take
<I
> {
2436 pub(super) n
: usize,
2439 pub(super) fn new(iter
: I
, n
: usize) -> Take
<I
> {
2444 #[stable(feature = "rust1", since = "1.0.0")]
2445 impl<I
> Iterator
for Take
<I
>
2449 type Item
= <I
as Iterator
>::Item
;
2452 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> {
2462 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
2468 self.iter
.nth(self.n
- 1);
2476 fn size_hint(&self) -> (usize, Option
<usize>) {
2478 return (0, Some(0));
2481 let (lower
, upper
) = self.iter
.size_hint();
2483 let lower
= cmp
::min(lower
, self.n
);
2485 let upper
= match upper
{
2486 Some(x
) if x
< self.n
=> Some(x
),
2494 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
2497 Fold
: FnMut(Acc
, Self::Item
) -> R
,
2500 fn check
<'a
, T
, Acc
, R
: Try
<Ok
= Acc
>>(
2502 mut fold
: impl FnMut(Acc
, T
) -> R
+ 'a
,
2503 ) -> impl FnMut(Acc
, T
) -> ControlFlow
<Acc
, R
> + 'a
{
2506 let r
= fold(acc
, x
);
2507 if *n
== 0 { ControlFlow::Break(r) }
else { ControlFlow::from_try(r) }
2514 let n
= &mut self.n
;
2515 self.iter
.try_fold(init
, check(n
, fold
)).into_try()
2520 fn fold
<Acc
, Fold
>(mut self, init
: Acc
, fold
: Fold
) -> Acc
2523 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
2526 fn ok
<B
, T
>(mut f
: impl FnMut(B
, T
) -> B
) -> impl FnMut(B
, T
) -> Result
<B
, !> {
2527 move |acc
, x
| Ok(f(acc
, x
))
2530 self.try_fold(init
, ok(fold
)).unwrap()
2534 #[unstable(issue = "none", feature = "inplace_iteration")]
2535 unsafe impl<S
: Iterator
, I
: Iterator
> SourceIter
for Take
<I
>
2537 I
: SourceIter
<Source
= S
>,
2542 unsafe fn as_inner(&mut self) -> &mut S
{
2543 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
2544 unsafe { SourceIter::as_inner(&mut self.iter) }
2548 #[unstable(issue = "none", feature = "inplace_iteration")]
2549 unsafe impl<I
: InPlaceIterable
> InPlaceIterable
for Take
<I
> {}
2551 #[stable(feature = "double_ended_take_iterator", since = "1.38.0")]
2552 impl<I
> DoubleEndedIterator
for Take
<I
>
2554 I
: DoubleEndedIterator
+ ExactSizeIterator
,
2557 fn next_back(&mut self) -> Option
<Self::Item
> {
2563 self.iter
.nth_back(self.iter
.len().saturating_sub(n
))
2568 fn nth_back(&mut self, n
: usize) -> Option
<Self::Item
> {
2569 let len
= self.iter
.len();
2571 let m
= len
.saturating_sub(self.n
) + n
;
2573 self.iter
.nth_back(m
)
2576 self.iter
.nth_back(len
- 1);
2583 fn try_rfold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
2586 Fold
: FnMut(Acc
, Self::Item
) -> R
,
2592 let len
= self.iter
.len();
2593 if len
> self.n
&& self.iter
.nth_back(len
- self.n
- 1).is_none() {
2596 self.iter
.try_rfold(init
, fold
)
2602 fn rfold
<Acc
, Fold
>(mut self, init
: Acc
, fold
: Fold
) -> Acc
2605 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
2610 let len
= self.iter
.len();
2611 if len
> self.n
&& self.iter
.nth_back(len
- self.n
- 1).is_none() {
2614 self.iter
.rfold(init
, fold
)
2620 #[stable(feature = "rust1", since = "1.0.0")]
2621 impl<I
> ExactSizeIterator
for Take
<I
> where I
: ExactSizeIterator {}
2623 #[stable(feature = "fused", since = "1.26.0")]
2624 impl<I
> FusedIterator
for Take
<I
> where I
: FusedIterator {}
2626 #[unstable(feature = "trusted_len", issue = "37572")]
2627 unsafe impl<I
: TrustedLen
> TrustedLen
for Take
<I
> {}
2629 /// An iterator to maintain state while iterating another iterator.
2631 /// This `struct` is created by the [`scan`] method on [`Iterator`]. See its
2632 /// documentation for more.
2634 /// [`scan`]: trait.Iterator.html#method.scan
2635 /// [`Iterator`]: trait.Iterator.html
2636 #[must_use = "iterators are lazy and do nothing unless consumed"]
2637 #[stable(feature = "rust1", since = "1.0.0")]
2639 pub struct Scan
<I
, St
, F
> {
2644 impl<I
, St
, F
> Scan
<I
, St
, F
> {
2645 pub(super) fn new(iter
: I
, state
: St
, f
: F
) -> Scan
<I
, St
, F
> {
2646 Scan { iter, state, f }
2650 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2651 impl<I
: fmt
::Debug
, St
: fmt
::Debug
, F
> fmt
::Debug
for Scan
<I
, St
, F
> {
2652 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2653 f
.debug_struct("Scan").field("iter", &self.iter
).field("state", &self.state
).finish()
2657 #[stable(feature = "rust1", since = "1.0.0")]
2658 impl<B
, I
, St
, F
> Iterator
for Scan
<I
, St
, F
>
2661 F
: FnMut(&mut St
, I
::Item
) -> Option
<B
>,
2666 fn next(&mut self) -> Option
<B
> {
2667 let a
= self.iter
.next()?
;
2668 (self.f
)(&mut self.state
, a
)
2672 fn size_hint(&self) -> (usize, Option
<usize>) {
2673 let (_
, upper
) = self.iter
.size_hint();
2674 (0, upper
) // can't know a lower bound, due to the scan function
2678 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
2681 Fold
: FnMut(Acc
, Self::Item
) -> R
,
2684 fn scan
<'a
, T
, St
, B
, Acc
, R
: Try
<Ok
= Acc
>>(
2686 f
: &'a
mut impl FnMut(&mut St
, T
) -> Option
<B
>,
2687 mut fold
: impl FnMut(Acc
, B
) -> R
+ 'a
,
2688 ) -> impl FnMut(Acc
, T
) -> ControlFlow
<Acc
, R
> + 'a
{
2689 move |acc
, x
| match f(state
, x
) {
2690 None
=> ControlFlow
::Break(Try
::from_ok(acc
)),
2691 Some(x
) => ControlFlow
::from_try(fold(acc
, x
)),
2695 let state
= &mut self.state
;
2696 let f
= &mut self.f
;
2697 self.iter
.try_fold(init
, scan(state
, f
, fold
)).into_try()
2701 fn fold
<Acc
, Fold
>(mut self, init
: Acc
, fold
: Fold
) -> Acc
2704 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
2707 fn ok
<B
, T
>(mut f
: impl FnMut(B
, T
) -> B
) -> impl FnMut(B
, T
) -> Result
<B
, !> {
2708 move |acc
, x
| Ok(f(acc
, x
))
2711 self.try_fold(init
, ok(fold
)).unwrap()
2715 #[unstable(issue = "none", feature = "inplace_iteration")]
2716 unsafe impl<St
, F
, B
, S
: Iterator
, I
: Iterator
> SourceIter
for Scan
<I
, St
, F
>
2718 I
: SourceIter
<Source
= S
>,
2719 F
: FnMut(&mut St
, I
::Item
) -> Option
<B
>,
2724 unsafe fn as_inner(&mut self) -> &mut S
{
2725 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
2726 unsafe { SourceIter::as_inner(&mut self.iter) }
2730 #[unstable(issue = "none", feature = "inplace_iteration")]
2731 unsafe impl<St
, F
, B
, I
: InPlaceIterable
> InPlaceIterable
for Scan
<I
, St
, F
> where
2732 F
: FnMut(&mut St
, I
::Item
) -> Option
<B
>
2736 /// An iterator that calls a function with a reference to each element before
2739 /// This `struct` is created by the [`inspect`] method on [`Iterator`]. See its
2740 /// documentation for more.
2742 /// [`inspect`]: trait.Iterator.html#method.inspect
2743 /// [`Iterator`]: trait.Iterator.html
2744 #[must_use = "iterators are lazy and do nothing unless consumed"]
2745 #[stable(feature = "rust1", since = "1.0.0")]
2747 pub struct Inspect
<I
, F
> {
2751 impl<I
, F
> Inspect
<I
, F
> {
2752 pub(super) fn new(iter
: I
, f
: F
) -> Inspect
<I
, F
> {
2757 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2758 impl<I
: fmt
::Debug
, F
> fmt
::Debug
for Inspect
<I
, F
> {
2759 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2760 f
.debug_struct("Inspect").field("iter", &self.iter
).finish()
2764 impl<I
: Iterator
, F
> Inspect
<I
, F
>
2769 fn do_inspect(&mut self, elt
: Option
<I
::Item
>) -> Option
<I
::Item
> {
2770 if let Some(ref a
) = elt
{
2778 fn inspect_fold
<T
, Acc
>(
2779 mut f
: impl FnMut(&T
),
2780 mut fold
: impl FnMut(Acc
, T
) -> Acc
,
2781 ) -> impl FnMut(Acc
, T
) -> Acc
{
2788 fn inspect_try_fold
<'a
, T
, Acc
, R
>(
2789 f
: &'a
mut impl FnMut(&T
),
2790 mut fold
: impl FnMut(Acc
, T
) -> R
+ 'a
,
2791 ) -> impl FnMut(Acc
, T
) -> R
+ 'a
{
2798 #[stable(feature = "rust1", since = "1.0.0")]
2799 impl<I
: Iterator
, F
> Iterator
for Inspect
<I
, F
>
2803 type Item
= I
::Item
;
2806 fn next(&mut self) -> Option
<I
::Item
> {
2807 let next
= self.iter
.next();
2808 self.do_inspect(next
)
2812 fn size_hint(&self) -> (usize, Option
<usize>) {
2813 self.iter
.size_hint()
2817 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
2820 Fold
: FnMut(Acc
, Self::Item
) -> R
,
2823 self.iter
.try_fold(init
, inspect_try_fold(&mut self.f
, fold
))
2827 fn fold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
2829 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
2831 self.iter
.fold(init
, inspect_fold(self.f
, fold
))
2835 #[stable(feature = "rust1", since = "1.0.0")]
2836 impl<I
: DoubleEndedIterator
, F
> DoubleEndedIterator
for Inspect
<I
, F
>
2841 fn next_back(&mut self) -> Option
<I
::Item
> {
2842 let next
= self.iter
.next_back();
2843 self.do_inspect(next
)
2847 fn try_rfold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
2850 Fold
: FnMut(Acc
, Self::Item
) -> R
,
2853 self.iter
.try_rfold(init
, inspect_try_fold(&mut self.f
, fold
))
2857 fn rfold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
2859 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
2861 self.iter
.rfold(init
, inspect_fold(self.f
, fold
))
2865 #[stable(feature = "rust1", since = "1.0.0")]
2866 impl<I
: ExactSizeIterator
, F
> ExactSizeIterator
for Inspect
<I
, F
>
2870 fn len(&self) -> usize {
2874 fn is_empty(&self) -> bool
{
2875 self.iter
.is_empty()
2879 #[stable(feature = "fused", since = "1.26.0")]
2880 impl<I
: FusedIterator
, F
> FusedIterator
for Inspect
<I
, F
> where F
: FnMut(&I
::Item
) {}
2882 #[unstable(issue = "none", feature = "inplace_iteration")]
2883 unsafe impl<S
: Iterator
, I
: Iterator
, F
> SourceIter
for Inspect
<I
, F
>
2886 I
: SourceIter
<Source
= S
>,
2891 unsafe fn as_inner(&mut self) -> &mut S
{
2892 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
2893 unsafe { SourceIter::as_inner(&mut self.iter) }
2897 #[unstable(issue = "none", feature = "inplace_iteration")]
2898 unsafe impl<I
: InPlaceIterable
, F
> InPlaceIterable
for Inspect
<I
, F
> where F
: FnMut(&I
::Item
) {}
2900 /// An iterator adapter that produces output as long as the underlying
2901 /// iterator produces `Result::Ok` values.
2903 /// If an error is encountered, the iterator stops and the error is
2905 pub(crate) struct ResultShunt
<'a
, I
, E
> {
2907 error
: &'a
mut Result
<(), E
>,
2910 /// Process the given iterator as if it yielded a `T` instead of a
2911 /// `Result<T, _>`. Any errors will stop the inner iterator and
2912 /// the overall result will be an error.
2913 pub(crate) fn process_results
<I
, T
, E
, F
, U
>(iter
: I
, mut f
: F
) -> Result
<U
, E
>
2915 I
: Iterator
<Item
= Result
<T
, E
>>,
2916 for<'a
> F
: FnMut(ResultShunt
<'a
, I
, E
>) -> U
,
2918 let mut error
= Ok(());
2919 let shunt
= ResultShunt { iter, error: &mut error }
;
2920 let value
= f(shunt
);
2921 error
.map(|()| value
)
2924 impl<I
, T
, E
> Iterator
for ResultShunt
<'_
, I
, E
>
2926 I
: Iterator
<Item
= Result
<T
, E
>>,
2930 fn next(&mut self) -> Option
<Self::Item
> {
2934 fn size_hint(&self) -> (usize, Option
<usize>) {
2935 if self.error
.is_err() {
2938 let (_
, upper
) = self.iter
.size_hint();
2943 fn try_fold
<B
, F
, R
>(&mut self, init
: B
, mut f
: F
) -> R
2945 F
: FnMut(B
, Self::Item
) -> R
,
2948 let error
= &mut *self.error
;
2950 .try_fold(init
, |acc
, x
| match x
{
2951 Ok(x
) => ControlFlow
::from_try(f(acc
, x
)),
2954 ControlFlow
::Break(Try
::from_ok(acc
))
2960 fn fold
<B
, F
>(mut self, init
: B
, fold
: F
) -> B
2963 F
: FnMut(B
, Self::Item
) -> B
,
2966 fn ok
<B
, T
>(mut f
: impl FnMut(B
, T
) -> B
) -> impl FnMut(B
, T
) -> Result
<B
, !> {
2967 move |acc
, x
| Ok(f(acc
, x
))
2970 self.try_fold(init
, ok(fold
)).unwrap()