1 // Copyright 2013 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 defines an interface for objects which implement iteration as a state machine.
15 Algorithms like `zip` are provided as `Iterator` implementations which wrap other objects
16 implementing the `Iterator` trait.
21 use num::{Zero, One, Saturating};
22 use option::{Option, Some, None};
28 /// Conversion from an `Iterator`
29 pub trait FromIterator<A, T: Iterator<A>> {
30 /// Build a container with elements from an external iterator.
31 fn from_iterator(iterator: &mut T) -> Self;
34 /// A type growable from an `Iterator` implementation
35 pub trait Extendable<A, T: Iterator<A>>: FromIterator<A, T> {
36 /// Extend a container with the elements yielded by an iterator
37 fn extend(&mut self, iterator: &mut T);
40 /// An interface for dealing with "external iterators". These types of iterators
41 /// can be resumed at any time as all state is stored internally as opposed to
42 /// being located on the call stack.
43 pub trait Iterator<A> {
44 /// Advance the iterator and return the next value. Return `None` when the end is reached.
45 fn next(&mut self) -> Option<A>;
47 /// Return a lower bound and upper bound on the remaining length of the iterator.
49 /// The common use case for the estimate is pre-allocating space to store the results.
51 fn size_hint(&self) -> (uint, Option<uint>) { (0, None) }
54 /// A range iterator able to yield elements from both ends
55 pub trait DoubleEndedIterator<A>: Iterator<A> {
56 /// Yield an element from the end of the range, returning `None` if the range is empty.
57 fn next_back(&mut self) -> Option<A>;
60 /// An object implementing random access indexing by `uint`
62 /// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`.
63 pub trait RandomAccessIterator<A>: Iterator<A> {
64 /// Return the number of indexable elements. At most `std::uint::max_value`
65 /// elements are indexable, even if the iterator represents a longer range.
66 fn indexable(&self) -> uint;
68 /// Return an element at an index
69 fn idx(&self, index: uint) -> Option<A>;
72 /// Iterator adaptors provided for every `DoubleEndedIterator` implementation.
74 /// In the future these will be default methods instead of a utility trait.
75 pub trait DoubleEndedIteratorUtil {
76 /// Flip the direction of the iterator
77 fn invert(self) -> Invert<Self>;
80 /// Iterator adaptors provided for every `DoubleEndedIterator` implementation.
82 /// In the future these will be default methods instead of a utility trait.
83 impl<A, T: DoubleEndedIterator<A>> DoubleEndedIteratorUtil for T {
84 /// Flip the direction of the iterator
86 /// The inverted iterator flips the ends on an iterator that can already
87 /// be iterated from the front and from the back.
90 /// If the iterator also implements RandomAccessIterator, the inverted
91 /// iterator is also random access, with the indices starting at the back
92 /// of the original iterator.
94 /// Note: Random access with inverted indices still only applies to the first
95 /// `uint::max_value` elements of the original iterator.
97 fn invert(self) -> Invert<T> {
102 /// An double-ended iterator with the direction inverted
104 pub struct Invert<T> {
108 impl<A, T: DoubleEndedIterator<A>> Iterator<A> for Invert<T> {
110 fn next(&mut self) -> Option<A> { self.iter.next_back() }
112 fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
115 impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Invert<T> {
117 fn next_back(&mut self) -> Option<A> { self.iter.next() }
120 impl<A, T: DoubleEndedIterator<A> + RandomAccessIterator<A>> RandomAccessIterator<A>
123 fn indexable(&self) -> uint { self.iter.indexable() }
125 fn idx(&self, index: uint) -> Option<A> {
126 self.iter.idx(self.indexable() - index - 1)
130 /// Iterator adaptors provided for every `Iterator` implementation. The adaptor objects are also
131 /// implementations of the `Iterator` trait.
133 /// In the future these will be default methods instead of a utility trait.
134 pub trait IteratorUtil<A> {
135 /// Chain this iterator with another, returning a new iterator which will
136 /// finish iterating over the current iterator, and then it will iterate
137 /// over the other specified iterator.
144 /// let mut it = a.iter().chain_(b.iter());
145 /// assert_eq!(it.next().get(), &0);
146 /// assert_eq!(it.next().get(), &1);
147 /// assert!(it.next().is_none());
149 fn chain_<U: Iterator<A>>(self, other: U) -> Chain<Self, U>;
151 /// Creates an iterator which iterates over both this and the specified
152 /// iterators simultaneously, yielding the two elements as pairs. When
153 /// either iterator returns None, all further invocations of next() will
161 /// let mut it = a.iter().zip(b.iter());
162 /// assert_eq!(it.next().get(), (&0, &1));
163 /// assert!(it.next().is_none());
165 fn zip<B, U: Iterator<B>>(self, other: U) -> Zip<Self, U>;
167 // FIXME: #5898: should be called map
168 /// Creates a new iterator which will apply the specified function to each
169 /// element returned by the first, yielding the mapped element instead.
175 /// let mut it = a.iter().transform(|&x| 2 * x);
176 /// assert_eq!(it.next().get(), 2);
177 /// assert_eq!(it.next().get(), 4);
178 /// assert!(it.next().is_none());
180 fn transform<'r, B>(self, f: &'r fn(A) -> B) -> Map<'r, A, B, Self>;
182 /// Creates an iterator which applies the predicate to each element returned
183 /// by this iterator. Only elements which have the predicate evaluate to
184 /// `true` will be yielded.
190 /// let mut it = a.iter().filter(|&x| *x > 1);
191 /// assert_eq!(it.next().get(), &2);
192 /// assert!(it.next().is_none());
194 fn filter<'r>(self, predicate: &'r fn(&A) -> bool) -> Filter<'r, A, Self>;
196 /// Creates an iterator which both filters and maps elements.
197 /// If the specified function returns None, the element is skipped.
198 /// Otherwise the option is unwrapped and the new value is yielded.
204 /// let mut it = a.iter().filter_map(|&x| if x > 1 {Some(2 * x)} else {None});
205 /// assert_eq!(it.next().get(), 4);
206 /// assert!(it.next().is_none());
208 fn filter_map<'r, B>(self, f: &'r fn(A) -> Option<B>) -> FilterMap<'r, A, B, Self>;
210 /// Creates an iterator which yields a pair of the value returned by this
211 /// iterator plus the current index of iteration.
216 /// let a = [100, 200];
217 /// let mut it = a.iter().enumerate();
218 /// assert_eq!(it.next().get(), (0, &100));
219 /// assert_eq!(it.next().get(), (1, &200));
220 /// assert!(it.next().is_none());
222 fn enumerate(self) -> Enumerate<Self>;
224 /// Creates an iterator which invokes the predicate on elements until it
225 /// returns false. Once the predicate returns false, all further elements are
231 /// let a = [1, 2, 3, 2, 1];
232 /// let mut it = a.iter().skip_while(|&a| *a < 3);
233 /// assert_eq!(it.next().get(), &3);
234 /// assert_eq!(it.next().get(), &2);
235 /// assert_eq!(it.next().get(), &1);
236 /// assert!(it.next().is_none());
238 fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) -> SkipWhile<'r, A, Self>;
240 /// Creates an iterator which yields elements so long as the predicate
241 /// returns true. After the predicate returns false for the first time, no
242 /// further elements will be yielded.
247 /// let a = [1, 2, 3, 2, 1];
248 /// let mut it = a.iter().take_while(|&a| *a < 3);
249 /// assert_eq!(it.next().get(), &1);
250 /// assert_eq!(it.next().get(), &2);
251 /// assert!(it.next().is_none());
253 fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) -> TakeWhile<'r, A, Self>;
255 /// Creates an iterator which skips the first `n` elements of this iterator,
256 /// and then it yields all further items.
261 /// let a = [1, 2, 3, 4, 5];
262 /// let mut it = a.iter().skip(3);
263 /// assert_eq!(it.next().get(), &4);
264 /// assert_eq!(it.next().get(), &5);
265 /// assert!(it.next().is_none());
267 fn skip(self, n: uint) -> Skip<Self>;
269 // FIXME: #5898: should be called take
270 /// Creates an iterator which yields the first `n` elements of this
271 /// iterator, and then it will always return None.
276 /// let a = [1, 2, 3, 4, 5];
277 /// let mut it = a.iter().take_(3);
278 /// assert_eq!(it.next().get(), &1);
279 /// assert_eq!(it.next().get(), &2);
280 /// assert_eq!(it.next().get(), &3);
281 /// assert!(it.next().is_none());
283 fn take_(self, n: uint) -> Take<Self>;
285 /// Creates a new iterator which behaves in a similar fashion to foldl.
286 /// There is a state which is passed between each iteration and can be
287 /// mutated as necessary. The yielded values from the closure are yielded
288 /// from the Scan instance when not None.
293 /// let a = [1, 2, 3, 4, 5];
294 /// let mut it = a.iter().scan(1, |fac, &x| {
298 /// assert_eq!(it.next().get(), 1);
299 /// assert_eq!(it.next().get(), 2);
300 /// assert_eq!(it.next().get(), 6);
301 /// assert_eq!(it.next().get(), 24);
302 /// assert_eq!(it.next().get(), 120);
303 /// assert!(it.next().is_none());
305 fn scan<'r, St, B>(self, initial_state: St, f: &'r fn(&mut St, A) -> Option<B>)
306 -> Scan<'r, A, B, Self, St>;
308 /// Creates an iterator that maps each element to an iterator,
309 /// and yields the elements of the produced iterators
314 /// let xs = [2u, 3];
315 /// let ys = [0u, 1, 0, 1, 2];
316 /// let mut it = xs.iter().flat_map_(|&x| count(0u, 1).take_(x));
317 /// // Check that `it` has the same elements as `ys`
319 /// for x: uint in it {
320 /// assert_eq!(x, ys[i]);
324 // FIXME: #5898: should be called `flat_map`
325 fn flat_map_<'r, B, U: Iterator<B>>(self, f: &'r fn(A) -> U)
326 -> FlatMap<'r, A, Self, U>;
328 /// Creates an iterator that calls a function with a reference to each
329 /// element before yielding it. This is often useful for debugging an
330 /// iterator pipeline.
335 ///let xs = [1u, 4, 2, 3, 8, 9, 6];
336 ///let sum = xs.iter()
337 /// .transform(|&x| x)
338 /// .peek_(|&x| debug!("filtering %u", x))
339 /// .filter(|&x| x % 2 == 0)
340 /// .peek_(|&x| debug!("%u made it through", x))
342 ///println(sum.to_str());
344 // FIXME: #5898: should be called `peek`
345 fn peek_<'r>(self, f: &'r fn(&A)) -> Peek<'r, A, Self>;
347 /// An adaptation of an external iterator to the for-loop protocol of rust.
352 /// use std::iterator::Counter;
354 /// for i in count(0, 10) {
355 /// printfln!("%d", i);
358 fn advance(&mut self, f: &fn(A) -> bool) -> bool;
360 /// Loops through the entire iterator, collecting all of the elements into
361 /// a container implementing `FromIterator`.
366 /// let a = [1, 2, 3, 4, 5];
367 /// let b: ~[int] = a.iter().transform(|&x| x).collect();
370 fn collect<B: FromIterator<A, Self>>(&mut self) -> B;
372 /// Loops through the entire iterator, collecting all of the elements into
373 /// a unique vector. This is simply collect() specialized for vectors.
378 /// let a = [1, 2, 3, 4, 5];
379 /// let b: ~[int] = a.iter().transform(|&x| x).to_owned_vec();
382 fn to_owned_vec(&mut self) -> ~[A];
384 /// Loops through `n` iterations, returning the `n`th element of the
390 /// let a = [1, 2, 3, 4, 5];
391 /// let mut it = a.iter();
392 /// assert!(it.nth(2).get() == &3);
393 /// assert!(it.nth(2) == None);
395 fn nth(&mut self, n: uint) -> Option<A>;
397 /// Loops through the entire iterator, returning the last element of the
403 /// let a = [1, 2, 3, 4, 5];
404 /// assert!(a.iter().last().get() == &5);
406 // FIXME: #5898: should be called `last`
407 fn last_(&mut self) -> Option<A>;
409 /// Performs a fold operation over the entire iterator, returning the
410 /// eventual state at the end of the iteration.
415 /// let a = [1, 2, 3, 4, 5];
416 /// assert!(a.iter().fold(0, |a, &b| a + b) == 15);
418 fn fold<B>(&mut self, start: B, f: &fn(B, A) -> B) -> B;
420 // FIXME: #5898: should be called len
421 /// Counts the number of elements in this iterator.
426 /// let a = [1, 2, 3, 4, 5];
427 /// let mut it = a.iter();
428 /// assert!(it.len_() == 5);
429 /// assert!(it.len_() == 0);
431 fn len_(&mut self) -> uint;
433 /// Tests whether the predicate holds true for all elements in the iterator.
438 /// let a = [1, 2, 3, 4, 5];
439 /// assert!(a.iter().all(|&x| *x > 0));
440 /// assert!(!a.iter().all(|&x| *x > 2));
442 fn all(&mut self, f: &fn(A) -> bool) -> bool;
444 /// Tests whether any element of an iterator satisfies the specified
450 /// let a = [1, 2, 3, 4, 5];
451 /// let mut it = a.iter();
452 /// assert!(it.any(|&x| *x == 3));
453 /// assert!(!it.any(|&x| *x == 3));
455 fn any(&mut self, f: &fn(A) -> bool) -> bool;
457 /// Return the first element satisfying the specified predicate
458 fn find_(&mut self, predicate: &fn(&A) -> bool) -> Option<A>;
460 /// Return the index of the first element satisfying the specified predicate
461 fn position(&mut self, predicate: &fn(A) -> bool) -> Option<uint>;
463 /// Count the number of elements satisfying the specified predicate
464 fn count(&mut self, predicate: &fn(A) -> bool) -> uint;
466 /// Return the element that gives the maximum value from the specfied function
471 /// let xs = [-3, 0, 1, 5, -10];
472 /// assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
474 fn max_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A>;
476 /// Return the element that gives the minimum value from the specfied function
481 /// let xs = [-3, 0, 1, 5, -10];
482 /// assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
484 fn min_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A>;
487 /// Iterator adaptors provided for every `Iterator` implementation. The adaptor objects are also
488 /// implementations of the `Iterator` trait.
490 /// In the future these will be default methods instead of a utility trait.
491 impl<A, T: Iterator<A>> IteratorUtil<A> for T {
493 fn chain_<U: Iterator<A>>(self, other: U) -> Chain<T, U> {
494 Chain{a: self, b: other, flag: false}
498 fn zip<B, U: Iterator<B>>(self, other: U) -> Zip<T, U> {
499 Zip{a: self, b: other}
502 // FIXME: #5898: should be called map
504 fn transform<'r, B>(self, f: &'r fn(A) -> B) -> Map<'r, A, B, T> {
505 Map{iter: self, f: f}
509 fn filter<'r>(self, predicate: &'r fn(&A) -> bool) -> Filter<'r, A, T> {
510 Filter{iter: self, predicate: predicate}
514 fn filter_map<'r, B>(self, f: &'r fn(A) -> Option<B>) -> FilterMap<'r, A, B, T> {
515 FilterMap { iter: self, f: f }
519 fn enumerate(self) -> Enumerate<T> {
520 Enumerate{iter: self, count: 0}
524 fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) -> SkipWhile<'r, A, T> {
525 SkipWhile{iter: self, flag: false, predicate: predicate}
529 fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) -> TakeWhile<'r, A, T> {
530 TakeWhile{iter: self, flag: false, predicate: predicate}
534 fn skip(self, n: uint) -> Skip<T> {
535 Skip{iter: self, n: n}
538 // FIXME: #5898: should be called take
540 fn take_(self, n: uint) -> Take<T> {
541 Take{iter: self, n: n}
545 fn scan<'r, St, B>(self, initial_state: St, f: &'r fn(&mut St, A) -> Option<B>)
546 -> Scan<'r, A, B, T, St> {
547 Scan{iter: self, f: f, state: initial_state}
551 fn flat_map_<'r, B, U: Iterator<B>>(self, f: &'r fn(A) -> U)
552 -> FlatMap<'r, A, T, U> {
553 FlatMap{iter: self, f: f, frontiter: None, backiter: None }
556 // FIXME: #5898: should be called `peek`
558 fn peek_<'r>(self, f: &'r fn(&A)) -> Peek<'r, A, T> {
559 Peek{iter: self, f: f}
562 /// A shim implementing the `for` loop iteration protocol for iterator objects
564 fn advance(&mut self, f: &fn(A) -> bool) -> bool {
568 if !f(x) { return false; }
570 None => { return true; }
576 fn collect<B: FromIterator<A, T>>(&mut self) -> B {
577 FromIterator::from_iterator(self)
581 fn to_owned_vec(&mut self) -> ~[A] {
585 /// Return the `n`th item yielded by an iterator.
587 fn nth(&mut self, mut n: uint) -> Option<A> {
590 Some(x) => if n == 0 { return Some(x) },
597 /// Return the last item yielded by an iterator.
599 fn last_(&mut self) -> Option<A> {
601 for x in *self { last = Some(x); }
605 /// Reduce an iterator to an accumulated value
607 fn fold<B>(&mut self, init: B, f: &fn(B, A) -> B) -> B {
608 let mut accum = init;
611 Some(x) => { accum = f(accum, x); }
618 /// Count the number of items yielded by an iterator
620 fn len_(&mut self) -> uint { self.fold(0, |cnt, _x| cnt + 1) }
623 fn all(&mut self, f: &fn(A) -> bool) -> bool {
624 for x in *self { if !f(x) { return false; } }
629 fn any(&mut self, f: &fn(A) -> bool) -> bool {
630 for x in *self { if f(x) { return true; } }
634 /// Return the first element satisfying the specified predicate
636 fn find_(&mut self, predicate: &fn(&A) -> bool) -> Option<A> {
638 if predicate(&x) { return Some(x) }
643 /// Return the index of the first element satisfying the specified predicate
645 fn position(&mut self, predicate: &fn(A) -> bool) -> Option<uint> {
657 fn count(&mut self, predicate: &fn(A) -> bool) -> uint {
660 if predicate(x) { i += 1 }
666 fn max_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A> {
667 self.fold(None, |max: Option<(A, B)>, x| {
670 None => Some((x, x_val)),
671 Some((y, y_val)) => if x_val > y_val {
677 }).map_consume(|(x, _)| x)
681 fn min_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A> {
682 self.fold(None, |min: Option<(A, B)>, x| {
685 None => Some((x, x_val)),
686 Some((y, y_val)) => if x_val < y_val {
692 }).map_consume(|(x, _)| x)
696 /// A trait for iterators over elements which can be added together
697 pub trait AdditiveIterator<A> {
698 /// Iterates over the entire iterator, summing up all the elements
703 /// let a = [1, 2, 3, 4, 5];
704 /// let mut it = a.iter().transform(|&x| x);
705 /// assert!(it.sum() == 15);
707 fn sum(&mut self) -> A;
710 impl<A: Add<A, A> + Zero, T: Iterator<A>> AdditiveIterator<A> for T {
712 fn sum(&mut self) -> A { self.fold(Zero::zero::<A>(), |s, x| s + x) }
715 /// A trait for iterators over elements whose elements can be multiplied
717 pub trait MultiplicativeIterator<A> {
718 /// Iterates over the entire iterator, multiplying all the elements
723 /// use std::iterator::Counter;
725 /// fn factorial(n: uint) -> uint {
726 /// count(1u, 1).take_while(|&i| i <= n).product()
728 /// assert!(factorial(0) == 1);
729 /// assert!(factorial(1) == 1);
730 /// assert!(factorial(5) == 120);
732 fn product(&mut self) -> A;
735 impl<A: Mul<A, A> + One, T: Iterator<A>> MultiplicativeIterator<A> for T {
737 fn product(&mut self) -> A { self.fold(One::one::<A>(), |p, x| p * x) }
740 /// A trait for iterators over elements which can be compared to one another.
741 /// The type of each element must ascribe to the `Ord` trait.
742 pub trait OrdIterator<A> {
743 /// Consumes the entire iterator to return the maximum element.
748 /// let a = [1, 2, 3, 4, 5];
749 /// assert!(a.iter().max().get() == &5);
751 fn max(&mut self) -> Option<A>;
753 /// Consumes the entire iterator to return the minimum element.
758 /// let a = [1, 2, 3, 4, 5];
759 /// assert!(a.iter().min().get() == &1);
761 fn min(&mut self) -> Option<A>;
764 impl<A: Ord, T: Iterator<A>> OrdIterator<A> for T {
766 fn max(&mut self) -> Option<A> {
767 self.fold(None, |max, x| {
770 Some(y) => Some(cmp::max(x, y))
776 fn min(&mut self) -> Option<A> {
777 self.fold(None, |min, x| {
780 Some(y) => Some(cmp::min(x, y))
786 /// A trait for iterators that are clonable.
787 pub trait ClonableIterator {
788 /// Repeats an iterator endlessly
793 /// let a = count(1,1).take_(1);
794 /// let mut cy = a.cycle();
795 /// assert_eq!(cy.next(), Some(1));
796 /// assert_eq!(cy.next(), Some(1));
798 fn cycle(self) -> Cycle<Self>;
801 impl<A, T: Clone + Iterator<A>> ClonableIterator for T {
803 fn cycle(self) -> Cycle<T> {
804 Cycle{orig: self.clone(), iter: self}
808 /// An iterator that repeats endlessly
810 pub struct Cycle<T> {
815 impl<A, T: Clone + Iterator<A>> Iterator<A> for Cycle<T> {
817 fn next(&mut self) -> Option<A> {
818 match self.iter.next() {
819 None => { self.iter = self.orig.clone(); self.iter.next() }
825 fn size_hint(&self) -> (uint, Option<uint>) {
826 // the cycle iterator is either empty or infinite
827 match self.orig.size_hint() {
828 sz @ (0, Some(0)) => sz,
830 _ => (uint::max_value, None)
835 impl<A, T: Clone + RandomAccessIterator<A>> RandomAccessIterator<A> for Cycle<T> {
837 fn indexable(&self) -> uint {
838 if self.orig.indexable() > 0 {
846 fn idx(&self, index: uint) -> Option<A> {
847 let liter = self.iter.indexable();
848 let lorig = self.orig.indexable();
851 } else if index < liter {
854 self.orig.idx((index - liter) % lorig)
859 /// An iterator which strings two iterators together
861 pub struct Chain<T, U> {
867 impl<A, T: Iterator<A>, U: Iterator<A>> Iterator<A> for Chain<T, U> {
869 fn next(&mut self) -> Option<A> {
873 match self.a.next() {
874 Some(x) => return Some(x),
883 fn size_hint(&self) -> (uint, Option<uint>) {
884 let (a_lower, a_upper) = self.a.size_hint();
885 let (b_lower, b_upper) = self.b.size_hint();
887 let lower = a_lower.saturating_add(b_lower);
889 let upper = match (a_upper, b_upper) {
890 (Some(x), Some(y)) => Some(x.saturating_add(y)),
898 impl<A, T: DoubleEndedIterator<A>, U: DoubleEndedIterator<A>> DoubleEndedIterator<A>
901 fn next_back(&mut self) -> Option<A> {
902 match self.b.next_back() {
904 None => self.a.next_back()
909 impl<A, T: RandomAccessIterator<A>, U: RandomAccessIterator<A>> RandomAccessIterator<A>
912 fn indexable(&self) -> uint {
913 let (a, b) = (self.a.indexable(), self.b.indexable());
918 fn idx(&self, index: uint) -> Option<A> {
919 let len = self.a.indexable();
923 self.b.idx(index - len)
928 /// An iterator which iterates two other iterators simultaneously
930 pub struct Zip<T, U> {
935 impl<A, B, T: Iterator<A>, U: Iterator<B>> Iterator<(A, B)> for Zip<T, U> {
937 fn next(&mut self) -> Option<(A, B)> {
938 match (self.a.next(), self.b.next()) {
939 (Some(x), Some(y)) => Some((x, y)),
945 fn size_hint(&self) -> (uint, Option<uint>) {
946 let (a_lower, a_upper) = self.a.size_hint();
947 let (b_lower, b_upper) = self.b.size_hint();
949 let lower = cmp::min(a_lower, b_lower);
951 let upper = match (a_upper, b_upper) {
952 (Some(x), Some(y)) => Some(cmp::min(x,y)),
953 (Some(x), None) => Some(x),
954 (None, Some(y)) => Some(y),
962 impl<A, B, T: RandomAccessIterator<A>, U: RandomAccessIterator<B>>
963 RandomAccessIterator<(A, B)> for Zip<T, U> {
965 fn indexable(&self) -> uint {
966 cmp::min(self.a.indexable(), self.b.indexable())
970 fn idx(&self, index: uint) -> Option<(A, B)> {
971 match (self.a.idx(index), self.b.idx(index)) {
972 (Some(x), Some(y)) => Some((x, y)),
978 /// An iterator which maps the values of `iter` with `f`
979 pub struct Map<'self, A, B, T> {
981 priv f: &'self fn(A) -> B
984 impl<'self, A, B, T> Map<'self, A, B, T> {
986 fn do_map(&self, elt: Option<A>) -> Option<B> {
988 Some(a) => Some((self.f)(a)),
994 impl<'self, A, B, T: Iterator<A>> Iterator<B> for Map<'self, A, B, T> {
996 fn next(&mut self) -> Option<B> {
997 let next = self.iter.next();
1002 fn size_hint(&self) -> (uint, Option<uint>) {
1003 self.iter.size_hint()
1007 impl<'self, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B>
1008 for Map<'self, A, B, T> {
1010 fn next_back(&mut self) -> Option<B> {
1011 let next = self.iter.next_back();
1016 impl<'self, A, B, T: RandomAccessIterator<A>> RandomAccessIterator<B>
1017 for Map<'self, A, B, T> {
1019 fn indexable(&self) -> uint {
1020 self.iter.indexable()
1024 fn idx(&self, index: uint) -> Option<B> {
1025 self.do_map(self.iter.idx(index))
1029 /// An iterator which filters the elements of `iter` with `predicate`
1030 pub struct Filter<'self, A, T> {
1032 priv predicate: &'self fn(&A) -> bool
1035 impl<'self, A, T: Iterator<A>> Iterator<A> for Filter<'self, A, T> {
1037 fn next(&mut self) -> Option<A> {
1038 for x in self.iter {
1039 if (self.predicate)(&x) {
1049 fn size_hint(&self) -> (uint, Option<uint>) {
1050 let (_, upper) = self.iter.size_hint();
1051 (0, upper) // can't know a lower bound, due to the predicate
1055 impl<'self, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Filter<'self, A, T> {
1057 fn next_back(&mut self) -> Option<A> {
1059 match self.iter.next_back() {
1060 None => return None,
1062 if (self.predicate)(&x) {
1073 /// An iterator which uses `f` to both filter and map elements from `iter`
1074 pub struct FilterMap<'self, A, B, T> {
1076 priv f: &'self fn(A) -> Option<B>
1079 impl<'self, A, B, T: Iterator<A>> Iterator<B> for FilterMap<'self, A, B, T> {
1081 fn next(&mut self) -> Option<B> {
1082 for x in self.iter {
1084 Some(y) => return Some(y),
1092 fn size_hint(&self) -> (uint, Option<uint>) {
1093 let (_, upper) = self.iter.size_hint();
1094 (0, upper) // can't know a lower bound, due to the predicate
1098 impl<'self, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B>
1099 for FilterMap<'self, A, B, T> {
1101 fn next_back(&mut self) -> Option<B> {
1103 match self.iter.next_back() {
1104 None => return None,
1107 Some(y) => return Some(y),
1116 /// An iterator which yields the current count and the element during iteration
1118 pub struct Enumerate<T> {
1123 impl<A, T: Iterator<A>> Iterator<(uint, A)> for Enumerate<T> {
1125 fn next(&mut self) -> Option<(uint, A)> {
1126 match self.iter.next() {
1128 let ret = Some((self.count, a));
1137 fn size_hint(&self) -> (uint, Option<uint>) {
1138 self.iter.size_hint()
1142 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<(uint, A)> for Enumerate<T> {
1144 fn indexable(&self) -> uint {
1145 self.iter.indexable()
1149 fn idx(&self, index: uint) -> Option<(uint, A)> {
1150 match self.iter.idx(index) {
1151 Some(a) => Some((self.count + index, a)),
1157 /// An iterator which rejects elements while `predicate` is true
1158 pub struct SkipWhile<'self, A, T> {
1161 priv predicate: &'self fn(&A) -> bool
1164 impl<'self, A, T: Iterator<A>> Iterator<A> for SkipWhile<'self, A, T> {
1166 fn next(&mut self) -> Option<A> {
1167 let mut next = self.iter.next();
1174 if (self.predicate)(&x) {
1175 next = self.iter.next();
1189 fn size_hint(&self) -> (uint, Option<uint>) {
1190 let (_, upper) = self.iter.size_hint();
1191 (0, upper) // can't know a lower bound, due to the predicate
1195 /// An iterator which only accepts elements while `predicate` is true
1196 pub struct TakeWhile<'self, A, T> {
1199 priv predicate: &'self fn(&A) -> bool
1202 impl<'self, A, T: Iterator<A>> Iterator<A> for TakeWhile<'self, A, T> {
1204 fn next(&mut self) -> Option<A> {
1208 match self.iter.next() {
1210 if (self.predicate)(&x) {
1223 fn size_hint(&self) -> (uint, Option<uint>) {
1224 let (_, upper) = self.iter.size_hint();
1225 (0, upper) // can't know a lower bound, due to the predicate
1229 /// An iterator which skips over `n` elements of `iter`.
1231 pub struct Skip<T> {
1236 impl<A, T: Iterator<A>> Iterator<A> for Skip<T> {
1238 fn next(&mut self) -> Option<A> {
1239 let mut next = self.iter.next();
1248 next = self.iter.next();
1263 fn size_hint(&self) -> (uint, Option<uint>) {
1264 let (lower, upper) = self.iter.size_hint();
1266 let lower = lower.saturating_sub(self.n);
1268 let upper = match upper {
1269 Some(x) => Some(x.saturating_sub(self.n)),
1277 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Skip<T> {
1279 fn indexable(&self) -> uint {
1280 self.iter.indexable().saturating_sub(self.n)
1284 fn idx(&self, index: uint) -> Option<A> {
1285 if index >= self.indexable() {
1288 self.iter.idx(index + self.n)
1293 /// An iterator which only iterates over the first `n` iterations of `iter`.
1295 pub struct Take<T> {
1300 impl<A, T: Iterator<A>> Iterator<A> for Take<T> {
1302 fn next(&mut self) -> Option<A> {
1312 fn size_hint(&self) -> (uint, Option<uint>) {
1313 let (lower, upper) = self.iter.size_hint();
1315 let lower = cmp::min(lower, self.n);
1317 let upper = match upper {
1318 Some(x) if x < self.n => Some(x),
1326 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Take<T> {
1328 fn indexable(&self) -> uint {
1329 cmp::min(self.iter.indexable(), self.n)
1333 fn idx(&self, index: uint) -> Option<A> {
1334 if index >= self.n {
1337 self.iter.idx(index)
1343 /// An iterator to maintain state while iterating another iterator
1344 pub struct Scan<'self, A, B, T, St> {
1346 priv f: &'self fn(&mut St, A) -> Option<B>,
1348 /// The current internal state to be passed to the closure next.
1352 impl<'self, A, B, T: Iterator<A>, St> Iterator<B> for Scan<'self, A, B, T, St> {
1354 fn next(&mut self) -> Option<B> {
1355 self.iter.next().chain(|a| (self.f)(&mut self.state, a))
1359 fn size_hint(&self) -> (uint, Option<uint>) {
1360 let (_, upper) = self.iter.size_hint();
1361 (0, upper) // can't know a lower bound, due to the scan function
1365 /// An iterator that maps each element to an iterator,
1366 /// and yields the elements of the produced iterators
1368 pub struct FlatMap<'self, A, T, U> {
1370 priv f: &'self fn(A) -> U,
1371 priv frontiter: Option<U>,
1372 priv backiter: Option<U>,
1375 impl<'self, A, T: Iterator<A>, B, U: Iterator<B>> Iterator<B> for
1376 FlatMap<'self, A, T, U> {
1378 fn next(&mut self) -> Option<B> {
1380 for inner in self.frontiter.mut_iter() {
1385 match self.iter.next().map_consume(|x| (self.f)(x)) {
1386 None => return self.backiter.chain_mut_ref(|it| it.next()),
1387 next => self.frontiter = next,
1393 fn size_hint(&self) -> (uint, Option<uint>) {
1394 let (flo, fhi) = self.frontiter.map_default((0, Some(0)), |it| it.size_hint());
1395 let (blo, bhi) = self.backiter.map_default((0, Some(0)), |it| it.size_hint());
1396 let lo = flo.saturating_add(blo);
1397 match (self.iter.size_hint(), fhi, bhi) {
1398 ((0, Some(0)), Some(a), Some(b)) => (lo, Some(a.saturating_add(b))),
1405 A, T: DoubleEndedIterator<A>,
1406 B, U: DoubleEndedIterator<B>> DoubleEndedIterator<B>
1407 for FlatMap<'self, A, T, U> {
1409 fn next_back(&mut self) -> Option<B> {
1411 for inner in self.backiter.mut_iter() {
1412 match inner.next_back() {
1417 match self.iter.next_back().map_consume(|x| (self.f)(x)) {
1418 None => return self.frontiter.chain_mut_ref(|it| it.next_back()),
1419 next => self.backiter = next,
1425 /// An iterator that calls a function with a reference to each
1426 /// element before yielding it.
1427 pub struct Peek<'self, A, T> {
1429 priv f: &'self fn(&A)
1432 impl<'self, A, T> Peek<'self, A, T> {
1434 fn do_peek(&self, elt: Option<A>) -> Option<A> {
1436 Some(ref a) => (self.f)(a),
1444 impl<'self, A, T: Iterator<A>> Iterator<A> for Peek<'self, A, T> {
1446 fn next(&mut self) -> Option<A> {
1447 let next = self.iter.next();
1452 fn size_hint(&self) -> (uint, Option<uint>) {
1453 self.iter.size_hint()
1457 impl<'self, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Peek<'self, A, T> {
1459 fn next_back(&mut self) -> Option<A> {
1460 let next = self.iter.next_back();
1465 impl<'self, A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Peek<'self, A, T> {
1467 fn indexable(&self) -> uint {
1468 self.iter.indexable()
1472 fn idx(&self, index: uint) -> Option<A> {
1473 self.do_peek(self.iter.idx(index))
1477 /// An iterator which just modifies the contained state throughout iteration.
1478 pub struct Unfoldr<'self, A, St> {
1479 priv f: &'self fn(&mut St) -> Option<A>,
1480 /// Internal state that will be yielded on the next iteration
1484 impl<'self, A, St> Unfoldr<'self, A, St> {
1485 /// Creates a new iterator with the specified closure as the "iterator
1486 /// function" and an initial state to eventually pass to the iterator
1488 pub fn new<'a>(initial_state: St, f: &'a fn(&mut St) -> Option<A>)
1489 -> Unfoldr<'a, A, St> {
1492 state: initial_state
1497 impl<'self, A, St> Iterator<A> for Unfoldr<'self, A, St> {
1499 fn next(&mut self) -> Option<A> {
1500 (self.f)(&mut self.state)
1504 /// An infinite iterator starting at `start` and advancing by `step` with each
1507 pub struct Counter<A> {
1508 /// The current state the counter is at (next value to be yielded)
1510 /// The amount that this iterator is stepping by
1514 /// Creates a new counter with the specified start/step
1516 pub fn count<A>(start: A, step: A) -> Counter<A> {
1517 Counter{state: start, step: step}
1520 /// A range of numbers from [0, N)
1521 #[deriving(Clone, DeepClone)]
1522 pub struct Range<A> {
1528 /// Return an iterator over the range [start, stop)
1530 pub fn range<A: Add<A, A> + Ord + Clone + One>(start: A, stop: A) -> Range<A> {
1531 Range{state: start, stop: stop, one: One::one()}
1534 impl<A: Add<A, A> + Ord + Clone + One> Iterator<A> for Range<A> {
1536 fn next(&mut self) -> Option<A> {
1537 if self.state < self.stop {
1538 let result = self.state.clone();
1539 self.state = self.state + self.one;
1547 impl<A: Add<A, A> + Clone> Iterator<A> for Counter<A> {
1549 fn next(&mut self) -> Option<A> {
1550 let result = self.state.clone();
1551 self.state = self.state + self.step;
1556 fn size_hint(&self) -> (uint, Option<uint>) {
1557 (uint::max_value, None) // Too bad we can't specify an infinite lower bound
1561 /// An iterator that repeats an element endlessly
1562 #[deriving(Clone, DeepClone)]
1563 pub struct Repeat<A> {
1567 impl<A: Clone> Repeat<A> {
1568 /// Create a new `Repeat` that enlessly repeats the element `elt`.
1570 pub fn new(elt: A) -> Repeat<A> {
1571 Repeat{element: elt}
1575 impl<A: Clone> Iterator<A> for Repeat<A> {
1577 fn next(&mut self) -> Option<A> { self.idx(0) }
1579 fn size_hint(&self) -> (uint, Option<uint>) { (uint::max_value, None) }
1582 impl<A: Clone> DoubleEndedIterator<A> for Repeat<A> {
1584 fn next_back(&mut self) -> Option<A> { self.idx(0) }
1587 impl<A: Clone> RandomAccessIterator<A> for Repeat<A> {
1589 fn indexable(&self) -> uint { uint::max_value }
1591 fn idx(&self, _: uint) -> Option<A> { Some(self.element.clone()) }
1603 fn test_counter_from_iter() {
1604 let mut it = count(0, 5).take_(10);
1605 let xs: ~[int] = FromIterator::from_iterator(&mut it);
1606 assert_eq!(xs, ~[0, 5, 10, 15, 20, 25, 30, 35, 40, 45]);
1610 fn test_iterator_chain() {
1611 let xs = [0u, 1, 2, 3, 4, 5];
1612 let ys = [30u, 40, 50, 60];
1613 let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
1614 let mut it = xs.iter().chain_(ys.iter());
1617 assert_eq!(x, expected[i]);
1620 assert_eq!(i, expected.len());
1622 let ys = count(30u, 10).take_(4);
1623 let mut it = xs.iter().transform(|&x| x).chain_(ys);
1626 assert_eq!(x, expected[i]);
1629 assert_eq!(i, expected.len());
1633 fn test_filter_map() {
1634 let mut it = count(0u, 1u).take_(10)
1635 .filter_map(|x| if x.is_even() { Some(x*x) } else { None });
1636 assert_eq!(it.collect::<~[uint]>(), ~[0*0, 2*2, 4*4, 6*6, 8*8]);
1640 fn test_iterator_enumerate() {
1641 let xs = [0u, 1, 2, 3, 4, 5];
1642 let mut it = xs.iter().enumerate();
1649 fn test_iterator_take_while() {
1650 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1651 let ys = [0u, 1, 2, 3, 5, 13];
1652 let mut it = xs.iter().take_while(|&x| *x < 15u);
1655 assert_eq!(x, ys[i]);
1658 assert_eq!(i, ys.len());
1662 fn test_iterator_skip_while() {
1663 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1664 let ys = [15, 16, 17, 19];
1665 let mut it = xs.iter().skip_while(|&x| *x < 15u);
1668 assert_eq!(x, ys[i]);
1671 assert_eq!(i, ys.len());
1675 fn test_iterator_skip() {
1676 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1677 let ys = [13, 15, 16, 17, 19, 20, 30];
1678 let mut it = xs.iter().skip(5);
1681 assert_eq!(x, ys[i]);
1684 assert_eq!(i, ys.len());
1688 fn test_iterator_take() {
1689 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1690 let ys = [0u, 1, 2, 3, 5];
1691 let mut it = xs.iter().take_(5);
1694 assert_eq!(x, ys[i]);
1697 assert_eq!(i, ys.len());
1701 fn test_iterator_scan() {
1702 // test the type inference
1703 fn add(old: &mut int, new: &uint) -> Option<float> {
1704 *old += *new as int;
1707 let xs = [0u, 1, 2, 3, 4];
1708 let ys = [0f, 1f, 3f, 6f, 10f];
1710 let mut it = xs.iter().scan(0, add);
1713 assert_eq!(x, ys[i]);
1716 assert_eq!(i, ys.len());
1720 fn test_iterator_flat_map() {
1721 let xs = [0u, 3, 6];
1722 let ys = [0u, 1, 2, 3, 4, 5, 6, 7, 8];
1723 let mut it = xs.iter().flat_map_(|&x| count(x, 1).take_(3));
1726 assert_eq!(x, ys[i]);
1729 assert_eq!(i, ys.len());
1734 let xs = [1u, 2, 3, 4];
1740 .collect::<~[uint]>();
1742 assert_eq!(n, xs.len());
1743 assert_eq!(xs, ys.as_slice());
1748 fn count(st: &mut uint) -> Option<uint> {
1750 let ret = Some(*st);
1758 let mut it = Unfoldr::new(0, count);
1761 assert_eq!(counted, i);
1770 let it = count(0u, 1).take_(cycle_len).cycle();
1771 assert_eq!(it.size_hint(), (uint::max_value, None));
1772 for (i, x) in it.take_(100).enumerate() {
1773 assert_eq!(i % cycle_len, x);
1776 let mut it = count(0u, 1).take_(0).cycle();
1777 assert_eq!(it.size_hint(), (0, Some(0)));
1778 assert_eq!(it.next(), None);
1782 fn test_iterator_nth() {
1783 let v = &[0, 1, 2, 3, 4];
1784 for i in range(0u, v.len()) {
1785 assert_eq!(v.iter().nth(i).unwrap(), &v[i]);
1790 fn test_iterator_last() {
1791 let v = &[0, 1, 2, 3, 4];
1792 assert_eq!(v.iter().last_().unwrap(), &4);
1793 assert_eq!(v.slice(0, 1).iter().last_().unwrap(), &0);
1797 fn test_iterator_len() {
1798 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1799 assert_eq!(v.slice(0, 4).iter().len_(), 4);
1800 assert_eq!(v.slice(0, 10).iter().len_(), 10);
1801 assert_eq!(v.slice(0, 0).iter().len_(), 0);
1805 fn test_iterator_sum() {
1806 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1807 assert_eq!(v.slice(0, 4).iter().transform(|&x| x).sum(), 6);
1808 assert_eq!(v.iter().transform(|&x| x).sum(), 55);
1809 assert_eq!(v.slice(0, 0).iter().transform(|&x| x).sum(), 0);
1813 fn test_iterator_product() {
1814 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1815 assert_eq!(v.slice(0, 4).iter().transform(|&x| x).product(), 0);
1816 assert_eq!(v.slice(1, 5).iter().transform(|&x| x).product(), 24);
1817 assert_eq!(v.slice(0, 0).iter().transform(|&x| x).product(), 1);
1821 fn test_iterator_max() {
1822 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1823 assert_eq!(v.slice(0, 4).iter().transform(|&x| x).max(), Some(3));
1824 assert_eq!(v.iter().transform(|&x| x).max(), Some(10));
1825 assert_eq!(v.slice(0, 0).iter().transform(|&x| x).max(), None);
1829 fn test_iterator_min() {
1830 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1831 assert_eq!(v.slice(0, 4).iter().transform(|&x| x).min(), Some(0));
1832 assert_eq!(v.iter().transform(|&x| x).min(), Some(0));
1833 assert_eq!(v.slice(0, 0).iter().transform(|&x| x).min(), None);
1837 fn test_iterator_size_hint() {
1838 let c = count(0, 1);
1839 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
1840 let v2 = &[10, 11, 12];
1843 assert_eq!(c.size_hint(), (uint::max_value, None));
1844 assert_eq!(vi.size_hint(), (10, Some(10)));
1846 assert_eq!(c.take_(5).size_hint(), (5, Some(5)));
1847 assert_eq!(c.skip(5).size_hint().second(), None);
1848 assert_eq!(c.take_while(|_| false).size_hint(), (0, None));
1849 assert_eq!(c.skip_while(|_| false).size_hint(), (0, None));
1850 assert_eq!(c.enumerate().size_hint(), (uint::max_value, None));
1851 assert_eq!(c.chain_(vi.transform(|&i| i)).size_hint(), (uint::max_value, None));
1852 assert_eq!(c.zip(vi).size_hint(), (10, Some(10)));
1853 assert_eq!(c.scan(0, |_,_| Some(0)).size_hint(), (0, None));
1854 assert_eq!(c.filter(|_| false).size_hint(), (0, None));
1855 assert_eq!(c.transform(|_| 0).size_hint(), (uint::max_value, None));
1856 assert_eq!(c.filter_map(|_| Some(0)).size_hint(), (0, None));
1858 assert_eq!(vi.take_(5).size_hint(), (5, Some(5)));
1859 assert_eq!(vi.take_(12).size_hint(), (10, Some(10)));
1860 assert_eq!(vi.skip(3).size_hint(), (7, Some(7)));
1861 assert_eq!(vi.skip(12).size_hint(), (0, Some(0)));
1862 assert_eq!(vi.take_while(|_| false).size_hint(), (0, Some(10)));
1863 assert_eq!(vi.skip_while(|_| false).size_hint(), (0, Some(10)));
1864 assert_eq!(vi.enumerate().size_hint(), (10, Some(10)));
1865 assert_eq!(vi.chain_(v2.iter()).size_hint(), (13, Some(13)));
1866 assert_eq!(vi.zip(v2.iter()).size_hint(), (3, Some(3)));
1867 assert_eq!(vi.scan(0, |_,_| Some(0)).size_hint(), (0, Some(10)));
1868 assert_eq!(vi.filter(|_| false).size_hint(), (0, Some(10)));
1869 assert_eq!(vi.transform(|i| i+1).size_hint(), (10, Some(10)));
1870 assert_eq!(vi.filter_map(|_| Some(0)).size_hint(), (0, Some(10)));
1875 let a = ~[1, 2, 3, 4, 5];
1876 let b: ~[int] = a.iter().transform(|&x| x).collect();
1882 let v = ~&[1, 2, 3, 4, 5];
1883 assert!(v.iter().all(|&x| x < 10));
1884 assert!(!v.iter().all(|&x| x.is_even()));
1885 assert!(!v.iter().all(|&x| x > 100));
1886 assert!(v.slice(0, 0).iter().all(|_| fail!()));
1891 let v = ~&[1, 2, 3, 4, 5];
1892 assert!(v.iter().any(|&x| x < 10));
1893 assert!(v.iter().any(|&x| x.is_even()));
1894 assert!(!v.iter().any(|&x| x > 100));
1895 assert!(!v.slice(0, 0).iter().any(|_| fail!()));
1900 let v = &[1, 3, 9, 27, 103, 14, 11];
1901 assert_eq!(*v.iter().find_(|x| *x & 1 == 0).unwrap(), 14);
1902 assert_eq!(*v.iter().find_(|x| *x % 3 == 0).unwrap(), 3);
1903 assert!(v.iter().find_(|x| *x % 12 == 0).is_none());
1907 fn test_position() {
1908 let v = &[1, 3, 9, 27, 103, 14, 11];
1909 assert_eq!(v.iter().position(|x| *x & 1 == 0).unwrap(), 5);
1910 assert_eq!(v.iter().position(|x| *x % 3 == 0).unwrap(), 1);
1911 assert!(v.iter().position(|x| *x % 12 == 0).is_none());
1916 let xs = &[1, 2, 2, 1, 5, 9, 0, 2];
1917 assert_eq!(xs.iter().count(|x| *x == 2), 3);
1918 assert_eq!(xs.iter().count(|x| *x == 5), 1);
1919 assert_eq!(xs.iter().count(|x| *x == 95), 0);
1924 let xs = [-3, 0, 1, 5, -10];
1925 assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
1930 let xs = [-3, 0, 1, 5, -10];
1931 assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
1936 let xs = [2, 4, 6, 8, 10, 12, 14, 16];
1937 let mut it = xs.iter();
1940 assert_eq!(it.invert().transform(|&x| x).collect::<~[int]>(), ~[16, 14, 12, 10, 8, 6]);
1944 fn test_double_ended_map() {
1945 let xs = [1, 2, 3, 4, 5, 6];
1946 let mut it = xs.iter().transform(|&x| x * -1);
1947 assert_eq!(it.next(), Some(-1));
1948 assert_eq!(it.next(), Some(-2));
1949 assert_eq!(it.next_back(), Some(-6));
1950 assert_eq!(it.next_back(), Some(-5));
1951 assert_eq!(it.next(), Some(-3));
1952 assert_eq!(it.next_back(), Some(-4));
1953 assert_eq!(it.next(), None);
1957 fn test_double_ended_filter() {
1958 let xs = [1, 2, 3, 4, 5, 6];
1959 let mut it = xs.iter().filter(|&x| *x & 1 == 0);
1960 assert_eq!(it.next_back().unwrap(), &6);
1961 assert_eq!(it.next_back().unwrap(), &4);
1962 assert_eq!(it.next().unwrap(), &2);
1963 assert_eq!(it.next_back(), None);
1967 fn test_double_ended_filter_map() {
1968 let xs = [1, 2, 3, 4, 5, 6];
1969 let mut it = xs.iter().filter_map(|&x| if x & 1 == 0 { Some(x * 2) } else { None });
1970 assert_eq!(it.next_back().unwrap(), 12);
1971 assert_eq!(it.next_back().unwrap(), 8);
1972 assert_eq!(it.next().unwrap(), 4);
1973 assert_eq!(it.next_back(), None);
1977 fn test_double_ended_chain() {
1978 let xs = [1, 2, 3, 4, 5];
1979 let ys = ~[7, 9, 11];
1980 let mut it = xs.iter().chain_(ys.iter()).invert();
1981 assert_eq!(it.next().unwrap(), &11)
1982 assert_eq!(it.next().unwrap(), &9)
1983 assert_eq!(it.next_back().unwrap(), &1)
1984 assert_eq!(it.next_back().unwrap(), &2)
1985 assert_eq!(it.next_back().unwrap(), &3)
1986 assert_eq!(it.next_back().unwrap(), &4)
1987 assert_eq!(it.next_back().unwrap(), &5)
1988 assert_eq!(it.next_back().unwrap(), &7)
1989 assert_eq!(it.next_back(), None)
1993 fn check_randacc_iter<A: Eq, T: Clone + RandomAccessIterator<A>>(a: T, len: uint)
1995 let mut b = a.clone();
1996 assert_eq!(len, b.indexable());
1998 for (i, elt) in a.enumerate() {
1999 assert_eq!(Some(elt), b.idx(i));
2003 assert_eq!(None, b.idx(n));
2004 // call recursively to check after picking off an element
2007 check_randacc_iter(b, len-1);
2013 fn test_double_ended_flat_map() {
2016 let mut it = u.iter().flat_map_(|x| v.slice(*x, v.len()).iter());
2017 assert_eq!(it.next_back().unwrap(), &8);
2018 assert_eq!(it.next().unwrap(), &5);
2019 assert_eq!(it.next_back().unwrap(), &7);
2020 assert_eq!(it.next_back().unwrap(), &6);
2021 assert_eq!(it.next_back().unwrap(), &8);
2022 assert_eq!(it.next().unwrap(), &6);
2023 assert_eq!(it.next_back().unwrap(), &7);
2024 assert_eq!(it.next_back(), None);
2025 assert_eq!(it.next(), None);
2026 assert_eq!(it.next_back(), None);
2030 fn test_random_access_chain() {
2031 let xs = [1, 2, 3, 4, 5];
2032 let ys = ~[7, 9, 11];
2033 let mut it = xs.iter().chain_(ys.iter());
2034 assert_eq!(it.idx(0).unwrap(), &1);
2035 assert_eq!(it.idx(5).unwrap(), &7);
2036 assert_eq!(it.idx(7).unwrap(), &11);
2037 assert!(it.idx(8).is_none());
2043 assert_eq!(it.idx(0).unwrap(), &3);
2044 assert_eq!(it.idx(4).unwrap(), &9);
2045 assert!(it.idx(6).is_none());
2047 check_randacc_iter(it, xs.len() + ys.len() - 3);
2051 fn test_random_access_enumerate() {
2052 let xs = [1, 2, 3, 4, 5];
2053 check_randacc_iter(xs.iter().enumerate(), xs.len());
2057 fn test_random_access_invert() {
2058 let xs = [1, 2, 3, 4, 5];
2059 check_randacc_iter(xs.iter().invert(), xs.len());
2060 let mut it = xs.iter().invert();
2064 check_randacc_iter(it, xs.len() - 3);
2068 fn test_random_access_zip() {
2069 let xs = [1, 2, 3, 4, 5];
2070 let ys = [7, 9, 11];
2071 check_randacc_iter(xs.iter().zip(ys.iter()), cmp::min(xs.len(), ys.len()));
2075 fn test_random_access_take() {
2076 let xs = [1, 2, 3, 4, 5];
2077 let empty: &[int] = [];
2078 check_randacc_iter(xs.iter().take_(3), 3);
2079 check_randacc_iter(xs.iter().take_(20), xs.len());
2080 check_randacc_iter(xs.iter().take_(0), 0);
2081 check_randacc_iter(empty.iter().take_(2), 0);
2085 fn test_random_access_skip() {
2086 let xs = [1, 2, 3, 4, 5];
2087 let empty: &[int] = [];
2088 check_randacc_iter(xs.iter().skip(2), xs.len() - 2);
2089 check_randacc_iter(empty.iter().skip(2), 0);
2093 fn test_random_access_peek() {
2094 let xs = [1, 2, 3, 4, 5];
2096 // test .transform and .peek_ that don't implement Clone
2097 let it = xs.iter().peek_(|_| {});
2098 assert_eq!(xs.len(), it.indexable());
2099 for (i, elt) in xs.iter().enumerate() {
2100 assert_eq!(Some(elt), it.idx(i));
2106 fn test_random_access_transform() {
2107 let xs = [1, 2, 3, 4, 5];
2109 // test .transform and .peek_ that don't implement Clone
2110 let it = xs.iter().transform(|x| *x);
2111 assert_eq!(xs.len(), it.indexable());
2112 for (i, elt) in xs.iter().enumerate() {
2113 assert_eq!(Some(*elt), it.idx(i));
2118 fn test_random_access_cycle() {
2119 let xs = [1, 2, 3, 4, 5];
2120 let empty: &[int] = [];
2121 check_randacc_iter(xs.iter().cycle().take_(27), 27);
2122 check_randacc_iter(empty.iter().cycle(), 0);