Q:

Merge two sorted iterators without replace

I need to merge two iterators. I wrote this function:
def merge_no_repeat(iter1, iter2, key=None):
    """
    a = iter([(2, 'a'), (4, 'a'), (6, 'a')])
    b = iter([(1, 'b'), (2, 'b'), (3, 'b'), (4, 'b'), (5, 'b'), (6, 'b'), (7, 'b'), (8, 'b')])
    key = lambda item: item[0]
    fusion_no_repeat(a, b, key) ->
                iter([(1, 'b'), (2, 'a'), (3, 'b'), (4, 'a'), (5, 'b'), (6, 'a'), (7, 'b'), (8, 'b')])
    :param iter1: sorted iterator
    :param iter2: sorted iterator
    :param key: lambda get sorted key, default: lambda x: x
    :return: merged iterator
    """
    if key is None:
        key = lambda x: x
    element1 = next(iter1, None)
    element2 = next(iter2, None)
    while element1 is not None or element2 is not None:
        if element1 is None:
            yield element2
            element2 = next(iter2, None)
        elif element2 is None:
            yield element1
            element1 = next(iter1, None)
        elif key(element1) > key(element2):
            yield element2
            element2 = next(iter2, None)
        elif key(element1) == key(element2):
            yield element1
            element1 = next(iter1, None)
            element2 = next(iter2, None)
        elif key(element1) < key(element2):
            yield element1
            element1 = next(iter1, None)

This function works. But I think it's too complicated. Is it possible to make this function easiest using Python Standard Libraries?

A:

You can use:
def merge_no_repeat(iter1, iter2, key=None):
    if key is None:
        key = lambda x: x
    ref = next(iter1, None)
    for elem in iter2:
        key_elem = key(elem) # caching value so we won't compute it for each value in iter1 that is before this one
        while ref is not None and key_elem > key(ref):
            # Catch up with low values from iter1
            yield ref
            ref = next(iter1, None)
        if ref is None or key_elem < key(ref):
            # Catch up with low values from iter2, eliminate duplicates
            yield elem
    # Update: I forgot to consume iter1 in the first version of this code
    for elem in iter1:
        # Use remaining items of iter1 if needed
        yield elem

I assumed that the iterators wouldn't return None values except when completely consumed, since you have if element1 is None: and elif element1 is None: tests in your original code.

Examples:
>>> from operator import itemgetter
>>> list(merge_no_repeat(
...     iter([(2, 'a'), (4, 'a'), (6, 'a')]),
...     iter([(1, 'b')]),
...     itemgetter(0)))
[(1, 'b'), (2, 'a'), (4, 'a'), (6, 'a')]
>>> list(merge_no_repeat(
...     iter([(2, 'a'), (4, 'a'), (6, 'a')]),
...     iter([(1, 'b'),(7, 'b'), (8, 'b')]),
...     itemgetter(0)))
[(1, 'b'), (2, 'a'), (4, 'a'), (6, 'a'), (7, 'b'), (8, 'b')]
>>> list(merge_no_repeat(
...     iter([(2, 'a'), (4, 'a'), (6, 'a')]),
...     iter([(1, 'b'),(3, 'b'), (4,'b'),(5,'b'),(7, 'b'), (8, 'b')]),
...     itemgetter(0)))
[(1, 'b'), (2, 'a'), (3, 'b'), (4, 'a'), (5, 'b'), (6, 'a'), (7, 'b'), (8, 'b')]

