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