Demo/classes/bitvec.py

   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 error = 'bitvec.error'
  10
  11
  12 def _check_value(value):
  13     if type(value) != type(0) or not 0 <= value < 2:
  14         raise error, 'bitvec() items must have int value 0 or 1'
  15
  16
  17 import math
  18
  19 def _compute_len(param):
  20     mant, l = math.frexp(float(param))
  21     bitmask = 1L << l
  22     if bitmask <= param:
  23         raise 'FATAL', '(param, l) = %r' % ((param, l),)
  24     while l:
  25         bitmask = bitmask >> 1
  26         if param & bitmask:
  27             break
  28         l = l - 1
  29     return l
  30
  31
  32 def _check_key(len, key):
  33     if type(key) != type(0):
  34         raise TypeError, 'sequence subscript not int'
  35     if key < 0:
  36         key = key + len
  37     if not 0 <= key < len:
  38         raise IndexError, 'list index out of range'
  39     return key
  40
  41 def _check_slice(len, i, j):
  42     #the type is ok, Python already checked that
  43     i, j = max(i, 0), min(len, j)
  44     if i > j:
  45         i = j
  46     return i, j
  47
  48
  49 class BitVec:
  50
  51     def __init__(self, *params):
  52         self._data = 0L
  53         self._len = 0
  54         if not len(params):
  55             pass
  56         elif len(params) == 1:
  57             param, = params
  58             if type(param) == type([]):
  59                 value = 0L
  60                 bit_mask = 1L
  61                 for item in param:
  62                     # strict check
  63                     #_check_value(item)
  64                     if item:
  65                         value = value | bit_mask
  66                     bit_mask = bit_mask << 1
  67                 self._data = value
  68                 self._len = len(param)
  69             elif type(param) == type(0L):
  70                 if param < 0:
  71                     raise error, 'bitvec() can\'t handle negative longs'
  72                 self._data = param
  73                 self._len = _compute_len(param)
  74             else:
  75                 raise error, 'bitvec() requires array or long parameter'
  76         elif len(params) == 2:
  77             param, length = params
  78             if type(param) == type(0L):
  79                 if param < 0:
  80                     raise error, \
  81                       'can\'t handle negative longs'
  82                 self._data = param
  83                 if type(length) != type(0):
  84                     raise error, 'bitvec()\'s 2nd parameter must be int'
  85                 computed_length = _compute_len(param)
  86                 if computed_length > length:
  87                     print 'warning: bitvec() value is longer than the length indicates, truncating value'
  88                     self._data = self._data & \
  89                               ((1L << length) - 1)
  90                 self._len = length
  91             else:
  92                 raise error, 'bitvec() requires array or long parameter'
  93         else:
  94             raise error, 'bitvec() requires 0 -- 2 parameter(s)'
  95
  96
  97     def append(self, item):
  98         #_check_value(item)
  99         #self[self._len:self._len] = [item]
 100         self[self._len:self._len] = \
 101                   BitVec(long(not not item), 1)
 102
 103
 104     def count(self, value):
 105         #_check_value(value)
 106         if value:
 107             data = self._data
 108         else:
 109             data = (~self)._data
 110         count = 0
 111         while data:
 112             data, count = data >> 1, count + (data & 1 != 0)
 113         return count
 114
 115
 116     def index(self, value):
 117         #_check_value(value):
 118         if value:
 119             data = self._data
 120         else:
 121             data = (~self)._data
 122         index = 0
 123         if not data:
 124             raise ValueError, 'list.index(x): x not in list'
 125         while not (data & 1):
 126             data, index = data >> 1, index + 1
 127         return index
 128
 129
 130     def insert(self, index, item):
 131         #_check_value(item)
 132         #self[index:index] = [item]
 133         self[index:index] = BitVec(long(not not item), 1)
 134
 135
 136     def remove(self, value):
 137         del self[self.index(value)]
 138
 139
 140     def reverse(self):
 141         #ouch, this one is expensive!
 142         #for i in self._len>>1: self[i], self[l-i] = self[l-i], self[i]
 143         data, result = self._data, 0L
 144         for i in range(self._len):
 145             if not data:
 146                 result = result << (self._len - i)
 147                 break
 148             result, data = (result << 1) | (data & 1), data >> 1
 149         self._data = result
 150
 151
 152     def sort(self):
 153         c = self.count(1)
 154         self._data = ((1L << c) - 1) << (self._len - c)
 155
 156
 157     def copy(self):
 158         return BitVec(self._data, self._len)
 159
 160
 161     def seq(self):
 162         result = []
 163         for i in self:
 164             result.append(i)
 165         return result
 166
 167
 168     def __repr__(self):
 169         ##rprt('<bitvec class instance object>.' + '__repr__()\n')
 170         return 'bitvec(%r, %r)' % (self._data, self._len)
 171
 172     def __cmp__(self, other, *rest):
 173         #rprt('%r.__cmp__%r\n' % (self, (other,) + rest))
 174         if type(other) != type(self):
 175             other = apply(bitvec, (other, ) + rest)
 176         #expensive solution... recursive binary, with slicing
 177         length = self._len
 178         if length == 0 or other._len == 0:
 179             return cmp(length, other._len)
 180         if length != other._len:
 181             min_length = min(length, other._len)
 182             return cmp(self[:min_length], other[:min_length]) or \
 183                       cmp(self[min_length:], other[min_length:])
 184         #the lengths are the same now...
 185         if self._data == other._data:
 186             return 0
 187         if length == 1:
 188             return cmp(self[0], other[0])
 189         else:
 190             length = length >> 1
 191             return cmp(self[:length], other[:length]) or \
 192                       cmp(self[length:], other[length:])
 193
 194
 195     def __len__(self):
 196         #rprt('%r.__len__()\n' % (self,))
 197         return self._len
 198
 199     def __getitem__(self, key):
 200         #rprt('%r.__getitem__(%r)\n' % (self, key))
 201         key = _check_key(self._len, key)
 202         return self._data & (1L << key) != 0
 203
 204     def __setitem__(self, key, value):
 205         #rprt('%r.__setitem__(%r, %r)\n' % (self, key, value))
 206         key = _check_key(self._len, key)
 207         #_check_value(value)
 208         if value:
 209             self._data = self._data | (1L << key)
 210         else:
 211             self._data = self._data & ~(1L << key)
 212
 213     def __delitem__(self, key):
 214         #rprt('%r.__delitem__(%r)\n' % (self, key))
 215         key = _check_key(self._len, key)
 216         #el cheapo solution...
 217         self._data = self[:key]._data | self[key+1:]._data >> key
 218         self._len = self._len - 1
 219
 220     def __getslice__(self, i, j):
 221         #rprt('%r.__getslice__(%r, %r)\n' % (self, i, j))
 222         i, j = _check_slice(self._len, i, j)
 223         if i >= j:
 224             return BitVec(0L, 0)
 225         if i:
 226             ndata = self._data >> i
 227         else:
 228             ndata = self._data
 229         nlength = j - i
 230         if j != self._len:
 231             #we'll have to invent faster variants here
 232             #e.g. mod_2exp
 233             ndata = ndata & ((1L << nlength) - 1)
 234         return BitVec(ndata, nlength)
 235
 236     def __setslice__(self, i, j, sequence, *rest):
 237         #rprt('%s.__setslice__%r\n' % (self, (i, j, sequence) + rest))
 238         i, j = _check_slice(self._len, i, j)
 239         if type(sequence) != type(self):
 240             sequence = apply(bitvec, (sequence, ) + rest)
 241         #sequence is now of our own type
 242         ls_part = self[:i]
 243         ms_part = self[j:]
 244         self._data = ls_part._data | \
 245                   ((sequence._data | \
 246                   (ms_part._data << sequence._len)) << ls_part._len)
 247         self._len = self._len - j + i + sequence._len
 248
 249     def __delslice__(self, i, j):
 250         #rprt('%r.__delslice__(%r, %r)\n' % (self, i, j))
 251         i, j = _check_slice(self._len, i, j)
 252         if i == 0 and j == self._len:
 253             self._data, self._len = 0L, 0
 254         elif i < j:
 255             self._data = self[:i]._data | (self[j:]._data >> i)
 256             self._len = self._len - j + i
 257
 258     def __add__(self, other):
 259         #rprt('%r.__add__(%r)\n' % (self, other))
 260         retval = self.copy()
 261         retval[self._len:self._len] = other
 262         return retval
 263
 264     def __mul__(self, multiplier):
 265         #rprt('%r.__mul__(%r)\n' % (self, multiplier))
 266         if type(multiplier) != type(0):
 267             raise TypeError, 'sequence subscript not int'
 268         if multiplier <= 0:
 269             return BitVec(0L, 0)
 270         elif multiplier == 1:
 271             return self.copy()
 272         #handle special cases all 0 or all 1...
 273         if self._data == 0L:
 274             return BitVec(0L, self._len * multiplier)
 275         elif (~self)._data == 0L:
 276             return ~BitVec(0L, self._len * multiplier)
 277         #otherwise el cheapo again...
 278         retval = BitVec(0L, 0)
 279         while multiplier:
 280             retval, multiplier = retval + self, multiplier - 1
 281         return retval
 282
 283     def __and__(self, otherseq, *rest):
 284         #rprt('%r.__and__%r\n' % (self, (otherseq,) + rest))
 285         if type(otherseq) != type(self):
 286             otherseq = apply(bitvec, (otherseq, ) + rest)
 287         #sequence is now of our own type
 288         return BitVec(self._data & otherseq._data, \
 289                   min(self._len, otherseq._len))
 290
 291
 292     def __xor__(self, otherseq, *rest):
 293         #rprt('%r.__xor__%r\n' % (self, (otherseq,) + rest))
 294         if type(otherseq) != type(self):
 295             otherseq = apply(bitvec, (otherseq, ) + rest)
 296         #sequence is now of our own type
 297         return BitVec(self._data ^ otherseq._data, \
 298                   max(self._len, otherseq._len))
 299
 300
 301     def __or__(self, otherseq, *rest):
 302         #rprt('%r.__or__%r\n' % (self, (otherseq,) + rest))
 303         if type(otherseq) != type(self):
 304             otherseq = apply(bitvec, (otherseq, ) + rest)
 305         #sequence is now of our own type
 306         return BitVec(self._data | otherseq._data, \
 307                   max(self._len, otherseq._len))
 308
 309
 310     def __invert__(self):
 311         #rprt('%r.__invert__()\n' % (self,))
 312         return BitVec(~self._data & ((1L << self._len) - 1), \
 313                   self._len)
 314
 315     def __coerce__(self, otherseq, *rest):
 316         #needed for *some* of the arithmetic operations
 317         #rprt('%r.__coerce__%r\n' % (self, (otherseq,) + rest))
 318         if type(otherseq) != type(self):
 319             otherseq = apply(bitvec, (otherseq, ) + rest)
 320         return self, otherseq
 321
 322     def __int__(self):
 323         return int(self._data)
 324
 325     def __long__(self):
 326         return long(self._data)
 327
 328     def __float__(self):
 329         return float(self._data)
 330
 331
 332 bitvec = BitVec