extract libcollections tests into libcollectionstest

3 files changed, 1182 insertions, 0 deletions

diff --git a/src/libcollectionstest/bit/mod.rs b/src/libcollectionstest/bit/mod.rs
new file mode 100644
index 00000000000..8e06524f2e5
--- /dev/null
+++ b/src/libcollectionstest/bit/mod.rs
@@ -0,0 +1,12 @@
+// 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.
+
+mod set;
+mod vec;
diff --git a/src/libcollectionstest/bit/set.rs b/src/libcollectionstest/bit/set.rs
new file mode 100644
index 00000000000..4b4995d5fa7
--- /dev/null
+++ b/src/libcollectionstest/bit/set.rs
@@ -0,0 +1,441 @@
+// 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.
+
+use std::cmp::Ordering::{Equal, Greater, Less};
+use std::collections::{BitSet, BitVec};
+use std::iter::range_step;
+
+#[test]
+fn test_bit_set_show() {
+    let mut s = BitSet::new();
+    s.insert(1);
+    s.insert(10);
+    s.insert(50);
+    s.insert(2);
+    assert_eq!("{1, 2, 10, 50}", format!("{:?}", s));
+}
+
+#[test]
+fn test_bit_set_from_usizes() {
+    let usizes = vec![0, 2, 2, 3];
+    let a: BitSet = usizes.into_iter().collect();
+    let mut b = BitSet::new();
+    b.insert(0);
+    b.insert(2);
+    b.insert(3);
+    assert_eq!(a, b);
+}
+
+#[test]
+fn test_bit_set_iterator() {
+    let usizes = vec![0, 2, 2, 3];
+    let bit_vec: BitSet = usizes.into_iter().collect();
+
+    let idxs: Vec<_> = bit_vec.iter().collect();
+    assert_eq!(idxs, [0, 2, 3]);
+
+    let long: BitSet = (0..10000).filter(|&n| n % 2 == 0).collect();
+    let real: Vec<_> = range_step(0, 10000, 2).collect();
+
+    let idxs: Vec<_> = long.iter().collect();
+    assert_eq!(idxs, real);
+}
+
+#[test]
+fn test_bit_set_frombit_vec_init() {
+    let bools = [true, false];
+    let lengths = [10, 64, 100];
+    for &b in &bools {
+        for &l in &lengths {
+            let bitset = BitSet::from_bit_vec(BitVec::from_elem(l, b));
+            assert_eq!(bitset.contains(&1), b);
+            assert_eq!(bitset.contains(&(l-1)), b);
+            assert!(!bitset.contains(&l));
+        }
+    }
+}
+
+#[test]
+fn test_bit_vec_masking() {
+    let b = BitVec::from_elem(140, true);
+    let mut bs = BitSet::from_bit_vec(b);
+    assert!(bs.contains(&139));
+    assert!(!bs.contains(&140));
+    assert!(bs.insert(150));
+    assert!(!bs.contains(&140));
+    assert!(!bs.contains(&149));
+    assert!(bs.contains(&150));
+    assert!(!bs.contains(&151));
+}
+
+#[test]
+fn test_bit_set_basic() {
+    let mut b = BitSet::new();
+    assert!(b.insert(3));
+    assert!(!b.insert(3));
+    assert!(b.contains(&3));
+    assert!(b.insert(4));
+    assert!(!b.insert(4));
+    assert!(b.contains(&3));
+    assert!(b.insert(400));
+    assert!(!b.insert(400));
+    assert!(b.contains(&400));
+    assert_eq!(b.len(), 3);
+}
+
+#[test]
+fn test_bit_set_intersection() {
+    let mut a = BitSet::new();
+    let mut b = BitSet::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 expected = [3, 5, 11, 77];
+    let actual: Vec<_> = a.intersection(&b).collect();
+    assert_eq!(actual, expected);
+}
+
+#[test]
+fn test_bit_set_difference() {
+    let mut a = BitSet::new();
+    let mut b = BitSet::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 expected = [1, 5, 500];
+    let actual: Vec<_> = a.difference(&b).collect();
+    assert_eq!(actual, expected);
+}
+
+#[test]
+fn test_bit_set_symmetric_difference() {
+    let mut a = BitSet::new();
+    let mut b = BitSet::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 expected = [1, 5, 11, 14, 220];
+    let actual: Vec<_> = a.symmetric_difference(&b).collect();
+    assert_eq!(actual, expected);
+}
+
+#[test]
+fn test_bit_set_union() {
+    let mut a = BitSet::new();
+    let mut b = BitSet::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!(a.insert(200));
+
+    assert!(b.insert(1));
+    assert!(b.insert(5));
+    assert!(b.insert(9));
+    assert!(b.insert(13));
+    assert!(b.insert(19));
+
+    let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160, 200];
+    let actual: Vec<_> = a.union(&b).collect();
+    assert_eq!(actual, expected);
+}
+
+#[test]
+fn test_bit_set_subset() {
+    let mut set1 = BitSet::new();
+    let mut set2 = BitSet::new();
+
+    assert!(set1.is_subset(&set2)); //  {}  {}
+    set2.insert(100);
+    assert!(set1.is_subset(&set2)); //  {}  { 1 }
+    set2.insert(200);
+    assert!(set1.is_subset(&set2)); //  {}  { 1, 2 }
+    set1.insert(200);
+    assert!(set1.is_subset(&set2)); //  { 2 }  { 1, 2 }
+    set1.insert(300);
+    assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 1, 2 }
+    set2.insert(300);
+    assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3 }
+    set2.insert(400);
+    assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3, 4 }
+    set2.remove(&100);
+    assert!(set1.is_subset(&set2)); // { 2, 3 }  { 2, 3, 4 }
+    set2.remove(&300);
+    assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 2, 4 }
+    set1.remove(&300);
+    assert!(set1.is_subset(&set2)); // { 2 }  { 2, 4 }
+}
+
+#[test]
+fn test_bit_set_is_disjoint() {
+    let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+    let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01000000]));
+    let c = BitSet::new();
+    let d = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00110000]));
+
+    assert!(!a.is_disjoint(&d));
+    assert!(!d.is_disjoint(&a));
+
+    assert!(a.is_disjoint(&b));
+    assert!(a.is_disjoint(&c));
+    assert!(b.is_disjoint(&a));
+    assert!(b.is_disjoint(&c));
+    assert!(c.is_disjoint(&a));
+    assert!(c.is_disjoint(&b));
+}
+
+#[test]
+fn test_bit_set_union_with() {
+    //a should grow to include larger elements
+    let mut a = BitSet::new();
+    a.insert(0);
+    let mut b = BitSet::new();
+    b.insert(5);
+    let expected = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10000100]));
+    a.union_with(&b);
+    assert_eq!(a, expected);
+
+    // Standard
+    let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+    let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100010]));
+    let c = a.clone();
+    a.union_with(&b);
+    b.union_with(&c);
+    assert_eq!(a.len(), 4);
+    assert_eq!(b.len(), 4);
+}
+
+#[test]
+fn test_bit_set_intersect_with() {
+    // Explicitly 0'ed bits
+    let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+    let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000]));
+    let c = a.clone();
+    a.intersect_with(&b);
+    b.intersect_with(&c);
+    assert!(a.is_empty());
+    assert!(b.is_empty());
+
+    // Uninitialized bits should behave like 0's
+    let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+    let mut b = BitSet::new();
+    let c = a.clone();
+    a.intersect_with(&b);
+    b.intersect_with(&c);
+    assert!(a.is_empty());
+    assert!(b.is_empty());
+
+    // Standard
+    let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+    let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100010]));
+    let c = a.clone();
+    a.intersect_with(&b);
+    b.intersect_with(&c);
+    assert_eq!(a.len(), 2);
+    assert_eq!(b.len(), 2);
+}
+
+#[test]
+fn test_bit_set_difference_with() {
+    // Explicitly 0'ed bits
+    let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000]));
+    let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+    a.difference_with(&b);
+    assert!(a.is_empty());
+
+    // Uninitialized bits should behave like 0's
+    let mut a = BitSet::new();
+    let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11111111]));
+    a.difference_with(&b);
+    assert!(a.is_empty());
+
+    // Standard
+    let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+    let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100010]));
+    let c = a.clone();
+    a.difference_with(&b);
+    b.difference_with(&c);
+    assert_eq!(a.len(), 1);
+    assert_eq!(b.len(), 1);
+}
+
+#[test]
+fn test_bit_set_symmetric_difference_with() {
+    //a should grow to include larger elements
+    let mut a = BitSet::new();
+    a.insert(0);
+    a.insert(1);
+    let mut b = BitSet::new();
+    b.insert(1);
+    b.insert(5);
+    let expected = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10000100]));
+    a.symmetric_difference_with(&b);
+    assert_eq!(a, expected);
+
+    let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+    let b = BitSet::new();
+    let c = a.clone();
+    a.symmetric_difference_with(&b);
+    assert_eq!(a, c);
+
+    // Standard
+    let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11100010]));
+    let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101010]));
+    let c = a.clone();
+    a.symmetric_difference_with(&b);
+    b.symmetric_difference_with(&c);
+    assert_eq!(a.len(), 2);
+    assert_eq!(b.len(), 2);
+}
+
+#[test]
+fn test_bit_set_eq() {
+    let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+    let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000]));
+    let c = BitSet::new();
+
+    assert!(a == a);
+    assert!(a != b);
+    assert!(a != c);
+    assert!(b == b);
+    assert!(b == c);
+    assert!(c == c);
+}
+
+#[test]
+fn test_bit_set_cmp() {
+    let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+    let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000]));
+    let c = BitSet::new();
+
+    assert_eq!(a.cmp(&b), Greater);
+    assert_eq!(a.cmp(&c), Greater);
+    assert_eq!(b.cmp(&a), Less);
+    assert_eq!(b.cmp(&c), Equal);
+    assert_eq!(c.cmp(&a), Less);
+    assert_eq!(c.cmp(&b), Equal);
+}
+
+#[test]
+fn test_bit_vec_remove() {
+    let mut a = BitSet::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));
+    a.shrink_to_fit();
+}
+
+#[test]
+fn test_bit_vec_clone() {
+    let mut a = BitSet::new();
+
+    assert!(a.insert(1));
+    assert!(a.insert(100));
+    assert!(a.insert(1000));
+
+    let mut b = a.clone();
+
+    assert!(a == b);
+
+    assert!(b.remove(&1));
+    assert!(a.contains(&1));
+
+    assert!(a.remove(&1000));
+    assert!(b.contains(&1000));
+}
+
+mod bench {
+    use std::collections::{BitSet, BitVec};
+    use std::rand::{Rng, self};
+    use std::u32;
+
+    use test::{Bencher, black_box};
+
+    const BENCH_BITS : usize = 1 << 14;
+
+    fn rng() -> rand::IsaacRng {
+        let seed: &[_] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
+        rand::SeedableRng::from_seed(seed)
+    }
+
+    #[bench]
+    fn bench_bit_vecset_small(b: &mut Bencher) {
+        let mut r = rng();
+        let mut bit_vec = BitSet::new();
+        b.iter(|| {
+            for _ in 0..100 {
+                bit_vec.insert((r.next_u32() as usize) % u32::BITS as usize);
+            }
+            black_box(&bit_vec);
+        });
+    }
+
+    #[bench]
+    fn bench_bit_vecset_big(b: &mut Bencher) {
+        let mut r = rng();
+        let mut bit_vec = BitSet::new();
+        b.iter(|| {
+            for _ in 0..100 {
+                bit_vec.insert((r.next_u32() as usize) % BENCH_BITS);
+            }
+            black_box(&bit_vec);
+        });
+    }
+
+    #[bench]
+    fn bench_bit_vecset_iter(b: &mut Bencher) {
+        let bit_vec = BitSet::from_bit_vec(BitVec::from_fn(BENCH_BITS,
+                                              |idx| {idx % 3 == 0}));
+        b.iter(|| {
+            let mut sum = 0;
+            for idx in &bit_vec {
+                sum += idx as usize;
+            }
+            sum
+        })
+    }
+}
diff --git a/src/libcollectionstest/bit/vec.rs b/src/libcollectionstest/bit/vec.rs
new file mode 100644
index 00000000000..3826974d1ad
--- /dev/null
+++ b/src/libcollectionstest/bit/vec.rs
@@ -0,0 +1,729 @@
+// 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.
+
+use std::collections::BitVec;
+use std::u32;
+
+#[test]
+fn test_to_str() {
+    let zerolen = BitVec::new();
+    assert_eq!(format!("{:?}", zerolen), "");
+
+    let eightbits = BitVec::from_elem(8, false);
+    assert_eq!(format!("{:?}", eightbits), "00000000")
+}
+
+#[test]
+fn test_0_elements() {
+    let act = BitVec::new();
+    let exp = Vec::new();
+    assert!(act.eq_vec(&exp));
+    assert!(act.none() && act.all());
+}
+
+#[test]
+fn test_1_element() {
+    let mut act = BitVec::from_elem(1, false);
+    assert!(act.eq_vec(&[false]));
+    assert!(act.none() && !act.all());
+    act = BitVec::from_elem(1, true);
+    assert!(act.eq_vec(&[true]));
+    assert!(!act.none() && act.all());
+}
+
+#[test]
+fn test_2_elements() {
+    let mut b = BitVec::from_elem(2, false);
+    b.set(0, true);
+    b.set(1, false);
+    assert_eq!(format!("{:?}", b), "10");
+    assert!(!b.none() && !b.all());
+}
+
+#[test]
+fn test_10_elements() {
+    let mut act;
+    // all 0
+
+    act = BitVec::from_elem(10, false);
+    assert!((act.eq_vec(
+                &[false, false, false, false, false, false, false, false, false, false])));
+    assert!(act.none() && !act.all());
+    // all 1
+
+    act = BitVec::from_elem(10, true);
+    assert!((act.eq_vec(&[true, true, true, true, true, true, true, true, true, true])));
+    assert!(!act.none() && act.all());
+    // mixed
+
+    act = BitVec::from_elem(10, false);
+    act.set(0, true);
+    act.set(1, true);
+    act.set(2, true);
+    act.set(3, true);
+    act.set(4, true);
+    assert!((act.eq_vec(&[true, true, true, true, true, false, false, false, false, false])));
+    assert!(!act.none() && !act.all());
+    // mixed
+
+    act = BitVec::from_elem(10, false);
+    act.set(5, true);
+    act.set(6, true);
+    act.set(7, true);
+    act.set(8, true);
+    act.set(9, true);
+    assert!((act.eq_vec(&[false, false, false, false, false, true, true, true, true, true])));
+    assert!(!act.none() && !act.all());
+    // mixed
+
+    act = BitVec::from_elem(10, false);
+    act.set(0, true);
+    act.set(3, true);
+    act.set(6, true);
+    act.set(9, true);
+    assert!((act.eq_vec(&[true, false, false, true, false, false, true, false, false, true])));
+    assert!(!act.none() && !act.all());
+}
+
+#[test]
+fn test_31_elements() {
+    let mut act;
+    // all 0
+
+    act = BitVec::from_elem(31, 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]));
+    assert!(act.none() && !act.all());
+    // all 1
+
+    act = BitVec::from_elem(31, 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]));
+    assert!(!act.none() && act.all());
+    // mixed
+
+    act = BitVec::from_elem(31, false);
+    act.set(0, true);
+    act.set(1, true);
+    act.set(2, true);
+    act.set(3, true);
+    act.set(4, true);
+    act.set(5, true);
+    act.set(6, true);
+    act.set(7, 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]));
+    assert!(!act.none() && !act.all());
+    // mixed
+
+    act = BitVec::from_elem(31, false);
+    act.set(16, true);
+    act.set(17, true);
+    act.set(18, true);
+    act.set(19, true);
+    act.set(20, true);
+    act.set(21, true);
+    act.set(22, true);
+    act.set(23, 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]));
+    assert!(!act.none() && !act.all());
+    // mixed
+
+    act = BitVec::from_elem(31, false);
+    act.set(24, true);
+    act.set(25, true);
+    act.set(26, true);
+    act.set(27, true);
+    act.set(28, true);
+    act.set(29, true);
+    act.set(30, 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]));
+    assert!(!act.none() && !act.all());
+    // mixed
+
+    act = BitVec::from_elem(31, false);
+    act.set(3, true);
+    act.set(17, true);
+    act.set(30, 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]));
+    assert!(!act.none() && !act.all());
+}
+
+#[test]
+fn test_32_elements() {
+    let mut act;
+    // all 0
+
+    act = BitVec::from_elem(32, 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]));
+    assert!(act.none() && !act.all());
+    // all 1
+
+    act = BitVec::from_elem(32, 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]));
+    assert!(!act.none() && act.all());
+    // mixed
+
+    act = BitVec::from_elem(32, false);
+    act.set(0, true);
+    act.set(1, true);
+    act.set(2, true);
+    act.set(3, true);
+    act.set(4, true);
+    act.set(5, true);
+    act.set(6, true);
+    act.set(7, 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]));
+    assert!(!act.none() && !act.all());
+    // mixed
+
+    act = BitVec::from_elem(32, false);
+    act.set(16, true);
+    act.set(17, true);
+    act.set(18, true);
+    act.set(19, true);
+    act.set(20, true);
+    act.set(21, true);
+    act.set(22, true);
+    act.set(23, 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]));
+    assert!(!act.none() && !act.all());
+    // mixed
+
+    act = BitVec::from_elem(32, false);
+    act.set(24, true);
+    act.set(25, true);
+    act.set(26, true);
+    act.set(27, true);
+    act.set(28, true);
+    act.set(29, true);
+    act.set(30, true);
+    act.set(31, 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]));
+    assert!(!act.none() && !act.all());
+    // mixed
+
+    act = BitVec::from_elem(32, false);
+    act.set(3, true);
+    act.set(17, true);
+    act.set(30, true);
+    act.set(31, 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]));
+    assert!(!act.none() && !act.all());
+}
+
+#[test]
+fn test_33_elements() {
+    let mut act;
+    // all 0
+
+    act = BitVec::from_elem(33, 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]));
+    assert!(act.none() && !act.all());
+    // all 1
+
+    act = BitVec::from_elem(33, 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]));
+    assert!(!act.none() && act.all());
+    // mixed
+
+    act = BitVec::from_elem(33, false);
+    act.set(0, true);
+    act.set(1, true);
+    act.set(2, true);
+    act.set(3, true);
+    act.set(4, true);
+    act.set(5, true);
+    act.set(6, true);
+    act.set(7, 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]));
+    assert!(!act.none() && !act.all());
+    // mixed
+
+    act = BitVec::from_elem(33, false);
+    act.set(16, true);
+    act.set(17, true);
+    act.set(18, true);
+    act.set(19, true);
+    act.set(20, true);
+    act.set(21, true);
+    act.set(22, true);
+    act.set(23, 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]));
+    assert!(!act.none() && !act.all());
+    // mixed
+
+    act = BitVec::from_elem(33, false);
+    act.set(24, true);
+    act.set(25, true);
+    act.set(26, true);
+    act.set(27, true);
+    act.set(28, true);
+    act.set(29, true);
+    act.set(30, true);
+    act.set(31, 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]));
+    assert!(!act.none() && !act.all());
+    // mixed
+
+    act = BitVec::from_elem(33, false);
+    act.set(3, true);
+    act.set(17, true);
+    act.set(30, true);
+    act.set(31, true);
+    act.set(32, 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]));
+    assert!(!act.none() && !act.all());
+}
+
+#[test]
+fn test_equal_differing_sizes() {
+    let v0 = BitVec::from_elem(10, false);
+    let v1 = BitVec::from_elem(11, false);
+    assert!(v0 != v1);
+}
+
+#[test]
+fn test_equal_greatly_differing_sizes() {
+    let v0 = BitVec::from_elem(10, false);
+    let v1 = BitVec::from_elem(110, false);
+    assert!(v0 != v1);
+}
+
+#[test]
+fn test_equal_sneaky_small() {
+    let mut a = BitVec::from_elem(1, false);
+    a.set(0, true);
+
+    let mut b = BitVec::from_elem(1, true);
+    b.set(0, true);
+
+    assert_eq!(a, b);
+}
+
+#[test]
+fn test_equal_sneaky_big() {
+    let mut a = BitVec::from_elem(100, false);
+    for i in 0..100 {
+        a.set(i, true);
+    }
+
+    let mut b = BitVec::from_elem(100, true);
+    for i in 0..100 {
+        b.set(i, true);
+    }
+
+    assert_eq!(a, b);
+}
+
+#[test]
+fn test_from_bytes() {
+    let bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
+    let str = concat!("10110110", "00000000", "11111111");
+    assert_eq!(format!("{:?}", bit_vec), str);
+}
+
+#[test]
+fn test_to_bytes() {
+    let mut bv = BitVec::from_elem(3, true);
+    bv.set(1, false);
+    assert_eq!(bv.to_bytes(), [0b10100000]);
+
+    let mut bv = BitVec::from_elem(9, false);
+    bv.set(2, true);
+    bv.set(8, true);
+    assert_eq!(bv.to_bytes(), [0b00100000, 0b10000000]);
+}
+
+#[test]
+fn test_from_bools() {
+    let bools = vec![true, false, true, true];
+    let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
+    assert_eq!(format!("{:?}", bit_vec), "1011");
+}
+
+#[test]
+fn test_to_bools() {
+    let bools = vec![false, false, true, false, false, true, true, false];
+    assert_eq!(BitVec::from_bytes(&[0b00100110]).iter().collect::<Vec<bool>>(), bools);
+}
+
+#[test]
+fn test_bit_vec_iterator() {
+    let bools = vec![true, false, true, true];
+    let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
+
+    assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), bools);
+
+    let long: Vec<_> = (0..10000).map(|i| i % 2 == 0).collect();
+    let bit_vec: BitVec = long.iter().map(|n| *n).collect();
+    assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), long)
+}
+
+#[test]
+fn test_small_difference() {
+    let mut b1 = BitVec::from_elem(3, false);
+    let mut b2 = BitVec::from_elem(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 = BitVec::from_elem(100, false);
+    let mut b2 = BitVec::from_elem(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 = BitVec::from_elem(14, true);
+    assert!(!b.none() && b.all());
+    b.clear();
+    assert!(b.none() && !b.all());
+}
+
+#[test]
+fn test_big_clear() {
+    let mut b = BitVec::from_elem(140, true);
+    assert!(!b.none() && b.all());
+    b.clear();
+    assert!(b.none() && !b.all());
+}
+
+#[test]
+fn test_bit_vec_lt() {
+    let mut a = BitVec::from_elem(5, false);
+    let mut b = BitVec::from_elem(5, false);
+
+    assert!(!(a < b) && !(b < a));
+    b.set(2, true);
+    assert!(a < b);
+    a.set(3, true);
+    assert!(a < b);
+    a.set(2, true);
+    assert!(!(a < b) && b < a);
+    b.set(0, true);
+    assert!(a < b);
+}
+
+#[test]
+fn test_ord() {
+    let mut a = BitVec::from_elem(5, false);
+    let mut b = BitVec::from_elem(5, false);
+
+    assert!(a <= b && a >= b);
+    a.set(1, true);
+    assert!(a > b && a >= b);
+    assert!(b < a && b <= a);
+    b.set(1, true);
+    b.set(2, true);
+    assert!(b > a && b >= a);
+    assert!(a < b && a <= b);
+}
+
+
+#[test]
+fn test_small_bit_vec_tests() {
+    let v = BitVec::from_bytes(&[0]);
+    assert!(!v.all());
+    assert!(!v.any());
+    assert!(v.none());
+
+    let v = BitVec::from_bytes(&[0b00010100]);
+    assert!(!v.all());
+    assert!(v.any());
+    assert!(!v.none());
+
+    let v = BitVec::from_bytes(&[0xFF]);
+    assert!(v.all());
+    assert!(v.any());
+    assert!(!v.none());
+}
+
+#[test]
+fn test_big_bit_vec_tests() {
+    let v = BitVec::from_bytes(&[ // 88 bits
+        0, 0, 0, 0,
+        0, 0, 0, 0,
+        0, 0, 0]);
+    assert!(!v.all());
+    assert!(!v.any());
+    assert!(v.none());
+
+    let v = BitVec::from_bytes(&[ // 88 bits
+        0, 0, 0b00010100, 0,
+        0, 0, 0, 0b00110100,
+        0, 0, 0]);
+    assert!(!v.all());
+    assert!(v.any());
+    assert!(!v.none());
+
+    let v = BitVec::from_bytes(&[ // 88 bits
+        0xFF, 0xFF, 0xFF, 0xFF,
+        0xFF, 0xFF, 0xFF, 0xFF,
+        0xFF, 0xFF, 0xFF]);
+    assert!(v.all());
+    assert!(v.any());
+    assert!(!v.none());
+}
+
+#[test]
+fn test_bit_vec_push_pop() {
+    let mut s = BitVec::from_elem(5 * u32::BITS as usize - 2, false);
+    assert_eq!(s.len(), 5 * u32::BITS as usize - 2);
+    assert_eq!(s[5 * u32::BITS as usize - 3], false);
+    s.push(true);
+    s.push(true);
+    assert_eq!(s[5 * u32::BITS as usize - 2], true);
+    assert_eq!(s[5 * u32::BITS as usize - 1], true);
+    // Here the internal vector will need to be extended
+    s.push(false);
+    assert_eq!(s[5 * u32::BITS as usize], false);
+    s.push(false);
+    assert_eq!(s[5 * u32::BITS as usize + 1], false);
+    assert_eq!(s.len(), 5 * u32::BITS as usize + 2);
+    // Pop it all off
+    assert_eq!(s.pop(), Some(false));
+    assert_eq!(s.pop(), Some(false));
+    assert_eq!(s.pop(), Some(true));
+    assert_eq!(s.pop(), Some(true));
+    assert_eq!(s.len(), 5 * u32::BITS as usize - 2);
+}
+
+#[test]
+fn test_bit_vec_truncate() {
+    let mut s = BitVec::from_elem(5 * u32::BITS as usize, true);
+
+    assert_eq!(s, BitVec::from_elem(5 * u32::BITS as usize, true));
+    assert_eq!(s.len(), 5 * u32::BITS as usize);
+    s.truncate(4 * u32::BITS as usize);
+    assert_eq!(s, BitVec::from_elem(4 * u32::BITS as usize, true));
+    assert_eq!(s.len(), 4 * u32::BITS as usize);
+    // Truncating to a size > s.len() should be a noop
+    s.truncate(5 * u32::BITS as usize);
+    assert_eq!(s, BitVec::from_elem(4 * u32::BITS as usize, true));
+    assert_eq!(s.len(), 4 * u32::BITS as usize);
+    s.truncate(3 * u32::BITS as usize - 10);
+    assert_eq!(s, BitVec::from_elem(3 * u32::BITS as usize - 10, true));
+    assert_eq!(s.len(), 3 * u32::BITS as usize - 10);
+    s.truncate(0);
+    assert_eq!(s, BitVec::from_elem(0, true));
+    assert_eq!(s.len(), 0);
+}
+
+#[test]
+fn test_bit_vec_reserve() {
+    let mut s = BitVec::from_elem(5 * u32::BITS as usize, true);
+    // Check capacity
+    assert!(s.capacity() >= 5 * u32::BITS as usize);
+    s.reserve(2 * u32::BITS as usize);
+    assert!(s.capacity() >= 7 * u32::BITS as usize);
+    s.reserve(7 * u32::BITS as usize);
+    assert!(s.capacity() >= 12 * u32::BITS as usize);
+    s.reserve_exact(7 * u32::BITS as usize);
+    assert!(s.capacity() >= 12 * u32::BITS as usize);
+    s.reserve(7 * u32::BITS as usize + 1);
+    assert!(s.capacity() >= 12 * u32::BITS as usize + 1);
+    // Check that length hasn't changed
+    assert_eq!(s.len(), 5 * u32::BITS as usize);
+    s.push(true);
+    s.push(false);
+    s.push(true);
+    assert_eq!(s[5 * u32::BITS as usize - 1], true);
+    assert_eq!(s[5 * u32::BITS as usize - 0], true);
+    assert_eq!(s[5 * u32::BITS as usize + 1], false);
+    assert_eq!(s[5 * u32::BITS as usize + 2], true);
+}
+
+#[test]
+fn test_bit_vec_grow() {
+    let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010]);
+    bit_vec.grow(32, true);
+    assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
+                                 0xFF, 0xFF, 0xFF, 0xFF]));
+    bit_vec.grow(64, false);
+    assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
+                                 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0]));
+    bit_vec.grow(16, true);
+    assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
+                                 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF]));
+}
+
+#[test]
+fn test_bit_vec_extend() {
+    let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
+    let ext = BitVec::from_bytes(&[0b01001001, 0b10010010, 0b10111101]);
+    bit_vec.extend(ext.iter());
+    assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111,
+                                 0b01001001, 0b10010010, 0b10111101]));
+}
+
+mod bench {
+    use std::collections::BitVec;
+    use std::u32;
+    use std::rand::{Rng, self};
+
+    use test::{Bencher, black_box};
+
+    const BENCH_BITS : usize = 1 << 14;
+
+    fn rng() -> rand::IsaacRng {
+        let seed: &[_] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
+        rand::SeedableRng::from_seed(seed)
+    }
+
+    #[bench]
+    fn bench_usize_small(b: &mut Bencher) {
+        let mut r = rng();
+        let mut bit_vec = 0 as usize;
+        b.iter(|| {
+            for _ in 0..100 {
+                bit_vec |= 1 << ((r.next_u32() as usize) % u32::BITS as usize);
+            }
+            black_box(&bit_vec);
+        });
+    }
+
+    #[bench]
+    fn bench_bit_set_big_fixed(b: &mut Bencher) {
+        let mut r = rng();
+        let mut bit_vec = BitVec::from_elem(BENCH_BITS, false);
+        b.iter(|| {
+            for _ in 0..100 {
+                bit_vec.set((r.next_u32() as usize) % BENCH_BITS, true);
+            }
+            black_box(&bit_vec);
+        });
+    }
+
+    #[bench]
+    fn bench_bit_set_big_variable(b: &mut Bencher) {
+        let mut r = rng();
+        let mut bit_vec = BitVec::from_elem(BENCH_BITS, false);
+        b.iter(|| {
+            for _ in 0..100 {
+                bit_vec.set((r.next_u32() as usize) % BENCH_BITS, r.gen());
+            }
+            black_box(&bit_vec);
+        });
+    }
+
+    #[bench]
+    fn bench_bit_set_small(b: &mut Bencher) {
+        let mut r = rng();
+        let mut bit_vec = BitVec::from_elem(u32::BITS as usize, false);
+        b.iter(|| {
+            for _ in 0..100 {
+                bit_vec.set((r.next_u32() as usize) % u32::BITS as usize, true);
+            }
+            black_box(&bit_vec);
+        });
+    }
+
+    #[bench]
+    fn bench_bit_vec_big_union(b: &mut Bencher) {
+        let mut b1 = BitVec::from_elem(BENCH_BITS, false);
+        let b2 = BitVec::from_elem(BENCH_BITS, false);
+        b.iter(|| {
+            b1.union(&b2)
+        })
+    }
+
+    #[bench]
+    fn bench_bit_vec_small_iter(b: &mut Bencher) {
+        let bit_vec = BitVec::from_elem(u32::BITS as usize, false);
+        b.iter(|| {
+            let mut sum = 0;
+            for _ in 0..10 {
+                for pres in &bit_vec {
+                    sum += pres as usize;
+                }
+            }
+            sum
+        })
+    }
+
+    #[bench]
+    fn bench_bit_vec_big_iter(b: &mut Bencher) {
+        let bit_vec = BitVec::from_elem(BENCH_BITS, false);
+        b.iter(|| {
+            let mut sum = 0;
+            for pres in &bit_vec {
+                sum += pres as usize;
+            }
+            sum
+        })
+    }
+}