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 {}
110