]>
Commit | Line | Data |
---|---|---|
a7813a04 XL |
1 | // Copyright 2013-2016 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
abe05a73 | 10 | use ops::{Mul, Add, Try}; |
c30ab7b3 | 11 | use num::Wrapping; |
a7813a04 | 12 | |
abe05a73 XL |
13 | use super::{AlwaysOk, LoopState}; |
14 | ||
a7813a04 XL |
15 | /// Conversion from an `Iterator`. |
16 | /// | |
17 | /// By implementing `FromIterator` for a type, you define how it will be | |
18 | /// created from an iterator. This is common for types which describe a | |
19 | /// collection of some kind. | |
20 | /// | |
cc61c64b XL |
21 | /// `FromIterator`'s [`from_iter`] is rarely called explicitly, and is instead |
22 | /// used through [`Iterator`]'s [`collect`] method. See [`collect`]'s | |
a7813a04 XL |
23 | /// documentation for more examples. |
24 | /// | |
cc61c64b | 25 | /// [`from_iter`]: #tymethod.from_iter |
a7813a04 | 26 | /// [`Iterator`]: trait.Iterator.html |
cc61c64b | 27 | /// [`collect`]: trait.Iterator.html#method.collect |
a7813a04 XL |
28 | /// |
29 | /// See also: [`IntoIterator`]. | |
30 | /// | |
31 | /// [`IntoIterator`]: trait.IntoIterator.html | |
32 | /// | |
33 | /// # Examples | |
34 | /// | |
35 | /// Basic usage: | |
36 | /// | |
37 | /// ``` | |
38 | /// use std::iter::FromIterator; | |
39 | /// | |
40 | /// let five_fives = std::iter::repeat(5).take(5); | |
41 | /// | |
42 | /// let v = Vec::from_iter(five_fives); | |
43 | /// | |
44 | /// assert_eq!(v, vec![5, 5, 5, 5, 5]); | |
45 | /// ``` | |
46 | /// | |
cc61c64b | 47 | /// Using [`collect`] to implicitly use `FromIterator`: |
a7813a04 XL |
48 | /// |
49 | /// ``` | |
50 | /// let five_fives = std::iter::repeat(5).take(5); | |
51 | /// | |
52 | /// let v: Vec<i32> = five_fives.collect(); | |
53 | /// | |
54 | /// assert_eq!(v, vec![5, 5, 5, 5, 5]); | |
55 | /// ``` | |
56 | /// | |
57 | /// Implementing `FromIterator` for your type: | |
58 | /// | |
59 | /// ``` | |
60 | /// use std::iter::FromIterator; | |
61 | /// | |
62 | /// // A sample collection, that's just a wrapper over Vec<T> | |
63 | /// #[derive(Debug)] | |
64 | /// struct MyCollection(Vec<i32>); | |
65 | /// | |
66 | /// // Let's give it some methods so we can create one and add things | |
67 | /// // to it. | |
68 | /// impl MyCollection { | |
69 | /// fn new() -> MyCollection { | |
70 | /// MyCollection(Vec::new()) | |
71 | /// } | |
72 | /// | |
73 | /// fn add(&mut self, elem: i32) { | |
74 | /// self.0.push(elem); | |
75 | /// } | |
76 | /// } | |
77 | /// | |
78 | /// // and we'll implement FromIterator | |
79 | /// impl FromIterator<i32> for MyCollection { | |
80 | /// fn from_iter<I: IntoIterator<Item=i32>>(iter: I) -> Self { | |
81 | /// let mut c = MyCollection::new(); | |
82 | /// | |
83 | /// for i in iter { | |
84 | /// c.add(i); | |
85 | /// } | |
86 | /// | |
87 | /// c | |
88 | /// } | |
89 | /// } | |
90 | /// | |
91 | /// // Now we can make a new iterator... | |
92 | /// let iter = (0..5).into_iter(); | |
93 | /// | |
94 | /// // ... and make a MyCollection out of it | |
95 | /// let c = MyCollection::from_iter(iter); | |
96 | /// | |
97 | /// assert_eq!(c.0, vec![0, 1, 2, 3, 4]); | |
98 | /// | |
99 | /// // collect works too! | |
100 | /// | |
101 | /// let iter = (0..5).into_iter(); | |
102 | /// let c: MyCollection = iter.collect(); | |
103 | /// | |
104 | /// assert_eq!(c.0, vec![0, 1, 2, 3, 4]); | |
105 | /// ``` | |
106 | #[stable(feature = "rust1", since = "1.0.0")] | |
107 | #[rustc_on_unimplemented="a collection of type `{Self}` cannot be \ | |
108 | built from an iterator over elements of type `{A}`"] | |
109 | pub trait FromIterator<A>: Sized { | |
110 | /// Creates a value from an iterator. | |
111 | /// | |
112 | /// See the [module-level documentation] for more. | |
113 | /// | |
7cac9316 | 114 | /// [module-level documentation]: index.html |
a7813a04 XL |
115 | /// |
116 | /// # Examples | |
117 | /// | |
118 | /// Basic usage: | |
119 | /// | |
120 | /// ``` | |
121 | /// use std::iter::FromIterator; | |
122 | /// | |
123 | /// let five_fives = std::iter::repeat(5).take(5); | |
124 | /// | |
125 | /// let v = Vec::from_iter(five_fives); | |
126 | /// | |
127 | /// assert_eq!(v, vec![5, 5, 5, 5, 5]); | |
128 | /// ``` | |
129 | #[stable(feature = "rust1", since = "1.0.0")] | |
130 | fn from_iter<T: IntoIterator<Item=A>>(iter: T) -> Self; | |
131 | } | |
132 | ||
133 | /// Conversion into an `Iterator`. | |
134 | /// | |
135 | /// By implementing `IntoIterator` for a type, you define how it will be | |
136 | /// converted to an iterator. This is common for types which describe a | |
137 | /// collection of some kind. | |
138 | /// | |
139 | /// One benefit of implementing `IntoIterator` is that your type will [work | |
140 | /// with Rust's `for` loop syntax](index.html#for-loops-and-intoiterator). | |
141 | /// | |
142 | /// See also: [`FromIterator`]. | |
143 | /// | |
144 | /// [`FromIterator`]: trait.FromIterator.html | |
145 | /// | |
146 | /// # Examples | |
147 | /// | |
148 | /// Basic usage: | |
149 | /// | |
150 | /// ``` | |
151 | /// let v = vec![1, 2, 3]; | |
a7813a04 XL |
152 | /// let mut iter = v.into_iter(); |
153 | /// | |
3b2f2976 XL |
154 | /// assert_eq!(Some(1), iter.next()); |
155 | /// assert_eq!(Some(2), iter.next()); | |
156 | /// assert_eq!(Some(3), iter.next()); | |
157 | /// assert_eq!(None, iter.next()); | |
a7813a04 | 158 | /// ``` |
a7813a04 XL |
159 | /// Implementing `IntoIterator` for your type: |
160 | /// | |
161 | /// ``` | |
162 | /// // A sample collection, that's just a wrapper over Vec<T> | |
163 | /// #[derive(Debug)] | |
164 | /// struct MyCollection(Vec<i32>); | |
165 | /// | |
166 | /// // Let's give it some methods so we can create one and add things | |
167 | /// // to it. | |
168 | /// impl MyCollection { | |
169 | /// fn new() -> MyCollection { | |
170 | /// MyCollection(Vec::new()) | |
171 | /// } | |
172 | /// | |
173 | /// fn add(&mut self, elem: i32) { | |
174 | /// self.0.push(elem); | |
175 | /// } | |
176 | /// } | |
177 | /// | |
178 | /// // and we'll implement IntoIterator | |
179 | /// impl IntoIterator for MyCollection { | |
180 | /// type Item = i32; | |
181 | /// type IntoIter = ::std::vec::IntoIter<i32>; | |
182 | /// | |
183 | /// fn into_iter(self) -> Self::IntoIter { | |
184 | /// self.0.into_iter() | |
185 | /// } | |
186 | /// } | |
187 | /// | |
188 | /// // Now we can make a new collection... | |
189 | /// let mut c = MyCollection::new(); | |
190 | /// | |
191 | /// // ... add some stuff to it ... | |
192 | /// c.add(0); | |
193 | /// c.add(1); | |
194 | /// c.add(2); | |
195 | /// | |
196 | /// // ... and then turn it into an Iterator: | |
197 | /// for (i, n) in c.into_iter().enumerate() { | |
198 | /// assert_eq!(i as i32, n); | |
199 | /// } | |
200 | /// ``` | |
ea8adc8c XL |
201 | /// |
202 | /// It is common to use `IntoIterator` as a trait bound. This allows | |
203 | /// the input collection type to change, so long as it is still an | |
204 | /// iterator. Additional bounds can be specified by restricting on | |
205 | /// `Item`: | |
206 | /// | |
207 | /// ```rust | |
208 | /// fn collect_as_strings<T>(collection: T) -> Vec<String> | |
209 | /// where T: IntoIterator, | |
210 | /// T::Item : std::fmt::Debug, | |
211 | /// { | |
212 | /// collection | |
213 | /// .into_iter() | |
214 | /// .map(|item| format!("{:?}", item)) | |
215 | /// .collect() | |
216 | /// } | |
217 | /// ``` | |
a7813a04 XL |
218 | #[stable(feature = "rust1", since = "1.0.0")] |
219 | pub trait IntoIterator { | |
220 | /// The type of the elements being iterated over. | |
221 | #[stable(feature = "rust1", since = "1.0.0")] | |
222 | type Item; | |
223 | ||
224 | /// Which kind of iterator are we turning this into? | |
225 | #[stable(feature = "rust1", since = "1.0.0")] | |
226 | type IntoIter: Iterator<Item=Self::Item>; | |
227 | ||
228 | /// Creates an iterator from a value. | |
229 | /// | |
230 | /// See the [module-level documentation] for more. | |
231 | /// | |
7cac9316 | 232 | /// [module-level documentation]: index.html |
a7813a04 XL |
233 | /// |
234 | /// # Examples | |
235 | /// | |
236 | /// Basic usage: | |
237 | /// | |
238 | /// ``` | |
239 | /// let v = vec![1, 2, 3]; | |
a7813a04 XL |
240 | /// let mut iter = v.into_iter(); |
241 | /// | |
3b2f2976 XL |
242 | /// assert_eq!(Some(1), iter.next()); |
243 | /// assert_eq!(Some(2), iter.next()); | |
244 | /// assert_eq!(Some(3), iter.next()); | |
245 | /// assert_eq!(None, iter.next()); | |
a7813a04 XL |
246 | /// ``` |
247 | #[stable(feature = "rust1", since = "1.0.0")] | |
248 | fn into_iter(self) -> Self::IntoIter; | |
249 | } | |
250 | ||
251 | #[stable(feature = "rust1", since = "1.0.0")] | |
252 | impl<I: Iterator> IntoIterator for I { | |
253 | type Item = I::Item; | |
254 | type IntoIter = I; | |
255 | ||
256 | fn into_iter(self) -> I { | |
257 | self | |
258 | } | |
259 | } | |
260 | ||
261 | /// Extend a collection with the contents of an iterator. | |
262 | /// | |
263 | /// Iterators produce a series of values, and collections can also be thought | |
264 | /// of as a series of values. The `Extend` trait bridges this gap, allowing you | |
32a655c1 SL |
265 | /// to extend a collection by including the contents of that iterator. When |
266 | /// extending a collection with an already existing key, that entry is updated | |
267 | /// or, in the case of collections that permit multiple entries with equal | |
268 | /// keys, that entry is inserted. | |
a7813a04 XL |
269 | /// |
270 | /// # Examples | |
271 | /// | |
272 | /// Basic usage: | |
273 | /// | |
274 | /// ``` | |
275 | /// // You can extend a String with some chars: | |
276 | /// let mut message = String::from("The first three letters are: "); | |
277 | /// | |
278 | /// message.extend(&['a', 'b', 'c']); | |
279 | /// | |
280 | /// assert_eq!("abc", &message[29..32]); | |
281 | /// ``` | |
282 | /// | |
283 | /// Implementing `Extend`: | |
284 | /// | |
285 | /// ``` | |
286 | /// // A sample collection, that's just a wrapper over Vec<T> | |
287 | /// #[derive(Debug)] | |
288 | /// struct MyCollection(Vec<i32>); | |
289 | /// | |
290 | /// // Let's give it some methods so we can create one and add things | |
291 | /// // to it. | |
292 | /// impl MyCollection { | |
293 | /// fn new() -> MyCollection { | |
294 | /// MyCollection(Vec::new()) | |
295 | /// } | |
296 | /// | |
297 | /// fn add(&mut self, elem: i32) { | |
298 | /// self.0.push(elem); | |
299 | /// } | |
300 | /// } | |
301 | /// | |
302 | /// // since MyCollection has a list of i32s, we implement Extend for i32 | |
303 | /// impl Extend<i32> for MyCollection { | |
304 | /// | |
305 | /// // This is a bit simpler with the concrete type signature: we can call | |
306 | /// // extend on anything which can be turned into an Iterator which gives | |
307 | /// // us i32s. Because we need i32s to put into MyCollection. | |
308 | /// fn extend<T: IntoIterator<Item=i32>>(&mut self, iter: T) { | |
309 | /// | |
310 | /// // The implementation is very straightforward: loop through the | |
311 | /// // iterator, and add() each element to ourselves. | |
312 | /// for elem in iter { | |
313 | /// self.add(elem); | |
314 | /// } | |
315 | /// } | |
316 | /// } | |
317 | /// | |
318 | /// let mut c = MyCollection::new(); | |
319 | /// | |
320 | /// c.add(5); | |
321 | /// c.add(6); | |
322 | /// c.add(7); | |
323 | /// | |
324 | /// // let's extend our collection with three more numbers | |
325 | /// c.extend(vec![1, 2, 3]); | |
326 | /// | |
327 | /// // we've added these elements onto the end | |
328 | /// assert_eq!("MyCollection([5, 6, 7, 1, 2, 3])", format!("{:?}", c)); | |
329 | /// ``` | |
330 | #[stable(feature = "rust1", since = "1.0.0")] | |
331 | pub trait Extend<A> { | |
332 | /// Extends a collection with the contents of an iterator. | |
333 | /// | |
334 | /// As this is the only method for this trait, the [trait-level] docs | |
335 | /// contain more details. | |
336 | /// | |
337 | /// [trait-level]: trait.Extend.html | |
338 | /// | |
339 | /// # Examples | |
340 | /// | |
341 | /// Basic usage: | |
342 | /// | |
343 | /// ``` | |
344 | /// // You can extend a String with some chars: | |
345 | /// let mut message = String::from("abc"); | |
346 | /// | |
347 | /// message.extend(['d', 'e', 'f'].iter()); | |
348 | /// | |
349 | /// assert_eq!("abcdef", &message); | |
350 | /// ``` | |
351 | #[stable(feature = "rust1", since = "1.0.0")] | |
352 | fn extend<T: IntoIterator<Item=A>>(&mut self, iter: T); | |
353 | } | |
354 | ||
355 | /// An iterator able to yield elements from both ends. | |
356 | /// | |
357 | /// Something that implements `DoubleEndedIterator` has one extra capability | |
358 | /// over something that implements [`Iterator`]: the ability to also take | |
359 | /// `Item`s from the back, as well as the front. | |
360 | /// | |
361 | /// It is important to note that both back and forth work on the same range, | |
362 | /// and do not cross: iteration is over when they meet in the middle. | |
363 | /// | |
364 | /// In a similar fashion to the [`Iterator`] protocol, once a | |
365 | /// `DoubleEndedIterator` returns `None` from a `next_back()`, calling it again | |
366 | /// may or may not ever return `Some` again. `next()` and `next_back()` are | |
3b2f2976 | 367 | /// interchangeable for this purpose. |
a7813a04 XL |
368 | /// |
369 | /// [`Iterator`]: trait.Iterator.html | |
370 | /// | |
371 | /// # Examples | |
372 | /// | |
373 | /// Basic usage: | |
374 | /// | |
375 | /// ``` | |
5bcae85e | 376 | /// let numbers = vec![1, 2, 3, 4, 5, 6]; |
a7813a04 XL |
377 | /// |
378 | /// let mut iter = numbers.iter(); | |
379 | /// | |
380 | /// assert_eq!(Some(&1), iter.next()); | |
5bcae85e SL |
381 | /// assert_eq!(Some(&6), iter.next_back()); |
382 | /// assert_eq!(Some(&5), iter.next_back()); | |
383 | /// assert_eq!(Some(&2), iter.next()); | |
384 | /// assert_eq!(Some(&3), iter.next()); | |
385 | /// assert_eq!(Some(&4), iter.next()); | |
a7813a04 XL |
386 | /// assert_eq!(None, iter.next()); |
387 | /// assert_eq!(None, iter.next_back()); | |
388 | /// ``` | |
389 | #[stable(feature = "rust1", since = "1.0.0")] | |
390 | pub trait DoubleEndedIterator: Iterator { | |
5bcae85e | 391 | /// Removes and returns an element from the end of the iterator. |
a7813a04 | 392 | /// |
5bcae85e SL |
393 | /// Returns `None` when there are no more elements. |
394 | /// | |
395 | /// The [trait-level] docs contain more details. | |
a7813a04 XL |
396 | /// |
397 | /// [trait-level]: trait.DoubleEndedIterator.html | |
398 | /// | |
399 | /// # Examples | |
400 | /// | |
401 | /// Basic usage: | |
402 | /// | |
403 | /// ``` | |
5bcae85e | 404 | /// let numbers = vec![1, 2, 3, 4, 5, 6]; |
a7813a04 XL |
405 | /// |
406 | /// let mut iter = numbers.iter(); | |
407 | /// | |
408 | /// assert_eq!(Some(&1), iter.next()); | |
5bcae85e SL |
409 | /// assert_eq!(Some(&6), iter.next_back()); |
410 | /// assert_eq!(Some(&5), iter.next_back()); | |
411 | /// assert_eq!(Some(&2), iter.next()); | |
412 | /// assert_eq!(Some(&3), iter.next()); | |
413 | /// assert_eq!(Some(&4), iter.next()); | |
a7813a04 XL |
414 | /// assert_eq!(None, iter.next()); |
415 | /// assert_eq!(None, iter.next_back()); | |
416 | /// ``` | |
417 | #[stable(feature = "rust1", since = "1.0.0")] | |
418 | fn next_back(&mut self) -> Option<Self::Item>; | |
8bb4bdeb | 419 | |
abe05a73 XL |
420 | /// This is the reverse version of [`try_fold()`]: it takes elements |
421 | /// starting from the back of the iterator. | |
422 | /// | |
423 | /// [`try_fold()`]: trait.Iterator.html#method.try_fold | |
424 | /// | |
425 | /// # Examples | |
426 | /// | |
427 | /// Basic usage: | |
428 | /// | |
429 | /// ``` | |
430 | /// #![feature(iterator_try_fold)] | |
431 | /// let a = ["1", "2", "3"]; | |
432 | /// let sum = a.iter() | |
433 | /// .map(|&s| s.parse::<i32>()) | |
434 | /// .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y))); | |
435 | /// assert_eq!(sum, Ok(6)); | |
436 | /// ``` | |
437 | /// | |
438 | /// Short-circuiting: | |
439 | /// | |
440 | /// ``` | |
441 | /// #![feature(iterator_try_fold)] | |
442 | /// let a = ["1", "rust", "3"]; | |
443 | /// let mut it = a.iter(); | |
444 | /// let sum = it | |
445 | /// .by_ref() | |
446 | /// .map(|&s| s.parse::<i32>()) | |
447 | /// .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y))); | |
448 | /// assert!(sum.is_err()); | |
449 | /// | |
450 | /// // Because it short-circuited, the remaining elements are still | |
451 | /// // available through the iterator. | |
452 | /// assert_eq!(it.next_back(), Some(&"1")); | |
453 | /// ``` | |
454 | #[inline] | |
455 | #[unstable(feature = "iterator_try_fold", issue = "45594")] | |
456 | fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where | |
457 | Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B> | |
458 | { | |
459 | let mut accum = init; | |
460 | while let Some(x) = self.next_back() { | |
461 | accum = f(accum, x)?; | |
462 | } | |
463 | Try::from_ok(accum) | |
464 | } | |
465 | ||
ea8adc8c XL |
466 | /// An iterator method that reduces the iterator's elements to a single, |
467 | /// final value, starting from the back. | |
468 | /// | |
469 | /// This is the reverse version of [`fold()`]: it takes elements starting from | |
470 | /// the back of the iterator. | |
471 | /// | |
472 | /// `rfold()` takes two arguments: an initial value, and a closure with two | |
473 | /// arguments: an 'accumulator', and an element. The closure returns the value that | |
474 | /// the accumulator should have for the next iteration. | |
475 | /// | |
476 | /// The initial value is the value the accumulator will have on the first | |
477 | /// call. | |
478 | /// | |
479 | /// After applying this closure to every element of the iterator, `rfold()` | |
480 | /// returns the accumulator. | |
481 | /// | |
482 | /// This operation is sometimes called 'reduce' or 'inject'. | |
483 | /// | |
484 | /// Folding is useful whenever you have a collection of something, and want | |
485 | /// to produce a single value from it. | |
486 | /// | |
487 | /// [`fold()`]: trait.Iterator.html#method.fold | |
488 | /// | |
489 | /// # Examples | |
490 | /// | |
491 | /// Basic usage: | |
492 | /// | |
493 | /// ``` | |
494 | /// #![feature(iter_rfold)] | |
495 | /// let a = [1, 2, 3]; | |
496 | /// | |
497 | /// // the sum of all of the elements of a | |
498 | /// let sum = a.iter() | |
499 | /// .rfold(0, |acc, &x| acc + x); | |
500 | /// | |
501 | /// assert_eq!(sum, 6); | |
502 | /// ``` | |
503 | /// | |
504 | /// This example builds a string, starting with an initial value | |
505 | /// and continuing with each element from the back until the front: | |
506 | /// | |
507 | /// ``` | |
508 | /// #![feature(iter_rfold)] | |
509 | /// let numbers = [1, 2, 3, 4, 5]; | |
510 | /// | |
511 | /// let zero = "0".to_string(); | |
512 | /// | |
513 | /// let result = numbers.iter().rfold(zero, |acc, &x| { | |
514 | /// format!("({} + {})", x, acc) | |
515 | /// }); | |
516 | /// | |
517 | /// assert_eq!(result, "(1 + (2 + (3 + (4 + (5 + 0)))))"); | |
518 | /// ``` | |
519 | #[inline] | |
520 | #[unstable(feature = "iter_rfold", issue = "44705")] | |
abe05a73 | 521 | fn rfold<B, F>(mut self, accum: B, mut f: F) -> B where |
ea8adc8c XL |
522 | Self: Sized, F: FnMut(B, Self::Item) -> B, |
523 | { | |
abe05a73 | 524 | self.try_rfold(accum, move |acc, x| AlwaysOk(f(acc, x))).0 |
ea8adc8c XL |
525 | } |
526 | ||
8bb4bdeb XL |
527 | /// Searches for an element of an iterator from the right that satisfies a predicate. |
528 | /// | |
529 | /// `rfind()` takes a closure that returns `true` or `false`. It applies | |
530 | /// this closure to each element of the iterator, starting at the end, and if any | |
531 | /// of them return `true`, then `rfind()` returns [`Some(element)`]. If they all return | |
532 | /// `false`, it returns [`None`]. | |
533 | /// | |
534 | /// `rfind()` is short-circuiting; in other words, it will stop processing | |
535 | /// as soon as the closure returns `true`. | |
536 | /// | |
537 | /// Because `rfind()` takes a reference, and many iterators iterate over | |
538 | /// references, this leads to a possibly confusing situation where the | |
539 | /// argument is a double reference. You can see this effect in the | |
540 | /// examples below, with `&&x`. | |
541 | /// | |
542 | /// [`Some(element)`]: ../../std/option/enum.Option.html#variant.Some | |
543 | /// [`None`]: ../../std/option/enum.Option.html#variant.None | |
544 | /// | |
545 | /// # Examples | |
546 | /// | |
547 | /// Basic usage: | |
548 | /// | |
549 | /// ``` | |
550 | /// #![feature(iter_rfind)] | |
551 | /// | |
552 | /// let a = [1, 2, 3]; | |
553 | /// | |
554 | /// assert_eq!(a.iter().rfind(|&&x| x == 2), Some(&2)); | |
555 | /// | |
556 | /// assert_eq!(a.iter().rfind(|&&x| x == 5), None); | |
557 | /// ``` | |
558 | /// | |
559 | /// Stopping at the first `true`: | |
560 | /// | |
561 | /// ``` | |
562 | /// #![feature(iter_rfind)] | |
563 | /// | |
564 | /// let a = [1, 2, 3]; | |
565 | /// | |
566 | /// let mut iter = a.iter(); | |
567 | /// | |
568 | /// assert_eq!(iter.rfind(|&&x| x == 2), Some(&2)); | |
569 | /// | |
570 | /// // we can still use `iter`, as there are more elements. | |
571 | /// assert_eq!(iter.next_back(), Some(&1)); | |
572 | /// ``` | |
573 | #[inline] | |
574 | #[unstable(feature = "iter_rfind", issue = "39480")] | |
575 | fn rfind<P>(&mut self, mut predicate: P) -> Option<Self::Item> where | |
576 | Self: Sized, | |
577 | P: FnMut(&Self::Item) -> bool | |
578 | { | |
abe05a73 XL |
579 | self.try_rfold((), move |(), x| { |
580 | if predicate(&x) { LoopState::Break(x) } | |
581 | else { LoopState::Continue(()) } | |
582 | }).break_value() | |
8bb4bdeb | 583 | } |
a7813a04 XL |
584 | } |
585 | ||
586 | #[stable(feature = "rust1", since = "1.0.0")] | |
587 | impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I { | |
588 | fn next_back(&mut self) -> Option<I::Item> { (**self).next_back() } | |
589 | } | |
590 | ||
591 | /// An iterator that knows its exact length. | |
592 | /// | |
593 | /// Many [`Iterator`]s don't know how many times they will iterate, but some do. | |
594 | /// If an iterator knows how many times it can iterate, providing access to | |
595 | /// that information can be useful. For example, if you want to iterate | |
596 | /// backwards, a good start is to know where the end is. | |
597 | /// | |
598 | /// When implementing an `ExactSizeIterator`, You must also implement | |
cc61c64b | 599 | /// [`Iterator`]. When doing so, the implementation of [`size_hint`] *must* |
a7813a04 XL |
600 | /// return the exact size of the iterator. |
601 | /// | |
602 | /// [`Iterator`]: trait.Iterator.html | |
cc61c64b | 603 | /// [`size_hint`]: trait.Iterator.html#method.size_hint |
a7813a04 | 604 | /// |
cc61c64b | 605 | /// The [`len`] method has a default implementation, so you usually shouldn't |
a7813a04 XL |
606 | /// implement it. However, you may be able to provide a more performant |
607 | /// implementation than the default, so overriding it in this case makes sense. | |
608 | /// | |
cc61c64b | 609 | /// [`len`]: #method.len |
a7813a04 XL |
610 | /// |
611 | /// # Examples | |
612 | /// | |
613 | /// Basic usage: | |
614 | /// | |
615 | /// ``` | |
616 | /// // a finite range knows exactly how many times it will iterate | |
617 | /// let five = 0..5; | |
618 | /// | |
619 | /// assert_eq!(5, five.len()); | |
620 | /// ``` | |
621 | /// | |
622 | /// In the [module level docs][moddocs], we implemented an [`Iterator`], | |
623 | /// `Counter`. Let's implement `ExactSizeIterator` for it as well: | |
624 | /// | |
625 | /// [moddocs]: index.html | |
626 | /// | |
627 | /// ``` | |
628 | /// # struct Counter { | |
629 | /// # count: usize, | |
630 | /// # } | |
631 | /// # impl Counter { | |
632 | /// # fn new() -> Counter { | |
633 | /// # Counter { count: 0 } | |
634 | /// # } | |
635 | /// # } | |
636 | /// # impl Iterator for Counter { | |
637 | /// # type Item = usize; | |
638 | /// # fn next(&mut self) -> Option<usize> { | |
639 | /// # self.count += 1; | |
640 | /// # if self.count < 6 { | |
641 | /// # Some(self.count) | |
642 | /// # } else { | |
643 | /// # None | |
644 | /// # } | |
645 | /// # } | |
646 | /// # } | |
647 | /// impl ExactSizeIterator for Counter { | |
cc61c64b | 648 | /// // We can easily calculate the remaining number of iterations. |
a7813a04 | 649 | /// fn len(&self) -> usize { |
cc61c64b | 650 | /// 5 - self.count |
a7813a04 XL |
651 | /// } |
652 | /// } | |
653 | /// | |
654 | /// // And now we can use it! | |
655 | /// | |
656 | /// let counter = Counter::new(); | |
657 | /// | |
cc61c64b | 658 | /// assert_eq!(5, counter.len()); |
a7813a04 XL |
659 | /// ``` |
660 | #[stable(feature = "rust1", since = "1.0.0")] | |
661 | pub trait ExactSizeIterator: Iterator { | |
a7813a04 XL |
662 | /// Returns the exact number of times the iterator will iterate. |
663 | /// | |
664 | /// This method has a default implementation, so you usually should not | |
665 | /// implement it directly. However, if you can provide a more efficient | |
666 | /// implementation, you can do so. See the [trait-level] docs for an | |
667 | /// example. | |
668 | /// | |
cc61c64b | 669 | /// This function has the same safety guarantees as the [`size_hint`] |
a7813a04 XL |
670 | /// function. |
671 | /// | |
672 | /// [trait-level]: trait.ExactSizeIterator.html | |
cc61c64b | 673 | /// [`size_hint`]: trait.Iterator.html#method.size_hint |
a7813a04 XL |
674 | /// |
675 | /// # Examples | |
676 | /// | |
677 | /// Basic usage: | |
678 | /// | |
679 | /// ``` | |
680 | /// // a finite range knows exactly how many times it will iterate | |
681 | /// let five = 0..5; | |
682 | /// | |
683 | /// assert_eq!(5, five.len()); | |
684 | /// ``` | |
5bcae85e SL |
685 | #[inline] |
686 | #[stable(feature = "rust1", since = "1.0.0")] | |
a7813a04 XL |
687 | fn len(&self) -> usize { |
688 | let (lower, upper) = self.size_hint(); | |
689 | // Note: This assertion is overly defensive, but it checks the invariant | |
690 | // guaranteed by the trait. If this trait were rust-internal, | |
691 | // we could use debug_assert!; assert_eq! will check all Rust user | |
692 | // implementations too. | |
693 | assert_eq!(upper, Some(lower)); | |
694 | lower | |
695 | } | |
5bcae85e SL |
696 | |
697 | /// Returns whether the iterator is empty. | |
698 | /// | |
699 | /// This method has a default implementation using `self.len()`, so you | |
700 | /// don't need to implement it yourself. | |
701 | /// | |
702 | /// # Examples | |
703 | /// | |
704 | /// Basic usage: | |
705 | /// | |
706 | /// ``` | |
707 | /// #![feature(exact_size_is_empty)] | |
708 | /// | |
709 | /// let mut one_element = 0..1; | |
710 | /// assert!(!one_element.is_empty()); | |
711 | /// | |
712 | /// assert_eq!(one_element.next(), Some(0)); | |
713 | /// assert!(one_element.is_empty()); | |
714 | /// | |
715 | /// assert_eq!(one_element.next(), None); | |
716 | /// ``` | |
717 | #[inline] | |
718 | #[unstable(feature = "exact_size_is_empty", issue = "35428")] | |
719 | fn is_empty(&self) -> bool { | |
720 | self.len() == 0 | |
721 | } | |
a7813a04 XL |
722 | } |
723 | ||
724 | #[stable(feature = "rust1", since = "1.0.0")] | |
476ff2be SL |
725 | impl<'a, I: ExactSizeIterator + ?Sized> ExactSizeIterator for &'a mut I { |
726 | fn len(&self) -> usize { | |
727 | (**self).len() | |
728 | } | |
729 | fn is_empty(&self) -> bool { | |
730 | (**self).is_empty() | |
731 | } | |
732 | } | |
a7813a04 | 733 | |
3157f602 XL |
734 | /// Trait to represent types that can be created by summing up an iterator. |
735 | /// | |
cc61c64b XL |
736 | /// This trait is used to implement the [`sum`] method on iterators. Types which |
737 | /// implement the trait can be generated by the [`sum`] method. Like | |
476ff2be | 738 | /// [`FromIterator`] this trait should rarely be called directly and instead |
cc61c64b | 739 | /// interacted with through [`Iterator::sum`]. |
476ff2be | 740 | /// |
cc61c64b | 741 | /// [`sum`]: ../../std/iter/trait.Sum.html#tymethod.sum |
476ff2be | 742 | /// [`FromIterator`]: ../../std/iter/trait.FromIterator.html |
cc61c64b | 743 | /// [`Iterator::sum`]: ../../std/iter/trait.Iterator.html#method.sum |
5bcae85e | 744 | #[stable(feature = "iter_arith_traits", since = "1.12.0")] |
3157f602 XL |
745 | pub trait Sum<A = Self>: Sized { |
746 | /// Method which takes an iterator and generates `Self` from the elements by | |
747 | /// "summing up" the items. | |
5bcae85e | 748 | #[stable(feature = "iter_arith_traits", since = "1.12.0")] |
3157f602 XL |
749 | fn sum<I: Iterator<Item=A>>(iter: I) -> Self; |
750 | } | |
751 | ||
752 | /// Trait to represent types that can be created by multiplying elements of an | |
753 | /// iterator. | |
754 | /// | |
cc61c64b XL |
755 | /// This trait is used to implement the [`product`] method on iterators. Types |
756 | /// which implement the trait can be generated by the [`product`] method. Like | |
476ff2be | 757 | /// [`FromIterator`] this trait should rarely be called directly and instead |
cc61c64b | 758 | /// interacted with through [`Iterator::product`]. |
476ff2be | 759 | /// |
cc61c64b | 760 | /// [`product`]: ../../std/iter/trait.Product.html#tymethod.product |
476ff2be | 761 | /// [`FromIterator`]: ../../std/iter/trait.FromIterator.html |
cc61c64b | 762 | /// [`Iterator::product`]: ../../std/iter/trait.Iterator.html#method.product |
5bcae85e | 763 | #[stable(feature = "iter_arith_traits", since = "1.12.0")] |
3157f602 XL |
764 | pub trait Product<A = Self>: Sized { |
765 | /// Method which takes an iterator and generates `Self` from the elements by | |
766 | /// multiplying the items. | |
5bcae85e | 767 | #[stable(feature = "iter_arith_traits", since = "1.12.0")] |
3157f602 XL |
768 | fn product<I: Iterator<Item=A>>(iter: I) -> Self; |
769 | } | |
770 | ||
9e0c209e | 771 | // NB: explicitly use Add and Mul here to inherit overflow checks |
3157f602 | 772 | macro_rules! integer_sum_product { |
8bb4bdeb XL |
773 | (@impls $zero:expr, $one:expr, #[$attr:meta], $($a:ty)*) => ($( |
774 | #[$attr] | |
3157f602 XL |
775 | impl Sum for $a { |
776 | fn sum<I: Iterator<Item=$a>>(iter: I) -> $a { | |
c30ab7b3 | 777 | iter.fold($zero, Add::add) |
3157f602 XL |
778 | } |
779 | } | |
780 | ||
8bb4bdeb | 781 | #[$attr] |
3157f602 XL |
782 | impl Product for $a { |
783 | fn product<I: Iterator<Item=$a>>(iter: I) -> $a { | |
c30ab7b3 | 784 | iter.fold($one, Mul::mul) |
3157f602 XL |
785 | } |
786 | } | |
787 | ||
8bb4bdeb | 788 | #[$attr] |
3157f602 XL |
789 | impl<'a> Sum<&'a $a> for $a { |
790 | fn sum<I: Iterator<Item=&'a $a>>(iter: I) -> $a { | |
c30ab7b3 | 791 | iter.fold($zero, Add::add) |
3157f602 XL |
792 | } |
793 | } | |
794 | ||
8bb4bdeb | 795 | #[$attr] |
3157f602 XL |
796 | impl<'a> Product<&'a $a> for $a { |
797 | fn product<I: Iterator<Item=&'a $a>>(iter: I) -> $a { | |
c30ab7b3 | 798 | iter.fold($one, Mul::mul) |
3157f602 XL |
799 | } |
800 | } | |
c30ab7b3 SL |
801 | )*); |
802 | ($($a:ty)*) => ( | |
8bb4bdeb XL |
803 | integer_sum_product!(@impls 0, 1, |
804 | #[stable(feature = "iter_arith_traits", since = "1.12.0")], | |
805 | $($a)+); | |
806 | integer_sum_product!(@impls Wrapping(0), Wrapping(1), | |
807 | #[stable(feature = "wrapping_iter_arith", since = "1.14.0")], | |
808 | $(Wrapping<$a>)+); | |
c30ab7b3 | 809 | ); |
3157f602 XL |
810 | } |
811 | ||
812 | macro_rules! float_sum_product { | |
813 | ($($a:ident)*) => ($( | |
5bcae85e | 814 | #[stable(feature = "iter_arith_traits", since = "1.12.0")] |
3157f602 XL |
815 | impl Sum for $a { |
816 | fn sum<I: Iterator<Item=$a>>(iter: I) -> $a { | |
817 | iter.fold(0.0, |a, b| a + b) | |
818 | } | |
819 | } | |
820 | ||
5bcae85e | 821 | #[stable(feature = "iter_arith_traits", since = "1.12.0")] |
3157f602 XL |
822 | impl Product for $a { |
823 | fn product<I: Iterator<Item=$a>>(iter: I) -> $a { | |
824 | iter.fold(1.0, |a, b| a * b) | |
825 | } | |
826 | } | |
827 | ||
5bcae85e | 828 | #[stable(feature = "iter_arith_traits", since = "1.12.0")] |
3157f602 XL |
829 | impl<'a> Sum<&'a $a> for $a { |
830 | fn sum<I: Iterator<Item=&'a $a>>(iter: I) -> $a { | |
831 | iter.fold(0.0, |a, b| a + *b) | |
832 | } | |
833 | } | |
834 | ||
5bcae85e | 835 | #[stable(feature = "iter_arith_traits", since = "1.12.0")] |
3157f602 XL |
836 | impl<'a> Product<&'a $a> for $a { |
837 | fn product<I: Iterator<Item=&'a $a>>(iter: I) -> $a { | |
838 | iter.fold(1.0, |a, b| a * *b) | |
839 | } | |
840 | } | |
841 | )*) | |
842 | } | |
843 | ||
041b39d2 | 844 | integer_sum_product! { i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize } |
3157f602 | 845 | float_sum_product! { f32 f64 } |
9e0c209e | 846 | |
32a655c1 SL |
847 | /// An iterator adapter that produces output as long as the underlying |
848 | /// iterator produces `Result::Ok` values. | |
849 | /// | |
850 | /// If an error is encountered, the iterator stops and the error is | |
851 | /// stored. The error may be recovered later via `reconstruct`. | |
852 | struct ResultShunt<I, E> { | |
853 | iter: I, | |
854 | error: Option<E>, | |
855 | } | |
856 | ||
857 | impl<I, T, E> ResultShunt<I, E> | |
858 | where I: Iterator<Item = Result<T, E>> | |
859 | { | |
860 | /// Process the given iterator as if it yielded a `T` instead of a | |
861 | /// `Result<T, _>`. Any errors will stop the inner iterator and | |
862 | /// the overall result will be an error. | |
863 | pub fn process<F, U>(iter: I, mut f: F) -> Result<U, E> | |
864 | where F: FnMut(&mut Self) -> U | |
865 | { | |
866 | let mut shunt = ResultShunt::new(iter); | |
867 | let value = f(shunt.by_ref()); | |
868 | shunt.reconstruct(value) | |
869 | } | |
870 | ||
871 | fn new(iter: I) -> Self { | |
872 | ResultShunt { | |
3b2f2976 | 873 | iter, |
32a655c1 SL |
874 | error: None, |
875 | } | |
876 | } | |
877 | ||
878 | /// Consume the adapter and rebuild a `Result` value. This should | |
879 | /// *always* be called, otherwise any potential error would be | |
880 | /// lost. | |
881 | fn reconstruct<U>(self, val: U) -> Result<U, E> { | |
882 | match self.error { | |
883 | None => Ok(val), | |
884 | Some(e) => Err(e), | |
885 | } | |
886 | } | |
887 | } | |
888 | ||
889 | impl<I, T, E> Iterator for ResultShunt<I, E> | |
890 | where I: Iterator<Item = Result<T, E>> | |
891 | { | |
892 | type Item = T; | |
893 | ||
894 | fn next(&mut self) -> Option<Self::Item> { | |
895 | match self.iter.next() { | |
896 | Some(Ok(v)) => Some(v), | |
897 | Some(Err(e)) => { | |
898 | self.error = Some(e); | |
899 | None | |
900 | } | |
901 | None => None, | |
902 | } | |
903 | } | |
904 | } | |
905 | ||
906 | #[stable(feature = "iter_arith_traits_result", since="1.16.0")] | |
907 | impl<T, U, E> Sum<Result<U, E>> for Result<T, E> | |
908 | where T: Sum<U>, | |
909 | { | |
041b39d2 XL |
910 | /// Takes each element in the `Iterator`: if it is an `Err`, no further |
911 | /// elements are taken, and the `Err` is returned. Should no `Err` occur, | |
912 | /// the sum of all elements is returned. | |
913 | /// | |
914 | /// # Examples | |
915 | /// | |
916 | /// This sums up every integer in a vector, rejecting the sum if a negative | |
917 | /// element is encountered: | |
918 | /// | |
919 | /// ``` | |
920 | /// let v = vec![1, 2]; | |
921 | /// let res: Result<i32, &'static str> = v.iter().map(|&x: &i32| | |
922 | /// if x < 0 { Err("Negative element found") } | |
923 | /// else { Ok(x) } | |
924 | /// ).sum(); | |
925 | /// assert_eq!(res, Ok(3)); | |
926 | /// ``` | |
32a655c1 SL |
927 | fn sum<I>(iter: I) -> Result<T, E> |
928 | where I: Iterator<Item = Result<U, E>>, | |
929 | { | |
930 | ResultShunt::process(iter, |i| i.sum()) | |
931 | } | |
932 | } | |
933 | ||
934 | #[stable(feature = "iter_arith_traits_result", since="1.16.0")] | |
935 | impl<T, U, E> Product<Result<U, E>> for Result<T, E> | |
936 | where T: Product<U>, | |
937 | { | |
041b39d2 XL |
938 | /// Takes each element in the `Iterator`: if it is an `Err`, no further |
939 | /// elements are taken, and the `Err` is returned. Should no `Err` occur, | |
940 | /// the product of all elements is returned. | |
32a655c1 SL |
941 | fn product<I>(iter: I) -> Result<T, E> |
942 | where I: Iterator<Item = Result<U, E>>, | |
943 | { | |
944 | ResultShunt::process(iter, |i| i.product()) | |
945 | } | |
946 | } | |
947 | ||
9e0c209e SL |
948 | /// An iterator that always continues to yield `None` when exhausted. |
949 | /// | |
950 | /// Calling next on a fused iterator that has returned `None` once is guaranteed | |
041b39d2 | 951 | /// to return [`None`] again. This trait should be implemented by all iterators |
9e0c209e SL |
952 | /// that behave this way because it allows for some significant optimizations. |
953 | /// | |
954 | /// Note: In general, you should not use `FusedIterator` in generic bounds if | |
cc61c64b | 955 | /// you need a fused iterator. Instead, you should just call [`Iterator::fuse`] |
476ff2be | 956 | /// on the iterator. If the iterator is already fused, the additional [`Fuse`] |
9e0c209e | 957 | /// wrapper will be a no-op with no performance penalty. |
476ff2be SL |
958 | /// |
959 | /// [`None`]: ../../std/option/enum.Option.html#variant.None | |
cc61c64b | 960 | /// [`Iterator::fuse`]: ../../std/iter/trait.Iterator.html#method.fuse |
476ff2be | 961 | /// [`Fuse`]: ../../std/iter/struct.Fuse.html |
9e0c209e SL |
962 | #[unstable(feature = "fused", issue = "35602")] |
963 | pub trait FusedIterator: Iterator {} | |
964 | ||
965 | #[unstable(feature = "fused", issue = "35602")] | |
966 | impl<'a, I: FusedIterator + ?Sized> FusedIterator for &'a mut I {} | |
c30ab7b3 SL |
967 | |
968 | /// An iterator that reports an accurate length using size_hint. | |
969 | /// | |
970 | /// The iterator reports a size hint where it is either exact | |
476ff2be SL |
971 | /// (lower bound is equal to upper bound), or the upper bound is [`None`]. |
972 | /// The upper bound must only be [`None`] if the actual iterator length is | |
973 | /// larger than [`usize::MAX`]. | |
c30ab7b3 SL |
974 | /// |
975 | /// The iterator must produce exactly the number of elements it reported. | |
976 | /// | |
977 | /// # Safety | |
978 | /// | |
979 | /// This trait must only be implemented when the contract is upheld. | |
cc61c64b | 980 | /// Consumers of this trait must inspect [`.size_hint`]’s upper bound. |
476ff2be SL |
981 | /// |
982 | /// [`None`]: ../../std/option/enum.Option.html#variant.None | |
983 | /// [`usize::MAX`]: ../../std/usize/constant.MAX.html | |
cc61c64b | 984 | /// [`.size_hint`]: ../../std/iter/trait.Iterator.html#method.size_hint |
c30ab7b3 SL |
985 | #[unstable(feature = "trusted_len", issue = "37572")] |
986 | pub unsafe trait TrustedLen : Iterator {} | |
987 | ||
988 | #[unstable(feature = "trusted_len", issue = "37572")] | |
989 | unsafe impl<'a, I: TrustedLen + ?Sized> TrustedLen for &'a mut I {} |