summaryrefslogtreecommitdiffstats
path: root/Lib
diff options
context:
space:
mode:
Diffstat (limited to 'Lib')
-rw-r--r--Lib/bisect.py64
-rw-r--r--Lib/test/output/test_bisect1
-rw-r--r--Lib/test/test_bisect.py127
3 files changed, 188 insertions, 4 deletions
diff --git a/Lib/bisect.py b/Lib/bisect.py
index 47ef509..343bd5d 100644
--- a/Lib/bisect.py
+++ b/Lib/bisect.py
@@ -1,8 +1,15 @@
"""Bisection algorithms."""
-def insort(a, x, lo=0, hi=None):
- """Insert item x in list a, and keep it sorted assuming a is sorted."""
+def insort_right(a, x, lo=0, hi=None):
+ """Insert item x in list a, and keep it sorted assuming a is sorted.
+
+ If x is already in a, insert it to the right of the rightmost x.
+
+ Optional args lo (default 0) and hi (default len(a)) bound the
+ slice of a to be searched.
+ """
+
if hi is None:
hi = len(a)
while lo < hi:
@@ -11,9 +18,19 @@ def insort(a, x, lo=0, hi=None):
else: lo = mid+1
a.insert(lo, x)
+insort = insort_right # backward compatibility
+
+def bisect_right(a, x, lo=0, hi=None):
+ """Return the index where to insert item x in list a, assuming a is sorted.
+
+ The return value i is such that all e in a[:i] have e <= x, and all e in
+ a[i:] have e > x. So if x already appears in the list, i points just
+ beyond the rightmost x already there.
+
+ Optional args lo (default 0) and hi (default len(a)) bound the
+ slice of a to be searched.
+ """
-def bisect(a, x, lo=0, hi=None):
- """Find the index where to insert item x in list a, assuming a is sorted."""
if hi is None:
hi = len(a)
while lo < hi:
@@ -21,3 +38,42 @@ def bisect(a, x, lo=0, hi=None):
if x < a[mid]: hi = mid
else: lo = mid+1
return lo
+
+bisect = bisect_right # backward compatibility
+
+def insort_left(a, x, lo=0, hi=None):
+ """Insert item x in list a, and keep it sorted assuming a is sorted.
+
+ If x is already in a, insert it to the left of the leftmost x.
+
+ Optional args lo (default 0) and hi (default len(a)) bound the
+ slice of a to be searched.
+ """
+
+ if hi is None:
+ hi = len(a)
+ while lo < hi:
+ mid = (lo+hi)/2
+ if a[mid] < x: lo = mid+1
+ else: hi = mid
+ a.insert(lo, x)
+
+
+def bisect_left(a, x, lo=0, hi=None):
+ """Return the index where to insert item x in list a, assuming a is sorted.
+
+ The return value i is such that all e in a[:i] have e < x, and all e in
+ a[i:] have e >= x. So if x already appears in the list, i points just
+ before the leftmost x already there.
+
+ Optional args lo (default 0) and hi (default len(a)) bound the
+ slice of a to be searched.
+ """
+
+ if hi is None:
+ hi = len(a)
+ while lo < hi:
+ mid = (lo+hi)/2
+ if a[mid] < x: lo = mid+1
+ else: hi = mid
+ return lo
diff --git a/Lib/test/output/test_bisect b/Lib/test/output/test_bisect
new file mode 100644
index 0000000..a91c584
--- /dev/null
+++ b/Lib/test/output/test_bisect
@@ -0,0 +1 @@
+test_bisect
diff --git a/Lib/test/test_bisect.py b/Lib/test/test_bisect.py
new file mode 100644
index 0000000..1292915
--- /dev/null
+++ b/Lib/test/test_bisect.py
@@ -0,0 +1,127 @@
+from test_support import TestFailed
+
+import bisect
+import sys
+
+nerrors = 0
+
+def check_bisect(func, list, elt, expected):
+ global nerrors
+ got = func(list, elt)
+ if got != expected:
+ print >> sys.stderr, \
+ "expected %s(%s, %s) -> %s, but got %s" % (func.__name__,
+ list,
+ elt,
+ expected,
+ got)
+ nerrors += 1
+
+# XXX optional slice arguments need tests.
+
+check_bisect(bisect.bisect_right, [], 1, 0)
+check_bisect(bisect.bisect_right, [1], 0, 0)
+check_bisect(bisect.bisect_right, [1], 1, 1)
+check_bisect(bisect.bisect_right, [1], 2, 1)
+check_bisect(bisect.bisect_right, [1, 1], 0, 0)
+check_bisect(bisect.bisect_right, [1, 1], 1, 2)
+check_bisect(bisect.bisect_right, [1, 1], 2, 2)
+check_bisect(bisect.bisect_right, [1, 1, 1], 0, 0)
+check_bisect(bisect.bisect_right, [1, 1, 1], 1, 3)
+check_bisect(bisect.bisect_right, [1, 1, 1], 2, 3)
+check_bisect(bisect.bisect_right, [1, 1, 1, 1], 0, 0)
+check_bisect(bisect.bisect_right, [1, 1, 1, 1], 1, 4)
+check_bisect(bisect.bisect_right, [1, 1, 1, 1], 2, 4)
+check_bisect(bisect.bisect_right, [1, 2], 0, 0)
+check_bisect(bisect.bisect_right, [1, 2], 1, 1)
+check_bisect(bisect.bisect_right, [1, 2], 1.5, 1)
+check_bisect(bisect.bisect_right, [1, 2], 2, 2)
+check_bisect(bisect.bisect_right, [1, 2], 3, 2)
+check_bisect(bisect.bisect_right, [1, 1, 2, 2], 0, 0)
+check_bisect(bisect.bisect_right, [1, 1, 2, 2], 1, 2)
+check_bisect(bisect.bisect_right, [1, 1, 2, 2], 1.5, 2)
+check_bisect(bisect.bisect_right, [1, 1, 2, 2], 2, 4)
+check_bisect(bisect.bisect_right, [1, 1, 2, 2], 3, 4)
+check_bisect(bisect.bisect_right, [1, 2, 3], 0, 0)
+check_bisect(bisect.bisect_right, [1, 2, 3], 1, 1)
+check_bisect(bisect.bisect_right, [1, 2, 3], 1.5, 1)
+check_bisect(bisect.bisect_right, [1, 2, 3], 2, 2)
+check_bisect(bisect.bisect_right, [1, 2, 3], 2.5, 2)
+check_bisect(bisect.bisect_right, [1, 2, 3], 3, 3)
+check_bisect(bisect.bisect_right, [1, 2, 3], 4, 3)
+check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0)
+check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1)
+check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1)
+check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3)
+check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3)
+check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6)
+check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6)
+check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10)
+check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
+
+check_bisect(bisect.bisect_left, [], 1, 0)
+check_bisect(bisect.bisect_left, [1], 0, 0)
+check_bisect(bisect.bisect_left, [1], 1, 0)
+check_bisect(bisect.bisect_left, [1], 2, 1)
+check_bisect(bisect.bisect_left, [1, 1], 0, 0)
+check_bisect(bisect.bisect_left, [1, 1], 1, 0)
+check_bisect(bisect.bisect_left, [1, 1], 2, 2)
+check_bisect(bisect.bisect_left, [1, 1, 1], 0, 0)
+check_bisect(bisect.bisect_left, [1, 1, 1], 1, 0)
+check_bisect(bisect.bisect_left, [1, 1, 1], 2, 3)
+check_bisect(bisect.bisect_left, [1, 1, 1, 1], 0, 0)
+check_bisect(bisect.bisect_left, [1, 1, 1, 1], 1, 0)
+check_bisect(bisect.bisect_left, [1, 1, 1, 1], 2, 4)
+check_bisect(bisect.bisect_left, [1, 2], 0, 0)
+check_bisect(bisect.bisect_left, [1, 2], 1, 0)
+check_bisect(bisect.bisect_left, [1, 2], 1.5, 1)
+check_bisect(bisect.bisect_left, [1, 2], 2, 1)
+check_bisect(bisect.bisect_left, [1, 2], 3, 2)
+check_bisect(bisect.bisect_left, [1, 1, 2, 2], 0, 0)
+check_bisect(bisect.bisect_left, [1, 1, 2, 2], 1, 0)
+check_bisect(bisect.bisect_left, [1, 1, 2, 2], 1.5, 2)
+check_bisect(bisect.bisect_left, [1, 1, 2, 2], 2, 2)
+check_bisect(bisect.bisect_left, [1, 1, 2, 2], 3, 4)
+check_bisect(bisect.bisect_left, [1, 2, 3], 0, 0)
+check_bisect(bisect.bisect_left, [1, 2, 3], 1, 0)
+check_bisect(bisect.bisect_left, [1, 2, 3], 1.5, 1)
+check_bisect(bisect.bisect_left, [1, 2, 3], 2, 1)
+check_bisect(bisect.bisect_left, [1, 2, 3], 2.5, 2)
+check_bisect(bisect.bisect_left, [1, 2, 3], 3, 2)
+check_bisect(bisect.bisect_left, [1, 2, 3], 4, 3)
+check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0)
+check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0)
+check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1)
+check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1)
+check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3)
+check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3)
+check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6)
+check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6)
+check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
+
+def check_insort(n):
+ global nerrors
+ from random import choice
+ import sys
+ digits = "0123456789"
+ raw = []
+ insorted = []
+ for i in range(n):
+ digit = choice(digits)
+ raw.append(digit)
+ if digit in "02468":
+ f = bisect.insort_left
+ else:
+ f = bisect.insort_right
+ f(insorted, digit)
+ sorted = raw[:]
+ sorted.sort()
+ if sorted == insorted:
+ return
+ print >> sys.stderr, "insort test failed: raw %s got %s" % (raw, insorted)
+ nerrors += 1
+
+check_insort(500)
+
+if nerrors:
+ raise TestFailed("%d errors in test_bisect" % nerrors)
generated by cgit v0.12 at 2025-02-26 18:47:17 (GMT)