[Python-checkins] r76729 - in python/branches/py3k: Doc/library/collections.rst Lib/test/test_deque.py Misc/NEWS Modules/_collectionsmodule.c

[raymond.hettinger]

Author: raymond.hettinger
Date: Thu Dec 10 01:47:21 2009
New Revision: 76729

Log:
Add a reverse() method to collections.deque().

Modified:
   python/branches/py3k/Doc/library/collections.rst
   python/branches/py3k/Lib/test/test_deque.py
   python/branches/py3k/Misc/NEWS
   python/branches/py3k/Modules/_collectionsmodule.c

Modified: python/branches/py3k/Doc/library/collections.rst
==============================================================================
--- python/branches/py3k/Doc/library/collections.rst	(original)
+++ python/branches/py3k/Doc/library/collections.rst	Thu Dec 10 01:47:21 2009
@@ -357,6 +357,11 @@
       Removed the first occurrence of *value*.  If not found, raises a
       :exc:`ValueError`.
 
+   .. method:: reverse()
+
+      Reverse the elements of the deque in-place and then return ``None``.
+
+      .. versionadded:: 3.2
 
    .. method:: rotate(n)
 

Modified: python/branches/py3k/Lib/test/test_deque.py
==============================================================================
--- python/branches/py3k/Lib/test/test_deque.py	(original)
+++ python/branches/py3k/Lib/test/test_deque.py	Thu Dec 10 01:47:21 2009
@@ -193,6 +193,18 @@
             self.assertTrue(val not in d)
         self.assertEqual(len(d), 0)
 
+    def test_reverse(self):
+        n = 500         # O(n**2) test, don't make this too big
+        data = [random.random() for i in range(n)]
+        for i in range(n):
+            d = deque(data[:i])
+            r = d.reverse()
+            self.assertEqual(list(d), list(reversed(data[:i])))
+            self.assert_(r is None)
+            d.reverse()
+            self.assertEqual(list(d), data[:i])
+        self.assertRaises(TypeError, d.reverse, 1)          # Arity is zero
+
     def test_rotate(self):
         s = tuple('abcde')
         n = len(s)

Modified: python/branches/py3k/Misc/NEWS
==============================================================================
--- python/branches/py3k/Misc/NEWS	(original)
+++ python/branches/py3k/Misc/NEWS	Thu Dec 10 01:47:21 2009
@@ -154,6 +154,8 @@
 Library
 -------
 
+- Add a reverse() method to collections.deque().
+
 - Issue #6986: Fix crash in the JSON C accelerator when called with the
   wrong parameter types.  Patch by Victor Stinner.
 

Modified: python/branches/py3k/Modules/_collectionsmodule.c
==============================================================================
--- python/branches/py3k/Modules/_collectionsmodule.c	(original)
+++ python/branches/py3k/Modules/_collectionsmodule.c	Thu Dec 10 01:47:21 2009
@@ -427,6 +427,48 @@
 PyDoc_STRVAR(rotate_doc,
 "Rotate the deque n steps to the right (default n=1).  If n is negative, rotates left.");
 
+static PyObject *
+deque_reverse(dequeobject *deque, PyObject *unused)
+{
+	block *leftblock = deque->leftblock;
+	block *rightblock = deque->rightblock;
+	Py_ssize_t leftindex = deque->leftindex;
+	Py_ssize_t rightindex = deque->rightindex;
+	Py_ssize_t n = (deque->len)/2;
+	Py_ssize_t i;
+	PyObject *tmp;
+
+	for (i=0 ; i<n ; i++) {
+		/* Validate that pointers haven't met in the middle */
+		assert(leftblock != rightblock || leftindex < rightindex);
+
+		/* Swap */
+		tmp = leftblock->data[leftindex];
+		leftblock->data[leftindex] = rightblock->data[rightindex];
+		rightblock->data[rightindex] = tmp;
+
+		/* Advance left block/index pair */
+		leftindex++;
+		if (leftindex == BLOCKLEN) {
+			assert (leftblock->rightlink != NULL);
+			leftblock = leftblock->rightlink;
+			leftindex = 0;
+		}
+
+		/* Step backwards with the right block/index pair */
+		rightindex--;
+		if (rightindex == -1) {
+			assert (rightblock->leftlink != NULL);
+			rightblock = rightblock->leftlink;
+			rightindex = BLOCKLEN - 1;
+		}
+	}
+	Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(reverse_doc,
+"D.reverse() -- reverse *IN PLACE*");
+
 static Py_ssize_t
 deque_len(dequeobject *deque)
 {
@@ -865,6 +907,8 @@
 		METH_O,		 remove_doc},
 	{"__reversed__",	(PyCFunction)deque_reviter,
 		METH_NOARGS,	 reversed_doc},
+	{"reverse",		(PyCFunction)deque_reverse,
+		METH_NOARGS,	 reverse_doc},
 	{"rotate",		(PyCFunction)deque_rotate,
 		METH_VARARGS,	rotate_doc},
 	{NULL,		NULL}	/* sentinel */