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