Given IComparer, Zip two ordered IEnumerable-s, pairing only equal elements?

Question

I need to iterate two ordered IEnumerable-s, a and b, ordered by a given IComparer, "side-by-side", and Zip equal elements (equal according to the same IComparer).

I need to Zip all the elements without a match in the other collection with null (or default value, whatever).

By Zipping I mean "return a collection of f() call results, where f() is a given closure taking 2 parameters, one from a and one from b".

a and b can have different amount of elements, and don't have to match 1:1.

For example:

IComparer comparer = ...;

int[] a = { 1, 2, 4, 7, 7 };
int[] b = { -1, 1, 3, 4, 7, 8 };

var zipped = EvenMoreLinq.ZipEqual(a, b, comparer, (a, b) => new int[]{ a, b });

I expect zipped to be:

{ {0, -1}, {1, 1}, {2, 0}, {0, 3}, {4, 4}, {7, 7}, {7, 0}, {0, 8} };

Equal elements in a and b should be matched as much as there is a matching element in the other collection.

It is desirable for output collection to maintain the source order.

Does a library implementation of such exist?

Answer 1

EDIT

The grouping can be avoided but the result is obviously similar to Daniel's answer.

public static IEnumerable<Tuple<T, T>> ZipEqual<T>(
    this IEnumerable<T> source,
    IEnumerable<T> other,
    IComparer<T> comparer = null)
{
    if (other == null)
    {
        throw new ArgumentNullException("other");
    }

    if (comparer == null)
    {
        comparer = Comparer<T>.Default;
    }

    var first = source.OrderBy(t => t, comparer).GetEnumerator();
    var second = other.OrderBy(t => t, comparer).GetEnumerator();

    var firstMore = first.MoveNext();
    var secondMore = second.MoveNext();

    while (firstMore && secondMore)
    {
        var comp = comparer.Compare(first.Current, second.Current);

        if (comp == 0)
        {
            yield return Tuple.Create(first.Current, second.Current);
            firstMore = first.MoveNext();
            secondMore = second.MoveNext();
            continue;
        }

        if (comp > 0)
        {
             yield return Tuple.Create(default(T), second.Current);
             secondMore = second.MoveNext();
             continue;
        }

        yield return Tuple.Create(first.Current, default(T));
        firstMore = first.MoveNext();
    }

    while (firstMore)
    {
        yield return Tuple.Create(first.Current, default(T));
        firstMore = first.MoveNext();
    }

    while (secondMore)
    {
        yield return Tuple.Create(default(T), second.Current);
        secondMore = second.MoveNext();
    }
}

---

How about,

public static IEnumerable<Tuple<T, T>> ZipEqual<T>(
    this IEnumerable<T> source,
    IEnumerable<T> other,
    IComparer<T> comparer = null)
{
    if (other == null)
    {
        throw new ArgumentNullException("other");
    }

    if (comparer == null)
    {
        comparer = Comparer<T>.Default;
    }

    var orderedGroups =
        source.Select(t => new { Value = t, First = true })
            .Concat(other.Select(t => new { Value = t, First = false }))
            .ToLookup(a => a.Value)
            .OrderBy(l => l.Key, comparer);

    foreach (var group in orderedGroups)
    {
        var firsts = group.Where(a => a.First).Select(a => a.Value).ToList();
        var seconds = group.Where(a => !a.First).Select(a => a.Value).ToList();

        var limit = Math.Max(firsts.Count, seconds.Count);
        for (var i = 0; i < limit; i++)
        {
            yield return Tuple.Create(
                firsts.ElementAtOrDefault(i),
                seconds.ElementAtorDefault(i));
        }
    }
}

Answer 2

Assuming the answer to Jon's comment is "Yes", an implementation could look like this:

public static IEnumerable<TResult> ZipEqual<TFirst, TSecond, TResult>(
    this IEnumerable<TFirst> first, IEnumerable<TSecond> second,
    Func<TFirst, TSecond, TResult> resultSelector,
    IComparer comparer)
{
    var enumerator1 = first.GetEnumerator();
    var enumerator2 = second.GetEnumerator();

    var enumerator1HasElement = enumerator1.MoveNext();
    var enumerator2HasElement = enumerator2.MoveNext();

    while(enumerator1HasElement || enumerator2HasElement)
    {
        if(!enumerator2HasElement)
        {
            yield return resultSelector(enumerator1.Current, default(TSecond));
            enumerator1HasElement = enumerator1.MoveNext();
        }
        else if(!enumerator1HasElement)
        {
            yield return resultSelector(default(TFirst), enumerator2.Current);
            enumerator2HasElement = enumerator2.MoveNext();
        }
        else
        {
            var compareResult = comparer.Compare(enumerator1.Current,
                                                 enumerator2.Current);
            if(compareResult == 0)
            {
                yield return resultSelector(enumerator1.Current,
                                            enumerator2.Current);
                enumerator1HasElement = enumerator1.MoveNext();
                enumerator2HasElement = enumerator2.MoveNext();
            }
            else if(compareResult < 0)
            {
                yield return resultSelector(enumerator1.Current,
                                            default(TSecond));
                enumerator1HasElement = enumerator1.MoveNext();
            }
            else
            {
                yield return resultSelector(default(TFirst),
                                            enumerator2.Current);
                enumerator2HasElement = enumerator2.MoveNext();
            }
        }
    }
}