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