Lib/test/test_deque.py

   1 from collections import deque
   2 import unittest
   3 from test import test_support, seq_tests
   4 from weakref import proxy
   5 import copy
   6 import cPickle as pickle
   7 from cStringIO import StringIO
   8 import random
   9 import os
  10
  11 BIG = 100000
  12
  13 def fail():
  14     raise SyntaxError
  15     yield 1
  16
  17 class BadCmp:
  18     def __eq__(self, other):
  19         raise RuntimeError
  20
  21 class 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
  29 class TestBasic(unittest.TestCase):
  30
  31     def test_basics(self):
  32         d = deque(xrange(100))
  33         d.__init__(xrange(100, 200))
  34         for i in xrange(200, 400):
  35             d.append(i)
  36         for i in reversed(xrange(-200, 0)):
  37             d.appendleft(i)
  38         self.assertEqual(list(d), range(-200, 400))
  39         self.assertEqual(len(d), 600)
  40
  41         left = [d.popleft() for i in xrange(250)]
  42         self.assertEqual(left, range(-200, 50))
  43         self.assertEqual(list(d), range(50, 400))
  44
  45         right = [d.pop() for i in xrange(250)]
  46         right.reverse()
  47         self.assertEqual(right, range(150, 400))
  48         self.assertEqual(list(d), range(50, 150))
  49
  50     def test_comparisons(self):
  51         d = deque('xabc'); d.popleft()
  52         for e in [d, deque('abc'), deque('ab'), deque(), list(d)]:
  53             self.assertEqual(d==e, type(d)==type(e) and list(d)==list(e))
  54             self.assertEqual(d!=e, not(type(d)==type(e) and list(d)==list(e)))
  55
  56         args = map(deque, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba'))
  57         for x in args:
  58             for y in args:
  59                 self.assertEqual(x == y, list(x) == list(y), (x,y))
  60                 self.assertEqual(x != y, list(x) != list(y), (x,y))
  61                 self.assertEqual(x <  y, list(x) <  list(y), (x,y))
  62                 self.assertEqual(x <= y, list(x) <= list(y), (x,y))
  63                 self.assertEqual(x >  y, list(x) >  list(y), (x,y))
  64                 self.assertEqual(x >= y, list(x) >= list(y), (x,y))
  65                 self.assertEqual(cmp(x,y), cmp(list(x),list(y)), (x,y))
  66
  67     def test_extend(self):
  68         d = deque('a')
  69         self.assertRaises(TypeError, d.extend, 1)
  70         d.extend('bcd')
  71         self.assertEqual(list(d), list('abcd'))
  72
  73     def test_extendleft(self):
  74         d = deque('a')
  75         self.assertRaises(TypeError, d.extendleft, 1)
  76         d.extendleft('bcd')
  77         self.assertEqual(list(d), list(reversed('abcd')))
  78         d = deque()
  79         d.extendleft(range(1000))
  80         self.assertEqual(list(d), list(reversed(range(1000))))
  81         self.assertRaises(SyntaxError, d.extendleft, fail())
  82
  83     def test_getitem(self):
  84         n = 200
  85         d = deque(xrange(n))
  86         l = range(n)
  87         for i in xrange(n):
  88             d.popleft()
  89             l.pop(0)
  90             if random.random() < 0.5:
  91                 d.append(i)
  92                 l.append(i)
  93             for j in xrange(1-len(l), len(l)):
  94                 assert d[j] == l[j]
  95
  96         d = deque('superman')
  97         self.assertEqual(d[0], 's')
  98         self.assertEqual(d[-1], 'n')
  99         d = deque()
 100         self.assertRaises(IndexError, d.__getitem__, 0)
 101         self.assertRaises(IndexError, d.__getitem__, -1)
 102
 103     def test_setitem(self):
 104         n = 200
 105         d = deque(xrange(n))
 106         for i in xrange(n):
 107             d[i] = 10 * i
 108         self.assertEqual(list(d), [10*i for i in xrange(n)])
 109         l = list(d)
 110         for i in xrange(1-n, 0, -1):
 111             d[i] = 7*i
 112             l[i] = 7*i
 113         self.assertEqual(list(d), l)
 114
 115     def test_delitem(self):
 116         n = 500         # O(n**2) test, don't make this too big
 117         d = deque(xrange(n))
 118         self.assertRaises(IndexError, d.__delitem__, -n-1)
 119         self.assertRaises(IndexError, d.__delitem__, n)
 120         for i in xrange(n):
 121             self.assertEqual(len(d), n-i)
 122             j = random.randrange(-len(d), len(d))
 123             val = d[j]
 124             self.assert_(val in d)
 125             del d[j]
 126             self.assert_(val not in d)
 127         self.assertEqual(len(d), 0)
 128
 129     def test_rotate(self):
 130         s = tuple('abcde')
 131         n = len(s)
 132
 133         d = deque(s)
 134         d.rotate(1)             # verify rot(1)
 135         self.assertEqual(''.join(d), 'eabcd')
 136
 137         d = deque(s)
 138         d.rotate(-1)            # verify rot(-1)
 139         self.assertEqual(''.join(d), 'bcdea')
 140         d.rotate()              # check default to 1
 141         self.assertEqual(tuple(d), s)
 142
 143         for i in xrange(n*3):
 144             d = deque(s)
 145             e = deque(d)
 146             d.rotate(i)         # check vs. rot(1) n times
 147             for j in xrange(i):
 148                 e.rotate(1)
 149             self.assertEqual(tuple(d), tuple(e))
 150             d.rotate(-i)        # check that it works in reverse
 151             self.assertEqual(tuple(d), s)
 152             e.rotate(n-i)       # check that it wraps forward
 153             self.assertEqual(tuple(e), s)
 154
 155         for i in xrange(n*3):
 156             d = deque(s)
 157             e = deque(d)
 158             d.rotate(-i)
 159             for j in xrange(i):
 160                 e.rotate(-1)    # check vs. rot(-1) n times
 161             self.assertEqual(tuple(d), tuple(e))
 162             d.rotate(i)         # check that it works in reverse
 163             self.assertEqual(tuple(d), s)
 164             e.rotate(i-n)       # check that it wraps backaround
 165             self.assertEqual(tuple(e), s)
 166
 167         d = deque(s)
 168         e = deque(s)
 169         e.rotate(BIG+17)        # verify on long series of rotates
 170         dr = d.rotate
 171         for i in xrange(BIG+17):
 172             dr()
 173         self.assertEqual(tuple(d), tuple(e))
 174
 175         self.assertRaises(TypeError, d.rotate, 'x')   # Wrong arg type
 176         self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args
 177
 178         d = deque()
 179         d.rotate()              # rotate an empty deque
 180         self.assertEqual(d, deque())
 181
 182     def test_len(self):
 183         d = deque('ab')
 184         self.assertEqual(len(d), 2)
 185         d.popleft()
 186         self.assertEqual(len(d), 1)
 187         d.pop()
 188         self.assertEqual(len(d), 0)
 189         self.assertRaises(IndexError, d.pop)
 190         self.assertEqual(len(d), 0)
 191         d.append('c')
 192         self.assertEqual(len(d), 1)
 193         d.appendleft('d')
 194         self.assertEqual(len(d), 2)
 195         d.clear()
 196         self.assertEqual(len(d), 0)
 197
 198     def test_underflow(self):
 199         d = deque()
 200         self.assertRaises(IndexError, d.pop)
 201         self.assertRaises(IndexError, d.popleft)
 202
 203     def test_clear(self):
 204         d = deque(xrange(100))
 205         self.assertEqual(len(d), 100)
 206         d.clear()
 207         self.assertEqual(len(d), 0)
 208         self.assertEqual(list(d), [])
 209         d.clear()               # clear an emtpy deque
 210         self.assertEqual(list(d), [])
 211
 212     def test_remove(self):
 213         d = deque('abcdefghcij')
 214         d.remove('c')
 215         self.assertEqual(d, deque('abdefghcij'))
 216         d.remove('c')
 217         self.assertEqual(d, deque('abdefghij'))
 218         self.assertRaises(ValueError, d.remove, 'c')
 219         self.assertEqual(d, deque('abdefghij'))
 220
 221         # Handle comparison errors
 222         d = deque(['a', 'b', BadCmp(), 'c'])
 223         e = deque(d)
 224         self.assertRaises(RuntimeError, d.remove, 'c')
 225         for x, y in zip(d, e):
 226             # verify that original order and values are retained.
 227             self.assert_(x is y)
 228
 229         # Handle evil mutator
 230         for match in (True, False):
 231             d = deque(['ab'])
 232             d.extend([MutateCmp(d, match), 'c'])
 233             self.assertRaises(IndexError, d.remove, 'c')
 234             self.assertEqual(d, deque())
 235
 236     def test_repr(self):
 237         d = deque(xrange(200))
 238         e = eval(repr(d))
 239         self.assertEqual(list(d), list(e))
 240         d.append(d)
 241         self.assert_('...' in repr(d))
 242
 243     def test_print(self):
 244         d = deque(xrange(200))
 245         d.append(d)
 246         try:
 247             fo = open(test_support.TESTFN, "wb")
 248             print >> fo, d,
 249             fo.close()
 250             fo = open(test_support.TESTFN, "rb")
 251             self.assertEqual(fo.read(), repr(d))
 252         finally:
 253             fo.close()
 254             os.remove(test_support.TESTFN)
 255
 256     def test_init(self):
 257         self.assertRaises(TypeError, deque, 'abc', 2);
 258         self.assertRaises(TypeError, deque, 1);
 259
 260     def test_hash(self):
 261         self.assertRaises(TypeError, hash, deque('abc'))
 262
 263     def test_long_steadystate_queue_popleft(self):
 264         for size in (0, 1, 2, 100, 1000):
 265             d = deque(xrange(size))
 266             append, pop = d.append, d.popleft
 267             for i in xrange(size, BIG):
 268                 append(i)
 269                 x = pop()
 270                 if x != i - size:
 271                     self.assertEqual(x, i-size)
 272             self.assertEqual(list(d), range(BIG-size, BIG))
 273
 274     def test_long_steadystate_queue_popright(self):
 275         for size in (0, 1, 2, 100, 1000):
 276             d = deque(reversed(xrange(size)))
 277             append, pop = d.appendleft, d.pop
 278             for i in xrange(size, BIG):
 279                 append(i)
 280                 x = pop()
 281                 if x != i - size:
 282                     self.assertEqual(x, i-size)
 283             self.assertEqual(list(reversed(list(d))), range(BIG-size, BIG))
 284
 285     def test_big_queue_popleft(self):
 286         pass
 287         d = deque()
 288         append, pop = d.append, d.popleft
 289         for i in xrange(BIG):
 290             append(i)
 291         for i in xrange(BIG):
 292             x = pop()
 293             if x != i:
 294                 self.assertEqual(x, i)
 295
 296     def test_big_queue_popright(self):
 297         d = deque()
 298         append, pop = d.appendleft, d.pop
 299         for i in xrange(BIG):
 300             append(i)
 301         for i in xrange(BIG):
 302             x = pop()
 303             if x != i:
 304                 self.assertEqual(x, i)
 305
 306     def test_big_stack_right(self):
 307         d = deque()
 308         append, pop = d.append, d.pop
 309         for i in xrange(BIG):
 310             append(i)
 311         for i in reversed(xrange(BIG)):
 312             x = pop()
 313             if x != i:
 314                 self.assertEqual(x, i)
 315         self.assertEqual(len(d), 0)
 316
 317     def test_big_stack_left(self):
 318         d = deque()
 319         append, pop = d.appendleft, d.popleft
 320         for i in xrange(BIG):
 321             append(i)
 322         for i in reversed(xrange(BIG)):
 323             x = pop()
 324             if x != i:
 325                 self.assertEqual(x, i)
 326         self.assertEqual(len(d), 0)
 327
 328     def test_roundtrip_iter_init(self):
 329         d = deque(xrange(200))
 330         e = deque(d)
 331         self.assertNotEqual(id(d), id(e))
 332         self.assertEqual(list(d), list(e))
 333
 334     def test_pickle(self):
 335         d = deque(xrange(200))
 336         for i in (0, 1, 2):
 337             s = pickle.dumps(d, i)
 338             e = pickle.loads(s)
 339             self.assertNotEqual(id(d), id(e))
 340             self.assertEqual(list(d), list(e))
 341
 342     def test_pickle_recursive(self):
 343         d = deque('abc')
 344         d.append(d)
 345         for i in (0, 1, 2):
 346             e = pickle.loads(pickle.dumps(d, i))
 347             self.assertNotEqual(id(d), id(e))
 348             self.assertEqual(id(e), id(e[-1]))
 349
 350     def test_deepcopy(self):
 351         mut = [10]
 352         d = deque([mut])
 353         e = copy.deepcopy(d)
 354         self.assertEqual(list(d), list(e))
 355         mut[0] = 11
 356         self.assertNotEqual(id(d), id(e))
 357         self.assertNotEqual(list(d), list(e))
 358
 359     def test_copy(self):
 360         mut = [10]
 361         d = deque([mut])
 362         e = copy.copy(d)
 363         self.assertEqual(list(d), list(e))
 364         mut[0] = 11
 365         self.assertNotEqual(id(d), id(e))
 366         self.assertEqual(list(d), list(e))
 367
 368     def test_reversed(self):
 369         for s in ('abcd', xrange(2000)):
 370             self.assertEqual(list(reversed(deque(s))), list(reversed(s)))
 371
 372     def test_gc_doesnt_blowup(self):
 373         import gc
 374         # This used to assert-fail in deque_traverse() under a debug
 375         # build, or run wild with a NULL pointer in a release build.
 376         d = deque()
 377         for i in xrange(100):
 378             d.append(1)
 379             gc.collect()
 380
 381 class TestVariousIteratorArgs(unittest.TestCase):
 382
 383     def test_constructor(self):
 384         for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)):
 385             for g in (seq_tests.Sequence, seq_tests.IterFunc,
 386                       seq_tests.IterGen, seq_tests.IterFuncStop,
 387                       seq_tests.itermulti, seq_tests.iterfunc):
 388                 self.assertEqual(list(deque(g(s))), list(g(s)))
 389             self.assertRaises(TypeError, deque, seq_tests.IterNextOnly(s))
 390             self.assertRaises(TypeError, deque, seq_tests.IterNoNext(s))
 391             self.assertRaises(ZeroDivisionError, deque, seq_tests.IterGenExc(s))
 392
 393     def test_iter_with_altered_data(self):
 394         d = deque('abcdefg')
 395         it = iter(d)
 396         d.pop()
 397         self.assertRaises(RuntimeError, it.next)
 398
 399 class Deque(deque):
 400     pass
 401
 402 class DequeWithBadIter(deque):
 403     def __iter__(self):
 404         raise TypeError
 405
 406 class TestSubclass(unittest.TestCase):
 407
 408     def test_basics(self):
 409         d = Deque(xrange(100))
 410         d.__init__(xrange(100, 200))
 411         for i in xrange(200, 400):
 412             d.append(i)
 413         for i in reversed(xrange(-200, 0)):
 414             d.appendleft(i)
 415         self.assertEqual(list(d), range(-200, 400))
 416         self.assertEqual(len(d), 600)
 417
 418         left = [d.popleft() for i in xrange(250)]
 419         self.assertEqual(left, range(-200, 50))
 420         self.assertEqual(list(d), range(50, 400))
 421
 422         right = [d.pop() for i in xrange(250)]
 423         right.reverse()
 424         self.assertEqual(right, range(150, 400))
 425         self.assertEqual(list(d), range(50, 150))
 426
 427         d.clear()
 428         self.assertEqual(len(d), 0)
 429
 430     def test_copy_pickle(self):
 431
 432         d = Deque('abc')
 433
 434         e = d.__copy__()
 435         self.assertEqual(type(d), type(e))
 436         self.assertEqual(list(d), list(e))
 437
 438         e = Deque(d)
 439         self.assertEqual(type(d), type(e))
 440         self.assertEqual(list(d), list(e))
 441
 442         s = pickle.dumps(d)
 443         e = pickle.loads(s)
 444         self.assertNotEqual(id(d), id(e))
 445         self.assertEqual(type(d), type(e))
 446         self.assertEqual(list(d), list(e))
 447
 448     def test_pickle(self):
 449         d = Deque('abc')
 450         d.append(d)
 451
 452         e = pickle.loads(pickle.dumps(d))
 453         self.assertNotEqual(id(d), id(e))
 454         self.assertEqual(type(d), type(e))
 455         dd = d.pop()
 456         ee = e.pop()
 457         self.assertEqual(id(e), id(ee))
 458         self.assertEqual(d, e)
 459
 460         d.x = d
 461         e = pickle.loads(pickle.dumps(d))
 462         self.assertEqual(id(e), id(e.x))
 463
 464         d = DequeWithBadIter('abc')
 465         self.assertRaises(TypeError, pickle.dumps, d)
 466
 467     def test_weakref(self):
 468         d = deque('gallahad')
 469         p = proxy(d)
 470         self.assertEqual(str(p), str(d))
 471         d = None
 472         self.assertRaises(ReferenceError, str, p)
 473
 474     def test_strange_subclass(self):
 475         class X(deque):
 476             def __iter__(self):
 477                 return iter([])
 478         d1 = X([1,2,3])
 479         d2 = X([4,5,6])
 480         d1 == d2   # not clear if this is supposed to be True or False,
 481                    # but it used to give a SystemError
 482
 483 #==============================================================================
 484
 485 libreftest = """
 486 Example from the Library Reference:  Doc/lib/libcollections.tex
 487
 488 >>> from collections import deque
 489 >>> d = deque('ghi')                 # make a new deque with three items
 490 >>> for elem in d:                   # iterate over the deque's elements
 491 ...     print elem.upper()
 492 G
 493 H
 494 I
 495 >>> d.append('j')                    # add a new entry to the right side
 496 >>> d.appendleft('f')                # add a new entry to the left side
 497 >>> d                                # show the representation of the deque
 498 deque(['f', 'g', 'h', 'i', 'j'])
 499 >>> d.pop()                          # return and remove the rightmost item
 500 'j'
 501 >>> d.popleft()                      # return and remove the leftmost item
 502 'f'
 503 >>> list(d)                          # list the contents of the deque
 504 ['g', 'h', 'i']
 505 >>> d[0]                             # peek at leftmost item
 506 'g'
 507 >>> d[-1]                            # peek at rightmost item
 508 'i'
 509 >>> list(reversed(d))                # list the contents of a deque in reverse
 510 ['i', 'h', 'g']
 511 >>> 'h' in d                         # search the deque
 512 True
 513 >>> d.extend('jkl')                  # add multiple elements at once
 514 >>> d
 515 deque(['g', 'h', 'i', 'j', 'k', 'l'])
 516 >>> d.rotate(1)                      # right rotation
 517 >>> d
 518 deque(['l', 'g', 'h', 'i', 'j', 'k'])
 519 >>> d.rotate(-1)                     # left rotation
 520 >>> d
 521 deque(['g', 'h', 'i', 'j', 'k', 'l'])
 522 >>> deque(reversed(d))               # make a new deque in reverse order
 523 deque(['l', 'k', 'j', 'i', 'h', 'g'])
 524 >>> d.clear()                        # empty the deque
 525 >>> d.pop()                          # cannot pop from an empty deque
 526 Traceback (most recent call last):
 527   File "<pyshell#6>", line 1, in -toplevel-
 528     d.pop()
 529 IndexError: pop from an empty deque
 530
 531 >>> d.extendleft('abc')              # extendleft() reverses the input order
 532 >>> d
 533 deque(['c', 'b', 'a'])
 534
 535
 536
 537 >>> def delete_nth(d, n):
 538 ...     d.rotate(-n)
 539 ...     d.popleft()
 540 ...     d.rotate(n)
 541 ...
 542 >>> d = deque('abcdef')
 543 >>> delete_nth(d, 2)   # remove the entry at d[2]
 544 >>> d
 545 deque(['a', 'b', 'd', 'e', 'f'])
 546
 547
 548
 549 >>> def roundrobin(*iterables):
 550 ...     pending = deque(iter(i) for i in iterables)
 551 ...     while pending:
 552 ...         task = pending.popleft()
 553 ...         try:
 554 ...             yield task.next()
 555 ...         except StopIteration:
 556 ...             continue
 557 ...         pending.append(task)
 558 ...
 559
 560 >>> for value in roundrobin('abc', 'd', 'efgh'):
 561 ...     print value
 562 ...
 563 a
 564 d
 565 e
 566 b
 567 f
 568 c
 569 g
 570 h
 571
 572
 573 >>> def maketree(iterable):
 574 ...     d = deque(iterable)
 575 ...     while len(d) > 1:
 576 ...         pair = [d.popleft(), d.popleft()]
 577 ...         d.append(pair)
 578 ...     return list(d)
 579 ...
 580 >>> print maketree('abcdefgh')
 581 [[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]
 582
 583 """
 584
 585
 586 #==============================================================================
 587
 588 __test__ = {'libreftest' : libreftest}
 589
 590 def test_main(verbose=None):
 591     import sys
 592     test_classes = (
 593         TestBasic,
 594         TestVariousIteratorArgs,
 595         TestSubclass,
 596     )
 597
 598     test_support.run_unittest(*test_classes)
 599
 600     # verify reference counting
 601     if verbose and hasattr(sys, "gettotalrefcount"):
 602         import gc
 603         counts = [None] * 5
 604         for i in xrange(len(counts)):
 605             test_support.run_unittest(*test_classes)
 606             gc.collect()
 607             counts[i] = sys.gettotalrefcount()
 608         print counts
 609
 610     # doctests
 611     from test import test_deque
 612     test_support.run_doctest(test_deque, verbose)
 613
 614 if __name__ == "__main__":
 615     test_main(verbose=True)