Python code coverage for Lib/bisect.py

#	count	content
1	n/a	"""Bisection algorithms."""
2	n/a
3	n/a	def insort_right(a, x, lo=0, hi=None):
4	n/a	"""Insert item x in list a, and keep it sorted assuming a is sorted.
5	n/a
6	n/a	If x is already in a, insert it to the right of the rightmost x.
7	n/a
8	n/a	Optional args lo (default 0) and hi (default len(a)) bound the
9	n/a	slice of a to be searched.
10	n/a	"""
11	n/a
12	n/a	if lo < 0:
13	n/a	raise ValueError('lo must be non-negative')
14	n/a	if hi is None:
15	n/a	hi = len(a)
16	n/a	while lo < hi:
17	n/a	mid = (lo+hi)//2
18	n/a	if x < a[mid]: hi = mid
19	n/a	else: lo = mid+1
20	n/a	a.insert(lo, x)
21	n/a
22	n/a	def bisect_right(a, x, lo=0, hi=None):
23	n/a	"""Return the index where to insert item x in list a, assuming a is sorted.
24	n/a
25	n/a	The return value i is such that all e in a[:i] have e <= x, and all e in
26	n/a	a[i:] have e > x. So if x already appears in the list, a.insert(x) will
27	n/a	insert just after the rightmost x already there.
28	n/a
29	n/a	Optional args lo (default 0) and hi (default len(a)) bound the
30	n/a	slice of a to be searched.
31	n/a	"""
32	n/a
33	n/a	if lo < 0:
34	n/a	raise ValueError('lo must be non-negative')
35	n/a	if hi is None:
36	n/a	hi = len(a)
37	n/a	while lo < hi:
38	n/a	mid = (lo+hi)//2
39	n/a	if x < a[mid]: hi = mid
40	n/a	else: lo = mid+1
41	n/a	return lo
42	n/a
43	n/a	def insort_left(a, x, lo=0, hi=None):
44	n/a	"""Insert item x in list a, and keep it sorted assuming a is sorted.
45	n/a
46	n/a	If x is already in a, insert it to the left of the leftmost x.
47	n/a
48	n/a	Optional args lo (default 0) and hi (default len(a)) bound the
49	n/a	slice of a to be searched.
50	n/a	"""
51	n/a
52	n/a	if lo < 0:
53	n/a	raise ValueError('lo must be non-negative')
54	n/a	if hi is None:
55	n/a	hi = len(a)
56	n/a	while lo < hi:
57	n/a	mid = (lo+hi)//2
58	n/a	if a[mid] < x: lo = mid+1
59	n/a	else: hi = mid
60	n/a	a.insert(lo, x)
61	n/a
62	n/a
63	n/a	def bisect_left(a, x, lo=0, hi=None):
64	n/a	"""Return the index where to insert item x in list a, assuming a is sorted.
65	n/a
66	n/a	The return value i is such that all e in a[:i] have e < x, and all e in
67	n/a	a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
68	n/a	insert just before the leftmost x already there.
69	n/a
70	n/a	Optional args lo (default 0) and hi (default len(a)) bound the
71	n/a	slice of a to be searched.
72	n/a	"""
73	n/a
74	n/a	if lo < 0:
75	n/a	raise ValueError('lo must be non-negative')
76	n/a	if hi is None:
77	n/a	hi = len(a)
78	n/a	while lo < hi:
79	n/a	mid = (lo+hi)//2
80	n/a	if a[mid] < x: lo = mid+1
81	n/a	else: hi = mid
82	n/a	return lo
83	n/a
84	n/a	# Overwrite above definitions with a fast C implementation
85	n/a	try:
86	n/a	from _bisect import *
87	n/a	except ImportError:
88	n/a	pass
89	n/a
90	n/a	# Create aliases
91	n/a	bisect = bisect_right
92	n/a	insort = insort_right