Mercurial > cpython-lru_cache-weakref

annotate Lib/bisect.py @ 87690:66c1c9f32567 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add use_weakref option to functools.lru_cache The use_weakref option makes lru_cache create weak references to the function arguments when creating the cache key, which prevents them from staying in the memory forever even after all other references to them are gone. This is a proof of concept for http://bugs.python.org/issue19859
author Radomir Dopieralski <devel@sheep.art.pl>
date Tue, 03 Dec 2013 16:02:48 +0100
parents 7769c4d72806
children
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 *
84442
7769c4d72806 Issue #18200: Back out usage of ModuleNotFoundError (8d28d44f3a9a)
Brett Cannon <brett@python.org>
parents: 84114
diff changeset
91 except ImportError:
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 19694
diff changeset
92 pass