Commits

Matt Chaput committed 0bb0ff8

Improved bit set implementation, renamed BitVector to Bits, removed BitSet object.

Comments (0)

Files changed (6)

src/whoosh/query.py

 
         def _parent(self, docid):
             comb = self.comb
-            while docid > 0 and docid not in comb:
-                docid -= 1
-            return docid
+            return comb.before(docid + 1)
 
         def _gather(self):
             child = self.child

src/whoosh/searching.py

 from whoosh.compat import (iteritems, itervalues, iterkeys, xrange, text_type,
                            string_type)
 from whoosh.reading import TermNotFound
-from whoosh.support.bitvector import BitSet, Bits
+from whoosh.support.bitvector import Bits
 from whoosh.util import now, lru_cache
 
 
 
     @lru_cache(20)
     def _query_to_comb(self, fq):
-        return BitSet(self.doc_count_all(), source=self.docs_for_query(fq))
+        return Bits(self.doc_count_all(), source=self.docs_for_query(fq))
 
     def _filter_to_comb(self, obj):
         if obj is None:
             return None
-        if isinstance(obj, (set, Bits, BitSet)):
+        if isinstance(obj, (set, Bits)):
             c = obj
         elif isinstance(obj, Results):
             c = obj.docset

src/whoosh/support/bitvector.py

 from whoosh.compat import xrange
 
 
-#: Table of the number of '1' bits in each byte (0-255)
-BYTE_COUNTS = array('B', [
-    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
-    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8])
+# Number of '1' bits in each byte (0-255)
+_1SPERBYTE = array('B', [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2,
+2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
+3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3,
+3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5,
+5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,
+3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5,
+5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
+3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4,
+4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7,
+6, 7, 7, 8])
 
 
 class Bits(object):
     bytes array.
     """
 
-    def __init__(self, maxsize, source=None, bits=None):
+    def __init__(self, source=None, bits=None):
         """
         :param maxsize: the maximum size of the bit array.
         :param source: an iterable of positive integers to add to this set.
             bit array. This is used by some of the object's methods.
         """
 
-        self.size = maxsize
-        self.bcount = None
         if bits:
             self.bits = bits
         else:
-            self.bits = array("B")  #, (0 for _ in xrange(maxsize // 8 + 1)))
+            self.bits = array("B")
 
         if source:
             add = self.add
             for num in source:
                 add(num)
 
-    def trim(self):
+    def bin_digits(self):
+        """Returns a string of ones and zeros (e.g. ``"00010011100"``)
+        representing the underlying bit array. This is sometimes useful when
+        debugging.
+        """
+
+        contains = self.__contains__
+        return "".join("1" if contains(i) else "0"
+                       for i in xrange(0, len(self.bits) * 8))
+
+    def copy(self):
+        """Returns a shallow copy of this object.
+        """
+
+        return self.__class__(bits=array("B", self.bits))
+
+    def clear(self):
+        self.bits = array("B")
+
+    def _trim(self):
         bits = self.bits
         last = len(self.bits) - 1
         while last >= 0 and not bits[last]:
         curlength = len(self.bits)
         newlength = tosize // 8 + 1
         if newlength > curlength:
-            self.bits.extend(0 for _ in xrange(newlength - curlength))
+            self.bits.extend((0,) * (newlength - curlength))
         elif newlength < curlength:
             del self.bits[newlength + 1:]
 
-    def _fill(self):
-        curlength = len(self.bits)
-        fulllength = self.size // 8 + 1
-        if curlength < fulllength:
-            self.bits.extend(0 for _ in xrange(fulllength - curlength))
-        return self
-
-    def saving(self):
-        return (self.size // 8 + 1) - len(self.bits)
+    def _zero_extra_bits(self, size):
+        bits = self.bits
+        spill = size - (len(bits) - 1) * 8
+        if spill:
+            mask = 2 ** spill - 1
+            bits[-1] = bits[-1] & mask
 
     def __eq__(self, other):
-        from itertools import izip
-
         if not isinstance(other, Bits):
             return False
-        if self.size != other.size:
+
+        bits1, bits2 = self.bits, other.bits
+        if len(bits1) != len(bits2):
             return False
-
-        for a, b in izip(self, other):
-            if a != b:
-                return False
-
-        return True
+        return all(bits1[i] == bits2[i] for i in xrange(len(bits1)))
 
     def __neq__(self, other):
         return not self.__eq__(other)
 
-    def bin_digits(self):
-        """Returns a string of ones and zeros (e.g. ``"00010011100"``)
-        representing the underlying bit array. This is sometimes useful when
-        debugging.
-        """
-
-        contains = self.__contains__
-        return "".join("1" if contains(i) else "0"
-                       for i in xrange(0, self.size))
-
     def __repr__(self):
         r = "<Bits %r>" % (list(self),)
         return r
     def __len__(self):
         # This returns the count of "on" bits instead of the size to
         # make Bits exchangeable with a set() object.
-        if self.bcount is None:
-            self.bcount = sum(BYTE_COUNTS[b] for b in self.bits)
-        return self.bcount
+        return sum(_1SPERBYTE[b] for b in self.bits)
 
     def __iter__(self):
         contains = self.__contains__
-        for i in xrange(0, self.size):
+        for i in xrange(0, len(self.bits) * 8):
             if contains(i):
                 yield i
 
 
     __bool__ = __nonzero__
 
-    def __getitem__(self, index):
-        return self.bits[index // 8] & (1 << (index & 7)) != 0
+    def _logic(self, obj, op, other):
+        from whoosh.util import izip_longest
 
-    def __setitem__(self, index, value):
-        if value:
-            self.set(index)
-        else:
-            self.clear(index)
+        objbits = obj.bits
+        for i, (byte1, byte2) in enumerate(izip_longest(objbits, other.bits,
+                                                        fillvalue=0)):
+            value = op(byte1, byte2) & 0xFF
+            if i >= len(objbits):
+                objbits.append(value)
+            else:
+                objbits[i] = value
 
-    def _logic(self, op, other):
-        a, b = self, other
-        if len(a.bits) > len(b.bits):
-            b = Bits(a.size, bits=array("B", b.bits))._fill()
-        elif len(a.bits) < len(b.bits):
-            a = Bits(b.size, bits=array("B", a.bits))._fill()
-        b = Bits(a.size, bits=array('B', map(op, a.bits, b.bits)))
-        return b
+        obj._trim()
+        return obj
 
     def __and__(self, other):
-        if not isinstance(other, Bits):
-            other = Bits(self.size, source=other)
-        return self._logic(operator.__and__, other)
+        return self._logic(self.copy(), operator.__and__, other)
 
     def __or__(self, other):
-        if not isinstance(other, Bits):
-            other = Bits(self.size, source=other)
-        return self._logic(operator.__or__, other)
+        return self._logic(self.copy(), operator.__or__, other)
 
     def __ror__(self, other):
         return self.__or__(other)
         return self.__and__(other)
 
     def __xor__(self, other):
-        if not isinstance(other, Bits):
-            other = Bits(self.size, source=other)
-        return self._logic(operator.__xor__, other)
+        return self._logic(self.copy(), operator.__xor__, other)
 
-    def __invert__(self):
-        return Bits(self.size, bits=array("B", (~b & 0xFF for b in self.bits)))
+    def __sub__(self, other):
+        return self._logic(self.copy(), lambda x, y: x & ~y, other)
+
+    def __rsub__(self, other):
+        return self.__sub__(other)
 
     def __contains__(self, index):
         bits = self.bits
-        bucket = index // 8
+        bucket = index >> 3
         if bucket >= len(bits):
             return False
         byte = bits[bucket]
         return byte and (byte & (1 << (index & 7)))
 
     def add(self, index):
-        """Turns the bit at the given position on."""
-
         bits = self.bits
-        bucket = index // 8
+        bucket = index >> 3
         if bucket >= len(bits):
             self._resize(index)
         bits[bucket] |= 1 << (index & 7)
-        self.bcount = None
 
     def remove(self, index):
-        """Turns the bit at the given position off."""
-
         bits = self.bits
-        bucket = index // 8
+        bucket = index >> 3
         self.bits[bucket] &= ~(1 << (index & 7))
         if bucket == len(bits) - 1:
-            self.trim()
-        self.bcount = None
+            self._trim()
 
     def update(self, iterable):
-        """Takes an iterable of integers representing positions, and turns
-        on the bits at those positions.
-        """
-
         add = self.add
         for index in iterable:
             add(index)
 
+    def union(self, other):
+        if isinstance(other, Bits):
+            return self | other
+        b = self.copy()
+        b.update(other)
+        return b
+
+    def intersection(self, other):
+        if isinstance(other, Bits):
+            return self & other
+        return Bits(source=(n for n in self if n in other))
+
+    def difference(self, other):
+        if isinstance(other, Bits):
+            return self - other
+        return Bits(source=(n for n in self if n not in other))
+
+    def intersection_update(self, other):
+        if isinstance(other, Bits):
+            return self._logic(self, operator.__and__, other)
+        remove = self.remove
+        for n in self:
+            if n not in other:
+                remove(n)
+
+    def difference_update(self, other):
+        if isinstance(other, Bits):
+            return self._logic(self, lambda x, y: x & ~y, other)
+        remove = self.remove
+        for n in other:
+            remove(n)
+
+    def invert(self, size):
+        b = self.copy()
+        b.invert_update(size)
+        return b
+
+    def invert_update(self, size):
+        self._resize(size)
+        bits = self.bits
+        for i in xrange(len(bits)):
+            # On the last byte, mask the result to just the "spillover" bits
+            bits[i] = ~bits[i] & 0xFF
+        self._zero_extra_bits(size)
+
+    def isdisjoint(self, other):
+        from itertools import izip
+
+        if isinstance(other, Bits):
+            return not any(a & b for a, b in izip(self.bits, other.bits))
+        else:
+            contains = self.__contains__
+            for n in other:
+                if contains(n):
+                    return False
+            return True
+
     def after(self, index):
         """Returns the next integer in the set after ``index``, or None.
         """
 
         bits = self.bits
-        size = min(len(bits) * 8, self.size)
+        size = len(bits) * 8
         if index >= size:
             return None
         elif index < 0:
         """
 
         bits = self.bits
-        size = min(len(bits) * 8, self.size)
+        size = len(bits) * 8
         if index <= 0:
             return None
         elif index >= size:
 
         return None
 
-    def union(self, other):
-        return self.__or__(other)
 
-    def intersection(self, other):
-        return self.__and__(other)
 
-class BitSet(object):
-    """A set-like object for holding positive integers. It is dynamically
-    backed by either a set or a Bits object depending on how many numbers are
-    in the set, to save memory.
-    
-    Provides ``add``, ``remove``, ``union``, ``intersection``,
-    ``__contains__``, ``__len__``, ``__iter__``, ``__and__``, ``__or__``, and
-    methods.
-    """
-
-    def __init__(self, size, source=None):
-        self.size = size
-
-        self._back = ()
-        self._switch(size < 256)
-
-        if source:
-            for num in source:
-                self.add(num)
-
-    def _switch(self, toset):
-        if toset:
-            self._back = set(self._back)
-            self.add = self._set_add
-            self.remove = self._back.remove
-        else:
-            self._back = Bits(self.size, source=self._back)
-            self.add = self._back.add
-            self.remove = self._vec_remove
-
-        self.update = self._back.update
-
-    def __contains__(self, n):
-        return n in self._back
-
-    def __repr__(self):
-        return "<%s %s/%s>" % (self.__class__.__name__, len(self._back),
-                               self.size)
-
-    def __len__(self):
-        return len(self._back)
-
-    def __iter__(self):
-        return self._back.__iter__()
-
-    def as_set(self):
-        return frozenset(self._back)
-
-    def union(self, other):
-        return self.__or__(other)
-
-    def intersection(self, other):
-        return self.__and__(other)
-
-    def invert(self):
-        return BitSet(self.size, (x for x in xrange(self.size)
-                                  if x not in self))
-
-    def __and__(self, other):
-        return BitSet(self.size, self._back.intersection(other))
-
-    def __or__(self, other):
-        return BitSet(self.size, self._back.union(other))
-
-    def __rand__(self, other):
-        return self.__and__(other)
-
-    def __ror__(self, other):
-        return self.__or__(other)
-
-    def __invert__(self):
-        return self.invert()
-
-    def _set_add(self, num):
-        self._back.add(num)
-        if len(self._back) * 4 > self.size // 8 + 32:
-            self._switch(False)
-
-    def _vec_remove(self, num):
-        self._back.clear(num)
-        if len(self._back) * 4 < self.size // 8 - 32:
-            self._switch(True)

src/whoosh/util.py

             else:
                 return
 
+try:
+    from itertools import izip_longest  #@UnusedImport
+except ImportError:
+    from itertools import chain, izip, repeat
+    # This function was only added to itertools in 2.6...
+    def izip_longest(*args, **kwds):
+        fillvalue = kwds.get('fillvalue')
+        def sentinel(counter=([fillvalue]*(len(args) - 1)).pop):
+            yield counter()
+        fillers = repeat(fillvalue)
+        iters = [chain(it, sentinel(), fillers) for it in args]
+        try:
+            for tup in izip(*iters):
+                yield tup
+        except IndexError:
+            pass
 
 try:
     from operator import methodcaller  #@UnusedImport

tests/test_bits.py

+from nose.tools import assert_equal  #@UnresolvedImport
+
+from whoosh.support.bitvector import Bits
+
+
+def test_bit_basics():
+    b = Bits()
+    assert not b
+
+    b.update([0, 2, 4, 6, 7])
+    assert b
+    assert_equal([(n in b) for n in range(10)],
+                 [True, False, True, False, True, False, True, True, False,
+                  False])
+
+    b.add(9)
+    assert 9 in b
+    assert_equal(len(b), 6)
+
+    assert_equal(list(b.invert(10)), [1, 3, 5, 8])
+
+    b.remove(6)
+    assert_equal(list(b), [0, 2, 4, 7, 9])
+    assert_equal(len(b), 5)
+
+def test_len():
+    b = Bits()
+    b.add(3)
+    b.add(5)
+    b.add(1024)
+    assert_equal(len(b), 3)
+    b.add(5)
+    assert_equal(len(b), 3)
+    b.remove(1000)
+    assert_equal(len(b), 3)
+    b.remove(5)
+    assert_equal(len(b), 2)
+
+def test_union():
+    assert_equal(Bits([2, 4, 5]) | Bits([3, 9]), Bits([2, 3, 4, 5, 9]))
+    b = Bits([2, 4, 5])
+    b.update([3, 9])
+    assert_equal(list(b), [2, 3, 4, 5, 9])
+    b = Bits([2, 4, 5])
+    b.update(Bits([3, 9]))
+    assert_equal(list(b), [2, 3, 4, 5, 9])
+    b = Bits([1, 2])
+    b.update([1, 5, 9])
+    assert_equal(list(b), [1, 2, 5, 9])
+
+def test_intersection():
+    assert_equal(Bits([2, 4, 5]) & Bits([3, 9]), Bits())
+    assert_equal(Bits([2, 4, 5]) & Bits([4, 5, 9]), Bits([4, 5]))
+    b = Bits([2, 4, 5])
+    assert_equal(b.intersection([4, 5, 9]), Bits([4, 5]))
+    b.intersection_update([4, 5, 9])
+    assert_equal(list(b), [4, 5])
+    b = Bits([2, 4, 5])
+    b.intersection_update(Bits([4, 5, 9]))
+    assert_equal(list(b), [4, 5])
+
+def test_difference():
+    assert_equal(Bits([1, 3, 50, 72]) - Bits([3, 72]), Bits([1, 50]))
+    assert_equal(list(Bits([1, 3, 50, 72]).difference([3, 72])), [1, 50])
+    b = Bits([1, 3, 50, 72])
+    b.difference_update(Bits([3, 72]))
+    assert_equal(list(b), [1, 50])
+    b = Bits([1, 3, 50, 72])
+    b.difference_update([3, 72])
+    assert_equal(list(b), [1, 50])
+
+def test_xor():
+    assert_equal(Bits([2, 4, 5]) ^ Bits([4, 5, 9]), Bits([2, 9]))
+
+def test_copy():
+    b = Bits([1, 5, 100, 60])
+    assert_equal(b, b.copy())
+
+def test_clear():
+    b = Bits([1, 5, 100, 60])
+    b.clear()
+    assert_equal(list(b), [])
+
+def test_isdisjoint():
+    b = Bits([1, 7, 20, 100])
+    assert b.isdisjoint(Bits([2, 8, 25]))
+    assert b.isdisjoint([2, 8, 25])
+    assert not b.isdisjoint(Bits([2, 7, 25]))
+    assert not b.isdisjoint([1, 8, 25])
+
+def test_before_after():
+    b = Bits([10, 11, 30, 50, 80])
+    assert_equal(b.after(0), 10)
+    assert_equal(b.after(7), 10)
+    assert_equal(b.after(8), 10)
+    assert_equal(b.after(10), 11)
+    assert_equal(b.after(11), 30)
+    assert_equal(b.after(30), 50)
+    assert_equal(b.after(33), 50)
+    assert_equal(b.after(38), 50)
+    assert_equal(b.after(41), 50)
+    assert_equal(b.after(42), 50)
+    assert_equal(b.after(45), 50)
+    assert_equal(b.after(47), 50)
+    assert_equal(b.after(50), 80)
+    assert_equal(b.after(80), None)
+
+    assert_equal(b.before(0), None)
+    assert_equal(b.before(99), 80)
+    assert_equal(b.before(81), 80)
+    assert_equal(b.before(80), 50)
+    assert_equal(b.before(50), 30)
+    assert_equal(b.before(48), 30)
+    assert_equal(b.before(46), 30)
+    assert_equal(b.before(45), 30)
+    assert_equal(b.before(44), 30)
+    assert_equal(b.before(42), 30)
+    assert_equal(b.before(38), 30)
+    assert_equal(b.before(36), 30)
+    assert_equal(b.before(34), 30)
+    assert_equal(b.before(33), 30)
+    assert_equal(b.before(32), 30)
+    assert_equal(b.before(30), 11)
+    assert_equal(b.before(11), 10)
+    assert_equal(b.before(10), None)
+
+    b = Bits([7])
+    assert_equal(b.after(0), 7)
+    b = Bits([8])
+    assert_equal(b.after(0), 8)
+    b = Bits([9])
+    assert_equal(b.after(0), 9)
+
+    b = Bits([7])
+    assert_equal(b.before(16), 7)
+    b = Bits([8])
+    assert_equal(b.before(16), 8)
+    b = Bits([9])
+    assert_equal(b.before(16), 9)
+
+    b = Bits([49])
+    assert_equal(b.after(0), 49)

tests/test_misc.py

     test.cache_clear()
     assert_equal(test.cache_info(), (0, 0, 5, 0))
 
-def test_bits():
-    from whoosh.support.bitvector import Bits
 
-    b = Bits(10)
-    assert not b
 
-    b.update([0, 2, 4, 6, 7])
-    assert b
-    assert_equal([(n in b) for n in range(10)],
-                 [True, False, True, False, True, False, True, True, False,
-                  False])
-
-    b.add(9)
-    assert 9 in b
-    assert_equal(len(b), 6)
-
-    assert_equal(list(~b), [1, 3, 5, 8])
-
-    b.remove(6)
-    assert_equal(list(b), [0, 2, 4, 7, 9])
-    assert_equal(len(b), 5)
-
-    assert_equal(Bits(10, [2, 4, 5]) | Bits(10, [3, 9]),
-                 Bits(10, [2, 3, 4, 5, 9]))
-    assert_equal(Bits(10, [2, 4, 5]) & Bits(10, [3, 9]), Bits(10))
-    assert_equal(Bits(10, [2, 4, 5]) & Bits(10, [4, 5, 9]), Bits(10, [4, 5]))
-    assert_equal(Bits(10, [2, 4, 5]) ^ Bits(10, [4, 5, 9]), Bits(10, [2, 9]))
-
-    b = Bits(10, [1, 2])
-    b.update([1, 5, 9])
-    assert_equal(list(b), [1, 2, 5, 9])
-
-    b = Bits(100, [10, 11, 30, 50, 80])
-    assert_equal(b.after(0), 10)
-    assert_equal(b.after(7), 10)
-    assert_equal(b.after(8), 10)
-    assert_equal(b.after(10), 11)
-    assert_equal(b.after(11), 30)
-    assert_equal(b.after(30), 50)
-    assert_equal(b.after(33), 50)
-    assert_equal(b.after(38), 50)
-    assert_equal(b.after(41), 50)
-    assert_equal(b.after(42), 50)
-    assert_equal(b.after(45), 50)
-    assert_equal(b.after(47), 50)
-    assert_equal(b.after(50), 80)
-    assert_equal(b.after(80), None)
-
-    assert_equal(b.before(0), None)
-    assert_equal(b.before(99), 80)
-    assert_equal(b.before(81), 80)
-    assert_equal(b.before(80), 50)
-    assert_equal(b.before(50), 30)
-    assert_equal(b.before(48), 30)
-    assert_equal(b.before(46), 30)
-    assert_equal(b.before(45), 30)
-    assert_equal(b.before(44), 30)
-    assert_equal(b.before(42), 30)
-    assert_equal(b.before(38), 30)
-    assert_equal(b.before(36), 30)
-    assert_equal(b.before(34), 30)
-    assert_equal(b.before(33), 30)
-    assert_equal(b.before(32), 30)
-    assert_equal(b.before(30), 11)
-    assert_equal(b.before(11), 10)
-    assert_equal(b.before(10), None)
-
-    b = Bits(16, [7])
-    assert_equal(b.after(0), 7)
-    b = Bits(16, [8])
-    assert_equal(b.after(0), 8)
-    b = Bits(16, [9])
-    assert_equal(b.after(0), 9)
-
-    b = Bits(16, [7])
-    assert_equal(b.before(16), 7)
-    b = Bits(16, [8])
-    assert_equal(b.before(16), 8)
-    b = Bits(16, [9])
-    assert_equal(b.before(16), 9)
-
-    b = Bits(50, [49])
-    assert_equal(b.after(0), 49)
-
-