1//! The purpose of these tests is to cover corner cases of iterators
2//! and adaptors.
3//!
4//! In particular we test the tedious size_hint and exact size correctness.
5
6use quickcheck as qc;
7use std::default::Default;
8use std::num::Wrapping;
9use std::ops::Range;
10use std::cmp::{max, min, Ordering};
11use std::collections::{HashMap, HashSet};
12use itertools::Itertools;
13use itertools::{
14 multizip,
15 EitherOrBoth,
16 iproduct,
17 izip,
18};
19use itertools::free::{
20 cloned,
21 enumerate,
22 multipeek,
23 peek_nth,
24 put_back,
25 put_back_n,
26 rciter,
27 zip,
28 zip_eq,
29};
30
31use rand::Rng;
32use rand::seq::SliceRandom;
33use quickcheck::TestResult;
34
35/// Trait for size hint modifier types
36trait HintKind: Copy + Send + qc::Arbitrary {
37 fn loosen_bounds(&self, org_hint: (usize, Option<usize>)) -> (usize, Option<usize>);
38}
39
40/// Exact size hint variant that leaves hints unchanged
41#[derive(Clone, Copy, Debug)]
42struct Exact {}
43
44impl HintKind for Exact {
45 fn loosen_bounds(&self, org_hint: (usize, Option<usize>)) -> (usize, Option<usize>) {
46 org_hint
47 }
48}
49
50impl qc::Arbitrary for Exact {
51 fn arbitrary<G: qc::Gen>(_: &mut G) -> Self {
52 Exact {}
53 }
54}
55
56/// Inexact size hint variant to simulate imprecise (but valid) size hints
57///
58/// Will always decrease the lower bound and increase the upper bound
59/// of the size hint by set amounts.
60#[derive(Clone, Copy, Debug)]
61struct Inexact {
62 underestimate: usize,
63 overestimate: usize,
64}
65
66impl HintKind for Inexact {
67 fn loosen_bounds(&self, org_hint: (usize, Option<usize>)) -> (usize, Option<usize>) {
68 let (org_lower, org_upper) = org_hint;
69 (org_lower.saturating_sub(self.underestimate),
70 org_upper.and_then(move |x| x.checked_add(self.overestimate)))
71 }
72}
73
74impl qc::Arbitrary for Inexact {
75 fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
76 let ue_value = usize::arbitrary(g);
77 let oe_value = usize::arbitrary(g);
78 // Compensate for quickcheck using extreme values too rarely
79 let ue_choices = &[0, ue_value, usize::max_value()];
80 let oe_choices = &[0, oe_value, usize::max_value()];
81 Inexact {
82 underestimate: *ue_choices.choose(g).unwrap(),
83 overestimate: *oe_choices.choose(g).unwrap(),
84 }
85 }
86
87 fn shrink(&self) -> Box<dyn Iterator<Item=Self>> {
88 let underestimate_value = self.underestimate;
89 let overestimate_value = self.overestimate;
90 Box::new(
91 underestimate_value.shrink().flat_map(move |ue_value|
92 overestimate_value.shrink().map(move |oe_value|
93 Inexact {
94 underestimate: ue_value,
95 overestimate: oe_value,
96 }
97 )
98 )
99 )
100 }
101}
102
103/// Our base iterator that we can impl Arbitrary for
104///
105/// By default we'll return inexact bounds estimates for size_hint
106/// to make tests harder to pass.
107///
108/// NOTE: Iter is tricky and is not fused, to help catch bugs.
109/// At the end it will return None once, then return Some(0),
110/// then return None again.
111#[derive(Clone, Debug)]
112struct Iter<T, SK: HintKind = Inexact> {
113 iterator: Range<T>,
114 // fuse/done flag
115 fuse_flag: i32,
116 hint_kind: SK,
117}
118
119impl<T, HK> Iter<T, HK> where HK: HintKind
120{
121 fn new(it: Range<T>, hint_kind: HK) -> Self {
122 Iter {
123 iterator: it,
124 fuse_flag: 0,
125 hint_kind,
126 }
127 }
128}
129
130impl<T, HK> Iterator for Iter<T, HK>
131 where Range<T>: Iterator,
132 <Range<T> as Iterator>::Item: Default,
133 HK: HintKind,
134{
135 type Item = <Range<T> as Iterator>::Item;
136
137 fn next(&mut self) -> Option<Self::Item>
138 {
139 let elt = self.iterator.next();
140 if elt.is_none() {
141 self.fuse_flag += 1;
142 // check fuse flag
143 if self.fuse_flag == 2 {
144 return Some(Default::default())
145 }
146 }
147 elt
148 }
149
150 fn size_hint(&self) -> (usize, Option<usize>)
151 {
152 let org_hint = self.iterator.size_hint();
153 self.hint_kind.loosen_bounds(org_hint)
154 }
155}
156
157impl<T, HK> DoubleEndedIterator for Iter<T, HK>
158 where Range<T>: DoubleEndedIterator,
159 <Range<T> as Iterator>::Item: Default,
160 HK: HintKind
161{
162 fn next_back(&mut self) -> Option<Self::Item> { self.iterator.next_back() }
163}
164
165impl<T> ExactSizeIterator for Iter<T, Exact> where Range<T>: ExactSizeIterator,
166 <Range<T> as Iterator>::Item: Default,
167{ }
168
169impl<T, HK> qc::Arbitrary for Iter<T, HK>
170 where T: qc::Arbitrary,
171 HK: HintKind,
172{
173 fn arbitrary<G: qc::Gen>(g: &mut G) -> Self
174 {
175 Iter::new(T::arbitrary(g)..T::arbitrary(g), HK::arbitrary(g))
176 }
177
178 fn shrink(&self) -> Box<dyn Iterator<Item=Iter<T, HK>>>
179 {
180 let r = self.iterator.clone();
181 let hint_kind = self.hint_kind;
182 Box::new(
183 r.start.shrink().flat_map(move |a|
184 r.end.shrink().map(move |b|
185 Iter::new(a.clone()..b, hint_kind)
186 )
187 )
188 )
189 }
190}
191
192/// A meta-iterator which yields `Iter<i32>`s whose start/endpoints are
193/// increased or decreased linearly on each iteration.
194#[derive(Clone, Debug)]
195struct ShiftRange<HK = Inexact> {
196 range_start: i32,
197 range_end: i32,
198 start_step: i32,
199 end_step: i32,
200 iter_count: u32,
201 hint_kind: HK,
202}
203
204impl<HK> Iterator for ShiftRange<HK> where HK: HintKind {
205 type Item = Iter<i32, HK>;
206
207 fn next(&mut self) -> Option<Self::Item> {
208 if self.iter_count == 0 {
209 return None;
210 }
211
212 let iter = Iter::new(self.range_start..self.range_end, self.hint_kind);
213
214 self.range_start += self.start_step;
215 self.range_end += self.end_step;
216 self.iter_count -= 1;
217
218 Some(iter)
219 }
220}
221
222impl ExactSizeIterator for ShiftRange<Exact> { }
223
224impl<HK> qc::Arbitrary for ShiftRange<HK>
225 where HK: HintKind
226{
227 fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
228 const MAX_STARTING_RANGE_DIFF: i32 = 32;
229 const MAX_STEP_MODULO: i32 = 8;
230 const MAX_ITER_COUNT: u32 = 3;
231
232 let range_start = qc::Arbitrary::arbitrary(g);
233 let range_end = range_start + g.gen_range(0, MAX_STARTING_RANGE_DIFF + 1);
234 let start_step = g.gen_range(-MAX_STEP_MODULO, MAX_STEP_MODULO + 1);
235 let end_step = g.gen_range(-MAX_STEP_MODULO, MAX_STEP_MODULO + 1);
236 let iter_count = g.gen_range(0, MAX_ITER_COUNT + 1);
237 let hint_kind = qc::Arbitrary::arbitrary(g);
238
239 ShiftRange {
240 range_start,
241 range_end,
242 start_step,
243 end_step,
244 iter_count,
245 hint_kind,
246 }
247 }
248}
249
250fn correct_count<I, F>(get_it: F) -> bool
251where
252 I: Iterator,
253 F: Fn() -> I
254{
255 let mut counts = vec![get_it().count()];
256
257 'outer: loop {
258 let mut it = get_it();
259
260 for _ in 0..(counts.len() - 1) {
261 #[allow(clippy::manual_assert)]
262 if it.next().is_none() {
263 panic!("Iterator shouldn't be finished, may not be deterministic");
264 }
265 }
266
267 if it.next().is_none() {
268 break 'outer;
269 }
270
271 counts.push(it.count());
272 }
273
274 let total_actual_count = counts.len() - 1;
275
276 for (i, returned_count) in counts.into_iter().enumerate() {
277 let actual_count = total_actual_count - i;
278 if actual_count != returned_count {
279 println!("Total iterations: {} True count: {} returned count: {}", i, actual_count, returned_count);
280
281 return false;
282 }
283 }
284
285 true
286}
287
288fn correct_size_hint<I: Iterator>(mut it: I) -> bool {
289 // record size hint at each iteration
290 let initial_hint = it.size_hint();
291 let mut hints = Vec::with_capacity(initial_hint.0 + 1);
292 hints.push(initial_hint);
293 while let Some(_) = it.next() {
294 hints.push(it.size_hint())
295 }
296
297 let mut true_count = hints.len(); // start off +1 too much
298
299 // check all the size hints
300 for &(low, hi) in &hints {
301 true_count -= 1;
302 if low > true_count ||
303 (hi.is_some() && hi.unwrap() < true_count)
304 {
305 println!("True size: {:?}, size hint: {:?}", true_count, (low, hi));
306 //println!("All hints: {:?}", hints);
307 return false
308 }
309 }
310 true
311}
312
313fn exact_size<I: ExactSizeIterator>(mut it: I) -> bool {
314 // check every iteration
315 let (mut low, mut hi) = it.size_hint();
316 if Some(low) != hi { return false; }
317 while let Some(_) = it.next() {
318 let (xlow, xhi) = it.size_hint();
319 if low != xlow + 1 { return false; }
320 low = xlow;
321 hi = xhi;
322 if Some(low) != hi { return false; }
323 }
324 let (low, hi) = it.size_hint();
325 low == 0 && hi == Some(0)
326}
327
328// Exact size for this case, without ExactSizeIterator
329fn exact_size_for_this<I: Iterator>(mut it: I) -> bool {
330 // check every iteration
331 let (mut low, mut hi) = it.size_hint();
332 if Some(low) != hi { return false; }
333 while let Some(_) = it.next() {
334 let (xlow, xhi) = it.size_hint();
335 if low != xlow + 1 { return false; }
336 low = xlow;
337 hi = xhi;
338 if Some(low) != hi { return false; }
339 }
340 let (low, hi) = it.size_hint();
341 low == 0 && hi == Some(0)
342}
343
344/*
345 * NOTE: Range<i8> is broken!
346 * (all signed ranges are)
347#[quickcheck]
348fn size_range_i8(a: Iter<i8>) -> bool {
349 exact_size(a)
350}
351
352#[quickcheck]
353fn size_range_i16(a: Iter<i16>) -> bool {
354 exact_size(a)
355}
356
357#[quickcheck]
358fn size_range_u8(a: Iter<u8>) -> bool {
359 exact_size(a)
360}
361 */
362
363macro_rules! quickcheck {
364 // accept several property function definitions
365 // The property functions can use pattern matching and `mut` as usual
366 // in the function arguments, but the functions can not be generic.
367 {$($(#$attr:tt)* fn $fn_name:ident($($arg:tt)*) -> $ret:ty { $($code:tt)* })*} => (
368 $(
369 #[test]
370 $(#$attr)*
371 fn $fn_name() {
372 fn prop($($arg)*) -> $ret {
373 $($code)*
374 }
375 ::quickcheck::quickcheck(quickcheck!(@fn prop [] $($arg)*));
376 }
377 )*
378 );
379 // parse argument list (with patterns allowed) into prop as fn(_, _) -> _
380 (@fn $f:ident [$($t:tt)*]) => {
381 $f as fn($($t),*) -> _
382 };
383 (@fn $f:ident [$($p:tt)*] : $($tail:tt)*) => {
384 quickcheck!(@fn $f [$($p)* _] $($tail)*)
385 };
386 (@fn $f:ident [$($p:tt)*] $t:tt $($tail:tt)*) => {
387 quickcheck!(@fn $f [$($p)*] $($tail)*)
388 };
389}
390
391quickcheck! {
392
393 fn size_product(a: Iter<u16>, b: Iter<u16>) -> bool {
394 correct_size_hint(a.cartesian_product(b))
395 }
396 fn size_product3(a: Iter<u16>, b: Iter<u16>, c: Iter<u16>) -> bool {
397 correct_size_hint(iproduct!(a, b, c))
398 }
399
400 fn correct_cartesian_product3(a: Iter<u16>, b: Iter<u16>, c: Iter<u16>,
401 take_manual: usize) -> ()
402 {
403 // test correctness of iproduct through regular iteration (take)
404 // and through fold.
405 let ac = a.clone();
406 let br = &b.clone();
407 let cr = &c.clone();
408 let answer: Vec<_> = ac.flat_map(move |ea| br.clone().flat_map(move |eb| cr.clone().map(move |ec| (ea, eb, ec)))).collect();
409 let mut product_iter = iproduct!(a, b, c);
410 let mut actual = Vec::new();
411
412 actual.extend((&mut product_iter).take(take_manual));
413 if actual.len() == take_manual {
414 product_iter.fold((), |(), elt| actual.push(elt));
415 }
416 assert_eq!(answer, actual);
417 }
418
419 fn size_multi_product(a: ShiftRange) -> bool {
420 correct_size_hint(a.multi_cartesian_product())
421 }
422 fn correct_multi_product3(a: ShiftRange, take_manual: usize) -> () {
423 // Fix no. of iterators at 3
424 let a = ShiftRange { iter_count: 3, ..a };
425
426 // test correctness of MultiProduct through regular iteration (take)
427 // and through fold.
428 let mut iters = a.clone();
429 let i0 = iters.next().unwrap();
430 let i1r = &iters.next().unwrap();
431 let i2r = &iters.next().unwrap();
432 let answer: Vec<_> = i0.flat_map(move |ei0| i1r.clone().flat_map(move |ei1| i2r.clone().map(move |ei2| vec![ei0, ei1, ei2]))).collect();
433 let mut multi_product = a.clone().multi_cartesian_product();
434 let mut actual = Vec::new();
435
436 actual.extend((&mut multi_product).take(take_manual));
437 if actual.len() == take_manual {
438 multi_product.fold((), |(), elt| actual.push(elt));
439 }
440 assert_eq!(answer, actual);
441
442 assert_eq!(answer.into_iter().last(), a.multi_cartesian_product().last());
443 }
444
445 #[allow(deprecated)]
446 fn size_step(a: Iter<i16, Exact>, s: usize) -> bool {
447 let mut s = s;
448 if s == 0 {
449 s += 1; // never zero
450 }
451 let filt = a.clone().dedup();
452 correct_size_hint(filt.step(s)) &&
453 exact_size(a.step(s))
454 }
455
456 #[allow(deprecated)]
457 fn equal_step(a: Iter<i16>, s: usize) -> bool {
458 let mut s = s;
459 if s == 0 {
460 s += 1; // never zero
461 }
462 let mut i = 0;
463 itertools::equal(a.clone().step(s), a.filter(|_| {
464 let keep = i % s == 0;
465 i += 1;
466 keep
467 }))
468 }
469
470 #[allow(deprecated)]
471 fn equal_step_vec(a: Vec<i16>, s: usize) -> bool {
472 let mut s = s;
473 if s == 0 {
474 s += 1; // never zero
475 }
476 let mut i = 0;
477 itertools::equal(a.iter().step(s), a.iter().filter(|_| {
478 let keep = i % s == 0;
479 i += 1;
480 keep
481 }))
482 }
483
484 fn size_multipeek(a: Iter<u16, Exact>, s: u8) -> bool {
485 let mut it = multipeek(a);
486 // peek a few times
487 for _ in 0..s {
488 it.peek();
489 }
490 exact_size(it)
491 }
492
493 fn size_peek_nth(a: Iter<u16, Exact>, s: u8) -> bool {
494 let mut it = peek_nth(a);
495 // peek a few times
496 for n in 0..s {
497 it.peek_nth(n as usize);
498 }
499 exact_size(it)
500 }
501
502 fn equal_merge(mut a: Vec<i16>, mut b: Vec<i16>) -> bool {
503 a.sort();
504 b.sort();
505 let mut merged = a.clone();
506 merged.extend(b.iter().cloned());
507 merged.sort();
508 itertools::equal(&merged, a.iter().merge(&b))
509 }
510 fn size_merge(a: Iter<u16>, b: Iter<u16>) -> bool {
511 correct_size_hint(a.merge(b))
512 }
513 fn size_zip(a: Iter<i16, Exact>, b: Iter<i16, Exact>, c: Iter<i16, Exact>) -> bool {
514 let filt = a.clone().dedup();
515 correct_size_hint(multizip((filt, b.clone(), c.clone()))) &&
516 exact_size(multizip((a, b, c)))
517 }
518 fn size_zip_rc(a: Iter<i16>, b: Iter<i16>) -> bool {
519 let rc = rciter(a);
520 correct_size_hint(multizip((&rc, &rc, b)))
521 }
522
523 fn size_zip_macro(a: Iter<i16, Exact>, b: Iter<i16, Exact>, c: Iter<i16, Exact>) -> bool {
524 let filt = a.clone().dedup();
525 correct_size_hint(izip!(filt, b.clone(), c.clone())) &&
526 exact_size(izip!(a, b, c))
527 }
528 fn equal_kmerge(mut a: Vec<i16>, mut b: Vec<i16>, mut c: Vec<i16>) -> bool {
529 use itertools::free::kmerge;
530 a.sort();
531 b.sort();
532 c.sort();
533 let mut merged = a.clone();
534 merged.extend(b.iter().cloned());
535 merged.extend(c.iter().cloned());
536 merged.sort();
537 itertools::equal(merged.into_iter(), kmerge(vec![a, b, c]))
538 }
539
540 // Any number of input iterators
541 fn equal_kmerge_2(mut inputs: Vec<Vec<i16>>) -> bool {
542 use itertools::free::kmerge;
543 // sort the inputs
544 for input in &mut inputs {
545 input.sort();
546 }
547 let mut merged = inputs.concat();
548 merged.sort();
549 itertools::equal(merged.into_iter(), kmerge(inputs))
550 }
551
552 // Any number of input iterators
553 fn equal_kmerge_by_ge(mut inputs: Vec<Vec<i16>>) -> bool {
554 // sort the inputs
555 for input in &mut inputs {
556 input.sort();
557 input.reverse();
558 }
559 let mut merged = inputs.concat();
560 merged.sort();
561 merged.reverse();
562 itertools::equal(merged.into_iter(),
563 inputs.into_iter().kmerge_by(|x, y| x >= y))
564 }
565
566 // Any number of input iterators
567 fn equal_kmerge_by_lt(mut inputs: Vec<Vec<i16>>) -> bool {
568 // sort the inputs
569 for input in &mut inputs {
570 input.sort();
571 }
572 let mut merged = inputs.concat();
573 merged.sort();
574 itertools::equal(merged.into_iter(),
575 inputs.into_iter().kmerge_by(|x, y| x < y))
576 }
577
578 // Any number of input iterators
579 fn equal_kmerge_by_le(mut inputs: Vec<Vec<i16>>) -> bool {
580 // sort the inputs
581 for input in &mut inputs {
582 input.sort();
583 }
584 let mut merged = inputs.concat();
585 merged.sort();
586 itertools::equal(merged.into_iter(),
587 inputs.into_iter().kmerge_by(|x, y| x <= y))
588 }
589 fn size_kmerge(a: Iter<i16>, b: Iter<i16>, c: Iter<i16>) -> bool {
590 use itertools::free::kmerge;
591 correct_size_hint(kmerge(vec![a, b, c]))
592 }
593 fn equal_zip_eq(a: Vec<i32>, b: Vec<i32>) -> bool {
594 let len = std::cmp::min(a.len(), b.len());
595 let a = &a[..len];
596 let b = &b[..len];
597 itertools::equal(zip_eq(a, b), zip(a, b))
598 }
599 fn size_zip_longest(a: Iter<i16, Exact>, b: Iter<i16, Exact>) -> bool {
600 let filt = a.clone().dedup();
601 let filt2 = b.clone().dedup();
602 correct_size_hint(filt.zip_longest(b.clone())) &&
603 correct_size_hint(a.clone().zip_longest(filt2)) &&
604 exact_size(a.zip_longest(b))
605 }
606 fn size_2_zip_longest(a: Iter<i16>, b: Iter<i16>) -> bool {
607 let it = a.clone().zip_longest(b.clone());
608 let jt = a.clone().zip_longest(b.clone());
609 itertools::equal(a,
610 it.filter_map(|elt| match elt {
611 EitherOrBoth::Both(x, _) => Some(x),
612 EitherOrBoth::Left(x) => Some(x),
613 _ => None,
614 }
615 ))
616 &&
617 itertools::equal(b,
618 jt.filter_map(|elt| match elt {
619 EitherOrBoth::Both(_, y) => Some(y),
620 EitherOrBoth::Right(y) => Some(y),
621 _ => None,
622 }
623 ))
624 }
625 fn size_interleave(a: Iter<i16>, b: Iter<i16>) -> bool {
626 correct_size_hint(a.interleave(b))
627 }
628 fn exact_interleave(a: Iter<i16, Exact>, b: Iter<i16, Exact>) -> bool {
629 exact_size_for_this(a.interleave(b))
630 }
631 fn size_interleave_shortest(a: Iter<i16>, b: Iter<i16>) -> bool {
632 correct_size_hint(a.interleave_shortest(b))
633 }
634 fn exact_interleave_shortest(a: Vec<()>, b: Vec<()>) -> bool {
635 exact_size_for_this(a.iter().interleave_shortest(&b))
636 }
637 fn size_intersperse(a: Iter<i16>, x: i16) -> bool {
638 correct_size_hint(a.intersperse(x))
639 }
640 fn equal_intersperse(a: Vec<i32>, x: i32) -> bool {
641 let mut inter = false;
642 let mut i = 0;
643 for elt in a.iter().cloned().intersperse(x) {
644 if inter {
645 if elt != x { return false }
646 } else {
647 if elt != a[i] { return false }
648 i += 1;
649 }
650 inter = !inter;
651 }
652 true
653 }
654
655 fn equal_combinations_2(a: Vec<u8>) -> bool {
656 let mut v = Vec::new();
657 for (i, x) in enumerate(&a) {
658 for y in &a[i + 1..] {
659 v.push((x, y));
660 }
661 }
662 itertools::equal(a.iter().tuple_combinations::<(_, _)>(), v)
663 }
664
665 fn collect_tuple_matches_size(a: Iter<i16>) -> bool {
666 let size = a.clone().count();
667 a.collect_tuple::<(_, _, _)>().is_some() == (size == 3)
668 }
669
670 fn correct_permutations(vals: HashSet<i32>, k: usize) -> () {
671 // Test permutations only on iterators of distinct integers, to prevent
672 // false positives.
673
674 const MAX_N: usize = 5;
675
676 let n = min(vals.len(), MAX_N);
677 let vals: HashSet<i32> = vals.into_iter().take(n).collect();
678
679 let perms = vals.iter().permutations(k);
680
681 let mut actual = HashSet::new();
682
683 for perm in perms {
684 assert_eq!(perm.len(), k);
685
686 let all_items_valid = perm.iter().all(|p| vals.contains(p));
687 assert!(all_items_valid, "perm contains value not from input: {:?}", perm);
688
689 // Check that all perm items are distinct
690 let distinct_len = {
691 let perm_set: HashSet<_> = perm.iter().collect();
692 perm_set.len()
693 };
694 assert_eq!(perm.len(), distinct_len);
695
696 // Check that the perm is new
697 assert!(actual.insert(perm.clone()), "perm already encountered: {:?}", perm);
698 }
699 }
700
701 fn permutations_lexic_order(a: usize, b: usize) -> () {
702 let a = a % 6;
703 let b = b % 6;
704
705 let n = max(a, b);
706 let k = min (a, b);
707
708 let expected_first: Vec<usize> = (0..k).collect();
709 let expected_last: Vec<usize> = ((n - k)..n).rev().collect();
710
711 let mut perms = (0..n).permutations(k);
712
713 let mut curr_perm = match perms.next() {
714 Some(p) => p,
715 None => { return; }
716 };
717
718 assert_eq!(expected_first, curr_perm);
719
720 for next_perm in perms {
721 assert!(
722 next_perm > curr_perm,
723 "next perm isn't greater-than current; next_perm={:?} curr_perm={:?} n={}",
724 next_perm, curr_perm, n
725 );
726
727 curr_perm = next_perm;
728 }
729
730 assert_eq!(expected_last, curr_perm);
731
732 }
733
734 fn permutations_count(n: usize, k: usize) -> bool {
735 let n = n % 6;
736
737 correct_count(|| (0..n).permutations(k))
738 }
739
740 fn permutations_size(a: Iter<i32>, k: usize) -> bool {
741 correct_size_hint(a.take(5).permutations(k))
742 }
743
744 fn permutations_k0_yields_once(n: usize) -> () {
745 let k = 0;
746 let expected: Vec<Vec<usize>> = vec![vec![]];
747 let actual = (0..n).permutations(k).collect_vec();
748
749 assert_eq!(expected, actual);
750 }
751}
752
753quickcheck! {
754 fn dedup_via_coalesce(a: Vec<i32>) -> bool {
755 let mut b = a.clone();
756 b.dedup();
757 itertools::equal(
758 &b,
759 a
760 .iter()
761 .coalesce(|x, y| {
762 if x==y {
763 Ok(x)
764 } else {
765 Err((x, y))
766 }
767 })
768 .fold(vec![], |mut v, n| {
769 v.push(n);
770 v
771 })
772 )
773 }
774}
775
776quickcheck! {
777 fn equal_dedup(a: Vec<i32>) -> bool {
778 let mut b = a.clone();
779 b.dedup();
780 itertools::equal(&b, a.iter().dedup())
781 }
782}
783
784quickcheck! {
785 fn equal_dedup_by(a: Vec<(i32, i32)>) -> bool {
786 let mut b = a.clone();
787 b.dedup_by(|x, y| x.0==y.0);
788 itertools::equal(&b, a.iter().dedup_by(|x, y| x.0==y.0))
789 }
790}
791
792quickcheck! {
793 fn size_dedup(a: Vec<i32>) -> bool {
794 correct_size_hint(a.iter().dedup())
795 }
796}
797
798quickcheck! {
799 fn size_dedup_by(a: Vec<(i32, i32)>) -> bool {
800 correct_size_hint(a.iter().dedup_by(|x, y| x.0==y.0))
801 }
802}
803
804quickcheck! {
805 fn exact_repeatn((n, x): (usize, i32)) -> bool {
806 let it = itertools::repeat_n(x, n);
807 exact_size(it)
808 }
809}
810
811quickcheck! {
812 fn size_put_back(a: Vec<u8>, x: Option<u8>) -> bool {
813 let mut it = put_back(a.into_iter());
814 match x {
815 Some(t) => it.put_back(t),
816 None => {}
817 }
818 correct_size_hint(it)
819 }
820}
821
822quickcheck! {
823 fn size_put_backn(a: Vec<u8>, b: Vec<u8>) -> bool {
824 let mut it = put_back_n(a.into_iter());
825 for elt in b {
826 it.put_back(elt)
827 }
828 correct_size_hint(it)
829 }
830}
831
832quickcheck! {
833 fn size_tee(a: Vec<u8>) -> bool {
834 let (mut t1, mut t2) = a.iter().tee();
835 t1.next();
836 t1.next();
837 t2.next();
838 exact_size(t1) && exact_size(t2)
839 }
840}
841
842quickcheck! {
843 fn size_tee_2(a: Vec<u8>) -> bool {
844 let (mut t1, mut t2) = a.iter().dedup().tee();
845 t1.next();
846 t1.next();
847 t2.next();
848 correct_size_hint(t1) && correct_size_hint(t2)
849 }
850}
851
852quickcheck! {
853 fn size_take_while_ref(a: Vec<u8>, stop: u8) -> bool {
854 correct_size_hint(a.iter().take_while_ref(|x| **x != stop))
855 }
856}
857
858quickcheck! {
859 fn equal_partition(a: Vec<i32>) -> bool {
860 let mut a = a;
861 let mut ap = a.clone();
862 let split_index = itertools::partition(&mut ap, |x| *x >= 0);
863 let parted = (0..split_index).all(|i| ap[i] >= 0) &&
864 (split_index..a.len()).all(|i| ap[i] < 0);
865
866 a.sort();
867 ap.sort();
868 parted && (a == ap)
869 }
870}
871
872quickcheck! {
873 fn size_combinations(it: Iter<i16>) -> bool {
874 correct_size_hint(it.tuple_combinations::<(_, _)>())
875 }
876}
877
878quickcheck! {
879 fn equal_combinations(it: Iter<i16>) -> bool {
880 let values = it.clone().collect_vec();
881 let mut cmb = it.tuple_combinations();
882 for i in 0..values.len() {
883 for j in i+1..values.len() {
884 let pair = (values[i], values[j]);
885 if pair != cmb.next().unwrap() {
886 return false;
887 }
888 }
889 }
890 cmb.next() == None
891 }
892}
893
894quickcheck! {
895 fn size_pad_tail(it: Iter<i8>, pad: u8) -> bool {
896 correct_size_hint(it.clone().pad_using(pad as usize, |_| 0)) &&
897 correct_size_hint(it.dropping(1).rev().pad_using(pad as usize, |_| 0))
898 }
899}
900
901quickcheck! {
902 fn size_pad_tail2(it: Iter<i8, Exact>, pad: u8) -> bool {
903 exact_size(it.pad_using(pad as usize, |_| 0))
904 }
905}
906
907quickcheck! {
908 fn size_powerset(it: Iter<u8, Exact>) -> bool {
909 // Powerset cardinality gets large very quickly, limit input to keep test fast.
910 correct_size_hint(it.take(12).powerset())
911 }
912}
913
914quickcheck! {
915 fn size_duplicates(it: Iter<i8>) -> bool {
916 correct_size_hint(it.duplicates())
917 }
918}
919
920quickcheck! {
921 fn size_unique(it: Iter<i8>) -> bool {
922 correct_size_hint(it.unique())
923 }
924
925 fn count_unique(it: Vec<i8>, take_first: u8) -> () {
926 let answer = {
927 let mut v = it.clone();
928 v.sort(); v.dedup();
929 v.len()
930 };
931 let mut iter = cloned(&it).unique();
932 let first_count = (&mut iter).take(take_first as usize).count();
933 let rest_count = iter.count();
934 assert_eq!(answer, first_count + rest_count);
935 }
936}
937
938quickcheck! {
939 fn fuzz_group_by_lazy_1(it: Iter<u8>) -> bool {
940 let jt = it.clone();
941 let groups = it.group_by(|k| *k);
942 itertools::equal(jt, groups.into_iter().flat_map(|(_, x)| x))
943 }
944}
945
946quickcheck! {
947 fn fuzz_group_by_lazy_2(data: Vec<u8>) -> bool {
948 let groups = data.iter().group_by(|k| *k / 10);
949 let res = itertools::equal(data.iter(), groups.into_iter().flat_map(|(_, x)| x));
950 res
951 }
952}
953
954quickcheck! {
955 fn fuzz_group_by_lazy_3(data: Vec<u8>) -> bool {
956 let grouper = data.iter().group_by(|k| *k / 10);
957 let groups = grouper.into_iter().collect_vec();
958 let res = itertools::equal(data.iter(), groups.into_iter().flat_map(|(_, x)| x));
959 res
960 }
961}
962
963quickcheck! {
964 fn fuzz_group_by_lazy_duo(data: Vec<u8>, order: Vec<(bool, bool)>) -> bool {
965 let grouper = data.iter().group_by(|k| *k / 3);
966 let mut groups1 = grouper.into_iter();
967 let mut groups2 = grouper.into_iter();
968 let mut elts = Vec::<&u8>::new();
969 let mut old_groups = Vec::new();
970
971 let tup1 = |(_, b)| b;
972 for &(ord, consume_now) in &order {
973 let iter = &mut [&mut groups1, &mut groups2][ord as usize];
974 match iter.next() {
975 Some((_, gr)) => if consume_now {
976 for og in old_groups.drain(..) {
977 elts.extend(og);
978 }
979 elts.extend(gr);
980 } else {
981 old_groups.push(gr);
982 },
983 None => break,
984 }
985 }
986 for og in old_groups.drain(..) {
987 elts.extend(og);
988 }
989 for gr in groups1.map(&tup1) { elts.extend(gr); }
990 for gr in groups2.map(&tup1) { elts.extend(gr); }
991 itertools::assert_equal(&data, elts);
992 true
993 }
994}
995
996quickcheck! {
997 fn equal_chunks_lazy(a: Vec<u8>, size: u8) -> bool {
998 let mut size = size;
999 if size == 0 {
1000 size += 1;
1001 }
1002 let chunks = a.iter().chunks(size as usize);
1003 let it = a.chunks(size as usize);
1004 for (a, b) in chunks.into_iter().zip(it) {
1005 if !itertools::equal(a, b) {
1006 return false;
1007 }
1008 }
1009 true
1010 }
1011}
1012
1013quickcheck! {
1014 fn equal_tuple_windows_1(a: Vec<u8>) -> bool {
1015 let x = a.windows(1).map(|s| (&s[0], ));
1016 let y = a.iter().tuple_windows::<(_,)>();
1017 itertools::equal(x, y)
1018 }
1019
1020 fn equal_tuple_windows_2(a: Vec<u8>) -> bool {
1021 let x = a.windows(2).map(|s| (&s[0], &s[1]));
1022 let y = a.iter().tuple_windows::<(_, _)>();
1023 itertools::equal(x, y)
1024 }
1025
1026 fn equal_tuple_windows_3(a: Vec<u8>) -> bool {
1027 let x = a.windows(3).map(|s| (&s[0], &s[1], &s[2]));
1028 let y = a.iter().tuple_windows::<(_, _, _)>();
1029 itertools::equal(x, y)
1030 }
1031
1032 fn equal_tuple_windows_4(a: Vec<u8>) -> bool {
1033 let x = a.windows(4).map(|s| (&s[0], &s[1], &s[2], &s[3]));
1034 let y = a.iter().tuple_windows::<(_, _, _, _)>();
1035 itertools::equal(x, y)
1036 }
1037
1038 fn equal_tuples_1(a: Vec<u8>) -> bool {
1039 let x = a.chunks(1).map(|s| (&s[0], ));
1040 let y = a.iter().tuples::<(_,)>();
1041 itertools::equal(x, y)
1042 }
1043
1044 fn equal_tuples_2(a: Vec<u8>) -> bool {
1045 let x = a.chunks(2).filter(|s| s.len() == 2).map(|s| (&s[0], &s[1]));
1046 let y = a.iter().tuples::<(_, _)>();
1047 itertools::equal(x, y)
1048 }
1049
1050 fn equal_tuples_3(a: Vec<u8>) -> bool {
1051 let x = a.chunks(3).filter(|s| s.len() == 3).map(|s| (&s[0], &s[1], &s[2]));
1052 let y = a.iter().tuples::<(_, _, _)>();
1053 itertools::equal(x, y)
1054 }
1055
1056 fn equal_tuples_4(a: Vec<u8>) -> bool {
1057 let x = a.chunks(4).filter(|s| s.len() == 4).map(|s| (&s[0], &s[1], &s[2], &s[3]));
1058 let y = a.iter().tuples::<(_, _, _, _)>();
1059 itertools::equal(x, y)
1060 }
1061
1062 fn exact_tuple_buffer(a: Vec<u8>) -> bool {
1063 let mut iter = a.iter().tuples::<(_, _, _, _)>();
1064 (&mut iter).last();
1065 let buffer = iter.into_buffer();
1066 assert_eq!(buffer.len(), a.len() % 4);
1067 exact_size(buffer)
1068 }
1069}
1070
1071// with_position
1072quickcheck! {
1073 fn with_position_exact_size_1(a: Vec<u8>) -> bool {
1074 exact_size_for_this(a.iter().with_position())
1075 }
1076 fn with_position_exact_size_2(a: Iter<u8, Exact>) -> bool {
1077 exact_size_for_this(a.with_position())
1078 }
1079}
1080
1081quickcheck! {
1082 fn correct_group_map_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1083 let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
1084 let count = a.len();
1085 let lookup = a.into_iter().map(|i| (i % modulo, i)).into_group_map();
1086
1087 assert_eq!(lookup.values().flat_map(|vals| vals.iter()).count(), count);
1088
1089 for (&key, vals) in lookup.iter() {
1090 assert!(vals.iter().all(|&val| val % modulo == key));
1091 }
1092 }
1093}
1094
1095/// A peculiar type: Equality compares both tuple items, but ordering only the
1096/// first item. This is so we can check the stability property easily.
1097#[derive(Clone, Debug, PartialEq, Eq)]
1098struct Val(u32, u32);
1099
1100impl PartialOrd<Val> for Val {
1101 fn partial_cmp(&self, other: &Val) -> Option<Ordering> {
1102 self.0.partial_cmp(&other.0)
1103 }
1104}
1105
1106impl Ord for Val {
1107 fn cmp(&self, other: &Val) -> Ordering {
1108 self.0.cmp(&other.0)
1109 }
1110}
1111
1112impl qc::Arbitrary for Val {
1113 fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
1114 let (x, y) = <(u32, u32)>::arbitrary(g);
1115 Val(x, y)
1116 }
1117 fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
1118 Box::new((self.0, self.1).shrink().map(|(x, y)| Val(x, y)))
1119 }
1120}
1121
1122quickcheck! {
1123 fn minmax(a: Vec<Val>) -> bool {
1124 use itertools::MinMaxResult;
1125
1126
1127 let minmax = a.iter().minmax();
1128 let expected = match a.len() {
1129 0 => MinMaxResult::NoElements,
1130 1 => MinMaxResult::OneElement(&a[0]),
1131 _ => MinMaxResult::MinMax(a.iter().min().unwrap(),
1132 a.iter().max().unwrap()),
1133 };
1134 minmax == expected
1135 }
1136}
1137
1138quickcheck! {
1139 fn minmax_f64(a: Vec<f64>) -> TestResult {
1140 use itertools::MinMaxResult;
1141
1142 if a.iter().any(|x| x.is_nan()) {
1143 return TestResult::discard();
1144 }
1145
1146 let min = cloned(&a).fold1(f64::min);
1147 let max = cloned(&a).fold1(f64::max);
1148
1149 let minmax = cloned(&a).minmax();
1150 let expected = match a.len() {
1151 0 => MinMaxResult::NoElements,
1152 1 => MinMaxResult::OneElement(min.unwrap()),
1153 _ => MinMaxResult::MinMax(min.unwrap(), max.unwrap()),
1154 };
1155 TestResult::from_bool(minmax == expected)
1156 }
1157}
1158
1159quickcheck! {
1160 #[allow(deprecated)]
1161 fn tree_fold1_f64(mut a: Vec<f64>) -> TestResult {
1162 fn collapse_adjacent<F>(x: Vec<f64>, mut f: F) -> Vec<f64>
1163 where F: FnMut(f64, f64) -> f64
1164 {
1165 let mut out = Vec::new();
1166 for i in (0..x.len()).step(2) {
1167 if i == x.len()-1 {
1168 out.push(x[i])
1169 } else {
1170 out.push(f(x[i], x[i+1]));
1171 }
1172 }
1173 out
1174 }
1175
1176 if a.iter().any(|x| x.is_nan()) {
1177 return TestResult::discard();
1178 }
1179
1180 let actual = a.iter().cloned().tree_fold1(f64::atan2);
1181
1182 while a.len() > 1 {
1183 a = collapse_adjacent(a, f64::atan2);
1184 }
1185 let expected = a.pop();
1186
1187 TestResult::from_bool(actual == expected)
1188 }
1189}
1190
1191quickcheck! {
1192 fn exactly_one_i32(a: Vec<i32>) -> TestResult {
1193 let ret = a.iter().cloned().exactly_one();
1194 match a.len() {
1195 1 => TestResult::from_bool(ret.unwrap() == a[0]),
1196 _ => TestResult::from_bool(ret.unwrap_err().eq(a.iter().cloned())),
1197 }
1198 }
1199}
1200
1201quickcheck! {
1202 fn at_most_one_i32(a: Vec<i32>) -> TestResult {
1203 let ret = a.iter().cloned().at_most_one();
1204 match a.len() {
1205 0 => TestResult::from_bool(ret.unwrap() == None),
1206 1 => TestResult::from_bool(ret.unwrap() == Some(a[0])),
1207 _ => TestResult::from_bool(ret.unwrap_err().eq(a.iter().cloned())),
1208 }
1209 }
1210}
1211
1212quickcheck! {
1213 fn consistent_grouping_map_with_by(a: Vec<u8>, modulo: u8) -> () {
1214 let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
1215
1216 let lookup_grouping_map = a.iter().copied().map(|i| (i % modulo, i)).into_grouping_map().collect::<Vec<_>>();
1217 let lookup_grouping_map_by = a.iter().copied().into_grouping_map_by(|i| i % modulo).collect::<Vec<_>>();
1218
1219 assert_eq!(lookup_grouping_map, lookup_grouping_map_by);
1220 }
1221
1222 fn correct_grouping_map_by_aggregate_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1223 let modulo = if modulo < 2 { 2 } else { modulo } as u64; // Avoid `% 0`
1224 let lookup = a.iter()
1225 .map(|&b| b as u64) // Avoid overflows
1226 .into_grouping_map_by(|i| i % modulo)
1227 .aggregate(|acc, &key, val| {
1228 assert!(val % modulo == key);
1229 if val % (modulo - 1) == 0 {
1230 None
1231 } else {
1232 Some(acc.unwrap_or(0) + val)
1233 }
1234 });
1235
1236 let group_map_lookup = a.iter()
1237 .map(|&b| b as u64)
1238 .map(|i| (i % modulo, i))
1239 .into_group_map()
1240 .into_iter()
1241 .filter_map(|(key, vals)| {
1242 vals.into_iter().fold(None, |acc, val| {
1243 if val % (modulo - 1) == 0 {
1244 None
1245 } else {
1246 Some(acc.unwrap_or(0) + val)
1247 }
1248 }).map(|new_val| (key, new_val))
1249 })
1250 .collect::<HashMap<_,_>>();
1251 assert_eq!(lookup, group_map_lookup);
1252
1253 for m in 0..modulo {
1254 assert_eq!(
1255 lookup.get(&m).copied(),
1256 a.iter()
1257 .map(|&b| b as u64)
1258 .filter(|&val| val % modulo == m)
1259 .fold(None, |acc, val| {
1260 if val % (modulo - 1) == 0 {
1261 None
1262 } else {
1263 Some(acc.unwrap_or(0) + val)
1264 }
1265 })
1266 );
1267 }
1268 }
1269
1270 fn correct_grouping_map_by_fold_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1271 let modulo = if modulo == 0 { 1 } else { modulo } as u64; // Avoid `% 0`
1272 let lookup = a.iter().map(|&b| b as u64) // Avoid overflows
1273 .into_grouping_map_by(|i| i % modulo)
1274 .fold(0u64, |acc, &key, val| {
1275 assert!(val % modulo == key);
1276 acc + val
1277 });
1278
1279 let group_map_lookup = a.iter()
1280 .map(|&b| b as u64)
1281 .map(|i| (i % modulo, i))
1282 .into_group_map()
1283 .into_iter()
1284 .map(|(key, vals)| (key, vals.into_iter().sum()))
1285 .collect::<HashMap<_,_>>();
1286 assert_eq!(lookup, group_map_lookup);
1287
1288 for (&key, &sum) in lookup.iter() {
1289 assert_eq!(sum, a.iter().map(|&b| b as u64).filter(|&val| val % modulo == key).sum::<u64>());
1290 }
1291 }
1292
1293 fn correct_grouping_map_by_fold_first_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1294 let modulo = if modulo == 0 { 1 } else { modulo } as u64; // Avoid `% 0`
1295 let lookup = a.iter().map(|&b| b as u64) // Avoid overflows
1296 .into_grouping_map_by(|i| i % modulo)
1297 .fold_first(|acc, &key, val| {
1298 assert!(val % modulo == key);
1299 acc + val
1300 });
1301
1302 // TODO: Swap `fold1` with stdlib's `fold_first` when it's stabilized
1303 let group_map_lookup = a.iter()
1304 .map(|&b| b as u64)
1305 .map(|i| (i % modulo, i))
1306 .into_group_map()
1307 .into_iter()
1308 .map(|(key, vals)| (key, vals.into_iter().fold1(|acc, val| acc + val).unwrap()))
1309 .collect::<HashMap<_,_>>();
1310 assert_eq!(lookup, group_map_lookup);
1311
1312 for (&key, &sum) in lookup.iter() {
1313 assert_eq!(sum, a.iter().map(|&b| b as u64).filter(|&val| val % modulo == key).sum::<u64>());
1314 }
1315 }
1316
1317 fn correct_grouping_map_by_collect_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1318 let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
1319 let lookup_grouping_map = a.iter().copied().into_grouping_map_by(|i| i % modulo).collect::<Vec<_>>();
1320 let lookup_group_map = a.iter().copied().map(|i| (i % modulo, i)).into_group_map();
1321
1322 assert_eq!(lookup_grouping_map, lookup_group_map);
1323 }
1324
1325 fn correct_grouping_map_by_max_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1326 let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
1327 let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).max();
1328
1329 let group_map_lookup = a.iter().copied()
1330 .map(|i| (i % modulo, i))
1331 .into_group_map()
1332 .into_iter()
1333 .map(|(key, vals)| (key, vals.into_iter().max().unwrap()))
1334 .collect::<HashMap<_,_>>();
1335 assert_eq!(lookup, group_map_lookup);
1336
1337 for (&key, &max) in lookup.iter() {
1338 assert_eq!(Some(max), a.iter().copied().filter(|&val| val % modulo == key).max());
1339 }
1340 }
1341
1342 fn correct_grouping_map_by_max_by_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1343 let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
1344 let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).max_by(|_, v1, v2| v1.cmp(v2));
1345
1346 let group_map_lookup = a.iter().copied()
1347 .map(|i| (i % modulo, i))
1348 .into_group_map()
1349 .into_iter()
1350 .map(|(key, vals)| (key, vals.into_iter().max_by(|v1, v2| v1.cmp(v2)).unwrap()))
1351 .collect::<HashMap<_,_>>();
1352 assert_eq!(lookup, group_map_lookup);
1353
1354 for (&key, &max) in lookup.iter() {
1355 assert_eq!(Some(max), a.iter().copied().filter(|&val| val % modulo == key).max_by(|v1, v2| v1.cmp(v2)));
1356 }
1357 }
1358
1359 fn correct_grouping_map_by_max_by_key_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1360 let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
1361 let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).max_by_key(|_, &val| val);
1362
1363 let group_map_lookup = a.iter().copied()
1364 .map(|i| (i % modulo, i))
1365 .into_group_map()
1366 .into_iter()
1367 .map(|(key, vals)| (key, vals.into_iter().max_by_key(|&val| val).unwrap()))
1368 .collect::<HashMap<_,_>>();
1369 assert_eq!(lookup, group_map_lookup);
1370
1371 for (&key, &max) in lookup.iter() {
1372 assert_eq!(Some(max), a.iter().copied().filter(|&val| val % modulo == key).max_by_key(|&val| val));
1373 }
1374 }
1375
1376 fn correct_grouping_map_by_min_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1377 let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
1378 let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).min();
1379
1380 let group_map_lookup = a.iter().copied()
1381 .map(|i| (i % modulo, i))
1382 .into_group_map()
1383 .into_iter()
1384 .map(|(key, vals)| (key, vals.into_iter().min().unwrap()))
1385 .collect::<HashMap<_,_>>();
1386 assert_eq!(lookup, group_map_lookup);
1387
1388 for (&key, &min) in lookup.iter() {
1389 assert_eq!(Some(min), a.iter().copied().filter(|&val| val % modulo == key).min());
1390 }
1391 }
1392
1393 fn correct_grouping_map_by_min_by_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1394 let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
1395 let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).min_by(|_, v1, v2| v1.cmp(v2));
1396
1397 let group_map_lookup = a.iter().copied()
1398 .map(|i| (i % modulo, i))
1399 .into_group_map()
1400 .into_iter()
1401 .map(|(key, vals)| (key, vals.into_iter().min_by(|v1, v2| v1.cmp(v2)).unwrap()))
1402 .collect::<HashMap<_,_>>();
1403 assert_eq!(lookup, group_map_lookup);
1404
1405 for (&key, &min) in lookup.iter() {
1406 assert_eq!(Some(min), a.iter().copied().filter(|&val| val % modulo == key).min_by(|v1, v2| v1.cmp(v2)));
1407 }
1408 }
1409
1410 fn correct_grouping_map_by_min_by_key_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1411 let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
1412 let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).min_by_key(|_, &val| val);
1413
1414 let group_map_lookup = a.iter().copied()
1415 .map(|i| (i % modulo, i))
1416 .into_group_map()
1417 .into_iter()
1418 .map(|(key, vals)| (key, vals.into_iter().min_by_key(|&val| val).unwrap()))
1419 .collect::<HashMap<_,_>>();
1420 assert_eq!(lookup, group_map_lookup);
1421
1422 for (&key, &min) in lookup.iter() {
1423 assert_eq!(Some(min), a.iter().copied().filter(|&val| val % modulo == key).min_by_key(|&val| val));
1424 }
1425 }
1426
1427 fn correct_grouping_map_by_minmax_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1428 let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
1429 let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).minmax();
1430
1431 let group_map_lookup = a.iter().copied()
1432 .map(|i| (i % modulo, i))
1433 .into_group_map()
1434 .into_iter()
1435 .map(|(key, vals)| (key, vals.into_iter().minmax()))
1436 .collect::<HashMap<_,_>>();
1437 assert_eq!(lookup, group_map_lookup);
1438
1439 for (&key, &minmax) in lookup.iter() {
1440 assert_eq!(minmax, a.iter().copied().filter(|&val| val % modulo == key).minmax());
1441 }
1442 }
1443
1444 fn correct_grouping_map_by_minmax_by_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1445 let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
1446 let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).minmax_by(|_, v1, v2| v1.cmp(v2));
1447
1448 let group_map_lookup = a.iter().copied()
1449 .map(|i| (i % modulo, i))
1450 .into_group_map()
1451 .into_iter()
1452 .map(|(key, vals)| (key, vals.into_iter().minmax_by(|v1, v2| v1.cmp(v2))))
1453 .collect::<HashMap<_,_>>();
1454 assert_eq!(lookup, group_map_lookup);
1455
1456 for (&key, &minmax) in lookup.iter() {
1457 assert_eq!(minmax, a.iter().copied().filter(|&val| val % modulo == key).minmax_by(|v1, v2| v1.cmp(v2)));
1458 }
1459 }
1460
1461 fn correct_grouping_map_by_minmax_by_key_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1462 let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
1463 let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).minmax_by_key(|_, &val| val);
1464
1465 let group_map_lookup = a.iter().copied()
1466 .map(|i| (i % modulo, i))
1467 .into_group_map()
1468 .into_iter()
1469 .map(|(key, vals)| (key, vals.into_iter().minmax_by_key(|&val| val)))
1470 .collect::<HashMap<_,_>>();
1471 assert_eq!(lookup, group_map_lookup);
1472
1473 for (&key, &minmax) in lookup.iter() {
1474 assert_eq!(minmax, a.iter().copied().filter(|&val| val % modulo == key).minmax_by_key(|&val| val));
1475 }
1476 }
1477
1478 fn correct_grouping_map_by_sum_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1479 let modulo = if modulo == 0 { 1 } else { modulo } as u64; // Avoid `% 0`
1480 let lookup = a.iter().map(|&b| b as u64) // Avoid overflows
1481 .into_grouping_map_by(|i| i % modulo)
1482 .sum();
1483
1484 let group_map_lookup = a.iter().map(|&b| b as u64)
1485 .map(|i| (i % modulo, i))
1486 .into_group_map()
1487 .into_iter()
1488 .map(|(key, vals)| (key, vals.into_iter().sum()))
1489 .collect::<HashMap<_,_>>();
1490 assert_eq!(lookup, group_map_lookup);
1491
1492 for (&key, &sum) in lookup.iter() {
1493 assert_eq!(sum, a.iter().map(|&b| b as u64).filter(|&val| val % modulo == key).sum::<u64>());
1494 }
1495 }
1496
1497 fn correct_grouping_map_by_product_modulo_key(a: Vec<u8>, modulo: u8) -> () {
1498 let modulo = Wrapping(if modulo == 0 { 1 } else { modulo } as u64); // Avoid `% 0`
1499 let lookup = a.iter().map(|&b| Wrapping(b as u64)) // Avoid overflows
1500 .into_grouping_map_by(|i| i % modulo)
1501 .product();
1502
1503 let group_map_lookup = a.iter().map(|&b| Wrapping(b as u64))
1504 .map(|i| (i % modulo, i))
1505 .into_group_map()
1506 .into_iter()
1507 .map(|(key, vals)| (key, vals.into_iter().product::<Wrapping<u64>>()))
1508 .collect::<HashMap<_,_>>();
1509 assert_eq!(lookup, group_map_lookup);
1510
1511 for (&key, &prod) in lookup.iter() {
1512 assert_eq!(
1513 prod,
1514 a.iter()
1515 .map(|&b| Wrapping(b as u64))
1516 .filter(|&val| val % modulo == key)
1517 .product::<Wrapping<u64>>()
1518 );
1519 }
1520 }
1521
1522 // This should check that if multiple elements are equally minimum or maximum
1523 // then `max`, `min` and `minmax` pick the first minimum and the last maximum.
1524 // This is to be consistent with `std::iter::max` and `std::iter::min`.
1525 fn correct_grouping_map_by_min_max_minmax_order_modulo_key() -> () {
1526 use itertools::MinMaxResult;
1527
1528 let lookup = (0..=10)
1529 .into_grouping_map_by(|_| 0)
1530 .max_by(|_, _, _| Ordering::Equal);
1531
1532 assert_eq!(lookup[&0], 10);
1533
1534 let lookup = (0..=10)
1535 .into_grouping_map_by(|_| 0)
1536 .min_by(|_, _, _| Ordering::Equal);
1537
1538 assert_eq!(lookup[&0], 0);
1539
1540 let lookup = (0..=10)
1541 .into_grouping_map_by(|_| 0)
1542 .minmax_by(|_, _, _| Ordering::Equal);
1543
1544 assert_eq!(lookup[&0], MinMaxResult::MinMax(0, 10));
1545 }
1546}
1547
1548quickcheck! {
1549 fn counts(nums: Vec<isize>) -> TestResult {
1550 let counts = nums.iter().counts();
1551 for (&item, &count) in counts.iter() {
1552 #[allow(clippy::absurd_extreme_comparisons)]
1553 if count <= 0 {
1554 return TestResult::failed();
1555 }
1556 if count != nums.iter().filter(|&x| x == item).count() {
1557 return TestResult::failed();
1558 }
1559 }
1560 for item in nums.iter() {
1561 if !counts.contains_key(item) {
1562 return TestResult::failed();
1563 }
1564 }
1565 TestResult::passed()
1566 }
1567}
1568
1569quickcheck! {
1570 fn test_double_ended_zip_2(a: Vec<u8>, b: Vec<u8>) -> TestResult {
1571 let mut x =
1572 multizip((a.clone().into_iter(), b.clone().into_iter()))
1573 .collect_vec();
1574 x.reverse();
1575
1576 let y =
1577 multizip((a.into_iter(), b.into_iter()))
1578 .rfold(Vec::new(), |mut vec, e| { vec.push(e); vec });
1579
1580 TestResult::from_bool(itertools::equal(x, y))
1581 }
1582
1583 fn test_double_ended_zip_3(a: Vec<u8>, b: Vec<u8>, c: Vec<u8>) -> TestResult {
1584 let mut x =
1585 multizip((a.clone().into_iter(), b.clone().into_iter(), c.clone().into_iter()))
1586 .collect_vec();
1587 x.reverse();
1588
1589 let y =
1590 multizip((a.into_iter(), b.into_iter(), c.into_iter()))
1591 .rfold(Vec::new(), |mut vec, e| { vec.push(e); vec });
1592
1593 TestResult::from_bool(itertools::equal(x, y))
1594 }
1595}
1596
1597
1598fn is_fused<I: Iterator>(mut it: I) -> bool
1599{
1600 for _ in it.by_ref() {}
1601 for _ in 0..10{
1602 if it.next().is_some(){
1603 return false;
1604 }
1605 }
1606 true
1607}
1608
1609quickcheck! {
1610 fn fused_combination(a: Iter<i16>) -> bool
1611 {
1612 is_fused(a.clone().combinations(1)) &&
1613 is_fused(a.combinations(3))
1614 }
1615
1616 fn fused_combination_with_replacement(a: Iter<i16>) -> bool
1617 {
1618 is_fused(a.clone().combinations_with_replacement(1)) &&
1619 is_fused(a.combinations_with_replacement(3))
1620 }
1621
1622 fn fused_tuple_combination(a: Iter<i16>) -> bool
1623 {
1624 is_fused(a.clone().fuse().tuple_combinations::<(_,)>()) &&
1625 is_fused(a.fuse().tuple_combinations::<(_,_,_)>())
1626 }
1627
1628 fn fused_unique(a: Iter<i16>) -> bool
1629 {
1630 is_fused(a.fuse().unique())
1631 }
1632
1633 fn fused_unique_by(a: Iter<i16>) -> bool
1634 {
1635 is_fused(a.fuse().unique_by(|x| x % 100))
1636 }
1637
1638 fn fused_interleave_shortest(a: Iter<i16>, b: Iter<i16>) -> bool
1639 {
1640 !is_fused(a.clone().interleave_shortest(b.clone())) &&
1641 is_fused(a.fuse().interleave_shortest(b.fuse()))
1642 }
1643
1644 fn fused_product(a: Iter<i16>, b: Iter<i16>) -> bool
1645 {
1646 is_fused(a.fuse().cartesian_product(b.fuse()))
1647 }
1648
1649 fn fused_merge(a: Iter<i16>, b: Iter<i16>) -> bool
1650 {
1651 is_fused(a.fuse().merge(b.fuse()))
1652 }
1653
1654 fn fused_filter_ok(a: Iter<i16>) -> bool
1655 {
1656 is_fused(a.map(|x| if x % 2 == 0 {Ok(x)} else {Err(x)} )
1657 .filter_ok(|x| x % 3 == 0)
1658 .fuse())
1659 }
1660
1661 fn fused_filter_map_ok(a: Iter<i16>) -> bool
1662 {
1663 is_fused(a.map(|x| if x % 2 == 0 {Ok(x)} else {Err(x)} )
1664 .filter_map_ok(|x| if x % 3 == 0 {Some(x / 3)} else {None})
1665 .fuse())
1666 }
1667
1668 fn fused_positions(a: Iter<i16>) -> bool
1669 {
1670 !is_fused(a.clone().positions(|x|x%2==0)) &&
1671 is_fused(a.fuse().positions(|x|x%2==0))
1672 }
1673
1674 fn fused_update(a: Iter<i16>) -> bool
1675 {
1676 !is_fused(a.clone().update(|x|*x+=1)) &&
1677 is_fused(a.fuse().update(|x|*x+=1))
1678 }
1679
1680 fn fused_tuple_windows(a: Iter<i16>) -> bool
1681 {
1682 is_fused(a.fuse().tuple_windows::<(_,_)>())
1683 }
1684
1685 fn fused_pad_using(a: Iter<i16>) -> bool
1686 {
1687 is_fused(a.fuse().pad_using(100,|_|0))
1688 }
1689}
1690
1691quickcheck! {
1692 fn min_set_contains_min(a: Vec<(usize, char)>) -> bool {
1693 let result_set = a.iter().min_set();
1694 if let Some(result_element) = a.iter().min() {
1695 result_set.contains(&result_element)
1696 } else {
1697 result_set.is_empty()
1698 }
1699 }
1700
1701 fn min_set_by_contains_min(a: Vec<(usize, char)>) -> bool {
1702 let compare = |x: &&(usize, char), y: &&(usize, char)| x.1.cmp(&y.1);
1703 let result_set = a.iter().min_set_by(compare);
1704 if let Some(result_element) = a.iter().min_by(compare) {
1705 result_set.contains(&result_element)
1706 } else {
1707 result_set.is_empty()
1708 }
1709 }
1710
1711 fn min_set_by_key_contains_min(a: Vec<(usize, char)>) -> bool {
1712 let key = |x: &&(usize, char)| x.1;
1713 let result_set = a.iter().min_set_by_key(&key);
1714 if let Some(result_element) = a.iter().min_by_key(&key) {
1715 result_set.contains(&result_element)
1716 } else {
1717 result_set.is_empty()
1718 }
1719 }
1720
1721 fn max_set_contains_max(a: Vec<(usize, char)>) -> bool {
1722 let result_set = a.iter().max_set();
1723 if let Some(result_element) = a.iter().max() {
1724 result_set.contains(&result_element)
1725 } else {
1726 result_set.is_empty()
1727 }
1728 }
1729
1730 fn max_set_by_contains_max(a: Vec<(usize, char)>) -> bool {
1731 let compare = |x: &&(usize, char), y: &&(usize, char)| x.1.cmp(&y.1);
1732 let result_set = a.iter().max_set_by(compare);
1733 if let Some(result_element) = a.iter().max_by(compare) {
1734 result_set.contains(&result_element)
1735 } else {
1736 result_set.is_empty()
1737 }
1738 }
1739
1740 fn max_set_by_key_contains_max(a: Vec<(usize, char)>) -> bool {
1741 let key = |x: &&(usize, char)| x.1;
1742 let result_set = a.iter().max_set_by_key(&key);
1743 if let Some(result_element) = a.iter().max_by_key(&key) {
1744 result_set.contains(&result_element)
1745 } else {
1746 result_set.is_empty()
1747 }
1748 }
1749}
1750