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 int

   405 teedataobject_clear(teedataobject *tdo)

   406 {

   407 	int i;

   408 	Py_CLEAR(tdo->it);

   409 	for (i=0 ; i<tdo->numread ; i++)

   410 		Py_CLEAR(tdo->values[i]);

   411 	Py_CLEAR(tdo->nextlink);

   412 	return 0;

   413 }

   414 

   415 static void

   416 teedataobject_dealloc(teedataobject *tdo)

   417 {

   418 	PyObject_GC_UnTrack(tdo);

   419 	teedataobject_clear(tdo);

   420 	PyObject_GC_Del(tdo);

   421 }

   422 

   423 PyDoc_STRVAR(teedataobject_doc, "Data container common to multiple tee objects.");

   424 

   425 static PyTypeObject teedataobject_type = {

   426 	PyVarObject_HEAD_INIT(0, 0)	/* Must fill in type value later */

   427 	"itertools.tee_dataobject",		/* tp_name */

   428 	sizeof(teedataobject),			/* tp_basicsize */

   429 	0,					/* tp_itemsize */

   430 	/* methods */

   431 	(destructor)teedataobject_dealloc,	/* tp_dealloc */

   432 	0,					/* tp_print */

   433 	0,					/* tp_getattr */

   434 	0,					/* tp_setattr */

   435 	0,					/* tp_compare */

   436 	0,					/* tp_repr */

   437 	0,					/* tp_as_number */

   438 	0,					/* tp_as_sequence */

   439 	0,					/* tp_as_mapping */

   440 	0,					/* tp_hash */

   441 	0,					/* tp_call */

   442 	0,					/* tp_str */

   443 	PyObject_GenericGetAttr,		/* tp_getattro */

   444 	0,					/* tp_setattro */

   445 	0,					/* tp_as_buffer */

   446 	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,	/* tp_flags */

   447 	teedataobject_doc,			/* tp_doc */

   448 	(traverseproc)teedataobject_traverse,	/* tp_traverse */

   449 	(inquiry)teedataobject_clear,		/* tp_clear */

   450 	0,					/* tp_richcompare */

   451 	0,					/* tp_weaklistoffset */

   452 	0,					/* tp_iter */

   453 	0,					/* tp_iternext */

   454 	0,					/* tp_methods */

   455 	0,					/* tp_members */

   456 	0,					/* tp_getset */

   457 	0,					/* tp_base */

   458 	0,					/* tp_dict */

   459 	0,					/* tp_descr_get */

   460 	0,					/* tp_descr_set */

   461 	0,					/* tp_dictoffset */

   462 	0,					/* tp_init */

   463 	0,					/* tp_alloc */

   464 	0,					/* tp_new */

   465 	PyObject_GC_Del,			/* tp_free */

   466 };

   467 

   468 

   469 static PyTypeObject tee_type;

   470 

   471 static PyObject *

   472 tee_next(teeobject *to)

   473 {

   474 	PyObject *value, *link;

   475 

   476 	if (to->index >= LINKCELLS) {

   477 		link = teedataobject_jumplink(to->dataobj);

   478 		Py_DECREF(to->dataobj);

   479 		to->dataobj = (teedataobject *)link;

   480 		to->index = 0;

   481 	}

   482 	value = teedataobject_getitem(to->dataobj, to->index);

   483 	if (value == NULL)

   484 		return NULL;

   485 	to->index++;

   486 	return value;

   487 }

   488 

   489 static int

   490 tee_traverse(teeobject *to, visitproc visit, void *arg)

   491 {

   492 	Py_VISIT((PyObject *)to->dataobj);

   493 	return 0;

   494 }

   495 

   496 static PyObject *

   497 tee_copy(teeobject *to)

   498 {

   499 	teeobject *newto;

   500 

   501 	newto = PyObject_GC_New(teeobject, &tee_type);

   502 	if (newto == NULL)

   503 		return NULL;

   504 	Py_INCREF(to->dataobj);

   505 	newto->dataobj = to->dataobj;

   506 	newto->index = to->index;

   507 	newto->weakreflist = NULL;

   508 	PyObject_GC_Track(newto);

   509 	return (PyObject *)newto;

   510 }

   511 

   512 PyDoc_STRVAR(teecopy_doc, "Returns an independent iterator.");

   513 

   514 static PyObject *

   515 tee_fromiterable(PyObject *iterable)

   516 {

   517 	teeobject *to;

   518 	PyObject *it = NULL;

   519 

   520 	it = PyObject_GetIter(iterable);

   521 	if (it == NULL)

   522 		return NULL;

   523 	if (PyObject_TypeCheck(it, &tee_type)) {

   524 		to = (teeobject *)tee_copy((teeobject *)it);

   525 		goto done;

   526 	}

   527 

   528 	to = PyObject_GC_New(teeobject, &tee_type);

   529 	if (to == NULL) 

   530 		goto done;

   531 	to->dataobj = (teedataobject *)teedataobject_new(it);

   532 	if (!to->dataobj) {

   533 		PyObject_GC_Del(to);

   534 		to = NULL;

   535 		goto done;

   536 	}

   537 

   538 	to->index = 0;

   539 	to->weakreflist = NULL;

   540 	PyObject_GC_Track(to);

   541 done:

   542 	Py_XDECREF(it);

   543 	return (PyObject *)to;

   544 }

   545 

   546 static PyObject *

   547 tee_new(PyTypeObject *type, PyObject *args, PyObject *kw)

   548 {

   549 	PyObject *iterable;

   550 

   551 	if (!PyArg_UnpackTuple(args, "tee", 1, 1, &iterable))

   552 		return NULL;

   553 	return tee_fromiterable(iterable);

   554 }

   555 

   556 static int

   557 tee_clear(teeobject *to)

   558 {

   559 	if (to->weakreflist != NULL)

   560 		PyObject_ClearWeakRefs((PyObject *) to);

   561 	Py_CLEAR(to->dataobj);

   562 	return 0;

   563 }

   564 

   565 static void

   566 tee_dealloc(teeobject *to)

   567 {

   568 	PyObject_GC_UnTrack(to);

   569 	tee_clear(to);

   570 	PyObject_GC_Del(to);

   571 }

   572 

   573 PyDoc_STRVAR(teeobject_doc,

   574 "Iterator wrapped to make it copyable");

   575 

   576 static PyMethodDef tee_methods[] = {

   577 	{"__copy__",	(PyCFunction)tee_copy,	METH_NOARGS, teecopy_doc},

   578  	{NULL,		NULL}		/* sentinel */

   579 };

   580 

   581 static PyTypeObject tee_type = {

   582 	PyVarObject_HEAD_INIT(NULL, 0)

   583 	"itertools.tee",		/* tp_name */

   584 	sizeof(teeobject),		/* tp_basicsize */

   585 	0,				/* tp_itemsize */

   586 	/* methods */

   587 	(destructor)tee_dealloc,	/* tp_dealloc */

   588 	0,				/* tp_print */

   589 	0,				/* tp_getattr */

   590 	0,				/* tp_setattr */

   591 	0,				/* tp_compare */

   592 	0,				/* tp_repr */

   593 	0,				/* tp_as_number */

   594 	0,				/* tp_as_sequence */

   595 	0,				/* tp_as_mapping */

   596 	0,				/* tp_hash */

   597 	0,				/* tp_call */

   598 	0,				/* tp_str */

   599 	0,				/* tp_getattro */

   600 	0,				/* tp_setattro */

   601 	0,				/* tp_as_buffer */

   602 	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,	/* tp_flags */

   603 	teeobject_doc,			/* tp_doc */

   604 	(traverseproc)tee_traverse,	/* tp_traverse */

   605 	(inquiry)tee_clear,		/* tp_clear */

   606 	0,				/* tp_richcompare */

   607 	offsetof(teeobject, weakreflist),	/* tp_weaklistoffset */

   608 	PyObject_SelfIter,		/* tp_iter */

   609 	(iternextfunc)tee_next,		/* tp_iternext */

   610 	tee_methods,			/* tp_methods */

   611 	0,				/* tp_members */

   612 	0,				/* tp_getset */

   613 	0,				/* tp_base */

   614 	0,				/* tp_dict */

   615 	0,				/* tp_descr_get */

   616 	0,				/* tp_descr_set */

   617 	0,				/* tp_dictoffset */

   618 	0,				/* tp_init */

   619 	0,				/* tp_alloc */

   620 	tee_new,			/* tp_new */

   621 	PyObject_GC_Del,		/* tp_free */

   622 };

   623 

   624 static PyObject *

   625 tee(PyObject *self, PyObject *args)

   626 {

   627 	Py_ssize_t i, n=2;

   628 	PyObject *it, *iterable, *copyable, *result;

   629 

   630 	if (!PyArg_ParseTuple(args, "O|n", &iterable, &n))

   631 		return NULL;

   632 	if (n < 0) {

   633 		PyErr_SetString(PyExc_ValueError, "n must be >= 0");

   634 		return NULL;

   635 	}

   636 	result = PyTuple_New(n);

   637 	if (result == NULL)

   638 		return NULL;

   639 	if (n == 0)

   640 		return result;

   641 	it = PyObject_GetIter(iterable);

   642 	if (it == NULL) {

   643 		Py_DECREF(result);

   644 		return NULL;

   645 	}

   646 	if (!PyObject_HasAttrString(it, "__copy__")) {

   647 		copyable = tee_fromiterable(it);

   648 		Py_DECREF(it);

   649 		if (copyable == NULL) {

   650 			Py_DECREF(result);

   651 			return NULL;

   652 		}

   653 	} else

   654 		copyable = it;

   655 	PyTuple_SET_ITEM(result, 0, copyable);

   656 	for (i=1 ; i<n ; i++) {

   657 		copyable = PyObject_CallMethod(copyable, "__copy__", NULL);

   658 		if (copyable == NULL) {

   659 			Py_DECREF(result);

   660 			return NULL;

   661 		}

   662 		PyTuple_SET_ITEM(result, i, copyable);

   663 	}

   664 	return result;

   665 }

   666 

   667 PyDoc_STRVAR(tee_doc,

   668 "tee(iterable, n=2) --> tuple of n independent iterators.");

   669 

   670 

   671 /* cycle object **********************************************************/

   672 

   673 typedef struct {

   674 	PyObject_HEAD

   675 	PyObject *it;

   676 	PyObject *saved;

   677 	int firstpass;

   678 } cycleobject;

   679 

   680 static PyTypeObject cycle_type;

   681 

   682 static PyObject *

   683 cycle_new(PyTypeObject *type, PyObject *args, PyObject *kwds)

   684 {

   685 	PyObject *it;

   686 	PyObject *iterable;

   687 	PyObject *saved;

   688 	cycleobject *lz;

   689 

   690 	if (type == &cycle_type && !_PyArg_NoKeywords("cycle()", kwds))

   691 		return NULL;

   692 

   693 	if (!PyArg_UnpackTuple(args, "cycle", 1, 1, &iterable))

   694 		return NULL;

   695 

   696 	/* Get iterator. */

   697 	it = PyObject_GetIter(iterable);

   698 	if (it == NULL)

   699 		return NULL;

   700 

   701 	saved = PyList_New(0);

   702 	if (saved == NULL) {

   703 		Py_DECREF(it);

   704 		return NULL;

   705 	}

   706 

   707 	/* create cycleobject structure */

   708 	lz = (cycleobject *)type->tp_alloc(type, 0);

   709 	if (lz == NULL) {

   710 		Py_DECREF(it);

   711 		Py_DECREF(saved);

   712 		return NULL;

   713 	}

   714 	lz->it = it;

   715 	lz->saved = saved;

   716 	lz->firstpass = 0;

   717 

   718 	return (PyObject *)lz;

   719 }

   720 

   721 static void

   722 cycle_dealloc(cycleobject *lz)

   723 {

   724 	PyObject_GC_UnTrack(lz);

   725 	Py_XDECREF(lz->saved);

   726 	Py_XDECREF(lz->it);

   727 	Py_TYPE(lz)->tp_free(lz);

   728 }

   729 

   730 static int

   731 cycle_traverse(cycleobject *lz, visitproc visit, void *arg)

   732 {

   733 	Py_VISIT(lz->it);

   734 	Py_VISIT(lz->saved);

   735 	return 0;

   736 }

   737 

   738 static PyObject *

   739 cycle_next(cycleobject *lz)

   740 {

   741 	PyObject *item;

   742 	PyObject *it;

   743 	PyObject *tmp;

   744 

   745 	while (1) {

   746 		item = PyIter_Next(lz->it);

   747 		if (item != NULL) {

   748 			if (!lz->firstpass)

   749 				PyList_Append(lz->saved, item);

   750 			return item;

   751 		}

   752 		if (PyErr_Occurred()) {

   753 			if (PyErr_ExceptionMatches(PyExc_StopIteration))

   754 				PyErr_Clear();

   755 			else

   756 				return NULL;

   757 		}

   758 		if (PyList_Size(lz->saved) == 0) 

   759 			return NULL;

   760 		it = PyObject_GetIter(lz->saved);

   761 		if (it == NULL)

   762 			return NULL;

   763 		tmp = lz->it;

   764 		lz->it = it;

   765 		lz->firstpass = 1;

   766 		Py_DECREF(tmp);

   767 	}

   768 }

   769 

   770 PyDoc_STRVAR(cycle_doc,

   771 "cycle(iterable) --> cycle object\n\

   772 \n\

   773 Return elements from the iterable until it is exhausted.\n\

   774 Then repeat the sequence indefinitely.");

   775 

   776 static PyTypeObject cycle_type = {

   777 	PyVarObject_HEAD_INIT(NULL, 0)

   778 	"itertools.cycle",		/* tp_name */

   779 	sizeof(cycleobject),		/* tp_basicsize */

   780 	0,				/* tp_itemsize */

   781 	/* methods */

   782 	(destructor)cycle_dealloc,	/* tp_dealloc */

   783 	0,				/* tp_print */

   784 	0,				/* tp_getattr */

   785 	0,				/* tp_setattr */

   786 	0,				/* tp_compare */

   787 	0,				/* tp_repr */

   788 	0,				/* tp_as_number */

   789 	0,				/* tp_as_sequence */

   790 	0,				/* tp_as_mapping */

   791 	0,				/* tp_hash */

   792 	0,				/* tp_call */

   793 	0,				/* tp_str */

   794 	PyObject_GenericGetAttr,	/* tp_getattro */

   795 	0,				/* tp_setattro */

   796 	0,				/* tp_as_buffer */

   797 	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |

   798 		Py_TPFLAGS_BASETYPE,	/* tp_flags */

   799 	cycle_doc,			/* tp_doc */

   800 	(traverseproc)cycle_traverse,	/* tp_traverse */

   801 	0,				/* tp_clear */

   802 	0,				/* tp_richcompare */

   803 	0,				/* tp_weaklistoffset */

   804 	PyObject_SelfIter,		/* tp_iter */

   805 	(iternextfunc)cycle_next,	/* tp_iternext */

   806 	0,				/* tp_methods */

   807 	0,				/* tp_members */

   808 	0,				/* tp_getset */

   809 	0,				/* tp_base */

   810 	0,				/* tp_dict */

   811 	0,				/* tp_descr_get */

   812 	0,				/* tp_descr_set */

   813 	0,				/* tp_dictoffset */

   814 	0,				/* tp_init */

   815 	0,				/* tp_alloc */

   816 	cycle_new,			/* tp_new */

   817 	PyObject_GC_Del,		/* tp_free */

   818 };

   819 

   820 

   821 /* dropwhile object **********************************************************/

   822 

   823 typedef struct {

   824 	PyObject_HEAD

   825 	PyObject *func;

   826 	PyObject *it;

   827 	long	 start;

   828 } dropwhileobject;

   829 

   830 static PyTypeObject dropwhile_type;

   831 

   832 static PyObject *

   833 dropwhile_new(PyTypeObject *type, PyObject *args, PyObject *kwds)

   834 {

   835 	PyObject *func, *seq;

   836 	PyObject *it;

   837 	dropwhileobject *lz;

   838 

   839 	if (type == &dropwhile_type && !_PyArg_NoKeywords("dropwhile()", kwds))

   840 		return NULL;

   841 

   842 	if (!PyArg_UnpackTuple(args, "dropwhile", 2, 2, &func, &seq))

   843 		return NULL;

   844 

   845 	/* Get iterator. */

   846 	it = PyObject_GetIter(seq);

   847 	if (it == NULL)

   848 		return NULL;

   849 

   850 	/* create dropwhileobject structure */

   851 	lz = (dropwhileobject *)type->tp_alloc(type, 0);

   852 	if (lz == NULL) {

   853 		Py_DECREF(it);

   854 		return NULL;

   855 	}

   856 	Py_INCREF(func);

   857 	lz->func = func;

   858 	lz->it = it;

   859 	lz->start = 0;

   860 

   861 	return (PyObject *)lz;

   862 }

   863 

   864 static void

   865 dropwhile_dealloc(dropwhileobject *lz)

   866 {

   867 	PyObject_GC_UnTrack(lz);

   868 	Py_XDECREF(lz->func);

   869 	Py_XDECREF(lz->it);

   870 	Py_TYPE(lz)->tp_free(lz);

   871 }

   872 

   873 static int

   874 dropwhile_traverse(dropwhileobject *lz, visitproc visit, void *arg)

   875 {

   876 	Py_VISIT(lz->it);

   877 	Py_VISIT(lz->func);

   878 	return 0;

   879 }

   880 

   881 static PyObject *

   882 dropwhile_next(dropwhileobject *lz)

   883 {

   884 	PyObject *item, *good;

   885 	PyObject *it = lz->it;

   886 	long ok;

   887 	PyObject *(*iternext)(PyObject *);

   888 

   889 	assert(PyIter_Check(it));

   890 	iternext = *Py_TYPE(it)->tp_iternext;

   891 	for (;;) {

   892 		item = iternext(it);

   893 		if (item == NULL)

   894 			return NULL;

   895 		if (lz->start == 1)

   896 			return item;

   897 

   898 		good = PyObject_CallFunctionObjArgs(lz->func, item, NULL);

   899 		if (good == NULL) {

   900 			Py_DECREF(item);

   901 			return NULL;

   902 		}

   903 		ok = PyObject_IsTrue(good);

   904 		Py_DECREF(good);

   905 		if (!ok) {

   906 			lz->start = 1;

   907 			return item;

   908 		}

   909 		Py_DECREF(item);

   910 	}

   911 }

   912 

   913 PyDoc_STRVAR(dropwhile_doc,

   914 "dropwhile(predicate, iterable) --> dropwhile object\n\

   915 \n\

   916 Drop items from the iterable while predicate(item) is true.\n\

   917 Afterwards, return every element until the iterable is exhausted.");

   918 

   919 static PyTypeObject dropwhile_type = {

   920 	PyVarObject_HEAD_INIT(NULL, 0)

   921 	"itertools.dropwhile",		/* tp_name */

   922 	sizeof(dropwhileobject),	/* tp_basicsize */

   923 	0,				/* tp_itemsize */

   924 	/* methods */

   925 	(destructor)dropwhile_dealloc,	/* tp_dealloc */

   926 	0,				/* tp_print */

   927 	0,				/* tp_getattr */

   928 	0,				/* tp_setattr */

   929 	0,				/* tp_compare */

   930 	0,				/* tp_repr */

   931 	0,				/* tp_as_number */

   932 	0,				/* tp_as_sequence */

   933 	0,				/* tp_as_mapping */

   934 	0,				/* tp_hash */

   935 	0,				/* tp_call */

   936 	0,				/* tp_str */

   937 	PyObject_GenericGetAttr,	/* tp_getattro */

   938 	0,				/* tp_setattro */

   939 	0,				/* tp_as_buffer */

   940 	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |

   941 		Py_TPFLAGS_BASETYPE,	/* tp_flags */

   942 	dropwhile_doc,			/* tp_doc */

   943 	(traverseproc)dropwhile_traverse,    /* tp_traverse */

   944 	0,				/* tp_clear */

   945 	0,				/* tp_richcompare */

   946 	0,				/* tp_weaklistoffset */

   947 	PyObject_SelfIter,		/* tp_iter */

   948 	(iternextfunc)dropwhile_next,	/* tp_iternext */

   949 	0,				/* tp_methods */

   950 	0,				/* tp_members */

   951 	0,				/* tp_getset */

   952 	0,				/* tp_base */

   953 	0,				/* tp_dict */

   954 	0,				/* tp_descr_get */

   955 	0,				/* tp_descr_set */

   956 	0,				/* tp_dictoffset */

   957 	0,				/* tp_init */

   958 	0,				/* tp_alloc */

   959 	dropwhile_new,			/* tp_new */

   960 	PyObject_GC_Del,		/* tp_free */

   961 };

   962 

   963 

   964 /* takewhile object **********************************************************/

   965 

   966 typedef struct {

   967 	PyObject_HEAD

   968 	PyObject *func;

   969 	PyObject *it;

   970 	long	 stop;

   971 } takewhileobject;

   972 

   973 static PyTypeObject takewhile_type;

   974 

   975 static PyObject *

   976 takewhile_new(PyTypeObject *type, PyObject *args, PyObject *kwds)

   977 {

   978 	PyObject *func, *seq;

   979 	PyObject *it;

   980 	takewhileobject *lz;

   981 

   982 	if (type == &takewhile_type && !_PyArg_NoKeywords("takewhile()", kwds))

   983 		return NULL;

   984 

   985 	if (!PyArg_UnpackTuple(args, "takewhile", 2, 2, &func, &seq))

   986 		return NULL;

   987 

   988 	/* Get iterator. */

   989 	it = PyObject_GetIter(seq);

   990 	if (it == NULL)

   991 		return NULL;

   992 

   993 	/* create takewhileobject structure */

   994 	lz = (takewhileobject *)type->tp_alloc(type, 0);

   995 	if (lz == NULL) {

   996 		Py_DECREF(it);

   997 		return NULL;

   998 	}

   999 	Py_INCREF(func);

  1000 	lz->func = func;

  1001 	lz->it = it;

  1002 	lz->stop = 0;

  1003 

  1004 	return (PyObject *)lz;

  1005 }

  1006 

  1007 static void

  1008 takewhile_dealloc(takewhileobject *lz)

  1009 {

  1010 	PyObject_GC_UnTrack(lz);

  1011 	Py_XDECREF(lz->func);

  1012 	Py_XDECREF(lz->it);

  1013 	Py_TYPE(lz)->tp_free(lz);

  1014 }

  1015 

  1016 static int

  1017 takewhile_traverse(takewhileobject *lz, visitproc visit, void *arg)

  1018 {

  1019 	Py_VISIT(lz->it);

  1020 	Py_VISIT(lz->func);

  1021 	return 0;

  1022 }

  1023 

  1024 static PyObject *

  1025 takewhile_next(takewhileobject *lz)

  1026 {

  1027 	PyObject *item, *good;

  1028 	PyObject *it = lz->it;

  1029 	long ok;

  1030 

  1031 	if (lz->stop == 1)

  1032 		return NULL;

  1033 

  1034 	assert(PyIter_Check(it));

  1035 	item = (*Py_TYPE(it)->tp_iternext)(it);

  1036 	if (item == NULL)

  1037 		return NULL;

  1038 

  1039 	good = PyObject_CallFunctionObjArgs(lz->func, item, NULL);

  1040 	if (good == NULL) {

  1041 		Py_DECREF(item);

  1042 		return NULL;

  1043 	}

  1044 	ok = PyObject_IsTrue(good);

  1045 	Py_DECREF(good);

  1046 	if (ok)

  1047 		return item;

  1048 	Py_DECREF(item);

  1049 	lz->stop = 1;

  1050 	return NULL;

  1051 }

  1052 

  1053 PyDoc_STRVAR(takewhile_doc,

  1054 "takewhile(predicate, iterable) --> takewhile object\n\

  1055 \n\

  1056 Return successive entries from an iterable as long as the \n\

  1057 predicate evaluates to true for each entry.");

  1058 

  1059 static PyTypeObject takewhile_type = {

  1060 	PyVarObject_HEAD_INIT(NULL, 0)

  1061 	"itertools.takewhile",		/* tp_name */

  1062 	sizeof(takewhileobject),	/* tp_basicsize */

  1063 	0,				/* tp_itemsize */

  1064 	/* methods */

  1065 	(destructor)takewhile_dealloc,	/* tp_dealloc */

  1066 	0,				/* tp_print */

  1067 	0,				/* tp_getattr */

  1068 	0,				/* tp_setattr */

  1069 	0,				/* tp_compare */

  1070 	0,				/* tp_repr */

  1071 	0,				/* tp_as_number */

  1072 	0,				/* tp_as_sequence */

  1073 	0,				/* tp_as_mapping */

  1074 	0,				/* tp_hash */

  1075 	0,				/* tp_call */

  1076 	0,				/* tp_str */

  1077 	PyObject_GenericGetAttr,	/* tp_getattro */

  1078 	0,				/* tp_setattro */

  1079 	0,				/* tp_as_buffer */

  1080 	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |

  1081 		Py_TPFLAGS_BASETYPE,	/* tp_flags */

  1082 	takewhile_doc,			/* tp_doc */

  1083 	(traverseproc)takewhile_traverse,    /* tp_traverse */

  1084 	0,				/* tp_clear */

  1085 	0,				/* tp_richcompare */

  1086 	0,				/* tp_weaklistoffset */

  1087 	PyObject_SelfIter,		/* tp_iter */

  1088 	(iternextfunc)takewhile_next,	/* tp_iternext */

  1089 	0,				/* tp_methods */

  1090 	0,				/* tp_members */

  1091 	0,				/* tp_getset */

  1092 	0,				/* tp_base */

  1093 	0,				/* tp_dict */

  1094 	0,				/* tp_descr_get */

  1095 	0,				/* tp_descr_set */

  1096 	0,				/* tp_dictoffset */

  1097 	0,				/* tp_init */

  1098 	0,				/* tp_alloc */

  1099 	takewhile_new,			/* tp_new */

  1100 	PyObject_GC_Del,		/* tp_free */

  1101 };

  1102 

  1103 

  1104 /* islice object ************************************************************/

  1105 

  1106 typedef struct {

  1107 	PyObject_HEAD

  1108 	PyObject *it;

  1109 	Py_ssize_t next;

  1110 	Py_ssize_t stop;

  1111 	Py_ssize_t step;

  1112 	Py_ssize_t cnt;

  1113 } isliceobject;

  1114 

  1115 static PyTypeObject islice_type;

  1116 

  1117 static PyObject *

  1118 islice_new(PyTypeObject *type, PyObject *args, PyObject *kwds)

  1119 {

  1120 	PyObject *seq;

  1121 	Py_ssize_t start=0, stop=-1, step=1;

  1122 	PyObject *it, *a1=NULL, *a2=NULL, *a3=NULL;

  1123 	Py_ssize_t numargs;

  1124 	isliceobject *lz;

  1125 

  1126 	if (type == &islice_type && !_PyArg_NoKeywords("islice()", kwds))

  1127 		return NULL;

  1128 

  1129 	if (!PyArg_UnpackTuple(args, "islice", 2, 4, &seq, &a1, &a2, &a3))

  1130 		return NULL;

  1131 

  1132 	numargs = PyTuple_Size(args);

  1133 	if (numargs == 2) {

  1134 		if (a1 != Py_None) {

  1135 			stop = PyInt_AsSsize_t(a1);