src/libstd/iter.rs

   1 // Copyright 2013 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 /*!
  12
  13 Composable external iterators
  14
  15 # The `Iterator` trait
  16
  17 This module defines Rust's core iteration trait. The `Iterator` trait has one
  18 unimplemented method, `next`. All other methods are derived through default
  19 methods to perform operations such as `zip`, `chain`, `enumerate`, and `fold`.
  20
  21 The goal of this module is to unify iteration across all containers in Rust.
  22 An iterator can be considered as a state machine which is used to track which
  23 element will be yielded next.
  24
  25 There are various extensions also defined in this module to assist with various
  26 types of iteration, such as the `DoubleEndedIterator` for iterating in reverse,
  27 the `FromIterator` trait for creating a container from an iterator, and much
  28 more.
  29
  30 ## Rust's `for` loop
  31
  32 The special syntax used by rust's `for` loop is based around the `Iterator`
  33 trait defined in this module. For loops can be viewed as a syntactical expansion
  34 into a `loop`, for example, the `for` loop in this example is essentially
  35 translated to the `loop` below.
  36
  37 ```rust
  38 let values = ~[1, 2, 3];
  39
  40 // "Syntactical sugar" taking advantage of an iterator
  41 for &x in values.iter() {
  42     println!("{}", x);
  43 }
  44
  45 // Rough translation of the iteration without a `for` iterator.
  46 let mut it = values.iter();
  47 loop {
  48     match it.next() {
  49         Some(&x) => {
  50             println!("{}", x);
  51         }
  52         None => { break }
  53     }
  54 }
  55  ```
  56
  57 This `for` loop syntax can be applied to any iterator over any type.
  58
  59 ## Iteration protocol and more
  60
  61 More detailed information about iterators can be found in the [container
  62 tutorial](http://static.rust-lang.org/doc/master/tutorial-container.html) with
  63 the rest of the rust manuals.
  64
  65 */
  66
  67 use cmp;
  68 use num::{Zero, One, Integer, CheckedAdd, CheckedSub, Saturating, ToPrimitive};
  69 use option::{Option, Some, None};
  70 use ops::{Add, Mul, Sub};
  71 use cmp::{Eq, Ord};
  72 use clone::Clone;
  73 use uint;
  74 use util;
  75
  76 /// Conversion from an `Iterator`
  77 pub trait FromIterator<A> {
  78     /// Build a container with elements from an external iterator.
  79     fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> Self;
  80 }
  81
  82 /// A type growable from an `Iterator` implementation
  83 pub trait Extendable<A>: FromIterator<A> {
  84     /// Extend a container with the elements yielded by an iterator
  85     fn extend<T: Iterator<A>>(&mut self, iterator: &mut T);
  86 }
  87
  88 /// An interface for dealing with "external iterators". These types of iterators
  89 /// can be resumed at any time as all state is stored internally as opposed to
  90 /// being located on the call stack.
  91 ///
  92 /// The Iterator protocol states that an iterator yields a (potentially-empty,
  93 /// potentially-infinite) sequence of values, and returns `None` to signal that
  94 /// it's finished. The Iterator protocol does not define behavior after `None`
  95 /// is returned. A concrete Iterator implementation may choose to behave however
  96 /// it wishes, either by returning `None` infinitely, or by doing something
  97 /// else.
  98 pub trait Iterator<A> {
  99     /// Advance the iterator and return the next value. Return `None` when the end is reached.
 100     fn next(&mut self) -> Option<A>;
 101
 102     /// Return a lower bound and upper bound on the remaining length of the iterator.
 103     ///
 104     /// The common use case for the estimate is pre-allocating space to store the results.
 105     #[inline]
 106     fn size_hint(&self) -> (uint, Option<uint>) { (0, None) }
 107
 108     /// Chain this iterator with another, returning a new iterator which will
 109     /// finish iterating over the current iterator, and then it will iterate
 110     /// over the other specified iterator.
 111     ///
 112     /// # Example
 113     ///
 114     /// ```rust
 115     /// let a = [0];
 116     /// let b = [1];
 117     /// let mut it = a.iter().chain(b.iter());
 118     /// assert_eq!(it.next().unwrap(), &0);
 119     /// assert_eq!(it.next().unwrap(), &1);
 120     /// assert!(it.next().is_none());
 121     /// ```
 122     #[inline]
 123     fn chain<U: Iterator<A>>(self, other: U) -> Chain<Self, U> {
 124         Chain{a: self, b: other, flag: false}
 125     }
 126
 127     /// Creates an iterator which iterates over both this and the specified
 128     /// iterators simultaneously, yielding the two elements as pairs. When
 129     /// either iterator returns None, all further invocations of next() will
 130     /// return None.
 131     ///
 132     /// # Example
 133     ///
 134     /// ```rust
 135     /// let a = [0];
 136     /// let b = [1];
 137     /// let mut it = a.iter().zip(b.iter());
 138     /// assert_eq!(it.next().unwrap(), (&0, &1));
 139     /// assert!(it.next().is_none());
 140     /// ```
 141     #[inline]
 142     fn zip<B, U: Iterator<B>>(self, other: U) -> Zip<Self, U> {
 143         Zip{a: self, b: other}
 144     }
 145
 146     /// Creates a new iterator which will apply the specified function to each
 147     /// element returned by the first, yielding the mapped element instead.
 148     ///
 149     /// # Example
 150     ///
 151     /// ```rust
 152     /// let a = [1, 2];
 153     /// let mut it = a.iter().map(|&x| 2 * x);
 154     /// assert_eq!(it.next().unwrap(), 2);
 155     /// assert_eq!(it.next().unwrap(), 4);
 156     /// assert!(it.next().is_none());
 157     /// ```
 158     #[inline]
 159     fn map<'r, B>(self, f: 'r |A| -> B) -> Map<'r, A, B, Self> {
 160         Map{iter: self, f: f}
 161     }
 162
 163     /// Creates an iterator which applies the predicate to each element returned
 164     /// by this iterator. Only elements which have the predicate evaluate to
 165     /// `true` will be yielded.
 166     ///
 167     /// # Example
 168     ///
 169     /// ```rust
 170     /// let a = [1, 2];
 171     /// let mut it = a.iter().filter(|&x| *x > 1);
 172     /// assert_eq!(it.next().unwrap(), &2);
 173     /// assert!(it.next().is_none());
 174     /// ```
 175     #[inline]
 176     fn filter<'r>(self, predicate: 'r |&A| -> bool) -> Filter<'r, A, Self> {
 177         Filter{iter: self, predicate: predicate}
 178     }
 179
 180     /// Creates an iterator which both filters and maps elements.
 181     /// If the specified function returns None, the element is skipped.
 182     /// Otherwise the option is unwrapped and the new value is yielded.
 183     ///
 184     /// # Example
 185     ///
 186     /// ```rust
 187     /// let a = [1, 2];
 188     /// let mut it = a.iter().filter_map(|&x| if x > 1 {Some(2 * x)} else {None});
 189     /// assert_eq!(it.next().unwrap(), 4);
 190     /// assert!(it.next().is_none());
 191     /// ```
 192     #[inline]
 193     fn filter_map<'r, B>(self, f: 'r |A| -> Option<B>) -> FilterMap<'r, A, B, Self> {
 194         FilterMap { iter: self, f: f }
 195     }
 196
 197     /// Creates an iterator which yields a pair of the value returned by this
 198     /// iterator plus the current index of iteration.
 199     ///
 200     /// # Example
 201     ///
 202     /// ```rust
 203     /// let a = [100, 200];
 204     /// let mut it = a.iter().enumerate();
 205     /// assert_eq!(it.next().unwrap(), (0, &100));
 206     /// assert_eq!(it.next().unwrap(), (1, &200));
 207     /// assert!(it.next().is_none());
 208     /// ```
 209     #[inline]
 210     fn enumerate(self) -> Enumerate<Self> {
 211         Enumerate{iter: self, count: 0}
 212     }
 213
 214
 215     /// Creates an iterator that has a `.peek()` method
 216     /// that returns a optional reference to the next element.
 217     ///
 218     /// # Example
 219     ///
 220     /// ```rust
 221     /// let xs = [100, 200, 300];
 222     /// let mut it = xs.iter().map(|x| *x).peekable();
 223     /// assert_eq!(it.peek().unwrap(), &100);
 224     /// assert_eq!(it.next().unwrap(), 100);
 225     /// assert_eq!(it.next().unwrap(), 200);
 226     /// assert_eq!(it.peek().unwrap(), &300);
 227     /// assert_eq!(it.peek().unwrap(), &300);
 228     /// assert_eq!(it.next().unwrap(), 300);
 229     /// assert!(it.peek().is_none());
 230     /// assert!(it.next().is_none());
 231     /// ```
 232     #[inline]
 233     fn peekable(self) -> Peekable<A, Self> {
 234         Peekable{iter: self, peeked: None}
 235     }
 236
 237     /// Creates an iterator which invokes the predicate on elements until it
 238     /// returns false. Once the predicate returns false, all further elements are
 239     /// yielded.
 240     ///
 241     /// # Example
 242     ///
 243     /// ```rust
 244     /// let a = [1, 2, 3, 2, 1];
 245     /// let mut it = a.iter().skip_while(|&a| *a < 3);
 246     /// assert_eq!(it.next().unwrap(), &3);
 247     /// assert_eq!(it.next().unwrap(), &2);
 248     /// assert_eq!(it.next().unwrap(), &1);
 249     /// assert!(it.next().is_none());
 250     /// ```
 251     #[inline]
 252     fn skip_while<'r>(self, predicate: 'r |&A| -> bool) -> SkipWhile<'r, A, Self> {
 253         SkipWhile{iter: self, flag: false, predicate: predicate}
 254     }
 255
 256     /// Creates an iterator which yields elements so long as the predicate
 257     /// returns true. After the predicate returns false for the first time, no
 258     /// further elements will be yielded.
 259     ///
 260     /// # Example
 261     ///
 262     /// ```rust
 263     /// let a = [1, 2, 3, 2, 1];
 264     /// let mut it = a.iter().take_while(|&a| *a < 3);
 265     /// assert_eq!(it.next().unwrap(), &1);
 266     /// assert_eq!(it.next().unwrap(), &2);
 267     /// assert!(it.next().is_none());
 268     /// ```
 269     #[inline]
 270     fn take_while<'r>(self, predicate: 'r |&A| -> bool) -> TakeWhile<'r, A, Self> {
 271         TakeWhile{iter: self, flag: false, predicate: predicate}
 272     }
 273
 274     /// Creates an iterator which skips the first `n` elements of this iterator,
 275     /// and then it yields all further items.
 276     ///
 277     /// # Example
 278     ///
 279     /// ```rust
 280     /// let a = [1, 2, 3, 4, 5];
 281     /// let mut it = a.iter().skip(3);
 282     /// assert_eq!(it.next().unwrap(), &4);
 283     /// assert_eq!(it.next().unwrap(), &5);
 284     /// assert!(it.next().is_none());
 285     /// ```
 286     #[inline]
 287     fn skip(self, n: uint) -> Skip<Self> {
 288         Skip{iter: self, n: n}
 289     }
 290
 291     /// Creates an iterator which yields the first `n` elements of this
 292     /// iterator, and then it will always return None.
 293     ///
 294     /// # Example
 295     ///
 296     /// ```rust
 297     /// let a = [1, 2, 3, 4, 5];
 298     /// let mut it = a.iter().take(3);
 299     /// assert_eq!(it.next().unwrap(), &1);
 300     /// assert_eq!(it.next().unwrap(), &2);
 301     /// assert_eq!(it.next().unwrap(), &3);
 302     /// assert!(it.next().is_none());
 303     /// ```
 304     #[inline]
 305     fn take(self, n: uint) -> Take<Self> {
 306         Take{iter: self, n: n}
 307     }
 308
 309     /// Creates a new iterator which behaves in a similar fashion to foldl.
 310     /// There is a state which is passed between each iteration and can be
 311     /// mutated as necessary. The yielded values from the closure are yielded
 312     /// from the Scan instance when not None.
 313     ///
 314     /// # Example
 315     ///
 316     /// ```rust
 317     /// let a = [1, 2, 3, 4, 5];
 318     /// let mut it = a.iter().scan(1, |fac, &x| {
 319     ///   *fac = *fac * x;
 320     ///   Some(*fac)
 321     /// });
 322     /// assert_eq!(it.next().unwrap(), 1);
 323     /// assert_eq!(it.next().unwrap(), 2);
 324     /// assert_eq!(it.next().unwrap(), 6);
 325     /// assert_eq!(it.next().unwrap(), 24);
 326     /// assert_eq!(it.next().unwrap(), 120);
 327     /// assert!(it.next().is_none());
 328     /// ```
 329     #[inline]
 330     fn scan<'r, St, B>(self, initial_state: St, f: 'r |&mut St, A| -> Option<B>)
 331         -> Scan<'r, A, B, Self, St> {
 332         Scan{iter: self, f: f, state: initial_state}
 333     }
 334
 335     /// Creates an iterator that maps each element to an iterator,
 336     /// and yields the elements of the produced iterators
 337     ///
 338     /// # Example
 339     ///
 340     /// ```rust
 341     /// use std::iter::count;
 342     ///
 343     /// let xs = [2u, 3];
 344     /// let ys = [0u, 1, 0, 1, 2];
 345     /// let mut it = xs.iter().flat_map(|&x| count(0u, 1).take(x));
 346     /// // Check that `it` has the same elements as `ys`
 347     /// let mut i = 0;
 348     /// for x in it {
 349     ///     assert_eq!(x, ys[i]);
 350     ///     i += 1;
 351     /// }
 352     /// ```
 353     #[inline]
 354     fn flat_map<'r, B, U: Iterator<B>>(self, f: 'r |A| -> U)
 355         -> FlatMap<'r, A, Self, U> {
 356         FlatMap{iter: self, f: f, frontiter: None, backiter: None }
 357     }
 358
 359     /// Creates an iterator that yields `None` forever after the underlying
 360     /// iterator yields `None`. Random-access iterator behavior is not
 361     /// affected, only single and double-ended iterator behavior.
 362     ///
 363     /// # Example
 364     ///
 365     /// ```rust
 366     /// fn process<U: Iterator<int>>(it: U) -> int {
 367     ///     let mut it = it.fuse();
 368     ///     let mut sum = 0;
 369     ///     for x in it {
 370     ///         if x > 5 {
 371     ///             continue;
 372     ///         }
 373     ///         sum += x;
 374     ///     }
 375     ///     // did we exhaust the iterator?
 376     ///     if it.next().is_none() {
 377     ///         sum += 1000;
 378     ///     }
 379     ///     sum
 380     /// }
 381     /// let x = ~[1,2,3,7,8,9];
 382     /// assert_eq!(process(x.move_iter()), 1006);
 383     /// ```
 384     #[inline]
 385     fn fuse(self) -> Fuse<Self> {
 386         Fuse{iter: self, done: false}
 387     }
 388
 389     /// Creates an iterator that calls a function with a reference to each
 390     /// element before yielding it. This is often useful for debugging an
 391     /// iterator pipeline.
 392     ///
 393     /// # Example
 394     ///
 395     /// ```rust
 396     /// use std::iter::AdditiveIterator;
 397     ///
 398     /// let xs = [1u, 4, 2, 3, 8, 9, 6];
 399     /// let sum = xs.iter()
 400     ///             .map(|&x| x)
 401     ///             .inspect(|&x| debug!("filtering {}", x))
 402     ///             .filter(|&x| x % 2 == 0)
 403     ///             .inspect(|&x| debug!("{} made it through", x))
 404     ///             .sum();
 405     /// println(sum.to_str());
 406     /// ```
 407     #[inline]
 408     fn inspect<'r>(self, f: 'r |&A|) -> Inspect<'r, A, Self> {
 409         Inspect{iter: self, f: f}
 410     }
 411
 412     /// Creates a wrapper around a mutable reference to the iterator.
 413     ///
 414     /// This is useful to allow applying iterator adaptors while still
 415     /// retaining ownership of the original iterator value.
 416     ///
 417     /// # Example
 418     ///
 419     /// ```rust
 420     /// let mut xs = range(0, 10);
 421     /// // sum the first five values
 422     /// let partial_sum = xs.by_ref().take(5).fold(0, |a, b| a + b);
 423     /// assert!(partial_sum == 10);
 424     /// // xs.next() is now `5`
 425     /// assert!(xs.next() == Some(5));
 426     /// ```
 427     fn by_ref<'r>(&'r mut self) -> ByRef<'r, Self> {
 428         ByRef{iter: self}
 429     }
 430
 431     /// Apply a function to each element, or stop iterating if the
 432     /// function returns `false`.
 433     ///
 434     /// # Example
 435     ///
 436     /// ```rust
 437     /// range(0, 5).advance(|x| {print!("{} ", x); true});
 438     /// ```
 439     #[inline]
 440     fn advance(&mut self, f: |A| -> bool) -> bool {
 441         loop {
 442             match self.next() {
 443                 Some(x) => {
 444                     if !f(x) { return false; }
 445                 }
 446                 None => { return true; }
 447             }
 448         }
 449     }
 450
 451     /// Loops through the entire iterator, collecting all of the elements into
 452     /// a container implementing `FromIterator`.
 453     ///
 454     /// # Example
 455     ///
 456     /// ```rust
 457     /// let a = [1, 2, 3, 4, 5];
 458     /// let b: ~[int] = a.iter().map(|&x| x).collect();
 459     /// assert!(a == b);
 460     /// ```
 461     #[inline]
 462     fn collect<B: FromIterator<A>>(&mut self) -> B {
 463         FromIterator::from_iterator(self)
 464     }
 465
 466     /// Loops through the entire iterator, collecting all of the elements into
 467     /// a unique vector. This is simply collect() specialized for vectors.
 468     ///
 469     /// # Example
 470     ///
 471     /// ```rust
 472     /// let a = [1, 2, 3, 4, 5];
 473     /// let b: ~[int] = a.iter().map(|&x| x).to_owned_vec();
 474     /// assert!(a == b);
 475     /// ```
 476     #[inline]
 477     fn to_owned_vec(&mut self) -> ~[A] {
 478         self.collect()
 479     }
 480
 481     /// Loops through `n` iterations, returning the `n`th element of the
 482     /// iterator.
 483     ///
 484     /// # Example
 485     ///
 486     /// ```rust
 487     /// let a = [1, 2, 3, 4, 5];
 488     /// let mut it = a.iter();
 489     /// assert!(it.nth(2).unwrap() == &3);
 490     /// assert!(it.nth(2) == None);
 491     /// ```
 492     #[inline]
 493     fn nth(&mut self, mut n: uint) -> Option<A> {
 494         loop {
 495             match self.next() {
 496                 Some(x) => if n == 0 { return Some(x) },
 497                 None => return None
 498             }
 499             n -= 1;
 500         }
 501     }
 502
 503     /// Loops through the entire iterator, returning the last element of the
 504     /// iterator.
 505     ///
 506     /// # Example
 507     ///
 508     /// ```rust
 509     /// let a = [1, 2, 3, 4, 5];
 510     /// assert!(a.iter().last().unwrap() == &5);
 511     /// ```
 512     #[inline]
 513     fn last(&mut self) -> Option<A> {
 514         let mut last = None;
 515         for x in *self { last = Some(x); }
 516         last
 517     }
 518
 519     /// Performs a fold operation over the entire iterator, returning the
 520     /// eventual state at the end of the iteration.
 521     ///
 522     /// # Example
 523     ///
 524     /// ```rust
 525     /// let a = [1, 2, 3, 4, 5];
 526     /// assert!(a.iter().fold(0, |a, &b| a + b) == 15);
 527     /// ```
 528     #[inline]
 529     fn fold<B>(&mut self, init: B, f: |B, A| -> B) -> B {
 530         let mut accum = init;
 531         loop {
 532             match self.next() {
 533                 Some(x) => { accum = f(accum, x); }
 534                 None    => { break; }
 535             }
 536         }
 537         accum
 538     }
 539
 540     /// Counts the number of elements in this iterator.
 541     ///
 542     /// # Example
 543     ///
 544     /// ```rust
 545     /// let a = [1, 2, 3, 4, 5];
 546     /// let mut it = a.iter();
 547     /// assert!(it.len() == 5);
 548     /// assert!(it.len() == 0);
 549     /// ```
 550     #[inline]
 551     fn len(&mut self) -> uint {
 552         self.fold(0, |cnt, _x| cnt + 1)
 553     }
 554
 555     /// Tests whether the predicate holds true for all elements in the iterator.
 556     ///
 557     /// # Example
 558     ///
 559     /// ```rust
 560     /// let a = [1, 2, 3, 4, 5];
 561     /// assert!(a.iter().all(|x| *x > 0));
 562     /// assert!(!a.iter().all(|x| *x > 2));
 563     /// ```
 564     #[inline]
 565     fn all(&mut self, f: |A| -> bool) -> bool {
 566         for x in *self { if !f(x) { return false; } }
 567         true
 568     }
 569
 570     /// Tests whether any element of an iterator satisfies the specified
 571     /// predicate.
 572     ///
 573     /// # Example
 574     ///
 575     /// ```rust
 576     /// let a = [1, 2, 3, 4, 5];
 577     /// let mut it = a.iter();
 578     /// assert!(it.any(|x| *x == 3));
 579     /// assert!(!it.any(|x| *x == 3));
 580     /// ```
 581     #[inline]
 582     fn any(&mut self, f: |A| -> bool) -> bool {
 583         for x in *self { if f(x) { return true; } }
 584         false
 585     }
 586
 587     /// Return the first element satisfying the specified predicate
 588     #[inline]
 589     fn find(&mut self, predicate: |&A| -> bool) -> Option<A> {
 590         for x in *self {
 591             if predicate(&x) { return Some(x) }
 592         }
 593         None
 594     }
 595
 596     /// Return the index of the first element satisfying the specified predicate
 597     #[inline]
 598     fn position(&mut self, predicate: |A| -> bool) -> Option<uint> {
 599         let mut i = 0;
 600         for x in *self {
 601             if predicate(x) {
 602                 return Some(i);
 603             }
 604             i += 1;
 605         }
 606         None
 607     }
 608
 609     /// Count the number of elements satisfying the specified predicate
 610     #[inline]
 611     fn count(&mut self, predicate: |A| -> bool) -> uint {
 612         let mut i = 0;
 613         for x in *self {
 614             if predicate(x) { i += 1 }
 615         }
 616         i
 617     }
 618
 619     /// Return the element that gives the maximum value from the
 620     /// specified function.
 621     ///
 622     /// # Example
 623     ///
 624     /// ```rust
 625     /// let xs = [-3i, 0, 1, 5, -10];
 626     /// assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
 627     /// ```
 628     #[inline]
 629     fn max_by<B: Ord>(&mut self, f: |&A| -> B) -> Option<A> {
 630         self.fold(None, |max: Option<(A, B)>, x| {
 631             let x_val = f(&x);
 632             match max {
 633                 None             => Some((x, x_val)),
 634                 Some((y, y_val)) => if x_val > y_val {
 635                     Some((x, x_val))
 636                 } else {
 637                     Some((y, y_val))
 638                 }
 639             }
 640         }).map(|(x, _)| x)
 641     }
 642
 643     /// Return the element that gives the minimum value from the
 644     /// specified function.
 645     ///
 646     /// # Example
 647     ///
 648     /// ```rust
 649     /// let xs = [-3i, 0, 1, 5, -10];
 650     /// assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
 651     /// ```
 652     #[inline]
 653     fn min_by<B: Ord>(&mut self, f: |&A| -> B) -> Option<A> {
 654         self.fold(None, |min: Option<(A, B)>, x| {
 655             let x_val = f(&x);
 656             match min {
 657                 None             => Some((x, x_val)),
 658                 Some((y, y_val)) => if x_val < y_val {
 659                     Some((x, x_val))
 660                 } else {
 661                     Some((y, y_val))
 662                 }
 663             }
 664         }).map(|(x, _)| x)
 665     }
 666 }
 667
 668 /// A range iterator able to yield elements from both ends
 669 pub trait DoubleEndedIterator<A>: Iterator<A> {
 670     /// Yield an element from the end of the range, returning `None` if the range is empty.
 671     fn next_back(&mut self) -> Option<A>;
 672
 673     /// Flip the direction of the iterator
 674     ///
 675     /// The inverted iterator flips the ends on an iterator that can already
 676     /// be iterated from the front and from the back.
 677     ///
 678     ///
 679     /// If the iterator also implements RandomAccessIterator, the inverted
 680     /// iterator is also random access, with the indices starting at the back
 681     /// of the original iterator.
 682     ///
 683     /// Note: Random access with inverted indices still only applies to the first
 684     /// `uint::max_value` elements of the original iterator.
 685     #[inline]
 686     fn invert(self) -> Invert<Self> {
 687         Invert{iter: self}
 688     }
 689 }
 690
 691 /// A double-ended iterator yielding mutable references
 692 pub trait MutableDoubleEndedIterator {
 693     // FIXME: #5898: should be called `reverse`
 694     /// Use an iterator to reverse a container in-place
 695     fn reverse_(&mut self);
 696 }
 697
 698 impl<'a, A, T: DoubleEndedIterator<&'a mut A>> MutableDoubleEndedIterator for T {
 699     // FIXME: #5898: should be called `reverse`
 700     /// Use an iterator to reverse a container in-place
 701     fn reverse_(&mut self) {
 702         loop {
 703             match (self.next(), self.next_back()) {
 704                 (Some(x), Some(y)) => util::swap(x, y),
 705                 _ => break
 706             }
 707         }
 708     }
 709 }
 710
 711
 712 /// An object implementing random access indexing by `uint`
 713 ///
 714 /// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`.
 715 pub trait RandomAccessIterator<A>: Iterator<A> {
 716     /// Return the number of indexable elements. At most `std::uint::max_value`
 717     /// elements are indexable, even if the iterator represents a longer range.
 718     fn indexable(&self) -> uint;
 719
 720     /// Return an element at an index
 721     fn idx(&self, index: uint) -> Option<A>;
 722 }
 723
 724 /// An iterator that knows its exact length
 725 ///
 726 /// This trait is a helper for iterators like the vector iterator, so that
 727 /// it can support double-ended enumeration.
 728 ///
 729 /// `Iterator::size_hint` *must* return the exact size of the iterator.
 730 /// Note that the size must fit in `uint`.
 731 pub trait ExactSize<A> : DoubleEndedIterator<A> {
 732     /// Return the index of the last element satisfying the specified predicate
 733     ///
 734     /// If no element matches, None is returned.
 735     #[inline]
 736     fn rposition(&mut self, predicate: |A| -> bool) -> Option<uint> {
 737         let (lower, upper) = self.size_hint();
 738         assert!(upper == Some(lower));
 739         let mut i = lower;
 740         loop {
 741             match self.next_back() {
 742                 None => break,
 743                 Some(x) => {
 744                     i = match i.checked_sub(&1) {
 745                         Some(x) => x,
 746                         None => fail!("rposition: incorrect ExactSize")
 747                     };
 748                     if predicate(x) {
 749                         return Some(i)
 750                     }
 751                 }
 752             }
 753         }
 754         None
 755     }
 756 }
 757
 758 // All adaptors that preserve the size of the wrapped iterator are fine
 759 // Adaptors that may overflow in `size_hint` are not, i.e. `Chain`.
 760 impl<A, T: ExactSize<A>> ExactSize<(uint, A)> for Enumerate<T> {}
 761 impl<'a, A, T: ExactSize<A>> ExactSize<A> for Inspect<'a, A, T> {}
 762 impl<A, T: ExactSize<A>> ExactSize<A> for Invert<T> {}
 763 impl<'a, A, B, T: ExactSize<A>> ExactSize<B> for Map<'a, A, B, T> {}
 764 impl<A, B, T: ExactSize<A>, U: ExactSize<B>> ExactSize<(A, B)> for Zip<T, U> {}
 765
 766 /// An double-ended iterator with the direction inverted
 767 #[deriving(Clone)]
 768 pub struct Invert<T> {
 769     priv iter: T
 770 }
 771
 772 impl<A, T: DoubleEndedIterator<A>> Iterator<A> for Invert<T> {
 773     #[inline]
 774     fn next(&mut self) -> Option<A> { self.iter.next_back() }
 775     #[inline]
 776     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 777 }
 778
 779 impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Invert<T> {
 780     #[inline]
 781     fn next_back(&mut self) -> Option<A> { self.iter.next() }
 782 }
 783
 784 impl<A, T: DoubleEndedIterator<A> + RandomAccessIterator<A>> RandomAccessIterator<A>
 785     for Invert<T> {
 786     #[inline]
 787     fn indexable(&self) -> uint { self.iter.indexable() }
 788     #[inline]
 789     fn idx(&self, index: uint) -> Option<A> {
 790         self.iter.idx(self.indexable() - index - 1)
 791     }
 792 }
 793
 794 /// A mutable reference to an iterator
 795 pub struct ByRef<'a, T> {
 796     priv iter: &'a mut T
 797 }
 798
 799 impl<'a, A, T: Iterator<A>> Iterator<A> for ByRef<'a, T> {
 800     #[inline]
 801     fn next(&mut self) -> Option<A> { self.iter.next() }
 802     #[inline]
 803     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 804 }
 805
 806 impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for ByRef<'a, T> {
 807     #[inline]
 808     fn next_back(&mut self) -> Option<A> { self.iter.next_back() }
 809 }
 810
 811 /// A trait for iterators over elements which can be added together
 812 pub trait AdditiveIterator<A> {
 813     /// Iterates over the entire iterator, summing up all the elements
 814     ///
 815     /// # Example
 816     ///
 817     /// ```rust
 818     /// use std::iter::AdditiveIterator;
 819     ///
 820     /// let a = [1, 2, 3, 4, 5];
 821     /// let mut it = a.iter().map(|&x| x);
 822     /// assert!(it.sum() == 15);
 823     /// ```
 824     fn sum(&mut self) -> A;
 825 }
 826
 827 impl<A: Add<A, A> + Zero, T: Iterator<A>> AdditiveIterator<A> for T {
 828     #[inline]
 829     fn sum(&mut self) -> A {
 830         let zero: A = Zero::zero();
 831         self.fold(zero, |s, x| s + x)
 832     }
 833 }
 834
 835 /// A trait for iterators over elements whose elements can be multiplied
 836 /// together.
 837 pub trait MultiplicativeIterator<A> {
 838     /// Iterates over the entire iterator, multiplying all the elements
 839     ///
 840     /// # Example
 841     ///
 842     /// ```rust
 843     /// use std::iter::{count, MultiplicativeIterator};
 844     ///
 845     /// fn factorial(n: uint) -> uint {
 846     ///     count(1u, 1).take_while(|&i| i <= n).product()
 847     /// }
 848     /// assert!(factorial(0) == 1);
 849     /// assert!(factorial(1) == 1);
 850     /// assert!(factorial(5) == 120);
 851     /// ```
 852     fn product(&mut self) -> A;
 853 }
 854
 855 impl<A: Mul<A, A> + One, T: Iterator<A>> MultiplicativeIterator<A> for T {
 856     #[inline]
 857     fn product(&mut self) -> A {
 858         let one: A = One::one();
 859         self.fold(one, |p, x| p * x)
 860     }
 861 }
 862
 863 /// A trait for iterators over elements which can be compared to one another.
 864 /// The type of each element must ascribe to the `Ord` trait.
 865 pub trait OrdIterator<A> {
 866     /// Consumes the entire iterator to return the maximum element.
 867     ///
 868     /// # Example
 869     ///
 870     /// ```rust
 871     /// let a = [1, 2, 3, 4, 5];
 872     /// assert!(a.iter().max().unwrap() == &5);
 873     /// ```
 874     fn max(&mut self) -> Option<A>;
 875
 876     /// Consumes the entire iterator to return the minimum element.
 877     ///
 878     /// # Example
 879     ///
 880     /// ```rust
 881     /// let a = [1, 2, 3, 4, 5];
 882     /// assert!(a.iter().min().unwrap() == &1);
 883     /// ```
 884     fn min(&mut self) -> Option<A>;
 885 }
 886
 887 impl<A: Ord, T: Iterator<A>> OrdIterator<A> for T {
 888     #[inline]
 889     fn max(&mut self) -> Option<A> {
 890         self.fold(None, |max, x| {
 891             match max {
 892                 None    => Some(x),
 893                 Some(y) => Some(cmp::max(x, y))
 894             }
 895         })
 896     }
 897
 898     #[inline]
 899     fn min(&mut self) -> Option<A> {
 900         self.fold(None, |min, x| {
 901             match min {
 902                 None    => Some(x),
 903                 Some(y) => Some(cmp::min(x, y))
 904             }
 905         })
 906     }
 907 }
 908
 909 /// A trait for iterators that are cloneable.
 910 pub trait CloneableIterator {
 911     /// Repeats an iterator endlessly
 912     ///
 913     /// # Example
 914     ///
 915     /// ```rust
 916     /// use std::iter::{CloneableIterator, count};
 917     ///
 918     /// let a = count(1,1).take(1);
 919     /// let mut cy = a.cycle();
 920     /// assert_eq!(cy.next(), Some(1));
 921     /// assert_eq!(cy.next(), Some(1));
 922     /// ```
 923     fn cycle(self) -> Cycle<Self>;
 924 }
 925
 926 impl<A, T: Clone + Iterator<A>> CloneableIterator for T {
 927     #[inline]
 928     fn cycle(self) -> Cycle<T> {
 929         Cycle{orig: self.clone(), iter: self}
 930     }
 931 }
 932
 933 /// An iterator that repeats endlessly
 934 #[deriving(Clone)]
 935 pub struct Cycle<T> {
 936     priv orig: T,
 937     priv iter: T,
 938 }
 939
 940 impl<A, T: Clone + Iterator<A>> Iterator<A> for Cycle<T> {
 941     #[inline]
 942     fn next(&mut self) -> Option<A> {
 943         match self.iter.next() {
 944             None => { self.iter = self.orig.clone(); self.iter.next() }
 945             y => y
 946         }
 947     }
 948
 949     #[inline]
 950     fn size_hint(&self) -> (uint, Option<uint>) {
 951         // the cycle iterator is either empty or infinite
 952         match self.orig.size_hint() {
 953             sz @ (0, Some(0)) => sz,
 954             (0, _) => (0, None),
 955             _ => (uint::max_value, None)
 956         }
 957     }
 958 }
 959
 960 impl<A, T: Clone + RandomAccessIterator<A>> RandomAccessIterator<A> for Cycle<T> {
 961     #[inline]
 962     fn indexable(&self) -> uint {
 963         if self.orig.indexable() > 0 {
 964             uint::max_value
 965         } else {
 966             0
 967         }
 968     }
 969
 970     #[inline]
 971     fn idx(&self, index: uint) -> Option<A> {
 972         let liter = self.iter.indexable();
 973         let lorig = self.orig.indexable();
 974         if lorig == 0 {
 975             None
 976         } else if index < liter {
 977             self.iter.idx(index)
 978         } else {
 979             self.orig.idx((index - liter) % lorig)
 980         }
 981     }
 982 }
 983
 984 /// An iterator which strings two iterators together
 985 #[deriving(Clone)]
 986 pub struct Chain<T, U> {
 987     priv a: T,
 988     priv b: U,
 989     priv flag: bool
 990 }
 991
 992 impl<A, T: Iterator<A>, U: Iterator<A>> Iterator<A> for Chain<T, U> {
 993     #[inline]
 994     fn next(&mut self) -> Option<A> {
 995         if self.flag {
 996             self.b.next()
 997         } else {
 998             match self.a.next() {
 999                 Some(x) => return Some(x),
1000                 _ => ()
1001             }
1002             self.flag = true;
1003             self.b.next()
1004         }
1005     }
1006
1007     #[inline]
1008     fn size_hint(&self) -> (uint, Option<uint>) {
1009         let (a_lower, a_upper) = self.a.size_hint();
1010         let (b_lower, b_upper) = self.b.size_hint();
1011
1012         let lower = a_lower.saturating_add(b_lower);
1013
1014         let upper = match (a_upper, b_upper) {
1015             (Some(x), Some(y)) => x.checked_add(&y),
1016             _ => None
1017         };
1018
1019         (lower, upper)
1020     }
1021 }
1022
1023 impl<A, T: DoubleEndedIterator<A>, U: DoubleEndedIterator<A>> DoubleEndedIterator<A>
1024 for Chain<T, U> {
1025     #[inline]
1026     fn next_back(&mut self) -> Option<A> {
1027         match self.b.next_back() {
1028             Some(x) => Some(x),
1029             None => self.a.next_back()
1030         }
1031     }
1032 }
1033
1034 impl<A, T: RandomAccessIterator<A>, U: RandomAccessIterator<A>> RandomAccessIterator<A>
1035 for Chain<T, U> {
1036     #[inline]
1037     fn indexable(&self) -> uint {
1038         let (a, b) = (self.a.indexable(), self.b.indexable());
1039         a.saturating_add(b)
1040     }
1041
1042     #[inline]
1043     fn idx(&self, index: uint) -> Option<A> {
1044         let len = self.a.indexable();
1045         if index < len {
1046             self.a.idx(index)
1047         } else {
1048             self.b.idx(index - len)
1049         }
1050     }
1051 }
1052
1053 /// An iterator which iterates two other iterators simultaneously
1054 #[deriving(Clone)]
1055 pub struct Zip<T, U> {
1056     priv a: T,
1057     priv b: U
1058 }
1059
1060 impl<A, B, T: Iterator<A>, U: Iterator<B>> Iterator<(A, B)> for Zip<T, U> {
1061     #[inline]
1062     fn next(&mut self) -> Option<(A, B)> {
1063         match self.a.next() {
1064             None => None,
1065             Some(x) => match self.b.next() {
1066                 None => None,
1067                 Some(y) => Some((x, y))
1068             }
1069         }
1070     }
1071
1072     #[inline]
1073     fn size_hint(&self) -> (uint, Option<uint>) {
1074         let (a_lower, a_upper) = self.a.size_hint();
1075         let (b_lower, b_upper) = self.b.size_hint();
1076
1077         let lower = cmp::min(a_lower, b_lower);
1078
1079         let upper = match (a_upper, b_upper) {
1080             (Some(x), Some(y)) => Some(cmp::min(x,y)),
1081             (Some(x), None) => Some(x),
1082             (None, Some(y)) => Some(y),
1083             (None, None) => None
1084         };
1085
1086         (lower, upper)
1087     }
1088 }
1089
1090 impl<A, B, T: ExactSize<A>, U: ExactSize<B>> DoubleEndedIterator<(A, B)>
1091 for Zip<T, U> {
1092     #[inline]
1093     fn next_back(&mut self) -> Option<(A, B)> {
1094         let (a_sz, a_upper) = self.a.size_hint();
1095         let (b_sz, b_upper) = self.b.size_hint();
1096         assert!(a_upper == Some(a_sz));
1097         assert!(b_upper == Some(b_sz));
1098         if a_sz < b_sz {
1099             for _ in range(0, b_sz - a_sz) { self.b.next_back(); }
1100         } else if a_sz > b_sz {
1101             for _ in range(0, a_sz - b_sz) { self.a.next_back(); }
1102         }
1103         let (a_sz, _) = self.a.size_hint();
1104         let (b_sz, _) = self.b.size_hint();
1105         assert!(a_sz == b_sz);
1106         match (self.a.next_back(), self.b.next_back()) {
1107             (Some(x), Some(y)) => Some((x, y)),
1108             _ => None
1109         }
1110     }
1111 }
1112
1113 impl<A, B, T: RandomAccessIterator<A>, U: RandomAccessIterator<B>>
1114 RandomAccessIterator<(A, B)> for Zip<T, U> {
1115     #[inline]
1116     fn indexable(&self) -> uint {
1117         cmp::min(self.a.indexable(), self.b.indexable())
1118     }
1119
1120     #[inline]
1121     fn idx(&self, index: uint) -> Option<(A, B)> {
1122         match self.a.idx(index) {
1123             None => None,
1124             Some(x) => match self.b.idx(index) {
1125                 None => None,
1126                 Some(y) => Some((x, y))
1127             }
1128         }
1129     }
1130 }
1131
1132 /// An iterator which maps the values of `iter` with `f`
1133 pub struct Map<'a, A, B, T> {
1134     priv iter: T,
1135     priv f: 'a |A| -> B
1136 }
1137
1138 impl<'a, A, B, T> Map<'a, A, B, T> {
1139     #[inline]
1140     fn do_map(&self, elt: Option<A>) -> Option<B> {
1141         match elt {
1142             Some(a) => Some((self.f)(a)),
1143             _ => None
1144         }
1145     }
1146 }
1147
1148 impl<'a, A, B, T: Iterator<A>> Iterator<B> for Map<'a, A, B, T> {
1149     #[inline]
1150     fn next(&mut self) -> Option<B> {
1151         let next = self.iter.next();
1152         self.do_map(next)
1153     }
1154
1155     #[inline]
1156     fn size_hint(&self) -> (uint, Option<uint>) {
1157         self.iter.size_hint()
1158     }
1159 }
1160
1161 impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B> for Map<'a, A, B, T> {
1162     #[inline]
1163     fn next_back(&mut self) -> Option<B> {
1164         let next = self.iter.next_back();
1165         self.do_map(next)
1166     }
1167 }
1168
1169 impl<'a, A, B, T: RandomAccessIterator<A>> RandomAccessIterator<B> for Map<'a, A, B, T> {
1170     #[inline]
1171     fn indexable(&self) -> uint {
1172         self.iter.indexable()
1173     }
1174
1175     #[inline]
1176     fn idx(&self, index: uint) -> Option<B> {
1177         self.do_map(self.iter.idx(index))
1178     }
1179 }
1180
1181 /// An iterator which filters the elements of `iter` with `predicate`
1182 pub struct Filter<'a, A, T> {
1183     priv iter: T,
1184     priv predicate: 'a |&A| -> bool
1185 }
1186
1187 impl<'a, A, T: Iterator<A>> Iterator<A> for Filter<'a, A, T> {
1188     #[inline]
1189     fn next(&mut self) -> Option<A> {
1190         for x in self.iter {
1191             if (self.predicate)(&x) {
1192                 return Some(x);
1193             } else {
1194                 continue
1195             }
1196         }
1197         None
1198     }
1199
1200     #[inline]
1201     fn size_hint(&self) -> (uint, Option<uint>) {
1202         let (_, upper) = self.iter.size_hint();
1203         (0, upper) // can't know a lower bound, due to the predicate
1204     }
1205 }
1206
1207 impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Filter<'a, A, T> {
1208     #[inline]
1209     fn next_back(&mut self) -> Option<A> {
1210         loop {
1211             match self.iter.next_back() {
1212                 None => return None,
1213                 Some(x) => {
1214                     if (self.predicate)(&x) {
1215                         return Some(x);
1216                     } else {
1217                         continue
1218                     }
1219                 }
1220             }
1221         }
1222     }
1223 }
1224
1225 /// An iterator which uses `f` to both filter and map elements from `iter`
1226 pub struct FilterMap<'a, A, B, T> {
1227     priv iter: T,
1228     priv f: 'a |A| -> Option<B>
1229 }
1230
1231 impl<'a, A, B, T: Iterator<A>> Iterator<B> for FilterMap<'a, A, B, T> {
1232     #[inline]
1233     fn next(&mut self) -> Option<B> {
1234         for x in self.iter {
1235             match (self.f)(x) {
1236                 Some(y) => return Some(y),
1237                 None => ()
1238             }
1239         }
1240         None
1241     }
1242
1243     #[inline]
1244     fn size_hint(&self) -> (uint, Option<uint>) {
1245         let (_, upper) = self.iter.size_hint();
1246         (0, upper) // can't know a lower bound, due to the predicate
1247     }
1248 }
1249
1250 impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B>
1251 for FilterMap<'a, A, B, T> {
1252     #[inline]
1253     fn next_back(&mut self) -> Option<B> {
1254         loop {
1255             match self.iter.next_back() {
1256                 None => return None,
1257                 Some(x) => {
1258                     match (self.f)(x) {
1259                         Some(y) => return Some(y),
1260                         None => ()
1261                     }
1262                 }
1263             }
1264         }
1265     }
1266 }
1267
1268 /// An iterator which yields the current count and the element during iteration
1269 #[deriving(Clone)]
1270 pub struct Enumerate<T> {
1271     priv iter: T,
1272     priv count: uint
1273 }
1274
1275 impl<A, T: Iterator<A>> Iterator<(uint, A)> for Enumerate<T> {
1276     #[inline]
1277     fn next(&mut self) -> Option<(uint, A)> {
1278         match self.iter.next() {
1279             Some(a) => {
1280                 let ret = Some((self.count, a));
1281                 self.count += 1;
1282                 ret
1283             }
1284             _ => None
1285         }
1286     }
1287
1288     #[inline]
1289     fn size_hint(&self) -> (uint, Option<uint>) {
1290         self.iter.size_hint()
1291     }
1292 }
1293
1294 impl<A, T: ExactSize<A>> DoubleEndedIterator<(uint, A)> for Enumerate<T> {
1295     #[inline]
1296     fn next_back(&mut self) -> Option<(uint, A)> {
1297         match self.iter.next_back() {
1298             Some(a) => {
1299                 let (lower, upper) = self.iter.size_hint();
1300                 assert!(upper == Some(lower));
1301                 Some((self.count + lower, a))
1302             }
1303             _ => None
1304         }
1305     }
1306 }
1307
1308 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<(uint, A)> for Enumerate<T> {
1309     #[inline]
1310     fn indexable(&self) -> uint {
1311         self.iter.indexable()
1312     }
1313
1314     #[inline]
1315     fn idx(&self, index: uint) -> Option<(uint, A)> {
1316         match self.iter.idx(index) {
1317             Some(a) => Some((self.count + index, a)),
1318             _ => None,
1319         }
1320     }
1321 }
1322
1323 /// An iterator with a `peek()` that returns an optional reference to the next element.
1324 pub struct Peekable<A, T> {
1325     priv iter: T,
1326     priv peeked: Option<A>,
1327 }
1328
1329 impl<A, T: Iterator<A>> Iterator<A> for Peekable<A, T> {
1330     #[inline]
1331     fn next(&mut self) -> Option<A> {
1332         if self.peeked.is_some() { self.peeked.take() }
1333         else { self.iter.next() }
1334     }
1335
1336     #[inline]
1337     fn size_hint(&self) -> (uint, Option<uint>) {
1338         let (lo, hi) = self.iter.size_hint();
1339         if self.peeked.is_some() {
1340             let lo = lo.saturating_add(1);
1341             let hi = match hi {
1342                 Some(x) => x.checked_add(&1),
1343                 None => None
1344             };
1345             (lo, hi)
1346         } else {
1347             (lo, hi)
1348         }
1349     }
1350 }
1351
1352 impl<'a, A, T: Iterator<A>> Peekable<A, T> {
1353     /// Return a reference to the next element of the iterator with out advancing it,
1354     /// or None if the iterator is exhausted.
1355     #[inline]
1356     pub fn peek(&'a mut self) -> Option<&'a A> {
1357         if self.peeked.is_none() {
1358             self.peeked = self.iter.next();
1359         }
1360         match self.peeked {
1361             Some(ref value) => Some(value),
1362             None => None,
1363         }
1364     }
1365 }
1366
1367 /// An iterator which rejects elements while `predicate` is true
1368 pub struct SkipWhile<'a, A, T> {
1369     priv iter: T,
1370     priv flag: bool,
1371     priv predicate: 'a |&A| -> bool
1372 }
1373
1374 impl<'a, A, T: Iterator<A>> Iterator<A> for SkipWhile<'a, A, T> {
1375     #[inline]
1376     fn next(&mut self) -> Option<A> {
1377         let mut next = self.iter.next();
1378         if self.flag {
1379             next
1380         } else {
1381             loop {
1382                 match next {
1383                     Some(x) => {
1384                         if (self.predicate)(&x) {
1385                             next = self.iter.next();
1386                             continue
1387                         } else {
1388                             self.flag = true;
1389                             return Some(x)
1390                         }
1391                     }
1392                     None => return None
1393                 }
1394             }
1395         }
1396     }
1397
1398     #[inline]
1399     fn size_hint(&self) -> (uint, Option<uint>) {
1400         let (_, upper) = self.iter.size_hint();
1401         (0, upper) // can't know a lower bound, due to the predicate
1402     }
1403 }
1404
1405 /// An iterator which only accepts elements while `predicate` is true
1406 pub struct TakeWhile<'a, A, T> {
1407     priv iter: T,
1408     priv flag: bool,
1409     priv predicate: 'a |&A| -> bool
1410 }
1411
1412 impl<'a, A, T: Iterator<A>> Iterator<A> for TakeWhile<'a, A, T> {
1413     #[inline]
1414     fn next(&mut self) -> Option<A> {
1415         if self.flag {
1416             None
1417         } else {
1418             match self.iter.next() {
1419                 Some(x) => {
1420                     if (self.predicate)(&x) {
1421                         Some(x)
1422                     } else {
1423                         self.flag = true;
1424                         None
1425                     }
1426                 }
1427                 None => None
1428             }
1429         }
1430     }
1431
1432     #[inline]
1433     fn size_hint(&self) -> (uint, Option<uint>) {
1434         let (_, upper) = self.iter.size_hint();
1435         (0, upper) // can't know a lower bound, due to the predicate
1436     }
1437 }
1438
1439 /// An iterator which skips over `n` elements of `iter`.
1440 #[deriving(Clone)]
1441 pub struct Skip<T> {
1442     priv iter: T,
1443     priv n: uint
1444 }
1445
1446 impl<A, T: Iterator<A>> Iterator<A> for Skip<T> {
1447     #[inline]
1448     fn next(&mut self) -> Option<A> {
1449         let mut next = self.iter.next();
1450         if self.n == 0 {
1451             next
1452         } else {
1453             let mut n = self.n;
1454             while n > 0 {
1455                 n -= 1;
1456                 match next {
1457                     Some(_) => {
1458                         next = self.iter.next();
1459                         continue
1460                     }
1461                     None => {
1462                         self.n = 0;
1463                         return None
1464                     }
1465                 }
1466             }
1467             self.n = 0;
1468             next
1469         }
1470     }
1471
1472     #[inline]
1473     fn size_hint(&self) -> (uint, Option<uint>) {
1474         let (lower, upper) = self.iter.size_hint();
1475
1476         let lower = lower.saturating_sub(self.n);
1477
1478         let upper = match upper {
1479             Some(x) => Some(x.saturating_sub(self.n)),
1480             None => None
1481         };
1482
1483         (lower, upper)
1484     }
1485 }
1486
1487 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Skip<T> {
1488     #[inline]
1489     fn indexable(&self) -> uint {
1490         self.iter.indexable().saturating_sub(self.n)
1491     }
1492
1493     #[inline]
1494     fn idx(&self, index: uint) -> Option<A> {
1495         if index >= self.indexable() {
1496             None
1497         } else {
1498             self.iter.idx(index + self.n)
1499         }
1500     }
1501 }
1502
1503 /// An iterator which only iterates over the first `n` iterations of `iter`.
1504 #[deriving(Clone)]
1505 pub struct Take<T> {
1506     priv iter: T,
1507     priv n: uint
1508 }
1509
1510 impl<A, T: Iterator<A>> Iterator<A> for Take<T> {
1511     #[inline]
1512     fn next(&mut self) -> Option<A> {
1513         if self.n != 0 {
1514             self.n -= 1;
1515             self.iter.next()
1516         } else {
1517             None
1518         }
1519     }
1520
1521     #[inline]
1522     fn size_hint(&self) -> (uint, Option<uint>) {
1523         let (lower, upper) = self.iter.size_hint();
1524
1525         let lower = cmp::min(lower, self.n);
1526
1527         let upper = match upper {
1528             Some(x) if x < self.n => Some(x),
1529             _ => Some(self.n)
1530         };
1531
1532         (lower, upper)
1533     }
1534 }
1535
1536 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Take<T> {
1537     #[inline]
1538     fn indexable(&self) -> uint {
1539         cmp::min(self.iter.indexable(), self.n)
1540     }
1541
1542     #[inline]
1543     fn idx(&self, index: uint) -> Option<A> {
1544         if index >= self.n {
1545             None
1546         } else {
1547             self.iter.idx(index)
1548         }
1549     }
1550 }
1551
1552
1553 /// An iterator to maintain state while iterating another iterator
1554 pub struct Scan<'a, A, B, T, St> {
1555     priv iter: T,
1556     priv f: 'a |&mut St, A| -> Option<B>,
1557
1558     /// The current internal state to be passed to the closure next.
1559     state: St
1560 }
1561
1562 impl<'a, A, B, T: Iterator<A>, St> Iterator<B> for Scan<'a, A, B, T, St> {
1563     #[inline]
1564     fn next(&mut self) -> Option<B> {
1565         self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
1566     }
1567
1568     #[inline]
1569     fn size_hint(&self) -> (uint, Option<uint>) {
1570         let (_, upper) = self.iter.size_hint();
1571         (0, upper) // can't know a lower bound, due to the scan function
1572     }
1573 }
1574
1575 /// An iterator that maps each element to an iterator,
1576 /// and yields the elements of the produced iterators
1577 ///
1578 pub struct FlatMap<'a, A, T, U> {
1579     priv iter: T,
1580     priv f: 'a |A| -> U,
1581     priv frontiter: Option<U>,
1582     priv backiter: Option<U>,
1583 }
1584
1585 impl<'a, A, T: Iterator<A>, B, U: Iterator<B>> Iterator<B> for FlatMap<'a, A, T, U> {
1586     #[inline]
1587     fn next(&mut self) -> Option<B> {
1588         loop {
1589             for inner in self.frontiter.mut_iter() {
1590                 for x in *inner {
1591                     return Some(x)
1592                 }
1593             }
1594             match self.iter.next().map(|x| (self.f)(x)) {
1595                 None => return self.backiter.as_mut().and_then(|it| it.next()),
1596                 next => self.frontiter = next,
1597             }
1598         }
1599     }
1600
1601     #[inline]
1602     fn size_hint(&self) -> (uint, Option<uint>) {
1603         let (flo, fhi) = self.frontiter.as_ref().map_default((0, Some(0)), |it| it.size_hint());
1604         let (blo, bhi) = self.backiter.as_ref().map_default((0, Some(0)), |it| it.size_hint());
1605         let lo = flo.saturating_add(blo);
1606         match (self.iter.size_hint(), fhi, bhi) {
1607             ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(&b)),
1608             _ => (lo, None)
1609         }
1610     }
1611 }
1612
1613 impl<'a,
1614      A, T: DoubleEndedIterator<A>,
1615      B, U: DoubleEndedIterator<B>> DoubleEndedIterator<B>
1616      for FlatMap<'a, A, T, U> {
1617     #[inline]
1618     fn next_back(&mut self) -> Option<B> {
1619         loop {
1620             for inner in self.backiter.mut_iter() {
1621                 match inner.next_back() {
1622                     None => (),
1623                     y => return y
1624                 }
1625             }
1626             match self.iter.next_back().map(|x| (self.f)(x)) {
1627                 None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
1628                 next => self.backiter = next,
1629             }
1630         }
1631     }
1632 }
1633
1634 /// An iterator that yields `None` forever after the underlying iterator
1635 /// yields `None` once.
1636 #[deriving(Clone, DeepClone)]
1637 pub struct Fuse<T> {
1638     priv iter: T,
1639     priv done: bool
1640 }
1641
1642 impl<A, T: Iterator<A>> Iterator<A> for Fuse<T> {
1643     #[inline]
1644     fn next(&mut self) -> Option<A> {
1645         if self.done {
1646             None
1647         } else {
1648             match self.iter.next() {
1649                 None => {
1650                     self.done = true;
1651                     None
1652                 }
1653                 x => x
1654             }
1655         }
1656     }
1657
1658     #[inline]
1659     fn size_hint(&self) -> (uint, Option<uint>) {
1660         if self.done {
1661             (0, Some(0))
1662         } else {
1663             self.iter.size_hint()
1664         }
1665     }
1666 }
1667
1668 impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Fuse<T> {
1669     #[inline]
1670     fn next_back(&mut self) -> Option<A> {
1671         if self.done {
1672             None
1673         } else {
1674             match self.iter.next_back() {
1675                 None => {
1676                     self.done = true;
1677                     None
1678                 }
1679                 x => x
1680             }
1681         }
1682     }
1683 }
1684
1685 // Allow RandomAccessIterators to be fused without affecting random-access behavior
1686 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Fuse<T> {
1687     #[inline]
1688     fn indexable(&self) -> uint {
1689         self.iter.indexable()
1690     }
1691
1692     #[inline]
1693     fn idx(&self, index: uint) -> Option<A> {
1694         self.iter.idx(index)
1695     }
1696 }
1697
1698 impl<T> Fuse<T> {
1699     /// Resets the fuse such that the next call to .next() or .next_back() will
1700     /// call the underlying iterator again even if it previously returned None.
1701     #[inline]
1702     pub fn reset_fuse(&mut self) {
1703         self.done = false
1704     }
1705 }
1706
1707 /// An iterator that calls a function with a reference to each
1708 /// element before yielding it.
1709 pub struct Inspect<'a, A, T> {
1710     priv iter: T,
1711     priv f: 'a |&A|
1712 }
1713
1714 impl<'a, A, T> Inspect<'a, A, T> {
1715     #[inline]
1716     fn do_inspect(&self, elt: Option<A>) -> Option<A> {
1717         match elt {
1718             Some(ref a) => (self.f)(a),
1719             None => ()
1720         }
1721
1722         elt
1723     }
1724 }
1725
1726 impl<'a, A, T: Iterator<A>> Iterator<A> for Inspect<'a, A, T> {
1727     #[inline]
1728     fn next(&mut self) -> Option<A> {
1729         let next = self.iter.next();
1730         self.do_inspect(next)
1731     }
1732
1733     #[inline]
1734     fn size_hint(&self) -> (uint, Option<uint>) {
1735         self.iter.size_hint()
1736     }
1737 }
1738
1739 impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A>
1740 for Inspect<'a, A, T> {
1741     #[inline]
1742     fn next_back(&mut self) -> Option<A> {
1743         let next = self.iter.next_back();
1744         self.do_inspect(next)
1745     }
1746 }
1747
1748 impl<'a, A, T: RandomAccessIterator<A>> RandomAccessIterator<A>
1749 for Inspect<'a, A, T> {
1750     #[inline]
1751     fn indexable(&self) -> uint {
1752         self.iter.indexable()
1753     }
1754
1755     #[inline]
1756     fn idx(&self, index: uint) -> Option<A> {
1757         self.do_inspect(self.iter.idx(index))
1758     }
1759 }
1760
1761 /// An iterator which just modifies the contained state throughout iteration.
1762 pub struct Unfold<'a, A, St> {
1763     priv f: 'a |&mut St| -> Option<A>,
1764     /// Internal state that will be yielded on the next iteration
1765     state: St
1766 }
1767
1768 impl<'a, A, St> Unfold<'a, A, St> {
1769     /// Creates a new iterator with the specified closure as the "iterator
1770     /// function" and an initial state to eventually pass to the iterator
1771     #[inline]
1772     pub fn new<'a>(initial_state: St, f: 'a |&mut St| -> Option<A>)
1773                -> Unfold<'a, A, St> {
1774         Unfold {
1775             f: f,
1776             state: initial_state
1777         }
1778     }
1779 }
1780
1781 impl<'a, A, St> Iterator<A> for Unfold<'a, A, St> {
1782     #[inline]
1783     fn next(&mut self) -> Option<A> {
1784         (self.f)(&mut self.state)
1785     }
1786
1787     #[inline]
1788     fn size_hint(&self) -> (uint, Option<uint>) {
1789         // no possible known bounds at this point
1790         (0, None)
1791     }
1792 }
1793
1794 /// An infinite iterator starting at `start` and advancing by `step` with each
1795 /// iteration
1796 #[deriving(Clone)]
1797 pub struct Counter<A> {
1798     /// The current state the counter is at (next value to be yielded)
1799     priv state: A,
1800     /// The amount that this iterator is stepping by
1801     priv step: A
1802 }
1803
1804 /// Creates a new counter with the specified start/step
1805 #[inline]
1806 pub fn count<A>(start: A, step: A) -> Counter<A> {
1807     Counter{state: start, step: step}
1808 }
1809
1810 impl<A: Add<A, A> + Clone> Iterator<A> for Counter<A> {
1811     #[inline]
1812     fn next(&mut self) -> Option<A> {
1813         let result = self.state.clone();
1814         self.state = self.state + self.step;
1815         Some(result)
1816     }
1817
1818     #[inline]
1819     fn size_hint(&self) -> (uint, Option<uint>) {
1820         (uint::max_value, None) // Too bad we can't specify an infinite lower bound
1821     }
1822 }
1823
1824 /// An iterator over the range [start, stop)
1825 #[deriving(Clone, DeepClone)]
1826 pub struct Range<A> {
1827     priv state: A,
1828     priv stop: A,
1829     priv one: A
1830 }
1831
1832 /// Return an iterator over the range [start, stop)
1833 #[inline]
1834 pub fn range<A: Add<A, A> + Ord + Clone + One>(start: A, stop: A) -> Range<A> {
1835     Range{state: start, stop: stop, one: One::one()}
1836 }
1837
1838 // FIXME: #10414: Unfortunate type bound
1839 impl<A: Add<A, A> + Ord + Clone + ToPrimitive> Iterator<A> for Range<A> {
1840     #[inline]
1841     fn next(&mut self) -> Option<A> {
1842         if self.state < self.stop {
1843             let result = self.state.clone();
1844             self.state = self.state + self.one;
1845             Some(result)
1846         } else {
1847             None
1848         }
1849     }
1850
1851     #[inline]
1852     fn size_hint(&self) -> (uint, Option<uint>) {
1853         // This first checks if the elements are representable as i64. If they aren't, try u64 (to
1854         // handle cases like range(huge, huger)). We don't use uint/int because the difference of
1855         // the i64/u64 might lie within their range.
1856         let bound = match self.state.to_i64() {
1857             Some(a) => {
1858                 let sz = self.stop.to_i64().map(|b| b.checked_sub(&a));
1859                 match sz {
1860                     Some(Some(bound)) => bound.to_uint(),
1861                     _ => None,
1862                 }
1863             },
1864             None => match self.state.to_u64() {
1865                 Some(a) => {
1866                     let sz = self.stop.to_u64().map(|b| b.checked_sub(&a));
1867                     match sz {
1868                         Some(Some(bound)) => bound.to_uint(),
1869                         _ => None
1870                     }
1871                 },
1872                 None => None
1873             }
1874         };
1875
1876         match bound {
1877             Some(b) => (b, Some(b)),
1878             // Standard fallback for unbounded/unrepresentable bounds
1879             None => (0, None)
1880         }
1881     }
1882 }
1883
1884 /// `Integer` is required to ensure the range will be the same regardless of
1885 /// the direction it is consumed.
1886 impl<A: Integer + Ord + Clone + ToPrimitive> DoubleEndedIterator<A> for Range<A> {
1887     #[inline]
1888     fn next_back(&mut self) -> Option<A> {
1889         if self.stop > self.state {
1890             self.stop = self.stop - self.one;
1891             Some(self.stop.clone())
1892         } else {
1893             None
1894         }
1895     }
1896 }
1897
1898 /// An iterator over the range [start, stop]
1899 #[deriving(Clone, DeepClone)]
1900 pub struct RangeInclusive<A> {
1901     priv range: Range<A>,
1902     priv done: bool
1903 }
1904
1905 /// Return an iterator over the range [start, stop]
1906 #[inline]
1907 pub fn range_inclusive<A: Add<A, A> + Ord + Clone + One + ToPrimitive>(start: A, stop: A)
1908     -> RangeInclusive<A> {
1909     RangeInclusive{range: range(start, stop), done: false}
1910 }
1911
1912 impl<A: Add<A, A> + Eq + Ord + Clone + ToPrimitive> Iterator<A> for RangeInclusive<A> {
1913     #[inline]
1914     fn next(&mut self) -> Option<A> {
1915         match self.range.next() {
1916             Some(x) => Some(x),
1917             None => {
1918                 if !self.done && self.range.state == self.range.stop {
1919                     self.done = true;
1920                     Some(self.range.stop.clone())
1921                 } else {
1922                     None
1923                 }
1924             }
1925         }
1926     }
1927
1928     #[inline]
1929     fn size_hint(&self) -> (uint, Option<uint>) {
1930         let (lo, hi) = self.range.size_hint();
1931         if self.done {
1932             (lo, hi)
1933         } else {
1934             let lo = lo.saturating_add(1);
1935             let hi = match hi {
1936                 Some(x) => x.checked_add(&1),
1937                 None => None
1938             };
1939             (lo, hi)
1940         }
1941     }
1942 }
1943
1944 impl<A: Sub<A, A> + Integer + Ord + Clone + ToPrimitive> DoubleEndedIterator<A>
1945     for RangeInclusive<A> {
1946     #[inline]
1947     fn next_back(&mut self) -> Option<A> {
1948         if self.range.stop > self.range.state {
1949             let result = self.range.stop.clone();
1950             self.range.stop = self.range.stop - self.range.one;
1951             Some(result)
1952         } else if !self.done && self.range.state == self.range.stop {
1953             self.done = true;
1954             Some(self.range.stop.clone())
1955         } else {
1956             None
1957         }
1958     }
1959 }
1960
1961 /// An iterator over the range [start, stop) by `step`. It handles overflow by stopping.
1962 #[deriving(Clone, DeepClone)]
1963 pub struct RangeStep<A> {
1964     priv state: A,
1965     priv stop: A,
1966     priv step: A,
1967     priv rev: bool
1968 }
1969
1970 /// Return an iterator over the range [start, stop) by `step`. It handles overflow by stopping.
1971 #[inline]
1972 pub fn range_step<A: CheckedAdd + Ord + Clone + Zero>(start: A, stop: A, step: A) -> RangeStep<A> {
1973     let rev = step < Zero::zero();
1974     RangeStep{state: start, stop: stop, step: step, rev: rev}
1975 }
1976
1977 impl<A: CheckedAdd + Ord + Clone> Iterator<A> for RangeStep<A> {
1978     #[inline]
1979     fn next(&mut self) -> Option<A> {
1980         if (self.rev && self.state > self.stop) || (!self.rev && self.state < self.stop) {
1981             let result = self.state.clone();
1982             match self.state.checked_add(&self.step) {
1983                 Some(x) => self.state = x,
1984                 None => self.state = self.stop.clone()
1985             }
1986             Some(result)
1987         } else {
1988             None
1989         }
1990     }
1991 }
1992
1993 /// An iterator over the range [start, stop] by `step`. It handles overflow by stopping.
1994 #[deriving(Clone, DeepClone)]
1995 pub struct RangeStepInclusive<A> {
1996     priv state: A,
1997     priv stop: A,
1998     priv step: A,
1999     priv rev: bool,
2000     priv done: bool
2001 }
2002
2003 /// Return an iterator over the range [start, stop] by `step`. It handles overflow by stopping.
2004 #[inline]
2005 pub fn range_step_inclusive<A: CheckedAdd + Ord + Clone + Zero>(start: A, stop: A,
2006                                                                 step: A) -> RangeStepInclusive<A> {
2007     let rev = step < Zero::zero();
2008     RangeStepInclusive{state: start, stop: stop, step: step, rev: rev, done: false}
2009 }
2010
2011 impl<A: CheckedAdd + Ord + Clone + Eq> Iterator<A> for RangeStepInclusive<A> {
2012     #[inline]
2013     fn next(&mut self) -> Option<A> {
2014         if !self.done && ((self.rev && self.state >= self.stop) ||
2015                           (!self.rev && self.state <= self.stop)) {
2016             let result = self.state.clone();
2017             match self.state.checked_add(&self.step) {
2018                 Some(x) => self.state = x,
2019                 None => self.done = true
2020             }
2021             Some(result)
2022         } else {
2023             None
2024         }
2025     }
2026 }
2027
2028 /// An iterator that repeats an element endlessly
2029 #[deriving(Clone, DeepClone)]
2030 pub struct Repeat<A> {
2031     priv element: A
2032 }
2033
2034 impl<A: Clone> Repeat<A> {
2035     /// Create a new `Repeat` that endlessly repeats the element `elt`.
2036     #[inline]
2037     pub fn new(elt: A) -> Repeat<A> {
2038         Repeat{element: elt}
2039     }
2040 }
2041
2042 impl<A: Clone> Iterator<A> for Repeat<A> {
2043     #[inline]
2044     fn next(&mut self) -> Option<A> { self.idx(0) }
2045     #[inline]
2046     fn size_hint(&self) -> (uint, Option<uint>) { (uint::max_value, None) }
2047 }
2048
2049 impl<A: Clone> DoubleEndedIterator<A> for Repeat<A> {
2050     #[inline]
2051     fn next_back(&mut self) -> Option<A> { self.idx(0) }
2052 }
2053
2054 impl<A: Clone> RandomAccessIterator<A> for Repeat<A> {
2055     #[inline]
2056     fn indexable(&self) -> uint { uint::max_value }
2057     #[inline]
2058     fn idx(&self, _: uint) -> Option<A> { Some(self.element.clone()) }
2059 }
2060
2061 /// Functions for lexicographical ordering of sequences.
2062 ///
2063 /// Lexicographical ordering through `<`, `<=`, `>=`, `>` requires
2064 /// that the elements implement both `Eq` and `Ord`.
2065 ///
2066 /// If two sequences are equal up until the point where one ends,
2067 /// the shorter sequence compares less.
2068 pub mod order {
2069     use cmp;
2070     use cmp::{TotalEq, TotalOrd, Ord, Eq};
2071     use option::{Some, None};
2072     use super::Iterator;
2073
2074     /// Compare `a` and `b` for equality using `TotalOrd`
2075     pub fn equals<A: TotalEq, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2076         loop {
2077             match (a.next(), b.next()) {
2078                 (None, None) => return true,
2079                 (None, _) | (_, None) => return false,
2080                 (Some(x), Some(y)) => if !x.equals(&y) { return false },
2081             }
2082         }
2083     }
2084
2085     /// Order `a` and `b` lexicographically using `TotalOrd`
2086     pub fn cmp<A: TotalOrd, T: Iterator<A>>(mut a: T, mut b: T) -> cmp::Ordering {
2087         loop {
2088             match (a.next(), b.next()) {
2089                 (None, None) => return cmp::Equal,
2090                 (None, _   ) => return cmp::Less,
2091                 (_   , None) => return cmp::Greater,
2092                 (Some(x), Some(y)) => match x.cmp(&y) {
2093                     cmp::Equal => (),
2094                     non_eq => return non_eq,
2095                 },
2096             }
2097         }
2098     }
2099
2100     /// Compare `a` and `b` for equality (Using partial equality, `Eq`)
2101     pub fn eq<A: Eq, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2102         loop {
2103             match (a.next(), b.next()) {
2104                 (None, None) => return true,
2105                 (None, _) | (_, None) => return false,
2106                 (Some(x), Some(y)) => if !x.eq(&y) { return false },
2107             }
2108         }
2109     }
2110
2111     /// Compare `a` and `b` for nonequality (Using partial equality, `Eq`)
2112     pub fn ne<A: Eq, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2113         loop {
2114             match (a.next(), b.next()) {
2115                 (None, None) => return false,
2116                 (None, _) | (_, None) => return true,
2117                 (Some(x), Some(y)) => if x.ne(&y) { return true },
2118             }
2119         }
2120     }
2121
2122     /// Return `a` < `b` lexicographically (Using partial order, `Ord`)
2123     pub fn lt<A: Eq + Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2124         loop {
2125             match (a.next(), b.next()) {
2126                 (None, None) => return false,
2127                 (None, _   ) => return true,
2128                 (_   , None) => return false,
2129                 (Some(x), Some(y)) => if x.ne(&y) { return x.lt(&y) },
2130             }
2131         }
2132     }
2133
2134     /// Return `a` <= `b` lexicographically (Using partial order, `Ord`)
2135     pub fn le<A: Eq + Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2136         loop {
2137             match (a.next(), b.next()) {
2138                 (None, None) => return true,
2139                 (None, _   ) => return true,
2140                 (_   , None) => return false,
2141                 (Some(x), Some(y)) => if x.ne(&y) { return x.le(&y) },
2142             }
2143         }
2144     }
2145
2146     /// Return `a` > `b` lexicographically (Using partial order, `Ord`)
2147     pub fn gt<A: Eq + Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2148         loop {
2149             match (a.next(), b.next()) {
2150                 (None, None) => return false,
2151                 (None, _   ) => return false,
2152                 (_   , None) => return true,
2153                 (Some(x), Some(y)) => if x.ne(&y) { return x.gt(&y) },
2154             }
2155         }
2156     }
2157
2158     /// Return `a` >= `b` lexicographically (Using partial order, `Ord`)
2159     pub fn ge<A: Eq + Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2160         loop {
2161             match (a.next(), b.next()) {
2162                 (None, None) => return true,
2163                 (None, _   ) => return false,
2164                 (_   , None) => return true,
2165                 (Some(x), Some(y)) => if x.ne(&y) { return x.ge(&y) },
2166             }
2167         }
2168     }
2169
2170     #[test]
2171     fn test_lt() {
2172         use vec::ImmutableVector;
2173
2174         let empty: [int, ..0] = [];
2175         let xs = [1,2,3];
2176         let ys = [1,2,0];
2177
2178         assert!(!lt(xs.iter(), ys.iter()));
2179         assert!(!le(xs.iter(), ys.iter()));
2180         assert!( gt(xs.iter(), ys.iter()));
2181         assert!( ge(xs.iter(), ys.iter()));
2182
2183         assert!( lt(ys.iter(), xs.iter()));
2184         assert!( le(ys.iter(), xs.iter()));
2185         assert!(!gt(ys.iter(), xs.iter()));
2186         assert!(!ge(ys.iter(), xs.iter()));
2187
2188         assert!( lt(empty.iter(), xs.iter()));
2189         assert!( le(empty.iter(), xs.iter()));
2190         assert!(!gt(empty.iter(), xs.iter()));
2191         assert!(!ge(empty.iter(), xs.iter()));
2192
2193         // Sequence with NaN
2194         let u = [1.0, 2.0];
2195         let v = [0.0/0.0, 3.0];
2196
2197         assert!(!lt(u.iter(), v.iter()));
2198         assert!(!le(u.iter(), v.iter()));
2199         assert!(!gt(u.iter(), v.iter()));
2200         assert!(!ge(u.iter(), v.iter()));
2201
2202         let a = [0.0/0.0];
2203         let b = [1.0];
2204         let c = [2.0];
2205
2206         assert!(lt(a.iter(), b.iter()) == (a[0] <  b[0]));
2207         assert!(le(a.iter(), b.iter()) == (a[0] <= b[0]));
2208         assert!(gt(a.iter(), b.iter()) == (a[0] >  b[0]));
2209         assert!(ge(a.iter(), b.iter()) == (a[0] >= b[0]));
2210
2211         assert!(lt(c.iter(), b.iter()) == (c[0] <  b[0]));
2212         assert!(le(c.iter(), b.iter()) == (c[0] <= b[0]));
2213         assert!(gt(c.iter(), b.iter()) == (c[0] >  b[0]));
2214         assert!(ge(c.iter(), b.iter()) == (c[0] >= b[0]));
2215     }
2216 }
2217
2218 #[cfg(test)]
2219 mod tests {
2220     use super::*;
2221     use prelude::*;
2222
2223     use cmp;
2224     use uint;
2225     use num;
2226
2227     #[test]
2228     fn test_counter_from_iter() {
2229         let mut it = count(0, 5).take(10);
2230         let xs: ~[int] = FromIterator::from_iterator(&mut it);
2231         assert_eq!(xs, ~[0, 5, 10, 15, 20, 25, 30, 35, 40, 45]);
2232     }
2233
2234     #[test]
2235     fn test_iterator_chain() {
2236         let xs = [0u, 1, 2, 3, 4, 5];
2237         let ys = [30u, 40, 50, 60];
2238         let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
2239         let mut it = xs.iter().chain(ys.iter());
2240         let mut i = 0;
2241         for &x in it {
2242             assert_eq!(x, expected[i]);
2243             i += 1;
2244         }
2245         assert_eq!(i, expected.len());
2246
2247         let ys = count(30u, 10).take(4);
2248         let mut it = xs.iter().map(|&x| x).chain(ys);
2249         let mut i = 0;
2250         for x in it {
2251             assert_eq!(x, expected[i]);
2252             i += 1;
2253         }
2254         assert_eq!(i, expected.len());
2255     }
2256
2257     #[test]
2258     fn test_filter_map() {
2259         let mut it = count(0u, 1u).take(10)
2260             .filter_map(|x| if x.is_even() { Some(x*x) } else { None });
2261         assert_eq!(it.collect::<~[uint]>(), ~[0*0, 2*2, 4*4, 6*6, 8*8]);
2262     }
2263
2264     #[test]
2265     fn test_iterator_enumerate() {
2266         let xs = [0u, 1, 2, 3, 4, 5];
2267         let mut it = xs.iter().enumerate();
2268         for (i, &x) in it {
2269             assert_eq!(i, x);
2270         }
2271     }
2272
2273     #[test]
2274     fn test_iterator_peekable() {
2275         let xs = ~[0u, 1, 2, 3, 4, 5];
2276         let mut it = xs.iter().map(|&x|x).peekable();
2277         assert_eq!(it.peek().unwrap(), &0);
2278         assert_eq!(it.next().unwrap(), 0);
2279         assert_eq!(it.next().unwrap(), 1);
2280         assert_eq!(it.next().unwrap(), 2);
2281         assert_eq!(it.peek().unwrap(), &3);
2282         assert_eq!(it.peek().unwrap(), &3);
2283         assert_eq!(it.next().unwrap(), 3);
2284         assert_eq!(it.next().unwrap(), 4);
2285         assert_eq!(it.peek().unwrap(), &5);
2286         assert_eq!(it.next().unwrap(), 5);
2287         assert!(it.peek().is_none());
2288         assert!(it.next().is_none());
2289     }
2290
2291     #[test]
2292     fn test_iterator_take_while() {
2293         let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
2294         let ys = [0u, 1, 2, 3, 5, 13];
2295         let mut it = xs.iter().take_while(|&x| *x < 15u);
2296         let mut i = 0;
2297         for &x in it {
2298             assert_eq!(x, ys[i]);
2299             i += 1;
2300         }
2301         assert_eq!(i, ys.len());
2302     }
2303
2304     #[test]
2305     fn test_iterator_skip_while() {
2306         let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
2307         let ys = [15, 16, 17, 19];
2308         let mut it = xs.iter().skip_while(|&x| *x < 15u);
2309         let mut i = 0;
2310         for &x in it {
2311             assert_eq!(x, ys[i]);
2312             i += 1;
2313         }
2314         assert_eq!(i, ys.len());
2315     }
2316
2317     #[test]
2318     fn test_iterator_skip() {
2319         let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
2320         let ys = [13, 15, 16, 17, 19, 20, 30];
2321         let mut it = xs.iter().skip(5);
2322         let mut i = 0;
2323         for &x in it {
2324             assert_eq!(x, ys[i]);
2325             i += 1;
2326         }
2327         assert_eq!(i, ys.len());
2328     }
2329
2330     #[test]
2331     fn test_iterator_take() {
2332         let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
2333         let ys = [0u, 1, 2, 3, 5];
2334         let mut it = xs.iter().take(5);
2335         let mut i = 0;
2336         for &x in it {
2337             assert_eq!(x, ys[i]);
2338             i += 1;
2339         }
2340         assert_eq!(i, ys.len());
2341     }
2342
2343     #[test]
2344     fn test_iterator_scan() {
2345         // test the type inference
2346         fn add(old: &mut int, new: &uint) -> Option<f64> {
2347             *old += *new as int;
2348             Some(*old as f64)
2349         }
2350         let xs = [0u, 1, 2, 3, 4];
2351         let ys = [0f64, 1.0, 3.0, 6.0, 10.0];
2352
2353         let mut it = xs.iter().scan(0, add);
2354         let mut i = 0;
2355         for x in it {
2356             assert_eq!(x, ys[i]);
2357             i += 1;
2358         }
2359         assert_eq!(i, ys.len());
2360     }
2361
2362     #[test]
2363     fn test_iterator_flat_map() {
2364         let xs = [0u, 3, 6];
2365         let ys = [0u, 1, 2, 3, 4, 5, 6, 7, 8];
2366         let mut it = xs.iter().flat_map(|&x| count(x, 1).take(3));
2367         let mut i = 0;
2368         for x in it {
2369             assert_eq!(x, ys[i]);
2370             i += 1;
2371         }
2372         assert_eq!(i, ys.len());
2373     }
2374
2375     #[test]
2376     fn test_inspect() {
2377         let xs = [1u, 2, 3, 4];
2378         let mut n = 0;
2379
2380         let ys = xs.iter()
2381                    .map(|&x| x)
2382                    .inspect(|_| n += 1)
2383                    .collect::<~[uint]>();
2384
2385         assert_eq!(n, xs.len());
2386         assert_eq!(xs, ys.as_slice());
2387     }
2388
2389     #[test]
2390     fn test_unfoldr() {
2391         fn count(st: &mut uint) -> Option<uint> {
2392             if *st < 10 {
2393                 let ret = Some(*st);
2394                 *st += 1;
2395                 ret
2396             } else {
2397                 None
2398             }
2399         }
2400
2401         let mut it = Unfold::new(0, count);
2402         let mut i = 0;
2403         for counted in it {
2404             assert_eq!(counted, i);
2405             i += 1;
2406         }
2407         assert_eq!(i, 10);
2408     }
2409
2410     #[test]
2411     fn test_cycle() {
2412         let cycle_len = 3;
2413         let it = count(0u, 1).take(cycle_len).cycle();
2414         assert_eq!(it.size_hint(), (uint::max_value, None));
2415         for (i, x) in it.take(100).enumerate() {
2416             assert_eq!(i % cycle_len, x);
2417         }
2418
2419         let mut it = count(0u, 1).take(0).cycle();
2420         assert_eq!(it.size_hint(), (0, Some(0)));
2421         assert_eq!(it.next(), None);
2422     }
2423
2424     #[test]
2425     fn test_iterator_nth() {
2426         let v = &[0, 1, 2, 3, 4];
2427         for i in range(0u, v.len()) {
2428             assert_eq!(v.iter().nth(i).unwrap(), &v[i]);
2429         }
2430     }
2431
2432     #[test]
2433     fn test_iterator_last() {
2434         let v = &[0, 1, 2, 3, 4];
2435         assert_eq!(v.iter().last().unwrap(), &4);
2436         assert_eq!(v.slice(0, 1).iter().last().unwrap(), &0);
2437     }
2438
2439     #[test]
2440     fn test_iterator_len() {
2441         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2442         assert_eq!(v.slice(0, 4).iter().len(), 4);
2443         assert_eq!(v.slice(0, 10).iter().len(), 10);
2444         assert_eq!(v.slice(0, 0).iter().len(), 0);
2445     }
2446
2447     #[test]
2448     fn test_iterator_sum() {
2449         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2450         assert_eq!(v.slice(0, 4).iter().map(|&x| x).sum(), 6);
2451         assert_eq!(v.iter().map(|&x| x).sum(), 55);
2452         assert_eq!(v.slice(0, 0).iter().map(|&x| x).sum(), 0);
2453     }
2454
2455     #[test]
2456     fn test_iterator_product() {
2457         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2458         assert_eq!(v.slice(0, 4).iter().map(|&x| x).product(), 0);
2459         assert_eq!(v.slice(1, 5).iter().map(|&x| x).product(), 24);
2460         assert_eq!(v.slice(0, 0).iter().map(|&x| x).product(), 1);
2461     }
2462
2463     #[test]
2464     fn test_iterator_max() {
2465         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2466         assert_eq!(v.slice(0, 4).iter().map(|&x| x).max(), Some(3));
2467         assert_eq!(v.iter().map(|&x| x).max(), Some(10));
2468         assert_eq!(v.slice(0, 0).iter().map(|&x| x).max(), None);
2469     }
2470
2471     #[test]
2472     fn test_iterator_min() {
2473         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2474         assert_eq!(v.slice(0, 4).iter().map(|&x| x).min(), Some(0));
2475         assert_eq!(v.iter().map(|&x| x).min(), Some(0));
2476         assert_eq!(v.slice(0, 0).iter().map(|&x| x).min(), None);
2477     }
2478
2479     #[test]
2480     fn test_iterator_size_hint() {
2481         let c = count(0, 1);
2482         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
2483         let v2 = &[10, 11, 12];
2484         let vi = v.iter();
2485
2486         assert_eq!(c.size_hint(), (uint::max_value, None));
2487         assert_eq!(vi.size_hint(), (10, Some(10)));
2488
2489         assert_eq!(c.take(5).size_hint(), (5, Some(5)));
2490         assert_eq!(c.skip(5).size_hint().second(), None);
2491         assert_eq!(c.take_while(|_| false).size_hint(), (0, None));
2492         assert_eq!(c.skip_while(|_| false).size_hint(), (0, None));
2493         assert_eq!(c.enumerate().size_hint(), (uint::max_value, None));
2494         assert_eq!(c.chain(vi.map(|&i| i)).size_hint(), (uint::max_value, None));
2495         assert_eq!(c.zip(vi).size_hint(), (10, Some(10)));
2496         assert_eq!(c.scan(0, |_,_| Some(0)).size_hint(), (0, None));
2497         assert_eq!(c.filter(|_| false).size_hint(), (0, None));
2498         assert_eq!(c.map(|_| 0).size_hint(), (uint::max_value, None));
2499         assert_eq!(c.filter_map(|_| Some(0)).size_hint(), (0, None));
2500
2501         assert_eq!(vi.take(5).size_hint(), (5, Some(5)));
2502         assert_eq!(vi.take(12).size_hint(), (10, Some(10)));
2503         assert_eq!(vi.skip(3).size_hint(), (7, Some(7)));
2504         assert_eq!(vi.skip(12).size_hint(), (0, Some(0)));
2505         assert_eq!(vi.take_while(|_| false).size_hint(), (0, Some(10)));
2506         assert_eq!(vi.skip_while(|_| false).size_hint(), (0, Some(10)));
2507         assert_eq!(vi.enumerate().size_hint(), (10, Some(10)));
2508         assert_eq!(vi.chain(v2.iter()).size_hint(), (13, Some(13)));
2509         assert_eq!(vi.zip(v2.iter()).size_hint(), (3, Some(3)));
2510         assert_eq!(vi.scan(0, |_,_| Some(0)).size_hint(), (0, Some(10)));
2511         assert_eq!(vi.filter(|_| false).size_hint(), (0, Some(10)));
2512         assert_eq!(vi.map(|i| i+1).size_hint(), (10, Some(10)));
2513         assert_eq!(vi.filter_map(|_| Some(0)).size_hint(), (0, Some(10)));
2514     }
2515
2516     #[test]
2517     fn test_collect() {
2518         let a = ~[1, 2, 3, 4, 5];
2519         let b: ~[int] = a.iter().map(|&x| x).collect();
2520         assert_eq!(a, b);
2521     }
2522
2523     #[test]
2524     fn test_all() {
2525         let v: ~&[int] = ~&[1, 2, 3, 4, 5];
2526         assert!(v.iter().all(|&x| x < 10));
2527         assert!(!v.iter().all(|&x| x.is_even()));
2528         assert!(!v.iter().all(|&x| x > 100));
2529         assert!(v.slice(0, 0).iter().all(|_| fail!()));
2530     }
2531
2532     #[test]
2533     fn test_any() {
2534         let v: ~&[int] = ~&[1, 2, 3, 4, 5];
2535         assert!(v.iter().any(|&x| x < 10));
2536         assert!(v.iter().any(|&x| x.is_even()));
2537         assert!(!v.iter().any(|&x| x > 100));
2538         assert!(!v.slice(0, 0).iter().any(|_| fail!()));
2539     }
2540
2541     #[test]
2542     fn test_find() {
2543         let v: &[int] = &[1, 3, 9, 27, 103, 14, 11];
2544         assert_eq!(*v.iter().find(|x| *x & 1 == 0).unwrap(), 14);
2545         assert_eq!(*v.iter().find(|x| *x % 3 == 0).unwrap(), 3);
2546         assert!(v.iter().find(|x| *x % 12 == 0).is_none());
2547     }
2548
2549     #[test]
2550     fn test_position() {
2551         let v = &[1, 3, 9, 27, 103, 14, 11];
2552         assert_eq!(v.iter().position(|x| *x & 1 == 0).unwrap(), 5);
2553         assert_eq!(v.iter().position(|x| *x % 3 == 0).unwrap(), 1);
2554         assert!(v.iter().position(|x| *x % 12 == 0).is_none());
2555     }
2556
2557     #[test]
2558     fn test_count() {
2559         let xs = &[1, 2, 2, 1, 5, 9, 0, 2];
2560         assert_eq!(xs.iter().count(|x| *x == 2), 3);
2561         assert_eq!(xs.iter().count(|x| *x == 5), 1);
2562         assert_eq!(xs.iter().count(|x| *x == 95), 0);
2563     }
2564
2565     #[test]
2566     fn test_max_by() {
2567         let xs: &[int] = &[-3, 0, 1, 5, -10];
2568         assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
2569     }
2570
2571     #[test]
2572     fn test_min_by() {
2573         let xs: &[int] = &[-3, 0, 1, 5, -10];
2574         assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
2575     }
2576
2577     #[test]
2578     fn test_by_ref() {
2579         let mut xs = range(0, 10);
2580         // sum the first five values
2581         let partial_sum = xs.by_ref().take(5).fold(0, |a, b| a + b);
2582         assert_eq!(partial_sum, 10);
2583         assert_eq!(xs.next(), Some(5));
2584     }
2585
2586     #[test]
2587     fn test_invert() {
2588         let xs = [2, 4, 6, 8, 10, 12, 14, 16];
2589         let mut it = xs.iter();
2590         it.next();
2591         it.next();
2592         assert_eq!(it.invert().map(|&x| x).collect::<~[int]>(), ~[16, 14, 12, 10, 8, 6]);
2593     }
2594
2595     #[test]
2596     fn test_double_ended_map() {
2597         let xs = [1, 2, 3, 4, 5, 6];
2598         let mut it = xs.iter().map(|&x| x * -1);
2599         assert_eq!(it.next(), Some(-1));
2600         assert_eq!(it.next(), Some(-2));
2601         assert_eq!(it.next_back(), Some(-6));
2602         assert_eq!(it.next_back(), Some(-5));
2603         assert_eq!(it.next(), Some(-3));
2604         assert_eq!(it.next_back(), Some(-4));
2605         assert_eq!(it.next(), None);
2606     }
2607
2608     #[test]
2609     fn test_double_ended_enumerate() {
2610         let xs = [1, 2, 3, 4, 5, 6];
2611         let mut it = xs.iter().map(|&x| x).enumerate();
2612         assert_eq!(it.next(), Some((0, 1)));
2613         assert_eq!(it.next(), Some((1, 2)));
2614         assert_eq!(it.next_back(), Some((5, 6)));
2615         assert_eq!(it.next_back(), Some((4, 5)));
2616         assert_eq!(it.next_back(), Some((3, 4)));
2617         assert_eq!(it.next_back(), Some((2, 3)));
2618         assert_eq!(it.next(), None);
2619     }
2620
2621     #[test]
2622     fn test_double_ended_zip() {
2623         let xs = [1, 2, 3, 4, 5, 6];
2624         let ys = [1, 2, 3, 7];
2625         let a = xs.iter().map(|&x| x);
2626         let b = ys.iter().map(|&x| x);
2627         let mut it = a.zip(b);
2628         assert_eq!(it.next(), Some((1, 1)));
2629         assert_eq!(it.next(), Some((2, 2)));
2630         assert_eq!(it.next_back(), Some((4, 7)));
2631         assert_eq!(it.next_back(), Some((3, 3)));
2632         assert_eq!(it.next(), None);
2633     }
2634
2635     #[test]
2636     fn test_double_ended_filter() {
2637         let xs = [1, 2, 3, 4, 5, 6];
2638         let mut it = xs.iter().filter(|&x| *x & 1 == 0);
2639         assert_eq!(it.next_back().unwrap(), &6);
2640         assert_eq!(it.next_back().unwrap(), &4);
2641         assert_eq!(it.next().unwrap(), &2);
2642         assert_eq!(it.next_back(), None);
2643     }
2644
2645     #[test]
2646     fn test_double_ended_filter_map() {
2647         let xs = [1, 2, 3, 4, 5, 6];
2648         let mut it = xs.iter().filter_map(|&x| if x & 1 == 0 { Some(x * 2) } else { None });
2649         assert_eq!(it.next_back().unwrap(), 12);
2650         assert_eq!(it.next_back().unwrap(), 8);
2651         assert_eq!(it.next().unwrap(), 4);
2652         assert_eq!(it.next_back(), None);
2653     }
2654
2655     #[test]
2656     fn test_double_ended_chain() {
2657         let xs = [1, 2, 3, 4, 5];
2658         let ys = ~[7, 9, 11];
2659         let mut it = xs.iter().chain(ys.iter()).invert();
2660         assert_eq!(it.next().unwrap(), &11)
2661         assert_eq!(it.next().unwrap(), &9)
2662         assert_eq!(it.next_back().unwrap(), &1)
2663         assert_eq!(it.next_back().unwrap(), &2)
2664         assert_eq!(it.next_back().unwrap(), &3)
2665         assert_eq!(it.next_back().unwrap(), &4)
2666         assert_eq!(it.next_back().unwrap(), &5)
2667         assert_eq!(it.next_back().unwrap(), &7)
2668         assert_eq!(it.next_back(), None)
2669     }
2670
2671     #[test]
2672     fn test_rposition() {
2673         fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' }
2674         fn g(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'd' }
2675         let v = ~[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
2676
2677         assert_eq!(v.iter().rposition(f), Some(3u));
2678         assert!(v.iter().rposition(g).is_none());
2679     }
2680
2681     #[test]
2682     #[should_fail]
2683     fn test_rposition_fail() {
2684         let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
2685         let mut i = 0;
2686         v.iter().rposition(|_elt| {
2687             if i == 2 {
2688                 fail!()
2689             }
2690             i += 1;
2691             false
2692         });
2693     }
2694
2695
2696     #[cfg(test)]
2697     fn check_randacc_iter<A: Eq, T: Clone + RandomAccessIterator<A>>(a: T, len: uint)
2698     {
2699         let mut b = a.clone();
2700         assert_eq!(len, b.indexable());
2701         let mut n = 0;
2702         for (i, elt) in a.enumerate() {
2703             assert_eq!(Some(elt), b.idx(i));
2704             n += 1;
2705         }
2706         assert_eq!(n, len);
2707         assert_eq!(None, b.idx(n));
2708         // call recursively to check after picking off an element
2709         if len > 0 {
2710             b.next();
2711             check_randacc_iter(b, len-1);
2712         }
2713     }
2714
2715
2716     #[test]
2717     fn test_double_ended_flat_map() {
2718         let u = [0u,1];
2719         let v = [5,6,7,8];
2720         let mut it = u.iter().flat_map(|x| v.slice(*x, v.len()).iter());
2721         assert_eq!(it.next_back().unwrap(), &8);
2722         assert_eq!(it.next().unwrap(),      &5);
2723         assert_eq!(it.next_back().unwrap(), &7);
2724         assert_eq!(it.next_back().unwrap(), &6);
2725         assert_eq!(it.next_back().unwrap(), &8);
2726         assert_eq!(it.next().unwrap(),      &6);
2727         assert_eq!(it.next_back().unwrap(), &7);
2728         assert_eq!(it.next_back(), None);
2729         assert_eq!(it.next(),      None);
2730         assert_eq!(it.next_back(), None);
2731     }
2732
2733     #[test]
2734     fn test_random_access_chain() {
2735         let xs = [1, 2, 3, 4, 5];
2736         let ys = ~[7, 9, 11];
2737         let mut it = xs.iter().chain(ys.iter());
2738         assert_eq!(it.idx(0).unwrap(), &1);
2739         assert_eq!(it.idx(5).unwrap(), &7);
2740         assert_eq!(it.idx(7).unwrap(), &11);
2741         assert!(it.idx(8).is_none());
2742
2743         it.next();
2744         it.next();
2745         it.next_back();
2746
2747         assert_eq!(it.idx(0).unwrap(), &3);
2748         assert_eq!(it.idx(4).unwrap(), &9);
2749         assert!(it.idx(6).is_none());
2750
2751         check_randacc_iter(it, xs.len() + ys.len() - 3);
2752     }
2753
2754     #[test]
2755     fn test_random_access_enumerate() {
2756         let xs = [1, 2, 3, 4, 5];
2757         check_randacc_iter(xs.iter().enumerate(), xs.len());
2758     }
2759
2760     #[test]
2761     fn test_random_access_invert() {
2762         let xs = [1, 2, 3, 4, 5];
2763         check_randacc_iter(xs.iter().invert(), xs.len());
2764         let mut it = xs.iter().invert();
2765         it.next();
2766         it.next_back();
2767         it.next();
2768         check_randacc_iter(it, xs.len() - 3);
2769     }
2770
2771     #[test]
2772     fn test_random_access_zip() {
2773         let xs = [1, 2, 3, 4, 5];
2774         let ys = [7, 9, 11];
2775         check_randacc_iter(xs.iter().zip(ys.iter()), cmp::min(xs.len(), ys.len()));
2776     }
2777
2778     #[test]
2779     fn test_random_access_take() {
2780         let xs = [1, 2, 3, 4, 5];
2781         let empty: &[int] = [];
2782         check_randacc_iter(xs.iter().take(3), 3);
2783         check_randacc_iter(xs.iter().take(20), xs.len());
2784         check_randacc_iter(xs.iter().take(0), 0);
2785         check_randacc_iter(empty.iter().take(2), 0);
2786     }
2787
2788     #[test]
2789     fn test_random_access_skip() {
2790         let xs = [1, 2, 3, 4, 5];
2791         let empty: &[int] = [];
2792         check_randacc_iter(xs.iter().skip(2), xs.len() - 2);
2793         check_randacc_iter(empty.iter().skip(2), 0);
2794     }
2795
2796     #[test]
2797     fn test_random_access_inspect() {
2798         let xs = [1, 2, 3, 4, 5];
2799
2800         // test .map and .inspect that don't implement Clone
2801         let it = xs.iter().inspect(|_| {});
2802         assert_eq!(xs.len(), it.indexable());
2803         for (i, elt) in xs.iter().enumerate() {
2804             assert_eq!(Some(elt), it.idx(i));
2805         }
2806
2807     }
2808
2809     #[test]
2810     fn test_random_access_map() {
2811         let xs = [1, 2, 3, 4, 5];
2812
2813         let it = xs.iter().map(|x| *x);
2814         assert_eq!(xs.len(), it.indexable());
2815         for (i, elt) in xs.iter().enumerate() {
2816             assert_eq!(Some(*elt), it.idx(i));
2817         }
2818     }
2819
2820     #[test]
2821     fn test_random_access_cycle() {
2822         let xs = [1, 2, 3, 4, 5];
2823         let empty: &[int] = [];
2824         check_randacc_iter(xs.iter().cycle().take(27), 27);
2825         check_randacc_iter(empty.iter().cycle(), 0);
2826     }
2827
2828     #[test]
2829     fn test_double_ended_range() {
2830         assert_eq!(range(11i, 14).invert().collect::<~[int]>(), ~[13i, 12, 11]);
2831         for _ in range(10i, 0).invert() {
2832             fail!("unreachable");
2833         }
2834
2835         assert_eq!(range(11u, 14).invert().collect::<~[uint]>(), ~[13u, 12, 11]);
2836         for _ in range(10u, 0).invert() {
2837             fail!("unreachable");
2838         }
2839     }
2840
2841     #[test]
2842     fn test_range() {
2843         /// A mock type to check Range when ToPrimitive returns None
2844         struct Foo;
2845
2846         impl ToPrimitive for Foo {
2847             fn to_i64(&self) -> Option<i64> { None }
2848             fn to_u64(&self) -> Option<u64> { None }
2849         }
2850
2851         impl Add<Foo, Foo> for Foo {
2852             fn add(&self, _: &Foo) -> Foo {
2853                 Foo
2854             }
2855         }
2856
2857         impl Ord for Foo {
2858             fn lt(&self, _: &Foo) -> bool {
2859                 false
2860             }
2861         }
2862
2863         impl Clone for Foo {
2864             fn clone(&self) -> Foo {
2865                 Foo
2866             }
2867         }
2868
2869         impl num::One for Foo {
2870             fn one() -> Foo {
2871                 Foo
2872             }
2873         }
2874
2875         assert_eq!(range(0i, 5).collect::<~[int]>(), ~[0i, 1, 2, 3, 4]);
2876         assert_eq!(range(-10i, -1).collect::<~[int]>(), ~[-10, -9, -8, -7, -6, -5, -4, -3, -2]);
2877         assert_eq!(range(0i, 5).invert().collect::<~[int]>(), ~[4, 3, 2, 1, 0]);
2878         assert_eq!(range(200, -5).collect::<~[int]>(), ~[]);
2879         assert_eq!(range(200, -5).invert().collect::<~[int]>(), ~[]);
2880         assert_eq!(range(200, 200).collect::<~[int]>(), ~[]);
2881         assert_eq!(range(200, 200).invert().collect::<~[int]>(), ~[]);
2882
2883         assert_eq!(range(0i, 100).size_hint(), (100, Some(100)));
2884         // this test is only meaningful when sizeof uint < sizeof u64
2885         assert_eq!(range(uint::max_value - 1, uint::max_value).size_hint(), (1, Some(1)));
2886         assert_eq!(range(-10i, -1).size_hint(), (9, Some(9)));
2887         assert_eq!(range(Foo, Foo).size_hint(), (0, None));
2888     }
2889
2890     #[test]
2891     fn test_range_inclusive() {
2892         assert_eq!(range_inclusive(0i, 5).collect::<~[int]>(), ~[0i, 1, 2, 3, 4, 5]);
2893         assert_eq!(range_inclusive(0i, 5).invert().collect::<~[int]>(), ~[5i, 4, 3, 2, 1, 0]);
2894         assert_eq!(range_inclusive(200, -5).collect::<~[int]>(), ~[]);
2895         assert_eq!(range_inclusive(200, -5).invert().collect::<~[int]>(), ~[]);
2896         assert_eq!(range_inclusive(200, 200).collect::<~[int]>(), ~[200]);
2897         assert_eq!(range_inclusive(200, 200).invert().collect::<~[int]>(), ~[200]);
2898     }
2899
2900     #[test]
2901     fn test_range_step() {
2902         assert_eq!(range_step(0i, 20, 5).collect::<~[int]>(), ~[0, 5, 10, 15]);
2903         assert_eq!(range_step(20i, 0, -5).collect::<~[int]>(), ~[20, 15, 10, 5]);
2904         assert_eq!(range_step(20i, 0, -6).collect::<~[int]>(), ~[20, 14, 8, 2]);
2905         assert_eq!(range_step(200u8, 255, 50).collect::<~[u8]>(), ~[200u8, 250]);
2906         assert_eq!(range_step(200, -5, 1).collect::<~[int]>(), ~[]);
2907         assert_eq!(range_step(200, 200, 1).collect::<~[int]>(), ~[]);
2908     }
2909
2910     #[test]
2911     fn test_range_step_inclusive() {
2912         assert_eq!(range_step_inclusive(0i, 20, 5).collect::<~[int]>(), ~[0, 5, 10, 15, 20]);
2913         assert_eq!(range_step_inclusive(20i, 0, -5).collect::<~[int]>(), ~[20, 15, 10, 5, 0]);
2914         assert_eq!(range_step_inclusive(20i, 0, -6).collect::<~[int]>(), ~[20, 14, 8, 2]);
2915         assert_eq!(range_step_inclusive(200u8, 255, 50).collect::<~[u8]>(), ~[200u8, 250]);
2916         assert_eq!(range_step_inclusive(200, -5, 1).collect::<~[int]>(), ~[]);
2917         assert_eq!(range_step_inclusive(200, 200, 1).collect::<~[int]>(), ~[200]);
2918     }
2919
2920     #[test]
2921     fn test_reverse() {
2922         let mut ys = [1, 2, 3, 4, 5];
2923         ys.mut_iter().reverse_();
2924         assert_eq!(ys, [5, 4, 3, 2, 1]);
2925     }
2926 }