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