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