library/core/tests/iter.rs

   1 // ignore-tidy-filelength
   2
   3 use core::cell::Cell;
   4 use core::convert::TryFrom;
   5 use core::iter::*;
   6
   7 /// An iterator wrapper that panics whenever `next` or `next_back` is called
   8 /// after `None` has been returned.
   9 struct Unfuse<I> {
  10     iter: I,
  11     exhausted: bool,
  12 }
  13
  14 fn unfuse<I: IntoIterator>(iter: I) -> Unfuse<I::IntoIter> {
  15     Unfuse { iter: iter.into_iter(), exhausted: false }
  16 }
  17
  18 impl<I> Iterator for Unfuse<I>
  19 where
  20     I: Iterator,
  21 {
  22     type Item = I::Item;
  23
  24     fn next(&mut self) -> Option<Self::Item> {
  25         assert!(!self.exhausted);
  26         let next = self.iter.next();
  27         self.exhausted = next.is_none();
  28         next
  29     }
  30 }
  31
  32 impl<I> DoubleEndedIterator for Unfuse<I>
  33 where
  34     I: DoubleEndedIterator,
  35 {
  36     fn next_back(&mut self) -> Option<Self::Item> {
  37         assert!(!self.exhausted);
  38         let next = self.iter.next_back();
  39         self.exhausted = next.is_none();
  40         next
  41     }
  42 }
  43
  44 #[test]
  45 fn test_lt() {
  46     let empty: [isize; 0] = [];
  47     let xs = [1, 2, 3];
  48     let ys = [1, 2, 0];
  49
  50     assert!(!xs.iter().lt(ys.iter()));
  51     assert!(!xs.iter().le(ys.iter()));
  52     assert!(xs.iter().gt(ys.iter()));
  53     assert!(xs.iter().ge(ys.iter()));
  54
  55     assert!(ys.iter().lt(xs.iter()));
  56     assert!(ys.iter().le(xs.iter()));
  57     assert!(!ys.iter().gt(xs.iter()));
  58     assert!(!ys.iter().ge(xs.iter()));
  59
  60     assert!(empty.iter().lt(xs.iter()));
  61     assert!(empty.iter().le(xs.iter()));
  62     assert!(!empty.iter().gt(xs.iter()));
  63     assert!(!empty.iter().ge(xs.iter()));
  64
  65     // Sequence with NaN
  66     let u = [1.0f64, 2.0];
  67     let v = [0.0f64 / 0.0, 3.0];
  68
  69     assert!(!u.iter().lt(v.iter()));
  70     assert!(!u.iter().le(v.iter()));
  71     assert!(!u.iter().gt(v.iter()));
  72     assert!(!u.iter().ge(v.iter()));
  73
  74     let a = [0.0f64 / 0.0];
  75     let b = [1.0f64];
  76     let c = [2.0f64];
  77
  78     assert!(a.iter().lt(b.iter()) == (a[0] < b[0]));
  79     assert!(a.iter().le(b.iter()) == (a[0] <= b[0]));
  80     assert!(a.iter().gt(b.iter()) == (a[0] > b[0]));
  81     assert!(a.iter().ge(b.iter()) == (a[0] >= b[0]));
  82
  83     assert!(c.iter().lt(b.iter()) == (c[0] < b[0]));
  84     assert!(c.iter().le(b.iter()) == (c[0] <= b[0]));
  85     assert!(c.iter().gt(b.iter()) == (c[0] > b[0]));
  86     assert!(c.iter().ge(b.iter()) == (c[0] >= b[0]));
  87 }
  88
  89 #[test]
  90 fn test_multi_iter() {
  91     let xs = [1, 2, 3, 4];
  92     let ys = [4, 3, 2, 1];
  93     assert!(xs.iter().eq(ys.iter().rev()));
  94     assert!(xs.iter().lt(xs.iter().skip(2)));
  95 }
  96
  97 #[test]
  98 fn test_cmp_by() {
  99     use core::cmp::Ordering;
 100
 101     let f = |x: i32, y: i32| (x * x).cmp(&y);
 102     let xs = || [1, 2, 3, 4].iter().copied();
 103     let ys = || [1, 4, 16].iter().copied();
 104
 105     assert_eq!(xs().cmp_by(ys(), f), Ordering::Less);
 106     assert_eq!(ys().cmp_by(xs(), f), Ordering::Greater);
 107     assert_eq!(xs().cmp_by(xs().map(|x| x * x), f), Ordering::Equal);
 108     assert_eq!(xs().rev().cmp_by(ys().rev(), f), Ordering::Greater);
 109     assert_eq!(xs().cmp_by(ys().rev(), f), Ordering::Less);
 110     assert_eq!(xs().cmp_by(ys().take(2), f), Ordering::Greater);
 111 }
 112
 113 #[test]
 114 fn test_partial_cmp_by() {
 115     use core::cmp::Ordering;
 116
 117     let f = |x: i32, y: i32| (x * x).partial_cmp(&y);
 118     let xs = || [1, 2, 3, 4].iter().copied();
 119     let ys = || [1, 4, 16].iter().copied();
 120
 121     assert_eq!(xs().partial_cmp_by(ys(), f), Some(Ordering::Less));
 122     assert_eq!(ys().partial_cmp_by(xs(), f), Some(Ordering::Greater));
 123     assert_eq!(xs().partial_cmp_by(xs().map(|x| x * x), f), Some(Ordering::Equal));
 124     assert_eq!(xs().rev().partial_cmp_by(ys().rev(), f), Some(Ordering::Greater));
 125     assert_eq!(xs().partial_cmp_by(xs().rev(), f), Some(Ordering::Less));
 126     assert_eq!(xs().partial_cmp_by(ys().take(2), f), Some(Ordering::Greater));
 127
 128     let f = |x: f64, y: f64| (x * x).partial_cmp(&y);
 129     let xs = || [1.0, 2.0, 3.0, 4.0].iter().copied();
 130     let ys = || [1.0, 4.0, f64::NAN, 16.0].iter().copied();
 131
 132     assert_eq!(xs().partial_cmp_by(ys(), f), None);
 133     assert_eq!(ys().partial_cmp_by(xs(), f), Some(Ordering::Greater));
 134 }
 135
 136 #[test]
 137 fn test_eq_by() {
 138     let f = |x: i32, y: i32| x * x == y;
 139     let xs = || [1, 2, 3, 4].iter().copied();
 140     let ys = || [1, 4, 9, 16].iter().copied();
 141
 142     assert!(xs().eq_by(ys(), f));
 143     assert!(!ys().eq_by(xs(), f));
 144     assert!(!xs().eq_by(xs(), f));
 145     assert!(!ys().eq_by(ys(), f));
 146
 147     assert!(!xs().take(3).eq_by(ys(), f));
 148     assert!(!xs().eq_by(ys().take(3), f));
 149     assert!(xs().take(3).eq_by(ys().take(3), f));
 150 }
 151
 152 #[test]
 153 fn test_counter_from_iter() {
 154     let it = (0..).step_by(5).take(10);
 155     let xs: Vec<isize> = FromIterator::from_iter(it);
 156     assert_eq!(xs, [0, 5, 10, 15, 20, 25, 30, 35, 40, 45]);
 157 }
 158
 159 #[test]
 160 fn test_iterator_chain() {
 161     let xs = [0, 1, 2, 3, 4, 5];
 162     let ys = [30, 40, 50, 60];
 163     let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
 164     let it = xs.iter().chain(&ys);
 165     let mut i = 0;
 166     for &x in it {
 167         assert_eq!(x, expected[i]);
 168         i += 1;
 169     }
 170     assert_eq!(i, expected.len());
 171
 172     let ys = (30..).step_by(10).take(4);
 173     let it = xs.iter().cloned().chain(ys);
 174     let mut i = 0;
 175     for x in it {
 176         assert_eq!(x, expected[i]);
 177         i += 1;
 178     }
 179     assert_eq!(i, expected.len());
 180 }
 181
 182 #[test]
 183 fn test_iterator_chain_advance_by() {
 184     fn test_chain(xs: &[i32], ys: &[i32]) {
 185         let len = xs.len() + ys.len();
 186
 187         for i in 0..xs.len() {
 188             let mut iter = unfuse(xs).chain(unfuse(ys));
 189             iter.advance_by(i).unwrap();
 190             assert_eq!(iter.next(), Some(&xs[i]));
 191             assert_eq!(iter.advance_by(100), Err(len - i - 1));
 192         }
 193
 194         for i in 0..ys.len() {
 195             let mut iter = unfuse(xs).chain(unfuse(ys));
 196             iter.advance_by(xs.len() + i).unwrap();
 197             assert_eq!(iter.next(), Some(&ys[i]));
 198             assert_eq!(iter.advance_by(100), Err(ys.len() - i - 1));
 199         }
 200
 201         let mut iter = xs.iter().chain(ys);
 202         iter.advance_by(len).unwrap();
 203         assert_eq!(iter.next(), None);
 204
 205         let mut iter = xs.iter().chain(ys);
 206         assert_eq!(iter.advance_by(len + 1), Err(len));
 207     }
 208
 209     test_chain(&[], &[]);
 210     test_chain(&[], &[0, 1, 2, 3, 4, 5]);
 211     test_chain(&[0, 1, 2, 3, 4, 5], &[]);
 212     test_chain(&[0, 1, 2, 3, 4, 5], &[30, 40, 50, 60]);
 213 }
 214
 215 #[test]
 216 fn test_iterator_chain_advance_back_by() {
 217     fn test_chain(xs: &[i32], ys: &[i32]) {
 218         let len = xs.len() + ys.len();
 219
 220         for i in 0..ys.len() {
 221             let mut iter = unfuse(xs).chain(unfuse(ys));
 222             iter.advance_back_by(i).unwrap();
 223             assert_eq!(iter.next_back(), Some(&ys[ys.len() - i - 1]));
 224             assert_eq!(iter.advance_back_by(100), Err(len - i - 1));
 225         }
 226
 227         for i in 0..xs.len() {
 228             let mut iter = unfuse(xs).chain(unfuse(ys));
 229             iter.advance_back_by(ys.len() + i).unwrap();
 230             assert_eq!(iter.next_back(), Some(&xs[xs.len() - i - 1]));
 231             assert_eq!(iter.advance_back_by(100), Err(xs.len() - i - 1));
 232         }
 233
 234         let mut iter = xs.iter().chain(ys);
 235         iter.advance_back_by(len).unwrap();
 236         assert_eq!(iter.next_back(), None);
 237
 238         let mut iter = xs.iter().chain(ys);
 239         assert_eq!(iter.advance_back_by(len + 1), Err(len));
 240     }
 241
 242     test_chain(&[], &[]);
 243     test_chain(&[], &[0, 1, 2, 3, 4, 5]);
 244     test_chain(&[0, 1, 2, 3, 4, 5], &[]);
 245     test_chain(&[0, 1, 2, 3, 4, 5], &[30, 40, 50, 60]);
 246 }
 247
 248 #[test]
 249 fn test_iterator_chain_nth() {
 250     let xs = [0, 1, 2, 3, 4, 5];
 251     let ys = [30, 40, 50, 60];
 252     let zs = [];
 253     let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
 254     for (i, x) in expected.iter().enumerate() {
 255         assert_eq!(Some(x), xs.iter().chain(&ys).nth(i));
 256     }
 257     assert_eq!(zs.iter().chain(&xs).nth(0), Some(&0));
 258
 259     let mut it = xs.iter().chain(&zs);
 260     assert_eq!(it.nth(5), Some(&5));
 261     assert_eq!(it.next(), None);
 262 }
 263
 264 #[test]
 265 fn test_iterator_chain_nth_back() {
 266     let xs = [0, 1, 2, 3, 4, 5];
 267     let ys = [30, 40, 50, 60];
 268     let zs = [];
 269     let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
 270     for (i, x) in expected.iter().rev().enumerate() {
 271         assert_eq!(Some(x), xs.iter().chain(&ys).nth_back(i));
 272     }
 273     assert_eq!(zs.iter().chain(&xs).nth_back(0), Some(&5));
 274
 275     let mut it = xs.iter().chain(&zs);
 276     assert_eq!(it.nth_back(5), Some(&0));
 277     assert_eq!(it.next(), None);
 278 }
 279
 280 #[test]
 281 fn test_iterator_chain_last() {
 282     let xs = [0, 1, 2, 3, 4, 5];
 283     let ys = [30, 40, 50, 60];
 284     let zs = [];
 285     assert_eq!(xs.iter().chain(&ys).last(), Some(&60));
 286     assert_eq!(zs.iter().chain(&ys).last(), Some(&60));
 287     assert_eq!(ys.iter().chain(&zs).last(), Some(&60));
 288     assert_eq!(zs.iter().chain(&zs).last(), None);
 289 }
 290
 291 #[test]
 292 fn test_iterator_chain_count() {
 293     let xs = [0, 1, 2, 3, 4, 5];
 294     let ys = [30, 40, 50, 60];
 295     let zs = [];
 296     assert_eq!(xs.iter().chain(&ys).count(), 10);
 297     assert_eq!(zs.iter().chain(&ys).count(), 4);
 298 }
 299
 300 #[test]
 301 fn test_iterator_chain_find() {
 302     let xs = [0, 1, 2, 3, 4, 5];
 303     let ys = [30, 40, 50, 60];
 304     let mut iter = xs.iter().chain(&ys);
 305     assert_eq!(iter.find(|&&i| i == 4), Some(&4));
 306     assert_eq!(iter.next(), Some(&5));
 307     assert_eq!(iter.find(|&&i| i == 40), Some(&40));
 308     assert_eq!(iter.next(), Some(&50));
 309     assert_eq!(iter.find(|&&i| i == 100), None);
 310     assert_eq!(iter.next(), None);
 311 }
 312
 313 struct Toggle {
 314     is_empty: bool,
 315 }
 316
 317 impl Iterator for Toggle {
 318     type Item = ();
 319
 320     // alternates between `None` and `Some(())`
 321     fn next(&mut self) -> Option<Self::Item> {
 322         if self.is_empty {
 323             self.is_empty = false;
 324             None
 325         } else {
 326             self.is_empty = true;
 327             Some(())
 328         }
 329     }
 330
 331     fn size_hint(&self) -> (usize, Option<usize>) {
 332         if self.is_empty { (0, Some(0)) } else { (1, Some(1)) }
 333     }
 334 }
 335
 336 impl DoubleEndedIterator for Toggle {
 337     fn next_back(&mut self) -> Option<Self::Item> {
 338         self.next()
 339     }
 340 }
 341
 342 #[test]
 343 fn test_iterator_chain_size_hint() {
 344     // this chains an iterator of length 0 with an iterator of length 1,
 345     // so after calling `.next()` once, the iterator is empty and the
 346     // state is `ChainState::Back`. `.size_hint()` should now disregard
 347     // the size hint of the left iterator
 348     let mut iter = Toggle { is_empty: true }.chain(once(()));
 349     assert_eq!(iter.next(), Some(()));
 350     assert_eq!(iter.size_hint(), (0, Some(0)));
 351
 352     let mut iter = once(()).chain(Toggle { is_empty: true });
 353     assert_eq!(iter.next_back(), Some(()));
 354     assert_eq!(iter.size_hint(), (0, Some(0)));
 355 }
 356
 357 #[test]
 358 fn test_iterator_chain_unfused() {
 359     // Chain shouldn't be fused in its second iterator, depending on direction
 360     let mut iter = NonFused::new(empty()).chain(Toggle { is_empty: true });
 361     iter.next().unwrap_none();
 362     iter.next().unwrap();
 363     iter.next().unwrap_none();
 364
 365     let mut iter = Toggle { is_empty: true }.chain(NonFused::new(empty()));
 366     iter.next_back().unwrap_none();
 367     iter.next_back().unwrap();
 368     iter.next_back().unwrap_none();
 369 }
 370
 371 #[test]
 372 fn test_zip_nth() {
 373     let xs = [0, 1, 2, 4, 5];
 374     let ys = [10, 11, 12];
 375
 376     let mut it = xs.iter().zip(&ys);
 377     assert_eq!(it.nth(0), Some((&0, &10)));
 378     assert_eq!(it.nth(1), Some((&2, &12)));
 379     assert_eq!(it.nth(0), None);
 380
 381     let mut it = xs.iter().zip(&ys);
 382     assert_eq!(it.nth(3), None);
 383
 384     let mut it = ys.iter().zip(&xs);
 385     assert_eq!(it.nth(3), None);
 386 }
 387
 388 #[test]
 389 fn test_zip_nth_side_effects() {
 390     let mut a = Vec::new();
 391     let mut b = Vec::new();
 392     let value = [1, 2, 3, 4, 5, 6]
 393         .iter()
 394         .cloned()
 395         .map(|n| {
 396             a.push(n);
 397             n * 10
 398         })
 399         .zip([2, 3, 4, 5, 6, 7, 8].iter().cloned().map(|n| {
 400             b.push(n * 100);
 401             n * 1000
 402         }))
 403         .skip(1)
 404         .nth(3);
 405     assert_eq!(value, Some((50, 6000)));
 406     assert_eq!(a, vec![1, 2, 3, 4, 5]);
 407     assert_eq!(b, vec![200, 300, 400, 500, 600]);
 408 }
 409
 410 #[test]
 411 fn test_zip_next_back_side_effects() {
 412     let mut a = Vec::new();
 413     let mut b = Vec::new();
 414     let mut iter = [1, 2, 3, 4, 5, 6]
 415         .iter()
 416         .cloned()
 417         .map(|n| {
 418             a.push(n);
 419             n * 10
 420         })
 421         .zip([2, 3, 4, 5, 6, 7, 8].iter().cloned().map(|n| {
 422             b.push(n * 100);
 423             n * 1000
 424         }));
 425
 426     // The second iterator is one item longer, so `next_back` is called on it
 427     // one more time.
 428     assert_eq!(iter.next_back(), Some((60, 7000)));
 429     assert_eq!(iter.next_back(), Some((50, 6000)));
 430     assert_eq!(iter.next_back(), Some((40, 5000)));
 431     assert_eq!(iter.next_back(), Some((30, 4000)));
 432     assert_eq!(a, vec![6, 5, 4, 3]);
 433     assert_eq!(b, vec![800, 700, 600, 500, 400]);
 434 }
 435
 436 #[test]
 437 fn test_zip_nth_back_side_effects() {
 438     let mut a = Vec::new();
 439     let mut b = Vec::new();
 440     let value = [1, 2, 3, 4, 5, 6]
 441         .iter()
 442         .cloned()
 443         .map(|n| {
 444             a.push(n);
 445             n * 10
 446         })
 447         .zip([2, 3, 4, 5, 6, 7, 8].iter().cloned().map(|n| {
 448             b.push(n * 100);
 449             n * 1000
 450         }))
 451         .nth_back(3);
 452     assert_eq!(value, Some((30, 4000)));
 453     assert_eq!(a, vec![6, 5, 4, 3]);
 454     assert_eq!(b, vec![800, 700, 600, 500, 400]);
 455 }
 456
 457 #[test]
 458 fn test_zip_next_back_side_effects_exhausted() {
 459     let mut a = Vec::new();
 460     let mut b = Vec::new();
 461     let mut iter = [1, 2, 3, 4, 5, 6]
 462         .iter()
 463         .cloned()
 464         .map(|n| {
 465             a.push(n);
 466             n * 10
 467         })
 468         .zip([2, 3, 4].iter().cloned().map(|n| {
 469             b.push(n * 100);
 470             n * 1000
 471         }));
 472
 473     iter.next();
 474     iter.next();
 475     iter.next();
 476     iter.next();
 477     assert_eq!(iter.next_back(), None);
 478     assert_eq!(a, vec![1, 2, 3, 4, 6, 5]);
 479     assert_eq!(b, vec![200, 300, 400]);
 480 }
 481
 482 #[derive(Debug)]
 483 struct CountClone(Cell<i32>);
 484
 485 fn count_clone() -> CountClone {
 486     CountClone(Cell::new(0))
 487 }
 488
 489 impl PartialEq<i32> for CountClone {
 490     fn eq(&self, rhs: &i32) -> bool {
 491         self.0.get() == *rhs
 492     }
 493 }
 494
 495 impl Clone for CountClone {
 496     fn clone(&self) -> Self {
 497         let ret = CountClone(self.0.clone());
 498         let n = self.0.get();
 499         self.0.set(n + 1);
 500         ret
 501     }
 502 }
 503
 504 #[test]
 505 fn test_zip_cloned_sideffectful() {
 506     let xs = [count_clone(), count_clone(), count_clone(), count_clone()];
 507     let ys = [count_clone(), count_clone()];
 508
 509     for _ in xs.iter().cloned().zip(ys.iter().cloned()) {}
 510
 511     assert_eq!(&xs, &[1, 1, 1, 0][..]);
 512     assert_eq!(&ys, &[1, 1][..]);
 513
 514     let xs = [count_clone(), count_clone()];
 515     let ys = [count_clone(), count_clone(), count_clone(), count_clone()];
 516
 517     for _ in xs.iter().cloned().zip(ys.iter().cloned()) {}
 518
 519     assert_eq!(&xs, &[1, 1][..]);
 520     assert_eq!(&ys, &[1, 1, 0, 0][..]);
 521 }
 522
 523 #[test]
 524 fn test_zip_map_sideffectful() {
 525     let mut xs = [0; 6];
 526     let mut ys = [0; 4];
 527
 528     for _ in xs.iter_mut().map(|x| *x += 1).zip(ys.iter_mut().map(|y| *y += 1)) {}
 529
 530     assert_eq!(&xs, &[1, 1, 1, 1, 1, 0]);
 531     assert_eq!(&ys, &[1, 1, 1, 1]);
 532
 533     let mut xs = [0; 4];
 534     let mut ys = [0; 6];
 535
 536     for _ in xs.iter_mut().map(|x| *x += 1).zip(ys.iter_mut().map(|y| *y += 1)) {}
 537
 538     assert_eq!(&xs, &[1, 1, 1, 1]);
 539     assert_eq!(&ys, &[1, 1, 1, 1, 0, 0]);
 540 }
 541
 542 #[test]
 543 fn test_zip_map_rev_sideffectful() {
 544     let mut xs = [0; 6];
 545     let mut ys = [0; 4];
 546
 547     {
 548         let mut it = xs.iter_mut().map(|x| *x += 1).zip(ys.iter_mut().map(|y| *y += 1));
 549         it.next_back();
 550     }
 551     assert_eq!(&xs, &[0, 0, 0, 1, 1, 1]);
 552     assert_eq!(&ys, &[0, 0, 0, 1]);
 553
 554     let mut xs = [0; 6];
 555     let mut ys = [0; 4];
 556
 557     {
 558         let mut it = xs.iter_mut().map(|x| *x += 1).zip(ys.iter_mut().map(|y| *y += 1));
 559         (&mut it).take(5).count();
 560         it.next_back();
 561     }
 562     assert_eq!(&xs, &[1, 1, 1, 1, 1, 1]);
 563     assert_eq!(&ys, &[1, 1, 1, 1]);
 564 }
 565
 566 #[test]
 567 fn test_zip_nested_sideffectful() {
 568     let mut xs = [0; 6];
 569     let ys = [0; 4];
 570
 571     {
 572         // test that it has the side effect nested inside enumerate
 573         let it = xs.iter_mut().map(|x| *x = 1).enumerate().zip(&ys);
 574         it.count();
 575     }
 576     assert_eq!(&xs, &[1, 1, 1, 1, 1, 0]);
 577 }
 578
 579 #[test]
 580 fn test_zip_nth_back_side_effects_exhausted() {
 581     let mut a = Vec::new();
 582     let mut b = Vec::new();
 583     let mut iter = [1, 2, 3, 4, 5, 6]
 584         .iter()
 585         .cloned()
 586         .map(|n| {
 587             a.push(n);
 588             n * 10
 589         })
 590         .zip([2, 3, 4].iter().cloned().map(|n| {
 591             b.push(n * 100);
 592             n * 1000
 593         }));
 594
 595     iter.next();
 596     iter.next();
 597     iter.next();
 598     iter.next();
 599     assert_eq!(iter.nth_back(0), None);
 600     assert_eq!(a, vec![1, 2, 3, 4, 6, 5]);
 601     assert_eq!(b, vec![200, 300, 400]);
 602 }
 603
 604 #[test]
 605 fn test_iterator_step_by() {
 606     // Identity
 607     let mut it = (0..).step_by(1).take(3);
 608     assert_eq!(it.next(), Some(0));
 609     assert_eq!(it.next(), Some(1));
 610     assert_eq!(it.next(), Some(2));
 611     assert_eq!(it.next(), None);
 612
 613     let mut it = (0..).step_by(3).take(4);
 614     assert_eq!(it.next(), Some(0));
 615     assert_eq!(it.next(), Some(3));
 616     assert_eq!(it.next(), Some(6));
 617     assert_eq!(it.next(), Some(9));
 618     assert_eq!(it.next(), None);
 619
 620     let mut it = (0..3).step_by(1);
 621     assert_eq!(it.next_back(), Some(2));
 622     assert_eq!(it.next_back(), Some(1));
 623     assert_eq!(it.next_back(), Some(0));
 624     assert_eq!(it.next_back(), None);
 625
 626     let mut it = (0..11).step_by(3);
 627     assert_eq!(it.next_back(), Some(9));
 628     assert_eq!(it.next_back(), Some(6));
 629     assert_eq!(it.next_back(), Some(3));
 630     assert_eq!(it.next_back(), Some(0));
 631     assert_eq!(it.next_back(), None);
 632 }
 633
 634 #[test]
 635 fn test_iterator_step_by_nth() {
 636     let mut it = (0..16).step_by(5);
 637     assert_eq!(it.nth(0), Some(0));
 638     assert_eq!(it.nth(0), Some(5));
 639     assert_eq!(it.nth(0), Some(10));
 640     assert_eq!(it.nth(0), Some(15));
 641     assert_eq!(it.nth(0), None);
 642
 643     let it = (0..18).step_by(5);
 644     assert_eq!(it.clone().nth(0), Some(0));
 645     assert_eq!(it.clone().nth(1), Some(5));
 646     assert_eq!(it.clone().nth(2), Some(10));
 647     assert_eq!(it.clone().nth(3), Some(15));
 648     assert_eq!(it.clone().nth(4), None);
 649     assert_eq!(it.clone().nth(42), None);
 650 }
 651
 652 #[test]
 653 fn test_iterator_step_by_nth_overflow() {
 654     #[cfg(target_pointer_width = "8")]
 655     type Bigger = u16;
 656     #[cfg(target_pointer_width = "16")]
 657     type Bigger = u32;
 658     #[cfg(target_pointer_width = "32")]
 659     type Bigger = u64;
 660     #[cfg(target_pointer_width = "64")]
 661     type Bigger = u128;
 662
 663     #[derive(Clone)]
 664     struct Test(Bigger);
 665     impl Iterator for &mut Test {
 666         type Item = i32;
 667         fn next(&mut self) -> Option<Self::Item> {
 668             Some(21)
 669         }
 670         fn nth(&mut self, n: usize) -> Option<Self::Item> {
 671             self.0 += n as Bigger + 1;
 672             Some(42)
 673         }
 674     }
 675
 676     let mut it = Test(0);
 677     let root = usize::MAX >> (usize::BITS / 2);
 678     let n = root + 20;
 679     (&mut it).step_by(n).nth(n);
 680     assert_eq!(it.0, n as Bigger * n as Bigger);
 681
 682     // large step
 683     let mut it = Test(0);
 684     (&mut it).step_by(usize::MAX).nth(5);
 685     assert_eq!(it.0, (usize::MAX as Bigger) * 5);
 686
 687     // n + 1 overflows
 688     let mut it = Test(0);
 689     (&mut it).step_by(2).nth(usize::MAX);
 690     assert_eq!(it.0, (usize::MAX as Bigger) * 2);
 691
 692     // n + 1 overflows
 693     let mut it = Test(0);
 694     (&mut it).step_by(1).nth(usize::MAX);
 695     assert_eq!(it.0, (usize::MAX as Bigger) * 1);
 696 }
 697
 698 #[test]
 699 fn test_iterator_step_by_nth_try_fold() {
 700     let mut it = (0..).step_by(10);
 701     assert_eq!(it.try_fold(0, i8::checked_add), None);
 702     assert_eq!(it.next(), Some(60));
 703     assert_eq!(it.try_fold(0, i8::checked_add), None);
 704     assert_eq!(it.next(), Some(90));
 705
 706     let mut it = (100..).step_by(10);
 707     assert_eq!(it.try_fold(50, i8::checked_add), None);
 708     assert_eq!(it.next(), Some(110));
 709
 710     let mut it = (100..=100).step_by(10);
 711     assert_eq!(it.next(), Some(100));
 712     assert_eq!(it.try_fold(0, i8::checked_add), Some(0));
 713 }
 714
 715 #[test]
 716 fn test_iterator_step_by_nth_back() {
 717     let mut it = (0..16).step_by(5);
 718     assert_eq!(it.nth_back(0), Some(15));
 719     assert_eq!(it.nth_back(0), Some(10));
 720     assert_eq!(it.nth_back(0), Some(5));
 721     assert_eq!(it.nth_back(0), Some(0));
 722     assert_eq!(it.nth_back(0), None);
 723
 724     let mut it = (0..16).step_by(5);
 725     assert_eq!(it.next(), Some(0)); // to set `first_take` to `false`
 726     assert_eq!(it.nth_back(0), Some(15));
 727     assert_eq!(it.nth_back(0), Some(10));
 728     assert_eq!(it.nth_back(0), Some(5));
 729     assert_eq!(it.nth_back(0), None);
 730
 731     let it = || (0..18).step_by(5);
 732     assert_eq!(it().nth_back(0), Some(15));
 733     assert_eq!(it().nth_back(1), Some(10));
 734     assert_eq!(it().nth_back(2), Some(5));
 735     assert_eq!(it().nth_back(3), Some(0));
 736     assert_eq!(it().nth_back(4), None);
 737     assert_eq!(it().nth_back(42), None);
 738 }
 739
 740 #[test]
 741 fn test_iterator_step_by_nth_try_rfold() {
 742     let mut it = (0..100).step_by(10);
 743     assert_eq!(it.try_rfold(0, i8::checked_add), None);
 744     assert_eq!(it.next_back(), Some(70));
 745     assert_eq!(it.next(), Some(0));
 746     assert_eq!(it.try_rfold(0, i8::checked_add), None);
 747     assert_eq!(it.next_back(), Some(30));
 748
 749     let mut it = (0..100).step_by(10);
 750     assert_eq!(it.try_rfold(50, i8::checked_add), None);
 751     assert_eq!(it.next_back(), Some(80));
 752
 753     let mut it = (100..=100).step_by(10);
 754     assert_eq!(it.next_back(), Some(100));
 755     assert_eq!(it.try_fold(0, i8::checked_add), Some(0));
 756 }
 757
 758 #[test]
 759 #[should_panic]
 760 fn test_iterator_step_by_zero() {
 761     let mut it = (0..).step_by(0);
 762     it.next();
 763 }
 764
 765 #[test]
 766 fn test_iterator_step_by_size_hint() {
 767     struct StubSizeHint(usize, Option<usize>);
 768     impl Iterator for StubSizeHint {
 769         type Item = ();
 770         fn next(&mut self) -> Option<()> {
 771             self.0 -= 1;
 772             if let Some(ref mut upper) = self.1 {
 773                 *upper -= 1;
 774             }
 775             Some(())
 776         }
 777         fn size_hint(&self) -> (usize, Option<usize>) {
 778             (self.0, self.1)
 779         }
 780     }
 781
 782     // The two checks in each case are needed because the logic
 783     // is different before the first call to `next()`.
 784
 785     let mut it = StubSizeHint(10, Some(10)).step_by(1);
 786     assert_eq!(it.size_hint(), (10, Some(10)));
 787     it.next();
 788     assert_eq!(it.size_hint(), (9, Some(9)));
 789
 790     // exact multiple
 791     let mut it = StubSizeHint(10, Some(10)).step_by(3);
 792     assert_eq!(it.size_hint(), (4, Some(4)));
 793     it.next();
 794     assert_eq!(it.size_hint(), (3, Some(3)));
 795
 796     // larger base range, but not enough to get another element
 797     let mut it = StubSizeHint(12, Some(12)).step_by(3);
 798     assert_eq!(it.size_hint(), (4, Some(4)));
 799     it.next();
 800     assert_eq!(it.size_hint(), (3, Some(3)));
 801
 802     // smaller base range, so fewer resulting elements
 803     let mut it = StubSizeHint(9, Some(9)).step_by(3);
 804     assert_eq!(it.size_hint(), (3, Some(3)));
 805     it.next();
 806     assert_eq!(it.size_hint(), (2, Some(2)));
 807
 808     // infinite upper bound
 809     let mut it = StubSizeHint(usize::MAX, None).step_by(1);
 810     assert_eq!(it.size_hint(), (usize::MAX, None));
 811     it.next();
 812     assert_eq!(it.size_hint(), (usize::MAX - 1, None));
 813
 814     // still infinite with larger step
 815     let mut it = StubSizeHint(7, None).step_by(3);
 816     assert_eq!(it.size_hint(), (3, None));
 817     it.next();
 818     assert_eq!(it.size_hint(), (2, None));
 819
 820     // propagates ExactSizeIterator
 821     let a = [1, 2, 3, 4, 5];
 822     let it = a.iter().step_by(2);
 823     assert_eq!(it.len(), 3);
 824
 825     // Cannot be TrustedLen as a step greater than one makes an iterator
 826     // with (usize::MAX, None) no longer meet the safety requirements
 827     trait TrustedLenCheck {
 828         fn test(self) -> bool;
 829     }
 830     impl<T: Iterator> TrustedLenCheck for T {
 831         default fn test(self) -> bool {
 832             false
 833         }
 834     }
 835     impl<T: TrustedLen> TrustedLenCheck for T {
 836         fn test(self) -> bool {
 837             true
 838         }
 839     }
 840     assert!(TrustedLenCheck::test(a.iter()));
 841     assert!(!TrustedLenCheck::test(a.iter().step_by(1)));
 842 }
 843
 844 #[test]
 845 fn test_filter_map() {
 846     let it = (0..).step_by(1).take(10).filter_map(|x| if x % 2 == 0 { Some(x * x) } else { None });
 847     assert_eq!(it.collect::<Vec<usize>>(), [0 * 0, 2 * 2, 4 * 4, 6 * 6, 8 * 8]);
 848 }
 849
 850 #[test]
 851 fn test_filter_map_fold() {
 852     let xs = [0, 1, 2, 3, 4, 5, 6, 7, 8];
 853     let ys = [0 * 0, 2 * 2, 4 * 4, 6 * 6, 8 * 8];
 854     let it = xs.iter().filter_map(|&x| if x % 2 == 0 { Some(x * x) } else { None });
 855     let i = it.fold(0, |i, x| {
 856         assert_eq!(x, ys[i]);
 857         i + 1
 858     });
 859     assert_eq!(i, ys.len());
 860
 861     let it = xs.iter().filter_map(|&x| if x % 2 == 0 { Some(x * x) } else { None });
 862     let i = it.rfold(ys.len(), |i, x| {
 863         assert_eq!(x, ys[i - 1]);
 864         i - 1
 865     });
 866     assert_eq!(i, 0);
 867 }
 868
 869 #[test]
 870 fn test_iterator_enumerate() {
 871     let xs = [0, 1, 2, 3, 4, 5];
 872     let it = xs.iter().enumerate();
 873     for (i, &x) in it {
 874         assert_eq!(i, x);
 875     }
 876 }
 877
 878 #[test]
 879 fn test_iterator_enumerate_nth() {
 880     let xs = [0, 1, 2, 3, 4, 5];
 881     for (i, &x) in xs.iter().enumerate() {
 882         assert_eq!(i, x);
 883     }
 884
 885     let mut it = xs.iter().enumerate();
 886     while let Some((i, &x)) = it.nth(0) {
 887         assert_eq!(i, x);
 888     }
 889
 890     let mut it = xs.iter().enumerate();
 891     while let Some((i, &x)) = it.nth(1) {
 892         assert_eq!(i, x);
 893     }
 894
 895     let (i, &x) = xs.iter().enumerate().nth(3).unwrap();
 896     assert_eq!(i, x);
 897     assert_eq!(i, 3);
 898 }
 899
 900 #[test]
 901 fn test_iterator_enumerate_nth_back() {
 902     let xs = [0, 1, 2, 3, 4, 5];
 903     let mut it = xs.iter().enumerate();
 904     while let Some((i, &x)) = it.nth_back(0) {
 905         assert_eq!(i, x);
 906     }
 907
 908     let mut it = xs.iter().enumerate();
 909     while let Some((i, &x)) = it.nth_back(1) {
 910         assert_eq!(i, x);
 911     }
 912
 913     let (i, &x) = xs.iter().enumerate().nth_back(3).unwrap();
 914     assert_eq!(i, x);
 915     assert_eq!(i, 2);
 916 }
 917
 918 #[test]
 919 fn test_iterator_enumerate_count() {
 920     let xs = [0, 1, 2, 3, 4, 5];
 921     assert_eq!(xs.iter().enumerate().count(), 6);
 922 }
 923
 924 #[test]
 925 fn test_iterator_enumerate_fold() {
 926     let xs = [0, 1, 2, 3, 4, 5];
 927     let mut it = xs.iter().enumerate();
 928     // steal a couple to get an interesting offset
 929     assert_eq!(it.next(), Some((0, &0)));
 930     assert_eq!(it.next(), Some((1, &1)));
 931     let i = it.fold(2, |i, (j, &x)| {
 932         assert_eq!(i, j);
 933         assert_eq!(x, xs[j]);
 934         i + 1
 935     });
 936     assert_eq!(i, xs.len());
 937
 938     let mut it = xs.iter().enumerate();
 939     assert_eq!(it.next(), Some((0, &0)));
 940     let i = it.rfold(xs.len() - 1, |i, (j, &x)| {
 941         assert_eq!(i, j);
 942         assert_eq!(x, xs[j]);
 943         i - 1
 944     });
 945     assert_eq!(i, 0);
 946 }
 947
 948 #[test]
 949 fn test_iterator_filter_count() {
 950     let xs = [0, 1, 2, 3, 4, 5, 6, 7, 8];
 951     assert_eq!(xs.iter().filter(|&&x| x % 2 == 0).count(), 5);
 952 }
 953
 954 #[test]
 955 fn test_iterator_filter_fold() {
 956     let xs = [0, 1, 2, 3, 4, 5, 6, 7, 8];
 957     let ys = [0, 2, 4, 6, 8];
 958     let it = xs.iter().filter(|&&x| x % 2 == 0);
 959     let i = it.fold(0, |i, &x| {
 960         assert_eq!(x, ys[i]);
 961         i + 1
 962     });
 963     assert_eq!(i, ys.len());
 964
 965     let it = xs.iter().filter(|&&x| x % 2 == 0);
 966     let i = it.rfold(ys.len(), |i, &x| {
 967         assert_eq!(x, ys[i - 1]);
 968         i - 1
 969     });
 970     assert_eq!(i, 0);
 971 }
 972
 973 #[test]
 974 fn test_iterator_peekable() {
 975     let xs = vec![0, 1, 2, 3, 4, 5];
 976
 977     let mut it = xs.iter().cloned().peekable();
 978     assert_eq!(it.len(), 6);
 979     assert_eq!(it.peek().unwrap(), &0);
 980     assert_eq!(it.len(), 6);
 981     assert_eq!(it.next().unwrap(), 0);
 982     assert_eq!(it.len(), 5);
 983     assert_eq!(it.next().unwrap(), 1);
 984     assert_eq!(it.len(), 4);
 985     assert_eq!(it.next().unwrap(), 2);
 986     assert_eq!(it.len(), 3);
 987     assert_eq!(it.peek().unwrap(), &3);
 988     assert_eq!(it.len(), 3);
 989     assert_eq!(it.peek().unwrap(), &3);
 990     assert_eq!(it.len(), 3);
 991     assert_eq!(it.next().unwrap(), 3);
 992     assert_eq!(it.len(), 2);
 993     assert_eq!(it.next().unwrap(), 4);
 994     assert_eq!(it.len(), 1);
 995     assert_eq!(it.peek().unwrap(), &5);
 996     assert_eq!(it.len(), 1);
 997     assert_eq!(it.next().unwrap(), 5);
 998     assert_eq!(it.len(), 0);
 999     assert!(it.peek().is_none());
1000     assert_eq!(it.len(), 0);
1001     assert!(it.next().is_none());
1002     assert_eq!(it.len(), 0);
1003
1004     let mut it = xs.iter().cloned().peekable();
1005     assert_eq!(it.len(), 6);
1006     assert_eq!(it.peek().unwrap(), &0);
1007     assert_eq!(it.len(), 6);
1008     assert_eq!(it.next_back().unwrap(), 5);
1009     assert_eq!(it.len(), 5);
1010     assert_eq!(it.next_back().unwrap(), 4);
1011     assert_eq!(it.len(), 4);
1012     assert_eq!(it.next_back().unwrap(), 3);
1013     assert_eq!(it.len(), 3);
1014     assert_eq!(it.peek().unwrap(), &0);
1015     assert_eq!(it.len(), 3);
1016     assert_eq!(it.peek().unwrap(), &0);
1017     assert_eq!(it.len(), 3);
1018     assert_eq!(it.next_back().unwrap(), 2);
1019     assert_eq!(it.len(), 2);
1020     assert_eq!(it.next_back().unwrap(), 1);
1021     assert_eq!(it.len(), 1);
1022     assert_eq!(it.peek().unwrap(), &0);
1023     assert_eq!(it.len(), 1);
1024     assert_eq!(it.next_back().unwrap(), 0);
1025     assert_eq!(it.len(), 0);
1026     assert!(it.peek().is_none());
1027     assert_eq!(it.len(), 0);
1028     assert!(it.next_back().is_none());
1029     assert_eq!(it.len(), 0);
1030 }
1031
1032 #[test]
1033 fn test_iterator_peekable_count() {
1034     let xs = [0, 1, 2, 3, 4, 5];
1035     let ys = [10];
1036     let zs: [i32; 0] = [];
1037
1038     assert_eq!(xs.iter().peekable().count(), 6);
1039
1040     let mut it = xs.iter().peekable();
1041     assert_eq!(it.peek(), Some(&&0));
1042     assert_eq!(it.count(), 6);
1043
1044     assert_eq!(ys.iter().peekable().count(), 1);
1045
1046     let mut it = ys.iter().peekable();
1047     assert_eq!(it.peek(), Some(&&10));
1048     assert_eq!(it.count(), 1);
1049
1050     assert_eq!(zs.iter().peekable().count(), 0);
1051
1052     let mut it = zs.iter().peekable();
1053     assert_eq!(it.peek(), None);
1054 }
1055
1056 #[test]
1057 fn test_iterator_peekable_nth() {
1058     let xs = [0, 1, 2, 3, 4, 5];
1059     let mut it = xs.iter().peekable();
1060
1061     assert_eq!(it.peek(), Some(&&0));
1062     assert_eq!(it.nth(0), Some(&0));
1063     assert_eq!(it.peek(), Some(&&1));
1064     assert_eq!(it.nth(1), Some(&2));
1065     assert_eq!(it.peek(), Some(&&3));
1066     assert_eq!(it.nth(2), Some(&5));
1067     assert_eq!(it.next(), None);
1068 }
1069
1070 #[test]
1071 fn test_iterator_peekable_last() {
1072     let xs = [0, 1, 2, 3, 4, 5];
1073     let ys = [0];
1074
1075     let mut it = xs.iter().peekable();
1076     assert_eq!(it.peek(), Some(&&0));
1077     assert_eq!(it.last(), Some(&5));
1078
1079     let mut it = ys.iter().peekable();
1080     assert_eq!(it.peek(), Some(&&0));
1081     assert_eq!(it.last(), Some(&0));
1082
1083     let mut it = ys.iter().peekable();
1084     assert_eq!(it.next(), Some(&0));
1085     assert_eq!(it.peek(), None);
1086     assert_eq!(it.last(), None);
1087 }
1088
1089 #[test]
1090 fn test_iterator_peekable_fold() {
1091     let xs = [0, 1, 2, 3, 4, 5];
1092     let mut it = xs.iter().peekable();
1093     assert_eq!(it.peek(), Some(&&0));
1094     let i = it.fold(0, |i, &x| {
1095         assert_eq!(x, xs[i]);
1096         i + 1
1097     });
1098     assert_eq!(i, xs.len());
1099 }
1100
1101 #[test]
1102 fn test_iterator_peekable_rfold() {
1103     let xs = [0, 1, 2, 3, 4, 5];
1104     let mut it = xs.iter().peekable();
1105     assert_eq!(it.peek(), Some(&&0));
1106     let i = it.rfold(0, |i, &x| {
1107         assert_eq!(x, xs[xs.len() - 1 - i]);
1108         i + 1
1109     });
1110     assert_eq!(i, xs.len());
1111 }
1112
1113 #[test]
1114 fn test_iterator_peekable_next_if_eq() {
1115     // first, try on references
1116     let xs = vec!["Heart", "of", "Gold"];
1117     let mut it = xs.into_iter().peekable();
1118     // try before `peek()`
1119     assert_eq!(it.next_if_eq(&"trillian"), None);
1120     assert_eq!(it.next_if_eq(&"Heart"), Some("Heart"));
1121     // try after peek()
1122     assert_eq!(it.peek(), Some(&"of"));
1123     assert_eq!(it.next_if_eq(&"of"), Some("of"));
1124     assert_eq!(it.next_if_eq(&"zaphod"), None);
1125     // make sure `next()` still behaves
1126     assert_eq!(it.next(), Some("Gold"));
1127
1128     // make sure comparison works for owned values
1129     let xs = vec![String::from("Ludicrous"), "speed".into()];
1130     let mut it = xs.into_iter().peekable();
1131     // make sure basic functionality works
1132     assert_eq!(it.next_if_eq("Ludicrous"), Some("Ludicrous".into()));
1133     assert_eq!(it.next_if_eq("speed"), Some("speed".into()));
1134     assert_eq!(it.next_if_eq(""), None);
1135 }
1136
1137 #[test]
1138 fn test_iterator_peekable_mut() {
1139     let mut it = vec![1, 2, 3].into_iter().peekable();
1140     if let Some(p) = it.peek_mut() {
1141         if *p == 1 {
1142             *p = 5;
1143         }
1144     }
1145     assert_eq!(it.collect::<Vec<_>>(), vec![5, 2, 3]);
1146 }
1147
1148 /// This is an iterator that follows the Iterator contract,
1149 /// but it is not fused. After having returned None once, it will start
1150 /// producing elements if .next() is called again.
1151 pub struct CycleIter<'a, T> {
1152     index: usize,
1153     data: &'a [T],
1154 }
1155
1156 pub fn cycle<T>(data: &[T]) -> CycleIter<'_, T> {
1157     CycleIter { index: 0, data }
1158 }
1159
1160 impl<'a, T> Iterator for CycleIter<'a, T> {
1161     type Item = &'a T;
1162     fn next(&mut self) -> Option<Self::Item> {
1163         let elt = self.data.get(self.index);
1164         self.index += 1;
1165         self.index %= 1 + self.data.len();
1166         elt
1167     }
1168 }
1169
1170 #[test]
1171 fn test_iterator_peekable_remember_peek_none_1() {
1172     // Check that the loop using .peek() terminates
1173     let data = [1, 2, 3];
1174     let mut iter = cycle(&data).peekable();
1175
1176     let mut n = 0;
1177     while let Some(_) = iter.next() {
1178         let is_the_last = iter.peek().is_none();
1179         assert_eq!(is_the_last, n == data.len() - 1);
1180         n += 1;
1181         if n > data.len() {
1182             break;
1183         }
1184     }
1185     assert_eq!(n, data.len());
1186 }
1187
1188 #[test]
1189 fn test_iterator_peekable_remember_peek_none_2() {
1190     let data = [0];
1191     let mut iter = cycle(&data).peekable();
1192     iter.next();
1193     assert_eq!(iter.peek(), None);
1194     assert_eq!(iter.last(), None);
1195 }
1196
1197 #[test]
1198 fn test_iterator_peekable_remember_peek_none_3() {
1199     let data = [0];
1200     let mut iter = cycle(&data).peekable();
1201     iter.peek();
1202     assert_eq!(iter.nth(0), Some(&0));
1203
1204     let mut iter = cycle(&data).peekable();
1205     iter.next();
1206     assert_eq!(iter.peek(), None);
1207     assert_eq!(iter.nth(0), None);
1208 }
1209
1210 #[test]
1211 fn test_iterator_take_while() {
1212     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1213     let ys = [0, 1, 2, 3, 5, 13];
1214     let it = xs.iter().take_while(|&x| *x < 15);
1215     let mut i = 0;
1216     for x in it {
1217         assert_eq!(*x, ys[i]);
1218         i += 1;
1219     }
1220     assert_eq!(i, ys.len());
1221 }
1222
1223 #[test]
1224 fn test_iterator_skip_while() {
1225     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1226     let ys = [15, 16, 17, 19];
1227     let it = xs.iter().skip_while(|&x| *x < 15);
1228     let mut i = 0;
1229     for x in it {
1230         assert_eq!(*x, ys[i]);
1231         i += 1;
1232     }
1233     assert_eq!(i, ys.len());
1234 }
1235
1236 #[test]
1237 fn test_iterator_skip_while_fold() {
1238     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1239     let ys = [15, 16, 17, 19];
1240     let it = xs.iter().skip_while(|&x| *x < 15);
1241     let i = it.fold(0, |i, &x| {
1242         assert_eq!(x, ys[i]);
1243         i + 1
1244     });
1245     assert_eq!(i, ys.len());
1246
1247     let mut it = xs.iter().skip_while(|&x| *x < 15);
1248     assert_eq!(it.next(), Some(&ys[0])); // process skips before folding
1249     let i = it.fold(1, |i, &x| {
1250         assert_eq!(x, ys[i]);
1251         i + 1
1252     });
1253     assert_eq!(i, ys.len());
1254 }
1255
1256 #[test]
1257 fn test_iterator_skip() {
1258     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1259     let ys = [13, 15, 16, 17, 19, 20, 30];
1260     let mut it = xs.iter().skip(5);
1261     let mut i = 0;
1262     while let Some(&x) = it.next() {
1263         assert_eq!(x, ys[i]);
1264         i += 1;
1265         assert_eq!(it.len(), xs.len() - 5 - i);
1266     }
1267     assert_eq!(i, ys.len());
1268     assert_eq!(it.len(), 0);
1269 }
1270
1271 #[test]
1272 fn test_iterator_skip_doubleended() {
1273     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1274     let mut it = xs.iter().rev().skip(5);
1275     assert_eq!(it.next(), Some(&15));
1276     assert_eq!(it.by_ref().rev().next(), Some(&0));
1277     assert_eq!(it.next(), Some(&13));
1278     assert_eq!(it.by_ref().rev().next(), Some(&1));
1279     assert_eq!(it.next(), Some(&5));
1280     assert_eq!(it.by_ref().rev().next(), Some(&2));
1281     assert_eq!(it.next(), Some(&3));
1282     assert_eq!(it.next(), None);
1283     let mut it = xs.iter().rev().skip(5).rev();
1284     assert_eq!(it.next(), Some(&0));
1285     assert_eq!(it.rev().next(), Some(&15));
1286     let mut it_base = xs.iter();
1287     {
1288         let mut it = it_base.by_ref().skip(5).rev();
1289         assert_eq!(it.next(), Some(&30));
1290         assert_eq!(it.next(), Some(&20));
1291         assert_eq!(it.next(), Some(&19));
1292         assert_eq!(it.next(), Some(&17));
1293         assert_eq!(it.next(), Some(&16));
1294         assert_eq!(it.next(), Some(&15));
1295         assert_eq!(it.next(), Some(&13));
1296         assert_eq!(it.next(), None);
1297     }
1298     // make sure the skipped parts have not been consumed
1299     assert_eq!(it_base.next(), Some(&0));
1300     assert_eq!(it_base.next(), Some(&1));
1301     assert_eq!(it_base.next(), Some(&2));
1302     assert_eq!(it_base.next(), Some(&3));
1303     assert_eq!(it_base.next(), Some(&5));
1304     assert_eq!(it_base.next(), None);
1305     let it = xs.iter().skip(5).rev();
1306     assert_eq!(it.last(), Some(&13));
1307 }
1308
1309 #[test]
1310 fn test_iterator_skip_nth() {
1311     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1312
1313     let mut it = xs.iter().skip(0);
1314     assert_eq!(it.nth(0), Some(&0));
1315     assert_eq!(it.nth(1), Some(&2));
1316
1317     let mut it = xs.iter().skip(5);
1318     assert_eq!(it.nth(0), Some(&13));
1319     assert_eq!(it.nth(1), Some(&16));
1320
1321     let mut it = xs.iter().skip(12);
1322     assert_eq!(it.nth(0), None);
1323 }
1324
1325 #[test]
1326 fn test_iterator_skip_count() {
1327     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1328
1329     assert_eq!(xs.iter().skip(0).count(), 12);
1330     assert_eq!(xs.iter().skip(1).count(), 11);
1331     assert_eq!(xs.iter().skip(11).count(), 1);
1332     assert_eq!(xs.iter().skip(12).count(), 0);
1333     assert_eq!(xs.iter().skip(13).count(), 0);
1334 }
1335
1336 #[test]
1337 fn test_iterator_skip_last() {
1338     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1339
1340     assert_eq!(xs.iter().skip(0).last(), Some(&30));
1341     assert_eq!(xs.iter().skip(1).last(), Some(&30));
1342     assert_eq!(xs.iter().skip(11).last(), Some(&30));
1343     assert_eq!(xs.iter().skip(12).last(), None);
1344     assert_eq!(xs.iter().skip(13).last(), None);
1345
1346     let mut it = xs.iter().skip(5);
1347     assert_eq!(it.next(), Some(&13));
1348     assert_eq!(it.last(), Some(&30));
1349 }
1350
1351 #[test]
1352 fn test_iterator_skip_fold() {
1353     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1354     let ys = [13, 15, 16, 17, 19, 20, 30];
1355
1356     let it = xs.iter().skip(5);
1357     let i = it.fold(0, |i, &x| {
1358         assert_eq!(x, ys[i]);
1359         i + 1
1360     });
1361     assert_eq!(i, ys.len());
1362
1363     let mut it = xs.iter().skip(5);
1364     assert_eq!(it.next(), Some(&ys[0])); // process skips before folding
1365     let i = it.fold(1, |i, &x| {
1366         assert_eq!(x, ys[i]);
1367         i + 1
1368     });
1369     assert_eq!(i, ys.len());
1370
1371     let it = xs.iter().skip(5);
1372     let i = it.rfold(ys.len(), |i, &x| {
1373         let i = i - 1;
1374         assert_eq!(x, ys[i]);
1375         i
1376     });
1377     assert_eq!(i, 0);
1378
1379     let mut it = xs.iter().skip(5);
1380     assert_eq!(it.next(), Some(&ys[0])); // process skips before folding
1381     let i = it.rfold(ys.len(), |i, &x| {
1382         let i = i - 1;
1383         assert_eq!(x, ys[i]);
1384         i
1385     });
1386     assert_eq!(i, 1);
1387 }
1388
1389 #[test]
1390 fn test_iterator_take() {
1391     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1392     let ys = [0, 1, 2, 3, 5];
1393
1394     let mut it = xs.iter().take(ys.len());
1395     let mut i = 0;
1396     assert_eq!(it.len(), ys.len());
1397     while let Some(&x) = it.next() {
1398         assert_eq!(x, ys[i]);
1399         i += 1;
1400         assert_eq!(it.len(), ys.len() - i);
1401     }
1402     assert_eq!(i, ys.len());
1403     assert_eq!(it.len(), 0);
1404
1405     let mut it = xs.iter().take(ys.len());
1406     let mut i = 0;
1407     assert_eq!(it.len(), ys.len());
1408     while let Some(&x) = it.next_back() {
1409         i += 1;
1410         assert_eq!(x, ys[ys.len() - i]);
1411         assert_eq!(it.len(), ys.len() - i);
1412     }
1413     assert_eq!(i, ys.len());
1414     assert_eq!(it.len(), 0);
1415 }
1416
1417 #[test]
1418 fn test_iterator_take_nth() {
1419     let xs = [0, 1, 2, 4, 5];
1420     let mut it = xs.iter();
1421     {
1422         let mut take = it.by_ref().take(3);
1423         let mut i = 0;
1424         while let Some(&x) = take.nth(0) {
1425             assert_eq!(x, i);
1426             i += 1;
1427         }
1428     }
1429     assert_eq!(it.nth(1), Some(&5));
1430     assert_eq!(it.nth(0), None);
1431
1432     let xs = [0, 1, 2, 3, 4];
1433     let mut it = xs.iter().take(7);
1434     let mut i = 1;
1435     while let Some(&x) = it.nth(1) {
1436         assert_eq!(x, i);
1437         i += 2;
1438     }
1439 }
1440
1441 #[test]
1442 fn test_iterator_take_nth_back() {
1443     let xs = [0, 1, 2, 4, 5];
1444     let mut it = xs.iter();
1445     {
1446         let mut take = it.by_ref().take(3);
1447         let mut i = 0;
1448         while let Some(&x) = take.nth_back(0) {
1449             i += 1;
1450             assert_eq!(x, 3 - i);
1451         }
1452     }
1453     assert_eq!(it.nth_back(0), None);
1454
1455     let xs = [0, 1, 2, 3, 4];
1456     let mut it = xs.iter().take(7);
1457     assert_eq!(it.nth_back(1), Some(&3));
1458     assert_eq!(it.nth_back(1), Some(&1));
1459     assert_eq!(it.nth_back(1), None);
1460 }
1461
1462 #[test]
1463 fn test_iterator_take_short() {
1464     let xs = [0, 1, 2, 3];
1465
1466     let mut it = xs.iter().take(5);
1467     let mut i = 0;
1468     assert_eq!(it.len(), xs.len());
1469     while let Some(&x) = it.next() {
1470         assert_eq!(x, xs[i]);
1471         i += 1;
1472         assert_eq!(it.len(), xs.len() - i);
1473     }
1474     assert_eq!(i, xs.len());
1475     assert_eq!(it.len(), 0);
1476
1477     let mut it = xs.iter().take(5);
1478     let mut i = 0;
1479     assert_eq!(it.len(), xs.len());
1480     while let Some(&x) = it.next_back() {
1481         i += 1;
1482         assert_eq!(x, xs[xs.len() - i]);
1483         assert_eq!(it.len(), xs.len() - i);
1484     }
1485     assert_eq!(i, xs.len());
1486     assert_eq!(it.len(), 0);
1487 }
1488
1489 #[test]
1490 fn test_iterator_scan() {
1491     // test the type inference
1492     fn add(old: &mut isize, new: &usize) -> Option<f64> {
1493         *old += *new as isize;
1494         Some(*old as f64)
1495     }
1496     let xs = [0, 1, 2, 3, 4];
1497     let ys = [0f64, 1.0, 3.0, 6.0, 10.0];
1498
1499     let it = xs.iter().scan(0, add);
1500     let mut i = 0;
1501     for x in it {
1502         assert_eq!(x, ys[i]);
1503         i += 1;
1504     }
1505     assert_eq!(i, ys.len());
1506 }
1507
1508 #[test]
1509 fn test_iterator_flat_map() {
1510     let xs = [0, 3, 6];
1511     let ys = [0, 1, 2, 3, 4, 5, 6, 7, 8];
1512     let it = xs.iter().flat_map(|&x| (x..).step_by(1).take(3));
1513     let mut i = 0;
1514     for x in it {
1515         assert_eq!(x, ys[i]);
1516         i += 1;
1517     }
1518     assert_eq!(i, ys.len());
1519 }
1520
1521 /// Tests `FlatMap::fold` with items already picked off the front and back,
1522 /// to make sure all parts of the `FlatMap` are folded correctly.
1523 #[test]
1524 fn test_iterator_flat_map_fold() {
1525     let xs = [0, 3, 6];
1526     let ys = [1, 2, 3, 4, 5, 6, 7];
1527     let mut it = xs.iter().flat_map(|&x| x..x + 3);
1528     assert_eq!(it.next(), Some(0));
1529     assert_eq!(it.next_back(), Some(8));
1530     let i = it.fold(0, |i, x| {
1531         assert_eq!(x, ys[i]);
1532         i + 1
1533     });
1534     assert_eq!(i, ys.len());
1535
1536     let mut it = xs.iter().flat_map(|&x| x..x + 3);
1537     assert_eq!(it.next(), Some(0));
1538     assert_eq!(it.next_back(), Some(8));
1539     let i = it.rfold(ys.len(), |i, x| {
1540         assert_eq!(x, ys[i - 1]);
1541         i - 1
1542     });
1543     assert_eq!(i, 0);
1544 }
1545
1546 #[test]
1547 fn test_iterator_flatten() {
1548     let xs = [0, 3, 6];
1549     let ys = [0, 1, 2, 3, 4, 5, 6, 7, 8];
1550     let it = xs.iter().map(|&x| (x..).step_by(1).take(3)).flatten();
1551     let mut i = 0;
1552     for x in it {
1553         assert_eq!(x, ys[i]);
1554         i += 1;
1555     }
1556     assert_eq!(i, ys.len());
1557 }
1558
1559 /// Tests `Flatten::fold` with items already picked off the front and back,
1560 /// to make sure all parts of the `Flatten` are folded correctly.
1561 #[test]
1562 fn test_iterator_flatten_fold() {
1563     let xs = [0, 3, 6];
1564     let ys = [1, 2, 3, 4, 5, 6, 7];
1565     let mut it = xs.iter().map(|&x| x..x + 3).flatten();
1566     assert_eq!(it.next(), Some(0));
1567     assert_eq!(it.next_back(), Some(8));
1568     let i = it.fold(0, |i, x| {
1569         assert_eq!(x, ys[i]);
1570         i + 1
1571     });
1572     assert_eq!(i, ys.len());
1573
1574     let mut it = xs.iter().map(|&x| x..x + 3).flatten();
1575     assert_eq!(it.next(), Some(0));
1576     assert_eq!(it.next_back(), Some(8));
1577     let i = it.rfold(ys.len(), |i, x| {
1578         assert_eq!(x, ys[i - 1]);
1579         i - 1
1580     });
1581     assert_eq!(i, 0);
1582 }
1583
1584 #[test]
1585 fn test_inspect() {
1586     let xs = [1, 2, 3, 4];
1587     let mut n = 0;
1588
1589     let ys = xs.iter().cloned().inspect(|_| n += 1).collect::<Vec<usize>>();
1590
1591     assert_eq!(n, xs.len());
1592     assert_eq!(&xs[..], &ys[..]);
1593 }
1594
1595 #[test]
1596 fn test_inspect_fold() {
1597     let xs = [1, 2, 3, 4];
1598     let mut n = 0;
1599     {
1600         let it = xs.iter().inspect(|_| n += 1);
1601         let i = it.fold(0, |i, &x| {
1602             assert_eq!(x, xs[i]);
1603             i + 1
1604         });
1605         assert_eq!(i, xs.len());
1606     }
1607     assert_eq!(n, xs.len());
1608
1609     let mut n = 0;
1610     {
1611         let it = xs.iter().inspect(|_| n += 1);
1612         let i = it.rfold(xs.len(), |i, &x| {
1613             assert_eq!(x, xs[i - 1]);
1614             i - 1
1615         });
1616         assert_eq!(i, 0);
1617     }
1618     assert_eq!(n, xs.len());
1619 }
1620
1621 #[test]
1622 fn test_cycle() {
1623     let cycle_len = 3;
1624     let it = (0..).step_by(1).take(cycle_len).cycle();
1625     assert_eq!(it.size_hint(), (usize::MAX, None));
1626     for (i, x) in it.take(100).enumerate() {
1627         assert_eq!(i % cycle_len, x);
1628     }
1629
1630     let mut it = (0..).step_by(1).take(0).cycle();
1631     assert_eq!(it.size_hint(), (0, Some(0)));
1632     assert_eq!(it.next(), None);
1633
1634     assert_eq!(empty::<i32>().cycle().fold(0, |acc, x| acc + x), 0);
1635
1636     assert_eq!(once(1).cycle().skip(1).take(4).fold(0, |acc, x| acc + x), 4);
1637
1638     assert_eq!((0..10).cycle().take(5).sum::<i32>(), 10);
1639     assert_eq!((0..10).cycle().take(15).sum::<i32>(), 55);
1640     assert_eq!((0..10).cycle().take(25).sum::<i32>(), 100);
1641
1642     let mut iter = (0..10).cycle();
1643     iter.nth(14);
1644     assert_eq!(iter.take(8).sum::<i32>(), 38);
1645
1646     let mut iter = (0..10).cycle();
1647     iter.nth(9);
1648     assert_eq!(iter.take(3).sum::<i32>(), 3);
1649 }
1650
1651 #[test]
1652 fn test_iterator_nth() {
1653     let v: &[_] = &[0, 1, 2, 3, 4];
1654     for i in 0..v.len() {
1655         assert_eq!(v.iter().nth(i).unwrap(), &v[i]);
1656     }
1657     assert_eq!(v.iter().nth(v.len()), None);
1658 }
1659
1660 #[test]
1661 fn test_iterator_nth_back() {
1662     let v: &[_] = &[0, 1, 2, 3, 4];
1663     for i in 0..v.len() {
1664         assert_eq!(v.iter().nth_back(i).unwrap(), &v[v.len() - 1 - i]);
1665     }
1666     assert_eq!(v.iter().nth_back(v.len()), None);
1667 }
1668
1669 #[test]
1670 fn test_iterator_rev_nth_back() {
1671     let v: &[_] = &[0, 1, 2, 3, 4];
1672     for i in 0..v.len() {
1673         assert_eq!(v.iter().rev().nth_back(i).unwrap(), &v[i]);
1674     }
1675     assert_eq!(v.iter().rev().nth_back(v.len()), None);
1676 }
1677
1678 #[test]
1679 fn test_iterator_rev_nth() {
1680     let v: &[_] = &[0, 1, 2, 3, 4];
1681     for i in 0..v.len() {
1682         assert_eq!(v.iter().rev().nth(i).unwrap(), &v[v.len() - 1 - i]);
1683     }
1684     assert_eq!(v.iter().rev().nth(v.len()), None);
1685 }
1686
1687 #[test]
1688 fn test_iterator_advance_by() {
1689     let v: &[_] = &[0, 1, 2, 3, 4];
1690
1691     for i in 0..v.len() {
1692         let mut iter = v.iter();
1693         assert_eq!(iter.advance_by(i), Ok(()));
1694         assert_eq!(iter.next().unwrap(), &v[i]);
1695         assert_eq!(iter.advance_by(100), Err(v.len() - 1 - i));
1696     }
1697
1698     assert_eq!(v.iter().advance_by(v.len()), Ok(()));
1699     assert_eq!(v.iter().advance_by(100), Err(v.len()));
1700 }
1701
1702 #[test]
1703 fn test_iterator_advance_back_by() {
1704     let v: &[_] = &[0, 1, 2, 3, 4];
1705
1706     for i in 0..v.len() {
1707         let mut iter = v.iter();
1708         assert_eq!(iter.advance_back_by(i), Ok(()));
1709         assert_eq!(iter.next_back().unwrap(), &v[v.len() - 1 - i]);
1710         assert_eq!(iter.advance_back_by(100), Err(v.len() - 1 - i));
1711     }
1712
1713     assert_eq!(v.iter().advance_back_by(v.len()), Ok(()));
1714     assert_eq!(v.iter().advance_back_by(100), Err(v.len()));
1715 }
1716
1717 #[test]
1718 fn test_iterator_rev_advance_by() {
1719     let v: &[_] = &[0, 1, 2, 3, 4];
1720
1721     for i in 0..v.len() {
1722         let mut iter = v.iter().rev();
1723         assert_eq!(iter.advance_by(i), Ok(()));
1724         assert_eq!(iter.next().unwrap(), &v[v.len() - 1 - i]);
1725         assert_eq!(iter.advance_by(100), Err(v.len() - 1 - i));
1726     }
1727
1728     assert_eq!(v.iter().rev().advance_by(v.len()), Ok(()));
1729     assert_eq!(v.iter().rev().advance_by(100), Err(v.len()));
1730 }
1731
1732 #[test]
1733 fn test_iterator_rev_advance_back_by() {
1734     let v: &[_] = &[0, 1, 2, 3, 4];
1735
1736     for i in 0..v.len() {
1737         let mut iter = v.iter().rev();
1738         assert_eq!(iter.advance_back_by(i), Ok(()));
1739         assert_eq!(iter.next_back().unwrap(), &v[i]);
1740         assert_eq!(iter.advance_back_by(100), Err(v.len() - 1 - i));
1741     }
1742
1743     assert_eq!(v.iter().rev().advance_back_by(v.len()), Ok(()));
1744     assert_eq!(v.iter().rev().advance_back_by(100), Err(v.len()));
1745 }
1746
1747 #[test]
1748 fn test_iterator_last() {
1749     let v: &[_] = &[0, 1, 2, 3, 4];
1750     assert_eq!(v.iter().last().unwrap(), &4);
1751     assert_eq!(v[..1].iter().last().unwrap(), &0);
1752 }
1753
1754 #[test]
1755 fn test_iterator_len() {
1756     let v: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1757     assert_eq!(v[..4].iter().count(), 4);
1758     assert_eq!(v[..10].iter().count(), 10);
1759     assert_eq!(v[..0].iter().count(), 0);
1760 }
1761
1762 #[test]
1763 fn test_iterator_sum() {
1764     let v: &[i32] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1765     assert_eq!(v[..4].iter().cloned().sum::<i32>(), 6);
1766     assert_eq!(v.iter().cloned().sum::<i32>(), 55);
1767     assert_eq!(v[..0].iter().cloned().sum::<i32>(), 0);
1768 }
1769
1770 #[test]
1771 fn test_iterator_sum_result() {
1772     let v: &[Result<i32, ()>] = &[Ok(1), Ok(2), Ok(3), Ok(4)];
1773     assert_eq!(v.iter().cloned().sum::<Result<i32, _>>(), Ok(10));
1774     let v: &[Result<i32, ()>] = &[Ok(1), Err(()), Ok(3), Ok(4)];
1775     assert_eq!(v.iter().cloned().sum::<Result<i32, _>>(), Err(()));
1776
1777     #[derive(PartialEq, Debug)]
1778     struct S(Result<i32, ()>);
1779
1780     impl Sum<Result<i32, ()>> for S {
1781         fn sum<I: Iterator<Item = Result<i32, ()>>>(mut iter: I) -> Self {
1782             // takes the sum by repeatedly calling `next` on `iter`,
1783             // thus testing that repeated calls to `ResultShunt::try_fold`
1784             // produce the expected results
1785             Self(iter.by_ref().sum())
1786         }
1787     }
1788
1789     let v: &[Result<i32, ()>] = &[Ok(1), Ok(2), Ok(3), Ok(4)];
1790     assert_eq!(v.iter().cloned().sum::<S>(), S(Ok(10)));
1791     let v: &[Result<i32, ()>] = &[Ok(1), Err(()), Ok(3), Ok(4)];
1792     assert_eq!(v.iter().cloned().sum::<S>(), S(Err(())));
1793 }
1794
1795 #[test]
1796 fn test_iterator_sum_option() {
1797     let v: &[Option<i32>] = &[Some(1), Some(2), Some(3), Some(4)];
1798     assert_eq!(v.iter().cloned().sum::<Option<i32>>(), Some(10));
1799     let v: &[Option<i32>] = &[Some(1), None, Some(3), Some(4)];
1800     assert_eq!(v.iter().cloned().sum::<Option<i32>>(), None);
1801 }
1802
1803 #[test]
1804 fn test_iterator_product() {
1805     let v: &[i32] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1806     assert_eq!(v[..4].iter().cloned().product::<i32>(), 0);
1807     assert_eq!(v[1..5].iter().cloned().product::<i32>(), 24);
1808     assert_eq!(v[..0].iter().cloned().product::<i32>(), 1);
1809 }
1810
1811 #[test]
1812 fn test_iterator_product_result() {
1813     let v: &[Result<i32, ()>] = &[Ok(1), Ok(2), Ok(3), Ok(4)];
1814     assert_eq!(v.iter().cloned().product::<Result<i32, _>>(), Ok(24));
1815     let v: &[Result<i32, ()>] = &[Ok(1), Err(()), Ok(3), Ok(4)];
1816     assert_eq!(v.iter().cloned().product::<Result<i32, _>>(), Err(()));
1817 }
1818
1819 /// A wrapper struct that implements `Eq` and `Ord` based on the wrapped
1820 /// integer modulo 3. Used to test that `Iterator::max` and `Iterator::min`
1821 /// return the correct element if some of them are equal.
1822 #[derive(Debug)]
1823 struct Mod3(i32);
1824
1825 impl PartialEq for Mod3 {
1826     fn eq(&self, other: &Self) -> bool {
1827         self.0 % 3 == other.0 % 3
1828     }
1829 }
1830
1831 impl Eq for Mod3 {}
1832
1833 impl PartialOrd for Mod3 {
1834     fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
1835         Some(self.cmp(other))
1836     }
1837 }
1838
1839 impl Ord for Mod3 {
1840     fn cmp(&self, other: &Self) -> core::cmp::Ordering {
1841         (self.0 % 3).cmp(&(other.0 % 3))
1842     }
1843 }
1844
1845 #[test]
1846 fn test_iterator_product_option() {
1847     let v: &[Option<i32>] = &[Some(1), Some(2), Some(3), Some(4)];
1848     assert_eq!(v.iter().cloned().product::<Option<i32>>(), Some(24));
1849     let v: &[Option<i32>] = &[Some(1), None, Some(3), Some(4)];
1850     assert_eq!(v.iter().cloned().product::<Option<i32>>(), None);
1851 }
1852
1853 #[test]
1854 fn test_iterator_max() {
1855     let v: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1856     assert_eq!(v[..4].iter().cloned().max(), Some(3));
1857     assert_eq!(v.iter().cloned().max(), Some(10));
1858     assert_eq!(v[..0].iter().cloned().max(), None);
1859     assert_eq!(v.iter().cloned().map(Mod3).max().map(|x| x.0), Some(8));
1860 }
1861
1862 #[test]
1863 fn test_iterator_min() {
1864     let v: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1865     assert_eq!(v[..4].iter().cloned().min(), Some(0));
1866     assert_eq!(v.iter().cloned().min(), Some(0));
1867     assert_eq!(v[..0].iter().cloned().min(), None);
1868     assert_eq!(v.iter().cloned().map(Mod3).min().map(|x| x.0), Some(0));
1869 }
1870
1871 #[test]
1872 fn test_iterator_size_hint() {
1873     let c = (0..).step_by(1);
1874     let v: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
1875     let v2 = &[10, 11, 12];
1876     let vi = v.iter();
1877
1878     assert_eq!((0..).size_hint(), (usize::MAX, None));
1879     assert_eq!(c.size_hint(), (usize::MAX, None));
1880     assert_eq!(vi.clone().size_hint(), (10, Some(10)));
1881
1882     assert_eq!(c.clone().take(5).size_hint(), (5, Some(5)));
1883     assert_eq!(c.clone().skip(5).size_hint().1, None);
1884     assert_eq!(c.clone().take_while(|_| false).size_hint(), (0, None));
1885     assert_eq!(c.clone().map_while(|_| None::<()>).size_hint(), (0, None));
1886     assert_eq!(c.clone().skip_while(|_| false).size_hint(), (0, None));
1887     assert_eq!(c.clone().enumerate().size_hint(), (usize::MAX, None));
1888     assert_eq!(c.clone().chain(vi.clone().cloned()).size_hint(), (usize::MAX, None));
1889     assert_eq!(c.clone().zip(vi.clone()).size_hint(), (10, Some(10)));
1890     assert_eq!(c.clone().scan(0, |_, _| Some(0)).size_hint(), (0, None));
1891     assert_eq!(c.clone().filter(|_| false).size_hint(), (0, None));
1892     assert_eq!(c.clone().map(|_| 0).size_hint(), (usize::MAX, None));
1893     assert_eq!(c.filter_map(|_| Some(0)).size_hint(), (0, None));
1894
1895     assert_eq!(vi.clone().take(5).size_hint(), (5, Some(5)));
1896     assert_eq!(vi.clone().take(12).size_hint(), (10, Some(10)));
1897     assert_eq!(vi.clone().skip(3).size_hint(), (7, Some(7)));
1898     assert_eq!(vi.clone().skip(12).size_hint(), (0, Some(0)));
1899     assert_eq!(vi.clone().take_while(|_| false).size_hint(), (0, Some(10)));
1900     assert_eq!(vi.clone().map_while(|_| None::<()>).size_hint(), (0, Some(10)));
1901     assert_eq!(vi.clone().skip_while(|_| false).size_hint(), (0, Some(10)));
1902     assert_eq!(vi.clone().enumerate().size_hint(), (10, Some(10)));
1903     assert_eq!(vi.clone().chain(v2).size_hint(), (13, Some(13)));
1904     assert_eq!(vi.clone().zip(v2).size_hint(), (3, Some(3)));
1905     assert_eq!(vi.clone().scan(0, |_, _| Some(0)).size_hint(), (0, Some(10)));
1906     assert_eq!(vi.clone().filter(|_| false).size_hint(), (0, Some(10)));
1907     assert_eq!(vi.clone().map(|&i| i + 1).size_hint(), (10, Some(10)));
1908     assert_eq!(vi.filter_map(|_| Some(0)).size_hint(), (0, Some(10)));
1909 }
1910
1911 #[test]
1912 fn test_collect() {
1913     let a = vec![1, 2, 3, 4, 5];
1914     let b: Vec<isize> = a.iter().cloned().collect();
1915     assert!(a == b);
1916 }
1917
1918 #[test]
1919 fn test_all() {
1920     let v: Box<[isize]> = Box::new([1, 2, 3, 4, 5]);
1921     assert!(v.iter().all(|&x| x < 10));
1922     assert!(!v.iter().all(|&x| x % 2 == 0));
1923     assert!(!v.iter().all(|&x| x > 100));
1924     assert!(v[..0].iter().all(|_| panic!()));
1925 }
1926
1927 #[test]
1928 fn test_any() {
1929     let v: Box<[isize]> = Box::new([1, 2, 3, 4, 5]);
1930     assert!(v.iter().any(|&x| x < 10));
1931     assert!(v.iter().any(|&x| x % 2 == 0));
1932     assert!(!v.iter().any(|&x| x > 100));
1933     assert!(!v[..0].iter().any(|_| panic!()));
1934 }
1935
1936 #[test]
1937 fn test_find() {
1938     let v: &[isize] = &[1, 3, 9, 27, 103, 14, 11];
1939     assert_eq!(*v.iter().find(|&&x| x & 1 == 0).unwrap(), 14);
1940     assert_eq!(*v.iter().find(|&&x| x % 3 == 0).unwrap(), 3);
1941     assert!(v.iter().find(|&&x| x % 12 == 0).is_none());
1942 }
1943
1944 #[test]
1945 fn test_find_map() {
1946     let xs: &[isize] = &[];
1947     assert_eq!(xs.iter().find_map(half_if_even), None);
1948     let xs: &[isize] = &[3, 5];
1949     assert_eq!(xs.iter().find_map(half_if_even), None);
1950     let xs: &[isize] = &[4, 5];
1951     assert_eq!(xs.iter().find_map(half_if_even), Some(2));
1952     let xs: &[isize] = &[3, 6];
1953     assert_eq!(xs.iter().find_map(half_if_even), Some(3));
1954
1955     let xs: &[isize] = &[1, 2, 3, 4, 5, 6, 7];
1956     let mut iter = xs.iter();
1957     assert_eq!(iter.find_map(half_if_even), Some(1));
1958     assert_eq!(iter.find_map(half_if_even), Some(2));
1959     assert_eq!(iter.find_map(half_if_even), Some(3));
1960     assert_eq!(iter.next(), Some(&7));
1961
1962     fn half_if_even(x: &isize) -> Option<isize> {
1963         if x % 2 == 0 { Some(x / 2) } else { None }
1964     }
1965 }
1966
1967 #[test]
1968 fn test_try_find() {
1969     let xs: &[isize] = &[];
1970     assert_eq!(xs.iter().try_find(testfn), Ok(None));
1971     let xs: &[isize] = &[1, 2, 3, 4];
1972     assert_eq!(xs.iter().try_find(testfn), Ok(Some(&2)));
1973     let xs: &[isize] = &[1, 3, 4];
1974     assert_eq!(xs.iter().try_find(testfn), Err(()));
1975
1976     let xs: &[isize] = &[1, 2, 3, 4, 5, 6, 7];
1977     let mut iter = xs.iter();
1978     assert_eq!(iter.try_find(testfn), Ok(Some(&2)));
1979     assert_eq!(iter.try_find(testfn), Err(()));
1980     assert_eq!(iter.next(), Some(&5));
1981
1982     fn testfn(x: &&isize) -> Result<bool, ()> {
1983         if **x == 2 {
1984             return Ok(true);
1985         }
1986         if **x == 4 {
1987             return Err(());
1988         }
1989         Ok(false)
1990     }
1991 }
1992
1993 #[test]
1994 fn test_try_find_api_usability() -> Result<(), Box<dyn std::error::Error>> {
1995     let a = ["1", "2"];
1996
1997     let is_my_num = |s: &str, search: i32| -> Result<bool, std::num::ParseIntError> {
1998         Ok(s.parse::<i32>()? == search)
1999     };
2000
2001     let val = a.iter().try_find(|&&s| is_my_num(s, 2))?;
2002     assert_eq!(val, Some(&"2"));
2003
2004     Ok(())
2005 }
2006
2007 #[test]
2008 fn test_position() {
2009     let v = &[1, 3, 9, 27, 103, 14, 11];
2010     assert_eq!(v.iter().position(|x| *x & 1 == 0).unwrap(), 5);
2011     assert_eq!(v.iter().position(|x| *x % 3 == 0).unwrap(), 1);
2012     assert!(v.iter().position(|x| *x % 12 == 0).is_none());
2013 }
2014
2015 #[test]
2016 fn test_count() {
2017     let xs = &[1, 2, 2, 1, 5, 9, 0, 2];
2018     assert_eq!(xs.iter().filter(|x| **x == 2).count(), 3);
2019     assert_eq!(xs.iter().filter(|x| **x == 5).count(), 1);
2020     assert_eq!(xs.iter().filter(|x| **x == 95).count(), 0);
2021 }
2022
2023 #[test]
2024 fn test_max_by_key() {
2025     let xs: &[isize] = &[-3, 0, 1, 5, -10];
2026     assert_eq!(*xs.iter().max_by_key(|x| x.abs()).unwrap(), -10);
2027 }
2028
2029 #[test]
2030 fn test_max_by() {
2031     let xs: &[isize] = &[-3, 0, 1, 5, -10];
2032     assert_eq!(*xs.iter().max_by(|x, y| x.abs().cmp(&y.abs())).unwrap(), -10);
2033 }
2034
2035 #[test]
2036 fn test_min_by_key() {
2037     let xs: &[isize] = &[-3, 0, 1, 5, -10];
2038     assert_eq!(*xs.iter().min_by_key(|x| x.abs()).unwrap(), 0);
2039 }
2040
2041 #[test]
2042 fn test_min_by() {
2043     let xs: &[isize] = &[-3, 0, 1, 5, -10];
2044     assert_eq!(*xs.iter().min_by(|x, y| x.abs().cmp(&y.abs())).unwrap(), 0);
2045 }
2046
2047 #[test]
2048 fn test_by_ref() {
2049     let mut xs = 0..10;
2050     // sum the first five values
2051     let partial_sum = xs.by_ref().take(5).fold(0, |a, b| a + b);
2052     assert_eq!(partial_sum, 10);
2053     assert_eq!(xs.next(), Some(5));
2054 }
2055
2056 #[test]
2057 fn test_rev() {
2058     let xs = [2, 4, 6, 8, 10, 12, 14, 16];
2059     let mut it = xs.iter();
2060     it.next();
2061     it.next();
2062     assert!(it.rev().cloned().collect::<Vec<isize>>() == vec![16, 14, 12, 10, 8, 6]);
2063 }
2064
2065 #[test]
2066 fn test_copied() {
2067     let xs = [2, 4, 6, 8];
2068
2069     let mut it = xs.iter().copied();
2070     assert_eq!(it.len(), 4);
2071     assert_eq!(it.next(), Some(2));
2072     assert_eq!(it.len(), 3);
2073     assert_eq!(it.next(), Some(4));
2074     assert_eq!(it.len(), 2);
2075     assert_eq!(it.next_back(), Some(8));
2076     assert_eq!(it.len(), 1);
2077     assert_eq!(it.next_back(), Some(6));
2078     assert_eq!(it.len(), 0);
2079     assert_eq!(it.next_back(), None);
2080 }
2081
2082 #[test]
2083 fn test_cloned() {
2084     let xs = [2, 4, 6, 8];
2085
2086     let mut it = xs.iter().cloned();
2087     assert_eq!(it.len(), 4);
2088     assert_eq!(it.next(), Some(2));
2089     assert_eq!(it.len(), 3);
2090     assert_eq!(it.next(), Some(4));
2091     assert_eq!(it.len(), 2);
2092     assert_eq!(it.next_back(), Some(8));
2093     assert_eq!(it.len(), 1);
2094     assert_eq!(it.next_back(), Some(6));
2095     assert_eq!(it.len(), 0);
2096     assert_eq!(it.next_back(), None);
2097 }
2098
2099 #[test]
2100 fn test_cloned_side_effects() {
2101     let mut count = 0;
2102     {
2103         let iter = [1, 2, 3]
2104             .iter()
2105             .map(|x| {
2106                 count += 1;
2107                 x
2108             })
2109             .cloned()
2110             .zip(&[1]);
2111         for _ in iter {}
2112     }
2113     assert_eq!(count, 2);
2114 }
2115
2116 #[test]
2117 fn test_double_ended_map() {
2118     let xs = [1, 2, 3, 4, 5, 6];
2119     let mut it = xs.iter().map(|&x| x * -1);
2120     assert_eq!(it.next(), Some(-1));
2121     assert_eq!(it.next(), Some(-2));
2122     assert_eq!(it.next_back(), Some(-6));
2123     assert_eq!(it.next_back(), Some(-5));
2124     assert_eq!(it.next(), Some(-3));
2125     assert_eq!(it.next_back(), Some(-4));
2126     assert_eq!(it.next(), None);
2127 }
2128
2129 #[test]
2130 fn test_double_ended_enumerate() {
2131     let xs = [1, 2, 3, 4, 5, 6];
2132     let mut it = xs.iter().cloned().enumerate();
2133     assert_eq!(it.next(), Some((0, 1)));
2134     assert_eq!(it.next(), Some((1, 2)));
2135     assert_eq!(it.next_back(), Some((5, 6)));
2136     assert_eq!(it.next_back(), Some((4, 5)));
2137     assert_eq!(it.next_back(), Some((3, 4)));
2138     assert_eq!(it.next_back(), Some((2, 3)));
2139     assert_eq!(it.next(), None);
2140 }
2141
2142 #[test]
2143 fn test_double_ended_zip() {
2144     let xs = [1, 2, 3, 4, 5, 6];
2145     let ys = [1, 2, 3, 7];
2146     let a = xs.iter().cloned();
2147     let b = ys.iter().cloned();
2148     let mut it = a.zip(b);
2149     assert_eq!(it.next(), Some((1, 1)));
2150     assert_eq!(it.next(), Some((2, 2)));
2151     assert_eq!(it.next_back(), Some((4, 7)));
2152     assert_eq!(it.next_back(), Some((3, 3)));
2153     assert_eq!(it.next(), None);
2154 }
2155
2156 #[test]
2157 fn test_double_ended_filter() {
2158     let xs = [1, 2, 3, 4, 5, 6];
2159     let mut it = xs.iter().filter(|&x| *x & 1 == 0);
2160     assert_eq!(it.next_back().unwrap(), &6);
2161     assert_eq!(it.next_back().unwrap(), &4);
2162     assert_eq!(it.next().unwrap(), &2);
2163     assert_eq!(it.next_back(), None);
2164 }
2165
2166 #[test]
2167 fn test_double_ended_filter_map() {
2168     let xs = [1, 2, 3, 4, 5, 6];
2169     let mut it = xs.iter().filter_map(|&x| if x & 1 == 0 { Some(x * 2) } else { None });
2170     assert_eq!(it.next_back().unwrap(), 12);
2171     assert_eq!(it.next_back().unwrap(), 8);
2172     assert_eq!(it.next().unwrap(), 4);
2173     assert_eq!(it.next_back(), None);
2174 }
2175
2176 #[test]
2177 fn test_double_ended_chain() {
2178     let xs = [1, 2, 3, 4, 5];
2179     let ys = [7, 9, 11];
2180     let mut it = xs.iter().chain(&ys).rev();
2181     assert_eq!(it.next().unwrap(), &11);
2182     assert_eq!(it.next().unwrap(), &9);
2183     assert_eq!(it.next_back().unwrap(), &1);
2184     assert_eq!(it.next_back().unwrap(), &2);
2185     assert_eq!(it.next_back().unwrap(), &3);
2186     assert_eq!(it.next_back().unwrap(), &4);
2187     assert_eq!(it.next_back().unwrap(), &5);
2188     assert_eq!(it.next_back().unwrap(), &7);
2189     assert_eq!(it.next_back(), None);
2190
2191     // test that .chain() is well behaved with an unfused iterator
2192     struct CrazyIterator(bool);
2193     impl CrazyIterator {
2194         fn new() -> CrazyIterator {
2195             CrazyIterator(false)
2196         }
2197     }
2198     impl Iterator for CrazyIterator {
2199         type Item = i32;
2200         fn next(&mut self) -> Option<i32> {
2201             if self.0 {
2202                 Some(99)
2203             } else {
2204                 self.0 = true;
2205                 None
2206             }
2207         }
2208     }
2209
2210     impl DoubleEndedIterator for CrazyIterator {
2211         fn next_back(&mut self) -> Option<i32> {
2212             self.next()
2213         }
2214     }
2215
2216     assert_eq!(CrazyIterator::new().chain(0..10).rev().last(), Some(0));
2217     assert!((0..10).chain(CrazyIterator::new()).rev().any(|i| i == 0));
2218 }
2219
2220 #[test]
2221 fn test_rposition() {
2222     fn f(xy: &(isize, char)) -> bool {
2223         let (_x, y) = *xy;
2224         y == 'b'
2225     }
2226     fn g(xy: &(isize, char)) -> bool {
2227         let (_x, y) = *xy;
2228         y == 'd'
2229     }
2230     let v = [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
2231
2232     assert_eq!(v.iter().rposition(f), Some(3));
2233     assert!(v.iter().rposition(g).is_none());
2234 }
2235
2236 #[test]
2237 fn test_rev_rposition() {
2238     let v = [0, 0, 1, 1];
2239     assert_eq!(v.iter().rev().rposition(|&x| x == 1), Some(1));
2240 }
2241
2242 #[test]
2243 #[should_panic]
2244 fn test_rposition_panic() {
2245     let v: [(Box<_>, Box<_>); 4] = [(box 0, box 0), (box 0, box 0), (box 0, box 0), (box 0, box 0)];
2246     let mut i = 0;
2247     v.iter().rposition(|_elt| {
2248         if i == 2 {
2249             panic!()
2250         }
2251         i += 1;
2252         false
2253     });
2254 }
2255
2256 #[test]
2257 fn test_double_ended_flat_map() {
2258     let u = [0, 1];
2259     let v = [5, 6, 7, 8];
2260     let mut it = u.iter().flat_map(|x| &v[*x..v.len()]);
2261     assert_eq!(it.next_back().unwrap(), &8);
2262     assert_eq!(it.next().unwrap(), &5);
2263     assert_eq!(it.next_back().unwrap(), &7);
2264     assert_eq!(it.next_back().unwrap(), &6);
2265     assert_eq!(it.next_back().unwrap(), &8);
2266     assert_eq!(it.next().unwrap(), &6);
2267     assert_eq!(it.next_back().unwrap(), &7);
2268     assert_eq!(it.next_back(), None);
2269     assert_eq!(it.next(), None);
2270     assert_eq!(it.next_back(), None);
2271 }
2272
2273 #[test]
2274 fn test_double_ended_flatten() {
2275     let u = [0, 1];
2276     let v = [5, 6, 7, 8];
2277     let mut it = u.iter().map(|x| &v[*x..v.len()]).flatten();
2278     assert_eq!(it.next_back().unwrap(), &8);
2279     assert_eq!(it.next().unwrap(), &5);
2280     assert_eq!(it.next_back().unwrap(), &7);
2281     assert_eq!(it.next_back().unwrap(), &6);
2282     assert_eq!(it.next_back().unwrap(), &8);
2283     assert_eq!(it.next().unwrap(), &6);
2284     assert_eq!(it.next_back().unwrap(), &7);
2285     assert_eq!(it.next_back(), None);
2286     assert_eq!(it.next(), None);
2287     assert_eq!(it.next_back(), None);
2288 }
2289
2290 #[test]
2291 fn test_double_ended_range() {
2292     assert_eq!((11..14).rev().collect::<Vec<_>>(), [13, 12, 11]);
2293     for _ in (10..0).rev() {
2294         panic!("unreachable");
2295     }
2296
2297     assert_eq!((11..14).rev().collect::<Vec<_>>(), [13, 12, 11]);
2298     for _ in (10..0).rev() {
2299         panic!("unreachable");
2300     }
2301 }
2302
2303 #[test]
2304 fn test_range() {
2305     assert_eq!((0..5).collect::<Vec<_>>(), [0, 1, 2, 3, 4]);
2306     assert_eq!((-10..-1).collect::<Vec<_>>(), [-10, -9, -8, -7, -6, -5, -4, -3, -2]);
2307     assert_eq!((0..5).rev().collect::<Vec<_>>(), [4, 3, 2, 1, 0]);
2308     assert_eq!((200..-5).count(), 0);
2309     assert_eq!((200..-5).rev().count(), 0);
2310     assert_eq!((200..200).count(), 0);
2311     assert_eq!((200..200).rev().count(), 0);
2312
2313     assert_eq!((0..100).size_hint(), (100, Some(100)));
2314     // this test is only meaningful when sizeof usize < sizeof u64
2315     assert_eq!((usize::MAX - 1..usize::MAX).size_hint(), (1, Some(1)));
2316     assert_eq!((-10..-1).size_hint(), (9, Some(9)));
2317     assert_eq!((-1..-10).size_hint(), (0, Some(0)));
2318
2319     assert_eq!((-70..58).size_hint(), (128, Some(128)));
2320     assert_eq!((-128..127).size_hint(), (255, Some(255)));
2321     assert_eq!(
2322         (-2..isize::MAX).size_hint(),
2323         (isize::MAX as usize + 2, Some(isize::MAX as usize + 2))
2324     );
2325 }
2326
2327 #[test]
2328 fn test_char_range() {
2329     use std::char;
2330     // Miri is too slow
2331     let from = if cfg!(miri) { char::from_u32(0xD800 - 10).unwrap() } else { '\0' };
2332     let to = if cfg!(miri) { char::from_u32(0xDFFF + 10).unwrap() } else { char::MAX };
2333     assert!((from..=to).eq((from as u32..=to as u32).filter_map(char::from_u32)));
2334     assert!((from..=to).rev().eq((from as u32..=to as u32).filter_map(char::from_u32).rev()));
2335
2336     assert_eq!(('\u{D7FF}'..='\u{E000}').count(), 2);
2337     assert_eq!(('\u{D7FF}'..='\u{E000}').size_hint(), (2, Some(2)));
2338     assert_eq!(('\u{D7FF}'..'\u{E000}').count(), 1);
2339     assert_eq!(('\u{D7FF}'..'\u{E000}').size_hint(), (1, Some(1)));
2340 }
2341
2342 #[test]
2343 fn test_range_exhaustion() {
2344     let mut r = 10..10;
2345     assert!(r.is_empty());
2346     assert_eq!(r.next(), None);
2347     assert_eq!(r.next_back(), None);
2348     assert_eq!(r, 10..10);
2349
2350     let mut r = 10..12;
2351     assert_eq!(r.next(), Some(10));
2352     assert_eq!(r.next(), Some(11));
2353     assert!(r.is_empty());
2354     assert_eq!(r, 12..12);
2355     assert_eq!(r.next(), None);
2356
2357     let mut r = 10..12;
2358     assert_eq!(r.next_back(), Some(11));
2359     assert_eq!(r.next_back(), Some(10));
2360     assert!(r.is_empty());
2361     assert_eq!(r, 10..10);
2362     assert_eq!(r.next_back(), None);
2363
2364     let mut r = 100..10;
2365     assert!(r.is_empty());
2366     assert_eq!(r.next(), None);
2367     assert_eq!(r.next_back(), None);
2368     assert_eq!(r, 100..10);
2369 }
2370
2371 #[test]
2372 fn test_range_inclusive_exhaustion() {
2373     let mut r = 10..=10;
2374     assert_eq!(r.next(), Some(10));
2375     assert!(r.is_empty());
2376     assert_eq!(r.next(), None);
2377     assert_eq!(r.next(), None);
2378
2379     assert_eq!(*r.start(), 10);
2380     assert_eq!(*r.end(), 10);
2381     assert_ne!(r, 10..=10);
2382
2383     let mut r = 10..=10;
2384     assert_eq!(r.next_back(), Some(10));
2385     assert!(r.is_empty());
2386     assert_eq!(r.next_back(), None);
2387
2388     assert_eq!(*r.start(), 10);
2389     assert_eq!(*r.end(), 10);
2390     assert_ne!(r, 10..=10);
2391
2392     let mut r = 10..=12;
2393     assert_eq!(r.next(), Some(10));
2394     assert_eq!(r.next(), Some(11));
2395     assert_eq!(r.next(), Some(12));
2396     assert!(r.is_empty());
2397     assert_eq!(r.next(), None);
2398
2399     let mut r = 10..=12;
2400     assert_eq!(r.next_back(), Some(12));
2401     assert_eq!(r.next_back(), Some(11));
2402     assert_eq!(r.next_back(), Some(10));
2403     assert!(r.is_empty());
2404     assert_eq!(r.next_back(), None);
2405
2406     let mut r = 10..=12;
2407     assert_eq!(r.nth(2), Some(12));
2408     assert!(r.is_empty());
2409     assert_eq!(r.next(), None);
2410
2411     let mut r = 10..=12;
2412     assert_eq!(r.nth(5), None);
2413     assert!(r.is_empty());
2414     assert_eq!(r.next(), None);
2415
2416     let mut r = 100..=10;
2417     assert_eq!(r.next(), None);
2418     assert!(r.is_empty());
2419     assert_eq!(r.next(), None);
2420     assert_eq!(r.next(), None);
2421     assert_eq!(r, 100..=10);
2422
2423     let mut r = 100..=10;
2424     assert_eq!(r.next_back(), None);
2425     assert!(r.is_empty());
2426     assert_eq!(r.next_back(), None);
2427     assert_eq!(r.next_back(), None);
2428     assert_eq!(r, 100..=10);
2429 }
2430
2431 #[test]
2432 fn test_range_nth() {
2433     assert_eq!((10..15).nth(0), Some(10));
2434     assert_eq!((10..15).nth(1), Some(11));
2435     assert_eq!((10..15).nth(4), Some(14));
2436     assert_eq!((10..15).nth(5), None);
2437
2438     let mut r = 10..20;
2439     assert_eq!(r.nth(2), Some(12));
2440     assert_eq!(r, 13..20);
2441     assert_eq!(r.nth(2), Some(15));
2442     assert_eq!(r, 16..20);
2443     assert_eq!(r.nth(10), None);
2444     assert_eq!(r, 20..20);
2445 }
2446
2447 #[test]
2448 fn test_range_nth_back() {
2449     assert_eq!((10..15).nth_back(0), Some(14));
2450     assert_eq!((10..15).nth_back(1), Some(13));
2451     assert_eq!((10..15).nth_back(4), Some(10));
2452     assert_eq!((10..15).nth_back(5), None);
2453     assert_eq!((-120..80_i8).nth_back(199), Some(-120));
2454
2455     let mut r = 10..20;
2456     assert_eq!(r.nth_back(2), Some(17));
2457     assert_eq!(r, 10..17);
2458     assert_eq!(r.nth_back(2), Some(14));
2459     assert_eq!(r, 10..14);
2460     assert_eq!(r.nth_back(10), None);
2461     assert_eq!(r, 10..10);
2462 }
2463
2464 #[test]
2465 fn test_range_from_nth() {
2466     assert_eq!((10..).nth(0), Some(10));
2467     assert_eq!((10..).nth(1), Some(11));
2468     assert_eq!((10..).nth(4), Some(14));
2469
2470     let mut r = 10..;
2471     assert_eq!(r.nth(2), Some(12));
2472     assert_eq!(r, 13..);
2473     assert_eq!(r.nth(2), Some(15));
2474     assert_eq!(r, 16..);
2475     assert_eq!(r.nth(10), Some(26));
2476     assert_eq!(r, 27..);
2477
2478     assert_eq!((0..).size_hint(), (usize::MAX, None));
2479 }
2480
2481 fn is_trusted_len<I: TrustedLen>(_: I) {}
2482
2483 #[test]
2484 fn test_range_from_take() {
2485     let mut it = (0..).take(3);
2486     assert_eq!(it.next(), Some(0));
2487     assert_eq!(it.next(), Some(1));
2488     assert_eq!(it.next(), Some(2));
2489     assert_eq!(it.next(), None);
2490     is_trusted_len((0..).take(3));
2491     assert_eq!((0..).take(3).size_hint(), (3, Some(3)));
2492     assert_eq!((0..).take(0).size_hint(), (0, Some(0)));
2493     assert_eq!((0..).take(usize::MAX).size_hint(), (usize::MAX, Some(usize::MAX)));
2494 }
2495
2496 #[test]
2497 fn test_range_from_take_collect() {
2498     let v: Vec<_> = (0..).take(3).collect();
2499     assert_eq!(v, vec![0, 1, 2]);
2500 }
2501
2502 #[test]
2503 fn test_range_inclusive_nth() {
2504     assert_eq!((10..=15).nth(0), Some(10));
2505     assert_eq!((10..=15).nth(1), Some(11));
2506     assert_eq!((10..=15).nth(5), Some(15));
2507     assert_eq!((10..=15).nth(6), None);
2508
2509     let mut exhausted_via_next = 10_u8..=20;
2510     while exhausted_via_next.next().is_some() {}
2511
2512     let mut r = 10_u8..=20;
2513     assert_eq!(r.nth(2), Some(12));
2514     assert_eq!(r, 13..=20);
2515     assert_eq!(r.nth(2), Some(15));
2516     assert_eq!(r, 16..=20);
2517     assert_eq!(r.is_empty(), false);
2518     assert_eq!(ExactSizeIterator::is_empty(&r), false);
2519     assert_eq!(r.nth(10), None);
2520     assert_eq!(r.is_empty(), true);
2521     assert_eq!(r, exhausted_via_next);
2522     assert_eq!(ExactSizeIterator::is_empty(&r), true);
2523 }
2524
2525 #[test]
2526 fn test_range_inclusive_nth_back() {
2527     assert_eq!((10..=15).nth_back(0), Some(15));
2528     assert_eq!((10..=15).nth_back(1), Some(14));
2529     assert_eq!((10..=15).nth_back(5), Some(10));
2530     assert_eq!((10..=15).nth_back(6), None);
2531     assert_eq!((-120..=80_i8).nth_back(200), Some(-120));
2532
2533     let mut exhausted_via_next_back = 10_u8..=20;
2534     while exhausted_via_next_back.next_back().is_some() {}
2535
2536     let mut r = 10_u8..=20;
2537     assert_eq!(r.nth_back(2), Some(18));
2538     assert_eq!(r, 10..=17);
2539     assert_eq!(r.nth_back(2), Some(15));
2540     assert_eq!(r, 10..=14);
2541     assert_eq!(r.is_empty(), false);
2542     assert_eq!(ExactSizeIterator::is_empty(&r), false);
2543     assert_eq!(r.nth_back(10), None);
2544     assert_eq!(r.is_empty(), true);
2545     assert_eq!(r, exhausted_via_next_back);
2546     assert_eq!(ExactSizeIterator::is_empty(&r), true);
2547 }
2548
2549 #[test]
2550 fn test_range_len() {
2551     assert_eq!((0..10_u8).len(), 10);
2552     assert_eq!((9..10_u8).len(), 1);
2553     assert_eq!((10..10_u8).len(), 0);
2554     assert_eq!((11..10_u8).len(), 0);
2555     assert_eq!((100..10_u8).len(), 0);
2556 }
2557
2558 #[test]
2559 fn test_range_inclusive_len() {
2560     assert_eq!((0..=10_u8).len(), 11);
2561     assert_eq!((9..=10_u8).len(), 2);
2562     assert_eq!((10..=10_u8).len(), 1);
2563     assert_eq!((11..=10_u8).len(), 0);
2564     assert_eq!((100..=10_u8).len(), 0);
2565 }
2566
2567 #[test]
2568 fn test_range_step() {
2569     #![allow(deprecated)]
2570
2571     assert_eq!((0..20).step_by(5).collect::<Vec<isize>>(), [0, 5, 10, 15]);
2572     assert_eq!((1..21).rev().step_by(5).collect::<Vec<isize>>(), [20, 15, 10, 5]);
2573     assert_eq!((1..21).rev().step_by(6).collect::<Vec<isize>>(), [20, 14, 8, 2]);
2574     assert_eq!((200..255).step_by(50).collect::<Vec<u8>>(), [200, 250]);
2575     assert_eq!((200..-5).step_by(1).collect::<Vec<isize>>(), []);
2576     assert_eq!((200..200).step_by(1).collect::<Vec<isize>>(), []);
2577
2578     assert_eq!((0..20).step_by(1).size_hint(), (20, Some(20)));
2579     assert_eq!((0..20).step_by(21).size_hint(), (1, Some(1)));
2580     assert_eq!((0..20).step_by(5).size_hint(), (4, Some(4)));
2581     assert_eq!((1..21).rev().step_by(5).size_hint(), (4, Some(4)));
2582     assert_eq!((1..21).rev().step_by(6).size_hint(), (4, Some(4)));
2583     assert_eq!((20..-5).step_by(1).size_hint(), (0, Some(0)));
2584     assert_eq!((20..20).step_by(1).size_hint(), (0, Some(0)));
2585     assert_eq!((i8::MIN..i8::MAX).step_by(-(i8::MIN as i32) as usize).size_hint(), (2, Some(2)));
2586     assert_eq!((i16::MIN..i16::MAX).step_by(i16::MAX as usize).size_hint(), (3, Some(3)));
2587     assert_eq!((isize::MIN..isize::MAX).step_by(1).size_hint(), (usize::MAX, Some(usize::MAX)));
2588 }
2589
2590 #[test]
2591 fn test_step_by_skip() {
2592     assert_eq!((0..640).step_by(128).skip(1).collect::<Vec<_>>(), [128, 256, 384, 512]);
2593     assert_eq!((0..=50).step_by(10).nth(3), Some(30));
2594     assert_eq!((200..=255u8).step_by(10).nth(3), Some(230));
2595 }
2596
2597 #[test]
2598 fn test_range_inclusive_step() {
2599     assert_eq!((0..=50).step_by(10).collect::<Vec<_>>(), [0, 10, 20, 30, 40, 50]);
2600     assert_eq!((0..=5).step_by(1).collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5]);
2601     assert_eq!((200..=255u8).step_by(10).collect::<Vec<_>>(), [200, 210, 220, 230, 240, 250]);
2602     assert_eq!((250..=255u8).step_by(1).collect::<Vec<_>>(), [250, 251, 252, 253, 254, 255]);
2603 }
2604
2605 #[test]
2606 fn test_range_last_max() {
2607     assert_eq!((0..20).last(), Some(19));
2608     assert_eq!((-20..0).last(), Some(-1));
2609     assert_eq!((5..5).last(), None);
2610
2611     assert_eq!((0..20).max(), Some(19));
2612     assert_eq!((-20..0).max(), Some(-1));
2613     assert_eq!((5..5).max(), None);
2614 }
2615
2616 #[test]
2617 fn test_range_inclusive_last_max() {
2618     assert_eq!((0..=20).last(), Some(20));
2619     assert_eq!((-20..=0).last(), Some(0));
2620     assert_eq!((5..=5).last(), Some(5));
2621     let mut r = 10..=10;
2622     r.next();
2623     assert_eq!(r.last(), None);
2624
2625     assert_eq!((0..=20).max(), Some(20));
2626     assert_eq!((-20..=0).max(), Some(0));
2627     assert_eq!((5..=5).max(), Some(5));
2628     let mut r = 10..=10;
2629     r.next();
2630     assert_eq!(r.max(), None);
2631 }
2632
2633 #[test]
2634 fn test_range_min() {
2635     assert_eq!((0..20).min(), Some(0));
2636     assert_eq!((-20..0).min(), Some(-20));
2637     assert_eq!((5..5).min(), None);
2638 }
2639
2640 #[test]
2641 fn test_range_inclusive_min() {
2642     assert_eq!((0..=20).min(), Some(0));
2643     assert_eq!((-20..=0).min(), Some(-20));
2644     assert_eq!((5..=5).min(), Some(5));
2645     let mut r = 10..=10;
2646     r.next();
2647     assert_eq!(r.min(), None);
2648 }
2649
2650 #[test]
2651 fn test_range_inclusive_folds() {
2652     assert_eq!((1..=10).sum::<i32>(), 55);
2653     assert_eq!((1..=10).rev().sum::<i32>(), 55);
2654
2655     let mut it = 44..=50;
2656     assert_eq!(it.try_fold(0, i8::checked_add), None);
2657     assert_eq!(it, 47..=50);
2658     assert_eq!(it.try_fold(0, i8::checked_add), None);
2659     assert_eq!(it, 50..=50);
2660     assert_eq!(it.try_fold(0, i8::checked_add), Some(50));
2661     assert!(it.is_empty());
2662     assert_eq!(it.try_fold(0, i8::checked_add), Some(0));
2663     assert!(it.is_empty());
2664
2665     let mut it = 40..=47;
2666     assert_eq!(it.try_rfold(0, i8::checked_add), None);
2667     assert_eq!(it, 40..=44);
2668     assert_eq!(it.try_rfold(0, i8::checked_add), None);
2669     assert_eq!(it, 40..=41);
2670     assert_eq!(it.try_rfold(0, i8::checked_add), Some(81));
2671     assert!(it.is_empty());
2672     assert_eq!(it.try_rfold(0, i8::checked_add), Some(0));
2673     assert!(it.is_empty());
2674
2675     let mut it = 10..=20;
2676     assert_eq!(it.try_fold(0, |a, b| Some(a + b)), Some(165));
2677     assert!(it.is_empty());
2678     assert_eq!(it.try_fold(0, |a, b| Some(a + b)), Some(0));
2679     assert!(it.is_empty());
2680
2681     let mut it = 10..=20;
2682     assert_eq!(it.try_rfold(0, |a, b| Some(a + b)), Some(165));
2683     assert!(it.is_empty());
2684     assert_eq!(it.try_rfold(0, |a, b| Some(a + b)), Some(0));
2685     assert!(it.is_empty());
2686 }
2687
2688 #[test]
2689 fn test_range_size_hint() {
2690     assert_eq!((0..0usize).size_hint(), (0, Some(0)));
2691     assert_eq!((0..100usize).size_hint(), (100, Some(100)));
2692     assert_eq!((0..usize::MAX).size_hint(), (usize::MAX, Some(usize::MAX)));
2693
2694     let umax = u128::try_from(usize::MAX).unwrap();
2695     assert_eq!((0..0u128).size_hint(), (0, Some(0)));
2696     assert_eq!((0..100u128).size_hint(), (100, Some(100)));
2697     assert_eq!((0..umax).size_hint(), (usize::MAX, Some(usize::MAX)));
2698     assert_eq!((0..umax + 1).size_hint(), (usize::MAX, None));
2699
2700     assert_eq!((0..0isize).size_hint(), (0, Some(0)));
2701     assert_eq!((-100..100isize).size_hint(), (200, Some(200)));
2702     assert_eq!((isize::MIN..isize::MAX).size_hint(), (usize::MAX, Some(usize::MAX)));
2703
2704     let imin = i128::try_from(isize::MIN).unwrap();
2705     let imax = i128::try_from(isize::MAX).unwrap();
2706     assert_eq!((0..0i128).size_hint(), (0, Some(0)));
2707     assert_eq!((-100..100i128).size_hint(), (200, Some(200)));
2708     assert_eq!((imin..imax).size_hint(), (usize::MAX, Some(usize::MAX)));
2709     assert_eq!((imin..imax + 1).size_hint(), (usize::MAX, None));
2710 }
2711
2712 #[test]
2713 fn test_range_inclusive_size_hint() {
2714     assert_eq!((1..=0usize).size_hint(), (0, Some(0)));
2715     assert_eq!((0..=0usize).size_hint(), (1, Some(1)));
2716     assert_eq!((0..=100usize).size_hint(), (101, Some(101)));
2717     assert_eq!((0..=usize::MAX - 1).size_hint(), (usize::MAX, Some(usize::MAX)));
2718     assert_eq!((0..=usize::MAX).size_hint(), (usize::MAX, None));
2719
2720     let umax = u128::try_from(usize::MAX).unwrap();
2721     assert_eq!((1..=0u128).size_hint(), (0, Some(0)));
2722     assert_eq!((0..=0u128).size_hint(), (1, Some(1)));
2723     assert_eq!((0..=100u128).size_hint(), (101, Some(101)));
2724     assert_eq!((0..=umax - 1).size_hint(), (usize::MAX, Some(usize::MAX)));
2725     assert_eq!((0..=umax).size_hint(), (usize::MAX, None));
2726     assert_eq!((0..=umax + 1).size_hint(), (usize::MAX, None));
2727
2728     assert_eq!((0..=-1isize).size_hint(), (0, Some(0)));
2729     assert_eq!((0..=0isize).size_hint(), (1, Some(1)));
2730     assert_eq!((-100..=100isize).size_hint(), (201, Some(201)));
2731     assert_eq!((isize::MIN..=isize::MAX - 1).size_hint(), (usize::MAX, Some(usize::MAX)));
2732     assert_eq!((isize::MIN..=isize::MAX).size_hint(), (usize::MAX, None));
2733
2734     let imin = i128::try_from(isize::MIN).unwrap();
2735     let imax = i128::try_from(isize::MAX).unwrap();
2736     assert_eq!((0..=-1i128).size_hint(), (0, Some(0)));
2737     assert_eq!((0..=0i128).size_hint(), (1, Some(1)));
2738     assert_eq!((-100..=100i128).size_hint(), (201, Some(201)));
2739     assert_eq!((imin..=imax - 1).size_hint(), (usize::MAX, Some(usize::MAX)));
2740     assert_eq!((imin..=imax).size_hint(), (usize::MAX, None));
2741     assert_eq!((imin..=imax + 1).size_hint(), (usize::MAX, None));
2742 }
2743
2744 #[test]
2745 fn test_repeat() {
2746     let mut it = repeat(42);
2747     assert_eq!(it.next(), Some(42));
2748     assert_eq!(it.next(), Some(42));
2749     assert_eq!(it.next(), Some(42));
2750     assert_eq!(repeat(42).size_hint(), (usize::MAX, None));
2751 }
2752
2753 #[test]
2754 fn test_repeat_take() {
2755     let mut it = repeat(42).take(3);
2756     assert_eq!(it.next(), Some(42));
2757     assert_eq!(it.next(), Some(42));
2758     assert_eq!(it.next(), Some(42));
2759     assert_eq!(it.next(), None);
2760     is_trusted_len(repeat(42).take(3));
2761     assert_eq!(repeat(42).take(3).size_hint(), (3, Some(3)));
2762     assert_eq!(repeat(42).take(0).size_hint(), (0, Some(0)));
2763     assert_eq!(repeat(42).take(usize::MAX).size_hint(), (usize::MAX, Some(usize::MAX)));
2764 }
2765
2766 #[test]
2767 fn test_repeat_take_collect() {
2768     let v: Vec<_> = repeat(42).take(3).collect();
2769     assert_eq!(v, vec![42, 42, 42]);
2770 }
2771
2772 #[test]
2773 fn test_repeat_with() {
2774     #[derive(PartialEq, Debug)]
2775     struct NotClone(usize);
2776     let mut it = repeat_with(|| NotClone(42));
2777     assert_eq!(it.next(), Some(NotClone(42)));
2778     assert_eq!(it.next(), Some(NotClone(42)));
2779     assert_eq!(it.next(), Some(NotClone(42)));
2780     assert_eq!(repeat_with(|| NotClone(42)).size_hint(), (usize::MAX, None));
2781 }
2782
2783 #[test]
2784 fn test_repeat_with_take() {
2785     let mut it = repeat_with(|| 42).take(3);
2786     assert_eq!(it.next(), Some(42));
2787     assert_eq!(it.next(), Some(42));
2788     assert_eq!(it.next(), Some(42));
2789     assert_eq!(it.next(), None);
2790     is_trusted_len(repeat_with(|| 42).take(3));
2791     assert_eq!(repeat_with(|| 42).take(3).size_hint(), (3, Some(3)));
2792     assert_eq!(repeat_with(|| 42).take(0).size_hint(), (0, Some(0)));
2793     assert_eq!(repeat_with(|| 42).take(usize::MAX).size_hint(), (usize::MAX, Some(usize::MAX)));
2794 }
2795
2796 #[test]
2797 fn test_repeat_with_take_collect() {
2798     let mut curr = 1;
2799     let v: Vec<_> = repeat_with(|| {
2800         let tmp = curr;
2801         curr *= 2;
2802         tmp
2803     })
2804     .take(5)
2805     .collect();
2806     assert_eq!(v, vec![1, 2, 4, 8, 16]);
2807 }
2808
2809 #[test]
2810 fn test_successors() {
2811     let mut powers_of_10 = successors(Some(1_u16), |n| n.checked_mul(10));
2812     assert_eq!(powers_of_10.by_ref().collect::<Vec<_>>(), &[1, 10, 100, 1_000, 10_000]);
2813     assert_eq!(powers_of_10.next(), None);
2814
2815     let mut empty = successors(None::<u32>, |_| unimplemented!());
2816     assert_eq!(empty.next(), None);
2817     assert_eq!(empty.next(), None);
2818 }
2819
2820 #[test]
2821 fn test_fuse() {
2822     let mut it = 0..3;
2823     assert_eq!(it.len(), 3);
2824     assert_eq!(it.next(), Some(0));
2825     assert_eq!(it.len(), 2);
2826     assert_eq!(it.next(), Some(1));
2827     assert_eq!(it.len(), 1);
2828     assert_eq!(it.next(), Some(2));
2829     assert_eq!(it.len(), 0);
2830     assert_eq!(it.next(), None);
2831     assert_eq!(it.len(), 0);
2832     assert_eq!(it.next(), None);
2833     assert_eq!(it.len(), 0);
2834     assert_eq!(it.next(), None);
2835     assert_eq!(it.len(), 0);
2836 }
2837
2838 #[test]
2839 fn test_fuse_nth() {
2840     let xs = [0, 1, 2];
2841     let mut it = xs.iter();
2842
2843     assert_eq!(it.len(), 3);
2844     assert_eq!(it.nth(2), Some(&2));
2845     assert_eq!(it.len(), 0);
2846     assert_eq!(it.nth(2), None);
2847     assert_eq!(it.len(), 0);
2848 }
2849
2850 #[test]
2851 fn test_fuse_last() {
2852     let xs = [0, 1, 2];
2853     let it = xs.iter();
2854
2855     assert_eq!(it.len(), 3);
2856     assert_eq!(it.last(), Some(&2));
2857 }
2858
2859 #[test]
2860 fn test_fuse_count() {
2861     let xs = [0, 1, 2];
2862     let it = xs.iter();
2863
2864     assert_eq!(it.len(), 3);
2865     assert_eq!(it.count(), 3);
2866     // Can't check len now because count consumes.
2867 }
2868
2869 #[test]
2870 fn test_fuse_fold() {
2871     let xs = [0, 1, 2];
2872     let it = xs.iter(); // `FusedIterator`
2873     let i = it.fuse().fold(0, |i, &x| {
2874         assert_eq!(x, xs[i]);
2875         i + 1
2876     });
2877     assert_eq!(i, xs.len());
2878
2879     let it = xs.iter(); // `FusedIterator`
2880     let i = it.fuse().rfold(xs.len(), |i, &x| {
2881         assert_eq!(x, xs[i - 1]);
2882         i - 1
2883     });
2884     assert_eq!(i, 0);
2885
2886     let it = xs.iter().scan((), |_, &x| Some(x)); // `!FusedIterator`
2887     let i = it.fuse().fold(0, |i, x| {
2888         assert_eq!(x, xs[i]);
2889         i + 1
2890     });
2891     assert_eq!(i, xs.len());
2892 }
2893
2894 #[test]
2895 fn test_once() {
2896     let mut it = once(42);
2897     assert_eq!(it.next(), Some(42));
2898     assert_eq!(it.next(), None);
2899 }
2900
2901 #[test]
2902 fn test_once_with() {
2903     let count = Cell::new(0);
2904     let mut it = once_with(|| {
2905         count.set(count.get() + 1);
2906         42
2907     });
2908
2909     assert_eq!(count.get(), 0);
2910     assert_eq!(it.next(), Some(42));
2911     assert_eq!(count.get(), 1);
2912     assert_eq!(it.next(), None);
2913     assert_eq!(count.get(), 1);
2914     assert_eq!(it.next(), None);
2915     assert_eq!(count.get(), 1);
2916 }
2917
2918 #[test]
2919 fn test_empty() {
2920     let mut it = empty::<i32>();
2921     assert_eq!(it.next(), None);
2922 }
2923
2924 #[test]
2925 fn test_chain_fold() {
2926     let xs = [1, 2, 3];
2927     let ys = [1, 2, 0];
2928
2929     let mut iter = xs.iter().chain(&ys);
2930     iter.next();
2931     let mut result = Vec::new();
2932     iter.fold((), |(), &elt| result.push(elt));
2933     assert_eq!(&[2, 3, 1, 2, 0], &result[..]);
2934 }
2935
2936 #[test]
2937 fn test_steps_between() {
2938     assert_eq!(Step::steps_between(&20_u8, &200_u8), Some(180_usize));
2939     assert_eq!(Step::steps_between(&-20_i8, &80_i8), Some(100_usize));
2940     assert_eq!(Step::steps_between(&-120_i8, &80_i8), Some(200_usize));
2941     assert_eq!(Step::steps_between(&20_u32, &4_000_100_u32), Some(4_000_080_usize));
2942     assert_eq!(Step::steps_between(&-20_i32, &80_i32), Some(100_usize));
2943     assert_eq!(Step::steps_between(&-2_000_030_i32, &2_000_050_i32), Some(4_000_080_usize));
2944
2945     // Skip u64/i64 to avoid differences with 32-bit vs 64-bit platforms
2946
2947     assert_eq!(Step::steps_between(&20_u128, &200_u128), Some(180_usize));
2948     assert_eq!(Step::steps_between(&-20_i128, &80_i128), Some(100_usize));
2949     if cfg!(target_pointer_width = "64") {
2950         assert_eq!(Step::steps_between(&10_u128, &0x1_0000_0000_0000_0009_u128), Some(usize::MAX));
2951     }
2952     assert_eq!(Step::steps_between(&10_u128, &0x1_0000_0000_0000_000a_u128), None);
2953     assert_eq!(Step::steps_between(&10_i128, &0x1_0000_0000_0000_000a_i128), None);
2954     assert_eq!(
2955         Step::steps_between(&-0x1_0000_0000_0000_0000_i128, &0x1_0000_0000_0000_0000_i128,),
2956         None,
2957     );
2958 }
2959
2960 #[test]
2961 fn test_step_forward() {
2962     assert_eq!(Step::forward_checked(55_u8, 200_usize), Some(255_u8));
2963     assert_eq!(Step::forward_checked(252_u8, 200_usize), None);
2964     assert_eq!(Step::forward_checked(0_u8, 256_usize), None);
2965     assert_eq!(Step::forward_checked(-110_i8, 200_usize), Some(90_i8));
2966     assert_eq!(Step::forward_checked(-110_i8, 248_usize), None);
2967     assert_eq!(Step::forward_checked(-126_i8, 256_usize), None);
2968
2969     assert_eq!(Step::forward_checked(35_u16, 100_usize), Some(135_u16));
2970     assert_eq!(Step::forward_checked(35_u16, 65500_usize), Some(u16::MAX));
2971     assert_eq!(Step::forward_checked(36_u16, 65500_usize), None);
2972     assert_eq!(Step::forward_checked(-110_i16, 200_usize), Some(90_i16));
2973     assert_eq!(Step::forward_checked(-20_030_i16, 50_050_usize), Some(30_020_i16));
2974     assert_eq!(Step::forward_checked(-10_i16, 40_000_usize), None);
2975     assert_eq!(Step::forward_checked(-10_i16, 70_000_usize), None);
2976
2977     assert_eq!(Step::forward_checked(10_u128, 70_000_usize), Some(70_010_u128));
2978     assert_eq!(Step::forward_checked(10_i128, 70_030_usize), Some(70_040_i128));
2979     assert_eq!(
2980         Step::forward_checked(0xffff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_u128, 0xff_usize),
2981         Some(u128::MAX),
2982     );
2983     assert_eq!(
2984         Step::forward_checked(0xffff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_u128, 0x100_usize),
2985         None
2986     );
2987     assert_eq!(
2988         Step::forward_checked(0x7fff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_i128, 0xff_usize),
2989         Some(i128::MAX),
2990     );
2991     assert_eq!(
2992         Step::forward_checked(0x7fff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_i128, 0x100_usize),
2993         None
2994     );
2995 }
2996
2997 #[test]
2998 fn test_step_backward() {
2999     assert_eq!(Step::backward_checked(255_u8, 200_usize), Some(55_u8));
3000     assert_eq!(Step::backward_checked(100_u8, 200_usize), None);
3001     assert_eq!(Step::backward_checked(255_u8, 256_usize), None);
3002     assert_eq!(Step::backward_checked(90_i8, 200_usize), Some(-110_i8));
3003     assert_eq!(Step::backward_checked(110_i8, 248_usize), None);
3004     assert_eq!(Step::backward_checked(127_i8, 256_usize), None);
3005
3006     assert_eq!(Step::backward_checked(135_u16, 100_usize), Some(35_u16));
3007     assert_eq!(Step::backward_checked(u16::MAX, 65500_usize), Some(35_u16));
3008     assert_eq!(Step::backward_checked(10_u16, 11_usize), None);
3009     assert_eq!(Step::backward_checked(90_i16, 200_usize), Some(-110_i16));
3010     assert_eq!(Step::backward_checked(30_020_i16, 50_050_usize), Some(-20_030_i16));
3011     assert_eq!(Step::backward_checked(-10_i16, 40_000_usize), None);
3012     assert_eq!(Step::backward_checked(-10_i16, 70_000_usize), None);
3013
3014     assert_eq!(Step::backward_checked(70_010_u128, 70_000_usize), Some(10_u128));
3015     assert_eq!(Step::backward_checked(70_020_i128, 70_030_usize), Some(-10_i128));
3016     assert_eq!(Step::backward_checked(10_u128, 7_usize), Some(3_u128));
3017     assert_eq!(Step::backward_checked(10_u128, 11_usize), None);
3018     assert_eq!(
3019         Step::backward_checked(-0x7fff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_i128, 0x100_usize),
3020         Some(i128::MIN)
3021     );
3022 }
3023
3024 #[test]
3025 fn test_rev_try_folds() {
3026     let f = &|acc, x| i32::checked_add(2 * acc, x);
3027     assert_eq!((1..10).rev().try_fold(7, f), (1..10).try_rfold(7, f));
3028     assert_eq!((1..10).rev().try_rfold(7, f), (1..10).try_fold(7, f));
3029
3030     let a = [10, 20, 30, 40, 100, 60, 70, 80, 90];
3031     let mut iter = a.iter().rev();
3032     assert_eq!(iter.try_fold(0_i8, |acc, &x| acc.checked_add(x)), None);
3033     assert_eq!(iter.next(), Some(&70));
3034     let mut iter = a.iter().rev();
3035     assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None);
3036     assert_eq!(iter.next_back(), Some(&60));
3037 }
3038
3039 #[test]
3040 fn test_cloned_try_folds() {
3041     let a = [1, 2, 3, 4, 5, 6, 7, 8, 9];
3042     let f = &|acc, x| i32::checked_add(2 * acc, x);
3043     let f_ref = &|acc, &x| i32::checked_add(2 * acc, x);
3044     assert_eq!(a.iter().cloned().try_fold(7, f), a.iter().try_fold(7, f_ref));
3045     assert_eq!(a.iter().cloned().try_rfold(7, f), a.iter().try_rfold(7, f_ref));
3046
3047     let a = [10, 20, 30, 40, 100, 60, 70, 80, 90];
3048     let mut iter = a.iter().cloned();
3049     assert_eq!(iter.try_fold(0_i8, |acc, x| acc.checked_add(x)), None);
3050     assert_eq!(iter.next(), Some(60));
3051     let mut iter = a.iter().cloned();
3052     assert_eq!(iter.try_rfold(0_i8, |acc, x| acc.checked_add(x)), None);
3053     assert_eq!(iter.next_back(), Some(70));
3054 }
3055
3056 #[test]
3057 fn test_chain_try_folds() {
3058     let c = || (0..10).chain(10..20);
3059
3060     let f = &|acc, x| i32::checked_add(2 * acc, x);
3061     assert_eq!(c().try_fold(7, f), (0..20).try_fold(7, f));
3062     assert_eq!(c().try_rfold(7, f), (0..20).rev().try_fold(7, f));
3063
3064     let mut iter = c();
3065     assert_eq!(iter.position(|x| x == 5), Some(5));
3066     assert_eq!(iter.next(), Some(6), "stopped in front, state Both");
3067     assert_eq!(iter.position(|x| x == 13), Some(6));
3068     assert_eq!(iter.next(), Some(14), "stopped in back, state Back");
3069     assert_eq!(iter.try_fold(0, |acc, x| Some(acc + x)), Some((15..20).sum()));
3070
3071     let mut iter = c().rev(); // use rev to access try_rfold
3072     assert_eq!(iter.position(|x| x == 15), Some(4));
3073     assert_eq!(iter.next(), Some(14), "stopped in back, state Both");
3074     assert_eq!(iter.position(|x| x == 5), Some(8));
3075     assert_eq!(iter.next(), Some(4), "stopped in front, state Front");
3076     assert_eq!(iter.try_fold(0, |acc, x| Some(acc + x)), Some((0..4).sum()));
3077
3078     let mut iter = c();
3079     iter.by_ref().rev().nth(14); // skip the last 15, ending in state Front
3080     assert_eq!(iter.try_fold(7, f), (0..5).try_fold(7, f));
3081
3082     let mut iter = c();
3083     iter.nth(14); // skip the first 15, ending in state Back
3084     assert_eq!(iter.try_rfold(7, f), (15..20).try_rfold(7, f));
3085 }
3086
3087 #[test]
3088 fn test_map_try_folds() {
3089     let f = &|acc, x| i32::checked_add(2 * acc, x);
3090     assert_eq!((0..10).map(|x| x + 3).try_fold(7, f), (3..13).try_fold(7, f));
3091     assert_eq!((0..10).map(|x| x + 3).try_rfold(7, f), (3..13).try_rfold(7, f));
3092
3093     let mut iter = (0..40).map(|x| x + 10);
3094     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3095     assert_eq!(iter.next(), Some(20));
3096     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3097     assert_eq!(iter.next_back(), Some(46));
3098 }
3099
3100 #[test]
3101 fn test_filter_try_folds() {
3102     fn p(&x: &i32) -> bool {
3103         0 <= x && x < 10
3104     }
3105     let f = &|acc, x| i32::checked_add(2 * acc, x);
3106     assert_eq!((-10..20).filter(p).try_fold(7, f), (0..10).try_fold(7, f));
3107     assert_eq!((-10..20).filter(p).try_rfold(7, f), (0..10).try_rfold(7, f));
3108
3109     let mut iter = (0..40).filter(|&x| x % 2 == 1);
3110     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3111     assert_eq!(iter.next(), Some(25));
3112     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3113     assert_eq!(iter.next_back(), Some(31));
3114 }
3115
3116 #[test]
3117 fn test_filter_map_try_folds() {
3118     let mp = &|x| if 0 <= x && x < 10 { Some(x * 2) } else { None };
3119     let f = &|acc, x| i32::checked_add(2 * acc, x);
3120     assert_eq!((-9..20).filter_map(mp).try_fold(7, f), (0..10).map(|x| 2 * x).try_fold(7, f));
3121     assert_eq!((-9..20).filter_map(mp).try_rfold(7, f), (0..10).map(|x| 2 * x).try_rfold(7, f));
3122
3123     let mut iter = (0..40).filter_map(|x| if x % 2 == 1 { None } else { Some(x * 2 + 10) });
3124     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3125     assert_eq!(iter.next(), Some(38));
3126     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3127     assert_eq!(iter.next_back(), Some(78));
3128 }
3129
3130 #[test]
3131 fn test_enumerate_try_folds() {
3132     let f = &|acc, (i, x)| usize::checked_add(2 * acc, x / (i + 1) + i);
3133     assert_eq!((9..18).enumerate().try_fold(7, f), (0..9).map(|i| (i, i + 9)).try_fold(7, f));
3134     assert_eq!((9..18).enumerate().try_rfold(7, f), (0..9).map(|i| (i, i + 9)).try_rfold(7, f));
3135
3136     let mut iter = (100..200).enumerate();
3137     let f = &|acc, (i, x)| u8::checked_add(acc, u8::checked_div(x, i as u8 + 1)?);
3138     assert_eq!(iter.try_fold(0, f), None);
3139     assert_eq!(iter.next(), Some((7, 107)));
3140     assert_eq!(iter.try_rfold(0, f), None);
3141     assert_eq!(iter.next_back(), Some((11, 111)));
3142 }
3143
3144 #[test]
3145 fn test_peek_try_folds() {
3146     let f = &|acc, x| i32::checked_add(2 * acc, x);
3147
3148     assert_eq!((1..20).peekable().try_fold(7, f), (1..20).try_fold(7, f));
3149     assert_eq!((1..20).peekable().try_rfold(7, f), (1..20).try_rfold(7, f));
3150
3151     let mut iter = (1..20).peekable();
3152     assert_eq!(iter.peek(), Some(&1));
3153     assert_eq!(iter.try_fold(7, f), (1..20).try_fold(7, f));
3154
3155     let mut iter = (1..20).peekable();
3156     assert_eq!(iter.peek(), Some(&1));
3157     assert_eq!(iter.try_rfold(7, f), (1..20).try_rfold(7, f));
3158
3159     let mut iter = [100, 20, 30, 40, 50, 60, 70].iter().cloned().peekable();
3160     assert_eq!(iter.peek(), Some(&100));
3161     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3162     assert_eq!(iter.peek(), Some(&40));
3163
3164     let mut iter = [100, 20, 30, 40, 50, 60, 70].iter().cloned().peekable();
3165     assert_eq!(iter.peek(), Some(&100));
3166     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3167     assert_eq!(iter.peek(), Some(&100));
3168     assert_eq!(iter.next_back(), Some(50));
3169
3170     let mut iter = (2..5).peekable();
3171     assert_eq!(iter.peek(), Some(&2));
3172     assert_eq!(iter.try_for_each(Err), Err(2));
3173     assert_eq!(iter.peek(), Some(&3));
3174     assert_eq!(iter.try_for_each(Err), Err(3));
3175     assert_eq!(iter.peek(), Some(&4));
3176     assert_eq!(iter.try_for_each(Err), Err(4));
3177     assert_eq!(iter.peek(), None);
3178     assert_eq!(iter.try_for_each(Err), Ok(()));
3179
3180     let mut iter = (2..5).peekable();
3181     assert_eq!(iter.peek(), Some(&2));
3182     assert_eq!(iter.try_rfold((), |(), x| Err(x)), Err(4));
3183     assert_eq!(iter.peek(), Some(&2));
3184     assert_eq!(iter.try_rfold((), |(), x| Err(x)), Err(3));
3185     assert_eq!(iter.peek(), Some(&2));
3186     assert_eq!(iter.try_rfold((), |(), x| Err(x)), Err(2));
3187     assert_eq!(iter.peek(), None);
3188     assert_eq!(iter.try_rfold((), |(), x| Err(x)), Ok(()));
3189 }
3190
3191 #[test]
3192 fn test_skip_while_try_fold() {
3193     let f = &|acc, x| i32::checked_add(2 * acc, x);
3194     fn p(&x: &i32) -> bool {
3195         (x % 10) <= 5
3196     }
3197     assert_eq!((1..20).skip_while(p).try_fold(7, f), (6..20).try_fold(7, f));
3198     let mut iter = (1..20).skip_while(p);
3199     assert_eq!(iter.nth(5), Some(11));
3200     assert_eq!(iter.try_fold(7, f), (12..20).try_fold(7, f));
3201
3202     let mut iter = (0..50).skip_while(|&x| (x % 20) < 15);
3203     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3204     assert_eq!(iter.next(), Some(23));
3205 }
3206
3207 #[test]
3208 fn test_take_while_folds() {
3209     let f = &|acc, x| i32::checked_add(2 * acc, x);
3210     assert_eq!((1..20).take_while(|&x| x != 10).try_fold(7, f), (1..10).try_fold(7, f));
3211     let mut iter = (1..20).take_while(|&x| x != 10);
3212     assert_eq!(iter.try_fold(0, |x, y| Some(x + y)), Some((1..10).sum()));
3213     assert_eq!(iter.next(), None, "flag should be set");
3214     let iter = (1..20).take_while(|&x| x != 10);
3215     assert_eq!(iter.fold(0, |x, y| x + y), (1..10).sum());
3216
3217     let mut iter = (10..50).take_while(|&x| x != 40);
3218     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3219     assert_eq!(iter.next(), Some(20));
3220 }
3221
3222 #[test]
3223 fn test_skip_try_folds() {
3224     let f = &|acc, x| i32::checked_add(2 * acc, x);
3225     assert_eq!((1..20).skip(9).try_fold(7, f), (10..20).try_fold(7, f));
3226     assert_eq!((1..20).skip(9).try_rfold(7, f), (10..20).try_rfold(7, f));
3227
3228     let mut iter = (0..30).skip(10);
3229     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3230     assert_eq!(iter.next(), Some(20));
3231     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3232     assert_eq!(iter.next_back(), Some(24));
3233 }
3234
3235 #[test]
3236 fn test_skip_nth_back() {
3237     let xs = [0, 1, 2, 3, 4, 5];
3238     let mut it = xs.iter().skip(2);
3239     assert_eq!(it.nth_back(0), Some(&5));
3240     assert_eq!(it.nth_back(1), Some(&3));
3241     assert_eq!(it.nth_back(0), Some(&2));
3242     assert_eq!(it.nth_back(0), None);
3243
3244     let ys = [2, 3, 4, 5];
3245     let mut ity = ys.iter();
3246     let mut it = xs.iter().skip(2);
3247     assert_eq!(it.nth_back(1), ity.nth_back(1));
3248     assert_eq!(it.clone().nth(0), ity.clone().nth(0));
3249     assert_eq!(it.nth_back(0), ity.nth_back(0));
3250     assert_eq!(it.clone().nth(0), ity.clone().nth(0));
3251     assert_eq!(it.nth_back(0), ity.nth_back(0));
3252     assert_eq!(it.clone().nth(0), ity.clone().nth(0));
3253     assert_eq!(it.nth_back(0), ity.nth_back(0));
3254     assert_eq!(it.clone().nth(0), ity.clone().nth(0));
3255
3256     let mut it = xs.iter().skip(2);
3257     assert_eq!(it.nth_back(4), None);
3258     assert_eq!(it.nth_back(0), None);
3259
3260     let mut it = xs.iter();
3261     it.by_ref().skip(2).nth_back(3);
3262     assert_eq!(it.next_back(), Some(&1));
3263
3264     let mut it = xs.iter();
3265     it.by_ref().skip(2).nth_back(10);
3266     assert_eq!(it.next_back(), Some(&1));
3267 }
3268
3269 #[test]
3270 fn test_take_try_folds() {
3271     let f = &|acc, x| i32::checked_add(2 * acc, x);
3272     assert_eq!((10..30).take(10).try_fold(7, f), (10..20).try_fold(7, f));
3273     assert_eq!((10..30).take(10).try_rfold(7, f), (10..20).try_rfold(7, f));
3274
3275     let mut iter = (10..30).take(20);
3276     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3277     assert_eq!(iter.next(), Some(20));
3278     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3279     assert_eq!(iter.next_back(), Some(24));
3280
3281     let mut iter = (2..20).take(3);
3282     assert_eq!(iter.try_for_each(Err), Err(2));
3283     assert_eq!(iter.try_for_each(Err), Err(3));
3284     assert_eq!(iter.try_for_each(Err), Err(4));
3285     assert_eq!(iter.try_for_each(Err), Ok(()));
3286
3287     let mut iter = (2..20).take(3).rev();
3288     assert_eq!(iter.try_for_each(Err), Err(4));
3289     assert_eq!(iter.try_for_each(Err), Err(3));
3290     assert_eq!(iter.try_for_each(Err), Err(2));
3291     assert_eq!(iter.try_for_each(Err), Ok(()));
3292 }
3293
3294 #[test]
3295 fn test_flat_map_try_folds() {
3296     let f = &|acc, x| i32::checked_add(acc * 2 / 3, x);
3297     let mr = &|x| (5 * x)..(5 * x + 5);
3298     assert_eq!((0..10).flat_map(mr).try_fold(7, f), (0..50).try_fold(7, f));
3299     assert_eq!((0..10).flat_map(mr).try_rfold(7, f), (0..50).try_rfold(7, f));
3300     let mut iter = (0..10).flat_map(mr);
3301     iter.next();
3302     iter.next_back(); // have front and back iters in progress
3303     assert_eq!(iter.try_rfold(7, f), (1..49).try_rfold(7, f));
3304
3305     let mut iter = (0..10).flat_map(|x| (4 * x)..(4 * x + 4));
3306     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3307     assert_eq!(iter.next(), Some(17));
3308     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3309     assert_eq!(iter.next_back(), Some(35));
3310 }
3311
3312 #[test]
3313 fn test_flatten_try_folds() {
3314     let f = &|acc, x| i32::checked_add(acc * 2 / 3, x);
3315     let mr = &|x| (5 * x)..(5 * x + 5);
3316     assert_eq!((0..10).map(mr).flatten().try_fold(7, f), (0..50).try_fold(7, f));
3317     assert_eq!((0..10).map(mr).flatten().try_rfold(7, f), (0..50).try_rfold(7, f));
3318     let mut iter = (0..10).map(mr).flatten();
3319     iter.next();
3320     iter.next_back(); // have front and back iters in progress
3321     assert_eq!(iter.try_rfold(7, f), (1..49).try_rfold(7, f));
3322
3323     let mut iter = (0..10).map(|x| (4 * x)..(4 * x + 4)).flatten();
3324     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3325     assert_eq!(iter.next(), Some(17));
3326     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3327     assert_eq!(iter.next_back(), Some(35));
3328 }
3329
3330 #[test]
3331 fn test_functor_laws() {
3332     // identity:
3333     fn identity<T>(x: T) -> T {
3334         x
3335     }
3336     assert_eq!((0..10).map(identity).sum::<usize>(), (0..10).sum());
3337
3338     // composition:
3339     fn f(x: usize) -> usize {
3340         x + 3
3341     }
3342     fn g(x: usize) -> usize {
3343         x * 2
3344     }
3345     fn h(x: usize) -> usize {
3346         g(f(x))
3347     }
3348     assert_eq!((0..10).map(f).map(g).sum::<usize>(), (0..10).map(h).sum());
3349 }
3350
3351 #[test]
3352 fn test_monad_laws_left_identity() {
3353     fn f(x: usize) -> impl Iterator<Item = usize> {
3354         (0..10).map(move |y| x * y)
3355     }
3356     assert_eq!(once(42).flat_map(f.clone()).sum::<usize>(), f(42).sum());
3357 }
3358
3359 #[test]
3360 fn test_monad_laws_right_identity() {
3361     assert_eq!((0..10).flat_map(|x| once(x)).sum::<usize>(), (0..10).sum());
3362 }
3363
3364 #[test]
3365 fn test_monad_laws_associativity() {
3366     fn f(x: usize) -> impl Iterator<Item = usize> {
3367         0..x
3368     }
3369     fn g(x: usize) -> impl Iterator<Item = usize> {
3370         (0..x).rev()
3371     }
3372     assert_eq!(
3373         (0..10).flat_map(f).flat_map(g).sum::<usize>(),
3374         (0..10).flat_map(|x| f(x).flat_map(g)).sum::<usize>()
3375     );
3376 }
3377
3378 #[test]
3379 fn test_is_sorted() {
3380     assert!([1, 2, 2, 9].iter().is_sorted());
3381     assert!(![1, 3, 2].iter().is_sorted());
3382     assert!([0].iter().is_sorted());
3383     assert!(std::iter::empty::<i32>().is_sorted());
3384     assert!(![0.0, 1.0, f32::NAN].iter().is_sorted());
3385     assert!([-2, -1, 0, 3].iter().is_sorted());
3386     assert!(![-2i32, -1, 0, 3].iter().is_sorted_by_key(|n| n.abs()));
3387     assert!(!["c", "bb", "aaa"].iter().is_sorted());
3388     assert!(["c", "bb", "aaa"].iter().is_sorted_by_key(|s| s.len()));
3389 }
3390
3391 #[test]
3392 fn test_partition() {
3393     fn check(xs: &mut [i32], ref p: impl Fn(&i32) -> bool, expected: usize) {
3394         let i = xs.iter_mut().partition_in_place(p);
3395         assert_eq!(expected, i);
3396         assert!(xs[..i].iter().all(p));
3397         assert!(!xs[i..].iter().any(p));
3398         assert!(xs.iter().is_partitioned(p));
3399         if i == 0 || i == xs.len() {
3400             assert!(xs.iter().rev().is_partitioned(p));
3401         } else {
3402             assert!(!xs.iter().rev().is_partitioned(p));
3403         }
3404     }
3405
3406     check(&mut [], |_| true, 0);
3407     check(&mut [], |_| false, 0);
3408
3409     check(&mut [0], |_| true, 1);
3410     check(&mut [0], |_| false, 0);
3411
3412     check(&mut [-1, 1], |&x| x > 0, 1);
3413     check(&mut [-1, 1], |&x| x < 0, 1);
3414
3415     let ref mut xs = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
3416     check(xs, |_| true, 10);
3417     check(xs, |_| false, 0);
3418     check(xs, |&x| x % 2 == 0, 5); // evens
3419     check(xs, |&x| x % 2 == 1, 5); // odds
3420     check(xs, |&x| x % 3 == 0, 4); // multiple of 3
3421     check(xs, |&x| x % 4 == 0, 3); // multiple of 4
3422     check(xs, |&x| x % 5 == 0, 2); // multiple of 5
3423     check(xs, |&x| x < 3, 3); // small
3424     check(xs, |&x| x > 6, 3); // large
3425 }
3426
3427 /// An iterator that panics whenever `next` or next_back` is called
3428 /// after `None` has already been returned. This does not violate
3429 /// `Iterator`'s contract. Used to test that iterator adaptors don't
3430 /// poll their inner iterators after exhausting them.
3431 struct NonFused<I> {
3432     iter: I,
3433     done: bool,
3434 }
3435
3436 impl<I> NonFused<I> {
3437     fn new(iter: I) -> Self {
3438         Self { iter, done: false }
3439     }
3440 }
3441
3442 impl<I> Iterator for NonFused<I>
3443 where
3444     I: Iterator,
3445 {
3446     type Item = I::Item;
3447
3448     fn next(&mut self) -> Option<Self::Item> {
3449         assert!(!self.done, "this iterator has already returned None");
3450         self.iter.next().or_else(|| {
3451             self.done = true;
3452             None
3453         })
3454     }
3455 }
3456
3457 impl<I> DoubleEndedIterator for NonFused<I>
3458 where
3459     I: DoubleEndedIterator,
3460 {
3461     fn next_back(&mut self) -> Option<Self::Item> {
3462         assert!(!self.done, "this iterator has already returned None");
3463         self.iter.next_back().or_else(|| {
3464             self.done = true;
3465             None
3466         })
3467     }
3468 }
3469
3470 #[test]
3471 fn test_peekable_non_fused() {
3472     let mut iter = NonFused::new(empty::<i32>()).peekable();
3473
3474     assert_eq!(iter.peek(), None);
3475     assert_eq!(iter.next_back(), None);
3476 }
3477
3478 #[test]
3479 fn test_flatten_non_fused_outer() {
3480     let mut iter = NonFused::new(once(0..2)).flatten();
3481
3482     assert_eq!(iter.next_back(), Some(1));
3483     assert_eq!(iter.next(), Some(0));
3484     assert_eq!(iter.next(), None);
3485 }
3486
3487 #[test]
3488 fn test_flatten_non_fused_inner() {
3489     let mut iter = once(0..1).chain(once(1..3)).flat_map(NonFused::new);
3490
3491     assert_eq!(iter.next_back(), Some(2));
3492     assert_eq!(iter.next(), Some(0));
3493     assert_eq!(iter.next(), Some(1));
3494     assert_eq!(iter.next(), None);
3495 }
3496
3497 #[test]
3498 pub fn extend_for_unit() {
3499     let mut x = 0;
3500     {
3501         let iter = (0..5).map(|_| {
3502             x += 1;
3503         });
3504         ().extend(iter);
3505     }
3506     assert_eq!(x, 5);
3507 }
3508
3509 #[test]
3510 fn test_intersperse() {
3511     let v = std::iter::empty().intersperse(0u32).collect::<Vec<_>>();
3512     assert_eq!(v, vec![]);
3513
3514     let v = std::iter::once(1).intersperse(0).collect::<Vec<_>>();
3515     assert_eq!(v, vec![1]);
3516
3517     let xs = ["a", "", "b", "c"];
3518     let v: Vec<&str> = xs.iter().map(|x| x.clone()).intersperse(", ").collect();
3519     let text: String = v.concat();
3520     assert_eq!(text, "a, , b, c".to_string());
3521
3522     let ys = [0, 1, 2, 3];
3523     let mut it = ys[..0].iter().map(|x| *x).intersperse(1);
3524     assert!(it.next() == None);
3525 }
3526
3527 #[test]
3528 fn test_intersperse_size_hint() {
3529     let iter = std::iter::empty::<i32>().intersperse(0);
3530     assert_eq!(iter.size_hint(), (0, Some(0)));
3531
3532     let xs = ["a", "", "b", "c"];
3533     let mut iter = xs.iter().map(|x| x.clone()).intersperse(", ");
3534     assert_eq!(iter.size_hint(), (7, Some(7)));
3535
3536     assert_eq!(iter.next(), Some("a"));
3537     assert_eq!(iter.size_hint(), (6, Some(6)));
3538     assert_eq!(iter.next(), Some(", "));
3539     assert_eq!(iter.size_hint(), (5, Some(5)));
3540
3541     assert_eq!([].iter().intersperse(&()).size_hint(), (0, Some(0)));
3542 }
3543
3544 #[test]
3545 fn test_fold_specialization_intersperse() {
3546     let mut iter = (1..2).intersperse(0);
3547     iter.clone().for_each(|x| assert_eq!(Some(x), iter.next()));
3548
3549     let mut iter = (1..3).intersperse(0);
3550     iter.clone().for_each(|x| assert_eq!(Some(x), iter.next()));
3551
3552     let mut iter = (1..4).intersperse(0);
3553     iter.clone().for_each(|x| assert_eq!(Some(x), iter.next()));
3554 }
3555
3556 #[test]
3557 fn test_try_fold_specialization_intersperse_ok() {
3558     let mut iter = (1..2).intersperse(0);
3559     iter.clone().try_for_each(|x| {
3560         assert_eq!(Some(x), iter.next());
3561         Some(())
3562     });
3563
3564     let mut iter = (1..3).intersperse(0);
3565     iter.clone().try_for_each(|x| {
3566         assert_eq!(Some(x), iter.next());
3567         Some(())
3568     });
3569
3570     let mut iter = (1..4).intersperse(0);
3571     iter.clone().try_for_each(|x| {
3572         assert_eq!(Some(x), iter.next());
3573         Some(())
3574     });
3575 }
3576
3577 #[test]
3578 fn test_try_fold_specialization_intersperse_err() {
3579     let orig_iter = ["a", "b"].iter().copied().intersperse("-");
3580
3581     // Abort after the first item.
3582     let mut iter = orig_iter.clone();
3583     iter.try_for_each(|_| None::<()>);
3584     assert_eq!(iter.next(), Some("-"));
3585     assert_eq!(iter.next(), Some("b"));
3586     assert_eq!(iter.next(), None);
3587
3588     // Abort after the second item.
3589     let mut iter = orig_iter.clone();
3590     iter.try_for_each(|item| if item == "-" { None } else { Some(()) });
3591     assert_eq!(iter.next(), Some("b"));
3592     assert_eq!(iter.next(), None);
3593
3594     // Abort after the third item.
3595     let mut iter = orig_iter.clone();
3596     iter.try_for_each(|item| if item == "b" { None } else { Some(()) });
3597     assert_eq!(iter.next(), None);
3598 }
3599
3600 #[test]
3601 fn test_intersperse_with() {
3602     #[derive(PartialEq, Debug)]
3603     struct NotClone {
3604         u: u32,
3605     }
3606     let r = vec![NotClone { u: 0 }, NotClone { u: 1 }]
3607         .into_iter()
3608         .intersperse_with(|| NotClone { u: 2 })
3609         .collect::<Vec<_>>();
3610     assert_eq!(r, vec![NotClone { u: 0 }, NotClone { u: 2 }, NotClone { u: 1 }]);
3611
3612     let mut ctr = 100;
3613     let separator = || {
3614         ctr *= 2;
3615         ctr
3616     };
3617     let r = (0..3).intersperse_with(separator).collect::<Vec<_>>();
3618     assert_eq!(r, vec![0, 200, 1, 400, 2]);
3619 }