moved collections from libextra into libcollections

14 files changed, 12 insertions, 7811 deletions

diff --git a/src/libextra/bitv.rs b/src/libextra/bitv.rs
deleted file mode 100644
index 7211907f483..00000000000
--- a/src/libextra/bitv.rs
+++ /dev/null
@@ -1,1675 +0,0 @@
-// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-#[allow(missing_doc)];
-
-
-use std::cmp;
-use std::iter::RandomAccessIterator;
-use std::iter::{Rev, Enumerate, Repeat, Map, Zip};
-use std::num;
-use std::ops;
-use std::uint;
-use std::vec;
-
-#[deriving(Clone)]
-struct SmallBitv {
-    /// only the lowest nbits of this value are used. the rest is undefined.
-    bits: uint
-}
-
-/// a mask that has a 1 for each defined bit in a small_bitv, assuming n bits
-#[inline]
-fn small_mask(nbits: uint) -> uint {
-    (1 << nbits) - 1
-}
-
-impl SmallBitv {
-    pub fn new(bits: uint) -> SmallBitv {
-        SmallBitv {bits: bits}
-    }
-
-    #[inline]
-    pub fn bits_op(&mut self,
-                   right_bits: uint,
-                   nbits: uint,
-                   f: |uint, uint| -> uint)
-                   -> bool {
-        let mask = small_mask(nbits);
-        let old_b: uint = self.bits;
-        let new_b = f(old_b, right_bits);
-        self.bits = new_b;
-        mask & old_b != mask & new_b
-    }
-
-    #[inline]
-    pub fn union(&mut self, s: &SmallBitv, nbits: uint) -> bool {
-        self.bits_op(s.bits, nbits, |u1, u2| u1 | u2)
-    }
-
-    #[inline]
-    pub fn intersect(&mut self, s: &SmallBitv, nbits: uint) -> bool {
-        self.bits_op(s.bits, nbits, |u1, u2| u1 & u2)
-    }
-
-    #[inline]
-    pub fn become(&mut self, s: &SmallBitv, nbits: uint) -> bool {
-        self.bits_op(s.bits, nbits, |_u1, u2| u2)
-    }
-
-    #[inline]
-    pub fn difference(&mut self, s: &SmallBitv, nbits: uint) -> bool {
-        self.bits_op(s.bits, nbits, |u1, u2| u1 & !u2)
-    }
-
-    #[inline]
-    pub fn get(&self, i: uint) -> bool {
-        (self.bits & (1 << i)) != 0
-    }
-
-    #[inline]
-    pub fn set(&mut self, i: uint, x: bool) {
-        if x {
-            self.bits |= 1<<i;
-        }
-        else {
-            self.bits &= !(1<<i);
-        }
-    }
-
-    #[inline]
-    pub fn equals(&self, b: &SmallBitv, nbits: uint) -> bool {
-        let mask = small_mask(nbits);
-        mask & self.bits == mask & b.bits
-    }
-
-    #[inline]
-    pub fn clear(&mut self) { self.bits = 0; }
-
-    #[inline]
-    pub fn set_all(&mut self) { self.bits = !0; }
-
-    #[inline]
-    pub fn is_true(&self, nbits: uint) -> bool {
-        small_mask(nbits) & !self.bits == 0
-    }
-
-    #[inline]
-    pub fn is_false(&self, nbits: uint) -> bool {
-        small_mask(nbits) & self.bits == 0
-    }
-
-    #[inline]
-    pub fn negate(&mut self) { self.bits = !self.bits; }
-}
-
-#[deriving(Clone)]
-struct BigBitv {
-    storage: ~[uint]
-}
-
-/**
- * A mask that has a 1 for each defined bit in the n'th element of a `BigBitv`,
- * assuming n bits.
- */
-#[inline]
-fn big_mask(nbits: uint, elem: uint) -> uint {
-    let rmd = nbits % uint::BITS;
-    let nelems = nbits/uint::BITS + if rmd == 0 {0} else {1};
-
-    if elem < nelems - 1 || rmd == 0 {
-        !0
-    } else {
-        (1 << rmd) - 1
-    }
-}
-
-impl BigBitv {
-    pub fn new(storage: ~[uint]) -> BigBitv {
-        BigBitv {storage: storage}
-    }
-
-    #[inline]
-    pub fn process(&mut self,
-                   b: &BigBitv,
-                   nbits: uint,
-                   op: |uint, uint| -> uint)
-                   -> bool {
-        let len = b.storage.len();
-        assert_eq!(self.storage.len(), len);
-        let mut changed = false;
-        for (i, (a, b)) in self.storage.mut_iter()
-                               .zip(b.storage.iter())
-                               .enumerate() {
-            let mask = big_mask(nbits, i);
-            let w0 = *a & mask;
-            let w1 = *b & mask;
-            let w = op(w0, w1) & mask;
-            if w0 != w {
-                changed = true;
-                *a = w;
-            }
-        }
-        changed
-    }
-
-    #[inline]
-    pub fn each_storage(&mut self, op: |v: &mut uint| -> bool) -> bool {
-        self.storage.mut_iter().advance(|elt| op(elt))
-    }
-
-    #[inline]
-    pub fn negate(&mut self) {
-        self.each_storage(|w| { *w = !*w; true });
-    }
-
-    #[inline]
-    pub fn union(&mut self, b: &BigBitv, nbits: uint) -> bool {
-        self.process(b, nbits, |w1, w2| w1 | w2)
-    }
-
-    #[inline]
-    pub fn intersect(&mut self, b: &BigBitv, nbits: uint) -> bool {
-        self.process(b, nbits, |w1, w2| w1 & w2)
-    }
-
-    #[inline]
-    pub fn become(&mut self, b: &BigBitv, nbits: uint) -> bool {
-        self.process(b, nbits, |_, w| w)
-    }
-
-    #[inline]
-    pub fn difference(&mut self, b: &BigBitv, nbits: uint) -> bool {
-        self.process(b, nbits, |w1, w2| w1 & !w2)
-    }
-
-    #[inline]
-    pub fn get(&self, i: uint) -> bool {
-        let w = i / uint::BITS;
-        let b = i % uint::BITS;
-        let x = 1 & self.storage[w] >> b;
-        x == 1
-    }
-
-    #[inline]
-    pub fn set(&mut self, i: uint, x: bool) {
-        let w = i / uint::BITS;
-        let b = i % uint::BITS;
-        let flag = 1 << b;
-        self.storage[w] = if x { self.storage[w] | flag }
-                          else { self.storage[w] & !flag };
-    }
-
-    #[inline]
-    pub fn equals(&self, b: &BigBitv, nbits: uint) -> bool {
-        for (i, elt) in b.storage.iter().enumerate() {
-            let mask = big_mask(nbits, i);
-            if mask & self.storage[i] != mask & *elt {
-                return false;
-            }
-        }
-        true
-    }
-}
-
-#[deriving(Clone)]
-enum BitvVariant { Big(BigBitv), Small(SmallBitv) }
-
-enum Op {Union, Intersect, Assign, Difference}
-
-/// The bitvector type
-#[deriving(Clone)]
-pub struct Bitv {
-    /// Internal representation of the bit vector (small or large)
-    priv rep: BitvVariant,
-    /// The number of valid bits in the internal representation
-    priv nbits: uint
-}
-
-fn die() -> ! {
-    fail!("Tried to do operation on bit vectors with different sizes");
-}
-
-impl Bitv {
-    #[inline]
-    fn do_op(&mut self, op: Op, other: &Bitv) -> bool {
-        if self.nbits != other.nbits {
-            die();
-        }
-        match self.rep {
-          Small(ref mut s) => match other.rep {
-            Small(ref s1) => match op {
-              Union      => s.union(s1,      self.nbits),
-              Intersect  => s.intersect(s1,  self.nbits),
-              Assign     => s.become(s1,     self.nbits),
-              Difference => s.difference(s1, self.nbits)
-            },
-            Big(_) => die()
-          },
-          Big(ref mut s) => match other.rep {
-            Small(_) => die(),
-            Big(ref s1) => match op {
-              Union      => s.union(s1,      self.nbits),
-              Intersect  => s.intersect(s1,  self.nbits),
-              Assign     => s.become(s1,     self.nbits),
-              Difference => s.difference(s1, self.nbits)
-            }
-          }
-        }
-    }
-
-}
-
-impl Bitv {
-    pub fn new(nbits: uint, init: bool) -> Bitv {
-        let rep = if nbits < uint::BITS {
-            Small(SmallBitv::new(if init {(1<<nbits)-1} else {0}))
-        } else if nbits == uint::BITS {
-            Small(SmallBitv::new(if init {!0} else {0}))
-        } else {
-            let exact = nbits % uint::BITS == 0;
-            let nelems = nbits/uint::BITS + if exact {0} else {1};
-            let s =
-                if init {
-                    if exact {
-                        vec::from_elem(nelems, !0u)
-                    } else {
-                        let mut v = vec::from_elem(nelems-1, !0u);
-                        v.push((1<<nbits % uint::BITS)-1);
-                        v
-                    }
-                } else { vec::from_elem(nelems, 0u)};
-            Big(BigBitv::new(s))
-        };
-        Bitv {rep: rep, nbits: nbits}
-    }
-
-    /**
-     * Calculates the union of two bitvectors
-     *
-     * Sets `self` to the union of `self` and `v1`. Both bitvectors must be
-     * the same length. Returns `true` if `self` changed.
-    */
-    #[inline]
-    pub fn union(&mut self, v1: &Bitv) -> bool { self.do_op(Union, v1) }
-
-    /**
-     * Calculates the intersection of two bitvectors
-     *
-     * Sets `self` to the intersection of `self` and `v1`. Both bitvectors
-     * must be the same length. Returns `true` if `self` changed.
-    */
-    #[inline]
-    pub fn intersect(&mut self, v1: &Bitv) -> bool {
-        self.do_op(Intersect, v1)
-    }
-
-    /**
-     * Assigns the value of `v1` to `self`
-     *
-     * Both bitvectors must be the same length. Returns `true` if `self` was
-     * changed
-     */
-    #[inline]
-    pub fn assign(&mut self, v: &Bitv) -> bool { self.do_op(Assign, v) }
-
-    /// Retrieve the value at index `i`
-    #[inline]
-    pub fn get(&self, i: uint) -> bool {
-        assert!((i < self.nbits));
-        match self.rep {
-            Big(ref b)   => b.get(i),
-            Small(ref s) => s.get(i)
-        }
-    }
-
-    /**
-     * Set the value of a bit at a given index
-     *
-     * `i` must be less than the length of the bitvector.
-     */
-    #[inline]
-    pub fn set(&mut self, i: uint, x: bool) {
-      assert!((i < self.nbits));
-      match self.rep {
-        Big(ref mut b)   => b.set(i, x),
-        Small(ref mut s) => s.set(i, x)
-      }
-    }
-
-    /**
-     * Compares two bitvectors
-     *
-     * Both bitvectors must be the same length. Returns `true` if both
-     * bitvectors contain identical elements.
-     */
-    #[inline]
-    pub fn equal(&self, v1: &Bitv) -> bool {
-      if self.nbits != v1.nbits { return false; }
-      match self.rep {
-        Small(ref b) => match v1.rep {
-          Small(ref b1) => b.equals(b1, self.nbits),
-          _ => false
-        },
-        Big(ref s) => match v1.rep {
-          Big(ref s1) => s.equals(s1, self.nbits),
-          Small(_) => return false
-        }
-      }
-    }
-
-    /// Set all bits to 0
-    #[inline]
-    pub fn clear(&mut self) {
-        match self.rep {
-            Small(ref mut b) => b.clear(),
-            Big(ref mut s) => {
-                s.each_storage(|w| { *w = 0u; true });
-            }
-        }
-    }
-
-    /// Set all bits to 1
-    #[inline]
-    pub fn set_all(&mut self) {
-        match self.rep {
-            Small(ref mut b) => b.set_all(),
-            Big(ref mut s) => {
-                s.each_storage(|w| { *w = !0u; true });
-            }
-        }
-    }
-
-    /// Flip all bits
-    #[inline]
-    pub fn negate(&mut self) {
-        match self.rep {
-            Small(ref mut s) => s.negate(),
-            Big(ref mut b) => b.negate(),
-        }
-    }
-
-    /**
-     * Calculate the difference between two bitvectors
-     *
-     * Sets each element of `v0` to the value of that element minus the
-     * element of `v1` at the same index. Both bitvectors must be the same
-     * length.
-     *
-     * Returns `true` if `v0` was changed.
-     */
-    #[inline]
-    pub fn difference(&mut self, v: &Bitv) -> bool {
-        self.do_op(Difference, v)
-    }
-
-    /// Returns `true` if all bits are 1
-    #[inline]
-    pub fn is_true(&self) -> bool {
-      match self.rep {
-        Small(ref b) => b.is_true(self.nbits),
-        _ => {
-          for i in self.iter() { if !i { return false; } }
-          true
-        }
-      }
-    }
-
-    #[inline]
-    pub fn iter<'a>(&'a self) -> Bits<'a> {
-        Bits {bitv: self, next_idx: 0, end_idx: self.nbits}
-    }
-
-    #[inline]
-    pub fn rev_iter<'a>(&'a self) -> Rev<Bits<'a>> {
-        self.iter().rev()
-    }
-
-    /// Returns `true` if all bits are 0
-    pub fn is_false(&self) -> bool {
-      match self.rep {
-        Small(ref b) => b.is_false(self.nbits),
-        Big(_) => {
-          for i in self.iter() { if i { return false; } }
-          true
-        }
-      }
-    }
-
-    pub fn init_to_vec(&self, i: uint) -> uint {
-      return if self.get(i) { 1 } else { 0 };
-    }
-
-    /**
-     * Converts `self` to a vector of `uint` with the same length.
-     *
-     * Each `uint` in the resulting vector has either value `0u` or `1u`.
-     */
-    pub fn to_vec(&self) -> ~[uint] {
-        vec::from_fn(self.nbits, |x| self.init_to_vec(x))
-    }
-
-    /**
-     * Organise the bits into bytes, such that the first bit in the
-     * `Bitv` becomes the high-order bit of the first byte. If the
-     * size of the `Bitv` is not a multiple of 8 then trailing bits
-     * will be filled-in with false/0
-     */
-    pub fn to_bytes(&self) -> ~[u8] {
-        fn bit (bitv: &Bitv, byte: uint, bit: uint) -> u8 {
-            let offset = byte * 8 + bit;
-            if offset >= bitv.nbits {
-                0
-            } else {
-                bitv[offset] as u8 << (7 - bit)
-            }
-        }
-
-        let len = self.nbits/8 +
-                  if self.nbits % 8 == 0 { 0 } else { 1 };
-        vec::from_fn(len, |i|
-            bit(self, i, 0) |
-            bit(self, i, 1) |
-            bit(self, i, 2) |
-            bit(self, i, 3) |
-            bit(self, i, 4) |
-            bit(self, i, 5) |
-            bit(self, i, 6) |
-            bit(self, i, 7)
-        )
-    }
-
-    /**
-     * Transform `self` into a `[bool]` by turning each bit into a `bool`.
-     */
-    pub fn to_bools(&self) -> ~[bool] {
-        vec::from_fn(self.nbits, |i| self[i])
-    }
-
-    /**
-     * Converts `self` to a string.
-     *
-     * The resulting string has the same length as `self`, and each
-     * character is either '0' or '1'.
-     */
-     pub fn to_str(&self) -> ~str {
-        let mut rs = ~"";
-        for i in self.iter() {
-            if i {
-                rs.push_char('1');
-            } else {
-                rs.push_char('0');
-            }
-        };
-        rs
-     }
-
-
-    /**
-     * Compare a bitvector to a vector of `bool`.
-     *
-     * Both the bitvector and vector must have the same length.
-     */
-    pub fn eq_vec(&self, v: &[bool]) -> bool {
-        assert_eq!(self.nbits, v.len());
-        let mut i = 0;
-        while i < self.nbits {
-            if self.get(i) != v[i] { return false; }
-            i = i + 1;
-        }
-        true
-    }
-
-    pub fn ones(&self, f: |uint| -> bool) -> bool {
-        range(0u, self.nbits).advance(|i| !self.get(i) || f(i))
-    }
-
-}
-
-/**
- * Transform a byte-vector into a `Bitv`. Each byte becomes 8 bits,
- * with the most significant bits of each byte coming first. Each
- * bit becomes `true` if equal to 1 or `false` if equal to 0.
- */
-pub fn from_bytes(bytes: &[u8]) -> Bitv {
-    from_fn(bytes.len() * 8, |i| {
-        let b = bytes[i / 8] as uint;
-        let offset = i % 8;
-        b >> (7 - offset) & 1 == 1
-    })
-}
-
-/**
- * Transform a `[bool]` into a `Bitv` by converting each `bool` into a bit.
- */
-pub fn from_bools(bools: &[bool]) -> Bitv {
-    from_fn(bools.len(), |i| bools[i])
-}
-
-/**
- * Create a `Bitv` of the specified length where the value at each
- * index is `f(index)`.
- */
-pub fn from_fn(len: uint, f: |index: uint| -> bool) -> Bitv {
-    let mut bitv = Bitv::new(len, false);
-    for i in range(0u, len) {
-        bitv.set(i, f(i));
-    }
-    bitv
-}
-
-impl ops::Index<uint,bool> for Bitv {
-    fn index(&self, i: &uint) -> bool {
-        self.get(*i)
-    }
-}
-
-#[inline]
-fn iterate_bits(base: uint, bits: uint, f: |uint| -> bool) -> bool {
-    if bits == 0 {
-        return true;
-    }
-    for i in range(0u, uint::BITS) {
-        if bits & (1 << i) != 0 {
-            if !f(base + i) {
-                return false;
-            }
-        }
-    }
-    return true;
-}
-
-/// An iterator for `Bitv`.
-pub struct Bits<'a> {
-    priv bitv: &'a Bitv,
-    priv next_idx: uint,
-    priv end_idx: uint,
-}
-
-impl<'a> Iterator<bool> for Bits<'a> {
-    #[inline]
-    fn next(&mut self) -> Option<bool> {
-        if self.next_idx != self.end_idx {
-            let idx = self.next_idx;
-            self.next_idx += 1;
-            Some(self.bitv.get(idx))
-        } else {
-            None
-        }
-    }
-
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        let rem = self.end_idx - self.next_idx;
-        (rem, Some(rem))
-    }
-}
-
-impl<'a> DoubleEndedIterator<bool> for Bits<'a> {
-    #[inline]
-    fn next_back(&mut self) -> Option<bool> {
-        if self.next_idx != self.end_idx {
-            self.end_idx -= 1;
-            Some(self.bitv.get(self.end_idx))
-        } else {
-            None
-        }
-    }
-}
-
-impl<'a> ExactSize<bool> for Bits<'a> {}
-
-impl<'a> RandomAccessIterator<bool> for Bits<'a> {
-    #[inline]
-    fn indexable(&self) -> uint {
-        self.end_idx - self.next_idx
-    }
-
-    #[inline]
-    fn idx(&self, index: uint) -> Option<bool> {
-        if index >= self.indexable() {
-            None
-        } else {
-            Some(self.bitv.get(index))
-        }
-    }
-}
-
-/// An implementation of a set using a bit vector as an underlying
-/// representation for holding numerical elements.
-///
-/// It should also be noted that the amount of storage necessary for holding a
-/// set of objects is proportional to the maximum of the objects when viewed
-/// as a `uint`.
-#[deriving(Clone)]
-pub struct BitvSet {
-    priv size: uint,
-
-    // In theory this is a `Bitv` instead of always a `BigBitv`, but knowing that
-    // there's an array of storage makes our lives a whole lot easier when
-    // performing union/intersection/etc operations
-    priv bitv: BigBitv
-}
-
-impl BitvSet {
-    /// Creates a new bit vector set with initially no contents
-    pub fn new() -> BitvSet {
-        BitvSet{ size: 0, bitv: BigBitv::new(~[0]) }
-    }
-
-    /// Creates a new bit vector set from the given bit vector
-    pub fn from_bitv(bitv: Bitv) -> BitvSet {
-        let mut size = 0;
-        bitv.ones(|_| {
-            size += 1;
-            true
-        });
-        let Bitv{rep, ..} = bitv;
-        match rep {
-            Big(b) => BitvSet{ size: size, bitv: b },
-            Small(SmallBitv{bits}) =>
-                BitvSet{ size: size, bitv: BigBitv{ storage: ~[bits] } },
-        }
-    }
-
-    /// Returns the capacity in bits for this bit vector. Inserting any
-    /// element less than this amount will not trigger a resizing.
-    pub fn capacity(&self) -> uint { self.bitv.storage.len() * uint::BITS }
-
-    /// Consumes this set to return the underlying bit vector
-    pub fn unwrap(self) -> Bitv {
-        let cap = self.capacity();
-        let BitvSet{bitv, ..} = self;
-        return Bitv{ nbits:cap, rep: Big(bitv) };
-    }
-
-    #[inline]
-    fn other_op(&mut self, other: &BitvSet, f: |uint, uint| -> uint) {
-        fn nbits(mut w: uint) -> uint {
-            let mut bits = 0;
-            for _ in range(0u, uint::BITS) {
-                if w == 0 {
-                    break;
-                }
-                bits += w & 1;
-                w >>= 1;
-            }
-            return bits;
-        }
-        if self.capacity() < other.capacity() {
-            self.bitv.storage.grow(other.capacity() / uint::BITS, &0);
-        }
-        for (i, &w) in other.bitv.storage.iter().enumerate() {
-            let old = self.bitv.storage[i];
-            let new = f(old, w);
-            self.bitv.storage[i] = new;
-            self.size += nbits(new) - nbits(old);
-        }
-    }
-
-    /// Union in-place with the specified other bit vector
-    pub fn union_with(&mut self, other: &BitvSet) {
-        self.other_op(other, |w1, w2| w1 | w2);
-    }
-
-    /// Intersect in-place with the specified other bit vector
-    pub fn intersect_with(&mut self, other: &BitvSet) {
-        self.other_op(other, |w1, w2| w1 & w2);
-    }
-
-    /// Difference in-place with the specified other bit vector
-    pub fn difference_with(&mut self, other: &BitvSet) {
-        self.other_op(other, |w1, w2| w1 & !w2);
-    }
-
-    /// Symmetric difference in-place with the specified other bit vector
-    pub fn symmetric_difference_with(&mut self, other: &BitvSet) {
-        self.other_op(other, |w1, w2| w1 ^ w2);
-    }
-
-    pub fn iter<'a>(&'a self) -> BitPositions<'a> {
-        BitPositions {set: self, next_idx: 0}
-    }
-
-    pub fn difference(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
-        for (i, w1, w2) in self.commons(other) {
-            if !iterate_bits(i, w1 & !w2, |b| f(&b)) {
-                return false
-            }
-        };
-        /* everything we have that they don't also shows up */
-        self.outliers(other).advance(|(mine, i, w)|
-            !mine || iterate_bits(i, w, |b| f(&b))
-        )
-    }
-
-    pub fn symmetric_difference(&self, other: &BitvSet, f: |&uint| -> bool)
-                                -> bool {
-        for (i, w1, w2) in self.commons(other) {
-            if !iterate_bits(i, w1 ^ w2, |b| f(&b)) {
-                return false
-            }
-        };
-        self.outliers(other).advance(|(_, i, w)| iterate_bits(i, w, |b| f(&b)))
-    }
-
-    pub fn intersection(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
-        self.commons(other).advance(|(i, w1, w2)| iterate_bits(i, w1 & w2, |b| f(&b)))
-    }
-
-    pub fn union(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
-        for (i, w1, w2) in self.commons(other) {
-            if !iterate_bits(i, w1 | w2, |b| f(&b)) {
-                return false
-            }
-        };
-        self.outliers(other).advance(|(_, i, w)| iterate_bits(i, w, |b| f(&b)))
-    }
-}
-
-impl cmp::Eq for BitvSet {
-    fn eq(&self, other: &BitvSet) -> bool {
-        if self.size != other.size {
-            return false;
-        }
-        for (_, w1, w2) in self.commons(other) {
-            if w1 != w2 {
-                return false;
-            }
-        }
-        for (_, _, w) in self.outliers(other) {
-            if w != 0 {
-                return false;
-            }
-        }
-        return true;
-    }
-
-    fn ne(&self, other: &BitvSet) -> bool { !self.eq(other) }
-}
-
-impl Container for BitvSet {
-    #[inline]
-    fn len(&self) -> uint { self.size }
-}
-
-impl Mutable for BitvSet {
-    fn clear(&mut self) {
-        self.bitv.each_storage(|w| { *w = 0; true });
-        self.size = 0;
-    }
-}
-
-impl Set<uint> for BitvSet {
-    fn contains(&self, value: &uint) -> bool {
-        *value < self.bitv.storage.len() * uint::BITS && self.bitv.get(*value)
-    }
-
-    fn is_disjoint(&self, other: &BitvSet) -> bool {
-        self.intersection(other, |_| false)
-    }
-
-    fn is_subset(&self, other: &BitvSet) -> bool {
-        for (_, w1, w2) in self.commons(other) {
-            if w1 & w2 != w1 {
-                return false;
-            }
-        }
-        /* If anything is not ours, then everything is not ours so we're
-           definitely a subset in that case. Otherwise if there's any stray
-           ones that 'other' doesn't have, we're not a subset. */
-        for (mine, _, w) in self.outliers(other) {
-            if !mine {
-                return true;
-            } else if w != 0 {
-                return false;
-            }
-        }
-        return true;
-    }
-
-    fn is_superset(&self, other: &BitvSet) -> bool {
-        other.is_subset(self)
-    }
-}
-
-impl MutableSet<uint> for BitvSet {
-    fn insert(&mut self, value: uint) -> bool {
-        if self.contains(&value) {
-            return false;
-        }
-        let nbits = self.capacity();
-        if value >= nbits {
-            let newsize = num::max(value, nbits * 2) / uint::BITS + 1;
-            assert!(newsize > self.bitv.storage.len());
-            self.bitv.storage.grow(newsize, &0);
-        }
-        self.size += 1;
-        self.bitv.set(value, true);
-        return true;
-    }
-
-    fn remove(&mut self, value: &uint) -> bool {
-        if !self.contains(value) {
-            return false;
-        }
-        self.size -= 1;
-        self.bitv.set(*value, false);
-
-        // Attempt to truncate our storage
-        let mut i = self.bitv.storage.len();
-        while i > 1 && self.bitv.storage[i - 1] == 0 {
-            i -= 1;
-        }
-        self.bitv.storage.truncate(i);
-
-        return true;
-    }
-}
-
-impl BitvSet {
-    /// Visits each of the words that the two bit vectors (`self` and `other`)
-    /// both have in common. The three yielded arguments are (bit location,
-    /// w1, w2) where the bit location is the number of bits offset so far,
-    /// and w1/w2 are the words coming from the two vectors self, other.
-    fn commons<'a>(&'a self, other: &'a BitvSet)
-        -> Map<'static, ((uint, &'a uint), &'a ~[uint]), (uint, uint, uint),
-               Zip<Enumerate<vec::Items<'a, uint>>, Repeat<&'a ~[uint]>>> {
-        let min = num::min(self.bitv.storage.len(), other.bitv.storage.len());
-        self.bitv.storage.slice(0, min).iter().enumerate()
-            .zip(Repeat::new(&other.bitv.storage))
-            .map(|((i, &w), o_store)| (i * uint::BITS, w, o_store[i]))
-    }
-
-    /// Visits each word in `self` or `other` that extends beyond the other. This
-    /// will only iterate through one of the vectors, and it only iterates
-    /// over the portion that doesn't overlap with the other one.
-    ///
-    /// The yielded arguments are a `bool`, the bit offset, and a word. The `bool`
-    /// is true if the word comes from `self`, and `false` if it comes from
-    /// `other`.
-    fn outliers<'a>(&'a self, other: &'a BitvSet)
-        -> Map<'static, ((uint, &'a uint), uint), (bool, uint, uint),
-               Zip<Enumerate<vec::Items<'a, uint>>, Repeat<uint>>> {
-        let slen = self.bitv.storage.len();
-        let olen = other.bitv.storage.len();
-
-        if olen < slen {
-            self.bitv.storage.slice_from(olen).iter().enumerate()
-                .zip(Repeat::new(olen))
-                .map(|((i, &w), min)| (true, (i + min) * uint::BITS, w))
-        } else {
-            other.bitv.storage.slice_from(slen).iter().enumerate()
-                .zip(Repeat::new(slen))
-                .map(|((i, &w), min)| (false, (i + min) * uint::BITS, w))
-        }
-    }
-}
-
-pub struct BitPositions<'a> {
-    priv set: &'a BitvSet,
-    priv next_idx: uint
-}
-
-impl<'a> Iterator<uint> for BitPositions<'a> {
-    #[inline]
-    fn next(&mut self) -> Option<uint> {
-        while self.next_idx < self.set.capacity() {
-            let idx = self.next_idx;
-            self.next_idx += 1;
-
-            if self.set.contains(&idx) {
-                return Some(idx);
-            }
-        }
-
-        return None;
-    }
-
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        (0, Some(self.set.capacity() - self.next_idx))
-    }
-}
-
-#[cfg(test)]
-mod tests {
-    use extra::test::BenchHarness;
-
-    use bitv::{Bitv, SmallBitv, BigBitv, BitvSet, from_bools, from_fn,
-               from_bytes};
-    use bitv;
-
-    use std::uint;
-    use std::vec;
-    use std::rand;
-    use std::rand::Rng;
-
-    static BENCH_BITS : uint = 1 << 14;
-
-    #[test]
-    fn test_to_str() {
-        let zerolen = Bitv::new(0u, false);
-        assert_eq!(zerolen.to_str(), ~"");
-
-        let eightbits = Bitv::new(8u, false);
-        assert_eq!(eightbits.to_str(), ~"00000000");
-    }
-
-    #[test]
-    fn test_0_elements() {
-        let act = Bitv::new(0u, false);
-        let exp = vec::from_elem::<bool>(0u, false);
-        assert!(act.eq_vec(exp));
-    }
-
-    #[test]
-    fn test_1_element() {
-        let mut act = Bitv::new(1u, false);
-        assert!(act.eq_vec([false]));
-        act = Bitv::new(1u, true);
-        assert!(act.eq_vec([true]));
-    }
-
-    #[test]
-    fn test_2_elements() {
-        let mut b = bitv::Bitv::new(2, false);
-        b.set(0, true);
-        b.set(1, false);
-        assert_eq!(b.to_str(), ~"10");
-    }
-
-    #[test]
-    fn test_10_elements() {
-        let mut act;
-        // all 0
-
-        act = Bitv::new(10u, false);
-        assert!((act.eq_vec(
-                    [false, false, false, false, false, false, false, false, false, false])));
-        // all 1
-
-        act = Bitv::new(10u, true);
-        assert!((act.eq_vec([true, true, true, true, true, true, true, true, true, true])));
-        // mixed
-
-        act = Bitv::new(10u, false);
-        act.set(0u, true);
-        act.set(1u, true);
-        act.set(2u, true);
-        act.set(3u, true);
-        act.set(4u, true);
-        assert!((act.eq_vec([true, true, true, true, true, false, false, false, false, false])));
-        // mixed
-
-        act = Bitv::new(10u, false);
-        act.set(5u, true);
-        act.set(6u, true);
-        act.set(7u, true);
-        act.set(8u, true);
-        act.set(9u, true);
-        assert!((act.eq_vec([false, false, false, false, false, true, true, true, true, true])));
-        // mixed
-
-        act = Bitv::new(10u, false);
-        act.set(0u, true);
-        act.set(3u, true);
-        act.set(6u, true);
-        act.set(9u, true);
-        assert!((act.eq_vec([true, false, false, true, false, false, true, false, false, true])));
-    }
-
-    #[test]
-    fn test_31_elements() {
-        let mut act;
-        // all 0
-
-        act = Bitv::new(31u, false);
-        assert!(act.eq_vec(
-                [false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, false, false, false]));
-        // all 1
-
-        act = Bitv::new(31u, true);
-        assert!(act.eq_vec(
-                [true, true, true, true, true, true, true, true, true, true, true, true, true,
-                true, true, true, true, true, true, true, true, true, true, true, true, true, true,
-                true, true, true, true]));
-        // mixed
-
-        act = Bitv::new(31u, false);
-        act.set(0u, true);
-        act.set(1u, true);
-        act.set(2u, true);
-        act.set(3u, true);
-        act.set(4u, true);
-        act.set(5u, true);
-        act.set(6u, true);
-        act.set(7u, true);
-        assert!(act.eq_vec(
-                [true, true, true, true, true, true, true, true, false, false, false, false, false,
-                false, false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, false]));
-        // mixed
-
-        act = Bitv::new(31u, false);
-        act.set(16u, true);
-        act.set(17u, true);
-        act.set(18u, true);
-        act.set(19u, true);
-        act.set(20u, true);
-        act.set(21u, true);
-        act.set(22u, true);
-        act.set(23u, true);
-        assert!(act.eq_vec(
-                [false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, true, true, true, true, true, true, true, true,
-                false, false, false, false, false, false, false]));
-        // mixed
-
-        act = Bitv::new(31u, false);
-        act.set(24u, true);
-        act.set(25u, true);
-        act.set(26u, true);
-        act.set(27u, true);
-        act.set(28u, true);
-        act.set(29u, true);
-        act.set(30u, true);
-        assert!(act.eq_vec(
-                [false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, false, false, false, false, false, false, false,
-                false, true, true, true, true, true, true, true]));
-        // mixed
-
-        act = Bitv::new(31u, false);
-        act.set(3u, true);
-        act.set(17u, true);
-        act.set(30u, true);
-        assert!(act.eq_vec(
-                [false, false, false, true, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, true, false, false, false, false, false, false,
-                false, false, false, false, false, false, true]));
-    }
-
-    #[test]
-    fn test_32_elements() {
-        let mut act;
-        // all 0
-
-        act = Bitv::new(32u, false);
-        assert!(act.eq_vec(
-                [false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, false, false, false, false]));
-        // all 1
-
-        act = Bitv::new(32u, true);
-        assert!(act.eq_vec(
-                [true, true, true, true, true, true, true, true, true, true, true, true, true,
-                true, true, true, true, true, true, true, true, true, true, true, true, true, true,
-                true, true, true, true, true]));
-        // mixed
-
-        act = Bitv::new(32u, false);
-        act.set(0u, true);
-        act.set(1u, true);
-        act.set(2u, true);
-        act.set(3u, true);
-        act.set(4u, true);
-        act.set(5u, true);
-        act.set(6u, true);
-        act.set(7u, true);
-        assert!(act.eq_vec(
-                [true, true, true, true, true, true, true, true, false, false, false, false, false,
-                false, false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, false, false]));
-        // mixed
-
-        act = Bitv::new(32u, false);
-        act.set(16u, true);
-        act.set(17u, true);
-        act.set(18u, true);
-        act.set(19u, true);
-        act.set(20u, true);
-        act.set(21u, true);
-        act.set(22u, true);
-        act.set(23u, true);
-        assert!(act.eq_vec(
-                [false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, true, true, true, true, true, true, true, true,
-                false, false, false, false, false, false, false, false]));
-        // mixed
-
-        act = Bitv::new(32u, false);
-        act.set(24u, true);
-        act.set(25u, true);
-        act.set(26u, true);
-        act.set(27u, true);
-        act.set(28u, true);
-        act.set(29u, true);
-        act.set(30u, true);
-        act.set(31u, true);
-        assert!(act.eq_vec(
-                [false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, false, false, false, false, false, false, false,
-                false, true, true, true, true, true, true, true, true]));
-        // mixed
-
-        act = Bitv::new(32u, false);
-        act.set(3u, true);
-        act.set(17u, true);
-        act.set(30u, true);
-        act.set(31u, true);
-        assert!(act.eq_vec(
-                [false, false, false, true, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, true, false, false, false, false, false, false,
-                false, false, false, false, false, false, true, true]));
-    }
-
-    #[test]
-    fn test_33_elements() {
-        let mut act;
-        // all 0
-
-        act = Bitv::new(33u, false);
-        assert!(act.eq_vec(
-                [false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, false, false, false, false, false]));
-        // all 1
-
-        act = Bitv::new(33u, true);
-        assert!(act.eq_vec(
-                [true, true, true, true, true, true, true, true, true, true, true, true, true,
-                true, true, true, true, true, true, true, true, true, true, true, true, true, true,
-                true, true, true, true, true, true]));
-        // mixed
-
-        act = Bitv::new(33u, false);
-        act.set(0u, true);
-        act.set(1u, true);
-        act.set(2u, true);
-        act.set(3u, true);
-        act.set(4u, true);
-        act.set(5u, true);
-        act.set(6u, true);
-        act.set(7u, true);
-        assert!(act.eq_vec(
-                [true, true, true, true, true, true, true, true, false, false, false, false, false,
-                false, false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, false, false, false]));
-        // mixed
-
-        act = Bitv::new(33u, false);
-        act.set(16u, true);
-        act.set(17u, true);
-        act.set(18u, true);
-        act.set(19u, true);
-        act.set(20u, true);
-        act.set(21u, true);
-        act.set(22u, true);
-        act.set(23u, true);
-        assert!(act.eq_vec(
-                [false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, true, true, true, true, true, true, true, true,
-                false, false, false, false, false, false, false, false, false]));
-        // mixed
-
-        act = Bitv::new(33u, false);
-        act.set(24u, true);
-        act.set(25u, true);
-        act.set(26u, true);
-        act.set(27u, true);
-        act.set(28u, true);
-        act.set(29u, true);
-        act.set(30u, true);
-        act.set(31u, true);
-        assert!(act.eq_vec(
-                [false, false, false, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, false, false, false, false, false, false, false,
-                false, true, true, true, true, true, true, true, true, false]));
-        // mixed
-
-        act = Bitv::new(33u, false);
-        act.set(3u, true);
-        act.set(17u, true);
-        act.set(30u, true);
-        act.set(31u, true);
-        act.set(32u, true);
-        assert!(act.eq_vec(
-                [false, false, false, true, false, false, false, false, false, false, false, false,
-                false, false, false, false, false, true, false, false, false, false, false, false,
-                false, false, false, false, false, false, true, true, true]));
-    }
-
-    #[test]
-    fn test_equal_differing_sizes() {
-        let v0 = Bitv::new(10u, false);
-        let v1 = Bitv::new(11u, false);
-        assert!(!v0.equal(&v1));
-    }
-
-    #[test]
-    fn test_equal_greatly_differing_sizes() {
-        let v0 = Bitv::new(10u, false);
-        let v1 = Bitv::new(110u, false);
-        assert!(!v0.equal(&v1));
-    }
-
-    #[test]
-    fn test_equal_sneaky_small() {
-        let mut a = bitv::Bitv::new(1, false);
-        a.set(0, true);
-
-        let mut b = bitv::Bitv::new(1, true);
-        b.set(0, true);
-
-        assert!(a.equal(&b));
-    }
-
-    #[test]
-    fn test_equal_sneaky_big() {
-        let mut a = bitv::Bitv::new(100, false);
-        for i in range(0u, 100) {
-            a.set(i, true);
-        }
-
-        let mut b = bitv::Bitv::new(100, true);
-        for i in range(0u, 100) {
-            b.set(i, true);
-        }
-
-        assert!(a.equal(&b));
-    }
-
-    #[test]
-    fn test_from_bytes() {
-        let bitv = from_bytes([0b10110110, 0b00000000, 0b11111111]);
-        let str = ~"10110110" + "00000000" + "11111111";
-        assert_eq!(bitv.to_str(), str);
-    }
-
-    #[test]
-    fn test_to_bytes() {
-        let mut bv = Bitv::new(3, true);
-        bv.set(1, false);
-        assert_eq!(bv.to_bytes(), ~[0b10100000]);
-
-        let mut bv = Bitv::new(9, false);
-        bv.set(2, true);
-        bv.set(8, true);
-        assert_eq!(bv.to_bytes(), ~[0b00100000, 0b10000000]);
-    }
-
-    #[test]
-    fn test_from_bools() {
-        assert!(from_bools([true, false, true, true]).to_str() ==
-            ~"1011");
-    }
-
-    #[test]
-    fn test_to_bools() {
-        let bools = ~[false, false, true, false, false, true, true, false];
-        assert_eq!(from_bytes([0b00100110]).to_bools(), bools);
-    }
-
-    #[test]
-    fn test_bitv_iterator() {
-        let bools = [true, false, true, true];
-        let bitv = from_bools(bools);
-
-        for (act, &ex) in bitv.iter().zip(bools.iter()) {
-            assert_eq!(ex, act);
-        }
-    }
-
-    #[test]
-    fn test_bitv_set_iterator() {
-        let bools = [true, false, true, true];
-        let bitv = BitvSet::from_bitv(from_bools(bools));
-
-        let idxs: ~[uint] = bitv.iter().collect();
-        assert_eq!(idxs, ~[0, 2, 3]);
-    }
-
-    #[test]
-    fn test_bitv_set_frombitv_init() {
-        let bools = [true, false];
-        let lengths = [10, 64, 100];
-        for &b in bools.iter() {
-            for &l in lengths.iter() {
-                let bitset = BitvSet::from_bitv(Bitv::new(l, b));
-                assert_eq!(bitset.contains(&1u), b)
-                assert_eq!(bitset.contains(&(l-1u)), b)
-                assert!(!bitset.contains(&l))
-            }
-        }
-    }
-
-    #[test]
-    fn test_small_difference() {
-        let mut b1 = Bitv::new(3, false);
-        let mut b2 = Bitv::new(3, false);
-        b1.set(0, true);
-        b1.set(1, true);
-        b2.set(1, true);
-        b2.set(2, true);
-        assert!(b1.difference(&b2));
-        assert!(b1[0]);
-        assert!(!b1[1]);
-        assert!(!b1[2]);
-    }
-
-    #[test]
-    fn test_big_difference() {
-        let mut b1 = Bitv::new(100, false);
-        let mut b2 = Bitv::new(100, false);
-        b1.set(0, true);
-        b1.set(40, true);
-        b2.set(40, true);
-        b2.set(80, true);
-        assert!(b1.difference(&b2));
-        assert!(b1[0]);
-        assert!(!b1[40]);
-        assert!(!b1[80]);
-    }
-
-    #[test]
-    fn test_small_clear() {
-        let mut b = Bitv::new(14, true);
-        b.clear();
-        b.ones(|i| {
-            fail!("found 1 at {:?}", i)
-        });
-    }
-
-    #[test]
-    fn test_big_clear() {
-        let mut b = Bitv::new(140, true);
-        b.clear();
-        b.ones(|i| {
-            fail!("found 1 at {:?}", i)
-        });
-    }
-
-    #[test]
-    fn test_bitv_set_basic() {
-        let mut b = BitvSet::new();
-        assert!(b.insert(3));
-        assert!(!b.insert(3));
-        assert!(b.contains(&3));
-        assert!(b.insert(400));
-        assert!(!b.insert(400));
-        assert!(b.contains(&400));
-        assert_eq!(b.len(), 2);
-    }
-
-    #[test]
-    fn test_bitv_set_intersection() {
-        let mut a = BitvSet::new();
-        let mut b = BitvSet::new();
-
-        assert!(a.insert(11));
-        assert!(a.insert(1));
-        assert!(a.insert(3));
-        assert!(a.insert(77));
-        assert!(a.insert(103));
-        assert!(a.insert(5));
-
-        assert!(b.insert(2));
-        assert!(b.insert(11));
-        assert!(b.insert(77));
-        assert!(b.insert(5));
-        assert!(b.insert(3));
-
-        let mut i = 0;
-        let expected = [3, 5, 11, 77];
-        a.intersection(&b, |x| {
-            assert_eq!(*x, expected[i]);
-            i += 1;
-            true
-        });
-        assert_eq!(i, expected.len());
-    }
-
-    #[test]
-    fn test_bitv_set_difference() {
-        let mut a = BitvSet::new();
-        let mut b = BitvSet::new();
-
-        assert!(a.insert(1));
-        assert!(a.insert(3));
-        assert!(a.insert(5));
-        assert!(a.insert(200));
-        assert!(a.insert(500));
-
-        assert!(b.insert(3));
-        assert!(b.insert(200));
-
-        let mut i = 0;
-        let expected = [1, 5, 500];
-        a.difference(&b, |x| {
-            assert_eq!(*x, expected[i]);
-            i += 1;
-            true
-        });
-        assert_eq!(i, expected.len());
-    }
-
-    #[test]
-    fn test_bitv_set_symmetric_difference() {
-        let mut a = BitvSet::new();
-        let mut b = BitvSet::new();
-
-        assert!(a.insert(1));
-        assert!(a.insert(3));
-        assert!(a.insert(5));
-        assert!(a.insert(9));
-        assert!(a.insert(11));
-
-        assert!(b.insert(3));
-        assert!(b.insert(9));
-        assert!(b.insert(14));
-        assert!(b.insert(220));
-
-        let mut i = 0;
-        let expected = [1, 5, 11, 14, 220];
-        a.symmetric_difference(&b, |x| {
-            assert_eq!(*x, expected[i]);
-            i += 1;
-            true
-        });
-        assert_eq!(i, expected.len());
-    }
-
-    #[test]
-    fn test_bitv_set_union() {
-        let mut a = BitvSet::new();
-        let mut b = BitvSet::new();
-        assert!(a.insert(1));
-        assert!(a.insert(3));
-        assert!(a.insert(5));
-        assert!(a.insert(9));
-        assert!(a.insert(11));
-        assert!(a.insert(160));
-        assert!(a.insert(19));
-        assert!(a.insert(24));
-
-        assert!(b.insert(1));
-        assert!(b.insert(5));
-        assert!(b.insert(9));
-        assert!(b.insert(13));
-        assert!(b.insert(19));
-
-        let mut i = 0;
-        let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160];
-        a.union(&b, |x| {
-            assert_eq!(*x, expected[i]);
-            i += 1;
-            true
-        });
-        assert_eq!(i, expected.len());
-    }
-
-    #[test]
-    fn test_bitv_remove() {
-        let mut a = BitvSet::new();
-
-        assert!(a.insert(1));
-        assert!(a.remove(&1));
-
-        assert!(a.insert(100));
-        assert!(a.remove(&100));
-
-        assert!(a.insert(1000));
-        assert!(a.remove(&1000));
-        assert_eq!(a.capacity(), uint::BITS);
-    }
-
-    #[test]
-    fn test_bitv_clone() {
-        let mut a = BitvSet::new();
-
-        assert!(a.insert(1));
-        assert!(a.insert(100));
-        assert!(a.insert(1000));
-
-        let mut b = a.clone();
-
-        assert_eq!(&a, &b);
-
-        assert!(b.remove(&1));
-        assert!(a.contains(&1));
-
-        assert!(a.remove(&1000));
-        assert!(b.contains(&1000));
-    }
-
-    fn rng() -> rand::IsaacRng {
-        let seed = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
-        rand::SeedableRng::from_seed(seed)
-    }
-
-    #[bench]
-    fn bench_uint_small(b: &mut BenchHarness) {
-        let mut r = rng();
-        let mut bitv = 0 as uint;
-        b.iter(|| {
-            bitv |= (1 << ((r.next_u32() as uint) % uint::BITS));
-        })
-    }
-
-    #[bench]
-    fn bench_small_bitv_small(b: &mut BenchHarness) {
-        let mut r = rng();
-        let mut bitv = SmallBitv::new(uint::BITS);
-        b.iter(|| {
-            bitv.set((r.next_u32() as uint) % uint::BITS, true);
-        })
-    }
-
-    #[bench]
-    fn bench_big_bitv_small(b: &mut BenchHarness) {
-        let mut r = rng();
-        let mut bitv = BigBitv::new(~[0]);
-        b.iter(|| {
-            bitv.set((r.next_u32() as uint) % uint::BITS, true);
-        })
-    }
-
-    #[bench]
-    fn bench_big_bitv_big(b: &mut BenchHarness) {
-        let mut r = rng();
-        let mut storage = ~[];
-        storage.grow(BENCH_BITS / uint::BITS, &0u);
-        let mut bitv = BigBitv::new(storage);
-        b.iter(|| {
-            bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
-        })
-    }
-
-    #[bench]
-    fn bench_bitv_big(b: &mut BenchHarness) {
-        let mut r = rng();
-        let mut bitv = Bitv::new(BENCH_BITS, false);
-        b.iter(|| {
-            bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
-        })
-    }
-
-    #[bench]
-    fn bench_bitv_small(b: &mut BenchHarness) {
-        let mut r = rng();
-        let mut bitv = Bitv::new(uint::BITS, false);
-        b.iter(|| {
-            bitv.set((r.next_u32() as uint) % uint::BITS, true);
-        })
-    }
-
-    #[bench]
-    fn bench_bitv_set_small(b: &mut BenchHarness) {
-        let mut r = rng();
-        let mut bitv = BitvSet::new();
-        b.iter(|| {
-            bitv.insert((r.next_u32() as uint) % uint::BITS);
-        })
-    }
-
-    #[bench]
-    fn bench_bitv_set_big(b: &mut BenchHarness) {
-        let mut r = rng();
-        let mut bitv = BitvSet::new();
-        b.iter(|| {
-            bitv.insert((r.next_u32() as uint) % BENCH_BITS);
-        })
-    }
-
-    #[bench]
-    fn bench_bitv_big_union(b: &mut BenchHarness) {
-        let mut b1 = Bitv::new(BENCH_BITS, false);
-        let b2 = Bitv::new(BENCH_BITS, false);
-        b.iter(|| {
-            b1.union(&b2);
-        })
-    }
-
-    #[bench]
-    fn bench_btv_small_iter(b: &mut BenchHarness) {
-        let bitv = Bitv::new(uint::BITS, false);
-        b.iter(|| {
-            let mut _sum = 0;
-            for pres in bitv.iter() {
-                _sum += pres as uint;
-            }
-        })
-    }
-
-    #[bench]
-    fn bench_bitv_big_iter(b: &mut BenchHarness) {
-        let bitv = Bitv::new(BENCH_BITS, false);
-        b.iter(|| {
-            let mut _sum = 0;
-            for pres in bitv.iter() {
-                _sum += pres as uint;
-            }
-        })
-    }
-
-    #[bench]
-    fn bench_bitvset_iter(b: &mut BenchHarness) {
-        let bitv = BitvSet::from_bitv(from_fn(BENCH_BITS,
-                                              |idx| {idx % 3 == 0}));
-        b.iter(|| {
-            let mut _sum = 0;
-            for idx in bitv.iter() {
-                _sum += idx;
-            }
-        })
-    }
-}
diff --git a/src/libextra/btree.rs b/src/libextra/btree.rs
deleted file mode 100644
index 791673d75bb..00000000000
--- a/src/libextra/btree.rs
+++ /dev/null
@@ -1,592 +0,0 @@
-// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-//
-// btree.rs
-//
-
-//! Starting implementation of a btree for rust.
-//! Structure inspired by github user davidhalperin's gist.
-
-#[allow(dead_code)];
-#[allow(unused_variable)];
-
-///A B-tree contains a root node (which contains a vector of elements),
-///a length (the height of the tree), and lower and upper bounds on the
-///number of elements that a given node can contain.
-#[allow(missing_doc)]
-pub struct BTree<K, V> {
-    priv root: Node<K, V>,
-    priv len: uint,
-    priv lower_bound: uint,
-    priv upper_bound: uint
-}
-
-//We would probably want to remove the dependence on the Clone trait in the future.
-//It is here as a crutch to ensure values can be passed around through the tree's nodes
-//especially during insertions and deletions.
-//Using the swap or replace methods is one option for replacing dependence on Clone, or
-//changing the way in which the BTree is stored could also potentially work.
-impl<K: TotalOrd, V> BTree<K, V> {
-
-    ///Returns new BTree with root node (leaf) and user-supplied lower bound
-    pub fn new(k: K, v: V, lb: uint) -> BTree<K, V> {
-        BTree {
-            root: Node::new_leaf(~[LeafElt::new(k, v)]),
-            len: 1,
-            lower_bound: lb,
-            upper_bound: 2 * lb
-        }
-    }
-
-    ///Helper function for clone: returns new BTree with supplied root node,
-    ///length, and lower bound.  For use when the length is known already.
-    fn new_with_node_len(n: Node<K, V>,
-                         length: uint,
-                         lb: uint) -> BTree<K, V> {
-        BTree {
-            root: n,
-            len: length,
-            lower_bound: lb,
-            upper_bound: 2 * lb
-        }
-    }
-
-
-    ///Stub for add method in progress.
-    pub fn add(self, k: K, v: V) -> BTree<K, V> {
-        //replace(&self.root,self.root.add(k, v));
-        return BTree::new(k, v, 2);
-    }
-}
-
-impl<K: TotalOrd, V: Clone> BTree<K, V> {
-
-    ///Returns the value of a given key, which may not exist in the tree.
-    ///Calls the root node's get method.
-    pub fn get(self, k: K) -> Option<V> {
-        return self.root.get(k);
-    }
-}
-
-impl<K: Clone + TotalOrd, V: Clone> Clone for BTree<K, V> {
-    ///Implements the Clone trait for the BTree.
-    ///Uses a helper function/constructor to produce a new BTree.
-    fn clone(&self) -> BTree<K, V> {
-        BTree::new_with_node_len(self.root.clone(), self.len, self.lower_bound)
-    }
-}
-
-
-impl<K: TotalOrd, V: TotalEq> TotalEq for BTree<K, V> {
-    ///Testing equality on BTrees by comparing the root.
-    fn equals(&self, other: &BTree<K, V>) -> bool {
-        self.root.cmp(&other.root) == Equal
-    }
-}
-
-impl<K: TotalOrd, V: TotalEq> TotalOrd for BTree<K, V> {
-    ///Returns an ordering based on the root nodes of each BTree.
-    fn cmp(&self, other: &BTree<K, V>) -> Ordering {
-        self.root.cmp(&other.root)
-    }
-}
-
-impl<K: ToStr + TotalOrd, V: ToStr> ToStr for BTree<K, V> {
-    ///Returns a string representation of the BTree
-    fn to_str(&self) -> ~str {
-        let ret = self.root.to_str();
-        ret
-    }
-}
-
-
-//Node types
-//A node is either a LeafNode or a BranchNode, which contain either a Leaf or a Branch.
-//Branches contain BranchElts, which contain a left child (another node) and a key-value
-//pair.  Branches also contain the rightmost child of the elements in the array.
-//Leaves contain LeafElts, which do not have children.
-enum Node<K, V> {
-    LeafNode(Leaf<K, V>),
-    BranchNode(Branch<K, V>)
-}
-
-
-//Node functions/methods
-impl<K: TotalOrd, V> Node<K, V> {
-
-    ///Differentiates between leaf and branch nodes.
-    fn is_leaf(&self) -> bool {
-        match self{
-            &LeafNode(..) => true,
-            &BranchNode(..) => false
-        }
-    }
-
-    ///Creates a new leaf node given a vector of elements.
-    fn new_leaf(vec: ~[LeafElt<K, V>]) -> Node<K,V> {
-        LeafNode(Leaf::new(vec))
-    }
-
-
-    ///Creates a new branch node given a vector of an elements and a pointer to a rightmost child.
-    fn new_branch(vec: ~[BranchElt<K, V>], right: ~Node<K, V>) -> Node<K, V> {
-        BranchNode(Branch::new(vec, right))
-    }
-
-    ///A placeholder/stub for add
-    ///Currently returns a leaf node with a single value (the added one)
-    fn add(self, k: K, v: V) -> Node<K, V> {
-        return Node::new_leaf(~[LeafElt::new(k, v)]);
-    }
-}
-
-impl<K: TotalOrd, V: Clone> Node<K, V> {
-    ///Returns the corresponding value to the provided key.
-    ///get() is called in different ways on a branch or a leaf.
-    fn get(&self, k: K) -> Option<V> {
-        match *self {
-            LeafNode(ref leaf) => return leaf.get(k),
-            BranchNode(ref branch) => return branch.get(k)
-        }
-    }
-}
-
-impl<K: Clone + TotalOrd, V: Clone> Clone for Node<K, V> {
-    ///Returns a new node based on whether or not it is a branch or a leaf.
-    fn clone(&self) -> Node<K, V> {
-        match *self {
-            LeafNode(ref leaf) => {
-                Node::new_leaf(leaf.elts.clone())
-            }
-            BranchNode(ref branch) => {
-                Node::new_branch(branch.elts.clone(),
-                                 branch.rightmost_child.clone())
-            }
-        }
-    }
-}
-
-impl<K: TotalOrd, V: TotalEq> TotalEq for Node<K, V> {
-    ///Returns whether two nodes are equal
-    fn equals(&self, other: &Node<K, V>) -> bool{
-        match *self{
-            BranchNode(ref branch) => {
-                match *other{
-                    BranchNode(ref branch2) => branch.cmp(branch2) == Equal,
-                    LeafNode(ref leaf) => false
-                }
-            }
-
-            LeafNode(ref leaf) => {
-                match *other{
-                    LeafNode(ref leaf2) => leaf.cmp(leaf2) == Equal,
-                    BranchNode(ref branch) => false
-                }
-            }
-        }
-    }
-}
-
-impl<K: TotalOrd, V: TotalEq> TotalOrd for Node<K, V> {
-    ///Implementation of TotalOrd for Nodes.
-    fn cmp(&self, other: &Node<K, V>) -> Ordering {
-        match *self {
-            LeafNode(ref leaf) => {
-                match *other {
-                    LeafNode(ref leaf2) => leaf.cmp(leaf2),
-                    BranchNode(_) => Less
-                }
-            }
-            BranchNode(ref branch) => {
-                match *other {
-                    BranchNode(ref branch2) => branch.cmp(branch2),
-                    LeafNode(_) => Greater
-                }
-            }
-        }
-    }
-}
-
-impl<K: ToStr + TotalOrd, V: ToStr> ToStr for Node<K, V> {
-    ///Returns a string representation of a Node.
-    ///The Branch's to_str() is not implemented yet.
-    fn to_str(&self) -> ~str {
-        match *self {
-            LeafNode(ref leaf) => leaf.to_str(),
-            BranchNode(ref branch) => branch.to_str()
-        }
-    }
-}
-
-
-//A leaf is a vector with elements that contain no children.  A leaf also
-//does not contain a rightmost child.
-struct Leaf<K, V> {
-    elts: ~[LeafElt<K, V>]
-}
-
-//Vector of values with children, plus a rightmost child (greater than all)
-struct Branch<K, V> {
-    elts: ~[BranchElt<K,V>],
-    rightmost_child: ~Node<K, V>
-}
-
-
-impl<K: TotalOrd, V> Leaf<K, V> {
-    ///Creates a new Leaf from a vector of LeafElts.
-    fn new(vec: ~[LeafElt<K, V>]) -> Leaf<K, V> {
-        Leaf {
-            elts: vec
-        }
-    }
-
-    ///Placeholder for add method in progress.
-    ///Currently returns a new Leaf containing a single LeafElt.
-    fn add(&self, k: K, v: V) -> Node<K, V> {
-        return Node::new_leaf(~[LeafElt::new(k, v)]);
-    }
-
-}
-
-impl<K: TotalOrd, V: Clone> Leaf<K, V> {
-    ///Returns the corresponding value to the supplied key.
-    fn get(&self, k: K) -> Option<V> {
-        for s in self.elts.iter() {
-            let order = s.key.cmp(&k);
-            match order {
-                Equal => return Some(s.value.clone()),
-                _ => {}
-            }
-        }
-        return None;
-    }
-}
-
-impl<K: Clone + TotalOrd, V: Clone> Clone for Leaf<K, V> {
-    ///Returns a new Leaf with the same elts.
-    fn clone(&self) -> Leaf<K, V> {
-        Leaf::new(self.elts.clone())
-    }
-}
-
-impl<K: TotalOrd, V: TotalEq> TotalEq for Leaf<K, V> {
-    ///Implementation of equals function for leaves that compares LeafElts.
-    fn equals(&self, other: &Leaf<K, V>) -> bool {
-        self.elts.equals(&other.elts)
-    }
-}
-
-impl<K: TotalOrd, V: TotalEq> TotalOrd for Leaf<K, V> {
-    ///Returns an ordering based on the first element of each Leaf.
-    fn cmp(&self, other: &Leaf<K, V>) -> Ordering {
-        if self.elts.len() > other.elts.len() {
-            return Greater;
-        }
-        if self.elts.len() < other.elts.len() {
-            return Less;
-        }
-        self.elts[0].cmp(&other.elts[0])
-    }
-}
-
-
-impl<K: ToStr + TotalOrd, V: ToStr> ToStr for Leaf<K, V> {
-    ///Returns a string representation of a Leaf.
-    fn to_str(&self) -> ~str {
-        self.elts.iter().map(|s| s.to_str()).to_owned_vec().connect(" // ")
-    }
-}
-
-
-impl<K: TotalOrd, V> Branch<K, V> {
-    ///Creates a new Branch from a vector of BranchElts and a rightmost child (a node).
-    fn new(vec: ~[BranchElt<K, V>], right: ~Node<K, V>) -> Branch<K, V> {
-        Branch {
-            elts: vec,
-            rightmost_child: right
-        }
-    }
-
-    ///Placeholder for add method in progress
-    fn add(&self, k: K, v: V) -> Node<K, V> {
-        return Node::new_leaf(~[LeafElt::new(k, v)]);
-    }
-}
-
-impl<K: TotalOrd, V: Clone> Branch<K, V> {
-    ///Returns the corresponding value to the supplied key.
-    ///If the key is not there, find the child that might hold it.
-    fn get(&self, k: K) -> Option<V> {
-        for s in self.elts.iter() {
-            let order = s.key.cmp(&k);
-            match order {
-                Less => return s.left.get(k),
-                Equal => return Some(s.value.clone()),
-                _ => {}
-            }
-        }
-        self.rightmost_child.get(k)
-    }
-}
-
-impl<K: Clone + TotalOrd, V: Clone> Clone for Branch<K, V> {
-    ///Returns a new branch using the clone methods of the Branch's internal variables.
-    fn clone(&self) -> Branch<K, V> {
-        Branch::new(self.elts.clone(), self.rightmost_child.clone())
-    }
-}
-
-impl<K: TotalOrd, V: TotalEq> TotalEq for Branch<K, V> {
-    ///Equals function for Branches--compares all the elements in each branch
-    fn equals(&self, other: &Branch<K, V>) -> bool {
-        self.elts.equals(&other.elts)
-    }
-}
-
-impl<K: TotalOrd, V: TotalEq> TotalOrd for Branch<K, V> {
-    ///Compares the first elements of two branches to determine an ordering
-    fn cmp(&self, other: &Branch<K, V>) -> Ordering {
-        if self.elts.len() > other.elts.len() {
-            return Greater;
-        }
-        if self.elts.len() < other.elts.len() {
-            return Less;
-        }
-        self.elts[0].cmp(&other.elts[0])
-    }
-}
-
-impl<K: ToStr + TotalOrd, V: ToStr> ToStr for Branch<K, V> {
-    ///Returns a string representation of a Branch.
-    fn to_str(&self) -> ~str {
-        let mut ret = self.elts.iter().map(|s| s.to_str()).to_owned_vec().connect(" // ");
-        ret.push_str(" // ");
-        ret.push_str(self.rightmost_child.to_str());
-        ret
-    }
-}
-
-//A LeafElt containts no left child, but a key-value pair.
-struct LeafElt<K, V> {
-    key: K,
-    value: V
-}
-
-//A BranchElt has a left child in addition to a key-value pair.
-struct BranchElt<K, V> {
-    left: Node<K, V>,
-    key: K,
-    value: V
-}
-
-impl<K: TotalOrd, V> LeafElt<K, V> {
-    ///Creates a new LeafElt from a supplied key-value pair.
-    fn new(k: K, v: V) -> LeafElt<K, V> {
-        LeafElt {
-            key: k,
-            value: v
-        }
-    }
-
-    ///Compares another LeafElt against itself and determines whether
-    ///the original LeafElt's key is less than the other one's key.
-    fn less_than(&self, other: LeafElt<K, V>) -> bool {
-        let order = self.key.cmp(&other.key);
-        match order {
-            Less => true,
-            _ => false
-        }
-    }
-
-    ///Compares another LeafElt against itself and determines whether
-    ///the original LeafElt's key is greater than the other one's key.
-    fn greater_than(&self, other: LeafElt<K, V>) -> bool {
-        let order = self.key.cmp(&other.key);
-        match order {
-            Greater => true,
-            _ => false
-        }
-    }
-
-    ///Takes a key and determines whether its own key and the supplied key
-    ///are the same.
-    fn has_key(&self, other: K) -> bool {
-        let order = self.key.cmp(&other);
-        match order {
-            Equal => true,
-            _ => false
-        }
-    }
-}
-
-impl<K: Clone + TotalOrd, V: Clone> Clone for LeafElt<K, V> {
-    ///Returns a new LeafElt by cloning the key and value.
-    fn clone(&self) -> LeafElt<K, V> {
-        LeafElt::new(self.key.clone(), self.value.clone())
-    }
-}
-
-impl<K: TotalOrd, V: TotalEq> TotalEq for LeafElt<K, V> {
-    ///TotalEq for LeafElts
-    fn equals(&self, other: &LeafElt<K, V>) -> bool {
-        self.key.equals(&other.key) && self.value.equals(&other.value)
-    }
-}
-
-impl<K: TotalOrd, V: TotalEq> TotalOrd for LeafElt<K, V> {
-    ///Returns an ordering based on the keys of the LeafElts.
-    fn cmp(&self, other: &LeafElt<K, V>) -> Ordering {
-        self.key.cmp(&other.key)
-    }
-}
-
-impl<K: ToStr + TotalOrd, V: ToStr> ToStr for LeafElt<K, V> {
-    ///Returns a string representation of a LeafElt.
-    fn to_str(&self) -> ~str {
-        format!("Key: {}, value: {};",
-            self.key.to_str(), self.value.to_str())
-    }
-}
-
-impl<K: TotalOrd, V> BranchElt<K, V> {
-    ///Creates a new BranchElt from a supplied key, value, and left child.
-    fn new(k: K, v: V, n: Node<K, V>) -> BranchElt<K, V> {
-        BranchElt {
-            left: n,
-            key: k,
-            value: v
-        }
-    }
-
-    ///Placeholder for add method in progress.
-    ///Overall implementation will determine the actual return value of this method.
-    fn add(&self, k: K, v: V) -> LeafElt<K, V> {
-        return LeafElt::new(k, v);
-    }
-}
-
-
-impl<K: Clone + TotalOrd, V: Clone> Clone for BranchElt<K, V> {
-    ///Returns a new BranchElt by cloning the key, value, and left child.
-    fn clone(&self) -> BranchElt<K, V> {
-        BranchElt::new(self.key.clone(),
-                       self.value.clone(),
-                       self.left.clone())
-    }
-}
-
-impl<K: TotalOrd, V: TotalEq> TotalEq for BranchElt<K, V>{
-    ///TotalEq for BranchElts
-    fn equals(&self, other: &BranchElt<K, V>) -> bool {
-        self.key.equals(&other.key)&&self.value.equals(&other.value)
-    }
-}
-
-impl<K: TotalOrd, V: TotalEq> TotalOrd for BranchElt<K, V> {
-    ///Fulfills TotalOrd for BranchElts
-    fn cmp(&self, other: &BranchElt<K, V>) -> Ordering {
-        self.key.cmp(&other.key)
-    }
-}
-
-impl<K: ToStr + TotalOrd, V: ToStr> ToStr for BranchElt<K, V> {
-    ///Returns string containing key, value, and child (which should recur to a leaf)
-    ///Consider changing in future to be more readable.
-    fn to_str(&self) -> ~str {
-        format!("Key: {}, value: {}, child: {};",
-            self.key.to_str(), self.value.to_str(), self.left.to_str())
-    }
-}
-
-#[cfg(test)]
-mod test_btree {
-
-    use super::{BTree, LeafElt};
-
-    //Tests the functionality of the add methods (which are unfinished).
-    /*#[test]
-    fn add_test(){
-        let b = BTree::new(1, ~"abc", 2);
-        let is_add = b.add(2, ~"xyz");
-        assert!(is_add);
-    }*/
-
-    //Tests the functionality of the get method.
-    #[test]
-    fn get_test() {
-        let b = BTree::new(1, ~"abc", 2);
-        let val = b.get(1);
-        assert_eq!(val, Some(~"abc"));
-    }
-
-    //Tests the LeafElt's less_than() method.
-    #[test]
-    fn leaf_lt() {
-        let l1 = LeafElt::new(1, ~"abc");
-        let l2 = LeafElt::new(2, ~"xyz");
-        assert!(l1.less_than(l2));
-    }
-
-
-    //Tests the LeafElt's greater_than() method.
-    #[test]
-    fn leaf_gt() {
-        let l1 = LeafElt::new(1, ~"abc");
-        let l2 = LeafElt::new(2, ~"xyz");
-        assert!(l2.greater_than(l1));
-    }
-
-    //Tests the LeafElt's has_key() method.
-    #[test]
-    fn leaf_hk() {
-        let l1 = LeafElt::new(1, ~"abc");
-        assert!(l1.has_key(1));
-    }
-
-    //Tests the BTree's clone() method.
-    #[test]
-    fn btree_clone_test() {
-        let b = BTree::new(1, ~"abc", 2);
-        let b2 = b.clone();
-        assert!(b.root.equals(&b2.root))
-    }
-
-    //Tests the BTree's cmp() method when one node is "less than" another.
-    #[test]
-    fn btree_cmp_test_less() {
-        let b = BTree::new(1, ~"abc", 2);
-        let b2 = BTree::new(2, ~"bcd", 2);
-        assert!(&b.cmp(&b2) == &Less)
-    }
-
-    //Tests the BTree's cmp() method when two nodes are equal.
-    #[test]
-    fn btree_cmp_test_eq() {
-        let b = BTree::new(1, ~"abc", 2);
-        let b2 = BTree::new(1, ~"bcd", 2);
-        assert!(&b.cmp(&b2) == &Equal)
-    }
-
-    //Tests the BTree's cmp() method when one node is "greater than" another.
-    #[test]
-    fn btree_cmp_test_greater() {
-        let b = BTree::new(1, ~"abc", 2);
-        let b2 = BTree::new(2, ~"bcd", 2);
-        assert!(&b2.cmp(&b) == &Greater)
-    }
-
-    //Tests the BTree's to_str() method.
-    #[test]
-    fn btree_tostr_test() {
-        let b = BTree::new(1, ~"abc", 2);
-        assert_eq!(b.to_str(), ~"Key: 1, value: abc;")
-    }
-
-}
diff --git a/src/libextra/container.rs b/src/libextra/container.rs
deleted file mode 100644
index 0ba00510ed8..00000000000
--- a/src/libextra/container.rs
+++ /dev/null
@@ -1,122 +0,0 @@
-// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-//! Container traits for extra
-
-use std::container::Mutable;
-
-/// A double-ended sequence that allows querying, insertion and deletion at both ends.
-pub trait Deque<T> : Mutable {
-    /// Provide a reference to the front element, or None if the sequence is empty
-    fn front<'a>(&'a self) -> Option<&'a T>;
-
-    /// Provide a mutable reference to the front element, or None if the sequence is empty
-    fn front_mut<'a>(&'a mut self) -> Option<&'a mut T>;
-
-    /// Provide a reference to the back element, or None if the sequence is empty
-    fn back<'a>(&'a self) -> Option<&'a T>;
-
-    /// Provide a mutable reference to the back element, or None if the sequence is empty
-    fn back_mut<'a>(&'a mut self) -> Option<&'a mut T>;
-
-    /// Insert an element first in the sequence
-    fn push_front(&mut self, elt: T);
-
-    /// Insert an element last in the sequence
-    fn push_back(&mut self, elt: T);
-
-    /// Remove the last element and return it, or None if the sequence is empty
-    fn pop_back(&mut self) -> Option<T>;
-
-    /// Remove the first element and return it, or None if the sequence is empty
-    fn pop_front(&mut self) -> Option<T>;
-}
-
-#[cfg(test)]
-pub mod bench {
-    use std::container::MutableMap;
-    use std::{vec, rand};
-    use std::rand::Rng;
-    use test::BenchHarness;
-
-    pub fn insert_rand_n<M:MutableMap<uint,uint>>(n: uint,
-                                                  map: &mut M,
-                                                  bh: &mut BenchHarness) {
-        // setup
-        let mut rng = rand::XorShiftRng::new();
-
-        map.clear();
-        for _ in range(0, n) {
-            map.insert(rng.gen::<uint>() % n, 1);
-        }
-
-        // measure
-        bh.iter(|| {
-            let k = rng.gen::<uint>() % n;
-            map.insert(k, 1);
-            map.remove(&k);
-        })
-    }
-
-    pub fn insert_seq_n<M:MutableMap<uint,uint>>(n: uint,
-                                                 map: &mut M,
-                                                 bh: &mut BenchHarness) {
-        // setup
-        map.clear();
-        for i in range(0u, n) {
-            map.insert(i*2, 1);
-        }
-
-        // measure
-        let mut i = 1;
-        bh.iter(|| {
-            map.insert(i, 1);
-            map.remove(&i);
-            i = (i + 2) % n;
-        })
-    }
-
-    pub fn find_rand_n<M:MutableMap<uint,uint>>(n: uint,
-                                                map: &mut M,
-                                                bh: &mut BenchHarness) {
-        // setup
-        let mut rng = rand::XorShiftRng::new();
-        let mut keys = vec::from_fn(n, |_| rng.gen::<uint>() % n);
-
-        for k in keys.iter() {
-            map.insert(*k, 1);
-        }
-
-        rng.shuffle_mut(keys);
-
-        // measure
-        let mut i = 0;
-        bh.iter(|| {
-            map.find(&(keys[i]));
-            i = (i + 1) % n;
-        })
-    }
-
-    pub fn find_seq_n<M:MutableMap<uint,uint>>(n: uint,
-                                               map: &mut M,
-                                               bh: &mut BenchHarness) {
-        // setup
-        for i in range(0u, n) {
-            map.insert(i, 1);
-        }
-
-        // measure
-        let mut i = 0;
-        bh.iter(|| {
-            map.find(&i);
-            i = (i + 1) % n;
-        })
-     }
-}
diff --git a/src/libextra/dlist.rs b/src/libextra/dlist.rs
deleted file mode 100644
index 88df73845d0..00000000000
--- a/src/libextra/dlist.rs
+++ /dev/null
@@ -1,1204 +0,0 @@
-// Copyright 2012-2013 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-//! A doubly-linked list with owned nodes.
-//!
-//! The DList allows pushing and popping elements at either end.
-//!
-//! DList implements the trait Deque. It should be imported with `use
-//! extra::container::Deque`.
-
-
-// DList is constructed like a singly-linked list over the field `next`.
-// including the last link being None; each Node owns its `next` field.
-//
-// Backlinks over DList::prev are raw pointers that form a full chain in
-// the reverse direction.
-
-use std::cast;
-use std::ptr;
-use std::util;
-use std::iter::Rev;
-use std::iter;
-
-use container::Deque;
-
-use serialize::{Encodable, Decodable, Encoder, Decoder};
-
-/// A doubly-linked list.
-pub struct DList<T> {
-    priv length: uint,
-    priv list_head: Link<T>,
-    priv list_tail: Rawlink<Node<T>>,
-}
-
-type Link<T> = Option<~Node<T>>;
-struct Rawlink<T> { p: *mut T }
-
-struct Node<T> {
-    next: Link<T>,
-    prev: Rawlink<Node<T>>,
-    value: T,
-}
-
-/// Double-ended DList iterator
-pub struct Items<'a, T> {
-    priv head: &'a Link<T>,
-    priv tail: Rawlink<Node<T>>,
-    priv nelem: uint,
-}
-
-// FIXME #11820: the &'a Option<> of the Link stops clone working.
-impl<'a, T> Clone for Items<'a, T> {
-    fn clone(&self) -> Items<'a, T> { *self }
-}
-
-/// Double-ended mutable DList iterator
-pub struct MutItems<'a, T> {
-    priv list: &'a mut DList<T>,
-    priv head: Rawlink<Node<T>>,
-    priv tail: Rawlink<Node<T>>,
-    priv nelem: uint,
-}
-
-/// DList consuming iterator
-#[deriving(Clone)]
-pub struct MoveItems<T> {
-    priv list: DList<T>
-}
-
-/// Rawlink is a type like Option<T> but for holding a raw pointer
-impl<T> Rawlink<T> {
-    /// Like Option::None for Rawlink
-    fn none() -> Rawlink<T> {
-        Rawlink{p: ptr::mut_null()}
-    }
-
-    /// Like Option::Some for Rawlink
-    fn some(n: &mut T) -> Rawlink<T> {
-        Rawlink{p: ptr::to_mut_unsafe_ptr(n)}
-    }
-
-    /// Convert the `Rawlink` into an Option value
-    fn resolve_immut(&self) -> Option<&T> {
-        unsafe { self.p.to_option() }
-    }
-
-    /// Convert the `Rawlink` into an Option value
-    fn resolve(&mut self) -> Option<&mut T> {
-        if self.p.is_null() {
-            None
-        } else {
-            Some(unsafe { cast::transmute(self.p) })
-        }
-    }
-
-    /// Return the `Rawlink` and replace with `Rawlink::none()`
-    fn take(&mut self) -> Rawlink<T> {
-        util::replace(self, Rawlink::none())
-    }
-}
-
-impl<T> Clone for Rawlink<T> {
-    #[inline]
-    fn clone(&self) -> Rawlink<T> {
-        Rawlink{p: self.p}
-    }
-}
-
-impl<T> Node<T> {
-    fn new(v: T) -> Node<T> {
-        Node{value: v, next: None, prev: Rawlink::none()}
-    }
-}
-
-/// Set the .prev field on `next`, then return `Some(next)`
-fn link_with_prev<T>(mut next: ~Node<T>, prev: Rawlink<Node<T>>) -> Link<T> {
-    next.prev = prev;
-    Some(next)
-}
-
-impl<T> Container for DList<T> {
-    /// O(1)
-    #[inline]
-    fn is_empty(&self) -> bool {
-        self.list_head.is_none()
-    }
-    /// O(1)
-    #[inline]
-    fn len(&self) -> uint {
-        self.length
-    }
-}
-
-impl<T> Mutable for DList<T> {
-    /// Remove all elements from the DList
-    ///
-    /// O(N)
-    #[inline]
-    fn clear(&mut self) {
-        *self = DList::new()
-    }
-}
-
-// private methods
-impl<T> DList<T> {
-    /// Add a Node first in the list
-    #[inline]
-    fn push_front_node(&mut self, mut new_head: ~Node<T>) {
-        match self.list_head {
-            None => {
-                self.list_tail = Rawlink::some(new_head);
-                self.list_head = link_with_prev(new_head, Rawlink::none());
-            }
-            Some(ref mut head) => {
-                new_head.prev = Rawlink::none();
-                head.prev = Rawlink::some(new_head);
-                util::swap(head, &mut new_head);
-                head.next = Some(new_head);
-            }
-        }
-        self.length += 1;
-    }
-
-    /// Remove the first Node and return it, or None if the list is empty
-    #[inline]
-    fn pop_front_node(&mut self) -> Option<~Node<T>> {
-        self.list_head.take().map(|mut front_node| {
-            self.length -= 1;
-            match front_node.next.take() {
-                Some(node) => self.list_head = link_with_prev(node, Rawlink::none()),
-                None => self.list_tail = Rawlink::none()
-            }
-            front_node
-        })
-    }
-
-    /// Add a Node last in the list
-    #[inline]
-    fn push_back_node(&mut self, mut new_tail: ~Node<T>) {
-        match self.list_tail.resolve() {
-            None => return self.push_front_node(new_tail),
-            Some(tail) => {
-                self.list_tail = Rawlink::some(new_tail);
-                tail.next = link_with_prev(new_tail, Rawlink::some(tail));
-            }
-        }
-        self.length += 1;
-    }
-
-    /// Remove the last Node and return it, or None if the list is empty
-    #[inline]
-    fn pop_back_node(&mut self) -> Option<~Node<T>> {
-        self.list_tail.resolve().map_or(None, |tail| {
-            self.length -= 1;
-            self.list_tail = tail.prev;
-            match tail.prev.resolve() {
-                None => self.list_head.take(),
-                Some(tail_prev) => tail_prev.next.take()
-            }
-        })
-    }
-}
-
-impl<T> Deque<T> for DList<T> {
-    /// Provide a reference to the front element, or None if the list is empty
-    #[inline]
-    fn front<'a>(&'a self) -> Option<&'a T> {
-        self.list_head.as_ref().map(|head| &head.value)
-    }
-
-    /// Provide a mutable reference to the front element, or None if the list is empty
-    #[inline]
-    fn front_mut<'a>(&'a mut self) -> Option<&'a mut T> {
-        self.list_head.as_mut().map(|head| &mut head.value)
-    }
-
-    /// Provide a reference to the back element, or None if the list is empty
-    #[inline]
-    fn back<'a>(&'a self) -> Option<&'a T> {
-        let tmp = self.list_tail.resolve_immut(); // FIXME: #3511: shouldn't need variable
-        tmp.as_ref().map(|tail| &tail.value)
-    }
-
-    /// Provide a mutable reference to the back element, or None if the list is empty
-    #[inline]
-    fn back_mut<'a>(&'a mut self) -> Option<&'a mut T> {
-        let tmp: Option<&'a mut Node<T>> =
-            self.list_tail.resolve(); // FIXME: #3511: shouldn't need variable
-        tmp.map(|tail| &mut tail.value)
-    }
-
-    /// Add an element first in the list
-    ///
-    /// O(1)
-    fn push_front(&mut self, elt: T) {
-        self.push_front_node(~Node::new(elt))
-    }
-
-    /// Remove the first element and return it, or None if the list is empty
-    ///
-    /// O(1)
-    fn pop_front(&mut self) -> Option<T> {
-        self.pop_front_node().map(|~Node{value, ..}| value)
-    }
-
-    /// Add an element last in the list
-    ///
-    /// O(1)
-    fn push_back(&mut self, elt: T) {
-        self.push_back_node(~Node::new(elt))
-    }
-
-    /// Remove the last element and return it, or None if the list is empty
-    ///
-    /// O(1)
-    fn pop_back(&mut self) -> Option<T> {
-        self.pop_back_node().map(|~Node{value, ..}| value)
-    }
-}
-
-impl<T> DList<T> {
-    /// Create an empty DList
-    #[inline]
-    pub fn new() -> DList<T> {
-        DList{list_head: None, list_tail: Rawlink::none(), length: 0}
-    }
-
-    /// Move the last element to the front of the list.
-    ///
-    /// If the list is empty, do nothing.
-    #[inline]
-    pub fn rotate_forward(&mut self) {
-        self.pop_back_node().map(|tail| {
-            self.push_front_node(tail)
-        });
-    }
-
-    /// Move the first element to the back of the list.
-    ///
-    /// If the list is empty, do nothing.
-    #[inline]
-    pub fn rotate_backward(&mut self) {
-        self.pop_front_node().map(|head| {
-            self.push_back_node(head)
-        });
-    }
-
-    /// Add all elements from `other` to the end of the list
-    ///
-    /// O(1)
-    pub fn append(&mut self, mut other: DList<T>) {
-        match self.list_tail.resolve() {
-            None => *self = other,
-            Some(tail) => {
-                // Carefully empty `other`.
-                let o_tail = other.list_tail.take();
-                let o_length = other.length;
-                match other.list_head.take() {
-                    None => return,
-                    Some(node) => {
-                        tail.next = link_with_prev(node, self.list_tail);
-                        self.list_tail = o_tail;
-                        self.length += o_length;
-                    }
-                }
-            }
-        }
-    }
-
-    /// Add all elements from `other` to the beginning of the list
-    ///
-    /// O(1)
-    #[inline]
-    pub fn prepend(&mut self, mut other: DList<T>) {
-        util::swap(self, &mut other);
-        self.append(other);
-    }
-
-    /// Insert `elt` before the first `x` in the list where `f(x, elt)` is true,
-    /// or at the end.
-    ///
-    /// O(N)
-    pub fn insert_when(&mut self, elt: T, f: |&T, &T| -> bool) {
-        {
-            let mut it = self.mut_iter();
-            loop {
-                match it.peek_next() {
-                    None => break,
-                    Some(x) => if f(x, &elt) { break }
-                }
-                it.next();
-            }
-            it.insert_next(elt);
-        }
-    }
-
-    /// Merge DList `other` into this DList, using the function `f`.
-    /// Iterate the both DList with `a` from self and `b` from `other`, and
-    /// put `a` in the result if `f(a, b)` is true, else `b`.
-    ///
-    /// O(max(N, M))
-    pub fn merge(&mut self, mut other: DList<T>, f: |&T, &T| -> bool) {
-        {
-            let mut it = self.mut_iter();
-            loop {
-                let take_a = match (it.peek_next(), other.front()) {
-                    (_   , None) => return,
-                    (None, _   ) => break,
-                    (Some(ref mut x), Some(y)) => f(*x, y),
-                };
-                if take_a {
-                    it.next();
-                } else {
-                    it.insert_next_node(other.pop_front_node().unwrap());
-                }
-            }
-        }
-        self.append(other);
-    }
-
-
-    /// Provide a forward iterator
-    #[inline]
-    pub fn iter<'a>(&'a self) -> Items<'a, T> {
-        Items{nelem: self.len(), head: &self.list_head, tail: self.list_tail}
-    }
-
-    /// Provide a reverse iterator
-    #[inline]
-    pub fn rev_iter<'a>(&'a self) -> Rev<Items<'a, T>> {
-        self.iter().rev()
-    }
-
-    /// Provide a forward iterator with mutable references
-    #[inline]
-    pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T> {
-        let head_raw = match self.list_head {
-            Some(ref mut h) => Rawlink::some(*h),
-            None => Rawlink::none(),
-        };
-        MutItems{
-            nelem: self.len(),
-            head: head_raw,
-            tail: self.list_tail,
-            list: self
-        }
-    }
-    /// Provide a reverse iterator with mutable references
-    #[inline]
-    pub fn mut_rev_iter<'a>(&'a mut self) -> Rev<MutItems<'a, T>> {
-        self.mut_iter().rev()
-    }
-
-
-    /// Consume the list into an iterator yielding elements by value
-    #[inline]
-    pub fn move_iter(self) -> MoveItems<T> {
-        MoveItems{list: self}
-    }
-
-    /// Consume the list into an iterator yielding elements by value, in reverse
-    #[inline]
-    pub fn move_rev_iter(self) -> Rev<MoveItems<T>> {
-        self.move_iter().rev()
-    }
-}
-
-impl<T: Ord> DList<T> {
-    /// Insert `elt` sorted in ascending order
-    ///
-    /// O(N)
-    #[inline]
-    pub fn insert_ordered(&mut self, elt: T) {
-        self.insert_when(elt, |a, b| a >= b)
-    }
-}
-
-#[unsafe_destructor]
-impl<T> Drop for DList<T> {
-    fn drop(&mut self) {
-        // Dissolve the dlist in backwards direction
-        // Just dropping the list_head can lead to stack exhaustion
-        // when length is >> 1_000_000
-        let mut tail = self.list_tail;
-        loop {
-            match tail.resolve() {
-                None => break,
-                Some(prev) => {
-                    prev.next.take(); // release ~Node<T>
-                    tail = prev.prev;
-                }
-            }
-        }
-        self.length = 0;
-        self.list_head = None;
-        self.list_tail = Rawlink::none();
-    }
-}
-
-
-impl<'a, A> Iterator<&'a A> for Items<'a, A> {
-    #[inline]
-    fn next(&mut self) -> Option<&'a A> {
-        if self.nelem == 0 {
-            return None;
-        }
-        self.head.as_ref().map(|head| {
-            self.nelem -= 1;
-            self.head = &head.next;
-            &head.value
-        })
-    }
-
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        (self.nelem, Some(self.nelem))
-    }
-}
-
-impl<'a, A> DoubleEndedIterator<&'a A> for Items<'a, A> {
-    #[inline]
-    fn next_back(&mut self) -> Option<&'a A> {
-        if self.nelem == 0 {
-            return None;
-        }
-        let tmp = self.tail.resolve_immut(); // FIXME: #3511: shouldn't need variable
-        tmp.as_ref().map(|prev| {
-            self.nelem -= 1;
-            self.tail = prev.prev;
-            &prev.value
-        })
-    }
-}
-
-impl<'a, A> ExactSize<&'a A> for Items<'a, A> {}
-
-impl<'a, A> Iterator<&'a mut A> for MutItems<'a, A> {
-    #[inline]
-    fn next(&mut self) -> Option<&'a mut A> {
-        if self.nelem == 0 {
-            return None;
-        }
-        self.head.resolve().map(|next| {
-            self.nelem -= 1;
-            self.head = match next.next {
-                Some(ref mut node) => Rawlink::some(&mut **node),
-                None => Rawlink::none(),
-            };
-            &mut next.value
-        })
-    }
-
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        (self.nelem, Some(self.nelem))
-    }
-}
-
-impl<'a, A> DoubleEndedIterator<&'a mut A> for MutItems<'a, A> {
-    #[inline]
-    fn next_back(&mut self) -> Option<&'a mut A> {
-        if self.nelem == 0 {
-            return None;
-        }
-        self.tail.resolve().map(|prev| {
-            self.nelem -= 1;
-            self.tail = prev.prev;
-            &mut prev.value
-        })
-    }
-}
-
-impl<'a, A> ExactSize<&'a mut A> for MutItems<'a, A> {}
-
-/// Allow mutating the DList while iterating
-pub trait ListInsertion<A> {
-    /// Insert `elt` just after to the element most recently returned by `.next()`
-    ///
-    /// The inserted element does not appear in the iteration.
-    fn insert_next(&mut self, elt: A);
-
-    /// Provide a reference to the next element, without changing the iterator
-    fn peek_next<'a>(&'a mut self) -> Option<&'a mut A>;
-}
-
-// private methods for MutItems
-impl<'a, A> MutItems<'a, A> {
-    fn insert_next_node(&mut self, mut ins_node: ~Node<A>) {
-        // Insert before `self.head` so that it is between the
-        // previously yielded element and self.head.
-        //
-        // The inserted node will not appear in further iteration.
-        match self.head.resolve() {
-            None => { self.list.push_back_node(ins_node); }
-            Some(node) => {
-                let prev_node = match node.prev.resolve() {
-                    None => return self.list.push_front_node(ins_node),
-                    Some(prev) => prev,
-                };
-                let node_own = prev_node.next.take_unwrap();
-                ins_node.next = link_with_prev(node_own, Rawlink::some(ins_node));
-                prev_node.next = link_with_prev(ins_node, Rawlink::some(prev_node));
-                self.list.length += 1;
-            }
-        }
-    }
-}
-
-impl<'a, A> ListInsertion<A> for MutItems<'a, A> {
-    #[inline]
-    fn insert_next(&mut self, elt: A) {
-        self.insert_next_node(~Node::new(elt))
-    }
-
-    #[inline]
-    fn peek_next<'a>(&'a mut self) -> Option<&'a mut A> {
-        if self.nelem == 0 {
-            return None
-        }
-        self.head.resolve().map(|head| &mut head.value)
-    }
-}
-
-impl<A> Iterator<A> for MoveItems<A> {
-    #[inline]
-    fn next(&mut self) -> Option<A> { self.list.pop_front() }
-
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        (self.list.length, Some(self.list.length))
-    }
-}
-
-impl<A> DoubleEndedIterator<A> for MoveItems<A> {
-    #[inline]
-    fn next_back(&mut self) -> Option<A> { self.list.pop_back() }
-}
-
-impl<A> FromIterator<A> for DList<A> {
-    fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> DList<A> {
-        let mut ret = DList::new();
-        ret.extend(iterator);
-        ret
-    }
-}
-
-impl<A> Extendable<A> for DList<A> {
-    fn extend<T: Iterator<A>>(&mut self, iterator: &mut T) {
-        for elt in *iterator { self.push_back(elt); }
-    }
-}
-
-impl<A: Eq> Eq for DList<A> {
-    fn eq(&self, other: &DList<A>) -> bool {
-        self.len() == other.len() &&
-            iter::order::eq(self.iter(), other.iter())
-    }
-
-    fn ne(&self, other: &DList<A>) -> bool {
-        self.len() != other.len() ||
-            iter::order::ne(self.iter(), other.iter())
-    }
-}
-
-impl<A: Eq + Ord> Ord for DList<A> {
-    fn lt(&self, other: &DList<A>) -> bool {
-        iter::order::lt(self.iter(), other.iter())
-    }
-    fn le(&self, other: &DList<A>) -> bool {
-        iter::order::le(self.iter(), other.iter())
-    }
-    fn gt(&self, other: &DList<A>) -> bool {
-        iter::order::gt(self.iter(), other.iter())
-    }
-    fn ge(&self, other: &DList<A>) -> bool {
-        iter::order::ge(self.iter(), other.iter())
-    }
-}
-
-impl<A: Clone> Clone for DList<A> {
-    fn clone(&self) -> DList<A> {
-        self.iter().map(|x| x.clone()).collect()
-    }
-}
-
-impl<
-    S: Encoder,
-    T: Encodable<S>
-> Encodable<S> for DList<T> {
-    fn encode(&self, s: &mut S) {
-        s.emit_seq(self.len(), |s| {
-            for (i, e) in self.iter().enumerate() {
-                s.emit_seq_elt(i, |s| e.encode(s));
-            }
-        })
-    }
-}
-
-impl<D:Decoder,T:Decodable<D>> Decodable<D> for DList<T> {
-    fn decode(d: &mut D) -> DList<T> {
-        let mut list = DList::new();
-        d.read_seq(|d, len| {
-            for i in range(0u, len) {
-                list.push_back(d.read_seq_elt(i, |d| Decodable::decode(d)));
-            }
-        });
-        list
-    }
-}
-
-#[cfg(test)]
-mod tests {
-    use container::Deque;
-    use extra::test;
-    use std::rand;
-    use super::{DList, Node, ListInsertion};
-
-    pub fn check_links<T>(list: &DList<T>) {
-        let mut len = 0u;
-        let mut last_ptr: Option<&Node<T>> = None;
-        let mut node_ptr: &Node<T>;
-        match list.list_head {
-            None => { assert_eq!(0u, list.length); return }
-            Some(ref node) => node_ptr = &**node,
-        }
-        loop {
-            match (last_ptr, node_ptr.prev.resolve_immut()) {
-                (None   , None      ) => {}
-                (None   , _         ) => fail!("prev link for list_head"),
-                (Some(p), Some(pptr)) => {
-                    assert_eq!(p as *Node<T>, pptr as *Node<T>);
-                }
-                _ => fail!("prev link is none, not good"),
-            }
-            match node_ptr.next {
-                Some(ref next) => {
-                    last_ptr = Some(node_ptr);
-                    node_ptr = &**next;
-                    len += 1;
-                }
-                None => {
-                    len += 1;
-                    break;
-                }
-            }
-        }
-        assert_eq!(len, list.length);
-    }
-
-    #[test]
-    fn test_basic() {
-        let mut m: DList<~int> = DList::new();
-        assert_eq!(m.pop_front(), None);
-        assert_eq!(m.pop_back(), None);
-        assert_eq!(m.pop_front(), None);
-        m.push_front(~1);
-        assert_eq!(m.pop_front(), Some(~1));
-        m.push_back(~2);
-        m.push_back(~3);
-        assert_eq!(m.len(), 2);
-        assert_eq!(m.pop_front(), Some(~2));
-        assert_eq!(m.pop_front(), Some(~3));
-        assert_eq!(m.len(), 0);
-        assert_eq!(m.pop_front(), None);
-        m.push_back(~1);
-        m.push_back(~3);
-        m.push_back(~5);
-        m.push_back(~7);
-        assert_eq!(m.pop_front(), Some(~1));
-
-        let mut n = DList::new();
-        n.push_front(2);
-        n.push_front(3);
-        {
-            assert_eq!(n.front().unwrap(), &3);
-            let x = n.front_mut().unwrap();
-            assert_eq!(*x, 3);
-            *x = 0;
-        }
-        {
-            assert_eq!(n.back().unwrap(), &2);
-            let y = n.back_mut().unwrap();
-            assert_eq!(*y, 2);
-            *y = 1;
-        }
-        assert_eq!(n.pop_front(), Some(0));
-        assert_eq!(n.pop_front(), Some(1));
-    }
-
-    #[cfg(test)]
-    fn generate_test() -> DList<int> {
-        list_from(&[0,1,2,3,4,5,6])
-    }
-
-    #[cfg(test)]
-    fn list_from<T: Clone>(v: &[T]) -> DList<T> {
-        v.iter().map(|x| (*x).clone()).collect()
-    }
-
-    #[test]
-    fn test_append() {
-        {
-            let mut m = DList::new();
-            let mut n = DList::new();
-            n.push_back(2);
-            m.append(n);
-            assert_eq!(m.len(), 1);
-            assert_eq!(m.pop_back(), Some(2));
-            check_links(&m);
-        }
-        {
-            let mut m = DList::new();
-            let n = DList::new();
-            m.push_back(2);
-            m.append(n);
-            assert_eq!(m.len(), 1);
-            assert_eq!(m.pop_back(), Some(2));
-            check_links(&m);
-        }
-
-        let v = ~[1,2,3,4,5];
-        let u = ~[9,8,1,2,3,4,5];
-        let mut m = list_from(v);
-        m.append(list_from(u));
-        check_links(&m);
-        let sum = v + u;
-        assert_eq!(sum.len(), m.len());
-        for elt in sum.move_iter() {
-            assert_eq!(m.pop_front(), Some(elt))
-        }
-    }
-
-    #[test]
-    fn test_prepend() {
-        {
-            let mut m = DList::new();
-            let mut n = DList::new();
-            n.push_back(2);
-            m.prepend(n);
-            assert_eq!(m.len(), 1);
-            assert_eq!(m.pop_back(), Some(2));
-            check_links(&m);
-        }
-
-        let v = ~[1,2,3,4,5];
-        let u = ~[9,8,1,2,3,4,5];
-        let mut m = list_from(v);
-        m.prepend(list_from(u));
-        check_links(&m);
-        let sum = u + v;
-        assert_eq!(sum.len(), m.len());
-        for elt in sum.move_iter() {
-            assert_eq!(m.pop_front(), Some(elt))
-        }
-    }
-
-    #[test]
-    fn test_rotate() {
-        let mut n: DList<int> = DList::new();
-        n.rotate_backward(); check_links(&n);
-        assert_eq!(n.len(), 0);
-        n.rotate_forward(); check_links(&n);
-        assert_eq!(n.len(), 0);
-
-        let v = ~[1,2,3,4,5];
-        let mut m = list_from(v);
-        m.rotate_backward(); check_links(&m);
-        m.rotate_forward(); check_links(&m);
-        assert_eq!(v.iter().collect::<~[&int]>(), m.iter().collect());
-        m.rotate_forward(); check_links(&m);
-        m.rotate_forward(); check_links(&m);
-        m.pop_front(); check_links(&m);
-        m.rotate_forward(); check_links(&m);
-        m.rotate_backward(); check_links(&m);
-        m.push_front(9); check_links(&m);
-        m.rotate_forward(); check_links(&m);
-        assert_eq!(~[3,9,5,1,2], m.move_iter().collect());
-    }
-
-    #[test]
-    fn test_iterator() {
-        let m = generate_test();
-        for (i, elt) in m.iter().enumerate() {
-            assert_eq!(i as int, *elt);
-        }
-        let mut n = DList::new();
-        assert_eq!(n.iter().next(), None);
-        n.push_front(4);
-        let mut it = n.iter();
-        assert_eq!(it.size_hint(), (1, Some(1)));
-        assert_eq!(it.next().unwrap(), &4);
-        assert_eq!(it.size_hint(), (0, Some(0)));
-        assert_eq!(it.next(), None);
-    }
-
-    #[test]
-    fn test_iterator_clone() {
-        let mut n = DList::new();
-        n.push_back(2);
-        n.push_back(3);
-        n.push_back(4);
-        let mut it = n.iter();
-        it.next();
-        let mut jt = it.clone();
-        assert_eq!(it.next(), jt.next());
-        assert_eq!(it.next_back(), jt.next_back());
-        assert_eq!(it.next(), jt.next());
-    }
-
-    #[test]
-    fn test_iterator_double_end() {
-        let mut n = DList::new();
-        assert_eq!(n.iter().next(), None);
-        n.push_front(4);
-        n.push_front(5);
-        n.push_front(6);
-        let mut it = n.iter();
-        assert_eq!(it.size_hint(), (3, Some(3)));
-        assert_eq!(it.next().unwrap(), &6);
-        assert_eq!(it.size_hint(), (2, Some(2)));
-        assert_eq!(it.next_back().unwrap(), &4);
-        assert_eq!(it.size_hint(), (1, Some(1)));
-        assert_eq!(it.next_back().unwrap(), &5);
-        assert_eq!(it.next_back(), None);
-        assert_eq!(it.next(), None);
-    }
-
-    #[test]
-    fn test_rev_iter() {
-        let m = generate_test();
-        for (i, elt) in m.rev_iter().enumerate() {
-            assert_eq!((6 - i) as int, *elt);
-        }
-        let mut n = DList::new();
-        assert_eq!(n.rev_iter().next(), None);
-        n.push_front(4);
-        let mut it = n.rev_iter();
-        assert_eq!(it.size_hint(), (1, Some(1)));
-        assert_eq!(it.next().unwrap(), &4);
-        assert_eq!(it.size_hint(), (0, Some(0)));
-        assert_eq!(it.next(), None);
-    }
-
-    #[test]
-    fn test_mut_iter() {
-        let mut m = generate_test();
-        let mut len = m.len();
-        for (i, elt) in m.mut_iter().enumerate() {
-            assert_eq!(i as int, *elt);
-            len -= 1;
-        }
-        assert_eq!(len, 0);
-        let mut n = DList::new();
-        assert!(n.mut_iter().next().is_none());
-        n.push_front(4);
-        n.push_back(5);
-        let mut it = n.mut_iter();
-        assert_eq!(it.size_hint(), (2, Some(2)));
-        assert!(it.next().is_some());
-        assert!(it.next().is_some());
-        assert_eq!(it.size_hint(), (0, Some(0)));
-        assert!(it.next().is_none());
-    }
-
-    #[test]
-    fn test_iterator_mut_double_end() {
-        let mut n = DList::new();
-        assert!(n.mut_iter().next_back().is_none());
-        n.push_front(4);
-        n.push_front(5);
-        n.push_front(6);
-        let mut it = n.mut_iter();
-        assert_eq!(it.size_hint(), (3, Some(3)));
-        assert_eq!(*it.next().unwrap(), 6);
-        assert_eq!(it.size_hint(), (2, Some(2)));
-        assert_eq!(*it.next_back().unwrap(), 4);
-        assert_eq!(it.size_hint(), (1, Some(1)));
-        assert_eq!(*it.next_back().unwrap(), 5);
-        assert!(it.next_back().is_none());
-        assert!(it.next().is_none());
-    }
-
-    #[test]
-    fn test_insert_prev() {
-        let mut m = list_from(&[0,2,4,6,8]);
-        let len = m.len();
-        {
-            let mut it = m.mut_iter();
-            it.insert_next(-2);
-            loop {
-                match it.next() {
-                    None => break,
-                    Some(elt) => {
-                        it.insert_next(*elt + 1);
-                        match it.peek_next() {
-                            Some(x) => assert_eq!(*x, *elt + 2),
-                            None => assert_eq!(8, *elt),
-                        }
-                    }
-                }
-            }
-            it.insert_next(0);
-            it.insert_next(1);
-        }
-        check_links(&m);
-        assert_eq!(m.len(), 3 + len * 2);
-        assert_eq!(m.move_iter().collect::<~[int]>(), ~[-2,0,1,2,3,4,5,6,7,8,9,0,1]);
-    }
-
-    #[test]
-    fn test_merge() {
-        let mut m = list_from([0, 1, 3, 5, 6, 7, 2]);
-        let n = list_from([-1, 0, 0, 7, 7, 9]);
-        let len = m.len() + n.len();
-        m.merge(n, |a, b| a <= b);
-        assert_eq!(m.len(), len);
-        check_links(&m);
-        let res = m.move_iter().collect::<~[int]>();
-        assert_eq!(res, ~[-1, 0, 0, 0, 1, 3, 5, 6, 7, 2, 7, 7, 9]);
-    }
-
-    #[test]
-    fn test_insert_ordered() {
-        let mut n = DList::new();
-        n.insert_ordered(1);
-        assert_eq!(n.len(), 1);
-        assert_eq!(n.pop_front(), Some(1));
-
-        let mut m = DList::new();
-        m.push_back(2);
-        m.push_back(4);
-        m.insert_ordered(3);
-        check_links(&m);
-        assert_eq!(~[2,3,4], m.move_iter().collect::<~[int]>());
-    }
-
-    #[test]
-    fn test_mut_rev_iter() {
-        let mut m = generate_test();
-        for (i, elt) in m.mut_rev_iter().enumerate() {
-            assert_eq!((6-i) as int, *elt);
-        }
-        let mut n = DList::new();
-        assert!(n.mut_rev_iter().next().is_none());
-        n.push_front(4);
-        let mut it = n.mut_rev_iter();
-        assert!(it.next().is_some());
-        assert!(it.next().is_none());
-    }
-
-    #[test]
-    fn test_send() {
-        let n = list_from([1,2,3]);
-        spawn(proc() {
-            check_links(&n);
-            assert_eq!(~[&1,&2,&3], n.iter().collect::<~[&int]>());
-        });
-    }
-
-    #[test]
-    fn test_eq() {
-        let mut n: DList<u8> = list_from([]);
-        let mut m = list_from([]);
-        assert_eq!(&n, &m);
-        n.push_front(1);
-        assert!(n != m);
-        m.push_back(1);
-        assert_eq!(&n, &m);
-
-        let n = list_from([2,3,4]);
-        let m = list_from([1,2,3]);
-        assert!(n != m);
-    }
-
-    #[test]
-    fn test_ord() {
-        let n: DList<int> = list_from([]);
-        let m = list_from([1,2,3]);
-        assert!(n < m);
-        assert!(m > n);
-        assert!(n <= n);
-        assert!(n >= n);
-    }
-
-    #[test]
-    fn test_ord_nan() {
-        let nan = 0.0/0.0;
-        let n = list_from([nan]);
-        let m = list_from([nan]);
-        assert!(!(n < m));
-        assert!(!(n > m));
-        assert!(!(n <= m));
-        assert!(!(n >= m));
-
-        let n = list_from([nan]);
-        let one = list_from([1.0]);
-        assert!(!(n < one));
-        assert!(!(n > one));
-        assert!(!(n <= one));
-        assert!(!(n >= one));
-
-        let u = list_from([1.0,2.0,nan]);
-        let v = list_from([1.0,2.0,3.0]);
-        assert!(!(u < v));
-        assert!(!(u > v));
-        assert!(!(u <= v));
-        assert!(!(u >= v));
-
-        let s = list_from([1.0,2.0,4.0,2.0]);
-        let t = list_from([1.0,2.0,3.0,2.0]);
-        assert!(!(s < t));
-        assert!(s > one);
-        assert!(!(s <= one));
-        assert!(s >= one);
-    }
-
-    #[test]
-    fn test_fuzz() {
-        for _ in range(0, 25) {
-            fuzz_test(3);
-            fuzz_test(16);
-            fuzz_test(189);
-        }
-    }
-
-    #[cfg(test)]
-    fn fuzz_test(sz: int) {
-        let mut m: DList<int> = DList::new();
-        let mut v = ~[];
-        for i in range(0, sz) {
-            check_links(&m);
-            let r: u8 = rand::random();
-            match r % 6 {
-                0 => {
-                    m.pop_back();
-                    v.pop();
-                }
-                1 => {
-                    m.pop_front();
-                    v.shift();
-                }
-                2 | 4 =>  {
-                    m.push_front(-i);
-                    v.unshift(-i);
-                }
-                3 | 5 | _ => {
-                    m.push_back(i);
-                    v.push(i);
-                }
-            }
-        }
-
-        check_links(&m);
-
-        let mut i = 0u;
-        for (a, &b) in m.move_iter().zip(v.iter()) {
-            i += 1;
-            assert_eq!(a, b);
-        }
-        assert_eq!(i, v.len());
-    }
-
-    #[bench]
-    fn bench_collect_into(b: &mut test::BenchHarness) {
-        let v = &[0, ..64];
-        b.iter(|| {
-            let _: DList<int> = v.iter().map(|x| *x).collect();
-        })
-    }
-
-    #[bench]
-    fn bench_push_front(b: &mut test::BenchHarness) {
-        let mut m: DList<int> = DList::new();
-        b.iter(|| {
-            m.push_front(0);
-        })
-    }
-
-    #[bench]
-    fn bench_push_back(b: &mut test::BenchHarness) {
-        let mut m: DList<int> = DList::new();
-        b.iter(|| {
-            m.push_back(0);
-        })
-    }
-
-    #[bench]
-    fn bench_push_back_pop_back(b: &mut test::BenchHarness) {
-        let mut m: DList<int> = DList::new();
-        b.iter(|| {
-            m.push_back(0);
-            m.pop_back();
-        })
-    }
-
-    #[bench]
-    fn bench_push_front_pop_front(b: &mut test::BenchHarness) {
-        let mut m: DList<int> = DList::new();
-        b.iter(|| {
-            m.push_front(0);
-            m.pop_front();
-        })
-    }
-
-    #[bench]
-    fn bench_rotate_forward(b: &mut test::BenchHarness) {
-        let mut m: DList<int> = DList::new();
-        m.push_front(0);
-        m.push_front(1);
-        b.iter(|| {
-            m.rotate_forward();
-        })
-    }
-
-    #[bench]
-    fn bench_rotate_backward(b: &mut test::BenchHarness) {
-        let mut m: DList<int> = DList::new();
-        m.push_front(0);
-        m.push_front(1);
-        b.iter(|| {
-            m.rotate_backward();
-        })
-    }
-
-    #[bench]
-    fn bench_iter(b: &mut test::BenchHarness) {
-        let v = &[0, ..128];
-        let m: DList<int> = v.iter().map(|&x|x).collect();
-        b.iter(|| {
-            assert!(m.iter().len() == 128);
-        })
-    }
-    #[bench]
-    fn bench_iter_mut(b: &mut test::BenchHarness) {
-        let v = &[0, ..128];
-        let mut m: DList<int> = v.iter().map(|&x|x).collect();
-        b.iter(|| {
-            assert!(m.mut_iter().len() == 128);
-        })
-    }
-    #[bench]
-    fn bench_iter_rev(b: &mut test::BenchHarness) {
-        let v = &[0, ..128];
-        let m: DList<int> = v.iter().map(|&x|x).collect();
-        b.iter(|| {
-            assert!(m.rev_iter().len() == 128);
-        })
-    }
-    #[bench]
-    fn bench_iter_mut_rev(b: &mut test::BenchHarness) {
-        let v = &[0, ..128];
-        let mut m: DList<int> = v.iter().map(|&x|x).collect();
-        b.iter(|| {
-            assert!(m.mut_rev_iter().len() == 128);
-        })
-    }
-}
diff --git a/src/libextra/json.rs b/src/libextra/json.rs
index 8b082bf3056..75bbd3d8a01 100644
--- a/src/libextra/json.rs
+++ b/src/libextra/json.rs
@@ -98,9 +98,11 @@ A basic `ToJson` example using a TreeMap of attribute name / attribute value:
 
 
 ```rust
+extern mod collections;
+
 use extra::json;
 use extra::json::ToJson;
-use extra::treemap::TreeMap;
+use collections::TreeMap;
 
 pub struct MyStruct  {
     attr1: u8,
@@ -185,10 +187,12 @@ Example of `ToJson` trait implementation for TestStruct1.
 
 ```rust
 extern mod serialize;
+extern mod collections;
+
 use extra::json;
 use extra::json::ToJson;
 use serialize::{Encodable, Decodable};
-use extra::treemap::TreeMap;
+use collections::TreeMap;
 
 #[deriving(Decodable, Encodable)] // generate Decodable, Encodable impl.
 pub struct TestStruct1  {
@@ -236,7 +240,7 @@ use std::to_str;
 
 use serialize::Encodable;
 use serialize;
-use treemap::TreeMap;
+use collections::TreeMap;
 
 macro_rules! if_ok( ($e:expr) => (
     match $e { Ok(e) => e, Err(e) => { self.error = Err(e); return } }
@@ -1588,7 +1592,7 @@ mod tests {
 
     use std::io;
     use serialize::{Encodable, Decodable};
-    use treemap::TreeMap;
+    use collections::TreeMap;
 
     #[deriving(Eq, Encodable, Decodable)]
     enum Animal {
diff --git a/src/libextra/lib.rs b/src/libextra/lib.rs
index 97c38a59af8..519192fd177 100644
--- a/src/libextra/lib.rs
+++ b/src/libextra/lib.rs
@@ -38,6 +38,8 @@ extern mod sync;
 #[cfg(not(stage0))]
 extern mod serialize;
 
+extern mod collections;
+
 #[cfg(stage0)]
 pub mod serialize {
     #[allow(missing_doc)];
@@ -47,29 +49,10 @@ pub mod serialize {
                                    EncoderHelpers, DecoderHelpers};
 }
 
-#[cfg(stage0)]
-macro_rules! if_ok (
-    ($e:expr) => (match $e { Ok(e) => e, Err(e) => return Err(e) })
-)
-
 // Utility modules
 
 pub mod c_vec;
 
-// Collections
-
-pub mod container;
-pub mod bitv;
-pub mod list;
-pub mod ringbuf;
-pub mod priority_queue;
-pub mod smallintmap;
-
-pub mod dlist;
-pub mod treemap;
-pub mod btree;
-pub mod lru_cache;
-
 // And ... other stuff
 
 pub mod url;
diff --git a/src/libextra/list.rs b/src/libextra/list.rs
deleted file mode 100644
index b530d9c9bc1..00000000000
--- a/src/libextra/list.rs
+++ /dev/null
@@ -1,248 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-//! A standard, garbage-collected linked list.
-
-
-
-#[deriving(Clone, Eq)]
-#[allow(missing_doc)]
-pub enum List<T> {
-    Cons(T, @List<T>),
-    Nil,
-}
-
-/// Create a list from a vector
-pub fn from_vec<T:Clone + 'static>(v: &[T]) -> @List<T> {
-    v.rev_iter().fold(@Nil::<T>, |t, h| @Cons((*h).clone(), t))
-}
-
-/**
- * Left fold
- *
- * Applies `f` to `u` and the first element in the list, then applies `f` to
- * the result of the previous call and the second element, and so on,
- * returning the accumulated result.
- *
- * # Arguments
- *
- * * ls - The list to fold
- * * z - The initial value
- * * f - The function to apply
- */
-pub fn foldl<T:Clone,U>(z: T, ls: @List<U>, f: |&T, &U| -> T) -> T {
-    let mut accum: T = z;
-    iter(ls, |elt| accum = f(&accum, elt));
-    accum
-}
-
-/**
- * Search for an 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:Clone>(ls: @List<T>, f: |&T| -> bool) -> Option<T> {
-    let mut ls = ls;
-    loop {
-        ls = match *ls {
-          Cons(ref hd, tl) => {
-            if f(hd) { return Some((*hd).clone()); }
-            tl
-          }
-          Nil => return None
-        }
-    };
-}
-
-/// Returns true if a list contains an element with the given value
-pub fn has<T:Eq>(ls: @List<T>, elt: T) -> bool {
-    let mut found = false;
-    each(ls, |e| {
-        if *e == elt { found = true; false } else { true }
-    });
-    return found;
-}
-
-/// Returns true if the list is empty
-pub fn is_empty<T>(ls: @List<T>) -> bool {
-    match *ls {
-        Nil => true,
-        _ => false
-    }
-}
-
-/// Returns the length of a list
-pub fn len<T>(ls: @List<T>) -> uint {
-    let mut count = 0u;
-    iter(ls, |_e| count += 1u);
-    count
-}
-
-/// Returns all but the first element of a list
-pub fn tail<T>(ls: @List<T>) -> @List<T> {
-    match *ls {
-        Cons(_, tl) => return tl,
-        Nil => fail!("list empty")
-    }
-}
-
-/// Returns the first element of a list
-pub fn head<T:Clone>(ls: @List<T>) -> T {
-    match *ls {
-      Cons(ref hd, _) => (*hd).clone(),
-      // makes me sad
-      _ => fail!("head invoked on empty list")
-    }
-}
-
-/// Appends one list to another
-pub fn append<T:Clone + 'static>(l: @List<T>, m: @List<T>) -> @List<T> {
-    match *l {
-      Nil => return m,
-      Cons(ref x, xs) => {
-        let rest = append(xs, m);
-        return @Cons((*x).clone(), rest);
-      }
-    }
-}
-
-/*
-/// Push one element into the front of a list, returning a new list
-/// THIS VERSION DOESN'T ACTUALLY WORK
-fn push<T:Clone>(ll: &mut @list<T>, vv: T) {
-    ll = &mut @cons(vv, *ll)
-}
-*/
-
-/// Iterate over a list
-pub fn iter<T>(l: @List<T>, f: |&T|) {
-    let mut cur = l;
-    loop {
-        cur = match *cur {
-          Cons(ref hd, tl) => {
-            f(hd);
-            tl
-          }
-          Nil => break
-        }
-    }
-}
-
-/// Iterate over a list
-pub fn each<T>(l: @List<T>, f: |&T| -> bool) -> bool {
-    let mut cur = l;
-    loop {
-        cur = match *cur {
-          Cons(ref hd, tl) => {
-            if !f(hd) { return false; }
-            tl
-          }
-          Nil => { return true; }
-        }
-    }
-}
-
-#[cfg(test)]
-mod tests {
-    use list::*;
-    use list;
-
-    use std::option;
-
-    #[test]
-    fn test_is_empty() {
-        let empty : @list::List<int> = from_vec([]);
-        let full1 = from_vec([1]);
-        let full2 = from_vec(['r', 'u']);
-
-        assert!(is_empty(empty));
-        assert!(!is_empty(full1));
-        assert!(!is_empty(full2));
-    }
-
-    #[test]
-    fn test_from_vec() {
-        let l = from_vec([0, 1, 2]);
-
-        assert_eq!(head(l), 0);
-
-        let tail_l = tail(l);
-        assert_eq!(head(tail_l), 1);
-
-        let tail_tail_l = tail(tail_l);
-        assert_eq!(head(tail_tail_l), 2);
-    }
-
-    #[test]
-    fn test_from_vec_empty() {
-        let empty : @list::List<int> = from_vec([]);
-        assert_eq!(empty, @list::Nil::<int>);
-    }
-
-    #[test]
-    fn test_foldl() {
-        fn add(a: &uint, b: &int) -> uint { return *a + (*b as uint); }
-        let l = from_vec([0, 1, 2, 3, 4]);
-        let empty = @list::Nil::<int>;
-        assert_eq!(list::foldl(0u, l, add), 10u);
-        assert_eq!(list::foldl(0u, empty, add), 0u);
-    }
-
-    #[test]
-    fn test_foldl2() {
-        fn sub(a: &int, b: &int) -> int {
-            *a - *b
-        }
-        let l = from_vec([1, 2, 3, 4]);
-        assert_eq!(list::foldl(0, l, sub), -10);
-    }
-
-    #[test]
-    fn test_find_success() {
-        fn match_(i: &int) -> bool { return *i == 2; }
-        let l = from_vec([0, 1, 2]);
-        assert_eq!(list::find(l, match_), option::Some(2));
-    }
-
-    #[test]
-    fn test_find_fail() {
-        fn match_(_i: &int) -> bool { return false; }
-        let l = from_vec([0, 1, 2]);
-        let empty = @list::Nil::<int>;
-        assert_eq!(list::find(l, match_), option::None::<int>);
-        assert_eq!(list::find(empty, match_), option::None::<int>);
-    }
-
-    #[test]
-    fn test_has() {
-        let l = from_vec([5, 8, 6]);
-        let empty = @list::Nil::<int>;
-        assert!((list::has(l, 5)));
-        assert!((!list::has(l, 7)));
-        assert!((list::has(l, 8)));
-        assert!((!list::has(empty, 5)));
-    }
-
-    #[test]
-    fn test_len() {
-        let l = from_vec([0, 1, 2]);
-        let empty = @list::Nil::<int>;
-        assert_eq!(list::len(l), 3u);
-        assert_eq!(list::len(empty), 0u);
-    }
-
-    #[test]
-    fn test_append() {
-        assert!(from_vec([1,2,3,4])
-            == list::append(list::from_vec([1,2]), list::from_vec([3,4])));
-    }
-}
diff --git a/src/libextra/lru_cache.rs b/src/libextra/lru_cache.rs
deleted file mode 100644
index f602db2e54d..00000000000
--- a/src/libextra/lru_cache.rs
+++ /dev/null
@@ -1,367 +0,0 @@
-// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-
-//! A cache that holds a limited number of key-value pairs. When the
-//! capacity of the cache is exceeded, the least-recently-used
-//! (where "used" means a look-up or putting the pair into the cache)
-//! pair is automatically removed.
-//!
-//! # Example
-//!
-//! ```rust
-//! use extra::lru_cache::LruCache;
-//!
-//! let mut cache: LruCache<int, int> = LruCache::new(2);
-//! cache.put(1, 10);
-//! cache.put(2, 20);
-//! cache.put(3, 30);
-//! assert!(cache.get(&1).is_none());
-//! assert_eq!(*cache.get(&2).unwrap(), 20);
-//! assert_eq!(*cache.get(&3).unwrap(), 30);
-//!
-//! cache.put(2, 22);
-//! assert_eq!(*cache.get(&2).unwrap(), 22);
-//!
-//! cache.put(6, 60);
-//! assert!(cache.get(&3).is_none());
-//!
-//! cache.change_capacity(1);
-//! assert!(cache.get(&2).is_none());
-//! ```
-
-use std::container::Container;
-use std::hashmap::HashMap;
-use std::to_bytes::Cb;
-use std::ptr;
-use std::cast;
-
-struct KeyRef<K> { k: *K }
-
-struct LruEntry<K, V> {
-    key: Option<K>,
-    value: Option<V>,
-    next: *mut LruEntry<K, V>,
-    prev: *mut LruEntry<K, V>,
-}
-
-/// An LRU Cache.
-pub struct LruCache<K, V> {
-    priv map: HashMap<KeyRef<K>, ~LruEntry<K, V>>,
-    priv max_size: uint,
-    priv head: *mut LruEntry<K, V>,
-    priv tail: *mut LruEntry<K, V>,
-}
-
-impl<K: IterBytes> IterBytes for KeyRef<K> {
-    fn iter_bytes(&self, lsb0: bool, f: Cb) -> bool {
-        unsafe{ (*self.k).iter_bytes(lsb0, f) }
-    }
-}
-
-impl<K: Eq> Eq for KeyRef<K> {
-    fn eq(&self, other: &KeyRef<K>) -> bool {
-        unsafe{ (*self.k).eq(&*other.k) }
-    }
-}
-
-impl<K, V> LruEntry<K, V> {
-    fn new() -> LruEntry<K, V> {
-        LruEntry {
-            key: None,
-            value: None,
-            next: ptr::mut_null(),
-            prev: ptr::mut_null(),
-        }
-    }
-
-    fn with_key_value(k: K, v: V) -> LruEntry<K, V> {
-        LruEntry {
-            key: Some(k),
-            value: Some(v),
-            next: ptr::mut_null(),
-            prev: ptr::mut_null(),
-        }
-    }
-}
-
-impl<K: IterBytes + Eq, V> LruCache<K, V> {
-    /// Create an LRU Cache that holds at most `capacity` items.
-    pub fn new(capacity: uint) -> LruCache<K, V> {
-        let cache = LruCache {
-            map: HashMap::new(),
-            max_size: capacity,
-            head: unsafe{ cast::transmute(~LruEntry::<K, V>::new()) },
-            tail: unsafe{ cast::transmute(~LruEntry::<K, V>::new()) },
-        };
-        unsafe {
-            (*cache.head).next = cache.tail;
-            (*cache.tail).prev = cache.head;
-        }
-        return cache;
-    }
-
-    /// Put a key-value pair into cache.
-    pub fn put(&mut self, k: K, v: V) {
-        let mut key_existed = false;
-        let (node_ptr, node_opt) = match self.map.find_mut(&KeyRef{k: &k}) {
-            Some(node) => {
-                key_existed = true;
-                node.value = Some(v);
-                let node_ptr: *mut LruEntry<K, V> = &mut **node;
-                (node_ptr, None)
-            }
-            None => {
-                let mut node = ~LruEntry::with_key_value(k, v);
-                let node_ptr: *mut LruEntry<K, V> = &mut *node;
-                (node_ptr, Some(node))
-            }
-        };
-        if key_existed {
-            self.detach(node_ptr);
-            self.attach(node_ptr);
-        } else {
-            let keyref = unsafe { (*node_ptr).key.as_ref().unwrap() };
-            self.map.swap(KeyRef{k: keyref}, node_opt.unwrap());
-            self.attach(node_ptr);
-            if self.len() > self.capacity() {
-                self.remove_lru();
-            }
-        }
-    }
-
-    /// Return a value corresponding to the key in the cache.
-    pub fn get<'a>(&'a mut self, k: &K) -> Option<&'a V> {
-        let (value, node_ptr_opt) = match self.map.find_mut(&KeyRef{k: k}) {
-            None => (None, None),
-            Some(node) => {
-                let node_ptr: *mut LruEntry<K, V> = &mut **node;
-                unsafe {
-                    match (*node_ptr).value {
-                        None => (None, None),
-                        Some(ref value) => (Some(value), Some(node_ptr))
-                    }
-                }
-            }
-        };
-        match node_ptr_opt {
-            None => (),
-            Some(node_ptr) => {
-                self.detach(node_ptr);
-                self.attach(node_ptr);
-            }
-        }
-        return value;
-    }
-
-    /// Remove and return a value corresponding to the key from the cache.
-    pub fn pop(&mut self, k: &K) -> Option<V> {
-        match self.map.pop(&KeyRef{k: k}) {
-            None => None,
-            Some(lru_entry) => lru_entry.value
-        }
-    }
-
-    /// Return the maximum number of key-value pairs the cache can hold.
-    pub fn capacity(&self) -> uint {
-        self.max_size
-    }
-
-    /// Change the number of key-value pairs the cache can hold. Remove
-    /// least-recently-used key-value pairs if necessary.
-    pub fn change_capacity(&mut self, capacity: uint) {
-        for _ in range(capacity, self.len()) {
-            self.remove_lru();
-        }
-        self.max_size = capacity;
-    }
-
-    #[inline]
-    fn remove_lru(&mut self) {
-        if self.len() > 0 {
-            let lru = unsafe { (*self.tail).prev };
-            self.detach(lru);
-            unsafe {
-                match (*lru).key {
-                    None => (),
-                    Some(ref k) => { self.map.pop(&KeyRef{k: k}); }
-                }
-            }
-        }
-    }
-
-    #[inline]
-    fn detach(&mut self, node: *mut LruEntry<K, V>) {
-        unsafe {
-            (*(*node).prev).next = (*node).next;
-            (*(*node).next).prev = (*node).prev;
-        }
-    }
-
-    #[inline]
-    fn attach(&mut self, node: *mut LruEntry<K, V>) {
-        unsafe {
-            (*node).next = (*self.head).next;
-            (*node).prev = self.head;
-            (*self.head).next = node;
-            (*(*node).next).prev = node;
-        }
-    }
-}
-
-impl<A: ToStr + IterBytes + Eq, B: ToStr> ToStr for LruCache<A, B> {
-    /// Return a string that lists the key-value pairs from most-recently
-    /// used to least-recently used.
-    #[inline]
-    fn to_str(&self) -> ~str {
-        let mut acc = ~"{";
-        let mut cur = self.head;
-        for i in range(0, self.len()) {
-            if i > 0 {
-                acc.push_str(", ");
-            }
-            unsafe {
-                cur = (*cur).next;
-                match (*cur).key {
-                    // should never print nil
-                    None => acc.push_str("nil"),
-                    Some(ref k) => acc.push_str(k.to_str())
-                }
-            }
-            acc.push_str(": ");
-            unsafe {
-                match (*cur).value {
-                    // should never print nil
-                    None => acc.push_str("nil"),
-                    Some(ref value) => acc.push_str(value.to_str())
-                }
-            }
-        }
-        acc.push_char('}');
-        acc
-    }
-}
-
-impl<K: IterBytes + Eq, V> Container for LruCache<K, V> {
-    /// Return the number of key-value pairs in the cache.
-    fn len(&self) -> uint {
-        self.map.len()
-    }
-}
-
-impl<K: IterBytes + Eq, V> Mutable for LruCache<K, V> {
-    /// Clear the cache of all key-value pairs.
-    fn clear(&mut self) {
-        self.map.clear();
-    }
-}
-
-#[unsafe_destructor]
-impl<K, V> Drop for LruCache<K, V> {
-    fn drop(&mut self) {
-        unsafe {
-            let _: ~LruEntry<K, V> = cast::transmute(self.head);
-            let _: ~LruEntry<K, V> = cast::transmute(self.tail);
-        }
-    }
-}
-
-#[cfg(test)]
-mod tests {
-    use super::LruCache;
-
-    fn assert_opt_eq<V: Eq>(opt: Option<&V>, v: V) {
-        assert!(opt.is_some());
-        assert_eq!(opt.unwrap(), &v);
-    }
-
-    #[test]
-    fn test_put_and_get() {
-        let mut cache: LruCache<int, int> = LruCache::new(2);
-        cache.put(1, 10);
-        cache.put(2, 20);
-        assert_opt_eq(cache.get(&1), 10);
-        assert_opt_eq(cache.get(&2), 20);
-        assert_eq!(cache.len(), 2);
-    }
-
-    #[test]
-    fn test_put_update() {
-        let mut cache: LruCache<~str, ~[u8]> = LruCache::new(1);
-        cache.put(~"1", ~[10, 10]);
-        cache.put(~"1", ~[10, 19]);
-        assert_opt_eq(cache.get(&~"1"), ~[10, 19]);
-        assert_eq!(cache.len(), 1);
-    }
-
-    #[test]
-    fn test_expire_lru() {
-        let mut cache: LruCache<~str, ~str> = LruCache::new(2);
-        cache.put(~"foo1", ~"bar1");
-        cache.put(~"foo2", ~"bar2");
-        cache.put(~"foo3", ~"bar3");
-        assert!(cache.get(&~"foo1").is_none());
-        cache.put(~"foo2", ~"bar2update");
-        cache.put(~"foo4", ~"bar4");
-        assert!(cache.get(&~"foo3").is_none());
-    }
-
-    #[test]
-    fn test_pop() {
-        let mut cache: LruCache<int, int> = LruCache::new(2);
-        cache.put(1, 10);
-        cache.put(2, 20);
-        assert_eq!(cache.len(), 2);
-        let opt1 = cache.pop(&1);
-        assert!(opt1.is_some());
-        assert_eq!(opt1.unwrap(), 10);
-        assert!(cache.get(&1).is_none());
-        assert_eq!(cache.len(), 1);
-    }
-
-    #[test]
-    fn test_change_capacity() {
-        let mut cache: LruCache<int, int> = LruCache::new(2);
-        assert_eq!(cache.capacity(), 2);
-        cache.put(1, 10);
-        cache.put(2, 20);
-        cache.change_capacity(1);
-        assert!(cache.get(&1).is_none());
-        assert_eq!(cache.capacity(), 1);
-    }
-
-    #[test]
-    fn test_to_str() {
-        let mut cache: LruCache<int, int> = LruCache::new(3);
-        cache.put(1, 10);
-        cache.put(2, 20);
-        cache.put(3, 30);
-        assert_eq!(cache.to_str(), ~"{3: 30, 2: 20, 1: 10}");
-        cache.put(2, 22);
-        assert_eq!(cache.to_str(), ~"{2: 22, 3: 30, 1: 10}");
-        cache.put(6, 60);
-        assert_eq!(cache.to_str(), ~"{6: 60, 2: 22, 3: 30}");
-        cache.get(&3);
-        assert_eq!(cache.to_str(), ~"{3: 30, 6: 60, 2: 22}");
-        cache.change_capacity(2);
-        assert_eq!(cache.to_str(), ~"{3: 30, 6: 60}");
-    }
-
-    #[test]
-    fn test_clear() {
-        let mut cache: LruCache<int, int> = LruCache::new(2);
-        cache.put(1, 10);
-        cache.put(2, 20);
-        cache.clear();
-        assert!(cache.get(&1).is_none());
-        assert!(cache.get(&2).is_none());
-        assert_eq!(cache.to_str(), ~"{}");
-    }
-}
diff --git a/src/libextra/priority_queue.rs b/src/libextra/priority_queue.rs
deleted file mode 100644
index 3ae3dae9ea3..00000000000
--- a/src/libextra/priority_queue.rs
+++ /dev/null
@@ -1,388 +0,0 @@
-// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-//! A priority queue implemented with a binary heap
-
-#[allow(missing_doc)];
-
-use std::clone::Clone;
-use std::unstable::intrinsics::{move_val_init, init};
-use std::util::{replace, swap};
-use std::vec;
-
-/// A priority queue implemented with a binary heap
-#[deriving(Clone)]
-pub struct PriorityQueue<T> {
-    priv data: ~[T],
-}
-
-impl<T:Ord> Container for PriorityQueue<T> {
-    /// Returns the length of the queue
-    fn len(&self) -> uint { self.data.len() }
-}
-
-impl<T:Ord> Mutable for PriorityQueue<T> {
-    /// Drop all items from the queue
-    fn clear(&mut self) { self.data.truncate(0) }
-}
-
-impl<T:Ord> PriorityQueue<T> {
-    /// An iterator visiting all values in underlying vector, in
-    /// arbitrary order.
-    pub fn iter<'a>(&'a self) -> Items<'a, T> {
-        Items { iter: self.data.iter() }
-    }
-
-    /// Returns the greatest item in the queue - fails if empty
-    pub fn top<'a>(&'a self) -> &'a T { &self.data[0] }
-
-    /// Returns the greatest item in the queue - None if empty
-    pub fn maybe_top<'a>(&'a self) -> Option<&'a T> {
-        if self.is_empty() { None } else { Some(self.top()) }
-    }
-
-    /// Returns the number of elements the queue can hold without reallocating
-    pub fn capacity(&self) -> uint { self.data.capacity() }
-
-    /// Reserve capacity for exactly n elements in the PriorityQueue.
-    /// Do nothing if the capacity is already sufficient.
-    pub fn reserve_exact(&mut self, n: uint) { self.data.reserve_exact(n) }
-
-    /// Reserve capacity for at least n elements in the PriorityQueue.
-    /// Do nothing if the capacity is already sufficient.
-    pub fn reserve(&mut self, n: uint) {
-        self.data.reserve(n)
-    }
-
-    /// Pop the greatest item from the queue - fails if empty
-    pub fn pop(&mut self) -> T {
-        let mut item = self.data.pop().unwrap();
-        if !self.is_empty() {
-            swap(&mut item, &mut self.data[0]);
-            self.siftdown(0);
-        }
-        item
-    }
-
-    /// Pop the greatest item from the queue - None if empty
-    pub fn maybe_pop(&mut self) -> Option<T> {
-        if self.is_empty() { None } else { Some(self.pop()) }
-    }
-
-    /// Push an item onto the queue
-    pub fn push(&mut self, item: T) {
-        self.data.push(item);
-        let new_len = self.len() - 1;
-        self.siftup(0, new_len);
-    }
-
-    /// Optimized version of a push followed by a pop
-    pub fn push_pop(&mut self, mut item: T) -> T {
-        if !self.is_empty() && self.data[0] > item {
-            swap(&mut item, &mut self.data[0]);
-            self.siftdown(0);
-        }
-        item
-    }
-
-    /// Optimized version of a pop followed by a push - fails if empty
-    pub fn replace(&mut self, mut item: T) -> T {
-        swap(&mut item, &mut self.data[0]);
-        self.siftdown(0);
-        item
-    }
-
-    /// Consume the PriorityQueue and return the underlying vector
-    pub fn to_vec(self) -> ~[T] { let PriorityQueue{data: v} = self; v }
-
-    /// Consume the PriorityQueue and return a vector in sorted
-    /// (ascending) order
-    pub fn to_sorted_vec(self) -> ~[T] {
-        let mut q = self;
-        let mut end = q.len();
-        while end > 1 {
-            end -= 1;
-            q.data.swap(0, end);
-            q.siftdown_range(0, end)
-        }
-        q.to_vec()
-    }
-
-    /// Create an empty PriorityQueue
-    pub fn new() -> PriorityQueue<T> { PriorityQueue{data: ~[],} }
-
-    /// Create a PriorityQueue from a vector (heapify)
-    pub fn from_vec(xs: ~[T]) -> PriorityQueue<T> {
-        let mut q = PriorityQueue{data: xs,};
-        let mut n = q.len() / 2;
-        while n > 0 {
-            n -= 1;
-            q.siftdown(n)
-        }
-        q
-    }
-
-    // The implementations of siftup and siftdown use unsafe blocks in
-    // order to move an element out of the vector (leaving behind a
-    // zeroed element), shift along the others and move it back into the
-    // vector over the junk element.  This reduces the constant factor
-    // compared to using swaps, which involves twice as many moves.
-    fn siftup(&mut self, start: uint, mut pos: uint) {
-        unsafe {
-            let new = replace(&mut self.data[pos], init());
-
-            while pos > start {
-                let parent = (pos - 1) >> 1;
-                if new > self.data[parent] {
-                    let x = replace(&mut self.data[parent], init());
-                    move_val_init(&mut self.data[pos], x);
-                    pos = parent;
-                    continue
-                }
-                break
-            }
-            move_val_init(&mut self.data[pos], new);
-        }
-    }
-
-    fn siftdown_range(&mut self, mut pos: uint, end: uint) {
-        unsafe {
-            let start = pos;
-            let new = replace(&mut self.data[pos], init());
-
-            let mut child = 2 * pos + 1;
-            while child < end {
-                let right = child + 1;
-                if right < end && !(self.data[child] > self.data[right]) {
-                    child = right;
-                }
-                let x = replace(&mut self.data[child], init());
-                move_val_init(&mut self.data[pos], x);
-                pos = child;
-                child = 2 * pos + 1;
-            }
-
-            move_val_init(&mut self.data[pos], new);
-            self.siftup(start, pos);
-        }
-    }
-
-    fn siftdown(&mut self, pos: uint) {
-        let len = self.len();
-        self.siftdown_range(pos, len);
-    }
-}
-
-/// PriorityQueue iterator
-pub struct Items <'a, T> {
-    priv iter: vec::Items<'a, T>,
-}
-
-impl<'a, T> Iterator<&'a T> for Items<'a, T> {
-    #[inline]
-    fn next(&mut self) -> Option<(&'a T)> { self.iter.next() }
-
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
-}
-
-impl<T: Ord> FromIterator<T> for PriorityQueue<T> {
-    fn from_iterator<Iter: Iterator<T>>(iter: &mut Iter) -> PriorityQueue<T> {
-        let mut q = PriorityQueue::new();
-        q.extend(iter);
-
-        q
-    }
-}
-
-impl<T: Ord> Extendable<T> for PriorityQueue<T> {
-    fn extend<Iter: Iterator<T>>(&mut self, iter: &mut Iter) {
-        let (lower, _) = iter.size_hint();
-
-        let len = self.capacity();
-        self.reserve(len + lower);
-
-        for elem in *iter {
-            self.push(elem);
-        }
-    }
-}
-
-#[cfg(test)]
-mod tests {
-    use priority_queue::PriorityQueue;
-
-    #[test]
-    fn test_iterator() {
-        let data = ~[5, 9, 3];
-        let iterout = ~[9, 5, 3];
-        let pq = PriorityQueue::from_vec(data);
-        let mut i = 0;
-        for el in pq.iter() {
-            assert_eq!(*el, iterout[i]);
-            i += 1;
-        }
-    }
-
-    #[test]
-    fn test_top_and_pop() {
-        let data = ~[2u, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
-        let mut sorted = data.clone();
-        sorted.sort();
-        let mut heap = PriorityQueue::from_vec(data);
-        while !heap.is_empty() {
-            assert_eq!(heap.top(), sorted.last().unwrap());
-            assert_eq!(heap.pop(), sorted.pop().unwrap());
-        }
-    }
-
-    #[test]
-    fn test_push() {
-        let mut heap = PriorityQueue::from_vec(~[2, 4, 9]);
-        assert_eq!(heap.len(), 3);
-        assert!(*heap.top() == 9);
-        heap.push(11);
-        assert_eq!(heap.len(), 4);
-        assert!(*heap.top() == 11);
-        heap.push(5);
-        assert_eq!(heap.len(), 5);
-        assert!(*heap.top() == 11);
-        heap.push(27);
-        assert_eq!(heap.len(), 6);
-        assert!(*heap.top() == 27);
-        heap.push(3);
-        assert_eq!(heap.len(), 7);
-        assert!(*heap.top() == 27);
-        heap.push(103);
-        assert_eq!(heap.len(), 8);
-        assert!(*heap.top() == 103);
-    }
-
-    #[test]
-    fn test_push_unique() {
-        let mut heap = PriorityQueue::from_vec(~[~2, ~4, ~9]);
-        assert_eq!(heap.len(), 3);
-        assert!(*heap.top() == ~9);
-        heap.push(~11);
-        assert_eq!(heap.len(), 4);
-        assert!(*heap.top() == ~11);
-        heap.push(~5);
-        assert_eq!(heap.len(), 5);
-        assert!(*heap.top() == ~11);
-        heap.push(~27);
-        assert_eq!(heap.len(), 6);
-        assert!(*heap.top() == ~27);
-        heap.push(~3);
-        assert_eq!(heap.len(), 7);
-        assert!(*heap.top() == ~27);
-        heap.push(~103);
-        assert_eq!(heap.len(), 8);
-        assert!(*heap.top() == ~103);
-    }
-
-    #[test]
-    fn test_push_pop() {
-        let mut heap = PriorityQueue::from_vec(~[5, 5, 2, 1, 3]);
-        assert_eq!(heap.len(), 5);
-        assert_eq!(heap.push_pop(6), 6);
-        assert_eq!(heap.len(), 5);
-        assert_eq!(heap.push_pop(0), 5);
-        assert_eq!(heap.len(), 5);
-        assert_eq!(heap.push_pop(4), 5);
-        assert_eq!(heap.len(), 5);
-        assert_eq!(heap.push_pop(1), 4);
-        assert_eq!(heap.len(), 5);
-    }
-
-    #[test]
-    fn test_replace() {
-        let mut heap = PriorityQueue::from_vec(~[5, 5, 2, 1, 3]);
-        assert_eq!(heap.len(), 5);
-        assert_eq!(heap.replace(6), 5);
-        assert_eq!(heap.len(), 5);
-        assert_eq!(heap.replace(0), 6);
-        assert_eq!(heap.len(), 5);
-        assert_eq!(heap.replace(4), 5);
-        assert_eq!(heap.len(), 5);
-        assert_eq!(heap.replace(1), 4);
-        assert_eq!(heap.len(), 5);
-    }
-
-    fn check_to_vec(mut data: ~[int]) {
-        let heap = PriorityQueue::from_vec(data.clone());
-        let mut v = heap.clone().to_vec();
-        v.sort();
-        data.sort();
-
-        assert_eq!(v, data);
-        assert_eq!(heap.to_sorted_vec(), data);
-    }
-
-    #[test]
-    fn test_to_vec() {
-        check_to_vec(~[]);
-        check_to_vec(~[5]);
-        check_to_vec(~[3, 2]);
-        check_to_vec(~[2, 3]);
-        check_to_vec(~[5, 1, 2]);
-        check_to_vec(~[1, 100, 2, 3]);
-        check_to_vec(~[1, 3, 5, 7, 9, 2, 4, 6, 8, 0]);
-        check_to_vec(~[2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
-        check_to_vec(~[9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]);
-        check_to_vec(~[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
-        check_to_vec(~[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]);
-        check_to_vec(~[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]);
-        check_to_vec(~[5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]);
-    }
-
-    #[test]
-    #[should_fail]
-    fn test_empty_pop() {
-        let mut heap: PriorityQueue<int> = PriorityQueue::new();
-        heap.pop();
-    }
-
-    #[test]
-    fn test_empty_maybe_pop() {
-        let mut heap: PriorityQueue<int> = PriorityQueue::new();
-        assert!(heap.maybe_pop().is_none());
-    }
-
-    #[test]
-    #[should_fail]
-    fn test_empty_top() {
-        let empty: PriorityQueue<int> = PriorityQueue::new();
-        empty.top();
-    }
-
-    #[test]
-    fn test_empty_maybe_top() {
-        let empty: PriorityQueue<int> = PriorityQueue::new();
-        assert!(empty.maybe_top().is_none());
-    }
-
-    #[test]
-    #[should_fail]
-    fn test_empty_replace() {
-        let mut heap: PriorityQueue<int> = PriorityQueue::new();
-        heap.replace(5);
-    }
-
-    #[test]
-    fn test_from_iter() {
-        let xs = ~[9u, 8, 7, 6, 5, 4, 3, 2, 1];
-
-        let mut q: PriorityQueue<uint> = xs.rev_iter().map(|&x| x).collect();
-
-        for &x in xs.iter() {
-            assert_eq!(q.pop(), x);
-        }
-    }
-}
diff --git a/src/libextra/ringbuf.rs b/src/libextra/ringbuf.rs
deleted file mode 100644
index 17631f5bdff..00000000000
--- a/src/libextra/ringbuf.rs
+++ /dev/null
@@ -1,858 +0,0 @@
-// Copyright 2012-2013 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-//! A double-ended queue implemented as a circular buffer
-//!
-//! RingBuf implements the trait Deque. It should be imported with `use
-//! extra::container::Deque`.
-
-use std::num;
-use std::vec;
-use std::iter::{Rev, RandomAccessIterator};
-
-use container::Deque;
-
-use serialize::{Encodable, Decodable, Encoder, Decoder};
-
-static INITIAL_CAPACITY: uint = 8u; // 2^3
-static MINIMUM_CAPACITY: uint = 2u;
-
-/// RingBuf is a circular buffer that implements Deque.
-#[deriving(Clone)]
-pub struct RingBuf<T> {
-    priv nelts: uint,
-    priv lo: uint,
-    priv elts: ~[Option<T>]
-}
-
-impl<T> Container for RingBuf<T> {
-    /// Return the number of elements in the RingBuf
-    fn len(&self) -> uint { self.nelts }
-}
-
-impl<T> Mutable for RingBuf<T> {
-    /// Clear the RingBuf, removing all values.
-    fn clear(&mut self) {
-        for x in self.elts.mut_iter() { *x = None }
-        self.nelts = 0;
-        self.lo = 0;
-    }
-}
-
-impl<T> Deque<T> for RingBuf<T> {
-    /// Return a reference to the first element in the RingBuf
-    fn front<'a>(&'a self) -> Option<&'a T> {
-        if self.nelts > 0 { Some(self.get(0)) } else { None }
-    }
-
-    /// Return a mutable reference to the first element in the RingBuf
-    fn front_mut<'a>(&'a mut self) -> Option<&'a mut T> {
-        if self.nelts > 0 { Some(self.get_mut(0)) } else { None }
-    }
-
-    /// Return a reference to the last element in the RingBuf
-    fn back<'a>(&'a self) -> Option<&'a T> {
-        if self.nelts > 0 { Some(self.get(self.nelts - 1)) } else { None }
-    }
-
-    /// Return a mutable reference to the last element in the RingBuf
-    fn back_mut<'a>(&'a mut self) -> Option<&'a mut T> {
-        if self.nelts > 0 { Some(self.get_mut(self.nelts - 1)) } else { None }
-    }
-
-    /// Remove and return the first element in the RingBuf, or None if it is empty
-    fn pop_front(&mut self) -> Option<T> {
-        let result = self.elts[self.lo].take();
-        if result.is_some() {
-            self.lo = (self.lo + 1u) % self.elts.len();
-            self.nelts -= 1u;
-        }
-        result
-    }
-
-    /// Remove and return the last element in the RingBuf, or None if it is empty
-    fn pop_back(&mut self) -> Option<T> {
-        if self.nelts > 0 {
-            self.nelts -= 1;
-            let hi = self.raw_index(self.nelts);
-            self.elts[hi].take()
-        } else {
-            None
-        }
-    }
-
-    /// Prepend an element to the RingBuf
-    fn push_front(&mut self, t: T) {
-        if self.nelts == self.elts.len() {
-            grow(self.nelts, &mut self.lo, &mut self.elts);
-        }
-        if self.lo == 0u {
-            self.lo = self.elts.len() - 1u;
-        } else { self.lo -= 1u; }
-        self.elts[self.lo] = Some(t);
-        self.nelts += 1u;
-    }
-
-    /// Append an element to the RingBuf
-    fn push_back(&mut self, t: T) {
-        if self.nelts == self.elts.len() {
-            grow(self.nelts, &mut self.lo, &mut self.elts);
-        }
-        let hi = self.raw_index(self.nelts);
-        self.elts[hi] = Some(t);
-        self.nelts += 1u;
-    }
-}
-
-impl<T> RingBuf<T> {
-    /// Create an empty RingBuf
-    pub fn new() -> RingBuf<T> {
-        RingBuf::with_capacity(INITIAL_CAPACITY)
-    }
-
-    /// Create an empty RingBuf with space for at least `n` elements.
-    pub fn with_capacity(n: uint) -> RingBuf<T> {
-        RingBuf{nelts: 0, lo: 0,
-              elts: vec::from_fn(num::max(MINIMUM_CAPACITY, n), |_| None)}
-    }
-
-    /// Retrieve an element in the RingBuf by index
-    ///
-    /// Fails if there is no element with the given index
-    pub fn get<'a>(&'a self, i: uint) -> &'a T {
-        let idx = self.raw_index(i);
-        match self.elts[idx] {
-            None => fail!(),
-            Some(ref v) => v
-        }
-    }
-
-    /// Retrieve an element in the RingBuf by index
-    ///
-    /// Fails if there is no element with the given index
-    pub fn get_mut<'a>(&'a mut self, i: uint) -> &'a mut T {
-        let idx = self.raw_index(i);
-        match self.elts[idx] {
-            None => fail!(),
-            Some(ref mut v) => v
-        }
-    }
-
-    /// Swap elements at indices `i` and `j`
-    ///
-    /// `i` and `j` may be equal.
-    ///
-    /// Fails if there is no element with the given index
-    pub fn swap(&mut self, i: uint, j: uint) {
-        assert!(i < self.len());
-        assert!(j < self.len());
-        let ri = self.raw_index(i);
-        let rj = self.raw_index(j);
-        self.elts.swap(ri, rj);
-    }
-
-    /// Return index in underlying vec for a given logical element index
-    fn raw_index(&self, idx: uint) -> uint {
-        raw_index(self.lo, self.elts.len(), idx)
-    }
-
-    /// Reserve capacity for exactly `n` elements in the given RingBuf,
-    /// doing nothing if `self`'s capacity is already equal to or greater
-    /// than the requested capacity
-    ///
-    /// # Arguments
-    ///
-    /// * n - The number of elements to reserve space for
-    pub fn reserve_exact(&mut self, n: uint) {
-        self.elts.reserve_exact(n);
-    }
-
-    /// Reserve capacity for at least `n` elements in the given RingBuf,
-    /// over-allocating in case the caller needs to reserve additional
-    /// space.
-    ///
-    /// Do nothing if `self`'s capacity is already equal to or greater
-    /// than the requested capacity.
-    ///
-    /// # Arguments
-    ///
-    /// * n - The number of elements to reserve space for
-    pub fn reserve(&mut self, n: uint) {
-        self.elts.reserve(n);
-    }
-
-    /// Front-to-back iterator.
-    pub fn iter<'a>(&'a self) -> Items<'a, T> {
-        Items{index: 0, rindex: self.nelts, lo: self.lo, elts: self.elts}
-    }
-
-    /// Back-to-front iterator.
-    pub fn rev_iter<'a>(&'a self) -> Rev<Items<'a, T>> {
-        self.iter().rev()
-    }
-
-    /// Front-to-back iterator which returns mutable values.
-    pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T> {
-        let start_index = raw_index(self.lo, self.elts.len(), 0);
-        let end_index = raw_index(self.lo, self.elts.len(), self.nelts);
-
-        // Divide up the array
-        if end_index <= start_index {
-            // Items to iterate goes from:
-            //    start_index to self.elts.len()
-            // and then
-            //    0 to end_index
-            let (temp, remaining1) = self.elts.mut_split_at(start_index);
-            let (remaining2, _) = temp.mut_split_at(end_index);
-            MutItems { remaining1: remaining1,
-                                 remaining2: remaining2,
-                                 nelts: self.nelts }
-        } else {
-            // Items to iterate goes from start_index to end_index:
-            let (empty, elts) = self.elts.mut_split_at(0);
-            let remaining1 = elts.mut_slice(start_index, end_index);
-            MutItems { remaining1: remaining1,
-                                 remaining2: empty,
-                                 nelts: self.nelts }
-        }
-    }
-
-    /// Back-to-front iterator which returns mutable values.
-    pub fn mut_rev_iter<'a>(&'a mut self) -> Rev<MutItems<'a, T>> {
-        self.mut_iter().rev()
-    }
-}
-
-/// RingBuf iterator
-pub struct Items<'a, T> {
-    priv lo: uint,
-    priv index: uint,
-    priv rindex: uint,
-    priv elts: &'a [Option<T>],
-}
-
-impl<'a, T> Iterator<&'a T> for Items<'a, T> {
-    #[inline]
-    fn next(&mut self) -> Option<&'a T> {
-        if self.index == self.rindex {
-            return None;
-        }
-        let raw_index = raw_index(self.lo, self.elts.len(), self.index);
-        self.index += 1;
-        Some(self.elts[raw_index].get_ref())
-    }
-
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        let len = self.rindex - self.index;
-        (len, Some(len))
-    }
-}
-
-impl<'a, T> DoubleEndedIterator<&'a T> for Items<'a, T> {
-    #[inline]
-    fn next_back(&mut self) -> Option<&'a T> {
-        if self.index == self.rindex {
-            return None;
-        }
-        self.rindex -= 1;
-        let raw_index = raw_index(self.lo, self.elts.len(), self.rindex);
-        Some(self.elts[raw_index].get_ref())
-    }
-}
-
-impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
-
-impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
-    #[inline]
-    fn indexable(&self) -> uint { self.rindex - self.index }
-
-    #[inline]
-    fn idx(&self, j: uint) -> Option<&'a T> {
-        if j >= self.indexable() {
-            None
-        } else {
-            let raw_index = raw_index(self.lo, self.elts.len(), self.index + j);
-            Some(self.elts[raw_index].get_ref())
-        }
-    }
-}
-
-/// RingBuf mutable iterator
-pub struct MutItems<'a, T> {
-    priv remaining1: &'a mut [Option<T>],
-    priv remaining2: &'a mut [Option<T>],
-    priv nelts: uint,
-}
-
-impl<'a, T> Iterator<&'a mut T> for MutItems<'a, T> {
-    #[inline]
-    fn next(&mut self) -> Option<&'a mut T> {
-        if self.nelts == 0 {
-            return None;
-        }
-        let r = if self.remaining1.len() > 0 {
-            &mut self.remaining1
-        } else {
-            assert!(self.remaining2.len() > 0);
-            &mut self.remaining2
-        };
-        self.nelts -= 1;
-        Some(r.mut_shift_ref().unwrap().get_mut_ref())
-    }
-
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        (self.nelts, Some(self.nelts))
-    }
-}
-
-impl<'a, T> DoubleEndedIterator<&'a mut T> for MutItems<'a, T> {
-    #[inline]
-    fn next_back(&mut self) -> Option<&'a mut T> {
-        if self.nelts == 0 {
-            return None;
-        }
-        let r = if self.remaining2.len() > 0 {
-            &mut self.remaining2
-        } else {
-            assert!(self.remaining1.len() > 0);
-            &mut self.remaining1
-        };
-        self.nelts -= 1;
-        Some(r.mut_pop_ref().unwrap().get_mut_ref())
-    }
-}
-
-impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
-
-/// Grow is only called on full elts, so nelts is also len(elts), unlike
-/// elsewhere.
-fn grow<T>(nelts: uint, loptr: &mut uint, elts: &mut ~[Option<T>]) {
-    assert_eq!(nelts, elts.len());
-    let lo = *loptr;
-    let newlen = nelts * 2;
-    elts.reserve(newlen);
-
-    /* fill with None */
-    for _ in range(elts.len(), elts.capacity()) {
-        elts.push(None);
-    }
-
-    /*
-      Move the shortest half into the newly reserved area.
-      lo ---->|
-      nelts ----------->|
-        [o o o|o o o o o]
-      A [. . .|o o o o o o o o|. . . . .]
-      B [o o o|. . . . . . . .|o o o o o]
-     */
-
-    assert!(newlen - nelts/2 >= nelts);
-    if lo <= (nelts - lo) { // A
-        for i in range(0u, lo) {
-            elts.swap(i, nelts + i);
-        }
-    } else {                // B
-        for i in range(lo, nelts) {
-            elts.swap(i, newlen - nelts + i);
-        }
-        *loptr += newlen - nelts;
-    }
-}
-
-/// Return index in underlying vec for a given logical element index
-fn raw_index(lo: uint, len: uint, index: uint) -> uint {
-    if lo >= len - index {
-        lo + index - len
-    } else {
-        lo + index
-    }
-}
-
-impl<A: Eq> Eq for RingBuf<A> {
-    fn eq(&self, other: &RingBuf<A>) -> bool {
-        self.nelts == other.nelts &&
-            self.iter().zip(other.iter()).all(|(a, b)| a.eq(b))
-    }
-    fn ne(&self, other: &RingBuf<A>) -> bool {
-        !self.eq(other)
-    }
-}
-
-impl<A> FromIterator<A> for RingBuf<A> {
-    fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> RingBuf<A> {
-        let (lower, _) = iterator.size_hint();
-        let mut deq = RingBuf::with_capacity(lower);
-        deq.extend(iterator);
-        deq
-    }
-}
-
-impl<A> Extendable<A> for RingBuf<A> {
-    fn extend<T: Iterator<A>>(&mut self, iterator: &mut T) {
-        for elt in *iterator {
-            self.push_back(elt);
-        }
-    }
-}
-
-impl<
-    S: Encoder,
-    T: Encodable<S>
-> Encodable<S> for RingBuf<T> {
-    fn encode(&self, s: &mut S) {
-        s.emit_seq(self.len(), |s| {
-            for (i, e) in self.iter().enumerate() {
-                s.emit_seq_elt(i, |s| e.encode(s));
-            }
-        })
-    }
-}
-
-impl<D:Decoder,T:Decodable<D>> Decodable<D> for RingBuf<T> {
-    fn decode(d: &mut D) -> RingBuf<T> {
-        let mut deque = RingBuf::new();
-        d.read_seq(|d, len| {
-            for i in range(0u, len) {
-                deque.push_back(d.read_seq_elt(i, |d| Decodable::decode(d)));
-            }
-        });
-        deque
-    }
-}
-
-#[cfg(test)]
-mod tests {
-    use container::Deque;
-    use extra::test;
-    use std::clone::Clone;
-    use std::cmp::Eq;
-    use super::RingBuf;
-
-    #[test]
-    fn test_simple() {
-        let mut d = RingBuf::new();
-        assert_eq!(d.len(), 0u);
-        d.push_front(17);
-        d.push_front(42);
-        d.push_back(137);
-        assert_eq!(d.len(), 3u);
-        d.push_back(137);
-        assert_eq!(d.len(), 4u);
-        debug!("{:?}", d.front());
-        assert_eq!(*d.front().unwrap(), 42);
-        debug!("{:?}", d.back());
-        assert_eq!(*d.back().unwrap(), 137);
-        let mut i = d.pop_front();
-        debug!("{:?}", i);
-        assert_eq!(i, Some(42));
-        i = d.pop_back();
-        debug!("{:?}", i);
-        assert_eq!(i, Some(137));
-        i = d.pop_back();
-        debug!("{:?}", i);
-        assert_eq!(i, Some(137));
-        i = d.pop_back();
-        debug!("{:?}", i);
-        assert_eq!(i, Some(17));
-        assert_eq!(d.len(), 0u);
-        d.push_back(3);
-        assert_eq!(d.len(), 1u);
-        d.push_front(2);
-        assert_eq!(d.len(), 2u);
-        d.push_back(4);
-        assert_eq!(d.len(), 3u);
-        d.push_front(1);
-        assert_eq!(d.len(), 4u);
-        debug!("{:?}", d.get(0));
-        debug!("{:?}", d.get(1));
-        debug!("{:?}", d.get(2));
-        debug!("{:?}", d.get(3));
-        assert_eq!(*d.get(0), 1);
-        assert_eq!(*d.get(1), 2);
-        assert_eq!(*d.get(2), 3);
-        assert_eq!(*d.get(3), 4);
-    }
-
-    #[test]
-    fn test_boxes() {
-        let a: @int = @5;
-        let b: @int = @72;
-        let c: @int = @64;
-        let d: @int = @175;
-
-        let mut deq = RingBuf::new();
-        assert_eq!(deq.len(), 0);
-        deq.push_front(a);
-        deq.push_front(b);
-        deq.push_back(c);
-        assert_eq!(deq.len(), 3);
-        deq.push_back(d);
-        assert_eq!(deq.len(), 4);
-        assert_eq!(deq.front(), Some(&b));
-        assert_eq!(deq.back(), Some(&d));
-        assert_eq!(deq.pop_front(), Some(b));
-        assert_eq!(deq.pop_back(), Some(d));
-        assert_eq!(deq.pop_back(), Some(c));
-        assert_eq!(deq.pop_back(), Some(a));
-        assert_eq!(deq.len(), 0);
-        deq.push_back(c);
-        assert_eq!(deq.len(), 1);
-        deq.push_front(b);
-        assert_eq!(deq.len(), 2);
-        deq.push_back(d);
-        assert_eq!(deq.len(), 3);
-        deq.push_front(a);
-        assert_eq!(deq.len(), 4);
-        assert_eq!(*deq.get(0), a);
-        assert_eq!(*deq.get(1), b);
-        assert_eq!(*deq.get(2), c);
-        assert_eq!(*deq.get(3), d);
-    }
-
-    #[cfg(test)]
-    fn test_parameterized<T:Clone + Eq>(a: T, b: T, c: T, d: T) {
-        let mut deq = RingBuf::new();
-        assert_eq!(deq.len(), 0);
-        deq.push_front(a.clone());
-        deq.push_front(b.clone());
-        deq.push_back(c.clone());
-        assert_eq!(deq.len(), 3);
-        deq.push_back(d.clone());
-        assert_eq!(deq.len(), 4);
-        assert_eq!((*deq.front().unwrap()).clone(), b.clone());
-        assert_eq!((*deq.back().unwrap()).clone(), d.clone());
-        assert_eq!(deq.pop_front().unwrap(), b.clone());
-        assert_eq!(deq.pop_back().unwrap(), d.clone());
-        assert_eq!(deq.pop_back().unwrap(), c.clone());
-        assert_eq!(deq.pop_back().unwrap(), a.clone());
-        assert_eq!(deq.len(), 0);
-        deq.push_back(c.clone());
-        assert_eq!(deq.len(), 1);
-        deq.push_front(b.clone());
-        assert_eq!(deq.len(), 2);
-        deq.push_back(d.clone());
-        assert_eq!(deq.len(), 3);
-        deq.push_front(a.clone());
-        assert_eq!(deq.len(), 4);
-        assert_eq!((*deq.get(0)).clone(), a.clone());
-        assert_eq!((*deq.get(1)).clone(), b.clone());
-        assert_eq!((*deq.get(2)).clone(), c.clone());
-        assert_eq!((*deq.get(3)).clone(), d.clone());
-    }
-
-    #[test]
-    fn test_push_front_grow() {
-        let mut deq = RingBuf::new();
-        for i in range(0u, 66) {
-            deq.push_front(i);
-        }
-        assert_eq!(deq.len(), 66);
-
-        for i in range(0u, 66) {
-            assert_eq!(*deq.get(i), 65 - i);
-        }
-
-        let mut deq = RingBuf::new();
-        for i in range(0u, 66) {
-            deq.push_back(i);
-        }
-
-        for i in range(0u, 66) {
-            assert_eq!(*deq.get(i), i);
-        }
-    }
-
-    #[bench]
-    fn bench_new(b: &mut test::BenchHarness) {
-        b.iter(|| {
-            let _: RingBuf<u64> = RingBuf::new();
-        })
-    }
-
-    #[bench]
-    fn bench_push_back(b: &mut test::BenchHarness) {
-        let mut deq = RingBuf::new();
-        b.iter(|| {
-            deq.push_back(0);
-        })
-    }
-
-    #[bench]
-    fn bench_push_front(b: &mut test::BenchHarness) {
-        let mut deq = RingBuf::new();
-        b.iter(|| {
-            deq.push_front(0);
-        })
-    }
-
-    #[bench]
-    fn bench_grow(b: &mut test::BenchHarness) {
-        let mut deq = RingBuf::new();
-        b.iter(|| {
-            for _ in range(0, 65) {
-                deq.push_front(1);
-            }
-        })
-    }
-
-    #[deriving(Clone, Eq)]
-    enum Taggy {
-        One(int),
-        Two(int, int),
-        Three(int, int, int),
-    }
-
-    #[deriving(Clone, Eq)]
-    enum Taggypar<T> {
-        Onepar(int),
-        Twopar(int, int),
-        Threepar(int, int, int),
-    }
-
-    #[deriving(Clone, Eq)]
-    struct RecCy {
-        x: int,
-        y: int,
-        t: Taggy
-    }
-
-    #[test]
-    fn test_param_int() {
-        test_parameterized::<int>(5, 72, 64, 175);
-    }
-
-    #[test]
-    fn test_param_at_int() {
-        test_parameterized::<@int>(@5, @72, @64, @175);
-    }
-
-    #[test]
-    fn test_param_taggy() {
-        test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
-    }
-
-    #[test]
-    fn test_param_taggypar() {
-        test_parameterized::<Taggypar<int>>(Onepar::<int>(1),
-                                            Twopar::<int>(1, 2),
-                                            Threepar::<int>(1, 2, 3),
-                                            Twopar::<int>(17, 42));
-    }
-
-    #[test]
-    fn test_param_reccy() {
-        let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
-        let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
-        let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
-        let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
-        test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
-    }
-
-    #[test]
-    fn test_with_capacity() {
-        let mut d = RingBuf::with_capacity(0);
-        d.push_back(1);
-        assert_eq!(d.len(), 1);
-        let mut d = RingBuf::with_capacity(50);
-        d.push_back(1);
-        assert_eq!(d.len(), 1);
-    }
-
-    #[test]
-    fn test_reserve_exact() {
-        let mut d = RingBuf::new();
-        d.push_back(0u64);
-        d.reserve_exact(50);
-        assert_eq!(d.elts.capacity(), 50);
-        let mut d = RingBuf::new();
-        d.push_back(0u32);
-        d.reserve_exact(50);
-        assert_eq!(d.elts.capacity(), 50);
-    }
-
-    #[test]
-    fn test_reserve() {
-        let mut d = RingBuf::new();
-        d.push_back(0u64);
-        d.reserve(50);
-        assert_eq!(d.elts.capacity(), 64);
-        let mut d = RingBuf::new();
-        d.push_back(0u32);
-        d.reserve(50);
-        assert_eq!(d.elts.capacity(), 64);
-    }
-
-    #[test]
-    fn test_swap() {
-        let mut d: RingBuf<int> = range(0, 5).collect();
-        d.pop_front();
-        d.swap(0, 3);
-        assert_eq!(d.iter().map(|&x|x).collect::<~[int]>(), ~[4, 2, 3, 1]);
-    }
-
-    #[test]
-    fn test_iter() {
-        let mut d = RingBuf::new();
-        assert_eq!(d.iter().next(), None);
-        assert_eq!(d.iter().size_hint(), (0, Some(0)));
-
-        for i in range(0, 5) {
-            d.push_back(i);
-        }
-        assert_eq!(d.iter().collect::<~[&int]>(), ~[&0,&1,&2,&3,&4]);
-
-        for i in range(6, 9) {
-            d.push_front(i);
-        }
-        assert_eq!(d.iter().collect::<~[&int]>(), ~[&8,&7,&6,&0,&1,&2,&3,&4]);
-
-        let mut it = d.iter();
-        let mut len = d.len();
-        loop {
-            match it.next() {
-                None => break,
-                _ => { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) }
-            }
-        }
-    }
-
-    #[test]
-    fn test_rev_iter() {
-        let mut d = RingBuf::new();
-        assert_eq!(d.rev_iter().next(), None);
-
-        for i in range(0, 5) {
-            d.push_back(i);
-        }
-        assert_eq!(d.rev_iter().collect::<~[&int]>(), ~[&4,&3,&2,&1,&0]);
-
-        for i in range(6, 9) {
-            d.push_front(i);
-        }
-        assert_eq!(d.rev_iter().collect::<~[&int]>(), ~[&4,&3,&2,&1,&0,&6,&7,&8]);
-    }
-
-    #[test]
-    fn test_mut_rev_iter_wrap() {
-        let mut d = RingBuf::with_capacity(3);
-        assert!(d.mut_rev_iter().next().is_none());
-
-        d.push_back(1);
-        d.push_back(2);
-        d.push_back(3);
-        assert_eq!(d.pop_front(), Some(1));
-        d.push_back(4);
-
-        assert_eq!(d.mut_rev_iter().map(|x| *x).collect::<~[int]>(),
-                   ~[4, 3, 2]);
-    }
-
-    #[test]
-    fn test_mut_iter() {
-        let mut d = RingBuf::new();
-        assert!(d.mut_iter().next().is_none());
-
-        for i in range(0u, 3) {
-            d.push_front(i);
-        }
-
-        for (i, elt) in d.mut_iter().enumerate() {
-            assert_eq!(*elt, 2 - i);
-            *elt = i;
-        }
-
-        {
-            let mut it = d.mut_iter();
-            assert_eq!(*it.next().unwrap(), 0);
-            assert_eq!(*it.next().unwrap(), 1);
-            assert_eq!(*it.next().unwrap(), 2);
-            assert!(it.next().is_none());
-        }
-    }
-
-    #[test]
-    fn test_mut_rev_iter() {
-        let mut d = RingBuf::new();
-        assert!(d.mut_rev_iter().next().is_none());
-
-        for i in range(0u, 3) {
-            d.push_front(i);
-        }
-
-        for (i, elt) in d.mut_rev_iter().enumerate() {
-            assert_eq!(*elt, i);
-            *elt = i;
-        }
-
-        {
-            let mut it = d.mut_rev_iter();
-            assert_eq!(*it.next().unwrap(), 0);
-            assert_eq!(*it.next().unwrap(), 1);
-            assert_eq!(*it.next().unwrap(), 2);
-            assert!(it.next().is_none());
-        }
-    }
-
-    #[test]
-    fn test_from_iterator() {
-        use std::iter;
-        let v = ~[1,2,3,4,5,6,7];
-        let deq: RingBuf<int> = v.iter().map(|&x| x).collect();
-        let u: ~[int] = deq.iter().map(|&x| x).collect();
-        assert_eq!(u, v);
-
-        let mut seq = iter::count(0u, 2).take(256);
-        let deq: RingBuf<uint> = seq.collect();
-        for (i, &x) in deq.iter().enumerate() {
-            assert_eq!(2*i, x);
-        }
-        assert_eq!(deq.len(), 256);
-    }
-
-    #[test]
-    fn test_clone() {
-        let mut d = RingBuf::new();
-        d.push_front(17);
-        d.push_front(42);
-        d.push_back(137);
-        d.push_back(137);
-        assert_eq!(d.len(), 4u);
-        let mut e = d.clone();
-        assert_eq!(e.len(), 4u);
-        while !d.is_empty() {
-            assert_eq!(d.pop_back(), e.pop_back());
-        }
-        assert_eq!(d.len(), 0u);
-        assert_eq!(e.len(), 0u);
-    }
-
-    #[test]
-    fn test_eq() {
-        let mut d = RingBuf::new();
-        assert_eq!(&d, &RingBuf::with_capacity(0));
-        d.push_front(137);
-        d.push_front(17);
-        d.push_front(42);
-        d.push_back(137);
-        let mut e = RingBuf::with_capacity(0);
-        e.push_back(42);
-        e.push_back(17);
-        e.push_back(137);
-        e.push_back(137);
-        assert_eq!(&e, &d);
-        e.pop_back();
-        e.push_back(0);
-        assert!(e != d);
-        e.clear();
-        assert_eq!(e, RingBuf::new());
-    }
-}
diff --git a/src/libextra/smallintmap.rs b/src/libextra/smallintmap.rs
deleted file mode 100644
index abbd987a9c4..00000000000
--- a/src/libextra/smallintmap.rs
+++ /dev/null
@@ -1,529 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-/*!
- * A simple map based on a vector for small integer keys. Space requirements
- * are O(highest integer key).
- */
-
-#[allow(missing_doc)];
-
-use std::iter::{Enumerate, FilterMap, Rev};
-use std::util::replace;
-use std::vec;
-
-#[allow(missing_doc)]
-pub struct SmallIntMap<T> {
-    priv v: ~[Option<T>],
-}
-
-impl<V> Container for SmallIntMap<V> {
-    /// Return the number of elements in the map
-    fn len(&self) -> uint {
-        self.v.iter().count(|elt| elt.is_some())
-    }
-
-    /// Return true if there are no elements in the map
-    fn is_empty(&self) -> bool {
-        self.v.iter().all(|elt| elt.is_none())
-    }
-}
-
-impl<V> Mutable for SmallIntMap<V> {
-    /// Clear the map, removing all key-value pairs.
-    fn clear(&mut self) { self.v.clear() }
-}
-
-impl<V> Map<uint, V> for SmallIntMap<V> {
-    /// Return a reference to the value corresponding to the key
-    fn find<'a>(&'a self, key: &uint) -> Option<&'a V> {
-        if *key < self.v.len() {
-            match self.v[*key] {
-              Some(ref value) => Some(value),
-              None => None
-            }
-        } else {
-            None
-        }
-    }
-}
-
-impl<V> MutableMap<uint, V> for SmallIntMap<V> {
-    /// Return a mutable reference to the value corresponding to the key
-    fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut V> {
-        if *key < self.v.len() {
-            match self.v[*key] {
-              Some(ref mut value) => Some(value),
-              None => None
-            }
-        } else {
-            None
-        }
-    }
-
-    /// Insert a key-value pair into the map. An existing value for a
-    /// key is replaced by the new value. Return true if the key did
-    /// not already exist in the map.
-    fn insert(&mut self, key: uint, value: V) -> bool {
-        let exists = self.contains_key(&key);
-        let len = self.v.len();
-        if len <= key {
-            self.v.grow_fn(key - len + 1, |_| None);
-        }
-        self.v[key] = Some(value);
-        !exists
-    }
-
-    /// Remove a key-value pair from the map. Return true if the key
-    /// was present in the map, otherwise false.
-    fn remove(&mut self, key: &uint) -> bool {
-        self.pop(key).is_some()
-    }
-
-    /// Insert a key-value pair from the map. If the key already had a value
-    /// present in the map, that value is returned. Otherwise None is returned.
-    fn swap(&mut self, key: uint, value: V) -> Option<V> {
-        match self.find_mut(&key) {
-            Some(loc) => { return Some(replace(loc, value)); }
-            None => ()
-        }
-        self.insert(key, value);
-        return None;
-    }
-
-    /// Removes a key from the map, returning the value at the key if the key
-    /// was previously in the map.
-    fn pop(&mut self, key: &uint) -> Option<V> {
-        if *key >= self.v.len() {
-            return None;
-        }
-        self.v[*key].take()
-    }
-}
-
-impl<V> SmallIntMap<V> {
-    /// Create an empty SmallIntMap
-    pub fn new() -> SmallIntMap<V> { SmallIntMap{v: ~[]} }
-
-    pub fn get<'a>(&'a self, key: &uint) -> &'a V {
-        self.find(key).expect("key not present")
-    }
-
-    /// An iterator visiting all key-value pairs in ascending order by the keys.
-    /// Iterator element type is (uint, &'r V)
-    pub fn iter<'r>(&'r self) -> Entries<'r, V> {
-        Entries {
-            front: 0,
-            back: self.v.len(),
-            iter: self.v.iter()
-        }
-    }
-
-    /// An iterator visiting all key-value pairs in ascending order by the keys,
-    /// with mutable references to the values
-    /// Iterator element type is (uint, &'r mut V)
-    pub fn mut_iter<'r>(&'r mut self) -> MutEntries<'r, V> {
-        MutEntries {
-            front: 0,
-            back: self.v.len(),
-            iter: self.v.mut_iter()
-        }
-    }
-
-    /// An iterator visiting all key-value pairs in descending order by the keys.
-    /// Iterator element type is (uint, &'r V)
-    pub fn rev_iter<'r>(&'r self) -> RevEntries<'r, V> {
-        self.iter().rev()
-    }
-
-    /// An iterator visiting all key-value pairs in descending order by the keys,
-    /// with mutable references to the values
-    /// Iterator element type is (uint, &'r mut V)
-    pub fn mut_rev_iter<'r>(&'r mut self) -> RevMutEntries <'r, V> {
-        self.mut_iter().rev()
-    }
-
-    /// Empties the hash map, moving all values into the specified closure
-    pub fn move_iter(&mut self)
-        -> FilterMap<(uint, Option<V>), (uint, V),
-                Enumerate<vec::MoveItems<Option<V>>>>
-    {
-        let values = replace(&mut self.v, ~[]);
-        values.move_iter().enumerate().filter_map(|(i, v)| {
-            v.map(|v| (i, v))
-        })
-    }
-}
-
-impl<V:Clone> SmallIntMap<V> {
-    pub fn update_with_key(&mut self,
-                           key: uint,
-                           val: V,
-                           ff: |uint, V, V| -> V)
-                           -> bool {
-        let new_val = match self.find(&key) {
-            None => val,
-            Some(orig) => ff(key, (*orig).clone(), val)
-        };
-        self.insert(key, new_val)
-    }
-
-    pub fn update(&mut self, key: uint, newval: V, ff: |V, V| -> V) -> bool {
-        self.update_with_key(key, newval, |_k, v, v1| ff(v,v1))
-    }
-}
-
-
-macro_rules! iterator {
-    (impl $name:ident -> $elem:ty, $getter:ident) => {
-        impl<'a, T> Iterator<$elem> for $name<'a, T> {
-            #[inline]
-            fn next(&mut self) -> Option<$elem> {
-                while self.front < self.back {
-                    match self.iter.next() {
-                        Some(elem) => {
-                            if elem.is_some() {
-                                let index = self.front;
-                                self.front += 1;
-                                return Some((index, elem. $getter ()));
-                            }
-                        }
-                        _ => ()
-                    }
-                    self.front += 1;
-                }
-                None
-            }
-
-            #[inline]
-            fn size_hint(&self) -> (uint, Option<uint>) {
-                (0, Some(self.back - self.front))
-            }
-        }
-    }
-}
-
-macro_rules! double_ended_iterator {
-    (impl $name:ident -> $elem:ty, $getter:ident) => {
-        impl<'a, T> DoubleEndedIterator<$elem> for $name<'a, T> {
-            #[inline]
-            fn next_back(&mut self) -> Option<$elem> {
-                while self.front < self.back {
-                    match self.iter.next_back() {
-                        Some(elem) => {
-                            if elem.is_some() {
-                                self.back -= 1;
-                                return Some((self.back, elem. $getter ()));
-                            }
-                        }
-                        _ => ()
-                    }
-                    self.back -= 1;
-                }
-                None
-            }
-        }
-    }
-}
-
-pub struct Entries<'a, T> {
-    priv front: uint,
-    priv back: uint,
-    priv iter: vec::Items<'a, Option<T>>
-}
-
-iterator!(impl Entries -> (uint, &'a T), get_ref)
-double_ended_iterator!(impl Entries -> (uint, &'a T), get_ref)
-pub type RevEntries<'a, T> = Rev<Entries<'a, T>>;
-
-pub struct MutEntries<'a, T> {
-    priv front: uint,
-    priv back: uint,
-    priv iter: vec::MutItems<'a, Option<T>>
-}
-
-iterator!(impl MutEntries -> (uint, &'a mut T), get_mut_ref)
-double_ended_iterator!(impl MutEntries -> (uint, &'a mut T), get_mut_ref)
-pub type RevMutEntries<'a, T> = Rev<MutEntries<'a, T>>;
-
-#[cfg(test)]
-mod test_map {
-
-    use super::SmallIntMap;
-
-    #[test]
-    fn test_find_mut() {
-        let mut m = SmallIntMap::new();
-        assert!(m.insert(1, 12));
-        assert!(m.insert(2, 8));
-        assert!(m.insert(5, 14));
-        let new = 100;
-        match m.find_mut(&5) {
-            None => fail!(), Some(x) => *x = new
-        }
-        assert_eq!(m.find(&5), Some(&new));
-    }
-
-    #[test]
-    fn test_len() {
-        let mut map = SmallIntMap::new();
-        assert_eq!(map.len(), 0);
-        assert!(map.is_empty());
-        assert!(map.insert(5, 20));
-        assert_eq!(map.len(), 1);
-        assert!(!map.is_empty());
-        assert!(map.insert(11, 12));
-        assert_eq!(map.len(), 2);
-        assert!(!map.is_empty());
-        assert!(map.insert(14, 22));
-        assert_eq!(map.len(), 3);
-        assert!(!map.is_empty());
-    }
-
-    #[test]
-    fn test_clear() {
-        let mut map = SmallIntMap::new();
-        assert!(map.insert(5, 20));
-        assert!(map.insert(11, 12));
-        assert!(map.insert(14, 22));
-        map.clear();
-        assert!(map.is_empty());
-        assert!(map.find(&5).is_none());
-        assert!(map.find(&11).is_none());
-        assert!(map.find(&14).is_none());
-    }
-
-    #[test]
-    fn test_insert_with_key() {
-        let mut map = SmallIntMap::new();
-
-        // given a new key, initialize it with this new count, given
-        // given an existing key, add more to its count
-        fn addMoreToCount(_k: uint, v0: uint, v1: uint) -> uint {
-            v0 + v1
-        }
-
-        fn addMoreToCount_simple(v0: uint, v1: uint) -> uint {
-            v0 + v1
-        }
-
-        // count integers
-        map.update(3, 1, addMoreToCount_simple);
-        map.update_with_key(9, 1, addMoreToCount);
-        map.update(3, 7, addMoreToCount_simple);
-        map.update_with_key(5, 3, addMoreToCount);
-        map.update_with_key(3, 2, addMoreToCount);
-
-        // check the total counts
-        assert_eq!(map.find(&3).unwrap(), &10);
-        assert_eq!(map.find(&5).unwrap(), &3);
-        assert_eq!(map.find(&9).unwrap(), &1);
-
-        // sadly, no sevens were counted
-        assert!(map.find(&7).is_none());
-    }
-
-    #[test]
-    fn test_swap() {
-        let mut m = SmallIntMap::new();
-        assert_eq!(m.swap(1, 2), None);
-        assert_eq!(m.swap(1, 3), Some(2));
-        assert_eq!(m.swap(1, 4), Some(3));
-    }
-
-    #[test]
-    fn test_pop() {
-        let mut m = SmallIntMap::new();
-        m.insert(1, 2);
-        assert_eq!(m.pop(&1), Some(2));
-        assert_eq!(m.pop(&1), None);
-    }
-
-    #[test]
-    fn test_iterator() {
-        let mut m = SmallIntMap::new();
-
-        assert!(m.insert(0, 1));
-        assert!(m.insert(1, 2));
-        assert!(m.insert(3, 5));
-        assert!(m.insert(6, 10));
-        assert!(m.insert(10, 11));
-
-        let mut it = m.iter();
-        assert_eq!(it.size_hint(), (0, Some(11)));
-        assert_eq!(it.next().unwrap(), (0, &1));
-        assert_eq!(it.size_hint(), (0, Some(10)));
-        assert_eq!(it.next().unwrap(), (1, &2));
-        assert_eq!(it.size_hint(), (0, Some(9)));
-        assert_eq!(it.next().unwrap(), (3, &5));
-        assert_eq!(it.size_hint(), (0, Some(7)));
-        assert_eq!(it.next().unwrap(), (6, &10));
-        assert_eq!(it.size_hint(), (0, Some(4)));
-        assert_eq!(it.next().unwrap(), (10, &11));
-        assert_eq!(it.size_hint(), (0, Some(0)));
-        assert!(it.next().is_none());
-    }
-
-    #[test]
-    fn test_iterator_size_hints() {
-        let mut m = SmallIntMap::new();
-
-        assert!(m.insert(0, 1));
-        assert!(m.insert(1, 2));
-        assert!(m.insert(3, 5));
-        assert!(m.insert(6, 10));
-        assert!(m.insert(10, 11));
-
-        assert_eq!(m.iter().size_hint(), (0, Some(11)));
-        assert_eq!(m.rev_iter().size_hint(), (0, Some(11)));
-        assert_eq!(m.mut_iter().size_hint(), (0, Some(11)));
-        assert_eq!(m.mut_rev_iter().size_hint(), (0, Some(11)));
-    }
-
-    #[test]
-    fn test_mut_iterator() {
-        let mut m = SmallIntMap::new();
-
-        assert!(m.insert(0, 1));
-        assert!(m.insert(1, 2));
-        assert!(m.insert(3, 5));
-        assert!(m.insert(6, 10));
-        assert!(m.insert(10, 11));
-
-        for (k, v) in m.mut_iter() {
-            *v += k as int;
-        }
-
-        let mut it = m.iter();
-        assert_eq!(it.next().unwrap(), (0, &1));
-        assert_eq!(it.next().unwrap(), (1, &3));
-        assert_eq!(it.next().unwrap(), (3, &8));
-        assert_eq!(it.next().unwrap(), (6, &16));
-        assert_eq!(it.next().unwrap(), (10, &21));
-        assert!(it.next().is_none());
-    }
-
-    #[test]
-    fn test_rev_iterator() {
-        let mut m = SmallIntMap::new();
-
-        assert!(m.insert(0, 1));
-        assert!(m.insert(1, 2));
-        assert!(m.insert(3, 5));
-        assert!(m.insert(6, 10));
-        assert!(m.insert(10, 11));
-
-        let mut it = m.rev_iter();
-        assert_eq!(it.next().unwrap(), (10, &11));
-        assert_eq!(it.next().unwrap(), (6, &10));
-        assert_eq!(it.next().unwrap(), (3, &5));
-        assert_eq!(it.next().unwrap(), (1, &2));
-        assert_eq!(it.next().unwrap(), (0, &1));
-        assert!(it.next().is_none());
-    }
-
-    #[test]
-    fn test_mut_rev_iterator() {
-        let mut m = SmallIntMap::new();
-
-        assert!(m.insert(0, 1));
-        assert!(m.insert(1, 2));
-        assert!(m.insert(3, 5));
-        assert!(m.insert(6, 10));
-        assert!(m.insert(10, 11));
-
-        for (k, v) in m.mut_rev_iter() {
-            *v += k as int;
-        }
-
-        let mut it = m.iter();
-        assert_eq!(it.next().unwrap(), (0, &1));
-        assert_eq!(it.next().unwrap(), (1, &3));
-        assert_eq!(it.next().unwrap(), (3, &8));
-        assert_eq!(it.next().unwrap(), (6, &16));
-        assert_eq!(it.next().unwrap(), (10, &21));
-        assert!(it.next().is_none());
-    }
-
-    #[test]
-    fn test_move_iter() {
-        let mut m = SmallIntMap::new();
-        m.insert(1, ~2);
-        let mut called = false;
-        for (k, v) in m.move_iter() {
-            assert!(!called);
-            called = true;
-            assert_eq!(k, 1);
-            assert_eq!(v, ~2);
-        }
-        assert!(called);
-        m.insert(2, ~1);
-    }
-}
-
-#[cfg(test)]
-mod bench {
-
-    use super::*;
-    use test::BenchHarness;
-    use container::bench::*;
-
-    // Find seq
-    #[bench]
-    pub fn insert_rand_100(bh: &mut BenchHarness) {
-        let mut m : SmallIntMap<uint> = SmallIntMap::new();
-        insert_rand_n(100, &mut m, bh);
-    }
-
-    #[bench]
-    pub fn insert_rand_10_000(bh: &mut BenchHarness) {
-        let mut m : SmallIntMap<uint> = SmallIntMap::new();
-        insert_rand_n(10_000, &mut m, bh);
-    }
-
-    // Insert seq
-    #[bench]
-    pub fn insert_seq_100(bh: &mut BenchHarness) {
-        let mut m : SmallIntMap<uint> = SmallIntMap::new();
-        insert_seq_n(100, &mut m, bh);
-    }
-
-    #[bench]
-    pub fn insert_seq_10_000(bh: &mut BenchHarness) {
-        let mut m : SmallIntMap<uint> = SmallIntMap::new();
-        insert_seq_n(10_000, &mut m, bh);
-    }
-
-    // Find rand
-    #[bench]
-    pub fn find_rand_100(bh: &mut BenchHarness) {
-        let mut m : SmallIntMap<uint> = SmallIntMap::new();
-        find_rand_n(100, &mut m, bh);
-    }
-
-    #[bench]
-    pub fn find_rand_10_000(bh: &mut BenchHarness) {
-        let mut m : SmallIntMap<uint> = SmallIntMap::new();
-        find_rand_n(10_000, &mut m, bh);
-    }
-
-    // Find seq
-    #[bench]
-    pub fn find_seq_100(bh: &mut BenchHarness) {
-        let mut m : SmallIntMap<uint> = SmallIntMap::new();
-        find_seq_n(100, &mut m, bh);
-    }
-
-    #[bench]
-    pub fn find_seq_10_000(bh: &mut BenchHarness) {
-        let mut m : SmallIntMap<uint> = SmallIntMap::new();
-        find_seq_n(10_000, &mut m, bh);
-    }
-}
diff --git a/src/libextra/test.rs b/src/libextra/test.rs
index 4af0fa16233..d1fffd9e515 100644
--- a/src/libextra/test.rs
+++ b/src/libextra/test.rs
@@ -24,7 +24,7 @@ use serialize::Decodable;
 use stats::Stats;
 use stats;
 use time::precise_time_ns;
-use treemap::TreeMap;
+use collections::TreeMap;
 
 use std::clone::Clone;
 use std::io;
diff --git a/src/libextra/treemap.rs b/src/libextra/treemap.rs
deleted file mode 100644
index 449e72dd0ec..00000000000
--- a/src/libextra/treemap.rs
+++ /dev/null
@@ -1,1803 +0,0 @@
-// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-//! An ordered map and set implemented as self-balancing binary search
-//! trees. The only requirement for the types is that the key implements
-//! `TotalOrd`.
-
-use std::util::{swap, replace};
-use std::iter::{Peekable};
-use std::cmp::Ordering;
-use std::ptr;
-
-use serialize::{Encodable, Decodable, Encoder, Decoder};
-
-// This is implemented as an AA tree, which is a simplified variation of
-// a red-black tree where red (horizontal) nodes can only be added
-// as a right child. The time complexity is the same, and re-balancing
-// operations are more frequent but also cheaper.
-
-// Future improvements:
-
-// range search - O(log n) retrieval of an iterator from some key
-
-// (possibly) implement the overloads Python does for sets:
-//   * intersection: &
-//   * difference: -
-//   * symmetric difference: ^
-//   * union: |
-// These would be convenient since the methods work like `each`
-
-#[allow(missing_doc)]
-#[deriving(Clone)]
-pub struct TreeMap<K, V> {
-    priv root: Option<~TreeNode<K, V>>,
-    priv length: uint
-}
-
-impl<K: Eq + TotalOrd, V: Eq> Eq for TreeMap<K, V> {
-    fn eq(&self, other: &TreeMap<K, V>) -> bool {
-        self.len() == other.len() &&
-            self.iter().zip(other.iter()).all(|(a, b)| a == b)
-    }
-}
-
-// Lexicographical comparison
-fn lt<K: Ord + TotalOrd, V: Ord>(a: &TreeMap<K, V>,
-                                 b: &TreeMap<K, V>) -> bool {
-    // the Zip iterator is as long as the shortest of a and b.
-    for ((key_a, value_a), (key_b, value_b)) in a.iter().zip(b.iter()) {
-        if *key_a < *key_b { return true; }
-        if *key_a > *key_b { return false; }
-        if *value_a < *value_b { return true; }
-        if *value_a > *value_b { return false; }
-    }
-
-    a.len() < b.len()
-}
-
-impl<K: Ord + TotalOrd, V: Ord> Ord for TreeMap<K, V> {
-    #[inline]
-    fn lt(&self, other: &TreeMap<K, V>) -> bool { lt(self, other) }
-    #[inline]
-    fn le(&self, other: &TreeMap<K, V>) -> bool { !lt(other, self) }
-    #[inline]
-    fn ge(&self, other: &TreeMap<K, V>) -> bool { !lt(self, other) }
-    #[inline]
-    fn gt(&self, other: &TreeMap<K, V>) -> bool { lt(other, self) }
-}
-
-impl<K: TotalOrd, V> Container for TreeMap<K, V> {
-    /// Return the number of elements in the map
-    fn len(&self) -> uint { self.length }
-
-    /// Return true if the map contains no elements
-    fn is_empty(&self) -> bool { self.root.is_none() }
-}
-
-impl<K: TotalOrd, V> Mutable for TreeMap<K, V> {
-    /// Clear the map, removing all key-value pairs.
-    fn clear(&mut self) {
-        self.root = None;
-        self.length = 0
-    }
-}
-
-impl<K: TotalOrd, V> Map<K, V> for TreeMap<K, V> {
-    /// Return a reference to the value corresponding to the key
-    fn find<'a>(&'a self, key: &K) -> Option<&'a V> {
-        let mut current: &'a Option<~TreeNode<K, V>> = &self.root;
-        loop {
-            match *current {
-              Some(ref r) => {
-                match key.cmp(&r.key) {
-                  Less => current = &r.left,
-                  Greater => current = &r.right,
-                  Equal => return Some(&r.value)
-                }
-              }
-              None => return None
-            }
-        }
-    }
-}
-
-impl<K: TotalOrd, V> MutableMap<K, V> for TreeMap<K, V> {
-    /// Return a mutable reference to the value corresponding to the key
-    #[inline]
-    fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V> {
-        find_mut(&mut self.root, key)
-    }
-
-    /// Insert a key-value pair from the map. If the key already had a value
-    /// present in the map, that value is returned. Otherwise None is returned.
-    fn swap(&mut self, key: K, value: V) -> Option<V> {
-        let ret = insert(&mut self.root, key, value);
-        if ret.is_none() { self.length += 1 }
-        ret
-    }
-
-    /// Removes a key from the map, returning the value at the key if the key
-    /// was previously in the map.
-    fn pop(&mut self, key: &K) -> Option<V> {
-        let ret = remove(&mut self.root, key);
-        if ret.is_some() { self.length -= 1 }
-        ret
-    }
-}
-
-impl<K: TotalOrd, V> TreeMap<K, V> {
-    /// Create an empty TreeMap
-    pub fn new() -> TreeMap<K, V> { TreeMap{root: None, length: 0} }
-
-    /// Get a lazy iterator over the key-value pairs in the map.
-    /// Requires that it be frozen (immutable).
-    pub fn iter<'a>(&'a self) -> Entries<'a, K, V> {
-        Entries {
-            stack: ~[],
-            node: deref(&self.root),
-            remaining_min: self.length,
-            remaining_max: self.length
-        }
-    }
-
-    /// Get a lazy reverse iterator over the key-value pairs in the map.
-    /// Requires that it be frozen (immutable).
-    pub fn rev_iter<'a>(&'a self) -> RevEntries<'a, K, V> {
-        RevEntries{iter: self.iter()}
-    }
-
-    /// Get a lazy forward iterator over the key-value pairs in the
-    /// map, with the values being mutable.
-    pub fn mut_iter<'a>(&'a mut self) -> MutEntries<'a, K, V> {
-        MutEntries {
-            stack: ~[],
-            node: mut_deref(&mut self.root),
-            remaining_min: self.length,
-            remaining_max: self.length
-        }
-    }
-    /// Get a lazy reverse iterator over the key-value pairs in the
-    /// map, with the values being mutable.
-    pub fn mut_rev_iter<'a>(&'a mut self) -> RevMutEntries<'a, K, V> {
-        RevMutEntries{iter: self.mut_iter()}
-    }
-
-
-    /// Get a lazy iterator that consumes the treemap.
-    pub fn move_iter(self) -> MoveEntries<K, V> {
-        let TreeMap { root: root, length: length } = self;
-        let stk = match root {
-            None => ~[],
-            Some(~tn) => ~[tn]
-        };
-        MoveEntries {
-            stack: stk,
-            remaining: length
-        }
-    }
-}
-
-// range iterators.
-
-macro_rules! bound_setup {
-    // initialiser of the iterator to manipulate
-    ($iter:expr,
-     // whether we are looking for the lower or upper bound.
-     $is_lower_bound:expr) => {
-        {
-            let mut iter = $iter;
-            loop {
-                if !iter.node.is_null() {
-                    let node_k = unsafe {&(*iter.node).key};
-                    match k.cmp(node_k) {
-                        Less => iter.traverse_left(),
-                        Greater => iter.traverse_right(),
-                        Equal => {
-                            if $is_lower_bound {
-                                iter.traverse_complete();
-                                return iter;
-                            } else {
-                                iter.traverse_right()
-                            }
-                        }
-                    }
-                } else {
-                    iter.traverse_complete();
-                    return iter;
-                }
-            }
-        }
-    }
-}
-
-
-impl<K: TotalOrd, V> TreeMap<K, V> {
-    /// Get a lazy iterator that should be initialized using
-    /// `traverse_left`/`traverse_right`/`traverse_complete`.
-    fn iter_for_traversal<'a>(&'a self) -> Entries<'a, K, V> {
-        Entries {
-            stack: ~[],
-            node: deref(&self.root),
-            remaining_min: 0,
-            remaining_max: self.length
-        }
-    }
-
-    /// Return a lazy iterator to the first key-value pair whose key is not less than `k`
-    /// If all keys in map are less than `k` an empty iterator is returned.
-    pub fn lower_bound<'a>(&'a self, k: &K) -> Entries<'a, K, V> {
-        bound_setup!(self.iter_for_traversal(), true)
-    }
-
-    /// Return a lazy iterator to the first key-value pair whose key is greater than `k`
-    /// If all keys in map are not greater than `k` an empty iterator is returned.
-    pub fn upper_bound<'a>(&'a self, k: &K) -> Entries<'a, K, V> {
-        bound_setup!(self.iter_for_traversal(), false)
-    }
-
-    /// Get a lazy iterator that should be initialized using
-    /// `traverse_left`/`traverse_right`/`traverse_complete`.
-    fn mut_iter_for_traversal<'a>(&'a mut self) -> MutEntries<'a, K, V> {
-        MutEntries {
-            stack: ~[],
-            node: mut_deref(&mut self.root),
-            remaining_min: 0,
-            remaining_max: self.length
-        }
-    }
-
-    /// Return a lazy value iterator to the first key-value pair (with
-    /// the value being mutable) whose key is not less than `k`.
-    ///
-    /// If all keys in map are less than `k` an empty iterator is
-    /// returned.
-    pub fn mut_lower_bound<'a>(&'a mut self, k: &K) -> MutEntries<'a, K, V> {
-        bound_setup!(self.mut_iter_for_traversal(), true)
-    }
-
-    /// Return a lazy iterator to the first key-value pair (with the
-    /// value being mutable) whose key is greater than `k`.
-    ///
-    /// If all keys in map are not greater than `k` an empty iterator
-    /// is returned.
-    pub fn mut_upper_bound<'a>(&'a mut self, k: &K) -> MutEntries<'a, K, V> {
-        bound_setup!(self.mut_iter_for_traversal(), false)
-    }
-}
-
-/// Lazy forward iterator over a map
-pub struct Entries<'a, K, V> {
-    priv stack: ~[&'a TreeNode<K, V>],
-    // See the comment on MutEntries; this is just to allow
-    // code-sharing (for this immutable-values iterator it *could* very
-    // well be Option<&'a TreeNode<K,V>>).
-    priv node: *TreeNode<K, V>,
-    priv remaining_min: uint,
-    priv remaining_max: uint
-}
-
-/// Lazy backward iterator over a map
-pub struct RevEntries<'a, K, V> {
-    priv iter: Entries<'a, K, V>,
-}
-
-/// Lazy forward iterator over a map that allows for the mutation of
-/// the values.
-pub struct MutEntries<'a, K, V> {
-    priv stack: ~[&'a mut TreeNode<K, V>],
-    // Unfortunately, we require some unsafe-ness to get around the
-    // fact that we would be storing a reference *into* one of the
-    // nodes in the stack.
-    //
-    // As far as the compiler knows, this would let us invalidate the
-    // reference by assigning a new value to this node's position in
-    // its parent, which would cause this current one to be
-    // deallocated so this reference would be invalid. (i.e. the
-    // compilers complaints are 100% correct.)
-    //
-    // However, as far as you humans reading this code know (or are
-    // about to know, if you haven't read far enough down yet), we are
-    // only reading from the TreeNode.{left,right} fields. the only
-    // thing that is ever mutated is the .value field (although any
-    // actual mutation that happens is done externally, by the
-    // iterator consumer). So, don't be so concerned, rustc, we've got
-    // it under control.
-    //
-    // (This field can legitimately be null.)
-    priv node: *mut TreeNode<K, V>,
-    priv remaining_min: uint,
-    priv remaining_max: uint
-}
-
-/// Lazy backward iterator over a map
-pub struct RevMutEntries<'a, K, V> {
-    priv iter: MutEntries<'a, K, V>,
-}
-
-
-// FIXME #5846 we want to be able to choose between &x and &mut x
-// (with many different `x`) below, so we need to optionally pass mut
-// as a tt, but the only thing we can do with a `tt` is pass them to
-// other macros, so this takes the `& <mutability> <operand>` token
-// sequence and forces their evalutation as an expression.
-macro_rules! addr { ($e:expr) => { $e }}
-// putting an optional mut into type signatures
-macro_rules! item { ($i:item) => { $i }}
-
-macro_rules! define_iterator {
-    ($name:ident,
-     $rev_name:ident,
-
-     // the function to go from &m Option<~TreeNode> to *m TreeNode
-     deref = $deref:ident,
-
-     // see comment on `addr!`, this is just an optional `mut`, but
-     // there's no support for 0-or-1 repeats.
-     addr_mut = $($addr_mut:tt)*
-     ) => {
-        // private methods on the forward iterator (item!() for the
-        // addr_mut in the next_ return value)
-        item!(impl<'a, K, V> $name<'a, K, V> {
-            #[inline(always)]
-            fn next_(&mut self, forward: bool) -> Option<(&'a K, &'a $($addr_mut)* V)> {
-                while !self.stack.is_empty() || !self.node.is_null() {
-                    if !self.node.is_null() {
-                        let node = unsafe {addr!(& $($addr_mut)* *self.node)};
-                        {
-                            let next_node = if forward {
-                                addr!(& $($addr_mut)* node.left)
-                            } else {
-                                addr!(& $($addr_mut)* node.right)
-                            };
-                            self.node = $deref(next_node);
-                        }
-                        self.stack.push(node);
-                    } else {
-                        let node = self.stack.pop().unwrap();
-                        let next_node = if forward {
-                            addr!(& $($addr_mut)* node.right)
-                        } else {
-                            addr!(& $($addr_mut)* node.left)
-                        };
-                        self.node = $deref(next_node);
-                        self.remaining_max -= 1;
-                        if self.remaining_min > 0 {
-                            self.remaining_min -= 1;
-                        }
-                        return Some((&node.key, addr!(& $($addr_mut)* node.value)));
-                    }
-                }
-                None
-            }
-
-            /// traverse_left, traverse_right and traverse_complete are
-            /// used to initialize Entries/MutEntries
-            /// pointing to element inside tree structure.
-            ///
-            /// They should be used in following manner:
-            ///   - create iterator using TreeMap::[mut_]iter_for_traversal
-            ///   - find required node using `traverse_left`/`traverse_right`
-            ///     (current node is `Entries::node` field)
-            ///   - complete initialization with `traverse_complete`
-            ///
-            /// After this, iteration will start from `self.node`.  If
-            /// `self.node` is None iteration will start from last
-            /// node from which we traversed left.
-            #[inline]
-            fn traverse_left(&mut self) {
-                let node = unsafe {addr!(& $($addr_mut)* *self.node)};
-                self.node = $deref(addr!(& $($addr_mut)* node.left));
-                self.stack.push(node);
-            }
-
-            #[inline]
-            fn traverse_right(&mut self) {
-                let node = unsafe {addr!(& $($addr_mut)* *self.node)};
-                self.node = $deref(addr!(& $($addr_mut)* node.right));
-            }
-
-            #[inline]
-            fn traverse_complete(&mut self) {
-                if !self.node.is_null() {
-                    unsafe {
-                        self.stack.push(addr!(& $($addr_mut)* *self.node));
-                    }
-                    self.node = ptr::RawPtr::null();
-                }
-            }
-        })
-
-        // the forward Iterator impl.
-        item!(impl<'a, K, V> Iterator<(&'a K, &'a $($addr_mut)* V)> for $name<'a, K, V> {
-            /// Advance the iterator to the next node (in order) and return a
-            /// tuple with a reference to the key and value. If there are no
-            /// more nodes, return `None`.
-            fn next(&mut self) -> Option<(&'a K, &'a $($addr_mut)* V)> {
-                self.next_(true)
-            }
-
-            #[inline]
-            fn size_hint(&self) -> (uint, Option<uint>) {
-                (self.remaining_min, Some(self.remaining_max))
-            }
-        })
-
-        // the reverse Iterator impl.
-        item!(impl<'a, K, V> Iterator<(&'a K, &'a $($addr_mut)* V)> for $rev_name<'a, K, V> {
-            fn next(&mut self) -> Option<(&'a K, &'a $($addr_mut)* V)> {
-                self.iter.next_(false)
-            }
-
-            #[inline]
-            fn size_hint(&self) -> (uint, Option<uint>) {
-                self.iter.size_hint()
-            }
-        })
-    }
-} // end of define_iterator
-
-define_iterator! {
-    Entries,
-    RevEntries,
-    deref = deref,
-
-    // immutable, so no mut
-    addr_mut =
-}
-define_iterator! {
-    MutEntries,
-    RevMutEntries,
-    deref = mut_deref,
-
-    addr_mut = mut
-}
-
-fn deref<'a, K, V>(node: &'a Option<~TreeNode<K, V>>) -> *TreeNode<K, V> {
-    match *node {
-        Some(ref n) => {
-            let n: &TreeNode<K, V> = *n;
-            n as *TreeNode<K, V>
-        }
-        None => ptr::null()
-    }
-}
-
-fn mut_deref<K, V>(x: &mut Option<~TreeNode<K, V>>) -> *mut TreeNode<K, V> {
-    match *x {
-        Some(ref mut n) => {
-            let n: &mut TreeNode<K, V> = *n;
-            n as *mut TreeNode<K, V>
-        }
-        None => ptr::mut_null()
-    }
-}
-
-
-
-/// Lazy forward iterator over a map that consumes the map while iterating
-pub struct MoveEntries<K, V> {
-    priv stack: ~[TreeNode<K, V>],
-    priv remaining: uint
-}
-
-impl<K, V> Iterator<(K, V)> for MoveEntries<K,V> {
-    #[inline]
-    fn next(&mut self) -> Option<(K, V)> {
-        while !self.stack.is_empty() {
-            let TreeNode {
-                key: key,
-                value: value,
-                left: left,
-                right: right,
-                level: level
-            } = self.stack.pop().unwrap();
-
-            match left {
-                Some(~left) => {
-                    let n = TreeNode {
-                        key: key,
-                        value: value,
-                        left: None,
-                        right: right,
-                        level: level
-                    };
-                    self.stack.push(n);
-                    self.stack.push(left);
-                }
-                None => {
-                    match right {
-                        Some(~right) => self.stack.push(right),
-                        None => ()
-                    }
-                    self.remaining -= 1;
-                    return Some((key, value))
-                }
-            }
-        }
-        None
-    }
-
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        (self.remaining, Some(self.remaining))
-    }
-
-}
-
-impl<'a, T> Iterator<&'a T> for SetItems<'a, T> {
-    /// Advance the iterator to the next node (in order). If there are no more nodes, return `None`.
-    #[inline]
-    fn next(&mut self) -> Option<&'a T> {
-        self.iter.next().map(|(value, _)| value)
-    }
-}
-
-impl<'a, T> Iterator<&'a T> for RevSetItems<'a, T> {
-    /// Advance the iterator to the next node (in order). If there are no more nodes, return `None`.
-    #[inline]
-    fn next(&mut self) -> Option<&'a T> {
-        self.iter.next().map(|(value, _)| value)
-    }
-}
-
-/// A implementation of the `Set` trait on top of the `TreeMap` container. The
-/// only requirement is that the type of the elements contained ascribes to the
-/// `TotalOrd` trait.
-#[deriving(Clone)]
-pub struct TreeSet<T> {
-    priv map: TreeMap<T, ()>
-}
-
-impl<T: Eq + TotalOrd> Eq for TreeSet<T> {
-    #[inline]
-    fn eq(&self, other: &TreeSet<T>) -> bool { self.map == other.map }
-    #[inline]
-    fn ne(&self, other: &TreeSet<T>) -> bool { self.map != other.map }
-}
-
-impl<T: Ord + TotalOrd> Ord for TreeSet<T> {
-    #[inline]
-    fn lt(&self, other: &TreeSet<T>) -> bool { self.map < other.map }
-    #[inline]
-    fn le(&self, other: &TreeSet<T>) -> bool { self.map <= other.map }
-    #[inline]
-    fn ge(&self, other: &TreeSet<T>) -> bool { self.map >= other.map }
-    #[inline]
-    fn gt(&self, other: &TreeSet<T>) -> bool { self.map > other.map }
-}
-
-impl<T: TotalOrd> Container for TreeSet<T> {
-    /// Return the number of elements in the set
-    #[inline]
-    fn len(&self) -> uint { self.map.len() }
-
-    /// Return true if the set contains no elements
-    #[inline]
-    fn is_empty(&self) -> bool { self.map.is_empty() }
-}
-
-impl<T: TotalOrd> Mutable for TreeSet<T> {
-    /// Clear the set, removing all values.
-    #[inline]
-    fn clear(&mut self) { self.map.clear() }
-}
-
-impl<T: TotalOrd> Set<T> for TreeSet<T> {
-    /// Return true if the set contains a value
-    #[inline]
-    fn contains(&self, value: &T) -> bool {
-        self.map.contains_key(value)
-    }
-
-    /// Return true if the set has no elements in common with `other`.
-    /// This is equivalent to checking for an empty intersection.
-    fn is_disjoint(&self, other: &TreeSet<T>) -> bool {
-        self.intersection(other).next().is_none()
-    }
-
-    /// Return true if the set is a subset of another
-    #[inline]
-    fn is_subset(&self, other: &TreeSet<T>) -> bool {
-        other.is_superset(self)
-    }
-
-    /// Return true if the set is a superset of another
-    fn is_superset(&self, other: &TreeSet<T>) -> bool {
-        let mut x = self.iter();
-        let mut y = other.iter();
-        let mut a = x.next();
-        let mut b = y.next();
-        while b.is_some() {
-            if a.is_none() {
-                return false
-            }
-
-            let a1 = a.unwrap();
-            let b1 = b.unwrap();
-
-            match a1.cmp(b1) {
-              Less => (),
-              Greater => return false,
-              Equal => b = y.next(),
-            }
-
-            a = x.next();
-        }
-        true
-    }
-}
-
-impl<T: TotalOrd> MutableSet<T> for TreeSet<T> {
-    /// Add a value to the set. Return true if the value was not already
-    /// present in the set.
-    #[inline]
-    fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
-
-    /// Remove a value from the set. Return true if the value was
-    /// present in the set.
-    #[inline]
-    fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
-}
-
-impl<T: TotalOrd> TreeSet<T> {
-    /// Create an empty TreeSet
-    #[inline]
-    pub fn new() -> TreeSet<T> { TreeSet{map: TreeMap::new()} }
-
-    /// Get a lazy iterator over the values in the set.
-    /// Requires that it be frozen (immutable).
-    #[inline]
-    pub fn iter<'a>(&'a self) -> SetItems<'a, T> {
-        SetItems{iter: self.map.iter()}
-    }
-
-    /// Get a lazy iterator over the values in the set.
-    /// Requires that it be frozen (immutable).
-    #[inline]
-    pub fn rev_iter<'a>(&'a self) -> RevSetItems<'a, T> {
-        RevSetItems{iter: self.map.rev_iter()}
-    }
-
-    /// Get a lazy iterator pointing to the first value not less than `v` (greater or equal).
-    /// If all elements in the set are less than `v` empty iterator is returned.
-    #[inline]
-    pub fn lower_bound<'a>(&'a self, v: &T) -> SetItems<'a, T> {
-        SetItems{iter: self.map.lower_bound(v)}
-    }
-
-    /// Get a lazy iterator pointing to the first value greater than `v`.
-    /// If all elements in the set are not greater than `v` empty iterator is returned.
-    #[inline]
-    pub fn upper_bound<'a>(&'a self, v: &T) -> SetItems<'a, T> {
-        SetItems{iter: self.map.upper_bound(v)}
-    }
-
-    /// Visit the values (in-order) representing the difference
-    pub fn difference<'a>(&'a self, other: &'a TreeSet<T>) -> DifferenceItems<'a, T> {
-        DifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()}
-    }
-
-    /// Visit the values (in-order) representing the symmetric difference
-    pub fn symmetric_difference<'a>(&'a self, other: &'a TreeSet<T>)
-        -> SymDifferenceItems<'a, T> {
-        SymDifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()}
-    }
-
-    /// Visit the values (in-order) representing the intersection
-    pub fn intersection<'a>(&'a self, other: &'a TreeSet<T>)
-        -> IntersectionItems<'a, T> {
-        IntersectionItems{a: self.iter().peekable(), b: other.iter().peekable()}
-    }
-
-    /// Visit the values (in-order) representing the union
-    pub fn union<'a>(&'a self, other: &'a TreeSet<T>) -> UnionItems<'a, T> {
-        UnionItems{a: self.iter().peekable(), b: other.iter().peekable()}
-    }
-}
-
-/// Lazy forward iterator over a set
-pub struct SetItems<'a, T> {
-    priv iter: Entries<'a, T, ()>
-}
-
-/// Lazy backward iterator over a set
-pub struct RevSetItems<'a, T> {
-    priv iter: RevEntries<'a, T, ()>
-}
-
-/// Lazy iterator producing elements in the set difference (in-order)
-pub struct DifferenceItems<'a, T> {
-    priv a: Peekable<&'a T, SetItems<'a, T>>,
-    priv b: Peekable<&'a T, SetItems<'a, T>>,
-}
-
-/// Lazy iterator producing elements in the set symmetric difference (in-order)
-pub struct SymDifferenceItems<'a, T> {
-    priv a: Peekable<&'a T, SetItems<'a, T>>,
-    priv b: Peekable<&'a T, SetItems<'a, T>>,
-}
-
-/// Lazy iterator producing elements in the set intersection (in-order)
-pub struct IntersectionItems<'a, T> {
-    priv a: Peekable<&'a T, SetItems<'a, T>>,
-    priv b: Peekable<&'a T, SetItems<'a, T>>,
-}
-
-/// Lazy iterator producing elements in the set intersection (in-order)
-pub struct UnionItems<'a, T> {
-    priv a: Peekable<&'a T, SetItems<'a, T>>,
-    priv b: Peekable<&'a T, SetItems<'a, T>>,
-}
-
-/// Compare `x` and `y`, but return `short` if x is None and `long` if y is None
-fn cmp_opt<T: TotalOrd>(x: Option<&T>, y: Option<&T>,
-                        short: Ordering, long: Ordering) -> Ordering {
-    match (x, y) {
-        (None    , _       ) => short,
-        (_       , None    ) => long,
-        (Some(x1), Some(y1)) => x1.cmp(y1),
-    }
-}
-
-impl<'a, T: TotalOrd> Iterator<&'a T> for DifferenceItems<'a, T> {
-    fn next(&mut self) -> Option<&'a T> {
-        loop {
-            match cmp_opt(self.a.peek(), self.b.peek(), Less, Less) {
-                Less    => return self.a.next(),
-                Equal   => { self.a.next(); self.b.next(); }
-                Greater => { self.b.next(); }
-            }
-        }
-    }
-}
-
-impl<'a, T: TotalOrd> Iterator<&'a T> for SymDifferenceItems<'a, T> {
-    fn next(&mut self) -> Option<&'a T> {
-        loop {
-            match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
-                Less    => return self.a.next(),
-                Equal   => { self.a.next(); self.b.next(); }
-                Greater => return self.b.next(),
-            }
-        }
-    }
-}
-
-impl<'a, T: TotalOrd> Iterator<&'a T> for IntersectionItems<'a, T> {
-    fn next(&mut self) -> Option<&'a T> {
-        loop {
-            let o_cmp = match (self.a.peek(), self.b.peek()) {
-                (None    , _       ) => None,
-                (_       , None    ) => None,
-                (Some(a1), Some(b1)) => Some(a1.cmp(b1)),
-            };
-            match o_cmp {
-                None          => return None,
-                Some(Less)    => { self.a.next(); }
-                Some(Equal)   => { self.b.next(); return self.a.next() }
-                Some(Greater) => { self.b.next(); }
-            }
-        }
-    }
-}
-
-impl<'a, T: TotalOrd> Iterator<&'a T> for UnionItems<'a, T> {
-    fn next(&mut self) -> Option<&'a T> {
-        loop {
-            match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
-                Less    => return self.a.next(),
-                Equal   => { self.b.next(); return self.a.next() }
-                Greater => return self.b.next(),
-            }
-        }
-    }
-}
-
-
-// Nodes keep track of their level in the tree, starting at 1 in the
-// leaves and with a red child sharing the level of the parent.
-#[deriving(Clone)]
-struct TreeNode<K, V> {
-    key: K,
-    value: V,
-    left: Option<~TreeNode<K, V>>,
-    right: Option<~TreeNode<K, V>>,
-    level: uint
-}
-
-impl<K: TotalOrd, V> TreeNode<K, V> {
-    /// Creates a new tree node.
-    #[inline]
-    pub fn new(key: K, value: V) -> TreeNode<K, V> {
-        TreeNode{key: key, value: value, left: None, right: None, level: 1}
-    }
-}
-
-// Remove left horizontal link by rotating right
-fn skew<K: TotalOrd, V>(node: &mut ~TreeNode<K, V>) {
-    if node.left.as_ref().map_or(false, |x| x.level == node.level) {
-        let mut save = node.left.take_unwrap();
-        swap(&mut node.left, &mut save.right); // save.right now None
-        swap(node, &mut save);
-        node.right = Some(save);
-    }
-}
-
-// Remove dual horizontal link by rotating left and increasing level of
-// the parent
-fn split<K: TotalOrd, V>(node: &mut ~TreeNode<K, V>) {
-    if node.right.as_ref().map_or(false,
-      |x| x.right.as_ref().map_or(false, |y| y.level == node.level)) {
-        let mut save = node.right.take_unwrap();
-        swap(&mut node.right, &mut save.left); // save.left now None
-        save.level += 1;
-        swap(node, &mut save);
-        node.left = Some(save);
-    }
-}
-
-fn find_mut<'r, K: TotalOrd, V>(node: &'r mut Option<~TreeNode<K, V>>,
-                                key: &K)
-                             -> Option<&'r mut V> {
-    match *node {
-      Some(ref mut x) => {
-        match key.cmp(&x.key) {
-          Less => find_mut(&mut x.left, key),
-          Greater => find_mut(&mut x.right, key),
-          Equal => Some(&mut x.value),
-        }
-      }
-      None => None
-    }
-}
-
-fn insert<K: TotalOrd, V>(node: &mut Option<~TreeNode<K, V>>,
-                          key: K, value: V) -> Option<V> {
-    match *node {
-      Some(ref mut save) => {
-        match key.cmp(&save.key) {
-          Less => {
-            let inserted = insert(&mut save.left, key, value);
-            skew(save);
-            split(save);
-            inserted
-          }
-          Greater => {
-            let inserted = insert(&mut save.right, key, value);
-            skew(save);
-            split(save);
-            inserted
-          }
-          Equal => {
-            save.key = key;
-            Some(replace(&mut save.value, value))
-          }
-        }
-      }
-      None => {
-       *node = Some(~TreeNode::new(key, value));
-        None
-      }
-    }
-}
-
-fn remove<K: TotalOrd, V>(node: &mut Option<~TreeNode<K, V>>,
-                          key: &K) -> Option<V> {
-    fn heir_swap<K: TotalOrd, V>(node: &mut ~TreeNode<K, V>,
-                                 child: &mut Option<~TreeNode<K, V>>) {
-        // *could* be done without recursion, but it won't borrow check
-        for x in child.mut_iter() {
-            if x.right.is_some() {
-                heir_swap(node, &mut x.right);
-            } else {
-                swap(&mut node.key, &mut x.key);
-                swap(&mut node.value, &mut x.value);
-            }
-        }
-    }
-
-    match *node {
-      None => {
-        return None; // bottom of tree
-      }
-      Some(ref mut save) => {
-        let (ret, rebalance) = match key.cmp(&save.key) {
-          Less => (remove(&mut save.left, key), true),
-          Greater => (remove(&mut save.right, key), true),
-          Equal => {
-            if save.left.is_some() {
-                if save.right.is_some() {
-                    let mut left = save.left.take_unwrap();
-                    if left.right.is_some() {
-                        heir_swap(save, &mut left.right);
-                    } else {
-                        swap(&mut save.key, &mut left.key);
-                        swap(&mut save.value, &mut left.value);
-                    }
-                    save.left = Some(left);
-                    (remove(&mut save.left, key), true)
-                } else {
-                    let new = save.left.take_unwrap();
-                    let ~TreeNode{value, ..} = replace(save, new);
-                    *save = save.left.take_unwrap();
-                    (Some(value), true)
-                }
-            } else if save.right.is_some() {
-                let new = save.right.take_unwrap();
-                let ~TreeNode{value, ..} = replace(save, new);
-                (Some(value), true)
-            } else {
-                (None, false)
-            }
-          }
-        };
-
-        if rebalance {
-            let left_level = save.left.as_ref().map_or(0, |x| x.level);
-            let right_level = save.right.as_ref().map_or(0, |x| x.level);
-
-            // re-balance, if necessary
-            if left_level < save.level - 1 || right_level < save.level - 1 {
-                save.level -= 1;
-
-                if right_level > save.level {
-                    for x in save.right.mut_iter() { x.level = save.level }
-                }
-
-                skew(save);
-
-                for right in save.right.mut_iter() {
-                    skew(right);
-                    for x in right.right.mut_iter() { skew(x) }
-                }
-
-                split(save);
-                for x in save.right.mut_iter() { split(x) }
-            }
-
-            return ret;
-        }
-      }
-    }
-    return match node.take() {
-        Some(~TreeNode{value, ..}) => Some(value), None => fail!()
-    };
-}
-
-impl<K: TotalOrd, V> FromIterator<(K, V)> for TreeMap<K, V> {
-    fn from_iterator<T: Iterator<(K, V)>>(iter: &mut T) -> TreeMap<K, V> {
-        let mut map = TreeMap::new();
-        map.extend(iter);
-        map
-    }
-}
-
-impl<K: TotalOrd, V> Extendable<(K, V)> for TreeMap<K, V> {
-    #[inline]
-    fn extend<T: Iterator<(K, V)>>(&mut self, iter: &mut T) {
-        for (k, v) in *iter {
-            self.insert(k, v);
-        }
-    }
-}
-
-impl<T: TotalOrd> FromIterator<T> for TreeSet<T> {
-    fn from_iterator<Iter: Iterator<T>>(iter: &mut Iter) -> TreeSet<T> {
-        let mut set = TreeSet::new();
-        set.extend(iter);
-        set
-    }
-}
-
-impl<T: TotalOrd> Extendable<T> for TreeSet<T> {
-    #[inline]
-    fn extend<Iter: Iterator<T>>(&mut self, iter: &mut Iter) {
-        for elem in *iter {
-            self.insert(elem);
-        }
-    }
-}
-
-impl<
-    E: Encoder,
-    K: Encodable<E> + Eq + TotalOrd,
-    V: Encodable<E> + Eq
-> Encodable<E> for TreeMap<K, V> {
-    fn encode(&self, e: &mut E) {
-        e.emit_map(self.len(), |e| {
-            let mut i = 0;
-            for (key, val) in self.iter() {
-                e.emit_map_elt_key(i, |e| key.encode(e));
-                e.emit_map_elt_val(i, |e| val.encode(e));
-                i += 1;
-            }
-        })
-    }
-}
-
-impl<
-    D: Decoder,
-    K: Decodable<D> + Eq + TotalOrd,
-    V: Decodable<D> + Eq
-> Decodable<D> for TreeMap<K, V> {
-    fn decode(d: &mut D) -> TreeMap<K, V> {
-        d.read_map(|d, len| {
-            let mut map = TreeMap::new();
-            for i in range(0u, len) {
-                let key = d.read_map_elt_key(i, |d| Decodable::decode(d));
-                let val = d.read_map_elt_val(i, |d| Decodable::decode(d));
-                map.insert(key, val);
-            }
-            map
-        })
-    }
-}
-
-impl<
-    S: Encoder,
-    T: Encodable<S> + Eq + TotalOrd
-> Encodable<S> for TreeSet<T> {
-    fn encode(&self, s: &mut S) {
-        s.emit_seq(self.len(), |s| {
-            let mut i = 0;
-            for e in self.iter() {
-                s.emit_seq_elt(i, |s| e.encode(s));
-                i += 1;
-            }
-        })
-    }
-}
-
-impl<
-    D: Decoder,
-    T: Decodable<D> + Eq + TotalOrd
-> Decodable<D> for TreeSet<T> {
-    fn decode(d: &mut D) -> TreeSet<T> {
-        d.read_seq(|d, len| {
-            let mut set = TreeSet::new();
-            for i in range(0u, len) {
-                set.insert(d.read_seq_elt(i, |d| Decodable::decode(d)));
-            }
-            set
-        })
-    }
-}
-
-#[cfg(test)]
-mod test_treemap {
-
-    use super::{TreeMap, TreeNode};
-
-    use std::rand::Rng;
-    use std::rand;
-
-    #[test]
-    fn find_empty() {
-        let m: TreeMap<int,int> = TreeMap::new();
-        assert!(m.find(&5) == None);
-    }
-
-    #[test]
-    fn find_not_found() {
-        let mut m = TreeMap::new();
-        assert!(m.insert(1, 2));
-        assert!(m.insert(5, 3));
-        assert!(m.insert(9, 3));
-        assert_eq!(m.find(&2), None);
-    }
-
-    #[test]
-    fn test_find_mut() {
-        let mut m = TreeMap::new();
-        assert!(m.insert(1, 12));
-        assert!(m.insert(2, 8));
-        assert!(m.insert(5, 14));
-        let new = 100;
-        match m.find_mut(&5) {
-          None => fail!(), Some(x) => *x = new
-        }
-        assert_eq!(m.find(&5), Some(&new));
-    }
-
-    #[test]
-    fn insert_replace() {
-        let mut m = TreeMap::new();
-        assert!(m.insert(5, 2));
-        assert!(m.insert(2, 9));
-        assert!(!m.insert(2, 11));
-        assert_eq!(m.find(&2).unwrap(), &11);
-    }
-
-    #[test]
-    fn test_clear() {
-        let mut m = TreeMap::new();
-        m.clear();
-        assert!(m.insert(5, 11));
-        assert!(m.insert(12, -3));
-        assert!(m.insert(19, 2));
-        m.clear();
-        assert!(m.find(&5).is_none());
-        assert!(m.find(&12).is_none());
-        assert!(m.find(&19).is_none());
-        assert!(m.is_empty());
-    }
-
-    #[test]
-    fn u8_map() {
-        let mut m = TreeMap::new();
-
-        let k1 = "foo".as_bytes();
-        let k2 = "bar".as_bytes();
-        let v1 = "baz".as_bytes();
-        let v2 = "foobar".as_bytes();
-
-        m.insert(k1.clone(), v1.clone());
-        m.insert(k2.clone(), v2.clone());
-
-        assert_eq!(m.find(&k2), Some(&v2));
-        assert_eq!(m.find(&k1), Some(&v1));
-    }
-
-    fn check_equal<K: Eq + TotalOrd, V: Eq>(ctrl: &[(K, V)],
-                                            map: &TreeMap<K, V>) {
-        assert_eq!(ctrl.is_empty(), map.is_empty());
-        for x in ctrl.iter() {
-            let &(ref k, ref v) = x;
-            assert!(map.find(k).unwrap() == v)
-        }
-        for (map_k, map_v) in map.iter() {
-            let mut found = false;
-            for x in ctrl.iter() {
-                let &(ref ctrl_k, ref ctrl_v) = x;
-                if *map_k == *ctrl_k {
-                    assert!(*map_v == *ctrl_v);
-                    found = true;
-                    break;
-                }
-            }
-            assert!(found);
-        }
-    }
-
-    fn check_left<K: TotalOrd, V>(node: &Option<~TreeNode<K, V>>,
-                                  parent: &~TreeNode<K, V>) {
-        match *node {
-          Some(ref r) => {
-            assert_eq!(r.key.cmp(&parent.key), Less);
-            assert!(r.level == parent.level - 1); // left is black
-            check_left(&r.left, r);
-            check_right(&r.right, r, false);
-          }
-          None => assert!(parent.level == 1) // parent is leaf
-        }
-    }
-
-    fn check_right<K: TotalOrd, V>(node: &Option<~TreeNode<K, V>>,
-                                   parent: &~TreeNode<K, V>,
-                                   parent_red: bool) {
-        match *node {
-          Some(ref r) => {
-            assert_eq!(r.key.cmp(&parent.key), Greater);
-            let red = r.level == parent.level;
-            if parent_red { assert!(!red) } // no dual horizontal links
-            // Right red or black
-            assert!(red || r.level == parent.level - 1);
-            check_left(&r.left, r);
-            check_right(&r.right, r, red);
-          }
-          None => assert!(parent.level == 1) // parent is leaf
-        }
-    }
-
-    fn check_structure<K: TotalOrd, V>(map: &TreeMap<K, V>) {
-        match map.root {
-          Some(ref r) => {
-            check_left(&r.left, r);
-            check_right(&r.right, r, false);
-          }
-          None => ()
-        }
-    }
-
-    #[test]
-    fn test_rand_int() {
-        let mut map: TreeMap<int,int> = TreeMap::new();
-        let mut ctrl = ~[];
-
-        check_equal(ctrl, &map);
-        assert!(map.find(&5).is_none());
-
-        let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(&[42]);
-
-        for _ in range(0, 3) {
-            for _ in range(0, 90) {
-                let k = rng.gen();
-                let v = rng.gen();
-                if !ctrl.iter().any(|x| x == &(k, v)) {
-                    assert!(map.insert(k, v));
-                    ctrl.push((k, v));
-                    check_structure(&map);
-                    check_equal(ctrl, &map);
-                }
-            }
-
-            for _ in range(0, 30) {
-                let r = rng.gen_range(0, ctrl.len());
-                let (key, _) = ctrl.remove(r).unwrap();
-                assert!(map.remove(&key));
-                check_structure(&map);
-                check_equal(ctrl, &map);
-            }
-        }
-    }
-
-    #[test]
-    fn test_len() {
-        let mut m = TreeMap::new();
-        assert!(m.insert(3, 6));
-        assert_eq!(m.len(), 1);
-        assert!(m.insert(0, 0));
-        assert_eq!(m.len(), 2);
-        assert!(m.insert(4, 8));
-        assert_eq!(m.len(), 3);
-        assert!(m.remove(&3));
-        assert_eq!(m.len(), 2);
-        assert!(!m.remove(&5));
-        assert_eq!(m.len(), 2);
-        assert!(m.insert(2, 4));
-        assert_eq!(m.len(), 3);
-        assert!(m.insert(1, 2));
-        assert_eq!(m.len(), 4);
-    }
-
-    #[test]
-    fn test_iterator() {
-        let mut m = TreeMap::new();
-
-        assert!(m.insert(3, 6));
-        assert!(m.insert(0, 0));
-        assert!(m.insert(4, 8));
-        assert!(m.insert(2, 4));
-        assert!(m.insert(1, 2));
-
-        let mut n = 0;
-        for (k, v) in m.iter() {
-            assert_eq!(*k, n);
-            assert_eq!(*v, n * 2);
-            n += 1;
-        }
-        assert_eq!(n, 5);
-    }
-
-    #[test]
-    fn test_interval_iteration() {
-        let mut m = TreeMap::new();
-        for i in range(1, 100) {
-            assert!(m.insert(i * 2, i * 4));
-        }
-
-        for i in range(1, 198) {
-            let mut lb_it = m.lower_bound(&i);
-            let (&k, &v) = lb_it.next().unwrap();
-            let lb = i + i % 2;
-            assert_eq!(lb, k);
-            assert_eq!(lb * 2, v);
-
-            let mut ub_it = m.upper_bound(&i);
-            let (&k, &v) = ub_it.next().unwrap();
-            let ub = i + 2 - i % 2;
-            assert_eq!(ub, k);
-            assert_eq!(ub * 2, v);
-        }
-        let mut end_it = m.lower_bound(&199);
-        assert_eq!(end_it.next(), None);
-    }
-
-    #[test]
-    fn test_rev_iter() {
-        let mut m = TreeMap::new();
-
-        assert!(m.insert(3, 6));
-        assert!(m.insert(0, 0));
-        assert!(m.insert(4, 8));
-        assert!(m.insert(2, 4));
-        assert!(m.insert(1, 2));
-
-        let mut n = 4;
-        for (k, v) in m.rev_iter() {
-            assert_eq!(*k, n);
-            assert_eq!(*v, n * 2);
-            n -= 1;
-        }
-    }
-
-    #[test]
-    fn test_mut_iter() {
-        let mut m = TreeMap::new();
-        for i in range(0u, 10) {
-            assert!(m.insert(i, 100 * i));
-        }
-
-        for (i, (&k, v)) in m.mut_iter().enumerate() {
-            *v += k * 10 + i; // 000 + 00 + 0, 100 + 10 + 1, ...
-        }
-
-        for (&k, &v) in m.iter() {
-            assert_eq!(v, 111 * k);
-        }
-    }
-    #[test]
-    fn test_mut_rev_iter() {
-        let mut m = TreeMap::new();
-        for i in range(0u, 10) {
-            assert!(m.insert(i, 100 * i));
-        }
-
-        for (i, (&k, v)) in m.mut_rev_iter().enumerate() {
-            *v += k * 10 + (9 - i); // 900 + 90 + (9 - 0), 800 + 80 + (9 - 1), ...
-        }
-
-        for (&k, &v) in m.iter() {
-            assert_eq!(v, 111 * k);
-        }
-    }
-
-    #[test]
-    fn test_mut_interval_iter() {
-        let mut m_lower = TreeMap::new();
-        let mut m_upper = TreeMap::new();
-        for i in range(1, 100) {
-            assert!(m_lower.insert(i * 2, i * 4));
-            assert!(m_upper.insert(i * 2, i * 4));
-        }
-
-        for i in range(1, 199) {
-            let mut lb_it = m_lower.mut_lower_bound(&i);
-            let (&k, v) = lb_it.next().unwrap();
-            let lb = i + i % 2;
-            assert_eq!(lb, k);
-            *v -= k;
-        }
-        for i in range(0, 198) {
-            let mut ub_it = m_upper.mut_upper_bound(&i);
-            let (&k, v) = ub_it.next().unwrap();
-            let ub = i + 2 - i % 2;
-            assert_eq!(ub, k);
-            *v -= k;
-        }
-
-        assert!(m_lower.mut_lower_bound(&199).next().is_none());
-
-        assert!(m_upper.mut_upper_bound(&198).next().is_none());
-
-        assert!(m_lower.iter().all(|(_, &x)| x == 0));
-        assert!(m_upper.iter().all(|(_, &x)| x == 0));
-    }
-
-    #[test]
-    fn test_eq() {
-        let mut a = TreeMap::new();
-        let mut b = TreeMap::new();
-
-        assert!(a == b);
-        assert!(a.insert(0, 5));
-        assert!(a != b);
-        assert!(b.insert(0, 4));
-        assert!(a != b);
-        assert!(a.insert(5, 19));
-        assert!(a != b);
-        assert!(!b.insert(0, 5));
-        assert!(a != b);
-        assert!(b.insert(5, 19));
-        assert!(a == b);
-    }
-
-    #[test]
-    fn test_lt() {
-        let mut a = TreeMap::new();
-        let mut b = TreeMap::new();
-
-        assert!(!(a < b) && !(b < a));
-        assert!(b.insert(0, 5));
-        assert!(a < b);
-        assert!(a.insert(0, 7));
-        assert!(!(a < b) && b < a);
-        assert!(b.insert(-2, 0));
-        assert!(b < a);
-        assert!(a.insert(-5, 2));
-        assert!(a < b);
-        assert!(a.insert(6, 2));
-        assert!(a < b && !(b < a));
-    }
-
-    #[test]
-    fn test_ord() {
-        let mut a = TreeMap::new();
-        let mut b = TreeMap::new();
-
-        assert!(a <= b && a >= b);
-        assert!(a.insert(1, 1));
-        assert!(a > b && a >= b);
-        assert!(b < a && b <= a);
-        assert!(b.insert(2, 2));
-        assert!(b > a && b >= a);
-        assert!(a < b && a <= b);
-    }
-
-    #[test]
-    fn test_lazy_iterator() {
-        let mut m = TreeMap::new();
-        let (x1, y1) = (2, 5);
-        let (x2, y2) = (9, 12);
-        let (x3, y3) = (20, -3);
-        let (x4, y4) = (29, 5);
-        let (x5, y5) = (103, 3);
-
-        assert!(m.insert(x1, y1));
-        assert!(m.insert(x2, y2));
-        assert!(m.insert(x3, y3));
-        assert!(m.insert(x4, y4));
-        assert!(m.insert(x5, y5));
-
-        let m = m;
-        let mut a = m.iter();
-
-        assert_eq!(a.next().unwrap(), (&x1, &y1));
-        assert_eq!(a.next().unwrap(), (&x2, &y2));
-        assert_eq!(a.next().unwrap(), (&x3, &y3));
-        assert_eq!(a.next().unwrap(), (&x4, &y4));
-        assert_eq!(a.next().unwrap(), (&x5, &y5));
-
-        assert!(a.next().is_none());
-
-        let mut b = m.iter();
-
-        let expected = [(&x1, &y1), (&x2, &y2), (&x3, &y3), (&x4, &y4),
-                        (&x5, &y5)];
-        let mut i = 0;
-
-        for x in b {
-            assert_eq!(expected[i], x);
-            i += 1;
-
-            if i == 2 {
-                break
-            }
-        }
-
-        for x in b {
-            assert_eq!(expected[i], x);
-            i += 1;
-        }
-    }
-
-    #[test]
-    fn test_from_iter() {
-        let xs = ~[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
-
-        let map: TreeMap<int, int> = xs.iter().map(|&x| x).collect();
-
-        for &(k, v) in xs.iter() {
-            assert_eq!(map.find(&k), Some(&v));
-        }
-    }
-
-}
-
-#[cfg(test)]
-mod bench {
-
-    use super::*;
-    use test::BenchHarness;
-    use container::bench::*;
-
-    // Find seq
-    #[bench]
-    pub fn insert_rand_100(bh: &mut BenchHarness) {
-        let mut m : TreeMap<uint,uint> = TreeMap::new();
-        insert_rand_n(100, &mut m, bh);
-    }
-
-    #[bench]
-    pub fn insert_rand_10_000(bh: &mut BenchHarness) {
-        let mut m : TreeMap<uint,uint> = TreeMap::new();
-        insert_rand_n(10_000, &mut m, bh);
-    }
-
-    // Insert seq
-    #[bench]
-    pub fn insert_seq_100(bh: &mut BenchHarness) {
-        let mut m : TreeMap<uint,uint> = TreeMap::new();
-        insert_seq_n(100, &mut m, bh);
-    }
-
-    #[bench]
-    pub fn insert_seq_10_000(bh: &mut BenchHarness) {
-        let mut m : TreeMap<uint,uint> = TreeMap::new();
-        insert_seq_n(10_000, &mut m, bh);
-    }
-
-    // Find rand
-    #[bench]
-    pub fn find_rand_100(bh: &mut BenchHarness) {
-        let mut m : TreeMap<uint,uint> = TreeMap::new();
-        find_rand_n(100, &mut m, bh);
-    }
-
-    #[bench]
-    pub fn find_rand_10_000(bh: &mut BenchHarness) {
-        let mut m : TreeMap<uint,uint> = TreeMap::new();
-        find_rand_n(10_000, &mut m, bh);
-    }
-
-    // Find seq
-    #[bench]
-    pub fn find_seq_100(bh: &mut BenchHarness) {
-        let mut m : TreeMap<uint,uint> = TreeMap::new();
-        find_seq_n(100, &mut m, bh);
-    }
-
-    #[bench]
-    pub fn find_seq_10_000(bh: &mut BenchHarness) {
-        let mut m : TreeMap<uint,uint> = TreeMap::new();
-        find_seq_n(10_000, &mut m, bh);
-    }
-}
-
-#[cfg(test)]
-mod test_set {
-
-    use super::*;
-
-    #[test]
-    fn test_clear() {
-        let mut s = TreeSet::new();
-        s.clear();
-        assert!(s.insert(5));
-        assert!(s.insert(12));
-        assert!(s.insert(19));
-        s.clear();
-        assert!(!s.contains(&5));
-        assert!(!s.contains(&12));
-        assert!(!s.contains(&19));
-        assert!(s.is_empty());
-    }
-
-    #[test]
-    fn test_disjoint() {
-        let mut xs = TreeSet::new();
-        let mut ys = TreeSet::new();
-        assert!(xs.is_disjoint(&ys));
-        assert!(ys.is_disjoint(&xs));
-        assert!(xs.insert(5));
-        assert!(ys.insert(11));
-        assert!(xs.is_disjoint(&ys));
-        assert!(ys.is_disjoint(&xs));
-        assert!(xs.insert(7));
-        assert!(xs.insert(19));
-        assert!(xs.insert(4));
-        assert!(ys.insert(2));
-        assert!(ys.insert(-11));
-        assert!(xs.is_disjoint(&ys));
-        assert!(ys.is_disjoint(&xs));
-        assert!(ys.insert(7));
-        assert!(!xs.is_disjoint(&ys));
-        assert!(!ys.is_disjoint(&xs));
-    }
-
-    #[test]
-    fn test_subset_and_superset() {
-        let mut a = TreeSet::new();
-        assert!(a.insert(0));
-        assert!(a.insert(5));
-        assert!(a.insert(11));
-        assert!(a.insert(7));
-
-        let mut b = TreeSet::new();
-        assert!(b.insert(0));
-        assert!(b.insert(7));
-        assert!(b.insert(19));
-        assert!(b.insert(250));
-        assert!(b.insert(11));
-        assert!(b.insert(200));
-
-        assert!(!a.is_subset(&b));
-        assert!(!a.is_superset(&b));
-        assert!(!b.is_subset(&a));
-        assert!(!b.is_superset(&a));
-
-        assert!(b.insert(5));
-
-        assert!(a.is_subset(&b));
-        assert!(!a.is_superset(&b));
-        assert!(!b.is_subset(&a));
-        assert!(b.is_superset(&a));
-    }
-
-    #[test]
-    fn test_iterator() {
-        let mut m = TreeSet::new();
-
-        assert!(m.insert(3));
-        assert!(m.insert(0));
-        assert!(m.insert(4));
-        assert!(m.insert(2));
-        assert!(m.insert(1));
-
-        let mut n = 0;
-        for x in m.iter() {
-            assert_eq!(*x, n);
-            n += 1
-        }
-    }
-
-    #[test]
-    fn test_rev_iter() {
-        let mut m = TreeSet::new();
-
-        assert!(m.insert(3));
-        assert!(m.insert(0));
-        assert!(m.insert(4));
-        assert!(m.insert(2));
-        assert!(m.insert(1));
-
-        let mut n = 4;
-        for x in m.rev_iter() {
-            assert_eq!(*x, n);
-            n -= 1;
-        }
-    }
-
-    #[test]
-    fn test_clone_eq() {
-      let mut m = TreeSet::new();
-
-      m.insert(1);
-      m.insert(2);
-
-      assert!(m.clone() == m);
-    }
-
-    fn check(a: &[int],
-             b: &[int],
-             expected: &[int],
-             f: |&TreeSet<int>, &TreeSet<int>, f: |&int| -> bool| -> bool) {
-        let mut set_a = TreeSet::new();
-        let mut set_b = TreeSet::new();
-
-        for x in a.iter() { assert!(set_a.insert(*x)) }
-        for y in b.iter() { assert!(set_b.insert(*y)) }
-
-        let mut i = 0;
-        f(&set_a, &set_b, |x| {
-            assert_eq!(*x, expected[i]);
-            i += 1;
-            true
-        });
-        assert_eq!(i, expected.len());
-    }
-
-    #[test]
-    fn test_intersection() {
-        fn check_intersection(a: &[int], b: &[int], expected: &[int]) {
-            check(a, b, expected, |x, y, f| x.intersection(y).advance(f))
-        }
-
-        check_intersection([], [], []);
-        check_intersection([1, 2, 3], [], []);
-        check_intersection([], [1, 2, 3], []);
-        check_intersection([2], [1, 2, 3], [2]);
-        check_intersection([1, 2, 3], [2], [2]);
-        check_intersection([11, 1, 3, 77, 103, 5, -5],
-                           [2, 11, 77, -9, -42, 5, 3],
-                           [3, 5, 11, 77]);
-    }
-
-    #[test]
-    fn test_difference() {
-        fn check_difference(a: &[int], b: &[int], expected: &[int]) {
-            check(a, b, expected, |x, y, f| x.difference(y).advance(f))
-        }
-
-        check_difference([], [], []);
-        check_difference([1, 12], [], [1, 12]);
-        check_difference([], [1, 2, 3, 9], []);
-        check_difference([1, 3, 5, 9, 11],
-                         [3, 9],
-                         [1, 5, 11]);
-        check_difference([-5, 11, 22, 33, 40, 42],
-                         [-12, -5, 14, 23, 34, 38, 39, 50],
-                         [11, 22, 33, 40, 42]);
-    }
-
-    #[test]
-    fn test_symmetric_difference() {
-        fn check_symmetric_difference(a: &[int], b: &[int],
-                                      expected: &[int]) {
-            check(a, b, expected, |x, y, f| x.symmetric_difference(y).advance(f))
-        }
-
-        check_symmetric_difference([], [], []);
-        check_symmetric_difference([1, 2, 3], [2], [1, 3]);
-        check_symmetric_difference([2], [1, 2, 3], [1, 3]);
-        check_symmetric_difference([1, 3, 5, 9, 11],
-                                   [-2, 3, 9, 14, 22],
-                                   [-2, 1, 5, 11, 14, 22]);
-    }
-
-    #[test]
-    fn test_union() {
-        fn check_union(a: &[int], b: &[int],
-                                      expected: &[int]) {
-            check(a, b, expected, |x, y, f| x.union(y).advance(f))
-        }
-
-        check_union([], [], []);
-        check_union([1, 2, 3], [2], [1, 2, 3]);
-        check_union([2], [1, 2, 3], [1, 2, 3]);
-        check_union([1, 3, 5, 9, 11, 16, 19, 24],
-                    [-2, 1, 5, 9, 13, 19],
-                    [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]);
-    }
-
-    #[test]
-    fn test_zip() {
-        let mut x = TreeSet::new();
-        x.insert(5u);
-        x.insert(12u);
-        x.insert(11u);
-
-        let mut y = TreeSet::new();
-        y.insert("foo");
-        y.insert("bar");
-
-        let x = x;
-        let y = y;
-        let mut z = x.iter().zip(y.iter());
-
-        // FIXME: #5801: this needs a type hint to compile...
-        let result: Option<(&uint, & &'static str)> = z.next();
-        assert_eq!(result.unwrap(), (&5u, & &"bar"));
-
-        let result: Option<(&uint, & &'static str)> = z.next();
-        assert_eq!(result.unwrap(), (&11u, & &"foo"));
-
-        let result: Option<(&uint, & &'static str)> = z.next();
-        assert!(result.is_none());
-    }
-
-    #[test]
-    fn test_swap() {
-        let mut m = TreeMap::new();
-        assert_eq!(m.swap(1, 2), None);
-        assert_eq!(m.swap(1, 3), Some(2));
-        assert_eq!(m.swap(1, 4), Some(3));
-    }
-
-    #[test]
-    fn test_pop() {
-        let mut m = TreeMap::new();
-        m.insert(1, 2);
-        assert_eq!(m.pop(&1), Some(2));
-        assert_eq!(m.pop(&1), None);
-    }
-
-    #[test]
-    fn test_from_iter() {
-        let xs = ~[1, 2, 3, 4, 5, 6, 7, 8, 9];
-
-        let set: TreeSet<int> = xs.iter().map(|&x| x).collect();
-
-        for x in xs.iter() {
-            assert!(set.contains(x));
-        }
-    }
-}
diff --git a/src/libextra/workcache.rs b/src/libextra/workcache.rs
index d16edb7aa1e..007b54adbe5 100644
--- a/src/libextra/workcache.rs
+++ b/src/libextra/workcache.rs
@@ -14,7 +14,7 @@ use json;
 use json::ToJson;
 use serialize::{Encoder, Encodable, Decoder, Decodable};
 use sync::{Arc,RWArc};
-use treemap::TreeMap;
+use collections::TreeMap;
 use std::str;
 use std::io;
 use std::io::{File, MemWriter};