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