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.
20 #[allow(default_methods)]; // still off by default in stage0
25 use option::{Option, Some, None};
31 /// Conversion from an `Iterator`
32 pub trait FromIterator<A, T: Iterator<A>> {
33 /// Build a container with elements from an external iterator.
34 pub fn from_iterator(iterator: &mut T) -> Self;
37 /// An interface for dealing with "external iterators". These types of iterators
38 /// can be resumed at any time as all state is stored internally as opposed to
39 /// being located on the call stack.
40 pub trait Iterator<A> {
41 /// Advance the iterator and return the next value. Return `None` when the end is reached.
42 fn next(&mut self) -> Option<A>;
44 /// Return a lower bound and upper bound on the remaining length of the iterator.
46 /// The common use case for the estimate is pre-allocating space to store the results.
47 fn size_hint(&self) -> (uint, Option<uint>) { (0, None) }
50 /// A range iterator able to yield elements from both ends
51 pub trait DoubleEndedIterator<A>: Iterator<A> {
52 /// Yield an element from the end of the range, returning `None` if the range is empty.
53 fn next_back(&mut self) -> Option<A>;
56 /// An object implementing random access indexing by `uint`
57 pub trait RandomAccessIterator<A> {
58 /// Return the number of indexable elements. At most `std::uint::max_value`
59 /// elements are indexable, even if the iterator represents a longer range.
60 fn indexable(&self) -> uint;
62 /// Return an element at an index
63 fn idx(&self, index: uint) -> Option<A>;
66 /// Iterator adaptors provided for every `DoubleEndedIterator` implementation.
68 /// In the future these will be default methods instead of a utility trait.
69 pub trait DoubleEndedIteratorUtil<A> {
70 /// Flip the direction of the iterator
71 fn invert(self) -> InvertIterator<A, Self>;
74 /// Iterator adaptors provided for every `DoubleEndedIterator` implementation.
76 /// In the future these will be default methods instead of a utility trait.
77 impl<A, T: DoubleEndedIterator<A>> DoubleEndedIteratorUtil<A> for T {
78 /// Flip the direction of the iterator
80 fn invert(self) -> InvertIterator<A, T> {
81 InvertIterator{iter: self}
85 /// An double-ended iterator with the direction inverted
86 // FIXME #6967: Dummy A parameter to get around type inference bug
88 pub struct InvertIterator<A, T> {
92 impl<A, T: DoubleEndedIterator<A>> Iterator<A> for InvertIterator<A, T> {
94 fn next(&mut self) -> Option<A> { self.iter.next_back() }
96 fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
99 impl<A, T: Iterator<A>> DoubleEndedIterator<A> for InvertIterator<A, T> {
101 fn next_back(&mut self) -> Option<A> { self.iter.next() }
104 /// Iterator adaptors provided for every `Iterator` implementation. The adaptor objects are also
105 /// implementations of the `Iterator` trait.
107 /// In the future these will be default methods instead of a utility trait.
108 pub trait IteratorUtil<A> {
109 /// Chain this iterator with another, returning a new iterator which will
110 /// finish iterating over the current iterator, and then it will iterate
111 /// over the other specified iterator.
118 /// let mut it = a.iter().chain_(b.iter());
119 /// assert_eq!(it.next().get(), &0);
120 /// assert_eq!(it.next().get(), &1);
121 /// assert!(it.next().is_none());
123 fn chain_<U: Iterator<A>>(self, other: U) -> ChainIterator<A, Self, U>;
125 /// Creates an iterator which iterates over both this and the specified
126 /// iterators simultaneously, yielding the two elements as pairs. When
127 /// either iterator returns None, all further invocations of next() will
135 /// let mut it = a.iter().zip(b.iter());
136 /// assert_eq!(it.next().get(), (&0, &1));
137 /// assert!(it.next().is_none());
139 fn zip<B, U: Iterator<B>>(self, other: U) -> ZipIterator<A, Self, B, U>;
141 // FIXME: #5898: should be called map
142 /// Creates a new iterator which will apply the specified function to each
143 /// element returned by the first, yielding the mapped element instead.
149 /// let mut it = a.iter().transform(|&x| 2 * x);
150 /// assert_eq!(it.next().get(), 2);
151 /// assert_eq!(it.next().get(), 4);
152 /// assert!(it.next().is_none());
154 fn transform<'r, B>(self, f: &'r fn(A) -> B) -> MapIterator<'r, A, B, Self>;
156 /// Creates an iterator which applies the predicate to each element returned
157 /// by this iterator. Only elements which have the predicate evaluate to
158 /// `true` will be yielded.
164 /// let mut it = a.iter().filter(|&x| *x > 1);
165 /// assert_eq!(it.next().get(), &2);
166 /// assert!(it.next().is_none());
168 fn filter<'r>(self, predicate: &'r fn(&A) -> bool) -> FilterIterator<'r, A, Self>;
170 /// Creates an iterator which both filters and maps elements.
171 /// If the specified function returns None, the element is skipped.
172 /// Otherwise the option is unwrapped and the new value is yielded.
178 /// let mut it = a.iter().filter_map(|&x| if x > 1 {Some(2 * x)} else {None});
179 /// assert_eq!(it.next().get(), 4);
180 /// assert!(it.next().is_none());
182 fn filter_map<'r, B>(self, f: &'r fn(A) -> Option<B>) -> FilterMapIterator<'r, A, B, Self>;
184 /// Creates an iterator which yields a pair of the value returned by this
185 /// iterator plus the current index of iteration.
190 /// let a = [100, 200];
191 /// let mut it = a.iter().enumerate();
192 /// assert_eq!(it.next().get(), (0, &100));
193 /// assert_eq!(it.next().get(), (1, &200));
194 /// assert!(it.next().is_none());
196 fn enumerate(self) -> EnumerateIterator<A, Self>;
198 /// Creates an iterator which invokes the predicate on elements until it
199 /// returns false. Once the predicate returns false, all further elements are
205 /// let a = [1, 2, 3, 2, 1];
206 /// let mut it = a.iter().skip_while(|&a| *a < 3);
207 /// assert_eq!(it.next().get(), &3);
208 /// assert_eq!(it.next().get(), &2);
209 /// assert_eq!(it.next().get(), &1);
210 /// assert!(it.next().is_none());
212 fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) -> SkipWhileIterator<'r, A, Self>;
214 /// Creates an iterator which yields elements so long as the predicate
215 /// returns true. After the predicate returns false for the first time, no
216 /// further elements will be yielded.
221 /// let a = [1, 2, 3, 2, 1];
222 /// let mut it = a.iter().take_while(|&a| *a < 3);
223 /// assert_eq!(it.next().get(), &1);
224 /// assert_eq!(it.next().get(), &2);
225 /// assert!(it.next().is_none());
227 fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) -> TakeWhileIterator<'r, A, Self>;
229 /// Creates an iterator which skips the first `n` elements of this iterator,
230 /// and then it yields all further items.
235 /// let a = [1, 2, 3, 4, 5];
236 /// let mut it = a.iter().skip(3);
237 /// assert_eq!(it.next().get(), &4);
238 /// assert_eq!(it.next().get(), &5);
239 /// assert!(it.next().is_none());
241 fn skip(self, n: uint) -> SkipIterator<A, Self>;
243 // FIXME: #5898: should be called take
244 /// Creates an iterator which yields the first `n` elements of this
245 /// iterator, and then it will always return None.
250 /// let a = [1, 2, 3, 4, 5];
251 /// let mut it = a.iter().take_(3);
252 /// assert_eq!(it.next().get(), &1);
253 /// assert_eq!(it.next().get(), &2);
254 /// assert_eq!(it.next().get(), &3);
255 /// assert!(it.next().is_none());
257 fn take_(self, n: uint) -> TakeIterator<A, Self>;
259 /// Creates a new iterator which behaves in a similar fashion to foldl.
260 /// There is a state which is passed between each iteration and can be
261 /// mutated as necessary. The yielded values from the closure are yielded
262 /// from the ScanIterator instance when not None.
267 /// let a = [1, 2, 3, 4, 5];
268 /// let mut it = a.iter().scan(1, |fac, &x| {
272 /// assert_eq!(it.next().get(), 1);
273 /// assert_eq!(it.next().get(), 2);
274 /// assert_eq!(it.next().get(), 6);
275 /// assert_eq!(it.next().get(), 24);
276 /// assert_eq!(it.next().get(), 120);
277 /// assert!(it.next().is_none());
279 fn scan<'r, St, B>(self, initial_state: St, f: &'r fn(&mut St, A) -> Option<B>)
280 -> ScanIterator<'r, A, B, Self, St>;
282 /// Creates an iterator that maps each element to an iterator,
283 /// and yields the elements of the produced iterators
288 /// let xs = [2u, 3];
289 /// let ys = [0u, 1, 0, 1, 2];
290 /// let mut it = xs.iter().flat_map_(|&x| Counter::new(0u, 1).take_(x));
291 /// // Check that `it` has the same elements as `ys`
293 /// for it.advance |x: uint| {
294 /// assert_eq!(x, ys[i]);
298 // FIXME: #5898: should be called `flat_map`
299 fn flat_map_<'r, B, U: Iterator<B>>(self, f: &'r fn(A) -> U)
300 -> FlatMapIterator<'r, A, B, Self, U>;
302 /// Creates an iterator that calls a function with a reference to each
303 /// element before yielding it. This is often useful for debugging an
304 /// iterator pipeline.
309 ///let xs = [1u, 4, 2, 3, 8, 9, 6];
310 ///let sum = xs.iter()
311 /// .transform(|&x| x)
312 /// .peek_(|&x| debug!("filtering %u", x))
313 /// .filter(|&x| x % 2 == 0)
314 /// .peek_(|&x| debug!("%u made it through", x))
316 ///println(sum.to_str());
318 // FIXME: #5898: should be called `peek`
319 fn peek_<'r>(self, f: &'r fn(&A)) -> PeekIterator<'r, A, Self>;
321 /// An adaptation of an external iterator to the for-loop protocol of rust.
326 /// use std::iterator::Counter;
328 /// for Counter::new(0, 10).advance |i| {
329 /// io::println(fmt!("%d", i));
332 fn advance(&mut self, f: &fn(A) -> bool) -> bool;
334 /// Loops through the entire iterator, collecting all of the elements into
335 /// a container implementing `FromIterator`.
340 /// let a = [1, 2, 3, 4, 5];
341 /// let b: ~[int] = a.iter().transform(|&x| x).collect();
344 fn collect<B: FromIterator<A, Self>>(&mut self) -> B;
346 /// Loops through `n` iterations, returning the `n`th element of the
352 /// let a = [1, 2, 3, 4, 5];
353 /// let mut it = a.iter();
354 /// assert!(it.nth(2).get() == &3);
355 /// assert!(it.nth(2) == None);
357 fn nth(&mut self, n: uint) -> Option<A>;
359 /// Loops through the entire iterator, returning the last element of the
365 /// let a = [1, 2, 3, 4, 5];
366 /// assert!(a.iter().last().get() == &5);
368 // FIXME: #5898: should be called `last`
369 fn last_(&mut self) -> Option<A>;
371 /// Performs a fold operation over the entire iterator, returning the
372 /// eventual state at the end of the iteration.
377 /// let a = [1, 2, 3, 4, 5];
378 /// assert!(a.iter().fold(0, |a, &b| a + b) == 15);
380 fn fold<B>(&mut self, start: B, f: &fn(B, A) -> B) -> B;
382 // FIXME: #5898: should be called len
383 /// Counts the number of elements in this iterator.
388 /// let a = [1, 2, 3, 4, 5];
389 /// let mut it = a.iter();
390 /// assert!(it.len_() == 5);
391 /// assert!(it.len_() == 0);
393 fn len_(&mut self) -> uint;
395 /// Tests whether the predicate holds true for all elements in the iterator.
400 /// let a = [1, 2, 3, 4, 5];
401 /// assert!(a.iter().all(|&x| *x > 0));
402 /// assert!(!a.iter().all(|&x| *x > 2));
404 fn all(&mut self, f: &fn(A) -> bool) -> bool;
406 /// Tests whether any element of an iterator satisfies the specified
412 /// let a = [1, 2, 3, 4, 5];
413 /// let mut it = a.iter();
414 /// assert!(it.any(|&x| *x == 3));
415 /// assert!(!it.any(|&x| *x == 3));
417 fn any(&mut self, f: &fn(A) -> bool) -> bool;
419 /// Return the first element satisfying the specified predicate
420 fn find_(&mut self, predicate: &fn(&A) -> bool) -> Option<A>;
422 /// Return the index of the first element satisfying the specified predicate
423 fn position(&mut self, predicate: &fn(A) -> bool) -> Option<uint>;
425 /// Count the number of elements satisfying the specified predicate
426 fn count(&mut self, predicate: &fn(A) -> bool) -> uint;
428 /// Return the element that gives the maximum value from the specfied function
433 /// let xs = [-3, 0, 1, 5, -10];
434 /// assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
436 fn max_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A>;
438 /// Return the element that gives the minimum value from the specfied function
443 /// let xs = [-3, 0, 1, 5, -10];
444 /// assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
446 fn min_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A>;
449 /// Iterator adaptors provided for every `Iterator` implementation. The adaptor objects are also
450 /// implementations of the `Iterator` trait.
452 /// In the future these will be default methods instead of a utility trait.
453 impl<A, T: Iterator<A>> IteratorUtil<A> for T {
455 fn chain_<U: Iterator<A>>(self, other: U) -> ChainIterator<A, T, U> {
456 ChainIterator{a: self, b: other, flag: false}
460 fn zip<B, U: Iterator<B>>(self, other: U) -> ZipIterator<A, T, B, U> {
461 ZipIterator{a: self, b: other}
464 // FIXME: #5898: should be called map
466 fn transform<'r, B>(self, f: &'r fn(A) -> B) -> MapIterator<'r, A, B, T> {
467 MapIterator{iter: self, f: f}
471 fn filter<'r>(self, predicate: &'r fn(&A) -> bool) -> FilterIterator<'r, A, T> {
472 FilterIterator{iter: self, predicate: predicate}
476 fn filter_map<'r, B>(self, f: &'r fn(A) -> Option<B>) -> FilterMapIterator<'r, A, B, T> {
477 FilterMapIterator { iter: self, f: f }
481 fn enumerate(self) -> EnumerateIterator<A, T> {
482 EnumerateIterator{iter: self, count: 0}
486 fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) -> SkipWhileIterator<'r, A, T> {
487 SkipWhileIterator{iter: self, flag: false, predicate: predicate}
491 fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) -> TakeWhileIterator<'r, A, T> {
492 TakeWhileIterator{iter: self, flag: false, predicate: predicate}
496 fn skip(self, n: uint) -> SkipIterator<A, T> {
497 SkipIterator{iter: self, n: n}
500 // FIXME: #5898: should be called take
502 fn take_(self, n: uint) -> TakeIterator<A, T> {
503 TakeIterator{iter: self, n: n}
507 fn scan<'r, St, B>(self, initial_state: St, f: &'r fn(&mut St, A) -> Option<B>)
508 -> ScanIterator<'r, A, B, T, St> {
509 ScanIterator{iter: self, f: f, state: initial_state}
513 fn flat_map_<'r, B, U: Iterator<B>>(self, f: &'r fn(A) -> U)
514 -> FlatMapIterator<'r, A, B, T, U> {
515 FlatMapIterator{iter: self, f: f, subiter: None }
518 // FIXME: #5898: should be called `peek`
520 fn peek_<'r>(self, f: &'r fn(&A)) -> PeekIterator<'r, A, T> {
521 PeekIterator{iter: self, f: f}
524 /// A shim implementing the `for` loop iteration protocol for iterator objects
526 fn advance(&mut self, f: &fn(A) -> bool) -> bool {
530 if !f(x) { return false; }
532 None => { return true; }
538 fn collect<B: FromIterator<A, T>>(&mut self) -> B {
539 FromIterator::from_iterator(self)
542 /// Return the `n`th item yielded by an iterator.
544 fn nth(&mut self, mut n: uint) -> Option<A> {
547 Some(x) => if n == 0 { return Some(x) },
554 /// Return the last item yielded by an iterator.
556 fn last_(&mut self) -> Option<A> {
558 for self.advance |x| { last = Some(x); }
562 /// Reduce an iterator to an accumulated value
564 fn fold<B>(&mut self, init: B, f: &fn(B, A) -> B) -> B {
565 let mut accum = init;
568 Some(x) => { accum = f(accum, x); }
575 /// Count the number of items yielded by an iterator
577 fn len_(&mut self) -> uint { self.fold(0, |cnt, _x| cnt + 1) }
580 fn all(&mut self, f: &fn(A) -> bool) -> bool {
581 for self.advance |x| { if !f(x) { return false; } }
586 fn any(&mut self, f: &fn(A) -> bool) -> bool {
587 for self.advance |x| { if f(x) { return true; } }
591 /// Return the first element satisfying the specified predicate
593 fn find_(&mut self, predicate: &fn(&A) -> bool) -> Option<A> {
594 for self.advance |x| {
595 if predicate(&x) { return Some(x) }
600 /// Return the index of the first element satisfying the specified predicate
602 fn position(&mut self, predicate: &fn(A) -> bool) -> Option<uint> {
604 for self.advance |x| {
614 fn count(&mut self, predicate: &fn(A) -> bool) -> uint {
616 for self.advance |x| {
617 if predicate(x) { i += 1 }
623 fn max_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A> {
624 self.fold(None, |max: Option<(A, B)>, x| {
627 None => Some((x, x_val)),
628 Some((y, y_val)) => if x_val > y_val {
634 }).map_consume(|(x, _)| x)
638 fn min_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A> {
639 self.fold(None, |min: Option<(A, B)>, x| {
642 None => Some((x, x_val)),
643 Some((y, y_val)) => if x_val < y_val {
649 }).map_consume(|(x, _)| x)
653 /// A trait for iterators over elements which can be added together
654 pub trait AdditiveIterator<A> {
655 /// Iterates over the entire iterator, summing up all the elements
660 /// let a = [1, 2, 3, 4, 5];
661 /// let mut it = a.iter().transform(|&x| x);
662 /// assert!(it.sum() == 15);
664 fn sum(&mut self) -> A;
667 impl<A: Add<A, A> + Zero, T: Iterator<A>> AdditiveIterator<A> for T {
669 fn sum(&mut self) -> A { self.fold(Zero::zero::<A>(), |s, x| s + x) }
672 /// A trait for iterators over elements whose elements can be multiplied
674 pub trait MultiplicativeIterator<A> {
675 /// Iterates over the entire iterator, multiplying all the elements
680 /// use std::iterator::Counter;
682 /// fn factorial(n: uint) -> uint {
683 /// Counter::new(1u, 1).take_while(|&i| i <= n).product()
685 /// assert!(factorial(0) == 1);
686 /// assert!(factorial(1) == 1);
687 /// assert!(factorial(5) == 120);
689 fn product(&mut self) -> A;
692 impl<A: Mul<A, A> + One, T: Iterator<A>> MultiplicativeIterator<A> for T {
694 fn product(&mut self) -> A { self.fold(One::one::<A>(), |p, x| p * x) }
697 /// A trait for iterators over elements which can be compared to one another.
698 /// The type of each element must ascribe to the `Ord` trait.
699 pub trait OrdIterator<A> {
700 /// Consumes the entire iterator to return the maximum element.
705 /// let a = [1, 2, 3, 4, 5];
706 /// assert!(a.iter().max().get() == &5);
708 fn max(&mut self) -> Option<A>;
710 /// Consumes the entire iterator to return the minimum element.
715 /// let a = [1, 2, 3, 4, 5];
716 /// assert!(a.iter().min().get() == &1);
718 fn min(&mut self) -> Option<A>;
721 impl<A: Ord, T: Iterator<A>> OrdIterator<A> for T {
723 fn max(&mut self) -> Option<A> {
724 self.fold(None, |max, x| {
727 Some(y) => Some(cmp::max(x, y))
733 fn min(&mut self) -> Option<A> {
734 self.fold(None, |min, x| {
737 Some(y) => Some(cmp::min(x, y))
743 /// A trait for iterators that are clonable.
744 // FIXME #6967: Dummy A parameter to get around type inference bug
745 pub trait ClonableIterator<A> {
746 /// Repeats an iterator endlessly
751 /// let a = Counter::new(1,1).take_(1);
752 /// let mut cy = a.cycle();
753 /// assert_eq!(cy.next(), Some(1));
754 /// assert_eq!(cy.next(), Some(1));
756 fn cycle(self) -> CycleIterator<A, Self>;
759 impl<A, T: Clone + Iterator<A>> ClonableIterator<A> for T {
761 fn cycle(self) -> CycleIterator<A, T> {
762 CycleIterator{orig: self.clone(), iter: self}
766 /// An iterator that repeats endlessly
768 pub struct CycleIterator<A, T> {
773 impl<A, T: Clone + Iterator<A>> Iterator<A> for CycleIterator<A, T> {
775 fn next(&mut self) -> Option<A> {
776 match self.iter.next() {
777 None => { self.iter = self.orig.clone(); self.iter.next() }
783 fn size_hint(&self) -> (uint, Option<uint>) {
784 // the cycle iterator is either empty or infinite
785 match self.orig.size_hint() {
786 sz @ (0, Some(0)) => sz,
788 _ => (uint::max_value, None)
793 /// An iterator which strings two iterators together
794 // FIXME #6967: Dummy A parameter to get around type inference bug
796 pub struct ChainIterator<A, T, U> {
802 impl<A, T: Iterator<A>, U: Iterator<A>> Iterator<A> for ChainIterator<A, T, U> {
804 fn next(&mut self) -> Option<A> {
808 match self.a.next() {
809 Some(x) => return Some(x),
818 fn size_hint(&self) -> (uint, Option<uint>) {
819 let (a_lower, a_upper) = self.a.size_hint();
820 let (b_lower, b_upper) = self.b.size_hint();
822 let lower = if uint::max_value - a_lower < b_lower {
828 let upper = match (a_upper, b_upper) {
829 (Some(x), Some(y)) if uint::max_value - x < y => Some(uint::max_value),
830 (Some(x), Some(y)) => Some(x + y),
838 impl<A, T: DoubleEndedIterator<A>, U: DoubleEndedIterator<A>> DoubleEndedIterator<A>
839 for ChainIterator<A, T, U> {
841 fn next_back(&mut self) -> Option<A> {
842 match self.b.next_back() {
844 None => self.a.next_back()
849 impl<A, T: RandomAccessIterator<A>, U: RandomAccessIterator<A>> RandomAccessIterator<A>
850 for ChainIterator<A, T, U> {
852 fn indexable(&self) -> uint {
853 let (a, b) = (self.a.indexable(), self.b.indexable());
855 if total < a || total < b {
863 fn idx(&self, index: uint) -> Option<A> {
864 let len = self.a.indexable();
868 self.b.idx(index - len)
873 /// An iterator which iterates two other iterators simultaneously
874 // FIXME #6967: Dummy A & B parameters to get around type inference bug
876 pub struct ZipIterator<A, T, B, U> {
881 impl<A, B, T: Iterator<A>, U: Iterator<B>> Iterator<(A, B)> for ZipIterator<A, T, B, U> {
883 fn next(&mut self) -> Option<(A, B)> {
884 match (self.a.next(), self.b.next()) {
885 (Some(x), Some(y)) => Some((x, y)),
891 fn size_hint(&self) -> (uint, Option<uint>) {
892 let (a_lower, a_upper) = self.a.size_hint();
893 let (b_lower, b_upper) = self.b.size_hint();
895 let lower = cmp::min(a_lower, b_lower);
897 let upper = match (a_upper, b_upper) {
898 (Some(x), Some(y)) => Some(cmp::min(x,y)),
899 (Some(x), None) => Some(x),
900 (None, Some(y)) => Some(y),
908 /// An iterator which maps the values of `iter` with `f`
909 pub struct MapIterator<'self, A, B, T> {
911 priv f: &'self fn(A) -> B
914 impl<'self, A, B, T: Iterator<A>> Iterator<B> for MapIterator<'self, A, B, T> {
916 fn next(&mut self) -> Option<B> {
917 match self.iter.next() {
918 Some(a) => Some((self.f)(a)),
924 fn size_hint(&self) -> (uint, Option<uint>) {
925 self.iter.size_hint()
929 impl<'self, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B>
930 for MapIterator<'self, A, B, T> {
932 fn next_back(&mut self) -> Option<B> {
933 match self.iter.next_back() {
934 Some(a) => Some((self.f)(a)),
940 /// An iterator which filters the elements of `iter` with `predicate`
941 pub struct FilterIterator<'self, A, T> {
943 priv predicate: &'self fn(&A) -> bool
946 impl<'self, A, T: Iterator<A>> Iterator<A> for FilterIterator<'self, A, T> {
948 fn next(&mut self) -> Option<A> {
949 for self.iter.advance |x| {
950 if (self.predicate)(&x) {
960 fn size_hint(&self) -> (uint, Option<uint>) {
961 let (_, upper) = self.iter.size_hint();
962 (0, upper) // can't know a lower bound, due to the predicate
966 impl<'self, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for FilterIterator<'self, A, T> {
968 fn next_back(&mut self) -> Option<A> {
970 match self.iter.next_back() {
973 if (self.predicate)(&x) {
984 /// An iterator which uses `f` to both filter and map elements from `iter`
985 pub struct FilterMapIterator<'self, A, B, T> {
987 priv f: &'self fn(A) -> Option<B>
990 impl<'self, A, B, T: Iterator<A>> Iterator<B> for FilterMapIterator<'self, A, B, T> {
992 fn next(&mut self) -> Option<B> {
993 for self.iter.advance |x| {
995 Some(y) => return Some(y),
1003 fn size_hint(&self) -> (uint, Option<uint>) {
1004 let (_, upper) = self.iter.size_hint();
1005 (0, upper) // can't know a lower bound, due to the predicate
1009 impl<'self, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B>
1010 for FilterMapIterator<'self, A, B, T> {
1012 fn next_back(&mut self) -> Option<B> {
1014 match self.iter.next_back() {
1015 None => return None,
1018 Some(y) => return Some(y),
1027 /// An iterator which yields the current count and the element during iteration
1028 // FIXME #6967: Dummy A parameter to get around type inference bug
1030 pub struct EnumerateIterator<A, T> {
1035 impl<A, T: Iterator<A>> Iterator<(uint, A)> for EnumerateIterator<A, T> {
1037 fn next(&mut self) -> Option<(uint, A)> {
1038 match self.iter.next() {
1040 let ret = Some((self.count, a));
1049 fn size_hint(&self) -> (uint, Option<uint>) {
1050 self.iter.size_hint()
1054 /// An iterator which rejects elements while `predicate` is true
1055 pub struct SkipWhileIterator<'self, A, T> {
1058 priv predicate: &'self fn(&A) -> bool
1061 impl<'self, A, T: Iterator<A>> Iterator<A> for SkipWhileIterator<'self, A, T> {
1063 fn next(&mut self) -> Option<A> {
1064 let mut next = self.iter.next();
1071 if (self.predicate)(&x) {
1072 next = self.iter.next();
1086 fn size_hint(&self) -> (uint, Option<uint>) {
1087 let (_, upper) = self.iter.size_hint();
1088 (0, upper) // can't know a lower bound, due to the predicate
1092 /// An iterator which only accepts elements while `predicate` is true
1093 pub struct TakeWhileIterator<'self, A, T> {
1096 priv predicate: &'self fn(&A) -> bool
1099 impl<'self, A, T: Iterator<A>> Iterator<A> for TakeWhileIterator<'self, A, T> {
1101 fn next(&mut self) -> Option<A> {
1105 match self.iter.next() {
1107 if (self.predicate)(&x) {
1120 fn size_hint(&self) -> (uint, Option<uint>) {
1121 let (_, upper) = self.iter.size_hint();
1122 (0, upper) // can't know a lower bound, due to the predicate
1126 /// An iterator which skips over `n` elements of `iter`.
1127 // FIXME #6967: Dummy A parameter to get around type inference bug
1129 pub struct SkipIterator<A, T> {
1134 impl<A, T: Iterator<A>> Iterator<A> for SkipIterator<A, T> {
1136 fn next(&mut self) -> Option<A> {
1137 let mut next = self.iter.next();
1145 next = self.iter.next();
1160 fn size_hint(&self) -> (uint, Option<uint>) {
1161 let (lower, upper) = self.iter.size_hint();
1163 let lower = if lower >= self.n { lower - self.n } else { 0 };
1165 let upper = match upper {
1166 Some(x) if x >= self.n => Some(x - self.n),
1175 /// An iterator which only iterates over the first `n` iterations of `iter`.
1176 // FIXME #6967: Dummy A parameter to get around type inference bug
1178 pub struct TakeIterator<A, T> {
1183 impl<A, T: Iterator<A>> Iterator<A> for TakeIterator<A, T> {
1185 fn next(&mut self) -> Option<A> {
1186 let next = self.iter.next();
1196 fn size_hint(&self) -> (uint, Option<uint>) {
1197 let (lower, upper) = self.iter.size_hint();
1199 let lower = cmp::min(lower, self.n);
1201 let upper = match upper {
1202 Some(x) if x < self.n => Some(x),
1210 /// An iterator to maintain state while iterating another iterator
1211 pub struct ScanIterator<'self, A, B, T, St> {
1213 priv f: &'self fn(&mut St, A) -> Option<B>,
1215 /// The current internal state to be passed to the closure next.
1219 impl<'self, A, B, T: Iterator<A>, St> Iterator<B> for ScanIterator<'self, A, B, T, St> {
1221 fn next(&mut self) -> Option<B> {
1222 self.iter.next().chain(|a| (self.f)(&mut self.state, a))
1226 fn size_hint(&self) -> (uint, Option<uint>) {
1227 let (_, upper) = self.iter.size_hint();
1228 (0, upper) // can't know a lower bound, due to the scan function
1232 /// An iterator that maps each element to an iterator,
1233 /// and yields the elements of the produced iterators
1235 // FIXME #6967: Dummy B parameter to get around type inference bug
1236 pub struct FlatMapIterator<'self, A, B, T, U> {
1238 priv f: &'self fn(A) -> U,
1239 priv subiter: Option<U>,
1242 impl<'self, A, T: Iterator<A>, B, U: Iterator<B>> Iterator<B> for
1243 FlatMapIterator<'self, A, B, T, U> {
1245 fn next(&mut self) -> Option<B> {
1247 for self.subiter.mut_iter().advance |inner| {
1248 for inner.advance |x| {
1252 match self.iter.next().map_consume(|x| (self.f)(x)) {
1253 None => return None,
1254 next => self.subiter = next,
1260 /// An iterator that calls a function with a reference to each
1261 /// element before yielding it.
1262 pub struct PeekIterator<'self, A, T> {
1264 priv f: &'self fn(&A)
1267 impl<'self, A, T: Iterator<A>> Iterator<A> for PeekIterator<'self, A, T> {
1269 fn next(&mut self) -> Option<A> {
1270 let next = self.iter.next();
1273 Some(ref a) => (self.f)(a),
1281 fn size_hint(&self) -> (uint, Option<uint>) {
1282 self.iter.size_hint()
1286 impl<'self, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for PeekIterator<'self, A, T> {
1288 fn next_back(&mut self) -> Option<A> {
1289 let next = self.iter.next_back();
1292 Some(ref a) => (self.f)(a),
1300 /// An iterator which just modifies the contained state throughout iteration.
1301 pub struct UnfoldrIterator<'self, A, St> {
1302 priv f: &'self fn(&mut St) -> Option<A>,
1303 /// Internal state that will be yielded on the next iteration
1307 impl<'self, A, St> UnfoldrIterator<'self, A, St> {
1308 /// Creates a new iterator with the specified closure as the "iterator
1309 /// function" and an initial state to eventually pass to the iterator
1311 pub fn new<'a>(initial_state: St, f: &'a fn(&mut St) -> Option<A>)
1312 -> UnfoldrIterator<'a, A, St> {
1315 state: initial_state
1320 impl<'self, A, St> Iterator<A> for UnfoldrIterator<'self, A, St> {
1322 fn next(&mut self) -> Option<A> {
1323 (self.f)(&mut self.state)
1327 /// An infinite iterator starting at `start` and advancing by `step` with each
1330 pub struct Counter<A> {
1331 /// The current state the counter is at (next value to be yielded)
1333 /// The amount that this iterator is stepping by
1337 impl<A> Counter<A> {
1338 /// Creates a new counter with the specified start/step
1340 pub fn new(start: A, step: A) -> Counter<A> {
1341 Counter{state: start, step: step}
1345 impl<A: Add<A, A> + Clone> Iterator<A> for Counter<A> {
1347 fn next(&mut self) -> Option<A> {
1348 let result = self.state.clone();
1349 self.state = self.state.add(&self.step); // FIXME: #6050
1354 fn size_hint(&self) -> (uint, Option<uint>) {
1355 (uint::max_value, None) // Too bad we can't specify an infinite lower bound
1367 fn test_counter_from_iter() {
1368 let mut it = Counter::new(0, 5).take_(10);
1369 let xs: ~[int] = FromIterator::from_iterator(&mut it);
1370 assert_eq!(xs, ~[0, 5, 10, 15, 20, 25, 30, 35, 40, 45]);
1374 fn test_iterator_chain() {
1375 let xs = [0u, 1, 2, 3, 4, 5];
1376 let ys = [30u, 40, 50, 60];
1377 let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
1378 let mut it = xs.iter().chain_(ys.iter());
1380 for it.advance |&x| {
1381 assert_eq!(x, expected[i]);
1384 assert_eq!(i, expected.len());
1386 let ys = Counter::new(30u, 10).take_(4);
1387 let mut it = xs.iter().transform(|&x| x).chain_(ys);
1389 for it.advance |x| {
1390 assert_eq!(x, expected[i]);
1393 assert_eq!(i, expected.len());
1397 fn test_filter_map() {
1398 let mut it = Counter::new(0u, 1u).take_(10)
1399 .filter_map(|x| if x.is_even() { Some(x*x) } else { None });
1400 assert_eq!(it.collect::<~[uint]>(), ~[0*0, 2*2, 4*4, 6*6, 8*8]);
1404 fn test_iterator_enumerate() {
1405 let xs = [0u, 1, 2, 3, 4, 5];
1406 let mut it = xs.iter().enumerate();
1407 for it.advance |(i, &x)| {
1413 fn test_iterator_take_while() {
1414 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1415 let ys = [0u, 1, 2, 3, 5, 13];
1416 let mut it = xs.iter().take_while(|&x| *x < 15u);
1418 for it.advance |&x| {
1419 assert_eq!(x, ys[i]);
1422 assert_eq!(i, ys.len());
1426 fn test_iterator_skip_while() {
1427 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1428 let ys = [15, 16, 17, 19];
1429 let mut it = xs.iter().skip_while(|&x| *x < 15u);
1431 for it.advance |&x| {
1432 assert_eq!(x, ys[i]);
1435 assert_eq!(i, ys.len());
1439 fn test_iterator_skip() {
1440 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1441 let ys = [13, 15, 16, 17, 19, 20, 30];
1442 let mut it = xs.iter().skip(5);
1444 for it.advance |&x| {
1445 assert_eq!(x, ys[i]);
1448 assert_eq!(i, ys.len());
1452 fn test_iterator_take() {
1453 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1454 let ys = [0u, 1, 2, 3, 5];
1455 let mut it = xs.iter().take_(5);
1457 for it.advance |&x| {
1458 assert_eq!(x, ys[i]);
1461 assert_eq!(i, ys.len());
1465 fn test_iterator_scan() {
1466 // test the type inference
1467 fn add(old: &mut int, new: &uint) -> Option<float> {
1468 *old += *new as int;
1471 let xs = [0u, 1, 2, 3, 4];
1472 let ys = [0f, 1f, 3f, 6f, 10f];
1474 let mut it = xs.iter().scan(0, add);
1476 for it.advance |x| {
1477 assert_eq!(x, ys[i]);
1480 assert_eq!(i, ys.len());
1484 fn test_iterator_flat_map() {
1485 let xs = [0u, 3, 6];
1486 let ys = [0u, 1, 2, 3, 4, 5, 6, 7, 8];
1487 let mut it = xs.iter().flat_map_(|&x| Counter::new(x, 1).take_(3));
1489 for it.advance |x: uint| {
1490 assert_eq!(x, ys[i]);
1493 assert_eq!(i, ys.len());
1498 let xs = [1u, 2, 3, 4];
1504 .collect::<~[uint]>();
1506 assert_eq!(n, xs.len());
1507 assert_eq!(xs, ys.as_slice());
1512 fn count(st: &mut uint) -> Option<uint> {
1514 let ret = Some(*st);
1522 let mut it = UnfoldrIterator::new(0, count);
1524 for it.advance |counted| {
1525 assert_eq!(counted, i);
1534 let it = Counter::new(0u,1).take_(cycle_len).cycle();
1535 assert_eq!(it.size_hint(), (uint::max_value, None));
1536 for it.take_(100).enumerate().advance |(i, x)| {
1537 assert_eq!(i % cycle_len, x);
1540 let mut it = Counter::new(0u,1).take_(0).cycle();
1541 assert_eq!(it.size_hint(), (0, Some(0)));
1542 assert_eq!(it.next(), None);
1546 fn test_iterator_nth() {
1547 let v = &[0, 1, 2, 3, 4];
1548 for uint::range(0, v.len()) |i| {
1549 assert_eq!(v.iter().nth(i).unwrap(), &v[i]);
1554 fn test_iterator_last() {
1555 let v = &[0, 1, 2, 3, 4];
1556 assert_eq!(v.iter().last_().unwrap(), &4);
1557 assert_eq!(v.slice(0, 1).iter().last_().unwrap(), &0);
1561 fn test_iterator_len() {
1562 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1563 assert_eq!(v.slice(0, 4).iter().len_(), 4);
1564 assert_eq!(v.slice(0, 10).iter().len_(), 10);
1565 assert_eq!(v.slice(0, 0).iter().len_(), 0);
1569 fn test_iterator_sum() {
1570 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1571 assert_eq!(v.slice(0, 4).iter().transform(|&x| x).sum(), 6);
1572 assert_eq!(v.iter().transform(|&x| x).sum(), 55);
1573 assert_eq!(v.slice(0, 0).iter().transform(|&x| x).sum(), 0);
1577 fn test_iterator_product() {
1578 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1579 assert_eq!(v.slice(0, 4).iter().transform(|&x| x).product(), 0);
1580 assert_eq!(v.slice(1, 5).iter().transform(|&x| x).product(), 24);
1581 assert_eq!(v.slice(0, 0).iter().transform(|&x| x).product(), 1);
1585 fn test_iterator_max() {
1586 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1587 assert_eq!(v.slice(0, 4).iter().transform(|&x| x).max(), Some(3));
1588 assert_eq!(v.iter().transform(|&x| x).max(), Some(10));
1589 assert_eq!(v.slice(0, 0).iter().transform(|&x| x).max(), None);
1593 fn test_iterator_min() {
1594 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1595 assert_eq!(v.slice(0, 4).iter().transform(|&x| x).min(), Some(0));
1596 assert_eq!(v.iter().transform(|&x| x).min(), Some(0));
1597 assert_eq!(v.slice(0, 0).iter().transform(|&x| x).min(), None);
1601 fn test_iterator_size_hint() {
1602 let c = Counter::new(0, 1);
1603 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
1604 let v2 = &[10, 11, 12];
1607 assert_eq!(c.size_hint(), (uint::max_value, None));
1608 assert_eq!(vi.size_hint(), (10, Some(10)));
1610 assert_eq!(c.take_(5).size_hint(), (5, Some(5)));
1611 assert_eq!(c.skip(5).size_hint().second(), None);
1612 assert_eq!(c.take_while(|_| false).size_hint(), (0, None));
1613 assert_eq!(c.skip_while(|_| false).size_hint(), (0, None));
1614 assert_eq!(c.enumerate().size_hint(), (uint::max_value, None));
1615 assert_eq!(c.chain_(vi.transform(|&i| i)).size_hint(), (uint::max_value, None));
1616 assert_eq!(c.zip(vi).size_hint(), (10, Some(10)));
1617 assert_eq!(c.scan(0, |_,_| Some(0)).size_hint(), (0, None));
1618 assert_eq!(c.filter(|_| false).size_hint(), (0, None));
1619 assert_eq!(c.transform(|_| 0).size_hint(), (uint::max_value, None));
1620 assert_eq!(c.filter_map(|_| Some(0)).size_hint(), (0, None));
1622 assert_eq!(vi.take_(5).size_hint(), (5, Some(5)));
1623 assert_eq!(vi.take_(12).size_hint(), (10, Some(10)));
1624 assert_eq!(vi.skip(3).size_hint(), (7, Some(7)));
1625 assert_eq!(vi.skip(12).size_hint(), (0, Some(0)));
1626 assert_eq!(vi.take_while(|_| false).size_hint(), (0, Some(10)));
1627 assert_eq!(vi.skip_while(|_| false).size_hint(), (0, Some(10)));
1628 assert_eq!(vi.enumerate().size_hint(), (10, Some(10)));
1629 assert_eq!(vi.chain_(v2.iter()).size_hint(), (13, Some(13)));
1630 assert_eq!(vi.zip(v2.iter()).size_hint(), (3, Some(3)));
1631 assert_eq!(vi.scan(0, |_,_| Some(0)).size_hint(), (0, Some(10)));
1632 assert_eq!(vi.filter(|_| false).size_hint(), (0, Some(10)));
1633 assert_eq!(vi.transform(|i| i+1).size_hint(), (10, Some(10)));
1634 assert_eq!(vi.filter_map(|_| Some(0)).size_hint(), (0, Some(10)));
1639 let a = ~[1, 2, 3, 4, 5];
1640 let b: ~[int] = a.iter().transform(|&x| x).collect();
1646 let v = ~&[1, 2, 3, 4, 5];
1647 assert!(v.iter().all(|&x| x < 10));
1648 assert!(!v.iter().all(|&x| x.is_even()));
1649 assert!(!v.iter().all(|&x| x > 100));
1650 assert!(v.slice(0, 0).iter().all(|_| fail!()));
1655 let v = ~&[1, 2, 3, 4, 5];
1656 assert!(v.iter().any(|&x| x < 10));
1657 assert!(v.iter().any(|&x| x.is_even()));
1658 assert!(!v.iter().any(|&x| x > 100));
1659 assert!(!v.slice(0, 0).iter().any(|_| fail!()));
1664 let v = &[1, 3, 9, 27, 103, 14, 11];
1665 assert_eq!(*v.iter().find_(|x| *x & 1 == 0).unwrap(), 14);
1666 assert_eq!(*v.iter().find_(|x| *x % 3 == 0).unwrap(), 3);
1667 assert!(v.iter().find_(|x| *x % 12 == 0).is_none());
1671 fn test_position() {
1672 let v = &[1, 3, 9, 27, 103, 14, 11];
1673 assert_eq!(v.iter().position(|x| *x & 1 == 0).unwrap(), 5);
1674 assert_eq!(v.iter().position(|x| *x % 3 == 0).unwrap(), 1);
1675 assert!(v.iter().position(|x| *x % 12 == 0).is_none());
1680 let xs = &[1, 2, 2, 1, 5, 9, 0, 2];
1681 assert_eq!(xs.iter().count(|x| *x == 2), 3);
1682 assert_eq!(xs.iter().count(|x| *x == 5), 1);
1683 assert_eq!(xs.iter().count(|x| *x == 95), 0);
1688 let xs = [-3, 0, 1, 5, -10];
1689 assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
1694 let xs = [-3, 0, 1, 5, -10];
1695 assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
1700 let xs = [2, 4, 6, 8, 10, 12, 14, 16];
1701 let mut it = xs.iter();
1704 assert_eq!(it.invert().transform(|&x| x).collect::<~[int]>(), ~[16, 14, 12, 10, 8, 6]);
1708 fn test_double_ended_map() {
1709 let xs = [1, 2, 3, 4, 5, 6];
1710 let mut it = xs.iter().transform(|&x| x * -1);
1711 assert_eq!(it.next(), Some(-1));
1712 assert_eq!(it.next(), Some(-2));
1713 assert_eq!(it.next_back(), Some(-6));
1714 assert_eq!(it.next_back(), Some(-5));
1715 assert_eq!(it.next(), Some(-3));
1716 assert_eq!(it.next_back(), Some(-4));
1717 assert_eq!(it.next(), None);
1721 fn test_double_ended_filter() {
1722 let xs = [1, 2, 3, 4, 5, 6];
1723 let mut it = xs.iter().filter(|&x| *x & 1 == 0);
1724 assert_eq!(it.next_back().unwrap(), &6);
1725 assert_eq!(it.next_back().unwrap(), &4);
1726 assert_eq!(it.next().unwrap(), &2);
1727 assert_eq!(it.next_back(), None);
1731 fn test_double_ended_filter_map() {
1732 let xs = [1, 2, 3, 4, 5, 6];
1733 let mut it = xs.iter().filter_map(|&x| if x & 1 == 0 { Some(x * 2) } else { None });
1734 assert_eq!(it.next_back().unwrap(), 12);
1735 assert_eq!(it.next_back().unwrap(), 8);
1736 assert_eq!(it.next().unwrap(), 4);
1737 assert_eq!(it.next_back(), None);
1741 fn test_double_ended_chain() {
1742 let xs = [1, 2, 3, 4, 5];
1743 let ys = ~[7, 9, 11];
1744 let mut it = xs.iter().chain_(ys.iter()).invert();
1745 assert_eq!(it.next().unwrap(), &11)
1746 assert_eq!(it.next().unwrap(), &9)
1747 assert_eq!(it.next_back().unwrap(), &1)
1748 assert_eq!(it.next_back().unwrap(), &2)
1749 assert_eq!(it.next_back().unwrap(), &3)
1750 assert_eq!(it.next_back().unwrap(), &4)
1751 assert_eq!(it.next_back().unwrap(), &5)
1752 assert_eq!(it.next_back().unwrap(), &7)
1753 assert_eq!(it.next_back(), None)
1757 fn test_random_access_chain() {
1758 let xs = [1, 2, 3, 4, 5];
1759 let ys = ~[7, 9, 11];
1760 let mut it = xs.iter().chain_(ys.iter());
1761 assert_eq!(it.idx(0).unwrap(), &1);
1762 assert_eq!(it.idx(5).unwrap(), &7);
1763 assert_eq!(it.idx(7).unwrap(), &11);
1764 assert!(it.idx(8).is_none());
1770 assert_eq!(it.idx(0).unwrap(), &3);
1771 assert_eq!(it.idx(4).unwrap(), &9);
1772 assert!(it.idx(6).is_none());