key_zip.py

def cmp(x, y):
    return (x > y) - (x < y)

nil = object()

def sorted_zip(xs, ys, key=lambda x: x, cmp=cmp, nil=nil):
    xs = iter(xs)
    ys = iter(ys)
    x = next(xs, nil)
    y = next(ys, nil)
    while x is not nil and y is not nil:
        c = cmp(key(x), key(y))
        if c < 0:
            yield x, nil
            x = next(xs, nil)
        elif c > 0:
            yield nil, y
            y = next(ys, nil)
        else:
            yield x, y
            x = next(xs, nil)
            y = next(ys, nil)
    while x is not nil:
        yield x, nil
        x = next(xs, nil)
    while y is not nil:
        yield nil, y
        y = next(ys, nil)

def list_merge(xs, ys):
    for x, y in sorted_zip(xs, ys):
        if x is not nil:
            yield x
        if y is not nil:
            yield y

def set_union(xs, ys):
    for x, y in sorted_zip(xs, ys):
        if x is nil:
            yield y
        else:
            yield x

def set_intersect(xs, ys):
    for x, y in sorted_zip(xs, ys):
        if x is not nil and y is not nil:
            yield x

def set_subtract(xs, ys):
    for x, y in sorted_zip(xs, ys):
        if x is not nil and y is nil:
            yield x

def vector_zip(xs, ys):
    return sorted_zip(xs, ys, key=lambda ix: ix[0])

def vector_add(xs, ys):
    for ix, iy in vector_zip(xs, ys):
        if iy is nil:
            yield ix
        elif ix is nil:
            yield iy
        else:
            i, x = ix
            i, y = iy
            z = x + y
            if z:
                yield i, z

def vector_multiply(xs, ys):
    for ix, iy in vector_zip(xs, ys):
        if ix is not nil and iy is not nil:
            i, x = ix
            i, y = iy
            yield i, x * y

def vector_dot(xs, ys):
    return sum(xy for i, xy in vector_multiply(xs, ys))

def rangeset_zip(xs, ys):
    return sorted_zip(xs, ys, cmp=lambda x, y: (x[1] > y[0]) - (y[1] > x[0]))

def rangeset_union(xs, ys):
    for x, y in rangeset_zip(xs, ys):
        if y is nil:
            yield x
        elif x is nil:
            yield y
        else:
            x1, x2 = x
            y1, y2 = y
            z1, z2 = min(x1, y1), max(x2, y2)
            if z1 < z2:
                yield z1, z2

def rangeset_intersect(xs, ys):
    for x, y in rangeset_zip(xs, ys):
        if x is not nil and y is not nil:
            x1, x2 = x
            y1, y2 = y
            z1, z2 = max(x1, y1), min(x2, y2)
            if z1 < z2:
                yield z1, z2

def rangeset_subtract(xs, ys):
    for x, y in rangeset_zip(xs, ys):
        if y is nil:
            yield x
        elif x is not nil:
            x1, x2 = x
            y1, y2 = y
            if x1 < y1:
                yield x1, y1
            if y2 < x2:
                yield y2, x2

print(list(list_merge([1, 2, 3], [0, 2, 2, 4])))                                    # [0, 1, 2, 2, 2, 3, 4]
print(list(set_union([1, 2, 3], [0, 2, 3, 4])))                                     # [0, 1, 2, 3, 4]
print(list(set_intersect([1, 2, 3], [0, 2, 3, 4])))                                 # [2, 3]
print(list(set_subtract([1, 2, 3], [0, 2, 3, 4])))                                  # [1]
print(list(vector_add([(0, 1), (3, 1), (4, 1)], [(0, 1), (1, 1), (3, -1)])))        # [(0, 2), (1, 1), (4, 1)]
print(list(vector_multiply([(0, 2), (3, 1), (4, 1)], [(0, 3), (1, 1), (2, -1)])))   # [(0, 6)]
print(vector_dot([(0, 2), (3, 1), (4, 1)], [(0, 3), (1, 1), (2, -1)]))              # 6
print(list(rangeset_union([(0, 1), (3, 4)], [(0, 2), (5, 6)])))                     # [(0, 2), (3, 4), (5, 6)]
print(list(rangeset_intersect([(0, 2), (3, 4)], [(1, 3), (5, 6)])))                 # [(1, 2)]
print(list(rangeset_subtract([(0, 2), (3, 4)], [(0, 1), (5, 6)])))                  # [(1, 2), (3, 4)]