author | jjkang |
Fri, 11 Jun 2010 15:22:40 +0800 | |
changeset 2 | 9da1e5517a66 |
parent 0 | ae805ac0140d |
permissions | -rw-r--r-- |
0
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
1 |
"""Bisection algorithms.""" |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
2 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
3 |
def insort_right(a, x, lo=0, hi=None): |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
4 |
"""Insert item x in list a, and keep it sorted assuming a is sorted. |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
5 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
6 |
If x is already in a, insert it to the right of the rightmost x. |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
7 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
8 |
Optional args lo (default 0) and hi (default len(a)) bound the |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
9 |
slice of a to be searched. |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
10 |
""" |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
11 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
12 |
if hi is None: |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
13 |
hi = len(a) |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
14 |
while lo < hi: |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
15 |
mid = (lo+hi)//2 |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
16 |
if x < a[mid]: hi = mid |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
17 |
else: lo = mid+1 |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
18 |
a.insert(lo, x) |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
19 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
20 |
insort = insort_right # backward compatibility |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
21 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
22 |
def bisect_right(a, x, lo=0, hi=None): |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
23 |
"""Return the index where to insert item x in list a, assuming a is sorted. |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
24 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
25 |
The return value i is such that all e in a[:i] have e <= x, and all e in |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
26 |
a[i:] have e > x. So if x already appears in the list, a.insert(x) will |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
27 |
insert just after the rightmost x already there. |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
28 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
29 |
Optional args lo (default 0) and hi (default len(a)) bound the |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
30 |
slice of a to be searched. |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
31 |
""" |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
32 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
33 |
if hi is None: |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
34 |
hi = len(a) |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
35 |
while lo < hi: |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
36 |
mid = (lo+hi)//2 |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
37 |
if x < a[mid]: hi = mid |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
38 |
else: lo = mid+1 |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
39 |
return lo |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
40 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
41 |
bisect = bisect_right # backward compatibility |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
42 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
43 |
def insort_left(a, x, lo=0, hi=None): |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
44 |
"""Insert item x in list a, and keep it sorted assuming a is sorted. |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
45 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
46 |
If x is already in a, insert it to the left of the leftmost x. |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
47 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
48 |
Optional args lo (default 0) and hi (default len(a)) bound the |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
49 |
slice of a to be searched. |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
50 |
""" |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
51 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
52 |
if hi is None: |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
53 |
hi = len(a) |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
54 |
while lo < hi: |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
55 |
mid = (lo+hi)//2 |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
56 |
if a[mid] < x: lo = mid+1 |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
57 |
else: hi = mid |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
58 |
a.insert(lo, x) |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
59 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
60 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
61 |
def bisect_left(a, x, lo=0, hi=None): |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
62 |
"""Return the index where to insert item x in list a, assuming a is sorted. |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
63 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
64 |
The return value i is such that all e in a[:i] have e < x, and all e in |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
65 |
a[i:] have e >= x. So if x already appears in the list, a.insert(x) will |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
66 |
insert just before the leftmost x already there. |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
67 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
68 |
Optional args lo (default 0) and hi (default len(a)) bound the |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
69 |
slice of a to be searched. |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
70 |
""" |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
71 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
72 |
if hi is None: |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
73 |
hi = len(a) |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
74 |
while lo < hi: |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
75 |
mid = (lo+hi)//2 |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
76 |
if a[mid] < x: lo = mid+1 |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
77 |
else: hi = mid |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
78 |
return lo |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
79 |
|
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
80 |
# Overwrite above definitions with a fast C implementation |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
81 |
try: |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
82 |
from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
83 |
except ImportError: |
ae805ac0140d
DP tools release version Revision: 200912
Deepak Modgil <Deepak.Modgil@Nokia.com>
parents:
diff
changeset
|
84 |
pass |