Debian Codegraph @

.cargo/vendor/itertools/tests/quick.rs

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