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 bisect_right, bisect_left, insort_left, insort_right, insort, bisect

    91 except ImportError:

    92     pass