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