auto merge of #7015 : huonw/rust/each-fn-kill, r=thestinger

Continuation of #6995/#6999.

1 files changed, 98 insertions, 425 deletions

diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index d8424f4a29e..6137b589bdb 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -1066,138 +1066,12 @@ impl<'self, T:Copy> VectorVector<T> for &'self [&'self [T]] {
     }
 }
 
-/**
- * Reduces a vector from left to right.
- *
- * # Arguments
- * * `z` - initial accumulator value
- * * `v` - vector to iterate over
- * * `p` - a closure to operate on vector elements
- *
- * # Examples
- *
- * Sum all values in the vector [1, 2, 3]:
- *
- * ~~~ {.rust}
- * vec::foldl(0, [1, 2, 3], |a, b| a + *b);
- * ~~~
- *
- */
-pub fn foldl<'a, T, U>(z: T, v: &'a [U], p: &fn(t: T, u: &'a U) -> T) -> T {
-    let mut accum = z;
-    let mut i = 0;
-    let l = v.len();
-    while i < l {
-        // Use a while loop so that liveness analysis can handle moving
-        // the accumulator.
-        accum = p(accum, &v[i]);
-        i += 1;
-    }
-    accum
-}
-
-/**
- * Reduces a vector from right to left. Note that the argument order is
- * reversed compared to `foldl` to reflect the order they are provided to
- * the closure.
- *
- * # Arguments
- * * `v` - vector to iterate over
- * * `z` - initial accumulator value
- * * `p` - a closure to do operate on vector elements
- *
- * # Examples
- *
- * Sum all values in the vector [1, 2, 3]:
- *
- * ~~~ {.rust}
- * vec::foldr([1, 2, 3], 0, |a, b| a + *b);
- * ~~~
- *
- */
-pub fn foldr<'a, T, U>(v: &'a [T], mut z: U, p: &fn(t: &'a T, u: U) -> U) -> U {
-    let mut i = v.len();
-    while i > 0 {
-        i -= 1;
-        z = p(&v[i], z);
-    }
-    return z;
-}
-
-/**
- * Return true if a predicate matches any elements
- *
- * If the vector contains no elements then false is returned.
- */
-pub fn any<T>(v: &[T], f: &fn(t: &T) -> bool) -> bool {
-    for each(v) |elem| { if f(elem) { return true; } }
-    false
-}
-
-/**
- * Return true if a predicate matches any elements in both vectors.
- *
- * If the vectors contains no elements then false is returned.
- */
-pub fn any2<T, U>(v0: &[T], v1: &[U],
-                   f: &fn(a: &T, b: &U) -> bool) -> bool {
-    let v0_len = len(v0);
-    let v1_len = len(v1);
-    let mut i = 0u;
-    while i < v0_len && i < v1_len {
-        if f(&v0[i], &v1[i]) { return true; };
-        i += 1u;
-    }
-    false
-}
-
-/**
- * Return true if a predicate matches all elements
- *
- * If the vector contains no elements then true is returned.
- */
-pub fn all<T>(v: &[T], f: &fn(t: &T) -> bool) -> bool {
-    for each(v) |elem| { if !f(elem) { return false; } }
-    true
-}
-
-/**
- * Return true if a predicate matches all elements
- *
- * If the vector contains no elements then true is returned.
- */
-pub fn alli<T>(v: &[T], f: &fn(uint, t: &T) -> bool) -> bool {
-    for eachi(v) |i, elem| { if !f(i, elem) { return false; } }
-    true
-}
-
-/**
- * Return true if a predicate matches all elements in both vectors.
- *
- * If the vectors are not the same size then false is returned.
- */
-pub fn all2<T, U>(v0: &[T], v1: &[U],
-                   f: &fn(t: &T, u: &U) -> bool) -> bool {
-    let v0_len = len(v0);
-    if v0_len != len(v1) { return false; }
-    let mut i = 0u;
-    while i < v0_len { if !f(&v0[i], &v1[i]) { return false; }; i += 1u; }
-    true
-}
-
 /// Return true if a vector contains an element with the given value
 pub fn contains<T:Eq>(v: &[T], x: &T) -> bool {
     for each(v) |elt| { if *x == *elt { return true; } }
     false
 }
 
-/// Returns the number of elements that are equal to a given value
-pub fn count<T:Eq>(v: &[T], x: &T) -> uint {
-    let mut cnt = 0u;
-    for each(v) |elt| { if *x == *elt { cnt += 1u; } }
-    cnt
-}
-
 /**
  * Search for the first element that matches a given predicate
  *
@@ -1599,34 +1473,6 @@ pub fn eachi<'r,T>(v: &'r [T], f: &fn(uint, v: &'r T) -> bool) -> bool {
 }
 
 /**
- * Iterates over a vector's elements in reverse
- *
- * Return true to continue, false to break.
- */
-#[inline(always)]
-pub fn each_reverse<'r,T>(v: &'r [T], blk: &fn(v: &'r T) -> bool) -> bool {
-    eachi_reverse(v, |_i, v| blk(v))
-}
-
-/**
- * Iterates over a vector's elements and indices in reverse
- *
- * Return true to continue, false to break.
- */
-#[inline(always)]
-pub fn eachi_reverse<'r,T>(v: &'r [T],
-                            blk: &fn(i: uint, v: &'r T) -> bool) -> bool {
-    let mut i = v.len();
-    while i > 0 {
-        i -= 1;
-        if !blk(i, &v[i]) {
-            return false;
-        }
-    }
-    return true;
-}
-
-/**
  * Iterate over all permutations of vector `v`.
  *
  * Permutations are produced in lexicographic order with respect to the order
@@ -1964,6 +1810,7 @@ impl<'self,T:Copy> CopyableVector<T> for &'self [T] {
 pub trait ImmutableVector<'self, T> {
     fn slice(&self, start: uint, end: uint) -> &'self [T];
     fn iter(self) -> VecIterator<'self, T>;
+    fn rev_iter(self) -> VecRevIterator<'self, T>;
     fn head(&self) -> &'self T;
     fn head_opt(&self) -> Option<&'self T>;
     fn tail(&self) -> &'self [T];
@@ -1974,13 +1821,9 @@ pub trait ImmutableVector<'self, T> {
     fn last_opt(&self) -> Option<&'self T>;
     fn position(&self, f: &fn(t: &T) -> bool) -> Option<uint>;
     fn rposition(&self, f: &fn(t: &T) -> bool) -> Option<uint>;
-    fn each_reverse(&self, blk: &fn(&T) -> bool) -> bool;
-    fn eachi_reverse(&self, blk: &fn(uint, &T) -> bool) -> bool;
-    fn foldr<'a, U>(&'a self, z: U, p: &fn(t: &'a T, u: U) -> U) -> U;
     fn map<U>(&self, f: &fn(t: &T) -> U) -> ~[U];
     fn mapi<U>(&self, f: &fn(uint, t: &T) -> U) -> ~[U];
     fn map_r<U>(&self, f: &fn(x: &T) -> U) -> ~[U];
-    fn alli(&self, f: &fn(uint, t: &T) -> bool) -> bool;
     fn flat_map<U>(&self, f: &fn(t: &T) -> ~[U]) -> ~[U];
     fn filter_mapped<U:Copy>(&self, f: &fn(t: &T) -> Option<U>) -> ~[U];
     unsafe fn unsafe_ref(&self, index: uint) -> *T;
@@ -2002,6 +1845,15 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
                         lifetime: cast::transmute(p)}
         }
     }
+    #[inline]
+    fn rev_iter(self) -> VecRevIterator<'self, T> {
+        unsafe {
+            let p = vec::raw::to_ptr(self);
+            VecRevIterator{ptr: p.offset(self.len() - 1),
+                           end: p.offset(-1),
+                           lifetime: cast::transmute(p)}
+        }
+    }
 
     /// Returns the first element of a vector, failing if the vector is empty.
     #[inline]
@@ -2059,24 +1911,6 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
         rposition(*self, f)
     }
 
-    /// Iterates over a vector's elements in reverse.
-    #[inline]
-    fn each_reverse(&self, blk: &fn(&T) -> bool) -> bool {
-        each_reverse(*self, blk)
-    }
-
-    /// Iterates over a vector's elements and indices in reverse.
-    #[inline]
-    fn eachi_reverse(&self, blk: &fn(uint, &T) -> bool) -> bool {
-        eachi_reverse(*self, blk)
-    }
-
-    /// Reduce a vector from right to left
-    #[inline]
-    fn foldr<'a, U>(&'a self, z: U, p: &fn(t: &'a T, u: U) -> U) -> U {
-        foldr(*self, z, p)
-    }
-
     /// Apply a function to each element of a vector and return the results
     #[inline]
     fn map<U>(&self, f: &fn(t: &T) -> U) -> ~[U] { map(*self, f) }
@@ -2101,14 +1935,6 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
     }
 
     /**
-     * Returns true if the function returns true for all elements.
-     *
-     *     If the vector is empty, true is returned.
-     */
-    fn alli(&self, f: &fn(uint, t: &T) -> bool) -> bool {
-        alli(*self, f)
-    }
-    /**
      * Apply a function to each element of a vector and return a concatenation
      * of each result vector
      */
@@ -2350,7 +2176,8 @@ impl<T:Eq> OwnedEqVector<T> for ~[T] {
 #[allow(missing_doc)]
 pub trait MutableVector<'self, T> {
     fn mut_slice(self, start: uint, end: uint) -> &'self mut [T];
-    fn mut_iter(self) -> MutVecIterator<'self, T>;
+    fn mut_iter(self) -> VecMutIterator<'self, T>;
+    fn mut_rev_iter(self) -> VecMutRevIterator<'self, T>;
 
     unsafe fn unsafe_mut_ref(&self, index: uint) -> *mut T;
     unsafe fn unsafe_set(&self, index: uint, val: T);
@@ -2363,14 +2190,23 @@ impl<'self,T> MutableVector<'self, T> for &'self mut [T] {
     }
 
     #[inline]
-    fn mut_iter(self) -> MutVecIterator<'self, T> {
+    fn mut_iter(self) -> VecMutIterator<'self, T> {
         unsafe {
             let p = vec::raw::to_mut_ptr(self);
-            MutVecIterator{ptr: p, end: p.offset(self.len()),
+            VecMutIterator{ptr: p, end: p.offset(self.len()),
                            lifetime: cast::transmute(p)}
         }
     }
 
+    fn mut_rev_iter(self) -> VecMutRevIterator<'self, T> {
+        unsafe {
+            let p = vec::raw::to_mut_ptr(self);
+            VecMutRevIterator{ptr: p.offset(self.len() - 1),
+                              end: p.offset(-1),
+                              lifetime: cast::transmute(p)}
+        }
+    }
+
     #[inline(always)]
     unsafe fn unsafe_mut_ref(&self, index: uint) -> *mut T {
         let pair_ptr: &(*mut T, uint) = transmute(self);
@@ -2872,52 +2708,69 @@ impl<A:Clone> Clone for ~[A] {
     }
 }
 
-/// An external iterator for vectors (use with the std::iterator module)
+macro_rules! iterator {
+    /* FIXME: #4375 Cannot attach documentation/attributes to a macro generated struct.
+    (struct $name:ident -> $ptr:ty, $elem:ty) => {
+        pub struct $name<'self, T> {
+            priv ptr: $ptr,
+            priv end: $ptr,
+            priv lifetime: $elem // FIXME: #5922
+        }
+    };*/
+    (impl $name:ident -> $elem:ty, $step:expr) => {
+        // could be implemented with &[T] with .slice(), but this avoids bounds checks
+        impl<'self, T> Iterator<$elem> for $name<'self, T> {
+            #[inline]
+            fn next(&mut self) -> Option<$elem> {
+                unsafe {
+                    if self.ptr == self.end {
+                        None
+                    } else {
+                        let old = self.ptr;
+                        self.ptr = self.ptr.offset($step);
+                        Some(cast::transmute(old))
+                    }
+                }
+            }
+        }
+    }
+}
+
+//iterator!{struct VecIterator -> *T, &'self T}
+/// An iterator for iterating over a vector
 pub struct VecIterator<'self, T> {
     priv ptr: *T,
     priv end: *T,
     priv lifetime: &'self T // FIXME: #5922
 }
+iterator!{impl VecIterator -> &'self T, 1}
 
-// could be implemented with &[T] with .slice(), but this avoids bounds checks
-impl<'self, T> Iterator<&'self T> for VecIterator<'self, T> {
-    #[inline]
-    fn next(&mut self) -> Option<&'self T> {
-        unsafe {
-            if self.ptr == self.end {
-                None
-            } else {
-                let old = self.ptr;
-                self.ptr = self.ptr.offset(1);
-                Some(cast::transmute(old))
-            }
-        }
-    }
+//iterator!{struct VecRevIterator -> *T, &'self T}
+/// An iterator for iterating over a vector in reverse
+pub struct VecRevIterator<'self, T> {
+    priv ptr: *T,
+    priv end: *T,
+    priv lifetime: &'self T // FIXME: #5922
 }
+iterator!{impl VecRevIterator -> &'self T, -1}
 
-/// An external iterator for vectors with the possibility of mutating
-/// elements. (use with the std::iterator module)
-pub struct MutVecIterator<'self, T> {
+//iterator!{struct VecMutIterator -> *mut T, &'self mut T}
+/// An iterator for mutating the elements of a vector
+pub struct VecMutIterator<'self, T> {
     priv ptr: *mut T,
     priv end: *mut T,
     priv lifetime: &'self mut T // FIXME: #5922
 }
+iterator!{impl VecMutIterator -> &'self mut T, 1}
 
-// could be implemented with &[T] with .slice(), but this avoids bounds checks
-impl<'self, T> Iterator<&'self mut T> for MutVecIterator<'self, T> {
-    #[inline]
-    fn next(&mut self) -> Option<&'self mut T> {
-        unsafe {
-            if self.ptr == self.end {
-                None
-            } else {
-                let old = self.ptr;
-                self.ptr = self.ptr.offset(1);
-                Some(cast::transmute(old))
-            }
-        }
-    }
+//iterator!{struct VecMutRevIterator -> *mut T, &'self mut T}
+/// An iterator for mutating the elements of a vector in reverse
+pub struct VecMutRevIterator<'self, T> {
+    priv ptr: *mut T,
+    priv end: *mut T,
+    priv lifetime: &'self mut T // FIXME: #5922
 }
+iterator!{impl VecMutRevIterator -> &'self mut T, -1}
 
 impl<T> FromIter<T> for ~[T]{
     #[inline(always)]
@@ -3468,39 +3321,6 @@ mod tests {
     }
 
     #[test]
-    fn test_foldl() {
-        // Test on-stack fold.
-        let mut v = ~[1u, 2u, 3u];
-        let mut sum = foldl(0u, v, add);
-        assert_eq!(sum, 6u);
-
-        // Test on-heap fold.
-        v = ~[1u, 2u, 3u, 4u, 5u];
-        sum = foldl(0u, v, add);
-        assert_eq!(sum, 15u);
-    }
-
-    #[test]
-    fn test_foldl2() {
-        fn sub(a: int, b: &int) -> int {
-            a - *b
-        }
-        let v = ~[1, 2, 3, 4];
-        let sum = foldl(0, v, sub);
-        assert_eq!(sum, -10);
-    }
-
-    #[test]
-    fn test_foldr() {
-        fn sub(a: &int, b: int) -> int {
-            *a - b
-        }
-        let v = ~[1, 2, 3, 4];
-        let sum = foldr(v, 0, sub);
-        assert_eq!(sum, -2);
-    }
-
-    #[test]
     fn test_each_empty() {
         for each::<int>([]) |_v| {
             fail!(); // should never be executed
@@ -3528,51 +3348,14 @@ mod tests {
     }
 
     #[test]
-    fn test_each_reverse_empty() {
-        let v: ~[int] = ~[];
-        for v.each_reverse |_v| {
-            fail!(); // should never execute
-        }
-    }
-
-    #[test]
-    fn test_each_reverse_nonempty() {
-        let mut i = 0;
-        for each_reverse([1, 2, 3]) |v| {
-            if i == 0 { assert!(*v == 3); }
-            i += *v
-        }
-        assert_eq!(i, 6);
-    }
-
-    #[test]
-    fn test_eachi_reverse() {
-        let mut i = 0;
-        for eachi_reverse([0, 1, 2]) |j, v| {
-            if i == 0 { assert!(*v == 2); }
-            assert_eq!(j, *v as uint);
-            i += *v;
-        }
-        assert_eq!(i, 3);
-    }
-
-    #[test]
-    fn test_eachi_reverse_empty() {
-        let v: ~[int] = ~[];
-        for v.eachi_reverse |_i, _v| {
-            fail!(); // should never execute
-        }
-    }
-
-    #[test]
     fn test_each_ret_len0() {
-        let mut a0 : [int, .. 0] = [];
+        let a0 : [int, .. 0] = [];
         assert_eq!(each(a0, |_p| fail!()), true);
     }
 
     #[test]
     fn test_each_ret_len1() {
-        let mut a1 = [17];
+        let a1 = [17];
         assert_eq!(each(a1, |_p| true), true);
         assert_eq!(each(a1, |_p| false), false);
     }
@@ -3601,33 +3384,6 @@ mod tests {
     }
 
     #[test]
-    fn test_any_and_all() {
-        assert!(any([1u, 2u, 3u], is_three));
-        assert!(!any([0u, 1u, 2u], is_three));
-        assert!(any([1u, 2u, 3u, 4u, 5u], is_three));
-        assert!(!any([1u, 2u, 4u, 5u, 6u], is_three));
-
-        assert!(all([3u, 3u, 3u], is_three));
-        assert!(!all([3u, 3u, 2u], is_three));
-        assert!(all([3u, 3u, 3u, 3u, 3u], is_three));
-        assert!(!all([3u, 3u, 0u, 1u, 2u], is_three));
-    }
-
-    #[test]
-    fn test_any2_and_all2() {
-
-        assert!(any2([2u, 4u, 6u], [2u, 4u, 6u], is_equal));
-        assert!(any2([1u, 2u, 3u], [4u, 5u, 3u], is_equal));
-        assert!(!any2([1u, 2u, 3u], [4u, 5u, 6u], is_equal));
-        assert!(any2([2u, 4u, 6u], [2u, 4u], is_equal));
-
-        assert!(all2([2u, 4u, 6u], [2u, 4u, 6u], is_equal));
-        assert!(!all2([1u, 2u, 3u], [4u, 5u, 3u], is_equal));
-        assert!(!all2([1u, 2u, 3u], [4u, 5u, 6u], is_equal));
-        assert!(!all2([2u, 4u, 6u], [2u, 4u], is_equal));
-    }
-
-    #[test]
     fn test_zip_unzip() {
         let v1 = ~[1, 2, 3];
         let v2 = ~[4, 5, 6];
@@ -4375,113 +4131,6 @@ mod tests {
     #[ignore(windows)]
     #[should_fail]
     #[allow(non_implicitly_copyable_typarams)]
-    fn test_foldl_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do foldl((~0, @0), v) |_a, _b| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            (~0, @0)
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
-    fn test_foldr_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do foldr(v, (~0, @0)) |_a, _b| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            (~0, @0)
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_any_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do any(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            false
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_any2_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do any(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            false
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_all_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do all(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            true
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_alli_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do alli(v) |_i, _elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            true
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_all2_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do all2(v, v) |_elt1, _elt2| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            true
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
     fn test_find_fail() {
         let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
         let mut i = 0;
@@ -4643,6 +4292,30 @@ mod tests {
     }
 
     #[test]
+    fn test_rev_iterator() {
+        use iterator::*;
+
+        let xs = [1, 2, 5, 10, 11];
+        let ys = [11, 10, 5, 2, 1];
+        let mut i = 0;
+        for xs.rev_iter().advance |&x| {
+            assert_eq!(x, ys[i]);
+            i += 1;
+        }
+        assert_eq!(i, 5);
+    }
+
+    #[test]
+    fn test_mut_rev_iterator() {
+        use iterator::*;
+        let mut xs = [1u, 2, 3, 4, 5];
+        for xs.mut_rev_iter().enumerate().advance |(i,x)| {
+            *x += i;
+        }
+        assert_eq!(xs, [5, 5, 5, 5, 5])
+    }
+
+    #[test]
     fn test_reverse_part() {
         let mut values = [1,2,3,4,5];
         reverse_part(values,1,4);