src/libcore/iter/mod.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 //! Composable external iteration.
  12 //!
  13 //! If you've found yourself with a collection of some kind, and needed to
  14 //! perform an operation on the elements of said collection, you'll quickly run
  15 //! into 'iterators'. Iterators are heavily used in idiomatic Rust code, so
  16 //! it's worth becoming familiar with them.
  17 //!
  18 //! Before explaining more, let's talk about how this module is structured:
  19 //!
  20 //! # Organization
  21 //!
  22 //! This module is largely organized by type:
  23 //!
  24 //! * [Traits] are the core portion: these traits define what kind of iterators
  25 //!   exist and what you can do with them. The methods of these traits are worth
  26 //!   putting some extra study time into.
  27 //! * [Functions] provide some helpful ways to create some basic iterators.
  28 //! * [Structs] are often the return types of the various methods on this
  29 //!   module's traits. You'll usually want to look at the method that creates
  30 //!   the `struct`, rather than the `struct` itself. For more detail about why,
  31 //!   see '[Implementing Iterator](#implementing-iterator)'.
  32 //!
  33 //! [Traits]: #traits
  34 //! [Functions]: #functions
  35 //! [Structs]: #structs
  36 //!
  37 //! That's it! Let's dig into iterators.
  38 //!
  39 //! # Iterator
  40 //!
  41 //! The heart and soul of this module is the [`Iterator`] trait. The core of
  42 //! [`Iterator`] looks like this:
  43 //!
  44 //! ```
  45 //! trait Iterator {
  46 //!     type Item;
  47 //!     fn next(&mut self) -> Option<Self::Item>;
  48 //! }
  49 //! ```
  50 //!
  51 //! An iterator has a method, [`next()`], which when called, returns an
  52 //! [`Option`]`<Item>`. [`next()`] will return `Some(Item)` as long as there
  53 //! are elements, and once they've all been exhausted, will return `None` to
  54 //! indicate that iteration is finished. Individual iterators may choose to
  55 //! resume iteration, and so calling [`next()`] again may or may not eventually
  56 //! start returning `Some(Item)` again at some point.
  57 //!
  58 //! [`Iterator`]'s full definition includes a number of other methods as well,
  59 //! but they are default methods, built on top of [`next()`], and so you get
  60 //! them for free.
  61 //!
  62 //! Iterators are also composable, and it's common to chain them together to do
  63 //! more complex forms of processing. See the [Adapters](#adapters) section
  64 //! below for more details.
  65 //!
  66 //! [`Iterator`]: trait.Iterator.html
  67 //! [`next()`]: trait.Iterator.html#tymethod.next
  68 //! [`Option`]: ../../std/option/enum.Option.html
  69 //!
  70 //! # The three forms of iteration
  71 //!
  72 //! There are three common methods which can create iterators from a collection:
  73 //!
  74 //! * `iter()`, which iterates over `&T`.
  75 //! * `iter_mut()`, which iterates over `&mut T`.
  76 //! * `into_iter()`, which iterates over `T`.
  77 //!
  78 //! Various things in the standard library may implement one or more of the
  79 //! three, where appropriate.
  80 //!
  81 //! # Implementing Iterator
  82 //!
  83 //! Creating an iterator of your own involves two steps: creating a `struct` to
  84 //! hold the iterator's state, and then `impl`ementing [`Iterator`] for that
  85 //! `struct`. This is why there are so many `struct`s in this module: there is
  86 //! one for each iterator and iterator adapter.
  87 //!
  88 //! Let's make an iterator named `Counter` which counts from `1` to `5`:
  89 //!
  90 //! ```
  91 //! // First, the struct:
  92 //!
  93 //! /// An iterator which counts from one to five
  94 //! struct Counter {
  95 //!     count: usize,
  96 //! }
  97 //!
  98 //! // we want our count to start at one, so let's add a new() method to help.
  99 //! // This isn't strictly necessary, but is convenient. Note that we start
 100 //! // `count` at zero, we'll see why in `next()`'s implementation below.
 101 //! impl Counter {
 102 //!     fn new() -> Counter {
 103 //!         Counter { count: 0 }
 104 //!     }
 105 //! }
 106 //!
 107 //! // Then, we implement `Iterator` for our `Counter`:
 108 //!
 109 //! impl Iterator for Counter {
 110 //!     // we will be counting with usize
 111 //!     type Item = usize;
 112 //!
 113 //!     // next() is the only required method
 114 //!     fn next(&mut self) -> Option<usize> {
 115 //!         // increment our count. This is why we started at zero.
 116 //!         self.count += 1;
 117 //!
 118 //!         // check to see if we've finished counting or not.
 119 //!         if self.count < 6 {
 120 //!             Some(self.count)
 121 //!         } else {
 122 //!             None
 123 //!         }
 124 //!     }
 125 //! }
 126 //!
 127 //! // And now we can use it!
 128 //!
 129 //! let mut counter = Counter::new();
 130 //!
 131 //! let x = counter.next().unwrap();
 132 //! println!("{}", x);
 133 //!
 134 //! let x = counter.next().unwrap();
 135 //! println!("{}", x);
 136 //!
 137 //! let x = counter.next().unwrap();
 138 //! println!("{}", x);
 139 //!
 140 //! let x = counter.next().unwrap();
 141 //! println!("{}", x);
 142 //!
 143 //! let x = counter.next().unwrap();
 144 //! println!("{}", x);
 145 //! ```
 146 //!
 147 //! This will print `1` through `5`, each on their own line.
 148 //!
 149 //! Calling `next()` this way gets repetitive. Rust has a construct which can
 150 //! call `next()` on your iterator, until it reaches `None`. Let's go over that
 151 //! next.
 152 //!
 153 //! # for Loops and IntoIterator
 154 //!
 155 //! Rust's `for` loop syntax is actually sugar for iterators. Here's a basic
 156 //! example of `for`:
 157 //!
 158 //! ```
 159 //! let values = vec![1, 2, 3, 4, 5];
 160 //!
 161 //! for x in values {
 162 //!     println!("{}", x);
 163 //! }
 164 //! ```
 165 //!
 166 //! This will print the numbers one through five, each on their own line. But
 167 //! you'll notice something here: we never called anything on our vector to
 168 //! produce an iterator. What gives?
 169 //!
 170 //! There's a trait in the standard library for converting something into an
 171 //! iterator: [`IntoIterator`]. This trait has one method, [`into_iter()`],
 172 //! which converts the thing implementing [`IntoIterator`] into an iterator.
 173 //! Let's take a look at that `for` loop again, and what the compiler converts
 174 //! it into:
 175 //!
 176 //! [`IntoIterator`]: trait.IntoIterator.html
 177 //! [`into_iter()`]: trait.IntoIterator.html#tymethod.into_iter
 178 //!
 179 //! ```
 180 //! let values = vec![1, 2, 3, 4, 5];
 181 //!
 182 //! for x in values {
 183 //!     println!("{}", x);
 184 //! }
 185 //! ```
 186 //!
 187 //! Rust de-sugars this into:
 188 //!
 189 //! ```
 190 //! let values = vec![1, 2, 3, 4, 5];
 191 //! {
 192 //!     let result = match IntoIterator::into_iter(values) {
 193 //!         mut iter => loop {
 194 //!             match iter.next() {
 195 //!                 Some(x) => { println!("{}", x); },
 196 //!                 None => break,
 197 //!             }
 198 //!         },
 199 //!     };
 200 //!     result
 201 //! }
 202 //! ```
 203 //!
 204 //! First, we call `into_iter()` on the value. Then, we match on the iterator
 205 //! that returns, calling [`next()`] over and over until we see a `None`. At
 206 //! that point, we `break` out of the loop, and we're done iterating.
 207 //!
 208 //! There's one more subtle bit here: the standard library contains an
 209 //! interesting implementation of [`IntoIterator`]:
 210 //!
 211 //! ```ignore
 212 //! impl<I: Iterator> IntoIterator for I
 213 //! ```
 214 //!
 215 //! In other words, all [`Iterator`]s implement [`IntoIterator`], by just
 216 //! returning themselves. This means two things:
 217 //!
 218 //! 1. If you're writing an [`Iterator`], you can use it with a `for` loop.
 219 //! 2. If you're creating a collection, implementing [`IntoIterator`] for it
 220 //!    will allow your collection to be used with the `for` loop.
 221 //!
 222 //! # Adapters
 223 //!
 224 //! Functions which take an [`Iterator`] and return another [`Iterator`] are
 225 //! often called 'iterator adapters', as they're a form of the 'adapter
 226 //! pattern'.
 227 //!
 228 //! Common iterator adapters include [`map()`], [`take()`], and [`collect()`].
 229 //! For more, see their documentation.
 230 //!
 231 //! [`map()`]: trait.Iterator.html#method.map
 232 //! [`take()`]: trait.Iterator.html#method.take
 233 //! [`collect()`]: trait.Iterator.html#method.collect
 234 //!
 235 //! # Laziness
 236 //!
 237 //! Iterators (and iterator [adapters](#adapters)) are *lazy*. This means that
 238 //! just creating an iterator doesn't _do_ a whole lot. Nothing really happens
 239 //! until you call [`next()`]. This is sometimes a source of confusion when
 240 //! creating an iterator solely for its side effects. For example, the [`map()`]
 241 //! method calls a closure on each element it iterates over:
 242 //!
 243 //! ```
 244 //! # #![allow(unused_must_use)]
 245 //! let v = vec![1, 2, 3, 4, 5];
 246 //! v.iter().map(|x| println!("{}", x));
 247 //! ```
 248 //!
 249 //! This will not print any values, as we only created an iterator, rather than
 250 //! using it. The compiler will warn us about this kind of behavior:
 251 //!
 252 //! ```text
 253 //! warning: unused result which must be used: iterator adaptors are lazy and
 254 //! do nothing unless consumed
 255 //! ```
 256 //!
 257 //! The idiomatic way to write a [`map()`] for its side effects is to use a
 258 //! `for` loop instead:
 259 //!
 260 //! ```
 261 //! let v = vec![1, 2, 3, 4, 5];
 262 //!
 263 //! for x in &v {
 264 //!     println!("{}", x);
 265 //! }
 266 //! ```
 267 //!
 268 //! [`map()`]: trait.Iterator.html#method.map
 269 //!
 270 //! The two most common ways to evaluate an iterator are to use a `for` loop
 271 //! like this, or using the [`collect()`] adapter to produce a new collection.
 272 //!
 273 //! [`collect()`]: trait.Iterator.html#method.collect
 274 //!
 275 //! # Infinity
 276 //!
 277 //! Iterators do not have to be finite. As an example, an open-ended range is
 278 //! an infinite iterator:
 279 //!
 280 //! ```
 281 //! let numbers = 0..;
 282 //! ```
 283 //!
 284 //! It is common to use the [`take()`] iterator adapter to turn an infinite
 285 //! iterator into a finite one:
 286 //!
 287 //! ```
 288 //! let numbers = 0..;
 289 //! let five_numbers = numbers.take(5);
 290 //!
 291 //! for number in five_numbers {
 292 //!     println!("{}", number);
 293 //! }
 294 //! ```
 295 //!
 296 //! This will print the numbers `0` through `4`, each on their own line.
 297 //!
 298 //! [`take()`]: trait.Iterator.html#method.take
 299
 300 #![stable(feature = "rust1", since = "1.0.0")]
 301
 302 use clone::Clone;
 303 use cmp;
 304 use default::Default;
 305 use fmt;
 306 use iter_private::TrustedRandomAccess;
 307 use ops::FnMut;
 308 use option::Option::{self, Some, None};
 309 use usize;
 310
 311 #[stable(feature = "rust1", since = "1.0.0")]
 312 pub use self::iterator::Iterator;
 313
 314 #[unstable(feature = "step_trait",
 315            reason = "likely to be replaced by finer-grained traits",
 316            issue = "27741")]
 317 pub use self::range::Step;
 318 #[unstable(feature = "step_by", reason = "recent addition",
 319            issue = "27741")]
 320 pub use self::range::StepBy;
 321
 322 #[stable(feature = "rust1", since = "1.0.0")]
 323 pub use self::sources::{Repeat, repeat};
 324 #[stable(feature = "iter_empty", since = "1.2.0")]
 325 pub use self::sources::{Empty, empty};
 326 #[stable(feature = "iter_once", since = "1.2.0")]
 327 pub use self::sources::{Once, once};
 328
 329 #[stable(feature = "rust1", since = "1.0.0")]
 330 pub use self::traits::{FromIterator, IntoIterator, DoubleEndedIterator, Extend};
 331 #[stable(feature = "rust1", since = "1.0.0")]
 332 pub use self::traits::{ExactSizeIterator, Sum, Product};
 333
 334 mod iterator;
 335 mod range;
 336 mod sources;
 337 mod traits;
 338
 339 /// An double-ended iterator with the direction inverted.
 340 ///
 341 /// This `struct` is created by the [`rev()`] method on [`Iterator`]. See its
 342 /// documentation for more.
 343 ///
 344 /// [`rev()`]: trait.Iterator.html#method.rev
 345 /// [`Iterator`]: trait.Iterator.html
 346 #[derive(Clone, Debug)]
 347 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 348 #[stable(feature = "rust1", since = "1.0.0")]
 349 pub struct Rev<T> {
 350     iter: T
 351 }
 352
 353 #[stable(feature = "rust1", since = "1.0.0")]
 354 impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
 355     type Item = <I as Iterator>::Item;
 356
 357     #[inline]
 358     fn next(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next_back() }
 359     #[inline]
 360     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 361 }
 362
 363 #[stable(feature = "rust1", since = "1.0.0")]
 364 impl<I> DoubleEndedIterator for Rev<I> where I: DoubleEndedIterator {
 365     #[inline]
 366     fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next() }
 367 }
 368
 369 #[stable(feature = "rust1", since = "1.0.0")]
 370 impl<I> ExactSizeIterator for Rev<I>
 371     where I: ExactSizeIterator + DoubleEndedIterator {}
 372
 373 /// An iterator that clones the elements of an underlying iterator.
 374 ///
 375 /// This `struct` is created by the [`cloned()`] method on [`Iterator`]. See its
 376 /// documentation for more.
 377 ///
 378 /// [`cloned()`]: trait.Iterator.html#method.cloned
 379 /// [`Iterator`]: trait.Iterator.html
 380 #[stable(feature = "iter_cloned", since = "1.1.0")]
 381 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 382 #[derive(Clone, Debug)]
 383 pub struct Cloned<I> {
 384     it: I,
 385 }
 386
 387 #[stable(feature = "rust1", since = "1.0.0")]
 388 impl<'a, I, T: 'a> Iterator for Cloned<I>
 389     where I: Iterator<Item=&'a T>, T: Clone
 390 {
 391     type Item = T;
 392
 393     fn next(&mut self) -> Option<T> {
 394         self.it.next().cloned()
 395     }
 396
 397     fn size_hint(&self) -> (usize, Option<usize>) {
 398         self.it.size_hint()
 399     }
 400 }
 401
 402 #[stable(feature = "rust1", since = "1.0.0")]
 403 impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
 404     where I: DoubleEndedIterator<Item=&'a T>, T: Clone
 405 {
 406     fn next_back(&mut self) -> Option<T> {
 407         self.it.next_back().cloned()
 408     }
 409 }
 410
 411 #[stable(feature = "rust1", since = "1.0.0")]
 412 impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
 413     where I: ExactSizeIterator<Item=&'a T>, T: Clone
 414 {}
 415
 416 /// An iterator that repeats endlessly.
 417 ///
 418 /// This `struct` is created by the [`cycle()`] method on [`Iterator`]. See its
 419 /// documentation for more.
 420 ///
 421 /// [`cycle()`]: trait.Iterator.html#method.cycle
 422 /// [`Iterator`]: trait.Iterator.html
 423 #[derive(Clone, Debug)]
 424 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 425 #[stable(feature = "rust1", since = "1.0.0")]
 426 pub struct Cycle<I> {
 427     orig: I,
 428     iter: I,
 429 }
 430
 431 #[stable(feature = "rust1", since = "1.0.0")]
 432 impl<I> Iterator for Cycle<I> where I: Clone + Iterator {
 433     type Item = <I as Iterator>::Item;
 434
 435     #[inline]
 436     fn next(&mut self) -> Option<<I as Iterator>::Item> {
 437         match self.iter.next() {
 438             None => { self.iter = self.orig.clone(); self.iter.next() }
 439             y => y
 440         }
 441     }
 442
 443     #[inline]
 444     fn size_hint(&self) -> (usize, Option<usize>) {
 445         // the cycle iterator is either empty or infinite
 446         match self.orig.size_hint() {
 447             sz @ (0, Some(0)) => sz,
 448             (0, _) => (0, None),
 449             _ => (usize::MAX, None)
 450         }
 451     }
 452 }
 453
 454 /// An iterator that strings two iterators together.
 455 ///
 456 /// This `struct` is created by the [`chain()`] method on [`Iterator`]. See its
 457 /// documentation for more.
 458 ///
 459 /// [`chain()`]: trait.Iterator.html#method.chain
 460 /// [`Iterator`]: trait.Iterator.html
 461 #[derive(Clone, Debug)]
 462 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 463 #[stable(feature = "rust1", since = "1.0.0")]
 464 pub struct Chain<A, B> {
 465     a: A,
 466     b: B,
 467     state: ChainState,
 468 }
 469
 470 // The iterator protocol specifies that iteration ends with the return value
 471 // `None` from `.next()` (or `.next_back()`) and it is unspecified what
 472 // further calls return. The chain adaptor must account for this since it uses
 473 // two subiterators.
 474 //
 475 //  It uses three states:
 476 //
 477 //  - Both: `a` and `b` are remaining
 478 //  - Front: `a` remaining
 479 //  - Back: `b` remaining
 480 //
 481 //  The fourth state (neither iterator is remaining) only occurs after Chain has
 482 //  returned None once, so we don't need to store this state.
 483 #[derive(Clone, Debug)]
 484 enum ChainState {
 485     // both front and back iterator are remaining
 486     Both,
 487     // only front is remaining
 488     Front,
 489     // only back is remaining
 490     Back,
 491 }
 492
 493 #[stable(feature = "rust1", since = "1.0.0")]
 494 impl<A, B> Iterator for Chain<A, B> where
 495     A: Iterator,
 496     B: Iterator<Item = A::Item>
 497 {
 498     type Item = A::Item;
 499
 500     #[inline]
 501     fn next(&mut self) -> Option<A::Item> {
 502         match self.state {
 503             ChainState::Both => match self.a.next() {
 504                 elt @ Some(..) => elt,
 505                 None => {
 506                     self.state = ChainState::Back;
 507                     self.b.next()
 508                 }
 509             },
 510             ChainState::Front => self.a.next(),
 511             ChainState::Back => self.b.next(),
 512         }
 513     }
 514
 515     #[inline]
 516     #[rustc_inherit_overflow_checks]
 517     fn count(self) -> usize {
 518         match self.state {
 519             ChainState::Both => self.a.count() + self.b.count(),
 520             ChainState::Front => self.a.count(),
 521             ChainState::Back => self.b.count(),
 522         }
 523     }
 524
 525     #[inline]
 526     fn nth(&mut self, mut n: usize) -> Option<A::Item> {
 527         match self.state {
 528             ChainState::Both | ChainState::Front => {
 529                 for x in self.a.by_ref() {
 530                     if n == 0 {
 531                         return Some(x)
 532                     }
 533                     n -= 1;
 534                 }
 535                 if let ChainState::Both = self.state {
 536                     self.state = ChainState::Back;
 537                 }
 538             }
 539             ChainState::Back => {}
 540         }
 541         if let ChainState::Back = self.state {
 542             self.b.nth(n)
 543         } else {
 544             None
 545         }
 546     }
 547
 548     #[inline]
 549     fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
 550         P: FnMut(&Self::Item) -> bool,
 551     {
 552         match self.state {
 553             ChainState::Both => match self.a.find(&mut predicate) {
 554                 None => {
 555                     self.state = ChainState::Back;
 556                     self.b.find(predicate)
 557                 }
 558                 v => v
 559             },
 560             ChainState::Front => self.a.find(predicate),
 561             ChainState::Back => self.b.find(predicate),
 562         }
 563     }
 564
 565     #[inline]
 566     fn last(self) -> Option<A::Item> {
 567         match self.state {
 568             ChainState::Both => {
 569                 // Must exhaust a before b.
 570                 let a_last = self.a.last();
 571                 let b_last = self.b.last();
 572                 b_last.or(a_last)
 573             },
 574             ChainState::Front => self.a.last(),
 575             ChainState::Back => self.b.last()
 576         }
 577     }
 578
 579     #[inline]
 580     fn size_hint(&self) -> (usize, Option<usize>) {
 581         let (a_lower, a_upper) = self.a.size_hint();
 582         let (b_lower, b_upper) = self.b.size_hint();
 583
 584         let lower = a_lower.saturating_add(b_lower);
 585
 586         let upper = match (a_upper, b_upper) {
 587             (Some(x), Some(y)) => x.checked_add(y),
 588             _ => None
 589         };
 590
 591         (lower, upper)
 592     }
 593 }
 594
 595 #[stable(feature = "rust1", since = "1.0.0")]
 596 impl<A, B> DoubleEndedIterator for Chain<A, B> where
 597     A: DoubleEndedIterator,
 598     B: DoubleEndedIterator<Item=A::Item>,
 599 {
 600     #[inline]
 601     fn next_back(&mut self) -> Option<A::Item> {
 602         match self.state {
 603             ChainState::Both => match self.b.next_back() {
 604                 elt @ Some(..) => elt,
 605                 None => {
 606                     self.state = ChainState::Front;
 607                     self.a.next_back()
 608                 }
 609             },
 610             ChainState::Front => self.a.next_back(),
 611             ChainState::Back => self.b.next_back(),
 612         }
 613     }
 614 }
 615
 616 /// An iterator that iterates two other iterators simultaneously.
 617 ///
 618 /// This `struct` is created by the [`zip()`] method on [`Iterator`]. See its
 619 /// documentation for more.
 620 ///
 621 /// [`zip()`]: trait.Iterator.html#method.zip
 622 /// [`Iterator`]: trait.Iterator.html
 623 #[derive(Clone, Debug)]
 624 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 625 #[stable(feature = "rust1", since = "1.0.0")]
 626 pub struct Zip<A, B> {
 627     a: A,
 628     b: B,
 629     spec: <(A, B) as ZipImplData>::Data,
 630 }
 631
 632 #[stable(feature = "rust1", since = "1.0.0")]
 633 impl<A, B> Iterator for Zip<A, B> where A: Iterator, B: Iterator
 634 {
 635     type Item = (A::Item, B::Item);
 636
 637     #[inline]
 638     fn next(&mut self) -> Option<Self::Item> {
 639         ZipImpl::next(self)
 640     }
 641
 642     #[inline]
 643     fn size_hint(&self) -> (usize, Option<usize>) {
 644         ZipImpl::size_hint(self)
 645     }
 646 }
 647
 648 #[stable(feature = "rust1", since = "1.0.0")]
 649 impl<A, B> DoubleEndedIterator for Zip<A, B> where
 650     A: DoubleEndedIterator + ExactSizeIterator,
 651     B: DoubleEndedIterator + ExactSizeIterator,
 652 {
 653     #[inline]
 654     fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
 655         ZipImpl::next_back(self)
 656     }
 657 }
 658
 659 // Zip specialization trait
 660 #[doc(hidden)]
 661 trait ZipImpl<A, B> {
 662     type Item;
 663     fn new(a: A, b: B) -> Self;
 664     fn next(&mut self) -> Option<Self::Item>;
 665     fn size_hint(&self) -> (usize, Option<usize>);
 666     fn next_back(&mut self) -> Option<Self::Item>
 667         where A: DoubleEndedIterator + ExactSizeIterator,
 668               B: DoubleEndedIterator + ExactSizeIterator;
 669 }
 670
 671 // Zip specialization data members
 672 #[doc(hidden)]
 673 trait ZipImplData {
 674     type Data: 'static + Clone + Default + fmt::Debug;
 675 }
 676
 677 #[doc(hidden)]
 678 impl<T> ZipImplData for T {
 679     default type Data = ();
 680 }
 681
 682 // General Zip impl
 683 #[doc(hidden)]
 684 impl<A, B> ZipImpl<A, B> for Zip<A, B>
 685     where A: Iterator, B: Iterator
 686 {
 687     type Item = (A::Item, B::Item);
 688     default fn new(a: A, b: B) -> Self {
 689         Zip {
 690             a: a,
 691             b: b,
 692             spec: Default::default(), // unused
 693         }
 694     }
 695
 696     #[inline]
 697     default fn next(&mut self) -> Option<(A::Item, B::Item)> {
 698         self.a.next().and_then(|x| {
 699             self.b.next().and_then(|y| {
 700                 Some((x, y))
 701             })
 702         })
 703     }
 704
 705     #[inline]
 706     default fn next_back(&mut self) -> Option<(A::Item, B::Item)>
 707         where A: DoubleEndedIterator + ExactSizeIterator,
 708               B: DoubleEndedIterator + ExactSizeIterator
 709     {
 710         let a_sz = self.a.len();
 711         let b_sz = self.b.len();
 712         if a_sz != b_sz {
 713             // Adjust a, b to equal length
 714             if a_sz > b_sz {
 715                 for _ in 0..a_sz - b_sz { self.a.next_back(); }
 716             } else {
 717                 for _ in 0..b_sz - a_sz { self.b.next_back(); }
 718             }
 719         }
 720         match (self.a.next_back(), self.b.next_back()) {
 721             (Some(x), Some(y)) => Some((x, y)),
 722             (None, None) => None,
 723             _ => unreachable!(),
 724         }
 725     }
 726
 727     #[inline]
 728     default fn size_hint(&self) -> (usize, Option<usize>) {
 729         let (a_lower, a_upper) = self.a.size_hint();
 730         let (b_lower, b_upper) = self.b.size_hint();
 731
 732         let lower = cmp::min(a_lower, b_lower);
 733
 734         let upper = match (a_upper, b_upper) {
 735             (Some(x), Some(y)) => Some(cmp::min(x,y)),
 736             (Some(x), None) => Some(x),
 737             (None, Some(y)) => Some(y),
 738             (None, None) => None
 739         };
 740
 741         (lower, upper)
 742     }
 743 }
 744
 745 #[doc(hidden)]
 746 #[derive(Default, Debug, Clone)]
 747 struct ZipImplFields {
 748     index: usize,
 749     len: usize,
 750 }
 751
 752 #[doc(hidden)]
 753 impl<A, B> ZipImplData for (A, B)
 754     where A: TrustedRandomAccess, B: TrustedRandomAccess
 755 {
 756     type Data = ZipImplFields;
 757 }
 758
 759 #[doc(hidden)]
 760 impl<A, B> ZipImpl<A, B> for Zip<A, B>
 761     where A: TrustedRandomAccess, B: TrustedRandomAccess
 762 {
 763     fn new(a: A, b: B) -> Self {
 764         let len = cmp::min(a.len(), b.len());
 765         Zip {
 766             a: a,
 767             b: b,
 768             spec: ZipImplFields {
 769                 index: 0,
 770                 len: len,
 771             }
 772         }
 773     }
 774
 775     #[inline]
 776     fn next(&mut self) -> Option<(A::Item, B::Item)> {
 777         if self.spec.index < self.spec.len {
 778             let i = self.spec.index;
 779             self.spec.index += 1;
 780             unsafe {
 781                 Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
 782             }
 783         } else {
 784             None
 785         }
 786     }
 787
 788     #[inline]
 789     fn size_hint(&self) -> (usize, Option<usize>) {
 790         let len = self.spec.len - self.spec.index;
 791         (len, Some(len))
 792     }
 793
 794     #[inline]
 795     fn next_back(&mut self) -> Option<(A::Item, B::Item)>
 796         where A: DoubleEndedIterator + ExactSizeIterator,
 797               B: DoubleEndedIterator + ExactSizeIterator
 798     {
 799         if self.spec.index < self.spec.len {
 800             self.spec.len -= 1;
 801             let i = self.spec.len;
 802             unsafe {
 803                 Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
 804             }
 805         } else {
 806             None
 807         }
 808     }
 809 }
 810
 811 #[stable(feature = "rust1", since = "1.0.0")]
 812 impl<A, B> ExactSizeIterator for Zip<A, B>
 813     where A: ExactSizeIterator, B: ExactSizeIterator {}
 814
 815 #[doc(hidden)]
 816 unsafe impl<A, B> TrustedRandomAccess for Zip<A, B>
 817     where A: TrustedRandomAccess,
 818           B: TrustedRandomAccess,
 819 {
 820     unsafe fn get_unchecked(&mut self, i: usize) -> (A::Item, B::Item) {
 821         (self.a.get_unchecked(i), self.b.get_unchecked(i))
 822     }
 823
 824 }
 825
 826 /// An iterator that maps the values of `iter` with `f`.
 827 ///
 828 /// This `struct` is created by the [`map()`] method on [`Iterator`]. See its
 829 /// documentation for more.
 830 ///
 831 /// [`map()`]: trait.Iterator.html#method.map
 832 /// [`Iterator`]: trait.Iterator.html
 833 ///
 834 /// # Notes about side effects
 835 ///
 836 /// The [`map()`] iterator implements [`DoubleEndedIterator`], meaning that
 837 /// you can also [`map()`] backwards:
 838 ///
 839 /// ```rust
 840 /// let v: Vec<i32> = vec![1, 2, 3].into_iter().rev().map(|x| x + 1).collect();
 841 ///
 842 /// assert_eq!(v, [4, 3, 2]);
 843 /// ```
 844 ///
 845 /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
 846 ///
 847 /// But if your closure has state, iterating backwards may act in a way you do
 848 /// not expect. Let's go through an example. First, in the forward direction:
 849 ///
 850 /// ```rust
 851 /// let mut c = 0;
 852 ///
 853 /// for pair in vec!['a', 'b', 'c'].into_iter()
 854 ///                                .map(|letter| { c += 1; (letter, c) }) {
 855 ///     println!("{:?}", pair);
 856 /// }
 857 /// ```
 858 ///
 859 /// This will print "('a', 1), ('b', 2), ('c', 3)".
 860 ///
 861 /// Now consider this twist where we add a call to `rev`. This version will
 862 /// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed,
 863 /// but the values of the counter still go in order. This is because `map()` is
 864 /// still being called lazilly on each item, but we are popping items off the
 865 /// back of the vector now, instead of shifting them from the front.
 866 ///
 867 /// ```rust
 868 /// let mut c = 0;
 869 ///
 870 /// for pair in vec!['a', 'b', 'c'].into_iter()
 871 ///                                .map(|letter| { c += 1; (letter, c) })
 872 ///                                .rev() {
 873 ///     println!("{:?}", pair);
 874 /// }
 875 /// ```
 876 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 877 #[stable(feature = "rust1", since = "1.0.0")]
 878 #[derive(Clone)]
 879 pub struct Map<I, F> {
 880     iter: I,
 881     f: F,
 882 }
 883
 884 #[stable(feature = "core_impl_debug", since = "1.9.0")]
 885 impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> {
 886     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 887         f.debug_struct("Map")
 888             .field("iter", &self.iter)
 889             .finish()
 890     }
 891 }
 892
 893 #[stable(feature = "rust1", since = "1.0.0")]
 894 impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
 895     type Item = B;
 896
 897     #[inline]
 898     fn next(&mut self) -> Option<B> {
 899         self.iter.next().map(&mut self.f)
 900     }
 901
 902     #[inline]
 903     fn size_hint(&self) -> (usize, Option<usize>) {
 904         self.iter.size_hint()
 905     }
 906 }
 907
 908 #[stable(feature = "rust1", since = "1.0.0")]
 909 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where
 910     F: FnMut(I::Item) -> B,
 911 {
 912     #[inline]
 913     fn next_back(&mut self) -> Option<B> {
 914         self.iter.next_back().map(&mut self.f)
 915     }
 916 }
 917
 918 #[stable(feature = "rust1", since = "1.0.0")]
 919 impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F>
 920     where F: FnMut(I::Item) -> B {}
 921
 922 /// An iterator that filters the elements of `iter` with `predicate`.
 923 ///
 924 /// This `struct` is created by the [`filter()`] method on [`Iterator`]. See its
 925 /// documentation for more.
 926 ///
 927 /// [`filter()`]: trait.Iterator.html#method.filter
 928 /// [`Iterator`]: trait.Iterator.html
 929 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 930 #[stable(feature = "rust1", since = "1.0.0")]
 931 #[derive(Clone)]
 932 pub struct Filter<I, P> {
 933     iter: I,
 934     predicate: P,
 935 }
 936
 937 #[stable(feature = "core_impl_debug", since = "1.9.0")]
 938 impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
 939     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 940         f.debug_struct("Filter")
 941             .field("iter", &self.iter)
 942             .finish()
 943     }
 944 }
 945
 946 #[stable(feature = "rust1", since = "1.0.0")]
 947 impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {
 948     type Item = I::Item;
 949
 950     #[inline]
 951     fn next(&mut self) -> Option<I::Item> {
 952         for x in self.iter.by_ref() {
 953             if (self.predicate)(&x) {
 954                 return Some(x);
 955             }
 956         }
 957         None
 958     }
 959
 960     #[inline]
 961     fn size_hint(&self) -> (usize, Option<usize>) {
 962         let (_, upper) = self.iter.size_hint();
 963         (0, upper) // can't know a lower bound, due to the predicate
 964     }
 965 }
 966
 967 #[stable(feature = "rust1", since = "1.0.0")]
 968 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
 969     where P: FnMut(&I::Item) -> bool,
 970 {
 971     #[inline]
 972     fn next_back(&mut self) -> Option<I::Item> {
 973         for x in self.iter.by_ref().rev() {
 974             if (self.predicate)(&x) {
 975                 return Some(x);
 976             }
 977         }
 978         None
 979     }
 980 }
 981
 982 /// An iterator that uses `f` to both filter and map elements from `iter`.
 983 ///
 984 /// This `struct` is created by the [`filter_map()`] method on [`Iterator`]. See its
 985 /// documentation for more.
 986 ///
 987 /// [`filter_map()`]: trait.Iterator.html#method.filter_map
 988 /// [`Iterator`]: trait.Iterator.html
 989 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 990 #[stable(feature = "rust1", since = "1.0.0")]
 991 #[derive(Clone)]
 992 pub struct FilterMap<I, F> {
 993     iter: I,
 994     f: F,
 995 }
 996
 997 #[stable(feature = "core_impl_debug", since = "1.9.0")]
 998 impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> {
 999     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1000         f.debug_struct("FilterMap")
1001             .field("iter", &self.iter)
1002             .finish()
1003     }
1004 }
1005
1006 #[stable(feature = "rust1", since = "1.0.0")]
1007 impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
1008     where F: FnMut(I::Item) -> Option<B>,
1009 {
1010     type Item = B;
1011
1012     #[inline]
1013     fn next(&mut self) -> Option<B> {
1014         for x in self.iter.by_ref() {
1015             if let Some(y) = (self.f)(x) {
1016                 return Some(y);
1017             }
1018         }
1019         None
1020     }
1021
1022     #[inline]
1023     fn size_hint(&self) -> (usize, Option<usize>) {
1024         let (_, upper) = self.iter.size_hint();
1025         (0, upper) // can't know a lower bound, due to the predicate
1026     }
1027 }
1028
1029 #[stable(feature = "rust1", since = "1.0.0")]
1030 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
1031     where F: FnMut(I::Item) -> Option<B>,
1032 {
1033     #[inline]
1034     fn next_back(&mut self) -> Option<B> {
1035         for x in self.iter.by_ref().rev() {
1036             if let Some(y) = (self.f)(x) {
1037                 return Some(y);
1038             }
1039         }
1040         None
1041     }
1042 }
1043
1044 /// An iterator that yields the current count and the element during iteration.
1045 ///
1046 /// This `struct` is created by the [`enumerate()`] method on [`Iterator`]. See its
1047 /// documentation for more.
1048 ///
1049 /// [`enumerate()`]: trait.Iterator.html#method.enumerate
1050 /// [`Iterator`]: trait.Iterator.html
1051 #[derive(Clone, Debug)]
1052 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1053 #[stable(feature = "rust1", since = "1.0.0")]
1054 pub struct Enumerate<I> {
1055     iter: I,
1056     count: usize,
1057 }
1058
1059 #[stable(feature = "rust1", since = "1.0.0")]
1060 impl<I> Iterator for Enumerate<I> where I: Iterator {
1061     type Item = (usize, <I as Iterator>::Item);
1062
1063     /// # Overflow Behavior
1064     ///
1065     /// The method does no guarding against overflows, so enumerating more than
1066     /// `usize::MAX` elements either produces the wrong result or panics. If
1067     /// debug assertions are enabled, a panic is guaranteed.
1068     ///
1069     /// # Panics
1070     ///
1071     /// Might panic if the index of the element overflows a `usize`.
1072     #[inline]
1073     #[rustc_inherit_overflow_checks]
1074     fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1075         self.iter.next().map(|a| {
1076             let ret = (self.count, a);
1077             // Possible undefined overflow.
1078             self.count += 1;
1079             ret
1080         })
1081     }
1082
1083     #[inline]
1084     fn size_hint(&self) -> (usize, Option<usize>) {
1085         self.iter.size_hint()
1086     }
1087
1088     #[inline]
1089     #[rustc_inherit_overflow_checks]
1090     fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
1091         self.iter.nth(n).map(|a| {
1092             let i = self.count + n;
1093             self.count = i + 1;
1094             (i, a)
1095         })
1096     }
1097
1098     #[inline]
1099     fn count(self) -> usize {
1100         self.iter.count()
1101     }
1102 }
1103
1104 #[stable(feature = "rust1", since = "1.0.0")]
1105 impl<I> DoubleEndedIterator for Enumerate<I> where
1106     I: ExactSizeIterator + DoubleEndedIterator
1107 {
1108     #[inline]
1109     fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1110         self.iter.next_back().map(|a| {
1111             let len = self.iter.len();
1112             // Can safely add, `ExactSizeIterator` promises that the number of
1113             // elements fits into a `usize`.
1114             (self.count + len, a)
1115         })
1116     }
1117 }
1118
1119 #[stable(feature = "rust1", since = "1.0.0")]
1120 impl<I> ExactSizeIterator for Enumerate<I> where I: ExactSizeIterator {}
1121
1122 #[doc(hidden)]
1123 unsafe impl<I> TrustedRandomAccess for Enumerate<I>
1124     where I: TrustedRandomAccess
1125 {
1126     unsafe fn get_unchecked(&mut self, i: usize) -> (usize, I::Item) {
1127         (self.count + i, self.iter.get_unchecked(i))
1128     }
1129 }
1130
1131 /// An iterator with a `peek()` that returns an optional reference to the next
1132 /// element.
1133 ///
1134 /// This `struct` is created by the [`peekable()`] method on [`Iterator`]. See its
1135 /// documentation for more.
1136 ///
1137 /// [`peekable()`]: trait.Iterator.html#method.peekable
1138 /// [`Iterator`]: trait.Iterator.html
1139 #[derive(Clone, Debug)]
1140 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1141 #[stable(feature = "rust1", since = "1.0.0")]
1142 pub struct Peekable<I: Iterator> {
1143     iter: I,
1144     peeked: Option<I::Item>,
1145 }
1146
1147 #[stable(feature = "rust1", since = "1.0.0")]
1148 impl<I: Iterator> Iterator for Peekable<I> {
1149     type Item = I::Item;
1150
1151     #[inline]
1152     fn next(&mut self) -> Option<I::Item> {
1153         match self.peeked {
1154             Some(_) => self.peeked.take(),
1155             None => self.iter.next(),
1156         }
1157     }
1158
1159     #[inline]
1160     #[rustc_inherit_overflow_checks]
1161     fn count(self) -> usize {
1162         (if self.peeked.is_some() { 1 } else { 0 }) + self.iter.count()
1163     }
1164
1165     #[inline]
1166     fn nth(&mut self, n: usize) -> Option<I::Item> {
1167         match self.peeked {
1168             Some(_) if n == 0 => self.peeked.take(),
1169             Some(_) => {
1170                 self.peeked = None;
1171                 self.iter.nth(n-1)
1172             },
1173             None => self.iter.nth(n)
1174         }
1175     }
1176
1177     #[inline]
1178     fn last(self) -> Option<I::Item> {
1179         self.iter.last().or(self.peeked)
1180     }
1181
1182     #[inline]
1183     fn size_hint(&self) -> (usize, Option<usize>) {
1184         let (lo, hi) = self.iter.size_hint();
1185         if self.peeked.is_some() {
1186             let lo = lo.saturating_add(1);
1187             let hi = hi.and_then(|x| x.checked_add(1));
1188             (lo, hi)
1189         } else {
1190             (lo, hi)
1191         }
1192     }
1193 }
1194
1195 #[stable(feature = "rust1", since = "1.0.0")]
1196 impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
1197
1198 impl<I: Iterator> Peekable<I> {
1199     /// Returns a reference to the next() value without advancing the iterator.
1200     ///
1201     /// Like [`next()`], if there is a value, it is wrapped in a `Some(T)`.
1202     /// But if the iteration is over, `None` is returned.
1203     ///
1204     /// [`next()`]: trait.Iterator.html#tymethod.next
1205     ///
1206     /// Because `peek()` returns a reference, and many iterators iterate over
1207     /// references, there can be a possibly confusing situation where the
1208     /// return value is a double reference. You can see this effect in the
1209     /// examples below.
1210     ///
1211     /// # Examples
1212     ///
1213     /// Basic usage:
1214     ///
1215     /// ```
1216     /// let xs = [1, 2, 3];
1217     ///
1218     /// let mut iter = xs.iter().peekable();
1219     ///
1220     /// // peek() lets us see into the future
1221     /// assert_eq!(iter.peek(), Some(&&1));
1222     /// assert_eq!(iter.next(), Some(&1));
1223     ///
1224     /// assert_eq!(iter.next(), Some(&2));
1225     ///
1226     /// // The iterator does not advance even if we `peek` multiple times
1227     /// assert_eq!(iter.peek(), Some(&&3));
1228     /// assert_eq!(iter.peek(), Some(&&3));
1229     ///
1230     /// assert_eq!(iter.next(), Some(&3));
1231     ///
1232     /// // After the iterator is finished, so is `peek()`
1233     /// assert_eq!(iter.peek(), None);
1234     /// assert_eq!(iter.next(), None);
1235     /// ```
1236     #[inline]
1237     #[stable(feature = "rust1", since = "1.0.0")]
1238     pub fn peek(&mut self) -> Option<&I::Item> {
1239         if self.peeked.is_none() {
1240             self.peeked = self.iter.next();
1241         }
1242         match self.peeked {
1243             Some(ref value) => Some(value),
1244             None => None,
1245         }
1246     }
1247 }
1248
1249 /// An iterator that rejects elements while `predicate` is true.
1250 ///
1251 /// This `struct` is created by the [`skip_while()`] method on [`Iterator`]. See its
1252 /// documentation for more.
1253 ///
1254 /// [`skip_while()`]: trait.Iterator.html#method.skip_while
1255 /// [`Iterator`]: trait.Iterator.html
1256 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1257 #[stable(feature = "rust1", since = "1.0.0")]
1258 #[derive(Clone)]
1259 pub struct SkipWhile<I, P> {
1260     iter: I,
1261     flag: bool,
1262     predicate: P,
1263 }
1264
1265 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1266 impl<I: fmt::Debug, P> fmt::Debug for SkipWhile<I, P> {
1267     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1268         f.debug_struct("SkipWhile")
1269             .field("iter", &self.iter)
1270             .field("flag", &self.flag)
1271             .finish()
1272     }
1273 }
1274
1275 #[stable(feature = "rust1", since = "1.0.0")]
1276 impl<I: Iterator, P> Iterator for SkipWhile<I, P>
1277     where P: FnMut(&I::Item) -> bool
1278 {
1279     type Item = I::Item;
1280
1281     #[inline]
1282     fn next(&mut self) -> Option<I::Item> {
1283         for x in self.iter.by_ref() {
1284             if self.flag || !(self.predicate)(&x) {
1285                 self.flag = true;
1286                 return Some(x);
1287             }
1288         }
1289         None
1290     }
1291
1292     #[inline]
1293     fn size_hint(&self) -> (usize, Option<usize>) {
1294         let (_, upper) = self.iter.size_hint();
1295         (0, upper) // can't know a lower bound, due to the predicate
1296     }
1297 }
1298
1299 /// An iterator that only accepts elements while `predicate` is true.
1300 ///
1301 /// This `struct` is created by the [`take_while()`] method on [`Iterator`]. See its
1302 /// documentation for more.
1303 ///
1304 /// [`take_while()`]: trait.Iterator.html#method.take_while
1305 /// [`Iterator`]: trait.Iterator.html
1306 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1307 #[stable(feature = "rust1", since = "1.0.0")]
1308 #[derive(Clone)]
1309 pub struct TakeWhile<I, P> {
1310     iter: I,
1311     flag: bool,
1312     predicate: P,
1313 }
1314
1315 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1316 impl<I: fmt::Debug, P> fmt::Debug for TakeWhile<I, P> {
1317     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1318         f.debug_struct("TakeWhile")
1319             .field("iter", &self.iter)
1320             .field("flag", &self.flag)
1321             .finish()
1322     }
1323 }
1324
1325 #[stable(feature = "rust1", since = "1.0.0")]
1326 impl<I: Iterator, P> Iterator for TakeWhile<I, P>
1327     where P: FnMut(&I::Item) -> bool
1328 {
1329     type Item = I::Item;
1330
1331     #[inline]
1332     fn next(&mut self) -> Option<I::Item> {
1333         if self.flag {
1334             None
1335         } else {
1336             self.iter.next().and_then(|x| {
1337                 if (self.predicate)(&x) {
1338                     Some(x)
1339                 } else {
1340                     self.flag = true;
1341                     None
1342                 }
1343             })
1344         }
1345     }
1346
1347     #[inline]
1348     fn size_hint(&self) -> (usize, Option<usize>) {
1349         let (_, upper) = self.iter.size_hint();
1350         (0, upper) // can't know a lower bound, due to the predicate
1351     }
1352 }
1353
1354 /// An iterator that skips over `n` elements of `iter`.
1355 ///
1356 /// This `struct` is created by the [`skip()`] method on [`Iterator`]. See its
1357 /// documentation for more.
1358 ///
1359 /// [`skip()`]: trait.Iterator.html#method.skip
1360 /// [`Iterator`]: trait.Iterator.html
1361 #[derive(Clone, Debug)]
1362 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1363 #[stable(feature = "rust1", since = "1.0.0")]
1364 pub struct Skip<I> {
1365     iter: I,
1366     n: usize
1367 }
1368
1369 #[stable(feature = "rust1", since = "1.0.0")]
1370 impl<I> Iterator for Skip<I> where I: Iterator {
1371     type Item = <I as Iterator>::Item;
1372
1373     #[inline]
1374     fn next(&mut self) -> Option<I::Item> {
1375         if self.n == 0 {
1376             self.iter.next()
1377         } else {
1378             let old_n = self.n;
1379             self.n = 0;
1380             self.iter.nth(old_n)
1381         }
1382     }
1383
1384     #[inline]
1385     fn nth(&mut self, n: usize) -> Option<I::Item> {
1386         // Can't just add n + self.n due to overflow.
1387         if self.n == 0 {
1388             self.iter.nth(n)
1389         } else {
1390             let to_skip = self.n;
1391             self.n = 0;
1392             // nth(n) skips n+1
1393             if self.iter.nth(to_skip-1).is_none() {
1394                 return None;
1395             }
1396             self.iter.nth(n)
1397         }
1398     }
1399
1400     #[inline]
1401     fn count(self) -> usize {
1402         self.iter.count().saturating_sub(self.n)
1403     }
1404
1405     #[inline]
1406     fn last(mut self) -> Option<I::Item> {
1407         if self.n == 0 {
1408             self.iter.last()
1409         } else {
1410             let next = self.next();
1411             if next.is_some() {
1412                 // recurse. n should be 0.
1413                 self.last().or(next)
1414             } else {
1415                 None
1416             }
1417         }
1418     }
1419
1420     #[inline]
1421     fn size_hint(&self) -> (usize, Option<usize>) {
1422         let (lower, upper) = self.iter.size_hint();
1423
1424         let lower = lower.saturating_sub(self.n);
1425         let upper = upper.map(|x| x.saturating_sub(self.n));
1426
1427         (lower, upper)
1428     }
1429 }
1430
1431 #[stable(feature = "rust1", since = "1.0.0")]
1432 impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
1433
1434 #[stable(feature = "double_ended_skip_iterator", since = "1.8.0")]
1435 impl<I> DoubleEndedIterator for Skip<I> where I: DoubleEndedIterator + ExactSizeIterator {
1436     fn next_back(&mut self) -> Option<Self::Item> {
1437         if self.len() > 0 {
1438             self.iter.next_back()
1439         } else {
1440             None
1441         }
1442     }
1443 }
1444
1445 /// An iterator that only iterates over the first `n` iterations of `iter`.
1446 ///
1447 /// This `struct` is created by the [`take()`] method on [`Iterator`]. See its
1448 /// documentation for more.
1449 ///
1450 /// [`take()`]: trait.Iterator.html#method.take
1451 /// [`Iterator`]: trait.Iterator.html
1452 #[derive(Clone, Debug)]
1453 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1454 #[stable(feature = "rust1", since = "1.0.0")]
1455 pub struct Take<I> {
1456     iter: I,
1457     n: usize
1458 }
1459
1460 #[stable(feature = "rust1", since = "1.0.0")]
1461 impl<I> Iterator for Take<I> where I: Iterator{
1462     type Item = <I as Iterator>::Item;
1463
1464     #[inline]
1465     fn next(&mut self) -> Option<<I as Iterator>::Item> {
1466         if self.n != 0 {
1467             self.n -= 1;
1468             self.iter.next()
1469         } else {
1470             None
1471         }
1472     }
1473
1474     #[inline]
1475     fn nth(&mut self, n: usize) -> Option<I::Item> {
1476         if self.n > n {
1477             self.n -= n + 1;
1478             self.iter.nth(n)
1479         } else {
1480             if self.n > 0 {
1481                 self.iter.nth(self.n - 1);
1482                 self.n = 0;
1483             }
1484             None
1485         }
1486     }
1487
1488     #[inline]
1489     fn size_hint(&self) -> (usize, Option<usize>) {
1490         let (lower, upper) = self.iter.size_hint();
1491
1492         let lower = cmp::min(lower, self.n);
1493
1494         let upper = match upper {
1495             Some(x) if x < self.n => Some(x),
1496             _ => Some(self.n)
1497         };
1498
1499         (lower, upper)
1500     }
1501 }
1502
1503 #[stable(feature = "rust1", since = "1.0.0")]
1504 impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
1505
1506
1507 /// An iterator to maintain state while iterating another iterator.
1508 ///
1509 /// This `struct` is created by the [`scan()`] method on [`Iterator`]. See its
1510 /// documentation for more.
1511 ///
1512 /// [`scan()`]: trait.Iterator.html#method.scan
1513 /// [`Iterator`]: trait.Iterator.html
1514 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1515 #[stable(feature = "rust1", since = "1.0.0")]
1516 #[derive(Clone)]
1517 pub struct Scan<I, St, F> {
1518     iter: I,
1519     f: F,
1520     state: St,
1521 }
1522
1523 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1524 impl<I: fmt::Debug, St: fmt::Debug, F> fmt::Debug for Scan<I, St, F> {
1525     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1526         f.debug_struct("Scan")
1527             .field("iter", &self.iter)
1528             .field("state", &self.state)
1529             .finish()
1530     }
1531 }
1532
1533 #[stable(feature = "rust1", since = "1.0.0")]
1534 impl<B, I, St, F> Iterator for Scan<I, St, F> where
1535     I: Iterator,
1536     F: FnMut(&mut St, I::Item) -> Option<B>,
1537 {
1538     type Item = B;
1539
1540     #[inline]
1541     fn next(&mut self) -> Option<B> {
1542         self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
1543     }
1544
1545     #[inline]
1546     fn size_hint(&self) -> (usize, Option<usize>) {
1547         let (_, upper) = self.iter.size_hint();
1548         (0, upper) // can't know a lower bound, due to the scan function
1549     }
1550 }
1551
1552 /// An iterator that maps each element to an iterator, and yields the elements
1553 /// of the produced iterators.
1554 ///
1555 /// This `struct` is created by the [`flat_map()`] method on [`Iterator`]. See its
1556 /// documentation for more.
1557 ///
1558 /// [`flat_map()`]: trait.Iterator.html#method.flat_map
1559 /// [`Iterator`]: trait.Iterator.html
1560 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1561 #[stable(feature = "rust1", since = "1.0.0")]
1562 #[derive(Clone)]
1563 pub struct FlatMap<I, U: IntoIterator, F> {
1564     iter: I,
1565     f: F,
1566     frontiter: Option<U::IntoIter>,
1567     backiter: Option<U::IntoIter>,
1568 }
1569
1570 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1571 impl<I: fmt::Debug, U: IntoIterator, F> fmt::Debug for FlatMap<I, U, F>
1572     where U::IntoIter: fmt::Debug
1573 {
1574     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1575         f.debug_struct("FlatMap")
1576             .field("iter", &self.iter)
1577             .field("frontiter", &self.frontiter)
1578             .field("backiter", &self.backiter)
1579             .finish()
1580     }
1581 }
1582
1583 #[stable(feature = "rust1", since = "1.0.0")]
1584 impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F>
1585     where F: FnMut(I::Item) -> U,
1586 {
1587     type Item = U::Item;
1588
1589     #[inline]
1590     fn next(&mut self) -> Option<U::Item> {
1591         loop {
1592             if let Some(ref mut inner) = self.frontiter {
1593                 if let Some(x) = inner.by_ref().next() {
1594                     return Some(x)
1595                 }
1596             }
1597             match self.iter.next().map(&mut self.f) {
1598                 None => return self.backiter.as_mut().and_then(|it| it.next()),
1599                 next => self.frontiter = next.map(IntoIterator::into_iter),
1600             }
1601         }
1602     }
1603
1604     #[inline]
1605     fn size_hint(&self) -> (usize, Option<usize>) {
1606         let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
1607         let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
1608         let lo = flo.saturating_add(blo);
1609         match (self.iter.size_hint(), fhi, bhi) {
1610             ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
1611             _ => (lo, None)
1612         }
1613     }
1614 }
1615
1616 #[stable(feature = "rust1", since = "1.0.0")]
1617 impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F> where
1618     F: FnMut(I::Item) -> U,
1619     U: IntoIterator,
1620     U::IntoIter: DoubleEndedIterator
1621 {
1622     #[inline]
1623     fn next_back(&mut self) -> Option<U::Item> {
1624         loop {
1625             if let Some(ref mut inner) = self.backiter {
1626                 if let Some(y) = inner.next_back() {
1627                     return Some(y)
1628                 }
1629             }
1630             match self.iter.next_back().map(&mut self.f) {
1631                 None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
1632                 next => self.backiter = next.map(IntoIterator::into_iter),
1633             }
1634         }
1635     }
1636 }
1637
1638 /// An iterator that yields `None` forever after the underlying iterator
1639 /// yields `None` once.
1640 ///
1641 /// This `struct` is created by the [`fuse()`] method on [`Iterator`]. See its
1642 /// documentation for more.
1643 ///
1644 /// [`fuse()`]: trait.Iterator.html#method.fuse
1645 /// [`Iterator`]: trait.Iterator.html
1646 #[derive(Clone, Debug)]
1647 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1648 #[stable(feature = "rust1", since = "1.0.0")]
1649 pub struct Fuse<I> {
1650     iter: I,
1651     done: bool
1652 }
1653
1654 #[stable(feature = "rust1", since = "1.0.0")]
1655 impl<I> Iterator for Fuse<I> where I: Iterator {
1656     type Item = <I as Iterator>::Item;
1657
1658     #[inline]
1659     fn next(&mut self) -> Option<<I as Iterator>::Item> {
1660         if self.done {
1661             None
1662         } else {
1663             let next = self.iter.next();
1664             self.done = next.is_none();
1665             next
1666         }
1667     }
1668
1669     #[inline]
1670     fn nth(&mut self, n: usize) -> Option<I::Item> {
1671         if self.done {
1672             None
1673         } else {
1674             let nth = self.iter.nth(n);
1675             self.done = nth.is_none();
1676             nth
1677         }
1678     }
1679
1680     #[inline]
1681     fn last(self) -> Option<I::Item> {
1682         if self.done {
1683             None
1684         } else {
1685             self.iter.last()
1686         }
1687     }
1688
1689     #[inline]
1690     fn count(self) -> usize {
1691         if self.done {
1692             0
1693         } else {
1694             self.iter.count()
1695         }
1696     }
1697
1698     #[inline]
1699     fn size_hint(&self) -> (usize, Option<usize>) {
1700         if self.done {
1701             (0, Some(0))
1702         } else {
1703             self.iter.size_hint()
1704         }
1705     }
1706 }
1707
1708 #[stable(feature = "rust1", since = "1.0.0")]
1709 impl<I> DoubleEndedIterator for Fuse<I> where I: DoubleEndedIterator {
1710     #[inline]
1711     fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
1712         if self.done {
1713             None
1714         } else {
1715             let next = self.iter.next_back();
1716             self.done = next.is_none();
1717             next
1718         }
1719     }
1720 }
1721
1722 #[stable(feature = "rust1", since = "1.0.0")]
1723 impl<I> ExactSizeIterator for Fuse<I> where I: ExactSizeIterator {}
1724
1725 /// An iterator that calls a function with a reference to each element before
1726 /// yielding it.
1727 ///
1728 /// This `struct` is created by the [`inspect()`] method on [`Iterator`]. See its
1729 /// documentation for more.
1730 ///
1731 /// [`inspect()`]: trait.Iterator.html#method.inspect
1732 /// [`Iterator`]: trait.Iterator.html
1733 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1734 #[stable(feature = "rust1", since = "1.0.0")]
1735 #[derive(Clone)]
1736 pub struct Inspect<I, F> {
1737     iter: I,
1738     f: F,
1739 }
1740
1741 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1742 impl<I: fmt::Debug, F> fmt::Debug for Inspect<I, F> {
1743     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1744         f.debug_struct("Inspect")
1745             .field("iter", &self.iter)
1746             .finish()
1747     }
1748 }
1749
1750 impl<I: Iterator, F> Inspect<I, F> where F: FnMut(&I::Item) {
1751     #[inline]
1752     fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
1753         if let Some(ref a) = elt {
1754             (self.f)(a);
1755         }
1756
1757         elt
1758     }
1759 }
1760
1761 #[stable(feature = "rust1", since = "1.0.0")]
1762 impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) {
1763     type Item = I::Item;
1764
1765     #[inline]
1766     fn next(&mut self) -> Option<I::Item> {
1767         let next = self.iter.next();
1768         self.do_inspect(next)
1769     }
1770
1771     #[inline]
1772     fn size_hint(&self) -> (usize, Option<usize>) {
1773         self.iter.size_hint()
1774     }
1775 }
1776
1777 #[stable(feature = "rust1", since = "1.0.0")]
1778 impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
1779     where F: FnMut(&I::Item),
1780 {
1781     #[inline]
1782     fn next_back(&mut self) -> Option<I::Item> {
1783         let next = self.iter.next_back();
1784         self.do_inspect(next)
1785     }
1786 }
1787
1788 #[stable(feature = "rust1", since = "1.0.0")]
1789 impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F>
1790     where F: FnMut(&I::Item) {}