From 44459debc620106ed156c6ae8bc32ec02e3dec98 Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Sat, 3 Apr 2010 23:20:46 +0000
Subject: Add count() method to collections.deque().

---
 Doc/library/collections.rst  |  6 ++++++
 Lib/test/test_deque.py       | 24 ++++++++++++++++++++++++
 Misc/NEWS                    |  2 +-
 Modules/_collectionsmodule.c | 42 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 73 insertions(+), 1 deletion(-)

diff --git a/Doc/library/collections.rst b/Doc/library/collections.rst
index aa17a55..3d04063 100644
--- a/Doc/library/collections.rst
+++ b/Doc/library/collections.rst
@@ -338,6 +338,12 @@ counts, but the output will exclude results with counts of zero or less.
       Remove all elements from the deque leaving it with length 0.
 
 
+   .. method:: count(x)
+
+      Count the number of deque elements equal to *x*.
+
+      .. versionadded:: 3.2
+
    .. method:: extend(iterable)
 
       Extend the right side of the deque by appending elements from the iterable
diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py
index a2f5fae..17d724c 100644
--- a/Lib/test/test_deque.py
+++ b/Lib/test/test_deque.py
@@ -114,6 +114,30 @@ class TestBasic(unittest.TestCase):
             d = deque('abc')
             d.maxlen = 10
 
+    def test_count(self):
+        for s in ('', 'abracadabra', 'simsalabim'*500+'abc'):
+            s = list(s)
+            d = deque(s)
+            for letter in 'abcdefghijklmnopqrstuvwxyz':
+                self.assertEqual(s.count(letter), d.count(letter), (s, d, letter))
+        self.assertRaises(TypeError, d.count)       # too few args
+        self.assertRaises(TypeError, d.count, 1, 2) # too many args
+        class BadCompare:
+            def __eq__(self, other):
+                raise ArithmeticError
+        d = deque([1, 2, BadCompare(), 3])
+        self.assertRaises(ArithmeticError, d.count, 2)
+        d = deque([1, 2, 3])
+        self.assertRaises(ArithmeticError, d.count, BadCompare())
+        class MutatingCompare:
+            def __eq__(self, other):
+                self.d.pop()
+                return True
+        m = MutatingCompare()
+        d = deque([1, 2, 3, m, 4, 5])
+        m.d = d
+        self.assertRaises(RuntimeError, d.count, 3)
+
     def test_comparisons(self):
         d = deque('xabc'); d.popleft()
         for e in [d, deque('abc'), deque('ab'), deque(), list(d)]:
diff --git a/Misc/NEWS b/Misc/NEWS
index e042975..7c23e26 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -576,7 +576,7 @@ Library
 - Issue #5949: added check for correct lineends in input from IMAP server
   in imaplib.
 
-- Add a reverse() method to collections.deque().
+- Add count() and reverse() methods to collections.deque().
 
 - Fix variations of extending deques:  d.extend(d)  d.extendleft(d)  d+=d
 
diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c
index ffb2a80..fa0f004 100644
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -504,6 +504,46 @@ deque_reverse(dequeobject *deque, PyObject *unused)
 PyDoc_STRVAR(reverse_doc,
 "D.reverse() -- reverse *IN PLACE*");
 
+static PyObject *
+deque_count(dequeobject *deque, PyObject *v)
+{
+	block *leftblock = deque->leftblock;
+	Py_ssize_t leftindex = deque->leftindex;
+	Py_ssize_t n = (deque->len);
+	Py_ssize_t i;
+	Py_ssize_t count = 0;
+	PyObject *item;
+	long start_state = deque->state;
+	int cmp;
+
+	for (i=0 ; i<n ; i++) {
+		item = leftblock->data[leftindex];
+		cmp = PyObject_RichCompareBool(item, v, Py_EQ);
+		if (cmp > 0)
+			count++;
+		else if (cmp < 0)
+			return NULL;
+
+		if (start_state != deque->state) {
+			PyErr_SetString(PyExc_RuntimeError,
+					"deque mutated during iteration");
+			return NULL;
+		}
+
+		/* Advance left block/index pair */
+		leftindex++;
+		if (leftindex == BLOCKLEN) {
+			assert (leftblock->rightlink != NULL);
+			leftblock = leftblock->rightlink;
+			leftindex = 0;
+		}
+	}
+	return PyLong_FromSsize_t(count);
+}
+
+PyDoc_STRVAR(count_doc,
+"D.count(value) -> integer -- return number of occurrences of value");
+
 static Py_ssize_t
 deque_len(dequeobject *deque)
 {
@@ -933,6 +973,8 @@ static PyMethodDef deque_methods[] = {
 		METH_NOARGS,	 clear_doc},
 	{"__copy__",		(PyCFunction)deque_copy,
 		METH_NOARGS,	 copy_doc},
+	{"count",		(PyCFunction)deque_count,
+	    METH_O,			count_doc},
 	{"extend",		(PyCFunction)deque_extend,
 		METH_O,		 extend_doc},
 	{"extendleft",		(PyCFunction)deque_extendleft,
-- 
cgit v0.12