From 4aec61e0fc29217c93acd0615ad54bd081a64658 Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Fri, 18 Mar 2005 21:20:23 +0000
Subject: Add a remove() method to collections.deque objects.

---
 Doc/lib/libcollections.tex  |  6 ++++++
 Lib/test/test_deque.py      | 35 +++++++++++++++++++++++++++++++++++
 Misc/NEWS                   |  2 ++
 Modules/collectionsmodule.c | 39 ++++++++++++++++++++++++++++++++++++++-
 4 files changed, 81 insertions(+), 1 deletion(-)

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 @@ Deque objects support the following methods:
    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 @@ def fail():
     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 @@ class TestBasic(unittest.TestCase):
         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 @@ Core and builtins
 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 @@ deque_len(dequeobject *deque)
 	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 @@ static PyMethodDef deque_methods[] = {
 		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 @@ static PyMethodDef deque_methods[] = {
 		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,
-- 
cgit v0.12