Understanding Collections.reverseOrder() method in Java

Question

Consider one of the overloaded definitions of sort method from Array class:

public static <T> void sort(T[] a, Comparator<? super T> c)

A common way to sort array in reverse order is to pass Comparator returned by Collections.reverseOrder() as a second argument to this method.

Let's look at the implementation of Collections.reverseOrder() method from openjdk 7:

public static <T> Comparator<T> reverseOrder() {
    return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
}

ReverseComparator class:

private static class ReverseComparator
    implements Comparator<Comparable<Object>>, Serializable {

    private static final long serialVersionUID = 7207038068494060240L;

    static final ReverseComparator REVERSE_ORDER = new ReverseComparator();

    public int compare(Comparable<Object> c1, Comparable<Object> c2) {
        return c2.compareTo(c1);
    }

    private Object readResolve() { return reverseOrder(); }
}

My question is: why Collections.reverseOrder() is made to be generic? And why simply ReverseComparator.REVERSE_ORDER can't be returned?

Of course, we can specify type explicitly calling Collections.<T>reverseOrder(). But what's the benefit against simple Collections.reverseOrder() in this case?

I found a rather useful discussion there:

How does Collections.reverseOrder() know what type parameter to use?

But it doesn't answer to my question.

Also It's interesting for me how sort method uses compare method from ReverseComparator class. As we can see compare takes arguments of Comparable<Object> type. And what if we sort array of objects implementing Comparable<T>, where T is for example Integer? We can't invoke compare with Comparable<Integer> cause Comparable<Integer> isn't casted to Comparable<Object>.

Answer 1

This is all about type erasure. Remember, at runtime there is no such thing as a Comparable<Object>, there is only such a thing as a Comparable. Therefore the compare method of REVERSE_COMPARATOR works on two String instances, for example. It doesn't cause a ClassCastException at runtime because String implements Comparable<String>, and at runtime that's just Comparable.

However, the method reverseComparator has to be generic, because otherwise the user would have to cast the returned object to the appropriate type before it could be used. For example, consider this code where the comparator has the same type as the declared type of REVERSE_COMPARATOR.

Comparator<Comparable<Object>> comparator = Collections.reverseOrder();
String[] arr = {"A", "B", "C"};
Arrays.sort(arr, comparator);       // Doesn't compile.

The reason this doesn't compile is because arr is a String array, and so Arrays.sort expects a Comparator<? super String>, but Comparable<Object> is not a supertype of Comparable<String> (Is List<Dog> a subclass of List<Animal>? Why aren't Java's generics implicitly polymorphic?).

You can make it compile by using casts:

Comparator<Comparable<Object>> comparator = Collections.reverseOrder();
String[] arr = {"A", "B", "C"};
Arrays.sort(arr, (Comparator<String>) (Object) comparator);
System.out.println(Arrays.toString(arr));   // prints [C, B, A]

This generates a warning, but as you will see it you try it, it works. By using a generic method, the ugliness of the cast and the warning is kept out of the code using the method.

The fact that the same object (REVERSE_COMPARATOR) can be treated as being a Comparator<String> or a Comparator<Integer>, or a Comparator<X> where X is any type implementing Comparable is one of the many benefits of type erasure. This reuse of objects is not possible in C# because in C# instances of a generic class know the type.

There are many examples of this kind of reuse. For example, all of these generic methods always return the same instance, no matter what generic type you supply.

Collections.emptySet()
Optional.empty()
Comparator.naturalOrder()
Collections.emptyListIterator()

Answer 2

why Collections.reverseOrder() is made to be generic?

This function is generic so as to spare you from having to cast the result into your specific Comparable<T> type. (You might say that you don't care because you don't cast it anyway, in which case what this tells us is that you do not have enough warnings enabled.)

why we can't simply return ReverseComparator.REVERSE_ORDER?

One reason is because ReverseComparator.REVERSE_ORDER is package-private, so you cannot access it from outside that package. Which in turn begs the question "why is it package-private?" Well, mainly because this satisfies the purists who cringe when they see member variables being directly accessed even if they are final, but actually I would not blame them in this case, because accessors offer forward compatibility at the binary level, which might be completely unnecessary in application code, but it kind of becomes a necessity in a language runtime. And ReverseComparator is part of the java runtime.

But a more important reason is because Collections.reverseOrder() does the cast to (Comparator<T>) for you, so that you don't have to do it yourself. (Again, if you don't see a problem with this, that's because you do not have enough warnings enabled, which means you need to reconsider your practices.)

In short, if you tried to do the following:

Comparator<MyObject> myComparator = ReverseComparator.REVERSE_ORDER;

you would get an error, because this is an invalid assignment. So, you would have to change it to this:

Comparator<MyObject> myComparator = 
    (Comparator<MyObject>)ReverseComparator.REVERSE_ORDER;

but then you would get a warning, because this is an unchecked cast. So you would end up having to do this:

@SuppressWarnings( "unchecked" )
Comparator<MyObject> myComparator = 
    (Comparator<MyObject>)ReverseComparator.REVERSE_ORDER;

which is ugly. So, Collections.reverseOrder() saves you from that, allowing you to do this:

Comparator<MyObject> myComparator = Collections.reverseOrder();

As we can see compare takes arguments of Comparable type. And what if we sort array of objects implementing Comparable, where T is for example Integer? We can't invoke compare with Comparable cause Comparable isn't casted to Comparable.

Okay, I see what your real question is. Welcome to the wonderful world of java generics and type erasure. I will try to explain, but be sure to also look up the term "type erasure" in order to fully understand the concept.

In java, generics were introduced to the language as an afterthought. For this reason, they had to be implemented in such a way that generics-aware code would be backwards compatible with old code which was not generics-aware. The solution was a trick called type erasure, which basically means that generic information is completely stripped after compilation. This means that at the bytecode level, Comparator<String> and Comparator<Integer> and Comparator are one and the same thing. No difference whatsoever. This is what enables the java runtime to implement a single class which acts as a reverse comparator of any object. It is not really a Comparator<Object>, it is a Comparator<ANYTHING>, because all it does is reverse the direction of the comparison, so it does not really care about the nature of the objects that are being compared.

So, in java, if you really know what you are doing, you are free to cast an instance of a generic class to an instance of the same class, but with a different generic parameter. In this case, the creators of the java runtime are casting Comparator<Object> to Comparator<T>, which may in fact be later assigned to Comparator<Integer>, and that's fine.

This cast is tricky though, because the compiler has to trust that you really know what you are doing, so by default, the compiler issues an "unchecked assignment" warning on such casts, and then in turn we indicate that we swear we know what we are doing with a @SuppressWarnings( "unchecked" ) annotation.

Collections.reverseOrder() spares you from having to be concerned with all that.