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 hi is None:

    13         hi = len(a)

    14     while lo < hi:

    15         mid = (lo+hi)//2

    16         if x < a[mid]: hi = mid

    17         else: lo = mid+1

    18     a.insert(lo, x)

    19 

    20 insort = insort_right   # backward compatibility

    21 

    22 def 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 hi is None:

    34         hi = len(a)

    35     while lo < hi:

    36         mid = (lo+hi)//2

    37         if x < a[mid]: hi = mid

    38         else: lo = mid+1

    39     return lo

    40 

    41 bisect = bisect_right   # backward compatibility

    42 

    43 def 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 hi is None:

    53         hi = len(a)

    54     while lo < hi:

    55         mid = (lo+hi)//2

    56         if a[mid] < x: lo = mid+1

    57         else: hi = mid

    58     a.insert(lo, x)

    59 

    60 

    61 def bisect_left(a, x, lo=0, hi=None):

    62     """Return the index where to insert item x in list a, assuming a is sorted.

    63 

    64     The return value i is such that all e in a[:i] have e < x, and all e in

    65     a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will

    66     insert just before the leftmost x already there.

    67 

    68     Optional args lo (default 0) and hi (default len(a)) bound the

    69     slice of a to be searched.

    70     """

    71 

    72     if hi is None:

    73         hi = len(a)

    74     while lo < hi:

    75         mid = (lo+hi)//2

    76         if a[mid] < x: lo = mid+1

    77         else: hi = mid

    78     return lo

    79 

    80 # Overwrite above definitions with a fast C implementation

    81 try:

    82     from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect

    83 except ImportError:

    84     pass