AppPkg/Applications/Python/Python-2.7.2/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 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