diff options
| -rw-r--r-- | Doc/lib/libcollections.tex | 19 | ||||
| -rw-r--r-- | Lib/test/test_deque.py | 17 | ||||
| -rw-r--r-- | Modules/collectionsmodule.c | 41 |
3 files changed, 63 insertions, 14 deletions
diff --git a/Doc/lib/libcollections.tex b/Doc/lib/libcollections.tex index 148ddea..c7d5c50 100644 --- a/Doc/lib/libcollections.tex +++ b/Doc/lib/libcollections.tex @@ -137,24 +137,21 @@ This section shows various approaches to working with deques. The \method{rotate()} method provides a way to implement \class{deque} slicing and deletion: +This pure python implementation of \code{del d[n]} shows how to use the +\method{rotate()} method as a building block for implementing a variety +of class{deque} operations: + \begin{verbatim} def delete_nth(d, n): - "del d[n]" d.rotate(-n) d.popleft() d.rotate(n) - ->>> d = deque('abcdef') ->>> delete_nth(d, 2) # remove the entry at d[2] ->>> d -deque(['a', 'b', 'd', 'e', 'f']) - \end{verbatim} -For slicing, the idea is the same. Use \method{rotate()} to bring a target -element to the left side of the deque. Remove old entries with -\method{popleft()}, add new entries with \method{extend()}, and then -reverse the rotation. +To implement \class{deque} slicing, use a similar approach applying +\method{rotate()} to bring a target element to the left side of the deque. +Remove old entries with \method{popleft()}, add new entries with +\method{extend()}, and then reverse the rotation. With minor variations on that approach, it is easy to implement Forth style stack manipulations such as \code{dup}, \code{drop}, \code{swap}, \code{over}, diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py index e8d9ce4..9b857c5 100644 --- a/Lib/test/test_deque.py +++ b/Lib/test/test_deque.py @@ -90,6 +90,20 @@ class TestBasic(unittest.TestCase): l[i] = 7*i self.assertEqual(list(d), l) + def test_delitem(self): + n = 500 # O(n**2) test, don't make this too big + d = deque(xrange(n)) + self.assertRaises(IndexError, d.__delitem__, -n-1) + self.assertRaises(IndexError, d.__delitem__, n) + for i in xrange(n): + self.assertEqual(len(d), n-i) + j = random.randrange(-len(d), len(d)) + val = d[j] + self.assert_(val in d) + del d[j] + self.assert_(val not in d) + self.assertEqual(len(d), 0) + def test_rotate(self): s = tuple('abcde') n = len(s) @@ -476,9 +490,7 @@ deque(['c', 'b', 'a']) - >>> def delete_nth(d, n): -... "del d[n]" ... d.rotate(-n) ... d.popleft() ... d.rotate(n) @@ -524,7 +536,6 @@ h >>> print maketree('abcdefgh') [[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]] - """ diff --git a/Modules/collectionsmodule.c b/Modules/collectionsmodule.c index fc30c99..e49224d 100644 --- a/Modules/collectionsmodule.c +++ b/Modules/collectionsmodule.c @@ -353,6 +353,44 @@ deque_item(dequeobject *deque, int i) } static int +deque_del_item(dequeobject *deque, int i) +{ + PyObject *item=NULL, *minus_i=NULL, *plus_i=NULL; + int rv = -1; + + assert (i >= 0 && i < deque->len); + + minus_i = Py_BuildValue("(i)", -i); + if (minus_i == NULL) + goto fail; + + plus_i = Py_BuildValue("(i)", i); + if (plus_i == NULL) + goto fail; + + item = deque_rotate(deque, minus_i); + if (item == NULL) + goto fail; + Py_DECREF(item); + + item = deque_popleft(deque, NULL); + if (item == NULL) + goto fail; + Py_DECREF(item); + + item = deque_rotate(deque, plus_i); + if (item == NULL) + goto fail; + + rv = 0; +fail: + Py_XDECREF(item); + Py_XDECREF(minus_i); + Py_XDECREF(plus_i); + return rv; +} + +static int deque_ass_item(dequeobject *deque, int i, PyObject *v) { PyObject *old_value; @@ -364,6 +402,9 @@ deque_ass_item(dequeobject *deque, int i, PyObject *v) "deque index out of range"); return -1; } + if (v == NULL) + return deque_del_item(deque, i); + i += deque->leftindex; n = i / BLOCKLEN; i %= BLOCKLEN; |