(index<- )        ./libstd/iter.rs

    git branch:    * master           c7553ea auto merge of #13609 : richo/rust/str-type-vim, r=alexcrichton
    modified:    Wed Apr  9 17:27:02 2014

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

libstd/iter.rs:1235:57-1235:57 -struct- definition:
/// An iterator which maps the values of `iter` with `f`
pub struct Map<'a, A, B, T> {
    iter: T,
references:- 15
747: impl<A, T: ExactSize<A>> ExactSize<A> for Rev<T> {}
748: impl<'a, A, B, T: ExactSize<A>> ExactSize<B> for Map<'a, A, B, T> {}
749: impl<A, B, T: ExactSize<A>, U: ExactSize<B>> ExactSize<(A, B)> for Zip<T, U> {}
--
1264: impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B> for Map<'a, A, B, T> {
1265:     #[inline]
--
1272: impl<'a, A, B, T: RandomAccessIterator<A>> RandomAccessIterator<B> for Map<'a, A, B, T> {
1273:     #[inline]
libstd/path/posix.rs:
37: /// Iterator that yields components of a Path in reverse as Option<&str>
38: pub type RevStrComponents<'a> = Map<'a, &'a [u8], Option<&'a str>,
39:                                           RevComponents<'a>>;
libstd/path/windows.rs:
43: /// Iterator that yields successive components of a Path as &[u8]
44: pub type Components<'a> = Map<'a, Option<&'a str>, &'a [u8],
45:                                     StrComponents<'a>>;
46: /// Iterator that yields components of a Path in reverse as &[u8]
47: pub type RevComponents<'a> = Map<'a, Option<&'a str>, &'a [u8],
48:                                        RevStrComponents<'a>>;
libstd/str.rs:
390: pub type AnyLines<'a> =
391:     Map<'a, &'a str, &'a str, CharSplits<'a, char>>;
libstd/iter.rs:
1241: impl<'a, A, B, T> Map<'a, A, B, T> {
1242:     #[inline]


libstd/iter.rs:1942:10-1942:10 -fn- definition:
pub fn range<A: Add<A, A> + Ord + Clone + One>(start: A, stop: A) -> Range<A> {
    Range{state: start, stop: stop, one: One::one()}
}
references:- 19
1203:         } else if a_sz > b_sz {
1204:             for _ in range(0, a_sz - b_sz) { self.a.next_back(); }
1205:         }
--
2017:     -> RangeInclusive<A> {
2018:     RangeInclusive{range: range(start, stop), done: false}
2019: }
libstd/sync/deque.rs:
338:         // back into the pool.
339:         for i in range(t, b) {
340:             let _: T = unsafe { (*a).get(i) };
libstd/c_str.rs:
368: fn check_for_null(v: &[u8], buf: *mut libc::c_char) {
369:     for i in range(0, v.len()) {
370:         unsafe {
libstd/io/tempfile.rs:
43:         for _ in range(0u, 1000) {
44:             let filename = format!("rs-{}-{}-{}",
libstd/fmt/mod.rs:
1067:         let len = self.fill.encode_utf8(fill);
1068:         for _ in range(0, padding) {
1069:             try!(self.buf.write(fill.slice_to(len)));
libstd/slice.rs:
1279:         // start <= i < len;
1280:         for i in range(start, cmp::min(start + insertion, len)) {
1281:             // j satisfies: start <= j <= i;
libstd/vec.rs:
1188:             for i in range(0u, len) {
1189:                 if !f(&v[i]) {
--
1214:         self.reserve_additional(n);
1215:         for i in range(0u, n) {
1216:             self.push(f(i));
libstd/str.rs:
566:         let mut swapped = false;
567:         for j in range(1, len-i) {
568:             let class_a = *comb[j-1].ref1();
--
2663:         let mut ret = StrBuf::with_capacity(nn * self.len());
2664:         for _ in range(0, nn) {
2665:             ret.push_str(*self);
libstd/strbuf.rs:
109:         buf.reserve(size);
110:         for _ in range(1, length) {
111:             buf.push_char(ch)
--
124:     pub fn grow(&mut self, count: uint, ch: char) {
125:         for _ in range(0, count) {
126:             self.push_char(ch)
libstd/ptr.rs:
298:     //let start_ptr = *arr;
299:     for e in range(0, len) {
300:         let n = arr.offset(e as int);
libstd/sync/deque.rs:
381:         let mut buf = Buffer::new(self.log_size + delta);
382:         for i in range(t, b) {
383:             buf.put(i, self.get(i));


libstd/iter.rs:779:39-779:39 -struct- definition:
/// A mutable reference to an iterator
pub struct ByRef<'a, T> {
    iter: &'a mut T
references:- 4
784: impl<'a, A, T: Iterator<A>> Iterator<A> for ByRef<'a, T> {
785:     #[inline]
--
791: impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for ByRef<'a, T> {
792:     #[inline]


libstd/iter.rs:1514:70-1514:70 -struct- definition:
/// An iterator which only accepts elements while `predicate` is true
pub struct TakeWhile<'a, A, T> {
    iter: T,
references:- 3
270:     fn take_while<'r>(self, predicate: |&A|: 'r -> bool) -> TakeWhile<'r, A, Self> {
271:         TakeWhile{iter: self, flag: false, predicate: predicate}
272:     }
--
1521: impl<'a, A, T: Iterator<A>> Iterator<A> for TakeWhile<'a, A, T> {
1522:     #[inline]


libstd/iter.rs:1870:78-1870:78 -struct- definition:
/// An iterator which just modifies the contained state throughout iteration.
pub struct Unfold<'a, A, St> {
    f: |&mut St|: 'a -> Option<A>,
references:- 4
1890: impl<'a, A, St> Iterator<A> for Unfold<'a, A, St> {
1891:     #[inline]


libstd/iter.rs:2008:19-2008:19 -struct- definition:
pub struct RangeInclusive<A> {
    range: Range<A>,
    done: bool,
references:- 8
2007: /// An iterator over the range [start, stop]
2009: pub struct RangeInclusive<A> {
--
2021: impl<A: Add<A, A> + Ord + Clone + ToPrimitive> Iterator<A> for RangeInclusive<A> {
2022:     #[inline]
--
2053: impl<A: Sub<A, A> + Int + Ord + Clone + ToPrimitive> DoubleEndedIterator<A>
2054:     for RangeInclusive<A> {
2055:     #[inline]


libstd/iter.rs:2080:10-2080:10 -fn- definition:
pub fn range_step<A: CheckedAdd + Ord + Clone + Zero>(start: A, stop: A, step: A) -> RangeStep<A> {
    let rev = step < Zero::zero();
    RangeStep{state: start, stop: stop, step: step, rev: rev}
references:- 3
libstd/char.rs:
356:     };
357:     for offset in range_step::<i32>(4 * (pad - 1), -1, -4) {
358:         unsafe {
libstd/slice.rs:
1317:         // 0 <= start <= len.
1318:         for start in range_step(0, len, 2 * width) {
1319:             // manipulate pointers directly for speed (rather than


libstd/iter.rs:1284:70-1284:70 -struct- definition:
/// An iterator which filters the elements of `iter` with `predicate`
pub struct Filter<'a, A, T> {
    iter: T,
references:- 5
175:     #[inline]
176:     fn filter<'r>(self, predicate: |&A|: 'r -> bool) -> Filter<'r, A, Self> {
177:         Filter{iter: self, predicate: predicate}
--
1290: impl<'a, A, T: Iterator<A>> Iterator<A> for Filter<'a, A, T> {
1291:     #[inline]
--
1310: impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Filter<'a, A, T> {
1311:     #[inline]
libstd/str.rs:
386: pub type Words<'a> =
387:     Filter<'a, &'a str, CharSplits<'a, extern "Rust" fn(char) -> bool>>;
libstd/iter.rs:
176:     fn filter<'r>(self, predicate: |&A|: 'r -> bool) -> Filter<'r, A, Self> {
177:         Filter{iter: self, predicate: predicate}
178:     }


libstd/iter.rs:1905:19-1905:19 -struct- definition:
pub struct Counter<A> {
    /// The current state the counter is at (next value to be yielded)
    state: A,
references:- 7
1904: /// iteration
1906: pub struct Counter<A> {
--
1915: pub fn count<A>(start: A, step: A) -> Counter<A> {
1916:     Counter{state: start, step: step}
--
1919: impl<A: Add<A, A> + Clone> Iterator<A> for Counter<A> {
1920:     #[inline]


libstd/iter.rs:2138:19-2138:19 -struct- definition:
pub struct Repeat<A> {
    element: A
}
references:- 10
2137: /// An iterator that repeats an element endlessly
2139: pub struct Repeat<A> {
--
2151: impl<A: Clone> Iterator<A> for Repeat<A> {
2152:     #[inline]
--
2158: impl<A: Clone> DoubleEndedIterator<A> for Repeat<A> {
2159:     #[inline]
--
2163: impl<A: Clone> RandomAccessIterator<A> for Repeat<A> {
2164:     #[inline]


libstd/iter.rs:97:10-97:10 -trait- definition:
/// else.
pub trait Iterator<A> {
    /// Advance the iterator and return the next value. Return `None` when the end is reached.
references:- 125
libstd/option.rs:
libstd/result.rs:
libstd/comm/mod.rs:
libstd/comm/select.rs:
libstd/c_str.rs:
libstd/io/mod.rs:
libstd/io/extensions.rs:
libstd/io/fs.rs:
libstd/io/util.rs:
libstd/fmt/parse.rs:
libstd/rt/task.rs:
libstd/slice.rs:
libstd/vec.rs:
libstd/str.rs:
libstd/strbuf.rs:
libstd/iter.rs:


libstd/iter.rs:715:43-715:43 -trait- definition:
/// Note that the size must fit in `uint`.
pub trait ExactSize<A> : DoubleEndedIterator<A> {
    /// Return the index of the last element satisfying the specified predicate
references:- 17
745: impl<A, T: ExactSize<A>> ExactSize<(uint, A)> for Enumerate<T> {}
746: impl<'a, A, T: ExactSize<A>> ExactSize<A> for Inspect<'a, A, T> {}
747: impl<A, T: ExactSize<A>> ExactSize<A> for Rev<T> {}
748: impl<'a, A, B, T: ExactSize<A>> ExactSize<B> for Map<'a, A, B, T> {}
749: impl<A, B, T: ExactSize<A>, U: ExactSize<B>> ExactSize<(A, B)> for Zip<T, U> {}
--
1397: impl<A, T: ExactSize<A>> DoubleEndedIterator<(uint, A)> for Enumerate<T> {
1398:     #[inline]
libstd/option.rs:
563: impl<A> ExactSize<A> for Item<A> {}
libstd/slice.rs:
2112: impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
2113: impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
libstd/iter.rs:
1193: impl<A, B, T: ExactSize<A>, U: ExactSize<B>> DoubleEndedIterator<(A, B)>
1194: for Zip<T, U> {


libstd/iter.rs:699:83-699:83 -trait- definition:
/// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`.
pub trait RandomAccessIterator<A>: Iterator<A> {
    /// Return the number of indexable elements. At most `std::uint::MAX`
references:- 25
1063: impl<A, T: Clone + RandomAccessIterator<A>> RandomAccessIterator<A> for Cycle<T> {
1064:     #[inline]
--
1645: impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Take<T> {
1646:     #[inline]
--
2163: impl<A: Clone> RandomAccessIterator<A> for Repeat<A> {
2164:     #[inline]
libstd/slice.rs:
485: impl<'a, T> RandomAccessIterator<&'a [T]> for Chunks<'a, T> {
486:     #[inline]
--
2090: impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
2091:     #[inline]
libstd/iter.rs:
1272: impl<'a, A, B, T: RandomAccessIterator<A>> RandomAccessIterator<B> for Map<'a, A, B, T> {
1273:     #[inline]


libstd/iter.rs:1662:67-1662:67 -struct- definition:
/// An iterator to maintain state while iterating another iterator
pub struct Scan<'a, A, B, T, St> {
    iter: T,
references:- 3
330:     fn scan<'r, St, B>(self, initial_state: St, f: |&mut St, A|: 'r -> Option<B>)
331:         -> Scan<'r, A, B, Self, St> {
332:         Scan{iter: self, f: f, state: initial_state}
--
1671: impl<'a, A, B, T: Iterator<A>, St> Iterator<B> for Scan<'a, A, B, T, St> {
1672:     #[inline]


libstd/iter.rs:76:34-76:34 -trait- definition:
/// Conversion from an `Iterator`
pub trait FromIterator<A> {
    /// Build a container with elements from an external iterator.
references:- 9
82: /// A type growable from an `Iterator` implementation
83: pub trait Extendable<A>: FromIterator<A> {
84:     /// Extend a container with the elements yielded by an iterator
--
461:     #[inline]
462:     fn collect<B: FromIterator<A>>(&mut self) -> B {
463:         FromIterator::from_iter(self.by_ref())
libstd/option.rs:
584: pub fn collect<T, Iter: Iterator<Option<T>>, V: FromIterator<T>>(iter: Iter) -> Option<V> {
585:     // FIXME(#11084): This should be twice as fast once this bug is closed.
libstd/result.rs:
566: pub fn collect<T, E, Iter: Iterator<Result<T, E>>, V: FromIterator<T>>(iter: Iter) -> Result<V, E> {
567:     // FIXME(#11084): This should be twice as fast once this bug is closed.
libstd/slice.rs:
2280: impl<A> FromIterator<A> for ~[A] {
2281:     fn from_iter<T: Iterator<A>>(mut iterator: T) -> ~[A] {
libstd/vec.rs:
351: impl<T> FromIterator<T> for Vec<T> {
352:     fn from_iter<I:Iterator<T>>(mut iterator: I) -> Vec<T> {
libstd/str.rs:
2763: impl FromIterator<char> for ~str {
2764:     #[inline]
libstd/strbuf.rs:
248: impl FromIterator<char> for StrBuf {
249:     fn from_iter<I:Iterator<char>>(iterator: I) -> StrBuf {
libstd/iter.rs:
78:     /// Build a container with elements from an external iterator.
79:     fn from_iter<T: Iterator<A>>(iterator: T) -> Self;
80: }


libstd/iter.rs:1745:19-1745:19 -struct- definition:
pub struct Fuse<T> {
    iter: T,
    done: bool
references:- 10
1744: /// yields `None` once.
1746: pub struct Fuse<T> {
--
1794: // Allow RandomAccessIterators to be fused without affecting random-access behavior
1795: impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Fuse<T> {
1796:     #[inline]
--
1807: impl<T> Fuse<T> {
1808:     /// Resets the fuse such that the next call to .next() or .next_back() will


libstd/iter.rs:1372:19-1372:19 -struct- definition:
pub struct Enumerate<T> {
    iter: T,
    count: uint
references:- 10
744: // Adaptors that may overflow in `size_hint` are not, i.e. `Chain`.
745: impl<A, T: ExactSize<A>> ExactSize<(uint, A)> for Enumerate<T> {}
746: impl<'a, A, T: ExactSize<A>> ExactSize<A> for Inspect<'a, A, T> {}
--
1371: /// An iterator which yields the current count and the element during iteration
1373: pub struct Enumerate<T> {
--
1378: impl<A, T: Iterator<A>> Iterator<(uint, A)> for Enumerate<T> {
1379:     #[inline]
--
1397: impl<A, T: ExactSize<A>> DoubleEndedIterator<(uint, A)> for Enumerate<T> {
1398:     #[inline]
--
1411: impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<(uint, A)> for Enumerate<T> {
1412:     #[inline]


libstd/iter.rs:1686:4-1686:4 -struct- definition:
///
pub struct FlatMap<'a, A, T, U> {
    iter: T,
references:- 4
354:     fn flat_map<'r, B, U: Iterator<B>>(self, f: |A|: 'r -> U)
355:         -> FlatMap<'r, A, Self, U> {
356:         FlatMap{iter: self, f: f, frontiter: None, backiter: None }
--
1724:      B, U: DoubleEndedIterator<B>> DoubleEndedIterator<B>
1725:      for FlatMap<'a, A, T, U> {
1726:     #[inline]


libstd/iter.rs:971:29-971:29 -enum- definition:
pub enum MinMaxResult<T> {
    /// Empty iterator
    NoElements,
references:- 9
970: /// `MinMaxResult` is an enum returned by `min_max`. See `OrdIterator::min_max` for more detail.
972: pub enum MinMaxResult<T> {
--
983: impl<T: Clone> MinMaxResult<T> {
984:     /// `into_option` creates an `Option` of type `(T,T)`. The returned `Option` has variant


libstd/iter.rs:1426:88-1426:88 -struct- definition:
/// An iterator with a `peek()` that returns an optional reference to the next element.
pub struct Peekable<A, T> {
    iter: T,
references:- 4
1455: impl<'a, A, T: Iterator<A>> Peekable<A, T> {
1456:     /// Return a reference to the next element of the iterator with out advancing it,


libstd/iter.rs:2071:19-2071:19 -struct- definition:
pub struct RangeStep<A> {
    state: A,
    stop: A,
references:- 7
2082:     let rev = step < Zero::zero();
2083:     RangeStep{state: start, stop: stop, step: step, rev: rev}
2084: }
2086: impl<A: CheckedAdd + Ord + Clone> Iterator<A> for RangeStep<A> {
2087:     #[inline]


libstd/iter.rs:2103:19-2103:19 -struct- definition:
pub struct RangeStepInclusive<A> {
    state: A,
    stop: A,
references:- 7
2102: /// An iterator over the range [start, stop] by `step`. It handles overflow by stopping.
2104: pub struct RangeStepInclusive<A> {
--
2114: pub fn range_step_inclusive<A: CheckedAdd + Ord + Clone + Zero>(start: A, stop: A,
2115:                                                                 step: A) -> RangeStepInclusive<A> {
2116:     let rev = step < Zero::zero();
2117:     RangeStepInclusive{state: start, stop: stop, step: step, rev: rev, done: false}
2118: }
2120: impl<A: CheckedAdd + Ord + Clone + Eq> Iterator<A> for RangeStepInclusive<A> {
2121:     #[inline]


libstd/iter.rs:752:19-752:19 -struct- definition:
pub struct Rev<T> {
    iter: T
}
references:- 18
764: impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Rev<T> {
765:     #[inline]
--
769: impl<A, T: DoubleEndedIterator<A> + RandomAccessIterator<A>> RandomAccessIterator<A>
770:     for Rev<T> {
771:     #[inline]
libstd/path/windows.rs:
39: /// every component in WindowsPath is guaranteed to be Some.
40: pub type RevStrComponents<'a> = Rev<Map<'a, &'a str, Option<&'a str>,
41:                                                  CharSplits<'a, char>>>;
libstd/slice.rs:
2119: iterator!{struct MutItems -> *mut T, &'a mut T}
2120: pub type RevMutItems<'a, T> = Rev<MutItems<'a, T>>;
--
2277: /// An iterator that moves out of a vector in reverse order.
2278: pub type RevMoveItems<T> = Rev<MoveItems<T>>;
libstd/str.rs:
372: /// starting from the back of the string.
373: pub type RevCharSplits<'a, Sep> = Rev<CharSplits<'a, Sep>>;
libstd/iter.rs:
751: /// An double-ended iterator with the direction inverted
753: pub struct Rev<T> {


libstd/iter.rs:1328:75-1328:75 -struct- definition:
/// An iterator which uses `f` to both filter and map elements from `iter`
pub struct FilterMap<'a, A, B, T> {
    iter: T,
references:- 4
193:     fn filter_map<'r, B>(self, f: |A|: 'r -> Option<B>) -> FilterMap<'r, A, B, Self> {
194:         FilterMap { iter: self, f: f }
195:     }
--
1353: impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B>
1354: for FilterMap<'a, A, B, T> {
1355:     #[inline]


libstd/iter.rs:82:54-82:54 -trait- definition:
/// A type growable from an `Iterator` implementation
pub trait Extendable<A>: FromIterator<A> {
    /// Extend a container with the elements yielded by an iterator
references:- 2
libstd/strbuf.rs:
256: impl Extendable<char> for StrBuf {
257:     fn extend<I:Iterator<char>>(&mut self, mut iterator: I) {
libstd/vec.rs:
362: impl<T> Extendable<T> for Vec<T> {
363:     fn extend<I: Iterator<T>>(&mut self, mut iterator: I) {


libstd/iter.rs:1037:19-1037:19 -struct- definition:
pub struct Cycle<T> {
    orig: T,
    iter: T,
references:- 9
1036: /// An iterator that repeats endlessly
1038: pub struct Cycle<T> {
--
1043: impl<A, T: Clone + Iterator<A>> Iterator<A> for Cycle<T> {
1044:     #[inline]
--
1063: impl<A, T: Clone + RandomAccessIterator<A>> RandomAccessIterator<A> for Cycle<T> {
1064:     #[inline]


libstd/iter.rs:1549:19-1549:19 -struct- definition:
pub struct Skip<T> {
    iter: T,
    n: uint
references:- 8
1548: /// An iterator which skips over `n` elements of `iter`.
1550: pub struct Skip<T> {
--
1555: impl<A, T: Iterator<A>> Iterator<A> for Skip<T> {
1556:     #[inline]
--
1596: impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Skip<T> {
1597:     #[inline]


libstd/iter.rs:1613:19-1613:19 -struct- definition:
pub struct Take<T> {
    iter: T,
    n: uint
references:- 9
1612: /// An iterator which only iterates over the first `n` iterations of `iter`.
1614: pub struct Take<T> {
--
1645: impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Take<T> {
1646:     #[inline]
libstd/rt/task.rs:
333:     /// Converts one blocked task handle to a list of many handles to the same.
334:     pub fn make_selectable(self, num_handles: uint) -> Take<BlockedTasks> {
335:         let arc = match self {
libstd/iter.rs:
1619: impl<A, T: Iterator<A>> Iterator<A> for Take<T> {
1620:     #[inline]


libstd/iter.rs:1012:46-1012:46 -trait- definition:
/// A trait for iterators that are cloneable.
pub trait CloneableIterator {
    /// Repeats an iterator endlessly
references:- 2
1029: impl<A, T: Clone + Iterator<A>> CloneableIterator for T {
1030:     #[inline]


libstd/iter.rs:1476:65-1476:65 -struct- definition:
/// An iterator which rejects elements while `predicate` is true
pub struct SkipWhile<'a, A, T> {
    iter: T,
references:- 3
251:     #[inline]
252:     fn skip_while<'r>(self, predicate: |&A|: 'r -> bool) -> SkipWhile<'r, A, Self> {
253:         SkipWhile{iter: self, flag: false, predicate: predicate}
--
1483: impl<'a, A, T: Iterator<A>> Iterator<A> for SkipWhile<'a, A, T> {
1484:     #[inline]


libstd/iter.rs:1934:19-1934:19 -struct- definition:
pub struct Range<A> {
    state: A,
    stop: A,
references:- 9
1943: pub fn range<A: Add<A, A> + Ord + Clone + One>(start: A, stop: A) -> Range<A> {
1944:     Range{state: start, stop: stop, one: One::one()}
1945: }
--
1994: /// the direction it is consumed.
1995: impl<A: Int + Ord + Clone + ToPrimitive> DoubleEndedIterator<A> for Range<A> {
1996:     #[inline]
--
2009: pub struct RangeInclusive<A> {
2010:     range: Range<A>,
2011:     done: bool,


libstd/iter.rs:1817:32-1817:32 -struct- definition:
/// element before yielding it.
pub struct Inspect<'a, A, T> {
    iter: T,
references:- 7
1857: impl<'a, A, T: RandomAccessIterator<A>> RandomAccessIterator<A>
1858: for Inspect<'a, A, T> {
1859:     #[inline]


libstd/iter.rs:1088:19-1088:19 -struct- definition:
pub struct Chain<T, U> {
    a: T,
    b: U,
references:- 9
1087: /// An iterator which strings two iterators together
1089: pub struct Chain<T, U> {
--
1095: impl<A, T: Iterator<A>, U: Iterator<A>> Iterator<A> for Chain<T, U> {
1096:     #[inline]
--
1126: impl<A, T: DoubleEndedIterator<A>, U: DoubleEndedIterator<A>> DoubleEndedIterator<A>
1127: for Chain<T, U> {
1128:     #[inline]
--
1137: impl<A, T: RandomAccessIterator<A>, U: RandomAccessIterator<A>> RandomAccessIterator<A>
1138: for Chain<T, U> {
1139:     #[inline]


libstd/iter.rs:1157:19-1157:19 -struct- definition:
pub struct Zip<T, U> {
    a: T,
    b: U
references:- 10
748: impl<'a, A, B, T: ExactSize<A>> ExactSize<B> for Map<'a, A, B, T> {}
749: impl<A, B, T: ExactSize<A>, U: ExactSize<B>> ExactSize<(A, B)> for Zip<T, U> {}
--
1163: impl<A, B, T: Iterator<A>, U: Iterator<B>> Iterator<(A, B)> for Zip<T, U> {
1164:     #[inline]
--
1193: impl<A, B, T: ExactSize<A>, U: ExactSize<B>> DoubleEndedIterator<(A, B)>
1194: for Zip<T, U> {
1195:     #[inline]
--
1216: impl<A, B, T: RandomAccessIterator<A>, U: RandomAccessIterator<B>>
1217: RandomAccessIterator<(A, B)> for Zip<T, U> {
1218:     #[inline]


libstd/iter.rs:653:59-653:59 -trait- definition:
/// A range iterator able to yield elements from both ends
pub trait DoubleEndedIterator<A>: Iterator<A> {
    /// Yield an element from the end of the range, returning `None` if the range is empty.
references:- 41
libstd/option.rs:
libstd/slice.rs:
libstd/vec.rs:
libstd/str.rs:
libstd/iter.rs: