Collection equality regardless of item order

I wanted to test collection equality disregarding order. One int array of 1,2,3,4 and another of 4,2,3,1 would be equal. Also, collections of collections would be compared only by their items and the number of times those items appear in any collection.

char[] charsA = new char[] { 'a', 'b', 'c', 'a' };
char[] charsB = new char[] { 'a', 'c', 'b', 'a' };
Assert.IsTrue(Collection.Equals(charsA, charsB, false));
int[] intA = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5 };
int[] intB = new int[] { 9, 8, 7, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1, 0, 0 };
Assert.IsTrue(Collection.Equals(intA, intB, false));
ArrayList arrayListA = new ArrayList();
ArrayList arrayListB = new ArrayList();
arrayListA.Add(charsA); // Adds the array as an item
arrayListB.AddRange(charsB); // Adds the items from the array
arrayListA.Add(intA);
arrayListB.AddRange(intB);
Assert.IsTrue(arrayListA.Count == 2);
Assert.IsTrue(arrayListB.Count == 20);
Assert.IsTrue(Collection.Equals(arrayListA, arrayListB, false));


I had to create the RelaxComparer so I could add all types to two SortedList collections that are built by the algorithm to determine equality. The SortedList objects are also used to keep track of the number of times each item appears in each collection.

I merged the CollectionEquals method I created earlier together with this new algorithm to a new Collection class that can test both types of collection equality:


public class Collection {
/// <summary>
/// Determines whether the specified collections instances are considered equal.
/// </summary>
/// <remarks>
/// <para>Assumes that a collection's value equality is based on the position and
/// the value of each item inside a collection. Therefore, two collections with the
/// equivalent items in the same order are considered equal.</para>
/// <para>Performs value equality on collections of collections and returns false
/// when a circular reference is encountered.</para>
/// </remarks>
/// <param name="CollectionA">The first collection to compare.</param>
/// <param name="CollectionB">The second collection to compare.</param>
/// <returns><list type="bullet"><item><description>
/// true if CollectionA is the same instance as CollectionB or
/// </description></item><item><description>
/// true if both are null references or
/// </description></item><item><description>
/// true if each item in CollectionA equals the associated item in CollectionB;
/// </description></item><item><description>
/// otherwise, false.
/// </description></item></list></returns>
/// <exception cref="ArgumentException">Both objects must be IEnumerable</exception>
public static new bool Equals(object CollectionA, object CollectionB) {
if (!(CollectionA is IEnumerable && CollectionB is IEnumerable))
throw new ArgumentException("Both objects must be IEnumerable");
return Equals((IEnumerable)CollectionA, (IEnumerable)CollectionB, true);
}
/// <summary>
/// Determines whether the specified collections instances are considered equal.
/// </summary>
/// <remarks>
/// <para>Doesn't throw exceptions. If an exception is thrown, false is returned.</para>
/// <para>Performs value equality on collections of collections and returns false
/// when a circular reference is encountered.</para>
/// </remarks>
/// <param name="CollectionA">The first collection to compare.</param>
/// <param name="CollectionB">The second collection to compare.</param>
/// <param name="InOrder">True if the order of the items and value determine
/// equality. False if the count and value of each item determine equality.</param>
/// <returns><list type="bullet"><item><description>
/// true if CollectionA is the same instance as CollectionB or
/// </description></item><item><description>
/// true if both are null references or
/// </description></item><item><description>
/// true if each item in CollectionA equals the associated item in CollectionB;
/// </description></item><item><description>
/// otherwise, false.
/// </description></item></list></returns> public static bool Equals(IEnumerable CollectionA, IEnumerable CollectionB, bool InOrder) { bool result = false; try { // built-in equality (probably reference) if (!(result = object.Equals(CollectionA, CollectionB)) && (CollectionA != null) && (CollectionB != null)) if (InOrder) { IList encounteredCollections = new ArrayList(); result = EqualsInOrder(CollectionA, CollectionB, ref encounteredCollections); } else result = EqualsNoOrder(CollectionA, CollectionB); } catch {} // ignore exceptions return result; } private static bool EqualsInOrder(IEnumerable CollectionA, IEnumerable CollectionB, ref IList EncounteredCollections) { bool result = false; // built-in equality (probably reference) if (!EncounteredCollections.Contains(CollectionA) && !EncounteredCollections.Contains(CollectionB)) { EncounteredCollections.Add(CollectionA); EncounteredCollections.Add(CollectionB); IEnumerator enumeratorA = CollectionA.GetEnumerator(); IEnumerator enumeratorB = CollectionB.GetEnumerator(); if (enumeratorA != null && enumeratorB != null) { bool moveA, moveB; // possible InvalidOperationException on MoveNext() call while ((moveA = enumeratorA.MoveNext()) & (moveB = enumeratorB.MoveNext())) // if objects are not equal if ((!object.Equals(enumeratorA.Current, enumeratorB.Current)) && !( enumeratorA.Current is IEnumerable && enumeratorB.Current is IEnumerable && EqualsInOrder((IEnumerable)enumeratorA.Current, (IEnumerable)enumeratorB.Current, ref EncounteredCollections))) { return false; // items don't equal } /* Usually breaks when moveA == moveB == false, meaning the count * of both collections are equal. moveA != moveB when the collections * are different sizes (not equal). */ result = moveA == moveB; } EncounteredCollections.Remove(CollectionA); EncounteredCollections.Remove(CollectionB); } return result; } private static bool EqualsNoOrder(IEnumerable CollectionA, IEnumerable CollectionB) { RelaxComparer relaxComparer = new RelaxComparer(); IList encounteredCollections = new ArrayList(); IDictionary itemsA = new SortedList(relaxComparer); IDictionary itemsB = new SortedList(relaxComparer); // add items to a sorted list containing the item's count in each collection EqualsNoOrder(CollectionA, ref encounteredCollections, ref itemsA); EqualsNoOrder(CollectionB, ref encounteredCollections, ref itemsB); // check for position and value equality of the sorted lists return Equals(itemsA, itemsB, true); } private static void EqualsNoOrder(IEnumerable Collection, ref IList EncounteredCollections, ref IDictionary Items) { if (EncounteredCollections.Contains(Collection)) throw new Exception(); // circular reference EncounteredCollections.Add(Collection); IEnumerator enumerator = Collection.GetEnumerator(); if (enumerator != nul l) // possible InvalidOperationException on MoveNext() call while (enumerator.MoveNext()) if (enumerator.Current is IEnumerable) EqualsNoOrder((IEnumerable)enumerator.Current, ref EncounteredCollections, ref Items); else { if (Items.Contains(enumerator.Current)) Items[enumerator.Current] = (int)Items[enumerator.Current] + 1; else Items.Add(enumerator.Current, 1); } EncounteredCollections.Remove(Collection); } } /// <summary> /// Compares two objects for equivalence, where objects of different /// types are compared by their string representations. /// </summary> public class RelaxComparer : IComparer { public int Compare(object x, object y) { Type typeX = x.GetType(), typeY = y.GetType(); /* IComparable.CompareTo(object obj) The parameter, obj, must be * the same type as the class or value type that implements this * interface; otherwise, an ArgumentException is thrown */ if (typeX == typeY && typeof(IComparable).IsAssignableFrom(typeX)) return ((IComparable)x).CompareTo(y); else return x.ToString().CompareTo(y.ToString()); // use strings } }

2 comments on “Collection equality regardless of item order

Comments are closed.