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