14710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# 24710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# this is a rather strict implementation of a bit vector class 34710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# it is accessed the same way as an array of python-ints, except 44710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# the value must be 0 or 1 54710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# 64710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 74710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport sys; rprt = sys.stderr.write #for debugging 84710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 94710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass error(Exception): 104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm pass 114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef _check_value(value): 144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(value) != type(0) or not 0 <= value < 2: 154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise error, 'bitvec() items must have int value 0 or 1' 164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport math 194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef _compute_len(param): 214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm mant, l = math.frexp(float(param)) 224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm bitmask = 1L << l 234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if bitmask <= param: 244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise RuntimeError('(param, l) = %r' % ((param, l),)) 254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while l: 264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm bitmask = bitmask >> 1 274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if param & bitmask: 284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm break 294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm l = l - 1 304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return l 314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef _check_key(len, key): 344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(key) != type(0): 354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise TypeError, 'sequence subscript not int' 364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if key < 0: 374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm key = key + len 384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if not 0 <= key < len: 394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise IndexError, 'list index out of range' 404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return key 414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef _check_slice(len, i, j): 434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #the type is ok, Python already checked that 444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i, j = max(i, 0), min(len, j) 454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if i > j: 464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = j 474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return i, j 484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass BitVec: 514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __init__(self, *params): 534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._data = 0L 544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._len = 0 554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if not len(params): 564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm pass 574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif len(params) == 1: 584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm param, = params 594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(param) == type([]): 604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm value = 0L 614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm bit_mask = 1L 624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for item in param: 634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # strict check 644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #_check_value(item) 654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if item: 664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm value = value | bit_mask 674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm bit_mask = bit_mask << 1 684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._data = value 694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._len = len(param) 704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif type(param) == type(0L): 714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if param < 0: 724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise error, 'bitvec() can\'t handle negative longs' 734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._data = param 744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._len = _compute_len(param) 754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise error, 'bitvec() requires array or long parameter' 774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif len(params) == 2: 784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm param, length = params 794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(param) == type(0L): 804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if param < 0: 814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise error, \ 824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'can\'t handle negative longs' 834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._data = param 844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(length) != type(0): 854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise error, 'bitvec()\'s 2nd parameter must be int' 864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm computed_length = _compute_len(param) 874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if computed_length > length: 884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm print 'warning: bitvec() value is longer than the length indicates, truncating value' 894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._data = self._data & \ 904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ((1L << length) - 1) 914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._len = length 924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise error, 'bitvec() requires array or long parameter' 944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise error, 'bitvec() requires 0 -- 2 parameter(s)' 964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def append(self, item): 994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #_check_value(item) 1004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #self[self._len:self._len] = [item] 1014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self[self._len:self._len] = \ 1024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm BitVec(long(not not item), 1) 1034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def count(self, value): 1064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #_check_value(value) 1074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if value: 1084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm data = self._data 1094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 1104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm data = (~self)._data 1114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm count = 0 1124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while data: 1134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm data, count = data >> 1, count + (data & 1 != 0) 1144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return count 1154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def index(self, value): 1184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #_check_value(value): 1194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if value: 1204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm data = self._data 1214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 1224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm data = (~self)._data 1234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm index = 0 1244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if not data: 1254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise ValueError, 'list.index(x): x not in list' 1264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while not (data & 1): 1274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm data, index = data >> 1, index + 1 1284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return index 1294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def insert(self, index, item): 1324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #_check_value(item) 1334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #self[index:index] = [item] 1344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self[index:index] = BitVec(long(not not item), 1) 1354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def remove(self, value): 1384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm del self[self.index(value)] 1394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def reverse(self): 1424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #ouch, this one is expensive! 1434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #for i in self._len>>1: self[i], self[l-i] = self[l-i], self[i] 1444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm data, result = self._data, 0L 1454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for i in range(self._len): 1464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if not data: 1474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = result << (self._len - i) 1484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm break 1494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result, data = (result << 1) | (data & 1), data >> 1 1504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._data = result 1514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def sort(self): 1544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm c = self.count(1) 1554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._data = ((1L << c) - 1) << (self._len - c) 1564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def copy(self): 1594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return BitVec(self._data, self._len) 1604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def seq(self): 1634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = [] 1644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for i in self: 1654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result.append(i) 1664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result 1674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __repr__(self): 1704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ##rprt('<bitvec class instance object>.' + '__repr__()\n') 1714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 'bitvec(%r, %r)' % (self._data, self._len) 1724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __cmp__(self, other, *rest): 1744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__cmp__%r\n' % (self, (other,) + rest)) 1754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(other) != type(self): 1764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm other = apply(bitvec, (other, ) + rest) 1774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #expensive solution... recursive binary, with slicing 1784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm length = self._len 1794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if length == 0 or other._len == 0: 1804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return cmp(length, other._len) 1814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if length != other._len: 1824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm min_length = min(length, other._len) 1834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return cmp(self[:min_length], other[:min_length]) or \ 1844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm cmp(self[min_length:], other[min_length:]) 1854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #the lengths are the same now... 1864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if self._data == other._data: 1874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0 1884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if length == 1: 1894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return cmp(self[0], other[0]) 1904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 1914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm length = length >> 1 1924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return cmp(self[:length], other[:length]) or \ 1934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm cmp(self[length:], other[length:]) 1944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __len__(self): 1974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__len__()\n' % (self,)) 1984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self._len 1994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __getitem__(self, key): 2014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__getitem__(%r)\n' % (self, key)) 2024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm key = _check_key(self._len, key) 2034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self._data & (1L << key) != 0 2044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __setitem__(self, key, value): 2064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__setitem__(%r, %r)\n' % (self, key, value)) 2074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm key = _check_key(self._len, key) 2084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #_check_value(value) 2094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if value: 2104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._data = self._data | (1L << key) 2114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 2124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._data = self._data & ~(1L << key) 2134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __delitem__(self, key): 2154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__delitem__(%r)\n' % (self, key)) 2164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm key = _check_key(self._len, key) 2174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #el cheapo solution... 2184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._data = self[:key]._data | self[key+1:]._data >> key 2194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._len = self._len - 1 2204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __getslice__(self, i, j): 2224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__getslice__(%r, %r)\n' % (self, i, j)) 2234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i, j = _check_slice(self._len, i, j) 2244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if i >= j: 2254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return BitVec(0L, 0) 2264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if i: 2274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ndata = self._data >> i 2284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 2294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ndata = self._data 2304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm nlength = j - i 2314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if j != self._len: 2324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #we'll have to invent faster variants here 2334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #e.g. mod_2exp 2344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ndata = ndata & ((1L << nlength) - 1) 2354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return BitVec(ndata, nlength) 2364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __setslice__(self, i, j, sequence, *rest): 2384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%s.__setslice__%r\n' % (self, (i, j, sequence) + rest)) 2394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i, j = _check_slice(self._len, i, j) 2404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(sequence) != type(self): 2414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm sequence = apply(bitvec, (sequence, ) + rest) 2424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #sequence is now of our own type 2434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ls_part = self[:i] 2444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ms_part = self[j:] 2454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._data = ls_part._data | \ 2464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ((sequence._data | \ 2474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (ms_part._data << sequence._len)) << ls_part._len) 2484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._len = self._len - j + i + sequence._len 2494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __delslice__(self, i, j): 2514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__delslice__(%r, %r)\n' % (self, i, j)) 2524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i, j = _check_slice(self._len, i, j) 2534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if i == 0 and j == self._len: 2544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._data, self._len = 0L, 0 2554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif i < j: 2564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._data = self[:i]._data | (self[j:]._data >> i) 2574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._len = self._len - j + i 2584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __add__(self, other): 2604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__add__(%r)\n' % (self, other)) 2614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm retval = self.copy() 2624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm retval[self._len:self._len] = other 2634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return retval 2644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __mul__(self, multiplier): 2664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__mul__(%r)\n' % (self, multiplier)) 2674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(multiplier) != type(0): 2684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise TypeError, 'sequence subscript not int' 2694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if multiplier <= 0: 2704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return BitVec(0L, 0) 2714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif multiplier == 1: 2724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self.copy() 2734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #handle special cases all 0 or all 1... 2744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if self._data == 0L: 2754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return BitVec(0L, self._len * multiplier) 2764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif (~self)._data == 0L: 2774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return ~BitVec(0L, self._len * multiplier) 2784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #otherwise el cheapo again... 2794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm retval = BitVec(0L, 0) 2804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while multiplier: 2814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm retval, multiplier = retval + self, multiplier - 1 2824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return retval 2834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __and__(self, otherseq, *rest): 2854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__and__%r\n' % (self, (otherseq,) + rest)) 2864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(otherseq) != type(self): 2874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm otherseq = apply(bitvec, (otherseq, ) + rest) 2884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #sequence is now of our own type 2894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return BitVec(self._data & otherseq._data, \ 2904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm min(self._len, otherseq._len)) 2914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __xor__(self, otherseq, *rest): 2944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__xor__%r\n' % (self, (otherseq,) + rest)) 2954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(otherseq) != type(self): 2964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm otherseq = apply(bitvec, (otherseq, ) + rest) 2974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #sequence is now of our own type 2984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return BitVec(self._data ^ otherseq._data, \ 2994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm max(self._len, otherseq._len)) 3004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __or__(self, otherseq, *rest): 3034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__or__%r\n' % (self, (otherseq,) + rest)) 3044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(otherseq) != type(self): 3054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm otherseq = apply(bitvec, (otherseq, ) + rest) 3064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #sequence is now of our own type 3074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return BitVec(self._data | otherseq._data, \ 3084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm max(self._len, otherseq._len)) 3094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __invert__(self): 3124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__invert__()\n' % (self,)) 3134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return BitVec(~self._data & ((1L << self._len) - 1), \ 3144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._len) 3154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __coerce__(self, otherseq, *rest): 3174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #needed for *some* of the arithmetic operations 3184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm #rprt('%r.__coerce__%r\n' % (self, (otherseq,) + rest)) 3194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(otherseq) != type(self): 3204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm otherseq = apply(bitvec, (otherseq, ) + rest) 3214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self, otherseq 3224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __int__(self): 3244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return int(self._data) 3254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __long__(self): 3274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return long(self._data) 3284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __float__(self): 3304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return float(self._data) 3314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmbitvec = BitVec 334