| # |
| # this is a rather strict implementation of a bit vector class |
| # it is accessed the same way as an array of python-ints, except |
| # the value must be 0 or 1 |
| # |
| |
| import sys; rprt = sys.stderr.write #for debugging |
| |
| class error(Exception): |
| pass |
| |
| |
| def _check_value(value): |
| if type(value) != type(0) or not 0 <= value < 2: |
| raise error, 'bitvec() items must have int value 0 or 1' |
| |
| |
| import math |
| |
| def _compute_len(param): |
| mant, l = math.frexp(float(param)) |
| bitmask = 1L << l |
| if bitmask <= param: |
| raise RuntimeError('(param, l) = %r' % ((param, l),)) |
| while l: |
| bitmask = bitmask >> 1 |
| if param & bitmask: |
| break |
| l = l - 1 |
| return l |
| |
| |
| def _check_key(len, key): |
| if type(key) != type(0): |
| raise TypeError, 'sequence subscript not int' |
| if key < 0: |
| key = key + len |
| if not 0 <= key < len: |
| raise IndexError, 'list index out of range' |
| return key |
| |
| def _check_slice(len, i, j): |
| #the type is ok, Python already checked that |
| i, j = max(i, 0), min(len, j) |
| if i > j: |
| i = j |
| return i, j |
| |
| |
| class BitVec: |
| |
| def __init__(self, *params): |
| self._data = 0L |
| self._len = 0 |
| if not len(params): |
| pass |
| elif len(params) == 1: |
| param, = params |
| if type(param) == type([]): |
| value = 0L |
| bit_mask = 1L |
| for item in param: |
| # strict check |
| #_check_value(item) |
| if item: |
| value = value | bit_mask |
| bit_mask = bit_mask << 1 |
| self._data = value |
| self._len = len(param) |
| elif type(param) == type(0L): |
| if param < 0: |
| raise error, 'bitvec() can\'t handle negative longs' |
| self._data = param |
| self._len = _compute_len(param) |
| else: |
| raise error, 'bitvec() requires array or long parameter' |
| elif len(params) == 2: |
| param, length = params |
| if type(param) == type(0L): |
| if param < 0: |
| raise error, \ |
| 'can\'t handle negative longs' |
| self._data = param |
| if type(length) != type(0): |
| raise error, 'bitvec()\'s 2nd parameter must be int' |
| computed_length = _compute_len(param) |
| if computed_length > length: |
| print 'warning: bitvec() value is longer than the length indicates, truncating value' |
| self._data = self._data & \ |
| ((1L << length) - 1) |
| self._len = length |
| else: |
| raise error, 'bitvec() requires array or long parameter' |
| else: |
| raise error, 'bitvec() requires 0 -- 2 parameter(s)' |
| |
| |
| def append(self, item): |
| #_check_value(item) |
| #self[self._len:self._len] = [item] |
| self[self._len:self._len] = \ |
| BitVec(long(not not item), 1) |
| |
| |
| def count(self, value): |
| #_check_value(value) |
| if value: |
| data = self._data |
| else: |
| data = (~self)._data |
| count = 0 |
| while data: |
| data, count = data >> 1, count + (data & 1 != 0) |
| return count |
| |
| |
| def index(self, value): |
| #_check_value(value): |
| if value: |
| data = self._data |
| else: |
| data = (~self)._data |
| index = 0 |
| if not data: |
| raise ValueError, 'list.index(x): x not in list' |
| while not (data & 1): |
| data, index = data >> 1, index + 1 |
| return index |
| |
| |
| def insert(self, index, item): |
| #_check_value(item) |
| #self[index:index] = [item] |
| self[index:index] = BitVec(long(not not item), 1) |
| |
| |
| def remove(self, value): |
| del self[self.index(value)] |
| |
| |
| def reverse(self): |
| #ouch, this one is expensive! |
| #for i in self._len>>1: self[i], self[l-i] = self[l-i], self[i] |
| data, result = self._data, 0L |
| for i in range(self._len): |
| if not data: |
| result = result << (self._len - i) |
| break |
| result, data = (result << 1) | (data & 1), data >> 1 |
| self._data = result |
| |
| |
| def sort(self): |
| c = self.count(1) |
| self._data = ((1L << c) - 1) << (self._len - c) |
| |
| |
| def copy(self): |
| return BitVec(self._data, self._len) |
| |
| |
| def seq(self): |
| result = [] |
| for i in self: |
| result.append(i) |
| return result |
| |
| |
| def __repr__(self): |
| ##rprt('<bitvec class instance object>.' + '__repr__()\n') |
| return 'bitvec(%r, %r)' % (self._data, self._len) |
| |
| def __cmp__(self, other, *rest): |
| #rprt('%r.__cmp__%r\n' % (self, (other,) + rest)) |
| if type(other) != type(self): |
| other = apply(bitvec, (other, ) + rest) |
| #expensive solution... recursive binary, with slicing |
| length = self._len |
| if length == 0 or other._len == 0: |
| return cmp(length, other._len) |
| if length != other._len: |
| min_length = min(length, other._len) |
| return cmp(self[:min_length], other[:min_length]) or \ |
| cmp(self[min_length:], other[min_length:]) |
| #the lengths are the same now... |
| if self._data == other._data: |
| return 0 |
| if length == 1: |
| return cmp(self[0], other[0]) |
| else: |
| length = length >> 1 |
| return cmp(self[:length], other[:length]) or \ |
| cmp(self[length:], other[length:]) |
| |
| |
| def __len__(self): |
| #rprt('%r.__len__()\n' % (self,)) |
| return self._len |
| |
| def __getitem__(self, key): |
| #rprt('%r.__getitem__(%r)\n' % (self, key)) |
| key = _check_key(self._len, key) |
| return self._data & (1L << key) != 0 |
| |
| def __setitem__(self, key, value): |
| #rprt('%r.__setitem__(%r, %r)\n' % (self, key, value)) |
| key = _check_key(self._len, key) |
| #_check_value(value) |
| if value: |
| self._data = self._data | (1L << key) |
| else: |
| self._data = self._data & ~(1L << key) |
| |
| def __delitem__(self, key): |
| #rprt('%r.__delitem__(%r)\n' % (self, key)) |
| key = _check_key(self._len, key) |
| #el cheapo solution... |
| self._data = self[:key]._data | self[key+1:]._data >> key |
| self._len = self._len - 1 |
| |
| def __getslice__(self, i, j): |
| #rprt('%r.__getslice__(%r, %r)\n' % (self, i, j)) |
| i, j = _check_slice(self._len, i, j) |
| if i >= j: |
| return BitVec(0L, 0) |
| if i: |
| ndata = self._data >> i |
| else: |
| ndata = self._data |
| nlength = j - i |
| if j != self._len: |
| #we'll have to invent faster variants here |
| #e.g. mod_2exp |
| ndata = ndata & ((1L << nlength) - 1) |
| return BitVec(ndata, nlength) |
| |
| def __setslice__(self, i, j, sequence, *rest): |
| #rprt('%s.__setslice__%r\n' % (self, (i, j, sequence) + rest)) |
| i, j = _check_slice(self._len, i, j) |
| if type(sequence) != type(self): |
| sequence = apply(bitvec, (sequence, ) + rest) |
| #sequence is now of our own type |
| ls_part = self[:i] |
| ms_part = self[j:] |
| self._data = ls_part._data | \ |
| ((sequence._data | \ |
| (ms_part._data << sequence._len)) << ls_part._len) |
| self._len = self._len - j + i + sequence._len |
| |
| def __delslice__(self, i, j): |
| #rprt('%r.__delslice__(%r, %r)\n' % (self, i, j)) |
| i, j = _check_slice(self._len, i, j) |
| if i == 0 and j == self._len: |
| self._data, self._len = 0L, 0 |
| elif i < j: |
| self._data = self[:i]._data | (self[j:]._data >> i) |
| self._len = self._len - j + i |
| |
| def __add__(self, other): |
| #rprt('%r.__add__(%r)\n' % (self, other)) |
| retval = self.copy() |
| retval[self._len:self._len] = other |
| return retval |
| |
| def __mul__(self, multiplier): |
| #rprt('%r.__mul__(%r)\n' % (self, multiplier)) |
| if type(multiplier) != type(0): |
| raise TypeError, 'sequence subscript not int' |
| if multiplier <= 0: |
| return BitVec(0L, 0) |
| elif multiplier == 1: |
| return self.copy() |
| #handle special cases all 0 or all 1... |
| if self._data == 0L: |
| return BitVec(0L, self._len * multiplier) |
| elif (~self)._data == 0L: |
| return ~BitVec(0L, self._len * multiplier) |
| #otherwise el cheapo again... |
| retval = BitVec(0L, 0) |
| while multiplier: |
| retval, multiplier = retval + self, multiplier - 1 |
| return retval |
| |
| def __and__(self, otherseq, *rest): |
| #rprt('%r.__and__%r\n' % (self, (otherseq,) + rest)) |
| if type(otherseq) != type(self): |
| otherseq = apply(bitvec, (otherseq, ) + rest) |
| #sequence is now of our own type |
| return BitVec(self._data & otherseq._data, \ |
| min(self._len, otherseq._len)) |
| |
| |
| def __xor__(self, otherseq, *rest): |
| #rprt('%r.__xor__%r\n' % (self, (otherseq,) + rest)) |
| if type(otherseq) != type(self): |
| otherseq = apply(bitvec, (otherseq, ) + rest) |
| #sequence is now of our own type |
| return BitVec(self._data ^ otherseq._data, \ |
| max(self._len, otherseq._len)) |
| |
| |
| def __or__(self, otherseq, *rest): |
| #rprt('%r.__or__%r\n' % (self, (otherseq,) + rest)) |
| if type(otherseq) != type(self): |
| otherseq = apply(bitvec, (otherseq, ) + rest) |
| #sequence is now of our own type |
| return BitVec(self._data | otherseq._data, \ |
| max(self._len, otherseq._len)) |
| |
| |
| def __invert__(self): |
| #rprt('%r.__invert__()\n' % (self,)) |
| return BitVec(~self._data & ((1L << self._len) - 1), \ |
| self._len) |
| |
| def __coerce__(self, otherseq, *rest): |
| #needed for *some* of the arithmetic operations |
| #rprt('%r.__coerce__%r\n' % (self, (otherseq,) + rest)) |
| if type(otherseq) != type(self): |
| otherseq = apply(bitvec, (otherseq, ) + rest) |
| return self, otherseq |
| |
| def __int__(self): |
| return int(self._data) |
| |
| def __long__(self): |
| return long(self._data) |
| |
| def __float__(self): |
| return float(self._data) |
| |
| |
| bitvec = BitVec |
