src/libcore/tests/iter.rs

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