1from collections import deque 2import unittest 3from test import test_support, seq_tests 4import gc 5import weakref 6import copy 7import cPickle as pickle 8import random 9import struct 10 11BIG = 100000 12 13def fail(): 14 raise SyntaxError 15 yield 1 16 17class BadCmp: 18 def __eq__(self, other): 19 raise RuntimeError 20 21class MutateCmp: 22 def __init__(self, deque, result): 23 self.deque = deque 24 self.result = result 25 def __eq__(self, other): 26 self.deque.clear() 27 return self.result 28 29class TestBasic(unittest.TestCase): 30 31 def test_basics(self): 32 d = deque(xrange(-5125, -5000)) 33 d.__init__(xrange(200)) 34 for i in xrange(200, 400): 35 d.append(i) 36 for i in reversed(xrange(-200, 0)): 37 d.appendleft(i) 38 self.assertEqual(list(d), range(-200, 400)) 39 self.assertEqual(len(d), 600) 40 41 left = [d.popleft() for i in xrange(250)] 42 self.assertEqual(left, range(-200, 50)) 43 self.assertEqual(list(d), range(50, 400)) 44 45 right = [d.pop() for i in xrange(250)] 46 right.reverse() 47 self.assertEqual(right, range(150, 400)) 48 self.assertEqual(list(d), range(50, 150)) 49 50 def test_maxlen(self): 51 self.assertRaises(ValueError, deque, 'abc', -1) 52 self.assertRaises(ValueError, deque, 'abc', -2) 53 it = iter(range(10)) 54 d = deque(it, maxlen=3) 55 self.assertEqual(list(it), []) 56 self.assertEqual(repr(d), 'deque([7, 8, 9], maxlen=3)') 57 self.assertEqual(list(d), range(7, 10)) 58 self.assertEqual(d, deque(range(10), 3)) 59 d.append(10) 60 self.assertEqual(list(d), range(8, 11)) 61 d.appendleft(7) 62 self.assertEqual(list(d), range(7, 10)) 63 d.extend([10, 11]) 64 self.assertEqual(list(d), range(9, 12)) 65 d.extendleft([8, 7]) 66 self.assertEqual(list(d), range(7, 10)) 67 d = deque(xrange(200), maxlen=10) 68 d.append(d) 69 test_support.unlink(test_support.TESTFN) 70 fo = open(test_support.TESTFN, "wb") 71 try: 72 print >> fo, d, 73 fo.close() 74 fo = open(test_support.TESTFN, "rb") 75 self.assertEqual(fo.read(), repr(d)) 76 finally: 77 fo.close() 78 test_support.unlink(test_support.TESTFN) 79 80 d = deque(range(10), maxlen=None) 81 self.assertEqual(repr(d), 'deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])') 82 fo = open(test_support.TESTFN, "wb") 83 try: 84 print >> fo, d, 85 fo.close() 86 fo = open(test_support.TESTFN, "rb") 87 self.assertEqual(fo.read(), repr(d)) 88 finally: 89 fo.close() 90 test_support.unlink(test_support.TESTFN) 91 92 def test_maxlen_zero(self): 93 it = iter(range(100)) 94 deque(it, maxlen=0) 95 self.assertEqual(list(it), []) 96 97 it = iter(range(100)) 98 d = deque(maxlen=0) 99 d.extend(it) 100 self.assertEqual(list(it), []) 101 102 it = iter(range(100)) 103 d = deque(maxlen=0) 104 d.extendleft(it) 105 self.assertEqual(list(it), []) 106 107 def test_maxlen_attribute(self): 108 self.assertEqual(deque().maxlen, None) 109 self.assertEqual(deque('abc').maxlen, None) 110 self.assertEqual(deque('abc', maxlen=4).maxlen, 4) 111 self.assertEqual(deque('abc', maxlen=2).maxlen, 2) 112 self.assertEqual(deque('abc', maxlen=0).maxlen, 0) 113 with self.assertRaises(AttributeError): 114 d = deque('abc') 115 d.maxlen = 10 116 117 def test_count(self): 118 for s in ('', 'abracadabra', 'simsalabim'*500+'abc'): 119 s = list(s) 120 d = deque(s) 121 for letter in 'abcdefghijklmnopqrstuvwxyz': 122 self.assertEqual(s.count(letter), d.count(letter), (s, d, letter)) 123 self.assertRaises(TypeError, d.count) # too few args 124 self.assertRaises(TypeError, d.count, 1, 2) # too many args 125 class BadCompare: 126 def __eq__(self, other): 127 raise ArithmeticError 128 d = deque([1, 2, BadCompare(), 3]) 129 self.assertRaises(ArithmeticError, d.count, 2) 130 d = deque([1, 2, 3]) 131 self.assertRaises(ArithmeticError, d.count, BadCompare()) 132 class MutatingCompare: 133 def __eq__(self, other): 134 self.d.pop() 135 return True 136 m = MutatingCompare() 137 d = deque([1, 2, 3, m, 4, 5]) 138 m.d = d 139 self.assertRaises(RuntimeError, d.count, 3) 140 141 # test issue11004 142 # block advance failed after rotation aligned elements on right side of block 143 d = deque([None]*16) 144 for i in range(len(d)): 145 d.rotate(-1) 146 d.rotate(1) 147 self.assertEqual(d.count(1), 0) 148 self.assertEqual(d.count(None), 16) 149 150 def test_comparisons(self): 151 d = deque('xabc'); d.popleft() 152 for e in [d, deque('abc'), deque('ab'), deque(), list(d)]: 153 self.assertEqual(d==e, type(d)==type(e) and list(d)==list(e)) 154 self.assertEqual(d!=e, not(type(d)==type(e) and list(d)==list(e))) 155 156 args = map(deque, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba')) 157 for x in args: 158 for y in args: 159 self.assertEqual(x == y, list(x) == list(y), (x,y)) 160 self.assertEqual(x != y, list(x) != list(y), (x,y)) 161 self.assertEqual(x < y, list(x) < list(y), (x,y)) 162 self.assertEqual(x <= y, list(x) <= list(y), (x,y)) 163 self.assertEqual(x > y, list(x) > list(y), (x,y)) 164 self.assertEqual(x >= y, list(x) >= list(y), (x,y)) 165 self.assertEqual(cmp(x,y), cmp(list(x),list(y)), (x,y)) 166 167 def test_extend(self): 168 d = deque('a') 169 self.assertRaises(TypeError, d.extend, 1) 170 d.extend('bcd') 171 self.assertEqual(list(d), list('abcd')) 172 d.extend(d) 173 self.assertEqual(list(d), list('abcdabcd')) 174 175 def test_iadd(self): 176 d = deque('a') 177 d += 'bcd' 178 self.assertEqual(list(d), list('abcd')) 179 d += d 180 self.assertEqual(list(d), list('abcdabcd')) 181 182 def test_extendleft(self): 183 d = deque('a') 184 self.assertRaises(TypeError, d.extendleft, 1) 185 d.extendleft('bcd') 186 self.assertEqual(list(d), list(reversed('abcd'))) 187 d.extendleft(d) 188 self.assertEqual(list(d), list('abcddcba')) 189 d = deque() 190 d.extendleft(range(1000)) 191 self.assertEqual(list(d), list(reversed(range(1000)))) 192 self.assertRaises(SyntaxError, d.extendleft, fail()) 193 194 def test_getitem(self): 195 n = 200 196 d = deque(xrange(n)) 197 l = range(n) 198 for i in xrange(n): 199 d.popleft() 200 l.pop(0) 201 if random.random() < 0.5: 202 d.append(i) 203 l.append(i) 204 for j in xrange(1-len(l), len(l)): 205 assert d[j] == l[j] 206 207 d = deque('superman') 208 self.assertEqual(d[0], 's') 209 self.assertEqual(d[-1], 'n') 210 d = deque() 211 self.assertRaises(IndexError, d.__getitem__, 0) 212 self.assertRaises(IndexError, d.__getitem__, -1) 213 214 def test_setitem(self): 215 n = 200 216 d = deque(xrange(n)) 217 for i in xrange(n): 218 d[i] = 10 * i 219 self.assertEqual(list(d), [10*i for i in xrange(n)]) 220 l = list(d) 221 for i in xrange(1-n, 0, -1): 222 d[i] = 7*i 223 l[i] = 7*i 224 self.assertEqual(list(d), l) 225 226 def test_delitem(self): 227 n = 500 # O(n**2) test, don't make this too big 228 d = deque(xrange(n)) 229 self.assertRaises(IndexError, d.__delitem__, -n-1) 230 self.assertRaises(IndexError, d.__delitem__, n) 231 for i in xrange(n): 232 self.assertEqual(len(d), n-i) 233 j = random.randrange(-len(d), len(d)) 234 val = d[j] 235 self.assertIn(val, d) 236 del d[j] 237 self.assertNotIn(val, d) 238 self.assertEqual(len(d), 0) 239 240 def test_reverse(self): 241 n = 500 # O(n**2) test, don't make this too big 242 data = [random.random() for i in range(n)] 243 for i in range(n): 244 d = deque(data[:i]) 245 r = d.reverse() 246 self.assertEqual(list(d), list(reversed(data[:i]))) 247 self.assertIs(r, None) 248 d.reverse() 249 self.assertEqual(list(d), data[:i]) 250 self.assertRaises(TypeError, d.reverse, 1) # Arity is zero 251 252 def test_rotate(self): 253 s = tuple('abcde') 254 n = len(s) 255 256 d = deque(s) 257 d.rotate(1) # verify rot(1) 258 self.assertEqual(''.join(d), 'eabcd') 259 260 d = deque(s) 261 d.rotate(-1) # verify rot(-1) 262 self.assertEqual(''.join(d), 'bcdea') 263 d.rotate() # check default to 1 264 self.assertEqual(tuple(d), s) 265 266 for i in xrange(n*3): 267 d = deque(s) 268 e = deque(d) 269 d.rotate(i) # check vs. rot(1) n times 270 for j in xrange(i): 271 e.rotate(1) 272 self.assertEqual(tuple(d), tuple(e)) 273 d.rotate(-i) # check that it works in reverse 274 self.assertEqual(tuple(d), s) 275 e.rotate(n-i) # check that it wraps forward 276 self.assertEqual(tuple(e), s) 277 278 for i in xrange(n*3): 279 d = deque(s) 280 e = deque(d) 281 d.rotate(-i) 282 for j in xrange(i): 283 e.rotate(-1) # check vs. rot(-1) n times 284 self.assertEqual(tuple(d), tuple(e)) 285 d.rotate(i) # check that it works in reverse 286 self.assertEqual(tuple(d), s) 287 e.rotate(i-n) # check that it wraps backaround 288 self.assertEqual(tuple(e), s) 289 290 d = deque(s) 291 e = deque(s) 292 e.rotate(BIG+17) # verify on long series of rotates 293 dr = d.rotate 294 for i in xrange(BIG+17): 295 dr() 296 self.assertEqual(tuple(d), tuple(e)) 297 298 self.assertRaises(TypeError, d.rotate, 'x') # Wrong arg type 299 self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args 300 301 d = deque() 302 d.rotate() # rotate an empty deque 303 self.assertEqual(d, deque()) 304 305 def test_len(self): 306 d = deque('ab') 307 self.assertEqual(len(d), 2) 308 d.popleft() 309 self.assertEqual(len(d), 1) 310 d.pop() 311 self.assertEqual(len(d), 0) 312 self.assertRaises(IndexError, d.pop) 313 self.assertEqual(len(d), 0) 314 d.append('c') 315 self.assertEqual(len(d), 1) 316 d.appendleft('d') 317 self.assertEqual(len(d), 2) 318 d.clear() 319 self.assertEqual(len(d), 0) 320 321 def test_underflow(self): 322 d = deque() 323 self.assertRaises(IndexError, d.pop) 324 self.assertRaises(IndexError, d.popleft) 325 326 def test_clear(self): 327 d = deque(xrange(100)) 328 self.assertEqual(len(d), 100) 329 d.clear() 330 self.assertEqual(len(d), 0) 331 self.assertEqual(list(d), []) 332 d.clear() # clear an 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 536class TestVariousIteratorArgs(unittest.TestCase): 537 538 def test_constructor(self): 539 for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)): 540 for g in (seq_tests.Sequence, seq_tests.IterFunc, 541 seq_tests.IterGen, seq_tests.IterFuncStop, 542 seq_tests.itermulti, seq_tests.iterfunc): 543 self.assertEqual(list(deque(g(s))), list(g(s))) 544 self.assertRaises(TypeError, deque, seq_tests.IterNextOnly(s)) 545 self.assertRaises(TypeError, deque, seq_tests.IterNoNext(s)) 546 self.assertRaises(ZeroDivisionError, deque, seq_tests.IterGenExc(s)) 547 548 def test_iter_with_altered_data(self): 549 d = deque('abcdefg') 550 it = iter(d) 551 d.pop() 552 self.assertRaises(RuntimeError, it.next) 553 554 def test_runtime_error_on_empty_deque(self): 555 d = deque() 556 it = iter(d) 557 d.append(10) 558 self.assertRaises(RuntimeError, it.next) 559 560class Deque(deque): 561 pass 562 563class DequeWithBadIter(deque): 564 def __iter__(self): 565 raise TypeError 566 567class TestSubclass(unittest.TestCase): 568 569 def test_basics(self): 570 d = Deque(xrange(25)) 571 d.__init__(xrange(200)) 572 for i in xrange(200, 400): 573 d.append(i) 574 for i in reversed(xrange(-200, 0)): 575 d.appendleft(i) 576 self.assertEqual(list(d), range(-200, 400)) 577 self.assertEqual(len(d), 600) 578 579 left = [d.popleft() for i in xrange(250)] 580 self.assertEqual(left, range(-200, 50)) 581 self.assertEqual(list(d), range(50, 400)) 582 583 right = [d.pop() for i in xrange(250)] 584 right.reverse() 585 self.assertEqual(right, range(150, 400)) 586 self.assertEqual(list(d), range(50, 150)) 587 588 d.clear() 589 self.assertEqual(len(d), 0) 590 591 def test_copy_pickle(self): 592 593 d = Deque('abc') 594 595 e = d.__copy__() 596 self.assertEqual(type(d), type(e)) 597 self.assertEqual(list(d), list(e)) 598 599 e = Deque(d) 600 self.assertEqual(type(d), type(e)) 601 self.assertEqual(list(d), list(e)) 602 603 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 @test_support.cpython_only 663 def test_bug_31608(self): 664 # The interpreter used to crash in specific cases where a deque 665 # subclass returned a non-deque. 666 class X(deque): 667 pass 668 d = X() 669 def bad___new__(cls, *args, **kwargs): 670 return [42] 671 X.__new__ = bad___new__ 672 with self.assertRaises(TypeError): 673 d * 42 # shouldn't crash 674 with self.assertRaises(TypeError): 675 d + deque([1, 2, 3]) # shouldn't crash 676 677 678class SubclassWithKwargs(deque): 679 def __init__(self, newarg=1): 680 deque.__init__(self) 681 682class TestSubclassWithKwargs(unittest.TestCase): 683 def test_subclass_with_kwargs(self): 684 # SF bug #1486663 -- this used to erroneously raise a TypeError 685 SubclassWithKwargs(newarg=1) 686 687 def test_free_after_iterating(self): 688 # For now, bypass tests that require slicing 689 self.skipTest("Exhausted deque iterator doesn't free a deque") 690 691#============================================================================== 692 693libreftest = """ 694Example from the Library Reference: Doc/lib/libcollections.tex 695 696>>> from collections import deque 697>>> d = deque('ghi') # make a new deque with three items 698>>> for elem in d: # iterate over the deque's elements 699... print elem.upper() 700G 701H 702I 703>>> d.append('j') # add a new entry to the right side 704>>> d.appendleft('f') # add a new entry to the left side 705>>> d # show the representation of the deque 706deque(['f', 'g', 'h', 'i', 'j']) 707>>> d.pop() # return and remove the rightmost item 708'j' 709>>> d.popleft() # return and remove the leftmost item 710'f' 711>>> list(d) # list the contents of the deque 712['g', 'h', 'i'] 713>>> d[0] # peek at leftmost item 714'g' 715>>> d[-1] # peek at rightmost item 716'i' 717>>> list(reversed(d)) # list the contents of a deque in reverse 718['i', 'h', 'g'] 719>>> 'h' in d # search the deque 720True 721>>> d.extend('jkl') # add multiple elements at once 722>>> d 723deque(['g', 'h', 'i', 'j', 'k', 'l']) 724>>> d.rotate(1) # right rotation 725>>> d 726deque(['l', 'g', 'h', 'i', 'j', 'k']) 727>>> d.rotate(-1) # left rotation 728>>> d 729deque(['g', 'h', 'i', 'j', 'k', 'l']) 730>>> deque(reversed(d)) # make a new deque in reverse order 731deque(['l', 'k', 'j', 'i', 'h', 'g']) 732>>> d.clear() # empty the deque 733>>> d.pop() # cannot pop from an empty deque 734Traceback (most recent call last): 735 File "<pyshell#6>", line 1, in -toplevel- 736 d.pop() 737IndexError: pop from an empty deque 738 739>>> d.extendleft('abc') # extendleft() reverses the input order 740>>> d 741deque(['c', 'b', 'a']) 742 743 744 745>>> def delete_nth(d, n): 746... d.rotate(-n) 747... d.popleft() 748... d.rotate(n) 749... 750>>> d = deque('abcdef') 751>>> delete_nth(d, 2) # remove the entry at d[2] 752>>> d 753deque(['a', 'b', 'd', 'e', 'f']) 754 755 756 757>>> def roundrobin(*iterables): 758... pending = deque(iter(i) for i in iterables) 759... while pending: 760... task = pending.popleft() 761... try: 762... yield task.next() 763... except StopIteration: 764... continue 765... pending.append(task) 766... 767 768>>> for value in roundrobin('abc', 'd', 'efgh'): 769... print value 770... 771a 772d 773e 774b 775f 776c 777g 778h 779 780 781>>> def maketree(iterable): 782... d = deque(iterable) 783... while len(d) > 1: 784... pair = [d.popleft(), d.popleft()] 785... d.append(pair) 786... return list(d) 787... 788>>> print maketree('abcdefgh') 789[[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]] 790 791""" 792 793 794#============================================================================== 795 796__test__ = {'libreftest' : libreftest} 797 798def test_main(verbose=None): 799 import sys 800 test_classes = ( 801 TestBasic, 802 TestVariousIteratorArgs, 803 TestSubclass, 804 TestSubclassWithKwargs, 805 ) 806 807 test_support.run_unittest(*test_classes) 808 809 # verify reference counting 810 if verbose and hasattr(sys, "gettotalrefcount"): 811 import gc 812 counts = [None] * 5 813 for i in xrange(len(counts)): 814 test_support.run_unittest(*test_classes) 815 gc.collect() 816 counts[i] = sys.gettotalrefcount() 817 print counts 818 819 # doctests 820 from test import test_deque 821 test_support.run_doctest(test_deque, verbose) 822 823if __name__ == "__main__": 824 test_main(verbose=True) 825