moved collections from libextra into libcollections

11 files changed, 7832 insertions, 0 deletions

diff --git a/src/libcollections/bitv.rs b/src/libcollections/bitv.rs
new file mode 100644
index 00000000000..7211907f483
--- /dev/null
+++ b/src/libcollections/bitv.rs
@@ -0,0 +1,1675 @@
+// 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/libcollections/btree.rs b/src/libcollections/btree.rs
new file mode 100644
index 00000000000..791673d75bb
--- /dev/null
+++ b/src/libcollections/btree.rs
@@ -0,0 +1,592 @@
+// 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/libcollections/deque.rs b/src/libcollections/deque.rs
new file mode 100644
index 00000000000..325f0ee4edb
--- /dev/null
+++ b/src/libcollections/deque.rs
@@ -0,0 +1,122 @@
+// 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 extra::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/libcollections/dlist.rs b/src/libcollections/dlist.rs
new file mode 100644
index 00000000000..2b7c5d37336
--- /dev/null
+++ b/src/libcollections/dlist.rs
@@ -0,0 +1,1204 @@
+// 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 deque::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 deque::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/libcollections/lib.rs b/src/libcollections/lib.rs
new file mode 100644
index 00000000000..417bf47803e
--- /dev/null
+++ b/src/libcollections/lib.rs
@@ -0,0 +1,46 @@
+// Copyright 2013-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.
+
+/*!
+ * Collection types.
+ */
+
+#[crate_id = "collections#0.10-pre"];
+#[crate_type = "rlib"];
+#[crate_type = "dylib"];
+#[license = "MIT/ASL2"];
+
+#[feature(macro_rules, managed_boxes)];
+
+#[cfg(test)] extern mod extra;
+
+extern mod serialize;
+
+pub use bitv::Bitv;
+pub use btree::BTree;
+pub use deque::Deque;
+pub use dlist::DList;
+pub use list::List;
+pub use lru_cache::LruCache;
+pub use priority_queue::PriorityQueue;
+pub use ringbuf::RingBuf;
+pub use smallintmap::SmallIntMap;
+pub use treemap::{TreeMap, TreeSet};
+
+pub mod bitv;
+pub mod btree;
+pub mod deque;
+pub mod dlist;
+pub mod list;
+pub mod lru_cache;
+pub mod priority_queue;
+pub mod ringbuf;
+pub mod smallintmap;
+pub mod treemap;
\ No newline at end of file
diff --git a/src/libcollections/list.rs b/src/libcollections/list.rs
new file mode 100644
index 00000000000..79d0f3f49a7
--- /dev/null
+++ b/src/libcollections/list.rs
@@ -0,0 +1,248 @@
+// 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::{List, Nil, from_vec, head, is_empty, tail};
+    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/libcollections/lru_cache.rs b/src/libcollections/lru_cache.rs
new file mode 100644
index 00000000000..de7b511fd41
--- /dev/null
+++ b/src/libcollections/lru_cache.rs
@@ -0,0 +1,367 @@
+// 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 collections::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/libcollections/priority_queue.rs b/src/libcollections/priority_queue.rs
new file mode 100644
index 00000000000..3ae3dae9ea3
--- /dev/null
+++ b/src/libcollections/priority_queue.rs
@@ -0,0 +1,388 @@
+// 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/libcollections/ringbuf.rs b/src/libcollections/ringbuf.rs
new file mode 100644
index 00000000000..933fe2048e4
--- /dev/null
+++ b/src/libcollections/ringbuf.rs
@@ -0,0 +1,858 @@
+// 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 deque::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 deque::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/libcollections/smallintmap.rs b/src/libcollections/smallintmap.rs
new file mode 100644
index 00000000000..b996f0dea32
--- /dev/null
+++ b/src/libcollections/smallintmap.rs
@@ -0,0 +1,529 @@
+// 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::SmallIntMap;
+    use extra::test::BenchHarness;
+    use deque::bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
+
+    // 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/libcollections/treemap.rs b/src/libcollections/treemap.rs
new file mode 100644
index 00000000000..0fccc57b29e
--- /dev/null
+++ b/src/libcollections/treemap.rs
@@ -0,0 +1,1803 @@
+// 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::TreeMap;
+    use extra::test::BenchHarness;
+    use deque::bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
+
+    // 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::{TreeMap, TreeSet};
+
+    #[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));
+        }
+    }
+}