Add a remove() method to collections.deque objects.
diff --git a/Doc/lib/libcollections.tex b/Doc/lib/libcollections.tex
index 84cc507..51603aa 100644
--- a/Doc/lib/libcollections.tex
+++ b/Doc/lib/libcollections.tex
@@ -64,6 +64,12 @@
If no elements are present, raises a \exception{IndexError}.
\end{methoddesc}
+\begin{methoddesc}{remove}{value}
+ Removed the first occurrence of \var{value}. If not found,
+ raises a \exception{ValueError}.
+ \versionadded{2.5}
+\end{methoddesc}
+
\begin{methoddesc}{rotate}{n}
Rotate the deque \var{n} steps to the right. If \var{n} is
negative, rotate to the left. Rotating one step to the right
diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py
index 0a6c1f9..f498124 100644
--- a/Lib/test/test_deque.py
+++ b/Lib/test/test_deque.py
@@ -14,6 +14,17 @@
raise SyntaxError
yield 1
+class BadCmp:
+ def __eq__(self, other):
+ raise RuntimeError
+
+class MutateCmp:
+ def __init__(self, deque):
+ self.deque = deque
+ def __eq__(self, other):
+ self.deque.clear()
+ return True
+
class TestBasic(unittest.TestCase):
def test_basics(self):
@@ -197,6 +208,30 @@
d.clear() # clear an emtpy deque
self.assertEqual(list(d), [])
+ def test_remove(self):
+ d = deque('abcdefghcij')
+ d.remove('c')
+ self.assertEqual(d, deque('abdefghcij'))
+ d.remove('c')
+ self.assertEqual(d, deque('abdefghij'))
+ self.assertRaises(ValueError, d.remove, 'c')
+ self.assertEqual(d, deque('abdefghij'))
+
+ # Handle comparision errors
+ d = deque(['a', 'b', BadCmp(), 'c'])
+ e = deque(d)
+ self.assertRaises(RuntimeError, d.remove, 'c')
+ for x, y in zip(d, e):
+ # verify that original order and values are retained.
+ self.assert_(x is y)
+
+ # Handle evil mutator
+ d = deque(['ab'])
+ d.extend([MutateCmp(d), 'c'])
+ e = deque(d)
+ self.assertRaises(IndexError, d.remove, 'c')
+ self.assertEqual(d, deque())
+
def test_repr(self):
d = deque(xrange(200))
e = eval(repr(d))
diff --git a/Misc/NEWS b/Misc/NEWS
index bfeda83..9e3ffa4 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -49,6 +49,8 @@
Extension Modules
-----------------
+- collections.deque objects now support a remove() method.
+
- operator.itemgetter() and operator.attrgetter() now support retrieving
multiple fields. This provides direct support for sorting on multiple
keys (primary, secondary, etc).
diff --git a/Modules/collectionsmodule.c b/Modules/collectionsmodule.c
index ed10999..49c486f 100644
--- a/Modules/collectionsmodule.c
+++ b/Modules/collectionsmodule.c
@@ -368,6 +368,41 @@
return deque->len;
}
+static PyObject *
+deque_remove(dequeobject *deque, PyObject *value)
+{
+ int i, n=deque->len;
+
+ for (i=0 ; i<n ; i++) {
+ PyObject *item = deque->leftblock->data[deque->leftindex];
+ int cmp = PyObject_RichCompareBool(item, value, Py_EQ);
+ if (cmp > 0) {
+ PyObject *tgt;
+ if (deque->len != n) {
+ PyErr_SetString(PyExc_IndexError,
+ "deque mutated during remove().");
+ return NULL;
+ }
+ tgt = deque_popleft(deque, NULL);
+ assert (tgt != NULL);
+ Py_DECREF(tgt);
+ if (_deque_rotate(deque, i) == -1)
+ return NULL;
+ Py_RETURN_NONE;
+ }
+ else if (cmp < 0) {
+ _deque_rotate(deque, i);
+ return NULL;
+ }
+ _deque_rotate(deque, -1);
+ }
+ PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");
+ return NULL;
+}
+
+PyDoc_STRVAR(remove_doc,
+"D.remove(value) -- remove first occurrence of value.");
+
static int
deque_clear(dequeobject *deque)
{
@@ -764,7 +799,7 @@
METH_NOARGS, copy_doc},
{"extend", (PyCFunction)deque_extend,
METH_O, extend_doc},
- {"extendleft", (PyCFunction)deque_extendleft,
+ {"extendleft", (PyCFunction)deque_extendleft,
METH_O, extendleft_doc},
{"pop", (PyCFunction)deque_pop,
METH_NOARGS, pop_doc},
@@ -772,6 +807,8 @@
METH_NOARGS, popleft_doc},
{"__reduce__", (PyCFunction)deque_reduce,
METH_NOARGS, reduce_doc},
+ {"remove", (PyCFunction)deque_remove,
+ METH_O, remove_doc},
{"__reversed__", (PyCFunction)deque_reviter,
METH_NOARGS, reversed_doc},
{"rotate", (PyCFunction)deque_rotate,