auto merge of #7703 : sfackler/rust/bitv, r=alexcrichton

Switched Bitv and BitvSet to external iterators. They still use some internal iterators internally (ha).

Derived clone for all Bitv types.

Removed indirection in BitvVariant. It previously held a unique pointer to the appropriate Bitv struct, even though those structs are the size of a pointer themselves. BitvVariant is the same size (16 bytes) as it was previously.

1 files changed, 149 insertions, 51 deletions

diff --git a/src/libextra/bitv.rs b/src/libextra/bitv.rs
index 33a50f4e9ab..168d6a39916 100644
--- a/src/libextra/bitv.rs
+++ b/src/libextra/bitv.rs
@@ -17,6 +17,7 @@ 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
@@ -107,6 +108,7 @@ impl SmallBitv {
     pub fn negate(&mut self) { self.bits = !self.bits; }
 }
 
+#[deriving(Clone)]
 struct BigBitv {
     storage: ~[uint]
 }
@@ -212,11 +214,13 @@ impl BigBitv {
     }
 }
 
-enum BitvVariant { Big(~BigBitv), Small(~SmallBitv) }
+#[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)
     rep: BitvVariant,
@@ -237,20 +241,20 @@ impl Bitv {
         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)
+              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)
+              Union      => s.union(s1,      self.nbits),
+              Intersect  => s.intersect(s1,  self.nbits),
+              Assign     => s.become(s1,     self.nbits),
+              Difference => s.difference(s1, self.nbits)
             }
           }
         }
@@ -261,14 +265,14 @@ impl Bitv {
 impl Bitv {
     pub fn new(nbits: uint, init: bool) -> Bitv {
         let rep = if nbits <= uint::bits {
-            Small(~SmallBitv::new(if init {!0} else {0}))
+            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 {!0u} else {0u};
             let s = vec::from_elem(nelems, elem);
-            Big(~BigBitv::new(s))
+            Big(BigBitv::new(s))
         };
         Bitv {rep: rep, nbits: nbits}
     }
@@ -337,11 +341,11 @@ impl Bitv {
       if self.nbits != v1.nbits { return false; }
       match self.rep {
         Small(ref b) => match v1.rep {
-          Small(ref b1) => b.equals(*b1, self.nbits),
+          Small(ref b1) => b.equals(b1, self.nbits),
           _ => false
         },
         Big(ref s) => match v1.rep {
-          Big(ref s1) => s.equals(*s1, self.nbits),
+          Big(ref s1) => s.equals(s1, self.nbits),
           Small(_) => return false
         }
       }
@@ -392,20 +396,15 @@ impl Bitv {
       match self.rep {
         Small(ref b) => b.is_true(self.nbits),
         _ => {
-          for self.each() |i| { if !i { return false; } }
+          for self.iter().advance |i| { if !i { return false; } }
           true
         }
       }
     }
 
     #[inline]
-    pub fn each(&self, f: &fn(bool) -> bool) -> bool {
-        let mut i = 0;
-        while i < self.nbits {
-            if !f(self.get(i)) { return false; }
-            i += 1;
-        }
-        return true;
+    pub fn iter<'a>(&'a self) -> BitvIterator<'a> {
+        BitvIterator {bitv: self, next_idx: 0}
     }
 
     /// Returns true if all bits are 0
@@ -413,7 +412,7 @@ impl Bitv {
       match self.rep {
         Small(ref b) => b.is_false(self.nbits),
         Big(_) => {
-          for self.each() |i| { if i { return false; } }
+          for self.iter().advance |i| { if i { return false; } }
           true
         }
       }
@@ -477,7 +476,7 @@ impl Bitv {
      */
      pub fn to_str(&self) -> ~str {
         let mut rs = ~"";
-        for self.each() |i| {
+        for self.iter().advance |i| {
             if i {
                 rs.push_char('1');
             } else {
@@ -509,24 +508,6 @@ impl Bitv {
 
 }
 
-impl Clone for Bitv {
-    /// Makes a copy of a bitvector
-    #[inline]
-    fn clone(&self) -> Bitv {
-        match self.rep {
-          Small(ref b) => {
-            Bitv{nbits: self.nbits, rep: Small(~SmallBitv{bits: b.bits})}
-          }
-          Big(ref b) => {
-            let mut st = vec::from_elem(self.nbits / uint::bits + 1, 0u);
-            let len = st.len();
-            for uint::range(0, len) |i| { st[i] = b.storage[i]; };
-            Bitv{nbits: self.nbits, rep: Big(~BigBitv{storage: st})}
-          }
-        }
-    }
-}
-
 /**
  * Transform a byte-vector into a bitv. Each byte becomes 8 bits,
  * with the most significant bits of each byte coming first. Each
@@ -580,12 +561,37 @@ fn iterate_bits(base: uint, bits: uint, f: &fn(uint) -> bool) -> bool {
     return true;
 }
 
+/// An iterator for Bitv
+pub struct BitvIterator<'self> {
+    priv bitv: &'self Bitv,
+    priv next_idx: uint
+}
+
+impl<'self> Iterator<bool> for BitvIterator<'self> {
+    #[inline]
+    fn next(&mut self) -> Option<bool> {
+        if self.next_idx < self.bitv.nbits {
+            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.bitv.nbits - self.next_idx;
+        (rem, Some(rem))
+    }
+}
+
 /// 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,
 
@@ -609,8 +615,8 @@ impl BitvSet {
         }
         let Bitv{rep, _} = bitv;
         match rep {
-            Big(~b) => BitvSet{ size: size, bitv: b },
-            Small(~SmallBitv{bits}) =>
+            Big(b) => BitvSet{ size: size, bitv: b },
+            Small(SmallBitv{bits}) =>
                 BitvSet{ size: size, bitv: BigBitv{ storage: ~[bits] } },
         }
     }
@@ -623,7 +629,7 @@ impl BitvSet {
     pub fn unwrap(self) -> Bitv {
         let cap = self.capacity();
         let BitvSet{bitv, _} = self;
-        return Bitv{ nbits:cap, rep: Big(~bitv) };
+        return Bitv{ nbits:cap, rep: Big(bitv) };
     }
 
     #[inline]
@@ -670,13 +676,8 @@ impl BitvSet {
         self.other_op(other, |w1, w2| w1 ^ w2);
     }
 
-    pub fn each(&self, blk: &fn(v: &uint) -> bool) -> bool {
-        for self.bitv.storage.iter().enumerate().advance |(i, &w)| {
-            if !iterate_bits(i * uint::bits, w, |b| blk(&b)) {
-                return false;
-            }
-        }
-        return true;
+    pub fn iter<'a>(&'a self) -> BitvSetIterator<'a> {
+        BitvSetIterator {set: self, next_idx: 0}
     }
 }
 
@@ -860,6 +861,31 @@ impl BitvSet {
     }
 }
 
+pub struct BitvSetIterator<'self> {
+    priv set: &'self BitvSet,
+    priv next_idx: uint
+}
+
+impl<'self> Iterator<uint> for BitvSetIterator<'self> {
+    #[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;
@@ -1242,6 +1268,25 @@ mod tests {
     }
 
     #[test]
+    fn test_bitv_iterator() {
+        let bools = [true, false, true, true];
+        let bitv = from_bools(bools);
+
+        for bitv.iter().zip(bools.iter()).advance |(act, &ex)| {
+            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_small_difference() {
         let mut b1 = Bitv::new(3, false);
         let mut b2 = Bitv::new(3, false);
@@ -1417,6 +1462,25 @@ mod tests {
         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::IsaacRng::new_seeded(seed)
@@ -1504,4 +1568,38 @@ mod tests {
             b1.union(&b2);
         }
     }
+
+    #[bench]
+    fn bench_btv_small_iter(b: &mut BenchHarness) {
+        let bitv = Bitv::new(uint::bits, false);
+        do b.iter {
+            let mut sum = 0;
+            for bitv.iter().advance |pres| {
+                sum += pres as uint;
+            }
+        }
+    }
+
+    #[bench]
+    fn bench_bitv_big_iter(b: &mut BenchHarness) {
+        let bitv = Bitv::new(BENCH_BITS, false);
+        do b.iter {
+            let mut sum = 0;
+            for bitv.iter().advance |pres| {
+                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}));
+        do b.iter {
+            let mut sum = 0;
+            for bitv.iter().advance |idx| {
+                sum += idx;
+            }
+        }
+    }
 }