Java Wildcard Capture error for unknown reason
When writing a static generic method to perform insertion sort. I am facing the following card grabbing issue which I cannot solve. There is a simple solution to the problem, but I would still like to know why my initial attempt is not compiling. I've 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 work correctly . But since I am taking the wildcard in the "move" method below, it should also compile if I leave the "?" extends T "as is. Does anyone know why it refuses to compile? I am using jdk1.8.0_60 in Eclipse (NEON).
Here's the relevant code that doesn't 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 similar with quickSort, which, believe it or not, compiles correctly. Here is an online sort that actually compiles correctly. Pay attention to 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);
}
source to share
Short version: The problem is the T key
method parameter move
.
More details: you have a wildcard ? extends T
and List
which contains this type. Let's name any type U
. Since you are passing the list directly, in its original type, when you got it, you are calling the <U>
version move
. This requires you to pass it List<U>
- works great - and U key
- but the variable you pass for the key is the type T
. U
bound as a subclass T
, so it's an unsafe cast.
Alternatively, you can call version <T>
move
. In this case it T key
will be fine, but now you are trying to transfer List<U>
as List<T>
, and this is an unsafe translation. You have an unsafe cast anyway, so the compiler reports an error.
If you remove the intermediate variable and call it move(j+1, col.get(i), col)
, I believe it will compile because the compiler can tell that the result col.get(i)
is of a type U
that satisfies the type signature move<U>
.
To show more clearly why this is a problem, please skip the example. I will pretend to Number
implement Comparable<Number>
it because it makes things easier. You call your view like this:
ArrayList<Integer> list = new ArrayList<>();
list.add(2);
list.add(1);
insertionSort<Number>(list);
Now your code hits the first call move
. On this line, you have:
- First argument:,
j+1
likeint
- Second argument:,
ele
typeNumber
- Third argument:,
col
likeList<? extends Number>
In this case ? extends Number
it turns out Integer
.
Now, given these arguments, what is the generic type move
that is being invoked? There are two obvious possibilities: move<Integer>
and move<Number>
.
move<Integer>
: This requires a second argument ( T key
) of the type Integer
. You give it a type variable Number
. It doesn't fit, so this option doesn't work.
move<Number>
: The second argument works great, but now let's look at the third. The third argument requires a type List<Number>
. What you are passing on is this List<Integer>
. If the compiler allowed you to do this, it would mean that the method move
would be allowed to append to, say, 3.14159
a list, which would break the limit of the list to contain only integers. Therefore it does not fit, therefore this parameter does not work.
There are no other suitable options to consider. Thus, the compiler gets to that line, trying to figure out whether this is a challenge move<Integer>
, move<Number>
, move<String>
or something else, and discovers that nothing works. There is no version at all move
that matches all three arguments you are trying to pass to it at once, so it throws an error.
source to share
This compilation error is caused by producer renewal, superuser principle: PECS What is PECS (producer extend consumer super)?
Bottom line, your code is both producer and consumer (consumer is a method move
), so you can't use ? extends T
, because you can't put (or set
in this case) with extends
.
EDIT
why does your quicksort method swap
work?
Note the difference in the method signature
quicksort <T> void swap(int j, int partitionIndex, List<T> col)
against
insertingSort <T> void move(int jplus1, T key, List<T> col) {
The difference in quicksort is that you give the indices to swap, but in the insertionSort file, which does not compile, you specify one of the values as a type T
.
By simply using indices, you have to retrieve values from the list for the type to T
be the new intended type. In your insertionSort, you are providing the already received value T
, which is the wrong capture type compared to the new inferred type, which cannot have extends
in it, because you both get and place.
If you change your code to use offsets it will compile, but you have to change your method to insert in a different way because as you get it you will lose the value that was inserted earlier in the list if you change it like this way,
source to share
The difference between swap and move is that swap does not accept a shared key of type T. This is what the compiler complains about, as described in the previous answers. Using wildcards in your methods doesn't make any sense. Why do you need a template? Could 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);
}
source to share
I figured out a way to overcome the problem: it requires creating an additional method to fix the template correctly:
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){
source to share