+++ /dev/null
-import sys\r
-import unittest\r
-from test import test_support\r
-from UserList import UserList\r
-\r
-# We do a bit of trickery here to be able to test both the C implementation\r
-# and the Python implementation of the module.\r
-\r
-# Make it impossible to import the C implementation anymore.\r
-sys.modules['_bisect'] = 0\r
-# We must also handle the case that bisect was imported before.\r
-if 'bisect' in sys.modules:\r
- del sys.modules['bisect']\r
-\r
-# Now we can import the module and get the pure Python implementation.\r
-import bisect as py_bisect\r
-\r
-# Restore everything to normal.\r
-del sys.modules['_bisect']\r
-del sys.modules['bisect']\r
-\r
-# This is now the module with the C implementation.\r
-import bisect as c_bisect\r
-\r
-\r
-class TestBisect(unittest.TestCase):\r
- module = None\r
-\r
- def setUp(self):\r
- self.precomputedCases = [\r
- (self.module.bisect_right, [], 1, 0),\r
- (self.module.bisect_right, [1], 0, 0),\r
- (self.module.bisect_right, [1], 1, 1),\r
- (self.module.bisect_right, [1], 2, 1),\r
- (self.module.bisect_right, [1, 1], 0, 0),\r
- (self.module.bisect_right, [1, 1], 1, 2),\r
- (self.module.bisect_right, [1, 1], 2, 2),\r
- (self.module.bisect_right, [1, 1, 1], 0, 0),\r
- (self.module.bisect_right, [1, 1, 1], 1, 3),\r
- (self.module.bisect_right, [1, 1, 1], 2, 3),\r
- (self.module.bisect_right, [1, 1, 1, 1], 0, 0),\r
- (self.module.bisect_right, [1, 1, 1, 1], 1, 4),\r
- (self.module.bisect_right, [1, 1, 1, 1], 2, 4),\r
- (self.module.bisect_right, [1, 2], 0, 0),\r
- (self.module.bisect_right, [1, 2], 1, 1),\r
- (self.module.bisect_right, [1, 2], 1.5, 1),\r
- (self.module.bisect_right, [1, 2], 2, 2),\r
- (self.module.bisect_right, [1, 2], 3, 2),\r
- (self.module.bisect_right, [1, 1, 2, 2], 0, 0),\r
- (self.module.bisect_right, [1, 1, 2, 2], 1, 2),\r
- (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2),\r
- (self.module.bisect_right, [1, 1, 2, 2], 2, 4),\r
- (self.module.bisect_right, [1, 1, 2, 2], 3, 4),\r
- (self.module.bisect_right, [1, 2, 3], 0, 0),\r
- (self.module.bisect_right, [1, 2, 3], 1, 1),\r
- (self.module.bisect_right, [1, 2, 3], 1.5, 1),\r
- (self.module.bisect_right, [1, 2, 3], 2, 2),\r
- (self.module.bisect_right, [1, 2, 3], 2.5, 2),\r
- (self.module.bisect_right, [1, 2, 3], 3, 3),\r
- (self.module.bisect_right, [1, 2, 3], 4, 3),\r
- (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),\r
- (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),\r
- (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),\r
- (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),\r
- (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),\r
- (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),\r
- (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),\r
- (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),\r
- (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),\r
-\r
- (self.module.bisect_left, [], 1, 0),\r
- (self.module.bisect_left, [1], 0, 0),\r
- (self.module.bisect_left, [1], 1, 0),\r
- (self.module.bisect_left, [1], 2, 1),\r
- (self.module.bisect_left, [1, 1], 0, 0),\r
- (self.module.bisect_left, [1, 1], 1, 0),\r
- (self.module.bisect_left, [1, 1], 2, 2),\r
- (self.module.bisect_left, [1, 1, 1], 0, 0),\r
- (self.module.bisect_left, [1, 1, 1], 1, 0),\r
- (self.module.bisect_left, [1, 1, 1], 2, 3),\r
- (self.module.bisect_left, [1, 1, 1, 1], 0, 0),\r
- (self.module.bisect_left, [1, 1, 1, 1], 1, 0),\r
- (self.module.bisect_left, [1, 1, 1, 1], 2, 4),\r
- (self.module.bisect_left, [1, 2], 0, 0),\r
- (self.module.bisect_left, [1, 2], 1, 0),\r
- (self.module.bisect_left, [1, 2], 1.5, 1),\r
- (self.module.bisect_left, [1, 2], 2, 1),\r
- (self.module.bisect_left, [1, 2], 3, 2),\r
- (self.module.bisect_left, [1, 1, 2, 2], 0, 0),\r
- (self.module.bisect_left, [1, 1, 2, 2], 1, 0),\r
- (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2),\r
- (self.module.bisect_left, [1, 1, 2, 2], 2, 2),\r
- (self.module.bisect_left, [1, 1, 2, 2], 3, 4),\r
- (self.module.bisect_left, [1, 2, 3], 0, 0),\r
- (self.module.bisect_left, [1, 2, 3], 1, 0),\r
- (self.module.bisect_left, [1, 2, 3], 1.5, 1),\r
- (self.module.bisect_left, [1, 2, 3], 2, 1),\r
- (self.module.bisect_left, [1, 2, 3], 2.5, 2),\r
- (self.module.bisect_left, [1, 2, 3], 3, 2),\r
- (self.module.bisect_left, [1, 2, 3], 4, 3),\r
- (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),\r
- (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),\r
- (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),\r
- (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),\r
- (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),\r
- (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),\r
- (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),\r
- (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),\r
- (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)\r
- ]\r
-\r
- def test_precomputed(self):\r
- for func, data, elem, expected in self.precomputedCases:\r
- self.assertEqual(func(data, elem), expected)\r
- self.assertEqual(func(UserList(data), elem), expected)\r
-\r
- def test_negative_lo(self):\r
- # Issue 3301\r
- mod = self.module\r
- self.assertRaises(ValueError, mod.bisect_left, [1, 2, 3], 5, -1, 3),\r
- self.assertRaises(ValueError, mod.bisect_right, [1, 2, 3], 5, -1, 3),\r
- self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3),\r
- self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3),\r
-\r
- def test_random(self, n=25):\r
- from random import randrange\r
- for i in xrange(n):\r
- data = [randrange(0, n, 2) for j in xrange(i)]\r
- data.sort()\r
- elem = randrange(-1, n+1)\r
- ip = self.module.bisect_left(data, elem)\r
- if ip < len(data):\r
- self.assertTrue(elem <= data[ip])\r
- if ip > 0:\r
- self.assertTrue(data[ip-1] < elem)\r
- ip = self.module.bisect_right(data, elem)\r
- if ip < len(data):\r
- self.assertTrue(elem < data[ip])\r
- if ip > 0:\r
- self.assertTrue(data[ip-1] <= elem)\r
-\r
- def test_optionalSlicing(self):\r
- for func, data, elem, expected in self.precomputedCases:\r
- for lo in xrange(4):\r
- lo = min(len(data), lo)\r
- for hi in xrange(3,8):\r
- hi = min(len(data), hi)\r
- ip = func(data, elem, lo, hi)\r
- self.assertTrue(lo <= ip <= hi)\r
- if func is self.module.bisect_left and ip < hi:\r
- self.assertTrue(elem <= data[ip])\r
- if func is self.module.bisect_left and ip > lo:\r
- self.assertTrue(data[ip-1] < elem)\r
- if func is self.module.bisect_right and ip < hi:\r
- self.assertTrue(elem < data[ip])\r
- if func is self.module.bisect_right and ip > lo:\r
- self.assertTrue(data[ip-1] <= elem)\r
- self.assertEqual(ip, max(lo, min(hi, expected)))\r
-\r
- def test_backcompatibility(self):\r
- self.assertEqual(self.module.bisect, self.module.bisect_right)\r
-\r
- def test_keyword_args(self):\r
- data = [10, 20, 30, 40, 50]\r
- self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2)\r
- self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2)\r
- self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2)\r
- self.module.insort_left(a=data, x=25, lo=1, hi=3)\r
- self.module.insort_right(a=data, x=25, lo=1, hi=3)\r
- self.module.insort(a=data, x=25, lo=1, hi=3)\r
- self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])\r
-\r
-class TestBisectPython(TestBisect):\r
- module = py_bisect\r
-\r
-class TestBisectC(TestBisect):\r
- module = c_bisect\r
-\r
-#==============================================================================\r
-\r
-class TestInsort(unittest.TestCase):\r
- module = None\r
-\r
- def test_vsBuiltinSort(self, n=500):\r
- from random import choice\r
- for insorted in (list(), UserList()):\r
- for i in xrange(n):\r
- digit = choice("0123456789")\r
- if digit in "02468":\r
- f = self.module.insort_left\r
- else:\r
- f = self.module.insort_right\r
- f(insorted, digit)\r
- self.assertEqual(sorted(insorted), insorted)\r
-\r
- def test_backcompatibility(self):\r
- self.assertEqual(self.module.insort, self.module.insort_right)\r
-\r
- def test_listDerived(self):\r
- class List(list):\r
- data = []\r
- def insert(self, index, item):\r
- self.data.insert(index, item)\r
-\r
- lst = List()\r
- self.module.insort_left(lst, 10)\r
- self.module.insort_right(lst, 5)\r
- self.assertEqual([5, 10], lst.data)\r
-\r
-class TestInsortPython(TestInsort):\r
- module = py_bisect\r
-\r
-class TestInsortC(TestInsort):\r
- module = c_bisect\r
-\r
-#==============================================================================\r
-\r
-\r
-class LenOnly:\r
- "Dummy sequence class defining __len__ but not __getitem__."\r
- def __len__(self):\r
- return 10\r
-\r
-class GetOnly:\r
- "Dummy sequence class defining __getitem__ but not __len__."\r
- def __getitem__(self, ndx):\r
- return 10\r
-\r
-class CmpErr:\r
- "Dummy element that always raises an error during comparison"\r
- def __cmp__(self, other):\r
- raise ZeroDivisionError\r
-\r
-class TestErrorHandling(unittest.TestCase):\r
- module = None\r
-\r
- def test_non_sequence(self):\r
- for f in (self.module.bisect_left, self.module.bisect_right,\r
- self.module.insort_left, self.module.insort_right):\r
- self.assertRaises(TypeError, f, 10, 10)\r
-\r
- def test_len_only(self):\r
- for f in (self.module.bisect_left, self.module.bisect_right,\r
- self.module.insort_left, self.module.insort_right):\r
- self.assertRaises(AttributeError, f, LenOnly(), 10)\r
-\r
- def test_get_only(self):\r
- for f in (self.module.bisect_left, self.module.bisect_right,\r
- self.module.insort_left, self.module.insort_right):\r
- self.assertRaises(AttributeError, f, GetOnly(), 10)\r
-\r
- def test_cmp_err(self):\r
- seq = [CmpErr(), CmpErr(), CmpErr()]\r
- for f in (self.module.bisect_left, self.module.bisect_right,\r
- self.module.insort_left, self.module.insort_right):\r
- self.assertRaises(ZeroDivisionError, f, seq, 10)\r
-\r
- def test_arg_parsing(self):\r
- for f in (self.module.bisect_left, self.module.bisect_right,\r
- self.module.insort_left, self.module.insort_right):\r
- self.assertRaises(TypeError, f, 10)\r
-\r
-class TestErrorHandlingPython(TestErrorHandling):\r
- module = py_bisect\r
-\r
-class TestErrorHandlingC(TestErrorHandling):\r
- module = c_bisect\r
-\r
-#==============================================================================\r
-\r
-libreftest = """\r
-Example from the Library Reference: Doc/library/bisect.rst\r
-\r
-The bisect() function is generally useful for categorizing numeric data.\r
-This example uses bisect() to look up a letter grade for an exam total\r
-(say) based on a set of ordered numeric breakpoints: 85 and up is an `A',\r
-75..84 is a `B', etc.\r
-\r
- >>> grades = "FEDCBA"\r
- >>> breakpoints = [30, 44, 66, 75, 85]\r
- >>> from bisect import bisect\r
- >>> def grade(total):\r
- ... return grades[bisect(breakpoints, total)]\r
- ...\r
- >>> grade(66)\r
- 'C'\r
- >>> map(grade, [33, 99, 77, 44, 12, 88])\r
- ['E', 'A', 'B', 'D', 'F', 'A']\r
-\r
-"""\r
-\r
-#------------------------------------------------------------------------------\r
-\r
-__test__ = {'libreftest' : libreftest}\r
-\r
-def test_main(verbose=None):\r
- from test import test_bisect\r
-\r
- test_classes = [TestBisectPython, TestBisectC,\r
- TestInsortPython, TestInsortC,\r
- TestErrorHandlingPython, TestErrorHandlingC]\r
-\r
- test_support.run_unittest(*test_classes)\r
- test_support.run_doctest(test_bisect, verbose)\r
-\r
- # verify reference counting\r
- if verbose and hasattr(sys, "gettotalrefcount"):\r
- import gc\r
- counts = [None] * 5\r
- for i in xrange(len(counts)):\r
- test_support.run_unittest(*test_classes)\r
- gc.collect()\r
- counts[i] = sys.gettotalrefcount()\r
- print counts\r
-\r
-if __name__ == "__main__":\r
- test_main(verbose=True)\r