1 files changed, 60 insertions, 4 deletions
diff --git a/Lib/bisect.py b/Lib/bisect.py
index 47ef509a9b..343bd5da81 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