1  """Bisection algorithms."""
       2  
       3  
       4  def 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  
      19  def 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  
      53  def 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  
      68  def 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
     103  try:
     104      from _bisect import *
     105  except ImportError:
     106      pass
     107  
     108  # Create aliases
     109  bisect = bisect_right
     110  insort = insort_right