src/libcore/iter/iterator.rs

   1 // Copyright 2013-2016 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 use cmp::Ordering;
  12
  13 use super::{Chain, Cycle, Cloned, Enumerate, Filter, FilterMap, FlatMap, Fuse};
  14 use super::{Inspect, Map, Peekable, Scan, Skip, SkipWhile, StepBy, Take, TakeWhile, Rev};
  15 use super::{Zip, Sum, Product};
  16 use super::{ChainState, FromIterator, ZipImpl};
  17
  18 fn _assert_is_object_safe(_: &Iterator<Item=()>) {}
  19
  20 /// An interface for dealing with iterators.
  21 ///
  22 /// This is the main iterator trait. For more about the concept of iterators
  23 /// generally, please see the [module-level documentation]. In particular, you
  24 /// may want to know how to [implement `Iterator`][impl].
  25 ///
  26 /// [module-level documentation]: index.html
  27 /// [impl]: index.html#implementing-iterator
  28 #[stable(feature = "rust1", since = "1.0.0")]
  29 #[rustc_on_unimplemented = "`{Self}` is not an iterator; maybe try calling \
  30                             `.iter()` or a similar method"]
  31 pub trait Iterator {
  32     /// The type of the elements being iterated over.
  33     #[stable(feature = "rust1", since = "1.0.0")]
  34     type Item;
  35
  36     /// Advances the iterator and returns the next value.
  37     ///
  38     /// Returns [`None`] when iteration is finished. Individual iterator
  39     /// implementations may choose to resume iteration, and so calling `next()`
  40     /// again may or may not eventually start returning [`Some(Item)`] again at some
  41     /// point.
  42     ///
  43     /// [`None`]: ../../std/option/enum.Option.html#variant.None
  44     /// [`Some(Item)`]: ../../std/option/enum.Option.html#variant.Some
  45     ///
  46     /// # Examples
  47     ///
  48     /// Basic usage:
  49     ///
  50     /// ```
  51     /// let a = [1, 2, 3];
  52     ///
  53     /// let mut iter = a.iter();
  54     ///
  55     /// // A call to next() returns the next value...
  56     /// assert_eq!(Some(&1), iter.next());
  57     /// assert_eq!(Some(&2), iter.next());
  58     /// assert_eq!(Some(&3), iter.next());
  59     ///
  60     /// // ... and then None once it's over.
  61     /// assert_eq!(None, iter.next());
  62     ///
  63     /// // More calls may or may not return None. Here, they always will.
  64     /// assert_eq!(None, iter.next());
  65     /// assert_eq!(None, iter.next());
  66     /// ```
  67     #[stable(feature = "rust1", since = "1.0.0")]
  68     fn next(&mut self) -> Option<Self::Item>;
  69
  70     /// Returns the bounds on the remaining length of the iterator.
  71     ///
  72     /// Specifically, `size_hint()` returns a tuple where the first element
  73     /// is the lower bound, and the second element is the upper bound.
  74     ///
  75     /// The second half of the tuple that is returned is an [`Option`]`<`[`usize`]`>`.
  76     /// A [`None`] here means that either there is no known upper bound, or the
  77     /// upper bound is larger than [`usize`].
  78     ///
  79     /// # Implementation notes
  80     ///
  81     /// It is not enforced that an iterator implementation yields the declared
  82     /// number of elements. A buggy iterator may yield less than the lower bound
  83     /// or more than the upper bound of elements.
  84     ///
  85     /// `size_hint()` is primarily intended to be used for optimizations such as
  86     /// reserving space for the elements of the iterator, but must not be
  87     /// trusted to e.g. omit bounds checks in unsafe code. An incorrect
  88     /// implementation of `size_hint()` should not lead to memory safety
  89     /// violations.
  90     ///
  91     /// That said, the implementation should provide a correct estimation,
  92     /// because otherwise it would be a violation of the trait's protocol.
  93     ///
  94     /// The default implementation returns `(0, None)` which is correct for any
  95     /// iterator.
  96     ///
  97     /// [`usize`]: ../../std/primitive.usize.html
  98     /// [`Option`]: ../../std/option/enum.Option.html
  99     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 100     ///
 101     /// # Examples
 102     ///
 103     /// Basic usage:
 104     ///
 105     /// ```
 106     /// let a = [1, 2, 3];
 107     /// let iter = a.iter();
 108     ///
 109     /// assert_eq!((3, Some(3)), iter.size_hint());
 110     /// ```
 111     ///
 112     /// A more complex example:
 113     ///
 114     /// ```
 115     /// // The even numbers from zero to ten.
 116     /// let iter = (0..10).filter(|x| x % 2 == 0);
 117     ///
 118     /// // We might iterate from zero to ten times. Knowing that it's five
 119     /// // exactly wouldn't be possible without executing filter().
 120     /// assert_eq!((0, Some(10)), iter.size_hint());
 121     ///
 122     /// // Let's add five more numbers with chain()
 123     /// let iter = (0..10).filter(|x| x % 2 == 0).chain(15..20);
 124     ///
 125     /// // now both bounds are increased by five
 126     /// assert_eq!((5, Some(15)), iter.size_hint());
 127     /// ```
 128     ///
 129     /// Returning `None` for an upper bound:
 130     ///
 131     /// ```
 132     /// // an infinite iterator has no upper bound
 133     /// // and the maximum possible lower bound
 134     /// let iter = 0..;
 135     ///
 136     /// assert_eq!((usize::max_value(), None), iter.size_hint());
 137     /// ```
 138     #[inline]
 139     #[stable(feature = "rust1", since = "1.0.0")]
 140     fn size_hint(&self) -> (usize, Option<usize>) { (0, None) }
 141
 142     /// Consumes the iterator, counting the number of iterations and returning it.
 143     ///
 144     /// This method will evaluate the iterator until its [`next`] returns
 145     /// [`None`]. Once [`None`] is encountered, `count()` returns the number of
 146     /// times it called [`next`].
 147     ///
 148     /// [`next`]: #tymethod.next
 149     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 150     ///
 151     /// # Overflow Behavior
 152     ///
 153     /// The method does no guarding against overflows, so counting elements of
 154     /// an iterator with more than [`usize::MAX`] elements either produces the
 155     /// wrong result or panics. If debug assertions are enabled, a panic is
 156     /// guaranteed.
 157     ///
 158     /// # Panics
 159     ///
 160     /// This function might panic if the iterator has more than [`usize::MAX`]
 161     /// elements.
 162     ///
 163     /// [`usize::MAX`]: ../../std/isize/constant.MAX.html
 164     ///
 165     /// # Examples
 166     ///
 167     /// Basic usage:
 168     ///
 169     /// ```
 170     /// let a = [1, 2, 3];
 171     /// assert_eq!(a.iter().count(), 3);
 172     ///
 173     /// let a = [1, 2, 3, 4, 5];
 174     /// assert_eq!(a.iter().count(), 5);
 175     /// ```
 176     #[inline]
 177     #[rustc_inherit_overflow_checks]
 178     #[stable(feature = "rust1", since = "1.0.0")]
 179     fn count(self) -> usize where Self: Sized {
 180         // Might overflow.
 181         self.fold(0, |cnt, _| cnt + 1)
 182     }
 183
 184     /// Consumes the iterator, returning the last element.
 185     ///
 186     /// This method will evaluate the iterator until it returns [`None`]. While
 187     /// doing so, it keeps track of the current element. After [`None`] is
 188     /// returned, `last()` will then return the last element it saw.
 189     ///
 190     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 191     ///
 192     /// # Examples
 193     ///
 194     /// Basic usage:
 195     ///
 196     /// ```
 197     /// let a = [1, 2, 3];
 198     /// assert_eq!(a.iter().last(), Some(&3));
 199     ///
 200     /// let a = [1, 2, 3, 4, 5];
 201     /// assert_eq!(a.iter().last(), Some(&5));
 202     /// ```
 203     #[inline]
 204     #[stable(feature = "rust1", since = "1.0.0")]
 205     fn last(self) -> Option<Self::Item> where Self: Sized {
 206         let mut last = None;
 207         for x in self { last = Some(x); }
 208         last
 209     }
 210
 211     /// Returns the `n`th element of the iterator.
 212     ///
 213     /// Like most indexing operations, the count starts from zero, so `nth(0)`
 214     /// returns the first value, `nth(1)` the second, and so on.
 215     ///
 216     /// Note that all preceding elements, as well as the returned element, will be
 217     /// consumed from the iterator. That means that the preceding elements will be
 218     /// discarded, and also that calling `nth(0)` multiple times on the same iterator
 219     /// will return different elements.
 220     ///
 221     /// `nth()` will return [`None`] if `n` is greater than or equal to the length of the
 222     /// iterator.
 223     ///
 224     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 225     ///
 226     /// # Examples
 227     ///
 228     /// Basic usage:
 229     ///
 230     /// ```
 231     /// let a = [1, 2, 3];
 232     /// assert_eq!(a.iter().nth(1), Some(&2));
 233     /// ```
 234     ///
 235     /// Calling `nth()` multiple times doesn't rewind the iterator:
 236     ///
 237     /// ```
 238     /// let a = [1, 2, 3];
 239     ///
 240     /// let mut iter = a.iter();
 241     ///
 242     /// assert_eq!(iter.nth(1), Some(&2));
 243     /// assert_eq!(iter.nth(1), None);
 244     /// ```
 245     ///
 246     /// Returning `None` if there are less than `n + 1` elements:
 247     ///
 248     /// ```
 249     /// let a = [1, 2, 3];
 250     /// assert_eq!(a.iter().nth(10), None);
 251     /// ```
 252     #[inline]
 253     #[stable(feature = "rust1", since = "1.0.0")]
 254     fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
 255         for x in self {
 256             if n == 0 { return Some(x) }
 257             n -= 1;
 258         }
 259         None
 260     }
 261
 262     /// Creates an iterator starting at the same point, but stepping by
 263     /// the given amount at each iteration.
 264     ///
 265     /// Note that it will always return the first element of the range,
 266     /// regardless of the step given.
 267     ///
 268     /// # Panics
 269     ///
 270     /// The method will panic if the given step is `0`.
 271     ///
 272     /// # Examples
 273     ///
 274     /// Basic usage:
 275     ///
 276     /// ```
 277     /// #![feature(iterator_step_by)]
 278     /// let a = [0, 1, 2, 3, 4, 5];
 279     /// let mut iter = a.into_iter().step_by(2);
 280     ///
 281     /// assert_eq!(iter.next(), Some(&0));
 282     /// assert_eq!(iter.next(), Some(&2));
 283     /// assert_eq!(iter.next(), Some(&4));
 284     /// assert_eq!(iter.next(), None);
 285     /// ```
 286     #[inline]
 287     #[unstable(feature = "iterator_step_by",
 288                reason = "unstable replacement of Range::step_by",
 289                issue = "27741")]
 290     fn step_by(self, step: usize) -> StepBy<Self> where Self: Sized {
 291         assert!(step != 0);
 292         StepBy{iter: self, step: step - 1, first_take: true}
 293     }
 294
 295     /// Takes two iterators and creates a new iterator over both in sequence.
 296     ///
 297     /// `chain()` will return a new iterator which will first iterate over
 298     /// values from the first iterator and then over values from the second
 299     /// iterator.
 300     ///
 301     /// In other words, it links two iterators together, in a chain. 🔗
 302     ///
 303     /// # Examples
 304     ///
 305     /// Basic usage:
 306     ///
 307     /// ```
 308     /// let a1 = [1, 2, 3];
 309     /// let a2 = [4, 5, 6];
 310     ///
 311     /// let mut iter = a1.iter().chain(a2.iter());
 312     ///
 313     /// assert_eq!(iter.next(), Some(&1));
 314     /// assert_eq!(iter.next(), Some(&2));
 315     /// assert_eq!(iter.next(), Some(&3));
 316     /// assert_eq!(iter.next(), Some(&4));
 317     /// assert_eq!(iter.next(), Some(&5));
 318     /// assert_eq!(iter.next(), Some(&6));
 319     /// assert_eq!(iter.next(), None);
 320     /// ```
 321     ///
 322     /// Since the argument to `chain()` uses [`IntoIterator`], we can pass
 323     /// anything that can be converted into an [`Iterator`], not just an
 324     /// [`Iterator`] itself. For example, slices (`&[T]`) implement
 325     /// [`IntoIterator`], and so can be passed to `chain()` directly:
 326     ///
 327     /// [`IntoIterator`]: trait.IntoIterator.html
 328     /// [`Iterator`]: trait.Iterator.html
 329     ///
 330     /// ```
 331     /// let s1 = &[1, 2, 3];
 332     /// let s2 = &[4, 5, 6];
 333     ///
 334     /// let mut iter = s1.iter().chain(s2);
 335     ///
 336     /// assert_eq!(iter.next(), Some(&1));
 337     /// assert_eq!(iter.next(), Some(&2));
 338     /// assert_eq!(iter.next(), Some(&3));
 339     /// assert_eq!(iter.next(), Some(&4));
 340     /// assert_eq!(iter.next(), Some(&5));
 341     /// assert_eq!(iter.next(), Some(&6));
 342     /// assert_eq!(iter.next(), None);
 343     /// ```
 344     #[inline]
 345     #[stable(feature = "rust1", since = "1.0.0")]
 346     fn chain<U>(self, other: U) -> Chain<Self, U::IntoIter> where
 347         Self: Sized, U: IntoIterator<Item=Self::Item>,
 348     {
 349         Chain{a: self, b: other.into_iter(), state: ChainState::Both}
 350     }
 351
 352     /// 'Zips up' two iterators into a single iterator of pairs.
 353     ///
 354     /// `zip()` returns a new iterator that will iterate over two other
 355     /// iterators, returning a tuple where the first element comes from the
 356     /// first iterator, and the second element comes from the second iterator.
 357     ///
 358     /// In other words, it zips two iterators together, into a single one.
 359     ///
 360     /// When either iterator returns [`None`], all further calls to [`next`]
 361     /// will return [`None`].
 362     ///
 363     /// # Examples
 364     ///
 365     /// Basic usage:
 366     ///
 367     /// ```
 368     /// let a1 = [1, 2, 3];
 369     /// let a2 = [4, 5, 6];
 370     ///
 371     /// let mut iter = a1.iter().zip(a2.iter());
 372     ///
 373     /// assert_eq!(iter.next(), Some((&1, &4)));
 374     /// assert_eq!(iter.next(), Some((&2, &5)));
 375     /// assert_eq!(iter.next(), Some((&3, &6)));
 376     /// assert_eq!(iter.next(), None);
 377     /// ```
 378     ///
 379     /// Since the argument to `zip()` uses [`IntoIterator`], we can pass
 380     /// anything that can be converted into an [`Iterator`], not just an
 381     /// [`Iterator`] itself. For example, slices (`&[T]`) implement
 382     /// [`IntoIterator`], and so can be passed to `zip()` directly:
 383     ///
 384     /// [`IntoIterator`]: trait.IntoIterator.html
 385     /// [`Iterator`]: trait.Iterator.html
 386     ///
 387     /// ```
 388     /// let s1 = &[1, 2, 3];
 389     /// let s2 = &[4, 5, 6];
 390     ///
 391     /// let mut iter = s1.iter().zip(s2);
 392     ///
 393     /// assert_eq!(iter.next(), Some((&1, &4)));
 394     /// assert_eq!(iter.next(), Some((&2, &5)));
 395     /// assert_eq!(iter.next(), Some((&3, &6)));
 396     /// assert_eq!(iter.next(), None);
 397     /// ```
 398     ///
 399     /// `zip()` is often used to zip an infinite iterator to a finite one.
 400     /// This works because the finite iterator will eventually return [`None`],
 401     /// ending the zipper. Zipping with `(0..)` can look a lot like [`enumerate`]:
 402     ///
 403     /// ```
 404     /// let enumerate: Vec<_> = "foo".chars().enumerate().collect();
 405     ///
 406     /// let zipper: Vec<_> = (0..).zip("foo".chars()).collect();
 407     ///
 408     /// assert_eq!((0, 'f'), enumerate[0]);
 409     /// assert_eq!((0, 'f'), zipper[0]);
 410     ///
 411     /// assert_eq!((1, 'o'), enumerate[1]);
 412     /// assert_eq!((1, 'o'), zipper[1]);
 413     ///
 414     /// assert_eq!((2, 'o'), enumerate[2]);
 415     /// assert_eq!((2, 'o'), zipper[2]);
 416     /// ```
 417     ///
 418     /// [`enumerate`]: trait.Iterator.html#method.enumerate
 419     /// [`next`]: ../../std/iter/trait.Iterator.html#tymethod.next
 420     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 421     #[inline]
 422     #[stable(feature = "rust1", since = "1.0.0")]
 423     fn zip<U>(self, other: U) -> Zip<Self, U::IntoIter> where
 424         Self: Sized, U: IntoIterator
 425     {
 426         Zip::new(self, other.into_iter())
 427     }
 428
 429     /// Takes a closure and creates an iterator which calls that closure on each
 430     /// element.
 431     ///
 432     /// `map()` transforms one iterator into another, by means of its argument:
 433     /// something that implements `FnMut`. It produces a new iterator which
 434     /// calls this closure on each element of the original iterator.
 435     ///
 436     /// If you are good at thinking in types, you can think of `map()` like this:
 437     /// If you have an iterator that gives you elements of some type `A`, and
 438     /// you want an iterator of some other type `B`, you can use `map()`,
 439     /// passing a closure that takes an `A` and returns a `B`.
 440     ///
 441     /// `map()` is conceptually similar to a [`for`] loop. However, as `map()` is
 442     /// lazy, it is best used when you're already working with other iterators.
 443     /// If you're doing some sort of looping for a side effect, it's considered
 444     /// more idiomatic to use [`for`] than `map()`.
 445     ///
 446     /// [`for`]: ../../book/first-edition/loops.html#for
 447     ///
 448     /// # Examples
 449     ///
 450     /// Basic usage:
 451     ///
 452     /// ```
 453     /// let a = [1, 2, 3];
 454     ///
 455     /// let mut iter = a.into_iter().map(|x| 2 * x);
 456     ///
 457     /// assert_eq!(iter.next(), Some(2));
 458     /// assert_eq!(iter.next(), Some(4));
 459     /// assert_eq!(iter.next(), Some(6));
 460     /// assert_eq!(iter.next(), None);
 461     /// ```
 462     ///
 463     /// If you're doing some sort of side effect, prefer [`for`] to `map()`:
 464     ///
 465     /// ```
 466     /// # #![allow(unused_must_use)]
 467     /// // don't do this:
 468     /// (0..5).map(|x| println!("{}", x));
 469     ///
 470     /// // it won't even execute, as it is lazy. Rust will warn you about this.
 471     ///
 472     /// // Instead, use for:
 473     /// for x in 0..5 {
 474     ///     println!("{}", x);
 475     /// }
 476     /// ```
 477     #[inline]
 478     #[stable(feature = "rust1", since = "1.0.0")]
 479     fn map<B, F>(self, f: F) -> Map<Self, F> where
 480         Self: Sized, F: FnMut(Self::Item) -> B,
 481     {
 482         Map{iter: self, f: f}
 483     }
 484
 485     /// Creates an iterator which uses a closure to determine if an element
 486     /// should be yielded.
 487     ///
 488     /// The closure must return `true` or `false`. `filter()` creates an
 489     /// iterator which calls this closure on each element. If the closure
 490     /// returns `true`, then the element is returned. If the closure returns
 491     /// `false`, it will try again, and call the closure on the next element,
 492     /// seeing if it passes the test.
 493     ///
 494     /// # Examples
 495     ///
 496     /// Basic usage:
 497     ///
 498     /// ```
 499     /// let a = [0i32, 1, 2];
 500     ///
 501     /// let mut iter = a.into_iter().filter(|x| x.is_positive());
 502     ///
 503     /// assert_eq!(iter.next(), Some(&1));
 504     /// assert_eq!(iter.next(), Some(&2));
 505     /// assert_eq!(iter.next(), None);
 506     /// ```
 507     ///
 508     /// Because the closure passed to `filter()` takes a reference, and many
 509     /// iterators iterate over references, this leads to a possibly confusing
 510     /// situation, where the type of the closure is a double reference:
 511     ///
 512     /// ```
 513     /// let a = [0, 1, 2];
 514     ///
 515     /// let mut iter = a.into_iter().filter(|x| **x > 1); // need two *s!
 516     ///
 517     /// assert_eq!(iter.next(), Some(&2));
 518     /// assert_eq!(iter.next(), None);
 519     /// ```
 520     ///
 521     /// It's common to instead use destructuring on the argument to strip away
 522     /// one:
 523     ///
 524     /// ```
 525     /// let a = [0, 1, 2];
 526     ///
 527     /// let mut iter = a.into_iter().filter(|&x| *x > 1); // both & and *
 528     ///
 529     /// assert_eq!(iter.next(), Some(&2));
 530     /// assert_eq!(iter.next(), None);
 531     /// ```
 532     ///
 533     /// or both:
 534     ///
 535     /// ```
 536     /// let a = [0, 1, 2];
 537     ///
 538     /// let mut iter = a.into_iter().filter(|&&x| x > 1); // two &s
 539     ///
 540     /// assert_eq!(iter.next(), Some(&2));
 541     /// assert_eq!(iter.next(), None);
 542     /// ```
 543     ///
 544     /// of these layers.
 545     #[inline]
 546     #[stable(feature = "rust1", since = "1.0.0")]
 547     fn filter<P>(self, predicate: P) -> Filter<Self, P> where
 548         Self: Sized, P: FnMut(&Self::Item) -> bool,
 549     {
 550         Filter{iter: self, predicate: predicate}
 551     }
 552
 553     /// Creates an iterator that both filters and maps.
 554     ///
 555     /// The closure must return an [`Option<T>`]. `filter_map` creates an
 556     /// iterator which calls this closure on each element. If the closure
 557     /// returns [`Some(element)`][`Some`], then that element is returned. If the
 558     /// closure returns [`None`], it will try again, and call the closure on the
 559     /// next element, seeing if it will return [`Some`].
 560     ///
 561     /// Why `filter_map` and not just [`filter`].[`map`]? The key is in this
 562     /// part:
 563     ///
 564     /// [`filter`]: #method.filter
 565     /// [`map`]: #method.map
 566     ///
 567     /// > If the closure returns [`Some(element)`][`Some`], then that element is returned.
 568     ///
 569     /// In other words, it removes the [`Option<T>`] layer automatically. If your
 570     /// mapping is already returning an [`Option<T>`] and you want to skip over
 571     /// [`None`]s, then `filter_map` is much, much nicer to use.
 572     ///
 573     /// # Examples
 574     ///
 575     /// Basic usage:
 576     ///
 577     /// ```
 578     /// let a = ["1", "2", "lol"];
 579     ///
 580     /// let mut iter = a.iter().filter_map(|s| s.parse().ok());
 581     ///
 582     /// assert_eq!(iter.next(), Some(1));
 583     /// assert_eq!(iter.next(), Some(2));
 584     /// assert_eq!(iter.next(), None);
 585     /// ```
 586     ///
 587     /// Here's the same example, but with [`filter`] and [`map`]:
 588     ///
 589     /// ```
 590     /// let a = ["1", "2", "lol"];
 591     ///
 592     /// let mut iter = a.iter()
 593     ///                 .map(|s| s.parse().ok())
 594     ///                 .filter(|s| s.is_some());
 595     ///
 596     /// assert_eq!(iter.next(), Some(Some(1)));
 597     /// assert_eq!(iter.next(), Some(Some(2)));
 598     /// assert_eq!(iter.next(), None);
 599     /// ```
 600     ///
 601     /// There's an extra layer of [`Some`] in there.
 602     ///
 603     /// [`Option<T>`]: ../../std/option/enum.Option.html
 604     /// [`Some`]: ../../std/option/enum.Option.html#variant.Some
 605     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 606     #[inline]
 607     #[stable(feature = "rust1", since = "1.0.0")]
 608     fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F> where
 609         Self: Sized, F: FnMut(Self::Item) -> Option<B>,
 610     {
 611         FilterMap { iter: self, f: f }
 612     }
 613
 614     /// Creates an iterator which gives the current iteration count as well as
 615     /// the next value.
 616     ///
 617     /// The iterator returned yields pairs `(i, val)`, where `i` is the
 618     /// current index of iteration and `val` is the value returned by the
 619     /// iterator.
 620     ///
 621     /// `enumerate()` keeps its count as a [`usize`]. If you want to count by a
 622     /// different sized integer, the [`zip`] function provides similar
 623     /// functionality.
 624     ///
 625     /// # Overflow Behavior
 626     ///
 627     /// The method does no guarding against overflows, so enumerating more than
 628     /// [`usize::MAX`] elements either produces the wrong result or panics. If
 629     /// debug assertions are enabled, a panic is guaranteed.
 630     ///
 631     /// # Panics
 632     ///
 633     /// The returned iterator might panic if the to-be-returned index would
 634     /// overflow a [`usize`].
 635     ///
 636     /// [`usize::MAX`]: ../../std/usize/constant.MAX.html
 637     /// [`usize`]: ../../std/primitive.usize.html
 638     /// [`zip`]: #method.zip
 639     ///
 640     /// # Examples
 641     ///
 642     /// ```
 643     /// let a = ['a', 'b', 'c'];
 644     ///
 645     /// let mut iter = a.iter().enumerate();
 646     ///
 647     /// assert_eq!(iter.next(), Some((0, &'a')));
 648     /// assert_eq!(iter.next(), Some((1, &'b')));
 649     /// assert_eq!(iter.next(), Some((2, &'c')));
 650     /// assert_eq!(iter.next(), None);
 651     /// ```
 652     #[inline]
 653     #[stable(feature = "rust1", since = "1.0.0")]
 654     fn enumerate(self) -> Enumerate<Self> where Self: Sized {
 655         Enumerate { iter: self, count: 0 }
 656     }
 657
 658     /// Creates an iterator which can use `peek` to look at the next element of
 659     /// the iterator without consuming it.
 660     ///
 661     /// Adds a [`peek`] method to an iterator. See its documentation for
 662     /// more information.
 663     ///
 664     /// Note that the underlying iterator is still advanced when [`peek`] is
 665     /// called for the first time: In order to retrieve the next element,
 666     /// [`next`] is called on the underlying iterator, hence any side effects (i.e.
 667     /// anything other than fetching the next value) of the [`next`] method
 668     /// will occur.
 669     ///
 670     /// [`peek`]: struct.Peekable.html#method.peek
 671     /// [`next`]: ../../std/iter/trait.Iterator.html#tymethod.next
 672     ///
 673     /// # Examples
 674     ///
 675     /// Basic usage:
 676     ///
 677     /// ```
 678     /// let xs = [1, 2, 3];
 679     ///
 680     /// let mut iter = xs.iter().peekable();
 681     ///
 682     /// // peek() lets us see into the future
 683     /// assert_eq!(iter.peek(), Some(&&1));
 684     /// assert_eq!(iter.next(), Some(&1));
 685     ///
 686     /// assert_eq!(iter.next(), Some(&2));
 687     ///
 688     /// // we can peek() multiple times, the iterator won't advance
 689     /// assert_eq!(iter.peek(), Some(&&3));
 690     /// assert_eq!(iter.peek(), Some(&&3));
 691     ///
 692     /// assert_eq!(iter.next(), Some(&3));
 693     ///
 694     /// // after the iterator is finished, so is peek()
 695     /// assert_eq!(iter.peek(), None);
 696     /// assert_eq!(iter.next(), None);
 697     /// ```
 698     #[inline]
 699     #[stable(feature = "rust1", since = "1.0.0")]
 700     fn peekable(self) -> Peekable<Self> where Self: Sized {
 701         Peekable{iter: self, peeked: None}
 702     }
 703
 704     /// Creates an iterator that [`skip`]s elements based on a predicate.
 705     ///
 706     /// [`skip`]: #method.skip
 707     ///
 708     /// `skip_while()` takes a closure as an argument. It will call this
 709     /// closure on each element of the iterator, and ignore elements
 710     /// until it returns `false`.
 711     ///
 712     /// After `false` is returned, `skip_while()`'s job is over, and the
 713     /// rest of the elements are yielded.
 714     ///
 715     /// # Examples
 716     ///
 717     /// Basic usage:
 718     ///
 719     /// ```
 720     /// let a = [-1i32, 0, 1];
 721     ///
 722     /// let mut iter = a.into_iter().skip_while(|x| x.is_negative());
 723     ///
 724     /// assert_eq!(iter.next(), Some(&0));
 725     /// assert_eq!(iter.next(), Some(&1));
 726     /// assert_eq!(iter.next(), None);
 727     /// ```
 728     ///
 729     /// Because the closure passed to `skip_while()` takes a reference, and many
 730     /// iterators iterate over references, this leads to a possibly confusing
 731     /// situation, where the type of the closure is a double reference:
 732     ///
 733     /// ```
 734     /// let a = [-1, 0, 1];
 735     ///
 736     /// let mut iter = a.into_iter().skip_while(|x| **x < 0); // need two *s!
 737     ///
 738     /// assert_eq!(iter.next(), Some(&0));
 739     /// assert_eq!(iter.next(), Some(&1));
 740     /// assert_eq!(iter.next(), None);
 741     /// ```
 742     ///
 743     /// Stopping after an initial `false`:
 744     ///
 745     /// ```
 746     /// let a = [-1, 0, 1, -2];
 747     ///
 748     /// let mut iter = a.into_iter().skip_while(|x| **x < 0);
 749     ///
 750     /// assert_eq!(iter.next(), Some(&0));
 751     /// assert_eq!(iter.next(), Some(&1));
 752     ///
 753     /// // while this would have been false, since we already got a false,
 754     /// // skip_while() isn't used any more
 755     /// assert_eq!(iter.next(), Some(&-2));
 756     ///
 757     /// assert_eq!(iter.next(), None);
 758     /// ```
 759     #[inline]
 760     #[stable(feature = "rust1", since = "1.0.0")]
 761     fn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P> where
 762         Self: Sized, P: FnMut(&Self::Item) -> bool,
 763     {
 764         SkipWhile{iter: self, flag: false, predicate: predicate}
 765     }
 766
 767     /// Creates an iterator that yields elements based on a predicate.
 768     ///
 769     /// `take_while()` takes a closure as an argument. It will call this
 770     /// closure on each element of the iterator, and yield elements
 771     /// while it returns `true`.
 772     ///
 773     /// After `false` is returned, `take_while()`'s job is over, and the
 774     /// rest of the elements are ignored.
 775     ///
 776     /// # Examples
 777     ///
 778     /// Basic usage:
 779     ///
 780     /// ```
 781     /// let a = [-1i32, 0, 1];
 782     ///
 783     /// let mut iter = a.into_iter().take_while(|x| x.is_negative());
 784     ///
 785     /// assert_eq!(iter.next(), Some(&-1));
 786     /// assert_eq!(iter.next(), None);
 787     /// ```
 788     ///
 789     /// Because the closure passed to `take_while()` takes a reference, and many
 790     /// iterators iterate over references, this leads to a possibly confusing
 791     /// situation, where the type of the closure is a double reference:
 792     ///
 793     /// ```
 794     /// let a = [-1, 0, 1];
 795     ///
 796     /// let mut iter = a.into_iter().take_while(|x| **x < 0); // need two *s!
 797     ///
 798     /// assert_eq!(iter.next(), Some(&-1));
 799     /// assert_eq!(iter.next(), None);
 800     /// ```
 801     ///
 802     /// Stopping after an initial `false`:
 803     ///
 804     /// ```
 805     /// let a = [-1, 0, 1, -2];
 806     ///
 807     /// let mut iter = a.into_iter().take_while(|x| **x < 0);
 808     ///
 809     /// assert_eq!(iter.next(), Some(&-1));
 810     ///
 811     /// // We have more elements that are less than zero, but since we already
 812     /// // got a false, take_while() isn't used any more
 813     /// assert_eq!(iter.next(), None);
 814     /// ```
 815     ///
 816     /// Because `take_while()` needs to look at the value in order to see if it
 817     /// should be included or not, consuming iterators will see that it is
 818     /// removed:
 819     ///
 820     /// ```
 821     /// let a = [1, 2, 3, 4];
 822     /// let mut iter = a.into_iter();
 823     ///
 824     /// let result: Vec<i32> = iter.by_ref()
 825     ///                            .take_while(|n| **n != 3)
 826     ///                            .cloned()
 827     ///                            .collect();
 828     ///
 829     /// assert_eq!(result, &[1, 2]);
 830     ///
 831     /// let result: Vec<i32> = iter.cloned().collect();
 832     ///
 833     /// assert_eq!(result, &[4]);
 834     /// ```
 835     ///
 836     /// The `3` is no longer there, because it was consumed in order to see if
 837     /// the iteration should stop, but wasn't placed back into the iterator or
 838     /// some similar thing.
 839     #[inline]
 840     #[stable(feature = "rust1", since = "1.0.0")]
 841     fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P> where
 842         Self: Sized, P: FnMut(&Self::Item) -> bool,
 843     {
 844         TakeWhile{iter: self, flag: false, predicate: predicate}
 845     }
 846
 847     /// Creates an iterator that skips the first `n` elements.
 848     ///
 849     /// After they have been consumed, the rest of the elements are yielded.
 850     ///
 851     /// # Examples
 852     ///
 853     /// Basic usage:
 854     ///
 855     /// ```
 856     /// let a = [1, 2, 3];
 857     ///
 858     /// let mut iter = a.iter().skip(2);
 859     ///
 860     /// assert_eq!(iter.next(), Some(&3));
 861     /// assert_eq!(iter.next(), None);
 862     /// ```
 863     #[inline]
 864     #[stable(feature = "rust1", since = "1.0.0")]
 865     fn skip(self, n: usize) -> Skip<Self> where Self: Sized {
 866         Skip{iter: self, n: n}
 867     }
 868
 869     /// Creates an iterator that yields its first `n` elements.
 870     ///
 871     /// # Examples
 872     ///
 873     /// Basic usage:
 874     ///
 875     /// ```
 876     /// let a = [1, 2, 3];
 877     ///
 878     /// let mut iter = a.iter().take(2);
 879     ///
 880     /// assert_eq!(iter.next(), Some(&1));
 881     /// assert_eq!(iter.next(), Some(&2));
 882     /// assert_eq!(iter.next(), None);
 883     /// ```
 884     ///
 885     /// `take()` is often used with an infinite iterator, to make it finite:
 886     ///
 887     /// ```
 888     /// let mut iter = (0..).take(3);
 889     ///
 890     /// assert_eq!(iter.next(), Some(0));
 891     /// assert_eq!(iter.next(), Some(1));
 892     /// assert_eq!(iter.next(), Some(2));
 893     /// assert_eq!(iter.next(), None);
 894     /// ```
 895     #[inline]
 896     #[stable(feature = "rust1", since = "1.0.0")]
 897     fn take(self, n: usize) -> Take<Self> where Self: Sized, {
 898         Take{iter: self, n: n}
 899     }
 900
 901     /// An iterator adaptor similar to [`fold`] that holds internal state and
 902     /// produces a new iterator.
 903     ///
 904     /// [`fold`]: #method.fold
 905     ///
 906     /// `scan()` takes two arguments: an initial value which seeds the internal
 907     /// state, and a closure with two arguments, the first being a mutable
 908     /// reference to the internal state and the second an iterator element.
 909     /// The closure can assign to the internal state to share state between
 910     /// iterations.
 911     ///
 912     /// On iteration, the closure will be applied to each element of the
 913     /// iterator and the return value from the closure, an [`Option`], is
 914     /// yielded by the iterator.
 915     ///
 916     /// [`Option`]: ../../std/option/enum.Option.html
 917     ///
 918     /// # Examples
 919     ///
 920     /// Basic usage:
 921     ///
 922     /// ```
 923     /// let a = [1, 2, 3];
 924     ///
 925     /// let mut iter = a.iter().scan(1, |state, &x| {
 926     ///     // each iteration, we'll multiply the state by the element
 927     ///     *state = *state * x;
 928     ///
 929     ///     // the value passed on to the next iteration
 930     ///     Some(*state)
 931     /// });
 932     ///
 933     /// assert_eq!(iter.next(), Some(1));
 934     /// assert_eq!(iter.next(), Some(2));
 935     /// assert_eq!(iter.next(), Some(6));
 936     /// assert_eq!(iter.next(), None);
 937     /// ```
 938     #[inline]
 939     #[stable(feature = "rust1", since = "1.0.0")]
 940     fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>
 941         where Self: Sized, F: FnMut(&mut St, Self::Item) -> Option<B>,
 942     {
 943         Scan{iter: self, f: f, state: initial_state}
 944     }
 945
 946     /// Creates an iterator that works like map, but flattens nested structure.
 947     ///
 948     /// The [`map`] adapter is very useful, but only when the closure
 949     /// argument produces values. If it produces an iterator instead, there's
 950     /// an extra layer of indirection. `flat_map()` will remove this extra layer
 951     /// on its own.
 952     ///
 953     /// Another way of thinking about `flat_map()`: [`map`]'s closure returns
 954     /// one item for each element, and `flat_map()`'s closure returns an
 955     /// iterator for each element.
 956     ///
 957     /// [`map`]: #method.map
 958     ///
 959     /// # Examples
 960     ///
 961     /// Basic usage:
 962     ///
 963     /// ```
 964     /// let words = ["alpha", "beta", "gamma"];
 965     ///
 966     /// // chars() returns an iterator
 967     /// let merged: String = words.iter()
 968     ///                           .flat_map(|s| s.chars())
 969     ///                           .collect();
 970     /// assert_eq!(merged, "alphabetagamma");
 971     /// ```
 972     #[inline]
 973     #[stable(feature = "rust1", since = "1.0.0")]
 974     fn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F>
 975         where Self: Sized, U: IntoIterator, F: FnMut(Self::Item) -> U,
 976     {
 977         FlatMap{iter: self, f: f, frontiter: None, backiter: None }
 978     }
 979
 980     /// Creates an iterator which ends after the first [`None`].
 981     ///
 982     /// After an iterator returns [`None`], future calls may or may not yield
 983     /// [`Some(T)`] again. `fuse()` adapts an iterator, ensuring that after a
 984     /// [`None`] is given, it will always return [`None`] forever.
 985     ///
 986     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 987     /// [`Some(T)`]: ../../std/option/enum.Option.html#variant.Some
 988     ///
 989     /// # Examples
 990     ///
 991     /// Basic usage:
 992     ///
 993     /// ```
 994     /// // an iterator which alternates between Some and None
 995     /// struct Alternate {
 996     ///     state: i32,
 997     /// }
 998     ///
 999     /// impl Iterator for Alternate {
1000     ///     type Item = i32;
1001     ///
1002     ///     fn next(&mut self) -> Option<i32> {
1003     ///         let val = self.state;
1004     ///         self.state = self.state + 1;
1005     ///
1006     ///         // if it's even, Some(i32), else None
1007     ///         if val % 2 == 0 {
1008     ///             Some(val)
1009     ///         } else {
1010     ///             None
1011     ///         }
1012     ///     }
1013     /// }
1014     ///
1015     /// let mut iter = Alternate { state: 0 };
1016     ///
1017     /// // we can see our iterator going back and forth
1018     /// assert_eq!(iter.next(), Some(0));
1019     /// assert_eq!(iter.next(), None);
1020     /// assert_eq!(iter.next(), Some(2));
1021     /// assert_eq!(iter.next(), None);
1022     ///
1023     /// // however, once we fuse it...
1024     /// let mut iter = iter.fuse();
1025     ///
1026     /// assert_eq!(iter.next(), Some(4));
1027     /// assert_eq!(iter.next(), None);
1028     ///
1029     /// // it will always return None after the first time.
1030     /// assert_eq!(iter.next(), None);
1031     /// assert_eq!(iter.next(), None);
1032     /// assert_eq!(iter.next(), None);
1033     /// ```
1034     #[inline]
1035     #[stable(feature = "rust1", since = "1.0.0")]
1036     fn fuse(self) -> Fuse<Self> where Self: Sized {
1037         Fuse{iter: self, done: false}
1038     }
1039
1040     /// Do something with each element of an iterator, passing the value on.
1041     ///
1042     /// When using iterators, you'll often chain several of them together.
1043     /// While working on such code, you might want to check out what's
1044     /// happening at various parts in the pipeline. To do that, insert
1045     /// a call to `inspect()`.
1046     ///
1047     /// It's much more common for `inspect()` to be used as a debugging tool
1048     /// than to exist in your final code, but never say never.
1049     ///
1050     /// # Examples
1051     ///
1052     /// Basic usage:
1053     ///
1054     /// ```
1055     /// let a = [1, 4, 2, 3];
1056     ///
1057     /// // this iterator sequence is complex.
1058     /// let sum = a.iter()
1059     ///             .cloned()
1060     ///             .filter(|&x| x % 2 == 0)
1061     ///             .fold(0, |sum, i| sum + i);
1062     ///
1063     /// println!("{}", sum);
1064     ///
1065     /// // let's add some inspect() calls to investigate what's happening
1066     /// let sum = a.iter()
1067     ///             .cloned()
1068     ///             .inspect(|x| println!("about to filter: {}", x))
1069     ///             .filter(|&x| x % 2 == 0)
1070     ///             .inspect(|x| println!("made it through filter: {}", x))
1071     ///             .fold(0, |sum, i| sum + i);
1072     ///
1073     /// println!("{}", sum);
1074     /// ```
1075     ///
1076     /// This will print:
1077     ///
1078     /// ```text
1079     /// about to filter: 1
1080     /// about to filter: 4
1081     /// made it through filter: 4
1082     /// about to filter: 2
1083     /// made it through filter: 2
1084     /// about to filter: 3
1085     /// 6
1086     /// ```
1087     #[inline]
1088     #[stable(feature = "rust1", since = "1.0.0")]
1089     fn inspect<F>(self, f: F) -> Inspect<Self, F> where
1090         Self: Sized, F: FnMut(&Self::Item),
1091     {
1092         Inspect{iter: self, f: f}
1093     }
1094
1095     /// Borrows an iterator, rather than consuming it.
1096     ///
1097     /// This is useful to allow applying iterator adaptors while still
1098     /// retaining ownership of the original iterator.
1099     ///
1100     /// # Examples
1101     ///
1102     /// Basic usage:
1103     ///
1104     /// ```
1105     /// let a = [1, 2, 3];
1106     ///
1107     /// let iter = a.into_iter();
1108     ///
1109     /// let sum: i32 = iter.take(5)
1110     ///                    .fold(0, |acc, &i| acc + i );
1111     ///
1112     /// assert_eq!(sum, 6);
1113     ///
1114     /// // if we try to use iter again, it won't work. The following line
1115     /// // gives "error: use of moved value: `iter`
1116     /// // assert_eq!(iter.next(), None);
1117     ///
1118     /// // let's try that again
1119     /// let a = [1, 2, 3];
1120     ///
1121     /// let mut iter = a.into_iter();
1122     ///
1123     /// // instead, we add in a .by_ref()
1124     /// let sum: i32 = iter.by_ref()
1125     ///                    .take(2)
1126     ///                    .fold(0, |acc, &i| acc + i );
1127     ///
1128     /// assert_eq!(sum, 3);
1129     ///
1130     /// // now this is just fine:
1131     /// assert_eq!(iter.next(), Some(&3));
1132     /// assert_eq!(iter.next(), None);
1133     /// ```
1134     #[stable(feature = "rust1", since = "1.0.0")]
1135     fn by_ref(&mut self) -> &mut Self where Self: Sized { self }
1136
1137     /// Transforms an iterator into a collection.
1138     ///
1139     /// `collect()` can take anything iterable, and turn it into a relevant
1140     /// collection. This is one of the more powerful methods in the standard
1141     /// library, used in a variety of contexts.
1142     ///
1143     /// The most basic pattern in which `collect()` is used is to turn one
1144     /// collection into another. You take a collection, call [`iter`] on it,
1145     /// do a bunch of transformations, and then `collect()` at the end.
1146     ///
1147     /// One of the keys to `collect()`'s power is that many things you might
1148     /// not think of as 'collections' actually are. For example, a [`String`]
1149     /// is a collection of [`char`]s. And a collection of
1150     /// [`Result<T, E>`][`Result`] can be thought of as single
1151     /// [`Result`]`<Collection<T>, E>`. See the examples below for more.
1152     ///
1153     /// Because `collect()` is so general, it can cause problems with type
1154     /// inference. As such, `collect()` is one of the few times you'll see
1155     /// the syntax affectionately known as the 'turbofish': `::<>`. This
1156     /// helps the inference algorithm understand specifically which collection
1157     /// you're trying to collect into.
1158     ///
1159     /// # Examples
1160     ///
1161     /// Basic usage:
1162     ///
1163     /// ```
1164     /// let a = [1, 2, 3];
1165     ///
1166     /// let doubled: Vec<i32> = a.iter()
1167     ///                          .map(|&x| x * 2)
1168     ///                          .collect();
1169     ///
1170     /// assert_eq!(vec![2, 4, 6], doubled);
1171     /// ```
1172     ///
1173     /// Note that we needed the `: Vec<i32>` on the left-hand side. This is because
1174     /// we could collect into, for example, a [`VecDeque<T>`] instead:
1175     ///
1176     /// [`VecDeque<T>`]: ../../std/collections/struct.VecDeque.html
1177     ///
1178     /// ```
1179     /// use std::collections::VecDeque;
1180     ///
1181     /// let a = [1, 2, 3];
1182     ///
1183     /// let doubled: VecDeque<i32> = a.iter()
1184     ///                               .map(|&x| x * 2)
1185     ///                               .collect();
1186     ///
1187     /// assert_eq!(2, doubled[0]);
1188     /// assert_eq!(4, doubled[1]);
1189     /// assert_eq!(6, doubled[2]);
1190     /// ```
1191     ///
1192     /// Using the 'turbofish' instead of annotating `doubled`:
1193     ///
1194     /// ```
1195     /// let a = [1, 2, 3];
1196     ///
1197     /// let doubled = a.iter()
1198     ///                .map(|&x| x * 2)
1199     ///                .collect::<Vec<i32>>();
1200     ///
1201     /// assert_eq!(vec![2, 4, 6], doubled);
1202     /// ```
1203     ///
1204     /// Because `collect()` cares about what you're collecting into, you can
1205     /// still use a partial type hint, `_`, with the turbofish:
1206     ///
1207     /// ```
1208     /// let a = [1, 2, 3];
1209     ///
1210     /// let doubled = a.iter()
1211     ///                .map(|&x| x * 2)
1212     ///                .collect::<Vec<_>>();
1213     ///
1214     /// assert_eq!(vec![2, 4, 6], doubled);
1215     /// ```
1216     ///
1217     /// Using `collect()` to make a [`String`]:
1218     ///
1219     /// ```
1220     /// let chars = ['g', 'd', 'k', 'k', 'n'];
1221     ///
1222     /// let hello: String = chars.iter()
1223     ///                          .map(|&x| x as u8)
1224     ///                          .map(|x| (x + 1) as char)
1225     ///                          .collect();
1226     ///
1227     /// assert_eq!("hello", hello);
1228     /// ```
1229     ///
1230     /// If you have a list of [`Result<T, E>`][`Result`]s, you can use `collect()` to
1231     /// see if any of them failed:
1232     ///
1233     /// ```
1234     /// let results = [Ok(1), Err("nope"), Ok(3), Err("bad")];
1235     ///
1236     /// let result: Result<Vec<_>, &str> = results.iter().cloned().collect();
1237     ///
1238     /// // gives us the first error
1239     /// assert_eq!(Err("nope"), result);
1240     ///
1241     /// let results = [Ok(1), Ok(3)];
1242     ///
1243     /// let result: Result<Vec<_>, &str> = results.iter().cloned().collect();
1244     ///
1245     /// // gives us the list of answers
1246     /// assert_eq!(Ok(vec![1, 3]), result);
1247     /// ```
1248     ///
1249     /// [`iter`]: ../../std/iter/trait.Iterator.html#tymethod.next
1250     /// [`String`]: ../../std/string/struct.String.html
1251     /// [`char`]: ../../std/primitive.char.html
1252     /// [`Result`]: ../../std/result/enum.Result.html
1253     #[inline]
1254     #[stable(feature = "rust1", since = "1.0.0")]
1255     fn collect<B: FromIterator<Self::Item>>(self) -> B where Self: Sized {
1256         FromIterator::from_iter(self)
1257     }
1258
1259     /// Consumes an iterator, creating two collections from it.
1260     ///
1261     /// The predicate passed to `partition()` can return `true`, or `false`.
1262     /// `partition()` returns a pair, all of the elements for which it returned
1263     /// `true`, and all of the elements for which it returned `false`.
1264     ///
1265     /// # Examples
1266     ///
1267     /// Basic usage:
1268     ///
1269     /// ```
1270     /// let a = [1, 2, 3];
1271     ///
1272     /// let (even, odd): (Vec<i32>, Vec<i32>) = a.into_iter()
1273     ///                                          .partition(|&n| n % 2 == 0);
1274     ///
1275     /// assert_eq!(even, vec![2]);
1276     /// assert_eq!(odd, vec![1, 3]);
1277     /// ```
1278     #[stable(feature = "rust1", since = "1.0.0")]
1279     fn partition<B, F>(self, mut f: F) -> (B, B) where
1280         Self: Sized,
1281         B: Default + Extend<Self::Item>,
1282         F: FnMut(&Self::Item) -> bool
1283     {
1284         let mut left: B = Default::default();
1285         let mut right: B = Default::default();
1286
1287         for x in self {
1288             if f(&x) {
1289                 left.extend(Some(x))
1290             } else {
1291                 right.extend(Some(x))
1292             }
1293         }
1294
1295         (left, right)
1296     }
1297
1298     /// An iterator adaptor that applies a function, producing a single, final value.
1299     ///
1300     /// `fold()` takes two arguments: an initial value, and a closure with two
1301     /// arguments: an 'accumulator', and an element. The closure returns the value that
1302     /// the accumulator should have for the next iteration.
1303     ///
1304     /// The initial value is the value the accumulator will have on the first
1305     /// call.
1306     ///
1307     /// After applying this closure to every element of the iterator, `fold()`
1308     /// returns the accumulator.
1309     ///
1310     /// This operation is sometimes called 'reduce' or 'inject'.
1311     ///
1312     /// Folding is useful whenever you have a collection of something, and want
1313     /// to produce a single value from it.
1314     ///
1315     /// # Examples
1316     ///
1317     /// Basic usage:
1318     ///
1319     /// ```
1320     /// let a = [1, 2, 3];
1321     ///
1322     /// // the sum of all of the elements of a
1323     /// let sum = a.iter()
1324     ///            .fold(0, |acc, &x| acc + x);
1325     ///
1326     /// assert_eq!(sum, 6);
1327     /// ```
1328     ///
1329     /// Let's walk through each step of the iteration here:
1330     ///
1331     /// | element | acc | x | result |
1332     /// |---------|-----|---|--------|
1333     /// |         | 0   |   |        |
1334     /// | 1       | 0   | 1 | 1      |
1335     /// | 2       | 1   | 2 | 3      |
1336     /// | 3       | 3   | 3 | 6      |
1337     ///
1338     /// And so, our final result, `6`.
1339     ///
1340     /// It's common for people who haven't used iterators a lot to
1341     /// use a `for` loop with a list of things to build up a result. Those
1342     /// can be turned into `fold()`s:
1343     ///
1344     /// [`for`]: ../../book/first-edition/loops.html#for
1345     ///
1346     /// ```
1347     /// let numbers = [1, 2, 3, 4, 5];
1348     ///
1349     /// let mut result = 0;
1350     ///
1351     /// // for loop:
1352     /// for i in &numbers {
1353     ///     result = result + i;
1354     /// }
1355     ///
1356     /// // fold:
1357     /// let result2 = numbers.iter().fold(0, |acc, &x| acc + x);
1358     ///
1359     /// // they're the same
1360     /// assert_eq!(result, result2);
1361     /// ```
1362     #[inline]
1363     #[stable(feature = "rust1", since = "1.0.0")]
1364     fn fold<B, F>(self, init: B, mut f: F) -> B where
1365         Self: Sized, F: FnMut(B, Self::Item) -> B,
1366     {
1367         let mut accum = init;
1368         for x in self {
1369             accum = f(accum, x);
1370         }
1371         accum
1372     }
1373
1374     /// Tests if every element of the iterator matches a predicate.
1375     ///
1376     /// `all()` takes a closure that returns `true` or `false`. It applies
1377     /// this closure to each element of the iterator, and if they all return
1378     /// `true`, then so does `all()`. If any of them return `false`, it
1379     /// returns `false`.
1380     ///
1381     /// `all()` is short-circuiting; in other words, it will stop processing
1382     /// as soon as it finds a `false`, given that no matter what else happens,
1383     /// the result will also be `false`.
1384     ///
1385     /// An empty iterator returns `true`.
1386     ///
1387     /// # Examples
1388     ///
1389     /// Basic usage:
1390     ///
1391     /// ```
1392     /// let a = [1, 2, 3];
1393     ///
1394     /// assert!(a.iter().all(|&x| x > 0));
1395     ///
1396     /// assert!(!a.iter().all(|&x| x > 2));
1397     /// ```
1398     ///
1399     /// Stopping at the first `false`:
1400     ///
1401     /// ```
1402     /// let a = [1, 2, 3];
1403     ///
1404     /// let mut iter = a.iter();
1405     ///
1406     /// assert!(!iter.all(|&x| x != 2));
1407     ///
1408     /// // we can still use `iter`, as there are more elements.
1409     /// assert_eq!(iter.next(), Some(&3));
1410     /// ```
1411     #[inline]
1412     #[stable(feature = "rust1", since = "1.0.0")]
1413     fn all<F>(&mut self, mut f: F) -> bool where
1414         Self: Sized, F: FnMut(Self::Item) -> bool
1415     {
1416         for x in self {
1417             if !f(x) {
1418                 return false;
1419             }
1420         }
1421         true
1422     }
1423
1424     /// Tests if any element of the iterator matches a predicate.
1425     ///
1426     /// `any()` takes a closure that returns `true` or `false`. It applies
1427     /// this closure to each element of the iterator, and if any of them return
1428     /// `true`, then so does `any()`. If they all return `false`, it
1429     /// returns `false`.
1430     ///
1431     /// `any()` is short-circuiting; in other words, it will stop processing
1432     /// as soon as it finds a `true`, given that no matter what else happens,
1433     /// the result will also be `true`.
1434     ///
1435     /// An empty iterator returns `false`.
1436     ///
1437     /// # Examples
1438     ///
1439     /// Basic usage:
1440     ///
1441     /// ```
1442     /// let a = [1, 2, 3];
1443     ///
1444     /// assert!(a.iter().any(|&x| x > 0));
1445     ///
1446     /// assert!(!a.iter().any(|&x| x > 5));
1447     /// ```
1448     ///
1449     /// Stopping at the first `true`:
1450     ///
1451     /// ```
1452     /// let a = [1, 2, 3];
1453     ///
1454     /// let mut iter = a.iter();
1455     ///
1456     /// assert!(iter.any(|&x| x != 2));
1457     ///
1458     /// // we can still use `iter`, as there are more elements.
1459     /// assert_eq!(iter.next(), Some(&2));
1460     /// ```
1461     #[inline]
1462     #[stable(feature = "rust1", since = "1.0.0")]
1463     fn any<F>(&mut self, mut f: F) -> bool where
1464         Self: Sized,
1465         F: FnMut(Self::Item) -> bool
1466     {
1467         for x in self {
1468             if f(x) {
1469                 return true;
1470             }
1471         }
1472         false
1473     }
1474
1475     /// Searches for an element of an iterator that satisfies a predicate.
1476     ///
1477     /// `find()` takes a closure that returns `true` or `false`. It applies
1478     /// this closure to each element of the iterator, and if any of them return
1479     /// `true`, then `find()` returns [`Some(element)`]. If they all return
1480     /// `false`, it returns [`None`].
1481     ///
1482     /// `find()` is short-circuiting; in other words, it will stop processing
1483     /// as soon as the closure returns `true`.
1484     ///
1485     /// Because `find()` takes a reference, and many iterators iterate over
1486     /// references, this leads to a possibly confusing situation where the
1487     /// argument is a double reference. You can see this effect in the
1488     /// examples below, with `&&x`.
1489     ///
1490     /// [`Some(element)`]: ../../std/option/enum.Option.html#variant.Some
1491     /// [`None`]: ../../std/option/enum.Option.html#variant.None
1492     ///
1493     /// # Examples
1494     ///
1495     /// Basic usage:
1496     ///
1497     /// ```
1498     /// let a = [1, 2, 3];
1499     ///
1500     /// assert_eq!(a.iter().find(|&&x| x == 2), Some(&2));
1501     ///
1502     /// assert_eq!(a.iter().find(|&&x| x == 5), None);
1503     /// ```
1504     ///
1505     /// Stopping at the first `true`:
1506     ///
1507     /// ```
1508     /// let a = [1, 2, 3];
1509     ///
1510     /// let mut iter = a.iter();
1511     ///
1512     /// assert_eq!(iter.find(|&&x| x == 2), Some(&2));
1513     ///
1514     /// // we can still use `iter`, as there are more elements.
1515     /// assert_eq!(iter.next(), Some(&3));
1516     /// ```
1517     #[inline]
1518     #[stable(feature = "rust1", since = "1.0.0")]
1519     fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
1520         Self: Sized,
1521         P: FnMut(&Self::Item) -> bool,
1522     {
1523         for x in self {
1524             if predicate(&x) { return Some(x) }
1525         }
1526         None
1527     }
1528
1529     /// Searches for an element in an iterator, returning its index.
1530     ///
1531     /// `position()` takes a closure that returns `true` or `false`. It applies
1532     /// this closure to each element of the iterator, and if one of them
1533     /// returns `true`, then `position()` returns [`Some(index)`]. If all of
1534     /// them return `false`, it returns [`None`].
1535     ///
1536     /// `position()` is short-circuiting; in other words, it will stop
1537     /// processing as soon as it finds a `true`.
1538     ///
1539     /// # Overflow Behavior
1540     ///
1541     /// The method does no guarding against overflows, so if there are more
1542     /// than [`usize::MAX`] non-matching elements, it either produces the wrong
1543     /// result or panics. If debug assertions are enabled, a panic is
1544     /// guaranteed.
1545     ///
1546     /// # Panics
1547     ///
1548     /// This function might panic if the iterator has more than `usize::MAX`
1549     /// non-matching elements.
1550     ///
1551     /// [`Some(index)`]: ../../std/option/enum.Option.html#variant.Some
1552     /// [`None`]: ../../std/option/enum.Option.html#variant.None
1553     /// [`usize::MAX`]: ../../std/usize/constant.MAX.html
1554     ///
1555     /// # Examples
1556     ///
1557     /// Basic usage:
1558     ///
1559     /// ```
1560     /// let a = [1, 2, 3];
1561     ///
1562     /// assert_eq!(a.iter().position(|&x| x == 2), Some(1));
1563     ///
1564     /// assert_eq!(a.iter().position(|&x| x == 5), None);
1565     /// ```
1566     ///
1567     /// Stopping at the first `true`:
1568     ///
1569     /// ```
1570     /// let a = [1, 2, 3, 4];
1571     ///
1572     /// let mut iter = a.iter();
1573     ///
1574     /// assert_eq!(iter.position(|&x| x >= 2), Some(1));
1575     ///
1576     /// // we can still use `iter`, as there are more elements.
1577     /// assert_eq!(iter.next(), Some(&3));
1578     ///
1579     /// // The returned index depends on iterator state
1580     /// assert_eq!(iter.position(|&x| x == 4), Some(0));
1581     ///
1582     /// ```
1583     #[inline]
1584     #[stable(feature = "rust1", since = "1.0.0")]
1585     fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
1586         Self: Sized,
1587         P: FnMut(Self::Item) -> bool,
1588     {
1589         // `enumerate` might overflow.
1590         for (i, x) in self.enumerate() {
1591             if predicate(x) {
1592                 return Some(i);
1593             }
1594         }
1595         None
1596     }
1597
1598     /// Searches for an element in an iterator from the right, returning its
1599     /// index.
1600     ///
1601     /// `rposition()` takes a closure that returns `true` or `false`. It applies
1602     /// this closure to each element of the iterator, starting from the end,
1603     /// and if one of them returns `true`, then `rposition()` returns
1604     /// [`Some(index)`]. If all of them return `false`, it returns [`None`].
1605     ///
1606     /// `rposition()` is short-circuiting; in other words, it will stop
1607     /// processing as soon as it finds a `true`.
1608     ///
1609     /// [`Some(index)`]: ../../std/option/enum.Option.html#variant.Some
1610     /// [`None`]: ../../std/option/enum.Option.html#variant.None
1611     ///
1612     /// # Examples
1613     ///
1614     /// Basic usage:
1615     ///
1616     /// ```
1617     /// let a = [1, 2, 3];
1618     ///
1619     /// assert_eq!(a.iter().rposition(|&x| x == 3), Some(2));
1620     ///
1621     /// assert_eq!(a.iter().rposition(|&x| x == 5), None);
1622     /// ```
1623     ///
1624     /// Stopping at the first `true`:
1625     ///
1626     /// ```
1627     /// let a = [1, 2, 3];
1628     ///
1629     /// let mut iter = a.iter();
1630     ///
1631     /// assert_eq!(iter.rposition(|&x| x == 2), Some(1));
1632     ///
1633     /// // we can still use `iter`, as there are more elements.
1634     /// assert_eq!(iter.next(), Some(&1));
1635     /// ```
1636     #[inline]
1637     #[stable(feature = "rust1", since = "1.0.0")]
1638     fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
1639         P: FnMut(Self::Item) -> bool,
1640         Self: Sized + ExactSizeIterator + DoubleEndedIterator
1641     {
1642         let mut i = self.len();
1643
1644         while let Some(v) = self.next_back() {
1645             // No need for an overflow check here, because `ExactSizeIterator`
1646             // implies that the number of elements fits into a `usize`.
1647             i -= 1;
1648             if predicate(v) {
1649                 return Some(i);
1650             }
1651         }
1652         None
1653     }
1654
1655     /// Returns the maximum element of an iterator.
1656     ///
1657     /// If several elements are equally maximum, the last element is
1658     /// returned. If the iterator is empty, [`None`] is returned.
1659     ///
1660     /// [`None`]: ../../std/option/enum.Option.html#variant.None
1661     ///
1662     /// # Examples
1663     ///
1664     /// Basic usage:
1665     ///
1666     /// ```
1667     /// let a = [1, 2, 3];
1668     /// let b: Vec<u32> = Vec::new();
1669     ///
1670     /// assert_eq!(a.iter().max(), Some(&3));
1671     /// assert_eq!(b.iter().max(), None);
1672     /// ```
1673     #[inline]
1674     #[stable(feature = "rust1", since = "1.0.0")]
1675     fn max(self) -> Option<Self::Item> where Self: Sized, Self::Item: Ord
1676     {
1677         select_fold1(self,
1678                      |_| (),
1679                      // switch to y even if it is only equal, to preserve
1680                      // stability.
1681                      |_, x, _, y| *x <= *y)
1682             .map(|(_, x)| x)
1683     }
1684
1685     /// Returns the minimum element of an iterator.
1686     ///
1687     /// If several elements are equally minimum, the first element is
1688     /// returned. If the iterator is empty, [`None`] is returned.
1689     ///
1690     /// [`None`]: ../../std/option/enum.Option.html#variant.None
1691     ///
1692     /// # Examples
1693     ///
1694     /// Basic usage:
1695     ///
1696     /// ```
1697     /// let a = [1, 2, 3];
1698     /// let b: Vec<u32> = Vec::new();
1699     ///
1700     /// assert_eq!(a.iter().min(), Some(&1));
1701     /// assert_eq!(b.iter().min(), None);
1702     /// ```
1703     #[inline]
1704     #[stable(feature = "rust1", since = "1.0.0")]
1705     fn min(self) -> Option<Self::Item> where Self: Sized, Self::Item: Ord
1706     {
1707         select_fold1(self,
1708                      |_| (),
1709                      // only switch to y if it is strictly smaller, to
1710                      // preserve stability.
1711                      |_, x, _, y| *x > *y)
1712             .map(|(_, x)| x)
1713     }
1714
1715     /// Returns the element that gives the maximum value from the
1716     /// specified function.
1717     ///
1718     /// If several elements are equally maximum, the last element is
1719     /// returned. If the iterator is empty, [`None`] is returned.
1720     ///
1721     /// [`None`]: ../../std/option/enum.Option.html#variant.None
1722     ///
1723     /// # Examples
1724     ///
1725     /// ```
1726     /// let a = [-3_i32, 0, 1, 5, -10];
1727     /// assert_eq!(*a.iter().max_by_key(|x| x.abs()).unwrap(), -10);
1728     /// ```
1729     #[inline]
1730     #[stable(feature = "iter_cmp_by_key", since = "1.6.0")]
1731     fn max_by_key<B: Ord, F>(self, f: F) -> Option<Self::Item>
1732         where Self: Sized, F: FnMut(&Self::Item) -> B,
1733     {
1734         select_fold1(self,
1735                      f,
1736                      // switch to y even if it is only equal, to preserve
1737                      // stability.
1738                      |x_p, _, y_p, _| x_p <= y_p)
1739             .map(|(_, x)| x)
1740     }
1741
1742     /// Returns the element that gives the maximum value with respect to the
1743     /// specified comparison function.
1744     ///
1745     /// If several elements are equally maximum, the last element is
1746     /// returned. If the iterator is empty, [`None`] is returned.
1747     ///
1748     /// [`None`]: ../../std/option/enum.Option.html#variant.None
1749     ///
1750     /// # Examples
1751     ///
1752     /// ```
1753     /// let a = [-3_i32, 0, 1, 5, -10];
1754     /// assert_eq!(*a.iter().max_by(|x, y| x.cmp(y)).unwrap(), 5);
1755     /// ```
1756     #[inline]
1757     #[stable(feature = "iter_max_by", since = "1.15.0")]
1758     fn max_by<F>(self, mut compare: F) -> Option<Self::Item>
1759         where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering,
1760     {
1761         select_fold1(self,
1762                      |_| (),
1763                      // switch to y even if it is only equal, to preserve
1764                      // stability.
1765                      |_, x, _, y| Ordering::Greater != compare(x, y))
1766             .map(|(_, x)| x)
1767     }
1768
1769     /// Returns the element that gives the minimum value from the
1770     /// specified function.
1771     ///
1772     /// If several elements are equally minimum, the first element is
1773     /// returned. If the iterator is empty, [`None`] is returned.
1774     ///
1775     /// [`None`]: ../../std/option/enum.Option.html#variant.None
1776     ///
1777     /// # Examples
1778     ///
1779     /// ```
1780     /// let a = [-3_i32, 0, 1, 5, -10];
1781     /// assert_eq!(*a.iter().min_by_key(|x| x.abs()).unwrap(), 0);
1782     /// ```
1783     #[stable(feature = "iter_cmp_by_key", since = "1.6.0")]
1784     fn min_by_key<B: Ord, F>(self, f: F) -> Option<Self::Item>
1785         where Self: Sized, F: FnMut(&Self::Item) -> B,
1786     {
1787         select_fold1(self,
1788                      f,
1789                      // only switch to y if it is strictly smaller, to
1790                      // preserve stability.
1791                      |x_p, _, y_p, _| x_p > y_p)
1792             .map(|(_, x)| x)
1793     }
1794
1795     /// Returns the element that gives the minimum value with respect to the
1796     /// specified comparison function.
1797     ///
1798     /// If several elements are equally minimum, the first element is
1799     /// returned. If the iterator is empty, [`None`] is returned.
1800     ///
1801     /// [`None`]: ../../std/option/enum.Option.html#variant.None
1802     ///
1803     /// # Examples
1804     ///
1805     /// ```
1806     /// let a = [-3_i32, 0, 1, 5, -10];
1807     /// assert_eq!(*a.iter().min_by(|x, y| x.cmp(y)).unwrap(), -10);
1808     /// ```
1809     #[inline]
1810     #[stable(feature = "iter_min_by", since = "1.15.0")]
1811     fn min_by<F>(self, mut compare: F) -> Option<Self::Item>
1812         where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering,
1813     {
1814         select_fold1(self,
1815                      |_| (),
1816                      // switch to y even if it is strictly smaller, to
1817                      // preserve stability.
1818                      |_, x, _, y| Ordering::Greater == compare(x, y))
1819             .map(|(_, x)| x)
1820     }
1821
1822
1823     /// Reverses an iterator's direction.
1824     ///
1825     /// Usually, iterators iterate from left to right. After using `rev()`,
1826     /// an iterator will instead iterate from right to left.
1827     ///
1828     /// This is only possible if the iterator has an end, so `rev()` only
1829     /// works on [`DoubleEndedIterator`]s.
1830     ///
1831     /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
1832     ///
1833     /// # Examples
1834     ///
1835     /// ```
1836     /// let a = [1, 2, 3];
1837     ///
1838     /// let mut iter = a.iter().rev();
1839     ///
1840     /// assert_eq!(iter.next(), Some(&3));
1841     /// assert_eq!(iter.next(), Some(&2));
1842     /// assert_eq!(iter.next(), Some(&1));
1843     ///
1844     /// assert_eq!(iter.next(), None);
1845     /// ```
1846     #[inline]
1847     #[stable(feature = "rust1", since = "1.0.0")]
1848     fn rev(self) -> Rev<Self> where Self: Sized + DoubleEndedIterator {
1849         Rev{iter: self}
1850     }
1851
1852     /// Converts an iterator of pairs into a pair of containers.
1853     ///
1854     /// `unzip()` consumes an entire iterator of pairs, producing two
1855     /// collections: one from the left elements of the pairs, and one
1856     /// from the right elements.
1857     ///
1858     /// This function is, in some sense, the opposite of [`zip`].
1859     ///
1860     /// [`zip`]: #method.zip
1861     ///
1862     /// # Examples
1863     ///
1864     /// Basic usage:
1865     ///
1866     /// ```
1867     /// let a = [(1, 2), (3, 4)];
1868     ///
1869     /// let (left, right): (Vec<_>, Vec<_>) = a.iter().cloned().unzip();
1870     ///
1871     /// assert_eq!(left, [1, 3]);
1872     /// assert_eq!(right, [2, 4]);
1873     /// ```
1874     #[stable(feature = "rust1", since = "1.0.0")]
1875     fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB) where
1876         FromA: Default + Extend<A>,
1877         FromB: Default + Extend<B>,
1878         Self: Sized + Iterator<Item=(A, B)>,
1879     {
1880         let mut ts: FromA = Default::default();
1881         let mut us: FromB = Default::default();
1882
1883         for (t, u) in self {
1884             ts.extend(Some(t));
1885             us.extend(Some(u));
1886         }
1887
1888         (ts, us)
1889     }
1890
1891     /// Creates an iterator which [`clone`]s all of its elements.
1892     ///
1893     /// This is useful when you have an iterator over `&T`, but you need an
1894     /// iterator over `T`.
1895     ///
1896     /// [`clone`]: ../../std/clone/trait.Clone.html#tymethod.clone
1897     ///
1898     /// # Examples
1899     ///
1900     /// Basic usage:
1901     ///
1902     /// ```
1903     /// let a = [1, 2, 3];
1904     ///
1905     /// let v_cloned: Vec<_> = a.iter().cloned().collect();
1906     ///
1907     /// // cloned is the same as .map(|&x| x), for integers
1908     /// let v_map: Vec<_> = a.iter().map(|&x| x).collect();
1909     ///
1910     /// assert_eq!(v_cloned, vec![1, 2, 3]);
1911     /// assert_eq!(v_map, vec![1, 2, 3]);
1912     /// ```
1913     #[stable(feature = "rust1", since = "1.0.0")]
1914     fn cloned<'a, T: 'a>(self) -> Cloned<Self>
1915         where Self: Sized + Iterator<Item=&'a T>, T: Clone
1916     {
1917         Cloned { it: self }
1918     }
1919
1920     /// Repeats an iterator endlessly.
1921     ///
1922     /// Instead of stopping at [`None`], the iterator will instead start again,
1923     /// from the beginning. After iterating again, it will start at the
1924     /// beginning again. And again. And again. Forever.
1925     ///
1926     /// [`None`]: ../../std/option/enum.Option.html#variant.None
1927     ///
1928     /// # Examples
1929     ///
1930     /// Basic usage:
1931     ///
1932     /// ```
1933     /// let a = [1, 2, 3];
1934     ///
1935     /// let mut it = a.iter().cycle();
1936     ///
1937     /// assert_eq!(it.next(), Some(&1));
1938     /// assert_eq!(it.next(), Some(&2));
1939     /// assert_eq!(it.next(), Some(&3));
1940     /// assert_eq!(it.next(), Some(&1));
1941     /// assert_eq!(it.next(), Some(&2));
1942     /// assert_eq!(it.next(), Some(&3));
1943     /// assert_eq!(it.next(), Some(&1));
1944     /// ```
1945     #[stable(feature = "rust1", since = "1.0.0")]
1946     #[inline]
1947     fn cycle(self) -> Cycle<Self> where Self: Sized + Clone {
1948         Cycle{orig: self.clone(), iter: self}
1949     }
1950
1951     /// Sums the elements of an iterator.
1952     ///
1953     /// Takes each element, adds them together, and returns the result.
1954     ///
1955     /// An empty iterator returns the zero value of the type.
1956     ///
1957     /// # Panics
1958     ///
1959     /// When calling `sum()` and a primitive integer type is being returned, this
1960     /// method will panic if the computation overflows and debug assertions are
1961     /// enabled.
1962     ///
1963     /// # Examples
1964     ///
1965     /// Basic usage:
1966     ///
1967     /// ```
1968     /// let a = [1, 2, 3];
1969     /// let sum: i32 = a.iter().sum();
1970     ///
1971     /// assert_eq!(sum, 6);
1972     /// ```
1973     #[stable(feature = "iter_arith", since = "1.11.0")]
1974     fn sum<S>(self) -> S
1975         where Self: Sized,
1976               S: Sum<Self::Item>,
1977     {
1978         Sum::sum(self)
1979     }
1980
1981     /// Iterates over the entire iterator, multiplying all the elements
1982     ///
1983     /// An empty iterator returns the one value of the type.
1984     ///
1985     /// # Panics
1986     ///
1987     /// When calling `product()` and a primitive integer type is being returned,
1988     /// method will panic if the computation overflows and debug assertions are
1989     /// enabled.
1990     ///
1991     /// # Examples
1992     ///
1993     /// ```
1994     /// fn factorial(n: u32) -> u32 {
1995     ///     (1..).take_while(|&i| i <= n).product()
1996     /// }
1997     /// assert_eq!(factorial(0), 1);
1998     /// assert_eq!(factorial(1), 1);
1999     /// assert_eq!(factorial(5), 120);
2000     /// ```
2001     #[stable(feature = "iter_arith", since = "1.11.0")]
2002     fn product<P>(self) -> P
2003         where Self: Sized,
2004               P: Product<Self::Item>,
2005     {
2006         Product::product(self)
2007     }
2008
2009     /// Lexicographically compares the elements of this `Iterator` with those
2010     /// of another.
2011     #[stable(feature = "iter_order", since = "1.5.0")]
2012     fn cmp<I>(mut self, other: I) -> Ordering where
2013         I: IntoIterator<Item = Self::Item>,
2014         Self::Item: Ord,
2015         Self: Sized,
2016     {
2017         let mut other = other.into_iter();
2018
2019         loop {
2020             match (self.next(), other.next()) {
2021                 (None, None) => return Ordering::Equal,
2022                 (None, _   ) => return Ordering::Less,
2023                 (_   , None) => return Ordering::Greater,
2024                 (Some(x), Some(y)) => match x.cmp(&y) {
2025                     Ordering::Equal => (),
2026                     non_eq => return non_eq,
2027                 },
2028             }
2029         }
2030     }
2031
2032     /// Lexicographically compares the elements of this `Iterator` with those
2033     /// of another.
2034     #[stable(feature = "iter_order", since = "1.5.0")]
2035     fn partial_cmp<I>(mut self, other: I) -> Option<Ordering> where
2036         I: IntoIterator,
2037         Self::Item: PartialOrd<I::Item>,
2038         Self: Sized,
2039     {
2040         let mut other = other.into_iter();
2041
2042         loop {
2043             match (self.next(), other.next()) {
2044                 (None, None) => return Some(Ordering::Equal),
2045                 (None, _   ) => return Some(Ordering::Less),
2046                 (_   , None) => return Some(Ordering::Greater),
2047                 (Some(x), Some(y)) => match x.partial_cmp(&y) {
2048                     Some(Ordering::Equal) => (),
2049                     non_eq => return non_eq,
2050                 },
2051             }
2052         }
2053     }
2054
2055     /// Determines if the elements of this `Iterator` are equal to those of
2056     /// another.
2057     #[stable(feature = "iter_order", since = "1.5.0")]
2058     fn eq<I>(mut self, other: I) -> bool where
2059         I: IntoIterator,
2060         Self::Item: PartialEq<I::Item>,
2061         Self: Sized,
2062     {
2063         let mut other = other.into_iter();
2064
2065         loop {
2066             match (self.next(), other.next()) {
2067                 (None, None) => return true,
2068                 (None, _) | (_, None) => return false,
2069                 (Some(x), Some(y)) => if x != y { return false },
2070             }
2071         }
2072     }
2073
2074     /// Determines if the elements of this `Iterator` are unequal to those of
2075     /// another.
2076     #[stable(feature = "iter_order", since = "1.5.0")]
2077     fn ne<I>(mut self, other: I) -> bool where
2078         I: IntoIterator,
2079         Self::Item: PartialEq<I::Item>,
2080         Self: Sized,
2081     {
2082         let mut other = other.into_iter();
2083
2084         loop {
2085             match (self.next(), other.next()) {
2086                 (None, None) => return false,
2087                 (None, _) | (_, None) => return true,
2088                 (Some(x), Some(y)) => if x.ne(&y) { return true },
2089             }
2090         }
2091     }
2092
2093     /// Determines if the elements of this `Iterator` are lexicographically
2094     /// less than those of another.
2095     #[stable(feature = "iter_order", since = "1.5.0")]
2096     fn lt<I>(mut self, other: I) -> bool where
2097         I: IntoIterator,
2098         Self::Item: PartialOrd<I::Item>,
2099         Self: Sized,
2100     {
2101         let mut other = other.into_iter();
2102
2103         loop {
2104             match (self.next(), other.next()) {
2105                 (None, None) => return false,
2106                 (None, _   ) => return true,
2107                 (_   , None) => return false,
2108                 (Some(x), Some(y)) => {
2109                     match x.partial_cmp(&y) {
2110                         Some(Ordering::Less) => return true,
2111                         Some(Ordering::Equal) => {}
2112                         Some(Ordering::Greater) => return false,
2113                         None => return false,
2114                     }
2115                 },
2116             }
2117         }
2118     }
2119
2120     /// Determines if the elements of this `Iterator` are lexicographically
2121     /// less or equal to those of another.
2122     #[stable(feature = "iter_order", since = "1.5.0")]
2123     fn le<I>(mut self, other: I) -> bool where
2124         I: IntoIterator,
2125         Self::Item: PartialOrd<I::Item>,
2126         Self: Sized,
2127     {
2128         let mut other = other.into_iter();
2129
2130         loop {
2131             match (self.next(), other.next()) {
2132                 (None, None) => return true,
2133                 (None, _   ) => return true,
2134                 (_   , None) => return false,
2135                 (Some(x), Some(y)) => {
2136                     match x.partial_cmp(&y) {
2137                         Some(Ordering::Less) => return true,
2138                         Some(Ordering::Equal) => {}
2139                         Some(Ordering::Greater) => return false,
2140                         None => return false,
2141                     }
2142                 },
2143             }
2144         }
2145     }
2146
2147     /// Determines if the elements of this `Iterator` are lexicographically
2148     /// greater than those of another.
2149     #[stable(feature = "iter_order", since = "1.5.0")]
2150     fn gt<I>(mut self, other: I) -> bool where
2151         I: IntoIterator,
2152         Self::Item: PartialOrd<I::Item>,
2153         Self: Sized,
2154     {
2155         let mut other = other.into_iter();
2156
2157         loop {
2158             match (self.next(), other.next()) {
2159                 (None, None) => return false,
2160                 (None, _   ) => return false,
2161                 (_   , None) => return true,
2162                 (Some(x), Some(y)) => {
2163                     match x.partial_cmp(&y) {
2164                         Some(Ordering::Less) => return false,
2165                         Some(Ordering::Equal) => {}
2166                         Some(Ordering::Greater) => return true,
2167                         None => return false,
2168                     }
2169                 }
2170             }
2171         }
2172     }
2173
2174     /// Determines if the elements of this `Iterator` are lexicographically
2175     /// greater than or equal to those of another.
2176     #[stable(feature = "iter_order", since = "1.5.0")]
2177     fn ge<I>(mut self, other: I) -> bool where
2178         I: IntoIterator,
2179         Self::Item: PartialOrd<I::Item>,
2180         Self: Sized,
2181     {
2182         let mut other = other.into_iter();
2183
2184         loop {
2185             match (self.next(), other.next()) {
2186                 (None, None) => return true,
2187                 (None, _   ) => return false,
2188                 (_   , None) => return true,
2189                 (Some(x), Some(y)) => {
2190                     match x.partial_cmp(&y) {
2191                         Some(Ordering::Less) => return false,
2192                         Some(Ordering::Equal) => {}
2193                         Some(Ordering::Greater) => return true,
2194                         None => return false,
2195                     }
2196                 },
2197             }
2198         }
2199     }
2200 }
2201
2202 /// Select an element from an iterator based on the given "projection"
2203 /// and "comparison" function.
2204 ///
2205 /// This is an idiosyncratic helper to try to factor out the
2206 /// commonalities of {max,min}{,_by}. In particular, this avoids
2207 /// having to implement optimizations several times.
2208 #[inline]
2209 fn select_fold1<I, B, FProj, FCmp>(mut it: I,
2210                                    mut f_proj: FProj,
2211                                    mut f_cmp: FCmp) -> Option<(B, I::Item)>
2212     where I: Iterator,
2213           FProj: FnMut(&I::Item) -> B,
2214           FCmp: FnMut(&B, &I::Item, &B, &I::Item) -> bool
2215 {
2216     // start with the first element as our selection. This avoids
2217     // having to use `Option`s inside the loop, translating to a
2218     // sizeable performance gain (6x in one case).
2219     it.next().map(|mut sel| {
2220         let mut sel_p = f_proj(&sel);
2221
2222         for x in it {
2223             let x_p = f_proj(&x);
2224             if f_cmp(&sel_p, &sel, &x_p, &x) {
2225                 sel = x;
2226                 sel_p = x_p;
2227             }
2228         }
2229         (sel_p, sel)
2230     })
2231 }
2232
2233 #[stable(feature = "rust1", since = "1.0.0")]
2234 impl<'a, I: Iterator + ?Sized> Iterator for &'a mut I {
2235     type Item = I::Item;
2236     fn next(&mut self) -> Option<I::Item> { (**self).next() }
2237     fn size_hint(&self) -> (usize, Option<usize>) { (**self).size_hint() }
2238     fn nth(&mut self, n: usize) -> Option<Self::Item> {
2239         (**self).nth(n)
2240     }
2241 }