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