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 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 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 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 661 class SubclassWithKwargs(deque): 662 def __init__(self, newarg=1): 663 deque.__init__(self) 664 665 class 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 672 libreftest = """ 673 Example 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() 679 G 680 H 681 I 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 685 deque(['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 699 True 700 >>> d.extend('jkl') # add multiple elements at once 701 >>> d 702 deque(['g', 'h', 'i', 'j', 'k', 'l']) 703 >>> d.rotate(1) # right rotation 704 >>> d 705 deque(['l', 'g', 'h', 'i', 'j', 'k']) 706 >>> d.rotate(-1) # left rotation 707 >>> d 708 deque(['g', 'h', 'i', 'j', 'k', 'l']) 709 >>> deque(reversed(d)) # make a new deque in reverse order 710 deque(['l', 'k', 'j', 'i', 'h', 'g']) 711 >>> d.clear() # empty the deque 712 >>> d.pop() # cannot pop from an empty deque 713 Traceback (most recent call last): 714 File "<pyshell#6>", line 1, in -toplevel- 715 d.pop() 716 IndexError: pop from an empty deque 717 718 >>> d.extendleft('abc') # extendleft() reverses the input order 719 >>> d 720 deque(['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 732 deque(['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 ... 750 a 751 d 752 e 753 b 754 f 755 c 756 g 757 h 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 777 def 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 802 if __name__ == "__main__": 803 test_main(verbose=True) 804
