How can Collection.reverseOrder() used in Arrays.sort()

Question

I see the Collections.reverseOrder() method returns a type ReverseComparator, which implements Comparator<Comparable<Object>>, as below

    private static class ReverseComparator implements Comparator<Comparable<Object>>, Serializable {
            private static final long serialVersionUID = 7207038068494060240L;
            static final Collections.ReverseComparator REVERSE_ORDER = new Collections.ReverseComparator();
  ....

in below valid code:

var comparator = Collections.reverseOrder();
Arrays.sort(new Integer[]{2, 4}, comparator);

the 2nd parameter of the sort method is of type Comparator<? super Integer>.

I think when the sort method get called, the Comparator<Comparable<Object>> type is conceptually convertible to Comparator<? super Integer>, thus I wonder how a Comparable<Object> becoming super type of Integer, although I know Integer implements Comparable<Integer>.

Does this answer your question? [Java Generics (Wildcards)](https://stackoverflow.com/questions/252055/java-generics-wildcards) `? super Integer` means that it could be `Integer` or a supertype of `Integer`. — dan1st, May 21 '22 at 21:39

score 1 · Answer 1 · answered May 21 '22 at 21:39

1

This is actually a bit of compiler trickery. In Java, generics are stripped when compiling source code (.java) to JVM bytecode (.class). For this particular class, ReverseComparator, it actually does not care about the generic type of the object that's being compared. It does not use the generic in any way, and has therefore its generic defined using the parent of all classes, Object. Then, when the method reverseOrder() is called, the particular instance of ReverseComparator is casted to the particular type from the calling context, inferred by the compiler, or by the developer's specification using the Collections.<MyClass>reverseOrder() syntax.

The reason the compiler accepts this unsafe cast from Object -> T, is because of @SuppressWarnings("unchecked") above this method, allowing unchecked casts.

answered May 21 '22 at 21:39

Devxln

556
6
18

Your answer is not right, actually I changed "Arrays.sort(new Integer[]{2, 4}, comparator);" to two lines as "var comparator = Collections.reverseOrder(); Arrays.sort(new Integer[]{2, 4}, comparator);", it is a valid code and running as expected, you answer is not able to explain that. – IcyBrk May 21 '22 at 23:26
Sure, that is because the generic type `? super T` is used, basically accepting T, and all its parent classes, including the parent of all classes, `Object`. – Devxln May 22 '22 at 20:18
The type parameter T in `Comparator` is substituted by `Comparable – IcyBrk May 22 '22 at 22:54
Yes, in the type set `? super T` is `Object`. – Devxln May 23 '22 at 16:21

newacct · Answer 2 · 2022-05-30T07:42:34.567

The variable comparator has type Comparator<? super Integer> (or Comparator<Integer>; it doesn't matter for our purposes). The compiler sees that you want the Collections.reverseOrder() method to return the type Comparator<? super Integer>, so it infers the T in the call to Collections.reverseOrder() that will make it return a Comparator<? super Integer>. It might, for example, infer T = Integer, so the Collections.reverseOrder() call will return a Comparator<Integer> (or it is also valid to infer T = Object, so that Collections.reverseOrder() will return a Comparator<Object>; it doesn't matter either way). As for how the Collections.reverseOrder() gets a value of the type Comparator<Integer>, that's an internal implementation detail of the library.

In the implementation of the library you are looking at, it has a single global comparator instance, ReverseComparator.REVERSE_ORDER. But how can Collections.reverseOrder() return this no matter what T is? For example, it is not possible for something to be Comparator<Integer> and Comparator<String> at the same time. So basically, the library is lying. ReverseComparator.REVERSE_ORDER is declared as some dummy type of comparator (it happens to be Comparator<Comparable<Object>>, but it doesn't really matter; it could be Comparator<Math> for all we care), and then inside the Collections.reverseOrder() method it does an unchecked cast of ReverseComparator.REVERSE_ORDER into the right type of comparator that it wants to return (Comparator<T>).

This unchecked cast is theoretically "incorrect" because ReverseComparator is not actually a Comparator<T> for any T other than Comparable<Object> (and basically nobody ever implements Comparable<Object>, so it is basically always "incorrect"). However, generics are erased at runtime (that's why the cast is "unchecked" -- it is not possible to check it at runtime), so it won't cause any exceptions as long as using a ReverseComparator as a Comparator<Integer> won't lead to any invalid assumptions at runtime. The only thing that a Comparator<Integer> needs to do is have a method compare() that takes two Integers. ReverseComparator's compare() method is able to do that, since ReverseComparator's compare() method takes two Comparables, and Integers are Comparables. ReverseComparator's compare() method calls the compareTo() method on the second argument, passing the first argument; that is valid for Integers, since Integers are comparable to themselves. So this usage is safe, and the lie does not cause any problems.

If I were able to rewrite the reverseOrder() API from scratch and implement it in a "safe" way, I would probably do something like this:

public static <T extends Comparable<? super T>> Comparator<T> reverseOrder() {
    return new Comparator<T>() {
        public int compare(T c1, T c2) {
            return c2.compareTo(c1);
        }
    };
}

This guarantees that T is actually comparable to itself, and doesn't do any unchecked casts. One downside is that it needs to create a new Comparator instance for every call to reverseOrder(). (Perhaps using lambdas instead of anonymous classes could avoid that.)

How can Collection.reverseOrder() used in Arrays.sort()

2 Answers2