diff options
Diffstat (limited to 'third_party/rust/itertools/tests')
| -rw-r--r-- | third_party/rust/itertools/tests/adaptors_no_collect.rs | 46 | ||||
| -rw-r--r-- | third_party/rust/itertools/tests/flatten_ok.rs | 76 | ||||
| -rw-r--r-- | third_party/rust/itertools/tests/macros_hygiene.rs | 13 | ||||
| -rw-r--r-- | third_party/rust/itertools/tests/merge_join.rs | 108 | ||||
| -rw-r--r-- | third_party/rust/itertools/tests/peeking_take_while.rs | 50 | ||||
| -rw-r--r-- | third_party/rust/itertools/tests/quick.rs | 1749 | ||||
| -rw-r--r-- | third_party/rust/itertools/tests/specializations.rs | 153 | ||||
| -rw-r--r-- | third_party/rust/itertools/tests/test_core.rs | 317 | ||||
| -rw-r--r-- | third_party/rust/itertools/tests/test_std.rs | 1168 | ||||
| -rw-r--r-- | third_party/rust/itertools/tests/tuples.rs | 86 | ||||
| -rw-r--r-- | third_party/rust/itertools/tests/zip.rs | 77 |
11 files changed, 3843 insertions, 0 deletions
diff --git a/third_party/rust/itertools/tests/adaptors_no_collect.rs b/third_party/rust/itertools/tests/adaptors_no_collect.rs new file mode 100644 index 0000000000..103db23f1e --- /dev/null +++ b/third_party/rust/itertools/tests/adaptors_no_collect.rs @@ -0,0 +1,46 @@ +use itertools::Itertools; + +struct PanickingCounter { + curr: usize, + max: usize, +} + +impl Iterator for PanickingCounter { + type Item = (); + + fn next(&mut self) -> Option<Self::Item> { + self.curr += 1; + + assert_ne!( + self.curr, self.max, + "Input iterator reached maximum of {} suggesting collection by adaptor", + self.max + ); + + Some(()) + } +} + +fn no_collect_test<A, T>(to_adaptor: T) + where A: Iterator, T: Fn(PanickingCounter) -> A +{ + let counter = PanickingCounter { curr: 0, max: 10_000 }; + let adaptor = to_adaptor(counter); + + for _ in adaptor.take(5) {} +} + +#[test] +fn permutations_no_collect() { + no_collect_test(|iter| iter.permutations(5)) +} + +#[test] +fn combinations_no_collect() { + no_collect_test(|iter| iter.combinations(5)) +} + +#[test] +fn combinations_with_replacement_no_collect() { + no_collect_test(|iter| iter.combinations_with_replacement(5)) +}
\ No newline at end of file diff --git a/third_party/rust/itertools/tests/flatten_ok.rs b/third_party/rust/itertools/tests/flatten_ok.rs new file mode 100644 index 0000000000..bf835b5d70 --- /dev/null +++ b/third_party/rust/itertools/tests/flatten_ok.rs @@ -0,0 +1,76 @@ +use itertools::{assert_equal, Itertools}; +use std::{ops::Range, vec::IntoIter}; + +fn mix_data() -> IntoIter<Result<Range<i32>, bool>> { + vec![Ok(0..2), Err(false), Ok(2..4), Err(true), Ok(4..6)].into_iter() +} + +fn ok_data() -> IntoIter<Result<Range<i32>, bool>> { + vec![Ok(0..2), Ok(2..4), Ok(4..6)].into_iter() +} + +#[test] +fn flatten_ok_mixed_expected_forward() { + assert_equal( + mix_data().flatten_ok(), + vec![ + Ok(0), + Ok(1), + Err(false), + Ok(2), + Ok(3), + Err(true), + Ok(4), + Ok(5), + ], + ); +} + +#[test] +fn flatten_ok_mixed_expected_reverse() { + assert_equal( + mix_data().flatten_ok().rev(), + vec![ + Ok(5), + Ok(4), + Err(true), + Ok(3), + Ok(2), + Err(false), + Ok(1), + Ok(0), + ], + ); +} + +#[test] +fn flatten_ok_collect_mixed_forward() { + assert_eq!( + mix_data().flatten_ok().collect::<Result<Vec<_>, _>>(), + Err(false) + ); +} + +#[test] +fn flatten_ok_collect_mixed_reverse() { + assert_eq!( + mix_data().flatten_ok().rev().collect::<Result<Vec<_>, _>>(), + Err(true) + ); +} + +#[test] +fn flatten_ok_collect_ok_forward() { + assert_eq!( + ok_data().flatten_ok().collect::<Result<Vec<_>, _>>(), + Ok((0..6).collect()) + ); +} + +#[test] +fn flatten_ok_collect_ok_reverse() { + assert_eq!( + ok_data().flatten_ok().rev().collect::<Result<Vec<_>, _>>(), + Ok((0..6).rev().collect()) + ); +} diff --git a/third_party/rust/itertools/tests/macros_hygiene.rs b/third_party/rust/itertools/tests/macros_hygiene.rs new file mode 100644 index 0000000000..d1111245d6 --- /dev/null +++ b/third_party/rust/itertools/tests/macros_hygiene.rs @@ -0,0 +1,13 @@ +#[test] +fn iproduct_hygiene() { + let _ = itertools::iproduct!(0..6); + let _ = itertools::iproduct!(0..6, 0..9); + let _ = itertools::iproduct!(0..6, 0..9, 0..12); +} + +#[test] +fn izip_hygiene() { + let _ = itertools::izip!(0..6); + let _ = itertools::izip!(0..6, 0..9); + let _ = itertools::izip!(0..6, 0..9, 0..12); +} diff --git a/third_party/rust/itertools/tests/merge_join.rs b/third_party/rust/itertools/tests/merge_join.rs new file mode 100644 index 0000000000..3280b7d4ec --- /dev/null +++ b/third_party/rust/itertools/tests/merge_join.rs @@ -0,0 +1,108 @@ +use itertools::EitherOrBoth; +use itertools::free::merge_join_by; + +#[test] +fn empty() { + let left: Vec<u32> = vec![]; + let right: Vec<u32> = vec![]; + let expected_result: Vec<EitherOrBoth<u32, u32>> = vec![]; + let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)) + .collect::<Vec<_>>(); + assert_eq!(expected_result, actual_result); +} + +#[test] +fn left_only() { + let left: Vec<u32> = vec![1,2,3]; + let right: Vec<u32> = vec![]; + let expected_result: Vec<EitherOrBoth<u32, u32>> = vec![ + EitherOrBoth::Left(1), + EitherOrBoth::Left(2), + EitherOrBoth::Left(3) + ]; + let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)) + .collect::<Vec<_>>(); + assert_eq!(expected_result, actual_result); +} + +#[test] +fn right_only() { + let left: Vec<u32> = vec![]; + let right: Vec<u32> = vec![1,2,3]; + let expected_result: Vec<EitherOrBoth<u32, u32>> = vec![ + EitherOrBoth::Right(1), + EitherOrBoth::Right(2), + EitherOrBoth::Right(3) + ]; + let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)) + .collect::<Vec<_>>(); + assert_eq!(expected_result, actual_result); +} + +#[test] +fn first_left_then_right() { + let left: Vec<u32> = vec![1,2,3]; + let right: Vec<u32> = vec![4,5,6]; + let expected_result: Vec<EitherOrBoth<u32, u32>> = vec![ + EitherOrBoth::Left(1), + EitherOrBoth::Left(2), + EitherOrBoth::Left(3), + EitherOrBoth::Right(4), + EitherOrBoth::Right(5), + EitherOrBoth::Right(6) + ]; + let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)) + .collect::<Vec<_>>(); + assert_eq!(expected_result, actual_result); +} + +#[test] +fn first_right_then_left() { + let left: Vec<u32> = vec![4,5,6]; + let right: Vec<u32> = vec![1,2,3]; + let expected_result: Vec<EitherOrBoth<u32, u32>> = vec![ + EitherOrBoth::Right(1), + EitherOrBoth::Right(2), + EitherOrBoth::Right(3), + EitherOrBoth::Left(4), + EitherOrBoth::Left(5), + EitherOrBoth::Left(6) + ]; + let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)) + .collect::<Vec<_>>(); + assert_eq!(expected_result, actual_result); +} + +#[test] +fn interspersed_left_and_right() { + let left: Vec<u32> = vec![1,3,5]; + let right: Vec<u32> = vec![2,4,6]; + let expected_result: Vec<EitherOrBoth<u32, u32>> = vec![ + EitherOrBoth::Left(1), + EitherOrBoth::Right(2), + EitherOrBoth::Left(3), + EitherOrBoth::Right(4), + EitherOrBoth::Left(5), + EitherOrBoth::Right(6) + ]; + let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)) + .collect::<Vec<_>>(); + assert_eq!(expected_result, actual_result); +} + +#[test] +fn overlapping_left_and_right() { + let left: Vec<u32> = vec![1,3,4,6]; + let right: Vec<u32> = vec![2,3,4,5]; + let expected_result: Vec<EitherOrBoth<u32, u32>> = vec![ + EitherOrBoth::Left(1), + EitherOrBoth::Right(2), + EitherOrBoth::Both(3, 3), + EitherOrBoth::Both(4, 4), + EitherOrBoth::Right(5), + EitherOrBoth::Left(6) + ]; + let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)) + .collect::<Vec<_>>(); + assert_eq!(expected_result, actual_result); +} diff --git a/third_party/rust/itertools/tests/peeking_take_while.rs b/third_party/rust/itertools/tests/peeking_take_while.rs new file mode 100644 index 0000000000..a1147027e8 --- /dev/null +++ b/third_party/rust/itertools/tests/peeking_take_while.rs @@ -0,0 +1,50 @@ +use itertools::Itertools; +use itertools::{put_back, put_back_n}; + +#[test] +fn peeking_take_while_peekable() { + let mut r = (0..10).peekable(); + r.peeking_take_while(|x| *x <= 3).count(); + assert_eq!(r.next(), Some(4)); +} + +#[test] +fn peeking_take_while_put_back() { + let mut r = put_back(0..10); + r.peeking_take_while(|x| *x <= 3).count(); + assert_eq!(r.next(), Some(4)); + r.peeking_take_while(|_| true).count(); + assert_eq!(r.next(), None); +} + +#[test] +fn peeking_take_while_put_back_n() { + let mut r = put_back_n(6..10); + for elt in (0..6).rev() { + r.put_back(elt); + } + r.peeking_take_while(|x| *x <= 3).count(); + assert_eq!(r.next(), Some(4)); + r.peeking_take_while(|_| true).count(); + assert_eq!(r.next(), None); +} + +#[test] +fn peeking_take_while_slice_iter() { + let v = [1, 2, 3, 4, 5, 6]; + let mut r = v.iter(); + r.peeking_take_while(|x| **x <= 3).count(); + assert_eq!(r.next(), Some(&4)); + r.peeking_take_while(|_| true).count(); + assert_eq!(r.next(), None); +} + +#[test] +fn peeking_take_while_slice_iter_rev() { + let v = [1, 2, 3, 4, 5, 6]; + let mut r = v.iter().rev(); + r.peeking_take_while(|x| **x >= 3).count(); + assert_eq!(r.next(), Some(&2)); + r.peeking_take_while(|_| true).count(); + assert_eq!(r.next(), None); +} diff --git a/third_party/rust/itertools/tests/quick.rs b/third_party/rust/itertools/tests/quick.rs new file mode 100644 index 0000000000..0adcf1ad72 --- /dev/null +++ b/third_party/rust/itertools/tests/quick.rs @@ -0,0 +1,1749 @@ +//! The purpose of these tests is to cover corner cases of iterators +//! and adaptors. +//! +//! In particular we test the tedious size_hint and exact size correctness. + +use quickcheck as qc; +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; + +/// Trait for size hint modifier types +trait HintKind: Copy + Send + qc::Arbitrary { + fn loosen_bounds(&self, org_hint: (usize, Option<usize>)) -> (usize, Option<usize>); +} + +/// Exact size hint variant that leaves hints unchanged +#[derive(Clone, Copy, Debug)] +struct Exact {} + +impl HintKind for Exact { + fn loosen_bounds(&self, org_hint: (usize, Option<usize>)) -> (usize, Option<usize>) { + org_hint + } +} + +impl qc::Arbitrary for Exact { + fn arbitrary<G: qc::Gen>(_: &mut G) -> Self { + Exact {} + } +} + +/// Inexact size hint variant to simulate imprecise (but valid) size hints +/// +/// Will always decrease the lower bound and increase the upper bound +/// of the size hint by set amounts. +#[derive(Clone, Copy, Debug)] +struct Inexact { + underestimate: usize, + overestimate: usize, +} + +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))) + } +} + +impl qc::Arbitrary for Inexact { + fn arbitrary<G: qc::Gen>(g: &mut G) -> Self { + let ue_value = usize::arbitrary(g); + let oe_value = usize::arbitrary(g); + // Compensate for quickcheck using extreme values too rarely + let ue_choices = &[0, ue_value, usize::max_value()]; + let oe_choices = &[0, oe_value, usize::max_value()]; + Inexact { + underestimate: *ue_choices.choose(g).unwrap(), + overestimate: *oe_choices.choose(g).unwrap(), + } + } + + 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, + } + ) + ) + ) + } +} + +/// Our base iterator that we can impl Arbitrary for +/// +/// By default we'll return inexact bounds estimates for size_hint +/// to make tests harder to pass. +/// +/// NOTE: Iter is tricky and is not fused, to help catch bugs. +/// At the end it will return None once, then return Some(0), +/// then return None again. +#[derive(Clone, Debug)] +struct Iter<T, SK: HintKind = Inexact> { + iterator: Range<T>, + // fuse/done flag + fuse_flag: i32, + hint_kind: SK, +} + +impl<T, HK> Iter<T, HK> where HK: HintKind +{ + fn new(it: Range<T>, hint_kind: HK) -> Self { + Iter { + iterator: it, + fuse_flag: 0, + hint_kind, + } + } +} + +impl<T, HK> Iterator for Iter<T, HK> + 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> + { + 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()) + } + } + elt + } + + 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 +{ + fn next_back(&mut self) -> Option<Self::Item> { self.iterator.next_back() } +} + +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, +{ + 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>>> + { + 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) + ) + ) + ) + } +} + +/// A meta-iterator which yields `Iter<i32>`s whose start/endpoints are +/// increased or decreased linearly on each iteration. +#[derive(Clone, Debug)] +struct ShiftRange<HK = Inexact> { + range_start: i32, + range_end: i32, + start_step: i32, + end_step: i32, + iter_count: u32, + hint_kind: HK, +} + +impl<HK> Iterator for ShiftRange<HK> where HK: HintKind { + type Item = Iter<i32, HK>; + + fn next(&mut self) -> Option<Self::Item> { + if self.iter_count == 0 { + return None; + } + + let iter = Iter::new(self.range_start..self.range_end, self.hint_kind); + + self.range_start += self.start_step; + self.range_end += self.end_step; + self.iter_count -= 1; + + Some(iter) + } +} + +impl ExactSizeIterator for ShiftRange<Exact> { } + +impl<HK> qc::Arbitrary for ShiftRange<HK> + where HK: HintKind +{ + fn arbitrary<G: qc::Gen>(g: &mut G) -> Self { + const MAX_STARTING_RANGE_DIFF: i32 = 32; + const MAX_STEP_MODULO: i32 = 8; + const MAX_ITER_COUNT: u32 = 3; + + let range_start = qc::Arbitrary::arbitrary(g); + let range_end = range_start + g.gen_range(0, MAX_STARTING_RANGE_DIFF + 1); + let start_step = g.gen_range(-MAX_STEP_MODULO, MAX_STEP_MODULO + 1); + let end_step = g.gen_range(-MAX_STEP_MODULO, MAX_STEP_MODULO + 1); + let iter_count = g.gen_range(0, MAX_ITER_COUNT + 1); + let hint_kind = qc::Arbitrary::arbitrary(g); + + ShiftRange { + range_start, + range_end, + start_step, + end_step, + iter_count, + hint_kind, + } + } +} + +fn correct_count<I, F>(get_it: F) -> bool +where + I: Iterator, + F: Fn() -> I +{ + let mut counts = vec![get_it().count()]; + + 'outer: loop { + let mut it = get_it(); + + for _ in 0..(counts.len() - 1) { + #[allow(clippy::manual_assert)] + if it.next().is_none() { + panic!("Iterator shouldn't be finished, may not be deterministic"); + } + } + + if it.next().is_none() { + break 'outer; + } + + counts.push(it.count()); + } + + let total_actual_count = counts.len() - 1; + + 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); + + return false; + } + } + + true +} + +fn correct_size_hint<I: Iterator>(mut it: I) -> bool { + // record size hint at each iteration + let initial_hint = it.size_hint(); + let mut hints = Vec::with_capacity(initial_hint.0 + 1); + hints.push(initial_hint); + while let Some(_) = it.next() { + hints.push(it.size_hint()) + } + + let mut true_count = hints.len(); // start off +1 too much + + // check all the size hints + for &(low, hi) in &hints { + true_count -= 1; + 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 + } + } + true +} + +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; } + while let Some(_) = it.next() { + let (xlow, xhi) = it.size_hint(); + if low != xlow + 1 { return false; } + low = xlow; + hi = xhi; + if Some(low) != hi { return false; } + } + let (low, hi) = it.size_hint(); + low == 0 && hi == Some(0) +} + +// Exact size for this case, without ExactSizeIterator +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; } + while let Some(_) = it.next() { + let (xlow, xhi) = it.size_hint(); + if low != xlow + 1 { return false; } + low = xlow; + hi = xhi; + if Some(low) != hi { return false; } + } + let (low, hi) = it.size_hint(); + low == 0 && hi == Some(0) +} + +/* + * NOTE: Range<i8> is broken! + * (all signed ranges are) +#[quickcheck] +fn size_range_i8(a: Iter<i8>) -> bool { + exact_size(a) +} + +#[quickcheck] +fn size_range_i16(a: Iter<i16>) -> bool { + exact_size(a) +} + +#[quickcheck] +fn size_range_u8(a: Iter<u8>) -> bool { + exact_size(a) +} + */ + +macro_rules! quickcheck { + // accept several property function definitions + // The property functions can use pattern matching and `mut` as usual + // in the function arguments, but the functions can not be generic. + {$($(#$attr:tt)* fn $fn_name:ident($($arg:tt)*) -> $ret:ty { $($code:tt)* })*} => ( + $( + #[test] + $(#$attr)* + fn $fn_name() { + fn prop($($arg)*) -> $ret { + $($code)* + } + ::quickcheck::quickcheck(quickcheck!(@fn prop [] $($arg)*)); + } + )* + ); + // parse argument list (with patterns allowed) into prop as fn(_, _) -> _ + (@fn $f:ident [$($t:tt)*]) => { + $f as fn($($t),*) -> _ + }; + (@fn $f:ident [$($p:tt)*] : $($tail:tt)*) => { + quickcheck!(@fn $f [$($p)* _] $($tail)*) + }; + (@fn $f:ident [$($p:tt)*] $t:tt $($tail:tt)*) => { + quickcheck!(@fn $f [$($p)*] $($tail)*) + }; +} + +quickcheck! { + + fn size_product(a: Iter<u16>, b: Iter<u16>) -> bool { + correct_size_hint(a.cartesian_product(b)) + } + fn size_product3(a: Iter<u16>, b: Iter<u16>, c: Iter<u16>) -> bool { + correct_size_hint(iproduct!(a, b, c)) + } + + fn correct_cartesian_product3(a: Iter<u16>, b: Iter<u16>, c: Iter<u16>, + take_manual: usize) -> () + { + // test correctness of iproduct through regular iteration (take) + // and through fold. + let ac = a.clone(); + let br = &b.clone(); + let cr = &c.clone(); + let answer: Vec<_> = ac.flat_map(move |ea| br.clone().flat_map(move |eb| cr.clone().map(move |ec| (ea, eb, ec)))).collect(); + let mut product_iter = iproduct!(a, b, c); + let mut actual = Vec::new(); + + actual.extend((&mut product_iter).take(take_manual)); + if actual.len() == take_manual { + product_iter.fold((), |(), elt| actual.push(elt)); + } + assert_eq!(answer, actual); + } + + fn size_multi_product(a: ShiftRange) -> bool { + correct_size_hint(a.multi_cartesian_product()) + } + fn correct_multi_product3(a: ShiftRange, take_manual: usize) -> () { + // Fix no. of iterators at 3 + let a = ShiftRange { iter_count: 3, ..a }; + + // test correctness of MultiProduct through regular iteration (take) + // and through fold. + let mut iters = a.clone(); + let i0 = iters.next().unwrap(); + let i1r = &iters.next().unwrap(); + let i2r = &iters.next().unwrap(); + let answer: Vec<_> = i0.flat_map(move |ei0| i1r.clone().flat_map(move |ei1| i2r.clone().map(move |ei2| vec![ei0, ei1, ei2]))).collect(); + let mut multi_product = a.clone().multi_cartesian_product(); + let mut actual = Vec::new(); + + actual.extend((&mut multi_product).take(take_manual)); + if actual.len() == take_manual { + multi_product.fold((), |(), elt| actual.push(elt)); + } + assert_eq!(answer, actual); + + assert_eq!(answer.into_iter().last(), a.multi_cartesian_product().last()); + } + + #[allow(deprecated)] + fn size_step(a: Iter<i16, Exact>, s: usize) -> bool { + let mut s = s; + if s == 0 { + s += 1; // never zero + } + let filt = a.clone().dedup(); + correct_size_hint(filt.step(s)) && + exact_size(a.step(s)) + } + + #[allow(deprecated)] + fn equal_step(a: Iter<i16>, s: usize) -> bool { + let mut s = s; + if s == 0 { + s += 1; // never zero + } + let mut i = 0; + itertools::equal(a.clone().step(s), a.filter(|_| { + let keep = i % s == 0; + i += 1; + keep + })) + } + + #[allow(deprecated)] + fn equal_step_vec(a: Vec<i16>, s: usize) -> bool { + let mut s = s; + if s == 0 { + s += 1; // never zero + } + let mut i = 0; + itertools::equal(a.iter().step(s), a.iter().filter(|_| { + let keep = i % s == 0; + i += 1; + keep + })) + } + + fn size_multipeek(a: Iter<u16, Exact>, s: u8) -> bool { + let mut it = multipeek(a); + // peek a few times + for _ in 0..s { + it.peek(); + } + exact_size(it) + } + + fn size_peek_nth(a: Iter<u16, Exact>, s: u8) -> bool { + let mut it = peek_nth(a); + // peek a few times + for n in 0..s { + it.peek_nth(n as usize); + } + exact_size(it) + } + + fn equal_merge(mut a: Vec<i16>, mut b: Vec<i16>) -> bool { + a.sort(); + b.sort(); + let mut merged = a.clone(); + merged.extend(b.iter().cloned()); + merged.sort(); + itertools::equal(&merged, a.iter().merge(&b)) + } + fn size_merge(a: Iter<u16>, b: Iter<u16>) -> bool { + correct_size_hint(a.merge(b)) + } + fn size_zip(a: Iter<i16, Exact>, b: Iter<i16, Exact>, c: Iter<i16, Exact>) -> bool { + let filt = a.clone().dedup(); + correct_size_hint(multizip((filt, b.clone(), c.clone()))) && + exact_size(multizip((a, b, c))) + } + fn size_zip_rc(a: Iter<i16>, b: Iter<i16>) -> bool { + let rc = rciter(a); + correct_size_hint(multizip((&rc, &rc, b))) + } + + fn size_zip_macro(a: Iter<i16, Exact>, b: Iter<i16, Exact>, c: Iter<i16, Exact>) -> bool { + let filt = a.clone().dedup(); + correct_size_hint(izip!(filt, b.clone(), c.clone())) && + exact_size(izip!(a, b, c)) + } + fn equal_kmerge(mut a: Vec<i16>, mut b: Vec<i16>, mut c: Vec<i16>) -> bool { + use itertools::free::kmerge; + a.sort(); + b.sort(); + c.sort(); + let mut merged = a.clone(); + merged.extend(b.iter().cloned()); + merged.extend(c.iter().cloned()); + merged.sort(); + itertools::equal(merged.into_iter(), kmerge(vec![a, b, c])) + } + + // Any number of input iterators + fn equal_kmerge_2(mut inputs: Vec<Vec<i16>>) -> bool { + use itertools::free::kmerge; + // sort the inputs + for input in &mut inputs { + input.sort(); + } + let mut merged = inputs.concat(); + merged.sort(); + itertools::equal(merged.into_iter(), kmerge(inputs)) + } + + // Any number of input iterators + fn equal_kmerge_by_ge(mut inputs: Vec<Vec<i16>>) -> bool { + // sort the inputs + for input in &mut inputs { + input.sort(); + input.reverse(); + } + let mut merged = inputs.concat(); + merged.sort(); + merged.reverse(); + itertools::equal(merged.into_iter(), + inputs.into_iter().kmerge_by(|x, y| x >= y)) + } + + // Any number of input iterators + fn equal_kmerge_by_lt(mut inputs: Vec<Vec<i16>>) -> bool { + // sort the inputs + for input in &mut inputs { + input.sort(); + } + let mut merged = inputs.concat(); + merged.sort(); + itertools::equal(merged.into_iter(), + inputs.into_iter().kmerge_by(|x, y| x < y)) + } + + // Any number of input iterators + fn equal_kmerge_by_le(mut inputs: Vec<Vec<i16>>) -> bool { + // sort the inputs + for input in &mut inputs { + input.sort(); + } + let mut merged = inputs.concat(); + merged.sort(); + itertools::equal(merged.into_iter(), + inputs.into_iter().kmerge_by(|x, y| x <= y)) + } + fn size_kmerge(a: Iter<i16>, b: Iter<i16>, c: Iter<i16>) -> bool { + use itertools::free::kmerge; + correct_size_hint(kmerge(vec![a, b, c])) + } + fn equal_zip_eq(a: Vec<i32>, b: Vec<i32>) -> bool { + let len = std::cmp::min(a.len(), b.len()); + let a = &a[..len]; + let b = &b[..len]; + itertools::equal(zip_eq(a, b), zip(a, b)) + } + fn size_zip_longest(a: Iter<i16, Exact>, b: Iter<i16, Exact>) -> bool { + let filt = a.clone().dedup(); + let filt2 = b.clone().dedup(); + correct_size_hint(filt.zip_longest(b.clone())) && + correct_size_hint(a.clone().zip_longest(filt2)) && + exact_size(a.zip_longest(b)) + } + fn size_2_zip_longest(a: Iter<i16>, b: Iter<i16>) -> bool { + let it = a.clone().zip_longest(b.clone()); + let jt = a.clone().zip_longest(b.clone()); + itertools::equal(a, + it.filter_map(|elt| match elt { + EitherOrBoth::Both(x, _) => Some(x), + EitherOrBoth::Left(x) => Some(x), + _ => None, + } + )) + && + itertools::equal(b, + jt.filter_map(|elt| match elt { + EitherOrBoth::Both(_, y) => Some(y), + EitherOrBoth::Right(y) => Some(y), + _ => None, + } + )) + } + fn size_interleave(a: Iter<i16>, b: Iter<i16>) -> bool { + correct_size_hint(a.interleave(b)) + } + fn exact_interleave(a: Iter<i16, Exact>, b: Iter<i16, Exact>) -> bool { + exact_size_for_this(a.interleave(b)) + } + fn size_interleave_shortest(a: Iter<i16>, b: Iter<i16>) -> bool { + correct_size_hint(a.interleave_shortest(b)) + } + fn exact_interleave_shortest(a: Vec<()>, b: Vec<()>) -> bool { + exact_size_for_this(a.iter().interleave_shortest(&b)) + } + fn size_intersperse(a: Iter<i16>, x: i16) -> bool { + correct_size_hint(a.intersperse(x)) + } + fn equal_intersperse(a: Vec<i32>, x: i32) -> bool { + let mut inter = false; + let mut i = 0; + for elt in a.iter().cloned().intersperse(x) { + if inter { + if elt != x { return false } + } else { + if elt != a[i] { return false } + i += 1; + } + inter = !inter; + } + true + } + + fn equal_combinations_2(a: Vec<u8>) -> bool { + let mut v = Vec::new(); + for (i, x) in enumerate(&a) { + for y in &a[i + 1..] { + v.push((x, y)); + } + } + itertools::equal(a.iter().tuple_combinations::<(_, _)>(), v) + } + + fn collect_tuple_matches_size(a: Iter<i16>) -> bool { + let size = a.clone().count(); + a.collect_tuple::<(_, _, _)>().is_some() == (size == 3) + } + + fn correct_permutations(vals: HashSet<i32>, k: usize) -> () { + // Test permutations only on iterators of distinct integers, to prevent + // false positives. + + const MAX_N: usize = 5; + + let n = min(vals.len(), MAX_N); + let vals: HashSet<i32> = vals.into_iter().take(n).collect(); + + let perms = vals.iter().permutations(k); + + let mut actual = HashSet::new(); + + for perm in perms { + assert_eq!(perm.len(), k); + + let all_items_valid = perm.iter().all(|p| vals.contains(p)); + assert!(all_items_valid, "perm contains value not from input: {:?}", perm); + + // Check that all perm items are distinct + let distinct_len = { + let perm_set: HashSet<_> = perm.iter().collect(); + perm_set.len() + }; + assert_eq!(perm.len(), distinct_len); + + // Check that the perm is new + assert!(actual.insert(perm.clone()), "perm already encountered: {:?}", perm); + } + } + + fn permutations_lexic_order(a: usize, b: usize) -> () { + let a = a % 6; + let b = b % 6; + + let n = max(a, b); + let k = min (a, b); + + let expected_first: Vec<usize> = (0..k).collect(); + let expected_last: Vec<usize> = ((n - k)..n).rev().collect(); + + let mut perms = (0..n).permutations(k); + + let mut curr_perm = match perms.next() { + Some(p) => p, + None => { return; } + }; + + assert_eq!(expected_first, curr_perm); + + for next_perm in perms { + assert!( + next_perm > curr_perm, + "next perm isn't greater-than current; next_perm={:?} curr_perm={:?} n={}", + next_perm, curr_perm, n + ); + + curr_perm = next_perm; + } + + assert_eq!(expected_last, curr_perm); + + } + + fn permutations_count(n: usize, k: usize) -> bool { + let n = n % 6; + + correct_count(|| (0..n).permutations(k)) + } + + fn permutations_size(a: Iter<i32>, k: usize) -> bool { + correct_size_hint(a.take(5).permutations(k)) + } + + fn permutations_k0_yields_once(n: usize) -> () { + let k = 0; + let expected: Vec<Vec<usize>> = vec![vec![]]; + let actual = (0..n).permutations(k).collect_vec(); + + assert_eq!(expected, actual); + } +} + +quickcheck! { + fn dedup_via_coalesce(a: Vec<i32>) -> bool { + let mut b = a.clone(); + b.dedup(); + itertools::equal( + &b, + a + .iter() + .coalesce(|x, y| { + if x==y { + Ok(x) + } else { + Err((x, y)) + } + }) + .fold(vec![], |mut v, n| { + v.push(n); + v + }) + ) + } +} + +quickcheck! { + fn equal_dedup(a: Vec<i32>) -> bool { + let mut b = a.clone(); + b.dedup(); + itertools::equal(&b, a.iter().dedup()) + } +} + +quickcheck! { + fn equal_dedup_by(a: Vec<(i32, i32)>) -> bool { + let mut b = a.clone(); + b.dedup_by(|x, y| x.0==y.0); + itertools::equal(&b, a.iter().dedup_by(|x, y| x.0==y.0)) + } +} + +quickcheck! { + fn size_dedup(a: Vec<i32>) -> bool { + correct_size_hint(a.iter().dedup()) + } +} + +quickcheck! { + fn size_dedup_by(a: Vec<(i32, i32)>) -> bool { + correct_size_hint(a.iter().dedup_by(|x, y| x.0==y.0)) + } +} + +quickcheck! { + fn exact_repeatn((n, x): (usize, i32)) -> bool { + let it = itertools::repeat_n(x, n); + exact_size(it) + } +} + +quickcheck! { + fn size_put_back(a: Vec<u8>, x: Option<u8>) -> bool { + let mut it = put_back(a.into_iter()); + match x { + Some(t) => it.put_back(t), + None => {} + } + correct_size_hint(it) + } +} + +quickcheck! { + fn size_put_backn(a: Vec<u8>, b: Vec<u8>) -> bool { + let mut it = put_back_n(a.into_iter()); + for elt in b { + it.put_back(elt) + } + correct_size_hint(it) + } +} + +quickcheck! { + fn size_tee(a: Vec<u8>) -> bool { + let (mut t1, mut t2) = a.iter().tee(); + t1.next(); + t1.next(); + t2.next(); + exact_size(t1) && exact_size(t2) + } +} + +quickcheck! { + fn size_tee_2(a: Vec<u8>) -> bool { + let (mut t1, mut t2) = a.iter().dedup().tee(); + t1.next(); + t1.next(); + t2.next(); + correct_size_hint(t1) && correct_size_hint(t2) + } +} + +quickcheck! { + fn size_take_while_ref(a: Vec<u8>, stop: u8) -> bool { + correct_size_hint(a.iter().take_while_ref(|x| **x != stop)) + } +} + +quickcheck! { + fn equal_partition(a: Vec<i32>) -> bool { + let mut a = a; + let mut ap = a.clone(); + let split_index = itertools::partition(&mut ap, |x| *x >= 0); + let parted = (0..split_index).all(|i| ap[i] >= 0) && + (split_index..a.len()).all(|i| ap[i] < 0); + + a.sort(); + ap.sort(); + parted && (a == ap) + } +} + +quickcheck! { + fn size_combinations(it: Iter<i16>) -> bool { + correct_size_hint(it.tuple_combinations::<(_, _)>()) + } +} + +quickcheck! { + fn equal_combinations(it: Iter<i16>) -> bool { + let values = it.clone().collect_vec(); + let mut cmb = it.tuple_combinations(); + for i in 0..values.len() { + for j in i+1..values.len() { + let pair = (values[i], values[j]); + if pair != cmb.next().unwrap() { + return false; + } + } + } + cmb.next() == None + } +} + +quickcheck! { + fn size_pad_tail(it: Iter<i8>, pad: u8) -> bool { + correct_size_hint(it.clone().pad_using(pad as usize, |_| 0)) && + correct_size_hint(it.dropping(1).rev().pad_using(pad as usize, |_| 0)) + } +} + +quickcheck! { + fn size_pad_tail2(it: Iter<i8, Exact>, pad: u8) -> bool { + exact_size(it.pad_using(pad as usize, |_| 0)) + } +} + +quickcheck! { + fn size_powerset(it: Iter<u8, Exact>) -> bool { + // Powerset cardinality gets large very quickly, limit input to keep test fast. + correct_size_hint(it.take(12).powerset()) + } +} + +quickcheck! { + fn size_duplicates(it: Iter<i8>) -> bool { + correct_size_hint(it.duplicates()) + } +} + +quickcheck! { + fn size_unique(it: Iter<i8>) -> bool { + correct_size_hint(it.unique()) + } + + fn count_unique(it: Vec<i8>, take_first: u8) -> () { + let answer = { + let mut v = it.clone(); + v.sort(); v.dedup(); + v.len() + }; + let mut iter = cloned(&it).unique(); + let first_count = (&mut iter).take(take_first as usize).count(); + let rest_count = iter.count(); + assert_eq!(answer, first_count + rest_count); + } +} + +quickcheck! { + fn fuzz_group_by_lazy_1(it: Iter<u8>) -> bool { + let jt = it.clone(); + let groups = it.group_by(|k| *k); + itertools::equal(jt, groups.into_iter().flat_map(|(_, x)| x)) + } +} + +quickcheck! { + fn fuzz_group_by_lazy_2(data: Vec<u8>) -> bool { + let groups = data.iter().group_by(|k| *k / 10); + let res = itertools::equal(data.iter(), groups.into_iter().flat_map(|(_, x)| x)); + res + } +} + +quickcheck! { + fn fuzz_group_by_lazy_3(data: Vec<u8>) -> bool { + let grouper = data.iter().group_by(|k| *k / 10); + let groups = grouper.into_iter().collect_vec(); + let res = itertools::equal(data.iter(), groups.into_iter().flat_map(|(_, x)| x)); + res + } +} + +quickcheck! { + fn fuzz_group_by_lazy_duo(data: Vec<u8>, order: Vec<(bool, bool)>) -> bool { + let grouper = data.iter().group_by(|k| *k / 3); + let mut groups1 = grouper.into_iter(); + let mut groups2 = grouper.into_iter(); + let mut elts = Vec::<&u8>::new(); + let mut old_groups = Vec::new(); + + let tup1 = |(_, b)| b; + for &(ord, consume_now) in &order { + let iter = &mut [&mut groups1, &mut groups2][ord as usize]; + match iter.next() { + Some((_, gr)) => if consume_now { + for og in old_groups.drain(..) { + elts.extend(og); + } + elts.extend(gr); + } else { + old_groups.push(gr); + }, + None => break, + } + } + for og in old_groups.drain(..) { + elts.extend(og); + } + for gr in groups1.map(&tup1) { elts.extend(gr); } + for gr in groups2.map(&tup1) { elts.extend(gr); } + itertools::assert_equal(&data, elts); + true + } +} + +quickcheck! { + fn equal_chunks_lazy(a: Vec<u8>, size: u8) -> bool { + let mut size = size; + if size == 0 { + size += 1; + } + let chunks = a.iter().chunks(size as usize); + let it = a.chunks(size as usize); + for (a, b) in chunks.into_iter().zip(it) { + if !itertools::equal(a, b) { + return false; + } + } + true + } +} + +quickcheck! { + fn equal_tuple_windows_1(a: Vec<u8>) -> bool { + let x = a.windows(1).map(|s| (&s[0], )); + let y = a.iter().tuple_windows::<(_,)>(); + itertools::equal(x, y) + } + + fn equal_tuple_windows_2(a: Vec<u8>) -> bool { + let x = a.windows(2).map(|s| (&s[0], &s[1])); + let y = a.iter().tuple_windows::<(_, _)>(); + itertools::equal(x, y) + } + + fn equal_tuple_windows_3(a: Vec<u8>) -> bool { + let x = a.windows(3).map(|s| (&s[0], &s[1], &s[2])); + let y = a.iter().tuple_windows::<(_, _, _)>(); + itertools::equal(x, y) + } + + fn equal_tuple_windows_4(a: Vec<u8>) -> bool { + let x = a.windows(4).map(|s| (&s[0], &s[1], &s[2], &s[3])); + let y = a.iter().tuple_windows::<(_, _, _, _)>(); + itertools::equal(x, y) + } + + fn equal_tuples_1(a: Vec<u8>) -> bool { + let x = a.chunks(1).map(|s| (&s[0], )); + let y = a.iter().tuples::<(_,)>(); + itertools::equal(x, y) + } + + fn equal_tuples_2(a: Vec<u8>) -> bool { + let x = a.chunks(2).filter(|s| s.len() == 2).map(|s| (&s[0], &s[1])); + let y = a.iter().tuples::<(_, _)>(); + itertools::equal(x, y) + } + + fn equal_tuples_3(a: Vec<u8>) -> bool { + let x = a.chunks(3).filter(|s| s.len() == 3).map(|s| (&s[0], &s[1], &s[2])); + let y = a.iter().tuples::<(_, _, _)>(); + itertools::equal(x, y) + } + + fn equal_tuples_4(a: Vec<u8>) -> bool { + let x = a.chunks(4).filter(|s| s.len() == 4).map(|s| (&s[0], &s[1], &s[2], &s[3])); + let y = a.iter().tuples::<(_, _, _, _)>(); + itertools::equal(x, y) + } + + fn exact_tuple_buffer(a: Vec<u8>) -> bool { + let mut iter = a.iter().tuples::<(_, _, _, _)>(); + (&mut iter).last(); + let buffer = iter.into_buffer(); + assert_eq!(buffer.len(), a.len() % 4); + exact_size(buffer) + } +} + +// with_position +quickcheck! { + fn with_position_exact_size_1(a: Vec<u8>) -> bool { + exact_size_for_this(a.iter().with_position()) + } + fn with_position_exact_size_2(a: Iter<u8, Exact>) -> bool { + exact_size_for_this(a.with_position()) + } +} + +quickcheck! { + fn correct_group_map_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + let count = a.len(); + let lookup = a.into_iter().map(|i| (i % modulo, i)).into_group_map(); + + assert_eq!(lookup.values().flat_map(|vals| vals.iter()).count(), count); + + for (&key, vals) in lookup.iter() { + assert!(vals.iter().all(|&val| val % modulo == key)); + } + } +} + +/// A peculiar type: Equality compares both tuple items, but ordering only the +/// first item. This is so we can check the stability property easily. +#[derive(Clone, Debug, PartialEq, Eq)] +struct Val(u32, u32); + +impl PartialOrd<Val> for Val { + fn partial_cmp(&self, other: &Val) -> Option<Ordering> { + self.0.partial_cmp(&other.0) + } +} + +impl Ord for Val { + fn cmp(&self, other: &Val) -> Ordering { + self.0.cmp(&other.0) + } +} + +impl qc::Arbitrary for Val { + fn arbitrary<G: qc::Gen>(g: &mut G) -> Self { + let (x, y) = <(u32, u32)>::arbitrary(g); + Val(x, y) + } + fn shrink(&self) -> Box<dyn Iterator<Item = Self>> { + Box::new((self.0, self.1).shrink().map(|(x, y)| Val(x, y))) + } +} + +quickcheck! { + fn minmax(a: Vec<Val>) -> bool { + use itertools::MinMaxResult; + + + let minmax = a.iter().minmax(); + let expected = match a.len() { + 0 => MinMaxResult::NoElements, + 1 => MinMaxResult::OneElement(&a[0]), + _ => MinMaxResult::MinMax(a.iter().min().unwrap(), + a.iter().max().unwrap()), + }; + minmax == expected + } +} + +quickcheck! { + fn minmax_f64(a: Vec<f64>) -> TestResult { + use itertools::MinMaxResult; + + if a.iter().any(|x| x.is_nan()) { + return TestResult::discard(); + } + + let min = cloned(&a).fold1(f64::min); + let max = cloned(&a).fold1(f64::max); + + let minmax = cloned(&a).minmax(); + let expected = match a.len() { + 0 => MinMaxResult::NoElements, + 1 => MinMaxResult::OneElement(min.unwrap()), + _ => MinMaxResult::MinMax(min.unwrap(), max.unwrap()), + }; + TestResult::from_bool(minmax == expected) + } +} + +quickcheck! { + #[allow(deprecated)] + fn tree_fold1_f64(mut a: Vec<f64>) -> TestResult { + fn collapse_adjacent<F>(x: Vec<f64>, mut f: F) -> Vec<f64> + where F: FnMut(f64, f64) -> f64 + { + let mut out = Vec::new(); + for i in (0..x.len()).step(2) { + if i == x.len()-1 { + out.push(x[i]) + } else { + out.push(f(x[i], x[i+1])); + } + } + out + } + + if a.iter().any(|x| x.is_nan()) { + return TestResult::discard(); + } + + let actual = a.iter().cloned().tree_fold1(f64::atan2); + + while a.len() > 1 { + a = collapse_adjacent(a, f64::atan2); + } + let expected = a.pop(); + + TestResult::from_bool(actual == expected) + } +} + +quickcheck! { + fn exactly_one_i32(a: Vec<i32>) -> TestResult { + let ret = a.iter().cloned().exactly_one(); + match a.len() { + 1 => TestResult::from_bool(ret.unwrap() == a[0]), + _ => TestResult::from_bool(ret.unwrap_err().eq(a.iter().cloned())), + } + } +} + +quickcheck! { + fn at_most_one_i32(a: Vec<i32>) -> TestResult { + let ret = a.iter().cloned().at_most_one(); + match a.len() { + 0 => TestResult::from_bool(ret.unwrap() == None), + 1 => TestResult::from_bool(ret.unwrap() == Some(a[0])), + _ => TestResult::from_bool(ret.unwrap_err().eq(a.iter().cloned())), + } + } +} + +quickcheck! { + fn consistent_grouping_map_with_by(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + + let lookup_grouping_map = a.iter().copied().map(|i| (i % modulo, i)).into_grouping_map().collect::<Vec<_>>(); + let lookup_grouping_map_by = a.iter().copied().into_grouping_map_by(|i| i % modulo).collect::<Vec<_>>(); + + assert_eq!(lookup_grouping_map, lookup_grouping_map_by); + } + + fn correct_grouping_map_by_aggregate_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo < 2 { 2 } else { modulo } as u64; // Avoid `% 0` + let lookup = a.iter() + .map(|&b| b as u64) // Avoid overflows + .into_grouping_map_by(|i| i % modulo) + .aggregate(|acc, &key, val| { + assert!(val % modulo == key); + if val % (modulo - 1) == 0 { + None + } else { + Some(acc.unwrap_or(0) + val) + } + }); + + let group_map_lookup = a.iter() + .map(|&b| b as u64) + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .filter_map(|(key, vals)| { + vals.into_iter().fold(None, |acc, val| { + if val % (modulo - 1) == 0 { + None + } else { + Some(acc.unwrap_or(0) + val) + } + }).map(|new_val| (key, new_val)) + }) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for m in 0..modulo { + assert_eq!( + lookup.get(&m).copied(), + a.iter() + .map(|&b| b as u64) + .filter(|&val| val % modulo == m) + .fold(None, |acc, val| { + if val % (modulo - 1) == 0 { + None + } else { + Some(acc.unwrap_or(0) + val) + } + }) + ); + } + } + + 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 + .into_grouping_map_by(|i| i % modulo) + .fold(0u64, |acc, &key, val| { + assert!(val % modulo == key); + acc + val + }); + + 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())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &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_first_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 + .into_grouping_map_by(|i| i % modulo) + .fold_first(|acc, &key, val| { + assert!(val % modulo == key); + acc + val + }); + + // TODO: Swap `fold1` with stdlib's `fold_first` when it's stabilized + 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().fold1(|acc, val| acc + val).unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &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_collect_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + let lookup_grouping_map = a.iter().copied().into_grouping_map_by(|i| i % modulo).collect::<Vec<_>>(); + let lookup_group_map = a.iter().copied().map(|i| (i % modulo, i)).into_group_map(); + + assert_eq!(lookup_grouping_map, lookup_group_map); + } + + fn correct_grouping_map_by_max_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).max(); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().max().unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &max) in lookup.iter() { + assert_eq!(Some(max), a.iter().copied().filter(|&val| val % modulo == key).max()); + } + } + + fn correct_grouping_map_by_max_by_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).max_by(|_, v1, v2| v1.cmp(v2)); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().max_by(|v1, v2| v1.cmp(v2)).unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &max) in lookup.iter() { + assert_eq!(Some(max), a.iter().copied().filter(|&val| val % modulo == key).max_by(|v1, v2| v1.cmp(v2))); + } + } + + fn correct_grouping_map_by_max_by_key_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).max_by_key(|_, &val| val); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().max_by_key(|&val| val).unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &max) in lookup.iter() { + 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(); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().min().unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &min) in lookup.iter() { + assert_eq!(Some(min), a.iter().copied().filter(|&val| val % modulo == key).min()); + } + } + + fn correct_grouping_map_by_min_by_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_by(|_, v1, v2| v1.cmp(v2)); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().min_by(|v1, v2| v1.cmp(v2)).unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &min) in lookup.iter() { + assert_eq!(Some(min), a.iter().copied().filter(|&val| val % modulo == key).min_by(|v1, v2| v1.cmp(v2))); + } + } + + fn correct_grouping_map_by_min_by_key_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_by_key(|_, &val| val); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().min_by_key(|&val| val).unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &min) in lookup.iter() { + 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(); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().minmax())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &minmax) in lookup.iter() { + assert_eq!(minmax, a.iter().copied().filter(|&val| val % modulo == key).minmax()); + } + } + + fn correct_grouping_map_by_minmax_by_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_by(|_, v1, v2| v1.cmp(v2)); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().minmax_by(|v1, v2| v1.cmp(v2)))) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &minmax) in lookup.iter() { + assert_eq!(minmax, a.iter().copied().filter(|&val| val % modulo == key).minmax_by(|v1, v2| v1.cmp(v2))); + } + } + + fn correct_grouping_map_by_minmax_by_key_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_by_key(|_, &val| val); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().minmax_by_key(|&val| val))) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &minmax) in lookup.iter() { + assert_eq!(minmax, a.iter().copied().filter(|&val| val % modulo == key).minmax_by_key(|&val| val)); + } + } + + fn correct_grouping_map_by_sum_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 + .into_grouping_map_by(|i| i % modulo) + .sum(); + + 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())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &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_product_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = Wrapping(if modulo == 0 { 1 } else { modulo } as u64); // Avoid `% 0` + let lookup = a.iter().map(|&b| Wrapping(b as u64)) // Avoid overflows + .into_grouping_map_by(|i| i % modulo) + .product(); + + let group_map_lookup = a.iter().map(|&b| Wrapping(b as u64)) + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().product::<Wrapping<u64>>())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &prod) in lookup.iter() { + assert_eq!( + prod, + a.iter() + .map(|&b| Wrapping(b as u64)) + .filter(|&val| val % modulo == key) + .product::<Wrapping<u64>>() + ); + } + } + + // This should check that if multiple elements are equally minimum or maximum + // then `max`, `min` and `minmax` pick the first minimum and the last maximum. + // This is to be consistent with `std::iter::max` and `std::iter::min`. + fn correct_grouping_map_by_min_max_minmax_order_modulo_key() -> () { + use itertools::MinMaxResult; + + let lookup = (0..=10) + .into_grouping_map_by(|_| 0) + .max_by(|_, _, _| Ordering::Equal); + + assert_eq!(lookup[&0], 10); + + let lookup = (0..=10) + .into_grouping_map_by(|_| 0) + .min_by(|_, _, _| Ordering::Equal); + + assert_eq!(lookup[&0], 0); + + let lookup = (0..=10) + .into_grouping_map_by(|_| 0) + .minmax_by(|_, _, _| Ordering::Equal); + + assert_eq!(lookup[&0], MinMaxResult::MinMax(0, 10)); + } +} + +quickcheck! { + fn counts(nums: Vec<isize>) -> TestResult { + let counts = nums.iter().counts(); + for (&item, &count) in counts.iter() { + #[allow(clippy::absurd_extreme_comparisons)] + if count <= 0 { + return TestResult::failed(); + } + if count != nums.iter().filter(|&x| x == item).count() { + return TestResult::failed(); + } + } + for item in nums.iter() { + if !counts.contains_key(item) { + return TestResult::failed(); + } + } + TestResult::passed() + } +} + +quickcheck! { + fn test_double_ended_zip_2(a: Vec<u8>, b: Vec<u8>) -> TestResult { + let mut x = + multizip((a.clone().into_iter(), b.clone().into_iter())) + .collect_vec(); + x.reverse(); + + let y = + multizip((a.into_iter(), b.into_iter())) + .rfold(Vec::new(), |mut vec, e| { vec.push(e); vec }); + + TestResult::from_bool(itertools::equal(x, y)) + } + + fn test_double_ended_zip_3(a: Vec<u8>, b: Vec<u8>, c: Vec<u8>) -> TestResult { + let mut x = + multizip((a.clone().into_iter(), b.clone().into_iter(), c.clone().into_iter())) + .collect_vec(); + x.reverse(); + + let y = + multizip((a.into_iter(), b.into_iter(), c.into_iter())) + .rfold(Vec::new(), |mut vec, e| { vec.push(e); vec }); + + TestResult::from_bool(itertools::equal(x, y)) + } +} + + +fn is_fused<I: Iterator>(mut it: I) -> bool +{ + for _ in it.by_ref() {} + for _ in 0..10{ + if it.next().is_some(){ + return false; + } + } + true +} + +quickcheck! { + fn fused_combination(a: Iter<i16>) -> bool + { + is_fused(a.clone().combinations(1)) && + is_fused(a.combinations(3)) + } + + fn fused_combination_with_replacement(a: Iter<i16>) -> bool + { + is_fused(a.clone().combinations_with_replacement(1)) && + is_fused(a.combinations_with_replacement(3)) + } + + fn fused_tuple_combination(a: Iter<i16>) -> bool + { + is_fused(a.clone().fuse().tuple_combinations::<(_,)>()) && + is_fused(a.fuse().tuple_combinations::<(_,_,_)>()) + } + + fn fused_unique(a: Iter<i16>) -> bool + { + is_fused(a.fuse().unique()) + } + + fn fused_unique_by(a: Iter<i16>) -> bool + { + is_fused(a.fuse().unique_by(|x| x % 100)) + } + + fn fused_interleave_shortest(a: Iter<i16>, b: Iter<i16>) -> bool + { + !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())) + } + + fn fused_merge(a: Iter<i16>, b: Iter<i16>) -> bool + { + is_fused(a.fuse().merge(b.fuse())) + } + + fn fused_filter_ok(a: Iter<i16>) -> bool + { + is_fused(a.map(|x| if x % 2 == 0 {Ok(x)} else {Err(x)} ) + .filter_ok(|x| x % 3 == 0) + .fuse()) + } + + fn fused_filter_map_ok(a: Iter<i16>) -> bool + { + is_fused(a.map(|x| if x % 2 == 0 {Ok(x)} else {Err(x)} ) + .filter_map_ok(|x| if x % 3 == 0 {Some(x / 3)} else {None}) + .fuse()) + } + + fn fused_positions(a: Iter<i16>) -> bool + { + !is_fused(a.clone().positions(|x|x%2==0)) && + is_fused(a.fuse().positions(|x|x%2==0)) + } + + fn fused_update(a: Iter<i16>) -> bool + { + !is_fused(a.clone().update(|x|*x+=1)) && + is_fused(a.fuse().update(|x|*x+=1)) + } + + fn fused_tuple_windows(a: Iter<i16>) -> bool + { + is_fused(a.fuse().tuple_windows::<(_,_)>()) + } + + fn fused_pad_using(a: Iter<i16>) -> bool + { + is_fused(a.fuse().pad_using(100,|_|0)) + } +} + +quickcheck! { + fn min_set_contains_min(a: Vec<(usize, char)>) -> bool { + let result_set = a.iter().min_set(); + if let Some(result_element) = a.iter().min() { + result_set.contains(&result_element) + } else { + result_set.is_empty() + } + } + + fn min_set_by_contains_min(a: Vec<(usize, char)>) -> bool { + let compare = |x: &&(usize, char), y: &&(usize, char)| x.1.cmp(&y.1); + let result_set = a.iter().min_set_by(compare); + if let Some(result_element) = a.iter().min_by(compare) { + result_set.contains(&result_element) + } else { + result_set.is_empty() + } + } + + fn min_set_by_key_contains_min(a: Vec<(usize, char)>) -> bool { + let key = |x: &&(usize, char)| x.1; + let result_set = a.iter().min_set_by_key(&key); + if let Some(result_element) = a.iter().min_by_key(&key) { + result_set.contains(&result_element) + } else { + result_set.is_empty() + } + } + + fn max_set_contains_max(a: Vec<(usize, char)>) -> bool { + let result_set = a.iter().max_set(); + if let Some(result_element) = a.iter().max() { + result_set.contains(&result_element) + } else { + result_set.is_empty() + } + } + + fn max_set_by_contains_max(a: Vec<(usize, char)>) -> bool { + let compare = |x: &&(usize, char), y: &&(usize, char)| x.1.cmp(&y.1); + let result_set = a.iter().max_set_by(compare); + if let Some(result_element) = a.iter().max_by(compare) { + result_set.contains(&result_element) + } else { + result_set.is_empty() + } + } + + fn max_set_by_key_contains_max(a: Vec<(usize, char)>) -> bool { + let key = |x: &&(usize, char)| x.1; + let result_set = a.iter().max_set_by_key(&key); + if let Some(result_element) = a.iter().max_by_key(&key) { + result_set.contains(&result_element) + } else { + result_set.is_empty() + } + } +} diff --git a/third_party/rust/itertools/tests/specializations.rs b/third_party/rust/itertools/tests/specializations.rs new file mode 100644 index 0000000000..057e11c9f6 --- /dev/null +++ b/third_party/rust/itertools/tests/specializations.rs @@ -0,0 +1,153 @@ +use itertools::Itertools; +use std::fmt::Debug; +use quickcheck::quickcheck; + +struct Unspecialized<I>(I); +impl<I> Iterator for Unspecialized<I> +where + I: Iterator, +{ + type Item = I::Item; + + #[inline(always)] + fn next(&mut self) -> Option<Self::Item> { + self.0.next() + } +} + +macro_rules! check_specialized { + ($src:expr, |$it:pat| $closure:expr) => { + let $it = $src.clone(); + let v1 = $closure; + + let $it = Unspecialized($src.clone()); + let v2 = $closure; + + assert_eq!(v1, v2); + } +} + +fn test_specializations<IterItem, Iter>( + it: &Iter, +) where + IterItem: Eq + Debug + Clone, + Iter: Iterator<Item = IterItem> + Clone, +{ + check_specialized!(it, |i| i.count()); + check_specialized!(it, |i| i.last()); + check_specialized!(it, |i| i.collect::<Vec<_>>()); + check_specialized!(it, |i| { + let mut parameters_from_fold = vec![]; + let fold_result = i.fold(vec![], |mut acc, v: IterItem| { + parameters_from_fold.push((acc.clone(), v.clone())); + acc.push(v); + acc + }); + (parameters_from_fold, fold_result) + }); + check_specialized!(it, |mut i| { + let mut parameters_from_all = vec![]; + let first = i.next(); + let all_result = i.all(|x| { + parameters_from_all.push(x.clone()); + Some(x)==first + }); + (parameters_from_all, all_result) + }); + let size = it.clone().count(); + for n in 0..size + 2 { + check_specialized!(it, |mut i| i.nth(n)); + } + // size_hint is a bit harder to check + let mut it_sh = it.clone(); + for n in 0..size + 2 { + let len = it_sh.clone().count(); + let (min, max) = it_sh.size_hint(); + assert_eq!(size - n.min(size), len); + assert!(min <= len); + if let Some(max) = max { + assert!(len <= max); + } + it_sh.next(); + } +} + +quickcheck! { + fn intersperse(v: Vec<u8>) -> () { + test_specializations(&v.into_iter().intersperse(0)); + } +} + +quickcheck! { + fn put_back_qc(test_vec: Vec<i32>) -> () { + test_specializations(&itertools::put_back(test_vec.iter())); + let mut pb = itertools::put_back(test_vec.into_iter()); + pb.put_back(1); + test_specializations(&pb); + } +} + +quickcheck! { + fn merge_join_by_qc(i1: Vec<usize>, i2: Vec<usize>) -> () { + test_specializations(&i1.into_iter().merge_join_by(i2.into_iter(), std::cmp::Ord::cmp)); + } +} + +quickcheck! { + fn map_into(v: Vec<u8>) -> () { + test_specializations(&v.into_iter().map_into::<u32>()); + } +} + +quickcheck! { + fn map_ok(v: Vec<Result<u8, char>>) -> () { + test_specializations(&v.into_iter().map_ok(|u| u.checked_add(1))); + } +} + +quickcheck! { + fn process_results(v: Vec<Result<u8, u8>>) -> () { + helper(v.iter().copied()); + helper(v.iter().copied().filter(Result::is_ok)); + + fn helper(it: impl Iterator<Item = Result<u8, u8>> + Clone) { + macro_rules! check_results_specialized { + ($src:expr, |$it:pat| $closure:expr) => { + assert_eq!( + itertools::process_results($src.clone(), |$it| $closure), + itertools::process_results($src.clone(), |i| { + let $it = Unspecialized(i); + $closure + }), + ) + } + } + + check_results_specialized!(it, |i| i.count()); + check_results_specialized!(it, |i| i.last()); + check_results_specialized!(it, |i| i.collect::<Vec<_>>()); + check_results_specialized!(it, |i| { + let mut parameters_from_fold = vec![]; + let fold_result = i.fold(vec![], |mut acc, v| { + parameters_from_fold.push((acc.clone(), v)); + acc.push(v); + acc + }); + (parameters_from_fold, fold_result) + }); + check_results_specialized!(it, |mut i| { + let mut parameters_from_all = vec![]; + let first = i.next(); + let all_result = i.all(|x| { + parameters_from_all.push(x); + Some(x)==first + }); + (parameters_from_all, all_result) + }); + let size = it.clone().count(); + for n in 0..size + 2 { + check_results_specialized!(it, |mut i| i.nth(n)); + } + } + } +} diff --git a/third_party/rust/itertools/tests/test_core.rs b/third_party/rust/itertools/tests/test_core.rs new file mode 100644 index 0000000000..df94eb665f --- /dev/null +++ b/third_party/rust/itertools/tests/test_core.rs @@ -0,0 +1,317 @@ +//! Licensed under the Apache License, Version 2.0 +//! https://www.apache.org/licenses/LICENSE-2.0 or the MIT license +//! https://opensource.org/licenses/MIT, at your +//! option. This file may not be copied, modified, or distributed +//! except according to those terms. +#![no_std] + +use core::iter; +use itertools as it; +use crate::it::Itertools; +use crate::it::interleave; +use crate::it::intersperse; +use crate::it::intersperse_with; +use crate::it::multizip; +use crate::it::free::put_back; +use crate::it::iproduct; +use crate::it::izip; +use crate::it::chain; + +#[test] +fn product2() { + let s = "αβ"; + + let mut prod = iproduct!(s.chars(), 0..2); + assert!(prod.next() == Some(('α', 0))); + assert!(prod.next() == Some(('α', 1))); + assert!(prod.next() == Some(('β', 0))); + assert!(prod.next() == Some(('β', 1))); + assert!(prod.next() == None); +} + +#[test] +fn product_temporary() { + for (_x, _y, _z) in iproduct!( + [0, 1, 2].iter().cloned(), + [0, 1, 2].iter().cloned(), + [0, 1, 2].iter().cloned()) + { + // ok + } +} + + +#[test] +fn izip_macro() { + let mut zip = izip!(2..3); + assert!(zip.next() == Some(2)); + assert!(zip.next().is_none()); + + let mut zip = izip!(0..3, 0..2, 0..2i8); + for i in 0..2 { + assert!((i as usize, i, i as i8) == zip.next().unwrap()); + } + assert!(zip.next().is_none()); + + let xs: [isize; 0] = []; + let mut zip = izip!(0..3, 0..2, 0..2i8, &xs); + assert!(zip.next().is_none()); +} + +#[test] +fn izip2() { + let _zip1: iter::Zip<_, _> = izip!(1.., 2..); + let _zip2: iter::Zip<_, _> = izip!(1.., 2.., ); +} + +#[test] +fn izip3() { + let mut zip: iter::Map<iter::Zip<_, _>, _> = izip!(0..3, 0..2, 0..2i8); + for i in 0..2 { + assert!((i as usize, i, i as i8) == zip.next().unwrap()); + } + assert!(zip.next().is_none()); +} + +#[test] +fn multizip3() { + let mut zip = multizip((0..3, 0..2, 0..2i8)); + for i in 0..2 { + assert!((i as usize, i, i as i8) == zip.next().unwrap()); + } + assert!(zip.next().is_none()); + + let xs: [isize; 0] = []; + let mut zip = multizip((0..3, 0..2, 0..2i8, xs.iter())); + assert!(zip.next().is_none()); + + for (_, _, _, _, _) in multizip((0..3, 0..2, xs.iter(), &xs, xs.to_vec())) { + /* test compiles */ + } +} + +#[test] +fn chain_macro() { + let mut chain = chain!(2..3); + assert!(chain.next() == Some(2)); + assert!(chain.next().is_none()); + + let mut chain = chain!(0..2, 2..3, 3..5i8); + for i in 0..5i8 { + assert_eq!(Some(i), chain.next()); + } + assert!(chain.next().is_none()); + + let mut chain = chain!(); + assert_eq!(chain.next(), Option::<()>::None); +} + +#[test] +fn chain2() { + let _ = chain!(1.., 2..); + let _ = chain!(1.., 2.., ); +} + +#[test] +fn write_to() { + let xs = [7, 9, 8]; + let mut ys = [0; 5]; + let cnt = ys.iter_mut().set_from(xs.iter().copied()); + assert!(cnt == xs.len()); + assert!(ys == [7, 9, 8, 0, 0]); + + let cnt = ys.iter_mut().set_from(0..10); + assert!(cnt == ys.len()); + assert!(ys == [0, 1, 2, 3, 4]); +} + +#[test] +fn test_interleave() { + let xs: [u8; 0] = []; + let ys = [7u8, 9, 8, 10]; + let zs = [2u8, 77]; + let it = interleave(xs.iter(), ys.iter()); + it::assert_equal(it, ys.iter()); + + let rs = [7u8, 2, 9, 77, 8, 10]; + let it = interleave(ys.iter(), zs.iter()); + it::assert_equal(it, rs.iter()); +} + +#[test] +fn test_intersperse() { + let xs = [1u8, 2, 3]; + let ys = [1u8, 0, 2, 0, 3]; + let it = intersperse(&xs, &0); + it::assert_equal(it, ys.iter()); +} + +#[test] +fn test_intersperse_with() { + let xs = [1u8, 2, 3]; + let ys = [1u8, 10, 2, 10, 3]; + let i = 10; + let it = intersperse_with(&xs, || &i); + it::assert_equal(it, ys.iter()); +} + +#[allow(deprecated)] +#[test] +fn foreach() { + let xs = [1i32, 2, 3]; + let mut sum = 0; + xs.iter().foreach(|elt| sum += *elt); + assert!(sum == 6); +} + +#[test] +fn dropping() { + let xs = [1, 2, 3]; + let mut it = xs.iter().dropping(2); + assert_eq!(it.next(), Some(&3)); + assert!(it.next().is_none()); + let mut it = xs.iter().dropping(5); + assert!(it.next().is_none()); +} + +#[test] +fn batching() { + let xs = [0, 1, 2, 1, 3]; + let ys = [(0, 1), (2, 1)]; + + // An iterator that gathers elements up in pairs + let pit = xs + .iter() + .cloned() + .batching(|it| it.next().and_then(|x| it.next().map(|y| (x, y)))); + it::assert_equal(pit, ys.iter().cloned()); +} + +#[test] +fn test_put_back() { + let xs = [0, 1, 1, 1, 2, 1, 3, 3]; + let mut pb = put_back(xs.iter().cloned()); + pb.next(); + pb.put_back(1); + pb.put_back(0); + it::assert_equal(pb, xs.iter().cloned()); +} + +#[allow(deprecated)] +#[test] +fn step() { + it::assert_equal((0..10).step(1), 0..10); + it::assert_equal((0..10).step(2), (0..10).filter(|x: &i32| *x % 2 == 0)); + it::assert_equal((0..10).step(10), 0..1); +} + +#[allow(deprecated)] +#[test] +fn merge() { + it::assert_equal((0..10).step(2).merge((1..10).step(2)), 0..10); +} + + +#[test] +fn repeatn() { + let s = "α"; + let mut it = it::repeat_n(s, 3); + assert_eq!(it.len(), 3); + assert_eq!(it.next(), Some(s)); + assert_eq!(it.next(), Some(s)); + assert_eq!(it.next(), Some(s)); + assert_eq!(it.next(), None); + assert_eq!(it.next(), None); +} + +#[test] +fn count_clones() { + // Check that RepeatN only clones N - 1 times. + + use core::cell::Cell; + #[derive(PartialEq, Debug)] + struct Foo { + n: Cell<usize> + } + + impl Clone for Foo + { + fn clone(&self) -> Self + { + let n = self.n.get(); + self.n.set(n + 1); + Foo { n: Cell::new(n + 1) } + } + } + + + for n in 0..10 { + let f = Foo{n: Cell::new(0)}; + let it = it::repeat_n(f, n); + // drain it + let last = it.last(); + if n == 0 { + assert_eq!(last, None); + } else { + assert_eq!(last, Some(Foo{n: Cell::new(n - 1)})); + } + } +} + +#[test] +fn part() { + let mut data = [7, 1, 1, 9, 1, 1, 3]; + let i = it::partition(&mut data, |elt| *elt >= 3); + assert_eq!(i, 3); + assert_eq!(data, [7, 3, 9, 1, 1, 1, 1]); + + let i = it::partition(&mut data, |elt| *elt == 1); + assert_eq!(i, 4); + assert_eq!(data, [1, 1, 1, 1, 9, 3, 7]); + + let mut data = [1, 2, 3, 4, 5, 6, 7, 8, 9]; + let i = it::partition(&mut data, |elt| *elt % 3 == 0); + assert_eq!(i, 3); + assert_eq!(data, [9, 6, 3, 4, 5, 2, 7, 8, 1]); +} + +#[test] +fn tree_fold1() { + for i in 0..100 { + assert_eq!((0..i).tree_fold1(|x, y| x + y), (0..i).fold1(|x, y| x + y)); + } +} + +#[test] +fn exactly_one() { + assert_eq!((0..10).filter(|&x| x == 2).exactly_one().unwrap(), 2); + assert!((0..10).filter(|&x| x > 1 && x < 4).exactly_one().unwrap_err().eq(2..4)); + assert!((0..10).filter(|&x| x > 1 && x < 5).exactly_one().unwrap_err().eq(2..5)); + assert!((0..10).filter(|&_| false).exactly_one().unwrap_err().eq(0..0)); +} + +#[test] +fn at_most_one() { + assert_eq!((0..10).filter(|&x| x == 2).at_most_one().unwrap(), Some(2)); + assert!((0..10).filter(|&x| x > 1 && x < 4).at_most_one().unwrap_err().eq(2..4)); + assert!((0..10).filter(|&x| x > 1 && x < 5).at_most_one().unwrap_err().eq(2..5)); + assert_eq!((0..10).filter(|&_| false).at_most_one().unwrap(), None); +} + +#[test] +fn sum1() { + let v: &[i32] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; + assert_eq!(v[..0].iter().cloned().sum1::<i32>(), None); + assert_eq!(v[1..2].iter().cloned().sum1::<i32>(), Some(1)); + assert_eq!(v[1..3].iter().cloned().sum1::<i32>(), Some(3)); + assert_eq!(v.iter().cloned().sum1::<i32>(), Some(55)); +} + +#[test] +fn product1() { + let v: &[i32] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; + assert_eq!(v[..0].iter().cloned().product1::<i32>(), None); + assert_eq!(v[..1].iter().cloned().product1::<i32>(), Some(0)); + assert_eq!(v[1..3].iter().cloned().product1::<i32>(), Some(2)); + assert_eq!(v[1..5].iter().cloned().product1::<i32>(), Some(24)); +} diff --git a/third_party/rust/itertools/tests/test_std.rs b/third_party/rust/itertools/tests/test_std.rs new file mode 100644 index 0000000000..f590342349 --- /dev/null +++ b/third_party/rust/itertools/tests/test_std.rs @@ -0,0 +1,1168 @@ +use quickcheck as qc; +use rand::{distributions::{Distribution, Standard}, Rng, SeedableRng, rngs::StdRng}; +use rand::{seq::SliceRandom, thread_rng}; +use std::{cmp::min, fmt::Debug, marker::PhantomData}; +use itertools as it; +use crate::it::Itertools; +use crate::it::ExactlyOneError; +use crate::it::multizip; +use crate::it::multipeek; +use crate::it::peek_nth; +use crate::it::free::rciter; +use crate::it::free::put_back_n; +use crate::it::FoldWhile; +use crate::it::cloned; +use crate::it::iproduct; +use crate::it::izip; + +#[test] +fn product3() { + let prod = iproduct!(0..3, 0..2, 0..2); + assert_eq!(prod.size_hint(), (12, Some(12))); + let v = prod.collect_vec(); + for i in 0..3 { + for j in 0..2 { + for k in 0..2 { + assert!((i, j, k) == v[(i * 2 * 2 + j * 2 + k) as usize]); + } + } + } + for (_, _, _, _) in iproduct!(0..3, 0..2, 0..2, 0..3) { + /* test compiles */ + } +} + +#[test] +fn interleave_shortest() { + let v0: Vec<i32> = vec![0, 2, 4]; + let v1: Vec<i32> = vec![1, 3, 5, 7]; + let it = v0.into_iter().interleave_shortest(v1.into_iter()); + assert_eq!(it.size_hint(), (6, Some(6))); + assert_eq!(it.collect_vec(), vec![0, 1, 2, 3, 4, 5]); + + let v0: Vec<i32> = vec![0, 2, 4, 6, 8]; + let v1: Vec<i32> = vec![1, 3, 5]; + let it = v0.into_iter().interleave_shortest(v1.into_iter()); + assert_eq!(it.size_hint(), (7, Some(7))); + assert_eq!(it.collect_vec(), vec![0, 1, 2, 3, 4, 5, 6]); + + let i0 = ::std::iter::repeat(0); + let v1: Vec<_> = vec![1, 3, 5]; + let it = i0.interleave_shortest(v1.into_iter()); + assert_eq!(it.size_hint(), (7, Some(7))); + + let v0: Vec<_> = vec![0, 2, 4]; + let i1 = ::std::iter::repeat(1); + let it = v0.into_iter().interleave_shortest(i1); + assert_eq!(it.size_hint(), (6, Some(6))); +} + +#[test] +fn duplicates_by() { + let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"]; + let ys = ["aa", "bbbb", "cccc"]; + it::assert_equal(ys.iter(), xs.iter().duplicates_by(|x| x[..2].to_string())); + it::assert_equal(ys.iter(), xs.iter().rev().duplicates_by(|x| x[..2].to_string()).rev()); + let ys_rev = ["ccc", "aa", "bbbbb"]; + it::assert_equal(ys_rev.iter(), xs.iter().duplicates_by(|x| x[..2].to_string()).rev()); +} + +#[test] +fn duplicates() { + let xs = [0, 1, 2, 3, 2, 1, 3]; + let ys = [2, 1, 3]; + it::assert_equal(ys.iter(), xs.iter().duplicates()); + it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev()); + let ys_rev = [3, 2, 1]; + it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev()); + + let xs = [0, 1, 0, 1]; + let ys = [0, 1]; + it::assert_equal(ys.iter(), xs.iter().duplicates()); + it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev()); + let ys_rev = [1, 0]; + it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev()); + + let xs = vec![0, 1, 2, 1, 2]; + let ys = vec![1, 2]; + assert_eq!(ys, xs.iter().duplicates().cloned().collect_vec()); + assert_eq!(ys, xs.iter().rev().duplicates().rev().cloned().collect_vec()); + let ys_rev = vec![2, 1]; + assert_eq!(ys_rev, xs.iter().duplicates().rev().cloned().collect_vec()); +} + +#[test] +fn unique_by() { + let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"]; + let ys = ["aaa", "bbbbb", "ccc"]; + it::assert_equal(ys.iter(), xs.iter().unique_by(|x| x[..2].to_string())); + it::assert_equal(ys.iter(), xs.iter().rev().unique_by(|x| x[..2].to_string()).rev()); + let ys_rev = ["cccc", "aaaaa", "bbbb"]; + it::assert_equal(ys_rev.iter(), xs.iter().unique_by(|x| x[..2].to_string()).rev()); +} + +#[test] +fn unique() { + let xs = [0, 1, 2, 3, 2, 1, 3]; + let ys = [0, 1, 2, 3]; + it::assert_equal(ys.iter(), xs.iter().unique()); + it::assert_equal(ys.iter(), xs.iter().rev().unique().rev()); + let ys_rev = [3, 1, 2, 0]; + it::assert_equal(ys_rev.iter(), xs.iter().unique().rev()); + + let xs = [0, 1]; + let ys = [0, 1]; + it::assert_equal(ys.iter(), xs.iter().unique()); + it::assert_equal(ys.iter(), xs.iter().rev().unique().rev()); + let ys_rev = [1, 0]; + it::assert_equal(ys_rev.iter(), xs.iter().unique().rev()); +} + +#[test] +fn intersperse() { + let xs = ["a", "", "b", "c"]; + let v: Vec<&str> = xs.iter().cloned().intersperse(", ").collect(); + let text: String = v.concat(); + assert_eq!(text, "a, , b, c".to_string()); + + let ys = [0, 1, 2, 3]; + let mut it = ys[..0].iter().copied().intersperse(1); + assert!(it.next() == None); +} + +#[test] +fn dedup() { + let xs = [0, 1, 1, 1, 2, 1, 3, 3]; + let ys = [0, 1, 2, 1, 3]; + it::assert_equal(ys.iter(), xs.iter().dedup()); + let xs = [0, 0, 0, 0, 0]; + let ys = [0]; + it::assert_equal(ys.iter(), xs.iter().dedup()); + + let xs = [0, 1, 1, 1, 2, 1, 3, 3]; + let ys = [0, 1, 2, 1, 3]; + let mut xs_d = Vec::new(); + xs.iter().dedup().fold((), |(), &elt| xs_d.push(elt)); + assert_eq!(&xs_d, &ys); +} + +#[test] +fn coalesce() { + let data = vec![-1., -2., -3., 3., 1., 0., -1.]; + let it = data.iter().cloned().coalesce(|x, y| + if (x >= 0.) == (y >= 0.) { + Ok(x + y) + } else { + Err((x, y)) + } + ); + itertools::assert_equal(it.clone(), vec![-6., 4., -1.]); + assert_eq!( + it.fold(vec![], |mut v, n| { + v.push(n); + v + }), + vec![-6., 4., -1.] + ); +} + +#[test] +fn dedup_by() { + let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)]; + let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)]; + it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.1==y.1)); + let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]; + let ys = [(0, 1)]; + it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.0==y.0)); + + let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)]; + let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)]; + let mut xs_d = Vec::new(); + xs.iter().dedup_by(|x, y| x.1==y.1).fold((), |(), &elt| xs_d.push(elt)); + assert_eq!(&xs_d, &ys); +} + +#[test] +fn dedup_with_count() { + let xs: [i32; 8] = [0, 1, 1, 1, 2, 1, 3, 3]; + let ys: [(usize, &i32); 5] = [(1, &0), (3, &1), (1, &2), (1, &1), (2, &3)]; + + it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count()); + + let xs: [i32; 5] = [0, 0, 0, 0, 0]; + let ys: [(usize, &i32); 1] = [(5, &0)]; + + it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count()); +} + + +#[test] +fn dedup_by_with_count() { + let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)]; + let ys = [(1, &(0, 0)), (3, &(0, 1)), (1, &(0, 2)), (1, &(3, 1)), (2, &(0, 3))]; + + it::assert_equal(ys.iter().cloned(), xs.iter().dedup_by_with_count(|x, y| x.1==y.1)); + + let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]; + let ys = [( 5, &(0, 1))]; + + it::assert_equal(ys.iter().cloned(), xs.iter().dedup_by_with_count(|x, y| x.0==y.0)); +} + +#[test] +fn all_equal() { + assert!("".chars().all_equal()); + assert!("A".chars().all_equal()); + assert!(!"AABBCCC".chars().all_equal()); + assert!("AAAAAAA".chars().all_equal()); + for (_key, mut sub) in &"AABBCCC".chars().group_by(|&x| x) { + assert!(sub.all_equal()); + } +} + +#[test] +fn all_unique() { + assert!("ABCDEFGH".chars().all_unique()); + assert!(!"ABCDEFGA".chars().all_unique()); + assert!(::std::iter::empty::<usize>().all_unique()); +} + +#[test] +fn test_put_back_n() { + let xs = [0, 1, 1, 1, 2, 1, 3, 3]; + let mut pb = put_back_n(xs.iter().cloned()); + pb.next(); + pb.next(); + pb.put_back(1); + pb.put_back(0); + it::assert_equal(pb, xs.iter().cloned()); +} + +#[test] +fn tee() { + let xs = [0, 1, 2, 3]; + let (mut t1, mut t2) = xs.iter().cloned().tee(); + assert_eq!(t1.next(), Some(0)); + assert_eq!(t2.next(), Some(0)); + assert_eq!(t1.next(), Some(1)); + assert_eq!(t1.next(), Some(2)); + assert_eq!(t1.next(), Some(3)); + assert_eq!(t1.next(), None); + assert_eq!(t2.next(), Some(1)); + assert_eq!(t2.next(), Some(2)); + assert_eq!(t1.next(), None); + assert_eq!(t2.next(), Some(3)); + assert_eq!(t2.next(), None); + assert_eq!(t1.next(), None); + assert_eq!(t2.next(), None); + + let (t1, t2) = xs.iter().cloned().tee(); + it::assert_equal(t1, xs.iter().cloned()); + it::assert_equal(t2, xs.iter().cloned()); + + let (t1, t2) = xs.iter().cloned().tee(); + it::assert_equal(t1.zip(t2), xs.iter().cloned().zip(xs.iter().cloned())); +} + + +#[test] +fn test_rciter() { + let xs = [0, 1, 1, 1, 2, 1, 3, 5, 6]; + + let mut r1 = rciter(xs.iter().cloned()); + let mut r2 = r1.clone(); + assert_eq!(r1.next(), Some(0)); + assert_eq!(r2.next(), Some(1)); + let mut z = r1.zip(r2); + assert_eq!(z.next(), Some((1, 1))); + assert_eq!(z.next(), Some((2, 1))); + assert_eq!(z.next(), Some((3, 5))); + assert_eq!(z.next(), None); + + // test intoiterator + let r1 = rciter(0..5); + let mut z = izip!(&r1, r1); + assert_eq!(z.next(), Some((0, 1))); +} + +#[allow(deprecated)] +#[test] +fn trait_pointers() { + struct ByRef<'r, I: ?Sized>(&'r mut I) ; + + impl<'r, X, I: ?Sized> Iterator for ByRef<'r, I> where + I: 'r + Iterator<Item=X> + { + type Item = X; + fn next(&mut self) -> Option<Self::Item> + { + self.0.next() + } + } + + let mut it = Box::new(0..10) as Box<dyn Iterator<Item=i32>>; + assert_eq!(it.next(), Some(0)); + + { + /* make sure foreach works on non-Sized */ + let jt: &mut dyn Iterator<Item = i32> = &mut *it; + assert_eq!(jt.next(), Some(1)); + + { + let mut r = ByRef(jt); + assert_eq!(r.next(), Some(2)); + } + + assert_eq!(jt.find_position(|x| *x == 4), Some((1, 4))); + jt.foreach(|_| ()); + } +} + +#[test] +fn merge_by() { + let odd : Vec<(u32, &str)> = vec![(1, "hello"), (3, "world"), (5, "!")]; + let even = vec![(2, "foo"), (4, "bar"), (6, "baz")]; + let expected = vec![(1, "hello"), (2, "foo"), (3, "world"), (4, "bar"), (5, "!"), (6, "baz")]; + let results = odd.iter().merge_by(even.iter(), |a, b| a.0 <= b.0); + it::assert_equal(results, expected.iter()); +} + +#[test] +fn merge_by_btree() { + use std::collections::BTreeMap; + let mut bt1 = BTreeMap::new(); + bt1.insert("hello", 1); + bt1.insert("world", 3); + let mut bt2 = BTreeMap::new(); + bt2.insert("foo", 2); + bt2.insert("bar", 4); + let results = bt1.into_iter().merge_by(bt2.into_iter(), |a, b| a.0 <= b.0 ); + let expected = vec![("bar", 4), ("foo", 2), ("hello", 1), ("world", 3)]; + it::assert_equal(results, expected.into_iter()); +} + +#[allow(deprecated)] +#[test] +fn kmerge() { + let its = (0..4).map(|s| (s..10).step(4)); + + it::assert_equal(its.kmerge(), 0..10); +} + +#[allow(deprecated)] +#[test] +fn kmerge_2() { + let its = vec![3, 2, 1, 0].into_iter().map(|s| (s..10).step(4)); + + it::assert_equal(its.kmerge(), 0..10); +} + +#[test] +fn kmerge_empty() { + let its = (0..4).map(|_| 0..0); + assert_eq!(its.kmerge().next(), None); +} + +#[test] +fn kmerge_size_hint() { + let its = (0..5).map(|_| (0..10)); + assert_eq!(its.kmerge().size_hint(), (50, Some(50))); +} + +#[test] +fn kmerge_empty_size_hint() { + let its = (0..5).map(|_| (0..0)); + assert_eq!(its.kmerge().size_hint(), (0, Some(0))); +} + +#[test] +fn join() { + let many = [1, 2, 3]; + let one = [1]; + let none: Vec<i32> = vec![]; + + assert_eq!(many.iter().join(", "), "1, 2, 3"); + assert_eq!( one.iter().join(", "), "1"); + assert_eq!(none.iter().join(", "), ""); +} + +#[test] +fn sorted_unstable_by() { + let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| { + a.cmp(&b) + }); + it::assert_equal(sc, vec![1, 2, 3, 4]); + + let v = (0..5).sorted_unstable_by(|&a, &b| a.cmp(&b).reverse()); + it::assert_equal(v, vec![4, 3, 2, 1, 0]); +} + +#[test] +fn sorted_unstable_by_key() { + let sc = [3, 4, 1, 2].iter().cloned().sorted_unstable_by_key(|&x| x); + it::assert_equal(sc, vec![1, 2, 3, 4]); + + let v = (0..5).sorted_unstable_by_key(|&x| -x); + it::assert_equal(v, vec![4, 3, 2, 1, 0]); +} + +#[test] +fn sorted_by() { + let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| { + a.cmp(&b) + }); + it::assert_equal(sc, vec![1, 2, 3, 4]); + + let v = (0..5).sorted_by(|&a, &b| a.cmp(&b).reverse()); + it::assert_equal(v, vec![4, 3, 2, 1, 0]); +} + +qc::quickcheck! { + fn k_smallest_range(n: u64, m: u16, k: u16) -> () { + // u16 is used to constrain k and m to 0..2¹⁶, + // otherwise the test could use too much memory. + let (k, m) = (k as u64, m as u64); + + // Generate a random permutation of n..n+m + let i = { + let mut v: Vec<u64> = (n..n.saturating_add(m)).collect(); + v.shuffle(&mut thread_rng()); + v.into_iter() + }; + + // Check that taking the k smallest elements yields n..n+min(k, m) + it::assert_equal( + i.k_smallest(k as usize), + n..n.saturating_add(min(k, m)) + ); + } +} + +#[derive(Clone, Debug)] +struct RandIter<T: 'static + Clone + Send, R: 'static + Clone + Rng + SeedableRng + Send = StdRng> { + idx: usize, + len: usize, + rng: R, + _t: PhantomData<T> +} + +impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> Iterator for RandIter<T, R> +where Standard: Distribution<T> { + type Item = T; + fn next(&mut self) -> Option<T> { + if self.idx == self.len { + None + } else { + self.idx += 1; + Some(self.rng.gen()) + } + } +} + +impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> qc::Arbitrary for RandIter<T, R> { + fn arbitrary<G: qc::Gen>(g: &mut G) -> Self { + RandIter { + idx: 0, + len: g.size(), + rng: R::seed_from_u64(g.next_u64()), + _t : PhantomData{}, + } + } +} + +// Check that taking the k smallest is the same as +// sorting then taking the k first elements +fn k_smallest_sort<I>(i: I, k: u16) +where + I: Iterator + Clone, + I::Item: Ord + Debug, +{ + let j = i.clone(); + let k = k as usize; + it::assert_equal( + i.k_smallest(k), + j.sorted().take(k) + ) +} + +macro_rules! generic_test { + ($f:ident, $($t:ty),+) => { + $(paste::item! { + qc::quickcheck! { + fn [< $f _ $t >](i: RandIter<$t>, k: u16) -> () { + $f(i, k) + } + } + })+ + }; +} + +generic_test!(k_smallest_sort, u8, u16, u32, u64, i8, i16, i32, i64); + +#[test] +fn sorted_by_key() { + let sc = [3, 4, 1, 2].iter().cloned().sorted_by_key(|&x| x); + it::assert_equal(sc, vec![1, 2, 3, 4]); + + let v = (0..5).sorted_by_key(|&x| -x); + it::assert_equal(v, vec![4, 3, 2, 1, 0]); +} + +#[test] +fn sorted_by_cached_key() { + // Track calls to key function + let mut ncalls = 0; + + let sorted = [3, 4, 1, 2].iter().cloned().sorted_by_cached_key(|&x| { + ncalls += 1; + x.to_string() + }); + it::assert_equal(sorted, vec![1, 2, 3, 4]); + // Check key function called once per element + assert_eq!(ncalls, 4); + + let mut ncalls = 0; + + let sorted = (0..5).sorted_by_cached_key(|&x| { + ncalls += 1; + -x + }); + it::assert_equal(sorted, vec![4, 3, 2, 1, 0]); + // Check key function called once per element + assert_eq!(ncalls, 5); +} + +#[test] +fn test_multipeek() { + let nums = vec![1u8,2,3,4,5]; + + let mp = multipeek(nums.iter().copied()); + assert_eq!(nums, mp.collect::<Vec<_>>()); + + let mut mp = multipeek(nums.iter().copied()); + assert_eq!(mp.peek(), Some(&1)); + assert_eq!(mp.next(), Some(1)); + assert_eq!(mp.peek(), Some(&2)); + assert_eq!(mp.peek(), Some(&3)); + assert_eq!(mp.next(), Some(2)); + assert_eq!(mp.peek(), Some(&3)); + assert_eq!(mp.peek(), Some(&4)); + assert_eq!(mp.peek(), Some(&5)); + assert_eq!(mp.peek(), None); + assert_eq!(mp.next(), Some(3)); + assert_eq!(mp.next(), Some(4)); + assert_eq!(mp.peek(), Some(&5)); + assert_eq!(mp.peek(), None); + assert_eq!(mp.next(), Some(5)); + assert_eq!(mp.next(), None); + assert_eq!(mp.peek(), None); +} + +#[test] +fn test_multipeek_reset() { + let data = [1, 2, 3, 4]; + + let mut mp = multipeek(cloned(&data)); + assert_eq!(mp.peek(), Some(&1)); + assert_eq!(mp.next(), Some(1)); + assert_eq!(mp.peek(), Some(&2)); + assert_eq!(mp.peek(), Some(&3)); + mp.reset_peek(); + assert_eq!(mp.peek(), Some(&2)); + assert_eq!(mp.next(), Some(2)); +} + +#[test] +fn test_multipeek_peeking_next() { + use crate::it::PeekingNext; + let nums = vec![1u8,2,3,4,5,6,7]; + + let mut mp = multipeek(nums.iter().copied()); + assert_eq!(mp.peeking_next(|&x| x != 0), Some(1)); + assert_eq!(mp.next(), Some(2)); + assert_eq!(mp.peek(), Some(&3)); + assert_eq!(mp.peek(), Some(&4)); + assert_eq!(mp.peeking_next(|&x| x == 3), Some(3)); + assert_eq!(mp.peek(), Some(&4)); + assert_eq!(mp.peeking_next(|&x| x != 4), None); + assert_eq!(mp.peeking_next(|&x| x == 4), Some(4)); + assert_eq!(mp.peek(), Some(&5)); + assert_eq!(mp.peek(), Some(&6)); + assert_eq!(mp.peeking_next(|&x| x != 5), None); + assert_eq!(mp.peek(), Some(&7)); + assert_eq!(mp.peeking_next(|&x| x == 5), Some(5)); + assert_eq!(mp.peeking_next(|&x| x == 6), Some(6)); + assert_eq!(mp.peek(), Some(&7)); + assert_eq!(mp.peek(), None); + assert_eq!(mp.next(), Some(7)); + assert_eq!(mp.peek(), None); +} + +#[test] +fn test_peek_nth() { + let nums = vec![1u8,2,3,4,5]; + + let iter = peek_nth(nums.iter().copied()); + assert_eq!(nums, iter.collect::<Vec<_>>()); + + let mut iter = peek_nth(nums.iter().copied()); + + assert_eq!(iter.peek_nth(0), Some(&1)); + assert_eq!(iter.peek_nth(0), Some(&1)); + assert_eq!(iter.next(), Some(1)); + + assert_eq!(iter.peek_nth(0), Some(&2)); + assert_eq!(iter.peek_nth(1), Some(&3)); + assert_eq!(iter.next(), Some(2)); + + assert_eq!(iter.peek_nth(0), Some(&3)); + assert_eq!(iter.peek_nth(1), Some(&4)); + assert_eq!(iter.peek_nth(2), Some(&5)); + assert_eq!(iter.peek_nth(3), None); + + assert_eq!(iter.next(), Some(3)); + assert_eq!(iter.next(), Some(4)); + + assert_eq!(iter.peek_nth(0), Some(&5)); + assert_eq!(iter.peek_nth(1), None); + assert_eq!(iter.next(), Some(5)); + assert_eq!(iter.next(), None); + + assert_eq!(iter.peek_nth(0), None); + assert_eq!(iter.peek_nth(1), None); +} + +#[test] +fn test_peek_nth_peeking_next() { + use it::PeekingNext; + let nums = vec![1u8,2,3,4,5,6,7]; + let mut iter = peek_nth(nums.iter().copied()); + + assert_eq!(iter.peeking_next(|&x| x != 0), Some(1)); + assert_eq!(iter.next(), Some(2)); + + assert_eq!(iter.peek_nth(0), Some(&3)); + assert_eq!(iter.peek_nth(1), Some(&4)); + assert_eq!(iter.peeking_next(|&x| x == 3), Some(3)); + assert_eq!(iter.peek(), Some(&4)); + + assert_eq!(iter.peeking_next(|&x| x != 4), None); + assert_eq!(iter.peeking_next(|&x| x == 4), Some(4)); + assert_eq!(iter.peek_nth(0), Some(&5)); + assert_eq!(iter.peek_nth(1), Some(&6)); + + assert_eq!(iter.peeking_next(|&x| x != 5), None); + assert_eq!(iter.peek(), Some(&5)); + + assert_eq!(iter.peeking_next(|&x| x == 5), Some(5)); + assert_eq!(iter.peeking_next(|&x| x == 6), Some(6)); + assert_eq!(iter.peek_nth(0), Some(&7)); + assert_eq!(iter.peek_nth(1), None); + assert_eq!(iter.next(), Some(7)); + assert_eq!(iter.peek(), None); +} + +#[test] +fn pad_using() { + it::assert_equal((0..0).pad_using(1, |_| 1), 1..2); + + let v: Vec<usize> = vec![0, 1, 2]; + let r = v.into_iter().pad_using(5, |n| n); + it::assert_equal(r, vec![0, 1, 2, 3, 4]); + + let v: Vec<usize> = vec![0, 1, 2]; + let r = v.into_iter().pad_using(1, |_| panic!()); + it::assert_equal(r, vec![0, 1, 2]); +} + +#[test] +fn group_by() { + for (ch1, sub) in &"AABBCCC".chars().group_by(|&x| x) { + for ch2 in sub { + assert_eq!(ch1, ch2); + } + } + + for (ch1, sub) in &"AAABBBCCCCDDDD".chars().group_by(|&x| x) { + for ch2 in sub { + assert_eq!(ch1, ch2); + if ch1 == 'C' { + break; + } + } + } + + let toupper = |ch: &char| ch.to_uppercase().next().unwrap(); + + // try all possible orderings + for indices in permutohedron::Heap::new(&mut [0, 1, 2, 3]) { + let groups = "AaaBbbccCcDDDD".chars().group_by(&toupper); + let mut subs = groups.into_iter().collect_vec(); + + for &idx in &indices[..] { + let (key, text) = match idx { + 0 => ('A', "Aaa".chars()), + 1 => ('B', "Bbb".chars()), + 2 => ('C', "ccCc".chars()), + 3 => ('D', "DDDD".chars()), + _ => unreachable!(), + }; + assert_eq!(key, subs[idx].0); + it::assert_equal(&mut subs[idx].1, text); + } + } + + let groups = "AAABBBCCCCDDDD".chars().group_by(|&x| x); + let mut subs = groups.into_iter().map(|(_, g)| g).collect_vec(); + + let sd = subs.pop().unwrap(); + let sc = subs.pop().unwrap(); + let sb = subs.pop().unwrap(); + let sa = subs.pop().unwrap(); + for (a, b, c, d) in multizip((sa, sb, sc, sd)) { + assert_eq!(a, 'A'); + assert_eq!(b, 'B'); + assert_eq!(c, 'C'); + assert_eq!(d, 'D'); + } + + // check that the key closure is called exactly n times + { + let mut ntimes = 0; + let text = "AABCCC"; + for (_, sub) in &text.chars().group_by(|&x| { ntimes += 1; x}) { + for _ in sub { + } + } + assert_eq!(ntimes, text.len()); + } + + { + let mut ntimes = 0; + let text = "AABCCC"; + for _ in &text.chars().group_by(|&x| { ntimes += 1; x}) { + } + assert_eq!(ntimes, text.len()); + } + + { + let text = "ABCCCDEEFGHIJJKK"; + let gr = text.chars().group_by(|&x| x); + it::assert_equal(gr.into_iter().flat_map(|(_, sub)| sub), text.chars()); + } +} + +#[test] +fn group_by_lazy_2() { + let data = vec![0, 1]; + let groups = data.iter().group_by(|k| *k); + let gs = groups.into_iter().collect_vec(); + it::assert_equal(data.iter(), gs.into_iter().flat_map(|(_k, g)| g)); + + let data = vec![0, 1, 1, 0, 0]; + let groups = data.iter().group_by(|k| *k); + let mut gs = groups.into_iter().collect_vec(); + gs[1..].reverse(); + it::assert_equal(&[0, 0, 0, 1, 1], gs.into_iter().flat_map(|(_, g)| g)); + + let grouper = data.iter().group_by(|k| *k); + let mut groups = Vec::new(); + for (k, group) in &grouper { + if *k == 1 { + groups.push(group); + } + } + it::assert_equal(&mut groups[0], &[1, 1]); + + let data = vec![0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3]; + let grouper = data.iter().group_by(|k| *k); + let mut groups = Vec::new(); + for (i, (_, group)) in grouper.into_iter().enumerate() { + if i < 2 { + groups.push(group); + } else if i < 4 { + for _ in group { + } + } else { + groups.push(group); + } + } + it::assert_equal(&mut groups[0], &[0, 0, 0]); + it::assert_equal(&mut groups[1], &[1, 1]); + it::assert_equal(&mut groups[2], &[3, 3]); + + // use groups as chunks + let data = vec![0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3]; + let mut i = 0; + let grouper = data.iter().group_by(move |_| { let k = i / 3; i += 1; k }); + for (i, group) in &grouper { + match i { + 0 => it::assert_equal(group, &[0, 0, 0]), + 1 => it::assert_equal(group, &[1, 1, 0]), + 2 => it::assert_equal(group, &[0, 2, 2]), + 3 => it::assert_equal(group, &[3, 3]), + _ => unreachable!(), + } + } +} + +#[test] +fn group_by_lazy_3() { + // test consuming each group on the lap after it was produced + let data = vec![0, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2]; + let grouper = data.iter().group_by(|elt| *elt); + let mut last = None; + for (key, group) in &grouper { + if let Some(gr) = last.take() { + for elt in gr { + assert!(elt != key && i32::abs(elt - key) == 1); + } + } + last = Some(group); + } +} + +#[test] +fn chunks() { + let data = vec![0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3]; + let grouper = data.iter().chunks(3); + for (i, chunk) in grouper.into_iter().enumerate() { + match i { + 0 => it::assert_equal(chunk, &[0, 0, 0]), + 1 => it::assert_equal(chunk, &[1, 1, 0]), + 2 => it::assert_equal(chunk, &[0, 2, 2]), + 3 => it::assert_equal(chunk, &[3, 3]), + _ => unreachable!(), + } + } +} + +#[test] +fn concat_empty() { + let data: Vec<Vec<()>> = Vec::new(); + assert_eq!(data.into_iter().concat(), Vec::new()) +} + +#[test] +fn concat_non_empty() { + let data = vec![vec![1,2,3], vec![4,5,6], vec![7,8,9]]; + assert_eq!(data.into_iter().concat(), vec![1,2,3,4,5,6,7,8,9]) +} + +#[test] +fn combinations() { + assert!((1..3).combinations(5).next().is_none()); + + let it = (1..3).combinations(2); + it::assert_equal(it, vec![ + vec![1, 2], + ]); + + let it = (1..5).combinations(2); + it::assert_equal(it, vec![ + vec![1, 2], + vec![1, 3], + vec![1, 4], + vec![2, 3], + vec![2, 4], + vec![3, 4], + ]); + + it::assert_equal((0..0).tuple_combinations::<(_, _)>(), <Vec<_>>::new()); + it::assert_equal((0..1).tuple_combinations::<(_, _)>(), <Vec<_>>::new()); + it::assert_equal((0..2).tuple_combinations::<(_, _)>(), vec![(0, 1)]); + + it::assert_equal((0..0).combinations(2), <Vec<Vec<_>>>::new()); + it::assert_equal((0..1).combinations(1), vec![vec![0]]); + it::assert_equal((0..2).combinations(1), vec![vec![0], vec![1]]); + it::assert_equal((0..2).combinations(2), vec![vec![0, 1]]); +} + +#[test] +fn combinations_of_too_short() { + for i in 1..10 { + assert!((0..0).combinations(i).next().is_none()); + assert!((0..i - 1).combinations(i).next().is_none()); + } +} + + +#[test] +fn combinations_zero() { + it::assert_equal((1..3).combinations(0), vec![vec![]]); + it::assert_equal((0..0).combinations(0), vec![vec![]]); +} + +#[test] +fn permutations_zero() { + it::assert_equal((1..3).permutations(0), vec![vec![]]); + it::assert_equal((0..0).permutations(0), vec![vec![]]); +} + +#[test] +fn combinations_with_replacement() { + // Pool smaller than n + it::assert_equal((0..1).combinations_with_replacement(2), vec![vec![0, 0]]); + // Pool larger than n + it::assert_equal( + (0..3).combinations_with_replacement(2), + vec![ + vec![0, 0], + vec![0, 1], + vec![0, 2], + vec![1, 1], + vec![1, 2], + vec![2, 2], + ], + ); + // Zero size + it::assert_equal( + (0..3).combinations_with_replacement(0), + vec![vec![]], + ); + // Zero size on empty pool + it::assert_equal( + (0..0).combinations_with_replacement(0), + vec![vec![]], + ); + // Empty pool + it::assert_equal( + (0..0).combinations_with_replacement(2), + <Vec<Vec<_>>>::new(), + ); +} + +#[test] +fn powerset() { + it::assert_equal((0..0).powerset(), vec![vec![]]); + it::assert_equal((0..1).powerset(), vec![vec![], vec![0]]); + it::assert_equal((0..2).powerset(), vec![vec![], vec![0], vec![1], vec![0, 1]]); + it::assert_equal((0..3).powerset(), vec![ + vec![], + vec![0], vec![1], vec![2], + vec![0, 1], vec![0, 2], vec![1, 2], + vec![0, 1, 2] + ]); + + assert_eq!((0..4).powerset().count(), 1 << 4); + assert_eq!((0..8).powerset().count(), 1 << 8); + assert_eq!((0..16).powerset().count(), 1 << 16); +} + +#[test] +fn diff_mismatch() { + let a = vec![1, 2, 3, 4]; + let b = vec![1.0, 5.0, 3.0, 4.0]; + let b_map = b.into_iter().map(|f| f as i32); + let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b); + + assert!(match diff { + Some(it::Diff::FirstMismatch(1, _, from_diff)) => + from_diff.collect::<Vec<_>>() == vec![5, 3, 4], + _ => false, + }); +} + +#[test] +fn diff_longer() { + let a = vec![1, 2, 3, 4]; + let b = vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0]; + let b_map = b.into_iter().map(|f| f as i32); + let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b); + + assert!(match diff { + Some(it::Diff::Longer(_, remaining)) => + remaining.collect::<Vec<_>>() == vec![5, 6], + _ => false, + }); +} + +#[test] +fn diff_shorter() { + let a = vec![1, 2, 3, 4]; + let b = vec![1.0, 2.0]; + let b_map = b.into_iter().map(|f| f as i32); + let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b); + + assert!(match diff { + Some(it::Diff::Shorter(len, _)) => len == 2, + _ => false, + }); +} + +#[test] +fn extrema_set() { + use std::cmp::Ordering; + + // A peculiar type: Equality compares both tuple items, but ordering only the + // first item. Used to distinguish equal elements. + #[derive(Clone, Debug, PartialEq, Eq)] + struct Val(u32, u32); + + impl PartialOrd<Val> for Val { + fn partial_cmp(&self, other: &Val) -> Option<Ordering> { + self.0.partial_cmp(&other.0) + } + } + + impl Ord for Val { + fn cmp(&self, other: &Val) -> Ordering { + self.0.cmp(&other.0) + } + } + + assert_eq!(None::<u32>.iter().min_set(), Vec::<&u32>::new()); + assert_eq!(None::<u32>.iter().max_set(), Vec::<&u32>::new()); + + assert_eq!(Some(1u32).iter().min_set(), vec![&1]); + assert_eq!(Some(1u32).iter().max_set(), vec![&1]); + + let data = vec![Val(0, 1), Val(2, 0), Val(0, 2), Val(1, 0), Val(2, 1)]; + + let min_set = data.iter().min_set(); + assert_eq!(min_set, vec![&Val(0, 1), &Val(0, 2)]); + + let min_set_by_key = data.iter().min_set_by_key(|v| v.1); + assert_eq!(min_set_by_key, vec![&Val(2, 0), &Val(1, 0)]); + + let min_set_by = data.iter().min_set_by(|x, y| x.1.cmp(&y.1)); + assert_eq!(min_set_by, vec![&Val(2, 0), &Val(1, 0)]); + + let max_set = data.iter().max_set(); + assert_eq!(max_set, vec![&Val(2, 0), &Val(2, 1)]); + + let max_set_by_key = data.iter().max_set_by_key(|v| v.1); + assert_eq!(max_set_by_key, vec![&Val(0, 2)]); + + let max_set_by = data.iter().max_set_by(|x, y| x.1.cmp(&y.1)); + assert_eq!(max_set_by, vec![&Val(0, 2)]); +} + +#[test] +fn minmax() { + use std::cmp::Ordering; + use crate::it::MinMaxResult; + + // A peculiar type: Equality compares both tuple items, but ordering only the + // first item. This is so we can check the stability property easily. + #[derive(Clone, Debug, PartialEq, Eq)] + struct Val(u32, u32); + + impl PartialOrd<Val> for Val { + fn partial_cmp(&self, other: &Val) -> Option<Ordering> { + self.0.partial_cmp(&other.0) + } + } + + impl Ord for Val { + fn cmp(&self, other: &Val) -> Ordering { + self.0.cmp(&other.0) + } + } + + assert_eq!(None::<Option<u32>>.iter().minmax(), MinMaxResult::NoElements); + + assert_eq!(Some(1u32).iter().minmax(), MinMaxResult::OneElement(&1)); + + let data = vec![Val(0, 1), Val(2, 0), Val(0, 2), Val(1, 0), Val(2, 1)]; + + let minmax = data.iter().minmax(); + assert_eq!(minmax, MinMaxResult::MinMax(&Val(0, 1), &Val(2, 1))); + + let (min, max) = data.iter().minmax_by_key(|v| v.1).into_option().unwrap(); + assert_eq!(min, &Val(2, 0)); + assert_eq!(max, &Val(0, 2)); + + let (min, max) = data.iter().minmax_by(|x, y| x.1.cmp(&y.1)).into_option().unwrap(); + assert_eq!(min, &Val(2, 0)); + assert_eq!(max, &Val(0, 2)); +} + +#[test] +fn format() { + let data = [0, 1, 2, 3]; + let ans1 = "0, 1, 2, 3"; + let ans2 = "0--1--2--3"; + + let t1 = format!("{}", data.iter().format(", ")); + assert_eq!(t1, ans1); + let t2 = format!("{:?}", data.iter().format("--")); + assert_eq!(t2, ans2); + + let dataf = [1.1, 5.71828, -22.]; + let t3 = format!("{:.2e}", dataf.iter().format(", ")); + assert_eq!(t3, "1.10e0, 5.72e0, -2.20e1"); +} + +#[test] +fn while_some() { + let ns = (1..10).map(|x| if x % 5 != 0 { Some(x) } else { None }) + .while_some(); + it::assert_equal(ns, vec![1, 2, 3, 4]); +} + +#[allow(deprecated)] +#[test] +fn fold_while() { + let mut iterations = 0; + let vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; + let sum = vec.into_iter().fold_while(0, |acc, item| { + iterations += 1; + let new_sum = acc + item; + if new_sum <= 20 { + FoldWhile::Continue(new_sum) + } else { + FoldWhile::Done(acc) + } + }).into_inner(); + assert_eq!(iterations, 6); + assert_eq!(sum, 15); +} + +#[test] +fn tree_fold1() { + let x = [ + "", + "0", + "0 1 x", + "0 1 x 2 x", + "0 1 x 2 3 x x", + "0 1 x 2 3 x x 4 x", + "0 1 x 2 3 x x 4 5 x x", + "0 1 x 2 3 x x 4 5 x 6 x x", + "0 1 x 2 3 x x 4 5 x 6 7 x x x", + "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 x", + "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x x", + "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 x x", + "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x x", + "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x 12 x x", + "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x 12 13 x x x", + "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x 12 13 x 14 x x x", + "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x 12 13 x 14 15 x x x x", + ]; + for (i, &s) in x.iter().enumerate() { + let expected = if s.is_empty() { None } else { Some(s.to_string()) }; + let num_strings = (0..i).map(|x| x.to_string()); + let actual = num_strings.tree_fold1(|a, b| format!("{} {} x", a, b)); + assert_eq!(actual, expected); + } +} + +#[test] +fn exactly_one_question_mark_syntax_works() { + exactly_one_question_mark_return().unwrap_err(); +} + +fn exactly_one_question_mark_return() -> Result<(), ExactlyOneError<std::slice::Iter<'static, ()>>> { + [].iter().exactly_one()?; + Ok(()) +} + +#[test] +fn multiunzip() { + let (a, b, c): (Vec<_>, Vec<_>, Vec<_>) = [(0, 1, 2), (3, 4, 5), (6, 7, 8)].iter().cloned().multiunzip(); + assert_eq!((a, b, c), (vec![0, 3, 6], vec![1, 4, 7], vec![2, 5, 8])); + let (): () = [(), (), ()].iter().cloned().multiunzip(); + let t: (Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>) = [(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)].iter().cloned().multiunzip(); + assert_eq!(t, (vec![0], vec![1], vec![2], vec![3], vec![4], vec![5], vec![6], vec![7], vec![8], vec![9], vec![10], vec![11])); +} diff --git a/third_party/rust/itertools/tests/tuples.rs b/third_party/rust/itertools/tests/tuples.rs new file mode 100644 index 0000000000..9fc8b3cc78 --- /dev/null +++ b/third_party/rust/itertools/tests/tuples.rs @@ -0,0 +1,86 @@ +use itertools::Itertools; + +#[test] +fn tuples() { + let v = [1, 2, 3, 4, 5]; + let mut iter = v.iter().cloned().tuples(); + assert_eq!(Some((1,)), iter.next()); + assert_eq!(Some((2,)), iter.next()); + assert_eq!(Some((3,)), iter.next()); + assert_eq!(Some((4,)), iter.next()); + assert_eq!(Some((5,)), iter.next()); + assert_eq!(None, iter.next()); + assert_eq!(None, iter.into_buffer().next()); + + let mut iter = v.iter().cloned().tuples(); + assert_eq!(Some((1, 2)), iter.next()); + assert_eq!(Some((3, 4)), iter.next()); + assert_eq!(None, iter.next()); + itertools::assert_equal(vec![5], iter.into_buffer()); + + let mut iter = v.iter().cloned().tuples(); + assert_eq!(Some((1, 2, 3)), iter.next()); + assert_eq!(None, iter.next()); + itertools::assert_equal(vec![4, 5], iter.into_buffer()); + + let mut iter = v.iter().cloned().tuples(); + assert_eq!(Some((1, 2, 3, 4)), iter.next()); + assert_eq!(None, iter.next()); + itertools::assert_equal(vec![5], iter.into_buffer()); +} + +#[test] +fn tuple_windows() { + let v = [1, 2, 3, 4, 5]; + + let mut iter = v.iter().cloned().tuple_windows(); + assert_eq!(Some((1,)), iter.next()); + assert_eq!(Some((2,)), iter.next()); + assert_eq!(Some((3,)), iter.next()); + + let mut iter = v.iter().cloned().tuple_windows(); + assert_eq!(Some((1, 2)), iter.next()); + assert_eq!(Some((2, 3)), iter.next()); + assert_eq!(Some((3, 4)), iter.next()); + assert_eq!(Some((4, 5)), iter.next()); + assert_eq!(None, iter.next()); + + let mut iter = v.iter().cloned().tuple_windows(); + assert_eq!(Some((1, 2, 3)), iter.next()); + assert_eq!(Some((2, 3, 4)), iter.next()); + assert_eq!(Some((3, 4, 5)), iter.next()); + assert_eq!(None, iter.next()); + + let mut iter = v.iter().cloned().tuple_windows(); + assert_eq!(Some((1, 2, 3, 4)), iter.next()); + assert_eq!(Some((2, 3, 4, 5)), iter.next()); + assert_eq!(None, iter.next()); + + let v = [1, 2, 3]; + let mut iter = v.iter().cloned().tuple_windows::<(_, _, _, _)>(); + assert_eq!(None, iter.next()); +} + +#[test] +fn next_tuple() { + let v = [1, 2, 3, 4, 5]; + let mut iter = v.iter(); + assert_eq!(iter.next_tuple().map(|(&x, &y)| (x, y)), Some((1, 2))); + assert_eq!(iter.next_tuple().map(|(&x, &y)| (x, y)), Some((3, 4))); + assert_eq!(iter.next_tuple::<(_, _)>(), None); +} + +#[test] +fn collect_tuple() { + let v = [1, 2]; + let iter = v.iter().cloned(); + assert_eq!(iter.collect_tuple(), Some((1, 2))); + + let v = [1]; + let iter = v.iter().cloned(); + assert_eq!(iter.collect_tuple::<(_, _)>(), None); + + let v = [1, 2, 3]; + let iter = v.iter().cloned(); + assert_eq!(iter.collect_tuple::<(_, _)>(), None); +} diff --git a/third_party/rust/itertools/tests/zip.rs b/third_party/rust/itertools/tests/zip.rs new file mode 100644 index 0000000000..75157d34f3 --- /dev/null +++ b/third_party/rust/itertools/tests/zip.rs @@ -0,0 +1,77 @@ +use itertools::Itertools; +use itertools::EitherOrBoth::{Both, Left, Right}; +use itertools::free::zip_eq; +use itertools::multizip; + +#[test] +fn zip_longest_fused() { + let a = [Some(1), None, Some(3), Some(4)]; + let b = [1, 2, 3]; + + let unfused = a.iter().batching(|it| *it.next().unwrap()) + .zip_longest(b.iter().cloned()); + itertools::assert_equal(unfused, + vec![Both(1, 1), Right(2), Right(3)]); +} + +#[test] +fn test_zip_longest_size_hint() { + let c = (1..10).cycle(); + let v: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; + let v2 = &[10, 11, 12]; + + assert_eq!(c.zip_longest(v.iter()).size_hint(), (std::usize::MAX, None)); + + assert_eq!(v.iter().zip_longest(v2.iter()).size_hint(), (10, Some(10))); +} + +#[test] +fn test_double_ended_zip_longest() { + let xs = [1, 2, 3, 4, 5, 6]; + let ys = [1, 2, 3, 7]; + let a = xs.iter().copied(); + let b = ys.iter().copied(); + let mut it = a.zip_longest(b); + assert_eq!(it.next(), Some(Both(1, 1))); + assert_eq!(it.next(), Some(Both(2, 2))); + assert_eq!(it.next_back(), Some(Left(6))); + assert_eq!(it.next_back(), Some(Left(5))); + assert_eq!(it.next_back(), Some(Both(4, 7))); + assert_eq!(it.next(), Some(Both(3, 3))); + assert_eq!(it.next(), None); +} + +#[test] +fn test_double_ended_zip() { + let xs = [1, 2, 3, 4, 5, 6]; + let ys = [1, 2, 3, 7]; + let a = xs.iter().copied(); + let b = ys.iter().copied(); + let mut it = multizip((a, b)); + assert_eq!(it.next_back(), Some((4, 7))); + assert_eq!(it.next_back(), Some((3, 3))); + assert_eq!(it.next_back(), Some((2, 2))); + assert_eq!(it.next_back(), Some((1, 1))); + assert_eq!(it.next_back(), None); +} + + +#[should_panic] +#[test] +fn zip_eq_panic1() +{ + let a = [1, 2]; + let b = [1, 2, 3]; + + zip_eq(&a, &b).count(); +} + +#[should_panic] +#[test] +fn zip_eq_panic2() +{ + let a: [i32; 0] = []; + let b = [1, 2, 3]; + + zip_eq(&a, &b).count(); +} |