1 use paste;
2 use permutohedron;
3 use quickcheck as qc;
4 use rand::{distributions::{Distribution, Standard}, Rng, SeedableRng, rngs::StdRng};
5 use rand::{seq::SliceRandom, thread_rng};
6 use std::{cmp::min, fmt::Debug, marker::PhantomData};
7 use itertools as it;
8 use crate::it::Itertools;
9 use crate::it::ExactlyOneError;
10 use crate::it::multizip;
11 use crate::it::multipeek;
12 use crate::it::peek_nth;
13 use crate::it::free::rciter;
14 use crate::it::free::put_back_n;
15 use crate::it::FoldWhile;
16 use crate::it::cloned;
17 use crate::it::iproduct;
18 use crate::it::izip;
19 
20 #[test]
product3()21 fn product3() {
22     let prod = iproduct!(0..3, 0..2, 0..2);
23     assert_eq!(prod.size_hint(), (12, Some(12)));
24     let v = prod.collect_vec();
25     for i in 0..3 {
26         for j in 0..2 {
27             for k in 0..2 {
28                 assert!((i, j, k) == v[(i * 2 * 2 + j * 2 + k) as usize]);
29             }
30         }
31     }
32     for (_, _, _, _) in iproduct!(0..3, 0..2, 0..2, 0..3) {
33         /* test compiles */
34     }
35 }
36 
37 #[test]
interleave_shortest()38 fn interleave_shortest() {
39     let v0: Vec<i32> = vec![0, 2, 4];
40     let v1: Vec<i32> = vec![1, 3, 5, 7];
41     let it = v0.into_iter().interleave_shortest(v1.into_iter());
42     assert_eq!(it.size_hint(), (6, Some(6)));
43     assert_eq!(it.collect_vec(), vec![0, 1, 2, 3, 4, 5]);
44 
45     let v0: Vec<i32> = vec![0, 2, 4, 6, 8];
46     let v1: Vec<i32> = vec![1, 3, 5];
47     let it = v0.into_iter().interleave_shortest(v1.into_iter());
48     assert_eq!(it.size_hint(), (7, Some(7)));
49     assert_eq!(it.collect_vec(), vec![0, 1, 2, 3, 4, 5, 6]);
50 
51     let i0 = ::std::iter::repeat(0);
52     let v1: Vec<_> = vec![1, 3, 5];
53     let it = i0.interleave_shortest(v1.into_iter());
54     assert_eq!(it.size_hint(), (7, Some(7)));
55 
56     let v0: Vec<_> = vec![0, 2, 4];
57     let i1 = ::std::iter::repeat(1);
58     let it = v0.into_iter().interleave_shortest(i1);
59     assert_eq!(it.size_hint(), (6, Some(6)));
60 }
61 
62 #[test]
duplicates_by()63 fn duplicates_by() {
64     let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"];
65     let ys = ["aa", "bbbb", "cccc"];
66     it::assert_equal(ys.iter(), xs.iter().duplicates_by(|x| x[..2].to_string()));
67     it::assert_equal(ys.iter(), xs.iter().rev().duplicates_by(|x| x[..2].to_string()).rev());
68     let ys_rev = ["ccc", "aa", "bbbbb"];
69     it::assert_equal(ys_rev.iter(), xs.iter().duplicates_by(|x| x[..2].to_string()).rev());
70 }
71 
72 #[test]
duplicates()73 fn duplicates() {
74     let xs = [0, 1, 2, 3, 2, 1, 3];
75     let ys = [2, 1, 3];
76     it::assert_equal(ys.iter(), xs.iter().duplicates());
77     it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev());
78     let ys_rev = [3, 2, 1];
79     it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev());
80 
81     let xs = [0, 1, 0, 1];
82     let ys = [0, 1];
83     it::assert_equal(ys.iter(), xs.iter().duplicates());
84     it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev());
85     let ys_rev = [1, 0];
86     it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev());
87 
88     let xs = vec![0, 1, 2, 1, 2];
89     let ys = vec![1, 2];
90     assert_eq!(ys, xs.iter().duplicates().cloned().collect_vec());
91     assert_eq!(ys, xs.iter().rev().duplicates().rev().cloned().collect_vec());
92     let ys_rev = vec![2, 1];
93     assert_eq!(ys_rev, xs.iter().duplicates().rev().cloned().collect_vec());
94 }
95 
96 #[test]
unique_by()97 fn unique_by() {
98     let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"];
99     let ys = ["aaa", "bbbbb", "ccc"];
100     it::assert_equal(ys.iter(), xs.iter().unique_by(|x| x[..2].to_string()));
101     it::assert_equal(ys.iter(), xs.iter().rev().unique_by(|x| x[..2].to_string()).rev());
102     let ys_rev = ["cccc", "aaaaa", "bbbb"];
103     it::assert_equal(ys_rev.iter(), xs.iter().unique_by(|x| x[..2].to_string()).rev());
104 }
105 
106 #[test]
unique()107 fn unique() {
108     let xs = [0, 1, 2, 3, 2, 1, 3];
109     let ys = [0, 1, 2, 3];
110     it::assert_equal(ys.iter(), xs.iter().unique());
111     it::assert_equal(ys.iter(), xs.iter().rev().unique().rev());
112     let ys_rev = [3, 1, 2, 0];
113     it::assert_equal(ys_rev.iter(), xs.iter().unique().rev());
114 
115     let xs = [0, 1];
116     let ys = [0, 1];
117     it::assert_equal(ys.iter(), xs.iter().unique());
118     it::assert_equal(ys.iter(), xs.iter().rev().unique().rev());
119     let ys_rev = [1, 0];
120     it::assert_equal(ys_rev.iter(), xs.iter().unique().rev());
121 }
122 
123 #[test]
intersperse()124 fn intersperse() {
125     let xs = ["a", "", "b", "c"];
126     let v: Vec<&str> = xs.iter().map(|x| x.clone()).intersperse(", ").collect();
127     let text: String = v.concat();
128     assert_eq!(text, "a, , b, c".to_string());
129 
130     let ys = [0, 1, 2, 3];
131     let mut it = ys[..0].iter().map(|x| *x).intersperse(1);
132     assert!(it.next() == None);
133 }
134 
135 #[test]
dedup()136 fn dedup() {
137     let xs = [0, 1, 1, 1, 2, 1, 3, 3];
138     let ys = [0, 1, 2, 1, 3];
139     it::assert_equal(ys.iter(), xs.iter().dedup());
140     let xs = [0, 0, 0, 0, 0];
141     let ys = [0];
142     it::assert_equal(ys.iter(), xs.iter().dedup());
143 
144     let xs = [0, 1, 1, 1, 2, 1, 3, 3];
145     let ys = [0, 1, 2, 1, 3];
146     let mut xs_d = Vec::new();
147     xs.iter().dedup().fold((), |(), &elt| xs_d.push(elt));
148     assert_eq!(&xs_d, &ys);
149 }
150 
151 #[test]
coalesce()152 fn coalesce() {
153     let data = vec![-1., -2., -3., 3., 1., 0., -1.];
154     let it = data.iter().cloned().coalesce(|x, y|
155         if (x >= 0.) == (y >= 0.) {
156             Ok(x + y)
157         } else {
158             Err((x, y))
159         }
160     );
161     itertools::assert_equal(it.clone(), vec![-6., 4., -1.]);
162     assert_eq!(
163         it.fold(vec![], |mut v, n| {
164             v.push(n);
165             v
166         }),
167         vec![-6., 4., -1.]
168     );
169 }
170 
171 #[test]
dedup_by()172 fn dedup_by() {
173     let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)];
174     let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)];
175     it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.1==y.1));
176     let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)];
177     let ys = [(0, 1)];
178     it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.0==y.0));
179 
180     let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)];
181     let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)];
182     let mut xs_d = Vec::new();
183     xs.iter().dedup_by(|x, y| x.1==y.1).fold((), |(), &elt| xs_d.push(elt));
184     assert_eq!(&xs_d, &ys);
185 }
186 
187 #[test]
dedup_with_count()188 fn dedup_with_count() {
189     let xs: [i32; 8] = [0, 1, 1, 1, 2, 1, 3, 3];
190     let ys: [(usize, &i32); 5] = [(1, &0), (3, &1), (1, &2), (1, &1), (2, &3)];
191 
192     it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count());
193 
194     let xs: [i32; 5] = [0, 0, 0, 0, 0];
195     let ys: [(usize, &i32); 1] = [(5, &0)];
196 
197     it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count());
198 }
199 
200 
201 #[test]
dedup_by_with_count()202 fn dedup_by_with_count() {
203     let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)];
204     let ys = [(1, &(0, 0)), (3, &(0, 1)), (1, &(0, 2)), (1, &(3, 1)), (2, &(0, 3))];
205 
206     it::assert_equal(ys.iter().cloned(), xs.iter().dedup_by_with_count(|x, y| x.1==y.1));
207 
208     let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)];
209     let ys = [( 5, &(0, 1))];
210 
211     it::assert_equal(ys.iter().cloned(), xs.iter().dedup_by_with_count(|x, y| x.0==y.0));
212 }
213 
214 #[test]
all_equal()215 fn all_equal() {
216     assert!("".chars().all_equal());
217     assert!("A".chars().all_equal());
218     assert!(!"AABBCCC".chars().all_equal());
219     assert!("AAAAAAA".chars().all_equal());
220     for (_key, mut sub) in &"AABBCCC".chars().group_by(|&x| x) {
221         assert!(sub.all_equal());
222     }
223 }
224 
225 #[test]
all_unique()226 fn all_unique() {
227     assert!("ABCDEFGH".chars().all_unique());
228     assert!(!"ABCDEFGA".chars().all_unique());
229     assert!(::std::iter::empty::<usize>().all_unique());
230 }
231 
232 #[test]
test_put_back_n()233 fn test_put_back_n() {
234     let xs = [0, 1, 1, 1, 2, 1, 3, 3];
235     let mut pb = put_back_n(xs.iter().cloned());
236     pb.next();
237     pb.next();
238     pb.put_back(1);
239     pb.put_back(0);
240     it::assert_equal(pb, xs.iter().cloned());
241 }
242 
243 #[test]
tee()244 fn tee() {
245     let xs  = [0, 1, 2, 3];
246     let (mut t1, mut t2) = xs.iter().cloned().tee();
247     assert_eq!(t1.next(), Some(0));
248     assert_eq!(t2.next(), Some(0));
249     assert_eq!(t1.next(), Some(1));
250     assert_eq!(t1.next(), Some(2));
251     assert_eq!(t1.next(), Some(3));
252     assert_eq!(t1.next(), None);
253     assert_eq!(t2.next(), Some(1));
254     assert_eq!(t2.next(), Some(2));
255     assert_eq!(t1.next(), None);
256     assert_eq!(t2.next(), Some(3));
257     assert_eq!(t2.next(), None);
258     assert_eq!(t1.next(), None);
259     assert_eq!(t2.next(), None);
260 
261     let (t1, t2) = xs.iter().cloned().tee();
262     it::assert_equal(t1, xs.iter().cloned());
263     it::assert_equal(t2, xs.iter().cloned());
264 
265     let (t1, t2) = xs.iter().cloned().tee();
266     it::assert_equal(t1.zip(t2), xs.iter().cloned().zip(xs.iter().cloned()));
267 }
268 
269 
270 #[test]
test_rciter()271 fn test_rciter() {
272     let xs = [0, 1, 1, 1, 2, 1, 3, 5, 6];
273 
274     let mut r1 = rciter(xs.iter().cloned());
275     let mut r2 = r1.clone();
276     assert_eq!(r1.next(), Some(0));
277     assert_eq!(r2.next(), Some(1));
278     let mut z = r1.zip(r2);
279     assert_eq!(z.next(), Some((1, 1)));
280     assert_eq!(z.next(), Some((2, 1)));
281     assert_eq!(z.next(), Some((3, 5)));
282     assert_eq!(z.next(), None);
283 
284     // test intoiterator
285     let r1 = rciter(0..5);
286     let mut z = izip!(&r1, r1);
287     assert_eq!(z.next(), Some((0, 1)));
288 }
289 
290 #[allow(deprecated)]
291 #[test]
trait_pointers()292 fn trait_pointers() {
293     struct ByRef<'r, I: ?Sized>(&'r mut I) ;
294 
295     impl<'r, X, I: ?Sized> Iterator for ByRef<'r, I> where
296         I: 'r + Iterator<Item=X>
297     {
298         type Item = X;
299         fn next(&mut self) -> Option<Self::Item>
300         {
301             self.0.next()
302         }
303     }
304 
305     let mut it = Box::new(0..10) as Box<dyn Iterator<Item=i32>>;
306     assert_eq!(it.next(), Some(0));
307 
308     {
309         /* make sure foreach works on non-Sized */
310         let jt: &mut dyn Iterator<Item = i32> = &mut *it;
311         assert_eq!(jt.next(), Some(1));
312 
313         {
314             let mut r = ByRef(jt);
315             assert_eq!(r.next(), Some(2));
316         }
317 
318         assert_eq!(jt.find_position(|x| *x == 4), Some((1, 4)));
319         jt.foreach(|_| ());
320     }
321 }
322 
323 #[test]
merge_by()324 fn merge_by() {
325     let odd : Vec<(u32, &str)> = vec![(1, "hello"), (3, "world"), (5, "!")];
326     let even = vec![(2, "foo"), (4, "bar"), (6, "baz")];
327     let expected = vec![(1, "hello"), (2, "foo"), (3, "world"), (4, "bar"), (5, "!"), (6, "baz")];
328     let results = odd.iter().merge_by(even.iter(), |a, b| a.0 <= b.0);
329     it::assert_equal(results, expected.iter());
330 }
331 
332 #[test]
merge_by_btree()333 fn merge_by_btree() {
334     use std::collections::BTreeMap;
335     let mut bt1 = BTreeMap::new();
336     bt1.insert("hello", 1);
337     bt1.insert("world", 3);
338     let mut bt2 = BTreeMap::new();
339     bt2.insert("foo", 2);
340     bt2.insert("bar", 4);
341     let results = bt1.into_iter().merge_by(bt2.into_iter(), |a, b| a.0 <= b.0 );
342     let expected = vec![("bar", 4), ("foo", 2), ("hello", 1), ("world", 3)];
343     it::assert_equal(results, expected.into_iter());
344 }
345 
346 #[allow(deprecated)]
347 #[test]
kmerge()348 fn kmerge() {
349     let its = (0..4).map(|s| (s..10).step(4));
350 
351     it::assert_equal(its.kmerge(), 0..10);
352 }
353 
354 #[allow(deprecated)]
355 #[test]
kmerge_2()356 fn kmerge_2() {
357     let its = vec![3, 2, 1, 0].into_iter().map(|s| (s..10).step(4));
358 
359     it::assert_equal(its.kmerge(), 0..10);
360 }
361 
362 #[test]
kmerge_empty()363 fn kmerge_empty() {
364     let its = (0..4).map(|_| 0..0);
365     assert_eq!(its.kmerge().next(), None);
366 }
367 
368 #[test]
kmerge_size_hint()369 fn kmerge_size_hint() {
370     let its = (0..5).map(|_| (0..10));
371     assert_eq!(its.kmerge().size_hint(), (50, Some(50)));
372 }
373 
374 #[test]
kmerge_empty_size_hint()375 fn kmerge_empty_size_hint() {
376     let its = (0..5).map(|_| (0..0));
377     assert_eq!(its.kmerge().size_hint(), (0, Some(0)));
378 }
379 
380 #[test]
join()381 fn join() {
382     let many = [1, 2, 3];
383     let one  = [1];
384     let none: Vec<i32> = vec![];
385 
386     assert_eq!(many.iter().join(", "), "1, 2, 3");
387     assert_eq!( one.iter().join(", "), "1");
388     assert_eq!(none.iter().join(", "), "");
389 }
390 
391 #[test]
sorted_unstable_by()392 fn sorted_unstable_by() {
393     let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| {
394         a.cmp(&b)
395     });
396     it::assert_equal(sc, vec![1, 2, 3, 4]);
397 
398     let v = (0..5).sorted_unstable_by(|&a, &b| a.cmp(&b).reverse());
399     it::assert_equal(v, vec![4, 3, 2, 1, 0]);
400 }
401 
402 #[test]
sorted_unstable_by_key()403 fn sorted_unstable_by_key() {
404     let sc = [3, 4, 1, 2].iter().cloned().sorted_unstable_by_key(|&x| x);
405     it::assert_equal(sc, vec![1, 2, 3, 4]);
406 
407     let v = (0..5).sorted_unstable_by_key(|&x| -x);
408     it::assert_equal(v, vec![4, 3, 2, 1, 0]);
409 }
410 
411 #[test]
sorted_by()412 fn sorted_by() {
413     let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| {
414         a.cmp(&b)
415     });
416     it::assert_equal(sc, vec![1, 2, 3, 4]);
417 
418     let v = (0..5).sorted_by(|&a, &b| a.cmp(&b).reverse());
419     it::assert_equal(v, vec![4, 3, 2, 1, 0]);
420 }
421 
422 qc::quickcheck! {
423     fn k_smallest_range(n: u64, m: u16, k: u16) -> () {
424         // u16 is used to constrain k and m to 0..2¹⁶,
425         //  otherwise the test could use too much memory.
426         let (k, m) = (k as u64, m as u64);
427 
428         // Generate a random permutation of n..n+m
429         let i = {
430             let mut v: Vec<u64> = (n..n.saturating_add(m)).collect();
431             v.shuffle(&mut thread_rng());
432             v.into_iter()
433         };
434 
435         // Check that taking the k smallest elements yields n..n+min(k, m)
436         it::assert_equal(
437             i.k_smallest(k as usize),
438             n..n.saturating_add(min(k, m))
439         );
440     }
441 }
442 
443 #[derive(Clone, Debug)]
444 struct RandIter<T: 'static + Clone + Send, R: 'static + Clone + Rng + SeedableRng + Send = StdRng> {
445     idx: usize,
446     len: usize,
447     rng: R,
448     _t: PhantomData<T>
449 }
450 
451 impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> Iterator for RandIter<T, R>
452 where Standard: Distribution<T> {
453     type Item = T;
next(&mut self) -> Option<T>454     fn next(&mut self) -> Option<T> {
455         if self.idx == self.len {
456             None
457         } else {
458             self.idx += 1;
459             Some(self.rng.gen())
460         }
461     }
462 }
463 
464 impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> qc::Arbitrary for RandIter<T, R> {
arbitrary<G: qc::Gen>(g: &mut G) -> Self465     fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
466         RandIter {
467             idx: 0,
468             len: g.size(),
469             rng: R::seed_from_u64(g.next_u64()),
470             _t : PhantomData{},
471         }
472     }
473 }
474 
475 // Check that taking the k smallest is the same as
476 //  sorting then taking the k first elements
k_smallest_sort<I>(i: I, k: u16) -> () where I: Iterator + Clone, I::Item: Ord + Debug,477 fn k_smallest_sort<I>(i: I, k: u16) -> ()
478 where
479     I: Iterator + Clone,
480     I::Item: Ord + Debug,
481 {
482     let j = i.clone();
483     let k = k as usize;
484     it::assert_equal(
485         i.k_smallest(k),
486         j.sorted().take(k)
487     )
488 }
489 
490 macro_rules! generic_test {
491     ($f:ident, $($t:ty),+) => {
492         $(paste::item! {
493             qc::quickcheck! {
494                 fn [< $f _ $t >](i: RandIter<$t>, k: u16) -> () {
495                     $f(i, k)
496                 }
497             }
498         })+
499     };
500 }
501 
502 generic_test!(k_smallest_sort, u8, u16, u32, u64, i8, i16, i32, i64);
503 
504 #[test]
sorted_by_key()505 fn sorted_by_key() {
506     let sc = [3, 4, 1, 2].iter().cloned().sorted_by_key(|&x| x);
507     it::assert_equal(sc, vec![1, 2, 3, 4]);
508 
509     let v = (0..5).sorted_by_key(|&x| -x);
510     it::assert_equal(v, vec![4, 3, 2, 1, 0]);
511 }
512 
513 #[test]
sorted_by_cached_key()514 fn sorted_by_cached_key() {
515     // Track calls to key function
516     let mut ncalls = 0;
517 
518     let sorted = [3, 4, 1, 2].iter().cloned().sorted_by_cached_key(|&x| {
519         ncalls += 1;
520         x.to_string()
521     });
522     it::assert_equal(sorted, vec![1, 2, 3, 4]);
523     // Check key function called once per element
524     assert_eq!(ncalls, 4);
525 
526     let mut ncalls = 0;
527 
528     let sorted = (0..5).sorted_by_cached_key(|&x| {
529         ncalls += 1;
530         -x
531     });
532     it::assert_equal(sorted, vec![4, 3, 2, 1, 0]);
533     // Check key function called once per element
534     assert_eq!(ncalls, 5);
535 }
536 
537 #[test]
test_multipeek()538 fn test_multipeek() {
539     let nums = vec![1u8,2,3,4,5];
540 
541     let mp = multipeek(nums.iter().map(|&x| x));
542     assert_eq!(nums, mp.collect::<Vec<_>>());
543 
544     let mut mp = multipeek(nums.iter().map(|&x| x));
545     assert_eq!(mp.peek(), Some(&1));
546     assert_eq!(mp.next(), Some(1));
547     assert_eq!(mp.peek(), Some(&2));
548     assert_eq!(mp.peek(), Some(&3));
549     assert_eq!(mp.next(), Some(2));
550     assert_eq!(mp.peek(), Some(&3));
551     assert_eq!(mp.peek(), Some(&4));
552     assert_eq!(mp.peek(), Some(&5));
553     assert_eq!(mp.peek(), None);
554     assert_eq!(mp.next(), Some(3));
555     assert_eq!(mp.next(), Some(4));
556     assert_eq!(mp.peek(), Some(&5));
557     assert_eq!(mp.peek(), None);
558     assert_eq!(mp.next(), Some(5));
559     assert_eq!(mp.next(), None);
560     assert_eq!(mp.peek(), None);
561 }
562 
563 #[test]
test_multipeek_reset()564 fn test_multipeek_reset() {
565     let data = [1, 2, 3, 4];
566 
567     let mut mp = multipeek(cloned(&data));
568     assert_eq!(mp.peek(), Some(&1));
569     assert_eq!(mp.next(), Some(1));
570     assert_eq!(mp.peek(), Some(&2));
571     assert_eq!(mp.peek(), Some(&3));
572     mp.reset_peek();
573     assert_eq!(mp.peek(), Some(&2));
574     assert_eq!(mp.next(), Some(2));
575 }
576 
577 #[test]
test_multipeek_peeking_next()578 fn test_multipeek_peeking_next() {
579     use crate::it::PeekingNext;
580     let nums = vec![1u8,2,3,4,5,6,7];
581 
582     let mut mp = multipeek(nums.iter().map(|&x| x));
583     assert_eq!(mp.peeking_next(|&x| x != 0), Some(1));
584     assert_eq!(mp.next(), Some(2));
585     assert_eq!(mp.peek(), Some(&3));
586     assert_eq!(mp.peek(), Some(&4));
587     assert_eq!(mp.peeking_next(|&x| x == 3), Some(3));
588     assert_eq!(mp.peek(), Some(&4));
589     assert_eq!(mp.peeking_next(|&x| x != 4), None);
590     assert_eq!(mp.peeking_next(|&x| x == 4), Some(4));
591     assert_eq!(mp.peek(), Some(&5));
592     assert_eq!(mp.peek(), Some(&6));
593     assert_eq!(mp.peeking_next(|&x| x != 5), None);
594     assert_eq!(mp.peek(), Some(&7));
595     assert_eq!(mp.peeking_next(|&x| x == 5), Some(5));
596     assert_eq!(mp.peeking_next(|&x| x == 6), Some(6));
597     assert_eq!(mp.peek(), Some(&7));
598     assert_eq!(mp.peek(), None);
599     assert_eq!(mp.next(), Some(7));
600     assert_eq!(mp.peek(), None);
601 }
602 
603 #[test]
test_peek_nth()604 fn test_peek_nth() {
605     let nums = vec![1u8,2,3,4,5];
606 
607     let iter = peek_nth(nums.iter().map(|&x| x));
608     assert_eq!(nums, iter.collect::<Vec<_>>());
609 
610     let mut iter = peek_nth(nums.iter().map(|&x| x));
611 
612     assert_eq!(iter.peek_nth(0), Some(&1));
613     assert_eq!(iter.peek_nth(0), Some(&1));
614     assert_eq!(iter.next(), Some(1));
615 
616     assert_eq!(iter.peek_nth(0), Some(&2));
617     assert_eq!(iter.peek_nth(1), Some(&3));
618     assert_eq!(iter.next(), Some(2));
619 
620     assert_eq!(iter.peek_nth(0), Some(&3));
621     assert_eq!(iter.peek_nth(1), Some(&4));
622     assert_eq!(iter.peek_nth(2), Some(&5));
623     assert_eq!(iter.peek_nth(3), None);
624 
625     assert_eq!(iter.next(), Some(3));
626     assert_eq!(iter.next(), Some(4));
627 
628     assert_eq!(iter.peek_nth(0), Some(&5));
629     assert_eq!(iter.peek_nth(1), None);
630     assert_eq!(iter.next(), Some(5));
631     assert_eq!(iter.next(), None);
632 
633     assert_eq!(iter.peek_nth(0), None);
634     assert_eq!(iter.peek_nth(1), None);
635 }
636 
637 #[test]
test_peek_nth_peeking_next()638 fn test_peek_nth_peeking_next() {
639     use it::PeekingNext;
640     let nums = vec![1u8,2,3,4,5,6,7];
641     let mut iter = peek_nth(nums.iter().map(|&x| x));
642 
643     assert_eq!(iter.peeking_next(|&x| x != 0), Some(1));
644     assert_eq!(iter.next(), Some(2));
645 
646     assert_eq!(iter.peek_nth(0), Some(&3));
647     assert_eq!(iter.peek_nth(1), Some(&4));
648     assert_eq!(iter.peeking_next(|&x| x == 3), Some(3));
649     assert_eq!(iter.peek(), Some(&4));
650 
651     assert_eq!(iter.peeking_next(|&x| x != 4), None);
652     assert_eq!(iter.peeking_next(|&x| x == 4), Some(4));
653     assert_eq!(iter.peek_nth(0), Some(&5));
654     assert_eq!(iter.peek_nth(1), Some(&6));
655 
656     assert_eq!(iter.peeking_next(|&x| x != 5), None);
657     assert_eq!(iter.peek(), Some(&5));
658 
659     assert_eq!(iter.peeking_next(|&x| x == 5), Some(5));
660     assert_eq!(iter.peeking_next(|&x| x == 6), Some(6));
661     assert_eq!(iter.peek_nth(0), Some(&7));
662     assert_eq!(iter.peek_nth(1), None);
663     assert_eq!(iter.next(), Some(7));
664     assert_eq!(iter.peek(), None);
665 }
666 
667 #[test]
pad_using()668 fn pad_using() {
669     it::assert_equal((0..0).pad_using(1, |_| 1), 1..2);
670 
671     let v: Vec<usize> = vec![0, 1, 2];
672     let r = v.into_iter().pad_using(5, |n| n);
673     it::assert_equal(r, vec![0, 1, 2, 3, 4]);
674 
675     let v: Vec<usize> = vec![0, 1, 2];
676     let r = v.into_iter().pad_using(1, |_| panic!());
677     it::assert_equal(r, vec![0, 1, 2]);
678 }
679 
680 #[test]
group_by()681 fn group_by() {
682     for (ch1, sub) in &"AABBCCC".chars().group_by(|&x| x) {
683         for ch2 in sub {
684             assert_eq!(ch1, ch2);
685         }
686     }
687 
688     for (ch1, sub) in &"AAABBBCCCCDDDD".chars().group_by(|&x| x) {
689         for ch2 in sub {
690             assert_eq!(ch1, ch2);
691             if ch1 == 'C' {
692                 break;
693             }
694         }
695     }
696 
697     let toupper = |ch: &char| ch.to_uppercase().nth(0).unwrap();
698 
699     // try all possible orderings
700     for indices in permutohedron::Heap::new(&mut [0, 1, 2, 3]) {
701         let groups = "AaaBbbccCcDDDD".chars().group_by(&toupper);
702         let mut subs = groups.into_iter().collect_vec();
703 
704         for &idx in &indices[..] {
705             let (key, text) = match idx {
706                  0 => ('A', "Aaa".chars()),
707                  1 => ('B', "Bbb".chars()),
708                  2 => ('C', "ccCc".chars()),
709                  3 => ('D', "DDDD".chars()),
710                  _ => unreachable!(),
711             };
712             assert_eq!(key, subs[idx].0);
713             it::assert_equal(&mut subs[idx].1, text);
714         }
715     }
716 
717     let groups = "AAABBBCCCCDDDD".chars().group_by(|&x| x);
718     let mut subs = groups.into_iter().map(|(_, g)| g).collect_vec();
719 
720     let sd = subs.pop().unwrap();
721     let sc = subs.pop().unwrap();
722     let sb = subs.pop().unwrap();
723     let sa = subs.pop().unwrap();
724     for (a, b, c, d) in multizip((sa, sb, sc, sd)) {
725         assert_eq!(a, 'A');
726         assert_eq!(b, 'B');
727         assert_eq!(c, 'C');
728         assert_eq!(d, 'D');
729     }
730 
731     // check that the key closure is called exactly n times
732     {
733         let mut ntimes = 0;
734         let text = "AABCCC";
735         for (_, sub) in &text.chars().group_by(|&x| { ntimes += 1; x}) {
736             for _ in sub {
737             }
738         }
739         assert_eq!(ntimes, text.len());
740     }
741 
742     {
743         let mut ntimes = 0;
744         let text = "AABCCC";
745         for _ in &text.chars().group_by(|&x| { ntimes += 1; x}) {
746         }
747         assert_eq!(ntimes, text.len());
748     }
749 
750     {
751         let text = "ABCCCDEEFGHIJJKK";
752         let gr = text.chars().group_by(|&x| x);
753         it::assert_equal(gr.into_iter().flat_map(|(_, sub)| sub), text.chars());
754     }
755 }
756 
757 #[test]
group_by_lazy_2()758 fn group_by_lazy_2() {
759     let data = vec![0, 1];
760     let groups = data.iter().group_by(|k| *k);
761     let gs = groups.into_iter().collect_vec();
762     it::assert_equal(data.iter(), gs.into_iter().flat_map(|(_k, g)| g));
763 
764     let data = vec![0, 1, 1, 0, 0];
765     let groups = data.iter().group_by(|k| *k);
766     let mut gs = groups.into_iter().collect_vec();
767     gs[1..].reverse();
768     it::assert_equal(&[0, 0, 0, 1, 1], gs.into_iter().flat_map(|(_, g)| g));
769 
770     let grouper = data.iter().group_by(|k| *k);
771     let mut groups = Vec::new();
772     for (k, group) in &grouper {
773         if *k == 1 {
774             groups.push(group);
775         }
776     }
777     it::assert_equal(&mut groups[0], &[1, 1]);
778 
779     let data = vec![0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
780     let grouper = data.iter().group_by(|k| *k);
781     let mut groups = Vec::new();
782     for (i, (_, group)) in grouper.into_iter().enumerate() {
783         if i < 2 {
784             groups.push(group);
785         } else if i < 4 {
786             for _ in group {
787             }
788         } else {
789             groups.push(group);
790         }
791     }
792     it::assert_equal(&mut groups[0], &[0, 0, 0]);
793     it::assert_equal(&mut groups[1], &[1, 1]);
794     it::assert_equal(&mut groups[2], &[3, 3]);
795 
796     // use groups as chunks
797     let data = vec![0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
798     let mut i = 0;
799     let grouper = data.iter().group_by(move |_| { let k = i / 3; i += 1; k });
800     for (i, group) in &grouper {
801         match i {
802             0 => it::assert_equal(group, &[0, 0, 0]),
803             1 => it::assert_equal(group, &[1, 1, 0]),
804             2 => it::assert_equal(group, &[0, 2, 2]),
805             3 => it::assert_equal(group, &[3, 3]),
806             _ => unreachable!(),
807         }
808     }
809 }
810 
811 #[test]
group_by_lazy_3()812 fn group_by_lazy_3() {
813     // test consuming each group on the lap after it was produced
814     let data = vec![0, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2];
815     let grouper = data.iter().group_by(|elt| *elt);
816     let mut last = None;
817     for (key, group) in &grouper {
818         if let Some(gr) = last.take() {
819             for elt in gr {
820                 assert!(elt != key && i32::abs(elt - key) == 1);
821             }
822         }
823         last = Some(group);
824     }
825 }
826 
827 #[test]
chunks()828 fn chunks() {
829     let data = vec![0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
830     let grouper = data.iter().chunks(3);
831     for (i, chunk) in grouper.into_iter().enumerate() {
832         match i {
833             0 => it::assert_equal(chunk, &[0, 0, 0]),
834             1 => it::assert_equal(chunk, &[1, 1, 0]),
835             2 => it::assert_equal(chunk, &[0, 2, 2]),
836             3 => it::assert_equal(chunk, &[3, 3]),
837             _ => unreachable!(),
838         }
839     }
840 }
841 
842 #[test]
concat_empty()843 fn concat_empty() {
844     let data: Vec<Vec<()>> = Vec::new();
845     assert_eq!(data.into_iter().concat(), Vec::new())
846 }
847 
848 #[test]
concat_non_empty()849 fn concat_non_empty() {
850     let data = vec![vec![1,2,3], vec![4,5,6], vec![7,8,9]];
851     assert_eq!(data.into_iter().concat(), vec![1,2,3,4,5,6,7,8,9])
852 }
853 
854 #[test]
combinations()855 fn combinations() {
856     assert!((1..3).combinations(5).next().is_none());
857 
858     let it = (1..3).combinations(2);
859     it::assert_equal(it, vec![
860         vec![1, 2],
861         ]);
862 
863     let it = (1..5).combinations(2);
864     it::assert_equal(it, vec![
865         vec![1, 2],
866         vec![1, 3],
867         vec![1, 4],
868         vec![2, 3],
869         vec![2, 4],
870         vec![3, 4],
871         ]);
872 
873     it::assert_equal((0..0).tuple_combinations::<(_, _)>(), <Vec<_>>::new());
874     it::assert_equal((0..1).tuple_combinations::<(_, _)>(), <Vec<_>>::new());
875     it::assert_equal((0..2).tuple_combinations::<(_, _)>(), vec![(0, 1)]);
876 
877     it::assert_equal((0..0).combinations(2), <Vec<Vec<_>>>::new());
878     it::assert_equal((0..1).combinations(1), vec![vec![0]]);
879     it::assert_equal((0..2).combinations(1), vec![vec![0], vec![1]]);
880     it::assert_equal((0..2).combinations(2), vec![vec![0, 1]]);
881 }
882 
883 #[test]
combinations_of_too_short()884 fn combinations_of_too_short() {
885     for i in 1..10 {
886         assert!((0..0).combinations(i).next().is_none());
887         assert!((0..i - 1).combinations(i).next().is_none());
888     }
889 }
890 
891 
892 #[test]
combinations_zero()893 fn combinations_zero() {
894     it::assert_equal((1..3).combinations(0), vec![vec![]]);
895     it::assert_equal((0..0).combinations(0), vec![vec![]]);
896 }
897 
898 #[test]
permutations_zero()899 fn permutations_zero() {
900     it::assert_equal((1..3).permutations(0), vec![vec![]]);
901     it::assert_equal((0..0).permutations(0), vec![vec![]]);
902 }
903 
904 #[test]
combinations_with_replacement()905 fn combinations_with_replacement() {
906     // Pool smaller than n
907     it::assert_equal((0..1).combinations_with_replacement(2), vec![vec![0, 0]]);
908     // Pool larger than n
909     it::assert_equal(
910         (0..3).combinations_with_replacement(2),
911         vec![
912             vec![0, 0],
913             vec![0, 1],
914             vec![0, 2],
915             vec![1, 1],
916             vec![1, 2],
917             vec![2, 2],
918         ],
919     );
920     // Zero size
921     it::assert_equal(
922         (0..3).combinations_with_replacement(0),
923         vec![vec![]],
924     );
925     // Zero size on empty pool
926     it::assert_equal(
927         (0..0).combinations_with_replacement(0),
928         vec![vec![]],
929     );
930     // Empty pool
931     it::assert_equal(
932         (0..0).combinations_with_replacement(2),
933         <Vec<Vec<_>>>::new(),
934     );
935 }
936 
937 #[test]
powerset()938 fn powerset() {
939     it::assert_equal((0..0).powerset(), vec![vec![]]);
940     it::assert_equal((0..1).powerset(), vec![vec![], vec![0]]);
941     it::assert_equal((0..2).powerset(), vec![vec![], vec![0], vec![1], vec![0, 1]]);
942     it::assert_equal((0..3).powerset(), vec![
943         vec![],
944         vec![0], vec![1], vec![2],
945         vec![0, 1], vec![0, 2], vec![1, 2],
946         vec![0, 1, 2]
947     ]);
948 
949     assert_eq!((0..4).powerset().count(), 1 << 4);
950     assert_eq!((0..8).powerset().count(), 1 << 8);
951     assert_eq!((0..16).powerset().count(), 1 << 16);
952 }
953 
954 #[test]
diff_mismatch()955 fn diff_mismatch() {
956     let a = vec![1, 2, 3, 4];
957     let b = vec![1.0, 5.0, 3.0, 4.0];
958     let b_map = b.into_iter().map(|f| f as i32);
959     let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
960 
961     assert!(match diff {
962         Some(it::Diff::FirstMismatch(1, _, from_diff)) =>
963             from_diff.collect::<Vec<_>>() == vec![5, 3, 4],
964         _ => false,
965     });
966 }
967 
968 #[test]
diff_longer()969 fn diff_longer() {
970     let a = vec![1, 2, 3, 4];
971     let b = vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0];
972     let b_map = b.into_iter().map(|f| f as i32);
973     let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
974 
975     assert!(match diff {
976         Some(it::Diff::Longer(_, remaining)) =>
977             remaining.collect::<Vec<_>>() == vec![5, 6],
978         _ => false,
979     });
980 }
981 
982 #[test]
diff_shorter()983 fn diff_shorter() {
984     let a = vec![1, 2, 3, 4];
985     let b = vec![1.0, 2.0];
986     let b_map = b.into_iter().map(|f| f as i32);
987     let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
988 
989     assert!(match diff {
990         Some(it::Diff::Shorter(len, _)) => len == 2,
991         _ => false,
992     });
993 }
994 
995 #[test]
minmax()996 fn minmax() {
997     use std::cmp::Ordering;
998     use crate::it::MinMaxResult;
999 
1000     // A peculiar type: Equality compares both tuple items, but ordering only the
1001     // first item.  This is so we can check the stability property easily.
1002     #[derive(Clone, Debug, PartialEq, Eq)]
1003     struct Val(u32, u32);
1004 
1005     impl PartialOrd<Val> for Val {
1006         fn partial_cmp(&self, other: &Val) -> Option<Ordering> {
1007             self.0.partial_cmp(&other.0)
1008         }
1009     }
1010 
1011     impl Ord for Val {
1012         fn cmp(&self, other: &Val) -> Ordering {
1013             self.0.cmp(&other.0)
1014         }
1015     }
1016 
1017     assert_eq!(None::<Option<u32>>.iter().minmax(), MinMaxResult::NoElements);
1018 
1019     assert_eq!(Some(1u32).iter().minmax(), MinMaxResult::OneElement(&1));
1020 
1021     let data = vec![Val(0, 1), Val(2, 0), Val(0, 2), Val(1, 0), Val(2, 1)];
1022 
1023     let minmax = data.iter().minmax();
1024     assert_eq!(minmax, MinMaxResult::MinMax(&Val(0, 1), &Val(2, 1)));
1025 
1026     let (min, max) = data.iter().minmax_by_key(|v| v.1).into_option().unwrap();
1027     assert_eq!(min, &Val(2, 0));
1028     assert_eq!(max, &Val(0, 2));
1029 
1030     let (min, max) = data.iter().minmax_by(|x, y| x.1.cmp(&y.1)).into_option().unwrap();
1031     assert_eq!(min, &Val(2, 0));
1032     assert_eq!(max, &Val(0, 2));
1033 }
1034 
1035 #[test]
format()1036 fn format() {
1037     let data = [0, 1, 2, 3];
1038     let ans1 = "0, 1, 2, 3";
1039     let ans2 = "0--1--2--3";
1040 
1041     let t1 = format!("{}", data.iter().format(", "));
1042     assert_eq!(t1, ans1);
1043     let t2 = format!("{:?}", data.iter().format("--"));
1044     assert_eq!(t2, ans2);
1045 
1046     let dataf = [1.1, 2.71828, -22.];
1047     let t3 = format!("{:.2e}", dataf.iter().format(", "));
1048     assert_eq!(t3, "1.10e0, 2.72e0, -2.20e1");
1049 }
1050 
1051 #[test]
while_some()1052 fn while_some() {
1053     let ns = (1..10).map(|x| if x % 5 != 0 { Some(x) } else { None })
1054                     .while_some();
1055     it::assert_equal(ns, vec![1, 2, 3, 4]);
1056 }
1057 
1058 #[allow(deprecated)]
1059 #[test]
fold_while()1060 fn fold_while() {
1061     let mut iterations = 0;
1062     let vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1063     let sum = vec.into_iter().fold_while(0, |acc, item| {
1064         iterations += 1;
1065         let new_sum = acc.clone() + item;
1066         if new_sum <= 20 {
1067             FoldWhile::Continue(new_sum)
1068         } else {
1069             FoldWhile::Done(acc)
1070         }
1071     }).into_inner();
1072     assert_eq!(iterations, 6);
1073     assert_eq!(sum, 15);
1074 }
1075 
1076 #[test]
tree_fold1()1077 fn tree_fold1() {
1078     let x = [
1079         "",
1080         "0",
1081         "0 1 x",
1082         "0 1 x 2 x",
1083         "0 1 x 2 3 x x",
1084         "0 1 x 2 3 x x 4 x",
1085         "0 1 x 2 3 x x 4 5 x x",
1086         "0 1 x 2 3 x x 4 5 x 6 x x",
1087         "0 1 x 2 3 x x 4 5 x 6 7 x x x",
1088         "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 x",
1089         "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x x",
1090         "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 x x",
1091         "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x x",
1092         "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x 12 x x",
1093         "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x 12 13 x x x",
1094         "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x 12 13 x 14 x x x",
1095         "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x 12 13 x 14 15 x x x x",
1096     ];
1097     for (i, &s) in x.iter().enumerate() {
1098         let expected = if s == "" { None } else { Some(s.to_string()) };
1099         let num_strings = (0..i).map(|x| x.to_string());
1100         let actual = num_strings.tree_fold1(|a, b| format!("{} {} x", a, b));
1101         assert_eq!(actual, expected);
1102     }
1103 }
1104 
1105 #[test]
exactly_one_question_mark_syntax_works()1106 fn exactly_one_question_mark_syntax_works() {
1107     exactly_one_question_mark_return().unwrap_err();
1108 }
1109 
exactly_one_question_mark_return() -> Result<(), ExactlyOneError<std::slice::Iter<'static, ()>>>1110 fn exactly_one_question_mark_return() -> Result<(), ExactlyOneError<std::slice::Iter<'static, ()>>> {
1111     [].iter().exactly_one()?;
1112     Ok(())
1113 }
1114 
1115 #[test]
multiunzip()1116 fn multiunzip() {
1117     let (a, b, c): (Vec<_>, Vec<_>, Vec<_>) = [(0, 1, 2), (3, 4, 5), (6, 7, 8)].iter().cloned().multiunzip();
1118     assert_eq!((a, b, c), (vec![0, 3, 6], vec![1, 4, 7], vec![2, 5, 8]));
1119     let (): () = [(), (), ()].iter().cloned().multiunzip();
1120     let t: (Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>) = [(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)].iter().cloned().multiunzip();
1121     assert_eq!(t, (vec![0], vec![1], vec![2], vec![3], vec![4], vec![5], vec![6], vec![7], vec![8], vec![9], vec![10], vec![11]));
1122 }