Mercurial > cpython-lru_cache-weakref

annotate Lib/bisect.py @ 25838:8540887bcec6 2.2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Backport of 2.183: Fix memory leak in add_subclass() found by NealN with valgrind.
author Guido van Rossum <guido@python.org>
date Fri, 18 Oct 2002 13:42:21 +0000
parents 3716b116fb31
children ed20259a1ea5
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
11691
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
12 if hi is None:
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
13 hi = len(a)
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
14 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
15 mid = (lo+hi)//2
11691
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
16 if x < a[mid]: hi = mid
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
17 else: lo = mid+1
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
18 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
19
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
20 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
21
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
22 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
23 """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
24
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
25 The return value i is such that all e in a[:i] have e <= x, and all e in
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
26 a[i:] have e > x. So if x already appears in the list, i points just
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
27 beyond the rightmost x already there.
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
28
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
29 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
30 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
31 """
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
32
11691
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
33 if hi is None:
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
34 hi = len(a)
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
35 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
36 mid = (lo+hi)//2
11691
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
37 if x < a[mid]: hi = mid
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
38 else: lo = mid+1
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 7752
diff changeset
39 return lo
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
40
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
41 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
42
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
43 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
44 """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
45
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
46 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
47
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
48 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
49 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
50 """
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 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
53 hi = len(a)
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
54 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
55 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
56 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
57 else: hi = mid
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
58 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
59
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
60
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
61 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
62 """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
63
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
64 The return value i is such that all e in a[:i] have e < x, and all e in
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
65 a[i:] have e >= x. So if x already appears in the list, i points just
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
66 before the leftmost x already there.
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
67
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
68 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
69 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
70 """
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
71
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
72 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
73 hi = len(a)
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
74 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
75 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
76 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
77 else: hi = mid
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents: 11691
diff changeset
78 return lo