src/libcore/iter/mod.rs

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