Sequence membership

Given two sorted sequences, this method returns the intersection, a-b, and b-a, using a single iteration over both sequences. The return type is an IEnumerable<KeyValuePair<T, int>>, where:


  • only in A = -1

  • in both = 0

  • only in B = 1


/// <summary>
/// Return an int for every element in sortedSetA and sortedSetB specifying objects
/// that belong to A but not to B (-1), objects which are both in A and in B (0), and objects
/// that belong to B but not A (1).
/// </summary>
/// <remarks>This method is an O(n+m) operation when the two sets have different members, where n
/// is the count of <paramref name="sortedSetA"/> and m is the count of <paramref name="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="setA">A set where each element is of type <typeparamref name="T"/></param>
/// <param name="setB">A set where each element is of type <typeparamref name="T"/></param>
/// <returns>Returns A \ B (-1), the intersection of A and B (0), and B \ A (1)</returns>
public static IEnumerable<KeyValuePair<T, int>> Membership<T> (IEnumerable<T> sortedSetA, IEnumerable<T> sortedSetB) {
return Membership<T> (sortedSetA, sortedSetB, Comparer<T>.Default);
}
/// <summary>
/// Return a KeyValuePair<int, T> for every element in sortedSetA and sortedSetB where the int
/// specifies membership and T is the element. The int specifies objects that belong to A but
/// not to B (-1), objects which are both in A and in B (0), and objects that belong to B but
/// not A (1).
/// </summary>
/// <remarks>This method is an O(n+m) operation when the two sets have different members, where n
/// is the count of <paramref name="sortedSetA"/> and m is the count of <paramref name="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="setA">A set where each element is of type <typeparamref name="T"/></param>
/// <param name="setB">A set where each element is of type <typeparamref name="T"/></param>
/// <param name="comparer"><see cref="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<KeyValuePair<T, int>> Membership<T> (IEnumerable<T> sortedSetA, IEnumerable<T> sortedSetB, IComparer<T> comparer) {
const int onlyA = -1;
const int both = 0;
const int onlyB = 1;

if (sortedSetA == null)
throw new ArgumentNullException ("sortedSetA");
if (sortedSetB == null)
throw new ArgumentNullException ("sortedSetB");
if (comparer == null)
throw new ArgumentNullException ("comparer");

IEnumerator<T> enumeratorA = sortedSetA.GetEnumerator ();
IEnumerator<T> enumeratorB = sortedSetB.GetEnumerator ();

bool nextA = enumeratorA.MoveNext ();
bool nextB = enumeratorB.MoveNext ();

// default value for type T
T a = default (T);
// default value for type T
T b = default (T);

// if both collections have a value
if (nextA & nextB) {
// get current value
a = enumeratorA.Current;
// get current value
b = enumeratorB.Current;

do {
// Compare a to b: is a < b, a == b, or a > b ?
int val = comparer.Compare (a, b);
// a == b
if (val == 0) {
// return both collections have the value a
yield return new KeyValuePair<T, int> (a, both);
// if collection a can move next
if (nextA = enumeratorA.MoveNext ())
// get the next a
a = enumeratorA.Current;
// if collection b can move next
if (nextB = enumeratorB.MoveNext ())
// get the next b
b = enumeratorB.Current;
}
// a < b
else if (val < 0) {
// return only collection a has the value a
yield return new KeyValuePair<T, int> (a, onlyA);
// if collection a can move next
if (nextA = enumeratorA.MoveNext ())
// get the next a
a = enumeratorA.Current;
}
// a > b
else {
// return only collection b has the value b
yield return new KeyValuePair<T, int> (b, onlyB);
// if collection b can move next
if (nextB = enumeratorB.MoveNext ())
// get the next b
b = enumeratorB.Current;
}
// loop while there are values for both collections
} while (nextA & nextB);
}
// if collection a has more values
if (nextA) {
// return only collection a has the value a
yield return new KeyValuePair<T, int> (a, onlyA);
// if collection a can move next
while (enumeratorA.MoveNext ()) {
// return only collection a has the value a
yield return new KeyValuePair<T, int> (enumeratorA.Current, onlyA);
}
}
// if collection b has more values
else if (nextB) {
// return only collection b has the value b
yield return new KeyValuePair<T, int> (b, onlyB);
// if collection b can move next
while (enumeratorB.MoveNext ()) {
// return only collection b has the value b
yield return new KeyValuePair<T, int> (enumeratorB.Current, onlyB);
}
}
}