1 from collections import deque
2 import doctest
3 import unittest
4 from test import support, seq_tests
5 import gc
6 import weakref
7 import copy
8 import pickle
9 import random
10 import struct
11
12 BIG = 100000
13
14 def fail():
15 raise SyntaxError
16 yield 1
17
18 class ESC[4;38;5;81mBadCmp:
19 def __eq__(self, other):
20 raise RuntimeError
21
22 class ESC[4;38;5;81mMutateCmp:
23 def __init__(self, deque, result):
24 self.deque = deque
25 self.result = result
26 def __eq__(self, other):
27 self.deque.clear()
28 return self.result
29
30 class ESC[4;38;5;81mTestBasic(ESC[4;38;5;149munittestESC[4;38;5;149m.ESC[4;38;5;149mTestCase):
31
32 def test_basics(self):
33 d = deque(range(-5125, -5000))
34 d.__init__(range(200))
35 for i in range(200, 400):
36 d.append(i)
37 for i in reversed(range(-200, 0)):
38 d.appendleft(i)
39 self.assertEqual(list(d), list(range(-200, 400)))
40 self.assertEqual(len(d), 600)
41
42 left = [d.popleft() for i in range(250)]
43 self.assertEqual(left, list(range(-200, 50)))
44 self.assertEqual(list(d), list(range(50, 400)))
45
46 right = [d.pop() for i in range(250)]
47 right.reverse()
48 self.assertEqual(right, list(range(150, 400)))
49 self.assertEqual(list(d), list(range(50, 150)))
50
51 def test_maxlen(self):
52 self.assertRaises(ValueError, deque, 'abc', -1)
53 self.assertRaises(ValueError, deque, 'abc', -2)
54 it = iter(range(10))
55 d = deque(it, maxlen=3)
56 self.assertEqual(list(it), [])
57 self.assertEqual(repr(d), 'deque([7, 8, 9], maxlen=3)')
58 self.assertEqual(list(d), [7, 8, 9])
59 self.assertEqual(d, deque(range(10), 3))
60 d.append(10)
61 self.assertEqual(list(d), [8, 9, 10])
62 d.appendleft(7)
63 self.assertEqual(list(d), [7, 8, 9])
64 d.extend([10, 11])
65 self.assertEqual(list(d), [9, 10, 11])
66 d.extendleft([8, 7])
67 self.assertEqual(list(d), [7, 8, 9])
68 d = deque(range(200), maxlen=10)
69 d.append(d)
70 self.assertEqual(repr(d)[-30:], ', 198, 199, [...]], maxlen=10)')
71 d = deque(range(10), maxlen=None)
72 self.assertEqual(repr(d), 'deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])')
73
74 def test_maxlen_zero(self):
75 it = iter(range(100))
76 deque(it, maxlen=0)
77 self.assertEqual(list(it), [])
78
79 it = iter(range(100))
80 d = deque(maxlen=0)
81 d.extend(it)
82 self.assertEqual(list(it), [])
83
84 it = iter(range(100))
85 d = deque(maxlen=0)
86 d.extendleft(it)
87 self.assertEqual(list(it), [])
88
89 def test_maxlen_attribute(self):
90 self.assertEqual(deque().maxlen, None)
91 self.assertEqual(deque('abc').maxlen, None)
92 self.assertEqual(deque('abc', maxlen=4).maxlen, 4)
93 self.assertEqual(deque('abc', maxlen=2).maxlen, 2)
94 self.assertEqual(deque('abc', maxlen=0).maxlen, 0)
95 with self.assertRaises(AttributeError):
96 d = deque('abc')
97 d.maxlen = 10
98
99 def test_count(self):
100 for s in ('', 'abracadabra', 'simsalabim'*500+'abc'):
101 s = list(s)
102 d = deque(s)
103 for letter in 'abcdefghijklmnopqrstuvwxyz':
104 self.assertEqual(s.count(letter), d.count(letter), (s, d, letter))
105 self.assertRaises(TypeError, d.count) # too few args
106 self.assertRaises(TypeError, d.count, 1, 2) # too many args
107 class ESC[4;38;5;81mBadCompare:
108 def __eq__(self, other):
109 raise ArithmeticError
110 d = deque([1, 2, BadCompare(), 3])
111 self.assertRaises(ArithmeticError, d.count, 2)
112 d = deque([1, 2, 3])
113 self.assertRaises(ArithmeticError, d.count, BadCompare())
114 class ESC[4;38;5;81mMutatingCompare:
115 def __eq__(self, other):
116 self.d.pop()
117 return True
118 m = MutatingCompare()
119 d = deque([1, 2, 3, m, 4, 5])
120 m.d = d
121 self.assertRaises(RuntimeError, d.count, 3)
122
123 # test issue11004
124 # block advance failed after rotation aligned elements on right side of block
125 d = deque([None]*16)
126 for i in range(len(d)):
127 d.rotate(-1)
128 d.rotate(1)
129 self.assertEqual(d.count(1), 0)
130 self.assertEqual(d.count(None), 16)
131
132 def test_comparisons(self):
133 d = deque('xabc')
134 d.popleft()
135 for e in [d, deque('abc'), deque('ab'), deque(), list(d)]:
136 self.assertEqual(d==e, type(d)==type(e) and list(d)==list(e))
137 self.assertEqual(d!=e, not(type(d)==type(e) and list(d)==list(e)))
138
139 args = map(deque, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba'))
140 for x in args:
141 for y in args:
142 self.assertEqual(x == y, list(x) == list(y), (x,y))
143 self.assertEqual(x != y, list(x) != list(y), (x,y))
144 self.assertEqual(x < y, list(x) < list(y), (x,y))
145 self.assertEqual(x <= y, list(x) <= list(y), (x,y))
146 self.assertEqual(x > y, list(x) > list(y), (x,y))
147 self.assertEqual(x >= y, list(x) >= list(y), (x,y))
148
149 def test_contains(self):
150 n = 200
151
152 d = deque(range(n))
153 for i in range(n):
154 self.assertTrue(i in d)
155 self.assertTrue((n+1) not in d)
156
157 # Test detection of mutation during iteration
158 d = deque(range(n))
159 d[n//2] = MutateCmp(d, False)
160 with self.assertRaises(RuntimeError):
161 n in d
162
163 # Test detection of comparison exceptions
164 d = deque(range(n))
165 d[n//2] = BadCmp()
166 with self.assertRaises(RuntimeError):
167 n in d
168
169 def test_contains_count_stop_crashes(self):
170 class ESC[4;38;5;81mA:
171 def __eq__(self, other):
172 d.clear()
173 return NotImplemented
174 d = deque([A(), A()])
175 with self.assertRaises(RuntimeError):
176 _ = 3 in d
177 d = deque([A(), A()])
178 with self.assertRaises(RuntimeError):
179 _ = d.count(3)
180
181 def test_extend(self):
182 d = deque('a')
183 self.assertRaises(TypeError, d.extend, 1)
184 d.extend('bcd')
185 self.assertEqual(list(d), list('abcd'))
186 d.extend(d)
187 self.assertEqual(list(d), list('abcdabcd'))
188
189 def test_add(self):
190 d = deque()
191 e = deque('abc')
192 f = deque('def')
193 self.assertEqual(d + d, deque())
194 self.assertEqual(e + f, deque('abcdef'))
195 self.assertEqual(e + e, deque('abcabc'))
196 self.assertEqual(e + d, deque('abc'))
197 self.assertEqual(d + e, deque('abc'))
198 self.assertIsNot(d + d, deque())
199 self.assertIsNot(e + d, deque('abc'))
200 self.assertIsNot(d + e, deque('abc'))
201
202 g = deque('abcdef', maxlen=4)
203 h = deque('gh')
204 self.assertEqual(g + h, deque('efgh'))
205
206 with self.assertRaises(TypeError):
207 deque('abc') + 'def'
208
209 def test_iadd(self):
210 d = deque('a')
211 d += 'bcd'
212 self.assertEqual(list(d), list('abcd'))
213 d += d
214 self.assertEqual(list(d), list('abcdabcd'))
215
216 def test_extendleft(self):
217 d = deque('a')
218 self.assertRaises(TypeError, d.extendleft, 1)
219 d.extendleft('bcd')
220 self.assertEqual(list(d), list(reversed('abcd')))
221 d.extendleft(d)
222 self.assertEqual(list(d), list('abcddcba'))
223 d = deque()
224 d.extendleft(range(1000))
225 self.assertEqual(list(d), list(reversed(range(1000))))
226 self.assertRaises(SyntaxError, d.extendleft, fail())
227
228 def test_getitem(self):
229 n = 200
230 d = deque(range(n))
231 l = list(range(n))
232 for i in range(n):
233 d.popleft()
234 l.pop(0)
235 if random.random() < 0.5:
236 d.append(i)
237 l.append(i)
238 for j in range(1-len(l), len(l)):
239 assert d[j] == l[j]
240
241 d = deque('superman')
242 self.assertEqual(d[0], 's')
243 self.assertEqual(d[-1], 'n')
244 d = deque()
245 self.assertRaises(IndexError, d.__getitem__, 0)
246 self.assertRaises(IndexError, d.__getitem__, -1)
247
248 def test_index(self):
249 for n in 1, 2, 30, 40, 200:
250
251 d = deque(range(n))
252 for i in range(n):
253 self.assertEqual(d.index(i), i)
254
255 with self.assertRaises(ValueError):
256 d.index(n+1)
257
258 # Test detection of mutation during iteration
259 d = deque(range(n))
260 d[n//2] = MutateCmp(d, False)
261 with self.assertRaises(RuntimeError):
262 d.index(n)
263
264 # Test detection of comparison exceptions
265 d = deque(range(n))
266 d[n//2] = BadCmp()
267 with self.assertRaises(RuntimeError):
268 d.index(n)
269
270 # Test start and stop arguments behavior matches list.index()
271 elements = 'ABCDEFGHI'
272 nonelement = 'Z'
273 d = deque(elements * 2)
274 s = list(elements * 2)
275 for start in range(-5 - len(s)*2, 5 + len(s) * 2):
276 for stop in range(-5 - len(s)*2, 5 + len(s) * 2):
277 for element in elements + 'Z':
278 try:
279 target = s.index(element, start, stop)
280 except ValueError:
281 with self.assertRaises(ValueError):
282 d.index(element, start, stop)
283 else:
284 self.assertEqual(d.index(element, start, stop), target)
285
286 # Test large start argument
287 d = deque(range(0, 10000, 10))
288 for step in range(100):
289 i = d.index(8500, 700)
290 self.assertEqual(d[i], 8500)
291 # Repeat test with a different internal offset
292 d.rotate()
293
294 def test_index_bug_24913(self):
295 d = deque('A' * 3)
296 with self.assertRaises(ValueError):
297 i = d.index("Hello world", 0, 4)
298
299 def test_insert(self):
300 # Test to make sure insert behaves like lists
301 elements = 'ABCDEFGHI'
302 for i in range(-5 - len(elements)*2, 5 + len(elements) * 2):
303 d = deque('ABCDEFGHI')
304 s = list('ABCDEFGHI')
305 d.insert(i, 'Z')
306 s.insert(i, 'Z')
307 self.assertEqual(list(d), s)
308
309 def test_insert_bug_26194(self):
310 data = 'ABC'
311 d = deque(data, maxlen=len(data))
312 with self.assertRaises(IndexError):
313 d.insert(2, None)
314
315 elements = 'ABCDEFGHI'
316 for i in range(-len(elements), len(elements)):
317 d = deque(elements, maxlen=len(elements)+1)
318 d.insert(i, 'Z')
319 if i >= 0:
320 self.assertEqual(d[i], 'Z')
321 else:
322 self.assertEqual(d[i-1], 'Z')
323
324 def test_imul(self):
325 for n in (-10, -1, 0, 1, 2, 10, 1000):
326 d = deque()
327 d *= n
328 self.assertEqual(d, deque())
329 self.assertIsNone(d.maxlen)
330
331 for n in (-10, -1, 0, 1, 2, 10, 1000):
332 d = deque('a')
333 d *= n
334 self.assertEqual(d, deque('a' * n))
335 self.assertIsNone(d.maxlen)
336
337 for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000):
338 d = deque('a', 500)
339 d *= n
340 self.assertEqual(d, deque('a' * min(n, 500)))
341 self.assertEqual(d.maxlen, 500)
342
343 for n in (-10, -1, 0, 1, 2, 10, 1000):
344 d = deque('abcdef')
345 d *= n
346 self.assertEqual(d, deque('abcdef' * n))
347 self.assertIsNone(d.maxlen)
348
349 for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000):
350 d = deque('abcdef', 500)
351 d *= n
352 self.assertEqual(d, deque(('abcdef' * n)[-500:]))
353 self.assertEqual(d.maxlen, 500)
354
355 def test_mul(self):
356 d = deque('abc')
357 self.assertEqual(d * -5, deque())
358 self.assertEqual(d * 0, deque())
359 self.assertEqual(d * 1, deque('abc'))
360 self.assertEqual(d * 2, deque('abcabc'))
361 self.assertEqual(d * 3, deque('abcabcabc'))
362 self.assertIsNot(d * 1, d)
363
364 self.assertEqual(deque() * 0, deque())
365 self.assertEqual(deque() * 1, deque())
366 self.assertEqual(deque() * 5, deque())
367
368 self.assertEqual(-5 * d, deque())
369 self.assertEqual(0 * d, deque())
370 self.assertEqual(1 * d, deque('abc'))
371 self.assertEqual(2 * d, deque('abcabc'))
372 self.assertEqual(3 * d, deque('abcabcabc'))
373
374 d = deque('abc', maxlen=5)
375 self.assertEqual(d * -5, deque())
376 self.assertEqual(d * 0, deque())
377 self.assertEqual(d * 1, deque('abc'))
378 self.assertEqual(d * 2, deque('bcabc'))
379 self.assertEqual(d * 30, deque('bcabc'))
380
381 def test_setitem(self):
382 n = 200
383 d = deque(range(n))
384 for i in range(n):
385 d[i] = 10 * i
386 self.assertEqual(list(d), [10*i for i in range(n)])
387 l = list(d)
388 for i in range(1-n, 0, -1):
389 d[i] = 7*i
390 l[i] = 7*i
391 self.assertEqual(list(d), l)
392
393 def test_delitem(self):
394 n = 500 # O(n**2) test, don't make this too big
395 d = deque(range(n))
396 self.assertRaises(IndexError, d.__delitem__, -n-1)
397 self.assertRaises(IndexError, d.__delitem__, n)
398 for i in range(n):
399 self.assertEqual(len(d), n-i)
400 j = random.randrange(-len(d), len(d))
401 val = d[j]
402 self.assertIn(val, d)
403 del d[j]
404 self.assertNotIn(val, d)
405 self.assertEqual(len(d), 0)
406
407 def test_reverse(self):
408 n = 500 # O(n**2) test, don't make this too big
409 data = [random.random() for i in range(n)]
410 for i in range(n):
411 d = deque(data[:i])
412 r = d.reverse()
413 self.assertEqual(list(d), list(reversed(data[:i])))
414 self.assertIs(r, None)
415 d.reverse()
416 self.assertEqual(list(d), data[:i])
417 self.assertRaises(TypeError, d.reverse, 1) # Arity is zero
418
419 def test_rotate(self):
420 s = tuple('abcde')
421 n = len(s)
422
423 d = deque(s)
424 d.rotate(1) # verify rot(1)
425 self.assertEqual(''.join(d), 'eabcd')
426
427 d = deque(s)
428 d.rotate(-1) # verify rot(-1)
429 self.assertEqual(''.join(d), 'bcdea')
430 d.rotate() # check default to 1
431 self.assertEqual(tuple(d), s)
432
433 for i in range(n*3):
434 d = deque(s)
435 e = deque(d)
436 d.rotate(i) # check vs. rot(1) n times
437 for j in range(i):
438 e.rotate(1)
439 self.assertEqual(tuple(d), tuple(e))
440 d.rotate(-i) # check that it works in reverse
441 self.assertEqual(tuple(d), s)
442 e.rotate(n-i) # check that it wraps forward
443 self.assertEqual(tuple(e), s)
444
445 for i in range(n*3):
446 d = deque(s)
447 e = deque(d)
448 d.rotate(-i)
449 for j in range(i):
450 e.rotate(-1) # check vs. rot(-1) n times
451 self.assertEqual(tuple(d), tuple(e))
452 d.rotate(i) # check that it works in reverse
453 self.assertEqual(tuple(d), s)
454 e.rotate(i-n) # check that it wraps backaround
455 self.assertEqual(tuple(e), s)
456
457 d = deque(s)
458 e = deque(s)
459 e.rotate(BIG+17) # verify on long series of rotates
460 dr = d.rotate
461 for i in range(BIG+17):
462 dr()
463 self.assertEqual(tuple(d), tuple(e))
464
465 self.assertRaises(TypeError, d.rotate, 'x') # Wrong arg type
466 self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args
467
468 d = deque()
469 d.rotate() # rotate an empty deque
470 self.assertEqual(d, deque())
471
472 def test_len(self):
473 d = deque('ab')
474 self.assertEqual(len(d), 2)
475 d.popleft()
476 self.assertEqual(len(d), 1)
477 d.pop()
478 self.assertEqual(len(d), 0)
479 self.assertRaises(IndexError, d.pop)
480 self.assertEqual(len(d), 0)
481 d.append('c')
482 self.assertEqual(len(d), 1)
483 d.appendleft('d')
484 self.assertEqual(len(d), 2)
485 d.clear()
486 self.assertEqual(len(d), 0)
487
488 def test_underflow(self):
489 d = deque()
490 self.assertRaises(IndexError, d.pop)
491 self.assertRaises(IndexError, d.popleft)
492
493 def test_clear(self):
494 d = deque(range(100))
495 self.assertEqual(len(d), 100)
496 d.clear()
497 self.assertEqual(len(d), 0)
498 self.assertEqual(list(d), [])
499 d.clear() # clear an empty deque
500 self.assertEqual(list(d), [])
501
502 def test_remove(self):
503 d = deque('abcdefghcij')
504 d.remove('c')
505 self.assertEqual(d, deque('abdefghcij'))
506 d.remove('c')
507 self.assertEqual(d, deque('abdefghij'))
508 self.assertRaises(ValueError, d.remove, 'c')
509 self.assertEqual(d, deque('abdefghij'))
510
511 # Handle comparison errors
512 d = deque(['a', 'b', BadCmp(), 'c'])
513 e = deque(d)
514 self.assertRaises(RuntimeError, d.remove, 'c')
515 for x, y in zip(d, e):
516 # verify that original order and values are retained.
517 self.assertTrue(x is y)
518
519 # Handle evil mutator
520 for match in (True, False):
521 d = deque(['ab'])
522 d.extend([MutateCmp(d, match), 'c'])
523 self.assertRaises(IndexError, d.remove, 'c')
524 self.assertEqual(d, deque())
525
526 def test_repr(self):
527 d = deque(range(200))
528 e = eval(repr(d))
529 self.assertEqual(list(d), list(e))
530 d.append(d)
531 self.assertEqual(repr(d)[-20:], '7, 198, 199, [...]])')
532
533 def test_init(self):
534 self.assertRaises(TypeError, deque, 'abc', 2, 3)
535 self.assertRaises(TypeError, deque, 1)
536
537 def test_hash(self):
538 self.assertRaises(TypeError, hash, deque('abc'))
539
540 def test_long_steadystate_queue_popleft(self):
541 for size in (0, 1, 2, 100, 1000):
542 d = deque(range(size))
543 append, pop = d.append, d.popleft
544 for i in range(size, BIG):
545 append(i)
546 x = pop()
547 if x != i - size:
548 self.assertEqual(x, i-size)
549 self.assertEqual(list(d), list(range(BIG-size, BIG)))
550
551 def test_long_steadystate_queue_popright(self):
552 for size in (0, 1, 2, 100, 1000):
553 d = deque(reversed(range(size)))
554 append, pop = d.appendleft, d.pop
555 for i in range(size, BIG):
556 append(i)
557 x = pop()
558 if x != i - size:
559 self.assertEqual(x, i-size)
560 self.assertEqual(list(reversed(list(d))),
561 list(range(BIG-size, BIG)))
562
563 def test_big_queue_popleft(self):
564 pass
565 d = deque()
566 append, pop = d.append, d.popleft
567 for i in range(BIG):
568 append(i)
569 for i in range(BIG):
570 x = pop()
571 if x != i:
572 self.assertEqual(x, i)
573
574 def test_big_queue_popright(self):
575 d = deque()
576 append, pop = d.appendleft, d.pop
577 for i in range(BIG):
578 append(i)
579 for i in range(BIG):
580 x = pop()
581 if x != i:
582 self.assertEqual(x, i)
583
584 def test_big_stack_right(self):
585 d = deque()
586 append, pop = d.append, d.pop
587 for i in range(BIG):
588 append(i)
589 for i in reversed(range(BIG)):
590 x = pop()
591 if x != i:
592 self.assertEqual(x, i)
593 self.assertEqual(len(d), 0)
594
595 def test_big_stack_left(self):
596 d = deque()
597 append, pop = d.appendleft, d.popleft
598 for i in range(BIG):
599 append(i)
600 for i in reversed(range(BIG)):
601 x = pop()
602 if x != i:
603 self.assertEqual(x, i)
604 self.assertEqual(len(d), 0)
605
606 def test_roundtrip_iter_init(self):
607 d = deque(range(200))
608 e = deque(d)
609 self.assertNotEqual(id(d), id(e))
610 self.assertEqual(list(d), list(e))
611
612 def test_pickle(self):
613 for d in deque(range(200)), deque(range(200), 100):
614 for i in range(pickle.HIGHEST_PROTOCOL + 1):
615 s = pickle.dumps(d, i)
616 e = pickle.loads(s)
617 self.assertNotEqual(id(e), id(d))
618 self.assertEqual(list(e), list(d))
619 self.assertEqual(e.maxlen, d.maxlen)
620
621 def test_pickle_recursive(self):
622 for d in deque('abc'), deque('abc', 3):
623 d.append(d)
624 for i in range(pickle.HIGHEST_PROTOCOL + 1):
625 e = pickle.loads(pickle.dumps(d, i))
626 self.assertNotEqual(id(e), id(d))
627 self.assertEqual(id(e[-1]), id(e))
628 self.assertEqual(e.maxlen, d.maxlen)
629
630 def test_iterator_pickle(self):
631 orig = deque(range(200))
632 data = [i*1.01 for i in orig]
633 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
634 # initial iterator
635 itorg = iter(orig)
636 dump = pickle.dumps((itorg, orig), proto)
637 it, d = pickle.loads(dump)
638 for i, x in enumerate(data):
639 d[i] = x
640 self.assertEqual(type(it), type(itorg))
641 self.assertEqual(list(it), data)
642
643 # running iterator
644 next(itorg)
645 dump = pickle.dumps((itorg, orig), proto)
646 it, d = pickle.loads(dump)
647 for i, x in enumerate(data):
648 d[i] = x
649 self.assertEqual(type(it), type(itorg))
650 self.assertEqual(list(it), data[1:])
651
652 # empty iterator
653 for i in range(1, len(data)):
654 next(itorg)
655 dump = pickle.dumps((itorg, orig), proto)
656 it, d = pickle.loads(dump)
657 for i, x in enumerate(data):
658 d[i] = x
659 self.assertEqual(type(it), type(itorg))
660 self.assertEqual(list(it), [])
661
662 # exhausted iterator
663 self.assertRaises(StopIteration, next, itorg)
664 dump = pickle.dumps((itorg, orig), proto)
665 it, d = pickle.loads(dump)
666 for i, x in enumerate(data):
667 d[i] = x
668 self.assertEqual(type(it), type(itorg))
669 self.assertEqual(list(it), [])
670
671 def test_deepcopy(self):
672 mut = [10]
673 d = deque([mut])
674 e = copy.deepcopy(d)
675 self.assertEqual(list(d), list(e))
676 mut[0] = 11
677 self.assertNotEqual(id(d), id(e))
678 self.assertNotEqual(list(d), list(e))
679
680 def test_copy(self):
681 mut = [10]
682 d = deque([mut])
683 e = copy.copy(d)
684 self.assertEqual(list(d), list(e))
685 mut[0] = 11
686 self.assertNotEqual(id(d), id(e))
687 self.assertEqual(list(d), list(e))
688
689 for i in range(5):
690 for maxlen in range(-1, 6):
691 s = [random.random() for j in range(i)]
692 d = deque(s) if maxlen == -1 else deque(s, maxlen)
693 e = d.copy()
694 self.assertEqual(d, e)
695 self.assertEqual(d.maxlen, e.maxlen)
696 self.assertTrue(all(x is y for x, y in zip(d, e)))
697
698 def test_copy_method(self):
699 mut = [10]
700 d = deque([mut])
701 e = d.copy()
702 self.assertEqual(list(d), list(e))
703 mut[0] = 11
704 self.assertNotEqual(id(d), id(e))
705 self.assertEqual(list(d), list(e))
706
707 def test_reversed(self):
708 for s in ('abcd', range(2000)):
709 self.assertEqual(list(reversed(deque(s))), list(reversed(s)))
710
711 def test_reversed_new(self):
712 klass = type(reversed(deque()))
713 for s in ('abcd', range(2000)):
714 self.assertEqual(list(klass(deque(s))), list(reversed(s)))
715
716 def test_gc_doesnt_blowup(self):
717 import gc
718 # This used to assert-fail in deque_traverse() under a debug
719 # build, or run wild with a NULL pointer in a release build.
720 d = deque()
721 for i in range(100):
722 d.append(1)
723 gc.collect()
724
725 def test_container_iterator(self):
726 # Bug #3680: tp_traverse was not implemented for deque iterator objects
727 class ESC[4;38;5;81mC(ESC[4;38;5;149mobject):
728 pass
729 for i in range(2):
730 obj = C()
731 ref = weakref.ref(obj)
732 if i == 0:
733 container = deque([obj, 1])
734 else:
735 container = reversed(deque([obj, 1]))
736 obj.x = iter(container)
737 del obj, container
738 gc.collect()
739 self.assertTrue(ref() is None, "Cycle was not collected")
740
741 check_sizeof = support.check_sizeof
742
743 @support.cpython_only
744 def test_sizeof(self):
745 MAXFREEBLOCKS = 16
746 BLOCKLEN = 64
747 basesize = support.calcvobjsize('2P5n%dPP' % MAXFREEBLOCKS)
748 blocksize = struct.calcsize('P%dPP' % BLOCKLEN)
749 self.assertEqual(object.__sizeof__(deque()), basesize)
750 check = self.check_sizeof
751 check(deque(), basesize + blocksize)
752 check(deque('a'), basesize + blocksize)
753 check(deque('a' * (BLOCKLEN - 1)), basesize + blocksize)
754 check(deque('a' * BLOCKLEN), basesize + 2 * blocksize)
755 check(deque('a' * (42 * BLOCKLEN)), basesize + 43 * blocksize)
756
757 class ESC[4;38;5;81mTestVariousIteratorArgs(ESC[4;38;5;149munittestESC[4;38;5;149m.ESC[4;38;5;149mTestCase):
758
759 def test_constructor(self):
760 for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
761 for g in (seq_tests.Sequence, seq_tests.IterFunc,
762 seq_tests.IterGen, seq_tests.IterFuncStop,
763 seq_tests.itermulti, seq_tests.iterfunc):
764 self.assertEqual(list(deque(g(s))), list(g(s)))
765 self.assertRaises(TypeError, deque, seq_tests.IterNextOnly(s))
766 self.assertRaises(TypeError, deque, seq_tests.IterNoNext(s))
767 self.assertRaises(ZeroDivisionError, deque, seq_tests.IterGenExc(s))
768
769 def test_iter_with_altered_data(self):
770 d = deque('abcdefg')
771 it = iter(d)
772 d.pop()
773 self.assertRaises(RuntimeError, next, it)
774
775 def test_runtime_error_on_empty_deque(self):
776 d = deque()
777 it = iter(d)
778 d.append(10)
779 self.assertRaises(RuntimeError, next, it)
780
781 class ESC[4;38;5;81mDeque(ESC[4;38;5;149mdeque):
782 pass
783
784 class ESC[4;38;5;81mDequeWithSlots(ESC[4;38;5;149mdeque):
785 __slots__ = ('x', 'y', '__dict__')
786
787 class ESC[4;38;5;81mDequeWithBadIter(ESC[4;38;5;149mdeque):
788 def __iter__(self):
789 raise TypeError
790
791 class ESC[4;38;5;81mTestSubclass(ESC[4;38;5;149munittestESC[4;38;5;149m.ESC[4;38;5;149mTestCase):
792
793 def test_basics(self):
794 d = Deque(range(25))
795 d.__init__(range(200))
796 for i in range(200, 400):
797 d.append(i)
798 for i in reversed(range(-200, 0)):
799 d.appendleft(i)
800 self.assertEqual(list(d), list(range(-200, 400)))
801 self.assertEqual(len(d), 600)
802
803 left = [d.popleft() for i in range(250)]
804 self.assertEqual(left, list(range(-200, 50)))
805 self.assertEqual(list(d), list(range(50, 400)))
806
807 right = [d.pop() for i in range(250)]
808 right.reverse()
809 self.assertEqual(right, list(range(150, 400)))
810 self.assertEqual(list(d), list(range(50, 150)))
811
812 d.clear()
813 self.assertEqual(len(d), 0)
814
815 def test_copy_pickle(self):
816 for cls in Deque, DequeWithSlots:
817 for d in cls('abc'), cls('abcde', maxlen=4):
818 d.x = ['x']
819 d.z = ['z']
820
821 e = d.__copy__()
822 self.assertEqual(type(d), type(e))
823 self.assertEqual(list(d), list(e))
824
825 e = cls(d)
826 self.assertEqual(type(d), type(e))
827 self.assertEqual(list(d), list(e))
828
829 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
830 s = pickle.dumps(d, proto)
831 e = pickle.loads(s)
832 self.assertNotEqual(id(d), id(e))
833 self.assertEqual(type(d), type(e))
834 self.assertEqual(list(d), list(e))
835 self.assertEqual(e.x, d.x)
836 self.assertEqual(e.z, d.z)
837 self.assertFalse(hasattr(e, 'y'))
838
839 def test_pickle_recursive(self):
840 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
841 for d in Deque('abc'), Deque('abc', 3):
842 d.append(d)
843
844 e = pickle.loads(pickle.dumps(d, proto))
845 self.assertNotEqual(id(e), id(d))
846 self.assertEqual(type(e), type(d))
847 self.assertEqual(e.maxlen, d.maxlen)
848 dd = d.pop()
849 ee = e.pop()
850 self.assertEqual(id(ee), id(e))
851 self.assertEqual(e, d)
852
853 d.x = d
854 e = pickle.loads(pickle.dumps(d, proto))
855 self.assertEqual(id(e.x), id(e))
856
857 for d in DequeWithBadIter('abc'), DequeWithBadIter('abc', 2):
858 self.assertRaises(TypeError, pickle.dumps, d, proto)
859
860 def test_weakref(self):
861 d = deque('gallahad')
862 p = weakref.proxy(d)
863 self.assertEqual(str(p), str(d))
864 d = None
865 support.gc_collect() # For PyPy or other GCs.
866 self.assertRaises(ReferenceError, str, p)
867
868 def test_strange_subclass(self):
869 class ESC[4;38;5;81mX(ESC[4;38;5;149mdeque):
870 def __iter__(self):
871 return iter([])
872 d1 = X([1,2,3])
873 d2 = X([4,5,6])
874 d1 == d2 # not clear if this is supposed to be True or False,
875 # but it used to give a SystemError
876
877 @support.cpython_only
878 def test_bug_31608(self):
879 # The interpreter used to crash in specific cases where a deque
880 # subclass returned a non-deque.
881 class ESC[4;38;5;81mX(ESC[4;38;5;149mdeque):
882 pass
883 d = X()
884 def bad___new__(cls, *args, **kwargs):
885 return [42]
886 X.__new__ = bad___new__
887 with self.assertRaises(TypeError):
888 d * 42 # shouldn't crash
889 with self.assertRaises(TypeError):
890 d + deque([1, 2, 3]) # shouldn't crash
891
892
893 class ESC[4;38;5;81mSubclassWithKwargs(ESC[4;38;5;149mdeque):
894 def __init__(self, newarg=1):
895 deque.__init__(self)
896
897 class ESC[4;38;5;81mTestSubclassWithKwargs(ESC[4;38;5;149munittestESC[4;38;5;149m.ESC[4;38;5;149mTestCase):
898 def test_subclass_with_kwargs(self):
899 # SF bug #1486663 -- this used to erroneously raise a TypeError
900 SubclassWithKwargs(newarg=1)
901
902 class ESC[4;38;5;81mTestSequence(ESC[4;38;5;149mseq_testsESC[4;38;5;149m.ESC[4;38;5;149mCommonTest):
903 type2test = deque
904
905 def test_getitem(self):
906 # For now, bypass tests that require slicing
907 pass
908
909 def test_getslice(self):
910 # For now, bypass tests that require slicing
911 pass
912
913 def test_subscript(self):
914 # For now, bypass tests that require slicing
915 pass
916
917 def test_free_after_iterating(self):
918 # For now, bypass tests that require slicing
919 self.skipTest("Exhausted deque iterator doesn't free a deque")
920
921 #==============================================================================
922
923 libreftest = """
924 Example from the Library Reference: Doc/lib/libcollections.tex
925
926 >>> from collections import deque
927 >>> d = deque('ghi') # make a new deque with three items
928 >>> for elem in d: # iterate over the deque's elements
929 ... print(elem.upper())
930 G
931 H
932 I
933 >>> d.append('j') # add a new entry to the right side
934 >>> d.appendleft('f') # add a new entry to the left side
935 >>> d # show the representation of the deque
936 deque(['f', 'g', 'h', 'i', 'j'])
937 >>> d.pop() # return and remove the rightmost item
938 'j'
939 >>> d.popleft() # return and remove the leftmost item
940 'f'
941 >>> list(d) # list the contents of the deque
942 ['g', 'h', 'i']
943 >>> d[0] # peek at leftmost item
944 'g'
945 >>> d[-1] # peek at rightmost item
946 'i'
947 >>> list(reversed(d)) # list the contents of a deque in reverse
948 ['i', 'h', 'g']
949 >>> 'h' in d # search the deque
950 True
951 >>> d.extend('jkl') # add multiple elements at once
952 >>> d
953 deque(['g', 'h', 'i', 'j', 'k', 'l'])
954 >>> d.rotate(1) # right rotation
955 >>> d
956 deque(['l', 'g', 'h', 'i', 'j', 'k'])
957 >>> d.rotate(-1) # left rotation
958 >>> d
959 deque(['g', 'h', 'i', 'j', 'k', 'l'])
960 >>> deque(reversed(d)) # make a new deque in reverse order
961 deque(['l', 'k', 'j', 'i', 'h', 'g'])
962 >>> d.clear() # empty the deque
963 >>> d.pop() # cannot pop from an empty deque
964 Traceback (most recent call last):
965 File "<pyshell#6>", line 1, in -toplevel-
966 d.pop()
967 IndexError: pop from an empty deque
968
969 >>> d.extendleft('abc') # extendleft() reverses the input order
970 >>> d
971 deque(['c', 'b', 'a'])
972
973
974
975 >>> def delete_nth(d, n):
976 ... d.rotate(-n)
977 ... d.popleft()
978 ... d.rotate(n)
979 ...
980 >>> d = deque('abcdef')
981 >>> delete_nth(d, 2) # remove the entry at d[2]
982 >>> d
983 deque(['a', 'b', 'd', 'e', 'f'])
984
985
986
987 >>> def roundrobin(*iterables):
988 ... pending = deque(iter(i) for i in iterables)
989 ... while pending:
990 ... task = pending.popleft()
991 ... try:
992 ... yield next(task)
993 ... except StopIteration:
994 ... continue
995 ... pending.append(task)
996 ...
997
998 >>> for value in roundrobin('abc', 'd', 'efgh'):
999 ... print(value)
1000 ...
1001 a
1002 d
1003 e
1004 b
1005 f
1006 c
1007 g
1008 h
1009
1010
1011 >>> def maketree(iterable):
1012 ... d = deque(iterable)
1013 ... while len(d) > 1:
1014 ... pair = [d.popleft(), d.popleft()]
1015 ... d.append(pair)
1016 ... return list(d)
1017 ...
1018 >>> print(maketree('abcdefgh'))
1019 [[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]
1020
1021 """
1022
1023
1024 #==============================================================================
1025
1026 __test__ = {'libreftest' : libreftest}
1027
1028 def load_tests(loader, tests, pattern):
1029 tests.addTest(doctest.DocTestSuite())
1030 return tests
1031
1032
1033 if __name__ == "__main__":
1034 unittest.main()