Python code coverage for Lib/test/test_bisect.py

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