Merge remote-tracking branch 'mozilla/master'

Conflicts:
	src/libextra/test.rs
	src/libstd/at_vec.rs
	src/libstd/cleanup.rs
	src/libstd/rt/comm.rs
	src/libstd/rt/global_heap.rs
	src/libstd/task/spawn.rs
	src/libstd/unstable/lang.rs
	src/libstd/vec.rs
	src/rt/rustrt.def.in
	src/test/run-pass/extern-pub.rs

1 files changed, 820 insertions, 1606 deletions

diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index 4339153c43e..1180ac883e7 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -15,113 +15,45 @@
 use cast::transmute;
 use cast;
 use container::{Container, Mutable};
+use cmp;
 use cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Less, Equal, Greater};
 use clone::Clone;
-use old_iter::BaseIter;
-use old_iter;
-use iterator::{Iterator};
+use iterator::{FromIterator, Iterator, IteratorUtil};
 use iter::FromIter;
 use kinds::Copy;
-use libc;
+use libc::c_void;
 use num::Zero;
-use old_iter::CopyableIter;
+use ops::Add;
 use option::{None, Option, Some};
 use ptr::to_unsafe_ptr;
 use ptr;
 use ptr::RawPtr;
+use rt::global_heap::realloc_raw;
 use sys;
+use sys::size_of;
 use uint;
 use unstable::intrinsics;
+#[cfg(stage0)]
+use intrinsic::{get_tydesc};
+#[cfg(not(stage0))]
+use unstable::intrinsics::{get_tydesc, contains_managed};
 use vec;
 use util;
 
 #[cfg(not(test))] use cmp::Equiv;
 
-pub mod rustrt {
-    use libc;
-    use sys;
-    use vec::raw;
-
-    #[abi = "cdecl"]
-    pub extern {
-        // These names are terrible. reserve_shared applies
-        // to ~[] and reserve_shared_actual applies to @[].
-        #[fast_ffi]
-        unsafe fn vec_reserve_shared(t: *sys::TypeDesc,
-                                     v: *mut *mut raw::VecRepr,
-                                     n: libc::size_t);
-    }
-}
-
 /// Returns true if two vectors have the same length
-pub fn same_length<T, U>(xs: &const [T], ys: &const [U]) -> bool {
+pub fn same_length<T, U>(xs: &[T], ys: &[U]) -> bool {
     xs.len() == ys.len()
 }
 
 /**
- * Reserves capacity for exactly `n` elements in the given vector.
- *
- * If the capacity for `v` is already equal to or greater than the requested
- * capacity, then no action is taken.
- *
- * # Arguments
- *
- * * v - A vector
- * * n - The number of elements to reserve space for
- */
-#[inline]
-pub fn reserve<T>(v: &mut ~[T], n: uint) {
-    // Only make the (slow) call into the runtime if we have to
-    use managed;
-    if capacity(v) < n {
-        unsafe {
-            let ptr: *mut *mut raw::VecRepr = cast::transmute(v);
-            let td = sys::get_type_desc::<T>();
-            if ((**ptr).box_header.ref_count ==
-                managed::raw::RC_MANAGED_UNIQUE) {
-                ::at_vec::raw::reserve_raw(td, ptr, n);
-            } else {
-                rustrt::vec_reserve_shared(td, ptr, n as libc::size_t);
-            }
-        }
-    }
-}
-
-/**
- * Reserves capacity for at least `n` elements in the given vector.
- *
- * This function will over-allocate in order to amortize the allocation costs
- * in scenarios where the caller may need to repeatedly reserve additional
- * space.
- *
- * If the capacity for `v` is already equal to or greater than the requested
- * capacity, then no action is taken.
- *
- * # Arguments
- *
- * * v - A vector
- * * n - The number of elements to reserve space for
- */
-pub fn reserve_at_least<T>(v: &mut ~[T], n: uint) {
-    reserve(v, uint::next_power_of_two(n));
-}
-
-/// Returns the number of elements the vector can hold without reallocating
-#[inline]
-pub fn capacity<T>(v: &const ~[T]) -> uint {
-    unsafe {
-        let repr: **raw::VecRepr = transmute(v);
-        (**repr).unboxed.alloc / sys::nonzero_size_of::<T>()
-    }
-}
-
-/**
  * Creates and initializes an owned vector.
  *
  * Creates an owned vector of size `n_elts` and initializes the elements
  * to the value returned by the function `op`.
  */
-pub fn from_fn<T>(n_elts: uint, op: old_iter::InitOp<T>) -> ~[T] {
+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| {
@@ -169,7 +101,7 @@ pub fn to_owned<T:Copy>(t: &[T]) -> ~[T] {
 /// Creates a new vector with a capacity of `capacity`
 pub fn with_capacity<T>(capacity: uint) -> ~[T] {
     let mut vec = ~[];
-    reserve(&mut vec, capacity);
+    vec.reserve(capacity);
     vec
 }
 
@@ -228,85 +160,6 @@ pub fn build_sized_opt<A>(size: Option<uint>,
 
 // Accessors
 
-/// Returns the first element of a vector
-pub fn head<'r,T>(v: &'r [T]) -> &'r T {
-    if v.len() == 0 { fail!("head: empty vector") }
-    &v[0]
-}
-
-/// Returns `Some(x)` where `x` is the first element of the slice `v`,
-/// or `None` if the vector is empty.
-pub fn head_opt<'r,T>(v: &'r [T]) -> Option<&'r T> {
-    if v.len() == 0 { None } else { Some(&v[0]) }
-}
-
-/// Returns a vector containing all but the first element of a slice
-pub fn tail<'r,T>(v: &'r [T]) -> &'r [T] { slice(v, 1, v.len()) }
-
-/// Returns a vector containing all but the first `n` elements of a slice
-pub fn tailn<'r,T>(v: &'r [T], n: uint) -> &'r [T] { slice(v, n, v.len()) }
-
-/// Returns a vector containing all but the last element of a slice
-pub fn init<'r,T>(v: &'r [T]) -> &'r [T] { slice(v, 0, v.len() - 1) }
-
-/// Returns a vector containing all but the last `n' elements of a slice
-pub fn initn<'r,T>(v: &'r [T], n: uint) -> &'r [T] {
-    slice(v, 0, v.len() - n)
-}
-
-/// Returns the last element of the slice `v`, failing if the slice is empty.
-pub fn last<'r,T>(v: &'r [T]) -> &'r T {
-    if v.len() == 0 { fail!("last: empty vector") }
-    &v[v.len() - 1]
-}
-
-/// Returns `Some(x)` where `x` is the last element of the slice `v`, or
-/// `None` if the vector is empty.
-pub fn last_opt<'r,T>(v: &'r [T]) -> Option<&'r T> {
-    if v.len() == 0 { None } else { Some(&v[v.len() - 1]) }
-}
-
-/// Return a slice that points into another slice.
-#[inline]
-pub fn slice<'r,T>(v: &'r [T], start: uint, end: uint) -> &'r [T] {
-    assert!(start <= end);
-    assert!(end <= v.len());
-    do as_imm_buf(v) |p, _len| {
-        unsafe {
-            transmute((ptr::offset(p, start),
-                       (end - start) * sys::nonzero_size_of::<T>()))
-        }
-    }
-}
-
-/// Return a slice that points into another slice.
-#[inline]
-pub fn mut_slice<'r,T>(v: &'r mut [T], start: uint, end: uint)
-                    -> &'r mut [T] {
-    assert!(start <= end);
-    assert!(end <= v.len());
-    do as_mut_buf(v) |p, _len| {
-        unsafe {
-            transmute((ptr::mut_offset(p, start),
-                       (end - start) * sys::nonzero_size_of::<T>()))
-        }
-    }
-}
-
-/// Return a slice that points into another slice.
-#[inline]
-pub fn const_slice<'r,T>(v: &'r const [T], start: uint, end: uint)
-                      -> &'r const [T] {
-    assert!(start <= end);
-    assert!(end <= v.len());
-    do as_const_buf(v) |p, _len| {
-        unsafe {
-            transmute((ptr::const_offset(p, start),
-                       (end - start) * sys::nonzero_size_of::<T>()))
-        }
-    }
-}
-
 /// Copies
 
 /// Split the vector `v` by applying each element against the predicate `f`.
@@ -317,15 +170,15 @@ pub fn split<T:Copy>(v: &[T], f: &fn(t: &T) -> bool) -> ~[~[T]] {
     let mut start = 0u;
     let mut result = ~[];
     while start < ln {
-        match position_between(v, start, ln, f) {
+        match v.slice(start, ln).iter().position_(|t| f(t)) {
             None => break,
             Some(i) => {
-                result.push(slice(v, start, i).to_vec());
-                start = i + 1u;
+                result.push(v.slice(start, start + i).to_owned());
+                start += i + 1u;
             }
         }
     }
-    result.push(slice(v, start, ln).to_vec());
+    result.push(v.slice(start, ln).to_owned());
     result
 }
 
@@ -341,17 +194,17 @@ pub fn splitn<T:Copy>(v: &[T], n: uint, f: &fn(t: &T) -> bool) -> ~[~[T]] {
     let mut count = n;
     let mut result = ~[];
     while start < ln && count > 0u {
-        match position_between(v, start, ln, f) {
+        match v.slice(start, ln).iter().position_(|t| f(t)) {
             None => break,
             Some(i) => {
-                result.push(slice(v, start, i).to_vec());
+                result.push(v.slice(start, start + i).to_owned());
                 // Make sure to skip the separator.
-                start = i + 1u;
+                start += i + 1u;
                 count -= 1u;
             }
         }
     }
-    result.push(slice(v, start, ln).to_vec());
+    result.push(v.slice(start, ln).to_owned());
     result
 }
 
@@ -366,16 +219,16 @@ pub fn rsplit<T:Copy>(v: &[T], f: &fn(t: &T) -> bool) -> ~[~[T]] {
     let mut end = ln;
     let mut result = ~[];
     while end > 0 {
-        match rposition_between(v, 0, end, f) {
+        match v.slice(0, end).rposition(|t| f(t)) {
             None => break,
             Some(i) => {
-                result.push(slice(v, i + 1, end).to_vec());
+                result.push(v.slice(i + 1, end).to_owned());
                 end = i;
             }
         }
     }
-    result.push(slice(v, 0u, end).to_vec());
-    reverse(result);
+    result.push(v.slice(0u, end).to_owned());
+    result.reverse();
     result
 }
 
@@ -391,151 +244,21 @@ pub fn rsplitn<T:Copy>(v: &[T], n: uint, f: &fn(t: &T) -> bool) -> ~[~[T]] {
     let mut count = n;
     let mut result = ~[];
     while end > 0u && count > 0u {
-        match rposition_between(v, 0u, end, f) {
+        match v.slice(0, end).rposition(|t| f(t)) {
             None => break,
             Some(i) => {
-                result.push(slice(v, i + 1u, end).to_vec());
+                result.push(v.slice(i + 1u, end).to_owned());
                 // Make sure to skip the separator.
                 end = i;
                 count -= 1u;
             }
         }
     }
-    result.push(slice(v, 0u, end).to_vec());
-    reverse(result);
+    result.push(v.slice(0u, end).to_owned());
+    result.reverse();
     result
 }
 
-/**
- * Partitions a vector into two new vectors: those that satisfies the
- * predicate, and those that do not.
- */
-pub fn partition<T>(v: ~[T], f: &fn(&T) -> bool) -> (~[T], ~[T]) {
-    let mut lefts  = ~[];
-    let mut rights = ~[];
-
-    // FIXME (#4355 maybe): using v.consume here crashes
-    // do v.consume |_, elt| {
-    do consume(v) |_, elt| {
-        if f(&elt) {
-            lefts.push(elt);
-        } else {
-            rights.push(elt);
-        }
-    }
-
-    (lefts, rights)
-}
-
-/**
- * Partitions a vector into two new vectors: those that satisfies the
- * predicate, and those that do not.
- */
-pub fn partitioned<T:Copy>(v: &[T], f: &fn(&T) -> bool) -> (~[T], ~[T]) {
-    let mut lefts  = ~[];
-    let mut rights = ~[];
-
-    for each(v) |elt| {
-        if f(elt) {
-            lefts.push(copy *elt);
-        } else {
-            rights.push(copy *elt);
-        }
-    }
-
-    (lefts, rights)
-}
-
-// Mutators
-
-/// Removes the first element from a vector and return it
-pub fn shift<T>(v: &mut ~[T]) -> T {
-    unsafe {
-        assert!(!v.is_empty());
-
-        if v.len() == 1 { return v.pop() }
-
-        if v.len() == 2 {
-            let last = v.pop();
-            let first = v.pop();
-            v.push(last);
-            return first;
-        }
-
-        let ln = v.len();
-        let next_ln = v.len() - 1;
-
-        // Save the last element. We're going to overwrite its position
-        let work_elt = v.pop();
-        // We still should have room to work where what last element was
-        assert!(capacity(v) >= ln);
-        // Pretend like we have the original length so we can use
-        // the vector copy_memory to overwrite the hole we just made
-        raw::set_len(&mut *v, ln);
-
-        // Memcopy the head element (the one we want) to the location we just
-        // popped. For the moment it unsafely exists at both the head and last
-        // positions
-        {
-            let first_slice = slice(*v, 0, 1);
-            let last_slice = slice(*v, next_ln, ln);
-            raw::copy_memory(transmute(last_slice), first_slice, 1);
-        }
-
-        // Memcopy everything to the left one element
-        {
-            let init_slice = slice(*v, 0, next_ln);
-            let tail_slice = slice(*v, 1, ln);
-            raw::copy_memory(transmute(init_slice),
-                             tail_slice,
-                             next_ln);
-        }
-
-        // Set the new length. Now the vector is back to normal
-        raw::set_len(&mut *v, next_ln);
-
-        // Swap out the element we want from the end
-        let vp = raw::to_mut_ptr(*v);
-        let vp = ptr::mut_offset(vp, next_ln - 1);
-
-        ptr::replace_ptr(vp, work_elt)
-    }
-}
-
-/// Prepend an element to the vector
-pub fn unshift<T>(v: &mut ~[T], x: T) {
-    let vv = util::replace(v, ~[x]);
-    v.push_all_move(vv);
-}
-
-/// Insert an element at position i within v, shifting all
-/// elements after position i one position to the right.
-pub fn insert<T>(v: &mut ~[T], i: uint, x: T) {
-    let len = v.len();
-    assert!(i <= len);
-
-    v.push(x);
-    let mut j = len;
-    while j > i {
-        swap(*v, j, j - 1);
-        j -= 1;
-    }
-}
-
-/// Remove and return the element at position i within v, shifting
-/// all elements after position i one position to the left.
-pub fn remove<T>(v: &mut ~[T], i: uint) -> T {
-    let len = v.len();
-    assert!(i < len);
-
-    let mut j = i;
-    while j < len - 1 {
-        swap(*v, j, j + 1);
-        j += 1;
-    }
-    v.pop()
-}
-
 /// Consumes all elements, in a vector, moving them out into the / closure
 /// provided. The vector is traversed from the start to the end.
 ///
@@ -597,174 +320,12 @@ pub fn consume_reverse<T>(mut v: ~[T], f: &fn(uint, v: T)) {
     }
 }
 
-/// Remove the last element from a vector and return it
-pub fn pop<T>(v: &mut ~[T]) -> T {
-    let ln = v.len();
-    if ln == 0 {
-        fail!("sorry, cannot vec::pop an empty vector")
-    }
-    let valptr = ptr::to_mut_unsafe_ptr(&mut v[ln - 1u]);
-    unsafe {
-        let val = ptr::replace_ptr(valptr, intrinsics::init());
-        raw::set_len(v, ln - 1u);
-        val
-    }
-}
-
-/**
- * Remove an element from anywhere in the vector and return it, replacing it
- * with the last element. This does not preserve ordering, but is O(1).
- *
- * Fails if index >= length.
- */
-pub fn swap_remove<T>(v: &mut ~[T], index: uint) -> T {
-    let ln = v.len();
-    if index >= ln {
-        fail!("vec::swap_remove - index %u >= length %u", index, ln);
-    }
-    if index < ln - 1 {
-        swap(*v, index, ln - 1);
-    }
-    v.pop()
-}
-
-/// Append an element to a vector
-#[inline]
-pub fn push<T>(v: &mut ~[T], initval: T) {
-    unsafe {
-        let repr: **raw::VecRepr = transmute(&mut *v);
-        let fill = (**repr).unboxed.fill;
-        if (**repr).unboxed.alloc > fill {
-            push_fast(v, initval);
-        }
-        else {
-            push_slow(v, initval);
-        }
-    }
-}
-
-// This doesn't bother to make sure we have space.
-#[inline] // really pretty please
-unsafe fn push_fast<T>(v: &mut ~[T], initval: T) {
-    let repr: **mut raw::VecRepr = transmute(v);
-    let fill = (**repr).unboxed.fill;
-    (**repr).unboxed.fill += sys::nonzero_size_of::<T>();
-    let p = to_unsafe_ptr(&((**repr).unboxed.data));
-    let p = ptr::offset(p, fill) as *mut T;
-    intrinsics::move_val_init(&mut(*p), initval);
-}
-
-#[inline(never)]
-fn push_slow<T>(v: &mut ~[T], initval: T) {
-    let new_len = v.len() + 1;
-    reserve_at_least(&mut *v, new_len);
-    unsafe { push_fast(v, initval) }
-}
-
-/// Iterates over the slice `rhs`, copies each element, and then appends it to
-/// the vector provided `v`. The `rhs` vector is traversed in-order.
-///
-/// # Example
-///
-/// ~~~ {.rust}
-/// let mut a = ~[1];
-/// vec::push_all(&mut a, [2, 3, 4]);
-/// assert!(a == ~[1, 2, 3, 4]);
-/// ~~~
-#[inline]
-pub fn push_all<T:Copy>(v: &mut ~[T], rhs: &const [T]) {
-    let new_len = v.len() + rhs.len();
-    reserve(&mut *v, new_len);
-
-    for uint::range(0u, rhs.len()) |i| {
-        push(&mut *v, unsafe { raw::get(rhs, i) })
-    }
-}
-
-/// Takes ownership of the vector `rhs`, moving all elements into the specified
-/// vector `v`. This does not copy any elements, and it is illegal to use the
-/// `rhs` vector after calling this method (because it is moved here).
-///
-/// # Example
-///
-/// ~~~ {.rust}
-/// let mut a = ~[~1];
-/// vec::push_all_move(&mut a, ~[~2, ~3, ~4]);
-/// assert!(a == ~[~1, ~2, ~3, ~4]);
-/// ~~~
-#[inline]
-pub fn push_all_move<T>(v: &mut ~[T], mut rhs: ~[T]) {
-    let new_len = v.len() + rhs.len();
-    reserve(&mut *v, new_len);
-    unsafe {
-        do as_mut_buf(rhs) |p, len| {
-            for uint::range(0, len) |i| {
-                let x = ptr::replace_ptr(ptr::mut_offset(p, i),
-                                         intrinsics::uninit());
-                push(&mut *v, x);
-            }
-        }
-        raw::set_len(&mut rhs, 0);
-    }
-}
-
-/// Shorten a vector, dropping excess elements.
-pub fn truncate<T>(v: &mut ~[T], newlen: uint) {
-    do as_mut_buf(*v) |p, oldlen| {
-        assert!(newlen <= oldlen);
-        unsafe {
-            // This loop is optimized out for non-drop types.
-            for uint::range(newlen, oldlen) |i| {
-                ptr::replace_ptr(ptr::mut_offset(p, i), intrinsics::uninit());
-            }
-        }
-    }
-    unsafe { raw::set_len(&mut *v, newlen); }
-}
-
-/**
- * Remove consecutive repeated elements from a vector; if the vector is
- * sorted, this removes all duplicates.
- */
-pub fn dedup<T:Eq>(v: &mut ~[T]) {
-    unsafe {
-        if v.len() < 1 { return; }
-        let mut (last_written, next_to_read) = (0, 1);
-        do as_const_buf(*v) |p, ln| {
-            // We have a mutable reference to v, so we can make arbitrary
-            // changes. (cf. push and pop)
-            let p = p as *mut T;
-            // last_written < next_to_read <= ln
-            while next_to_read < ln {
-                // last_written < next_to_read < ln
-                if *ptr::mut_offset(p, next_to_read) ==
-                    *ptr::mut_offset(p, last_written) {
-                    ptr::replace_ptr(ptr::mut_offset(p, next_to_read),
-                                     intrinsics::uninit());
-                } else {
-                    last_written += 1;
-                    // last_written <= next_to_read < ln
-                    if next_to_read != last_written {
-                        ptr::swap_ptr(ptr::mut_offset(p, last_written),
-                                      ptr::mut_offset(p, next_to_read));
-                    }
-                }
-                // last_written <= next_to_read < ln
-                next_to_read += 1;
-                // last_written < next_to_read <= ln
-            }
-        }
-        // last_written < next_to_read == ln
-        raw::set_len(v, last_written + 1);
-    }
-}
-
 // Appending
 
 /// Iterates over the `rhs` vector, copying each element and appending it to the
 /// `lhs`. Afterwards, the `lhs` is then returned for use again.
 #[inline]
-pub fn append<T:Copy>(lhs: ~[T], rhs: &const [T]) -> ~[T] {
+pub fn append<T:Copy>(lhs: ~[T], rhs: &[T]) -> ~[T] {
     let mut v = lhs;
     v.push_all(rhs);
     v
@@ -779,74 +340,8 @@ pub fn append_one<T>(lhs: ~[T], x: T) -> ~[T] {
     v
 }
 
-/**
- * Expands a vector in place, initializing the new elements to a given value
- *
- * # Arguments
- *
- * * v - The vector to grow
- * * n - The number of elements to add
- * * initval - The value for the new elements
- */
-pub fn grow<T:Copy>(v: &mut ~[T], n: uint, initval: &T) {
-    let new_len = v.len() + n;
-    reserve_at_least(&mut *v, new_len);
-    let mut i: uint = 0u;
-
-    while i < n {
-        v.push(copy *initval);
-        i += 1u;
-    }
-}
-
-/**
- * Expands a vector in place, initializing the new elements to the result of
- * a function
- *
- * Function `init_op` is called `n` times with the values [0..`n`)
- *
- * # Arguments
- *
- * * v - The vector to grow
- * * n - The number of elements to add
- * * init_op - A function to call to retreive each appended element's
- *             value
- */
-pub fn grow_fn<T>(v: &mut ~[T], n: uint, op: old_iter::InitOp<T>) {
-    let new_len = v.len() + n;
-    reserve_at_least(&mut *v, new_len);
-    let mut i: uint = 0u;
-    while i < n {
-        v.push(op(i));
-        i += 1u;
-    }
-}
-
-/**
- * Sets the value of a vector element at a given index, growing the vector as
- * needed
- *
- * Sets the element at position `index` to `val`. If `index` is past the end
- * of the vector, expands the vector by replicating `initval` to fill the
- * intervening space.
- */
-pub fn grow_set<T:Copy>(v: &mut ~[T], index: uint, initval: &T, val: T) {
-    let l = v.len();
-    if index >= l { grow(&mut *v, index - l + 1u, initval); }
-    v[index] = val;
-}
-
 // Functional utilities
 
-/// Apply a function to each element of a vector and return the results
-pub fn map<T, U>(v: &[T], f: &fn(t: &T) -> U) -> ~[U] {
-    let mut result = with_capacity(v.len());
-    for each(v) |elem| {
-        result.push(f(elem));
-    }
-    result
-}
-
 /// 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
@@ -861,43 +356,16 @@ pub fn map_consume<T, U>(v: ~[T], f: &fn(v: T) -> U) -> ~[U] {
     }
     result
 }
-
-/// Apply a function to each element of a vector and return the results
-pub fn mapi<T, U>(v: &[T], f: &fn(uint, t: &T) -> U) -> ~[U] {
-    let mut i = 0;
-    do map(v) |e| {
-        i += 1;
-        f(i - 1, e)
-    }
-}
-
 /**
  * Apply a function to each element of a vector and return a concatenation
  * of each result vector
  */
 pub fn flat_map<T, U>(v: &[T], f: &fn(t: &T) -> ~[U]) -> ~[U] {
     let mut result = ~[];
-    for each(v) |elem| { result.push_all_move(f(elem)); }
+    for v.iter().advance |elem| { result.push_all_move(f(elem)); }
     result
 }
 
-/**
- * Apply a function to each pair of elements and return the results.
- * Equivalent to `map(zip(v0, v1), f)`.
- */
-pub fn map_zip<T:Copy,U:Copy,V>(v0: &[T], v1: &[U],
-                                  f: &fn(t: &T, v: &U) -> V) -> ~[V] {
-    let v0_len = v0.len();
-    if v0_len != v1.len() { fail!(); }
-    let mut u: ~[V] = ~[];
-    let mut i = 0u;
-    while i < v0_len {
-        u.push(f(&v0[i], &v1[i]));
-        i += 1u;
-    }
-    u
-}
-
 pub fn filter_map<T, U>(
     v: ~[T],
     f: &fn(t: T) -> Option<U>) -> ~[U]
@@ -930,7 +398,7 @@ pub fn filter_mapped<T, U: Copy>(
      */
 
     let mut result = ~[];
-    for each(v) |elem| {
+    for v.iter().advance |elem| {
         match f(elem) {
           None => {/* no-op */ }
           Some(result_elem) => { result.push(result_elem); }
@@ -965,32 +433,12 @@ pub fn filter<T>(v: ~[T], f: &fn(t: &T) -> bool) -> ~[T] {
  */
 pub fn filtered<T:Copy>(v: &[T], f: &fn(t: &T) -> bool) -> ~[T] {
     let mut result = ~[];
-    for each(v) |elem| {
+    for v.iter().advance |elem| {
         if f(elem) { result.push(copy *elem); }
     }
     result
 }
 
-/**
- * Like `filter()`, but in place.  Preserves order of `v`.  Linear time.
- */
-pub fn retain<T>(v: &mut ~[T], f: &fn(t: &T) -> bool) {
-    let len = v.len();
-    let mut deleted: uint = 0;
-
-    for uint::range(0, len) |i| {
-        if !f(&v[i]) {
-            deleted += 1;
-        } else if deleted > 0 {
-            swap(*v, i - deleted, i);
-        }
-    }
-
-    if deleted > 0 {
-        v.truncate(len - deleted);
-    }
-}
-
 /// Flattens a vector of vectors of T into a single vector of T.
 pub fn concat<T:Copy>(v: &[~[T]]) -> ~[T] { v.concat_vec() }
 
@@ -1021,7 +469,7 @@ impl<'self, T:Copy> VectorVector<T> for &'self [~[T]] {
     pub fn connect_vec(&self, sep: &T) -> ~[T] {
         let mut r = ~[];
         let mut first = true;
-        for self.each |&inner| {
+        for self.iter().advance |&inner| {
             if first { first = false; } else { r.push(copy *sep); }
             r.push_all(inner);
         }
@@ -1039,7 +487,7 @@ impl<'self, T:Copy> VectorVector<T> for &'self [&'self [T]] {
     pub fn connect_vec(&self, sep: &T) -> ~[T] {
         let mut r = ~[];
         let mut first = true;
-        for self.each |&inner| {
+        for self.iter().advance |&inner| {
             if first { first = false; } else { r.push(copy *sep); }
             r.push_all(inner);
         }
@@ -1047,172 +495,6 @@ impl<'self, T:Copy> VectorVector<T> for &'self [&'self [T]] {
     }
 }
 
-/// 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
-}
-
-/**
- * Search for the first element that matches a given predicate
- *
- * Apply function `f` to each element of `v`, starting from the first.
- * When function `f` returns true then an option containing the element
- * is returned. If `f` matches no elements then none is returned.
- */
-pub fn find<T:Copy>(v: &[T], f: &fn(t: &T) -> bool) -> Option<T> {
-    find_between(v, 0u, v.len(), f)
-}
-
-/**
- * Search for the first element that matches a given predicate within a range
- *
- * Apply function `f` to each element of `v` within the range
- * [`start`, `end`). When function `f` returns true then an option containing
- * the element is returned. If `f` matches no elements then none is returned.
- */
-pub fn find_between<T:Copy>(v: &[T], start: uint, end: uint,
-                      f: &fn(t: &T) -> bool) -> Option<T> {
-    position_between(v, start, end, f).map(|i| copy v[*i])
-}
-
-/**
- * Search for the last element that matches a given predicate
- *
- * Apply function `f` to each element of `v` in reverse order. When function
- * `f` returns true then an option containing the element is returned. If `f`
- * matches no elements then none is returned.
- */
-pub fn rfind<T:Copy>(v: &[T], f: &fn(t: &T) -> bool) -> Option<T> {
-    rfind_between(v, 0u, v.len(), f)
-}
-
-/**
- * Search for the last element that matches a given predicate within a range
- *
- * Apply function `f` to each element of `v` in reverse order within the range
- * [`start`, `end`). When function `f` returns true then an option containing
- * the element is returned. If `f` matches no elements then none is return.
- */
-pub fn rfind_between<T:Copy>(v: &[T],
-                             start: uint,
-                             end: uint,
-                             f: &fn(t: &T) -> bool)
-                          -> Option<T> {
-    rposition_between(v, start, end, f).map(|i| copy v[*i])
-}
-
-/// Find the first index containing a matching value
-pub fn position_elem<T:Eq>(v: &[T], x: &T) -> Option<uint> {
-    position(v, |y| *x == *y)
-}
-
-/**
- * Find the first index matching some predicate
- *
- * Apply function `f` to each element of `v`.  When function `f` returns true
- * then an option containing the index is returned. If `f` matches no elements
- * then none is returned.
- */
-pub fn position<T>(v: &[T], f: &fn(t: &T) -> bool) -> Option<uint> {
-    position_between(v, 0u, v.len(), f)
-}
-
-/**
- * Find the first index matching some predicate within a range
- *
- * Apply function `f` to each element of `v` between the range
- * [`start`, `end`). When function `f` returns true then an option containing
- * the index is returned. If `f` matches no elements then none is returned.
- */
-pub fn position_between<T>(v: &[T],
-                           start: uint,
-                           end: uint,
-                           f: &fn(t: &T) -> bool)
-                        -> Option<uint> {
-    assert!(start <= end);
-    assert!(end <= v.len());
-    let mut i = start;
-    while i < end { if f(&v[i]) { return Some::<uint>(i); } i += 1u; }
-    None
-}
-
-/// Find the last index containing a matching value
-pub fn rposition_elem<T:Eq>(v: &[T], x: &T) -> Option<uint> {
-    rposition(v, |y| *x == *y)
-}
-
-/**
- * Find the last index matching some predicate
- *
- * Apply function `f` to each element of `v` in reverse order.  When function
- * `f` returns true then an option containing the index is returned. If `f`
- * matches no elements then none is returned.
- */
-pub fn rposition<T>(v: &[T], f: &fn(t: &T) -> bool) -> Option<uint> {
-    rposition_between(v, 0u, v.len(), f)
-}
-
-/**
- * Find the last index matching some predicate within a range
- *
- * Apply function `f` to each element of `v` in reverse order between the
- * range [`start`, `end`). When function `f` returns true then an option
- * containing the index is returned. If `f` matches no elements then none is
- * returned.
- */
-pub fn rposition_between<T>(v: &[T], start: uint, end: uint,
-                             f: &fn(t: &T) -> bool) -> Option<uint> {
-    assert!(start <= end);
-    assert!(end <= v.len());
-    let mut i = end;
-    while i > start {
-        if f(&v[i - 1u]) { return Some::<uint>(i - 1u); }
-        i -= 1u;
-    }
-    None
-}
-
-
-
-/**
- * Binary search a sorted vector with a comparator function.
- *
- * The comparator should implement an order consistent with the sort
- * order of the underlying vector, returning an order code that indicates
- * whether its argument is `Less`, `Equal` or `Greater` the desired target.
- *
- * Returns the index where the comparator returned `Equal`, or `None` if
- * not found.
- */
-pub fn bsearch<T>(v: &[T], f: &fn(&T) -> Ordering) -> Option<uint> {
-    let mut base : uint = 0;
-    let mut lim : uint = v.len();
-
-    while lim != 0 {
-        let ix = base + (lim >> 1);
-        match f(&v[ix]) {
-            Equal => return Some(ix),
-            Less => {
-                base = ix + 1;
-                lim -= 1;
-            }
-            Greater => ()
-        }
-        lim >>= 1;
-    }
-    return None;
-}
-
-/**
- * Binary search a sorted vector for a given element.
- *
- * Returns the index of the element or None if not found.
- */
-pub fn bsearch_elem<T:TotalOrd>(v: &[T], x: &T) -> Option<uint> {
-    bsearch(v, |p| p.cmp(x))
-}
-
 // FIXME: if issue #586 gets implemented, could have a postcondition
 // saying the two result lists have the same length -- or, could
 // return a nominal record with a constraint saying that, instead of
@@ -1221,8 +503,9 @@ pub fn bsearch_elem<T:TotalOrd>(v: &[T], x: &T) -> Option<uint> {
  * Convert a vector of pairs into a pair of vectors, by reference. As unzip().
  */
 pub fn unzip_slice<T:Copy,U:Copy>(v: &[(T, U)]) -> (~[T], ~[U]) {
-    let mut (ts, us) = (~[], ~[]);
-    for each(v) |p| {
+    let mut ts = ~[];
+    let mut us = ~[];
+    for v.iter().advance |p| {
         let (t, u) = copy *p;
         ts.push(t);
         us.push(u);
@@ -1239,7 +522,8 @@ pub fn unzip_slice<T:Copy,U:Copy>(v: &[(T, U)]) -> (~[T], ~[U]) {
  * of the i-th tuple of the input vector.
  */
 pub fn unzip<T,U>(v: ~[(T, U)]) -> (~[T], ~[U]) {
-    let mut (ts, us) = (~[], ~[]);
+    let mut ts = ~[];
+    let mut us = ~[];
     do consume(v) |_i, p| {
         let (t, u) = p;
         ts.push(t);
@@ -1251,7 +535,7 @@ pub fn unzip<T,U>(v: ~[(T, U)]) -> (~[T], ~[U]) {
 /**
  * Convert two vectors to a vector of pairs, by reference. As zip().
  */
-pub fn zip_slice<T:Copy,U:Copy>(v: &const [T], u: &const [U])
+pub fn zip_slice<T:Copy,U:Copy>(v: &[T], u: &[U])
         -> ~[(T, U)] {
     let mut zipped = ~[];
     let sz = v.len();
@@ -1278,80 +562,12 @@ pub fn zip<T, U>(mut v: ~[T], mut u: ~[U]) -> ~[(T, U)] {
         w.push((v.pop(),u.pop()));
         i -= 1;
     }
-    reverse(w);
+    w.reverse();
     w
 }
 
-/**
- * Swaps two elements in a vector
- *
- * # Arguments
- *
- * * v  The input vector
- * * a - The index of the first element
- * * b - The index of the second element
- */
-#[inline]
-pub fn swap<T>(v: &mut [T], a: uint, b: uint) {
-    unsafe {
-        // Can't take two mutable loans from one vector, so instead just cast
-        // them to their raw pointers to do the swap
-        let pa: *mut T = &mut v[a];
-        let pb: *mut T = &mut v[b];
-        ptr::swap_ptr(pa, pb);
-    }
-}
-
-/// Reverse the order of elements in a vector, in place
-pub fn reverse<T>(v: &mut [T]) {
-    let mut i: uint = 0;
-    let ln = v.len();
-    while i < ln / 2 {
-        swap(v, i, ln - i - 1);
-        i += 1;
-    }
-}
-
-/**
- * Reverse part of a vector in place.
- *
- * Reverse the elements in the vector between `start` and `end - 1`.
- *
- * If either start or end do not represent valid positions in the vector, the
- * vector is returned unchanged.
- *
- * # Arguments
- *
- * * `v` - The mutable vector to be modified
- *
- * * `start` - Index of the first element of the slice
- *
- * * `end` - Index one past the final element to be reversed.
- *
- * # Example
- *
- * Assume a mutable vector `v` contains `[1,2,3,4,5]`. After the call:
- *
- * ~~~ {.rust}
- * reverse_part(v, 1, 4);
- * ~~~
- *
- * `v` now contains `[1,4,3,2,5]`.
- */
-pub fn reverse_part<T>(v: &mut [T], start: uint, end : uint) {
-    let sz = v.len();
-    if start >= sz || end > sz { return; }
-    let mut i = start;
-    let mut j = end - 1;
-    while i < j {
-        vec::swap(v, i, j);
-        i += 1;
-        j -= 1;
-    }
-}
-
 /// Returns a vector with the order of elements reversed
-pub fn reversed<T:Copy>(v: &const [T]) -> ~[T] {
+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; }
@@ -1361,99 +577,6 @@ pub fn reversed<T:Copy>(v: &const [T]) -> ~[T] {
 }
 
 /**
- * Iterates over a vector, yielding each element to a closure.
- *
- * # Arguments
- *
- * * `v` - A vector, to be iterated over
- * * `f` - A closure to do the iterating. Within this closure, return true to
- * * continue iterating, false to break.
- *
- * # Examples
- *
- * ~~~ {.rust}
- * [1,2,3].each(|&i| {
- *     io::println(int::str(i));
- *     true
- * });
- * ~~~
- *
- * ~~~ {.rust}
- * [1,2,3,4,5].each(|&i| {
- *     if i < 4 {
- *         io::println(int::str(i));
- *         true
- *     }
- *     else {
- *         false
- *     }
- * });
- * ~~~
- *
- * You probably will want to use each with a `for`/`do` expression, depending
- * on your iteration needs:
- *
- * ~~~ {.rust}
- * for [1,2,3].each |&i| {
- *     io::println(int::str(i));
- * }
- * ~~~
- */
-#[inline]
-pub fn each<'r,T>(v: &'r [T], f: &fn(&'r T) -> bool) -> bool {
-    //            ^^^^
-    // NB---this CANNOT be &const [T]!  The reason
-    // is that you are passing it to `f()` using
-    // an immutable.
-
-    let mut broke = false;
-    do as_imm_buf(v) |p, n| {
-        let mut n = n;
-        let mut p = p;
-        while n > 0u {
-            unsafe {
-                let q = cast::copy_lifetime_vec(v, &*p);
-                if !f(q) { break; }
-                p = ptr::offset(p, 1u);
-            }
-            n -= 1u;
-        }
-        broke = n > 0;
-    }
-    return !broke;
-}
-
-/// Like `each()`, but for the case where you have a vector that *may or may
-/// not* have mutable contents.
-#[inline]
-pub fn each_const<T>(v: &const [T], f: &fn(elem: &const T) -> bool) -> bool {
-    let mut i = 0;
-    let n = v.len();
-    while i < n {
-        if !f(&const v[i]) {
-            return false;
-        }
-        i += 1;
-    }
-    return true;
-}
-
-/**
- * Iterates over a vector's elements and indices
- *
- * Return true to continue, false to break.
- */
-#[inline]
-pub fn eachi<'r,T>(v: &'r [T], f: &fn(uint, v: &'r T) -> bool) -> bool {
-    let mut i = 0;
-    for each(v) |p| {
-        if !f(i, p) { return false; }
-        i += 1;
-    }
-    return true;
-}
-
-/**
  * Iterate over all permutations of vector `v`.
  *
  * Permutations are produced in lexicographic order with respect to the order
@@ -1498,8 +621,8 @@ pub fn each_permutation<T:Copy>(values: &[T], fun: &fn(perm : &[T]) -> bool) ->
         }
         // swap indices[k] and indices[l]; sort indices[k+1..]
         // (they're just reversed)
-        vec::swap(indices, k, l);
-        reverse_part(indices, k+1, length);
+        indices.swap(k, l);
+        indices.mut_slice(k+1, length).reverse();
         // fixup permutation based on indices
         for uint::range(k, length) |i| {
             permutation[i] = copy values[indices[i]];
@@ -1554,16 +677,6 @@ pub fn as_imm_buf<T,U>(s: &[T],
     }
 }
 
-/// Similar to `as_imm_buf` but passing a `*const T`
-#[inline]
-pub fn as_const_buf<T,U>(s: &const [T], f: &fn(*const T, uint) -> U) -> U {
-    unsafe {
-        let v : *(*const T,uint) = transmute(&s);
-        let (buf,len) = *v;
-        f(buf, len / sys::nonzero_size_of::<T>())
-    }
-}
-
 /// 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 {
@@ -1744,30 +857,24 @@ impl<T:Ord> Ord for @[T] {
 }
 
 #[cfg(not(test))]
-pub mod traits {
-    use kinds::Copy;
-    use ops::Add;
-    use vec::append;
-
-    impl<'self,T:Copy> Add<&'self const [T],~[T]> for ~[T] {
-        #[inline]
-        fn add(&self, rhs: & &'self const [T]) -> ~[T] {
-            append(copy *self, (*rhs))
-        }
+impl<'self,T:Copy> Add<&'self [T], ~[T]> for ~[T] {
+    #[inline]
+    fn add(&self, rhs: & &'self [T]) -> ~[T] {
+        append(copy *self, (*rhs))
     }
 }
 
-impl<'self, T> Container for &'self const [T] {
+impl<'self, T> Container for &'self [T] {
     /// Returns true if a vector contains no elements
     #[inline]
     fn is_empty(&self) -> bool {
-        as_const_buf(*self, |_p, len| len == 0u)
+        as_imm_buf(*self, |_p, len| len == 0u)
     }
 
     /// Returns the length of a vector
     #[inline]
     fn len(&self) -> uint {
-        as_const_buf(*self, |_p, len| len)
+        as_imm_buf(*self, |_p, len| len)
     }
 }
 
@@ -1775,13 +882,13 @@ impl<T> Container for ~[T] {
     /// Returns true if a vector contains no elements
     #[inline]
     fn is_empty(&self) -> bool {
-        as_const_buf(*self, |_p, len| len == 0u)
+        as_imm_buf(*self, |_p, len| len == 0u)
     }
 
     /// Returns the length of a vector
     #[inline]
     fn len(&self) -> uint {
-        as_const_buf(*self, |_p, len| len)
+        as_imm_buf(*self, |_p, len| len)
     }
 }
 
@@ -1795,13 +902,11 @@ impl<'self,T:Copy> CopyableVector<T> for &'self [T] {
     /// Returns a copy of `v`.
     #[inline]
     fn to_owned(&self) -> ~[T] {
-        let mut result = ~[];
-        reserve(&mut result, self.len());
-        for self.each |e| {
+        let mut result = with_capacity(self.len());
+        for self.iter().advance |e| {
             result.push(copy *e);
         }
         result
-
     }
 }
 
@@ -1818,14 +923,14 @@ pub trait ImmutableVector<'self, T> {
     fn initn(&self, n: uint) -> &'self [T];
     fn last(&self) -> &'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 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 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];
 }
 
 /// Extension methods for vectors
@@ -1833,7 +938,14 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
     /// Return a slice that points into another slice.
     #[inline]
     fn slice(&self, start: uint, end: uint) -> &'self [T] {
-        slice(*self, start, end)
+    assert!(start <= end);
+    assert!(end <= self.len());
+        do as_imm_buf(*self) |p, _len| {
+            unsafe {
+                transmute((ptr::offset(p, start),
+                           (end - start) * sys::nonzero_size_of::<T>()))
+            }
+        }
     }
 
     #[inline]
@@ -1856,46 +968,48 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
 
     /// Returns the first element of a vector, failing if the vector is empty.
     #[inline]
-    fn head(&self) -> &'self T { head(*self) }
+    fn head(&self) -> &'self T {
+        if self.len() == 0 { fail!("head: empty vector") }
+        &self[0]
+    }
 
-    /// Returns the first element of a vector
+    /// Returns the first element of a vector, or `None` if it is empty
     #[inline]
-    fn head_opt(&self) -> Option<&'self T> { head_opt(*self) }
+    fn head_opt(&self) -> Option<&'self T> {
+        if self.len() == 0 { None } else { Some(&self[0]) }
+    }
 
     /// Returns all but the first element of a vector
     #[inline]
-    fn tail(&self) -> &'self [T] { tail(*self) }
+    fn tail(&self) -> &'self [T] { self.slice(1, self.len()) }
 
     /// Returns all but the first `n' elements of a vector
     #[inline]
-    fn tailn(&self, n: uint) -> &'self [T] { tailn(*self, n) }
+    fn tailn(&self, n: uint) -> &'self [T] { self.slice(n, self.len()) }
 
-    /// Returns all but the last elemnt of a vector
+    /// Returns all but the last element of a vector
     #[inline]
-    fn init(&self) -> &'self [T] { init(*self) }
+    fn init(&self) -> &'self [T] {
+        self.slice(0, self.len() - 1)
+    }
 
     /// Returns all but the last `n' elemnts of a vector
     #[inline]
-    fn initn(&self, n: uint) -> &'self [T] { initn(*self, n) }
-
-    /// Returns the last element of a `v`, failing if the vector is empty.
-    #[inline]
-    fn last(&self) -> &'self T { last(*self) }
+    fn initn(&self, n: uint) -> &'self [T] {
+        self.slice(0, self.len() - n)
+    }
 
-    /// Returns the last element of a `v`, failing if the vector is empty.
+    /// Returns the last element of a vector, failing if the vector is empty.
     #[inline]
-    fn last_opt(&self) -> Option<&'self T> { last_opt(*self) }
+    fn last(&self) -> &'self T {
+        if self.len() == 0 { fail!("last: empty vector") }
+        &self[self.len() - 1]
+    }
 
-    /**
-     * Find the first index matching some predicate
-     *
-     * Apply function `f` to each element of `v`.  When function `f` returns
-     * true then an option containing the index is returned. If `f` matches no
-     * elements then none is returned.
-     */
+    /// Returns the last element of a vector, or `None` if it is empty.
     #[inline]
-    fn position(&self, f: &fn(t: &T) -> bool) -> Option<uint> {
-        position(*self, f)
+    fn last_opt(&self) -> Option<&'self T> {
+            if self.len() == 0 { None } else { Some(&self[self.len() - 1]) }
     }
 
     /**
@@ -1903,34 +1017,14 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
      *
      * Apply function `f` to each element of `v` in reverse order.  When
      * function `f` returns true then an option containing the index is
-     * returned. If `f` matches no elements then none is returned.
+     * returned. If `f` matches no elements then None is returned.
      */
     #[inline]
     fn rposition(&self, f: &fn(t: &T) -> bool) -> Option<uint> {
-        rposition(*self, f)
-    }
-
-    /// 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) }
-
-    /**
-     * Apply a function to the index and value of each element in the vector
-     * and return the results
-     */
-    fn mapi<U>(&self, f: &fn(uint, t: &T) -> U) -> ~[U] {
-        mapi(*self, f)
-    }
-
-    #[inline]
-    fn map_r<U>(&self, f: &fn(x: &T) -> U) -> ~[U] {
-        let mut r = ~[];
-        let mut i = 0;
-        while i < self.len() {
-            r.push(f(&self[i]));
-            i += 1;
+        for self.rev_iter().enumerate().advance |(i, t)| {
+            if f(t) { return Some(self.len() - i - 1); }
         }
-        r
+        None
     }
 
     /**
@@ -1959,32 +1053,90 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
         let (ptr, _): (*T, uint) = transmute(*self);
         ptr.offset(index)
     }
+
+    /**
+     * Binary search a sorted vector with a comparator function.
+     *
+     * The comparator should implement an order consistent with the sort
+     * order of the underlying vector, returning an order code that indicates
+     * whether its argument is `Less`, `Equal` or `Greater` the desired target.
+     *
+     * Returns the index where the comparator returned `Equal`, or `None` if
+     * not found.
+     */
+    fn bsearch(&self, f: &fn(&T) -> Ordering) -> Option<uint> {
+        let mut base : uint = 0;
+        let mut lim : uint = self.len();
+
+        while lim != 0 {
+            let ix = base + (lim >> 1);
+            match f(&self[ix]) {
+                Equal => return Some(ix),
+                Less => {
+                    base = ix + 1;
+                    lim -= 1;
+                }
+                Greater => ()
+            }
+            lim >>= 1;
+        }
+        return None;
+    }
+
+    /// Deprecated, use iterators where possible
+    /// (`self.iter().transform(f)`). Apply a function to each element
+    /// of a vector and return the results.
+    fn map<U>(&self, f: &fn(t: &T) -> U) -> ~[U] {
+        self.iter().transform(f).collect()
+    }
 }
 
 #[allow(missing_doc)]
 pub trait ImmutableEqVector<T:Eq> {
     fn position_elem(&self, t: &T) -> Option<uint>;
     fn rposition_elem(&self, t: &T) -> Option<uint>;
+    fn contains(&self, x: &T) -> bool;
 }
 
 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> {
-        position_elem(*self, x)
+        self.iter().position_(|y| *x == *y)
     }
 
     /// Find the last index containing a matching value
     #[inline]
     fn rposition_elem(&self, t: &T) -> Option<uint> {
-        rposition_elem(*self, t)
+        self.rposition(|x| *x == *t)
+    }
+
+    /// Return true if a vector contains an element with the given value
+    fn contains(&self, x: &T) -> bool {
+        for self.iter().advance |elt| { if *x == *elt { return true; } }
+        false
+    }
+}
+
+#[allow(missing_doc)]
+pub trait ImmutableTotalOrdVector<T: TotalOrd> {
+    fn bsearch_elem(&self, x: &T) -> Option<uint>;
+}
+
+impl<'self, T: TotalOrd> ImmutableTotalOrdVector<T> for &'self [T] {
+    /**
+     * Binary search a sorted vector for a given element.
+     *
+     * Returns the index of the element or None if not found.
+     */
+    fn bsearch_elem(&self, x: &T) -> Option<uint> {
+        self.bsearch(|p| p.cmp(x))
     }
 }
 
 #[allow(missing_doc)]
 pub trait ImmutableCopyableVector<T> {
     fn filtered(&self, f: &fn(&T) -> bool) -> ~[T];
-    fn rfind(&self, f: &fn(t: &T) -> bool) -> Option<T>;
     fn partitioned(&self, f: &fn(&T) -> bool) -> (~[T], ~[T]);
     unsafe fn unsafe_get(&self, elem: uint) -> T;
 }
@@ -2004,24 +1156,23 @@ impl<'self,T:Copy> ImmutableCopyableVector<T> for &'self [T] {
     }
 
     /**
-     * Search for the last element that matches a given predicate
-     *
-     * Apply function `f` to each element of `v` in reverse order. When
-     * function `f` returns true then an option containing the element is
-     * returned. If `f` matches no elements then none is returned.
-     */
-    #[inline]
-    fn rfind(&self, f: &fn(t: &T) -> bool) -> Option<T> {
-        rfind(*self, f)
-    }
-
-    /**
      * Partitions the vector into those that satisfies the predicate, and
      * those that do not.
      */
     #[inline]
     fn partitioned(&self, f: &fn(&T) -> bool) -> (~[T], ~[T]) {
-        partitioned(*self, f)
+        let mut lefts  = ~[];
+        let mut rights = ~[];
+
+        for self.iter().advance |elt| {
+            if f(elt) {
+                lefts.push(copy *elt);
+            } else {
+                rights.push(copy *elt);
+            }
+        }
+
+        (lefts, rights)
     }
 
     /// Returns the element at the given index, without doing bounds checking.
@@ -2033,7 +1184,13 @@ impl<'self,T:Copy> ImmutableCopyableVector<T> for &'self [T] {
 
 #[allow(missing_doc)]
 pub trait OwnedVector<T> {
+    fn reserve(&mut self, n: uint);
+    fn reserve_at_least(&mut self, n: uint);
+    fn capacity(&self) -> uint;
+
     fn push(&mut self, t: T);
+    unsafe fn push_fast(&mut self, t: T);
+
     fn push_all_move(&mut self, rhs: ~[T]);
     fn pop(&mut self) -> T;
     fn shift(&mut self) -> T;
@@ -2047,58 +1204,316 @@ pub trait OwnedVector<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: old_iter::InitOp<T>);
+    fn grow_fn(&mut self, n: uint, op: &fn(uint) -> T);
 }
 
 impl<T> OwnedVector<T> for ~[T] {
+    /**
+     * Reserves capacity for exactly `n` elements in the given vector.
+     *
+     * If the capacity for `self` is already equal to or greater than the requested
+     * capacity, then no action is taken.
+     *
+     * # Arguments
+     *
+     * * n - The number of elements to reserve space for
+     */
     #[inline]
-    fn push(&mut self, t: T) {
-        push(self, t);
+    #[cfg(stage0)]
+    fn reserve(&mut self, n: uint) {
+        // Only make the (slow) call into the runtime if we have to
+        use managed;
+        if self.capacity() < n {
+            unsafe {
+                let ptr: *mut *mut raw::VecRepr = cast::transmute(self);
+                let td = get_tydesc::<T>();
+                if ((**ptr).box_header.ref_count ==
+                    managed::raw::RC_MANAGED_UNIQUE) {
+                    // XXX transmute shouldn't be necessary
+                    let td = cast::transmute(td);
+                    ::at_vec::raw::reserve_raw(td, ptr, n);
+                } else {
+                    let alloc = n * sys::nonzero_size_of::<T>();
+                    *ptr = realloc_raw(*ptr as *mut c_void, alloc + size_of::<raw::VecRepr>())
+                           as *mut raw::VecRepr;
+                    (**ptr).unboxed.alloc = alloc;
+                }
+            }
+        }
+    }
+
+    /**
+     * Reserves capacity for exactly `n` elements in the given vector.
+     *
+     * If the capacity for `self` is already equal to or greater than the requested
+     * capacity, then no action is taken.
+     *
+     * # Arguments
+     *
+     * * n - The number of elements to reserve space for
+     */
+    #[inline]
+    #[cfg(not(stage0))]
+    fn reserve(&mut self, n: uint) {
+        // Only make the (slow) call into the runtime if we have to
+        if self.capacity() < n {
+            unsafe {
+                let ptr: *mut *mut raw::VecRepr = cast::transmute(self);
+                let td = get_tydesc::<T>();
+                if contains_managed::<T>() {
+                    ::at_vec::raw::reserve_raw(td, ptr, n);
+                } else {
+                    let alloc = n * sys::nonzero_size_of::<T>();
+                    *ptr = realloc_raw(*ptr as *mut c_void, alloc + size_of::<raw::VecRepr>())
+                           as *mut raw::VecRepr;
+                    (**ptr).unboxed.alloc = alloc;
+                }
+            }
+        }
+    }
+
+    /**
+     * Reserves capacity for at least `n` elements in the given vector.
+     *
+     * This function will over-allocate in order to amortize the allocation costs
+     * in scenarios where the caller may need to repeatedly reserve additional
+     * space.
+     *
+     * If the capacity for `self` is already equal to or greater than the requested
+     * capacity, then no action is taken.
+     *
+     * # Arguments
+     *
+     * * n - The number of elements to reserve space for
+     */
+    fn reserve_at_least(&mut self, n: uint) {
+        self.reserve(uint::next_power_of_two(n));
     }
 
+    /// Returns the number of elements the vector can hold without reallocating.
     #[inline]
-    fn push_all_move(&mut self, rhs: ~[T]) {
-        push_all_move(self, rhs);
+    fn capacity(&self) -> uint {
+        unsafe {
+            let repr: **raw::VecRepr = transmute(self);
+            (**repr).unboxed.alloc / sys::nonzero_size_of::<T>()
+        }
     }
 
+    /// Append an element to a vector
     #[inline]
+    fn push(&mut self, t: T) {
+        unsafe {
+            let repr: **raw::VecRepr = transmute(&mut *self);
+            let fill = (**repr).unboxed.fill;
+            if (**repr).unboxed.alloc <= fill {
+                // need more space
+                reserve_no_inline(self);
+            }
+
+            self.push_fast(t);
+        }
+
+        // this peculiar function is because reserve_at_least is very
+        // large (because of reserve), and will be inlined, which
+        // makes push too large.
+        #[inline(never)]
+        fn reserve_no_inline<T>(v: &mut ~[T]) {
+            let new_len = v.len() + 1;
+            v.reserve_at_least(new_len);
+        }
+    }
+
+    // This doesn't bother to make sure we have space.
+    #[inline] // really pretty please
+    unsafe fn push_fast(&mut self, t: T) {
+        let repr: **mut raw::VecRepr = transmute(self);
+        let fill = (**repr).unboxed.fill;
+        (**repr).unboxed.fill += sys::nonzero_size_of::<T>();
+        let p = to_unsafe_ptr(&((**repr).unboxed.data));
+        let p = ptr::offset(p, fill) as *mut T;
+        intrinsics::move_val_init(&mut(*p), t);
+    }
+
+    /// Takes ownership of the vector `rhs`, moving all elements into
+    /// the current vector. This does not copy any elements, and it is
+    /// illegal to use the `rhs` vector after calling this method
+    /// (because it is moved here).
+    ///
+    /// # Example
+    ///
+    /// ~~~ {.rust}
+    /// let mut a = ~[~1];
+    /// a.push_all_move(~[~2, ~3, ~4]);
+    /// assert!(a == ~[~1, ~2, ~3, ~4]);
+    /// ~~~
+    #[inline]
+    fn push_all_move(&mut self, mut rhs: ~[T]) {
+        let new_len = self.len() + rhs.len();
+        self.reserve(new_len);
+        unsafe {
+            do as_mut_buf(rhs) |p, len| {
+                for uint::range(0, len) |i| {
+                    let x = ptr::replace_ptr(ptr::mut_offset(p, i),
+                                             intrinsics::uninit());
+                    self.push(x);
+                }
+            }
+            raw::set_len(&mut rhs, 0);
+        }
+    }
+
+    /// Remove the last element from a vector and return it
     fn pop(&mut self) -> T {
-        pop(self)
+        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
+        }
     }
 
-    #[inline]
+    /// Removes the first element from a vector and return it
     fn shift(&mut self) -> T {
-        shift(self)
+        unsafe {
+            assert!(!self.is_empty());
+
+            if self.len() == 1 { return self.pop() }
+
+            if self.len() == 2 {
+                let last = self.pop();
+                let first = self.pop();
+                self.push(last);
+                return first;
+            }
+
+            let ln = self.len();
+            let next_ln = self.len() - 1;
+
+            // Save the last element. We're going to overwrite its position
+            let work_elt = self.pop();
+            // We still should have room to work where what last element was
+            assert!(self.capacity() >= ln);
+            // Pretend like we have the original length so we can use
+            // the vector copy_memory to overwrite the hole we just made
+            raw::set_len(self, ln);
+
+            // Memcopy the head element (the one we want) to the location we just
+            // popped. For the moment it unsafely exists at both the head and last
+            // positions
+            {
+                let first_slice = self.slice(0, 1);
+                let last_slice = self.slice(next_ln, ln);
+                raw::copy_memory(transmute(last_slice), first_slice, 1);
+            }
+
+            // Memcopy everything to the left one element
+            {
+                let init_slice = self.slice(0, next_ln);
+                let tail_slice = self.slice(1, ln);
+                raw::copy_memory(transmute(init_slice),
+                                 tail_slice,
+                                 next_ln);
+            }
+
+            // Set the new length. Now the vector is back to normal
+            raw::set_len(self, next_ln);
+
+            // Swap out the element we want from the end
+            let vp = raw::to_mut_ptr(*self);
+            let vp = ptr::mut_offset(vp, next_ln - 1);
+
+            ptr::replace_ptr(vp, work_elt)
+        }
     }
 
-    #[inline]
+    /// Prepend an element to the vector
     fn unshift(&mut self, x: T) {
-        unshift(self, x)
+        let v = util::replace(self, ~[x]);
+        self.push_all_move(v);
     }
 
-    #[inline]
+    /// Insert an element at position i within v, shifting all
+    /// elements after position i one position to the right.
     fn insert(&mut self, i: uint, x:T) {
-        insert(self, i, x)
+        let len = self.len();
+        assert!(i <= len);
+
+        self.push(x);
+        let mut j = len;
+        while j > i {
+            self.swap(j, j - 1);
+            j -= 1;
+        }
     }
 
-    #[inline]
+    /// Remove and return the element at position i within v, shifting
+    /// all elements after position i one position to the left.
     fn remove(&mut self, i: uint) -> T {
-        remove(self, i)
+        let len = self.len();
+        assert!(i < len);
+
+        let mut j = i;
+        while j < len - 1 {
+            self.swap(j, j + 1);
+            j += 1;
+        }
+        self.pop()
     }
 
-    #[inline]
+    /**
+     * Remove an element from anywhere in the vector and return it, replacing it
+     * with the last element. This does not preserve ordering, but is O(1).
+     *
+     * Fails if index >= length.
+     */
     fn swap_remove(&mut self, index: uint) -> T {
-        swap_remove(self, index)
+        let ln = self.len();
+        if index >= ln {
+            fail!("vec::swap_remove - index %u >= length %u", index, ln);
+        }
+        if index < ln - 1 {
+            self.swap(index, ln - 1);
+        }
+        self.pop()
     }
 
-    #[inline]
+    /// Shorten a vector, dropping excess elements.
     fn truncate(&mut self, newlen: uint) {
-        truncate(self, newlen);
+        do as_mut_buf(*self) |p, oldlen| {
+            assert!(newlen <= oldlen);
+            unsafe {
+                // This loop is optimized out for non-drop types.
+                for uint::range(newlen, oldlen) |i| {
+                    ptr::replace_ptr(ptr::mut_offset(p, i), intrinsics::uninit());
+                }
+            }
+        }
+        unsafe { raw::set_len(self, newlen); }
     }
 
-    #[inline]
+
+    /**
+     * Like `filter()`, but in place.  Preserves order of `v`.  Linear time.
+     */
     fn retain(&mut self, f: &fn(t: &T) -> bool) {
-        retain(self, f);
+        let len = self.len();
+        let mut deleted: uint = 0;
+
+        for uint::range(0, len) |i| {
+            if !f(&self[i]) {
+                deleted += 1;
+            } else if deleted > 0 {
+                self.swap(i - deleted, i);
+            }
+        }
+
+        if deleted > 0 {
+            self.truncate(len - deleted);
+        }
     }
 
     #[inline]
@@ -2122,12 +1537,40 @@ impl<T> OwnedVector<T> for ~[T] {
      */
     #[inline]
     fn partition(self, f: &fn(&T) -> bool) -> (~[T], ~[T]) {
-        partition(self, f)
+        let mut lefts  = ~[];
+        let mut rights = ~[];
+
+        do self.consume |_, elt| {
+            if f(&elt) {
+                lefts.push(elt);
+            } else {
+                rights.push(elt);
+            }
+        }
+
+        (lefts, rights)
     }
 
-    #[inline]
-    fn grow_fn(&mut self, n: uint, op: old_iter::InitOp<T>) {
-        grow_fn(self, n, op);
+    /**
+     * Expands a vector in place, initializing the new elements to the result of
+     * a function
+     *
+     * Function `init_op` is called `n` times with the values [0..`n`)
+     *
+     * # Arguments
+     *
+     * * n - The number of elements to add
+     * * init_op - A function to call to retreive each appended element's
+     *             value
+     */
+    fn grow_fn(&mut self, n: uint, op: &fn(uint) -> T) {
+        let new_len = self.len() + n;
+        self.reserve_at_least(new_len);
+        let mut i: uint = 0u;
+        while i < n {
+            self.push(op(i));
+            i += 1u;
+        }
     }
 }
 
@@ -2138,37 +1581,105 @@ impl<T> Mutable for ~[T] {
 
 #[allow(missing_doc)]
 pub trait OwnedCopyableVector<T:Copy> {
-    fn push_all(&mut self, rhs: &const [T]);
+    fn push_all(&mut self, rhs: &[T]);
     fn grow(&mut self, n: uint, initval: &T);
     fn grow_set(&mut self, index: uint, initval: &T, val: T);
 }
 
 impl<T:Copy> OwnedCopyableVector<T> for ~[T] {
+    /// Iterates over the slice `rhs`, copies each element, and then appends it to
+    /// the vector provided `v`. The `rhs` vector is traversed in-order.
+    ///
+    /// # Example
+    ///
+    /// ~~~ {.rust}
+    /// let mut a = ~[1];
+    /// a.push_all([2, 3, 4]);
+    /// assert!(a == ~[1, 2, 3, 4]);
+    /// ~~~
     #[inline]
-    fn push_all(&mut self, rhs: &const [T]) {
-        push_all(self, rhs);
+    fn push_all(&mut self, rhs: &[T]) {
+        let new_len = self.len() + rhs.len();
+        self.reserve(new_len);
+
+        for uint::range(0u, rhs.len()) |i| {
+            self.push(unsafe { raw::get(rhs, i) })
+        }
     }
 
-    #[inline]
+    /**
+     * Expands a vector in place, initializing the new elements to a given value
+     *
+     * # Arguments
+     *
+     * * n - The number of elements to add
+     * * initval - The value for the new elements
+     */
     fn grow(&mut self, n: uint, initval: &T) {
-        grow(self, n, initval);
+        let new_len = self.len() + n;
+        self.reserve_at_least(new_len);
+        let mut i: uint = 0u;
+
+        while i < n {
+            self.push(copy *initval);
+            i += 1u;
+        }
     }
 
-    #[inline]
+    /**
+     * Sets the value of a vector element at a given index, growing the vector as
+     * needed
+     *
+     * Sets the element at position `index` to `val`. If `index` is past the end
+     * of the vector, expands the vector by replicating `initval` to fill the
+     * intervening space.
+     */
     fn grow_set(&mut self, index: uint, initval: &T, val: T) {
-        grow_set(self, index, initval, val);
+        let l = self.len();
+        if index >= l { self.grow(index - l + 1u, initval); }
+        self[index] = val;
     }
 }
 
 #[allow(missing_doc)]
-trait OwnedEqVector<T:Eq> {
+pub trait OwnedEqVector<T:Eq> {
     fn dedup(&mut self);
 }
 
 impl<T:Eq> OwnedEqVector<T> for ~[T] {
-    #[inline]
-    fn dedup(&mut self) {
-        dedup(self)
+    /**
+     * Remove consecutive repeated elements from a vector; if the vector is
+     * sorted, this removes all duplicates.
+     */
+    pub fn dedup(&mut self) {
+        unsafe {
+            if self.len() == 0 { return; }
+            let mut last_written = 0;
+            let mut next_to_read = 1;
+            do as_mut_buf(*self) |p, ln| {
+                // last_written < next_to_read <= ln
+                while next_to_read < ln {
+                    // last_written < next_to_read < ln
+                    if *ptr::mut_offset(p, next_to_read) ==
+                        *ptr::mut_offset(p, last_written) {
+                        ptr::replace_ptr(ptr::mut_offset(p, next_to_read),
+                                         intrinsics::uninit());
+                    } else {
+                        last_written += 1;
+                        // last_written <= next_to_read < ln
+                        if next_to_read != last_written {
+                            ptr::swap_ptr(ptr::mut_offset(p, last_written),
+                                          ptr::mut_offset(p, next_to_read));
+                        }
+                    }
+                    // last_written <= next_to_read < ln
+                    next_to_read += 1;
+                    // last_written < next_to_read <= ln
+                }
+            }
+            // last_written < next_to_read == ln
+            raw::set_len(self, last_written + 1);
+        }
     }
 }
 
@@ -2178,14 +1689,41 @@ pub trait MutableVector<'self, T> {
     fn mut_iter(self) -> VecMutIterator<'self, T>;
     fn mut_rev_iter(self) -> VecMutRevIterator<'self, T>;
 
+    fn swap(self, a: uint, b: uint);
+
+    fn reverse(self);
+
+    /**
+     * Consumes `src` and moves as many elements as it can into `self`
+     * from the range [start,end).
+     *
+     * Returns the number of elements copied (the shorter of self.len()
+     * and end - start).
+     *
+     * # Arguments
+     *
+     * * src - A mutable vector of `T`
+     * * start - The index into `src` to start copying from
+     * * end - The index into `str` to stop copying from
+     */
+    fn move_from(self, src: ~[T], start: uint, end: uint) -> uint;
+
     unsafe fn unsafe_mut_ref(&self, index: uint) -> *mut T;
     unsafe fn unsafe_set(&self, index: uint, val: T);
 }
 
 impl<'self,T> MutableVector<'self, T> for &'self mut [T] {
+    /// Return a slice that points into another slice.
     #[inline]
     fn mut_slice(self, start: uint, end: uint) -> &'self mut [T] {
-        mut_slice(self, start, end)
+        assert!(start <= end);
+        assert!(end <= self.len());
+        do as_mut_buf(self) |p, _len| {
+            unsafe {
+                transmute((ptr::mut_offset(p, start),
+                           (end - start) * sys::nonzero_size_of::<T>()))
+            }
+        }
     }
 
     #[inline]
@@ -2206,6 +1744,42 @@ impl<'self,T> MutableVector<'self, T> for &'self mut [T] {
         }
     }
 
+    /**
+     * Swaps two elements in a vector
+     *
+     * # Arguments
+     *
+     * * a - The index of the first element
+     * * b - The index of the second element
+     */
+    fn swap(self, a: uint, b: uint) {
+        unsafe {
+            // Can't take two mutable loans from one vector, so instead just cast
+            // them to their raw pointers to do the swap
+            let pa: *mut T = &mut self[a];
+            let pb: *mut T = &mut self[b];
+            ptr::swap_ptr(pa, pb);
+        }
+    }
+
+    /// Reverse the order of elements in a vector, in place
+    fn reverse(self) {
+        let mut i: uint = 0;
+        let ln = self.len();
+        while i < ln / 2 {
+            self.swap(i, ln - i - 1);
+            i += 1;
+        }
+    }
+
+    #[inline]
+    fn move_from(self, mut src: ~[T], start: uint, end: uint) -> uint {
+        for self.mut_iter().zip(src.mut_slice(start, end).mut_iter()).advance |(a, b)| {
+            util::swap(a, b);
+        }
+        cmp::min(self.len(), end-start)
+    }
+
     #[inline]
     unsafe fn unsafe_mut_ref(&self, index: uint) -> *mut T {
         let pair_ptr: &(*mut T, uint) = transmute(self);
@@ -2219,6 +1793,23 @@ impl<'self,T> MutableVector<'self, T> for &'self mut [T] {
     }
 }
 
+/// Trait for ~[T] where T is Cloneable
+pub trait MutableCloneableVector<T> {
+    /// Copies as many elements from `src` as it can into `self`
+    /// (the shorter of self.len() and src.len()). Returns the number of elements copied.
+    fn copy_from(self, &[T]) -> uint;
+}
+
+impl<'self, T:Clone> MutableCloneableVector<T> for &'self mut [T] {
+    #[inline]
+    fn copy_from(self, src: &[T]) -> uint {
+        for self.mut_iter().zip(src.iter()).advance |(a, b)| {
+            *a = b.clone();
+        }
+        cmp::min(self.len(), src.len())
+    }
+}
+
 /**
 * Constructs a vector from an unsafe pointer to a buffer
 *
@@ -2249,7 +1840,7 @@ pub mod raw {
     use ptr;
     use sys;
     use unstable::intrinsics;
-    use vec::{UnboxedVecRepr, as_const_buf, as_mut_buf, with_capacity};
+    use vec::{UnboxedVecRepr, as_imm_buf, as_mut_buf, with_capacity};
     use util;
 
     /// The internal representation of a (boxed) vector
@@ -2299,15 +1890,6 @@ pub mod raw {
 
     /** see `to_ptr()` */
     #[inline]
-    pub fn to_const_ptr<T>(v: &const [T]) -> *const T {
-        unsafe {
-            let repr: **SliceRepr = transmute(&v);
-            transmute(&((**repr).data))
-        }
-    }
-
-    /** see `to_ptr()` */
-    #[inline]
     pub fn to_mut_ptr<T>(v: &mut [T]) -> *mut T {
         unsafe {
             let repr: **SliceRepr = transmute(&v);
@@ -2345,8 +1927,8 @@ pub mod raw {
      * Unchecked vector indexing.
      */
     #[inline]
-    pub unsafe fn get<T:Copy>(v: &const [T], i: uint) -> T {
-        as_const_buf(v, |p, _len| copy *ptr::const_offset(p, i))
+    pub unsafe fn get<T:Copy>(v: &[T], i: uint) -> T {
+        as_imm_buf(v, |p, _len| copy *ptr::offset(p, i))
     }
 
     /**
@@ -2388,13 +1970,13 @@ pub mod raw {
       * may overlap.
       */
     #[inline]
-    pub unsafe fn copy_memory<T>(dst: &mut [T], src: &const [T],
+    pub unsafe fn copy_memory<T>(dst: &mut [T], src: &[T],
                                  count: uint) {
         assert!(dst.len() >= count);
         assert!(src.len() >= count);
 
         do as_mut_buf(dst) |p_dst, _len_dst| {
-            do as_const_buf(src) |p_src, _len_src| {
+            do as_imm_buf(src) |p_src, _len_src| {
                 ptr::copy_memory(p_dst, p_src, count)
             }
         }
@@ -2407,6 +1989,22 @@ pub mod bytes {
     use uint;
     use vec::raw;
     use vec;
+    use ptr;
+
+    /// A trait for operations on mutable operations on `[u8]`
+    pub trait MutableByteVector {
+        /// Sets all bytes of the receiver to the given value.
+        pub fn set_memory(self, value: u8);
+    }
+
+    impl<'self> MutableByteVector for &'self mut [u8] {
+        #[inline]
+        fn set_memory(self, value: u8) {
+            do vec::as_mut_buf(self) |p, len| {
+                unsafe { ptr::set_memory(p, value, len) };
+            }
+        }
+    }
 
     /// Bytewise string comparison
     pub fn memcmp(a: &~[u8], b: &~[u8]) -> int {
@@ -2454,174 +2052,16 @@ pub mod bytes {
       * may overlap.
       */
     #[inline]
-    pub fn copy_memory(dst: &mut [u8], src: &const [u8], count: uint) {
+    pub fn copy_memory(dst: &mut [u8], src: &[u8], count: uint) {
         // Bound checks are done at vec::raw::copy_memory.
         unsafe { vec::raw::copy_memory(dst, src, count) }
     }
 }
 
-// ___________________________________________________________________________
-// ITERATION TRAIT METHODS
-
-impl<'self,A> old_iter::BaseIter<A> for &'self [A] {
-    #[inline]
-    fn each<'a>(&'a self, blk: &fn(v: &'a A) -> bool) -> bool {
-        each(*self, blk)
-    }
-    #[inline]
-    fn size_hint(&self) -> Option<uint> { Some(self.len()) }
-}
-
-// FIXME(#4148): This should be redundant
-impl<A> old_iter::BaseIter<A> for ~[A] {
-    #[inline]
-    fn each<'a>(&'a self, blk: &fn(v: &'a A) -> bool) -> bool {
-        each(*self, blk)
-    }
-    #[inline]
-    fn size_hint(&self) -> Option<uint> { Some(self.len()) }
-}
-
-// FIXME(#4148): This should be redundant
-impl<A> old_iter::BaseIter<A> for @[A] {
-    #[inline]
-    fn each<'a>(&'a self, blk: &fn(v: &'a A) -> bool) -> bool {
-        each(*self, blk)
-    }
-    #[inline]
-    fn size_hint(&self) -> Option<uint> { Some(self.len()) }
-}
-
-impl<'self,A> old_iter::ExtendedIter<A> for &'self [A] {
-    pub fn eachi(&self, blk: &fn(uint, v: &A) -> bool) -> bool {
-        old_iter::eachi(self, blk)
-    }
-    pub fn all(&self, blk: &fn(&A) -> bool) -> bool {
-        old_iter::all(self, blk)
-    }
-    pub fn any(&self, blk: &fn(&A) -> bool) -> bool {
-        old_iter::any(self, blk)
-    }
-    pub fn foldl<B>(&self, b0: B, blk: &fn(&B, &A) -> B) -> B {
-        old_iter::foldl(self, b0, blk)
-    }
-    pub fn position(&self, f: &fn(&A) -> bool) -> Option<uint> {
-        old_iter::position(self, f)
-    }
-    fn map_to_vec<B>(&self, op: &fn(&A) -> B) -> ~[B] {
-        old_iter::map_to_vec(self, op)
-    }
-    fn flat_map_to_vec<B,IB:BaseIter<B>>(&self, op: &fn(&A) -> IB)
-        -> ~[B] {
-        old_iter::flat_map_to_vec(self, op)
-    }
-}
-
-// FIXME(#4148): This should be redundant
-impl<A> old_iter::ExtendedIter<A> for ~[A] {
-    pub fn eachi(&self, blk: &fn(uint, v: &A) -> bool) -> bool {
-        old_iter::eachi(self, blk)
-    }
-    pub fn all(&self, blk: &fn(&A) -> bool) -> bool {
-        old_iter::all(self, blk)
-    }
-    pub fn any(&self, blk: &fn(&A) -> bool) -> bool {
-        old_iter::any(self, blk)
-    }
-    pub fn foldl<B>(&self, b0: B, blk: &fn(&B, &A) -> B) -> B {
-        old_iter::foldl(self, b0, blk)
-    }
-    pub fn position(&self, f: &fn(&A) -> bool) -> Option<uint> {
-        old_iter::position(self, f)
-    }
-    fn map_to_vec<B>(&self, op: &fn(&A) -> B) -> ~[B] {
-        old_iter::map_to_vec(self, op)
-    }
-    fn flat_map_to_vec<B,IB:BaseIter<B>>(&self, op: &fn(&A) -> IB)
-        -> ~[B] {
-        old_iter::flat_map_to_vec(self, op)
-    }
-}
-
-// FIXME(#4148): This should be redundant
-impl<A> old_iter::ExtendedIter<A> for @[A] {
-    pub fn eachi(&self, blk: &fn(uint, v: &A) -> bool) -> bool {
-        old_iter::eachi(self, blk)
-    }
-    pub fn all(&self, blk: &fn(&A) -> bool) -> bool {
-        old_iter::all(self, blk)
-    }
-    pub fn any(&self, blk: &fn(&A) -> bool) -> bool {
-        old_iter::any(self, blk)
-    }
-    pub fn foldl<B>(&self, b0: B, blk: &fn(&B, &A) -> B) -> B {
-        old_iter::foldl(self, b0, blk)
-    }
-    pub fn position(&self, f: &fn(&A) -> bool) -> Option<uint> {
-        old_iter::position(self, f)
-    }
-    fn map_to_vec<B>(&self, op: &fn(&A) -> B) -> ~[B] {
-        old_iter::map_to_vec(self, op)
-    }
-    fn flat_map_to_vec<B,IB:BaseIter<B>>(&self, op: &fn(&A) -> IB)
-        -> ~[B] {
-        old_iter::flat_map_to_vec(self, op)
-    }
-}
-
-impl<'self,A:Eq> old_iter::EqIter<A> for &'self [A] {
-    pub fn contains(&self, x: &A) -> bool { old_iter::contains(self, x) }
-    pub fn count(&self, x: &A) -> uint { old_iter::count(self, x) }
-}
-
-// FIXME(#4148): This should be redundant
-impl<A:Eq> old_iter::EqIter<A> for ~[A] {
-    pub fn contains(&self, x: &A) -> bool { old_iter::contains(self, x) }
-    pub fn count(&self, x: &A) -> uint { old_iter::count(self, x) }
-}
-
-// FIXME(#4148): This should be redundant
-impl<A:Eq> old_iter::EqIter<A> for @[A] {
-    pub fn contains(&self, x: &A) -> bool { old_iter::contains(self, x) }
-    pub fn count(&self, x: &A) -> uint { old_iter::count(self, x) }
-}
-
-impl<'self,A:Copy> old_iter::CopyableIter<A> for &'self [A] {
-    fn filter_to_vec(&self, pred: &fn(&A) -> bool) -> ~[A] {
-        old_iter::filter_to_vec(self, pred)
-    }
-    fn to_vec(&self) -> ~[A] { old_iter::to_vec(self) }
-    pub fn find(&self, f: &fn(&A) -> bool) -> Option<A> {
-        old_iter::find(self, f)
-    }
-}
-
-// FIXME(#4148): This should be redundant
-impl<A:Copy> old_iter::CopyableIter<A> for ~[A] {
-    fn filter_to_vec(&self, pred: &fn(&A) -> bool) -> ~[A] {
-        old_iter::filter_to_vec(self, pred)
-    }
-    fn to_vec(&self) -> ~[A] { old_iter::to_vec(self) }
-    pub fn find(&self, f: &fn(&A) -> bool) -> Option<A> {
-        old_iter::find(self, f)
-    }
-}
-
-// FIXME(#4148): This should be redundant
-impl<A:Copy> old_iter::CopyableIter<A> for @[A] {
-    fn filter_to_vec(&self, pred: &fn(&A) -> bool) -> ~[A] {
-        old_iter::filter_to_vec(self, pred)
-    }
-    fn to_vec(&self) -> ~[A] { old_iter::to_vec(self) }
-    pub fn find(&self, f: &fn(&A) -> bool) -> Option<A> {
-        old_iter::find(self, f)
-    }
-}
-
 impl<A:Clone> Clone for ~[A] {
     #[inline]
     fn clone(&self) -> ~[A] {
-        self.map(|item| item.clone())
+        self.iter().transform(|item| item.clone()).collect()
     }
 }
 
@@ -2665,6 +2105,12 @@ 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)
+            }
         }
     }
 }
@@ -2714,6 +2160,31 @@ impl<T> FromIter<T> for ~[T]{
     }
 }
 
+#[cfg(stage0)]
+impl<A, T: Iterator<A>> FromIterator<A, T> for ~[A] {
+    pub fn from_iterator(iterator: &mut T) -> ~[A] {
+        let mut xs = ~[];
+        for iterator.advance |x| {
+            xs.push(x);
+        }
+        xs
+    }
+}
+
+
+#[cfg(not(stage0))]
+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());
+        for iterator.advance |x| {
+            xs.push(x);
+        }
+        xs
+    }
+}
+
+
 #[cfg(test)]
 mod tests {
     use option::{None, Option, Some};
@@ -2942,7 +2413,7 @@ mod tests {
     fn test_slice() {
         // Test fixed length vector.
         let vec_fixed = [1, 2, 3, 4];
-        let v_a = slice(vec_fixed, 1u, vec_fixed.len()).to_vec();
+        let v_a = vec_fixed.slice(1u, vec_fixed.len()).to_owned();
         assert_eq!(v_a.len(), 3u);
         assert_eq!(v_a[0], 2);
         assert_eq!(v_a[1], 3);
@@ -2950,14 +2421,14 @@ mod tests {
 
         // Test on stack.
         let vec_stack = &[1, 2, 3];
-        let v_b = slice(vec_stack, 1u, 3u).to_vec();
+        let v_b = vec_stack.slice(1u, 3u).to_owned();
         assert_eq!(v_b.len(), 2u);
         assert_eq!(v_b[0], 2);
         assert_eq!(v_b[1], 3);
 
         // Test on managed heap.
         let vec_managed = @[1, 2, 3, 4, 5];
-        let v_c = slice(vec_managed, 0u, 3u).to_vec();
+        let v_c = vec_managed.slice(0u, 3u).to_owned();
         assert_eq!(v_c.len(), 3u);
         assert_eq!(v_c[0], 1);
         assert_eq!(v_c[1], 2);
@@ -2965,7 +2436,7 @@ mod tests {
 
         // Test on exchange heap.
         let vec_unique = ~[1, 2, 3, 4, 5, 6];
-        let v_d = slice(vec_unique, 1u, 6u).to_vec();
+        let v_d = vec_unique.slice(1u, 6u).to_owned();
         assert_eq!(v_d.len(), 5u);
         assert_eq!(v_d[0], 2);
         assert_eq!(v_d[1], 3);
@@ -3137,16 +2608,16 @@ mod tests {
     #[test]
     fn test_map() {
         // Test on-stack map.
-        let mut v = ~[1u, 2u, 3u];
-        let mut w = map(v, square_ref);
+        let v = &[1u, 2u, 3u];
+        let mut w = v.map(square_ref);
         assert_eq!(w.len(), 3u);
         assert_eq!(w[0], 1u);
         assert_eq!(w[1], 4u);
         assert_eq!(w[2], 9u);
 
         // Test on-heap map.
-        v = ~[1u, 2u, 3u, 4u, 5u];
-        w = map(v, square_ref);
+        let v = ~[1u, 2u, 3u, 4u, 5u];
+        w = v.map(square_ref);
         assert_eq!(w.len(), 5u);
         assert_eq!(w[0], 1u);
         assert_eq!(w[1], 4u);
@@ -3156,17 +2627,6 @@ mod tests {
     }
 
     #[test]
-    fn test_map_zip() {
-        fn times(x: &int, y: &int) -> int { *x * *y }
-        let f = times;
-        let v0 = ~[1, 2, 3, 4, 5];
-        let v1 = ~[5, 4, 3, 2, 1];
-        let u = map_zip::<int, int, int>(v0, v1, f);
-        let mut i = 0;
-        while i < 5 { assert!(v0[i] * v1[i] == u[i]); i += 1; }
-    }
-
-    #[test]
     fn test_filter_mapped() {
         // Test on-stack filter-map.
         let mut v = ~[1u, 2u, 3u];
@@ -3197,7 +2657,7 @@ mod tests {
         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) ==
-                     map(all_even, halve_for_sure));
+                     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);
@@ -3235,7 +2695,7 @@ mod tests {
         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) ==
-                     map(all_even0, halve_for_sure));
+                     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);
@@ -3255,47 +2715,6 @@ mod tests {
     }
 
     #[test]
-    fn test_each_empty() {
-        for each::<int>([]) |_v| {
-            fail!(); // should never be executed
-        }
-    }
-
-    #[test]
-    fn test_each_nonempty() {
-        let mut i = 0;
-        for each([1, 2, 3]) |v| {
-            i += *v;
-        }
-        assert_eq!(i, 6);
-    }
-
-    #[test]
-    fn test_eachi() {
-        let mut i = 0;
-        for eachi([1, 2, 3]) |j, v| {
-            if i == 0 { assert!(*v == 1); }
-            assert_eq!(j + 1u, *v as uint);
-            i += *v;
-        }
-        assert_eq!(i, 6);
-    }
-
-    #[test]
-    fn test_each_ret_len0() {
-        let a0 : [int, .. 0] = [];
-        assert_eq!(each(a0, |_p| fail!()), true);
-    }
-
-    #[test]
-    fn test_each_ret_len1() {
-        let a1 = [17];
-        assert_eq!(each(a1, |_p| true), true);
-        assert_eq!(each(a1, |_p| false), false);
-    }
-
-
-    #[test]
     fn test_each_permutation() {
         let mut results: ~[~[int]];
 
@@ -3337,218 +2756,68 @@ mod tests {
 
     #[test]
     fn test_position_elem() {
-        assert!(position_elem([], &1).is_none());
+        assert!([].position_elem(&1).is_none());
 
         let v1 = ~[1, 2, 3, 3, 2, 5];
-        assert_eq!(position_elem(v1, &1), Some(0u));
-        assert_eq!(position_elem(v1, &2), Some(1u));
-        assert_eq!(position_elem(v1, &5), Some(5u));
-        assert!(position_elem(v1, &4).is_none());
-    }
-
-    #[test]
-    fn test_position() {
-        fn less_than_three(i: &int) -> bool { *i < 3 }
-        fn is_eighteen(i: &int) -> bool { *i == 18 }
-
-        assert!(position([], less_than_three).is_none());
-
-        let v1 = ~[5, 4, 3, 2, 1];
-        assert_eq!(position(v1, less_than_three), Some(3u));
-        assert!(position(v1, is_eighteen).is_none());
-    }
-
-    #[test]
-    fn test_position_between() {
-        assert!(position_between([], 0u, 0u, f).is_none());
-
-        fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' }
-        let v = ~[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
-
-        assert!(position_between(v, 0u, 0u, f).is_none());
-        assert!(position_between(v, 0u, 1u, f).is_none());
-        assert_eq!(position_between(v, 0u, 2u, f), Some(1u));
-        assert_eq!(position_between(v, 0u, 3u, f), Some(1u));
-        assert_eq!(position_between(v, 0u, 4u, f), Some(1u));
-
-        assert!(position_between(v, 1u, 1u, f).is_none());
-        assert_eq!(position_between(v, 1u, 2u, f), Some(1u));
-        assert_eq!(position_between(v, 1u, 3u, f), Some(1u));
-        assert_eq!(position_between(v, 1u, 4u, f), Some(1u));
-
-        assert!(position_between(v, 2u, 2u, f).is_none());
-        assert!(position_between(v, 2u, 3u, f).is_none());
-        assert_eq!(position_between(v, 2u, 4u, f), Some(3u));
-
-        assert!(position_between(v, 3u, 3u, f).is_none());
-        assert_eq!(position_between(v, 3u, 4u, f), Some(3u));
-
-        assert!(position_between(v, 4u, 4u, f).is_none());
-    }
-
-    #[test]
-    fn test_find() {
-        assert!(find([], f).is_none());
-
-        fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' }
-        fn g(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'd' }
-        let v = ~[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
-
-        assert_eq!(find(v, f), Some((1, 'b')));
-        assert!(find(v, g).is_none());
-    }
-
-    #[test]
-    fn test_find_between() {
-        assert!(find_between([], 0u, 0u, f).is_none());
-
-        fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' }
-        let v = ~[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
-
-        assert!(find_between(v, 0u, 0u, f).is_none());
-        assert!(find_between(v, 0u, 1u, f).is_none());
-        assert_eq!(find_between(v, 0u, 2u, f), Some((1, 'b')));
-        assert_eq!(find_between(v, 0u, 3u, f), Some((1, 'b')));
-        assert_eq!(find_between(v, 0u, 4u, f), Some((1, 'b')));
-
-        assert!(find_between(v, 1u, 1u, f).is_none());
-        assert_eq!(find_between(v, 1u, 2u, f), Some((1, 'b')));
-        assert_eq!(find_between(v, 1u, 3u, f), Some((1, 'b')));
-        assert_eq!(find_between(v, 1u, 4u, f), Some((1, 'b')));
-
-        assert!(find_between(v, 2u, 2u, f).is_none());
-        assert!(find_between(v, 2u, 3u, f).is_none());
-        assert_eq!(find_between(v, 2u, 4u, f), Some((3, 'b')));
-
-        assert!(find_between(v, 3u, 3u, f).is_none());
-        assert_eq!(find_between(v, 3u, 4u, f), Some((3, 'b')));
-
-        assert!(find_between(v, 4u, 4u, f).is_none());
+        assert_eq!(v1.position_elem(&1), Some(0u));
+        assert_eq!(v1.position_elem(&2), Some(1u));
+        assert_eq!(v1.position_elem(&5), Some(5u));
+        assert!(v1.position_elem(&4).is_none());
     }
 
     #[test]
     fn test_rposition() {
-        assert!(find([], f).is_none());
-
-        fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' }
-        fn g(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'd' }
-        let v = ~[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
-
-        assert_eq!(position(v, f), Some(1u));
-        assert!(position(v, g).is_none());
-    }
-
-    #[test]
-    fn test_rposition_between() {
-        assert!(rposition_between([], 0u, 0u, f).is_none());
-
-        fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' }
-        let v = ~[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
-
-        assert!(rposition_between(v, 0u, 0u, f).is_none());
-        assert!(rposition_between(v, 0u, 1u, f).is_none());
-        assert_eq!(rposition_between(v, 0u, 2u, f), Some(1u));
-        assert_eq!(rposition_between(v, 0u, 3u, f), Some(1u));
-        assert_eq!(rposition_between(v, 0u, 4u, f), Some(3u));
-
-        assert!(rposition_between(v, 1u, 1u, f).is_none());
-        assert_eq!(rposition_between(v, 1u, 2u, f), Some(1u));
-        assert_eq!(rposition_between(v, 1u, 3u, f), Some(1u));
-        assert_eq!(rposition_between(v, 1u, 4u, f), Some(3u));
-
-        assert!(rposition_between(v, 2u, 2u, f).is_none());
-        assert!(rposition_between(v, 2u, 3u, f).is_none());
-        assert_eq!(rposition_between(v, 2u, 4u, f), Some(3u));
-
-        assert!(rposition_between(v, 3u, 3u, f).is_none());
-        assert_eq!(rposition_between(v, 3u, 4u, f), Some(3u));
-
-        assert!(rposition_between(v, 4u, 4u, f).is_none());
-    }
-
-    #[test]
-    fn test_rfind() {
-        assert!(rfind([], f).is_none());
-
         fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' }
         fn g(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'd' }
         let v = ~[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
 
-        assert_eq!(rfind(v, f), Some((3, 'b')));
-        assert!(rfind(v, g).is_none());
-    }
-
-    #[test]
-    fn test_rfind_between() {
-        assert!(rfind_between([], 0u, 0u, f).is_none());
-
-        fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' }
-        let v = ~[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
-
-        assert!(rfind_between(v, 0u, 0u, f).is_none());
-        assert!(rfind_between(v, 0u, 1u, f).is_none());
-        assert_eq!(rfind_between(v, 0u, 2u, f), Some((1, 'b')));
-        assert_eq!(rfind_between(v, 0u, 3u, f), Some((1, 'b')));
-        assert_eq!(rfind_between(v, 0u, 4u, f), Some((3, 'b')));
-
-        assert!(rfind_between(v, 1u, 1u, f).is_none());
-        assert_eq!(rfind_between(v, 1u, 2u, f), Some((1, 'b')));
-        assert_eq!(rfind_between(v, 1u, 3u, f), Some((1, 'b')));
-        assert_eq!(rfind_between(v, 1u, 4u, f), Some((3, 'b')));
-
-        assert!(rfind_between(v, 2u, 2u, f).is_none());
-        assert!(rfind_between(v, 2u, 3u, f).is_none());
-        assert_eq!(rfind_between(v, 2u, 4u, f), Some((3, 'b')));
-
-        assert!(rfind_between(v, 3u, 3u, f).is_none());
-        assert_eq!(rfind_between(v, 3u, 4u, f), Some((3, 'b')));
-
-        assert!(rfind_between(v, 4u, 4u, f).is_none());
+        assert_eq!(v.rposition(f), Some(3u));
+        assert!(v.rposition(g).is_none());
     }
 
     #[test]
     fn test_bsearch_elem() {
-        assert_eq!(bsearch_elem([1,2,3,4,5], &5), Some(4));
-        assert_eq!(bsearch_elem([1,2,3,4,5], &4), Some(3));
-        assert_eq!(bsearch_elem([1,2,3,4,5], &3), Some(2));
-        assert_eq!(bsearch_elem([1,2,3,4,5], &2), Some(1));
-        assert_eq!(bsearch_elem([1,2,3,4,5], &1), Some(0));
+        assert_eq!([1,2,3,4,5].bsearch_elem(&5), Some(4));
+        assert_eq!([1,2,3,4,5].bsearch_elem(&4), Some(3));
+        assert_eq!([1,2,3,4,5].bsearch_elem(&3), Some(2));
+        assert_eq!([1,2,3,4,5].bsearch_elem(&2), Some(1));
+        assert_eq!([1,2,3,4,5].bsearch_elem(&1), Some(0));
 
-        assert_eq!(bsearch_elem([2,4,6,8,10], &1), None);
-        assert_eq!(bsearch_elem([2,4,6,8,10], &5), None);
-        assert_eq!(bsearch_elem([2,4,6,8,10], &4), Some(1));
-        assert_eq!(bsearch_elem([2,4,6,8,10], &10), Some(4));
+        assert_eq!([2,4,6,8,10].bsearch_elem(&1), None);
+        assert_eq!([2,4,6,8,10].bsearch_elem(&5), None);
+        assert_eq!([2,4,6,8,10].bsearch_elem(&4), Some(1));
+        assert_eq!([2,4,6,8,10].bsearch_elem(&10), Some(4));
 
-        assert_eq!(bsearch_elem([2,4,6,8], &1), None);
-        assert_eq!(bsearch_elem([2,4,6,8], &5), None);
-        assert_eq!(bsearch_elem([2,4,6,8], &4), Some(1));
-        assert_eq!(bsearch_elem([2,4,6,8], &8), Some(3));
+        assert_eq!([2,4,6,8].bsearch_elem(&1), None);
+        assert_eq!([2,4,6,8].bsearch_elem(&5), None);
+        assert_eq!([2,4,6,8].bsearch_elem(&4), Some(1));
+        assert_eq!([2,4,6,8].bsearch_elem(&8), Some(3));
 
-        assert_eq!(bsearch_elem([2,4,6], &1), None);
-        assert_eq!(bsearch_elem([2,4,6], &5), None);
-        assert_eq!(bsearch_elem([2,4,6], &4), Some(1));
-        assert_eq!(bsearch_elem([2,4,6], &6), Some(2));
+        assert_eq!([2,4,6].bsearch_elem(&1), None);
+        assert_eq!([2,4,6].bsearch_elem(&5), None);
+        assert_eq!([2,4,6].bsearch_elem(&4), Some(1));
+        assert_eq!([2,4,6].bsearch_elem(&6), Some(2));
 
-        assert_eq!(bsearch_elem([2,4], &1), None);
-        assert_eq!(bsearch_elem([2,4], &5), None);
-        assert_eq!(bsearch_elem([2,4], &2), Some(0));
-        assert_eq!(bsearch_elem([2,4], &4), Some(1));
+        assert_eq!([2,4].bsearch_elem(&1), None);
+        assert_eq!([2,4].bsearch_elem(&5), None);
+        assert_eq!([2,4].bsearch_elem(&2), Some(0));
+        assert_eq!([2,4].bsearch_elem(&4), Some(1));
 
-        assert_eq!(bsearch_elem([2], &1), None);
-        assert_eq!(bsearch_elem([2], &5), None);
-        assert_eq!(bsearch_elem([2], &2), Some(0));
+        assert_eq!([2].bsearch_elem(&1), None);
+        assert_eq!([2].bsearch_elem(&5), None);
+        assert_eq!([2].bsearch_elem(&2), Some(0));
 
-        assert_eq!(bsearch_elem([], &1), None);
-        assert_eq!(bsearch_elem([], &5), None);
+        assert_eq!([].bsearch_elem(&1), None);
+        assert_eq!([].bsearch_elem(&5), None);
 
-        assert!(bsearch_elem([1,1,1,1,1], &1) != None);
-        assert!(bsearch_elem([1,1,1,1,2], &1) != None);
-        assert!(bsearch_elem([1,1,1,2,2], &1) != None);
-        assert!(bsearch_elem([1,1,2,2,2], &1) != None);
-        assert_eq!(bsearch_elem([1,2,2,2,2], &1), Some(0));
+        assert!([1,1,1,1,1].bsearch_elem(&1) != None);
+        assert!([1,1,1,1,2].bsearch_elem(&1) != None);
+        assert!([1,1,1,2,2].bsearch_elem(&1) != None);
+        assert!([1,1,2,2,2].bsearch_elem(&1) != None);
+        assert_eq!([1,2,2,2,2].bsearch_elem(&1), Some(0));
 
-        assert_eq!(bsearch_elem([1,2,3,4,5], &6), None);
-        assert_eq!(bsearch_elem([1,2,3,4,5], &0), None);
+        assert_eq!([1,2,3,4,5].bsearch_elem(&6), None);
+        assert_eq!([1,2,3,4,5].bsearch_elem(&0), None);
     }
 
     #[test]
@@ -3556,7 +2825,7 @@ mod tests {
         let mut v: ~[int] = ~[10, 20];
         assert_eq!(v[0], 10);
         assert_eq!(v[1], 20);
-        reverse(v);
+        v.reverse();
         assert_eq!(v[0], 20);
         assert_eq!(v[1], 10);
         let v2 = reversed::<int>([10, 20]);
@@ -3569,7 +2838,7 @@ mod tests {
         let v4 = reversed::<int>([]);
         assert_eq!(v4, ~[]);
         let mut v3: ~[int] = ~[];
-        reverse::<int>(v3);
+        v3.reverse();
     }
 
     #[test]
@@ -3625,11 +2894,10 @@ mod tests {
 
     #[test]
     fn test_partition() {
-        // FIXME (#4355 maybe): using v.partition here crashes
-        assert_eq!(partition(~[], |x: &int| *x < 3), (~[], ~[]));
-        assert_eq!(partition(~[1, 2, 3], |x: &int| *x < 4), (~[1, 2, 3], ~[]));
-        assert_eq!(partition(~[1, 2, 3], |x: &int| *x < 2), (~[1], ~[2, 3]));
-        assert_eq!(partition(~[1, 2, 3], |x: &int| *x < 0), (~[], ~[1, 2, 3]));
+        assert_eq!((~[]).partition(|x: &int| *x < 3), (~[], ~[]));
+        assert_eq!((~[1, 2, 3]).partition(|x: &int| *x < 4), (~[1, 2, 3], ~[]));
+        assert_eq!((~[1, 2, 3]).partition(|x: &int| *x < 2), (~[1], ~[2, 3]));
+        assert_eq!((~[1, 2, 3]).partition(|x: &int| *x < 0), (~[], ~[1, 2, 3]));
     }
 
     #[test]
@@ -3749,11 +3017,11 @@ mod tests {
     #[test]
     fn test_capacity() {
         let mut v = ~[0u64];
-        reserve(&mut v, 10u);
-        assert_eq!(capacity(&v), 10u);
+        v.reserve(10u);
+        assert_eq!(v.capacity(), 10u);
         let mut v = ~[0u32];
-        reserve(&mut v, 10u);
-        assert_eq!(capacity(&v), 10u);
+        v.reserve(10u);
+        assert_eq!(v.capacity(), 10u);
     }
 
     #[test]
@@ -3959,7 +3227,7 @@ mod tests {
     fn test_map_fail() {
         let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
         let mut i = 0;
-        do map(v) |_elt| {
+        do v.map |_elt| {
             if i == 2 {
                 fail!()
             }
@@ -3986,41 +3254,10 @@ mod tests {
     #[test]
     #[ignore(windows)]
     #[should_fail]
-    fn test_mapi_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do mapi(v) |_i, _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;
-        do map(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            ~[(~0, @0)]
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
-    fn test_map_zip_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do map_zip(v, v) |_elt1, _elt2| {
+        do flat_map(v) |_elt| {
             if i == 2 {
                 fail!()
             }
@@ -4064,71 +3301,10 @@ mod tests {
     #[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;
-        do find(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            false
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_position_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do position(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            false
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
     fn test_rposition_fail() {
         let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
         let mut i = 0;
-        do rposition(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            false
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_each_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do each(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            false
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_eachi_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do eachi(v) |_i, _elt| {
+        do v.rposition |_elt| {
             if i == 2 {
                 fail!()
             }
@@ -4163,16 +3339,6 @@ mod tests {
     }
 
     #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_as_const_buf_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        do as_const_buf(v) |_buf, _i| {
-            fail!()
-        }
-    }
-
-    #[test]
     #[ignore(cfg(windows))]
     #[should_fail]
     fn test_as_mut_buf_fail() {
@@ -4206,13 +3372,19 @@ mod tests {
     fn test_iterator() {
         use iterator::*;
         let xs = [1, 2, 5, 10, 11];
-        let ys = [1, 2, 5, 10, 11, 19];
         let mut it = xs.iter();
-        let mut i = 0;
-        for it.advance |&x| {
-            assert_eq!(x, ys[i]);
-            i += 1;
-        }
+        assert_eq!(it.size_hint(), (Some(5), Some(5)));
+        assert_eq!(it.next().unwrap(), &1);
+        assert_eq!(it.size_hint(), (Some(4), Some(4)));
+        assert_eq!(it.next().unwrap(), &2);
+        assert_eq!(it.size_hint(), (Some(3), Some(3)));
+        assert_eq!(it.next().unwrap(), &5);
+        assert_eq!(it.size_hint(), (Some(2), Some(2)));
+        assert_eq!(it.next().unwrap(), &10);
+        assert_eq!(it.size_hint(), (Some(1), Some(1)));
+        assert_eq!(it.next().unwrap(), &11);
+        assert_eq!(it.size_hint(), (Some(0), Some(0)));
+        assert!(it.next().is_none());
     }
 
     #[test]
@@ -4250,9 +3422,41 @@ mod tests {
     }
 
     #[test]
+    fn test_move_from() {
+        let mut a = [1,2,3,4,5];
+        let b = ~[6,7,8];
+        assert_eq!(a.move_from(b, 0, 3), 3);
+        assert_eq!(a, [6,7,8,4,5]);
+        let mut a = [7,2,8,1];
+        let b = ~[3,1,4,1,5,9];
+        assert_eq!(a.move_from(b, 0, 6), 4);
+        assert_eq!(a, [3,1,4,1]);
+        let mut a = [1,2,3,4];
+        let b = ~[5,6,7,8,9,0];
+        assert_eq!(a.move_from(b, 2, 3), 1);
+        assert_eq!(a, [7,2,3,4]);
+        let mut a = [1,2,3,4,5];
+        let b = ~[5,6,7,8,9,0];
+        assert_eq!(a.mut_slice(2,4).move_from(b,1,6), 2);
+        assert_eq!(a, [1,2,6,7,5]);
+    }
+
+    #[test]
+    fn test_copy_from() {
+        let mut a = [1,2,3,4,5];
+        let b = [6,7,8];
+        assert_eq!(a.copy_from(b), 3);
+        assert_eq!(a, [6,7,8,4,5]);
+        let mut c = [7,2,8,1];
+        let d = [3,1,4,1,5,9];
+        assert_eq!(c.copy_from(d), 4);
+        assert_eq!(c, [3,1,4,1]);
+    }
+
+    #[test]
     fn test_reverse_part() {
         let mut values = [1,2,3,4,5];
-        reverse_part(values,1,4);
+        values.mut_slice(1, 4).reverse();
         assert_eq!(values, [1,4,3,2,5]);
     }
 
@@ -4300,15 +3504,25 @@ mod tests {
     fn test_vec_zero() {
         use num::Zero;
         macro_rules! t (
-            ($ty:ty) => {
+            ($ty:ty) => {{
                 let v: $ty = Zero::zero();
                 assert!(v.is_empty());
                 assert!(v.is_zero());
-            }
+            }}
         );
 
         t!(&[int]);
         t!(@[int]);
         t!(~[int]);
     }
+
+    #[test]
+    fn test_bytes_set_memory() {
+        use vec::bytes::MutableByteVector;
+        let mut values = [1u8,2,3,4,5];
+        values.mut_slice(0,5).set_memory(0xAB);
+        assert_eq!(values, [0xAB, 0xAB, 0xAB, 0xAB, 0xAB]);
+        values.mut_slice(2,4).set_memory(0xFF);
+        assert_eq!(values, [0xAB, 0xAB, 0xFF, 0xFF, 0xAB]);
+    }
 }