Debian Codegraph @

Lib/test/test_heapq.py

raw
1 """Unittests for heapq."""
2
3 import random
4 import unittest
5 import doctest
6
7 from test.support import import_helper
8 from unittest import TestCase, skipUnless
9 from operator import itemgetter
10
11 py_heapq = import_helper.import_fresh_module('heapq', blocked=['_heapq'])
12 c_heapq = import_helper.import_fresh_module('heapq', fresh=['_heapq'])
13
14 # _heapq.nlargest/nsmallest are saved in heapq._nlargest/_smallest when
15 # _heapq is imported, so check them there
16 func_names = ['heapify', 'heappop', 'heappush', 'heappushpop', 'heapreplace']
17 # Add max-heap variants
18 func_names += [func + '_max' for func in func_names]
19
20 class TestModules(TestCase):
21 def test_py_functions(self):
22 for fname in func_names:
23 self.assertEqual(getattr(py_heapq, fname).__module__, 'heapq')
24
25 @skipUnless(c_heapq, 'requires _heapq')
26 def test_c_functions(self):
27 for fname in func_names:
28 self.assertEqual(getattr(c_heapq, fname).__module__, '_heapq', fname)
29
30
31 def load_tests(loader, tests, ignore):
32 # The 'merge' function has examples in its docstring which we should test
33 # with 'doctest'.
34 #
35 # However, doctest can't easily find all docstrings in the module (loading
36 # it through import_fresh_module seems to confuse it), so we specifically
37 # create a finder which returns the doctests from the merge method.
38
39 class HeapqMergeDocTestFinder:
40 def find(self, *args, **kwargs):
41 dtf = doctest.DocTestFinder()
42 return dtf.find(py_heapq.merge)
43
44 tests.addTests(doctest.DocTestSuite(py_heapq,
45 test_finder=HeapqMergeDocTestFinder()))
46 return tests
47
48 class TestHeap:
49
50 def test_push_pop(self):
51 # 1) Push 256 random numbers and pop them off, verifying all's OK.
52 heap = []
53 data = []
54 self.check_invariant(heap)
55 for i in range(256):
56 item = random.random()
57 data.append(item)
58 self.module.heappush(heap, item)
59 self.check_invariant(heap)
60 results = []
61 while heap:
62 item = self.module.heappop(heap)
63 self.check_invariant(heap)
64 results.append(item)
65 data_sorted = data[:]
66 data_sorted.sort()
67 self.assertEqual(data_sorted, results)
68 # 2) Check that the invariant holds for a sorted array
69 self.check_invariant(results)
70
71 self.assertRaises(TypeError, self.module.heappush, [])
72 try:
73 self.assertRaises(TypeError, self.module.heappush, None, None)
74 self.assertRaises(TypeError, self.module.heappop, None)
75 except AttributeError:
76 pass
77
78 def test_max_push_pop(self):
79 # 1) Push 256 random numbers and pop them off, verifying all's OK.
80 heap = []
81 data = []
82 self.check_max_invariant(heap)
83 for i in range(256):
84 item = random.random()
85 data.append(item)
86 self.module.heappush_max(heap, item)
87 self.check_max_invariant(heap)
88 results = []
89 while heap:
90 item = self.module.heappop_max(heap)
91 self.check_max_invariant(heap)
92 results.append(item)
93 data_sorted = data[:]
94 data_sorted.sort(reverse=True)
95
96 self.assertEqual(data_sorted, results)
97 # 2) Check that the invariant holds for a sorted array
98 self.check_max_invariant(results)
99
100 self.assertRaises(TypeError, self.module.heappush_max, [])
101
102 exc_types = (AttributeError, TypeError)
103 self.assertRaises(exc_types, self.module.heappush_max, None, None)
104 self.assertRaises(exc_types, self.module.heappop_max, None)
105
106 def check_invariant(self, heap):
107 # Check the heap invariant.
108 for pos, item in enumerate(heap):
109 if pos: # pos 0 has no parent
110 parentpos = (pos-1) >> 1
111 self.assertTrue(heap[parentpos] <= item)
112
113 def check_max_invariant(self, heap):
114 for pos, item in enumerate(heap[1:], start=1):
115 parentpos = (pos - 1) >> 1
116 self.assertGreaterEqual(heap[parentpos], item)
117
118 def test_heapify(self):
119 for size in list(range(30)) + [20000]:
120 heap = [random.random() for dummy in range(size)]
121 self.module.heapify(heap)
122 self.check_invariant(heap)
123
124 self.assertRaises(TypeError, self.module.heapify, None)
125
126 def test_heapify_max(self):
127 for size in list(range(30)) + [20000]:
128 heap = [random.random() for dummy in range(size)]
129 self.module.heapify_max(heap)
130 self.check_max_invariant(heap)
131
132 self.assertRaises(TypeError, self.module.heapify_max, None)
133
134 def test_naive_nbest(self):
135 data = [random.randrange(2000) for i in range(1000)]
136 heap = []
137 for item in data:
138 self.module.heappush(heap, item)
139 if len(heap) > 10:
140 self.module.heappop(heap)
141 heap.sort()
142 self.assertEqual(heap, sorted(data)[-10:])
143
144 def heapiter(self, heap):
145 # An iterator returning a heap's elements, smallest-first.
146 try:
147 while 1:
148 yield self.module.heappop(heap)
149 except IndexError:
150 pass
151
152 def test_nbest(self):
153 # Less-naive "N-best" algorithm, much faster (if len(data) is big
154 # enough <wink>) than sorting all of data.
155 data = [random.randrange(2000) for i in range(1000)]
156 heap = data[:10]
157 self.module.heapify(heap)
158 for item in data[10:]:
159 if item > heap[0]: # this gets rarer the longer we run
160 self.module.heapreplace(heap, item)
161 self.assertEqual(list(self.heapiter(heap)), sorted(data)[-10:])
162
163 self.assertRaises(TypeError, self.module.heapreplace, None)
164 self.assertRaises(TypeError, self.module.heapreplace, None, None)
165 self.assertRaises(IndexError, self.module.heapreplace, [], None)
166
167 def test_nbest_maxheap(self):
168 # With a max heap instead of a min heap, the "N-best" algorithm can
169 # go even faster still via heapify'ing all of data (linear time), then
170 # doing 10 heappops (10 log-time steps).
171 data = [random.randrange(2000) for i in range(1000)]
172 heap = data[:]
173 self.module.heapify_max(heap)
174 result = [self.module.heappop_max(heap) for _ in range(10)]
175 result.reverse()
176 self.assertEqual(result, sorted(data)[-10:])
177
178 def test_nbest_with_pushpop(self):
179 data = [random.randrange(2000) for i in range(1000)]
180 heap = data[:10]
181 self.module.heapify(heap)
182 for item in data[10:]:
183 self.module.heappushpop(heap, item)
184 self.assertEqual(list(self.heapiter(heap)), sorted(data)[-10:])
185 self.assertEqual(self.module.heappushpop([], 'x'), 'x')
186
187 def test_naive_nworst(self):
188 # Max-heap variant of "test_naive_nbest"
189 data = [random.randrange(2000) for i in range(1000)]
190 heap = []
191 for item in data:
192 self.module.heappush_max(heap, item)
193 if len(heap) > 10:
194 self.module.heappop_max(heap)
195 heap.sort()
196 expected = sorted(data)[:10]
197 self.assertEqual(heap, expected)
198
199 def heapiter_max(self, heap):
200 # An iterator returning a max-heap's elements, largest-first.
201 try:
202 while 1:
203 yield self.module.heappop_max(heap)
204 except IndexError:
205 pass
206
207 def test_nworst(self):
208 # Max-heap variant of "test_nbest"
209 data = [random.randrange(2000) for i in range(1000)]
210 heap = data[:10]
211 self.module.heapify_max(heap)
212 for item in data[10:]:
213 if item < heap[0]: # this gets rarer the longer we run
214 self.module.heapreplace_max(heap, item)
215 expected = sorted(data, reverse=True)[-10:]
216 self.assertEqual(list(self.heapiter_max(heap)), expected)
217
218 self.assertRaises(TypeError, self.module.heapreplace_max, None)
219 self.assertRaises(TypeError, self.module.heapreplace_max, None, None)
220 self.assertRaises(IndexError, self.module.heapreplace_max, [], None)
221
222 def test_nworst_minheap(self):
223 # Min-heap variant of "test_nbest_maxheap"
224 data = [random.randrange(2000) for i in range(1000)]
225 heap = data[:]
226 self.module.heapify(heap)
227 result = [self.module.heappop(heap) for _ in range(10)]
228 result.reverse()
229 expected = sorted(data, reverse=True)[-10:]
230 self.assertEqual(result, expected)
231
232 def test_nworst_with_pushpop(self):
233 # Max-heap variant of "test_nbest_with_pushpop"
234 data = [random.randrange(2000) for i in range(1000)]
235 heap = data[:10]
236 self.module.heapify_max(heap)
237 for item in data[10:]:
238 self.module.heappushpop_max(heap, item)
239 expected = sorted(data, reverse=True)[-10:]
240 self.assertEqual(list(self.heapiter_max(heap)), expected)
241 self.assertEqual(self.module.heappushpop_max([], 'x'), 'x')
242
243 def test_heappushpop(self):
244 h = []
245 x = self.module.heappushpop(h, 10)
246 self.assertEqual((h, x), ([], 10))
247
248 h = [10]
249 x = self.module.heappushpop(h, 10.0)
250 self.assertEqual((h, x), ([10], 10.0))
251 self.assertEqual(type(h[0]), int)
252 self.assertEqual(type(x), float)
253
254 h = [10]
255 x = self.module.heappushpop(h, 9)
256 self.assertEqual((h, x), ([10], 9))
257
258 h = [10]
259 x = self.module.heappushpop(h, 11)
260 self.assertEqual((h, x), ([11], 10))
261
262 def test_heappushpop_max(self):
263 h = []
264 x = self.module.heappushpop_max(h, 10)
265 self.assertTupleEqual((h, x), ([], 10))
266
267 h = [10]
268 x = self.module.heappushpop_max(h, 10.0)
269 self.assertTupleEqual((h, x), ([10], 10.0))
270 self.assertIsInstance(h[0], int)
271 self.assertIsInstance(x, float)
272
273 h = [10]
274 x = self.module.heappushpop_max(h, 11)
275 self.assertTupleEqual((h, x), ([10], 11))
276
277 h = [10]
278 x = self.module.heappushpop_max(h, 9)
279 self.assertTupleEqual((h, x), ([9], 10))
280
281 def test_heappop_max(self):
282 # heapop_max has an optimization for one-item lists which isn't
283 # covered in other tests, so test that case explicitly here
284 h = [3, 2]
285 self.assertEqual(self.module.heappop_max(h), 3)
286 self.assertEqual(self.module.heappop_max(h), 2)
287
288 def test_heapsort(self):
289 # Exercise everything with repeated heapsort checks
290 for trial in range(100):
291 size = random.randrange(50)
292 data = [random.randrange(25) for i in range(size)]
293 if trial & 1: # Half of the time, use heapify
294 heap = data[:]
295 self.module.heapify(heap)
296 else: # The rest of the time, use heappush
297 heap = []
298 for item in data:
299 self.module.heappush(heap, item)
300 heap_sorted = [self.module.heappop(heap) for i in range(size)]
301 self.assertEqual(heap_sorted, sorted(data))
302
303 def test_heapsort_max(self):
304 for trial in range(100):
305 size = random.randrange(50)
306 data = [random.randrange(25) for i in range(size)]
307 if trial & 1: # Half of the time, use heapify_max
308 heap = data[:]
309 self.module.heapify_max(heap)
310 else: # The rest of the time, use heappush_max
311 heap = []
312 for item in data:
313 self.module.heappush_max(heap, item)
314 heap_sorted = [self.module.heappop_max(heap) for i in range(size)]
315 self.assertEqual(heap_sorted, sorted(data, reverse=True))
316
317 def test_merge(self):
318 inputs = []
319 for i in range(random.randrange(25)):
320 row = []
321 for j in range(random.randrange(100)):
322 tup = random.choice('ABC'), random.randrange(-500, 500)
323 row.append(tup)
324 inputs.append(row)
325
326 for key in [None, itemgetter(0), itemgetter(1), itemgetter(1, 0)]:
327 for reverse in [False, True]:
328 seqs = []
329 for seq in inputs:
330 seqs.append(sorted(seq, key=key, reverse=reverse))
331 self.assertEqual(sorted(chain(*inputs), key=key, reverse=reverse),
332 list(self.module.merge(*seqs, key=key, reverse=reverse)))
333 self.assertEqual(list(self.module.merge()), [])
334
335 def test_empty_merges(self):
336 # Merging two empty lists (with or without a key) should produce
337 # another empty list.
338 self.assertEqual(list(self.module.merge([], [])), [])
339 self.assertEqual(list(self.module.merge([], [], key=lambda: 6)), [])
340
341 def test_merge_does_not_suppress_index_error(self):
342 # Issue 19018: Heapq.merge suppresses IndexError from user generator
343 def iterable():
344 s = list(range(10))
345 for i in range(20):
346 yield s[i] # IndexError when i > 10
347 with self.assertRaises(IndexError):
348 list(self.module.merge(iterable(), iterable()))
349
350 def test_merge_stability(self):
351 class Int(int):
352 pass
353 inputs = [[], [], [], []]
354 for i in range(20000):
355 stream = random.randrange(4)
356 x = random.randrange(500)
357 obj = Int(x)
358 obj.pair = (x, stream)
359 inputs[stream].append(obj)
360 for stream in inputs:
361 stream.sort()
362 result = [i.pair for i in self.module.merge(*inputs)]
363 self.assertEqual(result, sorted(result))
364
365 def test_nsmallest(self):
366 data = [(random.randrange(2000), i) for i in range(1000)]
367 for f in (None, lambda x: x[0] * 547 % 2000):
368 for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):
369 self.assertEqual(list(self.module.nsmallest(n, data)),
370 sorted(data)[:n])
371 self.assertEqual(list(self.module.nsmallest(n, data, key=f)),
372 sorted(data, key=f)[:n])
373
374 def test_nlargest(self):
375 data = [(random.randrange(2000), i) for i in range(1000)]
376 for f in (None, lambda x: x[0] * 547 % 2000):
377 for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):
378 self.assertEqual(list(self.module.nlargest(n, data)),
379 sorted(data, reverse=True)[:n])
380 self.assertEqual(list(self.module.nlargest(n, data, key=f)),
381 sorted(data, key=f, reverse=True)[:n])
382
383 def test_comparison_operator(self):
384 # Issue 3051: Make sure heapq works with both __lt__
385 # For python 3.0, __le__ alone is not enough
386 def hsort(data, comp):
387 data = [comp(x) for x in data]
388 self.module.heapify(data)
389 return [self.module.heappop(data).x for i in range(len(data))]
390 class LT:
391 def __init__(self, x):
392 self.x = x
393 def __lt__(self, other):
394 return self.x > other.x
395 class LE:
396 def __init__(self, x):
397 self.x = x
398 def __le__(self, other):
399 return self.x >= other.x
400 data = [random.random() for i in range(100)]
401 target = sorted(data, reverse=True)
402 self.assertEqual(hsort(data, LT), target)
403 self.assertRaises(TypeError, data, LE)
404
405
406 class TestHeapPython(TestHeap, TestCase):
407 module = py_heapq
408
409
410 @skipUnless(c_heapq, 'requires _heapq')
411 class TestHeapC(TestHeap, TestCase):
412 module = c_heapq
413
414
415 #==============================================================================
416
417 class LenOnly:
418 "Dummy sequence class defining __len__ but not __getitem__."
419 def __len__(self):
420 return 10
421
422 class CmpErr:
423 "Dummy element that always raises an error during comparison"
424 def __eq__(self, other):
425 raise ZeroDivisionError
426 __ne__ = __lt__ = __le__ = __gt__ = __ge__ = __eq__
427
428 def R(seqn):
429 'Regular generator'
430 for i in seqn:
431 yield i
432
433 class G:
434 'Sequence using __getitem__'
435 def __init__(self, seqn):
436 self.seqn = seqn
437 def __getitem__(self, i):
438 return self.seqn[i]
439
440 class I:
441 'Sequence using iterator protocol'
442 def __init__(self, seqn):
443 self.seqn = seqn
444 self.i = 0
445 def __iter__(self):
446 return self
447 def __next__(self):
448 if self.i >= len(self.seqn): raise StopIteration
449 v = self.seqn[self.i]
450 self.i += 1
451 return v
452
453 class Ig:
454 'Sequence using iterator protocol defined with a generator'
455 def __init__(self, seqn):
456 self.seqn = seqn
457 self.i = 0
458 def __iter__(self):
459 for val in self.seqn:
460 yield val
461
462 class X:
463 'Missing __getitem__ and __iter__'
464 def __init__(self, seqn):
465 self.seqn = seqn
466 self.i = 0
467 def __next__(self):
468 if self.i >= len(self.seqn): raise StopIteration
469 v = self.seqn[self.i]
470 self.i += 1
471 return v
472
473 class N:
474 'Iterator missing __next__()'
475 def __init__(self, seqn):
476 self.seqn = seqn
477 self.i = 0
478 def __iter__(self):
479 return self
480
481 class E:
482 'Test propagation of exceptions'
483 def __init__(self, seqn):
484 self.seqn = seqn
485 self.i = 0
486 def __iter__(self):
487 return self
488 def __next__(self):
489 3 // 0
490
491 class S:
492 'Test immediate stop'
493 def __init__(self, seqn):
494 pass
495 def __iter__(self):
496 return self
497 def __next__(self):
498 raise StopIteration
499
500 from itertools import chain
501 def L(seqn):
502 'Test multiple tiers of iterators'
503 return chain(map(lambda x:x, R(Ig(G(seqn)))))
504
505
506 class SideEffectLT:
507 def __init__(self, value, heap):
508 self.value = value
509 self.heap = heap
510
511 def __lt__(self, other):
512 self.heap[:] = []
513 return self.value < other.value
514
515
516 class TestErrorHandling:
517
518 def test_non_sequence(self):
519 for f in (self.module.heapify, self.module.heappop,
520 self.module.heapify_max, self.module.heappop_max):
521 self.assertRaises((TypeError, AttributeError), f, 10)
522 for f in (self.module.heappush, self.module.heapreplace,
523 self.module.heappush_max, self.module.heapreplace_max,
524 self.module.nlargest, self.module.nsmallest):
525 self.assertRaises((TypeError, AttributeError), f, 10, 10)
526
527 def test_len_only(self):
528 for f in (self.module.heapify, self.module.heappop,
529 self.module.heapify_max, self.module.heappop_max):
530 self.assertRaises((TypeError, AttributeError), f, LenOnly())
531 for f in (self.module.heappush, self.module.heapreplace,
532 self.module.heappush_max, self.module.heapreplace_max):
533 self.assertRaises((TypeError, AttributeError), f, LenOnly(), 10)
534 for f in (self.module.nlargest, self.module.nsmallest):
535 self.assertRaises(TypeError, f, 2, LenOnly())
536
537 def test_cmp_err(self):
538 seq = [CmpErr(), CmpErr(), CmpErr()]
539 for f in (self.module.heapify, self.module.heappop):
540 self.assertRaises(ZeroDivisionError, f, seq)
541 for f in (self.module.heappush, self.module.heapreplace,
542 self.module.heappush_max, self.module.heapreplace_max):
543 self.assertRaises(ZeroDivisionError, f, seq, 10)
544 for f in (self.module.nlargest, self.module.nsmallest):
545 self.assertRaises(ZeroDivisionError, f, 2, seq)
546
547 def test_arg_parsing(self):
548 for f in (self.module.heapify, self.module.heappop,
549 self.module.heappush, self.module.heapreplace,
550 self.module.heapify_max, self.module.heappop_max,
551 self.module.heappush_max, self.module.heapreplace_max,
552 self.module.nlargest, self.module.nsmallest):
553 self.assertRaises((TypeError, AttributeError), f, 10)
554
555 def test_iterable_args(self):
556 for f in (self.module.nlargest, self.module.nsmallest):
557 for s in ("123", "", range(1000), (1, 1.2), range(2000,2200,5)):
558 for g in (G, I, Ig, L, R):
559 self.assertEqual(list(f(2, g(s))), list(f(2,s)))
560 self.assertEqual(list(f(2, S(s))), [])
561 self.assertRaises(TypeError, f, 2, X(s))
562 self.assertRaises(TypeError, f, 2, N(s))
563 self.assertRaises(ZeroDivisionError, f, 2, E(s))
564
565 # Issue #17278: the heap may change size while it's being walked.
566
567 def test_heappush_mutating_heap(self):
568 heap = []
569 heap.extend(SideEffectLT(i, heap) for i in range(200))
570 # Python version raises IndexError, C version RuntimeError
571 with self.assertRaises((IndexError, RuntimeError)):
572 self.module.heappush(heap, SideEffectLT(5, heap))
573 heap = []
574 heap.extend(SideEffectLT(i, heap) for i in range(200))
575 with self.assertRaises((IndexError, RuntimeError)):
576 self.module.heappush_max(heap, SideEffectLT(5, heap))
577
578 def test_heappop_mutating_heap(self):
579 heap = []
580 heap.extend(SideEffectLT(i, heap) for i in range(200))
581 # Python version raises IndexError, C version RuntimeError
582 with self.assertRaises((IndexError, RuntimeError)):
583 self.module.heappop(heap)
584 heap = []
585 heap.extend(SideEffectLT(i, heap) for i in range(200))
586 with self.assertRaises((IndexError, RuntimeError)):
587 self.module.heappop_max(heap)
588
589 def test_comparison_operator_modifying_heap(self):
590 # See bpo-39421: Strong references need to be taken
591 # when comparing objects as they can alter the heap
592 class EvilClass(int):
593 def __lt__(self, o):
594 heap.clear()
595 return NotImplemented
596
597 heap = []
598 self.module.heappush(heap, EvilClass(0))
599 self.assertRaises(IndexError, self.module.heappushpop, heap, 1)
600
601 def test_comparison_operator_modifying_heap_two_heaps(self):
602
603 class h(int):
604 def __lt__(self, o):
605 list2.clear()
606 return NotImplemented
607
608 class g(int):
609 def __lt__(self, o):
610 list1.clear()
611 return NotImplemented
612
613 list1, list2 = [], []
614
615 self.module.heappush(list1, h(0))
616 self.module.heappush(list2, g(0))
617
618 self.assertRaises((IndexError, RuntimeError), self.module.heappush, list1, g(1))
619 self.assertRaises((IndexError, RuntimeError), self.module.heappush, list2, h(1))
620
621 list1, list2 = [], []
622
623 self.module.heappush_max(list1, h(0))
624 self.module.heappush_max(list2, g(0))
625 self.module.heappush_max(list1, g(1))
626 self.module.heappush_max(list2, h(1))
627
628 self.assertRaises((IndexError, RuntimeError), self.module.heappush_max, list1, g(1))
629 self.assertRaises((IndexError, RuntimeError), self.module.heappush_max, list2, h(1))
630
631
632 class TestErrorHandlingPython(TestErrorHandling, TestCase):
633 module = py_heapq
634
635 @skipUnless(c_heapq, 'requires _heapq')
636 class TestErrorHandlingC(TestErrorHandling, TestCase):
637 module = c_heapq
638
639
640 if __name__ == "__main__":
641 unittest.main()