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