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