Lib/test/test_deque.py

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