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