src/libcore/iter/traits.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 use ops::{Mul, Add, Try};
  11 use num::Wrapping;
  12
  13 use super::LoopState;
  14
  15 /// Conversion from an `Iterator`.
  16 ///
  17 /// By implementing `FromIterator` for a type, you define how it will be
  18 /// created from an iterator. This is common for types which describe a
  19 /// collection of some kind.
  20 ///
  21 /// `FromIterator`'s [`from_iter`] is rarely called explicitly, and is instead
  22 /// used through [`Iterator`]'s [`collect`] method. See [`collect`]'s
  23 /// documentation for more examples.
  24 ///
  25 /// [`from_iter`]: #tymethod.from_iter
  26 /// [`Iterator`]: trait.Iterator.html
  27 /// [`collect`]: trait.Iterator.html#method.collect
  28 ///
  29 /// See also: [`IntoIterator`].
  30 ///
  31 /// [`IntoIterator`]: trait.IntoIterator.html
  32 ///
  33 /// # Examples
  34 ///
  35 /// Basic usage:
  36 ///
  37 /// ```
  38 /// use std::iter::FromIterator;
  39 ///
  40 /// let five_fives = std::iter::repeat(5).take(5);
  41 ///
  42 /// let v = Vec::from_iter(five_fives);
  43 ///
  44 /// assert_eq!(v, vec![5, 5, 5, 5, 5]);
  45 /// ```
  46 ///
  47 /// Using [`collect`] to implicitly use `FromIterator`:
  48 ///
  49 /// ```
  50 /// let five_fives = std::iter::repeat(5).take(5);
  51 ///
  52 /// let v: Vec<i32> = five_fives.collect();
  53 ///
  54 /// assert_eq!(v, vec![5, 5, 5, 5, 5]);
  55 /// ```
  56 ///
  57 /// Implementing `FromIterator` for your type:
  58 ///
  59 /// ```
  60 /// use std::iter::FromIterator;
  61 ///
  62 /// // A sample collection, that's just a wrapper over Vec<T>
  63 /// #[derive(Debug)]
  64 /// struct MyCollection(Vec<i32>);
  65 ///
  66 /// // Let's give it some methods so we can create one and add things
  67 /// // to it.
  68 /// impl MyCollection {
  69 ///     fn new() -> MyCollection {
  70 ///         MyCollection(Vec::new())
  71 ///     }
  72 ///
  73 ///     fn add(&mut self, elem: i32) {
  74 ///         self.0.push(elem);
  75 ///     }
  76 /// }
  77 ///
  78 /// // and we'll implement FromIterator
  79 /// impl FromIterator<i32> for MyCollection {
  80 ///     fn from_iter<I: IntoIterator<Item=i32>>(iter: I) -> Self {
  81 ///         let mut c = MyCollection::new();
  82 ///
  83 ///         for i in iter {
  84 ///             c.add(i);
  85 ///         }
  86 ///
  87 ///         c
  88 ///     }
  89 /// }
  90 ///
  91 /// // Now we can make a new iterator...
  92 /// let iter = (0..5).into_iter();
  93 ///
  94 /// // ... and make a MyCollection out of it
  95 /// let c = MyCollection::from_iter(iter);
  96 ///
  97 /// assert_eq!(c.0, vec![0, 1, 2, 3, 4]);
  98 ///
  99 /// // collect works too!
 100 ///
 101 /// let iter = (0..5).into_iter();
 102 /// let c: MyCollection = iter.collect();
 103 ///
 104 /// assert_eq!(c.0, vec![0, 1, 2, 3, 4]);
 105 /// ```
 106 #[stable(feature = "rust1", since = "1.0.0")]
 107 #[rustc_on_unimplemented(
 108     message="a collection of type `{Self}` cannot be built from an iterator \
 109              over elements of type `{A}`",
 110     label="a collection of type `{Self}` cannot be built from `std::iter::Iterator<Item={A}>`",
 111 )]
 112 pub trait FromIterator<A>: Sized {
 113     /// Creates a value from an iterator.
 114     ///
 115     /// See the [module-level documentation] for more.
 116     ///
 117     /// [module-level documentation]: index.html
 118     ///
 119     /// # Examples
 120     ///
 121     /// Basic usage:
 122     ///
 123     /// ```
 124     /// use std::iter::FromIterator;
 125     ///
 126     /// let five_fives = std::iter::repeat(5).take(5);
 127     ///
 128     /// let v = Vec::from_iter(five_fives);
 129     ///
 130     /// assert_eq!(v, vec![5, 5, 5, 5, 5]);
 131     /// ```
 132     #[stable(feature = "rust1", since = "1.0.0")]
 133     fn from_iter<T: IntoIterator<Item=A>>(iter: T) -> Self;
 134 }
 135
 136 /// Conversion into an `Iterator`.
 137 ///
 138 /// By implementing `IntoIterator` for a type, you define how it will be
 139 /// converted to an iterator. This is common for types which describe a
 140 /// collection of some kind.
 141 ///
 142 /// One benefit of implementing `IntoIterator` is that your type will [work
 143 /// with Rust's `for` loop syntax](index.html#for-loops-and-intoiterator).
 144 ///
 145 /// See also: [`FromIterator`].
 146 ///
 147 /// [`FromIterator`]: trait.FromIterator.html
 148 ///
 149 /// # Examples
 150 ///
 151 /// Basic usage:
 152 ///
 153 /// ```
 154 /// let v = vec![1, 2, 3];
 155 /// let mut iter = v.into_iter();
 156 ///
 157 /// assert_eq!(Some(1), iter.next());
 158 /// assert_eq!(Some(2), iter.next());
 159 /// assert_eq!(Some(3), iter.next());
 160 /// assert_eq!(None, iter.next());
 161 /// ```
 162 /// Implementing `IntoIterator` for your type:
 163 ///
 164 /// ```
 165 /// // A sample collection, that's just a wrapper over Vec<T>
 166 /// #[derive(Debug)]
 167 /// struct MyCollection(Vec<i32>);
 168 ///
 169 /// // Let's give it some methods so we can create one and add things
 170 /// // to it.
 171 /// impl MyCollection {
 172 ///     fn new() -> MyCollection {
 173 ///         MyCollection(Vec::new())
 174 ///     }
 175 ///
 176 ///     fn add(&mut self, elem: i32) {
 177 ///         self.0.push(elem);
 178 ///     }
 179 /// }
 180 ///
 181 /// // and we'll implement IntoIterator
 182 /// impl IntoIterator for MyCollection {
 183 ///     type Item = i32;
 184 ///     type IntoIter = ::std::vec::IntoIter<i32>;
 185 ///
 186 ///     fn into_iter(self) -> Self::IntoIter {
 187 ///         self.0.into_iter()
 188 ///     }
 189 /// }
 190 ///
 191 /// // Now we can make a new collection...
 192 /// let mut c = MyCollection::new();
 193 ///
 194 /// // ... add some stuff to it ...
 195 /// c.add(0);
 196 /// c.add(1);
 197 /// c.add(2);
 198 ///
 199 /// // ... and then turn it into an Iterator:
 200 /// for (i, n) in c.into_iter().enumerate() {
 201 ///     assert_eq!(i as i32, n);
 202 /// }
 203 /// ```
 204 ///
 205 /// It is common to use `IntoIterator` as a trait bound. This allows
 206 /// the input collection type to change, so long as it is still an
 207 /// iterator. Additional bounds can be specified by restricting on
 208 /// `Item`:
 209 ///
 210 /// ```rust
 211 /// fn collect_as_strings<T>(collection: T) -> Vec<String>
 212 ///     where T: IntoIterator,
 213 ///           T::Item : std::fmt::Debug,
 214 /// {
 215 ///     collection
 216 ///         .into_iter()
 217 ///         .map(|item| format!("{:?}", item))
 218 ///         .collect()
 219 /// }
 220 /// ```
 221 #[stable(feature = "rust1", since = "1.0.0")]
 222 pub trait IntoIterator {
 223     /// The type of the elements being iterated over.
 224     #[stable(feature = "rust1", since = "1.0.0")]
 225     type Item;
 226
 227     /// Which kind of iterator are we turning this into?
 228     #[stable(feature = "rust1", since = "1.0.0")]
 229     type IntoIter: Iterator<Item=Self::Item>;
 230
 231     /// Creates an iterator from a value.
 232     ///
 233     /// See the [module-level documentation] for more.
 234     ///
 235     /// [module-level documentation]: index.html
 236     ///
 237     /// # Examples
 238     ///
 239     /// Basic usage:
 240     ///
 241     /// ```
 242     /// let v = vec![1, 2, 3];
 243     /// let mut iter = v.into_iter();
 244     ///
 245     /// assert_eq!(Some(1), iter.next());
 246     /// assert_eq!(Some(2), iter.next());
 247     /// assert_eq!(Some(3), iter.next());
 248     /// assert_eq!(None, iter.next());
 249     /// ```
 250     #[stable(feature = "rust1", since = "1.0.0")]
 251     fn into_iter(self) -> Self::IntoIter;
 252 }
 253
 254 #[stable(feature = "rust1", since = "1.0.0")]
 255 impl<I: Iterator> IntoIterator for I {
 256     type Item = I::Item;
 257     type IntoIter = I;
 258
 259     fn into_iter(self) -> I {
 260         self
 261     }
 262 }
 263
 264 /// Extend a collection with the contents of an iterator.
 265 ///
 266 /// Iterators produce a series of values, and collections can also be thought
 267 /// of as a series of values. The `Extend` trait bridges this gap, allowing you
 268 /// to extend a collection by including the contents of that iterator. When
 269 /// extending a collection with an already existing key, that entry is updated
 270 /// or, in the case of collections that permit multiple entries with equal
 271 /// keys, that entry is inserted.
 272 ///
 273 /// # Examples
 274 ///
 275 /// Basic usage:
 276 ///
 277 /// ```
 278 /// // You can extend a String with some chars:
 279 /// let mut message = String::from("The first three letters are: ");
 280 ///
 281 /// message.extend(&['a', 'b', 'c']);
 282 ///
 283 /// assert_eq!("abc", &message[29..32]);
 284 /// ```
 285 ///
 286 /// Implementing `Extend`:
 287 ///
 288 /// ```
 289 /// // A sample collection, that's just a wrapper over Vec<T>
 290 /// #[derive(Debug)]
 291 /// struct MyCollection(Vec<i32>);
 292 ///
 293 /// // Let's give it some methods so we can create one and add things
 294 /// // to it.
 295 /// impl MyCollection {
 296 ///     fn new() -> MyCollection {
 297 ///         MyCollection(Vec::new())
 298 ///     }
 299 ///
 300 ///     fn add(&mut self, elem: i32) {
 301 ///         self.0.push(elem);
 302 ///     }
 303 /// }
 304 ///
 305 /// // since MyCollection has a list of i32s, we implement Extend for i32
 306 /// impl Extend<i32> for MyCollection {
 307 ///
 308 ///     // This is a bit simpler with the concrete type signature: we can call
 309 ///     // extend on anything which can be turned into an Iterator which gives
 310 ///     // us i32s. Because we need i32s to put into MyCollection.
 311 ///     fn extend<T: IntoIterator<Item=i32>>(&mut self, iter: T) {
 312 ///
 313 ///         // The implementation is very straightforward: loop through the
 314 ///         // iterator, and add() each element to ourselves.
 315 ///         for elem in iter {
 316 ///             self.add(elem);
 317 ///         }
 318 ///     }
 319 /// }
 320 ///
 321 /// let mut c = MyCollection::new();
 322 ///
 323 /// c.add(5);
 324 /// c.add(6);
 325 /// c.add(7);
 326 ///
 327 /// // let's extend our collection with three more numbers
 328 /// c.extend(vec![1, 2, 3]);
 329 ///
 330 /// // we've added these elements onto the end
 331 /// assert_eq!("MyCollection([5, 6, 7, 1, 2, 3])", format!("{:?}", c));
 332 /// ```
 333 #[stable(feature = "rust1", since = "1.0.0")]
 334 pub trait Extend<A> {
 335     /// Extends a collection with the contents of an iterator.
 336     ///
 337     /// As this is the only method for this trait, the [trait-level] docs
 338     /// contain more details.
 339     ///
 340     /// [trait-level]: trait.Extend.html
 341     ///
 342     /// # Examples
 343     ///
 344     /// Basic usage:
 345     ///
 346     /// ```
 347     /// // You can extend a String with some chars:
 348     /// let mut message = String::from("abc");
 349     ///
 350     /// message.extend(['d', 'e', 'f'].iter());
 351     ///
 352     /// assert_eq!("abcdef", &message);
 353     /// ```
 354     #[stable(feature = "rust1", since = "1.0.0")]
 355     fn extend<T: IntoIterator<Item=A>>(&mut self, iter: T);
 356 }
 357
 358 #[stable(feature = "extend_for_unit", since = "1.28.0")]
 359 impl Extend<()> for () {
 360     fn extend<T: IntoIterator<Item = ()>>(&mut self, iter: T) {
 361         iter.into_iter().for_each(drop)
 362     }
 363 }
 364
 365 /// An iterator able to yield elements from both ends.
 366 ///
 367 /// Something that implements `DoubleEndedIterator` has one extra capability
 368 /// over something that implements [`Iterator`]: the ability to also take
 369 /// `Item`s from the back, as well as the front.
 370 ///
 371 /// It is important to note that both back and forth work on the same range,
 372 /// and do not cross: iteration is over when they meet in the middle.
 373 ///
 374 /// In a similar fashion to the [`Iterator`] protocol, once a
 375 /// `DoubleEndedIterator` returns `None` from a `next_back()`, calling it again
 376 /// may or may not ever return `Some` again. `next()` and `next_back()` are
 377 /// interchangeable for this purpose.
 378 ///
 379 /// [`Iterator`]: trait.Iterator.html
 380 ///
 381 /// # Examples
 382 ///
 383 /// Basic usage:
 384 ///
 385 /// ```
 386 /// let numbers = vec![1, 2, 3, 4, 5, 6];
 387 ///
 388 /// let mut iter = numbers.iter();
 389 ///
 390 /// assert_eq!(Some(&1), iter.next());
 391 /// assert_eq!(Some(&6), iter.next_back());
 392 /// assert_eq!(Some(&5), iter.next_back());
 393 /// assert_eq!(Some(&2), iter.next());
 394 /// assert_eq!(Some(&3), iter.next());
 395 /// assert_eq!(Some(&4), iter.next());
 396 /// assert_eq!(None, iter.next());
 397 /// assert_eq!(None, iter.next_back());
 398 /// ```
 399 #[stable(feature = "rust1", since = "1.0.0")]
 400 pub trait DoubleEndedIterator: Iterator {
 401     /// Removes and returns an element from the end of the iterator.
 402     ///
 403     /// Returns `None` when there are no more elements.
 404     ///
 405     /// The [trait-level] docs contain more details.
 406     ///
 407     /// [trait-level]: trait.DoubleEndedIterator.html
 408     ///
 409     /// # Examples
 410     ///
 411     /// Basic usage:
 412     ///
 413     /// ```
 414     /// let numbers = vec![1, 2, 3, 4, 5, 6];
 415     ///
 416     /// let mut iter = numbers.iter();
 417     ///
 418     /// assert_eq!(Some(&1), iter.next());
 419     /// assert_eq!(Some(&6), iter.next_back());
 420     /// assert_eq!(Some(&5), iter.next_back());
 421     /// assert_eq!(Some(&2), iter.next());
 422     /// assert_eq!(Some(&3), iter.next());
 423     /// assert_eq!(Some(&4), iter.next());
 424     /// assert_eq!(None, iter.next());
 425     /// assert_eq!(None, iter.next_back());
 426     /// ```
 427     #[stable(feature = "rust1", since = "1.0.0")]
 428     fn next_back(&mut self) -> Option<Self::Item>;
 429
 430     /// Returns the `n`th element from the end of the iterator.
 431     ///
 432     /// This is essentially the reversed version of [`nth`]. Although like most indexing
 433     /// operations, the count starts from zero, so `nth_back(0)` returns the first value fro
 434     /// the end, `nth_back(1)` the second, and so on.
 435     ///
 436     /// Note that all elements between the end and the returned element will be
 437     /// consumed, including the returned element. This also means that calling
 438     /// `nth_back(0)` multiple times on the same iterator will return different
 439     /// elements.
 440     ///
 441     /// `nth_back()` will return [`None`] if `n` is greater than or equal to the length of the
 442     /// iterator.
 443     ///
 444     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 445     /// [`nth`]: ../../std/iter/trait.Iterator.html#method.nth
 446     ///
 447     /// # Examples
 448     ///
 449     /// Basic usage:
 450     ///
 451     /// ```
 452     /// #![feature(iter_nth_back)]
 453     /// let a = [1, 2, 3];
 454     /// assert_eq!(a.iter().nth_back(2), Some(&1));
 455     /// ```
 456     ///
 457     /// Calling `nth_back()` multiple times doesn't rewind the iterator:
 458     ///
 459     /// ```
 460     /// #![feature(iter_nth_back)]
 461     /// let a = [1, 2, 3];
 462     ///
 463     /// let mut iter = a.iter();
 464     ///
 465     /// assert_eq!(iter.nth_back(1), Some(&2));
 466     /// assert_eq!(iter.nth_back(1), None);
 467     /// ```
 468     ///
 469     /// Returning `None` if there are less than `n + 1` elements:
 470     ///
 471     /// ```
 472     /// #![feature(iter_nth_back)]
 473     /// let a = [1, 2, 3];
 474     /// assert_eq!(a.iter().nth_back(10), None);
 475     /// ```
 476     #[inline]
 477     #[unstable(feature = "iter_nth_back", issue = "56995")]
 478     fn nth_back(&mut self, mut n: usize) -> Option<Self::Item> {
 479         for x in self.rev() {
 480             if n == 0 { return Some(x) }
 481             n -= 1;
 482         }
 483         None
 484     }
 485
 486     /// This is the reverse version of [`try_fold()`]: it takes elements
 487     /// starting from the back of the iterator.
 488     ///
 489     /// [`try_fold()`]: trait.Iterator.html#method.try_fold
 490     ///
 491     /// # Examples
 492     ///
 493     /// Basic usage:
 494     ///
 495     /// ```
 496     /// let a = ["1", "2", "3"];
 497     /// let sum = a.iter()
 498     ///     .map(|&s| s.parse::<i32>())
 499     ///     .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
 500     /// assert_eq!(sum, Ok(6));
 501     /// ```
 502     ///
 503     /// Short-circuiting:
 504     ///
 505     /// ```
 506     /// let a = ["1", "rust", "3"];
 507     /// let mut it = a.iter();
 508     /// let sum = it
 509     ///     .by_ref()
 510     ///     .map(|&s| s.parse::<i32>())
 511     ///     .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
 512     /// assert!(sum.is_err());
 513     ///
 514     /// // Because it short-circuited, the remaining elements are still
 515     /// // available through the iterator.
 516     /// assert_eq!(it.next_back(), Some(&"1"));
 517     /// ```
 518     #[inline]
 519     #[stable(feature = "iterator_try_fold", since = "1.27.0")]
 520     fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
 521     where
 522         Self: Sized,
 523         F: FnMut(B, Self::Item) -> R,
 524         R: Try<Ok=B>
 525     {
 526         let mut accum = init;
 527         while let Some(x) = self.next_back() {
 528             accum = f(accum, x)?;
 529         }
 530         Try::from_ok(accum)
 531     }
 532
 533     /// An iterator method that reduces the iterator's elements to a single,
 534     /// final value, starting from the back.
 535     ///
 536     /// This is the reverse version of [`fold()`]: it takes elements starting from
 537     /// the back of the iterator.
 538     ///
 539     /// `rfold()` takes two arguments: an initial value, and a closure with two
 540     /// arguments: an 'accumulator', and an element. The closure returns the value that
 541     /// the accumulator should have for the next iteration.
 542     ///
 543     /// The initial value is the value the accumulator will have on the first
 544     /// call.
 545     ///
 546     /// After applying this closure to every element of the iterator, `rfold()`
 547     /// returns the accumulator.
 548     ///
 549     /// This operation is sometimes called 'reduce' or 'inject'.
 550     ///
 551     /// Folding is useful whenever you have a collection of something, and want
 552     /// to produce a single value from it.
 553     ///
 554     /// [`fold()`]: trait.Iterator.html#method.fold
 555     ///
 556     /// # Examples
 557     ///
 558     /// Basic usage:
 559     ///
 560     /// ```
 561     /// let a = [1, 2, 3];
 562     ///
 563     /// // the sum of all of the elements of a
 564     /// let sum = a.iter()
 565     ///            .rfold(0, |acc, &x| acc + x);
 566     ///
 567     /// assert_eq!(sum, 6);
 568     /// ```
 569     ///
 570     /// This example builds a string, starting with an initial value
 571     /// and continuing with each element from the back until the front:
 572     ///
 573     /// ```
 574     /// let numbers = [1, 2, 3, 4, 5];
 575     ///
 576     /// let zero = "0".to_string();
 577     ///
 578     /// let result = numbers.iter().rfold(zero, |acc, &x| {
 579     ///     format!("({} + {})", x, acc)
 580     /// });
 581     ///
 582     /// assert_eq!(result, "(1 + (2 + (3 + (4 + (5 + 0)))))");
 583     /// ```
 584     #[inline]
 585     #[stable(feature = "iter_rfold", since = "1.27.0")]
 586     fn rfold<B, F>(mut self, accum: B, mut f: F) -> B
 587     where
 588         Self: Sized,
 589         F: FnMut(B, Self::Item) -> B,
 590     {
 591         self.try_rfold(accum, move |acc, x| Ok::<B, !>(f(acc, x))).unwrap()
 592     }
 593
 594     /// Searches for an element of an iterator from the back that satisfies a predicate.
 595     ///
 596     /// `rfind()` takes a closure that returns `true` or `false`. It applies
 597     /// this closure to each element of the iterator, starting at the end, and if any
 598     /// of them return `true`, then `rfind()` returns [`Some(element)`]. If they all return
 599     /// `false`, it returns [`None`].
 600     ///
 601     /// `rfind()` is short-circuiting; in other words, it will stop processing
 602     /// as soon as the closure returns `true`.
 603     ///
 604     /// Because `rfind()` takes a reference, and many iterators iterate over
 605     /// references, this leads to a possibly confusing situation where the
 606     /// argument is a double reference. You can see this effect in the
 607     /// examples below, with `&&x`.
 608     ///
 609     /// [`Some(element)`]: ../../std/option/enum.Option.html#variant.Some
 610     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 611     ///
 612     /// # Examples
 613     ///
 614     /// Basic usage:
 615     ///
 616     /// ```
 617     /// let a = [1, 2, 3];
 618     ///
 619     /// assert_eq!(a.iter().rfind(|&&x| x == 2), Some(&2));
 620     ///
 621     /// assert_eq!(a.iter().rfind(|&&x| x == 5), None);
 622     /// ```
 623     ///
 624     /// Stopping at the first `true`:
 625     ///
 626     /// ```
 627     /// let a = [1, 2, 3];
 628     ///
 629     /// let mut iter = a.iter();
 630     ///
 631     /// assert_eq!(iter.rfind(|&&x| x == 2), Some(&2));
 632     ///
 633     /// // we can still use `iter`, as there are more elements.
 634     /// assert_eq!(iter.next_back(), Some(&1));
 635     /// ```
 636     #[inline]
 637     #[stable(feature = "iter_rfind", since = "1.27.0")]
 638     fn rfind<P>(&mut self, mut predicate: P) -> Option<Self::Item>
 639     where
 640         Self: Sized,
 641         P: FnMut(&Self::Item) -> bool
 642     {
 643         self.try_rfold((), move |(), x| {
 644             if predicate(&x) { LoopState::Break(x) }
 645             else { LoopState::Continue(()) }
 646         }).break_value()
 647     }
 648 }
 649
 650 #[stable(feature = "rust1", since = "1.0.0")]
 651 impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I {
 652     fn next_back(&mut self) -> Option<I::Item> {
 653         (**self).next_back()
 654     }
 655     fn nth_back(&mut self, n: usize) -> Option<I::Item> {
 656         (**self).nth_back(n)
 657     }
 658 }
 659
 660 /// An iterator that knows its exact length.
 661 ///
 662 /// Many [`Iterator`]s don't know how many times they will iterate, but some do.
 663 /// If an iterator knows how many times it can iterate, providing access to
 664 /// that information can be useful. For example, if you want to iterate
 665 /// backwards, a good start is to know where the end is.
 666 ///
 667 /// When implementing an `ExactSizeIterator`, you must also implement
 668 /// [`Iterator`]. When doing so, the implementation of [`size_hint`] *must*
 669 /// return the exact size of the iterator.
 670 ///
 671 /// [`Iterator`]: trait.Iterator.html
 672 /// [`size_hint`]: trait.Iterator.html#method.size_hint
 673 ///
 674 /// The [`len`] method has a default implementation, so you usually shouldn't
 675 /// implement it. However, you may be able to provide a more performant
 676 /// implementation than the default, so overriding it in this case makes sense.
 677 ///
 678 /// [`len`]: #method.len
 679 ///
 680 /// # Examples
 681 ///
 682 /// Basic usage:
 683 ///
 684 /// ```
 685 /// // a finite range knows exactly how many times it will iterate
 686 /// let five = 0..5;
 687 ///
 688 /// assert_eq!(5, five.len());
 689 /// ```
 690 ///
 691 /// In the [module level docs][moddocs], we implemented an [`Iterator`],
 692 /// `Counter`. Let's implement `ExactSizeIterator` for it as well:
 693 ///
 694 /// [moddocs]: index.html
 695 ///
 696 /// ```
 697 /// # struct Counter {
 698 /// #     count: usize,
 699 /// # }
 700 /// # impl Counter {
 701 /// #     fn new() -> Counter {
 702 /// #         Counter { count: 0 }
 703 /// #     }
 704 /// # }
 705 /// # impl Iterator for Counter {
 706 /// #     type Item = usize;
 707 /// #     fn next(&mut self) -> Option<usize> {
 708 /// #         self.count += 1;
 709 /// #         if self.count < 6 {
 710 /// #             Some(self.count)
 711 /// #         } else {
 712 /// #             None
 713 /// #         }
 714 /// #     }
 715 /// # }
 716 /// impl ExactSizeIterator for Counter {
 717 ///     // We can easily calculate the remaining number of iterations.
 718 ///     fn len(&self) -> usize {
 719 ///         5 - self.count
 720 ///     }
 721 /// }
 722 ///
 723 /// // And now we can use it!
 724 ///
 725 /// let counter = Counter::new();
 726 ///
 727 /// assert_eq!(5, counter.len());
 728 /// ```
 729 #[stable(feature = "rust1", since = "1.0.0")]
 730 pub trait ExactSizeIterator: Iterator {
 731     /// Returns the exact number of times the iterator will iterate.
 732     ///
 733     /// This method has a default implementation, so you usually should not
 734     /// implement it directly. However, if you can provide a more efficient
 735     /// implementation, you can do so. See the [trait-level] docs for an
 736     /// example.
 737     ///
 738     /// This function has the same safety guarantees as the [`size_hint`]
 739     /// function.
 740     ///
 741     /// [trait-level]: trait.ExactSizeIterator.html
 742     /// [`size_hint`]: trait.Iterator.html#method.size_hint
 743     ///
 744     /// # Examples
 745     ///
 746     /// Basic usage:
 747     ///
 748     /// ```
 749     /// // a finite range knows exactly how many times it will iterate
 750     /// let five = 0..5;
 751     ///
 752     /// assert_eq!(5, five.len());
 753     /// ```
 754     #[inline]
 755     #[stable(feature = "rust1", since = "1.0.0")]
 756     fn len(&self) -> usize {
 757         let (lower, upper) = self.size_hint();
 758         // Note: This assertion is overly defensive, but it checks the invariant
 759         // guaranteed by the trait. If this trait were rust-internal,
 760         // we could use debug_assert!; assert_eq! will check all Rust user
 761         // implementations too.
 762         assert_eq!(upper, Some(lower));
 763         lower
 764     }
 765
 766     /// Returns whether the iterator is empty.
 767     ///
 768     /// This method has a default implementation using `self.len()`, so you
 769     /// don't need to implement it yourself.
 770     ///
 771     /// # Examples
 772     ///
 773     /// Basic usage:
 774     ///
 775     /// ```
 776     /// #![feature(exact_size_is_empty)]
 777     ///
 778     /// let mut one_element = std::iter::once(0);
 779     /// assert!(!one_element.is_empty());
 780     ///
 781     /// assert_eq!(one_element.next(), Some(0));
 782     /// assert!(one_element.is_empty());
 783     ///
 784     /// assert_eq!(one_element.next(), None);
 785     /// ```
 786     #[inline]
 787     #[unstable(feature = "exact_size_is_empty", issue = "35428")]
 788     fn is_empty(&self) -> bool {
 789         self.len() == 0
 790     }
 791 }
 792
 793 #[stable(feature = "rust1", since = "1.0.0")]
 794 impl<I: ExactSizeIterator + ?Sized> ExactSizeIterator for &mut I {
 795     fn len(&self) -> usize {
 796         (**self).len()
 797     }
 798     fn is_empty(&self) -> bool {
 799         (**self).is_empty()
 800     }
 801 }
 802
 803 /// Trait to represent types that can be created by summing up an iterator.
 804 ///
 805 /// This trait is used to implement the [`sum`] method on iterators. Types which
 806 /// implement the trait can be generated by the [`sum`] method. Like
 807 /// [`FromIterator`] this trait should rarely be called directly and instead
 808 /// interacted with through [`Iterator::sum`].
 809 ///
 810 /// [`sum`]: ../../std/iter/trait.Sum.html#tymethod.sum
 811 /// [`FromIterator`]: ../../std/iter/trait.FromIterator.html
 812 /// [`Iterator::sum`]: ../../std/iter/trait.Iterator.html#method.sum
 813 #[stable(feature = "iter_arith_traits", since = "1.12.0")]
 814 pub trait Sum<A = Self>: Sized {
 815     /// Method which takes an iterator and generates `Self` from the elements by
 816     /// "summing up" the items.
 817     #[stable(feature = "iter_arith_traits", since = "1.12.0")]
 818     fn sum<I: Iterator<Item=A>>(iter: I) -> Self;
 819 }
 820
 821 /// Trait to represent types that can be created by multiplying elements of an
 822 /// iterator.
 823 ///
 824 /// This trait is used to implement the [`product`] method on iterators. Types
 825 /// which implement the trait can be generated by the [`product`] method. Like
 826 /// [`FromIterator`] this trait should rarely be called directly and instead
 827 /// interacted with through [`Iterator::product`].
 828 ///
 829 /// [`product`]: ../../std/iter/trait.Product.html#tymethod.product
 830 /// [`FromIterator`]: ../../std/iter/trait.FromIterator.html
 831 /// [`Iterator::product`]: ../../std/iter/trait.Iterator.html#method.product
 832 #[stable(feature = "iter_arith_traits", since = "1.12.0")]
 833 pub trait Product<A = Self>: Sized {
 834     /// Method which takes an iterator and generates `Self` from the elements by
 835     /// multiplying the items.
 836     #[stable(feature = "iter_arith_traits", since = "1.12.0")]
 837     fn product<I: Iterator<Item=A>>(iter: I) -> Self;
 838 }
 839
 840 // N.B., explicitly use Add and Mul here to inherit overflow checks
 841 macro_rules! integer_sum_product {
 842     (@impls $zero:expr, $one:expr, #[$attr:meta], $($a:ty)*) => ($(
 843         #[$attr]
 844         impl Sum for $a {
 845             fn sum<I: Iterator<Item=$a>>(iter: I) -> $a {
 846                 iter.fold($zero, Add::add)
 847             }
 848         }
 849
 850         #[$attr]
 851         impl Product for $a {
 852             fn product<I: Iterator<Item=$a>>(iter: I) -> $a {
 853                 iter.fold($one, Mul::mul)
 854             }
 855         }
 856
 857         #[$attr]
 858         impl<'a> Sum<&'a $a> for $a {
 859             fn sum<I: Iterator<Item=&'a $a>>(iter: I) -> $a {
 860                 iter.fold($zero, Add::add)
 861             }
 862         }
 863
 864         #[$attr]
 865         impl<'a> Product<&'a $a> for $a {
 866             fn product<I: Iterator<Item=&'a $a>>(iter: I) -> $a {
 867                 iter.fold($one, Mul::mul)
 868             }
 869         }
 870     )*);
 871     ($($a:ty)*) => (
 872         integer_sum_product!(@impls 0, 1,
 873                 #[stable(feature = "iter_arith_traits", since = "1.12.0")],
 874                 $($a)+);
 875         integer_sum_product!(@impls Wrapping(0), Wrapping(1),
 876                 #[stable(feature = "wrapping_iter_arith", since = "1.14.0")],
 877                 $(Wrapping<$a>)+);
 878     );
 879 }
 880
 881 macro_rules! float_sum_product {
 882     ($($a:ident)*) => ($(
 883         #[stable(feature = "iter_arith_traits", since = "1.12.0")]
 884         impl Sum for $a {
 885             fn sum<I: Iterator<Item=$a>>(iter: I) -> $a {
 886                 iter.fold(0.0, |a, b| a + b)
 887             }
 888         }
 889
 890         #[stable(feature = "iter_arith_traits", since = "1.12.0")]
 891         impl Product for $a {
 892             fn product<I: Iterator<Item=$a>>(iter: I) -> $a {
 893                 iter.fold(1.0, |a, b| a * b)
 894             }
 895         }
 896
 897         #[stable(feature = "iter_arith_traits", since = "1.12.0")]
 898         impl<'a> Sum<&'a $a> for $a {
 899             fn sum<I: Iterator<Item=&'a $a>>(iter: I) -> $a {
 900                 iter.fold(0.0, |a, b| a + *b)
 901             }
 902         }
 903
 904         #[stable(feature = "iter_arith_traits", since = "1.12.0")]
 905         impl<'a> Product<&'a $a> for $a {
 906             fn product<I: Iterator<Item=&'a $a>>(iter: I) -> $a {
 907                 iter.fold(1.0, |a, b| a * *b)
 908             }
 909         }
 910     )*)
 911 }
 912
 913 integer_sum_product! { i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize }
 914 float_sum_product! { f32 f64 }
 915
 916 /// An iterator adapter that produces output as long as the underlying
 917 /// iterator produces `Result::Ok` values.
 918 ///
 919 /// If an error is encountered, the iterator stops and the error is
 920 /// stored. The error may be recovered later via `reconstruct`.
 921 struct ResultShunt<I, E> {
 922     iter: I,
 923     error: Option<E>,
 924 }
 925
 926 impl<I, T, E> ResultShunt<I, E>
 927     where I: Iterator<Item = Result<T, E>>
 928 {
 929     /// Process the given iterator as if it yielded a `T` instead of a
 930     /// `Result<T, _>`. Any errors will stop the inner iterator and
 931     /// the overall result will be an error.
 932     pub fn process<F, U>(iter: I, mut f: F) -> Result<U, E>
 933         where F: FnMut(&mut Self) -> U
 934     {
 935         let mut shunt = ResultShunt::new(iter);
 936         let value = f(shunt.by_ref());
 937         shunt.reconstruct(value)
 938     }
 939
 940     fn new(iter: I) -> Self {
 941         ResultShunt {
 942             iter,
 943             error: None,
 944         }
 945     }
 946
 947     /// Consume the adapter and rebuild a `Result` value. This should
 948     /// *always* be called, otherwise any potential error would be
 949     /// lost.
 950     fn reconstruct<U>(self, val: U) -> Result<U, E> {
 951         match self.error {
 952             None => Ok(val),
 953             Some(e) => Err(e),
 954         }
 955     }
 956 }
 957
 958 impl<I, T, E> Iterator for ResultShunt<I, E>
 959     where I: Iterator<Item = Result<T, E>>
 960 {
 961     type Item = T;
 962
 963     fn next(&mut self) -> Option<Self::Item> {
 964         match self.iter.next() {
 965             Some(Ok(v)) => Some(v),
 966             Some(Err(e)) => {
 967                 self.error = Some(e);
 968                 None
 969             }
 970             None => None,
 971         }
 972     }
 973
 974     fn size_hint(&self) -> (usize, Option<usize>) {
 975         if self.error.is_some() {
 976             (0, Some(0))
 977         } else {
 978             let (_, upper) = self.iter.size_hint();
 979             (0, upper)
 980         }
 981     }
 982 }
 983
 984 #[stable(feature = "iter_arith_traits_result", since="1.16.0")]
 985 impl<T, U, E> Sum<Result<U, E>> for Result<T, E>
 986     where T: Sum<U>,
 987 {
 988     /// Takes each element in the `Iterator`: if it is an `Err`, no further
 989     /// elements are taken, and the `Err` is returned. Should no `Err` occur,
 990     /// the sum of all elements is returned.
 991     ///
 992     /// # Examples
 993     ///
 994     /// This sums up every integer in a vector, rejecting the sum if a negative
 995     /// element is encountered:
 996     ///
 997     /// ```
 998     /// let v = vec![1, 2];
 999     /// let res: Result<i32, &'static str> = v.iter().map(|&x: &i32|
1000     ///     if x < 0 { Err("Negative element found") }
1001     ///     else { Ok(x) }
1002     /// ).sum();
1003     /// assert_eq!(res, Ok(3));
1004     /// ```
1005     fn sum<I>(iter: I) -> Result<T, E>
1006         where I: Iterator<Item = Result<U, E>>,
1007     {
1008         ResultShunt::process(iter, |i| i.sum())
1009     }
1010 }
1011
1012 #[stable(feature = "iter_arith_traits_result", since="1.16.0")]
1013 impl<T, U, E> Product<Result<U, E>> for Result<T, E>
1014     where T: Product<U>,
1015 {
1016     /// Takes each element in the `Iterator`: if it is an `Err`, no further
1017     /// elements are taken, and the `Err` is returned. Should no `Err` occur,
1018     /// the product of all elements is returned.
1019     fn product<I>(iter: I) -> Result<T, E>
1020         where I: Iterator<Item = Result<U, E>>,
1021     {
1022         ResultShunt::process(iter, |i| i.product())
1023     }
1024 }
1025
1026 /// An iterator that always continues to yield `None` when exhausted.
1027 ///
1028 /// Calling next on a fused iterator that has returned `None` once is guaranteed
1029 /// to return [`None`] again. This trait should be implemented by all iterators
1030 /// that behave this way because it allows optimizing [`Iterator::fuse`].
1031 ///
1032 /// Note: In general, you should not use `FusedIterator` in generic bounds if
1033 /// you need a fused iterator. Instead, you should just call [`Iterator::fuse`]
1034 /// on the iterator. If the iterator is already fused, the additional [`Fuse`]
1035 /// wrapper will be a no-op with no performance penalty.
1036 ///
1037 /// [`None`]: ../../std/option/enum.Option.html#variant.None
1038 /// [`Iterator::fuse`]: ../../std/iter/trait.Iterator.html#method.fuse
1039 /// [`Fuse`]: ../../std/iter/struct.Fuse.html
1040 #[stable(feature = "fused", since = "1.26.0")]
1041 pub trait FusedIterator: Iterator {}
1042
1043 #[stable(feature = "fused", since = "1.26.0")]
1044 impl<I: FusedIterator + ?Sized> FusedIterator for &mut I {}
1045
1046 /// An iterator that reports an accurate length using size_hint.
1047 ///
1048 /// The iterator reports a size hint where it is either exact
1049 /// (lower bound is equal to upper bound), or the upper bound is [`None`].
1050 /// The upper bound must only be [`None`] if the actual iterator length is
1051 /// larger than [`usize::MAX`]. In that case, the lower bound must be
1052 /// [`usize::MAX`], resulting in a [`.size_hint`] of `(usize::MAX, None)`.
1053 ///
1054 /// The iterator must produce exactly the number of elements it reported
1055 /// or diverge before reaching the end.
1056 ///
1057 /// # Safety
1058 ///
1059 /// This trait must only be implemented when the contract is upheld.
1060 /// Consumers of this trait must inspect [`.size_hint`]’s upper bound.
1061 ///
1062 /// [`None`]: ../../std/option/enum.Option.html#variant.None
1063 /// [`usize::MAX`]: ../../std/usize/constant.MAX.html
1064 /// [`.size_hint`]: ../../std/iter/trait.Iterator.html#method.size_hint
1065 #[unstable(feature = "trusted_len", issue = "37572")]
1066 pub unsafe trait TrustedLen : Iterator {}
1067
1068 #[unstable(feature = "trusted_len", issue = "37572")]
1069 unsafe impl<I: TrustedLen + ?Sized> TrustedLen for &mut I {}