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