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.
6 #[macro_use] extern crate itertools;
8 extern crate quickcheck
;
11 use std
::default::Default
;
15 use std
::cmp
::{max, min, Ordering}
;
16 use std
::collections
::HashSet
;
17 use itertools
::Itertools
;
22 use itertools
::free
::{
34 use rand
::seq
::SliceRandom
;
35 use quickcheck
::TestResult
;
37 /// Trait for size hint modifier types
38 trait HintKind
: Copy
+ Send
+ qc
::Arbitrary
{
39 fn loosen_bounds(&self, org_hint
: (usize, Option
<usize>)) -> (usize, Option
<usize>);
42 /// Exact size hint variant that leaves hints unchanged
43 #[derive(Clone, Copy, Debug)]
46 impl HintKind
for Exact
{
47 fn loosen_bounds(&self, org_hint
: (usize, Option
<usize>)) -> (usize, Option
<usize>) {
52 impl qc
::Arbitrary
for Exact
{
53 fn arbitrary
<G
: qc
::Gen
>(_
: &mut G
) -> Self {
58 /// Inexact size hint variant to simulate imprecise (but valid) size hints
60 /// Will always decrease the lower bound and increase the upper bound
61 /// of the size hint by set amounts.
62 #[derive(Clone, Copy, Debug)]
68 impl HintKind
for Inexact
{
69 fn loosen_bounds(&self, org_hint
: (usize, Option
<usize>)) -> (usize, Option
<usize>) {
70 let (org_lower
, org_upper
) = org_hint
;
71 (org_lower
.saturating_sub(self.underestimate
),
72 org_upper
.and_then(move |x
| x
.checked_add(self.overestimate
)))
76 impl qc
::Arbitrary
for Inexact
{
77 fn arbitrary
<G
: qc
::Gen
>(g
: &mut G
) -> Self {
78 let ue_value
= usize::arbitrary(g
);
79 let oe_value
= usize::arbitrary(g
);
80 // Compensate for quickcheck using extreme values too rarely
81 let ue_choices
= &[0, ue_value
, usize::max_value()];
82 let oe_choices
= &[0, oe_value
, usize::max_value()];
84 underestimate
: *ue_choices
.choose(g
).unwrap(),
85 overestimate
: *oe_choices
.choose(g
).unwrap(),
89 fn shrink(&self) -> Box
<Iterator
<Item
=Self>> {
90 let underestimate_value
= self.underestimate
;
91 let overestimate_value
= self.overestimate
;
93 underestimate_value
.shrink().flat_map(move |ue_value
|
94 overestimate_value
.shrink().map(move |oe_value
|
96 underestimate
: ue_value
,
97 overestimate
: oe_value
,
105 /// Our base iterator that we can impl Arbitrary for
107 /// By default we'll return inexact bounds estimates for size_hint
108 /// to make tests harder to pass.
110 /// NOTE: Iter is tricky and is not fused, to help catch bugs.
111 /// At the end it will return None once, then return Some(0),
112 /// then return None again.
113 #[derive(Clone, Debug)]
114 struct Iter
<T
, SK
: HintKind
= Inexact
> {
121 impl<T
, HK
> Iter
<T
, HK
> where HK
: HintKind
123 fn new(it
: Range
<T
>, hint_kind
: HK
) -> Self {
132 impl<T
, HK
> Iterator
for Iter
<T
, HK
>
133 where Range
<T
>: Iterator
,
134 <Range
<T
> as Iterator
>::Item
: Default
,
137 type Item
= <Range
<T
> as Iterator
>::Item
;
139 fn next(&mut self) -> Option
<Self::Item
>
141 let elt
= self.iterator
.next();
145 if self.fuse_flag
== 2 {
146 return Some(Default
::default())
152 fn size_hint(&self) -> (usize, Option
<usize>)
154 let org_hint
= self.iterator
.size_hint();
155 self.hint_kind
.loosen_bounds(org_hint
)
159 impl<T
, HK
> DoubleEndedIterator
for Iter
<T
, HK
>
160 where Range
<T
>: DoubleEndedIterator
,
161 <Range
<T
> as Iterator
>::Item
: Default
,
164 fn next_back(&mut self) -> Option
<Self::Item
> { self.iterator.next_back() }
167 impl<T
> ExactSizeIterator
for Iter
<T
, Exact
> where Range
<T
>: ExactSizeIterator
,
168 <Range
<T
> as Iterator
>::Item
: Default
,
171 impl<T
, HK
> qc
::Arbitrary
for Iter
<T
, HK
>
172 where T
: qc
::Arbitrary
,
175 fn arbitrary
<G
: qc
::Gen
>(g
: &mut G
) -> Self
177 Iter
::new(T
::arbitrary(g
)..T
::arbitrary(g
), HK
::arbitrary(g
))
180 fn shrink(&self) -> Box
<Iterator
<Item
=Iter
<T
, HK
>>>
182 let r
= self.iterator
.clone();
183 let hint_kind
= self.hint_kind
;
185 r
.start
.shrink().flat_map(move |a
|
186 r
.end
.shrink().map(move |b
|
187 Iter
::new(a
.clone()..b
, hint_kind
)
194 /// A meta-iterator which yields `Iter<i32>`s whose start/endpoints are
195 /// increased or decreased linearly on each iteration.
196 #[derive(Clone, Debug)]
197 struct ShiftRange
<HK
= Inexact
> {
206 impl<HK
> Iterator
for ShiftRange
<HK
> where HK
: HintKind
{
207 type Item
= Iter
<i32, HK
>;
209 fn next(&mut self) -> Option
<Self::Item
> {
210 if self.iter_count
== 0 {
214 let iter
= Iter
::new(self.range_start
..self.range_end
, self.hint_kind
);
216 self.range_start
+= self.start_step
;
217 self.range_end
+= self.end_step
;
218 self.iter_count
-= 1;
224 impl ExactSizeIterator
for ShiftRange
<Exact
> { }
226 impl<HK
> qc
::Arbitrary
for ShiftRange
<HK
>
229 fn arbitrary
<G
: qc
::Gen
>(g
: &mut G
) -> Self {
230 const MAX_STARTING_RANGE_DIFF
: i32 = 32;
231 const MAX_STEP_MODULO
: i32 = 8;
232 const MAX_ITER_COUNT
: u32 = 3;
234 let range_start
= qc
::Arbitrary
::arbitrary(g
);
235 let range_end
= range_start
+ g
.gen_range(0, MAX_STARTING_RANGE_DIFF
+ 1);
236 let start_step
= g
.gen_range(-MAX_STEP_MODULO
, MAX_STEP_MODULO
+ 1);
237 let end_step
= g
.gen_range(-MAX_STEP_MODULO
, MAX_STEP_MODULO
+ 1);
238 let iter_count
= g
.gen_range(0, MAX_ITER_COUNT
+ 1);
239 let hint_kind
= qc
::Arbitrary
::arbitrary(g
);
242 range_start
: range_start
,
243 range_end
: range_end
,
244 start_step
: start_step
,
246 iter_count
: iter_count
,
252 fn correct_count
<I
, F
>(get_it
: F
) -> bool
257 let mut counts
= vec
![get_it().count()];
260 let mut it
= get_it();
262 for _
in 0..(counts
.len() - 1) {
263 if let None
= it
.next() {
264 panic
!("Iterator shouldn't be finished, may not be deterministic");
268 if let None
= it
.next() {
272 counts
.push(it
.count());
275 let total_actual_count
= counts
.len() - 1;
277 for (i
, returned_count
) in counts
.into_iter().enumerate() {
278 let actual_count
= total_actual_count
- i
;
279 if actual_count
!= returned_count
{
280 println
!("Total iterations: {} True count: {} returned count: {}", i
, actual_count
, returned_count
);
289 fn correct_size_hint
<I
: Iterator
>(mut it
: I
) -> bool
{
290 // record size hint at each iteration
291 let initial_hint
= it
.size_hint();
292 let mut hints
= Vec
::with_capacity(initial_hint
.0 + 1);
293 hints
.push(initial_hint
);
294 while let Some(_
) = it
.next() {
295 hints
.push(it
.size_hint())
298 let mut true_count
= hints
.len(); // start off +1 too much
300 // check all the size hints
301 for &(low
, hi
) in &hints
{
303 if low
> true_count
||
304 (hi
.is_some() && hi
.unwrap() < true_count
)
306 println
!("True size: {:?}, size hint: {:?}", true_count
, (low
, hi
));
307 //println!("All hints: {:?}", hints);
314 fn exact_size
<I
: ExactSizeIterator
>(mut it
: I
) -> bool
{
315 // check every iteration
316 let (mut low
, mut hi
) = it
.size_hint();
317 if Some(low
) != hi { return false; }
318 while let Some(_
) = it
.next() {
319 let (xlow
, xhi
) = it
.size_hint();
320 if low
!= xlow
+ 1 { return false; }
323 if Some(low
) != hi { return false; }
325 let (low
, hi
) = it
.size_hint();
326 low
== 0 && hi
== Some(0)
329 // Exact size for this case, without ExactSizeIterator
330 fn exact_size_for_this
<I
: Iterator
>(mut it
: I
) -> bool
{
331 // check every iteration
332 let (mut low
, mut hi
) = it
.size_hint();
333 if Some(low
) != hi { return false; }
334 while let Some(_
) = it
.next() {
335 let (xlow
, xhi
) = it
.size_hint();
336 if low
!= xlow
+ 1 { return false; }
339 if Some(low
) != hi { return false; }
341 let (low
, hi
) = it
.size_hint();
342 low
== 0 && hi
== Some(0)
346 * NOTE: Range<i8> is broken!
347 * (all signed ranges are)
349 fn size_range_i8(a: Iter<i8>) -> bool {
354 fn size_range_i16(a: Iter<i16>) -> bool {
359 fn size_range_u8(a: Iter<u8>) -> bool {
364 macro_rules
! quickcheck
{
365 // accept several property function definitions
366 // The property functions can use pattern matching and `mut` as usual
367 // in the function arguments, but the functions can not be generic.
368 {$($(#$attr:tt)* fn $fn_name:ident($($arg:tt)*) -> $ret:ty { $($code:tt)* }
)*} => (
373 fn prop($
($arg
)*) -> $ret
{
376 ::quickcheck
::quickcheck(quickcheck
!(@
fn prop
[] $
($arg
)*));
380 // parse argument list (with patterns allowed) into prop as fn(_, _) -> _
381 (@
fn $f
:ident
[$
($t
:tt
)*]) => {
382 $f
as fn($
($t
),*) -> _
384 (@
fn $f
:ident
[$
($p
:tt
)*] : $
($tail
:tt
)*) => {
385 quickcheck
!(@
fn $f
[$
($p
)* _
] $
($tail
)*)
387 (@
fn $f
:ident
[$
($p
:tt
)*] $t
:tt $
($tail
:tt
)*) => {
388 quickcheck
!(@
fn $f
[$
($p
)*] $
($tail
)*)
394 fn size_product(a
: Iter
<u16>, b
: Iter
<u16>) -> bool
{
395 correct_size_hint(a
.cartesian_product(b
))
397 fn size_product3(a
: Iter
<u16>, b
: Iter
<u16>, c
: Iter
<u16>) -> bool
{
398 correct_size_hint(iproduct
!(a
, b
, c
))
401 fn correct_cartesian_product3(a
: Iter
<u16>, b
: Iter
<u16>, c
: Iter
<u16>,
402 take_manual
: usize) -> ()
404 // test correctness of iproduct through regular iteration (take)
409 let answer
: Vec
<_
> = ac
.flat_map(move |ea
| br
.clone().flat_map(move |eb
| cr
.clone().map(move |ec
| (ea
, eb
, ec
)))).collect();
410 let mut product_iter
= iproduct
!(a
, b
, c
);
411 let mut actual
= Vec
::new();
413 actual
.extend((&mut product_iter
).take(take_manual
));
414 if actual
.len() == take_manual
{
415 product_iter
.fold((), |(), elt
| actual
.push(elt
));
417 assert_eq
!(answer
, actual
);
420 fn size_multi_product(a
: ShiftRange
) -> bool
{
421 correct_size_hint(a
.multi_cartesian_product())
423 fn correct_multi_product3(a
: ShiftRange
, take_manual
: usize) -> () {
424 // Fix no. of iterators at 3
425 let a
= ShiftRange { iter_count: 3, ..a }
;
427 // test correctness of MultiProduct through regular iteration (take)
429 let mut iters
= a
.clone();
430 let i0
= iters
.next().unwrap();
431 let i1r
= &iters
.next().unwrap();
432 let i2r
= &iters
.next().unwrap();
433 let answer
: Vec
<_
> = i0
.flat_map(move |ei0
| i1r
.clone().flat_map(move |ei1
| i2r
.clone().map(move |ei2
| vec
![ei0
, ei1
, ei2
]))).collect();
434 let mut multi_product
= a
.clone().multi_cartesian_product();
435 let mut actual
= Vec
::new();
437 actual
.extend((&mut multi_product
).take(take_manual
));
438 if actual
.len() == take_manual
{
439 multi_product
.fold((), |(), elt
| actual
.push(elt
));
441 assert_eq
!(answer
, actual
);
443 assert_eq
!(answer
.into_iter().last(), a
.clone().multi_cartesian_product().last());
447 fn size_step(a
: Iter
<i16, Exact
>, s
: usize) -> bool
{
450 s
+= 1; // never zero
452 let filt
= a
.clone().dedup();
453 correct_size_hint(filt
.step(s
)) &&
454 exact_size(a
.step(s
))
458 fn equal_step(a
: Iter
<i16>, s
: usize) -> bool
{
461 s
+= 1; // never zero
464 itertools
::equal(a
.clone().step(s
), a
.filter(|_
| {
465 let keep
= i
% s
== 0;
472 fn equal_step_vec(a
: Vec
<i16>, s
: usize) -> bool
{
475 s
+= 1; // never zero
478 itertools
::equal(a
.iter().step(s
), a
.iter().filter(|_
| {
479 let keep
= i
% s
== 0;
485 fn size_multipeek(a
: Iter
<u16, Exact
>, s
: u8) -> bool
{
486 let mut it
= multipeek(a
);
494 fn equal_merge(a
: Vec
<i16>, b
: Vec
<i16>) -> bool
{
495 let mut sa
= a
.clone();
496 let mut sb
= b
.clone();
499 let mut merged
= sa
.clone();
500 merged
.extend(sb
.iter().cloned());
502 itertools
::equal(&merged
, sa
.iter().merge(&sb
))
504 fn size_merge(a
: Iter
<u16>, b
: Iter
<u16>) -> bool
{
505 correct_size_hint(a
.merge(b
))
507 fn size_zip(a
: Iter
<i16, Exact
>, b
: Iter
<i16, Exact
>, c
: Iter
<i16, Exact
>) -> bool
{
508 let filt
= a
.clone().dedup();
509 correct_size_hint(multizip((filt
, b
.clone(), c
.clone()))) &&
510 exact_size(multizip((a
, b
, c
)))
512 fn size_zip_rc(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
{
513 let rc
= rciter(a
.clone());
514 correct_size_hint(multizip((&rc
, &rc
, b
)))
517 fn size_zip_macro(a
: Iter
<i16, Exact
>, b
: Iter
<i16, Exact
>, c
: Iter
<i16, Exact
>) -> bool
{
518 let filt
= a
.clone().dedup();
519 correct_size_hint(izip
!(filt
, b
.clone(), c
.clone())) &&
520 exact_size(izip
!(a
, b
, c
))
522 fn equal_kmerge(a
: Vec
<i16>, b
: Vec
<i16>, c
: Vec
<i16>) -> bool
{
523 use itertools
::free
::kmerge
;
524 let mut sa
= a
.clone();
525 let mut sb
= b
.clone();
526 let mut sc
= c
.clone();
530 let mut merged
= sa
.clone();
531 merged
.extend(sb
.iter().cloned());
532 merged
.extend(sc
.iter().cloned());
534 itertools
::equal(merged
.into_iter(), kmerge(vec
![sa
, sb
, sc
]))
537 // Any number of input iterators
538 fn equal_kmerge_2(mut inputs
: Vec
<Vec
<i16>>) -> bool
{
539 use itertools
::free
::kmerge
;
541 for input
in &mut inputs
{
544 let mut merged
= inputs
.concat();
546 itertools
::equal(merged
.into_iter(), kmerge(inputs
))
549 // Any number of input iterators
550 fn equal_kmerge_by_ge(mut inputs
: Vec
<Vec
<i16>>) -> bool
{
552 for input
in &mut inputs
{
556 let mut merged
= inputs
.concat();
559 itertools
::equal(merged
.into_iter(),
560 inputs
.into_iter().kmerge_by(|x
, y
| x
>= y
))
563 // Any number of input iterators
564 fn equal_kmerge_by_lt(mut inputs
: Vec
<Vec
<i16>>) -> bool
{
566 for input
in &mut inputs
{
569 let mut merged
= inputs
.concat();
571 itertools
::equal(merged
.into_iter(),
572 inputs
.into_iter().kmerge_by(|x
, y
| x
< y
))
575 // Any number of input iterators
576 fn equal_kmerge_by_le(mut inputs
: Vec
<Vec
<i16>>) -> bool
{
578 for input
in &mut inputs
{
581 let mut merged
= inputs
.concat();
583 itertools
::equal(merged
.into_iter(),
584 inputs
.into_iter().kmerge_by(|x
, y
| x
<= y
))
586 fn size_kmerge(a
: Iter
<i16>, b
: Iter
<i16>, c
: Iter
<i16>) -> bool
{
587 use itertools
::free
::kmerge
;
588 correct_size_hint(kmerge(vec
![a
, b
, c
]))
590 fn equal_zip_eq(a
: Vec
<i32>, b
: Vec
<i32>) -> bool
{
591 let len
= std
::cmp
::min(a
.len(), b
.len());
594 itertools
::equal(zip_eq(a
, b
), zip(a
, b
))
596 fn size_zip_longest(a
: Iter
<i16, Exact
>, b
: Iter
<i16, Exact
>) -> bool
{
597 let filt
= a
.clone().dedup();
598 let filt2
= b
.clone().dedup();
599 correct_size_hint(filt
.zip_longest(b
.clone())) &&
600 correct_size_hint(a
.clone().zip_longest(filt2
)) &&
601 exact_size(a
.zip_longest(b
))
603 fn size_2_zip_longest(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
{
604 let it
= a
.clone().zip_longest(b
.clone());
605 let jt
= a
.clone().zip_longest(b
.clone());
606 itertools
::equal(a
.clone(),
607 it
.filter_map(|elt
| match elt
{
608 EitherOrBoth
::Both(x
, _
) => Some(x
),
609 EitherOrBoth
::Left(x
) => Some(x
),
614 itertools
::equal(b
.clone(),
615 jt
.filter_map(|elt
| match elt
{
616 EitherOrBoth
::Both(_
, y
) => Some(y
),
617 EitherOrBoth
::Right(y
) => Some(y
),
622 fn size_interleave(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
{
623 correct_size_hint(a
.interleave(b
))
625 fn exact_interleave(a
: Iter
<i16, Exact
>, b
: Iter
<i16, Exact
>) -> bool
{
626 exact_size_for_this(a
.interleave(b
))
628 fn size_interleave_shortest(a
: Iter
<i16>, b
: Iter
<i16>) -> bool
{
629 correct_size_hint(a
.interleave_shortest(b
))
631 fn exact_interleave_shortest(a
: Vec
<()>, b
: Vec
<()>) -> bool
{
632 exact_size_for_this(a
.iter().interleave_shortest(&b
))
634 fn size_intersperse(a
: Iter
<i16>, x
: i16) -> bool
{
635 correct_size_hint(a
.intersperse(x
))
637 fn equal_intersperse(a
: Vec
<i32>, x
: i32) -> bool
{
638 let mut inter
= false;
640 for elt
in a
.iter().cloned().intersperse(x
) {
642 if elt
!= x { return false }
644 if elt
!= a
[i
] { return false }
652 fn equal_combinations_2(a
: Vec
<u8>) -> bool
{
653 let mut v
= Vec
::new();
654 for (i
, x
) in enumerate(&a
) {
655 for y
in &a
[i
+ 1..] {
659 itertools
::equal(a
.iter().tuple_combinations
::<(_
, _
)>(), v
)
662 fn collect_tuple_matches_size(a
: Iter
<i16>) -> bool
{
663 let size
= a
.clone().count();
664 a
.collect_tuple
::<(_
, _
, _
)>().is_some() == (size
== 3)
667 fn correct_permutations(vals
: HashSet
<i32>, k
: usize) -> () {
668 // Test permutations only on iterators of distinct integers, to prevent
671 const MAX_N
: usize = 5;
673 let n
= min(vals
.len(), MAX_N
);
674 let vals
: HashSet
<i32> = vals
.into_iter().take(n
).collect();
676 let perms
= vals
.iter().permutations(k
);
678 let mut actual
= HashSet
::new();
681 assert_eq
!(perm
.len(), k
);
683 let all_items_valid
= perm
.iter().all(|p
| vals
.contains(p
));
684 assert
!(all_items_valid
, "perm contains value not from input: {:?}", perm
);
686 // Check that all perm items are distinct
688 let perm_set
: HashSet
<_
> = perm
.iter().collect();
691 assert_eq
!(perm
.len(), distinct_len
);
693 // Check that the perm is new
694 assert
!(actual
.insert(perm
.clone()), "perm already encountered: {:?}", perm
);
698 fn permutations_lexic_order(a
: usize, b
: usize) -> () {
705 let expected_first
: Vec
<usize> = (0..k
).collect();
706 let expected_last
: Vec
<usize> = ((n
- k
)..n
).rev().collect();
708 let mut perms
= (0..n
).permutations(k
);
710 let mut curr_perm
= match perms
.next() {
715 assert_eq
!(expected_first
, curr_perm
);
717 while let Some(next_perm
) = perms
.next() {
719 next_perm
> curr_perm
,
720 "next perm isn't greater-than current; next_perm={:?} curr_perm={:?} n={}",
721 next_perm
, curr_perm
, n
724 curr_perm
= next_perm
;
727 assert_eq
!(expected_last
, curr_perm
);
731 fn permutations_count(n
: usize, k
: usize) -> bool
{
734 correct_count(|| (0..n
).permutations(k
))
737 fn permutations_size(a
: Iter
<i32>, k
: usize) -> bool
{
738 correct_size_hint(a
.take(5).permutations(k
))
741 fn permutations_k0_yields_once(n
: usize) -> () {
743 let expected
: Vec
<Vec
<usize>> = vec
![vec
![]];
744 let actual
= (0..n
).permutations(k
).collect_vec();
746 assert_eq
!(expected
, actual
);
751 fn equal_dedup(a
: Vec
<i32>) -> bool
{
752 let mut b
= a
.clone();
754 itertools
::equal(&b
, a
.iter().dedup())
759 fn equal_dedup_by(a
: Vec
<(i32, i32)>) -> bool
{
760 let mut b
= a
.clone();
761 b
.dedup_by(|x
, y
| x
.0==y
.0);
762 itertools
::equal(&b
, a
.iter().dedup_by(|x
, y
| x
.0==y
.0))
767 fn size_dedup(a
: Vec
<i32>) -> bool
{
768 correct_size_hint(a
.iter().dedup())
773 fn size_dedup_by(a
: Vec
<(i32, i32)>) -> bool
{
774 correct_size_hint(a
.iter().dedup_by(|x
, y
| x
.0==y
.0))
779 fn exact_repeatn((n
, x
): (usize, i32)) -> bool
{
780 let it
= itertools
::repeat_n(x
, n
);
786 fn size_put_back(a
: Vec
<u8>, x
: Option
<u8>) -> bool
{
787 let mut it
= put_back(a
.into_iter());
789 Some(t
) => it
.put_back(t
),
792 correct_size_hint(it
)
797 fn size_put_backn(a
: Vec
<u8>, b
: Vec
<u8>) -> bool
{
798 let mut it
= put_back_n(a
.into_iter());
802 correct_size_hint(it
)
807 fn size_tee(a
: Vec
<u8>) -> bool
{
808 let (mut t1
, mut t2
) = a
.iter().tee();
812 exact_size(t1
) && exact_size(t2
)
817 fn size_tee_2(a
: Vec
<u8>) -> bool
{
818 let (mut t1
, mut t2
) = a
.iter().dedup().tee();
822 correct_size_hint(t1
) && correct_size_hint(t2
)
827 fn size_take_while_ref(a
: Vec
<u8>, stop
: u8) -> bool
{
828 correct_size_hint(a
.iter().take_while_ref(|x
| **x
!= stop
))
833 fn equal_partition(a
: Vec
<i32>) -> bool
{
835 let mut ap
= a
.clone();
836 let split_index
= itertools
::partition(&mut ap
, |x
| *x
>= 0);
837 let parted
= (0..split_index
).all(|i
| ap
[i
] >= 0) &&
838 (split_index
..a
.len()).all(|i
| ap
[i
] < 0);
847 fn size_combinations(it
: Iter
<i16>) -> bool
{
848 correct_size_hint(it
.tuple_combinations
::<(_
, _
)>())
853 fn equal_combinations(it
: Iter
<i16>) -> bool
{
854 let values
= it
.clone().collect_vec();
855 let mut cmb
= it
.tuple_combinations();
856 for i
in 0..values
.len() {
857 for j
in i
+1..values
.len() {
858 let pair
= (values
[i
], values
[j
]);
859 if pair
!= cmb
.next().unwrap() {
869 fn size_pad_tail(it
: Iter
<i8>, pad
: u8) -> bool
{
870 correct_size_hint(it
.clone().pad_using(pad
as usize, |_
| 0)) &&
871 correct_size_hint(it
.dropping(1).rev().pad_using(pad
as usize, |_
| 0))
876 fn size_pad_tail2(it
: Iter
<i8, Exact
>, pad
: u8) -> bool
{
877 exact_size(it
.pad_using(pad
as usize, |_
| 0))
882 fn size_unique(it
: Iter
<i8>) -> bool
{
883 correct_size_hint(it
.unique())
886 fn count_unique(it
: Vec
<i8>, take_first
: u8) -> () {
888 let mut v
= it
.clone();
892 let mut iter
= cloned(&it
).unique();
893 let first_count
= (&mut iter
).take(take_first
as usize).count();
894 let rest_count
= iter
.count();
895 assert_eq
!(answer
, first_count
+ rest_count
);
900 fn fuzz_group_by_lazy_1(it
: Iter
<u8>) -> bool
{
902 let groups
= it
.group_by(|k
| *k
);
903 let res
= itertools
::equal(jt
, groups
.into_iter().flat_map(|(_
, x
)| x
));
909 fn fuzz_group_by_lazy_2(data
: Vec
<u8>) -> bool
{
910 let groups
= data
.iter().group_by(|k
| *k
/ 10);
911 let res
= itertools
::equal(data
.iter(), groups
.into_iter().flat_map(|(_
, x
)| x
));
917 fn fuzz_group_by_lazy_3(data
: Vec
<u8>) -> bool
{
918 let grouper
= data
.iter().group_by(|k
| *k
/ 10);
919 let groups
= grouper
.into_iter().collect_vec();
920 let res
= itertools
::equal(data
.iter(), groups
.into_iter().flat_map(|(_
, x
)| x
));
926 fn fuzz_group_by_lazy_duo(data
: Vec
<u8>, order
: Vec
<(bool
, bool
)>) -> bool
{
927 let grouper
= data
.iter().group_by(|k
| *k
/ 3);
928 let mut groups1
= grouper
.into_iter();
929 let mut groups2
= grouper
.into_iter();
930 let mut elts
= Vec
::<&u8>::new();
931 let mut old_groups
= Vec
::new();
933 let tup1
= |(_
, b
)| b
;
934 for &(ord
, consume_now
) in &order
{
935 let iter
= &mut [&mut groups1
, &mut groups2
][ord
as usize];
937 Some((_
, gr
)) => if consume_now
{
938 for og
in old_groups
.drain(..) {
948 for og
in old_groups
.drain(..) {
951 for gr
in groups1
.map(&tup1
) { elts.extend(gr); }
952 for gr
in groups2
.map(&tup1
) { elts.extend(gr); }
953 itertools
::assert_equal(&data
, elts
);
959 fn equal_chunks_lazy(a
: Vec
<u8>, size
: u8) -> bool
{
964 let chunks
= a
.iter().chunks(size
as usize);
965 let it
= a
.chunks(size
as usize);
966 for (a
, b
) in chunks
.into_iter().zip(it
) {
967 if !itertools
::equal(a
, b
) {
976 fn equal_tuple_windows_1(a
: Vec
<u8>) -> bool
{
977 let x
= a
.windows(1).map(|s
| (&s
[0], ));
978 let y
= a
.iter().tuple_windows
::<(_
,)>();
979 itertools
::equal(x
, y
)
982 fn equal_tuple_windows_2(a
: Vec
<u8>) -> bool
{
983 let x
= a
.windows(2).map(|s
| (&s
[0], &s
[1]));
984 let y
= a
.iter().tuple_windows
::<(_
, _
)>();
985 itertools
::equal(x
, y
)
988 fn equal_tuple_windows_3(a
: Vec
<u8>) -> bool
{
989 let x
= a
.windows(3).map(|s
| (&s
[0], &s
[1], &s
[2]));
990 let y
= a
.iter().tuple_windows
::<(_
, _
, _
)>();
991 itertools
::equal(x
, y
)
994 fn equal_tuple_windows_4(a
: Vec
<u8>) -> bool
{
995 let x
= a
.windows(4).map(|s
| (&s
[0], &s
[1], &s
[2], &s
[3]));
996 let y
= a
.iter().tuple_windows
::<(_
, _
, _
, _
)>();
997 itertools
::equal(x
, y
)
1000 fn equal_tuples_1(a
: Vec
<u8>) -> bool
{
1001 let x
= a
.chunks(1).map(|s
| (&s
[0], ));
1002 let y
= a
.iter().tuples
::<(_
,)>();
1003 itertools
::equal(x
, y
)
1006 fn equal_tuples_2(a
: Vec
<u8>) -> bool
{
1007 let x
= a
.chunks(2).filter(|s
| s
.len() == 2).map(|s
| (&s
[0], &s
[1]));
1008 let y
= a
.iter().tuples
::<(_
, _
)>();
1009 itertools
::equal(x
, y
)
1012 fn equal_tuples_3(a
: Vec
<u8>) -> bool
{
1013 let x
= a
.chunks(3).filter(|s
| s
.len() == 3).map(|s
| (&s
[0], &s
[1], &s
[2]));
1014 let y
= a
.iter().tuples
::<(_
, _
, _
)>();
1015 itertools
::equal(x
, y
)
1018 fn equal_tuples_4(a
: Vec
<u8>) -> bool
{
1019 let x
= a
.chunks(4).filter(|s
| s
.len() == 4).map(|s
| (&s
[0], &s
[1], &s
[2], &s
[3]));
1020 let y
= a
.iter().tuples
::<(_
, _
, _
, _
)>();
1021 itertools
::equal(x
, y
)
1024 fn exact_tuple_buffer(a
: Vec
<u8>) -> bool
{
1025 let mut iter
= a
.iter().tuples
::<(_
, _
, _
, _
)>();
1027 let buffer
= iter
.into_buffer();
1028 assert_eq
!(buffer
.len(), a
.len() % 4);
1035 fn with_position_exact_size_1(a
: Vec
<u8>) -> bool
{
1036 exact_size_for_this(a
.iter().with_position())
1038 fn with_position_exact_size_2(a
: Iter
<u8, Exact
>) -> bool
{
1039 exact_size_for_this(a
.with_position())
1044 fn correct_group_map_modulo_key(a
: Vec
<u8>, modulo
: u8) -> () {
1045 let modulo
= if modulo
== 0 { 1 }
else { modulo }
; // Avoid `% 0`
1046 let count
= a
.len();
1047 let lookup
= a
.into_iter().map(|i
| (i
% modulo
, i
)).into_group_map();
1049 assert_eq
!(lookup
.values().flat_map(|vals
| vals
.iter()).count(), count
);
1051 for (&key
, vals
) in lookup
.iter() {
1052 assert
!(vals
.iter().all(|&val
| val
% modulo
== key
));
1057 /// A peculiar type: Equality compares both tuple items, but ordering only the
1058 /// first item. This is so we can check the stability property easily.
1059 #[derive(Clone, Debug, PartialEq, Eq)]
1060 struct Val(u32, u32);
1062 impl PartialOrd
<Val
> for Val
{
1063 fn partial_cmp(&self, other
: &Val
) -> Option
<Ordering
> {
1064 self.0.partial_cmp(&other
.0)
1069 fn cmp(&self, other
: &Val
) -> Ordering
{
1070 self.0.cmp(&other
.0)
1074 impl qc
::Arbitrary
for Val
{
1075 fn arbitrary
<G
: qc
::Gen
>(g
: &mut G
) -> Self {
1076 let (x
, y
) = <(u32, u32)>::arbitrary(g
);
1079 fn shrink(&self) -> Box
<Iterator
<Item
= Self>> {
1080 Box
::new((self.0, self.1).shrink().map(|(x
, y
)| Val(x
, y
)))
1085 fn minmax(a
: Vec
<Val
>) -> bool
{
1086 use itertools
::MinMaxResult
;
1089 let minmax
= a
.iter().minmax();
1090 let expected
= match a
.len() {
1091 0 => MinMaxResult
::NoElements
,
1092 1 => MinMaxResult
::OneElement(&a
[0]),
1093 _
=> MinMaxResult
::MinMax(a
.iter().min().unwrap(),
1094 a
.iter().max().unwrap()),
1101 fn minmax_f64(a
: Vec
<f64>) -> TestResult
{
1102 use itertools
::MinMaxResult
;
1104 if a
.iter().any(|x
| x
.is_nan()) {
1105 return TestResult
::discard();
1108 let min
= cloned(&a
).fold1(f64::min
);
1109 let max
= cloned(&a
).fold1(f64::max
);
1111 let minmax
= cloned(&a
).minmax();
1112 let expected
= match a
.len() {
1113 0 => MinMaxResult
::NoElements
,
1114 1 => MinMaxResult
::OneElement(min
.unwrap()),
1115 _
=> MinMaxResult
::MinMax(min
.unwrap(), max
.unwrap()),
1117 TestResult
::from_bool(minmax
== expected
)
1122 #[allow(deprecated)]
1123 fn tree_fold1_f64(mut a
: Vec
<f64>) -> TestResult
{
1124 fn collapse_adjacent
<F
>(x
: Vec
<f64>, mut f
: F
) -> Vec
<f64>
1125 where F
: FnMut(f64, f64) -> f64
1127 let mut out
= Vec
::new();
1128 for i
in (0..x
.len()).step(2) {
1132 out
.push(f(x
[i
], x
[i
+1]));
1138 if a
.iter().any(|x
| x
.is_nan()) {
1139 return TestResult
::discard();
1142 let actual
= a
.iter().cloned().tree_fold1(f64::atan2
);
1145 a
= collapse_adjacent(a
, f64::atan2
);
1147 let expected
= a
.pop();
1149 TestResult
::from_bool(actual
== expected
)
1154 fn exactly_one_i32(a
: Vec
<i32>) -> TestResult
{
1155 let ret
= a
.iter().cloned().exactly_one();
1157 1 => TestResult
::from_bool(ret
.unwrap() == a
[0]),
1158 _
=> TestResult
::from_bool(ret
.unwrap_err().eq(a
.iter().cloned())),