* Move collections.deque() in from the sandbox
* Add unittests, newsitem, and whatsnew
* Apply to Queue.py mutex.py threading.py pydoc.py and shlex.py
* Docs are forthcoming
diff --git a/Lib/Queue.py b/Lib/Queue.py
index 980aee6..44c9ca3 100644
--- a/Lib/Queue.py
+++ b/Lib/Queue.py
@@ -1,6 +1,7 @@
"""A multi-producer, multi-consumer queue."""
from time import time as _time, sleep as _sleep
+from collections import deque
__all__ = ['Empty', 'Full', 'Queue']
@@ -184,7 +185,7 @@
# Initialize the queue representation
def _init(self, maxsize):
self.maxsize = maxsize
- self.queue = []
+ self.queue = deque()
def _qsize(self):
return len(self.queue)
@@ -203,4 +204,4 @@
# Get an item from the queue
def _get(self):
- return self.queue.pop(0)
+ return self.queue.popleft()
diff --git a/Lib/mutex.py b/Lib/mutex.py
index e15710a..5d35bdf 100644
--- a/Lib/mutex.py
+++ b/Lib/mutex.py
@@ -12,11 +12,13 @@
for lock, where a function is called once the lock is aquired.
"""
+from collections import deque
+
class mutex:
def __init__(self):
"""Create a new mutex -- initially unlocked."""
self.locked = 0
- self.queue = []
+ self.queue = deque()
def test(self):
"""Test the locked bit of the mutex."""
@@ -44,7 +46,7 @@
"""Unlock a mutex. If the queue is not empty, call the next
function with its argument."""
if self.queue:
- function, argument = self.queue.pop(0)
+ function, argument = self.queue.popleft()
function(argument)
else:
self.locked = 0
diff --git a/Lib/pydoc.py b/Lib/pydoc.py
index e53aa16..e6b53c1 100755
--- a/Lib/pydoc.py
+++ b/Lib/pydoc.py
@@ -55,6 +55,7 @@
import sys, imp, os, re, types, inspect, __builtin__
from repr import Repr
from string import expandtabs, find, join, lower, split, strip, rfind, rstrip
+from collections import deque
# --------------------------------------------------------- common routines
@@ -685,7 +686,7 @@
hr = HorizontalRule()
# List the mro, if non-trivial.
- mro = list(inspect.getmro(object))
+ mro = deque(inspect.getmro(object))
if len(mro) > 2:
hr.maybe()
push('<dl><dt>Method resolution order:</dt>\n')
@@ -763,7 +764,7 @@
while attrs:
if mro:
- thisclass = mro.pop(0)
+ thisclass = mro.popleft()
else:
thisclass = attrs[0][2]
attrs, inherited = _split_list(attrs, lambda t: t[2] is thisclass)
@@ -1083,7 +1084,7 @@
push = contents.append
# List the mro, if non-trivial.
- mro = list(inspect.getmro(object))
+ mro = deque(inspect.getmro(object))
if len(mro) > 2:
push("Method resolution order:")
for base in mro:
@@ -1152,7 +1153,7 @@
inspect.classify_class_attrs(object))
while attrs:
if mro:
- thisclass = mro.pop(0)
+ thisclass = mro.popleft()
else:
thisclass = attrs[0][2]
attrs, inherited = _split_list(attrs, lambda t: t[2] is thisclass)
diff --git a/Lib/shlex.py b/Lib/shlex.py
index b302699..ccf9038 100644
--- a/Lib/shlex.py
+++ b/Lib/shlex.py
@@ -9,6 +9,7 @@
import os.path
import sys
+from collections import deque
try:
from cStringIO import StringIO
@@ -45,11 +46,11 @@
self.escape = '\\'
self.escapedquotes = '"'
self.state = ' '
- self.pushback = []
+ self.pushback = deque()
self.lineno = 1
self.debug = 0
self.token = ''
- self.filestack = []
+ self.filestack = deque()
self.source = None
if self.debug:
print 'shlex: reading from %s, line %d' \
@@ -59,13 +60,13 @@
"Push a token onto the stack popped by the get_token method"
if self.debug >= 1:
print "shlex: pushing token " + `tok`
- self.pushback.insert(0, tok)
+ self.pushback.appendleft(tok)
def push_source(self, newstream, newfile=None):
"Push an input source onto the lexer's input source stack."
if isinstance(newstream, basestring):
newstream = StringIO(newstream)
- self.filestack.insert(0, (self.infile, self.instream, self.lineno))
+ self.filestack.appendleft((self.infile, self.instream, self.lineno))
self.infile = newfile
self.instream = newstream
self.lineno = 1
@@ -78,8 +79,7 @@
def pop_source(self):
"Pop the input source stack."
self.instream.close()
- (self.infile, self.instream, self.lineno) = self.filestack[0]
- self.filestack = self.filestack[1:]
+ (self.infile, self.instream, self.lineno) = self.filestack.popleft()
if self.debug:
print 'shlex: popping to %s, line %d' \
% (self.instream, self.lineno)
@@ -88,7 +88,7 @@
def get_token(self):
"Get a token from the input stream (or from stack if it's nonempty)"
if self.pushback:
- tok = self.pushback.pop(0)
+ tok = self.pushback.popleft()
if self.debug >= 1:
print "shlex: popping token " + `tok`
return tok
@@ -226,7 +226,7 @@
or self.whitespace_split:
self.token = self.token + nextchar
else:
- self.pushback.insert(0, nextchar)
+ self.pushback.appendleft(nextchar)
if self.debug >= 2:
print "shlex: I see punctuation in word state"
self.state = ' '
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 @@
>>> 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)
diff --git a/Lib/threading.py b/Lib/threading.py
index c5d5af3..6461adc 100644
--- a/Lib/threading.py
+++ b/Lib/threading.py
@@ -10,6 +10,7 @@
from time import time as _time, sleep as _sleep
from traceback import format_exc as _format_exc
+from collections import deque
# Rename some stuff so "from threading import *" is safe
__all__ = ['activeCount', 'Condition', 'currentThread', 'enumerate', 'Event',
@@ -639,7 +640,7 @@
self.rc = Condition(self.mon)
self.wc = Condition(self.mon)
self.limit = limit
- self.queue = []
+ self.queue = deque()
def put(self, item):
self.mon.acquire()
@@ -657,7 +658,7 @@
while not self.queue:
self._note("get(): queue empty")
self.rc.wait()
- item = self.queue.pop(0)
+ item = self.queue.popleft()
self._note("get(): got %s, %d left", item, len(self.queue))
self.wc.notify()
self.mon.release()