Issue 23704: Add index(), copy(), and insert() to deques. Register deques as a MutableSequence.

6 files changed, 178 insertions, 1 deletions

diff --git a/Doc/library/collections.rst b/Doc/library/collections.rst
index c21f456..2b4e4ba 100644
--- a/Doc/library/collections.rst
+++ b/Doc/library/collections.rst
@@ -437,6 +437,13 @@ or subtracting from an empty counter.
         Remove all elements from the deque leaving it with length 0.
 
 
+    .. method:: copy()
+
+        Create a shallow copy of the deque.
+
+        .. versionadded:: 3.5
+
+
     .. method:: count(x)
 
         Count the number of deque elements equal to *x*.
@@ -457,6 +464,21 @@ or subtracting from an empty counter.
         elements in the iterable argument.
 
 
+    .. method:: index(x[, start[, end]])
+
+        Return the position of *x* in the deque.  Returns the first match
+        or raises :exc:`ValueError` if not found.
+
+        .. versionadded:: 3.5
+
+
+    .. method:: insert(i, x)
+
+        Insert *x* into the deque at position *i*.
+
+        .. versionadded:: 3.5
+
+
     .. method:: pop()
 
         Remove and return an element from the right side of the deque. If no
diff --git a/Lib/collections/__init__.py b/Lib/collections/__init__.py
index ce67f0b..9fd3532 100644
--- a/Lib/collections/__init__.py
+++ b/Lib/collections/__init__.py
@@ -16,6 +16,8 @@ from _weakref import proxy as _proxy
 from itertools import repeat as _repeat, chain as _chain, starmap as _starmap
 from reprlib import recursive_repr as _recursive_repr
 
+MutableSequence.register(deque)
+
 ################################################################################
 ### OrderedDict
 ################################################################################
diff --git a/Lib/test/test_collections.py b/Lib/test/test_collections.py
index a94b5da..958fb62 100644
--- a/Lib/test/test_collections.py
+++ b/Lib/test/test_collections.py
@@ -13,6 +13,7 @@ import re
 import sys
 from collections import UserDict
 from collections import ChainMap
+from collections import deque
 from collections.abc import Hashable, Iterable, Iterator
 from collections.abc import Sized, Container, Callable
 from collections.abc import Set, MutableSet
@@ -1014,7 +1015,7 @@ class TestCollectionABCs(ABCTestCase):
         for sample in [tuple, str, bytes]:
             self.assertNotIsInstance(sample(), MutableSequence)
             self.assertFalse(issubclass(sample, MutableSequence))
-        for sample in [list, bytearray]:
+        for sample in [list, bytearray, deque]:
             self.assertIsInstance(sample(), MutableSequence)
             self.assertTrue(issubclass(sample, MutableSequence))
         self.assertFalse(issubclass(str, MutableSequence))
diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py
index 7d69448..07e5ef9 100644
--- a/Lib/test/test_deque.py
+++ b/Lib/test/test_deque.py
@@ -231,6 +231,54 @@ class TestBasic(unittest.TestCase):
         self.assertRaises(IndexError, d.__getitem__, 0)
         self.assertRaises(IndexError, d.__getitem__, -1)
 
+    def test_index(self):
+        for n in 1, 2, 30, 40, 200:
+
+            d = deque(range(n))
+            for i in range(n):
+                self.assertEqual(d.index(i), i)
+
+            with self.assertRaises(ValueError):
+                d.index(n+1)
+
+            # Test detection of mutation during iteration
+            d = deque(range(n))
+            d[n//2] = MutateCmp(d, False)
+            with self.assertRaises(RuntimeError):
+                d.index(n)
+
+            # Test detection of comparison exceptions
+            d = deque(range(n))
+            d[n//2] = BadCmp()
+            with self.assertRaises(RuntimeError):
+                d.index(n)
+
+        # Test start and stop arguments behavior matches list.index()
+        elements = 'ABCDEFGHI'
+        nonelement = 'Z'
+        d = deque(elements * 2)
+        s = list(elements * 2)
+        for start in range(-5 - len(s)*2, 5 + len(s) * 2):
+            for stop in range(-5 - len(s)*2, 5 + len(s) * 2):
+                for element in elements + 'Z':
+                    try:
+                        target = s.index(element, start, stop)
+                    except ValueError:
+                        with self.assertRaises(ValueError):
+                            d.index(element, start, stop)
+                    else:
+                        self.assertEqual(d.index(element, start, stop), target)
+
+    def test_insert(self):
+        # Test to make sure insert behaves like lists
+        elements = 'ABCDEFGHI'
+        for i in range(-5 - len(elements)*2, 5 + len(elements) * 2):
+            d = deque('ABCDEFGHI')
+            s = list('ABCDEFGHI')
+            d.insert(i, 'Z')
+            s.insert(i, 'Z')
+            self.assertEqual(list(d), s)
+
     def test_setitem(self):
         n = 200
         d = deque(range(n))
@@ -524,6 +572,15 @@ class TestBasic(unittest.TestCase):
         self.assertNotEqual(id(d), id(e))
         self.assertEqual(list(d), list(e))
 
+    def test_copy_method(self):
+        mut = [10]
+        d = deque([mut])
+        e = d.copy()
+        self.assertEqual(list(d), list(e))
+        mut[0] = 11
+        self.assertNotEqual(id(d), id(e))
+        self.assertEqual(list(d), list(e))
+
     def test_reversed(self):
         for s in ('abcd', range(2000)):
             self.assertEqual(list(reversed(deque(s))), list(reversed(s)))
diff --git a/Misc/NEWS b/Misc/NEWS
index 5053fc5..cc8e20a 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -27,6 +27,10 @@ Library
   and socket open until the garbage collector cleans them up.  Patch by
   Martin Panter.
 
+- Issue #23704: collections.deque() objects now support methods for index(),
+  insert(), and copy().  This allows deques to be registered as a
+  MutableSequence and it improves their substitutablity for lists.
+
 - Issue #23715: :func:`signal.sigwaitinfo` and :func:`signal.sigtimedwait` are
   now retried when interrupted by a signal not in the *sigset* parameter, if
   the signal handler does not raise an exception. signal.sigtimedwait()
diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c
index 26a0c8f..223ad53 100644
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -763,6 +763,91 @@ deque_len(dequeobject *deque)
 }
 
 static PyObject *
+deque_index(dequeobject *deque, PyObject *args)
+{
+    Py_ssize_t i, start=0, stop=Py_SIZE(deque);
+    PyObject *v, *item;
+    block *b = deque->leftblock;
+    Py_ssize_t index = deque->leftindex;
+    size_t start_state = deque->state;
+
+    if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
+                                _PyEval_SliceIndex, &start,
+                                _PyEval_SliceIndex, &stop))
+        return NULL;
+    if (start < 0) {
+        start += Py_SIZE(deque);
+        if (start < 0)
+            start = 0;
+    }
+    if (stop < 0) {
+        stop += Py_SIZE(deque);
+        if (stop < 0)
+            stop = 0;
+    }
+
+    for (i=0 ; i<stop ; i++) {
+        if (i >= start) {
+            int cmp;
+            CHECK_NOT_END(b);
+            item = b->data[index];
+            cmp = PyObject_RichCompareBool(item, v, Py_EQ);
+            if (cmp > 0)
+                return PyLong_FromSsize_t(i);
+            else if (cmp < 0)
+                return NULL;
+            if (start_state != deque->state) {
+                PyErr_SetString(PyExc_RuntimeError,
+                                "deque mutated during iteration");
+                return NULL;
+            }
+        }
+        index++;
+        if (index == BLOCKLEN) {
+            b = b->rightlink;
+            index = 0;
+        }
+    }
+    PyErr_Format(PyExc_ValueError, "%R is not in deque", v);
+    return NULL;
+}
+
+PyDoc_STRVAR(index_doc,
+"D.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
+"Raises ValueError if the value is not present.");
+
+static PyObject *
+deque_insert(dequeobject *deque, PyObject *args)
+{
+    Py_ssize_t index;
+    Py_ssize_t n = Py_SIZE(deque);
+    PyObject *value;
+    PyObject *rv;
+
+    if (!PyArg_ParseTuple(args, "nO:insert", &index, &value))
+        return NULL;
+    if (index >= n)
+        return deque_append(deque, value);
+    if (index <= -n || index == 0)
+        return deque_appendleft(deque, value);
+    if (_deque_rotate(deque, -index))
+        return NULL;
+    if (index < 0)
+        rv = deque_append(deque, value);
+    else
+        rv = deque_appendleft(deque, value);
+    if (rv == NULL)
+        return NULL;
+    Py_DECREF(rv);
+    if (_deque_rotate(deque, index))
+        return NULL;
+    Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(insert_doc,
+"D.insert(index, object) -- insert object before index");
+
+static PyObject *
 deque_remove(dequeobject *deque, PyObject *value)
 {
     Py_ssize_t i, n=Py_SIZE(deque);
@@ -1208,12 +1293,18 @@ static PyMethodDef deque_methods[] = {
         METH_NOARGS,             clear_doc},
     {"__copy__",                (PyCFunction)deque_copy,
         METH_NOARGS,             copy_doc},
+    {"copy",                    (PyCFunction)deque_copy,
+        METH_NOARGS,             copy_doc},
     {"count",                   (PyCFunction)deque_count,
         METH_O,                         count_doc},
     {"extend",                  (PyCFunction)deque_extend,
         METH_O,                  extend_doc},
     {"extendleft",              (PyCFunction)deque_extendleft,
         METH_O,                  extendleft_doc},
+    {"index",                   (PyCFunction)deque_index,
+        METH_VARARGS,            index_doc},
+    {"insert",                  (PyCFunction)deque_insert,
+        METH_VARARGS,            insert_doc},
     {"pop",                     (PyCFunction)deque_pop,
         METH_NOARGS,             pop_doc},
     {"popleft",                 (PyCFunction)deque_popleft,