CODEWITHSUNDEEP
javaalgorithmsorting
Kasper van den Berg
Kasper van den Berg

Reputation: 9526

Partial ordered Comparator

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

Upvotes: 14

Views: 4820

Answers (6)

Arend
Arend

Reputation: 2423

Any time I've tried using hash codes for this sort of thing I've come to regret it. You will be much happier if your ordering is deterministic - for debuggability if nothing else. The following will achieve that, by creating a fresh index for any not previously encountered Item and using those indices for the comparison if all else fails.

Note that the ordering still is not guaranteed to be transitive.

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

Upvotes: 2

Joop Eggen
Joop Eggen

Reputation: 109597

If a < b and b < c implies a < c, then you have made a total ordering by using the hashCodes. Take a < d, d < c. The partial order says that b and d not necessarily are ordered. By introducing hashCodes you provide an ordering.

Example: is-a-descendant-of(human, human).

Adam (hash 42) < Moses (hash 17), Adam < Joe (hash 9)

Implies

Adam < Joe < Moses

A negative example would be the same relation, but when time travel allows being your own descendant.

Upvotes: 0

Jayan
Jayan

Reputation: 18458

In jdk7, your object will throw runtime exception :

Area: API: Utilities Synopsis: Updated sort behavior for Arrays and Collections may throw an IllegalArgumentException Description: The sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort has been replaced.
The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract. The previous implementation silently ignored such a situation. If the previous behavior is desired, you can use the new system property, java.util.Arrays.useLegacyMergeSort, to restore previous mergesort behavior.

Nature of Incompatibility: behavioral
RFE: 6804124

Upvotes: 1

Bohemian
Bohemian

Reputation: 425198

When one item is neither "before" nor "after" another, instead of returning a comparison of the hashcode, just return 0. The result will be "total ordering" and "arbitrary" ordering of coincident items.

Upvotes: -1

David Eisenstat
David Eisenstat

Reputation: 65488

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.

Upvotes: 9

Benjamin Gruenbaum
Benjamin Gruenbaum

Reputation: 276406

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.

Upvotes: 8

Related Questions