src/vendor/itertools/tests/quick.rs

   1 //! The purpose of these tests is to cover corner cases of iterators
   2 //! and adaptors.
   3 //!
   4 //! In particular we test the tedious size_hint and exact size correctness.
   5
   6 #[macro_use] extern crate itertools;
   7
   8 extern crate quickcheck;
   9
  10 use std::default::Default;
  11
  12 use quickcheck as qc;
  13 use std::ops::Range;
  14 use std::cmp::Ordering;
  15 use itertools::Itertools;
  16 use itertools::{
  17     multizip,
  18     EitherOrBoth,
  19 };
  20 use itertools::flatten;
  21 use itertools::free::{
  22     cloned,
  23     enumerate,
  24     multipeek,
  25     put_back,
  26     put_back_n,
  27     rciter,
  28     zip,
  29     zip_eq,
  30 };
  31
  32 use quickcheck::TestResult;
  33
  34 /// Trait for size hint modifier types
  35 trait HintKind: Copy + Send + qc::Arbitrary {
  36     fn loosen_bounds(&self, org_hint: (usize, Option<usize>)) -> (usize, Option<usize>);
  37 }
  38
  39 /// Exact size hint variant that leaves hints unchanged
  40 #[derive(Clone, Copy, Debug)]
  41 struct Exact {}
  42
  43 impl HintKind for Exact {
  44     fn loosen_bounds(&self, org_hint: (usize, Option<usize>)) -> (usize, Option<usize>) {
  45         org_hint
  46     }
  47 }
  48
  49 impl qc::Arbitrary for Exact {
  50     fn arbitrary<G: qc::Gen>(_: &mut G) -> Self {
  51         Exact {}
  52     }
  53 }
  54
  55 /// Inexact size hint variant to simulate imprecise (but valid) size hints
  56 ///
  57 /// Will always decrease the lower bound and increase the upper bound
  58 /// of the size hint by set amounts.
  59 #[derive(Clone, Copy, Debug)]
  60 struct Inexact {
  61     underestimate: usize,
  62     overestimate: usize,
  63 }
  64
  65 impl HintKind for Inexact {
  66     fn loosen_bounds(&self, org_hint: (usize, Option<usize>)) -> (usize, Option<usize>) {
  67         let (org_lower, org_upper) = org_hint;
  68         (org_lower.saturating_sub(self.underestimate),
  69          org_upper.and_then(move |x| x.checked_add(self.overestimate)))
  70     }
  71 }
  72
  73 impl qc::Arbitrary for Inexact {
  74     fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
  75         let ue_value = usize::arbitrary(g);
  76         let oe_value = usize::arbitrary(g);
  77         // Compensate for quickcheck using extreme values too rarely
  78         let ue_choices = &[0, ue_value, usize::max_value()];
  79         let oe_choices = &[0, oe_value, usize::max_value()];
  80         Inexact {
  81             underestimate: *g.choose(ue_choices).unwrap(),
  82             overestimate: *g.choose(oe_choices).unwrap(),
  83         }
  84     }
  85
  86     fn shrink(&self) -> Box<Iterator<Item=Self>> {
  87         let underestimate_value = self.underestimate;
  88         let overestimate_value = self.overestimate;
  89         Box::new(
  90             underestimate_value.shrink().flat_map(move |ue_value|
  91                 overestimate_value.shrink().map(move |oe_value|
  92                     Inexact {
  93                         underestimate: ue_value,
  94                         overestimate: oe_value,
  95                     }
  96                 )
  97             )
  98         )
  99     }
 100 }
 101
 102 /// Our base iterator that we can impl Arbitrary for
 103 ///
 104 /// By default we'll return inexact bounds estimates for size_hint
 105 /// to make tests harder to pass.
 106 ///
 107 /// NOTE: Iter is tricky and is not fused, to help catch bugs.
 108 /// At the end it will return None once, then return Some(0),
 109 /// then return None again.
 110 #[derive(Clone, Debug)]
 111 struct Iter<T, SK: HintKind = Inexact> {
 112     iterator: Range<T>,
 113     // fuse/done flag
 114     fuse_flag: i32,
 115     hint_kind: SK,
 116 }
 117
 118 impl<T, HK> Iter<T, HK> where HK: HintKind
 119 {
 120     fn new(it: Range<T>, hint_kind: HK) -> Self {
 121         Iter {
 122             iterator: it,
 123             fuse_flag: 0,
 124             hint_kind: hint_kind
 125         }
 126     }
 127 }
 128
 129 impl<T, HK> Iterator for Iter<T, HK>
 130     where Range<T>: Iterator,
 131           <Range<T> as Iterator>::Item: Default,
 132           HK: HintKind,
 133 {
 134     type Item = <Range<T> as Iterator>::Item;
 135
 136     fn next(&mut self) -> Option<Self::Item>
 137     {
 138         let elt = self.iterator.next();
 139         if elt.is_none() {
 140             self.fuse_flag += 1;
 141             // check fuse flag
 142             if self.fuse_flag == 2 {
 143                 return Some(Default::default())
 144             }
 145         }
 146         elt
 147     }
 148
 149     fn size_hint(&self) -> (usize, Option<usize>)
 150     {
 151         let org_hint = self.iterator.size_hint();
 152         self.hint_kind.loosen_bounds(org_hint)
 153     }
 154 }
 155
 156 impl<T, HK> DoubleEndedIterator for Iter<T, HK>
 157     where Range<T>: DoubleEndedIterator,
 158           <Range<T> as Iterator>::Item: Default,
 159           HK: HintKind
 160 {
 161     fn next_back(&mut self) -> Option<Self::Item> { self.iterator.next_back() }
 162 }
 163
 164 impl<T> ExactSizeIterator for Iter<T, Exact> where Range<T>: ExactSizeIterator,
 165     <Range<T> as Iterator>::Item: Default,
 166 { }
 167
 168 impl<T, HK> qc::Arbitrary for Iter<T, HK>
 169     where T: qc::Arbitrary,
 170           HK: HintKind,
 171 {
 172     fn arbitrary<G: qc::Gen>(g: &mut G) -> Self
 173     {
 174         Iter::new(T::arbitrary(g)..T::arbitrary(g), HK::arbitrary(g))
 175     }
 176
 177     fn shrink(&self) -> Box<Iterator<Item=Iter<T, HK>>>
 178     {
 179         let r = self.iterator.clone();
 180         let hint_kind = self.hint_kind;
 181         Box::new(
 182             r.start.shrink().flat_map(move |a|
 183                 r.end.shrink().map(move |b|
 184                     Iter::new(a.clone()..b, hint_kind)
 185                 )
 186             )
 187         )
 188     }
 189 }
 190
 191 /// A meta-iterator which yields `Iter<i32>`s whose start/endpoints are
 192 /// increased or decreased linearly on each iteration.
 193 #[derive(Clone, Debug)]
 194 struct ShiftRange<HK = Inexact> {
 195     range_start: i32,
 196     range_end: i32,
 197     start_step: i32,
 198     end_step: i32,
 199     iter_count: u32,
 200     hint_kind: HK,
 201 }
 202
 203 impl<HK> Iterator for ShiftRange<HK> where HK: HintKind {
 204     type Item = Iter<i32, HK>;
 205
 206     fn next(&mut self) -> Option<Self::Item> {
 207         if self.iter_count == 0 {
 208             return None;
 209         }
 210
 211         let iter = Iter::new(self.range_start..self.range_end, self.hint_kind);
 212
 213         self.range_start += self.start_step;
 214         self.range_end += self.end_step;
 215         self.iter_count -= 1;
 216
 217         Some(iter)
 218     }
 219 }
 220
 221 impl ExactSizeIterator for ShiftRange<Exact> { }
 222
 223 impl<HK> qc::Arbitrary for ShiftRange<HK>
 224     where HK: HintKind
 225 {
 226     fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
 227         const MAX_STARTING_RANGE_DIFF: i32 = 32;
 228         const MAX_STEP_MODULO: i32 = 8;
 229         const MAX_ITER_COUNT: u32 = 3;
 230
 231         let range_start = qc::Arbitrary::arbitrary(g);
 232         let range_end = range_start + g.gen_range(0, MAX_STARTING_RANGE_DIFF + 1);
 233         let start_step = g.gen_range(-MAX_STEP_MODULO, MAX_STEP_MODULO + 1);
 234         let end_step = g.gen_range(-MAX_STEP_MODULO, MAX_STEP_MODULO + 1);
 235         let iter_count = g.gen_range(0, MAX_ITER_COUNT + 1);
 236         let hint_kind = qc::Arbitrary::arbitrary(g);
 237
 238         ShiftRange {
 239             range_start: range_start,
 240             range_end: range_end,
 241             start_step: start_step,
 242             end_step: end_step,
 243             iter_count: iter_count,
 244             hint_kind: hint_kind
 245         }
 246     }
 247 }
 248
 249 fn correct_size_hint<I: Iterator>(mut it: I) -> bool {
 250     // record size hint at each iteration
 251     let initial_hint = it.size_hint();
 252     let mut hints = Vec::with_capacity(initial_hint.0 + 1);
 253     hints.push(initial_hint);
 254     while let Some(_) = it.next() {
 255         hints.push(it.size_hint())
 256     }
 257
 258     let mut true_count = hints.len(); // start off +1 too much
 259
 260     // check all the size hints
 261     for &(low, hi) in &hints {
 262         true_count -= 1;
 263         if low > true_count ||
 264             (hi.is_some() && hi.unwrap() < true_count)
 265         {
 266             println!("True size: {:?}, size hint: {:?}", true_count, (low, hi));
 267             //println!("All hints: {:?}", hints);
 268             return false
 269         }
 270     }
 271     true
 272 }
 273
 274 fn exact_size<I: ExactSizeIterator>(mut it: I) -> bool {
 275     // check every iteration
 276     let (mut low, mut hi) = it.size_hint();
 277     if Some(low) != hi { return false; }
 278     while let Some(_) = it.next() {
 279         let (xlow, xhi) = it.size_hint();
 280         if low != xlow + 1 { return false; }
 281         low = xlow;
 282         hi = xhi;
 283         if Some(low) != hi { return false; }
 284     }
 285     let (low, hi) = it.size_hint();
 286     low == 0 && hi == Some(0)
 287 }
 288
 289 // Exact size for this case, without ExactSizeIterator
 290 fn exact_size_for_this<I: Iterator>(mut it: I) -> bool {
 291     // check every iteration
 292     let (mut low, mut hi) = it.size_hint();
 293     if Some(low) != hi { return false; }
 294     while let Some(_) = it.next() {
 295         let (xlow, xhi) = it.size_hint();
 296         if low != xlow + 1 { return false; }
 297         low = xlow;
 298         hi = xhi;
 299         if Some(low) != hi { return false; }
 300     }
 301     let (low, hi) = it.size_hint();
 302     low == 0 && hi == Some(0)
 303 }
 304
 305 /*
 306  * NOTE: Range<i8> is broken!
 307  * (all signed ranges are)
 308 #[quickcheck]
 309 fn size_range_i8(a: Iter<i8>) -> bool {
 310     exact_size(a)
 311 }
 312
 313 #[quickcheck]
 314 fn size_range_i16(a: Iter<i16>) -> bool {
 315     exact_size(a)
 316 }
 317
 318 #[quickcheck]
 319 fn size_range_u8(a: Iter<u8>) -> bool {
 320     exact_size(a)
 321 }
 322  */
 323
 324 macro_rules! quickcheck {
 325     // accept several property function definitions
 326     // The property functions can use pattern matching and `mut` as usual
 327     // in the function arguments, but the functions can not be generic.
 328     {$($(#$attr:tt)* fn $fn_name:ident($($arg:tt)*) -> $ret:ty { $($code:tt)* })*} => (
 329         $(
 330             #[test]
 331             $(#$attr)*
 332             fn $fn_name() {
 333                 fn prop($($arg)*) -> $ret {
 334                     $($code)*
 335                 }
 336                 ::quickcheck::quickcheck(quickcheck!(@fn prop [] $($arg)*));
 337             }
 338         )*
 339     );
 340     // parse argument list (with patterns allowed) into prop as fn(_, _) -> _
 341     (@fn $f:ident [$($t:tt)*]) => {
 342         $f as fn($($t),*) -> _
 343     };
 344     (@fn $f:ident [$($p:tt)*] : $($tail:tt)*) => {
 345         quickcheck!(@fn $f [$($p)* _] $($tail)*)
 346     };
 347     (@fn $f:ident [$($p:tt)*] $t:tt $($tail:tt)*) => {
 348         quickcheck!(@fn $f [$($p)*] $($tail)*)
 349     };
 350 }
 351
 352 quickcheck! {
 353
 354     fn size_product(a: Iter<u16>, b: Iter<u16>) -> bool {
 355         correct_size_hint(a.cartesian_product(b))
 356     }
 357     fn size_product3(a: Iter<u16>, b: Iter<u16>, c: Iter<u16>) -> bool {
 358         correct_size_hint(iproduct!(a, b, c))
 359     }
 360
 361     fn correct_cartesian_product3(a: Iter<u16>, b: Iter<u16>, c: Iter<u16>,
 362                                   take_manual: usize) -> ()
 363     {
 364         // test correctness of iproduct through regular iteration (take)
 365         // and through fold.
 366         let ac = a.clone();
 367         let br = &b.clone();
 368         let cr = &c.clone();
 369         let answer: Vec<_> = ac.flat_map(move |ea| br.clone().flat_map(move |eb| cr.clone().map(move |ec| (ea, eb, ec)))).collect();
 370         let mut product_iter = iproduct!(a, b, c);
 371         let mut actual = Vec::new();
 372
 373         actual.extend((&mut product_iter).take(take_manual));
 374         if actual.len() == take_manual {
 375             product_iter.fold((), |(), elt| actual.push(elt));
 376         }
 377         assert_eq!(answer, actual);
 378     }
 379
 380     fn size_multi_product(a: ShiftRange) -> bool {
 381         correct_size_hint(a.multi_cartesian_product())
 382     }
 383     fn correct_multi_product3(a: ShiftRange, take_manual: usize) -> () {
 384         // Fix no. of iterators at 3
 385         let a = ShiftRange { iter_count: 3, ..a };
 386
 387         // test correctness of MultiProduct through regular iteration (take)
 388         // and through fold.
 389         let mut iters = a.clone();
 390         let i0 = iters.next().unwrap();
 391         let i1r = &iters.next().unwrap();
 392         let i2r = &iters.next().unwrap();
 393         let answer: Vec<_> = i0.flat_map(move |ei0| i1r.clone().flat_map(move |ei1| i2r.clone().map(move |ei2| vec![ei0, ei1, ei2]))).collect();
 394         let mut multi_product = a.clone().multi_cartesian_product();
 395         let mut actual = Vec::new();
 396
 397         actual.extend((&mut multi_product).take(take_manual));
 398         if actual.len() == take_manual {
 399             multi_product.fold((), |(), elt| actual.push(elt));
 400         }
 401         assert_eq!(answer, actual);
 402
 403         assert_eq!(answer.into_iter().last(), a.clone().multi_cartesian_product().last());
 404     }
 405
 406     fn size_step(a: Iter<i16, Exact>, s: usize) -> bool {
 407         let mut s = s;
 408         if s == 0 {
 409             s += 1; // never zero
 410         }
 411         let filt = a.clone().dedup();
 412         correct_size_hint(filt.step(s)) &&
 413             exact_size(a.step(s))
 414     }
 415     fn equal_step(a: Iter<i16>, s: usize) -> bool {
 416         let mut s = s;
 417         if s == 0 {
 418             s += 1; // never zero
 419         }
 420         let mut i = 0;
 421         itertools::equal(a.clone().step(s), a.filter(|_| {
 422             let keep = i % s == 0;
 423             i += 1;
 424             keep
 425         }))
 426     }
 427     fn equal_step_vec(a: Vec<i16>, s: usize) -> bool {
 428         let mut s = s;
 429         if s == 0 {
 430             s += 1; // never zero
 431         }
 432         let mut i = 0;
 433         itertools::equal(a.iter().step(s), a.iter().filter(|_| {
 434             let keep = i % s == 0;
 435             i += 1;
 436             keep
 437         }))
 438     }
 439
 440     fn size_multipeek(a: Iter<u16, Exact>, s: u8) -> bool {
 441         let mut it = multipeek(a);
 442         // peek a few times
 443         for _ in 0..s {
 444             it.peek();
 445         }
 446         exact_size(it)
 447     }
 448
 449     fn equal_merge(a: Vec<i16>, b: Vec<i16>) -> bool {
 450         let mut sa = a.clone();
 451         let mut sb = b.clone();
 452         sa.sort();
 453         sb.sort();
 454         let mut merged = sa.clone();
 455         merged.extend(sb.iter().cloned());
 456         merged.sort();
 457         itertools::equal(&merged, sa.iter().merge(&sb))
 458     }
 459     fn size_merge(a: Iter<u16>, b: Iter<u16>) -> bool {
 460         correct_size_hint(a.merge(b))
 461     }
 462     fn size_zip(a: Iter<i16, Exact>, b: Iter<i16, Exact>, c: Iter<i16, Exact>) -> bool {
 463         let filt = a.clone().dedup();
 464         correct_size_hint(multizip((filt, b.clone(), c.clone()))) &&
 465             exact_size(multizip((a, b, c)))
 466     }
 467     fn size_zip_rc(a: Iter<i16>, b: Iter<i16>) -> bool {
 468         let rc = rciter(a.clone());
 469         correct_size_hint(multizip((&rc, &rc, b)))
 470     }
 471
 472     fn size_zip_macro(a: Iter<i16, Exact>, b: Iter<i16, Exact>, c: Iter<i16, Exact>) -> bool {
 473         let filt = a.clone().dedup();
 474         correct_size_hint(izip!(filt, b.clone(), c.clone())) &&
 475             exact_size(izip!(a, b, c))
 476     }
 477     fn equal_kmerge(a: Vec<i16>, b: Vec<i16>, c: Vec<i16>) -> bool {
 478         use itertools::free::kmerge;
 479         let mut sa = a.clone();
 480         let mut sb = b.clone();
 481         let mut sc = c.clone();
 482         sa.sort();
 483         sb.sort();
 484         sc.sort();
 485         let mut merged = sa.clone();
 486         merged.extend(sb.iter().cloned());
 487         merged.extend(sc.iter().cloned());
 488         merged.sort();
 489         itertools::equal(merged.into_iter(), kmerge(vec![sa, sb, sc]))
 490     }
 491
 492     // Any number of input iterators
 493     fn equal_kmerge_2(mut inputs: Vec<Vec<i16>>) -> bool {
 494         use itertools::free::kmerge;
 495         // sort the inputs
 496         for input in &mut inputs {
 497             input.sort();
 498         }
 499         let mut merged = inputs.concat();
 500         merged.sort();
 501         itertools::equal(merged.into_iter(), kmerge(inputs))
 502     }
 503
 504     // Any number of input iterators
 505     fn equal_kmerge_by_ge(mut inputs: Vec<Vec<i16>>) -> bool {
 506         // sort the inputs
 507         for input in &mut inputs {
 508             input.sort();
 509             input.reverse();
 510         }
 511         let mut merged = inputs.concat();
 512         merged.sort();
 513         merged.reverse();
 514         itertools::equal(merged.into_iter(),
 515                          inputs.into_iter().kmerge_by(|x, y| x >= y))
 516     }
 517
 518     // Any number of input iterators
 519     fn equal_kmerge_by_lt(mut inputs: Vec<Vec<i16>>) -> bool {
 520         // sort the inputs
 521         for input in &mut inputs {
 522             input.sort();
 523         }
 524         let mut merged = inputs.concat();
 525         merged.sort();
 526         itertools::equal(merged.into_iter(),
 527                          inputs.into_iter().kmerge_by(|x, y| x < y))
 528     }
 529
 530     // Any number of input iterators
 531     fn equal_kmerge_by_le(mut inputs: Vec<Vec<i16>>) -> bool {
 532         // sort the inputs
 533         for input in &mut inputs {
 534             input.sort();
 535         }
 536         let mut merged = inputs.concat();
 537         merged.sort();
 538         itertools::equal(merged.into_iter(),
 539                          inputs.into_iter().kmerge_by(|x, y| x <= y))
 540     }
 541     fn size_kmerge(a: Iter<i16>, b: Iter<i16>, c: Iter<i16>) -> bool {
 542         use itertools::free::kmerge;
 543         correct_size_hint(kmerge(vec![a, b, c]))
 544     }
 545     fn equal_zip_eq(a: Vec<i32>, b: Vec<i32>) -> bool {
 546         let len = std::cmp::min(a.len(), b.len());
 547         let a = &a[..len];
 548         let b = &b[..len];
 549         itertools::equal(zip_eq(a, b), zip(a, b))
 550     }
 551     fn size_zip_longest(a: Iter<i16, Exact>, b: Iter<i16, Exact>) -> bool {
 552         let filt = a.clone().dedup();
 553         let filt2 = b.clone().dedup();
 554         correct_size_hint(filt.zip_longest(b.clone())) &&
 555         correct_size_hint(a.clone().zip_longest(filt2)) &&
 556             exact_size(a.zip_longest(b))
 557     }
 558     fn size_2_zip_longest(a: Iter<i16>, b: Iter<i16>) -> bool {
 559         let it = a.clone().zip_longest(b.clone());
 560         let jt = a.clone().zip_longest(b.clone());
 561         itertools::equal(a.clone(),
 562                          it.filter_map(|elt| match elt {
 563                              EitherOrBoth::Both(x, _) => Some(x),
 564                              EitherOrBoth::Left(x) => Some(x),
 565                              _ => None,
 566                          }
 567                          ))
 568             &&
 569         itertools::equal(b.clone(),
 570                          jt.filter_map(|elt| match elt {
 571                              EitherOrBoth::Both(_, y) => Some(y),
 572                              EitherOrBoth::Right(y) => Some(y),
 573                              _ => None,
 574                          }
 575                          ))
 576     }
 577     fn size_interleave(a: Iter<i16>, b: Iter<i16>) -> bool {
 578         correct_size_hint(a.interleave(b))
 579     }
 580     fn exact_interleave(a: Iter<i16, Exact>, b: Iter<i16, Exact>) -> bool {
 581         exact_size_for_this(a.interleave(b))
 582     }
 583     fn size_interleave_shortest(a: Iter<i16>, b: Iter<i16>) -> bool {
 584         correct_size_hint(a.interleave_shortest(b))
 585     }
 586     fn exact_interleave_shortest(a: Vec<()>, b: Vec<()>) -> bool {
 587         exact_size_for_this(a.iter().interleave_shortest(&b))
 588     }
 589     fn size_intersperse(a: Iter<i16>, x: i16) -> bool {
 590         correct_size_hint(a.intersperse(x))
 591     }
 592     fn equal_intersperse(a: Vec<i32>, x: i32) -> bool {
 593         let mut inter = false;
 594         let mut i = 0;
 595         for elt in a.iter().cloned().intersperse(x) {
 596             if inter {
 597                 if elt != x { return false }
 598             } else {
 599                 if elt != a[i] { return false }
 600                 i += 1;
 601             }
 602             inter = !inter;
 603         }
 604         true
 605     }
 606
 607     fn equal_flatten(a: Vec<Option<i32>>) -> bool {
 608         itertools::equal(flatten(&a),
 609                          a.iter().filter_map(|x| x.as_ref()))
 610     }
 611
 612     fn equal_flatten_vec(a: Vec<Vec<u8>>) -> bool {
 613         itertools::equal(flatten(&a),
 614                          a.iter().flat_map(|x| x))
 615     }
 616
 617     fn equal_combinations_2(a: Vec<u8>) -> bool {
 618         let mut v = Vec::new();
 619         for (i, x) in enumerate(&a) {
 620             for y in &a[i + 1..] {
 621                 v.push((x, y));
 622             }
 623         }
 624         itertools::equal(a.iter().tuple_combinations::<(_, _)>(), v)
 625     }
 626
 627     fn collect_tuple_matches_size(a: Iter<i16>) -> bool {
 628         let size = a.clone().count();
 629         a.collect_tuple::<(_, _, _)>().is_some() == (size == 3)
 630     }
 631 }
 632
 633 quickcheck! {
 634     fn equal_dedup(a: Vec<i32>) -> bool {
 635         let mut b = a.clone();
 636         b.dedup();
 637         itertools::equal(&b, a.iter().dedup())
 638     }
 639 }
 640
 641 quickcheck! {
 642     fn size_dedup(a: Vec<i32>) -> bool {
 643         correct_size_hint(a.iter().dedup())
 644     }
 645 }
 646
 647 quickcheck! {
 648     fn exact_repeatn((n, x): (usize, i32)) -> bool {
 649         let it = itertools::repeat_n(x, n);
 650         exact_size(it)
 651     }
 652 }
 653
 654 quickcheck! {
 655     fn size_put_back(a: Vec<u8>, x: Option<u8>) -> bool {
 656         let mut it = put_back(a.into_iter());
 657         match x {
 658             Some(t) => it.put_back(t),
 659             None => {}
 660         }
 661         correct_size_hint(it)
 662     }
 663 }
 664
 665 quickcheck! {
 666     fn size_put_backn(a: Vec<u8>, b: Vec<u8>) -> bool {
 667         let mut it = put_back_n(a.into_iter());
 668         for elt in b {
 669             it.put_back(elt)
 670         }
 671         correct_size_hint(it)
 672     }
 673 }
 674
 675 quickcheck! {
 676     fn size_tee(a: Vec<u8>) -> bool {
 677         let (mut t1, mut t2) = a.iter().tee();
 678         t1.next();
 679         t1.next();
 680         t2.next();
 681         exact_size(t1) && exact_size(t2)
 682     }
 683 }
 684
 685 quickcheck! {
 686     fn size_tee_2(a: Vec<u8>) -> bool {
 687         let (mut t1, mut t2) = a.iter().dedup().tee();
 688         t1.next();
 689         t1.next();
 690         t2.next();
 691         correct_size_hint(t1) && correct_size_hint(t2)
 692     }
 693 }
 694
 695 quickcheck! {
 696     fn size_take_while_ref(a: Vec<u8>, stop: u8) -> bool {
 697         correct_size_hint(a.iter().take_while_ref(|x| **x != stop))
 698     }
 699 }
 700
 701 quickcheck! {
 702     fn equal_partition(a: Vec<i32>) -> bool {
 703         let mut a = a;
 704         let mut ap = a.clone();
 705         let split_index = itertools::partition(&mut ap, |x| *x >= 0);
 706         let parted = (0..split_index).all(|i| ap[i] >= 0) &&
 707             (split_index..a.len()).all(|i| ap[i] < 0);
 708
 709         a.sort();
 710         ap.sort();
 711         parted && (a == ap)
 712     }
 713 }
 714
 715 quickcheck! {
 716     fn size_combinations(it: Iter<i16>) -> bool {
 717         correct_size_hint(it.tuple_combinations::<(_, _)>())
 718     }
 719 }
 720
 721 quickcheck! {
 722     fn equal_combinations(it: Iter<i16>) -> bool {
 723         let values = it.clone().collect_vec();
 724         let mut cmb = it.tuple_combinations();
 725         for i in 0..values.len() {
 726             for j in i+1..values.len() {
 727                 let pair = (values[i], values[j]);
 728                 if pair != cmb.next().unwrap() {
 729                     return false;
 730                 }
 731             }
 732         }
 733         cmb.next() == None
 734     }
 735 }
 736
 737 quickcheck! {
 738     fn size_pad_tail(it: Iter<i8>, pad: u8) -> bool {
 739         correct_size_hint(it.clone().pad_using(pad as usize, |_| 0)) &&
 740             correct_size_hint(it.dropping(1).rev().pad_using(pad as usize, |_| 0))
 741     }
 742 }
 743
 744 quickcheck! {
 745     fn size_pad_tail2(it: Iter<i8, Exact>, pad: u8) -> bool {
 746         exact_size(it.pad_using(pad as usize, |_| 0))
 747     }
 748 }
 749
 750 quickcheck! {
 751     fn size_unique(it: Iter<i8>) -> bool {
 752         correct_size_hint(it.unique())
 753     }
 754
 755     fn count_unique(it: Vec<i8>, take_first: u8) -> () {
 756         let answer = {
 757             let mut v = it.clone();
 758             v.sort(); v.dedup();
 759             v.len()
 760         };
 761         let mut iter = cloned(&it).unique();
 762         let first_count = (&mut iter).take(take_first as usize).count();
 763         let rest_count = iter.count();
 764         assert_eq!(answer, first_count + rest_count);
 765     }
 766 }
 767
 768 quickcheck! {
 769     fn fuzz_group_by_lazy_1(it: Iter<u8>) -> bool {
 770         let jt = it.clone();
 771         let groups = it.group_by(|k| *k);
 772         let res = itertools::equal(jt, groups.into_iter().flat_map(|(_, x)| x));
 773         res
 774     }
 775 }
 776
 777 quickcheck! {
 778     fn fuzz_group_by_lazy_2(data: Vec<u8>) -> bool {
 779         let groups = data.iter().group_by(|k| *k / 10);
 780         let res = itertools::equal(data.iter(), groups.into_iter().flat_map(|(_, x)| x));
 781         res
 782     }
 783 }
 784
 785 quickcheck! {
 786     fn fuzz_group_by_lazy_3(data: Vec<u8>) -> bool {
 787         let grouper = data.iter().group_by(|k| *k / 10);
 788         let groups = grouper.into_iter().collect_vec();
 789         let res = itertools::equal(data.iter(), groups.into_iter().flat_map(|(_, x)| x));
 790         res
 791     }
 792 }
 793
 794 quickcheck! {
 795     fn fuzz_group_by_lazy_duo(data: Vec<u8>, order: Vec<(bool, bool)>) -> bool {
 796         let grouper = data.iter().group_by(|k| *k / 3);
 797         let mut groups1 = grouper.into_iter();
 798         let mut groups2 = grouper.into_iter();
 799         let mut elts = Vec::<&u8>::new();
 800         let mut old_groups = Vec::new();
 801
 802         let tup1 = |(_, b)| b;
 803         for &(ord, consume_now) in &order {
 804             let iter = &mut [&mut groups1, &mut groups2][ord as usize];
 805             match iter.next() {
 806                 Some((_, gr)) => if consume_now {
 807                     for og in old_groups.drain(..) {
 808                         elts.extend(og);
 809                     }
 810                     elts.extend(gr);
 811                 } else {
 812                     old_groups.push(gr);
 813                 },
 814                 None => break,
 815             }
 816         }
 817         for og in old_groups.drain(..) {
 818             elts.extend(og);
 819         }
 820         for gr in groups1.map(&tup1) { elts.extend(gr); }
 821         for gr in groups2.map(&tup1) { elts.extend(gr); }
 822         itertools::assert_equal(&data, elts);
 823         true
 824     }
 825 }
 826
 827 quickcheck! {
 828     fn equal_chunks_lazy(a: Vec<u8>, size: u8) -> bool {
 829         let mut size = size;
 830         if size == 0 {
 831             size += 1;
 832         }
 833         let chunks = a.iter().chunks(size as usize);
 834         let it = a.chunks(size as usize);
 835         for (a, b) in chunks.into_iter().zip(it) {
 836             if !itertools::equal(a, b) {
 837                 return false;
 838             }
 839         }
 840         true
 841     }
 842 }
 843
 844 quickcheck! {
 845     fn equal_tuple_windows_1(a: Vec<u8>) -> bool {
 846         let x = a.windows(1).map(|s| (&s[0], ));
 847         let y = a.iter().tuple_windows::<(_,)>();
 848         itertools::equal(x, y)
 849     }
 850
 851     fn equal_tuple_windows_2(a: Vec<u8>) -> bool {
 852         let x = a.windows(2).map(|s| (&s[0], &s[1]));
 853         let y = a.iter().tuple_windows::<(_, _)>();
 854         itertools::equal(x, y)
 855     }
 856
 857     fn equal_tuple_windows_3(a: Vec<u8>) -> bool {
 858         let x = a.windows(3).map(|s| (&s[0], &s[1], &s[2]));
 859         let y = a.iter().tuple_windows::<(_, _, _)>();
 860         itertools::equal(x, y)
 861     }
 862
 863     fn equal_tuple_windows_4(a: Vec<u8>) -> bool {
 864         let x = a.windows(4).map(|s| (&s[0], &s[1], &s[2], &s[3]));
 865         let y = a.iter().tuple_windows::<(_, _, _, _)>();
 866         itertools::equal(x, y)
 867     }
 868
 869     fn equal_tuples_1(a: Vec<u8>) -> bool {
 870         let x = a.chunks(1).map(|s| (&s[0], ));
 871         let y = a.iter().tuples::<(_,)>();
 872         itertools::equal(x, y)
 873     }
 874
 875     fn equal_tuples_2(a: Vec<u8>) -> bool {
 876         let x = a.chunks(2).filter(|s| s.len() == 2).map(|s| (&s[0], &s[1]));
 877         let y = a.iter().tuples::<(_, _)>();
 878         itertools::equal(x, y)
 879     }
 880
 881     fn equal_tuples_3(a: Vec<u8>) -> bool {
 882         let x = a.chunks(3).filter(|s| s.len() == 3).map(|s| (&s[0], &s[1], &s[2]));
 883         let y = a.iter().tuples::<(_, _, _)>();
 884         itertools::equal(x, y)
 885     }
 886
 887     fn equal_tuples_4(a: Vec<u8>) -> bool {
 888         let x = a.chunks(4).filter(|s| s.len() == 4).map(|s| (&s[0], &s[1], &s[2], &s[3]));
 889         let y = a.iter().tuples::<(_, _, _, _)>();
 890         itertools::equal(x, y)
 891     }
 892
 893     fn exact_tuple_buffer(a: Vec<u8>) -> bool {
 894         let mut iter = a.iter().tuples::<(_, _, _, _)>();
 895         (&mut iter).last();
 896         let buffer = iter.into_buffer();
 897         assert_eq!(buffer.len(), a.len() % 4);
 898         exact_size(buffer)
 899     }
 900 }
 901
 902 // with_position
 903 quickcheck! {
 904     fn with_position_exact_size_1(a: Vec<u8>) -> bool {
 905         exact_size_for_this(a.iter().with_position())
 906     }
 907     fn with_position_exact_size_2(a: Iter<u8, Exact>) -> bool {
 908         exact_size_for_this(a.with_position())
 909     }
 910 }
 911
 912 quickcheck! {
 913     fn correct_group_map_modulo_key(a: Vec<u8>, modulo: u8) -> () {
 914         let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
 915         let count = a.len();
 916         let lookup = a.into_iter().map(|i| (i % modulo, i)).into_group_map();
 917
 918         assert_eq!(lookup.values().flat_map(|vals| vals.iter()).count(), count);
 919
 920         for (&key, vals) in lookup.iter() {
 921             assert!(vals.iter().all(|&val| val % modulo == key));
 922         }
 923     }
 924 }
 925
 926 /// A peculiar type: Equality compares both tuple items, but ordering only the
 927 /// first item.  This is so we can check the stability property easily.
 928 #[derive(Clone, Debug, PartialEq, Eq)]
 929 struct Val(u32, u32);
 930
 931 impl PartialOrd<Val> for Val {
 932     fn partial_cmp(&self, other: &Val) -> Option<Ordering> {
 933         self.0.partial_cmp(&other.0)
 934     }
 935 }
 936
 937 impl Ord for Val {
 938     fn cmp(&self, other: &Val) -> Ordering {
 939         self.0.cmp(&other.0)
 940     }
 941 }
 942
 943 impl qc::Arbitrary for Val {
 944     fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
 945         let (x, y) = <(u32, u32)>::arbitrary(g);
 946         Val(x, y)
 947     }
 948     fn shrink(&self) -> Box<Iterator<Item = Self>> {
 949         Box::new((self.0, self.1).shrink().map(|(x, y)| Val(x, y)))
 950     }
 951 }
 952
 953 quickcheck! {
 954     fn minmax(a: Vec<Val>) -> bool {
 955         use itertools::MinMaxResult;
 956
 957
 958         let minmax = a.iter().minmax();
 959         let expected = match a.len() {
 960             0 => MinMaxResult::NoElements,
 961             1 => MinMaxResult::OneElement(&a[0]),
 962             _ => MinMaxResult::MinMax(a.iter().min().unwrap(),
 963                                       a.iter().max().unwrap()),
 964         };
 965         minmax == expected
 966     }
 967 }
 968
 969 quickcheck! {
 970     fn minmax_f64(a: Vec<f64>) -> TestResult {
 971         use itertools::MinMaxResult;
 972
 973         if a.iter().any(|x| x.is_nan()) {
 974             return TestResult::discard();
 975         }
 976
 977         let min = cloned(&a).fold1(f64::min);
 978         let max = cloned(&a).fold1(f64::max);
 979
 980         let minmax = cloned(&a).minmax();
 981         let expected = match a.len() {
 982             0 => MinMaxResult::NoElements,
 983             1 => MinMaxResult::OneElement(min.unwrap()),
 984             _ => MinMaxResult::MinMax(min.unwrap(), max.unwrap()),
 985         };
 986         TestResult::from_bool(minmax == expected)
 987     }
 988 }
 989
 990 quickcheck! {
 991     fn tree_fold1_f64(mut a: Vec<f64>) -> TestResult {
 992         fn collapse_adjacent<F>(x: Vec<f64>, mut f: F) -> Vec<f64>
 993             where F: FnMut(f64, f64) -> f64
 994         {
 995             let mut out = Vec::new();
 996             for i in (0..x.len()).step(2) {
 997                 if i == x.len()-1 {
 998                     out.push(x[i])
 999                 } else {
1000                     out.push(f(x[i], x[i+1]));
1001                 }
1002             }
1003             out
1004         }
1005
1006         if a.iter().any(|x| x.is_nan()) {
1007             return TestResult::discard();
1008         }
1009
1010         let actual = a.iter().cloned().tree_fold1(f64::atan2);
1011
1012         while a.len() > 1 {
1013             a = collapse_adjacent(a, f64::atan2);
1014         }
1015         let expected = a.pop();
1016
1017         TestResult::from_bool(actual == expected)
1018     }
1019 }