ยปCore Development>Code coverage>Lib/bisect.py

Python code coverage for Lib/bisect.py

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