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