Impose a total ordering on all instances of *any* class in Java

Question

I'm unsure whether the following code would ensure all conditions given in Comparator's Javadoc.

class TotalOrder<T> implements Comparator<T> {

    public boolean compare(T o1, T o2) {
        if (o1 == o2 || equal(o1, o2)) return 0;

        int h1 = System.identityHashCode(o1);
        int h2 = System.identityHashCode(o2);

        if (h1 != h2) {
            return h1 < h2 ? -1 : 1;
        }

        // equals returned false but identity hash code was same, assume o1 == o2
        return 0;
    }

    boolean equal(Object o1, Object o2) {
        return o1 == null ? o2 == null : o1.equals(o2);
    }
}

Will the code above impose a total ordering on all instances of any class, even if that class does not implement Comparable?

Answer 1

You answered in your comment:

equals returned false but identity hash code was same, assume o1 == o2

Unfortunately you cannot assume that. Most of the time that is going to work, but in some exceptionnal cases, it won't. And you cannot know when. When such a case appear, it would lead to lose instances in TreeSets for example.

Answer 2

I don't think it does since this clause is not met:

Finally, the implementer must ensure that x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.

Since equal(o1, o2) depends on o1's implementation of equals, two objects that are logically equal (as determined by equals) still have two differrent identityHashCodes.

So when comparing them to a third object (z), they might end up yielding different values for compareTo.

Make sense?

Answer 3

I'm not really sure about the System.identityHashCode(Object). That's pretty much what the == is used for. You might rather want to use the Object.hashCode() - it's more in parallel with Object.equals(Object).

Answer 4

Damien, I agree this is not ideal, hence the comment. Any suggestions?

Answer 5

Allain, it seems to me that since I'm checking for equivalence before looking at the hash codes, this condition would be satisfied as long as the equals implementation is transitive (which it needs to be according to its contract). Am I missing something?

Answer 6

You should probably raise an exception if it gets to that last return 0 line --when a hash collision happens. I do have a question though: you are doing a total ordering on the hash's, which I guess is fine, but shouldn't some function be passed to it to define a Lexicographical order?

    int h1 = System.identityHashCode(o1);
    int h2 = System.identityHashCode(o2);
    if (h1 != h2) {
        return h1 < h2 ? -1 : 1;
    }

I can imagine that you have the objects as a tuple of two integers that form a real number. But you wont get the proper ordering since you're only taking a hash of the object. This is all up to you if hashing is what you meant, but to me, it doesn't make much sense.

Answer 7

I agree this is not ideal, hence the comment. Any suggestions?

I think there is now way you can solve that, because you cannot access the one and only one thing that can distinguish two instances: their address in memory. So I have only one suggestion: reconsider your need of having a general total ordering process in Java :-)

Answer 8

nlucaroni, you're right that the ordering this comparator imposes is not "proper" in that it would be unexpected based on the intrinsic meaning of the particular objects. The use case, though, is to have different components to agree on a single way to sort an arbitrary list of items. In this case, I can not assume any intrinsic meaning for the given objects.

Answer 9

Hey, look at what I found!

http://gafter.blogspot.com/2007/03/compact-object-comparator.html

This is exactly what I was looking for.

Answer 10

Hey, look at what I found!

http://gafter.blogspot.com/2007/03/compact-object-comparator.html

Oh yes, I forgot about the IdentityHashMap (Java 6 and above only). Just have to pay attention at releasing your comparator.