1 //! The purpose of these tests is to cover corner cases of iterators
4 //! In particular we test the tedious size_hint and exact size correctness.
7 use std
::default::Default
;
8 use std
::num
::Wrapping
;
10 use std
::cmp
::{max, min, Ordering}
;
11 use std
::collections
::{HashMap, HashSet}
;
12 use itertools
::Itertools
;
19 use itertools
::free
::{
32 use rand
::seq
::SliceRandom
;
33 use quickcheck
::TestResult
;
35 /// Trait for size hint modifier types
36 trait HintKind
: Copy
+ Send
+ qc
::Arbitrary
{
37 fn loosen_bounds(&self, org_hint
: (usize, Option
<usize>)) -> (usize, Option
<usize>);
40 /// Exact size hint variant that leaves hints unchanged
41 #[derive(Clone, Copy, Debug)]
44 impl HintKind
for Exact
{
45 fn loosen_bounds(&self, org_hint
: (usize, Option
<usize>)) -> (usize, Option
<usize>) {
50 impl qc
::Arbitrary
for Exact
{
51 fn arbitrary
<G
: qc
::Gen
>(_
: &mut G
) -> Self {
56 /// Inexact size hint variant to simulate imprecise (but valid) size hints
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)]
66 impl 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
)))
74 impl 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()];
82 underestimate
: *ue_choices
.choose(g
).unwrap(),
83 overestimate
: *oe_choices
.choose(g
).unwrap(),
87 fn shrink(&self) -> Box
<dyn Iterator
<Item
=Self>> {
88 let underestimate_value
= self.underestimate
;
89 let overestimate_value
= self.overestimate
;
91 underestimate_value
.shrink().flat_map(move |ue_value
|
92 overestimate_value
.shrink().map(move |oe_value
|
94 underestimate
: ue_value
,
95 overestimate
: oe_value
,
103 /// Our base iterator that we can impl Arbitrary for
105 /// By default we'll return inexact bounds estimates for size_hint
106 /// to make tests harder to pass.
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)]
112 struct Iter
<T
, SK
: HintKind
= Inexact
> {
119 impl<T
, HK
> Iter
<T
, HK
> where HK
: HintKind
121 fn new(it
: Range
<T
>, hint_kind
: HK
) -> Self {
130 impl<T
, HK
> Iterator
for Iter
<T
, HK
>
131 where Range
<T
>: Iterator
,
132 <Range
<T
> as Iterator
>::Item
: Default
,
135 type Item
= <Range
<T
> as Iterator
>::Item
;
137 fn next(&mut self) -> Option
<Self::Item
>
139 let elt
= self.iterator
.next();
143 if self.fuse_flag
== 2 {
144 return Some(Default
::default())
150 fn size_hint(&self) -> (usize, Option
<usize>)
152 let org_hint
= self.iterator
.size_hint();
153 self.hint_kind
.loosen_bounds(org_hint
)
157 impl<T
, HK
> DoubleEndedIterator
for Iter
<T
, HK
>
158 where Range
<T
>: DoubleEndedIterator
,
159 <Range
<T
> as Iterator
>::Item
: Default
,
162 fn next_back(&mut self) -> Option
<Self::Item
> { self.iterator.next_back() }
165 impl<T
> ExactSizeIterator
for Iter
<T
, Exact
> where Range
<T
>: ExactSizeIterator
,
166 <Range
<T
> as Iterator
>::Item
: Default
,
169 impl<T
, HK
> qc
::Arbitrary
for Iter
<T
, HK
>
170 where T
: qc
::Arbitrary
,
173 fn arbitrary
<G
: qc
::Gen
>(g
: &mut G
) -> Self
175 Iter
::new(T
::arbitrary(g
)..T
::arbitrary(g
), HK
::arbitrary(g
))
178 fn shrink(&self) -> Box
<dyn Iterator
<Item
=Iter
<T
, HK
>>>
180 let r
= self.iterator
.clone();
181 let hint_kind
= self.hint_kind
;
183 r
.start
.shrink().flat_map(move |a
|
184 r
.end
.shrink().map(move |b
|
185 Iter
::new(a
.clone()..b
, hint_kind
)
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)]
195 struct ShiftRange
<HK
= Inexact
> {
204 impl<HK
> Iterator
for ShiftRange
<HK
> where HK
: HintKind
{
205 type Item
= Iter
<i32, HK
>;
207 fn next(&mut self) -> Option
<Self::Item
> {
208 if self.iter_count
== 0 {
212 let iter
= Iter
::new(self.range_start
..self.range_end
, self.hint_kind
);
214 self.range_start
+= self.start_step
;
215 self.range_end
+= self.end_step
;
216 self.iter_count
-= 1;
222 impl ExactSizeIterator
for ShiftRange
<Exact
> { }
224 impl<HK
> qc
::Arbitrary
for ShiftRange
<HK
>
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;
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
);
250 fn correct_count
<I
, F
>(get_it
: F
) -> bool
255 let mut counts
= vec
![get_it().count()];
258 let mut it
= get_it();
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");
267 if it
.next().is_none() {
271 counts
.push(it
.count());
274 let total_actual_count
= counts
.len() - 1;
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
);
288 fn 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())
297 let mut true_count
= hints
.len(); // start off +1 too much
299 // check all the size hints
300 for &(low
, hi
) in &hints
{
302 if low
> true_count
||
303 (hi
.is_some() && hi
.unwrap() < true_count
)
305 println
!("True size: {:?}, size hint: {:?}", true_count
, (low
, hi
));
306 //println!("All hints: {:?}", hints);
313 fn 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; }
322 if Some(low
) != hi { return false; }
324 let (low
, hi
) = it
.size_hint();
325 low
== 0 && hi
== Some(0)
328 // Exact size for this case, without ExactSizeIterator
329 fn 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; }
338 if Some(low
) != hi { return false; }
340 let (low
, hi
) = it
.size_hint();
341 low
== 0 && hi
== Some(0)
345 * NOTE: Range<i8> is broken!
346 * (all signed ranges are)
348 fn size_range_i8(a: Iter<i8>) -> bool {
353 fn size_range_i16(a: Iter<i16>) -> bool {
358 fn size_range_u8(a: Iter<u8>) -> bool {
363 macro_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)* }
)*} => (
372 fn prop($
($arg
)*) -> $ret
{
375 ::quickcheck
::quickcheck(quickcheck
!(@
fn prop
[] $
($arg
)*));
379 // parse argument list (with patterns allowed) into prop as fn(_, _) -> _
380 (@
fn $f
:ident
[$
($t
:tt
)*]) => {
381 $f
as fn($
($t
),*) -> _
383 (@
fn $f
:ident
[$
($p
:tt
)*] : $
($tail
:tt
)*) => {
384 quickcheck
!(@
fn $f
[$
($p
)* _
] $
($tail
)*)
386 (@
fn $f
:ident
[$
($p
:tt
)*] $t
:tt $
($tail
:tt
)*) => {
387 quickcheck
!(@
fn $f
[$
($p
)*] $
($tail
)*)
393 fn size_product(a
: Iter
<u16>, b
: Iter
<u16>) -> bool
{
394 correct_size_hint(a
.cartesian_product(b
))
396 fn size_product3(a
: Iter
<u16>, b
: Iter
<u16>, c
: Iter
<u16>) -> bool
{
397 correct_size_hint(iproduct
!(a
, b
, c
))
400 fn correct_cartesian_product3(a
: Iter
<u16>, b
: Iter
<u16>, c
: Iter
<u16>,
401 take_manual
: usize) -> ()
403 // test correctness of iproduct through regular iteration (take)
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();
412 actual
.extend((&mut product_iter
).take(take_manual
));
413 if actual
.len() == take_manual
{
414 product_iter
.fold((), |(), elt
| actual
.push(elt
));
416 assert_eq
!(answer
, actual
);
419 fn size_multi_product(a
: ShiftRange
) -> bool
{
420 correct_size_hint(a
.multi_cartesian_product())
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 }
;
426 // test correctness of MultiProduct through regular iteration (take)
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();
436 actual
.extend((&mut multi_product
).take(take_manual
));
437 if actual
.len() == take_manual
{
438 multi_product
.fold((), |(), elt
| actual
.push(elt
));
440 assert_eq
!(answer
, actual
);
442 assert_eq
!(answer
.into_iter().last(), a
.multi_cartesian_product().last());
446 fn size_step(a
: Iter
<i16, Exact
>, s
: usize) -> bool
{
449 s
+= 1; // never zero
451 let filt
= a
.clone().dedup();
452 correct_size_hint(filt
.step(s
)) &&
453 exact_size(a
.step(s
))
457 fn equal_step(a
: Iter
<i16>, s
: usize) -> bool
{
460 s
+= 1; // never zero
463 itertools
::equal(a
.clone().step(s
), a
.filter(|_
| {
464 let keep
= i
% s
== 0;
471 fn equal_step_vec(a
: Vec
<i16>, s
: usize) -> bool
{
474 s
+= 1; // never zero
477 itertools
::equal(a
.iter().step(s
), a
.iter().filter(|_
| {
478 let keep
= i
% s
== 0;
484 fn size_multipeek(a
: Iter
<u16, Exact
>, s
: u8) -> bool
{
485 let mut it
= multipeek(a
);
493 fn size_peek_nth(a
: Iter
<u16, Exact
>, s
: u8) -> bool
{
494 let mut it
= peek_nth(a
);
497 it
.peek_nth(n
as usize);
502 fn equal_merge(mut a
: Vec
<i16>, mut b
: Vec
<i16>) -> bool
{
505 let mut merged
= a
.clone();
506 merged
.extend(b
.iter().cloned());
508 itertools
::equal(&merged
, a
.iter().merge(&b
))
510 fn size_merge(a
: Iter
<u16>, b
: Iter
<u16>) -> bool
{
511 correct_size_hint(a
.merge(b
))
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
)))
518 fn size_zip_rc(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
{
520 correct_size_hint(multizip((&rc
, &rc
, b
)))
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
))
528 fn equal_kmerge(mut a
: Vec
<i16>, mut b
: Vec
<i16>, mut c
: Vec
<i16>) -> bool
{
529 use itertools
::free
::kmerge
;
533 let mut merged
= a
.clone();
534 merged
.extend(b
.iter().cloned());
535 merged
.extend(c
.iter().cloned());
537 itertools
::equal(merged
.into_iter(), kmerge(vec
![a
, b
, c
]))
540 // Any number of input iterators
541 fn equal_kmerge_2(mut inputs
: Vec
<Vec
<i16>>) -> bool
{
542 use itertools
::free
::kmerge
;
544 for input
in &mut inputs
{
547 let mut merged
= inputs
.concat();
549 itertools
::equal(merged
.into_iter(), kmerge(inputs
))
552 // Any number of input iterators
553 fn equal_kmerge_by_ge(mut inputs
: Vec
<Vec
<i16>>) -> bool
{
555 for input
in &mut inputs
{
559 let mut merged
= inputs
.concat();
562 itertools
::equal(merged
.into_iter(),
563 inputs
.into_iter().kmerge_by(|x
, y
| x
>= y
))
566 // Any number of input iterators
567 fn equal_kmerge_by_lt(mut inputs
: Vec
<Vec
<i16>>) -> bool
{
569 for input
in &mut inputs
{
572 let mut merged
= inputs
.concat();
574 itertools
::equal(merged
.into_iter(),
575 inputs
.into_iter().kmerge_by(|x
, y
| x
< y
))
578 // Any number of input iterators
579 fn equal_kmerge_by_le(mut inputs
: Vec
<Vec
<i16>>) -> bool
{
581 for input
in &mut inputs
{
584 let mut merged
= inputs
.concat();
586 itertools
::equal(merged
.into_iter(),
587 inputs
.into_iter().kmerge_by(|x
, y
| x
<= y
))
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
]))
593 fn equal_zip_eq(a
: Vec
<i32>, b
: Vec
<i32>) -> bool
{
594 let len
= std
::cmp
::min(a
.len(), b
.len());
597 itertools
::equal(zip_eq(a
, b
), zip(a
, b
))
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
))
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());
610 it
.filter_map(|elt
| match elt
{
611 EitherOrBoth
::Both(x
, _
) => Some(x
),
612 EitherOrBoth
::Left(x
) => Some(x
),
618 jt
.filter_map(|elt
| match elt
{
619 EitherOrBoth
::Both(_
, y
) => Some(y
),
620 EitherOrBoth
::Right(y
) => Some(y
),
625 fn size_interleave(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
{
626 correct_size_hint(a
.interleave(b
))
628 fn exact_interleave(a
: Iter
<i16, Exact
>, b
: Iter
<i16, Exact
>) -> bool
{
629 exact_size_for_this(a
.interleave(b
))
631 fn size_interleave_shortest(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
{
632 correct_size_hint(a
.interleave_shortest(b
))
634 fn exact_interleave_shortest(a
: Vec
<()>, b
: Vec
<()>) -> bool
{
635 exact_size_for_this(a
.iter().interleave_shortest(&b
))
637 fn size_intersperse(a
: Iter
<i16>, x
: i16) -> bool
{
638 correct_size_hint(a
.intersperse(x
))
640 fn equal_intersperse(a
: Vec
<i32>, x
: i32) -> bool
{
641 let mut inter
= false;
643 for elt
in a
.iter().cloned().intersperse(x
) {
645 if elt
!= x { return false }
647 if elt
!= a
[i
] { return false }
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..] {
662 itertools
::equal(a
.iter().tuple_combinations
::<(_
, _
)>(), v
)
665 fn collect_tuple_matches_size(a
: Iter
<i16>) -> bool
{
666 let size
= a
.clone().count();
667 a
.collect_tuple
::<(_
, _
, _
)>().is_some() == (size
== 3)
670 fn correct_permutations(vals
: HashSet
<i32>, k
: usize) -> () {
671 // Test permutations only on iterators of distinct integers, to prevent
674 const MAX_N
: usize = 5;
676 let n
= min(vals
.len(), MAX_N
);
677 let vals
: HashSet
<i32> = vals
.into_iter().take(n
).collect();
679 let perms
= vals
.iter().permutations(k
);
681 let mut actual
= HashSet
::new();
684 assert_eq
!(perm
.len(), k
);
686 let all_items_valid
= perm
.iter().all(|p
| vals
.contains(p
));
687 assert
!(all_items_valid
, "perm contains value not from input: {:?}", perm
);
689 // Check that all perm items are distinct
691 let perm_set
: HashSet
<_
> = perm
.iter().collect();
694 assert_eq
!(perm
.len(), distinct_len
);
696 // Check that the perm is new
697 assert
!(actual
.insert(perm
.clone()), "perm already encountered: {:?}", perm
);
701 fn permutations_lexic_order(a
: usize, b
: usize) -> () {
708 let expected_first
: Vec
<usize> = (0..k
).collect();
709 let expected_last
: Vec
<usize> = ((n
- k
)..n
).rev().collect();
711 let mut perms
= (0..n
).permutations(k
);
713 let mut curr_perm
= match perms
.next() {
718 assert_eq
!(expected_first
, curr_perm
);
720 for next_perm
in perms
{
722 next_perm
> curr_perm
,
723 "next perm isn't greater-than current; next_perm={:?} curr_perm={:?} n={}",
724 next_perm
, curr_perm
, n
727 curr_perm
= next_perm
;
730 assert_eq
!(expected_last
, curr_perm
);
734 fn permutations_count(n
: usize, k
: usize) -> bool
{
737 correct_count(|| (0..n
).permutations(k
))
740 fn permutations_size(a
: Iter
<i32>, k
: usize) -> bool
{
741 correct_size_hint(a
.take(5).permutations(k
))
744 fn permutations_k0_yields_once(n
: usize) -> () {
746 let expected
: Vec
<Vec
<usize>> = vec
![vec
![]];
747 let actual
= (0..n
).permutations(k
).collect_vec();
749 assert_eq
!(expected
, actual
);
754 fn dedup_via_coalesce(a
: Vec
<i32>) -> bool
{
755 let mut b
= a
.clone();
768 .fold(vec
![], |mut v
, n
| {
777 fn equal_dedup(a
: Vec
<i32>) -> bool
{
778 let mut b
= a
.clone();
780 itertools
::equal(&b
, a
.iter().dedup())
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))
793 fn size_dedup(a
: Vec
<i32>) -> bool
{
794 correct_size_hint(a
.iter().dedup())
799 fn size_dedup_by(a
: Vec
<(i32, i32)>) -> bool
{
800 correct_size_hint(a
.iter().dedup_by(|x
, y
| x
.0==y
.0))
805 fn exact_repeatn((n
, x
): (usize, i32)) -> bool
{
806 let it
= itertools
::repeat_n(x
, n
);
812 fn size_put_back(a
: Vec
<u8>, x
: Option
<u8>) -> bool
{
813 let mut it
= put_back(a
.into_iter());
815 Some(t
) => it
.put_back(t
),
818 correct_size_hint(it
)
823 fn size_put_backn(a
: Vec
<u8>, b
: Vec
<u8>) -> bool
{
824 let mut it
= put_back_n(a
.into_iter());
828 correct_size_hint(it
)
833 fn merge_join_by_ordering_vs_bool(a
: Vec
<u8>, b
: Vec
<u8>) -> bool
{
835 use itertools
::free
::merge_join_by
;
836 let mut has_equal
= false;
837 let it_ord
= merge_join_by(a
.clone(), b
.clone(), Ord
::cmp
).flat_map(|v
| match v
{
838 EitherOrBoth
::Both(l
, r
) => {
840 vec
![Either
::Left(l
), Either
::Right(r
)]
842 EitherOrBoth
::Left(l
) => vec
![Either
::Left(l
)],
843 EitherOrBoth
::Right(r
) => vec
![Either
::Right(r
)],
845 let it_bool
= merge_join_by(a
, b
, PartialOrd
::le
);
846 itertools
::equal(it_ord
, it_bool
) || has_equal
848 fn merge_join_by_bool_unwrapped_is_merge_by(a
: Vec
<u8>, b
: Vec
<u8>) -> bool
{
850 use itertools
::free
::merge_join_by
;
851 let it
= a
.clone().into_iter().merge_by(b
.clone(), PartialOrd
::ge
);
852 let it_join
= merge_join_by(a
, b
, PartialOrd
::ge
).map(Either
::into_inner
);
853 itertools
::equal(it
, it_join
)
858 fn size_tee(a
: Vec
<u8>) -> bool
{
859 let (mut t1
, mut t2
) = a
.iter().tee();
863 exact_size(t1
) && exact_size(t2
)
868 fn size_tee_2(a
: Vec
<u8>) -> bool
{
869 let (mut t1
, mut t2
) = a
.iter().dedup().tee();
873 correct_size_hint(t1
) && correct_size_hint(t2
)
878 fn size_take_while_ref(a
: Vec
<u8>, stop
: u8) -> bool
{
879 correct_size_hint(a
.iter().take_while_ref(|x
| **x
!= stop
))
884 fn equal_partition(a
: Vec
<i32>) -> bool
{
886 let mut ap
= a
.clone();
887 let split_index
= itertools
::partition(&mut ap
, |x
| *x
>= 0);
888 let parted
= (0..split_index
).all(|i
| ap
[i
] >= 0) &&
889 (split_index
..a
.len()).all(|i
| ap
[i
] < 0);
898 fn size_combinations(it
: Iter
<i16>) -> bool
{
899 correct_size_hint(it
.tuple_combinations
::<(_
, _
)>())
904 fn equal_combinations(it
: Iter
<i16>) -> bool
{
905 let values
= it
.clone().collect_vec();
906 let mut cmb
= it
.tuple_combinations();
907 for i
in 0..values
.len() {
908 for j
in i
+1..values
.len() {
909 let pair
= (values
[i
], values
[j
]);
910 if pair
!= cmb
.next().unwrap() {
920 fn size_pad_tail(it
: Iter
<i8>, pad
: u8) -> bool
{
921 correct_size_hint(it
.clone().pad_using(pad
as usize, |_
| 0)) &&
922 correct_size_hint(it
.dropping(1).rev().pad_using(pad
as usize, |_
| 0))
927 fn size_pad_tail2(it
: Iter
<i8, Exact
>, pad
: u8) -> bool
{
928 exact_size(it
.pad_using(pad
as usize, |_
| 0))
933 fn size_powerset(it
: Iter
<u8, Exact
>) -> bool
{
934 // Powerset cardinality gets large very quickly, limit input to keep test fast.
935 correct_size_hint(it
.take(12).powerset())
940 fn size_duplicates(it
: Iter
<i8>) -> bool
{
941 correct_size_hint(it
.duplicates())
946 fn size_unique(it
: Iter
<i8>) -> bool
{
947 correct_size_hint(it
.unique())
950 fn count_unique(it
: Vec
<i8>, take_first
: u8) -> () {
952 let mut v
= it
.clone();
956 let mut iter
= cloned(&it
).unique();
957 let first_count
= (&mut iter
).take(take_first
as usize).count();
958 let rest_count
= iter
.count();
959 assert_eq
!(answer
, first_count
+ rest_count
);
964 fn fuzz_group_by_lazy_1(it
: Iter
<u8>) -> bool
{
966 let groups
= it
.group_by(|k
| *k
);
967 itertools
::equal(jt
, groups
.into_iter().flat_map(|(_
, x
)| x
))
972 fn fuzz_group_by_lazy_2(data
: Vec
<u8>) -> bool
{
973 let groups
= data
.iter().group_by(|k
| *k
/ 10);
974 let res
= itertools
::equal(data
.iter(), groups
.into_iter().flat_map(|(_
, x
)| x
));
980 fn fuzz_group_by_lazy_3(data
: Vec
<u8>) -> bool
{
981 let grouper
= data
.iter().group_by(|k
| *k
/ 10);
982 let groups
= grouper
.into_iter().collect_vec();
983 let res
= itertools
::equal(data
.iter(), groups
.into_iter().flat_map(|(_
, x
)| x
));
989 fn fuzz_group_by_lazy_duo(data
: Vec
<u8>, order
: Vec
<(bool
, bool
)>) -> bool
{
990 let grouper
= data
.iter().group_by(|k
| *k
/ 3);
991 let mut groups1
= grouper
.into_iter();
992 let mut groups2
= grouper
.into_iter();
993 let mut elts
= Vec
::<&u8>::new();
994 let mut old_groups
= Vec
::new();
996 let tup1
= |(_
, b
)| b
;
997 for &(ord
, consume_now
) in &order
{
998 let iter
= &mut [&mut groups1
, &mut groups2
][ord
as usize];
1000 Some((_
, gr
)) => if consume_now
{
1001 for og
in old_groups
.drain(..) {
1006 old_groups
.push(gr
);
1011 for og
in old_groups
.drain(..) {
1014 for gr
in groups1
.map(&tup1
) { elts.extend(gr); }
1015 for gr
in groups2
.map(&tup1
) { elts.extend(gr); }
1016 itertools
::assert_equal(&data
, elts
);
1022 fn chunk_clone_equal(a
: Vec
<u8>, size
: u8) -> () {
1023 let mut size
= size
;
1027 let it
= a
.chunks(size
as usize);
1028 itertools
::assert_equal(it
.clone(), it
);
1033 fn equal_chunks_lazy(a
: Vec
<u8>, size
: u8) -> bool
{
1034 let mut size
= size
;
1038 let chunks
= a
.iter().chunks(size
as usize);
1039 let it
= a
.chunks(size
as usize);
1040 for (a
, b
) in chunks
.into_iter().zip(it
) {
1041 if !itertools
::equal(a
, b
) {
1051 fn equal_circular_tuple_windows_1(a
: Vec
<u8>) -> bool
{
1052 let x
= a
.iter().map(|e
| (e
,) );
1053 let y
= a
.iter().circular_tuple_windows
::<(_
,)>();
1054 itertools
::assert_equal(x
,y
);
1058 fn equal_circular_tuple_windows_2(a
: Vec
<u8>) -> bool
{
1059 let x
= (0..a
.len()).map(|start_idx
| (
1061 &a
[(start_idx
+ 1) % a
.len()],
1063 let y
= a
.iter().circular_tuple_windows
::<(_
, _
)>();
1064 itertools
::assert_equal(x
,y
);
1068 fn equal_circular_tuple_windows_3(a
: Vec
<u8>) -> bool
{
1069 let x
= (0..a
.len()).map(|start_idx
| (
1071 &a
[(start_idx
+ 1) % a
.len()],
1072 &a
[(start_idx
+ 2) % a
.len()],
1074 let y
= a
.iter().circular_tuple_windows
::<(_
, _
, _
)>();
1075 itertools
::assert_equal(x
,y
);
1079 fn equal_circular_tuple_windows_4(a
: Vec
<u8>) -> bool
{
1080 let x
= (0..a
.len()).map(|start_idx
| (
1082 &a
[(start_idx
+ 1) % a
.len()],
1083 &a
[(start_idx
+ 2) % a
.len()],
1084 &a
[(start_idx
+ 3) % a
.len()],
1086 let y
= a
.iter().circular_tuple_windows
::<(_
, _
, _
, _
)>();
1087 itertools
::assert_equal(x
,y
);
1091 fn equal_cloned_circular_tuple_windows(a
: Vec
<u8>) -> bool
{
1092 let x
= a
.iter().circular_tuple_windows
::<(_
, _
, _
, _
)>();
1094 itertools
::assert_equal(x
,y
);
1098 fn equal_cloned_circular_tuple_windows_noninitial(a
: Vec
<u8>) -> bool
{
1099 let mut x
= a
.iter().circular_tuple_windows
::<(_
, _
, _
, _
)>();
1102 itertools
::assert_equal(x
,y
);
1106 fn equal_cloned_circular_tuple_windows_complete(a
: Vec
<u8>) -> bool
{
1107 let mut x
= a
.iter().circular_tuple_windows
::<(_
, _
, _
, _
)>();
1108 for _
in x
.by_ref() {}
1110 itertools
::assert_equal(x
,y
);
1114 fn equal_tuple_windows_1(a
: Vec
<u8>) -> bool
{
1115 let x
= a
.windows(1).map(|s
| (&s
[0], ));
1116 let y
= a
.iter().tuple_windows
::<(_
,)>();
1117 itertools
::equal(x
, y
)
1120 fn equal_tuple_windows_2(a
: Vec
<u8>) -> bool
{
1121 let x
= a
.windows(2).map(|s
| (&s
[0], &s
[1]));
1122 let y
= a
.iter().tuple_windows
::<(_
, _
)>();
1123 itertools
::equal(x
, y
)
1126 fn equal_tuple_windows_3(a
: Vec
<u8>) -> bool
{
1127 let x
= a
.windows(3).map(|s
| (&s
[0], &s
[1], &s
[2]));
1128 let y
= a
.iter().tuple_windows
::<(_
, _
, _
)>();
1129 itertools
::equal(x
, y
)
1132 fn equal_tuple_windows_4(a
: Vec
<u8>) -> bool
{
1133 let x
= a
.windows(4).map(|s
| (&s
[0], &s
[1], &s
[2], &s
[3]));
1134 let y
= a
.iter().tuple_windows
::<(_
, _
, _
, _
)>();
1135 itertools
::equal(x
, y
)
1138 fn equal_tuples_1(a
: Vec
<u8>) -> bool
{
1139 let x
= a
.chunks(1).map(|s
| (&s
[0], ));
1140 let y
= a
.iter().tuples
::<(_
,)>();
1141 itertools
::equal(x
, y
)
1144 fn equal_tuples_2(a
: Vec
<u8>) -> bool
{
1145 let x
= a
.chunks(2).filter(|s
| s
.len() == 2).map(|s
| (&s
[0], &s
[1]));
1146 let y
= a
.iter().tuples
::<(_
, _
)>();
1147 itertools
::equal(x
, y
)
1150 fn equal_tuples_3(a
: Vec
<u8>) -> bool
{
1151 let x
= a
.chunks(3).filter(|s
| s
.len() == 3).map(|s
| (&s
[0], &s
[1], &s
[2]));
1152 let y
= a
.iter().tuples
::<(_
, _
, _
)>();
1153 itertools
::equal(x
, y
)
1156 fn equal_tuples_4(a
: Vec
<u8>) -> bool
{
1157 let x
= a
.chunks(4).filter(|s
| s
.len() == 4).map(|s
| (&s
[0], &s
[1], &s
[2], &s
[3]));
1158 let y
= a
.iter().tuples
::<(_
, _
, _
, _
)>();
1159 itertools
::equal(x
, y
)
1162 fn exact_tuple_buffer(a
: Vec
<u8>) -> bool
{
1163 let mut iter
= a
.iter().tuples
::<(_
, _
, _
, _
)>();
1165 let buffer
= iter
.into_buffer();
1166 assert_eq
!(buffer
.len(), a
.len() % 4);
1173 fn with_position_exact_size_1(a
: Vec
<u8>) -> bool
{
1174 exact_size_for_this(a
.iter().with_position())
1176 fn with_position_exact_size_2(a
: Iter
<u8, Exact
>) -> bool
{
1177 exact_size_for_this(a
.with_position())
1182 fn correct_group_map_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1183 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1184 let count
= a
.len();
1185 let lookup
= a
.into_iter().map(|i
| (i
% modulo
, i
)).into_group_map();
1187 assert_eq
!(lookup
.values().flat_map(|vals
| vals
.iter()).count(), count
);
1189 for (&key
, vals
) in lookup
.iter() {
1190 assert
!(vals
.iter().all(|&val
| val
% modulo
== key
));
1195 /// A peculiar type: Equality compares both tuple items, but ordering only the
1196 /// first item. This is so we can check the stability property easily.
1197 #[derive(Clone, Debug, PartialEq, Eq)]
1198 struct Val(u32, u32);
1200 impl PartialOrd
<Val
> for Val
{
1201 fn partial_cmp(&self, other
: &Val
) -> Option
<Ordering
> {
1202 self.0.partial_cmp(&other
.0)
1207 fn cmp(&self, other
: &Val
) -> Ordering
{
1208 self.0.cmp(&other
.0)
1212 impl qc
::Arbitrary
for Val
{
1213 fn arbitrary
<G
: qc
::Gen
>(g
: &mut G
) -> Self {
1214 let (x
, y
) = <(u32, u32)>::arbitrary(g
);
1217 fn shrink(&self) -> Box
<dyn Iterator
<Item
= Self>> {
1218 Box
::new((self.0, self.1).shrink().map(|(x
, y
)| Val(x
, y
)))
1223 fn minmax(a
: Vec
<Val
>) -> bool
{
1224 use itertools
::MinMaxResult
;
1227 let minmax
= a
.iter().minmax();
1228 let expected
= match a
.len() {
1229 0 => MinMaxResult
::NoElements
,
1230 1 => MinMaxResult
::OneElement(&a
[0]),
1231 _
=> MinMaxResult
::MinMax(a
.iter().min().unwrap(),
1232 a
.iter().max().unwrap()),
1239 fn minmax_f64(a
: Vec
<f64>) -> TestResult
{
1240 use itertools
::MinMaxResult
;
1242 if a
.iter().any(|x
| x
.is_nan()) {
1243 return TestResult
::discard();
1246 let min
= cloned(&a
).fold1(f64::min
);
1247 let max
= cloned(&a
).fold1(f64::max
);
1249 let minmax
= cloned(&a
).minmax();
1250 let expected
= match a
.len() {
1251 0 => MinMaxResult
::NoElements
,
1252 1 => MinMaxResult
::OneElement(min
.unwrap()),
1253 _
=> MinMaxResult
::MinMax(min
.unwrap(), max
.unwrap()),
1255 TestResult
::from_bool(minmax
== expected
)
1260 #[allow(deprecated)]
1261 fn tree_fold1_f64(mut a
: Vec
<f64>) -> TestResult
{
1262 fn collapse_adjacent
<F
>(x
: Vec
<f64>, mut f
: F
) -> Vec
<f64>
1263 where F
: FnMut(f64, f64) -> f64
1265 let mut out
= Vec
::new();
1266 for i
in (0..x
.len()).step(2) {
1270 out
.push(f(x
[i
], x
[i
+1]));
1276 if a
.iter().any(|x
| x
.is_nan()) {
1277 return TestResult
::discard();
1280 let actual
= a
.iter().cloned().tree_fold1(f64::atan2
);
1283 a
= collapse_adjacent(a
, f64::atan2
);
1285 let expected
= a
.pop();
1287 TestResult
::from_bool(actual
== expected
)
1292 fn exactly_one_i32(a
: Vec
<i32>) -> TestResult
{
1293 let ret
= a
.iter().cloned().exactly_one();
1295 1 => TestResult
::from_bool(ret
.unwrap() == a
[0]),
1296 _
=> TestResult
::from_bool(ret
.unwrap_err().eq(a
.iter().cloned())),
1302 fn at_most_one_i32(a
: Vec
<i32>) -> TestResult
{
1303 let ret
= a
.iter().cloned().at_most_one();
1305 0 => TestResult
::from_bool(ret
.unwrap() == None
),
1306 1 => TestResult
::from_bool(ret
.unwrap() == Some(a
[0])),
1307 _
=> TestResult
::from_bool(ret
.unwrap_err().eq(a
.iter().cloned())),
1313 fn consistent_grouping_map_with_by(a
: Vec
<u8>, modulo
: u8) -> () {
1314 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1316 let lookup_grouping_map
= a
.iter().copied().map(|i
| (i
% modulo
, i
)).into_grouping_map().collect
::<Vec
<_
>>();
1317 let lookup_grouping_map_by
= a
.iter().copied().into_grouping_map_by(|i
| i
% modulo
).collect
::<Vec
<_
>>();
1319 assert_eq
!(lookup_grouping_map
, lookup_grouping_map_by
);
1322 fn correct_grouping_map_by_aggregate_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1323 let modulo
= if modulo
< 2 { 2 }
else { modulo }
as u64; // Avoid `% 0`
1324 let lookup
= a
.iter()
1325 .map(|&b
| b
as u64) // Avoid overflows
1326 .into_grouping_map_by(|i
| i
% modulo
)
1327 .aggregate(|acc
, &key
, val
| {
1328 assert
!(val
% modulo
== key
);
1329 if val
% (modulo
- 1) == 0 {
1332 Some(acc
.unwrap_or(0) + val
)
1336 let group_map_lookup
= a
.iter()
1338 .map(|i
| (i
% modulo
, i
))
1341 .filter_map(|(key
, vals
)| {
1342 vals
.into_iter().fold(None
, |acc
, val
| {
1343 if val
% (modulo
- 1) == 0 {
1346 Some(acc
.unwrap_or(0) + val
)
1348 }).map(|new_val
| (key
, new_val
))
1350 .collect
::<HashMap
<_
,_
>>();
1351 assert_eq
!(lookup
, group_map_lookup
);
1353 for m
in 0..modulo
{
1355 lookup
.get(&m
).copied(),
1358 .filter(|&val
| val
% modulo
== m
)
1359 .fold(None
, |acc
, val
| {
1360 if val
% (modulo
- 1) == 0 {
1363 Some(acc
.unwrap_or(0) + val
)
1370 fn correct_grouping_map_by_fold_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1371 let modulo
= if modulo
== 0 { 1 }
else { modulo }
as u64; // Avoid `% 0`
1372 let lookup
= a
.iter().map(|&b
| b
as u64) // Avoid overflows
1373 .into_grouping_map_by(|i
| i
% modulo
)
1374 .fold(0u64, |acc
, &key
, val
| {
1375 assert
!(val
% modulo
== key
);
1379 let group_map_lookup
= a
.iter()
1381 .map(|i
| (i
% modulo
, i
))
1384 .map(|(key
, vals
)| (key
, vals
.into_iter().sum()))
1385 .collect
::<HashMap
<_
,_
>>();
1386 assert_eq
!(lookup
, group_map_lookup
);
1388 for (&key
, &sum
) in lookup
.iter() {
1389 assert_eq
!(sum
, a
.iter().map(|&b
| b
as u64).filter(|&val
| val
% modulo
== key
).sum
::<u64>());
1393 fn correct_grouping_map_by_fold_first_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1394 let modulo
= if modulo
== 0 { 1 }
else { modulo }
as u64; // Avoid `% 0`
1395 let lookup
= a
.iter().map(|&b
| b
as u64) // Avoid overflows
1396 .into_grouping_map_by(|i
| i
% modulo
)
1397 .fold_first(|acc
, &key
, val
| {
1398 assert
!(val
% modulo
== key
);
1402 // TODO: Swap `fold1` with stdlib's `fold_first` when it's stabilized
1403 let group_map_lookup
= a
.iter()
1405 .map(|i
| (i
% modulo
, i
))
1408 .map(|(key
, vals
)| (key
, vals
.into_iter().fold1(|acc
, val
| acc
+ val
).unwrap()))
1409 .collect
::<HashMap
<_
,_
>>();
1410 assert_eq
!(lookup
, group_map_lookup
);
1412 for (&key
, &sum
) in lookup
.iter() {
1413 assert_eq
!(sum
, a
.iter().map(|&b
| b
as u64).filter(|&val
| val
% modulo
== key
).sum
::<u64>());
1417 fn correct_grouping_map_by_collect_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1418 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1419 let lookup_grouping_map
= a
.iter().copied().into_grouping_map_by(|i
| i
% modulo
).collect
::<Vec
<_
>>();
1420 let lookup_group_map
= a
.iter().copied().map(|i
| (i
% modulo
, i
)).into_group_map();
1422 assert_eq
!(lookup_grouping_map
, lookup_group_map
);
1425 fn correct_grouping_map_by_max_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1426 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1427 let lookup
= a
.iter().copied().into_grouping_map_by(|i
| i
% modulo
).max();
1429 let group_map_lookup
= a
.iter().copied()
1430 .map(|i
| (i
% modulo
, i
))
1433 .map(|(key
, vals
)| (key
, vals
.into_iter().max().unwrap()))
1434 .collect
::<HashMap
<_
,_
>>();
1435 assert_eq
!(lookup
, group_map_lookup
);
1437 for (&key
, &max
) in lookup
.iter() {
1438 assert_eq
!(Some(max
), a
.iter().copied().filter(|&val
| val
% modulo
== key
).max());
1442 fn correct_grouping_map_by_max_by_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1443 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1444 let lookup
= a
.iter().copied().into_grouping_map_by(|i
| i
% modulo
).max_by(|_
, v1
, v2
| v1
.cmp(v2
));
1446 let group_map_lookup
= a
.iter().copied()
1447 .map(|i
| (i
% modulo
, i
))
1450 .map(|(key
, vals
)| (key
, vals
.into_iter().max_by(|v1
, v2
| v1
.cmp(v2
)).unwrap()))
1451 .collect
::<HashMap
<_
,_
>>();
1452 assert_eq
!(lookup
, group_map_lookup
);
1454 for (&key
, &max
) in lookup
.iter() {
1455 assert_eq
!(Some(max
), a
.iter().copied().filter(|&val
| val
% modulo
== key
).max_by(|v1
, v2
| v1
.cmp(v2
)));
1459 fn correct_grouping_map_by_max_by_key_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1460 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1461 let lookup
= a
.iter().copied().into_grouping_map_by(|i
| i
% modulo
).max_by_key(|_
, &val
| val
);
1463 let group_map_lookup
= a
.iter().copied()
1464 .map(|i
| (i
% modulo
, i
))
1467 .map(|(key
, vals
)| (key
, vals
.into_iter().max_by_key(|&val
| val
).unwrap()))
1468 .collect
::<HashMap
<_
,_
>>();
1469 assert_eq
!(lookup
, group_map_lookup
);
1471 for (&key
, &max
) in lookup
.iter() {
1472 assert_eq
!(Some(max
), a
.iter().copied().filter(|&val
| val
% modulo
== key
).max_by_key(|&val
| val
));
1476 fn correct_grouping_map_by_min_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1477 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1478 let lookup
= a
.iter().copied().into_grouping_map_by(|i
| i
% modulo
).min();
1480 let group_map_lookup
= a
.iter().copied()
1481 .map(|i
| (i
% modulo
, i
))
1484 .map(|(key
, vals
)| (key
, vals
.into_iter().min().unwrap()))
1485 .collect
::<HashMap
<_
,_
>>();
1486 assert_eq
!(lookup
, group_map_lookup
);
1488 for (&key
, &min
) in lookup
.iter() {
1489 assert_eq
!(Some(min
), a
.iter().copied().filter(|&val
| val
% modulo
== key
).min());
1493 fn correct_grouping_map_by_min_by_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1494 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1495 let lookup
= a
.iter().copied().into_grouping_map_by(|i
| i
% modulo
).min_by(|_
, v1
, v2
| v1
.cmp(v2
));
1497 let group_map_lookup
= a
.iter().copied()
1498 .map(|i
| (i
% modulo
, i
))
1501 .map(|(key
, vals
)| (key
, vals
.into_iter().min_by(|v1
, v2
| v1
.cmp(v2
)).unwrap()))
1502 .collect
::<HashMap
<_
,_
>>();
1503 assert_eq
!(lookup
, group_map_lookup
);
1505 for (&key
, &min
) in lookup
.iter() {
1506 assert_eq
!(Some(min
), a
.iter().copied().filter(|&val
| val
% modulo
== key
).min_by(|v1
, v2
| v1
.cmp(v2
)));
1510 fn correct_grouping_map_by_min_by_key_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1511 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1512 let lookup
= a
.iter().copied().into_grouping_map_by(|i
| i
% modulo
).min_by_key(|_
, &val
| val
);
1514 let group_map_lookup
= a
.iter().copied()
1515 .map(|i
| (i
% modulo
, i
))
1518 .map(|(key
, vals
)| (key
, vals
.into_iter().min_by_key(|&val
| val
).unwrap()))
1519 .collect
::<HashMap
<_
,_
>>();
1520 assert_eq
!(lookup
, group_map_lookup
);
1522 for (&key
, &min
) in lookup
.iter() {
1523 assert_eq
!(Some(min
), a
.iter().copied().filter(|&val
| val
% modulo
== key
).min_by_key(|&val
| val
));
1527 fn correct_grouping_map_by_minmax_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1528 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1529 let lookup
= a
.iter().copied().into_grouping_map_by(|i
| i
% modulo
).minmax();
1531 let group_map_lookup
= a
.iter().copied()
1532 .map(|i
| (i
% modulo
, i
))
1535 .map(|(key
, vals
)| (key
, vals
.into_iter().minmax()))
1536 .collect
::<HashMap
<_
,_
>>();
1537 assert_eq
!(lookup
, group_map_lookup
);
1539 for (&key
, &minmax
) in lookup
.iter() {
1540 assert_eq
!(minmax
, a
.iter().copied().filter(|&val
| val
% modulo
== key
).minmax());
1544 fn correct_grouping_map_by_minmax_by_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1545 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1546 let lookup
= a
.iter().copied().into_grouping_map_by(|i
| i
% modulo
).minmax_by(|_
, v1
, v2
| v1
.cmp(v2
));
1548 let group_map_lookup
= a
.iter().copied()
1549 .map(|i
| (i
% modulo
, i
))
1552 .map(|(key
, vals
)| (key
, vals
.into_iter().minmax_by(|v1
, v2
| v1
.cmp(v2
))))
1553 .collect
::<HashMap
<_
,_
>>();
1554 assert_eq
!(lookup
, group_map_lookup
);
1556 for (&key
, &minmax
) in lookup
.iter() {
1557 assert_eq
!(minmax
, a
.iter().copied().filter(|&val
| val
% modulo
== key
).minmax_by(|v1
, v2
| v1
.cmp(v2
)));
1561 fn correct_grouping_map_by_minmax_by_key_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1562 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1563 let lookup
= a
.iter().copied().into_grouping_map_by(|i
| i
% modulo
).minmax_by_key(|_
, &val
| val
);
1565 let group_map_lookup
= a
.iter().copied()
1566 .map(|i
| (i
% modulo
, i
))
1569 .map(|(key
, vals
)| (key
, vals
.into_iter().minmax_by_key(|&val
| val
)))
1570 .collect
::<HashMap
<_
,_
>>();
1571 assert_eq
!(lookup
, group_map_lookup
);
1573 for (&key
, &minmax
) in lookup
.iter() {
1574 assert_eq
!(minmax
, a
.iter().copied().filter(|&val
| val
% modulo
== key
).minmax_by_key(|&val
| val
));
1578 fn correct_grouping_map_by_sum_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1579 let modulo
= if modulo
== 0 { 1 }
else { modulo }
as u64; // Avoid `% 0`
1580 let lookup
= a
.iter().map(|&b
| b
as u64) // Avoid overflows
1581 .into_grouping_map_by(|i
| i
% modulo
)
1584 let group_map_lookup
= a
.iter().map(|&b
| b
as u64)
1585 .map(|i
| (i
% modulo
, i
))
1588 .map(|(key
, vals
)| (key
, vals
.into_iter().sum()))
1589 .collect
::<HashMap
<_
,_
>>();
1590 assert_eq
!(lookup
, group_map_lookup
);
1592 for (&key
, &sum
) in lookup
.iter() {
1593 assert_eq
!(sum
, a
.iter().map(|&b
| b
as u64).filter(|&val
| val
% modulo
== key
).sum
::<u64>());
1597 fn correct_grouping_map_by_product_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1598 let modulo
= Wrapping(if modulo
== 0 { 1 }
else { modulo }
as u64); // Avoid `% 0`
1599 let lookup
= a
.iter().map(|&b
| Wrapping(b
as u64)) // Avoid overflows
1600 .into_grouping_map_by(|i
| i
% modulo
)
1603 let group_map_lookup
= a
.iter().map(|&b
| Wrapping(b
as u64))
1604 .map(|i
| (i
% modulo
, i
))
1607 .map(|(key
, vals
)| (key
, vals
.into_iter().product
::<Wrapping
<u64>>()))
1608 .collect
::<HashMap
<_
,_
>>();
1609 assert_eq
!(lookup
, group_map_lookup
);
1611 for (&key
, &prod
) in lookup
.iter() {
1615 .map(|&b
| Wrapping(b
as u64))
1616 .filter(|&val
| val
% modulo
== key
)
1617 .product
::<Wrapping
<u64>>()
1622 // This should check that if multiple elements are equally minimum or maximum
1623 // then `max`, `min` and `minmax` pick the first minimum and the last maximum.
1624 // This is to be consistent with `std::iter::max` and `std::iter::min`.
1625 fn correct_grouping_map_by_min_max_minmax_order_modulo_key() -> () {
1626 use itertools
::MinMaxResult
;
1628 let lookup
= (0..=10)
1629 .into_grouping_map_by(|_
| 0)
1630 .max_by(|_
, _
, _
| Ordering
::Equal
);
1632 assert_eq
!(lookup
[&0], 10);
1634 let lookup
= (0..=10)
1635 .into_grouping_map_by(|_
| 0)
1636 .min_by(|_
, _
, _
| Ordering
::Equal
);
1638 assert_eq
!(lookup
[&0], 0);
1640 let lookup
= (0..=10)
1641 .into_grouping_map_by(|_
| 0)
1642 .minmax_by(|_
, _
, _
| Ordering
::Equal
);
1644 assert_eq
!(lookup
[&0], MinMaxResult
::MinMax(0, 10));
1649 fn counts(nums
: Vec
<isize>) -> TestResult
{
1650 let counts
= nums
.iter().counts();
1651 for (&item
, &count
) in counts
.iter() {
1652 #[allow(clippy::absurd_extreme_comparisons)]
1654 return TestResult
::failed();
1656 if count
!= nums
.iter().filter(|&x
| x
== item
).count() {
1657 return TestResult
::failed();
1660 for item
in nums
.iter() {
1661 if !counts
.contains_key(item
) {
1662 return TestResult
::failed();
1665 TestResult
::passed()
1670 fn test_double_ended_zip_2(a
: Vec
<u8>, b
: Vec
<u8>) -> TestResult
{
1672 multizip((a
.clone().into_iter(), b
.clone().into_iter()))
1677 multizip((a
.into_iter(), b
.into_iter()))
1678 .rfold(Vec
::new(), |mut vec
, e
| { vec.push(e); vec }
);
1680 TestResult
::from_bool(itertools
::equal(x
, y
))
1683 fn test_double_ended_zip_3(a
: Vec
<u8>, b
: Vec
<u8>, c
: Vec
<u8>) -> TestResult
{
1685 multizip((a
.clone().into_iter(), b
.clone().into_iter(), c
.clone().into_iter()))
1690 multizip((a
.into_iter(), b
.into_iter(), c
.into_iter()))
1691 .rfold(Vec
::new(), |mut vec
, e
| { vec.push(e); vec }
);
1693 TestResult
::from_bool(itertools
::equal(x
, y
))
1698 fn is_fused
<I
: Iterator
>(mut it
: I
) -> bool
1700 for _
in it
.by_ref() {}
1702 if it
.next().is_some(){
1710 fn fused_combination(a
: Iter
<i16>) -> bool
1712 is_fused(a
.clone().combinations(1)) &&
1713 is_fused(a
.combinations(3))
1716 fn fused_combination_with_replacement(a
: Iter
<i16>) -> bool
1718 is_fused(a
.clone().combinations_with_replacement(1)) &&
1719 is_fused(a
.combinations_with_replacement(3))
1722 fn fused_tuple_combination(a
: Iter
<i16>) -> bool
1724 is_fused(a
.clone().fuse().tuple_combinations
::<(_
,)>()) &&
1725 is_fused(a
.fuse().tuple_combinations
::<(_
,_
,_
)>())
1728 fn fused_unique(a
: Iter
<i16>) -> bool
1730 is_fused(a
.fuse().unique())
1733 fn fused_unique_by(a
: Iter
<i16>) -> bool
1735 is_fused(a
.fuse().unique_by(|x
| x
% 100))
1738 fn fused_interleave_shortest(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
1740 !is_fused(a
.clone().interleave_shortest(b
.clone())) &&
1741 is_fused(a
.fuse().interleave_shortest(b
.fuse()))
1744 fn fused_product(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
1746 is_fused(a
.fuse().cartesian_product(b
.fuse()))
1749 fn fused_merge(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
1751 is_fused(a
.fuse().merge(b
.fuse()))
1754 fn fused_filter_ok(a
: Iter
<i16>) -> bool
1756 is_fused(a
.map(|x
| if x
% 2 == 0 {Ok(x)}
else {Err(x)}
)
1757 .filter_ok(|x
| x
% 3 == 0)
1761 fn fused_filter_map_ok(a
: Iter
<i16>) -> bool
1763 is_fused(a
.map(|x
| if x
% 2 == 0 {Ok(x)}
else {Err(x)}
)
1764 .filter_map_ok(|x
| if x
% 3 == 0 {Some(x / 3)}
else {None}
)
1768 fn fused_positions(a
: Iter
<i16>) -> bool
1770 !is_fused(a
.clone().positions(|x
|x
%2==0)) &&
1771 is_fused(a
.fuse().positions(|x
|x
%2==0))
1774 fn fused_update(a
: Iter
<i16>) -> bool
1776 !is_fused(a
.clone().update(|x
|*x
+=1)) &&
1777 is_fused(a
.fuse().update(|x
|*x
+=1))
1780 fn fused_tuple_windows(a
: Iter
<i16>) -> bool
1782 is_fused(a
.fuse().tuple_windows
::<(_
,_
)>())
1785 fn fused_pad_using(a
: Iter
<i16>) -> bool
1787 is_fused(a
.fuse().pad_using(100,|_
|0))
1792 fn min_set_contains_min(a
: Vec
<(usize, char)>) -> bool
{
1793 let result_set
= a
.iter().min_set();
1794 if let Some(result_element
) = a
.iter().min() {
1795 result_set
.contains(&result_element
)
1797 result_set
.is_empty()
1801 fn min_set_by_contains_min(a
: Vec
<(usize, char)>) -> bool
{
1802 let compare
= |x
: &&(usize, char), y
: &&(usize, char)| x
.1.cmp(&y
.1);
1803 let result_set
= a
.iter().min_set_by(compare
);
1804 if let Some(result_element
) = a
.iter().min_by(compare
) {
1805 result_set
.contains(&result_element
)
1807 result_set
.is_empty()
1811 fn min_set_by_key_contains_min(a
: Vec
<(usize, char)>) -> bool
{
1812 let key
= |x
: &&(usize, char)| x
.1;
1813 let result_set
= a
.iter().min_set_by_key(&key
);
1814 if let Some(result_element
) = a
.iter().min_by_key(&key
) {
1815 result_set
.contains(&result_element
)
1817 result_set
.is_empty()
1821 fn max_set_contains_max(a
: Vec
<(usize, char)>) -> bool
{
1822 let result_set
= a
.iter().max_set();
1823 if let Some(result_element
) = a
.iter().max() {
1824 result_set
.contains(&result_element
)
1826 result_set
.is_empty()
1830 fn max_set_by_contains_max(a
: Vec
<(usize, char)>) -> bool
{
1831 let compare
= |x
: &&(usize, char), y
: &&(usize, char)| x
.1.cmp(&y
.1);
1832 let result_set
= a
.iter().max_set_by(compare
);
1833 if let Some(result_element
) = a
.iter().max_by(compare
) {
1834 result_set
.contains(&result_element
)
1836 result_set
.is_empty()
1840 fn max_set_by_key_contains_max(a
: Vec
<(usize, char)>) -> bool
{
1841 let key
= |x
: &&(usize, char)| x
.1;
1842 let result_set
= a
.iter().max_set_by_key(&key
);
1843 if let Some(result_element
) = a
.iter().max_by_key(&key
) {
1844 result_set
.contains(&result_element
)
1846 result_set
.is_empty()