Impose a total ordering on all instances of *any*

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

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 2

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 3

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.

Answer 4

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 5

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