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 #[cfg_attr(not(test), rustc_diagnostic_item = "DoubleEndedIterator")]
  40 pub trait DoubleEndedIterator: Iterator {
  41     /// Removes and returns an element from the end of the iterator.
  42     ///
  43     /// Returns `None` when there are no more elements.
  44     ///
  45     /// The [trait-level] docs contain more details.
  46     ///
  47     /// [trait-level]: DoubleEndedIterator
  48     ///
  49     /// # Examples
  50     ///
  51     /// Basic usage:
  52     ///
  53     /// ```
  54     /// let numbers = vec![1, 2, 3, 4, 5, 6];
  55     ///
  56     /// let mut iter = numbers.iter();
  57     ///
  58     /// assert_eq!(Some(&1), iter.next());
  59     /// assert_eq!(Some(&6), iter.next_back());
  60     /// assert_eq!(Some(&5), iter.next_back());
  61     /// assert_eq!(Some(&2), iter.next());
  62     /// assert_eq!(Some(&3), iter.next());
  63     /// assert_eq!(Some(&4), iter.next());
  64     /// assert_eq!(None, iter.next());
  65     /// assert_eq!(None, iter.next_back());
  66     /// ```
  67     ///
  68     /// # Remarks
  69     ///
  70     /// The elements yielded by `DoubleEndedIterator`'s methods may differ from
  71     /// the ones yielded by [`Iterator`]'s methods:
  72     ///
  73     /// ```
  74     /// let vec = vec![(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b')];
  75     /// let uniq_by_fst_comp = || {
  76     ///     let mut seen = std::collections::HashSet::new();
  77     ///     vec.iter().copied().filter(move |x| seen.insert(x.0))
  78     /// };
  79     ///
  80     /// assert_eq!(uniq_by_fst_comp().last(), Some((2, 'a')));
  81     /// assert_eq!(uniq_by_fst_comp().next_back(), Some((2, 'b')));
  82     ///
  83     /// assert_eq!(
  84     ///     uniq_by_fst_comp().fold(vec![], |mut v, x| {v.push(x); v}),
  85     ///     vec![(1, 'a'), (2, 'a')]
  86     /// );
  87     /// assert_eq!(
  88     ///     uniq_by_fst_comp().rfold(vec![], |mut v, x| {v.push(x); v}),
  89     ///     vec![(2, 'b'), (1, 'c')]
  90     /// );
  91     /// ```
  92     #[stable(feature = "rust1", since = "1.0.0")]
  93     fn next_back(&mut self) -> Option<Self::Item>;
  94
  95     /// Advances the iterator from the back by `n` elements.
  96     ///
  97     /// `advance_back_by` is the reverse version of [`advance_by`]. This method will
  98     /// eagerly skip `n` elements starting from the back by calling [`next_back`] up
  99     /// to `n` times until [`None`] is encountered.
 100     ///
 101     /// `advance_back_by(n)` will return [`Ok(())`] if the iterator successfully advances by
 102     /// `n` elements, or [`Err(k)`] if [`None`] is encountered, where `k` is the number of
 103     /// elements the iterator is advanced by before running out of elements (i.e. the length
 104     /// of the iterator). Note that `k` is always less than `n`.
 105     ///
 106     /// Calling `advance_back_by(0)` can do meaningful work, for example [`Flatten`] can advance its
 107     /// outer iterator until it finds an inner iterator that is not empty, which then often
 108     /// allows it to return a more accurate `size_hint()` than in its initial state.
 109     /// `advance_back_by(0)` may either return `Ok()` or `Err(0)`. The former conveys no information
 110     /// whether the iterator is or is not exhausted, the latter can be treated as if [`next_back`]
 111     /// had returned `None`. Replacing a `Err(0)` with `Ok` is only correct for `n = 0`.
 112     ///
 113     /// [`advance_by`]: Iterator::advance_by
 114     /// [`Flatten`]: crate::iter::Flatten
 115     /// [`next_back`]: DoubleEndedIterator::next_back
 116     ///
 117     /// # Examples
 118     ///
 119     /// Basic usage:
 120     ///
 121     /// ```
 122     /// #![feature(iter_advance_by)]
 123     ///
 124     /// let a = [3, 4, 5, 6];
 125     /// let mut iter = a.iter();
 126     ///
 127     /// assert_eq!(iter.advance_back_by(2), Ok(()));
 128     /// assert_eq!(iter.next_back(), Some(&4));
 129     /// assert_eq!(iter.advance_back_by(0), Ok(()));
 130     /// assert_eq!(iter.advance_back_by(100), Err(1)); // only `&3` was skipped
 131     /// ```
 132     ///
 133     /// [`Ok(())`]: Ok
 134     /// [`Err(k)`]: Err
 135     #[inline]
 136     #[unstable(feature = "iter_advance_by", reason = "recently added", issue = "77404")]
 137     fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
 138         for i in 0..n {
 139             self.next_back().ok_or(i)?;
 140         }
 141         Ok(())
 142     }
 143
 144     /// Returns the `n`th element from the end of the iterator.
 145     ///
 146     /// This is essentially the reversed version of [`Iterator::nth()`].
 147     /// Although like most indexing operations, the count starts from zero, so
 148     /// `nth_back(0)` returns the first value from the end, `nth_back(1)` the
 149     /// second, and so on.
 150     ///
 151     /// Note that all elements between the end and the returned element will be
 152     /// consumed, including the returned element. This also means that calling
 153     /// `nth_back(0)` multiple times on the same iterator will return different
 154     /// elements.
 155     ///
 156     /// `nth_back()` will return [`None`] if `n` is greater than or equal to the
 157     /// length of the iterator.
 158     ///
 159     /// # Examples
 160     ///
 161     /// Basic usage:
 162     ///
 163     /// ```
 164     /// let a = [1, 2, 3];
 165     /// assert_eq!(a.iter().nth_back(2), Some(&1));
 166     /// ```
 167     ///
 168     /// Calling `nth_back()` multiple times doesn't rewind the iterator:
 169     ///
 170     /// ```
 171     /// let a = [1, 2, 3];
 172     ///
 173     /// let mut iter = a.iter();
 174     ///
 175     /// assert_eq!(iter.nth_back(1), Some(&2));
 176     /// assert_eq!(iter.nth_back(1), None);
 177     /// ```
 178     ///
 179     /// Returning `None` if there are less than `n + 1` elements:
 180     ///
 181     /// ```
 182     /// let a = [1, 2, 3];
 183     /// assert_eq!(a.iter().nth_back(10), None);
 184     /// ```
 185     #[inline]
 186     #[stable(feature = "iter_nth_back", since = "1.37.0")]
 187     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
 188         self.advance_back_by(n).ok()?;
 189         self.next_back()
 190     }
 191
 192     /// This is the reverse version of [`Iterator::try_fold()`]: it takes
 193     /// elements starting from the back of the iterator.
 194     ///
 195     /// # Examples
 196     ///
 197     /// Basic usage:
 198     ///
 199     /// ```
 200     /// let a = ["1", "2", "3"];
 201     /// let sum = a.iter()
 202     ///     .map(|&s| s.parse::<i32>())
 203     ///     .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
 204     /// assert_eq!(sum, Ok(6));
 205     /// ```
 206     ///
 207     /// Short-circuiting:
 208     ///
 209     /// ```
 210     /// let a = ["1", "rust", "3"];
 211     /// let mut it = a.iter();
 212     /// let sum = it
 213     ///     .by_ref()
 214     ///     .map(|&s| s.parse::<i32>())
 215     ///     .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
 216     /// assert!(sum.is_err());
 217     ///
 218     /// // Because it short-circuited, the remaining elements are still
 219     /// // available through the iterator.
 220     /// assert_eq!(it.next_back(), Some(&"1"));
 221     /// ```
 222     #[inline]
 223     #[stable(feature = "iterator_try_fold", since = "1.27.0")]
 224     fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
 225     where
 226         Self: Sized,
 227         F: FnMut(B, Self::Item) -> R,
 228         R: Try<Output = B>,
 229     {
 230         let mut accum = init;
 231         while let Some(x) = self.next_back() {
 232             accum = f(accum, x)?;
 233         }
 234         try { accum }
 235     }
 236
 237     /// An iterator method that reduces the iterator's elements to a single,
 238     /// final value, starting from the back.
 239     ///
 240     /// This is the reverse version of [`Iterator::fold()`]: it takes elements
 241     /// starting from the back of the iterator.
 242     ///
 243     /// `rfold()` takes two arguments: an initial value, and a closure with two
 244     /// arguments: an 'accumulator', and an element. The closure returns the value that
 245     /// the accumulator should have for the next iteration.
 246     ///
 247     /// The initial value is the value the accumulator will have on the first
 248     /// call.
 249     ///
 250     /// After applying this closure to every element of the iterator, `rfold()`
 251     /// returns the accumulator.
 252     ///
 253     /// This operation is sometimes called 'reduce' or 'inject'.
 254     ///
 255     /// Folding is useful whenever you have a collection of something, and want
 256     /// to produce a single value from it.
 257     ///
 258     /// Note: `rfold()` combines elements in a *right-associative* fashion. For associative
 259     /// operators like `+`, the order the elements are combined in is not important, but for non-associative
 260     /// operators like `-` the order will affect the final result.
 261     /// For a *left-associative* version of `rfold()`, see [`Iterator::fold()`].
 262     ///
 263     /// # Examples
 264     ///
 265     /// Basic usage:
 266     ///
 267     /// ```
 268     /// let a = [1, 2, 3];
 269     ///
 270     /// // the sum of all of the elements of a
 271     /// let sum = a.iter()
 272     ///            .rfold(0, |acc, &x| acc + x);
 273     ///
 274     /// assert_eq!(sum, 6);
 275     /// ```
 276     ///
 277     /// This example demonstrates the right-associative nature of `rfold()`:
 278     /// it builds a string, starting with an initial value
 279     /// and continuing with each element from the back until the front:
 280     ///
 281     /// ```
 282     /// let numbers = [1, 2, 3, 4, 5];
 283     ///
 284     /// let zero = "0".to_string();
 285     ///
 286     /// let result = numbers.iter().rfold(zero, |acc, &x| {
 287     ///     format!("({} + {})", x, acc)
 288     /// });
 289     ///
 290     /// assert_eq!(result, "(1 + (2 + (3 + (4 + (5 + 0)))))");
 291     /// ```
 292     #[doc(alias = "foldr")]
 293     #[inline]
 294     #[stable(feature = "iter_rfold", since = "1.27.0")]
 295     fn rfold<B, F>(mut self, init: B, mut f: F) -> B
 296     where
 297         Self: Sized,
 298         F: FnMut(B, Self::Item) -> B,
 299     {
 300         let mut accum = init;
 301         while let Some(x) = self.next_back() {
 302             accum = f(accum, x);
 303         }
 304         accum
 305     }
 306
 307     /// Searches for an element of an iterator from the back that satisfies a predicate.
 308     ///
 309     /// `rfind()` takes a closure that returns `true` or `false`. It applies
 310     /// this closure to each element of the iterator, starting at the end, and if any
 311     /// of them return `true`, then `rfind()` returns [`Some(element)`]. If they all return
 312     /// `false`, it returns [`None`].
 313     ///
 314     /// `rfind()` is short-circuiting; in other words, it will stop processing
 315     /// as soon as the closure returns `true`.
 316     ///
 317     /// Because `rfind()` takes a reference, and many iterators iterate over
 318     /// references, this leads to a possibly confusing situation where the
 319     /// argument is a double reference. You can see this effect in the
 320     /// examples below, with `&&x`.
 321     ///
 322     /// [`Some(element)`]: Some
 323     ///
 324     /// # Examples
 325     ///
 326     /// Basic usage:
 327     ///
 328     /// ```
 329     /// let a = [1, 2, 3];
 330     ///
 331     /// assert_eq!(a.iter().rfind(|&&x| x == 2), Some(&2));
 332     ///
 333     /// assert_eq!(a.iter().rfind(|&&x| x == 5), None);
 334     /// ```
 335     ///
 336     /// Stopping at the first `true`:
 337     ///
 338     /// ```
 339     /// let a = [1, 2, 3];
 340     ///
 341     /// let mut iter = a.iter();
 342     ///
 343     /// assert_eq!(iter.rfind(|&&x| x == 2), Some(&2));
 344     ///
 345     /// // we can still use `iter`, as there are more elements.
 346     /// assert_eq!(iter.next_back(), Some(&1));
 347     /// ```
 348     #[inline]
 349     #[stable(feature = "iter_rfind", since = "1.27.0")]
 350     fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
 351     where
 352         Self: Sized,
 353         P: FnMut(&Self::Item) -> bool,
 354     {
 355         #[inline]
 356         fn check<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut((), T) -> ControlFlow<T> {
 357             move |(), x| {
 358                 if predicate(&x) { ControlFlow::Break(x) } else { ControlFlow::CONTINUE }
 359             }
 360         }
 361
 362         self.try_rfold((), check(predicate)).break_value()
 363     }
 364 }
 365
 366 #[stable(feature = "rust1", since = "1.0.0")]
 367 impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I {
 368     fn next_back(&mut self) -> Option<I::Item> {
 369         (**self).next_back()
 370     }
 371     fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
 372         (**self).advance_back_by(n)
 373     }
 374     fn nth_back(&mut self, n: usize) -> Option<I::Item> {
 375         (**self).nth_back(n)
 376     }
 377 }