summaryrefslogtreecommitdiffstats
path: root/Lib/test
diff options
context:
space:
mode:
Diffstat (limited to 'Lib/test')
-rw-r--r--Lib/test/test_bisect.py17
-rw-r--r--Lib/test/test_deque.py337
2 files changed, 337 insertions, 17 deletions
diff --git a/Lib/test/test_bisect.py b/Lib/test/test_bisect.py
index 809d8af..6bb2112 100644
--- a/Lib/test/test_bisect.py
+++ b/Lib/test/test_bisect.py
@@ -170,23 +170,6 @@ This example uses bisect() to look up a letter grade for an exam total
>>> map(grade, [33, 99, 77, 44, 12, 88])
['E', 'A', 'B', 'D', 'F', 'A']
-The bisect module can be used with the Queue module to implement
-a priority queue (example courtesy of Fredrik Lundh):
-
->>> import Queue, bisect
->>> class PriorityQueue(Queue.Queue):
-... def _put(self, item):
-... bisect.insort(self.queue, item)
-...
->>> queue = PriorityQueue(0)
->>> queue.put((2, "second"))
->>> queue.put((1, "first"))
->>> queue.put((3, "third"))
->>> queue.get()
-(1, 'first')
->>> queue.get()
-(2, 'second')
-
"""
#------------------------------------------------------------------------------
diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py
new file mode 100644
index 0000000..6221c91
--- /dev/null
+++ b/Lib/test/test_deque.py
@@ -0,0 +1,337 @@
+from collections import deque
+import unittest
+from test import test_support
+import copy
+import cPickle as pickle
+from cStringIO import StringIO
+
+BIG = 100000
+
+class TestBasic(unittest.TestCase):
+
+ def test_basics(self):
+ d = deque(xrange(100))
+ d.__init__(xrange(100, 200))
+ for i in xrange(200, 400):
+ d.append(i)
+ for i in reversed(xrange(-200, 0)):
+ d.appendleft(i)
+ 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)]
+ right.reverse()
+ self.assertEqual(right, range(150, 400))
+ self.assertEqual(list(d), range(50, 150))
+
+ def test_len(self):
+ d = deque('ab')
+ self.assertEqual(len(d), 2)
+ d.popleft()
+ self.assertEqual(len(d), 1)
+ d.pop()
+ self.assertEqual(len(d), 0)
+ self.assertRaises(LookupError, d.pop)
+ self.assertEqual(len(d), 0)
+ d.append('c')
+ self.assertEqual(len(d), 1)
+ d.appendleft('d')
+ self.assertEqual(len(d), 2)
+ d.clear()
+ self.assertEqual(len(d), 0)
+
+ def test_underflow(self):
+ d = deque()
+ self.assertRaises(LookupError, d.pop)
+ self.assertRaises(LookupError, d.popleft)
+
+ def test_clear(self):
+ d = deque(xrange(100))
+ self.assertEqual(len(d), 100)
+ d.clear()
+ self.assertEqual(len(d), 0)
+ self.assertEqual(list(d), [])
+
+ def test_repr(self):
+ d = deque(xrange(200))
+ e = eval(repr(d))
+ self.assertEqual(list(d), list(e))
+ d.append(d)
+ self.assert_('...' in repr(d))
+
+ def test_print(self):
+ d = deque(xrange(200))
+ d.append(d)
+ f = StringIO()
+ print >> f, d,
+ self.assertEqual(f.getvalue(), repr(d))
+ f.close()
+
+ def test_hash(self):
+ self.assertRaises(TypeError, hash, deque('abc'))
+
+ def test_long_steadystate_queue_popleft(self):
+ for size in (0, 1, 2, 100, 1000):
+ d = deque(xrange(size))
+ append, pop = d.append, d.popleft
+ for i in xrange(size, BIG):
+ append(i)
+ x = pop()
+ if x != i - size:
+ 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):
+ append(i)
+ x = pop()
+ if x != i - size:
+ self.assertEqual(x, i-size)
+ self.assertEqual(list(reversed(list(d))), range(BIG-size, BIG))
+
+ def test_big_queue_popleft(self):
+ pass
+ d = deque()
+ append, pop = d.append, d.popleft
+ for i in xrange(BIG):
+ append(i)
+ for i in xrange(BIG):
+ x = pop()
+ if x != i:
+ self.assertEqual(x, i)
+
+ def test_big_queue_popright(self):
+ d = deque()
+ append, pop = d.appendleft, d.pop
+ for i in xrange(BIG):
+ append(i)
+ for i in xrange(BIG):
+ x = pop()
+ if x != i:
+ self.assertEqual(x, i)
+
+ def test_big_stack_right(self):
+ d = deque()
+ append, pop = d.append, d.pop
+ for i in xrange(BIG):
+ append(i)
+ for i in reversed(xrange(BIG)):
+ x = pop()
+ if x != i:
+ self.assertEqual(x, i)
+ self.assertEqual(len(d), 0)
+
+ def test_big_stack_left(self):
+ d = deque()
+ append, pop = d.appendleft, d.popleft
+ for i in xrange(BIG):
+ append(i)
+ for i in reversed(xrange(BIG)):
+ x = pop()
+ if x != i:
+ self.assertEqual(x, i)
+ self.assertEqual(len(d), 0)
+
+ def test_roundtrip_iter_init(self):
+ d = deque(xrange(200))
+ e = deque(d)
+ self.assertNotEqual(id(d), id(e))
+ self.assertEqual(list(d), list(e))
+
+ def test_pickle(self):
+ d = deque(xrange(200))
+ s = pickle.dumps(d)
+ e = pickle.loads(s)
+ self.assertNotEqual(id(d), id(e))
+ self.assertEqual(list(d), list(e))
+
+ def test_deepcopy(self):
+ mut = [10]
+ d = deque([mut])
+ e = copy.deepcopy(d)
+ self.assertEqual(list(d), list(e))
+ mut[0] = 11
+ self.assertNotEqual(id(d), id(e))
+ self.assertNotEqual(list(d), list(e))
+
+ def test_copy(self):
+ mut = [10]
+ d = deque([mut])
+ e = copy.copy(d)
+ self.assertEqual(list(d), list(e))
+ mut[0] = 11
+ self.assertNotEqual(id(d), id(e))
+ self.assertEqual(list(d), list(e))
+
+def R(seqn):
+ 'Regular generator'
+ for i in seqn:
+ yield i
+
+class G:
+ 'Sequence using __getitem__'
+ def __init__(self, seqn):
+ self.seqn = seqn
+ def __getitem__(self, i):
+ return self.seqn[i]
+
+class I:
+ 'Sequence using iterator protocol'
+ def __init__(self, seqn):
+ self.seqn = seqn
+ self.i = 0
+ def __iter__(self):
+ return self
+ def next(self):
+ if self.i >= len(self.seqn): raise StopIteration
+ v = self.seqn[self.i]
+ self.i += 1
+ return v
+
+class Ig:
+ 'Sequence using iterator protocol defined with a generator'
+ def __init__(self, seqn):
+ self.seqn = seqn
+ self.i = 0
+ def __iter__(self):
+ for val in self.seqn:
+ yield val
+
+class X:
+ 'Missing __getitem__ and __iter__'
+ def __init__(self, seqn):
+ self.seqn = seqn
+ self.i = 0
+ def next(self):
+ if self.i >= len(self.seqn): raise StopIteration
+ v = self.seqn[self.i]
+ self.i += 1
+ return v
+
+class N:
+ 'Iterator missing next()'
+ def __init__(self, seqn):
+ self.seqn = seqn
+ self.i = 0
+ def __iter__(self):
+ return self
+
+class E:
+ 'Test propagation of exceptions'
+ def __init__(self, seqn):
+ self.seqn = seqn
+ self.i = 0
+ def __iter__(self):
+ return self
+ def next(self):
+ 3/0
+
+class S:
+ 'Test immediate stop'
+ def __init__(self, seqn):
+ pass
+ def __iter__(self):
+ return self
+ def next(self):
+ raise StopIteration
+
+from itertools import chain, imap
+def L(seqn):
+ '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):
+ d = deque('abcdefg')
+ it = iter(d)
+ d.pop()
+ self.assertRaises(RuntimeError, it.next)
+
+class Deque(deque):
+ pass
+
+class TestSubclass(unittest.TestCase):
+
+ def test_basics(self):
+ d = Deque(xrange(100))
+ d.__init__(xrange(100, 200))
+ for i in xrange(200, 400):
+ d.append(i)
+ for i in reversed(xrange(-200, 0)):
+ d.appendleft(i)
+ 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)]
+ right.reverse()
+ self.assertEqual(right, range(150, 400))
+ self.assertEqual(list(d), range(50, 150))
+
+ d.clear()
+ self.assertEqual(len(d), 0)
+
+ def test_copy_pickle(self):
+
+ d = Deque('abc')
+
+ e = d.__copy__()
+ self.assertEqual(type(d), type(e))
+ self.assertEqual(list(d), list(e))
+
+ e = Deque(d)
+ self.assertEqual(type(d), type(e))
+ self.assertEqual(list(d), list(e))
+
+ s = pickle.dumps(d)
+ e = pickle.loads(s)
+ self.assertNotEqual(id(d), id(e))
+ self.assertEqual(type(d), type(e))
+ self.assertEqual(list(d), list(e))
+
+
+#==============================================================================
+
+def test_main(verbose=None):
+ import sys
+ from test import test_sets
+ test_classes = (
+ TestBasic,
+ TestVariousIteratorArgs,
+ TestSubclass,
+ )
+
+ test_support.run_unittest(*test_classes)
+
+ # verify reference counting
+ if verbose and hasattr(sys, "gettotalrefcount"):
+ import gc
+ counts = [None] * 5
+ for i in xrange(len(counts)):
+ test_support.run_unittest(*test_classes)
+ gc.collect()
+ counts[i] = sys.gettotalrefcount()
+ print counts
+
+if __name__ == "__main__":
+ test_main(verbose=True)
generated by cgit v0.12 at 2024-11-15 23:48:06 (GMT)