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