Make sure "del d[n]" is properly supported. Was necessary because the
same method that implements __setitem__ also implements __delitem__.
Also, there were several good use cases (removing items from a queue
and implementing Forth style stack ops).
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 @@
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 @@
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 @@
-
>>> def delete_nth(d, n):
-... "del d[n]"
... d.rotate(-n)
... d.popleft()
... d.rotate(n)
@@ -524,7 +536,6 @@
>>> 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 @@
}
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 index out of range");
return -1;
}
+ if (v == NULL)
+ return deque_del_item(deque, i);
+
i += deque->leftindex;
n = i / BLOCKLEN;
i %= BLOCKLEN;