blob: da00c0d206fd2f99d453eaebe3f9fe6d46da0c1c [file] [log] [blame]
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001from collections import deque
2import unittest
Benjamin Petersonee8712c2008-05-20 21:35:26 +00003from test import support, seq_tests
Antoine Pitrou7ddda782009-01-01 15:35:33 +00004import gc
5import weakref
Raymond Hettinger756b3f32004-01-29 06:37:52 +00006import copy
Guido van Rossumbf12cdb2006-08-17 20:24:18 +00007import pickle
Guido van Rossum34d19282007-08-09 01:03:29 +00008from io import StringIO
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00009import random
Raymond Hettinger756b3f32004-01-29 06:37:52 +000010
11BIG = 100000
12
Raymond Hettingera435c532004-07-09 04:10:20 +000013def fail():
14 raise SyntaxError
15 yield 1
16
Raymond Hettinger4aec61e2005-03-18 21:20:23 +000017class BadCmp:
18 def __eq__(self, other):
19 raise RuntimeError
20
21class MutateCmp:
Raymond Hettingerd73202c2005-03-19 00:00:51 +000022 def __init__(self, deque, result):
Raymond Hettinger4aec61e2005-03-18 21:20:23 +000023 self.deque = deque
Raymond Hettingerd73202c2005-03-19 00:00:51 +000024 self.result = result
Raymond Hettinger4aec61e2005-03-18 21:20:23 +000025 def __eq__(self, other):
26 self.deque.clear()
Raymond Hettingerd73202c2005-03-19 00:00:51 +000027 return self.result
Raymond Hettinger4aec61e2005-03-18 21:20:23 +000028
Raymond Hettinger756b3f32004-01-29 06:37:52 +000029class TestBasic(unittest.TestCase):
30
31 def test_basics(self):
Christian Heimes38053212007-12-14 01:24:44 +000032 d = deque(range(-5125, -5000))
33 d.__init__(range(200))
Guido van Rossum805365e2007-05-07 22:24:25 +000034 for i in range(200, 400):
Raymond Hettinger756b3f32004-01-29 06:37:52 +000035 d.append(i)
Guido van Rossum805365e2007-05-07 22:24:25 +000036 for i in reversed(range(-200, 0)):
Raymond Hettinger756b3f32004-01-29 06:37:52 +000037 d.appendleft(i)
Guido van Rossum805365e2007-05-07 22:24:25 +000038 self.assertEqual(list(d), list(range(-200, 400)))
Raymond Hettinger756b3f32004-01-29 06:37:52 +000039 self.assertEqual(len(d), 600)
40
Guido van Rossum805365e2007-05-07 22:24:25 +000041 left = [d.popleft() for i in range(250)]
42 self.assertEqual(left, list(range(-200, 50)))
43 self.assertEqual(list(d), list(range(50, 400)))
Raymond Hettinger756b3f32004-01-29 06:37:52 +000044
Guido van Rossum805365e2007-05-07 22:24:25 +000045 right = [d.pop() for i in range(250)]
Raymond Hettinger756b3f32004-01-29 06:37:52 +000046 right.reverse()
Guido van Rossum805365e2007-05-07 22:24:25 +000047 self.assertEqual(right, list(range(150, 400)))
48 self.assertEqual(list(d), list(range(50, 150)))
Raymond Hettinger756b3f32004-01-29 06:37:52 +000049
Guido van Rossum8ce8a782007-11-01 19:42:39 +000050 def test_maxlen(self):
51 self.assertRaises(ValueError, deque, 'abc', -1)
52 self.assertRaises(ValueError, deque, 'abc', -2)
Raymond Hettinger060c7f62009-03-10 09:36:07 +000053 it = iter(range(10))
54 d = deque(it, maxlen=3)
55 self.assertEqual(list(it), [])
Guido van Rossum8ce8a782007-11-01 19:42:39 +000056 self.assertEqual(repr(d), 'deque([7, 8, 9], maxlen=3)')
57 self.assertEqual(list(d), [7, 8, 9])
58 self.assertEqual(d, deque(range(10), 3))
59 d.append(10)
60 self.assertEqual(list(d), [8, 9, 10])
61 d.appendleft(7)
62 self.assertEqual(list(d), [7, 8, 9])
63 d.extend([10, 11])
64 self.assertEqual(list(d), [9, 10, 11])
65 d.extendleft([8, 7])
66 self.assertEqual(list(d), [7, 8, 9])
67 d = deque(range(200), maxlen=10)
68 d.append(d)
Benjamin Petersonee8712c2008-05-20 21:35:26 +000069 support.unlink(support.TESTFN)
70 fo = open(support.TESTFN, "w")
Christian Heimescc47b052008-03-25 14:56:36 +000071 try:
72 fo.write(str(d))
73 fo.close()
Benjamin Petersonee8712c2008-05-20 21:35:26 +000074 fo = open(support.TESTFN, "r")
Christian Heimescc47b052008-03-25 14:56:36 +000075 self.assertEqual(fo.read(), repr(d))
76 finally:
77 fo.close()
Benjamin Petersonee8712c2008-05-20 21:35:26 +000078 support.unlink(support.TESTFN)
Christian Heimescc47b052008-03-25 14:56:36 +000079
Guido van Rossum8ce8a782007-11-01 19:42:39 +000080 d = deque(range(10), maxlen=None)
81 self.assertEqual(repr(d), 'deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])')
Benjamin Petersonee8712c2008-05-20 21:35:26 +000082 fo = open(support.TESTFN, "w")
Christian Heimescc47b052008-03-25 14:56:36 +000083 try:
84 fo.write(str(d))
85 fo.close()
Benjamin Petersonee8712c2008-05-20 21:35:26 +000086 fo = open(support.TESTFN, "r")
Christian Heimescc47b052008-03-25 14:56:36 +000087 self.assertEqual(fo.read(), repr(d))
88 finally:
89 fo.close()
Benjamin Petersonee8712c2008-05-20 21:35:26 +000090 support.unlink(support.TESTFN)
Guido van Rossum8ce8a782007-11-01 19:42:39 +000091
Raymond Hettinger060c7f62009-03-10 09:36:07 +000092 def test_maxlen_zero(self):
93 it = iter(range(100))
94 deque(it, maxlen=0)
95 self.assertEqual(list(it), [])
96
97 it = iter(range(100))
98 d = deque(maxlen=0)
99 d.extend(it)
100 self.assertEqual(list(it), [])
101
102 it = iter(range(100))
103 d = deque(maxlen=0)
104 d.extendleft(it)
105 self.assertEqual(list(it), [])
106
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +0000107 def test_maxlen_attribute(self):
108 self.assertEqual(deque().maxlen, None)
109 self.assertEqual(deque('abc').maxlen, None)
110 self.assertEqual(deque('abc', maxlen=4).maxlen, 4)
111 self.assertEqual(deque('abc', maxlen=2).maxlen, 2)
112 self.assertEqual(deque('abc', maxlen=0).maxlen, 0)
113 with self.assertRaises(AttributeError):
114 d = deque('abc')
115 d.maxlen = 10
116
Raymond Hettinger44459de2010-04-03 23:20:46 +0000117 def test_count(self):
118 for s in ('', 'abracadabra', 'simsalabim'*500+'abc'):
119 s = list(s)
120 d = deque(s)
121 for letter in 'abcdefghijklmnopqrstuvwxyz':
122 self.assertEqual(s.count(letter), d.count(letter), (s, d, letter))
123 self.assertRaises(TypeError, d.count) # too few args
124 self.assertRaises(TypeError, d.count, 1, 2) # too many args
125 class BadCompare:
126 def __eq__(self, other):
127 raise ArithmeticError
128 d = deque([1, 2, BadCompare(), 3])
129 self.assertRaises(ArithmeticError, d.count, 2)
130 d = deque([1, 2, 3])
131 self.assertRaises(ArithmeticError, d.count, BadCompare())
132 class MutatingCompare:
133 def __eq__(self, other):
134 self.d.pop()
135 return True
136 m = MutatingCompare()
137 d = deque([1, 2, 3, m, 4, 5])
138 m.d = d
139 self.assertRaises(RuntimeError, d.count, 3)
140
Raymond Hettinger738ec902004-02-29 02:15:56 +0000141 def test_comparisons(self):
142 d = deque('xabc'); d.popleft()
143 for e in [d, deque('abc'), deque('ab'), deque(), list(d)]:
144 self.assertEqual(d==e, type(d)==type(e) and list(d)==list(e))
145 self.assertEqual(d!=e, not(type(d)==type(e) and list(d)==list(e)))
146
147 args = map(deque, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba'))
148 for x in args:
149 for y in args:
150 self.assertEqual(x == y, list(x) == list(y), (x,y))
151 self.assertEqual(x != y, list(x) != list(y), (x,y))
152 self.assertEqual(x < y, list(x) < list(y), (x,y))
153 self.assertEqual(x <= y, list(x) <= list(y), (x,y))
154 self.assertEqual(x > y, list(x) > list(y), (x,y))
155 self.assertEqual(x >= y, list(x) >= list(y), (x,y))
Raymond Hettinger738ec902004-02-29 02:15:56 +0000156
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000157 def test_extend(self):
158 d = deque('a')
159 self.assertRaises(TypeError, d.extend, 1)
160 d.extend('bcd')
161 self.assertEqual(list(d), list('abcd'))
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000162 d.extend(d)
163 self.assertEqual(list(d), list('abcdabcd'))
164
165 def test_iadd(self):
166 d = deque('a')
167 d += 'bcd'
168 self.assertEqual(list(d), list('abcd'))
169 d += d
170 self.assertEqual(list(d), list('abcdabcd'))
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000171
172 def test_extendleft(self):
173 d = deque('a')
174 self.assertRaises(TypeError, d.extendleft, 1)
175 d.extendleft('bcd')
176 self.assertEqual(list(d), list(reversed('abcd')))
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000177 d.extendleft(d)
178 self.assertEqual(list(d), list('abcddcba'))
Raymond Hettingera435c532004-07-09 04:10:20 +0000179 d = deque()
180 d.extendleft(range(1000))
181 self.assertEqual(list(d), list(reversed(range(1000))))
182 self.assertRaises(SyntaxError, d.extendleft, fail())
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000183
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000184 def test_getitem(self):
185 n = 200
Guido van Rossum805365e2007-05-07 22:24:25 +0000186 d = deque(range(n))
187 l = list(range(n))
188 for i in range(n):
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000189 d.popleft()
190 l.pop(0)
191 if random.random() < 0.5:
192 d.append(i)
193 l.append(i)
Guido van Rossum805365e2007-05-07 22:24:25 +0000194 for j in range(1-len(l), len(l)):
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000195 assert d[j] == l[j]
196
Raymond Hettinger738ec902004-02-29 02:15:56 +0000197 d = deque('superman')
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000198 self.assertEqual(d[0], 's')
199 self.assertEqual(d[-1], 'n')
Raymond Hettinger738ec902004-02-29 02:15:56 +0000200 d = deque()
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000201 self.assertRaises(IndexError, d.__getitem__, 0)
202 self.assertRaises(IndexError, d.__getitem__, -1)
203
204 def test_setitem(self):
205 n = 200
Guido van Rossum805365e2007-05-07 22:24:25 +0000206 d = deque(range(n))
207 for i in range(n):
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000208 d[i] = 10 * i
Guido van Rossum805365e2007-05-07 22:24:25 +0000209 self.assertEqual(list(d), [10*i for i in range(n)])
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000210 l = list(d)
Guido van Rossum805365e2007-05-07 22:24:25 +0000211 for i in range(1-n, 0, -1):
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000212 d[i] = 7*i
213 l[i] = 7*i
214 self.assertEqual(list(d), l)
Raymond Hettinger738ec902004-02-29 02:15:56 +0000215
Raymond Hettinger0e371f22004-05-12 20:55:56 +0000216 def test_delitem(self):
217 n = 500 # O(n**2) test, don't make this too big
Guido van Rossum805365e2007-05-07 22:24:25 +0000218 d = deque(range(n))
Raymond Hettinger0e371f22004-05-12 20:55:56 +0000219 self.assertRaises(IndexError, d.__delitem__, -n-1)
220 self.assertRaises(IndexError, d.__delitem__, n)
Guido van Rossum805365e2007-05-07 22:24:25 +0000221 for i in range(n):
Raymond Hettinger0e371f22004-05-12 20:55:56 +0000222 self.assertEqual(len(d), n-i)
223 j = random.randrange(-len(d), len(d))
224 val = d[j]
Benjamin Peterson577473f2010-01-19 00:09:57 +0000225 self.assertIn(val, d)
Raymond Hettinger0e371f22004-05-12 20:55:56 +0000226 del d[j]
Benjamin Peterson577473f2010-01-19 00:09:57 +0000227 self.assertNotIn(val, d)
Raymond Hettinger0e371f22004-05-12 20:55:56 +0000228 self.assertEqual(len(d), 0)
229
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000230 def test_reverse(self):
231 n = 500 # O(n**2) test, don't make this too big
232 data = [random.random() for i in range(n)]
233 for i in range(n):
234 d = deque(data[:i])
235 r = d.reverse()
236 self.assertEqual(list(d), list(reversed(data[:i])))
Ezio Melottib3aedd42010-11-20 19:04:17 +0000237 self.assertIs(r, None)
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000238 d.reverse()
239 self.assertEqual(list(d), data[:i])
240 self.assertRaises(TypeError, d.reverse, 1) # Arity is zero
241
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000242 def test_rotate(self):
Raymond Hettingeree33b272004-02-08 04:05:26 +0000243 s = tuple('abcde')
244 n = len(s)
245
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000246 d = deque(s)
Raymond Hettingeree33b272004-02-08 04:05:26 +0000247 d.rotate(1) # verify rot(1)
248 self.assertEqual(''.join(d), 'eabcd')
249
250 d = deque(s)
251 d.rotate(-1) # verify rot(-1)
252 self.assertEqual(''.join(d), 'bcdea')
253 d.rotate() # check default to 1
254 self.assertEqual(tuple(d), s)
255
Guido van Rossum805365e2007-05-07 22:24:25 +0000256 for i in range(n*3):
Raymond Hettingeree33b272004-02-08 04:05:26 +0000257 d = deque(s)
258 e = deque(d)
259 d.rotate(i) # check vs. rot(1) n times
Guido van Rossum805365e2007-05-07 22:24:25 +0000260 for j in range(i):
Raymond Hettingeree33b272004-02-08 04:05:26 +0000261 e.rotate(1)
262 self.assertEqual(tuple(d), tuple(e))
263 d.rotate(-i) # check that it works in reverse
264 self.assertEqual(tuple(d), s)
265 e.rotate(n-i) # check that it wraps forward
266 self.assertEqual(tuple(e), s)
267
Guido van Rossum805365e2007-05-07 22:24:25 +0000268 for i in range(n*3):
Raymond Hettingeree33b272004-02-08 04:05:26 +0000269 d = deque(s)
270 e = deque(d)
271 d.rotate(-i)
Guido van Rossum805365e2007-05-07 22:24:25 +0000272 for j in range(i):
Raymond Hettingeree33b272004-02-08 04:05:26 +0000273 e.rotate(-1) # check vs. rot(-1) n times
274 self.assertEqual(tuple(d), tuple(e))
275 d.rotate(i) # check that it works in reverse
276 self.assertEqual(tuple(d), s)
277 e.rotate(i-n) # check that it wraps backaround
278 self.assertEqual(tuple(e), s)
279
280 d = deque(s)
281 e = deque(s)
282 e.rotate(BIG+17) # verify on long series of rotates
283 dr = d.rotate
Guido van Rossum805365e2007-05-07 22:24:25 +0000284 for i in range(BIG+17):
Raymond Hettingeree33b272004-02-08 04:05:26 +0000285 dr()
286 self.assertEqual(tuple(d), tuple(e))
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000287
Raymond Hettingera435c532004-07-09 04:10:20 +0000288 self.assertRaises(TypeError, d.rotate, 'x') # Wrong arg type
289 self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args
290
291 d = deque()
292 d.rotate() # rotate an empty deque
293 self.assertEqual(d, deque())
294
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000295 def test_len(self):
296 d = deque('ab')
297 self.assertEqual(len(d), 2)
298 d.popleft()
299 self.assertEqual(len(d), 1)
300 d.pop()
301 self.assertEqual(len(d), 0)
Raymond Hettinger738ec902004-02-29 02:15:56 +0000302 self.assertRaises(IndexError, d.pop)
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000303 self.assertEqual(len(d), 0)
304 d.append('c')
305 self.assertEqual(len(d), 1)
306 d.appendleft('d')
307 self.assertEqual(len(d), 2)
308 d.clear()
309 self.assertEqual(len(d), 0)
310
311 def test_underflow(self):
312 d = deque()
Raymond Hettinger738ec902004-02-29 02:15:56 +0000313 self.assertRaises(IndexError, d.pop)
314 self.assertRaises(IndexError, d.popleft)
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000315
316 def test_clear(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000317 d = deque(range(100))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000318 self.assertEqual(len(d), 100)
319 d.clear()
320 self.assertEqual(len(d), 0)
321 self.assertEqual(list(d), [])
Raymond Hettingera435c532004-07-09 04:10:20 +0000322 d.clear() # clear an emtpy deque
323 self.assertEqual(list(d), [])
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000324
Raymond Hettinger4aec61e2005-03-18 21:20:23 +0000325 def test_remove(self):
326 d = deque('abcdefghcij')
327 d.remove('c')
328 self.assertEqual(d, deque('abdefghcij'))
329 d.remove('c')
330 self.assertEqual(d, deque('abdefghij'))
331 self.assertRaises(ValueError, d.remove, 'c')
332 self.assertEqual(d, deque('abdefghij'))
333
Walter Dörwaldc448a912005-03-22 11:22:38 +0000334 # Handle comparison errors
Raymond Hettinger4aec61e2005-03-18 21:20:23 +0000335 d = deque(['a', 'b', BadCmp(), 'c'])
336 e = deque(d)
337 self.assertRaises(RuntimeError, d.remove, 'c')
338 for x, y in zip(d, e):
339 # verify that original order and values are retained.
Benjamin Petersonc9c0f202009-06-30 23:06:06 +0000340 self.assertTrue(x is y)
Raymond Hettinger4aec61e2005-03-18 21:20:23 +0000341
342 # Handle evil mutator
Raymond Hettingerd73202c2005-03-19 00:00:51 +0000343 for match in (True, False):
344 d = deque(['ab'])
345 d.extend([MutateCmp(d, match), 'c'])
346 self.assertRaises(IndexError, d.remove, 'c')
347 self.assertEqual(d, deque())
Raymond Hettinger4aec61e2005-03-18 21:20:23 +0000348
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000349 def test_repr(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000350 d = deque(range(200))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000351 e = eval(repr(d))
352 self.assertEqual(list(d), list(e))
353 d.append(d)
Benjamin Peterson577473f2010-01-19 00:09:57 +0000354 self.assertIn('...', repr(d))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000355
356 def test_print(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000357 d = deque(range(200))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000358 d.append(d)
Raymond Hettingera435c532004-07-09 04:10:20 +0000359 try:
Benjamin Petersonee8712c2008-05-20 21:35:26 +0000360 support.unlink(support.TESTFN)
361 fo = open(support.TESTFN, "w")
Christian Heimescc47b052008-03-25 14:56:36 +0000362 print(d, file=fo, end='')
Raymond Hettingera435c532004-07-09 04:10:20 +0000363 fo.close()
Benjamin Petersonee8712c2008-05-20 21:35:26 +0000364 fo = open(support.TESTFN, "r")
Raymond Hettingera435c532004-07-09 04:10:20 +0000365 self.assertEqual(fo.read(), repr(d))
366 finally:
367 fo.close()
Benjamin Petersonee8712c2008-05-20 21:35:26 +0000368 support.unlink(support.TESTFN)
Raymond Hettingera435c532004-07-09 04:10:20 +0000369
370 def test_init(self):
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000371 self.assertRaises(TypeError, deque, 'abc', 2, 3);
Raymond Hettingera435c532004-07-09 04:10:20 +0000372 self.assertRaises(TypeError, deque, 1);
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000373
374 def test_hash(self):
375 self.assertRaises(TypeError, hash, deque('abc'))
376
377 def test_long_steadystate_queue_popleft(self):
378 for size in (0, 1, 2, 100, 1000):
Guido van Rossum805365e2007-05-07 22:24:25 +0000379 d = deque(range(size))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000380 append, pop = d.append, d.popleft
Guido van Rossum805365e2007-05-07 22:24:25 +0000381 for i in range(size, BIG):
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000382 append(i)
383 x = pop()
384 if x != i - size:
385 self.assertEqual(x, i-size)
Guido van Rossum805365e2007-05-07 22:24:25 +0000386 self.assertEqual(list(d), list(range(BIG-size, BIG)))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000387
388 def test_long_steadystate_queue_popright(self):
389 for size in (0, 1, 2, 100, 1000):
Guido van Rossum805365e2007-05-07 22:24:25 +0000390 d = deque(reversed(range(size)))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000391 append, pop = d.appendleft, d.pop
Guido van Rossum805365e2007-05-07 22:24:25 +0000392 for i in range(size, BIG):
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000393 append(i)
394 x = pop()
395 if x != i - size:
396 self.assertEqual(x, i-size)
Guido van Rossum805365e2007-05-07 22:24:25 +0000397 self.assertEqual(list(reversed(list(d))),
398 list(range(BIG-size, BIG)))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000399
400 def test_big_queue_popleft(self):
401 pass
402 d = deque()
403 append, pop = d.append, d.popleft
Guido van Rossum805365e2007-05-07 22:24:25 +0000404 for i in range(BIG):
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000405 append(i)
Guido van Rossum805365e2007-05-07 22:24:25 +0000406 for i in range(BIG):
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000407 x = pop()
408 if x != i:
409 self.assertEqual(x, i)
410
411 def test_big_queue_popright(self):
412 d = deque()
413 append, pop = d.appendleft, d.pop
Guido van Rossum805365e2007-05-07 22:24:25 +0000414 for i in range(BIG):
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000415 append(i)
Guido van Rossum805365e2007-05-07 22:24:25 +0000416 for i in range(BIG):
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000417 x = pop()
418 if x != i:
419 self.assertEqual(x, i)
420
421 def test_big_stack_right(self):
422 d = deque()
423 append, pop = d.append, d.pop
Guido van Rossum805365e2007-05-07 22:24:25 +0000424 for i in range(BIG):
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000425 append(i)
Guido van Rossum805365e2007-05-07 22:24:25 +0000426 for i in reversed(range(BIG)):
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000427 x = pop()
428 if x != i:
429 self.assertEqual(x, i)
430 self.assertEqual(len(d), 0)
431
432 def test_big_stack_left(self):
433 d = deque()
434 append, pop = d.appendleft, d.popleft
Guido van Rossum805365e2007-05-07 22:24:25 +0000435 for i in range(BIG):
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000436 append(i)
Guido van Rossum805365e2007-05-07 22:24:25 +0000437 for i in reversed(range(BIG)):
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000438 x = pop()
439 if x != i:
440 self.assertEqual(x, i)
441 self.assertEqual(len(d), 0)
442
443 def test_roundtrip_iter_init(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000444 d = deque(range(200))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000445 e = deque(d)
446 self.assertNotEqual(id(d), id(e))
447 self.assertEqual(list(d), list(e))
448
449 def test_pickle(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000450 d = deque(range(200))
Hirokazu Yamamoto801f9d32008-12-27 04:21:44 +0000451 for i in range(pickle.HIGHEST_PROTOCOL + 1):
Raymond Hettinger952f8802004-11-09 07:27:35 +0000452 s = pickle.dumps(d, i)
453 e = pickle.loads(s)
454 self.assertNotEqual(id(d), id(e))
455 self.assertEqual(list(d), list(e))
456
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000457## def test_pickle_recursive(self):
458## d = deque('abc')
459## d.append(d)
Hirokazu Yamamoto801f9d32008-12-27 04:21:44 +0000460## for i in range(pickle.HIGHEST_PROTOCOL + 1):
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000461## e = pickle.loads(pickle.dumps(d, i))
462## self.assertNotEqual(id(d), id(e))
463## self.assertEqual(id(e), id(e[-1]))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000464
465 def test_deepcopy(self):
466 mut = [10]
467 d = deque([mut])
468 e = copy.deepcopy(d)
469 self.assertEqual(list(d), list(e))
470 mut[0] = 11
471 self.assertNotEqual(id(d), id(e))
472 self.assertNotEqual(list(d), list(e))
473
474 def test_copy(self):
475 mut = [10]
476 d = deque([mut])
477 e = copy.copy(d)
478 self.assertEqual(list(d), list(e))
479 mut[0] = 11
480 self.assertNotEqual(id(d), id(e))
481 self.assertEqual(list(d), list(e))
482
Raymond Hettingerc058fd12004-02-07 02:45:22 +0000483 def test_reversed(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000484 for s in ('abcd', range(2000)):
Raymond Hettingerc058fd12004-02-07 02:45:22 +0000485 self.assertEqual(list(reversed(deque(s))), list(reversed(s)))
486
Tim Peters10c7e862004-10-01 02:01:04 +0000487 def test_gc_doesnt_blowup(self):
488 import gc
489 # This used to assert-fail in deque_traverse() under a debug
490 # build, or run wild with a NULL pointer in a release build.
491 d = deque()
Guido van Rossum805365e2007-05-07 22:24:25 +0000492 for i in range(100):
Tim Peters10c7e862004-10-01 02:01:04 +0000493 d.append(1)
494 gc.collect()
495
Antoine Pitrou7ddda782009-01-01 15:35:33 +0000496 def test_container_iterator(self):
497 # Bug #3680: tp_traverse was not implemented for deque iterator objects
498 class C(object):
499 pass
500 for i in range(2):
501 obj = C()
502 ref = weakref.ref(obj)
503 if i == 0:
504 container = deque([obj, 1])
505 else:
506 container = reversed(deque([obj, 1]))
507 obj.x = iter(container)
508 del obj, container
509 gc.collect()
Benjamin Petersonc9c0f202009-06-30 23:06:06 +0000510 self.assertTrue(ref() is None, "Cycle was not collected")
Antoine Pitrou7ddda782009-01-01 15:35:33 +0000511
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000512class TestVariousIteratorArgs(unittest.TestCase):
513
514 def test_constructor(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000515 for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
Walter Dörwald09a3f2c2005-03-22 22:43:28 +0000516 for g in (seq_tests.Sequence, seq_tests.IterFunc,
517 seq_tests.IterGen, seq_tests.IterFuncStop,
518 seq_tests.itermulti, seq_tests.iterfunc):
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000519 self.assertEqual(list(deque(g(s))), list(g(s)))
Walter Dörwald09a3f2c2005-03-22 22:43:28 +0000520 self.assertRaises(TypeError, deque, seq_tests.IterNextOnly(s))
521 self.assertRaises(TypeError, deque, seq_tests.IterNoNext(s))
522 self.assertRaises(ZeroDivisionError, deque, seq_tests.IterGenExc(s))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000523
524 def test_iter_with_altered_data(self):
525 d = deque('abcdefg')
526 it = iter(d)
527 d.pop()
Georg Brandla18af4e2007-04-21 15:47:16 +0000528 self.assertRaises(RuntimeError, next, it)
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000529
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000530 def test_runtime_error_on_empty_deque(self):
531 d = deque()
532 it = iter(d)
533 d.append(10)
Georg Brandla18af4e2007-04-21 15:47:16 +0000534 self.assertRaises(RuntimeError, next, it)
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000535
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000536class Deque(deque):
537 pass
538
Raymond Hettinger952f8802004-11-09 07:27:35 +0000539class DequeWithBadIter(deque):
540 def __iter__(self):
541 raise TypeError
542
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000543class TestSubclass(unittest.TestCase):
544
545 def test_basics(self):
Christian Heimes38053212007-12-14 01:24:44 +0000546 d = Deque(range(25))
547 d.__init__(range(200))
Guido van Rossum805365e2007-05-07 22:24:25 +0000548 for i in range(200, 400):
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000549 d.append(i)
Guido van Rossum805365e2007-05-07 22:24:25 +0000550 for i in reversed(range(-200, 0)):
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000551 d.appendleft(i)
Guido van Rossum805365e2007-05-07 22:24:25 +0000552 self.assertEqual(list(d), list(range(-200, 400)))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000553 self.assertEqual(len(d), 600)
554
Guido van Rossum805365e2007-05-07 22:24:25 +0000555 left = [d.popleft() for i in range(250)]
556 self.assertEqual(left, list(range(-200, 50)))
557 self.assertEqual(list(d), list(range(50, 400)))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000558
Guido van Rossum805365e2007-05-07 22:24:25 +0000559 right = [d.pop() for i in range(250)]
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000560 right.reverse()
Guido van Rossum805365e2007-05-07 22:24:25 +0000561 self.assertEqual(right, list(range(150, 400)))
562 self.assertEqual(list(d), list(range(50, 150)))
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000563
564 d.clear()
565 self.assertEqual(len(d), 0)
566
567 def test_copy_pickle(self):
568
569 d = Deque('abc')
570
571 e = d.__copy__()
572 self.assertEqual(type(d), type(e))
573 self.assertEqual(list(d), list(e))
574
575 e = Deque(d)
576 self.assertEqual(type(d), type(e))
577 self.assertEqual(list(d), list(e))
578
579 s = pickle.dumps(d)
580 e = pickle.loads(s)
581 self.assertNotEqual(id(d), id(e))
582 self.assertEqual(type(d), type(e))
583 self.assertEqual(list(d), list(e))
584
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000585 d = Deque('abcde', maxlen=4)
Raymond Hettinger952f8802004-11-09 07:27:35 +0000586
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000587 e = d.__copy__()
588 self.assertEqual(type(d), type(e))
589 self.assertEqual(list(d), list(e))
590
591 e = Deque(d)
592 self.assertEqual(type(d), type(e))
593 self.assertEqual(list(d), list(e))
594
595 s = pickle.dumps(d)
596 e = pickle.loads(s)
Raymond Hettinger952f8802004-11-09 07:27:35 +0000597 self.assertNotEqual(id(d), id(e))
598 self.assertEqual(type(d), type(e))
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000599 self.assertEqual(list(d), list(e))
Raymond Hettinger952f8802004-11-09 07:27:35 +0000600
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000601## def test_pickle(self):
602## d = Deque('abc')
603## d.append(d)
604##
605## e = pickle.loads(pickle.dumps(d))
606## self.assertNotEqual(id(d), id(e))
607## self.assertEqual(type(d), type(e))
608## dd = d.pop()
609## ee = e.pop()
610## self.assertEqual(id(e), id(ee))
611## self.assertEqual(d, e)
612##
613## d.x = d
614## e = pickle.loads(pickle.dumps(d))
615## self.assertEqual(id(e), id(e.x))
616##
617## d = DequeWithBadIter('abc')
618## self.assertRaises(TypeError, pickle.dumps, d)
Raymond Hettinger952f8802004-11-09 07:27:35 +0000619
Raymond Hettinger691d8052004-05-30 07:26:47 +0000620 def test_weakref(self):
621 d = deque('gallahad')
Antoine Pitrou7ddda782009-01-01 15:35:33 +0000622 p = weakref.proxy(d)
Raymond Hettinger691d8052004-05-30 07:26:47 +0000623 self.assertEqual(str(p), str(d))
624 d = None
625 self.assertRaises(ReferenceError, str, p)
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000626
Armin Rigo974d7572004-10-02 13:59:34 +0000627 def test_strange_subclass(self):
628 class X(deque):
629 def __iter__(self):
630 return iter([])
631 d1 = X([1,2,3])
632 d2 = X([4,5,6])
633 d1 == d2 # not clear if this is supposed to be True or False,
634 # but it used to give a SystemError
635
Thomas Woutersb2137042007-02-01 18:02:27 +0000636
637class SubclassWithKwargs(deque):
638 def __init__(self, newarg=1):
639 deque.__init__(self)
640
641class TestSubclassWithKwargs(unittest.TestCase):
642 def test_subclass_with_kwargs(self):
643 # SF bug #1486663 -- this used to erroneously raise a TypeError
644 SubclassWithKwargs(newarg=1)
645
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000646#==============================================================================
647
Raymond Hettinger738ec902004-02-29 02:15:56 +0000648libreftest = """
649Example from the Library Reference: Doc/lib/libcollections.tex
650
651>>> from collections import deque
652>>> d = deque('ghi') # make a new deque with three items
653>>> for elem in d: # iterate over the deque's elements
Guido van Rossum7131f842007-02-09 20:13:25 +0000654... print(elem.upper())
Raymond Hettinger738ec902004-02-29 02:15:56 +0000655G
656H
657I
658>>> d.append('j') # add a new entry to the right side
659>>> d.appendleft('f') # add a new entry to the left side
660>>> d # show the representation of the deque
661deque(['f', 'g', 'h', 'i', 'j'])
662>>> d.pop() # return and remove the rightmost item
663'j'
664>>> d.popleft() # return and remove the leftmost item
665'f'
666>>> list(d) # list the contents of the deque
667['g', 'h', 'i']
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000668>>> d[0] # peek at leftmost item
Raymond Hettinger738ec902004-02-29 02:15:56 +0000669'g'
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000670>>> d[-1] # peek at rightmost item
Raymond Hettinger738ec902004-02-29 02:15:56 +0000671'i'
672>>> list(reversed(d)) # list the contents of a deque in reverse
673['i', 'h', 'g']
674>>> 'h' in d # search the deque
675True
676>>> d.extend('jkl') # add multiple elements at once
677>>> d
678deque(['g', 'h', 'i', 'j', 'k', 'l'])
679>>> d.rotate(1) # right rotation
680>>> d
681deque(['l', 'g', 'h', 'i', 'j', 'k'])
682>>> d.rotate(-1) # left rotation
683>>> d
684deque(['g', 'h', 'i', 'j', 'k', 'l'])
685>>> deque(reversed(d)) # make a new deque in reverse order
686deque(['l', 'k', 'j', 'i', 'h', 'g'])
687>>> d.clear() # empty the deque
688>>> d.pop() # cannot pop from an empty deque
689Traceback (most recent call last):
690 File "<pyshell#6>", line 1, in -toplevel-
691 d.pop()
692IndexError: pop from an empty deque
693
694>>> d.extendleft('abc') # extendleft() reverses the input order
695>>> d
696deque(['c', 'b', 'a'])
697
Raymond Hettingere7169eb2004-05-09 01:15:01 +0000698
699
Raymond Hettingere7169eb2004-05-09 01:15:01 +0000700>>> def delete_nth(d, n):
Raymond Hettingere7169eb2004-05-09 01:15:01 +0000701... d.rotate(-n)
702... d.popleft()
703... d.rotate(n)
704...
705>>> d = deque('abcdef')
706>>> delete_nth(d, 2) # remove the entry at d[2]
707>>> d
708deque(['a', 'b', 'd', 'e', 'f'])
709
710
711
712>>> def roundrobin(*iterables):
713... pending = deque(iter(i) for i in iterables)
714... while pending:
715... task = pending.popleft()
716... try:
Georg Brandla18af4e2007-04-21 15:47:16 +0000717... yield next(task)
Raymond Hettingere7169eb2004-05-09 01:15:01 +0000718... except StopIteration:
719... continue
720... pending.append(task)
721...
722
723>>> for value in roundrobin('abc', 'd', 'efgh'):
Guido van Rossum7131f842007-02-09 20:13:25 +0000724... print(value)
Guido van Rossumd8faa362007-04-27 19:54:29 +0000725...
Raymond Hettingere7169eb2004-05-09 01:15:01 +0000726a
727d
728e
729b
730f
731c
732g
733h
734
735
736>>> def maketree(iterable):
737... d = deque(iterable)
738... while len(d) > 1:
739... pair = [d.popleft(), d.popleft()]
740... d.append(pair)
741... return list(d)
742...
Guido van Rossum7131f842007-02-09 20:13:25 +0000743>>> print(maketree('abcdefgh'))
Raymond Hettingere7169eb2004-05-09 01:15:01 +0000744[[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]
745
Raymond Hettinger738ec902004-02-29 02:15:56 +0000746"""
747
748
749#==============================================================================
750
751__test__ = {'libreftest' : libreftest}
752
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000753def test_main(verbose=None):
754 import sys
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000755 test_classes = (
756 TestBasic,
757 TestVariousIteratorArgs,
758 TestSubclass,
Thomas Woutersb2137042007-02-01 18:02:27 +0000759 TestSubclassWithKwargs,
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000760 )
761
Benjamin Petersonee8712c2008-05-20 21:35:26 +0000762 support.run_unittest(*test_classes)
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000763
764 # verify reference counting
765 if verbose and hasattr(sys, "gettotalrefcount"):
766 import gc
767 counts = [None] * 5
Guido van Rossum805365e2007-05-07 22:24:25 +0000768 for i in range(len(counts)):
Benjamin Petersonee8712c2008-05-20 21:35:26 +0000769 support.run_unittest(*test_classes)
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000770 gc.collect()
771 counts[i] = sys.gettotalrefcount()
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000772 print(counts)
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000773
Raymond Hettinger738ec902004-02-29 02:15:56 +0000774 # doctests
775 from test import test_deque
Benjamin Petersonee8712c2008-05-20 21:35:26 +0000776 support.run_doctest(test_deque, verbose)
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000777
778if __name__ == "__main__":
779 test_main(verbose=True)