Mercurial > cpython-lru_cache-weakref

annotate Lib/bisect.py @ 58765:2ba7677bfa95 legacy-trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
testCopysign was defined twice in test_math; combine the definitions
author Mark Dickinson <dickinsm@gmail.com>
date Sat, 06 Feb 2010 23:11:25 +0000
parents 840032d9efd6
children 8d28d44f3a9a
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
11691
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
1 """Bisection algorithms."""
1006
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
2
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
3 def insort_right(a, x, lo=0, hi=None):
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
4 """Insert item x in list a, and keep it sorted assuming a is sorted.
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
5
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
6 If x is already in a, insert it to the right of the rightmost x.
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
7
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
8 Optional args lo (default 0) and hi (default len(a)) bound the
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
9 slice of a to be searched.
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
10 """
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
11
48499
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 41554
diff changeset
12 if lo < 0:
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 41554
diff changeset
13 raise ValueError('lo must be non-negative')
11691
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
14 if hi is None:
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
15 hi = len(a)
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
16 while lo < hi:
19694
3716b116fb31 The first batch of changes recommended by the fixdiv tool. These are
Guido van Rossum <guido@python.org>
parents: 16657
diff changeset
17 mid = (lo+hi)//2
11691
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
18 if x < a[mid]: hi = mid
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
19 else: lo = mid+1
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
20 a.insert(lo, x)
1006
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
21
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
22 insort = insort_right # backward compatibility
1006
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
23
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
24 def bisect_right(a, x, lo=0, hi=None):
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
25 """Return the index where to insert item x in list a, assuming a is sorted.
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
26
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
27 The return value i is such that all e in a[:i] have e <= x, and all e in
41554
06145fbc7ab9 Merged revisions 53952-54987 via svnmerge from
Guido van Rossum <guido@python.org>
parents: 31353
diff changeset
28 a[i:] have e > x. So if x already appears in the list, a.insert(x) will
06145fbc7ab9 Merged revisions 53952-54987 via svnmerge from
Guido van Rossum <guido@python.org>
parents: 31353
diff changeset
29 insert just after the rightmost x already there.
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
30
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
31 Optional args lo (default 0) and hi (default len(a)) bound the
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
32 slice of a to be searched.
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
33 """
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
34
48499
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 41554
diff changeset
35 if lo < 0:
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 41554
diff changeset
36 raise ValueError('lo must be non-negative')
11691
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
37 if hi is None:
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
38 hi = len(a)
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
39 while lo < hi:
19694
3716b116fb31 The first batch of changes recommended by the fixdiv tool. These are
Guido van Rossum <guido@python.org>
parents: 16657
diff changeset
40 mid = (lo+hi)//2
11691
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
41 if x < a[mid]: hi = mid
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
42 else: lo = mid+1
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
43 return lo
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
44
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
45 bisect = bisect_right # backward compatibility
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
46
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
47 def insort_left(a, x, lo=0, hi=None):
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
48 """Insert item x in list a, and keep it sorted assuming a is sorted.
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
49
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
50 If x is already in a, insert it to the left of the leftmost x.
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
51
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
52 Optional args lo (default 0) and hi (default len(a)) bound the
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
53 slice of a to be searched.
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
54 """
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
55
48499
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 41554
diff changeset
56 if lo < 0:
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 41554
diff changeset
57 raise ValueError('lo must be non-negative')
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
58 if hi is None:
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
59 hi = len(a)
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
60 while lo < hi:
19694
3716b116fb31 The first batch of changes recommended by the fixdiv tool. These are
Guido van Rossum <guido@python.org>
parents: 16657
diff changeset
61 mid = (lo+hi)//2
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
62 if a[mid] < x: lo = mid+1
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
63 else: hi = mid
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
64 a.insert(lo, x)
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
65
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
66
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
67 def bisect_left(a, x, lo=0, hi=None):
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
68 """Return the index where to insert item x in list a, assuming a is sorted.
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
69
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
70 The return value i is such that all e in a[:i] have e < x, and all e in
41554
06145fbc7ab9 Merged revisions 53952-54987 via svnmerge from
Guido van Rossum <guido@python.org>
parents: 31353
diff changeset
71 a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
06145fbc7ab9 Merged revisions 53952-54987 via svnmerge from
Guido van Rossum <guido@python.org>
parents: 31353
diff changeset
72 insert just before the leftmost x already there.
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
73
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
74 Optional args lo (default 0) and hi (default len(a)) bound the
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
75 slice of a to be searched.
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
76 """
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
77
48499
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 41554
diff changeset
78 if lo < 0:
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 41554
diff changeset
79 raise ValueError('lo must be non-negative')
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
80 if hi is None:
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
81 hi = len(a)
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
82 while lo < hi:
19694
3716b116fb31 The first batch of changes recommended by the fixdiv tool. These are
Guido van Rossum <guido@python.org>
parents: 16657
diff changeset
83 mid = (lo+hi)//2
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
84 if a[mid] < x: lo = mid+1
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
85 else: hi = mid
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
86 return lo
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 19694
diff changeset
87
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 19694
diff changeset
88 # Overwrite above definitions with a fast C implementation
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 19694
diff changeset
89 try:
52548
840032d9efd6 Per the language summit, the optional fastpath imports should use from-import-star.
Raymond Hettinger <python@rcn.com>
parents: 48499
diff changeset
90 from _bisect import *
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 19694
diff changeset
91 except ImportError:
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 19694
diff changeset
92 pass