diff options
| -rw-r--r-- | Doc/library/collections.rst | 5 | ||||
| -rw-r--r-- | Lib/test/test_deque.py | 12 | ||||
| -rw-r--r-- | Misc/NEWS | 2 | ||||
| -rw-r--r-- | Modules/_collectionsmodule.c | 44 |
4 files changed, 63 insertions, 0 deletions
diff --git a/Doc/library/collections.rst b/Doc/library/collections.rst index dc81c0a..db9babf 100644 --- a/Doc/library/collections.rst +++ b/Doc/library/collections.rst @@ -379,6 +379,11 @@ counts, but the output will exclude results with counts of zero or less. .. versionadded:: 2.5 + .. method:: reverse() + + Reverse the elements of the deque in-place and then return ``None``. + + .. versionadded:: 2.7 .. method:: rotate(n) diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py index 23641ba..c1f1667 100644 --- a/Lib/test/test_deque.py +++ b/Lib/test/test_deque.py @@ -204,6 +204,18 @@ class TestBasic(unittest.TestCase): 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) @@ -513,6 +513,8 @@ Core and Builtins Library ------- +- Add a reverse() method to collections.deque(). + - Fix variations of extending deques: d.extend(d) d.extendleft(d) d+=d - Issue #6986: Fix crash in the JSON C accelerator when called with the diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c index 97b3905..978bd9a 100644 --- a/Modules/_collectionsmodule.c +++ b/Modules/_collectionsmodule.c @@ -462,6 +462,48 @@ deque_rotate(dequeobject *deque, PyObject *args) 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) { @@ -963,6 +1005,8 @@ static PyMethodDef deque_methods[] = { 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 */ |