Partial ordered Comparator

Question

How to implement java.util.Comparator that orders its elements according to a partial order relation?

For example given a partial order relation a ≺ c, b ≺ c; the order of a and b is undefined.

Since Comparator requires a total ordering, the implementation orders elements for which the partial ordering is undefined arbitrarily but consistent.

Would the following work?

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

• Is this comparator's ordering transitive?
  (I fear that it is not)
• Are Comparators required to be transitive?
  (when used in a TreeMap)
• How to implement it correctly?
  (if the implementation above doesn't work)
  (Hashcodes can collide, for simplicity collisions the example ignores collisions; see Damien B's answer to Impose a total ordering on all instances of *any* class in Java for a fail-safe ordering on hashcodes.)

Answer 1

The problem is that, when you have incomparable elements, you need to fall back to something cleverer than comparing hash codes. For example, given a partial order {a < b, c < d}, the hash codes could satisfy h(d) < h(b) < h(c) < h(a), which means that a < b < c < d < a (bold denotes tie broken by hash code), which will cause problems with a TreeMap.

In general, there's probably nothing for you to do except topologically sort the keys beforehand, so some details about the partial orders of interest to you would be welcome.

Answer 2

It seems to be more of an answer than a comment so I'll post it

The documentation says:

It follows immediately from the contract for compare that the quotient is an equivalence relation on S, and that the imposed ordering is a total order on S."

So no, a Comparator requires a total ordering. If you implement this with a partial ordering you're breaching the interface contract.

Even if it might work in some scenario, you should not attempt to solve your problem in a way that breaches the contract of the interface.

See this question about data structures that do fit a partial ordering.