| from collections import deque | |
| import doctest | |
| import unittest | |
| from test import support, seq_tests | |
| import gc | |
| import weakref | |
| import copy | |
| import pickle | |
| import random | |
| import struct | |
| BIG = 100000 | |
| def fail(): | |
| raise SyntaxError | |
| yield 1 | |
| class BadCmp: | |
| def __eq__(self, other): | |
| raise RuntimeError | |
| class MutateCmp: | |
| def __init__(self, deque, result): | |
| self.deque = deque | |
| self.result = result | |
| def __eq__(self, other): | |
| self.deque.clear() | |
| return self.result | |
| class TestBasic(unittest.TestCase): | |
| def test_basics(self): | |
| d = deque(range(-5125, -5000)) | |
| d.__init__(range(200)) | |
| for i in range(200, 400): | |
| d.append(i) | |
| for i in reversed(range(-200, 0)): | |
| d.appendleft(i) | |
| self.assertEqual(list(d), list(range(-200, 400))) | |
| self.assertEqual(len(d), 600) | |
| left = [d.popleft() for i in range(250)] | |
| self.assertEqual(left, list(range(-200, 50))) | |
| self.assertEqual(list(d), list(range(50, 400))) | |
| right = [d.pop() for i in range(250)] | |
| right.reverse() | |
| self.assertEqual(right, list(range(150, 400))) | |
| self.assertEqual(list(d), list(range(50, 150))) | |
| def test_maxlen(self): | |
| self.assertRaises(ValueError, deque, 'abc', -1) | |
| self.assertRaises(ValueError, deque, 'abc', -2) | |
| it = iter(range(10)) | |
| d = deque(it, maxlen=3) | |
| self.assertEqual(list(it), []) | |
| self.assertEqual(repr(d), 'deque([7, 8, 9], maxlen=3)') | |
| self.assertEqual(list(d), [7, 8, 9]) | |
| self.assertEqual(d, deque(range(10), 3)) | |
| d.append(10) | |
| self.assertEqual(list(d), [8, 9, 10]) | |
| d.appendleft(7) | |
| self.assertEqual(list(d), [7, 8, 9]) | |
| d.extend([10, 11]) | |
| self.assertEqual(list(d), [9, 10, 11]) | |
| d.extendleft([8, 7]) | |
| self.assertEqual(list(d), [7, 8, 9]) | |
| d = deque(range(200), maxlen=10) | |
| d.append(d) | |
| self.assertEqual(repr(d)[-30:], ', 198, 199, [...]], maxlen=10)') | |
| d = deque(range(10), maxlen=None) | |
| self.assertEqual(repr(d), 'deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])') | |
| def test_maxlen_zero(self): | |
| it = iter(range(100)) | |
| deque(it, maxlen=0) | |
| self.assertEqual(list(it), []) | |
| it = iter(range(100)) | |
| d = deque(maxlen=0) | |
| d.extend(it) | |
| self.assertEqual(list(it), []) | |
| it = iter(range(100)) | |
| d = deque(maxlen=0) | |
| d.extendleft(it) | |
| self.assertEqual(list(it), []) | |
| def test_maxlen_attribute(self): | |
| self.assertEqual(deque().maxlen, None) | |
| self.assertEqual(deque('abc').maxlen, None) | |
| self.assertEqual(deque('abc', maxlen=4).maxlen, 4) | |
| self.assertEqual(deque('abc', maxlen=2).maxlen, 2) | |
| self.assertEqual(deque('abc', maxlen=0).maxlen, 0) | |
| with self.assertRaises(AttributeError): | |
| d = deque('abc') | |
| d.maxlen = 10 | |
| def test_count(self): | |
| for s in ('', 'abracadabra', 'simsalabim'*500+'abc'): | |
| s = list(s) | |
| d = deque(s) | |
| for letter in 'abcdefghijklmnopqrstuvwxyz': | |
| self.assertEqual(s.count(letter), d.count(letter), (s, d, letter)) | |
| self.assertRaises(TypeError, d.count) # too few args | |
| self.assertRaises(TypeError, d.count, 1, 2) # too many args | |
| class BadCompare: | |
| def __eq__(self, other): | |
| raise ArithmeticError | |
| d = deque([1, 2, BadCompare(), 3]) | |
| self.assertRaises(ArithmeticError, d.count, 2) | |
| d = deque([1, 2, 3]) | |
| self.assertRaises(ArithmeticError, d.count, BadCompare()) | |
| class MutatingCompare: | |
| def __eq__(self, other): | |
| self.d.pop() | |
| return True | |
| m = MutatingCompare() | |
| d = deque([1, 2, 3, m, 4, 5]) | |
| m.d = d | |
| self.assertRaises(RuntimeError, d.count, 3) | |
| # test issue11004 | |
| # block advance failed after rotation aligned elements on right side of block | |
| d = deque([None]*16) | |
| for i in range(len(d)): | |
| d.rotate(-1) | |
| d.rotate(1) | |
| self.assertEqual(d.count(1), 0) | |
| self.assertEqual(d.count(None), 16) | |
| def test_comparisons(self): | |
| d = deque('xabc') | |
| d.popleft() | |
| for e in [d, deque('abc'), deque('ab'), deque(), list(d)]: | |
| self.assertEqual(d==e, type(d)==type(e) and list(d)==list(e)) | |
| self.assertEqual(d!=e, not(type(d)==type(e) and list(d)==list(e))) | |
| args = map(deque, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba')) | |
| for x in args: | |
| for y in args: | |
| self.assertEqual(x == y, list(x) == list(y), (x,y)) | |
| self.assertEqual(x != y, list(x) != list(y), (x,y)) | |
| self.assertEqual(x < y, list(x) < list(y), (x,y)) | |
| self.assertEqual(x <= y, list(x) <= list(y), (x,y)) | |
| self.assertEqual(x > y, list(x) > list(y), (x,y)) | |
| self.assertEqual(x >= y, list(x) >= list(y), (x,y)) | |
| def test_contains(self): | |
| n = 200 | |
| d = deque(range(n)) | |
| for i in range(n): | |
| self.assertTrue(i in d) | |
| self.assertTrue((n+1) not in d) | |
| # Test detection of mutation during iteration | |
| d = deque(range(n)) | |
| d[n//2] = MutateCmp(d, False) | |
| with self.assertRaises(RuntimeError): | |
| n in d | |
| # Test detection of comparison exceptions | |
| d = deque(range(n)) | |
| d[n//2] = BadCmp() | |
| with self.assertRaises(RuntimeError): | |
| n in d | |
| def test_contains_count_index_stop_crashes(self): | |
| class A: | |
| def __eq__(self, other): | |
| d.clear() | |
| return NotImplemented | |
| d = deque([A(), A()]) | |
| with self.assertRaises(RuntimeError): | |
| _ = 3 in d | |
| d = deque([A(), A()]) | |
| with self.assertRaises(RuntimeError): | |
| _ = d.count(3) | |
| d = deque([A()]) | |
| with self.assertRaises(RuntimeError): | |
| d.index(0) | |
| def test_extend(self): | |
| d = deque('a') | |
| self.assertRaises(TypeError, d.extend, 1) | |
| d.extend('bcd') | |
| self.assertEqual(list(d), list('abcd')) | |
| d.extend(d) | |
| self.assertEqual(list(d), list('abcdabcd')) | |
| def test_add(self): | |
| d = deque() | |
| e = deque('abc') | |
| f = deque('def') | |
| self.assertEqual(d + d, deque()) | |
| self.assertEqual(e + f, deque('abcdef')) | |
| self.assertEqual(e + e, deque('abcabc')) | |
| self.assertEqual(e + d, deque('abc')) | |
| self.assertEqual(d + e, deque('abc')) | |
| self.assertIsNot(d + d, deque()) | |
| self.assertIsNot(e + d, deque('abc')) | |
| self.assertIsNot(d + e, deque('abc')) | |
| g = deque('abcdef', maxlen=4) | |
| h = deque('gh') | |
| self.assertEqual(g + h, deque('efgh')) | |
| with self.assertRaises(TypeError): | |
| deque('abc') + 'def' | |
| def test_iadd(self): | |
| d = deque('a') | |
| d += 'bcd' | |
| self.assertEqual(list(d), list('abcd')) | |
| d += d | |
| self.assertEqual(list(d), list('abcdabcd')) | |
| def test_extendleft(self): | |
| d = deque('a') | |
| self.assertRaises(TypeError, d.extendleft, 1) | |
| d.extendleft('bcd') | |
| self.assertEqual(list(d), list(reversed('abcd'))) | |
| d.extendleft(d) | |
| self.assertEqual(list(d), list('abcddcba')) | |
| d = deque() | |
| d.extendleft(range(1000)) | |
| self.assertEqual(list(d), list(reversed(range(1000)))) | |
| self.assertRaises(SyntaxError, d.extendleft, fail()) | |
| def test_getitem(self): | |
| n = 200 | |
| d = deque(range(n)) | |
| l = list(range(n)) | |
| for i in range(n): | |
| d.popleft() | |
| l.pop(0) | |
| if random.random() < 0.5: | |
| d.append(i) | |
| l.append(i) | |
| for j in range(1-len(l), len(l)): | |
| assert d[j] == l[j] | |
| d = deque('superman') | |
| self.assertEqual(d[0], 's') | |
| self.assertEqual(d[-1], 'n') | |
| d = deque() | |
| self.assertRaises(IndexError, d.__getitem__, 0) | |
| self.assertRaises(IndexError, d.__getitem__, -1) | |
| def test_index(self): | |
| for n in 1, 2, 30, 40, 200: | |
| d = deque(range(n)) | |
| for i in range(n): | |
| self.assertEqual(d.index(i), i) | |
| with self.assertRaises(ValueError): | |
| d.index(n+1) | |
| # Test detection of mutation during iteration | |
| d = deque(range(n)) | |
| d[n//2] = MutateCmp(d, False) | |
| with self.assertRaises(RuntimeError): | |
| d.index(n) | |
| # Test detection of comparison exceptions | |
| d = deque(range(n)) | |
| d[n//2] = BadCmp() | |
| with self.assertRaises(RuntimeError): | |
| d.index(n) | |
| # Test start and stop arguments behavior matches list.index() | |
| elements = 'ABCDEFGHI' | |
| nonelement = 'Z' | |
| d = deque(elements * 2) | |
| s = list(elements * 2) | |
| for start in range(-5 - len(s)*2, 5 + len(s) * 2): | |
| for stop in range(-5 - len(s)*2, 5 + len(s) * 2): | |
| for element in elements + 'Z': | |
| try: | |
| target = s.index(element, start, stop) | |
| except ValueError: | |
| with self.assertRaises(ValueError): | |
| d.index(element, start, stop) | |
| else: | |
| self.assertEqual(d.index(element, start, stop), target) | |
| # Test stop argument | |
| for elem in d: | |
| index = d.index(elem) | |
| self.assertEqual( | |
| index, | |
| d.index(elem, 0), | |
| ) | |
| self.assertEqual( | |
| index, | |
| d.index(elem, 0, len(d)), | |
| ) | |
| self.assertEqual( | |
| index, | |
| d.index(elem, 0, len(d) + 100), | |
| ) | |
| # Test large start argument | |
| d = deque(range(0, 10000, 10)) | |
| for step in range(100): | |
| i = d.index(8500, 700) | |
| self.assertEqual(d[i], 8500) | |
| # Repeat test with a different internal offset | |
| d.rotate() | |
| def test_index_bug_24913(self): | |
| d = deque('A' * 3) | |
| with self.assertRaises(ValueError): | |
| i = d.index("Hello world", 0, 4) | |
| def test_insert(self): | |
| # Test to make sure insert behaves like lists | |
| elements = 'ABCDEFGHI' | |
| for i in range(-5 - len(elements)*2, 5 + len(elements) * 2): | |
| d = deque('ABCDEFGHI') | |
| s = list('ABCDEFGHI') | |
| d.insert(i, 'Z') | |
| s.insert(i, 'Z') | |
| self.assertEqual(list(d), s) | |
| def test_insert_bug_26194(self): | |
| data = 'ABC' | |
| d = deque(data, maxlen=len(data)) | |
| with self.assertRaises(IndexError): | |
| d.insert(2, None) | |
| elements = 'ABCDEFGHI' | |
| for i in range(-len(elements), len(elements)): | |
| d = deque(elements, maxlen=len(elements)+1) | |
| d.insert(i, 'Z') | |
| if i >= 0: | |
| self.assertEqual(d[i], 'Z') | |
| else: | |
| self.assertEqual(d[i-1], 'Z') | |
| def test_imul(self): | |
| for n in (-10, -1, 0, 1, 2, 10, 1000): | |
| d = deque() | |
| d *= n | |
| self.assertEqual(d, deque()) | |
| self.assertIsNone(d.maxlen) | |
| for n in (-10, -1, 0, 1, 2, 10, 1000): | |
| d = deque('a') | |
| d *= n | |
| self.assertEqual(d, deque('a' * n)) | |
| self.assertIsNone(d.maxlen) | |
| for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000): | |
| d = deque('a', 500) | |
| d *= n | |
| self.assertEqual(d, deque('a' * min(n, 500))) | |
| self.assertEqual(d.maxlen, 500) | |
| for n in (-10, -1, 0, 1, 2, 10, 1000): | |
| d = deque('abcdef') | |
| d *= n | |
| self.assertEqual(d, deque('abcdef' * n)) | |
| self.assertIsNone(d.maxlen) | |
| for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000): | |
| d = deque('abcdef', 500) | |
| d *= n | |
| self.assertEqual(d, deque(('abcdef' * n)[-500:])) | |
| self.assertEqual(d.maxlen, 500) | |
| def test_mul(self): | |
| d = deque('abc') | |
| self.assertEqual(d * -5, deque()) | |
| self.assertEqual(d * 0, deque()) | |
| self.assertEqual(d * 1, deque('abc')) | |
| self.assertEqual(d * 2, deque('abcabc')) | |
| self.assertEqual(d * 3, deque('abcabcabc')) | |
| self.assertIsNot(d * 1, d) | |
| self.assertEqual(deque() * 0, deque()) | |
| self.assertEqual(deque() * 1, deque()) | |
| self.assertEqual(deque() * 5, deque()) | |
| self.assertEqual(-5 * d, deque()) | |
| self.assertEqual(0 * d, deque()) | |
| self.assertEqual(1 * d, deque('abc')) | |
| self.assertEqual(2 * d, deque('abcabc')) | |
| self.assertEqual(3 * d, deque('abcabcabc')) | |
| d = deque('abc', maxlen=5) | |
| self.assertEqual(d * -5, deque()) | |
| self.assertEqual(d * 0, deque()) | |
| self.assertEqual(d * 1, deque('abc')) | |
| self.assertEqual(d * 2, deque('bcabc')) | |
| self.assertEqual(d * 30, deque('bcabc')) | |
| def test_setitem(self): | |
| n = 200 | |
| d = deque(range(n)) | |
| for i in range(n): | |
| d[i] = 10 * i | |
| self.assertEqual(list(d), [10*i for i in range(n)]) | |
| l = list(d) | |
| for i in range(1-n, 0, -1): | |
| d[i] = 7*i | |
| l[i] = 7*i | |
| self.assertEqual(list(d), l) | |
| def test_delitem(self): | |
| n = 500 # O(n**2) test, don't make this too big | |
| d = deque(range(n)) | |
| self.assertRaises(IndexError, d.__delitem__, -n-1) | |
| self.assertRaises(IndexError, d.__delitem__, n) | |
| for i in range(n): | |
| self.assertEqual(len(d), n-i) | |
| j = random.randrange(-len(d), len(d)) | |
| val = d[j] | |
| self.assertIn(val, d) | |
| del d[j] | |
| self.assertNotIn(val, d) | |
| self.assertEqual(len(d), 0) | |
| def test_reverse(self): | |
| n = 500 # O(n**2) test, don't make this too big | |
| data = [random.random() for i in range(n)] | |
| for i in range(n): | |
| d = deque(data[:i]) | |
| r = d.reverse() | |
| self.assertEqual(list(d), list(reversed(data[:i]))) | |
| self.assertIs(r, None) | |
| d.reverse() | |
| self.assertEqual(list(d), data[:i]) | |
| self.assertRaises(TypeError, d.reverse, 1) # Arity is zero | |
| def test_rotate(self): | |
| s = tuple('abcde') | |
| n = len(s) | |
| d = deque(s) | |
| d.rotate(1) # verify rot(1) | |
| self.assertEqual(''.join(d), 'eabcd') | |
| d = deque(s) | |
| d.rotate(-1) # verify rot(-1) | |
| self.assertEqual(''.join(d), 'bcdea') | |
| d.rotate() # check default to 1 | |
| self.assertEqual(tuple(d), s) | |
| for i in range(n*3): | |
| d = deque(s) | |
| e = deque(d) | |
| d.rotate(i) # check vs. rot(1) n times | |
| for j in range(i): | |
| e.rotate(1) | |
| self.assertEqual(tuple(d), tuple(e)) | |
| d.rotate(-i) # check that it works in reverse | |
| self.assertEqual(tuple(d), s) | |
| e.rotate(n-i) # check that it wraps forward | |
| self.assertEqual(tuple(e), s) | |
| for i in range(n*3): | |
| d = deque(s) | |
| e = deque(d) | |
| d.rotate(-i) | |
| for j in range(i): | |
| e.rotate(-1) # check vs. rot(-1) n times | |
| self.assertEqual(tuple(d), tuple(e)) | |
| d.rotate(i) # check that it works in reverse | |
| self.assertEqual(tuple(d), s) | |
| e.rotate(i-n) # check that it wraps backaround | |
| self.assertEqual(tuple(e), s) | |
| d = deque(s) | |
| e = deque(s) | |
| e.rotate(BIG+17) # verify on long series of rotates | |
| dr = d.rotate | |
| for i in range(BIG+17): | |
| dr() | |
| self.assertEqual(tuple(d), tuple(e)) | |
| self.assertRaises(TypeError, d.rotate, 'x') # Wrong arg type | |
| self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args | |
| d = deque() | |
| d.rotate() # rotate an empty deque | |
| self.assertEqual(d, deque()) | |
| def test_len(self): | |
| d = deque('ab') | |
| self.assertEqual(len(d), 2) | |
| d.popleft() | |
| self.assertEqual(len(d), 1) | |
| d.pop() | |
| self.assertEqual(len(d), 0) | |
| self.assertRaises(IndexError, d.pop) | |
| self.assertEqual(len(d), 0) | |
| d.append('c') | |
| self.assertEqual(len(d), 1) | |
| d.appendleft('d') | |
| self.assertEqual(len(d), 2) | |
| d.clear() | |
| self.assertEqual(len(d), 0) | |
| def test_underflow(self): | |
| d = deque() | |
| self.assertRaises(IndexError, d.pop) | |
| self.assertRaises(IndexError, d.popleft) | |
| def test_clear(self): | |
| d = deque(range(100)) | |
| self.assertEqual(len(d), 100) | |
| d.clear() | |
| self.assertEqual(len(d), 0) | |
| self.assertEqual(list(d), []) | |
| d.clear() # clear an empty deque | |
| self.assertEqual(list(d), []) | |
| def test_remove(self): | |
| d = deque('abcdefghcij') | |
| d.remove('c') | |
| self.assertEqual(d, deque('abdefghcij')) | |
| d.remove('c') | |
| self.assertEqual(d, deque('abdefghij')) | |
| self.assertRaises(ValueError, d.remove, 'c') | |
| self.assertEqual(d, deque('abdefghij')) | |
| # Handle comparison errors | |
| d = deque(['a', 'b', BadCmp(), 'c']) | |
| e = deque(d) | |
| self.assertRaises(RuntimeError, d.remove, 'c') | |
| for x, y in zip(d, e): | |
| # verify that original order and values are retained. | |
| self.assertTrue(x is y) | |
| # Handle evil mutator | |
| for match in (True, False): | |
| d = deque(['ab']) | |
| d.extend([MutateCmp(d, match), 'c']) | |
| self.assertRaises(IndexError, d.remove, 'c') | |
| self.assertEqual(d, deque()) | |
| def test_repr(self): | |
| d = deque(range(200)) | |
| e = eval(repr(d)) | |
| self.assertEqual(list(d), list(e)) | |
| d.append(d) | |
| self.assertEqual(repr(d)[-20:], '7, 198, 199, [...]])') | |
| def test_init(self): | |
| self.assertRaises(TypeError, deque, 'abc', 2, 3) | |
| self.assertRaises(TypeError, deque, 1) | |
| def test_hash(self): | |
| self.assertRaises(TypeError, hash, deque('abc')) | |
| def test_long_steadystate_queue_popleft(self): | |
| for size in (0, 1, 2, 100, 1000): | |
| d = deque(range(size)) | |
| append, pop = d.append, d.popleft | |
| for i in range(size, BIG): | |
| append(i) | |
| x = pop() | |
| if x != i - size: | |
| self.assertEqual(x, i-size) | |
| self.assertEqual(list(d), list(range(BIG-size, BIG))) | |
| def test_long_steadystate_queue_popright(self): | |
| for size in (0, 1, 2, 100, 1000): | |
| d = deque(reversed(range(size))) | |
| append, pop = d.appendleft, d.pop | |
| for i in range(size, BIG): | |
| append(i) | |
| x = pop() | |
| if x != i - size: | |
| self.assertEqual(x, i-size) | |
| self.assertEqual(list(reversed(list(d))), | |
| list(range(BIG-size, BIG))) | |
| def test_big_queue_popleft(self): | |
| pass | |
| d = deque() | |
| append, pop = d.append, d.popleft | |
| for i in range(BIG): | |
| append(i) | |
| for i in range(BIG): | |
| x = pop() | |
| if x != i: | |
| self.assertEqual(x, i) | |
| def test_big_queue_popright(self): | |
| d = deque() | |
| append, pop = d.appendleft, d.pop | |
| for i in range(BIG): | |
| append(i) | |
| for i in range(BIG): | |
| x = pop() | |
| if x != i: | |
| self.assertEqual(x, i) | |
| def test_big_stack_right(self): | |
| d = deque() | |
| append, pop = d.append, d.pop | |
| for i in range(BIG): | |
| append(i) | |
| for i in reversed(range(BIG)): | |
| x = pop() | |
| if x != i: | |
| self.assertEqual(x, i) | |
| self.assertEqual(len(d), 0) | |
| def test_big_stack_left(self): | |
| d = deque() | |
| append, pop = d.appendleft, d.popleft | |
| for i in range(BIG): | |
| append(i) | |
| for i in reversed(range(BIG)): | |
| x = pop() | |
| if x != i: | |
| self.assertEqual(x, i) | |
| self.assertEqual(len(d), 0) | |
| def test_roundtrip_iter_init(self): | |
| d = deque(range(200)) | |
| e = deque(d) | |
| self.assertNotEqual(id(d), id(e)) | |
| self.assertEqual(list(d), list(e)) | |
| def test_pickle(self): | |
| for d in deque(range(200)), deque(range(200), 100): | |
| for i in range(pickle.HIGHEST_PROTOCOL + 1): | |
| s = pickle.dumps(d, i) | |
| e = pickle.loads(s) | |
| self.assertNotEqual(id(e), id(d)) | |
| self.assertEqual(list(e), list(d)) | |
| self.assertEqual(e.maxlen, d.maxlen) | |
| def test_pickle_recursive(self): | |
| for d in deque('abc'), deque('abc', 3): | |
| d.append(d) | |
| for i in range(pickle.HIGHEST_PROTOCOL + 1): | |
| e = pickle.loads(pickle.dumps(d, i)) | |
| self.assertNotEqual(id(e), id(d)) | |
| self.assertEqual(id(e[-1]), id(e)) | |
| self.assertEqual(e.maxlen, d.maxlen) | |
| def test_iterator_pickle(self): | |
| orig = deque(range(200)) | |
| data = [i*1.01 for i in orig] | |
| for proto in range(pickle.HIGHEST_PROTOCOL + 1): | |
| # initial iterator | |
| itorg = iter(orig) | |
| dump = pickle.dumps((itorg, orig), proto) | |
| it, d = pickle.loads(dump) | |
| for i, x in enumerate(data): | |
| d[i] = x | |
| self.assertEqual(type(it), type(itorg)) | |
| self.assertEqual(list(it), data) | |
| # running iterator | |
| next(itorg) | |
| dump = pickle.dumps((itorg, orig), proto) | |
| it, d = pickle.loads(dump) | |
| for i, x in enumerate(data): | |
| d[i] = x | |
| self.assertEqual(type(it), type(itorg)) | |
| self.assertEqual(list(it), data[1:]) | |
| # empty iterator | |
| for i in range(1, len(data)): | |
| next(itorg) | |
| dump = pickle.dumps((itorg, orig), proto) | |
| it, d = pickle.loads(dump) | |
| for i, x in enumerate(data): | |
| d[i] = x | |
| self.assertEqual(type(it), type(itorg)) | |
| self.assertEqual(list(it), []) | |
| # exhausted iterator | |
| self.assertRaises(StopIteration, next, itorg) | |
| dump = pickle.dumps((itorg, orig), proto) | |
| it, d = pickle.loads(dump) | |
| for i, x in enumerate(data): | |
| d[i] = x | |
| self.assertEqual(type(it), type(itorg)) | |
| self.assertEqual(list(it), []) | |
| def test_deepcopy(self): | |
| mut = [10] | |
| d = deque([mut]) | |
| e = copy.deepcopy(d) | |
| self.assertEqual(list(d), list(e)) | |
| mut[0] = 11 | |
| self.assertNotEqual(id(d), id(e)) | |
| self.assertNotEqual(list(d), list(e)) | |
| def test_copy(self): | |
| mut = [10] | |
| d = deque([mut]) | |
| e = copy.copy(d) | |
| self.assertEqual(list(d), list(e)) | |
| mut[0] = 11 | |
| self.assertNotEqual(id(d), id(e)) | |
| self.assertEqual(list(d), list(e)) | |
| for i in range(5): | |
| for maxlen in range(-1, 6): | |
| s = [random.random() for j in range(i)] | |
| d = deque(s) if maxlen == -1 else deque(s, maxlen) | |
| e = d.copy() | |
| self.assertEqual(d, e) | |
| self.assertEqual(d.maxlen, e.maxlen) | |
| self.assertTrue(all(x is y for x, y in zip(d, e))) | |
| def test_copy_method(self): | |
| mut = [10] | |
| d = deque([mut]) | |
| e = d.copy() | |
| self.assertEqual(list(d), list(e)) | |
| mut[0] = 11 | |
| self.assertNotEqual(id(d), id(e)) | |
| self.assertEqual(list(d), list(e)) | |
| def test_reversed(self): | |
| for s in ('abcd', range(2000)): | |
| self.assertEqual(list(reversed(deque(s))), list(reversed(s))) | |
| def test_reversed_new(self): | |
| klass = type(reversed(deque())) | |
| for s in ('abcd', range(2000)): | |
| self.assertEqual(list(klass(deque(s))), list(reversed(s))) | |
| def test_gc_doesnt_blowup(self): | |
| import gc | |
| # This used to assert-fail in deque_traverse() under a debug | |
| # build, or run wild with a NULL pointer in a release build. | |
| d = deque() | |
| for i in range(100): | |
| d.append(1) | |
| gc.collect() | |
| def test_container_iterator(self): | |
| # Bug #3680: tp_traverse was not implemented for deque iterator objects | |
| class C(object): | |
| pass | |
| for i in range(2): | |
| obj = C() | |
| ref = weakref.ref(obj) | |
| if i == 0: | |
| container = deque([obj, 1]) | |
| else: | |
| container = reversed(deque([obj, 1])) | |
| obj.x = iter(container) | |
| del obj, container | |
| gc.collect() | |
| self.assertTrue(ref() is None, "Cycle was not collected") | |
| check_sizeof = support.check_sizeof | |
| @support.cpython_only | |
| def test_sizeof(self): | |
| MAXFREEBLOCKS = 16 | |
| BLOCKLEN = 64 | |
| basesize = support.calcvobjsize('2P5n%dPP' % MAXFREEBLOCKS) | |
| blocksize = struct.calcsize('P%dPP' % BLOCKLEN) | |
| self.assertEqual(object.__sizeof__(deque()), basesize) | |
| check = self.check_sizeof | |
| check(deque(), basesize + blocksize) | |
| check(deque('a'), basesize + blocksize) | |
| check(deque('a' * (BLOCKLEN - 1)), basesize + blocksize) | |
| check(deque('a' * BLOCKLEN), basesize + 2 * blocksize) | |
| check(deque('a' * (42 * BLOCKLEN)), basesize + 43 * blocksize) | |
| class TestVariousIteratorArgs(unittest.TestCase): | |
| def test_constructor(self): | |
| for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)): | |
| for g in (seq_tests.Sequence, seq_tests.IterFunc, | |
| seq_tests.IterGen, seq_tests.IterFuncStop, | |
| seq_tests.itermulti, seq_tests.iterfunc): | |
| self.assertEqual(list(deque(g(s))), list(g(s))) | |
| self.assertRaises(TypeError, deque, seq_tests.IterNextOnly(s)) | |
| self.assertRaises(TypeError, deque, seq_tests.IterNoNext(s)) | |
| self.assertRaises(ZeroDivisionError, deque, seq_tests.IterGenExc(s)) | |
| def test_iter_with_altered_data(self): | |
| d = deque('abcdefg') | |
| it = iter(d) | |
| d.pop() | |
| self.assertRaises(RuntimeError, next, it) | |
| def test_runtime_error_on_empty_deque(self): | |
| d = deque() | |
| it = iter(d) | |
| d.append(10) | |
| self.assertRaises(RuntimeError, next, it) | |
| class Deque(deque): | |
| pass | |
| class DequeWithSlots(deque): | |
| __slots__ = ('x', 'y', '__dict__') | |
| class DequeWithBadIter(deque): | |
| def __iter__(self): | |
| raise TypeError | |
| class TestSubclass(unittest.TestCase): | |
| def test_basics(self): | |
| d = Deque(range(25)) | |
| d.__init__(range(200)) | |
| for i in range(200, 400): | |
| d.append(i) | |
| for i in reversed(range(-200, 0)): | |
| d.appendleft(i) | |
| self.assertEqual(list(d), list(range(-200, 400))) | |
| self.assertEqual(len(d), 600) | |
| left = [d.popleft() for i in range(250)] | |
| self.assertEqual(left, list(range(-200, 50))) | |
| self.assertEqual(list(d), list(range(50, 400))) | |
| right = [d.pop() for i in range(250)] | |
| right.reverse() | |
| self.assertEqual(right, list(range(150, 400))) | |
| self.assertEqual(list(d), list(range(50, 150))) | |
| d.clear() | |
| self.assertEqual(len(d), 0) | |
| def test_copy_pickle(self): | |
| for cls in Deque, DequeWithSlots: | |
| for d in cls('abc'), cls('abcde', maxlen=4): | |
| d.x = ['x'] | |
| d.z = ['z'] | |
| e = d.__copy__() | |
| self.assertEqual(type(d), type(e)) | |
| self.assertEqual(list(d), list(e)) | |
| e = cls(d) | |
| self.assertEqual(type(d), type(e)) | |
| self.assertEqual(list(d), list(e)) | |
| for proto in range(pickle.HIGHEST_PROTOCOL + 1): | |
| s = pickle.dumps(d, proto) | |
| e = pickle.loads(s) | |
| self.assertNotEqual(id(d), id(e)) | |
| self.assertEqual(type(d), type(e)) | |
| self.assertEqual(list(d), list(e)) | |
| self.assertEqual(e.x, d.x) | |
| self.assertEqual(e.z, d.z) | |
| self.assertNotHasAttr(e, 'y') | |
| def test_pickle_recursive(self): | |
| for proto in range(pickle.HIGHEST_PROTOCOL + 1): | |
| for d in Deque('abc'), Deque('abc', 3): | |
| d.append(d) | |
| e = pickle.loads(pickle.dumps(d, proto)) | |
| self.assertNotEqual(id(e), id(d)) | |
| self.assertEqual(type(e), type(d)) | |
| self.assertEqual(e.maxlen, d.maxlen) | |
| dd = d.pop() | |
| ee = e.pop() | |
| self.assertEqual(id(ee), id(e)) | |
| self.assertEqual(e, d) | |
| d.x = d | |
| e = pickle.loads(pickle.dumps(d, proto)) | |
| self.assertEqual(id(e.x), id(e)) | |
| for d in DequeWithBadIter('abc'), DequeWithBadIter('abc', 2): | |
| self.assertRaises(TypeError, pickle.dumps, d, proto) | |
| def test_weakref(self): | |
| d = deque('gallahad') | |
| p = weakref.proxy(d) | |
| self.assertEqual(str(p), str(d)) | |
| d = None | |
| support.gc_collect() # For PyPy or other GCs. | |
| self.assertRaises(ReferenceError, str, p) | |
| def test_strange_subclass(self): | |
| class X(deque): | |
| def __iter__(self): | |
| return iter([]) | |
| d1 = X([1,2,3]) | |
| d2 = X([4,5,6]) | |
| d1 == d2 # not clear if this is supposed to be True or False, | |
| # but it used to give a SystemError | |
| @support.cpython_only | |
| def test_bug_31608(self): | |
| # The interpreter used to crash in specific cases where a deque | |
| # subclass returned a non-deque. | |
| class X(deque): | |
| pass | |
| d = X() | |
| def bad___new__(cls, *args, **kwargs): | |
| return [42] | |
| X.__new__ = bad___new__ | |
| with self.assertRaises(TypeError): | |
| d * 42 # shouldn't crash | |
| with self.assertRaises(TypeError): | |
| d + deque([1, 2, 3]) # shouldn't crash | |
| class SubclassWithKwargs(deque): | |
| def __init__(self, newarg=1): | |
| deque.__init__(self) | |
| class TestSubclassWithKwargs(unittest.TestCase): | |
| def test_subclass_with_kwargs(self): | |
| # SF bug #1486663 -- this used to erroneously raise a TypeError | |
| SubclassWithKwargs(newarg=1) | |
| class TestSequence(seq_tests.CommonTest): | |
| type2test = deque | |
| def test_getitem(self): | |
| # For now, bypass tests that require slicing | |
| pass | |
| def test_getslice(self): | |
| # For now, bypass tests that require slicing | |
| pass | |
| def test_subscript(self): | |
| # For now, bypass tests that require slicing | |
| pass | |
| def test_free_after_iterating(self): | |
| # For now, bypass tests that require slicing | |
| self.skipTest("Exhausted deque iterator doesn't free a deque") | |
| #============================================================================== | |
| libreftest = """ | |
| Example from the Library Reference: Doc/lib/libcollections.tex | |
| >>> from collections import deque | |
| >>> d = deque('ghi') # make a new deque with three items | |
| >>> for elem in d: # iterate over the deque's elements | |
| ... print(elem.upper()) | |
| G | |
| H | |
| I | |
| >>> d.append('j') # add a new entry to the right side | |
| >>> d.appendleft('f') # add a new entry to the left side | |
| >>> d # show the representation of the deque | |
| deque(['f', 'g', 'h', 'i', 'j']) | |
| >>> d.pop() # return and remove the rightmost item | |
| 'j' | |
| >>> d.popleft() # return and remove the leftmost item | |
| 'f' | |
| >>> list(d) # list the contents of the deque | |
| ['g', 'h', 'i'] | |
| >>> d[0] # peek at leftmost item | |
| 'g' | |
| >>> d[-1] # peek at rightmost item | |
| 'i' | |
| >>> list(reversed(d)) # list the contents of a deque in reverse | |
| ['i', 'h', 'g'] | |
| >>> 'h' in d # search the deque | |
| True | |
| >>> d.extend('jkl') # add multiple elements at once | |
| >>> d | |
| deque(['g', 'h', 'i', 'j', 'k', 'l']) | |
| >>> d.rotate(1) # right rotation | |
| >>> d | |
| deque(['l', 'g', 'h', 'i', 'j', 'k']) | |
| >>> d.rotate(-1) # left rotation | |
| >>> d | |
| deque(['g', 'h', 'i', 'j', 'k', 'l']) | |
| >>> deque(reversed(d)) # make a new deque in reverse order | |
| deque(['l', 'k', 'j', 'i', 'h', 'g']) | |
| >>> d.clear() # empty the deque | |
| >>> d.pop() # cannot pop from an empty deque | |
| Traceback (most recent call last): | |
| File "<pyshell#6>", line 1, in -toplevel- | |
| d.pop() | |
| IndexError: pop from an empty deque | |
| >>> d.extendleft('abc') # extendleft() reverses the input order | |
| >>> d | |
| deque(['c', 'b', 'a']) | |
| >>> def delete_nth(d, n): | |
| ... d.rotate(-n) | |
| ... d.popleft() | |
| ... d.rotate(n) | |
| ... | |
| >>> d = deque('abcdef') | |
| >>> delete_nth(d, 2) # remove the entry at d[2] | |
| >>> d | |
| deque(['a', 'b', 'd', 'e', 'f']) | |
| >>> def roundrobin(*iterables): | |
| ... pending = deque(iter(i) for i in iterables) | |
| ... while pending: | |
| ... task = pending.popleft() | |
| ... try: | |
| ... yield next(task) | |
| ... except StopIteration: | |
| ... continue | |
| ... pending.append(task) | |
| ... | |
| >>> for value in roundrobin('abc', 'd', 'efgh'): | |
| ... print(value) | |
| ... | |
| a | |
| d | |
| e | |
| b | |
| f | |
| c | |
| g | |
| h | |
| >>> def maketree(iterable): | |
| ... d = deque(iterable) | |
| ... while len(d) > 1: | |
| ... pair = [d.popleft(), d.popleft()] | |
| ... d.append(pair) | |
| ... return list(d) | |
| ... | |
| >>> print(maketree('abcdefgh')) | |
| [[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]] | |
| """ | |
| #============================================================================== | |
| __test__ = {'libreftest' : libreftest} | |
| def load_tests(loader, tests, pattern): | |
| tests.addTest(doctest.DocTestSuite()) | |
| return tests | |
| if __name__ == "__main__": | |
| unittest.main() |