Lines Matching defs:deque
4 /* collections module implementation of a deque() datatype
25 * and the rightmost block has rightlink==NULL). A deque d's first
69 "cannot add more blocks to the deque");
110 /* The deque's size limit is d.maxlen. The limit can be zero or positive.
113 * After an item is added to a deque, we check to see if the size has grown past
131 dequeobject *deque;
135 deque = (dequeobject *)type->tp_alloc(type, 0);
136 if (deque == NULL)
141 Py_DECREF(deque);
146 deque->leftblock = b;
147 deque->rightblock = b;
148 deque->leftindex = CENTER + 1;
149 deque->rightindex = CENTER;
150 deque->len = 0;
151 deque->state = 0;
152 deque->weakreflist = NULL;
153 deque->maxlen = -1;
155 return (PyObject *)deque;
159 deque_pop(dequeobject *deque, PyObject *unused)
164 if (deque->len == 0) {
165 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
168 item = deque->rightblock->data[deque->rightindex];
169 deque->rightindex--;
170 deque->len--;
171 deque->state++;
173 if (deque->rightindex == -1) {
174 if (deque->len == 0) {
175 assert(deque->leftblock == deque->rightblock);
176 assert(deque->leftindex == deque->rightindex+1);
178 deque->leftindex = CENTER + 1;
179 deque->rightindex = CENTER;
181 prevblock = deque->rightblock->leftlink;
182 assert(deque->leftblock != deque->rightblock);
183 freeblock(deque->rightblock);
185 deque->rightblock = prevblock;
186 deque->rightindex = BLOCKLEN - 1;
195 deque_popleft(dequeobject *deque, PyObject *unused)
200 if (deque->len == 0) {
201 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
204 assert(deque->leftblock != NULL);
205 item = deque->leftblock->data[deque->leftindex];
206 deque->leftindex++;
207 deque->len--;
208 deque->state++;
210 if (deque->leftindex == BLOCKLEN) {
211 if (deque->len == 0) {
212 assert(deque->leftblock == deque->rightblock);
213 assert(deque->leftindex == deque->rightindex+1);
215 deque->leftindex = CENTER + 1;
216 deque->rightindex = CENTER;
218 assert(deque->leftblock != deque->rightblock);
219 prevblock = deque->leftblock->rightlink;
220 freeblock(deque->leftblock);
223 deque->leftblock = prevblock;
224 deque->leftindex = 0;
233 deque_append(dequeobject *deque, PyObject *item)
235 deque->state++;
236 if (deque->rightindex == BLOCKLEN-1) {
237 block *b = newblock(deque->rightblock, NULL, deque->len);
240 assert(deque->rightblock->rightlink == NULL);
241 deque->rightblock->rightlink = b;
242 deque->rightblock = b;
243 deque->rightindex = -1;
246 deque->len++;
247 deque->rightindex++;
248 deque->rightblock->data[deque->rightindex] = item;
249 TRIM(deque, deque_popleft);
253 PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
256 deque_appendleft(dequeobject *deque, PyObject *item)
258 deque->state++;
259 if (deque->leftindex == 0) {
260 block *b = newblock(NULL, deque->leftblock, deque->len);
263 assert(deque->leftblock->leftlink == NULL);
264 deque->leftblock->leftlink = b;
265 deque->leftblock = b;
266 deque->leftindex = BLOCKLEN;
269 deque->len++;
270 deque->leftindex--;
271 deque->leftblock->data[deque->leftindex] = item;
272 TRIM(deque, deque_pop);
276 PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
296 deque_extend(dequeobject *deque, PyObject *iterable)
300 /* Handle case where id(deque) == id(iterable) */
301 if ((PyObject *)deque == iterable) {
306 result = deque_extend(deque, s);
315 if (deque->maxlen == 0)
319 deque->state++;
320 if (deque->rightindex == BLOCKLEN-1) {
321 block *b = newblock(deque->rightblock, NULL,
322 deque->len);
328 assert(deque->rightblock->rightlink == NULL);
329 deque->rightblock->rightlink = b;
330 deque->rightblock = b;
331 deque->rightindex = -1;
333 deque->len++;
334 deque->rightindex++;
335 deque->rightblock->data[deque->rightindex] = item;
336 TRIM(deque, deque_popleft);
345 "Extend the right side of the deque with elements from the iterable");
348 deque_extendleft(dequeobject *deque, PyObject *iterable)
352 /* Handle case where id(deque) == id(iterable) */
353 if ((PyObject *)deque == iterable) {
358 result = deque_extendleft(deque, s);
367 if (deque->maxlen == 0)
371 deque->state++;
372 if (deque->leftindex == 0) {
373 block *b = newblock(NULL, deque->leftblock,
374 deque->len);
380 assert(deque->leftblock->leftlink == NULL);
381 deque->leftblock->leftlink = b;
382 deque->leftblock = b;
383 deque->leftindex = BLOCKLEN;
385 deque->len++;
386 deque->leftindex--;
387 deque->leftblock->data[deque->leftindex] = item;
388 TRIM(deque, deque_pop);
397 "Extend the left side of the deque with elements from the iterable");
400 deque_inplace_concat(dequeobject *deque, PyObject *other)
404 result = deque_extend(deque, other);
408 Py_INCREF(deque);
409 return (PyObject *)deque;
413 _deque_rotate(dequeobject *deque, Py_ssize_t n)
415 Py_ssize_t m, len=deque->len, halflen=len>>1;
429 deque->state++;
431 if (deque->leftindex == 0) {
432 block *b = newblock(NULL, deque->leftblock, len);
435 assert(deque->leftblock->leftlink == NULL);
436 deque->leftblock->leftlink = b;
437 deque->leftblock = b;
438 deque->leftindex = BLOCKLEN;
440 assert(deque->leftindex > 0);
443 if (m > deque->rightindex + 1)
444 m = deque->rightindex + 1;
445 if (m > deque->leftindex)
446 m = deque->leftindex;
448 memcpy(&deque->leftblock->data[deque->leftindex - m],
449 &deque->rightblock->data[deque->rightindex + 1 - m],
451 deque->rightindex -= m;
452 deque->leftindex -= m;
455 if (deque->rightindex == -1) {
456 block *prevblock = deque->rightblock->leftlink;
457 assert(deque->rightblock != NULL);
458 assert(deque->leftblock != deque->rightblock);
459 freeblock(deque->rightblock);
461 deque->rightblock = prevblock;
462 deque->rightindex = BLOCKLEN - 1;
466 if (deque->rightindex == BLOCKLEN - 1) {
467 block *b = newblock(deque->rightblock, NULL, len);
470 assert(deque->rightblock->rightlink == NULL);
471 deque->rightblock->rightlink = b;
472 deque->rightblock = b;
473 deque->rightindex = -1;
475 assert (deque->rightindex < BLOCKLEN - 1);
478 if (m > BLOCKLEN - deque->leftindex)
479 m = BLOCKLEN - deque->leftindex;
480 if (m > BLOCKLEN - 1 - deque->rightindex)
481 m = BLOCKLEN - 1 - deque->rightindex;
483 memcpy(&deque->rightblock->data[deque->rightindex + 1],
484 &deque->leftblock->data[deque->leftindex],
486 deque->leftindex += m;
487 deque->rightindex += m;
490 if (deque->leftindex == BLOCKLEN) {
491 block *nextblock = deque->leftblock->rightlink;
492 assert(deque->leftblock != deque->rightblock);
493 freeblock(deque->leftblock);
496 deque->leftblock = nextblock;
497 deque->leftindex = 0;
504 deque_rotate(dequeobject *deque, PyObject *args)
510 if (_deque_rotate(deque, n) == 0)
516 "Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
519 deque_reverse(dequeobject *deque, PyObject *unused)
521 block *leftblock = deque->leftblock;
522 block *rightblock = deque->rightblock;
523 Py_ssize_t leftindex = deque->leftindex;
524 Py_ssize_t rightindex = deque->rightindex;
525 Py_ssize_t n = (deque->len)/2;
563 deque_count(dequeobject *deque, PyObject *v)
565 block *leftblock = deque->leftblock;
566 Py_ssize_t leftindex = deque->leftindex;
567 Py_ssize_t n = deque->len;
571 long start_state = deque->state;
582 if (start_state != deque->state) {
584 "deque mutated during iteration");
604 deque_len(dequeobject *deque)
606 return deque->len;
610 deque_remove(dequeobject *deque, PyObject *value)
612 Py_ssize_t i, n=deque->len;
615 PyObject *item = deque->leftblock->data[deque->leftindex];
618 if (deque->len != n) {
620 "deque mutated during remove().");
624 PyObject *tgt = deque_popleft(deque, NULL);
626 if (_deque_rotate(deque, i))
632 _deque_rotate(deque, i);
635 _deque_rotate(deque, -1);
637 PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");
645 deque_clear(dequeobject *deque)
649 while (deque->len) {
650 item = deque_pop(deque, NULL);
654 assert(deque->leftblock == deque->rightblock &&
655 deque->leftindex - 1 == deque->rightindex &&
656 deque->len == 0);
660 deque_item(dequeobject *deque, Py_ssize_t i)
666 if (i < 0 || i >= deque->len) {
668 "deque index out of range");
673 i = deque->leftindex;
674 b = deque->leftblock;
675 } else if (i == deque->len - 1) {
676 i = deque->rightindex;
677 b = deque->rightblock;
679 i += deque->leftindex;
682 if (index < (deque->len >> 1)) {
683 b = deque->leftblock;
687 n = (deque->leftindex + deque->len - 1) / BLOCKLEN - n;
688 b = deque->rightblock;
706 deque_del_item(dequeobject *deque, Py_ssize_t i)
711 assert (i >= 0 && i < deque->len);
712 if (_deque_rotate(deque, -i))
714 item = deque_popleft(deque, NULL);
715 rv = _deque_rotate(deque, i);
722 deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
726 Py_ssize_t n, len=deque->len, halflen=(len+1)>>1, index=i;
730 "deque index out of range");
734 return deque_del_item(deque, i);
736 i += deque->leftindex;
740 b = deque->leftblock;
744 n = (deque->leftindex + len - 1) / BLOCKLEN - n;
745 b = deque->rightblock;
757 deque_clearmethod(dequeobject *deque)
759 deque_clear(deque);
763 PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
766 deque_dealloc(dequeobject *deque)
768 PyObject_GC_UnTrack(deque);
769 if (deque->weakreflist != NULL)
770 PyObject_ClearWeakRefs((PyObject *) deque);
771 if (deque->leftblock != NULL) {
772 deque_clear(deque);
773 assert(deque->leftblock != NULL);
774 freeblock(deque->leftblock);
776 deque->leftblock = NULL;
777 deque->rightblock = NULL;
778 Py_TYPE(deque)->tp_free(deque);
782 deque_traverse(dequeobject *deque, visitproc visit, void *arg)
787 Py_ssize_t indexlo = deque->leftindex;
789 for (b = deque->leftblock; b != NULL; b = b->rightlink) {
790 const Py_ssize_t indexhi = b == deque->rightblock ?
791 deque->rightindex :
804 deque_copy(PyObject *deque)
806 if (((dequeobject *)deque)->maxlen == -1)
807 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "O", deque, NULL);
809 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",
810 deque, ((dequeobject *)deque)->maxlen, NULL);
813 PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
816 deque_reduce(dequeobject *deque)
820 dict = PyObject_GetAttrString((PyObject *)deque, "__dict__");
823 aslist = PySequence_List((PyObject *)deque);
829 if (deque->maxlen == -1)
830 result = Py_BuildValue("O(O)", Py_TYPE(deque), aslist);
832 result = Py_BuildValue("O(On)", Py_TYPE(deque), aslist, deque->maxlen);
834 if (deque->maxlen == -1)
835 result = Py_BuildValue("O(OO)O", Py_TYPE(deque), aslist, Py_None, dict);
837 result = Py_BuildValue("O(On)O", Py_TYPE(deque), aslist, deque->maxlen, dict);
847 deque_repr(PyObject *deque)
852 i = Py_ReprEnter(deque);
859 aslist = PySequence_List(deque);
861 Py_ReprLeave(deque);
864 if (((dequeobject *)deque)->maxlen != -1)
865 fmt = PyString_FromFormat("deque(%%r, maxlen=%zd)",
866 ((dequeobject *)deque)->maxlen);
868 fmt = PyString_FromString("deque(%r)");
871 Py_ReprLeave(deque);
877 Py_ReprLeave(deque);
882 deque_tp_print(PyObject *deque, FILE *fp, int flags)
889 i = Py_ReprEnter(deque);
899 it = PyObject_GetIter(deque);
904 fputs("deque([", fp);
914 Py_ReprLeave(deque);
919 Py_ReprLeave(deque);
925 if (((dequeobject *)deque)->maxlen == -1)
928 fprintf(fp, "], maxlen=%" PY_FORMAT_SIZE_T "d)", ((dequeobject *)deque)->maxlen);
988 /* We reached the end of one deque or both */
997 case Py_NE: cmp = x != y; break; /* if one deque continues */
1013 deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
1020 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist, &iterable, &maxlenobj))
1031 deque->maxlen = maxlen;
1032 deque_clear(deque);
1034 PyObject *rv = deque_extend(deque, iterable);
1043 deque_sizeof(dequeobject *deque, void *unused)
1049 blocks = (deque->leftindex + deque->len + BLOCKLEN - 1) / BLOCKLEN;
1050 assert(deque->leftindex + deque->len - 1 ==
1051 (blocks - 1) * BLOCKLEN + deque->rightindex);
1060 deque_get_maxlen(dequeobject *deque)
1062 if (deque->maxlen == -1)
1064 return PyInt_FromSsize_t(deque->maxlen);
1069 "maximum size of a deque or None if unbounded"},
1087 /* deque object ********************************************************/
1089 static PyObject *deque_iter(dequeobject *deque);
1090 static PyObject *deque_reviter(dequeobject *deque);
1092 "D.__reversed__() -- return a reverse iterator over the deque");
1129 "deque([iterable[, maxlen]]) --> deque object\n\
1135 "collections.deque", /* tp_name */
1177 /*********************** Deque Iterator **************************/
1183 dequeobject *deque;
1191 deque_iter(dequeobject *deque)
1198 it->b = deque->leftblock;
1199 it->index = deque->leftindex;
1200 Py_INCREF(deque);
1201 it->deque = deque;
1202 it->state = deque->state;
1203 it->counter = deque->len;
1211 Py_VISIT(dio->deque);
1218 Py_XDECREF(dio->deque);
1227 if (it->deque->state != it->state) {
1230 "deque mutated during iteration");
1235 assert (!(it->b == it->deque->rightblock &&
1236 it->index > it->deque->rightindex));
1296 /*********************** Deque Reverse Iterator **************************/
1301 deque_reviter(dequeobject *deque)
1308 it->b = deque->rightblock;
1309 it->index = deque->rightindex;
1310 Py_INCREF(deque);
1311 it->deque = deque;
1312 it->state = deque->state;
1313 it->counter = deque->len;
1325 if (it->deque->state != it->state) {
1328 "deque mutated during iteration");
1331 assert (!(it->b == it->deque->leftblock &&
1332 it->index < it->deque->leftindex));
1675 - deque: ordered collection accessible from endpoints only\n\
1691 PyModule_AddObject(m, "deque", (PyObject *)&deque_type);
