library/core/src/iter/traits/double_ended.rs

   1 use crate::ops::{ControlFlow, Try};
   2
   3 /// An iterator able to yield elements from both ends.
   4 ///
   5 /// Something that implements `DoubleEndedIterator` has one extra capability
   6 /// over something that implements [`Iterator`]: the ability to also take
   7 /// `Item`s from the back, as well as the front.
   8 ///
   9 /// It is important to note that both back and forth work on the same range,
  10 /// and do not cross: iteration is over when they meet in the middle.
  11 ///
  12 /// In a similar fashion to the [`Iterator`] protocol, once a
  13 /// `DoubleEndedIterator` returns `None` from a `next_back()`, calling it again
  14 /// may or may not ever return `Some` again. `next()` and `next_back()` are
  15 /// interchangeable for this purpose.
  16 ///
  17 /// [`Iterator`]: trait.Iterator.html
  18 ///
  19 /// # Examples
  20 ///
  21 /// Basic usage:
  22 ///
  23 /// ```
  24 /// let numbers = vec![1, 2, 3, 4, 5, 6];
  25 ///
  26 /// let mut iter = numbers.iter();
  27 ///
  28 /// assert_eq!(Some(&1), iter.next());
  29 /// assert_eq!(Some(&6), iter.next_back());
  30 /// assert_eq!(Some(&5), iter.next_back());
  31 /// assert_eq!(Some(&2), iter.next());
  32 /// assert_eq!(Some(&3), iter.next());
  33 /// assert_eq!(Some(&4), iter.next());
  34 /// assert_eq!(None, iter.next());
  35 /// assert_eq!(None, iter.next_back());
  36 /// ```
  37 #[stable(feature = "rust1", since = "1.0.0")]
  38 pub trait DoubleEndedIterator: Iterator {
  39     /// Removes and returns an element from the end of the iterator.
  40     ///
  41     /// Returns `None` when there are no more elements.
  42     ///
  43     /// The [trait-level] docs contain more details.
  44     ///
  45     /// [trait-level]: trait.DoubleEndedIterator.html
  46     ///
  47     /// # Examples
  48     ///
  49     /// Basic usage:
  50     ///
  51     /// ```
  52     /// let numbers = vec![1, 2, 3, 4, 5, 6];
  53     ///
  54     /// let mut iter = numbers.iter();
  55     ///
  56     /// assert_eq!(Some(&1), iter.next());
  57     /// assert_eq!(Some(&6), iter.next_back());
  58     /// assert_eq!(Some(&5), iter.next_back());
  59     /// assert_eq!(Some(&2), iter.next());
  60     /// assert_eq!(Some(&3), iter.next());
  61     /// assert_eq!(Some(&4), iter.next());
  62     /// assert_eq!(None, iter.next());
  63     /// assert_eq!(None, iter.next_back());
  64     /// ```
  65     ///
  66     /// # Remarks
  67     ///
  68     /// The elements yielded by `DoubleEndedIterator`'s methods may differ from
  69     /// the ones yielded by `Iterator`'s methods:
  70     ///
  71     /// ```
  72     /// let vec = vec![(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b')];
  73     /// let uniq_by_fst_comp = || {
  74     ///     let mut seen = std::collections::HashSet::new();
  75     ///     vec.iter().copied().filter(move |x| seen.insert(x.0))
  76     /// };
  77     ///
  78     /// assert_eq!(uniq_by_fst_comp().last(), Some((2, 'a')));
  79     /// assert_eq!(uniq_by_fst_comp().next_back(), Some((2, 'b')));
  80     ///
  81     /// assert_eq!(
  82     ///     uniq_by_fst_comp().fold(vec![], |mut v, x| {v.push(x); v}),
  83     ///     vec![(1, 'a'), (2, 'a')]
  84     /// );
  85     /// assert_eq!(
  86     ///     uniq_by_fst_comp().rfold(vec![], |mut v, x| {v.push(x); v}),
  87     ///     vec![(2, 'b'), (1, 'c')]
  88     /// );
  89     /// ```
  90     ///
  91     #[stable(feature = "rust1", since = "1.0.0")]
  92     fn next_back(&mut self) -> Option<Self::Item>;
  93
  94     /// Returns the `n`th element from the end of the iterator.
  95     ///
  96     /// This is essentially the reversed version of [`nth`]. Although like most indexing
  97     /// operations, the count starts from zero, so `nth_back(0)` returns the first value from
  98     /// the end, `nth_back(1)` the second, and so on.
  99     ///
 100     /// Note that all elements between the end and the returned element will be
 101     /// consumed, including the returned element. This also means that calling
 102     /// `nth_back(0)` multiple times on the same iterator will return different
 103     /// elements.
 104     ///
 105     /// `nth_back()` will return [`None`] if `n` is greater than or equal to the length of the
 106     /// iterator.
 107     ///
 108     /// [`nth`]: crate::iter::Iterator::nth
 109     ///
 110     /// # Examples
 111     ///
 112     /// Basic usage:
 113     ///
 114     /// ```
 115     /// let a = [1, 2, 3];
 116     /// assert_eq!(a.iter().nth_back(2), Some(&1));
 117     /// ```
 118     ///
 119     /// Calling `nth_back()` multiple times doesn't rewind the iterator:
 120     ///
 121     /// ```
 122     /// let a = [1, 2, 3];
 123     ///
 124     /// let mut iter = a.iter();
 125     ///
 126     /// assert_eq!(iter.nth_back(1), Some(&2));
 127     /// assert_eq!(iter.nth_back(1), None);
 128     /// ```
 129     ///
 130     /// Returning `None` if there are less than `n + 1` elements:
 131     ///
 132     /// ```
 133     /// let a = [1, 2, 3];
 134     /// assert_eq!(a.iter().nth_back(10), None);
 135     /// ```
 136     #[inline]
 137     #[stable(feature = "iter_nth_back", since = "1.37.0")]
 138     fn nth_back(&mut self, mut n: usize) -> Option<Self::Item> {
 139         for x in self.rev() {
 140             if n == 0 {
 141                 return Some(x);
 142             }
 143             n -= 1;
 144         }
 145         None
 146     }
 147
 148     /// This is the reverse version of [`try_fold()`]: it takes elements
 149     /// starting from the back of the iterator.
 150     ///
 151     /// [`try_fold()`]: Iterator::try_fold
 152     ///
 153     /// # Examples
 154     ///
 155     /// Basic usage:
 156     ///
 157     /// ```
 158     /// let a = ["1", "2", "3"];
 159     /// let sum = a.iter()
 160     ///     .map(|&s| s.parse::<i32>())
 161     ///     .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
 162     /// assert_eq!(sum, Ok(6));
 163     /// ```
 164     ///
 165     /// Short-circuiting:
 166     ///
 167     /// ```
 168     /// let a = ["1", "rust", "3"];
 169     /// let mut it = a.iter();
 170     /// let sum = it
 171     ///     .by_ref()
 172     ///     .map(|&s| s.parse::<i32>())
 173     ///     .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
 174     /// assert!(sum.is_err());
 175     ///
 176     /// // Because it short-circuited, the remaining elements are still
 177     /// // available through the iterator.
 178     /// assert_eq!(it.next_back(), Some(&"1"));
 179     /// ```
 180     #[inline]
 181     #[stable(feature = "iterator_try_fold", since = "1.27.0")]
 182     fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
 183     where
 184         Self: Sized,
 185         F: FnMut(B, Self::Item) -> R,
 186         R: Try<Ok = B>,
 187     {
 188         let mut accum = init;
 189         while let Some(x) = self.next_back() {
 190             accum = f(accum, x)?;
 191         }
 192         Try::from_ok(accum)
 193     }
 194
 195     /// An iterator method that reduces the iterator's elements to a single,
 196     /// final value, starting from the back.
 197     ///
 198     /// This is the reverse version of [`fold()`]: it takes elements starting from
 199     /// the back of the iterator.
 200     ///
 201     /// `rfold()` takes two arguments: an initial value, and a closure with two
 202     /// arguments: an 'accumulator', and an element. The closure returns the value that
 203     /// the accumulator should have for the next iteration.
 204     ///
 205     /// The initial value is the value the accumulator will have on the first
 206     /// call.
 207     ///
 208     /// After applying this closure to every element of the iterator, `rfold()`
 209     /// returns the accumulator.
 210     ///
 211     /// This operation is sometimes called 'reduce' or 'inject'.
 212     ///
 213     /// Folding is useful whenever you have a collection of something, and want
 214     /// to produce a single value from it.
 215     ///
 216     /// [`fold()`]: Iterator::fold
 217     ///
 218     /// # Examples
 219     ///
 220     /// Basic usage:
 221     ///
 222     /// ```
 223     /// let a = [1, 2, 3];
 224     ///
 225     /// // the sum of all of the elements of a
 226     /// let sum = a.iter()
 227     ///            .rfold(0, |acc, &x| acc + x);
 228     ///
 229     /// assert_eq!(sum, 6);
 230     /// ```
 231     ///
 232     /// This example builds a string, starting with an initial value
 233     /// and continuing with each element from the back until the front:
 234     ///
 235     /// ```
 236     /// let numbers = [1, 2, 3, 4, 5];
 237     ///
 238     /// let zero = "0".to_string();
 239     ///
 240     /// let result = numbers.iter().rfold(zero, |acc, &x| {
 241     ///     format!("({} + {})", x, acc)
 242     /// });
 243     ///
 244     /// assert_eq!(result, "(1 + (2 + (3 + (4 + (5 + 0)))))");
 245     /// ```
 246     #[inline]
 247     #[stable(feature = "iter_rfold", since = "1.27.0")]
 248     fn rfold<B, F>(mut self, init: B, mut f: F) -> B
 249     where
 250         Self: Sized,
 251         F: FnMut(B, Self::Item) -> B,
 252     {
 253         let mut accum = init;
 254         while let Some(x) = self.next_back() {
 255             accum = f(accum, x);
 256         }
 257         accum
 258     }
 259
 260     /// Searches for an element of an iterator from the back that satisfies a predicate.
 261     ///
 262     /// `rfind()` takes a closure that returns `true` or `false`. It applies
 263     /// this closure to each element of the iterator, starting at the end, and if any
 264     /// of them return `true`, then `rfind()` returns [`Some(element)`]. If they all return
 265     /// `false`, it returns [`None`].
 266     ///
 267     /// `rfind()` is short-circuiting; in other words, it will stop processing
 268     /// as soon as the closure returns `true`.
 269     ///
 270     /// Because `rfind()` takes a reference, and many iterators iterate over
 271     /// references, this leads to a possibly confusing situation where the
 272     /// argument is a double reference. You can see this effect in the
 273     /// examples below, with `&&x`.
 274     ///
 275     /// [`Some(element)`]: Some
 276     ///
 277     /// # Examples
 278     ///
 279     /// Basic usage:
 280     ///
 281     /// ```
 282     /// let a = [1, 2, 3];
 283     ///
 284     /// assert_eq!(a.iter().rfind(|&&x| x == 2), Some(&2));
 285     ///
 286     /// assert_eq!(a.iter().rfind(|&&x| x == 5), None);
 287     /// ```
 288     ///
 289     /// Stopping at the first `true`:
 290     ///
 291     /// ```
 292     /// let a = [1, 2, 3];
 293     ///
 294     /// let mut iter = a.iter();
 295     ///
 296     /// assert_eq!(iter.rfind(|&&x| x == 2), Some(&2));
 297     ///
 298     /// // we can still use `iter`, as there are more elements.
 299     /// assert_eq!(iter.next_back(), Some(&1));
 300     /// ```
 301     #[inline]
 302     #[stable(feature = "iter_rfind", since = "1.27.0")]
 303     fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
 304     where
 305         Self: Sized,
 306         P: FnMut(&Self::Item) -> bool,
 307     {
 308         #[inline]
 309         fn check<T>(
 310             mut predicate: impl FnMut(&T) -> bool,
 311         ) -> impl FnMut((), T) -> ControlFlow<(), T> {
 312             move |(), x| {
 313                 if predicate(&x) { ControlFlow::Break(x) } else { ControlFlow::CONTINUE }
 314             }
 315         }
 316
 317         self.try_rfold((), check(predicate)).break_value()
 318     }
 319 }
 320
 321 #[stable(feature = "rust1", since = "1.0.0")]
 322 impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I {
 323     fn next_back(&mut self) -> Option<I::Item> {
 324         (**self).next_back()
 325     }
 326     fn nth_back(&mut self, n: usize) -> Option<I::Item> {
 327         (**self).nth_back(n)
 328     }
 329 }