C# IComparer<T> standard usage question

Question

I have a question with whether or not this is a standard for using IComparer in C#. Say I have a situation in which there are three Person objects: P1, P2, and P3. Say I call the Compare method passing in P1 and P2 and the result is 0. This essentially means the two people should be categorized as equal. Now say I call the Compare method passing in P2 and P3 and the result for that is 0 as well. Again, this means the two people are equal. Logically speaking, one can assume P1 and P3 are equal as well; however, the Compare method could be implemented however someone decides to implement it. So is it a standard to implement it in such a way that P1 and P3 would also return 0 in this case?

Here's code of what I'm asking:

// Assume these are initialized properly
Person p1 = null, p2 = null, p3 = null;
IComparer<Person> comparer = null;

// Compare person 1 to person 2 and result is 0
Debug.Assert(comparer.Compare(p1, p2) == 0);

// Compare person 2 to person 3 and result is 0
Debug.Assert(comparer.Compare(p2, p3) == 0);

// Would this be a fair assumption that person 1 and person 3 would also be 0?
Debug.Assert(comparer.Compare(p1, p3) == 0);

Fantastic

Answer 1

Yes, that would be the standard. Its explicitly stated for IComparable:

If A.CompareTo(B) returns zero and B.CompareTo(C) returns zero, then A.CompareTo(C) is required to return zero.

I can't find anything in the official documentation that comes right out and states the same thing for ICompare but I think its safe to assume the same holds true.

Rafaelle

Answer 2

It has nothing to do with C#, it's a simple mathematical rule: Transitivity: http://en.wikipedia.org/wiki/Transitive_relation

So, yes in short.

--- Added information due to comment ---

If you go and read the documentation about IComparer: http://msdn.microsoft.com/en-us/library/system.collections.icomparer.compare.aspx

you'll see that:

Compares two objects and returns a value indicating whether one is less than, 
equal to, or greater than the other.

In other word, that means that when comparing object "a" and "b", you should always get the same result when calling multiple time the method Compare. If it's not the case, it means that you will get undefined behavior and it will be impossible to rely on that function for doing any sorting or comparison.

So, when you implement this method properly, the Transitivity rule apply and you can say without any doubt that a == c.

I hope that clarify your questioning about the implementation problem.

Tetreault

I realize that, but the Compare method could be implemented in such a way that the transitive rule wouldn't apply. The Compare method could return new Random().Next(); and then the transitive rule wouldn't apply. So I'm asking if it's a standard for the Compare method to implemented where the rule does apply. – Fantastic

It is a convention, moreover strong enough to be a contract that must be followed for the proper operation of the interface. Undefined Behavior if you do not follow the contract :) – Blanchard

Really funny. It's like making a method: getCurrentTime() { return Time(Random()); }. It just makes no sense. A compare method must be finite and always have the same behavior. In your example that means that a.Compare(b) cound return 3 different result if called 3 time consecutively. I don't think that's what this function is for. – Tetreault

Answer 3

It is part of the interface contract that if a == b and b == c that a == c (transitive property of equality). This is not enforced anywhere in code, but it is required for it to function correctly.

Blanchard

Answer 4

Equality is transitive, so yes you should assume that, and develop your IComparer with that in mind.

Transitivity

Ankney