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.
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 @@
else: lo = mid+1
a.insert(lo, x)
+insort = insort_right # backward compatibility
-def bisect(a, x, lo=0, hi=None):
- """Find the index where to insert item x in list a, assuming a is sorted."""
+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.
+ """
+
if hi is None:
hi = len(a)
while lo < hi:
@@ -21,3 +38,42 @@
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