偏序比较器

Question

如何实现根据偏序关系对元素排序的java.util.Comparator？

例如，给定一个偏序关系a≺c，b≺c；a和b的顺序未定义。

因为Comparator需要完全排序，所以实现顺序元素的偏序是任意定义的，但是是一致的。

下面的内容会有效吗？

interface Item {
    boolean before(Item other);
}

class ItemPartialOrderComperator implements Comparator<Item> {
    @Override
    public int compare(Item o1, Item o2) {
        if(o1.equals(o2)) {  // Comparator returns 0 if and only if o1 and o2 are equal;
            return 0;
        }
        if(o1.before(o2)) {
            return -1;
        }
        if(o2.before(o1)) {
            return +1;
        }
        return o1.hashCode() - o2.hashCode(); // Arbitrary order on hashcode
    }
}

• 这是比较器的序传递吗？ (恐怕不是)
• Comparators是否必须是传递性的？ (在TreeMap__中使用时)
• 如何正确地实现它？ (如果上面的实现不起作用) (哈希代码可能发生碰撞，为了简单冲突，示例忽略冲突；有关哈希代码的故障安全排序，请参见https://stackoverflow.com/a/28494/814206到https://stackoverflow.com/questions/28301/impose-a-total-ordering-on-all-instances-of-any-class-in-java。)

Answer 1

问题是，当您有无法比较的元素时，您需要回到比比较哈希码更聪明的地方。例如，给定一个偏序{a < b，c< d}，散列码可以满足h(d) < h(b) < h(c) < h(a)，这意味着< c< a(粗体表示被哈希码打破的领带)，这将导致TreeMap问题。

一般来说，您可能没有什么可做的，除了对键进行拓扑排序之前，所以欢迎提供一些您感兴趣的部分顺序的详细信息。

Answer 2

这似乎是一个回答，而不是一个评论，所以我会张贴它

文档说：

从合同的比较结果看，商是S上的等价关系，强加的顺序是S上的全序。“

所以不，一个比较器需要一个完全的排序。如果您用偏序来实现这一点，那么您就违反了接口契约。

即使它可能在某些场景中工作，您也不应该试图以破坏接口契约的方式解决问题。

有关符合偏序的数据结构，请参见这个问题。

Answer 3

每当我尝试使用哈希码来处理这类事情时，我都会后悔的。如果您的排序是确定性的，那么您会更高兴--如果没有其他的话，这是为了可调试器。通过为任何以前没有遇到过的Item创建一个新的索引，并在所有其他方法都失败时使用这些索引进行比较，以下将实现这一目标。

注意，排序仍然不能保证是传递的。

class ItemPartialOrderComperator implements Comparator<Item> {
    @Override
    public int compare(Item o1, Item o2) {
        if(o1.equals(o2)) {
            return 0;
        }
        if(o1.before(o2)) {
            return -1;
        }
        if(o2.before(o1)) {
            return +1;
        }
        return getIndex(o1) - getIndex(o2);
    }

    private int getIndex(Item i) {
        Integer result = indexMap.get(i);
        if (result == null) {
            indexMap.put(i, result = indexMap.size());
        }
        return result;
    }

    private Map<Item,Integer> indexMap = new HashMap<Item, Integer>();
}