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