[Python-checkins] python/dist/src/Lib/test test_sort.py,NONE,1.1

[tim_one@users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Lib/test
In directory usw-pr-cvs1:/tmp/cvs-serv24012

Added Files:
	test_sort.py 
Log Message:
New test for sorting sanity.  Note that this will fail in earlier Pythons,
in the stability tests.

Bizarre:  this takes 11x longer to run if and only if test_longexp is
run before it, on my box.  The bigger REPS is in test_longexp, the
slower this gets.  What happens on your box?  It's not gc on my box
(which is good, because gc isn't a plausible candidate here).

The slowdown is massive in the parts of test_sort that implicitly
invoke a new-style class's __lt__ or __cmp__ methods.  If I boost
REPS large enough in test_longexp, even the test_sort tests on an array
of size 64 visibly c-r-a-w-l.  The relative slowdown is even worse in
a debug build.  And if I reduce REPS in test_longexp, the slowdown in
test_sort goes away.

test_longexp does do horrid things to Win98's management of user
address space, but I thought I had made that a whole lot better a month
or so ago (by overallocating aggressively in the parser).


--- NEW FILE: test_sort.py ---
from test.test_support import verbose
import random

nerrors = 0

def check(tag, expected, raw, compare=None):
    global nerrors

    if verbose:
        print "    checking", tag

    orig = raw[:]   # save input in case of error
    if compare:
        raw.sort(compare)
    else:
        raw.sort()

    if len(expected) != len(raw):
        print "error in", tag
        print "length mismatch;", len(expected), len(raw)
        print expected
        print orig
        print raw
        nerrors += 1
        return

    for i, good in enumerate(expected):
        maybe = raw[i]
        if good is not maybe:
            print "error in", tag
            print "out of order at index", i, good, maybe
            print expected
            print orig
            print raw
            nerrors += 1
            return

# Try a variety of sizes at and around powers of 2, and at powers of 10.
sizes = [0]
for power in range(1, 10):
    n = 2 ** power
    sizes.extend(range(n-1, n+2))
sizes.extend([10, 100, 1000])

class Complains(object):
    maybe_complain = True

    def __init__(self, i):
        self.i = i

    def __lt__(self, other):
        if Complains.maybe_complain and random.random() < 0.001:
            if verbose:
                print "        complaining at", self, other
            raise RuntimeError
        return self.i < other.i

    def __repr__(self):
        return "Complains(%d)" % self.i

class Stable(object):
    maybe_complain = True

    def __init__(self, key, i):
        self.key = key
        self.index = i

    def __cmp__(self, other):
        return cmp(self.key, other.key)

    def __repr__(self):
        return "Stable(%d, %d)" % (self.key, self.index)

for n in sizes:
    x = range(n)
    if verbose:
        print "Testing size", n

    s = x[:]
    check("identity", x, s)

    s = x[:]
    s.reverse()
    check("reversed", x, s)

    s = x[:]
    random.shuffle(s)
    check("random permutation", x, s)

    y = x[:]
    y.reverse()
    s = x[:]
    check("reversed via function", y, s, lambda a, b: cmp(b, a))

    if verbose:
        print "    Checking against an insane comparison function."
        print "        If the implementation isn't careful, this may segfault."
    s = x[:]
    s.sort(lambda a, b:  int(random.random() * 3) - 1)
    check("an insane function left some permutation", x, s)

    x = [Complains(i) for i in x]
    s = x[:]
    random.shuffle(s)
    Complains.maybe_complain = True
    it_complained = False
    try:
        s.sort()
    except RuntimeError:
        it_complained = True
    if it_complained:
        Complains.maybe_complain = False
        check("exception during sort left some permutation", x, s)

    s = [Stable(random.randrange(10), i) for i in xrange(n)]
    augmented = [(e, e.index) for e in s]
    augmented.sort()    # forced stable because ties broken by index
    x = [e for e, i in augmented] # a stable sort of s
    check("stability", x, s)

if nerrors:
    print "Test failed", nerrors
elif verbose:
    print "Test passed -- no errors."