src/libcore/iter/traits/double_ended.rs

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