Replace left(), right(), and __reversed__() with the more general purpose

__getitem__() and __setitem__().

Simplifies the API, reduces the code size, adds flexibility, and makes
deques work with bisect.bisect(), random.shuffle(), and random.sample().

4 files changed, 110 insertions, 148 deletions

diff --git a/Doc/lib/libcollections.tex b/Doc/lib/libcollections.tex
index 2793095..14e3bf5 100644
--- a/Doc/lib/libcollections.tex
+++ b/Doc/lib/libcollections.tex
@@ -54,11 +54,6 @@ Deque objects support the following methods:
    reversing the order of elements in the iterable argument.
 \end{methoddesc}
 
-\begin{methoddesc}{left}{}
-   Return leftmost element from the deque.
-   If no elements are present, raises a \exception{IndexError}.   
-\end{methoddesc}
-
 \begin{methoddesc}{pop}{}
    Remove and return an element from the right side of the deque.
    If no elements are present, raises a \exception{IndexError}.
@@ -69,11 +64,6 @@ Deque objects support the following methods:
    If no elements are present, raises a \exception{IndexError}.   
 \end{methoddesc}
 
-\begin{methoddesc}{right}{}
-   Return the rightmost element from the deque.
-   If no elements are present, raises a \exception{IndexError}.   
-\end{methoddesc}
-
 \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
@@ -81,8 +71,9 @@ Deque objects support the following methods:
 \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.
+\samp{reversed(d)}, \samp{copy.copy(d)}, \samp{copy.deepcopy(d)},
+membership testing with the \keyword{in} operator, and subscript references
+such as \samp{d[-1]}.
 
 Example:
 
@@ -106,11 +97,11 @@ deque(['f', 'g', 'h', 'i', 'j'])
 'f'
 >>> list(d)                          # list the contents of the deque
 ['g', 'h', 'i']
-
->>> d.left()                         # peek at leftmost item
+>>> d[0]                             # peek at leftmost item
 'g'
->>> d.right()                        # peek at rightmost item
+>>> d[-1]                            # peek at rightmost item
 'i'
+
 >>> list(reversed(d))                # list the contents of a deque in reverse
 ['i', 'h', 'g']
 >>> 'h' in d                         # search the deque
diff --git a/Lib/asynchat.py b/Lib/asynchat.py
index 2c0bc3e..062ab3e 100644
--- a/Lib/asynchat.py
+++ b/Lib/asynchat.py
@@ -262,7 +262,7 @@ class fifo:
         return self.list == []
 
     def first (self):
-        return self.list.left()
+        return self.list[0]
 
     def push (self, data):
         self.list.append(data)
diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py
index db9733e..a99de03 100644
--- a/Lib/test/test_deque.py
+++ b/Lib/test/test_deque.py
@@ -4,6 +4,7 @@ from test import test_support
 import copy
 import cPickle as pickle
 from cStringIO import StringIO
+import random
 
 BIG = 100000
 
@@ -57,13 +58,37 @@ class TestBasic(unittest.TestCase):
         d.extendleft('bcd')
         self.assertEqual(list(d), list(reversed('abcd')))
 
-    def test_leftright(self):
+    def test_getitem(self):
+        n = 200
+        d = deque(xrange(n))
+        l = range(n)
+        for i in xrange(n):
+            d.popleft()
+            l.pop(0)
+            if random.random() < 0.5:
+                d.append(i)
+                l.append(i)
+            for j in xrange(1-len(l), len(l)):
+                assert d[j] == l[j]
+
         d = deque('superman')
-        self.assertEqual(d.left(), 's')
-        self.assertEqual(d.right(), 'n')
+        self.assertEqual(d[0], 's')
+        self.assertEqual(d[-1], 'n')
         d = deque()
-        self.assertRaises(IndexError, d.left)
-        self.assertRaises(IndexError, d.right)
+        self.assertRaises(IndexError, d.__getitem__, 0)
+        self.assertRaises(IndexError, d.__getitem__, -1)
+
+    def test_setitem(self):
+        n = 200
+        d = deque(xrange(n))
+        for i in xrange(n):
+            d[i] = 10 * i
+        self.assertEqual(list(d), [10*i for i in xrange(n)])
+        l = list(d)
+        for i in xrange(1-n, 0, -1):
+            d[i] = 7*i
+            l[i] = 7*i
+        self.assertEqual(list(d), l)
 
     def test_rotate(self):
         s = tuple('abcde')
@@ -405,7 +430,7 @@ Example from the Library Reference:  Doc/lib/libcollections.tex
 >>> from collections import deque
 >>> d = deque('ghi')                 # make a new deque with three items
 >>> for elem in d:                   # iterate over the deque's elements
-...     print elem.upper()	
+...     print elem.upper()
 G
 H
 I
@@ -419,9 +444,9 @@ deque(['f', 'g', 'h', 'i', 'j'])
 'f'
 >>> list(d)                          # list the contents of the deque
 ['g', 'h', 'i']
->>> d.left()                         # peek at leftmost item
+>>> d[0]                             # peek at leftmost item
 'g'
->>> d.right()                        # peek at rightmost item
+>>> d[-1]                            # peek at rightmost item
 'i'
 >>> list(reversed(d))                # list the contents of a deque in reverse
 ['i', 'h', 'g']
@@ -476,7 +501,7 @@ def test_main(verbose=None):
             gc.collect()
             counts[i] = sys.gettotalrefcount()
         print counts
-        
+
     # doctests
     from test import test_deque
     test_support.run_doctest(test_deque, verbose)
diff --git a/Modules/collectionsmodule.c b/Modules/collectionsmodule.c
index 252c5a6..f7fb91f 100644
--- a/Modules/collectionsmodule.c
+++ b/Modules/collectionsmodule.c
@@ -177,38 +177,6 @@ deque_popleft(dequeobject *deque, PyObject *unused)
 PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");
 
 static PyObject *
-deque_right(dequeobject *deque, PyObject *unused)
-{
-	PyObject *item;
-
-	if (deque->len == 0) {
-		PyErr_SetString(PyExc_IndexError, "deque is empty");
-		return NULL;
-	}
-	item = deque->rightblock->data[deque->rightindex];
-	Py_INCREF(item);
-	return item;
-}
-
-PyDoc_STRVAR(right_doc, "Return the rightmost element.");
-
-static PyObject *
-deque_left(dequeobject *deque, PyObject *unused)
-{
-	PyObject *item;
-
-	if (deque->len == 0) {
-		PyErr_SetString(PyExc_IndexError, "deque is empty");
-		return NULL;
-	}
-	item = deque->leftblock->data[deque->leftindex];
-	Py_INCREF(item);
-	return item;
-}
-
-PyDoc_STRVAR(left_doc, "Return the leftmost element.");
-
-static PyObject *
 deque_extend(dequeobject *deque, PyObject *iterable)
 {
 	PyObject *it, *item;
@@ -346,6 +314,69 @@ deque_clear(dequeobject *deque)
 }
 
 static PyObject *
+deque_item(dequeobject *deque, int i)
+{
+	block *b;
+	PyObject *item;
+	int n;
+
+	if (i < 0 || i >= deque->len) {
+		PyErr_SetString(PyExc_IndexError,
+				"deque index out of range");
+		return NULL;
+	}
+
+	i += deque->leftindex;
+	n = i / BLOCKLEN;
+	i %= BLOCKLEN;
+	if (i < (deque->len >> 1)) {
+		b = deque->leftblock;
+		while (n--)
+			b = b->rightlink;
+	} else {
+		n = (deque->leftindex + deque->len - 1) / BLOCKLEN - n;
+		b = deque->rightblock;
+		while (n--)
+			b = b->leftlink;
+	}
+	item = b->data[i];
+	Py_INCREF(item);
+	return item;
+}
+
+static int
+deque_ass_item(dequeobject *deque, int i, PyObject *v)
+{
+	PyObject *old_value;
+	block *b;
+	int n;
+
+	if (i < 0 || i >= deque->len) {
+		PyErr_SetString(PyExc_IndexError,
+				"deque index out of range");
+		return -1;
+	}
+	i += deque->leftindex;
+	n = i / BLOCKLEN;
+	i %= BLOCKLEN;
+	if (i < (deque->len >> 1)) {
+		b = deque->leftblock;
+		while (n--)
+			b = b->rightlink;
+	} else {
+		n = (deque->leftindex + deque->len - 1) / BLOCKLEN - n;
+		b = deque->rightblock;
+		while (n--)
+			b = b->leftlink;
+	}
+	Py_INCREF(v);
+	old_value = b->data[i];
+	b->data[i] = v;
+	Py_DECREF(old_value);
+	return 0;
+}
+
+static PyObject *
 deque_clearmethod(dequeobject *deque)
 {
 	if (deque_clear(deque) == -1)
@@ -371,7 +402,7 @@ deque_dealloc(dequeobject *deque)
 }
 
 static int
-set_traverse(dequeobject *deque, visitproc visit, void *arg)
+deque_traverse(dequeobject *deque, visitproc visit, void *arg)
 {
 	block * b = deque->leftblock;
 	int index = deque->leftindex;
@@ -597,14 +628,15 @@ deque_init(dequeobject *deque, PyObject *args, PyObject *kwds)
 static PySequenceMethods deque_as_sequence = {
 	(inquiry)deque_len,		/* sq_length */
 	0,				/* sq_concat */
+	0,				/* sq_repeat */
+	(intargfunc)deque_item,		/* sq_item */
+	0,				/* sq_slice */
+	(intobjargproc)deque_ass_item,	/* sq_ass_item */
 };
 
 /* deque object ********************************************************/
 
 static PyObject *deque_iter(dequeobject *deque);
-static PyObject *deque_reviter(dequeobject *deque);
-PyDoc_STRVAR(reversed_doc, 
-	"D.__reversed__() -- return a reverse iterator over the deque");
 
 static PyMethodDef deque_methods[] = {
 	{"append",		(PyCFunction)deque_append,	
@@ -619,18 +651,12 @@ static PyMethodDef deque_methods[] = {
 		METH_O,		 extend_doc},
 	{"extendleft",	(PyCFunction)deque_extendleft,	
 		METH_O,		 extendleft_doc},
-	{"left",		(PyCFunction)deque_left,	
-		METH_NOARGS,	 left_doc},
 	{"pop",			(PyCFunction)deque_pop,	
 		METH_NOARGS,	 pop_doc},
 	{"popleft",		(PyCFunction)deque_popleft,	
 		METH_NOARGS,	 popleft_doc},
 	{"__reduce__",	(PyCFunction)deque_reduce,	
 		METH_NOARGS,	 reduce_doc},
-	{"__reversed__",	(PyCFunction)deque_reviter,	
-		METH_NOARGS,	 reversed_doc},
-	{"right",		(PyCFunction)deque_right,	
-		METH_NOARGS,	 right_doc},
 	{"rotate",		(PyCFunction)deque_rotate,	
 		METH_VARARGS,	rotate_doc},
 	{NULL,		NULL}	/* sentinel */
@@ -665,7 +691,7 @@ static PyTypeObject deque_type = {
 	0,				/* tp_as_buffer */
 	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,	/* tp_flags */
 	deque_doc,			/* tp_doc */
-	(traverseproc)set_traverse,	/* tp_traverse */
+	(traverseproc)deque_traverse,	/* tp_traverse */
 	(inquiry)deque_clear,		/* tp_clear */
 	(richcmpfunc)deque_richcompare,	/* tp_richcompare */
 	0,				/* tp_weaklistoffset*/
@@ -777,83 +803,6 @@ PyTypeObject dequeiter_type = {
 	0,
 };
 
-/*********************** Deque Reverse Iterator **************************/
-
-PyTypeObject dequereviter_type;
-
-static PyObject *
-deque_reviter(dequeobject *deque)
-{
-	dequeiterobject *it;
-
-	it = PyObject_New(dequeiterobject, &dequereviter_type);
-	if (it == NULL)
-		return NULL;
-	it->b = deque->rightblock;
-	it->index = deque->rightindex;
-	Py_INCREF(deque);
-	it->deque = deque;
-	it->len = deque->len;
-	return (PyObject *)it;
-}
-
-static PyObject *
-dequereviter_next(dequeiterobject *it)
-{
-	PyObject *item;
-	if (it->b == it->deque->leftblock && it->index < it->deque->leftindex)
-		return NULL;
-
-	if (it->len != it->deque->len) {
-		it->len = -1; /* Make this state sticky */
-		PyErr_SetString(PyExc_RuntimeError,
-				"deque changed size during iteration");
-		return NULL;
-	}
-
-	item = it->b->data[it->index];
-	it->index--;
-	if (it->index == -1 && it->b->leftlink != NULL) {
-		it->b = it->b->leftlink;
-		it->index = BLOCKLEN - 1;
-	}
-	Py_INCREF(item);
-	return item;
-}
-
-PyTypeObject dequereviter_type = {
-	PyObject_HEAD_INIT(NULL)
-	0,					/* ob_size */
-	"deque_reverse_iterator",		/* tp_name */
-	sizeof(dequeiterobject),		/* tp_basicsize */
-	0,					/* tp_itemsize */
-	/* methods */
-	(destructor)dequeiter_dealloc,		/* tp_dealloc */
-	0,					/* tp_print */
-	0,					/* tp_getattr */
-	0,					/* tp_setattr */
-	0,					/* tp_compare */
-	0,					/* tp_repr */
-	0,					/* tp_as_number */
-	0,					/* tp_as_sequence */
-	0,					/* tp_as_mapping */
-	0,					/* tp_hash */
-	0,					/* tp_call */
-	0,					/* tp_str */
-	PyObject_GenericGetAttr,		/* tp_getattro */
-	0,					/* tp_setattro */
-	0,					/* tp_as_buffer */
-	Py_TPFLAGS_DEFAULT,			/* tp_flags */
-	0,					/* tp_doc */
-	0,					/* tp_traverse */
-	0,					/* tp_clear */
-	0,					/* tp_richcompare */
-	0,					/* tp_weaklistoffset */
-	PyObject_SelfIter,			/* tp_iter */
-	(iternextfunc)dequereviter_next,	/* tp_iternext */
-	0,
-};
-
 /* module level code ********************************************************/
 
 PyDoc_STRVAR(module_doc,
@@ -875,8 +824,5 @@ initcollections(void)
 	if (PyType_Ready(&dequeiter_type) < 0)
 		return;	
 
-	if (PyType_Ready(&dequereviter_type) < 0)
-		return;
-
 	return;
 }