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

Python code coverage for Lib/test/test_bisect.py

#countcontent
1n/aimport sys
2n/aimport unittest
3n/afrom test import support
4n/afrom collections import UserList
5n/a
6n/apy_bisect = support.import_fresh_module('bisect', blocked=['_bisect'])
7n/ac_bisect = support.import_fresh_module('bisect', fresh=['_bisect'])
8n/a
9n/aclass Range(object):
10n/a """A trivial range()-like object that has an insert() method."""
11n/a def __init__(self, start, stop):
12n/a self.start = start
13n/a self.stop = stop
14n/a self.last_insert = None
15n/a
16n/a def __len__(self):
17n/a return self.stop - self.start
18n/a
19n/a def __getitem__(self, idx):
20n/a n = self.stop - self.start
21n/a if idx < 0:
22n/a idx += n
23n/a if idx >= n:
24n/a raise IndexError(idx)
25n/a return self.start + idx
26n/a
27n/a def insert(self, idx, item):
28n/a self.last_insert = idx, item
29n/a
30n/a
31n/aclass TestBisect:
32n/a def setUp(self):
33n/a self.precomputedCases = [
34n/a (self.module.bisect_right, [], 1, 0),
35n/a (self.module.bisect_right, [1], 0, 0),
36n/a (self.module.bisect_right, [1], 1, 1),
37n/a (self.module.bisect_right, [1], 2, 1),
38n/a (self.module.bisect_right, [1, 1], 0, 0),
39n/a (self.module.bisect_right, [1, 1], 1, 2),
40n/a (self.module.bisect_right, [1, 1], 2, 2),
41n/a (self.module.bisect_right, [1, 1, 1], 0, 0),
42n/a (self.module.bisect_right, [1, 1, 1], 1, 3),
43n/a (self.module.bisect_right, [1, 1, 1], 2, 3),
44n/a (self.module.bisect_right, [1, 1, 1, 1], 0, 0),
45n/a (self.module.bisect_right, [1, 1, 1, 1], 1, 4),
46n/a (self.module.bisect_right, [1, 1, 1, 1], 2, 4),
47n/a (self.module.bisect_right, [1, 2], 0, 0),
48n/a (self.module.bisect_right, [1, 2], 1, 1),
49n/a (self.module.bisect_right, [1, 2], 1.5, 1),
50n/a (self.module.bisect_right, [1, 2], 2, 2),
51n/a (self.module.bisect_right, [1, 2], 3, 2),
52n/a (self.module.bisect_right, [1, 1, 2, 2], 0, 0),
53n/a (self.module.bisect_right, [1, 1, 2, 2], 1, 2),
54n/a (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2),
55n/a (self.module.bisect_right, [1, 1, 2, 2], 2, 4),
56n/a (self.module.bisect_right, [1, 1, 2, 2], 3, 4),
57n/a (self.module.bisect_right, [1, 2, 3], 0, 0),
58n/a (self.module.bisect_right, [1, 2, 3], 1, 1),
59n/a (self.module.bisect_right, [1, 2, 3], 1.5, 1),
60n/a (self.module.bisect_right, [1, 2, 3], 2, 2),
61n/a (self.module.bisect_right, [1, 2, 3], 2.5, 2),
62n/a (self.module.bisect_right, [1, 2, 3], 3, 3),
63n/a (self.module.bisect_right, [1, 2, 3], 4, 3),
64n/a (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
65n/a (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
66n/a (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
67n/a (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
68n/a (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
69n/a (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
70n/a (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
71n/a (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
72n/a (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
73n/a
74n/a (self.module.bisect_left, [], 1, 0),
75n/a (self.module.bisect_left, [1], 0, 0),
76n/a (self.module.bisect_left, [1], 1, 0),
77n/a (self.module.bisect_left, [1], 2, 1),
78n/a (self.module.bisect_left, [1, 1], 0, 0),
79n/a (self.module.bisect_left, [1, 1], 1, 0),
80n/a (self.module.bisect_left, [1, 1], 2, 2),
81n/a (self.module.bisect_left, [1, 1, 1], 0, 0),
82n/a (self.module.bisect_left, [1, 1, 1], 1, 0),
83n/a (self.module.bisect_left, [1, 1, 1], 2, 3),
84n/a (self.module.bisect_left, [1, 1, 1, 1], 0, 0),
85n/a (self.module.bisect_left, [1, 1, 1, 1], 1, 0),
86n/a (self.module.bisect_left, [1, 1, 1, 1], 2, 4),
87n/a (self.module.bisect_left, [1, 2], 0, 0),
88n/a (self.module.bisect_left, [1, 2], 1, 0),
89n/a (self.module.bisect_left, [1, 2], 1.5, 1),
90n/a (self.module.bisect_left, [1, 2], 2, 1),
91n/a (self.module.bisect_left, [1, 2], 3, 2),
92n/a (self.module.bisect_left, [1, 1, 2, 2], 0, 0),
93n/a (self.module.bisect_left, [1, 1, 2, 2], 1, 0),
94n/a (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2),
95n/a (self.module.bisect_left, [1, 1, 2, 2], 2, 2),
96n/a (self.module.bisect_left, [1, 1, 2, 2], 3, 4),
97n/a (self.module.bisect_left, [1, 2, 3], 0, 0),
98n/a (self.module.bisect_left, [1, 2, 3], 1, 0),
99n/a (self.module.bisect_left, [1, 2, 3], 1.5, 1),
100n/a (self.module.bisect_left, [1, 2, 3], 2, 1),
101n/a (self.module.bisect_left, [1, 2, 3], 2.5, 2),
102n/a (self.module.bisect_left, [1, 2, 3], 3, 2),
103n/a (self.module.bisect_left, [1, 2, 3], 4, 3),
104n/a (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
105n/a (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
106n/a (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
107n/a (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
108n/a (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
109n/a (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
110n/a (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
111n/a (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
112n/a (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
113n/a ]
114n/a
115n/a def test_precomputed(self):
116n/a for func, data, elem, expected in self.precomputedCases:
117n/a self.assertEqual(func(data, elem), expected)
118n/a self.assertEqual(func(UserList(data), elem), expected)
119n/a
120n/a def test_negative_lo(self):
121n/a # Issue 3301
122n/a mod = self.module
123n/a self.assertRaises(ValueError, mod.bisect_left, [1, 2, 3], 5, -1, 3)
124n/a self.assertRaises(ValueError, mod.bisect_right, [1, 2, 3], 5, -1, 3)
125n/a self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3)
126n/a self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3)
127n/a
128n/a def test_large_range(self):
129n/a # Issue 13496
130n/a mod = self.module
131n/a n = sys.maxsize
132n/a data = range(n-1)
133n/a self.assertEqual(mod.bisect_left(data, n-3), n-3)
134n/a self.assertEqual(mod.bisect_right(data, n-3), n-2)
135n/a self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
136n/a self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
137n/a
138n/a def test_large_pyrange(self):
139n/a # Same as above, but without C-imposed limits on range() parameters
140n/a mod = self.module
141n/a n = sys.maxsize
142n/a data = Range(0, n-1)
143n/a self.assertEqual(mod.bisect_left(data, n-3), n-3)
144n/a self.assertEqual(mod.bisect_right(data, n-3), n-2)
145n/a self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
146n/a self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
147n/a x = n - 100
148n/a mod.insort_left(data, x, x - 50, x + 50)
149n/a self.assertEqual(data.last_insert, (x, x))
150n/a x = n - 200
151n/a mod.insort_right(data, x, x - 50, x + 50)
152n/a self.assertEqual(data.last_insert, (x + 1, x))
153n/a
154n/a def test_random(self, n=25):
155n/a from random import randrange
156n/a for i in range(n):
157n/a data = [randrange(0, n, 2) for j in range(i)]
158n/a data.sort()
159n/a elem = randrange(-1, n+1)
160n/a ip = self.module.bisect_left(data, elem)
161n/a if ip < len(data):
162n/a self.assertTrue(elem <= data[ip])
163n/a if ip > 0:
164n/a self.assertTrue(data[ip-1] < elem)
165n/a ip = self.module.bisect_right(data, elem)
166n/a if ip < len(data):
167n/a self.assertTrue(elem < data[ip])
168n/a if ip > 0:
169n/a self.assertTrue(data[ip-1] <= elem)
170n/a
171n/a def test_optionalSlicing(self):
172n/a for func, data, elem, expected in self.precomputedCases:
173n/a for lo in range(4):
174n/a lo = min(len(data), lo)
175n/a for hi in range(3,8):
176n/a hi = min(len(data), hi)
177n/a ip = func(data, elem, lo, hi)
178n/a self.assertTrue(lo <= ip <= hi)
179n/a if func is self.module.bisect_left and ip < hi:
180n/a self.assertTrue(elem <= data[ip])
181n/a if func is self.module.bisect_left and ip > lo:
182n/a self.assertTrue(data[ip-1] < elem)
183n/a if func is self.module.bisect_right and ip < hi:
184n/a self.assertTrue(elem < data[ip])
185n/a if func is self.module.bisect_right and ip > lo:
186n/a self.assertTrue(data[ip-1] <= elem)
187n/a self.assertEqual(ip, max(lo, min(hi, expected)))
188n/a
189n/a def test_backcompatibility(self):
190n/a self.assertEqual(self.module.bisect, self.module.bisect_right)
191n/a
192n/a def test_keyword_args(self):
193n/a data = [10, 20, 30, 40, 50]
194n/a self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2)
195n/a self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2)
196n/a self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2)
197n/a self.module.insort_left(a=data, x=25, lo=1, hi=3)
198n/a self.module.insort_right(a=data, x=25, lo=1, hi=3)
199n/a self.module.insort(a=data, x=25, lo=1, hi=3)
200n/a self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])
201n/a
202n/aclass TestBisectPython(TestBisect, unittest.TestCase):
203n/a module = py_bisect
204n/a
205n/aclass TestBisectC(TestBisect, unittest.TestCase):
206n/a module = c_bisect
207n/a
208n/a#==============================================================================
209n/a
210n/aclass TestInsort:
211n/a def test_vsBuiltinSort(self, n=500):
212n/a from random import choice
213n/a for insorted in (list(), UserList()):
214n/a for i in range(n):
215n/a digit = choice("0123456789")
216n/a if digit in "02468":
217n/a f = self.module.insort_left
218n/a else:
219n/a f = self.module.insort_right
220n/a f(insorted, digit)
221n/a self.assertEqual(sorted(insorted), insorted)
222n/a
223n/a def test_backcompatibility(self):
224n/a self.assertEqual(self.module.insort, self.module.insort_right)
225n/a
226n/a def test_listDerived(self):
227n/a class List(list):
228n/a data = []
229n/a def insert(self, index, item):
230n/a self.data.insert(index, item)
231n/a
232n/a lst = List()
233n/a self.module.insort_left(lst, 10)
234n/a self.module.insort_right(lst, 5)
235n/a self.assertEqual([5, 10], lst.data)
236n/a
237n/aclass TestInsortPython(TestInsort, unittest.TestCase):
238n/a module = py_bisect
239n/a
240n/aclass TestInsortC(TestInsort, unittest.TestCase):
241n/a module = c_bisect
242n/a
243n/a#==============================================================================
244n/a
245n/aclass LenOnly:
246n/a "Dummy sequence class defining __len__ but not __getitem__."
247n/a def __len__(self):
248n/a return 10
249n/a
250n/aclass GetOnly:
251n/a "Dummy sequence class defining __getitem__ but not __len__."
252n/a def __getitem__(self, ndx):
253n/a return 10
254n/a
255n/aclass CmpErr:
256n/a "Dummy element that always raises an error during comparison"
257n/a def __lt__(self, other):
258n/a raise ZeroDivisionError
259n/a __gt__ = __lt__
260n/a __le__ = __lt__
261n/a __ge__ = __lt__
262n/a __eq__ = __lt__
263n/a __ne__ = __lt__
264n/a
265n/aclass TestErrorHandling:
266n/a def test_non_sequence(self):
267n/a for f in (self.module.bisect_left, self.module.bisect_right,
268n/a self.module.insort_left, self.module.insort_right):
269n/a self.assertRaises(TypeError, f, 10, 10)
270n/a
271n/a def test_len_only(self):
272n/a for f in (self.module.bisect_left, self.module.bisect_right,
273n/a self.module.insort_left, self.module.insort_right):
274n/a self.assertRaises(TypeError, f, LenOnly(), 10)
275n/a
276n/a def test_get_only(self):
277n/a for f in (self.module.bisect_left, self.module.bisect_right,
278n/a self.module.insort_left, self.module.insort_right):
279n/a self.assertRaises(TypeError, f, GetOnly(), 10)
280n/a
281n/a def test_cmp_err(self):
282n/a seq = [CmpErr(), CmpErr(), CmpErr()]
283n/a for f in (self.module.bisect_left, self.module.bisect_right,
284n/a self.module.insort_left, self.module.insort_right):
285n/a self.assertRaises(ZeroDivisionError, f, seq, 10)
286n/a
287n/a def test_arg_parsing(self):
288n/a for f in (self.module.bisect_left, self.module.bisect_right,
289n/a self.module.insort_left, self.module.insort_right):
290n/a self.assertRaises(TypeError, f, 10)
291n/a
292n/aclass TestErrorHandlingPython(TestErrorHandling, unittest.TestCase):
293n/a module = py_bisect
294n/a
295n/aclass TestErrorHandlingC(TestErrorHandling, unittest.TestCase):
296n/a module = c_bisect
297n/a
298n/a#==============================================================================
299n/a
300n/aclass TestDocExample:
301n/a def test_grades(self):
302n/a def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
303n/a i = self.module.bisect(breakpoints, score)
304n/a return grades[i]
305n/a
306n/a result = [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
307n/a self.assertEqual(result, ['F', 'A', 'C', 'C', 'B', 'A', 'A'])
308n/a
309n/a def test_colors(self):
310n/a data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
311n/a data.sort(key=lambda r: r[1])
312n/a keys = [r[1] for r in data]
313n/a bisect_left = self.module.bisect_left
314n/a self.assertEqual(data[bisect_left(keys, 0)], ('black', 0))
315n/a self.assertEqual(data[bisect_left(keys, 1)], ('blue', 1))
316n/a self.assertEqual(data[bisect_left(keys, 5)], ('red', 5))
317n/a self.assertEqual(data[bisect_left(keys, 8)], ('yellow', 8))
318n/a
319n/aclass TestDocExamplePython(TestDocExample, unittest.TestCase):
320n/a module = py_bisect
321n/a
322n/aclass TestDocExampleC(TestDocExample, unittest.TestCase):
323n/a module = c_bisect
324n/a
325n/a#------------------------------------------------------------------------------
326n/a
327n/aif __name__ == "__main__":
328n/a unittest.main()