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