1b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum# 2b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum# this is a rather strict implementation of a bit vector class 3b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum# it is accessed the same way as an array of python-ints, except 4b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum# the value must be 0 or 1 5b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum# 6b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 7b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumimport sys; rprt = sys.stderr.write #for debugging 8b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 9c997f178ed2fe9a636c71be9e62d6b4f46901e1bAndrew M. Kuchlingclass error(Exception): 10c997f178ed2fe9a636c71be9e62d6b4f46901e1bAndrew M. Kuchling pass 11b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 12b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 13b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumdef _check_value(value): 14946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if type(value) != type(0) or not 0 <= value < 2: 15946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling raise error, 'bitvec() items must have int value 0 or 1' 16b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 17b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 18b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumimport math 19b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 20b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumdef _compute_len(param): 21946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling mant, l = math.frexp(float(param)) 22946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling bitmask = 1L << l 23946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if bitmask <= param: 24d9a9c1066c64900a902f5a70b132880e29749eccAndrew M. Kuchling raise RuntimeError('(param, l) = %r' % ((param, l),)) 25946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling while l: 26946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling bitmask = bitmask >> 1 27946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if param & bitmask: 28946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling break 29946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling l = l - 1 30946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return l 31b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 32b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 33b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumdef _check_key(len, key): 34946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if type(key) != type(0): 35946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling raise TypeError, 'sequence subscript not int' 36946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if key < 0: 37946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling key = key + len 38946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if not 0 <= key < len: 39946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling raise IndexError, 'list index out of range' 40946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return key 41b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 42b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumdef _check_slice(len, i, j): 43946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #the type is ok, Python already checked that 44946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling i, j = max(i, 0), min(len, j) 45946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if i > j: 46946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling i = j 47946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return i, j 48946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 49b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 50b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumclass BitVec: 51b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 52946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __init__(self, *params): 53946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._data = 0L 54946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._len = 0 55946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if not len(params): 56946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling pass 57946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling elif len(params) == 1: 58946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling param, = params 59946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if type(param) == type([]): 60946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling value = 0L 61946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling bit_mask = 1L 62946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling for item in param: 63946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling # strict check 64946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #_check_value(item) 65946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if item: 66946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling value = value | bit_mask 67946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling bit_mask = bit_mask << 1 68946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._data = value 69946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._len = len(param) 70946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling elif type(param) == type(0L): 71946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if param < 0: 72946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling raise error, 'bitvec() can\'t handle negative longs' 73946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._data = param 74946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._len = _compute_len(param) 75946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling else: 76946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling raise error, 'bitvec() requires array or long parameter' 77946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling elif len(params) == 2: 78946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling param, length = params 79946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if type(param) == type(0L): 80946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if param < 0: 81946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling raise error, \ 82946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 'can\'t handle negative longs' 83946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._data = param 84946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if type(length) != type(0): 85946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling raise error, 'bitvec()\'s 2nd parameter must be int' 86946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling computed_length = _compute_len(param) 87946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if computed_length > length: 88946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling print 'warning: bitvec() value is longer than the length indicates, truncating value' 89946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._data = self._data & \ 90946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling ((1L << length) - 1) 91946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._len = length 92946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling else: 93946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling raise error, 'bitvec() requires array or long parameter' 94946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling else: 95946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling raise error, 'bitvec() requires 0 -- 2 parameter(s)' 96946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 97946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 98946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def append(self, item): 99946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #_check_value(item) 100946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #self[self._len:self._len] = [item] 101946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self[self._len:self._len] = \ 102946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling BitVec(long(not not item), 1) 103946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 104946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 105946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def count(self, value): 106946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #_check_value(value) 107946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if value: 108946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling data = self._data 109946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling else: 110946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling data = (~self)._data 111946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling count = 0 112946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling while data: 113946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling data, count = data >> 1, count + (data & 1 != 0) 114946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return count 115946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 116946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 117946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def index(self, value): 118946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #_check_value(value): 119946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if value: 120946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling data = self._data 121946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling else: 122946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling data = (~self)._data 123946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling index = 0 124946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if not data: 125946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling raise ValueError, 'list.index(x): x not in list' 126946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling while not (data & 1): 127946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling data, index = data >> 1, index + 1 128946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return index 129946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 130946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 131946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def insert(self, index, item): 132946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #_check_value(item) 133946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #self[index:index] = [item] 134946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self[index:index] = BitVec(long(not not item), 1) 135946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 136946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 137946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def remove(self, value): 138946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling del self[self.index(value)] 139946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 140946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 141946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def reverse(self): 142946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #ouch, this one is expensive! 143946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #for i in self._len>>1: self[i], self[l-i] = self[l-i], self[i] 144946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling data, result = self._data, 0L 145946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling for i in range(self._len): 146946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if not data: 147946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling result = result << (self._len - i) 148946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling break 149946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling result, data = (result << 1) | (data & 1), data >> 1 150946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._data = result 151946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 152946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 153946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def sort(self): 154946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling c = self.count(1) 155946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._data = ((1L << c) - 1) << (self._len - c) 156946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 157946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 158946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def copy(self): 159946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return BitVec(self._data, self._len) 160946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 161946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 162946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def seq(self): 163946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling result = [] 164946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling for i in self: 165946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling result.append(i) 166946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return result 167946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 168946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 169946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __repr__(self): 170946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling ##rprt('<bitvec class instance object>.' + '__repr__()\n') 17170a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald return 'bitvec(%r, %r)' % (self._data, self._len) 172946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 173946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __cmp__(self, other, *rest): 17470a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__cmp__%r\n' % (self, (other,) + rest)) 175946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if type(other) != type(self): 176946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling other = apply(bitvec, (other, ) + rest) 177946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #expensive solution... recursive binary, with slicing 178946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling length = self._len 179946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if length == 0 or other._len == 0: 180946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return cmp(length, other._len) 181946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if length != other._len: 182946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling min_length = min(length, other._len) 183946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return cmp(self[:min_length], other[:min_length]) or \ 184946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling cmp(self[min_length:], other[min_length:]) 185946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #the lengths are the same now... 186946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if self._data == other._data: 187946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return 0 188946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if length == 1: 189946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return cmp(self[0], other[0]) 190946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling else: 191946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling length = length >> 1 192946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return cmp(self[:length], other[:length]) or \ 193946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling cmp(self[length:], other[length:]) 194946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 195946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 196946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __len__(self): 19770a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__len__()\n' % (self,)) 198946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return self._len 199946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 200946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __getitem__(self, key): 20170a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__getitem__(%r)\n' % (self, key)) 202946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling key = _check_key(self._len, key) 203946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return self._data & (1L << key) != 0 204946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 205946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __setitem__(self, key, value): 20670a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__setitem__(%r, %r)\n' % (self, key, value)) 207946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling key = _check_key(self._len, key) 208946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #_check_value(value) 209946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if value: 210946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._data = self._data | (1L << key) 211946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling else: 212946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._data = self._data & ~(1L << key) 213946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 214946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __delitem__(self, key): 21570a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__delitem__(%r)\n' % (self, key)) 216946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling key = _check_key(self._len, key) 217946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #el cheapo solution... 218946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._data = self[:key]._data | self[key+1:]._data >> key 219946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._len = self._len - 1 220946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 221946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __getslice__(self, i, j): 22270a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__getslice__(%r, %r)\n' % (self, i, j)) 223946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling i, j = _check_slice(self._len, i, j) 224946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if i >= j: 225946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return BitVec(0L, 0) 226946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if i: 227946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling ndata = self._data >> i 228946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling else: 229946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling ndata = self._data 230946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling nlength = j - i 231946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if j != self._len: 232946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #we'll have to invent faster variants here 233946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #e.g. mod_2exp 234946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling ndata = ndata & ((1L << nlength) - 1) 235946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return BitVec(ndata, nlength) 236946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 237946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __setslice__(self, i, j, sequence, *rest): 23870a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%s.__setslice__%r\n' % (self, (i, j, sequence) + rest)) 239946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling i, j = _check_slice(self._len, i, j) 240946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if type(sequence) != type(self): 241946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling sequence = apply(bitvec, (sequence, ) + rest) 242946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #sequence is now of our own type 243946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling ls_part = self[:i] 244946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling ms_part = self[j:] 245946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._data = ls_part._data | \ 246946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling ((sequence._data | \ 247946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling (ms_part._data << sequence._len)) << ls_part._len) 248946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._len = self._len - j + i + sequence._len 249946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 250946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __delslice__(self, i, j): 25170a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__delslice__(%r, %r)\n' % (self, i, j)) 252946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling i, j = _check_slice(self._len, i, j) 253946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if i == 0 and j == self._len: 254946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._data, self._len = 0L, 0 255946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling elif i < j: 256946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._data = self[:i]._data | (self[j:]._data >> i) 257946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._len = self._len - j + i 258946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 259946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __add__(self, other): 26070a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__add__(%r)\n' % (self, other)) 261946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling retval = self.copy() 262946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling retval[self._len:self._len] = other 263946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return retval 264946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 265946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __mul__(self, multiplier): 26670a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__mul__(%r)\n' % (self, multiplier)) 267946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if type(multiplier) != type(0): 268946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling raise TypeError, 'sequence subscript not int' 269946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if multiplier <= 0: 270946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return BitVec(0L, 0) 271946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling elif multiplier == 1: 272946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return self.copy() 273946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #handle special cases all 0 or all 1... 274946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if self._data == 0L: 275946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return BitVec(0L, self._len * multiplier) 276946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling elif (~self)._data == 0L: 277946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return ~BitVec(0L, self._len * multiplier) 278946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #otherwise el cheapo again... 279946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling retval = BitVec(0L, 0) 280946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling while multiplier: 281946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling retval, multiplier = retval + self, multiplier - 1 282946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return retval 283946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 284946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __and__(self, otherseq, *rest): 28570a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__and__%r\n' % (self, (otherseq,) + rest)) 286946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if type(otherseq) != type(self): 287946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling otherseq = apply(bitvec, (otherseq, ) + rest) 288946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #sequence is now of our own type 289946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return BitVec(self._data & otherseq._data, \ 290946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling min(self._len, otherseq._len)) 291946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 292946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 293946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __xor__(self, otherseq, *rest): 29470a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__xor__%r\n' % (self, (otherseq,) + rest)) 295946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if type(otherseq) != type(self): 296946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling otherseq = apply(bitvec, (otherseq, ) + rest) 297946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #sequence is now of our own type 298946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return BitVec(self._data ^ otherseq._data, \ 299946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling max(self._len, otherseq._len)) 300946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 301946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 302946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __or__(self, otherseq, *rest): 30370a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__or__%r\n' % (self, (otherseq,) + rest)) 304946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if type(otherseq) != type(self): 305946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling otherseq = apply(bitvec, (otherseq, ) + rest) 306946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #sequence is now of our own type 307946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return BitVec(self._data | otherseq._data, \ 308946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling max(self._len, otherseq._len)) 309946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 310946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 311946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __invert__(self): 31270a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__invert__()\n' % (self,)) 313946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return BitVec(~self._data & ((1L << self._len) - 1), \ 314946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling self._len) 315946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 316946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __coerce__(self, otherseq, *rest): 317946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling #needed for *some* of the arithmetic operations 31870a6b49821a3226f55e9716f32d802d06640cb89Walter Dörwald #rprt('%r.__coerce__%r\n' % (self, (otherseq,) + rest)) 319946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling if type(otherseq) != type(self): 320946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling otherseq = apply(bitvec, (otherseq, ) + rest) 321946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return self, otherseq 322946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 323946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __int__(self): 324946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return int(self._data) 325946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 326946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __long__(self): 327946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return long(self._data) 328946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling 329946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling def __float__(self): 330946c53ed7ff53f38792ac35e5da21de3e0a48ef2Andrew M. Kuchling return float(self._data) 331b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 332b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 3337565b934144012f25e8b22d888572c048f0eb21aGuido van Rossumbitvec = BitVec 334