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.
112 /// let a = [1, 2, 3, 4, 5];
113 /// assert_eq!(a.iter().count(), 5);
116 #[stable(feature = "rust1", since = "1.0.0")]
117 fn count(self) -> usize where Self: Sized {
118 self.fold(0, |cnt, _x| cnt + 1)
121 /// Loops through the entire iterator, returning the last element.
126 /// let a = [1, 2, 3, 4, 5];
127 /// assert!(a.iter().last().unwrap() == &5);
130 #[stable(feature = "rust1", since = "1.0.0")]
131 fn last(self) -> Option<Self::Item> where Self: Sized {
133 for x in self { last = Some(x); }
137 /// Loops through `n` iterations, returning the `n`th element of the
143 /// let a = [1, 2, 3, 4, 5];
144 /// let mut it = a.iter();
145 /// assert!(it.nth(2).unwrap() == &3);
146 /// assert!(it.nth(2) == None);
149 #[stable(feature = "rust1", since = "1.0.0")]
150 fn nth(&mut self, mut n: usize) -> Option<Self::Item> where Self: Sized {
151 for x in self.by_ref() {
152 if n == 0 { return Some(x) }
158 /// Chain this iterator with another, returning a new iterator that will
159 /// finish iterating over the current iterator, and then iterate
160 /// over the other specified iterator.
167 /// let mut it = a.iter().chain(b.iter());
168 /// assert_eq!(it.next().unwrap(), &0);
169 /// assert_eq!(it.next().unwrap(), &1);
170 /// assert!(it.next().is_none());
173 #[stable(feature = "rust1", since = "1.0.0")]
174 fn chain<U>(self, other: U) -> Chain<Self, U::IntoIter> where
175 Self: Sized, U: IntoIterator<Item=Self::Item>,
177 Chain{a: self, b: other.into_iter(), flag: false}
180 /// Creates an iterator that iterates over both this and the specified
181 /// iterators simultaneously, yielding the two elements as pairs. When
182 /// either iterator returns `None`, all further invocations of `next()`
183 /// will return `None`.
190 /// let mut it = a.iter().zip(b.iter());
191 /// assert_eq!(it.next().unwrap(), (&0, &1));
192 /// assert!(it.next().is_none());
195 /// `zip` can provide similar functionality to `enumerate`:
198 /// for pair in "foo".chars().enumerate() {
199 /// println!("{:?}", pair);
202 /// for pair in (0..).zip("foo".chars()) {
203 /// println!("{:?}", pair);
207 /// both produce the same output.
209 #[stable(feature = "rust1", since = "1.0.0")]
210 fn zip<U>(self, other: U) -> Zip<Self, U::IntoIter> where
211 Self: Sized, U: IntoIterator
213 Zip{a: self, b: other.into_iter()}
216 /// Creates a new iterator that will apply the specified function to each
217 /// element returned by the first, yielding the mapped element instead.
223 /// let mut it = a.iter().map(|&x| 2 * x);
224 /// assert_eq!(it.next().unwrap(), 2);
225 /// assert_eq!(it.next().unwrap(), 4);
226 /// assert!(it.next().is_none());
229 #[stable(feature = "rust1", since = "1.0.0")]
230 fn map<B, F>(self, f: F) -> Map<Self, F> where
231 Self: Sized, F: FnMut(Self::Item) -> B,
233 Map{iter: self, f: f}
236 /// Creates an iterator that applies the predicate to each element returned
237 /// by this iterator. The only elements that will be yielded are those that
238 /// make the predicate evaluate to `true`.
244 /// let mut it = a.iter().filter(|&x| *x > 1);
245 /// assert_eq!(it.next().unwrap(), &2);
246 /// assert!(it.next().is_none());
249 #[stable(feature = "rust1", since = "1.0.0")]
250 fn filter<P>(self, predicate: P) -> Filter<Self, P> where
251 Self: Sized, P: FnMut(&Self::Item) -> bool,
253 Filter{iter: self, predicate: predicate}
256 /// Creates an iterator that both filters and maps elements.
257 /// If the specified function returns `None`, the element is skipped.
258 /// Otherwise the option is unwrapped and the new value is yielded.
264 /// let mut it = a.iter().filter_map(|&x| if x > 1 {Some(2 * x)} else {None});
265 /// assert_eq!(it.next().unwrap(), 4);
266 /// assert!(it.next().is_none());
269 #[stable(feature = "rust1", since = "1.0.0")]
270 fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F> where
271 Self: Sized, F: FnMut(Self::Item) -> Option<B>,
273 FilterMap { iter: self, f: f }
276 /// Creates an iterator that yields pairs `(i, val)` where `i` is the
277 /// current index of iteration and `val` is the value returned by the
280 /// `enumerate` keeps its count as a `usize`. If you want to count by a
281 /// different sized integer, the `zip` function provides similar
287 /// let a = [100, 200];
288 /// let mut it = a.iter().enumerate();
289 /// assert_eq!(it.next().unwrap(), (0, &100));
290 /// assert_eq!(it.next().unwrap(), (1, &200));
291 /// assert!(it.next().is_none());
294 #[stable(feature = "rust1", since = "1.0.0")]
295 fn enumerate(self) -> Enumerate<Self> where Self: Sized {
296 Enumerate{iter: self, count: 0}
299 /// Creates an iterator that has a `.peek()` method
300 /// that returns an optional reference to the next element.
305 /// # #![feature(core)]
306 /// let xs = [100, 200, 300];
307 /// let mut it = xs.iter().cloned().peekable();
308 /// assert_eq!(*it.peek().unwrap(), 100);
309 /// assert_eq!(it.next().unwrap(), 100);
310 /// assert_eq!(it.next().unwrap(), 200);
311 /// assert_eq!(*it.peek().unwrap(), 300);
312 /// assert_eq!(*it.peek().unwrap(), 300);
313 /// assert_eq!(it.next().unwrap(), 300);
314 /// assert!(it.peek().is_none());
315 /// assert!(it.next().is_none());
318 #[stable(feature = "rust1", since = "1.0.0")]
319 fn peekable(self) -> Peekable<Self> where Self: Sized {
320 Peekable{iter: self, peeked: None}
323 /// Creates an iterator that invokes the predicate on elements
324 /// until it returns false. Once the predicate returns false, that
325 /// element and all further elements are yielded.
330 /// let a = [1, 2, 3, 4, 5];
331 /// let mut it = a.iter().skip_while(|&a| *a < 3);
332 /// assert_eq!(it.next().unwrap(), &3);
333 /// assert_eq!(it.next().unwrap(), &4);
334 /// assert_eq!(it.next().unwrap(), &5);
335 /// assert!(it.next().is_none());
338 #[stable(feature = "rust1", since = "1.0.0")]
339 fn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P> where
340 Self: Sized, P: FnMut(&Self::Item) -> bool,
342 SkipWhile{iter: self, flag: false, predicate: predicate}
345 /// Creates an iterator that yields elements so long as the predicate
346 /// returns true. After the predicate returns false for the first time, no
347 /// further elements will be yielded.
352 /// let a = [1, 2, 3, 4, 5];
353 /// let mut it = a.iter().take_while(|&a| *a < 3);
354 /// assert_eq!(it.next().unwrap(), &1);
355 /// assert_eq!(it.next().unwrap(), &2);
356 /// assert!(it.next().is_none());
359 #[stable(feature = "rust1", since = "1.0.0")]
360 fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P> where
361 Self: Sized, P: FnMut(&Self::Item) -> bool,
363 TakeWhile{iter: self, flag: false, predicate: predicate}
366 /// Creates an iterator that skips the first `n` elements of this iterator,
367 /// and then yields all further items.
372 /// let a = [1, 2, 3, 4, 5];
373 /// let mut it = a.iter().skip(3);
374 /// assert_eq!(it.next().unwrap(), &4);
375 /// assert_eq!(it.next().unwrap(), &5);
376 /// assert!(it.next().is_none());
379 #[stable(feature = "rust1", since = "1.0.0")]
380 fn skip(self, n: usize) -> Skip<Self> where Self: Sized {
381 Skip{iter: self, n: n}
384 /// Creates an iterator that yields the first `n` elements of this
390 /// let a = [1, 2, 3, 4, 5];
391 /// let mut it = a.iter().take(3);
392 /// assert_eq!(it.next().unwrap(), &1);
393 /// assert_eq!(it.next().unwrap(), &2);
394 /// assert_eq!(it.next().unwrap(), &3);
395 /// assert!(it.next().is_none());
398 #[stable(feature = "rust1", since = "1.0.0")]
399 fn take(self, n: usize) -> Take<Self> where Self: Sized, {
400 Take{iter: self, n: n}
403 /// Creates a new iterator that behaves in a similar fashion to fold.
404 /// There is a state which is passed between each iteration and can be
405 /// mutated as necessary. The yielded values from the closure are yielded
406 /// from the Scan instance when not `None`.
411 /// let a = [1, 2, 3, 4, 5];
412 /// let mut it = a.iter().scan(1, |fac, &x| {
416 /// assert_eq!(it.next().unwrap(), 1);
417 /// assert_eq!(it.next().unwrap(), 2);
418 /// assert_eq!(it.next().unwrap(), 6);
419 /// assert_eq!(it.next().unwrap(), 24);
420 /// assert_eq!(it.next().unwrap(), 120);
421 /// assert!(it.next().is_none());
424 #[stable(feature = "rust1", since = "1.0.0")]
425 fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>
426 where Self: Sized, F: FnMut(&mut St, Self::Item) -> Option<B>,
428 Scan{iter: self, f: f, state: initial_state}
431 /// Creates an iterator that maps each element to an iterator,
432 /// and yields the elements of the produced iterators.
437 /// # #![feature(core)]
439 /// let ys = [0, 1, 0, 1, 2];
440 /// let it = xs.iter().flat_map(|&x| (0..).take(x));
441 /// // Check that `it` has the same elements as `ys`
442 /// for (i, x) in it.enumerate() {
443 /// assert_eq!(x, ys[i]);
447 #[stable(feature = "rust1", since = "1.0.0")]
448 fn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F>
449 where Self: Sized, U: IntoIterator, F: FnMut(Self::Item) -> U,
451 FlatMap{iter: self, f: f, frontiter: None, backiter: None }
454 /// Creates an iterator that yields `None` forever after the underlying
455 /// iterator yields `None`. Random-access iterator behavior is not
456 /// affected, only single and double-ended iterator behavior.
461 /// fn process<U: Iterator<Item=i32>>(it: U) -> i32 {
462 /// let mut it = it.fuse();
464 /// for x in it.by_ref() {
470 /// // did we exhaust the iterator?
471 /// if it.next().is_none() {
476 /// let x = vec![1, 2, 3, 7, 8, 9];
477 /// assert_eq!(process(x.into_iter()), 6);
478 /// let x = vec![1, 2, 3];
479 /// assert_eq!(process(x.into_iter()), 1006);
482 #[stable(feature = "rust1", since = "1.0.0")]
483 fn fuse(self) -> Fuse<Self> where Self: Sized {
484 Fuse{iter: self, done: false}
487 /// Creates an iterator that calls a function with a reference to each
488 /// element before yielding it. This is often useful for debugging an
489 /// iterator pipeline.
494 /// # #![feature(core)]
496 /// let a = [1, 4, 2, 3, 8, 9, 6];
497 /// let sum: i32 = a.iter()
499 /// .inspect(|&x| println!("filtering {}", x))
500 /// .filter(|&x| x % 2 == 0)
501 /// .inspect(|&x| println!("{} made it through", x))
503 /// println!("{}", sum);
506 #[stable(feature = "rust1", since = "1.0.0")]
507 fn inspect<F>(self, f: F) -> Inspect<Self, F> where
508 Self: Sized, F: FnMut(&Self::Item),
510 Inspect{iter: self, f: f}
513 /// Creates a wrapper around a mutable reference to the iterator.
515 /// This is useful to allow applying iterator adaptors while still
516 /// retaining ownership of the original iterator value.
521 /// let mut it = 0..10;
522 /// // sum the first five values
523 /// let partial_sum = it.by_ref().take(5).fold(0, |a, b| a + b);
524 /// assert!(partial_sum == 10);
525 /// assert!(it.next() == Some(5));
527 #[stable(feature = "rust1", since = "1.0.0")]
528 fn by_ref(&mut self) -> &mut Self where Self: Sized { self }
530 /// Loops through the entire iterator, collecting all of the elements into
531 /// a container implementing `FromIterator`.
536 /// let expected = [1, 2, 3, 4, 5];
537 /// let actual: Vec<_> = expected.iter().cloned().collect();
538 /// assert_eq!(actual, expected);
541 #[stable(feature = "rust1", since = "1.0.0")]
542 fn collect<B: FromIterator<Self::Item>>(self) -> B where Self: Sized {
543 FromIterator::from_iter(self)
546 /// Loops through the entire iterator, collecting all of the elements into
547 /// one of two containers, depending on a predicate. The elements of the
548 /// first container satisfy the predicate, while the elements of the second
552 /// # #![feature(core)]
553 /// let vec = vec![1, 2, 3, 4];
554 /// let (even, odd): (Vec<_>, Vec<_>) = vec.into_iter().partition(|&n| n % 2 == 0);
555 /// assert_eq!(even, [2, 4]);
556 /// assert_eq!(odd, [1, 3]);
558 #[stable(feature = "rust1", since = "1.0.0")]
559 fn partition<B, F>(self, mut f: F) -> (B, B) where
561 B: Default + Extend<Self::Item>,
562 F: FnMut(&Self::Item) -> bool
564 let mut left: B = Default::default();
565 let mut right: B = Default::default();
569 left.extend(Some(x).into_iter())
571 right.extend(Some(x).into_iter())
578 /// Performs a fold operation over the entire iterator, returning the
579 /// eventual state at the end of the iteration.
584 /// let a = [1, 2, 3, 4, 5];
585 /// assert!(a.iter().fold(0, |acc, &item| acc + item) == 15);
588 #[stable(feature = "rust1", since = "1.0.0")]
589 fn fold<B, F>(self, init: B, mut f: F) -> B where
590 Self: Sized, F: FnMut(B, Self::Item) -> B,
592 let mut accum = init;
599 /// Tests whether the predicate holds true for all elements in the iterator.
604 /// let a = [1, 2, 3, 4, 5];
605 /// assert!(a.iter().all(|x| *x > 0));
606 /// assert!(!a.iter().all(|x| *x > 2));
609 #[stable(feature = "rust1", since = "1.0.0")]
610 fn all<F>(&mut self, mut f: F) -> bool where
611 Self: Sized, F: FnMut(Self::Item) -> bool
613 for x in self.by_ref() {
621 /// Tests whether any element of an iterator satisfies the specified
624 /// Does not consume the iterator past the first found element.
629 /// # #![feature(core)]
630 /// let a = [1, 2, 3, 4, 5];
631 /// let mut it = a.iter();
632 /// assert!(it.any(|x| *x == 3));
633 /// assert_eq!(&it[..], [4, 5]);
637 #[stable(feature = "rust1", since = "1.0.0")]
638 fn any<F>(&mut self, mut f: F) -> bool where
640 F: FnMut(Self::Item) -> bool
642 for x in self.by_ref() {
650 /// Returns the first element satisfying the specified predicate.
652 /// Does not consume the iterator past the first found element.
657 /// # #![feature(core)]
658 /// let a = [1, 2, 3, 4, 5];
659 /// let mut it = a.iter();
660 /// assert_eq!(it.find(|&x| *x == 3).unwrap(), &3);
661 /// assert_eq!(&it[..], [4, 5]);
663 #[stable(feature = "rust1", since = "1.0.0")]
664 fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
666 P: FnMut(&Self::Item) -> bool,
668 for x in self.by_ref() {
669 if predicate(&x) { return Some(x) }
674 /// Returns the index of the first element satisfying the specified predicate
676 /// Does not consume the iterator past the first found element.
681 /// # #![feature(core)]
682 /// let a = [1, 2, 3, 4, 5];
683 /// let mut it = a.iter();
684 /// assert_eq!(it.position(|x| *x == 3).unwrap(), 2);
685 /// assert_eq!(&it[..], [4, 5]);
687 #[stable(feature = "rust1", since = "1.0.0")]
688 fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
690 P: FnMut(Self::Item) -> bool,
693 for x in self.by_ref() {
702 /// Returns the index of the last element satisfying the specified predicate
704 /// If no element matches, `None` is returned.
706 /// Does not consume the iterator *before* the first found element.
711 /// # #![feature(core)]
712 /// let a = [1, 2, 2, 4, 5];
713 /// let mut it = a.iter();
714 /// assert_eq!(it.rposition(|x| *x == 2).unwrap(), 2);
715 /// assert_eq!(&it[..], [1, 2]);
717 #[stable(feature = "rust1", since = "1.0.0")]
718 fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
719 P: FnMut(Self::Item) -> bool,
720 Self: Sized + ExactSizeIterator + DoubleEndedIterator
722 let mut i = self.len();
724 while let Some(v) = self.next_back() {
733 /// Consumes the entire iterator to return the maximum element.
735 /// Returns the rightmost element if the comparison determines two elements
736 /// to be equally maximum.
741 /// let a = [1, 2, 3, 4, 5];
742 /// assert!(a.iter().max().unwrap() == &5);
745 #[stable(feature = "rust1", since = "1.0.0")]
746 fn max(self) -> Option<Self::Item> where Self: Sized, Self::Item: Ord
750 // switch to y even if it is only equal, to preserve
752 |_, x, _, y| *x <= *y)
756 /// Consumes the entire iterator to return the minimum element.
758 /// Returns the leftmost element if the comparison determines two elements
759 /// to be equally minimum.
764 /// let a = [1, 2, 3, 4, 5];
765 /// assert!(a.iter().min().unwrap() == &1);
768 #[stable(feature = "rust1", since = "1.0.0")]
769 fn min(self) -> Option<Self::Item> where Self: Sized, Self::Item: Ord
773 // only switch to y if it is strictly smaller, to
774 // preserve stability.
775 |_, x, _, y| *x > *y)
779 /// `min_max` finds the minimum and maximum elements in the iterator.
781 /// The return type `MinMaxResult` is an enum of three variants:
783 /// - `NoElements` if the iterator is empty.
784 /// - `OneElement(x)` if the iterator has exactly one element.
785 /// - `MinMax(x, y)` is returned otherwise, where `x <= y`. Two
786 /// values are equal if and only if there is more than one
787 /// element in the iterator and all elements are equal.
789 /// On an iterator of length `n`, `min_max` does `1.5 * n` comparisons,
790 /// and so is faster than calling `min` and `max` separately which does `2 *
796 /// # #![feature(core)]
797 /// use std::iter::MinMaxResult::{NoElements, OneElement, MinMax};
799 /// let a: [i32; 0] = [];
800 /// assert_eq!(a.iter().min_max(), NoElements);
803 /// assert!(a.iter().min_max() == OneElement(&1));
805 /// let a = [1, 2, 3, 4, 5];
806 /// assert!(a.iter().min_max() == MinMax(&1, &5));
808 /// let a = [1, 1, 1, 1];
809 /// assert!(a.iter().min_max() == MinMax(&1, &1));
811 #[unstable(feature = "core", reason = "return type may change")]
812 fn min_max(mut self) -> MinMaxResult<Self::Item> where Self: Sized, Self::Item: Ord
814 let (mut min, mut max) = match self.next() {
815 None => return NoElements,
818 None => return OneElement(x),
819 Some(y) => if x <= y {(x, y)} else {(y, x)}
825 // `first` and `second` are the two next elements we want to look
826 // at. We first compare `first` and `second` (#1). The smaller one
827 // is then compared to current minimum (#2). The larger one is
828 // compared to current maximum (#3). This way we do 3 comparisons
830 let first = match self.next() {
834 let second = match self.next() {
838 } else if first >= max {
846 if first < min { min = first }
847 if second >= max { max = second }
849 if second < min { min = second }
850 if first >= max { max = first }
857 /// Returns the element that gives the maximum value from the
858 /// specified function.
860 /// Returns the rightmost element if the comparison determines two elements
861 /// to be equally maximum.
866 /// # #![feature(core)]
868 /// let a = [-3_i32, 0, 1, 5, -10];
869 /// assert_eq!(*a.iter().max_by(|x| x.abs()).unwrap(), -10);
872 #[unstable(feature = "core",
873 reason = "may want to produce an Ordering directly; see #15311")]
874 fn max_by<B: Ord, F>(self, f: F) -> Option<Self::Item> where
876 F: FnMut(&Self::Item) -> B,
880 // switch to y even if it is only equal, to preserve
882 |x_p, _, y_p, _| x_p <= y_p)
886 /// Returns the element that gives the minimum value from the
887 /// specified function.
889 /// Returns the leftmost element if the comparison determines two elements
890 /// to be equally minimum.
895 /// # #![feature(core)]
897 /// let a = [-3_i32, 0, 1, 5, -10];
898 /// assert_eq!(*a.iter().min_by(|x| x.abs()).unwrap(), 0);
901 #[unstable(feature = "core",
902 reason = "may want to produce an Ordering directly; see #15311")]
903 fn min_by<B: Ord, F>(self, f: F) -> Option<Self::Item> where
905 F: FnMut(&Self::Item) -> B,
909 // only switch to y if it is strictly smaller, to
910 // preserve stability.
911 |x_p, _, y_p, _| x_p > y_p)
915 /// Change the direction of the iterator
917 /// The flipped iterator swaps the ends on an iterator that can already
918 /// be iterated from the front and from the back.
921 /// If the iterator also implements RandomAccessIterator, the flipped
922 /// iterator is also random access, with the indices starting at the back
923 /// of the original iterator.
925 /// Note: Random access with flipped indices still only applies to the first
926 /// `std::usize::MAX` elements of the original iterator.
928 #[stable(feature = "rust1", since = "1.0.0")]
929 fn rev(self) -> Rev<Self> where Self: Sized + DoubleEndedIterator {
933 /// Converts an iterator of pairs into a pair of containers.
935 /// Loops through the entire iterator, collecting the first component of
936 /// each item into one new container, and the second component into another.
941 /// # #![feature(core)]
942 /// let a = [(1, 2), (3, 4)];
943 /// let (left, right): (Vec<_>, Vec<_>) = a.iter().cloned().unzip();
944 /// assert_eq!(left, [1, 3]);
945 /// assert_eq!(right, [2, 4]);
947 #[stable(feature = "rust1", since = "1.0.0")]
948 fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB) where
949 FromA: Default + Extend<A>,
950 FromB: Default + Extend<B>,
951 Self: Sized + Iterator<Item=(A, B)>,
953 struct SizeHint<A>(usize, Option<usize>, marker::PhantomData<A>);
954 impl<A> Iterator for SizeHint<A> {
957 fn next(&mut self) -> Option<A> { None }
958 fn size_hint(&self) -> (usize, Option<usize>) {
963 let (lo, hi) = self.size_hint();
964 let mut ts: FromA = Default::default();
965 let mut us: FromB = Default::default();
967 ts.extend(SizeHint(lo, hi, marker::PhantomData));
968 us.extend(SizeHint(lo, hi, marker::PhantomData));
971 ts.extend(Some(t).into_iter());
972 us.extend(Some(u).into_iter());
978 /// Creates an iterator that clones the elements it yields. Useful for
979 /// converting an Iterator<&T> to an Iterator<T>.
980 #[stable(feature = "rust1", since = "1.0.0")]
981 fn cloned<'a, T: 'a>(self) -> Cloned<Self>
982 where Self: Sized + Iterator<Item=&'a T>, T: Clone
987 /// Repeats an iterator endlessly
993 /// let mut it = a.iter().cycle();
994 /// assert_eq!(it.next().unwrap(), &1);
995 /// assert_eq!(it.next().unwrap(), &2);
996 /// assert_eq!(it.next().unwrap(), &1);
998 #[stable(feature = "rust1", since = "1.0.0")]
1000 fn cycle(self) -> Cycle<Self> where Self: Sized + Clone {
1001 Cycle{orig: self.clone(), iter: self}
1004 /// Use an iterator to reverse a container in place.
1005 #[unstable(feature = "core",
1006 reason = "uncertain about placement or widespread use")]
1007 fn reverse_in_place<'a, T: 'a>(&mut self) where
1008 Self: Sized + Iterator<Item=&'a mut T> + DoubleEndedIterator
1011 match (self.next(), self.next_back()) {
1012 (Some(x), Some(y)) => mem::swap(x, y),
1018 /// Iterates over the entire iterator, summing up all the elements
1023 /// # #![feature(core)]
1025 /// let a = [1, 2, 3, 4, 5];
1026 /// let mut it = a.iter().cloned();
1027 /// assert!(it.sum::<i32>() == 15);
1029 #[unstable(feature="core")]
1030 fn sum<S=<Self as Iterator>::Item>(self) -> S where
1031 S: Add<Self::Item, Output=S> + Zero,
1034 self.fold(Zero::zero(), |s, e| s + e)
1037 /// Iterates over the entire iterator, multiplying all the elements
1042 /// # #![feature(core)]
1044 /// fn factorial(n: u32) -> u32 {
1045 /// (1..).take_while(|&i| i <= n).product()
1047 /// assert!(factorial(0) == 1);
1048 /// assert!(factorial(1) == 1);
1049 /// assert!(factorial(5) == 120);
1051 #[unstable(feature="core")]
1052 fn product<P=<Self as Iterator>::Item>(self) -> P where
1053 P: Mul<Self::Item, Output=P> + One,
1056 self.fold(One::one(), |p, e| p * e)
1060 /// Select an element from an iterator based on the given projection
1061 /// and "comparison" function.
1063 /// This is an idiosyncratic helper to try to factor out the
1064 /// commonalities of {max,min}{,_by}. In particular, this avoids
1065 /// having to implement optimisations several times.
1067 fn select_fold1<I,B, FProj, FCmp>(mut it: I,
1069 mut f_cmp: FCmp) -> Option<(B, I::Item)>
1071 FProj: FnMut(&I::Item) -> B,
1072 FCmp: FnMut(&B, &I::Item, &B, &I::Item) -> bool
1074 // start with the first element as our selection. This avoids
1075 // having to use `Option`s inside the loop, translating to a
1076 // sizeable performance gain (6x in one case).
1077 it.next().map(|mut sel| {
1078 let mut sel_p = f_proj(&sel);
1081 let x_p = f_proj(&x);
1082 if f_cmp(&sel_p, &sel, &x_p, &x) {
1091 #[stable(feature = "rust1", since = "1.0.0")]
1092 impl<'a, I: Iterator + ?Sized> Iterator for &'a mut I {
1093 type Item = I::Item;
1094 fn next(&mut self) -> Option<I::Item> { (**self).next() }
1095 fn size_hint(&self) -> (usize, Option<usize>) { (**self).size_hint() }
1098 /// Conversion from an `Iterator`
1099 #[stable(feature = "rust1", since = "1.0.0")]
1100 #[rustc_on_unimplemented="a collection of type `{Self}` cannot be \
1101 built from an iterator over elements of type `{A}`"]
1102 pub trait FromIterator<A> {
1103 /// Builds a container with elements from something iterable.
1108 /// use std::collections::HashSet;
1109 /// use std::iter::FromIterator;
1111 /// let colors_vec = vec!["red", "red", "yellow", "blue"];
1112 /// let colors_set = HashSet::<&str>::from_iter(colors_vec);
1113 /// assert_eq!(colors_set.len(), 3);
1116 /// `FromIterator` is more commonly used implicitly via the
1117 /// `Iterator::collect` method:
1120 /// use std::collections::HashSet;
1122 /// let colors_vec = vec!["red", "red", "yellow", "blue"];
1123 /// let colors_set = colors_vec.into_iter().collect::<HashSet<&str>>();
1124 /// assert_eq!(colors_set.len(), 3);
1126 #[stable(feature = "rust1", since = "1.0.0")]
1127 fn from_iter<T: IntoIterator<Item=A>>(iterator: T) -> Self;
1130 /// Conversion into an `Iterator`
1132 /// Implementing this trait allows you to use your type with Rust's `for` loop. See
1133 /// the [module level documentation](index.html) for more details.
1134 #[stable(feature = "rust1", since = "1.0.0")]
1135 pub trait IntoIterator {
1136 /// The type of the elements being iterated
1137 #[stable(feature = "rust1", since = "1.0.0")]
1140 /// A container for iterating over elements of type `Item`
1141 #[stable(feature = "rust1", since = "1.0.0")]
1142 type IntoIter: Iterator<Item=Self::Item>;
1144 /// Consumes `Self` and returns an iterator over it
1145 #[stable(feature = "rust1", since = "1.0.0")]
1146 fn into_iter(self) -> Self::IntoIter;
1149 #[stable(feature = "rust1", since = "1.0.0")]
1150 impl<I: Iterator> IntoIterator for I {
1151 type Item = I::Item;
1154 fn into_iter(self) -> I {
1159 /// A type growable from an `Iterator` implementation
1160 #[stable(feature = "rust1", since = "1.0.0")]
1161 pub trait Extend<A> {
1162 /// Extends a container with the elements yielded by an arbitrary iterator
1163 #[stable(feature = "rust1", since = "1.0.0")]
1164 fn extend<T: IntoIterator<Item=A>>(&mut self, iterable: T);
1167 /// A range iterator able to yield elements from both ends
1169 /// A `DoubleEndedIterator` can be thought of as a deque in that `next()` and
1170 /// `next_back()` exhaust elements from the *same* range, and do not work
1171 /// independently of each other.
1172 #[stable(feature = "rust1", since = "1.0.0")]
1173 pub trait DoubleEndedIterator: Iterator {
1174 /// Yields an element from the end of the range, returning `None` if the
1176 #[stable(feature = "rust1", since = "1.0.0")]
1177 fn next_back(&mut self) -> Option<Self::Item>;
1180 #[stable(feature = "rust1", since = "1.0.0")]
1181 impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I {
1182 fn next_back(&mut self) -> Option<I::Item> { (**self).next_back() }
1185 /// An object implementing random access indexing by `usize`
1187 /// A `RandomAccessIterator` should be either infinite or a
1188 /// `DoubleEndedIterator`. Calling `next()` or `next_back()` on a
1189 /// `RandomAccessIterator` reduces the indexable range accordingly. That is,
1190 /// `it.idx(1)` will become `it.idx(0)` after `it.next()` is called.
1191 #[unstable(feature = "core",
1192 reason = "not widely used, may be better decomposed into Index \
1193 and ExactSizeIterator")]
1194 pub trait RandomAccessIterator: Iterator {
1195 /// Returns the number of indexable elements. At most `std::usize::MAX`
1196 /// elements are indexable, even if the iterator represents a longer range.
1197 fn indexable(&self) -> usize;
1199 /// Returns an element at an index, or `None` if the index is out of bounds
1200 fn idx(&mut self, index: usize) -> Option<Self::Item>;
1203 /// An iterator that knows its exact length
1205 /// This trait is a helper for iterators like the vector iterator, so that
1206 /// it can support double-ended enumeration.
1208 /// `Iterator::size_hint` *must* return the exact size of the iterator.
1209 /// Note that the size must fit in `usize`.
1210 #[stable(feature = "rust1", since = "1.0.0")]
1211 pub trait ExactSizeIterator: Iterator {
1213 #[stable(feature = "rust1", since = "1.0.0")]
1214 /// Returns the exact length of the iterator.
1215 fn len(&self) -> usize {
1216 let (lower, upper) = self.size_hint();
1217 // Note: This assertion is overly defensive, but it checks the invariant
1218 // guaranteed by the trait. If this trait were rust-internal,
1219 // we could use debug_assert!; assert_eq! will check all Rust user
1220 // implementations too.
1221 assert_eq!(upper, Some(lower));
1226 #[stable(feature = "rust1", since = "1.0.0")]
1227 impl<'a, I: ExactSizeIterator + ?Sized> ExactSizeIterator for &'a mut I {}
1229 // All adaptors that preserve the size of the wrapped iterator are fine
1230 // Adaptors that may overflow in `size_hint` are not, i.e. `Chain`.
1231 #[stable(feature = "rust1", since = "1.0.0")]
1232 impl<I> ExactSizeIterator for Enumerate<I> where I: ExactSizeIterator {}
1233 #[stable(feature = "rust1", since = "1.0.0")]
1234 impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F> where
1237 #[stable(feature = "rust1", since = "1.0.0")]
1238 impl<I> ExactSizeIterator for Rev<I>
1239 where I: ExactSizeIterator + DoubleEndedIterator {}
1240 #[stable(feature = "rust1", since = "1.0.0")]
1241 impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F> where
1242 F: FnMut(I::Item) -> B,
1244 #[stable(feature = "rust1", since = "1.0.0")]
1245 impl<A, B> ExactSizeIterator for Zip<A, B>
1246 where A: ExactSizeIterator, B: ExactSizeIterator {}
1248 /// An double-ended iterator with the direction inverted
1250 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1251 #[stable(feature = "rust1", since = "1.0.0")]
1256 #[stable(feature = "rust1", since = "1.0.0")]
1257 impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
1258 type Item = <I as Iterator>::Item;
1261 fn next(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next_back() }
1263 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
1266 #[stable(feature = "rust1", since = "1.0.0")]
1267 impl<I> DoubleEndedIterator for Rev<I> where I: DoubleEndedIterator {
1269 fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next() }
1272 #[unstable(feature = "core", reason = "trait is experimental")]
1273 impl<I> RandomAccessIterator for Rev<I>
1274 where I: DoubleEndedIterator + RandomAccessIterator
1277 fn indexable(&self) -> usize { self.iter.indexable() }
1279 fn idx(&mut self, index: usize) -> Option<<I as Iterator>::Item> {
1280 let amt = self.indexable();
1282 self.iter.idx(amt - index - 1)
1289 /// `MinMaxResult` is an enum returned by `min_max`. See `Iterator::min_max` for
1291 #[derive(Clone, PartialEq, Debug)]
1292 #[unstable(feature = "core",
1293 reason = "unclear whether such a fine-grained result is widely useful")]
1294 pub enum MinMaxResult<T> {
1298 /// Iterator with one element, so the minimum and maximum are the same
1301 /// More than one element in the iterator, the first element is not larger
1306 impl<T: Clone> MinMaxResult<T> {
1307 /// `into_option` creates an `Option` of type `(T,T)`. The returned `Option`
1308 /// has variant `None` if and only if the `MinMaxResult` has variant
1309 /// `NoElements`. Otherwise variant `Some(x,y)` is returned where `x <= y`.
1310 /// If `MinMaxResult` has variant `OneElement(x)`, performing this operation
1311 /// will make one clone of `x`.
1316 /// # #![feature(core)]
1317 /// use std::iter::MinMaxResult::{self, NoElements, OneElement, MinMax};
1319 /// let r: MinMaxResult<i32> = NoElements;
1320 /// assert_eq!(r.into_option(), None);
1322 /// let r = OneElement(1);
1323 /// assert_eq!(r.into_option(), Some((1, 1)));
1325 /// let r = MinMax(1, 2);
1326 /// assert_eq!(r.into_option(), Some((1, 2)));
1328 #[unstable(feature = "core", reason = "type is unstable")]
1329 pub fn into_option(self) -> Option<(T,T)> {
1332 OneElement(x) => Some((x.clone(), x)),
1333 MinMax(x, y) => Some((x, y))
1338 /// An iterator that clones the elements of an underlying iterator
1339 #[unstable(feature = "core", reason = "recent addition")]
1340 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1342 pub struct Cloned<I> {
1346 #[stable(feature = "rust1", since = "1.0.0")]
1347 impl<'a, I, T: 'a> Iterator for Cloned<I>
1348 where I: Iterator<Item=&'a T>, T: Clone
1352 fn next(&mut self) -> Option<T> {
1353 self.it.next().cloned()
1356 fn size_hint(&self) -> (usize, Option<usize>) {
1361 #[stable(feature = "rust1", since = "1.0.0")]
1362 impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
1363 where I: DoubleEndedIterator<Item=&'a T>, T: Clone
1365 fn next_back(&mut self) -> Option<T> {
1366 self.it.next_back().cloned()
1370 #[stable(feature = "rust1", since = "1.0.0")]
1371 impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
1372 where I: ExactSizeIterator<Item=&'a T>, T: Clone
1375 #[unstable(feature = "core", reason = "trait is experimental")]
1376 impl<'a, I, T: 'a> RandomAccessIterator for Cloned<I>
1377 where I: RandomAccessIterator<Item=&'a T>, T: Clone
1380 fn indexable(&self) -> usize {
1385 fn idx(&mut self, index: usize) -> Option<T> {
1386 self.it.idx(index).cloned()
1390 /// An iterator that repeats endlessly
1392 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1393 #[stable(feature = "rust1", since = "1.0.0")]
1394 pub struct Cycle<I> {
1399 #[stable(feature = "rust1", since = "1.0.0")]
1400 impl<I> Iterator for Cycle<I> where I: Clone + Iterator {
1401 type Item = <I as Iterator>::Item;
1404 fn next(&mut self) -> Option<<I as Iterator>::Item> {
1405 match self.iter.next() {
1406 None => { self.iter = self.orig.clone(); self.iter.next() }
1412 fn size_hint(&self) -> (usize, Option<usize>) {
1413 // the cycle iterator is either empty or infinite
1414 match self.orig.size_hint() {
1415 sz @ (0, Some(0)) => sz,
1416 (0, _) => (0, None),
1417 _ => (usize::MAX, None)
1422 #[unstable(feature = "core", reason = "trait is experimental")]
1423 impl<I> RandomAccessIterator for Cycle<I> where
1424 I: Clone + RandomAccessIterator,
1427 fn indexable(&self) -> usize {
1428 if self.orig.indexable() > 0 {
1436 fn idx(&mut self, index: usize) -> Option<<I as Iterator>::Item> {
1437 let liter = self.iter.indexable();
1438 let lorig = self.orig.indexable();
1441 } else if index < liter {
1442 self.iter.idx(index)
1444 self.orig.idx((index - liter) % lorig)
1449 /// An iterator that strings two iterators together
1451 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1452 #[stable(feature = "rust1", since = "1.0.0")]
1453 pub struct Chain<A, B> {
1459 #[stable(feature = "rust1", since = "1.0.0")]
1460 impl<A, B> Iterator for Chain<A, B> where
1462 B: Iterator<Item = A::Item>
1464 type Item = A::Item;
1467 fn next(&mut self) -> Option<A::Item> {
1471 match self.a.next() {
1472 Some(x) => return Some(x),
1481 fn size_hint(&self) -> (usize, Option<usize>) {
1482 let (a_lower, a_upper) = self.a.size_hint();
1483 let (b_lower, b_upper) = self.b.size_hint();
1485 let lower = a_lower.saturating_add(b_lower);
1487 let upper = match (a_upper, b_upper) {
1488 (Some(x), Some(y)) => x.checked_add(y),
1496 #[stable(feature = "rust1", since = "1.0.0")]
1497 impl<A, B> DoubleEndedIterator for Chain<A, B> where
1498 A: DoubleEndedIterator,
1499 B: DoubleEndedIterator<Item=A::Item>,
1502 fn next_back(&mut self) -> Option<A::Item> {
1503 match self.b.next_back() {
1505 None => self.a.next_back()
1510 #[unstable(feature = "core", reason = "trait is experimental")]
1511 impl<A, B> RandomAccessIterator for Chain<A, B> where
1512 A: RandomAccessIterator,
1513 B: RandomAccessIterator<Item = A::Item>,
1516 fn indexable(&self) -> usize {
1517 let (a, b) = (self.a.indexable(), self.b.indexable());
1522 fn idx(&mut self, index: usize) -> Option<A::Item> {
1523 let len = self.a.indexable();
1527 self.b.idx(index - len)
1532 /// An iterator that iterates two other iterators simultaneously
1534 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1535 #[stable(feature = "rust1", since = "1.0.0")]
1536 pub struct Zip<A, B> {
1541 #[stable(feature = "rust1", since = "1.0.0")]
1542 impl<A, B> Iterator for Zip<A, B> where A: Iterator, B: Iterator
1544 type Item = (A::Item, B::Item);
1547 fn next(&mut self) -> Option<(A::Item, B::Item)> {
1548 self.a.next().and_then(|x| {
1549 self.b.next().and_then(|y| {
1556 fn size_hint(&self) -> (usize, Option<usize>) {
1557 let (a_lower, a_upper) = self.a.size_hint();
1558 let (b_lower, b_upper) = self.b.size_hint();
1560 let lower = cmp::min(a_lower, b_lower);
1562 let upper = match (a_upper, b_upper) {
1563 (Some(x), Some(y)) => Some(cmp::min(x,y)),
1564 (Some(x), None) => Some(x),
1565 (None, Some(y)) => Some(y),
1566 (None, None) => None
1573 #[stable(feature = "rust1", since = "1.0.0")]
1574 impl<A, B> DoubleEndedIterator for Zip<A, B> where
1575 A: DoubleEndedIterator + ExactSizeIterator,
1576 B: DoubleEndedIterator + ExactSizeIterator,
1579 fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
1580 let a_sz = self.a.len();
1581 let b_sz = self.b.len();
1583 // Adjust a, b to equal length
1585 for _ in 0..a_sz - b_sz { self.a.next_back(); }
1587 for _ in 0..b_sz - a_sz { self.b.next_back(); }
1590 match (self.a.next_back(), self.b.next_back()) {
1591 (Some(x), Some(y)) => Some((x, y)),
1592 (None, None) => None,
1593 _ => unreachable!(),
1598 #[unstable(feature = "core", reason = "trait is experimental")]
1599 impl<A, B> RandomAccessIterator for Zip<A, B> where
1600 A: RandomAccessIterator,
1601 B: RandomAccessIterator
1604 fn indexable(&self) -> usize {
1605 cmp::min(self.a.indexable(), self.b.indexable())
1609 fn idx(&mut self, index: usize) -> Option<(A::Item, B::Item)> {
1610 self.a.idx(index).and_then(|x| {
1611 self.b.idx(index).and_then(|y| {
1618 /// An iterator that maps the values of `iter` with `f`
1619 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1620 #[stable(feature = "rust1", since = "1.0.0")]
1622 pub struct Map<I, F> {
1627 #[stable(feature = "rust1", since = "1.0.0")]
1628 impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
1632 fn next(&mut self) -> Option<B> {
1633 self.iter.next().map(|a| (self.f)(a))
1637 fn size_hint(&self) -> (usize, Option<usize>) {
1638 self.iter.size_hint()
1642 #[stable(feature = "rust1", since = "1.0.0")]
1643 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where
1644 F: FnMut(I::Item) -> B,
1647 fn next_back(&mut self) -> Option<B> {
1648 self.iter.next_back().map(|a| (self.f)(a))
1652 #[unstable(feature = "core", reason = "trait is experimental")]
1653 impl<B, I: RandomAccessIterator, F> RandomAccessIterator for Map<I, F> where
1654 F: FnMut(I::Item) -> B,
1657 fn indexable(&self) -> usize {
1658 self.iter.indexable()
1662 fn idx(&mut self, index: usize) -> Option<B> {
1663 self.iter.idx(index).map(|a| (self.f)(a))
1667 /// An iterator that filters the elements of `iter` with `predicate`
1668 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1669 #[stable(feature = "rust1", since = "1.0.0")]
1671 pub struct Filter<I, P> {
1676 #[stable(feature = "rust1", since = "1.0.0")]
1677 impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {
1678 type Item = I::Item;
1681 fn next(&mut self) -> Option<I::Item> {
1682 for x in self.iter.by_ref() {
1683 if (self.predicate)(&x) {
1691 fn size_hint(&self) -> (usize, Option<usize>) {
1692 let (_, upper) = self.iter.size_hint();
1693 (0, upper) // can't know a lower bound, due to the predicate
1697 #[stable(feature = "rust1", since = "1.0.0")]
1698 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
1699 where P: FnMut(&I::Item) -> bool,
1702 fn next_back(&mut self) -> Option<I::Item> {
1703 for x in self.iter.by_ref().rev() {
1704 if (self.predicate)(&x) {
1712 /// An iterator that uses `f` to both filter and map elements from `iter`
1713 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1714 #[stable(feature = "rust1", since = "1.0.0")]
1716 pub struct FilterMap<I, F> {
1721 #[stable(feature = "rust1", since = "1.0.0")]
1722 impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
1723 where F: FnMut(I::Item) -> Option<B>,
1728 fn next(&mut self) -> Option<B> {
1729 for x in self.iter.by_ref() {
1730 if let Some(y) = (self.f)(x) {
1738 fn size_hint(&self) -> (usize, Option<usize>) {
1739 let (_, upper) = self.iter.size_hint();
1740 (0, upper) // can't know a lower bound, due to the predicate
1744 #[stable(feature = "rust1", since = "1.0.0")]
1745 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
1746 where F: FnMut(I::Item) -> Option<B>,
1749 fn next_back(&mut self) -> Option<B> {
1750 for x in self.iter.by_ref().rev() {
1751 if let Some(y) = (self.f)(x) {
1759 /// An iterator that yields the current count and the element during iteration
1761 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1762 #[stable(feature = "rust1", since = "1.0.0")]
1763 pub struct Enumerate<I> {
1768 #[stable(feature = "rust1", since = "1.0.0")]
1769 impl<I> Iterator for Enumerate<I> where I: Iterator {
1770 type Item = (usize, <I as Iterator>::Item);
1773 fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1774 self.iter.next().map(|a| {
1775 let ret = (self.count, a);
1782 fn size_hint(&self) -> (usize, Option<usize>) {
1783 self.iter.size_hint()
1787 #[stable(feature = "rust1", since = "1.0.0")]
1788 impl<I> DoubleEndedIterator for Enumerate<I> where
1789 I: ExactSizeIterator + DoubleEndedIterator
1792 fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1793 self.iter.next_back().map(|a| {
1794 let len = self.iter.len();
1795 (self.count + len, a)
1800 #[unstable(feature = "core", reason = "trait is experimental")]
1801 impl<I> RandomAccessIterator for Enumerate<I> where I: RandomAccessIterator {
1803 fn indexable(&self) -> usize {
1804 self.iter.indexable()
1808 fn idx(&mut self, index: usize) -> Option<(usize, <I as Iterator>::Item)> {
1809 self.iter.idx(index).map(|a| (self.count + index, a))
1813 /// An iterator with a `peek()` that returns an optional reference to the next element.
1814 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1815 #[stable(feature = "rust1", since = "1.0.0")]
1816 pub struct Peekable<I: Iterator> {
1818 peeked: Option<I::Item>,
1821 impl<I: Iterator + Clone> Clone for Peekable<I> where I::Item: Clone {
1822 fn clone(&self) -> Peekable<I> {
1824 iter: self.iter.clone(),
1825 peeked: self.peeked.clone(),
1830 #[stable(feature = "rust1", since = "1.0.0")]
1831 impl<I: Iterator> Iterator for Peekable<I> {
1832 type Item = I::Item;
1835 fn next(&mut self) -> Option<I::Item> {
1837 Some(_) => self.peeked.take(),
1838 None => self.iter.next(),
1843 fn size_hint(&self) -> (usize, Option<usize>) {
1844 let (lo, hi) = self.iter.size_hint();
1845 if self.peeked.is_some() {
1846 let lo = lo.saturating_add(1);
1847 let hi = hi.and_then(|x| x.checked_add(1));
1855 #[stable(feature = "rust1", since = "1.0.0")]
1856 impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
1858 #[stable(feature = "rust1", since = "1.0.0")]
1859 impl<I: Iterator> Peekable<I> {
1860 /// Returns a reference to the next element of the iterator with out
1861 /// advancing it, or None if the iterator is exhausted.
1863 #[stable(feature = "rust1", since = "1.0.0")]
1864 pub fn peek(&mut self) -> Option<&I::Item> {
1865 if self.peeked.is_none() {
1866 self.peeked = self.iter.next();
1869 Some(ref value) => Some(value),
1874 /// Checks whether peekable iterator is empty or not.
1876 pub fn is_empty(&mut self) -> bool {
1877 self.peek().is_none()
1881 /// An iterator that rejects elements while `predicate` is true
1882 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1883 #[stable(feature = "rust1", since = "1.0.0")]
1885 pub struct SkipWhile<I, P> {
1891 #[stable(feature = "rust1", since = "1.0.0")]
1892 impl<I: Iterator, P> Iterator for SkipWhile<I, P>
1893 where P: FnMut(&I::Item) -> bool
1895 type Item = I::Item;
1898 fn next(&mut self) -> Option<I::Item> {
1899 for x in self.iter.by_ref() {
1900 if self.flag || !(self.predicate)(&x) {
1909 fn size_hint(&self) -> (usize, Option<usize>) {
1910 let (_, upper) = self.iter.size_hint();
1911 (0, upper) // can't know a lower bound, due to the predicate
1915 /// An iterator that only accepts elements while `predicate` is true
1916 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1917 #[stable(feature = "rust1", since = "1.0.0")]
1919 pub struct TakeWhile<I, P> {
1925 #[stable(feature = "rust1", since = "1.0.0")]
1926 impl<I: Iterator, P> Iterator for TakeWhile<I, P>
1927 where P: FnMut(&I::Item) -> bool
1929 type Item = I::Item;
1932 fn next(&mut self) -> Option<I::Item> {
1936 self.iter.next().and_then(|x| {
1937 if (self.predicate)(&x) {
1948 fn size_hint(&self) -> (usize, Option<usize>) {
1949 let (_, upper) = self.iter.size_hint();
1950 (0, upper) // can't know a lower bound, due to the predicate
1954 /// An iterator that skips over `n` elements of `iter`.
1956 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1957 #[stable(feature = "rust1", since = "1.0.0")]
1958 pub struct Skip<I> {
1963 #[stable(feature = "rust1", since = "1.0.0")]
1964 impl<I> Iterator for Skip<I> where I: Iterator {
1965 type Item = <I as Iterator>::Item;
1968 fn next(&mut self) -> Option<<I as Iterator>::Item> {
1969 let mut next = self.iter.next();
1978 next = self.iter.next();
1993 fn size_hint(&self) -> (usize, Option<usize>) {
1994 let (lower, upper) = self.iter.size_hint();
1996 let lower = lower.saturating_sub(self.n);
1997 let upper = upper.map(|x| x.saturating_sub(self.n));
2003 #[unstable(feature = "core", reason = "trait is experimental")]
2004 impl<I> RandomAccessIterator for Skip<I> where I: RandomAccessIterator{
2006 fn indexable(&self) -> usize {
2007 self.iter.indexable().saturating_sub(self.n)
2011 fn idx(&mut self, index: usize) -> Option<<I as Iterator>::Item> {
2012 if index >= self.indexable() {
2015 self.iter.idx(index + self.n)
2020 #[stable(feature = "rust1", since = "1.0.0")]
2021 impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
2023 /// An iterator that only iterates over the first `n` iterations of `iter`.
2025 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2026 #[stable(feature = "rust1", since = "1.0.0")]
2027 pub struct Take<I> {
2032 #[stable(feature = "rust1", since = "1.0.0")]
2033 impl<I> Iterator for Take<I> where I: Iterator{
2034 type Item = <I as Iterator>::Item;
2037 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2047 fn size_hint(&self) -> (usize, Option<usize>) {
2048 let (lower, upper) = self.iter.size_hint();
2050 let lower = cmp::min(lower, self.n);
2052 let upper = match upper {
2053 Some(x) if x < self.n => Some(x),
2061 #[unstable(feature = "core", reason = "trait is experimental")]
2062 impl<I> RandomAccessIterator for Take<I> where I: RandomAccessIterator{
2064 fn indexable(&self) -> usize {
2065 cmp::min(self.iter.indexable(), self.n)
2069 fn idx(&mut self, index: usize) -> Option<<I as Iterator>::Item> {
2070 if index >= self.n {
2073 self.iter.idx(index)
2078 #[stable(feature = "rust1", since = "1.0.0")]
2079 impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
2082 /// An iterator to maintain state while iterating another iterator
2083 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2084 #[stable(feature = "rust1", since = "1.0.0")]
2086 pub struct Scan<I, St, F> {
2090 /// The current internal state to be passed to the closure next.
2091 #[unstable(feature = "core")]
2095 #[stable(feature = "rust1", since = "1.0.0")]
2096 impl<B, I, St, F> Iterator for Scan<I, St, F> where
2098 F: FnMut(&mut St, I::Item) -> Option<B>,
2103 fn next(&mut self) -> Option<B> {
2104 self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
2108 fn size_hint(&self) -> (usize, Option<usize>) {
2109 let (_, upper) = self.iter.size_hint();
2110 (0, upper) // can't know a lower bound, due to the scan function
2114 /// An iterator that maps each element to an iterator,
2115 /// and yields the elements of the produced iterators
2117 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2118 #[stable(feature = "rust1", since = "1.0.0")]
2120 pub struct FlatMap<I, U: IntoIterator, F> {
2123 frontiter: Option<U::IntoIter>,
2124 backiter: Option<U::IntoIter>,
2127 #[stable(feature = "rust1", since = "1.0.0")]
2128 impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F>
2129 where F: FnMut(I::Item) -> U,
2131 type Item = U::Item;
2134 fn next(&mut self) -> Option<U::Item> {
2136 if let Some(ref mut inner) = self.frontiter {
2137 if let Some(x) = inner.by_ref().next() {
2141 match self.iter.next().map(|x| (self.f)(x)) {
2142 None => return self.backiter.as_mut().and_then(|it| it.next()),
2143 next => self.frontiter = next.map(IntoIterator::into_iter),
2149 fn size_hint(&self) -> (usize, Option<usize>) {
2150 let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
2151 let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
2152 let lo = flo.saturating_add(blo);
2153 match (self.iter.size_hint(), fhi, bhi) {
2154 ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
2160 #[stable(feature = "rust1", since = "1.0.0")]
2161 impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F> where
2162 F: FnMut(I::Item) -> U,
2164 U::IntoIter: DoubleEndedIterator
2167 fn next_back(&mut self) -> Option<U::Item> {
2169 if let Some(ref mut inner) = self.backiter {
2170 if let Some(y) = inner.next_back() {
2174 match self.iter.next_back().map(|x| (self.f)(x)) {
2175 None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
2176 next => self.backiter = next.map(IntoIterator::into_iter),
2182 /// An iterator that yields `None` forever after the underlying iterator
2183 /// yields `None` once.
2185 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2186 #[stable(feature = "rust1", since = "1.0.0")]
2187 pub struct Fuse<I> {
2192 #[stable(feature = "rust1", since = "1.0.0")]
2193 impl<I> Iterator for Fuse<I> where I: Iterator {
2194 type Item = <I as Iterator>::Item;
2197 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2201 let next = self.iter.next();
2202 self.done = next.is_none();
2208 fn size_hint(&self) -> (usize, Option<usize>) {
2212 self.iter.size_hint()
2217 #[stable(feature = "rust1", since = "1.0.0")]
2218 impl<I> DoubleEndedIterator for Fuse<I> where I: DoubleEndedIterator {
2220 fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
2224 let next = self.iter.next_back();
2225 self.done = next.is_none();
2231 // Allow RandomAccessIterators to be fused without affecting random-access behavior
2232 #[unstable(feature = "core", reason = "trait is experimental")]
2233 impl<I> RandomAccessIterator for Fuse<I> where I: RandomAccessIterator {
2235 fn indexable(&self) -> usize {
2236 self.iter.indexable()
2240 fn idx(&mut self, index: usize) -> Option<<I as Iterator>::Item> {
2241 self.iter.idx(index)
2245 #[stable(feature = "rust1", since = "1.0.0")]
2246 impl<I> ExactSizeIterator for Fuse<I> where I: ExactSizeIterator {}
2249 /// Resets the `Fuse` such that the next call to `.next()` or
2250 /// `.next_back()` will call the underlying iterator again even if it
2251 /// previously returned `None`.
2253 #[unstable(feature = "core", reason = "seems marginal")]
2254 pub fn reset_fuse(&mut self) {
2259 /// An iterator that calls a function with a reference to each
2260 /// element before yielding it.
2261 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2262 #[stable(feature = "rust1", since = "1.0.0")]
2264 pub struct Inspect<I, F> {
2269 impl<I: Iterator, F> Inspect<I, F> where F: FnMut(&I::Item) {
2271 fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
2272 if let Some(ref a) = elt {
2280 #[stable(feature = "rust1", since = "1.0.0")]
2281 impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) {
2282 type Item = I::Item;
2285 fn next(&mut self) -> Option<I::Item> {
2286 let next = self.iter.next();
2287 self.do_inspect(next)
2291 fn size_hint(&self) -> (usize, Option<usize>) {
2292 self.iter.size_hint()
2296 #[stable(feature = "rust1", since = "1.0.0")]
2297 impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
2298 where F: FnMut(&I::Item),
2301 fn next_back(&mut self) -> Option<I::Item> {
2302 let next = self.iter.next_back();
2303 self.do_inspect(next)
2307 #[unstable(feature = "core", reason = "trait is experimental")]
2308 impl<I: RandomAccessIterator, F> RandomAccessIterator for Inspect<I, F>
2309 where F: FnMut(&I::Item),
2312 fn indexable(&self) -> usize {
2313 self.iter.indexable()
2317 fn idx(&mut self, index: usize) -> Option<I::Item> {
2318 let element = self.iter.idx(index);
2319 self.do_inspect(element)
2323 /// An iterator that passes mutable state to a closure and yields the result.
2327 /// An iterator that yields sequential Fibonacci numbers, and stops on overflow.
2330 /// #![feature(core)]
2331 /// use std::iter::Unfold;
2333 /// // This iterator will yield up to the last Fibonacci number before the max
2334 /// // value of `u32`. You can simply change `u32` to `u64` in this line if
2335 /// // you want higher values than that.
2336 /// let mut fibonacci = Unfold::new((Some(0u32), Some(1u32)),
2337 /// |&mut (ref mut x2, ref mut x1)| {
2338 /// // Attempt to get the next Fibonacci number
2339 /// // `x1` will be `None` if previously overflowed.
2340 /// let next = match (*x2, *x1) {
2341 /// (Some(x2), Some(x1)) => x2.checked_add(x1),
2345 /// // Shift left: ret <- x2 <- x1 <- next
2353 /// for i in fibonacci {
2354 /// println!("{}", i);
2357 #[unstable(feature = "core")]
2359 pub struct Unfold<St, F> {
2361 /// Internal state that will be passed to the closure on the next iteration
2362 #[unstable(feature = "core")]
2366 #[unstable(feature = "core")]
2367 impl<A, St, F> Unfold<St, F> where F: FnMut(&mut St) -> Option<A> {
2368 /// Creates a new iterator with the specified closure as the "iterator
2369 /// function" and an initial state to eventually pass to the closure
2371 pub fn new(initial_state: St, f: F) -> Unfold<St, F> {
2374 state: initial_state
2379 #[stable(feature = "rust1", since = "1.0.0")]
2380 impl<A, St, F> Iterator for Unfold<St, F> where F: FnMut(&mut St) -> Option<A> {
2384 fn next(&mut self) -> Option<A> {
2385 (self.f)(&mut self.state)
2389 fn size_hint(&self) -> (usize, Option<usize>) {
2390 // no possible known bounds at this point
2395 /// Objects that can be stepped over in both directions.
2397 /// The `steps_between` function provides a way to efficiently compare
2398 /// two `Step` objects.
2399 #[unstable(feature = "step_trait",
2400 reason = "likely to be replaced by finer-grained traits")]
2401 pub trait Step: PartialOrd {
2402 /// Steps `self` if possible.
2403 fn step(&self, by: &Self) -> Option<Self>;
2405 /// Returns the number of steps between two step objects.
2407 /// `start` should always be less than `end`, so the result should never
2410 /// `by` must be > 0.
2412 /// Returns `None` if it is not possible to calculate steps_between
2413 /// without overflow.
2414 fn steps_between(start: &Self, end: &Self, by: &Self) -> Option<usize>;
2417 macro_rules! step_impl_unsigned {
2421 fn step(&self, by: &$t) -> Option<$t> {
2422 (*self).checked_add(*by)
2425 #[allow(trivial_numeric_casts)]
2426 fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
2428 // Note: We assume $t <= usize here
2429 Some((*end - *start) as usize / (*by as usize))
2437 macro_rules! step_impl_signed {
2441 fn step(&self, by: &$t) -> Option<$t> {
2442 (*self).checked_add(*by)
2445 #[allow(trivial_numeric_casts)]
2446 fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
2448 // Note: We assume $t <= isize here
2449 // Use .wrapping_sub and cast to usize to compute the
2450 // difference that may not fit inside the range of isize.
2452 ((*end as isize).wrapping_sub(*start as isize) as usize
2463 macro_rules! step_impl_no_between {
2467 fn step(&self, by: &$t) -> Option<$t> {
2468 (*self).checked_add(*by)
2471 fn steps_between(_a: &$t, _b: &$t, _by: &$t) -> Option<usize> {
2478 step_impl_unsigned!(usize u8 u16 u32);
2479 step_impl_signed!(isize i8 i16 i32);
2480 #[cfg(target_pointer_width = "64")]
2481 step_impl_unsigned!(u64);
2482 #[cfg(target_pointer_width = "64")]
2483 step_impl_signed!(i64);
2484 #[cfg(target_pointer_width = "32")]
2485 step_impl_no_between!(u64 i64);
2487 /// An adapter for stepping range iterators by a custom amount.
2489 /// The resulting iterator handles overflow by stopping. The `A`
2490 /// parameter is the type being iterated over, while `R` is the range
2491 /// type (usually one of `std::ops::{Range, RangeFrom}`.
2493 #[unstable(feature = "step_by", reason = "recent addition")]
2494 pub struct StepBy<A, R> {
2499 impl<A: Step> RangeFrom<A> {
2500 /// Creates an iterator starting at the same point, but stepping by
2501 /// the given amount at each iteration.
2506 /// for i in (0u8..).step_by(2) {
2507 /// println!("{}", i);
2511 /// This prints all even `u8` values.
2512 #[unstable(feature = "step_by", reason = "recent addition")]
2513 pub fn step_by(self, by: A) -> StepBy<A, Self> {
2521 #[allow(deprecated)]
2522 impl<A: Step> ops::Range<A> {
2523 /// Creates an iterator with the same range, but stepping by the
2524 /// given amount at each iteration.
2526 /// The resulting iterator handles overflow by stopping.
2531 /// # #![feature(step_by, core)]
2532 /// for i in (0..10).step_by(2) {
2533 /// println!("{}", i);
2546 #[unstable(feature = "step_by", reason = "recent addition")]
2547 pub fn step_by(self, by: A) -> StepBy<A, Self> {
2555 #[stable(feature = "rust1", since = "1.0.0")]
2556 impl<A> Iterator for StepBy<A, RangeFrom<A>> where
2558 for<'a> &'a A: Add<&'a A, Output = A>
2563 fn next(&mut self) -> Option<A> {
2564 let mut n = &self.range.start + &self.step_by;
2565 mem::swap(&mut n, &mut self.range.start);
2570 fn size_hint(&self) -> (usize, Option<usize>) {
2571 (usize::MAX, None) // Too bad we can't specify an infinite lower bound
2575 /// An iterator over the range [start, stop]
2577 #[unstable(feature = "core",
2578 reason = "likely to be replaced by range notation and adapters")]
2579 pub struct RangeInclusive<A> {
2580 range: ops::Range<A>,
2584 /// Returns an iterator over the range [start, stop].
2586 #[unstable(feature = "core",
2587 reason = "likely to be replaced by range notation and adapters")]
2588 pub fn range_inclusive<A>(start: A, stop: A) -> RangeInclusive<A>
2589 where A: Step + One + Clone
2597 #[unstable(feature = "core",
2598 reason = "likely to be replaced by range notation and adapters")]
2599 impl<A> Iterator for RangeInclusive<A> where
2600 A: PartialEq + Step + One + Clone,
2601 for<'a> &'a A: Add<&'a A, Output = A>
2606 fn next(&mut self) -> Option<A> {
2607 self.range.next().or_else(|| {
2608 if !self.done && self.range.start == self.range.end {
2610 Some(self.range.end.clone())
2618 fn size_hint(&self) -> (usize, Option<usize>) {
2619 let (lo, hi) = self.range.size_hint();
2623 let lo = lo.saturating_add(1);
2624 let hi = hi.and_then(|x| x.checked_add(1));
2630 #[unstable(feature = "core",
2631 reason = "likely to be replaced by range notation and adapters")]
2632 impl<A> DoubleEndedIterator for RangeInclusive<A> where
2633 A: PartialEq + Step + One + Clone,
2634 for<'a> &'a A: Add<&'a A, Output = A>,
2635 for<'a> &'a A: Sub<Output=A>
2638 fn next_back(&mut self) -> Option<A> {
2639 if self.range.end > self.range.start {
2640 let result = self.range.end.clone();
2641 self.range.end = &self.range.end - &A::one();
2643 } else if !self.done && self.range.start == self.range.end {
2645 Some(self.range.end.clone())
2652 #[stable(feature = "rust1", since = "1.0.0")]
2653 #[allow(deprecated)]
2654 impl<A: Step + Zero + Clone> Iterator for StepBy<A, ops::Range<A>> {
2658 fn next(&mut self) -> Option<A> {
2659 let rev = self.step_by < A::zero();
2660 if (rev && self.range.start > self.range.end) ||
2661 (!rev && self.range.start < self.range.end)
2663 match self.range.start.step(&self.step_by) {
2665 mem::swap(&mut self.range.start, &mut n);
2669 let mut n = self.range.end.clone();
2670 mem::swap(&mut self.range.start, &mut n);
2680 macro_rules! range_exact_iter_impl {
2682 #[stable(feature = "rust1", since = "1.0.0")]
2683 impl ExactSizeIterator for ops::Range<$t> { }
2687 #[stable(feature = "rust1", since = "1.0.0")]
2688 #[allow(deprecated)]
2689 impl<A: Step + One> Iterator for ops::Range<A> where
2690 for<'a> &'a A: Add<&'a A, Output = A>
2695 fn next(&mut self) -> Option<A> {
2696 if self.start < self.end {
2697 let mut n = &self.start + &A::one();
2698 mem::swap(&mut n, &mut self.start);
2706 fn size_hint(&self) -> (usize, Option<usize>) {
2707 match Step::steps_between(&self.start, &self.end, &A::one()) {
2708 Some(hint) => (hint, Some(hint)),
2714 // Ranges of u64 and i64 are excluded because they cannot guarantee having
2715 // a length <= usize::MAX, which is required by ExactSizeIterator.
2716 range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);
2718 #[stable(feature = "rust1", since = "1.0.0")]
2719 #[allow(deprecated)]
2720 impl<A: Step + One + Clone> DoubleEndedIterator for ops::Range<A> where
2721 for<'a> &'a A: Add<&'a A, Output = A>,
2722 for<'a> &'a A: Sub<&'a A, Output = A>
2725 fn next_back(&mut self) -> Option<A> {
2726 if self.start < self.end {
2727 self.end = &self.end - &A::one();
2728 Some(self.end.clone())
2735 #[stable(feature = "rust1", since = "1.0.0")]
2736 #[allow(deprecated)]
2737 impl<A: Step + One> Iterator for ops::RangeFrom<A> where
2738 for<'a> &'a A: Add<&'a A, Output = A>
2743 fn next(&mut self) -> Option<A> {
2744 let mut n = &self.start + &A::one();
2745 mem::swap(&mut n, &mut self.start);
2750 /// An iterator that repeats an element endlessly
2752 #[stable(feature = "rust1", since = "1.0.0")]
2753 pub struct Repeat<A> {
2757 #[stable(feature = "rust1", since = "1.0.0")]
2758 impl<A: Clone> Iterator for Repeat<A> {
2762 fn next(&mut self) -> Option<A> { self.idx(0) }
2764 fn size_hint(&self) -> (usize, Option<usize>) { (usize::MAX, None) }
2767 #[stable(feature = "rust1", since = "1.0.0")]
2768 impl<A: Clone> DoubleEndedIterator for Repeat<A> {
2770 fn next_back(&mut self) -> Option<A> { self.idx(0) }
2773 #[unstable(feature = "core", reason = "trait is experimental")]
2774 impl<A: Clone> RandomAccessIterator for Repeat<A> {
2776 fn indexable(&self) -> usize { usize::MAX }
2778 fn idx(&mut self, _: usize) -> Option<A> { Some(self.element.clone()) }
2781 type IterateState<T, F> = (F, Option<T>, bool);
2783 /// An iterator that repeatedly applies a given function, starting
2784 /// from a given seed value.
2785 #[unstable(feature = "core")]
2786 pub type Iterate<T, F> = Unfold<IterateState<T, F>, fn(&mut IterateState<T, F>) -> Option<T>>;
2788 /// Creates a new iterator that produces an infinite sequence of
2789 /// repeated applications of the given function `f`.
2790 #[unstable(feature = "core")]
2791 pub fn iterate<T, F>(seed: T, f: F) -> Iterate<T, F> where
2795 fn next<T, F>(st: &mut IterateState<T, F>) -> Option<T> where
2799 let &mut (ref mut f, ref mut val, ref mut first) = st;
2802 } else if let Some(x) = val.take() {
2803 *val = Some((*f)(x))
2808 // coerce to a fn pointer
2809 let next: fn(&mut IterateState<T,F>) -> Option<T> = next;
2811 Unfold::new((f, Some(seed), true), next)
2814 /// Creates a new iterator that endlessly repeats the element `elt`.
2816 #[stable(feature = "rust1", since = "1.0.0")]
2817 pub fn repeat<T: Clone>(elt: T) -> Repeat<T> {
2818 Repeat{element: elt}
2821 /// Functions for lexicographical ordering of sequences.
2823 /// Lexicographical ordering through `<`, `<=`, `>=`, `>` requires
2824 /// that the elements implement both `PartialEq` and `PartialOrd`.
2826 /// If two sequences are equal up until the point where one ends,
2827 /// the shorter sequence compares less.
2828 #[unstable(feature = "core", reason = "needs review and revision")]
2831 use cmp::{Eq, Ord, PartialOrd, PartialEq};
2832 use cmp::Ordering::{Equal, Less, Greater};
2834 use option::Option::{Some, None};
2835 use super::Iterator;
2837 /// Compare `a` and `b` for equality using `Eq`
2838 pub fn equals<A, L, R>(mut a: L, mut b: R) -> bool where
2840 L: Iterator<Item=A>,
2841 R: Iterator<Item=A>,
2844 match (a.next(), b.next()) {
2845 (None, None) => return true,
2846 (None, _) | (_, None) => return false,
2847 (Some(x), Some(y)) => if x != y { return false },
2852 /// Order `a` and `b` lexicographically using `Ord`
2853 pub fn cmp<A, L, R>(mut a: L, mut b: R) -> cmp::Ordering where
2855 L: Iterator<Item=A>,
2856 R: Iterator<Item=A>,
2859 match (a.next(), b.next()) {
2860 (None, None) => return Equal,
2861 (None, _ ) => return Less,
2862 (_ , None) => return Greater,
2863 (Some(x), Some(y)) => match x.cmp(&y) {
2865 non_eq => return non_eq,
2871 /// Order `a` and `b` lexicographically using `PartialOrd`
2872 pub fn partial_cmp<L: Iterator, R: Iterator>(mut a: L, mut b: R) -> Option<cmp::Ordering> where
2873 L::Item: PartialOrd<R::Item>
2876 match (a.next(), b.next()) {
2877 (None, None) => return Some(Equal),
2878 (None, _ ) => return Some(Less),
2879 (_ , None) => return Some(Greater),
2880 (Some(x), Some(y)) => match x.partial_cmp(&y) {
2882 non_eq => return non_eq,
2888 /// Compare `a` and `b` for equality (Using partial equality, `PartialEq`)
2889 pub fn eq<L: Iterator, R: Iterator>(mut a: L, mut b: R) -> bool where
2890 L::Item: PartialEq<R::Item>,
2893 match (a.next(), b.next()) {
2894 (None, None) => return true,
2895 (None, _) | (_, None) => return false,
2896 (Some(x), Some(y)) => if !x.eq(&y) { return false },
2901 /// Compares `a` and `b` for nonequality (Using partial equality, `PartialEq`)
2902 pub fn ne<L: Iterator, R: Iterator>(mut a: L, mut b: R) -> bool where
2903 L::Item: PartialEq<R::Item>,
2906 match (a.next(), b.next()) {
2907 (None, None) => return false,
2908 (None, _) | (_, None) => return true,
2909 (Some(x), Some(y)) => if x.ne(&y) { return true },
2914 /// Returns `a` < `b` lexicographically (Using partial order, `PartialOrd`)
2915 pub fn lt<R: Iterator, L: Iterator>(mut a: L, mut b: R) -> bool where
2916 L::Item: PartialOrd<R::Item>,
2919 match (a.next(), b.next()) {
2920 (None, None) => return false,
2921 (None, _ ) => return true,
2922 (_ , None) => return false,
2923 (Some(x), Some(y)) => if x.ne(&y) { return x.lt(&y) },
2928 /// Returns `a` <= `b` lexicographically (Using partial order, `PartialOrd`)
2929 pub fn le<L: Iterator, R: Iterator>(mut a: L, mut b: R) -> bool where
2930 L::Item: PartialOrd<R::Item>,
2933 match (a.next(), b.next()) {
2934 (None, None) => return true,
2935 (None, _ ) => return true,
2936 (_ , None) => return false,
2937 (Some(x), Some(y)) => if x.ne(&y) { return x.le(&y) },
2942 /// Returns `a` > `b` lexicographically (Using partial order, `PartialOrd`)
2943 pub fn gt<L: Iterator, R: Iterator>(mut a: L, mut b: R) -> bool where
2944 L::Item: PartialOrd<R::Item>,
2947 match (a.next(), b.next()) {
2948 (None, None) => return false,
2949 (None, _ ) => return false,
2950 (_ , None) => return true,
2951 (Some(x), Some(y)) => if x.ne(&y) { return x.gt(&y) },
2956 /// Returns `a` >= `b` lexicographically (Using partial order, `PartialOrd`)
2957 pub fn ge<L: Iterator, R: Iterator>(mut a: L, mut b: R) -> bool where
2958 L::Item: PartialOrd<R::Item>,
2961 match (a.next(), b.next()) {
2962 (None, None) => return true,
2963 (None, _ ) => return false,
2964 (_ , None) => return true,
2965 (Some(x), Some(y)) => if x.ne(&y) { return x.ge(&y) },