1from collections import deque
2import unittest
3from test import test_support, seq_tests
4import gc
5import weakref
6import copy
7import cPickle as pickle
8import random
9import struct
10
11BIG = 100000
12
13def fail():
14    raise SyntaxError
15    yield 1
16
17class BadCmp:
18    def __eq__(self, other):
19        raise RuntimeError
20
21class MutateCmp:
22    def __init__(self, deque, result):
23        self.deque = deque
24        self.result = result
25    def __eq__(self, other):
26        self.deque.clear()
27        return self.result
28
29class TestBasic(unittest.TestCase):
30
31    def test_basics(self):
32        d = deque(xrange(-5125, -5000))
33        d.__init__(xrange(200))
34        for i in xrange(200, 400):
35            d.append(i)
36        for i in reversed(xrange(-200, 0)):
37            d.appendleft(i)
38        self.assertEqual(list(d), range(-200, 400))
39        self.assertEqual(len(d), 600)
40
41        left = [d.popleft() for i in xrange(250)]
42        self.assertEqual(left, range(-200, 50))
43        self.assertEqual(list(d), range(50, 400))
44
45        right = [d.pop() for i in xrange(250)]
46        right.reverse()
47        self.assertEqual(right, range(150, 400))
48        self.assertEqual(list(d), range(50, 150))
49
50    def test_maxlen(self):
51        self.assertRaises(ValueError, deque, 'abc', -1)
52        self.assertRaises(ValueError, deque, 'abc', -2)
53        it = iter(range(10))
54        d = deque(it, maxlen=3)
55        self.assertEqual(list(it), [])
56        self.assertEqual(repr(d), 'deque([7, 8, 9], maxlen=3)')
57        self.assertEqual(list(d), range(7, 10))
58        self.assertEqual(d, deque(range(10), 3))
59        d.append(10)
60        self.assertEqual(list(d), range(8, 11))
61        d.appendleft(7)
62        self.assertEqual(list(d), range(7, 10))
63        d.extend([10, 11])
64        self.assertEqual(list(d), range(9, 12))
65        d.extendleft([8, 7])
66        self.assertEqual(list(d), range(7, 10))
67        d = deque(xrange(200), maxlen=10)
68        d.append(d)
69        test_support.unlink(test_support.TESTFN)
70        fo = open(test_support.TESTFN, "wb")
71        try:
72            print >> fo, d,
73            fo.close()
74            fo = open(test_support.TESTFN, "rb")
75            self.assertEqual(fo.read(), repr(d))
76        finally:
77            fo.close()
78            test_support.unlink(test_support.TESTFN)
79
80        d = deque(range(10), maxlen=None)
81        self.assertEqual(repr(d), 'deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])')
82        fo = open(test_support.TESTFN, "wb")
83        try:
84            print >> fo, d,
85            fo.close()
86            fo = open(test_support.TESTFN, "rb")
87            self.assertEqual(fo.read(), repr(d))
88        finally:
89            fo.close()
90            test_support.unlink(test_support.TESTFN)
91
92    def test_maxlen_zero(self):
93        it = iter(range(100))
94        deque(it, maxlen=0)
95        self.assertEqual(list(it), [])
96
97        it = iter(range(100))
98        d = deque(maxlen=0)
99        d.extend(it)
100        self.assertEqual(list(it), [])
101
102        it = iter(range(100))
103        d = deque(maxlen=0)
104        d.extendleft(it)
105        self.assertEqual(list(it), [])
106
107    def test_maxlen_attribute(self):
108        self.assertEqual(deque().maxlen, None)
109        self.assertEqual(deque('abc').maxlen, None)
110        self.assertEqual(deque('abc', maxlen=4).maxlen, 4)
111        self.assertEqual(deque('abc', maxlen=2).maxlen, 2)
112        self.assertEqual(deque('abc', maxlen=0).maxlen, 0)
113        with self.assertRaises(AttributeError):
114            d = deque('abc')
115            d.maxlen = 10
116
117    def test_count(self):
118        for s in ('', 'abracadabra', 'simsalabim'*500+'abc'):
119            s = list(s)
120            d = deque(s)
121            for letter in 'abcdefghijklmnopqrstuvwxyz':
122                self.assertEqual(s.count(letter), d.count(letter), (s, d, letter))
123        self.assertRaises(TypeError, d.count)       # too few args
124        self.assertRaises(TypeError, d.count, 1, 2) # too many args
125        class BadCompare:
126            def __eq__(self, other):
127                raise ArithmeticError
128        d = deque([1, 2, BadCompare(), 3])
129        self.assertRaises(ArithmeticError, d.count, 2)
130        d = deque([1, 2, 3])
131        self.assertRaises(ArithmeticError, d.count, BadCompare())
132        class MutatingCompare:
133            def __eq__(self, other):
134                self.d.pop()
135                return True
136        m = MutatingCompare()
137        d = deque([1, 2, 3, m, 4, 5])
138        m.d = d
139        self.assertRaises(RuntimeError, d.count, 3)
140
141        # test issue11004
142        # block advance failed after rotation aligned elements on right side of block
143        d = deque([None]*16)
144        for i in range(len(d)):
145            d.rotate(-1)
146        d.rotate(1)
147        self.assertEqual(d.count(1), 0)
148        self.assertEqual(d.count(None), 16)
149
150    def test_comparisons(self):
151        d = deque('xabc'); d.popleft()
152        for e in [d, deque('abc'), deque('ab'), deque(), list(d)]:
153            self.assertEqual(d==e, type(d)==type(e) and list(d)==list(e))
154            self.assertEqual(d!=e, not(type(d)==type(e) and list(d)==list(e)))
155
156        args = map(deque, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba'))
157        for x in args:
158            for y in args:
159                self.assertEqual(x == y, list(x) == list(y), (x,y))
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(cmp(x,y), cmp(list(x),list(y)), (x,y))
166
167    def test_extend(self):
168        d = deque('a')
169        self.assertRaises(TypeError, d.extend, 1)
170        d.extend('bcd')
171        self.assertEqual(list(d), list('abcd'))
172        d.extend(d)
173        self.assertEqual(list(d), list('abcdabcd'))
174
175    def test_iadd(self):
176        d = deque('a')
177        d += 'bcd'
178        self.assertEqual(list(d), list('abcd'))
179        d += d
180        self.assertEqual(list(d), list('abcdabcd'))
181
182    def test_extendleft(self):
183        d = deque('a')
184        self.assertRaises(TypeError, d.extendleft, 1)
185        d.extendleft('bcd')
186        self.assertEqual(list(d), list(reversed('abcd')))
187        d.extendleft(d)
188        self.assertEqual(list(d), list('abcddcba'))
189        d = deque()
190        d.extendleft(range(1000))
191        self.assertEqual(list(d), list(reversed(range(1000))))
192        self.assertRaises(SyntaxError, d.extendleft, fail())
193
194    def test_getitem(self):
195        n = 200
196        d = deque(xrange(n))
197        l = range(n)
198        for i in xrange(n):
199            d.popleft()
200            l.pop(0)
201            if random.random() < 0.5:
202                d.append(i)
203                l.append(i)
204            for j in xrange(1-len(l), len(l)):
205                assert d[j] == l[j]
206
207        d = deque('superman')
208        self.assertEqual(d[0], 's')
209        self.assertEqual(d[-1], 'n')
210        d = deque()
211        self.assertRaises(IndexError, d.__getitem__, 0)
212        self.assertRaises(IndexError, d.__getitem__, -1)
213
214    def test_setitem(self):
215        n = 200
216        d = deque(xrange(n))
217        for i in xrange(n):
218            d[i] = 10 * i
219        self.assertEqual(list(d), [10*i for i in xrange(n)])
220        l = list(d)
221        for i in xrange(1-n, 0, -1):
222            d[i] = 7*i
223            l[i] = 7*i
224        self.assertEqual(list(d), l)
225
226    def test_delitem(self):
227        n = 500         # O(n**2) test, don't make this too big
228        d = deque(xrange(n))
229        self.assertRaises(IndexError, d.__delitem__, -n-1)
230        self.assertRaises(IndexError, d.__delitem__, n)
231        for i in xrange(n):
232            self.assertEqual(len(d), n-i)
233            j = random.randrange(-len(d), len(d))
234            val = d[j]
235            self.assertIn(val, d)
236            del d[j]
237            self.assertNotIn(val, d)
238        self.assertEqual(len(d), 0)
239
240    def test_reverse(self):
241        n = 500         # O(n**2) test, don't make this too big
242        data = [random.random() for i in range(n)]
243        for i in range(n):
244            d = deque(data[:i])
245            r = d.reverse()
246            self.assertEqual(list(d), list(reversed(data[:i])))
247            self.assertIs(r, None)
248            d.reverse()
249            self.assertEqual(list(d), data[:i])
250        self.assertRaises(TypeError, d.reverse, 1)          # Arity is zero
251
252    def test_rotate(self):
253        s = tuple('abcde')
254        n = len(s)
255
256        d = deque(s)
257        d.rotate(1)             # verify rot(1)
258        self.assertEqual(''.join(d), 'eabcd')
259
260        d = deque(s)
261        d.rotate(-1)            # verify rot(-1)
262        self.assertEqual(''.join(d), 'bcdea')
263        d.rotate()              # check default to 1
264        self.assertEqual(tuple(d), s)
265
266        for i in xrange(n*3):
267            d = deque(s)
268            e = deque(d)
269            d.rotate(i)         # check vs. rot(1) n times
270            for j in xrange(i):
271                e.rotate(1)
272            self.assertEqual(tuple(d), tuple(e))
273            d.rotate(-i)        # check that it works in reverse
274            self.assertEqual(tuple(d), s)
275            e.rotate(n-i)       # check that it wraps forward
276            self.assertEqual(tuple(e), s)
277
278        for i in xrange(n*3):
279            d = deque(s)
280            e = deque(d)
281            d.rotate(-i)
282            for j in xrange(i):
283                e.rotate(-1)    # check vs. rot(-1) n times
284            self.assertEqual(tuple(d), tuple(e))
285            d.rotate(i)         # check that it works in reverse
286            self.assertEqual(tuple(d), s)
287            e.rotate(i-n)       # check that it wraps backaround
288            self.assertEqual(tuple(e), s)
289
290        d = deque(s)
291        e = deque(s)
292        e.rotate(BIG+17)        # verify on long series of rotates
293        dr = d.rotate
294        for i in xrange(BIG+17):
295            dr()
296        self.assertEqual(tuple(d), tuple(e))
297
298        self.assertRaises(TypeError, d.rotate, 'x')   # Wrong arg type
299        self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args
300
301        d = deque()
302        d.rotate()              # rotate an empty deque
303        self.assertEqual(d, deque())
304
305    def test_len(self):
306        d = deque('ab')
307        self.assertEqual(len(d), 2)
308        d.popleft()
309        self.assertEqual(len(d), 1)
310        d.pop()
311        self.assertEqual(len(d), 0)
312        self.assertRaises(IndexError, d.pop)
313        self.assertEqual(len(d), 0)
314        d.append('c')
315        self.assertEqual(len(d), 1)
316        d.appendleft('d')
317        self.assertEqual(len(d), 2)
318        d.clear()
319        self.assertEqual(len(d), 0)
320
321    def test_underflow(self):
322        d = deque()
323        self.assertRaises(IndexError, d.pop)
324        self.assertRaises(IndexError, d.popleft)
325
326    def test_clear(self):
327        d = deque(xrange(100))
328        self.assertEqual(len(d), 100)
329        d.clear()
330        self.assertEqual(len(d), 0)
331        self.assertEqual(list(d), [])
332        d.clear()               # clear an emtpy deque
333        self.assertEqual(list(d), [])
334
335    def test_remove(self):
336        d = deque('abcdefghcij')
337        d.remove('c')
338        self.assertEqual(d, deque('abdefghcij'))
339        d.remove('c')
340        self.assertEqual(d, deque('abdefghij'))
341        self.assertRaises(ValueError, d.remove, 'c')
342        self.assertEqual(d, deque('abdefghij'))
343
344        # Handle comparison errors
345        d = deque(['a', 'b', BadCmp(), 'c'])
346        e = deque(d)
347        self.assertRaises(RuntimeError, d.remove, 'c')
348        for x, y in zip(d, e):
349            # verify that original order and values are retained.
350            self.assertTrue(x is y)
351
352        # Handle evil mutator
353        for match in (True, False):
354            d = deque(['ab'])
355            d.extend([MutateCmp(d, match), 'c'])
356            self.assertRaises(IndexError, d.remove, 'c')
357            self.assertEqual(d, deque())
358
359    def test_repr(self):
360        d = deque(xrange(200))
361        e = eval(repr(d))
362        self.assertEqual(list(d), list(e))
363        d.append(d)
364        self.assertIn('...', repr(d))
365
366    def test_print(self):
367        d = deque(xrange(200))
368        d.append(d)
369        test_support.unlink(test_support.TESTFN)
370        fo = open(test_support.TESTFN, "wb")
371        try:
372            print >> fo, d,
373            fo.close()
374            fo = open(test_support.TESTFN, "rb")
375            self.assertEqual(fo.read(), repr(d))
376        finally:
377            fo.close()
378            test_support.unlink(test_support.TESTFN)
379
380    def test_init(self):
381        self.assertRaises(TypeError, deque, 'abc', 2, 3);
382        self.assertRaises(TypeError, deque, 1);
383
384    def test_hash(self):
385        self.assertRaises(TypeError, hash, deque('abc'))
386
387    def test_long_steadystate_queue_popleft(self):
388        for size in (0, 1, 2, 100, 1000):
389            d = deque(xrange(size))
390            append, pop = d.append, d.popleft
391            for i in xrange(size, BIG):
392                append(i)
393                x = pop()
394                if x != i - size:
395                    self.assertEqual(x, i-size)
396            self.assertEqual(list(d), range(BIG-size, BIG))
397
398    def test_long_steadystate_queue_popright(self):
399        for size in (0, 1, 2, 100, 1000):
400            d = deque(reversed(xrange(size)))
401            append, pop = d.appendleft, d.pop
402            for i in xrange(size, BIG):
403                append(i)
404                x = pop()
405                if x != i - size:
406                    self.assertEqual(x, i-size)
407            self.assertEqual(list(reversed(list(d))), range(BIG-size, BIG))
408
409    def test_big_queue_popleft(self):
410        pass
411        d = deque()
412        append, pop = d.append, d.popleft
413        for i in xrange(BIG):
414            append(i)
415        for i in xrange(BIG):
416            x = pop()
417            if x != i:
418                self.assertEqual(x, i)
419
420    def test_big_queue_popright(self):
421        d = deque()
422        append, pop = d.appendleft, d.pop
423        for i in xrange(BIG):
424            append(i)
425        for i in xrange(BIG):
426            x = pop()
427            if x != i:
428                self.assertEqual(x, i)
429
430    def test_big_stack_right(self):
431        d = deque()
432        append, pop = d.append, d.pop
433        for i in xrange(BIG):
434            append(i)
435        for i in reversed(xrange(BIG)):
436            x = pop()
437            if x != i:
438                self.assertEqual(x, i)
439        self.assertEqual(len(d), 0)
440
441    def test_big_stack_left(self):
442        d = deque()
443        append, pop = d.appendleft, d.popleft
444        for i in xrange(BIG):
445            append(i)
446        for i in reversed(xrange(BIG)):
447            x = pop()
448            if x != i:
449                self.assertEqual(x, i)
450        self.assertEqual(len(d), 0)
451
452    def test_roundtrip_iter_init(self):
453        d = deque(xrange(200))
454        e = deque(d)
455        self.assertNotEqual(id(d), id(e))
456        self.assertEqual(list(d), list(e))
457
458    def test_pickle(self):
459        d = deque(xrange(200))
460        for i in range(pickle.HIGHEST_PROTOCOL + 1):
461            s = pickle.dumps(d, i)
462            e = pickle.loads(s)
463            self.assertNotEqual(id(d), id(e))
464            self.assertEqual(list(d), list(e))
465
466##    def test_pickle_recursive(self):
467##        d = deque('abc')
468##        d.append(d)
469##        for i in range(pickle.HIGHEST_PROTOCOL + 1):
470##            e = pickle.loads(pickle.dumps(d, i))
471##            self.assertNotEqual(id(d), id(e))
472##            self.assertEqual(id(e), id(e[-1]))
473
474    def test_deepcopy(self):
475        mut = [10]
476        d = deque([mut])
477        e = copy.deepcopy(d)
478        self.assertEqual(list(d), list(e))
479        mut[0] = 11
480        self.assertNotEqual(id(d), id(e))
481        self.assertNotEqual(list(d), list(e))
482
483    def test_copy(self):
484        mut = [10]
485        d = deque([mut])
486        e = copy.copy(d)
487        self.assertEqual(list(d), list(e))
488        mut[0] = 11
489        self.assertNotEqual(id(d), id(e))
490        self.assertEqual(list(d), list(e))
491
492    def test_reversed(self):
493        for s in ('abcd', xrange(2000)):
494            self.assertEqual(list(reversed(deque(s))), list(reversed(s)))
495
496    def test_gc_doesnt_blowup(self):
497        import gc
498        # This used to assert-fail in deque_traverse() under a debug
499        # build, or run wild with a NULL pointer in a release build.
500        d = deque()
501        for i in xrange(100):
502            d.append(1)
503            gc.collect()
504
505    def test_container_iterator(self):
506        # Bug #3680: tp_traverse was not implemented for deque iterator objects
507        class C(object):
508            pass
509        for i in range(2):
510            obj = C()
511            ref = weakref.ref(obj)
512            if i == 0:
513                container = deque([obj, 1])
514            else:
515                container = reversed(deque([obj, 1]))
516            obj.x = iter(container)
517            del obj, container
518            gc.collect()
519            self.assertTrue(ref() is None, "Cycle was not collected")
520
521    check_sizeof = test_support.check_sizeof
522
523    @test_support.cpython_only
524    def test_sizeof(self):
525        BLOCKLEN = 62
526        basesize = test_support.calcobjsize('2P4PlP')
527        blocksize = struct.calcsize('2P%dP' % BLOCKLEN)
528        self.assertEqual(object.__sizeof__(deque()), basesize)
529        check = self.check_sizeof
530        check(deque(), basesize + blocksize)
531        check(deque('a'), basesize + blocksize)
532        check(deque('a' * (BLOCKLEN // 2)), basesize + blocksize)
533        check(deque('a' * (BLOCKLEN // 2 + 1)), basesize + 2 * blocksize)
534        check(deque('a' * (42 * BLOCKLEN)), basesize + 43 * blocksize)
535
536class TestVariousIteratorArgs(unittest.TestCase):
537
538    def test_constructor(self):
539        for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)):
540            for g in (seq_tests.Sequence, seq_tests.IterFunc,
541                      seq_tests.IterGen, seq_tests.IterFuncStop,
542                      seq_tests.itermulti, seq_tests.iterfunc):
543                self.assertEqual(list(deque(g(s))), list(g(s)))
544            self.assertRaises(TypeError, deque, seq_tests.IterNextOnly(s))
545            self.assertRaises(TypeError, deque, seq_tests.IterNoNext(s))
546            self.assertRaises(ZeroDivisionError, deque, seq_tests.IterGenExc(s))
547
548    def test_iter_with_altered_data(self):
549        d = deque('abcdefg')
550        it = iter(d)
551        d.pop()
552        self.assertRaises(RuntimeError, it.next)
553
554    def test_runtime_error_on_empty_deque(self):
555        d = deque()
556        it = iter(d)
557        d.append(10)
558        self.assertRaises(RuntimeError, it.next)
559
560class Deque(deque):
561    pass
562
563class DequeWithBadIter(deque):
564    def __iter__(self):
565        raise TypeError
566
567class TestSubclass(unittest.TestCase):
568
569    def test_basics(self):
570        d = Deque(xrange(25))
571        d.__init__(xrange(200))
572        for i in xrange(200, 400):
573            d.append(i)
574        for i in reversed(xrange(-200, 0)):
575            d.appendleft(i)
576        self.assertEqual(list(d), range(-200, 400))
577        self.assertEqual(len(d), 600)
578
579        left = [d.popleft() for i in xrange(250)]
580        self.assertEqual(left, range(-200, 50))
581        self.assertEqual(list(d), range(50, 400))
582
583        right = [d.pop() for i in xrange(250)]
584        right.reverse()
585        self.assertEqual(right, range(150, 400))
586        self.assertEqual(list(d), range(50, 150))
587
588        d.clear()
589        self.assertEqual(len(d), 0)
590
591    def test_copy_pickle(self):
592
593        d = Deque('abc')
594
595        e = d.__copy__()
596        self.assertEqual(type(d), type(e))
597        self.assertEqual(list(d), list(e))
598
599        e = Deque(d)
600        self.assertEqual(type(d), type(e))
601        self.assertEqual(list(d), list(e))
602
603        s = pickle.dumps(d)
604        e = pickle.loads(s)
605        self.assertNotEqual(id(d), id(e))
606        self.assertEqual(type(d), type(e))
607        self.assertEqual(list(d), list(e))
608
609        d = Deque('abcde', maxlen=4)
610
611        e = d.__copy__()
612        self.assertEqual(type(d), type(e))
613        self.assertEqual(list(d), list(e))
614
615        e = Deque(d)
616        self.assertEqual(type(d), type(e))
617        self.assertEqual(list(d), list(e))
618
619        s = pickle.dumps(d)
620        e = pickle.loads(s)
621        self.assertNotEqual(id(d), id(e))
622        self.assertEqual(type(d), type(e))
623        self.assertEqual(list(d), list(e))
624
625##    def test_pickle(self):
626##        d = Deque('abc')
627##        d.append(d)
628##
629##        e = pickle.loads(pickle.dumps(d))
630##        self.assertNotEqual(id(d), id(e))
631##        self.assertEqual(type(d), type(e))
632##        dd = d.pop()
633##        ee = e.pop()
634##        self.assertEqual(id(e), id(ee))
635##        self.assertEqual(d, e)
636##
637##        d.x = d
638##        e = pickle.loads(pickle.dumps(d))
639##        self.assertEqual(id(e), id(e.x))
640##
641##        d = DequeWithBadIter('abc')
642##        self.assertRaises(TypeError, pickle.dumps, d)
643
644    def test_weakref(self):
645        d = deque('gallahad')
646        p = weakref.proxy(d)
647        self.assertEqual(str(p), str(d))
648        d = None
649        self.assertRaises(ReferenceError, str, p)
650
651    def test_strange_subclass(self):
652        class X(deque):
653            def __iter__(self):
654                return iter([])
655        d1 = X([1,2,3])
656        d2 = X([4,5,6])
657        d1 == d2   # not clear if this is supposed to be True or False,
658                   # but it used to give a SystemError
659
660
661class SubclassWithKwargs(deque):
662    def __init__(self, newarg=1):
663        deque.__init__(self)
664
665class TestSubclassWithKwargs(unittest.TestCase):
666    def test_subclass_with_kwargs(self):
667        # SF bug #1486663 -- this used to erroneously raise a TypeError
668        SubclassWithKwargs(newarg=1)
669
670#==============================================================================
671
672libreftest = """
673Example from the Library Reference:  Doc/lib/libcollections.tex
674
675>>> from collections import deque
676>>> d = deque('ghi')                 # make a new deque with three items
677>>> for elem in d:                   # iterate over the deque's elements
678...     print elem.upper()
679G
680H
681I
682>>> d.append('j')                    # add a new entry to the right side
683>>> d.appendleft('f')                # add a new entry to the left side
684>>> d                                # show the representation of the deque
685deque(['f', 'g', 'h', 'i', 'j'])
686>>> d.pop()                          # return and remove the rightmost item
687'j'
688>>> d.popleft()                      # return and remove the leftmost item
689'f'
690>>> list(d)                          # list the contents of the deque
691['g', 'h', 'i']
692>>> d[0]                             # peek at leftmost item
693'g'
694>>> d[-1]                            # peek at rightmost item
695'i'
696>>> list(reversed(d))                # list the contents of a deque in reverse
697['i', 'h', 'g']
698>>> 'h' in d                         # search the deque
699True
700>>> d.extend('jkl')                  # add multiple elements at once
701>>> d
702deque(['g', 'h', 'i', 'j', 'k', 'l'])
703>>> d.rotate(1)                      # right rotation
704>>> d
705deque(['l', 'g', 'h', 'i', 'j', 'k'])
706>>> d.rotate(-1)                     # left rotation
707>>> d
708deque(['g', 'h', 'i', 'j', 'k', 'l'])
709>>> deque(reversed(d))               # make a new deque in reverse order
710deque(['l', 'k', 'j', 'i', 'h', 'g'])
711>>> d.clear()                        # empty the deque
712>>> d.pop()                          # cannot pop from an empty deque
713Traceback (most recent call last):
714  File "<pyshell#6>", line 1, in -toplevel-
715    d.pop()
716IndexError: pop from an empty deque
717
718>>> d.extendleft('abc')              # extendleft() reverses the input order
719>>> d
720deque(['c', 'b', 'a'])
721
722
723
724>>> def delete_nth(d, n):
725...     d.rotate(-n)
726...     d.popleft()
727...     d.rotate(n)
728...
729>>> d = deque('abcdef')
730>>> delete_nth(d, 2)   # remove the entry at d[2]
731>>> d
732deque(['a', 'b', 'd', 'e', 'f'])
733
734
735
736>>> def roundrobin(*iterables):
737...     pending = deque(iter(i) for i in iterables)
738...     while pending:
739...         task = pending.popleft()
740...         try:
741...             yield task.next()
742...         except StopIteration:
743...             continue
744...         pending.append(task)
745...
746
747>>> for value in roundrobin('abc', 'd', 'efgh'):
748...     print value
749...
750a
751d
752e
753b
754f
755c
756g
757h
758
759
760>>> def maketree(iterable):
761...     d = deque(iterable)
762...     while len(d) > 1:
763...         pair = [d.popleft(), d.popleft()]
764...         d.append(pair)
765...     return list(d)
766...
767>>> print maketree('abcdefgh')
768[[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]
769
770"""
771
772
773#==============================================================================
774
775__test__ = {'libreftest' : libreftest}
776
777def test_main(verbose=None):
778    import sys
779    test_classes = (
780        TestBasic,
781        TestVariousIteratorArgs,
782        TestSubclass,
783        TestSubclassWithKwargs,
784    )
785
786    test_support.run_unittest(*test_classes)
787
788    # verify reference counting
789    if verbose and hasattr(sys, "gettotalrefcount"):
790        import gc
791        counts = [None] * 5
792        for i in xrange(len(counts)):
793            test_support.run_unittest(*test_classes)
794            gc.collect()
795            counts[i] = sys.gettotalrefcount()
796        print counts
797
798    # doctests
799    from test import test_deque
800    test_support.run_doctest(test_deque, verbose)
801
802if __name__ == "__main__":
803    test_main(verbose=True)
804