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