svn-gvsig-desktop / tags / v1_0_2_Build_907 / extensions / extScripting / scripts / jython / Lib / bisect.py @ 11015
History | View | Annotate | Download (2.12 KB)
| 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
|