From 946c53ed7ff53f38792ac35e5da21de3e0a48ef2 Mon Sep 17 00:00:00 2001 From: "Andrew M. Kuchling" Date: Thu, 24 Apr 2003 17:13:18 +0000 Subject: Run these demo scripts through reindent.py to give them 4-space indents. I've verified that their output is unchanged. --- Demo/classes/Complex.py | 418 +++++++++++++-------------- Demo/classes/Dbm.py | 90 +++--- Demo/classes/Range.py | 88 +++--- Demo/classes/Rat.py | 558 ++++++++++++++++++------------------ Demo/classes/Rev.py | 82 +++--- Demo/classes/Vec.py | 82 +++--- Demo/classes/bitvec.py | 608 ++++++++++++++++++++-------------------- Demo/comparisons/regextest.py | 46 +-- Demo/comparisons/sortingtest.py | 48 ++-- Demo/comparisons/systemtest.py | 96 +++---- 10 files changed, 1058 insertions(+), 1058 deletions(-) diff --git a/Demo/classes/Complex.py b/Demo/classes/Complex.py index bfb0d95..4585f62 100755 --- a/Demo/classes/Complex.py +++ b/Demo/classes/Complex.py @@ -16,8 +16,8 @@ # ToComplex(z) -> a complex number equal to z; z itself if IsComplex(z) is true # if z is a tuple(re, im) it will also be converted # PolarToComplex([r [,phi [,fullcircle]]]) -> -# the complex number z for which r == z.radius() and phi == z.angle(fullcircle) -# (r and phi default to 0) +# the complex number z for which r == z.radius() and phi == z.angle(fullcircle) +# (r and phi default to 0) # exp(z) -> returns the complex exponential of z. Equivalent to pow(math.e,z). # # Complex numbers have the following methods: @@ -69,230 +69,230 @@ twopi = math.pi*2.0 halfpi = math.pi/2.0 def IsComplex(obj): - return hasattr(obj, 're') and hasattr(obj, 'im') + return hasattr(obj, 're') and hasattr(obj, 'im') def ToComplex(obj): - if IsComplex(obj): - return obj - elif type(obj) == types.TupleType: - return apply(Complex, obj) - else: - return Complex(obj) + if IsComplex(obj): + return obj + elif type(obj) == types.TupleType: + return apply(Complex, obj) + else: + return Complex(obj) def PolarToComplex(r = 0, phi = 0, fullcircle = twopi): - phi = phi * (twopi / fullcircle) - return Complex(math.cos(phi)*r, math.sin(phi)*r) + phi = phi * (twopi / fullcircle) + return Complex(math.cos(phi)*r, math.sin(phi)*r) def Re(obj): - if IsComplex(obj): - return obj.re - else: - return obj + if IsComplex(obj): + return obj.re + else: + return obj def Im(obj): - if IsComplex(obj): - return obj.im - else: - return obj + if IsComplex(obj): + return obj.im + else: + return obj class Complex: - def __init__(self, re=0, im=0): - if IsComplex(re): - im = i + Complex(0, re.im) - re = re.re - if IsComplex(im): - re = re - im.im - im = im.re - self.__dict__['re'] = re - self.__dict__['im'] = im - - def __setattr__(self, name, value): - raise TypeError, 'Complex numbers are immutable' - - def __hash__(self): - if not self.im: return hash(self.re) - mod = sys.maxint + 1L - return int((hash(self.re) + 2L*hash(self.im) + mod) % (2L*mod) - mod) - - def __repr__(self): - if not self.im: - return 'Complex(%s)' % `self.re` - else: - return 'Complex(%s, %s)' % (`self.re`, `self.im`) - - def __str__(self): - if not self.im: - return `self.re` - else: - return 'Complex(%s, %s)' % (`self.re`, `self.im`) - - def __neg__(self): - return Complex(-self.re, -self.im) - - def __pos__(self): - return self - - def __abs__(self): - # XXX could be done differently to avoid overflow! - return math.sqrt(self.re*self.re + self.im*self.im) - - def __int__(self): - if self.im: - raise ValueError, "can't convert Complex with nonzero im to int" - return int(self.re) - - def __long__(self): - if self.im: - raise ValueError, "can't convert Complex with nonzero im to long" - return long(self.re) - - def __float__(self): - if self.im: - raise ValueError, "can't convert Complex with nonzero im to float" - return float(self.re) - - def __cmp__(self, other): - other = ToComplex(other) - return cmp((self.re, self.im), (other.re, other.im)) - - def __rcmp__(self, other): - other = ToComplex(other) - return cmp(other, self) - - def __nonzero__(self): - return not (self.re == self.im == 0) - - abs = radius = __abs__ - - def angle(self, fullcircle = twopi): - return (fullcircle/twopi) * ((halfpi - math.atan2(self.re, self.im)) % twopi) - - phi = angle - - def __add__(self, other): - other = ToComplex(other) - return Complex(self.re + other.re, self.im + other.im) - - __radd__ = __add__ - - def __sub__(self, other): - other = ToComplex(other) - return Complex(self.re - other.re, self.im - other.im) - - def __rsub__(self, other): - other = ToComplex(other) - return other - self - - def __mul__(self, other): - other = ToComplex(other) - return Complex(self.re*other.re - self.im*other.im, - self.re*other.im + self.im*other.re) - - __rmul__ = __mul__ - - def __div__(self, other): - other = ToComplex(other) - d = float(other.re*other.re + other.im*other.im) - if not d: raise ZeroDivisionError, 'Complex division' - return Complex((self.re*other.re + self.im*other.im) / d, - (self.im*other.re - self.re*other.im) / d) - - def __rdiv__(self, other): - other = ToComplex(other) - return other / self - - def __pow__(self, n, z=None): - if z is not None: - raise TypeError, 'Complex does not support ternary pow()' - if IsComplex(n): - if n.im: - if self.im: raise TypeError, 'Complex to the Complex power' - else: return exp(math.log(self.re)*n) - n = n.re - r = pow(self.abs(), n) - phi = n*self.angle() - return Complex(math.cos(phi)*r, math.sin(phi)*r) - - def __rpow__(self, base): - base = ToComplex(base) - return pow(base, self) - + def __init__(self, re=0, im=0): + if IsComplex(re): + im = i + Complex(0, re.im) + re = re.re + if IsComplex(im): + re = re - im.im + im = im.re + self.__dict__['re'] = re + self.__dict__['im'] = im + + def __setattr__(self, name, value): + raise TypeError, 'Complex numbers are immutable' + + def __hash__(self): + if not self.im: return hash(self.re) + mod = sys.maxint + 1L + return int((hash(self.re) + 2L*hash(self.im) + mod) % (2L*mod) - mod) + + def __repr__(self): + if not self.im: + return 'Complex(%s)' % `self.re` + else: + return 'Complex(%s, %s)' % (`self.re`, `self.im`) + + def __str__(self): + if not self.im: + return `self.re` + else: + return 'Complex(%s, %s)' % (`self.re`, `self.im`) + + def __neg__(self): + return Complex(-self.re, -self.im) + + def __pos__(self): + return self + + def __abs__(self): + # XXX could be done differently to avoid overflow! + return math.sqrt(self.re*self.re + self.im*self.im) + + def __int__(self): + if self.im: + raise ValueError, "can't convert Complex with nonzero im to int" + return int(self.re) + + def __long__(self): + if self.im: + raise ValueError, "can't convert Complex with nonzero im to long" + return long(self.re) + + def __float__(self): + if self.im: + raise ValueError, "can't convert Complex with nonzero im to float" + return float(self.re) + + def __cmp__(self, other): + other = ToComplex(other) + return cmp((self.re, self.im), (other.re, other.im)) + + def __rcmp__(self, other): + other = ToComplex(other) + return cmp(other, self) + + def __nonzero__(self): + return not (self.re == self.im == 0) + + abs = radius = __abs__ + + def angle(self, fullcircle = twopi): + return (fullcircle/twopi) * ((halfpi - math.atan2(self.re, self.im)) % twopi) + + phi = angle + + def __add__(self, other): + other = ToComplex(other) + return Complex(self.re + other.re, self.im + other.im) + + __radd__ = __add__ + + def __sub__(self, other): + other = ToComplex(other) + return Complex(self.re - other.re, self.im - other.im) + + def __rsub__(self, other): + other = ToComplex(other) + return other - self + + def __mul__(self, other): + other = ToComplex(other) + return Complex(self.re*other.re - self.im*other.im, + self.re*other.im + self.im*other.re) + + __rmul__ = __mul__ + + def __div__(self, other): + other = ToComplex(other) + d = float(other.re*other.re + other.im*other.im) + if not d: raise ZeroDivisionError, 'Complex division' + return Complex((self.re*other.re + self.im*other.im) / d, + (self.im*other.re - self.re*other.im) / d) + + def __rdiv__(self, other): + other = ToComplex(other) + return other / self + + def __pow__(self, n, z=None): + if z is not None: + raise TypeError, 'Complex does not support ternary pow()' + if IsComplex(n): + if n.im: + if self.im: raise TypeError, 'Complex to the Complex power' + else: return exp(math.log(self.re)*n) + n = n.re + r = pow(self.abs(), n) + phi = n*self.angle() + return Complex(math.cos(phi)*r, math.sin(phi)*r) + + def __rpow__(self, base): + base = ToComplex(base) + return pow(base, self) + def exp(z): - r = math.exp(z.re) - return Complex(math.cos(z.im)*r,math.sin(z.im)*r) + r = math.exp(z.re) + return Complex(math.cos(z.im)*r,math.sin(z.im)*r) def checkop(expr, a, b, value, fuzz = 1e-6): - import sys - print ' ', a, 'and', b, - try: - result = eval(expr) - except: - result = sys.exc_type - print '->', result - if (type(result) == type('') or type(value) == type('')): - ok = result == value - else: - ok = abs(result - value) <= fuzz - if not ok: - print '!!\t!!\t!! should be', value, 'diff', abs(result - value) + import sys + print ' ', a, 'and', b, + try: + result = eval(expr) + except: + result = sys.exc_type + print '->', result + if (type(result) == type('') or type(value) == type('')): + ok = result == value + else: + ok = abs(result - value) <= fuzz + if not ok: + print '!!\t!!\t!! should be', value, 'diff', abs(result - value) def test(): - testsuite = { - 'a+b': [ - (1, 10, 11), - (1, Complex(0,10), Complex(1,10)), - (Complex(0,10), 1, Complex(1,10)), - (Complex(0,10), Complex(1), Complex(1,10)), - (Complex(1), Complex(0,10), Complex(1,10)), - ], - 'a-b': [ - (1, 10, -9), - (1, Complex(0,10), Complex(1,-10)), - (Complex(0,10), 1, Complex(-1,10)), - (Complex(0,10), Complex(1), Complex(-1,10)), - (Complex(1), Complex(0,10), Complex(1,-10)), - ], - 'a*b': [ - (1, 10, 10), - (1, Complex(0,10), Complex(0, 10)), - (Complex(0,10), 1, Complex(0,10)), - (Complex(0,10), Complex(1), Complex(0,10)), - (Complex(1), Complex(0,10), Complex(0,10)), - ], - 'a/b': [ - (1., 10, 0.1), - (1, Complex(0,10), Complex(0, -0.1)), - (Complex(0, 10), 1, Complex(0, 10)), - (Complex(0, 10), Complex(1), Complex(0, 10)), - (Complex(1), Complex(0,10), Complex(0, -0.1)), - ], - 'pow(a,b)': [ - (1, 10, 1), - (1, Complex(0,10), 1), - (Complex(0,10), 1, Complex(0,10)), - (Complex(0,10), Complex(1), Complex(0,10)), - (Complex(1), Complex(0,10), 1), - (2, Complex(4,0), 16), - ], - 'cmp(a,b)': [ - (1, 10, -1), - (1, Complex(0,10), 1), - (Complex(0,10), 1, -1), - (Complex(0,10), Complex(1), -1), - (Complex(1), Complex(0,10), 1), - ], - } - exprs = testsuite.keys() - exprs.sort() - for expr in exprs: - print expr + ':' - t = (expr,) - for item in testsuite[expr]: - apply(checkop, t+item) - + testsuite = { + 'a+b': [ + (1, 10, 11), + (1, Complex(0,10), Complex(1,10)), + (Complex(0,10), 1, Complex(1,10)), + (Complex(0,10), Complex(1), Complex(1,10)), + (Complex(1), Complex(0,10), Complex(1,10)), + ], + 'a-b': [ + (1, 10, -9), + (1, Complex(0,10), Complex(1,-10)), + (Complex(0,10), 1, Complex(-1,10)), + (Complex(0,10), Complex(1), Complex(-1,10)), + (Complex(1), Complex(0,10), Complex(1,-10)), + ], + 'a*b': [ + (1, 10, 10), + (1, Complex(0,10), Complex(0, 10)), + (Complex(0,10), 1, Complex(0,10)), + (Complex(0,10), Complex(1), Complex(0,10)), + (Complex(1), Complex(0,10), Complex(0,10)), + ], + 'a/b': [ + (1., 10, 0.1), + (1, Complex(0,10), Complex(0, -0.1)), + (Complex(0, 10), 1, Complex(0, 10)), + (Complex(0, 10), Complex(1), Complex(0, 10)), + (Complex(1), Complex(0,10), Complex(0, -0.1)), + ], + 'pow(a,b)': [ + (1, 10, 1), + (1, Complex(0,10), 1), + (Complex(0,10), 1, Complex(0,10)), + (Complex(0,10), Complex(1), Complex(0,10)), + (Complex(1), Complex(0,10), 1), + (2, Complex(4,0), 16), + ], + 'cmp(a,b)': [ + (1, 10, -1), + (1, Complex(0,10), 1), + (Complex(0,10), 1, -1), + (Complex(0,10), Complex(1), -1), + (Complex(1), Complex(0,10), 1), + ], + } + exprs = testsuite.keys() + exprs.sort() + for expr in exprs: + print expr + ':' + t = (expr,) + for item in testsuite[expr]: + apply(checkop, t+item) + if __name__ == '__main__': - test() + test() diff --git a/Demo/classes/Dbm.py b/Demo/classes/Dbm.py index 8d7fe0f..5566f99 100755 --- a/Demo/classes/Dbm.py +++ b/Demo/classes/Dbm.py @@ -6,61 +6,61 @@ class Dbm: - def __init__(self, filename, mode, perm): - import dbm - self.db = dbm.open(filename, mode, perm) + def __init__(self, filename, mode, perm): + import dbm + self.db = dbm.open(filename, mode, perm) - def __repr__(self): - s = '' - for key in self.keys(): - t = `key` + ': ' + `self[key]` - if s: t = ', ' + t - s = s + t - return '{' + s + '}' + def __repr__(self): + s = '' + for key in self.keys(): + t = `key` + ': ' + `self[key]` + if s: t = ', ' + t + s = s + t + return '{' + s + '}' - def __len__(self): - return len(self.db) + def __len__(self): + return len(self.db) - def __getitem__(self, key): - return eval(self.db[`key`]) + def __getitem__(self, key): + return eval(self.db[`key`]) - def __setitem__(self, key, value): - self.db[`key`] = `value` + def __setitem__(self, key, value): + self.db[`key`] = `value` - def __delitem__(self, key): - del self.db[`key`] + def __delitem__(self, key): + del self.db[`key`] - def keys(self): - res = [] - for key in self.db.keys(): - res.append(eval(key)) - return res + def keys(self): + res = [] + for key in self.db.keys(): + res.append(eval(key)) + return res - def has_key(self, key): - return self.db.has_key(`key`) + def has_key(self, key): + return self.db.has_key(`key`) def test(): - d = Dbm('@dbm', 'rw', 0600) - print d - while 1: - try: - key = input('key: ') - if d.has_key(key): - value = d[key] - print 'currently:', value - value = input('value: ') - if value == None: - del d[key] - else: - d[key] = value - except KeyboardInterrupt: - print '' - print d - except EOFError: - print '[eof]' - break - print d + d = Dbm('@dbm', 'rw', 0600) + print d + while 1: + try: + key = input('key: ') + if d.has_key(key): + value = d[key] + print 'currently:', value + value = input('value: ') + if value == None: + del d[key] + else: + d[key] = value + except KeyboardInterrupt: + print '' + print d + except EOFError: + print '[eof]' + break + print d test() diff --git a/Demo/classes/Range.py b/Demo/classes/Range.py index 18f626f..ebd1817 100755 --- a/Demo/classes/Range.py +++ b/Demo/classes/Range.py @@ -7,17 +7,17 @@ # Wrapper function to emulate the complicated range() arguments def range(*a): - if len(a) == 1: - start, stop, step = 0, a[0], 1 - elif len(a) == 2: - start, stop = a - step = 1 - elif len(a) == 3: - start, stop, step = a - else: - raise TypeError, 'range() needs 1-3 arguments' - return Range(start, stop, step) - + if len(a) == 1: + start, stop, step = 0, a[0], 1 + elif len(a) == 2: + start, stop = a + step = 1 + elif len(a) == 3: + start, stop, step = a + else: + raise TypeError, 'range() needs 1-3 arguments' + return Range(start, stop, step) + # Class implementing a range object. # To the user the instances feel like immutable sequences @@ -25,47 +25,47 @@ def range(*a): class Range: - # initialization -- should be called only by range() above - def __init__(self, start, stop, step): - if step == 0: - raise ValueError, 'range() called with zero step' - self.start = start - self.stop = stop - self.step = step - self.len = max(0, int((self.stop - self.start) / self.step)) + # initialization -- should be called only by range() above + def __init__(self, start, stop, step): + if step == 0: + raise ValueError, 'range() called with zero step' + self.start = start + self.stop = stop + self.step = step + self.len = max(0, int((self.stop - self.start) / self.step)) - # implement `x` and is also used by print x - def __repr__(self): - return 'range' + `self.start, self.stop, self.step` + # implement `x` and is also used by print x + def __repr__(self): + return 'range' + `self.start, self.stop, self.step` - # implement len(x) - def __len__(self): - return self.len + # implement len(x) + def __len__(self): + return self.len - # implement x[i] - def __getitem__(self, i): - if 0 <= i < self.len: - return self.start + self.step * i - else: - raise IndexError, 'range[i] index out of range' + # implement x[i] + def __getitem__(self, i): + if 0 <= i < self.len: + return self.start + self.step * i + else: + raise IndexError, 'range[i] index out of range' # Small test program def test(): - import time, __builtin__ - print range(10), range(-10, 10), range(0, 10, 2) - for i in range(100, -100, -10): print i, - print - t1 = time.time() - for i in range(1000): - pass - t2 = time.time() - for i in __builtin__.range(1000): - pass - t3 = time.time() - print t2-t1, 'sec (class)' - print t3-t2, 'sec (built-in)' + import time, __builtin__ + print range(10), range(-10, 10), range(0, 10, 2) + for i in range(100, -100, -10): print i, + print + t1 = time.time() + for i in range(1000): + pass + t2 = time.time() + for i in __builtin__.range(1000): + pass + t3 = time.time() + print t2-t1, 'sec (class)' + print t3-t2, 'sec (built-in)' test() diff --git a/Demo/classes/Rat.py b/Demo/classes/Rat.py index b81f19f..55543b6 100755 --- a/Demo/classes/Rat.py +++ b/Demo/classes/Rat.py @@ -2,7 +2,7 @@ This module implements rational numbers. The entry point of this module is the function - rat(numerator, denominator) + rat(numerator, denominator) If either numerator or denominator is of an integral or rational type, the result is a rational number, else, the result is the simplest of the types float and complex which can hold numerator/denominator. @@ -11,7 +11,7 @@ Rational numbers can be used in calculations with any other numeric type. The result of the calculation will be rational if possible. There is also a test function with calling sequence - test() + test() The documentation string of the test function contains the expected output. ''' @@ -21,289 +21,289 @@ output. from types import * def gcd(a, b): - '''Calculate the Greatest Common Divisor.''' - while b: - a, b = b, a%b - return a + '''Calculate the Greatest Common Divisor.''' + while b: + a, b = b, a%b + return a def rat(num, den = 1): - # must check complex before float - if isinstance(num, complex) or isinstance(den, complex): - # numerator or denominator is complex: return a complex - return complex(num) / complex(den) - if isinstance(num, float) or isinstance(den, float): - # numerator or denominator is float: return a float - return float(num) / float(den) - # otherwise return a rational - return Rat(num, den) + # must check complex before float + if isinstance(num, complex) or isinstance(den, complex): + # numerator or denominator is complex: return a complex + return complex(num) / complex(den) + if isinstance(num, float) or isinstance(den, float): + # numerator or denominator is float: return a float + return float(num) / float(den) + # otherwise return a rational + return Rat(num, den) class Rat: - '''This class implements rational numbers.''' - - def __init__(self, num, den = 1): - if den == 0: - raise ZeroDivisionError, 'rat(x, 0)' - - # normalize - - # must check complex before float - if (isinstance(num, complex) or - isinstance(den, complex)): - # numerator or denominator is complex: - # normalized form has denominator == 1+0j - self.__num = complex(num) / complex(den) - self.__den = complex(1) - return - if isinstance(num, float) or isinstance(den, float): - # numerator or denominator is float: - # normalized form has denominator == 1.0 - self.__num = float(num) / float(den) - self.__den = 1.0 - return - if (isinstance(num, self.__class__) or - isinstance(den, self.__class__)): - # numerator or denominator is rational - new = num / den - if not isinstance(new, self.__class__): - self.__num = new - if isinstance(new, complex): - self.__den = complex(1) - else: - self.__den = 1.0 - else: - self.__num = new.__num - self.__den = new.__den - else: - # make sure numerator and denominator don't - # have common factors - # this also makes sure that denominator > 0 - g = gcd(num, den) - self.__num = num / g - self.__den = den / g - # try making numerator and denominator of IntType if they fit - try: - numi = int(self.__num) - deni = int(self.__den) - except (OverflowError, TypeError): - pass - else: - if self.__num == numi and self.__den == deni: - self.__num = numi - self.__den = deni - - def __repr__(self): - return 'Rat(%s,%s)' % (self.__num, self.__den) - - def __str__(self): - if self.__den == 1: - return str(self.__num) - else: - return '(%s/%s)' % (str(self.__num), str(self.__den)) - - # a + b - def __add__(a, b): - try: - return rat(a.__num * b.__den + b.__num * a.__den, - a.__den * b.__den) - except OverflowError: - return rat(long(a.__num) * long(b.__den) + - long(b.__num) * long(a.__den), - long(a.__den) * long(b.__den)) - - def __radd__(b, a): - return Rat(a) + b - - # a - b - def __sub__(a, b): - try: - return rat(a.__num * b.__den - b.__num * a.__den, - a.__den * b.__den) - except OverflowError: - return rat(long(a.__num) * long(b.__den) - - long(b.__num) * long(a.__den), - long(a.__den) * long(b.__den)) - - def __rsub__(b, a): - return Rat(a) - b - - # a * b - def __mul__(a, b): - try: - return rat(a.__num * b.__num, a.__den * b.__den) - except OverflowError: - return rat(long(a.__num) * long(b.__num), - long(a.__den) * long(b.__den)) - - def __rmul__(b, a): - return Rat(a) * b - - # a / b - def __div__(a, b): - try: - return rat(a.__num * b.__den, a.__den * b.__num) - except OverflowError: - return rat(long(a.__num) * long(b.__den), - long(a.__den) * long(b.__num)) - - def __rdiv__(b, a): - return Rat(a) / b - - # a % b - def __mod__(a, b): - div = a / b - try: - div = int(div) - except OverflowError: - div = long(div) - return a - b * div - - def __rmod__(b, a): - return Rat(a) % b - - # a ** b - def __pow__(a, b): - if b.__den != 1: - if isinstance(a.__num, complex): - a = complex(a) - else: - a = float(a) - if isinstance(b.__num, complex): - b = complex(b) - else: - b = float(b) - return a ** b - try: - return rat(a.__num ** b.__num, a.__den ** b.__num) - except OverflowError: - return rat(long(a.__num) ** b.__num, - long(a.__den) ** b.__num) - - def __rpow__(b, a): - return Rat(a) ** b - - # -a - def __neg__(a): - try: - return rat(-a.__num, a.__den) - except OverflowError: - # a.__num == sys.maxint - return rat(-long(a.__num), a.__den) - - # abs(a) - def __abs__(a): - return rat(abs(a.__num), a.__den) - - # int(a) - def __int__(a): - return int(a.__num / a.__den) - - # long(a) - def __long__(a): - return long(a.__num) / long(a.__den) - - # float(a) - def __float__(a): - return float(a.__num) / float(a.__den) - - # complex(a) - def __complex__(a): - return complex(a.__num) / complex(a.__den) - - # cmp(a,b) - def __cmp__(a, b): - diff = Rat(a - b) - if diff.__num < 0: - return -1 - elif diff.__num > 0: - return 1 - else: - return 0 - - def __rcmp__(b, a): - return cmp(Rat(a), b) - - # a != 0 - def __nonzero__(a): - return a.__num != 0 - - # coercion - def __coerce__(a, b): - return a, Rat(b) + '''This class implements rational numbers.''' + + def __init__(self, num, den = 1): + if den == 0: + raise ZeroDivisionError, 'rat(x, 0)' + + # normalize + + # must check complex before float + if (isinstance(num, complex) or + isinstance(den, complex)): + # numerator or denominator is complex: + # normalized form has denominator == 1+0j + self.__num = complex(num) / complex(den) + self.__den = complex(1) + return + if isinstance(num, float) or isinstance(den, float): + # numerator or denominator is float: + # normalized form has denominator == 1.0 + self.__num = float(num) / float(den) + self.__den = 1.0 + return + if (isinstance(num, self.__class__) or + isinstance(den, self.__class__)): + # numerator or denominator is rational + new = num / den + if not isinstance(new, self.__class__): + self.__num = new + if isinstance(new, complex): + self.__den = complex(1) + else: + self.__den = 1.0 + else: + self.__num = new.__num + self.__den = new.__den + else: + # make sure numerator and denominator don't + # have common factors + # this also makes sure that denominator > 0 + g = gcd(num, den) + self.__num = num / g + self.__den = den / g + # try making numerator and denominator of IntType if they fit + try: + numi = int(self.__num) + deni = int(self.__den) + except (OverflowError, TypeError): + pass + else: + if self.__num == numi and self.__den == deni: + self.__num = numi + self.__den = deni + + def __repr__(self): + return 'Rat(%s,%s)' % (self.__num, self.__den) + + def __str__(self): + if self.__den == 1: + return str(self.__num) + else: + return '(%s/%s)' % (str(self.__num), str(self.__den)) + + # a + b + def __add__(a, b): + try: + return rat(a.__num * b.__den + b.__num * a.__den, + a.__den * b.__den) + except OverflowError: + return rat(long(a.__num) * long(b.__den) + + long(b.__num) * long(a.__den), + long(a.__den) * long(b.__den)) + + def __radd__(b, a): + return Rat(a) + b + + # a - b + def __sub__(a, b): + try: + return rat(a.__num * b.__den - b.__num * a.__den, + a.__den * b.__den) + except OverflowError: + return rat(long(a.__num) * long(b.__den) - + long(b.__num) * long(a.__den), + long(a.__den) * long(b.__den)) + + def __rsub__(b, a): + return Rat(a) - b + + # a * b + def __mul__(a, b): + try: + return rat(a.__num * b.__num, a.__den * b.__den) + except OverflowError: + return rat(long(a.__num) * long(b.__num), + long(a.__den) * long(b.__den)) + + def __rmul__(b, a): + return Rat(a) * b + + # a / b + def __div__(a, b): + try: + return rat(a.__num * b.__den, a.__den * b.__num) + except OverflowError: + return rat(long(a.__num) * long(b.__den), + long(a.__den) * long(b.__num)) + + def __rdiv__(b, a): + return Rat(a) / b + + # a % b + def __mod__(a, b): + div = a / b + try: + div = int(div) + except OverflowError: + div = long(div) + return a - b * div + + def __rmod__(b, a): + return Rat(a) % b + + # a ** b + def __pow__(a, b): + if b.__den != 1: + if isinstance(a.__num, complex): + a = complex(a) + else: + a = float(a) + if isinstance(b.__num, complex): + b = complex(b) + else: + b = float(b) + return a ** b + try: + return rat(a.__num ** b.__num, a.__den ** b.__num) + except OverflowError: + return rat(long(a.__num) ** b.__num, + long(a.__den) ** b.__num) + + def __rpow__(b, a): + return Rat(a) ** b + + # -a + def __neg__(a): + try: + return rat(-a.__num, a.__den) + except OverflowError: + # a.__num == sys.maxint + return rat(-long(a.__num), a.__den) + + # abs(a) + def __abs__(a): + return rat(abs(a.__num), a.__den) + + # int(a) + def __int__(a): + return int(a.__num / a.__den) + + # long(a) + def __long__(a): + return long(a.__num) / long(a.__den) + + # float(a) + def __float__(a): + return float(a.__num) / float(a.__den) + + # complex(a) + def __complex__(a): + return complex(a.__num) / complex(a.__den) + + # cmp(a,b) + def __cmp__(a, b): + diff = Rat(a - b) + if diff.__num < 0: + return -1 + elif diff.__num > 0: + return 1 + else: + return 0 + + def __rcmp__(b, a): + return cmp(Rat(a), b) + + # a != 0 + def __nonzero__(a): + return a.__num != 0 + + # coercion + def __coerce__(a, b): + return a, Rat(b) def test(): - '''\ - Test function for rat module. - - The expected output is (module some differences in floating - precission): - -1 - -1 - 0 0L 0.1 (0.1+0j) - [Rat(1,2), Rat(-3,10), Rat(1,25), Rat(1,4)] - [Rat(-3,10), Rat(1,25), Rat(1,4), Rat(1,2)] - 0 - (11/10) - (11/10) - 1.1 - OK - 2 1.5 (3/2) (1.5+1.5j) (15707963/5000000) - 2 2 2.0 (2+0j) - - 4 0 4 1 4 0 - 3.5 0.5 3.0 1.33333333333 2.82842712475 1 - (7/2) (1/2) 3 (4/3) 2.82842712475 1 - (3.5+1.5j) (0.5-1.5j) (3+3j) (0.666666666667-0.666666666667j) (1.43248815986+2.43884761145j) 1 - 1.5 1 1.5 (1.5+0j) - - 3.5 -0.5 3.0 0.75 2.25 -1 - 3.0 0.0 2.25 1.0 1.83711730709 0 - 3.0 0.0 2.25 1.0 1.83711730709 1 - (3+1.5j) -1.5j (2.25+2.25j) (0.5-0.5j) (1.50768393746+1.04970907623j) -1 - (3/2) 1 1.5 (1.5+0j) - - (7/2) (-1/2) 3 (3/4) (9/4) -1 - 3.0 0.0 2.25 1.0 1.83711730709 -1 - 3 0 (9/4) 1 1.83711730709 0 - (3+1.5j) -1.5j (2.25+2.25j) (0.5-0.5j) (1.50768393746+1.04970907623j) -1 - (1.5+1.5j) (1.5+1.5j) - - (3.5+1.5j) (-0.5+1.5j) (3+3j) (0.75+0.75j) 4.5j -1 - (3+1.5j) 1.5j (2.25+2.25j) (1+1j) (1.18235814075+2.85446505899j) 1 - (3+1.5j) 1.5j (2.25+2.25j) (1+1j) (1.18235814075+2.85446505899j) 1 - (3+3j) 0j 4.5j (1+0j) (-0.638110484918+0.705394566962j) 0 - ''' - print rat(-1L, 1) - print rat(1, -1) - a = rat(1, 10) - print int(a), long(a), float(a), complex(a) - b = rat(2, 5) - l = [a+b, a-b, a*b, a/b] - print l - l.sort() - print l - print rat(0, 1) - print a+1 - print a+1L - print a+1.0 - try: - print rat(1, 0) - raise SystemError, 'should have been ZeroDivisionError' - except ZeroDivisionError: - print 'OK' - print rat(2), rat(1.5), rat(3, 2), rat(1.5+1.5j), rat(31415926,10000000) - list = [2, 1.5, rat(3,2), 1.5+1.5j] - for i in list: - print i, - if not isinstance(i, complex): - print int(i), float(i), - print complex(i) - print - for j in list: - print i + j, i - j, i * j, i / j, i ** j, - if not (isinstance(i, complex) or - isinstance(j, complex)): - print cmp(i, j) - print + '''\ + Test function for rat module. + + The expected output is (module some differences in floating + precission): + -1 + -1 + 0 0L 0.1 (0.1+0j) + [Rat(1,2), Rat(-3,10), Rat(1,25), Rat(1,4)] + [Rat(-3,10), Rat(1,25), Rat(1,4), Rat(1,2)] + 0 + (11/10) + (11/10) + 1.1 + OK + 2 1.5 (3/2) (1.5+1.5j) (15707963/5000000) + 2 2 2.0 (2+0j) + + 4 0 4 1 4 0 + 3.5 0.5 3.0 1.33333333333 2.82842712475 1 + (7/2) (1/2) 3 (4/3) 2.82842712475 1 + (3.5+1.5j) (0.5-1.5j) (3+3j) (0.666666666667-0.666666666667j) (1.43248815986+2.43884761145j) 1 + 1.5 1 1.5 (1.5+0j) + + 3.5 -0.5 3.0 0.75 2.25 -1 + 3.0 0.0 2.25 1.0 1.83711730709 0 + 3.0 0.0 2.25 1.0 1.83711730709 1 + (3+1.5j) -1.5j (2.25+2.25j) (0.5-0.5j) (1.50768393746+1.04970907623j) -1 + (3/2) 1 1.5 (1.5+0j) + + (7/2) (-1/2) 3 (3/4) (9/4) -1 + 3.0 0.0 2.25 1.0 1.83711730709 -1 + 3 0 (9/4) 1 1.83711730709 0 + (3+1.5j) -1.5j (2.25+2.25j) (0.5-0.5j) (1.50768393746+1.04970907623j) -1 + (1.5+1.5j) (1.5+1.5j) + + (3.5+1.5j) (-0.5+1.5j) (3+3j) (0.75+0.75j) 4.5j -1 + (3+1.5j) 1.5j (2.25+2.25j) (1+1j) (1.18235814075+2.85446505899j) 1 + (3+1.5j) 1.5j (2.25+2.25j) (1+1j) (1.18235814075+2.85446505899j) 1 + (3+3j) 0j 4.5j (1+0j) (-0.638110484918+0.705394566962j) 0 + ''' + print rat(-1L, 1) + print rat(1, -1) + a = rat(1, 10) + print int(a), long(a), float(a), complex(a) + b = rat(2, 5) + l = [a+b, a-b, a*b, a/b] + print l + l.sort() + print l + print rat(0, 1) + print a+1 + print a+1L + print a+1.0 + try: + print rat(1, 0) + raise SystemError, 'should have been ZeroDivisionError' + except ZeroDivisionError: + print 'OK' + print rat(2), rat(1.5), rat(3, 2), rat(1.5+1.5j), rat(31415926,10000000) + list = [2, 1.5, rat(3,2), 1.5+1.5j] + for i in list: + print i, + if not isinstance(i, complex): + print int(i), float(i), + print complex(i) + print + for j in list: + print i + j, i - j, i * j, i / j, i ** j, + if not (isinstance(i, complex) or + isinstance(j, complex)): + print cmp(i, j) + print if __name__ == '__main__': diff --git a/Demo/classes/Rev.py b/Demo/classes/Rev.py index c1874c6..467bd57 100755 --- a/Demo/classes/Rev.py +++ b/Demo/classes/Rev.py @@ -5,13 +5,13 @@ # # >>> for c in Rev( 'Hello World!' ) : sys.stdout.write( c ) # ... else: sys.stdout.write( '\n' ) -# ... +# ... # !dlroW olleH # # The .forw is so you can use anonymous sequences in __init__, and still -# keep a reference the forward sequence. ) +# keep a reference the forward sequence. ) # If you give it a non-anonymous mutable sequence, the reverse sequence -# will track the updated values. ( but not reassignment! - another +# will track the updated values. ( but not reassignment! - another # good reason to use anonymous values in creating the sequence to avoid # confusion. Maybe it should be change to copy input sequence to break # the connection completely ? ) @@ -19,14 +19,14 @@ # >>> nnn = range( 0, 3 ) # >>> rnn = Rev( nnn ) # >>> for n in rnn: print n -# ... +# ... # 2 # 1 # 0 -# >>> for n in range( 4, 6 ): nnn.append( n ) # update nnn -# ... -# >>> for n in rnn: print n # prints reversed updated values -# ... +# >>> for n in range( 4, 6 ): nnn.append( n ) # update nnn +# ... +# >>> for n in rnn: print n # prints reversed updated values +# ... # 5 # 4 # 2 @@ -35,55 +35,55 @@ # >>> nnn = nnn[1:-1] # >>> nnn # [1, 2, 4] -# >>> for n in rnn: print n # prints reversed values of old nnn -# ... +# >>> for n in rnn: print n # prints reversed values of old nnn +# ... # 5 # 4 # 2 # 1 # 0 -# >>> +# >>> # # WH = Rev( 'Hello World!' ) # print WH.forw, WH.back # nnn = Rev( range( 1, 10 ) ) # print nnn.forw # print nnn -# +# # produces output: -# +# # Hello World! !dlroW olleH # [1, 2, 3, 4, 5, 6, 7, 8, 9] # [9, 8, 7, 6, 5, 4, 3, 2, 1] -# -# >>>rrr = Rev( nnn ) +# +# >>>rrr = Rev( nnn ) # >>>rrr -# <1, 2, 3, 4, 5, 6, 7, 8, 9> +# <1, 2, 3, 4, 5, 6, 7, 8, 9> from string import joinfields class Rev: - def __init__( self, seq ): - self.forw = seq - self.back = self - def __len__( self ): - return len( self.forw ) - def __getitem__( self, j ): - return self.forw[ -( j + 1 ) ] - def __repr__( self ): - seq = self.forw - if type(seq) == type( [] ) : - wrap = '[]' - sep = ', ' - elif type(seq) == type( () ) : - wrap = '()' - sep = ', ' - elif type(seq) == type( '' ) : - wrap = '' - sep = '' - else: - wrap = '<>' - sep = ', ' - outstrs = [] - for item in self.back : - outstrs.append( str( item ) ) - return wrap[:1] + joinfields( outstrs, sep ) + wrap[-1:] + def __init__( self, seq ): + self.forw = seq + self.back = self + def __len__( self ): + return len( self.forw ) + def __getitem__( self, j ): + return self.forw[ -( j + 1 ) ] + def __repr__( self ): + seq = self.forw + if type(seq) == type( [] ) : + wrap = '[]' + sep = ', ' + elif type(seq) == type( () ) : + wrap = '()' + sep = ', ' + elif type(seq) == type( '' ) : + wrap = '' + sep = '' + else: + wrap = '<>' + sep = ', ' + outstrs = [] + for item in self.back : + outstrs.append( str( item ) ) + return wrap[:1] + joinfields( outstrs, sep ) + wrap[-1:] diff --git a/Demo/classes/Vec.py b/Demo/classes/Vec.py index 8289bc8..0a56ddb 100755 --- a/Demo/classes/Vec.py +++ b/Demo/classes/Vec.py @@ -2,63 +2,63 @@ def vec(*v): - return apply(Vec, v) + return apply(Vec, v) class Vec: - def __init__(self, *v): - self.v = [] - for x in v: - self.v.append(x) + def __init__(self, *v): + self.v = [] + for x in v: + self.v.append(x) - def fromlist(self, v): - self.v = [] - if type(v) <> type([]): - raise TypeError - self.v = v[:] - return self + def fromlist(self, v): + self.v = [] + if type(v) <> type([]): + raise TypeError + self.v = v[:] + return self - def __repr__(self): - return 'vec(' + `self.v`[1:-1] + ')' + def __repr__(self): + return 'vec(' + `self.v`[1:-1] + ')' - def __len__(self): - return len(self.v) + def __len__(self): + return len(self.v) - def __getitem__(self, i): - return self.v[i] + def __getitem__(self, i): + return self.v[i] - def __add__(a, b): - # Element-wise addition - v = [] - for i in range(len(a)): - v.append(a[i] + b[i]) - return Vec().fromlist(v) + def __add__(a, b): + # Element-wise addition + v = [] + for i in range(len(a)): + v.append(a[i] + b[i]) + return Vec().fromlist(v) - def __sub__(a, b): - # Element-wise subtraction - v = [] - for i in range(len(a)): - v.append(a[i] - b[i]) - return Vec().fromlist(v) + def __sub__(a, b): + # Element-wise subtraction + v = [] + for i in range(len(a)): + v.append(a[i] - b[i]) + return Vec().fromlist(v) - def __mul__(self, scalar): - # Multiply by scalar - v = [] - for i in range(len(self.v)): - v.append(self.v[i]*scalar) - return Vec().fromlist(v) + def __mul__(self, scalar): + # Multiply by scalar + v = [] + for i in range(len(self.v)): + v.append(self.v[i]*scalar) + return Vec().fromlist(v) def test(): - a = vec(1, 2, 3) - b = vec(3, 2, 1) - print a - print b - print a+b - print a*3.0 + a = vec(1, 2, 3) + b = vec(3, 2, 1) + print a + print b + print a+b + print a*3.0 test() 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('.' + '__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('.' + '__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 diff --git a/Demo/comparisons/regextest.py b/Demo/comparisons/regextest.py index 97564b7..e4e18d6 100755 --- a/Demo/comparisons/regextest.py +++ b/Demo/comparisons/regextest.py @@ -1,13 +1,13 @@ #! /usr/bin/env python # 1) Regular Expressions Test -# -# Read a file of (extended per egrep) regular expressions (one per line), +# +# Read a file of (extended per egrep) regular expressions (one per line), # and apply those to all files whose names are listed on the command line. # Basically, an 'egrep -f' simulator. Test it with 20 "vt100" patterns # against a five /etc/termcap files. Tests using more elaborate patters # would also be interesting. Your code should not break if given hundreds -# of regular expressions or binary files to scan. +# of regular expressions or binary files to scan. # This implementation: # - combines all patterns into a single one using ( ... | ... | ... ) @@ -24,27 +24,27 @@ from regex_syntax import * regex.set_syntax(RE_SYNTAX_EGREP) def main(): - pats = map(chomp, sys.stdin.readlines()) - bigpat = '(' + string.joinfields(pats, '|') + ')' - prog = regex.compile(bigpat) - - for file in sys.argv[1:]: - try: - fp = open(file, 'r') - except IOError, msg: - print "%s: %s" % (file, msg) - continue - lineno = 0 - while 1: - line = fp.readline() - if not line: - break - lineno = lineno + 1 - if prog.search(line) >= 0: - print "%s:%s:%s" % (file, lineno, line), + pats = map(chomp, sys.stdin.readlines()) + bigpat = '(' + string.joinfields(pats, '|') + ')' + prog = regex.compile(bigpat) + + for file in sys.argv[1:]: + try: + fp = open(file, 'r') + except IOError, msg: + print "%s: %s" % (file, msg) + continue + lineno = 0 + while 1: + line = fp.readline() + if not line: + break + lineno = lineno + 1 + if prog.search(line) >= 0: + print "%s:%s:%s" % (file, lineno, line), def chomp(s): - if s[-1:] == '\n': return s[:-1] - else: return s + if s[-1:] == '\n': return s[:-1] + else: return s main() diff --git a/Demo/comparisons/sortingtest.py b/Demo/comparisons/sortingtest.py index d6c213c..8fe2bbb 100755 --- a/Demo/comparisons/sortingtest.py +++ b/Demo/comparisons/sortingtest.py @@ -1,17 +1,17 @@ #! /usr/bin/env python # 2) Sorting Test -# +# # Sort an input file that consists of lines like this -# +# # var1=23 other=14 ditto=23 fred=2 -# +# # such that each output line is sorted WRT to the number. Order # of output lines does not change. Resolve collisions using the # variable name. e.g. -# -# fred=2 other=14 ditto=23 var1=23 -# +# +# fred=2 other=14 ditto=23 var1=23 +# # Lines may be up to several kilobytes in length and contain # zillions of variables. @@ -28,23 +28,23 @@ import string import sys def main(): - prog = regex.compile('^\(.*\)=\([-+]?[0-9]+\)') - def makekey(item, prog=prog): - if prog.match(item) >= 0: - var, num = prog.group(1, 2) - return string.atoi(num), var - else: - # Bad input -- pretend it's a var with value 0 - return 0, item - while 1: - line = sys.stdin.readline() - if not line: - break - items = string.split(line) - items = map(makekey, items) - items.sort() - for num, var in items: - print "%s=%s" % (var, num), - print + prog = regex.compile('^\(.*\)=\([-+]?[0-9]+\)') + def makekey(item, prog=prog): + if prog.match(item) >= 0: + var, num = prog.group(1, 2) + return string.atoi(num), var + else: + # Bad input -- pretend it's a var with value 0 + return 0, item + while 1: + line = sys.stdin.readline() + if not line: + break + items = string.split(line) + items = map(makekey, items) + items.sort() + for num, var in items: + print "%s=%s" % (var, num), + print main() diff --git a/Demo/comparisons/systemtest.py b/Demo/comparisons/systemtest.py index f2533b1..bbc313b 100755 --- a/Demo/comparisons/systemtest.py +++ b/Demo/comparisons/systemtest.py @@ -1,7 +1,7 @@ #! /usr/bin/env python # 3) System Test -# +# # Given a list of directories, report any bogus symbolic links contained # anywhere in those subtrees. A bogus symbolic link is one that cannot # be resolved because it points to a nonexistent or otherwise @@ -21,54 +21,54 @@ import sys from stat import * def main(): - try: - # Note: can't test for presence of lstat -- it's always there - dummy = os.readlink - except AttributeError: - print "This system doesn't have symbolic links" - sys.exit(0) - if sys.argv[1:]: - prefix = sys.argv[1] - else: - prefix = '' - if prefix: - os.chdir(prefix) - if prefix[-1:] != '/': prefix = prefix + '/' - reportboguslinks(prefix) - else: - reportboguslinks('') + try: + # Note: can't test for presence of lstat -- it's always there + dummy = os.readlink + except AttributeError: + print "This system doesn't have symbolic links" + sys.exit(0) + if sys.argv[1:]: + prefix = sys.argv[1] + else: + prefix = '' + if prefix: + os.chdir(prefix) + if prefix[-1:] != '/': prefix = prefix + '/' + reportboguslinks(prefix) + else: + reportboguslinks('') def reportboguslinks(prefix): - try: - names = os.listdir('.') - except os.error, msg: - print "%s%s: can't list: %s" % (prefix, '.', msg) - return - names.sort() - for name in names: - if name == os.curdir or name == os.pardir: - continue - try: - mode = os.lstat(name)[ST_MODE] - except os.error: - print "%s%s: can't stat: %s" % (prefix, name, msg) - continue - if S_ISLNK(mode): - try: - os.stat(name) - except os.error: - print "%s%s -> %s" % \ - (prefix, name, os.readlink(name)) - elif S_ISDIR(mode): - try: - os.chdir(name) - except os.error, msg: - print "%s%s: can't chdir: %s" % \ - (prefix, name, msg) - continue - try: - reportboguslinks(prefix + name + '/') - finally: - os.chdir('..') + try: + names = os.listdir('.') + except os.error, msg: + print "%s%s: can't list: %s" % (prefix, '.', msg) + return + names.sort() + for name in names: + if name == os.curdir or name == os.pardir: + continue + try: + mode = os.lstat(name)[ST_MODE] + except os.error: + print "%s%s: can't stat: %s" % (prefix, name, msg) + continue + if S_ISLNK(mode): + try: + os.stat(name) + except os.error: + print "%s%s -> %s" % \ + (prefix, name, os.readlink(name)) + elif S_ISDIR(mode): + try: + os.chdir(name) + except os.error, msg: + print "%s%s: can't chdir: %s" % \ + (prefix, name, msg) + continue + try: + reportboguslinks(prefix + name + '/') + finally: + os.chdir('..') main() -- cgit v0.12