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