Debian Codegraph @

Lib/test/test_deque.py

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