Have deques support high volume loads.

3 files changed, 104 insertions, 25 deletions

diff --git a/Doc/lib/libcollections.tex b/Doc/lib/libcollections.tex
index e6ccd7a..ebb2079 100644
--- a/Doc/lib/libcollections.tex
+++ b/Doc/lib/libcollections.tex
@@ -37,6 +37,17 @@ Deque objects support the following methods:
    Remove all elements from the deque leaving it with length 0.
 \end{methoddesc}
 
+\begin{methoddesc}{extend}{iterable}
+   Extend the right side of the deque by appending elements from
+   the iterable argument.
+\end{methoddesc}
+
+\begin{methoddesc}{extendleft}{iterable}
+   Extend the left side of the deque by appending elements from
+   \var{iterable}.  Note, the series of left appends results in
+   reversing the order of elements in the iterable argument.
+\end{methoddesc}
+
 \begin{methoddesc}{pop}{}
    Remove and return an element from the right side of the deque.
    If no elements are present, raises a \exception{LookupError}.
@@ -75,14 +86,19 @@ deque(['f', 'g', 'h', 'i', 'j'])
 ['g', 'h', 'i']
 >>> 'h' in d                # search the deque
 True
->>> d.__init__('jkl')       # use __init__ to append many elements at once
+>>> d.extend('jkl')         # extend() will append many elements at once
 >>> d
 deque(['g', 'h', 'i', 'j', 'k', 'l'])
 >>> d.clear()               # empty the deque
->>> d.pop()                 # try to pop from an empty deque
+>>> d.pop()                 # cannot pop from an empty deque
 
 Traceback (most recent call last):
   File "<pyshell#6>", line 1, in -toplevel-
     d.pop()
 LookupError: pop from an empty deque
+
+>>> d.extendleft('abc')     # extendleft() reverses the element order
+>>> d
+deque(['c', 'b', 'a'])
+
 \end{verbatim}    
diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py
index 6221c91..51ce7b0 100644
--- a/Lib/test/test_deque.py
+++ b/Lib/test/test_deque.py
@@ -28,6 +28,18 @@ class TestBasic(unittest.TestCase):
         self.assertEqual(right, range(150, 400))
         self.assertEqual(list(d), range(50, 150))
 
+    def test_extend(self):
+        d = deque('a')
+        self.assertRaises(TypeError, d.extend, 1)
+        d.extend('bcd')
+        self.assertEqual(list(d), list('abcd'))
+
+    def test_extendleft(self):
+        d = deque('a')
+        self.assertRaises(TypeError, d.extendleft, 1)
+        d.extendleft('bcd')
+        self.assertEqual(list(d), list(reversed('abcd')))
+
     def test_len(self):
         d = deque('ab')
         self.assertEqual(len(d), 2)
diff --git a/Modules/collectionsmodule.c b/Modules/collectionsmodule.c
index 6780c57..83be6ac 100644
--- a/Modules/collectionsmodule.c
+++ b/Modules/collectionsmodule.c
@@ -174,6 +174,72 @@ deque_popleft(dequeobject *deque, PyObject *unused)
 
 PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");
 
+static PyObject *
+deque_extend(dequeobject *deque, PyObject *iterable)
+{
+	PyObject *it, *item;
+
+	it = PyObject_GetIter(iterable);
+	if (it == NULL)
+		return NULL;
+
+	while ((item = PyIter_Next(it)) != NULL) {
+		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_DECREF(it);
+	if (PyErr_Occurred()) 
+		return NULL;
+	Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(extend_doc, 
+"Extend the right side of the deque with elements from the iterable");
+
+static PyObject *
+deque_extendleft(dequeobject *deque, PyObject *iterable)
+{
+	PyObject *it, *item;
+
+	it = PyObject_GetIter(iterable);
+	if (it == NULL)
+		return NULL;
+
+	while ((item = PyIter_Next(it)) != NULL) {
+		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_DECREF(it);
+	if (PyErr_Occurred()) 
+		return NULL;
+	Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(extendleft_doc, 
+"Extend the left side of the deque with elements from the iterable");
+
 static int
 deque_len(dequeobject *deque)
 {
@@ -356,35 +422,16 @@ deque_tp_print(PyObject *deque, FILE *fp, int flags)
 static int
 deque_init(dequeobject *deque, PyObject *args, PyObject *kwds)
 {
-	PyObject *iterable = NULL, *it, *item;
+	PyObject *iterable = NULL;
 
 	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()) 
+		PyObject *rv = deque_extend(deque, iterable);
+		if (rv == NULL)
 			return -1;
+		Py_DECREF(rv);
 	}
 	return 0;
 }
@@ -413,6 +460,10 @@ static PyMethodDef deque_methods[] = {
 		METH_NOARGS,	 popleft_doc},
 	{"__reduce__",	(PyCFunction)deque_reduce,	
 		METH_NOARGS,	 reduce_doc},
+	{"extend",		(PyCFunction)deque_extend,	
+		METH_O,		 extend_doc},
+	{"extendleft",	(PyCFunction)deque_extendleft,	
+		METH_O,		 extendleft_doc},
 	{NULL,		NULL}	/* sentinel */
 };