Context Navigation

itertoolsmodule.c

Visit:

Last change on this file was 3225, checked in by bird, 18 years ago
Python 2.5
File size: 56.8 KB

Line
1
2	#include "Python.h"
3	#include "structmember.h"
4
5	/* Itertools module written and maintained
6	by Raymond D. Hettinger <python@rcn.com>
7	Copyright (c) 2003 Python Software Foundation.
8	All rights reserved.
9	*/
10
11
12	/* groupby object ***********************************************************/
13
14	typedef struct {
15	PyObject_HEAD
16	PyObject *it;
17	PyObject *keyfunc;
18	PyObject *tgtkey;
19	PyObject *currkey;
20	PyObject *currvalue;
21	} groupbyobject;
22
23	static PyTypeObject groupby_type;
24	static PyObject _grouper_create(groupbyobject , PyObject *);
25
26	static PyObject *
27	groupby_new(PyTypeObject type, PyObject args, PyObject *kwds)
28	{
29	static char *kwargs[] = {"iterable", "key", NULL};
30	groupbyobject *gbo;
31	PyObject it, keyfunc = Py_None;
32
33	if (!PyArg_ParseTupleAndKeywords(args, kwds, "O\|O:groupby", kwargs,
34	&it, &keyfunc))
35	return NULL;
36
37	gbo = (groupbyobject *)type->tp_alloc(type, 0);
38	if (gbo == NULL)
39	return NULL;
40	gbo->tgtkey = NULL;
41	gbo->currkey = NULL;
42	gbo->currvalue = NULL;
43	gbo->keyfunc = keyfunc;
44	Py_INCREF(keyfunc);
45	gbo->it = PyObject_GetIter(it);
46	if (gbo->it == NULL) {
47	Py_DECREF(gbo);
48	return NULL;
49	}
50	return (PyObject *)gbo;
51	}
52
53	static void
54	groupby_dealloc(groupbyobject *gbo)
55	{
56	PyObject_GC_UnTrack(gbo);
57	Py_XDECREF(gbo->it);
58	Py_XDECREF(gbo->keyfunc);
59	Py_XDECREF(gbo->tgtkey);
60	Py_XDECREF(gbo->currkey);
61	Py_XDECREF(gbo->currvalue);
62	gbo->ob_type->tp_free(gbo);
63	}
64
65	static int
66	groupby_traverse(groupbyobject gbo, visitproc visit, void arg)
67	{
68	Py_VISIT(gbo->it);
69	Py_VISIT(gbo->keyfunc);
70	Py_VISIT(gbo->tgtkey);
71	Py_VISIT(gbo->currkey);
72	Py_VISIT(gbo->currvalue);
73	return 0;
74	}
75
76	static PyObject *
77	groupby_next(groupbyobject *gbo)
78	{
79	PyObject newvalue, newkey, r, grouper, *tmp;
80
81	/* skip to next iteration group */
82	for (;;) {
83	if (gbo->currkey == NULL)
84	/* pass */;
85	else if (gbo->tgtkey == NULL)
86	break;
87	else {
88	int rcmp;
89
90	rcmp = PyObject_RichCompareBool(gbo->tgtkey,
91	gbo->currkey, Py_EQ);
92	if (rcmp == -1)
93	return NULL;
94	else if (rcmp == 0)
95	break;
96	}
97
98	newvalue = PyIter_Next(gbo->it);
99	if (newvalue == NULL)
100	return NULL;
101
102	if (gbo->keyfunc == Py_None) {
103	newkey = newvalue;
104	Py_INCREF(newvalue);
105	} else {
106	newkey = PyObject_CallFunctionObjArgs(gbo->keyfunc,
107	newvalue, NULL);
108	if (newkey == NULL) {
109	Py_DECREF(newvalue);
110	return NULL;
111	}
112	}
113
114	tmp = gbo->currkey;
115	gbo->currkey = newkey;
116	Py_XDECREF(tmp);
117
118	tmp = gbo->currvalue;
119	gbo->currvalue = newvalue;
120	Py_XDECREF(tmp);
121	}
122
123	Py_INCREF(gbo->currkey);
124	tmp = gbo->tgtkey;
125	gbo->tgtkey = gbo->currkey;
126	Py_XDECREF(tmp);
127
128	grouper = _grouper_create(gbo, gbo->tgtkey);
129	if (grouper == NULL)
130	return NULL;
131
132	r = PyTuple_Pack(2, gbo->currkey, grouper);
133	Py_DECREF(grouper);
134	return r;
135	}
136
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");
140
141	static PyTypeObject groupby_type = {
142	PyObject_HEAD_INIT(NULL)
143	0, /* ob_size */
144	"itertools.groupby", /* tp_name */
145	sizeof(groupbyobject), /* tp_basicsize */
146	0, /* tp_itemsize */
147	/* methods */
148	(destructor)groupby_dealloc, /* tp_dealloc */
149	0, /* tp_print */
150	0, /* tp_getattr */
151	0, /* tp_setattr */
152	0, /* tp_compare */
153	0, /* tp_repr */
154	0, /* tp_as_number */
155	0, /* tp_as_sequence */
156	0, /* tp_as_mapping */
157	0, /* tp_hash */
158	0, /* tp_call */
159	0, /* tp_str */
160	PyObject_GenericGetAttr, /* tp_getattro */
161	0, /* tp_setattro */
162	0, /* tp_as_buffer */
163	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
164	Py_TPFLAGS_BASETYPE, /* tp_flags */
165	groupby_doc, /* tp_doc */
166	(traverseproc)groupby_traverse, /* tp_traverse */
167	0, /* tp_clear */
168	0, /* tp_richcompare */
169	0, /* tp_weaklistoffset */
170	PyObject_SelfIter, /* tp_iter */
171	(iternextfunc)groupby_next, /* tp_iternext */
172	0, /* tp_methods */
173	0, /* tp_members */
174	0, /* tp_getset */
175	0, /* tp_base */
176	0, /* tp_dict */
177	0, /* tp_descr_get */
178	0, /* tp_descr_set */
179	0, /* tp_dictoffset */
180	0, /* tp_init */
181	0, /* tp_alloc */
182	groupby_new, /* tp_new */
183	PyObject_GC_Del, /* tp_free */
184	};
185
186
187	/* _grouper object (internal) ************************************************/
188
189	typedef struct {
190	PyObject_HEAD
191	PyObject *parent;
192	PyObject *tgtkey;
193	} _grouperobject;
194
195	static PyTypeObject _grouper_type;
196
197	static PyObject *
198	_grouper_create(groupbyobject parent, PyObject tgtkey)
199	{
200	_grouperobject *igo;
201
202	igo = PyObject_New(_grouperobject, &_grouper_type);
203	if (igo == NULL)
204	return NULL;
205	igo->parent = (PyObject *)parent;
206	Py_INCREF(parent);
207	igo->tgtkey = tgtkey;
208	Py_INCREF(tgtkey);
209
210	return (PyObject *)igo;
211	}
212
213	static void
214	_grouper_dealloc(_grouperobject *igo)
215	{
216	Py_DECREF(igo->parent);
217	Py_DECREF(igo->tgtkey);
218	PyObject_Del(igo);
219	}
220
221	static PyObject *
222	_grouper_next(_grouperobject *igo)
223	{
224	groupbyobject gbo = (groupbyobject )igo->parent;
225	PyObject newvalue, newkey, *r;
226	int rcmp;
227
228	if (gbo->currvalue == NULL) {
229	newvalue = PyIter_Next(gbo->it);
230	if (newvalue == NULL)
231	return NULL;
232
233	if (gbo->keyfunc == Py_None) {
234	newkey = newvalue;
235	Py_INCREF(newvalue);
236	} else {
237	newkey = PyObject_CallFunctionObjArgs(gbo->keyfunc,
238	newvalue, NULL);
239	if (newkey == NULL) {
240	Py_DECREF(newvalue);
241	return NULL;
242	}
243	}
244
245	assert(gbo->currkey == NULL);
246	gbo->currkey = newkey;
247	gbo->currvalue = newvalue;
248	}
249
250	assert(gbo->currkey != NULL);
251	rcmp = PyObject_RichCompareBool(igo->tgtkey, gbo->currkey, Py_EQ);
252	if (rcmp <= 0)
253	/* got any error or current group is end */
254	return NULL;
255
256	r = gbo->currvalue;
257	gbo->currvalue = NULL;
258	Py_CLEAR(gbo->currkey);
259
260	return r;
261	}
262
263	static PyTypeObject _grouper_type = {
264	PyObject_HEAD_INIT(NULL)
265	0, /* ob_size */
266	"itertools._grouper", /* tp_name */
267	sizeof(_grouperobject), /* tp_basicsize */
268	0, /* tp_itemsize */
269	/* methods */
270	(destructor)_grouper_dealloc, /* tp_dealloc */
271	0, /* tp_print */
272	0, /* tp_getattr */
273	0, /* tp_setattr */
274	0, /* tp_compare */
275	0, /* tp_repr */
276	0, /* tp_as_number */
277	0, /* tp_as_sequence */
278	0, /* tp_as_mapping */
279	0, /* tp_hash */
280	0, /* tp_call */
281	0, /* tp_str */
282	PyObject_GenericGetAttr, /* tp_getattro */
283	0, /* tp_setattro */
284	0, /* tp_as_buffer */
285	Py_TPFLAGS_DEFAULT, /* tp_flags */
286	0, /* tp_doc */
287	0, /* tp_traverse */
288	0, /* tp_clear */
289	0, /* tp_richcompare */
290	0, /* tp_weaklistoffset */
291	PyObject_SelfIter, /* tp_iter */
292	(iternextfunc)_grouper_next, /* tp_iternext */
293	0, /* tp_methods */
294	0, /* tp_members */
295	0, /* tp_getset */
296	0, /* tp_base */
297	0, /* tp_dict */
298	0, /* tp_descr_get */
299	0, /* tp_descr_set */
300	0, /* tp_dictoffset */
301	0, /* tp_init */
302	0, /* tp_alloc */
303	0, /* tp_new */
304	PyObject_Del, /* tp_free */
305	};
306
307
308
309	/* tee object and with supporting function and objects ***************/
310
311	/* The teedataobject pre-allocates space for LINKCELLS number of objects.
312	To help the object fit neatly inside cache lines (space for 16 to 32
313	pointers), the value should be a multiple of 16 minus space for
314	the other structure members including PyHEAD overhead. The larger the
315	value, the less memory overhead per object and the less time spent
316	allocating/deallocating new links. The smaller the number, the less
317	wasted space and the more rapid freeing of older data.
318	*/
319	#define LINKCELLS 57
320
321	typedef struct {
322	PyObject_HEAD
323	PyObject *it;
324	int numread;
325	PyObject *nextlink;
326	PyObject *(values[LINKCELLS]);
327	} teedataobject;
328
329	typedef struct {
330	PyObject_HEAD
331	teedataobject *dataobj;
332	int index;
333	PyObject *weakreflist;
334	} teeobject;
335
336	static PyTypeObject teedataobject_type;
337
338	static PyObject *
339	teedataobject_new(PyObject *it)
340	{
341	teedataobject *tdo;
342
343	tdo = PyObject_GC_New(teedataobject, &teedataobject_type);
344	if (tdo == NULL)
345	return NULL;
346
347	tdo->numread = 0;
348	tdo->nextlink = NULL;
349	Py_INCREF(it);
350	tdo->it = it;
351	PyObject_GC_Track(tdo);
352	return (PyObject *)tdo;
353	}
354
355	static PyObject *
356	teedataobject_jumplink(teedataobject *tdo)
357	{
358	if (tdo->nextlink == NULL)
359	tdo->nextlink = teedataobject_new(tdo->it);
360	Py_XINCREF(tdo->nextlink);
361	return tdo->nextlink;
362	}
363
364	static PyObject *
365	teedataobject_getitem(teedataobject *tdo, int i)
366	{
367	PyObject *value;
368
369	assert(i < LINKCELLS);
370	if (i < tdo->numread)
371	value = tdo->values[i];
372	else {
373	/* this is the lead iterator, so fetch more data */
374	assert(i == tdo->numread);
375	value = PyIter_Next(tdo->it);
376	if (value == NULL)
377	return NULL;
378	tdo->numread++;
379	tdo->values[i] = value;
380	}
381	Py_INCREF(value);
382	return value;
383	}
384
385	static int
386	teedataobject_traverse(teedataobject tdo, visitproc visit, void arg)
387	{
388	int i;
389	Py_VISIT(tdo->it);
390	for (i = 0; i < tdo->numread; i++)
391	Py_VISIT(tdo->values[i]);
392	Py_VISIT(tdo->nextlink);
393	return 0;
394	}
395
396	static int
397	teedataobject_clear(teedataobject *tdo)
398	{
399	int i;
400	Py_CLEAR(tdo->it);
401	for (i=0 ; i<tdo->numread ; i++)
402	Py_CLEAR(tdo->values[i]);
403	Py_CLEAR(tdo->nextlink);
404	return 0;
405	}
406
407	static void
408	teedataobject_dealloc(teedataobject *tdo)
409	{
410	PyObject_GC_UnTrack(tdo);
411	teedataobject_clear(tdo);
412	PyObject_GC_Del(tdo);
413	}
414
415	PyDoc_STRVAR(teedataobject_doc, "Data container common to multiple tee objects.");
416
417	static PyTypeObject teedataobject_type = {
418	PyObject_HEAD_INIT(0) /* Must fill in type value later */
419	0, /* ob_size */
420	"itertools.tee_dataobject", /* tp_name */
421	sizeof(teedataobject), /* tp_basicsize */
422	0, /* tp_itemsize */
423	/* methods */
424	(destructor)teedataobject_dealloc, /* tp_dealloc */
425	0, /* tp_print */
426	0, /* tp_getattr */
427	0, /* tp_setattr */
428	0, /* tp_compare */
429	0, /* tp_repr */
430	0, /* tp_as_number */
431	0, /* tp_as_sequence */
432	0, /* tp_as_mapping */
433	0, /* tp_hash */
434	0, /* tp_call */
435	0, /* tp_str */
436	PyObject_GenericGetAttr, /* tp_getattro */
437	0, /* tp_setattro */
438	0, /* tp_as_buffer */
439	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC, /* tp_flags */
440	teedataobject_doc, /* tp_doc */
441	(traverseproc)teedataobject_traverse, /* tp_traverse */
442	(inquiry)teedataobject_clear, /* tp_clear */
443	0, /* tp_richcompare */
444	0, /* tp_weaklistoffset */
445	0, /* tp_iter */
446	0, /* tp_iternext */
447	0, /* tp_methods */
448	0, /* tp_members */
449	0, /* tp_getset */
450	0, /* tp_base */
451	0, /* tp_dict */
452	0, /* tp_descr_get */
453	0, /* tp_descr_set */
454	0, /* tp_dictoffset */
455	0, /* tp_init */
456	0, /* tp_alloc */
457	0, /* tp_new */
458	PyObject_GC_Del, /* tp_free */
459	};
460
461
462	static PyTypeObject tee_type;
463
464	static PyObject *
465	tee_next(teeobject *to)
466	{
467	PyObject value, link;
468
469	if (to->index >= LINKCELLS) {
470	link = teedataobject_jumplink(to->dataobj);
471	Py_DECREF(to->dataobj);
472	to->dataobj = (teedataobject *)link;
473	to->index = 0;
474	}
475	value = teedataobject_getitem(to->dataobj, to->index);
476	if (value == NULL)
477	return NULL;
478	to->index++;
479	return value;
480	}
481
482	static int
483	tee_traverse(teeobject to, visitproc visit, void arg)
484	{
485	Py_VISIT((PyObject *)to->dataobj);
486	return 0;
487	}
488
489	static PyObject *
490	tee_copy(teeobject *to)
491	{
492	teeobject *newto;
493
494	newto = PyObject_GC_New(teeobject, &tee_type);
495	if (newto == NULL)
496	return NULL;
497	Py_INCREF(to->dataobj);
498	newto->dataobj = to->dataobj;
499	newto->index = to->index;
500	newto->weakreflist = NULL;
501	PyObject_GC_Track(newto);
502	return (PyObject *)newto;
503	}
504
505	PyDoc_STRVAR(teecopy_doc, "Returns an independent iterator.");
506
507	static PyObject *
508	tee_fromiterable(PyObject *iterable)
509	{
510	teeobject *to;
511	PyObject *it = NULL;
512
513	it = PyObject_GetIter(iterable);
514	if (it == NULL)
515	return NULL;
516	if (PyObject_TypeCheck(it, &tee_type)) {
517	to = (teeobject )tee_copy((teeobject )it);
518	goto done;
519	}
520
521	to = PyObject_GC_New(teeobject, &tee_type);
522	if (to == NULL)
523	goto done;
524	to->dataobj = (teedataobject *)teedataobject_new(it);
525	if (!to->dataobj) {
526	PyObject_GC_Del(to);
527	to = NULL;
528	goto done;
529	}
530
531	to->index = 0;
532	to->weakreflist = NULL;
533	PyObject_GC_Track(to);
534	done:
535	Py_XDECREF(it);
536	return (PyObject *)to;
537	}
538
539	static PyObject *
540	tee_new(PyTypeObject type, PyObject args, PyObject *kw)
541	{
542	PyObject *iterable;
543
544	if (!PyArg_UnpackTuple(args, "tee", 1, 1, &iterable))
545	return NULL;
546	return tee_fromiterable(iterable);
547	}
548
549	static int
550	tee_clear(teeobject *to)
551	{
552	if (to->weakreflist != NULL)
553	PyObject_ClearWeakRefs((PyObject *) to);
554	Py_CLEAR(to->dataobj);
555	return 0;
556	}
557
558	static void
559	tee_dealloc(teeobject *to)
560	{
561	PyObject_GC_UnTrack(to);
562	tee_clear(to);
563	PyObject_GC_Del(to);
564	}
565
566	PyDoc_STRVAR(teeobject_doc,
567	"Iterator wrapped to make it copyable");
568
569	static PyMethodDef tee_methods[] = {
570	{"__copy__", (PyCFunction)tee_copy, METH_NOARGS, teecopy_doc},
571	{NULL, NULL} /* sentinel */
572	};
573
574	static PyTypeObject tee_type = {
575	PyObject_HEAD_INIT(NULL)
576	0, /* ob_size */
577	"itertools.tee", /* tp_name */
578	sizeof(teeobject), /* tp_basicsize */
579	0, /* tp_itemsize */
580	/* methods */
581	(destructor)tee_dealloc, /* tp_dealloc */
582	0, /* tp_print */
583	0, /* tp_getattr */
584	0, /* tp_setattr */
585	0, /* tp_compare */
586	0, /* tp_repr */
587	0, /* tp_as_number */
588	0, /* tp_as_sequence */
589	0, /* tp_as_mapping */
590	0, /* tp_hash */
591	0, /* tp_call */
592	0, /* tp_str */
593	0, /* tp_getattro */
594	0, /* tp_setattro */
595	0, /* tp_as_buffer */
596	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC, /* tp_flags */
597	teeobject_doc, /* tp_doc */
598	(traverseproc)tee_traverse, /* tp_traverse */
599	(inquiry)tee_clear, /* tp_clear */
600	0, /* tp_richcompare */
601	offsetof(teeobject, weakreflist), /* tp_weaklistoffset */
602	PyObject_SelfIter, /* tp_iter */
603	(iternextfunc)tee_next, /* tp_iternext */
604	tee_methods, /* tp_methods */
605	0, /* tp_members */
606	0, /* tp_getset */
607	0, /* tp_base */
608	0, /* tp_dict */
609	0, /* tp_descr_get */
610	0, /* tp_descr_set */
611	0, /* tp_dictoffset */
612	0, /* tp_init */
613	0, /* tp_alloc */
614	tee_new, /* tp_new */
615	PyObject_GC_Del, /* tp_free */
616	};
617
618	static PyObject *
619	tee(PyObject self, PyObject args)
620	{
621	Py_ssize_t i, n=2;
622	PyObject it, iterable, copyable, result;
623
624	if (!PyArg_ParseTuple(args, "O\|n", &iterable, &n))
625	return NULL;
626	if (n < 0) {
627	PyErr_SetString(PyExc_ValueError, "n must be >= 0");
628	return NULL;
629	}
630	result = PyTuple_New(n);
631	if (result == NULL)
632	return NULL;
633	if (n == 0)
634	return result;
635	it = PyObject_GetIter(iterable);
636	if (it == NULL) {
637	Py_DECREF(result);
638	return NULL;
639	}
640	if (!PyObject_HasAttrString(it, "__copy__")) {
641	copyable = tee_fromiterable(it);
642	Py_DECREF(it);
643	if (copyable == NULL) {
644	Py_DECREF(result);
645	return NULL;
646	}
647	} else
648	copyable = it;
649	PyTuple_SET_ITEM(result, 0, copyable);
650	for (i=1 ; i<n ; i++) {
651	copyable = PyObject_CallMethod(copyable, "__copy__", NULL);
652	if (copyable == NULL) {
653	Py_DECREF(result);
654	return NULL;
655	}
656	PyTuple_SET_ITEM(result, i, copyable);
657	}
658	return result;
659	}
660
661	PyDoc_STRVAR(tee_doc,
662	"tee(iterable, n=2) --> tuple of n independent iterators.");
663
664
665	/* cycle object **********************************************************/
666
667	typedef struct {
668	PyObject_HEAD
669	PyObject *it;
670	PyObject *saved;
671	int firstpass;
672	} cycleobject;
673
674	static PyTypeObject cycle_type;
675
676	static PyObject *
677	cycle_new(PyTypeObject type, PyObject args, PyObject *kwds)
678	{
679	PyObject *it;
680	PyObject *iterable;
681	PyObject *saved;
682	cycleobject *lz;
683
684	if (!_PyArg_NoKeywords("cycle()", kwds))
685	return NULL;
686
687	if (!PyArg_UnpackTuple(args, "cycle", 1, 1, &iterable))
688	return NULL;
689
690	/* Get iterator. */
691	it = PyObject_GetIter(iterable);
692	if (it == NULL)
693	return NULL;
694
695	saved = PyList_New(0);
696	if (saved == NULL) {
697	Py_DECREF(it);
698	return NULL;
699	}
700
701	/* create cycleobject structure */
702	lz = (cycleobject *)type->tp_alloc(type, 0);
703	if (lz == NULL) {
704	Py_DECREF(it);
705	Py_DECREF(saved);
706	return NULL;
707	}
708	lz->it = it;
709	lz->saved = saved;
710	lz->firstpass = 0;
711
712	return (PyObject *)lz;
713	}
714
715	static void
716	cycle_dealloc(cycleobject *lz)
717	{
718	PyObject_GC_UnTrack(lz);
719	Py_XDECREF(lz->saved);
720	Py_XDECREF(lz->it);
721	lz->ob_type->tp_free(lz);
722	}
723
724	static int
725	cycle_traverse(cycleobject lz, visitproc visit, void arg)
726	{
727	Py_VISIT(lz->it);
728	Py_VISIT(lz->saved);
729	return 0;
730	}
731
732	static PyObject *
733	cycle_next(cycleobject *lz)
734	{
735	PyObject *item;
736	PyObject *it;
737	PyObject *tmp;
738
739	while (1) {
740	item = PyIter_Next(lz->it);
741	if (item != NULL) {
742	if (!lz->firstpass)
743	PyList_Append(lz->saved, item);
744	return item;
745	}
746	if (PyErr_Occurred()) {
747	if (PyErr_ExceptionMatches(PyExc_StopIteration))
748	PyErr_Clear();
749	else
750	return NULL;
751	}
752	if (PyList_Size(lz->saved) == 0)
753	return NULL;
754	it = PyObject_GetIter(lz->saved);
755	if (it == NULL)
756	return NULL;
757	tmp = lz->it;
758	lz->it = it;
759	lz->firstpass = 1;
760	Py_DECREF(tmp);
761	}
762	}
763
764	PyDoc_STRVAR(cycle_doc,
765	"cycle(iterable) --> cycle object\n\
766	\n\
767	Return elements from the iterable until it is exhausted.\n\
768	Then repeat the sequence indefinitely.");
769
770	static PyTypeObject cycle_type = {
771	PyObject_HEAD_INIT(NULL)
772	0, /* ob_size */
773	"itertools.cycle", /* tp_name */
774	sizeof(cycleobject), /* tp_basicsize */
775	0, /* tp_itemsize */
776	/* methods */
777	(destructor)cycle_dealloc, /* tp_dealloc */
778	0, /* tp_print */
779	0, /* tp_getattr */
780	0, /* tp_setattr */
781	0, /* tp_compare */
782	0, /* tp_repr */
783	0, /* tp_as_number */
784	0, /* tp_as_sequence */
785	0, /* tp_as_mapping */
786	0, /* tp_hash */
787	0, /* tp_call */
788	0, /* tp_str */
789	PyObject_GenericGetAttr, /* tp_getattro */
790	0, /* tp_setattro */
791	0, /* tp_as_buffer */
792	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
793	Py_TPFLAGS_BASETYPE, /* tp_flags */
794	cycle_doc, /* tp_doc */
795	(traverseproc)cycle_traverse, /* tp_traverse */
796	0, /* tp_clear */
797	0, /* tp_richcompare */
798	0, /* tp_weaklistoffset */
799	PyObject_SelfIter, /* tp_iter */
800	(iternextfunc)cycle_next, /* tp_iternext */
801	0, /* tp_methods */
802	0, /* tp_members */
803	0, /* tp_getset */
804	0, /* tp_base */
805	0, /* tp_dict */
806	0, /* tp_descr_get */
807	0, /* tp_descr_set */
808	0, /* tp_dictoffset */
809	0, /* tp_init */
810	0, /* tp_alloc */
811	cycle_new, /* tp_new */
812	PyObject_GC_Del, /* tp_free */
813	};
814
815
816	/* dropwhile object **********************************************************/
817
818	typedef struct {
819	PyObject_HEAD
820	PyObject *func;
821	PyObject *it;
822	long start;
823	} dropwhileobject;
824
825	static PyTypeObject dropwhile_type;
826
827	static PyObject *
828	dropwhile_new(PyTypeObject type, PyObject args, PyObject *kwds)
829	{
830	PyObject func, seq;
831	PyObject *it;
832	dropwhileobject *lz;
833
834	if (!_PyArg_NoKeywords("dropwhile()", kwds))
835	return NULL;
836
837	if (!PyArg_UnpackTuple(args, "dropwhile", 2, 2, &func, &seq))
838	return NULL;
839
840	/* Get iterator. */
841	it = PyObject_GetIter(seq);
842	if (it == NULL)
843	return NULL;
844
845	/* create dropwhileobject structure */
846	lz = (dropwhileobject *)type->tp_alloc(type, 0);
847	if (lz == NULL) {
848	Py_DECREF(it);
849	return NULL;
850	}
851	Py_INCREF(func);
852	lz->func = func;
853	lz->it = it;
854	lz->start = 0;
855
856	return (PyObject *)lz;
857	}
858
859	static void
860	dropwhile_dealloc(dropwhileobject *lz)
861	{
862	PyObject_GC_UnTrack(lz);
863	Py_XDECREF(lz->func);
864	Py_XDECREF(lz->it);
865	lz->ob_type->tp_free(lz);
866	}
867
868	static int
869	dropwhile_traverse(dropwhileobject lz, visitproc visit, void arg)
870	{
871	Py_VISIT(lz->it);
872	Py_VISIT(lz->func);
873	return 0;
874	}
875
876	static PyObject *
877	dropwhile_next(dropwhileobject *lz)
878	{
879	PyObject item, good;
880	PyObject *it = lz->it;
881	long ok;
882	PyObject (iternext)(PyObject *);
883
884	assert(PyIter_Check(it));
885	iternext = *it->ob_type->tp_iternext;
886	for (;;) {
887	item = iternext(it);
888	if (item == NULL)
889	return NULL;
890	if (lz->start == 1)
891	return item;
892
893	good = PyObject_CallFunctionObjArgs(lz->func, item, NULL);
894	if (good == NULL) {
895	Py_DECREF(item);
896	return NULL;
897	}
898	ok = PyObject_IsTrue(good);
899	Py_DECREF(good);
900	if (!ok) {
901	lz->start = 1;
902	return item;
903	}
904	Py_DECREF(item);
905	}
906	}
907
908	PyDoc_STRVAR(dropwhile_doc,
909	"dropwhile(predicate, iterable) --> dropwhile object\n\
910	\n\
911	Drop items from the iterable while predicate(item) is true.\n\
912	Afterwards, return every element until the iterable is exhausted.");
913
914	static PyTypeObject dropwhile_type = {
915	PyObject_HEAD_INIT(NULL)
916	0, /* ob_size */
917	"itertools.dropwhile", /* tp_name */
918	sizeof(dropwhileobject), /* tp_basicsize */
919	0, /* tp_itemsize */
920	/* methods */
921	(destructor)dropwhile_dealloc, /* tp_dealloc */
922	0, /* tp_print */
923	0, /* tp_getattr */
924	0, /* tp_setattr */
925	0, /* tp_compare */
926	0, /* tp_repr */
927	0, /* tp_as_number */
928	0, /* tp_as_sequence */
929	0, /* tp_as_mapping */
930	0, /* tp_hash */
931	0, /* tp_call */
932	0, /* tp_str */
933	PyObject_GenericGetAttr, /* tp_getattro */
934	0, /* tp_setattro */
935	0, /* tp_as_buffer */
936	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
937	Py_TPFLAGS_BASETYPE, /* tp_flags */
938	dropwhile_doc, /* tp_doc */
939	(traverseproc)dropwhile_traverse, /* tp_traverse */
940	0, /* tp_clear */
941	0, /* tp_richcompare */
942	0, /* tp_weaklistoffset */
943	PyObject_SelfIter, /* tp_iter */
944	(iternextfunc)dropwhile_next, /* tp_iternext */
945	0, /* tp_methods */
946	0, /* tp_members */
947	0, /* tp_getset */
948	0, /* tp_base */
949	0, /* tp_dict */
950	0, /* tp_descr_get */
951	0, /* tp_descr_set */
952	0, /* tp_dictoffset */
953	0, /* tp_init */
954	0, /* tp_alloc */
955	dropwhile_new, /* tp_new */
956	PyObject_GC_Del, /* tp_free */
957	};
958
959
960	/* takewhile object **********************************************************/
961
962	typedef struct {
963	PyObject_HEAD
964	PyObject *func;
965	PyObject *it;
966	long stop;
967	} takewhileobject;
968
969	static PyTypeObject takewhile_type;
970
971	static PyObject *
972	takewhile_new(PyTypeObject type, PyObject args, PyObject *kwds)
973	{
974	PyObject func, seq;
975	PyObject *it;
976	takewhileobject *lz;
977
978	if (!_PyArg_NoKeywords("takewhile()", kwds))
979	return NULL;
980
981	if (!PyArg_UnpackTuple(args, "takewhile", 2, 2, &func, &seq))
982	return NULL;
983
984	/* Get iterator. */
985	it = PyObject_GetIter(seq);
986	if (it == NULL)
987	return NULL;
988
989	/* create takewhileobject structure */
990	lz = (takewhileobject *)type->tp_alloc(type, 0);
991	if (lz == NULL) {
992	Py_DECREF(it);
993	return NULL;
994	}
995	Py_INCREF(func);
996	lz->func = func;
997	lz->it = it;
998	lz->stop = 0;
999
1000	return (PyObject *)lz;
1001	}
1002
1003	static void
1004	takewhile_dealloc(takewhileobject *lz)
1005	{
1006	PyObject_GC_UnTrack(lz);
1007	Py_XDECREF(lz->func);
1008	Py_XDECREF(lz->it);
1009	lz->ob_type->tp_free(lz);
1010	}
1011
1012	static int
1013	takewhile_traverse(takewhileobject lz, visitproc visit, void arg)
1014	{
1015	Py_VISIT(lz->it);
1016	Py_VISIT(lz->func);
1017	return 0;
1018	}
1019
1020	static PyObject *
1021	takewhile_next(takewhileobject *lz)
1022	{
1023	PyObject item, good;
1024	PyObject *it = lz->it;
1025	long ok;
1026
1027	if (lz->stop == 1)
1028	return NULL;
1029
1030	assert(PyIter_Check(it));
1031	item = (*it->ob_type->tp_iternext)(it);
1032	if (item == NULL)
1033	return NULL;
1034
1035	good = PyObject_CallFunctionObjArgs(lz->func, item, NULL);
1036	if (good == NULL) {
1037	Py_DECREF(item);
1038	return NULL;
1039	}
1040	ok = PyObject_IsTrue(good);
1041	Py_DECREF(good);
1042	if (ok)
1043	return item;
1044	Py_DECREF(item);
1045	lz->stop = 1;
1046	return NULL;
1047	}
1048
1049	PyDoc_STRVAR(takewhile_doc,
1050	"takewhile(predicate, iterable) --> takewhile object\n\
1051	\n\
1052	Return successive entries from an iterable as long as the \n\
1053	predicate evaluates to true for each entry.");
1054
1055	static PyTypeObject takewhile_type = {
1056	PyObject_HEAD_INIT(NULL)
1057	0, /* ob_size */
1058	"itertools.takewhile", /* tp_name */
1059	sizeof(takewhileobject), /* tp_basicsize */
1060	0, /* tp_itemsize */
1061	/* methods */
1062	(destructor)takewhile_dealloc, /* tp_dealloc */
1063	0, /* tp_print */
1064	0, /* tp_getattr */
1065	0, /* tp_setattr */
1066	0, /* tp_compare */
1067	0, /* tp_repr */
1068	0, /* tp_as_number */
1069	0, /* tp_as_sequence */
1070	0, /* tp_as_mapping */
1071	0, /* tp_hash */
1072	0, /* tp_call */
1073	0, /* tp_str */
1074	PyObject_GenericGetAttr, /* tp_getattro */
1075	0, /* tp_setattro */
1076	0, /* tp_as_buffer */
1077	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
1078	Py_TPFLAGS_BASETYPE, /* tp_flags */
1079	takewhile_doc, /* tp_doc */
1080	(traverseproc)takewhile_traverse, /* tp_traverse */
1081	0, /* tp_clear */
1082	0, /* tp_richcompare */
1083	0, /* tp_weaklistoffset */
1084	PyObject_SelfIter, /* tp_iter */
1085	(iternextfunc)takewhile_next, /* tp_iternext */
1086	0, /* tp_methods */
1087	0, /* tp_members */
1088	0, /* tp_getset */
1089	0, /* tp_base */
1090	0, /* tp_dict */
1091	0, /* tp_descr_get */
1092	0, /* tp_descr_set */
1093	0, /* tp_dictoffset */
1094	0, /* tp_init */
1095	0, /* tp_alloc */
1096	takewhile_new, /* tp_new */
1097	PyObject_GC_Del, /* tp_free */
1098	};
1099
1100
1101	/* islice object ************************************************************/
1102
1103	typedef struct {
1104	PyObject_HEAD
1105	PyObject *it;
1106	Py_ssize_t next;
1107	Py_ssize_t stop;
1108	Py_ssize_t step;
1109	Py_ssize_t cnt;
1110	} isliceobject;
1111
1112	static PyTypeObject islice_type;
1113
1114	static PyObject *
1115	islice_new(PyTypeObject type, PyObject args, PyObject *kwds)
1116	{
1117	PyObject *seq;
1118	Py_ssize_t start=0, stop=-1, step=1;
1119	PyObject it, a1=NULL, a2=NULL, a3=NULL;
1120	Py_ssize_t numargs;
1121	isliceobject *lz;
1122
1123	if (!_PyArg_NoKeywords("islice()", kwds))
1124	return NULL;
1125
1126	if (!PyArg_UnpackTuple(args, "islice", 2, 4, &seq, &a1, &a2, &a3))
1127	return NULL;
1128
1129	numargs = PyTuple_Size(args);
1130	if (numargs == 2) {
1131	if (a1 != Py_None) {
1132	stop = PyInt_AsSsize_t(a1);
1133	if (stop == -1) {
1134	if (PyErr_Occurred())
1135	PyErr_Clear();
1136	PyErr_SetString(PyExc_ValueError,
1137	"Stop argument for islice() must be a non-negative integer or None.");
1138	return NULL;
1139	}
1140	}
1141	} else {
1142	if (a1 != Py_None)
1143	start = PyInt_AsSsize_t(a1);
1144	if (start == -1 && PyErr_Occurred())
1145	PyErr_Clear();
1146	if (a2 != Py_None) {
1147	stop = PyInt_AsSsize_t(a2);
1148	if (stop == -1) {
1149	if (PyErr_Occurred())
1150	PyErr_Clear();
1151	PyErr_SetString(PyExc_ValueError,
1152	"Stop argument for islice() must be a non-negative integer or None.");
1153	return NULL;
1154	}
1155	}
1156	}
1157	if (start<0 \|\| stop<-1) {
1158	PyErr_SetString(PyExc_ValueError,
1159	"Indices for islice() must be non-negative integers or None.");
1160	return NULL;
1161	}
1162
1163	if (a3 != NULL) {
1164	if (a3 != Py_None)
1165	step = PyInt_AsSsize_t(a3);
1166	if (step == -1 && PyErr_Occurred())
1167	PyErr_Clear();
1168	}
1169	if (step<1) {
1170	PyErr_SetString(PyExc_ValueError,
1171	"Step for islice() must be a positive integer or None.");
1172	return NULL;
1173	}
1174
1175	/* Get iterator. */
1176	it = PyObject_GetIter(seq);
1177	if (it == NULL)
1178	return NULL;
1179
1180	/* create isliceobject structure */
1181	lz = (isliceobject *)type->tp_alloc(type, 0);
1182	if (lz == NULL) {
1183	Py_DECREF(it);
1184	return NULL;
1185	}
1186	lz->it = it;
1187	lz->next = start;
1188	lz->stop = stop;
1189	lz->step = step;
1190	lz->cnt = 0L;
1191
1192	return (PyObject *)lz;
1193	}
1194
1195	static void
1196	islice_dealloc(isliceobject *lz)
1197	{
1198	PyObject_GC_UnTrack(lz);
1199	Py_XDECREF(lz->it);
1200	lz->ob_type->tp_free(lz);
1201	}
1202
1203	static int
1204	islice_traverse(isliceobject lz, visitproc visit, void arg)
1205	{
1206	Py_VISIT(lz->it);
1207	return 0;
1208	}
1209
1210	static PyObject *
1211	islice_next(isliceobject *lz)
1212	{
1213	PyObject *item;
1214	PyObject *it = lz->it;
1215	Py_ssize_t oldnext;
1216	PyObject (iternext)(PyObject *);
1217
1218	assert(PyIter_Check(it));
1219	iternext = *it->ob_type->tp_iternext;
1220	while (lz->cnt < lz->next) {
1221	item = iternext(it);
1222	if (item == NULL)
1223	return NULL;
1224	Py_DECREF(item);
1225	lz->cnt++;
1226	}
1227	if (lz->stop != -1 && lz->cnt >= lz->stop)
1228	return NULL;
1229	assert(PyIter_Check(it));
1230	item = iternext(it);
1231	if (item == NULL)
1232	return NULL;
1233	lz->cnt++;
1234	oldnext = lz->next;
1235	lz->next += lz->step;
1236	if (lz->next < oldnext) /* Check for overflow */
1237	lz->next = lz->stop;
1238	return item;
1239	}
1240
1241	PyDoc_STRVAR(islice_doc,
1242	"islice(iterable, [start,] stop [, step]) --> islice object\n\
1243	\n\
1244	Return an iterator whose next() method returns selected values from an\n\
1245	iterable. If start is specified, will skip all preceding elements;\n\
1246	otherwise, start defaults to zero. Step defaults to one. If\n\
1247	specified as another value, step determines how many values are \n\
1248	skipped between successive calls. Works like a slice() on a list\n\
1249	but returns an iterator.");
1250
1251	static PyTypeObject islice_type = {
1252	PyObject_HEAD_INIT(NULL)
1253	0, /* ob_size */
1254	"itertools.islice", /* tp_name */
1255	sizeof(isliceobject), /* tp_basicsize */
1256	0, /* tp_itemsize */
1257	/* methods */
1258	(destructor)islice_dealloc, /* tp_dealloc */
1259	0, /* tp_print */
1260	0, /* tp_getattr */
1261	0, /* tp_setattr */
1262	0, /* tp_compare */
1263	0, /* tp_repr */
1264	0, /* tp_as_number */
1265	0, /* tp_as_sequence */
1266	0, /* tp_as_mapping */
1267	0, /* tp_hash */
1268	0, /* tp_call */
1269	0, /* tp_str */
1270	PyObject_GenericGetAttr, /* tp_getattro */
1271	0, /* tp_setattro */
1272	0, /* tp_as_buffer */
1273	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
1274	Py_TPFLAGS_BASETYPE, /* tp_flags */
1275	islice_doc, /* tp_doc */
1276	(traverseproc)islice_traverse, /* tp_traverse */
1277	0, /* tp_clear */
1278	0, /* tp_richcompare */
1279	0, /* tp_weaklistoffset */
1280	PyObject_SelfIter, /* tp_iter */
1281	(iternextfunc)islice_next, /* tp_iternext */
1282	0, /* tp_methods */
1283	0, /* tp_members */
1284	0, /* tp_getset */
1285	0, /* tp_base */
1286	0, /* tp_dict */
1287	0, /* tp_descr_get */
1288	0, /* tp_descr_set */
1289	0, /* tp_dictoffset */
1290	0, /* tp_init */
1291	0, /* tp_alloc */
1292	islice_new, /* tp_new */
1293	PyObject_GC_Del, /* tp_free */
1294	};
1295
1296
1297	/* starmap object ************************************************************/
1298
1299	typedef struct {
1300	PyObject_HEAD
1301	PyObject *func;
1302	PyObject *it;
1303	} starmapobject;
1304
1305	static PyTypeObject starmap_type;
1306
1307	static PyObject *
1308	starmap_new(PyTypeObject type, PyObject args, PyObject *kwds)
1309	{
1310	PyObject func, seq;
1311	PyObject *it;
1312	starmapobject *lz;
1313
1314	if (!_PyArg_NoKeywords("starmap()", kwds))
1315	return NULL;
1316
1317	if (!PyArg_UnpackTuple(args, "starmap", 2, 2, &func, &seq))
1318	return NULL;
1319
1320	/* Get iterator. */
1321	it = PyObject_GetIter(seq);
1322	if (it == NULL)
1323	return NULL;
1324
1325	/* create starmapobject structure */
1326	lz = (starmapobject *)type->tp_alloc(type, 0);
1327	if (lz == NULL) {
1328	Py_DECREF(it);
1329	return NULL;
1330	}
1331	Py_INCREF(func);
1332	lz->func = func;
1333	lz->it = it;
1334
1335	return (PyObject *)lz;
1336	}
1337
1338	static void
1339	starmap_dealloc(starmapobject *lz)
1340	{
1341	PyObject_GC_UnTrack(lz);
1342	Py_XDECREF(lz->func);
1343	Py_XDECREF(lz->it);
1344	lz->ob_type->tp_free(lz);
1345	}
1346
1347	static int
1348	starmap_traverse(starmapobject lz, visitproc visit, void arg)
1349	{
1350	Py_VISIT(lz->it);
1351	Py_VISIT(lz->func);
1352	return 0;
1353	}
1354
1355	static PyObject *
1356	starmap_next(starmapobject *lz)
1357	{
1358	PyObject *args;
1359	PyObject *result;
1360	PyObject *it = lz->it;
1361
1362	assert(PyIter_Check(it));
1363	args = (*it->ob_type->tp_iternext)(it);
1364	if (args == NULL)
1365	return NULL;
1366	if (!PyTuple_CheckExact(args)) {
1367	Py_DECREF(args);
1368	PyErr_SetString(PyExc_TypeError,
1369	"iterator must return a tuple");
1370	return NULL;
1371	}
1372	result = PyObject_Call(lz->func, args, NULL);
1373	Py_DECREF(args);
1374	return result;
1375	}
1376
1377	PyDoc_STRVAR(starmap_doc,
1378	"starmap(function, sequence) --> starmap object\n\
1379	\n\
1380	Return an iterator whose values are returned from the function evaluated\n\
1381	with a argument tuple taken from the given sequence.");
1382
1383	static PyTypeObject starmap_type = {
1384	PyObject_HEAD_INIT(NULL)
1385	0, /* ob_size */
1386	"itertools.starmap", /* tp_name */
1387	sizeof(starmapobject), /* tp_basicsize */
1388	0, /* tp_itemsize */
1389	/* methods */
1390	(destructor)starmap_dealloc, /* tp_dealloc */
1391	0, /* tp_print */
1392	0, /* tp_getattr */
1393	0, /* tp_setattr */
1394	0, /* tp_compare */
1395	0, /* tp_repr */
1396	0, /* tp_as_number */
1397	0, /* tp_as_sequence */
1398	0, /* tp_as_mapping */
1399	0, /* tp_hash */
1400	0, /* tp_call */
1401	0, /* tp_str */
1402	PyObject_GenericGetAttr, /* tp_getattro */
1403	0, /* tp_setattro */
1404	0, /* tp_as_buffer */
1405	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
1406	Py_TPFLAGS_BASETYPE, /* tp_flags */
1407	starmap_doc, /* tp_doc */
1408	(traverseproc)starmap_traverse, /* tp_traverse */
1409	0, /* tp_clear */
1410	0, /* tp_richcompare */
1411	0, /* tp_weaklistoffset */
1412	PyObject_SelfIter, /* tp_iter */
1413	(iternextfunc)starmap_next, /* tp_iternext */
1414	0, /* tp_methods */
1415	0, /* tp_members */
1416	0, /* tp_getset */
1417	0, /* tp_base */
1418	0, /* tp_dict */
1419	0, /* tp_descr_get */
1420	0, /* tp_descr_set */
1421	0, /* tp_dictoffset */
1422	0, /* tp_init */
1423	0, /* tp_alloc */
1424	starmap_new, /* tp_new */
1425	PyObject_GC_Del, /* tp_free */
1426	};
1427
1428
1429	/* imap object ************************************************************/
1430
1431	typedef struct {
1432	PyObject_HEAD
1433	PyObject *iters;
1434	PyObject *func;
1435	} imapobject;
1436
1437	static PyTypeObject imap_type;
1438
1439	static PyObject *
1440	imap_new(PyTypeObject type, PyObject args, PyObject *kwds)
1441	{
1442	PyObject it, iters, *func;
1443	imapobject *lz;
1444	Py_ssize_t numargs, i;
1445
1446	if (!_PyArg_NoKeywords("imap()", kwds))
1447	return NULL;
1448
1449	numargs = PyTuple_Size(args);
1450	if (numargs < 2) {
1451	PyErr_SetString(PyExc_TypeError,
1452	"imap() must have at least two arguments.");
1453	return NULL;
1454	}
1455
1456	iters = PyTuple_New(numargs-1);
1457	if (iters == NULL)
1458	return NULL;
1459
1460	for (i=1 ; i<numargs ; i++) {
1461	/* Get iterator. */
1462	it = PyObject_GetIter(PyTuple_GET_ITEM(args, i));
1463	if (it == NULL) {
1464	Py_DECREF(iters);
1465	return NULL;
1466	}
1467	PyTuple_SET_ITEM(iters, i-1, it);
1468	}
1469
1470	/* create imapobject structure */
1471	lz = (imapobject *)type->tp_alloc(type, 0);
1472	if (lz == NULL) {
1473	Py_DECREF(iters);
1474	return NULL;
1475	}
1476	lz->iters = iters;
1477	func = PyTuple_GET_ITEM(args, 0);
1478	Py_INCREF(func);
1479	lz->func = func;
1480
1481	return (PyObject *)lz;
1482	}
1483
1484	static void
1485	imap_dealloc(imapobject *lz)
1486	{
1487	PyObject_GC_UnTrack(lz);
1488	Py_XDECREF(lz->iters);
1489	Py_XDECREF(lz->func);
1490	lz->ob_type->tp_free(lz);
1491	}
1492
1493	static int
1494	imap_traverse(imapobject lz, visitproc visit, void arg)
1495	{
1496	Py_VISIT(lz->iters);
1497	Py_VISIT(lz->func);
1498	return 0;
1499	}
1500
1501	/*
1502	imap() is an iterator version of __builtins__.map() except that it does
1503	not have the None fill-in feature. That was intentionally left out for
1504	the following reasons:
1505
1506	1) Itertools are designed to be easily combined and chained together.
1507	Having all tools stop with the shortest input is a unifying principle
1508	that makes it easier to combine finite iterators (supplying data) with
1509	infinite iterators like count() and repeat() (for supplying sequential
1510	or constant arguments to a function).
1511
1512	2) In typical use cases for combining itertools, having one finite data
1513	supplier run out before another is likely to be an error condition which
1514	should not pass silently by automatically supplying None.
1515
1516	3) The use cases for automatic None fill-in are rare -- not many functions
1517	do something useful when a parameter suddenly switches type and becomes
1518	None.
1519
1520	4) If a need does arise, it can be met by __builtins__.map() or by
1521	writing: chain(iterable, repeat(None)).
1522
1523	5) Similar toolsets in Haskell and SML do not have automatic None fill-in.
1524	*/
1525
1526	static PyObject *
1527	imap_next(imapobject *lz)
1528	{
1529	PyObject *val;
1530	PyObject *argtuple;
1531	PyObject *result;
1532	Py_ssize_t numargs, i;
1533
1534	numargs = PyTuple_Size(lz->iters);
1535	argtuple = PyTuple_New(numargs);
1536	if (argtuple == NULL)
1537	return NULL;
1538
1539	for (i=0 ; i<numargs ; i++) {
1540	val = PyIter_Next(PyTuple_GET_ITEM(lz->iters, i));
1541	if (val == NULL) {
1542	Py_DECREF(argtuple);
1543	return NULL;
1544	}
1545	PyTuple_SET_ITEM(argtuple, i, val);
1546	}
1547	if (lz->func == Py_None)
1548	return argtuple;
1549	result = PyObject_Call(lz->func, argtuple, NULL);
1550	Py_DECREF(argtuple);
1551	return result;
1552	}
1553
1554	PyDoc_STRVAR(imap_doc,
1555	"imap(func, *iterables) --> imap object\n\
1556	\n\
1557	Make an iterator that computes the function using arguments from\n\
1558	each of the iterables. Like map() except that it returns\n\
1559	an iterator instead of a list and that it stops when the shortest\n\
1560	iterable is exhausted instead of filling in None for shorter\n\
1561	iterables.");
1562
1563	static PyTypeObject imap_type = {
1564	PyObject_HEAD_INIT(NULL)
1565	0, /* ob_size */
1566	"itertools.imap", /* tp_name */
1567	sizeof(imapobject), /* tp_basicsize */
1568	0, /* tp_itemsize */
1569	/* methods */
1570	(destructor)imap_dealloc, /* tp_dealloc */
1571	0, /* tp_print */
1572	0, /* tp_getattr */
1573	0, /* tp_setattr */
1574	0, /* tp_compare */
1575	0, /* tp_repr */
1576	0, /* tp_as_number */
1577	0, /* tp_as_sequence */
1578	0, /* tp_as_mapping */
1579	0, /* tp_hash */
1580	0, /* tp_call */
1581	0, /* tp_str */
1582	PyObject_GenericGetAttr, /* tp_getattro */
1583	0, /* tp_setattro */
1584	0, /* tp_as_buffer */
1585	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
1586	Py_TPFLAGS_BASETYPE, /* tp_flags */
1587	imap_doc, /* tp_doc */
1588	(traverseproc)imap_traverse, /* tp_traverse */
1589	0, /* tp_clear */
1590	0, /* tp_richcompare */
1591	0, /* tp_weaklistoffset */
1592	PyObject_SelfIter, /* tp_iter */
1593	(iternextfunc)imap_next, /* tp_iternext */
1594	0, /* tp_methods */
1595	0, /* tp_members */
1596	0, /* tp_getset */
1597	0, /* tp_base */
1598	0, /* tp_dict */
1599	0, /* tp_descr_get */
1600	0, /* tp_descr_set */
1601	0, /* tp_dictoffset */
1602	0, /* tp_init */
1603	0, /* tp_alloc */
1604	imap_new, /* tp_new */
1605	PyObject_GC_Del, /* tp_free */
1606	};
1607
1608
1609	/* chain object ************************************************************/
1610
1611	typedef struct {
1612	PyObject_HEAD
1613	Py_ssize_t tuplesize;
1614	Py_ssize_t iternum; /* which iterator is active */
1615	PyObject ittuple; / tuple of iterators */
1616	} chainobject;
1617
1618	static PyTypeObject chain_type;
1619
1620	static PyObject *
1621	chain_new(PyTypeObject type, PyObject args, PyObject *kwds)
1622	{
1623	chainobject *lz;
1624	Py_ssize_t tuplesize = PySequence_Length(args);
1625	Py_ssize_t i;
1626	PyObject *ittuple;
1627
1628	if (!_PyArg_NoKeywords("chain()", kwds))
1629	return NULL;
1630
1631	/* obtain iterators */
1632	assert(PyTuple_Check(args));
1633	ittuple = PyTuple_New(tuplesize);
1634	if (ittuple == NULL)
1635	return NULL;
1636	for (i=0; i < tuplesize; ++i) {
1637	PyObject *item = PyTuple_GET_ITEM(args, i);
1638	PyObject *it = PyObject_GetIter(item);
1639	if (it == NULL) {
1640	if (PyErr_ExceptionMatches(PyExc_TypeError))
1641	PyErr_Format(PyExc_TypeError,
1642	"chain argument #%zd must support iteration",
1643	i+1);
1644	Py_DECREF(ittuple);
1645	return NULL;
1646	}
1647	PyTuple_SET_ITEM(ittuple, i, it);
1648	}
1649
1650	/* create chainobject structure */
1651	lz = (chainobject *)type->tp_alloc(type, 0);
1652	if (lz == NULL) {
1653	Py_DECREF(ittuple);
1654	return NULL;
1655	}
1656
1657	lz->ittuple = ittuple;
1658	lz->iternum = 0;
1659	lz->tuplesize = tuplesize;
1660
1661	return (PyObject *)lz;
1662	}
1663
1664	static void
1665	chain_dealloc(chainobject *lz)
1666	{
1667	PyObject_GC_UnTrack(lz);
1668	Py_XDECREF(lz->ittuple);
1669	lz->ob_type->tp_free(lz);
1670	}
1671
1672	static int
1673	chain_traverse(chainobject lz, visitproc visit, void arg)
1674	{
1675	Py_VISIT(lz->ittuple);
1676	return 0;
1677	}
1678
1679	static PyObject *
1680	chain_next(chainobject *lz)
1681	{
1682	PyObject *it;
1683	PyObject *item;
1684
1685	while (lz->iternum < lz->tuplesize) {
1686	it = PyTuple_GET_ITEM(lz->ittuple, lz->iternum);
1687	item = PyIter_Next(it);
1688	if (item != NULL)
1689	return item;
1690	if (PyErr_Occurred()) {
1691	if (PyErr_ExceptionMatches(PyExc_StopIteration))
1692	PyErr_Clear();
1693	else
1694	return NULL;
1695	}
1696	lz->iternum++;
1697	}
1698	return NULL;
1699	}
1700
1701	PyDoc_STRVAR(chain_doc,
1702	"chain(*iterables) --> chain object\n\
1703	\n\
1704	Return a chain object whose .next() method returns elements from the\n\
1705	first iterable until it is exhausted, then elements from the next\n\
1706	iterable, until all of the iterables are exhausted.");
1707
1708	static PyTypeObject chain_type = {
1709	PyObject_HEAD_INIT(NULL)
1710	0, /* ob_size */
1711	"itertools.chain", /* tp_name */
1712	sizeof(chainobject), /* tp_basicsize */
1713	0, /* tp_itemsize */
1714	/* methods */
1715	(destructor)chain_dealloc, /* tp_dealloc */
1716	0, /* tp_print */
1717	0, /* tp_getattr */
1718	0, /* tp_setattr */
1719	0, /* tp_compare */
1720	0, /* tp_repr */
1721	0, /* tp_as_number */
1722	0, /* tp_as_sequence */
1723	0, /* tp_as_mapping */
1724	0, /* tp_hash */
1725	0, /* tp_call */
1726	0, /* tp_str */
1727	PyObject_GenericGetAttr, /* tp_getattro */
1728	0, /* tp_setattro */
1729	0, /* tp_as_buffer */
1730	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
1731	Py_TPFLAGS_BASETYPE, /* tp_flags */
1732	chain_doc, /* tp_doc */
1733	(traverseproc)chain_traverse, /* tp_traverse */
1734	0, /* tp_clear */
1735	0, /* tp_richcompare */
1736	0, /* tp_weaklistoffset */
1737	PyObject_SelfIter, /* tp_iter */
1738	(iternextfunc)chain_next, /* tp_iternext */
1739	0, /* tp_methods */
1740	0, /* tp_members */
1741	0, /* tp_getset */
1742	0, /* tp_base */
1743	0, /* tp_dict */
1744	0, /* tp_descr_get */
1745	0, /* tp_descr_set */
1746	0, /* tp_dictoffset */
1747	0, /* tp_init */
1748	0, /* tp_alloc */
1749	chain_new, /* tp_new */
1750	PyObject_GC_Del, /* tp_free */
1751	};
1752
1753
1754	/* ifilter object ************************************************************/
1755
1756	typedef struct {
1757	PyObject_HEAD
1758	PyObject *func;
1759	PyObject *it;
1760	} ifilterobject;
1761
1762	static PyTypeObject ifilter_type;
1763
1764	static PyObject *
1765	ifilter_new(PyTypeObject type, PyObject args, PyObject *kwds)
1766	{
1767	PyObject func, seq;
1768	PyObject *it;
1769	ifilterobject *lz;
1770
1771	if (!_PyArg_NoKeywords("ifilter()", kwds))
1772	return NULL;
1773
1774	if (!PyArg_UnpackTuple(args, "ifilter", 2, 2, &func, &seq))
1775	return NULL;
1776
1777	/* Get iterator. */
1778	it = PyObject_GetIter(seq);
1779	if (it == NULL)
1780	return NULL;
1781
1782	/* create ifilterobject structure */
1783	lz = (ifilterobject *)type->tp_alloc(type, 0);
1784	if (lz == NULL) {
1785	Py_DECREF(it);
1786	return NULL;
1787	}
1788	Py_INCREF(func);
1789	lz->func = func;
1790	lz->it = it;
1791
1792	return (PyObject *)lz;
1793	}
1794
1795	static void
1796	ifilter_dealloc(ifilterobject *lz)
1797	{
1798	PyObject_GC_UnTrack(lz);
1799	Py_XDECREF(lz->func);
1800	Py_XDECREF(lz->it);
1801	lz->ob_type->tp_free(lz);
1802	}
1803
1804	static int
1805	ifilter_traverse(ifilterobject lz, visitproc visit, void arg)
1806	{
1807	Py_VISIT(lz->it);
1808	Py_VISIT(lz->func);
1809	return 0;
1810	}
1811
1812	static PyObject *
1813	ifilter_next(ifilterobject *lz)
1814	{
1815	PyObject *item;
1816	PyObject *it = lz->it;
1817	long ok;
1818	PyObject (iternext)(PyObject *);
1819
1820	assert(PyIter_Check(it));
1821	iternext = *it->ob_type->tp_iternext;
1822	for (;;) {
1823	item = iternext(it);
1824	if (item == NULL)
1825	return NULL;
1826
1827	if (lz->func == Py_None) {
1828	ok = PyObject_IsTrue(item);
1829	} else {
1830	PyObject *good;
1831	good = PyObject_CallFunctionObjArgs(lz->func,
1832	item, NULL);
1833	if (good == NULL) {
1834	Py_DECREF(item);
1835	return NULL;
1836	}
1837	ok = PyObject_IsTrue(good);
1838	Py_DECREF(good);
1839	}
1840	if (ok)
1841	return item;
1842	Py_DECREF(item);
1843	}
1844	}
1845
1846	PyDoc_STRVAR(ifilter_doc,
1847	"ifilter(function or None, sequence) --> ifilter object\n\
1848	\n\
1849	Return those items of sequence for which function(item) is true.\n\
1850	If function is None, return the items that are true.");
1851
1852	static PyTypeObject ifilter_type = {
1853	PyObject_HEAD_INIT(NULL)
1854	0, /* ob_size */
1855	"itertools.ifilter", /* tp_name */
1856	sizeof(ifilterobject), /* tp_basicsize */
1857	0, /* tp_itemsize */
1858	/* methods */
1859	(destructor)ifilter_dealloc, /* tp_dealloc */
1860	0, /* tp_print */
1861	0, /* tp_getattr */
1862	0, /* tp_setattr */
1863	0, /* tp_compare */
1864	0, /* tp_repr */
1865	0, /* tp_as_number */
1866	0, /* tp_as_sequence */
1867	0, /* tp_as_mapping */
1868	0, /* tp_hash */
1869	0, /* tp_call */
1870	0, /* tp_str */
1871	PyObject_GenericGetAttr, /* tp_getattro */
1872	0, /* tp_setattro */
1873	0, /* tp_as_buffer */
1874	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
1875	Py_TPFLAGS_BASETYPE, /* tp_flags */
1876	ifilter_doc, /* tp_doc */
1877	(traverseproc)ifilter_traverse, /* tp_traverse */
1878	0, /* tp_clear */
1879	0, /* tp_richcompare */
1880	0, /* tp_weaklistoffset */
1881	PyObject_SelfIter, /* tp_iter */
1882	(iternextfunc)ifilter_next, /* tp_iternext */
1883	0, /* tp_methods */
1884	0, /* tp_members */
1885	0, /* tp_getset */
1886	0, /* tp_base */
1887	0, /* tp_dict */
1888	0, /* tp_descr_get */
1889	0, /* tp_descr_set */
1890	0, /* tp_dictoffset */
1891	0, /* tp_init */
1892	0, /* tp_alloc */
1893	ifilter_new, /* tp_new */
1894	PyObject_GC_Del, /* tp_free */
1895	};
1896
1897
1898	/* ifilterfalse object ************************************************************/
1899
1900	typedef struct {
1901	PyObject_HEAD
1902	PyObject *func;
1903	PyObject *it;
1904	} ifilterfalseobject;
1905
1906	static PyTypeObject ifilterfalse_type;
1907
1908	static PyObject *
1909	ifilterfalse_new(PyTypeObject type, PyObject args, PyObject *kwds)
1910	{
1911	PyObject func, seq;
1912	PyObject *it;
1913	ifilterfalseobject *lz;
1914
1915	if (!_PyArg_NoKeywords("ifilterfalse()", kwds))
1916	return NULL;
1917
1918	if (!PyArg_UnpackTuple(args, "ifilterfalse", 2, 2, &func, &seq))
1919	return NULL;
1920
1921	/* Get iterator. */
1922	it = PyObject_GetIter(seq);
1923	if (it == NULL)
1924	return NULL;
1925
1926	/* create ifilterfalseobject structure */
1927	lz = (ifilterfalseobject *)type->tp_alloc(type, 0);
1928	if (lz == NULL) {
1929	Py_DECREF(it);
1930	return NULL;
1931	}
1932	Py_INCREF(func);
1933	lz->func = func;
1934	lz->it = it;
1935
1936	return (PyObject *)lz;
1937	}
1938
1939	static void
1940	ifilterfalse_dealloc(ifilterfalseobject *lz)
1941	{
1942	PyObject_GC_UnTrack(lz);
1943	Py_XDECREF(lz->func);
1944	Py_XDECREF(lz->it);
1945	lz->ob_type->tp_free(lz);
1946	}
1947
1948	static int
1949	ifilterfalse_traverse(ifilterfalseobject lz, visitproc visit, void arg)
1950	{
1951	Py_VISIT(lz->it);
1952	Py_VISIT(lz->func);
1953	return 0;
1954	}
1955
1956	static PyObject *
1957	ifilterfalse_next(ifilterfalseobject *lz)
1958	{
1959	PyObject *item;
1960	PyObject *it = lz->it;
1961	long ok;
1962	PyObject (iternext)(PyObject *);
1963
1964	assert(PyIter_Check(it));
1965	iternext = *it->ob_type->tp_iternext;
1966	for (;;) {
1967	item = iternext(it);
1968	if (item == NULL)
1969	return NULL;
1970
1971	if (lz->func == Py_None) {
1972	ok = PyObject_IsTrue(item);
1973	} else {
1974	PyObject *good;
1975	good = PyObject_CallFunctionObjArgs(lz->func,
1976	item, NULL);
1977	if (good == NULL) {
1978	Py_DECREF(item);
1979	return NULL;
1980	}
1981	ok = PyObject_IsTrue(good);
1982	Py_DECREF(good);
1983	}
1984	if (!ok)
1985	return item;
1986	Py_DECREF(item);
1987	}
1988	}
1989
1990	PyDoc_STRVAR(ifilterfalse_doc,
1991	"ifilterfalse(function or None, sequence) --> ifilterfalse object\n\
1992	\n\
1993	Return those items of sequence for which function(item) is false.\n\
1994	If function is None, return the items that are false.");
1995
1996	static PyTypeObject ifilterfalse_type = {
1997	PyObject_HEAD_INIT(NULL)
1998	0, /* ob_size */
1999	"itertools.ifilterfalse", /* tp_name */
2000	sizeof(ifilterfalseobject), /* tp_basicsize */
2001	0, /* tp_itemsize */
2002	/* methods */
2003	(destructor)ifilterfalse_dealloc, /* tp_dealloc */
2004	0, /* tp_print */
2005	0, /* tp_getattr */
2006	0, /* tp_setattr */
2007	0, /* tp_compare */
2008	0, /* tp_repr */
2009	0, /* tp_as_number */
2010	0, /* tp_as_sequence */
2011	0, /* tp_as_mapping */
2012	0, /* tp_hash */
2013	0, /* tp_call */
2014	0, /* tp_str */
2015	PyObject_GenericGetAttr, /* tp_getattro */
2016	0, /* tp_setattro */
2017	0, /* tp_as_buffer */
2018	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
2019	Py_TPFLAGS_BASETYPE, /* tp_flags */
2020	ifilterfalse_doc, /* tp_doc */
2021	(traverseproc)ifilterfalse_traverse, /* tp_traverse */
2022	0, /* tp_clear */
2023	0, /* tp_richcompare */
2024	0, /* tp_weaklistoffset */
2025	PyObject_SelfIter, /* tp_iter */
2026	(iternextfunc)ifilterfalse_next, /* tp_iternext */
2027	0, /* tp_methods */
2028	0, /* tp_members */
2029	0, /* tp_getset */
2030	0, /* tp_base */
2031	0, /* tp_dict */
2032	0, /* tp_descr_get */
2033	0, /* tp_descr_set */
2034	0, /* tp_dictoffset */
2035	0, /* tp_init */
2036	0, /* tp_alloc */
2037	ifilterfalse_new, /* tp_new */
2038	PyObject_GC_Del, /* tp_free */
2039	};
2040
2041
2042	/* count object ************************************************************/
2043
2044	typedef struct {
2045	PyObject_HEAD
2046	Py_ssize_t cnt;
2047	} countobject;
2048
2049	static PyTypeObject count_type;
2050
2051	static PyObject *
2052	count_new(PyTypeObject type, PyObject args, PyObject *kwds)
2053	{
2054	countobject *lz;
2055	Py_ssize_t cnt = 0;
2056
2057	if (!_PyArg_NoKeywords("count()", kwds))
2058	return NULL;
2059
2060	if (!PyArg_ParseTuple(args, "\|n:count", &cnt))
2061	return NULL;
2062
2063	/* create countobject structure */
2064	lz = (countobject *)PyObject_New(countobject, &count_type);
2065	if (lz == NULL)
2066	return NULL;
2067	lz->cnt = cnt;
2068
2069	return (PyObject *)lz;
2070	}
2071
2072	static PyObject *
2073	count_next(countobject *lz)
2074	{
2075	return PyInt_FromSize_t(lz->cnt++);
2076	}
2077
2078	static PyObject *
2079	count_repr(countobject *lz)
2080	{
2081	return PyString_FromFormat("count(%zd)", lz->cnt);
2082	}
2083
2084	PyDoc_STRVAR(count_doc,
2085	"count([firstval]) --> count object\n\
2086	\n\
2087	Return a count object whose .next() method returns consecutive\n\
2088	integers starting from zero or, if specified, from firstval.");
2089
2090	static PyTypeObject count_type = {
2091	PyObject_HEAD_INIT(NULL)
2092	0, /* ob_size */
2093	"itertools.count", /* tp_name */
2094	sizeof(countobject), /* tp_basicsize */
2095	0, /* tp_itemsize */
2096	/* methods */
2097	(destructor)PyObject_Del, /* tp_dealloc */
2098	0, /* tp_print */
2099	0, /* tp_getattr */
2100	0, /* tp_setattr */
2101	0, /* tp_compare */
2102	(reprfunc)count_repr, /* tp_repr */
2103	0, /* tp_as_number */
2104	0, /* tp_as_sequence */
2105	0, /* tp_as_mapping */
2106	0, /* tp_hash */
2107	0, /* tp_call */
2108	0, /* tp_str */
2109	PyObject_GenericGetAttr, /* tp_getattro */
2110	0, /* tp_setattro */
2111	0, /* tp_as_buffer */
2112	Py_TPFLAGS_DEFAULT, /* tp_flags */
2113	count_doc, /* tp_doc */
2114	0, /* tp_traverse */
2115	0, /* tp_clear */
2116	0, /* tp_richcompare */
2117	0, /* tp_weaklistoffset */
2118	PyObject_SelfIter, /* tp_iter */
2119	(iternextfunc)count_next, /* tp_iternext */
2120	0, /* tp_methods */
2121	0, /* tp_members */
2122	0, /* tp_getset */
2123	0, /* tp_base */
2124	0, /* tp_dict */
2125	0, /* tp_descr_get */
2126	0, /* tp_descr_set */
2127	0, /* tp_dictoffset */
2128	0, /* tp_init */
2129	0, /* tp_alloc */
2130	count_new, /* tp_new */
2131	};
2132
2133
2134	/* izip object ************************************************************/
2135
2136	#include "Python.h"
2137
2138	typedef struct {
2139	PyObject_HEAD
2140	Py_ssize_t tuplesize;
2141	PyObject ittuple; / tuple of iterators */
2142	PyObject *result;
2143	} izipobject;
2144
2145	static PyTypeObject izip_type;
2146
2147	static PyObject *
2148	izip_new(PyTypeObject type, PyObject args, PyObject *kwds)
2149	{
2150	izipobject *lz;
2151	Py_ssize_t i;
2152	PyObject ittuple; / tuple of iterators */
2153	PyObject *result;
2154	Py_ssize_t tuplesize = PySequence_Length(args);
2155
2156	if (!_PyArg_NoKeywords("izip()", kwds))
2157	return NULL;
2158
2159	/* args must be a tuple */
2160	assert(PyTuple_Check(args));
2161
2162	/* obtain iterators */
2163	ittuple = PyTuple_New(tuplesize);
2164	if (ittuple == NULL)
2165	return NULL;
2166	for (i=0; i < tuplesize; ++i) {
2167	PyObject *item = PyTuple_GET_ITEM(args, i);
2168	PyObject *it = PyObject_GetIter(item);
2169	if (it == NULL) {
2170	if (PyErr_ExceptionMatches(PyExc_TypeError))
2171	PyErr_Format(PyExc_TypeError,
2172	"izip argument #%zd must support iteration",
2173	i+1);
2174	Py_DECREF(ittuple);
2175	return NULL;
2176	}
2177	PyTuple_SET_ITEM(ittuple, i, it);
2178	}
2179
2180	/* create a result holder */
2181	result = PyTuple_New(tuplesize);
2182	if (result == NULL) {
2183	Py_DECREF(ittuple);
2184	return NULL;
2185	}
2186	for (i=0 ; i < tuplesize ; i++) {
2187	Py_INCREF(Py_None);
2188	PyTuple_SET_ITEM(result, i, Py_None);
2189	}
2190
2191	/* create izipobject structure */
2192	lz = (izipobject *)type->tp_alloc(type, 0);
2193	if (lz == NULL) {
2194	Py_DECREF(ittuple);
2195	Py_DECREF(result);
2196	return NULL;
2197	}
2198	lz->ittuple = ittuple;
2199	lz->tuplesize = tuplesize;
2200	lz->result = result;
2201
2202	return (PyObject *)lz;
2203	}
2204
2205	static void
2206	izip_dealloc(izipobject *lz)
2207	{
2208	PyObject_GC_UnTrack(lz);
2209	Py_XDECREF(lz->ittuple);
2210	Py_XDECREF(lz->result);
2211	lz->ob_type->tp_free(lz);
2212	}
2213
2214	static int
2215	izip_traverse(izipobject lz, visitproc visit, void arg)
2216	{
2217	Py_VISIT(lz->ittuple);
2218	Py_VISIT(lz->result);
2219	return 0;
2220	}
2221
2222	static PyObject *
2223	izip_next(izipobject *lz)
2224	{
2225	Py_ssize_t i;
2226	Py_ssize_t tuplesize = lz->tuplesize;
2227	PyObject *result = lz->result;
2228	PyObject *it;
2229	PyObject *item;
2230	PyObject *olditem;
2231
2232	if (tuplesize == 0)
2233	return NULL;
2234	if (result->ob_refcnt == 1) {
2235	Py_INCREF(result);
2236	for (i=0 ; i < tuplesize ; i++) {
2237	it = PyTuple_GET_ITEM(lz->ittuple, i);
2238	assert(PyIter_Check(it));
2239	item = (*it->ob_type->tp_iternext)(it);
2240	if (item == NULL) {
2241	Py_DECREF(result);
2242	return NULL;
2243	}
2244	olditem = PyTuple_GET_ITEM(result, i);
2245	PyTuple_SET_ITEM(result, i, item);
2246	Py_DECREF(olditem);
2247	}
2248	} else {
2249	result = PyTuple_New(tuplesize);
2250	if (result == NULL)
2251	return NULL;
2252	for (i=0 ; i < tuplesize ; i++) {
2253	it = PyTuple_GET_ITEM(lz->ittuple, i);
2254	assert(PyIter_Check(it));
2255	item = (*it->ob_type->tp_iternext)(it);
2256	if (item == NULL) {
2257	Py_DECREF(result);
2258	return NULL;
2259	}
2260	PyTuple_SET_ITEM(result, i, item);
2261	}
2262	}
2263	return result;
2264	}
2265
2266	PyDoc_STRVAR(izip_doc,
2267	"izip(iter1 [,iter2 [...]]) --> izip object\n\
2268	\n\
2269	Return a izip object whose .next() method returns a tuple where\n\
2270	the i-th element comes from the i-th iterable argument. The .next()\n\
2271	method continues until the shortest iterable in the argument sequence\n\
2272	is exhausted and then it raises StopIteration. Works like the zip()\n\
2273	function but consumes less memory by returning an iterator instead of\n\
2274	a list.");
2275
2276	static PyTypeObject izip_type = {
2277	PyObject_HEAD_INIT(NULL)
2278	0, /* ob_size */
2279	"itertools.izip", /* tp_name */
2280	sizeof(izipobject), /* tp_basicsize */
2281	0, /* tp_itemsize */
2282	/* methods */
2283	(destructor)izip_dealloc, /* tp_dealloc */
2284	0, /* tp_print */
2285	0, /* tp_getattr */
2286	0, /* tp_setattr */
2287	0, /* tp_compare */
2288	0, /* tp_repr */
2289	0, /* tp_as_number */
2290	0, /* tp_as_sequence */
2291	0, /* tp_as_mapping */
2292	0, /* tp_hash */
2293	0, /* tp_call */
2294	0, /* tp_str */
2295	PyObject_GenericGetAttr, /* tp_getattro */
2296	0, /* tp_setattro */
2297	0, /* tp_as_buffer */
2298	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
2299	Py_TPFLAGS_BASETYPE, /* tp_flags */
2300	izip_doc, /* tp_doc */
2301	(traverseproc)izip_traverse, /* tp_traverse */
2302	0, /* tp_clear */
2303	0, /* tp_richcompare */
2304	0, /* tp_weaklistoffset */
2305	PyObject_SelfIter, /* tp_iter */
2306	(iternextfunc)izip_next, /* tp_iternext */
2307	0, /* tp_methods */
2308	0, /* tp_members */
2309	0, /* tp_getset */
2310	0, /* tp_base */
2311	0, /* tp_dict */
2312	0, /* tp_descr_get */
2313	0, /* tp_descr_set */
2314	0, /* tp_dictoffset */
2315	0, /* tp_init */
2316	0, /* tp_alloc */
2317	izip_new, /* tp_new */
2318	PyObject_GC_Del, /* tp_free */
2319	};
2320
2321
2322	/* repeat object ************************************************************/
2323
2324	typedef struct {
2325	PyObject_HEAD
2326	PyObject *element;
2327	Py_ssize_t cnt;
2328	} repeatobject;
2329
2330	static PyTypeObject repeat_type;
2331
2332	static PyObject *
2333	repeat_new(PyTypeObject type, PyObject args, PyObject *kwds)
2334	{
2335	repeatobject *ro;
2336	PyObject *element;
2337	Py_ssize_t cnt = -1;
2338
2339	if (!_PyArg_NoKeywords("repeat()", kwds))
2340	return NULL;
2341
2342	if (!PyArg_ParseTuple(args, "O\|n:repeat", &element, &cnt))
2343	return NULL;
2344
2345	if (PyTuple_Size(args) == 2 && cnt < 0)
2346	cnt = 0;
2347
2348	ro = (repeatobject *)type->tp_alloc(type, 0);
2349	if (ro == NULL)
2350	return NULL;
2351	Py_INCREF(element);
2352	ro->element = element;
2353	ro->cnt = cnt;
2354	return (PyObject *)ro;
2355	}
2356
2357	static void
2358	repeat_dealloc(repeatobject *ro)
2359	{
2360	PyObject_GC_UnTrack(ro);
2361	Py_XDECREF(ro->element);
2362	ro->ob_type->tp_free(ro);
2363	}
2364
2365	static int
2366	repeat_traverse(repeatobject ro, visitproc visit, void arg)
2367	{
2368	Py_VISIT(ro->element);
2369	return 0;
2370	}
2371
2372	static PyObject *
2373	repeat_next(repeatobject *ro)
2374	{
2375	if (ro->cnt == 0)
2376	return NULL;
2377	if (ro->cnt > 0)
2378	ro->cnt--;
2379	Py_INCREF(ro->element);
2380	return ro->element;
2381	}
2382
2383	static PyObject *
2384	repeat_repr(repeatobject *ro)
2385	{
2386	PyObject result, objrepr;
2387
2388	objrepr = PyObject_Repr(ro->element);
2389	if (objrepr == NULL)
2390	return NULL;
2391
2392	if (ro->cnt == -1)
2393	result = PyString_FromFormat("repeat(%s)",
2394	PyString_AS_STRING(objrepr));
2395	else
2396	result = PyString_FromFormat("repeat(%s, %zd)",
2397	PyString_AS_STRING(objrepr), ro->cnt);
2398	Py_DECREF(objrepr);
2399	return result;
2400	}
2401
2402	static PyObject *
2403	repeat_len(repeatobject *ro)
2404	{
2405	if (ro->cnt == -1) {
2406	PyErr_SetString(PyExc_TypeError, "len() of unsized object");
2407	return NULL;
2408	}
2409	return PyInt_FromSize_t(ro->cnt);
2410	}
2411
2412	PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
2413
2414	static PyMethodDef repeat_methods[] = {
2415	{"__length_hint__", (PyCFunction)repeat_len, METH_NOARGS, length_hint_doc},
2416	{NULL, NULL} /* sentinel */
2417	};
2418
2419	PyDoc_STRVAR(repeat_doc,
2420	"repeat(element [,times]) -> create an iterator which returns the element\n\
2421	for the specified number of times. If not specified, returns the element\n\
2422	endlessly.");
2423
2424	static PyTypeObject repeat_type = {
2425	PyObject_HEAD_INIT(NULL)
2426	0, /* ob_size */
2427	"itertools.repeat", /* tp_name */
2428	sizeof(repeatobject), /* tp_basicsize */
2429	0, /* tp_itemsize */
2430	/* methods */
2431	(destructor)repeat_dealloc, /* tp_dealloc */
2432	0, /* tp_print */
2433	0, /* tp_getattr */
2434	0, /* tp_setattr */
2435	0, /* tp_compare */
2436	(reprfunc)repeat_repr, /* tp_repr */
2437	0, /* tp_as_number */
2438	0, /* tp_as_sequence */
2439	0, /* tp_as_mapping */
2440	0, /* tp_hash */
2441	0, /* tp_call */
2442	0, /* tp_str */
2443	PyObject_GenericGetAttr, /* tp_getattro */
2444	0, /* tp_setattro */
2445	0, /* tp_as_buffer */
2446	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
2447	Py_TPFLAGS_BASETYPE, /* tp_flags */
2448	repeat_doc, /* tp_doc */
2449	(traverseproc)repeat_traverse, /* tp_traverse */
2450	0, /* tp_clear */
2451	0, /* tp_richcompare */
2452	0, /* tp_weaklistoffset */
2453	PyObject_SelfIter, /* tp_iter */
2454	(iternextfunc)repeat_next, /* tp_iternext */
2455	repeat_methods, /* tp_methods */
2456	0, /* tp_members */
2457	0, /* tp_getset */
2458	0, /* tp_base */
2459	0, /* tp_dict */
2460	0, /* tp_descr_get */
2461	0, /* tp_descr_set */
2462	0, /* tp_dictoffset */
2463	0, /* tp_init */
2464	0, /* tp_alloc */
2465	repeat_new, /* tp_new */
2466	PyObject_GC_Del, /* tp_free */
2467	};
2468
2469
2470	/* module level code ********************************************************/
2471
2472	PyDoc_STRVAR(module_doc,
2473	"Functional tools for creating and using iterators.\n\
2474	\n\
2475	Infinite iterators:\n\
2476	count([n]) --> n, n+1, n+2, ...\n\
2477	cycle(p) --> p0, p1, ... plast, p0, p1, ...\n\
2478	repeat(elem [,n]) --> elem, elem, elem, ... endlessly or up to n times\n\
2479	\n\
2480	Iterators terminating on the shortest input sequence:\n\
2481	izip(p, q, ...) --> (p[0], q[0]), (p[1], q[1]), ... \n\
2482	ifilter(pred, seq) --> elements of seq where pred(elem) is True\n\
2483	ifilterfalse(pred, seq) --> elements of seq where pred(elem) is False\n\
2484	islice(seq, [start,] stop [, step]) --> elements from\n\
2485	seq[start:stop:step]\n\
2486	imap(fun, p, q, ...) --> fun(p0, q0), fun(p1, q1), ...\n\
2487	starmap(fun, seq) --> fun(seq[0]), fun(seq[1]), ...\n\
2488	tee(it, n=2) --> (it1, it2 , ... itn) splits one iterator into n\n\
2489	chain(p, q, ...) --> p0, p1, ... plast, q0, q1, ... \n\
2490	takewhile(pred, seq) --> seq[0], seq[1], until pred fails\n\
2491	dropwhile(pred, seq) --> seq[n], seq[n+1], starting when pred fails\n\
2492	groupby(iterable[, keyfunc]) --> sub-iterators grouped by value of keyfunc(v)\n\
2493	");
2494
2495
2496	static PyMethodDef module_methods[] = {
2497	{"tee", (PyCFunction)tee, METH_VARARGS, tee_doc},
2498	{NULL, NULL} /* sentinel */
2499	};
2500
2501	PyMODINIT_FUNC
2502	inititertools(void)
2503	{
2504	int i;
2505	PyObject *m;
2506	char *name;
2507	PyTypeObject *typelist[] = {
2508	&cycle_type,
2509	&dropwhile_type,
2510	&takewhile_type,
2511	&islice_type,
2512	&starmap_type,
2513	&imap_type,
2514	&chain_type,
2515	&ifilter_type,
2516	&ifilterfalse_type,
2517	&count_type,
2518	&izip_type,
2519	&repeat_type,
2520	&groupby_type,
2521	NULL
2522	};
2523
2524	teedataobject_type.ob_type = &PyType_Type;
2525	m = Py_InitModule3("itertools", module_methods, module_doc);
2526	if (m == NULL)
2527	return;
2528
2529	for (i=0 ; typelist[i] != NULL ; i++) {
2530	if (PyType_Ready(typelist[i]) < 0)
2531	return;
2532	name = strchr(typelist[i]->tp_name, '.');
2533	assert (name != NULL);
2534	Py_INCREF(typelist[i]);
2535	PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
2536	}
2537
2538	if (PyType_Ready(&teedataobject_type) < 0)
2539	return;
2540	if (PyType_Ready(&tee_type) < 0)
2541	return;
2542	if (PyType_Ready(&_grouper_type) < 0)
2543	return;
2544	}

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: vendor/python/2.5/Modules/itertoolsmodule.c

Download in other formats: