from __future__ import generators

def chain(*iterables):
    """Make an iterator that returns elements from the first iterable
    until it is exhausted, then proceeds to the next iterable, until
    all of the iterables are exhausted. Used for treating consecutive
    sequences as a single sequence."""
    for it in iterables:
        for element in it:
            yield element

def count(n=0):
    """Make an iterator that returns consecutive integers starting
    with n. If not specified n defaults to zero. Does not currently
    support python long integers. Often used as an argument to imap()
    to generate consecutive data points. Also, used with izip() to add
    sequence numbers.

    Note, count() does not check for overflow and will return negative
    numbers after exceeding sys.maxint. This behavior may change in
    the future.
    """
    while True:
        yield n
        n += 1

def cycle(iterable):
    """Make an iterator returning elements from the iterable and
    saving a copy of each. When the iterable is exhausted, return
    elements from the saved copy. Repeats indefinitely.

    Note, this member of the toolkit may require significant auxiliary
    storage (depending on the length of the iterable)."""
    saved = []
    for element in iterable:
        yield element
        saved.append(element)
    while saved:
        for element in saved:
            yield element

def 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 any output until
     the predicate is true, so it may have a lengthy start-up
     time."""
     iterable = iter(iterable)
     for x in iterable:
         if not predicate(x):
             yield x
             break
     for x in iterable:
         yield x

class groupby(object):
    """Make an iterator that returns consecutive keys and groups from
    the iterable. The key is a function computing a key value for each
    element. If not specified or is None, key defaults to an identity
    function and returns the element unchanged. Generally, the
    iterable needs to already be sorted on the same key function.

    The returned group is itself an iterator that shares the
    underlying iterable with groupby(). Because the source is shared,
    when the groupby object is advanced, the previous group is no
    longer visible. So, if that data is needed later, it should be
    stored as a list:

    groups = []
    uniquekeys = []
    for k, g in groupby(data, keyfunc):
        groups.append(list(g)) # Store group iterator as a list
        uniquekeys.append(k)
    """
    def __init__(self, iterable, key=None):
        if key is None:
            key = lambda x: x
        self.keyfunc = key
        self.it = iter(iterable)
        self.tgtkey = self.currkey = self.currvalue = xrange(0)
    def __iter__(self):
        return self
    def next(self):
        while self.currkey == self.tgtkey:
            self.currvalue = self.it.next() # Exit on StopIteration
            self.currkey = self.keyfunc(self.currvalue)
        self.tgtkey = self.currkey
        return (self.currkey, self._grouper(self.tgtkey))
    def _grouper(self, tgtkey):
        while self.currkey == tgtkey:
            yield self.currvalue
            self.currvalue = self.it.next() # Exit on StopIteration
            self.currkey = self.keyfunc(self.currvalue)

def ifilter(predicate, iterable):
    """Make an iterator that filters elements from iterable returning
    only those for which the predicate is True. If predicate is None,
    return the items that are true."""
    if predicate is None:
        predicate = bool
    for x in iterable:
        if predicate(x):
            yield x

def ifilterfalse(predicate, iterable):
    """Make an iterator that filters elements from iterable returning
    only those for which the predicate is False. If predicate is None,
    return the items that are false."""
    if predicate is None:
        predicate = bool
    for x in iterable:
        if not predicate(x):
            yield x

def imap(function, *iterables):
    """Make an iterator that computes the function using arguments
    from each of the iterables. If function is set to None, then
    imap() returns the arguments as a tuple. Like map() but stops when
    the shortest iterable is exhausted instead of filling in None for
    shorter iterables. The reason for the difference is that infinite
    iterator arguments are typically an error for map() (because the
    output is fully evaluated) but represent a common and useful way
    of supplying arguments to imap()."""
    iterables = map(iter, iterables)
    while True:
        args = [i.next() for i in iterables]
        if function is None:
            yield tuple(args)
        else:
            yield function(*args)

def islice(iterable, *args):
    """Make an iterator that returns selected elements from the
    iterable. If start is non-zero, then elements from the iterable
    are skipped until start is reached. Afterward, elements are
    returned consecutively unless step is set higher than one which
    results in items being skipped. If stop is None, then iteration
    continues until the iterator is exhausted, if at all; otherwise,
    it stops at the specified position. Unlike regular slicing,
    islice() does not support negative values for start, stop, or
    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)."""
    s = slice(*args)
    it = iter(xrange(s.start or 0, s.stop or sys.maxint, s.step or 1))
    nexti = it.next()
    for i, element in enumerate(iterable):
        if i == nexti:
            yield element
            nexti = it.next()

def izip(*iterables):
    """Make an iterator that aggregates elements from each of the
    iterables. Like zip() except that it returns an iterator instead
    of a list. Used for lock-step iteration over several iterables at
    a time. When no iterables are specified, returns a zero length
    iterator."""
    iterables = map(iter, iterables)
    while iterables:
        result = [i.next() for i in iterables]
        yield tuple(result)

def repeat(object, times=None):
    """Make an iterator that returns object over and over again. Runs
    indefinitely unless the times argument is specified. Used as
    argument to imap() for invariant parameters to the called
    function. Also used with izip() to create an invariant part of a
    tuple record."""
    if times is None:
        while True:
            yield object
    else:
        for i in xrange(times):
            yield object

def starmap(function, iterable):
    """Make an iterator that computes the function using arguments
    tuples obtained from the iterable. Used instead of imap() when
    argument parameters are already grouped in tuples from a single
    iterable (the data has been ``pre-zipped''). The difference
    between imap() and starmap() parallels the distinction between
    function(a,b) and function(*c)."""
    iterable = iter(iterable)
    while True:
        yield function(*iterable.next())

def takewhile(predicate, iterable):
    """Make an iterator that returns elements from the iterable as
    long as the predicate is true."""
    for x in iterable:
        if predicate(x):
            yield x
        else:
            break