Python code coverage for Modules/itertoolsmodule.c

#	count	content
1	n/a
2	n/a	#define PY_SSIZE_T_CLEAN
3	n/a	#include "Python.h"
4	n/a	#include "structmember.h"
5	n/a
6	n/a	/* Itertools module written and maintained
7	n/a	by Raymond D. Hettinger <python@rcn.com>
8	n/a	*/
9	n/a
10	n/a
11	n/a	/* groupby object ************************************************************/
12	n/a
13	n/a	typedef struct {
14	n/a	PyObject_HEAD
15	n/a	PyObject *it;
16	n/a	PyObject *keyfunc;
17	n/a	PyObject *tgtkey;
18	n/a	PyObject *currkey;
19	n/a	PyObject *currvalue;
20	n/a	} groupbyobject;
21	n/a
22	n/a	static PyTypeObject groupby_type;
23	n/a	static PyObject _grouper_create(groupbyobject , PyObject *);
24	n/a
25	n/a	static PyObject *
26	n/a	groupby_new(PyTypeObject type, PyObject args, PyObject *kwds)
27	n/a	{
28	n/a	static char *kwargs[] = {"iterable", "key", NULL};
29	n/a	groupbyobject *gbo;
30	n/a	PyObject it, keyfunc = Py_None;
31	n/a
32	n/a	if (!PyArg_ParseTupleAndKeywords(args, kwds, "O\|O:groupby", kwargs,
33	n/a	&it, &keyfunc))
34	n/a	return NULL;
35	n/a
36	n/a	gbo = (groupbyobject *)type->tp_alloc(type, 0);
37	n/a	if (gbo == NULL)
38	n/a	return NULL;
39	n/a	gbo->tgtkey = NULL;
40	n/a	gbo->currkey = NULL;
41	n/a	gbo->currvalue = NULL;
42	n/a	gbo->keyfunc = keyfunc;
43	n/a	Py_INCREF(keyfunc);
44	n/a	gbo->it = PyObject_GetIter(it);
45	n/a	if (gbo->it == NULL) {
46	n/a	Py_DECREF(gbo);
47	n/a	return NULL;
48	n/a	}
49	n/a	return (PyObject *)gbo;
50	n/a	}
51	n/a
52	n/a	static void
53	n/a	groupby_dealloc(groupbyobject *gbo)
54	n/a	{
55	n/a	PyObject_GC_UnTrack(gbo);
56	n/a	Py_XDECREF(gbo->it);
57	n/a	Py_XDECREF(gbo->keyfunc);
58	n/a	Py_XDECREF(gbo->tgtkey);
59	n/a	Py_XDECREF(gbo->currkey);
60	n/a	Py_XDECREF(gbo->currvalue);
61	n/a	Py_TYPE(gbo)->tp_free(gbo);
62	n/a	}
63	n/a
64	n/a	static int
65	n/a	groupby_traverse(groupbyobject gbo, visitproc visit, void arg)
66	n/a	{
67	n/a	Py_VISIT(gbo->it);
68	n/a	Py_VISIT(gbo->keyfunc);
69	n/a	Py_VISIT(gbo->tgtkey);
70	n/a	Py_VISIT(gbo->currkey);
71	n/a	Py_VISIT(gbo->currvalue);
72	n/a	return 0;
73	n/a	}
74	n/a
75	n/a	static PyObject *
76	n/a	groupby_next(groupbyobject *gbo)
77	n/a	{
78	n/a	PyObject newvalue, newkey, r, grouper;
79	n/a
80	n/a	/* skip to next iteration group */
81	n/a	for (;;) {
82	n/a	if (gbo->currkey == NULL)
83	n/a	/* pass */;
84	n/a	else if (gbo->tgtkey == NULL)
85	n/a	break;
86	n/a	else {
87	n/a	int rcmp;
88	n/a
89	n/a	rcmp = PyObject_RichCompareBool(gbo->tgtkey, gbo->currkey, Py_EQ);
90	n/a	if (rcmp == -1)
91	n/a	return NULL;
92	n/a	else if (rcmp == 0)
93	n/a	break;
94	n/a	}
95	n/a
96	n/a	newvalue = PyIter_Next(gbo->it);
97	n/a	if (newvalue == NULL)
98	n/a	return NULL;
99	n/a
100	n/a	if (gbo->keyfunc == Py_None) {
101	n/a	newkey = newvalue;
102	n/a	Py_INCREF(newvalue);
103	n/a	} else {
104	n/a	newkey = PyObject_CallFunctionObjArgs(gbo->keyfunc, newvalue, NULL);
105	n/a	if (newkey == NULL) {
106	n/a	Py_DECREF(newvalue);
107	n/a	return NULL;
108	n/a	}
109	n/a	}
110	n/a
111	n/a	Py_XSETREF(gbo->currkey, newkey);
112	n/a	Py_XSETREF(gbo->currvalue, newvalue);
113	n/a	}
114	n/a
115	n/a	Py_INCREF(gbo->currkey);
116	n/a	Py_XSETREF(gbo->tgtkey, gbo->currkey);
117	n/a
118	n/a	grouper = _grouper_create(gbo, gbo->tgtkey);
119	n/a	if (grouper == NULL)
120	n/a	return NULL;
121	n/a
122	n/a	r = PyTuple_Pack(2, gbo->currkey, grouper);
123	n/a	Py_DECREF(grouper);
124	n/a	return r;
125	n/a	}
126	n/a
127	n/a	static PyObject *
128	n/a	groupby_reduce(groupbyobject *lz)
129	n/a	{
130	n/a	/* reduce as a 'new' call with an optional 'setstate' if groupby
131	n/a	* has started
132	n/a	*/
133	n/a	PyObject *value;
134	n/a	if (lz->tgtkey && lz->currkey && lz->currvalue)
135	n/a	value = Py_BuildValue("O(OO)(OOO)", Py_TYPE(lz),
136	n/a	lz->it, lz->keyfunc, lz->currkey, lz->currvalue, lz->tgtkey);
137	n/a	else
138	n/a	value = Py_BuildValue("O(OO)", Py_TYPE(lz),
139	n/a	lz->it, lz->keyfunc);
140	n/a
141	n/a	return value;
142	n/a	}
143	n/a
144	n/a	PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
145	n/a
146	n/a	static PyObject *
147	n/a	groupby_setstate(groupbyobject lz, PyObject state)
148	n/a	{
149	n/a	PyObject currkey, currvalue, *tgtkey;
150	n/a	if (!PyTuple_Check(state)) {
151	n/a	PyErr_SetString(PyExc_TypeError, "state is not a tuple");
152	n/a	return NULL;
153	n/a	}
154	n/a	if (!PyArg_ParseTuple(state, "OOO", &currkey, &currvalue, &tgtkey)) {
155	n/a	return NULL;
156	n/a	}
157	n/a	Py_INCREF(currkey);
158	n/a	Py_XSETREF(lz->currkey, currkey);
159	n/a	Py_INCREF(currvalue);
160	n/a	Py_XSETREF(lz->currvalue, currvalue);
161	n/a	Py_INCREF(tgtkey);
162	n/a	Py_XSETREF(lz->tgtkey, tgtkey);
163	n/a	Py_RETURN_NONE;
164	n/a	}
165	n/a
166	n/a	PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
167	n/a
168	n/a	static PyMethodDef groupby_methods[] = {
169	n/a	{"__reduce__", (PyCFunction)groupby_reduce, METH_NOARGS,
170	n/a	reduce_doc},
171	n/a	{"__setstate__", (PyCFunction)groupby_setstate, METH_O,
172	n/a	setstate_doc},
173	n/a	{NULL, NULL} /* sentinel */
174	n/a	};
175	n/a
176	n/a	PyDoc_STRVAR(groupby_doc,
177	n/a	"groupby(iterable[, keyfunc]) -> create an iterator which returns\n\
178	n/a	(key, sub-iterator) grouped by each value of key(value).\n");
179	n/a
180	n/a	static PyTypeObject groupby_type = {
181	n/a	PyVarObject_HEAD_INIT(NULL, 0)
182	n/a	"itertools.groupby", /* tp_name */
183	n/a	sizeof(groupbyobject), /* tp_basicsize */
184	n/a	0, /* tp_itemsize */
185	n/a	/* methods */
186	n/a	(destructor)groupby_dealloc, /* tp_dealloc */
187	n/a	0, /* tp_print */
188	n/a	0, /* tp_getattr */
189	n/a	0, /* tp_setattr */
190	n/a	0, /* tp_reserved */
191	n/a	0, /* tp_repr */
192	n/a	0, /* tp_as_number */
193	n/a	0, /* tp_as_sequence */
194	n/a	0, /* tp_as_mapping */
195	n/a	0, /* tp_hash */
196	n/a	0, /* tp_call */
197	n/a	0, /* tp_str */
198	n/a	PyObject_GenericGetAttr, /* tp_getattro */
199	n/a	0, /* tp_setattro */
200	n/a	0, /* tp_as_buffer */
201	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
202	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
203	n/a	groupby_doc, /* tp_doc */
204	n/a	(traverseproc)groupby_traverse, /* tp_traverse */
205	n/a	0, /* tp_clear */
206	n/a	0, /* tp_richcompare */
207	n/a	0, /* tp_weaklistoffset */
208	n/a	PyObject_SelfIter, /* tp_iter */
209	n/a	(iternextfunc)groupby_next, /* tp_iternext */
210	n/a	groupby_methods, /* tp_methods */
211	n/a	0, /* tp_members */
212	n/a	0, /* tp_getset */
213	n/a	0, /* tp_base */
214	n/a	0, /* tp_dict */
215	n/a	0, /* tp_descr_get */
216	n/a	0, /* tp_descr_set */
217	n/a	0, /* tp_dictoffset */
218	n/a	0, /* tp_init */
219	n/a	0, /* tp_alloc */
220	n/a	groupby_new, /* tp_new */
221	n/a	PyObject_GC_Del, /* tp_free */
222	n/a	};
223	n/a
224	n/a
225	n/a	/* _grouper object (internal) ************************************************/
226	n/a
227	n/a	typedef struct {
228	n/a	PyObject_HEAD
229	n/a	PyObject *parent;
230	n/a	PyObject *tgtkey;
231	n/a	} _grouperobject;
232	n/a
233	n/a	static PyTypeObject _grouper_type;
234	n/a
235	n/a	static PyObject *
236	n/a	_grouper_new(PyTypeObject type, PyObject args, PyObject *kwds)
237	n/a	{
238	n/a	PyObject parent, tgtkey;
239	n/a
240	n/a	if (!PyArg_ParseTuple(args, "O!O", &groupby_type, &parent, &tgtkey))
241	n/a	return NULL;
242	n/a
243	n/a	return _grouper_create((groupbyobject*) parent, tgtkey);
244	n/a	}
245	n/a
246	n/a	static PyObject *
247	n/a	_grouper_create(groupbyobject parent, PyObject tgtkey)
248	n/a	{
249	n/a	_grouperobject *igo;
250	n/a
251	n/a	igo = PyObject_GC_New(_grouperobject, &_grouper_type);
252	n/a	if (igo == NULL)
253	n/a	return NULL;
254	n/a	igo->parent = (PyObject *)parent;
255	n/a	Py_INCREF(parent);
256	n/a	igo->tgtkey = tgtkey;
257	n/a	Py_INCREF(tgtkey);
258	n/a
259	n/a	PyObject_GC_Track(igo);
260	n/a	return (PyObject *)igo;
261	n/a	}
262	n/a
263	n/a	static void
264	n/a	_grouper_dealloc(_grouperobject *igo)
265	n/a	{
266	n/a	PyObject_GC_UnTrack(igo);
267	n/a	Py_DECREF(igo->parent);
268	n/a	Py_DECREF(igo->tgtkey);
269	n/a	PyObject_GC_Del(igo);
270	n/a	}
271	n/a
272	n/a	static int
273	n/a	_grouper_traverse(_grouperobject igo, visitproc visit, void arg)
274	n/a	{
275	n/a	Py_VISIT(igo->parent);
276	n/a	Py_VISIT(igo->tgtkey);
277	n/a	return 0;
278	n/a	}
279	n/a
280	n/a	static PyObject *
281	n/a	_grouper_next(_grouperobject *igo)
282	n/a	{
283	n/a	groupbyobject gbo = (groupbyobject )igo->parent;
284	n/a	PyObject newvalue, newkey, *r;
285	n/a	int rcmp;
286	n/a
287	n/a	if (gbo->currvalue == NULL) {
288	n/a	newvalue = PyIter_Next(gbo->it);
289	n/a	if (newvalue == NULL)
290	n/a	return NULL;
291	n/a
292	n/a	if (gbo->keyfunc == Py_None) {
293	n/a	newkey = newvalue;
294	n/a	Py_INCREF(newvalue);
295	n/a	} else {
296	n/a	newkey = PyObject_CallFunctionObjArgs(gbo->keyfunc, newvalue, NULL);
297	n/a	if (newkey == NULL) {
298	n/a	Py_DECREF(newvalue);
299	n/a	return NULL;
300	n/a	}
301	n/a	}
302	n/a
303	n/a	assert(gbo->currkey == NULL);
304	n/a	gbo->currkey = newkey;
305	n/a	gbo->currvalue = newvalue;
306	n/a	}
307	n/a
308	n/a	assert(gbo->currkey != NULL);
309	n/a	rcmp = PyObject_RichCompareBool(igo->tgtkey, gbo->currkey, Py_EQ);
310	n/a	if (rcmp <= 0)
311	n/a	/* got any error or current group is end */
312	n/a	return NULL;
313	n/a
314	n/a	r = gbo->currvalue;
315	n/a	gbo->currvalue = NULL;
316	n/a	Py_CLEAR(gbo->currkey);
317	n/a
318	n/a	return r;
319	n/a	}
320	n/a
321	n/a	static PyObject *
322	n/a	_grouper_reduce(_grouperobject *lz)
323	n/a	{
324	n/a	return Py_BuildValue("O(OO)", Py_TYPE(lz), lz->parent, lz->tgtkey);
325	n/a	}
326	n/a
327	n/a	static PyMethodDef _grouper_methods[] = {
328	n/a	{"__reduce__", (PyCFunction)_grouper_reduce, METH_NOARGS,
329	n/a	reduce_doc},
330	n/a	{NULL, NULL} /* sentinel */
331	n/a	};
332	n/a
333	n/a
334	n/a	static PyTypeObject _grouper_type = {
335	n/a	PyVarObject_HEAD_INIT(NULL, 0)
336	n/a	"itertools._grouper", /* tp_name */
337	n/a	sizeof(_grouperobject), /* tp_basicsize */
338	n/a	0, /* tp_itemsize */
339	n/a	/* methods */
340	n/a	(destructor)_grouper_dealloc, /* tp_dealloc */
341	n/a	0, /* tp_print */
342	n/a	0, /* tp_getattr */
343	n/a	0, /* tp_setattr */
344	n/a	0, /* tp_reserved */
345	n/a	0, /* tp_repr */
346	n/a	0, /* tp_as_number */
347	n/a	0, /* tp_as_sequence */
348	n/a	0, /* tp_as_mapping */
349	n/a	0, /* tp_hash */
350	n/a	0, /* tp_call */
351	n/a	0, /* tp_str */
352	n/a	PyObject_GenericGetAttr, /* tp_getattro */
353	n/a	0, /* tp_setattro */
354	n/a	0, /* tp_as_buffer */
355	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC, /* tp_flags */
356	n/a	0, /* tp_doc */
357	n/a	(traverseproc)_grouper_traverse, /* tp_traverse */
358	n/a	0, /* tp_clear */
359	n/a	0, /* tp_richcompare */
360	n/a	0, /* tp_weaklistoffset */
361	n/a	PyObject_SelfIter, /* tp_iter */
362	n/a	(iternextfunc)_grouper_next, /* tp_iternext */
363	n/a	_grouper_methods, /* tp_methods */
364	n/a	0, /* tp_members */
365	n/a	0, /* tp_getset */
366	n/a	0, /* tp_base */
367	n/a	0, /* tp_dict */
368	n/a	0, /* tp_descr_get */
369	n/a	0, /* tp_descr_set */
370	n/a	0, /* tp_dictoffset */
371	n/a	0, /* tp_init */
372	n/a	0, /* tp_alloc */
373	n/a	_grouper_new, /* tp_new */
374	n/a	PyObject_GC_Del, /* tp_free */
375	n/a	};
376	n/a
377	n/a
378	n/a	/* tee object and with supporting function and objects ***********************/
379	n/a
380	n/a	/* The teedataobject pre-allocates space for LINKCELLS number of objects.
381	n/a	To help the object fit neatly inside cache lines (space for 16 to 32
382	n/a	pointers), the value should be a multiple of 16 minus space for
383	n/a	the other structure members including PyHEAD overhead. The larger the
384	n/a	value, the less memory overhead per object and the less time spent
385	n/a	allocating/deallocating new links. The smaller the number, the less
386	n/a	wasted space and the more rapid freeing of older data.
387	n/a	*/
388	n/a	#define LINKCELLS 57
389	n/a
390	n/a	typedef struct {
391	n/a	PyObject_HEAD
392	n/a	PyObject *it;
393	n/a	int numread; /* 0 <= numread <= LINKCELLS */
394	n/a	PyObject *nextlink;
395	n/a	PyObject *(values[LINKCELLS]);
396	n/a	} teedataobject;
397	n/a
398	n/a	typedef struct {
399	n/a	PyObject_HEAD
400	n/a	teedataobject *dataobj;
401	n/a	int index; /* 0 <= index <= LINKCELLS */
402	n/a	PyObject *weakreflist;
403	n/a	} teeobject;
404	n/a
405	n/a	static PyTypeObject teedataobject_type;
406	n/a
407	n/a	static PyObject *
408	n/a	teedataobject_newinternal(PyObject *it)
409	n/a	{
410	n/a	teedataobject *tdo;
411	n/a
412	n/a	tdo = PyObject_GC_New(teedataobject, &teedataobject_type);
413	n/a	if (tdo == NULL)
414	n/a	return NULL;
415	n/a
416	n/a	tdo->numread = 0;
417	n/a	tdo->nextlink = NULL;
418	n/a	Py_INCREF(it);
419	n/a	tdo->it = it;
420	n/a	PyObject_GC_Track(tdo);
421	n/a	return (PyObject *)tdo;
422	n/a	}
423	n/a
424	n/a	static PyObject *
425	n/a	teedataobject_jumplink(teedataobject *tdo)
426	n/a	{
427	n/a	if (tdo->nextlink == NULL)
428	n/a	tdo->nextlink = teedataobject_newinternal(tdo->it);
429	n/a	Py_XINCREF(tdo->nextlink);
430	n/a	return tdo->nextlink;
431	n/a	}
432	n/a
433	n/a	static PyObject *
434	n/a	teedataobject_getitem(teedataobject *tdo, int i)
435	n/a	{
436	n/a	PyObject *value;
437	n/a
438	n/a	assert(i < LINKCELLS);
439	n/a	if (i < tdo->numread)
440	n/a	value = tdo->values[i];
441	n/a	else {
442	n/a	/* this is the lead iterator, so fetch more data */
443	n/a	assert(i == tdo->numread);
444	n/a	value = PyIter_Next(tdo->it);
445	n/a	if (value == NULL)
446	n/a	return NULL;
447	n/a	tdo->numread++;
448	n/a	tdo->values[i] = value;
449	n/a	}
450	n/a	Py_INCREF(value);
451	n/a	return value;
452	n/a	}
453	n/a
454	n/a	static int
455	n/a	teedataobject_traverse(teedataobject tdo, visitproc visit, void arg)
456	n/a	{
457	n/a	int i;
458	n/a
459	n/a	Py_VISIT(tdo->it);
460	n/a	for (i = 0; i < tdo->numread; i++)
461	n/a	Py_VISIT(tdo->values[i]);
462	n/a	Py_VISIT(tdo->nextlink);
463	n/a	return 0;
464	n/a	}
465	n/a
466	n/a	static void
467	n/a	teedataobject_safe_decref(PyObject *obj)
468	n/a	{
469	n/a	while (obj && Py_TYPE(obj) == &teedataobject_type &&
470	n/a	Py_REFCNT(obj) == 1) {
471	n/a	PyObject nextlink = ((teedataobject )obj)->nextlink;
472	n/a	((teedataobject *)obj)->nextlink = NULL;
473	n/a	Py_DECREF(obj);
474	n/a	obj = nextlink;
475	n/a	}
476	n/a	Py_XDECREF(obj);
477	n/a	}
478	n/a
479	n/a	static int
480	n/a	teedataobject_clear(teedataobject *tdo)
481	n/a	{
482	n/a	int i;
483	n/a	PyObject *tmp;
484	n/a
485	n/a	Py_CLEAR(tdo->it);
486	n/a	for (i=0 ; i<tdo->numread ; i++)
487	n/a	Py_CLEAR(tdo->values[i]);
488	n/a	tmp = tdo->nextlink;
489	n/a	tdo->nextlink = NULL;
490	n/a	teedataobject_safe_decref(tmp);
491	n/a	return 0;
492	n/a	}
493	n/a
494	n/a	static void
495	n/a	teedataobject_dealloc(teedataobject *tdo)
496	n/a	{
497	n/a	PyObject_GC_UnTrack(tdo);
498	n/a	teedataobject_clear(tdo);
499	n/a	PyObject_GC_Del(tdo);
500	n/a	}
501	n/a
502	n/a	static PyObject *
503	n/a	teedataobject_reduce(teedataobject *tdo)
504	n/a	{
505	n/a	int i;
506	n/a	/* create a temporary list of already iterated values */
507	n/a	PyObject *values = PyList_New(tdo->numread);
508	n/a
509	n/a	if (!values)
510	n/a	return NULL;
511	n/a	for (i=0 ; i<tdo->numread ; i++) {
512	n/a	Py_INCREF(tdo->values[i]);
513	n/a	PyList_SET_ITEM(values, i, tdo->values[i]);
514	n/a	}
515	n/a	return Py_BuildValue("O(ONO)", Py_TYPE(tdo), tdo->it,
516	n/a	values,
517	n/a	tdo->nextlink ? tdo->nextlink : Py_None);
518	n/a	}
519	n/a
520	n/a	static PyTypeObject teedataobject_type;
521	n/a
522	n/a	static PyObject *
523	n/a	teedataobject_new(PyTypeObject type, PyObject args, PyObject *kw)
524	n/a	{
525	n/a	teedataobject *tdo;
526	n/a	PyObject it, values, *next;
527	n/a	Py_ssize_t i, len;
528	n/a
529	n/a	assert(type == &teedataobject_type);
530	n/a	if (!PyArg_ParseTuple(args, "OO!O", &it, &PyList_Type, &values, &next))
531	n/a	return NULL;
532	n/a
533	n/a	tdo = (teedataobject *)teedataobject_newinternal(it);
534	n/a	if (!tdo)
535	n/a	return NULL;
536	n/a
537	n/a	len = PyList_GET_SIZE(values);
538	n/a	if (len > LINKCELLS)
539	n/a	goto err;
540	n/a	for (i=0; i<len; i++) {
541	n/a	tdo->values[i] = PyList_GET_ITEM(values, i);
542	n/a	Py_INCREF(tdo->values[i]);
543	n/a	}
544	n/a	/* len <= LINKCELLS < INT_MAX */
545	n/a	tdo->numread = Py_SAFE_DOWNCAST(len, Py_ssize_t, int);
546	n/a
547	n/a	if (len == LINKCELLS) {
548	n/a	if (next != Py_None) {
549	n/a	if (Py_TYPE(next) != &teedataobject_type)
550	n/a	goto err;
551	n/a	assert(tdo->nextlink == NULL);
552	n/a	Py_INCREF(next);
553	n/a	tdo->nextlink = next;
554	n/a	}
555	n/a	} else {
556	n/a	if (next != Py_None)
557	n/a	goto err; /* shouldn't have a next if we are not full */
558	n/a	}
559	n/a	return (PyObject*)tdo;
560	n/a
561	n/a	err:
562	n/a	Py_XDECREF(tdo);
563	n/a	PyErr_SetString(PyExc_ValueError, "Invalid arguments");
564	n/a	return NULL;
565	n/a	}
566	n/a
567	n/a	static PyMethodDef teedataobject_methods[] = {
568	n/a	{"__reduce__", (PyCFunction)teedataobject_reduce, METH_NOARGS,
569	n/a	reduce_doc},
570	n/a	{NULL, NULL} /* sentinel */
571	n/a	};
572	n/a
573	n/a	PyDoc_STRVAR(teedataobject_doc, "Data container common to multiple tee objects.");
574	n/a
575	n/a	static PyTypeObject teedataobject_type = {
576	n/a	PyVarObject_HEAD_INIT(0, 0) /* Must fill in type value later */
577	n/a	"itertools._tee_dataobject", /* tp_name */
578	n/a	sizeof(teedataobject), /* tp_basicsize */
579	n/a	0, /* tp_itemsize */
580	n/a	/* methods */
581	n/a	(destructor)teedataobject_dealloc, /* tp_dealloc */
582	n/a	0, /* tp_print */
583	n/a	0, /* tp_getattr */
584	n/a	0, /* tp_setattr */
585	n/a	0, /* tp_reserved */
586	n/a	0, /* tp_repr */
587	n/a	0, /* tp_as_number */
588	n/a	0, /* tp_as_sequence */
589	n/a	0, /* tp_as_mapping */
590	n/a	0, /* tp_hash */
591	n/a	0, /* tp_call */
592	n/a	0, /* tp_str */
593	n/a	PyObject_GenericGetAttr, /* tp_getattro */
594	n/a	0, /* tp_setattro */
595	n/a	0, /* tp_as_buffer */
596	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC, /* tp_flags */
597	n/a	teedataobject_doc, /* tp_doc */
598	n/a	(traverseproc)teedataobject_traverse, /* tp_traverse */
599	n/a	(inquiry)teedataobject_clear, /* tp_clear */
600	n/a	0, /* tp_richcompare */
601	n/a	0, /* tp_weaklistoffset */
602	n/a	0, /* tp_iter */
603	n/a	0, /* tp_iternext */
604	n/a	teedataobject_methods, /* tp_methods */
605	n/a	0, /* tp_members */
606	n/a	0, /* tp_getset */
607	n/a	0, /* tp_base */
608	n/a	0, /* tp_dict */
609	n/a	0, /* tp_descr_get */
610	n/a	0, /* tp_descr_set */
611	n/a	0, /* tp_dictoffset */
612	n/a	0, /* tp_init */
613	n/a	0, /* tp_alloc */
614	n/a	teedataobject_new, /* tp_new */
615	n/a	PyObject_GC_Del, /* tp_free */
616	n/a	};
617	n/a
618	n/a
619	n/a	static PyTypeObject tee_type;
620	n/a
621	n/a	static PyObject *
622	n/a	tee_next(teeobject *to)
623	n/a	{
624	n/a	PyObject value, link;
625	n/a
626	n/a	if (to->index >= LINKCELLS) {
627	n/a	link = teedataobject_jumplink(to->dataobj);
628	n/a	if (link == NULL)
629	n/a	return NULL;
630	n/a	Py_SETREF(to->dataobj, (teedataobject *)link);
631	n/a	to->index = 0;
632	n/a	}
633	n/a	value = teedataobject_getitem(to->dataobj, to->index);
634	n/a	if (value == NULL)
635	n/a	return NULL;
636	n/a	to->index++;
637	n/a	return value;
638	n/a	}
639	n/a
640	n/a	static int
641	n/a	tee_traverse(teeobject to, visitproc visit, void arg)
642	n/a	{
643	n/a	Py_VISIT((PyObject *)to->dataobj);
644	n/a	return 0;
645	n/a	}
646	n/a
647	n/a	static PyObject *
648	n/a	tee_copy(teeobject *to)
649	n/a	{
650	n/a	teeobject *newto;
651	n/a
652	n/a	newto = PyObject_GC_New(teeobject, &tee_type);
653	n/a	if (newto == NULL)
654	n/a	return NULL;
655	n/a	Py_INCREF(to->dataobj);
656	n/a	newto->dataobj = to->dataobj;
657	n/a	newto->index = to->index;
658	n/a	newto->weakreflist = NULL;
659	n/a	PyObject_GC_Track(newto);
660	n/a	return (PyObject *)newto;
661	n/a	}
662	n/a
663	n/a	PyDoc_STRVAR(teecopy_doc, "Returns an independent iterator.");
664	n/a
665	n/a	static PyObject *
666	n/a	tee_fromiterable(PyObject *iterable)
667	n/a	{
668	n/a	teeobject *to;
669	n/a	PyObject *it = NULL;
670	n/a
671	n/a	it = PyObject_GetIter(iterable);
672	n/a	if (it == NULL)
673	n/a	return NULL;
674	n/a	if (PyObject_TypeCheck(it, &tee_type)) {
675	n/a	to = (teeobject )tee_copy((teeobject )it);
676	n/a	goto done;
677	n/a	}
678	n/a
679	n/a	to = PyObject_GC_New(teeobject, &tee_type);
680	n/a	if (to == NULL)
681	n/a	goto done;
682	n/a	to->dataobj = (teedataobject *)teedataobject_newinternal(it);
683	n/a	if (!to->dataobj) {
684	n/a	PyObject_GC_Del(to);
685	n/a	to = NULL;
686	n/a	goto done;
687	n/a	}
688	n/a
689	n/a	to->index = 0;
690	n/a	to->weakreflist = NULL;
691	n/a	PyObject_GC_Track(to);
692	n/a	done:
693	n/a	Py_XDECREF(it);
694	n/a	return (PyObject *)to;
695	n/a	}
696	n/a
697	n/a	static PyObject *
698	n/a	tee_new(PyTypeObject type, PyObject args, PyObject *kw)
699	n/a	{
700	n/a	PyObject *iterable;
701	n/a
702	n/a	if (!PyArg_UnpackTuple(args, "_tee", 1, 1, &iterable))
703	n/a	return NULL;
704	n/a	return tee_fromiterable(iterable);
705	n/a	}
706	n/a
707	n/a	static int
708	n/a	tee_clear(teeobject *to)
709	n/a	{
710	n/a	if (to->weakreflist != NULL)
711	n/a	PyObject_ClearWeakRefs((PyObject *) to);
712	n/a	Py_CLEAR(to->dataobj);
713	n/a	return 0;
714	n/a	}
715	n/a
716	n/a	static void
717	n/a	tee_dealloc(teeobject *to)
718	n/a	{
719	n/a	PyObject_GC_UnTrack(to);
720	n/a	tee_clear(to);
721	n/a	PyObject_GC_Del(to);
722	n/a	}
723	n/a
724	n/a	static PyObject *
725	n/a	tee_reduce(teeobject *to)
726	n/a	{
727	n/a	return Py_BuildValue("O(())(Oi)", Py_TYPE(to), to->dataobj, to->index);
728	n/a	}
729	n/a
730	n/a	static PyObject *
731	n/a	tee_setstate(teeobject to, PyObject state)
732	n/a	{
733	n/a	teedataobject *tdo;
734	n/a	int index;
735	n/a	if (!PyTuple_Check(state)) {
736	n/a	PyErr_SetString(PyExc_TypeError, "state is not a tuple");
737	n/a	return NULL;
738	n/a	}
739	n/a	if (!PyArg_ParseTuple(state, "O!i", &teedataobject_type, &tdo, &index)) {
740	n/a	return NULL;
741	n/a	}
742	n/a	if (index < 0 \|\| index > LINKCELLS) {
743	n/a	PyErr_SetString(PyExc_ValueError, "Index out of range");
744	n/a	return NULL;
745	n/a	}
746	n/a	Py_INCREF(tdo);
747	n/a	Py_XSETREF(to->dataobj, tdo);
748	n/a	to->index = index;
749	n/a	Py_RETURN_NONE;
750	n/a	}
751	n/a
752	n/a	PyDoc_STRVAR(teeobject_doc,
753	n/a	"Iterator wrapped to make it copyable");
754	n/a
755	n/a	static PyMethodDef tee_methods[] = {
756	n/a	{"__copy__", (PyCFunction)tee_copy, METH_NOARGS, teecopy_doc},
757	n/a	{"__reduce__", (PyCFunction)tee_reduce, METH_NOARGS, reduce_doc},
758	n/a	{"__setstate__", (PyCFunction)tee_setstate, METH_O, setstate_doc},
759	n/a	{NULL, NULL} /* sentinel */
760	n/a	};
761	n/a
762	n/a	static PyTypeObject tee_type = {
763	n/a	PyVarObject_HEAD_INIT(NULL, 0)
764	n/a	"itertools._tee", /* tp_name */
765	n/a	sizeof(teeobject), /* tp_basicsize */
766	n/a	0, /* tp_itemsize */
767	n/a	/* methods */
768	n/a	(destructor)tee_dealloc, /* tp_dealloc */
769	n/a	0, /* tp_print */
770	n/a	0, /* tp_getattr */
771	n/a	0, /* tp_setattr */
772	n/a	0, /* tp_reserved */
773	n/a	0, /* tp_repr */
774	n/a	0, /* tp_as_number */
775	n/a	0, /* tp_as_sequence */
776	n/a	0, /* tp_as_mapping */
777	n/a	0, /* tp_hash */
778	n/a	0, /* tp_call */
779	n/a	0, /* tp_str */
780	n/a	0, /* tp_getattro */
781	n/a	0, /* tp_setattro */
782	n/a	0, /* tp_as_buffer */
783	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC, /* tp_flags */
784	n/a	teeobject_doc, /* tp_doc */
785	n/a	(traverseproc)tee_traverse, /* tp_traverse */
786	n/a	(inquiry)tee_clear, /* tp_clear */
787	n/a	0, /* tp_richcompare */
788	n/a	offsetof(teeobject, weakreflist), /* tp_weaklistoffset */
789	n/a	PyObject_SelfIter, /* tp_iter */
790	n/a	(iternextfunc)tee_next, /* tp_iternext */
791	n/a	tee_methods, /* tp_methods */
792	n/a	0, /* tp_members */
793	n/a	0, /* tp_getset */
794	n/a	0, /* tp_base */
795	n/a	0, /* tp_dict */
796	n/a	0, /* tp_descr_get */
797	n/a	0, /* tp_descr_set */
798	n/a	0, /* tp_dictoffset */
799	n/a	0, /* tp_init */
800	n/a	0, /* tp_alloc */
801	n/a	tee_new, /* tp_new */
802	n/a	PyObject_GC_Del, /* tp_free */
803	n/a	};
804	n/a
805	n/a	static PyObject *
806	n/a	tee(PyObject self, PyObject args)
807	n/a	{
808	n/a	Py_ssize_t i, n=2;
809	n/a	PyObject it, iterable, copyable, result;
810	n/a	_Py_IDENTIFIER(__copy__);
811	n/a
812	n/a	if (!PyArg_ParseTuple(args, "O\|n", &iterable, &n))
813	n/a	return NULL;
814	n/a	if (n < 0) {
815	n/a	PyErr_SetString(PyExc_ValueError, "n must be >= 0");
816	n/a	return NULL;
817	n/a	}
818	n/a	result = PyTuple_New(n);
819	n/a	if (result == NULL)
820	n/a	return NULL;
821	n/a	if (n == 0)
822	n/a	return result;
823	n/a	it = PyObject_GetIter(iterable);
824	n/a	if (it == NULL) {
825	n/a	Py_DECREF(result);
826	n/a	return NULL;
827	n/a	}
828	n/a	if (!_PyObject_HasAttrId(it, &PyId___copy__)) {
829	n/a	copyable = tee_fromiterable(it);
830	n/a	Py_DECREF(it);
831	n/a	if (copyable == NULL) {
832	n/a	Py_DECREF(result);
833	n/a	return NULL;
834	n/a	}
835	n/a	} else
836	n/a	copyable = it;
837	n/a	PyTuple_SET_ITEM(result, 0, copyable);
838	n/a	for (i=1 ; i<n ; i++) {
839	n/a
840	n/a	copyable = _PyObject_CallMethodId(copyable, &PyId___copy__, NULL);
841	n/a	if (copyable == NULL) {
842	n/a	Py_DECREF(result);
843	n/a	return NULL;
844	n/a	}
845	n/a	PyTuple_SET_ITEM(result, i, copyable);
846	n/a	}
847	n/a	return result;
848	n/a	}
849	n/a
850	n/a	PyDoc_STRVAR(tee_doc,
851	n/a	"tee(iterable, n=2) --> tuple of n independent iterators.");
852	n/a
853	n/a
854	n/a	/* cycle object **************************************************************/
855	n/a
856	n/a	typedef struct {
857	n/a	PyObject_HEAD
858	n/a	PyObject *it;
859	n/a	PyObject *saved;
860	n/a	Py_ssize_t index;
861	n/a	int firstpass;
862	n/a	} cycleobject;
863	n/a
864	n/a	static PyTypeObject cycle_type;
865	n/a
866	n/a	static PyObject *
867	n/a	cycle_new(PyTypeObject type, PyObject args, PyObject *kwds)
868	n/a	{
869	n/a	PyObject *it;
870	n/a	PyObject *iterable;
871	n/a	PyObject *saved;
872	n/a	cycleobject *lz;
873	n/a
874	n/a	if (type == &cycle_type && !_PyArg_NoKeywords("cycle()", kwds))
875	n/a	return NULL;
876	n/a
877	n/a	if (!PyArg_UnpackTuple(args, "cycle", 1, 1, &iterable))
878	n/a	return NULL;
879	n/a
880	n/a	/* Get iterator. */
881	n/a	it = PyObject_GetIter(iterable);
882	n/a	if (it == NULL)
883	n/a	return NULL;
884	n/a
885	n/a	saved = PyList_New(0);
886	n/a	if (saved == NULL) {
887	n/a	Py_DECREF(it);
888	n/a	return NULL;
889	n/a	}
890	n/a
891	n/a	/* create cycleobject structure */
892	n/a	lz = (cycleobject *)type->tp_alloc(type, 0);
893	n/a	if (lz == NULL) {
894	n/a	Py_DECREF(it);
895	n/a	Py_DECREF(saved);
896	n/a	return NULL;
897	n/a	}
898	n/a	lz->it = it;
899	n/a	lz->saved = saved;
900	n/a	lz->index = 0;
901	n/a	lz->firstpass = 0;
902	n/a
903	n/a	return (PyObject *)lz;
904	n/a	}
905	n/a
906	n/a	static void
907	n/a	cycle_dealloc(cycleobject *lz)
908	n/a	{
909	n/a	PyObject_GC_UnTrack(lz);
910	n/a	Py_XDECREF(lz->it);
911	n/a	Py_XDECREF(lz->saved);
912	n/a	Py_TYPE(lz)->tp_free(lz);
913	n/a	}
914	n/a
915	n/a	static int
916	n/a	cycle_traverse(cycleobject lz, visitproc visit, void arg)
917	n/a	{
918	n/a	if (lz->it)
919	n/a	Py_VISIT(lz->it);
920	n/a	Py_VISIT(lz->saved);
921	n/a	return 0;
922	n/a	}
923	n/a
924	n/a	static PyObject *
925	n/a	cycle_next(cycleobject *lz)
926	n/a	{
927	n/a	PyObject *item;
928	n/a
929	n/a	if (lz->it != NULL) {
930	n/a	item = PyIter_Next(lz->it);
931	n/a	if (item != NULL) {
932	n/a	if (lz->firstpass)
933	n/a	return item;
934	n/a	if (PyList_Append(lz->saved, item)) {
935	n/a	Py_DECREF(item);
936	n/a	return NULL;
937	n/a	}
938	n/a	return item;
939	n/a	}
940	n/a	/* Note: StopIteration is already cleared by PyIter_Next() */
941	n/a	if (PyErr_Occurred())
942	n/a	return NULL;
943	n/a	Py_CLEAR(lz->it);
944	n/a	}
945	n/a	if (Py_SIZE(lz->saved) == 0)
946	n/a	return NULL;
947	n/a	item = PyList_GET_ITEM(lz->saved, lz->index);
948	n/a	lz->index++;
949	n/a	if (lz->index >= Py_SIZE(lz->saved))
950	n/a	lz->index = 0;
951	n/a	Py_INCREF(item);
952	n/a	return item;
953	n/a	}
954	n/a
955	n/a	static PyObject *
956	n/a	cycle_reduce(cycleobject *lz)
957	n/a	{
958	n/a	/* Create a new cycle with the iterator tuple, then set the saved state */
959	n/a	if (lz->it == NULL) {
960	n/a	PyObject *it = PyObject_GetIter(lz->saved);
961	n/a	if (it == NULL)
962	n/a	return NULL;
963	n/a	if (lz->index != 0) {
964	n/a	_Py_IDENTIFIER(__setstate__);
965	n/a	PyObject *res = _PyObject_CallMethodId(it, &PyId___setstate__,
966	n/a	"n", lz->index);
967	n/a	if (res == NULL) {
968	n/a	Py_DECREF(it);
969	n/a	return NULL;
970	n/a	}
971	n/a	Py_DECREF(res);
972	n/a	}
973	n/a	return Py_BuildValue("O(N)(Oi)", Py_TYPE(lz), it, lz->saved, 1);
974	n/a	}
975	n/a	return Py_BuildValue("O(O)(Oi)", Py_TYPE(lz), lz->it, lz->saved,
976	n/a	lz->firstpass);
977	n/a	}
978	n/a
979	n/a	static PyObject *
980	n/a	cycle_setstate(cycleobject lz, PyObject state)
981	n/a	{
982	n/a	PyObject *saved=NULL;
983	n/a	int firstpass;
984	n/a	if (!PyTuple_Check(state)) {
985	n/a	PyErr_SetString(PyExc_TypeError, "state is not a tuple");
986	n/a	return NULL;
987	n/a	}
988	n/a	if (!PyArg_ParseTuple(state, "O!i", &PyList_Type, &saved, &firstpass)) {
989	n/a	return NULL;
990	n/a	}
991	n/a	Py_INCREF(saved);
992	n/a	Py_XSETREF(lz->saved, saved);
993	n/a	lz->firstpass = firstpass != 0;
994	n/a	lz->index = 0;
995	n/a	Py_RETURN_NONE;
996	n/a	}
997	n/a
998	n/a	static PyMethodDef cycle_methods[] = {
999	n/a	{"__reduce__", (PyCFunction)cycle_reduce, METH_NOARGS,
1000	n/a	reduce_doc},
1001	n/a	{"__setstate__", (PyCFunction)cycle_setstate, METH_O,
1002	n/a	setstate_doc},
1003	n/a	{NULL, NULL} /* sentinel */
1004	n/a	};
1005	n/a
1006	n/a	PyDoc_STRVAR(cycle_doc,
1007	n/a	"cycle(iterable) --> cycle object\n\
1008	n/a	\n\
1009	n/a	Return elements from the iterable until it is exhausted.\n\
1010	n/a	Then repeat the sequence indefinitely.");
1011	n/a
1012	n/a	static PyTypeObject cycle_type = {
1013	n/a	PyVarObject_HEAD_INIT(NULL, 0)
1014	n/a	"itertools.cycle", /* tp_name */
1015	n/a	sizeof(cycleobject), /* tp_basicsize */
1016	n/a	0, /* tp_itemsize */
1017	n/a	/* methods */
1018	n/a	(destructor)cycle_dealloc, /* tp_dealloc */
1019	n/a	0, /* tp_print */
1020	n/a	0, /* tp_getattr */
1021	n/a	0, /* tp_setattr */
1022	n/a	0, /* tp_reserved */
1023	n/a	0, /* tp_repr */
1024	n/a	0, /* tp_as_number */
1025	n/a	0, /* tp_as_sequence */
1026	n/a	0, /* tp_as_mapping */
1027	n/a	0, /* tp_hash */
1028	n/a	0, /* tp_call */
1029	n/a	0, /* tp_str */
1030	n/a	PyObject_GenericGetAttr, /* tp_getattro */
1031	n/a	0, /* tp_setattro */
1032	n/a	0, /* tp_as_buffer */
1033	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
1034	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
1035	n/a	cycle_doc, /* tp_doc */
1036	n/a	(traverseproc)cycle_traverse, /* tp_traverse */
1037	n/a	0, /* tp_clear */
1038	n/a	0, /* tp_richcompare */
1039	n/a	0, /* tp_weaklistoffset */
1040	n/a	PyObject_SelfIter, /* tp_iter */
1041	n/a	(iternextfunc)cycle_next, /* tp_iternext */
1042	n/a	cycle_methods, /* tp_methods */
1043	n/a	0, /* tp_members */
1044	n/a	0, /* tp_getset */
1045	n/a	0, /* tp_base */
1046	n/a	0, /* tp_dict */
1047	n/a	0, /* tp_descr_get */
1048	n/a	0, /* tp_descr_set */
1049	n/a	0, /* tp_dictoffset */
1050	n/a	0, /* tp_init */
1051	n/a	0, /* tp_alloc */
1052	n/a	cycle_new, /* tp_new */
1053	n/a	PyObject_GC_Del, /* tp_free */
1054	n/a	};
1055	n/a
1056	n/a
1057	n/a	/* dropwhile object **********************************************************/
1058	n/a
1059	n/a	typedef struct {
1060	n/a	PyObject_HEAD
1061	n/a	PyObject *func;
1062	n/a	PyObject *it;
1063	n/a	long start;
1064	n/a	} dropwhileobject;
1065	n/a
1066	n/a	static PyTypeObject dropwhile_type;
1067	n/a
1068	n/a	static PyObject *
1069	n/a	dropwhile_new(PyTypeObject type, PyObject args, PyObject *kwds)
1070	n/a	{
1071	n/a	PyObject func, seq;
1072	n/a	PyObject *it;
1073	n/a	dropwhileobject *lz;
1074	n/a
1075	n/a	if (type == &dropwhile_type && !_PyArg_NoKeywords("dropwhile()", kwds))
1076	n/a	return NULL;
1077	n/a
1078	n/a	if (!PyArg_UnpackTuple(args, "dropwhile", 2, 2, &func, &seq))
1079	n/a	return NULL;
1080	n/a
1081	n/a	/* Get iterator. */
1082	n/a	it = PyObject_GetIter(seq);
1083	n/a	if (it == NULL)
1084	n/a	return NULL;
1085	n/a
1086	n/a	/* create dropwhileobject structure */
1087	n/a	lz = (dropwhileobject *)type->tp_alloc(type, 0);
1088	n/a	if (lz == NULL) {
1089	n/a	Py_DECREF(it);
1090	n/a	return NULL;
1091	n/a	}
1092	n/a	Py_INCREF(func);
1093	n/a	lz->func = func;
1094	n/a	lz->it = it;
1095	n/a	lz->start = 0;
1096	n/a
1097	n/a	return (PyObject *)lz;
1098	n/a	}
1099	n/a
1100	n/a	static void
1101	n/a	dropwhile_dealloc(dropwhileobject *lz)
1102	n/a	{
1103	n/a	PyObject_GC_UnTrack(lz);
1104	n/a	Py_XDECREF(lz->func);
1105	n/a	Py_XDECREF(lz->it);
1106	n/a	Py_TYPE(lz)->tp_free(lz);
1107	n/a	}
1108	n/a
1109	n/a	static int
1110	n/a	dropwhile_traverse(dropwhileobject lz, visitproc visit, void arg)
1111	n/a	{
1112	n/a	Py_VISIT(lz->it);
1113	n/a	Py_VISIT(lz->func);
1114	n/a	return 0;
1115	n/a	}
1116	n/a
1117	n/a	static PyObject *
1118	n/a	dropwhile_next(dropwhileobject *lz)
1119	n/a	{
1120	n/a	PyObject item, good;
1121	n/a	PyObject *it = lz->it;
1122	n/a	long ok;
1123	n/a	PyObject (iternext)(PyObject *);
1124	n/a
1125	n/a	iternext = *Py_TYPE(it)->tp_iternext;
1126	n/a	for (;;) {
1127	n/a	item = iternext(it);
1128	n/a	if (item == NULL)
1129	n/a	return NULL;
1130	n/a	if (lz->start == 1)
1131	n/a	return item;
1132	n/a
1133	n/a	good = PyObject_CallFunctionObjArgs(lz->func, item, NULL);
1134	n/a	if (good == NULL) {
1135	n/a	Py_DECREF(item);
1136	n/a	return NULL;
1137	n/a	}
1138	n/a	ok = PyObject_IsTrue(good);
1139	n/a	Py_DECREF(good);
1140	n/a	if (ok == 0) {
1141	n/a	lz->start = 1;
1142	n/a	return item;
1143	n/a	}
1144	n/a	Py_DECREF(item);
1145	n/a	if (ok < 0)
1146	n/a	return NULL;
1147	n/a	}
1148	n/a	}
1149	n/a
1150	n/a	static PyObject *
1151	n/a	dropwhile_reduce(dropwhileobject *lz)
1152	n/a	{
1153	n/a	return Py_BuildValue("O(OO)l", Py_TYPE(lz), lz->func, lz->it, lz->start);
1154	n/a	}
1155	n/a
1156	n/a	static PyObject *
1157	n/a	dropwhile_setstate(dropwhileobject lz, PyObject state)
1158	n/a	{
1159	n/a	int start = PyObject_IsTrue(state);
1160	n/a	if (start < 0)
1161	n/a	return NULL;
1162	n/a	lz->start = start;
1163	n/a	Py_RETURN_NONE;
1164	n/a	}
1165	n/a
1166	n/a	static PyMethodDef dropwhile_methods[] = {
1167	n/a	{"__reduce__", (PyCFunction)dropwhile_reduce, METH_NOARGS,
1168	n/a	reduce_doc},
1169	n/a	{"__setstate__", (PyCFunction)dropwhile_setstate, METH_O,
1170	n/a	setstate_doc},
1171	n/a	{NULL, NULL} /* sentinel */
1172	n/a	};
1173	n/a
1174	n/a	PyDoc_STRVAR(dropwhile_doc,
1175	n/a	"dropwhile(predicate, iterable) --> dropwhile object\n\
1176	n/a	\n\
1177	n/a	Drop items from the iterable while predicate(item) is true.\n\
1178	n/a	Afterwards, return every element until the iterable is exhausted.");
1179	n/a
1180	n/a	static PyTypeObject dropwhile_type = {
1181	n/a	PyVarObject_HEAD_INIT(NULL, 0)
1182	n/a	"itertools.dropwhile", /* tp_name */
1183	n/a	sizeof(dropwhileobject), /* tp_basicsize */
1184	n/a	0, /* tp_itemsize */
1185	n/a	/* methods */
1186	n/a	(destructor)dropwhile_dealloc, /* tp_dealloc */
1187	n/a	0, /* tp_print */
1188	n/a	0, /* tp_getattr */
1189	n/a	0, /* tp_setattr */
1190	n/a	0, /* tp_reserved */
1191	n/a	0, /* tp_repr */
1192	n/a	0, /* tp_as_number */
1193	n/a	0, /* tp_as_sequence */
1194	n/a	0, /* tp_as_mapping */
1195	n/a	0, /* tp_hash */
1196	n/a	0, /* tp_call */
1197	n/a	0, /* tp_str */
1198	n/a	PyObject_GenericGetAttr, /* tp_getattro */
1199	n/a	0, /* tp_setattro */
1200	n/a	0, /* tp_as_buffer */
1201	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
1202	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
1203	n/a	dropwhile_doc, /* tp_doc */
1204	n/a	(traverseproc)dropwhile_traverse, /* tp_traverse */
1205	n/a	0, /* tp_clear */
1206	n/a	0, /* tp_richcompare */
1207	n/a	0, /* tp_weaklistoffset */
1208	n/a	PyObject_SelfIter, /* tp_iter */
1209	n/a	(iternextfunc)dropwhile_next, /* tp_iternext */
1210	n/a	dropwhile_methods, /* tp_methods */
1211	n/a	0, /* tp_members */
1212	n/a	0, /* tp_getset */
1213	n/a	0, /* tp_base */
1214	n/a	0, /* tp_dict */
1215	n/a	0, /* tp_descr_get */
1216	n/a	0, /* tp_descr_set */
1217	n/a	0, /* tp_dictoffset */
1218	n/a	0, /* tp_init */
1219	n/a	0, /* tp_alloc */
1220	n/a	dropwhile_new, /* tp_new */
1221	n/a	PyObject_GC_Del, /* tp_free */
1222	n/a	};
1223	n/a
1224	n/a
1225	n/a	/* takewhile object **********************************************************/
1226	n/a
1227	n/a	typedef struct {
1228	n/a	PyObject_HEAD
1229	n/a	PyObject *func;
1230	n/a	PyObject *it;
1231	n/a	long stop;
1232	n/a	} takewhileobject;
1233	n/a
1234	n/a	static PyTypeObject takewhile_type;
1235	n/a
1236	n/a	static PyObject *
1237	n/a	takewhile_new(PyTypeObject type, PyObject args, PyObject *kwds)
1238	n/a	{
1239	n/a	PyObject func, seq;
1240	n/a	PyObject *it;
1241	n/a	takewhileobject *lz;
1242	n/a
1243	n/a	if (type == &takewhile_type && !_PyArg_NoKeywords("takewhile()", kwds))
1244	n/a	return NULL;
1245	n/a
1246	n/a	if (!PyArg_UnpackTuple(args, "takewhile", 2, 2, &func, &seq))
1247	n/a	return NULL;
1248	n/a
1249	n/a	/* Get iterator. */
1250	n/a	it = PyObject_GetIter(seq);
1251	n/a	if (it == NULL)
1252	n/a	return NULL;
1253	n/a
1254	n/a	/* create takewhileobject structure */
1255	n/a	lz = (takewhileobject *)type->tp_alloc(type, 0);
1256	n/a	if (lz == NULL) {
1257	n/a	Py_DECREF(it);
1258	n/a	return NULL;
1259	n/a	}
1260	n/a	Py_INCREF(func);
1261	n/a	lz->func = func;
1262	n/a	lz->it = it;
1263	n/a	lz->stop = 0;
1264	n/a
1265	n/a	return (PyObject *)lz;
1266	n/a	}
1267	n/a
1268	n/a	static void
1269	n/a	takewhile_dealloc(takewhileobject *lz)
1270	n/a	{
1271	n/a	PyObject_GC_UnTrack(lz);
1272	n/a	Py_XDECREF(lz->func);
1273	n/a	Py_XDECREF(lz->it);
1274	n/a	Py_TYPE(lz)->tp_free(lz);
1275	n/a	}
1276	n/a
1277	n/a	static int
1278	n/a	takewhile_traverse(takewhileobject lz, visitproc visit, void arg)
1279	n/a	{
1280	n/a	Py_VISIT(lz->it);
1281	n/a	Py_VISIT(lz->func);
1282	n/a	return 0;
1283	n/a	}
1284	n/a
1285	n/a	static PyObject *
1286	n/a	takewhile_next(takewhileobject *lz)
1287	n/a	{
1288	n/a	PyObject item, good;
1289	n/a	PyObject *it = lz->it;
1290	n/a	long ok;
1291	n/a
1292	n/a	if (lz->stop == 1)
1293	n/a	return NULL;
1294	n/a
1295	n/a	item = (*Py_TYPE(it)->tp_iternext)(it);
1296	n/a	if (item == NULL)
1297	n/a	return NULL;
1298	n/a
1299	n/a	good = PyObject_CallFunctionObjArgs(lz->func, item, NULL);
1300	n/a	if (good == NULL) {
1301	n/a	Py_DECREF(item);
1302	n/a	return NULL;
1303	n/a	}
1304	n/a	ok = PyObject_IsTrue(good);
1305	n/a	Py_DECREF(good);
1306	n/a	if (ok > 0)
1307	n/a	return item;
1308	n/a	Py_DECREF(item);
1309	n/a	if (ok == 0)
1310	n/a	lz->stop = 1;
1311	n/a	return NULL;
1312	n/a	}
1313	n/a
1314	n/a	static PyObject *
1315	n/a	takewhile_reduce(takewhileobject *lz)
1316	n/a	{
1317	n/a	return Py_BuildValue("O(OO)l", Py_TYPE(lz), lz->func, lz->it, lz->stop);
1318	n/a	}
1319	n/a
1320	n/a	static PyObject *
1321	n/a	takewhile_reduce_setstate(takewhileobject lz, PyObject state)
1322	n/a	{
1323	n/a	int stop = PyObject_IsTrue(state);
1324	n/a
1325	n/a	if (stop < 0)
1326	n/a	return NULL;
1327	n/a	lz->stop = stop;
1328	n/a	Py_RETURN_NONE;
1329	n/a	}
1330	n/a
1331	n/a	static PyMethodDef takewhile_reduce_methods[] = {
1332	n/a	{"__reduce__", (PyCFunction)takewhile_reduce, METH_NOARGS,
1333	n/a	reduce_doc},
1334	n/a	{"__setstate__", (PyCFunction)takewhile_reduce_setstate, METH_O,
1335	n/a	setstate_doc},
1336	n/a	{NULL, NULL} /* sentinel */
1337	n/a	};
1338	n/a	PyDoc_STRVAR(takewhile_doc,
1339	n/a	"takewhile(predicate, iterable) --> takewhile object\n\
1340	n/a	\n\
1341	n/a	Return successive entries from an iterable as long as the \n\
1342	n/a	predicate evaluates to true for each entry.");
1343	n/a
1344	n/a	static PyTypeObject takewhile_type = {
1345	n/a	PyVarObject_HEAD_INIT(NULL, 0)
1346	n/a	"itertools.takewhile", /* tp_name */
1347	n/a	sizeof(takewhileobject), /* tp_basicsize */
1348	n/a	0, /* tp_itemsize */
1349	n/a	/* methods */
1350	n/a	(destructor)takewhile_dealloc, /* tp_dealloc */
1351	n/a	0, /* tp_print */
1352	n/a	0, /* tp_getattr */
1353	n/a	0, /* tp_setattr */
1354	n/a	0, /* tp_reserved */
1355	n/a	0, /* tp_repr */
1356	n/a	0, /* tp_as_number */
1357	n/a	0, /* tp_as_sequence */
1358	n/a	0, /* tp_as_mapping */
1359	n/a	0, /* tp_hash */
1360	n/a	0, /* tp_call */
1361	n/a	0, /* tp_str */
1362	n/a	PyObject_GenericGetAttr, /* tp_getattro */
1363	n/a	0, /* tp_setattro */
1364	n/a	0, /* tp_as_buffer */
1365	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
1366	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
1367	n/a	takewhile_doc, /* tp_doc */
1368	n/a	(traverseproc)takewhile_traverse, /* tp_traverse */
1369	n/a	0, /* tp_clear */
1370	n/a	0, /* tp_richcompare */
1371	n/a	0, /* tp_weaklistoffset */
1372	n/a	PyObject_SelfIter, /* tp_iter */
1373	n/a	(iternextfunc)takewhile_next, /* tp_iternext */
1374	n/a	takewhile_reduce_methods, /* tp_methods */
1375	n/a	0, /* tp_members */
1376	n/a	0, /* tp_getset */
1377	n/a	0, /* tp_base */
1378	n/a	0, /* tp_dict */
1379	n/a	0, /* tp_descr_get */
1380	n/a	0, /* tp_descr_set */
1381	n/a	0, /* tp_dictoffset */
1382	n/a	0, /* tp_init */
1383	n/a	0, /* tp_alloc */
1384	n/a	takewhile_new, /* tp_new */
1385	n/a	PyObject_GC_Del, /* tp_free */
1386	n/a	};
1387	n/a
1388	n/a
1389	n/a	/* islice object *************************************************************/
1390	n/a
1391	n/a	typedef struct {
1392	n/a	PyObject_HEAD
1393	n/a	PyObject *it;
1394	n/a	Py_ssize_t next;
1395	n/a	Py_ssize_t stop;
1396	n/a	Py_ssize_t step;
1397	n/a	Py_ssize_t cnt;
1398	n/a	} isliceobject;
1399	n/a
1400	n/a	static PyTypeObject islice_type;
1401	n/a
1402	n/a	static PyObject *
1403	n/a	islice_new(PyTypeObject type, PyObject args, PyObject *kwds)
1404	n/a	{
1405	n/a	PyObject *seq;
1406	n/a	Py_ssize_t start=0, stop=-1, step=1;
1407	n/a	PyObject it, a1=NULL, a2=NULL, a3=NULL;
1408	n/a	Py_ssize_t numargs;
1409	n/a	isliceobject *lz;
1410	n/a
1411	n/a	if (type == &islice_type && !_PyArg_NoKeywords("islice()", kwds))
1412	n/a	return NULL;
1413	n/a
1414	n/a	if (!PyArg_UnpackTuple(args, "islice", 2, 4, &seq, &a1, &a2, &a3))
1415	n/a	return NULL;
1416	n/a
1417	n/a	numargs = PyTuple_Size(args);
1418	n/a	if (numargs == 2) {
1419	n/a	if (a1 != Py_None) {
1420	n/a	stop = PyLong_AsSsize_t(a1);
1421	n/a	if (stop == -1) {
1422	n/a	if (PyErr_Occurred())
1423	n/a	PyErr_Clear();
1424	n/a	PyErr_SetString(PyExc_ValueError,
1425	n/a	"Stop argument for islice() must be None or "
1426	n/a	"an integer: 0 <= x <= sys.maxsize.");
1427	n/a	return NULL;
1428	n/a	}
1429	n/a	}
1430	n/a	} else {
1431	n/a	if (a1 != Py_None)
1432	n/a	start = PyLong_AsSsize_t(a1);
1433	n/a	if (start == -1 && PyErr_Occurred())
1434	n/a	PyErr_Clear();
1435	n/a	if (a2 != Py_None) {
1436	n/a	stop = PyLong_AsSsize_t(a2);
1437	n/a	if (stop == -1) {
1438	n/a	if (PyErr_Occurred())
1439	n/a	PyErr_Clear();
1440	n/a	PyErr_SetString(PyExc_ValueError,
1441	n/a	"Stop argument for islice() must be None or "
1442	n/a	"an integer: 0 <= x <= sys.maxsize.");
1443	n/a	return NULL;
1444	n/a	}
1445	n/a	}
1446	n/a	}
1447	n/a	if (start<0 \|\| stop<-1) {
1448	n/a	PyErr_SetString(PyExc_ValueError,
1449	n/a	"Indices for islice() must be None or "
1450	n/a	"an integer: 0 <= x <= sys.maxsize.");
1451	n/a	return NULL;
1452	n/a	}
1453	n/a
1454	n/a	if (a3 != NULL) {
1455	n/a	if (a3 != Py_None)
1456	n/a	step = PyLong_AsSsize_t(a3);
1457	n/a	if (step == -1 && PyErr_Occurred())
1458	n/a	PyErr_Clear();
1459	n/a	}
1460	n/a	if (step<1) {
1461	n/a	PyErr_SetString(PyExc_ValueError,
1462	n/a	"Step for islice() must be a positive integer or None.");
1463	n/a	return NULL;
1464	n/a	}
1465	n/a
1466	n/a	/* Get iterator. */
1467	n/a	it = PyObject_GetIter(seq);
1468	n/a	if (it == NULL)
1469	n/a	return NULL;
1470	n/a
1471	n/a	/* create isliceobject structure */
1472	n/a	lz = (isliceobject *)type->tp_alloc(type, 0);
1473	n/a	if (lz == NULL) {
1474	n/a	Py_DECREF(it);
1475	n/a	return NULL;
1476	n/a	}
1477	n/a	lz->it = it;
1478	n/a	lz->next = start;
1479	n/a	lz->stop = stop;
1480	n/a	lz->step = step;
1481	n/a	lz->cnt = 0L;
1482	n/a
1483	n/a	return (PyObject *)lz;
1484	n/a	}
1485	n/a
1486	n/a	static void
1487	n/a	islice_dealloc(isliceobject *lz)
1488	n/a	{
1489	n/a	PyObject_GC_UnTrack(lz);
1490	n/a	Py_XDECREF(lz->it);
1491	n/a	Py_TYPE(lz)->tp_free(lz);
1492	n/a	}
1493	n/a
1494	n/a	static int
1495	n/a	islice_traverse(isliceobject lz, visitproc visit, void arg)
1496	n/a	{
1497	n/a	Py_VISIT(lz->it);
1498	n/a	return 0;
1499	n/a	}
1500	n/a
1501	n/a	static PyObject *
1502	n/a	islice_next(isliceobject *lz)
1503	n/a	{
1504	n/a	PyObject *item;
1505	n/a	PyObject *it = lz->it;
1506	n/a	Py_ssize_t stop = lz->stop;
1507	n/a	Py_ssize_t oldnext;
1508	n/a	PyObject (iternext)(PyObject *);
1509	n/a
1510	n/a	if (it == NULL)
1511	n/a	return NULL;
1512	n/a
1513	n/a	iternext = *Py_TYPE(it)->tp_iternext;
1514	n/a	while (lz->cnt < lz->next) {
1515	n/a	item = iternext(it);
1516	n/a	if (item == NULL)
1517	n/a	goto empty;
1518	n/a	Py_DECREF(item);
1519	n/a	lz->cnt++;
1520	n/a	}
1521	n/a	if (stop != -1 && lz->cnt >= stop)
1522	n/a	goto empty;
1523	n/a	item = iternext(it);
1524	n/a	if (item == NULL)
1525	n/a	goto empty;
1526	n/a	lz->cnt++;
1527	n/a	oldnext = lz->next;
1528	n/a	/* The (size_t) cast below avoids the danger of undefined
1529	n/a	behaviour from signed integer overflow. */
1530	n/a	lz->next += (size_t)lz->step;
1531	n/a	if (lz->next < oldnext \|\| (stop != -1 && lz->next > stop))
1532	n/a	lz->next = stop;
1533	n/a	return item;
1534	n/a
1535	n/a	empty:
1536	n/a	Py_CLEAR(lz->it);
1537	n/a	return NULL;
1538	n/a	}
1539	n/a
1540	n/a	static PyObject *
1541	n/a	islice_reduce(isliceobject *lz)
1542	n/a	{
1543	n/a	/* When unpickled, generate a new object with the same bounds,
1544	n/a	* then 'setstate' with the next and count
1545	n/a	*/
1546	n/a	PyObject *stop;
1547	n/a
1548	n/a	if (lz->it == NULL) {
1549	n/a	PyObject *empty_list;
1550	n/a	PyObject *empty_it;
1551	n/a	empty_list = PyList_New(0);
1552	n/a	if (empty_list == NULL)
1553	n/a	return NULL;
1554	n/a	empty_it = PyObject_GetIter(empty_list);
1555	n/a	Py_DECREF(empty_list);
1556	n/a	if (empty_it == NULL)
1557	n/a	return NULL;
1558	n/a	return Py_BuildValue("O(Nn)n", Py_TYPE(lz), empty_it, 0, 0);
1559	n/a	}
1560	n/a	if (lz->stop == -1) {
1561	n/a	stop = Py_None;
1562	n/a	Py_INCREF(stop);
1563	n/a	} else {
1564	n/a	stop = PyLong_FromSsize_t(lz->stop);
1565	n/a	if (stop == NULL)
1566	n/a	return NULL;
1567	n/a	}
1568	n/a	return Py_BuildValue("O(OnNn)n", Py_TYPE(lz),
1569	n/a	lz->it, lz->next, stop, lz->step,
1570	n/a	lz->cnt);
1571	n/a	}
1572	n/a
1573	n/a	static PyObject *
1574	n/a	islice_setstate(isliceobject lz, PyObject state)
1575	n/a	{
1576	n/a	Py_ssize_t cnt = PyLong_AsSsize_t(state);
1577	n/a
1578	n/a	if (cnt == -1 && PyErr_Occurred())
1579	n/a	return NULL;
1580	n/a	lz->cnt = cnt;
1581	n/a	Py_RETURN_NONE;
1582	n/a	}
1583	n/a
1584	n/a	static PyMethodDef islice_methods[] = {
1585	n/a	{"__reduce__", (PyCFunction)islice_reduce, METH_NOARGS,
1586	n/a	reduce_doc},
1587	n/a	{"__setstate__", (PyCFunction)islice_setstate, METH_O,
1588	n/a	setstate_doc},
1589	n/a	{NULL, NULL} /* sentinel */
1590	n/a	};
1591	n/a
1592	n/a	PyDoc_STRVAR(islice_doc,
1593	n/a	"islice(iterable, stop) --> islice object\n\
1594	n/a	islice(iterable, start, stop[, step]) --> islice object\n\
1595	n/a	\n\
1596	n/a	Return an iterator whose next() method returns selected values from an\n\
1597	n/a	iterable. If start is specified, will skip all preceding elements;\n\
1598	n/a	otherwise, start defaults to zero. Step defaults to one. If\n\
1599	n/a	specified as another value, step determines how many values are \n\
1600	n/a	skipped between successive calls. Works like a slice() on a list\n\
1601	n/a	but returns an iterator.");
1602	n/a
1603	n/a	static PyTypeObject islice_type = {
1604	n/a	PyVarObject_HEAD_INIT(NULL, 0)
1605	n/a	"itertools.islice", /* tp_name */
1606	n/a	sizeof(isliceobject), /* tp_basicsize */
1607	n/a	0, /* tp_itemsize */
1608	n/a	/* methods */
1609	n/a	(destructor)islice_dealloc, /* tp_dealloc */
1610	n/a	0, /* tp_print */
1611	n/a	0, /* tp_getattr */
1612	n/a	0, /* tp_setattr */
1613	n/a	0, /* tp_reserved */
1614	n/a	0, /* tp_repr */
1615	n/a	0, /* tp_as_number */
1616	n/a	0, /* tp_as_sequence */
1617	n/a	0, /* tp_as_mapping */
1618	n/a	0, /* tp_hash */
1619	n/a	0, /* tp_call */
1620	n/a	0, /* tp_str */
1621	n/a	PyObject_GenericGetAttr, /* tp_getattro */
1622	n/a	0, /* tp_setattro */
1623	n/a	0, /* tp_as_buffer */
1624	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
1625	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
1626	n/a	islice_doc, /* tp_doc */
1627	n/a	(traverseproc)islice_traverse, /* tp_traverse */
1628	n/a	0, /* tp_clear */
1629	n/a	0, /* tp_richcompare */
1630	n/a	0, /* tp_weaklistoffset */
1631	n/a	PyObject_SelfIter, /* tp_iter */
1632	n/a	(iternextfunc)islice_next, /* tp_iternext */
1633	n/a	islice_methods, /* tp_methods */
1634	n/a	0, /* tp_members */
1635	n/a	0, /* tp_getset */
1636	n/a	0, /* tp_base */
1637	n/a	0, /* tp_dict */
1638	n/a	0, /* tp_descr_get */
1639	n/a	0, /* tp_descr_set */
1640	n/a	0, /* tp_dictoffset */
1641	n/a	0, /* tp_init */
1642	n/a	0, /* tp_alloc */
1643	n/a	islice_new, /* tp_new */
1644	n/a	PyObject_GC_Del, /* tp_free */
1645	n/a	};
1646	n/a
1647	n/a
1648	n/a	/* starmap object ************************************************************/
1649	n/a
1650	n/a	typedef struct {
1651	n/a	PyObject_HEAD
1652	n/a	PyObject *func;
1653	n/a	PyObject *it;
1654	n/a	} starmapobject;
1655	n/a
1656	n/a	static PyTypeObject starmap_type;
1657	n/a
1658	n/a	static PyObject *
1659	n/a	starmap_new(PyTypeObject type, PyObject args, PyObject *kwds)
1660	n/a	{
1661	n/a	PyObject func, seq;
1662	n/a	PyObject *it;
1663	n/a	starmapobject *lz;
1664	n/a
1665	n/a	if (type == &starmap_type && !_PyArg_NoKeywords("starmap()", kwds))
1666	n/a	return NULL;
1667	n/a
1668	n/a	if (!PyArg_UnpackTuple(args, "starmap", 2, 2, &func, &seq))
1669	n/a	return NULL;
1670	n/a
1671	n/a	/* Get iterator. */
1672	n/a	it = PyObject_GetIter(seq);
1673	n/a	if (it == NULL)
1674	n/a	return NULL;
1675	n/a
1676	n/a	/* create starmapobject structure */
1677	n/a	lz = (starmapobject *)type->tp_alloc(type, 0);
1678	n/a	if (lz == NULL) {
1679	n/a	Py_DECREF(it);
1680	n/a	return NULL;
1681	n/a	}
1682	n/a	Py_INCREF(func);
1683	n/a	lz->func = func;
1684	n/a	lz->it = it;
1685	n/a
1686	n/a	return (PyObject *)lz;
1687	n/a	}
1688	n/a
1689	n/a	static void
1690	n/a	starmap_dealloc(starmapobject *lz)
1691	n/a	{
1692	n/a	PyObject_GC_UnTrack(lz);
1693	n/a	Py_XDECREF(lz->func);
1694	n/a	Py_XDECREF(lz->it);
1695	n/a	Py_TYPE(lz)->tp_free(lz);
1696	n/a	}
1697	n/a
1698	n/a	static int
1699	n/a	starmap_traverse(starmapobject lz, visitproc visit, void arg)
1700	n/a	{
1701	n/a	Py_VISIT(lz->it);
1702	n/a	Py_VISIT(lz->func);
1703	n/a	return 0;
1704	n/a	}
1705	n/a
1706	n/a	static PyObject *
1707	n/a	starmap_next(starmapobject *lz)
1708	n/a	{
1709	n/a	PyObject *args;
1710	n/a	PyObject *result;
1711	n/a	PyObject *it = lz->it;
1712	n/a
1713	n/a	args = (*Py_TYPE(it)->tp_iternext)(it);
1714	n/a	if (args == NULL)
1715	n/a	return NULL;
1716	n/a	if (!PyTuple_CheckExact(args)) {
1717	n/a	PyObject *newargs = PySequence_Tuple(args);
1718	n/a	Py_DECREF(args);
1719	n/a	if (newargs == NULL)
1720	n/a	return NULL;
1721	n/a	args = newargs;
1722	n/a	}
1723	n/a	result = PyObject_Call(lz->func, args, NULL);
1724	n/a	Py_DECREF(args);
1725	n/a	return result;
1726	n/a	}
1727	n/a
1728	n/a	static PyObject *
1729	n/a	starmap_reduce(starmapobject *lz)
1730	n/a	{
1731	n/a	/* Just pickle the iterator */
1732	n/a	return Py_BuildValue("O(OO)", Py_TYPE(lz), lz->func, lz->it);
1733	n/a	}
1734	n/a
1735	n/a	static PyMethodDef starmap_methods[] = {
1736	n/a	{"__reduce__", (PyCFunction)starmap_reduce, METH_NOARGS,
1737	n/a	reduce_doc},
1738	n/a	{NULL, NULL} /* sentinel */
1739	n/a	};
1740	n/a
1741	n/a	PyDoc_STRVAR(starmap_doc,
1742	n/a	"starmap(function, sequence) --> starmap object\n\
1743	n/a	\n\
1744	n/a	Return an iterator whose values are returned from the function evaluated\n\
1745	n/a	with an argument tuple taken from the given sequence.");
1746	n/a
1747	n/a	static PyTypeObject starmap_type = {
1748	n/a	PyVarObject_HEAD_INIT(NULL, 0)
1749	n/a	"itertools.starmap", /* tp_name */
1750	n/a	sizeof(starmapobject), /* tp_basicsize */
1751	n/a	0, /* tp_itemsize */
1752	n/a	/* methods */
1753	n/a	(destructor)starmap_dealloc, /* tp_dealloc */
1754	n/a	0, /* tp_print */
1755	n/a	0, /* tp_getattr */
1756	n/a	0, /* tp_setattr */
1757	n/a	0, /* tp_reserved */
1758	n/a	0, /* tp_repr */
1759	n/a	0, /* tp_as_number */
1760	n/a	0, /* tp_as_sequence */
1761	n/a	0, /* tp_as_mapping */
1762	n/a	0, /* tp_hash */
1763	n/a	0, /* tp_call */
1764	n/a	0, /* tp_str */
1765	n/a	PyObject_GenericGetAttr, /* tp_getattro */
1766	n/a	0, /* tp_setattro */
1767	n/a	0, /* tp_as_buffer */
1768	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
1769	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
1770	n/a	starmap_doc, /* tp_doc */
1771	n/a	(traverseproc)starmap_traverse, /* tp_traverse */
1772	n/a	0, /* tp_clear */
1773	n/a	0, /* tp_richcompare */
1774	n/a	0, /* tp_weaklistoffset */
1775	n/a	PyObject_SelfIter, /* tp_iter */
1776	n/a	(iternextfunc)starmap_next, /* tp_iternext */
1777	n/a	starmap_methods, /* tp_methods */
1778	n/a	0, /* tp_members */
1779	n/a	0, /* tp_getset */
1780	n/a	0, /* tp_base */
1781	n/a	0, /* tp_dict */
1782	n/a	0, /* tp_descr_get */
1783	n/a	0, /* tp_descr_set */
1784	n/a	0, /* tp_dictoffset */
1785	n/a	0, /* tp_init */
1786	n/a	0, /* tp_alloc */
1787	n/a	starmap_new, /* tp_new */
1788	n/a	PyObject_GC_Del, /* tp_free */
1789	n/a	};
1790	n/a
1791	n/a
1792	n/a	/* chain object **************************************************************/
1793	n/a
1794	n/a	typedef struct {
1795	n/a	PyObject_HEAD
1796	n/a	PyObject source; / Iterator over input iterables */
1797	n/a	PyObject active; / Currently running input iterator */
1798	n/a	} chainobject;
1799	n/a
1800	n/a	static PyTypeObject chain_type;
1801	n/a
1802	n/a	static PyObject *
1803	n/a	chain_new_internal(PyTypeObject type, PyObject source)
1804	n/a	{
1805	n/a	chainobject *lz;
1806	n/a
1807	n/a	lz = (chainobject *)type->tp_alloc(type, 0);
1808	n/a	if (lz == NULL) {
1809	n/a	Py_DECREF(source);
1810	n/a	return NULL;
1811	n/a	}
1812	n/a
1813	n/a	lz->source = source;
1814	n/a	lz->active = NULL;
1815	n/a	return (PyObject *)lz;
1816	n/a	}
1817	n/a
1818	n/a	static PyObject *
1819	n/a	chain_new(PyTypeObject type, PyObject args, PyObject *kwds)
1820	n/a	{
1821	n/a	PyObject *source;
1822	n/a
1823	n/a	if (type == &chain_type && !_PyArg_NoKeywords("chain()", kwds))
1824	n/a	return NULL;
1825	n/a
1826	n/a	source = PyObject_GetIter(args);
1827	n/a	if (source == NULL)
1828	n/a	return NULL;
1829	n/a
1830	n/a	return chain_new_internal(type, source);
1831	n/a	}
1832	n/a
1833	n/a	static PyObject *
1834	n/a	chain_new_from_iterable(PyTypeObject type, PyObject arg)
1835	n/a	{
1836	n/a	PyObject *source;
1837	n/a
1838	n/a	source = PyObject_GetIter(arg);
1839	n/a	if (source == NULL)
1840	n/a	return NULL;
1841	n/a
1842	n/a	return chain_new_internal(type, source);
1843	n/a	}
1844	n/a
1845	n/a	static void
1846	n/a	chain_dealloc(chainobject *lz)
1847	n/a	{
1848	n/a	PyObject_GC_UnTrack(lz);
1849	n/a	Py_XDECREF(lz->active);
1850	n/a	Py_XDECREF(lz->source);
1851	n/a	Py_TYPE(lz)->tp_free(lz);
1852	n/a	}
1853	n/a
1854	n/a	static int
1855	n/a	chain_traverse(chainobject lz, visitproc visit, void arg)
1856	n/a	{
1857	n/a	Py_VISIT(lz->source);
1858	n/a	Py_VISIT(lz->active);
1859	n/a	return 0;
1860	n/a	}
1861	n/a
1862	n/a	static PyObject *
1863	n/a	chain_next(chainobject *lz)
1864	n/a	{
1865	n/a	PyObject *item;
1866	n/a
1867	n/a	if (lz->source == NULL)
1868	n/a	return NULL; /* already stopped */
1869	n/a
1870	n/a	if (lz->active == NULL) {
1871	n/a	PyObject *iterable = PyIter_Next(lz->source);
1872	n/a	if (iterable == NULL) {
1873	n/a	Py_CLEAR(lz->source);
1874	n/a	return NULL; /* no more input sources */
1875	n/a	}
1876	n/a	lz->active = PyObject_GetIter(iterable);
1877	n/a	Py_DECREF(iterable);
1878	n/a	if (lz->active == NULL) {
1879	n/a	Py_CLEAR(lz->source);
1880	n/a	return NULL; /* input not iterable */
1881	n/a	}
1882	n/a	}
1883	n/a	item = (*Py_TYPE(lz->active)->tp_iternext)(lz->active);
1884	n/a	if (item != NULL)
1885	n/a	return item;
1886	n/a	if (PyErr_Occurred()) {
1887	n/a	if (PyErr_ExceptionMatches(PyExc_StopIteration))
1888	n/a	PyErr_Clear();
1889	n/a	else
1890	n/a	return NULL; /* input raised an exception */
1891	n/a	}
1892	n/a	Py_CLEAR(lz->active);
1893	n/a	return chain_next(lz); /* recurse and use next active */
1894	n/a	}
1895	n/a
1896	n/a	static PyObject *
1897	n/a	chain_reduce(chainobject *lz)
1898	n/a	{
1899	n/a	if (lz->source) {
1900	n/a	/* we can't pickle function objects (itertools.from_iterable) so
1901	n/a	* we must use setstate to replace the iterable. One day we
1902	n/a	* will fix pickling of functions
1903	n/a	*/
1904	n/a	if (lz->active) {
1905	n/a	return Py_BuildValue("O()(OO)", Py_TYPE(lz), lz->source, lz->active);
1906	n/a	} else {
1907	n/a	return Py_BuildValue("O()(O)", Py_TYPE(lz), lz->source);
1908	n/a	}
1909	n/a	} else {
1910	n/a	return Py_BuildValue("O()", Py_TYPE(lz)); /* exhausted */
1911	n/a	}
1912	n/a	return NULL;
1913	n/a	}
1914	n/a
1915	n/a	static PyObject *
1916	n/a	chain_setstate(chainobject lz, PyObject state)
1917	n/a	{
1918	n/a	PyObject source, active=NULL;
1919	n/a
1920	n/a	if (!PyTuple_Check(state)) {
1921	n/a	PyErr_SetString(PyExc_TypeError, "state is not a tuple");
1922	n/a	return NULL;
1923	n/a	}
1924	n/a	if (!PyArg_ParseTuple(state, "O\|O", &source, &active)) {
1925	n/a	return NULL;
1926	n/a	}
1927	n/a	if (!PyIter_Check(source) \|\| (active != NULL && !PyIter_Check(active))) {
1928	n/a	PyErr_SetString(PyExc_TypeError, "Arguments must be iterators.");
1929	n/a	return NULL;
1930	n/a	}
1931	n/a
1932	n/a	Py_INCREF(source);
1933	n/a	Py_XSETREF(lz->source, source);
1934	n/a	Py_XINCREF(active);
1935	n/a	Py_XSETREF(lz->active, active);
1936	n/a	Py_RETURN_NONE;
1937	n/a	}
1938	n/a
1939	n/a	PyDoc_STRVAR(chain_doc,
1940	n/a	"chain(*iterables) --> chain object\n\
1941	n/a	\n\
1942	n/a	Return a chain object whose .__next__() method returns elements from the\n\
1943	n/a	first iterable until it is exhausted, then elements from the next\n\
1944	n/a	iterable, until all of the iterables are exhausted.");
1945	n/a
1946	n/a	PyDoc_STRVAR(chain_from_iterable_doc,
1947	n/a	"chain.from_iterable(iterable) --> chain object\n\
1948	n/a	\n\
1949	n/a	Alternate chain() constructor taking a single iterable argument\n\
1950	n/a	that evaluates lazily.");
1951	n/a
1952	n/a	static PyMethodDef chain_methods[] = {
1953	n/a	{"from_iterable", (PyCFunction) chain_new_from_iterable, METH_O \| METH_CLASS,
1954	n/a	chain_from_iterable_doc},
1955	n/a	{"__reduce__", (PyCFunction)chain_reduce, METH_NOARGS,
1956	n/a	reduce_doc},
1957	n/a	{"__setstate__", (PyCFunction)chain_setstate, METH_O,
1958	n/a	setstate_doc},
1959	n/a	{NULL, NULL} /* sentinel */
1960	n/a	};
1961	n/a
1962	n/a	static PyTypeObject chain_type = {
1963	n/a	PyVarObject_HEAD_INIT(NULL, 0)
1964	n/a	"itertools.chain", /* tp_name */
1965	n/a	sizeof(chainobject), /* tp_basicsize */
1966	n/a	0, /* tp_itemsize */
1967	n/a	/* methods */
1968	n/a	(destructor)chain_dealloc, /* tp_dealloc */
1969	n/a	0, /* tp_print */
1970	n/a	0, /* tp_getattr */
1971	n/a	0, /* tp_setattr */
1972	n/a	0, /* tp_reserved */
1973	n/a	0, /* tp_repr */
1974	n/a	0, /* tp_as_number */
1975	n/a	0, /* tp_as_sequence */
1976	n/a	0, /* tp_as_mapping */
1977	n/a	0, /* tp_hash */
1978	n/a	0, /* tp_call */
1979	n/a	0, /* tp_str */
1980	n/a	PyObject_GenericGetAttr, /* tp_getattro */
1981	n/a	0, /* tp_setattro */
1982	n/a	0, /* tp_as_buffer */
1983	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
1984	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
1985	n/a	chain_doc, /* tp_doc */
1986	n/a	(traverseproc)chain_traverse, /* tp_traverse */
1987	n/a	0, /* tp_clear */
1988	n/a	0, /* tp_richcompare */
1989	n/a	0, /* tp_weaklistoffset */
1990	n/a	PyObject_SelfIter, /* tp_iter */
1991	n/a	(iternextfunc)chain_next, /* tp_iternext */
1992	n/a	chain_methods, /* tp_methods */
1993	n/a	0, /* tp_members */
1994	n/a	0, /* tp_getset */
1995	n/a	0, /* tp_base */
1996	n/a	0, /* tp_dict */
1997	n/a	0, /* tp_descr_get */
1998	n/a	0, /* tp_descr_set */
1999	n/a	0, /* tp_dictoffset */
2000	n/a	0, /* tp_init */
2001	n/a	0, /* tp_alloc */
2002	n/a	chain_new, /* tp_new */
2003	n/a	PyObject_GC_Del, /* tp_free */
2004	n/a	};
2005	n/a
2006	n/a
2007	n/a	/* product object ************************************************************/
2008	n/a
2009	n/a	typedef struct {
2010	n/a	PyObject_HEAD
2011	n/a	PyObject pools; / tuple of pool tuples */
2012	n/a	Py_ssize_t indices; / one index per pool */
2013	n/a	PyObject result; / most recently returned result tuple */
2014	n/a	int stopped; /* set to 1 when the iterator is exhausted */
2015	n/a	} productobject;
2016	n/a
2017	n/a	static PyTypeObject product_type;
2018	n/a
2019	n/a	static PyObject *
2020	n/a	product_new(PyTypeObject type, PyObject args, PyObject *kwds)
2021	n/a	{
2022	n/a	productobject *lz;
2023	n/a	Py_ssize_t nargs, npools, repeat=1;
2024	n/a	PyObject *pools = NULL;
2025	n/a	Py_ssize_t *indices = NULL;
2026	n/a	Py_ssize_t i;
2027	n/a
2028	n/a	if (kwds != NULL) {
2029	n/a	char *kwlist[] = {"repeat", 0};
2030	n/a	PyObject *tmpargs = PyTuple_New(0);
2031	n/a	if (tmpargs == NULL)
2032	n/a	return NULL;
2033	n/a	if (!PyArg_ParseTupleAndKeywords(tmpargs, kwds, "\|n:product",
2034	n/a	kwlist, &repeat)) {
2035	n/a	Py_DECREF(tmpargs);
2036	n/a	return NULL;
2037	n/a	}
2038	n/a	Py_DECREF(tmpargs);
2039	n/a	if (repeat < 0) {
2040	n/a	PyErr_SetString(PyExc_ValueError,
2041	n/a	"repeat argument cannot be negative");
2042	n/a	return NULL;
2043	n/a	}
2044	n/a	}
2045	n/a
2046	n/a	assert(PyTuple_CheckExact(args));
2047	n/a	if (repeat == 0) {
2048	n/a	nargs = 0;
2049	n/a	} else {
2050	n/a	nargs = PyTuple_GET_SIZE(args);
2051	n/a	if ((size_t)nargs > PY_SSIZE_T_MAX/sizeof(Py_ssize_t)/repeat) {
2052	n/a	PyErr_SetString(PyExc_OverflowError, "repeat argument too large");
2053	n/a	return NULL;
2054	n/a	}
2055	n/a	}
2056	n/a	npools = nargs * repeat;
2057	n/a
2058	n/a	indices = PyMem_New(Py_ssize_t, npools);
2059	n/a	if (indices == NULL) {
2060	n/a	PyErr_NoMemory();
2061	n/a	goto error;
2062	n/a	}
2063	n/a
2064	n/a	pools = PyTuple_New(npools);
2065	n/a	if (pools == NULL)
2066	n/a	goto error;
2067	n/a
2068	n/a	for (i=0; i < nargs ; ++i) {
2069	n/a	PyObject *item = PyTuple_GET_ITEM(args, i);
2070	n/a	PyObject *pool = PySequence_Tuple(item);
2071	n/a	if (pool == NULL)
2072	n/a	goto error;
2073	n/a	PyTuple_SET_ITEM(pools, i, pool);
2074	n/a	indices[i] = 0;
2075	n/a	}
2076	n/a	for ( ; i < npools; ++i) {
2077	n/a	PyObject *pool = PyTuple_GET_ITEM(pools, i - nargs);
2078	n/a	Py_INCREF(pool);
2079	n/a	PyTuple_SET_ITEM(pools, i, pool);
2080	n/a	indices[i] = 0;
2081	n/a	}
2082	n/a
2083	n/a	/* create productobject structure */
2084	n/a	lz = (productobject *)type->tp_alloc(type, 0);
2085	n/a	if (lz == NULL)
2086	n/a	goto error;
2087	n/a
2088	n/a	lz->pools = pools;
2089	n/a	lz->indices = indices;
2090	n/a	lz->result = NULL;
2091	n/a	lz->stopped = 0;
2092	n/a
2093	n/a	return (PyObject *)lz;
2094	n/a
2095	n/a	error:
2096	n/a	if (indices != NULL)
2097	n/a	PyMem_Free(indices);
2098	n/a	Py_XDECREF(pools);
2099	n/a	return NULL;
2100	n/a	}
2101	n/a
2102	n/a	static void
2103	n/a	product_dealloc(productobject *lz)
2104	n/a	{
2105	n/a	PyObject_GC_UnTrack(lz);
2106	n/a	Py_XDECREF(lz->pools);
2107	n/a	Py_XDECREF(lz->result);
2108	n/a	if (lz->indices != NULL)
2109	n/a	PyMem_Free(lz->indices);
2110	n/a	Py_TYPE(lz)->tp_free(lz);
2111	n/a	}
2112	n/a
2113	n/a	static PyObject *
2114	n/a	product_sizeof(productobject lz, void unused)
2115	n/a	{
2116	n/a	Py_ssize_t res;
2117	n/a
2118	n/a	res = _PyObject_SIZE(Py_TYPE(lz));
2119	n/a	res += PyTuple_GET_SIZE(lz->pools) * sizeof(Py_ssize_t);
2120	n/a	return PyLong_FromSsize_t(res);
2121	n/a	}
2122	n/a
2123	n/a	PyDoc_STRVAR(sizeof_doc, "Returns size in memory, in bytes.");
2124	n/a
2125	n/a	static int
2126	n/a	product_traverse(productobject lz, visitproc visit, void arg)
2127	n/a	{
2128	n/a	Py_VISIT(lz->pools);
2129	n/a	Py_VISIT(lz->result);
2130	n/a	return 0;
2131	n/a	}
2132	n/a
2133	n/a	static PyObject *
2134	n/a	product_next(productobject *lz)
2135	n/a	{
2136	n/a	PyObject *pool;
2137	n/a	PyObject *elem;
2138	n/a	PyObject *oldelem;
2139	n/a	PyObject *pools = lz->pools;
2140	n/a	PyObject *result = lz->result;
2141	n/a	Py_ssize_t npools = PyTuple_GET_SIZE(pools);
2142	n/a	Py_ssize_t i;
2143	n/a
2144	n/a	if (lz->stopped)
2145	n/a	return NULL;
2146	n/a
2147	n/a	if (result == NULL) {
2148	n/a	/* On the first pass, return an initial tuple filled with the
2149	n/a	first element from each pool. */
2150	n/a	result = PyTuple_New(npools);
2151	n/a	if (result == NULL)
2152	n/a	goto empty;
2153	n/a	lz->result = result;
2154	n/a	for (i=0; i < npools; i++) {
2155	n/a	pool = PyTuple_GET_ITEM(pools, i);
2156	n/a	if (PyTuple_GET_SIZE(pool) == 0)
2157	n/a	goto empty;
2158	n/a	elem = PyTuple_GET_ITEM(pool, 0);
2159	n/a	Py_INCREF(elem);
2160	n/a	PyTuple_SET_ITEM(result, i, elem);
2161	n/a	}
2162	n/a	} else {
2163	n/a	Py_ssize_t *indices = lz->indices;
2164	n/a
2165	n/a	/* Copy the previous result tuple or re-use it if available */
2166	n/a	if (Py_REFCNT(result) > 1) {
2167	n/a	PyObject *old_result = result;
2168	n/a	result = PyTuple_New(npools);
2169	n/a	if (result == NULL)
2170	n/a	goto empty;
2171	n/a	lz->result = result;
2172	n/a	for (i=0; i < npools; i++) {
2173	n/a	elem = PyTuple_GET_ITEM(old_result, i);
2174	n/a	Py_INCREF(elem);
2175	n/a	PyTuple_SET_ITEM(result, i, elem);
2176	n/a	}
2177	n/a	Py_DECREF(old_result);
2178	n/a	}
2179	n/a	/* Now, we've got the only copy so we can update it in-place */
2180	n/a	assert (npools==0 \|\| Py_REFCNT(result) == 1);
2181	n/a
2182	n/a	/* Update the pool indices right-to-left. Only advance to the
2183	n/a	next pool when the previous one rolls-over */
2184	n/a	for (i=npools-1 ; i >= 0 ; i--) {
2185	n/a	pool = PyTuple_GET_ITEM(pools, i);
2186	n/a	indices[i]++;
2187	n/a	if (indices[i] == PyTuple_GET_SIZE(pool)) {
2188	n/a	/* Roll-over and advance to next pool */
2189	n/a	indices[i] = 0;
2190	n/a	elem = PyTuple_GET_ITEM(pool, 0);
2191	n/a	Py_INCREF(elem);
2192	n/a	oldelem = PyTuple_GET_ITEM(result, i);
2193	n/a	PyTuple_SET_ITEM(result, i, elem);
2194	n/a	Py_DECREF(oldelem);
2195	n/a	} else {
2196	n/a	/* No rollover. Just increment and stop here. */
2197	n/a	elem = PyTuple_GET_ITEM(pool, indices[i]);
2198	n/a	Py_INCREF(elem);
2199	n/a	oldelem = PyTuple_GET_ITEM(result, i);
2200	n/a	PyTuple_SET_ITEM(result, i, elem);
2201	n/a	Py_DECREF(oldelem);
2202	n/a	break;
2203	n/a	}
2204	n/a	}
2205	n/a
2206	n/a	/* If i is negative, then the indices have all rolled-over
2207	n/a	and we're done. */
2208	n/a	if (i < 0)
2209	n/a	goto empty;
2210	n/a	}
2211	n/a
2212	n/a	Py_INCREF(result);
2213	n/a	return result;
2214	n/a
2215	n/a	empty:
2216	n/a	lz->stopped = 1;
2217	n/a	return NULL;
2218	n/a	}
2219	n/a
2220	n/a	static PyObject *
2221	n/a	product_reduce(productobject *lz)
2222	n/a	{
2223	n/a	if (lz->stopped) {
2224	n/a	return Py_BuildValue("O(())", Py_TYPE(lz));
2225	n/a	} else if (lz->result == NULL) {
2226	n/a	return Py_BuildValue("OO", Py_TYPE(lz), lz->pools);
2227	n/a	} else {
2228	n/a	PyObject *indices;
2229	n/a	Py_ssize_t n, i;
2230	n/a
2231	n/a	/* we must pickle the indices use them for setstate, and
2232	n/a	* additionally indicate that the iterator has started
2233	n/a	*/
2234	n/a	n = PyTuple_GET_SIZE(lz->pools);
2235	n/a	indices = PyTuple_New(n);
2236	n/a	if (indices == NULL)
2237	n/a	return NULL;
2238	n/a	for (i=0; i<n; i++){
2239	n/a	PyObject* index = PyLong_FromSsize_t(lz->indices[i]);
2240	n/a	if (!index) {
2241	n/a	Py_DECREF(indices);
2242	n/a	return NULL;
2243	n/a	}
2244	n/a	PyTuple_SET_ITEM(indices, i, index);
2245	n/a	}
2246	n/a	return Py_BuildValue("OON", Py_TYPE(lz), lz->pools, indices);
2247	n/a	}
2248	n/a	}
2249	n/a
2250	n/a	static PyObject *
2251	n/a	product_setstate(productobject lz, PyObject state)
2252	n/a	{
2253	n/a	PyObject *result;
2254	n/a	Py_ssize_t n, i;
2255	n/a
2256	n/a	n = PyTuple_GET_SIZE(lz->pools);
2257	n/a	if (!PyTuple_Check(state) \|\| PyTuple_GET_SIZE(state) != n) {
2258	n/a	PyErr_SetString(PyExc_ValueError, "invalid arguments");
2259	n/a	return NULL;
2260	n/a	}
2261	n/a	for (i=0; i<n; i++)
2262	n/a	{
2263	n/a	PyObject* indexObject = PyTuple_GET_ITEM(state, i);
2264	n/a	Py_ssize_t index = PyLong_AsSsize_t(indexObject);
2265	n/a	PyObject* pool;
2266	n/a	Py_ssize_t poolsize;
2267	n/a	if (index < 0 && PyErr_Occurred())
2268	n/a	return NULL; /* not an integer */
2269	n/a	pool = PyTuple_GET_ITEM(lz->pools, i);
2270	n/a	poolsize = PyTuple_GET_SIZE(pool);
2271	n/a	if (poolsize == 0) {
2272	n/a	lz->stopped = 1;
2273	n/a	Py_RETURN_NONE;
2274	n/a	}
2275	n/a	/* clamp the index */
2276	n/a	if (index < 0)
2277	n/a	index = 0;
2278	n/a	else if (index > poolsize-1)
2279	n/a	index = poolsize-1;
2280	n/a	lz->indices[i] = index;
2281	n/a	}
2282	n/a
2283	n/a	result = PyTuple_New(n);
2284	n/a	if (!result)
2285	n/a	return NULL;
2286	n/a	for (i=0; i<n; i++) {
2287	n/a	PyObject *pool = PyTuple_GET_ITEM(lz->pools, i);
2288	n/a	PyObject *element = PyTuple_GET_ITEM(pool, lz->indices[i]);
2289	n/a	Py_INCREF(element);
2290	n/a	PyTuple_SET_ITEM(result, i, element);
2291	n/a	}
2292	n/a	Py_XSETREF(lz->result, result);
2293	n/a	Py_RETURN_NONE;
2294	n/a	}
2295	n/a
2296	n/a	static PyMethodDef product_methods[] = {
2297	n/a	{"__reduce__", (PyCFunction)product_reduce, METH_NOARGS,
2298	n/a	reduce_doc},
2299	n/a	{"__setstate__", (PyCFunction)product_setstate, METH_O,
2300	n/a	setstate_doc},
2301	n/a	{"__sizeof__", (PyCFunction)product_sizeof, METH_NOARGS,
2302	n/a	sizeof_doc},
2303	n/a	{NULL, NULL} /* sentinel */
2304	n/a	};
2305	n/a
2306	n/a	PyDoc_STRVAR(product_doc,
2307	n/a	"product(*iterables, repeat=1) --> product object\n\
2308	n/a	\n\
2309	n/a	Cartesian product of input iterables. Equivalent to nested for-loops.\n\n\
2310	n/a	For example, product(A, B) returns the same as: ((x,y) for x in A for y in B).\n\
2311	n/a	The leftmost iterators are in the outermost for-loop, so the output tuples\n\
2312	n/a	cycle in a manner similar to an odometer (with the rightmost element changing\n\
2313	n/a	on every iteration).\n\n\
2314	n/a	To compute the product of an iterable with itself, specify the number\n\
2315	n/a	of repetitions with the optional repeat keyword argument. For example,\n\
2316	n/a	product(A, repeat=4) means the same as product(A, A, A, A).\n\n\
2317	n/a	product('ab', range(3)) --> ('a',0) ('a',1) ('a',2) ('b',0) ('b',1) ('b',2)\n\
2318	n/a	product((0,1), (0,1), (0,1)) --> (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) ...");
2319	n/a
2320	n/a	static PyTypeObject product_type = {
2321	n/a	PyVarObject_HEAD_INIT(NULL, 0)
2322	n/a	"itertools.product", /* tp_name */
2323	n/a	sizeof(productobject), /* tp_basicsize */
2324	n/a	0, /* tp_itemsize */
2325	n/a	/* methods */
2326	n/a	(destructor)product_dealloc, /* tp_dealloc */
2327	n/a	0, /* tp_print */
2328	n/a	0, /* tp_getattr */
2329	n/a	0, /* tp_setattr */
2330	n/a	0, /* tp_reserved */
2331	n/a	0, /* tp_repr */
2332	n/a	0, /* tp_as_number */
2333	n/a	0, /* tp_as_sequence */
2334	n/a	0, /* tp_as_mapping */
2335	n/a	0, /* tp_hash */
2336	n/a	0, /* tp_call */
2337	n/a	0, /* tp_str */
2338	n/a	PyObject_GenericGetAttr, /* tp_getattro */
2339	n/a	0, /* tp_setattro */
2340	n/a	0, /* tp_as_buffer */
2341	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
2342	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
2343	n/a	product_doc, /* tp_doc */
2344	n/a	(traverseproc)product_traverse, /* tp_traverse */
2345	n/a	0, /* tp_clear */
2346	n/a	0, /* tp_richcompare */
2347	n/a	0, /* tp_weaklistoffset */
2348	n/a	PyObject_SelfIter, /* tp_iter */
2349	n/a	(iternextfunc)product_next, /* tp_iternext */
2350	n/a	product_methods, /* tp_methods */
2351	n/a	0, /* tp_members */
2352	n/a	0, /* tp_getset */
2353	n/a	0, /* tp_base */
2354	n/a	0, /* tp_dict */
2355	n/a	0, /* tp_descr_get */
2356	n/a	0, /* tp_descr_set */
2357	n/a	0, /* tp_dictoffset */
2358	n/a	0, /* tp_init */
2359	n/a	0, /* tp_alloc */
2360	n/a	product_new, /* tp_new */
2361	n/a	PyObject_GC_Del, /* tp_free */
2362	n/a	};
2363	n/a
2364	n/a
2365	n/a	/* combinations object *******************************************************/
2366	n/a
2367	n/a	typedef struct {
2368	n/a	PyObject_HEAD
2369	n/a	PyObject pool; / input converted to a tuple */
2370	n/a	Py_ssize_t indices; / one index per result element */
2371	n/a	PyObject result; / most recently returned result tuple */
2372	n/a	Py_ssize_t r; /* size of result tuple */
2373	n/a	int stopped; /* set to 1 when the iterator is exhausted */
2374	n/a	} combinationsobject;
2375	n/a
2376	n/a	static PyTypeObject combinations_type;
2377	n/a
2378	n/a	static PyObject *
2379	n/a	combinations_new(PyTypeObject type, PyObject args, PyObject *kwds)
2380	n/a	{
2381	n/a	combinationsobject *co;
2382	n/a	Py_ssize_t n;
2383	n/a	Py_ssize_t r;
2384	n/a	PyObject *pool = NULL;
2385	n/a	PyObject *iterable = NULL;
2386	n/a	Py_ssize_t *indices = NULL;
2387	n/a	Py_ssize_t i;
2388	n/a	static char *kwargs[] = {"iterable", "r", NULL};
2389	n/a
2390	n/a	if (!PyArg_ParseTupleAndKeywords(args, kwds, "On:combinations", kwargs,
2391	n/a	&iterable, &r))
2392	n/a	return NULL;
2393	n/a
2394	n/a	pool = PySequence_Tuple(iterable);
2395	n/a	if (pool == NULL)
2396	n/a	goto error;
2397	n/a	n = PyTuple_GET_SIZE(pool);
2398	n/a	if (r < 0) {
2399	n/a	PyErr_SetString(PyExc_ValueError, "r must be non-negative");
2400	n/a	goto error;
2401	n/a	}
2402	n/a
2403	n/a	indices = PyMem_New(Py_ssize_t, r);
2404	n/a	if (indices == NULL) {
2405	n/a	PyErr_NoMemory();
2406	n/a	goto error;
2407	n/a	}
2408	n/a
2409	n/a	for (i=0 ; i<r ; i++)
2410	n/a	indices[i] = i;
2411	n/a
2412	n/a	/* create combinationsobject structure */
2413	n/a	co = (combinationsobject *)type->tp_alloc(type, 0);
2414	n/a	if (co == NULL)
2415	n/a	goto error;
2416	n/a
2417	n/a	co->pool = pool;
2418	n/a	co->indices = indices;
2419	n/a	co->result = NULL;
2420	n/a	co->r = r;
2421	n/a	co->stopped = r > n ? 1 : 0;
2422	n/a
2423	n/a	return (PyObject *)co;
2424	n/a
2425	n/a	error:
2426	n/a	if (indices != NULL)
2427	n/a	PyMem_Free(indices);
2428	n/a	Py_XDECREF(pool);
2429	n/a	return NULL;
2430	n/a	}
2431	n/a
2432	n/a	static void
2433	n/a	combinations_dealloc(combinationsobject *co)
2434	n/a	{
2435	n/a	PyObject_GC_UnTrack(co);
2436	n/a	Py_XDECREF(co->pool);
2437	n/a	Py_XDECREF(co->result);
2438	n/a	if (co->indices != NULL)
2439	n/a	PyMem_Free(co->indices);
2440	n/a	Py_TYPE(co)->tp_free(co);
2441	n/a	}
2442	n/a
2443	n/a	static PyObject *
2444	n/a	combinations_sizeof(combinationsobject co, void unused)
2445	n/a	{
2446	n/a	Py_ssize_t res;
2447	n/a
2448	n/a	res = _PyObject_SIZE(Py_TYPE(co));
2449	n/a	res += co->r * sizeof(Py_ssize_t);
2450	n/a	return PyLong_FromSsize_t(res);
2451	n/a	}
2452	n/a
2453	n/a	static int
2454	n/a	combinations_traverse(combinationsobject co, visitproc visit, void arg)
2455	n/a	{
2456	n/a	Py_VISIT(co->pool);
2457	n/a	Py_VISIT(co->result);
2458	n/a	return 0;
2459	n/a	}
2460	n/a
2461	n/a	static PyObject *
2462	n/a	combinations_next(combinationsobject *co)
2463	n/a	{
2464	n/a	PyObject *elem;
2465	n/a	PyObject *oldelem;
2466	n/a	PyObject *pool = co->pool;
2467	n/a	Py_ssize_t *indices = co->indices;
2468	n/a	PyObject *result = co->result;
2469	n/a	Py_ssize_t n = PyTuple_GET_SIZE(pool);
2470	n/a	Py_ssize_t r = co->r;
2471	n/a	Py_ssize_t i, j, index;
2472	n/a
2473	n/a	if (co->stopped)
2474	n/a	return NULL;
2475	n/a
2476	n/a	if (result == NULL) {
2477	n/a	/* On the first pass, initialize result tuple using the indices */
2478	n/a	result = PyTuple_New(r);
2479	n/a	if (result == NULL)
2480	n/a	goto empty;
2481	n/a	co->result = result;
2482	n/a	for (i=0; i<r ; i++) {
2483	n/a	index = indices[i];
2484	n/a	elem = PyTuple_GET_ITEM(pool, index);
2485	n/a	Py_INCREF(elem);
2486	n/a	PyTuple_SET_ITEM(result, i, elem);
2487	n/a	}
2488	n/a	} else {
2489	n/a	/* Copy the previous result tuple or re-use it if available */
2490	n/a	if (Py_REFCNT(result) > 1) {
2491	n/a	PyObject *old_result = result;
2492	n/a	result = PyTuple_New(r);
2493	n/a	if (result == NULL)
2494	n/a	goto empty;
2495	n/a	co->result = result;
2496	n/a	for (i=0; i<r ; i++) {
2497	n/a	elem = PyTuple_GET_ITEM(old_result, i);
2498	n/a	Py_INCREF(elem);
2499	n/a	PyTuple_SET_ITEM(result, i, elem);
2500	n/a	}
2501	n/a	Py_DECREF(old_result);
2502	n/a	}
2503	n/a	/* Now, we've got the only copy so we can update it in-place
2504	n/a	* CPython's empty tuple is a singleton and cached in
2505	n/a	* PyTuple's freelist.
2506	n/a	*/
2507	n/a	assert(r == 0 \|\| Py_REFCNT(result) == 1);
2508	n/a
2509	n/a	/* Scan indices right-to-left until finding one that is not
2510	n/a	at its maximum (i + n - r). */
2511	n/a	for (i=r-1 ; i >= 0 && indices[i] == i+n-r ; i--)
2512	n/a	;
2513	n/a
2514	n/a	/* If i is negative, then the indices are all at
2515	n/a	their maximum value and we're done. */
2516	n/a	if (i < 0)
2517	n/a	goto empty;
2518	n/a
2519	n/a	/* Increment the current index which we know is not at its
2520	n/a	maximum. Then move back to the right setting each index
2521	n/a	to its lowest possible value (one higher than the index
2522	n/a	to its left -- this maintains the sort order invariant). */
2523	n/a	indices[i]++;
2524	n/a	for (j=i+1 ; j<r ; j++)
2525	n/a	indices[j] = indices[j-1] + 1;
2526	n/a
2527	n/a	/* Update the result tuple for the new indices
2528	n/a	starting with i, the leftmost index that changed */
2529	n/a	for ( ; i<r ; i++) {
2530	n/a	index = indices[i];
2531	n/a	elem = PyTuple_GET_ITEM(pool, index);
2532	n/a	Py_INCREF(elem);
2533	n/a	oldelem = PyTuple_GET_ITEM(result, i);
2534	n/a	PyTuple_SET_ITEM(result, i, elem);
2535	n/a	Py_DECREF(oldelem);
2536	n/a	}
2537	n/a	}
2538	n/a
2539	n/a	Py_INCREF(result);
2540	n/a	return result;
2541	n/a
2542	n/a	empty:
2543	n/a	co->stopped = 1;
2544	n/a	return NULL;
2545	n/a	}
2546	n/a
2547	n/a	static PyObject *
2548	n/a	combinations_reduce(combinationsobject *lz)
2549	n/a	{
2550	n/a	if (lz->result == NULL) {
2551	n/a	return Py_BuildValue("O(On)", Py_TYPE(lz), lz->pool, lz->r);
2552	n/a	} else if (lz->stopped) {
2553	n/a	return Py_BuildValue("O(()n)", Py_TYPE(lz), lz->r);
2554	n/a	} else {
2555	n/a	PyObject *indices;
2556	n/a	Py_ssize_t i;
2557	n/a
2558	n/a	/* we must pickle the indices and use them for setstate */
2559	n/a	indices = PyTuple_New(lz->r);
2560	n/a	if (!indices)
2561	n/a	return NULL;
2562	n/a	for (i=0; i<lz->r; i++)
2563	n/a	{
2564	n/a	PyObject* index = PyLong_FromSsize_t(lz->indices[i]);
2565	n/a	if (!index) {
2566	n/a	Py_DECREF(indices);
2567	n/a	return NULL;
2568	n/a	}
2569	n/a	PyTuple_SET_ITEM(indices, i, index);
2570	n/a	}
2571	n/a
2572	n/a	return Py_BuildValue("O(On)N", Py_TYPE(lz), lz->pool, lz->r, indices);
2573	n/a	}
2574	n/a	}
2575	n/a
2576	n/a	static PyObject *
2577	n/a	combinations_setstate(combinationsobject lz, PyObject state)
2578	n/a	{
2579	n/a	PyObject *result;
2580	n/a	Py_ssize_t i;
2581	n/a	Py_ssize_t n = PyTuple_GET_SIZE(lz->pool);
2582	n/a
2583	n/a	if (!PyTuple_Check(state) \|\| PyTuple_GET_SIZE(state) != lz->r) {
2584	n/a	PyErr_SetString(PyExc_ValueError, "invalid arguments");
2585	n/a	return NULL;
2586	n/a	}
2587	n/a
2588	n/a	for (i=0; i<lz->r; i++) {
2589	n/a	Py_ssize_t max;
2590	n/a	PyObject* indexObject = PyTuple_GET_ITEM(state, i);
2591	n/a	Py_ssize_t index = PyLong_AsSsize_t(indexObject);
2592	n/a
2593	n/a	if (index == -1 && PyErr_Occurred())
2594	n/a	return NULL; /* not an integer */
2595	n/a	max = i + n - lz->r;
2596	n/a	/* clamp the index (beware of negative max) */
2597	n/a	if (index > max)
2598	n/a	index = max;
2599	n/a	if (index < 0)
2600	n/a	index = 0;
2601	n/a	lz->indices[i] = index;
2602	n/a	}
2603	n/a
2604	n/a	result = PyTuple_New(lz->r);
2605	n/a	if (result == NULL)
2606	n/a	return NULL;
2607	n/a	for (i=0; i<lz->r; i++) {
2608	n/a	PyObject *element = PyTuple_GET_ITEM(lz->pool, lz->indices[i]);
2609	n/a	Py_INCREF(element);
2610	n/a	PyTuple_SET_ITEM(result, i, element);
2611	n/a	}
2612	n/a
2613	n/a	Py_XSETREF(lz->result, result);
2614	n/a	Py_RETURN_NONE;
2615	n/a	}
2616	n/a
2617	n/a	static PyMethodDef combinations_methods[] = {
2618	n/a	{"__reduce__", (PyCFunction)combinations_reduce, METH_NOARGS,
2619	n/a	reduce_doc},
2620	n/a	{"__setstate__", (PyCFunction)combinations_setstate, METH_O,
2621	n/a	setstate_doc},
2622	n/a	{"__sizeof__", (PyCFunction)combinations_sizeof, METH_NOARGS,
2623	n/a	sizeof_doc},
2624	n/a	{NULL, NULL} /* sentinel */
2625	n/a	};
2626	n/a
2627	n/a	PyDoc_STRVAR(combinations_doc,
2628	n/a	"combinations(iterable, r) --> combinations object\n\
2629	n/a	\n\
2630	n/a	Return successive r-length combinations of elements in the iterable.\n\n\
2631	n/a	combinations(range(4), 3) --> (0,1,2), (0,1,3), (0,2,3), (1,2,3)");
2632	n/a
2633	n/a	static PyTypeObject combinations_type = {
2634	n/a	PyVarObject_HEAD_INIT(NULL, 0)
2635	n/a	"itertools.combinations", /* tp_name */
2636	n/a	sizeof(combinationsobject), /* tp_basicsize */
2637	n/a	0, /* tp_itemsize */
2638	n/a	/* methods */
2639	n/a	(destructor)combinations_dealloc, /* tp_dealloc */
2640	n/a	0, /* tp_print */
2641	n/a	0, /* tp_getattr */
2642	n/a	0, /* tp_setattr */
2643	n/a	0, /* tp_reserved */
2644	n/a	0, /* tp_repr */
2645	n/a	0, /* tp_as_number */
2646	n/a	0, /* tp_as_sequence */
2647	n/a	0, /* tp_as_mapping */
2648	n/a	0, /* tp_hash */
2649	n/a	0, /* tp_call */
2650	n/a	0, /* tp_str */
2651	n/a	PyObject_GenericGetAttr, /* tp_getattro */
2652	n/a	0, /* tp_setattro */
2653	n/a	0, /* tp_as_buffer */
2654	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
2655	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
2656	n/a	combinations_doc, /* tp_doc */
2657	n/a	(traverseproc)combinations_traverse,/* tp_traverse */
2658	n/a	0, /* tp_clear */
2659	n/a	0, /* tp_richcompare */
2660	n/a	0, /* tp_weaklistoffset */
2661	n/a	PyObject_SelfIter, /* tp_iter */
2662	n/a	(iternextfunc)combinations_next, /* tp_iternext */
2663	n/a	combinations_methods, /* tp_methods */
2664	n/a	0, /* tp_members */
2665	n/a	0, /* tp_getset */
2666	n/a	0, /* tp_base */
2667	n/a	0, /* tp_dict */
2668	n/a	0, /* tp_descr_get */
2669	n/a	0, /* tp_descr_set */
2670	n/a	0, /* tp_dictoffset */
2671	n/a	0, /* tp_init */
2672	n/a	0, /* tp_alloc */
2673	n/a	combinations_new, /* tp_new */
2674	n/a	PyObject_GC_Del, /* tp_free */
2675	n/a	};
2676	n/a
2677	n/a
2678	n/a	/* combinations with replacement object **************************************/
2679	n/a
2680	n/a	/* Equivalent to:
2681	n/a
2682	n/a	def combinations_with_replacement(iterable, r):
2683	n/a	"combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC"
2684	n/a	# number items returned: (n+r-1)! / r! / (n-1)!
2685	n/a	pool = tuple(iterable)
2686	n/a	n = len(pool)
2687	n/a	indices = [0] * r
2688	n/a	yield tuple(pool[i] for i in indices)
2689	n/a	while 1:
2690	n/a	for i in reversed(range(r)):
2691	n/a	if indices[i] != n - 1:
2692	n/a	break
2693	n/a	else:
2694	n/a	return
2695	n/a	indices[i:] = [indices[i] + 1] * (r - i)
2696	n/a	yield tuple(pool[i] for i in indices)
2697	n/a
2698	n/a	def combinations_with_replacement2(iterable, r):
2699	n/a	'Alternate version that filters from product()'
2700	n/a	pool = tuple(iterable)
2701	n/a	n = len(pool)
2702	n/a	for indices in product(range(n), repeat=r):
2703	n/a	if sorted(indices) == list(indices):
2704	n/a	yield tuple(pool[i] for i in indices)
2705	n/a	*/
2706	n/a	typedef struct {
2707	n/a	PyObject_HEAD
2708	n/a	PyObject pool; / input converted to a tuple */
2709	n/a	Py_ssize_t indices; / one index per result element */
2710	n/a	PyObject result; / most recently returned result tuple */
2711	n/a	Py_ssize_t r; /* size of result tuple */
2712	n/a	int stopped; /* set to 1 when the cwr iterator is exhausted */
2713	n/a	} cwrobject;
2714	n/a
2715	n/a	static PyTypeObject cwr_type;
2716	n/a
2717	n/a	static PyObject *
2718	n/a	cwr_new(PyTypeObject type, PyObject args, PyObject *kwds)
2719	n/a	{
2720	n/a	cwrobject *co;
2721	n/a	Py_ssize_t n;
2722	n/a	Py_ssize_t r;
2723	n/a	PyObject *pool = NULL;
2724	n/a	PyObject *iterable = NULL;
2725	n/a	Py_ssize_t *indices = NULL;
2726	n/a	Py_ssize_t i;
2727	n/a	static char *kwargs[] = {"iterable", "r", NULL};
2728	n/a
2729	n/a	if (!PyArg_ParseTupleAndKeywords(args, kwds,
2730	n/a	"On:combinations_with_replacement",
2731	n/a	kwargs, &iterable, &r))
2732	n/a	return NULL;
2733	n/a
2734	n/a	pool = PySequence_Tuple(iterable);
2735	n/a	if (pool == NULL)
2736	n/a	goto error;
2737	n/a	n = PyTuple_GET_SIZE(pool);
2738	n/a	if (r < 0) {
2739	n/a	PyErr_SetString(PyExc_ValueError, "r must be non-negative");
2740	n/a	goto error;
2741	n/a	}
2742	n/a
2743	n/a	indices = PyMem_New(Py_ssize_t, r);
2744	n/a	if (indices == NULL) {
2745	n/a	PyErr_NoMemory();
2746	n/a	goto error;
2747	n/a	}
2748	n/a
2749	n/a	for (i=0 ; i<r ; i++)
2750	n/a	indices[i] = 0;
2751	n/a
2752	n/a	/* create cwrobject structure */
2753	n/a	co = (cwrobject *)type->tp_alloc(type, 0);
2754	n/a	if (co == NULL)
2755	n/a	goto error;
2756	n/a
2757	n/a	co->pool = pool;
2758	n/a	co->indices = indices;
2759	n/a	co->result = NULL;
2760	n/a	co->r = r;
2761	n/a	co->stopped = !n && r;
2762	n/a
2763	n/a	return (PyObject *)co;
2764	n/a
2765	n/a	error:
2766	n/a	if (indices != NULL)
2767	n/a	PyMem_Free(indices);
2768	n/a	Py_XDECREF(pool);
2769	n/a	return NULL;
2770	n/a	}
2771	n/a
2772	n/a	static void
2773	n/a	cwr_dealloc(cwrobject *co)
2774	n/a	{
2775	n/a	PyObject_GC_UnTrack(co);
2776	n/a	Py_XDECREF(co->pool);
2777	n/a	Py_XDECREF(co->result);
2778	n/a	if (co->indices != NULL)
2779	n/a	PyMem_Free(co->indices);
2780	n/a	Py_TYPE(co)->tp_free(co);
2781	n/a	}
2782	n/a
2783	n/a	static PyObject *
2784	n/a	cwr_sizeof(cwrobject co, void unused)
2785	n/a	{
2786	n/a	Py_ssize_t res;
2787	n/a
2788	n/a	res = _PyObject_SIZE(Py_TYPE(co));
2789	n/a	res += co->r * sizeof(Py_ssize_t);
2790	n/a	return PyLong_FromSsize_t(res);
2791	n/a	}
2792	n/a
2793	n/a	static int
2794	n/a	cwr_traverse(cwrobject co, visitproc visit, void arg)
2795	n/a	{
2796	n/a	Py_VISIT(co->pool);
2797	n/a	Py_VISIT(co->result);
2798	n/a	return 0;
2799	n/a	}
2800	n/a
2801	n/a	static PyObject *
2802	n/a	cwr_next(cwrobject *co)
2803	n/a	{
2804	n/a	PyObject *elem;
2805	n/a	PyObject *oldelem;
2806	n/a	PyObject *pool = co->pool;
2807	n/a	Py_ssize_t *indices = co->indices;
2808	n/a	PyObject *result = co->result;
2809	n/a	Py_ssize_t n = PyTuple_GET_SIZE(pool);
2810	n/a	Py_ssize_t r = co->r;
2811	n/a	Py_ssize_t i, index;
2812	n/a
2813	n/a	if (co->stopped)
2814	n/a	return NULL;
2815	n/a
2816	n/a	if (result == NULL) {
2817	n/a	/* On the first pass, initialize result tuple with pool[0] */
2818	n/a	result = PyTuple_New(r);
2819	n/a	if (result == NULL)
2820	n/a	goto empty;
2821	n/a	co->result = result;
2822	n/a	if (n > 0) {
2823	n/a	elem = PyTuple_GET_ITEM(pool, 0);
2824	n/a	for (i=0; i<r ; i++) {
2825	n/a	assert(indices[i] == 0);
2826	n/a	Py_INCREF(elem);
2827	n/a	PyTuple_SET_ITEM(result, i, elem);
2828	n/a	}
2829	n/a	}
2830	n/a	} else {
2831	n/a	/* Copy the previous result tuple or re-use it if available */
2832	n/a	if (Py_REFCNT(result) > 1) {
2833	n/a	PyObject *old_result = result;
2834	n/a	result = PyTuple_New(r);
2835	n/a	if (result == NULL)
2836	n/a	goto empty;
2837	n/a	co->result = result;
2838	n/a	for (i=0; i<r ; i++) {
2839	n/a	elem = PyTuple_GET_ITEM(old_result, i);
2840	n/a	Py_INCREF(elem);
2841	n/a	PyTuple_SET_ITEM(result, i, elem);
2842	n/a	}
2843	n/a	Py_DECREF(old_result);
2844	n/a	}
2845	n/a	/* Now, we've got the only copy so we can update it in-place CPython's
2846	n/a	empty tuple is a singleton and cached in PyTuple's freelist. */
2847	n/a	assert(r == 0 \|\| Py_REFCNT(result) == 1);
2848	n/a
2849	n/a	/* Scan indices right-to-left until finding one that is not
2850	n/a	* at its maximum (n-1). */
2851	n/a	for (i=r-1 ; i >= 0 && indices[i] == n-1; i--)
2852	n/a	;
2853	n/a
2854	n/a	/* If i is negative, then the indices are all at
2855	n/a	their maximum value and we're done. */
2856	n/a	if (i < 0)
2857	n/a	goto empty;
2858	n/a
2859	n/a	/* Increment the current index which we know is not at its
2860	n/a	maximum. Then set all to the right to the same value. */
2861	n/a	index = indices[i] + 1;
2862	n/a	assert(index < n);
2863	n/a	elem = PyTuple_GET_ITEM(pool, index);
2864	n/a	for ( ; i<r ; i++) {
2865	n/a	indices[i] = index;
2866	n/a	Py_INCREF(elem);
2867	n/a	oldelem = PyTuple_GET_ITEM(result, i);
2868	n/a	PyTuple_SET_ITEM(result, i, elem);
2869	n/a	Py_DECREF(oldelem);
2870	n/a	}
2871	n/a	}
2872	n/a
2873	n/a	Py_INCREF(result);
2874	n/a	return result;
2875	n/a
2876	n/a	empty:
2877	n/a	co->stopped = 1;
2878	n/a	return NULL;
2879	n/a	}
2880	n/a
2881	n/a	static PyObject *
2882	n/a	cwr_reduce(cwrobject *lz)
2883	n/a	{
2884	n/a	if (lz->result == NULL) {
2885	n/a	return Py_BuildValue("O(On)", Py_TYPE(lz), lz->pool, lz->r);
2886	n/a	} else if (lz->stopped) {
2887	n/a	return Py_BuildValue("O(()n)", Py_TYPE(lz), lz->r);
2888	n/a	} else {
2889	n/a	PyObject *indices;
2890	n/a	Py_ssize_t i;
2891	n/a
2892	n/a	/* we must pickle the indices and use them for setstate */
2893	n/a	indices = PyTuple_New(lz->r);
2894	n/a	if (!indices)
2895	n/a	return NULL;
2896	n/a	for (i=0; i<lz->r; i++) {
2897	n/a	PyObject* index = PyLong_FromSsize_t(lz->indices[i]);
2898	n/a	if (!index) {
2899	n/a	Py_DECREF(indices);
2900	n/a	return NULL;
2901	n/a	}
2902	n/a	PyTuple_SET_ITEM(indices, i, index);
2903	n/a	}
2904	n/a
2905	n/a	return Py_BuildValue("O(On)N", Py_TYPE(lz), lz->pool, lz->r, indices);
2906	n/a	}
2907	n/a	}
2908	n/a
2909	n/a	static PyObject *
2910	n/a	cwr_setstate(cwrobject lz, PyObject state)
2911	n/a	{
2912	n/a	PyObject *result;
2913	n/a	Py_ssize_t n, i;
2914	n/a
2915	n/a	if (!PyTuple_Check(state) \|\| PyTuple_GET_SIZE(state) != lz->r)
2916	n/a	{
2917	n/a	PyErr_SetString(PyExc_ValueError, "invalid arguments");
2918	n/a	return NULL;
2919	n/a	}
2920	n/a
2921	n/a	n = PyTuple_GET_SIZE(lz->pool);
2922	n/a	for (i=0; i<lz->r; i++) {
2923	n/a	PyObject* indexObject = PyTuple_GET_ITEM(state, i);
2924	n/a	Py_ssize_t index = PyLong_AsSsize_t(indexObject);
2925	n/a
2926	n/a	if (index < 0 && PyErr_Occurred())
2927	n/a	return NULL; /* not an integer */
2928	n/a	/* clamp the index */
2929	n/a	if (index < 0)
2930	n/a	index = 0;
2931	n/a	else if (index > n-1)
2932	n/a	index = n-1;
2933	n/a	lz->indices[i] = index;
2934	n/a	}
2935	n/a	result = PyTuple_New(lz->r);
2936	n/a	if (result == NULL)
2937	n/a	return NULL;
2938	n/a	for (i=0; i<lz->r; i++) {
2939	n/a	PyObject *element = PyTuple_GET_ITEM(lz->pool, lz->indices[i]);
2940	n/a	Py_INCREF(element);
2941	n/a	PyTuple_SET_ITEM(result, i, element);
2942	n/a	}
2943	n/a	Py_XSETREF(lz->result, result);
2944	n/a	Py_RETURN_NONE;
2945	n/a	}
2946	n/a
2947	n/a	static PyMethodDef cwr_methods[] = {
2948	n/a	{"__reduce__", (PyCFunction)cwr_reduce, METH_NOARGS,
2949	n/a	reduce_doc},
2950	n/a	{"__setstate__", (PyCFunction)cwr_setstate, METH_O,
2951	n/a	setstate_doc},
2952	n/a	{"__sizeof__", (PyCFunction)cwr_sizeof, METH_NOARGS,
2953	n/a	sizeof_doc},
2954	n/a	{NULL, NULL} /* sentinel */
2955	n/a	};
2956	n/a
2957	n/a	PyDoc_STRVAR(cwr_doc,
2958	n/a	"combinations_with_replacement(iterable, r) --> combinations_with_replacement object\n\
2959	n/a	\n\
2960	n/a	Return successive r-length combinations of elements in the iterable\n\
2961	n/a	allowing individual elements to have successive repeats.\n\
2962	n/a	combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC");
2963	n/a
2964	n/a	static PyTypeObject cwr_type = {
2965	n/a	PyVarObject_HEAD_INIT(NULL, 0)
2966	n/a	"itertools.combinations_with_replacement", /* tp_name */
2967	n/a	sizeof(cwrobject), /* tp_basicsize */
2968	n/a	0, /* tp_itemsize */
2969	n/a	/* methods */
2970	n/a	(destructor)cwr_dealloc, /* tp_dealloc */
2971	n/a	0, /* tp_print */
2972	n/a	0, /* tp_getattr */
2973	n/a	0, /* tp_setattr */
2974	n/a	0, /* tp_reserved */
2975	n/a	0, /* tp_repr */
2976	n/a	0, /* tp_as_number */
2977	n/a	0, /* tp_as_sequence */
2978	n/a	0, /* tp_as_mapping */
2979	n/a	0, /* tp_hash */
2980	n/a	0, /* tp_call */
2981	n/a	0, /* tp_str */
2982	n/a	PyObject_GenericGetAttr, /* tp_getattro */
2983	n/a	0, /* tp_setattro */
2984	n/a	0, /* tp_as_buffer */
2985	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
2986	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
2987	n/a	cwr_doc, /* tp_doc */
2988	n/a	(traverseproc)cwr_traverse, /* tp_traverse */
2989	n/a	0, /* tp_clear */
2990	n/a	0, /* tp_richcompare */
2991	n/a	0, /* tp_weaklistoffset */
2992	n/a	PyObject_SelfIter, /* tp_iter */
2993	n/a	(iternextfunc)cwr_next, /* tp_iternext */
2994	n/a	cwr_methods, /* tp_methods */
2995	n/a	0, /* tp_members */
2996	n/a	0, /* tp_getset */
2997	n/a	0, /* tp_base */
2998	n/a	0, /* tp_dict */
2999	n/a	0, /* tp_descr_get */
3000	n/a	0, /* tp_descr_set */
3001	n/a	0, /* tp_dictoffset */
3002	n/a	0, /* tp_init */
3003	n/a	0, /* tp_alloc */
3004	n/a	cwr_new, /* tp_new */
3005	n/a	PyObject_GC_Del, /* tp_free */
3006	n/a	};
3007	n/a
3008	n/a
3009	n/a	/* permutations object ********************************************************
3010	n/a
3011	n/a	def permutations(iterable, r=None):
3012	n/a	'permutations(range(3), 2) --> (0,1) (0,2) (1,0) (1,2) (2,0) (2,1)'
3013	n/a	pool = tuple(iterable)
3014	n/a	n = len(pool)
3015	n/a	r = n if r is None else r
3016	n/a	indices = range(n)
3017	n/a	cycles = range(n-r+1, n+1)[::-1]
3018	n/a	yield tuple(pool[i] for i in indices[:r])
3019	n/a	while n:
3020	n/a	for i in reversed(range(r)):
3021	n/a	cycles[i] -= 1
3022	n/a	if cycles[i] == 0:
3023	n/a	indices[i:] = indices[i+1:] + indices[i:i+1]
3024	n/a	cycles[i] = n - i
3025	n/a	else:
3026	n/a	j = cycles[i]
3027	n/a	indices[i], indices[-j] = indices[-j], indices[i]
3028	n/a	yield tuple(pool[i] for i in indices[:r])
3029	n/a	break
3030	n/a	else:
3031	n/a	return
3032	n/a	*/
3033	n/a
3034	n/a	typedef struct {
3035	n/a	PyObject_HEAD
3036	n/a	PyObject pool; / input converted to a tuple */
3037	n/a	Py_ssize_t indices; / one index per element in the pool */
3038	n/a	Py_ssize_t cycles; / one rollover counter per element in the result */
3039	n/a	PyObject result; / most recently returned result tuple */
3040	n/a	Py_ssize_t r; /* size of result tuple */
3041	n/a	int stopped; /* set to 1 when the iterator is exhausted */
3042	n/a	} permutationsobject;
3043	n/a
3044	n/a	static PyTypeObject permutations_type;
3045	n/a
3046	n/a	static PyObject *
3047	n/a	permutations_new(PyTypeObject type, PyObject args, PyObject *kwds)
3048	n/a	{
3049	n/a	permutationsobject *po;
3050	n/a	Py_ssize_t n;
3051	n/a	Py_ssize_t r;
3052	n/a	PyObject *robj = Py_None;
3053	n/a	PyObject *pool = NULL;
3054	n/a	PyObject *iterable = NULL;
3055	n/a	Py_ssize_t *indices = NULL;
3056	n/a	Py_ssize_t *cycles = NULL;
3057	n/a	Py_ssize_t i;
3058	n/a	static char *kwargs[] = {"iterable", "r", NULL};
3059	n/a
3060	n/a	if (!PyArg_ParseTupleAndKeywords(args, kwds, "O\|O:permutations", kwargs,
3061	n/a	&iterable, &robj))
3062	n/a	return NULL;
3063	n/a
3064	n/a	pool = PySequence_Tuple(iterable);
3065	n/a	if (pool == NULL)
3066	n/a	goto error;
3067	n/a	n = PyTuple_GET_SIZE(pool);
3068	n/a
3069	n/a	r = n;
3070	n/a	if (robj != Py_None) {
3071	n/a	if (!PyLong_Check(robj)) {
3072	n/a	PyErr_SetString(PyExc_TypeError, "Expected int as r");
3073	n/a	goto error;
3074	n/a	}
3075	n/a	r = PyLong_AsSsize_t(robj);
3076	n/a	if (r == -1 && PyErr_Occurred())
3077	n/a	goto error;
3078	n/a	}
3079	n/a	if (r < 0) {
3080	n/a	PyErr_SetString(PyExc_ValueError, "r must be non-negative");
3081	n/a	goto error;
3082	n/a	}
3083	n/a
3084	n/a	indices = PyMem_New(Py_ssize_t, n);
3085	n/a	cycles = PyMem_New(Py_ssize_t, r);
3086	n/a	if (indices == NULL \|\| cycles == NULL) {
3087	n/a	PyErr_NoMemory();
3088	n/a	goto error;
3089	n/a	}
3090	n/a
3091	n/a	for (i=0 ; i<n ; i++)
3092	n/a	indices[i] = i;
3093	n/a	for (i=0 ; i<r ; i++)
3094	n/a	cycles[i] = n - i;
3095	n/a
3096	n/a	/* create permutationsobject structure */
3097	n/a	po = (permutationsobject *)type->tp_alloc(type, 0);
3098	n/a	if (po == NULL)
3099	n/a	goto error;
3100	n/a
3101	n/a	po->pool = pool;
3102	n/a	po->indices = indices;
3103	n/a	po->cycles = cycles;
3104	n/a	po->result = NULL;
3105	n/a	po->r = r;
3106	n/a	po->stopped = r > n ? 1 : 0;
3107	n/a
3108	n/a	return (PyObject *)po;
3109	n/a
3110	n/a	error:
3111	n/a	if (indices != NULL)
3112	n/a	PyMem_Free(indices);
3113	n/a	if (cycles != NULL)
3114	n/a	PyMem_Free(cycles);
3115	n/a	Py_XDECREF(pool);
3116	n/a	return NULL;
3117	n/a	}
3118	n/a
3119	n/a	static void
3120	n/a	permutations_dealloc(permutationsobject *po)
3121	n/a	{
3122	n/a	PyObject_GC_UnTrack(po);
3123	n/a	Py_XDECREF(po->pool);
3124	n/a	Py_XDECREF(po->result);
3125	n/a	PyMem_Free(po->indices);
3126	n/a	PyMem_Free(po->cycles);
3127	n/a	Py_TYPE(po)->tp_free(po);
3128	n/a	}
3129	n/a
3130	n/a	static PyObject *
3131	n/a	permutations_sizeof(permutationsobject po, void unused)
3132	n/a	{
3133	n/a	Py_ssize_t res;
3134	n/a
3135	n/a	res = _PyObject_SIZE(Py_TYPE(po));
3136	n/a	res += PyTuple_GET_SIZE(po->pool) * sizeof(Py_ssize_t);
3137	n/a	res += po->r * sizeof(Py_ssize_t);
3138	n/a	return PyLong_FromSsize_t(res);
3139	n/a	}
3140	n/a
3141	n/a	static int
3142	n/a	permutations_traverse(permutationsobject po, visitproc visit, void arg)
3143	n/a	{
3144	n/a	Py_VISIT(po->pool);
3145	n/a	Py_VISIT(po->result);
3146	n/a	return 0;
3147	n/a	}
3148	n/a
3149	n/a	static PyObject *
3150	n/a	permutations_next(permutationsobject *po)
3151	n/a	{
3152	n/a	PyObject *elem;
3153	n/a	PyObject *oldelem;
3154	n/a	PyObject *pool = po->pool;
3155	n/a	Py_ssize_t *indices = po->indices;
3156	n/a	Py_ssize_t *cycles = po->cycles;
3157	n/a	PyObject *result = po->result;
3158	n/a	Py_ssize_t n = PyTuple_GET_SIZE(pool);
3159	n/a	Py_ssize_t r = po->r;
3160	n/a	Py_ssize_t i, j, k, index;
3161	n/a
3162	n/a	if (po->stopped)
3163	n/a	return NULL;
3164	n/a
3165	n/a	if (result == NULL) {
3166	n/a	/* On the first pass, initialize result tuple using the indices */
3167	n/a	result = PyTuple_New(r);
3168	n/a	if (result == NULL)
3169	n/a	goto empty;
3170	n/a	po->result = result;
3171	n/a	for (i=0; i<r ; i++) {
3172	n/a	index = indices[i];
3173	n/a	elem = PyTuple_GET_ITEM(pool, index);
3174	n/a	Py_INCREF(elem);
3175	n/a	PyTuple_SET_ITEM(result, i, elem);
3176	n/a	}
3177	n/a	} else {
3178	n/a	if (n == 0)
3179	n/a	goto empty;
3180	n/a
3181	n/a	/* Copy the previous result tuple or re-use it if available */
3182	n/a	if (Py_REFCNT(result) > 1) {
3183	n/a	PyObject *old_result = result;
3184	n/a	result = PyTuple_New(r);
3185	n/a	if (result == NULL)
3186	n/a	goto empty;
3187	n/a	po->result = result;
3188	n/a	for (i=0; i<r ; i++) {
3189	n/a	elem = PyTuple_GET_ITEM(old_result, i);
3190	n/a	Py_INCREF(elem);
3191	n/a	PyTuple_SET_ITEM(result, i, elem);
3192	n/a	}
3193	n/a	Py_DECREF(old_result);
3194	n/a	}
3195	n/a	/* Now, we've got the only copy so we can update it in-place */
3196	n/a	assert(r == 0 \|\| Py_REFCNT(result) == 1);
3197	n/a
3198	n/a	/* Decrement rightmost cycle, moving leftward upon zero rollover */
3199	n/a	for (i=r-1 ; i>=0 ; i--) {
3200	n/a	cycles[i] -= 1;
3201	n/a	if (cycles[i] == 0) {
3202	n/a	/* rotatation: indices[i:] = indices[i+1:] + indices[i:i+1] */
3203	n/a	index = indices[i];
3204	n/a	for (j=i ; j<n-1 ; j++)
3205	n/a	indices[j] = indices[j+1];
3206	n/a	indices[n-1] = index;
3207	n/a	cycles[i] = n - i;
3208	n/a	} else {
3209	n/a	j = cycles[i];
3210	n/a	index = indices[i];
3211	n/a	indices[i] = indices[n-j];
3212	n/a	indices[n-j] = index;
3213	n/a
3214	n/a	for (k=i; k<r ; k++) {
3215	n/a	/* start with i, the leftmost element that changed */
3216	n/a	/* yield tuple(pool[k] for k in indices[:r]) */
3217	n/a	index = indices[k];
3218	n/a	elem = PyTuple_GET_ITEM(pool, index);
3219	n/a	Py_INCREF(elem);
3220	n/a	oldelem = PyTuple_GET_ITEM(result, k);
3221	n/a	PyTuple_SET_ITEM(result, k, elem);
3222	n/a	Py_DECREF(oldelem);
3223	n/a	}
3224	n/a	break;
3225	n/a	}
3226	n/a	}
3227	n/a	/* If i is negative, then the cycles have all
3228	n/a	rolled-over and we're done. */
3229	n/a	if (i < 0)
3230	n/a	goto empty;
3231	n/a	}
3232	n/a	Py_INCREF(result);
3233	n/a	return result;
3234	n/a
3235	n/a	empty:
3236	n/a	po->stopped = 1;
3237	n/a	return NULL;
3238	n/a	}
3239	n/a
3240	n/a	static PyObject *
3241	n/a	permutations_reduce(permutationsobject *po)
3242	n/a	{
3243	n/a	if (po->result == NULL) {
3244	n/a	return Py_BuildValue("O(On)", Py_TYPE(po), po->pool, po->r);
3245	n/a	} else if (po->stopped) {
3246	n/a	return Py_BuildValue("O(()n)", Py_TYPE(po), po->r);
3247	n/a	} else {
3248	n/a	PyObject indices=NULL, cycles=NULL;
3249	n/a	Py_ssize_t n, i;
3250	n/a
3251	n/a	/* we must pickle the indices and cycles and use them for setstate */
3252	n/a	n = PyTuple_GET_SIZE(po->pool);
3253	n/a	indices = PyTuple_New(n);
3254	n/a	if (indices == NULL)
3255	n/a	goto err;
3256	n/a	for (i=0; i<n; i++) {
3257	n/a	PyObject* index = PyLong_FromSsize_t(po->indices[i]);
3258	n/a	if (!index)
3259	n/a	goto err;
3260	n/a	PyTuple_SET_ITEM(indices, i, index);
3261	n/a	}
3262	n/a
3263	n/a	cycles = PyTuple_New(po->r);
3264	n/a	if (cycles == NULL)
3265	n/a	goto err;
3266	n/a	for (i=0 ; i<po->r ; i++) {
3267	n/a	PyObject* index = PyLong_FromSsize_t(po->cycles[i]);
3268	n/a	if (!index)
3269	n/a	goto err;
3270	n/a	PyTuple_SET_ITEM(cycles, i, index);
3271	n/a	}
3272	n/a	return Py_BuildValue("O(On)(NN)", Py_TYPE(po),
3273	n/a	po->pool, po->r,
3274	n/a	indices, cycles);
3275	n/a	err:
3276	n/a	Py_XDECREF(indices);
3277	n/a	Py_XDECREF(cycles);
3278	n/a	return NULL;
3279	n/a	}
3280	n/a	}
3281	n/a
3282	n/a	static PyObject *
3283	n/a	permutations_setstate(permutationsobject po, PyObject state)
3284	n/a	{
3285	n/a	PyObject indices, cycles, *result;
3286	n/a	Py_ssize_t n, i;
3287	n/a
3288	n/a	if (!PyTuple_Check(state)) {
3289	n/a	PyErr_SetString(PyExc_TypeError, "state is not a tuple");
3290	n/a	return NULL;
3291	n/a	}
3292	n/a	if (!PyArg_ParseTuple(state, "O!O!",
3293	n/a	&PyTuple_Type, &indices,
3294	n/a	&PyTuple_Type, &cycles)) {
3295	n/a	return NULL;
3296	n/a	}
3297	n/a
3298	n/a	n = PyTuple_GET_SIZE(po->pool);
3299	n/a	if (PyTuple_GET_SIZE(indices) != n \|\| PyTuple_GET_SIZE(cycles) != po->r) {
3300	n/a	PyErr_SetString(PyExc_ValueError, "invalid arguments");
3301	n/a	return NULL;
3302	n/a	}
3303	n/a
3304	n/a	for (i=0; i<n; i++) {
3305	n/a	PyObject* indexObject = PyTuple_GET_ITEM(indices, i);
3306	n/a	Py_ssize_t index = PyLong_AsSsize_t(indexObject);
3307	n/a	if (index < 0 && PyErr_Occurred())
3308	n/a	return NULL; /* not an integer */
3309	n/a	/* clamp the index */
3310	n/a	if (index < 0)
3311	n/a	index = 0;
3312	n/a	else if (index > n-1)
3313	n/a	index = n-1;
3314	n/a	po->indices[i] = index;
3315	n/a	}
3316	n/a
3317	n/a	for (i=0; i<po->r; i++) {
3318	n/a	PyObject* indexObject = PyTuple_GET_ITEM(cycles, i);
3319	n/a	Py_ssize_t index = PyLong_AsSsize_t(indexObject);
3320	n/a	if (index < 0 && PyErr_Occurred())
3321	n/a	return NULL; /* not an integer */
3322	n/a	if (index < 1)
3323	n/a	index = 1;
3324	n/a	else if (index > n-i)
3325	n/a	index = n-i;
3326	n/a	po->cycles[i] = index;
3327	n/a	}
3328	n/a	result = PyTuple_New(po->r);
3329	n/a	if (result == NULL)
3330	n/a	return NULL;
3331	n/a	for (i=0; i<po->r; i++) {
3332	n/a	PyObject *element = PyTuple_GET_ITEM(po->pool, po->indices[i]);
3333	n/a	Py_INCREF(element);
3334	n/a	PyTuple_SET_ITEM(result, i, element);
3335	n/a	}
3336	n/a	Py_XSETREF(po->result, result);
3337	n/a	Py_RETURN_NONE;
3338	n/a	}
3339	n/a
3340	n/a	static PyMethodDef permuations_methods[] = {
3341	n/a	{"__reduce__", (PyCFunction)permutations_reduce, METH_NOARGS,
3342	n/a	reduce_doc},
3343	n/a	{"__setstate__", (PyCFunction)permutations_setstate, METH_O,
3344	n/a	setstate_doc},
3345	n/a	{"__sizeof__", (PyCFunction)permutations_sizeof, METH_NOARGS,
3346	n/a	sizeof_doc},
3347	n/a	{NULL, NULL} /* sentinel */
3348	n/a	};
3349	n/a
3350	n/a	PyDoc_STRVAR(permutations_doc,
3351	n/a	"permutations(iterable[, r]) --> permutations object\n\
3352	n/a	\n\
3353	n/a	Return successive r-length permutations of elements in the iterable.\n\n\
3354	n/a	permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)");
3355	n/a
3356	n/a	static PyTypeObject permutations_type = {
3357	n/a	PyVarObject_HEAD_INIT(NULL, 0)
3358	n/a	"itertools.permutations", /* tp_name */
3359	n/a	sizeof(permutationsobject), /* tp_basicsize */
3360	n/a	0, /* tp_itemsize */
3361	n/a	/* methods */
3362	n/a	(destructor)permutations_dealloc, /* tp_dealloc */
3363	n/a	0, /* tp_print */
3364	n/a	0, /* tp_getattr */
3365	n/a	0, /* tp_setattr */
3366	n/a	0, /* tp_reserved */
3367	n/a	0, /* tp_repr */
3368	n/a	0, /* tp_as_number */
3369	n/a	0, /* tp_as_sequence */
3370	n/a	0, /* tp_as_mapping */
3371	n/a	0, /* tp_hash */
3372	n/a	0, /* tp_call */
3373	n/a	0, /* tp_str */
3374	n/a	PyObject_GenericGetAttr, /* tp_getattro */
3375	n/a	0, /* tp_setattro */
3376	n/a	0, /* tp_as_buffer */
3377	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
3378	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
3379	n/a	permutations_doc, /* tp_doc */
3380	n/a	(traverseproc)permutations_traverse,/* tp_traverse */
3381	n/a	0, /* tp_clear */
3382	n/a	0, /* tp_richcompare */
3383	n/a	0, /* tp_weaklistoffset */
3384	n/a	PyObject_SelfIter, /* tp_iter */
3385	n/a	(iternextfunc)permutations_next, /* tp_iternext */
3386	n/a	permuations_methods, /* tp_methods */
3387	n/a	0, /* tp_members */
3388	n/a	0, /* tp_getset */
3389	n/a	0, /* tp_base */
3390	n/a	0, /* tp_dict */
3391	n/a	0, /* tp_descr_get */
3392	n/a	0, /* tp_descr_set */
3393	n/a	0, /* tp_dictoffset */
3394	n/a	0, /* tp_init */
3395	n/a	0, /* tp_alloc */
3396	n/a	permutations_new, /* tp_new */
3397	n/a	PyObject_GC_Del, /* tp_free */
3398	n/a	};
3399	n/a
3400	n/a	/* accumulate object ********************************************************/
3401	n/a
3402	n/a	typedef struct {
3403	n/a	PyObject_HEAD
3404	n/a	PyObject *total;
3405	n/a	PyObject *it;
3406	n/a	PyObject *binop;
3407	n/a	} accumulateobject;
3408	n/a
3409	n/a	static PyTypeObject accumulate_type;
3410	n/a
3411	n/a	static PyObject *
3412	n/a	accumulate_new(PyTypeObject type, PyObject args, PyObject *kwds)
3413	n/a	{
3414	n/a	static char *kwargs[] = {"iterable", "func", NULL};
3415	n/a	PyObject *iterable;
3416	n/a	PyObject *it;
3417	n/a	PyObject *binop = Py_None;
3418	n/a	accumulateobject *lz;
3419	n/a
3420	n/a	if (!PyArg_ParseTupleAndKeywords(args, kwds, "O\|O:accumulate",
3421	n/a	kwargs, &iterable, &binop))
3422	n/a	return NULL;
3423	n/a
3424	n/a	/* Get iterator. */
3425	n/a	it = PyObject_GetIter(iterable);
3426	n/a	if (it == NULL)
3427	n/a	return NULL;
3428	n/a
3429	n/a	/* create accumulateobject structure */
3430	n/a	lz = (accumulateobject *)type->tp_alloc(type, 0);
3431	n/a	if (lz == NULL) {
3432	n/a	Py_DECREF(it);
3433	n/a	return NULL;
3434	n/a	}
3435	n/a
3436	n/a	if (binop != Py_None) {
3437	n/a	Py_XINCREF(binop);
3438	n/a	lz->binop = binop;
3439	n/a	}
3440	n/a	lz->total = NULL;
3441	n/a	lz->it = it;
3442	n/a	return (PyObject *)lz;
3443	n/a	}
3444	n/a
3445	n/a	static void
3446	n/a	accumulate_dealloc(accumulateobject *lz)
3447	n/a	{
3448	n/a	PyObject_GC_UnTrack(lz);
3449	n/a	Py_XDECREF(lz->binop);
3450	n/a	Py_XDECREF(lz->total);
3451	n/a	Py_XDECREF(lz->it);
3452	n/a	Py_TYPE(lz)->tp_free(lz);
3453	n/a	}
3454	n/a
3455	n/a	static int
3456	n/a	accumulate_traverse(accumulateobject lz, visitproc visit, void arg)
3457	n/a	{
3458	n/a	Py_VISIT(lz->binop);
3459	n/a	Py_VISIT(lz->it);
3460	n/a	Py_VISIT(lz->total);
3461	n/a	return 0;
3462	n/a	}
3463	n/a
3464	n/a	static PyObject *
3465	n/a	accumulate_next(accumulateobject *lz)
3466	n/a	{
3467	n/a	PyObject val, newtotal;
3468	n/a
3469	n/a	val = (*Py_TYPE(lz->it)->tp_iternext)(lz->it);
3470	n/a	if (val == NULL)
3471	n/a	return NULL;
3472	n/a
3473	n/a	if (lz->total == NULL) {
3474	n/a	Py_INCREF(val);
3475	n/a	lz->total = val;
3476	n/a	return lz->total;
3477	n/a	}
3478	n/a
3479	n/a	if (lz->binop == NULL)
3480	n/a	newtotal = PyNumber_Add(lz->total, val);
3481	n/a	else
3482	n/a	newtotal = PyObject_CallFunctionObjArgs(lz->binop, lz->total, val, NULL);
3483	n/a	Py_DECREF(val);
3484	n/a	if (newtotal == NULL)
3485	n/a	return NULL;
3486	n/a
3487	n/a	Py_INCREF(newtotal);
3488	n/a	Py_SETREF(lz->total, newtotal);
3489	n/a	return newtotal;
3490	n/a	}
3491	n/a
3492	n/a	static PyObject *
3493	n/a	accumulate_reduce(accumulateobject *lz)
3494	n/a	{
3495	n/a	if (lz->total == Py_None) {
3496	n/a	PyObject *it;
3497	n/a
3498	n/a	if (PyType_Ready(&chain_type) < 0)
3499	n/a	return NULL;
3500	n/a	if (PyType_Ready(&islice_type) < 0)
3501	n/a	return NULL;
3502	n/a	it = PyObject_CallFunction((PyObject *)&chain_type, "(O)O",
3503	n/a	lz->total, lz->it);
3504	n/a	if (it == NULL)
3505	n/a	return NULL;
3506	n/a	it = PyObject_CallFunction((PyObject *)Py_TYPE(lz), "NO",
3507	n/a	it, lz->binop ? lz->binop : Py_None);
3508	n/a	if (it == NULL)
3509	n/a	return NULL;
3510	n/a	return Py_BuildValue("O(NiO)", &islice_type, it, 1, Py_None);
3511	n/a	}
3512	n/a	return Py_BuildValue("O(OO)O", Py_TYPE(lz),
3513	n/a	lz->it, lz->binop?lz->binop:Py_None,
3514	n/a	lz->total?lz->total:Py_None);
3515	n/a	}
3516	n/a
3517	n/a	static PyObject *
3518	n/a	accumulate_setstate(accumulateobject lz, PyObject state)
3519	n/a	{
3520	n/a	Py_INCREF(state);
3521	n/a	Py_XSETREF(lz->total, state);
3522	n/a	Py_RETURN_NONE;
3523	n/a	}
3524	n/a
3525	n/a	static PyMethodDef accumulate_methods[] = {
3526	n/a	{"__reduce__", (PyCFunction)accumulate_reduce, METH_NOARGS,
3527	n/a	reduce_doc},
3528	n/a	{"__setstate__", (PyCFunction)accumulate_setstate, METH_O,
3529	n/a	setstate_doc},
3530	n/a	{NULL, NULL} /* sentinel */
3531	n/a	};
3532	n/a
3533	n/a	PyDoc_STRVAR(accumulate_doc,
3534	n/a	"accumulate(iterable[, func]) --> accumulate object\n\
3535	n/a	\n\
3536	n/a	Return series of accumulated sums (or other binary function results).");
3537	n/a
3538	n/a	static PyTypeObject accumulate_type = {
3539	n/a	PyVarObject_HEAD_INIT(NULL, 0)
3540	n/a	"itertools.accumulate", /* tp_name */
3541	n/a	sizeof(accumulateobject), /* tp_basicsize */
3542	n/a	0, /* tp_itemsize */
3543	n/a	/* methods */
3544	n/a	(destructor)accumulate_dealloc, /* tp_dealloc */
3545	n/a	0, /* tp_print */
3546	n/a	0, /* tp_getattr */
3547	n/a	0, /* tp_setattr */
3548	n/a	0, /* tp_reserved */
3549	n/a	0, /* tp_repr */
3550	n/a	0, /* tp_as_number */
3551	n/a	0, /* tp_as_sequence */
3552	n/a	0, /* tp_as_mapping */
3553	n/a	0, /* tp_hash */
3554	n/a	0, /* tp_call */
3555	n/a	0, /* tp_str */
3556	n/a	PyObject_GenericGetAttr, /* tp_getattro */
3557	n/a	0, /* tp_setattro */
3558	n/a	0, /* tp_as_buffer */
3559	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
3560	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
3561	n/a	accumulate_doc, /* tp_doc */
3562	n/a	(traverseproc)accumulate_traverse, /* tp_traverse */
3563	n/a	0, /* tp_clear */
3564	n/a	0, /* tp_richcompare */
3565	n/a	0, /* tp_weaklistoffset */
3566	n/a	PyObject_SelfIter, /* tp_iter */
3567	n/a	(iternextfunc)accumulate_next, /* tp_iternext */
3568	n/a	accumulate_methods, /* tp_methods */
3569	n/a	0, /* tp_members */
3570	n/a	0, /* tp_getset */
3571	n/a	0, /* tp_base */
3572	n/a	0, /* tp_dict */
3573	n/a	0, /* tp_descr_get */
3574	n/a	0, /* tp_descr_set */
3575	n/a	0, /* tp_dictoffset */
3576	n/a	0, /* tp_init */
3577	n/a	0, /* tp_alloc */
3578	n/a	accumulate_new, /* tp_new */
3579	n/a	PyObject_GC_Del, /* tp_free */
3580	n/a	};
3581	n/a
3582	n/a
3583	n/a	/* compress object ************************************************************/
3584	n/a
3585	n/a	/* Equivalent to:
3586	n/a
3587	n/a	def compress(data, selectors):
3588	n/a	"compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F"
3589	n/a	return (d for d, s in zip(data, selectors) if s)
3590	n/a	*/
3591	n/a
3592	n/a	typedef struct {
3593	n/a	PyObject_HEAD
3594	n/a	PyObject *data;
3595	n/a	PyObject *selectors;
3596	n/a	} compressobject;
3597	n/a
3598	n/a	static PyTypeObject compress_type;
3599	n/a
3600	n/a	static PyObject *
3601	n/a	compress_new(PyTypeObject type, PyObject args, PyObject *kwds)
3602	n/a	{
3603	n/a	PyObject seq1, seq2;
3604	n/a	PyObject data=NULL, selectors=NULL;
3605	n/a	compressobject *lz;
3606	n/a	static char *kwargs[] = {"data", "selectors", NULL};
3607	n/a
3608	n/a	if (!PyArg_ParseTupleAndKeywords(args, kwds, "OO:compress", kwargs, &seq1, &seq2))
3609	n/a	return NULL;
3610	n/a
3611	n/a	data = PyObject_GetIter(seq1);
3612	n/a	if (data == NULL)
3613	n/a	goto fail;
3614	n/a	selectors = PyObject_GetIter(seq2);
3615	n/a	if (selectors == NULL)
3616	n/a	goto fail;
3617	n/a
3618	n/a	/* create compressobject structure */
3619	n/a	lz = (compressobject *)type->tp_alloc(type, 0);
3620	n/a	if (lz == NULL)
3621	n/a	goto fail;
3622	n/a	lz->data = data;
3623	n/a	lz->selectors = selectors;
3624	n/a	return (PyObject *)lz;
3625	n/a
3626	n/a	fail:
3627	n/a	Py_XDECREF(data);
3628	n/a	Py_XDECREF(selectors);
3629	n/a	return NULL;
3630	n/a	}
3631	n/a
3632	n/a	static void
3633	n/a	compress_dealloc(compressobject *lz)
3634	n/a	{
3635	n/a	PyObject_GC_UnTrack(lz);
3636	n/a	Py_XDECREF(lz->data);
3637	n/a	Py_XDECREF(lz->selectors);
3638	n/a	Py_TYPE(lz)->tp_free(lz);
3639	n/a	}
3640	n/a
3641	n/a	static int
3642	n/a	compress_traverse(compressobject lz, visitproc visit, void arg)
3643	n/a	{
3644	n/a	Py_VISIT(lz->data);
3645	n/a	Py_VISIT(lz->selectors);
3646	n/a	return 0;
3647	n/a	}
3648	n/a
3649	n/a	static PyObject *
3650	n/a	compress_next(compressobject *lz)
3651	n/a	{
3652	n/a	PyObject data = lz->data, selectors = lz->selectors;
3653	n/a	PyObject datum, selector;
3654	n/a	PyObject (datanext)(PyObject ) = Py_TYPE(data)->tp_iternext;
3655	n/a	PyObject (selectornext)(PyObject ) = Py_TYPE(selectors)->tp_iternext;
3656	n/a	int ok;
3657	n/a
3658	n/a	while (1) {
3659	n/a	/* Steps: get datum, get selector, evaluate selector.
3660	n/a	Order is important (to match the pure python version
3661	n/a	in terms of which input gets a chance to raise an
3662	n/a	exception first).
3663	n/a	*/
3664	n/a
3665	n/a	datum = datanext(data);
3666	n/a	if (datum == NULL)
3667	n/a	return NULL;
3668	n/a
3669	n/a	selector = selectornext(selectors);
3670	n/a	if (selector == NULL) {
3671	n/a	Py_DECREF(datum);
3672	n/a	return NULL;
3673	n/a	}
3674	n/a
3675	n/a	ok = PyObject_IsTrue(selector);
3676	n/a	Py_DECREF(selector);
3677	n/a	if (ok > 0)
3678	n/a	return datum;
3679	n/a	Py_DECREF(datum);
3680	n/a	if (ok < 0)
3681	n/a	return NULL;
3682	n/a	}
3683	n/a	}
3684	n/a
3685	n/a	static PyObject *
3686	n/a	compress_reduce(compressobject *lz)
3687	n/a	{
3688	n/a	return Py_BuildValue("O(OO)", Py_TYPE(lz),
3689	n/a	lz->data, lz->selectors);
3690	n/a	}
3691	n/a
3692	n/a	static PyMethodDef compress_methods[] = {
3693	n/a	{"__reduce__", (PyCFunction)compress_reduce, METH_NOARGS,
3694	n/a	reduce_doc},
3695	n/a	{NULL, NULL} /* sentinel */
3696	n/a	};
3697	n/a
3698	n/a	PyDoc_STRVAR(compress_doc,
3699	n/a	"compress(data, selectors) --> iterator over selected data\n\
3700	n/a	\n\
3701	n/a	Return data elements corresponding to true selector elements.\n\
3702	n/a	Forms a shorter iterator from selected data elements using the\n\
3703	n/a	selectors to choose the data elements.");
3704	n/a
3705	n/a	static PyTypeObject compress_type = {
3706	n/a	PyVarObject_HEAD_INIT(NULL, 0)
3707	n/a	"itertools.compress", /* tp_name */
3708	n/a	sizeof(compressobject), /* tp_basicsize */
3709	n/a	0, /* tp_itemsize */
3710	n/a	/* methods */
3711	n/a	(destructor)compress_dealloc, /* tp_dealloc */
3712	n/a	0, /* tp_print */
3713	n/a	0, /* tp_getattr */
3714	n/a	0, /* tp_setattr */
3715	n/a	0, /* tp_reserved */
3716	n/a	0, /* tp_repr */
3717	n/a	0, /* tp_as_number */
3718	n/a	0, /* tp_as_sequence */
3719	n/a	0, /* tp_as_mapping */
3720	n/a	0, /* tp_hash */
3721	n/a	0, /* tp_call */
3722	n/a	0, /* tp_str */
3723	n/a	PyObject_GenericGetAttr, /* tp_getattro */
3724	n/a	0, /* tp_setattro */
3725	n/a	0, /* tp_as_buffer */
3726	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
3727	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
3728	n/a	compress_doc, /* tp_doc */
3729	n/a	(traverseproc)compress_traverse, /* tp_traverse */
3730	n/a	0, /* tp_clear */
3731	n/a	0, /* tp_richcompare */
3732	n/a	0, /* tp_weaklistoffset */
3733	n/a	PyObject_SelfIter, /* tp_iter */
3734	n/a	(iternextfunc)compress_next, /* tp_iternext */
3735	n/a	compress_methods, /* tp_methods */
3736	n/a	0, /* tp_members */
3737	n/a	0, /* tp_getset */
3738	n/a	0, /* tp_base */
3739	n/a	0, /* tp_dict */
3740	n/a	0, /* tp_descr_get */
3741	n/a	0, /* tp_descr_set */
3742	n/a	0, /* tp_dictoffset */
3743	n/a	0, /* tp_init */
3744	n/a	0, /* tp_alloc */
3745	n/a	compress_new, /* tp_new */
3746	n/a	PyObject_GC_Del, /* tp_free */
3747	n/a	};
3748	n/a
3749	n/a
3750	n/a	/* filterfalse object ************************************************************/
3751	n/a
3752	n/a	typedef struct {
3753	n/a	PyObject_HEAD
3754	n/a	PyObject *func;
3755	n/a	PyObject *it;
3756	n/a	} filterfalseobject;
3757	n/a
3758	n/a	static PyTypeObject filterfalse_type;
3759	n/a
3760	n/a	static PyObject *
3761	n/a	filterfalse_new(PyTypeObject type, PyObject args, PyObject *kwds)
3762	n/a	{
3763	n/a	PyObject func, seq;
3764	n/a	PyObject *it;
3765	n/a	filterfalseobject *lz;
3766	n/a
3767	n/a	if (type == &filterfalse_type &&
3768	n/a	!_PyArg_NoKeywords("filterfalse()", kwds))
3769	n/a	return NULL;
3770	n/a
3771	n/a	if (!PyArg_UnpackTuple(args, "filterfalse", 2, 2, &func, &seq))
3772	n/a	return NULL;
3773	n/a
3774	n/a	/* Get iterator. */
3775	n/a	it = PyObject_GetIter(seq);
3776	n/a	if (it == NULL)
3777	n/a	return NULL;
3778	n/a
3779	n/a	/* create filterfalseobject structure */
3780	n/a	lz = (filterfalseobject *)type->tp_alloc(type, 0);
3781	n/a	if (lz == NULL) {
3782	n/a	Py_DECREF(it);
3783	n/a	return NULL;
3784	n/a	}
3785	n/a	Py_INCREF(func);
3786	n/a	lz->func = func;
3787	n/a	lz->it = it;
3788	n/a
3789	n/a	return (PyObject *)lz;
3790	n/a	}
3791	n/a
3792	n/a	static void
3793	n/a	filterfalse_dealloc(filterfalseobject *lz)
3794	n/a	{
3795	n/a	PyObject_GC_UnTrack(lz);
3796	n/a	Py_XDECREF(lz->func);
3797	n/a	Py_XDECREF(lz->it);
3798	n/a	Py_TYPE(lz)->tp_free(lz);
3799	n/a	}
3800	n/a
3801	n/a	static int
3802	n/a	filterfalse_traverse(filterfalseobject lz, visitproc visit, void arg)
3803	n/a	{
3804	n/a	Py_VISIT(lz->it);
3805	n/a	Py_VISIT(lz->func);
3806	n/a	return 0;
3807	n/a	}
3808	n/a
3809	n/a	static PyObject *
3810	n/a	filterfalse_next(filterfalseobject *lz)
3811	n/a	{
3812	n/a	PyObject *item;
3813	n/a	PyObject *it = lz->it;
3814	n/a	long ok;
3815	n/a	PyObject (iternext)(PyObject *);
3816	n/a
3817	n/a	iternext = *Py_TYPE(it)->tp_iternext;
3818	n/a	for (;;) {
3819	n/a	item = iternext(it);
3820	n/a	if (item == NULL)
3821	n/a	return NULL;
3822	n/a
3823	n/a	if (lz->func == Py_None \|\| lz->func == (PyObject *)&PyBool_Type) {
3824	n/a	ok = PyObject_IsTrue(item);
3825	n/a	} else {
3826	n/a	PyObject *good;
3827	n/a	good = PyObject_CallFunctionObjArgs(lz->func, item, NULL);
3828	n/a	if (good == NULL) {
3829	n/a	Py_DECREF(item);
3830	n/a	return NULL;
3831	n/a	}
3832	n/a	ok = PyObject_IsTrue(good);
3833	n/a	Py_DECREF(good);
3834	n/a	}
3835	n/a	if (ok == 0)
3836	n/a	return item;
3837	n/a	Py_DECREF(item);
3838	n/a	if (ok < 0)
3839	n/a	return NULL;
3840	n/a	}
3841	n/a	}
3842	n/a
3843	n/a	static PyObject *
3844	n/a	filterfalse_reduce(filterfalseobject *lz)
3845	n/a	{
3846	n/a	return Py_BuildValue("O(OO)", Py_TYPE(lz), lz->func, lz->it);
3847	n/a	}
3848	n/a
3849	n/a	static PyMethodDef filterfalse_methods[] = {
3850	n/a	{"__reduce__", (PyCFunction)filterfalse_reduce, METH_NOARGS,
3851	n/a	reduce_doc},
3852	n/a	{NULL, NULL} /* sentinel */
3853	n/a	};
3854	n/a
3855	n/a	PyDoc_STRVAR(filterfalse_doc,
3856	n/a	"filterfalse(function or None, sequence) --> filterfalse object\n\
3857	n/a	\n\
3858	n/a	Return those items of sequence for which function(item) is false.\n\
3859	n/a	If function is None, return the items that are false.");
3860	n/a
3861	n/a	static PyTypeObject filterfalse_type = {
3862	n/a	PyVarObject_HEAD_INIT(NULL, 0)
3863	n/a	"itertools.filterfalse", /* tp_name */
3864	n/a	sizeof(filterfalseobject), /* tp_basicsize */
3865	n/a	0, /* tp_itemsize */
3866	n/a	/* methods */
3867	n/a	(destructor)filterfalse_dealloc, /* tp_dealloc */
3868	n/a	0, /* tp_print */
3869	n/a	0, /* tp_getattr */
3870	n/a	0, /* tp_setattr */
3871	n/a	0, /* tp_reserved */
3872	n/a	0, /* tp_repr */
3873	n/a	0, /* tp_as_number */
3874	n/a	0, /* tp_as_sequence */
3875	n/a	0, /* tp_as_mapping */
3876	n/a	0, /* tp_hash */
3877	n/a	0, /* tp_call */
3878	n/a	0, /* tp_str */
3879	n/a	PyObject_GenericGetAttr, /* tp_getattro */
3880	n/a	0, /* tp_setattro */
3881	n/a	0, /* tp_as_buffer */
3882	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
3883	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
3884	n/a	filterfalse_doc, /* tp_doc */
3885	n/a	(traverseproc)filterfalse_traverse, /* tp_traverse */
3886	n/a	0, /* tp_clear */
3887	n/a	0, /* tp_richcompare */
3888	n/a	0, /* tp_weaklistoffset */
3889	n/a	PyObject_SelfIter, /* tp_iter */
3890	n/a	(iternextfunc)filterfalse_next, /* tp_iternext */
3891	n/a	filterfalse_methods, /* tp_methods */
3892	n/a	0, /* tp_members */
3893	n/a	0, /* tp_getset */
3894	n/a	0, /* tp_base */
3895	n/a	0, /* tp_dict */
3896	n/a	0, /* tp_descr_get */
3897	n/a	0, /* tp_descr_set */
3898	n/a	0, /* tp_dictoffset */
3899	n/a	0, /* tp_init */
3900	n/a	0, /* tp_alloc */
3901	n/a	filterfalse_new, /* tp_new */
3902	n/a	PyObject_GC_Del, /* tp_free */
3903	n/a	};
3904	n/a
3905	n/a
3906	n/a	/* count object ************************************************************/
3907	n/a
3908	n/a	typedef struct {
3909	n/a	PyObject_HEAD
3910	n/a	Py_ssize_t cnt;
3911	n/a	PyObject *long_cnt;
3912	n/a	PyObject *long_step;
3913	n/a	} countobject;
3914	n/a
3915	n/a	/* Counting logic and invariants:
3916	n/a
3917	n/a	fast_mode: when cnt an integer < PY_SSIZE_T_MAX and no step is specified.
3918	n/a
3919	n/a	assert(cnt != PY_SSIZE_T_MAX && long_cnt == NULL && long_step==PyLong(1));
3920	n/a	Advances with: cnt += 1
3921	n/a	When count hits Y_SSIZE_T_MAX, switch to slow_mode.
3922	n/a
3923	n/a	slow_mode: when cnt == PY_SSIZE_T_MAX, step is not int(1), or cnt is a float.
3924	n/a
3925	n/a	assert(cnt == PY_SSIZE_T_MAX && long_cnt != NULL && long_step != NULL);
3926	n/a	All counting is done with python objects (no overflows or underflows).
3927	n/a	Advances with: long_cnt += long_step
3928	n/a	Step may be zero -- effectively a slow version of repeat(cnt).
3929	n/a	Either long_cnt or long_step may be a float, Fraction, or Decimal.
3930	n/a	*/
3931	n/a
3932	n/a	static PyTypeObject count_type;
3933	n/a
3934	n/a	static PyObject *
3935	n/a	count_new(PyTypeObject type, PyObject args, PyObject *kwds)
3936	n/a	{
3937	n/a	countobject *lz;
3938	n/a	int fast_mode;
3939	n/a	Py_ssize_t cnt = 0;
3940	n/a	PyObject *long_cnt = NULL;
3941	n/a	PyObject *long_step = NULL;
3942	n/a	long step;
3943	n/a	static char *kwlist[] = {"start", "step", 0};
3944	n/a
3945	n/a	if (!PyArg_ParseTupleAndKeywords(args, kwds, "\|OO:count",
3946	n/a	kwlist, &long_cnt, &long_step))
3947	n/a	return NULL;
3948	n/a
3949	n/a	if ((long_cnt != NULL && !PyNumber_Check(long_cnt)) \|\|
3950	n/a	(long_step != NULL && !PyNumber_Check(long_step))) {
3951	n/a	PyErr_SetString(PyExc_TypeError, "a number is required");
3952	n/a	return NULL;
3953	n/a	}
3954	n/a
3955	n/a	fast_mode = (long_cnt == NULL \|\| PyLong_Check(long_cnt)) &&
3956	n/a	(long_step == NULL \|\| PyLong_Check(long_step));
3957	n/a
3958	n/a	/* If not specified, start defaults to 0 */
3959	n/a	if (long_cnt != NULL) {
3960	n/a	if (fast_mode) {
3961	n/a	assert(PyLong_Check(long_cnt));
3962	n/a	cnt = PyLong_AsSsize_t(long_cnt);
3963	n/a	if (cnt == -1 && PyErr_Occurred()) {
3964	n/a	PyErr_Clear();
3965	n/a	fast_mode = 0;
3966	n/a	}
3967	n/a	}
3968	n/a	Py_INCREF(long_cnt);
3969	n/a	} else {
3970	n/a	cnt = 0;
3971	n/a	long_cnt = PyLong_FromLong(0);
3972	n/a	if (long_cnt == NULL) {
3973	n/a	return NULL;
3974	n/a	}
3975	n/a	}
3976	n/a
3977	n/a	/* If not specified, step defaults to 1 */
3978	n/a	if (long_step == NULL) {
3979	n/a	long_step = PyLong_FromLong(1);
3980	n/a	if (long_step == NULL) {
3981	n/a	Py_DECREF(long_cnt);
3982	n/a	return NULL;
3983	n/a	}
3984	n/a	} else
3985	n/a	Py_INCREF(long_step);
3986	n/a
3987	n/a	assert(long_cnt != NULL && long_step != NULL);
3988	n/a
3989	n/a	/* Fast mode only works when the step is 1 */
3990	n/a	if (fast_mode) {
3991	n/a	assert(PyLong_Check(long_step));
3992	n/a	step = PyLong_AsLong(long_step);
3993	n/a	if (step != 1) {
3994	n/a	fast_mode = 0;
3995	n/a	if (step == -1 && PyErr_Occurred())
3996	n/a	PyErr_Clear();
3997	n/a	}
3998	n/a	}
3999	n/a
4000	n/a	if (fast_mode)
4001	n/a	Py_CLEAR(long_cnt);
4002	n/a	else
4003	n/a	cnt = PY_SSIZE_T_MAX;
4004	n/a
4005	n/a	assert((cnt != PY_SSIZE_T_MAX && long_cnt == NULL && fast_mode) \|\|
4006	n/a	(cnt == PY_SSIZE_T_MAX && long_cnt != NULL && !fast_mode));
4007	n/a	assert(!fast_mode \|\|
4008	n/a	(PyLong_Check(long_step) && PyLong_AS_LONG(long_step) == 1));
4009	n/a
4010	n/a	/* create countobject structure */
4011	n/a	lz = (countobject *)type->tp_alloc(type, 0);
4012	n/a	if (lz == NULL) {
4013	n/a	Py_XDECREF(long_cnt);
4014	n/a	return NULL;
4015	n/a	}
4016	n/a	lz->cnt = cnt;
4017	n/a	lz->long_cnt = long_cnt;
4018	n/a	lz->long_step = long_step;
4019	n/a
4020	n/a	return (PyObject *)lz;
4021	n/a	}
4022	n/a
4023	n/a	static void
4024	n/a	count_dealloc(countobject *lz)
4025	n/a	{
4026	n/a	PyObject_GC_UnTrack(lz);
4027	n/a	Py_XDECREF(lz->long_cnt);
4028	n/a	Py_XDECREF(lz->long_step);
4029	n/a	Py_TYPE(lz)->tp_free(lz);
4030	n/a	}
4031	n/a
4032	n/a	static int
4033	n/a	count_traverse(countobject lz, visitproc visit, void arg)
4034	n/a	{
4035	n/a	Py_VISIT(lz->long_cnt);
4036	n/a	Py_VISIT(lz->long_step);
4037	n/a	return 0;
4038	n/a	}
4039	n/a
4040	n/a	static PyObject *
4041	n/a	count_nextlong(countobject *lz)
4042	n/a	{
4043	n/a	PyObject *long_cnt;
4044	n/a	PyObject *stepped_up;
4045	n/a
4046	n/a	long_cnt = lz->long_cnt;
4047	n/a	if (long_cnt == NULL) {
4048	n/a	/* Switch to slow_mode */
4049	n/a	long_cnt = PyLong_FromSsize_t(PY_SSIZE_T_MAX);
4050	n/a	if (long_cnt == NULL)
4051	n/a	return NULL;
4052	n/a	}
4053	n/a	assert(lz->cnt == PY_SSIZE_T_MAX && long_cnt != NULL);
4054	n/a
4055	n/a	stepped_up = PyNumber_Add(long_cnt, lz->long_step);
4056	n/a	if (stepped_up == NULL)
4057	n/a	return NULL;
4058	n/a	lz->long_cnt = stepped_up;
4059	n/a	return long_cnt;
4060	n/a	}
4061	n/a
4062	n/a	static PyObject *
4063	n/a	count_next(countobject *lz)
4064	n/a	{
4065	n/a	if (lz->cnt == PY_SSIZE_T_MAX)
4066	n/a	return count_nextlong(lz);
4067	n/a	return PyLong_FromSsize_t(lz->cnt++);
4068	n/a	}
4069	n/a
4070	n/a	static PyObject *
4071	n/a	count_repr(countobject *lz)
4072	n/a	{
4073	n/a	if (lz->cnt != PY_SSIZE_T_MAX)
4074	n/a	return PyUnicode_FromFormat("count(%zd)", lz->cnt);
4075	n/a
4076	n/a	if (PyLong_Check(lz->long_step)) {
4077	n/a	long step = PyLong_AsLong(lz->long_step);
4078	n/a	if (step == -1 && PyErr_Occurred()) {
4079	n/a	PyErr_Clear();
4080	n/a	}
4081	n/a	if (step == 1) {
4082	n/a	/* Don't display step when it is an integer equal to 1 */
4083	n/a	return PyUnicode_FromFormat("count(%R)", lz->long_cnt);
4084	n/a	}
4085	n/a	}
4086	n/a	return PyUnicode_FromFormat("count(%R, %R)",
4087	n/a	lz->long_cnt, lz->long_step);
4088	n/a	}
4089	n/a
4090	n/a	static PyObject *
4091	n/a	count_reduce(countobject *lz)
4092	n/a	{
4093	n/a	if (lz->cnt == PY_SSIZE_T_MAX)
4094	n/a	return Py_BuildValue("O(OO)", Py_TYPE(lz), lz->long_cnt, lz->long_step);
4095	n/a	return Py_BuildValue("O(n)", Py_TYPE(lz), lz->cnt);
4096	n/a	}
4097	n/a
4098	n/a	static PyMethodDef count_methods[] = {
4099	n/a	{"__reduce__", (PyCFunction)count_reduce, METH_NOARGS,
4100	n/a	reduce_doc},
4101	n/a	{NULL, NULL} /* sentinel */
4102	n/a	};
4103	n/a
4104	n/a	PyDoc_STRVAR(count_doc,
4105	n/a	"count(start=0, step=1) --> count object\n\
4106	n/a	\n\
4107	n/a	Return a count object whose .__next__() method returns consecutive values.\n\
4108	n/a	Equivalent to:\n\n\
4109	n/a	def count(firstval=0, step=1):\n\
4110	n/a	x = firstval\n\
4111	n/a	while 1:\n\
4112	n/a	yield x\n\
4113	n/a	x += step\n");
4114	n/a
4115	n/a	static PyTypeObject count_type = {
4116	n/a	PyVarObject_HEAD_INIT(NULL, 0)
4117	n/a	"itertools.count", /* tp_name */
4118	n/a	sizeof(countobject), /* tp_basicsize */
4119	n/a	0, /* tp_itemsize */
4120	n/a	/* methods */
4121	n/a	(destructor)count_dealloc, /* tp_dealloc */
4122	n/a	0, /* tp_print */
4123	n/a	0, /* tp_getattr */
4124	n/a	0, /* tp_setattr */
4125	n/a	0, /* tp_reserved */
4126	n/a	(reprfunc)count_repr, /* tp_repr */
4127	n/a	0, /* tp_as_number */
4128	n/a	0, /* tp_as_sequence */
4129	n/a	0, /* tp_as_mapping */
4130	n/a	0, /* tp_hash */
4131	n/a	0, /* tp_call */
4132	n/a	0, /* tp_str */
4133	n/a	PyObject_GenericGetAttr, /* tp_getattro */
4134	n/a	0, /* tp_setattro */
4135	n/a	0, /* tp_as_buffer */
4136	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
4137	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
4138	n/a	count_doc, /* tp_doc */
4139	n/a	(traverseproc)count_traverse, /* tp_traverse */
4140	n/a	0, /* tp_clear */
4141	n/a	0, /* tp_richcompare */
4142	n/a	0, /* tp_weaklistoffset */
4143	n/a	PyObject_SelfIter, /* tp_iter */
4144	n/a	(iternextfunc)count_next, /* tp_iternext */
4145	n/a	count_methods, /* tp_methods */
4146	n/a	0, /* tp_members */
4147	n/a	0, /* tp_getset */
4148	n/a	0, /* tp_base */
4149	n/a	0, /* tp_dict */
4150	n/a	0, /* tp_descr_get */
4151	n/a	0, /* tp_descr_set */
4152	n/a	0, /* tp_dictoffset */
4153	n/a	0, /* tp_init */
4154	n/a	0, /* tp_alloc */
4155	n/a	count_new, /* tp_new */
4156	n/a	PyObject_GC_Del, /* tp_free */
4157	n/a	};
4158	n/a
4159	n/a
4160	n/a	/* repeat object ************************************************************/
4161	n/a
4162	n/a	typedef struct {
4163	n/a	PyObject_HEAD
4164	n/a	PyObject *element;
4165	n/a	Py_ssize_t cnt;
4166	n/a	} repeatobject;
4167	n/a
4168	n/a	static PyTypeObject repeat_type;
4169	n/a
4170	n/a	static PyObject *
4171	n/a	repeat_new(PyTypeObject type, PyObject args, PyObject *kwds)
4172	n/a	{
4173	n/a	repeatobject *ro;
4174	n/a	PyObject *element;
4175	n/a	Py_ssize_t cnt = -1, n_kwds = 0;
4176	n/a	static char *kwargs[] = {"object", "times", NULL};
4177	n/a
4178	n/a	if (!PyArg_ParseTupleAndKeywords(args, kwds, "O\|n:repeat", kwargs,
4179	n/a	&element, &cnt))
4180	n/a	return NULL;
4181	n/a
4182	n/a	if (kwds != NULL)
4183	n/a	n_kwds = PyDict_GET_SIZE(kwds);
4184	n/a	/* Does user supply times argument? */
4185	n/a	if ((PyTuple_Size(args) + n_kwds == 2) && cnt < 0)
4186	n/a	cnt = 0;
4187	n/a
4188	n/a	ro = (repeatobject *)type->tp_alloc(type, 0);
4189	n/a	if (ro == NULL)
4190	n/a	return NULL;
4191	n/a	Py_INCREF(element);
4192	n/a	ro->element = element;
4193	n/a	ro->cnt = cnt;
4194	n/a	return (PyObject *)ro;
4195	n/a	}
4196	n/a
4197	n/a	static void
4198	n/a	repeat_dealloc(repeatobject *ro)
4199	n/a	{
4200	n/a	PyObject_GC_UnTrack(ro);
4201	n/a	Py_XDECREF(ro->element);
4202	n/a	Py_TYPE(ro)->tp_free(ro);
4203	n/a	}
4204	n/a
4205	n/a	static int
4206	n/a	repeat_traverse(repeatobject ro, visitproc visit, void arg)
4207	n/a	{
4208	n/a	Py_VISIT(ro->element);
4209	n/a	return 0;
4210	n/a	}
4211	n/a
4212	n/a	static PyObject *
4213	n/a	repeat_next(repeatobject *ro)
4214	n/a	{
4215	n/a	if (ro->cnt == 0)
4216	n/a	return NULL;
4217	n/a	if (ro->cnt > 0)
4218	n/a	ro->cnt--;
4219	n/a	Py_INCREF(ro->element);
4220	n/a	return ro->element;
4221	n/a	}
4222	n/a
4223	n/a	static PyObject *
4224	n/a	repeat_repr(repeatobject *ro)
4225	n/a	{
4226	n/a	if (ro->cnt == -1)
4227	n/a	return PyUnicode_FromFormat("repeat(%R)", ro->element);
4228	n/a	else
4229	n/a	return PyUnicode_FromFormat("repeat(%R, %zd)", ro->element, ro->cnt);
4230	n/a	}
4231	n/a
4232	n/a	static PyObject *
4233	n/a	repeat_len(repeatobject *ro)
4234	n/a	{
4235	n/a	if (ro->cnt == -1) {
4236	n/a	PyErr_SetString(PyExc_TypeError, "len() of unsized object");
4237	n/a	return NULL;
4238	n/a	}
4239	n/a	return PyLong_FromSize_t(ro->cnt);
4240	n/a	}
4241	n/a
4242	n/a	PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
4243	n/a
4244	n/a	static PyObject *
4245	n/a	repeat_reduce(repeatobject *ro)
4246	n/a	{
4247	n/a	/* unpickle this so that a new repeat iterator is constructed with an
4248	n/a	* object, then call __setstate__ on it to set cnt
4249	n/a	*/
4250	n/a	if (ro->cnt >= 0)
4251	n/a	return Py_BuildValue("O(On)", Py_TYPE(ro), ro->element, ro->cnt);
4252	n/a	else
4253	n/a	return Py_BuildValue("O(O)", Py_TYPE(ro), ro->element);
4254	n/a	}
4255	n/a
4256	n/a	static PyMethodDef repeat_methods[] = {
4257	n/a	{"__length_hint__", (PyCFunction)repeat_len, METH_NOARGS, length_hint_doc},
4258	n/a	{"__reduce__", (PyCFunction)repeat_reduce, METH_NOARGS, reduce_doc},
4259	n/a	{NULL, NULL} /* sentinel */
4260	n/a	};
4261	n/a
4262	n/a	PyDoc_STRVAR(repeat_doc,
4263	n/a	"repeat(object [,times]) -> create an iterator which returns the object\n\
4264	n/a	for the specified number of times. If not specified, returns the object\n\
4265	n/a	endlessly.");
4266	n/a
4267	n/a	static PyTypeObject repeat_type = {
4268	n/a	PyVarObject_HEAD_INIT(NULL, 0)
4269	n/a	"itertools.repeat", /* tp_name */
4270	n/a	sizeof(repeatobject), /* tp_basicsize */
4271	n/a	0, /* tp_itemsize */
4272	n/a	/* methods */
4273	n/a	(destructor)repeat_dealloc, /* tp_dealloc */
4274	n/a	0, /* tp_print */
4275	n/a	0, /* tp_getattr */
4276	n/a	0, /* tp_setattr */
4277	n/a	0, /* tp_reserved */
4278	n/a	(reprfunc)repeat_repr, /* tp_repr */
4279	n/a	0, /* tp_as_number */
4280	n/a	0, /* tp_as_sequence */
4281	n/a	0, /* tp_as_mapping */
4282	n/a	0, /* tp_hash */
4283	n/a	0, /* tp_call */
4284	n/a	0, /* tp_str */
4285	n/a	PyObject_GenericGetAttr, /* tp_getattro */
4286	n/a	0, /* tp_setattro */
4287	n/a	0, /* tp_as_buffer */
4288	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
4289	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
4290	n/a	repeat_doc, /* tp_doc */
4291	n/a	(traverseproc)repeat_traverse, /* tp_traverse */
4292	n/a	0, /* tp_clear */
4293	n/a	0, /* tp_richcompare */
4294	n/a	0, /* tp_weaklistoffset */
4295	n/a	PyObject_SelfIter, /* tp_iter */
4296	n/a	(iternextfunc)repeat_next, /* tp_iternext */
4297	n/a	repeat_methods, /* tp_methods */
4298	n/a	0, /* tp_members */
4299	n/a	0, /* tp_getset */
4300	n/a	0, /* tp_base */
4301	n/a	0, /* tp_dict */
4302	n/a	0, /* tp_descr_get */
4303	n/a	0, /* tp_descr_set */
4304	n/a	0, /* tp_dictoffset */
4305	n/a	0, /* tp_init */
4306	n/a	0, /* tp_alloc */
4307	n/a	repeat_new, /* tp_new */
4308	n/a	PyObject_GC_Del, /* tp_free */
4309	n/a	};
4310	n/a
4311	n/a	/* ziplongest object *********************************************************/
4312	n/a
4313	n/a	typedef struct {
4314	n/a	PyObject_HEAD
4315	n/a	Py_ssize_t tuplesize;
4316	n/a	Py_ssize_t numactive;
4317	n/a	PyObject ittuple; / tuple of iterators */
4318	n/a	PyObject *result;
4319	n/a	PyObject *fillvalue;
4320	n/a	} ziplongestobject;
4321	n/a
4322	n/a	static PyTypeObject ziplongest_type;
4323	n/a
4324	n/a	static PyObject *
4325	n/a	zip_longest_new(PyTypeObject type, PyObject args, PyObject *kwds)
4326	n/a	{
4327	n/a	ziplongestobject *lz;
4328	n/a	Py_ssize_t i;
4329	n/a	PyObject ittuple; / tuple of iterators */
4330	n/a	PyObject *result;
4331	n/a	PyObject *fillvalue = Py_None;
4332	n/a	Py_ssize_t tuplesize = PySequence_Length(args);
4333	n/a
4334	n/a	if (kwds != NULL && PyDict_CheckExact(kwds) && PyDict_GET_SIZE(kwds) > 0) {
4335	n/a	fillvalue = PyDict_GetItemString(kwds, "fillvalue");
4336	n/a	if (fillvalue == NULL \|\| PyDict_GET_SIZE(kwds) > 1) {
4337	n/a	PyErr_SetString(PyExc_TypeError,
4338	n/a	"zip_longest() got an unexpected keyword argument");
4339	n/a	return NULL;
4340	n/a	}
4341	n/a	}
4342	n/a
4343	n/a	/* args must be a tuple */
4344	n/a	assert(PyTuple_Check(args));
4345	n/a
4346	n/a	/* obtain iterators */
4347	n/a	ittuple = PyTuple_New(tuplesize);
4348	n/a	if (ittuple == NULL)
4349	n/a	return NULL;
4350	n/a	for (i=0; i < tuplesize; i++) {
4351	n/a	PyObject *item = PyTuple_GET_ITEM(args, i);
4352	n/a	PyObject *it = PyObject_GetIter(item);
4353	n/a	if (it == NULL) {
4354	n/a	if (PyErr_ExceptionMatches(PyExc_TypeError))
4355	n/a	PyErr_Format(PyExc_TypeError,
4356	n/a	"zip_longest argument #%zd must support iteration",
4357	n/a	i+1);
4358	n/a	Py_DECREF(ittuple);
4359	n/a	return NULL;
4360	n/a	}
4361	n/a	PyTuple_SET_ITEM(ittuple, i, it);
4362	n/a	}
4363	n/a
4364	n/a	/* create a result holder */
4365	n/a	result = PyTuple_New(tuplesize);
4366	n/a	if (result == NULL) {
4367	n/a	Py_DECREF(ittuple);
4368	n/a	return NULL;
4369	n/a	}
4370	n/a	for (i=0 ; i < tuplesize ; i++) {
4371	n/a	Py_INCREF(Py_None);
4372	n/a	PyTuple_SET_ITEM(result, i, Py_None);
4373	n/a	}
4374	n/a
4375	n/a	/* create ziplongestobject structure */
4376	n/a	lz = (ziplongestobject *)type->tp_alloc(type, 0);
4377	n/a	if (lz == NULL) {
4378	n/a	Py_DECREF(ittuple);
4379	n/a	Py_DECREF(result);
4380	n/a	return NULL;
4381	n/a	}
4382	n/a	lz->ittuple = ittuple;
4383	n/a	lz->tuplesize = tuplesize;
4384	n/a	lz->numactive = tuplesize;
4385	n/a	lz->result = result;
4386	n/a	Py_INCREF(fillvalue);
4387	n/a	lz->fillvalue = fillvalue;
4388	n/a	return (PyObject *)lz;
4389	n/a	}
4390	n/a
4391	n/a	static void
4392	n/a	zip_longest_dealloc(ziplongestobject *lz)
4393	n/a	{
4394	n/a	PyObject_GC_UnTrack(lz);
4395	n/a	Py_XDECREF(lz->ittuple);
4396	n/a	Py_XDECREF(lz->result);
4397	n/a	Py_XDECREF(lz->fillvalue);
4398	n/a	Py_TYPE(lz)->tp_free(lz);
4399	n/a	}
4400	n/a
4401	n/a	static int
4402	n/a	zip_longest_traverse(ziplongestobject lz, visitproc visit, void arg)
4403	n/a	{
4404	n/a	Py_VISIT(lz->ittuple);
4405	n/a	Py_VISIT(lz->result);
4406	n/a	Py_VISIT(lz->fillvalue);
4407	n/a	return 0;
4408	n/a	}
4409	n/a
4410	n/a	static PyObject *
4411	n/a	zip_longest_next(ziplongestobject *lz)
4412	n/a	{
4413	n/a	Py_ssize_t i;
4414	n/a	Py_ssize_t tuplesize = lz->tuplesize;
4415	n/a	PyObject *result = lz->result;
4416	n/a	PyObject *it;
4417	n/a	PyObject *item;
4418	n/a	PyObject *olditem;
4419	n/a
4420	n/a	if (tuplesize == 0)
4421	n/a	return NULL;
4422	n/a	if (lz->numactive == 0)
4423	n/a	return NULL;
4424	n/a	if (Py_REFCNT(result) == 1) {
4425	n/a	Py_INCREF(result);
4426	n/a	for (i=0 ; i < tuplesize ; i++) {
4427	n/a	it = PyTuple_GET_ITEM(lz->ittuple, i);
4428	n/a	if (it == NULL) {
4429	n/a	Py_INCREF(lz->fillvalue);
4430	n/a	item = lz->fillvalue;
4431	n/a	} else {
4432	n/a	item = PyIter_Next(it);
4433	n/a	if (item == NULL) {
4434	n/a	lz->numactive -= 1;
4435	n/a	if (lz->numactive == 0 \|\| PyErr_Occurred()) {
4436	n/a	lz->numactive = 0;
4437	n/a	Py_DECREF(result);
4438	n/a	return NULL;
4439	n/a	} else {
4440	n/a	Py_INCREF(lz->fillvalue);
4441	n/a	item = lz->fillvalue;
4442	n/a	PyTuple_SET_ITEM(lz->ittuple, i, NULL);
4443	n/a	Py_DECREF(it);
4444	n/a	}
4445	n/a	}
4446	n/a	}
4447	n/a	olditem = PyTuple_GET_ITEM(result, i);
4448	n/a	PyTuple_SET_ITEM(result, i, item);
4449	n/a	Py_DECREF(olditem);
4450	n/a	}
4451	n/a	} else {
4452	n/a	result = PyTuple_New(tuplesize);
4453	n/a	if (result == NULL)
4454	n/a	return NULL;
4455	n/a	for (i=0 ; i < tuplesize ; i++) {
4456	n/a	it = PyTuple_GET_ITEM(lz->ittuple, i);
4457	n/a	if (it == NULL) {
4458	n/a	Py_INCREF(lz->fillvalue);
4459	n/a	item = lz->fillvalue;
4460	n/a	} else {
4461	n/a	item = PyIter_Next(it);
4462	n/a	if (item == NULL) {
4463	n/a	lz->numactive -= 1;
4464	n/a	if (lz->numactive == 0 \|\| PyErr_Occurred()) {
4465	n/a	lz->numactive = 0;
4466	n/a	Py_DECREF(result);
4467	n/a	return NULL;
4468	n/a	} else {
4469	n/a	Py_INCREF(lz->fillvalue);
4470	n/a	item = lz->fillvalue;
4471	n/a	PyTuple_SET_ITEM(lz->ittuple, i, NULL);
4472	n/a	Py_DECREF(it);
4473	n/a	}
4474	n/a	}
4475	n/a	}
4476	n/a	PyTuple_SET_ITEM(result, i, item);
4477	n/a	}
4478	n/a	}
4479	n/a	return result;
4480	n/a	}
4481	n/a
4482	n/a	static PyObject *
4483	n/a	zip_longest_reduce(ziplongestobject *lz)
4484	n/a	{
4485	n/a
4486	n/a	/* Create a new tuple with empty sequences where appropriate to pickle.
4487	n/a	* Then use setstate to set the fillvalue
4488	n/a	*/
4489	n/a	int i;
4490	n/a	PyObject *args = PyTuple_New(PyTuple_GET_SIZE(lz->ittuple));
4491	n/a
4492	n/a	if (args == NULL)
4493	n/a	return NULL;
4494	n/a	for (i=0; i<PyTuple_GET_SIZE(lz->ittuple); i++) {
4495	n/a	PyObject *elem = PyTuple_GET_ITEM(lz->ittuple, i);
4496	n/a	if (elem == NULL) {
4497	n/a	elem = PyTuple_New(0);
4498	n/a	if (elem == NULL) {
4499	n/a	Py_DECREF(args);
4500	n/a	return NULL;
4501	n/a	}
4502	n/a	} else
4503	n/a	Py_INCREF(elem);
4504	n/a	PyTuple_SET_ITEM(args, i, elem);
4505	n/a	}
4506	n/a	return Py_BuildValue("ONO", Py_TYPE(lz), args, lz->fillvalue);
4507	n/a	}
4508	n/a
4509	n/a	static PyObject *
4510	n/a	zip_longest_setstate(ziplongestobject lz, PyObject state)
4511	n/a	{
4512	n/a	Py_INCREF(state);
4513	n/a	Py_XSETREF(lz->fillvalue, state);
4514	n/a	Py_RETURN_NONE;
4515	n/a	}
4516	n/a
4517	n/a	static PyMethodDef zip_longest_methods[] = {
4518	n/a	{"__reduce__", (PyCFunction)zip_longest_reduce, METH_NOARGS,
4519	n/a	reduce_doc},
4520	n/a	{"__setstate__", (PyCFunction)zip_longest_setstate, METH_O,
4521	n/a	setstate_doc},
4522	n/a	{NULL, NULL} /* sentinel */
4523	n/a	};
4524	n/a
4525	n/a	PyDoc_STRVAR(zip_longest_doc,
4526	n/a	"zip_longest(iter1 [,iter2 [...]], [fillvalue=None]) --> zip_longest object\n\
4527	n/a	\n\
4528	n/a	Return a zip_longest object whose .__next__() method returns a tuple where\n\
4529	n/a	the i-th element comes from the i-th iterable argument. The .__next__()\n\
4530	n/a	method continues until the longest iterable in the argument sequence\n\
4531	n/a	is exhausted and then it raises StopIteration. When the shorter iterables\n\
4532	n/a	are exhausted, the fillvalue is substituted in their place. The fillvalue\n\
4533	n/a	defaults to None or can be specified by a keyword argument.\n\
4534	n/a	");
4535	n/a
4536	n/a	static PyTypeObject ziplongest_type = {
4537	n/a	PyVarObject_HEAD_INIT(NULL, 0)
4538	n/a	"itertools.zip_longest", /* tp_name */
4539	n/a	sizeof(ziplongestobject), /* tp_basicsize */
4540	n/a	0, /* tp_itemsize */
4541	n/a	/* methods */
4542	n/a	(destructor)zip_longest_dealloc, /* tp_dealloc */
4543	n/a	0, /* tp_print */
4544	n/a	0, /* tp_getattr */
4545	n/a	0, /* tp_setattr */
4546	n/a	0, /* tp_reserved */
4547	n/a	0, /* tp_repr */
4548	n/a	0, /* tp_as_number */
4549	n/a	0, /* tp_as_sequence */
4550	n/a	0, /* tp_as_mapping */
4551	n/a	0, /* tp_hash */
4552	n/a	0, /* tp_call */
4553	n/a	0, /* tp_str */
4554	n/a	PyObject_GenericGetAttr, /* tp_getattro */
4555	n/a	0, /* tp_setattro */
4556	n/a	0, /* tp_as_buffer */
4557	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
4558	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
4559	n/a	zip_longest_doc, /* tp_doc */
4560	n/a	(traverseproc)zip_longest_traverse, /* tp_traverse */
4561	n/a	0, /* tp_clear */
4562	n/a	0, /* tp_richcompare */
4563	n/a	0, /* tp_weaklistoffset */
4564	n/a	PyObject_SelfIter, /* tp_iter */
4565	n/a	(iternextfunc)zip_longest_next, /* tp_iternext */
4566	n/a	zip_longest_methods, /* tp_methods */
4567	n/a	0, /* tp_members */
4568	n/a	0, /* tp_getset */
4569	n/a	0, /* tp_base */
4570	n/a	0, /* tp_dict */
4571	n/a	0, /* tp_descr_get */
4572	n/a	0, /* tp_descr_set */
4573	n/a	0, /* tp_dictoffset */
4574	n/a	0, /* tp_init */
4575	n/a	0, /* tp_alloc */
4576	n/a	zip_longest_new, /* tp_new */
4577	n/a	PyObject_GC_Del, /* tp_free */
4578	n/a	};
4579	n/a
4580	n/a	/* module level code ********************************************************/
4581	n/a
4582	n/a	PyDoc_STRVAR(module_doc,
4583	n/a	"Functional tools for creating and using iterators.\n\
4584	n/a	\n\
4585	n/a	Infinite iterators:\n\
4586	n/a	count(start=0, step=1) --> start, start+step, start+2*step, ...\n\
4587	n/a	cycle(p) --> p0, p1, ... plast, p0, p1, ...\n\
4588	n/a	repeat(elem [,n]) --> elem, elem, elem, ... endlessly or up to n times\n\
4589	n/a	\n\
4590	n/a	Iterators terminating on the shortest input sequence:\n\
4591	n/a	accumulate(p[, func]) --> p0, p0+p1, p0+p1+p2\n\
4592	n/a	chain(p, q, ...) --> p0, p1, ... plast, q0, q1, ... \n\
4593	n/a	chain.from_iterable([p, q, ...]) --> p0, p1, ... plast, q0, q1, ... \n\
4594	n/a	compress(data, selectors) --> (d[0] if s[0]), (d[1] if s[1]), ...\n\
4595	n/a	dropwhile(pred, seq) --> seq[n], seq[n+1], starting when pred fails\n\
4596	n/a	groupby(iterable[, keyfunc]) --> sub-iterators grouped by value of keyfunc(v)\n\
4597	n/a	filterfalse(pred, seq) --> elements of seq where pred(elem) is False\n\
4598	n/a	islice(seq, [start,] stop [, step]) --> elements from\n\
4599	n/a	seq[start:stop:step]\n\
4600	n/a	starmap(fun, seq) --> fun(seq[0]), fun(seq[1]), ...\n\
4601	n/a	tee(it, n=2) --> (it1, it2 , ... itn) splits one iterator into n\n\
4602	n/a	takewhile(pred, seq) --> seq[0], seq[1], until pred fails\n\
4603	n/a	zip_longest(p, q, ...) --> (p[0], q[0]), (p[1], q[1]), ... \n\
4604	n/a	\n\
4605	n/a	Combinatoric generators:\n\
4606	n/a	product(p, q, ... [repeat=1]) --> cartesian product\n\
4607	n/a	permutations(p[, r])\n\
4608	n/a	combinations(p, r)\n\
4609	n/a	combinations_with_replacement(p, r)\n\
4610	n/a	");
4611	n/a
4612	n/a
4613	n/a	static PyMethodDef module_methods[] = {
4614	n/a	{"tee", (PyCFunction)tee, METH_VARARGS, tee_doc},
4615	n/a	{NULL, NULL} /* sentinel */
4616	n/a	};
4617	n/a
4618	n/a
4619	n/a	static struct PyModuleDef itertoolsmodule = {
4620	n/a	PyModuleDef_HEAD_INIT,
4621	n/a	"itertools",
4622	n/a	module_doc,
4623	n/a	-1,
4624	n/a	module_methods,
4625	n/a	NULL,
4626	n/a	NULL,
4627	n/a	NULL,
4628	n/a	NULL
4629	n/a	};
4630	n/a
4631	n/a	PyMODINIT_FUNC
4632	n/a	PyInit_itertools(void)
4633	n/a	{
4634	n/a	int i;
4635	n/a	PyObject *m;
4636	n/a	char *name;
4637	n/a	PyTypeObject *typelist[] = {
4638	n/a	&accumulate_type,
4639	n/a	&combinations_type,
4640	n/a	&cwr_type,
4641	n/a	&cycle_type,
4642	n/a	&dropwhile_type,
4643	n/a	&takewhile_type,
4644	n/a	&islice_type,
4645	n/a	&starmap_type,
4646	n/a	&chain_type,
4647	n/a	&compress_type,
4648	n/a	&filterfalse_type,
4649	n/a	&count_type,
4650	n/a	&ziplongest_type,
4651	n/a	&permutations_type,
4652	n/a	&product_type,
4653	n/a	&repeat_type,
4654	n/a	&groupby_type,
4655	n/a	&_grouper_type,
4656	n/a	&tee_type,
4657	n/a	&teedataobject_type,
4658	n/a	NULL
4659	n/a	};
4660	n/a
4661	n/a	Py_TYPE(&teedataobject_type) = &PyType_Type;
4662	n/a	m = PyModule_Create(&itertoolsmodule);
4663	n/a	if (m == NULL)
4664	n/a	return NULL;
4665	n/a
4666	n/a	for (i=0 ; typelist[i] != NULL ; i++) {
4667	n/a	if (PyType_Ready(typelist[i]) < 0)
4668	n/a	return NULL;
4669	n/a	name = strchr(typelist[i]->tp_name, '.');
4670	n/a	assert (name != NULL);
4671	n/a	Py_INCREF(typelist[i]);
4672	n/a	PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
4673	n/a	}
4674	n/a
4675	n/a	return m;
4676	n/a	}