from collections
import deque
from test
import test_support
from weakref
import proxy
from cStringIO
import StringIO
class TestBasic(unittest
.TestCase
):
d
.__init
__(xrange(100, 200))
for i
in xrange(200, 400):
for i
in reversed(xrange(-200, 0)):
self
.assertEqual(list(d
), range(-200, 400))
self
.assertEqual(len(d
), 600)
left
= [d
.popleft() for i
in xrange(250)]
self
.assertEqual(left
, range(-200, 50))
self
.assertEqual(list(d
), range(50, 400))
right
= [d
.pop() for i
in xrange(250)]
self
.assertEqual(right
, range(150, 400))
self
.assertEqual(list(d
), range(50, 150))
def test_comparisons(self
):
d
= deque('xabc'); d
.popleft()
for e
in [d
, deque('abc'), deque('ab'), deque(), list(d
)]:
self
.assertEqual(d
==e
, type(d
)==type(e
) and list(d
)==list(e
))
self
.assertEqual(d
!=e
, not(type(d
)==type(e
) and list(d
)==list(e
)))
args
= map(deque
, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba'))
self
.assertEqual(x
== y
, list(x
) == list(y
), (x
,y
))
self
.assertEqual(x
!= y
, list(x
) != list(y
), (x
,y
))
self
.assertEqual(x
< y
, list(x
) < list(y
), (x
,y
))
self
.assertEqual(x
<= y
, list(x
) <= list(y
), (x
,y
))
self
.assertEqual(x
> y
, list(x
) > list(y
), (x
,y
))
self
.assertEqual(x
>= y
, list(x
) >= list(y
), (x
,y
))
self
.assertEqual(cmp(x
,y
), cmp(list(x
),list(y
)), (x
,y
))
self
.assertRaises(TypeError, d
.extend
, 1)
self
.assertEqual(list(d
), list('abcd'))
def test_extendleft(self
):
self
.assertRaises(TypeError, d
.extendleft
, 1)
self
.assertEqual(list(d
), list(reversed('abcd')))
d
.extendleft(range(1000))
self
.assertEqual(list(d
), list(reversed(range(1000))))
self
.assertRaises(SyntaxError, d
.extendleft
, fail())
if random
.random() < 0.5:
for j
in xrange(1-len(l
), len(l
)):
self
.assertEqual(d
[0], 's')
self
.assertEqual(d
[-1], 'n')
self
.assertRaises(IndexError, d
.__getitem
__, 0)
self
.assertRaises(IndexError, d
.__getitem
__, -1)
self
.assertEqual(list(d
), [10*i
for i
in xrange(n
)])
for i
in xrange(1-n
, 0, -1):
self
.assertEqual(list(d
), l
)
n
= 500 # O(n**2) test, don't make this too big
self
.assertRaises(IndexError, d
.__delitem
__, -n
-1)
self
.assertRaises(IndexError, d
.__delitem
__, n
)
self
.assertEqual(len(d
), n
-i
)
j
= random
.randrange(-len(d
), len(d
))
self
.assert_(val
not in d
)
self
.assertEqual(len(d
), 0)
d
.rotate(1) # verify rot(1)
self
.assertEqual(''.join(d
), 'eabcd')
d
.rotate(-1) # verify rot(-1)
self
.assertEqual(''.join(d
), 'bcdea')
d
.rotate() # check default to 1
self
.assertEqual(tuple(d
), s
)
d
.rotate(i
) # check vs. rot(1) n times
self
.assertEqual(tuple(d
), tuple(e
))
d
.rotate(-i
) # check that it works in reverse
self
.assertEqual(tuple(d
), s
)
e
.rotate(n
-i
) # check that it wraps forward
self
.assertEqual(tuple(e
), s
)
e
.rotate(-1) # check vs. rot(-1) n times
self
.assertEqual(tuple(d
), tuple(e
))
d
.rotate(i
) # check that it works in reverse
self
.assertEqual(tuple(d
), s
)
e
.rotate(i
-n
) # check that it wraps backaround
self
.assertEqual(tuple(e
), s
)
e
.rotate(BIG
+17) # verify on long series of rotates
self
.assertEqual(tuple(d
), tuple(e
))
self
.assertRaises(TypeError, d
.rotate
, 'x') # Wrong arg type
self
.assertRaises(TypeError, d
.rotate
, 1, 10) # Too many args
d
.rotate() # rotate an empty deque
self
.assertEqual(d
, deque())
self
.assertEqual(len(d
), 2)
self
.assertEqual(len(d
), 1)
self
.assertEqual(len(d
), 0)
self
.assertRaises(IndexError, d
.pop
)
self
.assertEqual(len(d
), 0)
self
.assertEqual(len(d
), 1)
self
.assertEqual(len(d
), 2)
self
.assertEqual(len(d
), 0)
def test_underflow(self
):
self
.assertRaises(IndexError, d
.pop
)
self
.assertRaises(IndexError, d
.popleft
)
self
.assertEqual(len(d
), 100)
self
.assertEqual(len(d
), 0)
self
.assertEqual(list(d
), [])
d
.clear() # clear an emtpy deque
self
.assertEqual(list(d
), [])
self
.assertEqual(list(d
), list(e
))
self
.assert_('...' in repr(d
))
fo
= open(test_support
.TESTFN
, "wb")
fo
= open(test_support
.TESTFN
, "rb")
self
.assertEqual(fo
.read(), repr(d
))
os
.remove(test_support
.TESTFN
)
self
.assertRaises(TypeError, deque
, 'abc', 2);
self
.assertRaises(TypeError, deque
, 1);
self
.assertRaises(TypeError, hash, deque('abc'))
def test_long_steadystate_queue_popleft(self
):
for size
in (0, 1, 2, 100, 1000):
append
, pop
= d
.append
, d
.popleft
for i
in xrange(size
, BIG
):
self
.assertEqual(x
, i
-size
)
self
.assertEqual(list(d
), range(BIG
-size
, BIG
))
def test_long_steadystate_queue_popright(self
):
for size
in (0, 1, 2, 100, 1000):
d
= deque(reversed(xrange(size
)))
append
, pop
= d
.appendleft
, d
.pop
for i
in xrange(size
, BIG
):
self
.assertEqual(x
, i
-size
)
self
.assertEqual(list(reversed(list(d
))), range(BIG
-size
, BIG
))
def test_big_queue_popleft(self
):
append
, pop
= d
.append
, d
.popleft
def test_big_queue_popright(self
):
append
, pop
= d
.appendleft
, d
.pop
def test_big_stack_right(self
):
append
, pop
= d
.append
, d
.pop
for i
in reversed(xrange(BIG
)):
self
.assertEqual(len(d
), 0)
def test_big_stack_left(self
):
append
, pop
= d
.appendleft
, d
.popleft
for i
in reversed(xrange(BIG
)):
self
.assertEqual(len(d
), 0)
def test_roundtrip_iter_init(self
):
self
.assertNotEqual(id(d
), id(e
))
self
.assertEqual(list(d
), list(e
))
self
.assertNotEqual(id(d
), id(e
))
self
.assertEqual(list(d
), list(e
))
def test_pickle_recursive(self
):
e
= pickle
.loads(pickle
.dumps(d
, i
))
self
.assertNotEqual(id(d
), id(e
))
self
.assertEqual(id(e
), id(e
[-1]))
self
.assertEqual(list(d
), list(e
))
self
.assertNotEqual(id(d
), id(e
))
self
.assertNotEqual(list(d
), list(e
))
self
.assertEqual(list(d
), list(e
))
self
.assertNotEqual(id(d
), id(e
))
self
.assertEqual(list(d
), list(e
))
for s
in ('abcd', xrange(2000)):
self
.assertEqual(list(reversed(deque(s
))), list(reversed(s
)))
def test_gc_doesnt_blowup(self
):
# This used to assert-fail in deque_traverse() under a debug
# build, or run wild with a NULL pointer in a release build.
'Sequence using __getitem__'
def __init__(self
, seqn
):
def __getitem__(self
, i
):
'Sequence using iterator protocol'
def __init__(self
, seqn
):
if self
.i
>= len(self
.seqn
): raise StopIteration
'Sequence using iterator protocol defined with a generator'
def __init__(self
, seqn
):
'Missing __getitem__ and __iter__'
def __init__(self
, seqn
):
if self
.i
>= len(self
.seqn
): raise StopIteration
'Iterator missing next()'
def __init__(self
, seqn
):
'Test propagation of exceptions'
def __init__(self
, seqn
):
def __init__(self
, seqn
):
from itertools
import chain
, imap
'Test multiple tiers of iterators'
return chain(imap(lambda x
:x
, R(Ig(G(seqn
)))))
class TestVariousIteratorArgs(unittest
.TestCase
):
def test_constructor(self
):
for s
in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)):
for g
in (G
, I
, Ig
, S
, L
, R
):
self
.assertEqual(list(deque(g(s
))), list(g(s
)))
self
.assertRaises(TypeError, deque
, X(s
))
self
.assertRaises(TypeError, deque
, N(s
))
self
.assertRaises(ZeroDivisionError, deque
, E(s
))
def test_iter_with_altered_data(self
):
self
.assertRaises(RuntimeError, it
.next
)
class DequeWithBadIter(deque
):
class TestSubclass(unittest
.TestCase
):
d
.__init
__(xrange(100, 200))
for i
in xrange(200, 400):
for i
in reversed(xrange(-200, 0)):
self
.assertEqual(list(d
), range(-200, 400))
self
.assertEqual(len(d
), 600)
left
= [d
.popleft() for i
in xrange(250)]
self
.assertEqual(left
, range(-200, 50))
self
.assertEqual(list(d
), range(50, 400))
right
= [d
.pop() for i
in xrange(250)]
self
.assertEqual(right
, range(150, 400))
self
.assertEqual(list(d
), range(50, 150))
self
.assertEqual(len(d
), 0)
def test_copy_pickle(self
):
self
.assertEqual(type(d
), type(e
))
self
.assertEqual(list(d
), list(e
))
self
.assertEqual(type(d
), type(e
))
self
.assertEqual(list(d
), list(e
))
self
.assertNotEqual(id(d
), id(e
))
self
.assertEqual(type(d
), type(e
))
self
.assertEqual(list(d
), list(e
))
e
= pickle
.loads(pickle
.dumps(d
))
self
.assertNotEqual(id(d
), id(e
))
self
.assertEqual(type(d
), type(e
))
self
.assertEqual(id(e
), id(ee
))
e
= pickle
.loads(pickle
.dumps(d
))
self
.assertEqual(id(e
), id(e
.x
))
d
= DequeWithBadIter('abc')
self
.assertRaises(TypeError, pickle
.dumps
, d
)
self
.assertEqual(str(p
), str(d
))
self
.assertRaises(ReferenceError, str, p
)
def test_strange_subclass(self
):
d1
== d2
# not clear if this is supposed to be True or False,
# but it used to give a SystemError
#==============================================================================
Example from the Library Reference: Doc/lib/libcollections.tex
>>> from collections import deque
>>> d = deque('ghi') # make a new deque with three items
>>> for elem in d: # iterate over the deque's elements
>>> d.append('j') # add a new entry to the right side
>>> d.appendleft('f') # add a new entry to the left side
>>> d # show the representation of the deque
deque(['f', 'g', 'h', 'i', 'j'])
>>> d.pop() # return and remove the rightmost item
>>> d.popleft() # return and remove the leftmost item
>>> list(d) # list the contents of the deque
>>> d[0] # peek at leftmost item
>>> d[-1] # peek at rightmost item
>>> list(reversed(d)) # list the contents of a deque in reverse
>>> 'h' in d # search the deque
>>> d.extend('jkl') # add multiple elements at once
deque(['g', 'h', 'i', 'j', 'k', 'l'])
>>> d.rotate(1) # right rotation
deque(['l', 'g', 'h', 'i', 'j', 'k'])
>>> d.rotate(-1) # left rotation
deque(['g', 'h', 'i', 'j', 'k', 'l'])
>>> deque(reversed(d)) # make a new deque in reverse order
deque(['l', 'k', 'j', 'i', 'h', 'g'])
>>> d.clear() # empty the deque
>>> d.pop() # cannot pop from an empty deque
Traceback (most recent call last):
File "<pyshell#6>", line 1, in -toplevel-
IndexError: pop from an empty deque
>>> d.extendleft('abc') # extendleft() reverses the input order
>>> def delete_nth(d, n):
>>> delete_nth(d, 2) # remove the entry at d[2]
deque(['a', 'b', 'd', 'e', 'f'])
>>> def roundrobin(*iterables):
... pending = deque(iter(i) for i in iterables)
... task = pending.popleft()
... except StopIteration:
>>> for value in roundrobin('abc', 'd', 'efgh'):
>>> def maketree(iterable):
... pair = [d.popleft(), d.popleft()]
>>> print maketree('abcdefgh')
[[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]
#==============================================================================
__test__
= {'libreftest' : libreftest
}
def test_main(verbose
=None):
test_support
.run_unittest(*test_classes
)
# verify reference counting
if verbose
and hasattr(sys
, "gettotalrefcount"):
for i
in xrange(len(counts
)):
test_support
.run_unittest(*test_classes
)
counts
[i
] = sys
.gettotalrefcount()
from test
import test_deque
test_support
.run_doctest(test_deque
, verbose
)
if __name__
== "__main__":