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