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