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
);
749 PyList_Append(lz
->saved
, item
);
752 if (PyErr_Occurred()) {
753 if (PyErr_ExceptionMatches(PyExc_StopIteration
))
758 if (PyList_Size(lz
->saved
) == 0)
760 it
= PyObject_GetIter(lz
->saved
);
770 PyDoc_STRVAR(cycle_doc
,
771 "cycle(iterable) --> cycle object\n\
773 Return elements from the iterable until it is exhausted.\n\
774 Then repeat the sequence indefinitely.");
776 static PyTypeObject cycle_type
= {
777 PyVarObject_HEAD_INIT(NULL
, 0)
778 "itertools.cycle", /* tp_name */
779 sizeof(cycleobject
), /* tp_basicsize */
782 (destructor
)cycle_dealloc
, /* tp_dealloc */
788 0, /* tp_as_number */
789 0, /* tp_as_sequence */
790 0, /* tp_as_mapping */
794 PyObject_GenericGetAttr
, /* tp_getattro */
796 0, /* tp_as_buffer */
797 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
798 Py_TPFLAGS_BASETYPE
, /* tp_flags */
799 cycle_doc
, /* tp_doc */
800 (traverseproc
)cycle_traverse
, /* tp_traverse */
802 0, /* tp_richcompare */
803 0, /* tp_weaklistoffset */
804 PyObject_SelfIter
, /* tp_iter */
805 (iternextfunc
)cycle_next
, /* tp_iternext */
811 0, /* tp_descr_get */
812 0, /* tp_descr_set */
813 0, /* tp_dictoffset */
816 cycle_new
, /* tp_new */
817 PyObject_GC_Del
, /* tp_free */
821 /* dropwhile object **********************************************************/
830 static PyTypeObject dropwhile_type
;
833 dropwhile_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
835 PyObject
*func
, *seq
;
839 if (type
== &dropwhile_type
&& !_PyArg_NoKeywords("dropwhile()", kwds
))
842 if (!PyArg_UnpackTuple(args
, "dropwhile", 2, 2, &func
, &seq
))
846 it
= PyObject_GetIter(seq
);
850 /* create dropwhileobject structure */
851 lz
= (dropwhileobject
*)type
->tp_alloc(type
, 0);
861 return (PyObject
*)lz
;
865 dropwhile_dealloc(dropwhileobject
*lz
)
867 PyObject_GC_UnTrack(lz
);
868 Py_XDECREF(lz
->func
);
870 Py_TYPE(lz
)->tp_free(lz
);
874 dropwhile_traverse(dropwhileobject
*lz
, visitproc visit
, void *arg
)
882 dropwhile_next(dropwhileobject
*lz
)
884 PyObject
*item
, *good
;
885 PyObject
*it
= lz
->it
;
887 PyObject
*(*iternext
)(PyObject
*);
889 assert(PyIter_Check(it
));
890 iternext
= *Py_TYPE(it
)->tp_iternext
;
898 good
= PyObject_CallFunctionObjArgs(lz
->func
, item
, NULL
);
903 ok
= PyObject_IsTrue(good
);
913 PyDoc_STRVAR(dropwhile_doc
,
914 "dropwhile(predicate, iterable) --> dropwhile object\n\
916 Drop items from the iterable while predicate(item) is true.\n\
917 Afterwards, return every element until the iterable is exhausted.");
919 static PyTypeObject dropwhile_type
= {
920 PyVarObject_HEAD_INIT(NULL
, 0)
921 "itertools.dropwhile", /* tp_name */
922 sizeof(dropwhileobject
), /* tp_basicsize */
925 (destructor
)dropwhile_dealloc
, /* tp_dealloc */
931 0, /* tp_as_number */
932 0, /* tp_as_sequence */
933 0, /* tp_as_mapping */
937 PyObject_GenericGetAttr
, /* tp_getattro */
939 0, /* tp_as_buffer */
940 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
941 Py_TPFLAGS_BASETYPE
, /* tp_flags */
942 dropwhile_doc
, /* tp_doc */
943 (traverseproc
)dropwhile_traverse
, /* tp_traverse */
945 0, /* tp_richcompare */
946 0, /* tp_weaklistoffset */
947 PyObject_SelfIter
, /* tp_iter */
948 (iternextfunc
)dropwhile_next
, /* tp_iternext */
954 0, /* tp_descr_get */
955 0, /* tp_descr_set */
956 0, /* tp_dictoffset */
959 dropwhile_new
, /* tp_new */
960 PyObject_GC_Del
, /* tp_free */
964 /* takewhile object **********************************************************/
973 static PyTypeObject takewhile_type
;
976 takewhile_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
978 PyObject
*func
, *seq
;
982 if (type
== &takewhile_type
&& !_PyArg_NoKeywords("takewhile()", kwds
))
985 if (!PyArg_UnpackTuple(args
, "takewhile", 2, 2, &func
, &seq
))
989 it
= PyObject_GetIter(seq
);
993 /* create takewhileobject structure */
994 lz
= (takewhileobject
*)type
->tp_alloc(type
, 0);
1004 return (PyObject
*)lz
;
1008 takewhile_dealloc(takewhileobject
*lz
)
1010 PyObject_GC_UnTrack(lz
);
1011 Py_XDECREF(lz
->func
);
1013 Py_TYPE(lz
)->tp_free(lz
);
1017 takewhile_traverse(takewhileobject
*lz
, visitproc visit
, void *arg
)
1025 takewhile_next(takewhileobject
*lz
)
1027 PyObject
*item
, *good
;
1028 PyObject
*it
= lz
->it
;
1034 assert(PyIter_Check(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 */
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
= PyInt_AsSsize_t(a1
);
1137 if (PyErr_Occurred())
1139 PyErr_SetString(PyExc_ValueError
,
1140 "Stop argument for islice() must be a non-negative integer or None.");
1146 start
= PyInt_AsSsize_t(a1
);
1147 if (start
== -1 && PyErr_Occurred())
1149 if (a2
!= Py_None
) {
1150 stop
= PyInt_AsSsize_t(a2
);
1152 if (PyErr_Occurred())
1154 PyErr_SetString(PyExc_ValueError
,
1155 "Stop argument for islice() must be a non-negative integer or None.");
1160 if (start
<0 || stop
<-1) {
1161 PyErr_SetString(PyExc_ValueError
,
1162 "Indices for islice() must be non-negative integers or None.");
1168 step
= PyInt_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 assert(PyIter_Check(it
));
1222 iternext
= *Py_TYPE(it
)->tp_iternext
;
1223 while (lz
->cnt
< lz
->next
) {
1224 item
= iternext(it
);
1230 if (lz
->stop
!= -1 && lz
->cnt
>= lz
->stop
)
1232 assert(PyIter_Check(it
));
1233 item
= iternext(it
);
1238 lz
->next
+= lz
->step
;
1239 if (lz
->next
< oldnext
) /* Check for overflow */
1240 lz
->next
= lz
->stop
;
1244 PyDoc_STRVAR(islice_doc
,
1245 "islice(iterable, [start,] stop [, step]) --> islice object\n\
1247 Return an iterator whose next() method returns selected values from an\n\
1248 iterable. If start is specified, will skip all preceding elements;\n\
1249 otherwise, start defaults to zero. Step defaults to one. If\n\
1250 specified as another value, step determines how many values are \n\
1251 skipped between successive calls. Works like a slice() on a list\n\
1252 but returns an iterator.");
1254 static PyTypeObject islice_type
= {
1255 PyVarObject_HEAD_INIT(NULL
, 0)
1256 "itertools.islice", /* tp_name */
1257 sizeof(isliceobject
), /* tp_basicsize */
1258 0, /* tp_itemsize */
1260 (destructor
)islice_dealloc
, /* tp_dealloc */
1266 0, /* tp_as_number */
1267 0, /* tp_as_sequence */
1268 0, /* tp_as_mapping */
1272 PyObject_GenericGetAttr
, /* tp_getattro */
1273 0, /* tp_setattro */
1274 0, /* tp_as_buffer */
1275 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1276 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1277 islice_doc
, /* tp_doc */
1278 (traverseproc
)islice_traverse
, /* tp_traverse */
1280 0, /* tp_richcompare */
1281 0, /* tp_weaklistoffset */
1282 PyObject_SelfIter
, /* tp_iter */
1283 (iternextfunc
)islice_next
, /* tp_iternext */
1289 0, /* tp_descr_get */
1290 0, /* tp_descr_set */
1291 0, /* tp_dictoffset */
1294 islice_new
, /* tp_new */
1295 PyObject_GC_Del
, /* tp_free */
1299 /* starmap object ************************************************************/
1307 static PyTypeObject starmap_type
;
1310 starmap_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1312 PyObject
*func
, *seq
;
1316 if (type
== &starmap_type
&& !_PyArg_NoKeywords("starmap()", kwds
))
1319 if (!PyArg_UnpackTuple(args
, "starmap", 2, 2, &func
, &seq
))
1323 it
= PyObject_GetIter(seq
);
1327 /* create starmapobject structure */
1328 lz
= (starmapobject
*)type
->tp_alloc(type
, 0);
1337 return (PyObject
*)lz
;
1341 starmap_dealloc(starmapobject
*lz
)
1343 PyObject_GC_UnTrack(lz
);
1344 Py_XDECREF(lz
->func
);
1346 Py_TYPE(lz
)->tp_free(lz
);
1350 starmap_traverse(starmapobject
*lz
, visitproc visit
, void *arg
)
1358 starmap_next(starmapobject
*lz
)
1362 PyObject
*it
= lz
->it
;
1364 assert(PyIter_Check(it
));
1365 args
= (*Py_TYPE(it
)->tp_iternext
)(it
);
1368 if (!PyTuple_CheckExact(args
)) {
1369 PyObject
*newargs
= PySequence_Tuple(args
);
1371 if (newargs
== NULL
)
1375 result
= PyObject_Call(lz
->func
, args
, NULL
);
1380 PyDoc_STRVAR(starmap_doc
,
1381 "starmap(function, sequence) --> starmap object\n\
1383 Return an iterator whose values are returned from the function evaluated\n\
1384 with a argument tuple taken from the given sequence.");
1386 static PyTypeObject starmap_type
= {
1387 PyVarObject_HEAD_INIT(NULL
, 0)
1388 "itertools.starmap", /* tp_name */
1389 sizeof(starmapobject
), /* tp_basicsize */
1390 0, /* tp_itemsize */
1392 (destructor
)starmap_dealloc
, /* tp_dealloc */
1398 0, /* tp_as_number */
1399 0, /* tp_as_sequence */
1400 0, /* tp_as_mapping */
1404 PyObject_GenericGetAttr
, /* tp_getattro */
1405 0, /* tp_setattro */
1406 0, /* tp_as_buffer */
1407 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1408 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1409 starmap_doc
, /* tp_doc */
1410 (traverseproc
)starmap_traverse
, /* tp_traverse */
1412 0, /* tp_richcompare */
1413 0, /* tp_weaklistoffset */
1414 PyObject_SelfIter
, /* tp_iter */
1415 (iternextfunc
)starmap_next
, /* tp_iternext */
1421 0, /* tp_descr_get */
1422 0, /* tp_descr_set */
1423 0, /* tp_dictoffset */
1426 starmap_new
, /* tp_new */
1427 PyObject_GC_Del
, /* tp_free */
1431 /* imap object ************************************************************/
1439 static PyTypeObject imap_type
;
1442 imap_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1444 PyObject
*it
, *iters
, *func
;
1446 Py_ssize_t numargs
, i
;
1448 if (type
== &imap_type
&& !_PyArg_NoKeywords("imap()", kwds
))
1451 numargs
= PyTuple_Size(args
);
1453 PyErr_SetString(PyExc_TypeError
,
1454 "imap() must have at least two arguments.");
1458 iters
= PyTuple_New(numargs
-1);
1462 for (i
=1 ; i
<numargs
; i
++) {
1464 it
= PyObject_GetIter(PyTuple_GET_ITEM(args
, i
));
1469 PyTuple_SET_ITEM(iters
, i
-1, it
);
1472 /* create imapobject structure */
1473 lz
= (imapobject
*)type
->tp_alloc(type
, 0);
1479 func
= PyTuple_GET_ITEM(args
, 0);
1483 return (PyObject
*)lz
;
1487 imap_dealloc(imapobject
*lz
)
1489 PyObject_GC_UnTrack(lz
);
1490 Py_XDECREF(lz
->iters
);
1491 Py_XDECREF(lz
->func
);
1492 Py_TYPE(lz
)->tp_free(lz
);
1496 imap_traverse(imapobject
*lz
, visitproc visit
, void *arg
)
1498 Py_VISIT(lz
->iters
);
1504 imap() is an iterator version of __builtins__.map() except that it does
1505 not have the None fill-in feature. That was intentionally left out for
1506 the following reasons:
1508 1) Itertools are designed to be easily combined and chained together.
1509 Having all tools stop with the shortest input is a unifying principle
1510 that makes it easier to combine finite iterators (supplying data) with
1511 infinite iterators like count() and repeat() (for supplying sequential
1512 or constant arguments to a function).
1514 2) In typical use cases for combining itertools, having one finite data
1515 supplier run out before another is likely to be an error condition which
1516 should not pass silently by automatically supplying None.
1518 3) The use cases for automatic None fill-in are rare -- not many functions
1519 do something useful when a parameter suddenly switches type and becomes
1522 4) If a need does arise, it can be met by __builtins__.map() or by
1523 writing: chain(iterable, repeat(None)).
1525 5) Similar toolsets in Haskell and SML do not have automatic None fill-in.
1529 imap_next(imapobject
*lz
)
1534 Py_ssize_t numargs
, i
;
1536 numargs
= PyTuple_Size(lz
->iters
);
1537 argtuple
= PyTuple_New(numargs
);
1538 if (argtuple
== NULL
)
1541 for (i
=0 ; i
<numargs
; i
++) {
1542 val
= PyIter_Next(PyTuple_GET_ITEM(lz
->iters
, i
));
1544 Py_DECREF(argtuple
);
1547 PyTuple_SET_ITEM(argtuple
, i
, val
);
1549 if (lz
->func
== Py_None
)
1551 result
= PyObject_Call(lz
->func
, argtuple
, NULL
);
1552 Py_DECREF(argtuple
);
1556 PyDoc_STRVAR(imap_doc
,
1557 "imap(func, *iterables) --> imap object\n\
1559 Make an iterator that computes the function using arguments from\n\
1560 each of the iterables. Like map() except that it returns\n\
1561 an iterator instead of a list and that it stops when the shortest\n\
1562 iterable is exhausted instead of filling in None for shorter\n\
1565 static PyTypeObject imap_type
= {
1566 PyVarObject_HEAD_INIT(NULL
, 0)
1567 "itertools.imap", /* tp_name */
1568 sizeof(imapobject
), /* tp_basicsize */
1569 0, /* tp_itemsize */
1571 (destructor
)imap_dealloc
, /* tp_dealloc */
1577 0, /* tp_as_number */
1578 0, /* tp_as_sequence */
1579 0, /* tp_as_mapping */
1583 PyObject_GenericGetAttr
, /* tp_getattro */
1584 0, /* tp_setattro */
1585 0, /* tp_as_buffer */
1586 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1587 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1588 imap_doc
, /* tp_doc */
1589 (traverseproc
)imap_traverse
, /* tp_traverse */
1591 0, /* tp_richcompare */
1592 0, /* tp_weaklistoffset */
1593 PyObject_SelfIter
, /* tp_iter */
1594 (iternextfunc
)imap_next
, /* tp_iternext */
1600 0, /* tp_descr_get */
1601 0, /* tp_descr_set */
1602 0, /* tp_dictoffset */
1605 imap_new
, /* tp_new */
1606 PyObject_GC_Del
, /* tp_free */
1610 /* chain object ************************************************************/
1614 PyObject
*source
; /* Iterator over input iterables */
1615 PyObject
*active
; /* Currently running input iterator */
1618 static PyTypeObject chain_type
;
1621 chain_new_internal(PyTypeObject
*type
, PyObject
*source
)
1625 lz
= (chainobject
*)type
->tp_alloc(type
, 0);
1631 lz
->source
= source
;
1633 return (PyObject
*)lz
;
1637 chain_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1641 if (type
== &chain_type
&& !_PyArg_NoKeywords("chain()", kwds
))
1644 source
= PyObject_GetIter(args
);
1648 return chain_new_internal(type
, source
);
1652 chain_new_from_iterable(PyTypeObject
*type
, PyObject
*arg
)
1656 source
= PyObject_GetIter(arg
);
1660 return chain_new_internal(type
, source
);
1664 chain_dealloc(chainobject
*lz
)
1666 PyObject_GC_UnTrack(lz
);
1667 Py_XDECREF(lz
->active
);
1668 Py_XDECREF(lz
->source
);
1669 Py_TYPE(lz
)->tp_free(lz
);
1673 chain_traverse(chainobject
*lz
, visitproc visit
, void *arg
)
1675 Py_VISIT(lz
->source
);
1676 Py_VISIT(lz
->active
);
1681 chain_next(chainobject
*lz
)
1685 if (lz
->source
== NULL
)
1686 return NULL
; /* already stopped */
1688 if (lz
->active
== NULL
) {
1689 PyObject
*iterable
= PyIter_Next(lz
->source
);
1690 if (iterable
== NULL
) {
1691 Py_CLEAR(lz
->source
);
1692 return NULL
; /* no more input sources */
1694 lz
->active
= PyObject_GetIter(iterable
);
1695 Py_DECREF(iterable
);
1696 if (lz
->active
== NULL
) {
1697 Py_CLEAR(lz
->source
);
1698 return NULL
; /* input not iterable */
1701 item
= PyIter_Next(lz
->active
);
1704 if (PyErr_Occurred()) {
1705 if (PyErr_ExceptionMatches(PyExc_StopIteration
))
1708 return NULL
; /* input raised an exception */
1710 Py_CLEAR(lz
->active
);
1711 return chain_next(lz
); /* recurse and use next active */
1714 PyDoc_STRVAR(chain_doc
,
1715 "chain(*iterables) --> chain object\n\
1717 Return a chain object whose .next() method returns elements from the\n\
1718 first iterable until it is exhausted, then elements from the next\n\
1719 iterable, until all of the iterables are exhausted.");
1721 PyDoc_STRVAR(chain_from_iterable_doc
,
1722 "chain.from_iterable(iterable) --> chain object\n\
1724 Alternate chain() contructor taking a single iterable argument\n\
1725 that evaluates lazily.");
1727 static PyMethodDef chain_methods
[] = {
1728 {"from_iterable", (PyCFunction
) chain_new_from_iterable
, METH_O
| METH_CLASS
,
1729 chain_from_iterable_doc
},
1730 {NULL
, NULL
} /* sentinel */
1733 static PyTypeObject chain_type
= {
1734 PyVarObject_HEAD_INIT(NULL
, 0)
1735 "itertools.chain", /* tp_name */
1736 sizeof(chainobject
), /* tp_basicsize */
1737 0, /* tp_itemsize */
1739 (destructor
)chain_dealloc
, /* tp_dealloc */
1745 0, /* tp_as_number */
1746 0, /* tp_as_sequence */
1747 0, /* tp_as_mapping */
1751 PyObject_GenericGetAttr
, /* tp_getattro */
1752 0, /* tp_setattro */
1753 0, /* tp_as_buffer */
1754 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1755 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1756 chain_doc
, /* tp_doc */
1757 (traverseproc
)chain_traverse
, /* tp_traverse */
1759 0, /* tp_richcompare */
1760 0, /* tp_weaklistoffset */
1761 PyObject_SelfIter
, /* tp_iter */
1762 (iternextfunc
)chain_next
, /* tp_iternext */
1763 chain_methods
, /* tp_methods */
1768 0, /* tp_descr_get */
1769 0, /* tp_descr_set */
1770 0, /* tp_dictoffset */
1773 chain_new
, /* tp_new */
1774 PyObject_GC_Del
, /* tp_free */
1778 /* product object ************************************************************/
1782 PyObject
*pools
; /* tuple of pool tuples */
1783 Py_ssize_t
*indices
; /* one index per pool */
1784 PyObject
*result
; /* most recently returned result tuple */
1785 int stopped
; /* set to 1 when the product iterator is exhausted */
1788 static PyTypeObject product_type
;
1791 product_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1794 Py_ssize_t nargs
, npools
, repeat
=1;
1795 PyObject
*pools
= NULL
;
1796 Py_ssize_t
*indices
= NULL
;
1800 char *kwlist
[] = {"repeat", 0};
1801 PyObject
*tmpargs
= PyTuple_New(0);
1802 if (tmpargs
== NULL
)
1804 if (!PyArg_ParseTupleAndKeywords(tmpargs
, kwds
, "|n:product", kwlist
, &repeat
)) {
1810 PyErr_SetString(PyExc_ValueError
,
1811 "repeat argument cannot be negative");
1816 assert(PyTuple_Check(args
));
1817 nargs
= (repeat
== 0) ? 0 : PyTuple_GET_SIZE(args
);
1818 npools
= nargs
* repeat
;
1820 indices
= PyMem_Malloc(npools
* sizeof(Py_ssize_t
));
1821 if (indices
== NULL
) {
1826 pools
= PyTuple_New(npools
);
1830 for (i
=0; i
< nargs
; ++i
) {
1831 PyObject
*item
= PyTuple_GET_ITEM(args
, i
);
1832 PyObject
*pool
= PySequence_Tuple(item
);
1835 PyTuple_SET_ITEM(pools
, i
, pool
);
1838 for ( ; i
< npools
; ++i
) {
1839 PyObject
*pool
= PyTuple_GET_ITEM(pools
, i
- nargs
);
1841 PyTuple_SET_ITEM(pools
, i
, pool
);
1845 /* create productobject structure */
1846 lz
= (productobject
*)type
->tp_alloc(type
, 0);
1851 lz
->indices
= indices
;
1855 return (PyObject
*)lz
;
1858 if (indices
!= NULL
)
1859 PyMem_Free(indices
);
1865 product_dealloc(productobject
*lz
)
1867 PyObject_GC_UnTrack(lz
);
1868 Py_XDECREF(lz
->pools
);
1869 Py_XDECREF(lz
->result
);
1870 PyMem_Free(lz
->indices
);
1871 Py_TYPE(lz
)->tp_free(lz
);
1875 product_traverse(productobject
*lz
, visitproc visit
, void *arg
)
1877 Py_VISIT(lz
->pools
);
1878 Py_VISIT(lz
->result
);
1883 product_next(productobject
*lz
)
1888 PyObject
*pools
= lz
->pools
;
1889 PyObject
*result
= lz
->result
;
1890 Py_ssize_t npools
= PyTuple_GET_SIZE(pools
);
1896 if (result
== NULL
) {
1897 /* On the first pass, return an initial tuple filled with the
1898 first element from each pool. */
1899 result
= PyTuple_New(npools
);
1902 lz
->result
= result
;
1903 for (i
=0; i
< npools
; i
++) {
1904 pool
= PyTuple_GET_ITEM(pools
, i
);
1905 if (PyTuple_GET_SIZE(pool
) == 0)
1907 elem
= PyTuple_GET_ITEM(pool
, 0);
1909 PyTuple_SET_ITEM(result
, i
, elem
);
1912 Py_ssize_t
*indices
= lz
->indices
;
1914 /* Copy the previous result tuple or re-use it if available */
1915 if (Py_REFCNT(result
) > 1) {
1916 PyObject
*old_result
= result
;
1917 result
= PyTuple_New(npools
);
1920 lz
->result
= result
;
1921 for (i
=0; i
< npools
; i
++) {
1922 elem
= PyTuple_GET_ITEM(old_result
, i
);
1924 PyTuple_SET_ITEM(result
, i
, elem
);
1926 Py_DECREF(old_result
);
1928 /* Now, we've got the only copy so we can update it in-place */
1929 assert (npools
==0 || Py_REFCNT(result
) == 1);
1931 /* Update the pool indices right-to-left. Only advance to the
1932 next pool when the previous one rolls-over */
1933 for (i
=npools
-1 ; i
>= 0 ; i
--) {
1934 pool
= PyTuple_GET_ITEM(pools
, i
);
1936 if (indices
[i
] == PyTuple_GET_SIZE(pool
)) {
1937 /* Roll-over and advance to next pool */
1939 elem
= PyTuple_GET_ITEM(pool
, 0);
1941 oldelem
= PyTuple_GET_ITEM(result
, i
);
1942 PyTuple_SET_ITEM(result
, i
, elem
);
1945 /* No rollover. Just increment and stop here. */
1946 elem
= PyTuple_GET_ITEM(pool
, indices
[i
]);
1948 oldelem
= PyTuple_GET_ITEM(result
, i
);
1949 PyTuple_SET_ITEM(result
, i
, elem
);
1955 /* If i is negative, then the indices have all rolled-over
1969 PyDoc_STRVAR(product_doc
,
1970 "product(*iterables) --> product object\n\
1972 Cartesian product of input iterables. Equivalent to nested for-loops.\n\n\
1973 For example, product(A, B) returns the same as: ((x,y) for x in A for y in B).\n\
1974 The leftmost iterators are in the outermost for-loop, so the output tuples\n\
1975 cycle in a manner similar to an odometer (with the rightmost element changing\n\
1976 on every iteration).\n\n\
1977 product('ab', range(3)) --> ('a',0) ('a',1) ('a',2) ('b',0) ('b',1) ('b',2)\n\
1978 product((0,1), (0,1), (0,1)) --> (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) ...");
1980 static PyTypeObject product_type
= {
1981 PyVarObject_HEAD_INIT(NULL
, 0)
1982 "itertools.product", /* tp_name */
1983 sizeof(productobject
), /* tp_basicsize */
1984 0, /* tp_itemsize */
1986 (destructor
)product_dealloc
, /* tp_dealloc */
1992 0, /* tp_as_number */
1993 0, /* tp_as_sequence */
1994 0, /* tp_as_mapping */
1998 PyObject_GenericGetAttr
, /* tp_getattro */
1999 0, /* tp_setattro */
2000 0, /* tp_as_buffer */
2001 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2002 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2003 product_doc
, /* tp_doc */
2004 (traverseproc
)product_traverse
, /* tp_traverse */
2006 0, /* tp_richcompare */
2007 0, /* tp_weaklistoffset */
2008 PyObject_SelfIter
, /* tp_iter */
2009 (iternextfunc
)product_next
, /* tp_iternext */
2015 0, /* tp_descr_get */
2016 0, /* tp_descr_set */
2017 0, /* tp_dictoffset */
2020 product_new
, /* tp_new */
2021 PyObject_GC_Del
, /* tp_free */
2025 /* combinations object ************************************************************/
2029 PyObject
*pool
; /* input converted to a tuple */
2030 Py_ssize_t
*indices
; /* one index per result element */
2031 PyObject
*result
; /* most recently returned result tuple */
2032 Py_ssize_t r
; /* size of result tuple */
2033 int stopped
; /* set to 1 when the combinations iterator is exhausted */
2034 } combinationsobject
;
2036 static PyTypeObject combinations_type
;
2039 combinations_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2041 combinationsobject
*co
;
2044 PyObject
*pool
= NULL
;
2045 PyObject
*iterable
= NULL
;
2046 Py_ssize_t
*indices
= NULL
;
2048 static char *kwargs
[] = {"iterable", "r", NULL
};
2050 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "On:combinations", kwargs
,
2054 pool
= PySequence_Tuple(iterable
);
2057 n
= PyTuple_GET_SIZE(pool
);
2059 PyErr_SetString(PyExc_ValueError
, "r must be non-negative");
2063 PyErr_SetString(PyExc_ValueError
, "r cannot be bigger than the iterable");
2067 indices
= PyMem_Malloc(r
* sizeof(Py_ssize_t
));
2068 if (indices
== NULL
) {
2073 for (i
=0 ; i
<r
; i
++)
2076 /* create combinationsobject structure */
2077 co
= (combinationsobject
*)type
->tp_alloc(type
, 0);
2082 co
->indices
= indices
;
2087 return (PyObject
*)co
;
2090 if (indices
!= NULL
)
2091 PyMem_Free(indices
);
2097 combinations_dealloc(combinationsobject
*co
)
2099 PyObject_GC_UnTrack(co
);
2100 Py_XDECREF(co
->pool
);
2101 Py_XDECREF(co
->result
);
2102 PyMem_Free(co
->indices
);
2103 Py_TYPE(co
)->tp_free(co
);
2107 combinations_traverse(combinationsobject
*co
, visitproc visit
, void *arg
)
2110 Py_VISIT(co
->result
);
2115 combinations_next(combinationsobject
*co
)
2119 PyObject
*pool
= co
->pool
;
2120 Py_ssize_t
*indices
= co
->indices
;
2121 PyObject
*result
= co
->result
;
2122 Py_ssize_t n
= PyTuple_GET_SIZE(pool
);
2123 Py_ssize_t r
= co
->r
;
2124 Py_ssize_t i
, j
, index
;
2129 if (result
== NULL
) {
2130 /* On the first pass, initialize result tuple using the indices */
2131 result
= PyTuple_New(r
);
2134 co
->result
= result
;
2135 for (i
=0; i
<r
; i
++) {
2137 elem
= PyTuple_GET_ITEM(pool
, index
);
2139 PyTuple_SET_ITEM(result
, i
, elem
);
2142 /* Copy the previous result tuple or re-use it if available */
2143 if (Py_REFCNT(result
) > 1) {
2144 PyObject
*old_result
= result
;
2145 result
= PyTuple_New(r
);
2148 co
->result
= result
;
2149 for (i
=0; i
<r
; i
++) {
2150 elem
= PyTuple_GET_ITEM(old_result
, i
);
2152 PyTuple_SET_ITEM(result
, i
, elem
);
2154 Py_DECREF(old_result
);
2156 /* Now, we've got the only copy so we can update it in-place
2157 * CPython's empty tuple is a singleton and cached in
2158 * PyTuple's freelist.
2160 assert(r
== 0 || Py_REFCNT(result
) == 1);
2162 /* Scan indices right-to-left until finding one that is not
2163 at its maximum (i + n - r). */
2164 for (i
=r
-1 ; i
>= 0 && indices
[i
] == i
+n
-r
; i
--)
2167 /* If i is negative, then the indices are all at
2168 their maximum value and we're done. */
2172 /* Increment the current index which we know is not at its
2173 maximum. Then move back to the right setting each index
2174 to its lowest possible value (one higher than the index
2175 to its left -- this maintains the sort order invariant). */
2177 for (j
=i
+1 ; j
<r
; j
++)
2178 indices
[j
] = indices
[j
-1] + 1;
2180 /* Update the result tuple for the new indices
2181 starting with i, the leftmost index that changed */
2182 for ( ; i
<r
; i
++) {
2184 elem
= PyTuple_GET_ITEM(pool
, index
);
2186 oldelem
= PyTuple_GET_ITEM(result
, i
);
2187 PyTuple_SET_ITEM(result
, i
, elem
);
2200 PyDoc_STRVAR(combinations_doc
,
2201 "combinations(iterable[, r]) --> combinations object\n\
2203 Return successive r-length combinations of elements in the iterable.\n\n\
2204 combinations(range(4), 3) --> (0,1,2), (0,1,3), (0,2,3), (1,2,3)");
2206 static PyTypeObject combinations_type
= {
2207 PyVarObject_HEAD_INIT(NULL
, 0)
2208 "itertools.combinations", /* tp_name */
2209 sizeof(combinationsobject
), /* tp_basicsize */
2210 0, /* tp_itemsize */
2212 (destructor
)combinations_dealloc
, /* tp_dealloc */
2218 0, /* tp_as_number */
2219 0, /* tp_as_sequence */
2220 0, /* tp_as_mapping */
2224 PyObject_GenericGetAttr
, /* tp_getattro */
2225 0, /* tp_setattro */
2226 0, /* tp_as_buffer */
2227 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2228 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2229 combinations_doc
, /* tp_doc */
2230 (traverseproc
)combinations_traverse
, /* tp_traverse */
2232 0, /* tp_richcompare */
2233 0, /* tp_weaklistoffset */
2234 PyObject_SelfIter
, /* tp_iter */
2235 (iternextfunc
)combinations_next
, /* tp_iternext */
2241 0, /* tp_descr_get */
2242 0, /* tp_descr_set */
2243 0, /* tp_dictoffset */
2246 combinations_new
, /* tp_new */
2247 PyObject_GC_Del
, /* tp_free */
2251 /* permutations object ************************************************************
2253 def permutations(iterable, r=None):
2254 'permutations(range(3), 2) --> (0,1) (0,2) (1,0) (1,2) (2,0) (2,1)'
2255 pool = tuple(iterable)
2257 r = n if r is None else r
2259 cycles = range(n-r+1, n+1)[::-1]
2260 yield tuple(pool[i] for i in indices[:r])
2262 for i in reversed(range(r)):
2265 indices[i:] = indices[i+1:] + indices[i:i+1]
2269 indices[i], indices[-j] = indices[-j], indices[i]
2270 yield tuple(pool[i] for i in indices[:r])
2278 PyObject
*pool
; /* input converted to a tuple */
2279 Py_ssize_t
*indices
; /* one index per element in the pool */
2280 Py_ssize_t
*cycles
; /* one rollover counter per element in the result */
2281 PyObject
*result
; /* most recently returned result tuple */
2282 Py_ssize_t r
; /* size of result tuple */
2283 int stopped
; /* set to 1 when the permutations iterator is exhausted */
2284 } permutationsobject
;
2286 static PyTypeObject permutations_type
;
2289 permutations_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2291 permutationsobject
*po
;
2294 PyObject
*robj
= Py_None
;
2295 PyObject
*pool
= NULL
;
2296 PyObject
*iterable
= NULL
;
2297 Py_ssize_t
*indices
= NULL
;
2298 Py_ssize_t
*cycles
= NULL
;
2300 static char *kwargs
[] = {"iterable", "r", NULL
};
2302 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "O|O:permutations", kwargs
,
2306 pool
= PySequence_Tuple(iterable
);
2309 n
= PyTuple_GET_SIZE(pool
);
2312 if (robj
!= Py_None
) {
2313 r
= PyInt_AsSsize_t(robj
);
2314 if (r
== -1 && PyErr_Occurred())
2318 PyErr_SetString(PyExc_ValueError
, "r must be non-negative");
2322 PyErr_SetString(PyExc_ValueError
, "r cannot be bigger than the iterable");
2326 indices
= PyMem_Malloc(n
* sizeof(Py_ssize_t
));
2327 cycles
= PyMem_Malloc(r
* sizeof(Py_ssize_t
));
2328 if (indices
== NULL
|| cycles
== NULL
) {
2333 for (i
=0 ; i
<n
; i
++)
2335 for (i
=0 ; i
<r
; i
++)
2338 /* create permutationsobject structure */
2339 po
= (permutationsobject
*)type
->tp_alloc(type
, 0);
2344 po
->indices
= indices
;
2345 po
->cycles
= cycles
;
2350 return (PyObject
*)po
;
2353 if (indices
!= NULL
)
2354 PyMem_Free(indices
);
2362 permutations_dealloc(permutationsobject
*po
)
2364 PyObject_GC_UnTrack(po
);
2365 Py_XDECREF(po
->pool
);
2366 Py_XDECREF(po
->result
);
2367 PyMem_Free(po
->indices
);
2368 PyMem_Free(po
->cycles
);
2369 Py_TYPE(po
)->tp_free(po
);
2373 permutations_traverse(permutationsobject
*po
, visitproc visit
, void *arg
)
2376 Py_VISIT(po
->result
);
2381 permutations_next(permutationsobject
*po
)
2385 PyObject
*pool
= po
->pool
;
2386 Py_ssize_t
*indices
= po
->indices
;
2387 Py_ssize_t
*cycles
= po
->cycles
;
2388 PyObject
*result
= po
->result
;
2389 Py_ssize_t n
= PyTuple_GET_SIZE(pool
);
2390 Py_ssize_t r
= po
->r
;
2391 Py_ssize_t i
, j
, k
, index
;
2396 if (result
== NULL
) {
2397 /* On the first pass, initialize result tuple using the indices */
2398 result
= PyTuple_New(r
);
2401 po
->result
= result
;
2402 for (i
=0; i
<r
; i
++) {
2404 elem
= PyTuple_GET_ITEM(pool
, index
);
2406 PyTuple_SET_ITEM(result
, i
, elem
);
2412 /* Copy the previous result tuple or re-use it if available */
2413 if (Py_REFCNT(result
) > 1) {
2414 PyObject
*old_result
= result
;
2415 result
= PyTuple_New(r
);
2418 po
->result
= result
;
2419 for (i
=0; i
<r
; i
++) {
2420 elem
= PyTuple_GET_ITEM(old_result
, i
);
2422 PyTuple_SET_ITEM(result
, i
, elem
);
2424 Py_DECREF(old_result
);
2426 /* Now, we've got the only copy so we can update it in-place */
2427 assert(r
== 0 || Py_REFCNT(result
) == 1);
2429 /* Decrement rightmost cycle, moving leftward upon zero rollover */
2430 for (i
=r
-1 ; i
>=0 ; i
--) {
2432 if (cycles
[i
] == 0) {
2433 /* rotatation: indices[i:] = indices[i+1:] + indices[i:i+1] */
2435 for (j
=i
; j
<n
-1 ; j
++)
2436 indices
[j
] = indices
[j
+1];
2437 indices
[n
-1] = index
;
2442 indices
[i
] = indices
[n
-j
];
2443 indices
[n
-j
] = index
;
2445 for (k
=i
; k
<r
; k
++) {
2446 /* start with i, the leftmost element that changed */
2447 /* yield tuple(pool[k] for k in indices[:r]) */
2449 elem
= PyTuple_GET_ITEM(pool
, index
);
2451 oldelem
= PyTuple_GET_ITEM(result
, k
);
2452 PyTuple_SET_ITEM(result
, k
, elem
);
2458 /* If i is negative, then the cycles have all
2459 rolled-over and we're done. */
2471 PyDoc_STRVAR(permutations_doc
,
2472 "permutations(iterable[, r]) --> permutations object\n\
2474 Return successive r-length permutations of elements in the iterable.\n\n\
2475 permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)");
2477 static PyTypeObject permutations_type
= {
2478 PyVarObject_HEAD_INIT(NULL
, 0)
2479 "itertools.permutations", /* tp_name */
2480 sizeof(permutationsobject
), /* tp_basicsize */
2481 0, /* tp_itemsize */
2483 (destructor
)permutations_dealloc
, /* tp_dealloc */
2489 0, /* tp_as_number */
2490 0, /* tp_as_sequence */
2491 0, /* tp_as_mapping */
2495 PyObject_GenericGetAttr
, /* tp_getattro */
2496 0, /* tp_setattro */
2497 0, /* tp_as_buffer */
2498 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2499 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2500 permutations_doc
, /* tp_doc */
2501 (traverseproc
)permutations_traverse
, /* tp_traverse */
2503 0, /* tp_richcompare */
2504 0, /* tp_weaklistoffset */
2505 PyObject_SelfIter
, /* tp_iter */
2506 (iternextfunc
)permutations_next
, /* tp_iternext */
2512 0, /* tp_descr_get */
2513 0, /* tp_descr_set */
2514 0, /* tp_dictoffset */
2517 permutations_new
, /* tp_new */
2518 PyObject_GC_Del
, /* tp_free */
2522 /* ifilter object ************************************************************/
2530 static PyTypeObject ifilter_type
;
2533 ifilter_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2535 PyObject
*func
, *seq
;
2539 if (type
== &ifilter_type
&& !_PyArg_NoKeywords("ifilter()", kwds
))
2542 if (!PyArg_UnpackTuple(args
, "ifilter", 2, 2, &func
, &seq
))
2546 it
= PyObject_GetIter(seq
);
2550 /* create ifilterobject structure */
2551 lz
= (ifilterobject
*)type
->tp_alloc(type
, 0);
2560 return (PyObject
*)lz
;
2564 ifilter_dealloc(ifilterobject
*lz
)
2566 PyObject_GC_UnTrack(lz
);
2567 Py_XDECREF(lz
->func
);
2569 Py_TYPE(lz
)->tp_free(lz
);
2573 ifilter_traverse(ifilterobject
*lz
, visitproc visit
, void *arg
)
2581 ifilter_next(ifilterobject
*lz
)
2584 PyObject
*it
= lz
->it
;
2586 PyObject
*(*iternext
)(PyObject
*);
2588 assert(PyIter_Check(it
));
2589 iternext
= *Py_TYPE(it
)->tp_iternext
;
2591 item
= iternext(it
);
2595 if (lz
->func
== Py_None
|| lz
->func
== (PyObject
*)&PyBool_Type
) {
2596 ok
= PyObject_IsTrue(item
);
2599 good
= PyObject_CallFunctionObjArgs(lz
->func
,
2605 ok
= PyObject_IsTrue(good
);
2614 PyDoc_STRVAR(ifilter_doc
,
2615 "ifilter(function or None, sequence) --> ifilter object\n\
2617 Return those items of sequence for which function(item) is true.\n\
2618 If function is None, return the items that are true.");
2620 static PyTypeObject ifilter_type
= {
2621 PyVarObject_HEAD_INIT(NULL
, 0)
2622 "itertools.ifilter", /* tp_name */
2623 sizeof(ifilterobject
), /* tp_basicsize */
2624 0, /* tp_itemsize */
2626 (destructor
)ifilter_dealloc
, /* tp_dealloc */
2632 0, /* tp_as_number */
2633 0, /* tp_as_sequence */
2634 0, /* tp_as_mapping */
2638 PyObject_GenericGetAttr
, /* tp_getattro */
2639 0, /* tp_setattro */
2640 0, /* tp_as_buffer */
2641 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2642 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2643 ifilter_doc
, /* tp_doc */
2644 (traverseproc
)ifilter_traverse
, /* tp_traverse */
2646 0, /* tp_richcompare */
2647 0, /* tp_weaklistoffset */
2648 PyObject_SelfIter
, /* tp_iter */
2649 (iternextfunc
)ifilter_next
, /* tp_iternext */
2655 0, /* tp_descr_get */
2656 0, /* tp_descr_set */
2657 0, /* tp_dictoffset */
2660 ifilter_new
, /* tp_new */
2661 PyObject_GC_Del
, /* tp_free */
2665 /* ifilterfalse object ************************************************************/
2671 } ifilterfalseobject
;
2673 static PyTypeObject ifilterfalse_type
;
2676 ifilterfalse_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2678 PyObject
*func
, *seq
;
2680 ifilterfalseobject
*lz
;
2682 if (type
== &ifilterfalse_type
&&
2683 !_PyArg_NoKeywords("ifilterfalse()", kwds
))
2686 if (!PyArg_UnpackTuple(args
, "ifilterfalse", 2, 2, &func
, &seq
))
2690 it
= PyObject_GetIter(seq
);
2694 /* create ifilterfalseobject structure */
2695 lz
= (ifilterfalseobject
*)type
->tp_alloc(type
, 0);
2704 return (PyObject
*)lz
;
2708 ifilterfalse_dealloc(ifilterfalseobject
*lz
)
2710 PyObject_GC_UnTrack(lz
);
2711 Py_XDECREF(lz
->func
);
2713 Py_TYPE(lz
)->tp_free(lz
);
2717 ifilterfalse_traverse(ifilterfalseobject
*lz
, visitproc visit
, void *arg
)
2725 ifilterfalse_next(ifilterfalseobject
*lz
)
2728 PyObject
*it
= lz
->it
;
2730 PyObject
*(*iternext
)(PyObject
*);
2732 assert(PyIter_Check(it
));
2733 iternext
= *Py_TYPE(it
)->tp_iternext
;
2735 item
= iternext(it
);
2739 if (lz
->func
== Py_None
|| lz
->func
== (PyObject
*)&PyBool_Type
) {
2740 ok
= PyObject_IsTrue(item
);
2743 good
= PyObject_CallFunctionObjArgs(lz
->func
,
2749 ok
= PyObject_IsTrue(good
);
2758 PyDoc_STRVAR(ifilterfalse_doc
,
2759 "ifilterfalse(function or None, sequence) --> ifilterfalse object\n\
2761 Return those items of sequence for which function(item) is false.\n\
2762 If function is None, return the items that are false.");
2764 static PyTypeObject ifilterfalse_type
= {
2765 PyVarObject_HEAD_INIT(NULL
, 0)
2766 "itertools.ifilterfalse", /* tp_name */
2767 sizeof(ifilterfalseobject
), /* tp_basicsize */
2768 0, /* tp_itemsize */
2770 (destructor
)ifilterfalse_dealloc
, /* tp_dealloc */
2776 0, /* tp_as_number */
2777 0, /* tp_as_sequence */
2778 0, /* tp_as_mapping */
2782 PyObject_GenericGetAttr
, /* tp_getattro */
2783 0, /* tp_setattro */
2784 0, /* tp_as_buffer */
2785 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2786 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2787 ifilterfalse_doc
, /* tp_doc */
2788 (traverseproc
)ifilterfalse_traverse
, /* tp_traverse */
2790 0, /* tp_richcompare */
2791 0, /* tp_weaklistoffset */
2792 PyObject_SelfIter
, /* tp_iter */
2793 (iternextfunc
)ifilterfalse_next
, /* tp_iternext */
2799 0, /* tp_descr_get */
2800 0, /* tp_descr_set */
2801 0, /* tp_dictoffset */
2804 ifilterfalse_new
, /* tp_new */
2805 PyObject_GC_Del
, /* tp_free */
2809 /* count object ************************************************************/
2814 PyObject
*long_cnt
; /* Arbitrarily large count when cnt >= PY_SSIZE_T_MAX */
2817 static PyTypeObject count_type
;
2820 count_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2824 PyObject
*cnt_arg
= NULL
;
2825 PyObject
*long_cnt
= NULL
;
2827 if (type
== &count_type
&& !_PyArg_NoKeywords("count()", kwds
))
2830 if (!PyArg_UnpackTuple(args
, "count", 0, 1, &cnt_arg
))
2833 if (cnt_arg
!= NULL
) {
2834 cnt
= PyInt_AsSsize_t(cnt_arg
);
2835 if (cnt
== -1 && PyErr_Occurred()) {
2837 if (!PyLong_Check(cnt_arg
)) {
2838 PyErr_SetString(PyExc_TypeError
, "an integer is required");
2842 Py_INCREF(long_cnt
);
2843 cnt
= PY_SSIZE_T_MAX
;
2847 /* create countobject structure */
2848 lz
= (countobject
*)PyObject_New(countobject
, &count_type
);
2850 Py_XDECREF(long_cnt
);
2854 lz
->long_cnt
= long_cnt
;
2856 return (PyObject
*)lz
;
2860 count_dealloc(countobject
*lz
)
2862 Py_XDECREF(lz
->long_cnt
);
2867 count_nextlong(countobject
*lz
)
2869 static PyObject
*one
= NULL
;
2871 PyObject
*stepped_up
;
2873 if (lz
->long_cnt
== NULL
) {
2874 lz
->long_cnt
= PyInt_FromSsize_t(PY_SSIZE_T_MAX
);
2875 if (lz
->long_cnt
== NULL
)
2879 one
= PyInt_FromLong(1);
2884 assert(cnt
!= NULL
);
2885 stepped_up
= PyNumber_Add(cnt
, one
);
2886 if (stepped_up
== NULL
)
2888 lz
->long_cnt
= stepped_up
;
2893 count_next(countobject
*lz
)
2895 if (lz
->cnt
== PY_SSIZE_T_MAX
)
2896 return count_nextlong(lz
);
2897 return PyInt_FromSsize_t(lz
->cnt
++);
2901 count_repr(countobject
*lz
)
2906 if (lz
->cnt
!= PY_SSIZE_T_MAX
)
2907 return PyString_FromFormat("count(%zd)", lz
->cnt
);
2909 cnt_repr
= PyObject_Repr(lz
->long_cnt
);
2910 if (cnt_repr
== NULL
)
2912 result
= PyString_FromFormat("count(%s)", PyString_AS_STRING(cnt_repr
));
2913 Py_DECREF(cnt_repr
);
2917 PyDoc_STRVAR(count_doc
,
2918 "count([firstval]) --> count object\n\
2920 Return a count object whose .next() method returns consecutive\n\
2921 integers starting from zero or, if specified, from firstval.");
2923 static PyTypeObject count_type
= {
2924 PyVarObject_HEAD_INIT(NULL
, 0)
2925 "itertools.count", /* tp_name */
2926 sizeof(countobject
), /* tp_basicsize */
2927 0, /* tp_itemsize */
2929 (destructor
)count_dealloc
, /* tp_dealloc */
2934 (reprfunc
)count_repr
, /* tp_repr */
2935 0, /* tp_as_number */
2936 0, /* tp_as_sequence */
2937 0, /* tp_as_mapping */
2941 PyObject_GenericGetAttr
, /* tp_getattro */
2942 0, /* tp_setattro */
2943 0, /* tp_as_buffer */
2944 Py_TPFLAGS_DEFAULT
, /* tp_flags */
2945 count_doc
, /* tp_doc */
2946 0, /* tp_traverse */
2948 0, /* tp_richcompare */
2949 0, /* tp_weaklistoffset */
2950 PyObject_SelfIter
, /* tp_iter */
2951 (iternextfunc
)count_next
, /* tp_iternext */
2957 0, /* tp_descr_get */
2958 0, /* tp_descr_set */
2959 0, /* tp_dictoffset */
2962 count_new
, /* tp_new */
2966 /* izip object ************************************************************/
2972 Py_ssize_t tuplesize
;
2973 PyObject
*ittuple
; /* tuple of iterators */
2977 static PyTypeObject izip_type
;
2980 izip_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2984 PyObject
*ittuple
; /* tuple of iterators */
2986 Py_ssize_t tuplesize
= PySequence_Length(args
);
2988 if (type
== &izip_type
&& !_PyArg_NoKeywords("izip()", kwds
))
2991 /* args must be a tuple */
2992 assert(PyTuple_Check(args
));
2994 /* obtain iterators */
2995 ittuple
= PyTuple_New(tuplesize
);
2996 if (ittuple
== NULL
)
2998 for (i
=0; i
< tuplesize
; ++i
) {
2999 PyObject
*item
= PyTuple_GET_ITEM(args
, i
);
3000 PyObject
*it
= PyObject_GetIter(item
);
3002 if (PyErr_ExceptionMatches(PyExc_TypeError
))
3003 PyErr_Format(PyExc_TypeError
,
3004 "izip argument #%zd must support iteration",
3009 PyTuple_SET_ITEM(ittuple
, i
, it
);
3012 /* create a result holder */
3013 result
= PyTuple_New(tuplesize
);
3014 if (result
== NULL
) {
3018 for (i
=0 ; i
< tuplesize
; i
++) {
3020 PyTuple_SET_ITEM(result
, i
, Py_None
);
3023 /* create izipobject structure */
3024 lz
= (izipobject
*)type
->tp_alloc(type
, 0);
3030 lz
->ittuple
= ittuple
;
3031 lz
->tuplesize
= tuplesize
;
3032 lz
->result
= result
;
3034 return (PyObject
*)lz
;
3038 izip_dealloc(izipobject
*lz
)
3040 PyObject_GC_UnTrack(lz
);
3041 Py_XDECREF(lz
->ittuple
);
3042 Py_XDECREF(lz
->result
);
3043 Py_TYPE(lz
)->tp_free(lz
);
3047 izip_traverse(izipobject
*lz
, visitproc visit
, void *arg
)
3049 Py_VISIT(lz
->ittuple
);
3050 Py_VISIT(lz
->result
);
3055 izip_next(izipobject
*lz
)
3058 Py_ssize_t tuplesize
= lz
->tuplesize
;
3059 PyObject
*result
= lz
->result
;
3066 if (Py_REFCNT(result
) == 1) {
3068 for (i
=0 ; i
< tuplesize
; i
++) {
3069 it
= PyTuple_GET_ITEM(lz
->ittuple
, i
);
3070 assert(PyIter_Check(it
));
3071 item
= (*Py_TYPE(it
)->tp_iternext
)(it
);
3076 olditem
= PyTuple_GET_ITEM(result
, i
);
3077 PyTuple_SET_ITEM(result
, i
, item
);
3081 result
= PyTuple_New(tuplesize
);
3084 for (i
=0 ; i
< tuplesize
; i
++) {
3085 it
= PyTuple_GET_ITEM(lz
->ittuple
, i
);
3086 assert(PyIter_Check(it
));
3087 item
= (*Py_TYPE(it
)->tp_iternext
)(it
);
3092 PyTuple_SET_ITEM(result
, i
, item
);
3098 PyDoc_STRVAR(izip_doc
,
3099 "izip(iter1 [,iter2 [...]]) --> izip object\n\
3101 Return a izip object whose .next() method returns a tuple where\n\
3102 the i-th element comes from the i-th iterable argument. The .next()\n\
3103 method continues until the shortest iterable in the argument sequence\n\
3104 is exhausted and then it raises StopIteration. Works like the zip()\n\
3105 function but consumes less memory by returning an iterator instead of\n\
3108 static PyTypeObject izip_type
= {
3109 PyVarObject_HEAD_INIT(NULL
, 0)
3110 "itertools.izip", /* tp_name */
3111 sizeof(izipobject
), /* tp_basicsize */
3112 0, /* tp_itemsize */
3114 (destructor
)izip_dealloc
, /* tp_dealloc */
3120 0, /* tp_as_number */
3121 0, /* tp_as_sequence */
3122 0, /* tp_as_mapping */
3126 PyObject_GenericGetAttr
, /* tp_getattro */
3127 0, /* tp_setattro */
3128 0, /* tp_as_buffer */
3129 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
3130 Py_TPFLAGS_BASETYPE
, /* tp_flags */
3131 izip_doc
, /* tp_doc */
3132 (traverseproc
)izip_traverse
, /* tp_traverse */
3134 0, /* tp_richcompare */
3135 0, /* tp_weaklistoffset */
3136 PyObject_SelfIter
, /* tp_iter */
3137 (iternextfunc
)izip_next
, /* tp_iternext */
3143 0, /* tp_descr_get */
3144 0, /* tp_descr_set */
3145 0, /* tp_dictoffset */
3148 izip_new
, /* tp_new */
3149 PyObject_GC_Del
, /* tp_free */
3153 /* repeat object ************************************************************/
3161 static PyTypeObject repeat_type
;
3164 repeat_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
3168 Py_ssize_t cnt
= -1;
3170 if (type
== &repeat_type
&& !_PyArg_NoKeywords("repeat()", kwds
))
3173 if (!PyArg_ParseTuple(args
, "O|n:repeat", &element
, &cnt
))
3176 if (PyTuple_Size(args
) == 2 && cnt
< 0)
3179 ro
= (repeatobject
*)type
->tp_alloc(type
, 0);
3183 ro
->element
= element
;
3185 return (PyObject
*)ro
;
3189 repeat_dealloc(repeatobject
*ro
)
3191 PyObject_GC_UnTrack(ro
);
3192 Py_XDECREF(ro
->element
);
3193 Py_TYPE(ro
)->tp_free(ro
);
3197 repeat_traverse(repeatobject
*ro
, visitproc visit
, void *arg
)
3199 Py_VISIT(ro
->element
);
3204 repeat_next(repeatobject
*ro
)
3210 Py_INCREF(ro
->element
);
3215 repeat_repr(repeatobject
*ro
)
3217 PyObject
*result
, *objrepr
;
3219 objrepr
= PyObject_Repr(ro
->element
);
3220 if (objrepr
== NULL
)
3224 result
= PyString_FromFormat("repeat(%s)",
3225 PyString_AS_STRING(objrepr
));
3227 result
= PyString_FromFormat("repeat(%s, %zd)",
3228 PyString_AS_STRING(objrepr
), ro
->cnt
);
3234 repeat_len(repeatobject
*ro
)
3236 if (ro
->cnt
== -1) {
3237 PyErr_SetString(PyExc_TypeError
, "len() of unsized object");
3240 return PyInt_FromSize_t(ro
->cnt
);
3243 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
3245 static PyMethodDef repeat_methods
[] = {
3246 {"__length_hint__", (PyCFunction
)repeat_len
, METH_NOARGS
, length_hint_doc
},
3247 {NULL
, NULL
} /* sentinel */
3250 PyDoc_STRVAR(repeat_doc
,
3251 "repeat(element [,times]) -> create an iterator which returns the element\n\
3252 for the specified number of times. If not specified, returns the element\n\
3255 static PyTypeObject repeat_type
= {
3256 PyVarObject_HEAD_INIT(NULL
, 0)
3257 "itertools.repeat", /* tp_name */
3258 sizeof(repeatobject
), /* tp_basicsize */
3259 0, /* tp_itemsize */
3261 (destructor
)repeat_dealloc
, /* tp_dealloc */
3266 (reprfunc
)repeat_repr
, /* tp_repr */
3267 0, /* tp_as_number */
3268 0, /* tp_as_sequence */
3269 0, /* tp_as_mapping */
3273 PyObject_GenericGetAttr
, /* tp_getattro */
3274 0, /* tp_setattro */
3275 0, /* tp_as_buffer */
3276 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
3277 Py_TPFLAGS_BASETYPE
, /* tp_flags */
3278 repeat_doc
, /* tp_doc */
3279 (traverseproc
)repeat_traverse
, /* tp_traverse */
3281 0, /* tp_richcompare */
3282 0, /* tp_weaklistoffset */
3283 PyObject_SelfIter
, /* tp_iter */
3284 (iternextfunc
)repeat_next
, /* tp_iternext */
3285 repeat_methods
, /* tp_methods */
3290 0, /* tp_descr_get */
3291 0, /* tp_descr_set */
3292 0, /* tp_dictoffset */
3295 repeat_new
, /* tp_new */
3296 PyObject_GC_Del
, /* tp_free */
3299 /* iziplongest object ************************************************************/
3305 Py_ssize_t tuplesize
;
3306 Py_ssize_t numactive
;
3307 PyObject
*ittuple
; /* tuple of iterators */
3309 PyObject
*fillvalue
;
3310 } iziplongestobject
;
3312 static PyTypeObject iziplongest_type
;
3315 izip_longest_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
3317 iziplongestobject
*lz
;
3319 PyObject
*ittuple
; /* tuple of iterators */
3321 PyObject
*fillvalue
= Py_None
;
3322 Py_ssize_t tuplesize
= PySequence_Length(args
);
3324 if (kwds
!= NULL
&& PyDict_CheckExact(kwds
) && PyDict_Size(kwds
) > 0) {
3325 fillvalue
= PyDict_GetItemString(kwds
, "fillvalue");
3326 if (fillvalue
== NULL
|| PyDict_Size(kwds
) > 1) {
3327 PyErr_SetString(PyExc_TypeError
,
3328 "izip_longest() got an unexpected keyword argument");
3333 /* args must be a tuple */
3334 assert(PyTuple_Check(args
));
3336 /* obtain iterators */
3337 ittuple
= PyTuple_New(tuplesize
);
3338 if (ittuple
== NULL
)
3340 for (i
=0; i
< tuplesize
; ++i
) {
3341 PyObject
*item
= PyTuple_GET_ITEM(args
, i
);
3342 PyObject
*it
= PyObject_GetIter(item
);
3344 if (PyErr_ExceptionMatches(PyExc_TypeError
))
3345 PyErr_Format(PyExc_TypeError
,
3346 "izip_longest argument #%zd must support iteration",
3351 PyTuple_SET_ITEM(ittuple
, i
, it
);
3354 /* create a result holder */
3355 result
= PyTuple_New(tuplesize
);
3356 if (result
== NULL
) {
3360 for (i
=0 ; i
< tuplesize
; i
++) {
3362 PyTuple_SET_ITEM(result
, i
, Py_None
);
3365 /* create iziplongestobject structure */
3366 lz
= (iziplongestobject
*)type
->tp_alloc(type
, 0);
3372 lz
->ittuple
= ittuple
;
3373 lz
->tuplesize
= tuplesize
;
3374 lz
->numactive
= tuplesize
;
3375 lz
->result
= result
;
3376 Py_INCREF(fillvalue
);
3377 lz
->fillvalue
= fillvalue
;
3378 return (PyObject
*)lz
;
3382 izip_longest_dealloc(iziplongestobject
*lz
)
3384 PyObject_GC_UnTrack(lz
);
3385 Py_XDECREF(lz
->ittuple
);
3386 Py_XDECREF(lz
->result
);
3387 Py_XDECREF(lz
->fillvalue
);
3388 Py_TYPE(lz
)->tp_free(lz
);
3392 izip_longest_traverse(iziplongestobject
*lz
, visitproc visit
, void *arg
)
3394 Py_VISIT(lz
->ittuple
);
3395 Py_VISIT(lz
->result
);
3396 Py_VISIT(lz
->fillvalue
);
3401 izip_longest_next(iziplongestobject
*lz
)
3404 Py_ssize_t tuplesize
= lz
->tuplesize
;
3405 PyObject
*result
= lz
->result
;
3412 if (lz
->numactive
== 0)
3414 if (Py_REFCNT(result
) == 1) {
3416 for (i
=0 ; i
< tuplesize
; i
++) {
3417 it
= PyTuple_GET_ITEM(lz
->ittuple
, i
);
3419 Py_INCREF(lz
->fillvalue
);
3420 item
= lz
->fillvalue
;
3422 assert(PyIter_Check(it
));
3423 item
= (*Py_TYPE(it
)->tp_iternext
)(it
);
3426 if (lz
->numactive
== 0) {
3430 Py_INCREF(lz
->fillvalue
);
3431 item
= lz
->fillvalue
;
3432 PyTuple_SET_ITEM(lz
->ittuple
, i
, NULL
);
3437 olditem
= PyTuple_GET_ITEM(result
, i
);
3438 PyTuple_SET_ITEM(result
, i
, item
);
3442 result
= PyTuple_New(tuplesize
);
3445 for (i
=0 ; i
< tuplesize
; i
++) {
3446 it
= PyTuple_GET_ITEM(lz
->ittuple
, i
);
3448 Py_INCREF(lz
->fillvalue
);
3449 item
= lz
->fillvalue
;
3451 assert(PyIter_Check(it
));
3452 item
= (*Py_TYPE(it
)->tp_iternext
)(it
);
3455 if (lz
->numactive
== 0) {
3459 Py_INCREF(lz
->fillvalue
);
3460 item
= lz
->fillvalue
;
3461 PyTuple_SET_ITEM(lz
->ittuple
, i
, NULL
);
3466 PyTuple_SET_ITEM(result
, i
, item
);
3472 PyDoc_STRVAR(izip_longest_doc
,
3473 "izip_longest(iter1 [,iter2 [...]], [fillvalue=None]) --> izip_longest object\n\
3475 Return an izip_longest object whose .next() method returns a tuple where\n\
3476 the i-th element comes from the i-th iterable argument. The .next()\n\
3477 method continues until the longest iterable in the argument sequence\n\
3478 is exhausted and then it raises StopIteration. When the shorter iterables\n\
3479 are exhausted, the fillvalue is substituted in their place. The fillvalue\n\
3480 defaults to None or can be specified by a keyword argument.\n\
3483 static PyTypeObject iziplongest_type
= {
3484 PyVarObject_HEAD_INIT(NULL
, 0)
3485 "itertools.izip_longest", /* tp_name */
3486 sizeof(iziplongestobject
), /* tp_basicsize */
3487 0, /* tp_itemsize */
3489 (destructor
)izip_longest_dealloc
, /* tp_dealloc */
3495 0, /* tp_as_number */
3496 0, /* tp_as_sequence */
3497 0, /* tp_as_mapping */
3501 PyObject_GenericGetAttr
, /* tp_getattro */
3502 0, /* tp_setattro */
3503 0, /* tp_as_buffer */
3504 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
3505 Py_TPFLAGS_BASETYPE
, /* tp_flags */
3506 izip_longest_doc
, /* tp_doc */
3507 (traverseproc
)izip_longest_traverse
, /* tp_traverse */
3509 0, /* tp_richcompare */
3510 0, /* tp_weaklistoffset */
3511 PyObject_SelfIter
, /* tp_iter */
3512 (iternextfunc
)izip_longest_next
, /* tp_iternext */
3518 0, /* tp_descr_get */
3519 0, /* tp_descr_set */
3520 0, /* tp_dictoffset */
3523 izip_longest_new
, /* tp_new */
3524 PyObject_GC_Del
, /* tp_free */
3527 /* module level code ********************************************************/
3529 PyDoc_STRVAR(module_doc
,
3530 "Functional tools for creating and using iterators.\n\
3532 Infinite iterators:\n\
3533 count([n]) --> n, n+1, n+2, ...\n\
3534 cycle(p) --> p0, p1, ... plast, p0, p1, ...\n\
3535 repeat(elem [,n]) --> elem, elem, elem, ... endlessly or up to n times\n\
3537 Iterators terminating on the shortest input sequence:\n\
3538 izip(p, q, ...) --> (p[0], q[0]), (p[1], q[1]), ... \n\
3539 izip_longest(p, q, ...) --> (p[0], q[0]), (p[1], q[1]), ... \n\
3540 ifilter(pred, seq) --> elements of seq where pred(elem) is True\n\
3541 ifilterfalse(pred, seq) --> elements of seq where pred(elem) is False\n\
3542 islice(seq, [start,] stop [, step]) --> elements from\n\
3543 seq[start:stop:step]\n\
3544 imap(fun, p, q, ...) --> fun(p0, q0), fun(p1, q1), ...\n\
3545 starmap(fun, seq) --> fun(*seq[0]), fun(*seq[1]), ...\n\
3546 tee(it, n=2) --> (it1, it2 , ... itn) splits one iterator into n\n\
3547 chain(p, q, ...) --> p0, p1, ... plast, q0, q1, ... \n\
3548 takewhile(pred, seq) --> seq[0], seq[1], until pred fails\n\
3549 dropwhile(pred, seq) --> seq[n], seq[n+1], starting when pred fails\n\
3550 groupby(iterable[, keyfunc]) --> sub-iterators grouped by value of keyfunc(v)\n\
3554 static PyMethodDef module_methods
[] = {
3555 {"tee", (PyCFunction
)tee
, METH_VARARGS
, tee_doc
},
3556 {NULL
, NULL
} /* sentinel */
3565 PyTypeObject
*typelist
[] = {
3586 Py_TYPE(&teedataobject_type
) = &PyType_Type
;
3587 m
= Py_InitModule3("itertools", module_methods
, module_doc
);
3591 for (i
=0 ; typelist
[i
] != NULL
; i
++) {
3592 if (PyType_Ready(typelist
[i
]) < 0)
3594 name
= strchr(typelist
[i
]->tp_name
, '.');
3595 assert (name
!= NULL
);
3596 Py_INCREF(typelist
[i
]);
3597 PyModule_AddObject(m
, name
+1, (PyObject
*)typelist
[i
]);
3600 if (PyType_Ready(&teedataobject_type
) < 0)
3602 if (PyType_Ready(&tee_type
) < 0)
3604 if (PyType_Ready(&_grouper_type
) < 0)