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