Sequence Membership

/// <summary>
/// Identify in which set(s) the object lives
/// </summary>
/// <remarks>
/// Descriptions from http://en.wikipedia.org/wiki/Set_(mathematics)
/// </remarks>
public enum ObjectSetLocation : byte {
    /// <summary>
    /// The relative complement of B in A, denoted by A − B (or A \ B),
    /// is the set of all elements which are members of A but not
    /// members of B.
    /// </summary>
    AButNotB = 10,
    /// <summary>
    /// The intersection of A and B, denoted by A ∩ B, is the set
    /// of all things which are members of both A and B. If A ∩ B = ∅,
    /// then A and B are said to be disjoint.
    /// </summary>
    Intersection = 11,
    /// <summary>
    /// The relative complement of A in B, denoted by B − A (or B \ A),
    /// is the set of all elements which are members of B but not
    /// members of A.
    /// </summary>
    BButNotA = 12
}

/// <summary>
/// Return a tuple for every element in sortedSetA and sortedSetB specifying objects
/// that belong to A but not to B, objects which are both in A and in B, and objects
/// that belong to B but not A.
/// </summary>
/// <remarks>This method is an O(n+m) operation when the two sets have different members, where n
/// is the count of sortedSetA and m is the count of sortedSetB.
/// Otherwise the operation approaches O(n+m-n) where m is the count of the larger set and n is the
/// smaller set.
/// </remarks>
/// <typeparam name="T">Type of element in each set</typeparam>
/// <param name="sortedSetA">A sorted set where each element is of type T</param>
/// <param name="sortedSetB">A sorted set where each element is of type T</param>
/// <param name="comparer">IComparer used to sort the sets</param>
/// <returns>Returns A \ B (-1), the intersection of A and B (0), and B \ A (1)</returns>
public static IEnumerable<Tuple<T, ObjectSetLocation>> Membership<T> (this IEnumerable<T> sortedSetA, IEnumerable<T> sortedSetB, IComparer<T> comparer = null) {
    Contract.Requires (sortedSetA != null);
    Contract.Requires (sortedSetB != null);

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

    using (var enumeratorA = sortedSetA.GetEnumerator ())
    using (var enumeratorB = sortedSetB.GetEnumerator ()) {
        bool moveNextA = enumeratorA.MoveNext ();
        bool moveNextB = enumeratorB.MoveNext ();
        T currentA = default (T);
        T currentB = default (T);
        if (moveNextA & moveNextB) {
            currentA = enumeratorA.Current;
            currentB = enumeratorB.Current;
            do {
                int compareResult = comparer.Compare (currentA, currentB);
                if (compareResult == 0) {
                    yield return new Tuple<T, ObjectSetLocation> (currentA, ObjectSetLocation.Intersection);
                    if (moveNextA = enumeratorA.MoveNext ())
                        currentA = enumeratorA.Current;
                    if (moveNextB = enumeratorB.MoveNext ())
                        currentB = enumeratorB.Current;
                }
                else if (compareResult < 0) {
                    yield return new Tuple<T, ObjectSetLocation> (currentA, ObjectSetLocation.AButNotB);
                    if (moveNextA = enumeratorA.MoveNext ())
                        currentA = enumeratorA.Current;
                }
                else {
                    yield return new Tuple<T, ObjectSetLocation> (currentA, ObjectSetLocation.BButNotA);
                    if (moveNextB = enumeratorB.MoveNext ())
                        currentB = enumeratorB.Current;
                }
            }
            while (moveNextA & moveNextB);
        }
        if (moveNextA) {
            yield return new Tuple<T, ObjectSetLocation> (currentA, ObjectSetLocation.AButNotB);
            while (enumeratorA.MoveNext ()) {
                yield return new Tuple<T, ObjectSetLocation> (enumeratorA.Current, ObjectSetLocation.AButNotB);
            }
        }
        else if (moveNextB) {
            yield return new Tuple<T, ObjectSetLocation> (currentA, ObjectSetLocation.BButNotA);
            while (enumeratorB.MoveNext ()) {
                yield return new Tuple<T, ObjectSetLocation> (enumeratorB.Current, ObjectSetLocation.BButNotA);
            }
        }
    }
}