In test_heapq and test_bisect, test both the Python and the C implementation.

Originally written for GHOP by Josip Dzolonga, heavily patched by me.

2 files changed, 234 insertions, 159 deletions

diff --git a/Lib/test/test_bisect.py b/Lib/test/test_bisect.py
index f6e24a6..fb490b7 100644
--- a/Lib/test/test_bisect.py
+++ b/Lib/test/test_bisect.py
@@ -1,91 +1,113 @@
+import sys
 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):
+# We do a bit of trickery here to be able to test both the C implementation
+# and the Python implementation of the module.
+
+# Make it impossible to import the C implementation anymore.
+sys.modules['_bisect'] = 0
+# We must also handle the case that bisect was imported before.
+if 'bisect' in sys.modules:
+    del sys.modules['bisect']
+
+# Now we can import the module and get the pure Python implementation.
+import bisect as py_bisect
+
+# Restore everything to normal.
+del sys.modules['_bisect']
+del sys.modules['bisect']
 
-    precomputedCases = [
-        (bisect_right, [], 1, 0),
-        (bisect_right, [1], 0, 0),
-        (bisect_right, [1], 1, 1),
-        (bisect_right, [1], 2, 1),
-        (bisect_right, [1, 1], 0, 0),
-        (bisect_right, [1, 1], 1, 2),
-        (bisect_right, [1, 1], 2, 2),
-        (bisect_right, [1, 1, 1], 0, 0),
-        (bisect_right, [1, 1, 1], 1, 3),
-        (bisect_right, [1, 1, 1], 2, 3),
-        (bisect_right, [1, 1, 1, 1], 0, 0),
-        (bisect_right, [1, 1, 1, 1], 1, 4),
-        (bisect_right, [1, 1, 1, 1], 2, 4),
-        (bisect_right, [1, 2], 0, 0),
-        (bisect_right, [1, 2], 1, 1),
-        (bisect_right, [1, 2], 1.5, 1),
-        (bisect_right, [1, 2], 2, 2),
-        (bisect_right, [1, 2], 3, 2),
-        (bisect_right, [1, 1, 2, 2], 0, 0),
-        (bisect_right, [1, 1, 2, 2], 1, 2),
-        (bisect_right, [1, 1, 2, 2], 1.5, 2),
-        (bisect_right, [1, 1, 2, 2], 2, 4),
-        (bisect_right, [1, 1, 2, 2], 3, 4),
-        (bisect_right, [1, 2, 3], 0, 0),
-        (bisect_right, [1, 2, 3], 1, 1),
-        (bisect_right, [1, 2, 3], 1.5, 1),
-        (bisect_right, [1, 2, 3], 2, 2),
-        (bisect_right, [1, 2, 3], 2.5, 2),
-        (bisect_right, [1, 2, 3], 3, 3),
-        (bisect_right, [1, 2, 3], 4, 3),
-        (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
-        (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
-        (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
-        (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
-        (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
-        (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
-        (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
-        (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
-        (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
-
-        (bisect_left, [], 1, 0),
-        (bisect_left, [1], 0, 0),
-        (bisect_left, [1], 1, 0),
-        (bisect_left, [1], 2, 1),
-        (bisect_left, [1, 1], 0, 0),
-        (bisect_left, [1, 1], 1, 0),
-        (bisect_left, [1, 1], 2, 2),
-        (bisect_left, [1, 1, 1], 0, 0),
-        (bisect_left, [1, 1, 1], 1, 0),
-        (bisect_left, [1, 1, 1], 2, 3),
-        (bisect_left, [1, 1, 1, 1], 0, 0),
-        (bisect_left, [1, 1, 1, 1], 1, 0),
-        (bisect_left, [1, 1, 1, 1], 2, 4),
-        (bisect_left, [1, 2], 0, 0),
-        (bisect_left, [1, 2], 1, 0),
-        (bisect_left, [1, 2], 1.5, 1),
-        (bisect_left, [1, 2], 2, 1),
-        (bisect_left, [1, 2], 3, 2),
-        (bisect_left, [1, 1, 2, 2], 0, 0),
-        (bisect_left, [1, 1, 2, 2], 1, 0),
-        (bisect_left, [1, 1, 2, 2], 1.5, 2),
-        (bisect_left, [1, 1, 2, 2], 2, 2),
-        (bisect_left, [1, 1, 2, 2], 3, 4),
-        (bisect_left, [1, 2, 3], 0, 0),
-        (bisect_left, [1, 2, 3], 1, 0),
-        (bisect_left, [1, 2, 3], 1.5, 1),
-        (bisect_left, [1, 2, 3], 2, 1),
-        (bisect_left, [1, 2, 3], 2.5, 2),
-        (bisect_left, [1, 2, 3], 3, 2),
-        (bisect_left, [1, 2, 3], 4, 3),
-        (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
-        (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
-        (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
-        (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
-        (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
-        (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
-        (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
-        (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
-        (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
-    ]
+# This is now the module with the C implementation.
+import bisect as c_bisect
+
+
+class TestBisect(unittest.TestCase):
+    module = None
+
+    def setUp(self):
+        self.precomputedCases = [
+            (self.module.bisect_right, [], 1, 0),
+            (self.module.bisect_right, [1], 0, 0),
+            (self.module.bisect_right, [1], 1, 1),
+            (self.module.bisect_right, [1], 2, 1),
+            (self.module.bisect_right, [1, 1], 0, 0),
+            (self.module.bisect_right, [1, 1], 1, 2),
+            (self.module.bisect_right, [1, 1], 2, 2),
+            (self.module.bisect_right, [1, 1, 1], 0, 0),
+            (self.module.bisect_right, [1, 1, 1], 1, 3),
+            (self.module.bisect_right, [1, 1, 1], 2, 3),
+            (self.module.bisect_right, [1, 1, 1, 1], 0, 0),
+            (self.module.bisect_right, [1, 1, 1, 1], 1, 4),
+            (self.module.bisect_right, [1, 1, 1, 1], 2, 4),
+            (self.module.bisect_right, [1, 2], 0, 0),
+            (self.module.bisect_right, [1, 2], 1, 1),
+            (self.module.bisect_right, [1, 2], 1.5, 1),
+            (self.module.bisect_right, [1, 2], 2, 2),
+            (self.module.bisect_right, [1, 2], 3, 2),
+            (self.module.bisect_right, [1, 1, 2, 2], 0, 0),
+            (self.module.bisect_right, [1, 1, 2, 2], 1, 2),
+            (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2),
+            (self.module.bisect_right, [1, 1, 2, 2], 2, 4),
+            (self.module.bisect_right, [1, 1, 2, 2], 3, 4),
+            (self.module.bisect_right, [1, 2, 3], 0, 0),
+            (self.module.bisect_right, [1, 2, 3], 1, 1),
+            (self.module.bisect_right, [1, 2, 3], 1.5, 1),
+            (self.module.bisect_right, [1, 2, 3], 2, 2),
+            (self.module.bisect_right, [1, 2, 3], 2.5, 2),
+            (self.module.bisect_right, [1, 2, 3], 3, 3),
+            (self.module.bisect_right, [1, 2, 3], 4, 3),
+            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
+            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
+            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
+            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
+            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
+            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
+            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
+            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
+            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
+
+            (self.module.bisect_left, [], 1, 0),
+            (self.module.bisect_left, [1], 0, 0),
+            (self.module.bisect_left, [1], 1, 0),
+            (self.module.bisect_left, [1], 2, 1),
+            (self.module.bisect_left, [1, 1], 0, 0),
+            (self.module.bisect_left, [1, 1], 1, 0),
+            (self.module.bisect_left, [1, 1], 2, 2),
+            (self.module.bisect_left, [1, 1, 1], 0, 0),
+            (self.module.bisect_left, [1, 1, 1], 1, 0),
+            (self.module.bisect_left, [1, 1, 1], 2, 3),
+            (self.module.bisect_left, [1, 1, 1, 1], 0, 0),
+            (self.module.bisect_left, [1, 1, 1, 1], 1, 0),
+            (self.module.bisect_left, [1, 1, 1, 1], 2, 4),
+            (self.module.bisect_left, [1, 2], 0, 0),
+            (self.module.bisect_left, [1, 2], 1, 0),
+            (self.module.bisect_left, [1, 2], 1.5, 1),
+            (self.module.bisect_left, [1, 2], 2, 1),
+            (self.module.bisect_left, [1, 2], 3, 2),
+            (self.module.bisect_left, [1, 1, 2, 2], 0, 0),
+            (self.module.bisect_left, [1, 1, 2, 2], 1, 0),
+            (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2),
+            (self.module.bisect_left, [1, 1, 2, 2], 2, 2),
+            (self.module.bisect_left, [1, 1, 2, 2], 3, 4),
+            (self.module.bisect_left, [1, 2, 3], 0, 0),
+            (self.module.bisect_left, [1, 2, 3], 1, 0),
+            (self.module.bisect_left, [1, 2, 3], 1.5, 1),
+            (self.module.bisect_left, [1, 2, 3], 2, 1),
+            (self.module.bisect_left, [1, 2, 3], 2.5, 2),
+            (self.module.bisect_left, [1, 2, 3], 3, 2),
+            (self.module.bisect_left, [1, 2, 3], 4, 3),
+            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
+            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
+            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
+            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
+            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
+            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
+            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
+            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
+            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
+        ]
 
     def test_precomputed(self):
         for func, data, elem, expected in self.precomputedCases:
@@ -98,12 +120,12 @@ class TestBisect(unittest.TestCase):
             data = [randrange(0, n, 2) for j in xrange(i)]
             data.sort()
             elem = randrange(-1, n+1)
-            ip = bisect_left(data, elem)
+            ip = self.module.bisect_left(data, elem)
             if ip < len(data):
                 self.failUnless(elem <= data[ip])
             if ip > 0:
                 self.failUnless(data[ip-1] < elem)
-            ip = bisect_right(data, elem)
+            ip = self.module.bisect_right(data, elem)
             if ip < len(data):
                 self.failUnless(elem < data[ip])
             if ip > 0:
@@ -117,32 +139,39 @@ class TestBisect(unittest.TestCase):
                     hi = min(len(data), hi)
                     ip = func(data, elem, lo, hi)
                     self.failUnless(lo <= ip <= hi)
-                    if func is bisect_left and ip < hi:
+                    if func is self.module.bisect_left and ip < hi:
                         self.failUnless(elem <= data[ip])
-                    if func is bisect_left and ip > lo:
+                    if func is self.module.bisect_left and ip > lo:
                         self.failUnless(data[ip-1] < elem)
-                    if func is bisect_right and ip < hi:
+                    if func is self.module.bisect_right and ip < hi:
                         self.failUnless(elem < data[ip])
-                    if func is bisect_right and ip > lo:
+                    if func is self.module.bisect_right and ip > lo:
                         self.failUnless(data[ip-1] <= elem)
                     self.assertEqual(ip, max(lo, min(hi, expected)))
 
     def test_backcompatibility(self):
-        self.assertEqual(bisect, bisect_right)
+        self.assertEqual(self.module.bisect, self.module.bisect_right)
 
     def test_keyword_args(self):
         data = [10, 20, 30, 40, 50]
-        self.assertEqual(bisect_left(a=data, x=25, lo=1, hi=3), 2)
-        self.assertEqual(bisect_right(a=data, x=25, lo=1, hi=3), 2)
-        self.assertEqual(bisect(a=data, x=25, lo=1, hi=3), 2)
-        insort_left(a=data, x=25, lo=1, hi=3)
-        insort_right(a=data, x=25, lo=1, hi=3)
-        insort(a=data, x=25, lo=1, hi=3)
+        self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2)
+        self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2)
+        self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2)
+        self.module.insort_left(a=data, x=25, lo=1, hi=3)
+        self.module.insort_right(a=data, x=25, lo=1, hi=3)
+        self.module.insort(a=data, x=25, lo=1, hi=3)
         self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])
 
+class TestBisectPython(TestBisect):
+    module = py_bisect
+
+class TestBisectC(TestBisect):
+    module = c_bisect
+
 #==============================================================================
 
 class TestInsort(unittest.TestCase):
+    module = None
 
     def test_vsBuiltinSort(self, n=500):
         from random import choice
@@ -150,14 +179,20 @@ class TestInsort(unittest.TestCase):
             for i in xrange(n):
                 digit = choice("0123456789")
                 if digit in "02468":
-                    f = insort_left
+                    f = self.module.insort_left
                 else:
-                    f = insort_right
+                    f = self.module.insort_right
                 f(insorted, digit)
         self.assertEqual(sorted(insorted), insorted)
 
     def test_backcompatibility(self):
-        self.assertEqual(insort, insort_right)
+        self.assertEqual(self.module.insort, self.module.insort_right)
+
+class TestInsortPython(TestInsort):
+    module = py_bisect
+
+class TestInsortC(TestInsort):
+    module = c_bisect
 
 #==============================================================================
 
@@ -178,32 +213,44 @@ class CmpErr:
         raise ZeroDivisionError
 
 class TestErrorHandling(unittest.TestCase):
+    module = None
 
     def test_non_sequence(self):
-        for f in (bisect_left, bisect_right, insort_left, insort_right):
+        for f in (self.module.bisect_left, self.module.bisect_right,
+                  self.module.insort_left, self.module.insort_right):
             self.assertRaises(TypeError, f, 10, 10)
 
     def test_len_only(self):
-        for f in (bisect_left, bisect_right, insort_left, insort_right):
+        for f in (self.module.bisect_left, self.module.bisect_right,
+                  self.module.insort_left, self.module.insort_right):
             self.assertRaises(AttributeError, f, LenOnly(), 10)
 
     def test_get_only(self):
-        for f in (bisect_left, bisect_right, insort_left, insort_right):
+        for f in (self.module.bisect_left, self.module.bisect_right,
+                  self.module.insort_left, self.module.insort_right):
             self.assertRaises(AttributeError, f, GetOnly(), 10)
 
     def test_cmp_err(self):
         seq = [CmpErr(), CmpErr(), CmpErr()]
-        for f in (bisect_left, bisect_right, insort_left, insort_right):
+        for f in (self.module.bisect_left, self.module.bisect_right,
+                  self.module.insort_left, self.module.insort_right):
             self.assertRaises(ZeroDivisionError, f, seq, 10)
 
     def test_arg_parsing(self):
-        for f in (bisect_left, bisect_right, insort_left, insort_right):
+        for f in (self.module.bisect_left, self.module.bisect_right,
+                  self.module.insort_left, self.module.insort_right):
             self.assertRaises(TypeError, f, 10)
 
+class TestErrorHandlingPython(TestErrorHandling):
+    module = py_bisect
+
+class TestErrorHandlingC(TestErrorHandling):
+    module = c_bisect
+
 #==============================================================================
 
 libreftest = """
-Example from the Library Reference:  Doc/lib/libbisect.tex
+Example from the Library Reference:  Doc/library/bisect.rst
 
 The bisect() function is generally useful for categorizing numeric data.
 This example uses bisect() to look up a letter grade for an exam total
@@ -229,12 +276,10 @@ __test__ = {'libreftest' : libreftest}
 
 def test_main(verbose=None):
     from test import test_bisect
-    from types import BuiltinFunctionType
-    import sys
 
-    test_classes = [TestBisect, TestInsort]
-    if isinstance(bisect_left, BuiltinFunctionType):
-        test_classes.append(TestErrorHandling)
+    test_classes = [TestBisectPython, TestBisectC,
+                    TestInsortPython, TestInsortC,
+                    TestErrorHandlingPython, TestErrorHandlingC]
 
     test_support.run_unittest(*test_classes)
     test_support.run_doctest(test_bisect, verbose)
diff --git a/Lib/test/test_heapq.py b/Lib/test/test_heapq.py
index b2bbfab..7f6e4b5 100644
--- a/Lib/test/test_heapq.py
+++ b/Lib/test/test_heapq.py
@@ -1,21 +1,32 @@
 """Unittests for heapq."""
 
-from heapq import heappush, heappop, heapify, heapreplace, merge, nlargest, nsmallest
 import random
 import unittest
 from test import test_support
 import sys
 
+# We do a bit of trickery here to be able to test both the C implementation
+# and the Python implementation of the module.
+
+# Make it impossible to import the C implementation anymore.
+sys.modules['_heapq'] = 0
+# We must also handle the case that heapq was imported before.
+if 'heapq' in sys.modules:
+    del sys.modules['heapq']
+
+# Now we can import the module and get the pure Python implementation.
+import heapq as py_heapq
+
+# Restore everything to normal.
+del sys.modules['_heapq']
+del sys.modules['heapq']
+
+# This is now the module with the C implementation.
+import heapq as c_heapq
 
-def heapiter(heap):
-    # An iterator returning a heap's elements, smallest-first.
-    try:
-        while 1:
-            yield heappop(heap)
-    except IndexError:
-        pass
 
 class TestHeap(unittest.TestCase):
+    module = None
 
     def test_push_pop(self):
         # 1) Push 256 random numbers and pop them off, verifying all's OK.
@@ -25,11 +36,11 @@ class TestHeap(unittest.TestCase):
         for i in range(256):
             item = random.random()
             data.append(item)
-            heappush(heap, item)
+            self.module.heappush(heap, item)
             self.check_invariant(heap)
         results = []
         while heap:
-            item = heappop(heap)
+            item = self.module.heappop(heap)
             self.check_invariant(heap)
             results.append(item)
         data_sorted = data[:]
@@ -38,10 +49,10 @@ class TestHeap(unittest.TestCase):
         # 2) Check that the invariant holds for a sorted array
         self.check_invariant(results)
 
-        self.assertRaises(TypeError, heappush, [])
+        self.assertRaises(TypeError, self.module.heappush, [])
         try:
-            self.assertRaises(TypeError, heappush, None, None)
-            self.assertRaises(TypeError, heappop, None)
+            self.assertRaises(TypeError, self.module.heappush, None, None)
+            self.assertRaises(TypeError, self.module.heappop, None)
         except AttributeError:
             pass
 
@@ -55,21 +66,29 @@ class TestHeap(unittest.TestCase):
     def test_heapify(self):
         for size in range(30):
             heap = [random.random() for dummy in range(size)]
-            heapify(heap)
+            self.module.heapify(heap)
             self.check_invariant(heap)
 
-        self.assertRaises(TypeError, heapify, None)
+        self.assertRaises(TypeError, self.module.heapify, None)
 
     def test_naive_nbest(self):
         data = [random.randrange(2000) for i in range(1000)]
         heap = []
         for item in data:
-            heappush(heap, item)
+            self.module.heappush(heap, item)
             if len(heap) > 10:
-                heappop(heap)
+                self.module.heappop(heap)
         heap.sort()
         self.assertEqual(heap, sorted(data)[-10:])
 
+    def heapiter(self, heap):
+        # An iterator returning a heap's elements, smallest-first.
+        try:
+            while 1:
+                yield self.module.heappop(heap)
+        except IndexError:
+            pass
+
     def test_nbest(self):
         # Less-naive "N-best" algorithm, much faster (if len(data) is big
         # enough <wink>) than sorting all of data.  However, if we had a max
@@ -78,15 +97,15 @@ class TestHeap(unittest.TestCase):
         # (10 log-time steps).
         data = [random.randrange(2000) for i in range(1000)]
         heap = data[:10]
-        heapify(heap)
+        self.module.heapify(heap)
         for item in data[10:]:
             if item > heap[0]:  # this gets rarer the longer we run
-                heapreplace(heap, item)
-        self.assertEqual(list(heapiter(heap)), sorted(data)[-10:])
+                self.module.heapreplace(heap, item)
+        self.assertEqual(list(self.heapiter(heap)), sorted(data)[-10:])
 
-        self.assertRaises(TypeError, heapreplace, None)
-        self.assertRaises(TypeError, heapreplace, None, None)
-        self.assertRaises(IndexError, heapreplace, [], None)
+        self.assertRaises(TypeError, self.module.heapreplace, None)
+        self.assertRaises(TypeError, self.module.heapreplace, None, None)
+        self.assertRaises(IndexError, self.module.heapreplace, [], None)
 
     def test_heapsort(self):
         # Exercise everything with repeated heapsort checks
@@ -95,12 +114,12 @@ class TestHeap(unittest.TestCase):
             data = [random.randrange(25) for i in range(size)]
             if trial & 1:     # Half of the time, use heapify
                 heap = data[:]
-                heapify(heap)
+                self.module.heapify(heap)
             else:             # The rest of the time, use heappush
                 heap = []
                 for item in data:
-                    heappush(heap, item)
-            heap_sorted = [heappop(heap) for i in range(size)]
+                    self.module.heappush(heap, item)
+            heap_sorted = [self.module.heappop(heap) for i in range(size)]
             self.assertEqual(heap_sorted, sorted(data))
 
     def test_merge(self):
@@ -108,8 +127,8 @@ class TestHeap(unittest.TestCase):
         for i in xrange(random.randrange(5)):
             row = sorted(random.randrange(1000) for j in range(random.randrange(10)))
             inputs.append(row)
-        self.assertEqual(sorted(chain(*inputs)), list(merge(*inputs)))
-        self.assertEqual(list(merge()), [])
+        self.assertEqual(sorted(chain(*inputs)), list(self.module.merge(*inputs)))
+        self.assertEqual(list(self.module.merge()), [])
 
     def test_merge_stability(self):
         class Int(int):
@@ -123,25 +142,32 @@ class TestHeap(unittest.TestCase):
             inputs[stream].append(obj)
         for stream in inputs:
             stream.sort()
-        result = [i.pair for i in merge(*inputs)]
+        result = [i.pair for i in self.module.merge(*inputs)]
         self.assertEqual(result, sorted(result))
 
     def test_nsmallest(self):
         data = [(random.randrange(2000), i) for i in range(1000)]
         for f in (None, lambda x:  x[0] * 547 % 2000):
             for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):
-                self.assertEqual(nsmallest(n, data), sorted(data)[:n])
-                self.assertEqual(nsmallest(n, data, key=f),
+                self.assertEqual(self.module.nsmallest(n, data), sorted(data)[:n])
+                self.assertEqual(self.module.nsmallest(n, data, key=f),
                                  sorted(data, key=f)[:n])
 
     def test_nlargest(self):
         data = [(random.randrange(2000), i) for i in range(1000)]
         for f in (None, lambda x:  x[0] * 547 % 2000):
             for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):
-                self.assertEqual(nlargest(n, data), sorted(data, reverse=True)[:n])
-                self.assertEqual(nlargest(n, data, key=f),
+                self.assertEqual(self.module.nlargest(n, data),
+                                 sorted(data, reverse=True)[:n])
+                self.assertEqual(self.module.nlargest(n, data, key=f),
                                  sorted(data, key=f, reverse=True)[:n])
 
+class TestHeapPython(TestHeap):
+    module = py_heapq
+
+class TestHeapC(TestHeap):
+    module = c_heapq
+
 
 #==============================================================================
 
@@ -238,44 +264,49 @@ def L(seqn):
     return chain(imap(lambda x:x, R(Ig(G(seqn)))))
 
 class TestErrorHandling(unittest.TestCase):
+    # only for C implementation
+    module = c_heapq
 
     def test_non_sequence(self):
-        for f in (heapify, heappop):
+        for f in (self.module.heapify, self.module.heappop):
             self.assertRaises(TypeError, f, 10)
-        for f in (heappush, heapreplace, nlargest, nsmallest):
+        for f in (self.module.heappush, self.module.heapreplace,
+                  self.module.nlargest, self.module.nsmallest):
             self.assertRaises(TypeError, f, 10, 10)
 
     def test_len_only(self):
-        for f in (heapify, heappop):
+        for f in (self.module.heapify, self.module.heappop):
             self.assertRaises(TypeError, f, LenOnly())
-        for f in (heappush, heapreplace):
+        for f in (self.module.heappush, self.module.heapreplace):
             self.assertRaises(TypeError, f, LenOnly(), 10)
-        for f in (nlargest, nsmallest):
+        for f in (self.module.nlargest, self.module.nsmallest):
             self.assertRaises(TypeError, f, 2, LenOnly())
 
     def test_get_only(self):
-        for f in (heapify, heappop):
+        for f in (self.module.heapify, self.module.heappop):
             self.assertRaises(TypeError, f, GetOnly())
-        for f in (heappush, heapreplace):
+        for f in (self.module.heappush, self.module.heapreplace):
             self.assertRaises(TypeError, f, GetOnly(), 10)
-        for f in (nlargest, nsmallest):
+        for f in (self.module.nlargest, self.module.nsmallest):
             self.assertRaises(TypeError, f, 2, GetOnly())
 
     def test_get_only(self):
         seq = [CmpErr(), CmpErr(), CmpErr()]
-        for f in (heapify, heappop):
+        for f in (self.module.heapify, self.module.heappop):
             self.assertRaises(ZeroDivisionError, f, seq)
-        for f in (heappush, heapreplace):
+        for f in (self.module.heappush, self.module.heapreplace):
             self.assertRaises(ZeroDivisionError, f, seq, 10)
-        for f in (nlargest, nsmallest):
+        for f in (self.module.nlargest, self.module.nsmallest):
             self.assertRaises(ZeroDivisionError, f, 2, seq)
 
     def test_arg_parsing(self):
-        for f in (heapify, heappop, heappush, heapreplace, nlargest, nsmallest):
+        for f in (self.module.heapify, self.module.heappop,
+                  self.module.heappush, self.module.heapreplace,
+                  self.module.nlargest, self.module.nsmallest):
             self.assertRaises(TypeError, f, 10)
 
     def test_iterable_args(self):
-        for f in  (nlargest, nsmallest):
+        for f in (self.module.nlargest, self.module.nsmallest):
             for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)):
                 for g in (G, I, Ig, L, R):
                     self.assertEqual(f(2, g(s)), f(2,s))
@@ -284,15 +315,14 @@ class TestErrorHandling(unittest.TestCase):
                 self.assertRaises(TypeError, f, 2, N(s))
                 self.assertRaises(ZeroDivisionError, f, 2, E(s))
 
+
 #==============================================================================
 
 
 def test_main(verbose=None):
     from types import BuiltinFunctionType
 
-    test_classes = [TestHeap]
-    if isinstance(heapify, BuiltinFunctionType):
-        test_classes.append(TestErrorHandling)
+    test_classes = [TestHeapPython, TestHeapC, TestErrorHandling]
     test_support.run_unittest(*test_classes)
 
     # verify reference counting