diff options
| -rw-r--r-- | Doc/lib/libcollections.tex | 21 | ||||
| -rw-r--r-- | Lib/asynchat.py | 2 | ||||
| -rw-r--r-- | Lib/test/test_deque.py | 43 | ||||
| -rw-r--r-- | Modules/collectionsmodule.c | 192 |
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; } |