14adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaofrom collections import deque 24adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoimport unittest 34adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaofrom test import test_support, seq_tests 44adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoimport gc 54adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoimport weakref 64adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoimport copy 74adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoimport cPickle as pickle 84adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoimport random 94adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoimport struct 104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 114adfde8bc82dd39f59e0445588c3e599ada477dJosh GaoBIG = 100000 124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaodef fail(): 144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise SyntaxError 154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao yield 1 164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoclass BadCmp: 184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __eq__(self, other): 194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise RuntimeError 204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoclass MutateCmp: 224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __init__(self, deque, result): 234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.deque = deque 244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.result = result 254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __eq__(self, other): 264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.deque.clear() 274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return self.result 284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoclass TestBasic(unittest.TestCase): 304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_basics(self): 324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(xrange(-5125, -5000)) 334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.__init__(xrange(200)) 344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(200, 400): 354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.append(i) 364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in reversed(xrange(-200, 0)): 374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.appendleft(i) 384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), range(-200, 400)) 394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 600) 404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao left = [d.popleft() for i in xrange(250)] 424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(left, range(-200, 50)) 434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), range(50, 400)) 444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao right = [d.pop() for i in xrange(250)] 464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao right.reverse() 474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(right, range(150, 400)) 484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), range(50, 150)) 494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_maxlen(self): 514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(ValueError, deque, 'abc', -1) 524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(ValueError, deque, 'abc', -2) 534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao it = iter(range(10)) 544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(it, maxlen=3) 554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(it), []) 564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(repr(d), 'deque([7, 8, 9], maxlen=3)') 574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), range(7, 10)) 584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(d, deque(range(10), 3)) 594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.append(10) 604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), range(8, 11)) 614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.appendleft(7) 624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), range(7, 10)) 634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.extend([10, 11]) 644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), range(9, 12)) 654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.extendleft([8, 7]) 664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), range(7, 10)) 674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(xrange(200), maxlen=10) 684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.append(d) 694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao test_support.unlink(test_support.TESTFN) 704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao fo = open(test_support.TESTFN, "wb") 714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao try: 724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao print >> fo, d, 734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao fo.close() 744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao fo = open(test_support.TESTFN, "rb") 754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(fo.read(), repr(d)) 764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao finally: 774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao fo.close() 784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao test_support.unlink(test_support.TESTFN) 794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(range(10), maxlen=None) 814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(repr(d), 'deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])') 824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao fo = open(test_support.TESTFN, "wb") 834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao try: 844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao print >> fo, d, 854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao fo.close() 864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao fo = open(test_support.TESTFN, "rb") 874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(fo.read(), repr(d)) 884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao finally: 894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao fo.close() 904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao test_support.unlink(test_support.TESTFN) 914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_maxlen_zero(self): 934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao it = iter(range(100)) 944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao deque(it, maxlen=0) 954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(it), []) 964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao it = iter(range(100)) 984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(maxlen=0) 994adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.extend(it) 1004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(it), []) 1014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao it = iter(range(100)) 1034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(maxlen=0) 1044adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.extendleft(it) 1054adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(it), []) 1064adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1074adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_maxlen_attribute(self): 1084adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(deque().maxlen, None) 1094adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(deque('abc').maxlen, None) 1104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(deque('abc', maxlen=4).maxlen, 4) 1114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(deque('abc', maxlen=2).maxlen, 2) 1124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(deque('abc', maxlen=0).maxlen, 0) 1134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao with self.assertRaises(AttributeError): 1144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque('abc') 1154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.maxlen = 10 1164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_count(self): 1184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for s in ('', 'abracadabra', 'simsalabim'*500+'abc'): 1194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao s = list(s) 1204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(s) 1214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for letter in 'abcdefghijklmnopqrstuvwxyz': 1224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(s.count(letter), d.count(letter), (s, d, letter)) 1234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(TypeError, d.count) # too few args 1244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(TypeError, d.count, 1, 2) # too many args 1254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao class BadCompare: 1264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __eq__(self, other): 1274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise ArithmeticError 1284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque([1, 2, BadCompare(), 3]) 1294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(ArithmeticError, d.count, 2) 1304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque([1, 2, 3]) 1314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(ArithmeticError, d.count, BadCompare()) 1324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao class MutatingCompare: 1334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __eq__(self, other): 1344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.d.pop() 1354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return True 1364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao m = MutatingCompare() 1374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque([1, 2, 3, m, 4, 5]) 1384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao m.d = d 1394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(RuntimeError, d.count, 3) 1404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # test issue11004 1424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # block advance failed after rotation aligned elements on right side of block 1434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque([None]*16) 1444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in range(len(d)): 1454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.rotate(-1) 1464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.rotate(1) 1474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(d.count(1), 0) 1484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(d.count(None), 16) 1494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_comparisons(self): 1514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque('xabc'); d.popleft() 1524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for e in [d, deque('abc'), deque('ab'), deque(), list(d)]: 1534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(d==e, type(d)==type(e) and list(d)==list(e)) 1544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(d!=e, not(type(d)==type(e) and list(d)==list(e))) 1554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao args = map(deque, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba')) 1574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for x in args: 1584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for y in args: 1594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(x == y, list(x) == list(y), (x,y)) 1604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(x != y, list(x) != list(y), (x,y)) 1614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(x < y, list(x) < list(y), (x,y)) 1624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(x <= y, list(x) <= list(y), (x,y)) 1634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(x > y, list(x) > list(y), (x,y)) 1644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(x >= y, list(x) >= list(y), (x,y)) 1654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(cmp(x,y), cmp(list(x),list(y)), (x,y)) 1664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_extend(self): 1684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque('a') 1694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(TypeError, d.extend, 1) 1704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.extend('bcd') 1714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list('abcd')) 1724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.extend(d) 1734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list('abcdabcd')) 1744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_iadd(self): 1764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque('a') 1774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d += 'bcd' 1784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list('abcd')) 1794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d += d 1804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list('abcdabcd')) 1814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_extendleft(self): 1834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque('a') 1844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(TypeError, d.extendleft, 1) 1854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.extendleft('bcd') 1864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(reversed('abcd'))) 1874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.extendleft(d) 1884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list('abcddcba')) 1894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque() 1904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.extendleft(range(1000)) 1914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(reversed(range(1000)))) 1924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(SyntaxError, d.extendleft, fail()) 1934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_getitem(self): 1954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao n = 200 1964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(xrange(n)) 1974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao l = range(n) 1984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(n): 1994adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.popleft() 2004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao l.pop(0) 2014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if random.random() < 0.5: 2024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.append(i) 2034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao l.append(i) 2044adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for j in xrange(1-len(l), len(l)): 2054adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao assert d[j] == l[j] 2064adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2074adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque('superman') 2084adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(d[0], 's') 2094adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(d[-1], 'n') 2104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque() 2114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(IndexError, d.__getitem__, 0) 2124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(IndexError, d.__getitem__, -1) 2134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_setitem(self): 2154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao n = 200 2164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(xrange(n)) 2174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(n): 2184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d[i] = 10 * i 2194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), [10*i for i in xrange(n)]) 2204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao l = list(d) 2214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(1-n, 0, -1): 2224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d[i] = 7*i 2234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao l[i] = 7*i 2244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), l) 2254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_delitem(self): 2274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao n = 500 # O(n**2) test, don't make this too big 2284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(xrange(n)) 2294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(IndexError, d.__delitem__, -n-1) 2304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(IndexError, d.__delitem__, n) 2314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(n): 2324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), n-i) 2334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao j = random.randrange(-len(d), len(d)) 2344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao val = d[j] 2354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertIn(val, d) 2364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao del d[j] 2374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertNotIn(val, d) 2384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 0) 2394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_reverse(self): 2414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao n = 500 # O(n**2) test, don't make this too big 2424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao data = [random.random() for i in range(n)] 2434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in range(n): 2444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(data[:i]) 2454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao r = d.reverse() 2464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(reversed(data[:i]))) 2474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertIs(r, None) 2484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.reverse() 2494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), data[:i]) 2504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(TypeError, d.reverse, 1) # Arity is zero 2514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_rotate(self): 2534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao s = tuple('abcde') 2544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao n = len(s) 2554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(s) 2574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.rotate(1) # verify rot(1) 2584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(''.join(d), 'eabcd') 2594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(s) 2614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.rotate(-1) # verify rot(-1) 2624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(''.join(d), 'bcdea') 2634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.rotate() # check default to 1 2644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(tuple(d), s) 2654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(n*3): 2674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(s) 2684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = deque(d) 2694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.rotate(i) # check vs. rot(1) n times 2704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for j in xrange(i): 2714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e.rotate(1) 2724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(tuple(d), tuple(e)) 2734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.rotate(-i) # check that it works in reverse 2744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(tuple(d), s) 2754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e.rotate(n-i) # check that it wraps forward 2764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(tuple(e), s) 2774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(n*3): 2794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(s) 2804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = deque(d) 2814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.rotate(-i) 2824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for j in xrange(i): 2834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e.rotate(-1) # check vs. rot(-1) n times 2844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(tuple(d), tuple(e)) 2854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.rotate(i) # check that it works in reverse 2864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(tuple(d), s) 2874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e.rotate(i-n) # check that it wraps backaround 2884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(tuple(e), s) 2894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(s) 2914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = deque(s) 2924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e.rotate(BIG+17) # verify on long series of rotates 2934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao dr = d.rotate 2944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(BIG+17): 2954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao dr() 2964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(tuple(d), tuple(e)) 2974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(TypeError, d.rotate, 'x') # Wrong arg type 2994adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args 3004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque() 3024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.rotate() # rotate an empty deque 3034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(d, deque()) 3044adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3054adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_len(self): 3064adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque('ab') 3074adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 2) 3084adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.popleft() 3094adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 1) 3104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.pop() 3114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 0) 3124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(IndexError, d.pop) 3134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 0) 3144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.append('c') 3154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 1) 3164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.appendleft('d') 3174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 2) 3184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.clear() 3194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 0) 3204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_underflow(self): 3224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque() 3234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(IndexError, d.pop) 3244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(IndexError, d.popleft) 3254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_clear(self): 3274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(xrange(100)) 3284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 100) 3294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.clear() 3304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 0) 3314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), []) 3324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.clear() # clear an emtpy deque 3334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), []) 3344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_remove(self): 3364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque('abcdefghcij') 3374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.remove('c') 3384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(d, deque('abdefghcij')) 3394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.remove('c') 3404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(d, deque('abdefghij')) 3414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(ValueError, d.remove, 'c') 3424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(d, deque('abdefghij')) 3434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Handle comparison errors 3454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(['a', 'b', BadCmp(), 'c']) 3464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = deque(d) 3474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(RuntimeError, d.remove, 'c') 3484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for x, y in zip(d, e): 3494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # verify that original order and values are retained. 3504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertTrue(x is y) 3514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Handle evil mutator 3534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for match in (True, False): 3544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(['ab']) 3554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.extend([MutateCmp(d, match), 'c']) 3564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(IndexError, d.remove, 'c') 3574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(d, deque()) 3584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_repr(self): 3604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(xrange(200)) 3614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = eval(repr(d)) 3624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(e)) 3634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.append(d) 3644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertIn('...', repr(d)) 3654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_print(self): 3674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(xrange(200)) 3684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.append(d) 3694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao test_support.unlink(test_support.TESTFN) 3704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao fo = open(test_support.TESTFN, "wb") 3714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao try: 3724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao print >> fo, d, 3734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao fo.close() 3744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao fo = open(test_support.TESTFN, "rb") 3754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(fo.read(), repr(d)) 3764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao finally: 3774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao fo.close() 3784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao test_support.unlink(test_support.TESTFN) 3794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_init(self): 3814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(TypeError, deque, 'abc', 2, 3); 3824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(TypeError, deque, 1); 3834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_hash(self): 3854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(TypeError, hash, deque('abc')) 3864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_long_steadystate_queue_popleft(self): 3884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for size in (0, 1, 2, 100, 1000): 3894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(xrange(size)) 3904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao append, pop = d.append, d.popleft 3914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(size, BIG): 3924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao append(i) 3934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao x = pop() 3944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if x != i - size: 3954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(x, i-size) 3964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), range(BIG-size, BIG)) 3974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_long_steadystate_queue_popright(self): 3994adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for size in (0, 1, 2, 100, 1000): 4004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(reversed(xrange(size))) 4014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao append, pop = d.appendleft, d.pop 4024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(size, BIG): 4034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao append(i) 4044adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao x = pop() 4054adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if x != i - size: 4064adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(x, i-size) 4074adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(reversed(list(d))), range(BIG-size, BIG)) 4084adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4094adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_big_queue_popleft(self): 4104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao pass 4114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque() 4124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao append, pop = d.append, d.popleft 4134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(BIG): 4144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao append(i) 4154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(BIG): 4164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao x = pop() 4174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if x != i: 4184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(x, i) 4194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_big_queue_popright(self): 4214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque() 4224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao append, pop = d.appendleft, d.pop 4234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(BIG): 4244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao append(i) 4254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(BIG): 4264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao x = pop() 4274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if x != i: 4284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(x, i) 4294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_big_stack_right(self): 4314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque() 4324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao append, pop = d.append, d.pop 4334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(BIG): 4344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao append(i) 4354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in reversed(xrange(BIG)): 4364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao x = pop() 4374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if x != i: 4384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(x, i) 4394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 0) 4404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_big_stack_left(self): 4424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque() 4434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao append, pop = d.appendleft, d.popleft 4444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(BIG): 4454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao append(i) 4464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in reversed(xrange(BIG)): 4474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao x = pop() 4484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if x != i: 4494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(x, i) 4504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 0) 4514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_roundtrip_iter_init(self): 4534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(xrange(200)) 4544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = deque(d) 4554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertNotEqual(id(d), id(e)) 4564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(e)) 4574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_pickle(self): 4594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque(xrange(200)) 4604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in range(pickle.HIGHEST_PROTOCOL + 1): 4614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao s = pickle.dumps(d, i) 4624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = pickle.loads(s) 4634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertNotEqual(id(d), id(e)) 4644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(e)) 4654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## def test_pickle_recursive(self): 4674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## d = deque('abc') 4684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## d.append(d) 4694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## for i in range(pickle.HIGHEST_PROTOCOL + 1): 4704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## e = pickle.loads(pickle.dumps(d, i)) 4714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## self.assertNotEqual(id(d), id(e)) 4724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## self.assertEqual(id(e), id(e[-1])) 4734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_deepcopy(self): 4754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao mut = [10] 4764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque([mut]) 4774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = copy.deepcopy(d) 4784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(e)) 4794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao mut[0] = 11 4804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertNotEqual(id(d), id(e)) 4814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertNotEqual(list(d), list(e)) 4824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_copy(self): 4844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao mut = [10] 4854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque([mut]) 4864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = copy.copy(d) 4874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(e)) 4884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao mut[0] = 11 4894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertNotEqual(id(d), id(e)) 4904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(e)) 4914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_reversed(self): 4934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for s in ('abcd', xrange(2000)): 4944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(reversed(deque(s))), list(reversed(s))) 4954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_gc_doesnt_blowup(self): 4974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao import gc 4984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # This used to assert-fail in deque_traverse() under a debug 4994adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # build, or run wild with a NULL pointer in a release build. 5004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque() 5014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(100): 5024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.append(1) 5034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao gc.collect() 5044adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5054adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_container_iterator(self): 5064adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Bug #3680: tp_traverse was not implemented for deque iterator objects 5074adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao class C(object): 5084adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao pass 5094adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in range(2): 5104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao obj = C() 5114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ref = weakref.ref(obj) 5124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if i == 0: 5134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao container = deque([obj, 1]) 5144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao else: 5154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao container = reversed(deque([obj, 1])) 5164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao obj.x = iter(container) 5174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao del obj, container 5184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao gc.collect() 5194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertTrue(ref() is None, "Cycle was not collected") 5204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao check_sizeof = test_support.check_sizeof 5224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao @test_support.cpython_only 5244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_sizeof(self): 5254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao BLOCKLEN = 62 5264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao basesize = test_support.calcobjsize('2P4PlP') 5274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao blocksize = struct.calcsize('2P%dP' % BLOCKLEN) 5284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(object.__sizeof__(deque()), basesize) 5294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao check = self.check_sizeof 5304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao check(deque(), basesize + blocksize) 5314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao check(deque('a'), basesize + blocksize) 5324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao check(deque('a' * (BLOCKLEN // 2)), basesize + blocksize) 5334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao check(deque('a' * (BLOCKLEN // 2 + 1)), basesize + 2 * blocksize) 5344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao check(deque('a' * (42 * BLOCKLEN)), basesize + 43 * blocksize) 5354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoclass TestVariousIteratorArgs(unittest.TestCase): 5374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_constructor(self): 5394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)): 5404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for g in (seq_tests.Sequence, seq_tests.IterFunc, 5414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao seq_tests.IterGen, seq_tests.IterFuncStop, 5424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao seq_tests.itermulti, seq_tests.iterfunc): 5434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(deque(g(s))), list(g(s))) 5444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(TypeError, deque, seq_tests.IterNextOnly(s)) 5454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(TypeError, deque, seq_tests.IterNoNext(s)) 5464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(ZeroDivisionError, deque, seq_tests.IterGenExc(s)) 5474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_iter_with_altered_data(self): 5494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque('abcdefg') 5504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao it = iter(d) 5514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.pop() 5524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(RuntimeError, it.next) 5534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_runtime_error_on_empty_deque(self): 5554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque() 5564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao it = iter(d) 5574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.append(10) 5584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(RuntimeError, it.next) 5594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoclass Deque(deque): 5614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao pass 5624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoclass DequeWithBadIter(deque): 5644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __iter__(self): 5654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise TypeError 5664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoclass TestSubclass(unittest.TestCase): 5684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_basics(self): 5704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = Deque(xrange(25)) 5714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.__init__(xrange(200)) 5724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(200, 400): 5734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.append(i) 5744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in reversed(xrange(-200, 0)): 5754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.appendleft(i) 5764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), range(-200, 400)) 5774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 600) 5784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao left = [d.popleft() for i in xrange(250)] 5804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(left, range(-200, 50)) 5814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), range(50, 400)) 5824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao right = [d.pop() for i in xrange(250)] 5844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao right.reverse() 5854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(right, range(150, 400)) 5864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), range(50, 150)) 5874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.clear() 5894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(len(d), 0) 5904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_copy_pickle(self): 5924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = Deque('abc') 5944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = d.__copy__() 5964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(type(d), type(e)) 5974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(e)) 5984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5994adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = Deque(d) 6004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(type(d), type(e)) 6014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(e)) 6024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao s = pickle.dumps(d) 6044adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = pickle.loads(s) 6054adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertNotEqual(id(d), id(e)) 6064adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(type(d), type(e)) 6074adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(e)) 6084adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6094adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = Deque('abcde', maxlen=4) 6104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = d.__copy__() 6124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(type(d), type(e)) 6134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(e)) 6144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = Deque(d) 6164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(type(d), type(e)) 6174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(e)) 6184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao s = pickle.dumps(d) 6204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao e = pickle.loads(s) 6214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertNotEqual(id(d), id(e)) 6224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(type(d), type(e)) 6234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(list(d), list(e)) 6244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## def test_pickle(self): 6264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## d = Deque('abc') 6274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## d.append(d) 6284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## 6294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## e = pickle.loads(pickle.dumps(d)) 6304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## self.assertNotEqual(id(d), id(e)) 6314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## self.assertEqual(type(d), type(e)) 6324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## dd = d.pop() 6334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## ee = e.pop() 6344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## self.assertEqual(id(e), id(ee)) 6354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## self.assertEqual(d, e) 6364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## 6374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## d.x = d 6384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## e = pickle.loads(pickle.dumps(d)) 6394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## self.assertEqual(id(e), id(e.x)) 6404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## 6414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## d = DequeWithBadIter('abc') 6424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao## self.assertRaises(TypeError, pickle.dumps, d) 6434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_weakref(self): 6454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = deque('gallahad') 6464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao p = weakref.proxy(d) 6474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertEqual(str(p), str(d)) 6484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d = None 6494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.assertRaises(ReferenceError, str, p) 6504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_strange_subclass(self): 6524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao class X(deque): 6534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __iter__(self): 6544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return iter([]) 6554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d1 = X([1,2,3]) 6564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d2 = X([4,5,6]) 6574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d1 == d2 # not clear if this is supposed to be True or False, 6584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # but it used to give a SystemError 6594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoclass SubclassWithKwargs(deque): 6624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __init__(self, newarg=1): 6634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao deque.__init__(self) 6644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoclass TestSubclassWithKwargs(unittest.TestCase): 6664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def test_subclass_with_kwargs(self): 6674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # SF bug #1486663 -- this used to erroneously raise a TypeError 6684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao SubclassWithKwargs(newarg=1) 6694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao#============================================================================== 6714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaolibreftest = """ 6734adfde8bc82dd39f59e0445588c3e599ada477dJosh GaoExample from the Library Reference: Doc/lib/libcollections.tex 6744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> from collections import deque 6764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d = deque('ghi') # make a new deque with three items 6774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> for elem in d: # iterate over the deque's elements 6784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... print elem.upper() 6794adfde8bc82dd39f59e0445588c3e599ada477dJosh GaoG 6804adfde8bc82dd39f59e0445588c3e599ada477dJosh GaoH 6814adfde8bc82dd39f59e0445588c3e599ada477dJosh GaoI 6824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d.append('j') # add a new entry to the right side 6834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d.appendleft('f') # add a new entry to the left side 6844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d # show the representation of the deque 6854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaodeque(['f', 'g', 'h', 'i', 'j']) 6864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d.pop() # return and remove the rightmost item 6874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao'j' 6884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d.popleft() # return and remove the leftmost item 6894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao'f' 6904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> list(d) # list the contents of the deque 6914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao['g', 'h', 'i'] 6924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d[0] # peek at leftmost item 6934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao'g' 6944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d[-1] # peek at rightmost item 6954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao'i' 6964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> list(reversed(d)) # list the contents of a deque in reverse 6974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao['i', 'h', 'g'] 6984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> 'h' in d # search the deque 6994adfde8bc82dd39f59e0445588c3e599ada477dJosh GaoTrue 7004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d.extend('jkl') # add multiple elements at once 7014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d 7024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaodeque(['g', 'h', 'i', 'j', 'k', 'l']) 7034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d.rotate(1) # right rotation 7044adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d 7054adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaodeque(['l', 'g', 'h', 'i', 'j', 'k']) 7064adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d.rotate(-1) # left rotation 7074adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d 7084adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaodeque(['g', 'h', 'i', 'j', 'k', 'l']) 7094adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> deque(reversed(d)) # make a new deque in reverse order 7104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaodeque(['l', 'k', 'j', 'i', 'h', 'g']) 7114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d.clear() # empty the deque 7124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d.pop() # cannot pop from an empty deque 7134adfde8bc82dd39f59e0445588c3e599ada477dJosh GaoTraceback (most recent call last): 7144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao File "<pyshell#6>", line 1, in -toplevel- 7154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao d.pop() 7164adfde8bc82dd39f59e0445588c3e599ada477dJosh GaoIndexError: pop from an empty deque 7174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d.extendleft('abc') # extendleft() reverses the input order 7194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d 7204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaodeque(['c', 'b', 'a']) 7214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> def delete_nth(d, n): 7254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... d.rotate(-n) 7264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... d.popleft() 7274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... d.rotate(n) 7284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... 7294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d = deque('abcdef') 7304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> delete_nth(d, 2) # remove the entry at d[2] 7314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> d 7324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaodeque(['a', 'b', 'd', 'e', 'f']) 7334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> def roundrobin(*iterables): 7374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... pending = deque(iter(i) for i in iterables) 7384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... while pending: 7394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... task = pending.popleft() 7404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... try: 7414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... yield task.next() 7424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... except StopIteration: 7434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... continue 7444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... pending.append(task) 7454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... 7464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> for value in roundrobin('abc', 'd', 'efgh'): 7484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... print value 7494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... 7504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoa 7514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaod 7524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoe 7534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaob 7544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaof 7554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoc 7564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaog 7574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoh 7584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> def maketree(iterable): 7614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... d = deque(iterable) 7624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... while len(d) > 1: 7634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... pair = [d.popleft(), d.popleft()] 7644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... d.append(pair) 7654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... return list(d) 7664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao... 7674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao>>> print maketree('abcdefgh') 7684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao[[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]] 7694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao""" 7714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao#============================================================================== 7744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao__test__ = {'libreftest' : libreftest} 7764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaodef test_main(verbose=None): 7784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao import sys 7794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao test_classes = ( 7804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao TestBasic, 7814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao TestVariousIteratorArgs, 7824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao TestSubclass, 7834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao TestSubclassWithKwargs, 7844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ) 7854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao test_support.run_unittest(*test_classes) 7874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # verify reference counting 7894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if verbose and hasattr(sys, "gettotalrefcount"): 7904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao import gc 7914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao counts = [None] * 5 7924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for i in xrange(len(counts)): 7934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao test_support.run_unittest(*test_classes) 7944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao gc.collect() 7954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao counts[i] = sys.gettotalrefcount() 7964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao print counts 7974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # doctests 7994adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao from test import test_deque 8004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao test_support.run_doctest(test_deque, verbose) 8014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 8024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoif __name__ == "__main__": 8034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao test_main(verbose=True) 804