Java Wildcard Capture failing for unknown reason

Question

In writing a static generic method to do an insertion Sort. I ran across the following wild card capture problem that I cannot solve. There is a simple solution to the problem but I still would like to know why my original attempt does not compile. I have done a similar thing for quicksort which compiles correctly.

Note: I know that by changing the declaration from List<? extends T> col to List<T> col the code will compile and run properly. But because I am capturing the wildcard in the "move" method below, it should also compile if I leave the "? extends T" as is. Does anyone have any idea why it refuses to compile? I am using jdk1.8.0_60 in Eclipse( NEON ).

Here is the relevant code that does not compile:

public static <T extends Comparable<? super T>> 
    void insertionSort(List<? extends T> col) {

    for ( int i = 1 ; i < col.size(); i++ ){
        int j = i - 1 ;
        T key = col.get(i);
        while ( j > -1  && col.get(j).compareTo(key)  > 0 ) {
        T ele = col.get(j);
        InsertionSort.move(j+1,ele,col); // **DOES NOT COMPILE** 
        j = j - 1;
        }
        InsertionSort.move(j+1, key, col); // **DOES NOT COMPILE** 
    }
}

private static <T> void move(int jplus1, T key, List<T> col) {
    col.set(jplus1, key);   
}

I am doing a similar thing with quickSort which, believe it or not , compiles correctly. Here is the quicksort that actually compiles correctly: Notice the swap method.

public static <T extends Comparable<? super T>> 
void quickSort(List<? extends T> col) {
    Objects.requireNonNull(col);
    _quickSort(col, 0, col.size() - 1);
}

private static <T extends Comparable<? super T>> 
    void _quickSort(List<? extends T> col, int start, int end) {
    int partitionPoint = 0;
    if (start < end) {
        partitionPoint = partition(col, start, end);
        _quickSort(col, start, partitionPoint - 1);
        _quickSort(col, partitionPoint + 1, end);
    }
}

private static <T extends Comparable<? super T>> 
int partition(List<? extends T> col, int start, int end) {
    T pivot = col.get(end);
    int partitionIndex = start;
    for (int j = start; j <= (end - 1); j++) {
        int cmp = col.get(j).compareTo(pivot);
        if (cmp < 1) {
            swap(j, partitionIndex, col); // COMPILES CORRECTLY
            partitionIndex++;
        }
    }
    swap(partitionIndex, end, col);
    return partitionIndex;
}

private static <T> void swap(int j, int partitionIndex, List<T> col) {
    T temp = col.get(j);
    col.set(j, col.get(partitionIndex));
    col.set(partitionIndex, temp);
}

Answer 1

The short version: The problem is the T key parameter of the move method.

More in depth: So you have a ? extends T wildcard, and a List that contains that type. Let's call whatever the type actually is U. Since you are passing the list directly on, in its original type as you received it, you are calling the <U> version of move. This requires that you pass it a List<U> - works fine - and a U key - but the variable you're passing for the key is type T. U is bound as a subclass of T, so that's an unsafe cast.

You could alternatively be calling the <T> version of move. In that case, T key would be fine, but now you're trying to pass a List<U> as a List<T> and that is an unsafe cast. Either way you have an unsafe cast, so the compiler reports an error.

If you eliminate the intervening variable and call move(j+1, col.get(i), col), I believe that would compile because the compiler can tell that the result of col.get(i) is of type U, satisfying the type signature of move<U>.

To show a bit more explicitly why this is a problem, let's go through an example. I'll pretend that Number implements Comparable<Number> because it makes things easier to follow. You call your sort as follows:

ArrayList<Integer> list = new ArrayList<>();
list.add(2);
list.add(1);
insertionSort<Number>(list);

Now, your code gets to the first move call. On that line, you have:

• First argument: j+1, of type int
• Second argument: ele, of type Number
• Third argument: col, of type List<? extends Number>

The ? extends Number in this case happens to be Integer.

Now, given those arguments, what is the generic type of move that gets called? There are two obvious possibilities, move<Integer> and move<Number>.

move<Integer>: This requires a second argument (T key) of type Integer. You're giving it a variable of type Number. That doesn't fit, so this option doesn't work.

move<Number>: The second argument works fine, but now look at the third. The third argument requires type List<Number>. What you're passing it is List<Integer>. If the compiler allowed you to do that, it would mean that the move method would be allowed to add, say, 3.14159 to the list, which would break the list's constraint of only containing integers. Therefore that doesn't fit, so this option doesn't work.

There aren't any other relevant options to consider. So, the compiler gets to that line, tries to figure out whether it's calling move<Integer>, move<Number>, move<String>, or whatever else, and finds that nothing works. There is no version at all of move that fits all three arguments you're trying to pass to it at once, so it throws an error.

Answer 2

This compile error is caused by the Producer Extends, Consumer Super Principle : PECS What is PECS (Producer Extends Consumer Super)?

Bottom line, your code is both a producer AND a consumer (the consumer is the move method) so you can't use ? extends T because you can't do a put (or set in this case) using an extends.

EDIT

why does your quicksort swap method work then?

Notice the method signature difference

quicksort <T> void swap(int j, int partitionIndex, List<T> col)

vs

insertionSort <T> void move(int jplus1, T key, List<T> col) {

The difference in the quicksort is you give the indexes to swap but in the insertionSort that doesn't compile you provide one of the values as a type T.
By just using the indexes you have to fetch the values from the list so the type T is a brand new inferred type. In your insertionSort you provide an already fetched T value which is the wrong capture type compared to the new inferred type which can't have an extends in it because you are both getting and putting.

If you change your code to use just offsets it will compile but you will have to modify your method to insert differently because the way you have it you will lose the value to be inserted earlier in the list if you change it this way.

Answer 3

The difference between swap and move is that swap does not take generic key of type T. That is what the compiler is complaining about, as described in the previous answers. Using wildcards in your methods does not make sense at all. Why do you need wildcard at all? Can't you just do this:

public static <T extends Comparable<T>> void insertionSort(List<T> col) {
    for (int i = 1; i < col.size(); i++) {
        int j = i - 1;
        T key = col.get(i);
        while (j > -1 && col.get(j).compareTo(key) > 0) {
            T ele = col.get(j);
            move(j + 1, ele, col); // **DOES NOT COMPILE**
            j = j - 1;
        }
        move(j + 1, key, col); // **DOES NOT COMPILE**
    }
}

private static <T> void move(int jplus1, T key, List<T> col) {
    col.set(jplus1, key);
}

Answer 4

I figured out a way to overcome the problem: It requires creating an additional method to properly capture the wildcard:

public static <T extends Comparable<? super T>> void insertionSort(List<? extends T> col){
    _insertionSort(col,1,col.size());
}
public static <T extends Comparable<? super T>> void _insertionSort(List<T> col,int start,int end){