OrderBy with a non-transitive IComparer

Question

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:}

Answer 1

The problem is that the first sorting level (on X) can result in different orders already. Imagine that all items are within one epsilon of each other. Then all sort orders are consistent with your comparer because it will always return 0. The sort algorithm could flip coins and still provide a "right" answer. Not useful.

If the first level is arbitrarily sorted, you cannot expect the 2nd sorting level to work.

Of course, all of this discussion is moot because you are violating the precondition of the sorting API. Even if it happened to work, you couldn't be sure that it would work on a) all data b) on all future releases of .NET.

How can you still achieve your goal? Your problem is just ill-defined because many solutions are possible. I get what you want to achieve but it is not possible with your current definition of the problem.

I propose this: sort all items by X (without epsilon). Then, traverse the sorted items left-to-right and merge the items into groups that one epsilon wide at most. That gives you groups of items whose X-value is at most epsilon apart.

You can then use the group number as the first sorting level. It is just a simple integer, so no trouble sorting on it. For the Y field, you can then use a normal comparer without epsilon (or repeat the same trick).

Answer 2

view my code snippet here. it's just for first level sorting and not optimized.

OrderBy and ThenBy are using general algorithm. you need to re-implement OrderBy and ThenBy with special algorithm like mine. then it can work as OrderBy().ThenBy().

Detail of algorithm:

in a sorted sequence(x1 x2 x3...) under your EpsilonComparer, if x4>x1, then x5>x1. if x4=x1, then x3=x1 and either x5>x1 or x5=x1.

with epsilon(0.4), input following numbers:0.1, 0.6, 1, 1.1, 1.6, 2, 2, 2.6, 3, 3.1, 3.6, 4, 4.1, 4.6, 5, 5.1, 5.6, 6, 6.1, 6.6

result:0.1 0.6 1 1.1 (1.6 2 2 ) 2.6 3 3.1 3.6 4 4.1 4.6 (5 5.1 ) 5.6 (6 6.1 ) 6.6

(a,b,c) indicates these numbers are equal and the order of numbers is not fixed. they can be (a,b,c), (c,a,b) and any other order.

a b indicates a < b and order is fixed.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Rextester
{
    class Program
    {
        public static void Main(string[] args)
        {
            new EpsilonSort(new EpsilonComparer(0.4), 0.1, 0.6, 1, 1.1, 1.6, 2, 2, 2.6, 3, 3.1, 3.6, 4, 4.1, 4.6, 5, 5.1, 5.6, 6, 6.1, 6.6).Sort();
        }
    }

    public class EpsilonSort
    {
        private readonly IComparer<double> m_comparer;
        private readonly double[] m_nums;
        public EpsilonSort(IComparer<double> comparer, params double[] nums)
        {
            this.m_comparer = comparer;
            this.m_nums = nums;
        }

        public void Sort()
        {
            Node root = new Node();
            root.Datas = new List<double>(this.m_nums);

            foreach (double i in (double[])this.m_nums.Clone())
            {
                this.ProcessNode(i, root);
            }

            this.OutputNodes(root);
        }

        private void OutputNodes(Node root)
        {
            if (root.Datas == null)
            {
                foreach (var i in root.Nodes)
                {
                    this.OutputNodes(i);
                }
            }
            else
            {
                if (root.Datas.Count == 1)
                {
                    Console.WriteLine(root.Datas[0]);
                }
                else
                {
                    Console.Write('(');
                    foreach (var i in root.Datas)
                    {
                        Console.Write(i);
                        Console.Write(' ');
                    }
                    Console.WriteLine(')');
                }
            }
        }

        private void ProcessNode(double value, Node one)
        {
            if (one.Datas == null)
            {
                foreach (var i in one.Nodes)
                {
                    this.ProcessNode(value, i);
                }
            }
            else
            {
                Node[] childrennodes = new Node[3];
                foreach (var i in one.Datas)
                {
                    int direction = this.m_comparer.Compare(i, value);
                    if (direction == 0)
                    {
                        this.AddData(ref childrennodes[1], i);
                    }
                    else
                    {
                        if (direction < 0)
                        {
                            this.AddData(ref childrennodes[0], i);
                        }
                        else
                        {
                            this.AddData(ref childrennodes[2], i);
                        }
                    }
                }
                childrennodes = childrennodes.Where(x => x != null).ToArray();
                if (childrennodes.Length >= 2)
                {
                    one.Datas = null;
                    one.Nodes = childrennodes;
                }
            }
        }

        private void AddData(ref Node node, double value)
        {
            node = node ?? new Node();
            node.Datas = node.Datas ?? new List<double>();
            node.Datas.Add(value);
        }

        private class Node
        {
            public Node[] Nodes;
            public List<double> Datas;
        }
    }

    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);
        }
    }
}