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