Move itertools module from the sandbox and into production.
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 @@
\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}{[email protected]}
+\sectionauthor{Raymond Hettinger}{[email protected]}
+\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)
diff --git a/Misc/NEWS b/Misc/NEWS
index 38e7db2..c0aa976 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -30,6 +30,9 @@
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 <[email protected]>
+ 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 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 @@
{"_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 @@
# 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
diff --git a/setup.py b/setup.py
index 346f026..6f2d34e 100644
--- a/setup.py
+++ b/setup.py
@@ -324,6 +324,8 @@
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
