1from collections import deque 2import unittest 3from test import support, seq_tests 4import gc 5import weakref 6import copy 7import 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(range(-5125, -5000)) 33 d.__init__(range(200)) 34 for i in range(200, 400): 35 d.append(i) 36 for i in reversed(range(-200, 0)): 37 d.appendleft(i) 38 self.assertEqual(list(d), list(range(-200, 400))) 39 self.assertEqual(len(d), 600) 40 41 left = [d.popleft() for i in range(250)] 42 self.assertEqual(left, list(range(-200, 50))) 43 self.assertEqual(list(d), list(range(50, 400))) 44 45 right = [d.pop() for i in range(250)] 46 right.reverse() 47 self.assertEqual(right, list(range(150, 400))) 48 self.assertEqual(list(d), list(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), [7, 8, 9]) 58 self.assertEqual(d, deque(range(10), 3)) 59 d.append(10) 60 self.assertEqual(list(d), [8, 9, 10]) 61 d.appendleft(7) 62 self.assertEqual(list(d), [7, 8, 9]) 63 d.extend([10, 11]) 64 self.assertEqual(list(d), [9, 10, 11]) 65 d.extendleft([8, 7]) 66 self.assertEqual(list(d), [7, 8, 9]) 67 d = deque(range(200), maxlen=10) 68 d.append(d) 69 support.unlink(support.TESTFN) 70 fo = open(support.TESTFN, "w") 71 try: 72 fo.write(str(d)) 73 fo.close() 74 fo = open(support.TESTFN, "r") 75 self.assertEqual(fo.read(), repr(d)) 76 finally: 77 fo.close() 78 support.unlink(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(support.TESTFN, "w") 83 try: 84 fo.write(str(d)) 85 fo.close() 86 fo = open(support.TESTFN, "r") 87 self.assertEqual(fo.read(), repr(d)) 88 finally: 89 fo.close() 90 support.unlink(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 166 def test_contains(self): 167 n = 200 168 169 d = deque(range(n)) 170 for i in range(n): 171 self.assertTrue(i in d) 172 self.assertTrue((n+1) not in d) 173 174 # Test detection of mutation during iteration 175 d = deque(range(n)) 176 d[n//2] = MutateCmp(d, False) 177 with self.assertRaises(RuntimeError): 178 n in d 179 180 # Test detection of comparison exceptions 181 d = deque(range(n)) 182 d[n//2] = BadCmp() 183 with self.assertRaises(RuntimeError): 184 n in d 185 186 def test_extend(self): 187 d = deque('a') 188 self.assertRaises(TypeError, d.extend, 1) 189 d.extend('bcd') 190 self.assertEqual(list(d), list('abcd')) 191 d.extend(d) 192 self.assertEqual(list(d), list('abcdabcd')) 193 194 def test_add(self): 195 d = deque() 196 e = deque('abc') 197 f = deque('def') 198 self.assertEqual(d + d, deque()) 199 self.assertEqual(e + f, deque('abcdef')) 200 self.assertEqual(e + e, deque('abcabc')) 201 self.assertEqual(e + d, deque('abc')) 202 self.assertEqual(d + e, deque('abc')) 203 self.assertIsNot(d + d, deque()) 204 self.assertIsNot(e + d, deque('abc')) 205 self.assertIsNot(d + e, deque('abc')) 206 207 g = deque('abcdef', maxlen=4) 208 h = deque('gh') 209 self.assertEqual(g + h, deque('efgh')) 210 211 with self.assertRaises(TypeError): 212 deque('abc') + 'def' 213 214 def test_iadd(self): 215 d = deque('a') 216 d += 'bcd' 217 self.assertEqual(list(d), list('abcd')) 218 d += d 219 self.assertEqual(list(d), list('abcdabcd')) 220 221 def test_extendleft(self): 222 d = deque('a') 223 self.assertRaises(TypeError, d.extendleft, 1) 224 d.extendleft('bcd') 225 self.assertEqual(list(d), list(reversed('abcd'))) 226 d.extendleft(d) 227 self.assertEqual(list(d), list('abcddcba')) 228 d = deque() 229 d.extendleft(range(1000)) 230 self.assertEqual(list(d), list(reversed(range(1000)))) 231 self.assertRaises(SyntaxError, d.extendleft, fail()) 232 233 def test_getitem(self): 234 n = 200 235 d = deque(range(n)) 236 l = list(range(n)) 237 for i in range(n): 238 d.popleft() 239 l.pop(0) 240 if random.random() < 0.5: 241 d.append(i) 242 l.append(i) 243 for j in range(1-len(l), len(l)): 244 assert d[j] == l[j] 245 246 d = deque('superman') 247 self.assertEqual(d[0], 's') 248 self.assertEqual(d[-1], 'n') 249 d = deque() 250 self.assertRaises(IndexError, d.__getitem__, 0) 251 self.assertRaises(IndexError, d.__getitem__, -1) 252 253 def test_index(self): 254 for n in 1, 2, 30, 40, 200: 255 256 d = deque(range(n)) 257 for i in range(n): 258 self.assertEqual(d.index(i), i) 259 260 with self.assertRaises(ValueError): 261 d.index(n+1) 262 263 # Test detection of mutation during iteration 264 d = deque(range(n)) 265 d[n//2] = MutateCmp(d, False) 266 with self.assertRaises(RuntimeError): 267 d.index(n) 268 269 # Test detection of comparison exceptions 270 d = deque(range(n)) 271 d[n//2] = BadCmp() 272 with self.assertRaises(RuntimeError): 273 d.index(n) 274 275 # Test start and stop arguments behavior matches list.index() 276 elements = 'ABCDEFGHI' 277 nonelement = 'Z' 278 d = deque(elements * 2) 279 s = list(elements * 2) 280 for start in range(-5 - len(s)*2, 5 + len(s) * 2): 281 for stop in range(-5 - len(s)*2, 5 + len(s) * 2): 282 for element in elements + 'Z': 283 try: 284 target = s.index(element, start, stop) 285 except ValueError: 286 with self.assertRaises(ValueError): 287 d.index(element, start, stop) 288 else: 289 self.assertEqual(d.index(element, start, stop), target) 290 291 # Test large start argument 292 d = deque(range(0, 10000, 10)) 293 for step in range(100): 294 i = d.index(8500, 700) 295 self.assertEqual(d[i], 8500) 296 # Repeat test with a different internal offset 297 d.rotate() 298 299 def test_index_bug_24913(self): 300 d = deque('A' * 3) 301 with self.assertRaises(ValueError): 302 i = d.index("Hello world", 0, 4) 303 304 def test_insert(self): 305 # Test to make sure insert behaves like lists 306 elements = 'ABCDEFGHI' 307 for i in range(-5 - len(elements)*2, 5 + len(elements) * 2): 308 d = deque('ABCDEFGHI') 309 s = list('ABCDEFGHI') 310 d.insert(i, 'Z') 311 s.insert(i, 'Z') 312 self.assertEqual(list(d), s) 313 314 def test_insert_bug_26194(self): 315 data = 'ABC' 316 d = deque(data, maxlen=len(data)) 317 with self.assertRaises(IndexError): 318 d.insert(2, None) 319 320 elements = 'ABCDEFGHI' 321 for i in range(-len(elements), len(elements)): 322 d = deque(elements, maxlen=len(elements)+1) 323 d.insert(i, 'Z') 324 if i >= 0: 325 self.assertEqual(d[i], 'Z') 326 else: 327 self.assertEqual(d[i-1], 'Z') 328 329 def test_imul(self): 330 for n in (-10, -1, 0, 1, 2, 10, 1000): 331 d = deque() 332 d *= n 333 self.assertEqual(d, deque()) 334 self.assertIsNone(d.maxlen) 335 336 for n in (-10, -1, 0, 1, 2, 10, 1000): 337 d = deque('a') 338 d *= n 339 self.assertEqual(d, deque('a' * n)) 340 self.assertIsNone(d.maxlen) 341 342 for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000): 343 d = deque('a', 500) 344 d *= n 345 self.assertEqual(d, deque('a' * min(n, 500))) 346 self.assertEqual(d.maxlen, 500) 347 348 for n in (-10, -1, 0, 1, 2, 10, 1000): 349 d = deque('abcdef') 350 d *= n 351 self.assertEqual(d, deque('abcdef' * n)) 352 self.assertIsNone(d.maxlen) 353 354 for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000): 355 d = deque('abcdef', 500) 356 d *= n 357 self.assertEqual(d, deque(('abcdef' * n)[-500:])) 358 self.assertEqual(d.maxlen, 500) 359 360 def test_mul(self): 361 d = deque('abc') 362 self.assertEqual(d * -5, deque()) 363 self.assertEqual(d * 0, deque()) 364 self.assertEqual(d * 1, deque('abc')) 365 self.assertEqual(d * 2, deque('abcabc')) 366 self.assertEqual(d * 3, deque('abcabcabc')) 367 self.assertIsNot(d * 1, d) 368 369 self.assertEqual(deque() * 0, deque()) 370 self.assertEqual(deque() * 1, deque()) 371 self.assertEqual(deque() * 5, deque()) 372 373 self.assertEqual(-5 * d, deque()) 374 self.assertEqual(0 * d, deque()) 375 self.assertEqual(1 * d, deque('abc')) 376 self.assertEqual(2 * d, deque('abcabc')) 377 self.assertEqual(3 * d, deque('abcabcabc')) 378 379 d = deque('abc', maxlen=5) 380 self.assertEqual(d * -5, deque()) 381 self.assertEqual(d * 0, deque()) 382 self.assertEqual(d * 1, deque('abc')) 383 self.assertEqual(d * 2, deque('bcabc')) 384 self.assertEqual(d * 30, deque('bcabc')) 385 386 def test_setitem(self): 387 n = 200 388 d = deque(range(n)) 389 for i in range(n): 390 d[i] = 10 * i 391 self.assertEqual(list(d), [10*i for i in range(n)]) 392 l = list(d) 393 for i in range(1-n, 0, -1): 394 d[i] = 7*i 395 l[i] = 7*i 396 self.assertEqual(list(d), l) 397 398 def test_delitem(self): 399 n = 500 # O(n**2) test, don't make this too big 400 d = deque(range(n)) 401 self.assertRaises(IndexError, d.__delitem__, -n-1) 402 self.assertRaises(IndexError, d.__delitem__, n) 403 for i in range(n): 404 self.assertEqual(len(d), n-i) 405 j = random.randrange(-len(d), len(d)) 406 val = d[j] 407 self.assertIn(val, d) 408 del d[j] 409 self.assertNotIn(val, d) 410 self.assertEqual(len(d), 0) 411 412 def test_reverse(self): 413 n = 500 # O(n**2) test, don't make this too big 414 data = [random.random() for i in range(n)] 415 for i in range(n): 416 d = deque(data[:i]) 417 r = d.reverse() 418 self.assertEqual(list(d), list(reversed(data[:i]))) 419 self.assertIs(r, None) 420 d.reverse() 421 self.assertEqual(list(d), data[:i]) 422 self.assertRaises(TypeError, d.reverse, 1) # Arity is zero 423 424 def test_rotate(self): 425 s = tuple('abcde') 426 n = len(s) 427 428 d = deque(s) 429 d.rotate(1) # verify rot(1) 430 self.assertEqual(''.join(d), 'eabcd') 431 432 d = deque(s) 433 d.rotate(-1) # verify rot(-1) 434 self.assertEqual(''.join(d), 'bcdea') 435 d.rotate() # check default to 1 436 self.assertEqual(tuple(d), s) 437 438 for i in range(n*3): 439 d = deque(s) 440 e = deque(d) 441 d.rotate(i) # check vs. rot(1) n times 442 for j in range(i): 443 e.rotate(1) 444 self.assertEqual(tuple(d), tuple(e)) 445 d.rotate(-i) # check that it works in reverse 446 self.assertEqual(tuple(d), s) 447 e.rotate(n-i) # check that it wraps forward 448 self.assertEqual(tuple(e), s) 449 450 for i in range(n*3): 451 d = deque(s) 452 e = deque(d) 453 d.rotate(-i) 454 for j in range(i): 455 e.rotate(-1) # check vs. rot(-1) n times 456 self.assertEqual(tuple(d), tuple(e)) 457 d.rotate(i) # check that it works in reverse 458 self.assertEqual(tuple(d), s) 459 e.rotate(i-n) # check that it wraps backaround 460 self.assertEqual(tuple(e), s) 461 462 d = deque(s) 463 e = deque(s) 464 e.rotate(BIG+17) # verify on long series of rotates 465 dr = d.rotate 466 for i in range(BIG+17): 467 dr() 468 self.assertEqual(tuple(d), tuple(e)) 469 470 self.assertRaises(TypeError, d.rotate, 'x') # Wrong arg type 471 self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args 472 473 d = deque() 474 d.rotate() # rotate an empty deque 475 self.assertEqual(d, deque()) 476 477 def test_len(self): 478 d = deque('ab') 479 self.assertEqual(len(d), 2) 480 d.popleft() 481 self.assertEqual(len(d), 1) 482 d.pop() 483 self.assertEqual(len(d), 0) 484 self.assertRaises(IndexError, d.pop) 485 self.assertEqual(len(d), 0) 486 d.append('c') 487 self.assertEqual(len(d), 1) 488 d.appendleft('d') 489 self.assertEqual(len(d), 2) 490 d.clear() 491 self.assertEqual(len(d), 0) 492 493 def test_underflow(self): 494 d = deque() 495 self.assertRaises(IndexError, d.pop) 496 self.assertRaises(IndexError, d.popleft) 497 498 def test_clear(self): 499 d = deque(range(100)) 500 self.assertEqual(len(d), 100) 501 d.clear() 502 self.assertEqual(len(d), 0) 503 self.assertEqual(list(d), []) 504 d.clear() # clear an empty deque 505 self.assertEqual(list(d), []) 506 507 def test_remove(self): 508 d = deque('abcdefghcij') 509 d.remove('c') 510 self.assertEqual(d, deque('abdefghcij')) 511 d.remove('c') 512 self.assertEqual(d, deque('abdefghij')) 513 self.assertRaises(ValueError, d.remove, 'c') 514 self.assertEqual(d, deque('abdefghij')) 515 516 # Handle comparison errors 517 d = deque(['a', 'b', BadCmp(), 'c']) 518 e = deque(d) 519 self.assertRaises(RuntimeError, d.remove, 'c') 520 for x, y in zip(d, e): 521 # verify that original order and values are retained. 522 self.assertTrue(x is y) 523 524 # Handle evil mutator 525 for match in (True, False): 526 d = deque(['ab']) 527 d.extend([MutateCmp(d, match), 'c']) 528 self.assertRaises(IndexError, d.remove, 'c') 529 self.assertEqual(d, deque()) 530 531 def test_repr(self): 532 d = deque(range(200)) 533 e = eval(repr(d)) 534 self.assertEqual(list(d), list(e)) 535 d.append(d) 536 self.assertIn('...', repr(d)) 537 538 def test_print(self): 539 d = deque(range(200)) 540 d.append(d) 541 try: 542 support.unlink(support.TESTFN) 543 fo = open(support.TESTFN, "w") 544 print(d, file=fo, end='') 545 fo.close() 546 fo = open(support.TESTFN, "r") 547 self.assertEqual(fo.read(), repr(d)) 548 finally: 549 fo.close() 550 support.unlink(support.TESTFN) 551 552 def test_init(self): 553 self.assertRaises(TypeError, deque, 'abc', 2, 3); 554 self.assertRaises(TypeError, deque, 1); 555 556 def test_hash(self): 557 self.assertRaises(TypeError, hash, deque('abc')) 558 559 def test_long_steadystate_queue_popleft(self): 560 for size in (0, 1, 2, 100, 1000): 561 d = deque(range(size)) 562 append, pop = d.append, d.popleft 563 for i in range(size, BIG): 564 append(i) 565 x = pop() 566 if x != i - size: 567 self.assertEqual(x, i-size) 568 self.assertEqual(list(d), list(range(BIG-size, BIG))) 569 570 def test_long_steadystate_queue_popright(self): 571 for size in (0, 1, 2, 100, 1000): 572 d = deque(reversed(range(size))) 573 append, pop = d.appendleft, d.pop 574 for i in range(size, BIG): 575 append(i) 576 x = pop() 577 if x != i - size: 578 self.assertEqual(x, i-size) 579 self.assertEqual(list(reversed(list(d))), 580 list(range(BIG-size, BIG))) 581 582 def test_big_queue_popleft(self): 583 pass 584 d = deque() 585 append, pop = d.append, d.popleft 586 for i in range(BIG): 587 append(i) 588 for i in range(BIG): 589 x = pop() 590 if x != i: 591 self.assertEqual(x, i) 592 593 def test_big_queue_popright(self): 594 d = deque() 595 append, pop = d.appendleft, d.pop 596 for i in range(BIG): 597 append(i) 598 for i in range(BIG): 599 x = pop() 600 if x != i: 601 self.assertEqual(x, i) 602 603 def test_big_stack_right(self): 604 d = deque() 605 append, pop = d.append, d.pop 606 for i in range(BIG): 607 append(i) 608 for i in reversed(range(BIG)): 609 x = pop() 610 if x != i: 611 self.assertEqual(x, i) 612 self.assertEqual(len(d), 0) 613 614 def test_big_stack_left(self): 615 d = deque() 616 append, pop = d.appendleft, d.popleft 617 for i in range(BIG): 618 append(i) 619 for i in reversed(range(BIG)): 620 x = pop() 621 if x != i: 622 self.assertEqual(x, i) 623 self.assertEqual(len(d), 0) 624 625 def test_roundtrip_iter_init(self): 626 d = deque(range(200)) 627 e = deque(d) 628 self.assertNotEqual(id(d), id(e)) 629 self.assertEqual(list(d), list(e)) 630 631 def test_pickle(self): 632 for d in deque(range(200)), deque(range(200), 100): 633 for i in range(pickle.HIGHEST_PROTOCOL + 1): 634 s = pickle.dumps(d, i) 635 e = pickle.loads(s) 636 self.assertNotEqual(id(e), id(d)) 637 self.assertEqual(list(e), list(d)) 638 self.assertEqual(e.maxlen, d.maxlen) 639 640 def test_pickle_recursive(self): 641 for d in deque('abc'), deque('abc', 3): 642 d.append(d) 643 for i in range(pickle.HIGHEST_PROTOCOL + 1): 644 e = pickle.loads(pickle.dumps(d, i)) 645 self.assertNotEqual(id(e), id(d)) 646 self.assertEqual(id(e[-1]), id(e)) 647 self.assertEqual(e.maxlen, d.maxlen) 648 649 def test_iterator_pickle(self): 650 orig = deque(range(200)) 651 data = [i*1.01 for i in orig] 652 for proto in range(pickle.HIGHEST_PROTOCOL + 1): 653 # initial iterator 654 itorg = iter(orig) 655 dump = pickle.dumps((itorg, orig), proto) 656 it, d = pickle.loads(dump) 657 for i, x in enumerate(data): 658 d[i] = x 659 self.assertEqual(type(it), type(itorg)) 660 self.assertEqual(list(it), data) 661 662 # running iterator 663 next(itorg) 664 dump = pickle.dumps((itorg, orig), proto) 665 it, d = pickle.loads(dump) 666 for i, x in enumerate(data): 667 d[i] = x 668 self.assertEqual(type(it), type(itorg)) 669 self.assertEqual(list(it), data[1:]) 670 671 # empty iterator 672 for i in range(1, len(data)): 673 next(itorg) 674 dump = pickle.dumps((itorg, orig), proto) 675 it, d = pickle.loads(dump) 676 for i, x in enumerate(data): 677 d[i] = x 678 self.assertEqual(type(it), type(itorg)) 679 self.assertEqual(list(it), []) 680 681 # exhausted iterator 682 self.assertRaises(StopIteration, next, itorg) 683 dump = pickle.dumps((itorg, orig), proto) 684 it, d = pickle.loads(dump) 685 for i, x in enumerate(data): 686 d[i] = x 687 self.assertEqual(type(it), type(itorg)) 688 self.assertEqual(list(it), []) 689 690 def test_deepcopy(self): 691 mut = [10] 692 d = deque([mut]) 693 e = copy.deepcopy(d) 694 self.assertEqual(list(d), list(e)) 695 mut[0] = 11 696 self.assertNotEqual(id(d), id(e)) 697 self.assertNotEqual(list(d), list(e)) 698 699 def test_copy(self): 700 mut = [10] 701 d = deque([mut]) 702 e = copy.copy(d) 703 self.assertEqual(list(d), list(e)) 704 mut[0] = 11 705 self.assertNotEqual(id(d), id(e)) 706 self.assertEqual(list(d), list(e)) 707 708 for i in range(5): 709 for maxlen in range(-1, 6): 710 s = [random.random() for j in range(i)] 711 d = deque(s) if maxlen == -1 else deque(s, maxlen) 712 e = d.copy() 713 self.assertEqual(d, e) 714 self.assertEqual(d.maxlen, e.maxlen) 715 self.assertTrue(all(x is y for x, y in zip(d, e))) 716 717 def test_copy_method(self): 718 mut = [10] 719 d = deque([mut]) 720 e = d.copy() 721 self.assertEqual(list(d), list(e)) 722 mut[0] = 11 723 self.assertNotEqual(id(d), id(e)) 724 self.assertEqual(list(d), list(e)) 725 726 def test_reversed(self): 727 for s in ('abcd', range(2000)): 728 self.assertEqual(list(reversed(deque(s))), list(reversed(s))) 729 730 def test_reversed_new(self): 731 klass = type(reversed(deque())) 732 for s in ('abcd', range(2000)): 733 self.assertEqual(list(klass(deque(s))), list(reversed(s))) 734 735 def test_gc_doesnt_blowup(self): 736 import gc 737 # This used to assert-fail in deque_traverse() under a debug 738 # build, or run wild with a NULL pointer in a release build. 739 d = deque() 740 for i in range(100): 741 d.append(1) 742 gc.collect() 743 744 def test_container_iterator(self): 745 # Bug #3680: tp_traverse was not implemented for deque iterator objects 746 class C(object): 747 pass 748 for i in range(2): 749 obj = C() 750 ref = weakref.ref(obj) 751 if i == 0: 752 container = deque([obj, 1]) 753 else: 754 container = reversed(deque([obj, 1])) 755 obj.x = iter(container) 756 del obj, container 757 gc.collect() 758 self.assertTrue(ref() is None, "Cycle was not collected") 759 760 check_sizeof = support.check_sizeof 761 762 @support.cpython_only 763 def test_sizeof(self): 764 BLOCKLEN = 64 765 basesize = support.calcvobjsize('2P4nP') 766 blocksize = struct.calcsize('P%dPP' % BLOCKLEN) 767 self.assertEqual(object.__sizeof__(deque()), basesize) 768 check = self.check_sizeof 769 check(deque(), basesize + blocksize) 770 check(deque('a'), basesize + blocksize) 771 check(deque('a' * (BLOCKLEN - 1)), basesize + blocksize) 772 check(deque('a' * BLOCKLEN), basesize + 2 * blocksize) 773 check(deque('a' * (42 * BLOCKLEN)), basesize + 43 * blocksize) 774 775class TestVariousIteratorArgs(unittest.TestCase): 776 777 def test_constructor(self): 778 for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)): 779 for g in (seq_tests.Sequence, seq_tests.IterFunc, 780 seq_tests.IterGen, seq_tests.IterFuncStop, 781 seq_tests.itermulti, seq_tests.iterfunc): 782 self.assertEqual(list(deque(g(s))), list(g(s))) 783 self.assertRaises(TypeError, deque, seq_tests.IterNextOnly(s)) 784 self.assertRaises(TypeError, deque, seq_tests.IterNoNext(s)) 785 self.assertRaises(ZeroDivisionError, deque, seq_tests.IterGenExc(s)) 786 787 def test_iter_with_altered_data(self): 788 d = deque('abcdefg') 789 it = iter(d) 790 d.pop() 791 self.assertRaises(RuntimeError, next, it) 792 793 def test_runtime_error_on_empty_deque(self): 794 d = deque() 795 it = iter(d) 796 d.append(10) 797 self.assertRaises(RuntimeError, next, it) 798 799class Deque(deque): 800 pass 801 802class DequeWithBadIter(deque): 803 def __iter__(self): 804 raise TypeError 805 806class TestSubclass(unittest.TestCase): 807 808 def test_basics(self): 809 d = Deque(range(25)) 810 d.__init__(range(200)) 811 for i in range(200, 400): 812 d.append(i) 813 for i in reversed(range(-200, 0)): 814 d.appendleft(i) 815 self.assertEqual(list(d), list(range(-200, 400))) 816 self.assertEqual(len(d), 600) 817 818 left = [d.popleft() for i in range(250)] 819 self.assertEqual(left, list(range(-200, 50))) 820 self.assertEqual(list(d), list(range(50, 400))) 821 822 right = [d.pop() for i in range(250)] 823 right.reverse() 824 self.assertEqual(right, list(range(150, 400))) 825 self.assertEqual(list(d), list(range(50, 150))) 826 827 d.clear() 828 self.assertEqual(len(d), 0) 829 830 def test_copy_pickle(self): 831 832 d = Deque('abc') 833 834 e = d.__copy__() 835 self.assertEqual(type(d), type(e)) 836 self.assertEqual(list(d), list(e)) 837 838 e = Deque(d) 839 self.assertEqual(type(d), type(e)) 840 self.assertEqual(list(d), list(e)) 841 842 for proto in range(pickle.HIGHEST_PROTOCOL + 1): 843 s = pickle.dumps(d, proto) 844 e = pickle.loads(s) 845 self.assertNotEqual(id(d), id(e)) 846 self.assertEqual(type(d), type(e)) 847 self.assertEqual(list(d), list(e)) 848 849 d = Deque('abcde', maxlen=4) 850 851 e = d.__copy__() 852 self.assertEqual(type(d), type(e)) 853 self.assertEqual(list(d), list(e)) 854 855 e = Deque(d) 856 self.assertEqual(type(d), type(e)) 857 self.assertEqual(list(d), list(e)) 858 859 for proto in range(pickle.HIGHEST_PROTOCOL + 1): 860 s = pickle.dumps(d, proto) 861 e = pickle.loads(s) 862 self.assertNotEqual(id(d), id(e)) 863 self.assertEqual(type(d), type(e)) 864 self.assertEqual(list(d), list(e)) 865 866 def test_pickle_recursive(self): 867 for proto in range(pickle.HIGHEST_PROTOCOL + 1): 868 for d in Deque('abc'), Deque('abc', 3): 869 d.append(d) 870 871 e = pickle.loads(pickle.dumps(d, proto)) 872 self.assertNotEqual(id(e), id(d)) 873 self.assertEqual(type(e), type(d)) 874 self.assertEqual(e.maxlen, d.maxlen) 875 dd = d.pop() 876 ee = e.pop() 877 self.assertEqual(id(ee), id(e)) 878 self.assertEqual(e, d) 879 880 d.x = d 881 e = pickle.loads(pickle.dumps(d, proto)) 882 self.assertEqual(id(e.x), id(e)) 883 884 for d in DequeWithBadIter('abc'), DequeWithBadIter('abc', 2): 885 self.assertRaises(TypeError, pickle.dumps, d, proto) 886 887 def test_weakref(self): 888 d = deque('gallahad') 889 p = weakref.proxy(d) 890 self.assertEqual(str(p), str(d)) 891 d = None 892 self.assertRaises(ReferenceError, str, p) 893 894 def test_strange_subclass(self): 895 class X(deque): 896 def __iter__(self): 897 return iter([]) 898 d1 = X([1,2,3]) 899 d2 = X([4,5,6]) 900 d1 == d2 # not clear if this is supposed to be True or False, 901 # but it used to give a SystemError 902 903 @support.cpython_only 904 def test_bug_31608(self): 905 # The interpreter used to crash in specific cases where a deque 906 # subclass returned a non-deque. 907 class X(deque): 908 pass 909 d = X() 910 def bad___new__(cls, *args, **kwargs): 911 return [42] 912 X.__new__ = bad___new__ 913 with self.assertRaises(TypeError): 914 d * 42 # shouldn't crash 915 with self.assertRaises(TypeError): 916 d + deque([1, 2, 3]) # shouldn't crash 917 918 919class SubclassWithKwargs(deque): 920 def __init__(self, newarg=1): 921 deque.__init__(self) 922 923class TestSubclassWithKwargs(unittest.TestCase): 924 def test_subclass_with_kwargs(self): 925 # SF bug #1486663 -- this used to erroneously raise a TypeError 926 SubclassWithKwargs(newarg=1) 927 928class TestSequence(seq_tests.CommonTest): 929 type2test = deque 930 931 def test_getitem(self): 932 # For now, bypass tests that require slicing 933 pass 934 935 def test_getslice(self): 936 # For now, bypass tests that require slicing 937 pass 938 939 def test_subscript(self): 940 # For now, bypass tests that require slicing 941 pass 942 943 def test_free_after_iterating(self): 944 # For now, bypass tests that require slicing 945 self.skipTest("Exhausted deque iterator doesn't free a deque") 946 947#============================================================================== 948 949libreftest = """ 950Example from the Library Reference: Doc/lib/libcollections.tex 951 952>>> from collections import deque 953>>> d = deque('ghi') # make a new deque with three items 954>>> for elem in d: # iterate over the deque's elements 955... print(elem.upper()) 956G 957H 958I 959>>> d.append('j') # add a new entry to the right side 960>>> d.appendleft('f') # add a new entry to the left side 961>>> d # show the representation of the deque 962deque(['f', 'g', 'h', 'i', 'j']) 963>>> d.pop() # return and remove the rightmost item 964'j' 965>>> d.popleft() # return and remove the leftmost item 966'f' 967>>> list(d) # list the contents of the deque 968['g', 'h', 'i'] 969>>> d[0] # peek at leftmost item 970'g' 971>>> d[-1] # peek at rightmost item 972'i' 973>>> list(reversed(d)) # list the contents of a deque in reverse 974['i', 'h', 'g'] 975>>> 'h' in d # search the deque 976True 977>>> d.extend('jkl') # add multiple elements at once 978>>> d 979deque(['g', 'h', 'i', 'j', 'k', 'l']) 980>>> d.rotate(1) # right rotation 981>>> d 982deque(['l', 'g', 'h', 'i', 'j', 'k']) 983>>> d.rotate(-1) # left rotation 984>>> d 985deque(['g', 'h', 'i', 'j', 'k', 'l']) 986>>> deque(reversed(d)) # make a new deque in reverse order 987deque(['l', 'k', 'j', 'i', 'h', 'g']) 988>>> d.clear() # empty the deque 989>>> d.pop() # cannot pop from an empty deque 990Traceback (most recent call last): 991 File "<pyshell#6>", line 1, in -toplevel- 992 d.pop() 993IndexError: pop from an empty deque 994 995>>> d.extendleft('abc') # extendleft() reverses the input order 996>>> d 997deque(['c', 'b', 'a']) 998 999 1000 1001>>> def delete_nth(d, n): 1002... d.rotate(-n) 1003... d.popleft() 1004... d.rotate(n) 1005... 1006>>> d = deque('abcdef') 1007>>> delete_nth(d, 2) # remove the entry at d[2] 1008>>> d 1009deque(['a', 'b', 'd', 'e', 'f']) 1010 1011 1012 1013>>> def roundrobin(*iterables): 1014... pending = deque(iter(i) for i in iterables) 1015... while pending: 1016... task = pending.popleft() 1017... try: 1018... yield next(task) 1019... except StopIteration: 1020... continue 1021... pending.append(task) 1022... 1023 1024>>> for value in roundrobin('abc', 'd', 'efgh'): 1025... print(value) 1026... 1027a 1028d 1029e 1030b 1031f 1032c 1033g 1034h 1035 1036 1037>>> def maketree(iterable): 1038... d = deque(iterable) 1039... while len(d) > 1: 1040... pair = [d.popleft(), d.popleft()] 1041... d.append(pair) 1042... return list(d) 1043... 1044>>> print(maketree('abcdefgh')) 1045[[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]] 1046 1047""" 1048 1049 1050#============================================================================== 1051 1052__test__ = {'libreftest' : libreftest} 1053 1054def test_main(verbose=None): 1055 import sys 1056 test_classes = ( 1057 TestBasic, 1058 TestVariousIteratorArgs, 1059 TestSubclass, 1060 TestSubclassWithKwargs, 1061 TestSequence, 1062 ) 1063 1064 support.run_unittest(*test_classes) 1065 1066 # verify reference counting 1067 if verbose and hasattr(sys, "gettotalrefcount"): 1068 import gc 1069 counts = [None] * 5 1070 for i in range(len(counts)): 1071 support.run_unittest(*test_classes) 1072 gc.collect() 1073 counts[i] = sys.gettotalrefcount() 1074 print(counts) 1075 1076 # doctests 1077 from test import test_deque 1078 support.run_doctest(test_deque, verbose) 1079 1080if __name__ == "__main__": 1081 test_main(verbose=True) 1082