14710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport sys 24710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport unittest 34710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfrom test import test_support 44710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfrom UserList import UserList 54710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 64710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# We do a bit of trickery here to be able to test both the C implementation 74710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# and the Python implementation of the module. 84710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 94710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# Make it impossible to import the C implementation anymore. 104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmsys.modules['_bisect'] = 0 114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# We must also handle the case that bisect was imported before. 124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmif 'bisect' in sys.modules: 134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm del sys.modules['bisect'] 144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# Now we can import the module and get the pure Python implementation. 164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport bisect as py_bisect 174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# Restore everything to normal. 194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdel sys.modules['_bisect'] 204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdel sys.modules['bisect'] 214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# This is now the module with the C implementation. 234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport bisect as c_bisect 244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass TestBisect(unittest.TestCase): 274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm module = None 284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def setUp(self): 304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.precomputedCases = [ 314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [], 1, 0), 324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1], 0, 0), 334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1], 1, 1), 344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1], 2, 1), 354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1], 0, 0), 364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1], 1, 2), 374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1], 2, 2), 384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1, 1], 0, 0), 394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1, 1], 1, 3), 404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1, 1], 2, 3), 414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1, 1, 1], 0, 0), 424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1, 1, 1], 1, 4), 434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1, 1, 1], 2, 4), 444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2], 0, 0), 454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2], 1, 1), 464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2], 1.5, 1), 474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2], 2, 2), 484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2], 3, 2), 494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1, 2, 2], 0, 0), 504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1, 2, 2], 1, 2), 514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2), 524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1, 2, 2], 2, 4), 534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 1, 2, 2], 3, 4), 544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 3], 0, 0), 554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 3], 1, 1), 564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 3], 1.5, 1), 574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 3], 2, 2), 584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 3], 2.5, 2), 594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 3], 3, 3), 604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 3], 4, 3), 614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0), 624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1), 634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1), 644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3), 654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3), 664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6), 674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6), 684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10), 694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10), 704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [], 1, 0), 724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1], 0, 0), 734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1], 1, 0), 744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1], 2, 1), 754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1], 0, 0), 764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1], 1, 0), 774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1], 2, 2), 784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1, 1], 0, 0), 794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1, 1], 1, 0), 804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1, 1], 2, 3), 814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1, 1, 1], 0, 0), 824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1, 1, 1], 1, 0), 834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1, 1, 1], 2, 4), 844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2], 0, 0), 854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2], 1, 0), 864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2], 1.5, 1), 874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2], 2, 1), 884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2], 3, 2), 894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1, 2, 2], 0, 0), 904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1, 2, 2], 1, 0), 914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2), 924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1, 2, 2], 2, 2), 934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 1, 2, 2], 3, 4), 944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 3], 0, 0), 954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 3], 1, 0), 964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 3], 1.5, 1), 974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 3], 2, 1), 984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 3], 2.5, 2), 994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 3], 3, 2), 1004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 3], 4, 3), 1014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0), 1024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0), 1034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1), 1044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1), 1054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3), 1064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3), 1074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6), 1084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6), 1094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10) 1104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ] 1114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_precomputed(self): 1134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for func, data, elem, expected in self.precomputedCases: 1144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertEqual(func(data, elem), expected) 1154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertEqual(func(UserList(data), elem), expected) 1164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_negative_lo(self): 1184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Issue 3301 1194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm mod = self.module 1204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertRaises(ValueError, mod.bisect_left, [1, 2, 3], 5, -1, 3), 1214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertRaises(ValueError, mod.bisect_right, [1, 2, 3], 5, -1, 3), 1224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3), 1234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3), 1244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_random(self, n=25): 1264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm from random import randrange 1274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for i in xrange(n): 1284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm data = [randrange(0, n, 2) for j in xrange(i)] 1294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm data.sort() 1304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elem = randrange(-1, n+1) 1314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ip = self.module.bisect_left(data, elem) 1324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if ip < len(data): 1334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertTrue(elem <= data[ip]) 1344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if ip > 0: 1354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertTrue(data[ip-1] < elem) 1364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ip = self.module.bisect_right(data, elem) 1374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if ip < len(data): 1384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertTrue(elem < data[ip]) 1394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if ip > 0: 1404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertTrue(data[ip-1] <= elem) 1414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_optionalSlicing(self): 1434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for func, data, elem, expected in self.precomputedCases: 1444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for lo in xrange(4): 1454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm lo = min(len(data), lo) 1464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for hi in xrange(3,8): 1474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm hi = min(len(data), hi) 1484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ip = func(data, elem, lo, hi) 1494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertTrue(lo <= ip <= hi) 1504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if func is self.module.bisect_left and ip < hi: 1514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertTrue(elem <= data[ip]) 1524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if func is self.module.bisect_left and ip > lo: 1534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertTrue(data[ip-1] < elem) 1544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if func is self.module.bisect_right and ip < hi: 1554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertTrue(elem < data[ip]) 1564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if func is self.module.bisect_right and ip > lo: 1574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertTrue(data[ip-1] <= elem) 1584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertEqual(ip, max(lo, min(hi, expected))) 1594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_backcompatibility(self): 1614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertEqual(self.module.bisect, self.module.bisect_right) 1624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_keyword_args(self): 1644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm data = [10, 20, 30, 40, 50] 1654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2) 1664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2) 1674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2) 1684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.module.insort_left(a=data, x=25, lo=1, hi=3) 1694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.module.insort_right(a=data, x=25, lo=1, hi=3) 1704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.module.insort(a=data, x=25, lo=1, hi=3) 1714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50]) 1724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass TestBisectPython(TestBisect): 1744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm module = py_bisect 1754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass TestBisectC(TestBisect): 1774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm module = c_bisect 1784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#============================================================================== 1804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass TestInsort(unittest.TestCase): 1824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm module = None 1834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_vsBuiltinSort(self, n=500): 1854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm from random import choice 1864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for insorted in (list(), UserList()): 1874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for i in xrange(n): 1884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm digit = choice("0123456789") 1894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if digit in "02468": 1904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm f = self.module.insort_left 1914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 1924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm f = self.module.insort_right 1934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm f(insorted, digit) 1944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertEqual(sorted(insorted), insorted) 1954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_backcompatibility(self): 1974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertEqual(self.module.insort, self.module.insort_right) 1984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_listDerived(self): 2004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm class List(list): 2014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm data = [] 2024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def insert(self, index, item): 2034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.data.insert(index, item) 2044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm lst = List() 2064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.module.insort_left(lst, 10) 2074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.module.insort_right(lst, 5) 2084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertEqual([5, 10], lst.data) 2094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass TestInsortPython(TestInsort): 2114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm module = py_bisect 2124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass TestInsortC(TestInsort): 2144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm module = c_bisect 2154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#============================================================================== 2174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass LenOnly: 2204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "Dummy sequence class defining __len__ but not __getitem__." 2214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __len__(self): 2224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 10 2234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass GetOnly: 2254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "Dummy sequence class defining __getitem__ but not __len__." 2264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __getitem__(self, ndx): 2274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 10 2284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass CmpErr: 2304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "Dummy element that always raises an error during comparison" 2314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __cmp__(self, other): 2324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise ZeroDivisionError 2334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass TestErrorHandling(unittest.TestCase): 2354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm module = None 2364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_non_sequence(self): 2384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for f in (self.module.bisect_left, self.module.bisect_right, 2394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.module.insort_left, self.module.insort_right): 2404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertRaises(TypeError, f, 10, 10) 2414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_len_only(self): 2434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for f in (self.module.bisect_left, self.module.bisect_right, 2444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.module.insort_left, self.module.insort_right): 2454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertRaises(AttributeError, f, LenOnly(), 10) 2464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_get_only(self): 2484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for f in (self.module.bisect_left, self.module.bisect_right, 2494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.module.insort_left, self.module.insort_right): 2504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertRaises(AttributeError, f, GetOnly(), 10) 2514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_cmp_err(self): 2534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm seq = [CmpErr(), CmpErr(), CmpErr()] 2544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for f in (self.module.bisect_left, self.module.bisect_right, 2554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.module.insort_left, self.module.insort_right): 2564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertRaises(ZeroDivisionError, f, seq, 10) 2574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def test_arg_parsing(self): 2594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for f in (self.module.bisect_left, self.module.bisect_right, 2604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.module.insort_left, self.module.insort_right): 2614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.assertRaises(TypeError, f, 10) 2624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass TestErrorHandlingPython(TestErrorHandling): 2644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm module = py_bisect 2654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass TestErrorHandlingC(TestErrorHandling): 2674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm module = c_bisect 2684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#============================================================================== 2704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmlibreftest = """ 2724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmExample from the Library Reference: Doc/library/bisect.rst 2734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmThe bisect() function is generally useful for categorizing numeric data. 2754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmThis example uses bisect() to look up a letter grade for an exam total 2764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm(say) based on a set of ordered numeric breakpoints: 85 and up is an `A', 2774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm75..84 is a `B', etc. 2784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> grades = "FEDCBA" 2804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> breakpoints = [30, 44, 66, 75, 85] 2814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> from bisect import bisect 2824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> def grade(total): 2834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ... return grades[bisect(breakpoints, total)] 2844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ... 2854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> grade(66) 2864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'C' 2874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> map(grade, [33, 99, 77, 44, 12, 88]) 2884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ['E', 'A', 'B', 'D', 'F', 'A'] 2894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm""" 2914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#------------------------------------------------------------------------------ 2934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm__test__ = {'libreftest' : libreftest} 2954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef test_main(verbose=None): 2974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm from test import test_bisect 2984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm test_classes = [TestBisectPython, TestBisectC, 3004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm TestInsortPython, TestInsortC, 3014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm TestErrorHandlingPython, TestErrorHandlingC] 3024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm test_support.run_unittest(*test_classes) 3044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm test_support.run_doctest(test_bisect, verbose) 3054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # verify reference counting 3074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if verbose and hasattr(sys, "gettotalrefcount"): 3084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm import gc 3094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm counts = [None] * 5 3104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for i in xrange(len(counts)): 3114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm test_support.run_unittest(*test_classes) 3124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm gc.collect() 3134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm counts[i] = sys.gettotalrefcount() 3144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm print counts 3154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmif __name__ == "__main__": 3174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm test_main(verbose=True) 318