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