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