1 | use crate::num::NonZero; |
2 | use 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" )] |
41 | pub 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" , reason = "recently added" , 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.iter().rfind(|&&x| x == 2), Some(&2)); |
338 | /// |
339 | /// assert_eq!(a.iter().rfind(|&&x| x == 5), None); |
340 | /// ``` |
341 | /// |
342 | /// Stopping at the first `true`: |
343 | /// |
344 | /// ``` |
345 | /// let a = [1, 2, 3]; |
346 | /// |
347 | /// let mut iter = a.iter(); |
348 | /// |
349 | /// assert_eq!(iter.rfind(|&&x| x == 2), Some(&2)); |
350 | /// |
351 | /// // we can still use `iter`, as there are more elements. |
352 | /// assert_eq!(iter.next_back(), Some(&1)); |
353 | /// ``` |
354 | #[inline ] |
355 | #[stable (feature = "iter_rfind" , since = "1.27.0" )] |
356 | fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> |
357 | where |
358 | Self: Sized, |
359 | P: FnMut(&Self::Item) -> bool, |
360 | { |
361 | #[inline ] |
362 | fn check<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut((), T) -> ControlFlow<T> { |
363 | move |(), x| { |
364 | if predicate(&x) { ControlFlow::Break(x) } else { ControlFlow::Continue(()) } |
365 | } |
366 | } |
367 | |
368 | self.try_rfold((), check(predicate)).break_value() |
369 | } |
370 | } |
371 | |
372 | #[stable (feature = "rust1" , since = "1.0.0" )] |
373 | impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I { |
374 | fn next_back(&mut self) -> Option<I::Item> { |
375 | (**self).next_back() |
376 | } |
377 | fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> { |
378 | (**self).advance_back_by(n) |
379 | } |
380 | fn nth_back(&mut self, n: usize) -> Option<I::Item> { |
381 | (**self).nth_back(n) |
382 | } |
383 | fn rfold<B, F>(self, init: B, f: F) -> B |
384 | where |
385 | F: FnMut(B, Self::Item) -> B, |
386 | { |
387 | self.spec_rfold(init, f) |
388 | } |
389 | fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R |
390 | where |
391 | F: FnMut(B, Self::Item) -> R, |
392 | R: Try<Output = B>, |
393 | { |
394 | self.spec_try_rfold(init, f) |
395 | } |
396 | } |
397 | |
398 | /// Helper trait to specialize `rfold` and `rtry_fold` for `&mut I where I: Sized` |
399 | trait DoubleEndedIteratorRefSpec: DoubleEndedIterator { |
400 | fn spec_rfold<B, F>(self, init: B, f: F) -> B |
401 | where |
402 | F: FnMut(B, Self::Item) -> B; |
403 | |
404 | fn spec_try_rfold<B, F, R>(&mut self, init: B, f: F) -> R |
405 | where |
406 | F: FnMut(B, Self::Item) -> R, |
407 | R: Try<Output = B>; |
408 | } |
409 | |
410 | impl<I: DoubleEndedIterator + ?Sized> DoubleEndedIteratorRefSpec for &mut I { |
411 | default fn spec_rfold<B, F>(self, init: B, mut f: F) -> B |
412 | where |
413 | F: FnMut(B, Self::Item) -> B, |
414 | { |
415 | let mut accum: B = init; |
416 | while let Some(x: ::Item) = self.next_back() { |
417 | accum = f(accum, x); |
418 | } |
419 | accum |
420 | } |
421 | |
422 | default fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R |
423 | where |
424 | F: FnMut(B, Self::Item) -> R, |
425 | R: Try<Output = B>, |
426 | { |
427 | let mut accum: B = init; |
428 | while let Some(x: ::Item) = self.next_back() { |
429 | accum = f(accum, x)?; |
430 | } |
431 | try { accum } |
432 | } |
433 | } |
434 | |
435 | impl<I: DoubleEndedIterator> DoubleEndedIteratorRefSpec for &mut I { |
436 | impl_fold_via_try_fold! { spec_rfold -> spec_try_rfold } |
437 | |
438 | fn spec_try_rfold<B, F, R>(&mut self, init: B, f: F) -> R |
439 | where |
440 | F: FnMut(B, Self::Item) -> R, |
441 | R: Try<Output = B>, |
442 | { |
443 | (**self).try_rfold(init, f) |
444 | } |
445 | } |
446 | |