ยปCore Development>Code coverage>Lib/test/test_heapq.py

Python code coverage for Lib/test/test_heapq.py

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