OrderBy with a non-transitive IComparer

Viewed 870

Take a custom IComparer, that treats two doubles as equal if their difference is less than a given epsilon.

What would happen if this IComparer is used in a OrderBy().ThenBy() clause?

Specifically I am thinking of the following implementation:

public class EpsilonComparer : IComparer<double>
{
    private readonly double epsilon;

    public EpsilonComparer(double epsilon)
    {
        this.epsilon = epsilon;
    }

    public int Compare(double d1, double d2)
    {
        if (Math.Abs(d1-d2)<=epsilon) return 0;

        return d1.CompareTo(d2);
    }
}

Now this IComparer relationship is clearly not transitive. (if a ~ b and b ~ c then a ~ c)

With epsilon== 0.6 :

  • Compare(1, 1.5) == 0
  • Compare(1.5, 2) == 0
    yet
  • Compare(1, 2 ) == -1

What would happen if this IComparer was used in an OrderBy query, like this:

List<Item> itemlist;
itemList = itemlist.OrderBy(item=>item.X, new EpsilonComparer(0.352))
                   .ThenBy (item=>item.Y, new EpsilonComparer(1.743)).ToList();

Would the sort behave as one would expect, sorting the list first by X, then by Y, while treating roughly equal values as exactly equal?
Would it blow up under certain circumstances?
Or is this whole sort ill-defined?

What exactly are the consequences of using an IComparer without transitivity?

(I know that this is most likely undefined behavior of the c# language. I am still very much interested in an answer.)

And is there an alternative way to get this sorting behaviour?
(besides rounding the values, which would introduce artifacts when for two close doubles one is rounded up and the other down)

An online fidle of the code in this question is available here:

2 Answers
Related