diff options
| -rw-r--r-- | Doc/lib/lib.tex | 1 | ||||
| -rw-r--r-- | Doc/lib/libitertools.tex | 325 | ||||
| -rw-r--r-- | Lib/test/test_itertools.py | 158 | ||||
| -rw-r--r-- | Misc/NEWS | 3 | ||||
| -rw-r--r-- | Modules/itertoolsmodule.c | 1532 | ||||
| -rw-r--r-- | PC/config.c | 2 | ||||
| -rw-r--r-- | PCbuild/pythoncore.dsp | 4 | ||||
| -rw-r--r-- | setup.py | 2 |
8 files changed, 2027 insertions, 0 deletions
diff --git a/Doc/lib/lib.tex b/Doc/lib/lib.tex index d1fd943..750d3ac 100644 --- a/Doc/lib/lib.tex +++ b/Doc/lib/lib.tex @@ -125,6 +125,7 @@ and how to embed it in other applications. \input{libheapq} \input{libarray} \input{libsets} +\input{libitertools} \input{libcfgparser} \input{libfileinput} \input{libxreadlines} diff --git a/Doc/lib/libitertools.tex b/Doc/lib/libitertools.tex new file mode 100644 index 0000000..5d49e66 --- /dev/null +++ b/Doc/lib/libitertools.tex @@ -0,0 +1,325 @@ +\section{\module{itertools} --- + Functions creating iterators for efficient looping} + +\declaremodule{standard}{itertools} +\modulesynopsis{Functions creating iterators for efficient looping.} +\moduleauthor{Raymond Hettinger}{python@rcn.com} +\sectionauthor{Raymond Hettinger}{python@rcn.com} +\versionadded{2.3} + + +This module implements a number of iterator building blocks inspired +by constructs from the Haskell and SML programming languages. Each +has been recast in a form suitable for Python. + +With the advent of iterators and generators in Python 2.3, each of +these tools can be expressed easily and succinctly in pure python. +Rather duplicating what can already be done, this module emphasizes +providing value in other ways: + +\begin{itemize} + + \item Instead of constructing an over-specialized toolset, this module + provides basic building blocks that can be readily combined. + + For instance, SML provides a tabulation tool: \code{tabulate(\var{f})} + which produces a sequence \code{f(0), f(1), ...}. This toolbox + takes a different approach of providing \function{imap()} and + \function{count()} which can be combined to form + \code{imap(\var{f}, count())} and produce an equivalent result. + + \item Some tools were dropped because they offer no advantage over their + pure python counterparts or because their behavior was too + surprising. + + For instance, SML provides a tool: \code{cycle(\var{seq})} which + loops over the sequence elements and then starts again when the + sequence is exhausted. The surprising behavior is the need for + significant auxiliary storage (unusual for iterators). Also, it + is trivially implemented in python with almost no performance + penalty. + + \item Another source of value comes from standardizing a core set of tools + to avoid the readability and reliability problems that arise when many + different individuals create their own slightly varying implementations + each with their own quirks and naming conventions. + + \item Whether cast in pure python form or C code, tools that use iterators + are more memory efficient (and faster) than their list based counterparts. + Adopting the principles of just-in-time manufacturing, they create + data when and where needed instead of consuming memory with the + computer equivalent of ``inventory''. + +\end{itemize} + +\begin{seealso} + \seetext{The Standard ML Basis Library, + \citetitle[http://www.standardml.org/Basis/] + {The Standard ML Basis Library}.} + + \seetext{Haskell, A Purely Functional Language, + \citetitle[http://www.haskell.org/definition/] + {Definition of Haskell and the Standard Libraries}.} +\end{seealso} + + +\subsection{Itertool functions \label{itertools-functions}} + +The following module functions all construct and return iterators. +Some provide streams of infinite length, so they should only be accessed +by functions or loops that truncate the stream. + +\begin{funcdesc}{count}{\optional{n}} + Make an iterator that returns consecutive integers starting with \var{n}. + Does not currently support python long integers. Often used as an + argument to \function{imap()} to generate consecutive data points. + Also, used in \function{izip()} to add sequence numbers. Equivalent to: + + \begin{verbatim} + def count(n=0): + cnt = n + while True: + yield cnt + cnt += 1 + \end{verbatim} +\end{funcdesc} + +\begin{funcdesc}{dropwhile}{predicate, iterable} + Make an iterator that drops elements from the iterable as long as + the predicate is true; afterwards, returns every element. Note, + the iterator does not produce \emph{any} output until the predicate + is true, so it may have a lengthy start-up time. Equivalent to: + + \begin{verbatim} + def dropwhile(predicate, iterable): + iterable = iter(iterable) + while True: + x = iterable.next() + if predicate(x): continue # drop when predicate is true + yield x + break + while True: + yield iterable.next() + \end{verbatim} +\end{funcdesc} + +\begin{funcdesc}{ifilter}{predicate, iterable \optional{, invert}} + Make an iterator that filters elements from iterable returning only + those for which the predicate is \code{True}. If + \var{invert} is \code{True}, then reverse the process and pass through + only those elements for which the predicate is \code{False}. + If \var{predicate} is \code{None}, return the items that are true + (or false if \var{invert} has been set). Equivalent to: + + \begin{verbatim} + def ifilter(predicate, iterable, invert=False): + iterable = iter(iterable) + while True: + x = iterable.next() + if predicate is None: + b = bool(x) + else: + b = bool(predicate(x)) + if not invert and b or invert and not b: + yield x + \end{verbatim} +\end{funcdesc} + +\begin{funcdesc}{imap}{function, *iterables} + Make an iterator that computes the function using arguments from + each of the iterables. If \var{function} is set to \code{None}, then + \function{imap()} returns the arguments as a tuple. Like + \function{map()} but stops when the shortest iterable is exhausted + instead of filling in \code{None} for shorter iterables. The reason + for the difference is that infinite iterator arguments are typically + an error for \function{map()} (because the output is fully evaluated) + but represent a common and useful way of supplying arguments to + \function{imap()}. + Equivalent to: + + \begin{verbatim} + def imap(function, *iterables): + iterables = map(iter, iterables) + while True: + args = [i.next() for i in iterables] + if function is None: + yield tuple(args) + else: + yield function(*args) + \end{verbatim} +\end{funcdesc} + +\begin{funcdesc}{islice}{iterable, \optional{start,} stop \optional{, step}} + Make an iterator that returns selected elements from the iterable. + If \var{start} is non-zero, then elements from the iterable are skipped + until start is reached. Afterward, elements are returned consecutively + unless \var{step} is set higher than one which results in items being + skipped. If \var{stop} is specified, then iteration stops at the + specified element position; otherwise, it continues indefinitely or + until the iterable is exhausted. Unlike regular slicing, + \function{islice()} does not support negative values for \var{start}, + \var{stop}, or \var{step}. Can be used to extract related fields + from data where the internal structure has been flattened (for + example, a multi-line report may list a name field on every + third line). Equivalent to: + + \begin{verbatim} + def islice(iterable, *args): + iterable = iter(iterable) + s = slice(*args) + next = s.start or 0 + stop = s.stop + step = s.step or 1 + cnt = 0 + while True: + while cnt < next: + dummy = iterable.next() + cnt += 1 + if cnt >= stop: + break + yield iterable.next() + cnt += 1 + next += step + \end{verbatim} +\end{funcdesc} + +\begin{funcdesc}{izip}{*iterables} + Make an iterator that aggregates elements from each of the iterables. + Like \function{zip()} except that it returns an iterator instead of + a list. Used for lock-step iteration over several iterables at a + time. Equivalent to: + + \begin{verbatim} + def izip(*iterables): + iterables = map(iter, iterables) + while True: + result = [i.next() for i in iterables] + yield tuple(result) + \end{verbatim} +\end{funcdesc} + +\begin{funcdesc}{repeat}{obj} + Make an iterator that returns \var{obj} over and over again. + Used as argument to \function{imap()} for invariant parameters + to the called function. Also used with function{izip()} to create + an invariant part of a tuple record. Equivalent to: + + \begin{verbatim} + def repeat(x): + while True: + yield x + \end{verbatim} +\end{funcdesc} + +\begin{funcdesc}{starmap}{function, iterable} + Make an iterator that computes the function using arguments tuples + obtained from the iterable. Used instead of \function{imap()} when + argument parameters are already grouped in tuples from a single iterable + (the data has been ``pre-zipped''). The difference between + \function{imap()} and \function{starmap} parallels the distinction + between \code{function(a,b)} and \code{function(*c)}. + Equivalent to: + + \begin{verbatim} + def starmap(function, iterable): + iterable = iter(iterable) + while True: + yield function(*iterable.next()) + \end{verbatim} +\end{funcdesc} + +\begin{funcdesc}{takewhile}{predicate, iterable} + Make an iterator that returns elements from the iterable as long as + the predicate is true. Equivalent to: + + \begin{verbatim} + def takewhile(predicate, iterable): + iterable = iter(iterable) + while True: + x = iterable.next() + if predicate(x): + yield x + else: + break + \end{verbatim} +\end{funcdesc} + +\begin{funcdesc}{times}{n, \optional{object}} + Make an iterator that returns \var{object} \var{n} times. + \var{object} defaults to \code{None}. Used for looping a specific + number of times without creating a number object on each pass. + Equivalent to: + + \begin{verbatim} + def times(n, object=None): + if n<0 : raise ValueError + for i in xrange(n): + yield object + \end{verbatim} +\end{funcdesc} + + +\subsection{Examples \label{itertools-example}} + +The following examples show common uses for each tool and +demonstrate ways they can be combined. + +\begin{verbatim} +>>> for i in times(3): +... print "Hello" +... +Hello +Hello +Hello + +>>> amounts = [120.15, 764.05, 823.14] +>>> for checknum, amount in izip(count(1200), amounts): +... print 'Check %d is for $%.2f' % (checknum, amount) +... +Check 1200 is for $120.15 +Check 1201 is for $764.05 +Check 1202 is for $823.14 + +>>> import operator +>>> for cube in imap(operator.pow, xrange(1,4), repeat(3)): +... print cube +... +1 +8 +27 + +>>> reportlines = ['EuroPython', 'Roster', '', 'alex', '', 'laura', + '', 'martin', '', 'walter', '', 'samuele'] +>>> for name in islice(reportlines, 3, len(reportlines), 2): +... print name.title() +... +Alex +Laura +Martin +Walter +Samuele + +\end{verbatim} + +This section has further examples of how itertools can be combined. +Note that \function{enumerate()} and \method{iteritems()} already +have highly efficient implementations in Python. They are only +included here to illustrate how higher level tools can be created +from building blocks. + +\begin{verbatim} +>>> def enumerate(iterable): +... return izip(count(), iterable) + +>>> def tabulate(function): +... "Return function(0), function(1), ..." +... return imap(function, count()) + +>>> def iteritems(mapping): +... return izip(mapping.iterkeys(), mapping.itervalues()) + +>>> def nth(iterable, n): +... "Returns the nth item" +... return islice(iterable, n, n+1).next() + +\end{verbatim} diff --git a/Lib/test/test_itertools.py b/Lib/test/test_itertools.py new file mode 100644 index 0000000..c096e16 --- /dev/null +++ b/Lib/test/test_itertools.py @@ -0,0 +1,158 @@ +import unittest +from test import test_support +from itertools import * + +class TestBasicOps(unittest.TestCase): + def test_count(self): + self.assertEqual(zip('abc',count()), [('a', 0), ('b', 1), ('c', 2)]) + self.assertEqual(zip('abc',count(3)), [('a', 3), ('b', 4), ('c', 5)]) + self.assertRaises(TypeError, count, 2, 3) + + def test_ifilter(self): + def isEven(x): + return x%2==0 + self.assertEqual(list(ifilter(isEven, range(6))), [0,2,4]) + self.assertEqual(list(ifilter(isEven, range(6), True)), [1,3,5]) + self.assertEqual(list(ifilter(None, [0,1,0,2,0])), [1,2]) + self.assertRaises(TypeError, ifilter) + self.assertRaises(TypeError, ifilter, 3) + self.assertRaises(TypeError, ifilter, isEven, 3) + self.assertRaises(TypeError, ifilter, isEven, [3], True, 4) + + def test_izip(self): + ans = [(x,y) for x, y in izip('abc',count())] + self.assertEqual(ans, [('a', 0), ('b', 1), ('c', 2)]) + self.assertRaises(TypeError, izip) + + def test_repeat(self): + self.assertEqual(zip(xrange(3),repeat('a')), + [(0, 'a'), (1, 'a'), (2, 'a')]) + self.assertRaises(TypeError, repeat) + + def test_times(self): + self.assertEqual(list(times(3)), [None]*3) + self.assertEqual(list(times(3, True)), [True]*3) + self.assertRaises(ValueError, times, -1) + + def test_imap(self): + import operator + self.assertEqual(list(imap(operator.pow, range(3), range(1,7))), + [0**1, 1**2, 2**3]) + self.assertEqual(list(imap(None, 'abc', range(5))), + [('a',0),('b',1),('c',2)]) + self.assertRaises(TypeError, imap) + self.assertRaises(TypeError, imap, operator.neg) + + def test_starmap(self): + import operator + self.assertEqual(list(starmap(operator.pow, zip(range(3), range(1,7)))), + [0**1, 1**2, 2**3]) + + def test_islice(self): + for args in [ # islice(args) should agree with range(args) + (10, 20, 3), + (10, 3, 20), + (10, 20), + (10, 3), + (20,) + ]: + self.assertEqual(list(islice(xrange(100), *args)), range(*args)) + + for args, tgtargs in [ # Stop when seqn is exhausted + ((10, 110, 3), ((10, 100, 3))), + ((10, 110), ((10, 100))), + ((110,), (100,)) + ]: + self.assertEqual(list(islice(xrange(100), *args)), range(*tgtargs)) + + self.assertRaises(TypeError, islice, xrange(10)) + self.assertRaises(TypeError, islice, xrange(10), 1, 2, 3, 4) + self.assertRaises(ValueError, islice, xrange(10), -5, 10, 1) + self.assertRaises(ValueError, islice, xrange(10), 1, -5, -1) + self.assertRaises(ValueError, islice, xrange(10), 1, 10, -1) + self.assertRaises(ValueError, islice, xrange(10), 1, 10, 0) + + def test_takewhile(self): + data = [1, 3, 5, 20, 2, 4, 6, 8] + underten = lambda x: x<10 + self.assertEqual(list(takewhile(underten, data)), [1, 3, 5]) + + def test_dropwhile(self): + data = [1, 3, 5, 20, 2, 4, 6, 8] + underten = lambda x: x<10 + self.assertEqual(list(dropwhile(underten, data)), [20, 2, 4, 6, 8]) + +libreftest = """ Doctest for examples in the library reference, libitertools.tex + +>>> for i in times(3): +... print "Hello" +... +Hello +Hello +Hello + +>>> amounts = [120.15, 764.05, 823.14] +>>> for checknum, amount in izip(count(1200), amounts): +... print 'Check %d is for $%.2f' % (checknum, amount) +... +Check 1200 is for $120.15 +Check 1201 is for $764.05 +Check 1202 is for $823.14 + +>>> import operator +>>> import operator +>>> for cube in imap(operator.pow, xrange(1,4), repeat(3)): +... print cube +... +1 +8 +27 + +>>> reportlines = ['EuroPython', 'Roster', '', 'alex', '', 'laura', '', 'martin', '', 'walter', '', 'samuele'] +>>> for name in islice(reportlines, 3, len(reportlines), 2): +... print name.title() +... +Alex +Laura +Martin +Walter +Samuele + +>>> def enumerate(iterable): +... return izip(count(), iterable) + +>>> def tabulate(function): +... "Return function(0), function(1), ..." +... return imap(function, count()) + +>>> def iteritems(mapping): +... return izip(mapping.iterkeys(), mapping.itervalues()) + +>>> def nth(iterable, n): +... "Returns the nth item" +... return islice(iterable, n, n+1).next() + +""" + +__test__ = {'libreftest' : libreftest} + +def test_main(verbose=None): + import test_itertools + suite = unittest.TestSuite() + for testclass in (TestBasicOps, + ): + suite.addTest(unittest.makeSuite(testclass)) + test_support.run_suite(suite) + test_support.run_doctest(test_itertools, verbose) + + # verify reference counting + import sys + if verbose and hasattr(sys, "gettotalrefcount"): + counts = [] + for i in xrange(5): + test_support.run_suite(suite) + counts.append(sys.gettotalrefcount()) + print counts + +if __name__ == "__main__": + test_main(verbose=True) @@ -30,6 +30,9 @@ Core and builtins Extension modules ----------------- +- Added an itertools module containing high speed, memory efficient + looping constructs inspired by tools from Haskell and SML. + - The SSL module now handles sockets with a timeout set correctly (SF patch #675750, fixing SF bug #675552). diff --git a/Modules/itertoolsmodule.c b/Modules/itertoolsmodule.c new file mode 100644 index 0000000..1076ec1 --- /dev/null +++ b/Modules/itertoolsmodule.c @@ -0,0 +1,1532 @@ + +#include "Python.h" + +/* Itertools module written and maintained + by Raymond D. Hettinger <python@rcn.com> + Copyright (c) 2003 Python Software Foundation. + All rights reserved. +*/ + +/* dropwhile object **********************************************************/ + +typedef struct { + PyObject_HEAD + PyObject *func; + PyObject *it; + long start; +} dropwhileobject; + +PyTypeObject dropwhile_type; + +static PyObject * +dropwhile_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + PyObject *func, *seq; + PyObject *it; + dropwhileobject *lz; + + if (!PyArg_UnpackTuple(args, "dropwhile", 2, 2, &func, &seq)) + return NULL; + + /* Get iterator. */ + it = PyObject_GetIter(seq); + if (it == NULL) + return NULL; + + /* create dropwhileobject structure */ + lz = (dropwhileobject *)type->tp_alloc(type, 0); + if (lz == NULL) { + Py_DECREF(it); + return NULL; + } + Py_INCREF(func); + lz->func = func; + lz->it = it; + lz->start = 0; + + return (PyObject *)lz; +} + +static void +dropwhile_dealloc(dropwhileobject *lz) +{ + PyObject_GC_UnTrack(lz); + Py_XDECREF(lz->func); + Py_XDECREF(lz->it); + lz->ob_type->tp_free(lz); +} + +static int +dropwhile_traverse(dropwhileobject *lz, visitproc visit, void *arg) +{ + int err; + + if (lz->it) { + err = visit(lz->it, arg); + if (err) + return err; + } + if (lz->func) { + err = visit(lz->func, arg); + if (err) + return err; + } + return 0; +} + +static PyObject * +dropwhile_next(dropwhileobject *lz) +{ + PyObject *item, *good; + long ok; + + for (;;) { + item = PyIter_Next(lz->it); + if (item == NULL) + return NULL; + if (lz->start == 1) + return item; + + good = PyObject_CallFunctionObjArgs(lz->func, item, NULL); + if (good == NULL) { + Py_DECREF(item); + return NULL; + } + ok = PyObject_IsTrue(good); + Py_DECREF(good); + if (!ok) { + lz->start = 1; + return item; + } + Py_DECREF(item); + } +} + +static PyObject * +dropwhile_getiter(PyObject *lz) +{ + Py_INCREF(lz); + return lz; +} + +PyDoc_STRVAR(dropwhile_doc, +"dropwhile(predicate, iterable) --> dropwhile object\n\ +\n\ +Drop items from the iterable while predicate(item) is true.\n\ +Afterwards, return every element until the iterable is exhausted."); + +PyTypeObject dropwhile_type = { + PyObject_HEAD_INIT(NULL) + 0, /* ob_size */ + "itertools.dropwhile", /* tp_name */ + sizeof(dropwhileobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)dropwhile_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_compare */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | + Py_TPFLAGS_BASETYPE, /* tp_flags */ + dropwhile_doc, /* tp_doc */ + (traverseproc)dropwhile_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)dropwhile_getiter, /* tp_iter */ + (iternextfunc)dropwhile_next, /* tp_iternext */ + 0, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + 0, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + 0, /* tp_dictoffset */ + 0, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + dropwhile_new, /* tp_new */ + PyObject_GC_Del, /* tp_free */ +}; + + +/* takewhile object **********************************************************/ + +typedef struct { + PyObject_HEAD + PyObject *func; + PyObject *it; + long stop; +} takewhileobject; + +PyTypeObject takewhile_type; + +static PyObject * +takewhile_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + PyObject *func, *seq; + PyObject *it; + takewhileobject *lz; + + if (!PyArg_UnpackTuple(args, "takewhile", 2, 2, &func, &seq)) + return NULL; + + /* Get iterator. */ + it = PyObject_GetIter(seq); + if (it == NULL) + return NULL; + + /* create takewhileobject structure */ + lz = (takewhileobject *)type->tp_alloc(type, 0); + if (lz == NULL) { + Py_DECREF(it); + return NULL; + } + Py_INCREF(func); + lz->func = func; + lz->it = it; + lz->stop = 0; + + return (PyObject *)lz; +} + +static void +takewhile_dealloc(takewhileobject *lz) +{ + PyObject_GC_UnTrack(lz); + Py_XDECREF(lz->func); + Py_XDECREF(lz->it); + lz->ob_type->tp_free(lz); +} + +static int +takewhile_traverse(takewhileobject *lz, visitproc visit, void *arg) +{ + int err; + + if (lz->it) { + err = visit(lz->it, arg); + if (err) + return err; + } + if (lz->func) { + err = visit(lz->func, arg); + if (err) + return err; + } + return 0; +} + +static PyObject * +takewhile_next(takewhileobject *lz) +{ + PyObject *item, *good; + long ok; + + if (lz->stop == 1) + return NULL; + + item = PyIter_Next(lz->it); + if (item == NULL) + return NULL; + + good = PyObject_CallFunctionObjArgs(lz->func, item, NULL); + if (good == NULL) { + Py_DECREF(item); + return NULL; + } + ok = PyObject_IsTrue(good); + Py_DECREF(good); + if (ok) + return item; + Py_DECREF(item); + lz->stop = 1; + return NULL; +} + +static PyObject * +takewhile_getiter(PyObject *lz) +{ + Py_INCREF(lz); + return lz; +} + +PyDoc_STRVAR(takewhile_doc, +"takewhile(predicate, iterable) --> takewhile object\n\ +\n\ +Return successive entries from an iterable as long as the \n\ +predicate evaluates to true for each entry."); + +PyTypeObject takewhile_type = { + PyObject_HEAD_INIT(NULL) + 0, /* ob_size */ + "itertools.takewhile", /* tp_name */ + sizeof(takewhileobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)takewhile_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_compare */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | + Py_TPFLAGS_BASETYPE, /* tp_flags */ + takewhile_doc, /* tp_doc */ + (traverseproc)takewhile_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)takewhile_getiter, /* tp_iter */ + (iternextfunc)takewhile_next, /* tp_iternext */ + 0, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + 0, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + 0, /* tp_dictoffset */ + 0, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + takewhile_new, /* tp_new */ + PyObject_GC_Del, /* tp_free */ +}; + + +/* islice object ************************************************************/ + +typedef struct { + PyObject_HEAD + PyObject *it; + long next; + long stop; + long step; + long cnt; +} isliceobject; + +PyTypeObject islice_type; + +static PyObject * +islice_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + PyObject *seq; + long a1=0, a2=0, a3=0, start=0, stop=0, step=1; + PyObject *it; + int numargs; + isliceobject *lz; + + numargs = PyTuple_Size(args); + if (!PyArg_ParseTuple(args, "Ol|ll:islice", &seq, &a1, &a2, &a3)) + return NULL; + + if (numargs == 2) { + stop = a1; + } else if (numargs == 3) { + start = a1; + stop = a2; + } else { + start = a1; + stop = a2; + step = a3; + } + + if (start<0 || stop<0) { + PyErr_SetString(PyExc_ValueError, + "Indices for islice() must be positive."); + return NULL; + } + + if (step<1) { + PyErr_SetString(PyExc_ValueError, + "Step must be one or larger for islice()."); + return NULL; + } + + /* Get iterator. */ + it = PyObject_GetIter(seq); + if (it == NULL) + return NULL; + + /* create isliceobject structure */ + lz = (isliceobject *)type->tp_alloc(type, 0); + if (lz == NULL) { + Py_DECREF(it); + return NULL; + } + lz->it = it; + lz->next = start; + lz->stop = stop; + lz->step = step; + lz->cnt = 0L; + + return (PyObject *)lz; +} + +static void +islice_dealloc(isliceobject *lz) +{ + PyObject_GC_UnTrack(lz); + Py_XDECREF(lz->it); + lz->ob_type->tp_free(lz); +} + +static int +islice_traverse(isliceobject *lz, visitproc visit, void *arg) +{ + if (lz->it) + return visit(lz->it, arg); + return 0; +} + +static PyObject * +islice_next(isliceobject *lz) +{ + PyObject *item; + + while (lz->cnt < lz->next) { + item = PyIter_Next(lz->it); + if (item == NULL) + return NULL; + Py_DECREF(item); + lz->cnt++; + } + if (lz->cnt >= lz->stop) + return NULL; + item = PyIter_Next(lz->it); + if (item == NULL) + return NULL; + lz->cnt++; + lz->next += lz->step; + return item; +} + +static PyObject * +islice_getiter(PyObject *lz) +{ + Py_INCREF(lz); + return lz; +} + +PyDoc_STRVAR(islice_doc, +"islice(iterable, [start,] stop [, step]) --> islice object\n\ +\n\ +Return an iterator whose next() method returns selected values from an\n\ +iterable. If start is specified, will skip all preceding elements;\n\ +otherwise, start defaults to zero. Step defaults to one. If\n\ +specified as another value, step determines how many values are \n\ +skipped between successive calls. Works like a slice() on a list\n\ +but returns an iterator."); + +PyTypeObject islice_type = { + PyObject_HEAD_INIT(NULL) + 0, /* ob_size */ + "itertools.islice", /* tp_name */ + sizeof(isliceobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)islice_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_compare */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | + Py_TPFLAGS_BASETYPE, /* tp_flags */ + islice_doc, /* tp_doc */ + (traverseproc)islice_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)islice_getiter, /* tp_iter */ + (iternextfunc)islice_next, /* tp_iternext */ + 0, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + 0, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + 0, /* tp_dictoffset */ + 0, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + islice_new, /* tp_new */ + PyObject_GC_Del, /* tp_free */ +}; + + +/* starmap object ************************************************************/ + +typedef struct { + PyObject_HEAD + PyObject *func; + PyObject *it; +} starmapobject; + +PyTypeObject starmap_type; + +static PyObject * +starmap_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + PyObject *func, *seq; + PyObject *it; + starmapobject *lz; + + if (!PyArg_UnpackTuple(args, "starmap", 2, 2, &func, &seq)) + return NULL; + + /* Get iterator. */ + it = PyObject_GetIter(seq); + if (it == NULL) + return NULL; + + /* create starmapobject structure */ + lz = (starmapobject *)type->tp_alloc(type, 0); + if (lz == NULL) { + Py_DECREF(it); + return NULL; + } + Py_INCREF(func); + lz->func = func; + lz->it = it; + + return (PyObject *)lz; +} + +static void +starmap_dealloc(starmapobject *lz) +{ + PyObject_GC_UnTrack(lz); + Py_XDECREF(lz->func); + Py_XDECREF(lz->it); + lz->ob_type->tp_free(lz); +} + +static int +starmap_traverse(starmapobject *lz, visitproc visit, void *arg) +{ + int err; + + if (lz->it) { + err = visit(lz->it, arg); + if (err) + return err; + } + if (lz->func) { + err = visit(lz->func, arg); + if (err) + return err; + } + return 0; +} + +static PyObject * +starmap_next(starmapobject *lz) +{ + PyObject *args; + PyObject *result; + + args = PyIter_Next(lz->it); + if (args == NULL) + return NULL; + result = PyObject_Call(lz->func, args, NULL); + Py_DECREF(args); + return result; +} + +static PyObject * +starmap_getiter(PyObject *lz) +{ + Py_INCREF(lz); + return lz; +} + +PyDoc_STRVAR(starmap_doc, +"starmap(function, sequence) --> starmap object\n\ +\n\ +Return an iterator whose values are returned from the function evaluated\n\ +with a argument tuple taken from the given sequence."); + +PyTypeObject starmap_type = { + PyObject_HEAD_INIT(NULL) + 0, /* ob_size */ + "itertools.starmap", /* tp_name */ + sizeof(starmapobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)starmap_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_compare */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | + Py_TPFLAGS_BASETYPE, /* tp_flags */ + starmap_doc, /* tp_doc */ + (traverseproc)starmap_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)starmap_getiter, /* tp_iter */ + (iternextfunc)starmap_next, /* tp_iternext */ + 0, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + 0, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + 0, /* tp_dictoffset */ + 0, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + starmap_new, /* tp_new */ + PyObject_GC_Del, /* tp_free */ +}; + + +/* imap object ************************************************************/ + +typedef struct { + PyObject_HEAD + PyObject *iters; + PyObject *argtuple; + PyObject *func; +} imapobject; + +PyTypeObject imap_type; + +static PyObject * +imap_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + PyObject *it, *iters, *argtuple, *func; + imapobject *lz; + int numargs, i; + + numargs = PyTuple_Size(args); + if (numargs < 2) { + PyErr_SetString(PyExc_TypeError, + "imap() must have at least two arguments."); + return NULL; + } + + iters = PyTuple_New(numargs-1); + if (iters == NULL) + return NULL; + + argtuple = PyTuple_New(numargs-1); + if (argtuple == NULL) { + Py_DECREF(iters); + return NULL; + } + + for (i=1 ; i<numargs ; i++) { + /* Get iterator. */ + it = PyObject_GetIter(PyTuple_GET_ITEM(args, i)); + if (it == NULL) { + Py_DECREF(argtuple); + Py_DECREF(iters); + return NULL; + } + PyTuple_SET_ITEM(iters, i-1, it); + Py_INCREF(Py_None); + PyTuple_SET_ITEM(argtuple, i-1, Py_None); + } + + /* create imapobject structure */ + lz = (imapobject *)type->tp_alloc(type, 0); + if (lz == NULL) { + Py_DECREF(argtuple); + Py_DECREF(iters); + return NULL; + } + lz->iters = iters; + lz->argtuple = argtuple; + func = PyTuple_GET_ITEM(args, 0); + Py_INCREF(func); + lz->func = func; + + return (PyObject *)lz; +} + +static void +imap_dealloc(imapobject *lz) +{ + PyObject_GC_UnTrack(lz); + Py_XDECREF(lz->argtuple); + Py_XDECREF(lz->iters); + Py_XDECREF(lz->func); + lz->ob_type->tp_free(lz); +} + +static int +imap_traverse(imapobject *lz, visitproc visit, void *arg) +{ + int err; + + if (lz->iters) { + err = visit(lz->iters, arg); + if (err) + return err; + } + if (lz->argtuple) { + err = visit(lz->argtuple, arg); + if (err) + return err; + } + if (lz->func) { + err = visit(lz->func, arg); + if (err) + return err; + } + return 0; +} + +static PyObject * +imap_next(imapobject *lz) +{ + PyObject *val; + PyObject *argtuple=lz->argtuple; + int numargs, i; + + numargs = PyTuple_Size(lz->iters); + if (lz->func == Py_None) { + argtuple = PyTuple_New(numargs); + if (argtuple == NULL) + return NULL; + + for (i=0 ; i<numargs ; i++) { + val = PyIter_Next(PyTuple_GET_ITEM(lz->iters, i)); + if (val == NULL) { + Py_DECREF(argtuple); + return NULL; + } + PyTuple_SET_ITEM(argtuple, i, val); + } + return argtuple; + } else { + for (i=0 ; i<numargs ; i++) { + val = PyIter_Next(PyTuple_GET_ITEM(lz->iters, i)); + if (val == NULL) + return NULL; + Py_DECREF(PyTuple_GET_ITEM(argtuple, i)); + PyTuple_SET_ITEM(argtuple, i, val); + } + return PyObject_Call(lz->func, argtuple, NULL); + } +} + +static PyObject * +imap_getiter(PyObject *lz) +{ + Py_INCREF(lz); + return lz; +} + +PyDoc_STRVAR(imap_doc, +"imap(func, *iterables) --> imap object\n\ +\n\ +Make an iterator that computes the function using arguments from\n\ +each of the iterables. Like map() except that it returns\n\ +an iterator instead of a list and that it stops when the shortest\n\ +iterable is exhausted instead of filling in None for shorter\n\ +iterables."); + +PyTypeObject imap_type = { + PyObject_HEAD_INIT(NULL) + 0, /* ob_size */ + "itertools.imap", /* tp_name */ + sizeof(imapobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)imap_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_compare */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | + Py_TPFLAGS_BASETYPE, /* tp_flags */ + imap_doc, /* tp_doc */ + (traverseproc)imap_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)imap_getiter, /* tp_iter */ + (iternextfunc)imap_next, /* tp_iternext */ + 0, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + 0, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + 0, /* tp_dictoffset */ + 0, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + imap_new, /* tp_new */ + PyObject_GC_Del, /* tp_free */ +}; + + +/* times object ************************************************************/ + +typedef struct { + PyObject_HEAD + PyObject *obj; + long cnt; +} timesobject; + +PyTypeObject times_type; + +static PyObject * +times_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + timesobject *lz; + PyObject *obj = Py_None; + long cnt; + + if (!PyArg_ParseTuple(args, "l|O:times", &cnt, &obj)) + return NULL; + + if (cnt < 0) { + PyErr_SetString(PyExc_ValueError, + "count for imap() cannot be negative."); + return NULL; + } + + /* create timesobject structure */ + lz = (timesobject *)type->tp_alloc(type, 0); + if (lz == NULL) + return NULL; + lz->cnt = cnt; + Py_INCREF(obj); + lz->obj = obj; + + return (PyObject *)lz; +} + +static void +times_dealloc(timesobject *lz) +{ + PyObject_GC_UnTrack(lz); + Py_XDECREF(lz->obj); + lz->ob_type->tp_free(lz); +} + +static PyObject * +times_next(timesobject *lz) +{ + PyObject *obj = lz->obj; + + if (lz->cnt > 0) { + lz->cnt--; + Py_INCREF(obj); + return obj; + } + return NULL; +} + +static PyObject * +times_getiter(PyObject *lz) +{ + Py_INCREF(lz); + return lz; +} + +PyDoc_STRVAR(times_doc, +"times(n [,obj]) --> times object\n\ +\n\ +Return a times object whose .next() method returns n consecutive\n\ +instances of obj (default is None)."); + +PyTypeObject times_type = { + PyObject_HEAD_INIT(NULL) + 0, /* ob_size */ + "itertools.times", /* tp_name */ + sizeof(timesobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)times_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_compare */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | + Py_TPFLAGS_BASETYPE, /* tp_flags */ + times_doc, /* tp_doc */ + 0, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)times_getiter, /* tp_iter */ + (iternextfunc)times_next, /* tp_iternext */ + 0, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + 0, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + 0, /* tp_dictoffset */ + 0, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + times_new, /* tp_new */ + PyObject_GC_Del, /* tp_free */ +}; + + +/* ifilter object ************************************************************/ + +typedef struct { + PyObject_HEAD + PyObject *func; + PyObject *it; + long invert; +} ifilterobject; + +PyTypeObject ifilter_type; + +static PyObject * +ifilter_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + PyObject *func, *seq, *invert=NULL; + PyObject *it; + ifilterobject *lz; + long inv=0; + + if (!PyArg_UnpackTuple(args, "ifilter", 2, 3, &func, &seq, &invert)) + return NULL; + + if (invert != NULL && PyObject_IsTrue(invert)) + inv = 1; + + /* Get iterator. */ + it = PyObject_GetIter(seq); + if (it == NULL) + return NULL; + + /* create ifilterobject structure */ + lz = (ifilterobject *)type->tp_alloc(type, 0); + if (lz == NULL) { + Py_DECREF(it); + return NULL; + } + Py_INCREF(func); + lz->func = func; + lz->it = it; + lz->invert = inv; + + return (PyObject *)lz; +} + +static void +ifilter_dealloc(ifilterobject *lz) +{ + PyObject_GC_UnTrack(lz); + Py_XDECREF(lz->func); + Py_XDECREF(lz->it); + lz->ob_type->tp_free(lz); +} + +static int +ifilter_traverse(ifilterobject *lz, visitproc visit, void *arg) +{ + int err; + + if (lz->it) { + err = visit(lz->it, arg); + if (err) + return err; + } + if (lz->func) { + err = visit(lz->func, arg); + if (err) + return err; + } + return 0; +} + +static PyObject * +ifilter_next(ifilterobject *lz) +{ + PyObject *item; + long ok; + + for (;;) { + item = PyIter_Next(lz->it); + if (item == NULL) + return NULL; + + if (lz->func == Py_None) { + ok = PyObject_IsTrue(item); + } else { + PyObject *good; + good = PyObject_CallFunctionObjArgs(lz->func, + item, NULL); + if (good == NULL) { + Py_DECREF(item); + return NULL; + } + ok = PyObject_IsTrue(good); + Py_DECREF(good); + } + if (ok ^ lz->invert) + return item; + Py_DECREF(item); + } +} + +static PyObject * +ifilter_getiter(PyObject *lz) +{ + Py_INCREF(lz); + return lz; +} + +PyDoc_STRVAR(ifilter_doc, +"ifilter(function or None, sequence [, invert]) --> ifilter object\n\ +\n\ +Return those items of sequence for which function(item) is true. If\n\ +invert is set to True, return items for which function(item) if False.\n\ +If function is None, return the items that are true (unless invert is set)."); + +PyTypeObject ifilter_type = { + PyObject_HEAD_INIT(NULL) + 0, /* ob_size */ + "itertools.ifilter", /* tp_name */ + sizeof(ifilterobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)ifilter_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_compare */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | + Py_TPFLAGS_BASETYPE, /* tp_flags */ + ifilter_doc, /* tp_doc */ + (traverseproc)ifilter_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)ifilter_getiter, /* tp_iter */ + (iternextfunc)ifilter_next, /* tp_iternext */ + 0, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + 0, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + 0, /* tp_dictoffset */ + 0, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + ifilter_new, /* tp_new */ + PyObject_GC_Del, /* tp_free */ +}; + + +/* count object ************************************************************/ + +typedef struct { + PyObject_HEAD + long cnt; +} countobject; + +PyTypeObject count_type; + +static PyObject * +count_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + countobject *lz; + long cnt = 0; + + if (!PyArg_ParseTuple(args, "|l:count", &cnt)) + return NULL; + + /* create countobject structure */ + lz = (countobject *)PyObject_New(countobject, &count_type); + if (lz == NULL) + return NULL; + lz->cnt = cnt; + + return (PyObject *)lz; +} + +static PyObject * +count_next(countobject *lz) +{ + return PyInt_FromLong(lz->cnt++); +} + +static PyObject * +count_getiter(PyObject *lz) +{ + Py_INCREF(lz); + return lz; +} + +PyDoc_STRVAR(count_doc, +"count([firstval]) --> count object\n\ +\n\ +Return a count object whose .next() method returns consecutive\n\ +integers starting from zero or, if specified, from firstval."); + +PyTypeObject count_type = { + PyObject_HEAD_INIT(NULL) + 0, /* ob_size */ + "itertools.count", /* tp_name */ + sizeof(countobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)PyObject_Del, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_compare */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT, /* tp_flags */ + count_doc, /* tp_doc */ + 0, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)count_getiter, /* tp_iter */ + (iternextfunc)count_next, /* tp_iternext */ + 0, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + 0, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + 0, /* tp_dictoffset */ + 0, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + count_new, /* tp_new */ +}; + + +/* izip object ************************************************************/ + +#include "Python.h" + +typedef struct { + PyObject_HEAD + long tuplesize; + PyObject *ittuple; /* tuple of iterators */ +} izipobject; + +PyTypeObject izip_type; + +static PyObject * +izip_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + izipobject *lz; + int i; + PyObject *ittuple; /* tuple of iterators */ + int tuplesize = PySequence_Length(args); + + if (tuplesize < 1) { + PyErr_SetString(PyExc_TypeError, + "izip() requires at least one sequence"); + return NULL; + } + + /* args must be a tuple */ + assert(PyTuple_Check(args)); + + /* obtain iterators */ + ittuple = PyTuple_New(tuplesize); + if(ittuple == NULL) + return NULL; + for (i=0; i < tuplesize; ++i) { + PyObject *item = PyTuple_GET_ITEM(args, i); + PyObject *it = PyObject_GetIter(item); + if (it == NULL) { + if (PyErr_ExceptionMatches(PyExc_TypeError)) + PyErr_Format(PyExc_TypeError, + "izip argument #%d must support iteration", + i+1); + Py_DECREF(ittuple); + return NULL; + } + PyTuple_SET_ITEM(ittuple, i, it); + } + + /* create izipobject structure */ + lz = (izipobject *)type->tp_alloc(type, 0); + if (lz == NULL) { + Py_DECREF(ittuple); + return NULL; + } + lz->ittuple = ittuple; + lz->tuplesize = tuplesize; + + return (PyObject *)lz; +} + +static void +izip_dealloc(izipobject *lz) +{ + PyObject_GC_UnTrack(lz); + Py_XDECREF(lz->ittuple); + lz->ob_type->tp_free(lz); +} + +static int +izip_traverse(izipobject *lz, visitproc visit, void *arg) +{ + if (lz->ittuple) + return visit(lz->ittuple, arg); + return 0; +} + +static PyObject * +izip_next(izipobject *lz) +{ + int i; + long tuplesize = lz->tuplesize; + PyObject *result; + PyObject *it; + PyObject *item; + + result = PyTuple_New(tuplesize); + if (result == NULL) + return NULL; + + for (i=0 ; i < tuplesize ; i++) { + it = PyTuple_GET_ITEM(lz->ittuple, i); + item = PyIter_Next(it); + if (item == NULL) { + Py_DECREF(result); + return NULL; + } + PyTuple_SET_ITEM(result, i, item); + } + return result; +} + +static PyObject * +izip_getiter(PyObject *lz) +{ + Py_INCREF(lz); + return lz; +} + +PyDoc_STRVAR(izip_doc, +"izip(iter1 [,iter2 [...]]) --> izip object\n\ +\n\ +Return a izip object whose .next() method returns a tuple where\n\ +the i-th element comes from the i-th iterable argument. The .next()\n\ +method continues until the shortest iterable in the argument sequence\n\ +is exhausted and then it raises StopIteration. Works like the zip()\n\ +function but consumes less memory by returning an iterator instead of\n\ +a list."); + +PyTypeObject izip_type = { + PyObject_HEAD_INIT(NULL) + 0, /* ob_size */ + "itertools.izip", /* tp_name */ + sizeof(izipobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)izip_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_compare */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | + Py_TPFLAGS_BASETYPE, /* tp_flags */ + izip_doc, /* tp_doc */ + (traverseproc)izip_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)izip_getiter, /* tp_iter */ + (iternextfunc)izip_next, /* tp_iternext */ + 0, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + 0, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + 0, /* tp_dictoffset */ + 0, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + izip_new, /* tp_new */ + PyObject_GC_Del, /* tp_free */ +}; + + +/* repeat object ************************************************************/ + +typedef struct { + PyObject_HEAD + PyObject *element; +} repeatobject; + +PyTypeObject repeat_type; + +static PyObject * +repeat_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + repeatobject *ro; + PyObject *element; + + if (!PyArg_UnpackTuple(args, "repeat", 1, 1, &element)) + return NULL; + + ro = (repeatobject *)type->tp_alloc(type, 0); + if (ro == NULL) + return NULL; + Py_INCREF(element); + ro->element = element; + return (PyObject *)ro; +} + +static void +repeat_dealloc(repeatobject *ro) +{ + PyObject_GC_UnTrack(ro); + Py_XDECREF(ro->element); + ro->ob_type->tp_free(ro); +} + +static int +repeat_traverse(repeatobject *ro, visitproc visit, void *arg) +{ + if (ro->element) + return visit(ro->element, arg); + return 0; +} + +static PyObject * +repeat_next(repeatobject *ro) +{ + Py_INCREF(ro->element); + return ro->element; +} + +static PyObject * +repeat_getiter(PyObject *ro) +{ + Py_INCREF(ro); + return ro; +} + +PyDoc_STRVAR(repeat_doc, +"repeat(element) -> create an iterator which returns the element endlessly."); + +PyTypeObject repeat_type = { + PyObject_HEAD_INIT(NULL) + 0, /* ob_size */ + "itertools.repeat", /* tp_name */ + sizeof(repeatobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)repeat_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_compare */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | + Py_TPFLAGS_BASETYPE, /* tp_flags */ + repeat_doc, /* tp_doc */ + (traverseproc)repeat_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)repeat_getiter, /* tp_iter */ + (iternextfunc)repeat_next, /* tp_iternext */ + 0, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + 0, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + 0, /* tp_dictoffset */ + 0, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + repeat_new, /* tp_new */ + PyObject_GC_Del, /* tp_free */ +}; + + +/* module level code ********************************************************/ + +PyDoc_STRVAR(module_doc, +"Functional tools for creating and using iterators.\n\ +\n\ +Infinite iterators:\n\ +count([n]) --> n, n+1, n+2, ...\n\ +repeat(elem) --> elem, elem, elem, ...\n\ +\n\ +Iterators terminating on the shortest input sequence:\n\ +izip(p, q, ...) --> (p[0], q[0]), (p[1], q[1]), ... \n\ +ifilter(pred, seq, invert=False) --> elements of seq where\n\ + pred(elem) is True (or False if invert is set)\n\ +islice(seq, [start,] stop [, step]) --> elements from\n\ + seq[start:stop:step]\n\ +imap(fun, p, q, ...) --> fun(p0, q0), fun(p1, q1), ...\n\ +starmap(fun, seq) --> fun(*seq[0]), fun(*seq[1]), ...\n\ +times(n, [obj]) --> obj, obj, ... for n times. obj defaults to None\n\ +takewhile(pred, seq) --> seq[0], seq[1], until pred fails\n\ +dropwhile(pred, seq) --> seq[n], seq[n+1], starting when pred fails\n\ +"); + + +PyMODINIT_FUNC +inititertools(void) +{ + PyObject *m; + m = Py_InitModule3("itertools", NULL, module_doc); + + PyModule_AddObject(m, "dropwhile", (PyObject *)&dropwhile_type); + if (PyType_Ready(&dropwhile_type) < 0) + return; + Py_INCREF(&dropwhile_type); + + PyModule_AddObject(m, "takewhile", (PyObject *)&takewhile_type); + if (PyType_Ready(&takewhile_type) < 0) + return; + Py_INCREF(&takewhile_type); + + PyModule_AddObject(m, "islice", (PyObject *)&islice_type); + if (PyType_Ready(&islice_type) < 0) + return; + Py_INCREF(&islice_type); + + PyModule_AddObject(m, "starmap", (PyObject *)&starmap_type); + if (PyType_Ready(&starmap_type) < 0) + return; + Py_INCREF(&starmap_type); + + PyModule_AddObject(m, "imap", (PyObject *)&imap_type); + if (PyType_Ready(&imap_type) < 0) + return; + Py_INCREF(&imap_type); + + PyModule_AddObject(m, "times", (PyObject *)×_type); + if (PyType_Ready(×_type) < 0) + return; + Py_INCREF(×_type); + + if (PyType_Ready(&ifilter_type) < 0) + return; + Py_INCREF(&ifilter_type); + PyModule_AddObject(m, "ifilter", (PyObject *)&ifilter_type); + + if (PyType_Ready(&count_type) < 0) + return; + Py_INCREF(&count_type); + PyModule_AddObject(m, "count", (PyObject *)&count_type); + + if (PyType_Ready(&izip_type) < 0) + return; + Py_INCREF(&izip_type); + PyModule_AddObject(m, "izip", (PyObject *)&izip_type); + + if (PyType_Ready(&repeat_type) < 0) + return; + Py_INCREF(&repeat_type); + PyModule_AddObject(m, "repeat", (PyObject *)&repeat_type); +} diff --git a/PC/config.c b/PC/config.c index b20831d..717f267 100644 --- a/PC/config.c +++ b/PC/config.c @@ -45,6 +45,7 @@ extern void init_hotshot(void); extern void initxxsubtype(void); extern void initzipimport(void); extern void init_random(void); +extern void inititertools(void); /* XXX tim: what's the purpose of ADDMODULE MARKER? */ /* -- ADDMODULE MARKER 1 -- */ @@ -97,6 +98,7 @@ struct _inittab _PyImport_Inittab[] = { {"_weakref", init_weakref}, {"_hotshot", init_hotshot}, {"_random", init_random}, + {"itertools", inititertools}, {"xxsubtype", initxxsubtype}, {"zipimport", initzipimport}, diff --git a/PCbuild/pythoncore.dsp b/PCbuild/pythoncore.dsp index 5a84506..adcb706 100644 --- a/PCbuild/pythoncore.dsp +++ b/PCbuild/pythoncore.dsp @@ -323,6 +323,10 @@ SOURCE=..\Objects\iterobject.c # End Source File
# Begin Source File
+SOURCE=..\Modules\itertoolsmodule.c
+# End Source File
+# Begin Source File
+
SOURCE=..\Parser\listnode.c
# End Source File
# Begin Source File
@@ -324,6 +324,8 @@ class PyBuildExt(build_ext): libraries=math_libs) ) # random number generator implemented in C exts.append( Extension("_random", ["_randommodule.c"]) ) + # fast iterator tools implemented in C + exts.append( Extension("itertools", ["itertoolsmodule.c"]) ) # operator.add() and similar goodies exts.append( Extension('operator', ['operator.c']) ) # Python C API test module |