Have deques support high volume loads.
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 @@
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 @@
['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 @@
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 @@
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 @@
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)
+ PyObject *rv = deque_extend(deque, iterable);
+ if (rv == 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;
+ Py_DECREF(rv);
}
return 0;
}
@@ -413,6 +460,10 @@
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 */
};