home *** CD-ROM | disk | FTP | other *** search
/ Chip 2011 November / CHIP_2011_11.iso / Programy / Narzedzia / Inkscape / Inkscape-0.48.2-1-win32.exe / python / Lib / bisect.py < prev    next >
Encoding:
Python Source  |  2010-05-29  |  2.7 KB  |  93 lines
  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
  93.