Lib/bisect.py

   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, i points just
  27     beyond 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, i points just
  66     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