core/iter/adapters/
cycle.rs

1use crate::iter::FusedIterator;
2use crate::num::NonZero;
3use crate::ops::Try;
4
5/// An iterator that repeats endlessly.
6///
7/// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its
8/// documentation for more.
9///
10/// [`cycle`]: Iterator::cycle
11/// [`Iterator`]: trait.Iterator.html
12#[derive(Clone, Debug)]
13#[must_use = "iterators are lazy and do nothing unless consumed"]
14#[stable(feature = "rust1", since = "1.0.0")]
15pub struct Cycle<I> {
16    orig: I,
17    iter: I,
18}
19
20impl<I: Clone> Cycle<I> {
21    pub(in crate::iter) fn new(iter: I) -> Cycle<I> {
22        Cycle { orig: iter.clone(), iter }
23    }
24}
25
26#[stable(feature = "rust1", since = "1.0.0")]
27impl<I> Iterator for Cycle<I>
28where
29    I: Clone + Iterator,
30{
31    type Item = <I as Iterator>::Item;
32
33    #[inline]
34    fn next(&mut self) -> Option<<I as Iterator>::Item> {
35        match self.iter.next() {
36            None => {
37                self.iter = self.orig.clone();
38                self.iter.next()
39            }
40            y => y,
41        }
42    }
43
44    #[inline]
45    fn size_hint(&self) -> (usize, Option<usize>) {
46        // the cycle iterator is either empty or infinite
47        match self.orig.size_hint() {
48            sz @ (0, Some(0)) => sz,
49            (0, _) => (0, None),
50            _ => (usize::MAX, None),
51        }
52    }
53
54    #[inline]
55    fn try_fold<Acc, F, R>(&mut self, mut acc: Acc, mut f: F) -> R
56    where
57        F: FnMut(Acc, Self::Item) -> R,
58        R: Try<Output = Acc>,
59    {
60        // fully iterate the current iterator. this is necessary because
61        // `self.iter` may be empty even when `self.orig` isn't
62        acc = self.iter.try_fold(acc, &mut f)?;
63        self.iter = self.orig.clone();
64
65        // complete a full cycle, keeping track of whether the cycled
66        // iterator is empty or not. we need to return early in case
67        // of an empty iterator to prevent an infinite loop
68        let mut is_empty = true;
69        acc = self.iter.try_fold(acc, |acc, x| {
70            is_empty = false;
71            f(acc, x)
72        })?;
73
74        if is_empty {
75            return try { acc };
76        }
77
78        loop {
79            self.iter = self.orig.clone();
80            acc = self.iter.try_fold(acc, &mut f)?;
81        }
82    }
83
84    #[inline]
85    #[rustc_inherit_overflow_checks]
86    fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
87        let mut n = match self.iter.advance_by(n) {
88            Ok(()) => return Ok(()),
89            Err(rem) => rem.get(),
90        };
91
92        while n > 0 {
93            self.iter = self.orig.clone();
94            n = match self.iter.advance_by(n) {
95                Ok(()) => return Ok(()),
96                e @ Err(rem) if rem.get() == n => return e,
97                Err(rem) => rem.get(),
98            };
99        }
100
101        NonZero::new(n).map_or(Ok(()), Err)
102    }
103
104    // No `fold` override, because `fold` doesn't make much sense for `Cycle`,
105    // and we can't do anything better than the default.
106}
107
108#[stable(feature = "fused", since = "1.26.0")]
109impl<I> FusedIterator for Cycle<I> where I: Clone + Iterator {}