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
|