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 applied to any
55 //! iterator over any type.
57 #![stable(feature = "rust1", since = "1.0.0")]
59 use self::MinMaxResult
::*;
63 use cmp
::{Ord, PartialOrd, PartialEq}
;
68 use ops
::{self, Add, Sub, FnMut, Mul, RangeFrom}
;
69 use option
::Option
::{self, Some, None}
;
73 fn _assert_is_object_safe(_
: &Iterator
<Item
=()>) {}
75 /// An interface for dealing with "external iterators". These types of iterators
76 /// can be resumed at any time as all state is stored internally as opposed to
77 /// being located on the call stack.
79 /// The Iterator protocol states that an iterator yields a (potentially-empty,
80 /// potentially-infinite) sequence of values, and returns `None` to signal that
81 /// it's finished. The Iterator protocol does not define behavior after `None`
82 /// is returned. A concrete Iterator implementation may choose to behave however
83 /// it wishes, either by returning `None` infinitely, or by doing something
86 #[stable(feature = "rust1", since = "1.0.0")]
87 #[rustc_on_unimplemented = "`{Self}` is not an iterator; maybe try calling \
88 `.iter()` or a similar method"]
90 /// The type of the elements being iterated
91 #[stable(feature = "rust1", since = "1.0.0")]
94 /// Advances the iterator and returns the next value. Returns `None` when the
96 #[stable(feature = "rust1", since = "1.0.0")]
97 fn next(&mut self) -> Option
<Self::Item
>;
99 /// Returns a lower and upper bound on the remaining length of the iterator.
101 /// An upper bound of `None` means either there is no known upper bound, or
102 /// the upper bound does not fit within a `usize`.
104 #[stable(feature = "rust1", since = "1.0.0")]
105 fn size_hint(&self) -> (usize, Option
<usize>) { (0, None) }
107 /// Counts the number of elements in this iterator.
109 /// # Overflow Behavior
111 /// The method does no guarding against overflows, so counting elements of
112 /// an iterator with more than `usize::MAX` elements either produces the
113 /// wrong result or panics. If debug assertions are enabled, a panic is
118 /// This functions might panic if the iterator has more than `usize::MAX`
124 /// let a = [1, 2, 3, 4, 5];
125 /// assert_eq!(a.iter().count(), 5);
128 #[stable(feature = "rust1", since = "1.0.0")]
129 fn count(self) -> usize where Self: Sized
{
131 self.fold(0, |cnt
, _
| cnt
+ 1)
134 /// Loops through the entire iterator, returning the last element.
139 /// let a = [1, 2, 3, 4, 5];
140 /// assert_eq!(a.iter().last(), Some(&5));
143 #[stable(feature = "rust1", since = "1.0.0")]
144 fn last(self) -> Option
<Self::Item
> where Self: Sized
{
146 for x
in self { last = Some(x); }
150 /// Loops through `n` iterations, returning the `n`th element of the
156 /// let a = [1, 2, 3, 4, 5];
157 /// let mut it = a.iter();
158 /// assert_eq!(it.nth(2), Some(&3));
159 /// assert_eq!(it.nth(2), None);
162 #[stable(feature = "rust1", since = "1.0.0")]
163 fn nth(&mut self, mut n
: usize) -> Option
<Self::Item
> where Self: Sized
{
164 for x
in self.by_ref() {
165 if n
== 0 { return Some(x) }
171 /// Chain this iterator with another, returning a new iterator that will
172 /// finish iterating over the current iterator, and then iterate
173 /// over the other specified iterator.
180 /// let mut it = a.iter().chain(b.iter());
181 /// assert_eq!(it.next(), Some(&0));
182 /// assert_eq!(it.next(), Some(&1));
183 /// assert!(it.next().is_none());
186 #[stable(feature = "rust1", since = "1.0.0")]
187 fn chain
<U
>(self, other
: U
) -> Chain
<Self, U
::IntoIter
> where
188 Self: Sized
, U
: IntoIterator
<Item
=Self::Item
>,
190 Chain{a: self, b: other.into_iter(), flag: false}
193 /// Creates an iterator that iterates over both this and the specified
194 /// iterators simultaneously, yielding the two elements as pairs. When
195 /// either iterator returns `None`, all further invocations of `next()`
196 /// will return `None`.
203 /// let mut it = a.iter().zip(b.iter());
204 /// assert_eq!(it.next(), Some((&0, &1)));
205 /// assert!(it.next().is_none());
208 /// `zip` can provide similar functionality to `enumerate`:
211 /// for pair in "foo".chars().enumerate() {
212 /// println!("{:?}", pair);
215 /// for pair in (0..).zip("foo".chars()) {
216 /// println!("{:?}", pair);
220 /// both produce the same output.
222 #[stable(feature = "rust1", since = "1.0.0")]
223 fn zip
<U
>(self, other
: U
) -> Zip
<Self, U
::IntoIter
> where
224 Self: Sized
, U
: IntoIterator
226 Zip{a: self, b: other.into_iter()}
229 /// Creates a new iterator that will apply the specified function to each
230 /// element returned by the first, yielding the mapped element instead.
236 /// let mut it = a.iter().map(|&x| 2 * x);
237 /// assert_eq!(it.next(), Some(2));
238 /// assert_eq!(it.next(), Some(4));
239 /// assert!(it.next().is_none());
242 #[stable(feature = "rust1", since = "1.0.0")]
243 fn map
<B
, F
>(self, f
: F
) -> Map
<Self, F
> where
244 Self: Sized
, F
: FnMut(Self::Item
) -> B
,
246 Map{iter: self, f: f}
249 /// Creates an iterator that applies the predicate to each element returned
250 /// by this iterator. The only elements that will be yielded are those that
251 /// make the predicate evaluate to `true`.
257 /// let mut it = a.iter().filter(|&x| *x > 1);
258 /// assert_eq!(it.next(), Some(&2));
259 /// assert!(it.next().is_none());
262 #[stable(feature = "rust1", since = "1.0.0")]
263 fn filter
<P
>(self, predicate
: P
) -> Filter
<Self, P
> where
264 Self: Sized
, P
: FnMut(&Self::Item
) -> bool
,
266 Filter{iter: self, predicate: predicate}
269 /// Creates an iterator that both filters and maps elements.
270 /// If the specified function returns `None`, the element is skipped.
271 /// Otherwise the option is unwrapped and the new value is yielded.
277 /// let mut it = a.iter().filter_map(|&x| if x > 1 {Some(2 * x)} else {None});
278 /// assert_eq!(it.next(), Some(4));
279 /// assert!(it.next().is_none());
282 #[stable(feature = "rust1", since = "1.0.0")]
283 fn filter_map
<B
, F
>(self, f
: F
) -> FilterMap
<Self, F
> where
284 Self: Sized
, F
: FnMut(Self::Item
) -> Option
<B
>,
286 FilterMap { iter: self, f: f }
289 /// Creates an iterator that yields pairs `(i, val)` where `i` is the
290 /// current index of iteration and `val` is the value returned by the
293 /// `enumerate` keeps its count as a `usize`. If you want to count by a
294 /// different sized integer, the `zip` function provides similar
297 /// # Overflow Behavior
299 /// The method does no guarding against overflows, so enumerating more than
300 /// `usize::MAX` elements either produces the wrong result or panics. If
301 /// debug assertions are enabled, a panic is guaranteed.
305 /// The returned iterator might panic if the to-be-returned index would
306 /// overflow a `usize`.
311 /// let a = [100, 200];
312 /// let mut it = a.iter().enumerate();
313 /// assert_eq!(it.next(), Some((0, &100)));
314 /// assert_eq!(it.next(), Some((1, &200)));
315 /// assert!(it.next().is_none());
318 #[stable(feature = "rust1", since = "1.0.0")]
319 fn enumerate(self) -> Enumerate
<Self> where Self: Sized
{
320 Enumerate { iter: self, count: 0 }
323 /// Creates an iterator that has a `.peek()` method
324 /// that returns an optional reference to the next element.
329 /// # #![feature(core)]
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")]
449 fn scan
<St
, B
, F
>(self, initial_state
: St
, f
: F
) -> Scan
<Self, St
, F
>
450 where Self: Sized
, F
: FnMut(&mut St
, Self::Item
) -> Option
<B
>,
452 Scan{iter: self, f: f, state: initial_state}
455 /// Creates an iterator that maps each element to an iterator,
456 /// and yields the elements of the produced iterators.
461 /// # #![feature(core)]
463 /// let ys = [0, 1, 0, 1, 2];
464 /// let it = xs.iter().flat_map(|&x| (0..).take(x));
465 /// // Check that `it` has the same elements as `ys`
466 /// for (i, x) in it.enumerate() {
467 /// assert_eq!(x, ys[i]);
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 /// # #![feature(core)]
520 /// let a = [1, 4, 2, 3, 8, 9, 6];
521 /// let sum: i32 = a.iter()
523 /// .inspect(|&x| println!("filtering {}", x))
524 /// .filter(|&x| x % 2 == 0)
525 /// .inspect(|&x| println!("{} made it through", x))
527 /// println!("{}", sum);
530 #[stable(feature = "rust1", since = "1.0.0")]
531 fn inspect
<F
>(self, f
: F
) -> Inspect
<Self, F
> where
532 Self: Sized
, F
: FnMut(&Self::Item
),
534 Inspect{iter: self, f: f}
537 /// Creates a wrapper around a mutable reference to the iterator.
539 /// This is useful to allow applying iterator adaptors while still
540 /// retaining ownership of the original iterator value.
545 /// let mut it = 0..10;
546 /// // sum the first five values
547 /// let partial_sum = it.by_ref().take(5).fold(0, |a, b| a + b);
548 /// assert_eq!(partial_sum, 10);
549 /// assert_eq!(it.next(), Some(5));
551 #[stable(feature = "rust1", since = "1.0.0")]
552 fn by_ref(&mut self) -> &mut Self where Self: Sized { self }
554 /// Loops through the entire iterator, collecting all of the elements into
555 /// a container implementing `FromIterator`.
560 /// let expected = [1, 2, 3, 4, 5];
561 /// let actual: Vec<_> = expected.iter().cloned().collect();
562 /// assert_eq!(actual, expected);
565 #[stable(feature = "rust1", since = "1.0.0")]
566 fn collect
<B
: FromIterator
<Self::Item
>>(self) -> B
where Self: Sized
{
567 FromIterator
::from_iter(self)
570 /// Loops through the entire iterator, collecting all of the elements into
571 /// one of two containers, depending on a predicate. The elements of the
572 /// first container satisfy the predicate, while the elements of the second
576 /// # #![feature(core)]
577 /// let vec = vec![1, 2, 3, 4];
578 /// let (even, odd): (Vec<_>, Vec<_>) = vec.into_iter().partition(|&n| n % 2 == 0);
579 /// assert_eq!(even, [2, 4]);
580 /// assert_eq!(odd, [1, 3]);
582 #[stable(feature = "rust1", since = "1.0.0")]
583 fn partition
<B
, F
>(self, mut f
: F
) -> (B
, B
) where
585 B
: Default
+ Extend
<Self::Item
>,
586 F
: FnMut(&Self::Item
) -> bool
588 let mut left
: B
= Default
::default();
589 let mut right
: B
= Default
::default();
593 left
.extend(Some(x
).into_iter())
595 right
.extend(Some(x
).into_iter())
602 /// Performs a fold operation over the entire iterator, returning the
603 /// eventual state at the end of the iteration.
605 /// This operation is sometimes called 'reduce' or 'inject'.
610 /// let a = [1, 2, 3, 4, 5];
611 /// assert_eq!(a.iter().fold(0, |acc, &item| acc + item), 15);
614 #[stable(feature = "rust1", since = "1.0.0")]
615 fn fold
<B
, F
>(self, init
: B
, mut f
: F
) -> B
where
616 Self: Sized
, F
: FnMut(B
, Self::Item
) -> B
,
618 let mut accum
= init
;
625 /// Tests whether the predicate holds true for all elements in the iterator.
630 /// let a = [1, 2, 3, 4, 5];
631 /// assert!(a.iter().all(|x| *x > 0));
632 /// assert!(!a.iter().all(|x| *x > 2));
635 #[stable(feature = "rust1", since = "1.0.0")]
636 fn all
<F
>(&mut self, mut f
: F
) -> bool
where
637 Self: Sized
, F
: FnMut(Self::Item
) -> bool
639 for x
in self.by_ref() {
647 /// Tests whether any element of an iterator satisfies the specified
650 /// Does not consume the iterator past the first found element.
655 /// let a = [1, 2, 3, 4, 5];
656 /// let mut it = a.iter();
657 /// assert!(it.any(|x| *x == 3));
658 /// assert_eq!(it.collect::<Vec<_>>(), [&4, &5]);
661 #[stable(feature = "rust1", since = "1.0.0")]
662 fn any
<F
>(&mut self, mut f
: F
) -> bool
where
664 F
: FnMut(Self::Item
) -> bool
666 for x
in self.by_ref() {
674 /// Returns the first element satisfying the specified predicate.
676 /// Does not consume the iterator past the first found element.
681 /// let a = [1, 2, 3, 4, 5];
682 /// let mut it = a.iter();
683 /// assert_eq!(it.find(|&x| *x == 3), Some(&3));
684 /// assert_eq!(it.collect::<Vec<_>>(), [&4, &5]);
686 #[stable(feature = "rust1", since = "1.0.0")]
687 fn find
<P
>(&mut self, mut predicate
: P
) -> Option
<Self::Item
> where
689 P
: FnMut(&Self::Item
) -> bool
,
691 for x
in self.by_ref() {
692 if predicate(&x
) { return Some(x) }
697 /// Returns the index of the first element satisfying the specified predicate
699 /// Does not consume the iterator past the first found element.
701 /// # Overflow Behavior
703 /// The method does no guarding against overflows, so if there are more
704 /// than `usize::MAX` non-matching elements, it either produces the wrong
705 /// result or panics. If debug assertions are enabled, a panic is
710 /// This functions might panic if the iterator has more than `usize::MAX`
711 /// non-matching elements.
716 /// let a = [1, 2, 3, 4, 5];
717 /// let mut it = a.iter();
718 /// assert_eq!(it.position(|x| *x == 3), Some(2));
719 /// assert_eq!(it.collect::<Vec<_>>(), [&4, &5]);
721 #[stable(feature = "rust1", since = "1.0.0")]
722 fn position
<P
>(&mut self, mut predicate
: P
) -> Option
<usize> where
724 P
: FnMut(Self::Item
) -> bool
,
726 // `enumerate` might overflow.
727 for (i
, x
) in self.by_ref().enumerate() {
735 /// Returns the index of the last element satisfying the specified predicate
737 /// If no element matches, `None` is returned.
739 /// Does not consume the iterator *before* the first found element.
744 /// let a = [1, 2, 2, 4, 5];
745 /// let mut it = a.iter();
746 /// assert_eq!(it.rposition(|x| *x == 2), Some(2));
747 /// assert_eq!(it.collect::<Vec<_>>(), [&1, &2]);
749 #[stable(feature = "rust1", since = "1.0.0")]
750 fn rposition
<P
>(&mut self, mut predicate
: P
) -> Option
<usize> where
751 P
: FnMut(Self::Item
) -> bool
,
752 Self: Sized
+ ExactSizeIterator
+ DoubleEndedIterator
754 let mut i
= self.len();
756 while let Some(v
) = self.next_back() {
760 // No need for an overflow check here, because `ExactSizeIterator`
761 // implies that the number of elements fits into a `usize`.
767 /// Consumes the entire iterator to return the maximum element.
769 /// Returns the rightmost element if the comparison determines two elements
770 /// to be equally maximum.
775 /// let a = [1, 2, 3, 4, 5];
776 /// assert_eq!(a.iter().max(), Some(&5));
779 #[stable(feature = "rust1", since = "1.0.0")]
780 fn max(self) -> Option
<Self::Item
> where Self: Sized
, Self::Item
: Ord
784 // switch to y even if it is only equal, to preserve
786 |_
, x
, _
, y
| *x
<= *y
)
790 /// Consumes the entire iterator to return the minimum element.
792 /// Returns the leftmost element if the comparison determines two elements
793 /// to be equally minimum.
798 /// let a = [1, 2, 3, 4, 5];
799 /// assert_eq!(a.iter().min(), Some(&1));
802 #[stable(feature = "rust1", since = "1.0.0")]
803 fn min(self) -> Option
<Self::Item
> where Self: Sized
, Self::Item
: Ord
807 // only switch to y if it is strictly smaller, to
808 // preserve stability.
809 |_
, x
, _
, y
| *x
> *y
)
813 /// `min_max` finds the minimum and maximum elements in the iterator.
815 /// The return type `MinMaxResult` is an enum of three variants:
817 /// - `NoElements` if the iterator is empty.
818 /// - `OneElement(x)` if the iterator has exactly one element.
819 /// - `MinMax(x, y)` is returned otherwise, where `x <= y`. Two
820 /// values are equal if and only if there is more than one
821 /// element in the iterator and all elements are equal.
823 /// On an iterator of length `n`, `min_max` does `1.5 * n` comparisons,
824 /// and so is faster than calling `min` and `max` separately which does `2 *
830 /// # #![feature(core)]
831 /// use std::iter::MinMaxResult::{NoElements, OneElement, MinMax};
833 /// let a: [i32; 0] = [];
834 /// assert_eq!(a.iter().min_max(), NoElements);
837 /// assert_eq!(a.iter().min_max(), OneElement(&1));
839 /// let a = [1, 2, 3, 4, 5];
840 /// assert_eq!(a.iter().min_max(), MinMax(&1, &5));
842 /// let a = [1, 1, 1, 1];
843 /// assert_eq!(a.iter().min_max(), MinMax(&1, &1));
845 #[unstable(feature = "core", reason = "return type may change")]
846 fn min_max(mut self) -> MinMaxResult
<Self::Item
> where Self: Sized
, Self::Item
: Ord
848 let (mut min
, mut max
) = match self.next() {
849 None
=> return NoElements
,
852 None
=> return OneElement(x
),
853 Some(y
) => if x
<= y {(x, y)}
else {(y, x)}
859 // `first` and `second` are the two next elements we want to look
860 // at. We first compare `first` and `second` (#1). The smaller one
861 // is then compared to current minimum (#2). The larger one is
862 // compared to current maximum (#3). This way we do 3 comparisons
864 let first
= match self.next() {
868 let second
= match self.next() {
872 } else if first
>= max
{
880 if first
< min { min = first }
881 if second
>= max { max = second }
883 if second
< min { min = second }
884 if first
>= max { max = first }
891 /// Returns the element that gives the maximum value from the
892 /// specified function.
894 /// Returns the rightmost element if the comparison determines two elements
895 /// to be equally maximum.
900 /// # #![feature(core)]
902 /// let a = [-3_i32, 0, 1, 5, -10];
903 /// assert_eq!(*a.iter().max_by(|x| x.abs()).unwrap(), -10);
906 #[unstable(feature = "core",
907 reason
= "may want to produce an Ordering directly; see #15311")]
908 fn max_by
<B
: Ord
, F
>(self, f
: F
) -> Option
<Self::Item
> where
910 F
: FnMut(&Self::Item
) -> B
,
914 // switch to y even if it is only equal, to preserve
916 |x_p
, _
, y_p
, _
| x_p
<= y_p
)
920 /// Returns the element that gives the minimum value from the
921 /// specified function.
923 /// Returns the leftmost element if the comparison determines two elements
924 /// to be equally minimum.
929 /// # #![feature(core)]
931 /// let a = [-3_i32, 0, 1, 5, -10];
932 /// assert_eq!(*a.iter().min_by(|x| x.abs()).unwrap(), 0);
935 #[unstable(feature = "core",
936 reason
= "may want to produce an Ordering directly; see #15311")]
937 fn min_by
<B
: Ord
, F
>(self, f
: F
) -> Option
<Self::Item
> where
939 F
: FnMut(&Self::Item
) -> B
,
943 // only switch to y if it is strictly smaller, to
944 // preserve stability.
945 |x_p
, _
, y_p
, _
| x_p
> y_p
)
949 /// Change the direction of the iterator
951 /// The flipped iterator swaps the ends on an iterator that can already
952 /// be iterated from the front and from the back.
955 /// If the iterator also implements RandomAccessIterator, the flipped
956 /// iterator is also random access, with the indices starting at the back
957 /// of the original iterator.
959 /// Note: Random access with flipped indices still only applies to the first
960 /// `std::usize::MAX` elements of the original iterator.
962 #[stable(feature = "rust1", since = "1.0.0")]
963 fn rev(self) -> Rev
<Self> where Self: Sized
+ DoubleEndedIterator
{
967 /// Converts an iterator of pairs into a pair of containers.
969 /// Loops through the entire iterator, collecting the first component of
970 /// each item into one new container, and the second component into another.
975 /// # #![feature(core)]
976 /// let a = [(1, 2), (3, 4)];
977 /// let (left, right): (Vec<_>, Vec<_>) = a.iter().cloned().unzip();
978 /// assert_eq!(left, [1, 3]);
979 /// assert_eq!(right, [2, 4]);
981 #[stable(feature = "rust1", since = "1.0.0")]
982 fn unzip
<A
, B
, FromA
, FromB
>(self) -> (FromA
, FromB
) where
983 FromA
: Default
+ Extend
<A
>,
984 FromB
: Default
+ Extend
<B
>,
985 Self: Sized
+ Iterator
<Item
=(A
, B
)>,
987 struct SizeHint
<A
>(usize, Option
<usize>, marker
::PhantomData
<A
>);
988 impl<A
> Iterator
for SizeHint
<A
> {
991 fn next(&mut self) -> Option
<A
> { None }
992 fn size_hint(&self) -> (usize, Option
<usize>) {
997 let (lo
, hi
) = self.size_hint();
998 let mut ts
: FromA
= Default
::default();
999 let mut us
: FromB
= Default
::default();
1001 ts
.extend(SizeHint(lo
, hi
, marker
::PhantomData
));
1002 us
.extend(SizeHint(lo
, hi
, marker
::PhantomData
));
1004 for (t
, u
) in self {
1005 ts
.extend(Some(t
).into_iter());
1006 us
.extend(Some(u
).into_iter());
1012 /// Creates an iterator that clones the elements it yields. Useful for
1013 /// converting an Iterator<&T> to an Iterator<T>.
1014 #[stable(feature = "rust1", since = "1.0.0")]
1015 fn cloned
<'a
, T
: 'a
>(self) -> Cloned
<Self>
1016 where Self: Sized
+ Iterator
<Item
=&'a T
>, T
: Clone
1021 /// Repeats an iterator endlessly
1027 /// let mut it = a.iter().cycle();
1028 /// assert_eq!(it.next(), Some(&1));
1029 /// assert_eq!(it.next(), Some(&2));
1030 /// assert_eq!(it.next(), Some(&1));
1032 #[stable(feature = "rust1", since = "1.0.0")]
1034 fn cycle(self) -> Cycle
<Self> where Self: Sized
+ Clone
{
1035 Cycle{orig: self.clone(), iter: self}
1038 /// Use an iterator to reverse a container in place.
1039 #[unstable(feature = "core",
1040 reason
= "uncertain about placement or widespread use")]
1041 fn reverse_in_place
<'a
, T
: 'a
>(&mut self) where
1042 Self: Sized
+ Iterator
<Item
=&'a
mut T
> + DoubleEndedIterator
1045 match (self.next(), self.next_back()) {
1046 (Some(x
), Some(y
)) => mem
::swap(x
, y
),
1052 /// Iterates over the entire iterator, summing up all the elements
1057 /// # #![feature(core)]
1059 /// let a = [1, 2, 3, 4, 5];
1060 /// let mut it = a.iter().cloned();
1061 /// assert_eq!(it.sum::<i32>(), 15);
1063 #[unstable(feature="core")]
1064 fn sum
<S
=<Self as Iterator
>::Item
>(self) -> S
where
1065 S
: Add
<Self::Item
, Output
=S
> + Zero
,
1068 self.fold(Zero
::zero(), |s
, e
| s
+ e
)
1071 /// Iterates over the entire iterator, multiplying all the elements
1076 /// # #![feature(core)]
1078 /// fn factorial(n: u32) -> u32 {
1079 /// (1..).take_while(|&i| i <= n).product()
1081 /// assert_eq!(factorial(0), 1);
1082 /// assert_eq!(factorial(1), 1);
1083 /// assert_eq!(factorial(5), 120);
1085 #[unstable(feature="core")]
1086 fn product
<P
=<Self as Iterator
>::Item
>(self) -> P
where
1087 P
: Mul
<Self::Item
, Output
=P
> + One
,
1090 self.fold(One
::one(), |p
, e
| p
* e
)
1094 /// Select an element from an iterator based on the given projection
1095 /// and "comparison" function.
1097 /// This is an idiosyncratic helper to try to factor out the
1098 /// commonalities of {max,min}{,_by}. In particular, this avoids
1099 /// having to implement optimisations several times.
1101 fn select_fold1
<I
,B
, FProj
, FCmp
>(mut it
: I
,
1103 mut f_cmp
: FCmp
) -> Option
<(B
, I
::Item
)>
1105 FProj
: FnMut(&I
::Item
) -> B
,
1106 FCmp
: FnMut(&B
, &I
::Item
, &B
, &I
::Item
) -> bool
1108 // start with the first element as our selection. This avoids
1109 // having to use `Option`s inside the loop, translating to a
1110 // sizeable performance gain (6x in one case).
1111 it
.next().map(|mut sel
| {
1112 let mut sel_p
= f_proj(&sel
);
1115 let x_p
= f_proj(&x
);
1116 if f_cmp(&sel_p
, &sel
, &x_p
, &x
) {
1125 #[stable(feature = "rust1", since = "1.0.0")]
1126 impl<'a
, I
: Iterator
+ ?Sized
> Iterator
for &'a
mut I
{
1127 type Item
= I
::Item
;
1128 fn next(&mut self) -> Option
<I
::Item
> { (**self).next() }
1129 fn size_hint(&self) -> (usize, Option
<usize>) { (**self).size_hint() }
1132 /// Conversion from an `Iterator`
1133 #[stable(feature = "rust1", since = "1.0.0")]
1134 #[rustc_on_unimplemented="a collection of type `{Self}` cannot be \
1135 built from an iterator over elements of type `{A}`"]
1136 pub trait FromIterator
<A
> {
1137 /// Builds a container with elements from something iterable.
1142 /// use std::collections::HashSet;
1143 /// use std::iter::FromIterator;
1145 /// let colors_vec = vec!["red", "red", "yellow", "blue"];
1146 /// let colors_set = HashSet::<&str>::from_iter(colors_vec);
1147 /// assert_eq!(colors_set.len(), 3);
1150 /// `FromIterator` is more commonly used implicitly via the
1151 /// `Iterator::collect` method:
1154 /// use std::collections::HashSet;
1156 /// let colors_vec = vec!["red", "red", "yellow", "blue"];
1157 /// let colors_set = colors_vec.into_iter().collect::<HashSet<&str>>();
1158 /// assert_eq!(colors_set.len(), 3);
1160 #[stable(feature = "rust1", since = "1.0.0")]
1161 fn from_iter
<T
: IntoIterator
<Item
=A
>>(iterator
: T
) -> Self;
1164 /// Conversion into an `Iterator`
1166 /// Implementing this trait allows you to use your type with Rust's `for` loop. See
1167 /// the [module level documentation](index.html) for more details.
1168 #[stable(feature = "rust1", since = "1.0.0")]
1169 pub trait IntoIterator
{
1170 /// The type of the elements being iterated
1171 #[stable(feature = "rust1", since = "1.0.0")]
1174 /// A container for iterating over elements of type `Item`
1175 #[stable(feature = "rust1", since = "1.0.0")]
1176 type IntoIter
: Iterator
<Item
=Self::Item
>;
1178 /// Consumes `Self` and returns an iterator over it
1179 #[stable(feature = "rust1", since = "1.0.0")]
1180 fn into_iter(self) -> Self::IntoIter
;
1183 #[stable(feature = "rust1", since = "1.0.0")]
1184 impl<I
: Iterator
> IntoIterator
for I
{
1185 type Item
= I
::Item
;
1188 fn into_iter(self) -> I
{
1193 /// A type growable from an `Iterator` implementation
1194 #[stable(feature = "rust1", since = "1.0.0")]
1195 pub trait Extend
<A
> {
1196 /// Extends a container with the elements yielded by an arbitrary iterator
1197 #[stable(feature = "rust1", since = "1.0.0")]
1198 fn extend
<T
: IntoIterator
<Item
=A
>>(&mut self, iterable
: T
);
1201 /// A range iterator able to yield elements from both ends
1203 /// A `DoubleEndedIterator` can be thought of as a deque in that `next()` and
1204 /// `next_back()` exhaust elements from the *same* range, and do not work
1205 /// independently of each other.
1206 #[stable(feature = "rust1", since = "1.0.0")]
1207 pub trait DoubleEndedIterator
: Iterator
{
1208 /// Yields an element from the end of the range, returning `None` if the
1210 #[stable(feature = "rust1", since = "1.0.0")]
1211 fn next_back(&mut self) -> Option
<Self::Item
>;
1214 #[stable(feature = "rust1", since = "1.0.0")]
1215 impl<'a
, I
: DoubleEndedIterator
+ ?Sized
> DoubleEndedIterator
for &'a
mut I
{
1216 fn next_back(&mut self) -> Option
<I
::Item
> { (**self).next_back() }
1219 /// An object implementing random access indexing by `usize`
1221 /// A `RandomAccessIterator` should be either infinite or a
1222 /// `DoubleEndedIterator`. Calling `next()` or `next_back()` on a
1223 /// `RandomAccessIterator` reduces the indexable range accordingly. That is,
1224 /// `it.idx(1)` will become `it.idx(0)` after `it.next()` is called.
1225 #[unstable(feature = "core",
1226 reason
= "not widely used, may be better decomposed into Index \
1227 and ExactSizeIterator")]
1228 pub trait RandomAccessIterator
: Iterator
{
1229 /// Returns the number of indexable elements. At most `std::usize::MAX`
1230 /// elements are indexable, even if the iterator represents a longer range.
1231 fn indexable(&self) -> usize;
1233 /// Returns an element at an index, or `None` if the index is out of bounds
1234 fn idx(&mut self, index
: usize) -> Option
<Self::Item
>;
1237 /// An iterator that knows its exact length
1239 /// This trait is a helper for iterators like the vector iterator, so that
1240 /// it can support double-ended enumeration.
1242 /// `Iterator::size_hint` *must* return the exact size of the iterator.
1243 /// Note that the size must fit in `usize`.
1244 #[stable(feature = "rust1", since = "1.0.0")]
1245 pub trait ExactSizeIterator
: Iterator
{
1247 #[stable(feature = "rust1", since = "1.0.0")]
1248 /// Returns the exact length of the iterator.
1249 fn len(&self) -> usize {
1250 let (lower
, upper
) = self.size_hint();
1251 // Note: This assertion is overly defensive, but it checks the invariant
1252 // guaranteed by the trait. If this trait were rust-internal,
1253 // we could use debug_assert!; assert_eq! will check all Rust user
1254 // implementations too.
1255 assert_eq
!(upper
, Some(lower
));
1260 #[stable(feature = "rust1", since = "1.0.0")]
1261 impl<'a
, I
: ExactSizeIterator
+ ?Sized
> ExactSizeIterator
for &'a
mut I {}
1263 // All adaptors that preserve the size of the wrapped iterator are fine
1264 // Adaptors that may overflow in `size_hint` are not, i.e. `Chain`.
1265 #[stable(feature = "rust1", since = "1.0.0")]
1266 impl<I
> ExactSizeIterator
for Enumerate
<I
> where I
: ExactSizeIterator {}
1267 #[stable(feature = "rust1", since = "1.0.0")]
1268 impl<I
: ExactSizeIterator
, F
> ExactSizeIterator
for Inspect
<I
, F
> where
1271 #[stable(feature = "rust1", since = "1.0.0")]
1272 impl<I
> ExactSizeIterator
for Rev
<I
>
1273 where I
: ExactSizeIterator
+ DoubleEndedIterator {}
1274 #[stable(feature = "rust1", since = "1.0.0")]
1275 impl<B
, I
: ExactSizeIterator
, F
> ExactSizeIterator
for Map
<I
, F
> where
1276 F
: FnMut(I
::Item
) -> B
,
1278 #[stable(feature = "rust1", since = "1.0.0")]
1279 impl<A
, B
> ExactSizeIterator
for Zip
<A
, B
>
1280 where A
: ExactSizeIterator
, B
: ExactSizeIterator {}
1282 /// An double-ended iterator with the direction inverted
1284 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1285 #[stable(feature = "rust1", since = "1.0.0")]
1290 #[stable(feature = "rust1", since = "1.0.0")]
1291 impl<I
> Iterator
for Rev
<I
> where I
: DoubleEndedIterator
{
1292 type Item
= <I
as Iterator
>::Item
;
1295 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> { self.iter.next_back() }
1297 fn size_hint(&self) -> (usize, Option
<usize>) { self.iter.size_hint() }
1300 #[stable(feature = "rust1", since = "1.0.0")]
1301 impl<I
> DoubleEndedIterator
for Rev
<I
> where I
: DoubleEndedIterator
{
1303 fn next_back(&mut self) -> Option
<<I
as Iterator
>::Item
> { self.iter.next() }
1306 #[unstable(feature = "core", reason = "trait is experimental")]
1307 impl<I
> RandomAccessIterator
for Rev
<I
>
1308 where I
: DoubleEndedIterator
+ RandomAccessIterator
1311 fn indexable(&self) -> usize { self.iter.indexable() }
1313 fn idx(&mut self, index
: usize) -> Option
<<I
as Iterator
>::Item
> {
1314 let amt
= self.indexable();
1316 self.iter
.idx(amt
- index
- 1)
1323 /// `MinMaxResult` is an enum returned by `min_max`. See `Iterator::min_max` for
1325 #[derive(Clone, PartialEq, Debug)]
1326 #[unstable(feature = "core",
1327 reason
= "unclear whether such a fine-grained result is widely useful")]
1328 pub enum MinMaxResult
<T
> {
1332 /// Iterator with one element, so the minimum and maximum are the same
1335 /// More than one element in the iterator, the first element is not larger
1340 impl<T
: Clone
> MinMaxResult
<T
> {
1341 /// `into_option` creates an `Option` of type `(T,T)`. The returned `Option`
1342 /// has variant `None` if and only if the `MinMaxResult` has variant
1343 /// `NoElements`. Otherwise variant `Some(x,y)` is returned where `x <= y`.
1344 /// If `MinMaxResult` has variant `OneElement(x)`, performing this operation
1345 /// will make one clone of `x`.
1350 /// # #![feature(core)]
1351 /// use std::iter::MinMaxResult::{self, NoElements, OneElement, MinMax};
1353 /// let r: MinMaxResult<i32> = NoElements;
1354 /// assert_eq!(r.into_option(), None);
1356 /// let r = OneElement(1);
1357 /// assert_eq!(r.into_option(), Some((1, 1)));
1359 /// let r = MinMax(1, 2);
1360 /// assert_eq!(r.into_option(), Some((1, 2)));
1362 #[unstable(feature = "core", reason = "type is unstable")]
1363 pub fn into_option(self) -> Option
<(T
,T
)> {
1366 OneElement(x
) => Some((x
.clone(), x
)),
1367 MinMax(x
, y
) => Some((x
, y
))
1372 /// An iterator that clones the elements of an underlying iterator
1373 #[stable(feature = "iter_cloned", since = "1.1.0")]
1374 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1376 pub struct Cloned
<I
> {
1380 #[stable(feature = "rust1", since = "1.0.0")]
1381 impl<'a
, I
, T
: 'a
> Iterator
for Cloned
<I
>
1382 where I
: Iterator
<Item
=&'a T
>, T
: Clone
1386 fn next(&mut self) -> Option
<T
> {
1387 self.it
.next().cloned()
1390 fn size_hint(&self) -> (usize, Option
<usize>) {
1395 #[stable(feature = "rust1", since = "1.0.0")]
1396 impl<'a
, I
, T
: 'a
> DoubleEndedIterator
for Cloned
<I
>
1397 where I
: DoubleEndedIterator
<Item
=&'a T
>, T
: Clone
1399 fn next_back(&mut self) -> Option
<T
> {
1400 self.it
.next_back().cloned()
1404 #[stable(feature = "rust1", since = "1.0.0")]
1405 impl<'a
, I
, T
: 'a
> ExactSizeIterator
for Cloned
<I
>
1406 where I
: ExactSizeIterator
<Item
=&'a T
>, T
: Clone
1409 #[unstable(feature = "core", reason = "trait is experimental")]
1410 impl<'a
, I
, T
: 'a
> RandomAccessIterator
for Cloned
<I
>
1411 where I
: RandomAccessIterator
<Item
=&'a T
>, T
: Clone
1414 fn indexable(&self) -> usize {
1419 fn idx(&mut self, index
: usize) -> Option
<T
> {
1420 self.it
.idx(index
).cloned()
1424 /// An iterator that repeats endlessly
1426 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1427 #[stable(feature = "rust1", since = "1.0.0")]
1428 pub struct Cycle
<I
> {
1433 #[stable(feature = "rust1", since = "1.0.0")]
1434 impl<I
> Iterator
for Cycle
<I
> where I
: Clone
+ Iterator
{
1435 type Item
= <I
as Iterator
>::Item
;
1438 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> {
1439 match self.iter
.next() {
1440 None
=> { self.iter = self.orig.clone(); self.iter.next() }
1446 fn size_hint(&self) -> (usize, Option
<usize>) {
1447 // the cycle iterator is either empty or infinite
1448 match self.orig
.size_hint() {
1449 sz @
(0, Some(0)) => sz
,
1450 (0, _
) => (0, None
),
1451 _
=> (usize::MAX
, None
)
1456 #[unstable(feature = "core", reason = "trait is experimental")]
1457 impl<I
> RandomAccessIterator
for Cycle
<I
> where
1458 I
: Clone
+ RandomAccessIterator
,
1461 fn indexable(&self) -> usize {
1462 if self.orig
.indexable() > 0 {
1470 fn idx(&mut self, index
: usize) -> Option
<<I
as Iterator
>::Item
> {
1471 let liter
= self.iter
.indexable();
1472 let lorig
= self.orig
.indexable();
1475 } else if index
< liter
{
1476 self.iter
.idx(index
)
1478 self.orig
.idx((index
- liter
) % lorig
)
1483 /// An iterator that strings two iterators together
1485 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1486 #[stable(feature = "rust1", since = "1.0.0")]
1487 pub struct Chain
<A
, B
> {
1493 #[stable(feature = "rust1", since = "1.0.0")]
1494 impl<A
, B
> Iterator
for Chain
<A
, B
> where
1496 B
: Iterator
<Item
= A
::Item
>
1498 type Item
= A
::Item
;
1501 fn next(&mut self) -> Option
<A
::Item
> {
1505 match self.a
.next() {
1506 Some(x
) => return Some(x
),
1515 fn count(self) -> usize {
1516 (if !self.flag { self.a.count() }
else { 0 }
) + self.b
.count()
1520 fn nth(&mut self, mut n
: usize) -> Option
<A
::Item
> {
1522 for x
in self.a
.by_ref() {
1534 fn last(self) -> Option
<A
::Item
> {
1535 let a_last
= if self.flag { None }
else { self.a.last() }
;
1536 let b_last
= self.b
.last();
1541 fn size_hint(&self) -> (usize, Option
<usize>) {
1542 let (a_lower
, a_upper
) = self.a
.size_hint();
1543 let (b_lower
, b_upper
) = self.b
.size_hint();
1545 let lower
= a_lower
.saturating_add(b_lower
);
1547 let upper
= match (a_upper
, b_upper
) {
1548 (Some(x
), Some(y
)) => x
.checked_add(y
),
1556 #[stable(feature = "rust1", since = "1.0.0")]
1557 impl<A
, B
> DoubleEndedIterator
for Chain
<A
, B
> where
1558 A
: DoubleEndedIterator
,
1559 B
: DoubleEndedIterator
<Item
=A
::Item
>,
1562 fn next_back(&mut self) -> Option
<A
::Item
> {
1563 match self.b
.next_back() {
1565 None
=> self.a
.next_back()
1570 #[unstable(feature = "core", reason = "trait is experimental")]
1571 impl<A
, B
> RandomAccessIterator
for Chain
<A
, B
> where
1572 A
: RandomAccessIterator
,
1573 B
: RandomAccessIterator
<Item
= A
::Item
>,
1576 fn indexable(&self) -> usize {
1577 let (a
, b
) = (self.a
.indexable(), self.b
.indexable());
1582 fn idx(&mut self, index
: usize) -> Option
<A
::Item
> {
1583 let len
= self.a
.indexable();
1587 self.b
.idx(index
- len
)
1592 /// An iterator that iterates two other iterators simultaneously
1594 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1595 #[stable(feature = "rust1", since = "1.0.0")]
1596 pub struct Zip
<A
, B
> {
1601 #[stable(feature = "rust1", since = "1.0.0")]
1602 impl<A
, B
> Iterator
for Zip
<A
, B
> where A
: Iterator
, B
: Iterator
1604 type Item
= (A
::Item
, B
::Item
);
1607 fn next(&mut self) -> Option
<(A
::Item
, B
::Item
)> {
1608 self.a
.next().and_then(|x
| {
1609 self.b
.next().and_then(|y
| {
1616 fn size_hint(&self) -> (usize, Option
<usize>) {
1617 let (a_lower
, a_upper
) = self.a
.size_hint();
1618 let (b_lower
, b_upper
) = self.b
.size_hint();
1620 let lower
= cmp
::min(a_lower
, b_lower
);
1622 let upper
= match (a_upper
, b_upper
) {
1623 (Some(x
), Some(y
)) => Some(cmp
::min(x
,y
)),
1624 (Some(x
), None
) => Some(x
),
1625 (None
, Some(y
)) => Some(y
),
1626 (None
, None
) => None
1633 #[stable(feature = "rust1", since = "1.0.0")]
1634 impl<A
, B
> DoubleEndedIterator
for Zip
<A
, B
> where
1635 A
: DoubleEndedIterator
+ ExactSizeIterator
,
1636 B
: DoubleEndedIterator
+ ExactSizeIterator
,
1639 fn next_back(&mut self) -> Option
<(A
::Item
, B
::Item
)> {
1640 let a_sz
= self.a
.len();
1641 let b_sz
= self.b
.len();
1643 // Adjust a, b to equal length
1645 for _
in 0..a_sz
- b_sz { self.a.next_back(); }
1647 for _
in 0..b_sz
- a_sz { self.b.next_back(); }
1650 match (self.a
.next_back(), self.b
.next_back()) {
1651 (Some(x
), Some(y
)) => Some((x
, y
)),
1652 (None
, None
) => None
,
1653 _
=> unreachable
!(),
1658 #[unstable(feature = "core", reason = "trait is experimental")]
1659 impl<A
, B
> RandomAccessIterator
for Zip
<A
, B
> where
1660 A
: RandomAccessIterator
,
1661 B
: RandomAccessIterator
1664 fn indexable(&self) -> usize {
1665 cmp
::min(self.a
.indexable(), self.b
.indexable())
1669 fn idx(&mut self, index
: usize) -> Option
<(A
::Item
, B
::Item
)> {
1670 self.a
.idx(index
).and_then(|x
| {
1671 self.b
.idx(index
).and_then(|y
| {
1678 /// An iterator that maps the values of `iter` with `f`
1679 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1680 #[stable(feature = "rust1", since = "1.0.0")]
1682 pub struct Map
<I
, F
> {
1687 #[stable(feature = "rust1", since = "1.0.0")]
1688 impl<B
, I
: Iterator
, F
> Iterator
for Map
<I
, F
> where F
: FnMut(I
::Item
) -> B
{
1692 fn next(&mut self) -> Option
<B
> {
1693 self.iter
.next().map(|a
| (self.f
)(a
))
1697 fn size_hint(&self) -> (usize, Option
<usize>) {
1698 self.iter
.size_hint()
1702 #[stable(feature = "rust1", since = "1.0.0")]
1703 impl<B
, I
: DoubleEndedIterator
, F
> DoubleEndedIterator
for Map
<I
, F
> where
1704 F
: FnMut(I
::Item
) -> B
,
1707 fn next_back(&mut self) -> Option
<B
> {
1708 self.iter
.next_back().map(|a
| (self.f
)(a
))
1712 #[unstable(feature = "core", reason = "trait is experimental")]
1713 impl<B
, I
: RandomAccessIterator
, F
> RandomAccessIterator
for Map
<I
, F
> where
1714 F
: FnMut(I
::Item
) -> B
,
1717 fn indexable(&self) -> usize {
1718 self.iter
.indexable()
1722 fn idx(&mut self, index
: usize) -> Option
<B
> {
1723 self.iter
.idx(index
).map(|a
| (self.f
)(a
))
1727 /// An iterator that filters the elements of `iter` with `predicate`
1728 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1729 #[stable(feature = "rust1", since = "1.0.0")]
1731 pub struct Filter
<I
, P
> {
1736 #[stable(feature = "rust1", since = "1.0.0")]
1737 impl<I
: Iterator
, P
> Iterator
for Filter
<I
, P
> where P
: FnMut(&I
::Item
) -> bool
{
1738 type Item
= I
::Item
;
1741 fn next(&mut self) -> Option
<I
::Item
> {
1742 for x
in self.iter
.by_ref() {
1743 if (self.predicate
)(&x
) {
1751 fn size_hint(&self) -> (usize, Option
<usize>) {
1752 let (_
, upper
) = self.iter
.size_hint();
1753 (0, upper
) // can't know a lower bound, due to the predicate
1757 #[stable(feature = "rust1", since = "1.0.0")]
1758 impl<I
: DoubleEndedIterator
, P
> DoubleEndedIterator
for Filter
<I
, P
>
1759 where P
: FnMut(&I
::Item
) -> bool
,
1762 fn next_back(&mut self) -> Option
<I
::Item
> {
1763 for x
in self.iter
.by_ref().rev() {
1764 if (self.predicate
)(&x
) {
1772 /// An iterator that uses `f` to both filter and map elements from `iter`
1773 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1774 #[stable(feature = "rust1", since = "1.0.0")]
1776 pub struct FilterMap
<I
, F
> {
1781 #[stable(feature = "rust1", since = "1.0.0")]
1782 impl<B
, I
: Iterator
, F
> Iterator
for FilterMap
<I
, F
>
1783 where F
: FnMut(I
::Item
) -> Option
<B
>,
1788 fn next(&mut self) -> Option
<B
> {
1789 for x
in self.iter
.by_ref() {
1790 if let Some(y
) = (self.f
)(x
) {
1798 fn size_hint(&self) -> (usize, Option
<usize>) {
1799 let (_
, upper
) = self.iter
.size_hint();
1800 (0, upper
) // can't know a lower bound, due to the predicate
1804 #[stable(feature = "rust1", since = "1.0.0")]
1805 impl<B
, I
: DoubleEndedIterator
, F
> DoubleEndedIterator
for FilterMap
<I
, F
>
1806 where F
: FnMut(I
::Item
) -> Option
<B
>,
1809 fn next_back(&mut self) -> Option
<B
> {
1810 for x
in self.iter
.by_ref().rev() {
1811 if let Some(y
) = (self.f
)(x
) {
1819 /// An iterator that yields the current count and the element during iteration
1821 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1822 #[stable(feature = "rust1", since = "1.0.0")]
1823 pub struct Enumerate
<I
> {
1828 #[stable(feature = "rust1", since = "1.0.0")]
1829 impl<I
> Iterator
for Enumerate
<I
> where I
: Iterator
{
1830 type Item
= (usize, <I
as Iterator
>::Item
);
1832 /// # Overflow Behavior
1834 /// The method does no guarding against overflows, so enumerating more than
1835 /// `usize::MAX` elements either produces the wrong result or panics. If
1836 /// debug assertions are enabled, a panic is guaranteed.
1840 /// Might panic if the index of the element overflows a `usize`.
1842 fn next(&mut self) -> Option
<(usize, <I
as Iterator
>::Item
)> {
1843 self.iter
.next().map(|a
| {
1844 let ret
= (self.count
, a
);
1845 // Possible undefined overflow.
1852 fn size_hint(&self) -> (usize, Option
<usize>) {
1853 self.iter
.size_hint()
1857 fn nth(&mut self, n
: usize) -> Option
<(usize, I
::Item
)> {
1858 self.iter
.nth(n
).map(|a
| {
1859 let i
= self.count
+ n
;
1866 fn count(self) -> usize {
1871 #[stable(feature = "rust1", since = "1.0.0")]
1872 impl<I
> DoubleEndedIterator
for Enumerate
<I
> where
1873 I
: ExactSizeIterator
+ DoubleEndedIterator
1876 fn next_back(&mut self) -> Option
<(usize, <I
as Iterator
>::Item
)> {
1877 self.iter
.next_back().map(|a
| {
1878 let len
= self.iter
.len();
1879 // Can safely add, `ExactSizeIterator` promises that the number of
1880 // elements fits into a `usize`.
1881 (self.count
+ len
, a
)
1886 #[unstable(feature = "core", reason = "trait is experimental")]
1887 impl<I
> RandomAccessIterator
for Enumerate
<I
> where I
: RandomAccessIterator
{
1889 fn indexable(&self) -> usize {
1890 self.iter
.indexable()
1894 fn idx(&mut self, index
: usize) -> Option
<(usize, <I
as Iterator
>::Item
)> {
1895 // Can safely add, `ExactSizeIterator` (ancestor of
1896 // `RandomAccessIterator`) promises that the number of elements fits
1898 self.iter
.idx(index
).map(|a
| (self.count
+ index
, a
))
1902 /// An iterator with a `peek()` that returns an optional reference to the next element.
1903 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1904 #[stable(feature = "rust1", since = "1.0.0")]
1905 pub struct Peekable
<I
: Iterator
> {
1907 peeked
: Option
<I
::Item
>,
1910 impl<I
: Iterator
+ Clone
> Clone
for Peekable
<I
> where I
::Item
: Clone
{
1911 fn clone(&self) -> Peekable
<I
> {
1913 iter
: self.iter
.clone(),
1914 peeked
: self.peeked
.clone(),
1919 #[stable(feature = "rust1", since = "1.0.0")]
1920 impl<I
: Iterator
> Iterator
for Peekable
<I
> {
1921 type Item
= I
::Item
;
1924 fn next(&mut self) -> Option
<I
::Item
> {
1926 Some(_
) => self.peeked
.take(),
1927 None
=> self.iter
.next(),
1932 fn count(self) -> usize {
1933 (if self.peeked
.is_some() { 1 }
else { 0 }
) + self.iter
.count()
1937 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
1939 Some(_
) if n
== 0 => self.peeked
.take(),
1944 None
=> self.iter
.nth(n
)
1949 fn last(self) -> Option
<I
::Item
> {
1950 self.iter
.last().or(self.peeked
)
1954 fn size_hint(&self) -> (usize, Option
<usize>) {
1955 let (lo
, hi
) = self.iter
.size_hint();
1956 if self.peeked
.is_some() {
1957 let lo
= lo
.saturating_add(1);
1958 let hi
= hi
.and_then(|x
| x
.checked_add(1));
1966 #[stable(feature = "rust1", since = "1.0.0")]
1967 impl<I
: ExactSizeIterator
> ExactSizeIterator
for Peekable
<I
> {}
1969 #[stable(feature = "rust1", since = "1.0.0")]
1970 impl<I
: Iterator
> Peekable
<I
> {
1971 /// Returns a reference to the next element of the iterator with out
1972 /// advancing it, or None if the iterator is exhausted.
1974 #[stable(feature = "rust1", since = "1.0.0")]
1975 pub fn peek(&mut self) -> Option
<&I
::Item
> {
1976 if self.peeked
.is_none() {
1977 self.peeked
= self.iter
.next();
1980 Some(ref value
) => Some(value
),
1985 /// Checks whether peekable iterator is empty or not.
1987 pub fn is_empty(&mut self) -> bool
{
1988 self.peek().is_none()
1992 /// An iterator that rejects elements while `predicate` is true
1993 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1994 #[stable(feature = "rust1", since = "1.0.0")]
1996 pub struct SkipWhile
<I
, P
> {
2002 #[stable(feature = "rust1", since = "1.0.0")]
2003 impl<I
: Iterator
, P
> Iterator
for SkipWhile
<I
, P
>
2004 where P
: FnMut(&I
::Item
) -> bool
2006 type Item
= I
::Item
;
2009 fn next(&mut self) -> Option
<I
::Item
> {
2010 for x
in self.iter
.by_ref() {
2011 if self.flag
|| !(self.predicate
)(&x
) {
2020 fn size_hint(&self) -> (usize, Option
<usize>) {
2021 let (_
, upper
) = self.iter
.size_hint();
2022 (0, upper
) // can't know a lower bound, due to the predicate
2026 /// An iterator that only accepts elements while `predicate` is true
2027 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2028 #[stable(feature = "rust1", since = "1.0.0")]
2030 pub struct TakeWhile
<I
, P
> {
2036 #[stable(feature = "rust1", since = "1.0.0")]
2037 impl<I
: Iterator
, P
> Iterator
for TakeWhile
<I
, P
>
2038 where P
: FnMut(&I
::Item
) -> bool
2040 type Item
= I
::Item
;
2043 fn next(&mut self) -> Option
<I
::Item
> {
2047 self.iter
.next().and_then(|x
| {
2048 if (self.predicate
)(&x
) {
2059 fn size_hint(&self) -> (usize, Option
<usize>) {
2060 let (_
, upper
) = self.iter
.size_hint();
2061 (0, upper
) // can't know a lower bound, due to the predicate
2065 /// An iterator that skips over `n` elements of `iter`.
2067 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2068 #[stable(feature = "rust1", since = "1.0.0")]
2069 pub struct Skip
<I
> {
2074 #[stable(feature = "rust1", since = "1.0.0")]
2075 impl<I
> Iterator
for Skip
<I
> where I
: Iterator
{
2076 type Item
= <I
as Iterator
>::Item
;
2079 fn next(&mut self) -> Option
<I
::Item
> {
2085 self.iter
.nth(old_n
)
2090 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
2091 // Can't just add n + self.n due to overflow.
2095 let to_skip
= self.n
;
2098 if self.iter
.nth(to_skip
-1).is_none() {
2106 fn count(self) -> usize {
2107 self.iter
.count().saturating_sub(self.n
)
2111 fn last(mut self) -> Option
<I
::Item
> {
2115 let next
= self.next();
2117 // recurse. n should be 0.
2118 self.last().or(next
)
2126 fn size_hint(&self) -> (usize, Option
<usize>) {
2127 let (lower
, upper
) = self.iter
.size_hint();
2129 let lower
= lower
.saturating_sub(self.n
);
2130 let upper
= upper
.map(|x
| x
.saturating_sub(self.n
));
2136 #[unstable(feature = "core", reason = "trait is experimental")]
2137 impl<I
> RandomAccessIterator
for Skip
<I
> where I
: RandomAccessIterator
{
2139 fn indexable(&self) -> usize {
2140 self.iter
.indexable().saturating_sub(self.n
)
2144 fn idx(&mut self, index
: usize) -> Option
<<I
as Iterator
>::Item
> {
2145 if index
>= self.indexable() {
2148 self.iter
.idx(index
+ self.n
)
2153 #[stable(feature = "rust1", since = "1.0.0")]
2154 impl<I
> ExactSizeIterator
for Skip
<I
> where I
: ExactSizeIterator {}
2156 /// An iterator that only iterates over the first `n` iterations of `iter`.
2158 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2159 #[stable(feature = "rust1", since = "1.0.0")]
2160 pub struct Take
<I
> {
2165 #[stable(feature = "rust1", since = "1.0.0")]
2166 impl<I
> Iterator
for Take
<I
> where I
: Iterator
{
2167 type Item
= <I
as Iterator
>::Item
;
2170 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> {
2180 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
2186 self.iter
.nth(self.n
- 1);
2194 fn size_hint(&self) -> (usize, Option
<usize>) {
2195 let (lower
, upper
) = self.iter
.size_hint();
2197 let lower
= cmp
::min(lower
, self.n
);
2199 let upper
= match upper
{
2200 Some(x
) if x
< self.n
=> Some(x
),
2208 #[unstable(feature = "core", reason = "trait is experimental")]
2209 impl<I
> RandomAccessIterator
for Take
<I
> where I
: RandomAccessIterator
{
2211 fn indexable(&self) -> usize {
2212 cmp
::min(self.iter
.indexable(), self.n
)
2216 fn idx(&mut self, index
: usize) -> Option
<<I
as Iterator
>::Item
> {
2217 if index
>= self.n
{
2220 self.iter
.idx(index
)
2225 #[stable(feature = "rust1", since = "1.0.0")]
2226 impl<I
> ExactSizeIterator
for Take
<I
> where I
: ExactSizeIterator {}
2229 /// An iterator to maintain state while iterating another iterator
2230 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2231 #[stable(feature = "rust1", since = "1.0.0")]
2233 pub struct Scan
<I
, St
, F
> {
2237 /// The current internal state to be passed to the closure next.
2238 #[unstable(feature = "core")]
2242 #[stable(feature = "rust1", since = "1.0.0")]
2243 impl<B
, I
, St
, F
> Iterator
for Scan
<I
, St
, F
> where
2245 F
: FnMut(&mut St
, I
::Item
) -> Option
<B
>,
2250 fn next(&mut self) -> Option
<B
> {
2251 self.iter
.next().and_then(|a
| (self.f
)(&mut self.state
, a
))
2255 fn size_hint(&self) -> (usize, Option
<usize>) {
2256 let (_
, upper
) = self.iter
.size_hint();
2257 (0, upper
) // can't know a lower bound, due to the scan function
2261 /// An iterator that maps each element to an iterator,
2262 /// and yields the elements of the produced iterators
2264 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2265 #[stable(feature = "rust1", since = "1.0.0")]
2267 pub struct FlatMap
<I
, U
: IntoIterator
, F
> {
2270 frontiter
: Option
<U
::IntoIter
>,
2271 backiter
: Option
<U
::IntoIter
>,
2274 #[stable(feature = "rust1", since = "1.0.0")]
2275 impl<I
: Iterator
, U
: IntoIterator
, F
> Iterator
for FlatMap
<I
, U
, F
>
2276 where F
: FnMut(I
::Item
) -> U
,
2278 type Item
= U
::Item
;
2281 fn next(&mut self) -> Option
<U
::Item
> {
2283 if let Some(ref mut inner
) = self.frontiter
{
2284 if let Some(x
) = inner
.by_ref().next() {
2288 match self.iter
.next().map(|x
| (self.f
)(x
)) {
2289 None
=> return self.backiter
.as_mut().and_then(|it
| it
.next()),
2290 next
=> self.frontiter
= next
.map(IntoIterator
::into_iter
),
2296 fn size_hint(&self) -> (usize, Option
<usize>) {
2297 let (flo
, fhi
) = self.frontiter
.as_ref().map_or((0, Some(0)), |it
| it
.size_hint());
2298 let (blo
, bhi
) = self.backiter
.as_ref().map_or((0, Some(0)), |it
| it
.size_hint());
2299 let lo
= flo
.saturating_add(blo
);
2300 match (self.iter
.size_hint(), fhi
, bhi
) {
2301 ((0, Some(0)), Some(a
), Some(b
)) => (lo
, a
.checked_add(b
)),
2307 #[stable(feature = "rust1", since = "1.0.0")]
2308 impl<I
: DoubleEndedIterator
, U
, F
> DoubleEndedIterator
for FlatMap
<I
, U
, F
> where
2309 F
: FnMut(I
::Item
) -> U
,
2311 U
::IntoIter
: DoubleEndedIterator
2314 fn next_back(&mut self) -> Option
<U
::Item
> {
2316 if let Some(ref mut inner
) = self.backiter
{
2317 if let Some(y
) = inner
.next_back() {
2321 match self.iter
.next_back().map(|x
| (self.f
)(x
)) {
2322 None
=> return self.frontiter
.as_mut().and_then(|it
| it
.next_back()),
2323 next
=> self.backiter
= next
.map(IntoIterator
::into_iter
),
2329 /// An iterator that yields `None` forever after the underlying iterator
2330 /// yields `None` once.
2332 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2333 #[stable(feature = "rust1", since = "1.0.0")]
2334 pub struct Fuse
<I
> {
2339 #[stable(feature = "rust1", since = "1.0.0")]
2340 impl<I
> Iterator
for Fuse
<I
> where I
: Iterator
{
2341 type Item
= <I
as Iterator
>::Item
;
2344 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> {
2348 let next
= self.iter
.next();
2349 self.done
= next
.is_none();
2355 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
2359 let nth
= self.iter
.nth(n
);
2360 self.done
= nth
.is_none();
2366 fn last(self) -> Option
<I
::Item
> {
2375 fn count(self) -> usize {
2384 fn size_hint(&self) -> (usize, Option
<usize>) {
2388 self.iter
.size_hint()
2393 #[stable(feature = "rust1", since = "1.0.0")]
2394 impl<I
> DoubleEndedIterator
for Fuse
<I
> where I
: DoubleEndedIterator
{
2396 fn next_back(&mut self) -> Option
<<I
as Iterator
>::Item
> {
2400 let next
= self.iter
.next_back();
2401 self.done
= next
.is_none();
2407 // Allow RandomAccessIterators to be fused without affecting random-access behavior
2408 #[unstable(feature = "core", reason = "trait is experimental")]
2409 impl<I
> RandomAccessIterator
for Fuse
<I
> where I
: RandomAccessIterator
{
2411 fn indexable(&self) -> usize {
2412 self.iter
.indexable()
2416 fn idx(&mut self, index
: usize) -> Option
<<I
as Iterator
>::Item
> {
2417 self.iter
.idx(index
)
2421 #[stable(feature = "rust1", since = "1.0.0")]
2422 impl<I
> ExactSizeIterator
for Fuse
<I
> where I
: ExactSizeIterator {}
2425 /// Resets the `Fuse` such that the next call to `.next()` or
2426 /// `.next_back()` will call the underlying iterator again even if it
2427 /// previously returned `None`.
2429 #[unstable(feature = "core", reason = "seems marginal")]
2430 pub fn reset_fuse(&mut self) {
2435 /// An iterator that calls a function with a reference to each
2436 /// element before yielding it.
2437 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2438 #[stable(feature = "rust1", since = "1.0.0")]
2440 pub struct Inspect
<I
, F
> {
2445 impl<I
: Iterator
, F
> Inspect
<I
, F
> where F
: FnMut(&I
::Item
) {
2447 fn do_inspect(&mut self, elt
: Option
<I
::Item
>) -> Option
<I
::Item
> {
2448 if let Some(ref a
) = elt
{
2456 #[stable(feature = "rust1", since = "1.0.0")]
2457 impl<I
: Iterator
, F
> Iterator
for Inspect
<I
, F
> where F
: FnMut(&I
::Item
) {
2458 type Item
= I
::Item
;
2461 fn next(&mut self) -> Option
<I
::Item
> {
2462 let next
= self.iter
.next();
2463 self.do_inspect(next
)
2467 fn size_hint(&self) -> (usize, Option
<usize>) {
2468 self.iter
.size_hint()
2472 #[stable(feature = "rust1", since = "1.0.0")]
2473 impl<I
: DoubleEndedIterator
, F
> DoubleEndedIterator
for Inspect
<I
, F
>
2474 where F
: FnMut(&I
::Item
),
2477 fn next_back(&mut self) -> Option
<I
::Item
> {
2478 let next
= self.iter
.next_back();
2479 self.do_inspect(next
)
2483 #[unstable(feature = "core", reason = "trait is experimental")]
2484 impl<I
: RandomAccessIterator
, F
> RandomAccessIterator
for Inspect
<I
, F
>
2485 where F
: FnMut(&I
::Item
),
2488 fn indexable(&self) -> usize {
2489 self.iter
.indexable()
2493 fn idx(&mut self, index
: usize) -> Option
<I
::Item
> {
2494 let element
= self.iter
.idx(index
);
2495 self.do_inspect(element
)
2499 /// An iterator that passes mutable state to a closure and yields the result.
2503 /// An iterator that yields sequential Fibonacci numbers, and stops on overflow.
2506 /// #![feature(core)]
2507 /// use std::iter::Unfold;
2509 /// // This iterator will yield up to the last Fibonacci number before the max
2510 /// // value of `u32`. You can simply change `u32` to `u64` in this line if
2511 /// // you want higher values than that.
2512 /// let mut fibonacci = Unfold::new((Some(0u32), Some(1u32)),
2513 /// |&mut (ref mut x2, ref mut x1)| {
2514 /// // Attempt to get the next Fibonacci number
2515 /// // `x1` will be `None` if previously overflowed.
2516 /// let next = match (*x2, *x1) {
2517 /// (Some(x2), Some(x1)) => x2.checked_add(x1),
2521 /// // Shift left: ret <- x2 <- x1 <- next
2529 /// for i in fibonacci {
2530 /// println!("{}", i);
2533 #[unstable(feature = "core")]
2535 pub struct Unfold
<St
, F
> {
2537 /// Internal state that will be passed to the closure on the next iteration
2538 #[unstable(feature = "core")]
2542 #[unstable(feature = "core")]
2543 impl<A
, St
, F
> Unfold
<St
, F
> where F
: FnMut(&mut St
) -> Option
<A
> {
2544 /// Creates a new iterator with the specified closure as the "iterator
2545 /// function" and an initial state to eventually pass to the closure
2547 pub fn new(initial_state
: St
, f
: F
) -> Unfold
<St
, F
> {
2550 state
: initial_state
2555 #[stable(feature = "rust1", since = "1.0.0")]
2556 impl<A
, St
, F
> Iterator
for Unfold
<St
, F
> where F
: FnMut(&mut St
) -> Option
<A
> {
2560 fn next(&mut self) -> Option
<A
> {
2561 (self.f
)(&mut self.state
)
2565 fn size_hint(&self) -> (usize, Option
<usize>) {
2566 // no possible known bounds at this point
2571 /// Objects that can be stepped over in both directions.
2573 /// The `steps_between` function provides a way to efficiently compare
2574 /// two `Step` objects.
2575 #[unstable(feature = "step_trait",
2576 reason
= "likely to be replaced by finer-grained traits")]
2577 pub trait Step
: PartialOrd
{
2578 /// Steps `self` if possible.
2579 fn step(&self, by
: &Self) -> Option
<Self>;
2581 /// Returns the number of steps between two step objects. The count is
2582 /// inclusive of `start` and exclusive of `end`.
2584 /// Returns `None` if it is not possible to calculate `steps_between`
2585 /// without overflow.
2586 fn steps_between(start
: &Self, end
: &Self, by
: &Self) -> Option
<usize>;
2589 macro_rules
! step_impl_unsigned
{
2593 fn step(&self, by
: &$t
) -> Option
<$t
> {
2594 (*self).checked_add(*by
)
2597 #[allow(trivial_numeric_casts)]
2598 fn steps_between(start
: &$t
, end
: &$t
, by
: &$t
) -> Option
<usize> {
2599 if *by
== 0 { return None; }
2601 // Note: We assume $t <= usize here
2602 let diff
= (*end
- *start
) as usize;
2603 let by
= *by
as usize;
2616 macro_rules
! step_impl_signed
{
2620 fn step(&self, by
: &$t
) -> Option
<$t
> {
2621 (*self).checked_add(*by
)
2624 #[allow(trivial_numeric_casts)]
2625 fn steps_between(start
: &$t
, end
: &$t
, by
: &$t
) -> Option
<usize> {
2626 if *by
== 0 { return None; }
2627 let mut diff
: usize;
2628 let mut by_u
: usize;
2633 // Note: We assume $t <= isize here
2634 // Use .wrapping_sub and cast to usize to compute the
2635 // difference that may not fit inside the range of isize.
2636 diff
= (*end
as isize).wrapping_sub(*start
as isize) as usize;
2637 by_u
= *by
as usize;
2642 diff
= (*start
as isize).wrapping_sub(*end
as isize) as usize;
2643 by_u
= (*by
as isize).wrapping_mul(-1) as usize;
2645 if diff
% by_u
> 0 {
2646 Some(diff
/ by_u
+ 1)
2655 macro_rules
! step_impl_no_between
{
2659 fn step(&self, by
: &$t
) -> Option
<$t
> {
2660 (*self).checked_add(*by
)
2663 fn steps_between(_a
: &$t
, _b
: &$t
, _by
: &$t
) -> Option
<usize> {
2670 step_impl_unsigned
!(usize u8 u16 u32);
2671 step_impl_signed
!(isize i8 i16 i32);
2672 #[cfg(target_pointer_width = "64")]
2673 step_impl_unsigned
!(u64);
2674 #[cfg(target_pointer_width = "64")]
2675 step_impl_signed
!(i64);
2676 #[cfg(target_pointer_width = "32")]
2677 step_impl_no_between
!(u64 i64);
2679 /// An adapter for stepping range iterators by a custom amount.
2681 /// The resulting iterator handles overflow by stopping. The `A`
2682 /// parameter is the type being iterated over, while `R` is the range
2683 /// type (usually one of `std::ops::{Range, RangeFrom}`.
2685 #[unstable(feature = "step_by", reason = "recent addition")]
2686 pub struct StepBy
<A
, R
> {
2691 impl<A
: Step
> RangeFrom
<A
> {
2692 /// Creates an iterator starting at the same point, but stepping by
2693 /// the given amount at each iteration.
2698 /// for i in (0u8..).step_by(2) {
2699 /// println!("{}", i);
2703 /// This prints all even `u8` values.
2704 #[unstable(feature = "step_by", reason = "recent addition")]
2705 pub fn step_by(self, by
: A
) -> StepBy
<A
, Self> {
2713 #[allow(deprecated)]
2714 impl<A
: Step
> ops
::Range
<A
> {
2715 /// Creates an iterator with the same range, but stepping by the
2716 /// given amount at each iteration.
2718 /// The resulting iterator handles overflow by stopping.
2723 /// # #![feature(step_by, core)]
2724 /// for i in (0..10).step_by(2) {
2725 /// println!("{}", i);
2738 #[unstable(feature = "step_by", reason = "recent addition")]
2739 pub fn step_by(self, by
: A
) -> StepBy
<A
, Self> {
2747 #[stable(feature = "rust1", since = "1.0.0")]
2748 impl<A
> Iterator
for StepBy
<A
, RangeFrom
<A
>> where
2750 for<'a
> &'a A
: Add
<&'a A
, Output
= A
>
2755 fn next(&mut self) -> Option
<A
> {
2756 let mut n
= &self.range
.start
+ &self.step_by
;
2757 mem
::swap(&mut n
, &mut self.range
.start
);
2762 fn size_hint(&self) -> (usize, Option
<usize>) {
2763 (usize::MAX
, None
) // Too bad we can't specify an infinite lower bound
2767 /// An iterator over the range [start, stop]
2769 #[unstable(feature = "core",
2770 reason
= "likely to be replaced by range notation and adapters")]
2771 pub struct RangeInclusive
<A
> {
2772 range
: ops
::Range
<A
>,
2776 /// Returns an iterator over the range [start, stop].
2778 #[unstable(feature = "core",
2779 reason
= "likely to be replaced by range notation and adapters")]
2780 pub fn range_inclusive
<A
>(start
: A
, stop
: A
) -> RangeInclusive
<A
>
2781 where A
: Step
+ One
+ Clone
2789 #[unstable(feature = "core",
2790 reason
= "likely to be replaced by range notation and adapters")]
2791 impl<A
> Iterator
for RangeInclusive
<A
> where
2792 A
: PartialEq
+ Step
+ One
+ Clone
,
2793 for<'a
> &'a A
: Add
<&'a A
, Output
= A
>
2798 fn next(&mut self) -> Option
<A
> {
2799 self.range
.next().or_else(|| {
2800 if !self.done
&& self.range
.start
== self.range
.end
{
2802 Some(self.range
.end
.clone())
2810 fn size_hint(&self) -> (usize, Option
<usize>) {
2811 let (lo
, hi
) = self.range
.size_hint();
2815 let lo
= lo
.saturating_add(1);
2816 let hi
= hi
.and_then(|x
| x
.checked_add(1));
2822 #[unstable(feature = "core",
2823 reason
= "likely to be replaced by range notation and adapters")]
2824 impl<A
> DoubleEndedIterator
for RangeInclusive
<A
> where
2825 A
: PartialEq
+ Step
+ One
+ Clone
,
2826 for<'a
> &'a A
: Add
<&'a A
, Output
= A
>,
2827 for<'a
> &'a A
: Sub
<Output
=A
>
2830 fn next_back(&mut self) -> Option
<A
> {
2831 if self.range
.end
> self.range
.start
{
2832 let result
= self.range
.end
.clone();
2833 self.range
.end
= &self.range
.end
- &A
::one();
2835 } else if !self.done
&& self.range
.start
== self.range
.end
{
2837 Some(self.range
.end
.clone())
2844 #[stable(feature = "rust1", since = "1.0.0")]
2845 #[allow(deprecated)]
2846 impl<A
: Step
+ Zero
+ Clone
> Iterator
for StepBy
<A
, ops
::Range
<A
>> {
2850 fn next(&mut self) -> Option
<A
> {
2851 let rev
= self.step_by
< A
::zero();
2852 if (rev
&& self.range
.start
> self.range
.end
) ||
2853 (!rev
&& self.range
.start
< self.range
.end
)
2855 match self.range
.start
.step(&self.step_by
) {
2857 mem
::swap(&mut self.range
.start
, &mut n
);
2861 let mut n
= self.range
.end
.clone();
2862 mem
::swap(&mut self.range
.start
, &mut n
);
2872 fn size_hint(&self) -> (usize, Option
<usize>) {
2873 match Step
::steps_between(&self.range
.start
,
2876 Some(hint
) => (hint
, Some(hint
)),
2882 macro_rules
! range_exact_iter_impl
{
2884 #[stable(feature = "rust1", since = "1.0.0")]
2885 impl ExactSizeIterator
for ops
::Range
<$t
> { }
2889 #[stable(feature = "rust1", since = "1.0.0")]
2890 #[allow(deprecated)]
2891 impl<A
: Step
+ One
> Iterator
for ops
::Range
<A
> where
2892 for<'a
> &'a A
: Add
<&'a A
, Output
= A
>
2897 fn next(&mut self) -> Option
<A
> {
2898 if self.start
< self.end
{
2899 let mut n
= &self.start
+ &A
::one();
2900 mem
::swap(&mut n
, &mut self.start
);
2908 fn size_hint(&self) -> (usize, Option
<usize>) {
2909 match Step
::steps_between(&self.start
, &self.end
, &A
::one()) {
2910 Some(hint
) => (hint
, Some(hint
)),
2916 // Ranges of u64 and i64 are excluded because they cannot guarantee having
2917 // a length <= usize::MAX, which is required by ExactSizeIterator.
2918 range_exact_iter_impl
!(usize u8 u16 u32 isize i8 i16 i32);
2920 #[stable(feature = "rust1", since = "1.0.0")]
2921 #[allow(deprecated)]
2922 impl<A
: Step
+ One
+ Clone
> DoubleEndedIterator
for ops
::Range
<A
> where
2923 for<'a
> &'a A
: Add
<&'a A
, Output
= A
>,
2924 for<'a
> &'a A
: Sub
<&'a A
, Output
= A
>
2927 fn next_back(&mut self) -> Option
<A
> {
2928 if self.start
< self.end
{
2929 self.end
= &self.end
- &A
::one();
2930 Some(self.end
.clone())
2937 #[stable(feature = "rust1", since = "1.0.0")]
2938 #[allow(deprecated)]
2939 impl<A
: Step
+ One
> Iterator
for ops
::RangeFrom
<A
> where
2940 for<'a
> &'a A
: Add
<&'a A
, Output
= A
>
2945 fn next(&mut self) -> Option
<A
> {
2946 let mut n
= &self.start
+ &A
::one();
2947 mem
::swap(&mut n
, &mut self.start
);
2952 /// An iterator that repeats an element endlessly
2954 #[stable(feature = "rust1", since = "1.0.0")]
2955 pub struct Repeat
<A
> {
2959 #[stable(feature = "rust1", since = "1.0.0")]
2960 impl<A
: Clone
> Iterator
for Repeat
<A
> {
2964 fn next(&mut self) -> Option
<A
> { self.idx(0) }
2966 fn size_hint(&self) -> (usize, Option
<usize>) { (usize::MAX, None) }
2969 #[stable(feature = "rust1", since = "1.0.0")]
2970 impl<A
: Clone
> DoubleEndedIterator
for Repeat
<A
> {
2972 fn next_back(&mut self) -> Option
<A
> { self.idx(0) }
2975 #[unstable(feature = "core", reason = "trait is experimental")]
2976 impl<A
: Clone
> RandomAccessIterator
for Repeat
<A
> {
2978 fn indexable(&self) -> usize { usize::MAX }
2980 fn idx(&mut self, _
: usize) -> Option
<A
> { Some(self.element.clone()) }
2983 type IterateState
<T
, F
> = (F
, Option
<T
>, bool
);
2985 /// An iterator that repeatedly applies a given function, starting
2986 /// from a given seed value.
2987 #[unstable(feature = "core")]
2988 pub type Iterate
<T
, F
> = Unfold
<IterateState
<T
, F
>, fn(&mut IterateState
<T
, F
>) -> Option
<T
>>;
2990 /// Creates a new iterator that produces an infinite sequence of
2991 /// repeated applications of the given function `f`.
2992 #[unstable(feature = "core")]
2993 pub fn iterate
<T
, F
>(seed
: T
, f
: F
) -> Iterate
<T
, F
> where
2997 fn next
<T
, F
>(st
: &mut IterateState
<T
, F
>) -> Option
<T
> where
3001 let &mut (ref mut f
, ref mut val
, ref mut first
) = st
;
3004 } else if let Some(x
) = val
.take() {
3005 *val
= Some((*f
)(x
))
3010 // coerce to a fn pointer
3011 let next
: fn(&mut IterateState
<T
,F
>) -> Option
<T
> = next
;
3013 Unfold
::new((f
, Some(seed
), true), next
)
3016 /// Creates a new iterator that endlessly repeats the element `elt`.
3018 #[stable(feature = "rust1", since = "1.0.0")]
3019 pub fn repeat
<T
: Clone
>(elt
: T
) -> Repeat
<T
> {
3020 Repeat{element: elt}
3023 /// Functions for lexicographical ordering of sequences.
3025 /// Lexicographical ordering through `<`, `<=`, `>=`, `>` requires
3026 /// that the elements implement both `PartialEq` and `PartialOrd`.
3028 /// If two sequences are equal up until the point where one ends,
3029 /// the shorter sequence compares less.
3030 #[unstable(feature = "core", reason = "needs review and revision")]
3033 use cmp
::{Eq, Ord, PartialOrd, PartialEq}
;
3034 use cmp
::Ordering
::{Equal, Less, Greater}
;
3036 use option
::Option
::{Some, None}
;
3037 use super::Iterator
;
3039 /// Compare `a` and `b` for equality using `Eq`
3040 pub fn equals
<A
, L
, R
>(mut a
: L
, mut b
: R
) -> bool
where
3042 L
: Iterator
<Item
=A
>,
3043 R
: Iterator
<Item
=A
>,
3046 match (a
.next(), b
.next()) {
3047 (None
, None
) => return true,
3048 (None
, _
) | (_
, None
) => return false,
3049 (Some(x
), Some(y
)) => if x
!= y { return false }
,
3054 /// Order `a` and `b` lexicographically using `Ord`
3055 pub fn cmp
<A
, L
, R
>(mut a
: L
, mut b
: R
) -> cmp
::Ordering
where
3057 L
: Iterator
<Item
=A
>,
3058 R
: Iterator
<Item
=A
>,
3061 match (a
.next(), b
.next()) {
3062 (None
, None
) => return Equal
,
3063 (None
, _
) => return Less
,
3064 (_
, None
) => return Greater
,
3065 (Some(x
), Some(y
)) => match x
.cmp(&y
) {
3067 non_eq
=> return non_eq
,
3073 /// Order `a` and `b` lexicographically using `PartialOrd`
3074 pub fn partial_cmp
<L
: Iterator
, R
: Iterator
>(mut a
: L
, mut b
: R
) -> Option
<cmp
::Ordering
> where
3075 L
::Item
: PartialOrd
<R
::Item
>
3078 match (a
.next(), b
.next()) {
3079 (None
, None
) => return Some(Equal
),
3080 (None
, _
) => return Some(Less
),
3081 (_
, None
) => return Some(Greater
),
3082 (Some(x
), Some(y
)) => match x
.partial_cmp(&y
) {
3084 non_eq
=> return non_eq
,
3090 /// Compare `a` and `b` for equality (Using partial equality, `PartialEq`)
3091 pub fn eq
<L
: Iterator
, R
: Iterator
>(mut a
: L
, mut b
: R
) -> bool
where
3092 L
::Item
: PartialEq
<R
::Item
>,
3095 match (a
.next(), b
.next()) {
3096 (None
, None
) => return true,
3097 (None
, _
) | (_
, None
) => return false,
3098 (Some(x
), Some(y
)) => if !x
.eq(&y
) { return false }
,
3103 /// Compares `a` and `b` for nonequality (Using partial equality, `PartialEq`)
3104 pub fn ne
<L
: Iterator
, R
: Iterator
>(mut a
: L
, mut b
: R
) -> bool
where
3105 L
::Item
: PartialEq
<R
::Item
>,
3108 match (a
.next(), b
.next()) {
3109 (None
, None
) => return false,
3110 (None
, _
) | (_
, None
) => return true,
3111 (Some(x
), Some(y
)) => if x
.ne(&y
) { return true }
,
3116 /// Returns `a` < `b` lexicographically (Using partial order, `PartialOrd`)
3117 pub fn lt
<R
: Iterator
, L
: Iterator
>(mut a
: L
, mut b
: R
) -> bool
where
3118 L
::Item
: PartialOrd
<R
::Item
>,
3121 match (a
.next(), b
.next()) {
3122 (None
, None
) => return false,
3123 (None
, _
) => return true,
3124 (_
, None
) => return false,
3125 (Some(x
), Some(y
)) => if x
.ne(&y
) { return x.lt(&y) }
,
3130 /// Returns `a` <= `b` lexicographically (Using partial order, `PartialOrd`)
3131 pub fn le
<L
: Iterator
, R
: Iterator
>(mut a
: L
, mut b
: R
) -> bool
where
3132 L
::Item
: PartialOrd
<R
::Item
>,
3135 match (a
.next(), b
.next()) {
3136 (None
, None
) => return true,
3137 (None
, _
) => return true,
3138 (_
, None
) => return false,
3139 (Some(x
), Some(y
)) => if x
.ne(&y
) { return x.le(&y) }
,
3144 /// Returns `a` > `b` lexicographically (Using partial order, `PartialOrd`)
3145 pub fn gt
<L
: Iterator
, R
: Iterator
>(mut a
: L
, mut b
: R
) -> bool
where
3146 L
::Item
: PartialOrd
<R
::Item
>,
3149 match (a
.next(), b
.next()) {
3150 (None
, None
) => return false,
3151 (None
, _
) => return false,
3152 (_
, None
) => return true,
3153 (Some(x
), Some(y
)) => if x
.ne(&y
) { return x.gt(&y) }
,
3158 /// Returns `a` >= `b` lexicographically (Using partial order, `PartialOrd`)
3159 pub fn ge
<L
: Iterator
, R
: Iterator
>(mut a
: L
, mut b
: R
) -> bool
where
3160 L
::Item
: PartialOrd
<R
::Item
>,
3163 match (a
.next(), b
.next()) {
3164 (None
, None
) => return true,
3165 (None
, _
) => return false,
3166 (_
, None
) => return true,
3167 (Some(x
), Some(y
)) => if x
.ne(&y
) { return x.ge(&y) }
,