auto merge of #5005 : alexcrichton/rust/bitv++, r=catamorphism

These commits take the old bitv implementation and modernize it with an explicit self, some minor touchups, and using what I think is some more recent patterns (like `::new` instead of `Type()`).

Additionally, this adds an implementation of `container::Set` on top of a bit vector to have as a set of `uint`s. I initially tried to parameterize the type for the set to be `T: NumCast` but I was hitting build problems in stage0 which I think means that it's not in a snapshot yet, so it's just hardcoded as a set of `uint`s now. In the future perhaps it could be parameterized. I'm not sure if it would really add anything, though, so maybe it's nicer to be hardcoded anyway.

I also added some extra methods to do normal bit vector operations on the set in-place, but these aren't a part of the `Set` trait right now. I haven't benchmarked any of these operations just yet, but I imagine that there's quite a lot of room for optimization here and there.

1 files changed, 701 insertions, 187 deletions

diff --git a/src/libstd/bitv.rs b/src/libstd/bitv.rs
index 75b97f494bd..5ba10a9eb14 100644
--- a/src/libstd/bitv.rs
+++ b/src/libstd/bitv.rs
@@ -8,107 +8,104 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use core::container::{Container, Mutable, Set};
+use core::num::NumCast;
 use core::ops;
 use core::prelude::*;
 use core::uint;
-use core::vec::{cast_to_mut, from_elem};
+use core::vec::from_elem;
 use core::vec;
 
 struct SmallBitv {
     /// only the lowest nbits of this value are used. the rest is undefined.
-    mut bits: u32
-}
-
-fn SmallBitv(bits: u32) -> SmallBitv {
-    SmallBitv {bits: bits}
+    bits: uint
 }
 
 /// a mask that has a 1 for each defined bit in a small_bitv, assuming n bits
 #[inline(always)]
-fn small_mask(nbits: uint) -> u32 {
+fn small_mask(nbits: uint) -> uint {
     (1 << nbits) - 1
 }
 
 impl SmallBitv {
+    static fn new(bits: uint) -> SmallBitv {
+        SmallBitv {bits: bits}
+    }
 
     #[inline(always)]
-    fn bits_op(right_bits: u32, nbits: uint, f: fn(u32, u32) -> u32) -> bool {
+    fn bits_op(&mut self, right_bits: uint, nbits: uint,
+               f: fn(uint, uint) -> uint) -> bool {
         let mask = small_mask(nbits);
-        let old_b: u32 = self.bits;
+        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(always)]
-    fn union(s: &SmallBitv, nbits: uint) -> bool {
+    fn union(&mut self, s: &SmallBitv, nbits: uint) -> bool {
         self.bits_op(s.bits, nbits, |u1, u2| u1 | u2)
     }
 
     #[inline(always)]
-    fn intersect(s: &SmallBitv, nbits: uint) -> bool {
+    fn intersect(&mut self, s: &SmallBitv, nbits: uint) -> bool {
         self.bits_op(s.bits, nbits, |u1, u2| u1 & u2)
     }
 
     #[inline(always)]
-    fn become(s: &SmallBitv, nbits: uint) -> bool {
+    fn become(&mut self, s: &SmallBitv, nbits: uint) -> bool {
         self.bits_op(s.bits, nbits, |_u1, u2| u2)
     }
 
     #[inline(always)]
-    fn difference(s: &SmallBitv, nbits: uint) -> bool {
+    fn difference(&mut self, s: &SmallBitv, nbits: uint) -> bool {
         self.bits_op(s.bits, nbits, |u1, u2| u1 & !u2)
     }
 
     #[inline(always)]
-    pure fn get(i: uint) -> bool {
+    pure fn get(&self, i: uint) -> bool {
         (self.bits & (1 << i)) != 0
     }
 
     #[inline(always)]
-    fn set(i: uint, x: bool) {
+    fn set(&mut self, i: uint, x: bool) {
         if x {
             self.bits |= 1<<i;
         }
         else {
-            self.bits &= !(1<<i as u32);
+            self.bits &= !(1<<i as uint);
         }
     }
 
     #[inline(always)]
-    fn equals(b: &SmallBitv, nbits: uint) -> bool {
+    fn equals(&self, b: &SmallBitv, nbits: uint) -> bool {
         let mask = small_mask(nbits);
         mask & self.bits == mask & b.bits
     }
 
     #[inline(always)]
-    fn clear() { self.bits = 0; }
+    fn clear(&mut self) { self.bits = 0; }
 
     #[inline(always)]
-    fn set_all() { self.bits = !0; }
+    fn set_all(&mut self) { self.bits = !0; }
 
     #[inline(always)]
-    fn is_true(nbits: uint) -> bool {
+    fn is_true(&self, nbits: uint) -> bool {
         small_mask(nbits) & !self.bits == 0
     }
 
     #[inline(always)]
-    fn is_false(nbits: uint) -> bool {
+    fn is_false(&self, nbits: uint) -> bool {
         small_mask(nbits) & self.bits == 0
     }
 
     #[inline(always)]
-    fn invert() { self.bits = !self.bits; }
+    fn invert(&mut self) { self.bits = !self.bits; }
 
 }
 
 struct BigBitv {
-    // only mut b/c of clone and lack of other constructor
-    mut storage: ~[uint]
-}
-
-fn BigBitv(storage: ~[uint]) -> BigBitv {
-    BigBitv {storage: storage}
+    storage: ~[uint]
 }
 
 /**
@@ -117,8 +114,8 @@ fn BigBitv(storage: ~[uint]) -> BigBitv {
  */
 #[inline(always)]
 fn big_mask(nbits: uint, elem: uint) -> uint {
-    let rmd = nbits % uint_bits;
-    let nelems = nbits/uint_bits + if rmd == 0 {0} else {1};
+    let rmd = nbits % uint::bits;
+    let nelems = nbits/uint::bits + if rmd == 0 {0} else {1};
 
     if elem < nelems - 1 || rmd == 0 {
         !0
@@ -128,30 +125,31 @@ fn big_mask(nbits: uint, elem: uint) -> uint {
 }
 
 impl BigBitv {
+    static fn new(storage: ~[uint]) -> BigBitv {
+        BigBitv {storage: storage}
+    }
 
     #[inline(always)]
-    fn process(b: &BigBitv, nbits: uint, op: fn(uint, uint) -> uint) -> bool {
+    fn process(&mut self, b: &BigBitv, nbits: uint,
+               op: fn(uint, uint) -> uint) -> bool {
         let len = b.storage.len();
         assert (self.storage.len() == len);
         let mut changed = false;
-        do uint::range(0, len) |i| {
+        for uint::range(0, len) |i| {
             let mask = big_mask(nbits, i);
             let w0 = self.storage[i] & mask;
             let w1 = b.storage[i] & mask;
             let w = op(w0, w1) & mask;
             if w0 != w {
-                unsafe {
-                    changed = true;
-                    self.storage[i] = w;
-                }
+                changed = true;
+                self.storage[i] = w;
             }
-            true
         }
         changed
     }
 
     #[inline(always)]
-     fn each_storage(op: fn(v: &mut uint) -> bool) {
+    fn each_storage(&mut self, op: fn(v: &mut uint) -> bool) {
         for uint::range(0, self.storage.len()) |i| {
             let mut w = self.storage[i];
             let b = op(&mut w);
@@ -161,47 +159,47 @@ impl BigBitv {
      }
 
     #[inline(always)]
-    fn invert() { for self.each_storage() |w| { *w = !*w } }
+    fn invert(&mut self) { for self.each_storage |w| { *w = !*w } }
 
     #[inline(always)]
-    fn union(b: &BigBitv, nbits: uint) -> bool {
-        self.process(b, nbits, lor)
+    fn union(&mut self, b: &BigBitv, nbits: uint) -> bool {
+        self.process(b, nbits, |w1, w2| w1 | w2)
     }
 
     #[inline(always)]
-    fn intersect(b: &BigBitv, nbits: uint) -> bool {
-        self.process(b, nbits, land)
+    fn intersect(&mut self, b: &BigBitv, nbits: uint) -> bool {
+        self.process(b, nbits, |w1, w2| w1 & w2)
     }
 
     #[inline(always)]
-    fn become(b: &BigBitv, nbits: uint) -> bool {
-        self.process(b, nbits, right)
+    fn become(&mut self, b: &BigBitv, nbits: uint) -> bool {
+        self.process(b, nbits, |_, w| w)
     }
 
     #[inline(always)]
-    fn difference(b: &BigBitv, nbits: uint) -> bool {
-        self.process(b, nbits, difference)
+    fn difference(&mut self, b: &BigBitv, nbits: uint) -> bool {
+        self.process(b, nbits, |w1, w2| w1 & !w2)
     }
 
     #[inline(always)]
-    pure fn get(i: uint) -> bool {
-        let w = i / uint_bits;
-        let b = i % uint_bits;
+    pure 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(always)]
-    fn set(i: uint, x: bool) {
-        let w = i / uint_bits;
-        let b = i % uint_bits;
+    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 };
+                          else { self.storage[w] & !flag };
     }
 
     #[inline(always)]
-    fn equals(b: &BigBitv, nbits: uint) -> bool {
+    fn equals(&self, b: &BigBitv, nbits: uint) -> bool {
         let len = b.storage.len();
         for uint::iterate(0, len) |i| {
             let mask = big_mask(nbits, i);
@@ -223,33 +221,19 @@ pub struct Bitv {
     nbits: uint
 }
 
-pub fn Bitv (nbits: uint, init: bool) -> Bitv {
-    let rep = if nbits <= 32 {
-        Small(~SmallBitv(if init {!0} else {0}))
-    }
-    else {
-        let nelems = nbits/uint_bits +
-                     if nbits % uint_bits == 0 {0} else {1};
-        let elem = if init {!0} else {0};
-        let s = from_elem(nelems, elem);
-        Big(~BigBitv(s))
-    };
-    Bitv {rep: rep, nbits: nbits}
-}
-
 priv impl Bitv {
 
-    fn die() -> ! {
+    fn die(&self) -> ! {
         fail!(~"Tried to do operation on bit vectors with different sizes");
     }
 
     #[inline(always)]
-    fn do_op(op: Op, other: &Bitv) -> bool {
+    fn do_op(&mut self, op: Op, other: &Bitv) -> bool {
         if self.nbits != other.nbits {
             self.die();
         }
         match self.rep {
-          Small(ref s) => match other.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),
@@ -258,7 +242,7 @@ priv impl Bitv {
             },
             Big(_) => self.die()
           },
-          Big(ref s) => match other.rep {
+          Big(ref mut s) => match other.rep {
             Small(_) => self.die(),
             Big(ref s1) => match op {
               Union      => s.union(*s1,      self.nbits),
@@ -273,6 +257,19 @@ priv impl Bitv {
 }
 
 impl Bitv {
+    static fn new(nbits: uint, init: bool) -> Bitv {
+        let rep = if nbits <= uint::bits {
+            Small(~SmallBitv::new(if init {!0} else {0}))
+        }
+        else {
+            let nelems = nbits/uint::bits +
+                         if nbits % uint::bits == 0 {0} else {1};
+            let elem = if init {!0} else {0};
+            let s = from_elem(nelems, elem);
+            Big(~BigBitv::new(s))
+        };
+        Bitv {rep: rep, nbits: nbits}
+    }
 
     /**
      * Calculates the union of two bitvectors
@@ -281,7 +278,7 @@ impl Bitv {
      * the same length. Returns 'true' if `self` changed.
     */
     #[inline(always)]
-    fn union(v1: &Bitv) -> bool { self.do_op(Union, v1) }
+    fn union(&mut self, v1: &Bitv) -> bool { self.do_op(Union, v1) }
 
     /**
      * Calculates the intersection of two bitvectors
@@ -290,7 +287,7 @@ impl Bitv {
      * must be the same length. Returns 'true' if `self` changed.
     */
     #[inline(always)]
-    fn intersect(v1: &Bitv) -> bool { self.do_op(Intersect, v1) }
+    fn intersect(&mut self, v1: &Bitv) -> bool { self.do_op(Intersect, v1) }
 
     /**
      * Assigns the value of `v1` to `self`
@@ -299,11 +296,11 @@ impl Bitv {
      * changed
      */
     #[inline(always)]
-    fn assign(v: &Bitv) -> bool { self.do_op(Assign, v) }
+    fn assign(&mut self, v: &Bitv) -> bool { self.do_op(Assign, v) }
 
     /// Retrieve the value at index `i`
     #[inline(always)]
-    pure fn get(i: uint) -> bool {
+    pure fn get(&self, i: uint) -> bool {
        assert (i < self.nbits);
        match self.rep {
          Big(ref b)   => b.get(i),
@@ -317,11 +314,11 @@ impl Bitv {
      * `i` must be less than the length of the bitvector.
      */
     #[inline(always)]
-    fn set(i: uint, x: bool) {
+    fn set(&mut self, i: uint, x: bool) {
       assert (i < self.nbits);
       match self.rep {
-        Big(ref b)   => b.set(i, x),
-        Small(ref s) => s.set(i, x)
+        Big(ref mut b)   => b.set(i, x),
+        Small(ref mut s) => s.set(i, x)
       }
     }
 
@@ -332,7 +329,7 @@ impl Bitv {
      * bitvectors contain identical elements.
      */
     #[inline(always)]
-    fn equal(v1: &Bitv) -> bool {
+    fn equal(&self, v1: &Bitv) -> bool {
       if self.nbits != v1.nbits { return false; }
       match self.rep {
         Small(ref b) => match v1.rep {
@@ -348,27 +345,27 @@ impl Bitv {
 
     /// Set all bits to 0
     #[inline(always)]
-    fn clear() {
+    fn clear(&mut self) {
         match self.rep {
-          Small(ref b) => b.clear(),
-          Big(ref s) => for s.each_storage() |w| { *w = 0u }
+          Small(ref mut b) => b.clear(),
+          Big(ref mut s) => for s.each_storage() |w| { *w = 0u }
         }
     }
 
     /// Set all bits to 1
     #[inline(always)]
-    fn set_all() {
+    fn set_all(&mut self) {
       match self.rep {
-        Small(ref b) => b.set_all(),
-        Big(ref s) => for s.each_storage() |w| { *w = !0u } }
+        Small(ref mut b) => b.set_all(),
+        Big(ref mut s) => for s.each_storage() |w| { *w = !0u } }
     }
 
     /// Invert all bits
     #[inline(always)]
-    fn invert() {
+    fn invert(&mut self) {
       match self.rep {
-        Small(ref b) => b.invert(),
-        Big(ref s) => for s.each_storage() |w| { *w = !*w } }
+        Small(ref mut b) => b.invert(),
+        Big(ref mut s) => for s.each_storage() |w| { *w = !*w } }
     }
 
     /**
@@ -381,11 +378,11 @@ impl Bitv {
      * Returns `true` if `v0` was changed.
      */
     #[inline(always)]
-    fn difference(v: &Bitv) -> bool { self.do_op(Difference, v) }
+    fn difference(&mut self, v: &Bitv) -> bool { self.do_op(Difference, v) }
 
     /// Returns true if all bits are 1
     #[inline(always)]
-    fn is_true() -> bool {
+    fn is_true(&self) -> bool {
       match self.rep {
         Small(ref b) => b.is_true(self.nbits),
         _ => {
@@ -396,7 +393,7 @@ impl Bitv {
     }
 
     #[inline(always)]
-    fn each(f: fn(bool) -> bool) {
+    fn each(&self, f: fn(bool) -> bool) {
         let mut i = 0;
         while i < self.nbits {
             if !f(self.get(i)) { break; }
@@ -405,7 +402,7 @@ impl Bitv {
     }
 
     /// Returns true if all bits are 0
-    fn is_false() -> bool {
+    fn is_false(&self) -> bool {
       match self.rep {
         Small(ref b) => b.is_false(self.nbits),
         Big(_) => {
@@ -415,7 +412,7 @@ impl Bitv {
       }
     }
 
-    fn init_to_vec(i: uint) -> uint {
+    fn init_to_vec(&self, i: uint) -> uint {
       return if self.get(i) { 1 } else { 0 };
     }
 
@@ -424,7 +421,7 @@ impl Bitv {
      *
      * Each uint in the resulting vector has either value 0u or 1u.
      */
-    fn to_vec() -> ~[uint] {
+    fn to_vec(&self) -> ~[uint] {
         vec::from_fn(self.nbits, |x| self.init_to_vec(x))
     }
 
@@ -434,7 +431,7 @@ impl Bitv {
      * size of the bitv is not a multiple of 8 then trailing bits
      * will be filled-in with false/0
      */
-    fn to_bytes() -> ~[u8] {
+    fn to_bytes(&self) -> ~[u8] {
 
         fn bit (bitv: &Bitv, byte: uint, bit: uint) -> u8 {
             let offset = byte * 8 + bit;
@@ -448,21 +445,21 @@ impl Bitv {
         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)
+            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
      */
-    fn to_bools() -> ~[bool] {
+    fn to_bools(&self) -> ~[bool] {
         vec::from_fn(self.nbits, |i| self[i])
     }
 
@@ -485,7 +482,7 @@ impl Bitv {
      * The uint vector is expected to only contain the values 0u and 1u. Both
      * the bitvector and vector must have the same length
      */
-    fn eq_vec(v: ~[uint]) -> bool {
+    fn eq_vec(&self, v: ~[uint]) -> bool {
         assert self.nbits == v.len();
         let mut i = 0;
         while i < self.nbits {
@@ -497,7 +494,7 @@ impl Bitv {
         true
     }
 
-    fn ones(f: fn(uint) -> bool) {
+    fn ones(&self, f: fn(uint) -> bool) {
         for uint::range(0, self.nbits) |i| {
             if self.get(i) {
                 if !f(i) { break }
@@ -516,7 +513,7 @@ impl Clone for Bitv {
             Bitv{nbits: self.nbits, rep: Small(~SmallBitv{bits: b.bits})}
           }
           Big(ref b) => {
-            let mut st = from_elem(self.nbits / uint_bits + 1, 0);
+            let mut st = from_elem(self.nbits / uint::bits + 1, 0);
             let len = st.len();
             for uint::range(0, len) |i| { st[i] = b.storage[i]; };
             Bitv{nbits: self.nbits, rep: Big(~BigBitv{storage: st})}
@@ -551,45 +548,344 @@ pub fn from_bools(bools: &[bool]) -> Bitv {
  * index is f(index).
  */
 pub fn from_fn(len: uint, f: fn(index: uint) -> bool) -> Bitv {
-    let bitv = Bitv(len, false);
+    let mut bitv = Bitv::new(len, false);
     for uint::range(0, len) |i| {
         bitv.set(i, f(i));
     }
     bitv
 }
 
-const uint_bits: uint = 32u + (1u << 32u >> 27u);
+impl ops::Index<uint,bool> for Bitv {
+    pure fn index(&self, i: uint) -> bool {
+        self.get(i)
+    }
+}
 
-pure fn lor(w0: uint, w1: uint) -> uint { return w0 | w1; }
+#[inline(always)]
+pure fn iterate_bits(base: uint, bits: uint, f: fn(uint) -> bool) -> bool {
+    if bits == 0 {
+        return true;
+    }
+    for uint::range(0, uint::bits) |i| {
+        if bits & (1 << i) != 0 {
+            if !f(base + i) {
+                return false;
+            }
+        }
+    }
+    return true;
+}
 
-pure fn land(w0: uint, w1: uint) -> uint { return w0 & w1; }
+/// 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.
+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
+}
 
-pure fn difference(w0: uint, w1: uint) -> uint { return w0 & !w1; }
+impl BitvSet {
+    /// Creates a new bit vector set with initially no contents
+    static fn new() -> BitvSet {
+        BitvSet{ size: 0, bitv: BigBitv::new(~[0]) }
+    }
 
-pure fn right(_w0: uint, w1: uint) -> uint { return w1; }
+    /// Creates a new bit vector set from the given bit vector
+    static fn from_bitv(bitv: Bitv) -> BitvSet {
+        let mut size = 0;
+        for bitv.ones |_| {
+            size += 1;
+        }
+        let Bitv{rep, _} = bitv;
+        match rep {
+            Big(~b) => BitvSet{ size: size, bitv: b },
+            Small(~SmallBitv{bits}) =>
+                BitvSet{ size: size, bitv: BigBitv{ storage: ~[bits] } },
+        }
+    }
 
-impl ops::Index<uint,bool> for Bitv {
-    pure fn index(&self, i: uint) -> bool {
-        self.get(i)
+    /// Returns the capacity in bits for this bit vector. Inserting any
+    /// element less than this amount will not trigger a resizing.
+    pure fn capacity(&self) -> uint { self.bitv.storage.len() * uint::bits }
+
+    /// Consumes this set to return the underlying bit vector
+    fn unwrap(self) -> Bitv {
+        let cap = self.capacity();
+        let BitvSet{bitv, _} = self;
+        return Bitv{ nbits:cap, rep: Big(~bitv) };
+    }
+
+    #[inline(always)]
+    priv fn other_op(&mut self, other: &BitvSet, f: fn(uint, uint) -> uint) {
+        fn nbits(mut w: uint) -> uint {
+            let mut bits = 0;
+            for uint::bits.times {
+                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 other.bitv.storage.eachi |i, &w| {
+            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
+    fn union_with(&mut self, other: &BitvSet) {
+        self.other_op(other, |w1, w2| w1 | w2);
+    }
+
+    /// Intersect in-place with the specified other bit vector
+    fn intersect_with(&mut self, other: &BitvSet) {
+        self.other_op(other, |w1, w2| w1 & w2);
+    }
+
+    /// Difference in-place with the specified other bit vector
+    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
+    fn symmetric_difference_with(&mut self, other: &BitvSet) {
+        self.other_op(other, |w1, w2| w1 ^ w2);
+    }
+}
+
+impl BaseIter<uint> for BitvSet {
+    pure fn size_hint(&self) -> Option<uint> { Some(self.len()) }
+
+    pure fn each(&self, blk: fn(v: &uint) -> bool) {
+        for self.bitv.storage.eachi |i, &w| {
+            if !iterate_bits(i * uint::bits, w, |b| blk(&b)) {
+                return;
+            }
+        }
+    }
+}
+
+impl cmp::Eq for BitvSet {
+    pure fn eq(&self, other: &BitvSet) -> bool {
+        if self.size != other.size {
+            return false;
+        }
+        for self.each_common(other) |_, w1, w2| {
+            if w1 != w2 {
+                return false;
+            }
+        }
+        for self.each_outlier(other) |_, _, w| {
+            if w != 0 {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    pure fn ne(&self, other: &BitvSet) -> bool { !self.eq(other) }
+}
+
+impl Container for BitvSet {
+    pure fn len(&self) -> uint { self.size }
+    pure fn is_empty(&self) -> bool { self.size == 0 }
+}
+
+impl Mutable for BitvSet {
+    fn clear(&mut self) {
+        for self.bitv.each_storage |w| { *w = 0; }
+        self.size = 0;
+    }
+}
+
+impl Set<uint> for BitvSet {
+    pure fn contains(&self, value: &uint) -> bool {
+        *value < self.bitv.storage.len() * uint::bits && self.bitv.get(*value)
+    }
+
+    fn insert(&mut self, value: uint) -> bool {
+        if self.contains(&value) {
+            return false;
+        }
+        let nbits = self.capacity();
+        if value >= nbits {
+            let newsize = uint::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;
+    }
+
+    pure fn is_disjoint(&self, other: &BitvSet) -> bool {
+        for self.intersection(other) |_| {
+            return false;
+        }
+        return true;
+    }
+
+    pure fn is_subset(&self, other: &BitvSet) -> bool {
+        for self.each_common(other) |_, w1, w2| {
+            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 self.each_outlier(other) |mine, _, w| {
+            if !mine {
+                return true;
+            } else if w != 0 {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    pure fn is_superset(&self, other: &BitvSet) -> bool {
+        other.is_subset(self)
+    }
+
+    pure fn difference(&self, other: &BitvSet, f: fn(&uint) -> bool) {
+        for self.each_common(other) |i, w1, w2| {
+            if !iterate_bits(i, w1 & !w2, |b| f(&b)) {
+                return;
+            }
+        }
+        /* everything we have that they don't also shows up */
+        self.each_outlier(other, |mine, i, w|
+            !mine || iterate_bits(i, w, |b| f(&b))
+        );
+    }
+
+    pure fn symmetric_difference(&self, other: &BitvSet,
+                                 f: fn(&uint) -> bool) {
+        for self.each_common(other) |i, w1, w2| {
+            if !iterate_bits(i, w1 ^ w2, |b| f(&b)) {
+                return;
+            }
+        }
+        self.each_outlier(other, |_, i, w|
+            iterate_bits(i, w, |b| f(&b))
+        );
+    }
+
+    pure fn intersection(&self, other: &BitvSet, f: fn(&uint) -> bool) {
+        for self.each_common(other) |i, w1, w2| {
+            if !iterate_bits(i, w1 & w2, |b| f(&b)) {
+                return;
+            }
+        }
+    }
+
+    pure fn union(&self, other: &BitvSet, f: fn(&uint) -> bool) {
+        for self.each_common(other) |i, w1, w2| {
+            if !iterate_bits(i, w1 | w2, |b| f(&b)) {
+                return;
+            }
+        }
+        self.each_outlier(other, |_, i, w|
+            iterate_bits(i, w, |b| f(&b))
+        );
+    }
+}
+
+priv 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.
+    pure fn each_common(&self, other: &BitvSet,
+                        f: fn(uint, uint, uint) -> bool) {
+        let min = uint::min(self.bitv.storage.len(),
+                            other.bitv.storage.len());
+        for self.bitv.storage.view(0, min).eachi |i, &w| {
+            if !f(i * uint::bits, w, other.bitv.storage[i]) {
+                return;
+            }
+        }
+    }
+
+    /// 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'.
+    pure fn each_outlier(&self, other: &BitvSet,
+                         f: fn(bool, uint, uint) -> bool) {
+        let len1 = self.bitv.storage.len();
+        let len2 = other.bitv.storage.len();
+        let min = uint::min(len1, len2);
+
+        /* only one of these loops will execute and that's the point */
+        for self.bitv.storage.view(min, len1).eachi |i, &w| {
+            if !f(true, (i + min) * uint::bits, w) {
+                return;
+            }
+        }
+        for other.bitv.storage.view(min, len2).eachi |i, &w| {
+            if !f(false, (i + min) * uint::bits, w) {
+                return;
+            }
+        }
     }
 }
 
 #[cfg(test)]
 mod tests {
     use core::prelude::*;
+    use std::test::BenchHarness;
 
     use bitv::*;
     use bitv;
 
     use core::uint;
     use core::vec;
+    use core::rand;
+
+    const bench_bits : uint = 1 << 14;
 
     #[test]
     pub fn test_to_str() {
-        let zerolen = Bitv(0u, false);
+        let zerolen = Bitv::new(0u, false);
         assert zerolen.to_str() == ~"";
 
-        let eightbits = Bitv(8u, false);
+        let eightbits = Bitv::new(8u, false);
         assert eightbits.to_str() == ~"00000000";
     }
 
@@ -597,7 +893,7 @@ mod tests {
     pub fn test_0_elements() {
         let mut act;
         let mut exp;
-        act = Bitv(0u, false);
+        act = Bitv::new(0u, false);
         exp = vec::from_elem::<uint>(0u, 0u);
         assert act.eq_vec(exp);
     }
@@ -605,15 +901,15 @@ mod tests {
     #[test]
     pub fn test_1_element() {
         let mut act;
-        act = Bitv(1u, false);
+        act = Bitv::new(1u, false);
         assert act.eq_vec(~[0u]);
-        act = Bitv(1u, true);
+        act = Bitv::new(1u, true);
         assert act.eq_vec(~[1u]);
     }
 
     #[test]
     pub fn test_2_elements() {
-        let b = bitv::Bitv(2, false);
+        let mut b = bitv::Bitv::new(2, false);
         b.set(0, true);
         b.set(1, false);
         assert b.to_str() == ~"10";
@@ -624,15 +920,15 @@ mod tests {
         let mut act;
         // all 0
 
-        act = Bitv(10u, false);
+        act = Bitv::new(10u, false);
         assert (act.eq_vec(~[0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u]));
         // all 1
 
-        act = Bitv(10u, true);
+        act = Bitv::new(10u, true);
         assert (act.eq_vec(~[1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u]));
         // mixed
 
-        act = Bitv(10u, false);
+        act = Bitv::new(10u, false);
         act.set(0u, true);
         act.set(1u, true);
         act.set(2u, true);
@@ -641,7 +937,7 @@ mod tests {
         assert (act.eq_vec(~[1u, 1u, 1u, 1u, 1u, 0u, 0u, 0u, 0u, 0u]));
         // mixed
 
-        act = Bitv(10u, false);
+        act = Bitv::new(10u, false);
         act.set(5u, true);
         act.set(6u, true);
         act.set(7u, true);
@@ -650,7 +946,7 @@ mod tests {
         assert (act.eq_vec(~[0u, 0u, 0u, 0u, 0u, 1u, 1u, 1u, 1u, 1u]));
         // mixed
 
-        act = Bitv(10u, false);
+        act = Bitv::new(10u, false);
         act.set(0u, true);
         act.set(3u, true);
         act.set(6u, true);
@@ -663,21 +959,21 @@ mod tests {
         let mut act;
         // all 0
 
-        act = Bitv(31u, false);
+        act = Bitv::new(31u, false);
         assert (act.eq_vec(
                        ~[0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u,
                         0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u,
                         0u, 0u, 0u, 0u, 0u]));
         // all 1
 
-        act = Bitv(31u, true);
+        act = Bitv::new(31u, true);
         assert (act.eq_vec(
                        ~[1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u,
                         1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u,
                         1u, 1u, 1u, 1u, 1u]));
         // mixed
 
-        act = Bitv(31u, false);
+        act = Bitv::new(31u, false);
         act.set(0u, true);
         act.set(1u, true);
         act.set(2u, true);
@@ -692,7 +988,7 @@ mod tests {
                         0u, 0u, 0u, 0u, 0u]));
         // mixed
 
-        act = Bitv(31u, false);
+        act = Bitv::new(31u, false);
         act.set(16u, true);
         act.set(17u, true);
         act.set(18u, true);
@@ -707,7 +1003,7 @@ mod tests {
                         0u, 0u, 0u, 0u, 0u]));
         // mixed
 
-        act = Bitv(31u, false);
+        act = Bitv::new(31u, false);
         act.set(24u, true);
         act.set(25u, true);
         act.set(26u, true);
@@ -721,7 +1017,7 @@ mod tests {
                         1u, 1u, 1u, 1u, 1u]));
         // mixed
 
-        act = Bitv(31u, false);
+        act = Bitv::new(31u, false);
         act.set(3u, true);
         act.set(17u, true);
         act.set(30u, true);
@@ -736,21 +1032,21 @@ mod tests {
         let mut act;
         // all 0
 
-        act = Bitv(32u, false);
+        act = Bitv::new(32u, false);
         assert (act.eq_vec(
                        ~[0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u,
                         0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u,
                         0u, 0u, 0u, 0u, 0u, 0u]));
         // all 1
 
-        act = Bitv(32u, true);
+        act = Bitv::new(32u, true);
         assert (act.eq_vec(
                        ~[1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u,
                         1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u,
                         1u, 1u, 1u, 1u, 1u, 1u]));
         // mixed
 
-        act = Bitv(32u, false);
+        act = Bitv::new(32u, false);
         act.set(0u, true);
         act.set(1u, true);
         act.set(2u, true);
@@ -765,7 +1061,7 @@ mod tests {
                         0u, 0u, 0u, 0u, 0u, 0u]));
         // mixed
 
-        act = Bitv(32u, false);
+        act = Bitv::new(32u, false);
         act.set(16u, true);
         act.set(17u, true);
         act.set(18u, true);
@@ -780,7 +1076,7 @@ mod tests {
                         0u, 0u, 0u, 0u, 0u, 0u]));
         // mixed
 
-        act = Bitv(32u, false);
+        act = Bitv::new(32u, false);
         act.set(24u, true);
         act.set(25u, true);
         act.set(26u, true);
@@ -795,7 +1091,7 @@ mod tests {
                         1u, 1u, 1u, 1u, 1u, 1u]));
         // mixed
 
-        act = Bitv(32u, false);
+        act = Bitv::new(32u, false);
         act.set(3u, true);
         act.set(17u, true);
         act.set(30u, true);
@@ -811,21 +1107,21 @@ mod tests {
         let mut act;
         // all 0
 
-        act = Bitv(33u, false);
+        act = Bitv::new(33u, false);
         assert (act.eq_vec(
                        ~[0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u,
                         0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u,
                         0u, 0u, 0u, 0u, 0u, 0u, 0u]));
         // all 1
 
-        act = Bitv(33u, true);
+        act = Bitv::new(33u, true);
         assert (act.eq_vec(
                        ~[1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u,
                         1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u, 1u,
                         1u, 1u, 1u, 1u, 1u, 1u, 1u]));
         // mixed
 
-        act = Bitv(33u, false);
+        act = Bitv::new(33u, false);
         act.set(0u, true);
         act.set(1u, true);
         act.set(2u, true);
@@ -840,7 +1136,7 @@ mod tests {
                         0u, 0u, 0u, 0u, 0u, 0u, 0u]));
         // mixed
 
-        act = Bitv(33u, false);
+        act = Bitv::new(33u, false);
         act.set(16u, true);
         act.set(17u, true);
         act.set(18u, true);
@@ -855,7 +1151,7 @@ mod tests {
                         0u, 0u, 0u, 0u, 0u, 0u, 0u]));
         // mixed
 
-        act = Bitv(33u, false);
+        act = Bitv::new(33u, false);
         act.set(24u, true);
         act.set(25u, true);
         act.set(26u, true);
@@ -870,7 +1166,7 @@ mod tests {
                         1u, 1u, 1u, 1u, 1u, 1u, 0u]));
         // mixed
 
-        act = Bitv(33u, false);
+        act = Bitv::new(33u, false);
         act.set(3u, true);
         act.set(17u, true);
         act.set(30u, true);
@@ -884,24 +1180,24 @@ mod tests {
 
     #[test]
     pub fn test_equal_differing_sizes() {
-        let v0 = Bitv(10u, false);
-        let v1 = Bitv(11u, false);
+        let v0 = Bitv::new(10u, false);
+        let v1 = Bitv::new(11u, false);
         assert !v0.equal(&v1);
     }
 
     #[test]
     pub fn test_equal_greatly_differing_sizes() {
-        let v0 = Bitv(10u, false);
-        let v1 = Bitv(110u, false);
+        let v0 = Bitv::new(10u, false);
+        let v1 = Bitv::new(110u, false);
         assert !v0.equal(&v1);
     }
 
     #[test]
     pub fn test_equal_sneaky_small() {
-        let a = bitv::Bitv(1, false);
+        let mut a = bitv::Bitv::new(1, false);
         a.set(0, true);
 
-        let b = bitv::Bitv(1, true);
+        let mut b = bitv::Bitv::new(1, true);
         b.set(0, true);
 
         assert a.equal(&b);
@@ -909,12 +1205,12 @@ mod tests {
 
     #[test]
     pub fn test_equal_sneaky_big() {
-        let a = bitv::Bitv(100, false);
+        let mut a = bitv::Bitv::new(100, false);
         for uint::range(0, 100) |i| {
             a.set(i, true);
         }
 
-        let b = bitv::Bitv(100, true);
+        let mut b = bitv::Bitv::new(100, true);
         for uint::range(0, 100) |i| {
             b.set(i, true);
         }
@@ -931,11 +1227,11 @@ mod tests {
 
     #[test]
     pub fn test_to_bytes() {
-        let bv = Bitv(3, true);
+        let mut bv = Bitv::new(3, true);
         bv.set(1, false);
         assert bv.to_bytes() == ~[0b10100000];
 
-        let bv = Bitv(9, false);
+        let mut bv = Bitv::new(9, false);
         bv.set(2, true);
         bv.set(8, true);
         assert bv.to_bytes() == ~[0b00100000, 0b10000000];
@@ -954,48 +1250,266 @@ mod tests {
 
     #[test]
     pub fn test_small_difference() {
-      let b1 = Bitv(3, false);
-      let b2 = Bitv(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];
+        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]
     pub fn test_big_difference() {
-      let b1 = Bitv(100, false);
-      let b2 = Bitv(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];
+        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]
     pub fn test_small_clear() {
-      let b = Bitv(14, true);
-      b.clear();
-      for b.ones |i| {
-          fail!(fmt!("found 1 at %?", i));
-      }
+        let mut b = Bitv::new(14, true);
+        b.clear();
+        for b.ones |i| {
+            fail!(fmt!("found 1 at %?", i));
+        }
     }
 
     #[test]
     pub fn test_big_clear() {
-      let b = Bitv(140, true);
-      b.clear();
-      for b.ones |i| {
-          fail!(fmt!("found 1 at %?", i));
-      }
+        let mut b = Bitv::new(140, true);
+        b.clear();
+        for b.ones |i| {
+            fail!(fmt!("found 1 at %?", i));
+        }
+    }
+
+    #[test]
+    pub 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 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];
+        for a.intersection(&b) |x| {
+            assert *x == expected[i];
+            i += 1
+        }
+        assert 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];
+        for a.difference(&b) |x| {
+            assert *x == expected[i];
+            i += 1
+        }
+        assert 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];
+        for a.symmetric_difference(&b) |x| {
+            assert *x == expected[i];
+            i += 1
+        }
+        assert i == expected.len();
+    }
+
+    #[test]
+    pub 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];
+        for a.union(&b) |x| {
+            assert *x == expected[i];
+            i += 1
+        }
+        assert i == expected.len();
+    }
+
+    #[test]
+    pub 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 a.capacity() == uint::bits;
+    }
+
+    fn rng() -> rand::Rng {
+        let seed = ~[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
+        rand::seeded_rng(&seed)
+    }
+
+    #[bench]
+    pub fn bench_uint_small(b: &mut BenchHarness) {
+        let r = rng();
+        let mut bitv = 0 as uint;
+        do b.iter {
+            bitv |= (1 << ((r.next() as uint) % uint::bits));
+        }
+    }
+
+    #[bench]
+    pub fn bench_small_bitv_small(b: &mut BenchHarness) {
+        let r = rng();
+        let mut bitv = SmallBitv::new(uint::bits);
+        do b.iter {
+            bitv.set((r.next() as uint) % uint::bits, true);
+        }
+    }
+
+    #[bench]
+    pub fn bench_big_bitv_small(b: &mut BenchHarness) {
+        let r = rng();
+        let mut bitv = BigBitv::new(~[0]);
+        do b.iter {
+            bitv.set((r.next() as uint) % uint::bits, true);
+        }
+    }
+
+    #[bench]
+    pub fn bench_big_bitv_big(b: &mut BenchHarness) {
+        let r = rng();
+        let mut storage = ~[];
+        storage.grow(bench_bits / uint::bits, &0);
+        let mut bitv = BigBitv::new(storage);
+        do b.iter {
+            bitv.set((r.next() as uint) % bench_bits, true);
+        }
+    }
+
+    #[bench]
+    pub fn bench_bitv_big(b: &mut BenchHarness) {
+        let r = rng();
+        let mut bitv = Bitv::new(bench_bits, false);
+        do b.iter {
+            bitv.set((r.next() as uint) % bench_bits, true);
+        }
+    }
+
+    #[bench]
+    pub fn bench_bitv_small(b: &mut BenchHarness) {
+        let r = rng();
+        let mut bitv = Bitv::new(uint::bits, false);
+        do b.iter {
+            bitv.set((r.next() as uint) % uint::bits, true);
+        }
+    }
+
+    #[bench]
+    pub fn bench_bitv_set_small(b: &mut BenchHarness) {
+        let r = rng();
+        let mut bitv = BitvSet::new();
+        do b.iter {
+            bitv.insert((r.next() as uint) % uint::bits);
+        }
+    }
+
+    #[bench]
+    pub fn bench_bitv_set_big(b: &mut BenchHarness) {
+        let r = rng();
+        let mut bitv = BitvSet::new();
+        do b.iter {
+            bitv.insert((r.next() as uint) % bench_bits);
+        }
+    }
+
+    #[bench]
+    pub fn bench_bitv_big_union(b: &mut BenchHarness) {
+        let mut b1 = Bitv::new(bench_bits, false);
+        let mut b2 = Bitv::new(bench_bits, false);
+        do b.iter {
+            b1.union(&b2);
+        }
     }
 }