bitvec.py revision b6957e434fab0b901cb2c8fafeba77f9ae7a653f
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 9b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumerror = 'bitvec.error' 10b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 11b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 12b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumdef _check_value(value): 13b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if type(value) != type(0) or not 0 <= value < 2: 14b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum raise error, 'bitvec() items must have int value 0 or 1' 15b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 16b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 17b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumimport math 18b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 19b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumdef _compute_len(param): 20b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum mant, l = math.frexp(float(param)) 21b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum bitmask = 1L << l 22b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if bitmask <= param: 23b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum raise 'FATAL', '(param, l) = ' + `param, l` 24b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum while l: 25b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum bitmask = bitmask >> 1 26b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if param & bitmask: 27b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum break 28b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum l = l - 1 29b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return l 30b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 31b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 32b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumdef _check_key(len, key): 33b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if type(key) != type(0): 34b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum raise TypeError, 'sequence subscript not int' 35b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if key < 0: 36b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum key = key + len 37b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if not 0 <= key < len: 38b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum raise IndexError, 'list index out of range' 39b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return key 40b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 41b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumdef _check_slice(len, i, j): 42b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #the type is ok, Python already checked that 43b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum i, j = max(i, 0), min(len, j) 44b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if i > j: 45b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum i = j 46b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return i, j 47b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 48b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 49b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumclass BitVec: 50b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 51b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def init(self, *params): 52b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data = 0L 53b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._len = 0 54b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if not len(params): 55b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum pass 56b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum elif len(params) == 1: 57b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum param, = params 58b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if type(param) == type([]): 59b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum value = 0L 60b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum bit_mask = 1L 61b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum for item in param: 62b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum # strict check 63b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #_check_value(item) 64b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if item: 65b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum value = value | bit_mask 66b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum bit_mask = bit_mask << 1 67b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data = value 68b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._len = len(param) 69b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum elif type(param) == type(0L): 70b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if param < 0: 71b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum raise error, 'bitvec() can\'t handle negative longs' 72b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data = param 73b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._len = _compute_len(param) 74b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum else: 75b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum raise error, 'bitvec() requires array or long parameter' 76b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum elif len(params) == 2: 77b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum param, length = params 78b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if type(param) == type(0L): 79b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if param < 0: 80b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum raise error, \ 81b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 'can\'t handle negative longs' 82b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data = param 83b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if type(length) != type(0): 84b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum raise error, 'bitvec()\'s 2nd parameter must be int' 85b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum computed_length = _compute_len(param) 86b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if computed_length > length: 87b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum print 'warning: bitvec() value is longer than the lenght indicates, truncating value' 88b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data = self._data & \ 89b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum ((1L << length) - 1) 90b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._len = length 91b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum else: 92b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum raise error, 'bitvec() requires array or long parameter' 93b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum else: 94b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum raise error, 'bitvec() requires 0 -- 2 parameter(s)' 95b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 96b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return self 97b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 98b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 99b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def _init(self, data, len): 100b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data = data 101b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._len = len 102b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return self 103b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 104b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 105b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def append(self, item): 106b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #_check_value(item) 107b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #self[self._len:self._len] = [item] 108b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self[self._len:self._len] = \ 109b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum BitVec()._init(long(not not item), 1) 110b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 111b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 112b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def count(self, value): 113b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #_check_value(value) 114b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if value: 115b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum data = self._data 116b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum else: 117b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum data = (~self)._data 118b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum count = 0 119b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum while data: 120b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum data, count = data >> 1, count + (data & 1 != 0) 121b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return count 122b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 123b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 124b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def index(self, value): 125b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #_check_value(value): 126b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if value: 127b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum data = self._data 128b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum else: 129b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum data = (~self)._data 130b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum index = 0 131b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if not data: 132b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum raise ValueError, 'list.index(x): x not in list' 133b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum while not (data & 1): 134b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum data, index = data >> 1, index + 1 135b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return index 136b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 137b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 138b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def insert(self, index, item): 139b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #_check_value(item) 140b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #self[index:index] = [item] 141b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self[index:index] = BitVec()._init(long(not not item), 1) 142b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 143b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 144b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def remove(self, value): 145b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum del self[self.index(value)] 146b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 147b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 148b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def reverse(self): 149b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #ouch, this one is expensive! 150b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #for i in self._len>>1: self[i], self[l-i] = self[l-i], self[i] 151b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum data, result = self._data, 0L 152b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum for i in range(self._len): 153b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if not data: 154b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum result = result << (self._len - i) 155b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum break 156b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum result, data = (result << 1) | (data & 1), data >> 1 157b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data = result 158b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 159b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 160b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def sort(self): 161b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum c = self.count(1) 162b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data = ((1L << c) - 1) << (self._len - c) 163b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 164b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 165b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def copy(self): 166b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return BitVec()._init(self._data, self._len) 167b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 168b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 169b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def seq(self): 170b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum result = [] 171b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum for i in self: 172b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum result.append(i) 173b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return result 174b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 175b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 176b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __repr__(self): 177b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum ##rprt('<bitvec class instance object>.' + '__repr__()\n') 178b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return 'bitvec' + `self._data, self._len` 179b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 180b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __cmp__(self, other, *rest): 181b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__cmp__'+`(other, ) + rest`+'\n') 182b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if type(other) != type(self): 183b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum other = apply(bitvec, (other, ) + rest) 184b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #expensive solution... recursive binary, with slicing 185b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum length = self._len 186b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if length == 0 or other._len == 0: 187b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return cmp(length, other._len) 188b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if length != other._len: 189b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum min_lenght = min(length, other._len) 190b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return cmp(self[:min_length], other[:min_length]) or \ 191b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum cmp(self[min_length:], other[min_length:]) 192b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #the lengths are the same now... 193b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if self._data == other._data: 194b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return 0 195b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if length == 1: 196b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return cmp(self[0], other[0]) 197b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum else: 198b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum length = length >> 1 199b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return cmp(self[:length], other[:length]) or \ 200b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum cmp(self[length:], other[length:]) 201b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 202b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 203b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __len__(self): 204b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__len__()\n') 205b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return self._len 206b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 207b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __getitem__(self, key): 208b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__getitem__('+`key`+')\n') 209b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum key = _check_key(self._len, key) 210b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return self._data & (1L << key) != 0 211b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 212b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __setitem__(self, key, value): 213b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__setitem__'+`key, value`+'\n') 214b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum key = _check_key(self._len, key) 215b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #_check_value(value) 216b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if value: 217b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data = self._data | (1L << key) 218b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum else: 219b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data = self._data & ~(1L << key) 220b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 221b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __delitem__(self, key): 222b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__delitem__('+`key`+')\n') 223b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum key = _check_key(self._len, key) 224b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #el cheapo solution... 225b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data = self[:key]._data | self[key+1:]._data >> key 226b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._len = self._len - 1 227b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 228b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __getslice__(self, i, j): 229b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__getslice__'+`i, j`+'\n') 230b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum i, j = _check_slice(self._len, i, j) 231b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if i >= j: 232b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return BitVec()._init(0L, 0) 233b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if i: 234b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum ndata = self._data >> i 235b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum else: 236b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum ndata = self._data 237b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum nlength = j - i 238b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if j != self._len: 239b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #we'll have to invent faster variants here 240b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #e.g. mod_2exp 241b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum ndata = ndata & ((1L << nlength) - 1) 242b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return BitVec()._init(ndata, nlength) 243b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 244b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __setslice__(self, i, j, sequence, *rest): 245b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__setslice__'+`(i, j, sequence) + rest`+'\n') 246b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum i, j = _check_slice(self._len, i, j) 247b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if type(sequence) != type(self): 248b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum sequence = apply(bitvec, (sequence, ) + rest) 249b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #sequence is now of our own type 250b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum ls_part = self[:i] 251b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum ms_part = self[j:] 252b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data = ls_part._data | \ 253b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum ((sequence._data | \ 254b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum (ms_part._data << sequence._len)) << ls_part._len) 255b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._len = self._len - j + i + sequence._len 256b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 257b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __delslice__(self, i, j): 258b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__delslice__'+`i, j`+'\n') 259b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum i, j = _check_slice(self._len, i, j) 260b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if i == 0 and j == self._len: 261b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data, self._len = 0L, 0 262b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum elif i < j: 263b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._data = self[:i]._data | (self[j:]._data >> i) 264b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._len = self._len - j + i 265b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 266b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __add__(self, other): 267b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__add__('+`other`+')\n') 268b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum retval = self.copy() 269b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum retval[self._len:self._len] = other 270b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return retval 271b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 272b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __mul__(self, multiplier): 273b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__mul__('+`multiplier`+')\n') 274b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if type(multiplier) != type(0): 275b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum raise TypeError, 'sequence subscript not int' 276b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if multiplier <= 0: 277b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return BitVec()._init(0L, 0) 278b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum elif multiplier == 1: 279b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return self.copy() 280b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #handle special cases all 0 or all 1... 281b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if self._data == 0L: 282b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return BitVec()._init(0L, self._len * multiplier) 283b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum elif (~self)._data == 0L: 284b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return ~BitVec()._init(0L, self._len * multiplier) 285b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #otherwise el cheapo again... 286b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum retval = BitVec()._init(0L, 0) 287b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum while multiplier: 288b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum retval, multiplier = retval + self, multiplier - 1 289b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return retval 290b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 291b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __and__(self, otherseq, *rest): 292b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__and__'+`(otherseq, ) + rest`+'\n') 293b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if type(otherseq) != type(self): 294b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum otherseq = apply(bitvec, (otherseq, ) + rest) 295b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #sequence is now of our own type 296b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return BitVec()._init(self._data & otherseq._data, \ 297b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum min(self._len, otherseq._len)) 298b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 299b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 300b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __xor__(self, otherseq, *rest): 301b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__xor__'+`(otherseq, ) + rest`+'\n') 302b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if type(otherseq) != type(self): 303b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum otherseq = apply(bitvec, (otherseq, ) + rest) 304b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #sequence is now of our own type 305b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return BitVec()._init(self._data ^ otherseq._data, \ 306b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum max(self._len, otherseq._len)) 307b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 308b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 309b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __or__(self, otherseq, *rest): 310b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__or__'+`(otherseq, ) + rest`+'\n') 311b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if type(otherseq) != type(self): 312b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum otherseq = apply(bitvec, (otherseq, ) + rest) 313b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #sequence is now of our own type 314b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return BitVec()._init(self._data | otherseq._data, \ 315b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum max(self._len, otherseq._len)) 316b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 317b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 318b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __invert__(self): 319b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__invert__()\n') 320b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return BitVec()._init(~self._data & ((1L << self._len) - 1), \ 321b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum self._len) 322b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 323b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __coerce__(self, otherseq, *rest): 324b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #needed for *some* of the arithmetic operations 325b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum #rprt(`self`+'.__coerce__'+`(otherseq, ) + rest`+'\n') 326b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum if type(otherseq) != type(self): 327b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum otherseq = apply(bitvec, (otherseq, ) + rest) 328b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return self, otherseq 329b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 330b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __int__(self): 331b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return int(self._data) 332b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 333b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __long__(self): 334b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return long(self._data) 335b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 336b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum def __float__(self): 337b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return float(self._data) 338b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 339b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum 340b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossumdef bitvec(params): 341b6957e434fab0b901cb2c8fafeba77f9ae7a653fGuido van Rossum return apply(BitVec().init, params) 342