src/libcore/iter/traits/accum.rs

   1 use crate::ops::{Mul, Add};
   2 use crate::num::Wrapping;
   3
   4 /// Trait to represent types that can be created by summing up an iterator.
   5 ///
   6 /// This trait is used to implement the [`sum`] method on iterators. Types which
   7 /// implement the trait can be generated by the [`sum`] method. Like
   8 /// [`FromIterator`] this trait should rarely be called directly and instead
   9 /// interacted with through [`Iterator::sum`].
  10 ///
  11 /// [`sum`]: ../../std/iter/trait.Sum.html#tymethod.sum
  12 /// [`FromIterator`]: ../../std/iter/trait.FromIterator.html
  13 /// [`Iterator::sum`]: ../../std/iter/trait.Iterator.html#method.sum
  14 #[stable(feature = "iter_arith_traits", since = "1.12.0")]
  15 pub trait Sum<A = Self>: Sized {
  16     /// Method which takes an iterator and generates `Self` from the elements by
  17     /// "summing up" the items.
  18     #[stable(feature = "iter_arith_traits", since = "1.12.0")]
  19     fn sum<I: Iterator<Item=A>>(iter: I) -> Self;
  20 }
  21
  22 /// Trait to represent types that can be created by multiplying elements of an
  23 /// iterator.
  24 ///
  25 /// This trait is used to implement the [`product`] method on iterators. Types
  26 /// which implement the trait can be generated by the [`product`] method. Like
  27 /// [`FromIterator`] this trait should rarely be called directly and instead
  28 /// interacted with through [`Iterator::product`].
  29 ///
  30 /// [`product`]: ../../std/iter/trait.Product.html#tymethod.product
  31 /// [`FromIterator`]: ../../std/iter/trait.FromIterator.html
  32 /// [`Iterator::product`]: ../../std/iter/trait.Iterator.html#method.product
  33 #[stable(feature = "iter_arith_traits", since = "1.12.0")]
  34 pub trait Product<A = Self>: Sized {
  35     /// Method which takes an iterator and generates `Self` from the elements by
  36     /// multiplying the items.
  37     #[stable(feature = "iter_arith_traits", since = "1.12.0")]
  38     fn product<I: Iterator<Item=A>>(iter: I) -> Self;
  39 }
  40
  41 // N.B., explicitly use Add and Mul here to inherit overflow checks
  42 macro_rules! integer_sum_product {
  43     (@impls $zero:expr, $one:expr, #[$attr:meta], $($a:ty)*) => ($(
  44         #[$attr]
  45         impl Sum for $a {
  46             fn sum<I: Iterator<Item=$a>>(iter: I) -> $a {
  47                 iter.fold($zero, Add::add)
  48             }
  49         }
  50
  51         #[$attr]
  52         impl Product for $a {
  53             fn product<I: Iterator<Item=$a>>(iter: I) -> $a {
  54                 iter.fold($one, Mul::mul)
  55             }
  56         }
  57
  58         #[$attr]
  59         impl<'a> Sum<&'a $a> for $a {
  60             fn sum<I: Iterator<Item=&'a $a>>(iter: I) -> $a {
  61                 iter.fold($zero, Add::add)
  62             }
  63         }
  64
  65         #[$attr]
  66         impl<'a> Product<&'a $a> for $a {
  67             fn product<I: Iterator<Item=&'a $a>>(iter: I) -> $a {
  68                 iter.fold($one, Mul::mul)
  69             }
  70         }
  71     )*);
  72     ($($a:ty)*) => (
  73         integer_sum_product!(@impls 0, 1,
  74                 #[stable(feature = "iter_arith_traits", since = "1.12.0")],
  75                 $($a)+);
  76         integer_sum_product!(@impls Wrapping(0), Wrapping(1),
  77                 #[stable(feature = "wrapping_iter_arith", since = "1.14.0")],
  78                 $(Wrapping<$a>)+);
  79     );
  80 }
  81
  82 macro_rules! float_sum_product {
  83     ($($a:ident)*) => ($(
  84         #[stable(feature = "iter_arith_traits", since = "1.12.0")]
  85         impl Sum for $a {
  86             fn sum<I: Iterator<Item=$a>>(iter: I) -> $a {
  87                 iter.fold(0.0, |a, b| a + b)
  88             }
  89         }
  90
  91         #[stable(feature = "iter_arith_traits", since = "1.12.0")]
  92         impl Product for $a {
  93             fn product<I: Iterator<Item=$a>>(iter: I) -> $a {
  94                 iter.fold(1.0, |a, b| a * b)
  95             }
  96         }
  97
  98         #[stable(feature = "iter_arith_traits", since = "1.12.0")]
  99         impl<'a> Sum<&'a $a> for $a {
 100             fn sum<I: Iterator<Item=&'a $a>>(iter: I) -> $a {
 101                 iter.fold(0.0, |a, b| a + *b)
 102             }
 103         }
 104
 105         #[stable(feature = "iter_arith_traits", since = "1.12.0")]
 106         impl<'a> Product<&'a $a> for $a {
 107             fn product<I: Iterator<Item=&'a $a>>(iter: I) -> $a {
 108                 iter.fold(1.0, |a, b| a * *b)
 109             }
 110         }
 111     )*)
 112 }
 113
 114 integer_sum_product! { i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize }
 115 float_sum_product! { f32 f64 }
 116
 117 /// An iterator adapter that produces output as long as the underlying
 118 /// iterator produces `Result::Ok` values.
 119 ///
 120 /// If an error is encountered, the iterator stops and the error is
 121 /// stored. The error may be recovered later via `reconstruct`.
 122 struct ResultShunt<I, E> {
 123     iter: I,
 124     error: Option<E>,
 125 }
 126
 127 impl<I, T, E> ResultShunt<I, E>
 128     where I: Iterator<Item = Result<T, E>>
 129 {
 130     /// Process the given iterator as if it yielded a `T` instead of a
 131     /// `Result<T, _>`. Any errors will stop the inner iterator and
 132     /// the overall result will be an error.
 133     pub fn process<F, U>(iter: I, mut f: F) -> Result<U, E>
 134         where F: FnMut(&mut Self) -> U
 135     {
 136         let mut shunt = ResultShunt::new(iter);
 137         let value = f(shunt.by_ref());
 138         shunt.reconstruct(value)
 139     }
 140
 141     fn new(iter: I) -> Self {
 142         ResultShunt {
 143             iter,
 144             error: None,
 145         }
 146     }
 147
 148     /// Consume the adapter and rebuild a `Result` value. This should
 149     /// *always* be called, otherwise any potential error would be
 150     /// lost.
 151     fn reconstruct<U>(self, val: U) -> Result<U, E> {
 152         match self.error {
 153             None => Ok(val),
 154             Some(e) => Err(e),
 155         }
 156     }
 157 }
 158
 159 impl<I, T, E> Iterator for ResultShunt<I, E>
 160     where I: Iterator<Item = Result<T, E>>
 161 {
 162     type Item = T;
 163
 164     fn next(&mut self) -> Option<Self::Item> {
 165         match self.iter.next() {
 166             Some(Ok(v)) => Some(v),
 167             Some(Err(e)) => {
 168                 self.error = Some(e);
 169                 None
 170             }
 171             None => None,
 172         }
 173     }
 174
 175     fn size_hint(&self) -> (usize, Option<usize>) {
 176         if self.error.is_some() {
 177             (0, Some(0))
 178         } else {
 179             let (_, upper) = self.iter.size_hint();
 180             (0, upper)
 181         }
 182     }
 183 }
 184
 185 #[stable(feature = "iter_arith_traits_result", since="1.16.0")]
 186 impl<T, U, E> Sum<Result<U, E>> for Result<T, E>
 187     where T: Sum<U>,
 188 {
 189     /// Takes each element in the `Iterator`: if it is an `Err`, no further
 190     /// elements are taken, and the `Err` is returned. Should no `Err` occur,
 191     /// the sum of all elements is returned.
 192     ///
 193     /// # Examples
 194     ///
 195     /// This sums up every integer in a vector, rejecting the sum if a negative
 196     /// element is encountered:
 197     ///
 198     /// ```
 199     /// let v = vec![1, 2];
 200     /// let res: Result<i32, &'static str> = v.iter().map(|&x: &i32|
 201     ///     if x < 0 { Err("Negative element found") }
 202     ///     else { Ok(x) }
 203     /// ).sum();
 204     /// assert_eq!(res, Ok(3));
 205     /// ```
 206     fn sum<I>(iter: I) -> Result<T, E>
 207         where I: Iterator<Item = Result<U, E>>,
 208     {
 209         ResultShunt::process(iter, |i| i.sum())
 210     }
 211 }
 212
 213 #[stable(feature = "iter_arith_traits_result", since="1.16.0")]
 214 impl<T, U, E> Product<Result<U, E>> for Result<T, E>
 215     where T: Product<U>,
 216 {
 217     /// Takes each element in the `Iterator`: if it is an `Err`, no further
 218     /// elements are taken, and the `Err` is returned. Should no `Err` occur,
 219     /// the product of all elements is returned.
 220     fn product<I>(iter: I) -> Result<T, E>
 221         where I: Iterator<Item = Result<U, E>>,
 222     {
 223         ResultShunt::process(iter, |i| i.product())
 224     }
 225 }
 226
 227 /// An iterator adapter that produces output as long as the underlying
 228 /// iterator produces `Option::Some` values.
 229 struct OptionShunt<I> {
 230     iter: I,
 231     exited_early: bool,
 232 }
 233
 234 impl<I, T> OptionShunt<I>
 235 where
 236     I: Iterator<Item = Option<T>>,
 237 {
 238     /// Process the given iterator as if it yielded a `T` instead of a
 239     /// `Option<T>`. Any `None` value will stop the inner iterator and
 240     /// the overall result will be a `None`.
 241     pub fn process<F, U>(iter: I, mut f: F) -> Option<U>
 242     where
 243         F: FnMut(&mut Self) -> U,
 244     {
 245         let mut shunt = OptionShunt::new(iter);
 246         let value = f(shunt.by_ref());
 247         shunt.reconstruct(value)
 248     }
 249
 250     fn new(iter: I) -> Self {
 251         OptionShunt {
 252             iter,
 253             exited_early: false,
 254         }
 255     }
 256
 257     /// Consume the adapter and rebuild a `Option` value.
 258     fn reconstruct<U>(self, val: U) -> Option<U> {
 259         if self.exited_early {
 260             None
 261         } else {
 262             Some(val)
 263         }
 264     }
 265 }
 266
 267 impl<I, T> Iterator for OptionShunt<I>
 268 where
 269     I: Iterator<Item = Option<T>>,
 270 {
 271     type Item = T;
 272
 273     fn next(&mut self) -> Option<Self::Item> {
 274         match self.iter.next() {
 275             Some(Some(v)) => Some(v),
 276             Some(None) => {
 277                 self.exited_early = true;
 278                 None
 279             }
 280             None => None,
 281         }
 282     }
 283
 284     fn size_hint(&self) -> (usize, Option<usize>) {
 285         if self.exited_early {
 286             (0, Some(0))
 287         } else {
 288             let (_, upper) = self.iter.size_hint();
 289             (0, upper)
 290         }
 291     }
 292 }
 293
 294 #[stable(feature = "iter_arith_traits_option", since = "1.37.0")]
 295 impl<T, U> Sum<Option<U>> for Option<T>
 296 where
 297     T: Sum<U>,
 298 {
 299     /// Takes each element in the `Iterator`: if it is a `None`, no further
 300     /// elements are taken, and the `None` is returned. Should no `None` occur,
 301     /// the sum of all elements is returned.
 302     ///
 303     /// # Examples
 304     ///
 305     /// This sums up the position of the character 'a' in a vector of strings,
 306     /// if a word did not have the character 'a' the operation returns `None`:
 307     ///
 308     /// ```
 309     /// let words = vec!["have", "a", "great", "day"];
 310     /// let total: Option<usize> = words.iter().map(|w| w.find('a')).sum();
 311     /// assert_eq!(total, Some(5));
 312     /// ```
 313     fn sum<I>(iter: I) -> Option<T>
 314     where
 315         I: Iterator<Item = Option<U>>,
 316     {
 317         OptionShunt::process(iter, |i| i.sum())
 318     }
 319 }
 320
 321 #[stable(feature = "iter_arith_traits_option", since = "1.37.0")]
 322 impl<T, U> Product<Option<U>> for Option<T>
 323 where
 324     T: Product<U>,
 325 {
 326     /// Takes each element in the `Iterator`: if it is a `None`, no further
 327     /// elements are taken, and the `None` is returned. Should no `None` occur,
 328     /// the product of all elements is returned.
 329     fn product<I>(iter: I) -> Option<T>
 330     where
 331         I: Iterator<Item = Option<U>>,
 332     {
 333         OptionShunt::process(iter, |i| i.product())
 334     }
 335 }