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