From 36cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73 Mon Sep 17 00:00:00 2001 From: Tim Peters Date: Fri, 29 Dec 2000 02:06:45 +0000 Subject: Fred, THIS NEEDS DOCS! The function docstrings tell the tale. Christmas present to myself: the bisect module didn't define what happened if the new element was already in the list. It so happens that it inserted the new element "to the right" of all equal elements. Since it wasn't defined, among other bad implications it was a mystery how to use bisect to determine whether an element was already in the list (I've seen code that *assumed* "to the right" without justification). Added new methods bisect_left and insort_left that insert "to the left" instead; made the old names bisect and insort aliases for the new names bisect_right and insort_right; beefed up docstrings to explain what these actually do; and added a std test for the bisect module. --- Lib/bisect.py | 64 ++++++++++++++++++++-- Lib/test/output/test_bisect | 1 + Lib/test/test_bisect.py | 127 ++++++++++++++++++++++++++++++++++++++++++++ Misc/NEWS | 12 +++++ 4 files changed, 200 insertions(+), 4 deletions(-) create mode 100644 Lib/test/output/test_bisect create mode 100644 Lib/test/test_bisect.py 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) diff --git a/Misc/NEWS b/Misc/NEWS index df81a12..8f66106 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -34,6 +34,18 @@ Core language, builtins, and interpreter item. Such algorithms normally end up running in quadratic time; using popitem() they can usually be made to run in linear time. + +Standard library + +- The bisect module has new functions bisect_left, insort_left, + bisect_right and insort_right. The old names bisect and insort + are now aliases for bisect_right and insort_right. XXX_right + and XXX_left methods differ in what happens when the new element + compares equal to one or more elements already in the list: the + XXX_left methods insert to the left, the XXX_right methods to the + right. + + Windows changes - select module: By default under Windows, a select() call -- cgit v0.12