// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
-use ops::{Mul, Add};
+use ops::{Mul, Add, Try};
use num::Wrapping;
+use super::{AlwaysOk, LoopState};
+
/// Conversion from an `Iterator`.
///
/// By implementing `FromIterator` for a type, you define how it will be
/// created from an iterator. This is common for types which describe a
/// collection of some kind.
///
-/// `FromIterator`'s [`from_iter()`] is rarely called explicitly, and is instead
-/// used through [`Iterator`]'s [`collect()`] method. See [`collect()`]'s
+/// `FromIterator`'s [`from_iter`] is rarely called explicitly, and is instead
+/// used through [`Iterator`]'s [`collect`] method. See [`collect`]'s
/// documentation for more examples.
///
-/// [`from_iter()`]: #tymethod.from_iter
+/// [`from_iter`]: #tymethod.from_iter
/// [`Iterator`]: trait.Iterator.html
-/// [`collect()`]: trait.Iterator.html#method.collect
+/// [`collect`]: trait.Iterator.html#method.collect
///
/// See also: [`IntoIterator`].
///
/// assert_eq!(v, vec![5, 5, 5, 5, 5]);
/// ```
///
-/// Using [`collect()`] to implicitly use `FromIterator`:
+/// Using [`collect`] to implicitly use `FromIterator`:
///
/// ```
/// let five_fives = std::iter::repeat(5).take(5);
///
/// See the [module-level documentation] for more.
///
- /// [module-level documentation]: trait.FromIterator.html
+ /// [module-level documentation]: index.html
///
/// # Examples
///
///
/// ```
/// let v = vec![1, 2, 3];
-///
/// let mut iter = v.into_iter();
///
-/// let n = iter.next();
-/// assert_eq!(Some(1), n);
-///
-/// let n = iter.next();
-/// assert_eq!(Some(2), n);
-///
-/// let n = iter.next();
-/// assert_eq!(Some(3), n);
-///
-/// let n = iter.next();
-/// assert_eq!(None, n);
+/// assert_eq!(Some(1), iter.next());
+/// assert_eq!(Some(2), iter.next());
+/// assert_eq!(Some(3), iter.next());
+/// assert_eq!(None, iter.next());
/// ```
-///
/// Implementing `IntoIterator` for your type:
///
/// ```
/// assert_eq!(i as i32, n);
/// }
/// ```
+///
+/// It is common to use `IntoIterator` as a trait bound. This allows
+/// the input collection type to change, so long as it is still an
+/// iterator. Additional bounds can be specified by restricting on
+/// `Item`:
+///
+/// ```rust
+/// fn collect_as_strings<T>(collection: T) -> Vec<String>
+/// where T: IntoIterator,
+/// T::Item : std::fmt::Debug,
+/// {
+/// collection
+/// .into_iter()
+/// .map(|item| format!("{:?}", item))
+/// .collect()
+/// }
+/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub trait IntoIterator {
/// The type of the elements being iterated over.
///
/// See the [module-level documentation] for more.
///
- /// [module-level documentation]: trait.IntoIterator.html
+ /// [module-level documentation]: index.html
///
/// # Examples
///
///
/// ```
/// let v = vec![1, 2, 3];
- ///
/// let mut iter = v.into_iter();
///
- /// let n = iter.next();
- /// assert_eq!(Some(1), n);
- ///
- /// let n = iter.next();
- /// assert_eq!(Some(2), n);
- ///
- /// let n = iter.next();
- /// assert_eq!(Some(3), n);
- ///
- /// let n = iter.next();
- /// assert_eq!(None, n);
+ /// assert_eq!(Some(1), iter.next());
+ /// assert_eq!(Some(2), iter.next());
+ /// assert_eq!(Some(3), iter.next());
+ /// assert_eq!(None, iter.next());
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
fn into_iter(self) -> Self::IntoIter;
/// In a similar fashion to the [`Iterator`] protocol, once a
/// `DoubleEndedIterator` returns `None` from a `next_back()`, calling it again
/// may or may not ever return `Some` again. `next()` and `next_back()` are
-/// interchangable for this purpose.
+/// interchangeable for this purpose.
///
/// [`Iterator`]: trait.Iterator.html
///
#[stable(feature = "rust1", since = "1.0.0")]
fn next_back(&mut self) -> Option<Self::Item>;
+ /// This is the reverse version of [`try_fold()`]: it takes elements
+ /// starting from the back of the iterator.
+ ///
+ /// [`try_fold()`]: trait.Iterator.html#method.try_fold
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// #![feature(iterator_try_fold)]
+ /// let a = ["1", "2", "3"];
+ /// let sum = a.iter()
+ /// .map(|&s| s.parse::<i32>())
+ /// .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
+ /// assert_eq!(sum, Ok(6));
+ /// ```
+ ///
+ /// Short-circuiting:
+ ///
+ /// ```
+ /// #![feature(iterator_try_fold)]
+ /// let a = ["1", "rust", "3"];
+ /// let mut it = a.iter();
+ /// let sum = it
+ /// .by_ref()
+ /// .map(|&s| s.parse::<i32>())
+ /// .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
+ /// assert!(sum.is_err());
+ ///
+ /// // Because it short-circuited, the remaining elements are still
+ /// // available through the iterator.
+ /// assert_eq!(it.next_back(), Some(&"1"));
+ /// ```
+ #[inline]
+ #[unstable(feature = "iterator_try_fold", issue = "45594")]
+ fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
+ Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
+ {
+ let mut accum = init;
+ while let Some(x) = self.next_back() {
+ accum = f(accum, x)?;
+ }
+ Try::from_ok(accum)
+ }
+
+ /// An iterator method that reduces the iterator's elements to a single,
+ /// final value, starting from the back.
+ ///
+ /// This is the reverse version of [`fold()`]: it takes elements starting from
+ /// the back of the iterator.
+ ///
+ /// `rfold()` takes two arguments: an initial value, and a closure with two
+ /// arguments: an 'accumulator', and an element. The closure returns the value that
+ /// the accumulator should have for the next iteration.
+ ///
+ /// The initial value is the value the accumulator will have on the first
+ /// call.
+ ///
+ /// After applying this closure to every element of the iterator, `rfold()`
+ /// returns the accumulator.
+ ///
+ /// This operation is sometimes called 'reduce' or 'inject'.
+ ///
+ /// Folding is useful whenever you have a collection of something, and want
+ /// to produce a single value from it.
+ ///
+ /// [`fold()`]: trait.Iterator.html#method.fold
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// #![feature(iter_rfold)]
+ /// let a = [1, 2, 3];
+ ///
+ /// // the sum of all of the elements of a
+ /// let sum = a.iter()
+ /// .rfold(0, |acc, &x| acc + x);
+ ///
+ /// assert_eq!(sum, 6);
+ /// ```
+ ///
+ /// This example builds a string, starting with an initial value
+ /// and continuing with each element from the back until the front:
+ ///
+ /// ```
+ /// #![feature(iter_rfold)]
+ /// let numbers = [1, 2, 3, 4, 5];
+ ///
+ /// let zero = "0".to_string();
+ ///
+ /// let result = numbers.iter().rfold(zero, |acc, &x| {
+ /// format!("({} + {})", x, acc)
+ /// });
+ ///
+ /// assert_eq!(result, "(1 + (2 + (3 + (4 + (5 + 0)))))");
+ /// ```
+ #[inline]
+ #[unstable(feature = "iter_rfold", issue = "44705")]
+ fn rfold<B, F>(mut self, accum: B, mut f: F) -> B where
+ Self: Sized, F: FnMut(B, Self::Item) -> B,
+ {
+ self.try_rfold(accum, move |acc, x| AlwaysOk(f(acc, x))).0
+ }
+
/// Searches for an element of an iterator from the right that satisfies a predicate.
///
/// `rfind()` takes a closure that returns `true` or `false`. It applies
Self: Sized,
P: FnMut(&Self::Item) -> bool
{
- for x in self.by_ref().rev() {
- if predicate(&x) { return Some(x) }
- }
- None
+ self.try_rfold((), move |(), x| {
+ if predicate(&x) { LoopState::Break(x) }
+ else { LoopState::Continue(()) }
+ }).break_value()
}
}
/// backwards, a good start is to know where the end is.
///
/// When implementing an `ExactSizeIterator`, You must also implement
-/// [`Iterator`]. When doing so, the implementation of [`size_hint()`] *must*
+/// [`Iterator`]. When doing so, the implementation of [`size_hint`] *must*
/// return the exact size of the iterator.
///
/// [`Iterator`]: trait.Iterator.html
-/// [`size_hint()`]: trait.Iterator.html#method.size_hint
+/// [`size_hint`]: trait.Iterator.html#method.size_hint
///
-/// The [`len()`] method has a default implementation, so you usually shouldn't
+/// The [`len`] method has a default implementation, so you usually shouldn't
/// implement it. However, you may be able to provide a more performant
/// implementation than the default, so overriding it in this case makes sense.
///
-/// [`len()`]: #method.len
+/// [`len`]: #method.len
///
/// # Examples
///
/// # }
/// # }
/// impl ExactSizeIterator for Counter {
-/// // We already have the number of iterations, so we can use it directly.
+/// // We can easily calculate the remaining number of iterations.
/// fn len(&self) -> usize {
-/// self.count
+/// 5 - self.count
/// }
/// }
///
///
/// let counter = Counter::new();
///
-/// assert_eq!(0, counter.len());
+/// assert_eq!(5, counter.len());
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub trait ExactSizeIterator: Iterator {
/// implementation, you can do so. See the [trait-level] docs for an
/// example.
///
- /// This function has the same safety guarantees as the [`size_hint()`]
+ /// This function has the same safety guarantees as the [`size_hint`]
/// function.
///
/// [trait-level]: trait.ExactSizeIterator.html
- /// [`size_hint()`]: trait.Iterator.html#method.size_hint
+ /// [`size_hint`]: trait.Iterator.html#method.size_hint
///
/// # Examples
///
/// ```
/// #![feature(exact_size_is_empty)]
///
- /// let mut one_element = 0..1;
+ /// let mut one_element = std::iter::once(0);
/// assert!(!one_element.is_empty());
///
/// assert_eq!(one_element.next(), Some(0));
/// Trait to represent types that can be created by summing up an iterator.
///
-/// This trait is used to implement the [`sum()`] method on iterators. Types which
-/// implement the trait can be generated by the [`sum()`] method. Like
+/// This trait is used to implement the [`sum`] method on iterators. Types which
+/// implement the trait can be generated by the [`sum`] method. Like
/// [`FromIterator`] this trait should rarely be called directly and instead
-/// interacted with through [`Iterator::sum()`].
+/// interacted with through [`Iterator::sum`].
///
-/// [`sum()`]: ../../std/iter/trait.Sum.html#tymethod.sum
+/// [`sum`]: ../../std/iter/trait.Sum.html#tymethod.sum
/// [`FromIterator`]: ../../std/iter/trait.FromIterator.html
-/// [`Iterator::sum()`]: ../../std/iter/trait.Iterator.html#method.sum
+/// [`Iterator::sum`]: ../../std/iter/trait.Iterator.html#method.sum
#[stable(feature = "iter_arith_traits", since = "1.12.0")]
pub trait Sum<A = Self>: Sized {
/// Method which takes an iterator and generates `Self` from the elements by
/// Trait to represent types that can be created by multiplying elements of an
/// iterator.
///
-/// This trait is used to implement the [`product()`] method on iterators. Types
-/// which implement the trait can be generated by the [`product()`] method. Like
+/// This trait is used to implement the [`product`] method on iterators. Types
+/// which implement the trait can be generated by the [`product`] method. Like
/// [`FromIterator`] this trait should rarely be called directly and instead
-/// interacted with through [`Iterator::product()`].
+/// interacted with through [`Iterator::product`].
///
-/// [`product()`]: ../../std/iter/trait.Product.html#tymethod.product
+/// [`product`]: ../../std/iter/trait.Product.html#tymethod.product
/// [`FromIterator`]: ../../std/iter/trait.FromIterator.html
-/// [`Iterator::product()`]: ../../std/iter/trait.Iterator.html#method.product
+/// [`Iterator::product`]: ../../std/iter/trait.Iterator.html#method.product
#[stable(feature = "iter_arith_traits", since = "1.12.0")]
pub trait Product<A = Self>: Sized {
/// Method which takes an iterator and generates `Self` from the elements by
)*)
}
-integer_sum_product! { i8 i16 i32 i64 isize u8 u16 u32 u64 usize }
+integer_sum_product! { i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize }
float_sum_product! { f32 f64 }
/// An iterator adapter that produces output as long as the underlying
fn new(iter: I) -> Self {
ResultShunt {
- iter: iter,
+ iter,
error: None,
}
}
None => None,
}
}
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ if self.error.is_some() {
+ (0, Some(0))
+ } else {
+ let (_, upper) = self.iter.size_hint();
+ (0, upper)
+ }
+ }
}
#[stable(feature = "iter_arith_traits_result", since="1.16.0")]
impl<T, U, E> Sum<Result<U, E>> for Result<T, E>
where T: Sum<U>,
{
+ /// Takes each element in the `Iterator`: if it is an `Err`, no further
+ /// elements are taken, and the `Err` is returned. Should no `Err` occur,
+ /// the sum of all elements is returned.
+ ///
+ /// # Examples
+ ///
+ /// This sums up every integer in a vector, rejecting the sum if a negative
+ /// element is encountered:
+ ///
+ /// ```
+ /// let v = vec![1, 2];
+ /// let res: Result<i32, &'static str> = v.iter().map(|&x: &i32|
+ /// if x < 0 { Err("Negative element found") }
+ /// else { Ok(x) }
+ /// ).sum();
+ /// assert_eq!(res, Ok(3));
+ /// ```
fn sum<I>(iter: I) -> Result<T, E>
where I: Iterator<Item = Result<U, E>>,
{
impl<T, U, E> Product<Result<U, E>> for Result<T, E>
where T: Product<U>,
{
+ /// Takes each element in the `Iterator`: if it is an `Err`, no further
+ /// elements are taken, and the `Err` is returned. Should no `Err` occur,
+ /// the product of all elements is returned.
fn product<I>(iter: I) -> Result<T, E>
where I: Iterator<Item = Result<U, E>>,
{
/// An iterator that always continues to yield `None` when exhausted.
///
/// Calling next on a fused iterator that has returned `None` once is guaranteed
-/// to return [`None`] again. This trait is should be implemented by all iterators
+/// to return [`None`] again. This trait should be implemented by all iterators
/// that behave this way because it allows for some significant optimizations.
///
/// Note: In general, you should not use `FusedIterator` in generic bounds if
-/// you need a fused iterator. Instead, you should just call [`Iterator::fuse()`]
+/// you need a fused iterator. Instead, you should just call [`Iterator::fuse`]
/// on the iterator. If the iterator is already fused, the additional [`Fuse`]
/// wrapper will be a no-op with no performance penalty.
///
/// [`None`]: ../../std/option/enum.Option.html#variant.None
-/// [`Iterator::fuse()`]: ../../std/iter/trait.Iterator.html#method.fuse
+/// [`Iterator::fuse`]: ../../std/iter/trait.Iterator.html#method.fuse
/// [`Fuse`]: ../../std/iter/struct.Fuse.html
-#[unstable(feature = "fused", issue = "35602")]
+#[stable(feature = "fused", since = "1.26.0")]
pub trait FusedIterator: Iterator {}
-#[unstable(feature = "fused", issue = "35602")]
+#[stable(feature = "fused", since = "1.26.0")]
impl<'a, I: FusedIterator + ?Sized> FusedIterator for &'a mut I {}
/// An iterator that reports an accurate length using size_hint.
/// The iterator reports a size hint where it is either exact
/// (lower bound is equal to upper bound), or the upper bound is [`None`].
/// The upper bound must only be [`None`] if the actual iterator length is
-/// larger than [`usize::MAX`].
+/// larger than [`usize::MAX`]. In that case, the lower bound must be
+/// [`usize::MAX`], resulting in a [`.size_hint`] of `(usize::MAX, None)`.
///
-/// The iterator must produce exactly the number of elements it reported.
+/// The iterator must produce exactly the number of elements it reported
+/// or diverge before reaching the end.
///
/// # Safety
///
/// This trait must only be implemented when the contract is upheld.
-/// Consumers of this trait must inspect [`.size_hint()`]’s upper bound.
+/// Consumers of this trait must inspect [`.size_hint`]’s upper bound.
///
/// [`None`]: ../../std/option/enum.Option.html#variant.None
/// [`usize::MAX`]: ../../std/usize/constant.MAX.html
-/// [`.size_hint()`]: ../../std/iter/trait.Iterator.html#method.size_hint
+/// [`.size_hint`]: ../../std/iter/trait.Iterator.html#method.size_hint
#[unstable(feature = "trusted_len", issue = "37572")]
pub unsafe trait TrustedLen : Iterator {}
projects / rustc.git / blobdiff