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
;
9 use std
::cmp
::{max, min, Ordering}
;
10 use std
::collections
::HashSet
;
11 use itertools
::Itertools
;
18 use itertools
::free
::{
30 use rand
::seq
::SliceRandom
;
31 use quickcheck
::TestResult
;
33 /// Trait for size hint modifier types
34 trait HintKind
: Copy
+ Send
+ qc
::Arbitrary
{
35 fn loosen_bounds(&self, org_hint
: (usize, Option
<usize>)) -> (usize, Option
<usize>);
38 /// Exact size hint variant that leaves hints unchanged
39 #[derive(Clone, Copy, Debug)]
42 impl HintKind
for Exact
{
43 fn loosen_bounds(&self, org_hint
: (usize, Option
<usize>)) -> (usize, Option
<usize>) {
48 impl qc
::Arbitrary
for Exact
{
49 fn arbitrary
<G
: qc
::Gen
>(_
: &mut G
) -> Self {
54 /// Inexact size hint variant to simulate imprecise (but valid) size hints
56 /// Will always decrease the lower bound and increase the upper bound
57 /// of the size hint by set amounts.
58 #[derive(Clone, Copy, Debug)]
64 impl HintKind
for Inexact
{
65 fn loosen_bounds(&self, org_hint
: (usize, Option
<usize>)) -> (usize, Option
<usize>) {
66 let (org_lower
, org_upper
) = org_hint
;
67 (org_lower
.saturating_sub(self.underestimate
),
68 org_upper
.and_then(move |x
| x
.checked_add(self.overestimate
)))
72 impl qc
::Arbitrary
for Inexact
{
73 fn arbitrary
<G
: qc
::Gen
>(g
: &mut G
) -> Self {
74 let ue_value
= usize::arbitrary(g
);
75 let oe_value
= usize::arbitrary(g
);
76 // Compensate for quickcheck using extreme values too rarely
77 let ue_choices
= &[0, ue_value
, usize::max_value()];
78 let oe_choices
= &[0, oe_value
, usize::max_value()];
80 underestimate
: *ue_choices
.choose(g
).unwrap(),
81 overestimate
: *oe_choices
.choose(g
).unwrap(),
85 fn shrink(&self) -> Box
<dyn Iterator
<Item
=Self>> {
86 let underestimate_value
= self.underestimate
;
87 let overestimate_value
= self.overestimate
;
89 underestimate_value
.shrink().flat_map(move |ue_value
|
90 overestimate_value
.shrink().map(move |oe_value
|
92 underestimate
: ue_value
,
93 overestimate
: oe_value
,
101 /// Our base iterator that we can impl Arbitrary for
103 /// By default we'll return inexact bounds estimates for size_hint
104 /// to make tests harder to pass.
106 /// NOTE: Iter is tricky and is not fused, to help catch bugs.
107 /// At the end it will return None once, then return Some(0),
108 /// then return None again.
109 #[derive(Clone, Debug)]
110 struct Iter
<T
, SK
: HintKind
= Inexact
> {
117 impl<T
, HK
> Iter
<T
, HK
> where HK
: HintKind
119 fn new(it
: Range
<T
>, hint_kind
: HK
) -> Self {
128 impl<T
, HK
> Iterator
for Iter
<T
, HK
>
129 where Range
<T
>: Iterator
,
130 <Range
<T
> as Iterator
>::Item
: Default
,
133 type Item
= <Range
<T
> as Iterator
>::Item
;
135 fn next(&mut self) -> Option
<Self::Item
>
137 let elt
= self.iterator
.next();
141 if self.fuse_flag
== 2 {
142 return Some(Default
::default())
148 fn size_hint(&self) -> (usize, Option
<usize>)
150 let org_hint
= self.iterator
.size_hint();
151 self.hint_kind
.loosen_bounds(org_hint
)
155 impl<T
, HK
> DoubleEndedIterator
for Iter
<T
, HK
>
156 where Range
<T
>: DoubleEndedIterator
,
157 <Range
<T
> as Iterator
>::Item
: Default
,
160 fn next_back(&mut self) -> Option
<Self::Item
> { self.iterator.next_back() }
163 impl<T
> ExactSizeIterator
for Iter
<T
, Exact
> where Range
<T
>: ExactSizeIterator
,
164 <Range
<T
> as Iterator
>::Item
: Default
,
167 impl<T
, HK
> qc
::Arbitrary
for Iter
<T
, HK
>
168 where T
: qc
::Arbitrary
,
171 fn arbitrary
<G
: qc
::Gen
>(g
: &mut G
) -> Self
173 Iter
::new(T
::arbitrary(g
)..T
::arbitrary(g
), HK
::arbitrary(g
))
176 fn shrink(&self) -> Box
<dyn Iterator
<Item
=Iter
<T
, HK
>>>
178 let r
= self.iterator
.clone();
179 let hint_kind
= self.hint_kind
;
181 r
.start
.shrink().flat_map(move |a
|
182 r
.end
.shrink().map(move |b
|
183 Iter
::new(a
.clone()..b
, hint_kind
)
190 /// A meta-iterator which yields `Iter<i32>`s whose start/endpoints are
191 /// increased or decreased linearly on each iteration.
192 #[derive(Clone, Debug)]
193 struct ShiftRange
<HK
= Inexact
> {
202 impl<HK
> Iterator
for ShiftRange
<HK
> where HK
: HintKind
{
203 type Item
= Iter
<i32, HK
>;
205 fn next(&mut self) -> Option
<Self::Item
> {
206 if self.iter_count
== 0 {
210 let iter
= Iter
::new(self.range_start
..self.range_end
, self.hint_kind
);
212 self.range_start
+= self.start_step
;
213 self.range_end
+= self.end_step
;
214 self.iter_count
-= 1;
220 impl ExactSizeIterator
for ShiftRange
<Exact
> { }
222 impl<HK
> qc
::Arbitrary
for ShiftRange
<HK
>
225 fn arbitrary
<G
: qc
::Gen
>(g
: &mut G
) -> Self {
226 const MAX_STARTING_RANGE_DIFF
: i32 = 32;
227 const MAX_STEP_MODULO
: i32 = 8;
228 const MAX_ITER_COUNT
: u32 = 3;
230 let range_start
= qc
::Arbitrary
::arbitrary(g
);
231 let range_end
= range_start
+ g
.gen_range(0, MAX_STARTING_RANGE_DIFF
+ 1);
232 let start_step
= g
.gen_range(-MAX_STEP_MODULO
, MAX_STEP_MODULO
+ 1);
233 let end_step
= g
.gen_range(-MAX_STEP_MODULO
, MAX_STEP_MODULO
+ 1);
234 let iter_count
= g
.gen_range(0, MAX_ITER_COUNT
+ 1);
235 let hint_kind
= qc
::Arbitrary
::arbitrary(g
);
248 fn correct_count
<I
, F
>(get_it
: F
) -> bool
253 let mut counts
= vec
![get_it().count()];
256 let mut it
= get_it();
258 for _
in 0..(counts
.len() - 1) {
259 if let None
= it
.next() {
260 panic
!("Iterator shouldn't be finished, may not be deterministic");
264 if let None
= it
.next() {
268 counts
.push(it
.count());
271 let total_actual_count
= counts
.len() - 1;
273 for (i
, returned_count
) in counts
.into_iter().enumerate() {
274 let actual_count
= total_actual_count
- i
;
275 if actual_count
!= returned_count
{
276 println
!("Total iterations: {} True count: {} returned count: {}", i
, actual_count
, returned_count
);
285 fn correct_size_hint
<I
: Iterator
>(mut it
: I
) -> bool
{
286 // record size hint at each iteration
287 let initial_hint
= it
.size_hint();
288 let mut hints
= Vec
::with_capacity(initial_hint
.0 + 1);
289 hints
.push(initial_hint
);
290 while let Some(_
) = it
.next() {
291 hints
.push(it
.size_hint())
294 let mut true_count
= hints
.len(); // start off +1 too much
296 // check all the size hints
297 for &(low
, hi
) in &hints
{
299 if low
> true_count
||
300 (hi
.is_some() && hi
.unwrap() < true_count
)
302 println
!("True size: {:?}, size hint: {:?}", true_count
, (low
, hi
));
303 //println!("All hints: {:?}", hints);
310 fn exact_size
<I
: ExactSizeIterator
>(mut it
: I
) -> bool
{
311 // check every iteration
312 let (mut low
, mut hi
) = it
.size_hint();
313 if Some(low
) != hi { return false; }
314 while let Some(_
) = it
.next() {
315 let (xlow
, xhi
) = it
.size_hint();
316 if low
!= xlow
+ 1 { return false; }
319 if Some(low
) != hi { return false; }
321 let (low
, hi
) = it
.size_hint();
322 low
== 0 && hi
== Some(0)
325 // Exact size for this case, without ExactSizeIterator
326 fn exact_size_for_this
<I
: Iterator
>(mut it
: I
) -> bool
{
327 // check every iteration
328 let (mut low
, mut hi
) = it
.size_hint();
329 if Some(low
) != hi { return false; }
330 while let Some(_
) = it
.next() {
331 let (xlow
, xhi
) = it
.size_hint();
332 if low
!= xlow
+ 1 { return false; }
335 if Some(low
) != hi { return false; }
337 let (low
, hi
) = it
.size_hint();
338 low
== 0 && hi
== Some(0)
342 * NOTE: Range<i8> is broken!
343 * (all signed ranges are)
345 fn size_range_i8(a: Iter<i8>) -> bool {
350 fn size_range_i16(a: Iter<i16>) -> bool {
355 fn size_range_u8(a: Iter<u8>) -> bool {
360 macro_rules
! quickcheck
{
361 // accept several property function definitions
362 // The property functions can use pattern matching and `mut` as usual
363 // in the function arguments, but the functions can not be generic.
364 {$($(#$attr:tt)* fn $fn_name:ident($($arg:tt)*) -> $ret:ty { $($code:tt)* }
)*} => (
369 fn prop($
($arg
)*) -> $ret
{
372 ::quickcheck
::quickcheck(quickcheck
!(@
fn prop
[] $
($arg
)*));
376 // parse argument list (with patterns allowed) into prop as fn(_, _) -> _
377 (@
fn $f
:ident
[$
($t
:tt
)*]) => {
378 $f
as fn($
($t
),*) -> _
380 (@
fn $f
:ident
[$
($p
:tt
)*] : $
($tail
:tt
)*) => {
381 quickcheck
!(@
fn $f
[$
($p
)* _
] $
($tail
)*)
383 (@
fn $f
:ident
[$
($p
:tt
)*] $t
:tt $
($tail
:tt
)*) => {
384 quickcheck
!(@
fn $f
[$
($p
)*] $
($tail
)*)
390 fn size_product(a
: Iter
<u16>, b
: Iter
<u16>) -> bool
{
391 correct_size_hint(a
.cartesian_product(b
))
393 fn size_product3(a
: Iter
<u16>, b
: Iter
<u16>, c
: Iter
<u16>) -> bool
{
394 correct_size_hint(iproduct
!(a
, b
, c
))
397 fn correct_cartesian_product3(a
: Iter
<u16>, b
: Iter
<u16>, c
: Iter
<u16>,
398 take_manual
: usize) -> ()
400 // test correctness of iproduct through regular iteration (take)
405 let answer
: Vec
<_
> = ac
.flat_map(move |ea
| br
.clone().flat_map(move |eb
| cr
.clone().map(move |ec
| (ea
, eb
, ec
)))).collect();
406 let mut product_iter
= iproduct
!(a
, b
, c
);
407 let mut actual
= Vec
::new();
409 actual
.extend((&mut product_iter
).take(take_manual
));
410 if actual
.len() == take_manual
{
411 product_iter
.fold((), |(), elt
| actual
.push(elt
));
413 assert_eq
!(answer
, actual
);
416 fn size_multi_product(a
: ShiftRange
) -> bool
{
417 correct_size_hint(a
.multi_cartesian_product())
419 fn correct_multi_product3(a
: ShiftRange
, take_manual
: usize) -> () {
420 // Fix no. of iterators at 3
421 let a
= ShiftRange { iter_count: 3, ..a }
;
423 // test correctness of MultiProduct through regular iteration (take)
425 let mut iters
= a
.clone();
426 let i0
= iters
.next().unwrap();
427 let i1r
= &iters
.next().unwrap();
428 let i2r
= &iters
.next().unwrap();
429 let answer
: Vec
<_
> = i0
.flat_map(move |ei0
| i1r
.clone().flat_map(move |ei1
| i2r
.clone().map(move |ei2
| vec
![ei0
, ei1
, ei2
]))).collect();
430 let mut multi_product
= a
.clone().multi_cartesian_product();
431 let mut actual
= Vec
::new();
433 actual
.extend((&mut multi_product
).take(take_manual
));
434 if actual
.len() == take_manual
{
435 multi_product
.fold((), |(), elt
| actual
.push(elt
));
437 assert_eq
!(answer
, actual
);
439 assert_eq
!(answer
.into_iter().last(), a
.clone().multi_cartesian_product().last());
443 fn size_step(a
: Iter
<i16, Exact
>, s
: usize) -> bool
{
446 s
+= 1; // never zero
448 let filt
= a
.clone().dedup();
449 correct_size_hint(filt
.step(s
)) &&
450 exact_size(a
.step(s
))
454 fn equal_step(a
: Iter
<i16>, s
: usize) -> bool
{
457 s
+= 1; // never zero
460 itertools
::equal(a
.clone().step(s
), a
.filter(|_
| {
461 let keep
= i
% s
== 0;
468 fn equal_step_vec(a
: Vec
<i16>, s
: usize) -> bool
{
471 s
+= 1; // never zero
474 itertools
::equal(a
.iter().step(s
), a
.iter().filter(|_
| {
475 let keep
= i
% s
== 0;
481 fn size_multipeek(a
: Iter
<u16, Exact
>, s
: u8) -> bool
{
482 let mut it
= multipeek(a
);
490 fn equal_merge(a
: Vec
<i16>, b
: Vec
<i16>) -> bool
{
491 let mut sa
= a
.clone();
492 let mut sb
= b
.clone();
495 let mut merged
= sa
.clone();
496 merged
.extend(sb
.iter().cloned());
498 itertools
::equal(&merged
, sa
.iter().merge(&sb
))
500 fn size_merge(a
: Iter
<u16>, b
: Iter
<u16>) -> bool
{
501 correct_size_hint(a
.merge(b
))
503 fn size_zip(a
: Iter
<i16, Exact
>, b
: Iter
<i16, Exact
>, c
: Iter
<i16, Exact
>) -> bool
{
504 let filt
= a
.clone().dedup();
505 correct_size_hint(multizip((filt
, b
.clone(), c
.clone()))) &&
506 exact_size(multizip((a
, b
, c
)))
508 fn size_zip_rc(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
{
509 let rc
= rciter(a
.clone());
510 correct_size_hint(multizip((&rc
, &rc
, b
)))
513 fn size_zip_macro(a
: Iter
<i16, Exact
>, b
: Iter
<i16, Exact
>, c
: Iter
<i16, Exact
>) -> bool
{
514 let filt
= a
.clone().dedup();
515 correct_size_hint(izip
!(filt
, b
.clone(), c
.clone())) &&
516 exact_size(izip
!(a
, b
, c
))
518 fn equal_kmerge(a
: Vec
<i16>, b
: Vec
<i16>, c
: Vec
<i16>) -> bool
{
519 use itertools
::free
::kmerge
;
520 let mut sa
= a
.clone();
521 let mut sb
= b
.clone();
522 let mut sc
= c
.clone();
526 let mut merged
= sa
.clone();
527 merged
.extend(sb
.iter().cloned());
528 merged
.extend(sc
.iter().cloned());
530 itertools
::equal(merged
.into_iter(), kmerge(vec
![sa
, sb
, sc
]))
533 // Any number of input iterators
534 fn equal_kmerge_2(mut inputs
: Vec
<Vec
<i16>>) -> bool
{
535 use itertools
::free
::kmerge
;
537 for input
in &mut inputs
{
540 let mut merged
= inputs
.concat();
542 itertools
::equal(merged
.into_iter(), kmerge(inputs
))
545 // Any number of input iterators
546 fn equal_kmerge_by_ge(mut inputs
: Vec
<Vec
<i16>>) -> bool
{
548 for input
in &mut inputs
{
552 let mut merged
= inputs
.concat();
555 itertools
::equal(merged
.into_iter(),
556 inputs
.into_iter().kmerge_by(|x
, y
| x
>= y
))
559 // Any number of input iterators
560 fn equal_kmerge_by_lt(mut inputs
: Vec
<Vec
<i16>>) -> bool
{
562 for input
in &mut inputs
{
565 let mut merged
= inputs
.concat();
567 itertools
::equal(merged
.into_iter(),
568 inputs
.into_iter().kmerge_by(|x
, y
| x
< y
))
571 // Any number of input iterators
572 fn equal_kmerge_by_le(mut inputs
: Vec
<Vec
<i16>>) -> bool
{
574 for input
in &mut inputs
{
577 let mut merged
= inputs
.concat();
579 itertools
::equal(merged
.into_iter(),
580 inputs
.into_iter().kmerge_by(|x
, y
| x
<= y
))
582 fn size_kmerge(a
: Iter
<i16>, b
: Iter
<i16>, c
: Iter
<i16>) -> bool
{
583 use itertools
::free
::kmerge
;
584 correct_size_hint(kmerge(vec
![a
, b
, c
]))
586 fn equal_zip_eq(a
: Vec
<i32>, b
: Vec
<i32>) -> bool
{
587 let len
= std
::cmp
::min(a
.len(), b
.len());
590 itertools
::equal(zip_eq(a
, b
), zip(a
, b
))
592 fn size_zip_longest(a
: Iter
<i16, Exact
>, b
: Iter
<i16, Exact
>) -> bool
{
593 let filt
= a
.clone().dedup();
594 let filt2
= b
.clone().dedup();
595 correct_size_hint(filt
.zip_longest(b
.clone())) &&
596 correct_size_hint(a
.clone().zip_longest(filt2
)) &&
597 exact_size(a
.zip_longest(b
))
599 fn size_2_zip_longest(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
{
600 let it
= a
.clone().zip_longest(b
.clone());
601 let jt
= a
.clone().zip_longest(b
.clone());
602 itertools
::equal(a
.clone(),
603 it
.filter_map(|elt
| match elt
{
604 EitherOrBoth
::Both(x
, _
) => Some(x
),
605 EitherOrBoth
::Left(x
) => Some(x
),
610 itertools
::equal(b
.clone(),
611 jt
.filter_map(|elt
| match elt
{
612 EitherOrBoth
::Both(_
, y
) => Some(y
),
613 EitherOrBoth
::Right(y
) => Some(y
),
618 fn size_interleave(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
{
619 correct_size_hint(a
.interleave(b
))
621 fn exact_interleave(a
: Iter
<i16, Exact
>, b
: Iter
<i16, Exact
>) -> bool
{
622 exact_size_for_this(a
.interleave(b
))
624 fn size_interleave_shortest(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
{
625 correct_size_hint(a
.interleave_shortest(b
))
627 fn exact_interleave_shortest(a
: Vec
<()>, b
: Vec
<()>) -> bool
{
628 exact_size_for_this(a
.iter().interleave_shortest(&b
))
630 fn size_intersperse(a
: Iter
<i16>, x
: i16) -> bool
{
631 correct_size_hint(a
.intersperse(x
))
633 fn equal_intersperse(a
: Vec
<i32>, x
: i32) -> bool
{
634 let mut inter
= false;
636 for elt
in a
.iter().cloned().intersperse(x
) {
638 if elt
!= x { return false }
640 if elt
!= a
[i
] { return false }
648 fn equal_combinations_2(a
: Vec
<u8>) -> bool
{
649 let mut v
= Vec
::new();
650 for (i
, x
) in enumerate(&a
) {
651 for y
in &a
[i
+ 1..] {
655 itertools
::equal(a
.iter().tuple_combinations
::<(_
, _
)>(), v
)
658 fn collect_tuple_matches_size(a
: Iter
<i16>) -> bool
{
659 let size
= a
.clone().count();
660 a
.collect_tuple
::<(_
, _
, _
)>().is_some() == (size
== 3)
663 fn correct_permutations(vals
: HashSet
<i32>, k
: usize) -> () {
664 // Test permutations only on iterators of distinct integers, to prevent
667 const MAX_N
: usize = 5;
669 let n
= min(vals
.len(), MAX_N
);
670 let vals
: HashSet
<i32> = vals
.into_iter().take(n
).collect();
672 let perms
= vals
.iter().permutations(k
);
674 let mut actual
= HashSet
::new();
677 assert_eq
!(perm
.len(), k
);
679 let all_items_valid
= perm
.iter().all(|p
| vals
.contains(p
));
680 assert
!(all_items_valid
, "perm contains value not from input: {:?}", perm
);
682 // Check that all perm items are distinct
684 let perm_set
: HashSet
<_
> = perm
.iter().collect();
687 assert_eq
!(perm
.len(), distinct_len
);
689 // Check that the perm is new
690 assert
!(actual
.insert(perm
.clone()), "perm already encountered: {:?}", perm
);
694 fn permutations_lexic_order(a
: usize, b
: usize) -> () {
701 let expected_first
: Vec
<usize> = (0..k
).collect();
702 let expected_last
: Vec
<usize> = ((n
- k
)..n
).rev().collect();
704 let mut perms
= (0..n
).permutations(k
);
706 let mut curr_perm
= match perms
.next() {
711 assert_eq
!(expected_first
, curr_perm
);
713 while let Some(next_perm
) = perms
.next() {
715 next_perm
> curr_perm
,
716 "next perm isn't greater-than current; next_perm={:?} curr_perm={:?} n={}",
717 next_perm
, curr_perm
, n
720 curr_perm
= next_perm
;
723 assert_eq
!(expected_last
, curr_perm
);
727 fn permutations_count(n
: usize, k
: usize) -> bool
{
730 correct_count(|| (0..n
).permutations(k
))
733 fn permutations_size(a
: Iter
<i32>, k
: usize) -> bool
{
734 correct_size_hint(a
.take(5).permutations(k
))
737 fn permutations_k0_yields_once(n
: usize) -> () {
739 let expected
: Vec
<Vec
<usize>> = vec
![vec
![]];
740 let actual
= (0..n
).permutations(k
).collect_vec();
742 assert_eq
!(expected
, actual
);
747 fn equal_dedup(a
: Vec
<i32>) -> bool
{
748 let mut b
= a
.clone();
750 itertools
::equal(&b
, a
.iter().dedup())
755 fn equal_dedup_by(a
: Vec
<(i32, i32)>) -> bool
{
756 let mut b
= a
.clone();
757 b
.dedup_by(|x
, y
| x
.0==y
.0);
758 itertools
::equal(&b
, a
.iter().dedup_by(|x
, y
| x
.0==y
.0))
763 fn size_dedup(a
: Vec
<i32>) -> bool
{
764 correct_size_hint(a
.iter().dedup())
769 fn size_dedup_by(a
: Vec
<(i32, i32)>) -> bool
{
770 correct_size_hint(a
.iter().dedup_by(|x
, y
| x
.0==y
.0))
775 fn exact_repeatn((n
, x
): (usize, i32)) -> bool
{
776 let it
= itertools
::repeat_n(x
, n
);
782 fn size_put_back(a
: Vec
<u8>, x
: Option
<u8>) -> bool
{
783 let mut it
= put_back(a
.into_iter());
785 Some(t
) => it
.put_back(t
),
788 correct_size_hint(it
)
793 fn size_put_backn(a
: Vec
<u8>, b
: Vec
<u8>) -> bool
{
794 let mut it
= put_back_n(a
.into_iter());
798 correct_size_hint(it
)
803 fn size_tee(a
: Vec
<u8>) -> bool
{
804 let (mut t1
, mut t2
) = a
.iter().tee();
808 exact_size(t1
) && exact_size(t2
)
813 fn size_tee_2(a
: Vec
<u8>) -> bool
{
814 let (mut t1
, mut t2
) = a
.iter().dedup().tee();
818 correct_size_hint(t1
) && correct_size_hint(t2
)
823 fn size_take_while_ref(a
: Vec
<u8>, stop
: u8) -> bool
{
824 correct_size_hint(a
.iter().take_while_ref(|x
| **x
!= stop
))
829 fn equal_partition(a
: Vec
<i32>) -> bool
{
831 let mut ap
= a
.clone();
832 let split_index
= itertools
::partition(&mut ap
, |x
| *x
>= 0);
833 let parted
= (0..split_index
).all(|i
| ap
[i
] >= 0) &&
834 (split_index
..a
.len()).all(|i
| ap
[i
] < 0);
843 fn size_combinations(it
: Iter
<i16>) -> bool
{
844 correct_size_hint(it
.tuple_combinations
::<(_
, _
)>())
849 fn equal_combinations(it
: Iter
<i16>) -> bool
{
850 let values
= it
.clone().collect_vec();
851 let mut cmb
= it
.tuple_combinations();
852 for i
in 0..values
.len() {
853 for j
in i
+1..values
.len() {
854 let pair
= (values
[i
], values
[j
]);
855 if pair
!= cmb
.next().unwrap() {
865 fn size_pad_tail(it
: Iter
<i8>, pad
: u8) -> bool
{
866 correct_size_hint(it
.clone().pad_using(pad
as usize, |_
| 0)) &&
867 correct_size_hint(it
.dropping(1).rev().pad_using(pad
as usize, |_
| 0))
872 fn size_pad_tail2(it
: Iter
<i8, Exact
>, pad
: u8) -> bool
{
873 exact_size(it
.pad_using(pad
as usize, |_
| 0))
878 fn size_unique(it
: Iter
<i8>) -> bool
{
879 correct_size_hint(it
.unique())
882 fn count_unique(it
: Vec
<i8>, take_first
: u8) -> () {
884 let mut v
= it
.clone();
888 let mut iter
= cloned(&it
).unique();
889 let first_count
= (&mut iter
).take(take_first
as usize).count();
890 let rest_count
= iter
.count();
891 assert_eq
!(answer
, first_count
+ rest_count
);
896 fn fuzz_group_by_lazy_1(it
: Iter
<u8>) -> bool
{
898 let groups
= it
.group_by(|k
| *k
);
899 let res
= itertools
::equal(jt
, groups
.into_iter().flat_map(|(_
, x
)| x
));
905 fn fuzz_group_by_lazy_2(data
: Vec
<u8>) -> bool
{
906 let groups
= data
.iter().group_by(|k
| *k
/ 10);
907 let res
= itertools
::equal(data
.iter(), groups
.into_iter().flat_map(|(_
, x
)| x
));
913 fn fuzz_group_by_lazy_3(data
: Vec
<u8>) -> bool
{
914 let grouper
= data
.iter().group_by(|k
| *k
/ 10);
915 let groups
= grouper
.into_iter().collect_vec();
916 let res
= itertools
::equal(data
.iter(), groups
.into_iter().flat_map(|(_
, x
)| x
));
922 fn fuzz_group_by_lazy_duo(data
: Vec
<u8>, order
: Vec
<(bool
, bool
)>) -> bool
{
923 let grouper
= data
.iter().group_by(|k
| *k
/ 3);
924 let mut groups1
= grouper
.into_iter();
925 let mut groups2
= grouper
.into_iter();
926 let mut elts
= Vec
::<&u8>::new();
927 let mut old_groups
= Vec
::new();
929 let tup1
= |(_
, b
)| b
;
930 for &(ord
, consume_now
) in &order
{
931 let iter
= &mut [&mut groups1
, &mut groups2
][ord
as usize];
933 Some((_
, gr
)) => if consume_now
{
934 for og
in old_groups
.drain(..) {
944 for og
in old_groups
.drain(..) {
947 for gr
in groups1
.map(&tup1
) { elts.extend(gr); }
948 for gr
in groups2
.map(&tup1
) { elts.extend(gr); }
949 itertools
::assert_equal(&data
, elts
);
955 fn equal_chunks_lazy(a
: Vec
<u8>, size
: u8) -> bool
{
960 let chunks
= a
.iter().chunks(size
as usize);
961 let it
= a
.chunks(size
as usize);
962 for (a
, b
) in chunks
.into_iter().zip(it
) {
963 if !itertools
::equal(a
, b
) {
972 fn equal_tuple_windows_1(a
: Vec
<u8>) -> bool
{
973 let x
= a
.windows(1).map(|s
| (&s
[0], ));
974 let y
= a
.iter().tuple_windows
::<(_
,)>();
975 itertools
::equal(x
, y
)
978 fn equal_tuple_windows_2(a
: Vec
<u8>) -> bool
{
979 let x
= a
.windows(2).map(|s
| (&s
[0], &s
[1]));
980 let y
= a
.iter().tuple_windows
::<(_
, _
)>();
981 itertools
::equal(x
, y
)
984 fn equal_tuple_windows_3(a
: Vec
<u8>) -> bool
{
985 let x
= a
.windows(3).map(|s
| (&s
[0], &s
[1], &s
[2]));
986 let y
= a
.iter().tuple_windows
::<(_
, _
, _
)>();
987 itertools
::equal(x
, y
)
990 fn equal_tuple_windows_4(a
: Vec
<u8>) -> bool
{
991 let x
= a
.windows(4).map(|s
| (&s
[0], &s
[1], &s
[2], &s
[3]));
992 let y
= a
.iter().tuple_windows
::<(_
, _
, _
, _
)>();
993 itertools
::equal(x
, y
)
996 fn equal_tuples_1(a
: Vec
<u8>) -> bool
{
997 let x
= a
.chunks(1).map(|s
| (&s
[0], ));
998 let y
= a
.iter().tuples
::<(_
,)>();
999 itertools
::equal(x
, y
)
1002 fn equal_tuples_2(a
: Vec
<u8>) -> bool
{
1003 let x
= a
.chunks(2).filter(|s
| s
.len() == 2).map(|s
| (&s
[0], &s
[1]));
1004 let y
= a
.iter().tuples
::<(_
, _
)>();
1005 itertools
::equal(x
, y
)
1008 fn equal_tuples_3(a
: Vec
<u8>) -> bool
{
1009 let x
= a
.chunks(3).filter(|s
| s
.len() == 3).map(|s
| (&s
[0], &s
[1], &s
[2]));
1010 let y
= a
.iter().tuples
::<(_
, _
, _
)>();
1011 itertools
::equal(x
, y
)
1014 fn equal_tuples_4(a
: Vec
<u8>) -> bool
{
1015 let x
= a
.chunks(4).filter(|s
| s
.len() == 4).map(|s
| (&s
[0], &s
[1], &s
[2], &s
[3]));
1016 let y
= a
.iter().tuples
::<(_
, _
, _
, _
)>();
1017 itertools
::equal(x
, y
)
1020 fn exact_tuple_buffer(a
: Vec
<u8>) -> bool
{
1021 let mut iter
= a
.iter().tuples
::<(_
, _
, _
, _
)>();
1023 let buffer
= iter
.into_buffer();
1024 assert_eq
!(buffer
.len(), a
.len() % 4);
1031 fn with_position_exact_size_1(a
: Vec
<u8>) -> bool
{
1032 exact_size_for_this(a
.iter().with_position())
1034 fn with_position_exact_size_2(a
: Iter
<u8, Exact
>) -> bool
{
1035 exact_size_for_this(a
.with_position())
1040 fn correct_group_map_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1041 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1042 let count
= a
.len();
1043 let lookup
= a
.into_iter().map(|i
| (i
% modulo
, i
)).into_group_map();
1045 assert_eq
!(lookup
.values().flat_map(|vals
| vals
.iter()).count(), count
);
1047 for (&key
, vals
) in lookup
.iter() {
1048 assert
!(vals
.iter().all(|&val
| val
% modulo
== key
));
1053 /// A peculiar type: Equality compares both tuple items, but ordering only the
1054 /// first item. This is so we can check the stability property easily.
1055 #[derive(Clone, Debug, PartialEq, Eq)]
1056 struct Val(u32, u32);
1058 impl PartialOrd
<Val
> for Val
{
1059 fn partial_cmp(&self, other
: &Val
) -> Option
<Ordering
> {
1060 self.0.partial_cmp(&other
.0)
1065 fn cmp(&self, other
: &Val
) -> Ordering
{
1066 self.0.cmp(&other
.0)
1070 impl qc
::Arbitrary
for Val
{
1071 fn arbitrary
<G
: qc
::Gen
>(g
: &mut G
) -> Self {
1072 let (x
, y
) = <(u32, u32)>::arbitrary(g
);
1075 fn shrink(&self) -> Box
<dyn Iterator
<Item
= Self>> {
1076 Box
::new((self.0, self.1).shrink().map(|(x
, y
)| Val(x
, y
)))
1081 fn minmax(a
: Vec
<Val
>) -> bool
{
1082 use itertools
::MinMaxResult
;
1085 let minmax
= a
.iter().minmax();
1086 let expected
= match a
.len() {
1087 0 => MinMaxResult
::NoElements
,
1088 1 => MinMaxResult
::OneElement(&a
[0]),
1089 _
=> MinMaxResult
::MinMax(a
.iter().min().unwrap(),
1090 a
.iter().max().unwrap()),
1097 fn minmax_f64(a
: Vec
<f64>) -> TestResult
{
1098 use itertools
::MinMaxResult
;
1100 if a
.iter().any(|x
| x
.is_nan()) {
1101 return TestResult
::discard();
1104 let min
= cloned(&a
).fold1(f64::min
);
1105 let max
= cloned(&a
).fold1(f64::max
);
1107 let minmax
= cloned(&a
).minmax();
1108 let expected
= match a
.len() {
1109 0 => MinMaxResult
::NoElements
,
1110 1 => MinMaxResult
::OneElement(min
.unwrap()),
1111 _
=> MinMaxResult
::MinMax(min
.unwrap(), max
.unwrap()),
1113 TestResult
::from_bool(minmax
== expected
)
1118 #[allow(deprecated)]
1119 fn tree_fold1_f64(mut a
: Vec
<f64>) -> TestResult
{
1120 fn collapse_adjacent
<F
>(x
: Vec
<f64>, mut f
: F
) -> Vec
<f64>
1121 where F
: FnMut(f64, f64) -> f64
1123 let mut out
= Vec
::new();
1124 for i
in (0..x
.len()).step(2) {
1128 out
.push(f(x
[i
], x
[i
+1]));
1134 if a
.iter().any(|x
| x
.is_nan()) {
1135 return TestResult
::discard();
1138 let actual
= a
.iter().cloned().tree_fold1(f64::atan2
);
1141 a
= collapse_adjacent(a
, f64::atan2
);
1143 let expected
= a
.pop();
1145 TestResult
::from_bool(actual
== expected
)
1150 fn exactly_one_i32(a
: Vec
<i32>) -> TestResult
{
1151 let ret
= a
.iter().cloned().exactly_one();
1153 1 => TestResult
::from_bool(ret
.unwrap() == a
[0]),
1154 _
=> TestResult
::from_bool(ret
.unwrap_err().eq(a
.iter().cloned())),