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 cmp;
 303 use fmt;
 304 use iter_private::TrustedRandomAccess;
 305 use usize;
 306
 307 #[stable(feature = "rust1", since = "1.0.0")]
 308 pub use self::iterator::Iterator;
 309
 310 #[unstable(feature = "step_trait",
 311            reason = "likely to be replaced by finer-grained traits",
 312            issue = "27741")]
 313 pub use self::range::Step;
 314 #[unstable(feature = "step_by", reason = "recent addition",
 315            issue = "27741")]
 316 pub use self::range::StepBy;
 317
 318 #[stable(feature = "rust1", since = "1.0.0")]
 319 pub use self::sources::{Repeat, repeat};
 320 #[stable(feature = "iter_empty", since = "1.2.0")]
 321 pub use self::sources::{Empty, empty};
 322 #[stable(feature = "iter_once", since = "1.2.0")]
 323 pub use self::sources::{Once, once};
 324
 325 #[stable(feature = "rust1", since = "1.0.0")]
 326 pub use self::traits::{FromIterator, IntoIterator, DoubleEndedIterator, Extend};
 327 #[stable(feature = "rust1", since = "1.0.0")]
 328 pub use self::traits::{ExactSizeIterator, Sum, Product};
 329 #[unstable(feature = "fused", issue = "35602")]
 330 pub use self::traits::FusedIterator;
 331
 332 mod iterator;
 333 mod range;
 334 mod sources;
 335 mod traits;
 336
 337 /// An double-ended iterator with the direction inverted.
 338 ///
 339 /// This `struct` is created by the [`rev()`] method on [`Iterator`]. See its
 340 /// documentation for more.
 341 ///
 342 /// [`rev()`]: trait.Iterator.html#method.rev
 343 /// [`Iterator`]: trait.Iterator.html
 344 #[derive(Clone, Debug)]
 345 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 346 #[stable(feature = "rust1", since = "1.0.0")]
 347 pub struct Rev<T> {
 348     iter: T
 349 }
 350
 351 #[stable(feature = "rust1", since = "1.0.0")]
 352 impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
 353     type Item = <I as Iterator>::Item;
 354
 355     #[inline]
 356     fn next(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next_back() }
 357     #[inline]
 358     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 359 }
 360
 361 #[stable(feature = "rust1", since = "1.0.0")]
 362 impl<I> DoubleEndedIterator for Rev<I> where I: DoubleEndedIterator {
 363     #[inline]
 364     fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next() }
 365 }
 366
 367 #[stable(feature = "rust1", since = "1.0.0")]
 368 impl<I> ExactSizeIterator for Rev<I>
 369     where I: ExactSizeIterator + DoubleEndedIterator {}
 370
 371 #[unstable(feature = "fused", issue = "35602")]
 372 impl<I> FusedIterator for Rev<I>
 373     where I: FusedIterator + DoubleEndedIterator {}
 374
 375 /// An iterator that clones the elements of an underlying iterator.
 376 ///
 377 /// This `struct` is created by the [`cloned()`] method on [`Iterator`]. See its
 378 /// documentation for more.
 379 ///
 380 /// [`cloned()`]: trait.Iterator.html#method.cloned
 381 /// [`Iterator`]: trait.Iterator.html
 382 #[stable(feature = "iter_cloned", since = "1.1.0")]
 383 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 384 #[derive(Clone, Debug)]
 385 pub struct Cloned<I> {
 386     it: I,
 387 }
 388
 389 #[stable(feature = "rust1", since = "1.0.0")]
 390 impl<'a, I, T: 'a> Iterator for Cloned<I>
 391     where I: Iterator<Item=&'a T>, T: Clone
 392 {
 393     type Item = T;
 394
 395     fn next(&mut self) -> Option<T> {
 396         self.it.next().cloned()
 397     }
 398
 399     fn size_hint(&self) -> (usize, Option<usize>) {
 400         self.it.size_hint()
 401     }
 402 }
 403
 404 #[stable(feature = "rust1", since = "1.0.0")]
 405 impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
 406     where I: DoubleEndedIterator<Item=&'a T>, T: Clone
 407 {
 408     fn next_back(&mut self) -> Option<T> {
 409         self.it.next_back().cloned()
 410     }
 411 }
 412
 413 #[stable(feature = "rust1", since = "1.0.0")]
 414 impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
 415     where I: ExactSizeIterator<Item=&'a T>, T: Clone
 416 {}
 417
 418 #[unstable(feature = "fused", issue = "35602")]
 419 impl<'a, I, T: 'a> FusedIterator for Cloned<I>
 420     where I: FusedIterator<Item=&'a T>, T: Clone
 421 {}
 422
 423 /// An iterator that repeats endlessly.
 424 ///
 425 /// This `struct` is created by the [`cycle()`] method on [`Iterator`]. See its
 426 /// documentation for more.
 427 ///
 428 /// [`cycle()`]: trait.Iterator.html#method.cycle
 429 /// [`Iterator`]: trait.Iterator.html
 430 #[derive(Clone, Debug)]
 431 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 432 #[stable(feature = "rust1", since = "1.0.0")]
 433 pub struct Cycle<I> {
 434     orig: I,
 435     iter: I,
 436 }
 437
 438 #[stable(feature = "rust1", since = "1.0.0")]
 439 impl<I> Iterator for Cycle<I> where I: Clone + Iterator {
 440     type Item = <I as Iterator>::Item;
 441
 442     #[inline]
 443     fn next(&mut self) -> Option<<I as Iterator>::Item> {
 444         match self.iter.next() {
 445             None => { self.iter = self.orig.clone(); self.iter.next() }
 446             y => y
 447         }
 448     }
 449
 450     #[inline]
 451     fn size_hint(&self) -> (usize, Option<usize>) {
 452         // the cycle iterator is either empty or infinite
 453         match self.orig.size_hint() {
 454             sz @ (0, Some(0)) => sz,
 455             (0, _) => (0, None),
 456             _ => (usize::MAX, None)
 457         }
 458     }
 459 }
 460
 461 #[unstable(feature = "fused", issue = "35602")]
 462 impl<I> FusedIterator for Cycle<I> where I: Clone + Iterator {}
 463
 464 /// An iterator that strings two iterators together.
 465 ///
 466 /// This `struct` is created by the [`chain()`] method on [`Iterator`]. See its
 467 /// documentation for more.
 468 ///
 469 /// [`chain()`]: trait.Iterator.html#method.chain
 470 /// [`Iterator`]: trait.Iterator.html
 471 #[derive(Clone, Debug)]
 472 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 473 #[stable(feature = "rust1", since = "1.0.0")]
 474 pub struct Chain<A, B> {
 475     a: A,
 476     b: B,
 477     state: ChainState,
 478 }
 479
 480 // The iterator protocol specifies that iteration ends with the return value
 481 // `None` from `.next()` (or `.next_back()`) and it is unspecified what
 482 // further calls return. The chain adaptor must account for this since it uses
 483 // two subiterators.
 484 //
 485 //  It uses three states:
 486 //
 487 //  - Both: `a` and `b` are remaining
 488 //  - Front: `a` remaining
 489 //  - Back: `b` remaining
 490 //
 491 //  The fourth state (neither iterator is remaining) only occurs after Chain has
 492 //  returned None once, so we don't need to store this state.
 493 #[derive(Clone, Debug)]
 494 enum ChainState {
 495     // both front and back iterator are remaining
 496     Both,
 497     // only front is remaining
 498     Front,
 499     // only back is remaining
 500     Back,
 501 }
 502
 503 #[stable(feature = "rust1", since = "1.0.0")]
 504 impl<A, B> Iterator for Chain<A, B> where
 505     A: Iterator,
 506     B: Iterator<Item = A::Item>
 507 {
 508     type Item = A::Item;
 509
 510     #[inline]
 511     fn next(&mut self) -> Option<A::Item> {
 512         match self.state {
 513             ChainState::Both => match self.a.next() {
 514                 elt @ Some(..) => elt,
 515                 None => {
 516                     self.state = ChainState::Back;
 517                     self.b.next()
 518                 }
 519             },
 520             ChainState::Front => self.a.next(),
 521             ChainState::Back => self.b.next(),
 522         }
 523     }
 524
 525     #[inline]
 526     #[rustc_inherit_overflow_checks]
 527     fn count(self) -> usize {
 528         match self.state {
 529             ChainState::Both => self.a.count() + self.b.count(),
 530             ChainState::Front => self.a.count(),
 531             ChainState::Back => self.b.count(),
 532         }
 533     }
 534
 535     #[inline]
 536     fn nth(&mut self, mut n: usize) -> Option<A::Item> {
 537         match self.state {
 538             ChainState::Both | ChainState::Front => {
 539                 for x in self.a.by_ref() {
 540                     if n == 0 {
 541                         return Some(x)
 542                     }
 543                     n -= 1;
 544                 }
 545                 if let ChainState::Both = self.state {
 546                     self.state = ChainState::Back;
 547                 }
 548             }
 549             ChainState::Back => {}
 550         }
 551         if let ChainState::Back = self.state {
 552             self.b.nth(n)
 553         } else {
 554             None
 555         }
 556     }
 557
 558     #[inline]
 559     fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
 560         P: FnMut(&Self::Item) -> bool,
 561     {
 562         match self.state {
 563             ChainState::Both => match self.a.find(&mut predicate) {
 564                 None => {
 565                     self.state = ChainState::Back;
 566                     self.b.find(predicate)
 567                 }
 568                 v => v
 569             },
 570             ChainState::Front => self.a.find(predicate),
 571             ChainState::Back => self.b.find(predicate),
 572         }
 573     }
 574
 575     #[inline]
 576     fn last(self) -> Option<A::Item> {
 577         match self.state {
 578             ChainState::Both => {
 579                 // Must exhaust a before b.
 580                 let a_last = self.a.last();
 581                 let b_last = self.b.last();
 582                 b_last.or(a_last)
 583             },
 584             ChainState::Front => self.a.last(),
 585             ChainState::Back => self.b.last()
 586         }
 587     }
 588
 589     #[inline]
 590     fn size_hint(&self) -> (usize, Option<usize>) {
 591         let (a_lower, a_upper) = self.a.size_hint();
 592         let (b_lower, b_upper) = self.b.size_hint();
 593
 594         let lower = a_lower.saturating_add(b_lower);
 595
 596         let upper = match (a_upper, b_upper) {
 597             (Some(x), Some(y)) => x.checked_add(y),
 598             _ => None
 599         };
 600
 601         (lower, upper)
 602     }
 603 }
 604
 605 #[stable(feature = "rust1", since = "1.0.0")]
 606 impl<A, B> DoubleEndedIterator for Chain<A, B> where
 607     A: DoubleEndedIterator,
 608     B: DoubleEndedIterator<Item=A::Item>,
 609 {
 610     #[inline]
 611     fn next_back(&mut self) -> Option<A::Item> {
 612         match self.state {
 613             ChainState::Both => match self.b.next_back() {
 614                 elt @ Some(..) => elt,
 615                 None => {
 616                     self.state = ChainState::Front;
 617                     self.a.next_back()
 618                 }
 619             },
 620             ChainState::Front => self.a.next_back(),
 621             ChainState::Back => self.b.next_back(),
 622         }
 623     }
 624 }
 625
 626 // Note: *both* must be fused to handle double-ended iterators.
 627 #[unstable(feature = "fused", issue = "35602")]
 628 impl<A, B> FusedIterator for Chain<A, B>
 629     where A: FusedIterator,
 630           B: FusedIterator<Item=A::Item>,
 631 {}
 632
 633 /// An iterator that iterates two other iterators simultaneously.
 634 ///
 635 /// This `struct` is created by the [`zip()`] method on [`Iterator`]. See its
 636 /// documentation for more.
 637 ///
 638 /// [`zip()`]: trait.Iterator.html#method.zip
 639 /// [`Iterator`]: trait.Iterator.html
 640 #[derive(Clone, Debug)]
 641 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 642 #[stable(feature = "rust1", since = "1.0.0")]
 643 pub struct Zip<A, B> {
 644     a: A,
 645     b: B,
 646     spec: <(A, B) as ZipImplData>::Data,
 647 }
 648
 649 #[stable(feature = "rust1", since = "1.0.0")]
 650 impl<A, B> Iterator for Zip<A, B> where A: Iterator, B: Iterator
 651 {
 652     type Item = (A::Item, B::Item);
 653
 654     #[inline]
 655     fn next(&mut self) -> Option<Self::Item> {
 656         ZipImpl::next(self)
 657     }
 658
 659     #[inline]
 660     fn size_hint(&self) -> (usize, Option<usize>) {
 661         ZipImpl::size_hint(self)
 662     }
 663 }
 664
 665 #[stable(feature = "rust1", since = "1.0.0")]
 666 impl<A, B> DoubleEndedIterator for Zip<A, B> where
 667     A: DoubleEndedIterator + ExactSizeIterator,
 668     B: DoubleEndedIterator + ExactSizeIterator,
 669 {
 670     #[inline]
 671     fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
 672         ZipImpl::next_back(self)
 673     }
 674 }
 675
 676 // Zip specialization trait
 677 #[doc(hidden)]
 678 trait ZipImpl<A, B> {
 679     type Item;
 680     fn new(a: A, b: B) -> Self;
 681     fn next(&mut self) -> Option<Self::Item>;
 682     fn size_hint(&self) -> (usize, Option<usize>);
 683     fn next_back(&mut self) -> Option<Self::Item>
 684         where A: DoubleEndedIterator + ExactSizeIterator,
 685               B: DoubleEndedIterator + ExactSizeIterator;
 686 }
 687
 688 // Zip specialization data members
 689 #[doc(hidden)]
 690 trait ZipImplData {
 691     type Data: 'static + Clone + Default + fmt::Debug;
 692 }
 693
 694 #[doc(hidden)]
 695 impl<T> ZipImplData for T {
 696     default type Data = ();
 697 }
 698
 699 // General Zip impl
 700 #[doc(hidden)]
 701 impl<A, B> ZipImpl<A, B> for Zip<A, B>
 702     where A: Iterator, B: Iterator
 703 {
 704     type Item = (A::Item, B::Item);
 705     default fn new(a: A, b: B) -> Self {
 706         Zip {
 707             a: a,
 708             b: b,
 709             spec: Default::default(), // unused
 710         }
 711     }
 712
 713     #[inline]
 714     default fn next(&mut self) -> Option<(A::Item, B::Item)> {
 715         self.a.next().and_then(|x| {
 716             self.b.next().and_then(|y| {
 717                 Some((x, y))
 718             })
 719         })
 720     }
 721
 722     #[inline]
 723     default fn next_back(&mut self) -> Option<(A::Item, B::Item)>
 724         where A: DoubleEndedIterator + ExactSizeIterator,
 725               B: DoubleEndedIterator + ExactSizeIterator
 726     {
 727         let a_sz = self.a.len();
 728         let b_sz = self.b.len();
 729         if a_sz != b_sz {
 730             // Adjust a, b to equal length
 731             if a_sz > b_sz {
 732                 for _ in 0..a_sz - b_sz { self.a.next_back(); }
 733             } else {
 734                 for _ in 0..b_sz - a_sz { self.b.next_back(); }
 735             }
 736         }
 737         match (self.a.next_back(), self.b.next_back()) {
 738             (Some(x), Some(y)) => Some((x, y)),
 739             (None, None) => None,
 740             _ => unreachable!(),
 741         }
 742     }
 743
 744     #[inline]
 745     default fn size_hint(&self) -> (usize, Option<usize>) {
 746         let (a_lower, a_upper) = self.a.size_hint();
 747         let (b_lower, b_upper) = self.b.size_hint();
 748
 749         let lower = cmp::min(a_lower, b_lower);
 750
 751         let upper = match (a_upper, b_upper) {
 752             (Some(x), Some(y)) => Some(cmp::min(x,y)),
 753             (Some(x), None) => Some(x),
 754             (None, Some(y)) => Some(y),
 755             (None, None) => None
 756         };
 757
 758         (lower, upper)
 759     }
 760 }
 761
 762 #[doc(hidden)]
 763 #[derive(Default, Debug, Clone)]
 764 struct ZipImplFields {
 765     index: usize,
 766     len: usize,
 767 }
 768
 769 #[doc(hidden)]
 770 impl<A, B> ZipImplData for (A, B)
 771     where A: TrustedRandomAccess, B: TrustedRandomAccess
 772 {
 773     type Data = ZipImplFields;
 774 }
 775
 776 #[doc(hidden)]
 777 impl<A, B> ZipImpl<A, B> for Zip<A, B>
 778     where A: TrustedRandomAccess, B: TrustedRandomAccess
 779 {
 780     fn new(a: A, b: B) -> Self {
 781         let len = cmp::min(a.len(), b.len());
 782         Zip {
 783             a: a,
 784             b: b,
 785             spec: ZipImplFields {
 786                 index: 0,
 787                 len: len,
 788             }
 789         }
 790     }
 791
 792     #[inline]
 793     fn next(&mut self) -> Option<(A::Item, B::Item)> {
 794         if self.spec.index < self.spec.len {
 795             let i = self.spec.index;
 796             self.spec.index += 1;
 797             unsafe {
 798                 Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
 799             }
 800         } else {
 801             None
 802         }
 803     }
 804
 805     #[inline]
 806     fn size_hint(&self) -> (usize, Option<usize>) {
 807         let len = self.spec.len - self.spec.index;
 808         (len, Some(len))
 809     }
 810
 811     #[inline]
 812     fn next_back(&mut self) -> Option<(A::Item, B::Item)>
 813         where A: DoubleEndedIterator + ExactSizeIterator,
 814               B: DoubleEndedIterator + ExactSizeIterator
 815     {
 816         if self.spec.index < self.spec.len {
 817             self.spec.len -= 1;
 818             let i = self.spec.len;
 819             unsafe {
 820                 Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
 821             }
 822         } else {
 823             None
 824         }
 825     }
 826 }
 827
 828 #[stable(feature = "rust1", since = "1.0.0")]
 829 impl<A, B> ExactSizeIterator for Zip<A, B>
 830     where A: ExactSizeIterator, B: ExactSizeIterator {}
 831
 832 #[doc(hidden)]
 833 unsafe impl<A, B> TrustedRandomAccess for Zip<A, B>
 834     where A: TrustedRandomAccess,
 835           B: TrustedRandomAccess,
 836 {
 837     unsafe fn get_unchecked(&mut self, i: usize) -> (A::Item, B::Item) {
 838         (self.a.get_unchecked(i), self.b.get_unchecked(i))
 839     }
 840
 841 }
 842
 843 #[unstable(feature = "fused", issue = "35602")]
 844 impl<A, B> FusedIterator for Zip<A, B>
 845     where A: FusedIterator, B: FusedIterator, {}
 846
 847 /// An iterator that maps the values of `iter` with `f`.
 848 ///
 849 /// This `struct` is created by the [`map()`] method on [`Iterator`]. See its
 850 /// documentation for more.
 851 ///
 852 /// [`map()`]: trait.Iterator.html#method.map
 853 /// [`Iterator`]: trait.Iterator.html
 854 ///
 855 /// # Notes about side effects
 856 ///
 857 /// The [`map()`] iterator implements [`DoubleEndedIterator`], meaning that
 858 /// you can also [`map()`] backwards:
 859 ///
 860 /// ```rust
 861 /// let v: Vec<i32> = vec![1, 2, 3].into_iter().rev().map(|x| x + 1).collect();
 862 ///
 863 /// assert_eq!(v, [4, 3, 2]);
 864 /// ```
 865 ///
 866 /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
 867 ///
 868 /// But if your closure has state, iterating backwards may act in a way you do
 869 /// not expect. Let's go through an example. First, in the forward direction:
 870 ///
 871 /// ```rust
 872 /// let mut c = 0;
 873 ///
 874 /// for pair in vec!['a', 'b', 'c'].into_iter()
 875 ///                                .map(|letter| { c += 1; (letter, c) }) {
 876 ///     println!("{:?}", pair);
 877 /// }
 878 /// ```
 879 ///
 880 /// This will print "('a', 1), ('b', 2), ('c', 3)".
 881 ///
 882 /// Now consider this twist where we add a call to `rev`. This version will
 883 /// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed,
 884 /// but the values of the counter still go in order. This is because `map()` is
 885 /// still being called lazilly on each item, but we are popping items off the
 886 /// back of the vector now, instead of shifting them from the front.
 887 ///
 888 /// ```rust
 889 /// let mut c = 0;
 890 ///
 891 /// for pair in vec!['a', 'b', 'c'].into_iter()
 892 ///                                .map(|letter| { c += 1; (letter, c) })
 893 ///                                .rev() {
 894 ///     println!("{:?}", pair);
 895 /// }
 896 /// ```
 897 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 898 #[stable(feature = "rust1", since = "1.0.0")]
 899 #[derive(Clone)]
 900 pub struct Map<I, F> {
 901     iter: I,
 902     f: F,
 903 }
 904
 905 #[stable(feature = "core_impl_debug", since = "1.9.0")]
 906 impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> {
 907     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 908         f.debug_struct("Map")
 909             .field("iter", &self.iter)
 910             .finish()
 911     }
 912 }
 913
 914 #[stable(feature = "rust1", since = "1.0.0")]
 915 impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
 916     type Item = B;
 917
 918     #[inline]
 919     fn next(&mut self) -> Option<B> {
 920         self.iter.next().map(&mut self.f)
 921     }
 922
 923     #[inline]
 924     fn size_hint(&self) -> (usize, Option<usize>) {
 925         self.iter.size_hint()
 926     }
 927 }
 928
 929 #[stable(feature = "rust1", since = "1.0.0")]
 930 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where
 931     F: FnMut(I::Item) -> B,
 932 {
 933     #[inline]
 934     fn next_back(&mut self) -> Option<B> {
 935         self.iter.next_back().map(&mut self.f)
 936     }
 937 }
 938
 939 #[stable(feature = "rust1", since = "1.0.0")]
 940 impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F>
 941     where F: FnMut(I::Item) -> B {}
 942
 943 #[unstable(feature = "fused", issue = "35602")]
 944 impl<B, I: FusedIterator, F> FusedIterator for Map<I, F>
 945     where F: FnMut(I::Item) -> B {}
 946
 947 /// An iterator that filters the elements of `iter` with `predicate`.
 948 ///
 949 /// This `struct` is created by the [`filter()`] method on [`Iterator`]. See its
 950 /// documentation for more.
 951 ///
 952 /// [`filter()`]: trait.Iterator.html#method.filter
 953 /// [`Iterator`]: trait.Iterator.html
 954 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 955 #[stable(feature = "rust1", since = "1.0.0")]
 956 #[derive(Clone)]
 957 pub struct Filter<I, P> {
 958     iter: I,
 959     predicate: P,
 960 }
 961
 962 #[stable(feature = "core_impl_debug", since = "1.9.0")]
 963 impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
 964     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 965         f.debug_struct("Filter")
 966             .field("iter", &self.iter)
 967             .finish()
 968     }
 969 }
 970
 971 #[stable(feature = "rust1", since = "1.0.0")]
 972 impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {
 973     type Item = I::Item;
 974
 975     #[inline]
 976     fn next(&mut self) -> Option<I::Item> {
 977         for x in self.iter.by_ref() {
 978             if (self.predicate)(&x) {
 979                 return Some(x);
 980             }
 981         }
 982         None
 983     }
 984
 985     #[inline]
 986     fn size_hint(&self) -> (usize, Option<usize>) {
 987         let (_, upper) = self.iter.size_hint();
 988         (0, upper) // can't know a lower bound, due to the predicate
 989     }
 990 }
 991
 992 #[stable(feature = "rust1", since = "1.0.0")]
 993 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
 994     where P: FnMut(&I::Item) -> bool,
 995 {
 996     #[inline]
 997     fn next_back(&mut self) -> Option<I::Item> {
 998         for x in self.iter.by_ref().rev() {
 999             if (self.predicate)(&x) {
1000                 return Some(x);
1001             }
1002         }
1003         None
1004     }
1005 }
1006
1007 #[unstable(feature = "fused", issue = "35602")]
1008 impl<I: FusedIterator, P> FusedIterator for Filter<I, P>
1009     where P: FnMut(&I::Item) -> bool {}
1010
1011 /// An iterator that uses `f` to both filter and map elements from `iter`.
1012 ///
1013 /// This `struct` is created by the [`filter_map()`] method on [`Iterator`]. See its
1014 /// documentation for more.
1015 ///
1016 /// [`filter_map()`]: trait.Iterator.html#method.filter_map
1017 /// [`Iterator`]: trait.Iterator.html
1018 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1019 #[stable(feature = "rust1", since = "1.0.0")]
1020 #[derive(Clone)]
1021 pub struct FilterMap<I, F> {
1022     iter: I,
1023     f: F,
1024 }
1025
1026 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1027 impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> {
1028     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1029         f.debug_struct("FilterMap")
1030             .field("iter", &self.iter)
1031             .finish()
1032     }
1033 }
1034
1035 #[stable(feature = "rust1", since = "1.0.0")]
1036 impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
1037     where F: FnMut(I::Item) -> Option<B>,
1038 {
1039     type Item = B;
1040
1041     #[inline]
1042     fn next(&mut self) -> Option<B> {
1043         for x in self.iter.by_ref() {
1044             if let Some(y) = (self.f)(x) {
1045                 return Some(y);
1046             }
1047         }
1048         None
1049     }
1050
1051     #[inline]
1052     fn size_hint(&self) -> (usize, Option<usize>) {
1053         let (_, upper) = self.iter.size_hint();
1054         (0, upper) // can't know a lower bound, due to the predicate
1055     }
1056 }
1057
1058 #[stable(feature = "rust1", since = "1.0.0")]
1059 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
1060     where F: FnMut(I::Item) -> Option<B>,
1061 {
1062     #[inline]
1063     fn next_back(&mut self) -> Option<B> {
1064         for x in self.iter.by_ref().rev() {
1065             if let Some(y) = (self.f)(x) {
1066                 return Some(y);
1067             }
1068         }
1069         None
1070     }
1071 }
1072
1073 #[unstable(feature = "fused", issue = "35602")]
1074 impl<B, I: FusedIterator, F> FusedIterator for FilterMap<I, F>
1075     where F: FnMut(I::Item) -> Option<B> {}
1076
1077 /// An iterator that yields the current count and the element during iteration.
1078 ///
1079 /// This `struct` is created by the [`enumerate()`] method on [`Iterator`]. See its
1080 /// documentation for more.
1081 ///
1082 /// [`enumerate()`]: trait.Iterator.html#method.enumerate
1083 /// [`Iterator`]: trait.Iterator.html
1084 #[derive(Clone, Debug)]
1085 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1086 #[stable(feature = "rust1", since = "1.0.0")]
1087 pub struct Enumerate<I> {
1088     iter: I,
1089     count: usize,
1090 }
1091
1092 #[stable(feature = "rust1", since = "1.0.0")]
1093 impl<I> Iterator for Enumerate<I> where I: Iterator {
1094     type Item = (usize, <I as Iterator>::Item);
1095
1096     /// # Overflow Behavior
1097     ///
1098     /// The method does no guarding against overflows, so enumerating more than
1099     /// `usize::MAX` elements either produces the wrong result or panics. If
1100     /// debug assertions are enabled, a panic is guaranteed.
1101     ///
1102     /// # Panics
1103     ///
1104     /// Might panic if the index of the element overflows a `usize`.
1105     #[inline]
1106     #[rustc_inherit_overflow_checks]
1107     fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1108         self.iter.next().map(|a| {
1109             let ret = (self.count, a);
1110             // Possible undefined overflow.
1111             self.count += 1;
1112             ret
1113         })
1114     }
1115
1116     #[inline]
1117     fn size_hint(&self) -> (usize, Option<usize>) {
1118         self.iter.size_hint()
1119     }
1120
1121     #[inline]
1122     #[rustc_inherit_overflow_checks]
1123     fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
1124         self.iter.nth(n).map(|a| {
1125             let i = self.count + n;
1126             self.count = i + 1;
1127             (i, a)
1128         })
1129     }
1130
1131     #[inline]
1132     fn count(self) -> usize {
1133         self.iter.count()
1134     }
1135 }
1136
1137 #[stable(feature = "rust1", since = "1.0.0")]
1138 impl<I> DoubleEndedIterator for Enumerate<I> where
1139     I: ExactSizeIterator + DoubleEndedIterator
1140 {
1141     #[inline]
1142     fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1143         self.iter.next_back().map(|a| {
1144             let len = self.iter.len();
1145             // Can safely add, `ExactSizeIterator` promises that the number of
1146             // elements fits into a `usize`.
1147             (self.count + len, a)
1148         })
1149     }
1150 }
1151
1152 #[stable(feature = "rust1", since = "1.0.0")]
1153 impl<I> ExactSizeIterator for Enumerate<I> where I: ExactSizeIterator {}
1154
1155 #[doc(hidden)]
1156 unsafe impl<I> TrustedRandomAccess for Enumerate<I>
1157     where I: TrustedRandomAccess
1158 {
1159     unsafe fn get_unchecked(&mut self, i: usize) -> (usize, I::Item) {
1160         (self.count + i, self.iter.get_unchecked(i))
1161     }
1162 }
1163
1164 #[unstable(feature = "fused", issue = "35602")]
1165 impl<I> FusedIterator for Enumerate<I> where I: FusedIterator {}
1166
1167 /// An iterator with a `peek()` that returns an optional reference to the next
1168 /// element.
1169 ///
1170 /// This `struct` is created by the [`peekable()`] method on [`Iterator`]. See its
1171 /// documentation for more.
1172 ///
1173 /// [`peekable()`]: trait.Iterator.html#method.peekable
1174 /// [`Iterator`]: trait.Iterator.html
1175 #[derive(Clone, Debug)]
1176 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1177 #[stable(feature = "rust1", since = "1.0.0")]
1178 pub struct Peekable<I: Iterator> {
1179     iter: I,
1180     peeked: Option<I::Item>,
1181 }
1182
1183 #[stable(feature = "rust1", since = "1.0.0")]
1184 impl<I: Iterator> Iterator for Peekable<I> {
1185     type Item = I::Item;
1186
1187     #[inline]
1188     fn next(&mut self) -> Option<I::Item> {
1189         match self.peeked {
1190             Some(_) => self.peeked.take(),
1191             None => self.iter.next(),
1192         }
1193     }
1194
1195     #[inline]
1196     #[rustc_inherit_overflow_checks]
1197     fn count(self) -> usize {
1198         (if self.peeked.is_some() { 1 } else { 0 }) + self.iter.count()
1199     }
1200
1201     #[inline]
1202     fn nth(&mut self, n: usize) -> Option<I::Item> {
1203         match self.peeked {
1204             Some(_) if n == 0 => self.peeked.take(),
1205             Some(_) => {
1206                 self.peeked = None;
1207                 self.iter.nth(n-1)
1208             },
1209             None => self.iter.nth(n)
1210         }
1211     }
1212
1213     #[inline]
1214     fn last(self) -> Option<I::Item> {
1215         self.iter.last().or(self.peeked)
1216     }
1217
1218     #[inline]
1219     fn size_hint(&self) -> (usize, Option<usize>) {
1220         let (lo, hi) = self.iter.size_hint();
1221         if self.peeked.is_some() {
1222             let lo = lo.saturating_add(1);
1223             let hi = hi.and_then(|x| x.checked_add(1));
1224             (lo, hi)
1225         } else {
1226             (lo, hi)
1227         }
1228     }
1229 }
1230
1231 #[stable(feature = "rust1", since = "1.0.0")]
1232 impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
1233
1234 #[unstable(feature = "fused", issue = "35602")]
1235 impl<I: FusedIterator> FusedIterator for Peekable<I> {}
1236
1237 impl<I: Iterator> Peekable<I> {
1238     /// Returns a reference to the next() value without advancing the iterator.
1239     ///
1240     /// Like [`next()`], if there is a value, it is wrapped in a `Some(T)`.
1241     /// But if the iteration is over, `None` is returned.
1242     ///
1243     /// [`next()`]: trait.Iterator.html#tymethod.next
1244     ///
1245     /// Because `peek()` returns a reference, and many iterators iterate over
1246     /// references, there can be a possibly confusing situation where the
1247     /// return value is a double reference. You can see this effect in the
1248     /// examples below.
1249     ///
1250     /// # Examples
1251     ///
1252     /// Basic usage:
1253     ///
1254     /// ```
1255     /// let xs = [1, 2, 3];
1256     ///
1257     /// let mut iter = xs.iter().peekable();
1258     ///
1259     /// // peek() lets us see into the future
1260     /// assert_eq!(iter.peek(), Some(&&1));
1261     /// assert_eq!(iter.next(), Some(&1));
1262     ///
1263     /// assert_eq!(iter.next(), Some(&2));
1264     ///
1265     /// // The iterator does not advance even if we `peek` multiple times
1266     /// assert_eq!(iter.peek(), Some(&&3));
1267     /// assert_eq!(iter.peek(), Some(&&3));
1268     ///
1269     /// assert_eq!(iter.next(), Some(&3));
1270     ///
1271     /// // After the iterator is finished, so is `peek()`
1272     /// assert_eq!(iter.peek(), None);
1273     /// assert_eq!(iter.next(), None);
1274     /// ```
1275     #[inline]
1276     #[stable(feature = "rust1", since = "1.0.0")]
1277     pub fn peek(&mut self) -> Option<&I::Item> {
1278         if self.peeked.is_none() {
1279             self.peeked = self.iter.next();
1280         }
1281         match self.peeked {
1282             Some(ref value) => Some(value),
1283             None => None,
1284         }
1285     }
1286 }
1287
1288 /// An iterator that rejects elements while `predicate` is true.
1289 ///
1290 /// This `struct` is created by the [`skip_while()`] method on [`Iterator`]. See its
1291 /// documentation for more.
1292 ///
1293 /// [`skip_while()`]: trait.Iterator.html#method.skip_while
1294 /// [`Iterator`]: trait.Iterator.html
1295 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1296 #[stable(feature = "rust1", since = "1.0.0")]
1297 #[derive(Clone)]
1298 pub struct SkipWhile<I, P> {
1299     iter: I,
1300     flag: bool,
1301     predicate: P,
1302 }
1303
1304 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1305 impl<I: fmt::Debug, P> fmt::Debug for SkipWhile<I, P> {
1306     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1307         f.debug_struct("SkipWhile")
1308             .field("iter", &self.iter)
1309             .field("flag", &self.flag)
1310             .finish()
1311     }
1312 }
1313
1314 #[stable(feature = "rust1", since = "1.0.0")]
1315 impl<I: Iterator, P> Iterator for SkipWhile<I, P>
1316     where P: FnMut(&I::Item) -> bool
1317 {
1318     type Item = I::Item;
1319
1320     #[inline]
1321     fn next(&mut self) -> Option<I::Item> {
1322         for x in self.iter.by_ref() {
1323             if self.flag || !(self.predicate)(&x) {
1324                 self.flag = true;
1325                 return Some(x);
1326             }
1327         }
1328         None
1329     }
1330
1331     #[inline]
1332     fn size_hint(&self) -> (usize, Option<usize>) {
1333         let (_, upper) = self.iter.size_hint();
1334         (0, upper) // can't know a lower bound, due to the predicate
1335     }
1336 }
1337
1338 #[unstable(feature = "fused", issue = "35602")]
1339 impl<I, P> FusedIterator for SkipWhile<I, P>
1340     where I: FusedIterator, P: FnMut(&I::Item) -> bool {}
1341
1342 /// An iterator that only accepts elements while `predicate` is true.
1343 ///
1344 /// This `struct` is created by the [`take_while()`] method on [`Iterator`]. See its
1345 /// documentation for more.
1346 ///
1347 /// [`take_while()`]: trait.Iterator.html#method.take_while
1348 /// [`Iterator`]: trait.Iterator.html
1349 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1350 #[stable(feature = "rust1", since = "1.0.0")]
1351 #[derive(Clone)]
1352 pub struct TakeWhile<I, P> {
1353     iter: I,
1354     flag: bool,
1355     predicate: P,
1356 }
1357
1358 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1359 impl<I: fmt::Debug, P> fmt::Debug for TakeWhile<I, P> {
1360     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1361         f.debug_struct("TakeWhile")
1362             .field("iter", &self.iter)
1363             .field("flag", &self.flag)
1364             .finish()
1365     }
1366 }
1367
1368 #[stable(feature = "rust1", since = "1.0.0")]
1369 impl<I: Iterator, P> Iterator for TakeWhile<I, P>
1370     where P: FnMut(&I::Item) -> bool
1371 {
1372     type Item = I::Item;
1373
1374     #[inline]
1375     fn next(&mut self) -> Option<I::Item> {
1376         if self.flag {
1377             None
1378         } else {
1379             self.iter.next().and_then(|x| {
1380                 if (self.predicate)(&x) {
1381                     Some(x)
1382                 } else {
1383                     self.flag = true;
1384                     None
1385                 }
1386             })
1387         }
1388     }
1389
1390     #[inline]
1391     fn size_hint(&self) -> (usize, Option<usize>) {
1392         let (_, upper) = self.iter.size_hint();
1393         (0, upper) // can't know a lower bound, due to the predicate
1394     }
1395 }
1396
1397 #[unstable(feature = "fused", issue = "35602")]
1398 impl<I, P> FusedIterator for TakeWhile<I, P>
1399     where I: FusedIterator, P: FnMut(&I::Item) -> bool {}
1400
1401 /// An iterator that skips over `n` elements of `iter`.
1402 ///
1403 /// This `struct` is created by the [`skip()`] method on [`Iterator`]. See its
1404 /// documentation for more.
1405 ///
1406 /// [`skip()`]: trait.Iterator.html#method.skip
1407 /// [`Iterator`]: trait.Iterator.html
1408 #[derive(Clone, Debug)]
1409 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1410 #[stable(feature = "rust1", since = "1.0.0")]
1411 pub struct Skip<I> {
1412     iter: I,
1413     n: usize
1414 }
1415
1416 #[stable(feature = "rust1", since = "1.0.0")]
1417 impl<I> Iterator for Skip<I> where I: Iterator {
1418     type Item = <I as Iterator>::Item;
1419
1420     #[inline]
1421     fn next(&mut self) -> Option<I::Item> {
1422         if self.n == 0 {
1423             self.iter.next()
1424         } else {
1425             let old_n = self.n;
1426             self.n = 0;
1427             self.iter.nth(old_n)
1428         }
1429     }
1430
1431     #[inline]
1432     fn nth(&mut self, n: usize) -> Option<I::Item> {
1433         // Can't just add n + self.n due to overflow.
1434         if self.n == 0 {
1435             self.iter.nth(n)
1436         } else {
1437             let to_skip = self.n;
1438             self.n = 0;
1439             // nth(n) skips n+1
1440             if self.iter.nth(to_skip-1).is_none() {
1441                 return None;
1442             }
1443             self.iter.nth(n)
1444         }
1445     }
1446
1447     #[inline]
1448     fn count(self) -> usize {
1449         self.iter.count().saturating_sub(self.n)
1450     }
1451
1452     #[inline]
1453     fn last(mut self) -> Option<I::Item> {
1454         if self.n == 0 {
1455             self.iter.last()
1456         } else {
1457             let next = self.next();
1458             if next.is_some() {
1459                 // recurse. n should be 0.
1460                 self.last().or(next)
1461             } else {
1462                 None
1463             }
1464         }
1465     }
1466
1467     #[inline]
1468     fn size_hint(&self) -> (usize, Option<usize>) {
1469         let (lower, upper) = self.iter.size_hint();
1470
1471         let lower = lower.saturating_sub(self.n);
1472         let upper = upper.map(|x| x.saturating_sub(self.n));
1473
1474         (lower, upper)
1475     }
1476 }
1477
1478 #[stable(feature = "rust1", since = "1.0.0")]
1479 impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
1480
1481 #[stable(feature = "double_ended_skip_iterator", since = "1.8.0")]
1482 impl<I> DoubleEndedIterator for Skip<I> where I: DoubleEndedIterator + ExactSizeIterator {
1483     fn next_back(&mut self) -> Option<Self::Item> {
1484         if self.len() > 0 {
1485             self.iter.next_back()
1486         } else {
1487             None
1488         }
1489     }
1490 }
1491
1492 #[unstable(feature = "fused", issue = "35602")]
1493 impl<I> FusedIterator for Skip<I> where I: FusedIterator {}
1494
1495 /// An iterator that only iterates over the first `n` iterations of `iter`.
1496 ///
1497 /// This `struct` is created by the [`take()`] method on [`Iterator`]. See its
1498 /// documentation for more.
1499 ///
1500 /// [`take()`]: trait.Iterator.html#method.take
1501 /// [`Iterator`]: trait.Iterator.html
1502 #[derive(Clone, Debug)]
1503 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1504 #[stable(feature = "rust1", since = "1.0.0")]
1505 pub struct Take<I> {
1506     iter: I,
1507     n: usize
1508 }
1509
1510 #[stable(feature = "rust1", since = "1.0.0")]
1511 impl<I> Iterator for Take<I> where I: Iterator{
1512     type Item = <I as Iterator>::Item;
1513
1514     #[inline]
1515     fn next(&mut self) -> Option<<I as Iterator>::Item> {
1516         if self.n != 0 {
1517             self.n -= 1;
1518             self.iter.next()
1519         } else {
1520             None
1521         }
1522     }
1523
1524     #[inline]
1525     fn nth(&mut self, n: usize) -> Option<I::Item> {
1526         if self.n > n {
1527             self.n -= n + 1;
1528             self.iter.nth(n)
1529         } else {
1530             if self.n > 0 {
1531                 self.iter.nth(self.n - 1);
1532                 self.n = 0;
1533             }
1534             None
1535         }
1536     }
1537
1538     #[inline]
1539     fn size_hint(&self) -> (usize, Option<usize>) {
1540         let (lower, upper) = self.iter.size_hint();
1541
1542         let lower = cmp::min(lower, self.n);
1543
1544         let upper = match upper {
1545             Some(x) if x < self.n => Some(x),
1546             _ => Some(self.n)
1547         };
1548
1549         (lower, upper)
1550     }
1551 }
1552
1553 #[stable(feature = "rust1", since = "1.0.0")]
1554 impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
1555
1556 #[unstable(feature = "fused", issue = "35602")]
1557 impl<I> FusedIterator for Take<I> where I: FusedIterator {}
1558
1559 /// An iterator to maintain state while iterating another iterator.
1560 ///
1561 /// This `struct` is created by the [`scan()`] method on [`Iterator`]. See its
1562 /// documentation for more.
1563 ///
1564 /// [`scan()`]: trait.Iterator.html#method.scan
1565 /// [`Iterator`]: trait.Iterator.html
1566 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1567 #[stable(feature = "rust1", since = "1.0.0")]
1568 #[derive(Clone)]
1569 pub struct Scan<I, St, F> {
1570     iter: I,
1571     f: F,
1572     state: St,
1573 }
1574
1575 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1576 impl<I: fmt::Debug, St: fmt::Debug, F> fmt::Debug for Scan<I, St, F> {
1577     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1578         f.debug_struct("Scan")
1579             .field("iter", &self.iter)
1580             .field("state", &self.state)
1581             .finish()
1582     }
1583 }
1584
1585 #[stable(feature = "rust1", since = "1.0.0")]
1586 impl<B, I, St, F> Iterator for Scan<I, St, F> where
1587     I: Iterator,
1588     F: FnMut(&mut St, I::Item) -> Option<B>,
1589 {
1590     type Item = B;
1591
1592     #[inline]
1593     fn next(&mut self) -> Option<B> {
1594         self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
1595     }
1596
1597     #[inline]
1598     fn size_hint(&self) -> (usize, Option<usize>) {
1599         let (_, upper) = self.iter.size_hint();
1600         (0, upper) // can't know a lower bound, due to the scan function
1601     }
1602 }
1603
1604 #[unstable(feature = "fused", issue = "35602")]
1605 impl<B, I, St, F> FusedIterator for Scan<I, St, F>
1606     where I: FusedIterator, F: FnMut(&mut St, I::Item) -> Option<B> {}
1607
1608 /// An iterator that maps each element to an iterator, and yields the elements
1609 /// of the produced iterators.
1610 ///
1611 /// This `struct` is created by the [`flat_map()`] method on [`Iterator`]. See its
1612 /// documentation for more.
1613 ///
1614 /// [`flat_map()`]: trait.Iterator.html#method.flat_map
1615 /// [`Iterator`]: trait.Iterator.html
1616 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1617 #[stable(feature = "rust1", since = "1.0.0")]
1618 #[derive(Clone)]
1619 pub struct FlatMap<I, U: IntoIterator, F> {
1620     iter: I,
1621     f: F,
1622     frontiter: Option<U::IntoIter>,
1623     backiter: Option<U::IntoIter>,
1624 }
1625
1626 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1627 impl<I: fmt::Debug, U: IntoIterator, F> fmt::Debug for FlatMap<I, U, F>
1628     where U::IntoIter: fmt::Debug
1629 {
1630     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1631         f.debug_struct("FlatMap")
1632             .field("iter", &self.iter)
1633             .field("frontiter", &self.frontiter)
1634             .field("backiter", &self.backiter)
1635             .finish()
1636     }
1637 }
1638
1639 #[stable(feature = "rust1", since = "1.0.0")]
1640 impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F>
1641     where F: FnMut(I::Item) -> U,
1642 {
1643     type Item = U::Item;
1644
1645     #[inline]
1646     fn next(&mut self) -> Option<U::Item> {
1647         loop {
1648             if let Some(ref mut inner) = self.frontiter {
1649                 if let Some(x) = inner.by_ref().next() {
1650                     return Some(x)
1651                 }
1652             }
1653             match self.iter.next().map(&mut self.f) {
1654                 None => return self.backiter.as_mut().and_then(|it| it.next()),
1655                 next => self.frontiter = next.map(IntoIterator::into_iter),
1656             }
1657         }
1658     }
1659
1660     #[inline]
1661     fn size_hint(&self) -> (usize, Option<usize>) {
1662         let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
1663         let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
1664         let lo = flo.saturating_add(blo);
1665         match (self.iter.size_hint(), fhi, bhi) {
1666             ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
1667             _ => (lo, None)
1668         }
1669     }
1670 }
1671
1672 #[stable(feature = "rust1", since = "1.0.0")]
1673 impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F> where
1674     F: FnMut(I::Item) -> U,
1675     U: IntoIterator,
1676     U::IntoIter: DoubleEndedIterator
1677 {
1678     #[inline]
1679     fn next_back(&mut self) -> Option<U::Item> {
1680         loop {
1681             if let Some(ref mut inner) = self.backiter {
1682                 if let Some(y) = inner.next_back() {
1683                     return Some(y)
1684                 }
1685             }
1686             match self.iter.next_back().map(&mut self.f) {
1687                 None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
1688                 next => self.backiter = next.map(IntoIterator::into_iter),
1689             }
1690         }
1691     }
1692 }
1693
1694 #[unstable(feature = "fused", issue = "35602")]
1695 impl<I, U, F> FusedIterator for FlatMap<I, U, F>
1696     where I: FusedIterator, U: IntoIterator, F: FnMut(I::Item) -> U {}
1697
1698 /// An iterator that yields `None` forever after the underlying iterator
1699 /// yields `None` once.
1700 ///
1701 /// This `struct` is created by the [`fuse()`] method on [`Iterator`]. See its
1702 /// documentation for more.
1703 ///
1704 /// [`fuse()`]: trait.Iterator.html#method.fuse
1705 /// [`Iterator`]: trait.Iterator.html
1706 #[derive(Clone, Debug)]
1707 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1708 #[stable(feature = "rust1", since = "1.0.0")]
1709 pub struct Fuse<I> {
1710     iter: I,
1711     done: bool
1712 }
1713
1714 #[unstable(feature = "fused", issue = "35602")]
1715 impl<I> FusedIterator for Fuse<I> where I: Iterator {}
1716
1717 #[stable(feature = "rust1", since = "1.0.0")]
1718 impl<I> Iterator for Fuse<I> where I: Iterator {
1719     type Item = <I as Iterator>::Item;
1720
1721     #[inline]
1722     default fn next(&mut self) -> Option<<I as Iterator>::Item> {
1723         if self.done {
1724             None
1725         } else {
1726             let next = self.iter.next();
1727             self.done = next.is_none();
1728             next
1729         }
1730     }
1731
1732     #[inline]
1733     default fn nth(&mut self, n: usize) -> Option<I::Item> {
1734         if self.done {
1735             None
1736         } else {
1737             let nth = self.iter.nth(n);
1738             self.done = nth.is_none();
1739             nth
1740         }
1741     }
1742
1743     #[inline]
1744     default fn last(self) -> Option<I::Item> {
1745         if self.done {
1746             None
1747         } else {
1748             self.iter.last()
1749         }
1750     }
1751
1752     #[inline]
1753     default fn count(self) -> usize {
1754         if self.done {
1755             0
1756         } else {
1757             self.iter.count()
1758         }
1759     }
1760
1761     #[inline]
1762     default fn size_hint(&self) -> (usize, Option<usize>) {
1763         if self.done {
1764             (0, Some(0))
1765         } else {
1766             self.iter.size_hint()
1767         }
1768     }
1769 }
1770
1771 #[stable(feature = "rust1", since = "1.0.0")]
1772 impl<I> DoubleEndedIterator for Fuse<I> where I: DoubleEndedIterator {
1773     #[inline]
1774     default fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
1775         if self.done {
1776             None
1777         } else {
1778             let next = self.iter.next_back();
1779             self.done = next.is_none();
1780             next
1781         }
1782     }
1783 }
1784
1785 unsafe impl<I> TrustedRandomAccess for Fuse<I>
1786     where I: TrustedRandomAccess,
1787 {
1788     unsafe fn get_unchecked(&mut self, i: usize) -> I::Item {
1789         self.iter.get_unchecked(i)
1790     }
1791 }
1792
1793 #[unstable(feature = "fused", issue = "35602")]
1794 impl<I> Iterator for Fuse<I> where I: FusedIterator {
1795     #[inline]
1796     fn next(&mut self) -> Option<<I as Iterator>::Item> {
1797         self.iter.next()
1798     }
1799
1800     #[inline]
1801     fn nth(&mut self, n: usize) -> Option<I::Item> {
1802         self.iter.nth(n)
1803     }
1804
1805     #[inline]
1806     fn last(self) -> Option<I::Item> {
1807         self.iter.last()
1808     }
1809
1810     #[inline]
1811     fn count(self) -> usize {
1812         self.iter.count()
1813     }
1814
1815     #[inline]
1816     fn size_hint(&self) -> (usize, Option<usize>) {
1817         self.iter.size_hint()
1818     }
1819 }
1820
1821 #[unstable(feature = "fused", reason = "recently added", issue = "35602")]
1822 impl<I> DoubleEndedIterator for Fuse<I>
1823     where I: DoubleEndedIterator + FusedIterator
1824 {
1825     #[inline]
1826     fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
1827         self.iter.next_back()
1828     }
1829 }
1830
1831
1832 #[stable(feature = "rust1", since = "1.0.0")]
1833 impl<I> ExactSizeIterator for Fuse<I> where I: ExactSizeIterator {}
1834
1835 /// An iterator that calls a function with a reference to each element before
1836 /// yielding it.
1837 ///
1838 /// This `struct` is created by the [`inspect()`] method on [`Iterator`]. See its
1839 /// documentation for more.
1840 ///
1841 /// [`inspect()`]: trait.Iterator.html#method.inspect
1842 /// [`Iterator`]: trait.Iterator.html
1843 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1844 #[stable(feature = "rust1", since = "1.0.0")]
1845 #[derive(Clone)]
1846 pub struct Inspect<I, F> {
1847     iter: I,
1848     f: F,
1849 }
1850
1851 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1852 impl<I: fmt::Debug, F> fmt::Debug for Inspect<I, F> {
1853     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1854         f.debug_struct("Inspect")
1855             .field("iter", &self.iter)
1856             .finish()
1857     }
1858 }
1859
1860 impl<I: Iterator, F> Inspect<I, F> where F: FnMut(&I::Item) {
1861     #[inline]
1862     fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
1863         if let Some(ref a) = elt {
1864             (self.f)(a);
1865         }
1866
1867         elt
1868     }
1869 }
1870
1871 #[stable(feature = "rust1", since = "1.0.0")]
1872 impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) {
1873     type Item = I::Item;
1874
1875     #[inline]
1876     fn next(&mut self) -> Option<I::Item> {
1877         let next = self.iter.next();
1878         self.do_inspect(next)
1879     }
1880
1881     #[inline]
1882     fn size_hint(&self) -> (usize, Option<usize>) {
1883         self.iter.size_hint()
1884     }
1885 }
1886
1887 #[stable(feature = "rust1", since = "1.0.0")]
1888 impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
1889     where F: FnMut(&I::Item),
1890 {
1891     #[inline]
1892     fn next_back(&mut self) -> Option<I::Item> {
1893         let next = self.iter.next_back();
1894         self.do_inspect(next)
1895     }
1896 }
1897
1898 #[stable(feature = "rust1", since = "1.0.0")]
1899 impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F>
1900     where F: FnMut(&I::Item) {}
1901
1902 #[unstable(feature = "fused", issue = "35602")]
1903 impl<I: FusedIterator, F> FusedIterator for Inspect<I, F>
1904     where F: FnMut(&I::Item) {}