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