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.
13 Composable external iterators
15 # The `Iterator` trait
17 This module defines Rust's core iteration trait. The `Iterator` trait has one
18 unimplemented method, `next`. All other methods are derived through default
19 methods to perform operations such as `zip`, `chain`, `enumerate`, and `fold`.
21 The goal of this module is to unify iteration across all containers in Rust.
22 An iterator can be considered as a state machine which is used to track which
23 element will be yielded next.
25 There are various extensions also defined in this module to assist with various
26 types of iteration, such as the `DoubleEndedIterator` for iterating in reverse,
27 the `FromIterator` trait for creating a container from an iterator, and much
32 The special syntax used by rust's `for` loop is based around the `Iterator`
33 trait defined in this module. For loops can be viewed as a syntactical expansion
34 into a `loop`, for example, the `for` loop in this example is essentially
35 translated to the `loop` below.
38 let values = ~[1, 2, 3];
40 // "Syntactical sugar" taking advantage of an iterator
41 for &x in values.iter() {
45 // Rough translation of the iteration without a `for` iterator.
46 let mut it = values.iter();
57 This `for` loop syntax can be applied to any iterator over any type.
59 ## Iteration protocol and more
61 More detailed information about iterators can be found in the [container
62 tutorial](http://static.rust-lang.org/doc/master/tutorial-container.html) with
63 the rest of the rust manuals.
68 use num::{Zero, One, Integer, CheckedAdd, CheckedSub, Saturating, ToPrimitive};
69 use option::{Option, Some, None};
70 use ops::{Add, Mul, Sub};
76 /// Conversion from an `Iterator`
77 pub trait FromIterator<A> {
78 /// Build a container with elements from an external iterator.
79 fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> Self;
82 /// A type growable from an `Iterator` implementation
83 pub trait Extendable<A>: FromIterator<A> {
84 /// Extend a container with the elements yielded by an iterator
85 fn extend<T: Iterator<A>>(&mut self, iterator: &mut T);
88 /// An interface for dealing with "external iterators". These types of iterators
89 /// can be resumed at any time as all state is stored internally as opposed to
90 /// being located on the call stack.
92 /// The Iterator protocol states that an iterator yields a (potentially-empty,
93 /// potentially-infinite) sequence of values, and returns `None` to signal that
94 /// it's finished. The Iterator protocol does not define behavior after `None`
95 /// is returned. A concrete Iterator implementation may choose to behave however
96 /// it wishes, either by returning `None` infinitely, or by doing something
98 pub trait Iterator<A> {
99 /// Advance the iterator and return the next value. Return `None` when the end is reached.
100 fn next(&mut self) -> Option<A>;
102 /// Return a lower bound and upper bound on the remaining length of the iterator.
104 /// The common use case for the estimate is pre-allocating space to store the results.
106 fn size_hint(&self) -> (uint, Option<uint>) { (0, None) }
108 /// Chain this iterator with another, returning a new iterator which will
109 /// finish iterating over the current iterator, and then it will iterate
110 /// over the other specified iterator.
117 /// let mut it = a.iter().chain(b.iter());
118 /// assert_eq!(it.next().unwrap(), &0);
119 /// assert_eq!(it.next().unwrap(), &1);
120 /// assert!(it.next().is_none());
123 fn chain<U: Iterator<A>>(self, other: U) -> Chain<Self, U> {
124 Chain{a: self, b: other, flag: false}
127 /// Creates an iterator which iterates over both this and the specified
128 /// iterators simultaneously, yielding the two elements as pairs. When
129 /// either iterator returns None, all further invocations of next() will
137 /// let mut it = a.iter().zip(b.iter());
138 /// assert_eq!(it.next().unwrap(), (&0, &1));
139 /// assert!(it.next().is_none());
142 fn zip<B, U: Iterator<B>>(self, other: U) -> Zip<Self, U> {
143 Zip{a: self, b: other}
146 /// Creates a new iterator which will apply the specified function to each
147 /// element returned by the first, yielding the mapped element instead.
153 /// let mut it = a.iter().map(|&x| 2 * x);
154 /// assert_eq!(it.next().unwrap(), 2);
155 /// assert_eq!(it.next().unwrap(), 4);
156 /// assert!(it.next().is_none());
159 fn map<'r, B>(self, f: 'r |A| -> B) -> Map<'r, A, B, Self> {
160 Map{iter: self, f: f}
163 /// Creates an iterator which applies the predicate to each element returned
164 /// by this iterator. Only elements which have the predicate evaluate to
165 /// `true` will be yielded.
171 /// let mut it = a.iter().filter(|&x| *x > 1);
172 /// assert_eq!(it.next().unwrap(), &2);
173 /// assert!(it.next().is_none());
176 fn filter<'r>(self, predicate: 'r |&A| -> bool) -> Filter<'r, A, Self> {
177 Filter{iter: self, predicate: predicate}
180 /// Creates an iterator which both filters and maps elements.
181 /// If the specified function returns None, the element is skipped.
182 /// Otherwise the option is unwrapped and the new value is yielded.
188 /// let mut it = a.iter().filter_map(|&x| if x > 1 {Some(2 * x)} else {None});
189 /// assert_eq!(it.next().unwrap(), 4);
190 /// assert!(it.next().is_none());
193 fn filter_map<'r, B>(self, f: 'r |A| -> Option<B>) -> FilterMap<'r, A, B, Self> {
194 FilterMap { iter: self, f: f }
197 /// Creates an iterator which yields a pair of the value returned by this
198 /// iterator plus the current index of iteration.
203 /// let a = [100, 200];
204 /// let mut it = a.iter().enumerate();
205 /// assert_eq!(it.next().unwrap(), (0, &100));
206 /// assert_eq!(it.next().unwrap(), (1, &200));
207 /// assert!(it.next().is_none());
210 fn enumerate(self) -> Enumerate<Self> {
211 Enumerate{iter: self, count: 0}
215 /// Creates an iterator that has a `.peek()` method
216 /// that returns an optional reference to the next element.
221 /// let xs = [100, 200, 300];
222 /// let mut it = xs.iter().map(|x| *x).peekable();
223 /// assert_eq!(it.peek().unwrap(), &100);
224 /// assert_eq!(it.next().unwrap(), 100);
225 /// assert_eq!(it.next().unwrap(), 200);
226 /// assert_eq!(it.peek().unwrap(), &300);
227 /// assert_eq!(it.peek().unwrap(), &300);
228 /// assert_eq!(it.next().unwrap(), 300);
229 /// assert!(it.peek().is_none());
230 /// assert!(it.next().is_none());
233 fn peekable(self) -> Peekable<A, Self> {
234 Peekable{iter: self, peeked: None}
237 /// Creates an iterator which invokes the predicate on elements until it
238 /// returns false. Once the predicate returns false, all further elements are
244 /// let a = [1, 2, 3, 2, 1];
245 /// let mut it = a.iter().skip_while(|&a| *a < 3);
246 /// assert_eq!(it.next().unwrap(), &3);
247 /// assert_eq!(it.next().unwrap(), &2);
248 /// assert_eq!(it.next().unwrap(), &1);
249 /// assert!(it.next().is_none());
252 fn skip_while<'r>(self, predicate: 'r |&A| -> bool) -> SkipWhile<'r, A, Self> {
253 SkipWhile{iter: self, flag: false, predicate: predicate}
256 /// Creates an iterator which yields elements so long as the predicate
257 /// returns true. After the predicate returns false for the first time, no
258 /// further elements will be yielded.
263 /// let a = [1, 2, 3, 2, 1];
264 /// let mut it = a.iter().take_while(|&a| *a < 3);
265 /// assert_eq!(it.next().unwrap(), &1);
266 /// assert_eq!(it.next().unwrap(), &2);
267 /// assert!(it.next().is_none());
270 fn take_while<'r>(self, predicate: 'r |&A| -> bool) -> TakeWhile<'r, A, Self> {
271 TakeWhile{iter: self, flag: false, predicate: predicate}
274 /// Creates an iterator which skips the first `n` elements of this iterator,
275 /// and then it yields all further items.
280 /// let a = [1, 2, 3, 4, 5];
281 /// let mut it = a.iter().skip(3);
282 /// assert_eq!(it.next().unwrap(), &4);
283 /// assert_eq!(it.next().unwrap(), &5);
284 /// assert!(it.next().is_none());
287 fn skip(self, n: uint) -> Skip<Self> {
288 Skip{iter: self, n: n}
291 /// Creates an iterator which yields the first `n` elements of this
292 /// iterator, and then it will always return None.
297 /// let a = [1, 2, 3, 4, 5];
298 /// let mut it = a.iter().take(3);
299 /// assert_eq!(it.next().unwrap(), &1);
300 /// assert_eq!(it.next().unwrap(), &2);
301 /// assert_eq!(it.next().unwrap(), &3);
302 /// assert!(it.next().is_none());
305 fn take(self, n: uint) -> Take<Self> {
306 Take{iter: self, n: n}
309 /// Creates a new iterator which behaves in a similar fashion to foldl.
310 /// There is a state which is passed between each iteration and can be
311 /// mutated as necessary. The yielded values from the closure are yielded
312 /// from the Scan instance when not None.
317 /// let a = [1, 2, 3, 4, 5];
318 /// let mut it = a.iter().scan(1, |fac, &x| {
322 /// assert_eq!(it.next().unwrap(), 1);
323 /// assert_eq!(it.next().unwrap(), 2);
324 /// assert_eq!(it.next().unwrap(), 6);
325 /// assert_eq!(it.next().unwrap(), 24);
326 /// assert_eq!(it.next().unwrap(), 120);
327 /// assert!(it.next().is_none());
330 fn scan<'r, St, B>(self, initial_state: St, f: 'r |&mut St, A| -> Option<B>)
331 -> Scan<'r, A, B, Self, St> {
332 Scan{iter: self, f: f, state: initial_state}
335 /// Creates an iterator that maps each element to an iterator,
336 /// and yields the elements of the produced iterators
341 /// use std::iter::count;
343 /// let xs = [2u, 3];
344 /// let ys = [0u, 1, 0, 1, 2];
345 /// let mut it = xs.iter().flat_map(|&x| count(0u, 1).take(x));
346 /// // Check that `it` has the same elements as `ys`
349 /// assert_eq!(x, ys[i]);
354 fn flat_map<'r, B, U: Iterator<B>>(self, f: 'r |A| -> U)
355 -> FlatMap<'r, A, Self, U> {
356 FlatMap{iter: self, f: f, frontiter: None, backiter: None }
359 /// Creates an iterator that yields `None` forever after the underlying
360 /// iterator yields `None`. Random-access iterator behavior is not
361 /// affected, only single and double-ended iterator behavior.
366 /// fn process<U: Iterator<int>>(it: U) -> int {
367 /// let mut it = it.fuse();
375 /// // did we exhaust the iterator?
376 /// if it.next().is_none() {
381 /// let x = ~[1,2,3,7,8,9];
382 /// assert_eq!(process(x.move_iter()), 1006);
385 fn fuse(self) -> Fuse<Self> {
386 Fuse{iter: self, done: false}
389 /// Creates an iterator that calls a function with a reference to each
390 /// element before yielding it. This is often useful for debugging an
391 /// iterator pipeline.
396 /// use std::iter::AdditiveIterator;
398 /// let xs = [1u, 4, 2, 3, 8, 9, 6];
399 /// let sum = xs.iter()
401 /// .inspect(|&x| debug!("filtering {}", x))
402 /// .filter(|&x| x % 2 == 0)
403 /// .inspect(|&x| debug!("{} made it through", x))
405 /// println!("{}", sum);
408 fn inspect<'r>(self, f: 'r |&A|) -> Inspect<'r, A, Self> {
409 Inspect{iter: self, f: f}
412 /// Creates a wrapper around a mutable reference to the iterator.
414 /// This is useful to allow applying iterator adaptors while still
415 /// retaining ownership of the original iterator value.
420 /// let mut xs = range(0, 10);
421 /// // sum the first five values
422 /// let partial_sum = xs.by_ref().take(5).fold(0, |a, b| a + b);
423 /// assert!(partial_sum == 10);
424 /// // xs.next() is now `5`
425 /// assert!(xs.next() == Some(5));
427 fn by_ref<'r>(&'r mut self) -> ByRef<'r, Self> {
431 /// Apply a function to each element, or stop iterating if the
432 /// function returns `false`.
437 /// range(0, 5).advance(|x| {print!("{} ", x); true});
440 fn advance(&mut self, f: |A| -> bool) -> bool {
444 if !f(x) { return false; }
446 None => { return true; }
451 /// Loops through the entire iterator, collecting all of the elements into
452 /// a container implementing `FromIterator`.
457 /// let a = [1, 2, 3, 4, 5];
458 /// let b: ~[int] = a.iter().map(|&x| x).collect();
462 fn collect<B: FromIterator<A>>(&mut self) -> B {
463 FromIterator::from_iterator(self)
466 /// Loops through the entire iterator, collecting all of the elements into
467 /// a unique vector. This is simply collect() specialized for vectors.
472 /// let a = [1, 2, 3, 4, 5];
473 /// let b: ~[int] = a.iter().map(|&x| x).to_owned_vec();
477 fn to_owned_vec(&mut self) -> ~[A] {
481 /// Loops through `n` iterations, returning the `n`th element of the
487 /// let a = [1, 2, 3, 4, 5];
488 /// let mut it = a.iter();
489 /// assert!(it.nth(2).unwrap() == &3);
490 /// assert!(it.nth(2) == None);
493 fn nth(&mut self, mut n: uint) -> Option<A> {
496 Some(x) => if n == 0 { return Some(x) },
503 /// Loops through the entire iterator, returning the last element of the
509 /// let a = [1, 2, 3, 4, 5];
510 /// assert!(a.iter().last().unwrap() == &5);
513 fn last(&mut self) -> Option<A> {
515 for x in *self { last = Some(x); }
519 /// Performs a fold operation over the entire iterator, returning the
520 /// eventual state at the end of the iteration.
525 /// let a = [1, 2, 3, 4, 5];
526 /// assert!(a.iter().fold(0, |a, &b| a + b) == 15);
529 fn fold<B>(&mut self, init: B, f: |B, A| -> B) -> B {
530 let mut accum = init;
533 Some(x) => { accum = f(accum, x); }
540 /// Counts the number of elements in this iterator.
545 /// let a = [1, 2, 3, 4, 5];
546 /// let mut it = a.iter();
547 /// assert!(it.len() == 5);
548 /// assert!(it.len() == 0);
551 fn len(&mut self) -> uint {
552 self.fold(0, |cnt, _x| cnt + 1)
555 /// Tests whether the predicate holds true for all elements in the iterator.
560 /// let a = [1, 2, 3, 4, 5];
561 /// assert!(a.iter().all(|x| *x > 0));
562 /// assert!(!a.iter().all(|x| *x > 2));
565 fn all(&mut self, f: |A| -> bool) -> bool {
566 for x in *self { if !f(x) { return false; } }
570 /// Tests whether any element of an iterator satisfies the specified
576 /// let a = [1, 2, 3, 4, 5];
577 /// let mut it = a.iter();
578 /// assert!(it.any(|x| *x == 3));
579 /// assert!(!it.any(|x| *x == 3));
582 fn any(&mut self, f: |A| -> bool) -> bool {
583 for x in *self { if f(x) { return true; } }
587 /// Return the first element satisfying the specified predicate
589 fn find(&mut self, predicate: |&A| -> bool) -> Option<A> {
591 if predicate(&x) { return Some(x) }
596 /// Return the index of the first element satisfying the specified predicate
598 fn position(&mut self, predicate: |A| -> bool) -> Option<uint> {
609 /// Count the number of elements satisfying the specified predicate
611 fn count(&mut self, predicate: |A| -> bool) -> uint {
614 if predicate(x) { i += 1 }
619 /// Return the element that gives the maximum value from the
620 /// specified function.
625 /// let xs = [-3i, 0, 1, 5, -10];
626 /// assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
629 fn max_by<B: Ord>(&mut self, f: |&A| -> B) -> Option<A> {
630 self.fold(None, |max: Option<(A, B)>, x| {
633 None => Some((x, x_val)),
634 Some((y, y_val)) => if x_val > y_val {
643 /// Return the element that gives the minimum value from the
644 /// specified function.
649 /// let xs = [-3i, 0, 1, 5, -10];
650 /// assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
653 fn min_by<B: Ord>(&mut self, f: |&A| -> B) -> Option<A> {
654 self.fold(None, |min: Option<(A, B)>, x| {
657 None => Some((x, x_val)),
658 Some((y, y_val)) => if x_val < y_val {
668 /// A range iterator able to yield elements from both ends
669 pub trait DoubleEndedIterator<A>: Iterator<A> {
670 /// Yield an element from the end of the range, returning `None` if the range is empty.
671 fn next_back(&mut self) -> Option<A>;
673 /// Change the direction of the iterator
675 /// The flipped iterator swaps the ends on an iterator that can already
676 /// be iterated from the front and from the back.
679 /// If the iterator also implements RandomAccessIterator, the flipped
680 /// iterator is also random access, with the indices starting at the back
681 /// of the original iterator.
683 /// Note: Random access with flipped indices still only applies to the first
684 /// `uint::MAX` elements of the original iterator.
686 fn rev(self) -> Rev<Self> {
691 /// A double-ended iterator yielding mutable references
692 pub trait MutableDoubleEndedIterator {
693 // FIXME: #5898: should be called `reverse`
694 /// Use an iterator to reverse a container in-place
695 fn reverse_(&mut self);
698 impl<'a, A, T: DoubleEndedIterator<&'a mut A>> MutableDoubleEndedIterator for T {
699 // FIXME: #5898: should be called `reverse`
700 /// Use an iterator to reverse a container in-place
701 fn reverse_(&mut self) {
703 match (self.next(), self.next_back()) {
704 (Some(x), Some(y)) => util::swap(x, y),
712 /// An object implementing random access indexing by `uint`
714 /// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`.
715 pub trait RandomAccessIterator<A>: Iterator<A> {
716 /// Return the number of indexable elements. At most `std::uint::MAX`
717 /// elements are indexable, even if the iterator represents a longer range.
718 fn indexable(&self) -> uint;
720 /// Return an element at an index
721 fn idx(&self, index: uint) -> Option<A>;
724 /// An iterator that knows its exact length
726 /// This trait is a helper for iterators like the vector iterator, so that
727 /// it can support double-ended enumeration.
729 /// `Iterator::size_hint` *must* return the exact size of the iterator.
730 /// Note that the size must fit in `uint`.
731 pub trait ExactSize<A> : DoubleEndedIterator<A> {
732 /// Return the index of the last element satisfying the specified predicate
734 /// If no element matches, None is returned.
736 fn rposition(&mut self, predicate: |A| -> bool) -> Option<uint> {
737 let (lower, upper) = self.size_hint();
738 assert!(upper == Some(lower));
741 match self.next_back() {
744 i = match i.checked_sub(&1) {
746 None => fail!("rposition: incorrect ExactSize")
758 // All adaptors that preserve the size of the wrapped iterator are fine
759 // Adaptors that may overflow in `size_hint` are not, i.e. `Chain`.
760 impl<A, T: ExactSize<A>> ExactSize<(uint, A)> for Enumerate<T> {}
761 impl<'a, A, T: ExactSize<A>> ExactSize<A> for Inspect<'a, A, T> {}
762 impl<A, T: ExactSize<A>> ExactSize<A> for Rev<T> {}
763 impl<'a, A, B, T: ExactSize<A>> ExactSize<B> for Map<'a, A, B, T> {}
764 impl<A, B, T: ExactSize<A>, U: ExactSize<B>> ExactSize<(A, B)> for Zip<T, U> {}
766 /// An double-ended iterator with the direction inverted
772 impl<A, T: DoubleEndedIterator<A>> Iterator<A> for Rev<T> {
774 fn next(&mut self) -> Option<A> { self.iter.next_back() }
776 fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
779 impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Rev<T> {
781 fn next_back(&mut self) -> Option<A> { self.iter.next() }
784 impl<A, T: DoubleEndedIterator<A> + RandomAccessIterator<A>> RandomAccessIterator<A>
787 fn indexable(&self) -> uint { self.iter.indexable() }
789 fn idx(&self, index: uint) -> Option<A> {
790 self.iter.idx(self.indexable() - index - 1)
794 /// A mutable reference to an iterator
795 pub struct ByRef<'a, T> {
799 impl<'a, A, T: Iterator<A>> Iterator<A> for ByRef<'a, T> {
801 fn next(&mut self) -> Option<A> { self.iter.next() }
803 fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
806 impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for ByRef<'a, T> {
808 fn next_back(&mut self) -> Option<A> { self.iter.next_back() }
811 /// A trait for iterators over elements which can be added together
812 pub trait AdditiveIterator<A> {
813 /// Iterates over the entire iterator, summing up all the elements
818 /// use std::iter::AdditiveIterator;
820 /// let a = [1, 2, 3, 4, 5];
821 /// let mut it = a.iter().map(|&x| x);
822 /// assert!(it.sum() == 15);
824 fn sum(&mut self) -> A;
827 impl<A: Add<A, A> + Zero, T: Iterator<A>> AdditiveIterator<A> for T {
829 fn sum(&mut self) -> A {
830 let zero: A = Zero::zero();
831 self.fold(zero, |s, x| s + x)
835 /// A trait for iterators over elements whose elements can be multiplied
837 pub trait MultiplicativeIterator<A> {
838 /// Iterates over the entire iterator, multiplying all the elements
843 /// use std::iter::{count, MultiplicativeIterator};
845 /// fn factorial(n: uint) -> uint {
846 /// count(1u, 1).take_while(|&i| i <= n).product()
848 /// assert!(factorial(0) == 1);
849 /// assert!(factorial(1) == 1);
850 /// assert!(factorial(5) == 120);
852 fn product(&mut self) -> A;
855 impl<A: Mul<A, A> + One, T: Iterator<A>> MultiplicativeIterator<A> for T {
857 fn product(&mut self) -> A {
858 let one: A = One::one();
859 self.fold(one, |p, x| p * x)
863 /// A trait for iterators over elements which can be compared to one another.
864 /// The type of each element must ascribe to the `Ord` trait.
865 pub trait OrdIterator<A> {
866 /// Consumes the entire iterator to return the maximum element.
871 /// let a = [1, 2, 3, 4, 5];
872 /// assert!(a.iter().max().unwrap() == &5);
874 fn max(&mut self) -> Option<A>;
876 /// Consumes the entire iterator to return the minimum element.
881 /// let a = [1, 2, 3, 4, 5];
882 /// assert!(a.iter().min().unwrap() == &1);
884 fn min(&mut self) -> Option<A>;
886 /// `min_max` finds the mininum and maximum elements in the iterator.
888 /// The return type `MinMaxResult` is an enum of three variants:
889 /// - `NoElements` if the iterator is empty.
890 /// - `OneElement(x)` if the iterator has exactly one element.
891 /// - `MinMax(x, y)` is returned otherwise, where `x <= y`. Two values are equal if and only if
892 /// there is more than one element in the iterator and all elements are equal.
894 /// On an iterator of length `n`, `min_max` does `1.5 * n` comparisons,
895 /// and so faster than calling `min` and `max separately which does `2 * n` comparisons.
900 /// use std::iter::{NoElements, OneElement, MinMax};
902 /// let v: [int, ..0] = [];
903 /// assert_eq!(v.iter().min_max(), NoElements);
906 /// assert!(v.iter().min_max() == OneElement(&1));
908 /// let v = [1i, 2, 3, 4, 5];
909 /// assert!(v.iter().min_max() == MinMax(&1, &5));
911 /// let v = [1i, 2, 3, 4, 5, 6];
912 /// assert!(v.iter().min_max() == MinMax(&1, &6));
914 /// let v = [1i, 1, 1, 1];
915 /// assert!(v.iter().min_max() == MinMax(&1, &1));
917 fn min_max(&mut self) -> MinMaxResult<A>;
920 impl<A: Ord, T: Iterator<A>> OrdIterator<A> for T {
922 fn max(&mut self) -> Option<A> {
923 self.fold(None, |max, x| {
926 Some(y) => Some(cmp::max(x, y))
932 fn min(&mut self) -> Option<A> {
933 self.fold(None, |min, x| {
936 Some(y) => Some(cmp::min(x, y))
941 fn min_max(&mut self) -> MinMaxResult<A> {
942 let (mut min, mut max) = match self.next() {
943 None => return NoElements,
946 None => return OneElement(x),
947 Some(y) => if x < y {(x, y)} else {(y,x)}
953 // `first` and `second` are the two next elements we want to look at.
954 // We first compare `first` and `second` (#1). The smaller one is then compared to
955 // current mininum (#2). The larger one is compared to current maximum (#3). This
956 // way we do 3 comparisons for 2 elements.
957 let first = match self.next() {
961 let second = match self.next() {
965 } else if first > max {
973 if first < min {min = first;}
974 if max < second {max = second;}
976 if second < min {min = second;}
977 if max < first {max = first;}
985 /// `MinMaxResult` is an enum returned by `min_max`. See `OrdIterator::min_max` for more detail.
986 #[deriving(Clone, Eq)]
987 pub enum MinMaxResult<T> {
991 /// Iterator with one element, so the minimum and maximum are the same
994 /// More than one element in the iterator, the first element is not larger than the second
998 impl<T: Clone> MinMaxResult<T> {
999 /// `into_option` creates an `Option` of type `(T,T)`. The returned `Option` has variant
1000 /// `None` if and only if the `MinMaxResult` has variant `NoElements`. Otherwise variant
1001 /// `Some(x,y)` is returned where `x <= y`. If `MinMaxResult` has variant `OneElement(x)`,
1002 /// performing this operation will make one clone of `x`.
1007 /// use std::iter::{NoElements, OneElement, MinMax, MinMaxResult};
1009 /// let r: MinMaxResult<int> = NoElements;
1010 /// assert_eq!(r.into_option(), None)
1012 /// let r = OneElement(1);
1013 /// assert_eq!(r.into_option(), Some((1,1)));
1015 /// let r = MinMax(1,2);
1016 /// assert_eq!(r.into_option(), Some((1,2)));
1018 pub fn into_option(self) -> Option<(T,T)> {
1021 OneElement(x) => Some((x.clone(), x)),
1022 MinMax(x, y) => Some((x, y))
1027 /// A trait for iterators that are cloneable.
1028 pub trait CloneableIterator {
1029 /// Repeats an iterator endlessly
1034 /// use std::iter::{CloneableIterator, count};
1036 /// let a = count(1,1).take(1);
1037 /// let mut cy = a.cycle();
1038 /// assert_eq!(cy.next(), Some(1));
1039 /// assert_eq!(cy.next(), Some(1));
1041 fn cycle(self) -> Cycle<Self>;
1044 impl<A, T: Clone + Iterator<A>> CloneableIterator for T {
1046 fn cycle(self) -> Cycle<T> {
1047 Cycle{orig: self.clone(), iter: self}
1051 /// An iterator that repeats endlessly
1053 pub struct Cycle<T> {
1058 impl<A, T: Clone + Iterator<A>> Iterator<A> for Cycle<T> {
1060 fn next(&mut self) -> Option<A> {
1061 match self.iter.next() {
1062 None => { self.iter = self.orig.clone(); self.iter.next() }
1068 fn size_hint(&self) -> (uint, Option<uint>) {
1069 // the cycle iterator is either empty or infinite
1070 match self.orig.size_hint() {
1071 sz @ (0, Some(0)) => sz,
1072 (0, _) => (0, None),
1073 _ => (uint::MAX, None)
1078 impl<A, T: Clone + RandomAccessIterator<A>> RandomAccessIterator<A> for Cycle<T> {
1080 fn indexable(&self) -> uint {
1081 if self.orig.indexable() > 0 {
1089 fn idx(&self, index: uint) -> Option<A> {
1090 let liter = self.iter.indexable();
1091 let lorig = self.orig.indexable();
1094 } else if index < liter {
1095 self.iter.idx(index)
1097 self.orig.idx((index - liter) % lorig)
1102 /// An iterator which strings two iterators together
1104 pub struct Chain<T, U> {
1110 impl<A, T: Iterator<A>, U: Iterator<A>> Iterator<A> for Chain<T, U> {
1112 fn next(&mut self) -> Option<A> {
1116 match self.a.next() {
1117 Some(x) => return Some(x),
1126 fn size_hint(&self) -> (uint, Option<uint>) {
1127 let (a_lower, a_upper) = self.a.size_hint();
1128 let (b_lower, b_upper) = self.b.size_hint();
1130 let lower = a_lower.saturating_add(b_lower);
1132 let upper = match (a_upper, b_upper) {
1133 (Some(x), Some(y)) => x.checked_add(&y),
1141 impl<A, T: DoubleEndedIterator<A>, U: DoubleEndedIterator<A>> DoubleEndedIterator<A>
1144 fn next_back(&mut self) -> Option<A> {
1145 match self.b.next_back() {
1147 None => self.a.next_back()
1152 impl<A, T: RandomAccessIterator<A>, U: RandomAccessIterator<A>> RandomAccessIterator<A>
1155 fn indexable(&self) -> uint {
1156 let (a, b) = (self.a.indexable(), self.b.indexable());
1161 fn idx(&self, index: uint) -> Option<A> {
1162 let len = self.a.indexable();
1166 self.b.idx(index - len)
1171 /// An iterator which iterates two other iterators simultaneously
1173 pub struct Zip<T, U> {
1178 impl<A, B, T: Iterator<A>, U: Iterator<B>> Iterator<(A, B)> for Zip<T, U> {
1180 fn next(&mut self) -> Option<(A, B)> {
1181 match self.a.next() {
1183 Some(x) => match self.b.next() {
1185 Some(y) => Some((x, y))
1191 fn size_hint(&self) -> (uint, Option<uint>) {
1192 let (a_lower, a_upper) = self.a.size_hint();
1193 let (b_lower, b_upper) = self.b.size_hint();
1195 let lower = cmp::min(a_lower, b_lower);
1197 let upper = match (a_upper, b_upper) {
1198 (Some(x), Some(y)) => Some(cmp::min(x,y)),
1199 (Some(x), None) => Some(x),
1200 (None, Some(y)) => Some(y),
1201 (None, None) => None
1208 impl<A, B, T: ExactSize<A>, U: ExactSize<B>> DoubleEndedIterator<(A, B)>
1211 fn next_back(&mut self) -> Option<(A, B)> {
1212 let (a_sz, a_upper) = self.a.size_hint();
1213 let (b_sz, b_upper) = self.b.size_hint();
1214 assert!(a_upper == Some(a_sz));
1215 assert!(b_upper == Some(b_sz));
1217 for _ in range(0, b_sz - a_sz) { self.b.next_back(); }
1218 } else if a_sz > b_sz {
1219 for _ in range(0, a_sz - b_sz) { self.a.next_back(); }
1221 let (a_sz, _) = self.a.size_hint();
1222 let (b_sz, _) = self.b.size_hint();
1223 assert!(a_sz == b_sz);
1224 match (self.a.next_back(), self.b.next_back()) {
1225 (Some(x), Some(y)) => Some((x, y)),
1231 impl<A, B, T: RandomAccessIterator<A>, U: RandomAccessIterator<B>>
1232 RandomAccessIterator<(A, B)> for Zip<T, U> {
1234 fn indexable(&self) -> uint {
1235 cmp::min(self.a.indexable(), self.b.indexable())
1239 fn idx(&self, index: uint) -> Option<(A, B)> {
1240 match self.a.idx(index) {
1242 Some(x) => match self.b.idx(index) {
1244 Some(y) => Some((x, y))
1250 /// An iterator which maps the values of `iter` with `f`
1251 pub struct Map<'a, A, B, T> {
1256 impl<'a, A, B, T> Map<'a, A, B, T> {
1258 fn do_map(&self, elt: Option<A>) -> Option<B> {
1260 Some(a) => Some((self.f)(a)),
1266 impl<'a, A, B, T: Iterator<A>> Iterator<B> for Map<'a, A, B, T> {
1268 fn next(&mut self) -> Option<B> {
1269 let next = self.iter.next();
1274 fn size_hint(&self) -> (uint, Option<uint>) {
1275 self.iter.size_hint()
1279 impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B> for Map<'a, A, B, T> {
1281 fn next_back(&mut self) -> Option<B> {
1282 let next = self.iter.next_back();
1287 impl<'a, A, B, T: RandomAccessIterator<A>> RandomAccessIterator<B> for Map<'a, A, B, T> {
1289 fn indexable(&self) -> uint {
1290 self.iter.indexable()
1294 fn idx(&self, index: uint) -> Option<B> {
1295 self.do_map(self.iter.idx(index))
1299 /// An iterator which filters the elements of `iter` with `predicate`
1300 pub struct Filter<'a, A, T> {
1302 priv predicate: 'a |&A| -> bool
1305 impl<'a, A, T: Iterator<A>> Iterator<A> for Filter<'a, A, T> {
1307 fn next(&mut self) -> Option<A> {
1308 for x in self.iter {
1309 if (self.predicate)(&x) {
1319 fn size_hint(&self) -> (uint, Option<uint>) {
1320 let (_, upper) = self.iter.size_hint();
1321 (0, upper) // can't know a lower bound, due to the predicate
1325 impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Filter<'a, A, T> {
1327 fn next_back(&mut self) -> Option<A> {
1329 match self.iter.next_back() {
1330 None => return None,
1332 if (self.predicate)(&x) {
1343 /// An iterator which uses `f` to both filter and map elements from `iter`
1344 pub struct FilterMap<'a, A, B, T> {
1346 priv f: 'a |A| -> Option<B>
1349 impl<'a, A, B, T: Iterator<A>> Iterator<B> for FilterMap<'a, A, B, T> {
1351 fn next(&mut self) -> Option<B> {
1352 for x in self.iter {
1354 Some(y) => return Some(y),
1362 fn size_hint(&self) -> (uint, Option<uint>) {
1363 let (_, upper) = self.iter.size_hint();
1364 (0, upper) // can't know a lower bound, due to the predicate
1368 impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B>
1369 for FilterMap<'a, A, B, T> {
1371 fn next_back(&mut self) -> Option<B> {
1373 match self.iter.next_back() {
1374 None => return None,
1377 Some(y) => return Some(y),
1386 /// An iterator which yields the current count and the element during iteration
1388 pub struct Enumerate<T> {
1393 impl<A, T: Iterator<A>> Iterator<(uint, A)> for Enumerate<T> {
1395 fn next(&mut self) -> Option<(uint, A)> {
1396 match self.iter.next() {
1398 let ret = Some((self.count, a));
1407 fn size_hint(&self) -> (uint, Option<uint>) {
1408 self.iter.size_hint()
1412 impl<A, T: ExactSize<A>> DoubleEndedIterator<(uint, A)> for Enumerate<T> {
1414 fn next_back(&mut self) -> Option<(uint, A)> {
1415 match self.iter.next_back() {
1417 let (lower, upper) = self.iter.size_hint();
1418 assert!(upper == Some(lower));
1419 Some((self.count + lower, a))
1426 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<(uint, A)> for Enumerate<T> {
1428 fn indexable(&self) -> uint {
1429 self.iter.indexable()
1433 fn idx(&self, index: uint) -> Option<(uint, A)> {
1434 match self.iter.idx(index) {
1435 Some(a) => Some((self.count + index, a)),
1441 /// An iterator with a `peek()` that returns an optional reference to the next element.
1442 pub struct Peekable<A, T> {
1444 priv peeked: Option<A>,
1447 impl<A, T: Iterator<A>> Iterator<A> for Peekable<A, T> {
1449 fn next(&mut self) -> Option<A> {
1450 if self.peeked.is_some() { self.peeked.take() }
1451 else { self.iter.next() }
1455 fn size_hint(&self) -> (uint, Option<uint>) {
1456 let (lo, hi) = self.iter.size_hint();
1457 if self.peeked.is_some() {
1458 let lo = lo.saturating_add(1);
1460 Some(x) => x.checked_add(&1),
1470 impl<'a, A, T: Iterator<A>> Peekable<A, T> {
1471 /// Return a reference to the next element of the iterator with out advancing it,
1472 /// or None if the iterator is exhausted.
1474 pub fn peek(&'a mut self) -> Option<&'a A> {
1475 if self.peeked.is_none() {
1476 self.peeked = self.iter.next();
1479 Some(ref value) => Some(value),
1484 /// Check whether peekable iterator is empty or not.
1486 pub fn is_empty(&mut self) -> bool {
1487 self.peek().is_none()
1491 /// An iterator which rejects elements while `predicate` is true
1492 pub struct SkipWhile<'a, A, T> {
1495 priv predicate: 'a |&A| -> bool
1498 impl<'a, A, T: Iterator<A>> Iterator<A> for SkipWhile<'a, A, T> {
1500 fn next(&mut self) -> Option<A> {
1501 let mut next = self.iter.next();
1508 if (self.predicate)(&x) {
1509 next = self.iter.next();
1523 fn size_hint(&self) -> (uint, Option<uint>) {
1524 let (_, upper) = self.iter.size_hint();
1525 (0, upper) // can't know a lower bound, due to the predicate
1529 /// An iterator which only accepts elements while `predicate` is true
1530 pub struct TakeWhile<'a, A, T> {
1533 priv predicate: 'a |&A| -> bool
1536 impl<'a, A, T: Iterator<A>> Iterator<A> for TakeWhile<'a, A, T> {
1538 fn next(&mut self) -> Option<A> {
1542 match self.iter.next() {
1544 if (self.predicate)(&x) {
1557 fn size_hint(&self) -> (uint, Option<uint>) {
1558 let (_, upper) = self.iter.size_hint();
1559 (0, upper) // can't know a lower bound, due to the predicate
1563 /// An iterator which skips over `n` elements of `iter`.
1565 pub struct Skip<T> {
1570 impl<A, T: Iterator<A>> Iterator<A> for Skip<T> {
1572 fn next(&mut self) -> Option<A> {
1573 let mut next = self.iter.next();
1582 next = self.iter.next();
1597 fn size_hint(&self) -> (uint, Option<uint>) {
1598 let (lower, upper) = self.iter.size_hint();
1600 let lower = lower.saturating_sub(self.n);
1602 let upper = match upper {
1603 Some(x) => Some(x.saturating_sub(self.n)),
1611 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Skip<T> {
1613 fn indexable(&self) -> uint {
1614 self.iter.indexable().saturating_sub(self.n)
1618 fn idx(&self, index: uint) -> Option<A> {
1619 if index >= self.indexable() {
1622 self.iter.idx(index + self.n)
1627 /// An iterator which only iterates over the first `n` iterations of `iter`.
1629 pub struct Take<T> {
1634 impl<A, T: Iterator<A>> Iterator<A> for Take<T> {
1636 fn next(&mut self) -> Option<A> {
1646 fn size_hint(&self) -> (uint, Option<uint>) {
1647 let (lower, upper) = self.iter.size_hint();
1649 let lower = cmp::min(lower, self.n);
1651 let upper = match upper {
1652 Some(x) if x < self.n => Some(x),
1660 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Take<T> {
1662 fn indexable(&self) -> uint {
1663 cmp::min(self.iter.indexable(), self.n)
1667 fn idx(&self, index: uint) -> Option<A> {
1668 if index >= self.n {
1671 self.iter.idx(index)
1677 /// An iterator to maintain state while iterating another iterator
1678 pub struct Scan<'a, A, B, T, St> {
1680 priv f: 'a |&mut St, A| -> Option<B>,
1682 /// The current internal state to be passed to the closure next.
1686 impl<'a, A, B, T: Iterator<A>, St> Iterator<B> for Scan<'a, A, B, T, St> {
1688 fn next(&mut self) -> Option<B> {
1689 self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
1693 fn size_hint(&self) -> (uint, Option<uint>) {
1694 let (_, upper) = self.iter.size_hint();
1695 (0, upper) // can't know a lower bound, due to the scan function
1699 /// An iterator that maps each element to an iterator,
1700 /// and yields the elements of the produced iterators
1702 pub struct FlatMap<'a, A, T, U> {
1704 priv f: 'a |A| -> U,
1705 priv frontiter: Option<U>,
1706 priv backiter: Option<U>,
1709 impl<'a, A, T: Iterator<A>, B, U: Iterator<B>> Iterator<B> for FlatMap<'a, A, T, U> {
1711 fn next(&mut self) -> Option<B> {
1713 for inner in self.frontiter.mut_iter() {
1718 match self.iter.next().map(|x| (self.f)(x)) {
1719 None => return self.backiter.as_mut().and_then(|it| it.next()),
1720 next => self.frontiter = next,
1726 fn size_hint(&self) -> (uint, Option<uint>) {
1727 let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
1728 let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
1729 let lo = flo.saturating_add(blo);
1730 match (self.iter.size_hint(), fhi, bhi) {
1731 ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(&b)),
1738 A, T: DoubleEndedIterator<A>,
1739 B, U: DoubleEndedIterator<B>> DoubleEndedIterator<B>
1740 for FlatMap<'a, A, T, U> {
1742 fn next_back(&mut self) -> Option<B> {
1744 for inner in self.backiter.mut_iter() {
1745 match inner.next_back() {
1750 match self.iter.next_back().map(|x| (self.f)(x)) {
1751 None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
1752 next => self.backiter = next,
1758 /// An iterator that yields `None` forever after the underlying iterator
1759 /// yields `None` once.
1760 #[deriving(Clone, DeepClone)]
1761 pub struct Fuse<T> {
1766 impl<A, T: Iterator<A>> Iterator<A> for Fuse<T> {
1768 fn next(&mut self) -> Option<A> {
1772 match self.iter.next() {
1783 fn size_hint(&self) -> (uint, Option<uint>) {
1787 self.iter.size_hint()
1792 impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Fuse<T> {
1794 fn next_back(&mut self) -> Option<A> {
1798 match self.iter.next_back() {
1809 // Allow RandomAccessIterators to be fused without affecting random-access behavior
1810 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Fuse<T> {
1812 fn indexable(&self) -> uint {
1813 self.iter.indexable()
1817 fn idx(&self, index: uint) -> Option<A> {
1818 self.iter.idx(index)
1823 /// Resets the fuse such that the next call to .next() or .next_back() will
1824 /// call the underlying iterator again even if it previously returned None.
1826 pub fn reset_fuse(&mut self) {
1831 /// An iterator that calls a function with a reference to each
1832 /// element before yielding it.
1833 pub struct Inspect<'a, A, T> {
1838 impl<'a, A, T> Inspect<'a, A, T> {
1840 fn do_inspect(&self, elt: Option<A>) -> Option<A> {
1842 Some(ref a) => (self.f)(a),
1850 impl<'a, A, T: Iterator<A>> Iterator<A> for Inspect<'a, A, T> {
1852 fn next(&mut self) -> Option<A> {
1853 let next = self.iter.next();
1854 self.do_inspect(next)
1858 fn size_hint(&self) -> (uint, Option<uint>) {
1859 self.iter.size_hint()
1863 impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A>
1864 for Inspect<'a, A, T> {
1866 fn next_back(&mut self) -> Option<A> {
1867 let next = self.iter.next_back();
1868 self.do_inspect(next)
1872 impl<'a, A, T: RandomAccessIterator<A>> RandomAccessIterator<A>
1873 for Inspect<'a, A, T> {
1875 fn indexable(&self) -> uint {
1876 self.iter.indexable()
1880 fn idx(&self, index: uint) -> Option<A> {
1881 self.do_inspect(self.iter.idx(index))
1885 /// An iterator which just modifies the contained state throughout iteration.
1886 pub struct Unfold<'a, A, St> {
1887 priv f: 'a |&mut St| -> Option<A>,
1888 /// Internal state that will be yielded on the next iteration
1892 impl<'a, A, St> Unfold<'a, A, St> {
1893 /// Creates a new iterator with the specified closure as the "iterator
1894 /// function" and an initial state to eventually pass to the iterator
1896 pub fn new<'a>(initial_state: St, f: 'a |&mut St| -> Option<A>)
1897 -> Unfold<'a, A, St> {
1900 state: initial_state
1905 impl<'a, A, St> Iterator<A> for Unfold<'a, A, St> {
1907 fn next(&mut self) -> Option<A> {
1908 (self.f)(&mut self.state)
1912 fn size_hint(&self) -> (uint, Option<uint>) {
1913 // no possible known bounds at this point
1918 /// An infinite iterator starting at `start` and advancing by `step` with each
1921 pub struct Counter<A> {
1922 /// The current state the counter is at (next value to be yielded)
1924 /// The amount that this iterator is stepping by
1928 /// Creates a new counter with the specified start/step
1930 pub fn count<A>(start: A, step: A) -> Counter<A> {
1931 Counter{state: start, step: step}
1934 impl<A: Add<A, A> + Clone> Iterator<A> for Counter<A> {
1936 fn next(&mut self) -> Option<A> {
1937 let result = self.state.clone();
1938 self.state = self.state + self.step;
1943 fn size_hint(&self) -> (uint, Option<uint>) {
1944 (uint::MAX, None) // Too bad we can't specify an infinite lower bound
1948 /// An iterator over the range [start, stop)
1949 #[deriving(Clone, DeepClone)]
1950 pub struct Range<A> {
1956 /// Return an iterator over the range [start, stop)
1958 pub fn range<A: Add<A, A> + Ord + Clone + One>(start: A, stop: A) -> Range<A> {
1959 Range{state: start, stop: stop, one: One::one()}
1962 // FIXME: #10414: Unfortunate type bound
1963 impl<A: Add<A, A> + Ord + Clone + ToPrimitive> Iterator<A> for Range<A> {
1965 fn next(&mut self) -> Option<A> {
1966 if self.state < self.stop {
1967 let result = self.state.clone();
1968 self.state = self.state + self.one;
1976 fn size_hint(&self) -> (uint, Option<uint>) {
1977 // This first checks if the elements are representable as i64. If they aren't, try u64 (to
1978 // handle cases like range(huge, huger)). We don't use uint/int because the difference of
1979 // the i64/u64 might lie within their range.
1980 let bound = match self.state.to_i64() {
1982 let sz = self.stop.to_i64().map(|b| b.checked_sub(&a));
1984 Some(Some(bound)) => bound.to_uint(),
1988 None => match self.state.to_u64() {
1990 let sz = self.stop.to_u64().map(|b| b.checked_sub(&a));
1992 Some(Some(bound)) => bound.to_uint(),
2001 Some(b) => (b, Some(b)),
2002 // Standard fallback for unbounded/unrepresentable bounds
2008 /// `Integer` is required to ensure the range will be the same regardless of
2009 /// the direction it is consumed.
2010 impl<A: Integer + Ord + Clone + ToPrimitive> DoubleEndedIterator<A> for Range<A> {
2012 fn next_back(&mut self) -> Option<A> {
2013 if self.stop > self.state {
2014 self.stop = self.stop - self.one;
2015 Some(self.stop.clone())
2022 /// An iterator over the range [start, stop]
2023 #[deriving(Clone, DeepClone)]
2024 pub struct RangeInclusive<A> {
2025 priv range: Range<A>,
2029 /// Return an iterator over the range [start, stop]
2031 pub fn range_inclusive<A: Add<A, A> + Ord + Clone + One + ToPrimitive>(start: A, stop: A)
2032 -> RangeInclusive<A> {
2033 RangeInclusive{range: range(start, stop), done: false}
2036 impl<A: Add<A, A> + Eq + Ord + Clone + ToPrimitive> Iterator<A> for RangeInclusive<A> {
2038 fn next(&mut self) -> Option<A> {
2039 match self.range.next() {
2042 if !self.done && self.range.state == self.range.stop {
2044 Some(self.range.stop.clone())
2053 fn size_hint(&self) -> (uint, Option<uint>) {
2054 let (lo, hi) = self.range.size_hint();
2058 let lo = lo.saturating_add(1);
2060 Some(x) => x.checked_add(&1),
2068 impl<A: Sub<A, A> + Integer + Ord + Clone + ToPrimitive> DoubleEndedIterator<A>
2069 for RangeInclusive<A> {
2071 fn next_back(&mut self) -> Option<A> {
2072 if self.range.stop > self.range.state {
2073 let result = self.range.stop.clone();
2074 self.range.stop = self.range.stop - self.range.one;
2076 } else if !self.done && self.range.state == self.range.stop {
2078 Some(self.range.stop.clone())
2085 /// An iterator over the range [start, stop) by `step`. It handles overflow by stopping.
2086 #[deriving(Clone, DeepClone)]
2087 pub struct RangeStep<A> {
2094 /// Return an iterator over the range [start, stop) by `step`. It handles overflow by stopping.
2096 pub fn range_step<A: CheckedAdd + Ord + Clone + Zero>(start: A, stop: A, step: A) -> RangeStep<A> {
2097 let rev = step < Zero::zero();
2098 RangeStep{state: start, stop: stop, step: step, rev: rev}
2101 impl<A: CheckedAdd + Ord + Clone> Iterator<A> for RangeStep<A> {
2103 fn next(&mut self) -> Option<A> {
2104 if (self.rev && self.state > self.stop) || (!self.rev && self.state < self.stop) {
2105 let result = self.state.clone();
2106 match self.state.checked_add(&self.step) {
2107 Some(x) => self.state = x,
2108 None => self.state = self.stop.clone()
2117 /// An iterator over the range [start, stop] by `step`. It handles overflow by stopping.
2118 #[deriving(Clone, DeepClone)]
2119 pub struct RangeStepInclusive<A> {
2127 /// Return an iterator over the range [start, stop] by `step`. It handles overflow by stopping.
2129 pub fn range_step_inclusive<A: CheckedAdd + Ord + Clone + Zero>(start: A, stop: A,
2130 step: A) -> RangeStepInclusive<A> {
2131 let rev = step < Zero::zero();
2132 RangeStepInclusive{state: start, stop: stop, step: step, rev: rev, done: false}
2135 impl<A: CheckedAdd + Ord + Clone + Eq> Iterator<A> for RangeStepInclusive<A> {
2137 fn next(&mut self) -> Option<A> {
2138 if !self.done && ((self.rev && self.state >= self.stop) ||
2139 (!self.rev && self.state <= self.stop)) {
2140 let result = self.state.clone();
2141 match self.state.checked_add(&self.step) {
2142 Some(x) => self.state = x,
2143 None => self.done = true
2152 /// An iterator that repeats an element endlessly
2153 #[deriving(Clone, DeepClone)]
2154 pub struct Repeat<A> {
2158 impl<A: Clone> Repeat<A> {
2159 /// Create a new `Repeat` that endlessly repeats the element `elt`.
2161 pub fn new(elt: A) -> Repeat<A> {
2162 Repeat{element: elt}
2166 impl<A: Clone> Iterator<A> for Repeat<A> {
2168 fn next(&mut self) -> Option<A> { self.idx(0) }
2170 fn size_hint(&self) -> (uint, Option<uint>) { (uint::MAX, None) }
2173 impl<A: Clone> DoubleEndedIterator<A> for Repeat<A> {
2175 fn next_back(&mut self) -> Option<A> { self.idx(0) }
2178 impl<A: Clone> RandomAccessIterator<A> for Repeat<A> {
2180 fn indexable(&self) -> uint { uint::MAX }
2182 fn idx(&self, _: uint) -> Option<A> { Some(self.element.clone()) }
2185 /// Functions for lexicographical ordering of sequences.
2187 /// Lexicographical ordering through `<`, `<=`, `>=`, `>` requires
2188 /// that the elements implement both `Eq` and `Ord`.
2190 /// If two sequences are equal up until the point where one ends,
2191 /// the shorter sequence compares less.
2194 use cmp::{TotalEq, TotalOrd, Ord, Eq};
2195 use option::{Some, None};
2196 use super::Iterator;
2198 /// Compare `a` and `b` for equality using `TotalOrd`
2199 pub fn equals<A: TotalEq, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2201 match (a.next(), b.next()) {
2202 (None, None) => return true,
2203 (None, _) | (_, None) => return false,
2204 (Some(x), Some(y)) => if !x.equals(&y) { return false },
2209 /// Order `a` and `b` lexicographically using `TotalOrd`
2210 pub fn cmp<A: TotalOrd, T: Iterator<A>>(mut a: T, mut b: T) -> cmp::Ordering {
2212 match (a.next(), b.next()) {
2213 (None, None) => return cmp::Equal,
2214 (None, _ ) => return cmp::Less,
2215 (_ , None) => return cmp::Greater,
2216 (Some(x), Some(y)) => match x.cmp(&y) {
2218 non_eq => return non_eq,
2224 /// Compare `a` and `b` for equality (Using partial equality, `Eq`)
2225 pub fn eq<A: Eq, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2227 match (a.next(), b.next()) {
2228 (None, None) => return true,
2229 (None, _) | (_, None) => return false,
2230 (Some(x), Some(y)) => if !x.eq(&y) { return false },
2235 /// Compare `a` and `b` for nonequality (Using partial equality, `Eq`)
2236 pub fn ne<A: Eq, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2238 match (a.next(), b.next()) {
2239 (None, None) => return false,
2240 (None, _) | (_, None) => return true,
2241 (Some(x), Some(y)) => if x.ne(&y) { return true },
2246 /// Return `a` < `b` lexicographically (Using partial order, `Ord`)
2247 pub fn lt<A: Eq + Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2249 match (a.next(), b.next()) {
2250 (None, None) => return false,
2251 (None, _ ) => return true,
2252 (_ , None) => return false,
2253 (Some(x), Some(y)) => if x.ne(&y) { return x.lt(&y) },
2258 /// Return `a` <= `b` lexicographically (Using partial order, `Ord`)
2259 pub fn le<A: Eq + Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2261 match (a.next(), b.next()) {
2262 (None, None) => return true,
2263 (None, _ ) => return true,
2264 (_ , None) => return false,
2265 (Some(x), Some(y)) => if x.ne(&y) { return x.le(&y) },
2270 /// Return `a` > `b` lexicographically (Using partial order, `Ord`)
2271 pub fn gt<A: Eq + Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2273 match (a.next(), b.next()) {
2274 (None, None) => return false,
2275 (None, _ ) => return false,
2276 (_ , None) => return true,
2277 (Some(x), Some(y)) => if x.ne(&y) { return x.gt(&y) },
2282 /// Return `a` >= `b` lexicographically (Using partial order, `Ord`)
2283 pub fn ge<A: Eq + Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2285 match (a.next(), b.next()) {
2286 (None, None) => return true,
2287 (None, _ ) => return false,
2288 (_ , None) => return true,
2289 (Some(x), Some(y)) => if x.ne(&y) { return x.ge(&y) },
2296 use vec::ImmutableVector;
2298 let empty: [int, ..0] = [];
2302 assert!(!lt(xs.iter(), ys.iter()));
2303 assert!(!le(xs.iter(), ys.iter()));
2304 assert!( gt(xs.iter(), ys.iter()));
2305 assert!( ge(xs.iter(), ys.iter()));
2307 assert!( lt(ys.iter(), xs.iter()));
2308 assert!( le(ys.iter(), xs.iter()));
2309 assert!(!gt(ys.iter(), xs.iter()));
2310 assert!(!ge(ys.iter(), xs.iter()));
2312 assert!( lt(empty.iter(), xs.iter()));
2313 assert!( le(empty.iter(), xs.iter()));
2314 assert!(!gt(empty.iter(), xs.iter()));
2315 assert!(!ge(empty.iter(), xs.iter()));
2317 // Sequence with NaN
2319 let v = [0.0/0.0, 3.0];
2321 assert!(!lt(u.iter(), v.iter()));
2322 assert!(!le(u.iter(), v.iter()));
2323 assert!(!gt(u.iter(), v.iter()));
2324 assert!(!ge(u.iter(), v.iter()));
2330 assert!(lt(a.iter(), b.iter()) == (a[0] < b[0]));
2331 assert!(le(a.iter(), b.iter()) == (a[0] <= b[0]));
2332 assert!(gt(a.iter(), b.iter()) == (a[0] > b[0]));
2333 assert!(ge(a.iter(), b.iter()) == (a[0] >= b[0]));
2335 assert!(lt(c.iter(), b.iter()) == (c[0] < b[0]));
2336 assert!(le(c.iter(), b.iter()) == (c[0] <= b[0]));
2337 assert!(gt(c.iter(), b.iter()) == (c[0] > b[0]));
2338 assert!(ge(c.iter(), b.iter()) == (c[0] >= b[0]));
2352 fn test_counter_from_iter() {
2353 let mut it = count(0, 5).take(10);
2354 let xs: ~[int] = FromIterator::from_iterator(&mut it);
2355 assert_eq!(xs, ~[0, 5, 10, 15, 20, 25, 30, 35, 40, 45]);
2359 fn test_iterator_chain() {
2360 let xs = [0u, 1, 2, 3, 4, 5];
2361 let ys = [30u, 40, 50, 60];
2362 let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
2363 let mut it = xs.iter().chain(ys.iter());
2366 assert_eq!(x, expected[i]);
2369 assert_eq!(i, expected.len());
2371 let ys = count(30u, 10).take(4);
2372 let mut it = xs.iter().map(|&x| x).chain(ys);
2375 assert_eq!(x, expected[i]);
2378 assert_eq!(i, expected.len());
2382 fn test_filter_map() {
2383 let mut it = count(0u, 1u).take(10)
2384 .filter_map(|x| if x.is_even() { Some(x*x) } else { None });
2385 assert_eq!(it.collect::<~[uint]>(), ~[0*0, 2*2, 4*4, 6*6, 8*8]);
2389 fn test_iterator_enumerate() {
2390 let xs = [0u, 1, 2, 3, 4, 5];
2391 let mut it = xs.iter().enumerate();
2398 fn test_iterator_peekable() {
2399 let xs = ~[0u, 1, 2, 3, 4, 5];
2400 let mut it = xs.iter().map(|&x|x).peekable();
2401 assert_eq!(it.peek().unwrap(), &0);
2402 assert_eq!(it.next().unwrap(), 0);
2403 assert_eq!(it.next().unwrap(), 1);
2404 assert_eq!(it.next().unwrap(), 2);
2405 assert_eq!(it.peek().unwrap(), &3);
2406 assert_eq!(it.peek().unwrap(), &3);
2407 assert_eq!(it.next().unwrap(), 3);
2408 assert_eq!(it.next().unwrap(), 4);
2409 assert_eq!(it.peek().unwrap(), &5);
2410 assert_eq!(it.next().unwrap(), 5);
2411 assert!(it.peek().is_none());
2412 assert!(it.next().is_none());
2416 fn test_iterator_take_while() {
2417 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
2418 let ys = [0u, 1, 2, 3, 5, 13];
2419 let mut it = xs.iter().take_while(|&x| *x < 15u);
2422 assert_eq!(x, ys[i]);
2425 assert_eq!(i, ys.len());
2429 fn test_iterator_skip_while() {
2430 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
2431 let ys = [15, 16, 17, 19];
2432 let mut it = xs.iter().skip_while(|&x| *x < 15u);
2435 assert_eq!(x, ys[i]);
2438 assert_eq!(i, ys.len());
2442 fn test_iterator_skip() {
2443 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
2444 let ys = [13, 15, 16, 17, 19, 20, 30];
2445 let mut it = xs.iter().skip(5);
2448 assert_eq!(x, ys[i]);
2451 assert_eq!(i, ys.len());
2455 fn test_iterator_take() {
2456 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
2457 let ys = [0u, 1, 2, 3, 5];
2458 let mut it = xs.iter().take(5);
2461 assert_eq!(x, ys[i]);
2464 assert_eq!(i, ys.len());
2468 fn test_iterator_scan() {
2469 // test the type inference
2470 fn add(old: &mut int, new: &uint) -> Option<f64> {
2471 *old += *new as int;
2474 let xs = [0u, 1, 2, 3, 4];
2475 let ys = [0f64, 1.0, 3.0, 6.0, 10.0];
2477 let mut it = xs.iter().scan(0, add);
2480 assert_eq!(x, ys[i]);
2483 assert_eq!(i, ys.len());
2487 fn test_iterator_flat_map() {
2488 let xs = [0u, 3, 6];
2489 let ys = [0u, 1, 2, 3, 4, 5, 6, 7, 8];
2490 let mut it = xs.iter().flat_map(|&x| count(x, 1).take(3));
2493 assert_eq!(x, ys[i]);
2496 assert_eq!(i, ys.len());
2501 let xs = [1u, 2, 3, 4];
2506 .inspect(|_| n += 1)
2507 .collect::<~[uint]>();
2509 assert_eq!(n, xs.len());
2510 assert_eq!(xs, ys.as_slice());
2515 fn count(st: &mut uint) -> Option<uint> {
2517 let ret = Some(*st);
2525 let mut it = Unfold::new(0, count);
2528 assert_eq!(counted, i);
2537 let it = count(0u, 1).take(cycle_len).cycle();
2538 assert_eq!(it.size_hint(), (uint::MAX, None));
2539 for (i, x) in it.take(100).enumerate() {
2540 assert_eq!(i % cycle_len, x);
2543 let mut it = count(0u, 1).take(0).cycle();
2544 assert_eq!(it.size_hint(), (0, Some(0)));
2545 assert_eq!(it.next(), None);
2549 fn test_iterator_nth() {
2550 let v = &[0, 1, 2, 3, 4];
2551 for i in range(0u, v.len()) {
2552 assert_eq!(v.iter().nth(i).unwrap(), &v[i]);
2557 fn test_iterator_last() {
2558 let v = &[0, 1, 2, 3, 4];
2559 assert_eq!(v.iter().last().unwrap(), &4);
2560 assert_eq!(v.slice(0, 1).iter().last().unwrap(), &0);
2564 fn test_iterator_len() {
2565 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2566 assert_eq!(v.slice(0, 4).iter().len(), 4);
2567 assert_eq!(v.slice(0, 10).iter().len(), 10);
2568 assert_eq!(v.slice(0, 0).iter().len(), 0);
2572 fn test_iterator_sum() {
2573 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2574 assert_eq!(v.slice(0, 4).iter().map(|&x| x).sum(), 6);
2575 assert_eq!(v.iter().map(|&x| x).sum(), 55);
2576 assert_eq!(v.slice(0, 0).iter().map(|&x| x).sum(), 0);
2580 fn test_iterator_product() {
2581 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2582 assert_eq!(v.slice(0, 4).iter().map(|&x| x).product(), 0);
2583 assert_eq!(v.slice(1, 5).iter().map(|&x| x).product(), 24);
2584 assert_eq!(v.slice(0, 0).iter().map(|&x| x).product(), 1);
2588 fn test_iterator_max() {
2589 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2590 assert_eq!(v.slice(0, 4).iter().map(|&x| x).max(), Some(3));
2591 assert_eq!(v.iter().map(|&x| x).max(), Some(10));
2592 assert_eq!(v.slice(0, 0).iter().map(|&x| x).max(), None);
2596 fn test_iterator_min() {
2597 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2598 assert_eq!(v.slice(0, 4).iter().map(|&x| x).min(), Some(0));
2599 assert_eq!(v.iter().map(|&x| x).min(), Some(0));
2600 assert_eq!(v.slice(0, 0).iter().map(|&x| x).min(), None);
2604 fn test_iterator_size_hint() {
2605 let c = count(0, 1);
2606 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
2607 let v2 = &[10, 11, 12];
2610 assert_eq!(c.size_hint(), (uint::MAX, None));
2611 assert_eq!(vi.size_hint(), (10, Some(10)));
2613 assert_eq!(c.take(5).size_hint(), (5, Some(5)));
2614 assert_eq!(c.skip(5).size_hint().second(), None);
2615 assert_eq!(c.take_while(|_| false).size_hint(), (0, None));
2616 assert_eq!(c.skip_while(|_| false).size_hint(), (0, None));
2617 assert_eq!(c.enumerate().size_hint(), (uint::MAX, None));
2618 assert_eq!(c.chain(vi.map(|&i| i)).size_hint(), (uint::MAX, None));
2619 assert_eq!(c.zip(vi).size_hint(), (10, Some(10)));
2620 assert_eq!(c.scan(0, |_,_| Some(0)).size_hint(), (0, None));
2621 assert_eq!(c.filter(|_| false).size_hint(), (0, None));
2622 assert_eq!(c.map(|_| 0).size_hint(), (uint::MAX, None));
2623 assert_eq!(c.filter_map(|_| Some(0)).size_hint(), (0, None));
2625 assert_eq!(vi.take(5).size_hint(), (5, Some(5)));
2626 assert_eq!(vi.take(12).size_hint(), (10, Some(10)));
2627 assert_eq!(vi.skip(3).size_hint(), (7, Some(7)));
2628 assert_eq!(vi.skip(12).size_hint(), (0, Some(0)));
2629 assert_eq!(vi.take_while(|_| false).size_hint(), (0, Some(10)));
2630 assert_eq!(vi.skip_while(|_| false).size_hint(), (0, Some(10)));
2631 assert_eq!(vi.enumerate().size_hint(), (10, Some(10)));
2632 assert_eq!(vi.chain(v2.iter()).size_hint(), (13, Some(13)));
2633 assert_eq!(vi.zip(v2.iter()).size_hint(), (3, Some(3)));
2634 assert_eq!(vi.scan(0, |_,_| Some(0)).size_hint(), (0, Some(10)));
2635 assert_eq!(vi.filter(|_| false).size_hint(), (0, Some(10)));
2636 assert_eq!(vi.map(|i| i+1).size_hint(), (10, Some(10)));
2637 assert_eq!(vi.filter_map(|_| Some(0)).size_hint(), (0, Some(10)));
2642 let a = ~[1, 2, 3, 4, 5];
2643 let b: ~[int] = a.iter().map(|&x| x).collect();
2649 let v: ~&[int] = ~&[1, 2, 3, 4, 5];
2650 assert!(v.iter().all(|&x| x < 10));
2651 assert!(!v.iter().all(|&x| x.is_even()));
2652 assert!(!v.iter().all(|&x| x > 100));
2653 assert!(v.slice(0, 0).iter().all(|_| fail!()));
2658 let v: ~&[int] = ~&[1, 2, 3, 4, 5];
2659 assert!(v.iter().any(|&x| x < 10));
2660 assert!(v.iter().any(|&x| x.is_even()));
2661 assert!(!v.iter().any(|&x| x > 100));
2662 assert!(!v.slice(0, 0).iter().any(|_| fail!()));
2667 let v: &[int] = &[1, 3, 9, 27, 103, 14, 11];
2668 assert_eq!(*v.iter().find(|x| *x & 1 == 0).unwrap(), 14);
2669 assert_eq!(*v.iter().find(|x| *x % 3 == 0).unwrap(), 3);
2670 assert!(v.iter().find(|x| *x % 12 == 0).is_none());
2674 fn test_position() {
2675 let v = &[1, 3, 9, 27, 103, 14, 11];
2676 assert_eq!(v.iter().position(|x| *x & 1 == 0).unwrap(), 5);
2677 assert_eq!(v.iter().position(|x| *x % 3 == 0).unwrap(), 1);
2678 assert!(v.iter().position(|x| *x % 12 == 0).is_none());
2683 let xs = &[1, 2, 2, 1, 5, 9, 0, 2];
2684 assert_eq!(xs.iter().count(|x| *x == 2), 3);
2685 assert_eq!(xs.iter().count(|x| *x == 5), 1);
2686 assert_eq!(xs.iter().count(|x| *x == 95), 0);
2691 let xs: &[int] = &[-3, 0, 1, 5, -10];
2692 assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
2697 let xs: &[int] = &[-3, 0, 1, 5, -10];
2698 assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
2703 let mut xs = range(0, 10);
2704 // sum the first five values
2705 let partial_sum = xs.by_ref().take(5).fold(0, |a, b| a + b);
2706 assert_eq!(partial_sum, 10);
2707 assert_eq!(xs.next(), Some(5));
2712 let xs = [2, 4, 6, 8, 10, 12, 14, 16];
2713 let mut it = xs.iter();
2716 assert_eq!(it.rev().map(|&x| x).collect::<~[int]>(), ~[16, 14, 12, 10, 8, 6]);
2720 fn test_double_ended_map() {
2721 let xs = [1, 2, 3, 4, 5, 6];
2722 let mut it = xs.iter().map(|&x| x * -1);
2723 assert_eq!(it.next(), Some(-1));
2724 assert_eq!(it.next(), Some(-2));
2725 assert_eq!(it.next_back(), Some(-6));
2726 assert_eq!(it.next_back(), Some(-5));
2727 assert_eq!(it.next(), Some(-3));
2728 assert_eq!(it.next_back(), Some(-4));
2729 assert_eq!(it.next(), None);
2733 fn test_double_ended_enumerate() {
2734 let xs = [1, 2, 3, 4, 5, 6];
2735 let mut it = xs.iter().map(|&x| x).enumerate();
2736 assert_eq!(it.next(), Some((0, 1)));
2737 assert_eq!(it.next(), Some((1, 2)));
2738 assert_eq!(it.next_back(), Some((5, 6)));
2739 assert_eq!(it.next_back(), Some((4, 5)));
2740 assert_eq!(it.next_back(), Some((3, 4)));
2741 assert_eq!(it.next_back(), Some((2, 3)));
2742 assert_eq!(it.next(), None);
2746 fn test_double_ended_zip() {
2747 let xs = [1, 2, 3, 4, 5, 6];
2748 let ys = [1, 2, 3, 7];
2749 let a = xs.iter().map(|&x| x);
2750 let b = ys.iter().map(|&x| x);
2751 let mut it = a.zip(b);
2752 assert_eq!(it.next(), Some((1, 1)));
2753 assert_eq!(it.next(), Some((2, 2)));
2754 assert_eq!(it.next_back(), Some((4, 7)));
2755 assert_eq!(it.next_back(), Some((3, 3)));
2756 assert_eq!(it.next(), None);
2760 fn test_double_ended_filter() {
2761 let xs = [1, 2, 3, 4, 5, 6];
2762 let mut it = xs.iter().filter(|&x| *x & 1 == 0);
2763 assert_eq!(it.next_back().unwrap(), &6);
2764 assert_eq!(it.next_back().unwrap(), &4);
2765 assert_eq!(it.next().unwrap(), &2);
2766 assert_eq!(it.next_back(), None);
2770 fn test_double_ended_filter_map() {
2771 let xs = [1, 2, 3, 4, 5, 6];
2772 let mut it = xs.iter().filter_map(|&x| if x & 1 == 0 { Some(x * 2) } else { None });
2773 assert_eq!(it.next_back().unwrap(), 12);
2774 assert_eq!(it.next_back().unwrap(), 8);
2775 assert_eq!(it.next().unwrap(), 4);
2776 assert_eq!(it.next_back(), None);
2780 fn test_double_ended_chain() {
2781 let xs = [1, 2, 3, 4, 5];
2782 let ys = ~[7, 9, 11];
2783 let mut it = xs.iter().chain(ys.iter()).rev();
2784 assert_eq!(it.next().unwrap(), &11)
2785 assert_eq!(it.next().unwrap(), &9)
2786 assert_eq!(it.next_back().unwrap(), &1)
2787 assert_eq!(it.next_back().unwrap(), &2)
2788 assert_eq!(it.next_back().unwrap(), &3)
2789 assert_eq!(it.next_back().unwrap(), &4)
2790 assert_eq!(it.next_back().unwrap(), &5)
2791 assert_eq!(it.next_back().unwrap(), &7)
2792 assert_eq!(it.next_back(), None)
2796 fn test_rposition() {
2797 fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' }
2798 fn g(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'd' }
2799 let v = ~[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
2801 assert_eq!(v.iter().rposition(f), Some(3u));
2802 assert!(v.iter().rposition(g).is_none());
2807 fn test_rposition_fail() {
2808 let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
2810 v.iter().rposition(|_elt| {
2821 fn check_randacc_iter<A: Eq, T: Clone + RandomAccessIterator<A>>(a: T, len: uint)
2823 let mut b = a.clone();
2824 assert_eq!(len, b.indexable());
2826 for (i, elt) in a.enumerate() {
2827 assert_eq!(Some(elt), b.idx(i));
2831 assert_eq!(None, b.idx(n));
2832 // call recursively to check after picking off an element
2835 check_randacc_iter(b, len-1);
2841 fn test_double_ended_flat_map() {
2844 let mut it = u.iter().flat_map(|x| v.slice(*x, v.len()).iter());
2845 assert_eq!(it.next_back().unwrap(), &8);
2846 assert_eq!(it.next().unwrap(), &5);
2847 assert_eq!(it.next_back().unwrap(), &7);
2848 assert_eq!(it.next_back().unwrap(), &6);
2849 assert_eq!(it.next_back().unwrap(), &8);
2850 assert_eq!(it.next().unwrap(), &6);
2851 assert_eq!(it.next_back().unwrap(), &7);
2852 assert_eq!(it.next_back(), None);
2853 assert_eq!(it.next(), None);
2854 assert_eq!(it.next_back(), None);
2858 fn test_random_access_chain() {
2859 let xs = [1, 2, 3, 4, 5];
2860 let ys = ~[7, 9, 11];
2861 let mut it = xs.iter().chain(ys.iter());
2862 assert_eq!(it.idx(0).unwrap(), &1);
2863 assert_eq!(it.idx(5).unwrap(), &7);
2864 assert_eq!(it.idx(7).unwrap(), &11);
2865 assert!(it.idx(8).is_none());
2871 assert_eq!(it.idx(0).unwrap(), &3);
2872 assert_eq!(it.idx(4).unwrap(), &9);
2873 assert!(it.idx(6).is_none());
2875 check_randacc_iter(it, xs.len() + ys.len() - 3);
2879 fn test_random_access_enumerate() {
2880 let xs = [1, 2, 3, 4, 5];
2881 check_randacc_iter(xs.iter().enumerate(), xs.len());
2885 fn test_random_access_rev() {
2886 let xs = [1, 2, 3, 4, 5];
2887 check_randacc_iter(xs.iter().rev(), xs.len());
2888 let mut it = xs.iter().rev();
2892 check_randacc_iter(it, xs.len() - 3);
2896 fn test_random_access_zip() {
2897 let xs = [1, 2, 3, 4, 5];
2898 let ys = [7, 9, 11];
2899 check_randacc_iter(xs.iter().zip(ys.iter()), cmp::min(xs.len(), ys.len()));
2903 fn test_random_access_take() {
2904 let xs = [1, 2, 3, 4, 5];
2905 let empty: &[int] = [];
2906 check_randacc_iter(xs.iter().take(3), 3);
2907 check_randacc_iter(xs.iter().take(20), xs.len());
2908 check_randacc_iter(xs.iter().take(0), 0);
2909 check_randacc_iter(empty.iter().take(2), 0);
2913 fn test_random_access_skip() {
2914 let xs = [1, 2, 3, 4, 5];
2915 let empty: &[int] = [];
2916 check_randacc_iter(xs.iter().skip(2), xs.len() - 2);
2917 check_randacc_iter(empty.iter().skip(2), 0);
2921 fn test_random_access_inspect() {
2922 let xs = [1, 2, 3, 4, 5];
2924 // test .map and .inspect that don't implement Clone
2925 let it = xs.iter().inspect(|_| {});
2926 assert_eq!(xs.len(), it.indexable());
2927 for (i, elt) in xs.iter().enumerate() {
2928 assert_eq!(Some(elt), it.idx(i));
2934 fn test_random_access_map() {
2935 let xs = [1, 2, 3, 4, 5];
2937 let it = xs.iter().map(|x| *x);
2938 assert_eq!(xs.len(), it.indexable());
2939 for (i, elt) in xs.iter().enumerate() {
2940 assert_eq!(Some(*elt), it.idx(i));
2945 fn test_random_access_cycle() {
2946 let xs = [1, 2, 3, 4, 5];
2947 let empty: &[int] = [];
2948 check_randacc_iter(xs.iter().cycle().take(27), 27);
2949 check_randacc_iter(empty.iter().cycle(), 0);
2953 fn test_double_ended_range() {
2954 assert_eq!(range(11i, 14).rev().collect::<~[int]>(), ~[13i, 12, 11]);
2955 for _ in range(10i, 0).rev() {
2956 fail!("unreachable");
2959 assert_eq!(range(11u, 14).rev().collect::<~[uint]>(), ~[13u, 12, 11]);
2960 for _ in range(10u, 0).rev() {
2961 fail!("unreachable");
2967 /// A mock type to check Range when ToPrimitive returns None
2970 impl ToPrimitive for Foo {
2971 fn to_i64(&self) -> Option<i64> { None }
2972 fn to_u64(&self) -> Option<u64> { None }
2975 impl Add<Foo, Foo> for Foo {
2976 fn add(&self, _: &Foo) -> Foo {
2982 fn lt(&self, _: &Foo) -> bool {
2987 impl Clone for Foo {
2988 fn clone(&self) -> Foo {
2993 impl Mul<Foo, Foo> for Foo {
2994 fn mul(&self, _: &Foo) -> Foo {
2999 impl num::One for Foo {
3005 assert_eq!(range(0i, 5).collect::<~[int]>(), ~[0i, 1, 2, 3, 4]);
3006 assert_eq!(range(-10i, -1).collect::<~[int]>(), ~[-10, -9, -8, -7, -6, -5, -4, -3, -2]);
3007 assert_eq!(range(0i, 5).rev().collect::<~[int]>(), ~[4, 3, 2, 1, 0]);
3008 assert_eq!(range(200, -5).collect::<~[int]>(), ~[]);
3009 assert_eq!(range(200, -5).rev().collect::<~[int]>(), ~[]);
3010 assert_eq!(range(200, 200).collect::<~[int]>(), ~[]);
3011 assert_eq!(range(200, 200).rev().collect::<~[int]>(), ~[]);
3013 assert_eq!(range(0i, 100).size_hint(), (100, Some(100)));
3014 // this test is only meaningful when sizeof uint < sizeof u64
3015 assert_eq!(range(uint::MAX - 1, uint::MAX).size_hint(), (1, Some(1)));
3016 assert_eq!(range(-10i, -1).size_hint(), (9, Some(9)));
3017 assert_eq!(range(Foo, Foo).size_hint(), (0, None));
3021 fn test_range_inclusive() {
3022 assert_eq!(range_inclusive(0i, 5).collect::<~[int]>(), ~[0i, 1, 2, 3, 4, 5]);
3023 assert_eq!(range_inclusive(0i, 5).rev().collect::<~[int]>(), ~[5i, 4, 3, 2, 1, 0]);
3024 assert_eq!(range_inclusive(200, -5).collect::<~[int]>(), ~[]);
3025 assert_eq!(range_inclusive(200, -5).rev().collect::<~[int]>(), ~[]);
3026 assert_eq!(range_inclusive(200, 200).collect::<~[int]>(), ~[200]);
3027 assert_eq!(range_inclusive(200, 200).rev().collect::<~[int]>(), ~[200]);
3031 fn test_range_step() {
3032 assert_eq!(range_step(0i, 20, 5).collect::<~[int]>(), ~[0, 5, 10, 15]);
3033 assert_eq!(range_step(20i, 0, -5).collect::<~[int]>(), ~[20, 15, 10, 5]);
3034 assert_eq!(range_step(20i, 0, -6).collect::<~[int]>(), ~[20, 14, 8, 2]);
3035 assert_eq!(range_step(200u8, 255, 50).collect::<~[u8]>(), ~[200u8, 250]);
3036 assert_eq!(range_step(200, -5, 1).collect::<~[int]>(), ~[]);
3037 assert_eq!(range_step(200, 200, 1).collect::<~[int]>(), ~[]);
3041 fn test_range_step_inclusive() {
3042 assert_eq!(range_step_inclusive(0i, 20, 5).collect::<~[int]>(), ~[0, 5, 10, 15, 20]);
3043 assert_eq!(range_step_inclusive(20i, 0, -5).collect::<~[int]>(), ~[20, 15, 10, 5, 0]);
3044 assert_eq!(range_step_inclusive(20i, 0, -6).collect::<~[int]>(), ~[20, 14, 8, 2]);
3045 assert_eq!(range_step_inclusive(200u8, 255, 50).collect::<~[u8]>(), ~[200u8, 250]);
3046 assert_eq!(range_step_inclusive(200, -5, 1).collect::<~[int]>(), ~[]);
3047 assert_eq!(range_step_inclusive(200, 200, 1).collect::<~[int]>(), ~[200]);
3052 let mut ys = [1, 2, 3, 4, 5];
3053 ys.mut_iter().reverse_();
3054 assert_eq!(ys, [5, 4, 3, 2, 1]);
3058 fn test_peekable_is_empty() {
3060 let mut it = a.iter().peekable();
3061 assert!( !it.is_empty() );
3063 assert!( it.is_empty() );
3068 let v: [int, ..0] = [];
3069 assert_eq!(v.iter().min_max(), NoElements);
3072 assert!(v.iter().min_max() == OneElement(&1));
3074 let v = [1i, 2, 3, 4, 5];
3075 assert!(v.iter().min_max() == MinMax(&1, &5));
3077 let v = [1i, 2, 3, 4, 5, 6];
3078 assert!(v.iter().min_max() == MinMax(&1, &6));
3080 let v = [1i, 1, 1, 1];
3081 assert!(v.iter().min_max() == MinMax(&1, &1));
3085 fn test_MinMaxResult() {
3086 let r: MinMaxResult<int> = NoElements;
3087 assert_eq!(r.into_option(), None)
3089 let r = OneElement(1);
3090 assert_eq!(r.into_option(), Some((1,1)));
3092 let r = MinMax(1,2);
3093 assert_eq!(r.into_option(), Some((1,2)));