Home | History | Annotate | Download | only in classes 
      1 #

      2 # this is a rather strict implementation of a bit vector class

      3 # it is accessed the same way as an array of python-ints, except

      4 # the value must be 0 or 1

      5 #

      6 
      7 import sys; rprt = sys.stderr.write #for debugging

      8 
      9 class error(Exception):
     10     pass
     11 
     12 
     13 def _check_value(value):
     14     if type(value) != type(0) or not 0 <= value < 2:
     15         raise error, 'bitvec() items must have int value 0 or 1'
     16 
     17 
     18 import math
     19 
     20 def _compute_len(param):
     21     mant, l = math.frexp(float(param))
     22     bitmask = 1L << l
     23     if bitmask <= param:
     24         raise RuntimeError('(param, l) = %r' % ((param, l),))
     25     while l:
     26         bitmask = bitmask >> 1
     27         if param & bitmask:
     28             break
     29         l = l - 1
     30     return l
     31 
     32 
     33 def _check_key(len, key):
     34     if type(key) != type(0):
     35         raise TypeError, 'sequence subscript not int'
     36     if key < 0:
     37         key = key + len
     38     if not 0 <= key < len:
     39         raise IndexError, 'list index out of range'
     40     return key
     41 
     42 def _check_slice(len, i, j):
     43     #the type is ok, Python already checked that

     44     i, j = max(i, 0), min(len, j)
     45     if i > j:
     46         i = j
     47     return i, j
     48 
     49 
     50 class BitVec:
     51 
     52     def __init__(self, *params):
     53         self._data = 0L
     54         self._len = 0
     55         if not len(params):
     56             pass
     57         elif len(params) == 1:
     58             param, = params
     59             if type(param) == type([]):
     60                 value = 0L
     61                 bit_mask = 1L
     62                 for item in param:
     63                     # strict check

     64                     #_check_value(item)

     65                     if item:
     66                         value = value | bit_mask
     67                     bit_mask = bit_mask << 1
     68                 self._data = value
     69                 self._len = len(param)
     70             elif type(param) == type(0L):
     71                 if param < 0:
     72                     raise error, 'bitvec() can\'t handle negative longs'
     73                 self._data = param
     74                 self._len = _compute_len(param)
     75             else:
     76                 raise error, 'bitvec() requires array or long parameter'
     77         elif len(params) == 2:
     78             param, length = params
     79             if type(param) == type(0L):
     80                 if param < 0:
     81                     raise error, \
     82                       'can\'t handle negative longs'
     83                 self._data = param
     84                 if type(length) != type(0):
     85                     raise error, 'bitvec()\'s 2nd parameter must be int'
     86                 computed_length = _compute_len(param)
     87                 if computed_length > length:
     88                     print 'warning: bitvec() value is longer than the length indicates, truncating value'
     89                     self._data = self._data & \
     90                               ((1L << length) - 1)
     91                 self._len = length
     92             else:
     93                 raise error, 'bitvec() requires array or long parameter'
     94         else:
     95             raise error, 'bitvec() requires 0 -- 2 parameter(s)'
     96 
     97 
     98     def append(self, item):
     99         #_check_value(item)

    100         #self[self._len:self._len] = [item]

    101         self[self._len:self._len] = \
    102                   BitVec(long(not not item), 1)
    103 
    104 
    105     def count(self, value):
    106         #_check_value(value)

    107         if value:
    108             data = self._data
    109         else:
    110             data = (~self)._data
    111         count = 0
    112         while data:
    113             data, count = data >> 1, count + (data & 1 != 0)
    114         return count
    115 
    116 
    117     def index(self, value):
    118         #_check_value(value):

    119         if value:
    120             data = self._data
    121         else:
    122             data = (~self)._data
    123         index = 0
    124         if not data:
    125             raise ValueError, 'list.index(x): x not in list'
    126         while not (data & 1):
    127             data, index = data >> 1, index + 1
    128         return index
    129 
    130 
    131     def insert(self, index, item):
    132         #_check_value(item)

    133         #self[index:index] = [item]

    134         self[index:index] = BitVec(long(not not item), 1)
    135 
    136 
    137     def remove(self, value):
    138         del self[self.index(value)]
    139 
    140 
    141     def reverse(self):
    142         #ouch, this one is expensive!

    143         #for i in self._len>>1: self[i], self[l-i] = self[l-i], self[i]

    144         data, result = self._data, 0L
    145         for i in range(self._len):
    146             if not data:
    147                 result = result << (self._len - i)
    148                 break
    149             result, data = (result << 1) | (data & 1), data >> 1
    150         self._data = result
    151 
    152 
    153     def sort(self):
    154         c = self.count(1)
    155         self._data = ((1L << c) - 1) << (self._len - c)
    156 
    157 
    158     def copy(self):
    159         return BitVec(self._data, self._len)
    160 
    161 
    162     def seq(self):
    163         result = []
    164         for i in self:
    165             result.append(i)
    166         return result
    167 
    168 
    169     def __repr__(self):
    170         ##rprt('<bitvec class instance object>.' + '__repr__()\n')

    171         return 'bitvec(%r, %r)' % (self._data, self._len)
    172 
    173     def __cmp__(self, other, *rest):
    174         #rprt('%r.__cmp__%r\n' % (self, (other,) + rest))

    175         if type(other) != type(self):
    176             other = apply(bitvec, (other, ) + rest)
    177         #expensive solution... recursive binary, with slicing

    178         length = self._len
    179         if length == 0 or other._len == 0:
    180             return cmp(length, other._len)
    181         if length != other._len:
    182             min_length = min(length, other._len)
    183             return cmp(self[:min_length], other[:min_length]) or \
    184                       cmp(self[min_length:], other[min_length:])
    185         #the lengths are the same now...

    186         if self._data == other._data:
    187             return 0
    188         if length == 1:
    189             return cmp(self[0], other[0])
    190         else:
    191             length = length >> 1
    192             return cmp(self[:length], other[:length]) or \
    193                       cmp(self[length:], other[length:])
    194 
    195 
    196     def __len__(self):
    197         #rprt('%r.__len__()\n' % (self,))

    198         return self._len
    199 
    200     def __getitem__(self, key):
    201         #rprt('%r.__getitem__(%r)\n' % (self, key))

    202         key = _check_key(self._len, key)
    203         return self._data & (1L << key) != 0
    204 
    205     def __setitem__(self, key, value):
    206         #rprt('%r.__setitem__(%r, %r)\n' % (self, key, value))

    207         key = _check_key(self._len, key)
    208         #_check_value(value)

    209         if value:
    210             self._data = self._data | (1L << key)
    211         else:
    212             self._data = self._data & ~(1L << key)
    213 
    214     def __delitem__(self, key):
    215         #rprt('%r.__delitem__(%r)\n' % (self, key))

    216         key = _check_key(self._len, key)
    217         #el cheapo solution...

    218         self._data = self[:key]._data | self[key+1:]._data >> key
    219         self._len = self._len - 1
    220 
    221     def __getslice__(self, i, j):
    222         #rprt('%r.__getslice__(%r, %r)\n' % (self, i, j))

    223         i, j = _check_slice(self._len, i, j)
    224         if i >= j:
    225             return BitVec(0L, 0)
    226         if i:
    227             ndata = self._data >> i
    228         else:
    229             ndata = self._data
    230         nlength = j - i
    231         if j != self._len:
    232             #we'll have to invent faster variants here

    233             #e.g. mod_2exp

    234             ndata = ndata & ((1L << nlength) - 1)
    235         return BitVec(ndata, nlength)
    236 
    237     def __setslice__(self, i, j, sequence, *rest):
    238         #rprt('%s.__setslice__%r\n' % (self, (i, j, sequence) + rest))

    239         i, j = _check_slice(self._len, i, j)
    240         if type(sequence) != type(self):
    241             sequence = apply(bitvec, (sequence, ) + rest)
    242         #sequence is now of our own type

    243         ls_part = self[:i]
    244         ms_part = self[j:]
    245         self._data = ls_part._data | \
    246                   ((sequence._data | \
    247                   (ms_part._data << sequence._len)) << ls_part._len)
    248         self._len = self._len - j + i + sequence._len
    249 
    250     def __delslice__(self, i, j):
    251         #rprt('%r.__delslice__(%r, %r)\n' % (self, i, j))

    252         i, j = _check_slice(self._len, i, j)
    253         if i == 0 and j == self._len:
    254             self._data, self._len = 0L, 0
    255         elif i < j:
    256             self._data = self[:i]._data | (self[j:]._data >> i)
    257             self._len = self._len - j + i
    258 
    259     def __add__(self, other):
    260         #rprt('%r.__add__(%r)\n' % (self, other))

    261         retval = self.copy()
    262         retval[self._len:self._len] = other
    263         return retval
    264 
    265     def __mul__(self, multiplier):
    266         #rprt('%r.__mul__(%r)\n' % (self, multiplier))

    267         if type(multiplier) != type(0):
    268             raise TypeError, 'sequence subscript not int'
    269         if multiplier <= 0:
    270             return BitVec(0L, 0)
    271         elif multiplier == 1:
    272             return self.copy()
    273         #handle special cases all 0 or all 1...

    274         if self._data == 0L:
    275             return BitVec(0L, self._len * multiplier)
    276         elif (~self)._data == 0L:
    277             return ~BitVec(0L, self._len * multiplier)
    278         #otherwise el cheapo again...

    279         retval = BitVec(0L, 0)
    280         while multiplier:
    281             retval, multiplier = retval + self, multiplier - 1
    282         return retval
    283 
    284     def __and__(self, otherseq, *rest):
    285         #rprt('%r.__and__%r\n' % (self, (otherseq,) + rest))

    286         if type(otherseq) != type(self):
    287             otherseq = apply(bitvec, (otherseq, ) + rest)
    288         #sequence is now of our own type

    289         return BitVec(self._data & otherseq._data, \
    290                   min(self._len, otherseq._len))
    291 
    292 
    293     def __xor__(self, otherseq, *rest):
    294         #rprt('%r.__xor__%r\n' % (self, (otherseq,) + rest))

    295         if type(otherseq) != type(self):
    296             otherseq = apply(bitvec, (otherseq, ) + rest)
    297         #sequence is now of our own type

    298         return BitVec(self._data ^ otherseq._data, \
    299                   max(self._len, otherseq._len))
    300 
    301 
    302     def __or__(self, otherseq, *rest):
    303         #rprt('%r.__or__%r\n' % (self, (otherseq,) + rest))

    304         if type(otherseq) != type(self):
    305             otherseq = apply(bitvec, (otherseq, ) + rest)
    306         #sequence is now of our own type

    307         return BitVec(self._data | otherseq._data, \
    308                   max(self._len, otherseq._len))
    309 
    310 
    311     def __invert__(self):
    312         #rprt('%r.__invert__()\n' % (self,))

    313         return BitVec(~self._data & ((1L << self._len) - 1), \
    314                   self._len)
    315 
    316     def __coerce__(self, otherseq, *rest):
    317         #needed for *some* of the arithmetic operations

    318         #rprt('%r.__coerce__%r\n' % (self, (otherseq,) + rest))

    319         if type(otherseq) != type(self):
    320             otherseq = apply(bitvec, (otherseq, ) + rest)
    321         return self, otherseq
    322 
    323     def __int__(self):
    324         return int(self._data)
    325 
    326     def __long__(self):
    327         return long(self._data)
    328 
    329     def __float__(self):
    330         return float(self._data)
    331 
    332 
    333 bitvec = BitVec
    334