alternating_iter/
alternating.rs

1use core::iter;
2
3use crate::utils::{checked, min_and_1, saturating};
4#[allow(unused_imports)]
5use crate::AlternatingExt;
6
7/// Struct for alternating between the items of two iterators.
8///
9/// This struct is created by the [`AlternatingExt::alternate_with`] method, see its documentation for more.
10#[derive(Debug, Clone, Copy, PartialEq, Eq)]
11pub struct Alternating<I, J>
12where
13    I: Iterator,
14    J: Iterator<Item = I::Item>,
15{
16    i: I,
17    j: J,
18    i_next: bool,
19}
20
21impl<I, J> Alternating<I, J>
22where
23    I: Iterator,
24    J: Iterator<Item = I::Item>,
25{
26    /// Create a new `Alternating` iterator from two other iterables.
27    ///
28    /// Alternative to [`AlternatingExt::alternate_with`]. There is no  difference.
29    pub fn new(i: impl IntoIterator<IntoIter = I>, j: impl IntoIterator<IntoIter = J>) -> Self {
30        Self {
31            i: i.into_iter(),
32            j: j.into_iter(),
33            i_next: true,
34        }
35    }
36}
37
38impl<I, J> Iterator for Alternating<I, J>
39where
40    I: Iterator,
41    J: Iterator<Item = I::Item>,
42{
43    type Item = I::Item;
44    fn next(&mut self) -> Option<Self::Item> {
45        if self.i_next {
46            self.i_next = false;
47            self.i.next()
48        } else {
49            self.i_next = true;
50            self.j.next()
51        }
52    }
53
54    fn size_hint(&self) -> (usize, Option<usize>) {
55        let (i_lower, i_upper) = self.i.size_hint();
56        let (j_lower, j_upper) = self.j.size_hint();
57        let last_i = !self.i_next;
58
59        // The longest we can go without outputing consecutive elements
60        // from the same iterator NOR None is twice the length of the shorter iterator.
61        // We can squeeze 1 more if the other iterator is longer and
62        // the last element was from the same iterator.
63
64        let lower = saturating(min_and_1(i_lower, j_lower, last_i));
65        let upper = match (i_upper, j_upper) {
66            (Some(i_upper), Some(j_upper)) => checked(min_and_1(i_upper, j_upper, last_i)),
67            (Some(i_upper), None) => checked((i_upper, last_i)),
68            (None, Some(j_upper)) => checked((j_upper, !last_i)),
69            // Since both have no upper bound, as far as we are concerned,
70            // this mean they go on forever. Therefore, we don't have to worry
71            // about one of them running out.
72            (None, None) => None,
73        };
74        (lower, upper)
75    }
76}
77
78// Deprecated: According to the documentation for ExactSizeIterator,
79// "If an adapter makes an iterator longer, then it’s usually incorrect for
80// that adapter to implement ExactSizeIterator."
81
82// impl<I, J> iter::ExactSizeIterator for Alternating<I, J>
83// where
84//     I: iter::ExactSizeIterator,
85//     J: iter::ExactSizeIterator<Item = I::Item>,
86// {
87//     fn len(&self) -> usize {
88//         saturating(min_and_1(self.i.len(), self.j.len(), !self.i_next))
89//     }
90// }
91
92#[cfg(test)]
93mod tests {
94    use std::fmt::Debug;
95
96    use super::*;
97
98    const DEFAULT_ATTEMPT: usize = 10;
99    fn no_more<T: Debug>(mut iter: impl Iterator<Item = T>, attempt: usize) {
100        for i in 0..attempt {
101            let result = iter.next();
102            assert!(
103                result.is_none(),
104                "Expected None, got {:?} at iteration {}",
105                result,
106                i
107            );
108        }
109    }
110
111    #[test]
112    fn same_lengths() {
113        let a = [1, 2];
114        let b = [3, 4];
115
116        let mut iter = a.iter().alternate_with(b.iter());
117
118        assert_eq!(iter.next(), Some(&1));
119        assert_eq!(iter.next(), Some(&3));
120        assert_eq!(iter.next(), Some(&2));
121        assert_eq!(iter.next(), Some(&4));
122        assert_eq!(iter.next(), None);
123        no_more(iter, DEFAULT_ATTEMPT);
124    }
125    #[test]
126    fn different_lengths_1more() {
127        let a = [1, 2];
128        let b = [3, 4, 5];
129
130        let mut iter = a.iter().alternate_with(b.iter());
131
132        assert_eq!(iter.next(), Some(&1));
133        assert_eq!(iter.next(), Some(&3));
134        assert_eq!(iter.next(), Some(&2));
135        assert_eq!(iter.next(), Some(&4));
136        assert_eq!(iter.next(), None);
137        assert_eq!(iter.next(), Some(&5));
138        assert_eq!(iter.next(), None);
139        no_more(iter, DEFAULT_ATTEMPT);
140    }
141
142    #[test]
143    fn different_lengths_2more() {
144        let a = [1, 2];
145        let b = [3, 4, 5, 6];
146
147        let mut iter = a.iter().alternate_with(b.iter());
148
149        assert_eq!(iter.next(), Some(&1));
150        assert_eq!(iter.next(), Some(&3));
151        assert_eq!(iter.next(), Some(&2));
152        assert_eq!(iter.next(), Some(&4));
153        assert_eq!(iter.next(), None);
154        assert_eq!(iter.next(), Some(&5));
155        assert_eq!(iter.next(), None);
156        assert_eq!(iter.next(), Some(&6));
157        assert_eq!(iter.next(), None);
158        no_more(iter, DEFAULT_ATTEMPT);
159    }
160
161    #[test]
162    fn empty_iterators() {
163        let a: [i32; 0] = [];
164        let b: [i32; 0] = [];
165
166        let mut iter = a.iter().alternate_with(b.iter());
167
168        assert_eq!(iter.next(), None);
169        no_more(iter, DEFAULT_ATTEMPT);
170    }
171
172    #[test]
173    fn one_empty_iterator() {
174        let a = [1, 2, 3];
175        let b: [i32; 0] = [];
176
177        let mut iter = a.iter().alternate_with(b.iter());
178
179        assert_eq!(iter.next(), Some(&1));
180        assert_eq!(iter.next(), None);
181        assert_eq!(iter.next(), Some(&2));
182        assert_eq!(iter.next(), None);
183        assert_eq!(iter.next(), Some(&3));
184        no_more(iter, DEFAULT_ATTEMPT);
185    }
186
187    #[test]
188    fn same_iterator() {
189        let a = [1, 2, 3];
190
191        let mut iter = a.iter().alternate_with(a.iter());
192
193        assert_eq!(iter.next(), Some(&1));
194        assert_eq!(iter.next(), Some(&1));
195        assert_eq!(iter.next(), Some(&2));
196        assert_eq!(iter.next(), Some(&2));
197        assert_eq!(iter.next(), Some(&3));
198        assert_eq!(iter.next(), Some(&3));
199        assert_eq!(iter.next(), None);
200        no_more(iter, DEFAULT_ATTEMPT);
201    }
202
203    #[test]
204    fn size_hint_accurate() {
205        let a = [1, 2, 3];
206        let b = [4, 5];
207
208        assert_eq!(
209            a.iter().size_hint().1,
210            Some(a.iter().count()),
211            "Sanity check failed"
212        );
213        assert_eq!(
214            b.iter().size_hint().1,
215            Some(b.iter().count()),
216            "Sanity check failed"
217        );
218
219        let iter = a.iter().alternate_with(b.iter());
220
221        assert_eq!(iter.size_hint().1, Some(iter.count()));
222    }
223    #[test]
224    fn size_hint() {
225        let a = [1, 2, 3];
226        let b = [4, 5];
227
228        assert_eq!(a.iter().size_hint(), (3, Some(3)), "Sanity check failed");
229        assert_eq!(b.iter().size_hint(), (2, Some(2)), "Sanity check failed");
230
231        let iter = a.iter().alternate_with(b.iter());
232
233        assert_eq!(iter.size_hint(), (5, Some(5)));
234        assert_eq!(iter.count(), 5, "Inaccurate size hint");
235    }
236    #[test]
237    fn size_hint_unbounded_right() {
238        let a = [1, 2, 3];
239        let b = iter::repeat(&0);
240
241        assert_eq!(a.iter().size_hint(), (3, Some(3)), "Sanity check failed");
242        assert_eq!(b.size_hint(), (usize::MAX, None), "Sanity check failed");
243
244        let iter = a.iter().alternate_with(b);
245
246        assert_eq!(iter.size_hint(), (6, Some(6)));
247        assert_eq!(iter.count(), 6, "Inaccurate size hint");
248    }
249    #[test]
250    fn size_hint_unbounded_left() {
251        let a = iter::repeat(&0);
252        let b = [1, 2, 3];
253
254        assert_eq!(a.size_hint(), (usize::MAX, None), "Sanity check failed");
255        assert_eq!(b.iter().size_hint(), (3, Some(3)), "Sanity check failed");
256
257        let iter = a.alternate_with(b.iter());
258
259        assert_eq!(iter.size_hint(), (7, Some(7)));
260        assert_eq!(iter.count(), 7, "Inaccurate size hint");
261    }
262    #[test]
263    fn size_hint_bound_exceed_max() {
264        let a = 0..usize::MAX;
265        let b = 0..usize::MAX;
266
267        assert_eq!(
268            a.size_hint(),
269            (usize::MAX, Some(usize::MAX)),
270            "Sanity check failed"
271        );
272        assert_eq!(
273            b.size_hint(),
274            (usize::MAX, Some(usize::MAX)),
275            "Sanity check failed"
276        );
277
278        let iter = a.alternate_with(b);
279
280        assert_eq!(iter.size_hint(), (usize::MAX, None));
281    }
282    #[test]
283    fn size_hint_bound_half_max_left() {
284        let a = 0..usize::MAX / 2;
285        let b = 0..usize::MAX / 2 + 1;
286
287        assert_eq!(
288            a.size_hint(),
289            (usize::MAX / 2, Some(usize::MAX / 2)),
290            "Sanity check failed"
291        );
292        assert_eq!(
293            b.size_hint(),
294            (usize::MAX / 2 + 1, Some(usize::MAX / 2 + 1)),
295            "Sanity check failed"
296        );
297
298        let iter = a.alternate_with(b);
299
300        assert_eq!(iter.size_hint(), (usize::MAX - 1, Some(usize::MAX - 1)));
301    }
302    #[test]
303    fn size_hint_bound_half_max_right() {
304        let a = 0..usize::MAX / 2 + 1;
305        let b = 0..usize::MAX / 2;
306
307        assert_eq!(
308            a.size_hint(),
309            (usize::MAX / 2 + 1, Some(usize::MAX / 2 + 1)),
310            "Sanity check failed"
311        );
312        assert_eq!(
313            b.size_hint(),
314            (usize::MAX / 2, Some(usize::MAX / 2)),
315            "Sanity check failed"
316        );
317
318        let iter = a.alternate_with(b);
319
320        assert_eq!(iter.size_hint(), (usize::MAX, Some(usize::MAX)));
321    }
322    #[test]
323    fn size_hint_both_unbounded() {
324        let a = iter::repeat(0);
325        let b = iter::repeat(0);
326
327        assert_eq!(a.size_hint(), (usize::MAX, None), "Sanity check failed");
328        assert_eq!(b.size_hint(), (usize::MAX, None), "Sanity check failed");
329
330        let iter = a.alternate_with(b);
331
332        assert_eq!(iter.size_hint(), (usize::MAX, None));
333    }
334}
alternating_iter/alternating.rs

alternating_iter/
alternating.rs
