double_ended.rs - source
Description: Source of the Rust file `library/core/src/iter/traits/double_ended.rs`.

#
core/iter/traits/
double_ended.rs

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