src/libcoretest/iter.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use core::iter::*;
  12 use core::iter::order::*;
  13 use core::iter::MinMaxResult::*;
  14 use core::num::SignedInt;
  15 use core::uint;
  16 use core::cmp;
  17
  18 use test::Bencher;
  19
  20 #[test]
  21 fn test_lt() {
  22     let empty: [int; 0] = [];
  23     let xs = [1i,2,3];
  24     let ys = [1i,2,0];
  25
  26     assert!(!lt(xs.iter(), ys.iter()));
  27     assert!(!le(xs.iter(), ys.iter()));
  28     assert!( gt(xs.iter(), ys.iter()));
  29     assert!( ge(xs.iter(), ys.iter()));
  30
  31     assert!( lt(ys.iter(), xs.iter()));
  32     assert!( le(ys.iter(), xs.iter()));
  33     assert!(!gt(ys.iter(), xs.iter()));
  34     assert!(!ge(ys.iter(), xs.iter()));
  35
  36     assert!( lt(empty.iter(), xs.iter()));
  37     assert!( le(empty.iter(), xs.iter()));
  38     assert!(!gt(empty.iter(), xs.iter()));
  39     assert!(!ge(empty.iter(), xs.iter()));
  40
  41     // Sequence with NaN
  42     let u = [1.0f64, 2.0];
  43     let v = [0.0f64/0.0, 3.0];
  44
  45     assert!(!lt(u.iter(), v.iter()));
  46     assert!(!le(u.iter(), v.iter()));
  47     assert!(!gt(u.iter(), v.iter()));
  48     assert!(!ge(u.iter(), v.iter()));
  49
  50     let a = [0.0f64/0.0];
  51     let b = [1.0f64];
  52     let c = [2.0f64];
  53
  54     assert!(lt(a.iter(), b.iter()) == (a[0] <  b[0]));
  55     assert!(le(a.iter(), b.iter()) == (a[0] <= b[0]));
  56     assert!(gt(a.iter(), b.iter()) == (a[0] >  b[0]));
  57     assert!(ge(a.iter(), b.iter()) == (a[0] >= b[0]));
  58
  59     assert!(lt(c.iter(), b.iter()) == (c[0] <  b[0]));
  60     assert!(le(c.iter(), b.iter()) == (c[0] <= b[0]));
  61     assert!(gt(c.iter(), b.iter()) == (c[0] >  b[0]));
  62     assert!(ge(c.iter(), b.iter()) == (c[0] >= b[0]));
  63 }
  64
  65 #[test]
  66 fn test_multi_iter() {
  67     let xs = [1i,2,3,4];
  68     let ys = [4i,3,2,1];
  69     assert!(eq(xs.iter(), ys.iter().rev()));
  70     assert!(lt(xs.iter(), xs.iter().skip(2)));
  71 }
  72
  73 #[test]
  74 fn test_counter_from_iter() {
  75     let it = count(0i, 5).take(10);
  76     let xs: Vec<int> = FromIterator::from_iter(it);
  77     assert!(xs == vec![0, 5, 10, 15, 20, 25, 30, 35, 40, 45]);
  78 }
  79
  80 #[test]
  81 fn test_iterator_chain() {
  82     let xs = [0u, 1, 2, 3, 4, 5];
  83     let ys = [30u, 40, 50, 60];
  84     let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
  85     let mut it = xs.iter().chain(ys.iter());
  86     let mut i = 0;
  87     for &x in it {
  88         assert_eq!(x, expected[i]);
  89         i += 1;
  90     }
  91     assert_eq!(i, expected.len());
  92
  93     let ys = count(30u, 10).take(4);
  94     let mut it = xs.iter().map(|&x| x).chain(ys);
  95     let mut i = 0;
  96     for x in it {
  97         assert_eq!(x, expected[i]);
  98         i += 1;
  99     }
 100     assert_eq!(i, expected.len());
 101 }
 102
 103 #[test]
 104 fn test_filter_map() {
 105     let it = count(0u, 1u).take(10)
 106         .filter_map(|x| if x % 2 == 0 { Some(x*x) } else { None });
 107     assert!(it.collect::<Vec<uint>>() == vec![0*0, 2*2, 4*4, 6*6, 8*8]);
 108 }
 109
 110 #[test]
 111 fn test_iterator_enumerate() {
 112     let xs = [0u, 1, 2, 3, 4, 5];
 113     let mut it = xs.iter().enumerate();
 114     for (i, &x) in it {
 115         assert_eq!(i, x);
 116     }
 117 }
 118
 119 #[test]
 120 fn test_iterator_peekable() {
 121     let xs = vec![0u, 1, 2, 3, 4, 5];
 122     let mut it = xs.iter().map(|&x|x).peekable();
 123     assert_eq!(it.peek().unwrap(), &0);
 124     assert_eq!(it.next().unwrap(), 0);
 125     assert_eq!(it.next().unwrap(), 1);
 126     assert_eq!(it.next().unwrap(), 2);
 127     assert_eq!(it.peek().unwrap(), &3);
 128     assert_eq!(it.peek().unwrap(), &3);
 129     assert_eq!(it.next().unwrap(), 3);
 130     assert_eq!(it.next().unwrap(), 4);
 131     assert_eq!(it.peek().unwrap(), &5);
 132     assert_eq!(it.next().unwrap(), 5);
 133     assert!(it.peek().is_none());
 134     assert!(it.next().is_none());
 135 }
 136
 137 #[test]
 138 fn test_iterator_take_while() {
 139     let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
 140     let ys = [0u, 1, 2, 3, 5, 13];
 141     let mut it = xs.iter().take_while(|&x| *x < 15u);
 142     let mut i = 0;
 143     for x in it {
 144         assert_eq!(*x, ys[i]);
 145         i += 1;
 146     }
 147     assert_eq!(i, ys.len());
 148 }
 149
 150 #[test]
 151 fn test_iterator_skip_while() {
 152     let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
 153     let ys = [15, 16, 17, 19];
 154     let mut it = xs.iter().skip_while(|&x| *x < 15u);
 155     let mut i = 0;
 156     for x in it {
 157         assert_eq!(*x, ys[i]);
 158         i += 1;
 159     }
 160     assert_eq!(i, ys.len());
 161 }
 162
 163 #[test]
 164 fn test_iterator_skip() {
 165     let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
 166     let ys = [13, 15, 16, 17, 19, 20, 30];
 167     let mut it = xs.iter().skip(5);
 168     let mut i = 0;
 169     for &x in it {
 170         assert_eq!(x, ys[i]);
 171         i += 1;
 172     }
 173     assert_eq!(i, ys.len());
 174 }
 175
 176 #[test]
 177 fn test_iterator_take() {
 178     let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
 179     let ys = [0u, 1, 2, 3, 5];
 180     let mut it = xs.iter().take(5);
 181     let mut i = 0;
 182     for &x in it {
 183         assert_eq!(x, ys[i]);
 184         i += 1;
 185     }
 186     assert_eq!(i, ys.len());
 187 }
 188
 189 #[test]
 190 fn test_iterator_scan() {
 191     // test the type inference
 192     fn add(old: &mut int, new: &uint) -> Option<f64> {
 193         *old += *new as int;
 194         Some(*old as f64)
 195     }
 196     let xs = [0u, 1, 2, 3, 4];
 197     let ys = [0f64, 1.0, 3.0, 6.0, 10.0];
 198
 199     let mut it = xs.iter().scan(0, add);
 200     let mut i = 0;
 201     for x in it {
 202         assert_eq!(x, ys[i]);
 203         i += 1;
 204     }
 205     assert_eq!(i, ys.len());
 206 }
 207
 208 #[test]
 209 fn test_iterator_flat_map() {
 210     let xs = [0u, 3, 6];
 211     let ys = [0u, 1, 2, 3, 4, 5, 6, 7, 8];
 212     let mut it = xs.iter().flat_map(|&x| count(x, 1).take(3));
 213     let mut i = 0;
 214     for x in it {
 215         assert_eq!(x, ys[i]);
 216         i += 1;
 217     }
 218     assert_eq!(i, ys.len());
 219 }
 220
 221 #[test]
 222 fn test_inspect() {
 223     let xs = [1u, 2, 3, 4];
 224     let mut n = 0u;
 225
 226     let ys = xs.iter()
 227                .map(|&x| x)
 228                .inspect(|_| n += 1)
 229                .collect::<Vec<uint>>();
 230
 231     assert_eq!(n, xs.len());
 232     assert_eq!(&xs[], &ys[]);
 233 }
 234
 235 #[test]
 236 fn test_unfoldr() {
 237     fn count(st: &mut uint) -> Option<uint> {
 238         if *st < 10 {
 239             let ret = Some(*st);
 240             *st += 1;
 241             ret
 242         } else {
 243             None
 244         }
 245     }
 246
 247     let mut it = Unfold::new(0, count);
 248     let mut i = 0;
 249     for counted in it {
 250         assert_eq!(counted, i);
 251         i += 1;
 252     }
 253     assert_eq!(i, 10);
 254 }
 255
 256 #[test]
 257 fn test_cycle() {
 258     let cycle_len = 3;
 259     let it = count(0u, 1).take(cycle_len).cycle();
 260     assert_eq!(it.size_hint(), (uint::MAX, None));
 261     for (i, x) in it.take(100).enumerate() {
 262         assert_eq!(i % cycle_len, x);
 263     }
 264
 265     let mut it = count(0u, 1).take(0).cycle();
 266     assert_eq!(it.size_hint(), (0, Some(0)));
 267     assert_eq!(it.next(), None);
 268 }
 269
 270 #[test]
 271 fn test_iterator_nth() {
 272     let v: &[_] = &[0i, 1, 2, 3, 4];
 273     for i in range(0u, v.len()) {
 274         assert_eq!(v.iter().nth(i).unwrap(), &v[i]);
 275     }
 276     assert_eq!(v.iter().nth(v.len()), None);
 277 }
 278
 279 #[test]
 280 fn test_iterator_last() {
 281     let v: &[_] = &[0i, 1, 2, 3, 4];
 282     assert_eq!(v.iter().last().unwrap(), &4);
 283     assert_eq!(v[..1].iter().last().unwrap(), &0);
 284 }
 285
 286 #[test]
 287 fn test_iterator_len() {
 288     let v: &[_] = &[0i, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 289     assert_eq!(v[..4].iter().count(), 4);
 290     assert_eq!(v[..10].iter().count(), 10);
 291     assert_eq!(v[..0].iter().count(), 0);
 292 }
 293
 294 #[test]
 295 fn test_iterator_sum() {
 296     let v: &[_] = &[0i, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 297     assert_eq!(v[..4].iter().map(|&x| x).sum(), 6);
 298     assert_eq!(v.iter().map(|&x| x).sum(), 55);
 299     assert_eq!(v[..0].iter().map(|&x| x).sum(), 0);
 300 }
 301
 302 #[test]
 303 fn test_iterator_product() {
 304     let v: &[_] = &[0i, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 305     assert_eq!(v[..4].iter().map(|&x| x).product(), 0);
 306     assert_eq!(v[1..5].iter().map(|&x| x).product(), 24);
 307     assert_eq!(v[..0].iter().map(|&x| x).product(), 1);
 308 }
 309
 310 #[test]
 311 fn test_iterator_max() {
 312     let v: &[_] = &[0i, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 313     assert_eq!(v[..4].iter().map(|&x| x).max(), Some(3));
 314     assert_eq!(v.iter().map(|&x| x).max(), Some(10));
 315     assert_eq!(v[..0].iter().map(|&x| x).max(), None);
 316 }
 317
 318 #[test]
 319 fn test_iterator_min() {
 320     let v: &[_] = &[0i, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 321     assert_eq!(v[..4].iter().map(|&x| x).min(), Some(0));
 322     assert_eq!(v.iter().map(|&x| x).min(), Some(0));
 323     assert_eq!(v[..0].iter().map(|&x| x).min(), None);
 324 }
 325
 326 #[test]
 327 fn test_iterator_size_hint() {
 328     let c = count(0i, 1);
 329     let v: &[_] = &[0i, 1, 2, 3, 4, 5, 6, 7, 8, 9];
 330     let v2 = &[10i, 11, 12];
 331     let vi = v.iter();
 332
 333     assert_eq!(c.size_hint(), (uint::MAX, None));
 334     assert_eq!(vi.size_hint(), (10, Some(10)));
 335
 336     assert_eq!(c.take(5).size_hint(), (5, Some(5)));
 337     assert_eq!(c.skip(5).size_hint().1, None);
 338     assert_eq!(c.take_while(|_| false).size_hint(), (0, None));
 339     assert_eq!(c.skip_while(|_| false).size_hint(), (0, None));
 340     assert_eq!(c.enumerate().size_hint(), (uint::MAX, None));
 341     assert_eq!(c.chain(vi.map(|&i| i)).size_hint(), (uint::MAX, None));
 342     assert_eq!(c.zip(vi).size_hint(), (10, Some(10)));
 343     assert_eq!(c.scan(0i, |_,_| Some(0i)).size_hint(), (0, None));
 344     assert_eq!(c.filter(|_| false).size_hint(), (0, None));
 345     assert_eq!(c.map(|_| 0i).size_hint(), (uint::MAX, None));
 346     assert_eq!(c.filter_map(|_| Some(0i)).size_hint(), (0, None));
 347
 348     assert_eq!(vi.take(5).size_hint(), (5, Some(5)));
 349     assert_eq!(vi.take(12).size_hint(), (10, Some(10)));
 350     assert_eq!(vi.skip(3).size_hint(), (7, Some(7)));
 351     assert_eq!(vi.skip(12).size_hint(), (0, Some(0)));
 352     assert_eq!(vi.take_while(|_| false).size_hint(), (0, Some(10)));
 353     assert_eq!(vi.skip_while(|_| false).size_hint(), (0, Some(10)));
 354     assert_eq!(vi.enumerate().size_hint(), (10, Some(10)));
 355     assert_eq!(vi.chain(v2.iter()).size_hint(), (13, Some(13)));
 356     assert_eq!(vi.zip(v2.iter()).size_hint(), (3, Some(3)));
 357     assert_eq!(vi.scan(0i, |_,_| Some(0i)).size_hint(), (0, Some(10)));
 358     assert_eq!(vi.filter(|_| false).size_hint(), (0, Some(10)));
 359     assert_eq!(vi.map(|&i| i+1).size_hint(), (10, Some(10)));
 360     assert_eq!(vi.filter_map(|_| Some(0i)).size_hint(), (0, Some(10)));
 361 }
 362
 363 #[test]
 364 fn test_collect() {
 365     let a = vec![1i, 2, 3, 4, 5];
 366     let b: Vec<int> = a.iter().map(|&x| x).collect();
 367     assert!(a == b);
 368 }
 369
 370 #[test]
 371 fn test_all() {
 372     let v: Box<[int]> = box [1i, 2, 3, 4, 5];
 373     assert!(v.iter().all(|&x| x < 10));
 374     assert!(!v.iter().all(|&x| x % 2 == 0));
 375     assert!(!v.iter().all(|&x| x > 100));
 376     assert!(v[..0].iter().all(|_| panic!()));
 377 }
 378
 379 #[test]
 380 fn test_any() {
 381     let v: Box<[int]> = box [1i, 2, 3, 4, 5];
 382     assert!(v.iter().any(|&x| x < 10));
 383     assert!(v.iter().any(|&x| x % 2 == 0));
 384     assert!(!v.iter().any(|&x| x > 100));
 385     assert!(!v[..0].iter().any(|_| panic!()));
 386 }
 387
 388 #[test]
 389 fn test_find() {
 390     let v: &[int] = &[1i, 3, 9, 27, 103, 14, 11];
 391     assert_eq!(*v.iter().find(|&&x| x & 1 == 0).unwrap(), 14);
 392     assert_eq!(*v.iter().find(|&&x| x % 3 == 0).unwrap(), 3);
 393     assert!(v.iter().find(|&&x| x % 12 == 0).is_none());
 394 }
 395
 396 #[test]
 397 fn test_position() {
 398     let v = &[1i, 3, 9, 27, 103, 14, 11];
 399     assert_eq!(v.iter().position(|x| *x & 1 == 0).unwrap(), 5);
 400     assert_eq!(v.iter().position(|x| *x % 3 == 0).unwrap(), 1);
 401     assert!(v.iter().position(|x| *x % 12 == 0).is_none());
 402 }
 403
 404 #[test]
 405 fn test_count() {
 406     let xs = &[1i, 2, 2, 1, 5, 9, 0, 2];
 407     assert_eq!(xs.iter().filter(|x| **x == 2).count(), 3);
 408     assert_eq!(xs.iter().filter(|x| **x == 5).count(), 1);
 409     assert_eq!(xs.iter().filter(|x| **x == 95).count(), 0);
 410 }
 411
 412 #[test]
 413 fn test_max_by() {
 414     let xs: &[int] = &[-3i, 0, 1, 5, -10];
 415     assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
 416 }
 417
 418 #[test]
 419 fn test_min_by() {
 420     let xs: &[int] = &[-3i, 0, 1, 5, -10];
 421     assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
 422 }
 423
 424 #[test]
 425 fn test_by_ref() {
 426     let mut xs = range(0i, 10);
 427     // sum the first five values
 428     let partial_sum = xs.by_ref().take(5).fold(0, |a, b| a + b);
 429     assert_eq!(partial_sum, 10);
 430     assert_eq!(xs.next(), Some(5));
 431 }
 432
 433 #[test]
 434 fn test_rev() {
 435     let xs = [2i, 4, 6, 8, 10, 12, 14, 16];
 436     let mut it = xs.iter();
 437     it.next();
 438     it.next();
 439     assert!(it.rev().map(|&x| x).collect::<Vec<int>>() ==
 440             vec![16, 14, 12, 10, 8, 6]);
 441 }
 442
 443 #[test]
 444 fn test_cloned() {
 445     let xs = [2u8, 4, 6, 8];
 446
 447     let mut it = xs.iter().cloned();
 448     assert_eq!(it.len(), 4);
 449     assert_eq!(it.next(), Some(2));
 450     assert_eq!(it.len(), 3);
 451     assert_eq!(it.next(), Some(4));
 452     assert_eq!(it.len(), 2);
 453     assert_eq!(it.next_back(), Some(8));
 454     assert_eq!(it.len(), 1);
 455     assert_eq!(it.next_back(), Some(6));
 456     assert_eq!(it.len(), 0);
 457     assert_eq!(it.next_back(), None);
 458 }
 459
 460 #[test]
 461 fn test_double_ended_map() {
 462     let xs = [1i, 2, 3, 4, 5, 6];
 463     let mut it = xs.iter().map(|&x| x * -1);
 464     assert_eq!(it.next(), Some(-1));
 465     assert_eq!(it.next(), Some(-2));
 466     assert_eq!(it.next_back(), Some(-6));
 467     assert_eq!(it.next_back(), Some(-5));
 468     assert_eq!(it.next(), Some(-3));
 469     assert_eq!(it.next_back(), Some(-4));
 470     assert_eq!(it.next(), None);
 471 }
 472
 473 #[test]
 474 fn test_double_ended_enumerate() {
 475     let xs = [1i, 2, 3, 4, 5, 6];
 476     let mut it = xs.iter().map(|&x| x).enumerate();
 477     assert_eq!(it.next(), Some((0, 1)));
 478     assert_eq!(it.next(), Some((1, 2)));
 479     assert_eq!(it.next_back(), Some((5, 6)));
 480     assert_eq!(it.next_back(), Some((4, 5)));
 481     assert_eq!(it.next_back(), Some((3, 4)));
 482     assert_eq!(it.next_back(), Some((2, 3)));
 483     assert_eq!(it.next(), None);
 484 }
 485
 486 #[test]
 487 fn test_double_ended_zip() {
 488     let xs = [1i, 2, 3, 4, 5, 6];
 489     let ys = [1i, 2, 3, 7];
 490     let a = xs.iter().map(|&x| x);
 491     let b = ys.iter().map(|&x| x);
 492     let mut it = a.zip(b);
 493     assert_eq!(it.next(), Some((1, 1)));
 494     assert_eq!(it.next(), Some((2, 2)));
 495     assert_eq!(it.next_back(), Some((4, 7)));
 496     assert_eq!(it.next_back(), Some((3, 3)));
 497     assert_eq!(it.next(), None);
 498 }
 499
 500 #[test]
 501 fn test_double_ended_filter() {
 502     let xs = [1i, 2, 3, 4, 5, 6];
 503     let mut it = xs.iter().filter(|&x| *x & 1 == 0);
 504     assert_eq!(it.next_back().unwrap(), &6);
 505     assert_eq!(it.next_back().unwrap(), &4);
 506     assert_eq!(it.next().unwrap(), &2);
 507     assert_eq!(it.next_back(), None);
 508 }
 509
 510 #[test]
 511 fn test_double_ended_filter_map() {
 512     let xs = [1i, 2, 3, 4, 5, 6];
 513     let mut it = xs.iter().filter_map(|&x| if x & 1 == 0 { Some(x * 2) } else { None });
 514     assert_eq!(it.next_back().unwrap(), 12);
 515     assert_eq!(it.next_back().unwrap(), 8);
 516     assert_eq!(it.next().unwrap(), 4);
 517     assert_eq!(it.next_back(), None);
 518 }
 519
 520 #[test]
 521 fn test_double_ended_chain() {
 522     let xs = [1i, 2, 3, 4, 5];
 523     let ys = [7i, 9, 11];
 524     let mut it = xs.iter().chain(ys.iter()).rev();
 525     assert_eq!(it.next().unwrap(), &11);
 526     assert_eq!(it.next().unwrap(), &9);
 527     assert_eq!(it.next_back().unwrap(), &1);
 528     assert_eq!(it.next_back().unwrap(), &2);
 529     assert_eq!(it.next_back().unwrap(), &3);
 530     assert_eq!(it.next_back().unwrap(), &4);
 531     assert_eq!(it.next_back().unwrap(), &5);
 532     assert_eq!(it.next_back().unwrap(), &7);
 533     assert_eq!(it.next_back(), None);
 534 }
 535
 536 #[test]
 537 fn test_rposition() {
 538     fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' }
 539     fn g(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'd' }
 540     let v = [(0i, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
 541
 542     assert_eq!(v.iter().rposition(f), Some(3u));
 543     assert!(v.iter().rposition(g).is_none());
 544 }
 545
 546 #[test]
 547 #[should_fail]
 548 fn test_rposition_panic() {
 549     let v = [(box 0i, box 0i), (box 0i, box 0i),
 550              (box 0i, box 0i), (box 0i, box 0i)];
 551     let mut i = 0i;
 552     v.iter().rposition(|_elt| {
 553         if i == 2 {
 554             panic!()
 555         }
 556         i += 1;
 557         false
 558     });
 559 }
 560
 561
 562 #[cfg(test)]
 563 fn check_randacc_iter<A, T>(a: T, len: uint) where
 564     A: PartialEq,
 565     T: Clone + RandomAccessIterator + Iterator<Item=A>,
 566 {
 567     let mut b = a.clone();
 568     assert_eq!(len, b.indexable());
 569     let mut n = 0u;
 570     for (i, elt) in a.enumerate() {
 571         assert!(Some(elt) == b.idx(i));
 572         n += 1;
 573     }
 574     assert_eq!(n, len);
 575     assert!(None == b.idx(n));
 576     // call recursively to check after picking off an element
 577     if len > 0 {
 578         b.next();
 579         check_randacc_iter(b, len-1);
 580     }
 581 }
 582
 583
 584 #[test]
 585 fn test_double_ended_flat_map() {
 586     let u = [0u,1];
 587     let v = [5u,6,7,8];
 588     let mut it = u.iter().flat_map(|x| v[*x..v.len()].iter());
 589     assert_eq!(it.next_back().unwrap(), &8);
 590     assert_eq!(it.next().unwrap(),      &5);
 591     assert_eq!(it.next_back().unwrap(), &7);
 592     assert_eq!(it.next_back().unwrap(), &6);
 593     assert_eq!(it.next_back().unwrap(), &8);
 594     assert_eq!(it.next().unwrap(),      &6);
 595     assert_eq!(it.next_back().unwrap(), &7);
 596     assert_eq!(it.next_back(), None);
 597     assert_eq!(it.next(),      None);
 598     assert_eq!(it.next_back(), None);
 599 }
 600
 601 #[test]
 602 fn test_random_access_chain() {
 603     let xs = [1i, 2, 3, 4, 5];
 604     let ys = [7i, 9, 11];
 605     let mut it = xs.iter().chain(ys.iter());
 606     assert_eq!(it.idx(0).unwrap(), &1);
 607     assert_eq!(it.idx(5).unwrap(), &7);
 608     assert_eq!(it.idx(7).unwrap(), &11);
 609     assert!(it.idx(8).is_none());
 610
 611     it.next();
 612     it.next();
 613     it.next_back();
 614
 615     assert_eq!(it.idx(0).unwrap(), &3);
 616     assert_eq!(it.idx(4).unwrap(), &9);
 617     assert!(it.idx(6).is_none());
 618
 619     check_randacc_iter(it, xs.len() + ys.len() - 3);
 620 }
 621
 622 #[test]
 623 fn test_random_access_enumerate() {
 624     let xs = [1i, 2, 3, 4, 5];
 625     check_randacc_iter(xs.iter().enumerate(), xs.len());
 626 }
 627
 628 #[test]
 629 fn test_random_access_rev() {
 630     let xs = [1i, 2, 3, 4, 5];
 631     check_randacc_iter(xs.iter().rev(), xs.len());
 632     let mut it = xs.iter().rev();
 633     it.next();
 634     it.next_back();
 635     it.next();
 636     check_randacc_iter(it, xs.len() - 3);
 637 }
 638
 639 #[test]
 640 fn test_random_access_zip() {
 641     let xs = [1i, 2, 3, 4, 5];
 642     let ys = [7i, 9, 11];
 643     check_randacc_iter(xs.iter().zip(ys.iter()), cmp::min(xs.len(), ys.len()));
 644 }
 645
 646 #[test]
 647 fn test_random_access_take() {
 648     let xs = [1i, 2, 3, 4, 5];
 649     let empty: &[int] = &[];
 650     check_randacc_iter(xs.iter().take(3), 3);
 651     check_randacc_iter(xs.iter().take(20), xs.len());
 652     check_randacc_iter(xs.iter().take(0), 0);
 653     check_randacc_iter(empty.iter().take(2), 0);
 654 }
 655
 656 #[test]
 657 fn test_random_access_skip() {
 658     let xs = [1i, 2, 3, 4, 5];
 659     let empty: &[int] = &[];
 660     check_randacc_iter(xs.iter().skip(2), xs.len() - 2);
 661     check_randacc_iter(empty.iter().skip(2), 0);
 662 }
 663
 664 #[test]
 665 fn test_random_access_inspect() {
 666     let xs = [1i, 2, 3, 4, 5];
 667
 668     // test .map and .inspect that don't implement Clone
 669     let mut it = xs.iter().inspect(|_| {});
 670     assert_eq!(xs.len(), it.indexable());
 671     for (i, elt) in xs.iter().enumerate() {
 672         assert_eq!(Some(elt), it.idx(i));
 673     }
 674
 675 }
 676
 677 #[test]
 678 fn test_random_access_map() {
 679     let xs = [1i, 2, 3, 4, 5];
 680
 681     let mut it = xs.iter().map(|x| *x);
 682     assert_eq!(xs.len(), it.indexable());
 683     for (i, elt) in xs.iter().enumerate() {
 684         assert_eq!(Some(*elt), it.idx(i));
 685     }
 686 }
 687
 688 #[test]
 689 fn test_random_access_cycle() {
 690     let xs = [1i, 2, 3, 4, 5];
 691     let empty: &[int] = &[];
 692     check_randacc_iter(xs.iter().cycle().take(27), 27);
 693     check_randacc_iter(empty.iter().cycle(), 0);
 694 }
 695
 696 #[test]
 697 fn test_double_ended_range() {
 698     assert!(range(11i, 14).rev().collect::<Vec<int>>() == vec![13i, 12, 11]);
 699     for _ in range(10i, 0).rev() {
 700         panic!("unreachable");
 701     }
 702
 703     assert!(range(11u, 14).rev().collect::<Vec<uint>>() == vec![13u, 12, 11]);
 704     for _ in range(10u, 0).rev() {
 705         panic!("unreachable");
 706     }
 707 }
 708
 709 #[test]
 710 fn test_range() {
 711     assert!(range(0i, 5).collect::<Vec<int>>() == vec![0i, 1, 2, 3, 4]);
 712     assert!(range(-10i, -1).collect::<Vec<int>>() ==
 713                vec![-10, -9, -8, -7, -6, -5, -4, -3, -2]);
 714     assert!(range(0i, 5).rev().collect::<Vec<int>>() == vec![4, 3, 2, 1, 0]);
 715     assert_eq!(range(200i, -5).count(), 0);
 716     assert_eq!(range(200i, -5).rev().count(), 0);
 717     assert_eq!(range(200i, 200).count(), 0);
 718     assert_eq!(range(200i, 200).rev().count(), 0);
 719
 720     assert_eq!(range(0i, 100).size_hint(), (100, Some(100)));
 721     // this test is only meaningful when sizeof uint < sizeof u64
 722     assert_eq!(range(uint::MAX - 1, uint::MAX).size_hint(), (1, Some(1)));
 723     assert_eq!(range(-10i, -1).size_hint(), (9, Some(9)));
 724 }
 725
 726 #[test]
 727 fn test_range_inclusive() {
 728     assert!(range_inclusive(0i, 5).collect::<Vec<int>>() ==
 729             vec![0i, 1, 2, 3, 4, 5]);
 730     assert!(range_inclusive(0i, 5).rev().collect::<Vec<int>>() ==
 731             vec![5i, 4, 3, 2, 1, 0]);
 732     assert_eq!(range_inclusive(200i, -5).count(), 0);
 733     assert_eq!(range_inclusive(200i, -5).rev().count(), 0);
 734     assert!(range_inclusive(200i, 200).collect::<Vec<int>>() == vec![200]);
 735     assert!(range_inclusive(200i, 200).rev().collect::<Vec<int>>() == vec![200]);
 736 }
 737
 738 #[test]
 739 fn test_range_step() {
 740     assert!(range_step(0i, 20, 5).collect::<Vec<int>>() ==
 741             vec![0, 5, 10, 15]);
 742     assert!(range_step(20i, 0, -5).collect::<Vec<int>>() ==
 743             vec![20, 15, 10, 5]);
 744     assert!(range_step(20i, 0, -6).collect::<Vec<int>>() ==
 745             vec![20, 14, 8, 2]);
 746     assert!(range_step(200u8, 255, 50).collect::<Vec<u8>>() ==
 747             vec![200u8, 250]);
 748     assert!(range_step(200i, -5, 1).collect::<Vec<int>>() == vec![]);
 749     assert!(range_step(200i, 200, 1).collect::<Vec<int>>() == vec![]);
 750 }
 751
 752 #[test]
 753 fn test_range_step_inclusive() {
 754     assert!(range_step_inclusive(0i, 20, 5).collect::<Vec<int>>() ==
 755             vec![0, 5, 10, 15, 20]);
 756     assert!(range_step_inclusive(20i, 0, -5).collect::<Vec<int>>() ==
 757             vec![20, 15, 10, 5, 0]);
 758     assert!(range_step_inclusive(20i, 0, -6).collect::<Vec<int>>() ==
 759             vec![20, 14, 8, 2]);
 760     assert!(range_step_inclusive(200u8, 255, 50).collect::<Vec<u8>>() ==
 761             vec![200u8, 250]);
 762     assert!(range_step_inclusive(200i, -5, 1).collect::<Vec<int>>() ==
 763             vec![]);
 764     assert!(range_step_inclusive(200i, 200, 1).collect::<Vec<int>>() ==
 765             vec![200]);
 766 }
 767
 768 #[test]
 769 fn test_reverse() {
 770     let mut ys = [1i, 2, 3, 4, 5];
 771     ys.iter_mut().reverse_in_place();
 772     assert!(ys == [5, 4, 3, 2, 1]);
 773 }
 774
 775 #[test]
 776 fn test_peekable_is_empty() {
 777     let a = [1i];
 778     let mut it = a.iter().peekable();
 779     assert!( !it.is_empty() );
 780     it.next();
 781     assert!( it.is_empty() );
 782 }
 783
 784 #[test]
 785 fn test_min_max() {
 786     let v: [int; 0] = [];
 787     assert_eq!(v.iter().min_max(), NoElements);
 788
 789     let v = [1i];
 790     assert!(v.iter().min_max() == OneElement(&1));
 791
 792     let v = [1i, 2, 3, 4, 5];
 793     assert!(v.iter().min_max() == MinMax(&1, &5));
 794
 795     let v = [1i, 2, 3, 4, 5, 6];
 796     assert!(v.iter().min_max() == MinMax(&1, &6));
 797
 798     let v = [1i, 1, 1, 1];
 799     assert!(v.iter().min_max() == MinMax(&1, &1));
 800 }
 801
 802 #[test]
 803 fn test_min_max_result() {
 804     let r: MinMaxResult<int> = NoElements;
 805     assert_eq!(r.into_option(), None);
 806
 807     let r = OneElement(1i);
 808     assert_eq!(r.into_option(), Some((1,1)));
 809
 810     let r = MinMax(1i,2);
 811     assert_eq!(r.into_option(), Some((1,2)));
 812 }
 813
 814 #[test]
 815 fn test_iterate() {
 816     let mut it = iterate(1u, |x| x * 2);
 817     assert_eq!(it.next(), Some(1u));
 818     assert_eq!(it.next(), Some(2u));
 819     assert_eq!(it.next(), Some(4u));
 820     assert_eq!(it.next(), Some(8u));
 821 }
 822
 823 #[test]
 824 fn test_repeat() {
 825     let mut it = repeat(42u);
 826     assert_eq!(it.next(), Some(42u));
 827     assert_eq!(it.next(), Some(42u));
 828     assert_eq!(it.next(), Some(42u));
 829 }
 830
 831 #[bench]
 832 fn bench_rposition(b: &mut Bencher) {
 833     let it: Vec<uint> = range(0u, 300).collect();
 834     b.iter(|| {
 835         it.iter().rposition(|&x| x <= 150);
 836     });
 837 }
 838
 839 #[bench]
 840 fn bench_skip_while(b: &mut Bencher) {
 841     b.iter(|| {
 842         let it = range(0u, 100);
 843         let mut sum = 0;
 844         it.skip_while(|&x| { sum += x; sum < 4000 }).all(|_| true);
 845     });
 846 }
 847
 848 #[bench]
 849 fn bench_multiple_take(b: &mut Bencher) {
 850     let mut it = range(0u, 42).cycle();
 851     b.iter(|| {
 852         let n = it.next().unwrap();
 853         for _ in range(0u, n) {
 854             it.take(it.next().unwrap()).all(|_| true);
 855         }
 856     });
 857 }