home *** CD-ROM | disk | FTP | other *** search
/ H4CK3R 14 / hacker14.iso / programacao / pythonwin / python.exe / TEST_SORT.PY < prev    next >
Encoding:
Python Source  |  2003-01-02  |  4.1 KB  |  172 lines
  1. from test.test_support import verbose
  2. import random
  3.  
  4. nerrors = 0
  5.  
  6. def check(tag, expected, raw, compare=None):
  7.     global nerrors
  8.  
  9.     if verbose:
  10.         print "    checking", tag
  11.  
  12.     orig = raw[:]   # save input in case of error
  13.     if compare:
  14.         raw.sort(compare)
  15.     else:
  16.         raw.sort()
  17.  
  18.     if len(expected) != len(raw):
  19.         print "error in", tag
  20.         print "length mismatch;", len(expected), len(raw)
  21.         print expected
  22.         print orig
  23.         print raw
  24.         nerrors += 1
  25.         return
  26.  
  27.     for i, good in enumerate(expected):
  28.         maybe = raw[i]
  29.         if good is not maybe:
  30.             print "error in", tag
  31.             print "out of order at index", i, good, maybe
  32.             print expected
  33.             print orig
  34.             print raw
  35.             nerrors += 1
  36.             return
  37.  
  38. # Try a variety of sizes at and around powers of 2, and at powers of 10.
  39. sizes = [0]
  40. for power in range(1, 10):
  41.     n = 2 ** power
  42.     sizes.extend(range(n-1, n+2))
  43. sizes.extend([10, 100, 1000])
  44.  
  45. class Complains(object):
  46.     maybe_complain = True
  47.  
  48.     def __init__(self, i):
  49.         self.i = i
  50.  
  51.     def __lt__(self, other):
  52.         if Complains.maybe_complain and random.random() < 0.001:
  53.             if verbose:
  54.                 print "        complaining at", self, other
  55.             raise RuntimeError
  56.         return self.i < other.i
  57.  
  58.     def __repr__(self):
  59.         return "Complains(%d)" % self.i
  60.  
  61. class Stable(object):
  62.     def __init__(self, key, i):
  63.         self.key = key
  64.         self.index = i
  65.  
  66.     def __cmp__(self, other):
  67.         return cmp(self.key, other.key)
  68.  
  69.     def __repr__(self):
  70.         return "Stable(%d, %d)" % (self.key, self.index)
  71.  
  72. for n in sizes:
  73.     x = range(n)
  74.     if verbose:
  75.         print "Testing size", n
  76.  
  77.     s = x[:]
  78.     check("identity", x, s)
  79.  
  80.     s = x[:]
  81.     s.reverse()
  82.     check("reversed", x, s)
  83.  
  84.     s = x[:]
  85.     random.shuffle(s)
  86.     check("random permutation", x, s)
  87.  
  88.     y = x[:]
  89.     y.reverse()
  90.     s = x[:]
  91.     check("reversed via function", y, s, lambda a, b: cmp(b, a))
  92.  
  93.     if verbose:
  94.         print "    Checking against an insane comparison function."
  95.         print "        If the implementation isn't careful, this may segfault."
  96.     s = x[:]
  97.     s.sort(lambda a, b:  int(random.random() * 3) - 1)
  98.     check("an insane function left some permutation", x, s)
  99.  
  100.     x = [Complains(i) for i in x]
  101.     s = x[:]
  102.     random.shuffle(s)
  103.     Complains.maybe_complain = True
  104.     it_complained = False
  105.     try:
  106.         s.sort()
  107.     except RuntimeError:
  108.         it_complained = True
  109.     if it_complained:
  110.         Complains.maybe_complain = False
  111.         check("exception during sort left some permutation", x, s)
  112.  
  113.     s = [Stable(random.randrange(10), i) for i in xrange(n)]
  114.     augmented = [(e, e.index) for e in s]
  115.     augmented.sort()    # forced stable because ties broken by index
  116.     x = [e for e, i in augmented] # a stable sort of s
  117.     check("stability", x, s)
  118.  
  119. def bug453523():
  120.     global nerrors
  121.     from random import random
  122.  
  123.     # If this fails, the most likely outcome is a core dump.
  124.     if verbose:
  125.         print "Testing bug 453523 -- list.sort() crasher."
  126.  
  127.     class C:
  128.         def __lt__(self, other):
  129.             if L and random() < 0.75:
  130.                 pop()
  131.             else:
  132.                 push(3)
  133.             return random() < 0.5
  134.  
  135.     L = [C() for i in range(50)]
  136.     pop = L.pop
  137.     push = L.append
  138.     try:
  139.         L.sort()
  140.     except ValueError:
  141.         pass
  142.     else:
  143.         print "    Mutation during list.sort() wasn't caught."
  144.         nerrors += 1
  145.  
  146. bug453523()
  147.  
  148. def cmpNone():
  149.     global nerrors
  150.  
  151.     if verbose:
  152.         print "Testing None as a comparison function."
  153.  
  154.     L = range(50)
  155.     random.shuffle(L)
  156.     try:
  157.         L.sort(None)
  158.     except TypeError:
  159.         print "    Passing None as cmpfunc failed."
  160.         nerrors += 1
  161.     else:
  162.         if L != range(50):
  163.             print "    Passing None as cmpfunc failed."
  164.             nerrors += 1
  165.  
  166. cmpNone()
  167.  
  168. if nerrors:
  169.     print "Test failed", nerrors
  170. elif verbose:
  171.     print "Test passed -- no errors."
  172.