* 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/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 @@
'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 @@
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 @@
\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 @@
# 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()
diff --git a/Misc/NEWS b/Misc/NEWS
index fa5ef20..71a549e 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -121,6 +121,13 @@
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 @@
# 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 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 @@
{"_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 @@
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