src/libcore/iter.rs

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