From 6919cf5fe14701621437fcb57f3a0c38fb394c65 Mon Sep 17 00:00:00 2001 From: Daniel Micay Date: Sun, 8 Sep 2013 11:01:16 -0400 Subject: rename `std::iterator` to `std::iter` The trait will keep the `Iterator` naming, but a more concise module name makes using the free functions less verbose. The module will define iterables in addition to iterators, as it deals with iteration in general. --- src/etc/unicode.py | 2 +- src/libextra/bitv.rs | 4 +- src/libextra/dlist.rs | 16 +- src/libextra/enum_set.rs | 2 - src/libextra/json.rs | 7 +- src/libextra/num/bigint.rs | 4 +- src/libextra/priority_queue.rs | 1 - src/libextra/ringbuf.rs | 6 +- src/libextra/smallintmap.rs | 2 +- src/libextra/treemap.rs | 2 +- src/librustc/middle/check_match.rs | 4 +- src/librustc/middle/trans/basic_block.rs | 2 +- src/libstd/at_vec.rs | 2 +- src/libstd/c_str.rs | 4 +- src/libstd/either.rs | 2 +- src/libstd/fmt/mod.rs | 2 +- src/libstd/fmt/parse.rs | 3 +- src/libstd/hash.rs | 2 +- src/libstd/hashmap.rs | 4 +- src/libstd/io.rs | 2 +- src/libstd/iter.rs | 2659 ++++++++++++++++++++++++++++++ src/libstd/iterator.rs | 2659 ------------------------------ src/libstd/option.rs | 12 +- src/libstd/os.rs | 2 +- src/libstd/path.rs | 2 +- src/libstd/prelude.rs | 8 +- src/libstd/ptr.rs | 2 +- src/libstd/rand.rs | 4 +- src/libstd/repr.rs | 2 +- src/libstd/repr_stage0.rs | 2 +- src/libstd/result.rs | 4 +- src/libstd/rt/args.rs | 2 +- src/libstd/rt/io/extensions.rs | 2 +- src/libstd/rt/mod.rs | 2 +- src/libstd/rt/sched.rs | 2 +- src/libstd/rt/test.rs | 2 +- src/libstd/rt/uv/uvio.rs | 2 +- src/libstd/select.rs | 4 +- src/libstd/std.rs | 2 +- src/libstd/str.rs | 16 +- src/libstd/str/ascii.rs | 2 +- src/libstd/to_bytes.rs | 2 +- src/libstd/to_str.rs | 2 +- src/libstd/trie.rs | 1 - src/libstd/unicode.rs | 2 +- src/libstd/vec.rs | 20 +- src/test/auxiliary/nested_item.rs | 2 +- src/test/run-pass/unfold-cross-crate.rs | 2 +- 48 files changed, 2745 insertions(+), 2751 deletions(-) create mode 100644 src/libstd/iter.rs delete mode 100644 src/libstd/iterator.rs (limited to 'src') diff --git a/src/etc/unicode.py b/src/etc/unicode.py index d7c2016912c..a58c5767ead 100755 --- a/src/etc/unicode.py +++ b/src/etc/unicode.py @@ -310,7 +310,7 @@ def emit_decomp_module(f, canon, compat, combine): + " bsearch_range_value_table(c, combining_class_table)\n" + " }\n\n") f.write(" fn d(c: char, i: &fn(char), k: bool) {\n") - f.write(" use iterator::Iterator;\n"); + f.write(" use iter::Iterator;\n"); f.write(" if c <= '\\x7f' { i(c); return; }\n") diff --git a/src/libextra/bitv.rs b/src/libextra/bitv.rs index 70fd3a01ca4..780527e4532 100644 --- a/src/libextra/bitv.rs +++ b/src/libextra/bitv.rs @@ -12,8 +12,8 @@ use std::cmp; -use std::iterator::RandomAccessIterator; -use std::iterator::{Invert, Enumerate, Repeat, Map, Zip}; +use std::iter::RandomAccessIterator; +use std::iter::{Invert, Enumerate, Repeat, Map, Zip}; use std::num; use std::ops; use std::uint; diff --git a/src/libextra/dlist.rs b/src/libextra/dlist.rs index 64bb17a6271..ac296ad527e 100644 --- a/src/libextra/dlist.rs +++ b/src/libextra/dlist.rs @@ -25,8 +25,8 @@ use std::cast; use std::ptr; use std::util; -use std::iterator::{FromIterator, Extendable, Invert}; -use std::iterator; +use std::iter::Invert; +use std::iter; use container::Deque; @@ -593,27 +593,27 @@ impl Extendable for DList { impl Eq for DList { fn eq(&self, other: &DList) -> bool { self.len() == other.len() && - iterator::order::eq(self.iter(), other.iter()) + iter::order::eq(self.iter(), other.iter()) } fn ne(&self, other: &DList) -> bool { self.len() != other.len() || - iterator::order::ne(self.iter(), other.iter()) + iter::order::ne(self.iter(), other.iter()) } } impl Ord for DList { fn lt(&self, other: &DList) -> bool { - iterator::order::lt(self.iter(), other.iter()) + iter::order::lt(self.iter(), other.iter()) } fn le(&self, other: &DList) -> bool { - iterator::order::le(self.iter(), other.iter()) + iter::order::le(self.iter(), other.iter()) } fn gt(&self, other: &DList) -> bool { - iterator::order::gt(self.iter(), other.iter()) + iter::order::gt(self.iter(), other.iter()) } fn ge(&self, other: &DList) -> bool { - iterator::order::ge(self.iter(), other.iter()) + iter::order::ge(self.iter(), other.iter()) } } diff --git a/src/libextra/enum_set.rs b/src/libextra/enum_set.rs index 2b1246b0af0..242faa2b4da 100644 --- a/src/libextra/enum_set.rs +++ b/src/libextra/enum_set.rs @@ -8,8 +8,6 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use std::iterator::Iterator; - #[deriving(Clone, Eq, IterBytes, ToStr)] /// A specialized Set implementation to use enum types. pub struct EnumSet { diff --git a/src/libextra/json.rs b/src/libextra/json.rs index ee3e1966fe2..f76dc05b277 100644 --- a/src/libextra/json.rs +++ b/src/libextra/json.rs @@ -18,7 +18,6 @@ use std::char; use std::cast::transmute; -use std::iterator; use std::float; use std::hashmap::HashMap; use std::io::WriterUtil; @@ -489,7 +488,7 @@ pub struct Parser { } /// Decode a json value from an Iterator -pub fn Parser>(rdr: ~T) -> Parser { +pub fn Parser>(rdr: ~T) -> Parser { let mut p = Parser { rdr: rdr, ch: '\x00', @@ -500,7 +499,7 @@ pub fn Parser>(rdr: ~T) -> Parser { p } -impl> Parser { +impl> Parser { pub fn parse(&mut self) -> Result { match self.parse_value() { Ok(value) => { @@ -518,7 +517,7 @@ impl> Parser { } } -impl> Parser { +impl> Parser { // FIXME: #8971: unsound fn eof(&self) -> bool { self.ch == unsafe { transmute(-1u32) } } diff --git a/src/libextra/num/bigint.rs b/src/libextra/num/bigint.rs index cb764228155..2e61b7fdbdc 100644 --- a/src/libextra/num/bigint.rs +++ b/src/libextra/num/bigint.rs @@ -2011,13 +2011,13 @@ mod bigint_tests { #[cfg(test)] mod bench { use super::*; - use std::{iterator, util}; + use std::{iter, util}; use std::num::{Zero, One}; use extra::test::BenchHarness; fn factorial(n: uint) -> BigUint { let mut f: BigUint = One::one(); - for i in iterator::range_inclusive(1, n) { + for i in iter::range_inclusive(1, n) { f = f * BigUint::from_uint(i); } f diff --git a/src/libextra/priority_queue.rs b/src/libextra/priority_queue.rs index b085981aabb..6dd4759d927 100644 --- a/src/libextra/priority_queue.rs +++ b/src/libextra/priority_queue.rs @@ -16,7 +16,6 @@ use std::clone::Clone; use std::unstable::intrinsics::{move_val_init, init}; use std::util::{replace, swap}; use std::vec; -use std::iterator::{FromIterator, Extendable}; /// A priority queue implemented with a binary heap #[deriving(Clone)] diff --git a/src/libextra/ringbuf.rs b/src/libextra/ringbuf.rs index 9ae9b47e207..ea8537caeb5 100644 --- a/src/libextra/ringbuf.rs +++ b/src/libextra/ringbuf.rs @@ -15,7 +15,7 @@ use std::num; use std::vec; -use std::iterator::{FromIterator, Invert, RandomAccessIterator, Extendable}; +use std::iter::{Invert, RandomAccessIterator}; use container::Deque; @@ -694,13 +694,13 @@ mod tests { #[test] fn test_from_iterator() { - use std::iterator; + use std::iter; let v = ~[1,2,3,4,5,6,7]; let deq: RingBuf = v.iter().map(|&x| x).collect(); let u: ~[int] = deq.iter().map(|&x| x).collect(); assert_eq!(u, v); - let mut seq = iterator::count(0u, 2).take(256); + let mut seq = iter::count(0u, 2).take(256); let deq: RingBuf = seq.collect(); for (i, &x) in deq.iter().enumerate() { assert_eq!(2*i, x); diff --git a/src/libextra/smallintmap.rs b/src/libextra/smallintmap.rs index ac07fd2bebf..983247971d3 100644 --- a/src/libextra/smallintmap.rs +++ b/src/libextra/smallintmap.rs @@ -15,7 +15,7 @@ #[allow(missing_doc)]; -use std::iterator::{Iterator, Enumerate, FilterMap, Invert}; +use std::iter::{Enumerate, FilterMap, Invert}; use std::util::replace; use std::vec::{VecIterator, VecMutIterator}; use std::vec; diff --git a/src/libextra/treemap.rs b/src/libextra/treemap.rs index 307de43a067..99643e643b7 100644 --- a/src/libextra/treemap.rs +++ b/src/libextra/treemap.rs @@ -14,7 +14,7 @@ use std::util::{swap, replace}; -use std::iterator::{FromIterator, Extendable, Peekable}; +use std::iter::{Peekable}; use std::cmp::Ordering; // This is implemented as an AA tree, which is a simplified variation of diff --git a/src/librustc/middle/check_match.rs b/src/librustc/middle/check_match.rs index 14a4601e415..581e203ae9a 100644 --- a/src/librustc/middle/check_match.rs +++ b/src/librustc/middle/check_match.rs @@ -18,7 +18,7 @@ use middle::typeck::method_map; use middle::moves; use util::ppaux::ty_to_str; -use std::iterator; +use std::iter; use std::num; use std::vec; use extra::sort; @@ -282,7 +282,7 @@ pub fn is_useful(cx: &MatchCheckCtxt, m: &matrix, v: &[@Pat]) -> useful { _ => max_len } }; - for n in iterator::range(0u, max_len + 1) { + for n in iter::range(0u, max_len + 1) { match is_useful_specialized(cx, m, v, vec(n), n, left_ty) { not_useful => (), ref u => return *u, diff --git a/src/librustc/middle/trans/basic_block.rs b/src/librustc/middle/trans/basic_block.rs index 8ca18d81245..14ba9244260 100644 --- a/src/librustc/middle/trans/basic_block.rs +++ b/src/librustc/middle/trans/basic_block.rs @@ -10,7 +10,7 @@ use lib::llvm::{llvm, BasicBlockRef}; use middle::trans::value::{UserIterator, Value}; -use std::iterator::{Filter, Map}; +use std::iter::{Filter, Map}; pub struct BasicBlock(BasicBlockRef); diff --git a/src/libstd/at_vec.rs b/src/libstd/at_vec.rs index c192803efff..d69ed5d9102 100644 --- a/src/libstd/at_vec.rs +++ b/src/libstd/at_vec.rs @@ -12,7 +12,7 @@ use clone::Clone; use container::Container; -use iterator::Iterator; +use iter::Iterator; use option::{Option, Some, None}; use sys; use unstable::raw::Repr; diff --git a/src/libstd/c_str.rs b/src/libstd/c_str.rs index 6f12e219c3c..51b70a07be8 100644 --- a/src/libstd/c_str.rs +++ b/src/libstd/c_str.rs @@ -9,14 +9,14 @@ // except according to those terms. use cast; -use iterator::{Iterator,range}; +use iter::{Iterator, range}; use libc; use ops::Drop; use option::{Option, Some, None}; use ptr::RawPtr; use ptr; use str::StrSlice; -use vec::{ImmutableVector,CopyableVector}; +use vec::{ImmutableVector, CopyableVector}; use container::Container; /// Resolution options for the `null_byte` condition diff --git a/src/libstd/either.rs b/src/libstd/either.rs index 5d988965e8c..ec9e6d1ca4b 100644 --- a/src/libstd/either.rs +++ b/src/libstd/either.rs @@ -16,7 +16,7 @@ use option::{Some, None}; use clone::Clone; use container::Container; use cmp::Eq; -use iterator::{Iterator, FilterMap}; +use iter::{Iterator, FilterMap}; use result::Result; use result; use str::StrSlice; diff --git a/src/libstd/fmt/mod.rs b/src/libstd/fmt/mod.rs index ef036340412..7d5033e3a6a 100644 --- a/src/libstd/fmt/mod.rs +++ b/src/libstd/fmt/mod.rs @@ -812,7 +812,7 @@ macro_rules! upper_hex(($ty:ident, $into:ident) => { #[doc(hidden)] pub fn upperhex(buf: &[u8], f: &mut Formatter) { let mut local = [0u8, ..16]; - for i in ::iterator::range(0, buf.len()) { + for i in ::iter::range(0, buf.len()) { local[i] = match buf[i] as char { 'a' .. 'f' => (buf[i] - 'a' as u8) + 'A' as u8, c => c as u8, diff --git a/src/libstd/fmt/parse.rs b/src/libstd/fmt/parse.rs index 245318c4699..fd0e86d7a31 100644 --- a/src/libstd/fmt/parse.rs +++ b/src/libstd/fmt/parse.rs @@ -12,7 +12,6 @@ use prelude::*; use char; use str; -use iterator; condition! { pub parse_error: ~str -> (); } @@ -152,7 +151,7 @@ pub struct Parser<'self> { priv depth: uint, } -impl<'self> iterator::Iterator> for Parser<'self> { +impl<'self> Iterator> for Parser<'self> { fn next(&mut self) -> Option> { match self.cur.clone().next() { Some((_, '#')) => { self.cur.next(); Some(CurrentArgument) } diff --git a/src/libstd/hash.rs b/src/libstd/hash.rs index 6682a410979..4cce9995328 100644 --- a/src/libstd/hash.rs +++ b/src/libstd/hash.rs @@ -22,7 +22,7 @@ #[allow(missing_doc)]; use container::Container; -use iterator::Iterator; +use iter::Iterator; use option::{Some, None}; use rt::io::Writer; use str::OwnedStr; diff --git a/src/libstd/hashmap.rs b/src/libstd/hashmap.rs index bcd658ece66..fab8299f7a7 100644 --- a/src/libstd/hashmap.rs +++ b/src/libstd/hashmap.rs @@ -19,8 +19,8 @@ use container::{Container, Mutable, Map, MutableMap, Set, MutableSet}; use clone::Clone; use cmp::{Eq, Equiv}; use hash::Hash; -use iterator::{Iterator, FromIterator, Extendable}; -use iterator::{FilterMap, Chain, Repeat, Zip}; +use iter::{Iterator, FromIterator, Extendable}; +use iter::{FilterMap, Chain, Repeat, Zip}; use num; use option::{None, Option, Some}; use rand::RngUtil; diff --git a/src/libstd/io.rs b/src/libstd/io.rs index ee948446614..9919cca6729 100644 --- a/src/libstd/io.rs +++ b/src/libstd/io.rs @@ -52,7 +52,7 @@ use clone::Clone; use c_str::ToCStr; use container::Container; use int; -use iterator::Iterator; +use iter::Iterator; use libc::consts::os::posix88::*; use libc::{c_int, c_void, size_t}; use libc; diff --git a/src/libstd/iter.rs b/src/libstd/iter.rs new file mode 100644 index 00000000000..5ca827350d0 --- /dev/null +++ b/src/libstd/iter.rs @@ -0,0 +1,2659 @@ +// Copyright 2013 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +/*! Composable external iterators + +The `Iterator` trait defines an interface for objects which implement iteration as a state machine. + +Algorithms like `zip` are provided as `Iterator` implementations which wrap other objects +implementing the `Iterator` trait. + +*/ + +use cmp; +use num::{Zero, One, Integer, CheckedAdd, CheckedSub, Saturating}; +use option::{Option, Some, None}; +use ops::{Add, Mul, Sub}; +use cmp::Ord; +use clone::Clone; +use uint; +use util; + +/// Conversion from an `Iterator` +pub trait FromIterator { + /// Build a container with elements from an external iterator. + fn from_iterator>(iterator: &mut T) -> Self; +} + +/// A type growable from an `Iterator` implementation +pub trait Extendable: FromIterator { + /// Extend a container with the elements yielded by an iterator + fn extend>(&mut self, iterator: &mut T); +} + +/// An interface for dealing with "external iterators". These types of iterators +/// can be resumed at any time as all state is stored internally as opposed to +/// being located on the call stack. +/// +/// The Iterator protocol states that an iterator yields a (potentially-empty, +/// potentially-infinite) sequence of values, and returns `None` to signal that +/// it's finished. The Iterator protocol does not define behavior after `None` +/// is returned. A concrete Iterator implementation may choose to behave however +/// it wishes, either by returning `None` infinitely, or by doing something +/// else. +pub trait Iterator { + /// Advance the iterator and return the next value. Return `None` when the end is reached. + fn next(&mut self) -> Option; + + /// Return a lower bound and upper bound on the remaining length of the iterator. + /// + /// The common use case for the estimate is pre-allocating space to store the results. + #[inline] + fn size_hint(&self) -> (uint, Option) { (0, None) } + + /// Chain this iterator with another, returning a new iterator which will + /// finish iterating over the current iterator, and then it will iterate + /// over the other specified iterator. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [0]; + /// let b = [1]; + /// let mut it = a.iter().chain(b.iter()); + /// assert_eq!(it.next().get(), &0); + /// assert_eq!(it.next().get(), &1); + /// assert!(it.next().is_none()); + /// ~~~ + #[inline] + fn chain>(self, other: U) -> Chain { + Chain{a: self, b: other, flag: false} + } + + /// Creates an iterator which iterates over both this and the specified + /// iterators simultaneously, yielding the two elements as pairs. When + /// either iterator returns None, all further invocations of next() will + /// return None. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [0]; + /// let b = [1]; + /// let mut it = a.iter().zip(b.iter()); + /// assert_eq!(it.next().get(), (&0, &1)); + /// assert!(it.next().is_none()); + /// ~~~ + #[inline] + fn zip>(self, other: U) -> Zip { + Zip{a: self, b: other} + } + + /// Creates a new iterator which will apply the specified function to each + /// element returned by the first, yielding the mapped element instead. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2]; + /// let mut it = a.iter().map(|&x| 2 * x); + /// assert_eq!(it.next().get(), 2); + /// assert_eq!(it.next().get(), 4); + /// assert!(it.next().is_none()); + /// ~~~ + #[inline] + fn map<'r, B>(self, f: &'r fn(A) -> B) -> Map<'r, A, B, Self> { + Map{iter: self, f: f} + } + + /// Creates an iterator which applies the predicate to each element returned + /// by this iterator. Only elements which have the predicate evaluate to + /// `true` will be yielded. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2]; + /// let mut it = a.iter().filter(|&x| *x > 1); + /// assert_eq!(it.next().get(), &2); + /// assert!(it.next().is_none()); + /// ~~~ + #[inline] + fn filter<'r>(self, predicate: &'r fn(&A) -> bool) -> Filter<'r, A, Self> { + Filter{iter: self, predicate: predicate} + } + + /// Creates an iterator which both filters and maps elements. + /// If the specified function returns None, the element is skipped. + /// Otherwise the option is unwrapped and the new value is yielded. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2]; + /// let mut it = a.iter().filter_map(|&x| if x > 1 {Some(2 * x)} else {None}); + /// assert_eq!(it.next().get(), 4); + /// assert!(it.next().is_none()); + /// ~~~ + #[inline] + fn filter_map<'r, B>(self, f: &'r fn(A) -> Option) -> FilterMap<'r, A, B, Self> { + FilterMap { iter: self, f: f } + } + + /// Creates an iterator which yields a pair of the value returned by this + /// iterator plus the current index of iteration. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [100, 200]; + /// let mut it = a.iter().enumerate(); + /// assert_eq!(it.next().get(), (0, &100)); + /// assert_eq!(it.next().get(), (1, &200)); + /// assert!(it.next().is_none()); + /// ~~~ + #[inline] + fn enumerate(self) -> Enumerate { + Enumerate{iter: self, count: 0} + } + + + /// Creates an iterator that has a `.peek()` method + /// that returns a optional reference to the next element. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [100, 200, 300]; + /// let mut it = xs.iter().map(|&x|x).peekable(); + /// assert_eq!(it.peek().unwrap(), &100); + /// assert_eq!(it.next().unwrap(), 100); + /// assert_eq!(it.next().unwrap(), 200); + /// assert_eq!(it.peek().unwrap(), &300); + /// assert_eq!(it.peek().unwrap(), &300); + /// assert_eq!(it.next().unwrap(), 300); + /// assert!(it.peek().is_none()); + /// assert!(it.next().is_none()); + /// ~~~ + #[inline] + fn peekable(self) -> Peekable { + Peekable{iter: self, peeked: None} + } + + /// Creates an iterator which invokes the predicate on elements until it + /// returns false. Once the predicate returns false, all further elements are + /// yielded. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 2, 1]; + /// let mut it = a.iter().skip_while(|&a| *a < 3); + /// assert_eq!(it.next().get(), &3); + /// assert_eq!(it.next().get(), &2); + /// assert_eq!(it.next().get(), &1); + /// assert!(it.next().is_none()); + /// ~~~ + #[inline] + fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) -> SkipWhile<'r, A, Self> { + SkipWhile{iter: self, flag: false, predicate: predicate} + } + + /// Creates an iterator which yields elements so long as the predicate + /// returns true. After the predicate returns false for the first time, no + /// further elements will be yielded. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 2, 1]; + /// let mut it = a.iter().take_while(|&a| *a < 3); + /// assert_eq!(it.next().get(), &1); + /// assert_eq!(it.next().get(), &2); + /// assert!(it.next().is_none()); + /// ~~~ + #[inline] + fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) -> TakeWhile<'r, A, Self> { + TakeWhile{iter: self, flag: false, predicate: predicate} + } + + /// Creates an iterator which skips the first `n` elements of this iterator, + /// and then it yields all further items. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// let mut it = a.iter().skip(3); + /// assert_eq!(it.next().get(), &4); + /// assert_eq!(it.next().get(), &5); + /// assert!(it.next().is_none()); + /// ~~~ + #[inline] + fn skip(self, n: uint) -> Skip { + Skip{iter: self, n: n} + } + + /// Creates an iterator which yields the first `n` elements of this + /// iterator, and then it will always return None. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// let mut it = a.iter().take(3); + /// assert_eq!(it.next().get(), &1); + /// assert_eq!(it.next().get(), &2); + /// assert_eq!(it.next().get(), &3); + /// assert!(it.next().is_none()); + /// ~~~ + #[inline] + fn take(self, n: uint) -> Take { + Take{iter: self, n: n} + } + + /// Creates a new iterator which behaves in a similar fashion to foldl. + /// There is a state which is passed between each iteration and can be + /// mutated as necessary. The yielded values from the closure are yielded + /// from the Scan instance when not None. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// let mut it = a.iter().scan(1, |fac, &x| { + /// *fac = *fac * x; + /// Some(*fac) + /// }); + /// assert_eq!(it.next().get(), 1); + /// assert_eq!(it.next().get(), 2); + /// assert_eq!(it.next().get(), 6); + /// assert_eq!(it.next().get(), 24); + /// assert_eq!(it.next().get(), 120); + /// assert!(it.next().is_none()); + /// ~~~ + #[inline] + fn scan<'r, St, B>(self, initial_state: St, f: &'r fn(&mut St, A) -> Option) + -> Scan<'r, A, B, Self, St> { + Scan{iter: self, f: f, state: initial_state} + } + + /// Creates an iterator that maps each element to an iterator, + /// and yields the elements of the produced iterators + /// + /// # Example + /// + /// ~~~ {.rust} + /// let xs = [2u, 3]; + /// let ys = [0u, 1, 0, 1, 2]; + /// let mut it = xs.iter().flat_map(|&x| count(0u, 1).take(x)); + /// // Check that `it` has the same elements as `ys` + /// let mut i = 0; + /// for x: uint in it { + /// assert_eq!(x, ys[i]); + /// i += 1; + /// } + /// ~~~ + #[inline] + fn flat_map<'r, B, U: Iterator>(self, f: &'r fn(A) -> U) + -> FlatMap<'r, A, Self, U> { + FlatMap{iter: self, f: f, frontiter: None, backiter: None } + } + + /// Creates an iterator that yields `None` forever after the underlying + /// iterator yields `None`. Random-access iterator behavior is not + /// affected, only single and double-ended iterator behavior. + /// + /// # Example + /// + /// ~~~ {.rust} + /// fn process>(it: U) -> int { + /// let mut it = it.fuse(); + /// let mut sum = 0; + /// for x in it { + /// if x > 5 { + /// break; + /// } + /// sum += x; + /// } + /// // did we exhaust the iterator? + /// if it.next().is_none() { + /// sum += 1000; + /// } + /// sum + /// } + /// let x = ~[1,2,3,7,8,9]; + /// assert_eq!(process(x.move_iter()), 1006); + /// ~~~ + #[inline] + fn fuse(self) -> Fuse { + Fuse{iter: self, done: false} + } + + /// Creates an iterator that calls a function with a reference to each + /// element before yielding it. This is often useful for debugging an + /// iterator pipeline. + /// + /// # Example + /// + /// ~~~ {.rust} + ///let xs = [1u, 4, 2, 3, 8, 9, 6]; + ///let sum = xs.iter() + /// .map(|&x| x) + /// .inspect(|&x| debug!("filtering %u", x)) + /// .filter(|&x| x % 2 == 0) + /// .inspect(|&x| debug!("%u made it through", x)) + /// .sum(); + ///println(sum.to_str()); + /// ~~~ + #[inline] + fn inspect<'r>(self, f: &'r fn(&A)) -> Inspect<'r, A, Self> { + Inspect{iter: self, f: f} + } + + /// An adaptation of an external iterator to the for-loop protocol of rust. + /// + /// # Example + /// + /// ~~~ {.rust} + /// use std::iter::count; + /// + /// for i in count(0, 10) { + /// printfln!("%d", i); + /// } + /// ~~~ + #[inline] + fn advance(&mut self, f: &fn(A) -> bool) -> bool { + loop { + match self.next() { + Some(x) => { + if !f(x) { return false; } + } + None => { return true; } + } + } + } + + /// Loops through the entire iterator, collecting all of the elements into + /// a container implementing `FromIterator`. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// let b: ~[int] = a.iter().map(|&x| x).collect(); + /// assert!(a == b); + /// ~~~ + #[inline] + fn collect>(&mut self) -> B { + FromIterator::from_iterator(self) + } + + /// Loops through the entire iterator, collecting all of the elements into + /// a unique vector. This is simply collect() specialized for vectors. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// let b: ~[int] = a.iter().map(|&x| x).to_owned_vec(); + /// assert!(a == b); + /// ~~~ + #[inline] + fn to_owned_vec(&mut self) -> ~[A] { + self.collect() + } + + /// Loops through `n` iterations, returning the `n`th element of the + /// iterator. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// let mut it = a.iter(); + /// assert!(it.nth(2).get() == &3); + /// assert!(it.nth(2) == None); + /// ~~~ + #[inline] + fn nth(&mut self, mut n: uint) -> Option { + loop { + match self.next() { + Some(x) => if n == 0 { return Some(x) }, + None => return None + } + n -= 1; + } + } + + /// Loops through the entire iterator, returning the last element of the + /// iterator. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// assert!(a.iter().last().get() == &5); + /// ~~~ + #[inline] + fn last(&mut self) -> Option { + let mut last = None; + for x in *self { last = Some(x); } + last + } + + /// Performs a fold operation over the entire iterator, returning the + /// eventual state at the end of the iteration. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// assert!(a.iter().fold(0, |a, &b| a + b) == 15); + /// ~~~ + #[inline] + fn fold(&mut self, init: B, f: &fn(B, A) -> B) -> B { + let mut accum = init; + loop { + match self.next() { + Some(x) => { accum = f(accum, x); } + None => { break; } + } + } + accum + } + + /// Counts the number of elements in this iterator. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// let mut it = a.iter(); + /// assert!(it.len() == 5); + /// assert!(it.len() == 0); + /// ~~~ + #[inline] + fn len(&mut self) -> uint { + self.fold(0, |cnt, _x| cnt + 1) + } + + /// Tests whether the predicate holds true for all elements in the iterator. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// assert!(a.iter().all(|&x| *x > 0)); + /// assert!(!a.iter().all(|&x| *x > 2)); + /// ~~~ + #[inline] + fn all(&mut self, f: &fn(A) -> bool) -> bool { + for x in *self { if !f(x) { return false; } } + true + } + + /// Tests whether any element of an iterator satisfies the specified + /// predicate. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// let mut it = a.iter(); + /// assert!(it.any(|&x| *x == 3)); + /// assert!(!it.any(|&x| *x == 3)); + /// ~~~ + #[inline] + fn any(&mut self, f: &fn(A) -> bool) -> bool { + for x in *self { if f(x) { return true; } } + false + } + + /// Return the first element satisfying the specified predicate + #[inline] + fn find(&mut self, predicate: &fn(&A) -> bool) -> Option { + for x in *self { + if predicate(&x) { return Some(x) } + } + None + } + + /// Return the index of the first element satisfying the specified predicate + #[inline] + fn position(&mut self, predicate: &fn(A) -> bool) -> Option { + let mut i = 0; + for x in *self { + if predicate(x) { + return Some(i); + } + i += 1; + } + None + } + + /// Count the number of elements satisfying the specified predicate + #[inline] + fn count(&mut self, predicate: &fn(A) -> bool) -> uint { + let mut i = 0; + for x in *self { + if predicate(x) { i += 1 } + } + i + } + + /// Return the element that gives the maximum value from the + /// specified function. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let xs = [-3, 0, 1, 5, -10]; + /// assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10); + /// ~~~ + #[inline] + fn max_by(&mut self, f: &fn(&A) -> B) -> Option { + self.fold(None, |max: Option<(A, B)>, x| { + let x_val = f(&x); + match max { + None => Some((x, x_val)), + Some((y, y_val)) => if x_val > y_val { + Some((x, x_val)) + } else { + Some((y, y_val)) + } + } + }).map_move(|(x, _)| x) + } + + /// Return the element that gives the minimum value from the + /// specified function. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let xs = [-3, 0, 1, 5, -10]; + /// assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0); + /// ~~~ + #[inline] + fn min_by(&mut self, f: &fn(&A) -> B) -> Option { + self.fold(None, |min: Option<(A, B)>, x| { + let x_val = f(&x); + match min { + None => Some((x, x_val)), + Some((y, y_val)) => if x_val < y_val { + Some((x, x_val)) + } else { + Some((y, y_val)) + } + } + }).map_move(|(x, _)| x) + } +} + +/// A range iterator able to yield elements from both ends +pub trait DoubleEndedIterator: Iterator { + /// Yield an element from the end of the range, returning `None` if the range is empty. + fn next_back(&mut self) -> Option; + + /// Flip the direction of the iterator + /// + /// The inverted iterator flips the ends on an iterator that can already + /// be iterated from the front and from the back. + /// + /// + /// If the iterator also implements RandomAccessIterator, the inverted + /// iterator is also random access, with the indices starting at the back + /// of the original iterator. + /// + /// Note: Random access with inverted indices still only applies to the first + /// `uint::max_value` elements of the original iterator. + #[inline] + fn invert(self) -> Invert { + Invert{iter: self} + } +} + +/// A double-ended iterator yielding mutable references +pub trait MutableDoubleEndedIterator { + // FIXME: #5898: should be called `reverse` + /// Use an iterator to reverse a container in-place + fn reverse_(&mut self); +} + +impl<'self, A, T: DoubleEndedIterator<&'self mut A>> MutableDoubleEndedIterator for T { + // FIXME: #5898: should be called `reverse` + /// Use an iterator to reverse a container in-place + fn reverse_(&mut self) { + loop { + match (self.next(), self.next_back()) { + (Some(x), Some(y)) => util::swap(x, y), + _ => break + } + } + } +} + + +/// An object implementing random access indexing by `uint` +/// +/// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`. +pub trait RandomAccessIterator: Iterator { + /// Return the number of indexable elements. At most `std::uint::max_value` + /// elements are indexable, even if the iterator represents a longer range. + fn indexable(&self) -> uint; + + /// Return an element at an index + fn idx(&self, index: uint) -> Option; +} + +/// An iterator that knows its exact length +/// +/// This trait is a helper for iterators like the vector iterator, so that +/// it can support double-ended enumeration. +/// +/// `Iterator::size_hint` *must* return the exact size of the iterator. +/// Note that the size must fit in `uint`. +pub trait ExactSize : DoubleEndedIterator { + /// Return the index of the last element satisfying the specified predicate + /// + /// If no element matches, None is returned. + #[inline] + fn rposition(&mut self, predicate: &fn(A) -> bool) -> Option { + let (lower, upper) = self.size_hint(); + assert!(upper == Some(lower)); + let mut i = lower; + loop { + match self.next_back() { + None => break, + Some(x) => { + i = match i.checked_sub(&1) { + Some(x) => x, + None => fail!("rposition: incorrect ExactSize") + }; + if predicate(x) { + return Some(i) + } + } + } + } + None + } +} + +// All adaptors that preserve the size of the wrapped iterator are fine +// Adaptors that may overflow in `size_hint` are not, i.e. `Chain`. +impl> ExactSize<(uint, A)> for Enumerate {} +impl<'self, A, T: ExactSize> ExactSize for Inspect<'self, A, T> {} +impl> ExactSize for Invert {} +impl<'self, A, B, T: ExactSize> ExactSize for Map<'self, A, B, T> {} +impl, U: ExactSize> ExactSize<(A, B)> for Zip {} + +/// An double-ended iterator with the direction inverted +#[deriving(Clone)] +pub struct Invert { + priv iter: T +} + +impl> Iterator for Invert { + #[inline] + fn next(&mut self) -> Option { self.iter.next_back() } + #[inline] + fn size_hint(&self) -> (uint, Option) { self.iter.size_hint() } +} + +impl> DoubleEndedIterator for Invert { + #[inline] + fn next_back(&mut self) -> Option { self.iter.next() } +} + +impl + RandomAccessIterator> RandomAccessIterator + for Invert { + #[inline] + fn indexable(&self) -> uint { self.iter.indexable() } + #[inline] + fn idx(&self, index: uint) -> Option { + self.iter.idx(self.indexable() - index - 1) + } +} + +/// A trait for iterators over elements which can be added together +pub trait AdditiveIterator { + /// Iterates over the entire iterator, summing up all the elements + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// let mut it = a.iter().map(|&x| x); + /// assert!(it.sum() == 15); + /// ~~~ + fn sum(&mut self) -> A; +} + +impl + Zero, T: Iterator> AdditiveIterator for T { + #[inline] + fn sum(&mut self) -> A { + let zero: A = Zero::zero(); + self.fold(zero, |s, x| s + x) + } +} + +/// A trait for iterators over elements whose elements can be multiplied +/// together. +pub trait MultiplicativeIterator { + /// Iterates over the entire iterator, multiplying all the elements + /// + /// # Example + /// + /// ~~~ {.rust} + /// use std::iter::count; + /// + /// fn factorial(n: uint) -> uint { + /// count(1u, 1).take_while(|&i| i <= n).product() + /// } + /// assert!(factorial(0) == 1); + /// assert!(factorial(1) == 1); + /// assert!(factorial(5) == 120); + /// ~~~ + fn product(&mut self) -> A; +} + +impl + One, T: Iterator> MultiplicativeIterator for T { + #[inline] + fn product(&mut self) -> A { + let one: A = One::one(); + self.fold(one, |p, x| p * x) + } +} + +/// A trait for iterators over elements which can be compared to one another. +/// The type of each element must ascribe to the `Ord` trait. +pub trait OrdIterator { + /// Consumes the entire iterator to return the maximum element. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// assert!(a.iter().max().get() == &5); + /// ~~~ + fn max(&mut self) -> Option; + + /// Consumes the entire iterator to return the minimum element. + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = [1, 2, 3, 4, 5]; + /// assert!(a.iter().min().get() == &1); + /// ~~~ + fn min(&mut self) -> Option; +} + +impl> OrdIterator for T { + #[inline] + fn max(&mut self) -> Option { + self.fold(None, |max, x| { + match max { + None => Some(x), + Some(y) => Some(cmp::max(x, y)) + } + }) + } + + #[inline] + fn min(&mut self) -> Option { + self.fold(None, |min, x| { + match min { + None => Some(x), + Some(y) => Some(cmp::min(x, y)) + } + }) + } +} + +/// A trait for iterators that are clonable. +pub trait ClonableIterator { + /// Repeats an iterator endlessly + /// + /// # Example + /// + /// ~~~ {.rust} + /// let a = count(1,1).take(1); + /// let mut cy = a.cycle(); + /// assert_eq!(cy.next(), Some(1)); + /// assert_eq!(cy.next(), Some(1)); + /// ~~~ + fn cycle(self) -> Cycle; +} + +impl> ClonableIterator for T { + #[inline] + fn cycle(self) -> Cycle { + Cycle{orig: self.clone(), iter: self} + } +} + +/// An iterator that repeats endlessly +#[deriving(Clone)] +pub struct Cycle { + priv orig: T, + priv iter: T, +} + +impl> Iterator for Cycle { + #[inline] + fn next(&mut self) -> Option { + match self.iter.next() { + None => { self.iter = self.orig.clone(); self.iter.next() } + y => y + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + // the cycle iterator is either empty or infinite + match self.orig.size_hint() { + sz @ (0, Some(0)) => sz, + (0, _) => (0, None), + _ => (uint::max_value, None) + } + } +} + +impl> RandomAccessIterator for Cycle { + #[inline] + fn indexable(&self) -> uint { + if self.orig.indexable() > 0 { + uint::max_value + } else { + 0 + } + } + + #[inline] + fn idx(&self, index: uint) -> Option { + let liter = self.iter.indexable(); + let lorig = self.orig.indexable(); + if lorig == 0 { + None + } else if index < liter { + self.iter.idx(index) + } else { + self.orig.idx((index - liter) % lorig) + } + } +} + +/// An iterator which strings two iterators together +#[deriving(Clone)] +pub struct Chain { + priv a: T, + priv b: U, + priv flag: bool +} + +impl, U: Iterator> Iterator for Chain { + #[inline] + fn next(&mut self) -> Option { + if self.flag { + self.b.next() + } else { + match self.a.next() { + Some(x) => return Some(x), + _ => () + } + self.flag = true; + self.b.next() + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + let (a_lower, a_upper) = self.a.size_hint(); + let (b_lower, b_upper) = self.b.size_hint(); + + let lower = a_lower.saturating_add(b_lower); + + let upper = match (a_upper, b_upper) { + (Some(x), Some(y)) => x.checked_add(&y), + _ => None + }; + + (lower, upper) + } +} + +impl, U: DoubleEndedIterator> DoubleEndedIterator +for Chain { + #[inline] + fn next_back(&mut self) -> Option { + match self.b.next_back() { + Some(x) => Some(x), + None => self.a.next_back() + } + } +} + +impl, U: RandomAccessIterator> RandomAccessIterator +for Chain { + #[inline] + fn indexable(&self) -> uint { + let (a, b) = (self.a.indexable(), self.b.indexable()); + a.saturating_add(b) + } + + #[inline] + fn idx(&self, index: uint) -> Option { + let len = self.a.indexable(); + if index < len { + self.a.idx(index) + } else { + self.b.idx(index - len) + } + } +} + +/// An iterator which iterates two other iterators simultaneously +#[deriving(Clone)] +pub struct Zip { + priv a: T, + priv b: U +} + +impl, U: Iterator> Iterator<(A, B)> for Zip { + #[inline] + fn next(&mut self) -> Option<(A, B)> { + match self.a.next() { + None => None, + Some(x) => match self.b.next() { + None => None, + Some(y) => Some((x, y)) + } + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + let (a_lower, a_upper) = self.a.size_hint(); + let (b_lower, b_upper) = self.b.size_hint(); + + let lower = cmp::min(a_lower, b_lower); + + let upper = match (a_upper, b_upper) { + (Some(x), Some(y)) => Some(cmp::min(x,y)), + (Some(x), None) => Some(x), + (None, Some(y)) => Some(y), + (None, None) => None + }; + + (lower, upper) + } +} + +impl, U: ExactSize> DoubleEndedIterator<(A, B)> +for Zip { + #[inline] + fn next_back(&mut self) -> Option<(A, B)> { + let (a_sz, a_upper) = self.a.size_hint(); + let (b_sz, b_upper) = self.b.size_hint(); + assert!(a_upper == Some(a_sz)); + assert!(b_upper == Some(b_sz)); + if a_sz < b_sz { + for _ in range(0, b_sz - a_sz) { self.b.next_back(); } + } else if a_sz > b_sz { + for _ in range(0, a_sz - b_sz) { self.a.next_back(); } + } + let (a_sz, _) = self.a.size_hint(); + let (b_sz, _) = self.b.size_hint(); + assert!(a_sz == b_sz); + match (self.a.next_back(), self.b.next_back()) { + (Some(x), Some(y)) => Some((x, y)), + _ => None + } + } +} + +impl, U: RandomAccessIterator> +RandomAccessIterator<(A, B)> for Zip { + #[inline] + fn indexable(&self) -> uint { + cmp::min(self.a.indexable(), self.b.indexable()) + } + + #[inline] + fn idx(&self, index: uint) -> Option<(A, B)> { + match self.a.idx(index) { + None => None, + Some(x) => match self.b.idx(index) { + None => None, + Some(y) => Some((x, y)) + } + } + } +} + +/// An iterator which maps the values of `iter` with `f` +pub struct Map<'self, A, B, T> { + priv iter: T, + priv f: &'self fn(A) -> B +} + +impl<'self, A, B, T> Map<'self, A, B, T> { + #[inline] + fn do_map(&self, elt: Option) -> Option { + match elt { + Some(a) => Some((self.f)(a)), + _ => None + } + } +} + +impl<'self, A, B, T: Iterator> Iterator for Map<'self, A, B, T> { + #[inline] + fn next(&mut self) -> Option { + let next = self.iter.next(); + self.do_map(next) + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + self.iter.size_hint() + } +} + +impl<'self, A, B, T: DoubleEndedIterator> DoubleEndedIterator for Map<'self, A, B, T> { + #[inline] + fn next_back(&mut self) -> Option { + let next = self.iter.next_back(); + self.do_map(next) + } +} + +impl<'self, A, B, T: RandomAccessIterator> RandomAccessIterator for Map<'self, A, B, T> { + #[inline] + fn indexable(&self) -> uint { + self.iter.indexable() + } + + #[inline] + fn idx(&self, index: uint) -> Option { + self.do_map(self.iter.idx(index)) + } +} + +/// An iterator which filters the elements of `iter` with `predicate` +pub struct Filter<'self, A, T> { + priv iter: T, + priv predicate: &'self fn(&A) -> bool +} + +impl<'self, A, T: Iterator> Iterator for Filter<'self, A, T> { + #[inline] + fn next(&mut self) -> Option { + for x in self.iter { + if (self.predicate)(&x) { + return Some(x); + } else { + loop + } + } + None + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + let (_, upper) = self.iter.size_hint(); + (0, upper) // can't know a lower bound, due to the predicate + } +} + +impl<'self, A, T: DoubleEndedIterator> DoubleEndedIterator for Filter<'self, A, T> { + #[inline] + fn next_back(&mut self) -> Option { + loop { + match self.iter.next_back() { + None => return None, + Some(x) => { + if (self.predicate)(&x) { + return Some(x); + } else { + loop + } + } + } + } + } +} + +/// An iterator which uses `f` to both filter and map elements from `iter` +pub struct FilterMap<'self, A, B, T> { + priv iter: T, + priv f: &'self fn(A) -> Option +} + +impl<'self, A, B, T: Iterator> Iterator for FilterMap<'self, A, B, T> { + #[inline] + fn next(&mut self) -> Option { + for x in self.iter { + match (self.f)(x) { + Some(y) => return Some(y), + None => () + } + } + None + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + let (_, upper) = self.iter.size_hint(); + (0, upper) // can't know a lower bound, due to the predicate + } +} + +impl<'self, A, B, T: DoubleEndedIterator> DoubleEndedIterator +for FilterMap<'self, A, B, T> { + #[inline] + fn next_back(&mut self) -> Option { + loop { + match self.iter.next_back() { + None => return None, + Some(x) => { + match (self.f)(x) { + Some(y) => return Some(y), + None => () + } + } + } + } + } +} + +/// An iterator which yields the current count and the element during iteration +#[deriving(Clone)] +pub struct Enumerate { + priv iter: T, + priv count: uint +} + +impl> Iterator<(uint, A)> for Enumerate { + #[inline] + fn next(&mut self) -> Option<(uint, A)> { + match self.iter.next() { + Some(a) => { + let ret = Some((self.count, a)); + self.count += 1; + ret + } + _ => None + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + self.iter.size_hint() + } +} + +impl> DoubleEndedIterator<(uint, A)> for Enumerate { + #[inline] + fn next_back(&mut self) -> Option<(uint, A)> { + match self.iter.next_back() { + Some(a) => { + let (lower, upper) = self.iter.size_hint(); + assert!(upper == Some(lower)); + Some((self.count + lower, a)) + } + _ => None + } + } +} + +impl> RandomAccessIterator<(uint, A)> for Enumerate { + #[inline] + fn indexable(&self) -> uint { + self.iter.indexable() + } + + #[inline] + fn idx(&self, index: uint) -> Option<(uint, A)> { + match self.iter.idx(index) { + Some(a) => Some((self.count + index, a)), + _ => None, + } + } +} + +/// An iterator with a `peek()` that returns an optional reference to the next element. +pub struct Peekable { + priv iter: T, + priv peeked: Option, +} + +impl> Iterator for Peekable { + #[inline] + fn next(&mut self) -> Option { + if self.peeked.is_some() { self.peeked.take() } + else { self.iter.next() } + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + let (lo, hi) = self.iter.size_hint(); + if self.peeked.is_some() { + let lo = lo.saturating_add(1); + let hi = match hi { + Some(x) => x.checked_add(&1), + None => None + }; + (lo, hi) + } else { + (lo, hi) + } + } +} + +impl<'self, A, T: Iterator> Peekable { + /// Return a reference to the next element of the iterator with out advancing it, + /// or None if the iterator is exhausted. + #[inline] + pub fn peek(&'self mut self) -> Option<&'self A> { + if self.peeked.is_none() { + self.peeked = self.iter.next(); + } + match self.peeked { + Some(ref value) => Some(value), + None => None, + } + } +} + +/// An iterator which rejects elements while `predicate` is true +pub struct SkipWhile<'self, A, T> { + priv iter: T, + priv flag: bool, + priv predicate: &'self fn(&A) -> bool +} + +impl<'self, A, T: Iterator> Iterator for SkipWhile<'self, A, T> { + #[inline] + fn next(&mut self) -> Option { + let mut next = self.iter.next(); + if self.flag { + next + } else { + loop { + match next { + Some(x) => { + if (self.predicate)(&x) { + next = self.iter.next(); + loop + } else { + self.flag = true; + return Some(x) + } + } + None => return None + } + } + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + let (_, upper) = self.iter.size_hint(); + (0, upper) // can't know a lower bound, due to the predicate + } +} + +/// An iterator which only accepts elements while `predicate` is true +pub struct TakeWhile<'self, A, T> { + priv iter: T, + priv flag: bool, + priv predicate: &'self fn(&A) -> bool +} + +impl<'self, A, T: Iterator> Iterator for TakeWhile<'self, A, T> { + #[inline] + fn next(&mut self) -> Option { + if self.flag { + None + } else { + match self.iter.next() { + Some(x) => { + if (self.predicate)(&x) { + Some(x) + } else { + self.flag = true; + None + } + } + None => None + } + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + let (_, upper) = self.iter.size_hint(); + (0, upper) // can't know a lower bound, due to the predicate + } +} + +/// An iterator which skips over `n` elements of `iter`. +#[deriving(Clone)] +pub struct Skip { + priv iter: T, + priv n: uint +} + +impl> Iterator for Skip { + #[inline] + fn next(&mut self) -> Option { + let mut next = self.iter.next(); + if self.n == 0 { + next + } else { + let mut n = self.n; + while n > 0 { + n -= 1; + match next { + Some(_) => { + next = self.iter.next(); + loop + } + None => { + self.n = 0; + return None + } + } + } + self.n = 0; + next + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + let (lower, upper) = self.iter.size_hint(); + + let lower = lower.saturating_sub(self.n); + + let upper = match upper { + Some(x) => Some(x.saturating_sub(self.n)), + None => None + }; + + (lower, upper) + } +} + +impl> RandomAccessIterator for Skip { + #[inline] + fn indexable(&self) -> uint { + self.iter.indexable().saturating_sub(self.n) + } + + #[inline] + fn idx(&self, index: uint) -> Option { + if index >= self.indexable() { + None + } else { + self.iter.idx(index + self.n) + } + } +} + +/// An iterator which only iterates over the first `n` iterations of `iter`. +#[deriving(Clone)] +pub struct Take { + priv iter: T, + priv n: uint +} + +impl> Iterator for Take { + #[inline] + fn next(&mut self) -> Option { + if self.n != 0 { + self.n -= 1; + self.iter.next() + } else { + None + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + let (lower, upper) = self.iter.size_hint(); + + let lower = cmp::min(lower, self.n); + + let upper = match upper { + Some(x) if x < self.n => Some(x), + _ => Some(self.n) + }; + + (lower, upper) + } +} + +impl> RandomAccessIterator for Take { + #[inline] + fn indexable(&self) -> uint { + cmp::min(self.iter.indexable(), self.n) + } + + #[inline] + fn idx(&self, index: uint) -> Option { + if index >= self.n { + None + } else { + self.iter.idx(index) + } + } +} + + +/// An iterator to maintain state while iterating another iterator +pub struct Scan<'self, A, B, T, St> { + priv iter: T, + priv f: &'self fn(&mut St, A) -> Option, + + /// The current internal state to be passed to the closure next. + state: St +} + +impl<'self, A, B, T: Iterator, St> Iterator for Scan<'self, A, B, T, St> { + #[inline] + fn next(&mut self) -> Option { + self.iter.next().chain(|a| (self.f)(&mut self.state, a)) + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + let (_, upper) = self.iter.size_hint(); + (0, upper) // can't know a lower bound, due to the scan function + } +} + +/// An iterator that maps each element to an iterator, +/// and yields the elements of the produced iterators +/// +pub struct FlatMap<'self, A, T, U> { + priv iter: T, + priv f: &'self fn(A) -> U, + priv frontiter: Option, + priv backiter: Option, +} + +impl<'self, A, T: Iterator, B, U: Iterator> Iterator for + FlatMap<'self, A, T, U> { + #[inline] + fn next(&mut self) -> Option { + loop { + for inner in self.frontiter.mut_iter() { + for x in *inner { + return Some(x) + } + } + match self.iter.next().map_move(|x| (self.f)(x)) { + None => return self.backiter.chain_mut_ref(|it| it.next()), + next => self.frontiter = next, + } + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + let (flo, fhi) = self.frontiter.map_default((0, Some(0)), |it| it.size_hint()); + let (blo, bhi) = self.backiter.map_default((0, Some(0)), |it| it.size_hint()); + let lo = flo.saturating_add(blo); + match (self.iter.size_hint(), fhi, bhi) { + ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(&b)), + _ => (lo, None) + } + } +} + +impl<'self, + A, T: DoubleEndedIterator, + B, U: DoubleEndedIterator> DoubleEndedIterator + for FlatMap<'self, A, T, U> { + #[inline] + fn next_back(&mut self) -> Option { + loop { + for inner in self.backiter.mut_iter() { + match inner.next_back() { + None => (), + y => return y + } + } + match self.iter.next_back().map_move(|x| (self.f)(x)) { + None => return self.frontiter.chain_mut_ref(|it| it.next_back()), + next => self.backiter = next, + } + } + } +} + +/// An iterator that yields `None` forever after the underlying iterator +/// yields `None` once. +#[deriving(Clone, DeepClone)] +pub struct Fuse { + priv iter: T, + priv done: bool +} + +impl> Iterator for Fuse { + #[inline] + fn next(&mut self) -> Option { + if self.done { + None + } else { + match self.iter.next() { + None => { + self.done = true; + None + } + x => x + } + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + if self.done { + (0, Some(0)) + } else { + self.iter.size_hint() + } + } +} + +impl> DoubleEndedIterator for Fuse { + #[inline] + fn next_back(&mut self) -> Option { + if self.done { + None + } else { + match self.iter.next_back() { + None => { + self.done = true; + None + } + x => x + } + } + } +} + +// Allow RandomAccessIterators to be fused without affecting random-access behavior +impl> RandomAccessIterator for Fuse { + #[inline] + fn indexable(&self) -> uint { + self.iter.indexable() + } + + #[inline] + fn idx(&self, index: uint) -> Option { + self.iter.idx(index) + } +} + +impl Fuse { + /// Resets the fuse such that the next call to .next() or .next_back() will + /// call the underlying iterator again even if it prevously returned None. + #[inline] + fn reset_fuse(&mut self) { + self.done = false + } +} + +/// An iterator that calls a function with a reference to each +/// element before yielding it. +pub struct Inspect<'self, A, T> { + priv iter: T, + priv f: &'self fn(&A) +} + +impl<'self, A, T> Inspect<'self, A, T> { + #[inline] + fn do_inspect(&self, elt: Option) -> Option { + match elt { + Some(ref a) => (self.f)(a), + None => () + } + + elt + } +} + +impl<'self, A, T: Iterator> Iterator for Inspect<'self, A, T> { + #[inline] + fn next(&mut self) -> Option { + let next = self.iter.next(); + self.do_inspect(next) + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + self.iter.size_hint() + } +} + +impl<'self, A, T: DoubleEndedIterator> DoubleEndedIterator +for Inspect<'self, A, T> { + #[inline] + fn next_back(&mut self) -> Option { + let next = self.iter.next_back(); + self.do_inspect(next) + } +} + +impl<'self, A, T: RandomAccessIterator> RandomAccessIterator +for Inspect<'self, A, T> { + #[inline] + fn indexable(&self) -> uint { + self.iter.indexable() + } + + #[inline] + fn idx(&self, index: uint) -> Option { + self.do_inspect(self.iter.idx(index)) + } +} + +/// An iterator which just modifies the contained state throughout iteration. +pub struct Unfold<'self, A, St> { + priv f: &'self fn(&mut St) -> Option, + /// Internal state that will be yielded on the next iteration + state: St +} + +impl<'self, A, St> Unfold<'self, A, St> { + /// Creates a new iterator with the specified closure as the "iterator + /// function" and an initial state to eventually pass to the iterator + #[inline] + pub fn new<'a>(initial_state: St, f: &'a fn(&mut St) -> Option) + -> Unfold<'a, A, St> { + Unfold { + f: f, + state: initial_state + } + } +} + +impl<'self, A, St> Iterator for Unfold<'self, A, St> { + #[inline] + fn next(&mut self) -> Option { + (self.f)(&mut self.state) + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + // no possible known bounds at this point + (0, None) + } +} + +/// An infinite iterator starting at `start` and advancing by `step` with each +/// iteration +#[deriving(Clone)] +pub struct Counter { + /// The current state the counter is at (next value to be yielded) + state: A, + /// The amount that this iterator is stepping by + step: A +} + +/// Creates a new counter with the specified start/step +#[inline] +pub fn count(start: A, step: A) -> Counter { + Counter{state: start, step: step} +} + +/// A range of numbers from [0, N) +#[deriving(Clone, DeepClone)] +pub struct Range { + priv state: A, + priv stop: A, + priv one: A +} + +/// Return an iterator over the range [start, stop) +#[inline] +pub fn range + Ord + Clone + One>(start: A, stop: A) -> Range { + Range{state: start, stop: stop, one: One::one()} +} + +impl + Ord + Clone> Iterator for Range { + #[inline] + fn next(&mut self) -> Option { + if self.state < self.stop { + let result = self.state.clone(); + self.state = self.state + self.one; + Some(result) + } else { + None + } + } + + // FIXME: #8606 Implement size_hint() on Range + // Blocked on #8605 Need numeric trait for converting to `Option` +} + +impl + Integer + Ord + Clone> DoubleEndedIterator for Range { + #[inline] + fn next_back(&mut self) -> Option { + if self.stop > self.state { + // Integer doesn't technically define this rule, but we're going to assume that every + // Integer is reachable from every other one by adding or subtracting enough Ones. This + // seems like a reasonable-enough rule that every Integer should conform to, even if it + // can't be statically checked. + self.stop = self.stop - self.one; + Some(self.stop.clone()) + } else { + None + } + } +} + +/// A range of numbers from [0, N] +#[deriving(Clone, DeepClone)] +pub struct RangeInclusive { + priv range: Range, + priv done: bool +} + +/// Return an iterator over the range [start, stop] +#[inline] +pub fn range_inclusive + Ord + Clone + One>(start: A, stop: A) -> RangeInclusive { + RangeInclusive{range: range(start, stop), done: false} +} + +impl + Ord + Clone> Iterator for RangeInclusive { + #[inline] + fn next(&mut self) -> Option { + match self.range.next() { + Some(x) => Some(x), + None => { + if self.done { + None + } else { + self.done = true; + Some(self.range.stop.clone()) + } + } + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + let (lo, hi) = self.range.size_hint(); + if self.done { + (lo, hi) + } else { + let lo = lo.saturating_add(1); + let hi = match hi { + Some(x) => x.checked_add(&1), + None => None + }; + (lo, hi) + } + } +} + +impl + Integer + Ord + Clone> DoubleEndedIterator for RangeInclusive { + #[inline] + fn next_back(&mut self) -> Option { + if self.range.stop > self.range.state { + let result = self.range.stop.clone(); + self.range.stop = self.range.stop - self.range.one; + Some(result) + } else if self.done { + None + } else { + self.done = true; + Some(self.range.stop.clone()) + } + } +} + +impl + Clone> Iterator for Counter { + #[inline] + fn next(&mut self) -> Option { + let result = self.state.clone(); + self.state = self.state + self.step; + Some(result) + } + + #[inline] + fn size_hint(&self) -> (uint, Option) { + (uint::max_value, None) // Too bad we can't specify an infinite lower bound + } +} + +/// An iterator that repeats an element endlessly +#[deriving(Clone, DeepClone)] +pub struct Repeat { + priv element: A +} + +impl Repeat { + /// Create a new `Repeat` that endlessly repeats the element `elt`. + #[inline] + pub fn new(elt: A) -> Repeat { + Repeat{element: elt} + } +} + +impl Iterator for Repeat { + #[inline] + fn next(&mut self) -> Option { self.idx(0) } + #[inline] + fn size_hint(&self) -> (uint, Option) { (uint::max_value, None) } +} + +impl DoubleEndedIterator for Repeat { + #[inline] + fn next_back(&mut self) -> Option { self.idx(0) } +} + +impl RandomAccessIterator for Repeat { + #[inline] + fn indexable(&self) -> uint { uint::max_value } + #[inline] + fn idx(&self, _: uint) -> Option { Some(self.element.clone()) } +} + +/// Functions for lexicographical ordering of sequences. +/// +/// Lexicographical ordering through `<`, `<=`, `>=`, `>` requires +/// that the elements implement both `Eq` and `Ord`. +/// +/// If two sequences are equal up until the point where one ends, +/// the shorter sequence compares less. +pub mod order { + use cmp; + use cmp::{TotalEq, TotalOrd, Ord, Eq}; + use option::{Some, None}; + use super::Iterator; + + /// Compare `a` and `b` for equality using `TotalOrd` + pub fn equals>(mut a: T, mut b: T) -> bool { + loop { + match (a.next(), b.next()) { + (None, None) => return true, + (None, _) | (_, None) => return false, + (Some(x), Some(y)) => if !x.equals(&y) { return false }, + } + } + } + + /// Order `a` and `b` lexicographically using `TotalOrd` + pub fn cmp>(mut a: T, mut b: T) -> cmp::Ordering { + loop { + match (a.next(), b.next()) { + (None, None) => return cmp::Equal, + (None, _ ) => return cmp::Less, + (_ , None) => return cmp::Greater, + (Some(x), Some(y)) => match x.cmp(&y) { + cmp::Equal => (), + non_eq => return non_eq, + }, + } + } + } + + /// Compare `a` and `b` for equality (Using partial equality, `Eq`) + pub fn eq>(mut a: T, mut b: T) -> bool { + loop { + match (a.next(), b.next()) { + (None, None) => return true, + (None, _) | (_, None) => return false, + (Some(x), Some(y)) => if !x.eq(&y) { return false }, + } + } + } + + /// Compare `a` and `b` for nonequality (Using partial equality, `Eq`) + pub fn ne>(mut a: T, mut b: T) -> bool { + loop { + match (a.next(), b.next()) { + (None, None) => return false, + (None, _) | (_, None) => return true, + (Some(x), Some(y)) => if x.ne(&y) { return true }, + } + } + } + + /// Return `a` < `b` lexicographically (Using partial order, `Ord`) + pub fn lt>(mut a: T, mut b: T) -> bool { + loop { + match (a.next(), b.next()) { + (None, None) => return false, + (None, _ ) => return true, + (_ , None) => return false, + (Some(x), Some(y)) => if x.ne(&y) { return x.lt(&y) }, + } + } + } + + /// Return `a` <= `b` lexicographically (Using partial order, `Ord`) + pub fn le>(mut a: T, mut b: T) -> bool { + loop { + match (a.next(), b.next()) { + (None, None) => return true, + (None, _ ) => return true, + (_ , None) => return false, + (Some(x), Some(y)) => if x.ne(&y) { return x.le(&y) }, + } + } + } + + /// Return `a` > `b` lexicographically (Using partial order, `Ord`) + pub fn gt>(mut a: T, mut b: T) -> bool { + loop { + match (a.next(), b.next()) { + (None, None) => return false, + (None, _ ) => return false, + (_ , None) => return true, + (Some(x), Some(y)) => if x.ne(&y) { return x.gt(&y) }, + } + } + } + + /// Return `a` >= `b` lexicographically (Using partial order, `Ord`) + pub fn ge>(mut a: T, mut b: T) -> bool { + loop { + match (a.next(), b.next()) { + (None, None) => return true, + (None, _ ) => return false, + (_ , None) => return true, + (Some(x), Some(y)) => if x.ne(&y) { return x.ge(&y) }, + } + } + } + + #[test] + fn test_lt() { + use vec::ImmutableVector; + + let empty: [int, ..0] = []; + let xs = [1,2,3]; + let ys = [1,2,0]; + + assert!(!lt(xs.iter(), ys.iter())); + assert!(!le(xs.iter(), ys.iter())); + assert!( gt(xs.iter(), ys.iter())); + assert!( ge(xs.iter(), ys.iter())); + + assert!( lt(ys.iter(), xs.iter())); + assert!( le(ys.iter(), xs.iter())); + assert!(!gt(ys.iter(), xs.iter())); + assert!(!ge(ys.iter(), xs.iter())); + + assert!( lt(empty.iter(), xs.iter())); + assert!( le(empty.iter(), xs.iter())); + assert!(!gt(empty.iter(), xs.iter())); + assert!(!ge(empty.iter(), xs.iter())); + + // Sequence with NaN + let u = [1.0, 2.0]; + let v = [0.0/0.0, 3.0]; + + assert!(!lt(u.iter(), v.iter())); + assert!(!le(u.iter(), v.iter())); + assert!(!gt(u.iter(), v.iter())); + assert!(!ge(u.iter(), v.iter())); + + let a = [0.0/0.0]; + let b = [1.0]; + let c = [2.0]; + + assert!(lt(a.iter(), b.iter()) == (a[0] < b[0])); + assert!(le(a.iter(), b.iter()) == (a[0] <= b[0])); + assert!(gt(a.iter(), b.iter()) == (a[0] > b[0])); + assert!(ge(a.iter(), b.iter()) == (a[0] >= b[0])); + + assert!(lt(c.iter(), b.iter()) == (c[0] < b[0])); + assert!(le(c.iter(), b.iter()) == (c[0] <= b[0])); + assert!(gt(c.iter(), b.iter()) == (c[0] > b[0])); + assert!(ge(c.iter(), b.iter()) == (c[0] >= b[0])); + } +} + +#[cfg(test)] +mod tests { + use super::*; + use prelude::*; + + use cmp; + use uint; + + #[test] + fn test_counter_from_iter() { + let mut it = count(0, 5).take(10); + let xs: ~[int] = FromIterator::from_iterator(&mut it); + assert_eq!(xs, ~[0, 5, 10, 15, 20, 25, 30, 35, 40, 45]); + } + + #[test] + fn test_iterator_chain() { + let xs = [0u, 1, 2, 3, 4, 5]; + let ys = [30u, 40, 50, 60]; + let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60]; + let mut it = xs.iter().chain(ys.iter()); + let mut i = 0; + for &x in it { + assert_eq!(x, expected[i]); + i += 1; + } + assert_eq!(i, expected.len()); + + let ys = count(30u, 10).take(4); + let mut it = xs.iter().map(|&x| x).chain(ys); + let mut i = 0; + for x in it { + assert_eq!(x, expected[i]); + i += 1; + } + assert_eq!(i, expected.len()); + } + + #[test] + fn test_filter_map() { + let mut it = count(0u, 1u).take(10) + .filter_map(|x| if x.is_even() { Some(x*x) } else { None }); + assert_eq!(it.collect::<~[uint]>(), ~[0*0, 2*2, 4*4, 6*6, 8*8]); + } + + #[test] + fn test_iterator_enumerate() { + let xs = [0u, 1, 2, 3, 4, 5]; + let mut it = xs.iter().enumerate(); + for (i, &x) in it { + assert_eq!(i, x); + } + } + + #[test] + fn test_iterator_peekable() { + let xs = ~[0u, 1, 2, 3, 4, 5]; + let mut it = xs.iter().map(|&x|x).peekable(); + assert_eq!(it.peek().unwrap(), &0); + assert_eq!(it.next().unwrap(), 0); + assert_eq!(it.next().unwrap(), 1); + assert_eq!(it.next().unwrap(), 2); + assert_eq!(it.peek().unwrap(), &3); + assert_eq!(it.peek().unwrap(), &3); + assert_eq!(it.next().unwrap(), 3); + assert_eq!(it.next().unwrap(), 4); + assert_eq!(it.peek().unwrap(), &5); + assert_eq!(it.next().unwrap(), 5); + assert!(it.peek().is_none()); + assert!(it.next().is_none()); + } + + #[test] + fn test_iterator_take_while() { + let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19]; + let ys = [0u, 1, 2, 3, 5, 13]; + let mut it = xs.iter().take_while(|&x| *x < 15u); + let mut i = 0; + for &x in it { + assert_eq!(x, ys[i]); + i += 1; + } + assert_eq!(i, ys.len()); + } + + #[test] + fn test_iterator_skip_while() { + let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19]; + let ys = [15, 16, 17, 19]; + let mut it = xs.iter().skip_while(|&x| *x < 15u); + let mut i = 0; + for &x in it { + assert_eq!(x, ys[i]); + i += 1; + } + assert_eq!(i, ys.len()); + } + + #[test] + fn test_iterator_skip() { + let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30]; + let ys = [13, 15, 16, 17, 19, 20, 30]; + let mut it = xs.iter().skip(5); + let mut i = 0; + for &x in it { + assert_eq!(x, ys[i]); + i += 1; + } + assert_eq!(i, ys.len()); + } + + #[test] + fn test_iterator_take() { + let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19]; + let ys = [0u, 1, 2, 3, 5]; + let mut it = xs.iter().take(5); + let mut i = 0; + for &x in it { + assert_eq!(x, ys[i]); + i += 1; + } + assert_eq!(i, ys.len()); + } + + #[test] + fn test_iterator_scan() { + // test the type inference + fn add(old: &mut int, new: &uint) -> Option { + *old += *new as int; + Some(*old as float) + } + let xs = [0u, 1, 2, 3, 4]; + let ys = [0f, 1f, 3f, 6f, 10f]; + + let mut it = xs.iter().scan(0, add); + let mut i = 0; + for x in it { + assert_eq!(x, ys[i]); + i += 1; + } + assert_eq!(i, ys.len()); + } + + #[test] + fn test_iterator_flat_map() { + let xs = [0u, 3, 6]; + let ys = [0u, 1, 2, 3, 4, 5, 6, 7, 8]; + let mut it = xs.iter().flat_map(|&x| count(x, 1).take(3)); + let mut i = 0; + for x in it { + assert_eq!(x, ys[i]); + i += 1; + } + assert_eq!(i, ys.len()); + } + + #[test] + fn test_inspect() { + let xs = [1u, 2, 3, 4]; + let mut n = 0; + + let ys = xs.iter() + .map(|&x| x) + .inspect(|_| n += 1) + .collect::<~[uint]>(); + + assert_eq!(n, xs.len()); + assert_eq!(xs, ys.as_slice()); + } + + #[test] + fn test_unfoldr() { + fn count(st: &mut uint) -> Option { + if *st < 10 { + let ret = Some(*st); + *st += 1; + ret + } else { + None + } + } + + let mut it = Unfold::new(0, count); + let mut i = 0; + for counted in it { + assert_eq!(counted, i); + i += 1; + } + assert_eq!(i, 10); + } + + #[test] + fn test_cycle() { + let cycle_len = 3; + let it = count(0u, 1).take(cycle_len).cycle(); + assert_eq!(it.size_hint(), (uint::max_value, None)); + for (i, x) in it.take(100).enumerate() { + assert_eq!(i % cycle_len, x); + } + + let mut it = count(0u, 1).take(0).cycle(); + assert_eq!(it.size_hint(), (0, Some(0))); + assert_eq!(it.next(), None); + } + + #[test] + fn test_iterator_nth() { + let v = &[0, 1, 2, 3, 4]; + for i in range(0u, v.len()) { + assert_eq!(v.iter().nth(i).unwrap(), &v[i]); + } + } + + #[test] + fn test_iterator_last() { + let v = &[0, 1, 2, 3, 4]; + assert_eq!(v.iter().last().unwrap(), &4); + assert_eq!(v.slice(0, 1).iter().last().unwrap(), &0); + } + + #[test] + fn test_iterator_len() { + let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; + assert_eq!(v.slice(0, 4).iter().len(), 4); + assert_eq!(v.slice(0, 10).iter().len(), 10); + assert_eq!(v.slice(0, 0).iter().len(), 0); + } + + #[test] + fn test_iterator_sum() { + let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; + assert_eq!(v.slice(0, 4).iter().map(|&x| x).sum(), 6); + assert_eq!(v.iter().map(|&x| x).sum(), 55); + assert_eq!(v.slice(0, 0).iter().map(|&x| x).sum(), 0); + } + + #[test] + fn test_iterator_product() { + let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; + assert_eq!(v.slice(0, 4).iter().map(|&x| x).product(), 0); + assert_eq!(v.slice(1, 5).iter().map(|&x| x).product(), 24); + assert_eq!(v.slice(0, 0).iter().map(|&x| x).product(), 1); + } + + #[test] + fn test_iterator_max() { + let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; + assert_eq!(v.slice(0, 4).iter().map(|&x| x).max(), Some(3)); + assert_eq!(v.iter().map(|&x| x).max(), Some(10)); + assert_eq!(v.slice(0, 0).iter().map(|&x| x).max(), None); + } + + #[test] + fn test_iterator_min() { + let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; + assert_eq!(v.slice(0, 4).iter().map(|&x| x).min(), Some(0)); + assert_eq!(v.iter().map(|&x| x).min(), Some(0)); + assert_eq!(v.slice(0, 0).iter().map(|&x| x).min(), None); + } + + #[test] + fn test_iterator_size_hint() { + let c = count(0, 1); + let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; + let v2 = &[10, 11, 12]; + let vi = v.iter(); + + assert_eq!(c.size_hint(), (uint::max_value, None)); + assert_eq!(vi.size_hint(), (10, Some(10))); + + assert_eq!(c.take(5).size_hint(), (5, Some(5))); + assert_eq!(c.skip(5).size_hint().second(), None); + assert_eq!(c.take_while(|_| false).size_hint(), (0, None)); + assert_eq!(c.skip_while(|_| false).size_hint(), (0, None)); + assert_eq!(c.enumerate().size_hint(), (uint::max_value, None)); + assert_eq!(c.chain(vi.map(|&i| i)).size_hint(), (uint::max_value, None)); + assert_eq!(c.zip(vi).size_hint(), (10, Some(10))); + assert_eq!(c.scan(0, |_,_| Some(0)).size_hint(), (0, None)); + assert_eq!(c.filter(|_| false).size_hint(), (0, None)); + assert_eq!(c.map(|_| 0).size_hint(), (uint::max_value, None)); + assert_eq!(c.filter_map(|_| Some(0)).size_hint(), (0, None)); + + assert_eq!(vi.take(5).size_hint(), (5, Some(5))); + assert_eq!(vi.take(12).size_hint(), (10, Some(10))); + assert_eq!(vi.skip(3).size_hint(), (7, Some(7))); + assert_eq!(vi.skip(12).size_hint(), (0, Some(0))); + assert_eq!(vi.take_while(|_| false).size_hint(), (0, Some(10))); + assert_eq!(vi.skip_while(|_| false).size_hint(), (0, Some(10))); + assert_eq!(vi.enumerate().size_hint(), (10, Some(10))); + assert_eq!(vi.chain(v2.iter()).size_hint(), (13, Some(13))); + assert_eq!(vi.zip(v2.iter()).size_hint(), (3, Some(3))); + assert_eq!(vi.scan(0, |_,_| Some(0)).size_hint(), (0, Some(10))); + assert_eq!(vi.filter(|_| false).size_hint(), (0, Some(10))); + assert_eq!(vi.map(|i| i+1).size_hint(), (10, Some(10))); + assert_eq!(vi.filter_map(|_| Some(0)).size_hint(), (0, Some(10))); + } + + #[test] + fn test_collect() { + let a = ~[1, 2, 3, 4, 5]; + let b: ~[int] = a.iter().map(|&x| x).collect(); + assert_eq!(a, b); + } + + #[test] + fn test_all() { + let v: ~&[int] = ~&[1, 2, 3, 4, 5]; + assert!(v.iter().all(|&x| x < 10)); + assert!(!v.iter().all(|&x| x.is_even())); + assert!(!v.iter().all(|&x| x > 100)); + assert!(v.slice(0, 0).iter().all(|_| fail!())); + } + + #[test] + fn test_any() { + let v: ~&[int] = ~&[1, 2, 3, 4, 5]; + assert!(v.iter().any(|&x| x < 10)); + assert!(v.iter().any(|&x| x.is_even())); + assert!(!v.iter().any(|&x| x > 100)); + assert!(!v.slice(0, 0).iter().any(|_| fail!())); + } + + #[test] + fn test_find() { + let v: &[int] = &[1, 3, 9, 27, 103, 14, 11]; + assert_eq!(*v.iter().find(|x| *x & 1 == 0).unwrap(), 14); + assert_eq!(*v.iter().find(|x| *x % 3 == 0).unwrap(), 3); + assert!(v.iter().find(|x| *x % 12 == 0).is_none()); + } + + #[test] + fn test_position() { + let v = &[1, 3, 9, 27, 103, 14, 11]; + assert_eq!(v.iter().position(|x| *x & 1 == 0).unwrap(), 5); + assert_eq!(v.iter().position(|x| *x % 3 == 0).unwrap(), 1); + assert!(v.iter().position(|x| *x % 12 == 0).is_none()); + } + + #[test] + fn test_count() { + let xs = &[1, 2, 2, 1, 5, 9, 0, 2]; + assert_eq!(xs.iter().count(|x| *x == 2), 3); + assert_eq!(xs.iter().count(|x| *x == 5), 1); + assert_eq!(xs.iter().count(|x| *x == 95), 0); + } + + #[test] + fn test_max_by() { + let xs: &[int] = &[-3, 0, 1, 5, -10]; + assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10); + } + + #[test] + fn test_min_by() { + let xs: &[int] = &[-3, 0, 1, 5, -10]; + assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0); + } + + #[test] + fn test_invert() { + let xs = [2, 4, 6, 8, 10, 12, 14, 16]; + let mut it = xs.iter(); + it.next(); + it.next(); + assert_eq!(it.invert().map(|&x| x).collect::<~[int]>(), ~[16, 14, 12, 10, 8, 6]); + } + + #[test] + fn test_double_ended_map() { + let xs = [1, 2, 3, 4, 5, 6]; + let mut it = xs.iter().map(|&x| x * -1); + assert_eq!(it.next(), Some(-1)); + assert_eq!(it.next(), Some(-2)); + assert_eq!(it.next_back(), Some(-6)); + assert_eq!(it.next_back(), Some(-5)); + assert_eq!(it.next(), Some(-3)); + assert_eq!(it.next_back(), Some(-4)); + assert_eq!(it.next(), None); + } + + #[test] + fn test_double_ended_enumerate() { + let xs = [1, 2, 3, 4, 5, 6]; + let mut it = xs.iter().map(|&x| x).enumerate(); + assert_eq!(it.next(), Some((0, 1))); + assert_eq!(it.next(), Some((1, 2))); + assert_eq!(it.next_back(), Some((5, 6))); + assert_eq!(it.next_back(), Some((4, 5))); + assert_eq!(it.next_back(), Some((3, 4))); + assert_eq!(it.next_back(), Some((2, 3))); + assert_eq!(it.next(), None); + } + + #[test] + fn test_double_ended_zip() { + let xs = [1, 2, 3, 4, 5, 6]; + let ys = [1, 2, 3, 7]; + let a = xs.iter().map(|&x| x); + let b = ys.iter().map(|&x| x); + let mut it = a.zip(b); + assert_eq!(it.next(), Some((1, 1))); + assert_eq!(it.next(), Some((2, 2))); + assert_eq!(it.next_back(), Some((4, 7))); + assert_eq!(it.next_back(), Some((3, 3))); + assert_eq!(it.next(), None); + } + + #[test] + fn test_double_ended_filter() { + let xs = [1, 2, 3, 4, 5, 6]; + let mut it = xs.iter().filter(|&x| *x & 1 == 0); + assert_eq!(it.next_back().unwrap(), &6); + assert_eq!(it.next_back().unwrap(), &4); + assert_eq!(it.next().unwrap(), &2); + assert_eq!(it.next_back(), None); + } + + #[test] + fn test_double_ended_filter_map() { + let xs = [1, 2, 3, 4, 5, 6]; + let mut it = xs.iter().filter_map(|&x| if x & 1 == 0 { Some(x * 2) } else { None }); + assert_eq!(it.next_back().unwrap(), 12); + assert_eq!(it.next_back().unwrap(), 8); + assert_eq!(it.next().unwrap(), 4); + assert_eq!(it.next_back(), None); + } + + #[test] + fn test_double_ended_chain() { + let xs = [1, 2, 3, 4, 5]; + let ys = ~[7, 9, 11]; + let mut it = xs.iter().chain(ys.iter()).invert(); + assert_eq!(it.next().unwrap(), &11) + assert_eq!(it.next().unwrap(), &9) + assert_eq!(it.next_back().unwrap(), &1) + assert_eq!(it.next_back().unwrap(), &2) + assert_eq!(it.next_back().unwrap(), &3) + assert_eq!(it.next_back().unwrap(), &4) + assert_eq!(it.next_back().unwrap(), &5) + assert_eq!(it.next_back().unwrap(), &7) + assert_eq!(it.next_back(), None) + } + + #[test] + fn test_rposition() { + fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' } + fn g(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'd' } + let v = ~[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')]; + + assert_eq!(v.iter().rposition(f), Some(3u)); + assert!(v.iter().rposition(g).is_none()); + } + + #[test] + #[should_fail] + fn test_rposition_fail() { + let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)]; + let mut i = 0; + do v.iter().rposition |_elt| { + if i == 2 { + fail!() + } + i += 1; + false + }; + } + + + #[cfg(test)] + fn check_randacc_iter>(a: T, len: uint) + { + let mut b = a.clone(); + assert_eq!(len, b.indexable()); + let mut n = 0; + for (i, elt) in a.enumerate() { + assert_eq!(Some(elt), b.idx(i)); + n += 1; + } + assert_eq!(n, len); + assert_eq!(None, b.idx(n)); + // call recursively to check after picking off an element + if len > 0 { + b.next(); + check_randacc_iter(b, len-1); + } + } + + + #[test] + fn test_double_ended_flat_map() { + let u = [0u,1]; + let v = [5,6,7,8]; + let mut it = u.iter().flat_map(|x| v.slice(*x, v.len()).iter()); + assert_eq!(it.next_back().unwrap(), &8); + assert_eq!(it.next().unwrap(), &5); + assert_eq!(it.next_back().unwrap(), &7); + assert_eq!(it.next_back().unwrap(), &6); + assert_eq!(it.next_back().unwrap(), &8); + assert_eq!(it.next().unwrap(), &6); + assert_eq!(it.next_back().unwrap(), &7); + assert_eq!(it.next_back(), None); + assert_eq!(it.next(), None); + assert_eq!(it.next_back(), None); + } + + #[test] + fn test_random_access_chain() { + let xs = [1, 2, 3, 4, 5]; + let ys = ~[7, 9, 11]; + let mut it = xs.iter().chain(ys.iter()); + assert_eq!(it.idx(0).unwrap(), &1); + assert_eq!(it.idx(5).unwrap(), &7); + assert_eq!(it.idx(7).unwrap(), &11); + assert!(it.idx(8).is_none()); + + it.next(); + it.next(); + it.next_back(); + + assert_eq!(it.idx(0).unwrap(), &3); + assert_eq!(it.idx(4).unwrap(), &9); + assert!(it.idx(6).is_none()); + + check_randacc_iter(it, xs.len() + ys.len() - 3); + } + + #[test] + fn test_random_access_enumerate() { + let xs = [1, 2, 3, 4, 5]; + check_randacc_iter(xs.iter().enumerate(), xs.len()); + } + + #[test] + fn test_random_access_invert() { + let xs = [1, 2, 3, 4, 5]; + check_randacc_iter(xs.iter().invert(), xs.len()); + let mut it = xs.iter().invert(); + it.next(); + it.next_back(); + it.next(); + check_randacc_iter(it, xs.len() - 3); + } + + #[test] + fn test_random_access_zip() { + let xs = [1, 2, 3, 4, 5]; + let ys = [7, 9, 11]; + check_randacc_iter(xs.iter().zip(ys.iter()), cmp::min(xs.len(), ys.len())); + } + + #[test] + fn test_random_access_take() { + let xs = [1, 2, 3, 4, 5]; + let empty: &[int] = []; + check_randacc_iter(xs.iter().take(3), 3); + check_randacc_iter(xs.iter().take(20), xs.len()); + check_randacc_iter(xs.iter().take(0), 0); + check_randacc_iter(empty.iter().take(2), 0); + } + + #[test] + fn test_random_access_skip() { + let xs = [1, 2, 3, 4, 5]; + let empty: &[int] = []; + check_randacc_iter(xs.iter().skip(2), xs.len() - 2); + check_randacc_iter(empty.iter().skip(2), 0); + } + + #[test] + fn test_random_access_inspect() { + let xs = [1, 2, 3, 4, 5]; + + // test .map and .inspect that don't implement Clone + let it = xs.iter().inspect(|_| {}); + assert_eq!(xs.len(), it.indexable()); + for (i, elt) in xs.iter().enumerate() { + assert_eq!(Some(elt), it.idx(i)); + } + + } + + #[test] + fn test_random_access_map() { + let xs = [1, 2, 3, 4, 5]; + + let it = xs.iter().map(|x| *x); + assert_eq!(xs.len(), it.indexable()); + for (i, elt) in xs.iter().enumerate() { + assert_eq!(Some(*elt), it.idx(i)); + } + } + + #[test] + fn test_random_access_cycle() { + let xs = [1, 2, 3, 4, 5]; + let empty: &[int] = []; + check_randacc_iter(xs.iter().cycle().take(27), 27); + check_randacc_iter(empty.iter().cycle(), 0); + } + + #[test] + fn test_double_ended_range() { + assert_eq!(range(11i, 14).invert().collect::<~[int]>(), ~[13i, 12, 11]); + for _ in range(10i, 0).invert() { + fail!("unreachable"); + } + + assert_eq!(range(11u, 14).invert().collect::<~[uint]>(), ~[13u, 12, 11]); + for _ in range(10u, 0).invert() { + fail!("unreachable"); + } + } + + #[test] + fn test_range_inclusive() { + assert_eq!(range_inclusive(0i, 5).collect::<~[int]>(), ~[0i, 1, 2, 3, 4, 5]); + assert_eq!(range_inclusive(0i, 5).invert().collect::<~[int]>(), ~[5i, 4, 3, 2, 1, 0]); + } + + #[test] + fn test_reverse() { + let mut ys = [1, 2, 3, 4, 5]; + ys.mut_iter().reverse_(); + assert_eq!(ys, [5, 4, 3, 2, 1]); + } +} diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs deleted file mode 100644 index 77637b6998e..00000000000 --- a/src/libstd/iterator.rs +++ /dev/null @@ -1,2659 +0,0 @@ -// Copyright 2013 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -/*! Composable external iterators - -The `Iterator` trait defines an interface for objects which implement iteration as a state machine. - -Algorithms like `zip` are provided as `Iterator` implementations which wrap other objects -implementing the `Iterator` trait. - -*/ - -use cmp; -use num::{Zero, One, Integer, CheckedAdd, CheckedSub, Saturating}; -use option::{Option, Some, None}; -use ops::{Add, Mul, Sub}; -use cmp::Ord; -use clone::Clone; -use uint; -use util; - -/// Conversion from an `Iterator` -pub trait FromIterator { - /// Build a container with elements from an external iterator. - fn from_iterator>(iterator: &mut T) -> Self; -} - -/// A type growable from an `Iterator` implementation -pub trait Extendable: FromIterator { - /// Extend a container with the elements yielded by an iterator - fn extend>(&mut self, iterator: &mut T); -} - -/// An interface for dealing with "external iterators". These types of iterators -/// can be resumed at any time as all state is stored internally as opposed to -/// being located on the call stack. -/// -/// The Iterator protocol states that an iterator yields a (potentially-empty, -/// potentially-infinite) sequence of values, and returns `None` to signal that -/// it's finished. The Iterator protocol does not define behavior after `None` -/// is returned. A concrete Iterator implementation may choose to behave however -/// it wishes, either by returning `None` infinitely, or by doing something -/// else. -pub trait Iterator { - /// Advance the iterator and return the next value. Return `None` when the end is reached. - fn next(&mut self) -> Option; - - /// Return a lower bound and upper bound on the remaining length of the iterator. - /// - /// The common use case for the estimate is pre-allocating space to store the results. - #[inline] - fn size_hint(&self) -> (uint, Option) { (0, None) } - - /// Chain this iterator with another, returning a new iterator which will - /// finish iterating over the current iterator, and then it will iterate - /// over the other specified iterator. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [0]; - /// let b = [1]; - /// let mut it = a.iter().chain(b.iter()); - /// assert_eq!(it.next().get(), &0); - /// assert_eq!(it.next().get(), &1); - /// assert!(it.next().is_none()); - /// ~~~ - #[inline] - fn chain>(self, other: U) -> Chain { - Chain{a: self, b: other, flag: false} - } - - /// Creates an iterator which iterates over both this and the specified - /// iterators simultaneously, yielding the two elements as pairs. When - /// either iterator returns None, all further invocations of next() will - /// return None. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [0]; - /// let b = [1]; - /// let mut it = a.iter().zip(b.iter()); - /// assert_eq!(it.next().get(), (&0, &1)); - /// assert!(it.next().is_none()); - /// ~~~ - #[inline] - fn zip>(self, other: U) -> Zip { - Zip{a: self, b: other} - } - - /// Creates a new iterator which will apply the specified function to each - /// element returned by the first, yielding the mapped element instead. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2]; - /// let mut it = a.iter().map(|&x| 2 * x); - /// assert_eq!(it.next().get(), 2); - /// assert_eq!(it.next().get(), 4); - /// assert!(it.next().is_none()); - /// ~~~ - #[inline] - fn map<'r, B>(self, f: &'r fn(A) -> B) -> Map<'r, A, B, Self> { - Map{iter: self, f: f} - } - - /// Creates an iterator which applies the predicate to each element returned - /// by this iterator. Only elements which have the predicate evaluate to - /// `true` will be yielded. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2]; - /// let mut it = a.iter().filter(|&x| *x > 1); - /// assert_eq!(it.next().get(), &2); - /// assert!(it.next().is_none()); - /// ~~~ - #[inline] - fn filter<'r>(self, predicate: &'r fn(&A) -> bool) -> Filter<'r, A, Self> { - Filter{iter: self, predicate: predicate} - } - - /// Creates an iterator which both filters and maps elements. - /// If the specified function returns None, the element is skipped. - /// Otherwise the option is unwrapped and the new value is yielded. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2]; - /// let mut it = a.iter().filter_map(|&x| if x > 1 {Some(2 * x)} else {None}); - /// assert_eq!(it.next().get(), 4); - /// assert!(it.next().is_none()); - /// ~~~ - #[inline] - fn filter_map<'r, B>(self, f: &'r fn(A) -> Option) -> FilterMap<'r, A, B, Self> { - FilterMap { iter: self, f: f } - } - - /// Creates an iterator which yields a pair of the value returned by this - /// iterator plus the current index of iteration. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [100, 200]; - /// let mut it = a.iter().enumerate(); - /// assert_eq!(it.next().get(), (0, &100)); - /// assert_eq!(it.next().get(), (1, &200)); - /// assert!(it.next().is_none()); - /// ~~~ - #[inline] - fn enumerate(self) -> Enumerate { - Enumerate{iter: self, count: 0} - } - - - /// Creates an iterator that has a `.peek()` method - /// that returns a optional reference to the next element. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [100, 200, 300]; - /// let mut it = xs.iter().map(|&x|x).peekable(); - /// assert_eq!(it.peek().unwrap(), &100); - /// assert_eq!(it.next().unwrap(), 100); - /// assert_eq!(it.next().unwrap(), 200); - /// assert_eq!(it.peek().unwrap(), &300); - /// assert_eq!(it.peek().unwrap(), &300); - /// assert_eq!(it.next().unwrap(), 300); - /// assert!(it.peek().is_none()); - /// assert!(it.next().is_none()); - /// ~~~ - #[inline] - fn peekable(self) -> Peekable { - Peekable{iter: self, peeked: None} - } - - /// Creates an iterator which invokes the predicate on elements until it - /// returns false. Once the predicate returns false, all further elements are - /// yielded. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 2, 1]; - /// let mut it = a.iter().skip_while(|&a| *a < 3); - /// assert_eq!(it.next().get(), &3); - /// assert_eq!(it.next().get(), &2); - /// assert_eq!(it.next().get(), &1); - /// assert!(it.next().is_none()); - /// ~~~ - #[inline] - fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) -> SkipWhile<'r, A, Self> { - SkipWhile{iter: self, flag: false, predicate: predicate} - } - - /// Creates an iterator which yields elements so long as the predicate - /// returns true. After the predicate returns false for the first time, no - /// further elements will be yielded. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 2, 1]; - /// let mut it = a.iter().take_while(|&a| *a < 3); - /// assert_eq!(it.next().get(), &1); - /// assert_eq!(it.next().get(), &2); - /// assert!(it.next().is_none()); - /// ~~~ - #[inline] - fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) -> TakeWhile<'r, A, Self> { - TakeWhile{iter: self, flag: false, predicate: predicate} - } - - /// Creates an iterator which skips the first `n` elements of this iterator, - /// and then it yields all further items. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// let mut it = a.iter().skip(3); - /// assert_eq!(it.next().get(), &4); - /// assert_eq!(it.next().get(), &5); - /// assert!(it.next().is_none()); - /// ~~~ - #[inline] - fn skip(self, n: uint) -> Skip { - Skip{iter: self, n: n} - } - - /// Creates an iterator which yields the first `n` elements of this - /// iterator, and then it will always return None. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// let mut it = a.iter().take(3); - /// assert_eq!(it.next().get(), &1); - /// assert_eq!(it.next().get(), &2); - /// assert_eq!(it.next().get(), &3); - /// assert!(it.next().is_none()); - /// ~~~ - #[inline] - fn take(self, n: uint) -> Take { - Take{iter: self, n: n} - } - - /// Creates a new iterator which behaves in a similar fashion to foldl. - /// There is a state which is passed between each iteration and can be - /// mutated as necessary. The yielded values from the closure are yielded - /// from the Scan instance when not None. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// let mut it = a.iter().scan(1, |fac, &x| { - /// *fac = *fac * x; - /// Some(*fac) - /// }); - /// assert_eq!(it.next().get(), 1); - /// assert_eq!(it.next().get(), 2); - /// assert_eq!(it.next().get(), 6); - /// assert_eq!(it.next().get(), 24); - /// assert_eq!(it.next().get(), 120); - /// assert!(it.next().is_none()); - /// ~~~ - #[inline] - fn scan<'r, St, B>(self, initial_state: St, f: &'r fn(&mut St, A) -> Option) - -> Scan<'r, A, B, Self, St> { - Scan{iter: self, f: f, state: initial_state} - } - - /// Creates an iterator that maps each element to an iterator, - /// and yields the elements of the produced iterators - /// - /// # Example - /// - /// ~~~ {.rust} - /// let xs = [2u, 3]; - /// let ys = [0u, 1, 0, 1, 2]; - /// let mut it = xs.iter().flat_map(|&x| count(0u, 1).take(x)); - /// // Check that `it` has the same elements as `ys` - /// let mut i = 0; - /// for x: uint in it { - /// assert_eq!(x, ys[i]); - /// i += 1; - /// } - /// ~~~ - #[inline] - fn flat_map<'r, B, U: Iterator>(self, f: &'r fn(A) -> U) - -> FlatMap<'r, A, Self, U> { - FlatMap{iter: self, f: f, frontiter: None, backiter: None } - } - - /// Creates an iterator that yields `None` forever after the underlying - /// iterator yields `None`. Random-access iterator behavior is not - /// affected, only single and double-ended iterator behavior. - /// - /// # Example - /// - /// ~~~ {.rust} - /// fn process>(it: U) -> int { - /// let mut it = it.fuse(); - /// let mut sum = 0; - /// for x in it { - /// if x > 5 { - /// break; - /// } - /// sum += x; - /// } - /// // did we exhaust the iterator? - /// if it.next().is_none() { - /// sum += 1000; - /// } - /// sum - /// } - /// let x = ~[1,2,3,7,8,9]; - /// assert_eq!(process(x.move_iter()), 1006); - /// ~~~ - #[inline] - fn fuse(self) -> Fuse { - Fuse{iter: self, done: false} - } - - /// Creates an iterator that calls a function with a reference to each - /// element before yielding it. This is often useful for debugging an - /// iterator pipeline. - /// - /// # Example - /// - /// ~~~ {.rust} - ///let xs = [1u, 4, 2, 3, 8, 9, 6]; - ///let sum = xs.iter() - /// .map(|&x| x) - /// .inspect(|&x| debug!("filtering %u", x)) - /// .filter(|&x| x % 2 == 0) - /// .inspect(|&x| debug!("%u made it through", x)) - /// .sum(); - ///println(sum.to_str()); - /// ~~~ - #[inline] - fn inspect<'r>(self, f: &'r fn(&A)) -> Inspect<'r, A, Self> { - Inspect{iter: self, f: f} - } - - /// An adaptation of an external iterator to the for-loop protocol of rust. - /// - /// # Example - /// - /// ~~~ {.rust} - /// use std::iterator::Counter; - /// - /// for i in count(0, 10) { - /// printfln!("%d", i); - /// } - /// ~~~ - #[inline] - fn advance(&mut self, f: &fn(A) -> bool) -> bool { - loop { - match self.next() { - Some(x) => { - if !f(x) { return false; } - } - None => { return true; } - } - } - } - - /// Loops through the entire iterator, collecting all of the elements into - /// a container implementing `FromIterator`. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// let b: ~[int] = a.iter().map(|&x| x).collect(); - /// assert!(a == b); - /// ~~~ - #[inline] - fn collect>(&mut self) -> B { - FromIterator::from_iterator(self) - } - - /// Loops through the entire iterator, collecting all of the elements into - /// a unique vector. This is simply collect() specialized for vectors. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// let b: ~[int] = a.iter().map(|&x| x).to_owned_vec(); - /// assert!(a == b); - /// ~~~ - #[inline] - fn to_owned_vec(&mut self) -> ~[A] { - self.collect() - } - - /// Loops through `n` iterations, returning the `n`th element of the - /// iterator. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// let mut it = a.iter(); - /// assert!(it.nth(2).get() == &3); - /// assert!(it.nth(2) == None); - /// ~~~ - #[inline] - fn nth(&mut self, mut n: uint) -> Option { - loop { - match self.next() { - Some(x) => if n == 0 { return Some(x) }, - None => return None - } - n -= 1; - } - } - - /// Loops through the entire iterator, returning the last element of the - /// iterator. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// assert!(a.iter().last().get() == &5); - /// ~~~ - #[inline] - fn last(&mut self) -> Option { - let mut last = None; - for x in *self { last = Some(x); } - last - } - - /// Performs a fold operation over the entire iterator, returning the - /// eventual state at the end of the iteration. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// assert!(a.iter().fold(0, |a, &b| a + b) == 15); - /// ~~~ - #[inline] - fn fold(&mut self, init: B, f: &fn(B, A) -> B) -> B { - let mut accum = init; - loop { - match self.next() { - Some(x) => { accum = f(accum, x); } - None => { break; } - } - } - accum - } - - /// Counts the number of elements in this iterator. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// let mut it = a.iter(); - /// assert!(it.len() == 5); - /// assert!(it.len() == 0); - /// ~~~ - #[inline] - fn len(&mut self) -> uint { - self.fold(0, |cnt, _x| cnt + 1) - } - - /// Tests whether the predicate holds true for all elements in the iterator. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// assert!(a.iter().all(|&x| *x > 0)); - /// assert!(!a.iter().all(|&x| *x > 2)); - /// ~~~ - #[inline] - fn all(&mut self, f: &fn(A) -> bool) -> bool { - for x in *self { if !f(x) { return false; } } - true - } - - /// Tests whether any element of an iterator satisfies the specified - /// predicate. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// let mut it = a.iter(); - /// assert!(it.any(|&x| *x == 3)); - /// assert!(!it.any(|&x| *x == 3)); - /// ~~~ - #[inline] - fn any(&mut self, f: &fn(A) -> bool) -> bool { - for x in *self { if f(x) { return true; } } - false - } - - /// Return the first element satisfying the specified predicate - #[inline] - fn find(&mut self, predicate: &fn(&A) -> bool) -> Option { - for x in *self { - if predicate(&x) { return Some(x) } - } - None - } - - /// Return the index of the first element satisfying the specified predicate - #[inline] - fn position(&mut self, predicate: &fn(A) -> bool) -> Option { - let mut i = 0; - for x in *self { - if predicate(x) { - return Some(i); - } - i += 1; - } - None - } - - /// Count the number of elements satisfying the specified predicate - #[inline] - fn count(&mut self, predicate: &fn(A) -> bool) -> uint { - let mut i = 0; - for x in *self { - if predicate(x) { i += 1 } - } - i - } - - /// Return the element that gives the maximum value from the - /// specified function. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let xs = [-3, 0, 1, 5, -10]; - /// assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10); - /// ~~~ - #[inline] - fn max_by(&mut self, f: &fn(&A) -> B) -> Option { - self.fold(None, |max: Option<(A, B)>, x| { - let x_val = f(&x); - match max { - None => Some((x, x_val)), - Some((y, y_val)) => if x_val > y_val { - Some((x, x_val)) - } else { - Some((y, y_val)) - } - } - }).map_move(|(x, _)| x) - } - - /// Return the element that gives the minimum value from the - /// specified function. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let xs = [-3, 0, 1, 5, -10]; - /// assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0); - /// ~~~ - #[inline] - fn min_by(&mut self, f: &fn(&A) -> B) -> Option { - self.fold(None, |min: Option<(A, B)>, x| { - let x_val = f(&x); - match min { - None => Some((x, x_val)), - Some((y, y_val)) => if x_val < y_val { - Some((x, x_val)) - } else { - Some((y, y_val)) - } - } - }).map_move(|(x, _)| x) - } -} - -/// A range iterator able to yield elements from both ends -pub trait DoubleEndedIterator: Iterator { - /// Yield an element from the end of the range, returning `None` if the range is empty. - fn next_back(&mut self) -> Option; - - /// Flip the direction of the iterator - /// - /// The inverted iterator flips the ends on an iterator that can already - /// be iterated from the front and from the back. - /// - /// - /// If the iterator also implements RandomAccessIterator, the inverted - /// iterator is also random access, with the indices starting at the back - /// of the original iterator. - /// - /// Note: Random access with inverted indices still only applies to the first - /// `uint::max_value` elements of the original iterator. - #[inline] - fn invert(self) -> Invert { - Invert{iter: self} - } -} - -/// A double-ended iterator yielding mutable references -pub trait MutableDoubleEndedIterator { - // FIXME: #5898: should be called `reverse` - /// Use an iterator to reverse a container in-place - fn reverse_(&mut self); -} - -impl<'self, A, T: DoubleEndedIterator<&'self mut A>> MutableDoubleEndedIterator for T { - // FIXME: #5898: should be called `reverse` - /// Use an iterator to reverse a container in-place - fn reverse_(&mut self) { - loop { - match (self.next(), self.next_back()) { - (Some(x), Some(y)) => util::swap(x, y), - _ => break - } - } - } -} - - -/// An object implementing random access indexing by `uint` -/// -/// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`. -pub trait RandomAccessIterator: Iterator { - /// Return the number of indexable elements. At most `std::uint::max_value` - /// elements are indexable, even if the iterator represents a longer range. - fn indexable(&self) -> uint; - - /// Return an element at an index - fn idx(&self, index: uint) -> Option; -} - -/// An iterator that knows its exact length -/// -/// This trait is a helper for iterators like the vector iterator, so that -/// it can support double-ended enumeration. -/// -/// `Iterator::size_hint` *must* return the exact size of the iterator. -/// Note that the size must fit in `uint`. -pub trait ExactSize : DoubleEndedIterator { - /// Return the index of the last element satisfying the specified predicate - /// - /// If no element matches, None is returned. - #[inline] - fn rposition(&mut self, predicate: &fn(A) -> bool) -> Option { - let (lower, upper) = self.size_hint(); - assert!(upper == Some(lower)); - let mut i = lower; - loop { - match self.next_back() { - None => break, - Some(x) => { - i = match i.checked_sub(&1) { - Some(x) => x, - None => fail!("rposition: incorrect ExactSize") - }; - if predicate(x) { - return Some(i) - } - } - } - } - None - } -} - -// All adaptors that preserve the size of the wrapped iterator are fine -// Adaptors that may overflow in `size_hint` are not, i.e. `Chain`. -impl> ExactSize<(uint, A)> for Enumerate {} -impl<'self, A, T: ExactSize> ExactSize for Inspect<'self, A, T> {} -impl> ExactSize for Invert {} -impl<'self, A, B, T: ExactSize> ExactSize for Map<'self, A, B, T> {} -impl, U: ExactSize> ExactSize<(A, B)> for Zip {} - -/// An double-ended iterator with the direction inverted -#[deriving(Clone)] -pub struct Invert { - priv iter: T -} - -impl> Iterator for Invert { - #[inline] - fn next(&mut self) -> Option { self.iter.next_back() } - #[inline] - fn size_hint(&self) -> (uint, Option) { self.iter.size_hint() } -} - -impl> DoubleEndedIterator for Invert { - #[inline] - fn next_back(&mut self) -> Option { self.iter.next() } -} - -impl + RandomAccessIterator> RandomAccessIterator - for Invert { - #[inline] - fn indexable(&self) -> uint { self.iter.indexable() } - #[inline] - fn idx(&self, index: uint) -> Option { - self.iter.idx(self.indexable() - index - 1) - } -} - -/// A trait for iterators over elements which can be added together -pub trait AdditiveIterator { - /// Iterates over the entire iterator, summing up all the elements - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// let mut it = a.iter().map(|&x| x); - /// assert!(it.sum() == 15); - /// ~~~ - fn sum(&mut self) -> A; -} - -impl + Zero, T: Iterator> AdditiveIterator for T { - #[inline] - fn sum(&mut self) -> A { - let zero: A = Zero::zero(); - self.fold(zero, |s, x| s + x) - } -} - -/// A trait for iterators over elements whose elements can be multiplied -/// together. -pub trait MultiplicativeIterator { - /// Iterates over the entire iterator, multiplying all the elements - /// - /// # Example - /// - /// ~~~ {.rust} - /// use std::iterator::Counter; - /// - /// fn factorial(n: uint) -> uint { - /// count(1u, 1).take_while(|&i| i <= n).product() - /// } - /// assert!(factorial(0) == 1); - /// assert!(factorial(1) == 1); - /// assert!(factorial(5) == 120); - /// ~~~ - fn product(&mut self) -> A; -} - -impl + One, T: Iterator> MultiplicativeIterator for T { - #[inline] - fn product(&mut self) -> A { - let one: A = One::one(); - self.fold(one, |p, x| p * x) - } -} - -/// A trait for iterators over elements which can be compared to one another. -/// The type of each element must ascribe to the `Ord` trait. -pub trait OrdIterator { - /// Consumes the entire iterator to return the maximum element. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// assert!(a.iter().max().get() == &5); - /// ~~~ - fn max(&mut self) -> Option; - - /// Consumes the entire iterator to return the minimum element. - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = [1, 2, 3, 4, 5]; - /// assert!(a.iter().min().get() == &1); - /// ~~~ - fn min(&mut self) -> Option; -} - -impl> OrdIterator for T { - #[inline] - fn max(&mut self) -> Option { - self.fold(None, |max, x| { - match max { - None => Some(x), - Some(y) => Some(cmp::max(x, y)) - } - }) - } - - #[inline] - fn min(&mut self) -> Option { - self.fold(None, |min, x| { - match min { - None => Some(x), - Some(y) => Some(cmp::min(x, y)) - } - }) - } -} - -/// A trait for iterators that are clonable. -pub trait ClonableIterator { - /// Repeats an iterator endlessly - /// - /// # Example - /// - /// ~~~ {.rust} - /// let a = count(1,1).take(1); - /// let mut cy = a.cycle(); - /// assert_eq!(cy.next(), Some(1)); - /// assert_eq!(cy.next(), Some(1)); - /// ~~~ - fn cycle(self) -> Cycle; -} - -impl> ClonableIterator for T { - #[inline] - fn cycle(self) -> Cycle { - Cycle{orig: self.clone(), iter: self} - } -} - -/// An iterator that repeats endlessly -#[deriving(Clone)] -pub struct Cycle { - priv orig: T, - priv iter: T, -} - -impl> Iterator for Cycle { - #[inline] - fn next(&mut self) -> Option { - match self.iter.next() { - None => { self.iter = self.orig.clone(); self.iter.next() } - y => y - } - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - // the cycle iterator is either empty or infinite - match self.orig.size_hint() { - sz @ (0, Some(0)) => sz, - (0, _) => (0, None), - _ => (uint::max_value, None) - } - } -} - -impl> RandomAccessIterator for Cycle { - #[inline] - fn indexable(&self) -> uint { - if self.orig.indexable() > 0 { - uint::max_value - } else { - 0 - } - } - - #[inline] - fn idx(&self, index: uint) -> Option { - let liter = self.iter.indexable(); - let lorig = self.orig.indexable(); - if lorig == 0 { - None - } else if index < liter { - self.iter.idx(index) - } else { - self.orig.idx((index - liter) % lorig) - } - } -} - -/// An iterator which strings two iterators together -#[deriving(Clone)] -pub struct Chain { - priv a: T, - priv b: U, - priv flag: bool -} - -impl, U: Iterator> Iterator for Chain { - #[inline] - fn next(&mut self) -> Option { - if self.flag { - self.b.next() - } else { - match self.a.next() { - Some(x) => return Some(x), - _ => () - } - self.flag = true; - self.b.next() - } - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - let (a_lower, a_upper) = self.a.size_hint(); - let (b_lower, b_upper) = self.b.size_hint(); - - let lower = a_lower.saturating_add(b_lower); - - let upper = match (a_upper, b_upper) { - (Some(x), Some(y)) => x.checked_add(&y), - _ => None - }; - - (lower, upper) - } -} - -impl, U: DoubleEndedIterator> DoubleEndedIterator -for Chain { - #[inline] - fn next_back(&mut self) -> Option { - match self.b.next_back() { - Some(x) => Some(x), - None => self.a.next_back() - } - } -} - -impl, U: RandomAccessIterator> RandomAccessIterator -for Chain { - #[inline] - fn indexable(&self) -> uint { - let (a, b) = (self.a.indexable(), self.b.indexable()); - a.saturating_add(b) - } - - #[inline] - fn idx(&self, index: uint) -> Option { - let len = self.a.indexable(); - if index < len { - self.a.idx(index) - } else { - self.b.idx(index - len) - } - } -} - -/// An iterator which iterates two other iterators simultaneously -#[deriving(Clone)] -pub struct Zip { - priv a: T, - priv b: U -} - -impl, U: Iterator> Iterator<(A, B)> for Zip { - #[inline] - fn next(&mut self) -> Option<(A, B)> { - match self.a.next() { - None => None, - Some(x) => match self.b.next() { - None => None, - Some(y) => Some((x, y)) - } - } - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - let (a_lower, a_upper) = self.a.size_hint(); - let (b_lower, b_upper) = self.b.size_hint(); - - let lower = cmp::min(a_lower, b_lower); - - let upper = match (a_upper, b_upper) { - (Some(x), Some(y)) => Some(cmp::min(x,y)), - (Some(x), None) => Some(x), - (None, Some(y)) => Some(y), - (None, None) => None - }; - - (lower, upper) - } -} - -impl, U: ExactSize> DoubleEndedIterator<(A, B)> -for Zip { - #[inline] - fn next_back(&mut self) -> Option<(A, B)> { - let (a_sz, a_upper) = self.a.size_hint(); - let (b_sz, b_upper) = self.b.size_hint(); - assert!(a_upper == Some(a_sz)); - assert!(b_upper == Some(b_sz)); - if a_sz < b_sz { - for _ in range(0, b_sz - a_sz) { self.b.next_back(); } - } else if a_sz > b_sz { - for _ in range(0, a_sz - b_sz) { self.a.next_back(); } - } - let (a_sz, _) = self.a.size_hint(); - let (b_sz, _) = self.b.size_hint(); - assert!(a_sz == b_sz); - match (self.a.next_back(), self.b.next_back()) { - (Some(x), Some(y)) => Some((x, y)), - _ => None - } - } -} - -impl, U: RandomAccessIterator> -RandomAccessIterator<(A, B)> for Zip { - #[inline] - fn indexable(&self) -> uint { - cmp::min(self.a.indexable(), self.b.indexable()) - } - - #[inline] - fn idx(&self, index: uint) -> Option<(A, B)> { - match self.a.idx(index) { - None => None, - Some(x) => match self.b.idx(index) { - None => None, - Some(y) => Some((x, y)) - } - } - } -} - -/// An iterator which maps the values of `iter` with `f` -pub struct Map<'self, A, B, T> { - priv iter: T, - priv f: &'self fn(A) -> B -} - -impl<'self, A, B, T> Map<'self, A, B, T> { - #[inline] - fn do_map(&self, elt: Option) -> Option { - match elt { - Some(a) => Some((self.f)(a)), - _ => None - } - } -} - -impl<'self, A, B, T: Iterator> Iterator for Map<'self, A, B, T> { - #[inline] - fn next(&mut self) -> Option { - let next = self.iter.next(); - self.do_map(next) - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - self.iter.size_hint() - } -} - -impl<'self, A, B, T: DoubleEndedIterator> DoubleEndedIterator for Map<'self, A, B, T> { - #[inline] - fn next_back(&mut self) -> Option { - let next = self.iter.next_back(); - self.do_map(next) - } -} - -impl<'self, A, B, T: RandomAccessIterator> RandomAccessIterator for Map<'self, A, B, T> { - #[inline] - fn indexable(&self) -> uint { - self.iter.indexable() - } - - #[inline] - fn idx(&self, index: uint) -> Option { - self.do_map(self.iter.idx(index)) - } -} - -/// An iterator which filters the elements of `iter` with `predicate` -pub struct Filter<'self, A, T> { - priv iter: T, - priv predicate: &'self fn(&A) -> bool -} - -impl<'self, A, T: Iterator> Iterator for Filter<'self, A, T> { - #[inline] - fn next(&mut self) -> Option { - for x in self.iter { - if (self.predicate)(&x) { - return Some(x); - } else { - loop - } - } - None - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - let (_, upper) = self.iter.size_hint(); - (0, upper) // can't know a lower bound, due to the predicate - } -} - -impl<'self, A, T: DoubleEndedIterator> DoubleEndedIterator for Filter<'self, A, T> { - #[inline] - fn next_back(&mut self) -> Option { - loop { - match self.iter.next_back() { - None => return None, - Some(x) => { - if (self.predicate)(&x) { - return Some(x); - } else { - loop - } - } - } - } - } -} - -/// An iterator which uses `f` to both filter and map elements from `iter` -pub struct FilterMap<'self, A, B, T> { - priv iter: T, - priv f: &'self fn(A) -> Option -} - -impl<'self, A, B, T: Iterator> Iterator for FilterMap<'self, A, B, T> { - #[inline] - fn next(&mut self) -> Option { - for x in self.iter { - match (self.f)(x) { - Some(y) => return Some(y), - None => () - } - } - None - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - let (_, upper) = self.iter.size_hint(); - (0, upper) // can't know a lower bound, due to the predicate - } -} - -impl<'self, A, B, T: DoubleEndedIterator> DoubleEndedIterator -for FilterMap<'self, A, B, T> { - #[inline] - fn next_back(&mut self) -> Option { - loop { - match self.iter.next_back() { - None => return None, - Some(x) => { - match (self.f)(x) { - Some(y) => return Some(y), - None => () - } - } - } - } - } -} - -/// An iterator which yields the current count and the element during iteration -#[deriving(Clone)] -pub struct Enumerate { - priv iter: T, - priv count: uint -} - -impl> Iterator<(uint, A)> for Enumerate { - #[inline] - fn next(&mut self) -> Option<(uint, A)> { - match self.iter.next() { - Some(a) => { - let ret = Some((self.count, a)); - self.count += 1; - ret - } - _ => None - } - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - self.iter.size_hint() - } -} - -impl> DoubleEndedIterator<(uint, A)> for Enumerate { - #[inline] - fn next_back(&mut self) -> Option<(uint, A)> { - match self.iter.next_back() { - Some(a) => { - let (lower, upper) = self.iter.size_hint(); - assert!(upper == Some(lower)); - Some((self.count + lower, a)) - } - _ => None - } - } -} - -impl> RandomAccessIterator<(uint, A)> for Enumerate { - #[inline] - fn indexable(&self) -> uint { - self.iter.indexable() - } - - #[inline] - fn idx(&self, index: uint) -> Option<(uint, A)> { - match self.iter.idx(index) { - Some(a) => Some((self.count + index, a)), - _ => None, - } - } -} - -/// An iterator with a `peek()` that returns an optional reference to the next element. -pub struct Peekable { - priv iter: T, - priv peeked: Option, -} - -impl> Iterator for Peekable { - #[inline] - fn next(&mut self) -> Option { - if self.peeked.is_some() { self.peeked.take() } - else { self.iter.next() } - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - let (lo, hi) = self.iter.size_hint(); - if self.peeked.is_some() { - let lo = lo.saturating_add(1); - let hi = match hi { - Some(x) => x.checked_add(&1), - None => None - }; - (lo, hi) - } else { - (lo, hi) - } - } -} - -impl<'self, A, T: Iterator> Peekable { - /// Return a reference to the next element of the iterator with out advancing it, - /// or None if the iterator is exhausted. - #[inline] - pub fn peek(&'self mut self) -> Option<&'self A> { - if self.peeked.is_none() { - self.peeked = self.iter.next(); - } - match self.peeked { - Some(ref value) => Some(value), - None => None, - } - } -} - -/// An iterator which rejects elements while `predicate` is true -pub struct SkipWhile<'self, A, T> { - priv iter: T, - priv flag: bool, - priv predicate: &'self fn(&A) -> bool -} - -impl<'self, A, T: Iterator> Iterator for SkipWhile<'self, A, T> { - #[inline] - fn next(&mut self) -> Option { - let mut next = self.iter.next(); - if self.flag { - next - } else { - loop { - match next { - Some(x) => { - if (self.predicate)(&x) { - next = self.iter.next(); - loop - } else { - self.flag = true; - return Some(x) - } - } - None => return None - } - } - } - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - let (_, upper) = self.iter.size_hint(); - (0, upper) // can't know a lower bound, due to the predicate - } -} - -/// An iterator which only accepts elements while `predicate` is true -pub struct TakeWhile<'self, A, T> { - priv iter: T, - priv flag: bool, - priv predicate: &'self fn(&A) -> bool -} - -impl<'self, A, T: Iterator> Iterator for TakeWhile<'self, A, T> { - #[inline] - fn next(&mut self) -> Option { - if self.flag { - None - } else { - match self.iter.next() { - Some(x) => { - if (self.predicate)(&x) { - Some(x) - } else { - self.flag = true; - None - } - } - None => None - } - } - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - let (_, upper) = self.iter.size_hint(); - (0, upper) // can't know a lower bound, due to the predicate - } -} - -/// An iterator which skips over `n` elements of `iter`. -#[deriving(Clone)] -pub struct Skip { - priv iter: T, - priv n: uint -} - -impl> Iterator for Skip { - #[inline] - fn next(&mut self) -> Option { - let mut next = self.iter.next(); - if self.n == 0 { - next - } else { - let mut n = self.n; - while n > 0 { - n -= 1; - match next { - Some(_) => { - next = self.iter.next(); - loop - } - None => { - self.n = 0; - return None - } - } - } - self.n = 0; - next - } - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - let (lower, upper) = self.iter.size_hint(); - - let lower = lower.saturating_sub(self.n); - - let upper = match upper { - Some(x) => Some(x.saturating_sub(self.n)), - None => None - }; - - (lower, upper) - } -} - -impl> RandomAccessIterator for Skip { - #[inline] - fn indexable(&self) -> uint { - self.iter.indexable().saturating_sub(self.n) - } - - #[inline] - fn idx(&self, index: uint) -> Option { - if index >= self.indexable() { - None - } else { - self.iter.idx(index + self.n) - } - } -} - -/// An iterator which only iterates over the first `n` iterations of `iter`. -#[deriving(Clone)] -pub struct Take { - priv iter: T, - priv n: uint -} - -impl> Iterator for Take { - #[inline] - fn next(&mut self) -> Option { - if self.n != 0 { - self.n -= 1; - self.iter.next() - } else { - None - } - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - let (lower, upper) = self.iter.size_hint(); - - let lower = cmp::min(lower, self.n); - - let upper = match upper { - Some(x) if x < self.n => Some(x), - _ => Some(self.n) - }; - - (lower, upper) - } -} - -impl> RandomAccessIterator for Take { - #[inline] - fn indexable(&self) -> uint { - cmp::min(self.iter.indexable(), self.n) - } - - #[inline] - fn idx(&self, index: uint) -> Option { - if index >= self.n { - None - } else { - self.iter.idx(index) - } - } -} - - -/// An iterator to maintain state while iterating another iterator -pub struct Scan<'self, A, B, T, St> { - priv iter: T, - priv f: &'self fn(&mut St, A) -> Option, - - /// The current internal state to be passed to the closure next. - state: St -} - -impl<'self, A, B, T: Iterator, St> Iterator for Scan<'self, A, B, T, St> { - #[inline] - fn next(&mut self) -> Option { - self.iter.next().chain(|a| (self.f)(&mut self.state, a)) - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - let (_, upper) = self.iter.size_hint(); - (0, upper) // can't know a lower bound, due to the scan function - } -} - -/// An iterator that maps each element to an iterator, -/// and yields the elements of the produced iterators -/// -pub struct FlatMap<'self, A, T, U> { - priv iter: T, - priv f: &'self fn(A) -> U, - priv frontiter: Option, - priv backiter: Option, -} - -impl<'self, A, T: Iterator, B, U: Iterator> Iterator for - FlatMap<'self, A, T, U> { - #[inline] - fn next(&mut self) -> Option { - loop { - for inner in self.frontiter.mut_iter() { - for x in *inner { - return Some(x) - } - } - match self.iter.next().map_move(|x| (self.f)(x)) { - None => return self.backiter.chain_mut_ref(|it| it.next()), - next => self.frontiter = next, - } - } - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - let (flo, fhi) = self.frontiter.map_default((0, Some(0)), |it| it.size_hint()); - let (blo, bhi) = self.backiter.map_default((0, Some(0)), |it| it.size_hint()); - let lo = flo.saturating_add(blo); - match (self.iter.size_hint(), fhi, bhi) { - ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(&b)), - _ => (lo, None) - } - } -} - -impl<'self, - A, T: DoubleEndedIterator, - B, U: DoubleEndedIterator> DoubleEndedIterator - for FlatMap<'self, A, T, U> { - #[inline] - fn next_back(&mut self) -> Option { - loop { - for inner in self.backiter.mut_iter() { - match inner.next_back() { - None => (), - y => return y - } - } - match self.iter.next_back().map_move(|x| (self.f)(x)) { - None => return self.frontiter.chain_mut_ref(|it| it.next_back()), - next => self.backiter = next, - } - } - } -} - -/// An iterator that yields `None` forever after the underlying iterator -/// yields `None` once. -#[deriving(Clone, DeepClone)] -pub struct Fuse { - priv iter: T, - priv done: bool -} - -impl> Iterator for Fuse { - #[inline] - fn next(&mut self) -> Option { - if self.done { - None - } else { - match self.iter.next() { - None => { - self.done = true; - None - } - x => x - } - } - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - if self.done { - (0, Some(0)) - } else { - self.iter.size_hint() - } - } -} - -impl> DoubleEndedIterator for Fuse { - #[inline] - fn next_back(&mut self) -> Option { - if self.done { - None - } else { - match self.iter.next_back() { - None => { - self.done = true; - None - } - x => x - } - } - } -} - -// Allow RandomAccessIterators to be fused without affecting random-access behavior -impl> RandomAccessIterator for Fuse { - #[inline] - fn indexable(&self) -> uint { - self.iter.indexable() - } - - #[inline] - fn idx(&self, index: uint) -> Option { - self.iter.idx(index) - } -} - -impl Fuse { - /// Resets the fuse such that the next call to .next() or .next_back() will - /// call the underlying iterator again even if it prevously returned None. - #[inline] - fn reset_fuse(&mut self) { - self.done = false - } -} - -/// An iterator that calls a function with a reference to each -/// element before yielding it. -pub struct Inspect<'self, A, T> { - priv iter: T, - priv f: &'self fn(&A) -} - -impl<'self, A, T> Inspect<'self, A, T> { - #[inline] - fn do_inspect(&self, elt: Option) -> Option { - match elt { - Some(ref a) => (self.f)(a), - None => () - } - - elt - } -} - -impl<'self, A, T: Iterator> Iterator for Inspect<'self, A, T> { - #[inline] - fn next(&mut self) -> Option { - let next = self.iter.next(); - self.do_inspect(next) - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - self.iter.size_hint() - } -} - -impl<'self, A, T: DoubleEndedIterator> DoubleEndedIterator -for Inspect<'self, A, T> { - #[inline] - fn next_back(&mut self) -> Option { - let next = self.iter.next_back(); - self.do_inspect(next) - } -} - -impl<'self, A, T: RandomAccessIterator> RandomAccessIterator -for Inspect<'self, A, T> { - #[inline] - fn indexable(&self) -> uint { - self.iter.indexable() - } - - #[inline] - fn idx(&self, index: uint) -> Option { - self.do_inspect(self.iter.idx(index)) - } -} - -/// An iterator which just modifies the contained state throughout iteration. -pub struct Unfold<'self, A, St> { - priv f: &'self fn(&mut St) -> Option, - /// Internal state that will be yielded on the next iteration - state: St -} - -impl<'self, A, St> Unfold<'self, A, St> { - /// Creates a new iterator with the specified closure as the "iterator - /// function" and an initial state to eventually pass to the iterator - #[inline] - pub fn new<'a>(initial_state: St, f: &'a fn(&mut St) -> Option) - -> Unfold<'a, A, St> { - Unfold { - f: f, - state: initial_state - } - } -} - -impl<'self, A, St> Iterator for Unfold<'self, A, St> { - #[inline] - fn next(&mut self) -> Option { - (self.f)(&mut self.state) - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - // no possible known bounds at this point - (0, None) - } -} - -/// An infinite iterator starting at `start` and advancing by `step` with each -/// iteration -#[deriving(Clone)] -pub struct Counter { - /// The current state the counter is at (next value to be yielded) - state: A, - /// The amount that this iterator is stepping by - step: A -} - -/// Creates a new counter with the specified start/step -#[inline] -pub fn count(start: A, step: A) -> Counter { - Counter{state: start, step: step} -} - -/// A range of numbers from [0, N) -#[deriving(Clone, DeepClone)] -pub struct Range { - priv state: A, - priv stop: A, - priv one: A -} - -/// Return an iterator over the range [start, stop) -#[inline] -pub fn range + Ord + Clone + One>(start: A, stop: A) -> Range { - Range{state: start, stop: stop, one: One::one()} -} - -impl + Ord + Clone> Iterator for Range { - #[inline] - fn next(&mut self) -> Option { - if self.state < self.stop { - let result = self.state.clone(); - self.state = self.state + self.one; - Some(result) - } else { - None - } - } - - // FIXME: #8606 Implement size_hint() on Range - // Blocked on #8605 Need numeric trait for converting to `Option` -} - -impl + Integer + Ord + Clone> DoubleEndedIterator for Range { - #[inline] - fn next_back(&mut self) -> Option { - if self.stop > self.state { - // Integer doesn't technically define this rule, but we're going to assume that every - // Integer is reachable from every other one by adding or subtracting enough Ones. This - // seems like a reasonable-enough rule that every Integer should conform to, even if it - // can't be statically checked. - self.stop = self.stop - self.one; - Some(self.stop.clone()) - } else { - None - } - } -} - -/// A range of numbers from [0, N] -#[deriving(Clone, DeepClone)] -pub struct RangeInclusive { - priv range: Range, - priv done: bool -} - -/// Return an iterator over the range [start, stop] -#[inline] -pub fn range_inclusive + Ord + Clone + One>(start: A, stop: A) -> RangeInclusive { - RangeInclusive{range: range(start, stop), done: false} -} - -impl + Ord + Clone> Iterator for RangeInclusive { - #[inline] - fn next(&mut self) -> Option { - match self.range.next() { - Some(x) => Some(x), - None => { - if self.done { - None - } else { - self.done = true; - Some(self.range.stop.clone()) - } - } - } - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - let (lo, hi) = self.range.size_hint(); - if self.done { - (lo, hi) - } else { - let lo = lo.saturating_add(1); - let hi = match hi { - Some(x) => x.checked_add(&1), - None => None - }; - (lo, hi) - } - } -} - -impl + Integer + Ord + Clone> DoubleEndedIterator for RangeInclusive { - #[inline] - fn next_back(&mut self) -> Option { - if self.range.stop > self.range.state { - let result = self.range.stop.clone(); - self.range.stop = self.range.stop - self.range.one; - Some(result) - } else if self.done { - None - } else { - self.done = true; - Some(self.range.stop.clone()) - } - } -} - -impl + Clone> Iterator for Counter { - #[inline] - fn next(&mut self) -> Option { - let result = self.state.clone(); - self.state = self.state + self.step; - Some(result) - } - - #[inline] - fn size_hint(&self) -> (uint, Option) { - (uint::max_value, None) // Too bad we can't specify an infinite lower bound - } -} - -/// An iterator that repeats an element endlessly -#[deriving(Clone, DeepClone)] -pub struct Repeat { - priv element: A -} - -impl Repeat { - /// Create a new `Repeat` that endlessly repeats the element `elt`. - #[inline] - pub fn new(elt: A) -> Repeat { - Repeat{element: elt} - } -} - -impl Iterator for Repeat { - #[inline] - fn next(&mut self) -> Option { self.idx(0) } - #[inline] - fn size_hint(&self) -> (uint, Option) { (uint::max_value, None) } -} - -impl DoubleEndedIterator for Repeat { - #[inline] - fn next_back(&mut self) -> Option { self.idx(0) } -} - -impl RandomAccessIterator for Repeat { - #[inline] - fn indexable(&self) -> uint { uint::max_value } - #[inline] - fn idx(&self, _: uint) -> Option { Some(self.element.clone()) } -} - -/// Functions for lexicographical ordering of sequences. -/// -/// Lexicographical ordering through `<`, `<=`, `>=`, `>` requires -/// that the elements implement both `Eq` and `Ord`. -/// -/// If two sequences are equal up until the point where one ends, -/// the shorter sequence compares less. -pub mod order { - use cmp; - use cmp::{TotalEq, TotalOrd, Ord, Eq}; - use option::{Some, None}; - use super::Iterator; - - /// Compare `a` and `b` for equality using `TotalOrd` - pub fn equals>(mut a: T, mut b: T) -> bool { - loop { - match (a.next(), b.next()) { - (None, None) => return true, - (None, _) | (_, None) => return false, - (Some(x), Some(y)) => if !x.equals(&y) { return false }, - } - } - } - - /// Order `a` and `b` lexicographically using `TotalOrd` - pub fn cmp>(mut a: T, mut b: T) -> cmp::Ordering { - loop { - match (a.next(), b.next()) { - (None, None) => return cmp::Equal, - (None, _ ) => return cmp::Less, - (_ , None) => return cmp::Greater, - (Some(x), Some(y)) => match x.cmp(&y) { - cmp::Equal => (), - non_eq => return non_eq, - }, - } - } - } - - /// Compare `a` and `b` for equality (Using partial equality, `Eq`) - pub fn eq>(mut a: T, mut b: T) -> bool { - loop { - match (a.next(), b.next()) { - (None, None) => return true, - (None, _) | (_, None) => return false, - (Some(x), Some(y)) => if !x.eq(&y) { return false }, - } - } - } - - /// Compare `a` and `b` for nonequality (Using partial equality, `Eq`) - pub fn ne>(mut a: T, mut b: T) -> bool { - loop { - match (a.next(), b.next()) { - (None, None) => return false, - (None, _) | (_, None) => return true, - (Some(x), Some(y)) => if x.ne(&y) { return true }, - } - } - } - - /// Return `a` < `b` lexicographically (Using partial order, `Ord`) - pub fn lt>(mut a: T, mut b: T) -> bool { - loop { - match (a.next(), b.next()) { - (None, None) => return false, - (None, _ ) => return true, - (_ , None) => return false, - (Some(x), Some(y)) => if x.ne(&y) { return x.lt(&y) }, - } - } - } - - /// Return `a` <= `b` lexicographically (Using partial order, `Ord`) - pub fn le>(mut a: T, mut b: T) -> bool { - loop { - match (a.next(), b.next()) { - (None, None) => return true, - (None, _ ) => return true, - (_ , None) => return false, - (Some(x), Some(y)) => if x.ne(&y) { return x.le(&y) }, - } - } - } - - /// Return `a` > `b` lexicographically (Using partial order, `Ord`) - pub fn gt>(mut a: T, mut b: T) -> bool { - loop { - match (a.next(), b.next()) { - (None, None) => return false, - (None, _ ) => return false, - (_ , None) => return true, - (Some(x), Some(y)) => if x.ne(&y) { return x.gt(&y) }, - } - } - } - - /// Return `a` >= `b` lexicographically (Using partial order, `Ord`) - pub fn ge>(mut a: T, mut b: T) -> bool { - loop { - match (a.next(), b.next()) { - (None, None) => return true, - (None, _ ) => return false, - (_ , None) => return true, - (Some(x), Some(y)) => if x.ne(&y) { return x.ge(&y) }, - } - } - } - - #[test] - fn test_lt() { - use vec::ImmutableVector; - - let empty: [int, ..0] = []; - let xs = [1,2,3]; - let ys = [1,2,0]; - - assert!(!lt(xs.iter(), ys.iter())); - assert!(!le(xs.iter(), ys.iter())); - assert!( gt(xs.iter(), ys.iter())); - assert!( ge(xs.iter(), ys.iter())); - - assert!( lt(ys.iter(), xs.iter())); - assert!( le(ys.iter(), xs.iter())); - assert!(!gt(ys.iter(), xs.iter())); - assert!(!ge(ys.iter(), xs.iter())); - - assert!( lt(empty.iter(), xs.iter())); - assert!( le(empty.iter(), xs.iter())); - assert!(!gt(empty.iter(), xs.iter())); - assert!(!ge(empty.iter(), xs.iter())); - - // Sequence with NaN - let u = [1.0, 2.0]; - let v = [0.0/0.0, 3.0]; - - assert!(!lt(u.iter(), v.iter())); - assert!(!le(u.iter(), v.iter())); - assert!(!gt(u.iter(), v.iter())); - assert!(!ge(u.iter(), v.iter())); - - let a = [0.0/0.0]; - let b = [1.0]; - let c = [2.0]; - - assert!(lt(a.iter(), b.iter()) == (a[0] < b[0])); - assert!(le(a.iter(), b.iter()) == (a[0] <= b[0])); - assert!(gt(a.iter(), b.iter()) == (a[0] > b[0])); - assert!(ge(a.iter(), b.iter()) == (a[0] >= b[0])); - - assert!(lt(c.iter(), b.iter()) == (c[0] < b[0])); - assert!(le(c.iter(), b.iter()) == (c[0] <= b[0])); - assert!(gt(c.iter(), b.iter()) == (c[0] > b[0])); - assert!(ge(c.iter(), b.iter()) == (c[0] >= b[0])); - } -} - -#[cfg(test)] -mod tests { - use super::*; - use prelude::*; - - use cmp; - use uint; - - #[test] - fn test_counter_from_iter() { - let mut it = count(0, 5).take(10); - let xs: ~[int] = FromIterator::from_iterator(&mut it); - assert_eq!(xs, ~[0, 5, 10, 15, 20, 25, 30, 35, 40, 45]); - } - - #[test] - fn test_iterator_chain() { - let xs = [0u, 1, 2, 3, 4, 5]; - let ys = [30u, 40, 50, 60]; - let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60]; - let mut it = xs.iter().chain(ys.iter()); - let mut i = 0; - for &x in it { - assert_eq!(x, expected[i]); - i += 1; - } - assert_eq!(i, expected.len()); - - let ys = count(30u, 10).take(4); - let mut it = xs.iter().map(|&x| x).chain(ys); - let mut i = 0; - for x in it { - assert_eq!(x, expected[i]); - i += 1; - } - assert_eq!(i, expected.len()); - } - - #[test] - fn test_filter_map() { - let mut it = count(0u, 1u).take(10) - .filter_map(|x| if x.is_even() { Some(x*x) } else { None }); - assert_eq!(it.collect::<~[uint]>(), ~[0*0, 2*2, 4*4, 6*6, 8*8]); - } - - #[test] - fn test_iterator_enumerate() { - let xs = [0u, 1, 2, 3, 4, 5]; - let mut it = xs.iter().enumerate(); - for (i, &x) in it { - assert_eq!(i, x); - } - } - - #[test] - fn test_iterator_peekable() { - let xs = ~[0u, 1, 2, 3, 4, 5]; - let mut it = xs.iter().map(|&x|x).peekable(); - assert_eq!(it.peek().unwrap(), &0); - assert_eq!(it.next().unwrap(), 0); - assert_eq!(it.next().unwrap(), 1); - assert_eq!(it.next().unwrap(), 2); - assert_eq!(it.peek().unwrap(), &3); - assert_eq!(it.peek().unwrap(), &3); - assert_eq!(it.next().unwrap(), 3); - assert_eq!(it.next().unwrap(), 4); - assert_eq!(it.peek().unwrap(), &5); - assert_eq!(it.next().unwrap(), 5); - assert!(it.peek().is_none()); - assert!(it.next().is_none()); - } - - #[test] - fn test_iterator_take_while() { - let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19]; - let ys = [0u, 1, 2, 3, 5, 13]; - let mut it = xs.iter().take_while(|&x| *x < 15u); - let mut i = 0; - for &x in it { - assert_eq!(x, ys[i]); - i += 1; - } - assert_eq!(i, ys.len()); - } - - #[test] - fn test_iterator_skip_while() { - let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19]; - let ys = [15, 16, 17, 19]; - let mut it = xs.iter().skip_while(|&x| *x < 15u); - let mut i = 0; - for &x in it { - assert_eq!(x, ys[i]); - i += 1; - } - assert_eq!(i, ys.len()); - } - - #[test] - fn test_iterator_skip() { - let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30]; - let ys = [13, 15, 16, 17, 19, 20, 30]; - let mut it = xs.iter().skip(5); - let mut i = 0; - for &x in it { - assert_eq!(x, ys[i]); - i += 1; - } - assert_eq!(i, ys.len()); - } - - #[test] - fn test_iterator_take() { - let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19]; - let ys = [0u, 1, 2, 3, 5]; - let mut it = xs.iter().take(5); - let mut i = 0; - for &x in it { - assert_eq!(x, ys[i]); - i += 1; - } - assert_eq!(i, ys.len()); - } - - #[test] - fn test_iterator_scan() { - // test the type inference - fn add(old: &mut int, new: &uint) -> Option { - *old += *new as int; - Some(*old as float) - } - let xs = [0u, 1, 2, 3, 4]; - let ys = [0f, 1f, 3f, 6f, 10f]; - - let mut it = xs.iter().scan(0, add); - let mut i = 0; - for x in it { - assert_eq!(x, ys[i]); - i += 1; - } - assert_eq!(i, ys.len()); - } - - #[test] - fn test_iterator_flat_map() { - let xs = [0u, 3, 6]; - let ys = [0u, 1, 2, 3, 4, 5, 6, 7, 8]; - let mut it = xs.iter().flat_map(|&x| count(x, 1).take(3)); - let mut i = 0; - for x in it { - assert_eq!(x, ys[i]); - i += 1; - } - assert_eq!(i, ys.len()); - } - - #[test] - fn test_inspect() { - let xs = [1u, 2, 3, 4]; - let mut n = 0; - - let ys = xs.iter() - .map(|&x| x) - .inspect(|_| n += 1) - .collect::<~[uint]>(); - - assert_eq!(n, xs.len()); - assert_eq!(xs, ys.as_slice()); - } - - #[test] - fn test_unfoldr() { - fn count(st: &mut uint) -> Option { - if *st < 10 { - let ret = Some(*st); - *st += 1; - ret - } else { - None - } - } - - let mut it = Unfold::new(0, count); - let mut i = 0; - for counted in it { - assert_eq!(counted, i); - i += 1; - } - assert_eq!(i, 10); - } - - #[test] - fn test_cycle() { - let cycle_len = 3; - let it = count(0u, 1).take(cycle_len).cycle(); - assert_eq!(it.size_hint(), (uint::max_value, None)); - for (i, x) in it.take(100).enumerate() { - assert_eq!(i % cycle_len, x); - } - - let mut it = count(0u, 1).take(0).cycle(); - assert_eq!(it.size_hint(), (0, Some(0))); - assert_eq!(it.next(), None); - } - - #[test] - fn test_iterator_nth() { - let v = &[0, 1, 2, 3, 4]; - for i in range(0u, v.len()) { - assert_eq!(v.iter().nth(i).unwrap(), &v[i]); - } - } - - #[test] - fn test_iterator_last() { - let v = &[0, 1, 2, 3, 4]; - assert_eq!(v.iter().last().unwrap(), &4); - assert_eq!(v.slice(0, 1).iter().last().unwrap(), &0); - } - - #[test] - fn test_iterator_len() { - let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; - assert_eq!(v.slice(0, 4).iter().len(), 4); - assert_eq!(v.slice(0, 10).iter().len(), 10); - assert_eq!(v.slice(0, 0).iter().len(), 0); - } - - #[test] - fn test_iterator_sum() { - let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; - assert_eq!(v.slice(0, 4).iter().map(|&x| x).sum(), 6); - assert_eq!(v.iter().map(|&x| x).sum(), 55); - assert_eq!(v.slice(0, 0).iter().map(|&x| x).sum(), 0); - } - - #[test] - fn test_iterator_product() { - let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; - assert_eq!(v.slice(0, 4).iter().map(|&x| x).product(), 0); - assert_eq!(v.slice(1, 5).iter().map(|&x| x).product(), 24); - assert_eq!(v.slice(0, 0).iter().map(|&x| x).product(), 1); - } - - #[test] - fn test_iterator_max() { - let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; - assert_eq!(v.slice(0, 4).iter().map(|&x| x).max(), Some(3)); - assert_eq!(v.iter().map(|&x| x).max(), Some(10)); - assert_eq!(v.slice(0, 0).iter().map(|&x| x).max(), None); - } - - #[test] - fn test_iterator_min() { - let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; - assert_eq!(v.slice(0, 4).iter().map(|&x| x).min(), Some(0)); - assert_eq!(v.iter().map(|&x| x).min(), Some(0)); - assert_eq!(v.slice(0, 0).iter().map(|&x| x).min(), None); - } - - #[test] - fn test_iterator_size_hint() { - let c = count(0, 1); - let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; - let v2 = &[10, 11, 12]; - let vi = v.iter(); - - assert_eq!(c.size_hint(), (uint::max_value, None)); - assert_eq!(vi.size_hint(), (10, Some(10))); - - assert_eq!(c.take(5).size_hint(), (5, Some(5))); - assert_eq!(c.skip(5).size_hint().second(), None); - assert_eq!(c.take_while(|_| false).size_hint(), (0, None)); - assert_eq!(c.skip_while(|_| false).size_hint(), (0, None)); - assert_eq!(c.enumerate().size_hint(), (uint::max_value, None)); - assert_eq!(c.chain(vi.map(|&i| i)).size_hint(), (uint::max_value, None)); - assert_eq!(c.zip(vi).size_hint(), (10, Some(10))); - assert_eq!(c.scan(0, |_,_| Some(0)).size_hint(), (0, None)); - assert_eq!(c.filter(|_| false).size_hint(), (0, None)); - assert_eq!(c.map(|_| 0).size_hint(), (uint::max_value, None)); - assert_eq!(c.filter_map(|_| Some(0)).size_hint(), (0, None)); - - assert_eq!(vi.take(5).size_hint(), (5, Some(5))); - assert_eq!(vi.take(12).size_hint(), (10, Some(10))); - assert_eq!(vi.skip(3).size_hint(), (7, Some(7))); - assert_eq!(vi.skip(12).size_hint(), (0, Some(0))); - assert_eq!(vi.take_while(|_| false).size_hint(), (0, Some(10))); - assert_eq!(vi.skip_while(|_| false).size_hint(), (0, Some(10))); - assert_eq!(vi.enumerate().size_hint(), (10, Some(10))); - assert_eq!(vi.chain(v2.iter()).size_hint(), (13, Some(13))); - assert_eq!(vi.zip(v2.iter()).size_hint(), (3, Some(3))); - assert_eq!(vi.scan(0, |_,_| Some(0)).size_hint(), (0, Some(10))); - assert_eq!(vi.filter(|_| false).size_hint(), (0, Some(10))); - assert_eq!(vi.map(|i| i+1).size_hint(), (10, Some(10))); - assert_eq!(vi.filter_map(|_| Some(0)).size_hint(), (0, Some(10))); - } - - #[test] - fn test_collect() { - let a = ~[1, 2, 3, 4, 5]; - let b: ~[int] = a.iter().map(|&x| x).collect(); - assert_eq!(a, b); - } - - #[test] - fn test_all() { - let v: ~&[int] = ~&[1, 2, 3, 4, 5]; - assert!(v.iter().all(|&x| x < 10)); - assert!(!v.iter().all(|&x| x.is_even())); - assert!(!v.iter().all(|&x| x > 100)); - assert!(v.slice(0, 0).iter().all(|_| fail!())); - } - - #[test] - fn test_any() { - let v: ~&[int] = ~&[1, 2, 3, 4, 5]; - assert!(v.iter().any(|&x| x < 10)); - assert!(v.iter().any(|&x| x.is_even())); - assert!(!v.iter().any(|&x| x > 100)); - assert!(!v.slice(0, 0).iter().any(|_| fail!())); - } - - #[test] - fn test_find() { - let v: &[int] = &[1, 3, 9, 27, 103, 14, 11]; - assert_eq!(*v.iter().find(|x| *x & 1 == 0).unwrap(), 14); - assert_eq!(*v.iter().find(|x| *x % 3 == 0).unwrap(), 3); - assert!(v.iter().find(|x| *x % 12 == 0).is_none()); - } - - #[test] - fn test_position() { - let v = &[1, 3, 9, 27, 103, 14, 11]; - assert_eq!(v.iter().position(|x| *x & 1 == 0).unwrap(), 5); - assert_eq!(v.iter().position(|x| *x % 3 == 0).unwrap(), 1); - assert!(v.iter().position(|x| *x % 12 == 0).is_none()); - } - - #[test] - fn test_count() { - let xs = &[1, 2, 2, 1, 5, 9, 0, 2]; - assert_eq!(xs.iter().count(|x| *x == 2), 3); - assert_eq!(xs.iter().count(|x| *x == 5), 1); - assert_eq!(xs.iter().count(|x| *x == 95), 0); - } - - #[test] - fn test_max_by() { - let xs: &[int] = &[-3, 0, 1, 5, -10]; - assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10); - } - - #[test] - fn test_min_by() { - let xs: &[int] = &[-3, 0, 1, 5, -10]; - assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0); - } - - #[test] - fn test_invert() { - let xs = [2, 4, 6, 8, 10, 12, 14, 16]; - let mut it = xs.iter(); - it.next(); - it.next(); - assert_eq!(it.invert().map(|&x| x).collect::<~[int]>(), ~[16, 14, 12, 10, 8, 6]); - } - - #[test] - fn test_double_ended_map() { - let xs = [1, 2, 3, 4, 5, 6]; - let mut it = xs.iter().map(|&x| x * -1); - assert_eq!(it.next(), Some(-1)); - assert_eq!(it.next(), Some(-2)); - assert_eq!(it.next_back(), Some(-6)); - assert_eq!(it.next_back(), Some(-5)); - assert_eq!(it.next(), Some(-3)); - assert_eq!(it.next_back(), Some(-4)); - assert_eq!(it.next(), None); - } - - #[test] - fn test_double_ended_enumerate() { - let xs = [1, 2, 3, 4, 5, 6]; - let mut it = xs.iter().map(|&x| x).enumerate(); - assert_eq!(it.next(), Some((0, 1))); - assert_eq!(it.next(), Some((1, 2))); - assert_eq!(it.next_back(), Some((5, 6))); - assert_eq!(it.next_back(), Some((4, 5))); - assert_eq!(it.next_back(), Some((3, 4))); - assert_eq!(it.next_back(), Some((2, 3))); - assert_eq!(it.next(), None); - } - - #[test] - fn test_double_ended_zip() { - let xs = [1, 2, 3, 4, 5, 6]; - let ys = [1, 2, 3, 7]; - let a = xs.iter().map(|&x| x); - let b = ys.iter().map(|&x| x); - let mut it = a.zip(b); - assert_eq!(it.next(), Some((1, 1))); - assert_eq!(it.next(), Some((2, 2))); - assert_eq!(it.next_back(), Some((4, 7))); - assert_eq!(it.next_back(), Some((3, 3))); - assert_eq!(it.next(), None); - } - - #[test] - fn test_double_ended_filter() { - let xs = [1, 2, 3, 4, 5, 6]; - let mut it = xs.iter().filter(|&x| *x & 1 == 0); - assert_eq!(it.next_back().unwrap(), &6); - assert_eq!(it.next_back().unwrap(), &4); - assert_eq!(it.next().unwrap(), &2); - assert_eq!(it.next_back(), None); - } - - #[test] - fn test_double_ended_filter_map() { - let xs = [1, 2, 3, 4, 5, 6]; - let mut it = xs.iter().filter_map(|&x| if x & 1 == 0 { Some(x * 2) } else { None }); - assert_eq!(it.next_back().unwrap(), 12); - assert_eq!(it.next_back().unwrap(), 8); - assert_eq!(it.next().unwrap(), 4); - assert_eq!(it.next_back(), None); - } - - #[test] - fn test_double_ended_chain() { - let xs = [1, 2, 3, 4, 5]; - let ys = ~[7, 9, 11]; - let mut it = xs.iter().chain(ys.iter()).invert(); - assert_eq!(it.next().unwrap(), &11) - assert_eq!(it.next().unwrap(), &9) - assert_eq!(it.next_back().unwrap(), &1) - assert_eq!(it.next_back().unwrap(), &2) - assert_eq!(it.next_back().unwrap(), &3) - assert_eq!(it.next_back().unwrap(), &4) - assert_eq!(it.next_back().unwrap(), &5) - assert_eq!(it.next_back().unwrap(), &7) - assert_eq!(it.next_back(), None) - } - - #[test] - fn test_rposition() { - fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' } - fn g(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'd' } - let v = ~[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')]; - - assert_eq!(v.iter().rposition(f), Some(3u)); - assert!(v.iter().rposition(g).is_none()); - } - - #[test] - #[should_fail] - fn test_rposition_fail() { - let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)]; - let mut i = 0; - do v.iter().rposition |_elt| { - if i == 2 { - fail!() - } - i += 1; - false - }; - } - - - #[cfg(test)] - fn check_randacc_iter>(a: T, len: uint) - { - let mut b = a.clone(); - assert_eq!(len, b.indexable()); - let mut n = 0; - for (i, elt) in a.enumerate() { - assert_eq!(Some(elt), b.idx(i)); - n += 1; - } - assert_eq!(n, len); - assert_eq!(None, b.idx(n)); - // call recursively to check after picking off an element - if len > 0 { - b.next(); - check_randacc_iter(b, len-1); - } - } - - - #[test] - fn test_double_ended_flat_map() { - let u = [0u,1]; - let v = [5,6,7,8]; - let mut it = u.iter().flat_map(|x| v.slice(*x, v.len()).iter()); - assert_eq!(it.next_back().unwrap(), &8); - assert_eq!(it.next().unwrap(), &5); - assert_eq!(it.next_back().unwrap(), &7); - assert_eq!(it.next_back().unwrap(), &6); - assert_eq!(it.next_back().unwrap(), &8); - assert_eq!(it.next().unwrap(), &6); - assert_eq!(it.next_back().unwrap(), &7); - assert_eq!(it.next_back(), None); - assert_eq!(it.next(), None); - assert_eq!(it.next_back(), None); - } - - #[test] - fn test_random_access_chain() { - let xs = [1, 2, 3, 4, 5]; - let ys = ~[7, 9, 11]; - let mut it = xs.iter().chain(ys.iter()); - assert_eq!(it.idx(0).unwrap(), &1); - assert_eq!(it.idx(5).unwrap(), &7); - assert_eq!(it.idx(7).unwrap(), &11); - assert!(it.idx(8).is_none()); - - it.next(); - it.next(); - it.next_back(); - - assert_eq!(it.idx(0).unwrap(), &3); - assert_eq!(it.idx(4).unwrap(), &9); - assert!(it.idx(6).is_none()); - - check_randacc_iter(it, xs.len() + ys.len() - 3); - } - - #[test] - fn test_random_access_enumerate() { - let xs = [1, 2, 3, 4, 5]; - check_randacc_iter(xs.iter().enumerate(), xs.len()); - } - - #[test] - fn test_random_access_invert() { - let xs = [1, 2, 3, 4, 5]; - check_randacc_iter(xs.iter().invert(), xs.len()); - let mut it = xs.iter().invert(); - it.next(); - it.next_back(); - it.next(); - check_randacc_iter(it, xs.len() - 3); - } - - #[test] - fn test_random_access_zip() { - let xs = [1, 2, 3, 4, 5]; - let ys = [7, 9, 11]; - check_randacc_iter(xs.iter().zip(ys.iter()), cmp::min(xs.len(), ys.len())); - } - - #[test] - fn test_random_access_take() { - let xs = [1, 2, 3, 4, 5]; - let empty: &[int] = []; - check_randacc_iter(xs.iter().take(3), 3); - check_randacc_iter(xs.iter().take(20), xs.len()); - check_randacc_iter(xs.iter().take(0), 0); - check_randacc_iter(empty.iter().take(2), 0); - } - - #[test] - fn test_random_access_skip() { - let xs = [1, 2, 3, 4, 5]; - let empty: &[int] = []; - check_randacc_iter(xs.iter().skip(2), xs.len() - 2); - check_randacc_iter(empty.iter().skip(2), 0); - } - - #[test] - fn test_random_access_inspect() { - let xs = [1, 2, 3, 4, 5]; - - // test .map and .inspect that don't implement Clone - let it = xs.iter().inspect(|_| {}); - assert_eq!(xs.len(), it.indexable()); - for (i, elt) in xs.iter().enumerate() { - assert_eq!(Some(elt), it.idx(i)); - } - - } - - #[test] - fn test_random_access_map() { - let xs = [1, 2, 3, 4, 5]; - - let it = xs.iter().map(|x| *x); - assert_eq!(xs.len(), it.indexable()); - for (i, elt) in xs.iter().enumerate() { - assert_eq!(Some(*elt), it.idx(i)); - } - } - - #[test] - fn test_random_access_cycle() { - let xs = [1, 2, 3, 4, 5]; - let empty: &[int] = []; - check_randacc_iter(xs.iter().cycle().take(27), 27); - check_randacc_iter(empty.iter().cycle(), 0); - } - - #[test] - fn test_double_ended_range() { - assert_eq!(range(11i, 14).invert().collect::<~[int]>(), ~[13i, 12, 11]); - for _ in range(10i, 0).invert() { - fail!("unreachable"); - } - - assert_eq!(range(11u, 14).invert().collect::<~[uint]>(), ~[13u, 12, 11]); - for _ in range(10u, 0).invert() { - fail!("unreachable"); - } - } - - #[test] - fn test_range_inclusive() { - assert_eq!(range_inclusive(0i, 5).collect::<~[int]>(), ~[0i, 1, 2, 3, 4, 5]); - assert_eq!(range_inclusive(0i, 5).invert().collect::<~[int]>(), ~[5i, 4, 3, 2, 1, 0]); - } - - #[test] - fn test_reverse() { - let mut ys = [1, 2, 3, 4, 5]; - ys.mut_iter().reverse_(); - assert_eq!(ys, [5, 4, 3, 2, 1]); - } -} diff --git a/src/libstd/option.rs b/src/libstd/option.rs index dd66630187d..b72046cce72 100644 --- a/src/libstd/option.rs +++ b/src/libstd/option.rs @@ -45,8 +45,8 @@ use clone::Clone; use cmp::{Eq,Ord}; use util; use num::Zero; -use iterator; -use iterator::{Iterator, DoubleEndedIterator, ExactSize}; +use iter; +use iter::{Iterator, DoubleEndedIterator, ExactSize}; use str::{StrSlice, OwnedStr}; use to_str::ToStr; use clone::DeepClone; @@ -60,19 +60,19 @@ pub enum Option { impl Ord for Option { fn lt(&self, other: &Option) -> bool { - iterator::order::lt(self.iter(), other.iter()) + iter::order::lt(self.iter(), other.iter()) } fn le(&self, other: &Option) -> bool { - iterator::order::le(self.iter(), other.iter()) + iter::order::le(self.iter(), other.iter()) } fn ge(&self, other: &Option) -> bool { - iterator::order::ge(self.iter(), other.iter()) + iter::order::ge(self.iter(), other.iter()) } fn gt(&self, other: &Option) -> bool { - iterator::order::gt(self.iter(), other.iter()) + iter::order::gt(self.iter(), other.iter()) } } diff --git a/src/libstd/os.rs b/src/libstd/os.rs index ffd99fc9f75..ab1210aabad 100644 --- a/src/libstd/os.rs +++ b/src/libstd/os.rs @@ -32,7 +32,7 @@ use c_str::ToCStr; use clone::Clone; use container::Container; use io; -use iterator::range; +use iter::range; use libc; use libc::{c_char, c_void, c_int, size_t}; use libc::FILE; diff --git a/src/libstd/path.rs b/src/libstd/path.rs index 58668775136..336284963a2 100644 --- a/src/libstd/path.rs +++ b/src/libstd/path.rs @@ -21,7 +21,7 @@ use c_str; use clone::Clone; use cmp::Eq; use container::Container; -use iterator::{Iterator, range}; +use iter::{Iterator, range}; use libc; use num; use option::{None, Option, Some}; diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs index 9cdf7af091f..818b0562955 100644 --- a/src/libstd/prelude.rs +++ b/src/libstd/prelude.rs @@ -40,7 +40,7 @@ pub use result::{Result, Ok, Err}; // Reexported functions pub use io::{print, println}; -pub use iterator::range; +pub use iter::range; pub use from_str::from_str; // Reexported types and traits @@ -51,9 +51,9 @@ pub use char::Char; pub use container::{Container, Mutable, Map, MutableMap, Set, MutableSet}; pub use hash::Hash; pub use num::Times; -pub use iterator::{FromIterator, Extendable}; -pub use iterator::{Iterator, DoubleEndedIterator, RandomAccessIterator, ClonableIterator}; -pub use iterator::{OrdIterator, MutableDoubleEndedIterator, ExactSize}; +pub use iter::{FromIterator, Extendable}; +pub use iter::{Iterator, DoubleEndedIterator, RandomAccessIterator, ClonableIterator}; +pub use iter::{OrdIterator, MutableDoubleEndedIterator, ExactSize}; pub use num::{Num, NumCast, CheckedAdd, CheckedSub, CheckedMul}; pub use num::{Orderable, Signed, Unsigned, Round}; pub use num::{Algebraic, Trigonometric, Exponential, Hyperbolic}; diff --git a/src/libstd/ptr.rs b/src/libstd/ptr.rs index 38d8a244895..fafb1511973 100644 --- a/src/libstd/ptr.rs +++ b/src/libstd/ptr.rs @@ -14,7 +14,7 @@ use cast; use clone::Clone; #[cfg(not(test))] use cmp::Equiv; -use iterator::{range, Iterator}; +use iter::{range, Iterator}; use option::{Option, Some, None}; #[cfg(stage0)] use sys; diff --git a/src/libstd/rand.rs b/src/libstd/rand.rs index 58c75d3b408..813901207bb 100644 --- a/src/libstd/rand.rs +++ b/src/libstd/rand.rs @@ -48,7 +48,7 @@ use clone::Clone; use cmp; use container::Container; use int; -use iterator::{Iterator, range}; +use iter::{Iterator, range}; use local_data; use num; use prelude::*; @@ -957,7 +957,7 @@ pub fn random() -> T { #[cfg(test)] mod test { - use iterator::{Iterator, range}; + use iter::{Iterator, range}; use option::{Option, Some}; use super::*; diff --git a/src/libstd/repr.rs b/src/libstd/repr.rs index 9873317738d..fe45e20a2f0 100644 --- a/src/libstd/repr.rs +++ b/src/libstd/repr.rs @@ -20,7 +20,7 @@ use cast::transmute; use char; use container::Container; use rt::io; -use iterator::Iterator; +use iter::Iterator; use libc::c_void; use option::{Some, None}; use ptr; diff --git a/src/libstd/repr_stage0.rs b/src/libstd/repr_stage0.rs index 4e580d91d0c..cbce2005141 100644 --- a/src/libstd/repr_stage0.rs +++ b/src/libstd/repr_stage0.rs @@ -20,7 +20,7 @@ use cast::transmute; use char; use container::Container; use io::{Writer, WriterUtil}; -use iterator::Iterator; +use iter::Iterator; use libc::c_void; use option::{Some, None}; use ptr; diff --git a/src/libstd/result.rs b/src/libstd/result.rs index c7613ed3c2f..793086dca78 100644 --- a/src/libstd/result.rs +++ b/src/libstd/result.rs @@ -15,7 +15,7 @@ use clone::Clone; use cmp::Eq; use either; -use iterator::Iterator; +use iter::Iterator; use option::{None, Option, Some, OptionIterator}; use vec; use vec::OwnedVector; @@ -335,7 +335,7 @@ mod tests { use super::*; use either; - use iterator::range; + use iter::range; use str::OwnedStr; use vec::ImmutableVector; diff --git a/src/libstd/rt/args.rs b/src/libstd/rt/args.rs index e5075f8818a..afa8d3261fc 100644 --- a/src/libstd/rt/args.rs +++ b/src/libstd/rt/args.rs @@ -55,7 +55,7 @@ pub fn clone() -> Option<~[~str]> { mod imp { use libc; use option::{Option, Some, None}; - use iterator::Iterator; + use iter::Iterator; use str; use unstable::finally::Finally; use util; diff --git a/src/libstd/rt/io/extensions.rs b/src/libstd/rt/io/extensions.rs index 15ac6544dee..e221f0ee94d 100644 --- a/src/libstd/rt/io/extensions.rs +++ b/src/libstd/rt/io/extensions.rs @@ -15,7 +15,7 @@ use uint; use int; -use iterator::Iterator; +use iter::Iterator; use vec; use rt::io::{Reader, Writer, Decorator}; use rt::io::{read_error, standard_error, EndOfFile, DEFAULT_BUF_SIZE}; diff --git a/src/libstd/rt/mod.rs b/src/libstd/rt/mod.rs index 14ff1fd5804..c9c3c4ec6da 100644 --- a/src/libstd/rt/mod.rs +++ b/src/libstd/rt/mod.rs @@ -59,7 +59,7 @@ Several modules in `core` are clients of `rt`: use cell::Cell; use clone::Clone; use container::Container; -use iterator::Iterator; +use iter::Iterator; use option::{Option, None, Some}; use ptr::RawPtr; use rt::local::Local; diff --git a/src/libstd/rt/sched.rs b/src/libstd/rt/sched.rs index 6aa66a6ab6b..bcf9ae4a2a8 100644 --- a/src/libstd/rt/sched.rs +++ b/src/libstd/rt/sched.rs @@ -27,7 +27,7 @@ use rt::rtio::{RemoteCallback, PausibleIdleCallback}; use borrow::{to_uint}; use cell::Cell; use rand::{XorShiftRng, RngUtil}; -use iterator::{range}; +use iter::range; use vec::{OwnedVector}; /// A scheduler is responsible for coordinating the execution of Tasks diff --git a/src/libstd/rt/test.rs b/src/libstd/rt/test.rs index 2c293af1eaf..f35fe1a1d04 100644 --- a/src/libstd/rt/test.rs +++ b/src/libstd/rt/test.rs @@ -14,7 +14,7 @@ use option::{Some, None}; use cell::Cell; use clone::Clone; use container::Container; -use iterator::{Iterator, range}; +use iter::{Iterator, range}; use super::io::net::ip::{SocketAddr, Ipv4Addr, Ipv6Addr}; use vec::{OwnedVector, MutableVector, ImmutableVector}; use rt::sched::Scheduler; diff --git a/src/libstd/rt/uv/uvio.rs b/src/libstd/rt/uv/uvio.rs index c9b12e47f92..65910e5ad08 100644 --- a/src/libstd/rt/uv/uvio.rs +++ b/src/libstd/rt/uv/uvio.rs @@ -44,7 +44,7 @@ use task; #[cfg(test)] use rt::test::{spawntask, next_test_ip4, run_in_newsched_task}; -#[cfg(test)] use iterator::{Iterator, range}; +#[cfg(test)] use iter::{Iterator, range}; // XXX we should not be calling uvll functions in here. diff --git a/src/libstd/select.rs b/src/libstd/select.rs index 9f4fd8db788..94db609e9c7 100644 --- a/src/libstd/select.rs +++ b/src/libstd/select.rs @@ -11,7 +11,7 @@ use cell::Cell; use comm; use container::Container; -use iterator::{Iterator, DoubleEndedIterator}; +use iter::{Iterator, DoubleEndedIterator}; use option::*; // use either::{Either, Left, Right}; // use rt::kill::BlockedTask; @@ -134,7 +134,7 @@ mod test { use comm::GenericChan; use task; use cell::Cell; - use iterator::{Iterator, range}; + use iter::{Iterator, range}; #[test] #[should_fail] fn select_doesnt_get_trolled() { diff --git a/src/libstd/std.rs b/src/libstd/std.rs index ce0202ded7e..65fd24b7219 100644 --- a/src/libstd/std.rs +++ b/src/libstd/std.rs @@ -140,7 +140,7 @@ pub mod borrow; pub mod from_str; #[path = "num/num.rs"] pub mod num; -pub mod iterator; +pub mod iter; pub mod to_str; pub mod to_bytes; pub mod clone; diff --git a/src/libstd/str.rs b/src/libstd/str.rs index 9d718c30edb..0f125280c2d 100644 --- a/src/libstd/str.rs +++ b/src/libstd/str.rs @@ -23,9 +23,9 @@ use char::Char; use clone::{Clone, DeepClone}; use container::{Container, Mutable}; use num::Times; -use iterator::{Iterator, FromIterator, Extendable}; -use iterator::{Filter, AdditiveIterator, Map}; -use iterator::{Invert, DoubleEndedIterator, ExactSize}; +use iter::{Iterator, FromIterator, Extendable}; +use iter::{Filter, AdditiveIterator, Map}; +use iter::{Invert, DoubleEndedIterator, ExactSize}; use libc; use num::{Saturating}; use option::{None, Option, Some}; @@ -592,7 +592,7 @@ impl<'self> Iterator<&'self str> for StrSplitIterator<'self> { // Helper functions used for Unicode normalization fn canonical_sort(comb: &mut [(char, u8)]) { - use iterator::range; + use iter::range; use tuple::CopyableTuple; let len = comb.len(); @@ -3325,7 +3325,7 @@ mod tests { #[test] fn test_iterator() { - use iterator::*; + use iter::*; let s = ~"ศไทย中华Việt Nam"; let v = ~['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m']; @@ -3341,7 +3341,7 @@ mod tests { #[test] fn test_rev_iterator() { - use iterator::*; + use iter::*; let s = ~"ศไทย中华Việt Nam"; let v = ~['m', 'a', 'N', ' ', 't', 'ệ','i','V','华','中','ย','ท','ไ','ศ']; @@ -3397,7 +3397,7 @@ mod tests { #[test] fn test_char_offset_iterator() { - use iterator::*; + use iter::*; let s = "ศไทย中华Việt Nam"; let p = [0, 3, 6, 9, 12, 15, 18, 19, 20, 23, 24, 25, 26, 27]; let v = ['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m']; @@ -3415,7 +3415,7 @@ mod tests { #[test] fn test_char_offset_rev_iterator() { - use iterator::*; + use iter::*; let s = "ศไทย中华Việt Nam"; let p = [27, 26, 25, 24, 23, 20, 19, 18, 15, 12, 9, 6, 3, 0]; let v = ['m', 'a', 'N', ' ', 't', 'ệ','i','V','华','中','ย','ท','ไ','ศ']; diff --git a/src/libstd/str/ascii.rs b/src/libstd/str/ascii.rs index 4ed969f628e..2dd93feef05 100644 --- a/src/libstd/str/ascii.rs +++ b/src/libstd/str/ascii.rs @@ -17,7 +17,7 @@ use str::OwnedStr; use container::Container; use cast; use ptr; -use iterator::Iterator; +use iter::Iterator; use vec::{CopyableVector, ImmutableVector}; use to_bytes::IterBytes; use option::{Some, None}; diff --git a/src/libstd/to_bytes.rs b/src/libstd/to_bytes.rs index e3615b7b7db..855cdfcb851 100644 --- a/src/libstd/to_bytes.rs +++ b/src/libstd/to_bytes.rs @@ -18,7 +18,7 @@ use cast; use container::Container; use io; use io::Writer; -use iterator::Iterator; +use iter::Iterator; use option::{None, Option, Some}; use str::{Str, StrSlice}; use vec::{Vector, ImmutableVector}; diff --git a/src/libstd/to_str.rs b/src/libstd/to_str.rs index a8c450a0516..ff701267189 100644 --- a/src/libstd/to_str.rs +++ b/src/libstd/to_str.rs @@ -19,7 +19,7 @@ use str::OwnedStr; use hashmap::HashMap; use hashmap::HashSet; use hash::Hash; -use iterator::Iterator; +use iter::Iterator; use cmp::Eq; use vec::ImmutableVector; diff --git a/src/libstd/trie.rs b/src/libstd/trie.rs index f5c7b719c4f..32797216376 100644 --- a/src/libstd/trie.rs +++ b/src/libstd/trie.rs @@ -11,7 +11,6 @@ //! An ordered map and set for integer keys implemented as a radix trie use prelude::*; -use iterator::{FromIterator, Extendable}; use uint; use util::{swap, replace}; use vec; diff --git a/src/libstd/unicode.rs b/src/libstd/unicode.rs index 1b1e4be4ee1..d7f84a6abfb 100644 --- a/src/libstd/unicode.rs +++ b/src/libstd/unicode.rs @@ -3628,7 +3628,7 @@ pub mod decompose { } fn d(c: char, i: &fn(char), k: bool) { - use iterator::Iterator; + use iter::Iterator; if c <= '\x7f' { i(c); return; } match bsearch_table(c, canonical_table) { diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs index 4cc5c4f14ff..138a1cab5a0 100644 --- a/src/libstd/vec.rs +++ b/src/libstd/vec.rs @@ -63,7 +63,7 @@ use clone::{Clone, DeepClone}; use container::{Container, Mutable}; use cmp::{Eq, TotalOrd, Ordering, Less, Equal, Greater}; use cmp; -use iterator::*; +use iter::*; use libc::c_void; use num::{Integer, Zero, CheckedAdd, Saturating}; use option::{None, Option, Some}; @@ -592,7 +592,7 @@ pub mod traits { use clone::Clone; use cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Equiv}; - use iterator::order; + use iter::order; use ops::Add; impl<'self,T:Eq> Eq for &'self [T] { @@ -3241,7 +3241,7 @@ mod tests { #[test] fn test_iterator() { - use iterator::*; + use iter::*; let xs = [1, 2, 5, 10, 11]; let mut it = xs.iter(); assert_eq!(it.size_hint(), (5, Some(5))); @@ -3260,7 +3260,7 @@ mod tests { #[test] fn test_random_access_iterator() { - use iterator::*; + use iter::*; let xs = [1, 2, 5, 10, 11]; let mut it = xs.iter(); @@ -3299,7 +3299,7 @@ mod tests { #[test] fn test_iter_size_hints() { - use iterator::*; + use iter::*; let mut xs = [1, 2, 5, 10, 11]; assert_eq!(xs.iter().size_hint(), (5, Some(5))); assert_eq!(xs.rev_iter().size_hint(), (5, Some(5))); @@ -3320,7 +3320,7 @@ mod tests { #[test] fn test_mut_iterator() { - use iterator::*; + use iter::*; let mut xs = [1, 2, 3, 4, 5]; for x in xs.mut_iter() { *x += 1; @@ -3330,7 +3330,7 @@ mod tests { #[test] fn test_rev_iterator() { - use iterator::*; + use iter::*; let xs = [1, 2, 5, 10, 11]; let ys = [11, 10, 5, 2, 1]; @@ -3344,7 +3344,7 @@ mod tests { #[test] fn test_mut_rev_iterator() { - use iterator::*; + use iter::*; let mut xs = [1u, 2, 3, 4, 5]; for (i,x) in xs.mut_rev_iter().enumerate() { *x += i; @@ -3354,14 +3354,14 @@ mod tests { #[test] fn test_move_iterator() { - use iterator::*; + use iter::*; let xs = ~[1u,2,3,4,5]; assert_eq!(xs.move_iter().fold(0, |a: uint, b: uint| 10*a + b), 12345); } #[test] fn test_move_rev_iterator() { - use iterator::*; + use iter::*; let xs = ~[1u,2,3,4,5]; assert_eq!(xs.move_rev_iter().fold(0, |a: uint, b: uint| 10*a + b), 54321); } diff --git a/src/test/auxiliary/nested_item.rs b/src/test/auxiliary/nested_item.rs index e9dde0d14a3..c2f38134d1e 100644 --- a/src/test/auxiliary/nested_item.rs +++ b/src/test/auxiliary/nested_item.rs @@ -26,7 +26,7 @@ impl Foo { // issue 8134 pub struct Parser; -impl> Parser { +impl> Parser { fn in_doctype(&mut self) { static DOCTYPEPattern: [char, ..6] = ['O', 'C', 'T', 'Y', 'P', 'E']; } diff --git a/src/test/run-pass/unfold-cross-crate.rs b/src/test/run-pass/unfold-cross-crate.rs index 64cf3077c53..42e680d95e1 100644 --- a/src/test/run-pass/unfold-cross-crate.rs +++ b/src/test/run-pass/unfold-cross-crate.rs @@ -8,7 +8,7 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use std::iterator::*; +use std::iter::*; // Unfold had a bug with 'self that mean it didn't work // cross-crate -- cgit 1.4.1-3-g733a5