Commit | Line | Data |
---|---|---|
920dae64 AT |
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 | |
79 | ||
80 | # Overwrite above definitions with a fast C implementation | |
81 | try: | |
82 | from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect | |
83 | except ImportError: | |
84 | pass |