home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 January / Gamestar_80_2006-01_dvd.iso / Dema / Civilization4 / data1.cab / Civ4DemoComponent / Assets / Python / System / bisect.pyc (.txt) < prev    next >
Encoding:
Python Compiled Bytecode  |  2005-11-09  |  2.9 KB  |  97 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyc (Python 2.4)
  3.  
  4. '''Bisection algorithms.'''
  5.  
  6. def insort_right(a, x, lo = 0, hi = None):
  7.     '''Insert item x in list a, and keep it sorted assuming a is sorted.
  8.  
  9.     If x is already in a, insert it to the right of the rightmost x.
  10.  
  11.     Optional args lo (default 0) and hi (default len(a)) bound the
  12.     slice of a to be searched.
  13.     '''
  14.     if hi is None:
  15.         hi = len(a)
  16.     
  17.     while lo < hi:
  18.         mid = (lo + hi) // 2
  19.         if x < a[mid]:
  20.             hi = mid
  21.             continue
  22.         lo = mid + 1
  23.     a.insert(lo, x)
  24.  
  25. insort = insort_right
  26.  
  27. def bisect_right(a, x, lo = 0, hi = None):
  28.     '''Return the index where to insert item x in list a, assuming a is sorted.
  29.  
  30.     The return value i is such that all e in a[:i] have e <= x, and all e in
  31.     a[i:] have e > x.  So if x already appears in the list, i points just
  32.     beyond the rightmost x already there.
  33.  
  34.     Optional args lo (default 0) and hi (default len(a)) bound the
  35.     slice of a to be searched.
  36.     '''
  37.     if hi is None:
  38.         hi = len(a)
  39.     
  40.     while lo < hi:
  41.         mid = (lo + hi) // 2
  42.         if x < a[mid]:
  43.             hi = mid
  44.             continue
  45.         lo = mid + 1
  46.     return lo
  47.  
  48. bisect = bisect_right
  49.  
  50. def insort_left(a, x, lo = 0, hi = None):
  51.     '''Insert item x in list a, and keep it sorted assuming a is sorted.
  52.  
  53.     If x is already in a, insert it to the left of the leftmost x.
  54.  
  55.     Optional args lo (default 0) and hi (default len(a)) bound the
  56.     slice of a to be searched.
  57.     '''
  58.     if hi is None:
  59.         hi = len(a)
  60.     
  61.     while lo < hi:
  62.         mid = (lo + hi) // 2
  63.         if a[mid] < x:
  64.             lo = mid + 1
  65.             continue
  66.         hi = mid
  67.     a.insert(lo, x)
  68.  
  69.  
  70. def bisect_left(a, x, lo = 0, hi = None):
  71.     '''Return the index where to insert item x in list a, assuming a is sorted.
  72.  
  73.     The return value i is such that all e in a[:i] have e < x, and all e in
  74.     a[i:] have e >= x.  So if x already appears in the list, i points just
  75.     before the leftmost x already there.
  76.  
  77.     Optional args lo (default 0) and hi (default len(a)) bound the
  78.     slice of a to be searched.
  79.     '''
  80.     if hi is None:
  81.         hi = len(a)
  82.     
  83.     while lo < hi:
  84.         mid = (lo + hi) // 2
  85.         if a[mid] < x:
  86.             lo = mid + 1
  87.             continue
  88.         hi = mid
  89.     return lo
  90.  
  91.  
  92. try:
  93.     from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
  94. except ImportError:
  95.     pass
  96.  
  97.