summaryrefslogtreecommitdiffstats
path: root/Demo/classes/bitvec.py
diff options
context:
space:
mode:
authorAndrew M. Kuchling <amk@amk.ca>2003-04-24 17:13:18 (GMT)
committerAndrew M. Kuchling <amk@amk.ca>2003-04-24 17:13:18 (GMT)
commit946c53ed7ff53f38792ac35e5da21de3e0a48ef2 (patch)
treef4e9d42bd70a153c2b1f5d2394d123a15ccf6c98 /Demo/classes/bitvec.py
parent4f237b6870bc856e2af5f23e524a9d32cd42e027 (diff)
downloadcpython-946c53ed7ff53f38792ac35e5da21de3e0a48ef2.zip
cpython-946c53ed7ff53f38792ac35e5da21de3e0a48ef2.tar.gz
cpython-946c53ed7ff53f38792ac35e5da21de3e0a48ef2.tar.bz2
Run these demo scripts through reindent.py to give them 4-space indents. I've verified that their output is unchanged.
Diffstat (limited to 'Demo/classes/bitvec.py')
-rwxr-xr-xDemo/classes/bitvec.py608
1 files changed, 304 insertions, 304 deletions
diff --git a/Demo/classes/bitvec.py b/Demo/classes/bitvec.py
index b346997..ed89d67 100755
--- a/Demo/classes/bitvec.py
+++ b/Demo/classes/bitvec.py
@@ -10,323 +10,323 @@ error = 'bitvec.error'
def _check_value(value):
- if type(value) != type(0) or not 0 <= value < 2:
- raise error, 'bitvec() items must have int value 0 or 1'
+ if type(value) != type(0) or not 0 <= value < 2:
+ raise error, 'bitvec() items must have int value 0 or 1'
import math
def _compute_len(param):
- mant, l = math.frexp(float(param))
- bitmask = 1L << l
- if bitmask <= param:
- raise 'FATAL', '(param, l) = ' + `param, l`
- while l:
- bitmask = bitmask >> 1
- if param & bitmask:
- break
- l = l - 1
- return l
+ mant, l = math.frexp(float(param))
+ bitmask = 1L << l
+ if bitmask <= param:
+ raise 'FATAL', '(param, l) = ' + `param, l`
+ while l:
+ bitmask = bitmask >> 1
+ if param & bitmask:
+ break
+ l = l - 1
+ return l
def _check_key(len, key):
- if type(key) != type(0):
- raise TypeError, 'sequence subscript not int'
- if key < 0:
- key = key + len
- if not 0 <= key < len:
- raise IndexError, 'list index out of range'
- return key
+ if type(key) != type(0):
+ raise TypeError, 'sequence subscript not int'
+ if key < 0:
+ key = key + len
+ if not 0 <= key < len:
+ raise IndexError, 'list index out of range'
+ return key
def _check_slice(len, i, j):
- #the type is ok, Python already checked that
- i, j = max(i, 0), min(len, j)
- if i > j:
- i = j
- return i, j
-
+ #the type is ok, Python already checked that
+ i, j = max(i, 0), min(len, j)
+ if i > j:
+ i = j
+ return i, j
+
class BitVec:
- def __init__(self, *params):
- self._data = 0L
- self._len = 0
- if not len(params):
- pass
- elif len(params) == 1:
- param, = params
- if type(param) == type([]):
- value = 0L
- bit_mask = 1L
- for item in param:
- # strict check
- #_check_value(item)
- if item:
- value = value | bit_mask
- bit_mask = bit_mask << 1
- self._data = value
- self._len = len(param)
- elif type(param) == type(0L):
- if param < 0:
- raise error, 'bitvec() can\'t handle negative longs'
- self._data = param
- self._len = _compute_len(param)
- else:
- raise error, 'bitvec() requires array or long parameter'
- elif len(params) == 2:
- param, length = params
- if type(param) == type(0L):
- if param < 0:
- raise error, \
- 'can\'t handle negative longs'
- self._data = param
- if type(length) != type(0):
- raise error, 'bitvec()\'s 2nd parameter must be int'
- computed_length = _compute_len(param)
- if computed_length > length:
- print 'warning: bitvec() value is longer than the length indicates, truncating value'
- self._data = self._data & \
- ((1L << length) - 1)
- self._len = length
- else:
- raise error, 'bitvec() requires array or long parameter'
- else:
- raise error, 'bitvec() requires 0 -- 2 parameter(s)'
-
-
- def append(self, item):
- #_check_value(item)
- #self[self._len:self._len] = [item]
- self[self._len:self._len] = \
- BitVec(long(not not item), 1)
-
-
- def count(self, value):
- #_check_value(value)
- if value:
- data = self._data
- else:
- data = (~self)._data
- count = 0
- while data:
- data, count = data >> 1, count + (data & 1 != 0)
- return count
-
-
- def index(self, value):
- #_check_value(value):
- if value:
- data = self._data
- else:
- data = (~self)._data
- index = 0
- if not data:
- raise ValueError, 'list.index(x): x not in list'
- while not (data & 1):
- data, index = data >> 1, index + 1
- return index
-
-
- def insert(self, index, item):
- #_check_value(item)
- #self[index:index] = [item]
- self[index:index] = BitVec(long(not not item), 1)
-
-
- def remove(self, value):
- del self[self.index(value)]
-
-
- def reverse(self):
- #ouch, this one is expensive!
- #for i in self._len>>1: self[i], self[l-i] = self[l-i], self[i]
- data, result = self._data, 0L
- for i in range(self._len):
- if not data:
- result = result << (self._len - i)
- break
- result, data = (result << 1) | (data & 1), data >> 1
- self._data = result
-
-
- def sort(self):
- c = self.count(1)
- self._data = ((1L << c) - 1) << (self._len - c)
-
-
- def copy(self):
- return BitVec(self._data, self._len)
-
-
- def seq(self):
- result = []
- for i in self:
- result.append(i)
- return result
-
-
- def __repr__(self):
- ##rprt('<bitvec class instance object>.' + '__repr__()\n')
- return 'bitvec' + `self._data, self._len`
-
- def __cmp__(self, other, *rest):
- #rprt(`self`+'.__cmp__'+`(other, ) + rest`+'\n')
- if type(other) != type(self):
- other = apply(bitvec, (other, ) + rest)
- #expensive solution... recursive binary, with slicing
- length = self._len
- if length == 0 or other._len == 0:
- return cmp(length, other._len)
- if length != other._len:
- min_length = min(length, other._len)
- return cmp(self[:min_length], other[:min_length]) or \
- cmp(self[min_length:], other[min_length:])
- #the lengths are the same now...
- if self._data == other._data:
- return 0
- if length == 1:
- return cmp(self[0], other[0])
- else:
- length = length >> 1
- return cmp(self[:length], other[:length]) or \
- cmp(self[length:], other[length:])
-
-
- def __len__(self):
- #rprt(`self`+'.__len__()\n')
- return self._len
-
- def __getitem__(self, key):
- #rprt(`self`+'.__getitem__('+`key`+')\n')
- key = _check_key(self._len, key)
- return self._data & (1L << key) != 0
-
- def __setitem__(self, key, value):
- #rprt(`self`+'.__setitem__'+`key, value`+'\n')
- key = _check_key(self._len, key)
- #_check_value(value)
- if value:
- self._data = self._data | (1L << key)
- else:
- self._data = self._data & ~(1L << key)
-
- def __delitem__(self, key):
- #rprt(`self`+'.__delitem__('+`key`+')\n')
- key = _check_key(self._len, key)
- #el cheapo solution...
- self._data = self[:key]._data | self[key+1:]._data >> key
- self._len = self._len - 1
-
- def __getslice__(self, i, j):
- #rprt(`self`+'.__getslice__'+`i, j`+'\n')
- i, j = _check_slice(self._len, i, j)
- if i >= j:
- return BitVec(0L, 0)
- if i:
- ndata = self._data >> i
- else:
- ndata = self._data
- nlength = j - i
- if j != self._len:
- #we'll have to invent faster variants here
- #e.g. mod_2exp
- ndata = ndata & ((1L << nlength) - 1)
- return BitVec(ndata, nlength)
-
- def __setslice__(self, i, j, sequence, *rest):
- #rprt(`self`+'.__setslice__'+`(i, j, sequence) + rest`+'\n')
- i, j = _check_slice(self._len, i, j)
- if type(sequence) != type(self):
- sequence = apply(bitvec, (sequence, ) + rest)
- #sequence is now of our own type
- ls_part = self[:i]
- ms_part = self[j:]
- self._data = ls_part._data | \
- ((sequence._data | \
- (ms_part._data << sequence._len)) << ls_part._len)
- self._len = self._len - j + i + sequence._len
-
- def __delslice__(self, i, j):
- #rprt(`self`+'.__delslice__'+`i, j`+'\n')
- i, j = _check_slice(self._len, i, j)
- if i == 0 and j == self._len:
- self._data, self._len = 0L, 0
- elif i < j:
- self._data = self[:i]._data | (self[j:]._data >> i)
- self._len = self._len - j + i
-
- def __add__(self, other):
- #rprt(`self`+'.__add__('+`other`+')\n')
- retval = self.copy()
- retval[self._len:self._len] = other
- return retval
-
- def __mul__(self, multiplier):
- #rprt(`self`+'.__mul__('+`multiplier`+')\n')
- if type(multiplier) != type(0):
- raise TypeError, 'sequence subscript not int'
- if multiplier <= 0:
- return BitVec(0L, 0)
- elif multiplier == 1:
- return self.copy()
- #handle special cases all 0 or all 1...
- if self._data == 0L:
- return BitVec(0L, self._len * multiplier)
- elif (~self)._data == 0L:
- return ~BitVec(0L, self._len * multiplier)
- #otherwise el cheapo again...
- retval = BitVec(0L, 0)
- while multiplier:
- retval, multiplier = retval + self, multiplier - 1
- return retval
-
- def __and__(self, otherseq, *rest):
- #rprt(`self`+'.__and__'+`(otherseq, ) + rest`+'\n')
- if type(otherseq) != type(self):
- otherseq = apply(bitvec, (otherseq, ) + rest)
- #sequence is now of our own type
- return BitVec(self._data & otherseq._data, \
- min(self._len, otherseq._len))
-
-
- def __xor__(self, otherseq, *rest):
- #rprt(`self`+'.__xor__'+`(otherseq, ) + rest`+'\n')
- if type(otherseq) != type(self):
- otherseq = apply(bitvec, (otherseq, ) + rest)
- #sequence is now of our own type
- return BitVec(self._data ^ otherseq._data, \
- max(self._len, otherseq._len))
-
-
- def __or__(self, otherseq, *rest):
- #rprt(`self`+'.__or__'+`(otherseq, ) + rest`+'\n')
- if type(otherseq) != type(self):
- otherseq = apply(bitvec, (otherseq, ) + rest)
- #sequence is now of our own type
- return BitVec(self._data | otherseq._data, \
- max(self._len, otherseq._len))
-
-
- def __invert__(self):
- #rprt(`self`+'.__invert__()\n')
- return BitVec(~self._data & ((1L << self._len) - 1), \
- self._len)
-
- def __coerce__(self, otherseq, *rest):
- #needed for *some* of the arithmetic operations
- #rprt(`self`+'.__coerce__'+`(otherseq, ) + rest`+'\n')
- if type(otherseq) != type(self):
- otherseq = apply(bitvec, (otherseq, ) + rest)
- return self, otherseq
-
- def __int__(self):
- return int(self._data)
-
- def __long__(self):
- return long(self._data)
-
- def __float__(self):
- return float(self._data)
+ def __init__(self, *params):
+ self._data = 0L
+ self._len = 0
+ if not len(params):
+ pass
+ elif len(params) == 1:
+ param, = params
+ if type(param) == type([]):
+ value = 0L
+ bit_mask = 1L
+ for item in param:
+ # strict check
+ #_check_value(item)
+ if item:
+ value = value | bit_mask
+ bit_mask = bit_mask << 1
+ self._data = value
+ self._len = len(param)
+ elif type(param) == type(0L):
+ if param < 0:
+ raise error, 'bitvec() can\'t handle negative longs'
+ self._data = param
+ self._len = _compute_len(param)
+ else:
+ raise error, 'bitvec() requires array or long parameter'
+ elif len(params) == 2:
+ param, length = params
+ if type(param) == type(0L):
+ if param < 0:
+ raise error, \
+ 'can\'t handle negative longs'
+ self._data = param
+ if type(length) != type(0):
+ raise error, 'bitvec()\'s 2nd parameter must be int'
+ computed_length = _compute_len(param)
+ if computed_length > length:
+ print 'warning: bitvec() value is longer than the length indicates, truncating value'
+ self._data = self._data & \
+ ((1L << length) - 1)
+ self._len = length
+ else:
+ raise error, 'bitvec() requires array or long parameter'
+ else:
+ raise error, 'bitvec() requires 0 -- 2 parameter(s)'
+
+
+ def append(self, item):
+ #_check_value(item)
+ #self[self._len:self._len] = [item]
+ self[self._len:self._len] = \
+ BitVec(long(not not item), 1)
+
+
+ def count(self, value):
+ #_check_value(value)
+ if value:
+ data = self._data
+ else:
+ data = (~self)._data
+ count = 0
+ while data:
+ data, count = data >> 1, count + (data & 1 != 0)
+ return count
+
+
+ def index(self, value):
+ #_check_value(value):
+ if value:
+ data = self._data
+ else:
+ data = (~self)._data
+ index = 0
+ if not data:
+ raise ValueError, 'list.index(x): x not in list'
+ while not (data & 1):
+ data, index = data >> 1, index + 1
+ return index
+
+
+ def insert(self, index, item):
+ #_check_value(item)
+ #self[index:index] = [item]
+ self[index:index] = BitVec(long(not not item), 1)
+
+
+ def remove(self, value):
+ del self[self.index(value)]
+
+
+ def reverse(self):
+ #ouch, this one is expensive!
+ #for i in self._len>>1: self[i], self[l-i] = self[l-i], self[i]
+ data, result = self._data, 0L
+ for i in range(self._len):
+ if not data:
+ result = result << (self._len - i)
+ break
+ result, data = (result << 1) | (data & 1), data >> 1
+ self._data = result
+
+
+ def sort(self):
+ c = self.count(1)
+ self._data = ((1L << c) - 1) << (self._len - c)
+
+
+ def copy(self):
+ return BitVec(self._data, self._len)
+
+
+ def seq(self):
+ result = []
+ for i in self:
+ result.append(i)
+ return result
+
+
+ def __repr__(self):
+ ##rprt('<bitvec class instance object>.' + '__repr__()\n')
+ return 'bitvec' + `self._data, self._len`
+
+ def __cmp__(self, other, *rest):
+ #rprt(`self`+'.__cmp__'+`(other, ) + rest`+'\n')
+ if type(other) != type(self):
+ other = apply(bitvec, (other, ) + rest)
+ #expensive solution... recursive binary, with slicing
+ length = self._len
+ if length == 0 or other._len == 0:
+ return cmp(length, other._len)
+ if length != other._len:
+ min_length = min(length, other._len)
+ return cmp(self[:min_length], other[:min_length]) or \
+ cmp(self[min_length:], other[min_length:])
+ #the lengths are the same now...
+ if self._data == other._data:
+ return 0
+ if length == 1:
+ return cmp(self[0], other[0])
+ else:
+ length = length >> 1
+ return cmp(self[:length], other[:length]) or \
+ cmp(self[length:], other[length:])
+
+
+ def __len__(self):
+ #rprt(`self`+'.__len__()\n')
+ return self._len
+
+ def __getitem__(self, key):
+ #rprt(`self`+'.__getitem__('+`key`+')\n')
+ key = _check_key(self._len, key)
+ return self._data & (1L << key) != 0
+
+ def __setitem__(self, key, value):
+ #rprt(`self`+'.__setitem__'+`key, value`+'\n')
+ key = _check_key(self._len, key)
+ #_check_value(value)
+ if value:
+ self._data = self._data | (1L << key)
+ else:
+ self._data = self._data & ~(1L << key)
+
+ def __delitem__(self, key):
+ #rprt(`self`+'.__delitem__('+`key`+')\n')
+ key = _check_key(self._len, key)
+ #el cheapo solution...
+ self._data = self[:key]._data | self[key+1:]._data >> key
+ self._len = self._len - 1
+
+ def __getslice__(self, i, j):
+ #rprt(`self`+'.__getslice__'+`i, j`+'\n')
+ i, j = _check_slice(self._len, i, j)
+ if i >= j:
+ return BitVec(0L, 0)
+ if i:
+ ndata = self._data >> i
+ else:
+ ndata = self._data
+ nlength = j - i
+ if j != self._len:
+ #we'll have to invent faster variants here
+ #e.g. mod_2exp
+ ndata = ndata & ((1L << nlength) - 1)
+ return BitVec(ndata, nlength)
+
+ def __setslice__(self, i, j, sequence, *rest):
+ #rprt(`self`+'.__setslice__'+`(i, j, sequence) + rest`+'\n')
+ i, j = _check_slice(self._len, i, j)
+ if type(sequence) != type(self):
+ sequence = apply(bitvec, (sequence, ) + rest)
+ #sequence is now of our own type
+ ls_part = self[:i]
+ ms_part = self[j:]
+ self._data = ls_part._data | \
+ ((sequence._data | \
+ (ms_part._data << sequence._len)) << ls_part._len)
+ self._len = self._len - j + i + sequence._len
+
+ def __delslice__(self, i, j):
+ #rprt(`self`+'.__delslice__'+`i, j`+'\n')
+ i, j = _check_slice(self._len, i, j)
+ if i == 0 and j == self._len:
+ self._data, self._len = 0L, 0
+ elif i < j:
+ self._data = self[:i]._data | (self[j:]._data >> i)
+ self._len = self._len - j + i
+
+ def __add__(self, other):
+ #rprt(`self`+'.__add__('+`other`+')\n')
+ retval = self.copy()
+ retval[self._len:self._len] = other
+ return retval
+
+ def __mul__(self, multiplier):
+ #rprt(`self`+'.__mul__('+`multiplier`+')\n')
+ if type(multiplier) != type(0):
+ raise TypeError, 'sequence subscript not int'
+ if multiplier <= 0:
+ return BitVec(0L, 0)
+ elif multiplier == 1:
+ return self.copy()
+ #handle special cases all 0 or all 1...
+ if self._data == 0L:
+ return BitVec(0L, self._len * multiplier)
+ elif (~self)._data == 0L:
+ return ~BitVec(0L, self._len * multiplier)
+ #otherwise el cheapo again...
+ retval = BitVec(0L, 0)
+ while multiplier:
+ retval, multiplier = retval + self, multiplier - 1
+ return retval
+
+ def __and__(self, otherseq, *rest):
+ #rprt(`self`+'.__and__'+`(otherseq, ) + rest`+'\n')
+ if type(otherseq) != type(self):
+ otherseq = apply(bitvec, (otherseq, ) + rest)
+ #sequence is now of our own type
+ return BitVec(self._data & otherseq._data, \
+ min(self._len, otherseq._len))
+
+
+ def __xor__(self, otherseq, *rest):
+ #rprt(`self`+'.__xor__'+`(otherseq, ) + rest`+'\n')
+ if type(otherseq) != type(self):
+ otherseq = apply(bitvec, (otherseq, ) + rest)
+ #sequence is now of our own type
+ return BitVec(self._data ^ otherseq._data, \
+ max(self._len, otherseq._len))
+
+
+ def __or__(self, otherseq, *rest):
+ #rprt(`self`+'.__or__'+`(otherseq, ) + rest`+'\n')
+ if type(otherseq) != type(self):
+ otherseq = apply(bitvec, (otherseq, ) + rest)
+ #sequence is now of our own type
+ return BitVec(self._data | otherseq._data, \
+ max(self._len, otherseq._len))
+
+
+ def __invert__(self):
+ #rprt(`self`+'.__invert__()\n')
+ return BitVec(~self._data & ((1L << self._len) - 1), \
+ self._len)
+
+ def __coerce__(self, otherseq, *rest):
+ #needed for *some* of the arithmetic operations
+ #rprt(`self`+'.__coerce__'+`(otherseq, ) + rest`+'\n')
+ if type(otherseq) != type(self):
+ otherseq = apply(bitvec, (otherseq, ) + rest)
+ return self, otherseq
+
+ def __int__(self):
+ return int(self._data)
+
+ def __long__(self):
+ return long(self._data)
+
+ def __float__(self):
+ return float(self._data)
bitvec = BitVec