SF Patch #864863: Bisect C implementation

(Contributed by Dmitry Vasiliev.)

2 files changed, 18 insertions, 15 deletions

diff --git a/Lib/bisect.py b/Lib/bisect.py
index c9e6c60..152f6c7 100644
--- a/Lib/bisect.py
+++ b/Lib/bisect.py
@@ -76,3 +76,9 @@ def bisect_left(a, x, lo=0, hi=None):
         if a[mid] < x: lo = mid+1
         else: hi = mid
     return lo
+
+# Overwrite above definitions with a fast C implementation
+try:
+    from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
+except ImportError:
+    pass
diff --git a/Lib/test/test_bisect.py b/Lib/test/test_bisect.py
index 549978d..809d8af 100644
--- a/Lib/test/test_bisect.py
+++ b/Lib/test/test_bisect.py
@@ -1,6 +1,7 @@
 import unittest
 from test import test_support
 from bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
+from UserList import UserList
 
 class TestBisect(unittest.TestCase):
 
@@ -89,6 +90,7 @@ class TestBisect(unittest.TestCase):
     def test_precomputed(self):
         for func, data, elem, expected in self.precomputedCases:
             self.assertEqual(func(data, elem), expected)
+            self.assertEqual(func(UserList(data), elem), expected)
 
     def test_random(self, n=25):
         from random import randrange
@@ -132,22 +134,17 @@ class TestBisect(unittest.TestCase):
 
 class TestInsort(unittest.TestCase):
 
-    def test_vsListSort(self, n=500):
+    def test_vsBuiltinSort(self, n=500):
         from random import choice
-        digits = "0123456789"
-        raw = []
-        insorted = []
-        for i in range(n):
-            digit = choice(digits)
-            raw.append(digit)
-            if digit in "02468":
-                f = insort_left
-            else:
-                f = insort_right
-            f(insorted, digit)
-        sorted = raw[:]
-        sorted.sort()
-        self.assertEqual(sorted, insorted)
+        for insorted in (list(), UserList()):
+            for i in xrange(n):
+                digit = choice("0123456789")
+                if digit in "02468":
+                    f = insort_left
+                else:
+                    f = insort_right
+                f(insorted, digit)
+        self.assertEqual(sorted(insorted), insorted)
 
     def test_backcompatibility(self):
         self.assertEqual(insort, insort_right)