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