Skip to content

Commit 32ea165

Browse files
rhettingerrhettinger
committed
Issue 23704: Add index(), copy(), and insert() to deques. Register deques as a MutableSequence.
1 parent 0a9e272 commit 32ea165

File tree

6 files changed

+178
-1
lines changed

6 files changed

+178
-1
lines changed

‎Doc/library/collections.rst‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -437,6 +437,13 @@ or subtracting from an empty counter.
437437
Remove all elements from the deque leaving it with length 0.
438438

439439

440+
.. method:: copy()
441+
442+
Create a shallow copy of the deque.
443+
444+
.. versionadded:: 3.5
445+
446+
440447
.. method:: count(x)
441448

442449
Count the number of deque elements equal to *x*.
@@ -457,6 +464,21 @@ or subtracting from an empty counter.
457464
elements in the iterable argument.
458465

459466

467+
.. method:: index(x[, start[, end]])
468+
469+
Return the position of *x* in the deque. Returns the first match
470+
or raises :exc:`ValueError` if not found.
471+
472+
.. versionadded:: 3.5
473+
474+
475+
.. method:: insert(i, x)
476+
477+
Insert *x* into the deque at position *i*.
478+
479+
.. versionadded:: 3.5
480+
481+
460482
.. method:: pop()
461483

462484
Remove and return an element from the right side of the deque. If no

‎Lib/collections/__init__.py‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,8 @@
1616
from itertools import repeat as _repeat, chain as _chain, starmap as _starmap
1717
from reprlib import recursive_repr as _recursive_repr
1818

19+
MutableSequence.register(deque)
20+
1921
################################################################################
2022
### OrderedDict
2123
################################################################################

‎Lib/test/test_collections.py‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@
1313
import sys
1414
from collections import UserDict
1515
from collections import ChainMap
16+
from collections import deque
1617
from collections.abc import Hashable, Iterable, Iterator
1718
from collections.abc import Sized, Container, Callable
1819
from collections.abc import Set, MutableSet
@@ -1014,7 +1015,7 @@ def test_MutableSequence(self):
10141015
for sample in [tuple, str, bytes]:
10151016
self.assertNotIsInstance(sample(), MutableSequence)
10161017
self.assertFalse(issubclass(sample, MutableSequence))
1017-
for sample in [list, bytearray]:
1018+
for sample in [list, bytearray, deque]:
10181019
self.assertIsInstance(sample(), MutableSequence)
10191020
self.assertTrue(issubclass(sample, MutableSequence))
10201021
self.assertFalse(issubclass(str, MutableSequence))

‎Lib/test/test_deque.py‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -231,6 +231,54 @@ def test_getitem(self):
231231
self.assertRaises(IndexError, d.__getitem__, 0)
232232
self.assertRaises(IndexError, d.__getitem__, -1)
233233

234+
def test_index(self):
235+
for n in 1, 2, 30, 40, 200:
236+
237+
d = deque(range(n))
238+
for i in range(n):
239+
self.assertEqual(d.index(i), i)
240+
241+
with self.assertRaises(ValueError):
242+
d.index(n+1)
243+
244+
# Test detection of mutation during iteration
245+
d = deque(range(n))
246+
d[n//2] = MutateCmp(d, False)
247+
with self.assertRaises(RuntimeError):
248+
d.index(n)
249+
250+
# Test detection of comparison exceptions
251+
d = deque(range(n))
252+
d[n//2] = BadCmp()
253+
with self.assertRaises(RuntimeError):
254+
d.index(n)
255+
256+
# Test start and stop arguments behavior matches list.index()
257+
elements = 'ABCDEFGHI'
258+
nonelement = 'Z'
259+
d = deque(elements * 2)
260+
s = list(elements * 2)
261+
for start in range(-5 - len(s)*2, 5 + len(s) * 2):
262+
for stop in range(-5 - len(s)*2, 5 + len(s) * 2):
263+
for element in elements + 'Z':
264+
try:
265+
target = s.index(element, start, stop)
266+
except ValueError:
267+
with self.assertRaises(ValueError):
268+
d.index(element, start, stop)
269+
else:
270+
self.assertEqual(d.index(element, start, stop), target)
271+
272+
def test_insert(self):
273+
# Test to make sure insert behaves like lists
274+
elements = 'ABCDEFGHI'
275+
for i in range(-5 - len(elements)*2, 5 + len(elements) * 2):
276+
d = deque('ABCDEFGHI')
277+
s = list('ABCDEFGHI')
278+
d.insert(i, 'Z')
279+
s.insert(i, 'Z')
280+
self.assertEqual(list(d), s)
281+
234282
def test_setitem(self):
235283
n = 200
236284
d = deque(range(n))
@@ -524,6 +572,15 @@ def test_copy(self):
524572
self.assertNotEqual(id(d), id(e))
525573
self.assertEqual(list(d), list(e))
526574

575+
def test_copy_method(self):
576+
mut = [10]
577+
d = deque([mut])
578+
e = d.copy()
579+
self.assertEqual(list(d), list(e))
580+
mut[0] = 11
581+
self.assertNotEqual(id(d), id(e))
582+
self.assertEqual(list(d), list(e))
583+
527584
def test_reversed(self):
528585
for s in ('abcd', range(2000)):
529586
self.assertEqual(list(reversed(deque(s))), list(reversed(s)))

‎Misc/NEWS‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,10 @@ Library
2727
and socket open until the garbage collector cleans them up. Patch by
2828
Martin Panter.
2929

30+
- Issue #23704: collections.deque() objects now support methods for index(),
31+
insert(), and copy(). This allows deques to be registered as a
32+
MutableSequence and it improves their substitutablity for lists.
33+
3034
- Issue #23715: :func:`signal.sigwaitinfo` and :func:`signal.sigtimedwait` are
3135
now retried when interrupted by a signal not in the *sigset* parameter, if
3236
the signal handler does not raise an exception. signal.sigtimedwait()

‎Modules/_collectionsmodule.c‎

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -762,6 +762,91 @@ deque_len(dequeobject *deque)
762762
return Py_SIZE(deque);
763763
}
764764

765+
static PyObject *
766+
deque_index(dequeobject *deque, PyObject *args)
767+
{
768+
Py_ssize_t i, start=0, stop=Py_SIZE(deque);
769+
PyObject *v, *item;
770+
block *b = deque->leftblock;
771+
Py_ssize_t index = deque->leftindex;
772+
size_t start_state = deque->state;
773+
774+
if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
775+
_PyEval_SliceIndex, &start,
776+
_PyEval_SliceIndex, &stop))
777+
return NULL;
778+
if (start < 0) {
779+
start += Py_SIZE(deque);
780+
if (start < 0)
781+
start = 0;
782+
}
783+
if (stop < 0) {
784+
stop += Py_SIZE(deque);
785+
if (stop < 0)
786+
stop = 0;
787+
}
788+
789+
for (i=0 ; i<stop ; i++) {
790+
if (i >= start) {
791+
int cmp;
792+
CHECK_NOT_END(b);
793+
item = b->data[index];
794+
cmp = PyObject_RichCompareBool(item, v, Py_EQ);
795+
if (cmp > 0)
796+
return PyLong_FromSsize_t(i);
797+
else if (cmp < 0)
798+
return NULL;
799+
if (start_state != deque->state) {
800+
PyErr_SetString(PyExc_RuntimeError,
801+
"deque mutated during iteration");
802+
return NULL;
803+
}
804+
}
805+
index++;
806+
if (index == BLOCKLEN) {
807+
b = b->rightlink;
808+
index = 0;
809+
}
810+
}
811+
PyErr_Format(PyExc_ValueError, "%R is not in deque", v);
812+
return NULL;
813+
}
814+
815+
PyDoc_STRVAR(index_doc,
816+
"D.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
817+
"Raises ValueError if the value is not present.");
818+
819+
static PyObject *
820+
deque_insert(dequeobject *deque, PyObject *args)
821+
{
822+
Py_ssize_t index;
823+
Py_ssize_t n = Py_SIZE(deque);
824+
PyObject *value;
825+
PyObject *rv;
826+
827+
if (!PyArg_ParseTuple(args, "nO:insert", &index, &value))
828+
return NULL;
829+
if (index >= n)
830+
return deque_append(deque, value);
831+
if (index <= -n || index == 0)
832+
return deque_appendleft(deque, value);
833+
if (_deque_rotate(deque, -index))
834+
return NULL;
835+
if (index < 0)
836+
rv = deque_append(deque, value);
837+
else
838+
rv = deque_appendleft(deque, value);
839+
if (rv == NULL)
840+
return NULL;
841+
Py_DECREF(rv);
842+
if (_deque_rotate(deque, index))
843+
return NULL;
844+
Py_RETURN_NONE;
845+
}
846+
847+
PyDoc_STRVAR(insert_doc,
848+
"D.insert(index, object) -- insert object before index");
849+
765850
static PyObject *
766851
deque_remove(dequeobject *deque, PyObject *value)
767852
{
@@ -1208,12 +1293,18 @@ static PyMethodDef deque_methods[] = {
12081293
METH_NOARGS, clear_doc},
12091294
{"__copy__", (PyCFunction)deque_copy,
12101295
METH_NOARGS, copy_doc},
1296+
{"copy", (PyCFunction)deque_copy,
1297+
METH_NOARGS, copy_doc},
12111298
{"count", (PyCFunction)deque_count,
12121299
METH_O, count_doc},
12131300
{"extend", (PyCFunction)deque_extend,
12141301
METH_O, extend_doc},
12151302
{"extendleft", (PyCFunction)deque_extendleft,
12161303
METH_O, extendleft_doc},
1304+
{"index", (PyCFunction)deque_index,
1305+
METH_VARARGS, index_doc},
1306+
{"insert", (PyCFunction)deque_insert,
1307+
METH_VARARGS, insert_doc},
12171308
{"pop", (PyCFunction)deque_pop,
12181309
METH_NOARGS, pop_doc},
12191310
{"popleft", (PyCFunction)deque_popleft,

0 commit comments

Comments
 (0)