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) = ' + `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' + `self._data, self._len`
 171
 172         def __cmp__(self, other, *rest):
 173                 #rprt(`self`+'.__cmp__'+`(other, ) + rest`+'\n')
 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(`self`+'.__len__()\n')
 197                 return self._len
 198
 199         def __getitem__(self, key):
 200                 #rprt(`self`+'.__getitem__('+`key`+')\n')
 201                 key = _check_key(self._len, key)
 202                 return self._data & (1L << key) != 0
 203
 204         def __setitem__(self, key, value):
 205                 #rprt(`self`+'.__setitem__'+`key, value`+'\n')
 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(`self`+'.__delitem__('+`key`+')\n')
 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(`self`+'.__getslice__'+`i, j`+'\n')
 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(`self`+'.__setslice__'+`(i, j, sequence) + rest`+'\n')
 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(`self`+'.__delslice__'+`i, j`+'\n')
 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(`self`+'.__add__('+`other`+')\n')
 260                 retval = self.copy()
 261                 retval[self._len:self._len] = other
 262                 return retval
 263
 264         def __mul__(self, multiplier):
 265                 #rprt(`self`+'.__mul__('+`multiplier`+')\n')
 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(`self`+'.__and__'+`(otherseq, ) + rest`+'\n')
 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(`self`+'.__xor__'+`(otherseq, ) + rest`+'\n')
 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(`self`+'.__or__'+`(otherseq, ) + rest`+'\n')
 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(`self`+'.__invert__()\n')
 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(`self`+'.__coerce__'+`(otherseq, ) + rest`+'\n')
 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