]>
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. | |
10 | ||
11 | //! Composable external iteration. | |
12 | //! | |
13 | //! If you've found yourself with a collection of some kind, and needed to | |
14 | //! perform an operation on the elements of said collection, you'll quickly run | |
15 | //! into 'iterators'. Iterators are heavily used in idiomatic Rust code, so | |
16 | //! it's worth becoming familiar with them. | |
17 | //! | |
18 | //! Before explaining more, let's talk about how this module is structured: | |
19 | //! | |
20 | //! # Organization | |
21 | //! | |
22 | //! This module is largely organized by type: | |
23 | //! | |
24 | //! * [Traits] are the core portion: these traits define what kind of iterators | |
25 | //! exist and what you can do with them. The methods of these traits are worth | |
26 | //! putting some extra study time into. | |
27 | //! * [Functions] provide some helpful ways to create some basic iterators. | |
28 | //! * [Structs] are often the return types of the various methods on this | |
29 | //! module's traits. You'll usually want to look at the method that creates | |
30 | //! the `struct`, rather than the `struct` itself. For more detail about why, | |
31 | //! see '[Implementing Iterator](#implementing-iterator)'. | |
32 | //! | |
33 | //! [Traits]: #traits | |
34 | //! [Functions]: #functions | |
35 | //! [Structs]: #structs | |
36 | //! | |
37 | //! That's it! Let's dig into iterators. | |
38 | //! | |
39 | //! # Iterator | |
40 | //! | |
41 | //! The heart and soul of this module is the [`Iterator`] trait. The core of | |
42 | //! [`Iterator`] looks like this: | |
43 | //! | |
44 | //! ``` | |
45 | //! trait Iterator { | |
46 | //! type Item; | |
47 | //! fn next(&mut self) -> Option<Self::Item>; | |
48 | //! } | |
49 | //! ``` | |
50 | //! | |
cc61c64b XL |
51 | //! An iterator has a method, [`next`], which when called, returns an |
52 | //! [`Option`]`<Item>`. [`next`] will return `Some(Item)` as long as there | |
a7813a04 XL |
53 | //! are elements, and once they've all been exhausted, will return `None` to |
54 | //! indicate that iteration is finished. Individual iterators may choose to | |
cc61c64b | 55 | //! resume iteration, and so calling [`next`] again may or may not eventually |
a7813a04 XL |
56 | //! start returning `Some(Item)` again at some point. |
57 | //! | |
58 | //! [`Iterator`]'s full definition includes a number of other methods as well, | |
cc61c64b | 59 | //! but they are default methods, built on top of [`next`], and so you get |
a7813a04 XL |
60 | //! them for free. |
61 | //! | |
62 | //! Iterators are also composable, and it's common to chain them together to do | |
63 | //! more complex forms of processing. See the [Adapters](#adapters) section | |
64 | //! below for more details. | |
65 | //! | |
66 | //! [`Iterator`]: trait.Iterator.html | |
cc61c64b | 67 | //! [`next`]: trait.Iterator.html#tymethod.next |
a7813a04 XL |
68 | //! [`Option`]: ../../std/option/enum.Option.html |
69 | //! | |
70 | //! # The three forms of iteration | |
71 | //! | |
72 | //! There are three common methods which can create iterators from a collection: | |
73 | //! | |
74 | //! * `iter()`, which iterates over `&T`. | |
75 | //! * `iter_mut()`, which iterates over `&mut T`. | |
76 | //! * `into_iter()`, which iterates over `T`. | |
77 | //! | |
78 | //! Various things in the standard library may implement one or more of the | |
79 | //! three, where appropriate. | |
80 | //! | |
81 | //! # Implementing Iterator | |
82 | //! | |
83 | //! Creating an iterator of your own involves two steps: creating a `struct` to | |
84 | //! hold the iterator's state, and then `impl`ementing [`Iterator`] for that | |
85 | //! `struct`. This is why there are so many `struct`s in this module: there is | |
86 | //! one for each iterator and iterator adapter. | |
87 | //! | |
88 | //! Let's make an iterator named `Counter` which counts from `1` to `5`: | |
89 | //! | |
90 | //! ``` | |
91 | //! // First, the struct: | |
92 | //! | |
93 | //! /// An iterator which counts from one to five | |
94 | //! struct Counter { | |
95 | //! count: usize, | |
96 | //! } | |
97 | //! | |
98 | //! // we want our count to start at one, so let's add a new() method to help. | |
99 | //! // This isn't strictly necessary, but is convenient. Note that we start | |
100 | //! // `count` at zero, we'll see why in `next()`'s implementation below. | |
101 | //! impl Counter { | |
102 | //! fn new() -> Counter { | |
103 | //! Counter { count: 0 } | |
104 | //! } | |
105 | //! } | |
106 | //! | |
107 | //! // Then, we implement `Iterator` for our `Counter`: | |
108 | //! | |
109 | //! impl Iterator for Counter { | |
110 | //! // we will be counting with usize | |
111 | //! type Item = usize; | |
112 | //! | |
113 | //! // next() is the only required method | |
114 | //! fn next(&mut self) -> Option<usize> { | |
115 | //! // increment our count. This is why we started at zero. | |
116 | //! self.count += 1; | |
117 | //! | |
118 | //! // check to see if we've finished counting or not. | |
119 | //! if self.count < 6 { | |
120 | //! Some(self.count) | |
121 | //! } else { | |
122 | //! None | |
123 | //! } | |
124 | //! } | |
125 | //! } | |
126 | //! | |
127 | //! // And now we can use it! | |
128 | //! | |
129 | //! let mut counter = Counter::new(); | |
130 | //! | |
131 | //! let x = counter.next().unwrap(); | |
132 | //! println!("{}", x); | |
133 | //! | |
134 | //! let x = counter.next().unwrap(); | |
135 | //! println!("{}", x); | |
136 | //! | |
137 | //! let x = counter.next().unwrap(); | |
138 | //! println!("{}", x); | |
139 | //! | |
140 | //! let x = counter.next().unwrap(); | |
141 | //! println!("{}", x); | |
142 | //! | |
143 | //! let x = counter.next().unwrap(); | |
144 | //! println!("{}", x); | |
145 | //! ``` | |
146 | //! | |
147 | //! This will print `1` through `5`, each on their own line. | |
148 | //! | |
149 | //! Calling `next()` this way gets repetitive. Rust has a construct which can | |
150 | //! call `next()` on your iterator, until it reaches `None`. Let's go over that | |
151 | //! next. | |
152 | //! | |
153 | //! # for Loops and IntoIterator | |
154 | //! | |
155 | //! Rust's `for` loop syntax is actually sugar for iterators. Here's a basic | |
156 | //! example of `for`: | |
157 | //! | |
158 | //! ``` | |
159 | //! let values = vec![1, 2, 3, 4, 5]; | |
160 | //! | |
161 | //! for x in values { | |
162 | //! println!("{}", x); | |
163 | //! } | |
164 | //! ``` | |
165 | //! | |
166 | //! This will print the numbers one through five, each on their own line. But | |
167 | //! you'll notice something here: we never called anything on our vector to | |
168 | //! produce an iterator. What gives? | |
169 | //! | |
170 | //! There's a trait in the standard library for converting something into an | |
cc61c64b | 171 | //! iterator: [`IntoIterator`]. This trait has one method, [`into_iter`], |
a7813a04 XL |
172 | //! which converts the thing implementing [`IntoIterator`] into an iterator. |
173 | //! Let's take a look at that `for` loop again, and what the compiler converts | |
174 | //! it into: | |
175 | //! | |
176 | //! [`IntoIterator`]: trait.IntoIterator.html | |
cc61c64b | 177 | //! [`into_iter`]: trait.IntoIterator.html#tymethod.into_iter |
a7813a04 XL |
178 | //! |
179 | //! ``` | |
180 | //! let values = vec![1, 2, 3, 4, 5]; | |
181 | //! | |
182 | //! for x in values { | |
183 | //! println!("{}", x); | |
184 | //! } | |
185 | //! ``` | |
186 | //! | |
187 | //! Rust de-sugars this into: | |
188 | //! | |
189 | //! ``` | |
190 | //! let values = vec![1, 2, 3, 4, 5]; | |
191 | //! { | |
192 | //! let result = match IntoIterator::into_iter(values) { | |
193 | //! mut iter => loop { | |
7cac9316 | 194 | //! let next; |
a7813a04 | 195 | //! match iter.next() { |
7cac9316 | 196 | //! Some(val) => next = val, |
a7813a04 | 197 | //! None => break, |
7cac9316 XL |
198 | //! }; |
199 | //! let x = next; | |
200 | //! let () = { println!("{}", x); }; | |
a7813a04 XL |
201 | //! }, |
202 | //! }; | |
203 | //! result | |
204 | //! } | |
205 | //! ``` | |
206 | //! | |
207 | //! First, we call `into_iter()` on the value. Then, we match on the iterator | |
cc61c64b | 208 | //! that returns, calling [`next`] over and over until we see a `None`. At |
a7813a04 XL |
209 | //! that point, we `break` out of the loop, and we're done iterating. |
210 | //! | |
211 | //! There's one more subtle bit here: the standard library contains an | |
212 | //! interesting implementation of [`IntoIterator`]: | |
213 | //! | |
214 | //! ```ignore | |
215 | //! impl<I: Iterator> IntoIterator for I | |
216 | //! ``` | |
217 | //! | |
218 | //! In other words, all [`Iterator`]s implement [`IntoIterator`], by just | |
219 | //! returning themselves. This means two things: | |
220 | //! | |
221 | //! 1. If you're writing an [`Iterator`], you can use it with a `for` loop. | |
222 | //! 2. If you're creating a collection, implementing [`IntoIterator`] for it | |
223 | //! will allow your collection to be used with the `for` loop. | |
224 | //! | |
225 | //! # Adapters | |
226 | //! | |
227 | //! Functions which take an [`Iterator`] and return another [`Iterator`] are | |
228 | //! often called 'iterator adapters', as they're a form of the 'adapter | |
229 | //! pattern'. | |
230 | //! | |
cc61c64b | 231 | //! Common iterator adapters include [`map`], [`take`], and [`filter`]. |
a7813a04 XL |
232 | //! For more, see their documentation. |
233 | //! | |
cc61c64b XL |
234 | //! [`map`]: trait.Iterator.html#method.map |
235 | //! [`take`]: trait.Iterator.html#method.take | |
236 | //! [`filter`]: trait.Iterator.html#method.filter | |
a7813a04 XL |
237 | //! |
238 | //! # Laziness | |
239 | //! | |
240 | //! Iterators (and iterator [adapters](#adapters)) are *lazy*. This means that | |
241 | //! just creating an iterator doesn't _do_ a whole lot. Nothing really happens | |
cc61c64b XL |
242 | //! until you call [`next`]. This is sometimes a source of confusion when |
243 | //! creating an iterator solely for its side effects. For example, the [`map`] | |
a7813a04 XL |
244 | //! method calls a closure on each element it iterates over: |
245 | //! | |
246 | //! ``` | |
247 | //! # #![allow(unused_must_use)] | |
248 | //! let v = vec![1, 2, 3, 4, 5]; | |
249 | //! v.iter().map(|x| println!("{}", x)); | |
250 | //! ``` | |
251 | //! | |
252 | //! This will not print any values, as we only created an iterator, rather than | |
253 | //! using it. The compiler will warn us about this kind of behavior: | |
254 | //! | |
255 | //! ```text | |
256 | //! warning: unused result which must be used: iterator adaptors are lazy and | |
257 | //! do nothing unless consumed | |
258 | //! ``` | |
259 | //! | |
cc61c64b | 260 | //! The idiomatic way to write a [`map`] for its side effects is to use a |
a7813a04 XL |
261 | //! `for` loop instead: |
262 | //! | |
263 | //! ``` | |
264 | //! let v = vec![1, 2, 3, 4, 5]; | |
265 | //! | |
266 | //! for x in &v { | |
267 | //! println!("{}", x); | |
268 | //! } | |
269 | //! ``` | |
270 | //! | |
cc61c64b | 271 | //! [`map`]: trait.Iterator.html#method.map |
a7813a04 XL |
272 | //! |
273 | //! The two most common ways to evaluate an iterator are to use a `for` loop | |
cc61c64b | 274 | //! like this, or using the [`collect`] method to produce a new collection. |
a7813a04 | 275 | //! |
cc61c64b | 276 | //! [`collect`]: trait.Iterator.html#method.collect |
a7813a04 XL |
277 | //! |
278 | //! # Infinity | |
279 | //! | |
280 | //! Iterators do not have to be finite. As an example, an open-ended range is | |
281 | //! an infinite iterator: | |
282 | //! | |
283 | //! ``` | |
284 | //! let numbers = 0..; | |
285 | //! ``` | |
286 | //! | |
cc61c64b | 287 | //! It is common to use the [`take`] iterator adapter to turn an infinite |
a7813a04 XL |
288 | //! iterator into a finite one: |
289 | //! | |
290 | //! ``` | |
291 | //! let numbers = 0..; | |
292 | //! let five_numbers = numbers.take(5); | |
293 | //! | |
294 | //! for number in five_numbers { | |
295 | //! println!("{}", number); | |
296 | //! } | |
297 | //! ``` | |
298 | //! | |
299 | //! This will print the numbers `0` through `4`, each on their own line. | |
300 | //! | |
cc61c64b | 301 | //! [`take`]: trait.Iterator.html#method.take |
a7813a04 XL |
302 | |
303 | #![stable(feature = "rust1", since = "1.0.0")] | |
304 | ||
a7813a04 XL |
305 | use cmp; |
306 | use fmt; | |
3157f602 | 307 | use iter_private::TrustedRandomAccess; |
a7813a04 XL |
308 | use usize; |
309 | ||
310 | #[stable(feature = "rust1", since = "1.0.0")] | |
311 | pub use self::iterator::Iterator; | |
312 | ||
313 | #[unstable(feature = "step_trait", | |
314 | reason = "likely to be replaced by finer-grained traits", | |
7cac9316 | 315 | issue = "42168")] |
a7813a04 XL |
316 | pub use self::range::Step; |
317 | #[unstable(feature = "step_by", reason = "recent addition", | |
318 | issue = "27741")] | |
7cac9316 XL |
319 | #[rustc_deprecated(since = "1.19.0", |
320 | reason = "replaced by `iter::StepBy`")] | |
321 | #[allow(deprecated)] | |
322 | pub use self::range::StepBy as DeprecatedStepBy; | |
a7813a04 XL |
323 | |
324 | #[stable(feature = "rust1", since = "1.0.0")] | |
325 | pub use self::sources::{Repeat, repeat}; | |
326 | #[stable(feature = "iter_empty", since = "1.2.0")] | |
327 | pub use self::sources::{Empty, empty}; | |
328 | #[stable(feature = "iter_once", since = "1.2.0")] | |
329 | pub use self::sources::{Once, once}; | |
330 | ||
331 | #[stable(feature = "rust1", since = "1.0.0")] | |
3157f602 XL |
332 | pub use self::traits::{FromIterator, IntoIterator, DoubleEndedIterator, Extend}; |
333 | #[stable(feature = "rust1", since = "1.0.0")] | |
334 | pub use self::traits::{ExactSizeIterator, Sum, Product}; | |
9e0c209e SL |
335 | #[unstable(feature = "fused", issue = "35602")] |
336 | pub use self::traits::FusedIterator; | |
c30ab7b3 SL |
337 | #[unstable(feature = "trusted_len", issue = "37572")] |
338 | pub use self::traits::TrustedLen; | |
a7813a04 XL |
339 | |
340 | mod iterator; | |
341 | mod range; | |
342 | mod sources; | |
343 | mod traits; | |
344 | ||
8bb4bdeb | 345 | /// A double-ended iterator with the direction inverted. |
a7813a04 | 346 | /// |
cc61c64b | 347 | /// This `struct` is created by the [`rev`] method on [`Iterator`]. See its |
a7813a04 XL |
348 | /// documentation for more. |
349 | /// | |
cc61c64b | 350 | /// [`rev`]: trait.Iterator.html#method.rev |
a7813a04 XL |
351 | /// [`Iterator`]: trait.Iterator.html |
352 | #[derive(Clone, Debug)] | |
353 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
354 | #[stable(feature = "rust1", since = "1.0.0")] | |
355 | pub struct Rev<T> { | |
356 | iter: T | |
357 | } | |
358 | ||
359 | #[stable(feature = "rust1", since = "1.0.0")] | |
360 | impl<I> Iterator for Rev<I> where I: DoubleEndedIterator { | |
361 | type Item = <I as Iterator>::Item; | |
362 | ||
363 | #[inline] | |
364 | fn next(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next_back() } | |
365 | #[inline] | |
366 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } | |
cc61c64b XL |
367 | |
368 | fn find<P>(&mut self, predicate: P) -> Option<Self::Item> | |
369 | where P: FnMut(&Self::Item) -> bool | |
370 | { | |
371 | self.iter.rfind(predicate) | |
372 | } | |
a7813a04 XL |
373 | } |
374 | ||
375 | #[stable(feature = "rust1", since = "1.0.0")] | |
376 | impl<I> DoubleEndedIterator for Rev<I> where I: DoubleEndedIterator { | |
377 | #[inline] | |
378 | fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next() } | |
cc61c64b XL |
379 | |
380 | fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> | |
381 | where P: FnMut(&Self::Item) -> bool | |
382 | { | |
383 | self.iter.find(predicate) | |
384 | } | |
a7813a04 XL |
385 | } |
386 | ||
387 | #[stable(feature = "rust1", since = "1.0.0")] | |
388 | impl<I> ExactSizeIterator for Rev<I> | |
476ff2be SL |
389 | where I: ExactSizeIterator + DoubleEndedIterator |
390 | { | |
391 | fn len(&self) -> usize { | |
392 | self.iter.len() | |
393 | } | |
394 | ||
395 | fn is_empty(&self) -> bool { | |
396 | self.iter.is_empty() | |
397 | } | |
398 | } | |
a7813a04 | 399 | |
9e0c209e SL |
400 | #[unstable(feature = "fused", issue = "35602")] |
401 | impl<I> FusedIterator for Rev<I> | |
402 | where I: FusedIterator + DoubleEndedIterator {} | |
403 | ||
c30ab7b3 SL |
404 | #[unstable(feature = "trusted_len", issue = "37572")] |
405 | unsafe impl<I> TrustedLen for Rev<I> | |
406 | where I: TrustedLen + DoubleEndedIterator {} | |
407 | ||
a7813a04 XL |
408 | /// An iterator that clones the elements of an underlying iterator. |
409 | /// | |
cc61c64b | 410 | /// This `struct` is created by the [`cloned`] method on [`Iterator`]. See its |
a7813a04 XL |
411 | /// documentation for more. |
412 | /// | |
cc61c64b | 413 | /// [`cloned`]: trait.Iterator.html#method.cloned |
a7813a04 XL |
414 | /// [`Iterator`]: trait.Iterator.html |
415 | #[stable(feature = "iter_cloned", since = "1.1.0")] | |
416 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
417 | #[derive(Clone, Debug)] | |
418 | pub struct Cloned<I> { | |
419 | it: I, | |
420 | } | |
421 | ||
c30ab7b3 | 422 | #[stable(feature = "iter_cloned", since = "1.1.0")] |
a7813a04 XL |
423 | impl<'a, I, T: 'a> Iterator for Cloned<I> |
424 | where I: Iterator<Item=&'a T>, T: Clone | |
425 | { | |
426 | type Item = T; | |
427 | ||
428 | fn next(&mut self) -> Option<T> { | |
429 | self.it.next().cloned() | |
430 | } | |
431 | ||
432 | fn size_hint(&self) -> (usize, Option<usize>) { | |
433 | self.it.size_hint() | |
434 | } | |
c30ab7b3 SL |
435 | |
436 | fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc | |
437 | where F: FnMut(Acc, Self::Item) -> Acc, | |
438 | { | |
439 | self.it.fold(init, move |acc, elt| f(acc, elt.clone())) | |
440 | } | |
a7813a04 XL |
441 | } |
442 | ||
c30ab7b3 | 443 | #[stable(feature = "iter_cloned", since = "1.1.0")] |
a7813a04 XL |
444 | impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I> |
445 | where I: DoubleEndedIterator<Item=&'a T>, T: Clone | |
446 | { | |
447 | fn next_back(&mut self) -> Option<T> { | |
448 | self.it.next_back().cloned() | |
449 | } | |
450 | } | |
451 | ||
c30ab7b3 | 452 | #[stable(feature = "iter_cloned", since = "1.1.0")] |
a7813a04 XL |
453 | impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I> |
454 | where I: ExactSizeIterator<Item=&'a T>, T: Clone | |
476ff2be SL |
455 | { |
456 | fn len(&self) -> usize { | |
457 | self.it.len() | |
458 | } | |
459 | ||
460 | fn is_empty(&self) -> bool { | |
461 | self.it.is_empty() | |
462 | } | |
463 | } | |
a7813a04 | 464 | |
9e0c209e SL |
465 | #[unstable(feature = "fused", issue = "35602")] |
466 | impl<'a, I, T: 'a> FusedIterator for Cloned<I> | |
467 | where I: FusedIterator<Item=&'a T>, T: Clone | |
468 | {} | |
469 | ||
c30ab7b3 SL |
470 | #[doc(hidden)] |
471 | unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I> | |
472 | where I: TrustedRandomAccess<Item=&'a T>, T: Clone | |
473 | { | |
474 | unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item { | |
475 | self.it.get_unchecked(i).clone() | |
476 | } | |
477 | ||
478 | #[inline] | |
479 | fn may_have_side_effect() -> bool { true } | |
480 | } | |
481 | ||
482 | #[unstable(feature = "trusted_len", issue = "37572")] | |
483 | unsafe impl<'a, I, T: 'a> TrustedLen for Cloned<I> | |
484 | where I: TrustedLen<Item=&'a T>, | |
485 | T: Clone | |
486 | {} | |
487 | ||
a7813a04 XL |
488 | /// An iterator that repeats endlessly. |
489 | /// | |
cc61c64b | 490 | /// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its |
a7813a04 XL |
491 | /// documentation for more. |
492 | /// | |
cc61c64b | 493 | /// [`cycle`]: trait.Iterator.html#method.cycle |
a7813a04 XL |
494 | /// [`Iterator`]: trait.Iterator.html |
495 | #[derive(Clone, Debug)] | |
496 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
497 | #[stable(feature = "rust1", since = "1.0.0")] | |
498 | pub struct Cycle<I> { | |
499 | orig: I, | |
500 | iter: I, | |
501 | } | |
502 | ||
503 | #[stable(feature = "rust1", since = "1.0.0")] | |
504 | impl<I> Iterator for Cycle<I> where I: Clone + Iterator { | |
505 | type Item = <I as Iterator>::Item; | |
506 | ||
507 | #[inline] | |
508 | fn next(&mut self) -> Option<<I as Iterator>::Item> { | |
509 | match self.iter.next() { | |
510 | None => { self.iter = self.orig.clone(); self.iter.next() } | |
511 | y => y | |
512 | } | |
513 | } | |
514 | ||
515 | #[inline] | |
516 | fn size_hint(&self) -> (usize, Option<usize>) { | |
517 | // the cycle iterator is either empty or infinite | |
518 | match self.orig.size_hint() { | |
519 | sz @ (0, Some(0)) => sz, | |
520 | (0, _) => (0, None), | |
521 | _ => (usize::MAX, None) | |
522 | } | |
523 | } | |
524 | } | |
525 | ||
9e0c209e SL |
526 | #[unstable(feature = "fused", issue = "35602")] |
527 | impl<I> FusedIterator for Cycle<I> where I: Clone + Iterator {} | |
528 | ||
7cac9316 XL |
529 | /// An adapter for stepping iterators by a custom amount. |
530 | /// | |
531 | /// This `struct` is created by the [`step_by`] method on [`Iterator`]. See | |
532 | /// its documentation for more. | |
533 | /// | |
534 | /// [`step_by`]: trait.Iterator.html#method.step_by | |
535 | /// [`Iterator`]: trait.Iterator.html | |
536 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
537 | #[unstable(feature = "iterator_step_by", | |
538 | reason = "unstable replacement of Range::step_by", | |
539 | issue = "27741")] | |
540 | #[derive(Clone, Debug)] | |
541 | pub struct StepBy<I> { | |
542 | iter: I, | |
543 | step: usize, | |
544 | first_take: bool, | |
545 | } | |
546 | ||
547 | #[unstable(feature = "iterator_step_by", | |
548 | reason = "unstable replacement of Range::step_by", | |
549 | issue = "27741")] | |
550 | impl<I> Iterator for StepBy<I> where I: Iterator { | |
551 | type Item = I::Item; | |
552 | ||
553 | #[inline] | |
554 | fn next(&mut self) -> Option<Self::Item> { | |
555 | if self.first_take { | |
556 | self.first_take = false; | |
557 | self.iter.next() | |
558 | } else { | |
559 | self.iter.nth(self.step) | |
560 | } | |
561 | } | |
562 | ||
563 | #[inline] | |
564 | fn size_hint(&self) -> (usize, Option<usize>) { | |
565 | let inner_hint = self.iter.size_hint(); | |
566 | ||
567 | if self.first_take { | |
568 | let f = |n| if n == 0 { 0 } else { 1 + (n-1)/(self.step+1) }; | |
569 | (f(inner_hint.0), inner_hint.1.map(f)) | |
570 | } else { | |
571 | let f = |n| n / (self.step+1); | |
572 | (f(inner_hint.0), inner_hint.1.map(f)) | |
573 | } | |
574 | } | |
575 | } | |
576 | ||
577 | // StepBy can only make the iterator shorter, so the len will still fit. | |
578 | #[unstable(feature = "iterator_step_by", | |
579 | reason = "unstable replacement of Range::step_by", | |
580 | issue = "27741")] | |
581 | impl<I> ExactSizeIterator for StepBy<I> where I: ExactSizeIterator {} | |
582 | ||
a7813a04 XL |
583 | /// An iterator that strings two iterators together. |
584 | /// | |
cc61c64b | 585 | /// This `struct` is created by the [`chain`] method on [`Iterator`]. See its |
a7813a04 XL |
586 | /// documentation for more. |
587 | /// | |
cc61c64b | 588 | /// [`chain`]: trait.Iterator.html#method.chain |
a7813a04 XL |
589 | /// [`Iterator`]: trait.Iterator.html |
590 | #[derive(Clone, Debug)] | |
591 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
592 | #[stable(feature = "rust1", since = "1.0.0")] | |
593 | pub struct Chain<A, B> { | |
594 | a: A, | |
595 | b: B, | |
596 | state: ChainState, | |
597 | } | |
598 | ||
599 | // The iterator protocol specifies that iteration ends with the return value | |
600 | // `None` from `.next()` (or `.next_back()`) and it is unspecified what | |
601 | // further calls return. The chain adaptor must account for this since it uses | |
602 | // two subiterators. | |
603 | // | |
604 | // It uses three states: | |
605 | // | |
606 | // - Both: `a` and `b` are remaining | |
607 | // - Front: `a` remaining | |
608 | // - Back: `b` remaining | |
609 | // | |
610 | // The fourth state (neither iterator is remaining) only occurs after Chain has | |
611 | // returned None once, so we don't need to store this state. | |
612 | #[derive(Clone, Debug)] | |
613 | enum ChainState { | |
614 | // both front and back iterator are remaining | |
615 | Both, | |
616 | // only front is remaining | |
617 | Front, | |
618 | // only back is remaining | |
619 | Back, | |
620 | } | |
621 | ||
622 | #[stable(feature = "rust1", since = "1.0.0")] | |
623 | impl<A, B> Iterator for Chain<A, B> where | |
624 | A: Iterator, | |
625 | B: Iterator<Item = A::Item> | |
626 | { | |
627 | type Item = A::Item; | |
628 | ||
629 | #[inline] | |
630 | fn next(&mut self) -> Option<A::Item> { | |
631 | match self.state { | |
632 | ChainState::Both => match self.a.next() { | |
633 | elt @ Some(..) => elt, | |
634 | None => { | |
635 | self.state = ChainState::Back; | |
636 | self.b.next() | |
637 | } | |
638 | }, | |
639 | ChainState::Front => self.a.next(), | |
640 | ChainState::Back => self.b.next(), | |
641 | } | |
642 | } | |
643 | ||
644 | #[inline] | |
3157f602 | 645 | #[rustc_inherit_overflow_checks] |
a7813a04 XL |
646 | fn count(self) -> usize { |
647 | match self.state { | |
648 | ChainState::Both => self.a.count() + self.b.count(), | |
649 | ChainState::Front => self.a.count(), | |
650 | ChainState::Back => self.b.count(), | |
651 | } | |
652 | } | |
653 | ||
c30ab7b3 SL |
654 | fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc |
655 | where F: FnMut(Acc, Self::Item) -> Acc, | |
656 | { | |
657 | let mut accum = init; | |
658 | match self.state { | |
659 | ChainState::Both | ChainState::Front => { | |
660 | accum = self.a.fold(accum, &mut f); | |
661 | } | |
662 | _ => { } | |
663 | } | |
664 | match self.state { | |
665 | ChainState::Both | ChainState::Back => { | |
666 | accum = self.b.fold(accum, &mut f); | |
667 | } | |
668 | _ => { } | |
669 | } | |
670 | accum | |
671 | } | |
672 | ||
a7813a04 XL |
673 | #[inline] |
674 | fn nth(&mut self, mut n: usize) -> Option<A::Item> { | |
675 | match self.state { | |
676 | ChainState::Both | ChainState::Front => { | |
677 | for x in self.a.by_ref() { | |
678 | if n == 0 { | |
679 | return Some(x) | |
680 | } | |
681 | n -= 1; | |
682 | } | |
683 | if let ChainState::Both = self.state { | |
684 | self.state = ChainState::Back; | |
685 | } | |
686 | } | |
687 | ChainState::Back => {} | |
688 | } | |
689 | if let ChainState::Back = self.state { | |
690 | self.b.nth(n) | |
691 | } else { | |
692 | None | |
693 | } | |
694 | } | |
695 | ||
696 | #[inline] | |
697 | fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where | |
698 | P: FnMut(&Self::Item) -> bool, | |
699 | { | |
700 | match self.state { | |
701 | ChainState::Both => match self.a.find(&mut predicate) { | |
702 | None => { | |
703 | self.state = ChainState::Back; | |
704 | self.b.find(predicate) | |
705 | } | |
706 | v => v | |
707 | }, | |
708 | ChainState::Front => self.a.find(predicate), | |
709 | ChainState::Back => self.b.find(predicate), | |
710 | } | |
711 | } | |
712 | ||
713 | #[inline] | |
714 | fn last(self) -> Option<A::Item> { | |
715 | match self.state { | |
716 | ChainState::Both => { | |
717 | // Must exhaust a before b. | |
718 | let a_last = self.a.last(); | |
719 | let b_last = self.b.last(); | |
720 | b_last.or(a_last) | |
721 | }, | |
722 | ChainState::Front => self.a.last(), | |
723 | ChainState::Back => self.b.last() | |
724 | } | |
725 | } | |
726 | ||
727 | #[inline] | |
728 | fn size_hint(&self) -> (usize, Option<usize>) { | |
729 | let (a_lower, a_upper) = self.a.size_hint(); | |
730 | let (b_lower, b_upper) = self.b.size_hint(); | |
731 | ||
732 | let lower = a_lower.saturating_add(b_lower); | |
733 | ||
734 | let upper = match (a_upper, b_upper) { | |
735 | (Some(x), Some(y)) => x.checked_add(y), | |
736 | _ => None | |
737 | }; | |
738 | ||
739 | (lower, upper) | |
740 | } | |
741 | } | |
742 | ||
743 | #[stable(feature = "rust1", since = "1.0.0")] | |
744 | impl<A, B> DoubleEndedIterator for Chain<A, B> where | |
745 | A: DoubleEndedIterator, | |
746 | B: DoubleEndedIterator<Item=A::Item>, | |
747 | { | |
748 | #[inline] | |
749 | fn next_back(&mut self) -> Option<A::Item> { | |
750 | match self.state { | |
751 | ChainState::Both => match self.b.next_back() { | |
752 | elt @ Some(..) => elt, | |
753 | None => { | |
754 | self.state = ChainState::Front; | |
755 | self.a.next_back() | |
756 | } | |
757 | }, | |
758 | ChainState::Front => self.a.next_back(), | |
759 | ChainState::Back => self.b.next_back(), | |
760 | } | |
761 | } | |
762 | } | |
763 | ||
9e0c209e SL |
764 | // Note: *both* must be fused to handle double-ended iterators. |
765 | #[unstable(feature = "fused", issue = "35602")] | |
766 | impl<A, B> FusedIterator for Chain<A, B> | |
767 | where A: FusedIterator, | |
768 | B: FusedIterator<Item=A::Item>, | |
769 | {} | |
770 | ||
c30ab7b3 SL |
771 | #[unstable(feature = "trusted_len", issue = "37572")] |
772 | unsafe impl<A, B> TrustedLen for Chain<A, B> | |
773 | where A: TrustedLen, B: TrustedLen<Item=A::Item>, | |
774 | {} | |
775 | ||
a7813a04 XL |
776 | /// An iterator that iterates two other iterators simultaneously. |
777 | /// | |
cc61c64b | 778 | /// This `struct` is created by the [`zip`] method on [`Iterator`]. See its |
a7813a04 XL |
779 | /// documentation for more. |
780 | /// | |
cc61c64b | 781 | /// [`zip`]: trait.Iterator.html#method.zip |
a7813a04 XL |
782 | /// [`Iterator`]: trait.Iterator.html |
783 | #[derive(Clone, Debug)] | |
784 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
785 | #[stable(feature = "rust1", since = "1.0.0")] | |
786 | pub struct Zip<A, B> { | |
787 | a: A, | |
3157f602 | 788 | b: B, |
5bcae85e SL |
789 | // index and len are only used by the specialized version of zip |
790 | index: usize, | |
791 | len: usize, | |
a7813a04 XL |
792 | } |
793 | ||
794 | #[stable(feature = "rust1", since = "1.0.0")] | |
795 | impl<A, B> Iterator for Zip<A, B> where A: Iterator, B: Iterator | |
796 | { | |
797 | type Item = (A::Item, B::Item); | |
798 | ||
799 | #[inline] | |
3157f602 XL |
800 | fn next(&mut self) -> Option<Self::Item> { |
801 | ZipImpl::next(self) | |
a7813a04 XL |
802 | } |
803 | ||
804 | #[inline] | |
805 | fn size_hint(&self) -> (usize, Option<usize>) { | |
3157f602 | 806 | ZipImpl::size_hint(self) |
a7813a04 XL |
807 | } |
808 | } | |
809 | ||
810 | #[stable(feature = "rust1", since = "1.0.0")] | |
811 | impl<A, B> DoubleEndedIterator for Zip<A, B> where | |
812 | A: DoubleEndedIterator + ExactSizeIterator, | |
813 | B: DoubleEndedIterator + ExactSizeIterator, | |
814 | { | |
815 | #[inline] | |
816 | fn next_back(&mut self) -> Option<(A::Item, B::Item)> { | |
3157f602 XL |
817 | ZipImpl::next_back(self) |
818 | } | |
819 | } | |
820 | ||
821 | // Zip specialization trait | |
822 | #[doc(hidden)] | |
823 | trait ZipImpl<A, B> { | |
824 | type Item; | |
825 | fn new(a: A, b: B) -> Self; | |
826 | fn next(&mut self) -> Option<Self::Item>; | |
827 | fn size_hint(&self) -> (usize, Option<usize>); | |
828 | fn next_back(&mut self) -> Option<Self::Item> | |
829 | where A: DoubleEndedIterator + ExactSizeIterator, | |
830 | B: DoubleEndedIterator + ExactSizeIterator; | |
831 | } | |
832 | ||
3157f602 XL |
833 | // General Zip impl |
834 | #[doc(hidden)] | |
835 | impl<A, B> ZipImpl<A, B> for Zip<A, B> | |
836 | where A: Iterator, B: Iterator | |
837 | { | |
838 | type Item = (A::Item, B::Item); | |
839 | default fn new(a: A, b: B) -> Self { | |
840 | Zip { | |
841 | a: a, | |
842 | b: b, | |
5bcae85e SL |
843 | index: 0, // unused |
844 | len: 0, // unused | |
3157f602 XL |
845 | } |
846 | } | |
847 | ||
848 | #[inline] | |
849 | default fn next(&mut self) -> Option<(A::Item, B::Item)> { | |
850 | self.a.next().and_then(|x| { | |
851 | self.b.next().and_then(|y| { | |
852 | Some((x, y)) | |
853 | }) | |
854 | }) | |
855 | } | |
856 | ||
857 | #[inline] | |
858 | default fn next_back(&mut self) -> Option<(A::Item, B::Item)> | |
859 | where A: DoubleEndedIterator + ExactSizeIterator, | |
860 | B: DoubleEndedIterator + ExactSizeIterator | |
861 | { | |
a7813a04 XL |
862 | let a_sz = self.a.len(); |
863 | let b_sz = self.b.len(); | |
864 | if a_sz != b_sz { | |
865 | // Adjust a, b to equal length | |
866 | if a_sz > b_sz { | |
867 | for _ in 0..a_sz - b_sz { self.a.next_back(); } | |
868 | } else { | |
869 | for _ in 0..b_sz - a_sz { self.b.next_back(); } | |
870 | } | |
871 | } | |
872 | match (self.a.next_back(), self.b.next_back()) { | |
873 | (Some(x), Some(y)) => Some((x, y)), | |
874 | (None, None) => None, | |
875 | _ => unreachable!(), | |
876 | } | |
877 | } | |
3157f602 XL |
878 | |
879 | #[inline] | |
880 | default fn size_hint(&self) -> (usize, Option<usize>) { | |
881 | let (a_lower, a_upper) = self.a.size_hint(); | |
882 | let (b_lower, b_upper) = self.b.size_hint(); | |
883 | ||
884 | let lower = cmp::min(a_lower, b_lower); | |
885 | ||
886 | let upper = match (a_upper, b_upper) { | |
887 | (Some(x), Some(y)) => Some(cmp::min(x,y)), | |
888 | (Some(x), None) => Some(x), | |
889 | (None, Some(y)) => Some(y), | |
890 | (None, None) => None | |
891 | }; | |
892 | ||
893 | (lower, upper) | |
894 | } | |
895 | } | |
896 | ||
3157f602 XL |
897 | #[doc(hidden)] |
898 | impl<A, B> ZipImpl<A, B> for Zip<A, B> | |
899 | where A: TrustedRandomAccess, B: TrustedRandomAccess | |
900 | { | |
901 | fn new(a: A, b: B) -> Self { | |
902 | let len = cmp::min(a.len(), b.len()); | |
903 | Zip { | |
904 | a: a, | |
905 | b: b, | |
5bcae85e SL |
906 | index: 0, |
907 | len: len, | |
3157f602 XL |
908 | } |
909 | } | |
910 | ||
911 | #[inline] | |
912 | fn next(&mut self) -> Option<(A::Item, B::Item)> { | |
5bcae85e SL |
913 | if self.index < self.len { |
914 | let i = self.index; | |
915 | self.index += 1; | |
3157f602 XL |
916 | unsafe { |
917 | Some((self.a.get_unchecked(i), self.b.get_unchecked(i))) | |
918 | } | |
c30ab7b3 SL |
919 | } else if A::may_have_side_effect() && self.index < self.a.len() { |
920 | // match the base implementation's potential side effects | |
921 | unsafe { | |
922 | self.a.get_unchecked(self.index); | |
923 | } | |
924 | self.index += 1; | |
925 | None | |
3157f602 XL |
926 | } else { |
927 | None | |
928 | } | |
929 | } | |
930 | ||
931 | #[inline] | |
932 | fn size_hint(&self) -> (usize, Option<usize>) { | |
5bcae85e | 933 | let len = self.len - self.index; |
3157f602 XL |
934 | (len, Some(len)) |
935 | } | |
936 | ||
937 | #[inline] | |
938 | fn next_back(&mut self) -> Option<(A::Item, B::Item)> | |
939 | where A: DoubleEndedIterator + ExactSizeIterator, | |
940 | B: DoubleEndedIterator + ExactSizeIterator | |
941 | { | |
c30ab7b3 SL |
942 | // Adjust a, b to equal length |
943 | if A::may_have_side_effect() { | |
944 | let sz = self.a.len(); | |
945 | if sz > self.len { | |
946 | for _ in 0..sz - cmp::max(self.len, self.index) { | |
947 | self.a.next_back(); | |
948 | } | |
949 | } | |
950 | } | |
951 | if B::may_have_side_effect() { | |
952 | let sz = self.b.len(); | |
953 | if sz > self.len { | |
954 | for _ in 0..sz - self.len { | |
955 | self.b.next_back(); | |
956 | } | |
957 | } | |
958 | } | |
5bcae85e SL |
959 | if self.index < self.len { |
960 | self.len -= 1; | |
961 | let i = self.len; | |
3157f602 XL |
962 | unsafe { |
963 | Some((self.a.get_unchecked(i), self.b.get_unchecked(i))) | |
964 | } | |
965 | } else { | |
966 | None | |
967 | } | |
968 | } | |
a7813a04 XL |
969 | } |
970 | ||
971 | #[stable(feature = "rust1", since = "1.0.0")] | |
972 | impl<A, B> ExactSizeIterator for Zip<A, B> | |
973 | where A: ExactSizeIterator, B: ExactSizeIterator {} | |
974 | ||
3157f602 XL |
975 | #[doc(hidden)] |
976 | unsafe impl<A, B> TrustedRandomAccess for Zip<A, B> | |
977 | where A: TrustedRandomAccess, | |
978 | B: TrustedRandomAccess, | |
979 | { | |
980 | unsafe fn get_unchecked(&mut self, i: usize) -> (A::Item, B::Item) { | |
981 | (self.a.get_unchecked(i), self.b.get_unchecked(i)) | |
982 | } | |
983 | ||
c30ab7b3 SL |
984 | fn may_have_side_effect() -> bool { |
985 | A::may_have_side_effect() || B::may_have_side_effect() | |
986 | } | |
3157f602 XL |
987 | } |
988 | ||
9e0c209e SL |
989 | #[unstable(feature = "fused", issue = "35602")] |
990 | impl<A, B> FusedIterator for Zip<A, B> | |
991 | where A: FusedIterator, B: FusedIterator, {} | |
992 | ||
c30ab7b3 SL |
993 | #[unstable(feature = "trusted_len", issue = "37572")] |
994 | unsafe impl<A, B> TrustedLen for Zip<A, B> | |
995 | where A: TrustedLen, B: TrustedLen, | |
996 | {} | |
997 | ||
a7813a04 XL |
998 | /// An iterator that maps the values of `iter` with `f`. |
999 | /// | |
cc61c64b | 1000 | /// This `struct` is created by the [`map`] method on [`Iterator`]. See its |
a7813a04 XL |
1001 | /// documentation for more. |
1002 | /// | |
cc61c64b | 1003 | /// [`map`]: trait.Iterator.html#method.map |
a7813a04 XL |
1004 | /// [`Iterator`]: trait.Iterator.html |
1005 | /// | |
1006 | /// # Notes about side effects | |
1007 | /// | |
cc61c64b XL |
1008 | /// The [`map`] iterator implements [`DoubleEndedIterator`], meaning that |
1009 | /// you can also [`map`] backwards: | |
a7813a04 XL |
1010 | /// |
1011 | /// ```rust | |
476ff2be | 1012 | /// let v: Vec<i32> = vec![1, 2, 3].into_iter().map(|x| x + 1).rev().collect(); |
a7813a04 XL |
1013 | /// |
1014 | /// assert_eq!(v, [4, 3, 2]); | |
1015 | /// ``` | |
1016 | /// | |
1017 | /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html | |
1018 | /// | |
1019 | /// But if your closure has state, iterating backwards may act in a way you do | |
1020 | /// not expect. Let's go through an example. First, in the forward direction: | |
1021 | /// | |
1022 | /// ```rust | |
1023 | /// let mut c = 0; | |
1024 | /// | |
1025 | /// for pair in vec!['a', 'b', 'c'].into_iter() | |
1026 | /// .map(|letter| { c += 1; (letter, c) }) { | |
1027 | /// println!("{:?}", pair); | |
1028 | /// } | |
1029 | /// ``` | |
1030 | /// | |
1031 | /// This will print "('a', 1), ('b', 2), ('c', 3)". | |
1032 | /// | |
1033 | /// Now consider this twist where we add a call to `rev`. This version will | |
1034 | /// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed, | |
1035 | /// but the values of the counter still go in order. This is because `map()` is | |
1036 | /// still being called lazilly on each item, but we are popping items off the | |
1037 | /// back of the vector now, instead of shifting them from the front. | |
1038 | /// | |
1039 | /// ```rust | |
1040 | /// let mut c = 0; | |
1041 | /// | |
1042 | /// for pair in vec!['a', 'b', 'c'].into_iter() | |
1043 | /// .map(|letter| { c += 1; (letter, c) }) | |
1044 | /// .rev() { | |
1045 | /// println!("{:?}", pair); | |
1046 | /// } | |
1047 | /// ``` | |
1048 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
1049 | #[stable(feature = "rust1", since = "1.0.0")] | |
1050 | #[derive(Clone)] | |
1051 | pub struct Map<I, F> { | |
1052 | iter: I, | |
1053 | f: F, | |
1054 | } | |
1055 | ||
1056 | #[stable(feature = "core_impl_debug", since = "1.9.0")] | |
1057 | impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> { | |
1058 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1059 | f.debug_struct("Map") | |
1060 | .field("iter", &self.iter) | |
1061 | .finish() | |
1062 | } | |
1063 | } | |
1064 | ||
1065 | #[stable(feature = "rust1", since = "1.0.0")] | |
1066 | impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B { | |
1067 | type Item = B; | |
1068 | ||
1069 | #[inline] | |
1070 | fn next(&mut self) -> Option<B> { | |
1071 | self.iter.next().map(&mut self.f) | |
1072 | } | |
1073 | ||
1074 | #[inline] | |
1075 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1076 | self.iter.size_hint() | |
1077 | } | |
c30ab7b3 SL |
1078 | |
1079 | fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc | |
1080 | where G: FnMut(Acc, Self::Item) -> Acc, | |
1081 | { | |
1082 | let mut f = self.f; | |
1083 | self.iter.fold(init, move |acc, elt| g(acc, f(elt))) | |
1084 | } | |
a7813a04 XL |
1085 | } |
1086 | ||
1087 | #[stable(feature = "rust1", since = "1.0.0")] | |
1088 | impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where | |
1089 | F: FnMut(I::Item) -> B, | |
1090 | { | |
1091 | #[inline] | |
1092 | fn next_back(&mut self) -> Option<B> { | |
1093 | self.iter.next_back().map(&mut self.f) | |
1094 | } | |
1095 | } | |
1096 | ||
1097 | #[stable(feature = "rust1", since = "1.0.0")] | |
1098 | impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F> | |
476ff2be SL |
1099 | where F: FnMut(I::Item) -> B |
1100 | { | |
1101 | fn len(&self) -> usize { | |
1102 | self.iter.len() | |
1103 | } | |
1104 | ||
1105 | fn is_empty(&self) -> bool { | |
1106 | self.iter.is_empty() | |
1107 | } | |
1108 | } | |
a7813a04 | 1109 | |
9e0c209e SL |
1110 | #[unstable(feature = "fused", issue = "35602")] |
1111 | impl<B, I: FusedIterator, F> FusedIterator for Map<I, F> | |
1112 | where F: FnMut(I::Item) -> B {} | |
1113 | ||
c30ab7b3 SL |
1114 | #[unstable(feature = "trusted_len", issue = "37572")] |
1115 | unsafe impl<B, I, F> TrustedLen for Map<I, F> | |
1116 | where I: TrustedLen, | |
1117 | F: FnMut(I::Item) -> B {} | |
1118 | ||
1119 | #[doc(hidden)] | |
1120 | unsafe impl<B, I, F> TrustedRandomAccess for Map<I, F> | |
1121 | where I: TrustedRandomAccess, | |
1122 | F: FnMut(I::Item) -> B, | |
1123 | { | |
1124 | unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item { | |
1125 | (self.f)(self.iter.get_unchecked(i)) | |
1126 | } | |
1127 | #[inline] | |
1128 | fn may_have_side_effect() -> bool { true } | |
1129 | } | |
1130 | ||
a7813a04 XL |
1131 | /// An iterator that filters the elements of `iter` with `predicate`. |
1132 | /// | |
cc61c64b | 1133 | /// This `struct` is created by the [`filter`] method on [`Iterator`]. See its |
a7813a04 XL |
1134 | /// documentation for more. |
1135 | /// | |
cc61c64b | 1136 | /// [`filter`]: trait.Iterator.html#method.filter |
a7813a04 XL |
1137 | /// [`Iterator`]: trait.Iterator.html |
1138 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
1139 | #[stable(feature = "rust1", since = "1.0.0")] | |
1140 | #[derive(Clone)] | |
1141 | pub struct Filter<I, P> { | |
1142 | iter: I, | |
1143 | predicate: P, | |
1144 | } | |
1145 | ||
1146 | #[stable(feature = "core_impl_debug", since = "1.9.0")] | |
1147 | impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> { | |
1148 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1149 | f.debug_struct("Filter") | |
1150 | .field("iter", &self.iter) | |
1151 | .finish() | |
1152 | } | |
1153 | } | |
1154 | ||
1155 | #[stable(feature = "rust1", since = "1.0.0")] | |
1156 | impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool { | |
1157 | type Item = I::Item; | |
1158 | ||
1159 | #[inline] | |
1160 | fn next(&mut self) -> Option<I::Item> { | |
8bb4bdeb | 1161 | for x in &mut self.iter { |
a7813a04 XL |
1162 | if (self.predicate)(&x) { |
1163 | return Some(x); | |
1164 | } | |
1165 | } | |
1166 | None | |
1167 | } | |
1168 | ||
1169 | #[inline] | |
1170 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1171 | let (_, upper) = self.iter.size_hint(); | |
1172 | (0, upper) // can't know a lower bound, due to the predicate | |
1173 | } | |
8bb4bdeb XL |
1174 | |
1175 | // this special case allows the compiler to make `.filter(_).count()` | |
1176 | // branchless. Barring perfect branch prediction (which is unattainable in | |
1177 | // the general case), this will be much faster in >90% of cases (containing | |
1178 | // virtually all real workloads) and only a tiny bit slower in the rest. | |
1179 | // | |
1180 | // Having this specialization thus allows us to write `.filter(p).count()` | |
1181 | // where we would otherwise write `.map(|x| p(x) as usize).sum()`, which is | |
1182 | // less readable and also less backwards-compatible to Rust before 1.10. | |
1183 | // | |
1184 | // Using the branchless version will also simplify the LLVM byte code, thus | |
1185 | // leaving more budget for LLVM optimizations. | |
1186 | #[inline] | |
1187 | fn count(mut self) -> usize { | |
1188 | let mut count = 0; | |
1189 | for x in &mut self.iter { | |
1190 | count += (self.predicate)(&x) as usize; | |
1191 | } | |
1192 | count | |
1193 | } | |
a7813a04 XL |
1194 | } |
1195 | ||
1196 | #[stable(feature = "rust1", since = "1.0.0")] | |
1197 | impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P> | |
1198 | where P: FnMut(&I::Item) -> bool, | |
1199 | { | |
1200 | #[inline] | |
1201 | fn next_back(&mut self) -> Option<I::Item> { | |
1202 | for x in self.iter.by_ref().rev() { | |
1203 | if (self.predicate)(&x) { | |
1204 | return Some(x); | |
1205 | } | |
1206 | } | |
1207 | None | |
1208 | } | |
1209 | } | |
1210 | ||
9e0c209e SL |
1211 | #[unstable(feature = "fused", issue = "35602")] |
1212 | impl<I: FusedIterator, P> FusedIterator for Filter<I, P> | |
1213 | where P: FnMut(&I::Item) -> bool {} | |
1214 | ||
a7813a04 XL |
1215 | /// An iterator that uses `f` to both filter and map elements from `iter`. |
1216 | /// | |
cc61c64b | 1217 | /// This `struct` is created by the [`filter_map`] method on [`Iterator`]. See its |
a7813a04 XL |
1218 | /// documentation for more. |
1219 | /// | |
cc61c64b | 1220 | /// [`filter_map`]: trait.Iterator.html#method.filter_map |
a7813a04 XL |
1221 | /// [`Iterator`]: trait.Iterator.html |
1222 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
1223 | #[stable(feature = "rust1", since = "1.0.0")] | |
1224 | #[derive(Clone)] | |
1225 | pub struct FilterMap<I, F> { | |
1226 | iter: I, | |
1227 | f: F, | |
1228 | } | |
1229 | ||
1230 | #[stable(feature = "core_impl_debug", since = "1.9.0")] | |
1231 | impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> { | |
1232 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1233 | f.debug_struct("FilterMap") | |
1234 | .field("iter", &self.iter) | |
1235 | .finish() | |
1236 | } | |
1237 | } | |
1238 | ||
1239 | #[stable(feature = "rust1", since = "1.0.0")] | |
1240 | impl<B, I: Iterator, F> Iterator for FilterMap<I, F> | |
1241 | where F: FnMut(I::Item) -> Option<B>, | |
1242 | { | |
1243 | type Item = B; | |
1244 | ||
1245 | #[inline] | |
1246 | fn next(&mut self) -> Option<B> { | |
1247 | for x in self.iter.by_ref() { | |
1248 | if let Some(y) = (self.f)(x) { | |
1249 | return Some(y); | |
1250 | } | |
1251 | } | |
1252 | None | |
1253 | } | |
1254 | ||
1255 | #[inline] | |
1256 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1257 | let (_, upper) = self.iter.size_hint(); | |
1258 | (0, upper) // can't know a lower bound, due to the predicate | |
1259 | } | |
1260 | } | |
1261 | ||
1262 | #[stable(feature = "rust1", since = "1.0.0")] | |
1263 | impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F> | |
1264 | where F: FnMut(I::Item) -> Option<B>, | |
1265 | { | |
1266 | #[inline] | |
1267 | fn next_back(&mut self) -> Option<B> { | |
1268 | for x in self.iter.by_ref().rev() { | |
1269 | if let Some(y) = (self.f)(x) { | |
1270 | return Some(y); | |
1271 | } | |
1272 | } | |
1273 | None | |
1274 | } | |
1275 | } | |
1276 | ||
9e0c209e SL |
1277 | #[unstable(feature = "fused", issue = "35602")] |
1278 | impl<B, I: FusedIterator, F> FusedIterator for FilterMap<I, F> | |
1279 | where F: FnMut(I::Item) -> Option<B> {} | |
1280 | ||
a7813a04 XL |
1281 | /// An iterator that yields the current count and the element during iteration. |
1282 | /// | |
cc61c64b | 1283 | /// This `struct` is created by the [`enumerate`] method on [`Iterator`]. See its |
a7813a04 XL |
1284 | /// documentation for more. |
1285 | /// | |
cc61c64b | 1286 | /// [`enumerate`]: trait.Iterator.html#method.enumerate |
a7813a04 XL |
1287 | /// [`Iterator`]: trait.Iterator.html |
1288 | #[derive(Clone, Debug)] | |
1289 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
1290 | #[stable(feature = "rust1", since = "1.0.0")] | |
1291 | pub struct Enumerate<I> { | |
1292 | iter: I, | |
1293 | count: usize, | |
1294 | } | |
1295 | ||
1296 | #[stable(feature = "rust1", since = "1.0.0")] | |
1297 | impl<I> Iterator for Enumerate<I> where I: Iterator { | |
1298 | type Item = (usize, <I as Iterator>::Item); | |
1299 | ||
1300 | /// # Overflow Behavior | |
1301 | /// | |
1302 | /// The method does no guarding against overflows, so enumerating more than | |
1303 | /// `usize::MAX` elements either produces the wrong result or panics. If | |
1304 | /// debug assertions are enabled, a panic is guaranteed. | |
1305 | /// | |
1306 | /// # Panics | |
1307 | /// | |
1308 | /// Might panic if the index of the element overflows a `usize`. | |
1309 | #[inline] | |
3157f602 | 1310 | #[rustc_inherit_overflow_checks] |
a7813a04 XL |
1311 | fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> { |
1312 | self.iter.next().map(|a| { | |
1313 | let ret = (self.count, a); | |
1314 | // Possible undefined overflow. | |
1315 | self.count += 1; | |
1316 | ret | |
1317 | }) | |
1318 | } | |
1319 | ||
1320 | #[inline] | |
1321 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1322 | self.iter.size_hint() | |
1323 | } | |
1324 | ||
1325 | #[inline] | |
3157f602 | 1326 | #[rustc_inherit_overflow_checks] |
a7813a04 XL |
1327 | fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> { |
1328 | self.iter.nth(n).map(|a| { | |
1329 | let i = self.count + n; | |
1330 | self.count = i + 1; | |
1331 | (i, a) | |
1332 | }) | |
1333 | } | |
1334 | ||
1335 | #[inline] | |
1336 | fn count(self) -> usize { | |
1337 | self.iter.count() | |
1338 | } | |
1339 | } | |
1340 | ||
1341 | #[stable(feature = "rust1", since = "1.0.0")] | |
1342 | impl<I> DoubleEndedIterator for Enumerate<I> where | |
1343 | I: ExactSizeIterator + DoubleEndedIterator | |
1344 | { | |
1345 | #[inline] | |
1346 | fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> { | |
1347 | self.iter.next_back().map(|a| { | |
1348 | let len = self.iter.len(); | |
1349 | // Can safely add, `ExactSizeIterator` promises that the number of | |
1350 | // elements fits into a `usize`. | |
1351 | (self.count + len, a) | |
1352 | }) | |
1353 | } | |
1354 | } | |
1355 | ||
1356 | #[stable(feature = "rust1", since = "1.0.0")] | |
476ff2be SL |
1357 | impl<I> ExactSizeIterator for Enumerate<I> where I: ExactSizeIterator { |
1358 | fn len(&self) -> usize { | |
1359 | self.iter.len() | |
1360 | } | |
1361 | ||
1362 | fn is_empty(&self) -> bool { | |
1363 | self.iter.is_empty() | |
1364 | } | |
1365 | } | |
a7813a04 | 1366 | |
3157f602 XL |
1367 | #[doc(hidden)] |
1368 | unsafe impl<I> TrustedRandomAccess for Enumerate<I> | |
1369 | where I: TrustedRandomAccess | |
1370 | { | |
1371 | unsafe fn get_unchecked(&mut self, i: usize) -> (usize, I::Item) { | |
1372 | (self.count + i, self.iter.get_unchecked(i)) | |
1373 | } | |
c30ab7b3 SL |
1374 | |
1375 | fn may_have_side_effect() -> bool { | |
1376 | I::may_have_side_effect() | |
1377 | } | |
3157f602 XL |
1378 | } |
1379 | ||
9e0c209e SL |
1380 | #[unstable(feature = "fused", issue = "35602")] |
1381 | impl<I> FusedIterator for Enumerate<I> where I: FusedIterator {} | |
1382 | ||
c30ab7b3 SL |
1383 | #[unstable(feature = "trusted_len", issue = "37572")] |
1384 | unsafe impl<I> TrustedLen for Enumerate<I> | |
1385 | where I: TrustedLen, | |
1386 | {} | |
1387 | ||
1388 | ||
a7813a04 XL |
1389 | /// An iterator with a `peek()` that returns an optional reference to the next |
1390 | /// element. | |
1391 | /// | |
cc61c64b | 1392 | /// This `struct` is created by the [`peekable`] method on [`Iterator`]. See its |
a7813a04 XL |
1393 | /// documentation for more. |
1394 | /// | |
cc61c64b | 1395 | /// [`peekable`]: trait.Iterator.html#method.peekable |
a7813a04 XL |
1396 | /// [`Iterator`]: trait.Iterator.html |
1397 | #[derive(Clone, Debug)] | |
1398 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
1399 | #[stable(feature = "rust1", since = "1.0.0")] | |
1400 | pub struct Peekable<I: Iterator> { | |
1401 | iter: I, | |
476ff2be SL |
1402 | /// Remember a peeked value, even if it was None. |
1403 | peeked: Option<Option<I::Item>>, | |
a7813a04 XL |
1404 | } |
1405 | ||
476ff2be SL |
1406 | // Peekable must remember if a None has been seen in the `.peek()` method. |
1407 | // It ensures that `.peek(); .peek();` or `.peek(); .next();` only advances the | |
1408 | // underlying iterator at most once. This does not by itself make the iterator | |
1409 | // fused. | |
a7813a04 XL |
1410 | #[stable(feature = "rust1", since = "1.0.0")] |
1411 | impl<I: Iterator> Iterator for Peekable<I> { | |
1412 | type Item = I::Item; | |
1413 | ||
1414 | #[inline] | |
1415 | fn next(&mut self) -> Option<I::Item> { | |
476ff2be SL |
1416 | match self.peeked.take() { |
1417 | Some(v) => v, | |
a7813a04 XL |
1418 | None => self.iter.next(), |
1419 | } | |
1420 | } | |
1421 | ||
1422 | #[inline] | |
3157f602 | 1423 | #[rustc_inherit_overflow_checks] |
476ff2be SL |
1424 | fn count(mut self) -> usize { |
1425 | match self.peeked.take() { | |
1426 | Some(None) => 0, | |
1427 | Some(Some(_)) => 1 + self.iter.count(), | |
1428 | None => self.iter.count(), | |
1429 | } | |
a7813a04 XL |
1430 | } |
1431 | ||
1432 | #[inline] | |
1433 | fn nth(&mut self, n: usize) -> Option<I::Item> { | |
476ff2be SL |
1434 | match self.peeked.take() { |
1435 | // the .take() below is just to avoid "move into pattern guard" | |
1436 | Some(ref mut v) if n == 0 => v.take(), | |
1437 | Some(None) => None, | |
1438 | Some(Some(_)) => self.iter.nth(n - 1), | |
1439 | None => self.iter.nth(n), | |
a7813a04 XL |
1440 | } |
1441 | } | |
1442 | ||
1443 | #[inline] | |
476ff2be SL |
1444 | fn last(mut self) -> Option<I::Item> { |
1445 | let peek_opt = match self.peeked.take() { | |
1446 | Some(None) => return None, | |
1447 | Some(v) => v, | |
1448 | None => None, | |
1449 | }; | |
1450 | self.iter.last().or(peek_opt) | |
a7813a04 XL |
1451 | } |
1452 | ||
1453 | #[inline] | |
1454 | fn size_hint(&self) -> (usize, Option<usize>) { | |
476ff2be SL |
1455 | let peek_len = match self.peeked { |
1456 | Some(None) => return (0, Some(0)), | |
1457 | Some(Some(_)) => 1, | |
1458 | None => 0, | |
1459 | }; | |
a7813a04 | 1460 | let (lo, hi) = self.iter.size_hint(); |
476ff2be SL |
1461 | let lo = lo.saturating_add(peek_len); |
1462 | let hi = hi.and_then(|x| x.checked_add(peek_len)); | |
1463 | (lo, hi) | |
a7813a04 XL |
1464 | } |
1465 | } | |
1466 | ||
1467 | #[stable(feature = "rust1", since = "1.0.0")] | |
1468 | impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {} | |
1469 | ||
9e0c209e SL |
1470 | #[unstable(feature = "fused", issue = "35602")] |
1471 | impl<I: FusedIterator> FusedIterator for Peekable<I> {} | |
1472 | ||
a7813a04 XL |
1473 | impl<I: Iterator> Peekable<I> { |
1474 | /// Returns a reference to the next() value without advancing the iterator. | |
1475 | /// | |
cc61c64b | 1476 | /// Like [`next`], if there is a value, it is wrapped in a `Some(T)`. |
5bcae85e | 1477 | /// But if the iteration is over, `None` is returned. |
a7813a04 | 1478 | /// |
cc61c64b | 1479 | /// [`next`]: trait.Iterator.html#tymethod.next |
a7813a04 | 1480 | /// |
5bcae85e SL |
1481 | /// Because `peek()` returns a reference, and many iterators iterate over |
1482 | /// references, there can be a possibly confusing situation where the | |
a7813a04 | 1483 | /// return value is a double reference. You can see this effect in the |
5bcae85e | 1484 | /// examples below. |
a7813a04 XL |
1485 | /// |
1486 | /// # Examples | |
1487 | /// | |
1488 | /// Basic usage: | |
1489 | /// | |
1490 | /// ``` | |
1491 | /// let xs = [1, 2, 3]; | |
1492 | /// | |
1493 | /// let mut iter = xs.iter().peekable(); | |
1494 | /// | |
1495 | /// // peek() lets us see into the future | |
1496 | /// assert_eq!(iter.peek(), Some(&&1)); | |
1497 | /// assert_eq!(iter.next(), Some(&1)); | |
1498 | /// | |
1499 | /// assert_eq!(iter.next(), Some(&2)); | |
1500 | /// | |
5bcae85e | 1501 | /// // The iterator does not advance even if we `peek` multiple times |
a7813a04 XL |
1502 | /// assert_eq!(iter.peek(), Some(&&3)); |
1503 | /// assert_eq!(iter.peek(), Some(&&3)); | |
1504 | /// | |
1505 | /// assert_eq!(iter.next(), Some(&3)); | |
1506 | /// | |
5bcae85e | 1507 | /// // After the iterator is finished, so is `peek()` |
a7813a04 XL |
1508 | /// assert_eq!(iter.peek(), None); |
1509 | /// assert_eq!(iter.next(), None); | |
1510 | /// ``` | |
1511 | #[inline] | |
1512 | #[stable(feature = "rust1", since = "1.0.0")] | |
1513 | pub fn peek(&mut self) -> Option<&I::Item> { | |
1514 | if self.peeked.is_none() { | |
476ff2be SL |
1515 | self.peeked = Some(self.iter.next()); |
1516 | } | |
1517 | match self.peeked { | |
1518 | Some(Some(ref value)) => Some(value), | |
1519 | Some(None) => None, | |
1520 | _ => unreachable!(), | |
a7813a04 | 1521 | } |
a7813a04 | 1522 | } |
a7813a04 XL |
1523 | } |
1524 | ||
1525 | /// An iterator that rejects elements while `predicate` is true. | |
1526 | /// | |
cc61c64b | 1527 | /// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its |
a7813a04 XL |
1528 | /// documentation for more. |
1529 | /// | |
cc61c64b | 1530 | /// [`skip_while`]: trait.Iterator.html#method.skip_while |
a7813a04 XL |
1531 | /// [`Iterator`]: trait.Iterator.html |
1532 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
1533 | #[stable(feature = "rust1", since = "1.0.0")] | |
1534 | #[derive(Clone)] | |
1535 | pub struct SkipWhile<I, P> { | |
1536 | iter: I, | |
1537 | flag: bool, | |
1538 | predicate: P, | |
1539 | } | |
1540 | ||
1541 | #[stable(feature = "core_impl_debug", since = "1.9.0")] | |
1542 | impl<I: fmt::Debug, P> fmt::Debug for SkipWhile<I, P> { | |
1543 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1544 | f.debug_struct("SkipWhile") | |
1545 | .field("iter", &self.iter) | |
1546 | .field("flag", &self.flag) | |
1547 | .finish() | |
1548 | } | |
1549 | } | |
1550 | ||
1551 | #[stable(feature = "rust1", since = "1.0.0")] | |
1552 | impl<I: Iterator, P> Iterator for SkipWhile<I, P> | |
1553 | where P: FnMut(&I::Item) -> bool | |
1554 | { | |
1555 | type Item = I::Item; | |
1556 | ||
1557 | #[inline] | |
1558 | fn next(&mut self) -> Option<I::Item> { | |
1559 | for x in self.iter.by_ref() { | |
1560 | if self.flag || !(self.predicate)(&x) { | |
1561 | self.flag = true; | |
1562 | return Some(x); | |
1563 | } | |
1564 | } | |
1565 | None | |
1566 | } | |
1567 | ||
1568 | #[inline] | |
1569 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1570 | let (_, upper) = self.iter.size_hint(); | |
1571 | (0, upper) // can't know a lower bound, due to the predicate | |
1572 | } | |
1573 | } | |
1574 | ||
9e0c209e SL |
1575 | #[unstable(feature = "fused", issue = "35602")] |
1576 | impl<I, P> FusedIterator for SkipWhile<I, P> | |
1577 | where I: FusedIterator, P: FnMut(&I::Item) -> bool {} | |
1578 | ||
a7813a04 XL |
1579 | /// An iterator that only accepts elements while `predicate` is true. |
1580 | /// | |
cc61c64b | 1581 | /// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its |
a7813a04 XL |
1582 | /// documentation for more. |
1583 | /// | |
cc61c64b | 1584 | /// [`take_while`]: trait.Iterator.html#method.take_while |
a7813a04 XL |
1585 | /// [`Iterator`]: trait.Iterator.html |
1586 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
1587 | #[stable(feature = "rust1", since = "1.0.0")] | |
1588 | #[derive(Clone)] | |
1589 | pub struct TakeWhile<I, P> { | |
1590 | iter: I, | |
1591 | flag: bool, | |
1592 | predicate: P, | |
1593 | } | |
1594 | ||
1595 | #[stable(feature = "core_impl_debug", since = "1.9.0")] | |
1596 | impl<I: fmt::Debug, P> fmt::Debug for TakeWhile<I, P> { | |
1597 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1598 | f.debug_struct("TakeWhile") | |
1599 | .field("iter", &self.iter) | |
1600 | .field("flag", &self.flag) | |
1601 | .finish() | |
1602 | } | |
1603 | } | |
1604 | ||
1605 | #[stable(feature = "rust1", since = "1.0.0")] | |
1606 | impl<I: Iterator, P> Iterator for TakeWhile<I, P> | |
1607 | where P: FnMut(&I::Item) -> bool | |
1608 | { | |
1609 | type Item = I::Item; | |
1610 | ||
1611 | #[inline] | |
1612 | fn next(&mut self) -> Option<I::Item> { | |
1613 | if self.flag { | |
1614 | None | |
1615 | } else { | |
1616 | self.iter.next().and_then(|x| { | |
1617 | if (self.predicate)(&x) { | |
1618 | Some(x) | |
1619 | } else { | |
1620 | self.flag = true; | |
1621 | None | |
1622 | } | |
1623 | }) | |
1624 | } | |
1625 | } | |
1626 | ||
1627 | #[inline] | |
1628 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1629 | let (_, upper) = self.iter.size_hint(); | |
1630 | (0, upper) // can't know a lower bound, due to the predicate | |
1631 | } | |
1632 | } | |
1633 | ||
9e0c209e SL |
1634 | #[unstable(feature = "fused", issue = "35602")] |
1635 | impl<I, P> FusedIterator for TakeWhile<I, P> | |
1636 | where I: FusedIterator, P: FnMut(&I::Item) -> bool {} | |
1637 | ||
a7813a04 XL |
1638 | /// An iterator that skips over `n` elements of `iter`. |
1639 | /// | |
cc61c64b | 1640 | /// This `struct` is created by the [`skip`] method on [`Iterator`]. See its |
a7813a04 XL |
1641 | /// documentation for more. |
1642 | /// | |
cc61c64b | 1643 | /// [`skip`]: trait.Iterator.html#method.skip |
a7813a04 XL |
1644 | /// [`Iterator`]: trait.Iterator.html |
1645 | #[derive(Clone, Debug)] | |
1646 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
1647 | #[stable(feature = "rust1", since = "1.0.0")] | |
1648 | pub struct Skip<I> { | |
1649 | iter: I, | |
1650 | n: usize | |
1651 | } | |
1652 | ||
1653 | #[stable(feature = "rust1", since = "1.0.0")] | |
1654 | impl<I> Iterator for Skip<I> where I: Iterator { | |
1655 | type Item = <I as Iterator>::Item; | |
1656 | ||
1657 | #[inline] | |
1658 | fn next(&mut self) -> Option<I::Item> { | |
1659 | if self.n == 0 { | |
1660 | self.iter.next() | |
1661 | } else { | |
1662 | let old_n = self.n; | |
1663 | self.n = 0; | |
1664 | self.iter.nth(old_n) | |
1665 | } | |
1666 | } | |
1667 | ||
1668 | #[inline] | |
1669 | fn nth(&mut self, n: usize) -> Option<I::Item> { | |
1670 | // Can't just add n + self.n due to overflow. | |
1671 | if self.n == 0 { | |
1672 | self.iter.nth(n) | |
1673 | } else { | |
1674 | let to_skip = self.n; | |
1675 | self.n = 0; | |
1676 | // nth(n) skips n+1 | |
1677 | if self.iter.nth(to_skip-1).is_none() { | |
1678 | return None; | |
1679 | } | |
1680 | self.iter.nth(n) | |
1681 | } | |
1682 | } | |
1683 | ||
1684 | #[inline] | |
1685 | fn count(self) -> usize { | |
1686 | self.iter.count().saturating_sub(self.n) | |
1687 | } | |
1688 | ||
1689 | #[inline] | |
1690 | fn last(mut self) -> Option<I::Item> { | |
1691 | if self.n == 0 { | |
1692 | self.iter.last() | |
1693 | } else { | |
1694 | let next = self.next(); | |
1695 | if next.is_some() { | |
1696 | // recurse. n should be 0. | |
1697 | self.last().or(next) | |
1698 | } else { | |
1699 | None | |
1700 | } | |
1701 | } | |
1702 | } | |
1703 | ||
1704 | #[inline] | |
1705 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1706 | let (lower, upper) = self.iter.size_hint(); | |
1707 | ||
1708 | let lower = lower.saturating_sub(self.n); | |
1709 | let upper = upper.map(|x| x.saturating_sub(self.n)); | |
1710 | ||
1711 | (lower, upper) | |
1712 | } | |
1713 | } | |
1714 | ||
1715 | #[stable(feature = "rust1", since = "1.0.0")] | |
1716 | impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {} | |
1717 | ||
7cac9316 | 1718 | #[stable(feature = "double_ended_skip_iterator", since = "1.9.0")] |
a7813a04 XL |
1719 | impl<I> DoubleEndedIterator for Skip<I> where I: DoubleEndedIterator + ExactSizeIterator { |
1720 | fn next_back(&mut self) -> Option<Self::Item> { | |
1721 | if self.len() > 0 { | |
1722 | self.iter.next_back() | |
1723 | } else { | |
1724 | None | |
1725 | } | |
1726 | } | |
1727 | } | |
1728 | ||
9e0c209e SL |
1729 | #[unstable(feature = "fused", issue = "35602")] |
1730 | impl<I> FusedIterator for Skip<I> where I: FusedIterator {} | |
1731 | ||
a7813a04 XL |
1732 | /// An iterator that only iterates over the first `n` iterations of `iter`. |
1733 | /// | |
cc61c64b | 1734 | /// This `struct` is created by the [`take`] method on [`Iterator`]. See its |
a7813a04 XL |
1735 | /// documentation for more. |
1736 | /// | |
cc61c64b | 1737 | /// [`take`]: trait.Iterator.html#method.take |
a7813a04 XL |
1738 | /// [`Iterator`]: trait.Iterator.html |
1739 | #[derive(Clone, Debug)] | |
1740 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
1741 | #[stable(feature = "rust1", since = "1.0.0")] | |
1742 | pub struct Take<I> { | |
1743 | iter: I, | |
1744 | n: usize | |
1745 | } | |
1746 | ||
1747 | #[stable(feature = "rust1", since = "1.0.0")] | |
1748 | impl<I> Iterator for Take<I> where I: Iterator{ | |
1749 | type Item = <I as Iterator>::Item; | |
1750 | ||
1751 | #[inline] | |
1752 | fn next(&mut self) -> Option<<I as Iterator>::Item> { | |
1753 | if self.n != 0 { | |
1754 | self.n -= 1; | |
1755 | self.iter.next() | |
1756 | } else { | |
1757 | None | |
1758 | } | |
1759 | } | |
1760 | ||
1761 | #[inline] | |
1762 | fn nth(&mut self, n: usize) -> Option<I::Item> { | |
1763 | if self.n > n { | |
1764 | self.n -= n + 1; | |
1765 | self.iter.nth(n) | |
1766 | } else { | |
1767 | if self.n > 0 { | |
1768 | self.iter.nth(self.n - 1); | |
1769 | self.n = 0; | |
1770 | } | |
1771 | None | |
1772 | } | |
1773 | } | |
1774 | ||
1775 | #[inline] | |
1776 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1777 | let (lower, upper) = self.iter.size_hint(); | |
1778 | ||
1779 | let lower = cmp::min(lower, self.n); | |
1780 | ||
1781 | let upper = match upper { | |
1782 | Some(x) if x < self.n => Some(x), | |
1783 | _ => Some(self.n) | |
1784 | }; | |
1785 | ||
1786 | (lower, upper) | |
1787 | } | |
1788 | } | |
1789 | ||
1790 | #[stable(feature = "rust1", since = "1.0.0")] | |
1791 | impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {} | |
1792 | ||
9e0c209e SL |
1793 | #[unstable(feature = "fused", issue = "35602")] |
1794 | impl<I> FusedIterator for Take<I> where I: FusedIterator {} | |
a7813a04 XL |
1795 | |
1796 | /// An iterator to maintain state while iterating another iterator. | |
1797 | /// | |
cc61c64b | 1798 | /// This `struct` is created by the [`scan`] method on [`Iterator`]. See its |
a7813a04 XL |
1799 | /// documentation for more. |
1800 | /// | |
cc61c64b | 1801 | /// [`scan`]: trait.Iterator.html#method.scan |
a7813a04 XL |
1802 | /// [`Iterator`]: trait.Iterator.html |
1803 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
1804 | #[stable(feature = "rust1", since = "1.0.0")] | |
1805 | #[derive(Clone)] | |
1806 | pub struct Scan<I, St, F> { | |
1807 | iter: I, | |
1808 | f: F, | |
1809 | state: St, | |
1810 | } | |
1811 | ||
1812 | #[stable(feature = "core_impl_debug", since = "1.9.0")] | |
1813 | impl<I: fmt::Debug, St: fmt::Debug, F> fmt::Debug for Scan<I, St, F> { | |
1814 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1815 | f.debug_struct("Scan") | |
1816 | .field("iter", &self.iter) | |
1817 | .field("state", &self.state) | |
1818 | .finish() | |
1819 | } | |
1820 | } | |
1821 | ||
1822 | #[stable(feature = "rust1", since = "1.0.0")] | |
1823 | impl<B, I, St, F> Iterator for Scan<I, St, F> where | |
1824 | I: Iterator, | |
1825 | F: FnMut(&mut St, I::Item) -> Option<B>, | |
1826 | { | |
1827 | type Item = B; | |
1828 | ||
1829 | #[inline] | |
1830 | fn next(&mut self) -> Option<B> { | |
1831 | self.iter.next().and_then(|a| (self.f)(&mut self.state, a)) | |
1832 | } | |
1833 | ||
1834 | #[inline] | |
1835 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1836 | let (_, upper) = self.iter.size_hint(); | |
1837 | (0, upper) // can't know a lower bound, due to the scan function | |
1838 | } | |
1839 | } | |
1840 | ||
1841 | /// An iterator that maps each element to an iterator, and yields the elements | |
1842 | /// of the produced iterators. | |
1843 | /// | |
cc61c64b | 1844 | /// This `struct` is created by the [`flat_map`] method on [`Iterator`]. See its |
a7813a04 XL |
1845 | /// documentation for more. |
1846 | /// | |
cc61c64b | 1847 | /// [`flat_map`]: trait.Iterator.html#method.flat_map |
a7813a04 XL |
1848 | /// [`Iterator`]: trait.Iterator.html |
1849 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
1850 | #[stable(feature = "rust1", since = "1.0.0")] | |
1851 | #[derive(Clone)] | |
1852 | pub struct FlatMap<I, U: IntoIterator, F> { | |
1853 | iter: I, | |
1854 | f: F, | |
1855 | frontiter: Option<U::IntoIter>, | |
1856 | backiter: Option<U::IntoIter>, | |
1857 | } | |
1858 | ||
1859 | #[stable(feature = "core_impl_debug", since = "1.9.0")] | |
1860 | impl<I: fmt::Debug, U: IntoIterator, F> fmt::Debug for FlatMap<I, U, F> | |
1861 | where U::IntoIter: fmt::Debug | |
1862 | { | |
1863 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1864 | f.debug_struct("FlatMap") | |
1865 | .field("iter", &self.iter) | |
1866 | .field("frontiter", &self.frontiter) | |
1867 | .field("backiter", &self.backiter) | |
1868 | .finish() | |
1869 | } | |
1870 | } | |
1871 | ||
1872 | #[stable(feature = "rust1", since = "1.0.0")] | |
1873 | impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F> | |
1874 | where F: FnMut(I::Item) -> U, | |
1875 | { | |
1876 | type Item = U::Item; | |
1877 | ||
1878 | #[inline] | |
1879 | fn next(&mut self) -> Option<U::Item> { | |
1880 | loop { | |
1881 | if let Some(ref mut inner) = self.frontiter { | |
1882 | if let Some(x) = inner.by_ref().next() { | |
1883 | return Some(x) | |
1884 | } | |
1885 | } | |
1886 | match self.iter.next().map(&mut self.f) { | |
1887 | None => return self.backiter.as_mut().and_then(|it| it.next()), | |
1888 | next => self.frontiter = next.map(IntoIterator::into_iter), | |
1889 | } | |
1890 | } | |
1891 | } | |
1892 | ||
1893 | #[inline] | |
1894 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1895 | let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint()); | |
1896 | let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint()); | |
1897 | let lo = flo.saturating_add(blo); | |
1898 | match (self.iter.size_hint(), fhi, bhi) { | |
1899 | ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)), | |
1900 | _ => (lo, None) | |
1901 | } | |
1902 | } | |
1903 | } | |
1904 | ||
1905 | #[stable(feature = "rust1", since = "1.0.0")] | |
1906 | impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F> where | |
1907 | F: FnMut(I::Item) -> U, | |
1908 | U: IntoIterator, | |
1909 | U::IntoIter: DoubleEndedIterator | |
1910 | { | |
1911 | #[inline] | |
1912 | fn next_back(&mut self) -> Option<U::Item> { | |
1913 | loop { | |
1914 | if let Some(ref mut inner) = self.backiter { | |
1915 | if let Some(y) = inner.next_back() { | |
1916 | return Some(y) | |
1917 | } | |
1918 | } | |
1919 | match self.iter.next_back().map(&mut self.f) { | |
1920 | None => return self.frontiter.as_mut().and_then(|it| it.next_back()), | |
1921 | next => self.backiter = next.map(IntoIterator::into_iter), | |
1922 | } | |
1923 | } | |
1924 | } | |
1925 | } | |
1926 | ||
9e0c209e SL |
1927 | #[unstable(feature = "fused", issue = "35602")] |
1928 | impl<I, U, F> FusedIterator for FlatMap<I, U, F> | |
1929 | where I: FusedIterator, U: IntoIterator, F: FnMut(I::Item) -> U {} | |
1930 | ||
a7813a04 XL |
1931 | /// An iterator that yields `None` forever after the underlying iterator |
1932 | /// yields `None` once. | |
1933 | /// | |
cc61c64b | 1934 | /// This `struct` is created by the [`fuse`] method on [`Iterator`]. See its |
a7813a04 XL |
1935 | /// documentation for more. |
1936 | /// | |
cc61c64b | 1937 | /// [`fuse`]: trait.Iterator.html#method.fuse |
a7813a04 XL |
1938 | /// [`Iterator`]: trait.Iterator.html |
1939 | #[derive(Clone, Debug)] | |
1940 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
1941 | #[stable(feature = "rust1", since = "1.0.0")] | |
1942 | pub struct Fuse<I> { | |
1943 | iter: I, | |
1944 | done: bool | |
1945 | } | |
1946 | ||
9e0c209e SL |
1947 | #[unstable(feature = "fused", issue = "35602")] |
1948 | impl<I> FusedIterator for Fuse<I> where I: Iterator {} | |
1949 | ||
a7813a04 XL |
1950 | #[stable(feature = "rust1", since = "1.0.0")] |
1951 | impl<I> Iterator for Fuse<I> where I: Iterator { | |
1952 | type Item = <I as Iterator>::Item; | |
1953 | ||
1954 | #[inline] | |
9e0c209e | 1955 | default fn next(&mut self) -> Option<<I as Iterator>::Item> { |
a7813a04 XL |
1956 | if self.done { |
1957 | None | |
1958 | } else { | |
1959 | let next = self.iter.next(); | |
1960 | self.done = next.is_none(); | |
1961 | next | |
1962 | } | |
1963 | } | |
1964 | ||
1965 | #[inline] | |
9e0c209e | 1966 | default fn nth(&mut self, n: usize) -> Option<I::Item> { |
a7813a04 XL |
1967 | if self.done { |
1968 | None | |
1969 | } else { | |
1970 | let nth = self.iter.nth(n); | |
1971 | self.done = nth.is_none(); | |
1972 | nth | |
1973 | } | |
1974 | } | |
1975 | ||
1976 | #[inline] | |
9e0c209e | 1977 | default fn last(self) -> Option<I::Item> { |
a7813a04 XL |
1978 | if self.done { |
1979 | None | |
1980 | } else { | |
1981 | self.iter.last() | |
1982 | } | |
1983 | } | |
1984 | ||
1985 | #[inline] | |
9e0c209e | 1986 | default fn count(self) -> usize { |
a7813a04 XL |
1987 | if self.done { |
1988 | 0 | |
1989 | } else { | |
1990 | self.iter.count() | |
1991 | } | |
1992 | } | |
1993 | ||
1994 | #[inline] | |
9e0c209e | 1995 | default fn size_hint(&self) -> (usize, Option<usize>) { |
a7813a04 XL |
1996 | if self.done { |
1997 | (0, Some(0)) | |
1998 | } else { | |
1999 | self.iter.size_hint() | |
2000 | } | |
2001 | } | |
2002 | } | |
2003 | ||
2004 | #[stable(feature = "rust1", since = "1.0.0")] | |
2005 | impl<I> DoubleEndedIterator for Fuse<I> where I: DoubleEndedIterator { | |
2006 | #[inline] | |
9e0c209e | 2007 | default fn next_back(&mut self) -> Option<<I as Iterator>::Item> { |
a7813a04 XL |
2008 | if self.done { |
2009 | None | |
2010 | } else { | |
2011 | let next = self.iter.next_back(); | |
2012 | self.done = next.is_none(); | |
2013 | next | |
2014 | } | |
2015 | } | |
2016 | } | |
2017 | ||
9e0c209e SL |
2018 | unsafe impl<I> TrustedRandomAccess for Fuse<I> |
2019 | where I: TrustedRandomAccess, | |
2020 | { | |
2021 | unsafe fn get_unchecked(&mut self, i: usize) -> I::Item { | |
2022 | self.iter.get_unchecked(i) | |
2023 | } | |
c30ab7b3 SL |
2024 | |
2025 | fn may_have_side_effect() -> bool { | |
2026 | I::may_have_side_effect() | |
2027 | } | |
9e0c209e SL |
2028 | } |
2029 | ||
2030 | #[unstable(feature = "fused", issue = "35602")] | |
2031 | impl<I> Iterator for Fuse<I> where I: FusedIterator { | |
2032 | #[inline] | |
2033 | fn next(&mut self) -> Option<<I as Iterator>::Item> { | |
2034 | self.iter.next() | |
2035 | } | |
2036 | ||
2037 | #[inline] | |
2038 | fn nth(&mut self, n: usize) -> Option<I::Item> { | |
2039 | self.iter.nth(n) | |
2040 | } | |
2041 | ||
2042 | #[inline] | |
2043 | fn last(self) -> Option<I::Item> { | |
2044 | self.iter.last() | |
2045 | } | |
2046 | ||
2047 | #[inline] | |
2048 | fn count(self) -> usize { | |
2049 | self.iter.count() | |
2050 | } | |
2051 | ||
2052 | #[inline] | |
2053 | fn size_hint(&self) -> (usize, Option<usize>) { | |
2054 | self.iter.size_hint() | |
2055 | } | |
2056 | } | |
2057 | ||
2058 | #[unstable(feature = "fused", reason = "recently added", issue = "35602")] | |
2059 | impl<I> DoubleEndedIterator for Fuse<I> | |
2060 | where I: DoubleEndedIterator + FusedIterator | |
2061 | { | |
2062 | #[inline] | |
2063 | fn next_back(&mut self) -> Option<<I as Iterator>::Item> { | |
2064 | self.iter.next_back() | |
2065 | } | |
2066 | } | |
2067 | ||
2068 | ||
a7813a04 | 2069 | #[stable(feature = "rust1", since = "1.0.0")] |
476ff2be SL |
2070 | impl<I> ExactSizeIterator for Fuse<I> where I: ExactSizeIterator { |
2071 | fn len(&self) -> usize { | |
2072 | self.iter.len() | |
2073 | } | |
2074 | ||
2075 | fn is_empty(&self) -> bool { | |
2076 | self.iter.is_empty() | |
2077 | } | |
2078 | } | |
a7813a04 XL |
2079 | |
2080 | /// An iterator that calls a function with a reference to each element before | |
2081 | /// yielding it. | |
2082 | /// | |
cc61c64b | 2083 | /// This `struct` is created by the [`inspect`] method on [`Iterator`]. See its |
a7813a04 XL |
2084 | /// documentation for more. |
2085 | /// | |
cc61c64b | 2086 | /// [`inspect`]: trait.Iterator.html#method.inspect |
a7813a04 XL |
2087 | /// [`Iterator`]: trait.Iterator.html |
2088 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
2089 | #[stable(feature = "rust1", since = "1.0.0")] | |
2090 | #[derive(Clone)] | |
2091 | pub struct Inspect<I, F> { | |
2092 | iter: I, | |
2093 | f: F, | |
2094 | } | |
2095 | ||
2096 | #[stable(feature = "core_impl_debug", since = "1.9.0")] | |
2097 | impl<I: fmt::Debug, F> fmt::Debug for Inspect<I, F> { | |
2098 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
2099 | f.debug_struct("Inspect") | |
2100 | .field("iter", &self.iter) | |
2101 | .finish() | |
2102 | } | |
2103 | } | |
2104 | ||
2105 | impl<I: Iterator, F> Inspect<I, F> where F: FnMut(&I::Item) { | |
2106 | #[inline] | |
2107 | fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> { | |
2108 | if let Some(ref a) = elt { | |
2109 | (self.f)(a); | |
2110 | } | |
2111 | ||
2112 | elt | |
2113 | } | |
2114 | } | |
2115 | ||
2116 | #[stable(feature = "rust1", since = "1.0.0")] | |
2117 | impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) { | |
2118 | type Item = I::Item; | |
2119 | ||
2120 | #[inline] | |
2121 | fn next(&mut self) -> Option<I::Item> { | |
2122 | let next = self.iter.next(); | |
2123 | self.do_inspect(next) | |
2124 | } | |
2125 | ||
2126 | #[inline] | |
2127 | fn size_hint(&self) -> (usize, Option<usize>) { | |
2128 | self.iter.size_hint() | |
2129 | } | |
2130 | } | |
2131 | ||
2132 | #[stable(feature = "rust1", since = "1.0.0")] | |
2133 | impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F> | |
2134 | where F: FnMut(&I::Item), | |
2135 | { | |
2136 | #[inline] | |
2137 | fn next_back(&mut self) -> Option<I::Item> { | |
2138 | let next = self.iter.next_back(); | |
2139 | self.do_inspect(next) | |
2140 | } | |
2141 | } | |
2142 | ||
2143 | #[stable(feature = "rust1", since = "1.0.0")] | |
2144 | impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F> | |
476ff2be SL |
2145 | where F: FnMut(&I::Item) |
2146 | { | |
2147 | fn len(&self) -> usize { | |
2148 | self.iter.len() | |
2149 | } | |
2150 | ||
2151 | fn is_empty(&self) -> bool { | |
2152 | self.iter.is_empty() | |
2153 | } | |
2154 | } | |
9e0c209e SL |
2155 | |
2156 | #[unstable(feature = "fused", issue = "35602")] | |
2157 | impl<I: FusedIterator, F> FusedIterator for Inspect<I, F> | |
2158 | where F: FnMut(&I::Item) {} |