from collections import deque import unittest import random BIG = 100000 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) 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 # 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) 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')) 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)))) 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() def test_index(self): pass 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)) 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) j = random.randrange(-len(d), len(d)) val = d[j] self.assertIn(val, d) del d[j] self.assertNotIn(val, d) j = random.randrange(-len(d), len(d)) val = d[j] self.assertIn(val, d) del d[j] self.assertNotIn(val, d) j = random.randrange(-len(d), len(d)) val = d[j] self.assertIn(val, d) del d[j] self.assertNotIn(val, d) j = random.randrange(-len(d), len(d)) val = d[j] self.assertIn(val, d) del d[j] self.assertNotIn(val, d) j = random.randrange(-len(d), len(d)) val = d[j] self.assertIn(val, d) del d[j] self.assertNotIn(val, d) 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]) 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.assertIn('...', repr(d)) 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_reversed(self): for s in ('abcd', range(2000)): self.assertEqual(list(reversed(deque(s))), list(reversed(s))) if __name__ == "__main__": unittest.main()