N-shaped intersection of sorted enumerations

Question

Given n enumerations of the same type that return individual elements in ascending order, for example:

IEnumerable<char> s1 = "adhjlstxyz";
IEnumerable<char> s2 = "bdeijmnpsz";
IEnumerable<char> s3 = "dejlnopsvw";

I want to efficiently find all values ​​that are elements of all enumerations:

IEnumerable<char> sx = Intersect(new[] { s1, s2, s3 });

Debug.Assert(sx.SequenceEqual("djs"));

Effectively means that

• enumerated input should be listed only once,
• input counters should only be removed if necessary and
• an algorithm should not recursively list its own output.

I need some tips on how to approach the solution.

---

Here is my (naive) attempt:

static IEnumerable<T> Intersect<T>(IEnumerable<T>[] enums)
{
    return enums[0].Intersect(
        enums.Length == 2 ? enums[1] : Intersect(enums.Skip(1).ToArray()));
}

Enumerable.Intersect HashSet, . Intersect, . , , ( ). , .

---

. , n ?

static IEnumerable<T> Intersect<T>(IEnumerable<T> first, IEnumerable<T> second)
{
    using (var left = first.GetEnumerator())
    using (var right = second.GetEnumerator())
    {
        var leftHasNext = left.MoveNext();
        var rightHasNext = right.MoveNext();

        var comparer = Comparer<T>.Default;

        while (leftHasNext && rightHasNext)
        {
            switch (Math.Sign(comparer.Compare(left.Current, right.Current)))
            {
            case -1:
                leftHasNext = left.MoveNext();
                break;
            case 0:
                yield return left.Current;
                leftHasNext = left.MoveNext();
                rightHasNext = right.MoveNext();
                break;
            case 1:
                rightHasNext = right.MoveNext();
                break;
            }
        }
    }
}

Answer 1

OK; :

public static IEnumerable<T> Intersect<T>(params IEnumerable<T>[] enums) {
    return Intersect<T>(null, enums);
}
public static IEnumerable<T> Intersect<T>(IComparer<T> comparer, params IEnumerable<T>[] enums) {
    if(enums == null) throw new ArgumentNullException("enums");
    if(enums.Length == 0) return Enumerable.Empty<T>();
    if(enums.Length == 1) return enums[0];
    if(comparer == null) comparer = Comparer<T>.Default;
    return IntersectImpl(comparer, enums);
}
public static IEnumerable<T> IntersectImpl<T>(IComparer<T> comparer, IEnumerable<T>[] enums) {
    IEnumerator<T>[] iters = new IEnumerator<T>[enums.Length];
    try {
        // create iterators and move as far as the first item
        for (int i = 0; i < enums.Length; i++) {
            if(!(iters[i] = enums[i].GetEnumerator()).MoveNext()) {
                yield break; // no data for one of the iterators
            }
        }
        bool first = true;
        T lastValue = default(T);
        do { // get the next item from the first sequence
            T value = iters[0].Current;
            if (!first && comparer.Compare(value, lastValue) == 0) continue; // dup in first source
            bool allTrue = true;
            for (int i = 1; i < iters.Length; i++) {
                var iter = iters[i];
                // if any sequence isn't there yet, progress it; if any sequence
                // ends, we're all done
                while (comparer.Compare(iter.Current, value) < 0) {
                    if (!iter.MoveNext()) goto alldone; // nasty, but
                }
                // if any sequence is now **past** value, then short-circuit
                if (comparer.Compare(iter.Current, value) > 0) {
                    allTrue = false;
                    break;
                }
            }
            // so all sequences have this value
            if (allTrue) yield return value;
            first = false;
            lastValue = value;
        } while (iters[0].MoveNext());
    alldone:
        ;
    } finally { // clean up all iterators
        for (int i = 0; i < iters.Length; i++) {
            if (iters[i] != null) {
                try { iters[i].Dispose(); }
                catch { }
            }
        }
    }
}

Answer 2

LINQ:

    public static IEnumerable<T> Intersect<T>(IEnumerable<IEnumerable<T>> enums) {
        using (var iter = enums.GetEnumerator()) {
            IEnumerable<T> result;
            if (iter.MoveNext()) {
                result = iter.Current;
                while (iter.MoveNext()) {
                    result = result.Intersect(iter.Current);
                }
            } else {
                result = Enumerable.Empty<T>();
            }
            return result;
        }
    }

simple, -; n ( ) , - ?