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 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 *
  91 except ImportError:
  92     pass