src/libstd/iter.rs

   1 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 /*!
  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 guide](http://static.rust-lang.org/doc/master/guide-container.html) with
  63 the rest of the rust manuals.
  64
  65 */
  66
  67 use cmp;
  68 use num::{Zero, One, CheckedAdd, CheckedSub, Saturating, ToPrimitive, Int};
  69 use option::{Option, Some, None};
  70 use ops::{Add, Mul, Sub};
  71 use cmp::{Eq, Ord, TotalOrd};
  72 use clone::Clone;
  73 use uint;
  74 use mem;
  75
  76 /// Conversion from an `Iterator`
  77 pub trait FromIterator<A> {
  78     /// Build a container with elements from an external iterator.
  79     fn from_iter<T: Iterator<A>>(iterator: 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: 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: |A|: 'r -> 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: |&A|: 'r -> 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: |A|: 'r -> 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 an 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: |&A|: 'r -> 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: |&A|: 'r -> 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 fold.
 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: |&mut St, A|: 'r -> 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: |A|: 'r -> 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| println!("filtering {}", x))
 402     ///             .filter(|&x| x % 2 == 0)
 403     ///             .inspect(|&x| println!("{} made it through", x))
 404     ///             .sum();
 405     /// println!("{}", sum);
 406     /// ```
 407     #[inline]
 408     fn inspect<'r>(self, f: |&A|: 'r) -> 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_iter(self.by_ref())
 464     }
 465
 466     /// Loops through `n` iterations, returning the `n`th element of the
 467     /// iterator.
 468     ///
 469     /// # Example
 470     ///
 471     /// ```rust
 472     /// let a = [1, 2, 3, 4, 5];
 473     /// let mut it = a.iter();
 474     /// assert!(it.nth(2).unwrap() == &3);
 475     /// assert!(it.nth(2) == None);
 476     /// ```
 477     #[inline]
 478     fn nth(&mut self, mut n: uint) -> Option<A> {
 479         loop {
 480             match self.next() {
 481                 Some(x) => if n == 0 { return Some(x) },
 482                 None => return None
 483             }
 484             n -= 1;
 485         }
 486     }
 487
 488     /// Loops through the entire iterator, returning the last element of the
 489     /// iterator.
 490     ///
 491     /// # Example
 492     ///
 493     /// ```rust
 494     /// let a = [1, 2, 3, 4, 5];
 495     /// assert!(a.iter().last().unwrap() == &5);
 496     /// ```
 497     #[inline]
 498     fn last(&mut self) -> Option<A> {
 499         let mut last = None;
 500         for x in *self { last = Some(x); }
 501         last
 502     }
 503
 504     /// Performs a fold operation over the entire iterator, returning the
 505     /// eventual state at the end of the iteration.
 506     ///
 507     /// # Example
 508     ///
 509     /// ```rust
 510     /// let a = [1, 2, 3, 4, 5];
 511     /// assert!(a.iter().fold(0, |a, &b| a + b) == 15);
 512     /// ```
 513     #[inline]
 514     fn fold<B>(&mut self, init: B, f: |B, A| -> B) -> B {
 515         let mut accum = init;
 516         loop {
 517             match self.next() {
 518                 Some(x) => { accum = f(accum, x); }
 519                 None    => { break; }
 520             }
 521         }
 522         accum
 523     }
 524
 525     /// Counts the number of elements in this iterator.
 526     ///
 527     /// # Example
 528     ///
 529     /// ```rust
 530     /// let a = [1, 2, 3, 4, 5];
 531     /// let mut it = a.iter();
 532     /// assert!(it.len() == 5);
 533     /// assert!(it.len() == 0);
 534     /// ```
 535     #[inline]
 536     fn len(&mut self) -> uint {
 537         self.fold(0, |cnt, _x| cnt + 1)
 538     }
 539
 540     /// Tests whether the predicate holds true for all elements in the iterator.
 541     ///
 542     /// # Example
 543     ///
 544     /// ```rust
 545     /// let a = [1, 2, 3, 4, 5];
 546     /// assert!(a.iter().all(|x| *x > 0));
 547     /// assert!(!a.iter().all(|x| *x > 2));
 548     /// ```
 549     #[inline]
 550     fn all(&mut self, f: |A| -> bool) -> bool {
 551         for x in *self { if !f(x) { return false; } }
 552         true
 553     }
 554
 555     /// Tests whether any element of an iterator satisfies the specified
 556     /// predicate.
 557     ///
 558     /// # Example
 559     ///
 560     /// ```rust
 561     /// let a = [1, 2, 3, 4, 5];
 562     /// let mut it = a.iter();
 563     /// assert!(it.any(|x| *x == 3));
 564     /// assert!(!it.any(|x| *x == 3));
 565     /// ```
 566     #[inline]
 567     fn any(&mut self, f: |A| -> bool) -> bool {
 568         for x in *self { if f(x) { return true; } }
 569         false
 570     }
 571
 572     /// Return the first element satisfying the specified predicate
 573     #[inline]
 574     fn find(&mut self, predicate: |&A| -> bool) -> Option<A> {
 575         for x in *self {
 576             if predicate(&x) { return Some(x) }
 577         }
 578         None
 579     }
 580
 581     /// Return the index of the first element satisfying the specified predicate
 582     #[inline]
 583     fn position(&mut self, predicate: |A| -> bool) -> Option<uint> {
 584         let mut i = 0;
 585         for x in *self {
 586             if predicate(x) {
 587                 return Some(i);
 588             }
 589             i += 1;
 590         }
 591         None
 592     }
 593
 594     /// Count the number of elements satisfying the specified predicate
 595     #[inline]
 596     fn count(&mut self, predicate: |A| -> bool) -> uint {
 597         let mut i = 0;
 598         for x in *self {
 599             if predicate(x) { i += 1 }
 600         }
 601         i
 602     }
 603
 604     /// Return the element that gives the maximum value from the
 605     /// specified function.
 606     ///
 607     /// # Example
 608     ///
 609     /// ```rust
 610     /// let xs = [-3i, 0, 1, 5, -10];
 611     /// assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
 612     /// ```
 613     #[inline]
 614     fn max_by<B: TotalOrd>(&mut self, f: |&A| -> B) -> Option<A> {
 615         self.fold(None, |max: Option<(A, B)>, x| {
 616             let x_val = f(&x);
 617             match max {
 618                 None             => Some((x, x_val)),
 619                 Some((y, y_val)) => if x_val > y_val {
 620                     Some((x, x_val))
 621                 } else {
 622                     Some((y, y_val))
 623                 }
 624             }
 625         }).map(|(x, _)| x)
 626     }
 627
 628     /// Return the element that gives the minimum value from the
 629     /// specified function.
 630     ///
 631     /// # Example
 632     ///
 633     /// ```rust
 634     /// let xs = [-3i, 0, 1, 5, -10];
 635     /// assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
 636     /// ```
 637     #[inline]
 638     fn min_by<B: TotalOrd>(&mut self, f: |&A| -> B) -> Option<A> {
 639         self.fold(None, |min: Option<(A, B)>, x| {
 640             let x_val = f(&x);
 641             match min {
 642                 None             => Some((x, x_val)),
 643                 Some((y, y_val)) => if x_val < y_val {
 644                     Some((x, x_val))
 645                 } else {
 646                     Some((y, y_val))
 647                 }
 648             }
 649         }).map(|(x, _)| x)
 650     }
 651 }
 652
 653 /// A range iterator able to yield elements from both ends
 654 pub trait DoubleEndedIterator<A>: Iterator<A> {
 655     /// Yield an element from the end of the range, returning `None` if the range is empty.
 656     fn next_back(&mut self) -> Option<A>;
 657
 658     /// Change the direction of the iterator
 659     ///
 660     /// The flipped iterator swaps the ends on an iterator that can already
 661     /// be iterated from the front and from the back.
 662     ///
 663     ///
 664     /// If the iterator also implements RandomAccessIterator, the flipped
 665     /// iterator is also random access, with the indices starting at the back
 666     /// of the original iterator.
 667     ///
 668     /// Note: Random access with flipped indices still only applies to the first
 669     /// `uint::MAX` elements of the original iterator.
 670     #[inline]
 671     fn rev(self) -> Rev<Self> {
 672         Rev{iter: self}
 673     }
 674 }
 675
 676 /// A double-ended iterator yielding mutable references
 677 pub trait MutableDoubleEndedIterator {
 678     // FIXME: #5898: should be called `reverse`
 679     /// Use an iterator to reverse a container in-place
 680     fn reverse_(&mut self);
 681 }
 682
 683 impl<'a, A, T: DoubleEndedIterator<&'a mut A>> MutableDoubleEndedIterator for T {
 684     // FIXME: #5898: should be called `reverse`
 685     /// Use an iterator to reverse a container in-place
 686     fn reverse_(&mut self) {
 687         loop {
 688             match (self.next(), self.next_back()) {
 689                 (Some(x), Some(y)) => mem::swap(x, y),
 690                 _ => break
 691             }
 692         }
 693     }
 694 }
 695
 696
 697 /// An object implementing random access indexing by `uint`
 698 ///
 699 /// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`.
 700 pub trait RandomAccessIterator<A>: Iterator<A> {
 701     /// Return the number of indexable elements. At most `std::uint::MAX`
 702     /// elements are indexable, even if the iterator represents a longer range.
 703     fn indexable(&self) -> uint;
 704
 705     /// Return an element at an index
 706     fn idx(&mut self, index: uint) -> Option<A>;
 707 }
 708
 709 /// An iterator that knows its exact length
 710 ///
 711 /// This trait is a helper for iterators like the vector iterator, so that
 712 /// it can support double-ended enumeration.
 713 ///
 714 /// `Iterator::size_hint` *must* return the exact size of the iterator.
 715 /// Note that the size must fit in `uint`.
 716 pub trait ExactSize<A> : DoubleEndedIterator<A> {
 717     /// Return the index of the last element satisfying the specified predicate
 718     ///
 719     /// If no element matches, None is returned.
 720     #[inline]
 721     fn rposition(&mut self, predicate: |A| -> bool) -> Option<uint> {
 722         let (lower, upper) = self.size_hint();
 723         assert!(upper == Some(lower));
 724         let mut i = lower;
 725         loop {
 726             match self.next_back() {
 727                 None => break,
 728                 Some(x) => {
 729                     i = match i.checked_sub(&1) {
 730                         Some(x) => x,
 731                         None => fail!("rposition: incorrect ExactSize")
 732                     };
 733                     if predicate(x) {
 734                         return Some(i)
 735                     }
 736                 }
 737             }
 738         }
 739         None
 740     }
 741 }
 742
 743 // All adaptors that preserve the size of the wrapped iterator are fine
 744 // Adaptors that may overflow in `size_hint` are not, i.e. `Chain`.
 745 impl<A, T: ExactSize<A>> ExactSize<(uint, A)> for Enumerate<T> {}
 746 impl<'a, A, T: ExactSize<A>> ExactSize<A> for Inspect<'a, A, T> {}
 747 impl<A, T: ExactSize<A>> ExactSize<A> for Rev<T> {}
 748 impl<'a, A, B, T: ExactSize<A>> ExactSize<B> for Map<'a, A, B, T> {}
 749 impl<A, B, T: ExactSize<A>, U: ExactSize<B>> ExactSize<(A, B)> for Zip<T, U> {}
 750
 751 /// An double-ended iterator with the direction inverted
 752 #[deriving(Clone)]
 753 pub struct Rev<T> {
 754     iter: T
 755 }
 756
 757 impl<A, T: DoubleEndedIterator<A>> Iterator<A> for Rev<T> {
 758     #[inline]
 759     fn next(&mut self) -> Option<A> { self.iter.next_back() }
 760     #[inline]
 761     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 762 }
 763
 764 impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Rev<T> {
 765     #[inline]
 766     fn next_back(&mut self) -> Option<A> { self.iter.next() }
 767 }
 768
 769 impl<A, T: DoubleEndedIterator<A> + RandomAccessIterator<A>> RandomAccessIterator<A>
 770     for Rev<T> {
 771     #[inline]
 772     fn indexable(&self) -> uint { self.iter.indexable() }
 773     #[inline]
 774     fn idx(&mut self, index: uint) -> Option<A> {
 775         let amt = self.indexable();
 776         self.iter.idx(amt - index - 1)
 777     }
 778 }
 779
 780 /// A mutable reference to an iterator
 781 pub struct ByRef<'a, T> {
 782     iter: &'a mut T
 783 }
 784
 785 impl<'a, A, T: Iterator<A>> Iterator<A> for ByRef<'a, T> {
 786     #[inline]
 787     fn next(&mut self) -> Option<A> { self.iter.next() }
 788     #[inline]
 789     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 790 }
 791
 792 impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for ByRef<'a, T> {
 793     #[inline]
 794     fn next_back(&mut self) -> Option<A> { self.iter.next_back() }
 795 }
 796
 797 /// A trait for iterators over elements which can be added together
 798 pub trait AdditiveIterator<A> {
 799     /// Iterates over the entire iterator, summing up all the elements
 800     ///
 801     /// # Example
 802     ///
 803     /// ```rust
 804     /// use std::iter::AdditiveIterator;
 805     ///
 806     /// let a = [1, 2, 3, 4, 5];
 807     /// let mut it = a.iter().map(|&x| x);
 808     /// assert!(it.sum() == 15);
 809     /// ```
 810     fn sum(&mut self) -> A;
 811 }
 812
 813 impl<A: Add<A, A> + Zero, T: Iterator<A>> AdditiveIterator<A> for T {
 814     #[inline]
 815     fn sum(&mut self) -> A {
 816         let zero: A = Zero::zero();
 817         self.fold(zero, |s, x| s + x)
 818     }
 819 }
 820
 821 /// A trait for iterators over elements whose elements can be multiplied
 822 /// together.
 823 pub trait MultiplicativeIterator<A> {
 824     /// Iterates over the entire iterator, multiplying all the elements
 825     ///
 826     /// # Example
 827     ///
 828     /// ```rust
 829     /// use std::iter::{count, MultiplicativeIterator};
 830     ///
 831     /// fn factorial(n: uint) -> uint {
 832     ///     count(1u, 1).take_while(|&i| i <= n).product()
 833     /// }
 834     /// assert!(factorial(0) == 1);
 835     /// assert!(factorial(1) == 1);
 836     /// assert!(factorial(5) == 120);
 837     /// ```
 838     fn product(&mut self) -> A;
 839 }
 840
 841 impl<A: Mul<A, A> + One, T: Iterator<A>> MultiplicativeIterator<A> for T {
 842     #[inline]
 843     fn product(&mut self) -> A {
 844         let one: A = One::one();
 845         self.fold(one, |p, x| p * x)
 846     }
 847 }
 848
 849 /// A trait for iterators over elements which can be compared to one another.
 850 /// The type of each element must ascribe to the `Ord` trait.
 851 pub trait OrdIterator<A> {
 852     /// Consumes the entire iterator to return the maximum element.
 853     ///
 854     /// # Example
 855     ///
 856     /// ```rust
 857     /// let a = [1, 2, 3, 4, 5];
 858     /// assert!(a.iter().max().unwrap() == &5);
 859     /// ```
 860     fn max(&mut self) -> Option<A>;
 861
 862     /// Consumes the entire iterator to return the minimum element.
 863     ///
 864     /// # Example
 865     ///
 866     /// ```rust
 867     /// let a = [1, 2, 3, 4, 5];
 868     /// assert!(a.iter().min().unwrap() == &1);
 869     /// ```
 870     fn min(&mut self) -> Option<A>;
 871
 872     /// `min_max` finds the minimum and maximum elements in the iterator.
 873     ///
 874     /// The return type `MinMaxResult` is an enum of three variants:
 875     /// - `NoElements` if the iterator is empty.
 876     /// - `OneElement(x)` if the iterator has exactly one element.
 877     /// - `MinMax(x, y)` is returned otherwise, where `x <= y`. Two values are equal if and only if
 878     /// there is more than one element in the iterator and all elements are equal.
 879     ///
 880     /// On an iterator of length `n`, `min_max` does `1.5 * n` comparisons,
 881     /// and so faster than calling `min` and `max separately which does `2 * n` comparisons.
 882     ///
 883     /// # Example
 884     ///
 885     /// ```rust
 886     /// use std::iter::{NoElements, OneElement, MinMax};
 887     ///
 888     /// let v: [int, ..0] = [];
 889     /// assert_eq!(v.iter().min_max(), NoElements);
 890     ///
 891     /// let v = [1i];
 892     /// assert!(v.iter().min_max() == OneElement(&1));
 893     ///
 894     /// let v = [1i, 2, 3, 4, 5];
 895     /// assert!(v.iter().min_max() == MinMax(&1, &5));
 896     ///
 897     /// let v = [1i, 2, 3, 4, 5, 6];
 898     /// assert!(v.iter().min_max() == MinMax(&1, &6));
 899     ///
 900     /// let v = [1i, 1, 1, 1];
 901     /// assert!(v.iter().min_max() == MinMax(&1, &1));
 902     /// ```
 903     fn min_max(&mut self) -> MinMaxResult<A>;
 904 }
 905
 906 impl<A: TotalOrd, T: Iterator<A>> OrdIterator<A> for T {
 907     #[inline]
 908     fn max(&mut self) -> Option<A> {
 909         self.fold(None, |max, x| {
 910             match max {
 911                 None    => Some(x),
 912                 Some(y) => Some(cmp::max(x, y))
 913             }
 914         })
 915     }
 916
 917     #[inline]
 918     fn min(&mut self) -> Option<A> {
 919         self.fold(None, |min, x| {
 920             match min {
 921                 None    => Some(x),
 922                 Some(y) => Some(cmp::min(x, y))
 923             }
 924         })
 925     }
 926
 927     fn min_max(&mut self) -> MinMaxResult<A> {
 928         let (mut min, mut max) = match self.next() {
 929             None => return NoElements,
 930             Some(x) => {
 931                 match self.next() {
 932                     None => return OneElement(x),
 933                     Some(y) => if x < y {(x, y)} else {(y,x)}
 934                 }
 935             }
 936         };
 937
 938         loop {
 939             // `first` and `second` are the two next elements we want to look at.
 940             // We first compare `first` and `second` (#1). The smaller one is then compared to
 941             // current minimum (#2). The larger one is compared to current maximum (#3). This
 942             // way we do 3 comparisons for 2 elements.
 943             let first = match self.next() {
 944                 None => break,
 945                 Some(x) => x
 946             };
 947             let second = match self.next() {
 948                 None => {
 949                     if first < min {
 950                         min = first;
 951                     } else if first > max {
 952                         max = first;
 953                     }
 954                     break;
 955                 }
 956                 Some(x) => x
 957             };
 958             if first < second {
 959                 if first < min {min = first;}
 960                 if max < second {max = second;}
 961             } else {
 962                 if second < min {min = second;}
 963                 if max < first {max = first;}
 964             }
 965         }
 966
 967         MinMax(min, max)
 968     }
 969 }
 970
 971 /// `MinMaxResult` is an enum returned by `min_max`. See `OrdIterator::min_max` for more detail.
 972 #[deriving(Clone, Eq, Show)]
 973 pub enum MinMaxResult<T> {
 974     /// Empty iterator
 975     NoElements,
 976
 977     /// Iterator with one element, so the minimum and maximum are the same
 978     OneElement(T),
 979
 980     /// More than one element in the iterator, the first element is not larger than the second
 981     MinMax(T, T)
 982 }
 983
 984 impl<T: Clone> MinMaxResult<T> {
 985     /// `into_option` creates an `Option` of type `(T,T)`. The returned `Option` has variant
 986     /// `None` if and only if the `MinMaxResult` has variant `NoElements`. Otherwise variant
 987     /// `Some(x,y)` is returned where `x <= y`. If `MinMaxResult` has variant `OneElement(x)`,
 988     /// performing this operation will make one clone of `x`.
 989     ///
 990     /// # Example
 991     ///
 992     /// ```rust
 993     /// use std::iter::{NoElements, OneElement, MinMax, MinMaxResult};
 994     ///
 995     /// let r: MinMaxResult<int> = NoElements;
 996     /// assert_eq!(r.into_option(), None)
 997     ///
 998     /// let r = OneElement(1);
 999     /// assert_eq!(r.into_option(), Some((1,1)));
1000     ///
1001     /// let r = MinMax(1,2);
1002     /// assert_eq!(r.into_option(), Some((1,2)));
1003     /// ```
1004     pub fn into_option(self) -> Option<(T,T)> {
1005         match self {
1006             NoElements => None,
1007             OneElement(x) => Some((x.clone(), x)),
1008             MinMax(x, y) => Some((x, y))
1009         }
1010     }
1011 }
1012
1013 /// A trait for iterators that are cloneable.
1014 pub trait CloneableIterator {
1015     /// Repeats an iterator endlessly
1016     ///
1017     /// # Example
1018     ///
1019     /// ```rust
1020     /// use std::iter::{CloneableIterator, count};
1021     ///
1022     /// let a = count(1,1).take(1);
1023     /// let mut cy = a.cycle();
1024     /// assert_eq!(cy.next(), Some(1));
1025     /// assert_eq!(cy.next(), Some(1));
1026     /// ```
1027     fn cycle(self) -> Cycle<Self>;
1028 }
1029
1030 impl<A, T: Clone + Iterator<A>> CloneableIterator for T {
1031     #[inline]
1032     fn cycle(self) -> Cycle<T> {
1033         Cycle{orig: self.clone(), iter: self}
1034     }
1035 }
1036
1037 /// An iterator that repeats endlessly
1038 #[deriving(Clone)]
1039 pub struct Cycle<T> {
1040     orig: T,
1041     iter: T,
1042 }
1043
1044 impl<A, T: Clone + Iterator<A>> Iterator<A> for Cycle<T> {
1045     #[inline]
1046     fn next(&mut self) -> Option<A> {
1047         match self.iter.next() {
1048             None => { self.iter = self.orig.clone(); self.iter.next() }
1049             y => y
1050         }
1051     }
1052
1053     #[inline]
1054     fn size_hint(&self) -> (uint, Option<uint>) {
1055         // the cycle iterator is either empty or infinite
1056         match self.orig.size_hint() {
1057             sz @ (0, Some(0)) => sz,
1058             (0, _) => (0, None),
1059             _ => (uint::MAX, None)
1060         }
1061     }
1062 }
1063
1064 impl<A, T: Clone + RandomAccessIterator<A>> RandomAccessIterator<A> for Cycle<T> {
1065     #[inline]
1066     fn indexable(&self) -> uint {
1067         if self.orig.indexable() > 0 {
1068             uint::MAX
1069         } else {
1070             0
1071         }
1072     }
1073
1074     #[inline]
1075     fn idx(&mut self, index: uint) -> Option<A> {
1076         let liter = self.iter.indexable();
1077         let lorig = self.orig.indexable();
1078         if lorig == 0 {
1079             None
1080         } else if index < liter {
1081             self.iter.idx(index)
1082         } else {
1083             self.orig.idx((index - liter) % lorig)
1084         }
1085     }
1086 }
1087
1088 /// An iterator which strings two iterators together
1089 #[deriving(Clone)]
1090 pub struct Chain<T, U> {
1091     a: T,
1092     b: U,
1093     flag: bool
1094 }
1095
1096 impl<A, T: Iterator<A>, U: Iterator<A>> Iterator<A> for Chain<T, U> {
1097     #[inline]
1098     fn next(&mut self) -> Option<A> {
1099         if self.flag {
1100             self.b.next()
1101         } else {
1102             match self.a.next() {
1103                 Some(x) => return Some(x),
1104                 _ => ()
1105             }
1106             self.flag = true;
1107             self.b.next()
1108         }
1109     }
1110
1111     #[inline]
1112     fn size_hint(&self) -> (uint, Option<uint>) {
1113         let (a_lower, a_upper) = self.a.size_hint();
1114         let (b_lower, b_upper) = self.b.size_hint();
1115
1116         let lower = a_lower.saturating_add(b_lower);
1117
1118         let upper = match (a_upper, b_upper) {
1119             (Some(x), Some(y)) => x.checked_add(&y),
1120             _ => None
1121         };
1122
1123         (lower, upper)
1124     }
1125 }
1126
1127 impl<A, T: DoubleEndedIterator<A>, U: DoubleEndedIterator<A>> DoubleEndedIterator<A>
1128 for Chain<T, U> {
1129     #[inline]
1130     fn next_back(&mut self) -> Option<A> {
1131         match self.b.next_back() {
1132             Some(x) => Some(x),
1133             None => self.a.next_back()
1134         }
1135     }
1136 }
1137
1138 impl<A, T: RandomAccessIterator<A>, U: RandomAccessIterator<A>> RandomAccessIterator<A>
1139 for Chain<T, U> {
1140     #[inline]
1141     fn indexable(&self) -> uint {
1142         let (a, b) = (self.a.indexable(), self.b.indexable());
1143         a.saturating_add(b)
1144     }
1145
1146     #[inline]
1147     fn idx(&mut self, index: uint) -> Option<A> {
1148         let len = self.a.indexable();
1149         if index < len {
1150             self.a.idx(index)
1151         } else {
1152             self.b.idx(index - len)
1153         }
1154     }
1155 }
1156
1157 /// An iterator which iterates two other iterators simultaneously
1158 #[deriving(Clone)]
1159 pub struct Zip<T, U> {
1160     a: T,
1161     b: U
1162 }
1163
1164 impl<A, B, T: Iterator<A>, U: Iterator<B>> Iterator<(A, B)> for Zip<T, U> {
1165     #[inline]
1166     fn next(&mut self) -> Option<(A, B)> {
1167         match self.a.next() {
1168             None => None,
1169             Some(x) => match self.b.next() {
1170                 None => None,
1171                 Some(y) => Some((x, y))
1172             }
1173         }
1174     }
1175
1176     #[inline]
1177     fn size_hint(&self) -> (uint, Option<uint>) {
1178         let (a_lower, a_upper) = self.a.size_hint();
1179         let (b_lower, b_upper) = self.b.size_hint();
1180
1181         let lower = cmp::min(a_lower, b_lower);
1182
1183         let upper = match (a_upper, b_upper) {
1184             (Some(x), Some(y)) => Some(cmp::min(x,y)),
1185             (Some(x), None) => Some(x),
1186             (None, Some(y)) => Some(y),
1187             (None, None) => None
1188         };
1189
1190         (lower, upper)
1191     }
1192 }
1193
1194 impl<A, B, T: ExactSize<A>, U: ExactSize<B>> DoubleEndedIterator<(A, B)>
1195 for Zip<T, U> {
1196     #[inline]
1197     fn next_back(&mut self) -> Option<(A, B)> {
1198         let (a_sz, a_upper) = self.a.size_hint();
1199         let (b_sz, b_upper) = self.b.size_hint();
1200         assert!(a_upper == Some(a_sz));
1201         assert!(b_upper == Some(b_sz));
1202         if a_sz < b_sz {
1203             for _ in range(0, b_sz - a_sz) { self.b.next_back(); }
1204         } else if a_sz > b_sz {
1205             for _ in range(0, a_sz - b_sz) { self.a.next_back(); }
1206         }
1207         let (a_sz, _) = self.a.size_hint();
1208         let (b_sz, _) = self.b.size_hint();
1209         assert!(a_sz == b_sz);
1210         match (self.a.next_back(), self.b.next_back()) {
1211             (Some(x), Some(y)) => Some((x, y)),
1212             _ => None
1213         }
1214     }
1215 }
1216
1217 impl<A, B, T: RandomAccessIterator<A>, U: RandomAccessIterator<B>>
1218 RandomAccessIterator<(A, B)> for Zip<T, U> {
1219     #[inline]
1220     fn indexable(&self) -> uint {
1221         cmp::min(self.a.indexable(), self.b.indexable())
1222     }
1223
1224     #[inline]
1225     fn idx(&mut self, index: uint) -> Option<(A, B)> {
1226         match self.a.idx(index) {
1227             None => None,
1228             Some(x) => match self.b.idx(index) {
1229                 None => None,
1230                 Some(y) => Some((x, y))
1231             }
1232         }
1233     }
1234 }
1235
1236 /// An iterator which maps the values of `iter` with `f`
1237 pub struct Map<'a, A, B, T> {
1238     iter: T,
1239     f: |A|: 'a -> B
1240 }
1241
1242 impl<'a, A, B, T> Map<'a, A, B, T> {
1243     #[inline]
1244     fn do_map(&mut self, elt: Option<A>) -> Option<B> {
1245         match elt {
1246             Some(a) => Some((self.f)(a)),
1247             _ => None
1248         }
1249     }
1250 }
1251
1252 impl<'a, A, B, T: Iterator<A>> Iterator<B> for Map<'a, A, B, T> {
1253     #[inline]
1254     fn next(&mut self) -> Option<B> {
1255         let next = self.iter.next();
1256         self.do_map(next)
1257     }
1258
1259     #[inline]
1260     fn size_hint(&self) -> (uint, Option<uint>) {
1261         self.iter.size_hint()
1262     }
1263 }
1264
1265 impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B> for Map<'a, A, B, T> {
1266     #[inline]
1267     fn next_back(&mut self) -> Option<B> {
1268         let next = self.iter.next_back();
1269         self.do_map(next)
1270     }
1271 }
1272
1273 impl<'a, A, B, T: RandomAccessIterator<A>> RandomAccessIterator<B> for Map<'a, A, B, T> {
1274     #[inline]
1275     fn indexable(&self) -> uint {
1276         self.iter.indexable()
1277     }
1278
1279     #[inline]
1280     fn idx(&mut self, index: uint) -> Option<B> {
1281         let elt = self.iter.idx(index);
1282         self.do_map(elt)
1283     }
1284 }
1285
1286 /// An iterator which filters the elements of `iter` with `predicate`
1287 pub struct Filter<'a, A, T> {
1288     iter: T,
1289     predicate: |&A|: 'a -> bool
1290 }
1291
1292 impl<'a, A, T: Iterator<A>> Iterator<A> for Filter<'a, A, T> {
1293     #[inline]
1294     fn next(&mut self) -> Option<A> {
1295         for x in self.iter {
1296             if (self.predicate)(&x) {
1297                 return Some(x);
1298             } else {
1299                 continue
1300             }
1301         }
1302         None
1303     }
1304
1305     #[inline]
1306     fn size_hint(&self) -> (uint, Option<uint>) {
1307         let (_, upper) = self.iter.size_hint();
1308         (0, upper) // can't know a lower bound, due to the predicate
1309     }
1310 }
1311
1312 impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Filter<'a, A, T> {
1313     #[inline]
1314     fn next_back(&mut self) -> Option<A> {
1315         loop {
1316             match self.iter.next_back() {
1317                 None => return None,
1318                 Some(x) => {
1319                     if (self.predicate)(&x) {
1320                         return Some(x);
1321                     } else {
1322                         continue
1323                     }
1324                 }
1325             }
1326         }
1327     }
1328 }
1329
1330 /// An iterator which uses `f` to both filter and map elements from `iter`
1331 pub struct FilterMap<'a, A, B, T> {
1332     iter: T,
1333     f: |A|: 'a -> Option<B>
1334 }
1335
1336 impl<'a, A, B, T: Iterator<A>> Iterator<B> for FilterMap<'a, A, B, T> {
1337     #[inline]
1338     fn next(&mut self) -> Option<B> {
1339         for x in self.iter {
1340             match (self.f)(x) {
1341                 Some(y) => return Some(y),
1342                 None => ()
1343             }
1344         }
1345         None
1346     }
1347
1348     #[inline]
1349     fn size_hint(&self) -> (uint, Option<uint>) {
1350         let (_, upper) = self.iter.size_hint();
1351         (0, upper) // can't know a lower bound, due to the predicate
1352     }
1353 }
1354
1355 impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B>
1356 for FilterMap<'a, A, B, T> {
1357     #[inline]
1358     fn next_back(&mut self) -> Option<B> {
1359         loop {
1360             match self.iter.next_back() {
1361                 None => return None,
1362                 Some(x) => {
1363                     match (self.f)(x) {
1364                         Some(y) => return Some(y),
1365                         None => ()
1366                     }
1367                 }
1368             }
1369         }
1370     }
1371 }
1372
1373 /// An iterator which yields the current count and the element during iteration
1374 #[deriving(Clone)]
1375 pub struct Enumerate<T> {
1376     iter: T,
1377     count: uint
1378 }
1379
1380 impl<A, T: Iterator<A>> Iterator<(uint, A)> for Enumerate<T> {
1381     #[inline]
1382     fn next(&mut self) -> Option<(uint, A)> {
1383         match self.iter.next() {
1384             Some(a) => {
1385                 let ret = Some((self.count, a));
1386                 self.count += 1;
1387                 ret
1388             }
1389             _ => None
1390         }
1391     }
1392
1393     #[inline]
1394     fn size_hint(&self) -> (uint, Option<uint>) {
1395         self.iter.size_hint()
1396     }
1397 }
1398
1399 impl<A, T: ExactSize<A>> DoubleEndedIterator<(uint, A)> for Enumerate<T> {
1400     #[inline]
1401     fn next_back(&mut self) -> Option<(uint, A)> {
1402         match self.iter.next_back() {
1403             Some(a) => {
1404                 let (lower, upper) = self.iter.size_hint();
1405                 assert!(upper == Some(lower));
1406                 Some((self.count + lower, a))
1407             }
1408             _ => None
1409         }
1410     }
1411 }
1412
1413 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<(uint, A)> for Enumerate<T> {
1414     #[inline]
1415     fn indexable(&self) -> uint {
1416         self.iter.indexable()
1417     }
1418
1419     #[inline]
1420     fn idx(&mut self, index: uint) -> Option<(uint, A)> {
1421         match self.iter.idx(index) {
1422             Some(a) => Some((self.count + index, a)),
1423             _ => None,
1424         }
1425     }
1426 }
1427
1428 /// An iterator with a `peek()` that returns an optional reference to the next element.
1429 pub struct Peekable<A, T> {
1430     iter: T,
1431     peeked: Option<A>,
1432 }
1433
1434 impl<A, T: Iterator<A>> Iterator<A> for Peekable<A, T> {
1435     #[inline]
1436     fn next(&mut self) -> Option<A> {
1437         if self.peeked.is_some() { self.peeked.take() }
1438         else { self.iter.next() }
1439     }
1440
1441     #[inline]
1442     fn size_hint(&self) -> (uint, Option<uint>) {
1443         let (lo, hi) = self.iter.size_hint();
1444         if self.peeked.is_some() {
1445             let lo = lo.saturating_add(1);
1446             let hi = match hi {
1447                 Some(x) => x.checked_add(&1),
1448                 None => None
1449             };
1450             (lo, hi)
1451         } else {
1452             (lo, hi)
1453         }
1454     }
1455 }
1456
1457 impl<'a, A, T: Iterator<A>> Peekable<A, T> {
1458     /// Return a reference to the next element of the iterator with out advancing it,
1459     /// or None if the iterator is exhausted.
1460     #[inline]
1461     pub fn peek(&'a mut self) -> Option<&'a A> {
1462         if self.peeked.is_none() {
1463             self.peeked = self.iter.next();
1464         }
1465         match self.peeked {
1466             Some(ref value) => Some(value),
1467             None => None,
1468         }
1469     }
1470
1471     /// Check whether peekable iterator is empty or not.
1472     #[inline]
1473     pub fn is_empty(&mut self) -> bool {
1474         self.peek().is_none()
1475     }
1476 }
1477
1478 /// An iterator which rejects elements while `predicate` is true
1479 pub struct SkipWhile<'a, A, T> {
1480     iter: T,
1481     flag: bool,
1482     predicate: |&A|: 'a -> bool
1483 }
1484
1485 impl<'a, A, T: Iterator<A>> Iterator<A> for SkipWhile<'a, A, T> {
1486     #[inline]
1487     fn next(&mut self) -> Option<A> {
1488         let mut next = self.iter.next();
1489         if self.flag {
1490             next
1491         } else {
1492             loop {
1493                 match next {
1494                     Some(x) => {
1495                         if (self.predicate)(&x) {
1496                             next = self.iter.next();
1497                             continue
1498                         } else {
1499                             self.flag = true;
1500                             return Some(x)
1501                         }
1502                     }
1503                     None => return None
1504                 }
1505             }
1506         }
1507     }
1508
1509     #[inline]
1510     fn size_hint(&self) -> (uint, Option<uint>) {
1511         let (_, upper) = self.iter.size_hint();
1512         (0, upper) // can't know a lower bound, due to the predicate
1513     }
1514 }
1515
1516 /// An iterator which only accepts elements while `predicate` is true
1517 pub struct TakeWhile<'a, A, T> {
1518     iter: T,
1519     flag: bool,
1520     predicate: |&A|: 'a -> bool
1521 }
1522
1523 impl<'a, A, T: Iterator<A>> Iterator<A> for TakeWhile<'a, A, T> {
1524     #[inline]
1525     fn next(&mut self) -> Option<A> {
1526         if self.flag {
1527             None
1528         } else {
1529             match self.iter.next() {
1530                 Some(x) => {
1531                     if (self.predicate)(&x) {
1532                         Some(x)
1533                     } else {
1534                         self.flag = true;
1535                         None
1536                     }
1537                 }
1538                 None => None
1539             }
1540         }
1541     }
1542
1543     #[inline]
1544     fn size_hint(&self) -> (uint, Option<uint>) {
1545         let (_, upper) = self.iter.size_hint();
1546         (0, upper) // can't know a lower bound, due to the predicate
1547     }
1548 }
1549
1550 /// An iterator which skips over `n` elements of `iter`.
1551 #[deriving(Clone)]
1552 pub struct Skip<T> {
1553     iter: T,
1554     n: uint
1555 }
1556
1557 impl<A, T: Iterator<A>> Iterator<A> for Skip<T> {
1558     #[inline]
1559     fn next(&mut self) -> Option<A> {
1560         let mut next = self.iter.next();
1561         if self.n == 0 {
1562             next
1563         } else {
1564             let mut n = self.n;
1565             while n > 0 {
1566                 n -= 1;
1567                 match next {
1568                     Some(_) => {
1569                         next = self.iter.next();
1570                         continue
1571                     }
1572                     None => {
1573                         self.n = 0;
1574                         return None
1575                     }
1576                 }
1577             }
1578             self.n = 0;
1579             next
1580         }
1581     }
1582
1583     #[inline]
1584     fn size_hint(&self) -> (uint, Option<uint>) {
1585         let (lower, upper) = self.iter.size_hint();
1586
1587         let lower = lower.saturating_sub(self.n);
1588
1589         let upper = match upper {
1590             Some(x) => Some(x.saturating_sub(self.n)),
1591             None => None
1592         };
1593
1594         (lower, upper)
1595     }
1596 }
1597
1598 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Skip<T> {
1599     #[inline]
1600     fn indexable(&self) -> uint {
1601         self.iter.indexable().saturating_sub(self.n)
1602     }
1603
1604     #[inline]
1605     fn idx(&mut self, index: uint) -> Option<A> {
1606         if index >= self.indexable() {
1607             None
1608         } else {
1609             self.iter.idx(index + self.n)
1610         }
1611     }
1612 }
1613
1614 /// An iterator which only iterates over the first `n` iterations of `iter`.
1615 #[deriving(Clone)]
1616 pub struct Take<T> {
1617     iter: T,
1618     n: uint
1619 }
1620
1621 impl<A, T: Iterator<A>> Iterator<A> for Take<T> {
1622     #[inline]
1623     fn next(&mut self) -> Option<A> {
1624         if self.n != 0 {
1625             self.n -= 1;
1626             self.iter.next()
1627         } else {
1628             None
1629         }
1630     }
1631
1632     #[inline]
1633     fn size_hint(&self) -> (uint, Option<uint>) {
1634         let (lower, upper) = self.iter.size_hint();
1635
1636         let lower = cmp::min(lower, self.n);
1637
1638         let upper = match upper {
1639             Some(x) if x < self.n => Some(x),
1640             _ => Some(self.n)
1641         };
1642
1643         (lower, upper)
1644     }
1645 }
1646
1647 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Take<T> {
1648     #[inline]
1649     fn indexable(&self) -> uint {
1650         cmp::min(self.iter.indexable(), self.n)
1651     }
1652
1653     #[inline]
1654     fn idx(&mut self, index: uint) -> Option<A> {
1655         if index >= self.n {
1656             None
1657         } else {
1658             self.iter.idx(index)
1659         }
1660     }
1661 }
1662
1663
1664 /// An iterator to maintain state while iterating another iterator
1665 pub struct Scan<'a, A, B, T, St> {
1666     iter: T,
1667     f: |&mut St, A|: 'a -> Option<B>,
1668
1669     /// The current internal state to be passed to the closure next.
1670     pub state: St,
1671 }
1672
1673 impl<'a, A, B, T: Iterator<A>, St> Iterator<B> for Scan<'a, A, B, T, St> {
1674     #[inline]
1675     fn next(&mut self) -> Option<B> {
1676         self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
1677     }
1678
1679     #[inline]
1680     fn size_hint(&self) -> (uint, Option<uint>) {
1681         let (_, upper) = self.iter.size_hint();
1682         (0, upper) // can't know a lower bound, due to the scan function
1683     }
1684 }
1685
1686 /// An iterator that maps each element to an iterator,
1687 /// and yields the elements of the produced iterators
1688 ///
1689 pub struct FlatMap<'a, A, T, U> {
1690     iter: T,
1691     f: |A|: 'a -> U,
1692     frontiter: Option<U>,
1693     backiter: Option<U>,
1694 }
1695
1696 impl<'a, A, T: Iterator<A>, B, U: Iterator<B>> Iterator<B> for FlatMap<'a, A, T, U> {
1697     #[inline]
1698     fn next(&mut self) -> Option<B> {
1699         loop {
1700             for inner in self.frontiter.mut_iter() {
1701                 for x in *inner {
1702                     return Some(x)
1703                 }
1704             }
1705             match self.iter.next().map(|x| (self.f)(x)) {
1706                 None => return self.backiter.as_mut().and_then(|it| it.next()),
1707                 next => self.frontiter = next,
1708             }
1709         }
1710     }
1711
1712     #[inline]
1713     fn size_hint(&self) -> (uint, Option<uint>) {
1714         let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
1715         let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
1716         let lo = flo.saturating_add(blo);
1717         match (self.iter.size_hint(), fhi, bhi) {
1718             ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(&b)),
1719             _ => (lo, None)
1720         }
1721     }
1722 }
1723
1724 impl<'a,
1725      A, T: DoubleEndedIterator<A>,
1726      B, U: DoubleEndedIterator<B>> DoubleEndedIterator<B>
1727      for FlatMap<'a, A, T, U> {
1728     #[inline]
1729     fn next_back(&mut self) -> Option<B> {
1730         loop {
1731             for inner in self.backiter.mut_iter() {
1732                 match inner.next_back() {
1733                     None => (),
1734                     y => return y
1735                 }
1736             }
1737             match self.iter.next_back().map(|x| (self.f)(x)) {
1738                 None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
1739                 next => self.backiter = next,
1740             }
1741         }
1742     }
1743 }
1744
1745 /// An iterator that yields `None` forever after the underlying iterator
1746 /// yields `None` once.
1747 #[deriving(Clone)]
1748 pub struct Fuse<T> {
1749     iter: T,
1750     done: bool
1751 }
1752
1753 impl<A, T: Iterator<A>> Iterator<A> for Fuse<T> {
1754     #[inline]
1755     fn next(&mut self) -> Option<A> {
1756         if self.done {
1757             None
1758         } else {
1759             match self.iter.next() {
1760                 None => {
1761                     self.done = true;
1762                     None
1763                 }
1764                 x => x
1765             }
1766         }
1767     }
1768
1769     #[inline]
1770     fn size_hint(&self) -> (uint, Option<uint>) {
1771         if self.done {
1772             (0, Some(0))
1773         } else {
1774             self.iter.size_hint()
1775         }
1776     }
1777 }
1778
1779 impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Fuse<T> {
1780     #[inline]
1781     fn next_back(&mut self) -> Option<A> {
1782         if self.done {
1783             None
1784         } else {
1785             match self.iter.next_back() {
1786                 None => {
1787                     self.done = true;
1788                     None
1789                 }
1790                 x => x
1791             }
1792         }
1793     }
1794 }
1795
1796 // Allow RandomAccessIterators to be fused without affecting random-access behavior
1797 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Fuse<T> {
1798     #[inline]
1799     fn indexable(&self) -> uint {
1800         self.iter.indexable()
1801     }
1802
1803     #[inline]
1804     fn idx(&mut self, index: uint) -> Option<A> {
1805         self.iter.idx(index)
1806     }
1807 }
1808
1809 impl<T> Fuse<T> {
1810     /// Resets the fuse such that the next call to .next() or .next_back() will
1811     /// call the underlying iterator again even if it previously returned None.
1812     #[inline]
1813     pub fn reset_fuse(&mut self) {
1814         self.done = false
1815     }
1816 }
1817
1818 /// An iterator that calls a function with a reference to each
1819 /// element before yielding it.
1820 pub struct Inspect<'a, A, T> {
1821     iter: T,
1822     f: |&A|: 'a
1823 }
1824
1825 impl<'a, A, T> Inspect<'a, A, T> {
1826     #[inline]
1827     fn do_inspect(&mut self, elt: Option<A>) -> Option<A> {
1828         match elt {
1829             Some(ref a) => (self.f)(a),
1830             None => ()
1831         }
1832
1833         elt
1834     }
1835 }
1836
1837 impl<'a, A, T: Iterator<A>> Iterator<A> for Inspect<'a, A, T> {
1838     #[inline]
1839     fn next(&mut self) -> Option<A> {
1840         let next = self.iter.next();
1841         self.do_inspect(next)
1842     }
1843
1844     #[inline]
1845     fn size_hint(&self) -> (uint, Option<uint>) {
1846         self.iter.size_hint()
1847     }
1848 }
1849
1850 impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A>
1851 for Inspect<'a, A, T> {
1852     #[inline]
1853     fn next_back(&mut self) -> Option<A> {
1854         let next = self.iter.next_back();
1855         self.do_inspect(next)
1856     }
1857 }
1858
1859 impl<'a, A, T: RandomAccessIterator<A>> RandomAccessIterator<A>
1860 for Inspect<'a, A, T> {
1861     #[inline]
1862     fn indexable(&self) -> uint {
1863         self.iter.indexable()
1864     }
1865
1866     #[inline]
1867     fn idx(&mut self, index: uint) -> Option<A> {
1868         let element = self.iter.idx(index);
1869         self.do_inspect(element)
1870     }
1871 }
1872
1873 /// An iterator which just modifies the contained state throughout iteration.
1874 pub struct Unfold<'a, A, St> {
1875     f: |&mut St|: 'a -> Option<A>,
1876     /// Internal state that will be yielded on the next iteration
1877     pub state: St,
1878 }
1879
1880 impl<'a, A, St> Unfold<'a, A, St> {
1881     /// Creates a new iterator with the specified closure as the "iterator
1882     /// function" and an initial state to eventually pass to the iterator
1883     #[inline]
1884     pub fn new<'a>(initial_state: St, f: |&mut St|: 'a -> Option<A>)
1885                -> Unfold<'a, A, St> {
1886         Unfold {
1887             f: f,
1888             state: initial_state
1889         }
1890     }
1891 }
1892
1893 impl<'a, A, St> Iterator<A> for Unfold<'a, A, St> {
1894     #[inline]
1895     fn next(&mut self) -> Option<A> {
1896         (self.f)(&mut self.state)
1897     }
1898
1899     #[inline]
1900     fn size_hint(&self) -> (uint, Option<uint>) {
1901         // no possible known bounds at this point
1902         (0, None)
1903     }
1904 }
1905
1906 /// An infinite iterator starting at `start` and advancing by `step` with each
1907 /// iteration
1908 #[deriving(Clone)]
1909 pub struct Counter<A> {
1910     /// The current state the counter is at (next value to be yielded)
1911     state: A,
1912     /// The amount that this iterator is stepping by
1913     step: A,
1914 }
1915
1916 /// Creates a new counter with the specified start/step
1917 #[inline]
1918 pub fn count<A>(start: A, step: A) -> Counter<A> {
1919     Counter{state: start, step: step}
1920 }
1921
1922 impl<A: Add<A, A> + Clone> Iterator<A> for Counter<A> {
1923     #[inline]
1924     fn next(&mut self) -> Option<A> {
1925         let result = self.state.clone();
1926         self.state = self.state + self.step;
1927         Some(result)
1928     }
1929
1930     #[inline]
1931     fn size_hint(&self) -> (uint, Option<uint>) {
1932         (uint::MAX, None) // Too bad we can't specify an infinite lower bound
1933     }
1934 }
1935
1936 /// An iterator over the range [start, stop)
1937 #[deriving(Clone)]
1938 pub struct Range<A> {
1939     state: A,
1940     stop: A,
1941     one: A
1942 }
1943
1944 /// Return an iterator over the range [start, stop)
1945 #[inline]
1946 pub fn range<A: Add<A, A> + Ord + Clone + One>(start: A, stop: A) -> Range<A> {
1947     Range{state: start, stop: stop, one: One::one()}
1948 }
1949
1950 // FIXME: #10414: Unfortunate type bound
1951 impl<A: Add<A, A> + Ord + Clone + ToPrimitive> Iterator<A> for Range<A> {
1952     #[inline]
1953     fn next(&mut self) -> Option<A> {
1954         if self.state < self.stop {
1955             let result = self.state.clone();
1956             self.state = self.state + self.one;
1957             Some(result)
1958         } else {
1959             None
1960         }
1961     }
1962
1963     #[inline]
1964     fn size_hint(&self) -> (uint, Option<uint>) {
1965         // This first checks if the elements are representable as i64. If they aren't, try u64 (to
1966         // handle cases like range(huge, huger)). We don't use uint/int because the difference of
1967         // the i64/u64 might lie within their range.
1968         let bound = match self.state.to_i64() {
1969             Some(a) => {
1970                 let sz = self.stop.to_i64().map(|b| b.checked_sub(&a));
1971                 match sz {
1972                     Some(Some(bound)) => bound.to_uint(),
1973                     _ => None,
1974                 }
1975             },
1976             None => match self.state.to_u64() {
1977                 Some(a) => {
1978                     let sz = self.stop.to_u64().map(|b| b.checked_sub(&a));
1979                     match sz {
1980                         Some(Some(bound)) => bound.to_uint(),
1981                         _ => None
1982                     }
1983                 },
1984                 None => None
1985             }
1986         };
1987
1988         match bound {
1989             Some(b) => (b, Some(b)),
1990             // Standard fallback for unbounded/unrepresentable bounds
1991             None => (0, None)
1992         }
1993     }
1994 }
1995
1996 /// `Int` is required to ensure the range will be the same regardless of
1997 /// the direction it is consumed.
1998 impl<A: Int + Ord + Clone + ToPrimitive> DoubleEndedIterator<A> for Range<A> {
1999     #[inline]
2000     fn next_back(&mut self) -> Option<A> {
2001         if self.stop > self.state {
2002             self.stop = self.stop - self.one;
2003             Some(self.stop.clone())
2004         } else {
2005             None
2006         }
2007     }
2008 }
2009
2010 /// An iterator over the range [start, stop]
2011 #[deriving(Clone)]
2012 pub struct RangeInclusive<A> {
2013     range: Range<A>,
2014     done: bool,
2015 }
2016
2017 /// Return an iterator over the range [start, stop]
2018 #[inline]
2019 pub fn range_inclusive<A: Add<A, A> + Ord + Clone + One + ToPrimitive>(start: A, stop: A)
2020     -> RangeInclusive<A> {
2021     RangeInclusive{range: range(start, stop), done: false}
2022 }
2023
2024 impl<A: Add<A, A> + Ord + Clone + ToPrimitive> Iterator<A> for RangeInclusive<A> {
2025     #[inline]
2026     fn next(&mut self) -> Option<A> {
2027         match self.range.next() {
2028             Some(x) => Some(x),
2029             None => {
2030                 if !self.done && self.range.state == self.range.stop {
2031                     self.done = true;
2032                     Some(self.range.stop.clone())
2033                 } else {
2034                     None
2035                 }
2036             }
2037         }
2038     }
2039
2040     #[inline]
2041     fn size_hint(&self) -> (uint, Option<uint>) {
2042         let (lo, hi) = self.range.size_hint();
2043         if self.done {
2044             (lo, hi)
2045         } else {
2046             let lo = lo.saturating_add(1);
2047             let hi = match hi {
2048                 Some(x) => x.checked_add(&1),
2049                 None => None
2050             };
2051             (lo, hi)
2052         }
2053     }
2054 }
2055
2056 impl<A: Sub<A, A> + Int + Ord + Clone + ToPrimitive> DoubleEndedIterator<A>
2057     for RangeInclusive<A> {
2058     #[inline]
2059     fn next_back(&mut self) -> Option<A> {
2060         if self.range.stop > self.range.state {
2061             let result = self.range.stop.clone();
2062             self.range.stop = self.range.stop - self.range.one;
2063             Some(result)
2064         } else if !self.done && self.range.state == self.range.stop {
2065             self.done = true;
2066             Some(self.range.stop.clone())
2067         } else {
2068             None
2069         }
2070     }
2071 }
2072
2073 /// An iterator over the range [start, stop) by `step`. It handles overflow by stopping.
2074 #[deriving(Clone)]
2075 pub struct RangeStep<A> {
2076     state: A,
2077     stop: A,
2078     step: A,
2079     rev: bool,
2080 }
2081
2082 /// Return an iterator over the range [start, stop) by `step`. It handles overflow by stopping.
2083 #[inline]
2084 pub fn range_step<A: CheckedAdd + Ord + Clone + Zero>(start: A, stop: A, step: A) -> RangeStep<A> {
2085     let rev = step < Zero::zero();
2086     RangeStep{state: start, stop: stop, step: step, rev: rev}
2087 }
2088
2089 impl<A: CheckedAdd + Ord + Clone> Iterator<A> for RangeStep<A> {
2090     #[inline]
2091     fn next(&mut self) -> Option<A> {
2092         if (self.rev && self.state > self.stop) || (!self.rev && self.state < self.stop) {
2093             let result = self.state.clone();
2094             match self.state.checked_add(&self.step) {
2095                 Some(x) => self.state = x,
2096                 None => self.state = self.stop.clone()
2097             }
2098             Some(result)
2099         } else {
2100             None
2101         }
2102     }
2103 }
2104
2105 /// An iterator over the range [start, stop] by `step`. It handles overflow by stopping.
2106 #[deriving(Clone)]
2107 pub struct RangeStepInclusive<A> {
2108     state: A,
2109     stop: A,
2110     step: A,
2111     rev: bool,
2112     done: bool,
2113 }
2114
2115 /// Return an iterator over the range [start, stop] by `step`. It handles overflow by stopping.
2116 #[inline]
2117 pub fn range_step_inclusive<A: CheckedAdd + Ord + Clone + Zero>(start: A, stop: A,
2118                                                                 step: A) -> RangeStepInclusive<A> {
2119     let rev = step < Zero::zero();
2120     RangeStepInclusive{state: start, stop: stop, step: step, rev: rev, done: false}
2121 }
2122
2123 impl<A: CheckedAdd + Ord + Clone + Eq> Iterator<A> for RangeStepInclusive<A> {
2124     #[inline]
2125     fn next(&mut self) -> Option<A> {
2126         if !self.done && ((self.rev && self.state >= self.stop) ||
2127                           (!self.rev && self.state <= self.stop)) {
2128             let result = self.state.clone();
2129             match self.state.checked_add(&self.step) {
2130                 Some(x) => self.state = x,
2131                 None => self.done = true
2132             }
2133             Some(result)
2134         } else {
2135             None
2136         }
2137     }
2138 }
2139
2140 /// An iterator that repeats an element endlessly
2141 #[deriving(Clone)]
2142 pub struct Repeat<A> {
2143     element: A
2144 }
2145
2146 impl<A: Clone> Repeat<A> {
2147     /// Create a new `Repeat` that endlessly repeats the element `elt`.
2148     #[inline]
2149     pub fn new(elt: A) -> Repeat<A> {
2150         Repeat{element: elt}
2151     }
2152 }
2153
2154 impl<A: Clone> Iterator<A> for Repeat<A> {
2155     #[inline]
2156     fn next(&mut self) -> Option<A> { self.idx(0) }
2157     #[inline]
2158     fn size_hint(&self) -> (uint, Option<uint>) { (uint::MAX, None) }
2159 }
2160
2161 impl<A: Clone> DoubleEndedIterator<A> for Repeat<A> {
2162     #[inline]
2163     fn next_back(&mut self) -> Option<A> { self.idx(0) }
2164 }
2165
2166 impl<A: Clone> RandomAccessIterator<A> for Repeat<A> {
2167     #[inline]
2168     fn indexable(&self) -> uint { uint::MAX }
2169     #[inline]
2170     fn idx(&mut self, _: uint) -> Option<A> { Some(self.element.clone()) }
2171 }
2172
2173 /// Functions for lexicographical ordering of sequences.
2174 ///
2175 /// Lexicographical ordering through `<`, `<=`, `>=`, `>` requires
2176 /// that the elements implement both `Eq` and `Ord`.
2177 ///
2178 /// If two sequences are equal up until the point where one ends,
2179 /// the shorter sequence compares less.
2180 pub mod order {
2181     use cmp;
2182     use cmp::{TotalEq, TotalOrd, Ord, Eq};
2183     use option::{Some, None};
2184     use super::Iterator;
2185
2186     /// Compare `a` and `b` for equality using `TotalEq`
2187     pub fn equals<A: TotalEq, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2188         loop {
2189             match (a.next(), b.next()) {
2190                 (None, None) => return true,
2191                 (None, _) | (_, None) => return false,
2192                 (Some(x), Some(y)) => if x != y { return false },
2193             }
2194         }
2195     }
2196
2197     /// Order `a` and `b` lexicographically using `TotalOrd`
2198     pub fn cmp<A: TotalOrd, T: Iterator<A>>(mut a: T, mut b: T) -> cmp::Ordering {
2199         loop {
2200             match (a.next(), b.next()) {
2201                 (None, None) => return cmp::Equal,
2202                 (None, _   ) => return cmp::Less,
2203                 (_   , None) => return cmp::Greater,
2204                 (Some(x), Some(y)) => match x.cmp(&y) {
2205                     cmp::Equal => (),
2206                     non_eq => return non_eq,
2207                 },
2208             }
2209         }
2210     }
2211
2212     /// Compare `a` and `b` for equality (Using partial equality, `Eq`)
2213     pub fn eq<A: Eq, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2214         loop {
2215             match (a.next(), b.next()) {
2216                 (None, None) => return true,
2217                 (None, _) | (_, None) => return false,
2218                 (Some(x), Some(y)) => if !x.eq(&y) { return false },
2219             }
2220         }
2221     }
2222
2223     /// Compare `a` and `b` for nonequality (Using partial equality, `Eq`)
2224     pub fn ne<A: Eq, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2225         loop {
2226             match (a.next(), b.next()) {
2227                 (None, None) => return false,
2228                 (None, _) | (_, None) => return true,
2229                 (Some(x), Some(y)) => if x.ne(&y) { return true },
2230             }
2231         }
2232     }
2233
2234     /// Return `a` < `b` lexicographically (Using partial order, `Ord`)
2235     pub fn lt<A: Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2236         loop {
2237             match (a.next(), b.next()) {
2238                 (None, None) => return false,
2239                 (None, _   ) => return true,
2240                 (_   , None) => return false,
2241                 (Some(x), Some(y)) => if x.ne(&y) { return x.lt(&y) },
2242             }
2243         }
2244     }
2245
2246     /// Return `a` <= `b` lexicographically (Using partial order, `Ord`)
2247     pub fn le<A: Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2248         loop {
2249             match (a.next(), b.next()) {
2250                 (None, None) => return true,
2251                 (None, _   ) => return true,
2252                 (_   , None) => return false,
2253                 (Some(x), Some(y)) => if x.ne(&y) { return x.le(&y) },
2254             }
2255         }
2256     }
2257
2258     /// Return `a` > `b` lexicographically (Using partial order, `Ord`)
2259     pub fn gt<A: Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2260         loop {
2261             match (a.next(), b.next()) {
2262                 (None, None) => return false,
2263                 (None, _   ) => return false,
2264                 (_   , None) => return true,
2265                 (Some(x), Some(y)) => if x.ne(&y) { return x.gt(&y) },
2266             }
2267         }
2268     }
2269
2270     /// Return `a` >= `b` lexicographically (Using partial order, `Ord`)
2271     pub fn ge<A: Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2272         loop {
2273             match (a.next(), b.next()) {
2274                 (None, None) => return true,
2275                 (None, _   ) => return false,
2276                 (_   , None) => return true,
2277                 (Some(x), Some(y)) => if x.ne(&y) { return x.ge(&y) },
2278             }
2279         }
2280     }
2281
2282     #[test]
2283     fn test_lt() {
2284         use slice::ImmutableVector;
2285
2286         let empty: [int, ..0] = [];
2287         let xs = [1,2,3];
2288         let ys = [1,2,0];
2289
2290         assert!(!lt(xs.iter(), ys.iter()));
2291         assert!(!le(xs.iter(), ys.iter()));
2292         assert!( gt(xs.iter(), ys.iter()));
2293         assert!( ge(xs.iter(), ys.iter()));
2294
2295         assert!( lt(ys.iter(), xs.iter()));
2296         assert!( le(ys.iter(), xs.iter()));
2297         assert!(!gt(ys.iter(), xs.iter()));
2298         assert!(!ge(ys.iter(), xs.iter()));
2299
2300         assert!( lt(empty.iter(), xs.iter()));
2301         assert!( le(empty.iter(), xs.iter()));
2302         assert!(!gt(empty.iter(), xs.iter()));
2303         assert!(!ge(empty.iter(), xs.iter()));
2304
2305         // Sequence with NaN
2306         let u = [1.0, 2.0];
2307         let v = [0.0/0.0, 3.0];
2308
2309         assert!(!lt(u.iter(), v.iter()));
2310         assert!(!le(u.iter(), v.iter()));
2311         assert!(!gt(u.iter(), v.iter()));
2312         assert!(!ge(u.iter(), v.iter()));
2313
2314         let a = [0.0/0.0];
2315         let b = [1.0];
2316         let c = [2.0];
2317
2318         assert!(lt(a.iter(), b.iter()) == (a[0] <  b[0]));
2319         assert!(le(a.iter(), b.iter()) == (a[0] <= b[0]));
2320         assert!(gt(a.iter(), b.iter()) == (a[0] >  b[0]));
2321         assert!(ge(a.iter(), b.iter()) == (a[0] >= b[0]));
2322
2323         assert!(lt(c.iter(), b.iter()) == (c[0] <  b[0]));
2324         assert!(le(c.iter(), b.iter()) == (c[0] <= b[0]));
2325         assert!(gt(c.iter(), b.iter()) == (c[0] >  b[0]));
2326         assert!(ge(c.iter(), b.iter()) == (c[0] >= b[0]));
2327     }
2328 }
2329
2330 #[cfg(test)]
2331 mod tests {
2332     use super::*;
2333     use prelude::*;
2334
2335     use cmp;
2336     use uint;
2337     use num;
2338
2339     #[test]
2340     fn test_counter_from_iter() {
2341         let it = count(0, 5).take(10);
2342         let xs: ~[int] = FromIterator::from_iter(it);
2343         assert_eq!(xs, box [0, 5, 10, 15, 20, 25, 30, 35, 40, 45]);
2344     }
2345
2346     #[test]
2347     fn test_iterator_chain() {
2348         let xs = [0u, 1, 2, 3, 4, 5];
2349         let ys = [30u, 40, 50, 60];
2350         let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
2351         let mut it = xs.iter().chain(ys.iter());
2352         let mut i = 0;
2353         for &x in it {
2354             assert_eq!(x, expected[i]);
2355             i += 1;
2356         }
2357         assert_eq!(i, expected.len());
2358
2359         let ys = count(30u, 10).take(4);
2360         let mut it = xs.iter().map(|&x| x).chain(ys);
2361         let mut i = 0;
2362         for x in it {
2363             assert_eq!(x, expected[i]);
2364             i += 1;
2365         }
2366         assert_eq!(i, expected.len());
2367     }
2368
2369     #[test]
2370     fn test_filter_map() {
2371         let mut it = count(0u, 1u).take(10)
2372             .filter_map(|x| if x % 2 == 0 { Some(x*x) } else { None });
2373         assert_eq!(it.collect::<~[uint]>(), box [0*0, 2*2, 4*4, 6*6, 8*8]);
2374     }
2375
2376     #[test]
2377     fn test_iterator_enumerate() {
2378         let xs = [0u, 1, 2, 3, 4, 5];
2379         let mut it = xs.iter().enumerate();
2380         for (i, &x) in it {
2381             assert_eq!(i, x);
2382         }
2383     }
2384
2385     #[test]
2386     fn test_iterator_peekable() {
2387         let xs = box [0u, 1, 2, 3, 4, 5];
2388         let mut it = xs.iter().map(|&x|x).peekable();
2389         assert_eq!(it.peek().unwrap(), &0);
2390         assert_eq!(it.next().unwrap(), 0);
2391         assert_eq!(it.next().unwrap(), 1);
2392         assert_eq!(it.next().unwrap(), 2);
2393         assert_eq!(it.peek().unwrap(), &3);
2394         assert_eq!(it.peek().unwrap(), &3);
2395         assert_eq!(it.next().unwrap(), 3);
2396         assert_eq!(it.next().unwrap(), 4);
2397         assert_eq!(it.peek().unwrap(), &5);
2398         assert_eq!(it.next().unwrap(), 5);
2399         assert!(it.peek().is_none());
2400         assert!(it.next().is_none());
2401     }
2402
2403     #[test]
2404     fn test_iterator_take_while() {
2405         let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
2406         let ys = [0u, 1, 2, 3, 5, 13];
2407         let mut it = xs.iter().take_while(|&x| *x < 15u);
2408         let mut i = 0;
2409         for &x in it {
2410             assert_eq!(x, ys[i]);
2411             i += 1;
2412         }
2413         assert_eq!(i, ys.len());
2414     }
2415
2416     #[test]
2417     fn test_iterator_skip_while() {
2418         let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
2419         let ys = [15, 16, 17, 19];
2420         let mut it = xs.iter().skip_while(|&x| *x < 15u);
2421         let mut i = 0;
2422         for &x in it {
2423             assert_eq!(x, ys[i]);
2424             i += 1;
2425         }
2426         assert_eq!(i, ys.len());
2427     }
2428
2429     #[test]
2430     fn test_iterator_skip() {
2431         let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
2432         let ys = [13, 15, 16, 17, 19, 20, 30];
2433         let mut it = xs.iter().skip(5);
2434         let mut i = 0;
2435         for &x in it {
2436             assert_eq!(x, ys[i]);
2437             i += 1;
2438         }
2439         assert_eq!(i, ys.len());
2440     }
2441
2442     #[test]
2443     fn test_iterator_take() {
2444         let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
2445         let ys = [0u, 1, 2, 3, 5];
2446         let mut it = xs.iter().take(5);
2447         let mut i = 0;
2448         for &x in it {
2449             assert_eq!(x, ys[i]);
2450             i += 1;
2451         }
2452         assert_eq!(i, ys.len());
2453     }
2454
2455     #[test]
2456     fn test_iterator_scan() {
2457         // test the type inference
2458         fn add(old: &mut int, new: &uint) -> Option<f64> {
2459             *old += *new as int;
2460             Some(*old as f64)
2461         }
2462         let xs = [0u, 1, 2, 3, 4];
2463         let ys = [0f64, 1.0, 3.0, 6.0, 10.0];
2464
2465         let mut it = xs.iter().scan(0, add);
2466         let mut i = 0;
2467         for x in it {
2468             assert_eq!(x, ys[i]);
2469             i += 1;
2470         }
2471         assert_eq!(i, ys.len());
2472     }
2473
2474     #[test]
2475     fn test_iterator_flat_map() {
2476         let xs = [0u, 3, 6];
2477         let ys = [0u, 1, 2, 3, 4, 5, 6, 7, 8];
2478         let mut it = xs.iter().flat_map(|&x| count(x, 1).take(3));
2479         let mut i = 0;
2480         for x in it {
2481             assert_eq!(x, ys[i]);
2482             i += 1;
2483         }
2484         assert_eq!(i, ys.len());
2485     }
2486
2487     #[test]
2488     fn test_inspect() {
2489         let xs = [1u, 2, 3, 4];
2490         let mut n = 0;
2491
2492         let ys = xs.iter()
2493                    .map(|&x| x)
2494                    .inspect(|_| n += 1)
2495                    .collect::<~[uint]>();
2496
2497         assert_eq!(n, xs.len());
2498         assert_eq!(xs.as_slice(), ys.as_slice());
2499     }
2500
2501     #[test]
2502     fn test_unfoldr() {
2503         fn count(st: &mut uint) -> Option<uint> {
2504             if *st < 10 {
2505                 let ret = Some(*st);
2506                 *st += 1;
2507                 ret
2508             } else {
2509                 None
2510             }
2511         }
2512
2513         let mut it = Unfold::new(0, count);
2514         let mut i = 0;
2515         for counted in it {
2516             assert_eq!(counted, i);
2517             i += 1;
2518         }
2519         assert_eq!(i, 10);
2520     }
2521
2522     #[test]
2523     fn test_cycle() {
2524         let cycle_len = 3;
2525         let it = count(0u, 1).take(cycle_len).cycle();
2526         assert_eq!(it.size_hint(), (uint::MAX, None));
2527         for (i, x) in it.take(100).enumerate() {
2528             assert_eq!(i % cycle_len, x);
2529         }
2530
2531         let mut it = count(0u, 1).take(0).cycle();
2532         assert_eq!(it.size_hint(), (0, Some(0)));
2533         assert_eq!(it.next(), None);
2534     }
2535
2536     #[test]
2537     fn test_iterator_nth() {
2538         let v = &[0, 1, 2, 3, 4];
2539         for i in range(0u, v.len()) {
2540             assert_eq!(v.iter().nth(i).unwrap(), &v[i]);
2541         }
2542     }
2543
2544     #[test]
2545     fn test_iterator_last() {
2546         let v = &[0, 1, 2, 3, 4];
2547         assert_eq!(v.iter().last().unwrap(), &4);
2548         assert_eq!(v.slice(0, 1).iter().last().unwrap(), &0);
2549     }
2550
2551     #[test]
2552     fn test_iterator_len() {
2553         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2554         assert_eq!(v.slice(0, 4).iter().len(), 4);
2555         assert_eq!(v.slice(0, 10).iter().len(), 10);
2556         assert_eq!(v.slice(0, 0).iter().len(), 0);
2557     }
2558
2559     #[test]
2560     fn test_iterator_sum() {
2561         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2562         assert_eq!(v.slice(0, 4).iter().map(|&x| x).sum(), 6);
2563         assert_eq!(v.iter().map(|&x| x).sum(), 55);
2564         assert_eq!(v.slice(0, 0).iter().map(|&x| x).sum(), 0);
2565     }
2566
2567     #[test]
2568     fn test_iterator_product() {
2569         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2570         assert_eq!(v.slice(0, 4).iter().map(|&x| x).product(), 0);
2571         assert_eq!(v.slice(1, 5).iter().map(|&x| x).product(), 24);
2572         assert_eq!(v.slice(0, 0).iter().map(|&x| x).product(), 1);
2573     }
2574
2575     #[test]
2576     fn test_iterator_max() {
2577         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2578         assert_eq!(v.slice(0, 4).iter().map(|&x| x).max(), Some(3));
2579         assert_eq!(v.iter().map(|&x| x).max(), Some(10));
2580         assert_eq!(v.slice(0, 0).iter().map(|&x| x).max(), None);
2581     }
2582
2583     #[test]
2584     fn test_iterator_min() {
2585         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2586         assert_eq!(v.slice(0, 4).iter().map(|&x| x).min(), Some(0));
2587         assert_eq!(v.iter().map(|&x| x).min(), Some(0));
2588         assert_eq!(v.slice(0, 0).iter().map(|&x| x).min(), None);
2589     }
2590
2591     #[test]
2592     fn test_iterator_size_hint() {
2593         let c = count(0, 1);
2594         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
2595         let v2 = &[10, 11, 12];
2596         let vi = v.iter();
2597
2598         assert_eq!(c.size_hint(), (uint::MAX, None));
2599         assert_eq!(vi.size_hint(), (10, Some(10)));
2600
2601         assert_eq!(c.take(5).size_hint(), (5, Some(5)));
2602         assert_eq!(c.skip(5).size_hint().val1(), None);
2603         assert_eq!(c.take_while(|_| false).size_hint(), (0, None));
2604         assert_eq!(c.skip_while(|_| false).size_hint(), (0, None));
2605         assert_eq!(c.enumerate().size_hint(), (uint::MAX, None));
2606         assert_eq!(c.chain(vi.map(|&i| i)).size_hint(), (uint::MAX, None));
2607         assert_eq!(c.zip(vi).size_hint(), (10, Some(10)));
2608         assert_eq!(c.scan(0, |_,_| Some(0)).size_hint(), (0, None));
2609         assert_eq!(c.filter(|_| false).size_hint(), (0, None));
2610         assert_eq!(c.map(|_| 0).size_hint(), (uint::MAX, None));
2611         assert_eq!(c.filter_map(|_| Some(0)).size_hint(), (0, None));
2612
2613         assert_eq!(vi.take(5).size_hint(), (5, Some(5)));
2614         assert_eq!(vi.take(12).size_hint(), (10, Some(10)));
2615         assert_eq!(vi.skip(3).size_hint(), (7, Some(7)));
2616         assert_eq!(vi.skip(12).size_hint(), (0, Some(0)));
2617         assert_eq!(vi.take_while(|_| false).size_hint(), (0, Some(10)));
2618         assert_eq!(vi.skip_while(|_| false).size_hint(), (0, Some(10)));
2619         assert_eq!(vi.enumerate().size_hint(), (10, Some(10)));
2620         assert_eq!(vi.chain(v2.iter()).size_hint(), (13, Some(13)));
2621         assert_eq!(vi.zip(v2.iter()).size_hint(), (3, Some(3)));
2622         assert_eq!(vi.scan(0, |_,_| Some(0)).size_hint(), (0, Some(10)));
2623         assert_eq!(vi.filter(|_| false).size_hint(), (0, Some(10)));
2624         assert_eq!(vi.map(|i| i+1).size_hint(), (10, Some(10)));
2625         assert_eq!(vi.filter_map(|_| Some(0)).size_hint(), (0, Some(10)));
2626     }
2627
2628     #[test]
2629     fn test_collect() {
2630         let a = box [1, 2, 3, 4, 5];
2631         let b: ~[int] = a.iter().map(|&x| x).collect();
2632         assert_eq!(a, b);
2633     }
2634
2635     #[test]
2636     fn test_all() {
2637         let v: ~&[int] = box &[1, 2, 3, 4, 5];
2638         assert!(v.iter().all(|&x| x < 10));
2639         assert!(!v.iter().all(|&x| x % 2 == 0));
2640         assert!(!v.iter().all(|&x| x > 100));
2641         assert!(v.slice(0, 0).iter().all(|_| fail!()));
2642     }
2643
2644     #[test]
2645     fn test_any() {
2646         let v: ~&[int] = box &[1, 2, 3, 4, 5];
2647         assert!(v.iter().any(|&x| x < 10));
2648         assert!(v.iter().any(|&x| x % 2 == 0));
2649         assert!(!v.iter().any(|&x| x > 100));
2650         assert!(!v.slice(0, 0).iter().any(|_| fail!()));
2651     }
2652
2653     #[test]
2654     fn test_find() {
2655         let v: &[int] = &[1, 3, 9, 27, 103, 14, 11];
2656         assert_eq!(*v.iter().find(|x| *x & 1 == 0).unwrap(), 14);
2657         assert_eq!(*v.iter().find(|x| *x % 3 == 0).unwrap(), 3);
2658         assert!(v.iter().find(|x| *x % 12 == 0).is_none());
2659     }
2660
2661     #[test]
2662     fn test_position() {
2663         let v = &[1, 3, 9, 27, 103, 14, 11];
2664         assert_eq!(v.iter().position(|x| *x & 1 == 0).unwrap(), 5);
2665         assert_eq!(v.iter().position(|x| *x % 3 == 0).unwrap(), 1);
2666         assert!(v.iter().position(|x| *x % 12 == 0).is_none());
2667     }
2668
2669     #[test]
2670     fn test_count() {
2671         let xs = &[1, 2, 2, 1, 5, 9, 0, 2];
2672         assert_eq!(xs.iter().count(|x| *x == 2), 3);
2673         assert_eq!(xs.iter().count(|x| *x == 5), 1);
2674         assert_eq!(xs.iter().count(|x| *x == 95), 0);
2675     }
2676
2677     #[test]
2678     fn test_max_by() {
2679         let xs: &[int] = &[-3, 0, 1, 5, -10];
2680         assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
2681     }
2682
2683     #[test]
2684     fn test_min_by() {
2685         let xs: &[int] = &[-3, 0, 1, 5, -10];
2686         assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
2687     }
2688
2689     #[test]
2690     fn test_by_ref() {
2691         let mut xs = range(0, 10);
2692         // sum the first five values
2693         let partial_sum = xs.by_ref().take(5).fold(0, |a, b| a + b);
2694         assert_eq!(partial_sum, 10);
2695         assert_eq!(xs.next(), Some(5));
2696     }
2697
2698     #[test]
2699     fn test_rev() {
2700         let xs = [2, 4, 6, 8, 10, 12, 14, 16];
2701         let mut it = xs.iter();
2702         it.next();
2703         it.next();
2704         assert_eq!(it.rev().map(|&x| x).collect::<~[int]>(), box [16, 14, 12, 10, 8, 6]);
2705     }
2706
2707     #[test]
2708     fn test_double_ended_map() {
2709         let xs = [1, 2, 3, 4, 5, 6];
2710         let mut it = xs.iter().map(|&x| x * -1);
2711         assert_eq!(it.next(), Some(-1));
2712         assert_eq!(it.next(), Some(-2));
2713         assert_eq!(it.next_back(), Some(-6));
2714         assert_eq!(it.next_back(), Some(-5));
2715         assert_eq!(it.next(), Some(-3));
2716         assert_eq!(it.next_back(), Some(-4));
2717         assert_eq!(it.next(), None);
2718     }
2719
2720     #[test]
2721     fn test_double_ended_enumerate() {
2722         let xs = [1, 2, 3, 4, 5, 6];
2723         let mut it = xs.iter().map(|&x| x).enumerate();
2724         assert_eq!(it.next(), Some((0, 1)));
2725         assert_eq!(it.next(), Some((1, 2)));
2726         assert_eq!(it.next_back(), Some((5, 6)));
2727         assert_eq!(it.next_back(), Some((4, 5)));
2728         assert_eq!(it.next_back(), Some((3, 4)));
2729         assert_eq!(it.next_back(), Some((2, 3)));
2730         assert_eq!(it.next(), None);
2731     }
2732
2733     #[test]
2734     fn test_double_ended_zip() {
2735         let xs = [1, 2, 3, 4, 5, 6];
2736         let ys = [1, 2, 3, 7];
2737         let a = xs.iter().map(|&x| x);
2738         let b = ys.iter().map(|&x| x);
2739         let mut it = a.zip(b);
2740         assert_eq!(it.next(), Some((1, 1)));
2741         assert_eq!(it.next(), Some((2, 2)));
2742         assert_eq!(it.next_back(), Some((4, 7)));
2743         assert_eq!(it.next_back(), Some((3, 3)));
2744         assert_eq!(it.next(), None);
2745     }
2746
2747     #[test]
2748     fn test_double_ended_filter() {
2749         let xs = [1, 2, 3, 4, 5, 6];
2750         let mut it = xs.iter().filter(|&x| *x & 1 == 0);
2751         assert_eq!(it.next_back().unwrap(), &6);
2752         assert_eq!(it.next_back().unwrap(), &4);
2753         assert_eq!(it.next().unwrap(), &2);
2754         assert_eq!(it.next_back(), None);
2755     }
2756
2757     #[test]
2758     fn test_double_ended_filter_map() {
2759         let xs = [1, 2, 3, 4, 5, 6];
2760         let mut it = xs.iter().filter_map(|&x| if x & 1 == 0 { Some(x * 2) } else { None });
2761         assert_eq!(it.next_back().unwrap(), 12);
2762         assert_eq!(it.next_back().unwrap(), 8);
2763         assert_eq!(it.next().unwrap(), 4);
2764         assert_eq!(it.next_back(), None);
2765     }
2766
2767     #[test]
2768     fn test_double_ended_chain() {
2769         let xs = [1, 2, 3, 4, 5];
2770         let ys = box [7, 9, 11];
2771         let mut it = xs.iter().chain(ys.iter()).rev();
2772         assert_eq!(it.next().unwrap(), &11)
2773         assert_eq!(it.next().unwrap(), &9)
2774         assert_eq!(it.next_back().unwrap(), &1)
2775         assert_eq!(it.next_back().unwrap(), &2)
2776         assert_eq!(it.next_back().unwrap(), &3)
2777         assert_eq!(it.next_back().unwrap(), &4)
2778         assert_eq!(it.next_back().unwrap(), &5)
2779         assert_eq!(it.next_back().unwrap(), &7)
2780         assert_eq!(it.next_back(), None)
2781     }
2782
2783     #[test]
2784     fn test_rposition() {
2785         fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' }
2786         fn g(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'd' }
2787         let v = box [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
2788
2789         assert_eq!(v.iter().rposition(f), Some(3u));
2790         assert!(v.iter().rposition(g).is_none());
2791     }
2792
2793     #[test]
2794     #[should_fail]
2795     fn test_rposition_fail() {
2796         let v = [(box 0, @0), (box 0, @0), (box 0, @0), (box 0, @0)];
2797         let mut i = 0;
2798         v.iter().rposition(|_elt| {
2799             if i == 2 {
2800                 fail!()
2801             }
2802             i += 1;
2803             false
2804         });
2805     }
2806
2807
2808     #[cfg(test)]
2809     fn check_randacc_iter<A: Eq, T: Clone + RandomAccessIterator<A>>(a: T, len: uint)
2810     {
2811         let mut b = a.clone();
2812         assert_eq!(len, b.indexable());
2813         let mut n = 0;
2814         for (i, elt) in a.enumerate() {
2815             assert!(Some(elt) == b.idx(i));
2816             n += 1;
2817         }
2818         assert_eq!(n, len);
2819         assert!(None == b.idx(n));
2820         // call recursively to check after picking off an element
2821         if len > 0 {
2822             b.next();
2823             check_randacc_iter(b, len-1);
2824         }
2825     }
2826
2827
2828     #[test]
2829     fn test_double_ended_flat_map() {
2830         let u = [0u,1];
2831         let v = [5,6,7,8];
2832         let mut it = u.iter().flat_map(|x| v.slice(*x, v.len()).iter());
2833         assert_eq!(it.next_back().unwrap(), &8);
2834         assert_eq!(it.next().unwrap(),      &5);
2835         assert_eq!(it.next_back().unwrap(), &7);
2836         assert_eq!(it.next_back().unwrap(), &6);
2837         assert_eq!(it.next_back().unwrap(), &8);
2838         assert_eq!(it.next().unwrap(),      &6);
2839         assert_eq!(it.next_back().unwrap(), &7);
2840         assert_eq!(it.next_back(), None);
2841         assert_eq!(it.next(),      None);
2842         assert_eq!(it.next_back(), None);
2843     }
2844
2845     #[test]
2846     fn test_random_access_chain() {
2847         let xs = [1, 2, 3, 4, 5];
2848         let ys = box [7, 9, 11];
2849         let mut it = xs.iter().chain(ys.iter());
2850         assert_eq!(it.idx(0).unwrap(), &1);
2851         assert_eq!(it.idx(5).unwrap(), &7);
2852         assert_eq!(it.idx(7).unwrap(), &11);
2853         assert!(it.idx(8).is_none());
2854
2855         it.next();
2856         it.next();
2857         it.next_back();
2858
2859         assert_eq!(it.idx(0).unwrap(), &3);
2860         assert_eq!(it.idx(4).unwrap(), &9);
2861         assert!(it.idx(6).is_none());
2862
2863         check_randacc_iter(it, xs.len() + ys.len() - 3);
2864     }
2865
2866     #[test]
2867     fn test_random_access_enumerate() {
2868         let xs = [1, 2, 3, 4, 5];
2869         check_randacc_iter(xs.iter().enumerate(), xs.len());
2870     }
2871
2872     #[test]
2873     fn test_random_access_rev() {
2874         let xs = [1, 2, 3, 4, 5];
2875         check_randacc_iter(xs.iter().rev(), xs.len());
2876         let mut it = xs.iter().rev();
2877         it.next();
2878         it.next_back();
2879         it.next();
2880         check_randacc_iter(it, xs.len() - 3);
2881     }
2882
2883     #[test]
2884     fn test_random_access_zip() {
2885         let xs = [1, 2, 3, 4, 5];
2886         let ys = [7, 9, 11];
2887         check_randacc_iter(xs.iter().zip(ys.iter()), cmp::min(xs.len(), ys.len()));
2888     }
2889
2890     #[test]
2891     fn test_random_access_take() {
2892         let xs = [1, 2, 3, 4, 5];
2893         let empty: &[int] = [];
2894         check_randacc_iter(xs.iter().take(3), 3);
2895         check_randacc_iter(xs.iter().take(20), xs.len());
2896         check_randacc_iter(xs.iter().take(0), 0);
2897         check_randacc_iter(empty.iter().take(2), 0);
2898     }
2899
2900     #[test]
2901     fn test_random_access_skip() {
2902         let xs = [1, 2, 3, 4, 5];
2903         let empty: &[int] = [];
2904         check_randacc_iter(xs.iter().skip(2), xs.len() - 2);
2905         check_randacc_iter(empty.iter().skip(2), 0);
2906     }
2907
2908     #[test]
2909     fn test_random_access_inspect() {
2910         let xs = [1, 2, 3, 4, 5];
2911
2912         // test .map and .inspect that don't implement Clone
2913         let mut it = xs.iter().inspect(|_| {});
2914         assert_eq!(xs.len(), it.indexable());
2915         for (i, elt) in xs.iter().enumerate() {
2916             assert_eq!(Some(elt), it.idx(i));
2917         }
2918
2919     }
2920
2921     #[test]
2922     fn test_random_access_map() {
2923         let xs = [1, 2, 3, 4, 5];
2924
2925         let mut it = xs.iter().map(|x| *x);
2926         assert_eq!(xs.len(), it.indexable());
2927         for (i, elt) in xs.iter().enumerate() {
2928             assert_eq!(Some(*elt), it.idx(i));
2929         }
2930     }
2931
2932     #[test]
2933     fn test_random_access_cycle() {
2934         let xs = [1, 2, 3, 4, 5];
2935         let empty: &[int] = [];
2936         check_randacc_iter(xs.iter().cycle().take(27), 27);
2937         check_randacc_iter(empty.iter().cycle(), 0);
2938     }
2939
2940     #[test]
2941     fn test_double_ended_range() {
2942         assert_eq!(range(11i, 14).rev().collect::<~[int]>(), box [13i, 12, 11]);
2943         for _ in range(10i, 0).rev() {
2944             fail!("unreachable");
2945         }
2946
2947         assert_eq!(range(11u, 14).rev().collect::<~[uint]>(), box [13u, 12, 11]);
2948         for _ in range(10u, 0).rev() {
2949             fail!("unreachable");
2950         }
2951     }
2952
2953     #[test]
2954     fn test_range() {
2955         /// A mock type to check Range when ToPrimitive returns None
2956         struct Foo;
2957
2958         impl ToPrimitive for Foo {
2959             fn to_i64(&self) -> Option<i64> { None }
2960             fn to_u64(&self) -> Option<u64> { None }
2961         }
2962
2963         impl Add<Foo, Foo> for Foo {
2964             fn add(&self, _: &Foo) -> Foo {
2965                 Foo
2966             }
2967         }
2968
2969         impl Eq for Foo {
2970             fn eq(&self, _: &Foo) -> bool {
2971                 true
2972             }
2973         }
2974
2975         impl Ord for Foo {
2976             fn lt(&self, _: &Foo) -> bool {
2977                 false
2978             }
2979         }
2980
2981         impl Clone for Foo {
2982             fn clone(&self) -> Foo {
2983                 Foo
2984             }
2985         }
2986
2987         impl Mul<Foo, Foo> for Foo {
2988             fn mul(&self, _: &Foo) -> Foo {
2989                 Foo
2990             }
2991         }
2992
2993         impl num::One for Foo {
2994             fn one() -> Foo {
2995                 Foo
2996             }
2997         }
2998
2999         assert_eq!(range(0i, 5).collect::<~[int]>(), box [0i, 1, 2, 3, 4]);
3000         assert_eq!(range(-10i, -1).collect::<~[int]>(), box [-10, -9, -8, -7, -6, -5, -4, -3, -2]);
3001         assert_eq!(range(0i, 5).rev().collect::<~[int]>(), box [4, 3, 2, 1, 0]);
3002         assert_eq!(range(200, -5).collect::<~[int]>(), box []);
3003         assert_eq!(range(200, -5).rev().collect::<~[int]>(), box []);
3004         assert_eq!(range(200, 200).collect::<~[int]>(), box []);
3005         assert_eq!(range(200, 200).rev().collect::<~[int]>(), box []);
3006
3007         assert_eq!(range(0i, 100).size_hint(), (100, Some(100)));
3008         // this test is only meaningful when sizeof uint < sizeof u64
3009         assert_eq!(range(uint::MAX - 1, uint::MAX).size_hint(), (1, Some(1)));
3010         assert_eq!(range(-10i, -1).size_hint(), (9, Some(9)));
3011         assert_eq!(range(Foo, Foo).size_hint(), (0, None));
3012     }
3013
3014     #[test]
3015     fn test_range_inclusive() {
3016         assert_eq!(range_inclusive(0i, 5).collect::<~[int]>(), box [0i, 1, 2, 3, 4, 5]);
3017         assert_eq!(range_inclusive(0i, 5).rev().collect::<~[int]>(), box [5i, 4, 3, 2, 1, 0]);
3018         assert_eq!(range_inclusive(200, -5).collect::<~[int]>(), box []);
3019         assert_eq!(range_inclusive(200, -5).rev().collect::<~[int]>(), box []);
3020         assert_eq!(range_inclusive(200, 200).collect::<~[int]>(), box [200]);
3021         assert_eq!(range_inclusive(200, 200).rev().collect::<~[int]>(), box [200]);
3022     }
3023
3024     #[test]
3025     fn test_range_step() {
3026         assert_eq!(range_step(0i, 20, 5).collect::<~[int]>(), box [0, 5, 10, 15]);
3027         assert_eq!(range_step(20i, 0, -5).collect::<~[int]>(), box [20, 15, 10, 5]);
3028         assert_eq!(range_step(20i, 0, -6).collect::<~[int]>(), box [20, 14, 8, 2]);
3029         assert_eq!(range_step(200u8, 255, 50).collect::<~[u8]>(), box [200u8, 250]);
3030         assert_eq!(range_step(200, -5, 1).collect::<~[int]>(), box []);
3031         assert_eq!(range_step(200, 200, 1).collect::<~[int]>(), box []);
3032     }
3033
3034     #[test]
3035     fn test_range_step_inclusive() {
3036         assert_eq!(range_step_inclusive(0i, 20, 5).collect::<~[int]>(), box [0, 5, 10, 15, 20]);
3037         assert_eq!(range_step_inclusive(20i, 0, -5).collect::<~[int]>(), box [20, 15, 10, 5, 0]);
3038         assert_eq!(range_step_inclusive(20i, 0, -6).collect::<~[int]>(), box [20, 14, 8, 2]);
3039         assert_eq!(range_step_inclusive(200u8, 255, 50).collect::<~[u8]>(), box [200u8, 250]);
3040         assert_eq!(range_step_inclusive(200, -5, 1).collect::<~[int]>(), box []);
3041         assert_eq!(range_step_inclusive(200, 200, 1).collect::<~[int]>(), box [200]);
3042     }
3043
3044     #[test]
3045     fn test_reverse() {
3046         let mut ys = [1, 2, 3, 4, 5];
3047         ys.mut_iter().reverse_();
3048         assert!(ys == [5, 4, 3, 2, 1]);
3049     }
3050
3051     #[test]
3052     fn test_peekable_is_empty() {
3053         let a = [1];
3054         let mut it = a.iter().peekable();
3055         assert!( !it.is_empty() );
3056         it.next();
3057         assert!( it.is_empty() );
3058     }
3059
3060     #[test]
3061     fn test_min_max() {
3062         let v: [int, ..0] = [];
3063         assert_eq!(v.iter().min_max(), NoElements);
3064
3065         let v = [1i];
3066         assert!(v.iter().min_max() == OneElement(&1));
3067
3068         let v = [1i, 2, 3, 4, 5];
3069         assert!(v.iter().min_max() == MinMax(&1, &5));
3070
3071         let v = [1i, 2, 3, 4, 5, 6];
3072         assert!(v.iter().min_max() == MinMax(&1, &6));
3073
3074         let v = [1i, 1, 1, 1];
3075         assert!(v.iter().min_max() == MinMax(&1, &1));
3076     }
3077
3078     #[test]
3079     fn test_MinMaxResult() {
3080         let r: MinMaxResult<int> = NoElements;
3081         assert_eq!(r.into_option(), None)
3082
3083         let r = OneElement(1);
3084         assert_eq!(r.into_option(), Some((1,1)));
3085
3086         let r = MinMax(1,2);
3087         assert_eq!(r.into_option(), Some((1,2)));
3088     }
3089 }