使用(x,y)坐标对偏移进行排序会导致违反比较器合同

Question

我正在尝试对x和y点的集合进行排序,其中x的偏移使得px-qx应该被视为等于IF px == qx OR ABS(px-qx)<offset.请注意,我在这里取绝对值,所以我不应该得到任何负值.我的比较器如下:

 private static class XYOrder implements Comparator<ExtractPojo> {

    public int compare(ExtractPojo p, ExtractPojo q) {

        Integer a=p.x.intValue();
        Integer b=q.x.intValue();
        Integer c=p.y.intValue();
        Integer d=q.y.intValue();

        int offset=Math.abs(a-b); //calculate offset from x


      if(offset < 15 || a == b) //if x is the same, sort by y coordinate
            return c-d; 
       else return a-b; //if x is not same sort by x coordinate

    }
}

此代码适用于某些情况,但我在其他情况下收到以下错误消息:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeHi(TimSort.java:868)
at java.util.TimSort.mergeAt(TimSort.java:485)
at java.util.TimSort.mergeForceCollapse(TimSort.java:426)
at java.util.TimSort.sort(TimSort.java:223)
at java.util.TimSort.sort(TimSort.java:173)
at java.util.Arrays.sort(Arrays.java:659)
at java.util.Collections.sort(Collections.java:217)

我有一种感觉,我违反了一个过渡规则,因为我已经在这个网站上广泛搜索了一个答案,但我不确定如何测试我在这里缺少的东西.

我已经测试了没有偏移的代码,我没有得到这个错误信息,所以我知道它与我如何实现偏移量有关.我已经试图解决这个问题几个星期没有运气.

我希望得到一些关于此的提示或建议.非常感谢你.

所以我能想到的唯一解决方法是首先按x位置进行排序,然后遍历每个x并根据偏移调整x是相同的,然后再按上面提到的x,y进行排序而不进行偏移.看起来像是一个黑客,但我以前从未使用过比较器而且我很难解决这个问题.

Answer 1

我有一种感觉,我违反了一个跨性别规则

的确,你是.在你的比较器下,我们有(0, 20) > (10, 10) > (20, 0) > (0, 20).(另外,它拼写为"及物性".)

一般情况下,compare,compareTo,和equals方法,不宜用公差,因为公差本质上是不及.两个差异都低于公差可能会增加高于公差的差异.