From 5c5eb8634703b7e463ade6707d2b6f1a80769286 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Sat, 7 Feb 2004 21:13:00 +0000 Subject: * Incorporate Skip's suggestions for documentation (explain the word deque comes from and show the differences from lists). * Add a rotate() method. --- Doc/lib/libcollections.tex | 64 +++++++++++++++++++++++++++++---------------- Lib/test/test_deque.py | 12 +++++++++ Modules/collectionsmodule.c | 48 +++++++++++++++++++++++++++++++--- 3 files changed, 98 insertions(+), 26 deletions(-) diff --git a/Doc/lib/libcollections.tex b/Doc/lib/libcollections.tex index 55ab431..0378ea5 100644 --- a/Doc/lib/libcollections.tex +++ b/Doc/lib/libcollections.tex @@ -1,5 +1,5 @@ \section{\module{collections} --- - High-performance datatypes} + High-performance container datatypes} \declaremodule{standard}{collections} \modulesynopsis{High-performance datatypes} @@ -8,7 +8,7 @@ \versionadded{2.4} -This module implements high-performance datatypes. Currently, the +This module implements high-performance container datatypes. Currently, the only datatype is a deque. Future additions may include B-trees and Fibonacci heaps. @@ -17,9 +17,15 @@ and Fibonacci heaps. \method{append()}) with data from \var{iterable}. If \var{iterable} is not specified, the new deque is empty. - Deques are a generalization of stacks and queues. They support - thread-safe, memory efficient appends and pops from either side of the - deque with approximately the same performance in either direction. + Deques are a generalization of stacks and queues (the name is pronounced + ``deck'' and is short for ``double-ended queue''). Deques support + thread-safe, memory efficient appends and pops from either side of the deque + with approximately the same \code{O(1)} performance in either direction. + + Though \class{list} objects support similar operations, they are optimized + for fast fixed-length operations and incur \code{O(n)} memory movement costs + for \samp{pop(0)} and \samp{insert(0, v)} operations which change both the + size and position of the underlying data representation. \versionadded{2.4} \end{funcdesc} @@ -58,48 +64,62 @@ Deque objects support the following methods: If no elements are present, raises a \exception{LookupError}. \end{methoddesc} -In addition to the above, deques support iteration, membership testing -using the \keyword{in} operator, \samp{len(d)}, \samp{copy.copy(d)}, -\samp{copy.deepcopy(d)}, \samp{reversed(d)} and pickling. +\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 + is equivalent to: \samp{d.appendleft(d.pop())}. +\end{methoddesc} + +In addition to the above, deques support iteration, pickling, \samp{len(d)}, +\samp{reversed(d)}, \samp{copy.copy(d)}, \samp{copy.deepcopy(d)}, and +membership testing with the \keyword{in} operator. Example: \begin{verbatim} >>> from collections import deque ->>> d = deque('ghi') # make a new deque with three items ->>> for elem in d: # iterate over the deque's elements +>>> d = deque('ghi') # make a new deque with three items +>>> for elem in d: # iterate over the deque's elements print elem.upper() G H I ->>> d.append('j') # add a new entry to the right side ->>> d.appendleft('f') # add a new entry to the left side ->>> d # show the representation of the deque +>>> d.append('j') # add a new entry to the right side +>>> d.appendleft('f') # add a new entry to the left side +>>> d # show the representation of the deque deque(['f', 'g', 'h', 'i', 'j']) ->>> d.pop() # return and remove the rightmost item +>>> d.pop() # return and remove the rightmost item 'j' ->>> d.popleft() # return and remove the leftmost item +>>> d.popleft() # return and remove the leftmost item 'f' ->>> list(d) # list the contents of the deque +>>> list(d) # list the contents of the deque ['g', 'h', 'i'] ->>> list(reversed(d)) # list the contents of a deque in reverse +>>> list(reversed(d)) # list the contents of a deque in reverse ['i', 'h', 'g'] ->>> 'h' in d # search the deque +>>> 'h' in d # search the deque True ->>> d.extend('jkl') # extend() will append many elements at once +>>> d.extend('jkl') # add multiple elements at once +>>> d +deque(['g', 'h', 'i', 'j', 'k', 'l']) +>>> d.rotate(1) # right rotation +>>> d +deque(['l', 'g', 'h', 'i', 'j', 'k']) +>>> d.rotate(-1) # left rotation >>> d deque(['g', 'h', 'i', 'j', 'k', 'l']) ->>> d.clear() # empty the deque ->>> d.pop() # cannot pop from an empty deque +>>> deque(reversed(d)) # make a new deque in reverse order +deque(['l', 'k', 'j', 'i', 'h', 'g']) +>>> d.clear() # empty the deque +>>> d.pop() # cannot pop from an empty deque Traceback (most recent call last): File "", line 1, in -toplevel- d.pop() LookupError: pop from an empty deque ->>> d.extendleft('abc') # extendleft() reverses the element order +>>> d.extendleft('abc') # extendleft() reverses the input order >>> d deque(['c', 'b', 'a']) diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py index 5f2417f..016c2ae 100644 --- a/Lib/test/test_deque.py +++ b/Lib/test/test_deque.py @@ -40,6 +40,18 @@ class TestBasic(unittest.TestCase): d.extendleft('bcd') self.assertEqual(list(d), list(reversed('abcd'))) + def test_rotate(self): + s = 'abcde' + d = deque(s) + d.rotate(2) + self.assertEqual(''.join(d), 'deabc') + d.rotate(3) + self.assertEqual(''.join(d), s) + d.rotate(-3) + self.assertEqual(''.join(d), 'deabc') + d.rotate(-15) + self.assertEqual(''.join(d), 'deabc') + def test_len(self): d = deque('ab') self.assertEqual(len(d), 2) diff --git a/Modules/collectionsmodule.c b/Modules/collectionsmodule.c index 3533fc5..d60ede1 100644 --- a/Modules/collectionsmodule.c +++ b/Modules/collectionsmodule.c @@ -244,6 +244,44 @@ deque_extendleft(dequeobject *deque, PyObject *iterable) PyDoc_STRVAR(extendleft_doc, "Extend the left side of the deque with elements from the iterable"); +static PyObject * +deque_rotate(dequeobject *deque, PyObject *args) +{ + int i, n; + PyObject *item, *rv; + + if (!PyArg_ParseTuple(args, "i:rotate", &n)) + return NULL; + + if (n == 0 || deque->len == 0) + Py_RETURN_NONE; + + for (i=0 ; in ; i--) { + item = deque_popleft(deque, NULL); + if (item == NULL) + return NULL; + rv = deque_append(deque, item); + Py_DECREF(item); + if (rv == NULL) + return NULL; + Py_DECREF(rv); + } + Py_RETURN_NONE; +} + +PyDoc_STRVAR(rotate_doc, +"Rotate the deque n steps to the right. If n is negative, rotates left."); + static int deque_len(dequeobject *deque) { @@ -461,6 +499,10 @@ static PyMethodDef deque_methods[] = { METH_NOARGS, clear_doc}, {"__copy__", (PyCFunction)deque_copy, METH_NOARGS, copy_doc}, + {"extend", (PyCFunction)deque_extend, + METH_O, extend_doc}, + {"extendleft", (PyCFunction)deque_extendleft, + METH_O, extendleft_doc}, {"pop", (PyCFunction)deque_pop, METH_NOARGS, pop_doc}, {"popleft", (PyCFunction)deque_popleft, @@ -469,10 +511,8 @@ static PyMethodDef deque_methods[] = { METH_NOARGS, reduce_doc}, {"__reversed__", (PyCFunction)deque_reviter, METH_NOARGS, reversed_doc}, - {"extend", (PyCFunction)deque_extend, - METH_O, extend_doc}, - {"extendleft", (PyCFunction)deque_extendleft, - METH_O, extendleft_doc}, + {"rotate", (PyCFunction)deque_rotate, + METH_VARARGS, rotate_doc}, {NULL, NULL} /* sentinel */ }; -- cgit v0.12