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