1 from collections
import deque
3 from test
import test_support
, seq_tests
7 import cPickle
as pickle
17 def __eq__(self
, other
):
21 def __init__(self
, deque
, result
):
24 def __eq__(self
, other
):
28 class TestBasic(unittest
.TestCase
):
30 def test_basics(self
):
31 d
= deque(xrange(-5125, -5000))
32 d
.__init
__(xrange(200))
33 for i
in xrange(200, 400):
35 for i
in reversed(xrange(-200, 0)):
37 self
.assertEqual(list(d
), range(-200, 400))
38 self
.assertEqual(len(d
), 600)
40 left
= [d
.popleft() for i
in xrange(250)]
41 self
.assertEqual(left
, range(-200, 50))
42 self
.assertEqual(list(d
), range(50, 400))
44 right
= [d
.pop() for i
in xrange(250)]
46 self
.assertEqual(right
, range(150, 400))
47 self
.assertEqual(list(d
), range(50, 150))
49 def test_maxlen(self
):
50 self
.assertRaises(ValueError, deque
, 'abc', -1)
51 self
.assertRaises(ValueError, deque
, 'abc', -2)
53 d
= deque(it
, maxlen
=3)
54 self
.assertEqual(list(it
), [])
55 self
.assertEqual(repr(d
), 'deque([7, 8, 9], maxlen=3)')
56 self
.assertEqual(list(d
), range(7, 10))
57 self
.assertEqual(d
, deque(range(10), 3))
59 self
.assertEqual(list(d
), range(8, 11))
61 self
.assertEqual(list(d
), range(7, 10))
63 self
.assertEqual(list(d
), range(9, 12))
65 self
.assertEqual(list(d
), range(7, 10))
66 d
= deque(xrange(200), maxlen
=10)
68 test_support
.unlink(test_support
.TESTFN
)
69 fo
= open(test_support
.TESTFN
, "wb")
73 fo
= open(test_support
.TESTFN
, "rb")
74 self
.assertEqual(fo
.read(), repr(d
))
77 test_support
.unlink(test_support
.TESTFN
)
79 d
= deque(range(10), maxlen
=None)
80 self
.assertEqual(repr(d
), 'deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])')
81 fo
= open(test_support
.TESTFN
, "wb")
85 fo
= open(test_support
.TESTFN
, "rb")
86 self
.assertEqual(fo
.read(), repr(d
))
89 test_support
.unlink(test_support
.TESTFN
)
91 def test_maxlen_zero(self
):
94 self
.assertEqual(list(it
), [])
99 self
.assertEqual(list(it
), [])
101 it
= iter(range(100))
104 self
.assertEqual(list(it
), [])
106 def test_maxlen_attribute(self
):
107 self
.assertEqual(deque().maxlen
, None)
108 self
.assertEqual(deque('abc').maxlen
, None)
109 self
.assertEqual(deque('abc', maxlen
=4).maxlen
, 4)
110 self
.assertEqual(deque('abc', maxlen
=2).maxlen
, 2)
111 self
.assertEqual(deque('abc', maxlen
=0).maxlen
, 0)
112 with self
.assertRaises(AttributeError):
116 def test_count(self
):
117 for s
in ('', 'abracadabra', 'simsalabim'*500+'abc'):
120 for letter
in 'abcdefghijklmnopqrstuvwxyz':
121 self
.assertEqual(s
.count(letter
), d
.count(letter
), (s
, d
, letter
))
122 self
.assertRaises(TypeError, d
.count
) # too few args
123 self
.assertRaises(TypeError, d
.count
, 1, 2) # too many args
125 def __eq__(self
, other
):
126 raise ArithmeticError
127 d
= deque([1, 2, BadCompare(), 3])
128 self
.assertRaises(ArithmeticError, d
.count
, 2)
130 self
.assertRaises(ArithmeticError, d
.count
, BadCompare())
131 class MutatingCompare
:
132 def __eq__(self
, other
):
135 m
= MutatingCompare()
136 d
= deque([1, 2, 3, m
, 4, 5])
138 self
.assertRaises(RuntimeError, d
.count
, 3)
140 def test_comparisons(self
):
141 d
= deque('xabc'); d
.popleft()
142 for e
in [d
, deque('abc'), deque('ab'), deque(), list(d
)]:
143 self
.assertEqual(d
==e
, type(d
)==type(e
) and list(d
)==list(e
))
144 self
.assertEqual(d
!=e
, not(type(d
)==type(e
) and list(d
)==list(e
)))
146 args
= map(deque
, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba'))
149 self
.assertEqual(x
== y
, list(x
) == list(y
), (x
,y
))
150 self
.assertEqual(x
!= y
, list(x
) != list(y
), (x
,y
))
151 self
.assertEqual(x
< y
, list(x
) < list(y
), (x
,y
))
152 self
.assertEqual(x
<= y
, list(x
) <= list(y
), (x
,y
))
153 self
.assertEqual(x
> y
, list(x
) > list(y
), (x
,y
))
154 self
.assertEqual(x
>= y
, list(x
) >= list(y
), (x
,y
))
155 self
.assertEqual(cmp(x
,y
), cmp(list(x
),list(y
)), (x
,y
))
157 def test_extend(self
):
159 self
.assertRaises(TypeError, d
.extend
, 1)
161 self
.assertEqual(list(d
), list('abcd'))
163 self
.assertEqual(list(d
), list('abcdabcd'))
168 self
.assertEqual(list(d
), list('abcd'))
170 self
.assertEqual(list(d
), list('abcdabcd'))
172 def test_extendleft(self
):
174 self
.assertRaises(TypeError, d
.extendleft
, 1)
176 self
.assertEqual(list(d
), list(reversed('abcd')))
178 self
.assertEqual(list(d
), list('abcddcba'))
180 d
.extendleft(range(1000))
181 self
.assertEqual(list(d
), list(reversed(range(1000))))
182 self
.assertRaises(SyntaxError, d
.extendleft
, fail())
184 def test_getitem(self
):
191 if random
.random() < 0.5:
194 for j
in xrange(1-len(l
), len(l
)):
197 d
= deque('superman')
198 self
.assertEqual(d
[0], 's')
199 self
.assertEqual(d
[-1], 'n')
201 self
.assertRaises(IndexError, d
.__getitem
__, 0)
202 self
.assertRaises(IndexError, d
.__getitem
__, -1)
204 def test_setitem(self
):
209 self
.assertEqual(list(d
), [10*i
for i
in xrange(n
)])
211 for i
in xrange(1-n
, 0, -1):
214 self
.assertEqual(list(d
), l
)
216 def test_delitem(self
):
217 n
= 500 # O(n**2) test, don't make this too big
219 self
.assertRaises(IndexError, d
.__delitem
__, -n
-1)
220 self
.assertRaises(IndexError, d
.__delitem
__, n
)
222 self
.assertEqual(len(d
), n
-i
)
223 j
= random
.randrange(-len(d
), len(d
))
225 self
.assertIn(val
, d
)
227 self
.assertNotIn(val
, d
)
228 self
.assertEqual(len(d
), 0)
230 def test_reverse(self
):
231 n
= 500 # O(n**2) test, don't make this too big
232 data
= [random
.random() for i
in range(n
)]
236 self
.assertEqual(list(d
), list(reversed(data
[:i
])))
237 self
.assert_(r
is None)
239 self
.assertEqual(list(d
), data
[:i
])
240 self
.assertRaises(TypeError, d
.reverse
, 1) # Arity is zero
242 def test_rotate(self
):
247 d
.rotate(1) # verify rot(1)
248 self
.assertEqual(''.join(d
), 'eabcd')
251 d
.rotate(-1) # verify rot(-1)
252 self
.assertEqual(''.join(d
), 'bcdea')
253 d
.rotate() # check default to 1
254 self
.assertEqual(tuple(d
), s
)
256 for i
in xrange(n
*3):
259 d
.rotate(i
) # check vs. rot(1) n times
262 self
.assertEqual(tuple(d
), tuple(e
))
263 d
.rotate(-i
) # check that it works in reverse
264 self
.assertEqual(tuple(d
), s
)
265 e
.rotate(n
-i
) # check that it wraps forward
266 self
.assertEqual(tuple(e
), s
)
268 for i
in xrange(n
*3):
273 e
.rotate(-1) # check vs. rot(-1) n times
274 self
.assertEqual(tuple(d
), tuple(e
))
275 d
.rotate(i
) # check that it works in reverse
276 self
.assertEqual(tuple(d
), s
)
277 e
.rotate(i
-n
) # check that it wraps backaround
278 self
.assertEqual(tuple(e
), s
)
282 e
.rotate(BIG
+17) # verify on long series of rotates
284 for i
in xrange(BIG
+17):
286 self
.assertEqual(tuple(d
), tuple(e
))
288 self
.assertRaises(TypeError, d
.rotate
, 'x') # Wrong arg type
289 self
.assertRaises(TypeError, d
.rotate
, 1, 10) # Too many args
292 d
.rotate() # rotate an empty deque
293 self
.assertEqual(d
, deque())
297 self
.assertEqual(len(d
), 2)
299 self
.assertEqual(len(d
), 1)
301 self
.assertEqual(len(d
), 0)
302 self
.assertRaises(IndexError, d
.pop
)
303 self
.assertEqual(len(d
), 0)
305 self
.assertEqual(len(d
), 1)
307 self
.assertEqual(len(d
), 2)
309 self
.assertEqual(len(d
), 0)
311 def test_underflow(self
):
313 self
.assertRaises(IndexError, d
.pop
)
314 self
.assertRaises(IndexError, d
.popleft
)
316 def test_clear(self
):
317 d
= deque(xrange(100))
318 self
.assertEqual(len(d
), 100)
320 self
.assertEqual(len(d
), 0)
321 self
.assertEqual(list(d
), [])
322 d
.clear() # clear an emtpy deque
323 self
.assertEqual(list(d
), [])
325 def test_remove(self
):
326 d
= deque('abcdefghcij')
328 self
.assertEqual(d
, deque('abdefghcij'))
330 self
.assertEqual(d
, deque('abdefghij'))
331 self
.assertRaises(ValueError, d
.remove
, 'c')
332 self
.assertEqual(d
, deque('abdefghij'))
334 # Handle comparison errors
335 d
= deque(['a', 'b', BadCmp(), 'c'])
337 self
.assertRaises(RuntimeError, d
.remove
, 'c')
338 for x
, y
in zip(d
, e
):
339 # verify that original order and values are retained.
340 self
.assertTrue(x
is y
)
342 # Handle evil mutator
343 for match
in (True, False):
345 d
.extend([MutateCmp(d
, match
), 'c'])
346 self
.assertRaises(IndexError, d
.remove
, 'c')
347 self
.assertEqual(d
, deque())
350 d
= deque(xrange(200))
352 self
.assertEqual(list(d
), list(e
))
354 self
.assertIn('...', repr(d
))
356 def test_print(self
):
357 d
= deque(xrange(200))
359 test_support
.unlink(test_support
.TESTFN
)
360 fo
= open(test_support
.TESTFN
, "wb")
364 fo
= open(test_support
.TESTFN
, "rb")
365 self
.assertEqual(fo
.read(), repr(d
))
368 test_support
.unlink(test_support
.TESTFN
)
371 self
.assertRaises(TypeError, deque
, 'abc', 2, 3);
372 self
.assertRaises(TypeError, deque
, 1);
375 self
.assertRaises(TypeError, hash, deque('abc'))
377 def test_long_steadystate_queue_popleft(self
):
378 for size
in (0, 1, 2, 100, 1000):
379 d
= deque(xrange(size
))
380 append
, pop
= d
.append
, d
.popleft
381 for i
in xrange(size
, BIG
):
385 self
.assertEqual(x
, i
-size
)
386 self
.assertEqual(list(d
), range(BIG
-size
, BIG
))
388 def test_long_steadystate_queue_popright(self
):
389 for size
in (0, 1, 2, 100, 1000):
390 d
= deque(reversed(xrange(size
)))
391 append
, pop
= d
.appendleft
, d
.pop
392 for i
in xrange(size
, BIG
):
396 self
.assertEqual(x
, i
-size
)
397 self
.assertEqual(list(reversed(list(d
))), range(BIG
-size
, BIG
))
399 def test_big_queue_popleft(self
):
402 append
, pop
= d
.append
, d
.popleft
403 for i
in xrange(BIG
):
405 for i
in xrange(BIG
):
408 self
.assertEqual(x
, i
)
410 def test_big_queue_popright(self
):
412 append
, pop
= d
.appendleft
, d
.pop
413 for i
in xrange(BIG
):
415 for i
in xrange(BIG
):
418 self
.assertEqual(x
, i
)
420 def test_big_stack_right(self
):
422 append
, pop
= d
.append
, d
.pop
423 for i
in xrange(BIG
):
425 for i
in reversed(xrange(BIG
)):
428 self
.assertEqual(x
, i
)
429 self
.assertEqual(len(d
), 0)
431 def test_big_stack_left(self
):
433 append
, pop
= d
.appendleft
, d
.popleft
434 for i
in xrange(BIG
):
436 for i
in reversed(xrange(BIG
)):
439 self
.assertEqual(x
, i
)
440 self
.assertEqual(len(d
), 0)
442 def test_roundtrip_iter_init(self
):
443 d
= deque(xrange(200))
445 self
.assertNotEqual(id(d
), id(e
))
446 self
.assertEqual(list(d
), list(e
))
448 def test_pickle(self
):
449 d
= deque(xrange(200))
450 for i
in range(pickle
.HIGHEST_PROTOCOL
+ 1):
451 s
= pickle
.dumps(d
, i
)
453 self
.assertNotEqual(id(d
), id(e
))
454 self
.assertEqual(list(d
), list(e
))
456 ## def test_pickle_recursive(self):
459 ## for i in range(pickle.HIGHEST_PROTOCOL + 1):
460 ## e = pickle.loads(pickle.dumps(d, i))
461 ## self.assertNotEqual(id(d), id(e))
462 ## self.assertEqual(id(e), id(e[-1]))
464 def test_deepcopy(self
):
468 self
.assertEqual(list(d
), list(e
))
470 self
.assertNotEqual(id(d
), id(e
))
471 self
.assertNotEqual(list(d
), list(e
))
477 self
.assertEqual(list(d
), list(e
))
479 self
.assertNotEqual(id(d
), id(e
))
480 self
.assertEqual(list(d
), list(e
))
482 def test_reversed(self
):
483 for s
in ('abcd', xrange(2000)):
484 self
.assertEqual(list(reversed(deque(s
))), list(reversed(s
)))
486 def test_gc_doesnt_blowup(self
):
488 # This used to assert-fail in deque_traverse() under a debug
489 # build, or run wild with a NULL pointer in a release build.
491 for i
in xrange(100):
495 def test_container_iterator(self
):
496 # Bug #3680: tp_traverse was not implemented for deque iterator objects
501 ref
= weakref
.ref(obj
)
503 container
= deque([obj
, 1])
505 container
= reversed(deque([obj
, 1]))
506 obj
.x
= iter(container
)
509 self
.assertTrue(ref() is None, "Cycle was not collected")
511 class TestVariousIteratorArgs(unittest
.TestCase
):
513 def test_constructor(self
):
514 for s
in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)):
515 for g
in (seq_tests
.Sequence
, seq_tests
.IterFunc
,
516 seq_tests
.IterGen
, seq_tests
.IterFuncStop
,
517 seq_tests
.itermulti
, seq_tests
.iterfunc
):
518 self
.assertEqual(list(deque(g(s
))), list(g(s
)))
519 self
.assertRaises(TypeError, deque
, seq_tests
.IterNextOnly(s
))
520 self
.assertRaises(TypeError, deque
, seq_tests
.IterNoNext(s
))
521 self
.assertRaises(ZeroDivisionError, deque
, seq_tests
.IterGenExc(s
))
523 def test_iter_with_altered_data(self
):
527 self
.assertRaises(RuntimeError, it
.next
)
529 def test_runtime_error_on_empty_deque(self
):
533 self
.assertRaises(RuntimeError, it
.next
)
538 class DequeWithBadIter(deque
):
542 class TestSubclass(unittest
.TestCase
):
544 def test_basics(self
):
545 d
= Deque(xrange(25))
546 d
.__init
__(xrange(200))
547 for i
in xrange(200, 400):
549 for i
in reversed(xrange(-200, 0)):
551 self
.assertEqual(list(d
), range(-200, 400))
552 self
.assertEqual(len(d
), 600)
554 left
= [d
.popleft() for i
in xrange(250)]
555 self
.assertEqual(left
, range(-200, 50))
556 self
.assertEqual(list(d
), range(50, 400))
558 right
= [d
.pop() for i
in xrange(250)]
560 self
.assertEqual(right
, range(150, 400))
561 self
.assertEqual(list(d
), range(50, 150))
564 self
.assertEqual(len(d
), 0)
566 def test_copy_pickle(self
):
571 self
.assertEqual(type(d
), type(e
))
572 self
.assertEqual(list(d
), list(e
))
575 self
.assertEqual(type(d
), type(e
))
576 self
.assertEqual(list(d
), list(e
))
580 self
.assertNotEqual(id(d
), id(e
))
581 self
.assertEqual(type(d
), type(e
))
582 self
.assertEqual(list(d
), list(e
))
584 d
= Deque('abcde', maxlen
=4)
587 self
.assertEqual(type(d
), type(e
))
588 self
.assertEqual(list(d
), list(e
))
591 self
.assertEqual(type(d
), type(e
))
592 self
.assertEqual(list(d
), list(e
))
596 self
.assertNotEqual(id(d
), id(e
))
597 self
.assertEqual(type(d
), type(e
))
598 self
.assertEqual(list(d
), list(e
))
600 ## def test_pickle(self):
604 ## e = pickle.loads(pickle.dumps(d))
605 ## self.assertNotEqual(id(d), id(e))
606 ## self.assertEqual(type(d), type(e))
609 ## self.assertEqual(id(e), id(ee))
610 ## self.assertEqual(d, e)
613 ## e = pickle.loads(pickle.dumps(d))
614 ## self.assertEqual(id(e), id(e.x))
616 ## d = DequeWithBadIter('abc')
617 ## self.assertRaises(TypeError, pickle.dumps, d)
619 def test_weakref(self
):
620 d
= deque('gallahad')
622 self
.assertEqual(str(p
), str(d
))
624 self
.assertRaises(ReferenceError, str, p
)
626 def test_strange_subclass(self
):
632 d1
== d2
# not clear if this is supposed to be True or False,
633 # but it used to give a SystemError
636 class SubclassWithKwargs(deque
):
637 def __init__(self
, newarg
=1):
640 class TestSubclassWithKwargs(unittest
.TestCase
):
641 def test_subclass_with_kwargs(self
):
642 # SF bug #1486663 -- this used to erroneously raise a TypeError
643 SubclassWithKwargs(newarg
=1)
645 #==============================================================================
648 Example from the Library Reference: Doc/lib/libcollections.tex
650 >>> from collections import deque
651 >>> d = deque('ghi') # make a new deque with three items
652 >>> for elem in d: # iterate over the deque's elements
653 ... print elem.upper()
657 >>> d.append('j') # add a new entry to the right side
658 >>> d.appendleft('f') # add a new entry to the left side
659 >>> d # show the representation of the deque
660 deque(['f', 'g', 'h', 'i', 'j'])
661 >>> d.pop() # return and remove the rightmost item
663 >>> d.popleft() # return and remove the leftmost item
665 >>> list(d) # list the contents of the deque
667 >>> d[0] # peek at leftmost item
669 >>> d[-1] # peek at rightmost item
671 >>> list(reversed(d)) # list the contents of a deque in reverse
673 >>> 'h' in d # search the deque
675 >>> d.extend('jkl') # add multiple elements at once
677 deque(['g', 'h', 'i', 'j', 'k', 'l'])
678 >>> d.rotate(1) # right rotation
680 deque(['l', 'g', 'h', 'i', 'j', 'k'])
681 >>> d.rotate(-1) # left rotation
683 deque(['g', 'h', 'i', 'j', 'k', 'l'])
684 >>> deque(reversed(d)) # make a new deque in reverse order
685 deque(['l', 'k', 'j', 'i', 'h', 'g'])
686 >>> d.clear() # empty the deque
687 >>> d.pop() # cannot pop from an empty deque
688 Traceback (most recent call last):
689 File "<pyshell#6>", line 1, in -toplevel-
691 IndexError: pop from an empty deque
693 >>> d.extendleft('abc') # extendleft() reverses the input order
695 deque(['c', 'b', 'a'])
699 >>> def delete_nth(d, n):
704 >>> d = deque('abcdef')
705 >>> delete_nth(d, 2) # remove the entry at d[2]
707 deque(['a', 'b', 'd', 'e', 'f'])
711 >>> def roundrobin(*iterables):
712 ... pending = deque(iter(i) for i in iterables)
714 ... task = pending.popleft()
716 ... yield task.next()
717 ... except StopIteration:
719 ... pending.append(task)
722 >>> for value in roundrobin('abc', 'd', 'efgh'):
735 >>> def maketree(iterable):
736 ... d = deque(iterable)
737 ... while len(d) > 1:
738 ... pair = [d.popleft(), d.popleft()]
742 >>> print maketree('abcdefgh')
743 [[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]
748 #==============================================================================
750 __test__
= {'libreftest' : libreftest
}
752 def test_main(verbose
=None):
756 TestVariousIteratorArgs
,
758 TestSubclassWithKwargs
,
761 test_support
.run_unittest(*test_classes
)
763 # verify reference counting
764 if verbose
and hasattr(sys
, "gettotalrefcount"):
767 for i
in xrange(len(counts
)):
768 test_support
.run_unittest(*test_classes
)
770 counts
[i
] = sys
.gettotalrefcount()
774 from test
import test_deque
775 test_support
.run_doctest(test_deque
, verbose
)
777 if __name__
== "__main__":
778 test_main(verbose
=True)