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