Guido van Rossum | 0b19178 | 2002-08-02 18:29:53 +0000 | [diff] [blame] | 1 | """Unittests for heapq.""" |
| 2 | |
Ezio Melotti | 8269a44 | 2011-05-09 07:15:04 +0300 | [diff] [blame] | 3 | import random |
Ezio Melotti | 22ebb2d | 2013-01-02 21:19:37 +0200 | [diff] [blame] | 4 | import unittest |
Rob Day | 664fe39 | 2019-06-01 05:13:57 +0100 | [diff] [blame] | 5 | import doctest |
Guido van Rossum | 0b19178 | 2002-08-02 18:29:53 +0000 | [diff] [blame] | 6 | |
Ezio Melotti | 8269a44 | 2011-05-09 07:15:04 +0300 | [diff] [blame] | 7 | from test import support |
| 8 | from unittest import TestCase, skipUnless |
Raymond Hettinger | 35db439 | 2014-05-30 02:28:36 -0700 | [diff] [blame] | 9 | from operator import itemgetter |
Ezio Melotti | 8269a44 | 2011-05-09 07:15:04 +0300 | [diff] [blame] | 10 | |
Nick Coghlan | 4738470 | 2009-04-22 16:13:36 +0000 | [diff] [blame] | 11 | py_heapq = support.import_fresh_module('heapq', blocked=['_heapq']) |
Ezio Melotti | 8269a44 | 2011-05-09 07:15:04 +0300 | [diff] [blame] | 12 | c_heapq = support.import_fresh_module('heapq', fresh=['_heapq']) |
Tim Peters | aa7d243 | 2002-08-03 02:11:26 +0000 | [diff] [blame] | 13 | |
Ezio Melotti | 8269a44 | 2011-05-09 07:15:04 +0300 | [diff] [blame] | 14 | # _heapq.nlargest/nsmallest are saved in heapq._nlargest/_smallest when |
| 15 | # _heapq is imported, so check them there |
Raymond Hettinger | 48f68d0 | 2014-06-14 16:43:35 -0700 | [diff] [blame] | 16 | func_names = ['heapify', 'heappop', 'heappush', 'heappushpop', 'heapreplace', |
| 17 | '_heappop_max', '_heapreplace_max', '_heapify_max'] |
Ezio Melotti | 8269a44 | 2011-05-09 07:15:04 +0300 | [diff] [blame] | 18 | |
| 19 | class TestModules(TestCase): |
| 20 | def test_py_functions(self): |
| 21 | for fname in func_names: |
| 22 | self.assertEqual(getattr(py_heapq, fname).__module__, 'heapq') |
| 23 | |
| 24 | @skipUnless(c_heapq, 'requires _heapq') |
| 25 | def test_c_functions(self): |
| 26 | for fname in func_names: |
| 27 | self.assertEqual(getattr(c_heapq, fname).__module__, '_heapq') |
| 28 | |
| 29 | |
Rob Day | 664fe39 | 2019-06-01 05:13:57 +0100 | [diff] [blame] | 30 | def load_tests(loader, tests, ignore): |
| 31 | # The 'merge' function has examples in its docstring which we should test |
| 32 | # with 'doctest'. |
| 33 | # |
| 34 | # However, doctest can't easily find all docstrings in the module (loading |
| 35 | # it through import_fresh_module seems to confuse it), so we specifically |
| 36 | # create a finder which returns the doctests from the merge method. |
| 37 | |
| 38 | class HeapqMergeDocTestFinder: |
| 39 | def find(self, *args, **kwargs): |
| 40 | dtf = doctest.DocTestFinder() |
| 41 | return dtf.find(py_heapq.merge) |
| 42 | |
| 43 | tests.addTests(doctest.DocTestSuite(py_heapq, |
| 44 | test_finder=HeapqMergeDocTestFinder())) |
| 45 | return tests |
| 46 | |
Ezio Melotti | 22ebb2d | 2013-01-02 21:19:37 +0200 | [diff] [blame] | 47 | class TestHeap: |
Tim Peters | aa7d243 | 2002-08-03 02:11:26 +0000 | [diff] [blame] | 48 | |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 49 | def test_push_pop(self): |
| 50 | # 1) Push 256 random numbers and pop them off, verifying all's OK. |
| 51 | heap = [] |
| 52 | data = [] |
| 53 | self.check_invariant(heap) |
| 54 | for i in range(256): |
| 55 | item = random.random() |
| 56 | data.append(item) |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 57 | self.module.heappush(heap, item) |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 58 | self.check_invariant(heap) |
| 59 | results = [] |
| 60 | while heap: |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 61 | item = self.module.heappop(heap) |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 62 | self.check_invariant(heap) |
| 63 | results.append(item) |
| 64 | data_sorted = data[:] |
| 65 | data_sorted.sort() |
| 66 | self.assertEqual(data_sorted, results) |
| 67 | # 2) Check that the invariant holds for a sorted array |
| 68 | self.check_invariant(results) |
| 69 | |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 70 | self.assertRaises(TypeError, self.module.heappush, []) |
Raymond Hettinger | e1defa4 | 2004-11-29 05:54:48 +0000 | [diff] [blame] | 71 | try: |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 72 | self.assertRaises(TypeError, self.module.heappush, None, None) |
| 73 | self.assertRaises(TypeError, self.module.heappop, None) |
Raymond Hettinger | e1defa4 | 2004-11-29 05:54:48 +0000 | [diff] [blame] | 74 | except AttributeError: |
| 75 | pass |
Neal Norwitz | d7be118 | 2004-07-08 01:56:46 +0000 | [diff] [blame] | 76 | |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 77 | def check_invariant(self, heap): |
| 78 | # Check the heap invariant. |
| 79 | for pos, item in enumerate(heap): |
| 80 | if pos: # pos 0 has no parent |
| 81 | parentpos = (pos-1) >> 1 |
Benjamin Peterson | c9c0f20 | 2009-06-30 23:06:06 +0000 | [diff] [blame] | 82 | self.assertTrue(heap[parentpos] <= item) |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 83 | |
| 84 | def test_heapify(self): |
Raymond Hettinger | 849564f | 2015-05-12 21:42:40 -0700 | [diff] [blame] | 85 | for size in list(range(30)) + [20000]: |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 86 | heap = [random.random() for dummy in range(size)] |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 87 | self.module.heapify(heap) |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 88 | self.check_invariant(heap) |
| 89 | |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 90 | self.assertRaises(TypeError, self.module.heapify, None) |
Neal Norwitz | d7be118 | 2004-07-08 01:56:46 +0000 | [diff] [blame] | 91 | |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 92 | def test_naive_nbest(self): |
| 93 | data = [random.randrange(2000) for i in range(1000)] |
| 94 | heap = [] |
| 95 | for item in data: |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 96 | self.module.heappush(heap, item) |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 97 | if len(heap) > 10: |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 98 | self.module.heappop(heap) |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 99 | heap.sort() |
| 100 | self.assertEqual(heap, sorted(data)[-10:]) |
| 101 | |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 102 | def heapiter(self, heap): |
| 103 | # An iterator returning a heap's elements, smallest-first. |
| 104 | try: |
| 105 | while 1: |
| 106 | yield self.module.heappop(heap) |
| 107 | except IndexError: |
| 108 | pass |
| 109 | |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 110 | def test_nbest(self): |
| 111 | # Less-naive "N-best" algorithm, much faster (if len(data) is big |
| 112 | # enough <wink>) than sorting all of data. However, if we had a max |
| 113 | # heap instead of a min heap, it could go faster still via |
| 114 | # heapify'ing all of data (linear time), then doing 10 heappops |
| 115 | # (10 log-time steps). |
| 116 | data = [random.randrange(2000) for i in range(1000)] |
| 117 | heap = data[:10] |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 118 | self.module.heapify(heap) |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 119 | for item in data[10:]: |
| 120 | if item > heap[0]: # this gets rarer the longer we run |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 121 | self.module.heapreplace(heap, item) |
| 122 | self.assertEqual(list(self.heapiter(heap)), sorted(data)[-10:]) |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 123 | |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 124 | self.assertRaises(TypeError, self.module.heapreplace, None) |
| 125 | self.assertRaises(TypeError, self.module.heapreplace, None, None) |
| 126 | self.assertRaises(IndexError, self.module.heapreplace, [], None) |
Neal Norwitz | d7be118 | 2004-07-08 01:56:46 +0000 | [diff] [blame] | 127 | |
Christian Heimes | dd15f6c | 2008-03-16 00:07:10 +0000 | [diff] [blame] | 128 | def test_nbest_with_pushpop(self): |
| 129 | data = [random.randrange(2000) for i in range(1000)] |
| 130 | heap = data[:10] |
| 131 | self.module.heapify(heap) |
| 132 | for item in data[10:]: |
| 133 | self.module.heappushpop(heap, item) |
| 134 | self.assertEqual(list(self.heapiter(heap)), sorted(data)[-10:]) |
| 135 | self.assertEqual(self.module.heappushpop([], 'x'), 'x') |
| 136 | |
| 137 | def test_heappushpop(self): |
| 138 | h = [] |
| 139 | x = self.module.heappushpop(h, 10) |
| 140 | self.assertEqual((h, x), ([], 10)) |
| 141 | |
| 142 | h = [10] |
| 143 | x = self.module.heappushpop(h, 10.0) |
| 144 | self.assertEqual((h, x), ([10], 10.0)) |
| 145 | self.assertEqual(type(h[0]), int) |
| 146 | self.assertEqual(type(x), float) |
| 147 | |
| 148 | h = [10]; |
| 149 | x = self.module.heappushpop(h, 9) |
| 150 | self.assertEqual((h, x), ([10], 9)) |
| 151 | |
| 152 | h = [10]; |
| 153 | x = self.module.heappushpop(h, 11) |
| 154 | self.assertEqual((h, x), ([11], 10)) |
| 155 | |
Rob Day | 664fe39 | 2019-06-01 05:13:57 +0100 | [diff] [blame] | 156 | def test_heappop_max(self): |
| 157 | # _heapop_max has an optimization for one-item lists which isn't |
| 158 | # covered in other tests, so test that case explicitly here |
| 159 | h = [3, 2] |
| 160 | self.assertEqual(self.module._heappop_max(h), 3) |
| 161 | self.assertEqual(self.module._heappop_max(h), 2) |
| 162 | |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 163 | def test_heapsort(self): |
| 164 | # Exercise everything with repeated heapsort checks |
Guido van Rossum | 805365e | 2007-05-07 22:24:25 +0000 | [diff] [blame] | 165 | for trial in range(100): |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 166 | size = random.randrange(50) |
| 167 | data = [random.randrange(25) for i in range(size)] |
| 168 | if trial & 1: # Half of the time, use heapify |
| 169 | heap = data[:] |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 170 | self.module.heapify(heap) |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 171 | else: # The rest of the time, use heappush |
| 172 | heap = [] |
| 173 | for item in data: |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 174 | self.module.heappush(heap, item) |
| 175 | heap_sorted = [self.module.heappop(heap) for i in range(size)] |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 176 | self.assertEqual(heap_sorted, sorted(data)) |
| 177 | |
Thomas Wouters | cf297e4 | 2007-02-23 15:07:44 +0000 | [diff] [blame] | 178 | def test_merge(self): |
| 179 | inputs = [] |
Raymond Hettinger | 35db439 | 2014-05-30 02:28:36 -0700 | [diff] [blame] | 180 | for i in range(random.randrange(25)): |
| 181 | row = [] |
| 182 | for j in range(random.randrange(100)): |
| 183 | tup = random.choice('ABC'), random.randrange(-500, 500) |
| 184 | row.append(tup) |
Thomas Wouters | cf297e4 | 2007-02-23 15:07:44 +0000 | [diff] [blame] | 185 | inputs.append(row) |
Raymond Hettinger | 35db439 | 2014-05-30 02:28:36 -0700 | [diff] [blame] | 186 | |
| 187 | for key in [None, itemgetter(0), itemgetter(1), itemgetter(1, 0)]: |
| 188 | for reverse in [False, True]: |
| 189 | seqs = [] |
| 190 | for seq in inputs: |
| 191 | seqs.append(sorted(seq, key=key, reverse=reverse)) |
| 192 | self.assertEqual(sorted(chain(*inputs), key=key, reverse=reverse), |
| 193 | list(self.module.merge(*seqs, key=key, reverse=reverse))) |
| 194 | self.assertEqual(list(self.module.merge()), []) |
Thomas Wouters | cf297e4 | 2007-02-23 15:07:44 +0000 | [diff] [blame] | 195 | |
Rob Day | 664fe39 | 2019-06-01 05:13:57 +0100 | [diff] [blame] | 196 | def test_empty_merges(self): |
| 197 | # Merging two empty lists (with or without a key) should produce |
| 198 | # another empty list. |
| 199 | self.assertEqual(list(self.module.merge([], [])), []) |
| 200 | self.assertEqual(list(self.module.merge([], [], key=lambda: 6)), []) |
| 201 | |
Raymond Hettinger | 46f5ca3 | 2013-09-14 20:51:57 -0700 | [diff] [blame] | 202 | def test_merge_does_not_suppress_index_error(self): |
| 203 | # Issue 19018: Heapq.merge suppresses IndexError from user generator |
| 204 | def iterable(): |
| 205 | s = list(range(10)) |
| 206 | for i in range(20): |
| 207 | yield s[i] # IndexError when i > 10 |
| 208 | with self.assertRaises(IndexError): |
| 209 | list(self.module.merge(iterable(), iterable())) |
| 210 | |
Thomas Wouters | cf297e4 | 2007-02-23 15:07:44 +0000 | [diff] [blame] | 211 | def test_merge_stability(self): |
| 212 | class Int(int): |
| 213 | pass |
| 214 | inputs = [[], [], [], []] |
| 215 | for i in range(20000): |
| 216 | stream = random.randrange(4) |
| 217 | x = random.randrange(500) |
| 218 | obj = Int(x) |
| 219 | obj.pair = (x, stream) |
| 220 | inputs[stream].append(obj) |
| 221 | for stream in inputs: |
| 222 | stream.sort() |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 223 | result = [i.pair for i in self.module.merge(*inputs)] |
Thomas Wouters | cf297e4 | 2007-02-23 15:07:44 +0000 | [diff] [blame] | 224 | self.assertEqual(result, sorted(result)) |
| 225 | |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 226 | def test_nsmallest(self): |
Thomas Wouters | 902d6eb | 2007-01-09 23:18:33 +0000 | [diff] [blame] | 227 | data = [(random.randrange(2000), i) for i in range(1000)] |
| 228 | for f in (None, lambda x: x[0] * 547 % 2000): |
| 229 | for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100): |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 230 | self.assertEqual(list(self.module.nsmallest(n, data)), |
| 231 | sorted(data)[:n]) |
| 232 | self.assertEqual(list(self.module.nsmallest(n, data, key=f)), |
Thomas Wouters | 902d6eb | 2007-01-09 23:18:33 +0000 | [diff] [blame] | 233 | sorted(data, key=f)[:n]) |
Raymond Hettinger | bce036b | 2004-06-10 05:07:18 +0000 | [diff] [blame] | 234 | |
Raymond Hettinger | 4901a1f | 2004-12-02 08:59:14 +0000 | [diff] [blame] | 235 | def test_nlargest(self): |
Thomas Wouters | 902d6eb | 2007-01-09 23:18:33 +0000 | [diff] [blame] | 236 | data = [(random.randrange(2000), i) for i in range(1000)] |
| 237 | for f in (None, lambda x: x[0] * 547 % 2000): |
| 238 | for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100): |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 239 | self.assertEqual(list(self.module.nlargest(n, data)), |
Guido van Rossum | c1f779c | 2007-07-03 08:25:58 +0000 | [diff] [blame] | 240 | sorted(data, reverse=True)[:n]) |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 241 | self.assertEqual(list(self.module.nlargest(n, data, key=f)), |
Thomas Wouters | 902d6eb | 2007-01-09 23:18:33 +0000 | [diff] [blame] | 242 | sorted(data, key=f, reverse=True)[:n]) |
Tim Peters | aa7d243 | 2002-08-03 02:11:26 +0000 | [diff] [blame] | 243 | |
Amaury Forgeot d'Arc | fdfe62d | 2008-06-17 20:36:03 +0000 | [diff] [blame] | 244 | def test_comparison_operator(self): |
Ezio Melotti | f9756c2 | 2011-05-09 18:36:53 +0300 | [diff] [blame] | 245 | # Issue 3051: Make sure heapq works with both __lt__ |
Amaury Forgeot d'Arc | 2ba198d | 2008-06-17 21:25:35 +0000 | [diff] [blame] | 246 | # For python 3.0, __le__ alone is not enough |
Amaury Forgeot d'Arc | fdfe62d | 2008-06-17 20:36:03 +0000 | [diff] [blame] | 247 | def hsort(data, comp): |
| 248 | data = [comp(x) for x in data] |
| 249 | self.module.heapify(data) |
| 250 | return [self.module.heappop(data).x for i in range(len(data))] |
| 251 | class LT: |
| 252 | def __init__(self, x): |
| 253 | self.x = x |
| 254 | def __lt__(self, other): |
| 255 | return self.x > other.x |
| 256 | class LE: |
| 257 | def __init__(self, x): |
| 258 | self.x = x |
Amaury Forgeot d'Arc | 35c8658 | 2008-06-17 21:11:29 +0000 | [diff] [blame] | 259 | def __le__(self, other): |
Amaury Forgeot d'Arc | fdfe62d | 2008-06-17 20:36:03 +0000 | [diff] [blame] | 260 | return self.x >= other.x |
| 261 | data = [random.random() for i in range(100)] |
| 262 | target = sorted(data, reverse=True) |
| 263 | self.assertEqual(hsort(data, LT), target) |
Amaury Forgeot d'Arc | 2ba198d | 2008-06-17 21:25:35 +0000 | [diff] [blame] | 264 | self.assertRaises(TypeError, data, LE) |
Amaury Forgeot d'Arc | fdfe62d | 2008-06-17 20:36:03 +0000 | [diff] [blame] | 265 | |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 266 | |
Ezio Melotti | 22ebb2d | 2013-01-02 21:19:37 +0200 | [diff] [blame] | 267 | class TestHeapPython(TestHeap, TestCase): |
Ezio Melotti | f9756c2 | 2011-05-09 18:36:53 +0300 | [diff] [blame] | 268 | module = py_heapq |
| 269 | |
| 270 | |
| 271 | @skipUnless(c_heapq, 'requires _heapq') |
Ezio Melotti | 22ebb2d | 2013-01-02 21:19:37 +0200 | [diff] [blame] | 272 | class TestHeapC(TestHeap, TestCase): |
Ezio Melotti | f9756c2 | 2011-05-09 18:36:53 +0300 | [diff] [blame] | 273 | module = c_heapq |
| 274 | |
| 275 | |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 276 | #============================================================================== |
| 277 | |
| 278 | class LenOnly: |
| 279 | "Dummy sequence class defining __len__ but not __getitem__." |
| 280 | def __len__(self): |
| 281 | return 10 |
| 282 | |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 283 | class CmpErr: |
| 284 | "Dummy element that always raises an error during comparison" |
Mark Dickinson | a56c467 | 2009-01-27 18:17:45 +0000 | [diff] [blame] | 285 | def __eq__(self, other): |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 286 | raise ZeroDivisionError |
Mark Dickinson | a56c467 | 2009-01-27 18:17:45 +0000 | [diff] [blame] | 287 | __ne__ = __lt__ = __le__ = __gt__ = __ge__ = __eq__ |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 288 | |
| 289 | def R(seqn): |
| 290 | 'Regular generator' |
| 291 | for i in seqn: |
| 292 | yield i |
| 293 | |
| 294 | class G: |
| 295 | 'Sequence using __getitem__' |
| 296 | def __init__(self, seqn): |
| 297 | self.seqn = seqn |
| 298 | def __getitem__(self, i): |
| 299 | return self.seqn[i] |
| 300 | |
| 301 | class I: |
| 302 | 'Sequence using iterator protocol' |
| 303 | def __init__(self, seqn): |
| 304 | self.seqn = seqn |
| 305 | self.i = 0 |
| 306 | def __iter__(self): |
| 307 | return self |
Georg Brandl | a18af4e | 2007-04-21 15:47:16 +0000 | [diff] [blame] | 308 | def __next__(self): |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 309 | if self.i >= len(self.seqn): raise StopIteration |
| 310 | v = self.seqn[self.i] |
| 311 | self.i += 1 |
| 312 | return v |
| 313 | |
| 314 | class Ig: |
| 315 | 'Sequence using iterator protocol defined with a generator' |
| 316 | def __init__(self, seqn): |
| 317 | self.seqn = seqn |
| 318 | self.i = 0 |
| 319 | def __iter__(self): |
| 320 | for val in self.seqn: |
| 321 | yield val |
| 322 | |
| 323 | class X: |
| 324 | 'Missing __getitem__ and __iter__' |
| 325 | def __init__(self, seqn): |
| 326 | self.seqn = seqn |
| 327 | self.i = 0 |
Georg Brandl | a18af4e | 2007-04-21 15:47:16 +0000 | [diff] [blame] | 328 | def __next__(self): |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 329 | if self.i >= len(self.seqn): raise StopIteration |
| 330 | v = self.seqn[self.i] |
| 331 | self.i += 1 |
| 332 | return v |
| 333 | |
| 334 | class N: |
Georg Brandl | a18af4e | 2007-04-21 15:47:16 +0000 | [diff] [blame] | 335 | 'Iterator missing __next__()' |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 336 | def __init__(self, seqn): |
| 337 | self.seqn = seqn |
| 338 | self.i = 0 |
| 339 | def __iter__(self): |
| 340 | return self |
| 341 | |
| 342 | class E: |
| 343 | 'Test propagation of exceptions' |
| 344 | def __init__(self, seqn): |
| 345 | self.seqn = seqn |
| 346 | self.i = 0 |
| 347 | def __iter__(self): |
| 348 | return self |
Georg Brandl | a18af4e | 2007-04-21 15:47:16 +0000 | [diff] [blame] | 349 | def __next__(self): |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 350 | 3 // 0 |
| 351 | |
| 352 | class S: |
| 353 | 'Test immediate stop' |
| 354 | def __init__(self, seqn): |
| 355 | pass |
| 356 | def __iter__(self): |
| 357 | return self |
Georg Brandl | a18af4e | 2007-04-21 15:47:16 +0000 | [diff] [blame] | 358 | def __next__(self): |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 359 | raise StopIteration |
| 360 | |
Raymond Hettinger | 736c0ab | 2008-03-13 02:09:15 +0000 | [diff] [blame] | 361 | from itertools import chain |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 362 | def L(seqn): |
| 363 | 'Test multiple tiers of iterators' |
Raymond Hettinger | a6c6037 | 2008-03-13 01:26:19 +0000 | [diff] [blame] | 364 | return chain(map(lambda x:x, R(Ig(G(seqn))))) |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 365 | |
Ezio Melotti | 8269a44 | 2011-05-09 07:15:04 +0300 | [diff] [blame] | 366 | |
Antoine Pitrou | 44d5214 | 2013-03-04 20:30:01 +0100 | [diff] [blame] | 367 | class SideEffectLT: |
| 368 | def __init__(self, value, heap): |
| 369 | self.value = value |
| 370 | self.heap = heap |
| 371 | |
| 372 | def __lt__(self, other): |
| 373 | self.heap[:] = [] |
| 374 | return self.value < other.value |
| 375 | |
| 376 | |
Ezio Melotti | 22ebb2d | 2013-01-02 21:19:37 +0200 | [diff] [blame] | 377 | class TestErrorHandling: |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 378 | |
| 379 | def test_non_sequence(self): |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 380 | for f in (self.module.heapify, self.module.heappop): |
Raymond Hettinger | 8a9c4d9 | 2011-04-13 11:49:57 -0700 | [diff] [blame] | 381 | self.assertRaises((TypeError, AttributeError), f, 10) |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 382 | for f in (self.module.heappush, self.module.heapreplace, |
| 383 | self.module.nlargest, self.module.nsmallest): |
Raymond Hettinger | 8a9c4d9 | 2011-04-13 11:49:57 -0700 | [diff] [blame] | 384 | self.assertRaises((TypeError, AttributeError), f, 10, 10) |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 385 | |
| 386 | def test_len_only(self): |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 387 | for f in (self.module.heapify, self.module.heappop): |
Raymond Hettinger | 8a9c4d9 | 2011-04-13 11:49:57 -0700 | [diff] [blame] | 388 | self.assertRaises((TypeError, AttributeError), f, LenOnly()) |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 389 | for f in (self.module.heappush, self.module.heapreplace): |
Raymond Hettinger | 8a9c4d9 | 2011-04-13 11:49:57 -0700 | [diff] [blame] | 390 | self.assertRaises((TypeError, AttributeError), f, LenOnly(), 10) |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 391 | for f in (self.module.nlargest, self.module.nsmallest): |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 392 | self.assertRaises(TypeError, f, 2, LenOnly()) |
| 393 | |
Miss Islington (bot) | ef3ccd7 | 2019-08-23 22:54:07 -0700 | [diff] [blame] | 394 | def test_cmp_err(self): |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 395 | seq = [CmpErr(), CmpErr(), CmpErr()] |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 396 | for f in (self.module.heapify, self.module.heappop): |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 397 | self.assertRaises(ZeroDivisionError, f, seq) |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 398 | for f in (self.module.heappush, self.module.heapreplace): |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 399 | self.assertRaises(ZeroDivisionError, f, seq, 10) |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 400 | for f in (self.module.nlargest, self.module.nsmallest): |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 401 | self.assertRaises(ZeroDivisionError, f, 2, seq) |
| 402 | |
| 403 | def test_arg_parsing(self): |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 404 | for f in (self.module.heapify, self.module.heappop, |
| 405 | self.module.heappush, self.module.heapreplace, |
| 406 | self.module.nlargest, self.module.nsmallest): |
Raymond Hettinger | 8a9c4d9 | 2011-04-13 11:49:57 -0700 | [diff] [blame] | 407 | self.assertRaises((TypeError, AttributeError), f, 10) |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 408 | |
| 409 | def test_iterable_args(self): |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 410 | for f in (self.module.nlargest, self.module.nsmallest): |
Guido van Rossum | 805365e | 2007-05-07 22:24:25 +0000 | [diff] [blame] | 411 | for s in ("123", "", range(1000), (1, 1.2), range(2000,2200,5)): |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 412 | for g in (G, I, Ig, L, R): |
Guido van Rossum | c1f779c | 2007-07-03 08:25:58 +0000 | [diff] [blame] | 413 | self.assertEqual(list(f(2, g(s))), list(f(2,s))) |
| 414 | self.assertEqual(list(f(2, S(s))), []) |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 415 | self.assertRaises(TypeError, f, 2, X(s)) |
| 416 | self.assertRaises(TypeError, f, 2, N(s)) |
| 417 | self.assertRaises(ZeroDivisionError, f, 2, E(s)) |
| 418 | |
Antoine Pitrou | 44d5214 | 2013-03-04 20:30:01 +0100 | [diff] [blame] | 419 | # Issue #17278: the heap may change size while it's being walked. |
| 420 | |
| 421 | def test_heappush_mutating_heap(self): |
| 422 | heap = [] |
| 423 | heap.extend(SideEffectLT(i, heap) for i in range(200)) |
| 424 | # Python version raises IndexError, C version RuntimeError |
| 425 | with self.assertRaises((IndexError, RuntimeError)): |
| 426 | self.module.heappush(heap, SideEffectLT(5, heap)) |
| 427 | |
| 428 | def test_heappop_mutating_heap(self): |
| 429 | heap = [] |
| 430 | heap.extend(SideEffectLT(i, heap) for i in range(200)) |
| 431 | # Python version raises IndexError, C version RuntimeError |
| 432 | with self.assertRaises((IndexError, RuntimeError)): |
| 433 | self.module.heappop(heap) |
| 434 | |
Christian Heimes | d3eb5a15 | 2008-02-24 00:38:49 +0000 | [diff] [blame] | 435 | |
Ezio Melotti | 22ebb2d | 2013-01-02 21:19:37 +0200 | [diff] [blame] | 436 | class TestErrorHandlingPython(TestErrorHandling, TestCase): |
Ezio Melotti | fd69abb | 2011-05-09 07:20:47 +0300 | [diff] [blame] | 437 | module = py_heapq |
| 438 | |
Ezio Melotti | 19f7ca2 | 2011-05-09 07:27:20 +0300 | [diff] [blame] | 439 | @skipUnless(c_heapq, 'requires _heapq') |
Ezio Melotti | 22ebb2d | 2013-01-02 21:19:37 +0200 | [diff] [blame] | 440 | class TestErrorHandlingC(TestErrorHandling, TestCase): |
Ezio Melotti | fd69abb | 2011-05-09 07:20:47 +0300 | [diff] [blame] | 441 | module = c_heapq |
| 442 | |
Raymond Hettinger | 855d9a9 | 2004-09-28 00:03:54 +0000 | [diff] [blame] | 443 | |
Guido van Rossum | 0b19178 | 2002-08-02 18:29:53 +0000 | [diff] [blame] | 444 | if __name__ == "__main__": |
Ezio Melotti | 22ebb2d | 2013-01-02 21:19:37 +0200 | [diff] [blame] | 445 | unittest.main() |