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().map_while(|_| None::<()>).size_hint(), (0, None));
1481     assert_eq!(c.clone().skip_while(|_| false).size_hint(), (0, None));
1482     assert_eq!(c.clone().enumerate().size_hint(), (usize::MAX, None));
1483     assert_eq!(c.clone().chain(vi.clone().cloned()).size_hint(), (usize::MAX, None));
1484     assert_eq!(c.clone().zip(vi.clone()).size_hint(), (10, Some(10)));
1485     assert_eq!(c.clone().scan(0, |_, _| Some(0)).size_hint(), (0, None));
1486     assert_eq!(c.clone().filter(|_| false).size_hint(), (0, None));
1487     assert_eq!(c.clone().map(|_| 0).size_hint(), (usize::MAX, None));
1488     assert_eq!(c.filter_map(|_| Some(0)).size_hint(), (0, None));
1489
1490     assert_eq!(vi.clone().take(5).size_hint(), (5, Some(5)));
1491     assert_eq!(vi.clone().take(12).size_hint(), (10, Some(10)));
1492     assert_eq!(vi.clone().skip(3).size_hint(), (7, Some(7)));
1493     assert_eq!(vi.clone().skip(12).size_hint(), (0, Some(0)));
1494     assert_eq!(vi.clone().take_while(|_| false).size_hint(), (0, Some(10)));
1495     assert_eq!(vi.clone().map_while(|_| None::<()>).size_hint(), (0, Some(10)));
1496     assert_eq!(vi.clone().skip_while(|_| false).size_hint(), (0, Some(10)));
1497     assert_eq!(vi.clone().enumerate().size_hint(), (10, Some(10)));
1498     assert_eq!(vi.clone().chain(v2).size_hint(), (13, Some(13)));
1499     assert_eq!(vi.clone().zip(v2).size_hint(), (3, Some(3)));
1500     assert_eq!(vi.clone().scan(0, |_, _| Some(0)).size_hint(), (0, Some(10)));
1501     assert_eq!(vi.clone().filter(|_| false).size_hint(), (0, Some(10)));
1502     assert_eq!(vi.clone().map(|&i| i + 1).size_hint(), (10, Some(10)));
1503     assert_eq!(vi.filter_map(|_| Some(0)).size_hint(), (0, Some(10)));
1504 }
1505
1506 #[test]
1507 fn test_collect() {
1508     let a = vec![1, 2, 3, 4, 5];
1509     let b: Vec<isize> = a.iter().cloned().collect();
1510     assert!(a == b);
1511 }
1512
1513 #[test]
1514 fn test_all() {
1515     let v: Box<[isize]> = Box::new([1, 2, 3, 4, 5]);
1516     assert!(v.iter().all(|&x| x < 10));
1517     assert!(!v.iter().all(|&x| x % 2 == 0));
1518     assert!(!v.iter().all(|&x| x > 100));
1519     assert!(v[..0].iter().all(|_| panic!()));
1520 }
1521
1522 #[test]
1523 fn test_any() {
1524     let v: Box<[isize]> = Box::new([1, 2, 3, 4, 5]);
1525     assert!(v.iter().any(|&x| x < 10));
1526     assert!(v.iter().any(|&x| x % 2 == 0));
1527     assert!(!v.iter().any(|&x| x > 100));
1528     assert!(!v[..0].iter().any(|_| panic!()));
1529 }
1530
1531 #[test]
1532 fn test_find() {
1533     let v: &[isize] = &[1, 3, 9, 27, 103, 14, 11];
1534     assert_eq!(*v.iter().find(|&&x| x & 1 == 0).unwrap(), 14);
1535     assert_eq!(*v.iter().find(|&&x| x % 3 == 0).unwrap(), 3);
1536     assert!(v.iter().find(|&&x| x % 12 == 0).is_none());
1537 }
1538
1539 #[test]
1540 fn test_find_map() {
1541     let xs: &[isize] = &[];
1542     assert_eq!(xs.iter().find_map(half_if_even), None);
1543     let xs: &[isize] = &[3, 5];
1544     assert_eq!(xs.iter().find_map(half_if_even), None);
1545     let xs: &[isize] = &[4, 5];
1546     assert_eq!(xs.iter().find_map(half_if_even), Some(2));
1547     let xs: &[isize] = &[3, 6];
1548     assert_eq!(xs.iter().find_map(half_if_even), Some(3));
1549
1550     let xs: &[isize] = &[1, 2, 3, 4, 5, 6, 7];
1551     let mut iter = xs.iter();
1552     assert_eq!(iter.find_map(half_if_even), Some(1));
1553     assert_eq!(iter.find_map(half_if_even), Some(2));
1554     assert_eq!(iter.find_map(half_if_even), Some(3));
1555     assert_eq!(iter.next(), Some(&7));
1556
1557     fn half_if_even(x: &isize) -> Option<isize> {
1558         if x % 2 == 0 { Some(x / 2) } else { None }
1559     }
1560 }
1561
1562 #[test]
1563 fn test_try_find() {
1564     let xs: &[isize] = &[];
1565     assert_eq!(xs.iter().try_find(testfn), Ok(None));
1566     let xs: &[isize] = &[1, 2, 3, 4];
1567     assert_eq!(xs.iter().try_find(testfn), Ok(Some(&2)));
1568     let xs: &[isize] = &[1, 3, 4];
1569     assert_eq!(xs.iter().try_find(testfn), Err(()));
1570
1571     let xs: &[isize] = &[1, 2, 3, 4, 5, 6, 7];
1572     let mut iter = xs.iter();
1573     assert_eq!(iter.try_find(testfn), Ok(Some(&2)));
1574     assert_eq!(iter.try_find(testfn), Err(()));
1575     assert_eq!(iter.next(), Some(&5));
1576
1577     fn testfn(x: &&isize) -> Result<bool, ()> {
1578         if **x == 2 {
1579             return Ok(true);
1580         }
1581         if **x == 4 {
1582             return Err(());
1583         }
1584         Ok(false)
1585     }
1586 }
1587
1588 #[test]
1589 fn test_try_find_api_usability() -> Result<(), Box<dyn std::error::Error>> {
1590     let a = ["1", "2"];
1591
1592     let is_my_num = |s: &str, search: i32| -> Result<bool, std::num::ParseIntError> {
1593         Ok(s.parse::<i32>()? == search)
1594     };
1595
1596     let val = a.iter().try_find(|&&s| is_my_num(s, 2))?;
1597     assert_eq!(val, Some(&"2"));
1598
1599     Ok(())
1600 }
1601
1602 #[test]
1603 fn test_position() {
1604     let v = &[1, 3, 9, 27, 103, 14, 11];
1605     assert_eq!(v.iter().position(|x| *x & 1 == 0).unwrap(), 5);
1606     assert_eq!(v.iter().position(|x| *x % 3 == 0).unwrap(), 1);
1607     assert!(v.iter().position(|x| *x % 12 == 0).is_none());
1608 }
1609
1610 #[test]
1611 fn test_count() {
1612     let xs = &[1, 2, 2, 1, 5, 9, 0, 2];
1613     assert_eq!(xs.iter().filter(|x| **x == 2).count(), 3);
1614     assert_eq!(xs.iter().filter(|x| **x == 5).count(), 1);
1615     assert_eq!(xs.iter().filter(|x| **x == 95).count(), 0);
1616 }
1617
1618 #[test]
1619 fn test_max_by_key() {
1620     let xs: &[isize] = &[-3, 0, 1, 5, -10];
1621     assert_eq!(*xs.iter().max_by_key(|x| x.abs()).unwrap(), -10);
1622 }
1623
1624 #[test]
1625 fn test_max_by() {
1626     let xs: &[isize] = &[-3, 0, 1, 5, -10];
1627     assert_eq!(*xs.iter().max_by(|x, y| x.abs().cmp(&y.abs())).unwrap(), -10);
1628 }
1629
1630 #[test]
1631 fn test_min_by_key() {
1632     let xs: &[isize] = &[-3, 0, 1, 5, -10];
1633     assert_eq!(*xs.iter().min_by_key(|x| x.abs()).unwrap(), 0);
1634 }
1635
1636 #[test]
1637 fn test_min_by() {
1638     let xs: &[isize] = &[-3, 0, 1, 5, -10];
1639     assert_eq!(*xs.iter().min_by(|x, y| x.abs().cmp(&y.abs())).unwrap(), 0);
1640 }
1641
1642 #[test]
1643 fn test_by_ref() {
1644     let mut xs = 0..10;
1645     // sum the first five values
1646     let partial_sum = xs.by_ref().take(5).fold(0, |a, b| a + b);
1647     assert_eq!(partial_sum, 10);
1648     assert_eq!(xs.next(), Some(5));
1649 }
1650
1651 #[test]
1652 fn test_rev() {
1653     let xs = [2, 4, 6, 8, 10, 12, 14, 16];
1654     let mut it = xs.iter();
1655     it.next();
1656     it.next();
1657     assert!(it.rev().cloned().collect::<Vec<isize>>() == vec![16, 14, 12, 10, 8, 6]);
1658 }
1659
1660 #[test]
1661 fn test_copied() {
1662     let xs = [2, 4, 6, 8];
1663
1664     let mut it = xs.iter().copied();
1665     assert_eq!(it.len(), 4);
1666     assert_eq!(it.next(), Some(2));
1667     assert_eq!(it.len(), 3);
1668     assert_eq!(it.next(), Some(4));
1669     assert_eq!(it.len(), 2);
1670     assert_eq!(it.next_back(), Some(8));
1671     assert_eq!(it.len(), 1);
1672     assert_eq!(it.next_back(), Some(6));
1673     assert_eq!(it.len(), 0);
1674     assert_eq!(it.next_back(), None);
1675 }
1676
1677 #[test]
1678 fn test_cloned() {
1679     let xs = [2, 4, 6, 8];
1680
1681     let mut it = xs.iter().cloned();
1682     assert_eq!(it.len(), 4);
1683     assert_eq!(it.next(), Some(2));
1684     assert_eq!(it.len(), 3);
1685     assert_eq!(it.next(), Some(4));
1686     assert_eq!(it.len(), 2);
1687     assert_eq!(it.next_back(), Some(8));
1688     assert_eq!(it.len(), 1);
1689     assert_eq!(it.next_back(), Some(6));
1690     assert_eq!(it.len(), 0);
1691     assert_eq!(it.next_back(), None);
1692 }
1693
1694 #[test]
1695 fn test_cloned_side_effects() {
1696     let mut count = 0;
1697     {
1698         let iter = [1, 2, 3]
1699             .iter()
1700             .map(|x| {
1701                 count += 1;
1702                 x
1703             })
1704             .cloned()
1705             .zip(&[1]);
1706         for _ in iter {}
1707     }
1708     assert_eq!(count, 2);
1709 }
1710
1711 #[test]
1712 fn test_double_ended_map() {
1713     let xs = [1, 2, 3, 4, 5, 6];
1714     let mut it = xs.iter().map(|&x| x * -1);
1715     assert_eq!(it.next(), Some(-1));
1716     assert_eq!(it.next(), Some(-2));
1717     assert_eq!(it.next_back(), Some(-6));
1718     assert_eq!(it.next_back(), Some(-5));
1719     assert_eq!(it.next(), Some(-3));
1720     assert_eq!(it.next_back(), Some(-4));
1721     assert_eq!(it.next(), None);
1722 }
1723
1724 #[test]
1725 fn test_double_ended_enumerate() {
1726     let xs = [1, 2, 3, 4, 5, 6];
1727     let mut it = xs.iter().cloned().enumerate();
1728     assert_eq!(it.next(), Some((0, 1)));
1729     assert_eq!(it.next(), Some((1, 2)));
1730     assert_eq!(it.next_back(), Some((5, 6)));
1731     assert_eq!(it.next_back(), Some((4, 5)));
1732     assert_eq!(it.next_back(), Some((3, 4)));
1733     assert_eq!(it.next_back(), Some((2, 3)));
1734     assert_eq!(it.next(), None);
1735 }
1736
1737 #[test]
1738 fn test_double_ended_zip() {
1739     let xs = [1, 2, 3, 4, 5, 6];
1740     let ys = [1, 2, 3, 7];
1741     let a = xs.iter().cloned();
1742     let b = ys.iter().cloned();
1743     let mut it = a.zip(b);
1744     assert_eq!(it.next(), Some((1, 1)));
1745     assert_eq!(it.next(), Some((2, 2)));
1746     assert_eq!(it.next_back(), Some((4, 7)));
1747     assert_eq!(it.next_back(), Some((3, 3)));
1748     assert_eq!(it.next(), None);
1749 }
1750
1751 #[test]
1752 fn test_double_ended_filter() {
1753     let xs = [1, 2, 3, 4, 5, 6];
1754     let mut it = xs.iter().filter(|&x| *x & 1 == 0);
1755     assert_eq!(it.next_back().unwrap(), &6);
1756     assert_eq!(it.next_back().unwrap(), &4);
1757     assert_eq!(it.next().unwrap(), &2);
1758     assert_eq!(it.next_back(), None);
1759 }
1760
1761 #[test]
1762 fn test_double_ended_filter_map() {
1763     let xs = [1, 2, 3, 4, 5, 6];
1764     let mut it = xs.iter().filter_map(|&x| if x & 1 == 0 { Some(x * 2) } else { None });
1765     assert_eq!(it.next_back().unwrap(), 12);
1766     assert_eq!(it.next_back().unwrap(), 8);
1767     assert_eq!(it.next().unwrap(), 4);
1768     assert_eq!(it.next_back(), None);
1769 }
1770
1771 #[test]
1772 fn test_double_ended_chain() {
1773     let xs = [1, 2, 3, 4, 5];
1774     let ys = [7, 9, 11];
1775     let mut it = xs.iter().chain(&ys).rev();
1776     assert_eq!(it.next().unwrap(), &11);
1777     assert_eq!(it.next().unwrap(), &9);
1778     assert_eq!(it.next_back().unwrap(), &1);
1779     assert_eq!(it.next_back().unwrap(), &2);
1780     assert_eq!(it.next_back().unwrap(), &3);
1781     assert_eq!(it.next_back().unwrap(), &4);
1782     assert_eq!(it.next_back().unwrap(), &5);
1783     assert_eq!(it.next_back().unwrap(), &7);
1784     assert_eq!(it.next_back(), None);
1785
1786     // test that .chain() is well behaved with an unfused iterator
1787     struct CrazyIterator(bool);
1788     impl CrazyIterator {
1789         fn new() -> CrazyIterator {
1790             CrazyIterator(false)
1791         }
1792     }
1793     impl Iterator for CrazyIterator {
1794         type Item = i32;
1795         fn next(&mut self) -> Option<i32> {
1796             if self.0 {
1797                 Some(99)
1798             } else {
1799                 self.0 = true;
1800                 None
1801             }
1802         }
1803     }
1804
1805     impl DoubleEndedIterator for CrazyIterator {
1806         fn next_back(&mut self) -> Option<i32> {
1807             self.next()
1808         }
1809     }
1810
1811     assert_eq!(CrazyIterator::new().chain(0..10).rev().last(), Some(0));
1812     assert!((0..10).chain(CrazyIterator::new()).rev().any(|i| i == 0));
1813 }
1814
1815 #[test]
1816 fn test_rposition() {
1817     fn f(xy: &(isize, char)) -> bool {
1818         let (_x, y) = *xy;
1819         y == 'b'
1820     }
1821     fn g(xy: &(isize, char)) -> bool {
1822         let (_x, y) = *xy;
1823         y == 'd'
1824     }
1825     let v = [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
1826
1827     assert_eq!(v.iter().rposition(f), Some(3));
1828     assert!(v.iter().rposition(g).is_none());
1829 }
1830
1831 #[test]
1832 fn test_rev_rposition() {
1833     let v = [0, 0, 1, 1];
1834     assert_eq!(v.iter().rev().rposition(|&x| x == 1), Some(1));
1835 }
1836
1837 #[test]
1838 #[should_panic]
1839 fn test_rposition_panic() {
1840     let v: [(Box<_>, Box<_>); 4] = [(box 0, box 0), (box 0, box 0), (box 0, box 0), (box 0, box 0)];
1841     let mut i = 0;
1842     v.iter().rposition(|_elt| {
1843         if i == 2 {
1844             panic!()
1845         }
1846         i += 1;
1847         false
1848     });
1849 }
1850
1851 #[test]
1852 fn test_double_ended_flat_map() {
1853     let u = [0, 1];
1854     let v = [5, 6, 7, 8];
1855     let mut it = u.iter().flat_map(|x| &v[*x..v.len()]);
1856     assert_eq!(it.next_back().unwrap(), &8);
1857     assert_eq!(it.next().unwrap(), &5);
1858     assert_eq!(it.next_back().unwrap(), &7);
1859     assert_eq!(it.next_back().unwrap(), &6);
1860     assert_eq!(it.next_back().unwrap(), &8);
1861     assert_eq!(it.next().unwrap(), &6);
1862     assert_eq!(it.next_back().unwrap(), &7);
1863     assert_eq!(it.next_back(), None);
1864     assert_eq!(it.next(), None);
1865     assert_eq!(it.next_back(), None);
1866 }
1867
1868 #[test]
1869 fn test_double_ended_flatten() {
1870     let u = [0, 1];
1871     let v = [5, 6, 7, 8];
1872     let mut it = u.iter().map(|x| &v[*x..v.len()]).flatten();
1873     assert_eq!(it.next_back().unwrap(), &8);
1874     assert_eq!(it.next().unwrap(), &5);
1875     assert_eq!(it.next_back().unwrap(), &7);
1876     assert_eq!(it.next_back().unwrap(), &6);
1877     assert_eq!(it.next_back().unwrap(), &8);
1878     assert_eq!(it.next().unwrap(), &6);
1879     assert_eq!(it.next_back().unwrap(), &7);
1880     assert_eq!(it.next_back(), None);
1881     assert_eq!(it.next(), None);
1882     assert_eq!(it.next_back(), None);
1883 }
1884
1885 #[test]
1886 fn test_double_ended_range() {
1887     assert_eq!((11..14).rev().collect::<Vec<_>>(), [13, 12, 11]);
1888     for _ in (10..0).rev() {
1889         panic!("unreachable");
1890     }
1891
1892     assert_eq!((11..14).rev().collect::<Vec<_>>(), [13, 12, 11]);
1893     for _ in (10..0).rev() {
1894         panic!("unreachable");
1895     }
1896 }
1897
1898 #[test]
1899 fn test_range() {
1900     assert_eq!((0..5).collect::<Vec<_>>(), [0, 1, 2, 3, 4]);
1901     assert_eq!((-10..-1).collect::<Vec<_>>(), [-10, -9, -8, -7, -6, -5, -4, -3, -2]);
1902     assert_eq!((0..5).rev().collect::<Vec<_>>(), [4, 3, 2, 1, 0]);
1903     assert_eq!((200..-5).count(), 0);
1904     assert_eq!((200..-5).rev().count(), 0);
1905     assert_eq!((200..200).count(), 0);
1906     assert_eq!((200..200).rev().count(), 0);
1907
1908     assert_eq!((0..100).size_hint(), (100, Some(100)));
1909     // this test is only meaningful when sizeof usize < sizeof u64
1910     assert_eq!((usize::MAX - 1..usize::MAX).size_hint(), (1, Some(1)));
1911     assert_eq!((-10..-1).size_hint(), (9, Some(9)));
1912     assert_eq!((-1..-10).size_hint(), (0, Some(0)));
1913
1914     assert_eq!((-70..58).size_hint(), (128, Some(128)));
1915     assert_eq!((-128..127).size_hint(), (255, Some(255)));
1916     assert_eq!(
1917         (-2..isize::MAX).size_hint(),
1918         (isize::MAX as usize + 2, Some(isize::MAX as usize + 2))
1919     );
1920 }
1921
1922 #[test]
1923 fn test_range_exhaustion() {
1924     let mut r = 10..10;
1925     assert!(r.is_empty());
1926     assert_eq!(r.next(), None);
1927     assert_eq!(r.next_back(), None);
1928     assert_eq!(r, 10..10);
1929
1930     let mut r = 10..12;
1931     assert_eq!(r.next(), Some(10));
1932     assert_eq!(r.next(), Some(11));
1933     assert!(r.is_empty());
1934     assert_eq!(r, 12..12);
1935     assert_eq!(r.next(), None);
1936
1937     let mut r = 10..12;
1938     assert_eq!(r.next_back(), Some(11));
1939     assert_eq!(r.next_back(), Some(10));
1940     assert!(r.is_empty());
1941     assert_eq!(r, 10..10);
1942     assert_eq!(r.next_back(), None);
1943
1944     let mut r = 100..10;
1945     assert!(r.is_empty());
1946     assert_eq!(r.next(), None);
1947     assert_eq!(r.next_back(), None);
1948     assert_eq!(r, 100..10);
1949 }
1950
1951 #[test]
1952 fn test_range_inclusive_exhaustion() {
1953     let mut r = 10..=10;
1954     assert_eq!(r.next(), Some(10));
1955     assert!(r.is_empty());
1956     assert_eq!(r.next(), None);
1957     assert_eq!(r.next(), None);
1958
1959     assert_eq!(*r.start(), 10);
1960     assert_eq!(*r.end(), 10);
1961     assert_ne!(r, 10..=10);
1962
1963     let mut r = 10..=10;
1964     assert_eq!(r.next_back(), Some(10));
1965     assert!(r.is_empty());
1966     assert_eq!(r.next_back(), None);
1967
1968     assert_eq!(*r.start(), 10);
1969     assert_eq!(*r.end(), 10);
1970     assert_ne!(r, 10..=10);
1971
1972     let mut r = 10..=12;
1973     assert_eq!(r.next(), Some(10));
1974     assert_eq!(r.next(), Some(11));
1975     assert_eq!(r.next(), Some(12));
1976     assert!(r.is_empty());
1977     assert_eq!(r.next(), None);
1978
1979     let mut r = 10..=12;
1980     assert_eq!(r.next_back(), Some(12));
1981     assert_eq!(r.next_back(), Some(11));
1982     assert_eq!(r.next_back(), Some(10));
1983     assert!(r.is_empty());
1984     assert_eq!(r.next_back(), None);
1985
1986     let mut r = 10..=12;
1987     assert_eq!(r.nth(2), Some(12));
1988     assert!(r.is_empty());
1989     assert_eq!(r.next(), None);
1990
1991     let mut r = 10..=12;
1992     assert_eq!(r.nth(5), None);
1993     assert!(r.is_empty());
1994     assert_eq!(r.next(), None);
1995
1996     let mut r = 100..=10;
1997     assert_eq!(r.next(), None);
1998     assert!(r.is_empty());
1999     assert_eq!(r.next(), None);
2000     assert_eq!(r.next(), None);
2001     assert_eq!(r, 100..=10);
2002
2003     let mut r = 100..=10;
2004     assert_eq!(r.next_back(), None);
2005     assert!(r.is_empty());
2006     assert_eq!(r.next_back(), None);
2007     assert_eq!(r.next_back(), None);
2008     assert_eq!(r, 100..=10);
2009 }
2010
2011 #[test]
2012 fn test_range_nth() {
2013     assert_eq!((10..15).nth(0), Some(10));
2014     assert_eq!((10..15).nth(1), Some(11));
2015     assert_eq!((10..15).nth(4), Some(14));
2016     assert_eq!((10..15).nth(5), None);
2017
2018     let mut r = 10..20;
2019     assert_eq!(r.nth(2), Some(12));
2020     assert_eq!(r, 13..20);
2021     assert_eq!(r.nth(2), Some(15));
2022     assert_eq!(r, 16..20);
2023     assert_eq!(r.nth(10), None);
2024     assert_eq!(r, 20..20);
2025 }
2026
2027 #[test]
2028 fn test_range_nth_back() {
2029     assert_eq!((10..15).nth_back(0), Some(14));
2030     assert_eq!((10..15).nth_back(1), Some(13));
2031     assert_eq!((10..15).nth_back(4), Some(10));
2032     assert_eq!((10..15).nth_back(5), None);
2033     assert_eq!((-120..80_i8).nth_back(199), Some(-120));
2034
2035     let mut r = 10..20;
2036     assert_eq!(r.nth_back(2), Some(17));
2037     assert_eq!(r, 10..17);
2038     assert_eq!(r.nth_back(2), Some(14));
2039     assert_eq!(r, 10..14);
2040     assert_eq!(r.nth_back(10), None);
2041     assert_eq!(r, 10..10);
2042 }
2043
2044 #[test]
2045 fn test_range_from_nth() {
2046     assert_eq!((10..).nth(0), Some(10));
2047     assert_eq!((10..).nth(1), Some(11));
2048     assert_eq!((10..).nth(4), Some(14));
2049
2050     let mut r = 10..;
2051     assert_eq!(r.nth(2), Some(12));
2052     assert_eq!(r, 13..);
2053     assert_eq!(r.nth(2), Some(15));
2054     assert_eq!(r, 16..);
2055     assert_eq!(r.nth(10), Some(26));
2056     assert_eq!(r, 27..);
2057
2058     assert_eq!((0..).size_hint(), (usize::MAX, None));
2059 }
2060
2061 fn is_trusted_len<I: TrustedLen>(_: I) {}
2062
2063 #[test]
2064 fn test_range_from_take() {
2065     let mut it = (0..).take(3);
2066     assert_eq!(it.next(), Some(0));
2067     assert_eq!(it.next(), Some(1));
2068     assert_eq!(it.next(), Some(2));
2069     assert_eq!(it.next(), None);
2070     is_trusted_len((0..).take(3));
2071     assert_eq!((0..).take(3).size_hint(), (3, Some(3)));
2072     assert_eq!((0..).take(0).size_hint(), (0, Some(0)));
2073     assert_eq!((0..).take(usize::MAX).size_hint(), (usize::MAX, Some(usize::MAX)));
2074 }
2075
2076 #[test]
2077 fn test_range_from_take_collect() {
2078     let v: Vec<_> = (0..).take(3).collect();
2079     assert_eq!(v, vec![0, 1, 2]);
2080 }
2081
2082 #[test]
2083 fn test_range_inclusive_nth() {
2084     assert_eq!((10..=15).nth(0), Some(10));
2085     assert_eq!((10..=15).nth(1), Some(11));
2086     assert_eq!((10..=15).nth(5), Some(15));
2087     assert_eq!((10..=15).nth(6), None);
2088
2089     let mut exhausted_via_next = 10_u8..=20;
2090     while exhausted_via_next.next().is_some() {}
2091
2092     let mut r = 10_u8..=20;
2093     assert_eq!(r.nth(2), Some(12));
2094     assert_eq!(r, 13..=20);
2095     assert_eq!(r.nth(2), Some(15));
2096     assert_eq!(r, 16..=20);
2097     assert_eq!(r.is_empty(), false);
2098     assert_eq!(ExactSizeIterator::is_empty(&r), false);
2099     assert_eq!(r.nth(10), None);
2100     assert_eq!(r.is_empty(), true);
2101     assert_eq!(r, exhausted_via_next);
2102     assert_eq!(ExactSizeIterator::is_empty(&r), true);
2103 }
2104
2105 #[test]
2106 fn test_range_inclusive_nth_back() {
2107     assert_eq!((10..=15).nth_back(0), Some(15));
2108     assert_eq!((10..=15).nth_back(1), Some(14));
2109     assert_eq!((10..=15).nth_back(5), Some(10));
2110     assert_eq!((10..=15).nth_back(6), None);
2111     assert_eq!((-120..=80_i8).nth_back(200), Some(-120));
2112
2113     let mut exhausted_via_next_back = 10_u8..=20;
2114     while exhausted_via_next_back.next_back().is_some() {}
2115
2116     let mut r = 10_u8..=20;
2117     assert_eq!(r.nth_back(2), Some(18));
2118     assert_eq!(r, 10..=17);
2119     assert_eq!(r.nth_back(2), Some(15));
2120     assert_eq!(r, 10..=14);
2121     assert_eq!(r.is_empty(), false);
2122     assert_eq!(ExactSizeIterator::is_empty(&r), false);
2123     assert_eq!(r.nth_back(10), None);
2124     assert_eq!(r.is_empty(), true);
2125     assert_eq!(r, exhausted_via_next_back);
2126     assert_eq!(ExactSizeIterator::is_empty(&r), true);
2127 }
2128
2129 #[test]
2130 fn test_range_step() {
2131     #![allow(deprecated)]
2132
2133     assert_eq!((0..20).step_by(5).collect::<Vec<isize>>(), [0, 5, 10, 15]);
2134     assert_eq!((1..21).rev().step_by(5).collect::<Vec<isize>>(), [20, 15, 10, 5]);
2135     assert_eq!((1..21).rev().step_by(6).collect::<Vec<isize>>(), [20, 14, 8, 2]);
2136     assert_eq!((200..255).step_by(50).collect::<Vec<u8>>(), [200, 250]);
2137     assert_eq!((200..-5).step_by(1).collect::<Vec<isize>>(), []);
2138     assert_eq!((200..200).step_by(1).collect::<Vec<isize>>(), []);
2139
2140     assert_eq!((0..20).step_by(1).size_hint(), (20, Some(20)));
2141     assert_eq!((0..20).step_by(21).size_hint(), (1, Some(1)));
2142     assert_eq!((0..20).step_by(5).size_hint(), (4, Some(4)));
2143     assert_eq!((1..21).rev().step_by(5).size_hint(), (4, Some(4)));
2144     assert_eq!((1..21).rev().step_by(6).size_hint(), (4, Some(4)));
2145     assert_eq!((20..-5).step_by(1).size_hint(), (0, Some(0)));
2146     assert_eq!((20..20).step_by(1).size_hint(), (0, Some(0)));
2147     assert_eq!((i8::MIN..i8::MAX).step_by(-(i8::MIN as i32) as usize).size_hint(), (2, Some(2)));
2148     assert_eq!((i16::MIN..i16::MAX).step_by(i16::MAX as usize).size_hint(), (3, Some(3)));
2149     assert_eq!((isize::MIN..isize::MAX).step_by(1).size_hint(), (usize::MAX, Some(usize::MAX)));
2150 }
2151
2152 #[test]
2153 fn test_step_by_skip() {
2154     assert_eq!((0..640).step_by(128).skip(1).collect::<Vec<_>>(), [128, 256, 384, 512]);
2155     assert_eq!((0..=50).step_by(10).nth(3), Some(30));
2156     assert_eq!((200..=255u8).step_by(10).nth(3), Some(230));
2157 }
2158
2159 #[test]
2160 fn test_range_inclusive_step() {
2161     assert_eq!((0..=50).step_by(10).collect::<Vec<_>>(), [0, 10, 20, 30, 40, 50]);
2162     assert_eq!((0..=5).step_by(1).collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5]);
2163     assert_eq!((200..=255u8).step_by(10).collect::<Vec<_>>(), [200, 210, 220, 230, 240, 250]);
2164     assert_eq!((250..=255u8).step_by(1).collect::<Vec<_>>(), [250, 251, 252, 253, 254, 255]);
2165 }
2166
2167 #[test]
2168 fn test_range_last_max() {
2169     assert_eq!((0..20).last(), Some(19));
2170     assert_eq!((-20..0).last(), Some(-1));
2171     assert_eq!((5..5).last(), None);
2172
2173     assert_eq!((0..20).max(), Some(19));
2174     assert_eq!((-20..0).max(), Some(-1));
2175     assert_eq!((5..5).max(), None);
2176 }
2177
2178 #[test]
2179 fn test_range_inclusive_last_max() {
2180     assert_eq!((0..=20).last(), Some(20));
2181     assert_eq!((-20..=0).last(), Some(0));
2182     assert_eq!((5..=5).last(), Some(5));
2183     let mut r = 10..=10;
2184     r.next();
2185     assert_eq!(r.last(), None);
2186
2187     assert_eq!((0..=20).max(), Some(20));
2188     assert_eq!((-20..=0).max(), Some(0));
2189     assert_eq!((5..=5).max(), Some(5));
2190     let mut r = 10..=10;
2191     r.next();
2192     assert_eq!(r.max(), None);
2193 }
2194
2195 #[test]
2196 fn test_range_min() {
2197     assert_eq!((0..20).min(), Some(0));
2198     assert_eq!((-20..0).min(), Some(-20));
2199     assert_eq!((5..5).min(), None);
2200 }
2201
2202 #[test]
2203 fn test_range_inclusive_min() {
2204     assert_eq!((0..=20).min(), Some(0));
2205     assert_eq!((-20..=0).min(), Some(-20));
2206     assert_eq!((5..=5).min(), Some(5));
2207     let mut r = 10..=10;
2208     r.next();
2209     assert_eq!(r.min(), None);
2210 }
2211
2212 #[test]
2213 fn test_range_inclusive_folds() {
2214     assert_eq!((1..=10).sum::<i32>(), 55);
2215     assert_eq!((1..=10).rev().sum::<i32>(), 55);
2216
2217     let mut it = 44..=50;
2218     assert_eq!(it.try_fold(0, i8::checked_add), None);
2219     assert_eq!(it, 47..=50);
2220     assert_eq!(it.try_fold(0, i8::checked_add), None);
2221     assert_eq!(it, 50..=50);
2222     assert_eq!(it.try_fold(0, i8::checked_add), Some(50));
2223     assert!(it.is_empty());
2224     assert_eq!(it.try_fold(0, i8::checked_add), Some(0));
2225     assert!(it.is_empty());
2226
2227     let mut it = 40..=47;
2228     assert_eq!(it.try_rfold(0, i8::checked_add), None);
2229     assert_eq!(it, 40..=44);
2230     assert_eq!(it.try_rfold(0, i8::checked_add), None);
2231     assert_eq!(it, 40..=41);
2232     assert_eq!(it.try_rfold(0, i8::checked_add), Some(81));
2233     assert!(it.is_empty());
2234     assert_eq!(it.try_rfold(0, i8::checked_add), Some(0));
2235     assert!(it.is_empty());
2236
2237     let mut it = 10..=20;
2238     assert_eq!(it.try_fold(0, |a, b| Some(a + b)), Some(165));
2239     assert!(it.is_empty());
2240     assert_eq!(it.try_fold(0, |a, b| Some(a + b)), Some(0));
2241     assert!(it.is_empty());
2242
2243     let mut it = 10..=20;
2244     assert_eq!(it.try_rfold(0, |a, b| Some(a + b)), Some(165));
2245     assert!(it.is_empty());
2246     assert_eq!(it.try_rfold(0, |a, b| Some(a + b)), Some(0));
2247     assert!(it.is_empty());
2248 }
2249
2250 #[test]
2251 fn test_range_size_hint() {
2252     use core::usize::MAX as UMAX;
2253     assert_eq!((0..0usize).size_hint(), (0, Some(0)));
2254     assert_eq!((0..100usize).size_hint(), (100, Some(100)));
2255     assert_eq!((0..UMAX).size_hint(), (UMAX, Some(UMAX)));
2256
2257     let umax = u128::try_from(UMAX).unwrap();
2258     assert_eq!((0..0u128).size_hint(), (0, Some(0)));
2259     assert_eq!((0..100u128).size_hint(), (100, Some(100)));
2260     assert_eq!((0..umax).size_hint(), (UMAX, Some(UMAX)));
2261     assert_eq!((0..umax + 1).size_hint(), (UMAX, None));
2262
2263     use core::isize::{MAX as IMAX, MIN as IMIN};
2264     assert_eq!((0..0isize).size_hint(), (0, Some(0)));
2265     assert_eq!((-100..100isize).size_hint(), (200, Some(200)));
2266     assert_eq!((IMIN..IMAX).size_hint(), (UMAX, Some(UMAX)));
2267
2268     let imin = i128::try_from(IMIN).unwrap();
2269     let imax = i128::try_from(IMAX).unwrap();
2270     assert_eq!((0..0i128).size_hint(), (0, Some(0)));
2271     assert_eq!((-100..100i128).size_hint(), (200, Some(200)));
2272     assert_eq!((imin..imax).size_hint(), (UMAX, Some(UMAX)));
2273     assert_eq!((imin..imax + 1).size_hint(), (UMAX, None));
2274 }
2275
2276 #[test]
2277 fn test_range_inclusive_size_hint() {
2278     use core::usize::MAX as UMAX;
2279     assert_eq!((1..=0usize).size_hint(), (0, Some(0)));
2280     assert_eq!((0..=0usize).size_hint(), (1, Some(1)));
2281     assert_eq!((0..=100usize).size_hint(), (101, Some(101)));
2282     assert_eq!((0..=UMAX - 1).size_hint(), (UMAX, Some(UMAX)));
2283     assert_eq!((0..=UMAX).size_hint(), (UMAX, None));
2284
2285     let umax = u128::try_from(UMAX).unwrap();
2286     assert_eq!((1..=0u128).size_hint(), (0, Some(0)));
2287     assert_eq!((0..=0u128).size_hint(), (1, Some(1)));
2288     assert_eq!((0..=100u128).size_hint(), (101, Some(101)));
2289     assert_eq!((0..=umax - 1).size_hint(), (UMAX, Some(UMAX)));
2290     assert_eq!((0..=umax).size_hint(), (UMAX, None));
2291     assert_eq!((0..=umax + 1).size_hint(), (UMAX, None));
2292
2293     use core::isize::{MAX as IMAX, MIN as IMIN};
2294     assert_eq!((0..=-1isize).size_hint(), (0, Some(0)));
2295     assert_eq!((0..=0isize).size_hint(), (1, Some(1)));
2296     assert_eq!((-100..=100isize).size_hint(), (201, Some(201)));
2297     assert_eq!((IMIN..=IMAX - 1).size_hint(), (UMAX, Some(UMAX)));
2298     assert_eq!((IMIN..=IMAX).size_hint(), (UMAX, None));
2299
2300     let imin = i128::try_from(IMIN).unwrap();
2301     let imax = i128::try_from(IMAX).unwrap();
2302     assert_eq!((0..=-1i128).size_hint(), (0, Some(0)));
2303     assert_eq!((0..=0i128).size_hint(), (1, Some(1)));
2304     assert_eq!((-100..=100i128).size_hint(), (201, Some(201)));
2305     assert_eq!((imin..=imax - 1).size_hint(), (UMAX, Some(UMAX)));
2306     assert_eq!((imin..=imax).size_hint(), (UMAX, None));
2307     assert_eq!((imin..=imax + 1).size_hint(), (UMAX, None));
2308 }
2309
2310 #[test]
2311 fn test_repeat() {
2312     let mut it = repeat(42);
2313     assert_eq!(it.next(), Some(42));
2314     assert_eq!(it.next(), Some(42));
2315     assert_eq!(it.next(), Some(42));
2316     assert_eq!(repeat(42).size_hint(), (usize::MAX, None));
2317 }
2318
2319 #[test]
2320 fn test_repeat_take() {
2321     let mut it = repeat(42).take(3);
2322     assert_eq!(it.next(), Some(42));
2323     assert_eq!(it.next(), Some(42));
2324     assert_eq!(it.next(), Some(42));
2325     assert_eq!(it.next(), None);
2326     is_trusted_len(repeat(42).take(3));
2327     assert_eq!(repeat(42).take(3).size_hint(), (3, Some(3)));
2328     assert_eq!(repeat(42).take(0).size_hint(), (0, Some(0)));
2329     assert_eq!(repeat(42).take(usize::MAX).size_hint(), (usize::MAX, Some(usize::MAX)));
2330 }
2331
2332 #[test]
2333 fn test_repeat_take_collect() {
2334     let v: Vec<_> = repeat(42).take(3).collect();
2335     assert_eq!(v, vec![42, 42, 42]);
2336 }
2337
2338 #[test]
2339 fn test_repeat_with() {
2340     #[derive(PartialEq, Debug)]
2341     struct NotClone(usize);
2342     let mut it = repeat_with(|| NotClone(42));
2343     assert_eq!(it.next(), Some(NotClone(42)));
2344     assert_eq!(it.next(), Some(NotClone(42)));
2345     assert_eq!(it.next(), Some(NotClone(42)));
2346     assert_eq!(repeat_with(|| NotClone(42)).size_hint(), (usize::MAX, None));
2347 }
2348
2349 #[test]
2350 fn test_repeat_with_take() {
2351     let mut it = repeat_with(|| 42).take(3);
2352     assert_eq!(it.next(), Some(42));
2353     assert_eq!(it.next(), Some(42));
2354     assert_eq!(it.next(), Some(42));
2355     assert_eq!(it.next(), None);
2356     is_trusted_len(repeat_with(|| 42).take(3));
2357     assert_eq!(repeat_with(|| 42).take(3).size_hint(), (3, Some(3)));
2358     assert_eq!(repeat_with(|| 42).take(0).size_hint(), (0, Some(0)));
2359     assert_eq!(repeat_with(|| 42).take(usize::MAX).size_hint(), (usize::MAX, Some(usize::MAX)));
2360 }
2361
2362 #[test]
2363 fn test_repeat_with_take_collect() {
2364     let mut curr = 1;
2365     let v: Vec<_> = repeat_with(|| {
2366         let tmp = curr;
2367         curr *= 2;
2368         tmp
2369     })
2370     .take(5)
2371     .collect();
2372     assert_eq!(v, vec![1, 2, 4, 8, 16]);
2373 }
2374
2375 #[test]
2376 fn test_successors() {
2377     let mut powers_of_10 = successors(Some(1_u16), |n| n.checked_mul(10));
2378     assert_eq!(powers_of_10.by_ref().collect::<Vec<_>>(), &[1, 10, 100, 1_000, 10_000]);
2379     assert_eq!(powers_of_10.next(), None);
2380
2381     let mut empty = successors(None::<u32>, |_| unimplemented!());
2382     assert_eq!(empty.next(), None);
2383     assert_eq!(empty.next(), None);
2384 }
2385
2386 #[test]
2387 fn test_fuse() {
2388     let mut it = 0..3;
2389     assert_eq!(it.len(), 3);
2390     assert_eq!(it.next(), Some(0));
2391     assert_eq!(it.len(), 2);
2392     assert_eq!(it.next(), Some(1));
2393     assert_eq!(it.len(), 1);
2394     assert_eq!(it.next(), Some(2));
2395     assert_eq!(it.len(), 0);
2396     assert_eq!(it.next(), None);
2397     assert_eq!(it.len(), 0);
2398     assert_eq!(it.next(), None);
2399     assert_eq!(it.len(), 0);
2400     assert_eq!(it.next(), None);
2401     assert_eq!(it.len(), 0);
2402 }
2403
2404 #[test]
2405 fn test_fuse_nth() {
2406     let xs = [0, 1, 2];
2407     let mut it = xs.iter();
2408
2409     assert_eq!(it.len(), 3);
2410     assert_eq!(it.nth(2), Some(&2));
2411     assert_eq!(it.len(), 0);
2412     assert_eq!(it.nth(2), None);
2413     assert_eq!(it.len(), 0);
2414 }
2415
2416 #[test]
2417 fn test_fuse_last() {
2418     let xs = [0, 1, 2];
2419     let it = xs.iter();
2420
2421     assert_eq!(it.len(), 3);
2422     assert_eq!(it.last(), Some(&2));
2423 }
2424
2425 #[test]
2426 fn test_fuse_count() {
2427     let xs = [0, 1, 2];
2428     let it = xs.iter();
2429
2430     assert_eq!(it.len(), 3);
2431     assert_eq!(it.count(), 3);
2432     // Can't check len now because count consumes.
2433 }
2434
2435 #[test]
2436 fn test_fuse_fold() {
2437     let xs = [0, 1, 2];
2438     let it = xs.iter(); // `FusedIterator`
2439     let i = it.fuse().fold(0, |i, &x| {
2440         assert_eq!(x, xs[i]);
2441         i + 1
2442     });
2443     assert_eq!(i, xs.len());
2444
2445     let it = xs.iter(); // `FusedIterator`
2446     let i = it.fuse().rfold(xs.len(), |i, &x| {
2447         assert_eq!(x, xs[i - 1]);
2448         i - 1
2449     });
2450     assert_eq!(i, 0);
2451
2452     let it = xs.iter().scan((), |_, &x| Some(x)); // `!FusedIterator`
2453     let i = it.fuse().fold(0, |i, x| {
2454         assert_eq!(x, xs[i]);
2455         i + 1
2456     });
2457     assert_eq!(i, xs.len());
2458 }
2459
2460 #[test]
2461 fn test_once() {
2462     let mut it = once(42);
2463     assert_eq!(it.next(), Some(42));
2464     assert_eq!(it.next(), None);
2465 }
2466
2467 #[test]
2468 fn test_once_with() {
2469     let count = Cell::new(0);
2470     let mut it = once_with(|| {
2471         count.set(count.get() + 1);
2472         42
2473     });
2474
2475     assert_eq!(count.get(), 0);
2476     assert_eq!(it.next(), Some(42));
2477     assert_eq!(count.get(), 1);
2478     assert_eq!(it.next(), None);
2479     assert_eq!(count.get(), 1);
2480     assert_eq!(it.next(), None);
2481     assert_eq!(count.get(), 1);
2482 }
2483
2484 #[test]
2485 fn test_empty() {
2486     let mut it = empty::<i32>();
2487     assert_eq!(it.next(), None);
2488 }
2489
2490 #[test]
2491 fn test_chain_fold() {
2492     let xs = [1, 2, 3];
2493     let ys = [1, 2, 0];
2494
2495     let mut iter = xs.iter().chain(&ys);
2496     iter.next();
2497     let mut result = Vec::new();
2498     iter.fold((), |(), &elt| result.push(elt));
2499     assert_eq!(&[2, 3, 1, 2, 0], &result[..]);
2500 }
2501
2502 #[test]
2503 fn test_step_replace_unsigned() {
2504     let mut x = 4u32;
2505     let y = x.replace_zero();
2506     assert_eq!(x, 0);
2507     assert_eq!(y, 4);
2508
2509     x = 5;
2510     let y = x.replace_one();
2511     assert_eq!(x, 1);
2512     assert_eq!(y, 5);
2513 }
2514
2515 #[test]
2516 fn test_step_replace_signed() {
2517     let mut x = 4i32;
2518     let y = x.replace_zero();
2519     assert_eq!(x, 0);
2520     assert_eq!(y, 4);
2521
2522     x = 5;
2523     let y = x.replace_one();
2524     assert_eq!(x, 1);
2525     assert_eq!(y, 5);
2526 }
2527
2528 #[test]
2529 fn test_step_replace_no_between() {
2530     let mut x = 4u128;
2531     let y = x.replace_zero();
2532     assert_eq!(x, 0);
2533     assert_eq!(y, 4);
2534
2535     x = 5;
2536     let y = x.replace_one();
2537     assert_eq!(x, 1);
2538     assert_eq!(y, 5);
2539 }
2540
2541 #[test]
2542 fn test_rev_try_folds() {
2543     let f = &|acc, x| i32::checked_add(2 * acc, x);
2544     assert_eq!((1..10).rev().try_fold(7, f), (1..10).try_rfold(7, f));
2545     assert_eq!((1..10).rev().try_rfold(7, f), (1..10).try_fold(7, f));
2546
2547     let a = [10, 20, 30, 40, 100, 60, 70, 80, 90];
2548     let mut iter = a.iter().rev();
2549     assert_eq!(iter.try_fold(0_i8, |acc, &x| acc.checked_add(x)), None);
2550     assert_eq!(iter.next(), Some(&70));
2551     let mut iter = a.iter().rev();
2552     assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None);
2553     assert_eq!(iter.next_back(), Some(&60));
2554 }
2555
2556 #[test]
2557 fn test_cloned_try_folds() {
2558     let a = [1, 2, 3, 4, 5, 6, 7, 8, 9];
2559     let f = &|acc, x| i32::checked_add(2 * acc, x);
2560     let f_ref = &|acc, &x| i32::checked_add(2 * acc, x);
2561     assert_eq!(a.iter().cloned().try_fold(7, f), a.iter().try_fold(7, f_ref));
2562     assert_eq!(a.iter().cloned().try_rfold(7, f), a.iter().try_rfold(7, f_ref));
2563
2564     let a = [10, 20, 30, 40, 100, 60, 70, 80, 90];
2565     let mut iter = a.iter().cloned();
2566     assert_eq!(iter.try_fold(0_i8, |acc, x| acc.checked_add(x)), None);
2567     assert_eq!(iter.next(), Some(60));
2568     let mut iter = a.iter().cloned();
2569     assert_eq!(iter.try_rfold(0_i8, |acc, x| acc.checked_add(x)), None);
2570     assert_eq!(iter.next_back(), Some(70));
2571 }
2572
2573 #[test]
2574 fn test_chain_try_folds() {
2575     let c = || (0..10).chain(10..20);
2576
2577     let f = &|acc, x| i32::checked_add(2 * acc, x);
2578     assert_eq!(c().try_fold(7, f), (0..20).try_fold(7, f));
2579     assert_eq!(c().try_rfold(7, f), (0..20).rev().try_fold(7, f));
2580
2581     let mut iter = c();
2582     assert_eq!(iter.position(|x| x == 5), Some(5));
2583     assert_eq!(iter.next(), Some(6), "stopped in front, state Both");
2584     assert_eq!(iter.position(|x| x == 13), Some(6));
2585     assert_eq!(iter.next(), Some(14), "stopped in back, state Back");
2586     assert_eq!(iter.try_fold(0, |acc, x| Some(acc + x)), Some((15..20).sum()));
2587
2588     let mut iter = c().rev(); // use rev to access try_rfold
2589     assert_eq!(iter.position(|x| x == 15), Some(4));
2590     assert_eq!(iter.next(), Some(14), "stopped in back, state Both");
2591     assert_eq!(iter.position(|x| x == 5), Some(8));
2592     assert_eq!(iter.next(), Some(4), "stopped in front, state Front");
2593     assert_eq!(iter.try_fold(0, |acc, x| Some(acc + x)), Some((0..4).sum()));
2594
2595     let mut iter = c();
2596     iter.by_ref().rev().nth(14); // skip the last 15, ending in state Front
2597     assert_eq!(iter.try_fold(7, f), (0..5).try_fold(7, f));
2598
2599     let mut iter = c();
2600     iter.nth(14); // skip the first 15, ending in state Back
2601     assert_eq!(iter.try_rfold(7, f), (15..20).try_rfold(7, f));
2602 }
2603
2604 #[test]
2605 fn test_map_try_folds() {
2606     let f = &|acc, x| i32::checked_add(2 * acc, x);
2607     assert_eq!((0..10).map(|x| x + 3).try_fold(7, f), (3..13).try_fold(7, f));
2608     assert_eq!((0..10).map(|x| x + 3).try_rfold(7, f), (3..13).try_rfold(7, f));
2609
2610     let mut iter = (0..40).map(|x| x + 10);
2611     assert_eq!(iter.try_fold(0, i8::checked_add), None);
2612     assert_eq!(iter.next(), Some(20));
2613     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
2614     assert_eq!(iter.next_back(), Some(46));
2615 }
2616
2617 #[test]
2618 fn test_filter_try_folds() {
2619     fn p(&x: &i32) -> bool {
2620         0 <= x && x < 10
2621     }
2622     let f = &|acc, x| i32::checked_add(2 * acc, x);
2623     assert_eq!((-10..20).filter(p).try_fold(7, f), (0..10).try_fold(7, f));
2624     assert_eq!((-10..20).filter(p).try_rfold(7, f), (0..10).try_rfold(7, f));
2625
2626     let mut iter = (0..40).filter(|&x| x % 2 == 1);
2627     assert_eq!(iter.try_fold(0, i8::checked_add), None);
2628     assert_eq!(iter.next(), Some(25));
2629     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
2630     assert_eq!(iter.next_back(), Some(31));
2631 }
2632
2633 #[test]
2634 fn test_filter_map_try_folds() {
2635     let mp = &|x| if 0 <= x && x < 10 { Some(x * 2) } else { None };
2636     let f = &|acc, x| i32::checked_add(2 * acc, x);
2637     assert_eq!((-9..20).filter_map(mp).try_fold(7, f), (0..10).map(|x| 2 * x).try_fold(7, f));
2638     assert_eq!((-9..20).filter_map(mp).try_rfold(7, f), (0..10).map(|x| 2 * x).try_rfold(7, f));
2639
2640     let mut iter = (0..40).filter_map(|x| if x % 2 == 1 { None } else { Some(x * 2 + 10) });
2641     assert_eq!(iter.try_fold(0, i8::checked_add), None);
2642     assert_eq!(iter.next(), Some(38));
2643     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
2644     assert_eq!(iter.next_back(), Some(78));
2645 }
2646
2647 #[test]
2648 fn test_enumerate_try_folds() {
2649     let f = &|acc, (i, x)| usize::checked_add(2 * acc, x / (i + 1) + i);
2650     assert_eq!((9..18).enumerate().try_fold(7, f), (0..9).map(|i| (i, i + 9)).try_fold(7, f));
2651     assert_eq!((9..18).enumerate().try_rfold(7, f), (0..9).map(|i| (i, i + 9)).try_rfold(7, f));
2652
2653     let mut iter = (100..200).enumerate();
2654     let f = &|acc, (i, x)| u8::checked_add(acc, u8::checked_div(x, i as u8 + 1)?);
2655     assert_eq!(iter.try_fold(0, f), None);
2656     assert_eq!(iter.next(), Some((7, 107)));
2657     assert_eq!(iter.try_rfold(0, f), None);
2658     assert_eq!(iter.next_back(), Some((11, 111)));
2659 }
2660
2661 #[test]
2662 fn test_peek_try_folds() {
2663     let f = &|acc, x| i32::checked_add(2 * acc, x);
2664
2665     assert_eq!((1..20).peekable().try_fold(7, f), (1..20).try_fold(7, f));
2666     assert_eq!((1..20).peekable().try_rfold(7, f), (1..20).try_rfold(7, f));
2667
2668     let mut iter = (1..20).peekable();
2669     assert_eq!(iter.peek(), Some(&1));
2670     assert_eq!(iter.try_fold(7, f), (1..20).try_fold(7, f));
2671
2672     let mut iter = (1..20).peekable();
2673     assert_eq!(iter.peek(), Some(&1));
2674     assert_eq!(iter.try_rfold(7, f), (1..20).try_rfold(7, f));
2675
2676     let mut iter = [100, 20, 30, 40, 50, 60, 70].iter().cloned().peekable();
2677     assert_eq!(iter.peek(), Some(&100));
2678     assert_eq!(iter.try_fold(0, i8::checked_add), None);
2679     assert_eq!(iter.peek(), Some(&40));
2680
2681     let mut iter = [100, 20, 30, 40, 50, 60, 70].iter().cloned().peekable();
2682     assert_eq!(iter.peek(), Some(&100));
2683     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
2684     assert_eq!(iter.peek(), Some(&100));
2685     assert_eq!(iter.next_back(), Some(50));
2686
2687     let mut iter = (2..5).peekable();
2688     assert_eq!(iter.peek(), Some(&2));
2689     assert_eq!(iter.try_for_each(Err), Err(2));
2690     assert_eq!(iter.peek(), Some(&3));
2691     assert_eq!(iter.try_for_each(Err), Err(3));
2692     assert_eq!(iter.peek(), Some(&4));
2693     assert_eq!(iter.try_for_each(Err), Err(4));
2694     assert_eq!(iter.peek(), None);
2695     assert_eq!(iter.try_for_each(Err), Ok(()));
2696
2697     let mut iter = (2..5).peekable();
2698     assert_eq!(iter.peek(), Some(&2));
2699     assert_eq!(iter.try_rfold((), |(), x| Err(x)), Err(4));
2700     assert_eq!(iter.peek(), Some(&2));
2701     assert_eq!(iter.try_rfold((), |(), x| Err(x)), Err(3));
2702     assert_eq!(iter.peek(), Some(&2));
2703     assert_eq!(iter.try_rfold((), |(), x| Err(x)), Err(2));
2704     assert_eq!(iter.peek(), None);
2705     assert_eq!(iter.try_rfold((), |(), x| Err(x)), Ok(()));
2706 }
2707
2708 #[test]
2709 fn test_skip_while_try_fold() {
2710     let f = &|acc, x| i32::checked_add(2 * acc, x);
2711     fn p(&x: &i32) -> bool {
2712         (x % 10) <= 5
2713     }
2714     assert_eq!((1..20).skip_while(p).try_fold(7, f), (6..20).try_fold(7, f));
2715     let mut iter = (1..20).skip_while(p);
2716     assert_eq!(iter.nth(5), Some(11));
2717     assert_eq!(iter.try_fold(7, f), (12..20).try_fold(7, f));
2718
2719     let mut iter = (0..50).skip_while(|&x| (x % 20) < 15);
2720     assert_eq!(iter.try_fold(0, i8::checked_add), None);
2721     assert_eq!(iter.next(), Some(23));
2722 }
2723
2724 #[test]
2725 fn test_take_while_folds() {
2726     let f = &|acc, x| i32::checked_add(2 * acc, x);
2727     assert_eq!((1..20).take_while(|&x| x != 10).try_fold(7, f), (1..10).try_fold(7, f));
2728     let mut iter = (1..20).take_while(|&x| x != 10);
2729     assert_eq!(iter.try_fold(0, |x, y| Some(x + y)), Some((1..10).sum()));
2730     assert_eq!(iter.next(), None, "flag should be set");
2731     let iter = (1..20).take_while(|&x| x != 10);
2732     assert_eq!(iter.fold(0, |x, y| x + y), (1..10).sum());
2733
2734     let mut iter = (10..50).take_while(|&x| x != 40);
2735     assert_eq!(iter.try_fold(0, i8::checked_add), None);
2736     assert_eq!(iter.next(), Some(20));
2737 }
2738
2739 #[test]
2740 fn test_skip_try_folds() {
2741     let f = &|acc, x| i32::checked_add(2 * acc, x);
2742     assert_eq!((1..20).skip(9).try_fold(7, f), (10..20).try_fold(7, f));
2743     assert_eq!((1..20).skip(9).try_rfold(7, f), (10..20).try_rfold(7, f));
2744
2745     let mut iter = (0..30).skip(10);
2746     assert_eq!(iter.try_fold(0, i8::checked_add), None);
2747     assert_eq!(iter.next(), Some(20));
2748     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
2749     assert_eq!(iter.next_back(), Some(24));
2750 }
2751
2752 #[test]
2753 fn test_skip_nth_back() {
2754     let xs = [0, 1, 2, 3, 4, 5];
2755     let mut it = xs.iter().skip(2);
2756     assert_eq!(it.nth_back(0), Some(&5));
2757     assert_eq!(it.nth_back(1), Some(&3));
2758     assert_eq!(it.nth_back(0), Some(&2));
2759     assert_eq!(it.nth_back(0), None);
2760
2761     let ys = [2, 3, 4, 5];
2762     let mut ity = ys.iter();
2763     let mut it = xs.iter().skip(2);
2764     assert_eq!(it.nth_back(1), ity.nth_back(1));
2765     assert_eq!(it.clone().nth(0), ity.clone().nth(0));
2766     assert_eq!(it.nth_back(0), ity.nth_back(0));
2767     assert_eq!(it.clone().nth(0), ity.clone().nth(0));
2768     assert_eq!(it.nth_back(0), ity.nth_back(0));
2769     assert_eq!(it.clone().nth(0), ity.clone().nth(0));
2770     assert_eq!(it.nth_back(0), ity.nth_back(0));
2771     assert_eq!(it.clone().nth(0), ity.clone().nth(0));
2772
2773     let mut it = xs.iter().skip(2);
2774     assert_eq!(it.nth_back(4), None);
2775     assert_eq!(it.nth_back(0), None);
2776
2777     let mut it = xs.iter();
2778     it.by_ref().skip(2).nth_back(3);
2779     assert_eq!(it.next_back(), Some(&1));
2780
2781     let mut it = xs.iter();
2782     it.by_ref().skip(2).nth_back(10);
2783     assert_eq!(it.next_back(), Some(&1));
2784 }
2785
2786 #[test]
2787 fn test_take_try_folds() {
2788     let f = &|acc, x| i32::checked_add(2 * acc, x);
2789     assert_eq!((10..30).take(10).try_fold(7, f), (10..20).try_fold(7, f));
2790     assert_eq!((10..30).take(10).try_rfold(7, f), (10..20).try_rfold(7, f));
2791
2792     let mut iter = (10..30).take(20);
2793     assert_eq!(iter.try_fold(0, i8::checked_add), None);
2794     assert_eq!(iter.next(), Some(20));
2795     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
2796     assert_eq!(iter.next_back(), Some(24));
2797
2798     let mut iter = (2..20).take(3);
2799     assert_eq!(iter.try_for_each(Err), Err(2));
2800     assert_eq!(iter.try_for_each(Err), Err(3));
2801     assert_eq!(iter.try_for_each(Err), Err(4));
2802     assert_eq!(iter.try_for_each(Err), Ok(()));
2803
2804     let mut iter = (2..20).take(3).rev();
2805     assert_eq!(iter.try_for_each(Err), Err(4));
2806     assert_eq!(iter.try_for_each(Err), Err(3));
2807     assert_eq!(iter.try_for_each(Err), Err(2));
2808     assert_eq!(iter.try_for_each(Err), Ok(()));
2809 }
2810
2811 #[test]
2812 fn test_flat_map_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).flat_map(mr).try_fold(7, f), (0..50).try_fold(7, f));
2816     assert_eq!((0..10).flat_map(mr).try_rfold(7, f), (0..50).try_rfold(7, f));
2817     let mut iter = (0..10).flat_map(mr);
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).flat_map(|x| (4 * x)..(4 * x + 4));
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_flatten_try_folds() {
2831     let f = &|acc, x| i32::checked_add(acc * 2 / 3, x);
2832     let mr = &|x| (5 * x)..(5 * x + 5);
2833     assert_eq!((0..10).map(mr).flatten().try_fold(7, f), (0..50).try_fold(7, f));
2834     assert_eq!((0..10).map(mr).flatten().try_rfold(7, f), (0..50).try_rfold(7, f));
2835     let mut iter = (0..10).map(mr).flatten();
2836     iter.next();
2837     iter.next_back(); // have front and back iters in progress
2838     assert_eq!(iter.try_rfold(7, f), (1..49).try_rfold(7, f));
2839
2840     let mut iter = (0..10).map(|x| (4 * x)..(4 * x + 4)).flatten();
2841     assert_eq!(iter.try_fold(0, i8::checked_add), None);
2842     assert_eq!(iter.next(), Some(17));
2843     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
2844     assert_eq!(iter.next_back(), Some(35));
2845 }
2846
2847 #[test]
2848 fn test_functor_laws() {
2849     // identity:
2850     fn identity<T>(x: T) -> T {
2851         x
2852     }
2853     assert_eq!((0..10).map(identity).sum::<usize>(), (0..10).sum());
2854
2855     // composition:
2856     fn f(x: usize) -> usize {
2857         x + 3
2858     }
2859     fn g(x: usize) -> usize {
2860         x * 2
2861     }
2862     fn h(x: usize) -> usize {
2863         g(f(x))
2864     }
2865     assert_eq!((0..10).map(f).map(g).sum::<usize>(), (0..10).map(h).sum());
2866 }
2867
2868 #[test]
2869 fn test_monad_laws_left_identity() {
2870     fn f(x: usize) -> impl Iterator<Item = usize> {
2871         (0..10).map(move |y| x * y)
2872     }
2873     assert_eq!(once(42).flat_map(f.clone()).sum::<usize>(), f(42).sum());
2874 }
2875
2876 #[test]
2877 fn test_monad_laws_right_identity() {
2878     assert_eq!((0..10).flat_map(|x| once(x)).sum::<usize>(), (0..10).sum());
2879 }
2880
2881 #[test]
2882 fn test_monad_laws_associativity() {
2883     fn f(x: usize) -> impl Iterator<Item = usize> {
2884         0..x
2885     }
2886     fn g(x: usize) -> impl Iterator<Item = usize> {
2887         (0..x).rev()
2888     }
2889     assert_eq!(
2890         (0..10).flat_map(f).flat_map(g).sum::<usize>(),
2891         (0..10).flat_map(|x| f(x).flat_map(g)).sum::<usize>()
2892     );
2893 }
2894
2895 #[test]
2896 fn test_is_sorted() {
2897     assert!([1, 2, 2, 9].iter().is_sorted());
2898     assert!(![1, 3, 2].iter().is_sorted());
2899     assert!([0].iter().is_sorted());
2900     assert!(std::iter::empty::<i32>().is_sorted());
2901     assert!(![0.0, 1.0, std::f32::NAN].iter().is_sorted());
2902     assert!([-2, -1, 0, 3].iter().is_sorted());
2903     assert!(![-2i32, -1, 0, 3].iter().is_sorted_by_key(|n| n.abs()));
2904     assert!(!["c", "bb", "aaa"].iter().is_sorted());
2905     assert!(["c", "bb", "aaa"].iter().is_sorted_by_key(|s| s.len()));
2906 }
2907
2908 #[test]
2909 fn test_partition() {
2910     fn check(xs: &mut [i32], ref p: impl Fn(&i32) -> bool, expected: usize) {
2911         let i = xs.iter_mut().partition_in_place(p);
2912         assert_eq!(expected, i);
2913         assert!(xs[..i].iter().all(p));
2914         assert!(!xs[i..].iter().any(p));
2915         assert!(xs.iter().is_partitioned(p));
2916         if i == 0 || i == xs.len() {
2917             assert!(xs.iter().rev().is_partitioned(p));
2918         } else {
2919             assert!(!xs.iter().rev().is_partitioned(p));
2920         }
2921     }
2922
2923     check(&mut [], |_| true, 0);
2924     check(&mut [], |_| false, 0);
2925
2926     check(&mut [0], |_| true, 1);
2927     check(&mut [0], |_| false, 0);
2928
2929     check(&mut [-1, 1], |&x| x > 0, 1);
2930     check(&mut [-1, 1], |&x| x < 0, 1);
2931
2932     let ref mut xs = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
2933     check(xs, |_| true, 10);
2934     check(xs, |_| false, 0);
2935     check(xs, |&x| x % 2 == 0, 5); // evens
2936     check(xs, |&x| x % 2 == 1, 5); // odds
2937     check(xs, |&x| x % 3 == 0, 4); // multiple of 3
2938     check(xs, |&x| x % 4 == 0, 3); // multiple of 4
2939     check(xs, |&x| x % 5 == 0, 2); // multiple of 5
2940     check(xs, |&x| x < 3, 3); // small
2941     check(xs, |&x| x > 6, 3); // large
2942 }