Guido van Rossum | 0b19178 | 2002-08-02 18:29:53 +0000 | [diff] [blame] | 1 | """Unittests for heapq.""" |
| 2 | |
| 3 | from test.test_support import verify, vereq, verbose, TestFailed |
| 4 | |
| 5 | from heapq import heappush, heappop |
| 6 | import random |
| 7 | |
| 8 | def check_invariant(heap): |
| 9 | # Check the heap invariant. |
| 10 | for pos, item in enumerate(heap): |
Tim Peters | d9ea39d | 2002-08-02 19:16:44 +0000 | [diff] [blame^] | 11 | parentpos = ((pos+1) >> 1) - 1 |
Guido van Rossum | 0b19178 | 2002-08-02 18:29:53 +0000 | [diff] [blame] | 12 | if parentpos >= 0: |
| 13 | verify(heap[parentpos] <= item) |
| 14 | |
| 15 | def test_main(): |
| 16 | # 1) Push 100 random numbers and pop them off, verifying all's OK. |
| 17 | heap = [] |
| 18 | data = [] |
| 19 | check_invariant(heap) |
| 20 | for i in range(256): |
| 21 | item = random.random() |
| 22 | data.append(item) |
| 23 | heappush(heap, item) |
| 24 | check_invariant(heap) |
| 25 | results = [] |
| 26 | while heap: |
| 27 | item = heappop(heap) |
| 28 | check_invariant(heap) |
| 29 | results.append(item) |
| 30 | data_sorted = data[:] |
| 31 | data_sorted.sort() |
| 32 | vereq(data_sorted, results) |
| 33 | # 2) Check that the invariant holds for a sorted array |
| 34 | check_invariant(results) |
| 35 | # 3) Naive "N-best" algorithm |
| 36 | heap = [] |
| 37 | for item in data: |
| 38 | heappush(heap, item) |
| 39 | if len(heap) > 10: |
| 40 | heappop(heap) |
| 41 | heap.sort() |
| 42 | vereq(heap, data_sorted[-10:]) |
| 43 | # Make user happy |
| 44 | if verbose: |
| 45 | print "All OK" |
| 46 | |
| 47 | if __name__ == "__main__": |
| 48 | test_main() |