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
22insort = insort_right   # backward compatibility
23
24def 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
45bisect = bisect_right   # backward compatibility
46
47def 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
67def 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
89try:
90    from _bisect import *
91except ImportError:
92    pass
93