* 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

15 files changed, 982 insertions, 56 deletions

diff --git a/Doc/lib/libbisect.tex b/Doc/lib/libbisect.tex
index 3241891..516e5cf 100644
--- a/Doc/lib/libbisect.tex
+++ b/Doc/lib/libbisect.tex
@@ -80,22 +80,5 @@ breakpoints: 85 and up is an `A', 75..84 is a `B', etc.
 'C'
 >>> map(grade, [33, 99, 77, 44, 12, 88])
 ['E', 'A', 'B', 'D', 'F', 'A']
-\end{verbatim}
-
-The bisect module can be used with the Queue module to implement a priority
-queue (example courtesy of Fredrik Lundh): \index{Priority Queue}
-
-\begin{verbatim}
-import Queue, bisect
-
-class PriorityQueue(Queue.Queue):
-    def _put(self, item):
-        bisect.insort(self.queue, item)
 
-# usage
-queue = PriorityQueue(0)
-queue.put((2, "second"))
-queue.put((1, "first"))
-queue.put((3, "third"))
-priority, value = queue.get()
 \end{verbatim}
diff --git a/Doc/lib/libqueue.tex b/Doc/lib/libqueue.tex
index 0770bfe..52c1125 100644
--- a/Doc/lib/libqueue.tex
+++ b/Doc/lib/libqueue.tex
@@ -12,10 +12,6 @@ information must be exchanged safely between multiple threads.  The
 semantics.  It depends on the availability of thread support in
 Python.
 
-\begin{seealso}
-    \seemodule{bisect}{PriorityQueue example using the Queue class}
-\end{seealso}
-
 The \module{Queue} module defines the following class and exception:
 
 
diff --git a/Doc/whatsnew/whatsnew24.tex b/Doc/whatsnew/whatsnew24.tex
index f435b87..ed4a57f 100644
--- a/Doc/whatsnew/whatsnew24.tex
+++ b/Doc/whatsnew/whatsnew24.tex
@@ -322,6 +322,31 @@ euc-jisx0213, iso-2022-jp, iso-2022-jp-1, iso-2022-jp-2,
  \item Korean: cp949, euc-kr, johab, iso-2022-kr
 \end{itemize} 
 
+\item There is a new \module{collections} module which currently offers
+   just one new datatype, \class{deque}, which offers high-performance,
+   thread-safe, memory friendly appends and pops on either side of the
+   deque resulting in efficient stacks and queues:
+
+\begin{verbatim}
+>>> from collections import deque
+>>> d = deque('ghi')        # make a new deque with three items
+>>> 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
+'j'
+>>> d.popleft()             # return and remove the leftmost item
+'f'
+>>> list(d)                 # list the contents of the deque
+['g', 'h', 'i']
+>>> 'h' in d                # search the deque
+True  
+\end{verbatim}
+
+Several modules now take advantage of \class{collections.deque()} for
+improved performance:  \module{Queue}, \module{mutex}, \module{shlex}
+\module{threading}, and \module{pydoc}.
 
 \item The \module{heapq} module has been converted to C.  The resulting
    ten-fold improvement in speed makes the module suitable for handling
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 @@ class Queue:
     # 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 @@ class Queue:
 
     # 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 @@ Of course, no multi-threading is implied -- hence the funny interface
 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 @@ class mutex:
         """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 @@ Mynd you, møøse bites Kan be pretty nasti..."""
 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 @@ class HTMLDoc(Doc):
         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 @@ class HTMLDoc(Doc):
 
         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 @@ class TextDoc(Doc):
         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 @@ class TextDoc(Doc):
                        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 @@ class shlex:
         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 @@ class shlex:
         "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 @@ class shlex:
     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 @@ class shlex:
     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 @@ class shlex:
                     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 @@ 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)
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 @@ except ImportError:
 
 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 @@ def _test():
             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 @@ def _test():
             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()
diff --git a/Misc/NEWS b/Misc/NEWS
index fa5ef20..71a549e 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -121,6 +121,13 @@ Core and builtins
 Extension modules
 -----------------
 
+- Added a collections module containing a new datatype, deque(),
+  offering high-performance, thread-safe, memory friendly appends
+  and pops on either side of the deque.
+
+- Several modules now take advantage of collections.deque() for
+  improved performance:  Queue, mutex, shlex, threading, and pydoc.
+
 - The operator module has two new functions, attrgetter() and
   itemgetter() which are useful for creating fast data extractor
   functions for map(), list.sort(), itertools.groupby(), and
diff --git a/Modules/collectionsmodule.c b/Modules/collectionsmodule.c
new file mode 100644
index 0000000..16c6e9a
--- /dev/null
+++ b/Modules/collectionsmodule.c
@@ -0,0 +1,582 @@
+#include "Python.h"
+
+/* collections module implementation of a deque() datatype
+   Written and maintained by Raymond D. Hettinger <python@rcn.com>
+   Copyright (c) 2004 Python Software Foundation.
+   All rights reserved.
+*/
+
+#define BLOCKLEN 46
+
+typedef struct BLOCK {
+	struct BLOCK *leftlink;
+	struct BLOCK *rightlink;
+	PyObject *data[BLOCKLEN];
+} block;
+
+static block *newblock(block *leftlink, block *rightlink) {
+	block *b = PyMem_Malloc(sizeof(block));
+	if (b == NULL) {
+		PyErr_NoMemory();
+		return NULL;
+	}
+	b->leftlink = leftlink;
+	b->rightlink = rightlink;
+	return b;
+}
+
+typedef struct {
+	PyObject_HEAD
+	block *leftblock;
+	block *rightblock;
+	int leftindex;
+	int rightindex;
+	int len;
+} dequeobject;
+
+static PyObject *
+deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
+{
+	dequeobject *deque;
+	block *b;
+
+	/* create dequeobject structure */
+	deque = (dequeobject *)type->tp_alloc(type, 0);
+	if (deque == NULL)
+		return NULL;
+	
+	b = newblock(NULL, NULL);
+	if (b == NULL) {
+		Py_DECREF(deque);
+		return NULL;
+	}
+
+	deque->leftblock = b;
+	deque->rightblock = b;
+	deque->leftindex = BLOCKLEN / 2 + 1;
+	deque->rightindex = BLOCKLEN / 2;
+	deque->len = 0;
+
+	return (PyObject *)deque;
+}
+
+static PyObject *
+deque_append(dequeobject *deque, PyObject *item)
+{
+	deque->rightindex++;
+	deque->len++;
+	if (deque->rightindex == BLOCKLEN) {
+		block *b = newblock(deque->rightblock, NULL);
+		if (b == NULL)
+			return NULL;
+		assert(deque->rightblock->rightlink == NULL);
+		deque->rightblock->rightlink = b;
+		deque->rightblock = b;
+		deque->rightindex = 0;
+	}
+	Py_INCREF(item);
+	deque->rightblock->data[deque->rightindex] = item;
+	Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
+
+static PyObject *
+deque_appendleft(dequeobject *deque, PyObject *item)
+{
+	deque->leftindex--;
+	deque->len++;
+	if (deque->leftindex == -1) {
+		block *b = newblock(NULL, deque->leftblock);
+		if (b == NULL)
+			return NULL;
+		assert(deque->leftblock->leftlink == NULL);
+		deque->leftblock->leftlink = b;
+		deque->leftblock = b;
+		deque->leftindex = BLOCKLEN - 1;
+	}
+	Py_INCREF(item);
+	deque->leftblock->data[deque->leftindex] = item;
+	Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
+
+static PyObject *
+deque_pop(dequeobject *deque, PyObject *unused)
+{
+	PyObject *item;
+	block *prevblock;
+
+	if (deque->len == 0) {
+		PyErr_SetString(PyExc_LookupError, "pop from an emtpy deque");
+		return NULL;
+	}
+	item = deque->rightblock->data[deque->rightindex];
+	deque->rightindex--;
+	deque->len--;
+
+	if (deque->rightindex == -1) {
+		if (deque->len == 0) {
+			assert(deque->leftblock == deque->rightblock);
+			assert(deque->leftindex == deque->rightindex+1);
+			/* re-center instead of freeing a block */
+			deque->leftindex = BLOCKLEN / 2 + 1;
+			deque->rightindex = BLOCKLEN / 2;
+		} else {
+			prevblock = deque->rightblock->leftlink;
+			assert(deque->leftblock != deque->rightblock);
+			PyMem_Free(deque->rightblock);
+			prevblock->rightlink = NULL;
+			deque->rightblock = prevblock;
+			deque->rightindex = BLOCKLEN - 1;
+		}
+	}
+	return item;
+}
+
+PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element.");
+
+static PyObject *
+deque_popleft(dequeobject *deque, PyObject *unused)
+{
+	PyObject *item;
+	block *prevblock;
+
+	if (deque->len == 0) {
+		PyErr_SetString(PyExc_LookupError, "pop from an emtpy deque");
+		return NULL;
+	}
+	item = deque->leftblock->data[deque->leftindex];
+	deque->leftindex++;
+	deque->len--;
+
+	if (deque->leftindex == BLOCKLEN) {
+		if (deque->len == 0) {
+			assert(deque->leftblock == deque->rightblock);
+			assert(deque->leftindex == deque->rightindex+1);
+			/* re-center instead of freeing a block */
+			deque->leftindex = BLOCKLEN / 2 + 1;
+			deque->rightindex = BLOCKLEN / 2;
+		} else {
+			assert(deque->leftblock != deque->rightblock);
+			prevblock = deque->leftblock->rightlink;
+			assert(deque->leftblock != NULL);
+			PyMem_Free(deque->leftblock);
+			assert(prevblock != NULL);
+			prevblock->leftlink = NULL;
+			deque->leftblock = prevblock;
+			deque->leftindex = 0;
+		}
+	}
+	return item;
+}
+
+PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");
+
+static int
+deque_len(dequeobject *deque)
+{
+	return deque->len;
+}
+
+static int
+deque_clear(dequeobject *deque)
+{
+	PyObject *item;
+
+	while (deque_len(deque)) {
+		item = deque_pop(deque, NULL);
+		if (item == NULL)
+			return -1;
+		Py_DECREF(item);
+	}
+	assert(deque->leftblock == deque->rightblock &&
+		deque->leftindex > deque->rightindex);
+	return 0;
+}
+
+static PyObject *
+deque_clearmethod(dequeobject *deque)
+{
+	if (deque_clear(deque) == -1)
+		return NULL;
+	Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
+
+static void
+deque_dealloc(dequeobject *deque)
+{
+	PyObject_GC_UnTrack(deque);
+	if (deque->leftblock != NULL) {
+		int err = deque_clear(deque);
+		assert(err == 0);
+		assert(deque->leftblock != NULL);
+		PyMem_Free(deque->leftblock);
+	}
+	deque->leftblock = NULL;
+	deque->rightblock = NULL;
+	deque->ob_type->tp_free(deque);
+}
+
+static int
+set_traverse(dequeobject *deque, visitproc visit, void *arg)
+{
+	block * b = deque->leftblock;
+	int index = deque->leftindex;
+	int err;
+	PyObject *item;
+
+	while (b != deque->rightblock || index <= deque->rightindex) {
+		item = b->data[index];
+		index++;
+		if (index == BLOCKLEN && b->rightlink != NULL) {
+			b = b->rightlink;
+			index = 0;
+		}
+		err = visit(item, arg);
+		if (err) 
+			return err;
+	}
+	return 0;
+}
+
+static long
+deque_nohash(PyObject *self)
+{
+	PyErr_SetString(PyExc_TypeError, "deque objects are unhashable");
+	return -1;
+}
+
+static PyObject *
+deque_copy(PyObject *deque)
+{
+	return PyObject_CallFunctionObjArgs((PyObject *)(deque->ob_type), 
+		deque, NULL);
+}
+
+PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
+
+static PyObject *
+deque_reduce(dequeobject *deque)
+{
+	PyObject *seq, *args, *result;
+
+	seq = PySequence_Tuple((PyObject *)deque);
+	if (seq == NULL)
+		return NULL;
+	args = PyTuple_Pack(1, seq);
+	if (args == NULL) {
+		Py_DECREF(seq);
+		return NULL;
+	}
+	result = PyTuple_Pack(2, deque->ob_type, args);
+	Py_DECREF(seq);
+	Py_DECREF(args);
+	return result;
+}
+
+PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
+
+static PyObject *
+deque_repr(PyObject *deque)
+{
+	PyObject *aslist, *result, *fmt;
+	int i;
+
+	i = Py_ReprEnter(deque);
+	if (i != 0) {
+		if (i < 0)
+			return NULL;
+		return PyString_FromString("[...]");
+	}
+
+	aslist = PySequence_List(deque);
+	if (aslist == NULL) {
+		Py_ReprLeave(deque);
+		return NULL;
+	}
+
+	fmt = PyString_FromString("deque(%r)");
+	if (fmt == NULL) {
+		Py_DECREF(aslist);
+		Py_ReprLeave(deque);
+		return NULL;
+	}
+	result = PyString_Format(fmt, aslist);
+	Py_DECREF(fmt);
+	Py_DECREF(aslist);
+	Py_ReprLeave(deque);
+	return result;
+}
+
+static int
+deque_tp_print(PyObject *deque, FILE *fp, int flags)
+{
+	PyObject *it, *item;
+	int pos=0;
+	char *emit = "";	/* No separator emitted on first pass */
+	char *separator = ", ";
+	int i;
+
+	i = Py_ReprEnter(deque);
+	if (i != 0) {
+		if (i < 0)
+			return i;
+		fputs("[...]", fp);
+		return 0;
+	}
+
+	it = PyObject_GetIter(deque);
+	if (it == NULL)
+		return -1;
+
+	fputs("deque([", fp);
+	while ((item = PyIter_Next(it)) != NULL) {
+		fputs(emit, fp);
+		emit = separator;
+		if (PyObject_Print(item, fp, 0) != 0) {
+			Py_DECREF(item);
+			Py_DECREF(it);
+			Py_ReprLeave(deque);
+			return -1;
+		}
+		Py_DECREF(item);
+	}
+	Py_ReprLeave(deque);
+	Py_DECREF(it);
+	if (PyErr_Occurred()) 
+		return -1;
+	fputs("])", fp);
+	return 0;
+}
+
+static int
+deque_init(dequeobject *deque, PyObject *args, PyObject *kwds)
+{
+	PyObject *iterable = NULL, *it, *item;
+
+	if (!PyArg_UnpackTuple(args, "deque", 0, 1, &iterable))
+		return -1;
+
+	if (iterable != NULL) {
+		it = PyObject_GetIter(iterable);
+		if (it == NULL)
+			return -1;
+
+		while ((item = PyIter_Next(it)) != NULL) {
+			deque->rightindex++;
+			deque->len++;
+			if (deque->rightindex == BLOCKLEN) {
+				block *b = newblock(deque->rightblock, NULL);
+				if (b == NULL) {
+					Py_DECREF(it);
+					Py_DECREF(item);
+					return -1;
+				}
+				deque->rightblock->rightlink = b;
+				deque->rightblock = b;
+				deque->rightindex = 0;
+			}
+			deque->rightblock->data[deque->rightindex] = item;
+		}
+		Py_DECREF(it);
+		if (PyErr_Occurred()) 
+			return -1;
+	}
+	return 0;
+}
+
+static PySequenceMethods deque_as_sequence = {
+	(inquiry)deque_len,		/* sq_length */
+	0,				/* sq_concat */
+};
+
+/* deque object ********************************************************/
+
+static PyObject *deque_iter(dequeobject *deque);
+
+static PyMethodDef deque_methods[] = {
+	{"append",		(PyCFunction)deque_append,	
+		METH_O,		 append_doc},
+	{"appendleft",		(PyCFunction)deque_appendleft,	
+		METH_O,		 appendleft_doc},
+	{"clear",		(PyCFunction)deque_clearmethod,	
+		METH_NOARGS,	 clear_doc},
+	{"__copy__",		(PyCFunction)deque_copy,	
+		METH_NOARGS,	 copy_doc},
+	{"pop",			(PyCFunction)deque_pop,	
+		METH_NOARGS,	 pop_doc},
+	{"popleft",		(PyCFunction)deque_popleft,	
+		METH_NOARGS,	 popleft_doc},
+	{"__reduce__",	(PyCFunction)deque_reduce,	
+		METH_NOARGS,	 reduce_doc},
+	{NULL,		NULL}	/* sentinel */
+};
+
+PyDoc_STRVAR(deque_doc,
+"deque(iterable) --> deque object\n\
+\n\
+Build an ordered collection accessible from endpoints only.");
+
+PyTypeObject deque_type = {
+	PyObject_HEAD_INIT(NULL)
+	0,				/* ob_size */
+	"collections.deque",		/* tp_name */
+	sizeof(dequeobject),		/* tp_basicsize */
+	0,				/* tp_itemsize */
+	/* methods */
+	(destructor)deque_dealloc,	/* tp_dealloc */
+	(printfunc)deque_tp_print,	/* tp_print */
+	0,				/* tp_getattr */
+	0,				/* tp_setattr */
+	0,				/* tp_compare */
+	(reprfunc)deque_repr,		/* tp_repr */
+	0,				/* tp_as_number */
+	&deque_as_sequence,		/* tp_as_sequence */
+	0,				/* tp_as_mapping */
+	deque_nohash,			/* tp_hash */
+	0,				/* tp_call */
+	0,				/* tp_str */
+	PyObject_GenericGetAttr,	/* tp_getattro */
+	0,				/* tp_setattro */
+	0,				/* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,	/* tp_flags */
+	deque_doc,			/* tp_doc */
+	(traverseproc)set_traverse,	/* tp_traverse */
+	(inquiry)deque_clear,		/* tp_clear */
+	0,				/* tp_richcompare */
+	0,				/* tp_weaklistoffset*/
+	(getiterfunc)deque_iter,	/* tp_iter */
+	0,				/* tp_iternext */
+	deque_methods,			/* tp_methods */
+	0,				/* tp_members */
+	0,				/* tp_getset */
+	0,				/* tp_base */
+	0,				/* tp_dict */
+	0,				/* tp_descr_get */
+	0,				/* tp_descr_set */
+	0,				/* tp_dictoffset */
+	(initproc)deque_init,		/* tp_init */
+	PyType_GenericAlloc,		/* tp_alloc */
+	deque_new,			/* tp_new */
+	PyObject_GC_Del,		/* tp_free */
+};
+
+/*********************** Deque Iterator **************************/
+
+typedef struct {
+	PyObject_HEAD
+	int index;
+	block *b;
+	dequeobject *deque;
+	int len;
+} dequeiterobject;
+
+PyTypeObject dequeiter_type;
+
+static PyObject *
+deque_iter(dequeobject *deque)
+{
+	dequeiterobject *it;
+
+	it = PyObject_New(dequeiterobject, &dequeiter_type);
+	if (it == NULL)
+		return NULL;
+	it->b = deque->leftblock;
+	it->index = deque->leftindex;
+	Py_INCREF(deque);
+	it->deque = deque;
+	it->len = deque->len;
+	return (PyObject *)it;
+}
+
+static void
+dequeiter_dealloc(dequeiterobject *dio)
+{
+	Py_XDECREF(dio->deque);
+	dio->ob_type->tp_free(dio);
+}
+
+static PyObject *
+dequeiter_next(dequeiterobject *it)
+{
+	PyObject *item;
+	if (it->b == it->deque->rightblock && it->index > it->deque->rightindex)
+		return NULL;
+
+	if (it->len != it->deque->len) {
+		it->len = -1; /* Make this state sticky */
+		PyErr_SetString(PyExc_RuntimeError,
+				"deque changed size during iteration");
+		return NULL;
+	}
+
+	item = it->b->data[it->index];
+	it->index++;
+	if (it->index == BLOCKLEN && it->b->rightlink != NULL) {
+		it->b = it->b->rightlink;
+		it->index = 0;
+	}
+	Py_INCREF(item);
+	return item;
+}
+
+PyTypeObject dequeiter_type = {
+	PyObject_HEAD_INIT(NULL)
+	0,					/* ob_size */
+	"deque_iterator",			/* tp_name */
+	sizeof(dequeiterobject),		/* tp_basicsize */
+	0,					/* tp_itemsize */
+	/* methods */
+	(destructor)dequeiter_dealloc,		/* tp_dealloc */
+	0,					/* tp_print */
+	0,					/* tp_getattr */
+	0,					/* tp_setattr */
+	0,					/* tp_compare */
+	0,					/* tp_repr */
+	0,					/* tp_as_number */
+	0,					/* tp_as_sequence */
+	0,					/* tp_as_mapping */
+	0,					/* tp_hash */
+	0,					/* tp_call */
+	0,					/* tp_str */
+	PyObject_GenericGetAttr,		/* tp_getattro */
+	0,					/* tp_setattro */
+	0,					/* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT,			/* tp_flags */
+	0,					/* tp_doc */
+	0,					/* tp_traverse */
+	0,					/* tp_clear */
+	0,					/* tp_richcompare */
+	0,					/* tp_weaklistoffset */
+	PyObject_SelfIter,			/* tp_iter */
+	(iternextfunc)dequeiter_next,		/* tp_iternext */
+	0,
+};
+
+/* module level code ********************************************************/
+
+PyDoc_STRVAR(module_doc,
+"High performance data structures\n\
+");
+
+PyMODINIT_FUNC
+initcollections(void)
+{
+	PyObject *m;
+
+	m = Py_InitModule3("collections", NULL, module_doc);
+
+	if (PyType_Ready(&deque_type) < 0)
+		return;
+	Py_INCREF(&deque_type);
+	PyModule_AddObject(m, "deque", (PyObject *)&deque_type);
+
+	if (PyType_Ready(&dequeiter_type) < 0)
+		return;	
+
+	return;
+}
diff --git a/PC/VC6/pythoncore.dsp b/PC/VC6/pythoncore.dsp
index 56e8e37..5e0ba21 100644
--- a/PC/VC6/pythoncore.dsp
+++ b/PC/VC6/pythoncore.dsp
@@ -269,6 +269,10 @@ SOURCE=..\..\Python\codecs.c
 # End Source File

 # Begin Source File

 

+SOURCE=..\..\Modules\collectionsmodule.c

+# End Source File

+# Begin Source File

+

 SOURCE=..\..\Python\compile.c

 # End Source File

 # Begin Source File

diff --git a/PC/config.c b/PC/config.c
index a12f633..e618302 100644
--- a/PC/config.c
+++ b/PC/config.c
@@ -46,6 +46,7 @@ extern void initxxsubtype(void);
 extern void initzipimport(void);
 extern void init_random(void);
 extern void inititertools(void);
+extern void initcollections(void);
 extern void initheapq(void);
 extern void init_bisect(void);
 extern void init_symtable(void);
@@ -136,6 +137,7 @@ struct _inittab _PyImport_Inittab[] = {
         {"_bisect", init_bisect},
         {"heapq", initheapq},
 	{"itertools", inititertools},
+        {"collections", initcollections},
 	{"_symtable", init_symtable},
 	{"mmap", initmmap},
 	{"_csv", init_csv},
diff --git a/setup.py b/setup.py
index 7e2fdd4..8439ef4 100644
--- a/setup.py
+++ b/setup.py
@@ -322,6 +322,8 @@ class PyBuildExt(build_ext):
         exts.append( Extension("_random", ["_randommodule.c"]) )
         # fast iterator tools implemented in C
         exts.append( Extension("itertools", ["itertoolsmodule.c"]) )
+        # high-performance collections
+        exts.append( Extension("collections", ["collectionsmodule.c"]) )
         # bisect
         exts.append( Extension("_bisect", ["_bisectmodule.c"]) )
         # heapq