src/libcore/iter.rs

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