Omer van Kloeten's .NET Zen

Linq: SequenceSuperset

Here's another Linq method I wanted to share. This one takes two enumerations, enumeration and subset and checks to see whether subset exists in enumeration in its original order. I used the naming convention set by SequenceEqual.

Examples:

1. enumeration = (1, 2, 3, 4, 5); subset = (3, 4) ==> SequenceSuperset(enumeration, subset) = true
2. enumeration = (1, 2, 3, 4, 5); subset = (6, 5) ==> SequenceSuperset(enumeration, subset) = false (6 does not exist in enumeration)
3. enumeration = (1, 2, 3, 4, 5); subset = (3, 5) ==> SequenceSuperset(enumeration, subset) = false (3 is never immediately followed by 5 in enumeration)
4. enumeration = (1, 2, 3, 4, 5); subset = (5, 4) ==> SequenceSuperset(enumeration, subset) = false (5 is never immediately followed by 4 in enumeration)

And here's the code:

public static bool SequenceSuperset<T>(this IEnumerable<T> enumeration, IEnumerable<T> subset)
{
    return SequenceSuperset(enumeration, subset, EqualityComparer<T>.Default.Equals);
}

public static bool SequenceSuperset<T>(this IEnumerable<T> enumeration,
                                            IEnumerable<T> subset,
                                            Func<T, T, bool> equalityComparer)
{
    // Check to see that enumeration is not null
    if (enumeration == null)
        throw new ArgumentNullException("enumeration");

    // Check to see that subset is not null
    if (subset == null)
        throw new ArgumentNullException("subset");

    // Check to see that comparer is not null
    if (equalityComparer == null)
        throw new ArgumentNullException("comparer");

    using (IEnumerator<T> big = enumeration.GetEnumerator(), small = subset.GetEnumerator())
    {
        big.Reset(); small.Reset();

        while (big.MoveNext())
        {
            // End of subset, which means we've gone through it all and it's all equal.
            if (!small.MoveNext())
                return true;

            if (!equalityComparer(big.Current, small.Current))
            {
                // Comparison failed. Let's try comparing with the first item.
                small.Reset();
                
                // There's more than one item in the small enumeration. Guess why I know this.
                small.MoveNext();

                // No go with the first item? Reset the collection and brace for the next iteration of the big loop.
                if (!equalityComparer(big.Current, small.Current))
                    small.Reset();
            }
        }

        // End of both, which means that the small is the end of the big.
        if (!small.MoveNext())
            return true;
    }

    return false;
}