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