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