Java generic captures and comparable

Question

This is an implementation of a container that can be compared to any other container with a compatible key. I have a weird error using generics in Java, any ideas?

    private static class Container
    <Key extends Comparable<? super Key>, Value>
    implements Comparable<Container<? super Key, ?>> 
    {
        public Key key;
        public Value value;
        public Container(Key k, Value v) {
            key = k;
            value = v;
        }
        public int compareTo(Container<? super Key, ?> o) {
            return key.compareTo(o.key);
        }
    }
    ...

This is the error:

    compareTo(capture#98 of ? super Key) in
    java.lang.Comparable<capture#98 of ? super Key> cannot be applied to 
    (java.lang.Comparable<? super capture#822 of ? super Key>)
            return key.compareTo(o.key);
                      ^
    1 error

Answer 1

You're simply not implementing the interface correctly. You define Container as implementing Comparable<Pair<? super Key, Value>. That means that it must declare a method:

public int compareTo(Comparable<Pair<? super Key, Value> o)

but right now it doesn't, because it's missing the wildcard.

The problem in a broader sense is with your wildcard matching. The ? means "any type that matches these bounds". Critically, different instances of ? can be different concrete types; this is what the "capture of" types refer to.

Any time that you have question marks that you want to "pair up" at all, you should give that parameter a name so you can enforce the identity (e.g. introduce a generic parameter for the method). Whenever you use a ?, you're essentially saying that "I don't care at all what the concrete type of this parameter is", so you can't perform any operations that depend on matching parameters exactly (such as assignment).

---

Edit: in a more specific sense I think your intentions are slightly off. You've tried to declare a Container on a particular Key type as comparable to a Container on a different (superclass) of Key. I'm not convinced this is necessarily a good idea, as it introduces some asymmetry.

For instance, you're trying to make it so a Container<String> can be compared against a Container<Object>. But doing the comparison the other way round wouldn't even compile. Does this situation seem valid to you? I'd expect comparability to be symmetric, and it would confuse me that a.compareTo(b) is 1, but b.compareTo(a) doesn't return -1 but instead refuses to compile. This is why, for example Double implements Comparable<Double> and not Comparable<? super Double>.

EDIT for plain answer: So you should get rid of those wildcards, as it's not going to be possible to compare against an arbitrary object. Thus the definition would look like:

private static class Container
<Key extends Comparable<Key>, Value>
implements Comparable<Container<Key, ?>>
{
    ...

    public int compareTo(Container<Key, ?> o) {
        return key.compareTo(o.key);
    }
}

Answer 2

For some reason, Eclipse inserts "? super Type" when you create a Comparable type but that doesn't make sense (which superclass of Type will work in the compareTo()?).

Just get rid of "? super" and it will compile.

Answer 3

PECS: Producer extends, Consumer super.

Let's work backwards from the compareTo method. You want to compare to a container, and you want to compare using the keys (hence key.compareTo(o.key)). This means that your o must produce a Key, and your key must consume a Key. The first part means your method declaration should be public int compareTo(Container<? extends Key, ?> o), which then means you should implement Comparable<Container<? extends Key, ?>>. The second part means your Key should be a Comparable<? super Key>, which is how you had it.

private static class Container<Key extends Comparable<? super Key>, Value>
                    implements Comparable<Container<? extends Key, ?>> {

    public Key key;
    public Value value;

    public Container(Key k, Value v) {
        key = k;
        value = v;
    }

    public int compareTo(Container<? extends Key, ?> o) {
        return key.compareTo(o.key);
    }
}

Edit: Following exactly the comments below, the declaration would be a follows. Notice the flip in the keys calling compareTo, and how Key no longer needs to implement Comparable at all. You just need to take a Container that can produce some key that can consume a Key

private static class Container<Key, Value> implements
        Comparable<Container<? extends Comparable<? super Key>, ?>> {

    //fields and constructors...

    public int compareTo(Container<? extends Comparable<? super Key>, ?> o) {
        return -o.key.compareTo(key);
    }
}

Answer 4

This works, but looks like a hack:

    private static class Container
    <K extends Comparable<? super K>, Value>
    implements Comparable<Container<? extends Comparable<? super K>, ?>>
    {
        public K key;
        public Value value;
        public Container(K k, Value v) {
            key = k;
            value = v;
        }
        public int compareTo(Container<? extends Comparable<? super K>, ?> o) {
            return -o.key.compareTo(key);
        }
    }

I would certainly prefer to write key.compareTo(o.key), but I didn't manage to write the necessary generic constraint for that... :(