0001 from collections import deque 0002 import unittest 0003 from test import test_support 0004 from weakref import proxy 0005 import copy 0006 import cPickle as pickle 0007 from cStringIO import StringIO 0008 import random 0009 import os 0010 0011 BIG = 100000 0012 0013 def fail(): 0014 raise SyntaxError 0015 yield 1 0016 0017 class TestBasic(unittest.TestCase): 0018 0019 def test_basics(self): 0020 d = deque(xrange(100)) 0021 d.__init__(xrange(100, 200)) 0022 for i in xrange(200, 400): 0023 d.append(i) 0024 for i in reversed(xrange(-200, 0)): 0025 d.appendleft(i) 0026 self.assertEqual(list(d), range(-200, 400)) 0027 self.assertEqual(len(d), 600) 0028 0029 left = [d.popleft() for i in xrange(250)] 0030 self.assertEqual(left, range(-200, 50)) 0031 self.assertEqual(list(d), range(50, 400)) 0032 0033 right = [d.pop() for i in xrange(250)] 0034 right.reverse() 0035 self.assertEqual(right, range(150, 400)) 0036 self.assertEqual(list(d), range(50, 150)) 0037 0038 def test_comparisons(self): 0039 d = deque('xabc'); d.popleft() 0040 for e in [d, deque('abc'), deque('ab'), deque(), list(d)]: 0041 self.assertEqual(d==e, type(d)==type(e) and list(d)==list(e)) 0042 self.assertEqual(d!=e, not(type(d)==type(e) and list(d)==list(e))) 0043 0044 args = map(deque, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba')) 0045 for x in args: 0046 for y in args: 0047 self.assertEqual(x == y, list(x) == list(y), (x,y)) 0048 self.assertEqual(x != y, list(x) != list(y), (x,y)) 0049 self.assertEqual(x < y, list(x) < list(y), (x,y)) 0050 self.assertEqual(x <= y, list(x) <= list(y), (x,y)) 0051 self.assertEqual(x > y, list(x) > list(y), (x,y)) 0052 self.assertEqual(x >= y, list(x) >= list(y), (x,y)) 0053 self.assertEqual(cmp(x,y), cmp(list(x),list(y)), (x,y)) 0054 0055 def test_extend(self): 0056 d = deque('a') 0057 self.assertRaises(TypeError, d.extend, 1) 0058 d.extend('bcd') 0059 self.assertEqual(list(d), list('abcd')) 0060 0061 def test_extendleft(self): 0062 d = deque('a') 0063 self.assertRaises(TypeError, d.extendleft, 1) 0064 d.extendleft('bcd') 0065 self.assertEqual(list(d), list(reversed('abcd'))) 0066 d = deque() 0067 d.extendleft(range(1000)) 0068 self.assertEqual(list(d), list(reversed(range(1000)))) 0069 self.assertRaises(SyntaxError, d.extendleft, fail()) 0070 0071 def test_getitem(self): 0072 n = 200 0073 d = deque(xrange(n)) 0074 l = range(n) 0075 for i in xrange(n): 0076 d.popleft() 0077 l.pop(0) 0078 if random.random() < 0.5: 0079 d.append(i) 0080 l.append(i) 0081 for j in xrange(1-len(l), len(l)): 0082 assert d[j] == l[j] 0083 0084 d = deque('superman') 0085 self.assertEqual(d[0], 's') 0086 self.assertEqual(d[-1], 'n') 0087 d = deque() 0088 self.assertRaises(IndexError, d.__getitem__, 0) 0089 self.assertRaises(IndexError, d.__getitem__, -1) 0090 0091 def test_setitem(self): 0092 n = 200 0093 d = deque(xrange(n)) 0094 for i in xrange(n): 0095 d[i] = 10 * i 0096 self.assertEqual(list(d), [10*i for i in xrange(n)]) 0097 l = list(d) 0098 for i in xrange(1-n, 0, -1): 0099 d[i] = 7*i 0100 l[i] = 7*i 0101 self.assertEqual(list(d), l) 0102 0103 def test_delitem(self): 0104 n = 500 # O(n**2) test, don't make this too big 0105 d = deque(xrange(n)) 0106 self.assertRaises(IndexError, d.__delitem__, -n-1) 0107 self.assertRaises(IndexError, d.__delitem__, n) 0108 for i in xrange(n): 0109 self.assertEqual(len(d), n-i) 0110 j = random.randrange(-len(d), len(d)) 0111 val = d[j] 0112 self.assert_(val in d) 0113 del d[j] 0114 self.assert_(val not in d) 0115 self.assertEqual(len(d), 0) 0116 0117 def test_rotate(self): 0118 s = tuple('abcde') 0119 n = len(s) 0120 0121 d = deque(s) 0122 d.rotate(1) # verify rot(1) 0123 self.assertEqual(''.join(d), 'eabcd') 0124 0125 d = deque(s) 0126 d.rotate(-1) # verify rot(-1) 0127 self.assertEqual(''.join(d), 'bcdea') 0128 d.rotate() # check default to 1 0129 self.assertEqual(tuple(d), s) 0130 0131 for i in xrange(n*3): 0132 d = deque(s) 0133 e = deque(d) 0134 d.rotate(i) # check vs. rot(1) n times 0135 for j in xrange(i): 0136 e.rotate(1) 0137 self.assertEqual(tuple(d), tuple(e)) 0138 d.rotate(-i) # check that it works in reverse 0139 self.assertEqual(tuple(d), s) 0140 e.rotate(n-i) # check that it wraps forward 0141 self.assertEqual(tuple(e), s) 0142 0143 for i in xrange(n*3): 0144 d = deque(s) 0145 e = deque(d) 0146 d.rotate(-i) 0147 for j in xrange(i): 0148 e.rotate(-1) # check vs. rot(-1) n times 0149 self.assertEqual(tuple(d), tuple(e)) 0150 d.rotate(i) # check that it works in reverse 0151 self.assertEqual(tuple(d), s) 0152 e.rotate(i-n) # check that it wraps backaround 0153 self.assertEqual(tuple(e), s) 0154 0155 d = deque(s) 0156 e = deque(s) 0157 e.rotate(BIG+17) # verify on long series of rotates 0158 dr = d.rotate 0159 for i in xrange(BIG+17): 0160 dr() 0161 self.assertEqual(tuple(d), tuple(e)) 0162 0163 self.assertRaises(TypeError, d.rotate, 'x') # Wrong arg type 0164 self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args 0165 0166 d = deque() 0167 d.rotate() # rotate an empty deque 0168 self.assertEqual(d, deque()) 0169 0170 def test_len(self): 0171 d = deque('ab') 0172 self.assertEqual(len(d), 2) 0173 d.popleft() 0174 self.assertEqual(len(d), 1) 0175 d.pop() 0176 self.assertEqual(len(d), 0) 0177 self.assertRaises(IndexError, d.pop) 0178 self.assertEqual(len(d), 0) 0179 d.append('c') 0180 self.assertEqual(len(d), 1) 0181 d.appendleft('d') 0182 self.assertEqual(len(d), 2) 0183 d.clear() 0184 self.assertEqual(len(d), 0) 0185 0186 def test_underflow(self): 0187 d = deque() 0188 self.assertRaises(IndexError, d.pop) 0189 self.assertRaises(IndexError, d.popleft) 0190 0191 def test_clear(self): 0192 d = deque(xrange(100)) 0193 self.assertEqual(len(d), 100) 0194 d.clear() 0195 self.assertEqual(len(d), 0) 0196 self.assertEqual(list(d), []) 0197 d.clear() # clear an emtpy deque 0198 self.assertEqual(list(d), []) 0199 0200 def test_repr(self): 0201 d = deque(xrange(200)) 0202 e = eval(repr(d)) 0203 self.assertEqual(list(d), list(e)) 0204 d.append(d) 0205 self.assert_('...' in repr(d)) 0206 0207 def test_print(self): 0208 d = deque(xrange(200)) 0209 d.append(d) 0210 try: 0211 fo = open(test_support.TESTFN, "wb") 0212 print >> fo, d, 0213 fo.close() 0214 fo = open(test_support.TESTFN, "rb") 0215 self.assertEqual(fo.read(), repr(d)) 0216 finally: 0217 fo.close() 0218 os.remove(test_support.TESTFN) 0219 0220 def test_init(self): 0221 self.assertRaises(TypeError, deque, 'abc', 2); 0222 self.assertRaises(TypeError, deque, 1); 0223 0224 def test_hash(self): 0225 self.assertRaises(TypeError, hash, deque('abc')) 0226 0227 def test_long_steadystate_queue_popleft(self): 0228 for size in (0, 1, 2, 100, 1000): 0229 d = deque(xrange(size)) 0230 append, pop = d.append, d.popleft 0231 for i in xrange(size, BIG): 0232 append(i) 0233 x = pop() 0234 if x != i - size: 0235 self.assertEqual(x, i-size) 0236 self.assertEqual(list(d), range(BIG-size, BIG)) 0237 0238 def test_long_steadystate_queue_popright(self): 0239 for size in (0, 1, 2, 100, 1000): 0240 d = deque(reversed(xrange(size))) 0241 append, pop = d.appendleft, d.pop 0242 for i in xrange(size, BIG): 0243 append(i) 0244 x = pop() 0245 if x != i - size: 0246 self.assertEqual(x, i-size) 0247 self.assertEqual(list(reversed(list(d))), range(BIG-size, BIG)) 0248 0249 def test_big_queue_popleft(self): 0250 pass 0251 d = deque() 0252 append, pop = d.append, d.popleft 0253 for i in xrange(BIG): 0254 append(i) 0255 for i in xrange(BIG): 0256 x = pop() 0257 if x != i: 0258 self.assertEqual(x, i) 0259 0260 def test_big_queue_popright(self): 0261 d = deque() 0262 append, pop = d.appendleft, d.pop 0263 for i in xrange(BIG): 0264 append(i) 0265 for i in xrange(BIG): 0266 x = pop() 0267 if x != i: 0268 self.assertEqual(x, i) 0269 0270 def test_big_stack_right(self): 0271 d = deque() 0272 append, pop = d.append, d.pop 0273 for i in xrange(BIG): 0274 append(i) 0275 for i in reversed(xrange(BIG)): 0276 x = pop() 0277 if x != i: 0278 self.assertEqual(x, i) 0279 self.assertEqual(len(d), 0) 0280 0281 def test_big_stack_left(self): 0282 d = deque() 0283 append, pop = d.appendleft, d.popleft 0284 for i in xrange(BIG): 0285 append(i) 0286 for i in reversed(xrange(BIG)): 0287 x = pop() 0288 if x != i: 0289 self.assertEqual(x, i) 0290 self.assertEqual(len(d), 0) 0291 0292 def test_roundtrip_iter_init(self): 0293 d = deque(xrange(200)) 0294 e = deque(d) 0295 self.assertNotEqual(id(d), id(e)) 0296 self.assertEqual(list(d), list(e)) 0297 0298 def test_pickle(self): 0299 d = deque(xrange(200)) 0300 s = pickle.dumps(d) 0301 e = pickle.loads(s) 0302 self.assertNotEqual(id(d), id(e)) 0303 self.assertEqual(list(d), list(e)) 0304 0305 def test_deepcopy(self): 0306 mut = [10] 0307 d = deque([mut]) 0308 e = copy.deepcopy(d) 0309 self.assertEqual(list(d), list(e)) 0310 mut[0] = 11 0311 self.assertNotEqual(id(d), id(e)) 0312 self.assertNotEqual(list(d), list(e)) 0313 0314 def test_copy(self): 0315 mut = [10] 0316 d = deque([mut]) 0317 e = copy.copy(d) 0318 self.assertEqual(list(d), list(e)) 0319 mut[0] = 11 0320 self.assertNotEqual(id(d), id(e)) 0321 self.assertEqual(list(d), list(e)) 0322 0323 def test_reversed(self): 0324 for s in ('abcd', xrange(2000)): 0325 self.assertEqual(list(reversed(deque(s))), list(reversed(s))) 0326 0327 def test_gc_doesnt_blowup(self): 0328 import gc 0329 # This used to assert-fail in deque_traverse() under a debug 0330 # build, or run wild with a NULL pointer in a release build. 0331 d = deque() 0332 for i in xrange(100): 0333 d.append(1) 0334 gc.collect() 0335 0336 def R(seqn): 0337 'Regular generator' 0338 for i in seqn: 0339 yield i 0340 0341 class G: 0342 'Sequence using __getitem__' 0343 def __init__(self, seqn): 0344 self.seqn = seqn 0345 def __getitem__(self, i): 0346 return self.seqn[i] 0347 0348 class I: 0349 'Sequence using iterator protocol' 0350 def __init__(self, seqn): 0351 self.seqn = seqn 0352 self.i = 0 0353 def __iter__(self): 0354 return self 0355 def next(self): 0356 if self.i >= len(self.seqn): raise StopIteration 0357 v = self.seqn[self.i] 0358 self.i += 1 0359 return v 0360 0361 class Ig: 0362 'Sequence using iterator protocol defined with a generator' 0363 def __init__(self, seqn): 0364 self.seqn = seqn 0365 self.i = 0 0366 def __iter__(self): 0367 for val in self.seqn: 0368 yield val 0369 0370 class X: 0371 'Missing __getitem__ and __iter__' 0372 def __init__(self, seqn): 0373 self.seqn = seqn 0374 self.i = 0 0375 def next(self): 0376 if self.i >= len(self.seqn): raise StopIteration 0377 v = self.seqn[self.i] 0378 self.i += 1 0379 return v 0380 0381 class N: 0382 'Iterator missing next()' 0383 def __init__(self, seqn): 0384 self.seqn = seqn 0385 self.i = 0 0386 def __iter__(self): 0387 return self 0388 0389 class E: 0390 'Test propagation of exceptions' 0391 def __init__(self, seqn): 0392 self.seqn = seqn 0393 self.i = 0 0394 def __iter__(self): 0395 return self 0396 def next(self): 0397 3 // 0 0398 0399 class S: 0400 'Test immediate stop' 0401 def __init__(self, seqn): 0402 pass 0403 def __iter__(self): 0404 return self 0405 def next(self): 0406 raise StopIteration 0407 0408 from itertools import chain, imap 0409 def L(seqn): 0410 'Test multiple tiers of iterators' 0411 return chain(imap(lambda x:x, R(Ig(G(seqn))))) 0412 0413 0414 class TestVariousIteratorArgs(unittest.TestCase): 0415 0416 def test_constructor(self): 0417 for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)): 0418 for g in (G, I, Ig, S, L, R): 0419 self.assertEqual(list(deque(g(s))), list(g(s))) 0420 self.assertRaises(TypeError, deque, X(s)) 0421 self.assertRaises(TypeError, deque, N(s)) 0422 self.assertRaises(ZeroDivisionError, deque, E(s)) 0423 0424 def test_iter_with_altered_data(self): 0425 d = deque('abcdefg') 0426 it = iter(d) 0427 d.pop() 0428 self.assertRaises(RuntimeError, it.next) 0429 0430 class Deque(deque): 0431 pass 0432 0433 class TestSubclass(unittest.TestCase): 0434 0435 def test_basics(self): 0436 d = Deque(xrange(100)) 0437 d.__init__(xrange(100, 200)) 0438 for i in xrange(200, 400): 0439 d.append(i) 0440 for i in reversed(xrange(-200, 0)): 0441 d.appendleft(i) 0442 self.assertEqual(list(d), range(-200, 400)) 0443 self.assertEqual(len(d), 600) 0444 0445 left = [d.popleft() for i in xrange(250)] 0446 self.assertEqual(left, range(-200, 50)) 0447 self.assertEqual(list(d), range(50, 400)) 0448 0449 right = [d.pop() for i in xrange(250)] 0450 right.reverse() 0451 self.assertEqual(right, range(150, 400)) 0452 self.assertEqual(list(d), range(50, 150)) 0453 0454 d.clear() 0455 self.assertEqual(len(d), 0) 0456 0457 def test_copy_pickle(self): 0458 0459 d = Deque('abc') 0460 0461 e = d.__copy__() 0462 self.assertEqual(type(d), type(e)) 0463 self.assertEqual(list(d), list(e)) 0464 0465 e = Deque(d) 0466 self.assertEqual(type(d), type(e)) 0467 self.assertEqual(list(d), list(e)) 0468 0469 s = pickle.dumps(d) 0470 e = pickle.loads(s) 0471 self.assertNotEqual(id(d), id(e)) 0472 self.assertEqual(type(d), type(e)) 0473 self.assertEqual(list(d), list(e)) 0474 0475 def test_weakref(self): 0476 d = deque('gallahad') 0477 p = proxy(d) 0478 self.assertEqual(str(p), str(d)) 0479 d = None 0480 self.assertRaises(ReferenceError, str, p) 0481 0482 def test_strange_subclass(self): 0483 class X(deque): 0484 def __iter__(self): 0485 return iter([]) 0486 d1 = X([1,2,3]) 0487 d2 = X([4,5,6]) 0488 d1 == d2 # not clear if this is supposed to be True or False, 0489 # but it used to give a SystemError 0490 0491 #============================================================================== 0492 0493 libreftest = """ 0494 Example from the Library Reference: Doc/lib/libcollections.tex 0495 0496 >>> from collections import deque 0497 >>> d = deque('ghi') # make a new deque with three items 0498 >>> for elem in d: # iterate over the deque's elements 0499 ... print elem.upper() 0500 G 0501 H 0502 I 0503 >>> d.append('j') # add a new entry to the right side 0504 >>> d.appendleft('f') # add a new entry to the left side 0505 >>> d # show the representation of the deque 0506 deque(['f', 'g', 'h', 'i', 'j']) 0507 >>> d.pop() # return and remove the rightmost item 0508 'j' 0509 >>> d.popleft() # return and remove the leftmost item 0510 'f' 0511 >>> list(d) # list the contents of the deque 0512 ['g', 'h', 'i'] 0513 >>> d[0] # peek at leftmost item 0514 'g' 0515 >>> d[-1] # peek at rightmost item 0516 'i' 0517 >>> list(reversed(d)) # list the contents of a deque in reverse 0518 ['i', 'h', 'g'] 0519 >>> 'h' in d # search the deque 0520 True 0521 >>> d.extend('jkl') # add multiple elements at once 0522 >>> d 0523 deque(['g', 'h', 'i', 'j', 'k', 'l']) 0524 >>> d.rotate(1) # right rotation 0525 >>> d 0526 deque(['l', 'g', 'h', 'i', 'j', 'k']) 0527 >>> d.rotate(-1) # left rotation 0528 >>> d 0529 deque(['g', 'h', 'i', 'j', 'k', 'l']) 0530 >>> deque(reversed(d)) # make a new deque in reverse order 0531 deque(['l', 'k', 'j', 'i', 'h', 'g']) 0532 >>> d.clear() # empty the deque 0533 >>> d.pop() # cannot pop from an empty deque 0534 Traceback (most recent call last): 0535 File "<pyshell#6>", line 1, in -toplevel- 0536 d.pop() 0537 IndexError: pop from an empty deque 0538 0539 >>> d.extendleft('abc') # extendleft() reverses the input order 0540 >>> d 0541 deque(['c', 'b', 'a']) 0542 0543 0544 0545 >>> def delete_nth(d, n): 0546 ... d.rotate(-n) 0547 ... d.popleft() 0548 ... d.rotate(n) 0549 ... 0550 >>> d = deque('abcdef') 0551 >>> delete_nth(d, 2) # remove the entry at d[2] 0552 >>> d 0553 deque(['a', 'b', 'd', 'e', 'f']) 0554 0555 0556 0557 >>> def roundrobin(*iterables): 0558 ... pending = deque(iter(i) for i in iterables) 0559 ... while pending: 0560 ... task = pending.popleft() 0561 ... try: 0562 ... yield task.next() 0563 ... except StopIteration: 0564 ... continue 0565 ... pending.append(task) 0566 ... 0567 0568 >>> for value in roundrobin('abc', 'd', 'efgh'): 0569 ... print value 0570 ... 0571 a 0572 d 0573 e 0574 b 0575 f 0576 c 0577 g 0578 h 0579 0580 0581 >>> def maketree(iterable): 0582 ... d = deque(iterable) 0583 ... while len(d) > 1: 0584 ... pair = [d.popleft(), d.popleft()] 0585 ... d.append(pair) 0586 ... return list(d) 0587 ... 0588 >>> print maketree('abcdefgh') 0589 [[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]] 0590 0591 """ 0592 0593 0594 #============================================================================== 0595 0596 __test__ = {'libreftest' : libreftest} 0597 0598 def test_main(verbose=None): 0599 import sys 0600 test_classes = ( 0601 TestBasic, 0602 TestVariousIteratorArgs, 0603 TestSubclass, 0604 ) 0605 0606 test_support.run_unittest(*test_classes) 0607 0608 # verify reference counting 0609 if verbose and hasattr(sys, "gettotalrefcount"): 0610 import gc 0611 counts = [None] * 5 0612 for i in xrange(len(counts)): 0613 test_support.run_unittest(*test_classes) 0614 gc.collect() 0615 counts[i] = sys.gettotalrefcount() 0616 print counts 0617 0618 # doctests 0619 from test import test_deque 0620 test_support.run_doctest(test_deque, verbose) 0621 0622 if __name__ == "__main__": 0623 test_main(verbose=True) 0624
Generated by PyXR 0.9.4