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_New(_grouperobject
, &_grouper_type
);
204 igo
->parent
= (PyObject
*)parent
;
206 igo
->tgtkey
= tgtkey
;
209 return (PyObject
*)igo
;
213 _grouper_dealloc(_grouperobject
*igo
)
215 Py_DECREF(igo
->parent
);
216 Py_DECREF(igo
->tgtkey
);
221 _grouper_next(_grouperobject
*igo
)
223 groupbyobject
*gbo
= (groupbyobject
*)igo
->parent
;
224 PyObject
*newvalue
, *newkey
, *r
;
227 if (gbo
->currvalue
== NULL
) {
228 newvalue
= PyIter_Next(gbo
->it
);
229 if (newvalue
== NULL
)
232 if (gbo
->keyfunc
== Py_None
) {
236 newkey
= PyObject_CallFunctionObjArgs(gbo
->keyfunc
,
238 if (newkey
== NULL
) {
244 assert(gbo
->currkey
== NULL
);
245 gbo
->currkey
= newkey
;
246 gbo
->currvalue
= newvalue
;
249 assert(gbo
->currkey
!= NULL
);
250 rcmp
= PyObject_RichCompareBool(igo
->tgtkey
, gbo
->currkey
, Py_EQ
);
252 /* got any error or current group is end */
256 gbo
->currvalue
= NULL
;
257 Py_CLEAR(gbo
->currkey
);
262 static PyTypeObject _grouper_type
= {
263 PyVarObject_HEAD_INIT(NULL
, 0)
264 "itertools._grouper", /* tp_name */
265 sizeof(_grouperobject
), /* tp_basicsize */
268 (destructor
)_grouper_dealloc
, /* tp_dealloc */
274 0, /* tp_as_number */
275 0, /* tp_as_sequence */
276 0, /* tp_as_mapping */
280 PyObject_GenericGetAttr
, /* tp_getattro */
282 0, /* tp_as_buffer */
283 Py_TPFLAGS_DEFAULT
, /* tp_flags */
287 0, /* tp_richcompare */
288 0, /* tp_weaklistoffset */
289 PyObject_SelfIter
, /* tp_iter */
290 (iternextfunc
)_grouper_next
, /* tp_iternext */
296 0, /* tp_descr_get */
297 0, /* tp_descr_set */
298 0, /* tp_dictoffset */
302 PyObject_Del
, /* tp_free */
307 /* tee object and with supporting function and objects ***************/
309 /* The teedataobject pre-allocates space for LINKCELLS number of objects.
310 To help the object fit neatly inside cache lines (space for 16 to 32
311 pointers), the value should be a multiple of 16 minus space for
312 the other structure members including PyHEAD overhead. The larger the
313 value, the less memory overhead per object and the less time spent
314 allocating/deallocating new links. The smaller the number, the less
315 wasted space and the more rapid freeing of older data.
324 PyObject
*(values
[LINKCELLS
]);
329 teedataobject
*dataobj
;
331 PyObject
*weakreflist
;
334 static PyTypeObject teedataobject_type
;
337 teedataobject_new(PyObject
*it
)
341 tdo
= PyObject_GC_New(teedataobject
, &teedataobject_type
);
346 tdo
->nextlink
= NULL
;
349 PyObject_GC_Track(tdo
);
350 return (PyObject
*)tdo
;
354 teedataobject_jumplink(teedataobject
*tdo
)
356 if (tdo
->nextlink
== NULL
)
357 tdo
->nextlink
= teedataobject_new(tdo
->it
);
358 Py_XINCREF(tdo
->nextlink
);
359 return tdo
->nextlink
;
363 teedataobject_getitem(teedataobject
*tdo
, int i
)
367 assert(i
< LINKCELLS
);
368 if (i
< tdo
->numread
)
369 value
= tdo
->values
[i
];
371 /* this is the lead iterator, so fetch more data */
372 assert(i
== tdo
->numread
);
373 value
= PyIter_Next(tdo
->it
);
377 tdo
->values
[i
] = value
;
384 teedataobject_traverse(teedataobject
*tdo
, visitproc visit
, void * arg
)
388 for (i
= 0; i
< tdo
->numread
; i
++)
389 Py_VISIT(tdo
->values
[i
]);
390 Py_VISIT(tdo
->nextlink
);
395 teedataobject_clear(teedataobject
*tdo
)
399 for (i
=0 ; i
<tdo
->numread
; i
++)
400 Py_CLEAR(tdo
->values
[i
]);
401 Py_CLEAR(tdo
->nextlink
);
406 teedataobject_dealloc(teedataobject
*tdo
)
408 PyObject_GC_UnTrack(tdo
);
409 teedataobject_clear(tdo
);
410 PyObject_GC_Del(tdo
);
413 PyDoc_STRVAR(teedataobject_doc
, "Data container common to multiple tee objects.");
415 static PyTypeObject teedataobject_type
= {
416 PyVarObject_HEAD_INIT(0, 0) /* Must fill in type value later */
417 "itertools.tee_dataobject", /* tp_name */
418 sizeof(teedataobject
), /* tp_basicsize */
421 (destructor
)teedataobject_dealloc
, /* tp_dealloc */
427 0, /* tp_as_number */
428 0, /* tp_as_sequence */
429 0, /* tp_as_mapping */
433 PyObject_GenericGetAttr
, /* tp_getattro */
435 0, /* tp_as_buffer */
436 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
, /* tp_flags */
437 teedataobject_doc
, /* tp_doc */
438 (traverseproc
)teedataobject_traverse
, /* tp_traverse */
439 (inquiry
)teedataobject_clear
, /* tp_clear */
440 0, /* tp_richcompare */
441 0, /* tp_weaklistoffset */
449 0, /* tp_descr_get */
450 0, /* tp_descr_set */
451 0, /* tp_dictoffset */
455 PyObject_GC_Del
, /* tp_free */
459 static PyTypeObject tee_type
;
462 tee_next(teeobject
*to
)
464 PyObject
*value
, *link
;
466 if (to
->index
>= LINKCELLS
) {
467 link
= teedataobject_jumplink(to
->dataobj
);
468 Py_DECREF(to
->dataobj
);
469 to
->dataobj
= (teedataobject
*)link
;
472 value
= teedataobject_getitem(to
->dataobj
, to
->index
);
480 tee_traverse(teeobject
*to
, visitproc visit
, void *arg
)
482 Py_VISIT((PyObject
*)to
->dataobj
);
487 tee_copy(teeobject
*to
)
491 newto
= PyObject_GC_New(teeobject
, &tee_type
);
494 Py_INCREF(to
->dataobj
);
495 newto
->dataobj
= to
->dataobj
;
496 newto
->index
= to
->index
;
497 newto
->weakreflist
= NULL
;
498 PyObject_GC_Track(newto
);
499 return (PyObject
*)newto
;
502 PyDoc_STRVAR(teecopy_doc
, "Returns an independent iterator.");
505 tee_fromiterable(PyObject
*iterable
)
510 it
= PyObject_GetIter(iterable
);
513 if (PyObject_TypeCheck(it
, &tee_type
)) {
514 to
= (teeobject
*)tee_copy((teeobject
*)it
);
518 to
= PyObject_GC_New(teeobject
, &tee_type
);
521 to
->dataobj
= (teedataobject
*)teedataobject_new(it
);
529 to
->weakreflist
= NULL
;
530 PyObject_GC_Track(to
);
533 return (PyObject
*)to
;
537 tee_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kw
)
541 if (!PyArg_UnpackTuple(args
, "tee", 1, 1, &iterable
))
543 return tee_fromiterable(iterable
);
547 tee_clear(teeobject
*to
)
549 if (to
->weakreflist
!= NULL
)
550 PyObject_ClearWeakRefs((PyObject
*) to
);
551 Py_CLEAR(to
->dataobj
);
556 tee_dealloc(teeobject
*to
)
558 PyObject_GC_UnTrack(to
);
563 PyDoc_STRVAR(teeobject_doc
,
564 "Iterator wrapped to make it copyable");
566 static PyMethodDef tee_methods
[] = {
567 {"__copy__", (PyCFunction
)tee_copy
, METH_NOARGS
, teecopy_doc
},
568 {NULL
, NULL
} /* sentinel */
571 static PyTypeObject tee_type
= {
572 PyVarObject_HEAD_INIT(NULL
, 0)
573 "itertools.tee", /* tp_name */
574 sizeof(teeobject
), /* tp_basicsize */
577 (destructor
)tee_dealloc
, /* tp_dealloc */
583 0, /* tp_as_number */
584 0, /* tp_as_sequence */
585 0, /* tp_as_mapping */
591 0, /* tp_as_buffer */
592 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
, /* tp_flags */
593 teeobject_doc
, /* tp_doc */
594 (traverseproc
)tee_traverse
, /* tp_traverse */
595 (inquiry
)tee_clear
, /* tp_clear */
596 0, /* tp_richcompare */
597 offsetof(teeobject
, weakreflist
), /* tp_weaklistoffset */
598 PyObject_SelfIter
, /* tp_iter */
599 (iternextfunc
)tee_next
, /* tp_iternext */
600 tee_methods
, /* tp_methods */
605 0, /* tp_descr_get */
606 0, /* tp_descr_set */
607 0, /* tp_dictoffset */
610 tee_new
, /* tp_new */
611 PyObject_GC_Del
, /* tp_free */
615 tee(PyObject
*self
, PyObject
*args
)
618 PyObject
*it
, *iterable
, *copyable
, *result
;
620 if (!PyArg_ParseTuple(args
, "O|n", &iterable
, &n
))
623 PyErr_SetString(PyExc_ValueError
, "n must be >= 0");
626 result
= PyTuple_New(n
);
631 it
= PyObject_GetIter(iterable
);
636 if (!PyObject_HasAttrString(it
, "__copy__")) {
637 copyable
= tee_fromiterable(it
);
639 if (copyable
== NULL
) {
645 PyTuple_SET_ITEM(result
, 0, copyable
);
646 for (i
=1 ; i
<n
; i
++) {
647 copyable
= PyObject_CallMethod(copyable
, "__copy__", NULL
);
648 if (copyable
== NULL
) {
652 PyTuple_SET_ITEM(result
, i
, copyable
);
657 PyDoc_STRVAR(tee_doc
,
658 "tee(iterable, n=2) --> tuple of n independent iterators.");
661 /* cycle object **********************************************************/
670 static PyTypeObject cycle_type
;
673 cycle_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
680 if (type
== &cycle_type
&& !_PyArg_NoKeywords("cycle()", kwds
))
683 if (!PyArg_UnpackTuple(args
, "cycle", 1, 1, &iterable
))
687 it
= PyObject_GetIter(iterable
);
691 saved
= PyList_New(0);
697 /* create cycleobject structure */
698 lz
= (cycleobject
*)type
->tp_alloc(type
, 0);
708 return (PyObject
*)lz
;
712 cycle_dealloc(cycleobject
*lz
)
714 PyObject_GC_UnTrack(lz
);
715 Py_XDECREF(lz
->saved
);
717 Py_TYPE(lz
)->tp_free(lz
);
721 cycle_traverse(cycleobject
*lz
, visitproc visit
, void *arg
)
729 cycle_next(cycleobject
*lz
)
736 item
= PyIter_Next(lz
->it
);
739 PyList_Append(lz
->saved
, item
);
742 if (PyErr_Occurred()) {
743 if (PyErr_ExceptionMatches(PyExc_StopIteration
))
748 if (PyList_Size(lz
->saved
) == 0)
750 it
= PyObject_GetIter(lz
->saved
);
760 PyDoc_STRVAR(cycle_doc
,
761 "cycle(iterable) --> cycle object\n\
763 Return elements from the iterable until it is exhausted.\n\
764 Then repeat the sequence indefinitely.");
766 static PyTypeObject cycle_type
= {
767 PyVarObject_HEAD_INIT(NULL
, 0)
768 "itertools.cycle", /* tp_name */
769 sizeof(cycleobject
), /* tp_basicsize */
772 (destructor
)cycle_dealloc
, /* tp_dealloc */
778 0, /* tp_as_number */
779 0, /* tp_as_sequence */
780 0, /* tp_as_mapping */
784 PyObject_GenericGetAttr
, /* tp_getattro */
786 0, /* tp_as_buffer */
787 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
788 Py_TPFLAGS_BASETYPE
, /* tp_flags */
789 cycle_doc
, /* tp_doc */
790 (traverseproc
)cycle_traverse
, /* tp_traverse */
792 0, /* tp_richcompare */
793 0, /* tp_weaklistoffset */
794 PyObject_SelfIter
, /* tp_iter */
795 (iternextfunc
)cycle_next
, /* tp_iternext */
801 0, /* tp_descr_get */
802 0, /* tp_descr_set */
803 0, /* tp_dictoffset */
806 cycle_new
, /* tp_new */
807 PyObject_GC_Del
, /* tp_free */
811 /* dropwhile object **********************************************************/
820 static PyTypeObject dropwhile_type
;
823 dropwhile_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
825 PyObject
*func
, *seq
;
829 if (type
== &dropwhile_type
&& !_PyArg_NoKeywords("dropwhile()", kwds
))
832 if (!PyArg_UnpackTuple(args
, "dropwhile", 2, 2, &func
, &seq
))
836 it
= PyObject_GetIter(seq
);
840 /* create dropwhileobject structure */
841 lz
= (dropwhileobject
*)type
->tp_alloc(type
, 0);
851 return (PyObject
*)lz
;
855 dropwhile_dealloc(dropwhileobject
*lz
)
857 PyObject_GC_UnTrack(lz
);
858 Py_XDECREF(lz
->func
);
860 Py_TYPE(lz
)->tp_free(lz
);
864 dropwhile_traverse(dropwhileobject
*lz
, visitproc visit
, void *arg
)
872 dropwhile_next(dropwhileobject
*lz
)
874 PyObject
*item
, *good
;
875 PyObject
*it
= lz
->it
;
877 PyObject
*(*iternext
)(PyObject
*);
879 assert(PyIter_Check(it
));
880 iternext
= *Py_TYPE(it
)->tp_iternext
;
888 good
= PyObject_CallFunctionObjArgs(lz
->func
, item
, NULL
);
893 ok
= PyObject_IsTrue(good
);
903 PyDoc_STRVAR(dropwhile_doc
,
904 "dropwhile(predicate, iterable) --> dropwhile object\n\
906 Drop items from the iterable while predicate(item) is true.\n\
907 Afterwards, return every element until the iterable is exhausted.");
909 static PyTypeObject dropwhile_type
= {
910 PyVarObject_HEAD_INIT(NULL
, 0)
911 "itertools.dropwhile", /* tp_name */
912 sizeof(dropwhileobject
), /* tp_basicsize */
915 (destructor
)dropwhile_dealloc
, /* tp_dealloc */
921 0, /* tp_as_number */
922 0, /* tp_as_sequence */
923 0, /* tp_as_mapping */
927 PyObject_GenericGetAttr
, /* tp_getattro */
929 0, /* tp_as_buffer */
930 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
931 Py_TPFLAGS_BASETYPE
, /* tp_flags */
932 dropwhile_doc
, /* tp_doc */
933 (traverseproc
)dropwhile_traverse
, /* tp_traverse */
935 0, /* tp_richcompare */
936 0, /* tp_weaklistoffset */
937 PyObject_SelfIter
, /* tp_iter */
938 (iternextfunc
)dropwhile_next
, /* tp_iternext */
944 0, /* tp_descr_get */
945 0, /* tp_descr_set */
946 0, /* tp_dictoffset */
949 dropwhile_new
, /* tp_new */
950 PyObject_GC_Del
, /* tp_free */
954 /* takewhile object **********************************************************/
963 static PyTypeObject takewhile_type
;
966 takewhile_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
968 PyObject
*func
, *seq
;
972 if (type
== &takewhile_type
&& !_PyArg_NoKeywords("takewhile()", kwds
))
975 if (!PyArg_UnpackTuple(args
, "takewhile", 2, 2, &func
, &seq
))
979 it
= PyObject_GetIter(seq
);
983 /* create takewhileobject structure */
984 lz
= (takewhileobject
*)type
->tp_alloc(type
, 0);
994 return (PyObject
*)lz
;
998 takewhile_dealloc(takewhileobject
*lz
)
1000 PyObject_GC_UnTrack(lz
);
1001 Py_XDECREF(lz
->func
);
1003 Py_TYPE(lz
)->tp_free(lz
);
1007 takewhile_traverse(takewhileobject
*lz
, visitproc visit
, void *arg
)
1015 takewhile_next(takewhileobject
*lz
)
1017 PyObject
*item
, *good
;
1018 PyObject
*it
= lz
->it
;
1024 assert(PyIter_Check(it
));
1025 item
= (*Py_TYPE(it
)->tp_iternext
)(it
);
1029 good
= PyObject_CallFunctionObjArgs(lz
->func
, item
, NULL
);
1034 ok
= PyObject_IsTrue(good
);
1043 PyDoc_STRVAR(takewhile_doc
,
1044 "takewhile(predicate, iterable) --> takewhile object\n\
1046 Return successive entries from an iterable as long as the \n\
1047 predicate evaluates to true for each entry.");
1049 static PyTypeObject takewhile_type
= {
1050 PyVarObject_HEAD_INIT(NULL
, 0)
1051 "itertools.takewhile", /* tp_name */
1052 sizeof(takewhileobject
), /* tp_basicsize */
1053 0, /* tp_itemsize */
1055 (destructor
)takewhile_dealloc
, /* tp_dealloc */
1061 0, /* tp_as_number */
1062 0, /* tp_as_sequence */
1063 0, /* tp_as_mapping */
1067 PyObject_GenericGetAttr
, /* tp_getattro */
1068 0, /* tp_setattro */
1069 0, /* tp_as_buffer */
1070 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1071 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1072 takewhile_doc
, /* tp_doc */
1073 (traverseproc
)takewhile_traverse
, /* tp_traverse */
1075 0, /* tp_richcompare */
1076 0, /* tp_weaklistoffset */
1077 PyObject_SelfIter
, /* tp_iter */
1078 (iternextfunc
)takewhile_next
, /* tp_iternext */
1084 0, /* tp_descr_get */
1085 0, /* tp_descr_set */
1086 0, /* tp_dictoffset */
1089 takewhile_new
, /* tp_new */
1090 PyObject_GC_Del
, /* tp_free */
1094 /* islice object ************************************************************/
1105 static PyTypeObject islice_type
;
1108 islice_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1111 Py_ssize_t start
=0, stop
=-1, step
=1;
1112 PyObject
*it
, *a1
=NULL
, *a2
=NULL
, *a3
=NULL
;
1116 if (type
== &islice_type
&& !_PyArg_NoKeywords("islice()", kwds
))
1119 if (!PyArg_UnpackTuple(args
, "islice", 2, 4, &seq
, &a1
, &a2
, &a3
))
1122 numargs
= PyTuple_Size(args
);
1124 if (a1
!= Py_None
) {
1125 stop
= PyInt_AsSsize_t(a1
);
1127 if (PyErr_Occurred())
1129 PyErr_SetString(PyExc_ValueError
,
1130 "Stop argument for islice() must be a non-negative integer or None.");
1136 start
= PyInt_AsSsize_t(a1
);
1137 if (start
== -1 && PyErr_Occurred())
1139 if (a2
!= Py_None
) {
1140 stop
= PyInt_AsSsize_t(a2
);
1142 if (PyErr_Occurred())
1144 PyErr_SetString(PyExc_ValueError
,
1145 "Stop argument for islice() must be a non-negative integer or None.");
1150 if (start
<0 || stop
<-1) {
1151 PyErr_SetString(PyExc_ValueError
,
1152 "Indices for islice() must be non-negative integers or None.");
1158 step
= PyInt_AsSsize_t(a3
);
1159 if (step
== -1 && PyErr_Occurred())
1163 PyErr_SetString(PyExc_ValueError
,
1164 "Step for islice() must be a positive integer or None.");
1169 it
= PyObject_GetIter(seq
);
1173 /* create isliceobject structure */
1174 lz
= (isliceobject
*)type
->tp_alloc(type
, 0);
1185 return (PyObject
*)lz
;
1189 islice_dealloc(isliceobject
*lz
)
1191 PyObject_GC_UnTrack(lz
);
1193 Py_TYPE(lz
)->tp_free(lz
);
1197 islice_traverse(isliceobject
*lz
, visitproc visit
, void *arg
)
1204 islice_next(isliceobject
*lz
)
1207 PyObject
*it
= lz
->it
;
1209 PyObject
*(*iternext
)(PyObject
*);
1211 assert(PyIter_Check(it
));
1212 iternext
= *Py_TYPE(it
)->tp_iternext
;
1213 while (lz
->cnt
< lz
->next
) {
1214 item
= iternext(it
);
1220 if (lz
->stop
!= -1 && lz
->cnt
>= lz
->stop
)
1222 assert(PyIter_Check(it
));
1223 item
= iternext(it
);
1228 lz
->next
+= lz
->step
;
1229 if (lz
->next
< oldnext
) /* Check for overflow */
1230 lz
->next
= lz
->stop
;
1234 PyDoc_STRVAR(islice_doc
,
1235 "islice(iterable, [start,] stop [, step]) --> islice object\n\
1237 Return an iterator whose next() method returns selected values from an\n\
1238 iterable. If start is specified, will skip all preceding elements;\n\
1239 otherwise, start defaults to zero. Step defaults to one. If\n\
1240 specified as another value, step determines how many values are \n\
1241 skipped between successive calls. Works like a slice() on a list\n\
1242 but returns an iterator.");
1244 static PyTypeObject islice_type
= {
1245 PyVarObject_HEAD_INIT(NULL
, 0)
1246 "itertools.islice", /* tp_name */
1247 sizeof(isliceobject
), /* tp_basicsize */
1248 0, /* tp_itemsize */
1250 (destructor
)islice_dealloc
, /* tp_dealloc */
1256 0, /* tp_as_number */
1257 0, /* tp_as_sequence */
1258 0, /* tp_as_mapping */
1262 PyObject_GenericGetAttr
, /* tp_getattro */
1263 0, /* tp_setattro */
1264 0, /* tp_as_buffer */
1265 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1266 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1267 islice_doc
, /* tp_doc */
1268 (traverseproc
)islice_traverse
, /* tp_traverse */
1270 0, /* tp_richcompare */
1271 0, /* tp_weaklistoffset */
1272 PyObject_SelfIter
, /* tp_iter */
1273 (iternextfunc
)islice_next
, /* tp_iternext */
1279 0, /* tp_descr_get */
1280 0, /* tp_descr_set */
1281 0, /* tp_dictoffset */
1284 islice_new
, /* tp_new */
1285 PyObject_GC_Del
, /* tp_free */
1289 /* starmap object ************************************************************/
1297 static PyTypeObject starmap_type
;
1300 starmap_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1302 PyObject
*func
, *seq
;
1306 if (type
== &starmap_type
&& !_PyArg_NoKeywords("starmap()", kwds
))
1309 if (!PyArg_UnpackTuple(args
, "starmap", 2, 2, &func
, &seq
))
1313 it
= PyObject_GetIter(seq
);
1317 /* create starmapobject structure */
1318 lz
= (starmapobject
*)type
->tp_alloc(type
, 0);
1327 return (PyObject
*)lz
;
1331 starmap_dealloc(starmapobject
*lz
)
1333 PyObject_GC_UnTrack(lz
);
1334 Py_XDECREF(lz
->func
);
1336 Py_TYPE(lz
)->tp_free(lz
);
1340 starmap_traverse(starmapobject
*lz
, visitproc visit
, void *arg
)
1348 starmap_next(starmapobject
*lz
)
1352 PyObject
*it
= lz
->it
;
1354 assert(PyIter_Check(it
));
1355 args
= (*Py_TYPE(it
)->tp_iternext
)(it
);
1358 if (!PyTuple_CheckExact(args
)) {
1360 PyErr_SetString(PyExc_TypeError
,
1361 "iterator must return a tuple");
1364 result
= PyObject_Call(lz
->func
, args
, NULL
);
1369 PyDoc_STRVAR(starmap_doc
,
1370 "starmap(function, sequence) --> starmap object\n\
1372 Return an iterator whose values are returned from the function evaluated\n\
1373 with a argument tuple taken from the given sequence.");
1375 static PyTypeObject starmap_type
= {
1376 PyVarObject_HEAD_INIT(NULL
, 0)
1377 "itertools.starmap", /* tp_name */
1378 sizeof(starmapobject
), /* tp_basicsize */
1379 0, /* tp_itemsize */
1381 (destructor
)starmap_dealloc
, /* tp_dealloc */
1387 0, /* tp_as_number */
1388 0, /* tp_as_sequence */
1389 0, /* tp_as_mapping */
1393 PyObject_GenericGetAttr
, /* tp_getattro */
1394 0, /* tp_setattro */
1395 0, /* tp_as_buffer */
1396 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1397 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1398 starmap_doc
, /* tp_doc */
1399 (traverseproc
)starmap_traverse
, /* tp_traverse */
1401 0, /* tp_richcompare */
1402 0, /* tp_weaklistoffset */
1403 PyObject_SelfIter
, /* tp_iter */
1404 (iternextfunc
)starmap_next
, /* tp_iternext */
1410 0, /* tp_descr_get */
1411 0, /* tp_descr_set */
1412 0, /* tp_dictoffset */
1415 starmap_new
, /* tp_new */
1416 PyObject_GC_Del
, /* tp_free */
1420 /* imap object ************************************************************/
1428 static PyTypeObject imap_type
;
1431 imap_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1433 PyObject
*it
, *iters
, *func
;
1435 Py_ssize_t numargs
, i
;
1437 if (type
== &imap_type
&& !_PyArg_NoKeywords("imap()", kwds
))
1440 numargs
= PyTuple_Size(args
);
1442 PyErr_SetString(PyExc_TypeError
,
1443 "imap() must have at least two arguments.");
1447 iters
= PyTuple_New(numargs
-1);
1451 for (i
=1 ; i
<numargs
; i
++) {
1453 it
= PyObject_GetIter(PyTuple_GET_ITEM(args
, i
));
1458 PyTuple_SET_ITEM(iters
, i
-1, it
);
1461 /* create imapobject structure */
1462 lz
= (imapobject
*)type
->tp_alloc(type
, 0);
1468 func
= PyTuple_GET_ITEM(args
, 0);
1472 return (PyObject
*)lz
;
1476 imap_dealloc(imapobject
*lz
)
1478 PyObject_GC_UnTrack(lz
);
1479 Py_XDECREF(lz
->iters
);
1480 Py_XDECREF(lz
->func
);
1481 Py_TYPE(lz
)->tp_free(lz
);
1485 imap_traverse(imapobject
*lz
, visitproc visit
, void *arg
)
1487 Py_VISIT(lz
->iters
);
1493 imap() is an iterator version of __builtins__.map() except that it does
1494 not have the None fill-in feature. That was intentionally left out for
1495 the following reasons:
1497 1) Itertools are designed to be easily combined and chained together.
1498 Having all tools stop with the shortest input is a unifying principle
1499 that makes it easier to combine finite iterators (supplying data) with
1500 infinite iterators like count() and repeat() (for supplying sequential
1501 or constant arguments to a function).
1503 2) In typical use cases for combining itertools, having one finite data
1504 supplier run out before another is likely to be an error condition which
1505 should not pass silently by automatically supplying None.
1507 3) The use cases for automatic None fill-in are rare -- not many functions
1508 do something useful when a parameter suddenly switches type and becomes
1511 4) If a need does arise, it can be met by __builtins__.map() or by
1512 writing: chain(iterable, repeat(None)).
1514 5) Similar toolsets in Haskell and SML do not have automatic None fill-in.
1518 imap_next(imapobject
*lz
)
1523 Py_ssize_t numargs
, i
;
1525 numargs
= PyTuple_Size(lz
->iters
);
1526 argtuple
= PyTuple_New(numargs
);
1527 if (argtuple
== NULL
)
1530 for (i
=0 ; i
<numargs
; i
++) {
1531 val
= PyIter_Next(PyTuple_GET_ITEM(lz
->iters
, i
));
1533 Py_DECREF(argtuple
);
1536 PyTuple_SET_ITEM(argtuple
, i
, val
);
1538 if (lz
->func
== Py_None
)
1540 result
= PyObject_Call(lz
->func
, argtuple
, NULL
);
1541 Py_DECREF(argtuple
);
1545 PyDoc_STRVAR(imap_doc
,
1546 "imap(func, *iterables) --> imap object\n\
1548 Make an iterator that computes the function using arguments from\n\
1549 each of the iterables. Like map() except that it returns\n\
1550 an iterator instead of a list and that it stops when the shortest\n\
1551 iterable is exhausted instead of filling in None for shorter\n\
1554 static PyTypeObject imap_type
= {
1555 PyVarObject_HEAD_INIT(NULL
, 0)
1556 "itertools.imap", /* tp_name */
1557 sizeof(imapobject
), /* tp_basicsize */
1558 0, /* tp_itemsize */
1560 (destructor
)imap_dealloc
, /* tp_dealloc */
1566 0, /* tp_as_number */
1567 0, /* tp_as_sequence */
1568 0, /* tp_as_mapping */
1572 PyObject_GenericGetAttr
, /* tp_getattro */
1573 0, /* tp_setattro */
1574 0, /* tp_as_buffer */
1575 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1576 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1577 imap_doc
, /* tp_doc */
1578 (traverseproc
)imap_traverse
, /* tp_traverse */
1580 0, /* tp_richcompare */
1581 0, /* tp_weaklistoffset */
1582 PyObject_SelfIter
, /* tp_iter */
1583 (iternextfunc
)imap_next
, /* tp_iternext */
1589 0, /* tp_descr_get */
1590 0, /* tp_descr_set */
1591 0, /* tp_dictoffset */
1594 imap_new
, /* tp_new */
1595 PyObject_GC_Del
, /* tp_free */
1599 /* chain object ************************************************************/
1603 Py_ssize_t tuplesize
;
1604 Py_ssize_t iternum
; /* which iterator is active */
1605 PyObject
*ittuple
; /* tuple of iterators */
1608 static PyTypeObject chain_type
;
1611 chain_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1614 Py_ssize_t tuplesize
= PySequence_Length(args
);
1618 if (type
== &chain_type
&& !_PyArg_NoKeywords("chain()", kwds
))
1621 /* obtain iterators */
1622 assert(PyTuple_Check(args
));
1623 ittuple
= PyTuple_New(tuplesize
);
1624 if (ittuple
== NULL
)
1626 for (i
=0; i
< tuplesize
; ++i
) {
1627 PyObject
*item
= PyTuple_GET_ITEM(args
, i
);
1628 PyObject
*it
= PyObject_GetIter(item
);
1630 if (PyErr_ExceptionMatches(PyExc_TypeError
))
1631 PyErr_Format(PyExc_TypeError
,
1632 "chain argument #%zd must support iteration",
1637 PyTuple_SET_ITEM(ittuple
, i
, it
);
1640 /* create chainobject structure */
1641 lz
= (chainobject
*)type
->tp_alloc(type
, 0);
1647 lz
->ittuple
= ittuple
;
1649 lz
->tuplesize
= tuplesize
;
1651 return (PyObject
*)lz
;
1655 chain_dealloc(chainobject
*lz
)
1657 PyObject_GC_UnTrack(lz
);
1658 Py_XDECREF(lz
->ittuple
);
1659 Py_TYPE(lz
)->tp_free(lz
);
1663 chain_traverse(chainobject
*lz
, visitproc visit
, void *arg
)
1665 Py_VISIT(lz
->ittuple
);
1670 chain_next(chainobject
*lz
)
1675 while (lz
->iternum
< lz
->tuplesize
) {
1676 it
= PyTuple_GET_ITEM(lz
->ittuple
, lz
->iternum
);
1677 item
= PyIter_Next(it
);
1680 if (PyErr_Occurred()) {
1681 if (PyErr_ExceptionMatches(PyExc_StopIteration
))
1691 PyDoc_STRVAR(chain_doc
,
1692 "chain(*iterables) --> chain object\n\
1694 Return a chain object whose .next() method returns elements from the\n\
1695 first iterable until it is exhausted, then elements from the next\n\
1696 iterable, until all of the iterables are exhausted.");
1698 static PyTypeObject chain_type
= {
1699 PyVarObject_HEAD_INIT(NULL
, 0)
1700 "itertools.chain", /* tp_name */
1701 sizeof(chainobject
), /* tp_basicsize */
1702 0, /* tp_itemsize */
1704 (destructor
)chain_dealloc
, /* tp_dealloc */
1710 0, /* tp_as_number */
1711 0, /* tp_as_sequence */
1712 0, /* tp_as_mapping */
1716 PyObject_GenericGetAttr
, /* tp_getattro */
1717 0, /* tp_setattro */
1718 0, /* tp_as_buffer */
1719 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1720 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1721 chain_doc
, /* tp_doc */
1722 (traverseproc
)chain_traverse
, /* tp_traverse */
1724 0, /* tp_richcompare */
1725 0, /* tp_weaklistoffset */
1726 PyObject_SelfIter
, /* tp_iter */
1727 (iternextfunc
)chain_next
, /* tp_iternext */
1733 0, /* tp_descr_get */
1734 0, /* tp_descr_set */
1735 0, /* tp_dictoffset */
1738 chain_new
, /* tp_new */
1739 PyObject_GC_Del
, /* tp_free */
1743 /* ifilter object ************************************************************/
1751 static PyTypeObject ifilter_type
;
1754 ifilter_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1756 PyObject
*func
, *seq
;
1760 if (type
== &ifilter_type
&& !_PyArg_NoKeywords("ifilter()", kwds
))
1763 if (!PyArg_UnpackTuple(args
, "ifilter", 2, 2, &func
, &seq
))
1767 it
= PyObject_GetIter(seq
);
1771 /* create ifilterobject structure */
1772 lz
= (ifilterobject
*)type
->tp_alloc(type
, 0);
1781 return (PyObject
*)lz
;
1785 ifilter_dealloc(ifilterobject
*lz
)
1787 PyObject_GC_UnTrack(lz
);
1788 Py_XDECREF(lz
->func
);
1790 Py_TYPE(lz
)->tp_free(lz
);
1794 ifilter_traverse(ifilterobject
*lz
, visitproc visit
, void *arg
)
1802 ifilter_next(ifilterobject
*lz
)
1805 PyObject
*it
= lz
->it
;
1807 PyObject
*(*iternext
)(PyObject
*);
1809 assert(PyIter_Check(it
));
1810 iternext
= *Py_TYPE(it
)->tp_iternext
;
1812 item
= iternext(it
);
1816 if (lz
->func
== Py_None
) {
1817 ok
= PyObject_IsTrue(item
);
1820 good
= PyObject_CallFunctionObjArgs(lz
->func
,
1826 ok
= PyObject_IsTrue(good
);
1835 PyDoc_STRVAR(ifilter_doc
,
1836 "ifilter(function or None, sequence) --> ifilter object\n\
1838 Return those items of sequence for which function(item) is true.\n\
1839 If function is None, return the items that are true.");
1841 static PyTypeObject ifilter_type
= {
1842 PyVarObject_HEAD_INIT(NULL
, 0)
1843 "itertools.ifilter", /* tp_name */
1844 sizeof(ifilterobject
), /* tp_basicsize */
1845 0, /* tp_itemsize */
1847 (destructor
)ifilter_dealloc
, /* tp_dealloc */
1853 0, /* tp_as_number */
1854 0, /* tp_as_sequence */
1855 0, /* tp_as_mapping */
1859 PyObject_GenericGetAttr
, /* tp_getattro */
1860 0, /* tp_setattro */
1861 0, /* tp_as_buffer */
1862 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
1863 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1864 ifilter_doc
, /* tp_doc */
1865 (traverseproc
)ifilter_traverse
, /* tp_traverse */
1867 0, /* tp_richcompare */
1868 0, /* tp_weaklistoffset */
1869 PyObject_SelfIter
, /* tp_iter */
1870 (iternextfunc
)ifilter_next
, /* tp_iternext */
1876 0, /* tp_descr_get */
1877 0, /* tp_descr_set */
1878 0, /* tp_dictoffset */
1881 ifilter_new
, /* tp_new */
1882 PyObject_GC_Del
, /* tp_free */
1886 /* ifilterfalse object ************************************************************/
1892 } ifilterfalseobject
;
1894 static PyTypeObject ifilterfalse_type
;
1897 ifilterfalse_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1899 PyObject
*func
, *seq
;
1901 ifilterfalseobject
*lz
;
1903 if (type
== &ifilterfalse_type
&&
1904 !_PyArg_NoKeywords("ifilterfalse()", kwds
))
1907 if (!PyArg_UnpackTuple(args
, "ifilterfalse", 2, 2, &func
, &seq
))
1911 it
= PyObject_GetIter(seq
);
1915 /* create ifilterfalseobject structure */
1916 lz
= (ifilterfalseobject
*)type
->tp_alloc(type
, 0);
1925 return (PyObject
*)lz
;
1929 ifilterfalse_dealloc(ifilterfalseobject
*lz
)
1931 PyObject_GC_UnTrack(lz
);
1932 Py_XDECREF(lz
->func
);
1934 Py_TYPE(lz
)->tp_free(lz
);
1938 ifilterfalse_traverse(ifilterfalseobject
*lz
, visitproc visit
, void *arg
)
1946 ifilterfalse_next(ifilterfalseobject
*lz
)
1949 PyObject
*it
= lz
->it
;
1951 PyObject
*(*iternext
)(PyObject
*);
1953 assert(PyIter_Check(it
));
1954 iternext
= *Py_TYPE(it
)->tp_iternext
;
1956 item
= iternext(it
);
1960 if (lz
->func
== Py_None
) {
1961 ok
= PyObject_IsTrue(item
);
1964 good
= PyObject_CallFunctionObjArgs(lz
->func
,
1970 ok
= PyObject_IsTrue(good
);
1979 PyDoc_STRVAR(ifilterfalse_doc
,
1980 "ifilterfalse(function or None, sequence) --> ifilterfalse object\n\
1982 Return those items of sequence for which function(item) is false.\n\
1983 If function is None, return the items that are false.");
1985 static PyTypeObject ifilterfalse_type
= {
1986 PyVarObject_HEAD_INIT(NULL
, 0)
1987 "itertools.ifilterfalse", /* tp_name */
1988 sizeof(ifilterfalseobject
), /* tp_basicsize */
1989 0, /* tp_itemsize */
1991 (destructor
)ifilterfalse_dealloc
, /* tp_dealloc */
1997 0, /* tp_as_number */
1998 0, /* tp_as_sequence */
1999 0, /* tp_as_mapping */
2003 PyObject_GenericGetAttr
, /* tp_getattro */
2004 0, /* tp_setattro */
2005 0, /* tp_as_buffer */
2006 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2007 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2008 ifilterfalse_doc
, /* tp_doc */
2009 (traverseproc
)ifilterfalse_traverse
, /* tp_traverse */
2011 0, /* tp_richcompare */
2012 0, /* tp_weaklistoffset */
2013 PyObject_SelfIter
, /* tp_iter */
2014 (iternextfunc
)ifilterfalse_next
, /* tp_iternext */
2020 0, /* tp_descr_get */
2021 0, /* tp_descr_set */
2022 0, /* tp_dictoffset */
2025 ifilterfalse_new
, /* tp_new */
2026 PyObject_GC_Del
, /* tp_free */
2030 /* count object ************************************************************/
2035 PyObject
*long_cnt
; /* Arbitrarily large count when cnt >= PY_SSIZE_T_MAX */
2038 static PyTypeObject count_type
;
2041 count_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2045 PyObject
*cnt_arg
= NULL
;
2046 PyObject
*long_cnt
= NULL
;
2048 if (type
== &count_type
&& !_PyArg_NoKeywords("count()", kwds
))
2051 if (!PyArg_UnpackTuple(args
, "count", 0, 1, &cnt_arg
))
2054 if (cnt_arg
!= NULL
) {
2055 cnt
= PyInt_AsSsize_t(cnt_arg
);
2056 if (cnt
== -1 && PyErr_Occurred()) {
2058 if (!PyLong_Check(cnt_arg
)) {
2059 PyErr_SetString(PyExc_TypeError
, "an integer is required");
2063 Py_INCREF(long_cnt
);
2064 cnt
= PY_SSIZE_T_MAX
;
2068 /* create countobject structure */
2069 lz
= (countobject
*)PyObject_New(countobject
, &count_type
);
2071 Py_XDECREF(long_cnt
);
2075 lz
->long_cnt
= long_cnt
;
2077 return (PyObject
*)lz
;
2081 count_dealloc(countobject
*lz
)
2083 Py_XDECREF(lz
->long_cnt
);
2088 count_nextlong(countobject
*lz
)
2090 static PyObject
*one
= NULL
;
2092 PyObject
*stepped_up
;
2094 if (lz
->long_cnt
== NULL
) {
2095 lz
->long_cnt
= PyInt_FromSsize_t(PY_SSIZE_T_MAX
);
2096 if (lz
->long_cnt
== NULL
)
2100 one
= PyInt_FromLong(1);
2105 assert(cnt
!= NULL
);
2106 stepped_up
= PyNumber_Add(cnt
, one
);
2107 if (stepped_up
== NULL
)
2109 lz
->long_cnt
= stepped_up
;
2114 count_next(countobject
*lz
)
2116 if (lz
->cnt
== PY_SSIZE_T_MAX
)
2117 return count_nextlong(lz
);
2118 return PyInt_FromSsize_t(lz
->cnt
++);
2122 count_repr(countobject
*lz
)
2127 if (lz
->cnt
!= PY_SSIZE_T_MAX
)
2128 return PyString_FromFormat("count(%zd)", lz
->cnt
);
2130 cnt_repr
= PyObject_Repr(lz
->long_cnt
);
2131 if (cnt_repr
== NULL
)
2133 result
= PyString_FromFormat("count(%s)", PyString_AS_STRING(cnt_repr
));
2134 Py_DECREF(cnt_repr
);
2138 PyDoc_STRVAR(count_doc
,
2139 "count([firstval]) --> count object\n\
2141 Return a count object whose .next() method returns consecutive\n\
2142 integers starting from zero or, if specified, from firstval.");
2144 static PyTypeObject count_type
= {
2145 PyVarObject_HEAD_INIT(NULL
, 0)
2146 "itertools.count", /* tp_name */
2147 sizeof(countobject
), /* tp_basicsize */
2148 0, /* tp_itemsize */
2150 (destructor
)count_dealloc
, /* tp_dealloc */
2155 (reprfunc
)count_repr
, /* tp_repr */
2156 0, /* tp_as_number */
2157 0, /* tp_as_sequence */
2158 0, /* tp_as_mapping */
2162 PyObject_GenericGetAttr
, /* tp_getattro */
2163 0, /* tp_setattro */
2164 0, /* tp_as_buffer */
2165 Py_TPFLAGS_DEFAULT
, /* tp_flags */
2166 count_doc
, /* tp_doc */
2167 0, /* tp_traverse */
2169 0, /* tp_richcompare */
2170 0, /* tp_weaklistoffset */
2171 PyObject_SelfIter
, /* tp_iter */
2172 (iternextfunc
)count_next
, /* tp_iternext */
2178 0, /* tp_descr_get */
2179 0, /* tp_descr_set */
2180 0, /* tp_dictoffset */
2183 count_new
, /* tp_new */
2187 /* izip object ************************************************************/
2193 Py_ssize_t tuplesize
;
2194 PyObject
*ittuple
; /* tuple of iterators */
2198 static PyTypeObject izip_type
;
2201 izip_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2205 PyObject
*ittuple
; /* tuple of iterators */
2207 Py_ssize_t tuplesize
= PySequence_Length(args
);
2209 if (type
== &izip_type
&& !_PyArg_NoKeywords("izip()", kwds
))
2212 /* args must be a tuple */
2213 assert(PyTuple_Check(args
));
2215 /* obtain iterators */
2216 ittuple
= PyTuple_New(tuplesize
);
2217 if (ittuple
== NULL
)
2219 for (i
=0; i
< tuplesize
; ++i
) {
2220 PyObject
*item
= PyTuple_GET_ITEM(args
, i
);
2221 PyObject
*it
= PyObject_GetIter(item
);
2223 if (PyErr_ExceptionMatches(PyExc_TypeError
))
2224 PyErr_Format(PyExc_TypeError
,
2225 "izip argument #%zd must support iteration",
2230 PyTuple_SET_ITEM(ittuple
, i
, it
);
2233 /* create a result holder */
2234 result
= PyTuple_New(tuplesize
);
2235 if (result
== NULL
) {
2239 for (i
=0 ; i
< tuplesize
; i
++) {
2241 PyTuple_SET_ITEM(result
, i
, Py_None
);
2244 /* create izipobject structure */
2245 lz
= (izipobject
*)type
->tp_alloc(type
, 0);
2251 lz
->ittuple
= ittuple
;
2252 lz
->tuplesize
= tuplesize
;
2253 lz
->result
= result
;
2255 return (PyObject
*)lz
;
2259 izip_dealloc(izipobject
*lz
)
2261 PyObject_GC_UnTrack(lz
);
2262 Py_XDECREF(lz
->ittuple
);
2263 Py_XDECREF(lz
->result
);
2264 Py_TYPE(lz
)->tp_free(lz
);
2268 izip_traverse(izipobject
*lz
, visitproc visit
, void *arg
)
2270 Py_VISIT(lz
->ittuple
);
2271 Py_VISIT(lz
->result
);
2276 izip_next(izipobject
*lz
)
2279 Py_ssize_t tuplesize
= lz
->tuplesize
;
2280 PyObject
*result
= lz
->result
;
2287 if (Py_REFCNT(result
) == 1) {
2289 for (i
=0 ; i
< tuplesize
; i
++) {
2290 it
= PyTuple_GET_ITEM(lz
->ittuple
, i
);
2291 assert(PyIter_Check(it
));
2292 item
= (*Py_TYPE(it
)->tp_iternext
)(it
);
2297 olditem
= PyTuple_GET_ITEM(result
, i
);
2298 PyTuple_SET_ITEM(result
, i
, item
);
2302 result
= PyTuple_New(tuplesize
);
2305 for (i
=0 ; i
< tuplesize
; i
++) {
2306 it
= PyTuple_GET_ITEM(lz
->ittuple
, i
);
2307 assert(PyIter_Check(it
));
2308 item
= (*Py_TYPE(it
)->tp_iternext
)(it
);
2313 PyTuple_SET_ITEM(result
, i
, item
);
2319 PyDoc_STRVAR(izip_doc
,
2320 "izip(iter1 [,iter2 [...]]) --> izip object\n\
2322 Return a izip object whose .next() method returns a tuple where\n\
2323 the i-th element comes from the i-th iterable argument. The .next()\n\
2324 method continues until the shortest iterable in the argument sequence\n\
2325 is exhausted and then it raises StopIteration. Works like the zip()\n\
2326 function but consumes less memory by returning an iterator instead of\n\
2329 static PyTypeObject izip_type
= {
2330 PyVarObject_HEAD_INIT(NULL
, 0)
2331 "itertools.izip", /* tp_name */
2332 sizeof(izipobject
), /* tp_basicsize */
2333 0, /* tp_itemsize */
2335 (destructor
)izip_dealloc
, /* tp_dealloc */
2341 0, /* tp_as_number */
2342 0, /* tp_as_sequence */
2343 0, /* tp_as_mapping */
2347 PyObject_GenericGetAttr
, /* tp_getattro */
2348 0, /* tp_setattro */
2349 0, /* tp_as_buffer */
2350 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2351 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2352 izip_doc
, /* tp_doc */
2353 (traverseproc
)izip_traverse
, /* tp_traverse */
2355 0, /* tp_richcompare */
2356 0, /* tp_weaklistoffset */
2357 PyObject_SelfIter
, /* tp_iter */
2358 (iternextfunc
)izip_next
, /* tp_iternext */
2364 0, /* tp_descr_get */
2365 0, /* tp_descr_set */
2366 0, /* tp_dictoffset */
2369 izip_new
, /* tp_new */
2370 PyObject_GC_Del
, /* tp_free */
2374 /* repeat object ************************************************************/
2382 static PyTypeObject repeat_type
;
2385 repeat_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2389 Py_ssize_t cnt
= -1;
2391 if (type
== &repeat_type
&& !_PyArg_NoKeywords("repeat()", kwds
))
2394 if (!PyArg_ParseTuple(args
, "O|n:repeat", &element
, &cnt
))
2397 if (PyTuple_Size(args
) == 2 && cnt
< 0)
2400 ro
= (repeatobject
*)type
->tp_alloc(type
, 0);
2404 ro
->element
= element
;
2406 return (PyObject
*)ro
;
2410 repeat_dealloc(repeatobject
*ro
)
2412 PyObject_GC_UnTrack(ro
);
2413 Py_XDECREF(ro
->element
);
2414 Py_TYPE(ro
)->tp_free(ro
);
2418 repeat_traverse(repeatobject
*ro
, visitproc visit
, void *arg
)
2420 Py_VISIT(ro
->element
);
2425 repeat_next(repeatobject
*ro
)
2431 Py_INCREF(ro
->element
);
2436 repeat_repr(repeatobject
*ro
)
2438 PyObject
*result
, *objrepr
;
2440 objrepr
= PyObject_Repr(ro
->element
);
2441 if (objrepr
== NULL
)
2445 result
= PyString_FromFormat("repeat(%s)",
2446 PyString_AS_STRING(objrepr
));
2448 result
= PyString_FromFormat("repeat(%s, %zd)",
2449 PyString_AS_STRING(objrepr
), ro
->cnt
);
2455 repeat_len(repeatobject
*ro
)
2457 if (ro
->cnt
== -1) {
2458 PyErr_SetString(PyExc_TypeError
, "len() of unsized object");
2461 return PyInt_FromSize_t(ro
->cnt
);
2464 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
2466 static PyMethodDef repeat_methods
[] = {
2467 {"__length_hint__", (PyCFunction
)repeat_len
, METH_NOARGS
, length_hint_doc
},
2468 {NULL
, NULL
} /* sentinel */
2471 PyDoc_STRVAR(repeat_doc
,
2472 "repeat(element [,times]) -> create an iterator which returns the element\n\
2473 for the specified number of times. If not specified, returns the element\n\
2476 static PyTypeObject repeat_type
= {
2477 PyVarObject_HEAD_INIT(NULL
, 0)
2478 "itertools.repeat", /* tp_name */
2479 sizeof(repeatobject
), /* tp_basicsize */
2480 0, /* tp_itemsize */
2482 (destructor
)repeat_dealloc
, /* tp_dealloc */
2487 (reprfunc
)repeat_repr
, /* tp_repr */
2488 0, /* tp_as_number */
2489 0, /* tp_as_sequence */
2490 0, /* tp_as_mapping */
2494 PyObject_GenericGetAttr
, /* tp_getattro */
2495 0, /* tp_setattro */
2496 0, /* tp_as_buffer */
2497 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2498 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2499 repeat_doc
, /* tp_doc */
2500 (traverseproc
)repeat_traverse
, /* tp_traverse */
2502 0, /* tp_richcompare */
2503 0, /* tp_weaklistoffset */
2504 PyObject_SelfIter
, /* tp_iter */
2505 (iternextfunc
)repeat_next
, /* tp_iternext */
2506 repeat_methods
, /* tp_methods */
2511 0, /* tp_descr_get */
2512 0, /* tp_descr_set */
2513 0, /* tp_dictoffset */
2516 repeat_new
, /* tp_new */
2517 PyObject_GC_Del
, /* tp_free */
2520 /* iziplongest object ************************************************************/
2526 Py_ssize_t tuplesize
;
2527 Py_ssize_t numactive
;
2528 PyObject
*ittuple
; /* tuple of iterators */
2530 PyObject
*fillvalue
;
2531 } iziplongestobject
;
2533 static PyTypeObject iziplongest_type
;
2536 izip_longest_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2538 iziplongestobject
*lz
;
2540 PyObject
*ittuple
; /* tuple of iterators */
2542 PyObject
*fillvalue
= Py_None
;
2543 Py_ssize_t tuplesize
= PySequence_Length(args
);
2545 if (kwds
!= NULL
&& PyDict_CheckExact(kwds
) && PyDict_Size(kwds
) > 0) {
2546 fillvalue
= PyDict_GetItemString(kwds
, "fillvalue");
2547 if (fillvalue
== NULL
|| PyDict_Size(kwds
) > 1) {
2548 PyErr_SetString(PyExc_TypeError
,
2549 "izip_longest() got an unexpected keyword argument");
2554 /* args must be a tuple */
2555 assert(PyTuple_Check(args
));
2557 /* obtain iterators */
2558 ittuple
= PyTuple_New(tuplesize
);
2559 if (ittuple
== NULL
)
2561 for (i
=0; i
< tuplesize
; ++i
) {
2562 PyObject
*item
= PyTuple_GET_ITEM(args
, i
);
2563 PyObject
*it
= PyObject_GetIter(item
);
2565 if (PyErr_ExceptionMatches(PyExc_TypeError
))
2566 PyErr_Format(PyExc_TypeError
,
2567 "izip_longest argument #%zd must support iteration",
2572 PyTuple_SET_ITEM(ittuple
, i
, it
);
2575 /* create a result holder */
2576 result
= PyTuple_New(tuplesize
);
2577 if (result
== NULL
) {
2581 for (i
=0 ; i
< tuplesize
; i
++) {
2583 PyTuple_SET_ITEM(result
, i
, Py_None
);
2586 /* create iziplongestobject structure */
2587 lz
= (iziplongestobject
*)type
->tp_alloc(type
, 0);
2593 lz
->ittuple
= ittuple
;
2594 lz
->tuplesize
= tuplesize
;
2595 lz
->numactive
= tuplesize
;
2596 lz
->result
= result
;
2597 Py_INCREF(fillvalue
);
2598 lz
->fillvalue
= fillvalue
;
2599 return (PyObject
*)lz
;
2603 izip_longest_dealloc(iziplongestobject
*lz
)
2605 PyObject_GC_UnTrack(lz
);
2606 Py_XDECREF(lz
->ittuple
);
2607 Py_XDECREF(lz
->result
);
2608 Py_XDECREF(lz
->fillvalue
);
2609 Py_TYPE(lz
)->tp_free(lz
);
2613 izip_longest_traverse(iziplongestobject
*lz
, visitproc visit
, void *arg
)
2615 Py_VISIT(lz
->ittuple
);
2616 Py_VISIT(lz
->result
);
2617 Py_VISIT(lz
->fillvalue
);
2622 izip_longest_next(iziplongestobject
*lz
)
2625 Py_ssize_t tuplesize
= lz
->tuplesize
;
2626 PyObject
*result
= lz
->result
;
2633 if (lz
->numactive
== 0)
2635 if (Py_REFCNT(result
) == 1) {
2637 for (i
=0 ; i
< tuplesize
; i
++) {
2638 it
= PyTuple_GET_ITEM(lz
->ittuple
, i
);
2640 Py_INCREF(lz
->fillvalue
);
2641 item
= lz
->fillvalue
;
2643 assert(PyIter_Check(it
));
2644 item
= (*Py_TYPE(it
)->tp_iternext
)(it
);
2647 if (lz
->numactive
== 0) {
2651 Py_INCREF(lz
->fillvalue
);
2652 item
= lz
->fillvalue
;
2653 PyTuple_SET_ITEM(lz
->ittuple
, i
, NULL
);
2658 olditem
= PyTuple_GET_ITEM(result
, i
);
2659 PyTuple_SET_ITEM(result
, i
, item
);
2663 result
= PyTuple_New(tuplesize
);
2666 for (i
=0 ; i
< tuplesize
; i
++) {
2667 it
= PyTuple_GET_ITEM(lz
->ittuple
, i
);
2669 Py_INCREF(lz
->fillvalue
);
2670 item
= lz
->fillvalue
;
2672 assert(PyIter_Check(it
));
2673 item
= (*Py_TYPE(it
)->tp_iternext
)(it
);
2676 if (lz
->numactive
== 0) {
2680 Py_INCREF(lz
->fillvalue
);
2681 item
= lz
->fillvalue
;
2682 PyTuple_SET_ITEM(lz
->ittuple
, i
, NULL
);
2687 PyTuple_SET_ITEM(result
, i
, item
);
2693 PyDoc_STRVAR(izip_longest_doc
,
2694 "izip_longest(iter1 [,iter2 [...]], [fillvalue=None]) --> izip_longest object\n\
2696 Return an izip_longest object whose .next() method returns a tuple where\n\
2697 the i-th element comes from the i-th iterable argument. The .next()\n\
2698 method continues until the longest iterable in the argument sequence\n\
2699 is exhausted and then it raises StopIteration. When the shorter iterables\n\
2700 are exhausted, the fillvalue is substituted in their place. The fillvalue\n\
2701 defaults to None or can be specified by a keyword argument.\n\
2704 static PyTypeObject iziplongest_type
= {
2705 PyVarObject_HEAD_INIT(NULL
, 0)
2706 "itertools.izip_longest", /* tp_name */
2707 sizeof(iziplongestobject
), /* tp_basicsize */
2708 0, /* tp_itemsize */
2710 (destructor
)izip_longest_dealloc
, /* tp_dealloc */
2716 0, /* tp_as_number */
2717 0, /* tp_as_sequence */
2718 0, /* tp_as_mapping */
2722 PyObject_GenericGetAttr
, /* tp_getattro */
2723 0, /* tp_setattro */
2724 0, /* tp_as_buffer */
2725 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2726 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2727 izip_longest_doc
, /* tp_doc */
2728 (traverseproc
)izip_longest_traverse
, /* tp_traverse */
2730 0, /* tp_richcompare */
2731 0, /* tp_weaklistoffset */
2732 PyObject_SelfIter
, /* tp_iter */
2733 (iternextfunc
)izip_longest_next
, /* tp_iternext */
2739 0, /* tp_descr_get */
2740 0, /* tp_descr_set */
2741 0, /* tp_dictoffset */
2744 izip_longest_new
, /* tp_new */
2745 PyObject_GC_Del
, /* tp_free */
2748 /* module level code ********************************************************/
2750 PyDoc_STRVAR(module_doc
,
2751 "Functional tools for creating and using iterators.\n\
2753 Infinite iterators:\n\
2754 count([n]) --> n, n+1, n+2, ...\n\
2755 cycle(p) --> p0, p1, ... plast, p0, p1, ...\n\
2756 repeat(elem [,n]) --> elem, elem, elem, ... endlessly or up to n times\n\
2758 Iterators terminating on the shortest input sequence:\n\
2759 izip(p, q, ...) --> (p[0], q[0]), (p[1], q[1]), ... \n\
2760 izip_longest(p, q, ...) --> (p[0], q[0]), (p[1], q[1]), ... \n\
2761 ifilter(pred, seq) --> elements of seq where pred(elem) is True\n\
2762 ifilterfalse(pred, seq) --> elements of seq where pred(elem) is False\n\
2763 islice(seq, [start,] stop [, step]) --> elements from\n\
2764 seq[start:stop:step]\n\
2765 imap(fun, p, q, ...) --> fun(p0, q0), fun(p1, q1), ...\n\
2766 starmap(fun, seq) --> fun(*seq[0]), fun(*seq[1]), ...\n\
2767 tee(it, n=2) --> (it1, it2 , ... itn) splits one iterator into n\n\
2768 chain(p, q, ...) --> p0, p1, ... plast, q0, q1, ... \n\
2769 takewhile(pred, seq) --> seq[0], seq[1], until pred fails\n\
2770 dropwhile(pred, seq) --> seq[n], seq[n+1], starting when pred fails\n\
2771 groupby(iterable[, keyfunc]) --> sub-iterators grouped by value of keyfunc(v)\n\
2775 static PyMethodDef module_methods
[] = {
2776 {"tee", (PyCFunction
)tee
, METH_VARARGS
, tee_doc
},
2777 {NULL
, NULL
} /* sentinel */
2786 PyTypeObject
*typelist
[] = {
2804 Py_TYPE(&teedataobject_type
) = &PyType_Type
;
2805 m
= Py_InitModule3("itertools", module_methods
, module_doc
);
2809 for (i
=0 ; typelist
[i
] != NULL
; i
++) {
2810 if (PyType_Ready(typelist
[i
]) < 0)
2812 name
= strchr(typelist
[i
]->tp_name
, '.');
2813 assert (name
!= NULL
);
2814 Py_INCREF(typelist
[i
]);
2815 PyModule_AddObject(m
, name
+1, (PyObject
*)typelist
[i
]);
2818 if (PyType_Ready(&teedataobject_type
) < 0)
2820 if (PyType_Ready(&tee_type
) < 0)
2822 if (PyType_Ready(&_grouper_type
) < 0)