Defining Equals on an interface
I was wondering today if ICollection should declare an Equals method on it and state what the semantics of it would be. This came around because I currently have 3 implementations of ICollection:
- ArrayCollection (an ICollection backed by an array)
- EmptyCollection (a specialized collection that holds no elements. Uses a singleton for memory efficiency and specialized implementations of the methods for speed)
- SingletonCollection (a specialized collection that holds only one element. Useful for when you have a single element and you want ot pass it to something that expects a collection).
Now, it seemed reasonable that the following would be true:
new
ArrayCollection<int>().Equals(EmptyCollection<int>.Instance) and
ICollection<int> c = new ArrayCollection<int>();
c.Add(4);
c.Equals(new SingletonCollection<int>(4));
Now, the question is “why are those true”. It's intuitive to me that any empty collections should be equal, and any collection with one element in it would be equal to a SingletonCollection with that same element in it. However, is there a way to formalize that? The best i could come up with is “Two collections are equal if as you iterate over both of them you find their corresponding elements are equals _and_ you finish iterating over both collections at the same time.” Expressed in code that would be:
public override bool Equals(object obj)
{
ICollection<A> other = obj as ICollection<A>;
if (null == other)
{
return false;
}
IEnumerator<A> e1 = this.GetEnumerator();
IEnumerator<A> e2 = other.GetEnumerator();
while (true)
{
bool e1MoveNext = e1.MoveNext();
bool e2MoveNext = e2.MoveNext();
if (e1MoveNext != e2MoveNext)
{
//they have a different number of elements
return false;
}
if (e1MoveNext == false)
{
//no more elements in either
return true;
}
if (!this.authenticate(e1.Current, e2.Current))
{
return false;
}
}
}
That seems to work fine and works within my intuitive definition of how collections are felt of as equal. The problem I then ran into was that I tried to think down the line about whatever types of collections might be in the system. Pretty quickly i though about ISet (a collection containing only unique elements). If I were an ISet i would only consider something equal to me if it contained all my elements, no more, and no duplicate. Wow. That's something that's woudl be pretty difficult to check. I'd have to iterate over both checking if my elements were in it and it's elements were in me. I'd then have to figure out some way to make sure that it had no duplicates. That's a pretty tall order. (I'm not even sure how I would go ahead checking for duplicates). The alternative is to place the restriction that the thing I am comparing myself to is also an ISet. Then I know that the elements must be unique. I can then check my containment in it and it's containment in me. I.e. (this.IsSubsetOf(that) && that.IsSubsetOf(this)). If I were to eschew infinite sets and have a Count property then I could do: if (this.Count == that.Count && this.IsSubsetOf(that)). (note: taht would also be possible with an IOptional Count property.
However, I face a conundrum. Say I do: EmptyCollection<int>.Instance(EmptySet<int>.Instance). I get true based on the rules of Collection equality. However, if I fo EmptySet<int>.Instance(EmptyCollection<int>.Instance), i get falgs based on the rules of Set equality.
This is a big no-no (i think) as I've violated the requirement that a.Equals(b) <==> b.Equals(a). :-(
Is there a way to reconcile this system?
Has anyone else out there faced this problem of defining equals on interfaces in the presense of sub-interfaces?