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);
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);
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 /// let xs = [100, 200, 300];
330 /// let mut it = xs.iter().cloned().peekable();
331 /// assert_eq!(*it.peek().unwrap(), 100);
332 /// assert_eq!(it.next().unwrap(), 100);
333 /// assert_eq!(it.next().unwrap(), 200);
334 /// assert_eq!(*it.peek().unwrap(), 300);
335 /// assert_eq!(*it.peek().unwrap(), 300);
336 /// assert_eq!(it.next().unwrap(), 300);
337 /// assert!(it.peek().is_none());
338 /// assert!(it.next().is_none());
341 #[stable(feature = "rust1", since = "1.0.0")]
342 fn peekable(self) -> Peekable<Self> where Self: Sized {
343 Peekable{iter: self, peeked: None}
346 /// Creates an iterator that invokes the predicate on elements
347 /// until it returns false. Once the predicate returns false, that
348 /// element and all further elements are yielded.
353 /// let a = [1, 2, 3, 4, 5];
354 /// let mut it = a.iter().skip_while(|&a| *a < 3);
355 /// assert_eq!(it.next(), Some(&3));
356 /// assert_eq!(it.next(), Some(&4));
357 /// assert_eq!(it.next(), Some(&5));
358 /// assert!(it.next().is_none());
361 #[stable(feature = "rust1", since = "1.0.0")]
362 fn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P> where
363 Self: Sized, P: FnMut(&Self::Item) -> bool,
365 SkipWhile{iter: self, flag: false, predicate: predicate}
368 /// Creates an iterator that yields elements so long as the predicate
369 /// returns true. After the predicate returns false for the first time, no
370 /// further elements will be yielded.
375 /// let a = [1, 2, 3, 4, 5];
376 /// let mut it = a.iter().take_while(|&a| *a < 3);
377 /// assert_eq!(it.next(), Some(&1));
378 /// assert_eq!(it.next(), Some(&2));
379 /// assert!(it.next().is_none());
382 #[stable(feature = "rust1", since = "1.0.0")]
383 fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P> where
384 Self: Sized, P: FnMut(&Self::Item) -> bool,
386 TakeWhile{iter: self, flag: false, predicate: predicate}
389 /// Creates an iterator that skips the first `n` elements of this iterator,
390 /// and then yields all further items.
395 /// let a = [1, 2, 3, 4, 5];
396 /// let mut it = a.iter().skip(3);
397 /// assert_eq!(it.next(), Some(&4));
398 /// assert_eq!(it.next(), Some(&5));
399 /// assert!(it.next().is_none());
402 #[stable(feature = "rust1", since = "1.0.0")]
403 fn skip(self, n: usize) -> Skip<Self> where Self: Sized {
404 Skip{iter: self, n: n}
407 /// Creates an iterator that yields the first `n` elements of this
413 /// let a = [1, 2, 3, 4, 5];
414 /// let mut it = a.iter().take(3);
415 /// assert_eq!(it.next(), Some(&1));
416 /// assert_eq!(it.next(), Some(&2));
417 /// assert_eq!(it.next(), Some(&3));
418 /// assert!(it.next().is_none());
421 #[stable(feature = "rust1", since = "1.0.0")]
422 fn take(self, n: usize) -> Take<Self> where Self: Sized, {
423 Take{iter: self, n: n}
426 /// Creates a new iterator that behaves in a similar fashion to fold.
427 /// There is a state which is passed between each iteration and can be
428 /// mutated as necessary. The yielded values from the closure are yielded
429 /// from the Scan instance when not `None`.
434 /// let a = [1, 2, 3, 4, 5];
435 /// let mut it = a.iter().scan(1, |fac, &x| {
439 /// assert_eq!(it.next(), Some(1));
440 /// assert_eq!(it.next(), Some(2));
441 /// assert_eq!(it.next(), Some(6));
442 /// assert_eq!(it.next(), Some(24));
443 /// assert_eq!(it.next(), Some(120));
444 /// assert!(it.next().is_none());
447 #[stable(feature = "rust1", since = "1.0.0")]
448 fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>
449 where Self: Sized, F: FnMut(&mut St, Self::Item) -> Option<B>,
451 Scan{iter: self, f: f, state: initial_state}
454 /// Takes a function that maps each element to a new iterator and yields
455 /// all the elements of the produced iterators.
457 /// This is useful for unraveling nested structures.
462 /// let words = ["alpha", "beta", "gamma"];
463 /// let merged: String = words.iter()
464 /// .flat_map(|s| s.chars())
466 /// assert_eq!(merged, "alphabetagamma");
469 #[stable(feature = "rust1", since = "1.0.0")]
470 fn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F>
471 where Self: Sized, U: IntoIterator, F: FnMut(Self::Item) -> U,
473 FlatMap{iter: self, f: f, frontiter: None, backiter: None }
476 /// Creates an iterator that yields `None` forever after the underlying
477 /// iterator yields `None`. Random-access iterator behavior is not
478 /// affected, only single and double-ended iterator behavior.
483 /// fn process<U: Iterator<Item=i32>>(it: U) -> i32 {
484 /// let mut it = it.fuse();
486 /// for x in it.by_ref() {
492 /// // did we exhaust the iterator?
493 /// if it.next().is_none() {
498 /// let x = vec![1, 2, 3, 7, 8, 9];
499 /// assert_eq!(process(x.into_iter()), 6);
500 /// let x = vec![1, 2, 3];
501 /// assert_eq!(process(x.into_iter()), 1006);
504 #[stable(feature = "rust1", since = "1.0.0")]
505 fn fuse(self) -> Fuse<Self> where Self: Sized {
506 Fuse{iter: self, done: false}
509 /// Creates an iterator that calls a function with a reference to each
510 /// element before yielding it. This is often useful for debugging an
511 /// iterator pipeline.
516 /// let a = [1, 4, 2, 3, 8, 9, 6];
517 /// let sum: i32 = a.iter()
519 /// .inspect(|&x| println!("filtering {}", x))
520 /// .filter(|&x| x % 2 == 0)
521 /// .inspect(|&x| println!("{} made it through", x))
522 /// .fold(0, |sum, i| sum + i);
523 /// println!("{}", sum);
526 #[stable(feature = "rust1", since = "1.0.0")]
527 fn inspect<F>(self, f: F) -> Inspect<Self, F> where
528 Self: Sized, F: FnMut(&Self::Item),
530 Inspect{iter: self, f: f}
533 /// Creates a wrapper around a mutable reference to the iterator.
535 /// This is useful to allow applying iterator adaptors while still
536 /// retaining ownership of the original iterator value.
541 /// let mut it = 0..10;
542 /// // sum the first five values
543 /// let partial_sum = it.by_ref().take(5).fold(0, |a, b| a + b);
544 /// assert_eq!(partial_sum, 10);
545 /// assert_eq!(it.next(), Some(5));
547 #[stable(feature = "rust1", since = "1.0.0")]
548 fn by_ref(&mut self) -> &mut Self where Self: Sized { self }
550 /// Loops through the entire iterator, collecting all of the elements into
551 /// a container implementing `FromIterator`.
556 /// let expected = [1, 2, 3, 4, 5];
557 /// let actual: Vec<_> = expected.iter().cloned().collect();
558 /// assert_eq!(actual, expected);
561 #[stable(feature = "rust1", since = "1.0.0")]
562 fn collect<B: FromIterator<Self::Item>>(self) -> B where Self: Sized {
563 FromIterator::from_iter(self)
566 /// Loops through the entire iterator, collecting all of the elements into
567 /// one of two containers, depending on a predicate. The elements of the
568 /// first container satisfy the predicate, while the elements of the second
572 /// let vec = vec![1, 2, 3, 4];
573 /// let (even, odd): (Vec<_>, Vec<_>) = vec.into_iter().partition(|&n| n % 2 == 0);
574 /// assert_eq!(even, [2, 4]);
575 /// assert_eq!(odd, [1, 3]);
577 #[stable(feature = "rust1", since = "1.0.0")]
578 fn partition<B, F>(self, mut f: F) -> (B, B) where
580 B: Default + Extend<Self::Item>,
581 F: FnMut(&Self::Item) -> bool
583 let mut left: B = Default::default();
584 let mut right: B = Default::default();
590 right.extend(Some(x))
597 /// Performs a fold operation over the entire iterator, returning the
598 /// eventual state at the end of the iteration.
600 /// This operation is sometimes called 'reduce' or 'inject'.
605 /// let a = [1, 2, 3, 4, 5];
606 /// assert_eq!(a.iter().fold(0, |acc, &item| acc + item), 15);
609 #[stable(feature = "rust1", since = "1.0.0")]
610 fn fold<B, F>(self, init: B, mut f: F) -> B where
611 Self: Sized, F: FnMut(B, Self::Item) -> B,
613 let mut accum = init;
620 /// Tests whether the predicate holds true for all elements in the iterator.
625 /// let a = [1, 2, 3, 4, 5];
626 /// assert!(a.iter().all(|x| *x > 0));
627 /// assert!(!a.iter().all(|x| *x > 2));
630 #[stable(feature = "rust1", since = "1.0.0")]
631 fn all<F>(&mut self, mut f: F) -> bool where
632 Self: Sized, F: FnMut(Self::Item) -> bool
634 for x in self.by_ref() {
642 /// Tests whether any element of an iterator satisfies the specified
645 /// Does not consume the iterator past the first found element.
650 /// let a = [1, 2, 3, 4, 5];
651 /// let mut it = a.iter();
652 /// assert!(it.any(|x| *x == 3));
653 /// assert_eq!(it.collect::<Vec<_>>(), [&4, &5]);
656 #[stable(feature = "rust1", since = "1.0.0")]
657 fn any<F>(&mut self, mut f: F) -> bool where
659 F: FnMut(Self::Item) -> bool
661 for x in self.by_ref() {
669 /// Returns the first element satisfying the specified predicate.
671 /// Does not consume the iterator past the first found element.
676 /// let a = [1, 2, 3, 4, 5];
677 /// let mut it = a.iter();
678 /// assert_eq!(it.find(|&x| *x == 3), Some(&3));
679 /// assert_eq!(it.collect::<Vec<_>>(), [&4, &5]);
681 #[stable(feature = "rust1", since = "1.0.0")]
682 fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
684 P: FnMut(&Self::Item) -> bool,
686 for x in self.by_ref() {
687 if predicate(&x) { return Some(x) }
692 /// Returns the index of the first element satisfying the specified predicate
694 /// Does not consume the iterator past the first found element.
696 /// # Overflow Behavior
698 /// The method does no guarding against overflows, so if there are more
699 /// than `usize::MAX` non-matching elements, it either produces the wrong
700 /// result or panics. If debug assertions are enabled, a panic is
705 /// This functions might panic if the iterator has more than `usize::MAX`
706 /// non-matching elements.
711 /// let a = [1, 2, 3, 4, 5];
712 /// let mut it = a.iter();
713 /// assert_eq!(it.position(|x| *x == 3), Some(2));
714 /// assert_eq!(it.collect::<Vec<_>>(), [&4, &5]);
716 #[stable(feature = "rust1", since = "1.0.0")]
717 fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
719 P: FnMut(Self::Item) -> bool,
721 // `enumerate` might overflow.
722 for (i, x) in self.by_ref().enumerate() {
730 /// Returns the index of the last element satisfying the specified predicate
732 /// If no element matches, `None` is returned.
734 /// Does not consume the iterator *before* the first found element.
739 /// let a = [1, 2, 2, 4, 5];
740 /// let mut it = a.iter();
741 /// assert_eq!(it.rposition(|x| *x == 2), Some(2));
742 /// assert_eq!(it.collect::<Vec<_>>(), [&1, &2]);
744 #[stable(feature = "rust1", since = "1.0.0")]
745 fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
746 P: FnMut(Self::Item) -> bool,
747 Self: Sized + ExactSizeIterator + DoubleEndedIterator
749 let mut i = self.len();
751 while let Some(v) = self.next_back() {
755 // No need for an overflow check here, because `ExactSizeIterator`
756 // implies that the number of elements fits into a `usize`.
762 /// Consumes the entire iterator to return the maximum element.
764 /// Returns the rightmost element if the comparison determines two elements
765 /// to be equally maximum.
770 /// let a = [1, 2, 3, 4, 5];
771 /// assert_eq!(a.iter().max(), Some(&5));
774 #[stable(feature = "rust1", since = "1.0.0")]
775 fn max(self) -> Option<Self::Item> where Self: Sized, Self::Item: Ord
779 // switch to y even if it is only equal, to preserve
781 |_, x, _, y| *x <= *y)
785 /// Consumes the entire iterator to return the minimum element.
787 /// Returns the leftmost element if the comparison determines two elements
788 /// to be equally minimum.
793 /// let a = [1, 2, 3, 4, 5];
794 /// assert_eq!(a.iter().min(), Some(&1));
797 #[stable(feature = "rust1", since = "1.0.0")]
798 fn min(self) -> Option<Self::Item> where Self: Sized, Self::Item: Ord
802 // only switch to y if it is strictly smaller, to
803 // preserve stability.
804 |_, x, _, y| *x > *y)
808 /// `min_max` finds the minimum and maximum elements in the iterator.
810 /// The return type `MinMaxResult` is an enum of three variants:
812 /// - `NoElements` if the iterator is empty.
813 /// - `OneElement(x)` if the iterator has exactly one element.
814 /// - `MinMax(x, y)` is returned otherwise, where `x <= y`. Two
815 /// values are equal if and only if there is more than one
816 /// element in the iterator and all elements are equal.
818 /// On an iterator of length `n`, `min_max` does `1.5 * n` comparisons,
819 /// and so is faster than calling `min` and `max` separately which does `2 *
825 /// # #![feature(core)]
826 /// use std::iter::MinMaxResult::{NoElements, OneElement, MinMax};
828 /// let a: [i32; 0] = [];
829 /// assert_eq!(a.iter().min_max(), NoElements);
832 /// assert_eq!(a.iter().min_max(), OneElement(&1));
834 /// let a = [1, 2, 3, 4, 5];
835 /// assert_eq!(a.iter().min_max(), MinMax(&1, &5));
837 /// let a = [1, 1, 1, 1];
838 /// assert_eq!(a.iter().min_max(), MinMax(&1, &1));
840 #[unstable(feature = "core", reason = "return type may change")]
841 fn min_max(mut self) -> MinMaxResult<Self::Item> where Self: Sized, Self::Item: Ord
843 let (mut min, mut max) = match self.next() {
844 None => return NoElements,
847 None => return OneElement(x),
848 Some(y) => if x <= y {(x, y)} else {(y, x)}
854 // `first` and `second` are the two next elements we want to look
855 // at. We first compare `first` and `second` (#1). The smaller one
856 // is then compared to current minimum (#2). The larger one is
857 // compared to current maximum (#3). This way we do 3 comparisons
859 let first = match self.next() {
863 let second = match self.next() {
867 } else if first >= max {
875 if first < min { min = first }
876 if second >= max { max = second }
878 if second < min { min = second }
879 if first >= max { max = first }
886 /// Returns the element that gives the maximum value from the
887 /// specified function.
889 /// Returns the rightmost element if the comparison determines two elements
890 /// to be equally maximum.
895 /// # #![feature(core)]
896 /// let a = [-3_i32, 0, 1, 5, -10];
897 /// assert_eq!(*a.iter().max_by(|x| x.abs()).unwrap(), -10);
900 #[unstable(feature = "core",
901 reason = "may want to produce an Ordering directly; see #15311")]
902 fn max_by<B: Ord, F>(self, f: F) -> Option<Self::Item> where
904 F: FnMut(&Self::Item) -> B,
908 // switch to y even if it is only equal, to preserve
910 |x_p, _, y_p, _| x_p <= y_p)
914 /// Returns the element that gives the minimum value from the
915 /// specified function.
917 /// Returns the leftmost element if the comparison determines two elements
918 /// to be equally minimum.
923 /// # #![feature(core)]
924 /// let a = [-3_i32, 0, 1, 5, -10];
925 /// assert_eq!(*a.iter().min_by(|x| x.abs()).unwrap(), 0);
928 #[unstable(feature = "core",
929 reason = "may want to produce an Ordering directly; see #15311")]
930 fn min_by<B: Ord, F>(self, f: F) -> Option<Self::Item> where
932 F: FnMut(&Self::Item) -> B,
936 // only switch to y if it is strictly smaller, to
937 // preserve stability.
938 |x_p, _, y_p, _| x_p > y_p)
942 /// Change the direction of the iterator
944 /// The flipped iterator swaps the ends on an iterator that can already
945 /// be iterated from the front and from the back.
948 /// If the iterator also implements RandomAccessIterator, the flipped
949 /// iterator is also random access, with the indices starting at the back
950 /// of the original iterator.
952 /// Note: Random access with flipped indices still only applies to the first
953 /// `std::usize::MAX` elements of the original iterator.
955 #[stable(feature = "rust1", since = "1.0.0")]
956 fn rev(self) -> Rev<Self> where Self: Sized + DoubleEndedIterator {
960 /// Converts an iterator of pairs into a pair of containers.
962 /// Loops through the entire iterator, collecting the first component of
963 /// each item into one new container, and the second component into another.
968 /// let a = [(1, 2), (3, 4)];
969 /// let (left, right): (Vec<_>, Vec<_>) = a.iter().cloned().unzip();
970 /// assert_eq!(left, [1, 3]);
971 /// assert_eq!(right, [2, 4]);
973 #[stable(feature = "rust1", since = "1.0.0")]
974 fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB) where
975 FromA: Default + Extend<A>,
976 FromB: Default + Extend<B>,
977 Self: Sized + Iterator<Item=(A, B)>,
979 struct SizeHint<A>(usize, Option<usize>, marker::PhantomData<A>);
980 impl<A> Iterator for SizeHint<A> {
983 fn next(&mut self) -> Option<A> { None }
984 fn size_hint(&self) -> (usize, Option<usize>) {
989 let (lo, hi) = self.size_hint();
990 let mut ts: FromA = Default::default();
991 let mut us: FromB = Default::default();
993 ts.extend(SizeHint(lo, hi, marker::PhantomData));
994 us.extend(SizeHint(lo, hi, marker::PhantomData));
1004 /// Creates an iterator that clones the elements it yields.
1006 /// This is useful for converting an Iterator<&T> to an Iterator<T>,
1007 /// so it's a more convenient form of `map(|&x| x)`.
1012 /// let a = [0, 1, 2];
1013 /// let v_cloned: Vec<_> = a.iter().cloned().collect();
1014 /// let v_map: Vec<_> = a.iter().map(|&x| x).collect();
1015 /// assert_eq!(v_cloned, v_map);
1017 #[stable(feature = "rust1", since = "1.0.0")]
1018 fn cloned<'a, T: 'a>(self) -> Cloned<Self>
1019 where Self: Sized + Iterator<Item=&'a T>, T: Clone
1024 /// Repeats an iterator endlessly
1030 /// let mut it = a.iter().cycle();
1031 /// assert_eq!(it.next(), Some(&1));
1032 /// assert_eq!(it.next(), Some(&2));
1033 /// assert_eq!(it.next(), Some(&1));
1035 #[stable(feature = "rust1", since = "1.0.0")]
1037 fn cycle(self) -> Cycle<Self> where Self: Sized + Clone {
1038 Cycle{orig: self.clone(), iter: self}
1041 /// Use an iterator to reverse a container in place.
1042 #[unstable(feature = "core",
1043 reason = "uncertain about placement or widespread use")]
1044 fn reverse_in_place<'a, T: 'a>(&mut self) where
1045 Self: Sized + Iterator<Item=&'a mut T> + DoubleEndedIterator
1048 match (self.next(), self.next_back()) {
1049 (Some(x), Some(y)) => mem::swap(x, y),
1055 /// Iterates over the entire iterator, summing up all the elements
1060 /// # #![feature(core)]
1061 /// let a = [1, 2, 3, 4, 5];
1062 /// let it = a.iter();
1063 /// assert_eq!(it.sum::<i32>(), 15);
1065 #[unstable(feature="core")]
1066 fn sum<S=<Self as Iterator>::Item>(self) -> S where
1067 S: Add<Self::Item, Output=S> + Zero,
1070 self.fold(Zero::zero(), |s, e| s + e)
1073 /// Iterates over the entire iterator, multiplying all the elements
1078 /// # #![feature(core)]
1079 /// fn factorial(n: u32) -> u32 {
1080 /// (1..).take_while(|&i| i <= n).product()
1082 /// assert_eq!(factorial(0), 1);
1083 /// assert_eq!(factorial(1), 1);
1084 /// assert_eq!(factorial(5), 120);
1086 #[unstable(feature="core")]
1087 fn product<P=<Self as Iterator>::Item>(self) -> P where
1088 P: Mul<Self::Item, Output=P> + One,
1091 self.fold(One::one(), |p, e| p * e)
1095 /// Select an element from an iterator based on the given projection
1096 /// and "comparison" function.
1098 /// This is an idiosyncratic helper to try to factor out the
1099 /// commonalities of {max,min}{,_by}. In particular, this avoids
1100 /// having to implement optimisations several times.
1102 fn select_fold1<I,B, FProj, FCmp>(mut it: I,
1104 mut f_cmp: FCmp) -> Option<(B, I::Item)>
1106 FProj: FnMut(&I::Item) -> B,
1107 FCmp: FnMut(&B, &I::Item, &B, &I::Item) -> bool
1109 // start with the first element as our selection. This avoids
1110 // having to use `Option`s inside the loop, translating to a
1111 // sizeable performance gain (6x in one case).
1112 it.next().map(|mut sel| {
1113 let mut sel_p = f_proj(&sel);
1116 let x_p = f_proj(&x);
1117 if f_cmp(&sel_p, &sel, &x_p, &x) {
1126 #[stable(feature = "rust1", since = "1.0.0")]
1127 impl<'a, I: Iterator + ?Sized> Iterator for &'a mut I {
1128 type Item = I::Item;
1129 fn next(&mut self) -> Option<I::Item> { (**self).next() }
1130 fn size_hint(&self) -> (usize, Option<usize>) { (**self).size_hint() }
1133 /// Conversion from an `Iterator`
1134 #[stable(feature = "rust1", since = "1.0.0")]
1135 #[rustc_on_unimplemented="a collection of type `{Self}` cannot be \
1136 built from an iterator over elements of type `{A}`"]
1137 pub trait FromIterator<A> {
1138 /// Builds a container with elements from something iterable.
1143 /// use std::collections::HashSet;
1144 /// use std::iter::FromIterator;
1146 /// let colors_vec = vec!["red", "red", "yellow", "blue"];
1147 /// let colors_set = HashSet::<&str>::from_iter(colors_vec);
1148 /// assert_eq!(colors_set.len(), 3);
1151 /// `FromIterator` is more commonly used implicitly via the
1152 /// `Iterator::collect` method:
1155 /// use std::collections::HashSet;
1157 /// let colors_vec = vec!["red", "red", "yellow", "blue"];
1158 /// let colors_set = colors_vec.into_iter().collect::<HashSet<&str>>();
1159 /// assert_eq!(colors_set.len(), 3);
1161 #[stable(feature = "rust1", since = "1.0.0")]
1162 fn from_iter<T: IntoIterator<Item=A>>(iterator: T) -> Self;
1165 /// Conversion into an `Iterator`
1167 /// Implementing this trait allows you to use your type with Rust's `for` loop. See
1168 /// the [module level documentation](index.html) for more details.
1169 #[stable(feature = "rust1", since = "1.0.0")]
1170 pub trait IntoIterator {
1171 /// The type of the elements being iterated
1172 #[stable(feature = "rust1", since = "1.0.0")]
1175 /// A container for iterating over elements of type `Item`
1176 #[stable(feature = "rust1", since = "1.0.0")]
1177 type IntoIter: Iterator<Item=Self::Item>;
1179 /// Consumes `Self` and returns an iterator over it
1180 #[stable(feature = "rust1", since = "1.0.0")]
1181 fn into_iter(self) -> Self::IntoIter;
1184 #[stable(feature = "rust1", since = "1.0.0")]
1185 impl<I: Iterator> IntoIterator for I {
1186 type Item = I::Item;
1189 fn into_iter(self) -> I {
1194 /// A type growable from an `Iterator` implementation
1195 #[stable(feature = "rust1", since = "1.0.0")]
1196 pub trait Extend<A> {
1197 /// Extends a container with the elements yielded by an arbitrary iterator
1198 #[stable(feature = "rust1", since = "1.0.0")]
1199 fn extend<T: IntoIterator<Item=A>>(&mut self, iterable: T);
1202 /// A range iterator able to yield elements from both ends
1204 /// A `DoubleEndedIterator` can be thought of as a deque in that `next()` and
1205 /// `next_back()` exhaust elements from the *same* range, and do not work
1206 /// independently of each other.
1207 #[stable(feature = "rust1", since = "1.0.0")]
1208 pub trait DoubleEndedIterator: Iterator {
1209 /// Yields an element from the end of the range, returning `None` if the
1211 #[stable(feature = "rust1", since = "1.0.0")]
1212 fn next_back(&mut self) -> Option<Self::Item>;
1215 #[stable(feature = "rust1", since = "1.0.0")]
1216 impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I {
1217 fn next_back(&mut self) -> Option<I::Item> { (**self).next_back() }
1220 /// An object implementing random access indexing by `usize`
1222 /// A `RandomAccessIterator` should be either infinite or a
1223 /// `DoubleEndedIterator`. Calling `next()` or `next_back()` on a
1224 /// `RandomAccessIterator` reduces the indexable range accordingly. That is,
1225 /// `it.idx(1)` will become `it.idx(0)` after `it.next()` is called.
1226 #[unstable(feature = "core",
1227 reason = "not widely used, may be better decomposed into Index \
1228 and ExactSizeIterator")]
1229 pub trait RandomAccessIterator: Iterator {
1230 /// Returns the number of indexable elements. At most `std::usize::MAX`
1231 /// elements are indexable, even if the iterator represents a longer range.
1232 fn indexable(&self) -> usize;
1234 /// Returns an element at an index, or `None` if the index is out of bounds
1235 fn idx(&mut self, index: usize) -> Option<Self::Item>;
1238 /// An iterator that knows its exact length
1240 /// This trait is a helper for iterators like the vector iterator, so that
1241 /// it can support double-ended enumeration.
1243 /// `Iterator::size_hint` *must* return the exact size of the iterator.
1244 /// Note that the size must fit in `usize`.
1245 #[stable(feature = "rust1", since = "1.0.0")]
1246 pub trait ExactSizeIterator: Iterator {
1248 #[stable(feature = "rust1", since = "1.0.0")]
1249 /// Returns the exact length of the iterator.
1250 fn len(&self) -> usize {
1251 let (lower, upper) = self.size_hint();
1252 // Note: This assertion is overly defensive, but it checks the invariant
1253 // guaranteed by the trait. If this trait were rust-internal,
1254 // we could use debug_assert!; assert_eq! will check all Rust user
1255 // implementations too.
1256 assert_eq!(upper, Some(lower));
1261 #[stable(feature = "rust1", since = "1.0.0")]
1262 impl<'a, I: ExactSizeIterator + ?Sized> ExactSizeIterator for &'a mut I {}
1264 // All adaptors that preserve the size of the wrapped iterator are fine
1265 // Adaptors that may overflow in `size_hint` are not, i.e. `Chain`.
1266 #[stable(feature = "rust1", since = "1.0.0")]
1267 impl<I> ExactSizeIterator for Enumerate<I> where I: ExactSizeIterator {}
1268 #[stable(feature = "rust1", since = "1.0.0")]
1269 impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F> where
1272 #[stable(feature = "rust1", since = "1.0.0")]
1273 impl<I> ExactSizeIterator for Rev<I>
1274 where I: ExactSizeIterator + DoubleEndedIterator {}
1275 #[stable(feature = "rust1", since = "1.0.0")]
1276 impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F> where
1277 F: FnMut(I::Item) -> B,
1279 #[stable(feature = "rust1", since = "1.0.0")]
1280 impl<A, B> ExactSizeIterator for Zip<A, B>
1281 where A: ExactSizeIterator, B: ExactSizeIterator {}
1283 /// An double-ended iterator with the direction inverted
1285 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1286 #[stable(feature = "rust1", since = "1.0.0")]
1291 #[stable(feature = "rust1", since = "1.0.0")]
1292 impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
1293 type Item = <I as Iterator>::Item;
1296 fn next(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next_back() }
1298 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
1301 #[stable(feature = "rust1", since = "1.0.0")]
1302 impl<I> DoubleEndedIterator for Rev<I> where I: DoubleEndedIterator {
1304 fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next() }
1307 #[unstable(feature = "core", reason = "trait is experimental")]
1308 impl<I> RandomAccessIterator for Rev<I>
1309 where I: DoubleEndedIterator + RandomAccessIterator
1312 fn indexable(&self) -> usize { self.iter.indexable() }
1314 fn idx(&mut self, index: usize) -> Option<<I as Iterator>::Item> {
1315 let amt = self.indexable();
1317 self.iter.idx(amt - index - 1)
1324 /// `MinMaxResult` is an enum returned by `min_max`. See `Iterator::min_max` for
1326 #[derive(Clone, PartialEq, Debug)]
1327 #[unstable(feature = "core",
1328 reason = "unclear whether such a fine-grained result is widely useful")]
1329 pub enum MinMaxResult<T> {
1333 /// Iterator with one element, so the minimum and maximum are the same
1336 /// More than one element in the iterator, the first element is not larger
1341 impl<T: Clone> MinMaxResult<T> {
1342 /// `into_option` creates an `Option` of type `(T,T)`. The returned `Option`
1343 /// has variant `None` if and only if the `MinMaxResult` has variant
1344 /// `NoElements`. Otherwise variant `Some(x,y)` is returned where `x <= y`.
1345 /// If `MinMaxResult` has variant `OneElement(x)`, performing this operation
1346 /// will make one clone of `x`.
1351 /// # #![feature(core)]
1352 /// use std::iter::MinMaxResult::{self, NoElements, OneElement, MinMax};
1354 /// let r: MinMaxResult<i32> = NoElements;
1355 /// assert_eq!(r.into_option(), None);
1357 /// let r = OneElement(1);
1358 /// assert_eq!(r.into_option(), Some((1, 1)));
1360 /// let r = MinMax(1, 2);
1361 /// assert_eq!(r.into_option(), Some((1, 2)));
1363 #[unstable(feature = "core", reason = "type is unstable")]
1364 pub fn into_option(self) -> Option<(T,T)> {
1367 OneElement(x) => Some((x.clone(), x)),
1368 MinMax(x, y) => Some((x, y))
1373 /// An iterator that clones the elements of an underlying iterator
1374 #[stable(feature = "iter_cloned", since = "1.1.0")]
1375 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1377 pub struct Cloned<I> {
1381 #[stable(feature = "rust1", since = "1.0.0")]
1382 impl<'a, I, T: 'a> Iterator for Cloned<I>
1383 where I: Iterator<Item=&'a T>, T: Clone
1387 fn next(&mut self) -> Option<T> {
1388 self.it.next().cloned()
1391 fn size_hint(&self) -> (usize, Option<usize>) {
1396 #[stable(feature = "rust1", since = "1.0.0")]
1397 impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
1398 where I: DoubleEndedIterator<Item=&'a T>, T: Clone
1400 fn next_back(&mut self) -> Option<T> {
1401 self.it.next_back().cloned()
1405 #[stable(feature = "rust1", since = "1.0.0")]
1406 impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
1407 where I: ExactSizeIterator<Item=&'a T>, T: Clone
1410 #[unstable(feature = "core", reason = "trait is experimental")]
1411 impl<'a, I, T: 'a> RandomAccessIterator for Cloned<I>
1412 where I: RandomAccessIterator<Item=&'a T>, T: Clone
1415 fn indexable(&self) -> usize {
1420 fn idx(&mut self, index: usize) -> Option<T> {
1421 self.it.idx(index).cloned()
1425 /// An iterator that repeats endlessly
1427 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1428 #[stable(feature = "rust1", since = "1.0.0")]
1429 pub struct Cycle<I> {
1434 #[stable(feature = "rust1", since = "1.0.0")]
1435 impl<I> Iterator for Cycle<I> where I: Clone + Iterator {
1436 type Item = <I as Iterator>::Item;
1439 fn next(&mut self) -> Option<<I as Iterator>::Item> {
1440 match self.iter.next() {
1441 None => { self.iter = self.orig.clone(); self.iter.next() }
1447 fn size_hint(&self) -> (usize, Option<usize>) {
1448 // the cycle iterator is either empty or infinite
1449 match self.orig.size_hint() {
1450 sz @ (0, Some(0)) => sz,
1451 (0, _) => (0, None),
1452 _ => (usize::MAX, None)
1457 #[unstable(feature = "core", reason = "trait is experimental")]
1458 impl<I> RandomAccessIterator for Cycle<I> where
1459 I: Clone + RandomAccessIterator,
1462 fn indexable(&self) -> usize {
1463 if self.orig.indexable() > 0 {
1471 fn idx(&mut self, index: usize) -> Option<<I as Iterator>::Item> {
1472 let liter = self.iter.indexable();
1473 let lorig = self.orig.indexable();
1476 } else if index < liter {
1477 self.iter.idx(index)
1479 self.orig.idx((index - liter) % lorig)
1484 /// An iterator that strings two iterators together
1486 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1487 #[stable(feature = "rust1", since = "1.0.0")]
1488 pub struct Chain<A, B> {
1494 #[stable(feature = "rust1", since = "1.0.0")]
1495 impl<A, B> Iterator for Chain<A, B> where
1497 B: Iterator<Item = A::Item>
1499 type Item = A::Item;
1502 fn next(&mut self) -> Option<A::Item> {
1506 match self.a.next() {
1507 Some(x) => return Some(x),
1516 fn count(self) -> usize {
1517 (if !self.flag { self.a.count() } else { 0 }) + self.b.count()
1521 fn nth(&mut self, mut n: usize) -> Option<A::Item> {
1523 for x in self.a.by_ref() {
1535 fn last(self) -> Option<A::Item> {
1536 let a_last = if self.flag { None } else { self.a.last() };
1537 let b_last = self.b.last();
1542 fn size_hint(&self) -> (usize, Option<usize>) {
1543 let (a_lower, a_upper) = self.a.size_hint();
1544 let (b_lower, b_upper) = self.b.size_hint();
1546 let lower = a_lower.saturating_add(b_lower);
1548 let upper = match (a_upper, b_upper) {
1549 (Some(x), Some(y)) => x.checked_add(y),
1557 #[stable(feature = "rust1", since = "1.0.0")]
1558 impl<A, B> DoubleEndedIterator for Chain<A, B> where
1559 A: DoubleEndedIterator,
1560 B: DoubleEndedIterator<Item=A::Item>,
1563 fn next_back(&mut self) -> Option<A::Item> {
1564 match self.b.next_back() {
1566 None => self.a.next_back()
1571 #[unstable(feature = "core", reason = "trait is experimental")]
1572 impl<A, B> RandomAccessIterator for Chain<A, B> where
1573 A: RandomAccessIterator,
1574 B: RandomAccessIterator<Item = A::Item>,
1577 fn indexable(&self) -> usize {
1578 let (a, b) = (self.a.indexable(), self.b.indexable());
1583 fn idx(&mut self, index: usize) -> Option<A::Item> {
1584 let len = self.a.indexable();
1588 self.b.idx(index - len)
1593 /// An iterator that iterates two other iterators simultaneously
1595 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1596 #[stable(feature = "rust1", since = "1.0.0")]
1597 pub struct Zip<A, B> {
1602 #[stable(feature = "rust1", since = "1.0.0")]
1603 impl<A, B> Iterator for Zip<A, B> where A: Iterator, B: Iterator
1605 type Item = (A::Item, B::Item);
1608 fn next(&mut self) -> Option<(A::Item, B::Item)> {
1609 self.a.next().and_then(|x| {
1610 self.b.next().and_then(|y| {
1617 fn size_hint(&self) -> (usize, Option<usize>) {
1618 let (a_lower, a_upper) = self.a.size_hint();
1619 let (b_lower, b_upper) = self.b.size_hint();
1621 let lower = cmp::min(a_lower, b_lower);
1623 let upper = match (a_upper, b_upper) {
1624 (Some(x), Some(y)) => Some(cmp::min(x,y)),
1625 (Some(x), None) => Some(x),
1626 (None, Some(y)) => Some(y),
1627 (None, None) => None
1634 #[stable(feature = "rust1", since = "1.0.0")]
1635 impl<A, B> DoubleEndedIterator for Zip<A, B> where
1636 A: DoubleEndedIterator + ExactSizeIterator,
1637 B: DoubleEndedIterator + ExactSizeIterator,
1640 fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
1641 let a_sz = self.a.len();
1642 let b_sz = self.b.len();
1644 // Adjust a, b to equal length
1646 for _ in 0..a_sz - b_sz { self.a.next_back(); }
1648 for _ in 0..b_sz - a_sz { self.b.next_back(); }
1651 match (self.a.next_back(), self.b.next_back()) {
1652 (Some(x), Some(y)) => Some((x, y)),
1653 (None, None) => None,
1654 _ => unreachable!(),
1659 #[unstable(feature = "core", reason = "trait is experimental")]
1660 impl<A, B> RandomAccessIterator for Zip<A, B> where
1661 A: RandomAccessIterator,
1662 B: RandomAccessIterator
1665 fn indexable(&self) -> usize {
1666 cmp::min(self.a.indexable(), self.b.indexable())
1670 fn idx(&mut self, index: usize) -> Option<(A::Item, B::Item)> {
1671 self.a.idx(index).and_then(|x| {
1672 self.b.idx(index).and_then(|y| {
1679 /// An iterator that maps the values of `iter` with `f`
1680 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1681 #[stable(feature = "rust1", since = "1.0.0")]
1683 pub struct Map<I, F> {
1688 #[stable(feature = "rust1", since = "1.0.0")]
1689 impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
1693 fn next(&mut self) -> Option<B> {
1694 self.iter.next().map(|a| (self.f)(a))
1698 fn size_hint(&self) -> (usize, Option<usize>) {
1699 self.iter.size_hint()
1703 #[stable(feature = "rust1", since = "1.0.0")]
1704 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where
1705 F: FnMut(I::Item) -> B,
1708 fn next_back(&mut self) -> Option<B> {
1709 self.iter.next_back().map(|a| (self.f)(a))
1713 #[unstable(feature = "core", reason = "trait is experimental")]
1714 impl<B, I: RandomAccessIterator, F> RandomAccessIterator for Map<I, F> where
1715 F: FnMut(I::Item) -> B,
1718 fn indexable(&self) -> usize {
1719 self.iter.indexable()
1723 fn idx(&mut self, index: usize) -> Option<B> {
1724 self.iter.idx(index).map(|a| (self.f)(a))
1728 /// An iterator that filters the elements of `iter` with `predicate`
1729 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1730 #[stable(feature = "rust1", since = "1.0.0")]
1732 pub struct Filter<I, P> {
1737 #[stable(feature = "rust1", since = "1.0.0")]
1738 impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {
1739 type Item = I::Item;
1742 fn next(&mut self) -> Option<I::Item> {
1743 for x in self.iter.by_ref() {
1744 if (self.predicate)(&x) {
1752 fn size_hint(&self) -> (usize, Option<usize>) {
1753 let (_, upper) = self.iter.size_hint();
1754 (0, upper) // can't know a lower bound, due to the predicate
1758 #[stable(feature = "rust1", since = "1.0.0")]
1759 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
1760 where P: FnMut(&I::Item) -> bool,
1763 fn next_back(&mut self) -> Option<I::Item> {
1764 for x in self.iter.by_ref().rev() {
1765 if (self.predicate)(&x) {
1773 /// An iterator that uses `f` to both filter and map elements from `iter`
1774 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1775 #[stable(feature = "rust1", since = "1.0.0")]
1777 pub struct FilterMap<I, F> {
1782 #[stable(feature = "rust1", since = "1.0.0")]
1783 impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
1784 where F: FnMut(I::Item) -> Option<B>,
1789 fn next(&mut self) -> Option<B> {
1790 for x in self.iter.by_ref() {
1791 if let Some(y) = (self.f)(x) {
1799 fn size_hint(&self) -> (usize, Option<usize>) {
1800 let (_, upper) = self.iter.size_hint();
1801 (0, upper) // can't know a lower bound, due to the predicate
1805 #[stable(feature = "rust1", since = "1.0.0")]
1806 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
1807 where F: FnMut(I::Item) -> Option<B>,
1810 fn next_back(&mut self) -> Option<B> {
1811 for x in self.iter.by_ref().rev() {
1812 if let Some(y) = (self.f)(x) {
1820 /// An iterator that yields the current count and the element during iteration
1822 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1823 #[stable(feature = "rust1", since = "1.0.0")]
1824 pub struct Enumerate<I> {
1829 #[stable(feature = "rust1", since = "1.0.0")]
1830 impl<I> Iterator for Enumerate<I> where I: Iterator {
1831 type Item = (usize, <I as Iterator>::Item);
1833 /// # Overflow Behavior
1835 /// The method does no guarding against overflows, so enumerating more than
1836 /// `usize::MAX` elements either produces the wrong result or panics. If
1837 /// debug assertions are enabled, a panic is guaranteed.
1841 /// Might panic if the index of the element overflows a `usize`.
1843 fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1844 self.iter.next().map(|a| {
1845 let ret = (self.count, a);
1846 // Possible undefined overflow.
1853 fn size_hint(&self) -> (usize, Option<usize>) {
1854 self.iter.size_hint()
1858 fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
1859 self.iter.nth(n).map(|a| {
1860 let i = self.count + n;
1867 fn count(self) -> usize {
1872 #[stable(feature = "rust1", since = "1.0.0")]
1873 impl<I> DoubleEndedIterator for Enumerate<I> where
1874 I: ExactSizeIterator + DoubleEndedIterator
1877 fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1878 self.iter.next_back().map(|a| {
1879 let len = self.iter.len();
1880 // Can safely add, `ExactSizeIterator` promises that the number of
1881 // elements fits into a `usize`.
1882 (self.count + len, a)
1887 #[unstable(feature = "core", reason = "trait is experimental")]
1888 impl<I> RandomAccessIterator for Enumerate<I> where I: RandomAccessIterator {
1890 fn indexable(&self) -> usize {
1891 self.iter.indexable()
1895 fn idx(&mut self, index: usize) -> Option<(usize, <I as Iterator>::Item)> {
1896 // Can safely add, `ExactSizeIterator` (ancestor of
1897 // `RandomAccessIterator`) promises that the number of elements fits
1899 self.iter.idx(index).map(|a| (self.count + index, a))
1903 /// An iterator with a `peek()` that returns an optional reference to the next element.
1904 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1905 #[stable(feature = "rust1", since = "1.0.0")]
1906 pub struct Peekable<I: Iterator> {
1908 peeked: Option<I::Item>,
1911 impl<I: Iterator + Clone> Clone for Peekable<I> where I::Item: Clone {
1912 fn clone(&self) -> Peekable<I> {
1914 iter: self.iter.clone(),
1915 peeked: self.peeked.clone(),
1920 #[stable(feature = "rust1", since = "1.0.0")]
1921 impl<I: Iterator> Iterator for Peekable<I> {
1922 type Item = I::Item;
1925 fn next(&mut self) -> Option<I::Item> {
1927 Some(_) => self.peeked.take(),
1928 None => self.iter.next(),
1933 fn count(self) -> usize {
1934 (if self.peeked.is_some() { 1 } else { 0 }) + self.iter.count()
1938 fn nth(&mut self, n: usize) -> Option<I::Item> {
1940 Some(_) if n == 0 => self.peeked.take(),
1945 None => self.iter.nth(n)
1950 fn last(self) -> Option<I::Item> {
1951 self.iter.last().or(self.peeked)
1955 fn size_hint(&self) -> (usize, Option<usize>) {
1956 let (lo, hi) = self.iter.size_hint();
1957 if self.peeked.is_some() {
1958 let lo = lo.saturating_add(1);
1959 let hi = hi.and_then(|x| x.checked_add(1));
1967 #[stable(feature = "rust1", since = "1.0.0")]
1968 impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
1970 #[stable(feature = "rust1", since = "1.0.0")]
1971 impl<I: Iterator> Peekable<I> {
1972 /// Returns a reference to the next element of the iterator with out
1973 /// advancing it, or None if the iterator is exhausted.
1975 #[stable(feature = "rust1", since = "1.0.0")]
1976 pub fn peek(&mut self) -> Option<&I::Item> {
1977 if self.peeked.is_none() {
1978 self.peeked = self.iter.next();
1981 Some(ref value) => Some(value),
1986 /// Checks whether peekable iterator is empty or not.
1988 pub fn is_empty(&mut self) -> bool {
1989 self.peek().is_none()
1993 /// An iterator that rejects elements while `predicate` is true
1994 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1995 #[stable(feature = "rust1", since = "1.0.0")]
1997 pub struct SkipWhile<I, P> {
2003 #[stable(feature = "rust1", since = "1.0.0")]
2004 impl<I: Iterator, P> Iterator for SkipWhile<I, P>
2005 where P: FnMut(&I::Item) -> bool
2007 type Item = I::Item;
2010 fn next(&mut self) -> Option<I::Item> {
2011 for x in self.iter.by_ref() {
2012 if self.flag || !(self.predicate)(&x) {
2021 fn size_hint(&self) -> (usize, Option<usize>) {
2022 let (_, upper) = self.iter.size_hint();
2023 (0, upper) // can't know a lower bound, due to the predicate
2027 /// An iterator that only accepts elements while `predicate` is true
2028 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2029 #[stable(feature = "rust1", since = "1.0.0")]
2031 pub struct TakeWhile<I, P> {
2037 #[stable(feature = "rust1", since = "1.0.0")]
2038 impl<I: Iterator, P> Iterator for TakeWhile<I, P>
2039 where P: FnMut(&I::Item) -> bool
2041 type Item = I::Item;
2044 fn next(&mut self) -> Option<I::Item> {
2048 self.iter.next().and_then(|x| {
2049 if (self.predicate)(&x) {
2060 fn size_hint(&self) -> (usize, Option<usize>) {
2061 let (_, upper) = self.iter.size_hint();
2062 (0, upper) // can't know a lower bound, due to the predicate
2066 /// An iterator that skips over `n` elements of `iter`.
2068 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2069 #[stable(feature = "rust1", since = "1.0.0")]
2070 pub struct Skip<I> {
2075 #[stable(feature = "rust1", since = "1.0.0")]
2076 impl<I> Iterator for Skip<I> where I: Iterator {
2077 type Item = <I as Iterator>::Item;
2080 fn next(&mut self) -> Option<I::Item> {
2086 self.iter.nth(old_n)
2091 fn nth(&mut self, n: usize) -> Option<I::Item> {
2092 // Can't just add n + self.n due to overflow.
2096 let to_skip = self.n;
2099 if self.iter.nth(to_skip-1).is_none() {
2107 fn count(self) -> usize {
2108 self.iter.count().saturating_sub(self.n)
2112 fn last(mut self) -> Option<I::Item> {
2116 let next = self.next();
2118 // recurse. n should be 0.
2119 self.last().or(next)
2127 fn size_hint(&self) -> (usize, Option<usize>) {
2128 let (lower, upper) = self.iter.size_hint();
2130 let lower = lower.saturating_sub(self.n);
2131 let upper = upper.map(|x| x.saturating_sub(self.n));
2137 #[unstable(feature = "core", reason = "trait is experimental")]
2138 impl<I> RandomAccessIterator for Skip<I> where I: RandomAccessIterator{
2140 fn indexable(&self) -> usize {
2141 self.iter.indexable().saturating_sub(self.n)
2145 fn idx(&mut self, index: usize) -> Option<<I as Iterator>::Item> {
2146 if index >= self.indexable() {
2149 self.iter.idx(index + self.n)
2154 #[stable(feature = "rust1", since = "1.0.0")]
2155 impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
2157 /// An iterator that only iterates over the first `n` iterations of `iter`.
2159 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2160 #[stable(feature = "rust1", since = "1.0.0")]
2161 pub struct Take<I> {
2166 #[stable(feature = "rust1", since = "1.0.0")]
2167 impl<I> Iterator for Take<I> where I: Iterator{
2168 type Item = <I as Iterator>::Item;
2171 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2181 fn nth(&mut self, n: usize) -> Option<I::Item> {
2187 self.iter.nth(self.n - 1);
2195 fn size_hint(&self) -> (usize, Option<usize>) {
2196 let (lower, upper) = self.iter.size_hint();
2198 let lower = cmp::min(lower, self.n);
2200 let upper = match upper {
2201 Some(x) if x < self.n => Some(x),
2209 #[unstable(feature = "core", reason = "trait is experimental")]
2210 impl<I> RandomAccessIterator for Take<I> where I: RandomAccessIterator{
2212 fn indexable(&self) -> usize {
2213 cmp::min(self.iter.indexable(), self.n)
2217 fn idx(&mut self, index: usize) -> Option<<I as Iterator>::Item> {
2218 if index >= self.n {
2221 self.iter.idx(index)
2226 #[stable(feature = "rust1", since = "1.0.0")]
2227 impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
2230 /// An iterator to maintain state while iterating another iterator
2231 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2232 #[stable(feature = "rust1", since = "1.0.0")]
2234 pub struct Scan<I, St, F> {
2238 /// The current internal state to be passed to the closure next.
2239 #[unstable(feature = "core")]
2243 #[stable(feature = "rust1", since = "1.0.0")]
2244 impl<B, I, St, F> Iterator for Scan<I, St, F> where
2246 F: FnMut(&mut St, I::Item) -> Option<B>,
2251 fn next(&mut self) -> Option<B> {
2252 self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
2256 fn size_hint(&self) -> (usize, Option<usize>) {
2257 let (_, upper) = self.iter.size_hint();
2258 (0, upper) // can't know a lower bound, due to the scan function
2262 /// An iterator that maps each element to an iterator,
2263 /// and yields the elements of the produced iterators
2265 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2266 #[stable(feature = "rust1", since = "1.0.0")]
2268 pub struct FlatMap<I, U: IntoIterator, F> {
2271 frontiter: Option<U::IntoIter>,
2272 backiter: Option<U::IntoIter>,
2275 #[stable(feature = "rust1", since = "1.0.0")]
2276 impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F>
2277 where F: FnMut(I::Item) -> U,
2279 type Item = U::Item;
2282 fn next(&mut self) -> Option<U::Item> {
2284 if let Some(ref mut inner) = self.frontiter {
2285 if let Some(x) = inner.by_ref().next() {
2289 match self.iter.next().map(|x| (self.f)(x)) {
2290 None => return self.backiter.as_mut().and_then(|it| it.next()),
2291 next => self.frontiter = next.map(IntoIterator::into_iter),
2297 fn size_hint(&self) -> (usize, Option<usize>) {
2298 let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
2299 let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
2300 let lo = flo.saturating_add(blo);
2301 match (self.iter.size_hint(), fhi, bhi) {
2302 ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
2308 #[stable(feature = "rust1", since = "1.0.0")]
2309 impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F> where
2310 F: FnMut(I::Item) -> U,
2312 U::IntoIter: DoubleEndedIterator
2315 fn next_back(&mut self) -> Option<U::Item> {
2317 if let Some(ref mut inner) = self.backiter {
2318 if let Some(y) = inner.next_back() {
2322 match self.iter.next_back().map(|x| (self.f)(x)) {
2323 None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
2324 next => self.backiter = next.map(IntoIterator::into_iter),
2330 /// An iterator that yields `None` forever after the underlying iterator
2331 /// yields `None` once.
2333 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2334 #[stable(feature = "rust1", since = "1.0.0")]
2335 pub struct Fuse<I> {
2340 #[stable(feature = "rust1", since = "1.0.0")]
2341 impl<I> Iterator for Fuse<I> where I: Iterator {
2342 type Item = <I as Iterator>::Item;
2345 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2349 let next = self.iter.next();
2350 self.done = next.is_none();
2356 fn nth(&mut self, n: usize) -> Option<I::Item> {
2360 let nth = self.iter.nth(n);
2361 self.done = nth.is_none();
2367 fn last(self) -> Option<I::Item> {
2376 fn count(self) -> usize {
2385 fn size_hint(&self) -> (usize, Option<usize>) {
2389 self.iter.size_hint()
2394 #[stable(feature = "rust1", since = "1.0.0")]
2395 impl<I> DoubleEndedIterator for Fuse<I> where I: DoubleEndedIterator {
2397 fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
2401 let next = self.iter.next_back();
2402 self.done = next.is_none();
2408 // Allow RandomAccessIterators to be fused without affecting random-access behavior
2409 #[unstable(feature = "core", reason = "trait is experimental")]
2410 impl<I> RandomAccessIterator for Fuse<I> where I: RandomAccessIterator {
2412 fn indexable(&self) -> usize {
2413 self.iter.indexable()
2417 fn idx(&mut self, index: usize) -> Option<<I as Iterator>::Item> {
2418 self.iter.idx(index)
2422 #[stable(feature = "rust1", since = "1.0.0")]
2423 impl<I> ExactSizeIterator for Fuse<I> where I: ExactSizeIterator {}
2426 /// Resets the `Fuse` such that the next call to `.next()` or
2427 /// `.next_back()` will call the underlying iterator again even if it
2428 /// previously returned `None`.
2430 #[unstable(feature = "core", reason = "seems marginal")]
2431 pub fn reset_fuse(&mut self) {
2436 /// An iterator that calls a function with a reference to each
2437 /// element before yielding it.
2438 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2439 #[stable(feature = "rust1", since = "1.0.0")]
2441 pub struct Inspect<I, F> {
2446 impl<I: Iterator, F> Inspect<I, F> where F: FnMut(&I::Item) {
2448 fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
2449 if let Some(ref a) = elt {
2457 #[stable(feature = "rust1", since = "1.0.0")]
2458 impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) {
2459 type Item = I::Item;
2462 fn next(&mut self) -> Option<I::Item> {
2463 let next = self.iter.next();
2464 self.do_inspect(next)
2468 fn size_hint(&self) -> (usize, Option<usize>) {
2469 self.iter.size_hint()
2473 #[stable(feature = "rust1", since = "1.0.0")]
2474 impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
2475 where F: FnMut(&I::Item),
2478 fn next_back(&mut self) -> Option<I::Item> {
2479 let next = self.iter.next_back();
2480 self.do_inspect(next)
2484 #[unstable(feature = "core", reason = "trait is experimental")]
2485 impl<I: RandomAccessIterator, F> RandomAccessIterator for Inspect<I, F>
2486 where F: FnMut(&I::Item),
2489 fn indexable(&self) -> usize {
2490 self.iter.indexable()
2494 fn idx(&mut self, index: usize) -> Option<I::Item> {
2495 let element = self.iter.idx(index);
2496 self.do_inspect(element)
2500 /// An iterator that passes mutable state to a closure and yields the result.
2504 /// An iterator that yields sequential Fibonacci numbers, and stops on overflow.
2507 /// #![feature(core)]
2508 /// use std::iter::Unfold;
2510 /// // This iterator will yield up to the last Fibonacci number before the max
2511 /// // value of `u32`. You can simply change `u32` to `u64` in this line if
2512 /// // you want higher values than that.
2513 /// let mut fibonacci = Unfold::new((Some(0u32), Some(1u32)),
2514 /// |&mut (ref mut x2, ref mut x1)| {
2515 /// // Attempt to get the next Fibonacci number
2516 /// // `x1` will be `None` if previously overflowed.
2517 /// let next = match (*x2, *x1) {
2518 /// (Some(x2), Some(x1)) => x2.checked_add(x1),
2522 /// // Shift left: ret <- x2 <- x1 <- next
2530 /// for i in fibonacci {
2531 /// println!("{}", i);
2534 #[unstable(feature = "core")]
2536 pub struct Unfold<St, F> {
2538 /// Internal state that will be passed to the closure on the next iteration
2539 #[unstable(feature = "core")]
2543 #[unstable(feature = "core")]
2544 impl<A, St, F> Unfold<St, F> where F: FnMut(&mut St) -> Option<A> {
2545 /// Creates a new iterator with the specified closure as the "iterator
2546 /// function" and an initial state to eventually pass to the closure
2548 pub fn new(initial_state: St, f: F) -> Unfold<St, F> {
2551 state: initial_state
2556 #[stable(feature = "rust1", since = "1.0.0")]
2557 impl<A, St, F> Iterator for Unfold<St, F> where F: FnMut(&mut St) -> Option<A> {
2561 fn next(&mut self) -> Option<A> {
2562 (self.f)(&mut self.state)
2566 fn size_hint(&self) -> (usize, Option<usize>) {
2567 // no possible known bounds at this point
2572 /// Objects that can be stepped over in both directions.
2574 /// The `steps_between` function provides a way to efficiently compare
2575 /// two `Step` objects.
2576 #[unstable(feature = "step_trait",
2577 reason = "likely to be replaced by finer-grained traits")]
2578 pub trait Step: PartialOrd {
2579 /// Steps `self` if possible.
2580 fn step(&self, by: &Self) -> Option<Self>;
2582 /// Returns the number of steps between two step objects. The count is
2583 /// inclusive of `start` and exclusive of `end`.
2585 /// Returns `None` if it is not possible to calculate `steps_between`
2586 /// without overflow.
2587 fn steps_between(start: &Self, end: &Self, by: &Self) -> Option<usize>;
2590 macro_rules! step_impl_unsigned {
2594 fn step(&self, by: &$t) -> Option<$t> {
2595 (*self).checked_add(*by)
2598 #[allow(trivial_numeric_casts)]
2599 fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
2600 if *by == 0 { return None; }
2602 // Note: We assume $t <= usize here
2603 let diff = (*end - *start) as usize;
2604 let by = *by as usize;
2617 macro_rules! step_impl_signed {
2621 fn step(&self, by: &$t) -> Option<$t> {
2622 (*self).checked_add(*by)
2625 #[allow(trivial_numeric_casts)]
2626 fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
2627 if *by == 0 { return None; }
2628 let mut diff: usize;
2629 let mut by_u: usize;
2634 // Note: We assume $t <= isize here
2635 // Use .wrapping_sub and cast to usize to compute the
2636 // difference that may not fit inside the range of isize.
2637 diff = (*end as isize).wrapping_sub(*start as isize) as usize;
2638 by_u = *by as usize;
2643 diff = (*start as isize).wrapping_sub(*end as isize) as usize;
2644 by_u = (*by as isize).wrapping_mul(-1) as usize;
2646 if diff % by_u > 0 {
2647 Some(diff / by_u + 1)
2656 macro_rules! step_impl_no_between {
2660 fn step(&self, by: &$t) -> Option<$t> {
2661 (*self).checked_add(*by)
2664 fn steps_between(_a: &$t, _b: &$t, _by: &$t) -> Option<usize> {
2671 step_impl_unsigned!(usize u8 u16 u32);
2672 step_impl_signed!(isize i8 i16 i32);
2673 #[cfg(target_pointer_width = "64")]
2674 step_impl_unsigned!(u64);
2675 #[cfg(target_pointer_width = "64")]
2676 step_impl_signed!(i64);
2677 #[cfg(target_pointer_width = "32")]
2678 step_impl_no_between!(u64 i64);
2680 /// An adapter for stepping range iterators by a custom amount.
2682 /// The resulting iterator handles overflow by stopping. The `A`
2683 /// parameter is the type being iterated over, while `R` is the range
2684 /// type (usually one of `std::ops::{Range, RangeFrom}`.
2686 #[unstable(feature = "step_by", reason = "recent addition")]
2687 pub struct StepBy<A, R> {
2692 impl<A: Step> RangeFrom<A> {
2693 /// Creates an iterator starting at the same point, but stepping by
2694 /// the given amount at each iteration.
2699 /// for i in (0u8..).step_by(2) {
2700 /// println!("{}", i);
2704 /// This prints all even `u8` values.
2705 #[unstable(feature = "step_by", reason = "recent addition")]
2706 pub fn step_by(self, by: A) -> StepBy<A, Self> {
2714 #[allow(deprecated)]
2715 impl<A: Step> ops::Range<A> {
2716 /// Creates an iterator with the same range, but stepping by the
2717 /// given amount at each iteration.
2719 /// The resulting iterator handles overflow by stopping.
2724 /// # #![feature(step_by)]
2725 /// for i in (0..10).step_by(2) {
2726 /// println!("{}", i);
2739 #[unstable(feature = "step_by", reason = "recent addition")]
2740 pub fn step_by(self, by: A) -> StepBy<A, Self> {
2748 #[stable(feature = "rust1", since = "1.0.0")]
2749 impl<A> Iterator for StepBy<A, RangeFrom<A>> where
2751 for<'a> &'a A: Add<&'a A, Output = A>
2756 fn next(&mut self) -> Option<A> {
2757 let mut n = &self.range.start + &self.step_by;
2758 mem::swap(&mut n, &mut self.range.start);
2763 fn size_hint(&self) -> (usize, Option<usize>) {
2764 (usize::MAX, None) // Too bad we can't specify an infinite lower bound
2768 /// An iterator over the range [start, stop]
2770 #[unstable(feature = "core",
2771 reason = "likely to be replaced by range notation and adapters")]
2772 pub struct RangeInclusive<A> {
2773 range: ops::Range<A>,
2777 /// Returns an iterator over the range [start, stop].
2779 #[unstable(feature = "core",
2780 reason = "likely to be replaced by range notation and adapters")]
2781 pub fn range_inclusive<A>(start: A, stop: A) -> RangeInclusive<A>
2782 where A: Step + One + Clone
2790 #[unstable(feature = "core",
2791 reason = "likely to be replaced by range notation and adapters")]
2792 impl<A> Iterator for RangeInclusive<A> where
2793 A: PartialEq + Step + One + Clone,
2794 for<'a> &'a A: Add<&'a A, Output = A>
2799 fn next(&mut self) -> Option<A> {
2800 self.range.next().or_else(|| {
2801 if !self.done && self.range.start == self.range.end {
2803 Some(self.range.end.clone())
2811 fn size_hint(&self) -> (usize, Option<usize>) {
2812 let (lo, hi) = self.range.size_hint();
2816 let lo = lo.saturating_add(1);
2817 let hi = hi.and_then(|x| x.checked_add(1));
2823 #[unstable(feature = "core",
2824 reason = "likely to be replaced by range notation and adapters")]
2825 impl<A> DoubleEndedIterator for RangeInclusive<A> where
2826 A: PartialEq + Step + One + Clone,
2827 for<'a> &'a A: Add<&'a A, Output = A>,
2828 for<'a> &'a A: Sub<Output=A>
2831 fn next_back(&mut self) -> Option<A> {
2832 if self.range.end > self.range.start {
2833 let result = self.range.end.clone();
2834 self.range.end = &self.range.end - &A::one();
2836 } else if !self.done && self.range.start == self.range.end {
2838 Some(self.range.end.clone())
2845 #[stable(feature = "rust1", since = "1.0.0")]
2846 #[allow(deprecated)]
2847 impl<A: Step + Zero + Clone> Iterator for StepBy<A, ops::Range<A>> {
2851 fn next(&mut self) -> Option<A> {
2852 let rev = self.step_by < A::zero();
2853 if (rev && self.range.start > self.range.end) ||
2854 (!rev && self.range.start < self.range.end)
2856 match self.range.start.step(&self.step_by) {
2858 mem::swap(&mut self.range.start, &mut n);
2862 let mut n = self.range.end.clone();
2863 mem::swap(&mut self.range.start, &mut n);
2873 fn size_hint(&self) -> (usize, Option<usize>) {
2874 match Step::steps_between(&self.range.start,
2877 Some(hint) => (hint, Some(hint)),
2883 macro_rules! range_exact_iter_impl {
2885 #[stable(feature = "rust1", since = "1.0.0")]
2886 impl ExactSizeIterator for ops::Range<$t> { }
2890 #[stable(feature = "rust1", since = "1.0.0")]
2891 #[allow(deprecated)]
2892 impl<A: Step + One> Iterator for ops::Range<A> where
2893 for<'a> &'a A: Add<&'a A, Output = A>
2898 fn next(&mut self) -> Option<A> {
2899 if self.start < self.end {
2900 let mut n = &self.start + &A::one();
2901 mem::swap(&mut n, &mut self.start);
2909 fn size_hint(&self) -> (usize, Option<usize>) {
2910 match Step::steps_between(&self.start, &self.end, &A::one()) {
2911 Some(hint) => (hint, Some(hint)),
2917 // Ranges of u64 and i64 are excluded because they cannot guarantee having
2918 // a length <= usize::MAX, which is required by ExactSizeIterator.
2919 range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);
2921 #[stable(feature = "rust1", since = "1.0.0")]
2922 #[allow(deprecated)]
2923 impl<A: Step + One + Clone> DoubleEndedIterator for ops::Range<A> where
2924 for<'a> &'a A: Add<&'a A, Output = A>,
2925 for<'a> &'a A: Sub<&'a A, Output = A>
2928 fn next_back(&mut self) -> Option<A> {
2929 if self.start < self.end {
2930 self.end = &self.end - &A::one();
2931 Some(self.end.clone())
2938 #[stable(feature = "rust1", since = "1.0.0")]
2939 #[allow(deprecated)]
2940 impl<A: Step + One> Iterator for ops::RangeFrom<A> where
2941 for<'a> &'a A: Add<&'a A, Output = A>
2946 fn next(&mut self) -> Option<A> {
2947 let mut n = &self.start + &A::one();
2948 mem::swap(&mut n, &mut self.start);
2953 /// An iterator that repeats an element endlessly
2955 #[stable(feature = "rust1", since = "1.0.0")]
2956 pub struct Repeat<A> {
2960 #[stable(feature = "rust1", since = "1.0.0")]
2961 impl<A: Clone> Iterator for Repeat<A> {
2965 fn next(&mut self) -> Option<A> { self.idx(0) }
2967 fn size_hint(&self) -> (usize, Option<usize>) { (usize::MAX, None) }
2970 #[stable(feature = "rust1", since = "1.0.0")]
2971 impl<A: Clone> DoubleEndedIterator for Repeat<A> {
2973 fn next_back(&mut self) -> Option<A> { self.idx(0) }
2976 #[unstable(feature = "core", reason = "trait is experimental")]
2977 impl<A: Clone> RandomAccessIterator for Repeat<A> {
2979 fn indexable(&self) -> usize { usize::MAX }
2981 fn idx(&mut self, _: usize) -> Option<A> { Some(self.element.clone()) }
2984 type IterateState<T, F> = (F, Option<T>, bool);
2986 /// An iterator that repeatedly applies a given function, starting
2987 /// from a given seed value.
2988 #[unstable(feature = "core")]
2989 pub type Iterate<T, F> = Unfold<IterateState<T, F>, fn(&mut IterateState<T, F>) -> Option<T>>;
2991 /// Creates a new iterator that produces an infinite sequence of
2992 /// repeated applications of the given function `f`.
2993 #[unstable(feature = "core")]
2994 pub fn iterate<T, F>(seed: T, f: F) -> Iterate<T, F> where
2998 fn next<T, F>(st: &mut IterateState<T, F>) -> Option<T> where
3002 let &mut (ref mut f, ref mut val, ref mut first) = st;
3005 } else if let Some(x) = val.take() {
3006 *val = Some((*f)(x))
3011 // coerce to a fn pointer
3012 let next: fn(&mut IterateState<T,F>) -> Option<T> = next;
3014 Unfold::new((f, Some(seed), true), next)
3017 /// Creates a new iterator that endlessly repeats the element `elt`.
3019 #[stable(feature = "rust1", since = "1.0.0")]
3020 pub fn repeat<T: Clone>(elt: T) -> Repeat<T> {
3021 Repeat{element: elt}
3024 /// An iterator that yields nothing.
3025 #[unstable(feature="iter_empty", reason = "new addition")]
3026 pub struct Empty<T>(marker::PhantomData<T>);
3028 #[unstable(feature="iter_empty", reason = "new addition")]
3029 impl<T> Iterator for Empty<T> {
3032 fn next(&mut self) -> Option<T> {
3036 fn size_hint(&self) -> (usize, Option<usize>){
3041 #[unstable(feature="iter_empty", reason = "new addition")]
3042 impl<T> DoubleEndedIterator for Empty<T> {
3043 fn next_back(&mut self) -> Option<T> {
3048 #[unstable(feature="iter_empty", reason = "new addition")]
3049 impl<T> ExactSizeIterator for Empty<T> {
3050 fn len(&self) -> usize {
3055 // not #[derive] because that adds a Clone bound on T,
3056 // which isn't necessary.
3057 #[unstable(feature="iter_empty", reason = "new addition")]
3058 impl<T> Clone for Empty<T> {
3059 fn clone(&self) -> Empty<T> {
3060 Empty(marker::PhantomData)
3064 // not #[derive] because that adds a Default bound on T,
3065 // which isn't necessary.
3066 #[unstable(feature="iter_empty", reason = "new addition")]
3067 impl<T> Default for Empty<T> {
3068 fn default() -> Empty<T> {
3069 Empty(marker::PhantomData)
3073 /// Creates an iterator that yields nothing.
3074 #[unstable(feature="iter_empty", reason = "new addition")]
3075 pub fn empty<T>() -> Empty<T> {
3076 Empty(marker::PhantomData)
3079 /// An iterator that yields an element exactly once.
3081 #[unstable(feature="iter_once", reason = "new addition")]
3082 pub struct Once<T> {
3083 inner: ::option::IntoIter<T>
3086 #[unstable(feature="iter_once", reason = "new addition")]
3087 impl<T> Iterator for Once<T> {
3090 fn next(&mut self) -> Option<T> {
3094 fn size_hint(&self) -> (usize, Option<usize>) {
3095 self.inner.size_hint()
3099 #[unstable(feature="iter_once", reason = "new addition")]
3100 impl<T> DoubleEndedIterator for Once<T> {
3101 fn next_back(&mut self) -> Option<T> {
3102 self.inner.next_back()
3106 #[unstable(feature="iter_once", reason = "new addition")]
3107 impl<T> ExactSizeIterator for Once<T> {
3108 fn len(&self) -> usize {
3113 /// Creates an iterator that yields an element exactly once.
3114 #[unstable(feature="iter_once", reason = "new addition")]
3115 pub fn once<T>(value: T) -> Once<T> {
3116 Once { inner: Some(value).into_iter() }
3119 /// Functions for lexicographical ordering of sequences.
3121 /// Lexicographical ordering through `<`, `<=`, `>=`, `>` requires
3122 /// that the elements implement both `PartialEq` and `PartialOrd`.
3124 /// If two sequences are equal up until the point where one ends,
3125 /// the shorter sequence compares less.
3126 #[unstable(feature = "core", reason = "needs review and revision")]
3129 use cmp::{Eq, Ord, PartialOrd, PartialEq};
3130 use cmp::Ordering::{Equal, Less, Greater};
3132 use option::Option::{Some, None};
3133 use super::Iterator;
3135 /// Compare `a` and `b` for equality using `Eq`
3136 pub fn equals<A, L, R>(mut a: L, mut b: R) -> bool where
3138 L: Iterator<Item=A>,
3139 R: Iterator<Item=A>,
3142 match (a.next(), b.next()) {
3143 (None, None) => return true,
3144 (None, _) | (_, None) => return false,
3145 (Some(x), Some(y)) => if x != y { return false },
3150 /// Order `a` and `b` lexicographically using `Ord`
3151 pub fn cmp<A, L, R>(mut a: L, mut b: R) -> cmp::Ordering where
3153 L: Iterator<Item=A>,
3154 R: Iterator<Item=A>,
3157 match (a.next(), b.next()) {
3158 (None, None) => return Equal,
3159 (None, _ ) => return Less,
3160 (_ , None) => return Greater,
3161 (Some(x), Some(y)) => match x.cmp(&y) {
3163 non_eq => return non_eq,
3169 /// Order `a` and `b` lexicographically using `PartialOrd`
3170 pub fn partial_cmp<L: Iterator, R: Iterator>(mut a: L, mut b: R) -> Option<cmp::Ordering> where
3171 L::Item: PartialOrd<R::Item>
3174 match (a.next(), b.next()) {
3175 (None, None) => return Some(Equal),
3176 (None, _ ) => return Some(Less),
3177 (_ , None) => return Some(Greater),
3178 (Some(x), Some(y)) => match x.partial_cmp(&y) {
3180 non_eq => return non_eq,
3186 /// Compare `a` and `b` for equality (Using partial equality, `PartialEq`)
3187 pub fn eq<L: Iterator, R: Iterator>(mut a: L, mut b: R) -> bool where
3188 L::Item: PartialEq<R::Item>,
3191 match (a.next(), b.next()) {
3192 (None, None) => return true,
3193 (None, _) | (_, None) => return false,
3194 (Some(x), Some(y)) => if !x.eq(&y) { return false },
3199 /// Compares `a` and `b` for nonequality (Using partial equality, `PartialEq`)
3200 pub fn ne<L: Iterator, R: Iterator>(mut a: L, mut b: R) -> bool where
3201 L::Item: PartialEq<R::Item>,
3204 match (a.next(), b.next()) {
3205 (None, None) => return false,
3206 (None, _) | (_, None) => return true,
3207 (Some(x), Some(y)) => if x.ne(&y) { return true },
3212 /// Returns `a` < `b` lexicographically (Using partial order, `PartialOrd`)
3213 pub fn lt<L: Iterator, R: Iterator>(mut a: L, mut b: R) -> bool where
3214 L::Item: PartialOrd<R::Item>,
3217 match (a.next(), b.next()) {
3218 (None, None) => return false,
3219 (None, _ ) => return true,
3220 (_ , None) => return false,
3221 (Some(x), Some(y)) => if x.ne(&y) { return x.lt(&y) },
3226 /// Returns `a` <= `b` lexicographically (Using partial order, `PartialOrd`)
3227 pub fn le<L: Iterator, R: Iterator>(mut a: L, mut b: R) -> bool where
3228 L::Item: PartialOrd<R::Item>,
3231 match (a.next(), b.next()) {
3232 (None, None) => return true,
3233 (None, _ ) => return true,
3234 (_ , None) => return false,
3235 (Some(x), Some(y)) => if x.ne(&y) { return x.le(&y) },
3240 /// Returns `a` > `b` lexicographically (Using partial order, `PartialOrd`)
3241 pub fn gt<L: Iterator, R: Iterator>(mut a: L, mut b: R) -> bool where
3242 L::Item: PartialOrd<R::Item>,
3245 match (a.next(), b.next()) {
3246 (None, None) => return false,
3247 (None, _ ) => return false,
3248 (_ , None) => return true,
3249 (Some(x), Some(y)) => if x.ne(&y) { return x.gt(&y) },
3254 /// Returns `a` >= `b` lexicographically (Using partial order, `PartialOrd`)
3255 pub fn ge<L: Iterator, R: Iterator>(mut a: L, mut b: R) -> bool where
3256 L::Item: PartialOrd<R::Item>,
3259 match (a.next(), b.next()) {
3260 (None, None) => return true,
3261 (None, _ ) => return false,
3262 (_ , None) => return true,
3263 (Some(x), Some(y)) => if x.ne(&y) { return x.ge(&y) },