3 #include "structmember.h"
5 /* Itertools module written and maintained
6 by Raymond D. Hettinger <python@rcn.com>
7 Copyright (c) 2003 Python Software Foundation.
12 /* groupby object ***********************************************************/
23 static PyTypeObject groupby_type
;
24 static PyObject
*_grouper_create(groupbyobject
*, PyObject
*);
27 groupby_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
29 static char *kwargs
[] = {"iterable", "key", NULL
};
31 PyObject
*it
, *keyfunc
= Py_None
;
33 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "O|O:groupby", kwargs
,
37 gbo
= (groupbyobject
*)type
->tp_alloc(type
, 0);
42 gbo
->currvalue
= NULL
;
43 gbo
->keyfunc
= keyfunc
;
45 gbo
->it
= PyObject_GetIter(it
);
46 if (gbo
->it
== NULL
) {
50 return (PyObject
*)gbo
;
54 groupby_dealloc(groupbyobject
*gbo
)
56 PyObject_GC_UnTrack(gbo
);
58 Py_XDECREF(gbo
->keyfunc
);
59 Py_XDECREF(gbo
->tgtkey
);
60 Py_XDECREF(gbo
->currkey
);
61 Py_XDECREF(gbo
->currvalue
);
62 Py_TYPE(gbo
)->tp_free(gbo
);
66 groupby_traverse(groupbyobject
*gbo
, visitproc visit
, void *arg
)
69 Py_VISIT(gbo
->keyfunc
);
70 Py_VISIT(gbo
->tgtkey
);
71 Py_VISIT(gbo
->currkey
);
72 Py_VISIT(gbo
->currvalue
);
77 groupby_next(groupbyobject
*gbo
)
79 PyObject
*newvalue
, *newkey
, *r
, *grouper
, *tmp
;
81 /* skip to next iteration group */
83 if (gbo
->currkey
== NULL
)
85 else if (gbo
->tgtkey
== NULL
)
90 rcmp
= PyObject_RichCompareBool(gbo
->tgtkey
,
98 newvalue
= PyIter_Next(gbo
->it
);
102 if (gbo
->keyfunc
== Py_None
) {
106 newkey
= PyObject_CallFunctionObjArgs(gbo
->keyfunc
,
108 if (newkey
== NULL
) {
115 gbo
->currkey
= newkey
;
118 tmp
= gbo
->currvalue
;
119 gbo
->currvalue
= newvalue
;
123 Py_INCREF(gbo
->currkey
);
125 gbo
->tgtkey
= gbo
->currkey
;
128 grouper
= _grouper_create(gbo
, gbo
->tgtkey
);
132 r
= PyTuple_Pack(2, gbo
->currkey
, grouper
);
137 PyDoc_STRVAR(groupby_doc
,
138 "groupby(iterable[, keyfunc]) -> create an iterator which returns\n\
139 (key, sub-iterator) grouped by each value of key(value).\n");
141 static PyTypeObject groupby_type
= {
142 PyVarObject_HEAD_INIT(NULL
, 0)
143 "itertools.groupby", /* tp_name */
144 sizeof(groupbyobject
), /* tp_basicsize */
147 (destructor
)groupby_dealloc
, /* tp_dealloc */
153 0, /* tp_as_number */
154 0, /* tp_as_sequence */
155 0, /* tp_as_mapping */
159 PyObject_GenericGetAttr
, /* tp_getattro */
161 0, /* tp_as_buffer */
162 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
163 Py_TPFLAGS_BASETYPE
, /* tp_flags */
164 groupby_doc
, /* tp_doc */
165 (traverseproc
)groupby_traverse
, /* tp_traverse */
167 0, /* tp_richcompare */
168 0, /* tp_weaklistoffset */
169 PyObject_SelfIter
, /* tp_iter */
170 (iternextfunc
)groupby_next
, /* tp_iternext */
176 0, /* tp_descr_get */
177 0, /* tp_descr_set */
178 0, /* tp_dictoffset */
181 groupby_new
, /* tp_new */
182 PyObject_GC_Del
, /* tp_free */
186 /* _grouper object (internal) ************************************************/
194 static PyTypeObject _grouper_type
;
197 _grouper_create(groupbyobject
*parent
, PyObject
*tgtkey
)
201 igo
= PyObject_GC_New(_grouperobject
, &_grouper_type
);
204 igo
->parent
= (PyObject
*)parent
;
206 igo
->tgtkey
= tgtkey
;
209 PyObject_GC_Track(igo
);
210 return (PyObject
*)igo
;
214 _grouper_dealloc(_grouperobject
*igo
)
216 PyObject_GC_UnTrack(igo
);
217 Py_DECREF(igo
->parent
);
218 Py_DECREF(igo
->tgtkey
);
219 PyObject_GC_Del(igo
);
223 _grouper_traverse(_grouperobject
*igo
, visitproc visit
, void *arg
)
225 Py_VISIT(igo
->parent
);
226 Py_VISIT(igo
->tgtkey
);
231 _grouper_next(_grouperobject
*igo
)
233 groupbyobject
*gbo
= (groupbyobject
*)igo
->parent
;
234 PyObject
*newvalue
, *newkey
, *r
;
237 if (gbo
->currvalue
== NULL
) {
238 newvalue
= PyIter_Next(gbo
->it
);
239 if (newvalue
== NULL
)
242 if (gbo
->keyfunc
== Py_None
) {
246 newkey
= PyObject_CallFunctionObjArgs(gbo
->keyfunc
,
248 if (newkey
== NULL
) {
254 assert(gbo
->currkey
== NULL
);
255 gbo
->currkey
= newkey
;
256 gbo
->currvalue
= newvalue
;
259 assert(gbo
->currkey
!= NULL
);
260 rcmp
= PyObject_RichCompareBool(igo
->tgtkey
, gbo
->currkey
, Py_EQ
);
262 /* got any error or current group is end */
266 gbo
->currvalue
= NULL
;
267 Py_CLEAR(gbo
->currkey
);
272 static PyTypeObject _grouper_type
= {
273 PyVarObject_HEAD_INIT(NULL
, 0)
274 "itertools._grouper", /* tp_name */
275 sizeof(_grouperobject
), /* tp_basicsize */
278 (destructor
)_grouper_dealloc
, /* tp_dealloc */
284 0, /* tp_as_number */
285 0, /* tp_as_sequence */
286 0, /* tp_as_mapping */
290 PyObject_GenericGetAttr
, /* tp_getattro */
292 0, /* tp_as_buffer */
293 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
, /* tp_flags */
295 (traverseproc
)_grouper_traverse
,/* tp_traverse */
297 0, /* tp_richcompare */
298 0, /* tp_weaklistoffset */
299 PyObject_SelfIter
, /* tp_iter */
300 (iternextfunc
)_grouper_next
, /* tp_iternext */
306 0, /* tp_descr_get */
307 0, /* tp_descr_set */
308 0, /* tp_dictoffset */
312 PyObject_GC_Del
, /* tp_free */
317 /* tee object and with supporting function and objects ***************/
319 /* The teedataobject pre-allocates space for LINKCELLS number of objects.
320 To help the object fit neatly inside cache lines (space for 16 to 32
321 pointers), the value should be a multiple of 16 minus space for
322 the other structure members including PyHEAD overhead. The larger the
323 value, the less memory overhead per object and the less time spent
324 allocating/deallocating new links. The smaller the number, the less
325 wasted space and the more rapid freeing of older data.
334 PyObject
*(values
[LINKCELLS
]);
339 teedataobject
*dataobj
;
341 PyObject
*weakreflist
;
344 static PyTypeObject teedataobject_type
;
347 teedataobject_new(PyObject
*it
)
351 tdo
= PyObject_GC_New(teedataobject
, &teedataobject_type
);
356 tdo
->nextlink
= NULL
;
359 PyObject_GC_Track(tdo
);
360 return (PyObject
*)tdo
;
364 teedataobject_jumplink(teedataobject
*tdo
)
366 if (tdo
->nextlink
== NULL
)
367 tdo
->nextlink
= teedataobject_new(tdo
->it
);
368 Py_XINCREF(tdo
->nextlink
);
369 return tdo
->nextlink
;
373 teedataobject_getitem(teedataobject
*tdo
, int i
)
377 assert(i
< LINKCELLS
);
378 if (i
< tdo
->numread
)
379 value
= tdo
->values
[i
];
381 /* this is the lead iterator, so fetch more data */
382 assert(i
== tdo
->numread
);
383 value
= PyIter_Next(tdo
->it
);
387 tdo
->values
[i
] = value
;
394 teedataobject_traverse(teedataobject
*tdo
, visitproc visit
, void * arg
)
398 for (i
= 0; i
< tdo
->numread
; i
++)
399 Py_VISIT(tdo
->values
[i
]);
400 Py_VISIT(tdo
->nextlink
);
405 teedataobject_clear(teedataobject
*tdo
)
409 for (i
=0 ; i
<tdo
->numread
; i
++)
410 Py_CLEAR(tdo
->values
[i
]);
411 Py_CLEAR(tdo
->nextlink
);
416 teedataobject_dealloc(teedataobject
*tdo
)
418 PyObject_GC_UnTrack(tdo
);
419 teedataobject_clear(tdo
);
420 PyObject_GC_Del(tdo
);
423 PyDoc_STRVAR(teedataobject_doc
, "Data container common to multiple tee objects.");
425 static PyTypeObject teedataobject_type
= {
426 PyVarObject_HEAD_INIT(0, 0) /* Must fill in type value later */
427 "itertools.tee_dataobject", /* tp_name */
428 sizeof(teedataobject
), /* tp_basicsize */
431 (destructor
)teedataobject_dealloc
, /* tp_dealloc */
437 0, /* tp_as_number */
438 0, /* tp_as_sequence */
439 0, /* tp_as_mapping */
443 PyObject_GenericGetAttr
, /* tp_getattro */
445 0, /* tp_as_buffer */
446 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
, /* tp_flags */
447 teedataobject_doc
, /* tp_doc */
448 (traverseproc
)teedataobject_traverse
, /* tp_traverse */
449 (inquiry
)teedataobject_clear
, /* tp_clear */
450 0, /* tp_richcompare */
451 0, /* tp_weaklistoffset */
459 0, /* tp_descr_get */
460 0, /* tp_descr_set */
461 0, /* tp_dictoffset */
465 PyObject_GC_Del
, /* tp_free */
469 static PyTypeObject tee_type
;
472 tee_next(teeobject
*to
)
474 PyObject
*value
, *link
;
476 if (to
->index
>= LINKCELLS
) {
477 link
= teedataobject_jumplink(to
->dataobj
);
478 Py_DECREF(to
->dataobj
);
479 to
->dataobj
= (teedataobject
*)link
;
482 value
= teedataobject_getitem(to
->dataobj
, to
->index
);
490 tee_traverse(teeobject
*to
, visitproc visit
, void *arg
)
492 Py_VISIT((PyObject
*)to
->dataobj
);
497 tee_copy(teeobject
*to
)
501 newto
= PyObject_GC_New(teeobject
, &tee_type
);
504 Py_INCREF(to
->dataobj
);
505 newto
->dataobj
= to
->dataobj
;
506 newto
->index
= to
->index
;
507 newto
->weakreflist
= NULL
;
508 PyObject_GC_Track(newto
);
509 return (PyObject
*)newto
;
512 PyDoc_STRVAR(teecopy_doc
, "Returns an independent iterator.");
515 tee_fromiterable(PyObject
*iterable
)
520 it
= PyObject_GetIter(iterable
);
523 if (PyObject_TypeCheck(it
, &tee_type
)) {
524 to
= (teeobject
*)tee_copy((teeobject
*)it
);
528 to
= PyObject_GC_New(teeobject
, &tee_type
);
531 to
->dataobj
= (teedataobject
*)teedataobject_new(it
);
539 to
->weakreflist
= NULL
;
540 PyObject_GC_Track(to
);
543 return (PyObject
*)to
;
547 tee_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kw
)
551 if (!PyArg_UnpackTuple(args
, "tee", 1, 1, &iterable
))
553 return tee_fromiterable(iterable
);
557 tee_clear(teeobject
*to
)
559 if (to
->weakreflist
!= NULL
)
560 PyObject_ClearWeakRefs((PyObject
*) to
);
561 Py_CLEAR(to
->dataobj
);
566 tee_dealloc(teeobject
*to
)
568 PyObject_GC_UnTrack(to
);
573 PyDoc_STRVAR(teeobject_doc
,
574 "Iterator wrapped to make it copyable");
576 static PyMethodDef tee_methods
[] = {
577 {"__copy__", (PyCFunction
)tee_copy
, METH_NOARGS
, teecopy_doc
},
578 {NULL
, NULL
} /* sentinel */
581 static PyTypeObject tee_type
= {
582 PyVarObject_HEAD_INIT(NULL
, 0)
583 "itertools.tee", /* tp_name */
584 sizeof(teeobject
), /* tp_basicsize */
587 (destructor
)tee_dealloc
, /* tp_dealloc */
593 0, /* tp_as_number */
594 0, /* tp_as_sequence */
595 0, /* tp_as_mapping */
601 0, /* tp_as_buffer */
602 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
, /* tp_flags */
603 teeobject_doc
, /* tp_doc */
604 (traverseproc
)tee_traverse
, /* tp_traverse */
605 (inquiry
)tee_clear
, /* tp_clear */
606 0, /* tp_richcompare */
607 offsetof(teeobject
, weakreflist
), /* tp_weaklistoffset */
608 PyObject_SelfIter
, /* tp_iter */
609 (iternextfunc
)tee_next
, /* tp_iternext */
610 tee_methods
, /* tp_methods */
615 0, /* tp_descr_get */
616 0, /* tp_descr_set */
617 0, /* tp_dictoffset */
620 tee_new
, /* tp_new */
621 PyObject_GC_Del
, /* tp_free */
625 tee(PyObject
*self
, PyObject
*args
)
628 PyObject
*it
, *iterable
, *copyable
, *result
;
630 if (!PyArg_ParseTuple(args
, "O|n", &iterable
, &n
))
633 PyErr_SetString(PyExc_ValueError
, "n must be >= 0");
636 result
= PyTuple_New(n
);
641 it
= PyObject_GetIter(iterable
);
646 if (!PyObject_HasAttrString(it
, "__copy__")) {
647 copyable
= tee_fromiterable(it
);
649 if (copyable
== NULL
) {
655 PyTuple_SET_ITEM(result
, 0, copyable
);
656 for (i
=1 ; i
<n
; i
++) {
657 copyable
= PyObject_CallMethod(copyable
, "__copy__", NULL
);
658 if (copyable
== NULL
) {
662 PyTuple_SET_ITEM(result
, i
, copyable
);
667 PyDoc_STRVAR(tee_doc
,
668 "tee(iterable, n=2) --> tuple of n independent iterators.");
671 /* cycle object **********************************************************/
680 static PyTypeObject cycle_type
;
683 cycle_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
690 if (type
== &cycle_type
&& !_PyArg_NoKeywords("cycle()", kwds
))
693 if (!PyArg_UnpackTuple(args
, "cycle", 1, 1, &iterable
))
697 it
= PyObject_GetIter(iterable
);
701 saved
= PyList_New(0);
707 /* create cycleobject structure */
708 lz
= (cycleobject
*)type
->tp_alloc(type
, 0);
718 return (PyObject
*)lz
;
722 cycle_dealloc(cycleobject
*lz
)
724 PyObject_GC_UnTrack(lz
);
725 Py_XDECREF(lz
->saved
);
727 Py_TYPE(lz
)->tp_free(lz
);
731 cycle_traverse(cycleobject
*lz
, visitproc visit
, void *arg
)
739 cycle_next(cycleobject
*lz
)
746 item
= PyIter_Next(lz
->it
);
748 if (!lz
->firstpass
&& PyList_Append(lz
->saved
, item
)) {
754 if (PyErr_Occurred()) {
755 if (PyErr_ExceptionMatches(PyExc_StopIteration
))
760 if (PyList_Size(lz
->saved
) == 0)
762 it
= PyObject_GetIter(lz
->saved
);
772 PyDoc_STRVAR(cycle_doc
,
773 "cycle(iterable) --> cycle object\n\
775 Return elements from the iterable until it is exhausted.\n\
776 Then repeat the sequence indefinitely.");
778 static PyTypeObject cycle_type
= {
779 PyVarObject_HEAD_INIT(NULL
, 0)
780 "itertools.cycle", /* tp_name */
781 sizeof(cycleobject
), /* tp_basicsize */
784 (destructor
)cycle_dealloc
, /* tp_dealloc */
790 0, /* tp_as_number */
791 0, /* tp_as_sequence */
792 0, /* tp_as_mapping */
796 PyObject_GenericGetAttr
, /* tp_getattro */
798 0, /* tp_as_buffer */
799 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
800 Py_TPFLAGS_BASETYPE
, /* tp_flags */
801 cycle_doc
, /* tp_doc */
802 (traverseproc
)cycle_traverse
, /* tp_traverse */
804 0, /* tp_richcompare */
805 0, /* tp_weaklistoffset */
806 PyObject_SelfIter
, /* tp_iter */
807 (iternextfunc
)cycle_next
, /* tp_iternext */
813 0, /* tp_descr_get */
814 0, /* tp_descr_set */
815 0, /* tp_dictoffset */
818 cycle_new
, /* tp_new */
819 PyObject_GC_Del
, /* tp_free */
823 /* dropwhile object **********************************************************/
832 static PyTypeObject dropwhile_type
;
835 dropwhile_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
837 PyObject
*func
, *seq
;
841 if (type
== &dropwhile_type
&& !_PyArg_NoKeywords("dropwhile()", kwds
))
844 if (!PyArg_UnpackTuple(args
, "dropwhile", 2, 2, &func
, &seq
))
848 it
= PyObject_GetIter(seq
);
852 /* create dropwhileobject structure */
853 lz
= (dropwhileobject
*)type
->tp_alloc(type
, 0);
863 return (PyObject
*)lz
;
867 dropwhile_dealloc(dropwhileobject
*lz
)
869 PyObject_GC_UnTrack(lz
);
870 Py_XDECREF(lz
->func
);
872 Py_TYPE(lz
)->tp_free(lz
);
876 dropwhile_traverse(dropwhileobject
*lz
, visitproc visit
, void *arg
)
884 dropwhile_next(dropwhileobject
*lz
)
886 PyObject
*item
, *good
;
887 PyObject
*it
= lz
->it
;
889 PyObject
*(*iternext
)(PyObject
*);
891 iternext
= *Py_TYPE(it
)->tp_iternext
;
899 good
= PyObject_CallFunctionObjArgs(lz
->func
, item
, NULL
);
904 ok
= PyObject_IsTrue(good
);
914 PyDoc_STRVAR(dropwhile_doc
,
915 "dropwhile(predicate, iterable) --> dropwhile object\n\
917 Drop items from the iterable while predicate(item) is true.\n\
918 Afterwards, return every element until the iterable is exhausted.");
920 static PyTypeObject dropwhile_type
= {
921 PyVarObject_HEAD_INIT(NULL
, 0)
922 "itertools.dropwhile", /* tp_name */
923 sizeof(dropwhileobject
), /* tp_basicsize */
926 (destructor
)dropwhile_dealloc
, /* tp_dealloc */
932 0, /* tp_as_number */
933 0, /* tp_as_sequence */
934 0, /* tp_as_mapping */
938 PyObject_GenericGetAttr
, /* tp_getattro */
940 0, /* tp_as_buffer */
941 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
942 Py_TPFLAGS_BASETYPE
, /* tp_flags */
943 dropwhile_doc
, /* tp_doc */
944 (traverseproc
)dropwhile_traverse
, /* tp_traverse */
946 0, /* tp_richcompare */
947 0, /* tp_weaklistoffset */
948 PyObject_SelfIter
, /* tp_iter */
949 (iternextfunc
)dropwhile_next
, /* tp_iternext */
955 0, /* tp_descr_get */
956 0, /* tp_descr_set */
957 0, /* tp_dictoffset */
960 dropwhile_new
, /* tp_new */
961 PyObject_GC_Del
, /* tp_free */
965 /* takewhile object **********************************************************/
974 static PyTypeObject takewhile_type
;
977 takewhile_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
979 PyObject
*func
, *seq
;
983 if (type
== &takewhile_type
&& !_PyArg_NoKeywords("takewhile()", kwds
))
986 if (!PyArg_UnpackTuple(args
, "takewhile", 2, 2, &func
, &seq
))
990 it
= PyObject_GetIter(seq
);
994 /* create takewhileobject structure */
995 lz
= (takewhileobject
*)type
->tp_alloc(type
, 0);
1005 return (PyObject
*)lz
;
1009 takewhile_dealloc(takewhileobject
*lz
)
1011 PyObject_GC_UnTrack(lz
);
1012 Py_XDECREF(lz
->func
);
1014 Py_TYPE(lz
)->tp_free(lz
);
1018 takewhile_traverse(takewhileobject
*lz
, visitproc visit
, void *arg
)
1026 takewhile_next(takewhileobject
*lz
)
1028 PyObject
*item
, *good
;
1029 PyObject
*it
= lz
->it
;
1035 item
= (*Py_TYPE(it
)->tp_iternext
)(it
);
1039 good
= PyObject_CallFunctionObjArgs(lz
->func
, item
, NULL
);
1044 ok
= PyObject_IsTrue(good
);
1053 PyDoc_STRVAR(takewhile_doc
,
1054 "takewhile(predicate, iterable) --> takewhile object\n\
1056 Return successive entries from an iterable as long as the \n\
1057 predicate evaluates to true for each entry.");
1059 static PyTypeObject takewhile_type
= {
1060 PyVarObject_HEAD_INIT(NULL
, 0)
1061 "itertools.takewhile", /* tp_name */
1062 sizeof(takewhileobject
), /* tp_basicsize */
1063 0, /* tp_itemsize */
1065 (destructor
)takewhile_dealloc
, /* tp_dealloc */
1069 0, /* tp_reserved */
1071 0, /* tp_as_number */
1072 0, /* tp_as_sequence */
1073 0, /* tp_as_mapping */
1077 PyObject_GenericGetAttr
, /* tp_getattro */
1078 0, /* tp_setattro */
1079 0, /* tp_as_buffer */
1080 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1081 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1082 takewhile_doc
, /* tp_doc */
1083 (traverseproc
)takewhile_traverse
, /* tp_traverse */
1085 0, /* tp_richcompare */
1086 0, /* tp_weaklistoffset */
1087 PyObject_SelfIter
, /* tp_iter */
1088 (iternextfunc
)takewhile_next
, /* tp_iternext */
1094 0, /* tp_descr_get */
1095 0, /* tp_descr_set */
1096 0, /* tp_dictoffset */
1099 takewhile_new
, /* tp_new */
1100 PyObject_GC_Del
, /* tp_free */
1104 /* islice object ************************************************************/
1115 static PyTypeObject islice_type
;
1118 islice_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1121 Py_ssize_t start
=0, stop
=-1, step
=1;
1122 PyObject
*it
, *a1
=NULL
, *a2
=NULL
, *a3
=NULL
;
1126 if (type
== &islice_type
&& !_PyArg_NoKeywords("islice()", kwds
))
1129 if (!PyArg_UnpackTuple(args
, "islice", 2, 4, &seq
, &a1
, &a2
, &a3
))
1132 numargs
= PyTuple_Size(args
);
1134 if (a1
!= Py_None
) {
1135 stop
= PyLong_AsSsize_t(a1
);
1137 if (PyErr_Occurred())
1139 PyErr_SetString(PyExc_ValueError
,
1140 "Stop argument for islice() must be None or an integer: 0 <= x <= sys.maxsize.");
1146 start
= PyLong_AsSsize_t(a1
);
1147 if (start
== -1 && PyErr_Occurred())
1149 if (a2
!= Py_None
) {
1150 stop
= PyLong_AsSsize_t(a2
);
1152 if (PyErr_Occurred())
1154 PyErr_SetString(PyExc_ValueError
,
1155 "Stop argument for islice() must be None or an integer: 0 <= x <= sys.maxsize.");
1160 if (start
<0 || stop
<-1) {
1161 PyErr_SetString(PyExc_ValueError
,
1162 "Indices for islice() must be None or an integer: 0 <= x <= sys.maxsize.");
1168 step
= PyLong_AsSsize_t(a3
);
1169 if (step
== -1 && PyErr_Occurred())
1173 PyErr_SetString(PyExc_ValueError
,
1174 "Step for islice() must be a positive integer or None.");
1179 it
= PyObject_GetIter(seq
);
1183 /* create isliceobject structure */
1184 lz
= (isliceobject
*)type
->tp_alloc(type
, 0);
1195 return (PyObject
*)lz
;
1199 islice_dealloc(isliceobject
*lz
)
1201 PyObject_GC_UnTrack(lz
);
1203 Py_TYPE(lz
)->tp_free(lz
);
1207 islice_traverse(isliceobject
*lz
, visitproc visit
, void *arg
)
1214 islice_next(isliceobject
*lz
)
1217 PyObject
*it
= lz
->it
;
1219 PyObject
*(*iternext
)(PyObject
*);
1221 iternext
= *Py_TYPE(it
)->tp_iternext
;
1222 while (lz
->cnt
< lz
->next
) {
1223 item
= iternext(it
);
1229 if (lz
->stop
!= -1 && lz
->cnt
>= lz
->stop
)
1231 item
= iternext(it
);
1236 lz
->next
+= lz
->step
;
1237 if (lz
->next
< oldnext
) /* Check for overflow */
1238 lz
->next
= lz
->stop
;
1242 PyDoc_STRVAR(islice_doc
,
1243 "islice(iterable, [start,] stop [, step]) --> islice object\n\
1245 Return an iterator whose next() method returns selected values from an\n\
1246 iterable. If start is specified, will skip all preceding elements;\n\
1247 otherwise, start defaults to zero. Step defaults to one. If\n\
1248 specified as another value, step determines how many values are \n\
1249 skipped between successive calls. Works like a slice() on a list\n\
1250 but returns an iterator.");
1252 static PyTypeObject islice_type
= {
1253 PyVarObject_HEAD_INIT(NULL
, 0)
1254 "itertools.islice", /* tp_name */
1255 sizeof(isliceobject
), /* tp_basicsize */
1256 0, /* tp_itemsize */
1258 (destructor
)islice_dealloc
, /* tp_dealloc */
1262 0, /* tp_reserved */
1264 0, /* tp_as_number */
1265 0, /* tp_as_sequence */
1266 0, /* tp_as_mapping */
1270 PyObject_GenericGetAttr
, /* tp_getattro */
1271 0, /* tp_setattro */
1272 0, /* tp_as_buffer */
1273 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1274 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1275 islice_doc
, /* tp_doc */
1276 (traverseproc
)islice_traverse
, /* tp_traverse */
1278 0, /* tp_richcompare */
1279 0, /* tp_weaklistoffset */
1280 PyObject_SelfIter
, /* tp_iter */
1281 (iternextfunc
)islice_next
, /* tp_iternext */
1287 0, /* tp_descr_get */
1288 0, /* tp_descr_set */
1289 0, /* tp_dictoffset */
1292 islice_new
, /* tp_new */
1293 PyObject_GC_Del
, /* tp_free */
1297 /* starmap object ************************************************************/
1305 static PyTypeObject starmap_type
;
1308 starmap_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1310 PyObject
*func
, *seq
;
1314 if (type
== &starmap_type
&& !_PyArg_NoKeywords("starmap()", kwds
))
1317 if (!PyArg_UnpackTuple(args
, "starmap", 2, 2, &func
, &seq
))
1321 it
= PyObject_GetIter(seq
);
1325 /* create starmapobject structure */
1326 lz
= (starmapobject
*)type
->tp_alloc(type
, 0);
1335 return (PyObject
*)lz
;
1339 starmap_dealloc(starmapobject
*lz
)
1341 PyObject_GC_UnTrack(lz
);
1342 Py_XDECREF(lz
->func
);
1344 Py_TYPE(lz
)->tp_free(lz
);
1348 starmap_traverse(starmapobject
*lz
, visitproc visit
, void *arg
)
1356 starmap_next(starmapobject
*lz
)
1360 PyObject
*it
= lz
->it
;
1362 args
= (*Py_TYPE(it
)->tp_iternext
)(it
);
1365 if (!PyTuple_CheckExact(args
)) {
1366 PyObject
*newargs
= PySequence_Tuple(args
);
1368 if (newargs
== NULL
)
1372 result
= PyObject_Call(lz
->func
, args
, NULL
);
1377 PyDoc_STRVAR(starmap_doc
,
1378 "starmap(function, sequence) --> starmap object\n\
1380 Return an iterator whose values are returned from the function evaluated\n\
1381 with a argument tuple taken from the given sequence.");
1383 static PyTypeObject starmap_type
= {
1384 PyVarObject_HEAD_INIT(NULL
, 0)
1385 "itertools.starmap", /* tp_name */
1386 sizeof(starmapobject
), /* tp_basicsize */
1387 0, /* tp_itemsize */
1389 (destructor
)starmap_dealloc
, /* tp_dealloc */
1393 0, /* tp_reserved */
1395 0, /* tp_as_number */
1396 0, /* tp_as_sequence */
1397 0, /* tp_as_mapping */
1401 PyObject_GenericGetAttr
, /* tp_getattro */
1402 0, /* tp_setattro */
1403 0, /* tp_as_buffer */
1404 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1405 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1406 starmap_doc
, /* tp_doc */
1407 (traverseproc
)starmap_traverse
, /* tp_traverse */
1409 0, /* tp_richcompare */
1410 0, /* tp_weaklistoffset */
1411 PyObject_SelfIter
, /* tp_iter */
1412 (iternextfunc
)starmap_next
, /* tp_iternext */
1418 0, /* tp_descr_get */
1419 0, /* tp_descr_set */
1420 0, /* tp_dictoffset */
1423 starmap_new
, /* tp_new */
1424 PyObject_GC_Del
, /* tp_free */
1428 /* chain object ************************************************************/
1432 PyObject
*source
; /* Iterator over input iterables */
1433 PyObject
*active
; /* Currently running input iterator */
1436 static PyTypeObject chain_type
;
1439 chain_new_internal(PyTypeObject
*type
, PyObject
*source
)
1443 lz
= (chainobject
*)type
->tp_alloc(type
, 0);
1449 lz
->source
= source
;
1451 return (PyObject
*)lz
;
1455 chain_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1459 if (type
== &chain_type
&& !_PyArg_NoKeywords("chain()", kwds
))
1462 source
= PyObject_GetIter(args
);
1466 return chain_new_internal(type
, source
);
1470 chain_new_from_iterable(PyTypeObject
*type
, PyObject
*arg
)
1474 source
= PyObject_GetIter(arg
);
1478 return chain_new_internal(type
, source
);
1482 chain_dealloc(chainobject
*lz
)
1484 PyObject_GC_UnTrack(lz
);
1485 Py_XDECREF(lz
->active
);
1486 Py_XDECREF(lz
->source
);
1487 Py_TYPE(lz
)->tp_free(lz
);
1491 chain_traverse(chainobject
*lz
, visitproc visit
, void *arg
)
1493 Py_VISIT(lz
->source
);
1494 Py_VISIT(lz
->active
);
1499 chain_next(chainobject
*lz
)
1503 if (lz
->source
== NULL
)
1504 return NULL
; /* already stopped */
1506 if (lz
->active
== NULL
) {
1507 PyObject
*iterable
= PyIter_Next(lz
->source
);
1508 if (iterable
== NULL
) {
1509 Py_CLEAR(lz
->source
);
1510 return NULL
; /* no more input sources */
1512 lz
->active
= PyObject_GetIter(iterable
);
1513 Py_DECREF(iterable
);
1514 if (lz
->active
== NULL
) {
1515 Py_CLEAR(lz
->source
);
1516 return NULL
; /* input not iterable */
1519 item
= PyIter_Next(lz
->active
);
1522 if (PyErr_Occurred()) {
1523 if (PyErr_ExceptionMatches(PyExc_StopIteration
))
1526 return NULL
; /* input raised an exception */
1528 Py_CLEAR(lz
->active
);
1529 return chain_next(lz
); /* recurse and use next active */
1532 PyDoc_STRVAR(chain_doc
,
1533 "chain(*iterables) --> chain object\n\
1535 Return a chain object whose .__next__() method returns elements from the\n\
1536 first iterable until it is exhausted, then elements from the next\n\
1537 iterable, until all of the iterables are exhausted.");
1539 PyDoc_STRVAR(chain_from_iterable_doc
,
1540 "chain.from_iterable(iterable) --> chain object\n\
1542 Alternate chain() contructor taking a single iterable argument\n\
1543 that evaluates lazily.");
1545 static PyMethodDef chain_methods
[] = {
1546 {"from_iterable", (PyCFunction
) chain_new_from_iterable
, METH_O
| METH_CLASS
,
1547 chain_from_iterable_doc
},
1548 {NULL
, NULL
} /* sentinel */
1551 static PyTypeObject chain_type
= {
1552 PyVarObject_HEAD_INIT(NULL
, 0)
1553 "itertools.chain", /* tp_name */
1554 sizeof(chainobject
), /* tp_basicsize */
1555 0, /* tp_itemsize */
1557 (destructor
)chain_dealloc
, /* tp_dealloc */
1561 0, /* tp_reserved */
1563 0, /* tp_as_number */
1564 0, /* tp_as_sequence */
1565 0, /* tp_as_mapping */
1569 PyObject_GenericGetAttr
, /* tp_getattro */
1570 0, /* tp_setattro */
1571 0, /* tp_as_buffer */
1572 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1573 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1574 chain_doc
, /* tp_doc */
1575 (traverseproc
)chain_traverse
, /* tp_traverse */
1577 0, /* tp_richcompare */
1578 0, /* tp_weaklistoffset */
1579 PyObject_SelfIter
, /* tp_iter */
1580 (iternextfunc
)chain_next
, /* tp_iternext */
1581 chain_methods
, /* tp_methods */
1586 0, /* tp_descr_get */
1587 0, /* tp_descr_set */
1588 0, /* tp_dictoffset */
1591 chain_new
, /* tp_new */
1592 PyObject_GC_Del
, /* tp_free */
1596 /* product object ************************************************************/
1600 PyObject
*pools
; /* tuple of pool tuples */
1601 Py_ssize_t
*indices
; /* one index per pool */
1602 PyObject
*result
; /* most recently returned result tuple */
1603 int stopped
; /* set to 1 when the product iterator is exhausted */
1606 static PyTypeObject product_type
;
1609 product_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1612 Py_ssize_t nargs
, npools
, repeat
=1;
1613 PyObject
*pools
= NULL
;
1614 Py_ssize_t
*indices
= NULL
;
1618 char *kwlist
[] = {"repeat", 0};
1619 PyObject
*tmpargs
= PyTuple_New(0);
1620 if (tmpargs
== NULL
)
1622 if (!PyArg_ParseTupleAndKeywords(tmpargs
, kwds
, "|n:product", kwlist
, &repeat
)) {
1628 PyErr_SetString(PyExc_ValueError
,
1629 "repeat argument cannot be negative");
1634 assert(PyTuple_Check(args
));
1635 nargs
= (repeat
== 0) ? 0 : PyTuple_GET_SIZE(args
);
1636 npools
= nargs
* repeat
;
1638 indices
= PyMem_Malloc(npools
* sizeof(Py_ssize_t
));
1639 if (indices
== NULL
) {
1644 pools
= PyTuple_New(npools
);
1648 for (i
=0; i
< nargs
; ++i
) {
1649 PyObject
*item
= PyTuple_GET_ITEM(args
, i
);
1650 PyObject
*pool
= PySequence_Tuple(item
);
1653 PyTuple_SET_ITEM(pools
, i
, pool
);
1656 for ( ; i
< npools
; ++i
) {
1657 PyObject
*pool
= PyTuple_GET_ITEM(pools
, i
- nargs
);
1659 PyTuple_SET_ITEM(pools
, i
, pool
);
1663 /* create productobject structure */
1664 lz
= (productobject
*)type
->tp_alloc(type
, 0);
1669 lz
->indices
= indices
;
1673 return (PyObject
*)lz
;
1676 if (indices
!= NULL
)
1677 PyMem_Free(indices
);
1683 product_dealloc(productobject
*lz
)
1685 PyObject_GC_UnTrack(lz
);
1686 Py_XDECREF(lz
->pools
);
1687 Py_XDECREF(lz
->result
);
1688 if (lz
->indices
!= NULL
)
1689 PyMem_Free(lz
->indices
);
1690 Py_TYPE(lz
)->tp_free(lz
);
1694 product_traverse(productobject
*lz
, visitproc visit
, void *arg
)
1696 Py_VISIT(lz
->pools
);
1697 Py_VISIT(lz
->result
);
1702 product_next(productobject
*lz
)
1707 PyObject
*pools
= lz
->pools
;
1708 PyObject
*result
= lz
->result
;
1709 Py_ssize_t npools
= PyTuple_GET_SIZE(pools
);
1715 if (result
== NULL
) {
1716 /* On the first pass, return an initial tuple filled with the
1717 first element from each pool. */
1718 result
= PyTuple_New(npools
);
1721 lz
->result
= result
;
1722 for (i
=0; i
< npools
; i
++) {
1723 pool
= PyTuple_GET_ITEM(pools
, i
);
1724 if (PyTuple_GET_SIZE(pool
) == 0)
1726 elem
= PyTuple_GET_ITEM(pool
, 0);
1728 PyTuple_SET_ITEM(result
, i
, elem
);
1731 Py_ssize_t
*indices
= lz
->indices
;
1733 /* Copy the previous result tuple or re-use it if available */
1734 if (Py_REFCNT(result
) > 1) {
1735 PyObject
*old_result
= result
;
1736 result
= PyTuple_New(npools
);
1739 lz
->result
= result
;
1740 for (i
=0; i
< npools
; i
++) {
1741 elem
= PyTuple_GET_ITEM(old_result
, i
);
1743 PyTuple_SET_ITEM(result
, i
, elem
);
1745 Py_DECREF(old_result
);
1747 /* Now, we've got the only copy so we can update it in-place */
1748 assert (npools
==0 || Py_REFCNT(result
) == 1);
1750 /* Update the pool indices right-to-left. Only advance to the
1751 next pool when the previous one rolls-over */
1752 for (i
=npools
-1 ; i
>= 0 ; i
--) {
1753 pool
= PyTuple_GET_ITEM(pools
, i
);
1755 if (indices
[i
] == PyTuple_GET_SIZE(pool
)) {
1756 /* Roll-over and advance to next pool */
1758 elem
= PyTuple_GET_ITEM(pool
, 0);
1760 oldelem
= PyTuple_GET_ITEM(result
, i
);
1761 PyTuple_SET_ITEM(result
, i
, elem
);
1764 /* No rollover. Just increment and stop here. */
1765 elem
= PyTuple_GET_ITEM(pool
, indices
[i
]);
1767 oldelem
= PyTuple_GET_ITEM(result
, i
);
1768 PyTuple_SET_ITEM(result
, i
, elem
);
1774 /* If i is negative, then the indices have all rolled-over
1788 PyDoc_STRVAR(product_doc
,
1789 "product(*iterables) --> product object\n\
1791 Cartesian product of input iterables. Equivalent to nested for-loops.\n\n\
1792 For example, product(A, B) returns the same as: ((x,y) for x in A for y in B).\n\
1793 The leftmost iterators are in the outermost for-loop, so the output tuples\n\
1794 cycle in a manner similar to an odometer (with the rightmost element changing\n\
1795 on every iteration).\n\n\
1796 To compute the product of an iterable with itself, specify the number\n\
1797 of repetitions with the optional repeat keyword argument. For example,\n\
1798 product(A, repeat=4) means the same as product(A, A, A, A).\n\n\
1799 product('ab', range(3)) --> ('a',0) ('a',1) ('a',2) ('b',0) ('b',1) ('b',2)\n\
1800 product((0,1), (0,1), (0,1)) --> (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) ...");
1802 static PyTypeObject product_type
= {
1803 PyVarObject_HEAD_INIT(NULL
, 0)
1804 "itertools.product", /* tp_name */
1805 sizeof(productobject
), /* tp_basicsize */
1806 0, /* tp_itemsize */
1808 (destructor
)product_dealloc
, /* tp_dealloc */
1812 0, /* tp_reserved */
1814 0, /* tp_as_number */
1815 0, /* tp_as_sequence */
1816 0, /* tp_as_mapping */
1820 PyObject_GenericGetAttr
, /* tp_getattro */
1821 0, /* tp_setattro */
1822 0, /* tp_as_buffer */
1823 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1824 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1825 product_doc
, /* tp_doc */
1826 (traverseproc
)product_traverse
, /* tp_traverse */
1828 0, /* tp_richcompare */
1829 0, /* tp_weaklistoffset */
1830 PyObject_SelfIter
, /* tp_iter */
1831 (iternextfunc
)product_next
, /* tp_iternext */
1837 0, /* tp_descr_get */
1838 0, /* tp_descr_set */
1839 0, /* tp_dictoffset */
1842 product_new
, /* tp_new */
1843 PyObject_GC_Del
, /* tp_free */
1847 /* combinations object ************************************************************/
1851 PyObject
*pool
; /* input converted to a tuple */
1852 Py_ssize_t
*indices
; /* one index per result element */
1853 PyObject
*result
; /* most recently returned result tuple */
1854 Py_ssize_t r
; /* size of result tuple */
1855 int stopped
; /* set to 1 when the combinations iterator is exhausted */
1856 } combinationsobject
;
1858 static PyTypeObject combinations_type
;
1861 combinations_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1863 combinationsobject
*co
;
1866 PyObject
*pool
= NULL
;
1867 PyObject
*iterable
= NULL
;
1868 Py_ssize_t
*indices
= NULL
;
1870 static char *kwargs
[] = {"iterable", "r", NULL
};
1872 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "On:combinations", kwargs
,
1876 pool
= PySequence_Tuple(iterable
);
1879 n
= PyTuple_GET_SIZE(pool
);
1881 PyErr_SetString(PyExc_ValueError
, "r must be non-negative");
1885 indices
= PyMem_Malloc(r
* sizeof(Py_ssize_t
));
1886 if (indices
== NULL
) {
1891 for (i
=0 ; i
<r
; i
++)
1894 /* create combinationsobject structure */
1895 co
= (combinationsobject
*)type
->tp_alloc(type
, 0);
1900 co
->indices
= indices
;
1903 co
->stopped
= r
> n
? 1 : 0;
1905 return (PyObject
*)co
;
1908 if (indices
!= NULL
)
1909 PyMem_Free(indices
);
1915 combinations_dealloc(combinationsobject
*co
)
1917 PyObject_GC_UnTrack(co
);
1918 Py_XDECREF(co
->pool
);
1919 Py_XDECREF(co
->result
);
1920 if (co
->indices
!= NULL
)
1921 PyMem_Free(co
->indices
);
1922 Py_TYPE(co
)->tp_free(co
);
1926 combinations_traverse(combinationsobject
*co
, visitproc visit
, void *arg
)
1929 Py_VISIT(co
->result
);
1934 combinations_next(combinationsobject
*co
)
1938 PyObject
*pool
= co
->pool
;
1939 Py_ssize_t
*indices
= co
->indices
;
1940 PyObject
*result
= co
->result
;
1941 Py_ssize_t n
= PyTuple_GET_SIZE(pool
);
1942 Py_ssize_t r
= co
->r
;
1943 Py_ssize_t i
, j
, index
;
1948 if (result
== NULL
) {
1949 /* On the first pass, initialize result tuple using the indices */
1950 result
= PyTuple_New(r
);
1953 co
->result
= result
;
1954 for (i
=0; i
<r
; i
++) {
1956 elem
= PyTuple_GET_ITEM(pool
, index
);
1958 PyTuple_SET_ITEM(result
, i
, elem
);
1961 /* Copy the previous result tuple or re-use it if available */
1962 if (Py_REFCNT(result
) > 1) {
1963 PyObject
*old_result
= result
;
1964 result
= PyTuple_New(r
);
1967 co
->result
= result
;
1968 for (i
=0; i
<r
; i
++) {
1969 elem
= PyTuple_GET_ITEM(old_result
, i
);
1971 PyTuple_SET_ITEM(result
, i
, elem
);
1973 Py_DECREF(old_result
);
1975 /* Now, we've got the only copy so we can update it in-place
1976 * CPython's empty tuple is a singleton and cached in
1977 * PyTuple's freelist.
1979 assert(r
== 0 || Py_REFCNT(result
) == 1);
1981 /* Scan indices right-to-left until finding one that is not
1982 at its maximum (i + n - r). */
1983 for (i
=r
-1 ; i
>= 0 && indices
[i
] == i
+n
-r
; i
--)
1986 /* If i is negative, then the indices are all at
1987 their maximum value and we're done. */
1991 /* Increment the current index which we know is not at its
1992 maximum. Then move back to the right setting each index
1993 to its lowest possible value (one higher than the index
1994 to its left -- this maintains the sort order invariant). */
1996 for (j
=i
+1 ; j
<r
; j
++)
1997 indices
[j
] = indices
[j
-1] + 1;
1999 /* Update the result tuple for the new indices
2000 starting with i, the leftmost index that changed */
2001 for ( ; i
<r
; i
++) {
2003 elem
= PyTuple_GET_ITEM(pool
, index
);
2005 oldelem
= PyTuple_GET_ITEM(result
, i
);
2006 PyTuple_SET_ITEM(result
, i
, elem
);
2019 PyDoc_STRVAR(combinations_doc
,
2020 "combinations(iterable, r) --> combinations object\n\
2022 Return successive r-length combinations of elements in the iterable.\n\n\
2023 combinations(range(4), 3) --> (0,1,2), (0,1,3), (0,2,3), (1,2,3)");
2025 static PyTypeObject combinations_type
= {
2026 PyVarObject_HEAD_INIT(NULL
, 0)
2027 "itertools.combinations", /* tp_name */
2028 sizeof(combinationsobject
), /* tp_basicsize */
2029 0, /* tp_itemsize */
2031 (destructor
)combinations_dealloc
, /* tp_dealloc */
2035 0, /* tp_reserved */
2037 0, /* tp_as_number */
2038 0, /* tp_as_sequence */
2039 0, /* tp_as_mapping */
2043 PyObject_GenericGetAttr
, /* tp_getattro */
2044 0, /* tp_setattro */
2045 0, /* tp_as_buffer */
2046 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2047 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2048 combinations_doc
, /* tp_doc */
2049 (traverseproc
)combinations_traverse
, /* tp_traverse */
2051 0, /* tp_richcompare */
2052 0, /* tp_weaklistoffset */
2053 PyObject_SelfIter
, /* tp_iter */
2054 (iternextfunc
)combinations_next
, /* tp_iternext */
2060 0, /* tp_descr_get */
2061 0, /* tp_descr_set */
2062 0, /* tp_dictoffset */
2065 combinations_new
, /* tp_new */
2066 PyObject_GC_Del
, /* tp_free */
2070 /* combinations with replacement object *******************************************/
2074 def combinations_with_replacement(iterable, r):
2075 "combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC"
2076 # number items returned: (n+r-1)! / r! / (n-1)!
2077 pool = tuple(iterable)
2080 yield tuple(pool[i] for i in indices)
2082 for i in reversed(range(r)):
2083 if indices[i] != n - 1:
2087 indices[i:] = [indices[i] + 1] * (r - i)
2088 yield tuple(pool[i] for i in indices)
2090 def combinations_with_replacement2(iterable, r):
2091 'Alternate version that filters from product()'
2092 pool = tuple(iterable)
2094 for indices in product(range(n), repeat=r):
2095 if sorted(indices) == list(indices):
2096 yield tuple(pool[i] for i in indices)
2100 PyObject
*pool
; /* input converted to a tuple */
2101 Py_ssize_t
*indices
; /* one index per result element */
2102 PyObject
*result
; /* most recently returned result tuple */
2103 Py_ssize_t r
; /* size of result tuple */
2104 int stopped
; /* set to 1 when the cwr iterator is exhausted */
2107 static PyTypeObject cwr_type
;
2110 cwr_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2115 PyObject
*pool
= NULL
;
2116 PyObject
*iterable
= NULL
;
2117 Py_ssize_t
*indices
= NULL
;
2119 static char *kwargs
[] = {"iterable", "r", NULL
};
2121 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "On:combinations_with_replacement", kwargs
,
2125 pool
= PySequence_Tuple(iterable
);
2128 n
= PyTuple_GET_SIZE(pool
);
2130 PyErr_SetString(PyExc_ValueError
, "r must be non-negative");
2134 indices
= PyMem_Malloc(r
* sizeof(Py_ssize_t
));
2135 if (indices
== NULL
) {
2140 for (i
=0 ; i
<r
; i
++)
2143 /* create cwrobject structure */
2144 co
= (cwrobject
*)type
->tp_alloc(type
, 0);
2149 co
->indices
= indices
;
2152 co
->stopped
= !n
&& r
;
2154 return (PyObject
*)co
;
2157 if (indices
!= NULL
)
2158 PyMem_Free(indices
);
2164 cwr_dealloc(cwrobject
*co
)
2166 PyObject_GC_UnTrack(co
);
2167 Py_XDECREF(co
->pool
);
2168 Py_XDECREF(co
->result
);
2169 if (co
->indices
!= NULL
)
2170 PyMem_Free(co
->indices
);
2171 Py_TYPE(co
)->tp_free(co
);
2175 cwr_traverse(cwrobject
*co
, visitproc visit
, void *arg
)
2178 Py_VISIT(co
->result
);
2183 cwr_next(cwrobject
*co
)
2187 PyObject
*pool
= co
->pool
;
2188 Py_ssize_t
*indices
= co
->indices
;
2189 PyObject
*result
= co
->result
;
2190 Py_ssize_t n
= PyTuple_GET_SIZE(pool
);
2191 Py_ssize_t r
= co
->r
;
2192 Py_ssize_t i
, j
, index
;
2197 if (result
== NULL
) {
2198 /* On the first pass, initialize result tuple using the indices */
2199 result
= PyTuple_New(r
);
2202 co
->result
= result
;
2203 for (i
=0; i
<r
; i
++) {
2205 elem
= PyTuple_GET_ITEM(pool
, index
);
2207 PyTuple_SET_ITEM(result
, i
, elem
);
2210 /* Copy the previous result tuple or re-use it if available */
2211 if (Py_REFCNT(result
) > 1) {
2212 PyObject
*old_result
= result
;
2213 result
= PyTuple_New(r
);
2216 co
->result
= result
;
2217 for (i
=0; i
<r
; i
++) {
2218 elem
= PyTuple_GET_ITEM(old_result
, i
);
2220 PyTuple_SET_ITEM(result
, i
, elem
);
2222 Py_DECREF(old_result
);
2224 /* Now, we've got the only copy so we can update it in-place CPython's
2225 empty tuple is a singleton and cached in PyTuple's freelist. */
2226 assert(r
== 0 || Py_REFCNT(result
) == 1);
2228 /* Scan indices right-to-left until finding one that is not
2229 * at its maximum (n-1). */
2230 for (i
=r
-1 ; i
>= 0 && indices
[i
] == n
-1; i
--)
2233 /* If i is negative, then the indices are all at
2234 their maximum value and we're done. */
2238 /* Increment the current index which we know is not at its
2239 maximum. Then set all to the right to the same value. */
2241 for (j
=i
+1 ; j
<r
; j
++)
2242 indices
[j
] = indices
[j
-1];
2244 /* Update the result tuple for the new indices
2245 starting with i, the leftmost index that changed */
2246 for ( ; i
<r
; i
++) {
2248 elem
= PyTuple_GET_ITEM(pool
, index
);
2250 oldelem
= PyTuple_GET_ITEM(result
, i
);
2251 PyTuple_SET_ITEM(result
, i
, elem
);
2264 PyDoc_STRVAR(cwr_doc
,
2265 "combinations_with_replacement(iterable, r) --> combinations_with_replacement object\n\
2267 Return successive r-length combinations of elements in the iterable\n\
2268 allowing individual elements to have successive repeats.\n\
2269 combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC");
2271 static PyTypeObject cwr_type
= {
2272 PyVarObject_HEAD_INIT(NULL
, 0)
2273 "itertools.combinations_with_replacement", /* tp_name */
2274 sizeof(cwrobject
), /* tp_basicsize */
2275 0, /* tp_itemsize */
2277 (destructor
)cwr_dealloc
, /* tp_dealloc */
2281 0, /* tp_reserved */
2283 0, /* tp_as_number */
2284 0, /* tp_as_sequence */
2285 0, /* tp_as_mapping */
2289 PyObject_GenericGetAttr
, /* tp_getattro */
2290 0, /* tp_setattro */
2291 0, /* tp_as_buffer */
2292 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2293 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2294 cwr_doc
, /* tp_doc */
2295 (traverseproc
)cwr_traverse
, /* tp_traverse */
2297 0, /* tp_richcompare */
2298 0, /* tp_weaklistoffset */
2299 PyObject_SelfIter
, /* tp_iter */
2300 (iternextfunc
)cwr_next
, /* tp_iternext */
2306 0, /* tp_descr_get */
2307 0, /* tp_descr_set */
2308 0, /* tp_dictoffset */
2311 cwr_new
, /* tp_new */
2312 PyObject_GC_Del
, /* tp_free */
2316 /* permutations object ************************************************************
2318 def permutations(iterable, r=None):
2319 'permutations(range(3), 2) --> (0,1) (0,2) (1,0) (1,2) (2,0) (2,1)'
2320 pool = tuple(iterable)
2322 r = n if r is None else r
2324 cycles = range(n-r+1, n+1)[::-1]
2325 yield tuple(pool[i] for i in indices[:r])
2327 for i in reversed(range(r)):
2330 indices[i:] = indices[i+1:] + indices[i:i+1]
2334 indices[i], indices[-j] = indices[-j], indices[i]
2335 yield tuple(pool[i] for i in indices[:r])
2343 PyObject
*pool
; /* input converted to a tuple */
2344 Py_ssize_t
*indices
; /* one index per element in the pool */
2345 Py_ssize_t
*cycles
; /* one rollover counter per element in the result */
2346 PyObject
*result
; /* most recently returned result tuple */
2347 Py_ssize_t r
; /* size of result tuple */
2348 int stopped
; /* set to 1 when the permutations iterator is exhausted */
2349 } permutationsobject
;
2351 static PyTypeObject permutations_type
;
2354 permutations_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2356 permutationsobject
*po
;
2359 PyObject
*robj
= Py_None
;
2360 PyObject
*pool
= NULL
;
2361 PyObject
*iterable
= NULL
;
2362 Py_ssize_t
*indices
= NULL
;
2363 Py_ssize_t
*cycles
= NULL
;
2365 static char *kwargs
[] = {"iterable", "r", NULL
};
2367 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "O|O:permutations", kwargs
,
2371 pool
= PySequence_Tuple(iterable
);
2374 n
= PyTuple_GET_SIZE(pool
);
2377 if (robj
!= Py_None
) {
2378 if (!PyLong_Check(robj
)) {
2379 PyErr_SetString(PyExc_TypeError
, "Expected int as r");
2382 r
= PyLong_AsSsize_t(robj
);
2383 if (r
== -1 && PyErr_Occurred())
2387 PyErr_SetString(PyExc_ValueError
, "r must be non-negative");
2391 indices
= PyMem_Malloc(n
* sizeof(Py_ssize_t
));
2392 cycles
= PyMem_Malloc(r
* sizeof(Py_ssize_t
));
2393 if (indices
== NULL
|| cycles
== NULL
) {
2398 for (i
=0 ; i
<n
; i
++)
2400 for (i
=0 ; i
<r
; i
++)
2403 /* create permutationsobject structure */
2404 po
= (permutationsobject
*)type
->tp_alloc(type
, 0);
2409 po
->indices
= indices
;
2410 po
->cycles
= cycles
;
2413 po
->stopped
= r
> n
? 1 : 0;
2415 return (PyObject
*)po
;
2418 if (indices
!= NULL
)
2419 PyMem_Free(indices
);
2427 permutations_dealloc(permutationsobject
*po
)
2429 PyObject_GC_UnTrack(po
);
2430 Py_XDECREF(po
->pool
);
2431 Py_XDECREF(po
->result
);
2432 PyMem_Free(po
->indices
);
2433 PyMem_Free(po
->cycles
);
2434 Py_TYPE(po
)->tp_free(po
);
2438 permutations_traverse(permutationsobject
*po
, visitproc visit
, void *arg
)
2441 Py_VISIT(po
->result
);
2446 permutations_next(permutationsobject
*po
)
2450 PyObject
*pool
= po
->pool
;
2451 Py_ssize_t
*indices
= po
->indices
;
2452 Py_ssize_t
*cycles
= po
->cycles
;
2453 PyObject
*result
= po
->result
;
2454 Py_ssize_t n
= PyTuple_GET_SIZE(pool
);
2455 Py_ssize_t r
= po
->r
;
2456 Py_ssize_t i
, j
, k
, index
;
2461 if (result
== NULL
) {
2462 /* On the first pass, initialize result tuple using the indices */
2463 result
= PyTuple_New(r
);
2466 po
->result
= result
;
2467 for (i
=0; i
<r
; i
++) {
2469 elem
= PyTuple_GET_ITEM(pool
, index
);
2471 PyTuple_SET_ITEM(result
, i
, elem
);
2477 /* Copy the previous result tuple or re-use it if available */
2478 if (Py_REFCNT(result
) > 1) {
2479 PyObject
*old_result
= result
;
2480 result
= PyTuple_New(r
);
2483 po
->result
= result
;
2484 for (i
=0; i
<r
; i
++) {
2485 elem
= PyTuple_GET_ITEM(old_result
, i
);
2487 PyTuple_SET_ITEM(result
, i
, elem
);
2489 Py_DECREF(old_result
);
2491 /* Now, we've got the only copy so we can update it in-place */
2492 assert(r
== 0 || Py_REFCNT(result
) == 1);
2494 /* Decrement rightmost cycle, moving leftward upon zero rollover */
2495 for (i
=r
-1 ; i
>=0 ; i
--) {
2497 if (cycles
[i
] == 0) {
2498 /* rotatation: indices[i:] = indices[i+1:] + indices[i:i+1] */
2500 for (j
=i
; j
<n
-1 ; j
++)
2501 indices
[j
] = indices
[j
+1];
2502 indices
[n
-1] = index
;
2507 indices
[i
] = indices
[n
-j
];
2508 indices
[n
-j
] = index
;
2510 for (k
=i
; k
<r
; k
++) {
2511 /* start with i, the leftmost element that changed */
2512 /* yield tuple(pool[k] for k in indices[:r]) */
2514 elem
= PyTuple_GET_ITEM(pool
, index
);
2516 oldelem
= PyTuple_GET_ITEM(result
, k
);
2517 PyTuple_SET_ITEM(result
, k
, elem
);
2523 /* If i is negative, then the cycles have all
2524 rolled-over and we're done. */
2536 PyDoc_STRVAR(permutations_doc
,
2537 "permutations(iterable[, r]) --> permutations object\n\
2539 Return successive r-length permutations of elements in the iterable.\n\n\
2540 permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)");
2542 static PyTypeObject permutations_type
= {
2543 PyVarObject_HEAD_INIT(NULL
, 0)
2544 "itertools.permutations", /* tp_name */
2545 sizeof(permutationsobject
), /* tp_basicsize */
2546 0, /* tp_itemsize */
2548 (destructor
)permutations_dealloc
, /* tp_dealloc */
2552 0, /* tp_reserved */
2554 0, /* tp_as_number */
2555 0, /* tp_as_sequence */
2556 0, /* tp_as_mapping */
2560 PyObject_GenericGetAttr
, /* tp_getattro */
2561 0, /* tp_setattro */
2562 0, /* tp_as_buffer */
2563 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2564 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2565 permutations_doc
, /* tp_doc */
2566 (traverseproc
)permutations_traverse
, /* tp_traverse */
2568 0, /* tp_richcompare */
2569 0, /* tp_weaklistoffset */
2570 PyObject_SelfIter
, /* tp_iter */
2571 (iternextfunc
)permutations_next
, /* tp_iternext */
2577 0, /* tp_descr_get */
2578 0, /* tp_descr_set */
2579 0, /* tp_dictoffset */
2582 permutations_new
, /* tp_new */
2583 PyObject_GC_Del
, /* tp_free */
2587 /* compress object ************************************************************/
2591 def compress(data, selectors):
2592 "compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F"
2593 return (d for d, s in zip(data, selectors) if s)
2599 PyObject
*selectors
;
2602 static PyTypeObject compress_type
;
2605 compress_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2607 PyObject
*seq1
, *seq2
;
2608 PyObject
*data
=NULL
, *selectors
=NULL
;
2610 static char *kwargs
[] = {"data", "selectors", NULL
};
2612 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "OO:compress", kwargs
, &seq1
, &seq2
))
2615 data
= PyObject_GetIter(seq1
);
2618 selectors
= PyObject_GetIter(seq2
);
2619 if (selectors
== NULL
)
2622 /* create compressobject structure */
2623 lz
= (compressobject
*)type
->tp_alloc(type
, 0);
2627 lz
->selectors
= selectors
;
2628 return (PyObject
*)lz
;
2632 Py_XDECREF(selectors
);
2637 compress_dealloc(compressobject
*lz
)
2639 PyObject_GC_UnTrack(lz
);
2640 Py_XDECREF(lz
->data
);
2641 Py_XDECREF(lz
->selectors
);
2642 Py_TYPE(lz
)->tp_free(lz
);
2646 compress_traverse(compressobject
*lz
, visitproc visit
, void *arg
)
2649 Py_VISIT(lz
->selectors
);
2654 compress_next(compressobject
*lz
)
2656 PyObject
*data
= lz
->data
, *selectors
= lz
->selectors
;
2657 PyObject
*datum
, *selector
;
2658 PyObject
*(*datanext
)(PyObject
*) = *Py_TYPE(data
)->tp_iternext
;
2659 PyObject
*(*selectornext
)(PyObject
*) = *Py_TYPE(selectors
)->tp_iternext
;
2663 /* Steps: get datum, get selector, evaluate selector.
2664 Order is important (to match the pure python version
2665 in terms of which input gets a chance to raise an
2669 datum
= datanext(data
);
2673 selector
= selectornext(selectors
);
2674 if (selector
== NULL
) {
2679 ok
= PyObject_IsTrue(selector
);
2680 Py_DECREF(selector
);
2689 PyDoc_STRVAR(compress_doc
,
2690 "compress(data, selectors) --> iterator over selected data\n\
2692 Return data elements corresponding to true selector elements.\n\
2693 Forms a shorter iterator from selected data elements using the\n\
2694 selectors to choose the data elements.");
2696 static PyTypeObject compress_type
= {
2697 PyVarObject_HEAD_INIT(NULL
, 0)
2698 "itertools.compress", /* tp_name */
2699 sizeof(compressobject
), /* tp_basicsize */
2700 0, /* tp_itemsize */
2702 (destructor
)compress_dealloc
, /* tp_dealloc */
2706 0, /* tp_reserved */
2708 0, /* tp_as_number */
2709 0, /* tp_as_sequence */
2710 0, /* tp_as_mapping */
2714 PyObject_GenericGetAttr
, /* tp_getattro */
2715 0, /* tp_setattro */
2716 0, /* tp_as_buffer */
2717 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2718 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2719 compress_doc
, /* tp_doc */
2720 (traverseproc
)compress_traverse
, /* tp_traverse */
2722 0, /* tp_richcompare */
2723 0, /* tp_weaklistoffset */
2724 PyObject_SelfIter
, /* tp_iter */
2725 (iternextfunc
)compress_next
, /* tp_iternext */
2731 0, /* tp_descr_get */
2732 0, /* tp_descr_set */
2733 0, /* tp_dictoffset */
2736 compress_new
, /* tp_new */
2737 PyObject_GC_Del
, /* tp_free */
2741 /* filterfalse object ************************************************************/
2747 } filterfalseobject
;
2749 static PyTypeObject filterfalse_type
;
2752 filterfalse_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2754 PyObject
*func
, *seq
;
2756 filterfalseobject
*lz
;
2758 if (type
== &filterfalse_type
&&
2759 !_PyArg_NoKeywords("filterfalse()", kwds
))
2762 if (!PyArg_UnpackTuple(args
, "filterfalse", 2, 2, &func
, &seq
))
2766 it
= PyObject_GetIter(seq
);
2770 /* create filterfalseobject structure */
2771 lz
= (filterfalseobject
*)type
->tp_alloc(type
, 0);
2780 return (PyObject
*)lz
;
2784 filterfalse_dealloc(filterfalseobject
*lz
)
2786 PyObject_GC_UnTrack(lz
);
2787 Py_XDECREF(lz
->func
);
2789 Py_TYPE(lz
)->tp_free(lz
);
2793 filterfalse_traverse(filterfalseobject
*lz
, visitproc visit
, void *arg
)
2801 filterfalse_next(filterfalseobject
*lz
)
2804 PyObject
*it
= lz
->it
;
2806 PyObject
*(*iternext
)(PyObject
*);
2808 iternext
= *Py_TYPE(it
)->tp_iternext
;
2810 item
= iternext(it
);
2814 if (lz
->func
== Py_None
|| lz
->func
== (PyObject
*)&PyBool_Type
) {
2815 ok
= PyObject_IsTrue(item
);
2818 good
= PyObject_CallFunctionObjArgs(lz
->func
,
2824 ok
= PyObject_IsTrue(good
);
2833 PyDoc_STRVAR(filterfalse_doc
,
2834 "filterfalse(function or None, sequence) --> filterfalse object\n\
2836 Return those items of sequence for which function(item) is false.\n\
2837 If function is None, return the items that are false.");
2839 static PyTypeObject filterfalse_type
= {
2840 PyVarObject_HEAD_INIT(NULL
, 0)
2841 "itertools.filterfalse", /* tp_name */
2842 sizeof(filterfalseobject
), /* tp_basicsize */
2843 0, /* tp_itemsize */
2845 (destructor
)filterfalse_dealloc
, /* tp_dealloc */
2849 0, /* tp_reserved */
2851 0, /* tp_as_number */
2852 0, /* tp_as_sequence */
2853 0, /* tp_as_mapping */
2857 PyObject_GenericGetAttr
, /* tp_getattro */
2858 0, /* tp_setattro */
2859 0, /* tp_as_buffer */
2860 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2861 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2862 filterfalse_doc
, /* tp_doc */
2863 (traverseproc
)filterfalse_traverse
, /* tp_traverse */
2865 0, /* tp_richcompare */
2866 0, /* tp_weaklistoffset */
2867 PyObject_SelfIter
, /* tp_iter */
2868 (iternextfunc
)filterfalse_next
, /* tp_iternext */
2874 0, /* tp_descr_get */
2875 0, /* tp_descr_set */
2876 0, /* tp_dictoffset */
2879 filterfalse_new
, /* tp_new */
2880 PyObject_GC_Del
, /* tp_free */
2884 /* count object ************************************************************/
2890 PyObject
*long_step
;
2893 /* Counting logic and invariants:
2895 fast_mode: when cnt an integer < PY_SSIZE_T_MAX and no step is specified.
2897 assert(cnt != PY_SSIZE_T_MAX && long_cnt == NULL && long_step==PyInt(1));
2898 Advances with: cnt += 1
2899 When count hits Y_SSIZE_T_MAX, switch to slow_mode.
2901 slow_mode: when cnt == PY_SSIZE_T_MAX, step is not int(1), or cnt is a float.
2903 assert(cnt == PY_SSIZE_T_MAX && long_cnt != NULL && long_step != NULL);
2904 All counting is done with python objects (no overflows or underflows).
2905 Advances with: long_cnt += long_step
2906 Step may be zero -- effectively a slow version of repeat(cnt).
2907 Either long_cnt or long_step may be a float, Fraction, or Decimal.
2910 static PyTypeObject count_type
;
2913 count_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2918 PyObject
*long_cnt
= NULL
;
2919 PyObject
*long_step
= NULL
;
2920 static char *kwlist
[] = {"start", "step", 0};
2922 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "|OO:count",
2923 kwlist
, &long_cnt
, &long_step
))
2926 if ((long_cnt
!= NULL
&& !PyNumber_Check(long_cnt
)) ||
2927 (long_step
!= NULL
&& !PyNumber_Check(long_step
))) {
2928 PyErr_SetString(PyExc_TypeError
, "a number is required");
2932 if (long_cnt
!= NULL
) {
2933 cnt
= PyLong_AsSsize_t(long_cnt
);
2934 if ((cnt
== -1 && PyErr_Occurred()) || !PyLong_Check(long_cnt
)) {
2938 Py_INCREF(long_cnt
);
2941 long_cnt
= PyLong_FromLong(0);
2944 /* If not specified, step defaults to 1 */
2945 if (long_step
== NULL
) {
2946 long_step
= PyLong_FromLong(1);
2947 if (long_step
== NULL
) {
2948 Py_DECREF(long_cnt
);
2952 Py_INCREF(long_step
);
2954 assert(long_cnt
!= NULL
&& long_step
!= NULL
);
2956 /* Fast mode only works when the step is 1 */
2957 if (!PyLong_Check(long_step
) ||
2958 PyLong_AS_LONG(long_step
) != 1) {
2963 cnt
= PY_SSIZE_T_MAX
;
2967 assert((cnt
!= PY_SSIZE_T_MAX
&& long_cnt
== NULL
&& !slow_mode
) ||
2968 (cnt
== PY_SSIZE_T_MAX
&& long_cnt
!= NULL
&& slow_mode
));
2970 (PyLong_Check(long_step
) && PyLong_AS_LONG(long_step
) == 1));
2972 /* create countobject structure */
2973 lz
= (countobject
*)type
->tp_alloc(type
, 0);
2975 Py_XDECREF(long_cnt
);
2979 lz
->long_cnt
= long_cnt
;
2980 lz
->long_step
= long_step
;
2982 return (PyObject
*)lz
;
2986 count_dealloc(countobject
*lz
)
2988 PyObject_GC_UnTrack(lz
);
2989 Py_XDECREF(lz
->long_cnt
);
2990 Py_XDECREF(lz
->long_step
);
2991 Py_TYPE(lz
)->tp_free(lz
);
2995 count_traverse(countobject
*lz
, visitproc visit
, void *arg
)
2997 Py_VISIT(lz
->long_cnt
);
2998 Py_VISIT(lz
->long_step
);
3003 count_nextlong(countobject
*lz
)
3006 PyObject
*stepped_up
;
3008 long_cnt
= lz
->long_cnt
;
3009 if (long_cnt
== NULL
) {
3010 /* Switch to slow_mode */
3011 long_cnt
= PyLong_FromSsize_t(PY_SSIZE_T_MAX
);
3012 if (long_cnt
== NULL
)
3015 assert(lz
->cnt
== PY_SSIZE_T_MAX
&& long_cnt
!= NULL
);
3017 stepped_up
= PyNumber_Add(long_cnt
, lz
->long_step
);
3018 if (stepped_up
== NULL
)
3020 lz
->long_cnt
= stepped_up
;
3025 count_next(countobject
*lz
)
3027 if (lz
->cnt
== PY_SSIZE_T_MAX
)
3028 return count_nextlong(lz
);
3029 return PyLong_FromSsize_t(lz
->cnt
++);
3033 count_repr(countobject
*lz
)
3035 if (lz
->cnt
!= PY_SSIZE_T_MAX
)
3036 return PyUnicode_FromFormat("count(%zd)", lz
->cnt
);
3038 if (PyLong_Check(lz
->long_step
)) {
3039 long step
= PyLong_AsLong(lz
->long_step
);
3040 if (step
== -1 && PyErr_Occurred()) {
3044 /* Don't display step when it is an integer equal to 1 */
3045 return PyUnicode_FromFormat("count(%R)", lz
->long_cnt
);
3048 return PyUnicode_FromFormat("count(%R, %R)",
3049 lz
->long_cnt
, lz
->long_step
);
3053 count_reduce(countobject
*lz
)
3055 if (lz
->cnt
== PY_SSIZE_T_MAX
)
3056 return Py_BuildValue("O(OO)", Py_TYPE(lz
), lz
->long_cnt
, lz
->long_step
);
3057 return Py_BuildValue("O(n)", Py_TYPE(lz
), lz
->cnt
);
3060 PyDoc_STRVAR(count_reduce_doc
, "Return state information for pickling.");
3062 static PyMethodDef count_methods
[] = {
3063 {"__reduce__", (PyCFunction
)count_reduce
, METH_NOARGS
,
3065 {NULL
, NULL
} /* sentinel */
3068 PyDoc_STRVAR(count_doc
,
3069 "count(start=0, step=1]) --> count object\n\
3071 Return a count object whose .__next__() method returns consecutive values.\n\
3073 def count(firstval=0, step=1):\n\
3079 static PyTypeObject count_type
= {
3080 PyVarObject_HEAD_INIT(NULL
, 0)
3081 "itertools.count", /* tp_name */
3082 sizeof(countobject
), /* tp_basicsize */
3083 0, /* tp_itemsize */
3085 (destructor
)count_dealloc
, /* tp_dealloc */
3089 0, /* tp_reserved */
3090 (reprfunc
)count_repr
, /* tp_repr */
3091 0, /* tp_as_number */
3092 0, /* tp_as_sequence */
3093 0, /* tp_as_mapping */
3097 PyObject_GenericGetAttr
, /* tp_getattro */
3098 0, /* tp_setattro */
3099 0, /* tp_as_buffer */
3100 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
3101 Py_TPFLAGS_BASETYPE
, /* tp_flags */
3102 count_doc
, /* tp_doc */
3103 (traverseproc
)count_traverse
, /* tp_traverse */
3105 0, /* tp_richcompare */
3106 0, /* tp_weaklistoffset */
3107 PyObject_SelfIter
, /* tp_iter */
3108 (iternextfunc
)count_next
, /* tp_iternext */
3109 count_methods
, /* tp_methods */
3114 0, /* tp_descr_get */
3115 0, /* tp_descr_set */
3116 0, /* tp_dictoffset */
3119 count_new
, /* tp_new */
3120 PyObject_GC_Del
, /* tp_free */
3124 /* repeat object ************************************************************/
3132 static PyTypeObject repeat_type
;
3135 repeat_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
3139 Py_ssize_t cnt
= -1;
3140 static char *kwargs
[] = {"object", "times", NULL
};
3142 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "O|n:repeat", kwargs
,
3146 if (PyTuple_Size(args
) == 2 && cnt
< 0)
3149 ro
= (repeatobject
*)type
->tp_alloc(type
, 0);
3153 ro
->element
= element
;
3155 return (PyObject
*)ro
;
3159 repeat_dealloc(repeatobject
*ro
)
3161 PyObject_GC_UnTrack(ro
);
3162 Py_XDECREF(ro
->element
);
3163 Py_TYPE(ro
)->tp_free(ro
);
3167 repeat_traverse(repeatobject
*ro
, visitproc visit
, void *arg
)
3169 Py_VISIT(ro
->element
);
3174 repeat_next(repeatobject
*ro
)
3180 Py_INCREF(ro
->element
);
3185 repeat_repr(repeatobject
*ro
)
3188 return PyUnicode_FromFormat("repeat(%R)", ro
->element
);
3190 return PyUnicode_FromFormat("repeat(%R, %zd)", ro
->element
, ro
->cnt
);
3194 repeat_len(repeatobject
*ro
)
3196 if (ro
->cnt
== -1) {
3197 PyErr_SetString(PyExc_TypeError
, "len() of unsized object");
3200 return PyLong_FromSize_t(ro
->cnt
);
3203 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
3205 static PyMethodDef repeat_methods
[] = {
3206 {"__length_hint__", (PyCFunction
)repeat_len
, METH_NOARGS
, length_hint_doc
},
3207 {NULL
, NULL
} /* sentinel */
3210 PyDoc_STRVAR(repeat_doc
,
3211 "repeat(object [,times]) -> create an iterator which returns the object\n\
3212 for the specified number of times. If not specified, returns the object\n\
3215 static PyTypeObject repeat_type
= {
3216 PyVarObject_HEAD_INIT(NULL
, 0)
3217 "itertools.repeat", /* tp_name */
3218 sizeof(repeatobject
), /* tp_basicsize */
3219 0, /* tp_itemsize */
3221 (destructor
)repeat_dealloc
, /* tp_dealloc */
3225 0, /* tp_reserved */
3226 (reprfunc
)repeat_repr
, /* tp_repr */
3227 0, /* tp_as_number */
3228 0, /* tp_as_sequence */
3229 0, /* tp_as_mapping */
3233 PyObject_GenericGetAttr
, /* tp_getattro */
3234 0, /* tp_setattro */
3235 0, /* tp_as_buffer */
3236 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
3237 Py_TPFLAGS_BASETYPE
, /* tp_flags */
3238 repeat_doc
, /* tp_doc */
3239 (traverseproc
)repeat_traverse
, /* tp_traverse */
3241 0, /* tp_richcompare */
3242 0, /* tp_weaklistoffset */
3243 PyObject_SelfIter
, /* tp_iter */
3244 (iternextfunc
)repeat_next
, /* tp_iternext */
3245 repeat_methods
, /* tp_methods */
3250 0, /* tp_descr_get */
3251 0, /* tp_descr_set */
3252 0, /* tp_dictoffset */
3255 repeat_new
, /* tp_new */
3256 PyObject_GC_Del
, /* tp_free */
3259 /* ziplongest object ************************************************************/
3265 Py_ssize_t tuplesize
;
3266 Py_ssize_t numactive
;
3267 PyObject
*ittuple
; /* tuple of iterators */
3269 PyObject
*fillvalue
;
3272 static PyTypeObject ziplongest_type
;
3275 zip_longest_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
3277 ziplongestobject
*lz
;
3279 PyObject
*ittuple
; /* tuple of iterators */
3281 PyObject
*fillvalue
= Py_None
;
3282 Py_ssize_t tuplesize
= PySequence_Length(args
);
3284 if (kwds
!= NULL
&& PyDict_CheckExact(kwds
) && PyDict_Size(kwds
) > 0) {
3285 fillvalue
= PyDict_GetItemString(kwds
, "fillvalue");
3286 if (fillvalue
== NULL
|| PyDict_Size(kwds
) > 1) {
3287 PyErr_SetString(PyExc_TypeError
,
3288 "zip_longest() got an unexpected keyword argument");
3293 /* args must be a tuple */
3294 assert(PyTuple_Check(args
));
3296 /* obtain iterators */
3297 ittuple
= PyTuple_New(tuplesize
);
3298 if (ittuple
== NULL
)
3300 for (i
=0; i
< tuplesize
; ++i
) {
3301 PyObject
*item
= PyTuple_GET_ITEM(args
, i
);
3302 PyObject
*it
= PyObject_GetIter(item
);
3304 if (PyErr_ExceptionMatches(PyExc_TypeError
))
3305 PyErr_Format(PyExc_TypeError
,
3306 "zip_longest argument #%zd must support iteration",
3311 PyTuple_SET_ITEM(ittuple
, i
, it
);
3314 /* create a result holder */
3315 result
= PyTuple_New(tuplesize
);
3316 if (result
== NULL
) {
3320 for (i
=0 ; i
< tuplesize
; i
++) {
3322 PyTuple_SET_ITEM(result
, i
, Py_None
);
3325 /* create ziplongestobject structure */
3326 lz
= (ziplongestobject
*)type
->tp_alloc(type
, 0);
3332 lz
->ittuple
= ittuple
;
3333 lz
->tuplesize
= tuplesize
;
3334 lz
->numactive
= tuplesize
;
3335 lz
->result
= result
;
3336 Py_INCREF(fillvalue
);
3337 lz
->fillvalue
= fillvalue
;
3338 return (PyObject
*)lz
;
3342 zip_longest_dealloc(ziplongestobject
*lz
)
3344 PyObject_GC_UnTrack(lz
);
3345 Py_XDECREF(lz
->ittuple
);
3346 Py_XDECREF(lz
->result
);
3347 Py_XDECREF(lz
->fillvalue
);
3348 Py_TYPE(lz
)->tp_free(lz
);
3352 zip_longest_traverse(ziplongestobject
*lz
, visitproc visit
, void *arg
)
3354 Py_VISIT(lz
->ittuple
);
3355 Py_VISIT(lz
->result
);
3356 Py_VISIT(lz
->fillvalue
);
3361 zip_longest_next(ziplongestobject
*lz
)
3364 Py_ssize_t tuplesize
= lz
->tuplesize
;
3365 PyObject
*result
= lz
->result
;
3372 if (lz
->numactive
== 0)
3374 if (Py_REFCNT(result
) == 1) {
3376 for (i
=0 ; i
< tuplesize
; i
++) {
3377 it
= PyTuple_GET_ITEM(lz
->ittuple
, i
);
3379 Py_INCREF(lz
->fillvalue
);
3380 item
= lz
->fillvalue
;
3382 item
= PyIter_Next(it
);
3385 if (lz
->numactive
== 0 || PyErr_Occurred()) {
3390 Py_INCREF(lz
->fillvalue
);
3391 item
= lz
->fillvalue
;
3392 PyTuple_SET_ITEM(lz
->ittuple
, i
, NULL
);
3397 olditem
= PyTuple_GET_ITEM(result
, i
);
3398 PyTuple_SET_ITEM(result
, i
, item
);
3402 result
= PyTuple_New(tuplesize
);
3405 for (i
=0 ; i
< tuplesize
; i
++) {
3406 it
= PyTuple_GET_ITEM(lz
->ittuple
, i
);
3408 Py_INCREF(lz
->fillvalue
);
3409 item
= lz
->fillvalue
;
3411 item
= PyIter_Next(it
);
3414 if (lz
->numactive
== 0 || PyErr_Occurred()) {
3419 Py_INCREF(lz
->fillvalue
);
3420 item
= lz
->fillvalue
;
3421 PyTuple_SET_ITEM(lz
->ittuple
, i
, NULL
);
3426 PyTuple_SET_ITEM(result
, i
, item
);
3432 PyDoc_STRVAR(zip_longest_doc
,
3433 "zip_longest(iter1 [,iter2 [...]], [fillvalue=None]) --> zip_longest object\n\
3435 Return an zip_longest object whose .__next__() method returns a tuple where\n\
3436 the i-th element comes from the i-th iterable argument. The .__next__()\n\
3437 method continues until the longest iterable in the argument sequence\n\
3438 is exhausted and then it raises StopIteration. When the shorter iterables\n\
3439 are exhausted, the fillvalue is substituted in their place. The fillvalue\n\
3440 defaults to None or can be specified by a keyword argument.\n\
3443 static PyTypeObject ziplongest_type
= {
3444 PyVarObject_HEAD_INIT(NULL
, 0)
3445 "itertools.zip_longest", /* tp_name */
3446 sizeof(ziplongestobject
), /* tp_basicsize */
3447 0, /* tp_itemsize */
3449 (destructor
)zip_longest_dealloc
, /* tp_dealloc */
3453 0, /* tp_reserved */
3455 0, /* tp_as_number */
3456 0, /* tp_as_sequence */
3457 0, /* tp_as_mapping */
3461 PyObject_GenericGetAttr
, /* tp_getattro */
3462 0, /* tp_setattro */
3463 0, /* tp_as_buffer */
3464 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
3465 Py_TPFLAGS_BASETYPE
, /* tp_flags */
3466 zip_longest_doc
, /* tp_doc */
3467 (traverseproc
)zip_longest_traverse
, /* tp_traverse */
3469 0, /* tp_richcompare */
3470 0, /* tp_weaklistoffset */
3471 PyObject_SelfIter
, /* tp_iter */
3472 (iternextfunc
)zip_longest_next
, /* tp_iternext */
3478 0, /* tp_descr_get */
3479 0, /* tp_descr_set */
3480 0, /* tp_dictoffset */
3483 zip_longest_new
, /* tp_new */
3484 PyObject_GC_Del
, /* tp_free */
3487 /* module level code ********************************************************/
3489 PyDoc_STRVAR(module_doc
,
3490 "Functional tools for creating and using iterators.\n\
3492 Infinite iterators:\n\
3493 count([n]) --> n, n+1, n+2, ...\n\
3494 cycle(p) --> p0, p1, ... plast, p0, p1, ...\n\
3495 repeat(elem [,n]) --> elem, elem, elem, ... endlessly or up to n times\n\
3497 Iterators terminating on the shortest input sequence:\n\
3498 chain(p, q, ...) --> p0, p1, ... plast, q0, q1, ... \n\
3499 compress(data, selectors) --> (d[0] if s[0]), (d[1] if s[1]), ...\n\
3500 dropwhile(pred, seq) --> seq[n], seq[n+1], starting when pred fails\n\
3501 groupby(iterable[, keyfunc]) --> sub-iterators grouped by value of keyfunc(v)\n\
3502 filterfalse(pred, seq) --> elements of seq where pred(elem) is False\n\
3503 islice(seq, [start,] stop [, step]) --> elements from\n\
3504 seq[start:stop:step]\n\
3505 starmap(fun, seq) --> fun(*seq[0]), fun(*seq[1]), ...\n\
3506 tee(it, n=2) --> (it1, it2 , ... itn) splits one iterator into n\n\
3507 takewhile(pred, seq) --> seq[0], seq[1], until pred fails\n\
3508 zip_longest(p, q, ...) --> (p[0], q[0]), (p[1], q[1]), ... \n\
3510 Combinatoric generators:\n\
3511 product(p, q, ... [repeat=1]) --> cartesian product\n\
3512 permutations(p[, r])\n\
3513 combinations(p, r)\n\
3514 combinations_with_replacement(p, r)\n\
3518 static PyMethodDef module_methods
[] = {
3519 {"tee", (PyCFunction
)tee
, METH_VARARGS
, tee_doc
},
3520 {NULL
, NULL
} /* sentinel */
3524 static struct PyModuleDef itertoolsmodule
= {
3525 PyModuleDef_HEAD_INIT
,
3537 PyInit_itertools(void)
3542 PyTypeObject
*typelist
[] = {
3562 Py_TYPE(&teedataobject_type
) = &PyType_Type
;
3563 m
= PyModule_Create(&itertoolsmodule
);
3567 for (i
=0 ; typelist
[i
] != NULL
; i
++) {
3568 if (PyType_Ready(typelist
[i
]) < 0)
3570 name
= strchr(typelist
[i
]->tp_name
, '.');
3571 assert (name
!= NULL
);
3572 Py_INCREF(typelist
[i
]);
3573 PyModule_AddObject(m
, name
+1, (PyObject
*)typelist
[i
]);
3576 if (PyType_Ready(&teedataobject_type
) < 0)
3578 if (PyType_Ready(&tee_type
) < 0)
3580 if (PyType_Ready(&_grouper_type
) < 0)