diff options
Diffstat (limited to 'vendor/itertools/tests/quick.rs')
| -rw-r--r-- | vendor/itertools/tests/quick.rs | 314 |
1 files changed, 223 insertions, 91 deletions
diff --git a/vendor/itertools/tests/quick.rs b/vendor/itertools/tests/quick.rs index c19af6c1e..6f45a63d0 100644 --- a/vendor/itertools/tests/quick.rs +++ b/vendor/itertools/tests/quick.rs @@ -3,34 +3,23 @@ //! //! In particular we test the tedious size_hint and exact size correctness. +#![allow(deprecated, unstable_name_collisions)] + +use itertools::free::{ + cloned, enumerate, multipeek, peek_nth, put_back, put_back_n, rciter, zip, zip_eq, +}; +use itertools::Itertools; +use itertools::{iproduct, izip, multizip, EitherOrBoth}; use quickcheck as qc; +use std::cmp::{max, min, Ordering}; +use std::collections::{HashMap, HashSet}; use std::default::Default; use std::num::Wrapping; use std::ops::Range; -use std::cmp::{max, min, Ordering}; -use std::collections::{HashMap, HashSet}; -use itertools::Itertools; -use itertools::{ - multizip, - EitherOrBoth, - iproduct, - izip, -}; -use itertools::free::{ - cloned, - enumerate, - multipeek, - peek_nth, - put_back, - put_back_n, - rciter, - zip, - zip_eq, -}; -use rand::Rng; -use rand::seq::SliceRandom; use quickcheck::TestResult; +use rand::seq::SliceRandom; +use rand::Rng; /// Trait for size hint modifier types trait HintKind: Copy + Send + qc::Arbitrary { @@ -66,8 +55,10 @@ struct Inexact { impl HintKind for Inexact { fn loosen_bounds(&self, org_hint: (usize, Option<usize>)) -> (usize, Option<usize>) { let (org_lower, org_upper) = org_hint; - (org_lower.saturating_sub(self.underestimate), - org_upper.and_then(move |x| x.checked_add(self.overestimate))) + ( + org_lower.saturating_sub(self.underestimate), + org_upper.and_then(move |x| x.checked_add(self.overestimate)), + ) } } @@ -84,19 +75,15 @@ impl qc::Arbitrary for Inexact { } } - fn shrink(&self) -> Box<dyn Iterator<Item=Self>> { + fn shrink(&self) -> Box<dyn Iterator<Item = Self>> { let underestimate_value = self.underestimate; let overestimate_value = self.overestimate; - Box::new( - underestimate_value.shrink().flat_map(move |ue_value| - overestimate_value.shrink().map(move |oe_value| - Inexact { - underestimate: ue_value, - overestimate: oe_value, - } - ) - ) - ) + Box::new(underestimate_value.shrink().flat_map(move |ue_value| { + overestimate_value.shrink().map(move |oe_value| Inexact { + underestimate: ue_value, + overestimate: oe_value, + }) + })) } } @@ -116,7 +103,9 @@ struct Iter<T, SK: HintKind = Inexact> { hint_kind: SK, } -impl<T, HK> Iter<T, HK> where HK: HintKind +impl<T, HK> Iter<T, HK> +where + HK: HintKind, { fn new(it: Range<T>, hint_kind: HK) -> Self { Iter { @@ -128,64 +117,66 @@ impl<T, HK> Iter<T, HK> where HK: HintKind } impl<T, HK> Iterator for Iter<T, HK> - where Range<T>: Iterator, - <Range<T> as Iterator>::Item: Default, - HK: HintKind, +where + Range<T>: Iterator, + <Range<T> as Iterator>::Item: Default, + HK: HintKind, { type Item = <Range<T> as Iterator>::Item; - fn next(&mut self) -> Option<Self::Item> - { + fn next(&mut self) -> Option<Self::Item> { let elt = self.iterator.next(); if elt.is_none() { self.fuse_flag += 1; // check fuse flag if self.fuse_flag == 2 { - return Some(Default::default()) + return Some(Default::default()); } } elt } - fn size_hint(&self) -> (usize, Option<usize>) - { + fn size_hint(&self) -> (usize, Option<usize>) { let org_hint = self.iterator.size_hint(); self.hint_kind.loosen_bounds(org_hint) } } impl<T, HK> DoubleEndedIterator for Iter<T, HK> - where Range<T>: DoubleEndedIterator, - <Range<T> as Iterator>::Item: Default, - HK: HintKind +where + Range<T>: DoubleEndedIterator, + <Range<T> as Iterator>::Item: Default, + HK: HintKind, { - fn next_back(&mut self) -> Option<Self::Item> { self.iterator.next_back() } + fn next_back(&mut self) -> Option<Self::Item> { + self.iterator.next_back() + } } -impl<T> ExactSizeIterator for Iter<T, Exact> where Range<T>: ExactSizeIterator, +impl<T> ExactSizeIterator for Iter<T, Exact> +where + Range<T>: ExactSizeIterator, <Range<T> as Iterator>::Item: Default, -{ } +{ +} impl<T, HK> qc::Arbitrary for Iter<T, HK> - where T: qc::Arbitrary, - HK: HintKind, +where + T: qc::Arbitrary, + HK: HintKind, { - fn arbitrary<G: qc::Gen>(g: &mut G) -> Self - { + fn arbitrary<G: qc::Gen>(g: &mut G) -> Self { Iter::new(T::arbitrary(g)..T::arbitrary(g), HK::arbitrary(g)) } - fn shrink(&self) -> Box<dyn Iterator<Item=Iter<T, HK>>> - { + fn shrink(&self) -> Box<dyn Iterator<Item = Iter<T, HK>>> { let r = self.iterator.clone(); let hint_kind = self.hint_kind; - Box::new( - r.start.shrink().flat_map(move |a| - r.end.shrink().map(move |b| - Iter::new(a.clone()..b, hint_kind) - ) - ) - ) + Box::new(r.start.shrink().flat_map(move |a| { + r.end + .shrink() + .map(move |b| Iter::new(a.clone()..b, hint_kind)) + })) } } @@ -201,7 +192,10 @@ struct ShiftRange<HK = Inexact> { hint_kind: HK, } -impl<HK> Iterator for ShiftRange<HK> where HK: HintKind { +impl<HK> Iterator for ShiftRange<HK> +where + HK: HintKind, +{ type Item = Iter<i32, HK>; fn next(&mut self) -> Option<Self::Item> { @@ -219,10 +213,11 @@ impl<HK> Iterator for ShiftRange<HK> where HK: HintKind { } } -impl ExactSizeIterator for ShiftRange<Exact> { } +impl ExactSizeIterator for ShiftRange<Exact> {} impl<HK> qc::Arbitrary for ShiftRange<HK> - where HK: HintKind +where + HK: HintKind, { fn arbitrary<G: qc::Gen>(g: &mut G) -> Self { const MAX_STARTING_RANGE_DIFF: i32 = 32; @@ -250,7 +245,7 @@ impl<HK> qc::Arbitrary for ShiftRange<HK> fn correct_count<I, F>(get_it: F) -> bool where I: Iterator, - F: Fn() -> I + F: Fn() -> I, { let mut counts = vec![get_it().count()]; @@ -276,7 +271,10 @@ where for (i, returned_count) in counts.into_iter().enumerate() { let actual_count = total_actual_count - i; if actual_count != returned_count { - println!("Total iterations: {} True count: {} returned count: {}", i, actual_count, returned_count); + println!( + "Total iterations: {} True count: {} returned count: {}", + i, actual_count, returned_count + ); return false; } @@ -299,12 +297,10 @@ fn correct_size_hint<I: Iterator>(mut it: I) -> bool { // check all the size hints for &(low, hi) in &hints { true_count -= 1; - if low > true_count || - (hi.is_some() && hi.unwrap() < true_count) - { + if low > true_count || (hi.is_some() && hi.unwrap() < true_count) { println!("True size: {:?}, size hint: {:?}", true_count, (low, hi)); //println!("All hints: {:?}", hints); - return false + return false; } } true @@ -313,13 +309,19 @@ fn correct_size_hint<I: Iterator>(mut it: I) -> bool { fn exact_size<I: ExactSizeIterator>(mut it: I) -> bool { // check every iteration let (mut low, mut hi) = it.size_hint(); - if Some(low) != hi { return false; } + if Some(low) != hi { + return false; + } while let Some(_) = it.next() { let (xlow, xhi) = it.size_hint(); - if low != xlow + 1 { return false; } + if low != xlow + 1 { + return false; + } low = xlow; hi = xhi; - if Some(low) != hi { return false; } + if Some(low) != hi { + return false; + } } let (low, hi) = it.size_hint(); low == 0 && hi == Some(0) @@ -329,13 +331,19 @@ fn exact_size<I: ExactSizeIterator>(mut it: I) -> bool { fn exact_size_for_this<I: Iterator>(mut it: I) -> bool { // check every iteration let (mut low, mut hi) = it.size_hint(); - if Some(low) != hi { return false; } + if Some(low) != hi { + return false; + } while let Some(_) = it.next() { let (xlow, xhi) = it.size_hint(); - if low != xlow + 1 { return false; } + if low != xlow + 1 { + return false; + } low = xlow; hi = xhi; - if Some(low) != hi { return false; } + if Some(low) != hi { + return false; + } } let (low, hi) = it.size_hint(); low == 0 && hi == Some(0) @@ -751,6 +759,56 @@ quickcheck! { } quickcheck! { + fn correct_peek_nth(mut a: Vec<u16>) -> () { + let mut it = peek_nth(a.clone()); + for start_pos in 0..a.len() + 2 { + for real_idx in start_pos..a.len() + 2 { + let peek_idx = real_idx - start_pos; + assert_eq!(it.peek_nth(peek_idx), a.get(real_idx)); + assert_eq!(it.peek_nth_mut(peek_idx), a.get_mut(real_idx)); + } + assert_eq!(it.next(), a.get(start_pos).copied()); + } + } + + fn peek_nth_mut_replace(a: Vec<u16>, b: Vec<u16>) -> () { + let mut it = peek_nth(a.iter()); + for i in 0..a.len().min(b.len()) { + *it.peek_nth_mut(i).unwrap() = &b[i]; + } + for i in 0..a.len() { + assert_eq!(it.next().unwrap(), b.get(i).unwrap_or(&a[i])); + } + assert_eq!(it.next(), None); + assert_eq!(it.next(), None); + } + + fn peek_nth_next_if(a: Vec<u8>) -> () { + let mut it = peek_nth(a.clone()); + for (idx, mut value) in a.iter().copied().enumerate() { + let should_be_none = it.next_if(|x| x != &value); + assert_eq!(should_be_none, None); + if value % 5 == 0 { + // Sometimes, peek up to 3 further. + let n = value as usize % 3; + let nth = it.peek_nth(n); + assert_eq!(nth, a.get(idx + n)); + } else if value % 5 == 1 { + // Sometimes, peek next element mutably. + if let Some(v) = it.peek_mut() { + *v = v.wrapping_sub(1); + let should_be_none = it.next_if_eq(&value); + assert_eq!(should_be_none, None); + value = value.wrapping_sub(1); + } + } + let eq = it.next_if_eq(&value); + assert_eq!(eq, Some(value)); + } + } +} + +quickcheck! { fn dedup_via_coalesce(a: Vec<i32>) -> bool { let mut b = a.clone(); b.dedup(); @@ -895,8 +953,31 @@ quickcheck! { } quickcheck! { - fn size_combinations(it: Iter<i16>) -> bool { - correct_size_hint(it.tuple_combinations::<(_, _)>()) + fn size_combinations(a: Iter<i16>) -> bool { + let it = a.clone().tuple_combinations::<(_, _)>(); + correct_size_hint(it.clone()) && it.count() == binomial(a.count(), 2) + } + + fn exact_size_combinations_1(a: Vec<u8>) -> bool { + let it = a.iter().tuple_combinations::<(_,)>(); + exact_size_for_this(it.clone()) && it.count() == binomial(a.len(), 1) + } + fn exact_size_combinations_2(a: Vec<u8>) -> bool { + let it = a.iter().tuple_combinations::<(_, _)>(); + exact_size_for_this(it.clone()) && it.count() == binomial(a.len(), 2) + } + fn exact_size_combinations_3(mut a: Vec<u8>) -> bool { + a.truncate(15); + let it = a.iter().tuple_combinations::<(_, _, _)>(); + exact_size_for_this(it.clone()) && it.count() == binomial(a.len(), 3) + } +} + +fn binomial(n: usize, k: usize) -> usize { + if k > n { + 0 + } else { + (n - k + 1..=n).product::<usize>() / (1..=k).product::<usize>() } } @@ -1111,6 +1192,10 @@ quickcheck! { true } + fn circular_tuple_windows_exact_size(a: Vec<u8>) -> bool { + exact_size(a.iter().circular_tuple_windows::<(_, _, _, _)>()) + } + fn equal_tuple_windows_1(a: Vec<u8>) -> bool { let x = a.windows(1).map(|s| (&s[0], )); let y = a.iter().tuple_windows::<(_,)>(); @@ -1135,6 +1220,14 @@ quickcheck! { itertools::equal(x, y) } + fn tuple_windows_exact_size_1(a: Vec<u8>) -> bool { + exact_size(a.iter().tuple_windows::<(_,)>()) + } + + fn tuple_windows_exact_size_4(a: Vec<u8>) -> bool { + exact_size(a.iter().tuple_windows::<(_, _, _, _)>()) + } + fn equal_tuples_1(a: Vec<u8>) -> bool { let x = a.chunks(1).map(|s| (&s[0], )); let y = a.iter().tuples::<(_,)>(); @@ -1166,6 +1259,18 @@ quickcheck! { assert_eq!(buffer.len(), a.len() % 4); exact_size(buffer) } + + fn tuples_size_hint_inexact(a: Iter<u8>) -> bool { + correct_size_hint(a.clone().tuples::<(_,)>()) + && correct_size_hint(a.clone().tuples::<(_, _)>()) + && correct_size_hint(a.tuples::<(_, _, _, _)>()) + } + + fn tuples_size_hint_exact(a: Iter<u8, Exact>) -> bool { + exact_size(a.clone().tuples::<(_,)>()) + && exact_size(a.clone().tuples::<(_, _)>()) + && exact_size(a.tuples::<(_, _, _, _)>()) + } } // with_position @@ -1332,7 +1437,7 @@ quickcheck! { Some(acc.unwrap_or(0) + val) } }); - + let group_map_lookup = a.iter() .map(|&b| b as u64) .map(|i| (i % modulo, i)) @@ -1352,7 +1457,7 @@ quickcheck! { for m in 0..modulo { assert_eq!( - lookup.get(&m).copied(), + lookup.get(&m).copied(), a.iter() .map(|&b| b as u64) .filter(|&val| val % modulo == m) @@ -1367,6 +1472,35 @@ quickcheck! { } } + fn correct_grouping_map_by_fold_with_modulo_key(a: Vec<u8>, modulo: u8) -> () { + #[derive(Debug, Default, PartialEq)] + struct Accumulator { + acc: u64, + } + + let modulo = if modulo == 0 { 1 } else { modulo } as u64; // Avoid `% 0` + let lookup = a.iter().map(|&b| b as u64) // Avoid overflows + .into_grouping_map_by(|i| i % modulo) + .fold_with(|_key, _val| Default::default(), |Accumulator { acc }, &key, val| { + assert!(val % modulo == key); + let acc = acc + val; + Accumulator { acc } + }); + + let group_map_lookup = a.iter() + .map(|&b| b as u64) + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().sum())).map(|(key, acc)| (key,Accumulator { acc })) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &Accumulator { acc: sum }) in lookup.iter() { + assert_eq!(sum, a.iter().map(|&b| b as u64).filter(|&val| val % modulo == key).sum::<u64>()); + } + } + fn correct_grouping_map_by_fold_modulo_key(a: Vec<u8>, modulo: u8) -> () { let modulo = if modulo == 0 { 1 } else { modulo } as u64; // Avoid `% 0` let lookup = a.iter().map(|&b| b as u64) // Avoid overflows @@ -1472,7 +1606,7 @@ quickcheck! { assert_eq!(Some(max), a.iter().copied().filter(|&val| val % modulo == key).max_by_key(|&val| val)); } } - + fn correct_grouping_map_by_min_modulo_key(a: Vec<u8>, modulo: u8) -> () { let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).min(); @@ -1523,7 +1657,7 @@ quickcheck! { assert_eq!(Some(min), a.iter().copied().filter(|&val| val % modulo == key).min_by_key(|&val| val)); } } - + fn correct_grouping_map_by_minmax_modulo_key(a: Vec<u8>, modulo: u8) -> () { let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).minmax(); @@ -1636,7 +1770,7 @@ quickcheck! { .min_by(|_, _, _| Ordering::Equal); assert_eq!(lookup[&0], 0); - + let lookup = (0..=10) .into_grouping_map_by(|_| 0) .minmax_by(|_, _, _| Ordering::Equal); @@ -1694,12 +1828,10 @@ quickcheck! { } } - -fn is_fused<I: Iterator>(mut it: I) -> bool -{ +fn is_fused<I: Iterator>(mut it: I) -> bool { for _ in it.by_ref() {} - for _ in 0..10{ - if it.next().is_some(){ + for _ in 0..10 { + if it.next().is_some() { return false; } } @@ -1740,7 +1872,7 @@ quickcheck! { !is_fused(a.clone().interleave_shortest(b.clone())) && is_fused(a.fuse().interleave_shortest(b.fuse())) } - + fn fused_product(a: Iter<i16>, b: Iter<i16>) -> bool { is_fused(a.fuse().cartesian_product(b.fuse())) |