Java Generics: compareTo and "capture#1-of ?"

Question

The following gives me an error message:

public static List<Comparable<?>> merge(Set<List<Comparable<?>>> lists) {
    List<Comparable<?>> result = new LinkedList<Comparable<?>>();
    HashBiMap<List<Comparable<?>>, Integer> location = HashBiMap.create();

    int totalSize;
    for (List<Comparable<?>> l : lists) {
        location.put(l, 0);
        totalSize += l.size();
    }

    boolean first;
    List<Comparable<?>> lowest; //the list with the lowest item to add
    int index;

    while (result.size() < totalSize) {
        first = true;

        for (List<Comparable<?>> l : lists) {
            if (! l.isEmpty()) {
                if (first) {
                    lowest = l;
                }
                else if (l.get(location.get(l)).compareTo(lowest.get(location.get(lowest))) <= 0) { //error here
                    lowest = l;
                }
            }
        }
        index = location.get(lowest);
        result.add(lowest.get(index));
        lowest.remove(index);
    }
    return result;
}

The error is:

The method compareTo(capture#1-of ?) in the type Comparable<capture#1-of ?> is not applicable for the arguments (Comparable<capture#2-of ?>)

What's going on here? I made the type of everything Comparable so I could call .compareTo and sort this list. Am I using generics incorrectly?

Answer 1

List<?> means "List of anything", so two objects with this type are not the same: One could be a list of String, the other a list of BigDecimal. Obviously, those are not the same.

List<T> means "List of anything but when you see T again, it's the same T".

You must tell the compiler when you mean the same type in different places. Try:

public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) {
    List<T> result = new LinkedList<T>();
    HashBiMap<List<T>, Integer> location = HashBiMap.create();

[EDIT] So what does <T extends Comparable<? super T>> List<T> mean? The first part defines a type T with the following properties: It must implement the interface Comparable<? super T> (or Comparable<X> where X is also defined in terms of T).

? super T means that the type which the Comparable supports must T or one of its super types.

Imagine for a moment this inheritance: Double extends Integer extends Number. This is not correct in Java but imagine that Double is just an Integer plus a fraction part. In this scenario, a Comparable which works for Number also works for Integer and Double since both derive from Number. So Comparable<Number> would satisfy the super part for T being Number, Integer or Double.

As long as each of these types support the Comparable interface, they also satisfy the first part of the declaration. This means, you can pass in Number for T and the resulting code will also work when there are Integer and Double instances in the lists. If you Integer for T, you can still use Double but Number is not possible because it doesn't satisfy T extends Comparable anymore (the super part would still work, though).

The next step is to understand that the expression between static and List just declares the properties of the type T which is used later in the code. This way, you don't have to repeat this long declaration over and over again. It's part of the behavior of the method (like public) and not part of the actual code.