1use crate::num::NonZeroUsize;
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#[cfg_attr(not(test), 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(NonZeroUsize)` 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::NonZeroUsize;
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(NonZeroUsize::new(99).unwrap())); // 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<(), NonZeroUsize> {
138 for i in 0..n {
139 if self.next_back().is_none() {
140 // SAFETY: `i` is always less than `n`.
141 return Err(unsafe { NonZeroUsize::new_unchecked(n - i) });
142 }
143 }
144 Ok(())
145 }
146
147 /// Returns the `n`th element from the end of the iterator.
148 ///
149 /// This is essentially the reversed version of [`Iterator::nth()`].
150 /// Although like most indexing operations, the count starts from zero, so
151 /// `nth_back(0)` returns the first value from the end, `nth_back(1)` the
152 /// second, and so on.
153 ///
154 /// Note that all elements between the end and the returned element will be
155 /// consumed, including the returned element. This also means that calling
156 /// `nth_back(0)` multiple times on the same iterator will return different
157 /// elements.
158 ///
159 /// `nth_back()` will return [`None`] if `n` is greater than or equal to the
160 /// length of the iterator.
161 ///
162 /// # Examples
163 ///
164 /// Basic usage:
165 ///
166 /// ```
167 /// let a = [1, 2, 3];
168 /// assert_eq!(a.iter().nth_back(2), Some(&1));
169 /// ```
170 ///
171 /// Calling `nth_back()` multiple times doesn't rewind the iterator:
172 ///
173 /// ```
174 /// let a = [1, 2, 3];
175 ///
176 /// let mut iter = a.iter();
177 ///
178 /// assert_eq!(iter.nth_back(1), Some(&2));
179 /// assert_eq!(iter.nth_back(1), None);
180 /// ```
181 ///
182 /// Returning `None` if there are less than `n + 1` elements:
183 ///
184 /// ```
185 /// let a = [1, 2, 3];
186 /// assert_eq!(a.iter().nth_back(10), None);
187 /// ```
188 #[inline]
189 #[stable(feature = "iter_nth_back", since = "1.37.0")]
190 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
191 if self.advance_back_by(n).is_err() {
192 return None;
193 }
194 self.next_back()
195 }
196
197 /// This is the reverse version of [`Iterator::try_fold()`]: it takes
198 /// elements starting from the back of the iterator.
199 ///
200 /// # Examples
201 ///
202 /// Basic usage:
203 ///
204 /// ```
205 /// let a = ["1", "2", "3"];
206 /// let sum = a.iter()
207 /// .map(|&s| s.parse::<i32>())
208 /// .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
209 /// assert_eq!(sum, Ok(6));
210 /// ```
211 ///
212 /// Short-circuiting:
213 ///
214 /// ```
215 /// let a = ["1", "rust", "3"];
216 /// let mut it = a.iter();
217 /// let sum = it
218 /// .by_ref()
219 /// .map(|&s| s.parse::<i32>())
220 /// .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
221 /// assert!(sum.is_err());
222 ///
223 /// // Because it short-circuited, the remaining elements are still
224 /// // available through the iterator.
225 /// assert_eq!(it.next_back(), Some(&"1"));
226 /// ```
227 #[inline]
228 #[stable(feature = "iterator_try_fold", since = "1.27.0")]
229 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
230 where
231 Self: Sized,
232 F: FnMut(B, Self::Item) -> R,
233 R: Try<Output = B>,
234 {
235 let mut accum = init;
236 while let Some(x) = self.next_back() {
237 accum = f(accum, x)?;
238 }
239 try { accum }
240 }
241
242 /// An iterator method that reduces the iterator's elements to a single,
243 /// final value, starting from the back.
244 ///
245 /// This is the reverse version of [`Iterator::fold()`]: it takes elements
246 /// starting from the back of the iterator.
247 ///
248 /// `rfold()` takes two arguments: an initial value, and a closure with two
249 /// arguments: an 'accumulator', and an element. The closure returns the value that
250 /// the accumulator should have for the next iteration.
251 ///
252 /// The initial value is the value the accumulator will have on the first
253 /// call.
254 ///
255 /// After applying this closure to every element of the iterator, `rfold()`
256 /// returns the accumulator.
257 ///
258 /// This operation is sometimes called 'reduce' or 'inject'.
259 ///
260 /// Folding is useful whenever you have a collection of something, and want
261 /// to produce a single value from it.
262 ///
263 /// Note: `rfold()` combines elements in a *right-associative* fashion. For associative
264 /// operators like `+`, the order the elements are combined in is not important, but for non-associative
265 /// operators like `-` the order will affect the final result.
266 /// For a *left-associative* version of `rfold()`, see [`Iterator::fold()`].
267 ///
268 /// # Examples
269 ///
270 /// Basic usage:
271 ///
272 /// ```
273 /// let a = [1, 2, 3];
274 ///
275 /// // the sum of all of the elements of a
276 /// let sum = a.iter()
277 /// .rfold(0, |acc, &x| acc + x);
278 ///
279 /// assert_eq!(sum, 6);
280 /// ```
281 ///
282 /// This example demonstrates the right-associative nature of `rfold()`:
283 /// it builds a string, starting with an initial value
284 /// and continuing with each element from the back until the front:
285 ///
286 /// ```
287 /// let numbers = [1, 2, 3, 4, 5];
288 ///
289 /// let zero = "0".to_string();
290 ///
291 /// let result = numbers.iter().rfold(zero, |acc, &x| {
292 /// format!("({x} + {acc})")
293 /// });
294 ///
295 /// assert_eq!(result, "(1 + (2 + (3 + (4 + (5 + 0)))))");
296 /// ```
297 #[doc(alias = "foldr")]
298 #[inline]
299 #[stable(feature = "iter_rfold", since = "1.27.0")]
300 fn rfold<B, F>(mut self, init: B, mut f: F) -> B
301 where
302 Self: Sized,
303 F: FnMut(B, Self::Item) -> B,
304 {
305 let mut accum = init;
306 while let Some(x) = self.next_back() {
307 accum = f(accum, x);
308 }
309 accum
310 }
311
312 /// Searches for an element of an iterator from the back that satisfies a predicate.
313 ///
314 /// `rfind()` takes a closure that returns `true` or `false`. It applies
315 /// this closure to each element of the iterator, starting at the end, and if any
316 /// of them return `true`, then `rfind()` returns [`Some(element)`]. If they all return
317 /// `false`, it returns [`None`].
318 ///
319 /// `rfind()` is short-circuiting; in other words, it will stop processing
320 /// as soon as the closure returns `true`.
321 ///
322 /// Because `rfind()` takes a reference, and many iterators iterate over
323 /// references, this leads to a possibly confusing situation where the
324 /// argument is a double reference. You can see this effect in the
325 /// examples below, with `&&x`.
326 ///
327 /// [`Some(element)`]: Some
328 ///
329 /// # Examples
330 ///
331 /// Basic usage:
332 ///
333 /// ```
334 /// let a = [1, 2, 3];
335 ///
336 /// assert_eq!(a.iter().rfind(|&&x| x == 2), Some(&2));
337 ///
338 /// assert_eq!(a.iter().rfind(|&&x| x == 5), None);
339 /// ```
340 ///
341 /// Stopping at the first `true`:
342 ///
343 /// ```
344 /// let a = [1, 2, 3];
345 ///
346 /// let mut iter = a.iter();
347 ///
348 /// assert_eq!(iter.rfind(|&&x| x == 2), Some(&2));
349 ///
350 /// // we can still use `iter`, as there are more elements.
351 /// assert_eq!(iter.next_back(), Some(&1));
352 /// ```
353 #[inline]
354 #[stable(feature = "iter_rfind", since = "1.27.0")]
355 fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
356 where
357 Self: Sized,
358 P: FnMut(&Self::Item) -> bool,
359 {
360 #[inline]
361 fn check<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut((), T) -> ControlFlow<T> {
362 move |(), x| {
363 if predicate(&x) { ControlFlow::Break(x) } else { ControlFlow::Continue(()) }
364 }
365 }
366
367 self.try_rfold((), check(predicate)).break_value()
368 }
369}
370
371#[stable(feature = "rust1", since = "1.0.0")]
372impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I {
373 fn next_back(&mut self) -> Option<I::Item> {
374 (**self).next_back()
375 }
376 fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
377 (**self).advance_back_by(n)
378 }
379 fn nth_back(&mut self, n: usize) -> Option<I::Item> {
380 (**self).nth_back(n)
381 }
382 fn rfold<B, F>(self, init: B, f: F) -> B
383 where
384 F: FnMut(B, Self::Item) -> B,
385 {
386 self.spec_rfold(init, f)
387 }
388 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
389 where
390 F: FnMut(B, Self::Item) -> R,
391 R: Try<Output = B>,
392 {
393 self.spec_try_rfold(init, f)
394 }
395}
396
397/// Helper trait to specialize `rfold` and `rtry_fold` for `&mut I where I: Sized`
398trait DoubleEndedIteratorRefSpec: DoubleEndedIterator {
399 fn spec_rfold<B, F>(self, init: B, f: F) -> B
400 where
401 F: FnMut(B, Self::Item) -> B;
402
403 fn spec_try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
404 where
405 F: FnMut(B, Self::Item) -> R,
406 R: Try<Output = B>;
407}
408
409impl<I: DoubleEndedIterator + ?Sized> DoubleEndedIteratorRefSpec for &mut I {
410 default fn spec_rfold<B, F>(self, init: B, mut f: F) -> B
411 where
412 F: FnMut(B, Self::Item) -> B,
413 {
414 let mut accum: B = init;
415 while let Some(x: ::Item) = self.next_back() {
416 accum = f(accum, x);
417 }
418 accum
419 }
420
421 default fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
422 where
423 F: FnMut(B, Self::Item) -> R,
424 R: Try<Output = B>,
425 {
426 let mut accum: B = init;
427 while let Some(x: ::Item) = self.next_back() {
428 accum = f(accum, x)?;
429 }
430 try { accum }
431 }
432}
433
434impl<I: DoubleEndedIterator> DoubleEndedIteratorRefSpec for &mut I {
435 impl_fold_via_try_fold! { spec_rfold -> spec_try_rfold }
436
437 fn spec_try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
438 where
439 F: FnMut(B, Self::Item) -> R,
440 R: Try<Output = B>,
441 {
442 (**self).try_rfold(init, f)
443 }
444}
445