How to tell Java that two wildcard types are the same?

Question

I have written a small list sorter that works by using Key objects to extract specific "keys" from objects in comparable form. The sorter then sorts the list in accordance with all the keys in turn.

The sorter can sort using any set of keys that work on the given types of object. Each key is able to deal with one type of object and always returns the same type of comparable value.

class Sorter {
    public interface Key<T, V extends Comparable<V>> {
        public V get(T t);
    }
    static <T> void sort(List<T> data, final Key<T, ?> key[], final int dir[]) {
        Collections.sort(list, new Comparator<T>() {
            public int compare(T a, T b) {
                for (int i = 0; i < key.length; i++) {
                    final Comparable av = key[i].get(a), bv = key[i].get(b);
                    final int cmp = av.compareTo(bv);
                    if (cmp != 0) return cmp * dir[i];
                }
                return 0;
            }
        });
    }
}

So, for example, you could have a JSONStringKey that extracts a String (which is Comparable), and you could have a separate JSONNumericKey that extracts a Double) (which is also Comparable). Values from two different keys will never be compared, but the same key across two different objects will be compared.

class JSONStringKey extends Sorter.Key<JSONObject, String> {
    final String key;
    JSONStringKey(String key) {this.key = key;}
    public String get(JSONObject o) {return o.optString(key);}
}

class JSONNumericKey extends Sorter.Key<JSONObject, Double> {
    final String key;
    JSONNumericKey(String key) {this.key = key;}
    public Double get(JSONObject o) {return o.optDouble(key);}
}

...

// sort by price descending then name ascending
final Key<JSONObject, ?> keys[] = { new JSONNumericKey("price"), new JSONStringKey("name") };
sort(list, keys, new int[]{-1, 1});

Java warns about this line in the sorter:

final Comparable av = key[i].get(a), bv = key[i].get(b);

It warns that av and bv are declared with raw types: Comparable instead of Comparable<?>. And they are. But if I change the type to Comparable<?>, then the next line, av.compareTo(bv) fails, because two different Comparable<?> are not necessarily the same type. In my specific implementation, they will be, but I don't know how to express that to the type system.

How can I tell the type system that av and bv have exactly the same type? I can't "fix" it by giving a specific type (e.g. Comparable<String>) because in my example, the first key in the loop returns String (which implements Comparable<String>) and the second key in the loop returns Double (which implements Comparable<Double>).

I could write @SuppressWarnings("rawtypes") on the key[i].get() lines and @SuppressWarnings("unchecked") on the av.compareTo(bv) line, but I want to have the types checked as far as possible.

EDIT: thanks to the answer from davmac, creating an intermediary method that fixes to a specific comparable type works correctly:

public int compare(T a, T b) {
    for (int i = 0; i < key.length; i++) {
        final int cmp = compareKey(key[i], a, b);
        if (cmp != 0) return cmp * dir[i];
    }
}
private <V extends Comparable<V>> compareKey(Key<T, V> key, T a, T b) {
    final V av = key.get(a), bv = key.get(b);
    return av.compareTo(bv);
}

Answer 1

You need to use a type parameter to say that two 'unknown' types are the same. I thought that maybe you should change your method signature from:

static <T> void sort(List<T> data, final Key<T, ?> key[], final int dir[]) 

to

static <T,U> void sort(List<T> data, final Key<T,U> key[], final int dir[])

However, I don't think this would work with your full example, because the elements from the keys are not the same type:

// sort by price descending then name ascending
final Key<JSONObject, ?> keys[] = { new JSONNumericKey("price"), new JSONStringKey("name") };
sort(list, keys, new int[]{-1, 1});

So, instead, you could extract the relevant part from the sorter into a generic method:

        public int compare(T a, T b) {
            for (int i = 0; i < key.length; i++) {
                final Comparable<?> av = key[i].get(a), bv = key[i].get(b);
                final int cmp = doCompareTo(av, bv);
                if (cmp != 0) return cmp * dir[i];
            }
            return 0;
        }

        private <U extends Comparable<U>> int doCompareTo(U a, U b) {
            return a.compareTo(b);
        }

... but this wouldn't work either, because a Comparable<U> doesn't necessarily extend U. The problem is that your Keys return Comparable<V>, but you want to compare two of these; that's not possible. A Comparable<V> can be compared with a V, but not with another Comparable<V>.

In general, there are too many issues here to give you a simple solution. You need to re-think the types completely. For instance, if you want the Key's get method to return objects that are comparable with each other, then it should return V and not Comparable<V>.

I hope the suggestions above at least point you in the right direction.

Answer 2

The way you have them declared right now, you can use a private capture helper:

static <T> void sort(List<T> data, final Key<T, ?> key[], final int dir[]) {
    Collections.sort(list, new Comparator<T>() {
        public int compare(T a, T b) {
            for (int i = 0; i < key.length; i++) {
                final int cmp = compareHelper(key[i], a, b);
                if (cmp != 0) return cmp * dir[i];
            }
            return 0;
        }
    });
}

private static <T, U extends Comparable<U>> int compareHelper(Key<T, U> k, T a, T b) {
    U av = k.get(a), bv = k.get(b);
    return av.compareTo(bv);
}

Or you can get rid of V from Key altogether and make the constraint on sort only, which will be parameterized on U:

public interface Key<T, V> {
    public V get(T t);
}
static <T, U extends Comparable<? super U>> void sort(List<T> data, final Key<T, U> key[], final int dir[]) {
    Collections.sort(list, new Comparator<T>() {
        public int compare(T a, T b) {
            for (int i = 0; i < key.length; i++) {
                U av = k.get(a), bv = k.get(b);
                final int cmp = av.compareTo(bv);
                if (cmp != 0) return cmp * dir[i];
            }
            return 0;
        }
    });
}