]>
Commit | Line | Data |
---|---|---|
3257aa99 DM |
1 | """Bisection algorithms."""\r |
2 | \r | |
3 | def insort_right(a, x, lo=0, hi=None):\r | |
4 | """Insert item x in list a, and keep it sorted assuming a is sorted.\r | |
5 | \r | |
6 | If x is already in a, insert it to the right of the rightmost x.\r | |
7 | \r | |
8 | Optional args lo (default 0) and hi (default len(a)) bound the\r | |
9 | slice of a to be searched.\r | |
10 | """\r | |
11 | \r | |
12 | if lo < 0:\r | |
13 | raise ValueError('lo must be non-negative')\r | |
14 | if hi is None:\r | |
15 | hi = len(a)\r | |
16 | while lo < hi:\r | |
17 | mid = (lo+hi)//2\r | |
18 | if x < a[mid]: hi = mid\r | |
19 | else: lo = mid+1\r | |
20 | a.insert(lo, x)\r | |
21 | \r | |
22 | insort = insort_right # backward compatibility\r | |
23 | \r | |
24 | def bisect_right(a, x, lo=0, hi=None):\r | |
25 | """Return the index where to insert item x in list a, assuming a is sorted.\r | |
26 | \r | |
27 | The return value i is such that all e in a[:i] have e <= x, and all e in\r | |
28 | a[i:] have e > x. So if x already appears in the list, a.insert(x) will\r | |
29 | insert just after the rightmost x already there.\r | |
30 | \r | |
31 | Optional args lo (default 0) and hi (default len(a)) bound the\r | |
32 | slice of a to be searched.\r | |
33 | """\r | |
34 | \r | |
35 | if lo < 0:\r | |
36 | raise ValueError('lo must be non-negative')\r | |
37 | if hi is None:\r | |
38 | hi = len(a)\r | |
39 | while lo < hi:\r | |
40 | mid = (lo+hi)//2\r | |
41 | if x < a[mid]: hi = mid\r | |
42 | else: lo = mid+1\r | |
43 | return lo\r | |
44 | \r | |
45 | bisect = bisect_right # backward compatibility\r | |
46 | \r | |
47 | def insort_left(a, x, lo=0, hi=None):\r | |
48 | """Insert item x in list a, and keep it sorted assuming a is sorted.\r | |
49 | \r | |
50 | If x is already in a, insert it to the left of the leftmost x.\r | |
51 | \r | |
52 | Optional args lo (default 0) and hi (default len(a)) bound the\r | |
53 | slice of a to be searched.\r | |
54 | """\r | |
55 | \r | |
56 | if lo < 0:\r | |
57 | raise ValueError('lo must be non-negative')\r | |
58 | if hi is None:\r | |
59 | hi = len(a)\r | |
60 | while lo < hi:\r | |
61 | mid = (lo+hi)//2\r | |
62 | if a[mid] < x: lo = mid+1\r | |
63 | else: hi = mid\r | |
64 | a.insert(lo, x)\r | |
65 | \r | |
66 | \r | |
67 | def bisect_left(a, x, lo=0, hi=None):\r | |
68 | """Return the index where to insert item x in list a, assuming a is sorted.\r | |
69 | \r | |
70 | The return value i is such that all e in a[:i] have e < x, and all e in\r | |
71 | a[i:] have e >= x. So if x already appears in the list, a.insert(x) will\r | |
72 | insert just before the leftmost x already there.\r | |
73 | \r | |
74 | Optional args lo (default 0) and hi (default len(a)) bound the\r | |
75 | slice of a to be searched.\r | |
76 | """\r | |
77 | \r | |
78 | if lo < 0:\r | |
79 | raise ValueError('lo must be non-negative')\r | |
80 | if hi is None:\r | |
81 | hi = len(a)\r | |
82 | while lo < hi:\r | |
83 | mid = (lo+hi)//2\r | |
84 | if a[mid] < x: lo = mid+1\r | |
85 | else: hi = mid\r | |
86 | return lo\r | |
87 | \r | |
88 | # Overwrite above definitions with a fast C implementation\r | |
89 | try:\r | |
90 | from _bisect import *\r | |
91 | except ImportError:\r | |
92 | pass\r |