1 // Copyright 2013-2014 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.
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.
11 //! Composable external iterators
13 //! # The `Iterator` trait
15 //! This module defines Rust's core iteration trait. The `Iterator` trait has
16 //! one unimplemented method, `next`. All other methods are derived through
17 //! default methods to perform operations such as `zip`, `chain`, `enumerate`,
20 //! The goal of this module is to unify iteration across all containers in Rust.
21 //! An iterator can be considered as a state machine which is used to track
22 //! which element will be yielded next.
24 //! There are various extensions also defined in this module to assist with
25 //! various types of iteration, such as the `DoubleEndedIterator` for iterating
26 //! in reverse, the `FromIterator` trait for creating a container from an
27 //! iterator, and much more.
29 //! # Rust's `for` loop
31 //! The special syntax used by rust's `for` loop is based around the
32 //! `IntoIterator` trait defined in this module. `for` loops can be viewed as a
33 //! syntactical expansion into a `loop`, for example, the `for` loop in this
34 //! example is essentially translated to the `loop` below.
37 //! let values = vec![1, 2, 3];
40 //! println!("{}", x);
43 //! // Rough translation of the iteration without a `for` iterator.
44 //! # let values = vec![1, 2, 3];
45 //! let mut it = values.into_iter();
48 //! Some(x) => println!("{}", x),
54 //! Because `Iterator`s implement `IntoIterator`, this `for` loop syntax can be
55 //! applied to any iterator over any type.
57 #![stable(feature = "rust1", since = "1.0.0")]
60 use self::MinMaxResult
::*;
64 use cmp
::{Ord, PartialOrd, PartialEq}
;
69 use ops
::{self, Add, Sub, FnMut, Mul, RangeFrom}
;
70 use option
::Option
::{self, Some, None}
;
74 fn _assert_is_object_safe(_
: &Iterator
<Item
=()>) {}
76 /// An interface for dealing with "external iterators". These types of iterators
77 /// can be resumed at any time as all state is stored internally as opposed to
78 /// being located on the call stack.
80 /// The Iterator protocol states that an iterator yields a (potentially-empty,
81 /// potentially-infinite) sequence of values, and returns `None` to signal that
82 /// it's finished. The Iterator protocol does not define behavior after `None`
83 /// is returned. A concrete Iterator implementation may choose to behave however
84 /// it wishes, either by returning `None` infinitely, or by doing something
87 #[stable(feature = "rust1", since = "1.0.0")]
88 #[rustc_on_unimplemented = "`{Self}` is not an iterator; maybe try calling \
89 `.iter()` or a similar method"]
91 /// The type of the elements being iterated
92 #[stable(feature = "rust1", since = "1.0.0")]
95 /// Advances the iterator and returns the next value. Returns `None` when the
97 #[stable(feature = "rust1", since = "1.0.0")]
98 fn next(&mut self) -> Option
<Self::Item
>;
100 /// Returns a lower and upper bound on the remaining length of the iterator.
102 /// An upper bound of `None` means either there is no known upper bound, or
103 /// the upper bound does not fit within a `usize`.
105 #[stable(feature = "rust1", since = "1.0.0")]
106 fn size_hint(&self) -> (usize, Option
<usize>) { (0, None) }
108 /// Counts the number of elements in this iterator.
110 /// # Overflow Behavior
112 /// The method does no guarding against overflows, so counting elements of
113 /// an iterator with more than `usize::MAX` elements either produces the
114 /// wrong result or panics. If debug assertions are enabled, a panic is
119 /// This functions might panic if the iterator has more than `usize::MAX`
125 /// let a = [1, 2, 3, 4, 5];
126 /// assert_eq!(a.iter().count(), 5);
129 #[stable(feature = "rust1", since = "1.0.0")]
130 fn count(self) -> usize where Self: Sized
{
132 self.fold(0, |cnt
, _
| cnt
+ 1)
135 /// Loops through the entire iterator, returning the last element.
140 /// let a = [1, 2, 3, 4, 5];
141 /// assert_eq!(a.iter().last(), Some(&5));
144 #[stable(feature = "rust1", since = "1.0.0")]
145 fn last(self) -> Option
<Self::Item
> where Self: Sized
{
147 for x
in self { last = Some(x); }
151 /// Loops through `n` iterations, returning the `n`th element of the
157 /// let a = [1, 2, 3, 4, 5];
158 /// let mut it = a.iter();
159 /// assert_eq!(it.nth(2), Some(&3));
160 /// assert_eq!(it.nth(2), None);
163 #[stable(feature = "rust1", since = "1.0.0")]
164 fn nth(&mut self, mut n
: usize) -> Option
<Self::Item
> where Self: Sized
{
165 for x
in self.by_ref() {
166 if n
== 0 { return Some(x) }
172 /// Chain this iterator with another, returning a new iterator that will
173 /// finish iterating over the current iterator, and then iterate
174 /// over the other specified iterator.
181 /// let mut it = a.iter().chain(&b);
182 /// assert_eq!(it.next(), Some(&0));
183 /// assert_eq!(it.next(), Some(&1));
184 /// assert!(it.next().is_none());
187 #[stable(feature = "rust1", since = "1.0.0")]
188 fn chain
<U
>(self, other
: U
) -> Chain
<Self, U
::IntoIter
> where
189 Self: Sized
, U
: IntoIterator
<Item
=Self::Item
>,
191 Chain{a: self, b: other.into_iter(), flag: false}
194 /// Creates an iterator that iterates over both this and the specified
195 /// iterators simultaneously, yielding the two elements as pairs. When
196 /// either iterator returns `None`, all further invocations of `next()`
197 /// will return `None`.
204 /// let mut it = a.iter().zip(&b);
205 /// assert_eq!(it.next(), Some((&0, &1)));
206 /// assert!(it.next().is_none());
209 /// `zip` can provide similar functionality to `enumerate`:
212 /// for pair in "foo".chars().enumerate() {
213 /// println!("{:?}", pair);
216 /// for pair in (0..).zip("foo".chars()) {
217 /// println!("{:?}", pair);
221 /// both produce the same output.
223 #[stable(feature = "rust1", since = "1.0.0")]
224 fn zip
<U
>(self, other
: U
) -> Zip
<Self, U
::IntoIter
> where
225 Self: Sized
, U
: IntoIterator
227 Zip{a: self, b: other.into_iter()}
230 /// Creates a new iterator that will apply the specified function to each
231 /// element returned by the first, yielding the mapped element instead.
237 /// let mut it = a.iter().map(|&x| 2 * x);
238 /// assert_eq!(it.next(), Some(2));
239 /// assert_eq!(it.next(), Some(4));
240 /// assert!(it.next().is_none());
243 #[stable(feature = "rust1", since = "1.0.0")]
244 fn map
<B
, F
>(self, f
: F
) -> Map
<Self, F
> where
245 Self: Sized
, F
: FnMut(Self::Item
) -> B
,
247 Map{iter: self, f: f}
250 /// Creates an iterator that applies the predicate to each element returned
251 /// by this iterator. The only elements that will be yielded are those that
252 /// make the predicate evaluate to `true`.
258 /// let mut it = a.iter().filter(|&x| *x > 1);
259 /// assert_eq!(it.next(), Some(&2));
260 /// assert!(it.next().is_none());
263 #[stable(feature = "rust1", since = "1.0.0")]
264 fn filter
<P
>(self, predicate
: P
) -> Filter
<Self, P
> where
265 Self: Sized
, P
: FnMut(&Self::Item
) -> bool
,
267 Filter{iter: self, predicate: predicate}
270 /// Creates an iterator that both filters and maps elements.
271 /// If the specified function returns `None`, the element is skipped.
272 /// Otherwise the option is unwrapped and the new value is yielded.
278 /// let mut it = a.iter().filter_map(|&x| if x > 1 {Some(2 * x)} else {None});
279 /// assert_eq!(it.next(), Some(4));
280 /// assert!(it.next().is_none());
283 #[stable(feature = "rust1", since = "1.0.0")]
284 fn filter_map
<B
, F
>(self, f
: F
) -> FilterMap
<Self, F
> where
285 Self: Sized
, F
: FnMut(Self::Item
) -> Option
<B
>,
287 FilterMap { iter: self, f: f }
290 /// Creates an iterator that yields pairs `(i, val)` where `i` is the
291 /// current index of iteration and `val` is the value returned by the
294 /// `enumerate` keeps its count as a `usize`. If you want to count by a
295 /// different sized integer, the `zip` function provides similar
298 /// # Overflow Behavior
300 /// The method does no guarding against overflows, so enumerating more than
301 /// `usize::MAX` elements either produces the wrong result or panics. If
302 /// debug assertions are enabled, a panic is guaranteed.
306 /// The returned iterator might panic if the to-be-returned index would
307 /// overflow a `usize`.
312 /// let a = [100, 200];
313 /// let mut it = a.iter().enumerate();
314 /// assert_eq!(it.next(), Some((0, &100)));
315 /// assert_eq!(it.next(), Some((1, &200)));
316 /// assert!(it.next().is_none());
319 #[stable(feature = "rust1", since = "1.0.0")]
320 fn enumerate(self) -> Enumerate
<Self> where Self: Sized
{
321 Enumerate { iter: self, count: 0 }
324 /// Creates an iterator that has a `.peek()` method
325 /// that returns an optional reference to the next element.
330 /// let xs = [100, 200, 300];
331 /// let mut it = xs.iter().cloned().peekable();
332 /// assert_eq!(*it.peek().unwrap(), 100);
333 /// assert_eq!(it.next().unwrap(), 100);
334 /// assert_eq!(it.next().unwrap(), 200);
335 /// assert_eq!(*it.peek().unwrap(), 300);
336 /// assert_eq!(*it.peek().unwrap(), 300);
337 /// assert_eq!(it.next().unwrap(), 300);
338 /// assert!(it.peek().is_none());
339 /// assert!(it.next().is_none());
342 #[stable(feature = "rust1", since = "1.0.0")]
343 fn peekable(self) -> Peekable
<Self> where Self: Sized
{
344 Peekable{iter: self, peeked: None}
347 /// Creates an iterator that invokes the predicate on elements
348 /// until it returns false. Once the predicate returns false, that
349 /// element and all further elements are yielded.
354 /// let a = [1, 2, 3, 4, 5];
355 /// let mut it = a.iter().skip_while(|&a| *a < 3);
356 /// assert_eq!(it.next(), Some(&3));
357 /// assert_eq!(it.next(), Some(&4));
358 /// assert_eq!(it.next(), Some(&5));
359 /// assert!(it.next().is_none());
362 #[stable(feature = "rust1", since = "1.0.0")]
363 fn skip_while
<P
>(self, predicate
: P
) -> SkipWhile
<Self, P
> where
364 Self: Sized
, P
: FnMut(&Self::Item
) -> bool
,
366 SkipWhile{iter: self, flag: false, predicate: predicate}
369 /// Creates an iterator that yields elements so long as the predicate
370 /// returns true. After the predicate returns false for the first time, no
371 /// further elements will be yielded.
376 /// let a = [1, 2, 3, 4, 5];
377 /// let mut it = a.iter().take_while(|&a| *a < 3);
378 /// assert_eq!(it.next(), Some(&1));
379 /// assert_eq!(it.next(), Some(&2));
380 /// assert!(it.next().is_none());
383 #[stable(feature = "rust1", since = "1.0.0")]
384 fn take_while
<P
>(self, predicate
: P
) -> TakeWhile
<Self, P
> where
385 Self: Sized
, P
: FnMut(&Self::Item
) -> bool
,
387 TakeWhile{iter: self, flag: false, predicate: predicate}
390 /// Creates an iterator that skips the first `n` elements of this iterator,
391 /// and then yields all further items.
396 /// let a = [1, 2, 3, 4, 5];
397 /// let mut it = a.iter().skip(3);
398 /// assert_eq!(it.next(), Some(&4));
399 /// assert_eq!(it.next(), Some(&5));
400 /// assert!(it.next().is_none());
403 #[stable(feature = "rust1", since = "1.0.0")]
404 fn skip(self, n
: usize) -> Skip
<Self> where Self: Sized
{
405 Skip{iter: self, n: n}
408 /// Creates an iterator that yields the first `n` elements of this
414 /// let a = [1, 2, 3, 4, 5];
415 /// let mut it = a.iter().take(3);
416 /// assert_eq!(it.next(), Some(&1));
417 /// assert_eq!(it.next(), Some(&2));
418 /// assert_eq!(it.next(), Some(&3));
419 /// assert!(it.next().is_none());
422 #[stable(feature = "rust1", since = "1.0.0")]
423 fn take(self, n
: usize) -> Take
<Self> where Self: Sized
, {
424 Take{iter: self, n: n}
427 /// Creates a new iterator that behaves in a similar fashion to fold.
428 /// There is a state which is passed between each iteration and can be
429 /// mutated as necessary. The yielded values from the closure are yielded
430 /// from the Scan instance when not `None`.
435 /// let a = [1, 2, 3, 4, 5];
436 /// let mut it = a.iter().scan(1, |fac, &x| {
440 /// assert_eq!(it.next(), Some(1));
441 /// assert_eq!(it.next(), Some(2));
442 /// assert_eq!(it.next(), Some(6));
443 /// assert_eq!(it.next(), Some(24));
444 /// assert_eq!(it.next(), Some(120));
445 /// assert!(it.next().is_none());
448 #[stable(feature = "rust1", since = "1.0.0")]
450 fn scan
<St
, B
, F
>(self, initial_state
: St
, f
: F
) -> Scan
<Self, St
, F
>
451 where Self: Sized
, F
: FnMut(&mut St
, Self::Item
) -> Option
<B
>,
453 Scan{iter: self, f: f, state: initial_state}
456 /// Takes a function that maps each element to a new iterator and yields
457 /// all the elements of the produced iterators.
459 /// This is useful for unraveling nested structures.
464 /// let words = ["alpha", "beta", "gamma"];
465 /// let merged: String = words.iter()
466 /// .flat_map(|s| s.chars())
468 /// assert_eq!(merged, "alphabetagamma");
471 #[stable(feature = "rust1", since = "1.0.0")]
472 fn flat_map
<U
, F
>(self, f
: F
) -> FlatMap
<Self, U
, F
>
473 where Self: Sized
, U
: IntoIterator
, F
: FnMut(Self::Item
) -> U
,
475 FlatMap{iter: self, f: f, frontiter: None, backiter: None }
478 /// Creates an iterator that yields `None` forever after the underlying
479 /// iterator yields `None`. Random-access iterator behavior is not
480 /// affected, only single and double-ended iterator behavior.
485 /// fn process<U: Iterator<Item=i32>>(it: U) -> i32 {
486 /// let mut it = it.fuse();
488 /// for x in it.by_ref() {
494 /// // did we exhaust the iterator?
495 /// if it.next().is_none() {
500 /// let x = vec![1, 2, 3, 7, 8, 9];
501 /// assert_eq!(process(x.into_iter()), 6);
502 /// let x = vec![1, 2, 3];
503 /// assert_eq!(process(x.into_iter()), 1006);
506 #[stable(feature = "rust1", since = "1.0.0")]
507 fn fuse(self) -> Fuse
<Self> where Self: Sized
{
508 Fuse{iter: self, done: false}
511 /// Creates an iterator that calls a function with a reference to each
512 /// element before yielding it. This is often useful for debugging an
513 /// iterator pipeline.
518 /// let a = [1, 4, 2, 3, 8, 9, 6];
519 /// let sum: i32 = a.iter()
521 /// .inspect(|&x| println!("filtering {}", x))
522 /// .filter(|&x| x % 2 == 0)
523 /// .inspect(|&x| println!("{} made it through", x))
524 /// .fold(0, |sum, i| sum + i);
525 /// println!("{}", sum);
528 #[stable(feature = "rust1", since = "1.0.0")]
529 fn inspect
<F
>(self, f
: F
) -> Inspect
<Self, F
> where
530 Self: Sized
, F
: FnMut(&Self::Item
),
532 Inspect{iter: self, f: f}
535 /// Creates a wrapper around a mutable reference to the iterator.
537 /// This is useful to allow applying iterator adaptors while still
538 /// retaining ownership of the original iterator value.
543 /// let mut it = 0..10;
544 /// // sum the first five values
545 /// let partial_sum = it.by_ref().take(5).fold(0, |a, b| a + b);
546 /// assert_eq!(partial_sum, 10);
547 /// assert_eq!(it.next(), Some(5));
549 #[stable(feature = "rust1", since = "1.0.0")]
550 fn by_ref(&mut self) -> &mut Self where Self: Sized { self }
552 /// Loops through the entire iterator, collecting all of the elements into
553 /// a container implementing `FromIterator`.
558 /// let expected = [1, 2, 3, 4, 5];
559 /// let actual: Vec<_> = expected.iter().cloned().collect();
560 /// assert_eq!(actual, expected);
563 #[stable(feature = "rust1", since = "1.0.0")]
564 fn collect
<B
: FromIterator
<Self::Item
>>(self) -> B
where Self: Sized
{
565 FromIterator
::from_iter(self)
568 /// Loops through the entire iterator, collecting all of the elements into
569 /// one of two containers, depending on a predicate. The elements of the
570 /// first container satisfy the predicate, while the elements of the second
574 /// let vec = vec![1, 2, 3, 4];
575 /// let (even, odd): (Vec<_>, Vec<_>) = vec.into_iter().partition(|&n| n % 2 == 0);
576 /// assert_eq!(even, [2, 4]);
577 /// assert_eq!(odd, [1, 3]);
579 #[stable(feature = "rust1", since = "1.0.0")]
580 fn partition
<B
, F
>(self, mut f
: F
) -> (B
, B
) where
582 B
: Default
+ Extend
<Self::Item
>,
583 F
: FnMut(&Self::Item
) -> bool
585 let mut left
: B
= Default
::default();
586 let mut right
: B
= Default
::default();
592 right
.extend(Some(x
))
599 /// Performs a fold operation over the entire iterator, returning the
600 /// eventual state at the end of the iteration.
602 /// This operation is sometimes called 'reduce' or 'inject'.
607 /// let a = [1, 2, 3, 4, 5];
608 /// assert_eq!(a.iter().fold(0, |acc, &item| acc + item), 15);
611 #[stable(feature = "rust1", since = "1.0.0")]
612 fn fold
<B
, F
>(self, init
: B
, mut f
: F
) -> B
where
613 Self: Sized
, F
: FnMut(B
, Self::Item
) -> B
,
615 let mut accum
= init
;
622 /// Tests whether the predicate holds true for all elements in the iterator.
627 /// let a = [1, 2, 3, 4, 5];
628 /// assert!(a.iter().all(|x| *x > 0));
629 /// assert!(!a.iter().all(|x| *x > 2));
632 #[stable(feature = "rust1", since = "1.0.0")]
633 fn all
<F
>(&mut self, mut f
: F
) -> bool
where
634 Self: Sized
, F
: FnMut(Self::Item
) -> bool
636 for x
in self.by_ref() {
644 /// Tests whether any element of an iterator satisfies the specified
647 /// Does not consume the iterator past the first found element.
652 /// let a = [1, 2, 3, 4, 5];
653 /// let mut it = a.iter();
654 /// assert!(it.any(|x| *x == 3));
655 /// assert_eq!(it.collect::<Vec<_>>(), [&4, &5]);
658 #[stable(feature = "rust1", since = "1.0.0")]
659 fn any
<F
>(&mut self, mut f
: F
) -> bool
where
661 F
: FnMut(Self::Item
) -> bool
663 for x
in self.by_ref() {
671 /// Returns the first element satisfying the specified predicate.
673 /// Does not consume the iterator past the first found element.
678 /// let a = [1, 2, 3, 4, 5];
679 /// let mut it = a.iter();
680 /// assert_eq!(it.find(|&x| *x == 3), Some(&3));
681 /// assert_eq!(it.collect::<Vec<_>>(), [&4, &5]);
683 #[stable(feature = "rust1", since = "1.0.0")]
684 fn find
<P
>(&mut self, mut predicate
: P
) -> Option
<Self::Item
> where
686 P
: FnMut(&Self::Item
) -> bool
,
688 for x
in self.by_ref() {
689 if predicate(&x
) { return Some(x) }
694 /// Returns the index of the first element satisfying the specified predicate
696 /// Does not consume the iterator past the first found element.
698 /// # Overflow Behavior
700 /// The method does no guarding against overflows, so if there are more
701 /// than `usize::MAX` non-matching elements, it either produces the wrong
702 /// result or panics. If debug assertions are enabled, a panic is
707 /// This functions might panic if the iterator has more than `usize::MAX`
708 /// non-matching elements.
713 /// let a = [1, 2, 3, 4, 5];
714 /// let mut it = a.iter();
715 /// assert_eq!(it.position(|x| *x == 3), Some(2));
716 /// assert_eq!(it.collect::<Vec<_>>(), [&4, &5]);
718 #[stable(feature = "rust1", since = "1.0.0")]
719 fn position
<P
>(&mut self, mut predicate
: P
) -> Option
<usize> where
721 P
: FnMut(Self::Item
) -> bool
,
723 // `enumerate` might overflow.
724 for (i
, x
) in self.by_ref().enumerate() {
732 /// Returns the index of the last element satisfying the specified predicate
734 /// If no element matches, `None` is returned.
736 /// Does not consume the iterator *before* the first found element.
741 /// let a = [1, 2, 2, 4, 5];
742 /// let mut it = a.iter();
743 /// assert_eq!(it.rposition(|x| *x == 2), Some(2));
744 /// assert_eq!(it.collect::<Vec<_>>(), [&1, &2]);
746 #[stable(feature = "rust1", since = "1.0.0")]
747 fn rposition
<P
>(&mut self, mut predicate
: P
) -> Option
<usize> where
748 P
: FnMut(Self::Item
) -> bool
,
749 Self: Sized
+ ExactSizeIterator
+ DoubleEndedIterator
751 let mut i
= self.len();
753 while let Some(v
) = self.next_back() {
757 // No need for an overflow check here, because `ExactSizeIterator`
758 // implies that the number of elements fits into a `usize`.
764 /// Consumes the entire iterator to return the maximum element.
766 /// Returns the rightmost element if the comparison determines two elements
767 /// to be equally maximum.
772 /// let a = [1, 2, 3, 4, 5];
773 /// assert_eq!(a.iter().max(), Some(&5));
776 #[stable(feature = "rust1", since = "1.0.0")]
777 fn max(self) -> Option
<Self::Item
> where Self: Sized
, Self::Item
: Ord
781 // switch to y even if it is only equal, to preserve
783 |_
, x
, _
, y
| *x
<= *y
)
787 /// Consumes the entire iterator to return the minimum element.
789 /// Returns the leftmost element if the comparison determines two elements
790 /// to be equally minimum.
795 /// let a = [1, 2, 3, 4, 5];
796 /// assert_eq!(a.iter().min(), Some(&1));
799 #[stable(feature = "rust1", since = "1.0.0")]
800 fn min(self) -> Option
<Self::Item
> where Self: Sized
, Self::Item
: Ord
804 // only switch to y if it is strictly smaller, to
805 // preserve stability.
806 |_
, x
, _
, y
| *x
> *y
)
810 /// `min_max` finds the minimum and maximum elements in the iterator.
812 /// The return type `MinMaxResult` is an enum of three variants:
814 /// - `NoElements` if the iterator is empty.
815 /// - `OneElement(x)` if the iterator has exactly one element.
816 /// - `MinMax(x, y)` is returned otherwise, where `x <= y`. Two
817 /// values are equal if and only if there is more than one
818 /// element in the iterator and all elements are equal.
820 /// On an iterator of length `n`, `min_max` does `1.5 * n` comparisons,
821 /// and so is faster than calling `min` and `max` separately which does `2 *
827 /// #![feature(iter_min_max)]
829 /// use std::iter::MinMaxResult::{NoElements, OneElement, MinMax};
831 /// let a: [i32; 0] = [];
832 /// assert_eq!(a.iter().min_max(), NoElements);
835 /// assert_eq!(a.iter().min_max(), OneElement(&1));
837 /// let a = [1, 2, 3, 4, 5];
838 /// assert_eq!(a.iter().min_max(), MinMax(&1, &5));
840 /// let a = [1, 1, 1, 1];
841 /// assert_eq!(a.iter().min_max(), MinMax(&1, &1));
843 #[unstable(feature = "iter_min_max",
844 reason
= "return type may change or may wish to have a closure \
845 based version as well")]
846 #[deprecated(since = "1.3.0", reason = "has not proven itself")]
848 fn min_max(mut self) -> MinMaxResult
<Self::Item
> where Self: Sized
, Self::Item
: Ord
850 let (mut min
, mut max
) = match self.next() {
851 None
=> return NoElements
,
854 None
=> return OneElement(x
),
855 Some(y
) => if x
<= y {(x, y)}
else {(y, x)}
861 // `first` and `second` are the two next elements we want to look
862 // at. We first compare `first` and `second` (#1). The smaller one
863 // is then compared to current minimum (#2). The larger one is
864 // compared to current maximum (#3). This way we do 3 comparisons
866 let first
= match self.next() {
870 let second
= match self.next() {
874 } else if first
>= max
{
882 if first
< min { min = first }
883 if second
>= max { max = second }
885 if second
< min { min = second }
886 if first
>= max { max = first }
893 /// Returns the element that gives the maximum value from the
894 /// specified function.
896 /// Returns the rightmost element if the comparison determines two elements
897 /// to be equally maximum.
902 /// #![feature(iter_cmp)]
904 /// let a = [-3_i32, 0, 1, 5, -10];
905 /// assert_eq!(*a.iter().max_by(|x| x.abs()).unwrap(), -10);
908 #[unstable(feature = "iter_cmp",
909 reason
= "may want to produce an Ordering directly; see #15311")]
910 fn max_by
<B
: Ord
, F
>(self, f
: F
) -> Option
<Self::Item
> where
912 F
: FnMut(&Self::Item
) -> B
,
916 // switch to y even if it is only equal, to preserve
918 |x_p
, _
, y_p
, _
| x_p
<= y_p
)
922 /// Returns the element that gives the minimum value from the
923 /// specified function.
925 /// Returns the leftmost element if the comparison determines two elements
926 /// to be equally minimum.
931 /// #![feature(iter_cmp)]
933 /// let a = [-3_i32, 0, 1, 5, -10];
934 /// assert_eq!(*a.iter().min_by(|x| x.abs()).unwrap(), 0);
937 #[unstable(feature = "iter_cmp",
938 reason
= "may want to produce an Ordering directly; see #15311")]
939 fn min_by
<B
: Ord
, F
>(self, f
: F
) -> Option
<Self::Item
> where
941 F
: FnMut(&Self::Item
) -> B
,
945 // only switch to y if it is strictly smaller, to
946 // preserve stability.
947 |x_p
, _
, y_p
, _
| x_p
> y_p
)
951 /// Change the direction of the iterator
953 /// The flipped iterator swaps the ends on an iterator that can already
954 /// be iterated from the front and from the back.
957 /// If the iterator also implements RandomAccessIterator, the flipped
958 /// iterator is also random access, with the indices starting at the back
959 /// of the original iterator.
961 /// Note: Random access with flipped indices still only applies to the first
962 /// `std::usize::MAX` elements of the original iterator.
964 #[stable(feature = "rust1", since = "1.0.0")]
965 fn rev(self) -> Rev
<Self> where Self: Sized
+ DoubleEndedIterator
{
969 /// Converts an iterator of pairs into a pair of containers.
971 /// Loops through the entire iterator, collecting the first component of
972 /// each item into one new container, and the second component into another.
977 /// let a = [(1, 2), (3, 4)];
978 /// let (left, right): (Vec<_>, Vec<_>) = a.iter().cloned().unzip();
979 /// assert_eq!(left, [1, 3]);
980 /// assert_eq!(right, [2, 4]);
982 #[stable(feature = "rust1", since = "1.0.0")]
983 fn unzip
<A
, B
, FromA
, FromB
>(self) -> (FromA
, FromB
) where
984 FromA
: Default
+ Extend
<A
>,
985 FromB
: Default
+ Extend
<B
>,
986 Self: Sized
+ Iterator
<Item
=(A
, B
)>,
988 struct SizeHint
<A
>(usize, Option
<usize>, marker
::PhantomData
<A
>);
989 impl<A
> Iterator
for SizeHint
<A
> {
992 fn next(&mut self) -> Option
<A
> { None }
993 fn size_hint(&self) -> (usize, Option
<usize>) {
998 let (lo
, hi
) = self.size_hint();
999 let mut ts
: FromA
= Default
::default();
1000 let mut us
: FromB
= Default
::default();
1002 ts
.extend(SizeHint(lo
, hi
, marker
::PhantomData
));
1003 us
.extend(SizeHint(lo
, hi
, marker
::PhantomData
));
1005 for (t
, u
) in self {
1013 /// Creates an iterator that clones the elements it yields.
1015 /// This is useful for converting an Iterator<&T> to an Iterator<T>,
1016 /// so it's a more convenient form of `map(|&x| x)`.
1021 /// let a = [0, 1, 2];
1022 /// let v_cloned: Vec<_> = a.iter().cloned().collect();
1023 /// let v_map: Vec<_> = a.iter().map(|&x| x).collect();
1024 /// assert_eq!(v_cloned, v_map);
1026 #[stable(feature = "rust1", since = "1.0.0")]
1027 fn cloned
<'a
, T
: 'a
>(self) -> Cloned
<Self>
1028 where Self: Sized
+ Iterator
<Item
=&'a T
>, T
: Clone
1033 /// Repeats an iterator endlessly
1039 /// let mut it = a.iter().cycle();
1040 /// assert_eq!(it.next(), Some(&1));
1041 /// assert_eq!(it.next(), Some(&2));
1042 /// assert_eq!(it.next(), Some(&1));
1044 #[stable(feature = "rust1", since = "1.0.0")]
1046 fn cycle(self) -> Cycle
<Self> where Self: Sized
+ Clone
{
1047 Cycle{orig: self.clone(), iter: self}
1050 /// Use an iterator to reverse a container in place.
1051 #[unstable(feature = "core",
1052 reason
= "uncertain about placement or widespread use")]
1053 #[deprecated(since = "1.2.0",
1054 reason
= "not performant enough to justify inclusion")]
1055 fn reverse_in_place
<'a
, T
: 'a
>(&mut self) where
1056 Self: Sized
+ Iterator
<Item
=&'a
mut T
> + DoubleEndedIterator
1059 match (self.next(), self.next_back()) {
1060 (Some(x
), Some(y
)) => mem
::swap(x
, y
),
1066 /// Iterates over the entire iterator, summing up all the elements
1071 /// #![feature(iter_arith)]
1073 /// let a = [1, 2, 3, 4, 5];
1074 /// let it = a.iter();
1075 /// assert_eq!(it.sum::<i32>(), 15);
1077 #[unstable(feature="iter_arith", reason = "bounds recently changed")]
1078 fn sum
<S
=<Self as Iterator
>::Item
>(self) -> S
where
1079 S
: Add
<Self::Item
, Output
=S
> + Zero
,
1082 self.fold(Zero
::zero(), |s
, e
| s
+ e
)
1085 /// Iterates over the entire iterator, multiplying all the elements
1090 /// #![feature(iter_arith)]
1092 /// fn factorial(n: u32) -> u32 {
1093 /// (1..).take_while(|&i| i <= n).product()
1095 /// assert_eq!(factorial(0), 1);
1096 /// assert_eq!(factorial(1), 1);
1097 /// assert_eq!(factorial(5), 120);
1099 #[unstable(feature="iter_arith", reason = "bounds recently changed")]
1100 fn product
<P
=<Self as Iterator
>::Item
>(self) -> P
where
1101 P
: Mul
<Self::Item
, Output
=P
> + One
,
1104 self.fold(One
::one(), |p
, e
| p
* e
)
1108 /// Select an element from an iterator based on the given projection
1109 /// and "comparison" function.
1111 /// This is an idiosyncratic helper to try to factor out the
1112 /// commonalities of {max,min}{,_by}. In particular, this avoids
1113 /// having to implement optimisations several times.
1115 fn select_fold1
<I
,B
, FProj
, FCmp
>(mut it
: I
,
1117 mut f_cmp
: FCmp
) -> Option
<(B
, I
::Item
)>
1119 FProj
: FnMut(&I
::Item
) -> B
,
1120 FCmp
: FnMut(&B
, &I
::Item
, &B
, &I
::Item
) -> bool
1122 // start with the first element as our selection. This avoids
1123 // having to use `Option`s inside the loop, translating to a
1124 // sizeable performance gain (6x in one case).
1125 it
.next().map(|mut sel
| {
1126 let mut sel_p
= f_proj(&sel
);
1129 let x_p
= f_proj(&x
);
1130 if f_cmp(&sel_p
, &sel
, &x_p
, &x
) {
1139 #[stable(feature = "rust1", since = "1.0.0")]
1140 impl<'a
, I
: Iterator
+ ?Sized
> Iterator
for &'a
mut I
{
1141 type Item
= I
::Item
;
1142 fn next(&mut self) -> Option
<I
::Item
> { (**self).next() }
1143 fn size_hint(&self) -> (usize, Option
<usize>) { (**self).size_hint() }
1146 /// Conversion from an `Iterator`
1147 #[stable(feature = "rust1", since = "1.0.0")]
1148 #[rustc_on_unimplemented="a collection of type `{Self}` cannot be \
1149 built from an iterator over elements of type `{A}`"]
1150 pub trait FromIterator
<A
> {
1151 /// Builds a container with elements from something iterable.
1156 /// use std::collections::HashSet;
1157 /// use std::iter::FromIterator;
1159 /// let colors_vec = vec!["red", "red", "yellow", "blue"];
1160 /// let colors_set = HashSet::<&str>::from_iter(colors_vec);
1161 /// assert_eq!(colors_set.len(), 3);
1164 /// `FromIterator` is more commonly used implicitly via the
1165 /// `Iterator::collect` method:
1168 /// use std::collections::HashSet;
1170 /// let colors_vec = vec!["red", "red", "yellow", "blue"];
1171 /// let colors_set = colors_vec.into_iter().collect::<HashSet<&str>>();
1172 /// assert_eq!(colors_set.len(), 3);
1174 #[stable(feature = "rust1", since = "1.0.0")]
1175 fn from_iter
<T
: IntoIterator
<Item
=A
>>(iterator
: T
) -> Self;
1178 /// Conversion into an `Iterator`
1180 /// Implementing this trait allows you to use your type with Rust's `for` loop. See
1181 /// the [module level documentation](index.html) for more details.
1182 #[stable(feature = "rust1", since = "1.0.0")]
1183 pub trait IntoIterator
{
1184 /// The type of the elements being iterated
1185 #[stable(feature = "rust1", since = "1.0.0")]
1188 /// A container for iterating over elements of type `Item`
1189 #[stable(feature = "rust1", since = "1.0.0")]
1190 type IntoIter
: Iterator
<Item
=Self::Item
>;
1192 /// Consumes `Self` and returns an iterator over it
1193 #[stable(feature = "rust1", since = "1.0.0")]
1194 fn into_iter(self) -> Self::IntoIter
;
1197 #[stable(feature = "rust1", since = "1.0.0")]
1198 impl<I
: Iterator
> IntoIterator
for I
{
1199 type Item
= I
::Item
;
1202 fn into_iter(self) -> I
{
1207 /// A type growable from an `Iterator` implementation
1208 #[stable(feature = "rust1", since = "1.0.0")]
1209 pub trait Extend
<A
> {
1210 /// Extends a container with the elements yielded by an arbitrary iterator
1211 #[stable(feature = "rust1", since = "1.0.0")]
1212 fn extend
<T
: IntoIterator
<Item
=A
>>(&mut self, iterable
: T
);
1215 /// A range iterator able to yield elements from both ends
1217 /// A `DoubleEndedIterator` can be thought of as a deque in that `next()` and
1218 /// `next_back()` exhaust elements from the *same* range, and do not work
1219 /// independently of each other.
1220 #[stable(feature = "rust1", since = "1.0.0")]
1221 pub trait DoubleEndedIterator
: Iterator
{
1222 /// Yields an element from the end of the range, returning `None` if the
1224 #[stable(feature = "rust1", since = "1.0.0")]
1225 fn next_back(&mut self) -> Option
<Self::Item
>;
1228 #[stable(feature = "rust1", since = "1.0.0")]
1229 impl<'a
, I
: DoubleEndedIterator
+ ?Sized
> DoubleEndedIterator
for &'a
mut I
{
1230 fn next_back(&mut self) -> Option
<I
::Item
> { (**self).next_back() }
1233 /// An object implementing random access indexing by `usize`
1235 /// A `RandomAccessIterator` should be either infinite or a
1236 /// `DoubleEndedIterator`. Calling `next()` or `next_back()` on a
1237 /// `RandomAccessIterator` reduces the indexable range accordingly. That is,
1238 /// `it.idx(1)` will become `it.idx(0)` after `it.next()` is called.
1239 #[unstable(feature = "iter_idx",
1240 reason
= "not widely used, may be better decomposed into Index \
1241 and ExactSizeIterator")]
1242 #[deprecated(since = "1.2.0",
1243 reason
= "trait has not proven itself as a widely useful \
1244 abstraction for iterators, and more time may be needed \
1245 for iteration on the design")]
1246 #[allow(deprecated)]
1247 pub trait RandomAccessIterator
: Iterator
{
1248 /// Returns the number of indexable elements. At most `std::usize::MAX`
1249 /// elements are indexable, even if the iterator represents a longer range.
1250 fn indexable(&self) -> usize;
1252 /// Returns an element at an index, or `None` if the index is out of bounds
1253 fn idx(&mut self, index
: usize) -> Option
<Self::Item
>;
1256 /// An iterator that knows its exact length
1258 /// This trait is a helper for iterators like the vector iterator, so that
1259 /// it can support double-ended enumeration.
1261 /// `Iterator::size_hint` *must* return the exact size of the iterator.
1262 /// Note that the size must fit in `usize`.
1263 #[stable(feature = "rust1", since = "1.0.0")]
1264 pub trait ExactSizeIterator
: Iterator
{
1266 #[stable(feature = "rust1", since = "1.0.0")]
1267 /// Returns the exact length of the iterator.
1268 fn len(&self) -> usize {
1269 let (lower
, upper
) = self.size_hint();
1270 // Note: This assertion is overly defensive, but it checks the invariant
1271 // guaranteed by the trait. If this trait were rust-internal,
1272 // we could use debug_assert!; assert_eq! will check all Rust user
1273 // implementations too.
1274 assert_eq
!(upper
, Some(lower
));
1279 #[stable(feature = "rust1", since = "1.0.0")]
1280 impl<'a
, I
: ExactSizeIterator
+ ?Sized
> ExactSizeIterator
for &'a
mut I {}
1282 // All adaptors that preserve the size of the wrapped iterator are fine
1283 // Adaptors that may overflow in `size_hint` are not, i.e. `Chain`.
1284 #[stable(feature = "rust1", since = "1.0.0")]
1285 impl<I
> ExactSizeIterator
for Enumerate
<I
> where I
: ExactSizeIterator {}
1286 #[stable(feature = "rust1", since = "1.0.0")]
1287 impl<I
: ExactSizeIterator
, F
> ExactSizeIterator
for Inspect
<I
, F
> where
1290 #[stable(feature = "rust1", since = "1.0.0")]
1291 impl<I
> ExactSizeIterator
for Rev
<I
>
1292 where I
: ExactSizeIterator
+ DoubleEndedIterator {}
1293 #[stable(feature = "rust1", since = "1.0.0")]
1294 impl<B
, I
: ExactSizeIterator
, F
> ExactSizeIterator
for Map
<I
, F
> where
1295 F
: FnMut(I
::Item
) -> B
,
1297 #[stable(feature = "rust1", since = "1.0.0")]
1298 impl<A
, B
> ExactSizeIterator
for Zip
<A
, B
>
1299 where A
: ExactSizeIterator
, B
: ExactSizeIterator {}
1301 /// An double-ended iterator with the direction inverted
1303 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1304 #[stable(feature = "rust1", since = "1.0.0")]
1309 #[stable(feature = "rust1", since = "1.0.0")]
1310 impl<I
> Iterator
for Rev
<I
> where I
: DoubleEndedIterator
{
1311 type Item
= <I
as Iterator
>::Item
;
1314 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> { self.iter.next_back() }
1316 fn size_hint(&self) -> (usize, Option
<usize>) { self.iter.size_hint() }
1319 #[stable(feature = "rust1", since = "1.0.0")]
1320 impl<I
> DoubleEndedIterator
for Rev
<I
> where I
: DoubleEndedIterator
{
1322 fn next_back(&mut self) -> Option
<<I
as Iterator
>::Item
> { self.iter.next() }
1325 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
1326 #[allow(deprecated)]
1327 impl<I
> RandomAccessIterator
for Rev
<I
>
1328 where I
: DoubleEndedIterator
+ RandomAccessIterator
1331 fn indexable(&self) -> usize { self.iter.indexable() }
1333 fn idx(&mut self, index
: usize) -> Option
<<I
as Iterator
>::Item
> {
1334 let amt
= self.indexable();
1336 self.iter
.idx(amt
- index
- 1)
1343 /// `MinMaxResult` is an enum returned by `min_max`. See `Iterator::min_max` for
1345 #[derive(Clone, PartialEq, Debug)]
1346 #[unstable(feature = "iter_min_max",
1347 reason
= "unclear whether such a fine-grained result is widely useful")]
1348 #[deprecated(since = "1.3.0", reason = "has not proven itself")]
1349 #[allow(deprecated)]
1350 pub enum MinMaxResult
<T
> {
1354 /// Iterator with one element, so the minimum and maximum are the same
1357 /// More than one element in the iterator, the first element is not larger
1362 #[unstable(feature = "iter_min_max", reason = "type is unstable")]
1363 #[deprecated(since = "1.3.0", reason = "has not proven itself")]
1364 #[allow(deprecated)]
1365 impl<T
: Clone
> MinMaxResult
<T
> {
1366 /// `into_option` creates an `Option` of type `(T,T)`. The returned `Option`
1367 /// has variant `None` if and only if the `MinMaxResult` has variant
1368 /// `NoElements`. Otherwise variant `Some(x,y)` is returned where `x <= y`.
1369 /// If `MinMaxResult` has variant `OneElement(x)`, performing this operation
1370 /// will make one clone of `x`.
1375 /// #![feature(iter_min_max)]
1377 /// use std::iter::MinMaxResult::{self, NoElements, OneElement, MinMax};
1379 /// let r: MinMaxResult<i32> = NoElements;
1380 /// assert_eq!(r.into_option(), None);
1382 /// let r = OneElement(1);
1383 /// assert_eq!(r.into_option(), Some((1, 1)));
1385 /// let r = MinMax(1, 2);
1386 /// assert_eq!(r.into_option(), Some((1, 2)));
1388 pub fn into_option(self) -> Option
<(T
,T
)> {
1391 OneElement(x
) => Some((x
.clone(), x
)),
1392 MinMax(x
, y
) => Some((x
, y
))
1397 /// An iterator that clones the elements of an underlying iterator
1398 #[stable(feature = "iter_cloned", since = "1.1.0")]
1399 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1401 pub struct Cloned
<I
> {
1405 #[stable(feature = "rust1", since = "1.0.0")]
1406 impl<'a
, I
, T
: 'a
> Iterator
for Cloned
<I
>
1407 where I
: Iterator
<Item
=&'a T
>, T
: Clone
1411 fn next(&mut self) -> Option
<T
> {
1412 self.it
.next().cloned()
1415 fn size_hint(&self) -> (usize, Option
<usize>) {
1420 #[stable(feature = "rust1", since = "1.0.0")]
1421 impl<'a
, I
, T
: 'a
> DoubleEndedIterator
for Cloned
<I
>
1422 where I
: DoubleEndedIterator
<Item
=&'a T
>, T
: Clone
1424 fn next_back(&mut self) -> Option
<T
> {
1425 self.it
.next_back().cloned()
1429 #[stable(feature = "rust1", since = "1.0.0")]
1430 impl<'a
, I
, T
: 'a
> ExactSizeIterator
for Cloned
<I
>
1431 where I
: ExactSizeIterator
<Item
=&'a T
>, T
: Clone
1434 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
1435 #[allow(deprecated)]
1436 impl<'a
, I
, T
: 'a
> RandomAccessIterator
for Cloned
<I
>
1437 where I
: RandomAccessIterator
<Item
=&'a T
>, T
: Clone
1440 fn indexable(&self) -> usize {
1445 fn idx(&mut self, index
: usize) -> Option
<T
> {
1446 self.it
.idx(index
).cloned()
1450 /// An iterator that repeats endlessly
1452 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1453 #[stable(feature = "rust1", since = "1.0.0")]
1454 pub struct Cycle
<I
> {
1459 #[stable(feature = "rust1", since = "1.0.0")]
1460 impl<I
> Iterator
for Cycle
<I
> where I
: Clone
+ Iterator
{
1461 type Item
= <I
as Iterator
>::Item
;
1464 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> {
1465 match self.iter
.next() {
1466 None
=> { self.iter = self.orig.clone(); self.iter.next() }
1472 fn size_hint(&self) -> (usize, Option
<usize>) {
1473 // the cycle iterator is either empty or infinite
1474 match self.orig
.size_hint() {
1475 sz @
(0, Some(0)) => sz
,
1476 (0, _
) => (0, None
),
1477 _
=> (usize::MAX
, None
)
1482 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
1483 #[allow(deprecated)]
1484 impl<I
> RandomAccessIterator
for Cycle
<I
> where
1485 I
: Clone
+ RandomAccessIterator
,
1488 fn indexable(&self) -> usize {
1489 if self.orig
.indexable() > 0 {
1497 fn idx(&mut self, index
: usize) -> Option
<<I
as Iterator
>::Item
> {
1498 let liter
= self.iter
.indexable();
1499 let lorig
= self.orig
.indexable();
1502 } else if index
< liter
{
1503 self.iter
.idx(index
)
1505 self.orig
.idx((index
- liter
) % lorig
)
1510 /// An iterator that strings two iterators together
1512 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1513 #[stable(feature = "rust1", since = "1.0.0")]
1514 pub struct Chain
<A
, B
> {
1520 #[stable(feature = "rust1", since = "1.0.0")]
1521 impl<A
, B
> Iterator
for Chain
<A
, B
> where
1523 B
: Iterator
<Item
= A
::Item
>
1525 type Item
= A
::Item
;
1528 fn next(&mut self) -> Option
<A
::Item
> {
1532 match self.a
.next() {
1533 Some(x
) => return Some(x
),
1542 fn count(self) -> usize {
1543 (if !self.flag { self.a.count() }
else { 0 }
) + self.b
.count()
1547 fn nth(&mut self, mut n
: usize) -> Option
<A
::Item
> {
1549 for x
in self.a
.by_ref() {
1561 fn last(self) -> Option
<A
::Item
> {
1562 let a_last
= if self.flag { None }
else { self.a.last() }
;
1563 let b_last
= self.b
.last();
1568 fn size_hint(&self) -> (usize, Option
<usize>) {
1569 let (a_lower
, a_upper
) = self.a
.size_hint();
1570 let (b_lower
, b_upper
) = self.b
.size_hint();
1572 let lower
= a_lower
.saturating_add(b_lower
);
1574 let upper
= match (a_upper
, b_upper
) {
1575 (Some(x
), Some(y
)) => x
.checked_add(y
),
1583 #[stable(feature = "rust1", since = "1.0.0")]
1584 impl<A
, B
> DoubleEndedIterator
for Chain
<A
, B
> where
1585 A
: DoubleEndedIterator
,
1586 B
: DoubleEndedIterator
<Item
=A
::Item
>,
1589 fn next_back(&mut self) -> Option
<A
::Item
> {
1590 match self.b
.next_back() {
1592 None
=> self.a
.next_back()
1597 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
1598 #[allow(deprecated)]
1599 impl<A
, B
> RandomAccessIterator
for Chain
<A
, B
> where
1600 A
: RandomAccessIterator
,
1601 B
: RandomAccessIterator
<Item
= A
::Item
>,
1604 fn indexable(&self) -> usize {
1605 let (a
, b
) = (self.a
.indexable(), self.b
.indexable());
1610 fn idx(&mut self, index
: usize) -> Option
<A
::Item
> {
1611 let len
= self.a
.indexable();
1615 self.b
.idx(index
- len
)
1620 /// An iterator that iterates two other iterators simultaneously
1622 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1623 #[stable(feature = "rust1", since = "1.0.0")]
1624 pub struct Zip
<A
, B
> {
1629 #[stable(feature = "rust1", since = "1.0.0")]
1630 impl<A
, B
> Iterator
for Zip
<A
, B
> where A
: Iterator
, B
: Iterator
1632 type Item
= (A
::Item
, B
::Item
);
1635 fn next(&mut self) -> Option
<(A
::Item
, B
::Item
)> {
1636 self.a
.next().and_then(|x
| {
1637 self.b
.next().and_then(|y
| {
1644 fn size_hint(&self) -> (usize, Option
<usize>) {
1645 let (a_lower
, a_upper
) = self.a
.size_hint();
1646 let (b_lower
, b_upper
) = self.b
.size_hint();
1648 let lower
= cmp
::min(a_lower
, b_lower
);
1650 let upper
= match (a_upper
, b_upper
) {
1651 (Some(x
), Some(y
)) => Some(cmp
::min(x
,y
)),
1652 (Some(x
), None
) => Some(x
),
1653 (None
, Some(y
)) => Some(y
),
1654 (None
, None
) => None
1661 #[stable(feature = "rust1", since = "1.0.0")]
1662 impl<A
, B
> DoubleEndedIterator
for Zip
<A
, B
> where
1663 A
: DoubleEndedIterator
+ ExactSizeIterator
,
1664 B
: DoubleEndedIterator
+ ExactSizeIterator
,
1667 fn next_back(&mut self) -> Option
<(A
::Item
, B
::Item
)> {
1668 let a_sz
= self.a
.len();
1669 let b_sz
= self.b
.len();
1671 // Adjust a, b to equal length
1673 for _
in 0..a_sz
- b_sz { self.a.next_back(); }
1675 for _
in 0..b_sz
- a_sz { self.b.next_back(); }
1678 match (self.a
.next_back(), self.b
.next_back()) {
1679 (Some(x
), Some(y
)) => Some((x
, y
)),
1680 (None
, None
) => None
,
1681 _
=> unreachable
!(),
1686 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
1687 #[allow(deprecated)]
1688 impl<A
, B
> RandomAccessIterator
for Zip
<A
, B
> where
1689 A
: RandomAccessIterator
,
1690 B
: RandomAccessIterator
1693 fn indexable(&self) -> usize {
1694 cmp
::min(self.a
.indexable(), self.b
.indexable())
1698 fn idx(&mut self, index
: usize) -> Option
<(A
::Item
, B
::Item
)> {
1699 self.a
.idx(index
).and_then(|x
| {
1700 self.b
.idx(index
).and_then(|y
| {
1707 /// An iterator that maps the values of `iter` with `f`
1708 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1709 #[stable(feature = "rust1", since = "1.0.0")]
1711 pub struct Map
<I
, F
> {
1716 #[stable(feature = "rust1", since = "1.0.0")]
1717 impl<B
, I
: Iterator
, F
> Iterator
for Map
<I
, F
> where F
: FnMut(I
::Item
) -> B
{
1721 fn next(&mut self) -> Option
<B
> {
1722 self.iter
.next().map(|a
| (self.f
)(a
))
1726 fn size_hint(&self) -> (usize, Option
<usize>) {
1727 self.iter
.size_hint()
1731 #[stable(feature = "rust1", since = "1.0.0")]
1732 impl<B
, I
: DoubleEndedIterator
, F
> DoubleEndedIterator
for Map
<I
, F
> where
1733 F
: FnMut(I
::Item
) -> B
,
1736 fn next_back(&mut self) -> Option
<B
> {
1737 self.iter
.next_back().map(|a
| (self.f
)(a
))
1741 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
1742 #[allow(deprecated)]
1743 impl<B
, I
: RandomAccessIterator
, F
> RandomAccessIterator
for Map
<I
, F
> where
1744 F
: FnMut(I
::Item
) -> B
,
1747 fn indexable(&self) -> usize {
1748 self.iter
.indexable()
1752 fn idx(&mut self, index
: usize) -> Option
<B
> {
1753 self.iter
.idx(index
).map(|a
| (self.f
)(a
))
1757 /// An iterator that filters the elements of `iter` with `predicate`
1758 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1759 #[stable(feature = "rust1", since = "1.0.0")]
1761 pub struct Filter
<I
, P
> {
1766 #[stable(feature = "rust1", since = "1.0.0")]
1767 impl<I
: Iterator
, P
> Iterator
for Filter
<I
, P
> where P
: FnMut(&I
::Item
) -> bool
{
1768 type Item
= I
::Item
;
1771 fn next(&mut self) -> Option
<I
::Item
> {
1772 for x
in self.iter
.by_ref() {
1773 if (self.predicate
)(&x
) {
1781 fn size_hint(&self) -> (usize, Option
<usize>) {
1782 let (_
, upper
) = self.iter
.size_hint();
1783 (0, upper
) // can't know a lower bound, due to the predicate
1787 #[stable(feature = "rust1", since = "1.0.0")]
1788 impl<I
: DoubleEndedIterator
, P
> DoubleEndedIterator
for Filter
<I
, P
>
1789 where P
: FnMut(&I
::Item
) -> bool
,
1792 fn next_back(&mut self) -> Option
<I
::Item
> {
1793 for x
in self.iter
.by_ref().rev() {
1794 if (self.predicate
)(&x
) {
1802 /// An iterator that uses `f` to both filter and map elements from `iter`
1803 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1804 #[stable(feature = "rust1", since = "1.0.0")]
1806 pub struct FilterMap
<I
, F
> {
1811 #[stable(feature = "rust1", since = "1.0.0")]
1812 impl<B
, I
: Iterator
, F
> Iterator
for FilterMap
<I
, F
>
1813 where F
: FnMut(I
::Item
) -> Option
<B
>,
1818 fn next(&mut self) -> Option
<B
> {
1819 for x
in self.iter
.by_ref() {
1820 if let Some(y
) = (self.f
)(x
) {
1828 fn size_hint(&self) -> (usize, Option
<usize>) {
1829 let (_
, upper
) = self.iter
.size_hint();
1830 (0, upper
) // can't know a lower bound, due to the predicate
1834 #[stable(feature = "rust1", since = "1.0.0")]
1835 impl<B
, I
: DoubleEndedIterator
, F
> DoubleEndedIterator
for FilterMap
<I
, F
>
1836 where F
: FnMut(I
::Item
) -> Option
<B
>,
1839 fn next_back(&mut self) -> Option
<B
> {
1840 for x
in self.iter
.by_ref().rev() {
1841 if let Some(y
) = (self.f
)(x
) {
1849 /// An iterator that yields the current count and the element during iteration
1851 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1852 #[stable(feature = "rust1", since = "1.0.0")]
1853 pub struct Enumerate
<I
> {
1858 #[stable(feature = "rust1", since = "1.0.0")]
1859 impl<I
> Iterator
for Enumerate
<I
> where I
: Iterator
{
1860 type Item
= (usize, <I
as Iterator
>::Item
);
1862 /// # Overflow Behavior
1864 /// The method does no guarding against overflows, so enumerating more than
1865 /// `usize::MAX` elements either produces the wrong result or panics. If
1866 /// debug assertions are enabled, a panic is guaranteed.
1870 /// Might panic if the index of the element overflows a `usize`.
1872 fn next(&mut self) -> Option
<(usize, <I
as Iterator
>::Item
)> {
1873 self.iter
.next().map(|a
| {
1874 let ret
= (self.count
, a
);
1875 // Possible undefined overflow.
1882 fn size_hint(&self) -> (usize, Option
<usize>) {
1883 self.iter
.size_hint()
1887 fn nth(&mut self, n
: usize) -> Option
<(usize, I
::Item
)> {
1888 self.iter
.nth(n
).map(|a
| {
1889 let i
= self.count
+ n
;
1896 fn count(self) -> usize {
1901 #[stable(feature = "rust1", since = "1.0.0")]
1902 impl<I
> DoubleEndedIterator
for Enumerate
<I
> where
1903 I
: ExactSizeIterator
+ DoubleEndedIterator
1906 fn next_back(&mut self) -> Option
<(usize, <I
as Iterator
>::Item
)> {
1907 self.iter
.next_back().map(|a
| {
1908 let len
= self.iter
.len();
1909 // Can safely add, `ExactSizeIterator` promises that the number of
1910 // elements fits into a `usize`.
1911 (self.count
+ len
, a
)
1916 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
1917 #[allow(deprecated)]
1918 impl<I
> RandomAccessIterator
for Enumerate
<I
> where I
: RandomAccessIterator
{
1920 fn indexable(&self) -> usize {
1921 self.iter
.indexable()
1925 fn idx(&mut self, index
: usize) -> Option
<(usize, <I
as Iterator
>::Item
)> {
1926 // Can safely add, `ExactSizeIterator` (ancestor of
1927 // `RandomAccessIterator`) promises that the number of elements fits
1929 self.iter
.idx(index
).map(|a
| (self.count
+ index
, a
))
1933 /// An iterator with a `peek()` that returns an optional reference to the next element.
1934 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1935 #[stable(feature = "rust1", since = "1.0.0")]
1936 pub struct Peekable
<I
: Iterator
> {
1938 peeked
: Option
<I
::Item
>,
1941 impl<I
: Iterator
+ Clone
> Clone
for Peekable
<I
> where I
::Item
: Clone
{
1942 fn clone(&self) -> Peekable
<I
> {
1944 iter
: self.iter
.clone(),
1945 peeked
: self.peeked
.clone(),
1950 #[stable(feature = "rust1", since = "1.0.0")]
1951 impl<I
: Iterator
> Iterator
for Peekable
<I
> {
1952 type Item
= I
::Item
;
1955 fn next(&mut self) -> Option
<I
::Item
> {
1957 Some(_
) => self.peeked
.take(),
1958 None
=> self.iter
.next(),
1963 fn count(self) -> usize {
1964 (if self.peeked
.is_some() { 1 }
else { 0 }
) + self.iter
.count()
1968 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
1970 Some(_
) if n
== 0 => self.peeked
.take(),
1975 None
=> self.iter
.nth(n
)
1980 fn last(self) -> Option
<I
::Item
> {
1981 self.iter
.last().or(self.peeked
)
1985 fn size_hint(&self) -> (usize, Option
<usize>) {
1986 let (lo
, hi
) = self.iter
.size_hint();
1987 if self.peeked
.is_some() {
1988 let lo
= lo
.saturating_add(1);
1989 let hi
= hi
.and_then(|x
| x
.checked_add(1));
1997 #[stable(feature = "rust1", since = "1.0.0")]
1998 impl<I
: ExactSizeIterator
> ExactSizeIterator
for Peekable
<I
> {}
2000 #[stable(feature = "rust1", since = "1.0.0")]
2001 impl<I
: Iterator
> Peekable
<I
> {
2002 /// Returns a reference to the next element of the iterator with out
2003 /// advancing it, or None if the iterator is exhausted.
2005 #[stable(feature = "rust1", since = "1.0.0")]
2006 pub fn peek(&mut self) -> Option
<&I
::Item
> {
2007 if self.peeked
.is_none() {
2008 self.peeked
= self.iter
.next();
2011 Some(ref value
) => Some(value
),
2016 /// Checks whether peekable iterator is empty or not.
2018 pub fn is_empty(&mut self) -> bool
{
2019 self.peek().is_none()
2023 /// An iterator that rejects elements while `predicate` is true
2024 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2025 #[stable(feature = "rust1", since = "1.0.0")]
2027 pub struct SkipWhile
<I
, P
> {
2033 #[stable(feature = "rust1", since = "1.0.0")]
2034 impl<I
: Iterator
, P
> Iterator
for SkipWhile
<I
, P
>
2035 where P
: FnMut(&I
::Item
) -> bool
2037 type Item
= I
::Item
;
2040 fn next(&mut self) -> Option
<I
::Item
> {
2041 for x
in self.iter
.by_ref() {
2042 if self.flag
|| !(self.predicate
)(&x
) {
2051 fn size_hint(&self) -> (usize, Option
<usize>) {
2052 let (_
, upper
) = self.iter
.size_hint();
2053 (0, upper
) // can't know a lower bound, due to the predicate
2057 /// An iterator that only accepts elements while `predicate` is true
2058 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2059 #[stable(feature = "rust1", since = "1.0.0")]
2061 pub struct TakeWhile
<I
, P
> {
2067 #[stable(feature = "rust1", since = "1.0.0")]
2068 impl<I
: Iterator
, P
> Iterator
for TakeWhile
<I
, P
>
2069 where P
: FnMut(&I
::Item
) -> bool
2071 type Item
= I
::Item
;
2074 fn next(&mut self) -> Option
<I
::Item
> {
2078 self.iter
.next().and_then(|x
| {
2079 if (self.predicate
)(&x
) {
2090 fn size_hint(&self) -> (usize, Option
<usize>) {
2091 let (_
, upper
) = self.iter
.size_hint();
2092 (0, upper
) // can't know a lower bound, due to the predicate
2096 /// An iterator that skips over `n` elements of `iter`.
2098 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2099 #[stable(feature = "rust1", since = "1.0.0")]
2100 pub struct Skip
<I
> {
2105 #[stable(feature = "rust1", since = "1.0.0")]
2106 impl<I
> Iterator
for Skip
<I
> where I
: Iterator
{
2107 type Item
= <I
as Iterator
>::Item
;
2110 fn next(&mut self) -> Option
<I
::Item
> {
2116 self.iter
.nth(old_n
)
2121 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
2122 // Can't just add n + self.n due to overflow.
2126 let to_skip
= self.n
;
2129 if self.iter
.nth(to_skip
-1).is_none() {
2137 fn count(self) -> usize {
2138 self.iter
.count().saturating_sub(self.n
)
2142 fn last(mut self) -> Option
<I
::Item
> {
2146 let next
= self.next();
2148 // recurse. n should be 0.
2149 self.last().or(next
)
2157 fn size_hint(&self) -> (usize, Option
<usize>) {
2158 let (lower
, upper
) = self.iter
.size_hint();
2160 let lower
= lower
.saturating_sub(self.n
);
2161 let upper
= upper
.map(|x
| x
.saturating_sub(self.n
));
2167 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
2168 #[allow(deprecated)]
2169 impl<I
> RandomAccessIterator
for Skip
<I
> where I
: RandomAccessIterator
{
2171 fn indexable(&self) -> usize {
2172 self.iter
.indexable().saturating_sub(self.n
)
2176 fn idx(&mut self, index
: usize) -> Option
<<I
as Iterator
>::Item
> {
2177 if index
>= self.indexable() {
2180 self.iter
.idx(index
+ self.n
)
2185 #[stable(feature = "rust1", since = "1.0.0")]
2186 impl<I
> ExactSizeIterator
for Skip
<I
> where I
: ExactSizeIterator {}
2188 /// An iterator that only iterates over the first `n` iterations of `iter`.
2190 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2191 #[stable(feature = "rust1", since = "1.0.0")]
2192 pub struct Take
<I
> {
2197 #[stable(feature = "rust1", since = "1.0.0")]
2198 impl<I
> Iterator
for Take
<I
> where I
: Iterator
{
2199 type Item
= <I
as Iterator
>::Item
;
2202 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> {
2212 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
2218 self.iter
.nth(self.n
- 1);
2226 fn size_hint(&self) -> (usize, Option
<usize>) {
2227 let (lower
, upper
) = self.iter
.size_hint();
2229 let lower
= cmp
::min(lower
, self.n
);
2231 let upper
= match upper
{
2232 Some(x
) if x
< self.n
=> Some(x
),
2240 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
2241 #[allow(deprecated)]
2242 impl<I
> RandomAccessIterator
for Take
<I
> where I
: RandomAccessIterator
{
2244 fn indexable(&self) -> usize {
2245 cmp
::min(self.iter
.indexable(), self.n
)
2249 fn idx(&mut self, index
: usize) -> Option
<<I
as Iterator
>::Item
> {
2250 if index
>= self.n
{
2253 self.iter
.idx(index
)
2258 #[stable(feature = "rust1", since = "1.0.0")]
2259 impl<I
> ExactSizeIterator
for Take
<I
> where I
: ExactSizeIterator {}
2262 /// An iterator to maintain state while iterating another iterator
2263 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2264 #[stable(feature = "rust1", since = "1.0.0")]
2266 #[allow(deprecated)]
2267 pub struct Scan
<I
, St
, F
> {
2271 /// The current internal state to be passed to the closure next.
2272 #[unstable(feature = "scan_state",
2273 reason
= "public fields are otherwise rare in the stdlib")]
2274 #[deprecated(since = "1.3.0", reason = "unclear whether this is necessary")]
2278 #[stable(feature = "rust1", since = "1.0.0")]
2279 impl<B
, I
, St
, F
> Iterator
for Scan
<I
, St
, F
> where
2281 F
: FnMut(&mut St
, I
::Item
) -> Option
<B
>,
2286 #[allow(deprecated)]
2287 fn next(&mut self) -> Option
<B
> {
2288 self.iter
.next().and_then(|a
| (self.f
)(&mut self.state
, a
))
2292 fn size_hint(&self) -> (usize, Option
<usize>) {
2293 let (_
, upper
) = self.iter
.size_hint();
2294 (0, upper
) // can't know a lower bound, due to the scan function
2298 /// An iterator that maps each element to an iterator,
2299 /// and yields the elements of the produced iterators
2301 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2302 #[stable(feature = "rust1", since = "1.0.0")]
2304 pub struct FlatMap
<I
, U
: IntoIterator
, F
> {
2307 frontiter
: Option
<U
::IntoIter
>,
2308 backiter
: Option
<U
::IntoIter
>,
2311 #[stable(feature = "rust1", since = "1.0.0")]
2312 impl<I
: Iterator
, U
: IntoIterator
, F
> Iterator
for FlatMap
<I
, U
, F
>
2313 where F
: FnMut(I
::Item
) -> U
,
2315 type Item
= U
::Item
;
2318 fn next(&mut self) -> Option
<U
::Item
> {
2320 if let Some(ref mut inner
) = self.frontiter
{
2321 if let Some(x
) = inner
.by_ref().next() {
2325 match self.iter
.next().map(|x
| (self.f
)(x
)) {
2326 None
=> return self.backiter
.as_mut().and_then(|it
| it
.next()),
2327 next
=> self.frontiter
= next
.map(IntoIterator
::into_iter
),
2333 fn size_hint(&self) -> (usize, Option
<usize>) {
2334 let (flo
, fhi
) = self.frontiter
.as_ref().map_or((0, Some(0)), |it
| it
.size_hint());
2335 let (blo
, bhi
) = self.backiter
.as_ref().map_or((0, Some(0)), |it
| it
.size_hint());
2336 let lo
= flo
.saturating_add(blo
);
2337 match (self.iter
.size_hint(), fhi
, bhi
) {
2338 ((0, Some(0)), Some(a
), Some(b
)) => (lo
, a
.checked_add(b
)),
2344 #[stable(feature = "rust1", since = "1.0.0")]
2345 impl<I
: DoubleEndedIterator
, U
, F
> DoubleEndedIterator
for FlatMap
<I
, U
, F
> where
2346 F
: FnMut(I
::Item
) -> U
,
2348 U
::IntoIter
: DoubleEndedIterator
2351 fn next_back(&mut self) -> Option
<U
::Item
> {
2353 if let Some(ref mut inner
) = self.backiter
{
2354 if let Some(y
) = inner
.next_back() {
2358 match self.iter
.next_back().map(|x
| (self.f
)(x
)) {
2359 None
=> return self.frontiter
.as_mut().and_then(|it
| it
.next_back()),
2360 next
=> self.backiter
= next
.map(IntoIterator
::into_iter
),
2366 /// An iterator that yields `None` forever after the underlying iterator
2367 /// yields `None` once.
2369 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2370 #[stable(feature = "rust1", since = "1.0.0")]
2371 pub struct Fuse
<I
> {
2376 #[stable(feature = "rust1", since = "1.0.0")]
2377 impl<I
> Iterator
for Fuse
<I
> where I
: Iterator
{
2378 type Item
= <I
as Iterator
>::Item
;
2381 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> {
2385 let next
= self.iter
.next();
2386 self.done
= next
.is_none();
2392 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
2396 let nth
= self.iter
.nth(n
);
2397 self.done
= nth
.is_none();
2403 fn last(self) -> Option
<I
::Item
> {
2412 fn count(self) -> usize {
2421 fn size_hint(&self) -> (usize, Option
<usize>) {
2425 self.iter
.size_hint()
2430 #[stable(feature = "rust1", since = "1.0.0")]
2431 impl<I
> DoubleEndedIterator
for Fuse
<I
> where I
: DoubleEndedIterator
{
2433 fn next_back(&mut self) -> Option
<<I
as Iterator
>::Item
> {
2437 let next
= self.iter
.next_back();
2438 self.done
= next
.is_none();
2444 // Allow RandomAccessIterators to be fused without affecting random-access behavior
2445 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
2446 #[allow(deprecated)]
2447 impl<I
> RandomAccessIterator
for Fuse
<I
> where I
: RandomAccessIterator
{
2449 fn indexable(&self) -> usize {
2450 self.iter
.indexable()
2454 fn idx(&mut self, index
: usize) -> Option
<<I
as Iterator
>::Item
> {
2455 self.iter
.idx(index
)
2459 #[stable(feature = "rust1", since = "1.0.0")]
2460 impl<I
> ExactSizeIterator
for Fuse
<I
> where I
: ExactSizeIterator {}
2463 /// Resets the `Fuse` such that the next call to `.next()` or
2464 /// `.next_back()` will call the underlying iterator again even if it
2465 /// previously returned `None`.
2467 #[unstable(feature = "iter_reset_fuse", reason = "seems marginal")]
2468 #[deprecated(since = "1.3.0",
2469 reason
= "unusual for adaptors to have one-off methods")]
2470 pub fn reset_fuse(&mut self) {
2475 /// An iterator that calls a function with a reference to each
2476 /// element before yielding it.
2477 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2478 #[stable(feature = "rust1", since = "1.0.0")]
2480 pub struct Inspect
<I
, F
> {
2485 impl<I
: Iterator
, F
> Inspect
<I
, F
> where F
: FnMut(&I
::Item
) {
2487 fn do_inspect(&mut self, elt
: Option
<I
::Item
>) -> Option
<I
::Item
> {
2488 if let Some(ref a
) = elt
{
2496 #[stable(feature = "rust1", since = "1.0.0")]
2497 impl<I
: Iterator
, F
> Iterator
for Inspect
<I
, F
> where F
: FnMut(&I
::Item
) {
2498 type Item
= I
::Item
;
2501 fn next(&mut self) -> Option
<I
::Item
> {
2502 let next
= self.iter
.next();
2503 self.do_inspect(next
)
2507 fn size_hint(&self) -> (usize, Option
<usize>) {
2508 self.iter
.size_hint()
2512 #[stable(feature = "rust1", since = "1.0.0")]
2513 impl<I
: DoubleEndedIterator
, F
> DoubleEndedIterator
for Inspect
<I
, F
>
2514 where F
: FnMut(&I
::Item
),
2517 fn next_back(&mut self) -> Option
<I
::Item
> {
2518 let next
= self.iter
.next_back();
2519 self.do_inspect(next
)
2523 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
2524 #[allow(deprecated)]
2525 impl<I
: RandomAccessIterator
, F
> RandomAccessIterator
for Inspect
<I
, F
>
2526 where F
: FnMut(&I
::Item
),
2529 fn indexable(&self) -> usize {
2530 self.iter
.indexable()
2534 fn idx(&mut self, index
: usize) -> Option
<I
::Item
> {
2535 let element
= self.iter
.idx(index
);
2536 self.do_inspect(element
)
2540 /// An iterator that passes mutable state to a closure and yields the result.
2544 /// An iterator that yields sequential Fibonacci numbers, and stops on overflow.
2547 /// #![feature(iter_unfold)]
2548 /// use std::iter::Unfold;
2550 /// // This iterator will yield up to the last Fibonacci number before the max
2551 /// // value of `u32`. You can simply change `u32` to `u64` in this line if
2552 /// // you want higher values than that.
2553 /// let mut fibonacci = Unfold::new((Some(0u32), Some(1u32)),
2554 /// |&mut (ref mut x2, ref mut x1)| {
2555 /// // Attempt to get the next Fibonacci number
2556 /// // `x1` will be `None` if previously overflowed.
2557 /// let next = match (*x2, *x1) {
2558 /// (Some(x2), Some(x1)) => x2.checked_add(x1),
2562 /// // Shift left: ret <- x2 <- x1 <- next
2570 /// for i in fibonacci {
2571 /// println!("{}", i);
2574 #[unstable(feature = "iter_unfold")]
2576 #[deprecated(since = "1.2.0",
2577 reason
= "has not gained enough traction to retain its position \
2578 in the standard library")]
2579 #[allow(deprecated)]
2580 pub struct Unfold
<St
, F
> {
2582 /// Internal state that will be passed to the closure on the next iteration
2583 #[unstable(feature = "iter_unfold")]
2587 #[unstable(feature = "iter_unfold")]
2588 #[deprecated(since = "1.2.0",
2589 reason
= "has not gained enough traction to retain its position \
2590 in the standard library")]
2591 #[allow(deprecated)]
2592 impl<A
, St
, F
> Unfold
<St
, F
> where F
: FnMut(&mut St
) -> Option
<A
> {
2593 /// Creates a new iterator with the specified closure as the "iterator
2594 /// function" and an initial state to eventually pass to the closure
2596 pub fn new(initial_state
: St
, f
: F
) -> Unfold
<St
, F
> {
2599 state
: initial_state
2604 #[stable(feature = "rust1", since = "1.0.0")]
2605 #[allow(deprecated)]
2606 impl<A
, St
, F
> Iterator
for Unfold
<St
, F
> where F
: FnMut(&mut St
) -> Option
<A
> {
2610 fn next(&mut self) -> Option
<A
> {
2611 (self.f
)(&mut self.state
)
2615 fn size_hint(&self) -> (usize, Option
<usize>) {
2616 // no possible known bounds at this point
2621 /// Objects that can be stepped over in both directions.
2623 /// The `steps_between` function provides a way to efficiently compare
2624 /// two `Step` objects.
2625 #[unstable(feature = "step_trait",
2626 reason
= "likely to be replaced by finer-grained traits")]
2627 pub trait Step
: PartialOrd
{
2628 /// Steps `self` if possible.
2629 fn step(&self, by
: &Self) -> Option
<Self>;
2631 /// Returns the number of steps between two step objects. The count is
2632 /// inclusive of `start` and exclusive of `end`.
2634 /// Returns `None` if it is not possible to calculate `steps_between`
2635 /// without overflow.
2636 fn steps_between(start
: &Self, end
: &Self, by
: &Self) -> Option
<usize>;
2639 macro_rules
! step_impl_unsigned
{
2643 fn step(&self, by
: &$t
) -> Option
<$t
> {
2644 (*self).checked_add(*by
)
2647 #[allow(trivial_numeric_casts)]
2648 fn steps_between(start
: &$t
, end
: &$t
, by
: &$t
) -> Option
<usize> {
2649 if *by
== 0 { return None; }
2651 // Note: We assume $t <= usize here
2652 let diff
= (*end
- *start
) as usize;
2653 let by
= *by
as usize;
2666 macro_rules
! step_impl_signed
{
2670 fn step(&self, by
: &$t
) -> Option
<$t
> {
2671 (*self).checked_add(*by
)
2674 #[allow(trivial_numeric_casts)]
2675 fn steps_between(start
: &$t
, end
: &$t
, by
: &$t
) -> Option
<usize> {
2676 if *by
== 0 { return None; }
2683 // Note: We assume $t <= isize here
2684 // Use .wrapping_sub and cast to usize to compute the
2685 // difference that may not fit inside the range of isize.
2686 diff
= (*end
as isize).wrapping_sub(*start
as isize) as usize;
2687 by_u
= *by
as usize;
2692 diff
= (*start
as isize).wrapping_sub(*end
as isize) as usize;
2693 by_u
= (*by
as isize).wrapping_mul(-1) as usize;
2695 if diff
% by_u
> 0 {
2696 Some(diff
/ by_u
+ 1)
2705 macro_rules
! step_impl_no_between
{
2709 fn step(&self, by
: &$t
) -> Option
<$t
> {
2710 (*self).checked_add(*by
)
2713 fn steps_between(_a
: &$t
, _b
: &$t
, _by
: &$t
) -> Option
<usize> {
2720 step_impl_unsigned
!(usize u8 u16 u32);
2721 step_impl_signed
!(isize i8 i16 i32);
2722 #[cfg(target_pointer_width = "64")]
2723 step_impl_unsigned
!(u64);
2724 #[cfg(target_pointer_width = "64")]
2725 step_impl_signed
!(i64);
2726 #[cfg(target_pointer_width = "32")]
2727 step_impl_no_between
!(u64 i64);
2729 /// An adapter for stepping range iterators by a custom amount.
2731 /// The resulting iterator handles overflow by stopping. The `A`
2732 /// parameter is the type being iterated over, while `R` is the range
2733 /// type (usually one of `std::ops::{Range, RangeFrom}`.
2735 #[unstable(feature = "step_by", reason = "recent addition")]
2736 pub struct StepBy
<A
, R
> {
2741 impl<A
: Step
> RangeFrom
<A
> {
2742 /// Creates an iterator starting at the same point, but stepping by
2743 /// the given amount at each iteration.
2748 /// for i in (0u8..).step_by(2) {
2749 /// println!("{}", i);
2753 /// This prints all even `u8` values.
2754 #[unstable(feature = "step_by", reason = "recent addition")]
2755 pub fn step_by(self, by
: A
) -> StepBy
<A
, Self> {
2763 #[allow(deprecated)]
2764 impl<A
: Step
> ops
::Range
<A
> {
2765 /// Creates an iterator with the same range, but stepping by the
2766 /// given amount at each iteration.
2768 /// The resulting iterator handles overflow by stopping.
2773 /// #![feature(step_by)]
2775 /// for i in (0..10).step_by(2) {
2776 /// println!("{}", i);
2789 #[unstable(feature = "step_by", reason = "recent addition")]
2790 pub fn step_by(self, by
: A
) -> StepBy
<A
, Self> {
2798 #[stable(feature = "rust1", since = "1.0.0")]
2799 impl<A
> Iterator
for StepBy
<A
, RangeFrom
<A
>> where
2801 for<'a
> &'a A
: Add
<&'a A
, Output
= A
>
2806 fn next(&mut self) -> Option
<A
> {
2807 let mut n
= &self.range
.start
+ &self.step_by
;
2808 mem
::swap(&mut n
, &mut self.range
.start
);
2813 fn size_hint(&self) -> (usize, Option
<usize>) {
2814 (usize::MAX
, None
) // Too bad we can't specify an infinite lower bound
2818 /// An iterator over the range [start, stop]
2820 #[unstable(feature = "range_inclusive",
2821 reason
= "likely to be replaced by range notation and adapters")]
2822 pub struct RangeInclusive
<A
> {
2823 range
: ops
::Range
<A
>,
2827 /// Returns an iterator over the range [start, stop].
2829 #[unstable(feature = "range_inclusive",
2830 reason
= "likely to be replaced by range notation and adapters")]
2831 pub fn range_inclusive
<A
>(start
: A
, stop
: A
) -> RangeInclusive
<A
>
2832 where A
: Step
+ One
+ Clone
2840 #[unstable(feature = "range_inclusive",
2841 reason
= "likely to be replaced by range notation and adapters")]
2842 impl<A
> Iterator
for RangeInclusive
<A
> where
2843 A
: PartialEq
+ Step
+ One
+ Clone
,
2844 for<'a
> &'a A
: Add
<&'a A
, Output
= A
>
2849 fn next(&mut self) -> Option
<A
> {
2850 self.range
.next().or_else(|| {
2851 if !self.done
&& self.range
.start
== self.range
.end
{
2853 Some(self.range
.end
.clone())
2861 fn size_hint(&self) -> (usize, Option
<usize>) {
2862 let (lo
, hi
) = self.range
.size_hint();
2866 let lo
= lo
.saturating_add(1);
2867 let hi
= hi
.and_then(|x
| x
.checked_add(1));
2873 #[unstable(feature = "range_inclusive",
2874 reason
= "likely to be replaced by range notation and adapters")]
2875 impl<A
> DoubleEndedIterator
for RangeInclusive
<A
> where
2876 A
: PartialEq
+ Step
+ One
+ Clone
,
2877 for<'a
> &'a A
: Add
<&'a A
, Output
= A
>,
2878 for<'a
> &'a A
: Sub
<Output
=A
>
2881 fn next_back(&mut self) -> Option
<A
> {
2882 if self.range
.end
> self.range
.start
{
2883 let result
= self.range
.end
.clone();
2884 self.range
.end
= &self.range
.end
- &A
::one();
2886 } else if !self.done
&& self.range
.start
== self.range
.end
{
2888 Some(self.range
.end
.clone())
2895 #[stable(feature = "rust1", since = "1.0.0")]
2896 #[allow(deprecated)]
2897 impl<A
: Step
+ Zero
+ Clone
> Iterator
for StepBy
<A
, ops
::Range
<A
>> {
2901 fn next(&mut self) -> Option
<A
> {
2902 let rev
= self.step_by
< A
::zero();
2903 if (rev
&& self.range
.start
> self.range
.end
) ||
2904 (!rev
&& self.range
.start
< self.range
.end
)
2906 match self.range
.start
.step(&self.step_by
) {
2908 mem
::swap(&mut self.range
.start
, &mut n
);
2912 let mut n
= self.range
.end
.clone();
2913 mem
::swap(&mut self.range
.start
, &mut n
);
2923 fn size_hint(&self) -> (usize, Option
<usize>) {
2924 match Step
::steps_between(&self.range
.start
,
2927 Some(hint
) => (hint
, Some(hint
)),
2933 macro_rules
! range_exact_iter_impl
{
2935 #[stable(feature = "rust1", since = "1.0.0")]
2936 impl ExactSizeIterator
for ops
::Range
<$t
> { }
2940 #[stable(feature = "rust1", since = "1.0.0")]
2941 #[allow(deprecated)]
2942 impl<A
: Step
+ One
> Iterator
for ops
::Range
<A
> where
2943 for<'a
> &'a A
: Add
<&'a A
, Output
= A
>
2948 fn next(&mut self) -> Option
<A
> {
2949 if self.start
< self.end
{
2950 let mut n
= &self.start
+ &A
::one();
2951 mem
::swap(&mut n
, &mut self.start
);
2959 fn size_hint(&self) -> (usize, Option
<usize>) {
2960 match Step
::steps_between(&self.start
, &self.end
, &A
::one()) {
2961 Some(hint
) => (hint
, Some(hint
)),
2967 // Ranges of u64 and i64 are excluded because they cannot guarantee having
2968 // a length <= usize::MAX, which is required by ExactSizeIterator.
2969 range_exact_iter_impl
!(usize u8 u16 u32 isize i8 i16 i32);
2971 #[stable(feature = "rust1", since = "1.0.0")]
2972 #[allow(deprecated)]
2973 impl<A
: Step
+ One
+ Clone
> DoubleEndedIterator
for ops
::Range
<A
> where
2974 for<'a
> &'a A
: Add
<&'a A
, Output
= A
>,
2975 for<'a
> &'a A
: Sub
<&'a A
, Output
= A
>
2978 fn next_back(&mut self) -> Option
<A
> {
2979 if self.start
< self.end
{
2980 self.end
= &self.end
- &A
::one();
2981 Some(self.end
.clone())
2988 #[stable(feature = "rust1", since = "1.0.0")]
2989 #[allow(deprecated)]
2990 impl<A
: Step
+ One
> Iterator
for ops
::RangeFrom
<A
> where
2991 for<'a
> &'a A
: Add
<&'a A
, Output
= A
>
2996 fn next(&mut self) -> Option
<A
> {
2997 let mut n
= &self.start
+ &A
::one();
2998 mem
::swap(&mut n
, &mut self.start
);
3003 /// An iterator that repeats an element endlessly
3005 #[stable(feature = "rust1", since = "1.0.0")]
3006 pub struct Repeat
<A
> {
3010 #[stable(feature = "rust1", since = "1.0.0")]
3011 impl<A
: Clone
> Iterator
for Repeat
<A
> {
3015 fn next(&mut self) -> Option
<A
> { Some(self.element.clone()) }
3017 fn size_hint(&self) -> (usize, Option
<usize>) { (usize::MAX, None) }
3020 #[stable(feature = "rust1", since = "1.0.0")]
3021 impl<A
: Clone
> DoubleEndedIterator
for Repeat
<A
> {
3023 fn next_back(&mut self) -> Option
<A
> { Some(self.element.clone()) }
3026 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
3027 #[allow(deprecated)]
3028 impl<A
: Clone
> RandomAccessIterator
for Repeat
<A
> {
3030 fn indexable(&self) -> usize { usize::MAX }
3032 fn idx(&mut self, _
: usize) -> Option
<A
> { Some(self.element.clone()) }
3035 type IterateState
<T
, F
> = (F
, Option
<T
>, bool
);
3037 /// An iterator that repeatedly applies a given function, starting
3038 /// from a given seed value.
3039 #[unstable(feature = "iter_iterate")]
3040 #[deprecated(since = "1.2.0",
3041 reason
= "has not gained enough traction to retain its position \
3042 in the standard library")]
3043 #[allow(deprecated)]
3044 pub type Iterate
<T
, F
> = Unfold
<IterateState
<T
, F
>, fn(&mut IterateState
<T
, F
>) -> Option
<T
>>;
3046 /// Creates a new iterator that produces an infinite sequence of
3047 /// repeated applications of the given function `f`.
3048 #[unstable(feature = "iter_iterate")]
3049 #[deprecated(since = "1.2.0",
3050 reason
= "has not gained enough traction to retain its position \
3051 in the standard library")]
3052 #[allow(deprecated)]
3053 pub fn iterate
<T
, F
>(seed
: T
, f
: F
) -> Iterate
<T
, F
> where
3057 fn next
<T
, F
>(st
: &mut IterateState
<T
, F
>) -> Option
<T
> where
3061 let &mut (ref mut f
, ref mut val
, ref mut first
) = st
;
3064 } else if let Some(x
) = val
.take() {
3065 *val
= Some((*f
)(x
))
3070 // coerce to a fn pointer
3071 let next
: fn(&mut IterateState
<T
,F
>) -> Option
<T
> = next
;
3073 Unfold
::new((f
, Some(seed
), true), next
)
3076 /// Creates a new iterator that endlessly repeats the element `elt`.
3078 #[stable(feature = "rust1", since = "1.0.0")]
3079 pub fn repeat
<T
: Clone
>(elt
: T
) -> Repeat
<T
> {
3080 Repeat{element: elt}
3083 /// An iterator that yields nothing.
3084 #[stable(feature = "iter_empty", since = "1.2.0")]
3085 pub struct Empty
<T
>(marker
::PhantomData
<T
>);
3087 #[stable(feature = "iter_empty", since = "1.2.0")]
3088 impl<T
> Iterator
for Empty
<T
> {
3091 fn next(&mut self) -> Option
<T
> {
3095 fn size_hint(&self) -> (usize, Option
<usize>){
3100 #[stable(feature = "iter_empty", since = "1.2.0")]
3101 impl<T
> DoubleEndedIterator
for Empty
<T
> {
3102 fn next_back(&mut self) -> Option
<T
> {
3107 #[stable(feature = "iter_empty", since = "1.2.0")]
3108 impl<T
> ExactSizeIterator
for Empty
<T
> {
3109 fn len(&self) -> usize {
3114 // not #[derive] because that adds a Clone bound on T,
3115 // which isn't necessary.
3116 #[stable(feature = "iter_empty", since = "1.2.0")]
3117 impl<T
> Clone
for Empty
<T
> {
3118 fn clone(&self) -> Empty
<T
> {
3119 Empty(marker
::PhantomData
)
3123 // not #[derive] because that adds a Default bound on T,
3124 // which isn't necessary.
3125 #[stable(feature = "iter_empty", since = "1.2.0")]
3126 impl<T
> Default
for Empty
<T
> {
3127 fn default() -> Empty
<T
> {
3128 Empty(marker
::PhantomData
)
3132 /// Creates an iterator that yields nothing.
3133 #[stable(feature = "iter_empty", since = "1.2.0")]
3134 pub fn empty
<T
>() -> Empty
<T
> {
3135 Empty(marker
::PhantomData
)
3138 /// An iterator that yields an element exactly once.
3140 #[stable(feature = "iter_once", since = "1.2.0")]
3141 pub struct Once
<T
> {
3142 inner
: ::option
::IntoIter
<T
>
3145 #[stable(feature = "iter_once", since = "1.2.0")]
3146 impl<T
> Iterator
for Once
<T
> {
3149 fn next(&mut self) -> Option
<T
> {
3153 fn size_hint(&self) -> (usize, Option
<usize>) {
3154 self.inner
.size_hint()
3158 #[stable(feature = "iter_once", since = "1.2.0")]
3159 impl<T
> DoubleEndedIterator
for Once
<T
> {
3160 fn next_back(&mut self) -> Option
<T
> {
3161 self.inner
.next_back()
3165 #[stable(feature = "iter_once", since = "1.2.0")]
3166 impl<T
> ExactSizeIterator
for Once
<T
> {
3167 fn len(&self) -> usize {
3172 /// Creates an iterator that yields an element exactly once.
3173 #[stable(feature = "iter_once", since = "1.2.0")]
3174 pub fn once
<T
>(value
: T
) -> Once
<T
> {
3175 Once { inner: Some(value).into_iter() }
3178 /// Functions for lexicographical ordering of sequences.
3180 /// Lexicographical ordering through `<`, `<=`, `>=`, `>` requires
3181 /// that the elements implement both `PartialEq` and `PartialOrd`.
3183 /// If two sequences are equal up until the point where one ends,
3184 /// the shorter sequence compares less.
3185 #[unstable(feature = "iter_order", reason = "needs review and revision")]
3188 use cmp
::{Eq, Ord, PartialOrd, PartialEq}
;
3189 use cmp
::Ordering
::{Equal, Less, Greater}
;
3191 use option
::Option
::{Some, None}
;
3192 use super::Iterator
;
3194 /// Compare `a` and `b` for equality using `Eq`
3195 pub fn equals
<A
, L
, R
>(mut a
: L
, mut b
: R
) -> bool
where
3197 L
: Iterator
<Item
=A
>,
3198 R
: Iterator
<Item
=A
>,
3201 match (a
.next(), b
.next()) {
3202 (None
, None
) => return true,
3203 (None
, _
) | (_
, None
) => return false,
3204 (Some(x
), Some(y
)) => if x
!= y { return false }
,
3209 /// Order `a` and `b` lexicographically using `Ord`
3210 pub fn cmp
<A
, L
, R
>(mut a
: L
, mut b
: R
) -> cmp
::Ordering
where
3212 L
: Iterator
<Item
=A
>,
3213 R
: Iterator
<Item
=A
>,
3216 match (a
.next(), b
.next()) {
3217 (None
, None
) => return Equal
,
3218 (None
, _
) => return Less
,
3219 (_
, None
) => return Greater
,
3220 (Some(x
), Some(y
)) => match x
.cmp(&y
) {
3222 non_eq
=> return non_eq
,
3228 /// Order `a` and `b` lexicographically using `PartialOrd`
3229 pub fn partial_cmp
<L
: Iterator
, R
: Iterator
>(mut a
: L
, mut b
: R
) -> Option
<cmp
::Ordering
> where
3230 L
::Item
: PartialOrd
<R
::Item
>
3233 match (a
.next(), b
.next()) {
3234 (None
, None
) => return Some(Equal
),
3235 (None
, _
) => return Some(Less
),
3236 (_
, None
) => return Some(Greater
),
3237 (Some(x
), Some(y
)) => match x
.partial_cmp(&y
) {
3239 non_eq
=> return non_eq
,
3245 /// Compare `a` and `b` for equality (Using partial equality, `PartialEq`)
3246 pub fn eq
<L
: Iterator
, R
: Iterator
>(mut a
: L
, mut b
: R
) -> bool
where
3247 L
::Item
: PartialEq
<R
::Item
>,
3250 match (a
.next(), b
.next()) {
3251 (None
, None
) => return true,
3252 (None
, _
) | (_
, None
) => return false,
3253 (Some(x
), Some(y
)) => if !x
.eq(&y
) { return false }
,
3258 /// Compares `a` and `b` for nonequality (Using partial equality, `PartialEq`)
3259 pub fn ne
<L
: Iterator
, R
: Iterator
>(mut a
: L
, mut b
: R
) -> bool
where
3260 L
::Item
: PartialEq
<R
::Item
>,
3263 match (a
.next(), b
.next()) {
3264 (None
, None
) => return false,
3265 (None
, _
) | (_
, None
) => return true,
3266 (Some(x
), Some(y
)) => if x
.ne(&y
) { return true }
,
3271 /// Returns `a` < `b` lexicographically (Using partial order, `PartialOrd`)
3272 pub fn lt
<L
: Iterator
, R
: Iterator
>(mut a
: L
, mut b
: R
) -> bool
where
3273 L
::Item
: PartialOrd
<R
::Item
>,
3276 match (a
.next(), b
.next()) {
3277 (None
, None
) => return false,
3278 (None
, _
) => return true,
3279 (_
, None
) => return false,
3280 (Some(x
), Some(y
)) => if x
.ne(&y
) { return x.lt(&y) }
,
3285 /// Returns `a` <= `b` lexicographically (Using partial order, `PartialOrd`)
3286 pub fn le
<L
: Iterator
, R
: Iterator
>(mut a
: L
, mut b
: R
) -> bool
where
3287 L
::Item
: PartialOrd
<R
::Item
>,
3290 match (a
.next(), b
.next()) {
3291 (None
, None
) => return true,
3292 (None
, _
) => return true,
3293 (_
, None
) => return false,
3294 (Some(x
), Some(y
)) => if x
.ne(&y
) { return x.le(&y) }
,
3299 /// Returns `a` > `b` lexicographically (Using partial order, `PartialOrd`)
3300 pub fn gt
<L
: Iterator
, R
: Iterator
>(mut a
: L
, mut b
: R
) -> bool
where
3301 L
::Item
: PartialOrd
<R
::Item
>,
3304 match (a
.next(), b
.next()) {
3305 (None
, None
) => return false,
3306 (None
, _
) => return false,
3307 (_
, None
) => return true,
3308 (Some(x
), Some(y
)) => if x
.ne(&y
) { return x.gt(&y) }
,
3313 /// Returns `a` >= `b` lexicographically (Using partial order, `PartialOrd`)
3314 pub fn ge
<L
: Iterator
, R
: Iterator
>(mut a
: L
, mut b
: R
) -> bool
where
3315 L
::Item
: PartialOrd
<R
::Item
>,
3318 match (a
.next(), b
.next()) {
3319 (None
, None
) => return true,
3320 (None
, _
) => return false,
3321 (_
, None
) => return true,
3322 (Some(x
), Some(y
)) => if x
.ne(&y
) { return x.ge(&y) }
,