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 import struct 10 11 BIG = 100000 12 13 def fail(): 14 raise SyntaxError 15 yield 1 16 17 class BadCmp: 18 def __eq__(self, other): 19 raise RuntimeError 20 21 class 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 29 class 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 empty 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('2P3PlPP') 527 blocksize = struct.calcsize('%dP2P' % 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 536 class 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 560 class Deque(deque): 561 pass 562 563 class DequeWithBadIter(deque): 564 def __iter__(self): 565 raise TypeError 566 567 class 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 for proto in range(pickle.HIGHEST_PROTOCOL + 1): 604 s = pickle.dumps(d, proto) 605 e = pickle.loads(s) 606 self.assertNotEqual(id(d), id(e)) 607 self.assertEqual(type(d), type(e)) 608 self.assertEqual(list(d), list(e)) 609 610 d = Deque('abcde', maxlen=4) 611 612 e = d.__copy__() 613 self.assertEqual(type(d), type(e)) 614 self.assertEqual(list(d), list(e)) 615 616 e = Deque(d) 617 self.assertEqual(type(d), type(e)) 618 self.assertEqual(list(d), list(e)) 619 620 for proto in range(pickle.HIGHEST_PROTOCOL + 1): 621 s = pickle.dumps(d, proto) 622 e = pickle.loads(s) 623 self.assertNotEqual(id(d), id(e)) 624 self.assertEqual(type(d), type(e)) 625 self.assertEqual(list(d), list(e)) 626 627 ## def test_pickle(self): 628 ## d = Deque('abc') 629 ## d.append(d) 630 ## 631 ## e = pickle.loads(pickle.dumps(d)) 632 ## self.assertNotEqual(id(d), id(e)) 633 ## self.assertEqual(type(d), type(e)) 634 ## dd = d.pop() 635 ## ee = e.pop() 636 ## self.assertEqual(id(e), id(ee)) 637 ## self.assertEqual(d, e) 638 ## 639 ## d.x = d 640 ## e = pickle.loads(pickle.dumps(d)) 641 ## self.assertEqual(id(e), id(e.x)) 642 ## 643 ## d = DequeWithBadIter('abc') 644 ## self.assertRaises(TypeError, pickle.dumps, d) 645 646 def test_weakref(self): 647 d = deque('gallahad') 648 p = weakref.proxy(d) 649 self.assertEqual(str(p), str(d)) 650 d = None 651 self.assertRaises(ReferenceError, str, p) 652 653 def test_strange_subclass(self): 654 class X(deque): 655 def __iter__(self): 656 return iter([]) 657 d1 = X([1,2,3]) 658 d2 = X([4,5,6]) 659 d1 == d2 # not clear if this is supposed to be True or False, 660 # but it used to give a SystemError 661 662 663 class SubclassWithKwargs(deque): 664 def __init__(self, newarg=1): 665 deque.__init__(self) 666 667 class TestSubclassWithKwargs(unittest.TestCase): 668 def test_subclass_with_kwargs(self): 669 # SF bug #1486663 -- this used to erroneously raise a TypeError 670 SubclassWithKwargs(newarg=1) 671 672 def test_free_after_iterating(self): 673 # For now, bypass tests that require slicing 674 self.skipTest("Exhausted deque iterator doesn't free a deque") 675 676 #============================================================================== 677 678 libreftest = """ 679 Example from the Library Reference: Doc/lib/libcollections.tex 680 681 >>> from collections import deque 682 >>> d = deque('ghi') # make a new deque with three items 683 >>> for elem in d: # iterate over the deque's elements 684 ... print elem.upper() 685 G 686 H 687 I 688 >>> d.append('j') # add a new entry to the right side 689 >>> d.appendleft('f') # add a new entry to the left side 690 >>> d # show the representation of the deque 691 deque(['f', 'g', 'h', 'i', 'j']) 692 >>> d.pop() # return and remove the rightmost item 693 'j' 694 >>> d.popleft() # return and remove the leftmost item 695 'f' 696 >>> list(d) # list the contents of the deque 697 ['g', 'h', 'i'] 698 >>> d[0] # peek at leftmost item 699 'g' 700 >>> d[-1] # peek at rightmost item 701 'i' 702 >>> list(reversed(d)) # list the contents of a deque in reverse 703 ['i', 'h', 'g'] 704 >>> 'h' in d # search the deque 705 True 706 >>> d.extend('jkl') # add multiple elements at once 707 >>> d 708 deque(['g', 'h', 'i', 'j', 'k', 'l']) 709 >>> d.rotate(1) # right rotation 710 >>> d 711 deque(['l', 'g', 'h', 'i', 'j', 'k']) 712 >>> d.rotate(-1) # left rotation 713 >>> d 714 deque(['g', 'h', 'i', 'j', 'k', 'l']) 715 >>> deque(reversed(d)) # make a new deque in reverse order 716 deque(['l', 'k', 'j', 'i', 'h', 'g']) 717 >>> d.clear() # empty the deque 718 >>> d.pop() # cannot pop from an empty deque 719 Traceback (most recent call last): 720 File "<pyshell#6>", line 1, in -toplevel- 721 d.pop() 722 IndexError: pop from an empty deque 723 724 >>> d.extendleft('abc') # extendleft() reverses the input order 725 >>> d 726 deque(['c', 'b', 'a']) 727 728 729 730 >>> def delete_nth(d, n): 731 ... d.rotate(-n) 732 ... d.popleft() 733 ... d.rotate(n) 734 ... 735 >>> d = deque('abcdef') 736 >>> delete_nth(d, 2) # remove the entry at d[2] 737 >>> d 738 deque(['a', 'b', 'd', 'e', 'f']) 739 740 741 742 >>> def roundrobin(*iterables): 743 ... pending = deque(iter(i) for i in iterables) 744 ... while pending: 745 ... task = pending.popleft() 746 ... try: 747 ... yield task.next() 748 ... except StopIteration: 749 ... continue 750 ... pending.append(task) 751 ... 752 753 >>> for value in roundrobin('abc', 'd', 'efgh'): 754 ... print value 755 ... 756 a 757 d 758 e 759 b 760 f 761 c 762 g 763 h 764 765 766 >>> def maketree(iterable): 767 ... d = deque(iterable) 768 ... while len(d) > 1: 769 ... pair = [d.popleft(), d.popleft()] 770 ... d.append(pair) 771 ... return list(d) 772 ... 773 >>> print maketree('abcdefgh') 774 [[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]] 775 776 """ 777 778 779 #============================================================================== 780 781 __test__ = {'libreftest' : libreftest} 782 783 def test_main(verbose=None): 784 import sys 785 test_classes = ( 786 TestBasic, 787 TestVariousIteratorArgs, 788 TestSubclass, 789 TestSubclassWithKwargs, 790 ) 791 792 test_support.run_unittest(*test_classes) 793 794 # verify reference counting 795 if verbose and hasattr(sys, "gettotalrefcount"): 796 import gc 797 counts = [None] * 5 798 for i in xrange(len(counts)): 799 test_support.run_unittest(*test_classes) 800 gc.collect() 801 counts[i] = sys.gettotalrefcount() 802 print counts 803 804 # doctests 805 from test import test_deque 806 test_support.run_doctest(test_deque, verbose) 807 808 if __name__ == "__main__": 809 test_main(verbose=True) 810
