src/libcore/tests/iter.rs

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