1from collections import deque
2import unittest
3from test import support, seq_tests
4import gc
5import weakref
6import copy
7import pickle
8from io import StringIO
9import random
10import struct
11
12BIG = 100000
13
14def fail():
15    raise SyntaxError
16    yield 1
17
18class BadCmp:
19    def __eq__(self, other):
20        raise RuntimeError
21
22class 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
30class 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        support.unlink(support.TESTFN)
71        fo = open(support.TESTFN, "w")
72        try:
73            fo.write(str(d))
74            fo.close()
75            fo = open(support.TESTFN, "r")
76            self.assertEqual(fo.read(), repr(d))
77        finally:
78            fo.close()
79            support.unlink(support.TESTFN)
80
81        d = deque(range(10), maxlen=None)
82        self.assertEqual(repr(d), 'deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])')
83        fo = open(support.TESTFN, "w")
84        try:
85            fo.write(str(d))
86            fo.close()
87            fo = open(support.TESTFN, "r")
88            self.assertEqual(fo.read(), repr(d))
89        finally:
90            fo.close()
91            support.unlink(support.TESTFN)
92
93    def test_maxlen_zero(self):
94        it = iter(range(100))
95        deque(it, maxlen=0)
96        self.assertEqual(list(it), [])
97
98        it = iter(range(100))
99        d = deque(maxlen=0)
100        d.extend(it)
101        self.assertEqual(list(it), [])
102
103        it = iter(range(100))
104        d = deque(maxlen=0)
105        d.extendleft(it)
106        self.assertEqual(list(it), [])
107
108    def test_maxlen_attribute(self):
109        self.assertEqual(deque().maxlen, None)
110        self.assertEqual(deque('abc').maxlen, None)
111        self.assertEqual(deque('abc', maxlen=4).maxlen, 4)
112        self.assertEqual(deque('abc', maxlen=2).maxlen, 2)
113        self.assertEqual(deque('abc', maxlen=0).maxlen, 0)
114        with self.assertRaises(AttributeError):
115            d = deque('abc')
116            d.maxlen = 10
117
118    def test_count(self):
119        for s in ('', 'abracadabra', 'simsalabim'*500+'abc'):
120            s = list(s)
121            d = deque(s)
122            for letter in 'abcdefghijklmnopqrstuvwxyz':
123                self.assertEqual(s.count(letter), d.count(letter), (s, d, letter))
124        self.assertRaises(TypeError, d.count)       # too few args
125        self.assertRaises(TypeError, d.count, 1, 2) # too many args
126        class BadCompare:
127            def __eq__(self, other):
128                raise ArithmeticError
129        d = deque([1, 2, BadCompare(), 3])
130        self.assertRaises(ArithmeticError, d.count, 2)
131        d = deque([1, 2, 3])
132        self.assertRaises(ArithmeticError, d.count, BadCompare())
133        class MutatingCompare:
134            def __eq__(self, other):
135                self.d.pop()
136                return True
137        m = MutatingCompare()
138        d = deque([1, 2, 3, m, 4, 5])
139        m.d = d
140        self.assertRaises(RuntimeError, d.count, 3)
141
142        # test issue11004
143        # block advance failed after rotation aligned elements on right side of block
144        d = deque([None]*16)
145        for i in range(len(d)):
146            d.rotate(-1)
147        d.rotate(1)
148        self.assertEqual(d.count(1), 0)
149        self.assertEqual(d.count(None), 16)
150
151    def test_comparisons(self):
152        d = deque('xabc'); d.popleft()
153        for e in [d, deque('abc'), deque('ab'), deque(), list(d)]:
154            self.assertEqual(d==e, type(d)==type(e) and list(d)==list(e))
155            self.assertEqual(d!=e, not(type(d)==type(e) and list(d)==list(e)))
156
157        args = map(deque, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba'))
158        for x in args:
159            for y in args:
160                self.assertEqual(x == y, list(x) == list(y), (x,y))
161                self.assertEqual(x != y, list(x) != list(y), (x,y))
162                self.assertEqual(x <  y, list(x) <  list(y), (x,y))
163                self.assertEqual(x <= y, list(x) <= list(y), (x,y))
164                self.assertEqual(x >  y, list(x) >  list(y), (x,y))
165                self.assertEqual(x >= y, list(x) >= list(y), (x,y))
166
167    def test_contains(self):
168        n = 200
169
170        d = deque(range(n))
171        for i in range(n):
172            self.assertTrue(i in d)
173        self.assertTrue((n+1) not in d)
174
175        # Test detection of mutation during iteration
176        d = deque(range(n))
177        d[n//2] = MutateCmp(d, False)
178        with self.assertRaises(RuntimeError):
179            n in d
180
181        # Test detection of comparison exceptions
182        d = deque(range(n))
183        d[n//2] = BadCmp()
184        with self.assertRaises(RuntimeError):
185            n in d
186
187    def test_extend(self):
188        d = deque('a')
189        self.assertRaises(TypeError, d.extend, 1)
190        d.extend('bcd')
191        self.assertEqual(list(d), list('abcd'))
192        d.extend(d)
193        self.assertEqual(list(d), list('abcdabcd'))
194
195    def test_add(self):
196        d = deque()
197        e = deque('abc')
198        f = deque('def')
199        self.assertEqual(d + d, deque())
200        self.assertEqual(e + f, deque('abcdef'))
201        self.assertEqual(e + e, deque('abcabc'))
202        self.assertEqual(e + d, deque('abc'))
203        self.assertEqual(d + e, deque('abc'))
204        self.assertIsNot(d + d, deque())
205        self.assertIsNot(e + d, deque('abc'))
206        self.assertIsNot(d + e, deque('abc'))
207
208        g = deque('abcdef', maxlen=4)
209        h = deque('gh')
210        self.assertEqual(g + h, deque('efgh'))
211
212        with self.assertRaises(TypeError):
213            deque('abc') + 'def'
214
215    def test_iadd(self):
216        d = deque('a')
217        d += 'bcd'
218        self.assertEqual(list(d), list('abcd'))
219        d += d
220        self.assertEqual(list(d), list('abcdabcd'))
221
222    def test_extendleft(self):
223        d = deque('a')
224        self.assertRaises(TypeError, d.extendleft, 1)
225        d.extendleft('bcd')
226        self.assertEqual(list(d), list(reversed('abcd')))
227        d.extendleft(d)
228        self.assertEqual(list(d), list('abcddcba'))
229        d = deque()
230        d.extendleft(range(1000))
231        self.assertEqual(list(d), list(reversed(range(1000))))
232        self.assertRaises(SyntaxError, d.extendleft, fail())
233
234    def test_getitem(self):
235        n = 200
236        d = deque(range(n))
237        l = list(range(n))
238        for i in range(n):
239            d.popleft()
240            l.pop(0)
241            if random.random() < 0.5:
242                d.append(i)
243                l.append(i)
244            for j in range(1-len(l), len(l)):
245                assert d[j] == l[j]
246
247        d = deque('superman')
248        self.assertEqual(d[0], 's')
249        self.assertEqual(d[-1], 'n')
250        d = deque()
251        self.assertRaises(IndexError, d.__getitem__, 0)
252        self.assertRaises(IndexError, d.__getitem__, -1)
253
254    def test_index(self):
255        for n in 1, 2, 30, 40, 200:
256
257            d = deque(range(n))
258            for i in range(n):
259                self.assertEqual(d.index(i), i)
260
261            with self.assertRaises(ValueError):
262                d.index(n+1)
263
264            # Test detection of mutation during iteration
265            d = deque(range(n))
266            d[n//2] = MutateCmp(d, False)
267            with self.assertRaises(RuntimeError):
268                d.index(n)
269
270            # Test detection of comparison exceptions
271            d = deque(range(n))
272            d[n//2] = BadCmp()
273            with self.assertRaises(RuntimeError):
274                d.index(n)
275
276        # Test start and stop arguments behavior matches list.index()
277        elements = 'ABCDEFGHI'
278        nonelement = 'Z'
279        d = deque(elements * 2)
280        s = list(elements * 2)
281        for start in range(-5 - len(s)*2, 5 + len(s) * 2):
282            for stop in range(-5 - len(s)*2, 5 + len(s) * 2):
283                for element in elements + 'Z':
284                    try:
285                        target = s.index(element, start, stop)
286                    except ValueError:
287                        with self.assertRaises(ValueError):
288                            d.index(element, start, stop)
289                    else:
290                        self.assertEqual(d.index(element, start, stop), target)
291
292    def test_index_bug_24913(self):
293        d = deque('A' * 3)
294        with self.assertRaises(ValueError):
295            i = d.index("Hello world", 0, 4)
296
297    def test_insert(self):
298        # Test to make sure insert behaves like lists
299        elements = 'ABCDEFGHI'
300        for i in range(-5 - len(elements)*2, 5 + len(elements) * 2):
301            d = deque('ABCDEFGHI')
302            s = list('ABCDEFGHI')
303            d.insert(i, 'Z')
304            s.insert(i, 'Z')
305            self.assertEqual(list(d), s)
306
307    def test_insert_bug_26194(self):
308        data = 'ABC'
309        d = deque(data, maxlen=len(data))
310        with self.assertRaises(IndexError):
311            d.insert(2, None)
312
313        elements = 'ABCDEFGHI'
314        for i in range(-len(elements), len(elements)):
315            d = deque(elements, maxlen=len(elements)+1)
316            d.insert(i, 'Z')
317            if i >= 0:
318                self.assertEqual(d[i], 'Z')
319            else:
320                self.assertEqual(d[i-1], 'Z')
321
322    def test_imul(self):
323        for n in (-10, -1, 0, 1, 2, 10, 1000):
324            d = deque()
325            d *= n
326            self.assertEqual(d, deque())
327            self.assertIsNone(d.maxlen)
328
329        for n in (-10, -1, 0, 1, 2, 10, 1000):
330            d = deque('a')
331            d *= n
332            self.assertEqual(d, deque('a' * n))
333            self.assertIsNone(d.maxlen)
334
335        for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000):
336            d = deque('a', 500)
337            d *= n
338            self.assertEqual(d, deque('a' * min(n, 500)))
339            self.assertEqual(d.maxlen, 500)
340
341        for n in (-10, -1, 0, 1, 2, 10, 1000):
342            d = deque('abcdef')
343            d *= n
344            self.assertEqual(d, deque('abcdef' * n))
345            self.assertIsNone(d.maxlen)
346
347        for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000):
348            d = deque('abcdef', 500)
349            d *= n
350            self.assertEqual(d, deque(('abcdef' * n)[-500:]))
351            self.assertEqual(d.maxlen, 500)
352
353    def test_mul(self):
354        d = deque('abc')
355        self.assertEqual(d * -5, deque())
356        self.assertEqual(d * 0, deque())
357        self.assertEqual(d * 1, deque('abc'))
358        self.assertEqual(d * 2, deque('abcabc'))
359        self.assertEqual(d * 3, deque('abcabcabc'))
360        self.assertIsNot(d * 1, d)
361
362        self.assertEqual(deque() * 0, deque())
363        self.assertEqual(deque() * 1, deque())
364        self.assertEqual(deque() * 5, deque())
365
366        self.assertEqual(-5 * d, deque())
367        self.assertEqual(0 * d, deque())
368        self.assertEqual(1 * d, deque('abc'))
369        self.assertEqual(2 * d, deque('abcabc'))
370        self.assertEqual(3 * d, deque('abcabcabc'))
371
372        d = deque('abc', maxlen=5)
373        self.assertEqual(d * -5, deque())
374        self.assertEqual(d * 0, deque())
375        self.assertEqual(d * 1, deque('abc'))
376        self.assertEqual(d * 2, deque('bcabc'))
377        self.assertEqual(d * 30, deque('bcabc'))
378
379    def test_setitem(self):
380        n = 200
381        d = deque(range(n))
382        for i in range(n):
383            d[i] = 10 * i
384        self.assertEqual(list(d), [10*i for i in range(n)])
385        l = list(d)
386        for i in range(1-n, 0, -1):
387            d[i] = 7*i
388            l[i] = 7*i
389        self.assertEqual(list(d), l)
390
391    def test_delitem(self):
392        n = 500         # O(n**2) test, don't make this too big
393        d = deque(range(n))
394        self.assertRaises(IndexError, d.__delitem__, -n-1)
395        self.assertRaises(IndexError, d.__delitem__, n)
396        for i in range(n):
397            self.assertEqual(len(d), n-i)
398            j = random.randrange(-len(d), len(d))
399            val = d[j]
400            self.assertIn(val, d)
401            del d[j]
402            self.assertNotIn(val, d)
403        self.assertEqual(len(d), 0)
404
405    def test_reverse(self):
406        n = 500         # O(n**2) test, don't make this too big
407        data = [random.random() for i in range(n)]
408        for i in range(n):
409            d = deque(data[:i])
410            r = d.reverse()
411            self.assertEqual(list(d), list(reversed(data[:i])))
412            self.assertIs(r, None)
413            d.reverse()
414            self.assertEqual(list(d), data[:i])
415        self.assertRaises(TypeError, d.reverse, 1)          # Arity is zero
416
417    def test_rotate(self):
418        s = tuple('abcde')
419        n = len(s)
420
421        d = deque(s)
422        d.rotate(1)             # verify rot(1)
423        self.assertEqual(''.join(d), 'eabcd')
424
425        d = deque(s)
426        d.rotate(-1)            # verify rot(-1)
427        self.assertEqual(''.join(d), 'bcdea')
428        d.rotate()              # check default to 1
429        self.assertEqual(tuple(d), s)
430
431        for i in range(n*3):
432            d = deque(s)
433            e = deque(d)
434            d.rotate(i)         # check vs. rot(1) n times
435            for j in range(i):
436                e.rotate(1)
437            self.assertEqual(tuple(d), tuple(e))
438            d.rotate(-i)        # check that it works in reverse
439            self.assertEqual(tuple(d), s)
440            e.rotate(n-i)       # check that it wraps forward
441            self.assertEqual(tuple(e), s)
442
443        for i in range(n*3):
444            d = deque(s)
445            e = deque(d)
446            d.rotate(-i)
447            for j in range(i):
448                e.rotate(-1)    # check vs. rot(-1) n times
449            self.assertEqual(tuple(d), tuple(e))
450            d.rotate(i)         # check that it works in reverse
451            self.assertEqual(tuple(d), s)
452            e.rotate(i-n)       # check that it wraps backaround
453            self.assertEqual(tuple(e), s)
454
455        d = deque(s)
456        e = deque(s)
457        e.rotate(BIG+17)        # verify on long series of rotates
458        dr = d.rotate
459        for i in range(BIG+17):
460            dr()
461        self.assertEqual(tuple(d), tuple(e))
462
463        self.assertRaises(TypeError, d.rotate, 'x')   # Wrong arg type
464        self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args
465
466        d = deque()
467        d.rotate()              # rotate an empty deque
468        self.assertEqual(d, deque())
469
470    def test_len(self):
471        d = deque('ab')
472        self.assertEqual(len(d), 2)
473        d.popleft()
474        self.assertEqual(len(d), 1)
475        d.pop()
476        self.assertEqual(len(d), 0)
477        self.assertRaises(IndexError, d.pop)
478        self.assertEqual(len(d), 0)
479        d.append('c')
480        self.assertEqual(len(d), 1)
481        d.appendleft('d')
482        self.assertEqual(len(d), 2)
483        d.clear()
484        self.assertEqual(len(d), 0)
485
486    def test_underflow(self):
487        d = deque()
488        self.assertRaises(IndexError, d.pop)
489        self.assertRaises(IndexError, d.popleft)
490
491    def test_clear(self):
492        d = deque(range(100))
493        self.assertEqual(len(d), 100)
494        d.clear()
495        self.assertEqual(len(d), 0)
496        self.assertEqual(list(d), [])
497        d.clear()               # clear an empty deque
498        self.assertEqual(list(d), [])
499
500    def test_remove(self):
501        d = deque('abcdefghcij')
502        d.remove('c')
503        self.assertEqual(d, deque('abdefghcij'))
504        d.remove('c')
505        self.assertEqual(d, deque('abdefghij'))
506        self.assertRaises(ValueError, d.remove, 'c')
507        self.assertEqual(d, deque('abdefghij'))
508
509        # Handle comparison errors
510        d = deque(['a', 'b', BadCmp(), 'c'])
511        e = deque(d)
512        self.assertRaises(RuntimeError, d.remove, 'c')
513        for x, y in zip(d, e):
514            # verify that original order and values are retained.
515            self.assertTrue(x is y)
516
517        # Handle evil mutator
518        for match in (True, False):
519            d = deque(['ab'])
520            d.extend([MutateCmp(d, match), 'c'])
521            self.assertRaises(IndexError, d.remove, 'c')
522            self.assertEqual(d, deque())
523
524    def test_repr(self):
525        d = deque(range(200))
526        e = eval(repr(d))
527        self.assertEqual(list(d), list(e))
528        d.append(d)
529        self.assertIn('...', repr(d))
530
531    def test_print(self):
532        d = deque(range(200))
533        d.append(d)
534        try:
535            support.unlink(support.TESTFN)
536            fo = open(support.TESTFN, "w")
537            print(d, file=fo, end='')
538            fo.close()
539            fo = open(support.TESTFN, "r")
540            self.assertEqual(fo.read(), repr(d))
541        finally:
542            fo.close()
543            support.unlink(support.TESTFN)
544
545    def test_init(self):
546        self.assertRaises(TypeError, deque, 'abc', 2, 3);
547        self.assertRaises(TypeError, deque, 1);
548
549    def test_hash(self):
550        self.assertRaises(TypeError, hash, deque('abc'))
551
552    def test_long_steadystate_queue_popleft(self):
553        for size in (0, 1, 2, 100, 1000):
554            d = deque(range(size))
555            append, pop = d.append, d.popleft
556            for i in range(size, BIG):
557                append(i)
558                x = pop()
559                if x != i - size:
560                    self.assertEqual(x, i-size)
561            self.assertEqual(list(d), list(range(BIG-size, BIG)))
562
563    def test_long_steadystate_queue_popright(self):
564        for size in (0, 1, 2, 100, 1000):
565            d = deque(reversed(range(size)))
566            append, pop = d.appendleft, d.pop
567            for i in range(size, BIG):
568                append(i)
569                x = pop()
570                if x != i - size:
571                    self.assertEqual(x, i-size)
572            self.assertEqual(list(reversed(list(d))),
573                             list(range(BIG-size, BIG)))
574
575    def test_big_queue_popleft(self):
576        pass
577        d = deque()
578        append, pop = d.append, d.popleft
579        for i in range(BIG):
580            append(i)
581        for i in range(BIG):
582            x = pop()
583            if x != i:
584                self.assertEqual(x, i)
585
586    def test_big_queue_popright(self):
587        d = deque()
588        append, pop = d.appendleft, d.pop
589        for i in range(BIG):
590            append(i)
591        for i in range(BIG):
592            x = pop()
593            if x != i:
594                self.assertEqual(x, i)
595
596    def test_big_stack_right(self):
597        d = deque()
598        append, pop = d.append, d.pop
599        for i in range(BIG):
600            append(i)
601        for i in reversed(range(BIG)):
602            x = pop()
603            if x != i:
604                self.assertEqual(x, i)
605        self.assertEqual(len(d), 0)
606
607    def test_big_stack_left(self):
608        d = deque()
609        append, pop = d.appendleft, d.popleft
610        for i in range(BIG):
611            append(i)
612        for i in reversed(range(BIG)):
613            x = pop()
614            if x != i:
615                self.assertEqual(x, i)
616        self.assertEqual(len(d), 0)
617
618    def test_roundtrip_iter_init(self):
619        d = deque(range(200))
620        e = deque(d)
621        self.assertNotEqual(id(d), id(e))
622        self.assertEqual(list(d), list(e))
623
624    def test_pickle(self):
625        for d in deque(range(200)), deque(range(200), 100):
626            for i in range(pickle.HIGHEST_PROTOCOL + 1):
627                s = pickle.dumps(d, i)
628                e = pickle.loads(s)
629                self.assertNotEqual(id(e), id(d))
630                self.assertEqual(list(e), list(d))
631                self.assertEqual(e.maxlen, d.maxlen)
632
633    def test_pickle_recursive(self):
634        for d in deque('abc'), deque('abc', 3):
635            d.append(d)
636            for i in range(pickle.HIGHEST_PROTOCOL + 1):
637                e = pickle.loads(pickle.dumps(d, i))
638                self.assertNotEqual(id(e), id(d))
639                self.assertEqual(id(e[-1]), id(e))
640                self.assertEqual(e.maxlen, d.maxlen)
641
642    def test_iterator_pickle(self):
643        orig = deque(range(200))
644        data = [i*1.01 for i in orig]
645        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
646            # initial iterator
647            itorg = iter(orig)
648            dump = pickle.dumps((itorg, orig), proto)
649            it, d = pickle.loads(dump)
650            for i, x in enumerate(data):
651                d[i] = x
652            self.assertEqual(type(it), type(itorg))
653            self.assertEqual(list(it), data)
654
655            # running iterator
656            next(itorg)
657            dump = pickle.dumps((itorg, orig), proto)
658            it, d = pickle.loads(dump)
659            for i, x in enumerate(data):
660                d[i] = x
661            self.assertEqual(type(it), type(itorg))
662            self.assertEqual(list(it), data[1:])
663
664            # empty iterator
665            for i in range(1, len(data)):
666                next(itorg)
667            dump = pickle.dumps((itorg, orig), proto)
668            it, d = pickle.loads(dump)
669            for i, x in enumerate(data):
670                d[i] = x
671            self.assertEqual(type(it), type(itorg))
672            self.assertEqual(list(it), [])
673
674            # exhausted iterator
675            self.assertRaises(StopIteration, next, itorg)
676            dump = pickle.dumps((itorg, orig), proto)
677            it, d = pickle.loads(dump)
678            for i, x in enumerate(data):
679                d[i] = x
680            self.assertEqual(type(it), type(itorg))
681            self.assertEqual(list(it), [])
682
683    def test_deepcopy(self):
684        mut = [10]
685        d = deque([mut])
686        e = copy.deepcopy(d)
687        self.assertEqual(list(d), list(e))
688        mut[0] = 11
689        self.assertNotEqual(id(d), id(e))
690        self.assertNotEqual(list(d), list(e))
691
692    def test_copy(self):
693        mut = [10]
694        d = deque([mut])
695        e = copy.copy(d)
696        self.assertEqual(list(d), list(e))
697        mut[0] = 11
698        self.assertNotEqual(id(d), id(e))
699        self.assertEqual(list(d), list(e))
700
701        for i in range(5):
702            for maxlen in range(-1, 6):
703                s = [random.random() for j in range(i)]
704                d = deque(s) if maxlen == -1 else deque(s, maxlen)
705                e = d.copy()
706                self.assertEqual(d, e)
707                self.assertEqual(d.maxlen, e.maxlen)
708                self.assertTrue(all(x is y for x, y in zip(d, e)))
709
710    def test_copy_method(self):
711        mut = [10]
712        d = deque([mut])
713        e = d.copy()
714        self.assertEqual(list(d), list(e))
715        mut[0] = 11
716        self.assertNotEqual(id(d), id(e))
717        self.assertEqual(list(d), list(e))
718
719    def test_reversed(self):
720        for s in ('abcd', range(2000)):
721            self.assertEqual(list(reversed(deque(s))), list(reversed(s)))
722
723    def test_reversed_new(self):
724        klass = type(reversed(deque()))
725        for s in ('abcd', range(2000)):
726            self.assertEqual(list(klass(deque(s))), list(reversed(s)))
727
728    def test_gc_doesnt_blowup(self):
729        import gc
730        # This used to assert-fail in deque_traverse() under a debug
731        # build, or run wild with a NULL pointer in a release build.
732        d = deque()
733        for i in range(100):
734            d.append(1)
735            gc.collect()
736
737    def test_container_iterator(self):
738        # Bug #3680: tp_traverse was not implemented for deque iterator objects
739        class C(object):
740            pass
741        for i in range(2):
742            obj = C()
743            ref = weakref.ref(obj)
744            if i == 0:
745                container = deque([obj, 1])
746            else:
747                container = reversed(deque([obj, 1]))
748            obj.x = iter(container)
749            del obj, container
750            gc.collect()
751            self.assertTrue(ref() is None, "Cycle was not collected")
752
753    check_sizeof = support.check_sizeof
754
755    @support.cpython_only
756    def test_sizeof(self):
757        BLOCKLEN = 64
758        basesize = support.calcvobjsize('2P4nP')
759        blocksize = struct.calcsize('P%dPP' % BLOCKLEN)
760        self.assertEqual(object.__sizeof__(deque()), basesize)
761        check = self.check_sizeof
762        check(deque(), basesize + blocksize)
763        check(deque('a'), basesize + blocksize)
764        check(deque('a' * (BLOCKLEN - 1)), basesize + blocksize)
765        check(deque('a' * BLOCKLEN), basesize + 2 * blocksize)
766        check(deque('a' * (42 * BLOCKLEN)), basesize + 43 * blocksize)
767
768class TestVariousIteratorArgs(unittest.TestCase):
769
770    def test_constructor(self):
771        for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
772            for g in (seq_tests.Sequence, seq_tests.IterFunc,
773                      seq_tests.IterGen, seq_tests.IterFuncStop,
774                      seq_tests.itermulti, seq_tests.iterfunc):
775                self.assertEqual(list(deque(g(s))), list(g(s)))
776            self.assertRaises(TypeError, deque, seq_tests.IterNextOnly(s))
777            self.assertRaises(TypeError, deque, seq_tests.IterNoNext(s))
778            self.assertRaises(ZeroDivisionError, deque, seq_tests.IterGenExc(s))
779
780    def test_iter_with_altered_data(self):
781        d = deque('abcdefg')
782        it = iter(d)
783        d.pop()
784        self.assertRaises(RuntimeError, next, it)
785
786    def test_runtime_error_on_empty_deque(self):
787        d = deque()
788        it = iter(d)
789        d.append(10)
790        self.assertRaises(RuntimeError, next, it)
791
792class Deque(deque):
793    pass
794
795class DequeWithBadIter(deque):
796    def __iter__(self):
797        raise TypeError
798
799class TestSubclass(unittest.TestCase):
800
801    def test_basics(self):
802        d = Deque(range(25))
803        d.__init__(range(200))
804        for i in range(200, 400):
805            d.append(i)
806        for i in reversed(range(-200, 0)):
807            d.appendleft(i)
808        self.assertEqual(list(d), list(range(-200, 400)))
809        self.assertEqual(len(d), 600)
810
811        left = [d.popleft() for i in range(250)]
812        self.assertEqual(left, list(range(-200, 50)))
813        self.assertEqual(list(d), list(range(50, 400)))
814
815        right = [d.pop() for i in range(250)]
816        right.reverse()
817        self.assertEqual(right, list(range(150, 400)))
818        self.assertEqual(list(d), list(range(50, 150)))
819
820        d.clear()
821        self.assertEqual(len(d), 0)
822
823    def test_copy_pickle(self):
824
825        d = Deque('abc')
826
827        e = d.__copy__()
828        self.assertEqual(type(d), type(e))
829        self.assertEqual(list(d), list(e))
830
831        e = Deque(d)
832        self.assertEqual(type(d), type(e))
833        self.assertEqual(list(d), list(e))
834
835        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
836            s = pickle.dumps(d, proto)
837            e = pickle.loads(s)
838            self.assertNotEqual(id(d), id(e))
839            self.assertEqual(type(d), type(e))
840            self.assertEqual(list(d), list(e))
841
842        d = Deque('abcde', maxlen=4)
843
844        e = d.__copy__()
845        self.assertEqual(type(d), type(e))
846        self.assertEqual(list(d), list(e))
847
848        e = Deque(d)
849        self.assertEqual(type(d), type(e))
850        self.assertEqual(list(d), list(e))
851
852        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
853            s = pickle.dumps(d, proto)
854            e = pickle.loads(s)
855            self.assertNotEqual(id(d), id(e))
856            self.assertEqual(type(d), type(e))
857            self.assertEqual(list(d), list(e))
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        self.assertRaises(ReferenceError, str, p)
886
887    def test_strange_subclass(self):
888        class X(deque):
889            def __iter__(self):
890                return iter([])
891        d1 = X([1,2,3])
892        d2 = X([4,5,6])
893        d1 == d2   # not clear if this is supposed to be True or False,
894                   # but it used to give a SystemError
895
896
897class SubclassWithKwargs(deque):
898    def __init__(self, newarg=1):
899        deque.__init__(self)
900
901class 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
906class 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
927libreftest = """
928Example 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())
934G
935H
936I
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
940deque(['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
954True
955>>> d.extend('jkl')                  # add multiple elements at once
956>>> d
957deque(['g', 'h', 'i', 'j', 'k', 'l'])
958>>> d.rotate(1)                      # right rotation
959>>> d
960deque(['l', 'g', 'h', 'i', 'j', 'k'])
961>>> d.rotate(-1)                     # left rotation
962>>> d
963deque(['g', 'h', 'i', 'j', 'k', 'l'])
964>>> deque(reversed(d))               # make a new deque in reverse order
965deque(['l', 'k', 'j', 'i', 'h', 'g'])
966>>> d.clear()                        # empty the deque
967>>> d.pop()                          # cannot pop from an empty deque
968Traceback (most recent call last):
969  File "<pyshell#6>", line 1, in -toplevel-
970    d.pop()
971IndexError: pop from an empty deque
972
973>>> d.extendleft('abc')              # extendleft() reverses the input order
974>>> d
975deque(['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
987deque(['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...
1005a
1006d
1007e
1008b
1009f
1010c
1011g
1012h
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
1032def test_main(verbose=None):
1033    import sys
1034    test_classes = (
1035        TestBasic,
1036        TestVariousIteratorArgs,
1037        TestSubclass,
1038        TestSubclassWithKwargs,
1039        TestSequence,
1040    )
1041
1042    support.run_unittest(*test_classes)
1043
1044    # verify reference counting
1045    if verbose and hasattr(sys, "gettotalrefcount"):
1046        import gc
1047        counts = [None] * 5
1048        for i in range(len(counts)):
1049            support.run_unittest(*test_classes)
1050            gc.collect()
1051            counts[i] = sys.gettotalrefcount()
1052        print(counts)
1053
1054    # doctests
1055    from test import test_deque
1056    support.run_doctest(test_deque, verbose)
1057
1058if __name__ == "__main__":
1059    test_main(verbose=True)
1060