← Back to branch summary

~ubuntu-branches/ubuntu/karmic/pypy/karmic

« back to all changes in this revision

Viewing changes to lib-python/2.4.1/test/test_sort.py

  • Committer: Bazaar Package Importer
  • Author(s): Alexandre Fayolle
  • Date: 2007-04-13 09:33:09 UTC
  • Revision ID: james.westby@ubuntu.com-20070413093309-yoojh4jcoocu2krz
Tags: upstream-1.0.0
Import upstream version 1.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib-python/2.4.1/test/test_sort.py
 
1
from test.test_support import verbose
 
2
import random
 
3
from UserList import UserList
 
4
 
 
5
nerrors = 0
 
6
 
 
7
def check(tag, expected, raw, compare=None):
 
8
    global nerrors
 
9
 
 
10
    if verbose:
 
11
        print "    checking", tag
 
12
 
 
13
    orig = raw[:]   # save input in case of error
 
14
    if compare:
 
15
        raw.sort(compare)
 
16
    else:
 
17
        raw.sort()
 
18
 
 
19
    if len(expected) != len(raw):
 
20
        print "error in", tag
 
21
        print "length mismatch;", len(expected), len(raw)
 
22
        print expected
 
23
        print orig
 
24
        print raw
 
25
        nerrors += 1
 
26
        return
 
27
 
 
28
    for i, good in enumerate(expected):
 
29
        maybe = raw[i]
 
30
        if good is not maybe:
 
31
            print "error in", tag
 
32
            print "out of order at index", i, good, maybe
 
33
            print expected
 
34
            print orig
 
35
            print raw
 
36
            nerrors += 1
 
37
            return
 
38
 
 
39
# Try a variety of sizes at and around powers of 2, and at powers of 10.
 
40
sizes = [0]
 
41
for power in range(1, 10):
 
42
    n = 2 ** power
 
43
    sizes.extend(range(n-1, n+2))
 
44
sizes.extend([10, 100, 1000])
 
45
 
 
46
class Complains(object):
 
47
    maybe_complain = True
 
48
 
 
49
    def __init__(self, i):
 
50
        self.i = i
 
51
 
 
52
    def __lt__(self, other):
 
53
        if Complains.maybe_complain and random.random() < 0.001:
 
54
            if verbose:
 
55
                print "        complaining at", self, other
 
56
            raise RuntimeError
 
57
        return self.i < other.i
 
58
 
 
59
    def __repr__(self):
 
60
        return "Complains(%d)" % self.i
 
61
 
 
62
class Stable(object):
 
63
    def __init__(self, key, i):
 
64
        self.key = key
 
65
        self.index = i
 
66
 
 
67
    def __cmp__(self, other):
 
68
        return cmp(self.key, other.key)
 
69
 
 
70
    def __repr__(self):
 
71
        return "Stable(%d, %d)" % (self.key, self.index)
 
72
 
 
73
for n in sizes:
 
74
    x = range(n)
 
75
    if verbose:
 
76
        print "Testing size", n
 
77
 
 
78
    s = x[:]
 
79
    check("identity", x, s)
 
80
 
 
81
    s = x[:]
 
82
    s.reverse()
 
83
    check("reversed", x, s)
 
84
 
 
85
    s = x[:]
 
86
    random.shuffle(s)
 
87
    check("random permutation", x, s)
 
88
 
 
89
    y = x[:]
 
90
    y.reverse()
 
91
    s = x[:]
 
92
    check("reversed via function", y, s, lambda a, b: cmp(b, a))
 
93
 
 
94
    if verbose:
 
95
        print "    Checking against an insane comparison function."
 
96
        print "        If the implementation isn't careful, this may segfault."
 
97
    s = x[:]
 
98
    s.sort(lambda a, b:  int(random.random() * 3) - 1)
 
99
    check("an insane function left some permutation", x, s)
 
100
 
 
101
    x = [Complains(i) for i in x]
 
102
    s = x[:]
 
103
    random.shuffle(s)
 
104
    Complains.maybe_complain = True
 
105
    it_complained = False
 
106
    try:
 
107
        s.sort()
 
108
    except RuntimeError:
 
109
        it_complained = True
 
110
    if it_complained:
 
111
        Complains.maybe_complain = False
 
112
        check("exception during sort left some permutation", x, s)
 
113
 
 
114
    s = [Stable(random.randrange(10), i) for i in xrange(n)]
 
115
    augmented = [(e, e.index) for e in s]
 
116
    augmented.sort()    # forced stable because ties broken by index
 
117
    x = [e for e, i in augmented] # a stable sort of s
 
118
    check("stability", x, s)
 
119
 
 
120
 
 
121
import unittest
 
122
from test import test_support
 
123
import sys
 
124
 
 
125
#==============================================================================
 
126
 
 
127
class TestBugs(unittest.TestCase):
 
128
 
 
129
    def test_bug453523(self):
 
130
        # bug 453523 -- list.sort() crasher.
 
131
        # If this fails, the most likely outcome is a core dump.
 
132
        # Mutations during a list sort should raise a ValueError.
 
133
 
 
134
        class C:
 
135
            def __lt__(self, other):
 
136
                if L and random.random() < 0.75:
 
137
                    L.pop()
 
138
                else:
 
139
                    L.append(3)
 
140
                return random.random() < 0.5
 
141
 
 
142
        L = [C() for i in range(50)]
 
143
        self.assertRaises(ValueError, L.sort)
 
144
 
 
145
    def test_cmpNone(self):
 
146
        # Testing None as a comparison function.
 
147
 
 
148
        L = range(50)
 
149
        random.shuffle(L)
 
150
        L.sort(None)
 
151
        self.assertEqual(L, range(50))
 
152
 
 
153
    def test_undetected_mutation(self):
 
154
        # Python 2.4a1 did not always detect mutation
 
155
        memorywaster = []
 
156
        for i in range(20):
 
157
            def mutating_cmp(x, y):
 
158
                L.append(3)
 
159
                L.pop()
 
160
                return cmp(x, y)
 
161
            L = [1,2]
 
162
            self.assertRaises(ValueError, L.sort, mutating_cmp)
 
163
            def mutating_cmp(x, y):
 
164
                L.append(3)
 
165
                del L[:]
 
166
                return cmp(x, y)
 
167
            self.assertRaises(ValueError, L.sort, mutating_cmp)
 
168
            memorywaster = [memorywaster]
 
169
 
 
170
#==============================================================================
 
171
 
 
172
class TestDecorateSortUndecorate(unittest.TestCase):
 
173
 
 
174
    def test_decorated(self):
 
175
        data = 'The quick Brown fox Jumped over The lazy Dog'.split()
 
176
        copy = data[:]
 
177
        random.shuffle(data)
 
178
        data.sort(key=str.lower)
 
179
        copy.sort(cmp=lambda x,y: cmp(x.lower(), y.lower()))
 
180
 
 
181
    def test_baddecorator(self):
 
182
        data = 'The quick Brown fox Jumped over The lazy Dog'.split()
 
183
        self.assertRaises(TypeError, data.sort, None, lambda x,y: 0)
 
184
 
 
185
    def test_stability(self):
 
186
        data = [(random.randrange(100), i) for i in xrange(200)]
 
187
        copy = data[:]
 
188
        data.sort(key=lambda (x,y): x)  # sort on the random first field
 
189
        copy.sort()                     # sort using both fields
 
190
        self.assertEqual(data, copy)    # should get the same result
 
191
 
 
192
    def test_cmp_and_key_combination(self):
 
193
        # Verify that the wrapper has been removed
 
194
        def compare(x, y):
 
195
            self.assertEqual(type(x), str)
 
196
            self.assertEqual(type(x), str)
 
197
            return cmp(x, y)
 
198
        data = 'The quick Brown fox Jumped over The lazy Dog'.split()
 
199
        data.sort(cmp=compare, key=str.lower)
 
200
 
 
201
    def test_badcmp_with_key(self):
 
202
        # Verify that the wrapper has been removed
 
203
        data = 'The quick Brown fox Jumped over The lazy Dog'.split()
 
204
        self.assertRaises(TypeError, data.sort, "bad", str.lower)
 
205
 
 
206
    def test_key_with_exception(self):
 
207
        # Verify that the wrapper has been removed
 
208
        data = range(-2,2)
 
209
        dup = data[:]
 
210
        self.assertRaises(ZeroDivisionError, data.sort, None, lambda x: 1/x)
 
211
        self.assertEqual(data, dup)
 
212
 
 
213
    def test_key_with_mutation(self):
 
214
        data = range(10)
 
215
        def k(x):
 
216
            del data[:]
 
217
            data[:] = range(20)
 
218
            return x
 
219
        self.assertRaises(ValueError, data.sort, key=k)
 
220
 
 
221
    def test_key_with_mutating_del(self):
 
222
        data = range(10)
 
223
        class SortKiller(object):
 
224
            def __init__(self, x):
 
225
                pass
 
226
            def __del__(self):
 
227
                del data[:]
 
228
                data[:] = range(20)
 
229
        self.assertRaises(ValueError, data.sort, key=SortKiller)
 
230
 
 
231
    def test_key_with_mutating_del_and_exception(self):
 
232
        data = range(10)
 
233
        ## dup = data[:]
 
234
        class SortKiller(object):
 
235
            def __init__(self, x):
 
236
                if x > 2:
 
237
                    raise RuntimeError
 
238
            def __del__(self):
 
239
                del data[:]
 
240
                data[:] = range(20)
 
241
        self.assertRaises(RuntimeError, data.sort, key=SortKiller)
 
242
        ## major honking subtlety: we *can't* do:
 
243
        ##
 
244
        ## self.assertEqual(data, dup)
 
245
        ##
 
246
        ## because there is a reference to a SortKiller in the
 
247
        ## traceback and by the time it dies we're outside the call to
 
248
        ## .sort() and so the list protection gimmicks are out of
 
249
        ## date (this cost some brain cells to figure out...).
 
250
 
 
251
    def test_reverse(self):
 
252
        data = range(100)
 
253
        random.shuffle(data)
 
254
        data.sort(reverse=True)
 
255
        self.assertEqual(data, range(99,-1,-1))
 
256
        self.assertRaises(TypeError, data.sort, "wrong type")
 
257
 
 
258
    def test_reverse_stability(self):
 
259
        data = [(random.randrange(100), i) for i in xrange(200)]
 
260
        copy1 = data[:]
 
261
        copy2 = data[:]
 
262
        data.sort(cmp=lambda x,y: cmp(x[0],y[0]), reverse=True)
 
263
        copy1.sort(cmp=lambda x,y: cmp(y[0],x[0]))
 
264
        self.assertEqual(data, copy1)
 
265
        copy2.sort(key=lambda x: x[0], reverse=True)
 
266
        self.assertEqual(data, copy2)
 
267
 
 
268
#==============================================================================
 
269
 
 
270
def test_main(verbose=None):
 
271
    test_classes = (
 
272
        TestDecorateSortUndecorate,
 
273
        TestBugs,
 
274
    )
 
275
 
 
276
    test_support.run_unittest(*test_classes)
 
277
 
 
278
    # verify reference counting
 
279
    if verbose and hasattr(sys, "gettotalrefcount"):
 
280
        import gc
 
281
        counts = [None] * 5
 
282
        for i in xrange(len(counts)):
 
283
            test_support.run_unittest(*test_classes)
 
284
            gc.collect()
 
285
            counts[i] = sys.gettotalrefcount()
 
286
        print counts
 
287
 
 
288
if __name__ == "__main__":
 
289
    test_main(verbose=True)