new, simpler approach to the iter library

8 files changed, 140 insertions, 152 deletions

diff --git a/src/libcore/core.rc b/src/libcore/core.rc
index f32895fb7ae..fa423809404 100644
--- a/src/libcore/core.rc
+++ b/src/libcore/core.rc
@@ -42,6 +42,9 @@ export extfmt;
 export tuple;
 export to_str;
 
+// NDM seems to be necessary for resolve to work
+export vec_iter, option_iter;
+
 // FIXME: This creates some APIs that I do not want to commit to. It is
 // currently exported for the uv code in std, but when that code moves into
 // core this should become unexported
@@ -144,16 +147,25 @@ mod f64;
 mod str;
 mod ptr;
 mod vec;
+#[path="iter-trait"]
+mod vec_iter {
+    #[path = "vec.rs"]
+    mod inst;
+}
 mod bool;
 mod tuple;
 
-
 // Ubiquitous-utility-type modules
 
 mod either;
 mod iter;
 mod logging;
 mod option;
+#[path="iter-trait"]
+mod option_iter {
+    #[path = "option.rs"]
+    mod inst;
+}
 mod result;
 mod to_str;
 
@@ -195,5 +207,4 @@ mod cmath;
 // indent-tabs-mode: nil
 // c-basic-offset: 4
 // buffer-file-coding-system: utf-8-unix
-// compile-command: "make -k -C .. 2>&1 | sed -e 's/\\/x\\//x:\\//g'";
 // End:
diff --git a/src/libcore/core.rs b/src/libcore/core.rs
index d359cbf083d..8681f7d2a1c 100644
--- a/src/libcore/core.rs
+++ b/src/libcore/core.rs
@@ -7,7 +7,9 @@ import option = option::option;
 import path = path::path;
 import str::extensions;
 import vec::extensions;
+import vec_iter::extensions;
 import option::extensions;
+import option_iter::extensions;
 import ptr::extensions;
 
 export path, option, some, none, unreachable;
diff --git a/src/libcore/iter-trait.rs b/src/libcore/iter-trait.rs
new file mode 100644
index 00000000000..8c23bb0ac54
--- /dev/null
+++ b/src/libcore/iter-trait.rs
@@ -0,0 +1,35 @@
+// This makes use of a clever hack that brson came up with to
+// workaround our lack of traits and lack of macros.  See core.{rc,rs} for
+// how this file is used.
+
+import inst::{IMPL_T, EACH, SIZE_HINT};
+export extensions;
+
+impl extensions<A> of iter::base_iter<A> for IMPL_T<A> {
+    fn each(blk: fn(A) -> bool) { EACH(self, blk) }
+    fn size_hint() -> option<uint> { SIZE_HINT(self) }
+    fn eachi(blk: fn(uint, A) -> bool) { iter::eachi(self, blk) }
+    fn all(blk: fn(A) -> bool) -> bool { iter::all(self, blk) }
+    fn any(blk: fn(A) -> bool) -> bool { iter::any(self, blk) }
+    fn foldl<B>(+b0: B, blk: fn(B, A) -> B) -> B {
+        iter::foldl(self, b0, blk)
+    }
+    fn contains(x: A) -> bool { iter::contains(self, x) }
+    fn count(x: A) -> uint { iter::count(self, x) }
+}
+
+impl extensions<A:copy> for IMPL_T<A> {
+    fn filter_to_vec(pred: fn(A) -> bool) -> [A] {
+        iter::filter_to_vec(self, pred)
+    }
+    fn map_to_vec<B>(op: fn(A) -> B) -> [B] { iter::map_to_vec(self, op) }
+    fn to_vec() -> [A] { iter::to_vec(self) }
+
+    // FIXME--bug in resolve prevents this from working
+    // fn flat_map_to_vec<B:copy,IB:base_iter<B>>(op: fn(A) -> IB) -> [B] {
+    //     iter::flat_map_to_vec(self, op)
+    // }
+
+    fn min() -> A { iter::min(self) }
+    fn max() -> A { iter::max(self) }
+}
diff --git a/src/libcore/iter-trait/option.rs b/src/libcore/iter-trait/option.rs
new file mode 100644
index 00000000000..530de27c614
--- /dev/null
+++ b/src/libcore/iter-trait/option.rs
@@ -0,0 +1,15 @@
+type IMPL_T<A> = option<A>;
+
+fn EACH<A>(self: IMPL_T<A>, f: fn(A) -> bool) {
+    alt self {
+      none { }
+      some(a) { f(a); }
+    }
+}
+
+fn SIZE_HINT<A>(self: IMPL_T<A>) -> option<uint> {
+    alt self {
+      none { some(0u) }
+      some(_) { some(1u) }
+    }
+}
diff --git a/src/libcore/iter-trait/vec.rs b/src/libcore/iter-trait/vec.rs
new file mode 100644
index 00000000000..62f9458303b
--- /dev/null
+++ b/src/libcore/iter-trait/vec.rs
@@ -0,0 +1,9 @@
+type IMPL_T<A> = [const A];
+
+fn EACH<A>(self: IMPL_T<A>, f: fn(A) -> bool) {
+    vec::each(self, f)
+}
+
+fn SIZE_HINT<A>(self: IMPL_T<A>) -> option<uint> {
+    some(vec::len(self))
+}
diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs
index 7b1bffaada1..80ccfc1422e 100644
--- a/src/libcore/iter.rs
+++ b/src/libcore/iter.rs
@@ -1,115 +1,81 @@
-iface iterable<A> {
-    fn iter(blk: fn(A));
+iface base_iter<A> {
+    fn each(blk: fn(A) -> bool);
+    fn size_hint() -> option<uint>;
 }
 
-impl<A> of iterable<A> for fn@(fn(A)) {
-    fn iter(blk: fn(A)) {
-        self(blk);
-    }
-}
-
-// accomodate the fact that int/uint are passed by value by default:
-impl of iterable<int> for fn@(fn(int)) {
-    fn iter(blk: fn(&&int)) {
-        self {|i| blk(i)}
-    }
-}
-
-impl of iterable<uint> for fn@(fn(uint)) {
-    fn iter(blk: fn(&&uint)) {
-        self {|i| blk(i)}
-    }
-}
-
-impl<A> of iterable<A> for [A] {
-    fn iter(blk: fn(A)) {
-        vec::iter(self, blk)
-    }
-}
-
-impl<A> of iterable<A> for option<A> {
-    fn iter(blk: fn(A)) {
-        option::iter(self, blk)
-    }
-}
-
-impl of iterable<char> for str {
-    fn iter(blk: fn(&&char)) {
-        str::chars_iter(self) { |ch| blk(ch) }
-    }
-}
-
-fn enumerate<A,IA:iterable<A>>(self: IA, blk: fn(uint, A)) {
+fn eachi<A,IA:base_iter<A>>(self: IA, blk: fn(uint, A) -> bool) {
     let mut i = 0u;
-    self.iter {|a|
-        blk(i, a);
+    for self.each {|a|
+        if !blk(i, a) { break; }
         i += 1u;
     }
 }
 
-// Here: we have to use fn@ for predicates and map functions, because
-// we will be binding them up into a closure.  Disappointing.  A true
-// region type system might be able to do better than this.
-
-fn filter<A,IA:iterable<A>>(self: IA, prd: fn@(A) -> bool, blk: fn(A)) {
-    self.iter {|a|
-        if prd(a) { blk(a) }
+fn all<A,IA:base_iter<A>>(self: IA, blk: fn(A) -> bool) -> bool {
+    for self.each {|a|
+        if !blk(a) { ret false; }
     }
+    ret true;
 }
 
-fn filter_map<A,B,IA:iterable<A>>(self: IA, cnv: fn@(A) -> option<B>,
-                                  blk: fn(B)) {
-    self.iter {|a|
-        alt cnv(a) {
-          some(b) { blk(b) }
-          none { }
-        }
+fn any<A,IA:base_iter<A>>(self: IA, blk: fn(A) -> bool) -> bool {
+    for self.each {|a|
+        if blk(a) { ret true; }
     }
+    ret false;
 }
 
-fn map<A,B,IA:iterable<A>>(self: IA, cnv: fn@(A) -> B, blk: fn(B)) {
-    self.iter {|a|
-        let b = cnv(a);
-        blk(b);
+fn filter_to_vec<A:copy,IA:base_iter<A>>(self: IA,
+                                         prd: fn(A) -> bool) -> [A] {
+    let mut result = [];
+    self.size_hint().iter {|hint| vec::reserve(result, hint); }
+    for self.each {|a|
+        if prd(a) { vec::push(result, a); }
     }
+    ret result;
 }
 
-fn flat_map<A,B,IA:iterable<A>,IB:iterable<B>>(
-    self: IA, cnv: fn@(A) -> IB, blk: fn(B)) {
-    self.iter {|a|
-        cnv(a).iter(blk)
+fn map_to_vec<A:copy,B,IA:base_iter<A>>(self: IA, op: fn(A) -> B) -> [B] {
+    let mut result = [];
+    self.size_hint().iter {|hint| vec::reserve(result, hint); }
+    for self.each {|a|
+        vec::push(result, op(a));
     }
+    ret result;
 }
 
-fn foldl<A,B,IA:iterable<A>>(self: IA, +b0: B, blk: fn(B, A) -> B) -> B {
-    let mut b <- b0;
-    self.iter {|a|
-        b <- blk(b, a);
+fn flat_map_to_vec<A:copy,B:copy,IA:base_iter<A>,IB:base_iter<B>>(
+    self: IA, op: fn(A) -> IB) -> [B] {
+
+    let mut result = [];
+    for self.each {|a|
+        for op(a).each {|b|
+            vec::push(result, b);
+        }
     }
-    ret b;
+    ret result;
 }
 
-fn foldr<A:copy,B,IA:iterable<A>>(
-    self: IA, +b0: B, blk: fn(A, B) -> B) -> B {
-
+fn foldl<A,B,IA:base_iter<A>>(self: IA, +b0: B, blk: fn(B, A) -> B) -> B {
     let mut b <- b0;
-    reversed(self) {|a|
-        b <- blk(a, b);
+    for self.each {|a|
+        b = blk(b, a);
     }
     ret b;
 }
 
-fn to_vec<A:copy,IA:iterable<A>>(self: IA) -> [A] {
+fn to_vec<A:copy,IA:base_iter<A>>(self: IA) -> [A] {
     foldl::<A,[A],IA>(self, [], {|r, a| r + [a]})
 }
 
-// FIXME: This could be made more efficient with an riterable interface
-// #2005
-fn reversed<A:copy,IA:iterable<A>>(self: IA, blk: fn(A)) {
-    vec::riter(to_vec(self), blk)
+fn contains<A,IA:base_iter<A>>(self: IA, x: A) -> bool {
+    for self.each {|a|
+        if a == x { ret true; }
+    }
+    ret false;
 }
 
-fn count<A,IA:iterable<A>>(self: IA, x: A) -> uint {
+fn count<A,IA:base_iter<A>>(self: IA, x: A) -> uint {
     foldl(self, 0u) {|count, value|
         if value == x {
             count + 1u
@@ -127,7 +93,7 @@ fn repeat(times: uint, blk: fn()) {
     }
 }
 
-fn min<A:copy,IA:iterable<A>>(self: IA) -> A {
+fn min<A:copy,IA:base_iter<A>>(self: IA) -> A {
     alt foldl::<A,option<A>,IA>(self, none) {|a, b|
         alt a {
           some(a_) if a_ < b {
@@ -143,7 +109,7 @@ fn min<A:copy,IA:iterable<A>>(self: IA) -> A {
     }
 }
 
-fn max<A:copy,IA:iterable<A>>(self: IA) -> A {
+fn max<A:copy,IA:base_iter<A>>(self: IA) -> A {
     alt foldl::<A,option<A>,IA>(self, none) {|a, b|
         alt a {
           some(a_) if a_ > b {
@@ -159,6 +125,7 @@ fn max<A:copy,IA:iterable<A>>(self: IA) -> A {
     }
 }
 
+/*
 #[test]
 fn test_enumerate() {
     enumerate(["0", "1", "2"]) {|i,j|
@@ -296,4 +263,5 @@ fn test_foldr() {
     }
     let sum = foldr([1, 2, 3, 4], 0, sub);
     assert sum == -2;
-}
\ No newline at end of file
+}
+*/
diff --git a/src/libcore/option.rs b/src/libcore/option.rs
index db0d0030f83..3cf4bc92321 100644
--- a/src/libcore/option.rs
+++ b/src/libcore/option.rs
@@ -101,23 +101,6 @@ impl extensions<T:copy> for option<T> {
     #[doc = "Performs an operation on the contained value or does nothing"]
     fn iter(f: fn(T)) { iter(self, f) }
 
-    #[doc = "Converts `none` to a zero-element list and `some` to a \
-             one-element list."]
-    fn to_vec() -> [T] {
-        alt self {
-          some(t) { [t] }
-          none { [] }
-        }
-    }
-
-    #[doc = "Performs an operation on the contained value or does nothing"]
-    fn each(f: fn(T) -> bool) {
-        alt self {
-          none { /* ok */ }
-          some(e) { f(e); }
-        }
-    }
-
     #[doc = "
     Gets the value out of an option
 
diff --git a/src/libcore/vec.rs b/src/libcore/vec.rs
index 191012e5156..ad1c3f2344a 100644
--- a/src/libcore/vec.rs
+++ b/src/libcore/vec.rs
@@ -494,7 +494,7 @@ holds.
 Apply function `f` to each element of `v` and return a vector containing
 only those elements for which `f` returned true.
 "]
-fn filter<T: copy>(v: [T], f: fn(T) -> bool) -> [T] {
+fn filter<T: copy>(v: [const T], f: fn(T) -> bool) -> [T] {
     let mut result = [];
     for each(v) {|elem|
         if f(elem) { result += [elem]; }
@@ -970,23 +970,6 @@ fn unpack_slice<T,U>(s: [const T]/&, f: fn(*T, uint) -> U) -> U unsafe {
 
 #[doc = "Extension methods for vectors"]
 impl extensions<T> for [const T] {
-    #[doc = "
-    Return true if a vector contains an element with the given value
-    "]
-    #[inline]
-    fn contains(x: T) -> bool { contains(self, x) }
-    #[doc = "Returns the number of elements that are equal to a given value"]
-    #[inline]
-    fn count(x: T) -> uint { count(self, x) }
-    #[doc = "Iterates over a vector, with option to break"]
-    #[inline]
-    fn each<T>(f: fn(T) -> bool) { each(self, f) }
-    #[doc = "Iterates over a vector's elements and indices"]
-    #[inline]
-    fn eachi<T>(f: fn(uint, T) -> bool) { eachi(self, f) }
-    #[doc = "Reduce a vector from left to right"]
-    #[inline]
-    fn foldl<U: copy>(z: U, p: fn(U, T) -> U) -> U { foldl(z, self, p) }
     #[doc = "Reduce a vector from right to left"]
     #[inline]
     fn foldr<U: copy>(z: U, p: fn(T, U) -> U) -> U { foldr(self, z, p) }
@@ -1060,6 +1043,15 @@ impl extensions<T> for [const T] {
 #[doc = "Extension methods for vectors"]
 impl extensions<T: copy> for [const T] {
     #[doc = "
+    Construct a new vector from the elements of a vector for which some
+    predicate holds.
+
+    Apply function `f` to each element of `v` and return a vector containing
+    only those elements for which `f` returned true.
+    "]
+    #[inline]
+    fn filter(f: fn(T) -> bool) -> [T] { filter(self, f) }
+    #[doc = "
     Search for the first element that matches a given predicate
 
     Apply function `f` to each element of `v`, starting from the first.
@@ -1099,19 +1091,16 @@ impl extensions<T: copy> for [const T] {
 #[doc = "Extension methods for vectors"]
 impl extensions<T> for [T] {
     #[doc = "
-    Return true if a predicate matches all elements
-
-    If the vector contains no elements then true is returned.
+    Apply a function to each element of a vector and return the results
     "]
     #[inline]
-    fn all(f: fn(T) -> bool) -> bool { all(self, f) }
+    fn map<U>(f: fn(T) -> U) -> [U] { map(self, f) }
     #[doc = "
-    Return true if a predicate matches any elements
-
-    If the vector contains no elements then false is returned.
+    Apply a function to each element of a vector and return a concatenation
+    of each result vector
     "]
     #[inline]
-    fn any(f: fn(T) -> bool) -> bool { any(self, f) }
+    fn flat_map<U>(f: fn(T) -> [U]) -> [U] { flat_map(self, f) }
     #[doc = "
     Apply a function to each element of a vector and return the results
 
@@ -1122,32 +1111,8 @@ impl extensions<T> for [T] {
     fn filter_map<U: copy>(f: fn(T) -> option<U>) -> [U] {
         filter_map(self, f)
     }
-    #[doc = "
-    Apply a function eo each element of a vector and return a concatenation
-    of each result vector
-    "]
-    #[inline]
-    fn flat_map<U>(f: fn(T) -> [U]) -> [U] { flat_map(self, f) }
-    #[doc = "
-    Apply a function to each element of a vector and return the results
-    "]
-    #[inline]
-    fn map<U>(f: fn(T) -> U) -> [U] { map(self, f) }
 }
 
-#[doc = "Extension methods for vectors"]
-impl extensions<T: copy> for [T] {
-    #[doc = "
-    Construct a new vector from the elements of a vector for which some
-    predicate holds.
-
-    Apply function `f` to each element of `v` and return a vector containing
-    only those elements for which `f` returned true.
-    "]
-   #[inline]
-    fn filter(f: fn(T) -> bool) -> [T] { filter(self, f) }
- }
-
 #[doc = "Unsafe operations"]
 mod unsafe {
     // FIXME: This should have crate visibility (#1893 blocks that)