1 #![allow(unstable_name_collisions)]
2 
3 use crate::it::cloned;
4 use crate::it::free::put_back_n;
5 use crate::it::free::rciter;
6 use crate::it::iproduct;
7 use crate::it::izip;
8 use crate::it::multipeek;
9 use crate::it::multizip;
10 use crate::it::peek_nth;
11 use crate::it::repeat_n;
12 use crate::it::ExactlyOneError;
13 use crate::it::FoldWhile;
14 use crate::it::Itertools;
15 use itertools as it;
16 use quickcheck as qc;
17 use rand::{
18     distributions::{Distribution, Standard},
19     rngs::StdRng,
20     Rng, SeedableRng,
21 };
22 use rand::{seq::SliceRandom, thread_rng};
23 use std::{cmp::min, fmt::Debug, marker::PhantomData};
24 
25 #[test]
product3()26 fn product3() {
27     let prod = iproduct!(0..3, 0..2, 0..2);
28     assert_eq!(prod.size_hint(), (12, Some(12)));
29     let v = prod.collect_vec();
30     for i in 0..3 {
31         for j in 0..2 {
32             for k in 0..2 {
33                 assert!((i, j, k) == v[(i * 2 * 2 + j * 2 + k) as usize]);
34             }
35         }
36     }
37     for (_, _, _, _) in iproduct!(0..3, 0..2, 0..2, 0..3) { /* test compiles */ }
38 }
39 
40 #[test]
interleave_shortest()41 fn interleave_shortest() {
42     let v0: Vec<i32> = vec![0, 2, 4];
43     let v1: Vec<i32> = vec![1, 3, 5, 7];
44     let it = v0.into_iter().interleave_shortest(v1);
45     assert_eq!(it.size_hint(), (6, Some(6)));
46     assert_eq!(it.collect_vec(), vec![0, 1, 2, 3, 4, 5]);
47 
48     let v0: Vec<i32> = vec![0, 2, 4, 6, 8];
49     let v1: Vec<i32> = vec![1, 3, 5];
50     let it = v0.into_iter().interleave_shortest(v1);
51     assert_eq!(it.size_hint(), (7, Some(7)));
52     assert_eq!(it.collect_vec(), vec![0, 1, 2, 3, 4, 5, 6]);
53 
54     let i0 = ::std::iter::repeat(0);
55     let v1: Vec<_> = vec![1, 3, 5];
56     let it = i0.interleave_shortest(v1);
57     assert_eq!(it.size_hint(), (7, Some(7)));
58 
59     let v0: Vec<_> = vec![0, 2, 4];
60     let i1 = ::std::iter::repeat(1);
61     let it = v0.into_iter().interleave_shortest(i1);
62     assert_eq!(it.size_hint(), (6, Some(6)));
63 }
64 
65 #[test]
duplicates_by()66 fn duplicates_by() {
67     let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"];
68     let ys = ["aa", "bbbb", "cccc"];
69     it::assert_equal(ys.iter(), xs.iter().duplicates_by(|x| x[..2].to_string()));
70     it::assert_equal(
71         ys.iter(),
72         xs.iter().rev().duplicates_by(|x| x[..2].to_string()).rev(),
73     );
74     let ys_rev = ["ccc", "aa", "bbbbb"];
75     it::assert_equal(
76         ys_rev.iter(),
77         xs.iter().duplicates_by(|x| x[..2].to_string()).rev(),
78     );
79 }
80 
81 #[test]
duplicates()82 fn duplicates() {
83     let xs = [0, 1, 2, 3, 2, 1, 3];
84     let ys = [2, 1, 3];
85     it::assert_equal(ys.iter(), xs.iter().duplicates());
86     it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev());
87     let ys_rev = [3, 2, 1];
88     it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev());
89 
90     let xs = [0, 1, 0, 1];
91     let ys = [0, 1];
92     it::assert_equal(ys.iter(), xs.iter().duplicates());
93     it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev());
94     let ys_rev = [1, 0];
95     it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev());
96 
97     let xs = [0, 1, 2, 1, 2];
98     let ys = vec![1, 2];
99     assert_eq!(ys, xs.iter().duplicates().cloned().collect_vec());
100     assert_eq!(
101         ys,
102         xs.iter().rev().duplicates().rev().cloned().collect_vec()
103     );
104     let ys_rev = vec![2, 1];
105     assert_eq!(ys_rev, xs.iter().duplicates().rev().cloned().collect_vec());
106 }
107 
108 #[test]
unique_by()109 fn unique_by() {
110     let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"];
111     let ys = ["aaa", "bbbbb", "ccc"];
112     it::assert_equal(ys.iter(), xs.iter().unique_by(|x| x[..2].to_string()));
113     it::assert_equal(
114         ys.iter(),
115         xs.iter().rev().unique_by(|x| x[..2].to_string()).rev(),
116     );
117     let ys_rev = ["cccc", "aaaaa", "bbbb"];
118     it::assert_equal(
119         ys_rev.iter(),
120         xs.iter().unique_by(|x| x[..2].to_string()).rev(),
121     );
122 }
123 
124 #[test]
unique()125 fn unique() {
126     let xs = [0, 1, 2, 3, 2, 1, 3];
127     let ys = [0, 1, 2, 3];
128     it::assert_equal(ys.iter(), xs.iter().unique());
129     it::assert_equal(ys.iter(), xs.iter().rev().unique().rev());
130     let ys_rev = [3, 1, 2, 0];
131     it::assert_equal(ys_rev.iter(), xs.iter().unique().rev());
132 
133     let xs = [0, 1];
134     let ys = [0, 1];
135     it::assert_equal(ys.iter(), xs.iter().unique());
136     it::assert_equal(ys.iter(), xs.iter().rev().unique().rev());
137     let ys_rev = [1, 0];
138     it::assert_equal(ys_rev.iter(), xs.iter().unique().rev());
139 }
140 
141 #[test]
intersperse()142 fn intersperse() {
143     let xs = ["a", "", "b", "c"];
144     let v: Vec<&str> = xs.iter().cloned().intersperse(", ").collect();
145     let text: String = v.concat();
146     assert_eq!(text, "a, , b, c".to_string());
147 
148     let ys = [0, 1, 2, 3];
149     let mut it = ys[..0].iter().copied().intersperse(1);
150     assert!(it.next().is_none());
151 }
152 
153 #[test]
dedup()154 fn dedup() {
155     let xs = [0, 1, 1, 1, 2, 1, 3, 3];
156     let ys = [0, 1, 2, 1, 3];
157     it::assert_equal(ys.iter(), xs.iter().dedup());
158     let xs = [0, 0, 0, 0, 0];
159     let ys = [0];
160     it::assert_equal(ys.iter(), xs.iter().dedup());
161 
162     let xs = [0, 1, 1, 1, 2, 1, 3, 3];
163     let ys = [0, 1, 2, 1, 3];
164     let mut xs_d = Vec::new();
165     xs.iter().dedup().fold((), |(), &elt| xs_d.push(elt));
166     assert_eq!(&xs_d, &ys);
167 }
168 
169 #[test]
coalesce()170 fn coalesce() {
171     let data = [-1., -2., -3., 3., 1., 0., -1.];
172     let it = data.iter().cloned().coalesce(|x, y| {
173         if (x >= 0.) == (y >= 0.) {
174             Ok(x + y)
175         } else {
176             Err((x, y))
177         }
178     });
179     itertools::assert_equal(it.clone(), vec![-6., 4., -1.]);
180     assert_eq!(
181         it.fold(vec![], |mut v, n| {
182             v.push(n);
183             v
184         }),
185         vec![-6., 4., -1.]
186     );
187 }
188 
189 #[test]
dedup_by()190 fn dedup_by() {
191     let xs = [
192         (0, 0),
193         (0, 1),
194         (1, 1),
195         (2, 1),
196         (0, 2),
197         (3, 1),
198         (0, 3),
199         (1, 3),
200     ];
201     let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)];
202     it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.1 == y.1));
203     let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)];
204     let ys = [(0, 1)];
205     it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.0 == y.0));
206 
207     let xs = [
208         (0, 0),
209         (0, 1),
210         (1, 1),
211         (2, 1),
212         (0, 2),
213         (3, 1),
214         (0, 3),
215         (1, 3),
216     ];
217     let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)];
218     let mut xs_d = Vec::new();
219     xs.iter()
220         .dedup_by(|x, y| x.1 == y.1)
221         .fold((), |(), &elt| xs_d.push(elt));
222     assert_eq!(&xs_d, &ys);
223 }
224 
225 #[test]
dedup_with_count()226 fn dedup_with_count() {
227     let xs: [i32; 8] = [0, 1, 1, 1, 2, 1, 3, 3];
228     let ys: [(usize, &i32); 5] = [(1, &0), (3, &1), (1, &2), (1, &1), (2, &3)];
229 
230     it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count());
231 
232     let xs: [i32; 5] = [0, 0, 0, 0, 0];
233     let ys: [(usize, &i32); 1] = [(5, &0)];
234 
235     it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count());
236 }
237 
238 #[test]
dedup_by_with_count()239 fn dedup_by_with_count() {
240     let xs = [
241         (0, 0),
242         (0, 1),
243         (1, 1),
244         (2, 1),
245         (0, 2),
246         (3, 1),
247         (0, 3),
248         (1, 3),
249     ];
250     let ys = [
251         (1, &(0, 0)),
252         (3, &(0, 1)),
253         (1, &(0, 2)),
254         (1, &(3, 1)),
255         (2, &(0, 3)),
256     ];
257 
258     it::assert_equal(
259         ys.iter().cloned(),
260         xs.iter().dedup_by_with_count(|x, y| x.1 == y.1),
261     );
262 
263     let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)];
264     let ys = [(5, &(0, 1))];
265 
266     it::assert_equal(
267         ys.iter().cloned(),
268         xs.iter().dedup_by_with_count(|x, y| x.0 == y.0),
269     );
270 }
271 
272 #[test]
all_equal()273 fn all_equal() {
274     assert!("".chars().all_equal());
275     assert!("A".chars().all_equal());
276     assert!(!"AABBCCC".chars().all_equal());
277     assert!("AAAAAAA".chars().all_equal());
278     for (_key, mut sub) in &"AABBCCC".chars().chunk_by(|&x| x) {
279         assert!(sub.all_equal());
280     }
281 }
282 
283 #[test]
all_equal_value()284 fn all_equal_value() {
285     assert_eq!("".chars().all_equal_value(), Err(None));
286     assert_eq!("A".chars().all_equal_value(), Ok('A'));
287     assert_eq!("AABBCCC".chars().all_equal_value(), Err(Some(('A', 'B'))));
288     assert_eq!("AAAAAAA".chars().all_equal_value(), Ok('A'));
289     {
290         let mut it = [1, 2, 3].iter().copied();
291         let result = it.all_equal_value();
292         assert_eq!(result, Err(Some((1, 2))));
293         let remaining = it.next();
294         assert_eq!(remaining, Some(3));
295         assert!(it.next().is_none());
296     }
297 }
298 
299 #[test]
all_unique()300 fn all_unique() {
301     assert!("ABCDEFGH".chars().all_unique());
302     assert!(!"ABCDEFGA".chars().all_unique());
303     assert!(::std::iter::empty::<usize>().all_unique());
304 }
305 
306 #[test]
test_put_back_n()307 fn test_put_back_n() {
308     let xs = [0, 1, 1, 1, 2, 1, 3, 3];
309     let mut pb = put_back_n(xs.iter().cloned());
310     pb.next();
311     pb.next();
312     pb.put_back(1);
313     pb.put_back(0);
314     it::assert_equal(pb, xs.iter().cloned());
315 }
316 
317 #[test]
tee()318 fn tee() {
319     let xs = [0, 1, 2, 3];
320     let (mut t1, mut t2) = xs.iter().cloned().tee();
321     assert_eq!(t1.next(), Some(0));
322     assert_eq!(t2.next(), Some(0));
323     assert_eq!(t1.next(), Some(1));
324     assert_eq!(t1.next(), Some(2));
325     assert_eq!(t1.next(), Some(3));
326     assert_eq!(t1.next(), None);
327     assert_eq!(t2.next(), Some(1));
328     assert_eq!(t2.next(), Some(2));
329     assert_eq!(t1.next(), None);
330     assert_eq!(t2.next(), Some(3));
331     assert_eq!(t2.next(), None);
332     assert_eq!(t1.next(), None);
333     assert_eq!(t2.next(), None);
334 
335     let (t1, t2) = xs.iter().cloned().tee();
336     it::assert_equal(t1, xs.iter().cloned());
337     it::assert_equal(t2, xs.iter().cloned());
338 
339     let (t1, t2) = xs.iter().cloned().tee();
340     it::assert_equal(t1.zip(t2), xs.iter().cloned().zip(xs.iter().cloned()));
341 }
342 
343 #[test]
test_rciter()344 fn test_rciter() {
345     let xs = [0, 1, 1, 1, 2, 1, 3, 5, 6];
346 
347     let mut r1 = rciter(xs.iter().cloned());
348     let mut r2 = r1.clone();
349     assert_eq!(r1.next(), Some(0));
350     assert_eq!(r2.next(), Some(1));
351     let mut z = r1.zip(r2);
352     assert_eq!(z.next(), Some((1, 1)));
353     assert_eq!(z.next(), Some((2, 1)));
354     assert_eq!(z.next(), Some((3, 5)));
355     assert_eq!(z.next(), None);
356 
357     // test intoiterator
358     let r1 = rciter(0..5);
359     let mut z = izip!(&r1, r1);
360     assert_eq!(z.next(), Some((0, 1)));
361 }
362 
363 #[test]
trait_pointers()364 fn trait_pointers() {
365     struct ByRef<'r, I: ?Sized>(&'r mut I);
366 
367     impl<'r, X, I> Iterator for ByRef<'r, I>
368     where
369         I: ?Sized + 'r + Iterator<Item = X>,
370     {
371         type Item = X;
372         fn next(&mut self) -> Option<Self::Item> {
373             self.0.next()
374         }
375     }
376 
377     let mut it = Box::new(0..10) as Box<dyn Iterator<Item = i32>>;
378     assert_eq!(it.next(), Some(0));
379 
380     {
381         let jt: &mut dyn Iterator<Item = i32> = &mut *it;
382         assert_eq!(jt.next(), Some(1));
383 
384         {
385             let mut r = ByRef(jt);
386             assert_eq!(r.next(), Some(2));
387         }
388 
389         assert_eq!(jt.find_position(|x| *x == 4), Some((1, 4)));
390         jt.for_each(|_| ());
391     }
392 }
393 
394 #[test]
merge_by()395 fn merge_by() {
396     let odd: Vec<(u32, &str)> = vec![(1, "hello"), (3, "world"), (5, "!")];
397     let even = [(2, "foo"), (4, "bar"), (6, "baz")];
398     let expected = [
399         (1, "hello"),
400         (2, "foo"),
401         (3, "world"),
402         (4, "bar"),
403         (5, "!"),
404         (6, "baz"),
405     ];
406     let results = odd.iter().merge_by(even.iter(), |a, b| a.0 <= b.0);
407     it::assert_equal(results, expected.iter());
408 }
409 
410 #[test]
merge_by_btree()411 fn merge_by_btree() {
412     use std::collections::BTreeMap;
413     let mut bt1 = BTreeMap::new();
414     bt1.insert("hello", 1);
415     bt1.insert("world", 3);
416     let mut bt2 = BTreeMap::new();
417     bt2.insert("foo", 2);
418     bt2.insert("bar", 4);
419     let results = bt1.into_iter().merge_by(bt2, |a, b| a.0 <= b.0);
420     let expected = vec![("bar", 4), ("foo", 2), ("hello", 1), ("world", 3)];
421     it::assert_equal(results, expected);
422 }
423 
424 #[test]
kmerge()425 fn kmerge() {
426     let its = (0..4).map(|s| (s..10).step_by(4));
427 
428     it::assert_equal(its.kmerge(), 0..10);
429 }
430 
431 #[test]
kmerge_2()432 fn kmerge_2() {
433     let its = vec![3, 2, 1, 0].into_iter().map(|s| (s..10).step_by(4));
434 
435     it::assert_equal(its.kmerge(), 0..10);
436 }
437 
438 #[test]
kmerge_empty()439 fn kmerge_empty() {
440     let its = (0..4).map(|_| 0..0);
441     assert_eq!(its.kmerge().next(), None);
442 }
443 
444 #[test]
kmerge_size_hint()445 fn kmerge_size_hint() {
446     let its = (0..5).map(|_| (0..10));
447     assert_eq!(its.kmerge().size_hint(), (50, Some(50)));
448 }
449 
450 #[test]
kmerge_empty_size_hint()451 fn kmerge_empty_size_hint() {
452     let its = (0..5).map(|_| (0..0));
453     assert_eq!(its.kmerge().size_hint(), (0, Some(0)));
454 }
455 
456 #[test]
join()457 fn join() {
458     let many = [1, 2, 3];
459     let one = [1];
460     let none: Vec<i32> = vec![];
461 
462     assert_eq!(many.iter().join(", "), "1, 2, 3");
463     assert_eq!(one.iter().join(", "), "1");
464     assert_eq!(none.iter().join(", "), "");
465 }
466 
467 #[test]
sorted_unstable_by()468 fn sorted_unstable_by() {
469     let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| a.cmp(&b));
470     it::assert_equal(sc, vec![1, 2, 3, 4]);
471 
472     let v = (0..5).sorted_unstable_by(|&a, &b| a.cmp(&b).reverse());
473     it::assert_equal(v, vec![4, 3, 2, 1, 0]);
474 }
475 
476 #[test]
sorted_unstable_by_key()477 fn sorted_unstable_by_key() {
478     let sc = [3, 4, 1, 2].iter().cloned().sorted_unstable_by_key(|&x| x);
479     it::assert_equal(sc, vec![1, 2, 3, 4]);
480 
481     let v = (0..5).sorted_unstable_by_key(|&x| -x);
482     it::assert_equal(v, vec![4, 3, 2, 1, 0]);
483 }
484 
485 #[test]
sorted_by()486 fn sorted_by() {
487     let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| a.cmp(&b));
488     it::assert_equal(sc, vec![1, 2, 3, 4]);
489 
490     let v = (0..5).sorted_by(|&a, &b| a.cmp(&b).reverse());
491     it::assert_equal(v, vec![4, 3, 2, 1, 0]);
492 }
493 
494 qc::quickcheck! {
495     fn k_smallest_range(n: i64, m: u16, k: u16) -> () {
496         // u16 is used to constrain k and m to 0..2¹⁶,
497         //  otherwise the test could use too much memory.
498         let (k, m) = (k as usize, m as u64);
499 
500         let mut v: Vec<_> = (n..n.saturating_add(m as _)).collect();
501         // Generate a random permutation of n..n+m
502         v.shuffle(&mut thread_rng());
503 
504         // Construct the right answers for the top and bottom elements
505         let mut sorted = v.clone();
506         sorted.sort();
507         // how many elements are we checking
508         let num_elements = min(k, m as _);
509 
510         // Compute the top and bottom k in various combinations
511         let sorted_smallest = sorted[..num_elements].iter().cloned();
512         let smallest = v.iter().cloned().k_smallest(k);
513         let smallest_by = v.iter().cloned().k_smallest_by(k, Ord::cmp);
514         let smallest_by_key = v.iter().cloned().k_smallest_by_key(k, |&x| x);
515 
516         let sorted_largest = sorted[sorted.len() - num_elements..].iter().rev().cloned();
517         let largest = v.iter().cloned().k_largest(k);
518         let largest_by = v.iter().cloned().k_largest_by(k, Ord::cmp);
519         let largest_by_key = v.iter().cloned().k_largest_by_key(k, |&x| x);
520 
521         // Check the variations produce the same answers and that they're right
522         it::assert_equal(smallest, sorted_smallest.clone());
523         it::assert_equal(smallest_by, sorted_smallest.clone());
524         it::assert_equal(smallest_by_key, sorted_smallest);
525 
526         it::assert_equal(largest, sorted_largest.clone());
527         it::assert_equal(largest_by, sorted_largest.clone());
528         it::assert_equal(largest_by_key, sorted_largest);
529     }
530 }
531 
532 #[derive(Clone, Debug)]
533 struct RandIter<T: 'static + Clone + Send, R: 'static + Clone + Rng + SeedableRng + Send = StdRng> {
534     idx: usize,
535     len: usize,
536     rng: R,
537     _t: PhantomData<T>,
538 }
539 
540 impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> Iterator for RandIter<T, R>
541 where
542     Standard: Distribution<T>,
543 {
544     type Item = T;
next(&mut self) -> Option<T>545     fn next(&mut self) -> Option<T> {
546         if self.idx == self.len {
547             None
548         } else {
549             self.idx += 1;
550             Some(self.rng.gen())
551         }
552     }
553 }
554 
555 impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> qc::Arbitrary for RandIter<T, R> {
arbitrary<G: qc::Gen>(g: &mut G) -> Self556     fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
557         Self {
558             idx: 0,
559             len: g.size(),
560             rng: R::seed_from_u64(g.next_u64()),
561             _t: PhantomData {},
562         }
563     }
564 }
565 
566 // Check that taking the k smallest is the same as
567 //  sorting then taking the k first elements
k_smallest_sort<I>(i: I, k: u16) where I: Iterator + Clone, I::Item: Ord + Debug,568 fn k_smallest_sort<I>(i: I, k: u16)
569 where
570     I: Iterator + Clone,
571     I::Item: Ord + Debug,
572 {
573     let j = i.clone();
574     let k = k as usize;
575     it::assert_equal(i.k_smallest(k), j.sorted().take(k))
576 }
577 
578 // Similar to `k_smallest_sort` but for our custom heap implementation.
k_smallest_by_sort<I>(i: I, k: u16) where I: Iterator + Clone, I::Item: Ord + Debug,579 fn k_smallest_by_sort<I>(i: I, k: u16)
580 where
581     I: Iterator + Clone,
582     I::Item: Ord + Debug,
583 {
584     let j = i.clone();
585     let k = k as usize;
586     it::assert_equal(i.k_smallest_by(k, Ord::cmp), j.sorted().take(k))
587 }
588 
589 macro_rules! generic_test {
590     ($f:ident, $($t:ty),+) => {
591         $(paste::item! {
592             qc::quickcheck! {
593                 fn [< $f _ $t >](i: RandIter<$t>, k: u16) -> () {
594                     $f(i, k)
595                 }
596             }
597         })+
598     };
599 }
600 
601 generic_test!(k_smallest_sort, u8, u16, u32, u64, i8, i16, i32, i64);
602 generic_test!(k_smallest_by_sort, u8, u16, u32, u64, i8, i16, i32, i64);
603 
604 #[test]
sorted_by_key()605 fn sorted_by_key() {
606     let sc = [3, 4, 1, 2].iter().cloned().sorted_by_key(|&x| x);
607     it::assert_equal(sc, vec![1, 2, 3, 4]);
608 
609     let v = (0..5).sorted_by_key(|&x| -x);
610     it::assert_equal(v, vec![4, 3, 2, 1, 0]);
611 }
612 
613 #[test]
sorted_by_cached_key()614 fn sorted_by_cached_key() {
615     // Track calls to key function
616     let mut ncalls = 0;
617 
618     let sorted = [3, 4, 1, 2].iter().cloned().sorted_by_cached_key(|&x| {
619         ncalls += 1;
620         x.to_string()
621     });
622     it::assert_equal(sorted, vec![1, 2, 3, 4]);
623     // Check key function called once per element
624     assert_eq!(ncalls, 4);
625 
626     let mut ncalls = 0;
627 
628     let sorted = (0..5).sorted_by_cached_key(|&x| {
629         ncalls += 1;
630         -x
631     });
632     it::assert_equal(sorted, vec![4, 3, 2, 1, 0]);
633     // Check key function called once per element
634     assert_eq!(ncalls, 5);
635 }
636 
637 #[test]
test_multipeek()638 fn test_multipeek() {
639     let nums = vec![1u8, 2, 3, 4, 5];
640 
641     let mp = multipeek(nums.iter().copied());
642     assert_eq!(nums, mp.collect::<Vec<_>>());
643 
644     let mut mp = multipeek(nums.iter().copied());
645     assert_eq!(mp.peek(), Some(&1));
646     assert_eq!(mp.next(), Some(1));
647     assert_eq!(mp.peek(), Some(&2));
648     assert_eq!(mp.peek(), Some(&3));
649     assert_eq!(mp.next(), Some(2));
650     assert_eq!(mp.peek(), Some(&3));
651     assert_eq!(mp.peek(), Some(&4));
652     assert_eq!(mp.peek(), Some(&5));
653     assert_eq!(mp.peek(), None);
654     assert_eq!(mp.next(), Some(3));
655     assert_eq!(mp.next(), Some(4));
656     assert_eq!(mp.peek(), Some(&5));
657     assert_eq!(mp.peek(), None);
658     assert_eq!(mp.next(), Some(5));
659     assert_eq!(mp.next(), None);
660     assert_eq!(mp.peek(), None);
661 }
662 
663 #[test]
test_multipeek_reset()664 fn test_multipeek_reset() {
665     let data = [1, 2, 3, 4];
666 
667     let mut mp = multipeek(cloned(&data));
668     assert_eq!(mp.peek(), Some(&1));
669     assert_eq!(mp.next(), Some(1));
670     assert_eq!(mp.peek(), Some(&2));
671     assert_eq!(mp.peek(), Some(&3));
672     mp.reset_peek();
673     assert_eq!(mp.peek(), Some(&2));
674     assert_eq!(mp.next(), Some(2));
675 }
676 
677 #[test]
test_multipeek_peeking_next()678 fn test_multipeek_peeking_next() {
679     use crate::it::PeekingNext;
680     let nums = [1u8, 2, 3, 4, 5, 6, 7];
681 
682     let mut mp = multipeek(nums.iter().copied());
683     assert_eq!(mp.peeking_next(|&x| x != 0), Some(1));
684     assert_eq!(mp.next(), Some(2));
685     assert_eq!(mp.peek(), Some(&3));
686     assert_eq!(mp.peek(), Some(&4));
687     assert_eq!(mp.peeking_next(|&x| x == 3), Some(3));
688     assert_eq!(mp.peek(), Some(&4));
689     assert_eq!(mp.peeking_next(|&x| x != 4), None);
690     assert_eq!(mp.peeking_next(|&x| x == 4), Some(4));
691     assert_eq!(mp.peek(), Some(&5));
692     assert_eq!(mp.peek(), Some(&6));
693     assert_eq!(mp.peeking_next(|&x| x != 5), None);
694     assert_eq!(mp.peek(), Some(&7));
695     assert_eq!(mp.peeking_next(|&x| x == 5), Some(5));
696     assert_eq!(mp.peeking_next(|&x| x == 6), Some(6));
697     assert_eq!(mp.peek(), Some(&7));
698     assert_eq!(mp.peek(), None);
699     assert_eq!(mp.next(), Some(7));
700     assert_eq!(mp.peek(), None);
701 }
702 
703 #[test]
test_repeat_n_peeking_next()704 fn test_repeat_n_peeking_next() {
705     use crate::it::PeekingNext;
706     let mut rn = repeat_n(0, 5);
707     assert_eq!(rn.peeking_next(|&x| x != 0), None);
708     assert_eq!(rn.peeking_next(|&x| x <= 0), Some(0));
709     assert_eq!(rn.next(), Some(0));
710     assert_eq!(rn.peeking_next(|&x| x <= 0), Some(0));
711     assert_eq!(rn.peeking_next(|&x| x != 0), None);
712     assert_eq!(rn.peeking_next(|&x| x >= 0), Some(0));
713     assert_eq!(rn.next(), Some(0));
714     assert_eq!(rn.peeking_next(|&x| x <= 0), None);
715     assert_eq!(rn.next(), None);
716 }
717 
718 #[test]
test_peek_nth()719 fn test_peek_nth() {
720     let nums = vec![1u8, 2, 3, 4, 5];
721 
722     let iter = peek_nth(nums.iter().copied());
723     assert_eq!(nums, iter.collect::<Vec<_>>());
724 
725     let mut iter = peek_nth(nums.iter().copied());
726 
727     assert_eq!(iter.peek_nth(0), Some(&1));
728     assert_eq!(iter.peek_nth(0), Some(&1));
729     assert_eq!(iter.next(), Some(1));
730 
731     assert_eq!(iter.peek_nth(0), Some(&2));
732     assert_eq!(iter.peek_nth(1), Some(&3));
733     assert_eq!(iter.next(), Some(2));
734 
735     assert_eq!(iter.peek_nth(0), Some(&3));
736     assert_eq!(iter.peek_nth(1), Some(&4));
737     assert_eq!(iter.peek_nth(2), Some(&5));
738     assert_eq!(iter.peek_nth(3), None);
739 
740     assert_eq!(iter.next(), Some(3));
741     assert_eq!(iter.next(), Some(4));
742 
743     assert_eq!(iter.peek_nth(0), Some(&5));
744     assert_eq!(iter.peek_nth(1), None);
745     assert_eq!(iter.next(), Some(5));
746     assert_eq!(iter.next(), None);
747 
748     assert_eq!(iter.peek_nth(0), None);
749     assert_eq!(iter.peek_nth(1), None);
750 }
751 
752 #[test]
test_peek_nth_peeking_next()753 fn test_peek_nth_peeking_next() {
754     use it::PeekingNext;
755     let nums = [1u8, 2, 3, 4, 5, 6, 7];
756     let mut iter = peek_nth(nums.iter().copied());
757 
758     assert_eq!(iter.peeking_next(|&x| x != 0), Some(1));
759     assert_eq!(iter.next(), Some(2));
760 
761     assert_eq!(iter.peek_nth(0), Some(&3));
762     assert_eq!(iter.peek_nth(1), Some(&4));
763     assert_eq!(iter.peeking_next(|&x| x == 3), Some(3));
764     assert_eq!(iter.peek(), Some(&4));
765 
766     assert_eq!(iter.peeking_next(|&x| x != 4), None);
767     assert_eq!(iter.peeking_next(|&x| x == 4), Some(4));
768     assert_eq!(iter.peek_nth(0), Some(&5));
769     assert_eq!(iter.peek_nth(1), Some(&6));
770 
771     assert_eq!(iter.peeking_next(|&x| x != 5), None);
772     assert_eq!(iter.peek(), Some(&5));
773 
774     assert_eq!(iter.peeking_next(|&x| x == 5), Some(5));
775     assert_eq!(iter.peeking_next(|&x| x == 6), Some(6));
776     assert_eq!(iter.peek_nth(0), Some(&7));
777     assert_eq!(iter.peek_nth(1), None);
778     assert_eq!(iter.next(), Some(7));
779     assert_eq!(iter.peek(), None);
780 }
781 
782 #[test]
test_peek_nth_next_if()783 fn test_peek_nth_next_if() {
784     let nums = [1u8, 2, 3, 4, 5, 6, 7];
785     let mut iter = peek_nth(nums.iter().copied());
786 
787     assert_eq!(iter.next_if(|&x| x != 0), Some(1));
788     assert_eq!(iter.next(), Some(2));
789 
790     assert_eq!(iter.peek_nth(0), Some(&3));
791     assert_eq!(iter.peek_nth(1), Some(&4));
792     assert_eq!(iter.next_if_eq(&3), Some(3));
793     assert_eq!(iter.peek(), Some(&4));
794 
795     assert_eq!(iter.next_if(|&x| x != 4), None);
796     assert_eq!(iter.next_if_eq(&4), Some(4));
797     assert_eq!(iter.peek_nth(0), Some(&5));
798     assert_eq!(iter.peek_nth(1), Some(&6));
799 
800     assert_eq!(iter.next_if(|&x| x != 5), None);
801     assert_eq!(iter.peek(), Some(&5));
802 
803     assert_eq!(iter.next_if(|&x| x % 2 == 1), Some(5));
804     assert_eq!(iter.next_if_eq(&6), Some(6));
805     assert_eq!(iter.peek_nth(0), Some(&7));
806     assert_eq!(iter.peek_nth(1), None);
807     assert_eq!(iter.next(), Some(7));
808     assert_eq!(iter.peek(), None);
809 }
810 
811 #[test]
pad_using()812 fn pad_using() {
813     it::assert_equal((0..0).pad_using(1, |_| 1), 1..2);
814 
815     let v: Vec<usize> = vec![0, 1, 2];
816     let r = v.into_iter().pad_using(5, |n| n);
817     it::assert_equal(r, vec![0, 1, 2, 3, 4]);
818 
819     let v: Vec<usize> = vec![0, 1, 2];
820     let r = v.into_iter().pad_using(1, |_| panic!());
821     it::assert_equal(r, vec![0, 1, 2]);
822 }
823 
824 #[test]
chunk_by()825 fn chunk_by() {
826     for (ch1, sub) in &"AABBCCC".chars().chunk_by(|&x| x) {
827         for ch2 in sub {
828             assert_eq!(ch1, ch2);
829         }
830     }
831 
832     for (ch1, sub) in &"AAABBBCCCCDDDD".chars().chunk_by(|&x| x) {
833         for ch2 in sub {
834             assert_eq!(ch1, ch2);
835             if ch1 == 'C' {
836                 break;
837             }
838         }
839     }
840 
841     let toupper = |ch: &char| ch.to_uppercase().next().unwrap();
842 
843     // try all possible orderings
844     for indices in permutohedron::Heap::new(&mut [0, 1, 2, 3]) {
845         let chunks = "AaaBbbccCcDDDD".chars().chunk_by(&toupper);
846         let mut subs = chunks.into_iter().collect_vec();
847 
848         for &idx in &indices[..] {
849             let (key, text) = match idx {
850                 0 => ('A', "Aaa".chars()),
851                 1 => ('B', "Bbb".chars()),
852                 2 => ('C', "ccCc".chars()),
853                 3 => ('D', "DDDD".chars()),
854                 _ => unreachable!(),
855             };
856             assert_eq!(key, subs[idx].0);
857             it::assert_equal(&mut subs[idx].1, text);
858         }
859     }
860 
861     let chunks = "AAABBBCCCCDDDD".chars().chunk_by(|&x| x);
862     let mut subs = chunks.into_iter().map(|(_, g)| g).collect_vec();
863 
864     let sd = subs.pop().unwrap();
865     let sc = subs.pop().unwrap();
866     let sb = subs.pop().unwrap();
867     let sa = subs.pop().unwrap();
868     for (a, b, c, d) in multizip((sa, sb, sc, sd)) {
869         assert_eq!(a, 'A');
870         assert_eq!(b, 'B');
871         assert_eq!(c, 'C');
872         assert_eq!(d, 'D');
873     }
874 
875     // check that the key closure is called exactly n times
876     {
877         let mut ntimes = 0;
878         let text = "AABCCC";
879         for (_, sub) in &text.chars().chunk_by(|&x| {
880             ntimes += 1;
881             x
882         }) {
883             for _ in sub {}
884         }
885         assert_eq!(ntimes, text.len());
886     }
887 
888     {
889         let mut ntimes = 0;
890         let text = "AABCCC";
891         for _ in &text.chars().chunk_by(|&x| {
892             ntimes += 1;
893             x
894         }) {}
895         assert_eq!(ntimes, text.len());
896     }
897 
898     {
899         let text = "ABCCCDEEFGHIJJKK";
900         let gr = text.chars().chunk_by(|&x| x);
901         it::assert_equal(gr.into_iter().flat_map(|(_, sub)| sub), text.chars());
902     }
903 }
904 
905 #[test]
chunk_by_lazy_2()906 fn chunk_by_lazy_2() {
907     let data = [0, 1];
908     let chunks = data.iter().chunk_by(|k| *k);
909     let gs = chunks.into_iter().collect_vec();
910     it::assert_equal(data.iter(), gs.into_iter().flat_map(|(_k, g)| g));
911 
912     let data = [0, 1, 1, 0, 0];
913     let chunks = data.iter().chunk_by(|k| *k);
914     let mut gs = chunks.into_iter().collect_vec();
915     gs[1..].reverse();
916     it::assert_equal(&[0, 0, 0, 1, 1], gs.into_iter().flat_map(|(_, g)| g));
917 
918     let grouper = data.iter().chunk_by(|k| *k);
919     let mut chunks = Vec::new();
920     for (k, chunk) in &grouper {
921         if *k == 1 {
922             chunks.push(chunk);
923         }
924     }
925     it::assert_equal(&mut chunks[0], &[1, 1]);
926 
927     let data = [0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
928     let grouper = data.iter().chunk_by(|k| *k);
929     let mut chunks = Vec::new();
930     for (i, (_, chunk)) in grouper.into_iter().enumerate() {
931         if i < 2 {
932             chunks.push(chunk);
933         } else if i < 4 {
934             for _ in chunk {}
935         } else {
936             chunks.push(chunk);
937         }
938     }
939     it::assert_equal(&mut chunks[0], &[0, 0, 0]);
940     it::assert_equal(&mut chunks[1], &[1, 1]);
941     it::assert_equal(&mut chunks[2], &[3, 3]);
942 
943     let data = [0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
944     let mut i = 0;
945     let grouper = data.iter().chunk_by(move |_| {
946         let k = i / 3;
947         i += 1;
948         k
949     });
950     for (i, chunk) in &grouper {
951         match i {
952             0 => it::assert_equal(chunk, &[0, 0, 0]),
953             1 => it::assert_equal(chunk, &[1, 1, 0]),
954             2 => it::assert_equal(chunk, &[0, 2, 2]),
955             3 => it::assert_equal(chunk, &[3, 3]),
956             _ => unreachable!(),
957         }
958     }
959 }
960 
961 #[test]
chunk_by_lazy_3()962 fn chunk_by_lazy_3() {
963     // test consuming each chunk on the lap after it was produced
964     let data = [0, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2];
965     let grouper = data.iter().chunk_by(|elt| *elt);
966     let mut last = None;
967     for (key, chunk) in &grouper {
968         if let Some(gr) = last.take() {
969             for elt in gr {
970                 assert!(elt != key && i32::abs(elt - key) == 1);
971             }
972         }
973         last = Some(chunk);
974     }
975 }
976 
977 #[test]
chunks()978 fn chunks() {
979     let data = [0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
980     let grouper = data.iter().chunks(3);
981     for (i, chunk) in grouper.into_iter().enumerate() {
982         match i {
983             0 => it::assert_equal(chunk, &[0, 0, 0]),
984             1 => it::assert_equal(chunk, &[1, 1, 0]),
985             2 => it::assert_equal(chunk, &[0, 2, 2]),
986             3 => it::assert_equal(chunk, &[3, 3]),
987             _ => unreachable!(),
988         }
989     }
990 }
991 
992 #[test]
concat_empty()993 fn concat_empty() {
994     let data: Vec<Vec<()>> = Vec::new();
995     assert_eq!(data.into_iter().concat(), Vec::new())
996 }
997 
998 #[test]
concat_non_empty()999 fn concat_non_empty() {
1000     let data = vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]];
1001     assert_eq!(data.into_iter().concat(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9])
1002 }
1003 
1004 #[test]
combinations()1005 fn combinations() {
1006     assert!((1..3).combinations(5).next().is_none());
1007 
1008     let it = (1..3).combinations(2);
1009     it::assert_equal(it, vec![vec![1, 2]]);
1010 
1011     let it = (1..5).combinations(2);
1012     it::assert_equal(
1013         it,
1014         vec![
1015             vec![1, 2],
1016             vec![1, 3],
1017             vec![1, 4],
1018             vec![2, 3],
1019             vec![2, 4],
1020             vec![3, 4],
1021         ],
1022     );
1023 
1024     it::assert_equal((0..0).tuple_combinations::<(_, _)>(), <Vec<_>>::new());
1025     it::assert_equal((0..1).tuple_combinations::<(_, _)>(), <Vec<_>>::new());
1026     it::assert_equal((0..2).tuple_combinations::<(_, _)>(), vec![(0, 1)]);
1027 
1028     it::assert_equal((0..0).combinations(2), <Vec<Vec<_>>>::new());
1029     it::assert_equal((0..1).combinations(1), vec![vec![0]]);
1030     it::assert_equal((0..2).combinations(1), vec![vec![0], vec![1]]);
1031     it::assert_equal((0..2).combinations(2), vec![vec![0, 1]]);
1032 }
1033 
1034 #[test]
combinations_of_too_short()1035 fn combinations_of_too_short() {
1036     for i in 1..10 {
1037         assert!((0..0).combinations(i).next().is_none());
1038         assert!((0..i - 1).combinations(i).next().is_none());
1039     }
1040 }
1041 
1042 #[test]
combinations_zero()1043 fn combinations_zero() {
1044     it::assert_equal((1..3).combinations(0), vec![vec![]]);
1045     it::assert_equal((0..0).combinations(0), vec![vec![]]);
1046 }
1047 
binomial(n: usize, k: usize) -> usize1048 fn binomial(n: usize, k: usize) -> usize {
1049     if k > n {
1050         0
1051     } else {
1052         (n - k + 1..=n).product::<usize>() / (1..=k).product::<usize>()
1053     }
1054 }
1055 
1056 #[test]
combinations_range_count()1057 fn combinations_range_count() {
1058     for n in 0..=10 {
1059         for k in 0..=10 {
1060             let len = binomial(n, k);
1061             let mut it = (0..n).combinations(k);
1062             assert_eq!(len, it.clone().count());
1063             assert_eq!(len, it.size_hint().0);
1064             assert_eq!(Some(len), it.size_hint().1);
1065             for count in (0..len).rev() {
1066                 let elem = it.next();
1067                 assert!(elem.is_some());
1068                 assert_eq!(count, it.clone().count());
1069                 assert_eq!(count, it.size_hint().0);
1070                 assert_eq!(Some(count), it.size_hint().1);
1071             }
1072             let should_be_none = it.next();
1073             assert!(should_be_none.is_none());
1074         }
1075     }
1076 }
1077 
1078 #[test]
combinations_inexact_size_hints()1079 fn combinations_inexact_size_hints() {
1080     for k in 0..=10 {
1081         let mut numbers = (0..18).filter(|i| i % 2 == 0); // 9 elements
1082         let mut it = numbers.clone().combinations(k);
1083         let real_n = numbers.clone().count();
1084         let len = binomial(real_n, k);
1085         assert_eq!(len, it.clone().count());
1086 
1087         let mut nb_loaded = 0;
1088         let sh = numbers.size_hint();
1089         assert_eq!(binomial(sh.0 + nb_loaded, k), it.size_hint().0);
1090         assert_eq!(sh.1.map(|n| binomial(n + nb_loaded, k)), it.size_hint().1);
1091 
1092         for next_count in 1..=len {
1093             let elem = it.next();
1094             assert!(elem.is_some());
1095             assert_eq!(len - next_count, it.clone().count());
1096             if next_count == 1 {
1097                 // The very first time, the lazy buffer is prefilled.
1098                 nb_loaded = numbers.by_ref().take(k).count();
1099             } else {
1100                 // Then it loads one item each time until exhausted.
1101                 let nb = numbers.next();
1102                 if nb.is_some() {
1103                     nb_loaded += 1;
1104                 }
1105             }
1106             let sh = numbers.size_hint();
1107             if next_count > real_n - k + 1 {
1108                 assert_eq!(0, sh.0);
1109                 assert_eq!(Some(0), sh.1);
1110                 assert_eq!(real_n, nb_loaded);
1111                 // Once it's fully loaded, size hints of `it` are exacts.
1112             }
1113             assert_eq!(binomial(sh.0 + nb_loaded, k) - next_count, it.size_hint().0);
1114             assert_eq!(
1115                 sh.1.map(|n| binomial(n + nb_loaded, k) - next_count),
1116                 it.size_hint().1
1117             );
1118         }
1119         let should_be_none = it.next();
1120         assert!(should_be_none.is_none());
1121     }
1122 }
1123 
1124 #[test]
permutations_zero()1125 fn permutations_zero() {
1126     it::assert_equal((1..3).permutations(0), vec![vec![]]);
1127     it::assert_equal((0..0).permutations(0), vec![vec![]]);
1128 }
1129 
1130 #[test]
permutations_range_count()1131 fn permutations_range_count() {
1132     for n in 0..=7 {
1133         for k in 0..=7 {
1134             let len = if k <= n { (n - k + 1..=n).product() } else { 0 };
1135             let mut it = (0..n).permutations(k);
1136             assert_eq!(len, it.clone().count());
1137             assert_eq!(len, it.size_hint().0);
1138             assert_eq!(Some(len), it.size_hint().1);
1139             for count in (0..len).rev() {
1140                 let elem = it.next();
1141                 assert!(elem.is_some());
1142                 assert_eq!(count, it.clone().count());
1143                 assert_eq!(count, it.size_hint().0);
1144                 assert_eq!(Some(count), it.size_hint().1);
1145             }
1146             let should_be_none = it.next();
1147             assert!(should_be_none.is_none());
1148         }
1149     }
1150 }
1151 
1152 #[test]
permutations_overflowed_size_hints()1153 fn permutations_overflowed_size_hints() {
1154     let mut it = std::iter::repeat(()).permutations(2);
1155     assert_eq!(it.size_hint().0, usize::MAX);
1156     assert_eq!(it.size_hint().1, None);
1157     for nb_generated in 1..=1000 {
1158         it.next();
1159         assert!(it.size_hint().0 >= usize::MAX - nb_generated);
1160         assert_eq!(it.size_hint().1, None);
1161     }
1162 }
1163 
1164 #[test]
combinations_with_replacement()1165 fn combinations_with_replacement() {
1166     // Pool smaller than n
1167     it::assert_equal((0..1).combinations_with_replacement(2), vec![vec![0, 0]]);
1168     // Pool larger than n
1169     it::assert_equal(
1170         (0..3).combinations_with_replacement(2),
1171         vec![
1172             vec![0, 0],
1173             vec![0, 1],
1174             vec![0, 2],
1175             vec![1, 1],
1176             vec![1, 2],
1177             vec![2, 2],
1178         ],
1179     );
1180     // Zero size
1181     it::assert_equal((0..3).combinations_with_replacement(0), vec![vec![]]);
1182     // Zero size on empty pool
1183     it::assert_equal((0..0).combinations_with_replacement(0), vec![vec![]]);
1184     // Empty pool
1185     it::assert_equal(
1186         (0..0).combinations_with_replacement(2),
1187         <Vec<Vec<_>>>::new(),
1188     );
1189 }
1190 
1191 #[test]
combinations_with_replacement_range_count()1192 fn combinations_with_replacement_range_count() {
1193     for n in 0..=7 {
1194         for k in 0..=7 {
1195             let len = binomial(usize::saturating_sub(n + k, 1), k);
1196             let mut it = (0..n).combinations_with_replacement(k);
1197             assert_eq!(len, it.clone().count());
1198             assert_eq!(len, it.size_hint().0);
1199             assert_eq!(Some(len), it.size_hint().1);
1200             for count in (0..len).rev() {
1201                 let elem = it.next();
1202                 assert!(elem.is_some());
1203                 assert_eq!(count, it.clone().count());
1204                 assert_eq!(count, it.size_hint().0);
1205                 assert_eq!(Some(count), it.size_hint().1);
1206             }
1207             let should_be_none = it.next();
1208             assert!(should_be_none.is_none());
1209         }
1210     }
1211 }
1212 
1213 #[test]
powerset()1214 fn powerset() {
1215     it::assert_equal((0..0).powerset(), vec![vec![]]);
1216     it::assert_equal((0..1).powerset(), vec![vec![], vec![0]]);
1217     it::assert_equal(
1218         (0..2).powerset(),
1219         vec![vec![], vec![0], vec![1], vec![0, 1]],
1220     );
1221     it::assert_equal(
1222         (0..3).powerset(),
1223         vec![
1224             vec![],
1225             vec![0],
1226             vec![1],
1227             vec![2],
1228             vec![0, 1],
1229             vec![0, 2],
1230             vec![1, 2],
1231             vec![0, 1, 2],
1232         ],
1233     );
1234 
1235     assert_eq!((0..4).powerset().count(), 1 << 4);
1236     assert_eq!((0..8).powerset().count(), 1 << 8);
1237     assert_eq!((0..16).powerset().count(), 1 << 16);
1238 
1239     for n in 0..=10 {
1240         let mut it = (0..n).powerset();
1241         let len = 2_usize.pow(n);
1242         assert_eq!(len, it.clone().count());
1243         assert_eq!(len, it.size_hint().0);
1244         assert_eq!(Some(len), it.size_hint().1);
1245         for count in (0..len).rev() {
1246             let elem = it.next();
1247             assert!(elem.is_some());
1248             assert_eq!(count, it.clone().count());
1249             assert_eq!(count, it.size_hint().0);
1250             assert_eq!(Some(count), it.size_hint().1);
1251         }
1252         let should_be_none = it.next();
1253         assert!(should_be_none.is_none());
1254     }
1255 }
1256 
1257 #[test]
diff_mismatch()1258 fn diff_mismatch() {
1259     let a = [1, 2, 3, 4];
1260     let b = vec![1.0, 5.0, 3.0, 4.0];
1261     let b_map = b.into_iter().map(|f| f as i32);
1262     let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
1263 
1264     assert!(match diff {
1265         Some(it::Diff::FirstMismatch(1, _, from_diff)) =>
1266             from_diff.collect::<Vec<_>>() == vec![5, 3, 4],
1267         _ => false,
1268     });
1269 }
1270 
1271 #[test]
diff_longer()1272 fn diff_longer() {
1273     let a = [1, 2, 3, 4];
1274     let b = vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0];
1275     let b_map = b.into_iter().map(|f| f as i32);
1276     let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
1277 
1278     assert!(match diff {
1279         Some(it::Diff::Longer(_, remaining)) => remaining.collect::<Vec<_>>() == vec![5, 6],
1280         _ => false,
1281     });
1282 }
1283 
1284 #[test]
diff_shorter()1285 fn diff_shorter() {
1286     let a = [1, 2, 3, 4];
1287     let b = vec![1.0, 2.0];
1288     let b_map = b.into_iter().map(|f| f as i32);
1289     let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
1290 
1291     assert!(match diff {
1292         Some(it::Diff::Shorter(len, _)) => len == 2,
1293         _ => false,
1294     });
1295 }
1296 
1297 #[test]
extrema_set()1298 fn extrema_set() {
1299     use std::cmp::Ordering;
1300 
1301     // A peculiar type: Equality compares both tuple items, but ordering only the
1302     // first item. Used to distinguish equal elements.
1303     #[derive(Clone, Debug, PartialEq, Eq)]
1304     struct Val(u32, u32);
1305 
1306     impl PartialOrd<Self> for Val {
1307         fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1308             Some(self.cmp(other))
1309         }
1310     }
1311 
1312     impl Ord for Val {
1313         fn cmp(&self, other: &Self) -> Ordering {
1314             self.0.cmp(&other.0)
1315         }
1316     }
1317 
1318     assert_eq!(None::<u32>.iter().min_set(), Vec::<&u32>::new());
1319     assert_eq!(None::<u32>.iter().max_set(), Vec::<&u32>::new());
1320 
1321     assert_eq!(Some(1u32).iter().min_set(), vec![&1]);
1322     assert_eq!(Some(1u32).iter().max_set(), vec![&1]);
1323 
1324     let data = [Val(0, 1), Val(2, 0), Val(0, 2), Val(1, 0), Val(2, 1)];
1325 
1326     let min_set = data.iter().min_set();
1327     assert_eq!(min_set, vec![&Val(0, 1), &Val(0, 2)]);
1328 
1329     let min_set_by_key = data.iter().min_set_by_key(|v| v.1);
1330     assert_eq!(min_set_by_key, vec![&Val(2, 0), &Val(1, 0)]);
1331 
1332     let min_set_by = data.iter().min_set_by(|x, y| x.1.cmp(&y.1));
1333     assert_eq!(min_set_by, vec![&Val(2, 0), &Val(1, 0)]);
1334 
1335     let max_set = data.iter().max_set();
1336     assert_eq!(max_set, vec![&Val(2, 0), &Val(2, 1)]);
1337 
1338     let max_set_by_key = data.iter().max_set_by_key(|v| v.1);
1339     assert_eq!(max_set_by_key, vec![&Val(0, 2)]);
1340 
1341     let max_set_by = data.iter().max_set_by(|x, y| x.1.cmp(&y.1));
1342     assert_eq!(max_set_by, vec![&Val(0, 2)]);
1343 }
1344 
1345 #[test]
minmax()1346 fn minmax() {
1347     use crate::it::MinMaxResult;
1348     use std::cmp::Ordering;
1349 
1350     // A peculiar type: Equality compares both tuple items, but ordering only the
1351     // first item.  This is so we can check the stability property easily.
1352     #[derive(Clone, Debug, PartialEq, Eq)]
1353     struct Val(u32, u32);
1354 
1355     impl PartialOrd<Self> for Val {
1356         fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1357             Some(self.cmp(other))
1358         }
1359     }
1360 
1361     impl Ord for Val {
1362         fn cmp(&self, other: &Self) -> Ordering {
1363             self.0.cmp(&other.0)
1364         }
1365     }
1366 
1367     assert_eq!(
1368         None::<Option<u32>>.iter().minmax(),
1369         MinMaxResult::NoElements
1370     );
1371 
1372     assert_eq!(Some(1u32).iter().minmax(), MinMaxResult::OneElement(&1));
1373 
1374     let data = [Val(0, 1), Val(2, 0), Val(0, 2), Val(1, 0), Val(2, 1)];
1375 
1376     let minmax = data.iter().minmax();
1377     assert_eq!(minmax, MinMaxResult::MinMax(&Val(0, 1), &Val(2, 1)));
1378 
1379     let (min, max) = data.iter().minmax_by_key(|v| v.1).into_option().unwrap();
1380     assert_eq!(min, &Val(2, 0));
1381     assert_eq!(max, &Val(0, 2));
1382 
1383     let (min, max) = data
1384         .iter()
1385         .minmax_by(|x, y| x.1.cmp(&y.1))
1386         .into_option()
1387         .unwrap();
1388     assert_eq!(min, &Val(2, 0));
1389     assert_eq!(max, &Val(0, 2));
1390 }
1391 
1392 #[test]
format()1393 fn format() {
1394     let data = [0, 1, 2, 3];
1395     let ans1 = "0, 1, 2, 3";
1396     let ans2 = "0--1--2--3";
1397 
1398     let t1 = format!("{}", data.iter().format(", "));
1399     assert_eq!(t1, ans1);
1400     let t2 = format!("{:?}", data.iter().format("--"));
1401     assert_eq!(t2, ans2);
1402 
1403     let dataf = [1.1, 5.71828, -22.];
1404     let t3 = format!("{:.2e}", dataf.iter().format(", "));
1405     assert_eq!(t3, "1.10e0, 5.72e0, -2.20e1");
1406 }
1407 
1408 #[test]
while_some()1409 fn while_some() {
1410     let ns = (1..10)
1411         .map(|x| if x % 5 != 0 { Some(x) } else { None })
1412         .while_some();
1413     it::assert_equal(ns, vec![1, 2, 3, 4]);
1414 }
1415 
1416 #[test]
fold_while()1417 fn fold_while() {
1418     let mut iterations = 0;
1419     let vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1420     let sum = vec
1421         .into_iter()
1422         .fold_while(0, |acc, item| {
1423             iterations += 1;
1424             let new_sum = acc + item;
1425             if new_sum <= 20 {
1426                 FoldWhile::Continue(new_sum)
1427             } else {
1428                 FoldWhile::Done(acc)
1429             }
1430         })
1431         .into_inner();
1432     assert_eq!(iterations, 6);
1433     assert_eq!(sum, 15);
1434 }
1435 
1436 #[test]
tree_reduce()1437 fn tree_reduce() {
1438     let x = [
1439         "",
1440         "0",
1441         "0 1 x",
1442         "0 1 x 2 x",
1443         "0 1 x 2 3 x x",
1444         "0 1 x 2 3 x x 4 x",
1445         "0 1 x 2 3 x x 4 5 x x",
1446         "0 1 x 2 3 x x 4 5 x 6 x x",
1447         "0 1 x 2 3 x x 4 5 x 6 7 x x x",
1448         "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 x",
1449         "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x x",
1450         "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 x x",
1451         "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x x",
1452         "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",
1453         "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",
1454         "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",
1455         "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",
1456     ];
1457     for (i, &s) in x.iter().enumerate() {
1458         let expected = if s.is_empty() {
1459             None
1460         } else {
1461             Some(s.to_string())
1462         };
1463         let num_strings = (0..i).map(|x| x.to_string());
1464         let actual = num_strings.tree_reduce(|a, b| format!("{} {} x", a, b));
1465         assert_eq!(actual, expected);
1466     }
1467 }
1468 
1469 #[test]
exactly_one_question_mark_syntax_works()1470 fn exactly_one_question_mark_syntax_works() {
1471     exactly_one_question_mark_return().unwrap_err();
1472 }
1473 
exactly_one_question_mark_return() -> Result<(), ExactlyOneError<std::slice::Iter<'static, ()>>>1474 fn exactly_one_question_mark_return() -> Result<(), ExactlyOneError<std::slice::Iter<'static, ()>>>
1475 {
1476     [].iter().exactly_one()?;
1477     Ok(())
1478 }
1479 
1480 #[test]
multiunzip()1481 fn multiunzip() {
1482     let (a, b, c): (Vec<_>, Vec<_>, Vec<_>) = [(0, 1, 2), (3, 4, 5), (6, 7, 8)]
1483         .iter()
1484         .cloned()
1485         .multiunzip();
1486     assert_eq!((a, b, c), (vec![0, 3, 6], vec![1, 4, 7], vec![2, 5, 8]));
1487     let (): () = [(), (), ()].iter().cloned().multiunzip();
1488     #[allow(clippy::type_complexity)]
1489     let t: (
1490         Vec<_>,
1491         Vec<_>,
1492         Vec<_>,
1493         Vec<_>,
1494         Vec<_>,
1495         Vec<_>,
1496         Vec<_>,
1497         Vec<_>,
1498         Vec<_>,
1499         Vec<_>,
1500         Vec<_>,
1501         Vec<_>,
1502     ) = [(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)]
1503         .iter()
1504         .cloned()
1505         .multiunzip();
1506     assert_eq!(
1507         t,
1508         (
1509             vec![0],
1510             vec![1],
1511             vec![2],
1512             vec![3],
1513             vec![4],
1514             vec![5],
1515             vec![6],
1516             vec![7],
1517             vec![8],
1518             vec![9],
1519             vec![10],
1520             vec![11]
1521         )
1522     );
1523 }
1524