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