Move itertools module from the sandbox and into production.

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)
diff --git a/Misc/NEWS b/Misc/NEWS
index 38e7db2..c0aa976 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -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 *)&times_type);
+	if (PyType_Ready(&times_type) < 0)
+		return;
+	Py_INCREF(&times_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

diff --git a/setup.py b/setup.py
index 346f026..6f2d34e 100644
--- a/setup.py
+++ b/setup.py
@@ -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