Merge remote-tracking branch 'mozilla/master'

Conflicts:
	src/libextra/test.rs
	src/libstd/rt/global_heap.rs
	src/libstd/unstable/lang.rs
	src/libstd/vec.rs

1 files changed, 652 insertions, 906 deletions

diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index 1180ac883e7..2c1e913511e 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -16,14 +16,12 @@ use cast::transmute;
 use cast;
 use container::{Container, Mutable};
 use cmp;
-use cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Less, Equal, Greater};
+use cmp::{Eq, TotalEq, TotalOrd, Ordering, Less, Equal, Greater};
 use clone::Clone;
 use iterator::{FromIterator, Iterator, IteratorUtil};
-use iter::FromIter;
 use kinds::Copy;
 use libc::c_void;
 use num::Zero;
-use ops::Add;
 use option::{None, Option, Some};
 use ptr::to_unsafe_ptr;
 use ptr;
@@ -34,9 +32,9 @@ use sys::size_of;
 use uint;
 use unstable::intrinsics;
 #[cfg(stage0)]
-use intrinsic::{get_tydesc};
+use intrinsic::{get_tydesc, TyDesc};
 #[cfg(not(stage0))]
-use unstable::intrinsics::{get_tydesc, contains_managed};
+use unstable::intrinsics::{get_tydesc, contains_managed, TyDesc};
 use vec;
 use util;
 
@@ -56,7 +54,7 @@ pub fn same_length<T, U>(xs: &[T], ys: &[U]) -> bool {
 pub fn from_fn<T>(n_elts: uint, op: &fn(uint) -> T) -> ~[T] {
     unsafe {
         let mut v = with_capacity(n_elts);
-        do as_mut_buf(v) |p, _len| {
+        do v.as_mut_buf |p, _len| {
             let mut i: uint = 0u;
             while i < n_elts {
                 intrinsics::move_val_init(&mut(*ptr::mut_offset(p, i)), op(i));
@@ -81,7 +79,7 @@ pub fn from_elem<T:Copy>(n_elts: uint, t: T) -> ~[T] {
     // vec::with_capacity/ptr::set_memory for primitive types.
     unsafe {
         let mut v = with_capacity(n_elts);
-        do as_mut_buf(v) |p, _len| {
+        do v.as_mut_buf |p, _len| {
             let mut i = 0u;
             while i < n_elts {
                 intrinsics::move_val_init(&mut(*ptr::mut_offset(p, i)), copy t);
@@ -158,165 +156,69 @@ pub fn build_sized_opt<A>(size: Option<uint>,
     build_sized(size.get_or_default(4), builder)
 }
 
-// Accessors
-
-/// Copies
+/// An iterator over the slices of a vector separated by elements that
+/// match a predicate function.
+pub struct VecSplitIterator<'self, T> {
+    priv v: &'self [T],
+    priv n: uint,
+    priv pred: &'self fn(t: &T) -> bool,
+    priv finished: bool
+}
 
-/// Split the vector `v` by applying each element against the predicate `f`.
-pub fn split<T:Copy>(v: &[T], f: &fn(t: &T) -> bool) -> ~[~[T]] {
-    let ln = v.len();
-    if (ln == 0u) { return ~[] }
+impl<'self, T> Iterator<&'self [T]> for VecSplitIterator<'self, T> {
+    fn next(&mut self) -> Option<&'self [T]> {
+        if self.finished { return None; }
 
-    let mut start = 0u;
-    let mut result = ~[];
-    while start < ln {
-        match v.slice(start, ln).iter().position_(|t| f(t)) {
-            None => break,
-            Some(i) => {
-                result.push(v.slice(start, start + i).to_owned());
-                start += i + 1u;
-            }
+        if self.n == 0 {
+            self.finished = true;
+            return Some(self.v);
         }
-    }
-    result.push(v.slice(start, ln).to_owned());
-    result
-}
-
-/**
- * Split the vector `v` by applying each element against the predicate `f` up
- * to `n` times.
- */
-pub fn splitn<T:Copy>(v: &[T], n: uint, f: &fn(t: &T) -> bool) -> ~[~[T]] {
-    let ln = v.len();
-    if (ln == 0u) { return ~[] }
 
-    let mut start = 0u;
-    let mut count = n;
-    let mut result = ~[];
-    while start < ln && count > 0u {
-        match v.slice(start, ln).iter().position_(|t| f(t)) {
-            None => break,
-            Some(i) => {
-                result.push(v.slice(start, start + i).to_owned());
-                // Make sure to skip the separator.
-                start += i + 1u;
-                count -= 1u;
+        match self.v.iter().position(|x| (self.pred)(x)) {
+            None => {
+                self.finished = true;
+                Some(self.v)
+            }
+            Some(idx) => {
+                let ret = Some(self.v.slice(0, idx));
+                self.v = self.v.slice(idx + 1, self.v.len());
+                self.n -= 1;
+                ret
             }
         }
     }
-    result.push(v.slice(start, ln).to_owned());
-    result
 }
 
-/**
- * Reverse split the vector `v` by applying each element against the predicate
- * `f`.
- */
-pub fn rsplit<T:Copy>(v: &[T], f: &fn(t: &T) -> bool) -> ~[~[T]] {
-    let ln = v.len();
-    if (ln == 0) { return ~[] }
-
-    let mut end = ln;
-    let mut result = ~[];
-    while end > 0 {
-        match v.slice(0, end).rposition(|t| f(t)) {
-            None => break,
-            Some(i) => {
-                result.push(v.slice(i + 1, end).to_owned());
-                end = i;
-            }
-        }
-    }
-    result.push(v.slice(0u, end).to_owned());
-    result.reverse();
-    result
+/// An iterator over the slices of a vector separated by elements that
+/// match a predicate function, from back to front.
+pub struct VecRSplitIterator<'self, T> {
+    priv v: &'self [T],
+    priv n: uint,
+    priv pred: &'self fn(t: &T) -> bool,
+    priv finished: bool
 }
 
-/**
- * Reverse split the vector `v` by applying each element against the predicate
- * `f` up to `n times.
- */
-pub fn rsplitn<T:Copy>(v: &[T], n: uint, f: &fn(t: &T) -> bool) -> ~[~[T]] {
-    let ln = v.len();
-    if (ln == 0u) { return ~[] }
+impl<'self, T> Iterator<&'self [T]> for VecRSplitIterator<'self, T> {
+    fn next(&mut self) -> Option<&'self [T]> {
+        if self.finished { return None; }
 
-    let mut end = ln;
-    let mut count = n;
-    let mut result = ~[];
-    while end > 0u && count > 0u {
-        match v.slice(0, end).rposition(|t| f(t)) {
-            None => break,
-            Some(i) => {
-                result.push(v.slice(i + 1u, end).to_owned());
-                // Make sure to skip the separator.
-                end = i;
-                count -= 1u;
-            }
+        if self.n == 0 {
+            self.finished = true;
+            return Some(self.v);
         }
-    }
-    result.push(v.slice(0u, end).to_owned());
-    result.reverse();
-    result
-}
 
-/// Consumes all elements, in a vector, moving them out into the / closure
-/// provided. The vector is traversed from the start to the end.
-///
-/// This method does not impose any requirements on the type of the vector being
-/// consumed, but it prevents any usage of the vector after this function is
-/// called.
-///
-/// # Examples
-///
-/// ~~~ {.rust}
-/// let v = ~[~"a", ~"b"];
-/// do vec::consume(v) |i, s| {
-///   // s has type ~str, not &~str
-///   io::println(s + fmt!(" %d", i));
-/// }
-/// ~~~
-pub fn consume<T>(mut v: ~[T], f: &fn(uint, v: T)) {
-    unsafe {
-        do as_mut_buf(v) |p, ln| {
-            for uint::range(0, ln) |i| {
-                // NB: This unsafe operation counts on init writing 0s to the
-                // holes we create in the vector. That ensures that, if the
-                // iterator fails then we won't try to clean up the consumed
-                // elements during unwinding
-                let x = intrinsics::init();
-                let p = ptr::mut_offset(p, i);
-                f(i, ptr::replace_ptr(p, x));
+        match self.v.rposition(|x| (self.pred)(x)) {
+            None => {
+                self.finished = true;
+                Some(self.v)
             }
-        }
-
-        raw::set_len(&mut v, 0);
-    }
-}
-
-/// Consumes all elements, in a vector, moving them out into the / closure
-/// provided. The vectors is traversed in reverse order (from end to start).
-///
-/// This method does not impose any requirements on the type of the vector being
-/// consumed, but it prevents any usage of the vector after this function is
-/// called.
-pub fn consume_reverse<T>(mut v: ~[T], f: &fn(uint, v: T)) {
-    unsafe {
-        do as_mut_buf(v) |p, ln| {
-            let mut i = ln;
-            while i > 0 {
-                i -= 1;
-
-                // NB: This unsafe operation counts on init writing 0s to the
-                // holes we create in the vector. That ensures that, if the
-                // iterator fails then we won't try to clean up the consumed
-                // elements during unwinding
-                let x = intrinsics::init();
-                let p = ptr::mut_offset(p, i);
-                f(i, ptr::replace_ptr(p, x));
+            Some(idx) => {
+                let ret = Some(self.v.slice(idx + 1, self.v.len()));
+                self.v = self.v.slice(0, idx);
+                self.n -= 1;
+                ret
             }
         }
-
-        raw::set_len(&mut v, 0);
     }
 }
 
@@ -342,20 +244,6 @@ pub fn append_one<T>(lhs: ~[T], x: T) -> ~[T] {
 
 // Functional utilities
 
-/// Consumes a vector, mapping it into a different vector. This function takes
-/// ownership of the supplied vector `v`, moving each element into the closure
-/// provided to generate a new element. The vector of new elements is then
-/// returned.
-///
-/// The original vector `v` cannot be used after this function call (it is moved
-/// inside), but there are no restrictions on the type of the vector.
-pub fn map_consume<T, U>(v: ~[T], f: &fn(v: T) -> U) -> ~[U] {
-    let mut result = ~[];
-    do consume(v) |_i, x| {
-        result.push(f(x));
-    }
-    result
-}
 /**
  * Apply a function to each element of a vector and return a concatenation
  * of each result vector
@@ -366,79 +254,6 @@ pub fn flat_map<T, U>(v: &[T], f: &fn(t: &T) -> ~[U]) -> ~[U] {
     result
 }
 
-pub fn filter_map<T, U>(
-    v: ~[T],
-    f: &fn(t: T) -> Option<U>) -> ~[U]
-{
-    /*!
-     *
-     * Apply a function to each element of a vector and return the results.
-     * Consumes the input vector.  If function `f` returns `None` then that
-     * element is excluded from the resulting vector.
-     */
-
-    let mut result = ~[];
-    do consume(v) |_, elem| {
-        match f(elem) {
-            None => {}
-            Some(result_elem) => { result.push(result_elem); }
-        }
-    }
-    result
-}
-
-pub fn filter_mapped<T, U: Copy>(
-    v: &[T],
-    f: &fn(t: &T) -> Option<U>) -> ~[U]
-{
-    /*!
-     *
-     * Like `filter_map()`, but operates on a borrowed slice
-     * and does not consume the input.
-     */
-
-    let mut result = ~[];
-    for v.iter().advance |elem| {
-        match f(elem) {
-          None => {/* no-op */ }
-          Some(result_elem) => { result.push(result_elem); }
-        }
-    }
-    result
-}
-
-/**
- * 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.
- */
-pub fn filter<T>(v: ~[T], f: &fn(t: &T) -> bool) -> ~[T] {
-    let mut result = ~[];
-    // FIXME (#4355 maybe): using v.consume here crashes
-    // do v.consume |_, elem| {
-    do consume(v) |_, elem| {
-        if f(&elem) { result.push(elem); }
-    }
-    result
-}
-
-/**
- * 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.
- */
-pub fn filtered<T:Copy>(v: &[T], f: &fn(t: &T) -> bool) -> ~[T] {
-    let mut result = ~[];
-    for v.iter().advance |elem| {
-        if f(elem) { result.push(copy *elem); }
-    }
-    result
-}
-
 /// Flattens a vector of vectors of T into a single vector of T.
 pub fn concat<T:Copy>(v: &[~[T]]) -> ~[T] { v.concat_vec() }
 
@@ -524,7 +339,7 @@ pub fn unzip_slice<T:Copy,U:Copy>(v: &[(T, U)]) -> (~[T], ~[U]) {
 pub fn unzip<T,U>(v: ~[(T, U)]) -> (~[T], ~[U]) {
     let mut ts = ~[];
     let mut us = ~[];
-    do consume(v) |_i, p| {
+    for v.consume_iter().advance |p| {
         let (t, u) = p;
         ts.push(t);
         us.push(u);
@@ -566,16 +381,6 @@ pub fn zip<T, U>(mut v: ~[T], mut u: ~[U]) -> ~[(T, U)] {
     w
 }
 
-/// Returns a vector with the order of elements reversed
-pub fn reversed<T:Copy>(v: &[T]) -> ~[T] {
-    let mut rs: ~[T] = ~[];
-    let mut i = v.len();
-    if i == 0 { return (rs); } else { i -= 1; }
-    while i != 0 { rs.push(copy v[i]); i -= 1; }
-    rs.push(copy v[0]);
-    rs
-}
-
 /**
  * Iterate over all permutations of vector `v`.
  *
@@ -630,251 +435,222 @@ pub fn each_permutation<T:Copy>(values: &[T], fun: &fn(perm : &[T]) -> bool) ->
     }
 }
 
-/**
- * Iterate over all contiguous windows of length `n` of the vector `v`.
- *
- * # Example
- *
- * Print the adjacent pairs of a vector (i.e. `[1,2]`, `[2,3]`, `[3,4]`)
- *
- * ~~~ {.rust}
- * for windowed(2, &[1,2,3,4]) |v| {
- *     io::println(fmt!("%?", v));
- * }
- * ~~~
- *
- */
-pub fn windowed<'r, T>(n: uint, v: &'r [T], it: &fn(&'r [T]) -> bool) -> bool {
-    assert!(1u <= n);
-    if n > v.len() { return true; }
-    for uint::range(0, v.len() - n + 1) |i| {
-        if !it(v.slice(i, i + n)) { return false; }
-    }
-    return true;
+/// An iterator over the (overlapping) slices of length `size` within
+/// a vector.
+pub struct VecWindowIter<'self, T> {
+    priv v: &'self [T],
+    priv size: uint
 }
 
-/**
- * Work with the buffer of a vector.
- *
- * Allows for unsafe manipulation of vector contents, which is useful for
- * foreign interop.
- */
-#[inline]
-pub fn as_imm_buf<T,U>(s: &[T],
-                       /* NB---this CANNOT be const, see below */
-                       f: &fn(*T, uint) -> U) -> U {
-
-    // NB---Do not change the type of s to `&const [T]`.  This is
-    // unsound.  The reason is that we are going to create immutable pointers
-    // into `s` and pass them to `f()`, but in fact they are potentially
-    // pointing at *mutable memory*.  Use `as_const_buf` or `as_mut_buf`
-    // instead!
-
-    unsafe {
-        let v : *(*T,uint) = transmute(&s);
-        let (buf,len) = *v;
-        f(buf, len / sys::nonzero_size_of::<T>())
+impl<'self, T> Iterator<&'self [T]> for VecWindowIter<'self, T> {
+    fn next(&mut self) -> Option<&'self [T]> {
+        if self.size > self.v.len() {
+            None
+        } else {
+            let ret = Some(self.v.slice(0, self.size));
+            self.v = self.v.slice(1, self.v.len());
+            ret
+        }
     }
 }
 
-/// Similar to `as_imm_buf` but passing a `*mut T`
-#[inline]
-pub fn as_mut_buf<T,U>(s: &mut [T], f: &fn(*mut T, uint) -> U) -> U {
-    unsafe {
-        let v : *(*mut T,uint) = transmute(&s);
-        let (buf,len) = *v;
-        f(buf, len / sys::nonzero_size_of::<T>())
+/// An iterator over a vector in (non-overlapping) chunks (`size`
+/// elements at a time).
+pub struct VecChunkIter<'self, T> {
+    priv v: &'self [T],
+    priv size: uint
+}
+
+impl<'self, T> Iterator<&'self [T]> for VecChunkIter<'self, T> {
+    fn next(&mut self) -> Option<&'self [T]> {
+        if self.size == 0 {
+            None
+        } else if self.size >= self.v.len() {
+            // finished
+            self.size = 0;
+            Some(self.v)
+        } else {
+            let ret = Some(self.v.slice(0, self.size));
+            self.v = self.v.slice(self.size, self.v.len());
+            ret
+        }
     }
 }
 
 // Equality
 
-/// Tests whether two slices are equal to one another. This is only true if both
-/// slices are of the same length, and each of the corresponding elements return
-/// true when queried via the `eq` function.
-fn eq<T: Eq>(a: &[T], b: &[T]) -> bool {
-    let (a_len, b_len) = (a.len(), b.len());
-    if a_len != b_len { return false; }
+#[cfg(not(test))]
+pub mod traits {
+    use super::Vector;
+    use kinds::Copy;
+    use cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Equal, Equiv};
+    use ops::Add;
 
-    let mut i = 0;
-    while i < a_len {
-        if a[i] != b[i] { return false; }
-        i += 1;
+    impl<'self,T:Eq> Eq for &'self [T] {
+        fn eq(&self, other: & &'self [T]) -> bool {
+            self.len() == other.len() &&
+                self.iter().zip(other.iter()).all(|(s,o)| *s == *o)
+        }
+        #[inline]
+        fn ne(&self, other: & &'self [T]) -> bool { !self.eq(other) }
     }
-    true
-}
 
-/// Similar to the `vec::eq` function, but this is defined for types which
-/// implement `TotalEq` as opposed to types which implement `Eq`. Equality
-/// comparisons are done via the `equals` function instead of `eq`.
-fn equals<T: TotalEq>(a: &[T], b: &[T]) -> bool {
-    let (a_len, b_len) = (a.len(), b.len());
-    if a_len != b_len { return false; }
-
-    let mut i = 0;
-    while i < a_len {
-        if !a[i].equals(&b[i]) { return false; }
-        i += 1;
+    impl<T:Eq> Eq for ~[T] {
+        #[inline]
+        fn eq(&self, other: &~[T]) -> bool { self.as_slice() == *other }
+        #[inline]
+        fn ne(&self, other: &~[T]) -> bool { !self.eq(other) }
     }
-    true
-}
-
-#[cfg(not(test))]
-impl<'self,T:Eq> Eq for &'self [T] {
-    #[inline]
-    fn eq(&self, other: & &'self [T]) -> bool { eq(*self, *other) }
-    #[inline]
-    fn ne(&self, other: & &'self [T]) -> bool { !self.eq(other) }
-}
 
-#[cfg(not(test))]
-impl<T:Eq> Eq for ~[T] {
-    #[inline]
-    fn eq(&self, other: &~[T]) -> bool { eq(*self, *other) }
-    #[inline]
-    fn ne(&self, other: &~[T]) -> bool { !self.eq(other) }
-}
-
-#[cfg(not(test))]
-impl<T:Eq> Eq for @[T] {
-    #[inline]
-    fn eq(&self, other: &@[T]) -> bool { eq(*self, *other) }
-    #[inline]
-    fn ne(&self, other: &@[T]) -> bool { !self.eq(other) }
-}
+    impl<T:Eq> Eq for @[T] {
+        #[inline]
+        fn eq(&self, other: &@[T]) -> bool { self.as_slice() == *other }
+        #[inline]
+        fn ne(&self, other: &@[T]) -> bool { !self.eq(other) }
+    }
 
-#[cfg(not(test))]
-impl<'self,T:TotalEq> TotalEq for &'self [T] {
-    #[inline]
-    fn equals(&self, other: & &'self [T]) -> bool { equals(*self, *other) }
-}
+    impl<'self,T:TotalEq> TotalEq for &'self [T] {
+        fn equals(&self, other: & &'self [T]) -> bool {
+            self.len() == other.len() &&
+                self.iter().zip(other.iter()).all(|(s,o)| s.equals(o))
+        }
+    }
 
-#[cfg(not(test))]
-impl<T:TotalEq> TotalEq for ~[T] {
-    #[inline]
-    fn equals(&self, other: &~[T]) -> bool { equals(*self, *other) }
-}
+    impl<T:TotalEq> TotalEq for ~[T] {
+        #[inline]
+        fn equals(&self, other: &~[T]) -> bool { self.as_slice().equals(&other.as_slice()) }
+    }
 
-#[cfg(not(test))]
-impl<T:TotalEq> TotalEq for @[T] {
-    #[inline]
-    fn equals(&self, other: &@[T]) -> bool { equals(*self, *other) }
-}
+    impl<T:TotalEq> TotalEq for @[T] {
+        #[inline]
+        fn equals(&self, other: &@[T]) -> bool { self.as_slice().equals(&other.as_slice()) }
+    }
 
-#[cfg(not(test))]
-impl<'self,T:Eq> Equiv<~[T]> for &'self [T] {
-    #[inline]
-    fn equiv(&self, other: &~[T]) -> bool { eq(*self, *other) }
-}
+    impl<'self,T:Eq, V: Vector<T>> Equiv<V> for &'self [T] {
+        #[inline]
+        fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
+    }
 
-// Lexicographical comparison
+    impl<'self,T:Eq, V: Vector<T>> Equiv<V> for ~[T] {
+        #[inline]
+        fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
+    }
 
-fn cmp<T: TotalOrd>(a: &[T], b: &[T]) -> Ordering {
-    let low = uint::min(a.len(), b.len());
+    impl<'self,T:Eq, V: Vector<T>> Equiv<V> for @[T] {
+        #[inline]
+        fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
+    }
 
-    for uint::range(0, low) |idx| {
-        match a[idx].cmp(&b[idx]) {
-          Greater => return Greater,
-          Less => return Less,
-          Equal => ()
+    impl<'self,T:TotalOrd> TotalOrd for &'self [T] {
+        fn cmp(&self, other: & &'self [T]) -> Ordering {
+            for self.iter().zip(other.iter()).advance |(s,o)| {
+                match s.cmp(o) {
+                    Equal => {},
+                    non_eq => { return non_eq; }
+                }
+            }
+            self.len().cmp(&other.len())
         }
     }
 
-    a.len().cmp(&b.len())
-}
-
-#[cfg(not(test))]
-impl<'self,T:TotalOrd> TotalOrd for &'self [T] {
-    #[inline]
-    fn cmp(&self, other: & &'self [T]) -> Ordering { cmp(*self, *other) }
-}
+    impl<T: TotalOrd> TotalOrd for ~[T] {
+        #[inline]
+        fn cmp(&self, other: &~[T]) -> Ordering { self.as_slice().cmp(&other.as_slice()) }
+    }
 
-#[cfg(not(test))]
-impl<T: TotalOrd> TotalOrd for ~[T] {
-    #[inline]
-    fn cmp(&self, other: &~[T]) -> Ordering { cmp(*self, *other) }
-}
+    impl<T: TotalOrd> TotalOrd for @[T] {
+        #[inline]
+        fn cmp(&self, other: &@[T]) -> Ordering { self.as_slice().cmp(&other.as_slice()) }
+    }
 
-#[cfg(not(test))]
-impl<T: TotalOrd> TotalOrd for @[T] {
-    #[inline]
-    fn cmp(&self, other: &@[T]) -> Ordering { cmp(*self, *other) }
-}
+    impl<'self,T:Ord> Ord for &'self [T] {
+        fn lt(&self, other: & &'self [T]) -> bool {
+            for self.iter().zip(other.iter()).advance |(s,o)| {
+                if *s < *o { return true; }
+                if *s > *o { return false; }
+            }
+            self.len() < other.len()
+        }
+        #[inline]
+        fn le(&self, other: & &'self [T]) -> bool { !(*other < *self) }
+        #[inline]
+        fn ge(&self, other: & &'self [T]) -> bool { !(*self < *other) }
+        #[inline]
+        fn gt(&self, other: & &'self [T]) -> bool { *other < *self }
+    }
 
-fn lt<T:Ord>(a: &[T], b: &[T]) -> bool {
-    let (a_len, b_len) = (a.len(), b.len());
-    let end = uint::min(a_len, b_len);
+    impl<T:Ord> Ord for ~[T] {
+        #[inline]
+        fn lt(&self, other: &~[T]) -> bool { self.as_slice() < other.as_slice() }
+        #[inline]
+        fn le(&self, other: &~[T]) -> bool { self.as_slice() <= other.as_slice() }
+        #[inline]
+        fn ge(&self, other: &~[T]) -> bool { self.as_slice() >= other.as_slice() }
+        #[inline]
+        fn gt(&self, other: &~[T]) -> bool { self.as_slice() > other.as_slice() }
+    }
 
-    let mut i = 0;
-    while i < end {
-        let (c_a, c_b) = (&a[i], &b[i]);
-        if *c_a < *c_b { return true; }
-        if *c_a > *c_b { return false; }
-        i += 1;
+    impl<T:Ord> Ord for @[T] {
+        #[inline]
+        fn lt(&self, other: &@[T]) -> bool { self.as_slice() < other.as_slice() }
+        #[inline]
+        fn le(&self, other: &@[T]) -> bool { self.as_slice() <= other.as_slice() }
+        #[inline]
+        fn ge(&self, other: &@[T]) -> bool { self.as_slice() >= other.as_slice() }
+        #[inline]
+        fn gt(&self, other: &@[T]) -> bool { self.as_slice() > other.as_slice() }
     }
 
-    a_len < b_len
+    impl<'self,T:Copy, V: Vector<T>> Add<V, ~[T]> for &'self [T] {
+        #[inline]
+        fn add(&self, rhs: &V) -> ~[T] {
+            let mut res = self.to_owned();
+            res.push_all(rhs.as_slice());
+            res
+        }
+    }
+    impl<T:Copy, V: Vector<T>> Add<V, ~[T]> for ~[T] {
+        #[inline]
+        fn add(&self, rhs: &V) -> ~[T] {
+            let mut res = self.to_owned();
+            res.push_all(rhs.as_slice());
+            res
+        }
+    }
 }
 
-fn le<T:Ord>(a: &[T], b: &[T]) -> bool { !lt(b, a) }
-fn ge<T:Ord>(a: &[T], b: &[T]) -> bool { !lt(a, b) }
-fn gt<T:Ord>(a: &[T], b: &[T]) -> bool { lt(b, a)  }
+#[cfg(test)]
+pub mod traits {}
 
-#[cfg(not(test))]
-impl<'self,T:Ord> Ord for &'self [T] {
-    #[inline]
-    fn lt(&self, other: & &'self [T]) -> bool { lt((*self), (*other)) }
-    #[inline]
-    fn le(&self, other: & &'self [T]) -> bool { le((*self), (*other)) }
-    #[inline]
-    fn ge(&self, other: & &'self [T]) -> bool { ge((*self), (*other)) }
-    #[inline]
-    fn gt(&self, other: & &'self [T]) -> bool { gt((*self), (*other)) }
+/// Any vector that can be represented as a slice.
+pub trait Vector<T> {
+    /// Work with `self` as a slice.
+    fn as_slice<'a>(&'a self) -> &'a [T];
 }
-
-#[cfg(not(test))]
-impl<T:Ord> Ord for ~[T] {
-    #[inline]
-    fn lt(&self, other: &~[T]) -> bool { lt((*self), (*other)) }
-    #[inline]
-    fn le(&self, other: &~[T]) -> bool { le((*self), (*other)) }
-    #[inline]
-    fn ge(&self, other: &~[T]) -> bool { ge((*self), (*other)) }
-    #[inline]
-    fn gt(&self, other: &~[T]) -> bool { gt((*self), (*other)) }
+impl<'self,T> Vector<T> for &'self [T] {
+    #[inline(always)]
+    fn as_slice<'a>(&'a self) -> &'a [T] { *self }
 }
-
-#[cfg(not(test))]
-impl<T:Ord> Ord for @[T] {
-    #[inline]
-    fn lt(&self, other: &@[T]) -> bool { lt((*self), (*other)) }
-    #[inline]
-    fn le(&self, other: &@[T]) -> bool { le((*self), (*other)) }
-    #[inline]
-    fn ge(&self, other: &@[T]) -> bool { ge((*self), (*other)) }
-    #[inline]
-    fn gt(&self, other: &@[T]) -> bool { gt((*self), (*other)) }
+impl<T> Vector<T> for ~[T] {
+    #[inline(always)]
+    fn as_slice<'a>(&'a self) -> &'a [T] { let v: &'a [T] = *self; v }
 }
-
-#[cfg(not(test))]
-impl<'self,T:Copy> Add<&'self [T], ~[T]> for ~[T] {
-    #[inline]
-    fn add(&self, rhs: & &'self [T]) -> ~[T] {
-        append(copy *self, (*rhs))
-    }
+impl<T> Vector<T> for @[T] {
+    #[inline(always)]
+    fn as_slice<'a>(&'a self) -> &'a [T] { let v: &'a [T] = *self; v }
 }
 
 impl<'self, T> Container for &'self [T] {
     /// Returns true if a vector contains no elements
     #[inline]
     fn is_empty(&self) -> bool {
-        as_imm_buf(*self, |_p, len| len == 0u)
+        self.as_imm_buf(|_p, len| len == 0u)
     }
 
     /// Returns the length of a vector
     #[inline]
     fn len(&self) -> uint {
-        as_imm_buf(*self, |_p, len| len)
+        self.as_imm_buf(|_p, len| len)
     }
 }
 
@@ -882,13 +658,13 @@ impl<T> Container for ~[T] {
     /// Returns true if a vector contains no elements
     #[inline]
     fn is_empty(&self) -> bool {
-        as_imm_buf(*self, |_p, len| len == 0u)
+        self.as_imm_buf(|_p, len| len == 0u)
     }
 
     /// Returns the length of a vector
     #[inline]
     fn len(&self) -> uint {
-        as_imm_buf(*self, |_p, len| len)
+        self.as_imm_buf(|_p, len| len)
     }
 }
 
@@ -915,6 +691,14 @@ 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 split_iter(self, pred: &'self fn(&T) -> bool) -> VecSplitIterator<'self, T>;
+    fn splitn_iter(self, n: uint, pred: &'self fn(&T) -> bool) -> VecSplitIterator<'self, T>;
+    fn rsplit_iter(self, pred: &'self fn(&T) -> bool) -> VecRSplitIterator<'self, T>;
+    fn rsplitn_iter(self,  n: uint, pred: &'self fn(&T) -> bool) -> VecRSplitIterator<'self, T>;
+
+    fn window_iter(self, size: uint) -> VecWindowIter<'self, T>;
+    fn chunk_iter(self, size: uint) -> VecChunkIter<'self, T>;
+
     fn head(&self) -> &'self T;
     fn head_opt(&self) -> Option<&'self T>;
     fn tail(&self) -> &'self [T];
@@ -925,12 +709,13 @@ pub trait ImmutableVector<'self, T> {
     fn last_opt(&self) -> Option<&'self T>;
     fn rposition(&self, f: &fn(t: &T) -> bool) -> Option<uint>;
     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;
 
     fn bsearch(&self, f: &fn(&T) -> Ordering) -> Option<uint>;
 
     fn map<U>(&self, &fn(t: &T) -> U) -> ~[U];
+
+    fn as_imm_buf<U>(&self, f: &fn(*T, uint) -> U) -> U;
 }
 
 /// Extension methods for vectors
@@ -940,7 +725,7 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
     fn slice(&self, start: uint, end: uint) -> &'self [T] {
     assert!(start <= end);
     assert!(end <= self.len());
-        do as_imm_buf(*self) |p, _len| {
+        do self.as_imm_buf |p, _len| {
             unsafe {
                 transmute((ptr::offset(p, start),
                            (end - start) * sys::nonzero_size_of::<T>()))
@@ -966,6 +751,101 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
         }
     }
 
+    /// Returns an iterator over the subslices of the vector which are
+    /// separated by elements that match `pred`.
+    #[inline]
+    fn split_iter(self, pred: &'self fn(&T) -> bool) -> VecSplitIterator<'self, T> {
+        self.splitn_iter(uint::max_value, pred)
+    }
+    /// Returns an iterator over the subslices of the vector which are
+    /// separated by elements that match `pred`, limited to splitting
+    /// at most `n` times.
+    #[inline]
+    fn splitn_iter(self, n: uint, pred: &'self fn(&T) -> bool) -> VecSplitIterator<'self, T> {
+        VecSplitIterator {
+            v: self,
+            n: n,
+            pred: pred,
+            finished: false
+        }
+    }
+    /// Returns an iterator over the subslices of the vector which are
+    /// separated by elements that match `pred`. This starts at the
+    /// end of the vector and works backwards.
+    #[inline]
+    fn rsplit_iter(self, pred: &'self fn(&T) -> bool) -> VecRSplitIterator<'self, T> {
+        self.rsplitn_iter(uint::max_value, pred)
+    }
+    /// Returns an iterator over the subslices of the vector which are
+    /// separated by elements that match `pred` limited to splitting
+    /// at most `n` times. This starts at the end of the vector and
+    /// works backwards.
+    #[inline]
+    fn rsplitn_iter(self, n: uint, pred: &'self fn(&T) -> bool) -> VecRSplitIterator<'self, T> {
+        VecRSplitIterator {
+            v: self,
+            n: n,
+            pred: pred,
+            finished: false
+        }
+    }
+
+    /**
+     * Returns an iterator over all contiguous windows of length
+     * `size`. The windows overlap. If the vector is shorter than
+     * `size`, the iterator returns no values.
+     *
+     * # Failure
+     *
+     * Fails if `size` is 0.
+     *
+     * # Example
+     *
+     * Print the adjacent pairs of a vector (i.e. `[1,2]`, `[2,3]`,
+     * `[3,4]`):
+     *
+     * ~~~ {.rust}
+     * let v = &[1,2,3,4];
+     * for v.window_iter().advance |win| {
+     *     io::println(fmt!("%?", win));
+     * }
+     * ~~~
+     *
+     */
+    fn window_iter(self, size: uint) -> VecWindowIter<'self, T> {
+        assert!(size != 0);
+        VecWindowIter { v: self, size: size }
+    }
+
+    /**
+     *
+     * Returns an iterator over `size` elements of the vector at a
+     * time. The chunks do not overlap. If `size` does not divide the
+     * length of the vector, then the last chunk will not have length
+     * `size`.
+     *
+     * # Failure
+     *
+     * Fails if `size` is 0.
+     *
+     * # Example
+     *
+     * Print the vector two elements at a time (i.e. `[1,2]`,
+     * `[3,4]`, `[5]`):
+     *
+     * ~~~ {.rust}
+     * let v = &[1,2,3,4,5];
+     * for v.chunk_iter().advance |win| {
+     *     io::println(fmt!("%?", win));
+     * }
+     * ~~~
+     *
+     */
+    fn chunk_iter(self, size: uint) -> VecChunkIter<'self, T> {
+        assert!(size != 0);
+        VecChunkIter { v: self, size: size }
+    }
+
     /// Returns the first element of a vector, failing if the vector is empty.
     #[inline]
     fn head(&self) -> &'self T {
@@ -1035,17 +915,6 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
     fn flat_map<U>(&self, f: &fn(t: &T) -> ~[U]) -> ~[U] {
         flat_map(*self, f)
     }
-    /**
-     * Apply a function to each element of a vector and return the results
-     *
-     * If function `f` returns `none` then that element is excluded from
-     * the resulting vector.
-     */
-    #[inline]
-    fn filter_mapped<U:Copy>(&self, f: &fn(t: &T) -> Option<U>) -> ~[U] {
-        filter_mapped(*self, f)
-    }
-
     /// Returns a pointer to the element at the given index, without doing
     /// bounds checking.
     #[inline]
@@ -1089,6 +958,28 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
     fn map<U>(&self, f: &fn(t: &T) -> U) -> ~[U] {
         self.iter().transform(f).collect()
     }
+
+    /**
+     * Work with the buffer of a vector.
+     *
+     * Allows for unsafe manipulation of vector contents, which is useful for
+     * foreign interop.
+     */
+    #[inline]
+    fn as_imm_buf<U>(&self,
+                     /* NB---this CANNOT be const, see below */
+                     f: &fn(*T, uint) -> U) -> U {
+        // NB---Do not change the type of s to `&const [T]`.  This is
+        // unsound.  The reason is that we are going to create immutable pointers
+        // into `s` and pass them to `f()`, but in fact they are potentially
+        // pointing at *mutable memory*.  Use `as_mut_buf` instead!
+
+        unsafe {
+            let v : *(*T,uint) = transmute(self);
+            let (buf,len) = *v;
+            f(buf, len / sys::nonzero_size_of::<T>())
+        }
+    }
 }
 
 #[allow(missing_doc)]
@@ -1102,7 +993,7 @@ impl<'self,T:Eq> ImmutableEqVector<T> for &'self [T] {
     /// Find the first index containing a matching value
     #[inline]
     fn position_elem(&self, x: &T) -> Option<uint> {
-        self.iter().position_(|y| *x == *y)
+        self.iter().position(|y| *x == *y)
     }
 
     /// Find the last index containing a matching value
@@ -1136,7 +1027,6 @@ impl<'self, T: TotalOrd> ImmutableTotalOrdVector<T> for &'self [T] {
 
 #[allow(missing_doc)]
 pub trait ImmutableCopyableVector<T> {
-    fn filtered(&self, f: &fn(&T) -> bool) -> ~[T];
     fn partitioned(&self, f: &fn(&T) -> bool) -> (~[T], ~[T]);
     unsafe fn unsafe_get(&self, elem: uint) -> T;
 }
@@ -1144,18 +1034,6 @@ pub trait ImmutableCopyableVector<T> {
 /// Extension methods for vectors
 impl<'self,T:Copy> ImmutableCopyableVector<T> for &'self [T] {
     /**
-     * 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 filtered(&self, f: &fn(t: &T) -> bool) -> ~[T] {
-        filtered(*self, f)
-    }
-
-    /**
      * Partitions the vector into those that satisfies the predicate, and
      * those that do not.
      */
@@ -1184,6 +1062,9 @@ impl<'self,T:Copy> ImmutableCopyableVector<T> for &'self [T] {
 
 #[allow(missing_doc)]
 pub trait OwnedVector<T> {
+    fn consume_iter(self) -> VecConsumeIterator<T>;
+    fn consume_rev_iter(self) -> VecConsumeRevIterator<T>;
+
     fn reserve(&mut self, n: uint);
     fn reserve_at_least(&mut self, n: uint);
     fn capacity(&self) -> uint;
@@ -1193,21 +1074,46 @@ pub trait OwnedVector<T> {
 
     fn push_all_move(&mut self, rhs: ~[T]);
     fn pop(&mut self) -> T;
+    fn pop_opt(&mut self) -> Option<T>;
     fn shift(&mut self) -> T;
+    fn shift_opt(&mut self) -> Option<T>;
     fn unshift(&mut self, x: T);
     fn insert(&mut self, i: uint, x:T);
     fn remove(&mut self, i: uint) -> T;
     fn swap_remove(&mut self, index: uint) -> T;
     fn truncate(&mut self, newlen: uint);
     fn retain(&mut self, f: &fn(t: &T) -> bool);
-    fn consume(self, f: &fn(uint, v: T));
-    fn consume_reverse(self, f: &fn(uint, v: T));
-    fn filter(self, f: &fn(t: &T) -> bool) -> ~[T];
     fn partition(self, f: &fn(&T) -> bool) -> (~[T], ~[T]);
     fn grow_fn(&mut self, n: uint, op: &fn(uint) -> T);
 }
 
 impl<T> OwnedVector<T> for ~[T] {
+    /// Creates a consuming iterator, that is, one that moves each
+    /// value out of the vector (from start to end). The vector cannot
+    /// be used after calling this.
+    ///
+    /// Note that this performs O(n) swaps, and so `consume_rev_iter`
+    /// (which just calls `pop` repeatedly) is more efficient.
+    ///
+    /// # Examples
+    ///
+    /// ~~~ {.rust}
+    /// let v = ~[~"a", ~"b"];
+    /// for v.consume_iter().advance |s| {
+    ///   // s has type ~str, not &~str
+    ///   println(s);
+    /// }
+    /// ~~~
+    fn consume_iter(self) -> VecConsumeIterator<T> {
+        VecConsumeIterator { v: self, idx: 0 }
+    }
+    /// Creates a consuming iterator that moves out of the vector in
+    /// reverse order. Also see `consume_iter`, however note that this
+    /// is more efficient.
+    fn consume_rev_iter(self) -> VecConsumeRevIterator<T> {
+        VecConsumeRevIterator { v: self }
+    }
+
     /**
      * Reserves capacity for exactly `n` elements in the given vector.
      *
@@ -1351,7 +1257,7 @@ impl<T> OwnedVector<T> for ~[T] {
         let new_len = self.len() + rhs.len();
         self.reserve(new_len);
         unsafe {
-            do as_mut_buf(rhs) |p, len| {
+            do rhs.as_mut_buf |p, len| {
                 for uint::range(0, len) |i| {
                     let x = ptr::replace_ptr(ptr::mut_offset(p, i),
                                              intrinsics::uninit());
@@ -1362,35 +1268,49 @@ impl<T> OwnedVector<T> for ~[T] {
         }
     }
 
-    /// Remove the last element from a vector and return it
-    fn pop(&mut self) -> T {
-        let ln = self.len();
-        if ln == 0 {
-            fail!("sorry, cannot pop an empty vector")
-        }
-        let valptr = ptr::to_mut_unsafe_ptr(&mut self[ln - 1u]);
-        unsafe {
-            let val = ptr::replace_ptr(valptr, intrinsics::init());
-            raw::set_len(self, ln - 1u);
-            val
+    /// Remove the last element from a vector and return it, or `None` if it is empty
+    fn pop_opt(&mut self) -> Option<T> {
+        match self.len() {
+            0  => None,
+            ln => {
+                let valptr = ptr::to_mut_unsafe_ptr(&mut self[ln - 1u]);
+                unsafe {
+                    let val = ptr::replace_ptr(valptr, intrinsics::init());
+                    raw::set_len(self, ln - 1u);
+                    Some(val)
+                }
+            }
         }
     }
 
+
+    /// Remove the last element from a vector and return it, failing if it is empty
+    #[inline]
+    fn pop(&mut self) -> T {
+        self.pop_opt().expect("pop: empty vector")
+    }
+
     /// Removes the first element from a vector and return it
+    #[inline]
     fn shift(&mut self) -> T {
-        unsafe {
-            assert!(!self.is_empty());
-
-            if self.len() == 1 { return self.pop() }
+        self.shift_opt().expect("shift: empty vector")
+    }
 
-            if self.len() == 2 {
-                let last = self.pop();
-                let first = self.pop();
-                self.push(last);
-                return first;
-            }
+    /// Removes the first element from a vector and return it, or `None` if it is empty
+    fn shift_opt(&mut self) -> Option<T> {
+        unsafe {
+            let ln = match self.len() {
+                0 => return None,
+                1 => return self.pop_opt(),
+                2 =>  {
+                    let last = self.pop();
+                    let first = self.pop_opt();
+                    self.push(last);
+                    return first;
+                }
+                x => x
+            };
 
-            let ln = self.len();
             let next_ln = self.len() - 1;
 
             // Save the last element. We're going to overwrite its position
@@ -1426,7 +1346,7 @@ impl<T> OwnedVector<T> for ~[T] {
             let vp = raw::to_mut_ptr(*self);
             let vp = ptr::mut_offset(vp, next_ln - 1);
 
-            ptr::replace_ptr(vp, work_elt)
+            Some(ptr::replace_ptr(vp, work_elt))
         }
     }
 
@@ -1483,7 +1403,7 @@ impl<T> OwnedVector<T> for ~[T] {
 
     /// Shorten a vector, dropping excess elements.
     fn truncate(&mut self, newlen: uint) {
-        do as_mut_buf(*self) |p, oldlen| {
+        do self.as_mut_buf |p, oldlen| {
             assert!(newlen <= oldlen);
             unsafe {
                 // This loop is optimized out for non-drop types.
@@ -1516,21 +1436,6 @@ impl<T> OwnedVector<T> for ~[T] {
         }
     }
 
-    #[inline]
-    fn consume(self, f: &fn(uint, v: T)) {
-        consume(self, f)
-    }
-
-    #[inline]
-    fn consume_reverse(self, f: &fn(uint, v: T)) {
-        consume_reverse(self, f)
-    }
-
-    #[inline]
-    fn filter(self, f: &fn(&T) -> bool) -> ~[T] {
-        filter(self, f)
-    }
-
     /**
      * Partitions the vector into those that satisfies the predicate, and
      * those that do not.
@@ -1540,7 +1445,7 @@ impl<T> OwnedVector<T> for ~[T] {
         let mut lefts  = ~[];
         let mut rights = ~[];
 
-        do self.consume |_, elt| {
+        for self.consume_iter().advance |elt| {
             if f(&elt) {
                 lefts.push(elt);
             } else {
@@ -1656,7 +1561,7 @@ impl<T:Eq> OwnedEqVector<T> for ~[T] {
             if self.len() == 0 { return; }
             let mut last_written = 0;
             let mut next_to_read = 1;
-            do as_mut_buf(*self) |p, ln| {
+            do self.as_mut_buf |p, ln| {
                 // last_written < next_to_read <= ln
                 while next_to_read < ln {
                     // last_written < next_to_read < ln
@@ -1710,6 +1615,8 @@ pub trait MutableVector<'self, T> {
 
     unsafe fn unsafe_mut_ref(&self, index: uint) -> *mut T;
     unsafe fn unsafe_set(&self, index: uint, val: T);
+
+    fn as_mut_buf<U>(&self, f: &fn(*mut T, uint) -> U) -> U;
 }
 
 impl<'self,T> MutableVector<'self, T> for &'self mut [T] {
@@ -1718,7 +1625,7 @@ impl<'self,T> MutableVector<'self, T> for &'self mut [T] {
     fn mut_slice(self, start: uint, end: uint) -> &'self mut [T] {
         assert!(start <= end);
         assert!(end <= self.len());
-        do as_mut_buf(self) |p, _len| {
+        do self.as_mut_buf |p, _len| {
             unsafe {
                 transmute((ptr::mut_offset(p, start),
                            (end - start) * sys::nonzero_size_of::<T>()))
@@ -1791,6 +1698,17 @@ impl<'self,T> MutableVector<'self, T> for &'self mut [T] {
     unsafe fn unsafe_set(&self, index: uint, val: T) {
         *self.unsafe_mut_ref(index) = val;
     }
+
+    /// Similar to `as_imm_buf` but passing a `*mut T`
+    #[inline]
+    fn as_mut_buf<U>(&self, f: &fn(*mut T, uint) -> U) -> U {
+        unsafe {
+            let v : *(*mut T,uint) = transmute(self);
+            let (buf,len) = *v;
+            f(buf, len / sys::nonzero_size_of::<T>())
+        }
+    }
+
 }
 
 /// Trait for ~[T] where T is Cloneable
@@ -1840,7 +1758,7 @@ pub mod raw {
     use ptr;
     use sys;
     use unstable::intrinsics;
-    use vec::{UnboxedVecRepr, as_imm_buf, as_mut_buf, with_capacity};
+    use vec::{UnboxedVecRepr, with_capacity, ImmutableVector, MutableVector};
     use util;
 
     /// The internal representation of a (boxed) vector
@@ -1928,7 +1846,7 @@ pub mod raw {
      */
     #[inline]
     pub unsafe fn get<T:Copy>(v: &[T], i: uint) -> T {
-        as_imm_buf(v, |p, _len| copy *ptr::offset(p, i))
+        v.as_imm_buf(|p, _len| copy *ptr::offset(p, i))
     }
 
     /**
@@ -1939,7 +1857,7 @@ pub mod raw {
     #[inline]
     pub unsafe fn init_elem<T>(v: &mut [T], i: uint, val: T) {
         let mut box = Some(val);
-        do as_mut_buf(v) |p, _len| {
+        do v.as_mut_buf |p, _len| {
             let box2 = util::replace(&mut box, None);
             intrinsics::move_val_init(&mut(*ptr::mut_offset(p, i)),
                                       box2.unwrap());
@@ -1959,7 +1877,7 @@ pub mod raw {
     pub unsafe fn from_buf_raw<T>(ptr: *T, elts: uint) -> ~[T] {
         let mut dst = with_capacity(elts);
         set_len(&mut dst, elts);
-        as_mut_buf(dst, |p_dst, _len_dst| ptr::copy_memory(p_dst, ptr, elts));
+        dst.as_mut_buf(|p_dst, _len_dst| ptr::copy_memory(p_dst, ptr, elts));
         dst
     }
 
@@ -1975,8 +1893,8 @@ pub mod raw {
         assert!(dst.len() >= count);
         assert!(src.len() >= count);
 
-        do as_mut_buf(dst) |p_dst, _len_dst| {
-            do as_imm_buf(src) |p_src, _len_src| {
+        do dst.as_mut_buf |p_dst, _len_dst| {
+            do src.as_imm_buf |p_src, _len_src| {
                 ptr::copy_memory(p_dst, p_src, count)
             }
         }
@@ -2000,7 +1918,7 @@ pub mod bytes {
     impl<'self> MutableByteVector for &'self mut [u8] {
         #[inline]
         fn set_memory(self, value: u8) {
-            do vec::as_mut_buf(self) |p, len| {
+            do self.as_mut_buf |p, len| {
                 unsafe { ptr::set_memory(p, value, len) };
             }
         }
@@ -2107,16 +2025,21 @@ macro_rules! iterator {
             }
 
             #[inline]
-            fn size_hint(&self) -> (Option<uint>, Option<uint>) {
-                let exact = Some(((self.end as uint) - (self.ptr as uint)) / size_of::<$elem>());
-                (exact, exact)
+            fn size_hint(&self) -> (uint, Option<uint>) {
+                let diff = if $step > 0 {
+                    (self.end as uint) - (self.ptr as uint)
+                } else {
+                    (self.ptr as uint) - (self.end as uint)
+                };
+                let exact = diff / size_of::<$elem>();
+                (exact, Some(exact))
             }
         }
     }
 }
 
 //iterator!{struct VecIterator -> *T, &'self T}
-/// An iterator for iterating over a vector
+/// An iterator for iterating over a vector.
 pub struct VecIterator<'self, T> {
     priv ptr: *T,
     priv end: *T,
@@ -2125,7 +2048,7 @@ pub struct VecIterator<'self, T> {
 iterator!{impl VecIterator -> &'self T, 1}
 
 //iterator!{struct VecRevIterator -> *T, &'self T}
-/// An iterator for iterating over a vector in reverse
+/// An iterator for iterating over a vector in reverse.
 pub struct VecRevIterator<'self, T> {
     priv ptr: *T,
     priv end: *T,
@@ -2134,7 +2057,7 @@ pub struct VecRevIterator<'self, T> {
 iterator!{impl VecRevIterator -> &'self T, -1}
 
 //iterator!{struct VecMutIterator -> *mut T, &'self mut T}
-/// An iterator for mutating the elements of a vector
+/// An iterator for mutating the elements of a vector.
 pub struct VecMutIterator<'self, T> {
     priv ptr: *mut T,
     priv end: *mut T,
@@ -2143,7 +2066,7 @@ pub struct VecMutIterator<'self, T> {
 iterator!{impl VecMutIterator -> &'self mut T, 1}
 
 //iterator!{struct VecMutRevIterator -> *mut T, &'self mut T}
-/// An iterator for mutating the elements of a vector in reverse
+/// An iterator for mutating the elements of a vector in reverse.
 pub struct VecMutRevIterator<'self, T> {
     priv ptr: *mut T,
     priv end: *mut T,
@@ -2151,12 +2074,40 @@ pub struct VecMutRevIterator<'self, T> {
 }
 iterator!{impl VecMutRevIterator -> &'self mut T, -1}
 
-impl<T> FromIter<T> for ~[T]{
-    #[inline]
-    pub fn from_iter(iter: &fn(f: &fn(T) -> bool) -> bool) -> ~[T] {
-        let mut v = ~[];
-        for iter |x| { v.push(x) }
-        v
+/// An iterator that moves out of a vector.
+pub struct VecConsumeIterator<T> {
+    priv v: ~[T],
+    priv idx: uint,
+}
+
+impl<T> Iterator<T> for VecConsumeIterator<T> {
+    fn next(&mut self) -> Option<T> {
+        // this is peculiar, but is required for safety with respect
+        // to dtors. It traverses the first half of the vec, and
+        // removes them by swapping them with the last element (and
+        // popping), which results in the second half in reverse
+        // order, and so these can just be pop'd off. That is,
+        //
+        // [1,2,3,4,5] => 1, [5,2,3,4] => 2, [5,4,3] => 3, [5,4] => 4,
+        // [5] -> 5, []
+        let l = self.v.len();
+        if self.idx < l {
+            self.v.swap(self.idx, l - 1);
+            self.idx += 1;
+        }
+
+        self.v.pop_opt()
+    }
+}
+
+/// An iterator that moves out of a vector in reverse order.
+pub struct VecConsumeRevIterator<T> {
+    priv v: ~[T]
+}
+
+impl<T> Iterator<T> for VecConsumeRevIterator<T> {
+    fn next(&mut self) -> Option<T> {
+        self.v.pop_opt()
     }
 }
 
@@ -2176,7 +2127,7 @@ impl<A, T: Iterator<A>> FromIterator<A, T> for ~[A] {
 impl<A, T: Iterator<A>> FromIterator<A, T> for ~[A] {
     pub fn from_iterator(iterator: &mut T) -> ~[A] {
         let (lower, _) = iterator.size_hint();
-        let mut xs = with_capacity(lower.get_or_zero());
+        let mut xs = with_capacity(lower);
         for iterator.advance |x| {
             xs.push(x);
         }
@@ -2459,6 +2410,17 @@ mod tests {
     }
 
     #[test]
+    fn test_pop_opt() {
+        let mut v = ~[5];
+        let e = v.pop_opt();
+        assert_eq!(v.len(), 0);
+        assert_eq!(e, Some(5));
+        let f = v.pop_opt();
+        assert_eq!(f, None);
+        let g = v.pop_opt();
+        assert_eq!(g, None);
+    }
+
     fn test_swap_remove() {
         let mut v = ~[1, 2, 3, 4, 5];
         let mut e = v.swap_remove(0);
@@ -2627,87 +2589,6 @@ mod tests {
     }
 
     #[test]
-    fn test_filter_mapped() {
-        // Test on-stack filter-map.
-        let mut v = ~[1u, 2u, 3u];
-        let mut w = filter_mapped(v, square_if_odd_r);
-        assert_eq!(w.len(), 2u);
-        assert_eq!(w[0], 1u);
-        assert_eq!(w[1], 9u);
-
-        // Test on-heap filter-map.
-        v = ~[1u, 2u, 3u, 4u, 5u];
-        w = filter_mapped(v, square_if_odd_r);
-        assert_eq!(w.len(), 3u);
-        assert_eq!(w[0], 1u);
-        assert_eq!(w[1], 9u);
-        assert_eq!(w[2], 25u);
-
-        fn halve(i: &int) -> Option<int> {
-            if *i % 2 == 0 {
-                Some::<int>(*i / 2)
-            } else {
-                None::<int>
-            }
-        }
-        fn halve_for_sure(i: &int) -> int { *i / 2 }
-        let all_even: ~[int] = ~[0, 2, 8, 6];
-        let all_odd1: ~[int] = ~[1, 7, 3];
-        let all_odd2: ~[int] = ~[];
-        let mix: ~[int] = ~[9, 2, 6, 7, 1, 0, 0, 3];
-        let mix_dest: ~[int] = ~[1, 3, 0, 0];
-        assert!(filter_mapped(all_even, halve) ==
-                     all_even.map(halve_for_sure));
-        assert_eq!(filter_mapped(all_odd1, halve), ~[]);
-        assert_eq!(filter_mapped(all_odd2, halve), ~[]);
-        assert_eq!(filter_mapped(mix, halve), mix_dest);
-    }
-
-    #[test]
-    fn test_filter_map() {
-        // Test on-stack filter-map.
-        let mut v = ~[1u, 2u, 3u];
-        let mut w = filter_map(v, square_if_odd_v);
-        assert_eq!(w.len(), 2u);
-        assert_eq!(w[0], 1u);
-        assert_eq!(w[1], 9u);
-
-        // Test on-heap filter-map.
-        v = ~[1u, 2u, 3u, 4u, 5u];
-        w = filter_map(v, square_if_odd_v);
-        assert_eq!(w.len(), 3u);
-        assert_eq!(w[0], 1u);
-        assert_eq!(w[1], 9u);
-        assert_eq!(w[2], 25u);
-
-        fn halve(i: int) -> Option<int> {
-            if i % 2 == 0 {
-                Some::<int>(i / 2)
-            } else {
-                None::<int>
-            }
-        }
-        fn halve_for_sure(i: &int) -> int { *i / 2 }
-        let all_even: ~[int] = ~[0, 2, 8, 6];
-        let all_even0: ~[int] = copy all_even;
-        let all_odd1: ~[int] = ~[1, 7, 3];
-        let all_odd2: ~[int] = ~[];
-        let mix: ~[int] = ~[9, 2, 6, 7, 1, 0, 0, 3];
-        let mix_dest: ~[int] = ~[1, 3, 0, 0];
-        assert!(filter_map(all_even, halve) ==
-                     all_even0.map(halve_for_sure));
-        assert_eq!(filter_map(all_odd1, halve), ~[]);
-        assert_eq!(filter_map(all_odd2, halve), ~[]);
-        assert_eq!(filter_map(mix, halve), mix_dest);
-    }
-
-    #[test]
-    fn test_filter() {
-        assert_eq!(filter(~[1u, 2u, 3u], is_odd), ~[1u, 3u]);
-        assert_eq!(filter(~[1u, 2u, 4u, 8u, 16u], is_three), ~[]);
-    }
-
-    #[test]
     fn test_retain() {
         let mut v = ~[1, 2, 3, 4, 5];
         v.retain(is_odd);
@@ -2821,75 +2702,17 @@ mod tests {
     }
 
     #[test]
-    fn reverse_and_reversed() {
+    fn test_reverse() {
         let mut v: ~[int] = ~[10, 20];
         assert_eq!(v[0], 10);
         assert_eq!(v[1], 20);
         v.reverse();
         assert_eq!(v[0], 20);
         assert_eq!(v[1], 10);
-        let v2 = reversed::<int>([10, 20]);
-        assert_eq!(v2[0], 20);
-        assert_eq!(v2[1], 10);
-        v[0] = 30;
-        assert_eq!(v2[0], 20);
-        // Make sure they work with 0-length vectors too.
-
-        let v4 = reversed::<int>([]);
-        assert_eq!(v4, ~[]);
+
         let mut v3: ~[int] = ~[];
         v3.reverse();
-    }
-
-    #[test]
-    fn reversed_mut() {
-        let v2 = reversed::<int>([10, 20]);
-        assert_eq!(v2[0], 20);
-        assert_eq!(v2[1], 10);
-    }
-
-    #[test]
-    fn test_split() {
-        fn f(x: &int) -> bool { *x == 3 }
-
-        assert_eq!(split([], f), ~[]);
-        assert_eq!(split([1, 2], f), ~[~[1, 2]]);
-        assert_eq!(split([3, 1, 2], f), ~[~[], ~[1, 2]]);
-        assert_eq!(split([1, 2, 3], f), ~[~[1, 2], ~[]]);
-        assert_eq!(split([1, 2, 3, 4, 3, 5], f), ~[~[1, 2], ~[4], ~[5]]);
-    }
-
-    #[test]
-    fn test_splitn() {
-        fn f(x: &int) -> bool { *x == 3 }
-
-        assert_eq!(splitn([], 1u, f), ~[]);
-        assert_eq!(splitn([1, 2], 1u, f), ~[~[1, 2]]);
-        assert_eq!(splitn([3, 1, 2], 1u, f), ~[~[], ~[1, 2]]);
-        assert_eq!(splitn([1, 2, 3], 1u, f), ~[~[1, 2], ~[]]);
-        assert!(splitn([1, 2, 3, 4, 3, 5], 1u, f) ==
-                      ~[~[1, 2], ~[4, 3, 5]]);
-    }
-
-    #[test]
-    fn test_rsplit() {
-        fn f(x: &int) -> bool { *x == 3 }
-
-        assert_eq!(rsplit([], f), ~[]);
-        assert_eq!(rsplit([1, 2], f), ~[~[1, 2]]);
-        assert_eq!(rsplit([1, 2, 3], f), ~[~[1, 2], ~[]]);
-        assert!(rsplit([1, 2, 3, 4, 3, 5], f) ==
-            ~[~[1, 2], ~[4], ~[5]]);
-    }
-
-    #[test]
-    fn test_rsplitn() {
-        fn f(x: &int) -> bool { *x == 3 }
-
-        assert_eq!(rsplitn([], 1u, f), ~[]);
-        assert_eq!(rsplitn([1, 2], 1u, f), ~[~[1, 2]]);
-        assert_eq!(rsplitn([1, 2, 3], 1u, f), ~[~[1, 2], ~[]]);
-        assert_eq!(rsplitn([1, 2, 3, 4, 3, 5], 1u, f), ~[~[1, 2, 3, 4], ~[5]]);
+        assert!(v3.is_empty());
     }
 
     #[test]
@@ -2933,28 +2756,24 @@ mod tests {
     }
 
     #[test]
-    fn test_windowed () {
-        fn t(n: uint, expected: &[&[int]]) {
-            let mut i = 0;
-            for windowed(n, [1,2,3,4,5,6]) |v| {
-                assert_eq!(v, expected[i]);
-                i += 1;
-            }
-
-            // check that we actually iterated the right number of times
-            assert_eq!(i, expected.len());
-        }
-        t(3, &[&[1,2,3],&[2,3,4],&[3,4,5],&[4,5,6]]);
-        t(4, &[&[1,2,3,4],&[2,3,4,5],&[3,4,5,6]]);
-        t(7, &[]);
-        t(8, &[]);
+    fn test_shift() {
+        let mut x = ~[1, 2, 3];
+        assert_eq!(x.shift(), 1);
+        assert_eq!(&x, &~[2, 3]);
+        assert_eq!(x.shift(), 2);
+        assert_eq!(x.shift(), 3);
+        assert_eq!(x.len(), 0);
     }
 
     #[test]
-    #[should_fail]
-    #[ignore(cfg(windows))]
-    fn test_windowed_() {
-        for windowed (0u, [1u,2u,3u,4u,5u,6u]) |_v| {}
+    fn test_shift_opt() {
+        let mut x = ~[1, 2, 3];
+        assert_eq!(x.shift_opt(), Some(1));
+        assert_eq!(&x, &~[2, 3]);
+        assert_eq!(x.shift_opt(), Some(2));
+        assert_eq!(x.shift_opt(), Some(3));
+        assert_eq!(x.shift_opt(), None);
+        assert_eq!(x.len(), 0);
     }
 
     #[test]
@@ -3061,156 +2880,6 @@ mod tests {
     #[ignore(windows)]
     #[should_fail]
     #[allow(non_implicitly_copyable_typarams)]
-    fn test_split_fail_ret_true() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do split(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 1;
-
-            true
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
-    fn test_split_fail_ret_false() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do split(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 1;
-
-            false
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
-    fn test_splitn_fail_ret_true() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do splitn(v, 100) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 1;
-
-            true
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
-    fn test_splitn_fail_ret_false() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do split(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 1;
-
-            false
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
-    fn test_rsplit_fail_ret_true() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do rsplit(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 1;
-
-            true
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
-    fn test_rsplit_fail_ret_false() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do rsplit(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 1;
-
-            false
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
-    fn test_rsplitn_fail_ret_true() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do rsplitn(v, 100) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 1;
-
-            true
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
-    fn test_rsplitn_fail_ret_false() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do rsplitn(v, 100) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 1;
-
-            false
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_consume_fail() {
-        let v = ~[(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do consume(v) |_i, _elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 1;
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
     fn test_grow_fn_fail() {
         let mut v = ~[];
         do v.grow_fn(100) |i| {
@@ -3239,21 +2908,6 @@ mod tests {
     #[test]
     #[ignore(windows)]
     #[should_fail]
-    fn test_map_consume_fail() {
-        let v = ~[(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do map_consume(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            ~[(~0, @0)]
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
     fn test_flat_map_fail() {
         let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
         let mut i = 0;
@@ -3269,38 +2923,6 @@ mod tests {
     #[test]
     #[ignore(windows)]
     #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
-    fn test_filter_mapped_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do filter_mapped(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            Some((~0, @0))
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
-    fn test_filter_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do v.filtered |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            true
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
     fn test_rposition_fail() {
         let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
         let mut i = 0;
@@ -3333,7 +2955,7 @@ mod tests {
     #[should_fail]
     fn test_as_imm_buf_fail() {
         let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        do as_imm_buf(v) |_buf, _i| {
+        do v.as_imm_buf |_buf, _i| {
             fail!()
         }
     }
@@ -3343,7 +2965,7 @@ mod tests {
     #[should_fail]
     fn test_as_mut_buf_fail() {
         let mut v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        do as_mut_buf(v) |_buf, _i| {
+        do v.as_mut_buf |_buf, _i| {
             fail!()
         }
     }
@@ -3373,21 +2995,31 @@ mod tests {
         use iterator::*;
         let xs = [1, 2, 5, 10, 11];
         let mut it = xs.iter();
-        assert_eq!(it.size_hint(), (Some(5), Some(5)));
+        assert_eq!(it.size_hint(), (5, Some(5)));
         assert_eq!(it.next().unwrap(), &1);
-        assert_eq!(it.size_hint(), (Some(4), Some(4)));
+        assert_eq!(it.size_hint(), (4, Some(4)));
         assert_eq!(it.next().unwrap(), &2);
-        assert_eq!(it.size_hint(), (Some(3), Some(3)));
+        assert_eq!(it.size_hint(), (3, Some(3)));
         assert_eq!(it.next().unwrap(), &5);
-        assert_eq!(it.size_hint(), (Some(2), Some(2)));
+        assert_eq!(it.size_hint(), (2, Some(2)));
         assert_eq!(it.next().unwrap(), &10);
-        assert_eq!(it.size_hint(), (Some(1), Some(1)));
+        assert_eq!(it.size_hint(), (1, Some(1)));
         assert_eq!(it.next().unwrap(), &11);
-        assert_eq!(it.size_hint(), (Some(0), Some(0)));
+        assert_eq!(it.size_hint(), (0, Some(0)));
         assert!(it.next().is_none());
     }
 
     #[test]
+    fn test_iter_size_hints() {
+        use iterator::*;
+        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)));
+        assert_eq!(xs.mut_iter().size_hint(), (5, Some(5)));
+        assert_eq!(xs.mut_rev_iter().size_hint(), (5, Some(5)));
+    }
+
+    #[test]
     fn test_mut_iterator() {
         use iterator::*;
         let mut xs = [1, 2, 3, 4, 5];
@@ -3422,6 +3054,120 @@ mod tests {
     }
 
     #[test]
+    fn test_consume_iterator() {
+        use iterator::*;
+        let xs = ~[1u,2,3,4,5];
+        assert_eq!(xs.consume_iter().fold(0, |a: uint, b: uint| 10*a + b), 12345);
+    }
+
+    #[test]
+    fn test_consume_rev_iterator() {
+        use iterator::*;
+        let xs = ~[1u,2,3,4,5];
+        assert_eq!(xs.consume_rev_iter().fold(0, |a: uint, b: uint| 10*a + b), 54321);
+    }
+
+    #[test]
+    fn test_split_iterator() {
+        let xs = &[1i,2,3,4,5];
+
+        assert_eq!(xs.split_iter(|x| *x % 2 == 0).collect::<~[&[int]]>(),
+                   ~[&[1], &[3], &[5]]);
+        assert_eq!(xs.split_iter(|x| *x == 1).collect::<~[&[int]]>(),
+                   ~[&[], &[2,3,4,5]]);
+        assert_eq!(xs.split_iter(|x| *x == 5).collect::<~[&[int]]>(),
+                   ~[&[1,2,3,4], &[]]);
+        assert_eq!(xs.split_iter(|x| *x == 10).collect::<~[&[int]]>(),
+                   ~[&[1,2,3,4,5]]);
+        assert_eq!(xs.split_iter(|_| true).collect::<~[&[int]]>(),
+                   ~[&[], &[], &[], &[], &[], &[]]);
+
+        let xs: &[int] = &[];
+        assert_eq!(xs.split_iter(|x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
+    }
+
+    #[test]
+    fn test_splitn_iterator() {
+        let xs = &[1i,2,3,4,5];
+
+        assert_eq!(xs.splitn_iter(0, |x| *x % 2 == 0).collect::<~[&[int]]>(),
+                   ~[&[1,2,3,4,5]]);
+        assert_eq!(xs.splitn_iter(1, |x| *x % 2 == 0).collect::<~[&[int]]>(),
+                   ~[&[1], &[3,4,5]]);
+        assert_eq!(xs.splitn_iter(3, |_| true).collect::<~[&[int]]>(),
+                   ~[&[], &[], &[], &[4,5]]);
+
+        let xs: &[int] = &[];
+        assert_eq!(xs.splitn_iter(1, |x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
+    }
+
+    #[test]
+    fn test_rsplit_iterator() {
+        let xs = &[1i,2,3,4,5];
+
+        assert_eq!(xs.rsplit_iter(|x| *x % 2 == 0).collect::<~[&[int]]>(),
+                   ~[&[5], &[3], &[1]]);
+        assert_eq!(xs.rsplit_iter(|x| *x == 1).collect::<~[&[int]]>(),
+                   ~[&[2,3,4,5], &[]]);
+        assert_eq!(xs.rsplit_iter(|x| *x == 5).collect::<~[&[int]]>(),
+                   ~[&[], &[1,2,3,4]]);
+        assert_eq!(xs.rsplit_iter(|x| *x == 10).collect::<~[&[int]]>(),
+                   ~[&[1,2,3,4,5]]);
+
+        let xs: &[int] = &[];
+        assert_eq!(xs.rsplit_iter(|x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
+    }
+
+    #[test]
+    fn test_rsplitn_iterator() {
+        let xs = &[1,2,3,4,5];
+
+        assert_eq!(xs.rsplitn_iter(0, |x| *x % 2 == 0).collect::<~[&[int]]>(),
+                   ~[&[1,2,3,4,5]]);
+        assert_eq!(xs.rsplitn_iter(1, |x| *x % 2 == 0).collect::<~[&[int]]>(),
+                   ~[&[5], &[1,2,3]]);
+        assert_eq!(xs.rsplitn_iter(3, |_| true).collect::<~[&[int]]>(),
+                   ~[&[], &[], &[], &[1,2]]);
+
+        let xs: &[int] = &[];
+        assert_eq!(xs.rsplitn_iter(1, |x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
+    }
+
+    #[test]
+    fn test_window_iterator() {
+        let v = &[1i,2,3,4];
+
+        assert_eq!(v.window_iter(2).collect::<~[&[int]]>(), ~[&[1,2], &[2,3], &[3,4]]);
+        assert_eq!(v.window_iter(3).collect::<~[&[int]]>(), ~[&[1i,2,3], &[2,3,4]]);
+        assert!(v.window_iter(6).next().is_none());
+    }
+
+    #[test]
+    #[should_fail]
+    #[ignore(cfg(windows))]
+    fn test_window_iterator_0() {
+        let v = &[1i,2,3,4];
+        let _it = v.window_iter(0);
+    }
+
+    #[test]
+    fn test_chunk_iterator() {
+        let v = &[1i,2,3,4,5];
+
+        assert_eq!(v.chunk_iter(2).collect::<~[&[int]]>(), ~[&[1i,2], &[3,4], &[5]]);
+        assert_eq!(v.chunk_iter(3).collect::<~[&[int]]>(), ~[&[1i,2,3], &[4,5]]);
+        assert_eq!(v.chunk_iter(6).collect::<~[&[int]]>(), ~[&[1i,2,3,4,5]]);
+    }
+
+    #[test]
+    #[should_fail]
+    #[ignore(cfg(windows))]
+    fn test_chunk_iterator_0() {
+        let v = &[1i,2,3,4];
+        let _it = v.chunk_iter(0);
+    }
+
+    #[test]
     fn test_move_from() {
         let mut a = [1,2,3,4,5];
         let b = ~[6,7,8];