# Misc iterator tools

# Iterator merging, based on http://code.activestate.com/recipes/491285/
import heapq


def imerge(*iterables):
    '''Merge multiple sorted inputs into a single sorted output.

    Equivalent to:  sorted(itertools.chain(*iterables))

    >>> list(imerge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25]))
    [0, 1, 2, 3, 4, 5, 5, 7, 8, 10, 15, 20, 25]

    '''
    heappop, siftup, _Stop = heapq.heappop, heapq._siftup, StopIteration

    h = []
    h_append = h.append
    for it in map(iter, iterables):
        try:
            nexter = it.__next__
            h_append([nexter(), nexter])
        except _Stop:
            pass
    heapq.heapify(h)

    while 1:
        try:
            while 1:
                v, nexter = s = h[0]    # raises IndexError when h is empty
                yield v
                s[0] = nexter()         # raises StopIteration when exhausted
                siftup(h, 0)            # restore heap condition
        except _Stop:
            heappop(h)                  # remove empty iterator
        except IndexError:
            return
