# | |
# 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 |