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