I'm new to generics (and Java, and Stack Overflow), and there is a point in the textbook I'm learning from where it discusses the implementation of a generic binary search tree (excerpt below).
The Comparable interface is generic, so let’s consider storing the following type of elements in our search tree:
< T extends Comparable< T>>
This still causes a problem. Suppose that both Dog and Cat are subclasses of a class Mammal and that the Mammal class implements the Comparable interface. Now if we create a binary search tree that stores Mammal objects, then a Dog and Cat could be added, but are not really comparable to each other. So this solution, if used in this particular way, has the same problem as using the nongeneric version of Comparable. A more comprehensive solution, though not as intellectually satisfying, is to write the generic type as:
< T extends Comparable< ? super T>>
This declaration restricts the comparable nature of the element to any superclass of T.
So I get why the type parameter needs to be Comparable< T>, but then the book claims that this can pose problems if the tree of Mammals contains different subtypes that attempt to invoke the compareTo() method on each other. Well if the reference type for the Cat and Dog objects in the tree is Mammal, then wouldn't they be invoking Mammal's compareTo() method anyway (being Comparable< Mammal>), making it a valid comparison (just on the Mammal level)?
I don't understand what difference Comparable< ? super T> makes, because would that not be the same thing, except perhaps if Mammals aren't Comparable then it falls back to a Comparable superclass like the Animal class or something?
I'm probably missing something, like some nasty consquence of type erasure or something that will cause the comparisons to not work like I'm thinking they would.
Okay, so you understand that <T extends Comparable<T>> works with a class like this:
class Mammal extends Comparable<Mammal>
Now you have a subclass of Mammal, Cat: class Cat extends Mammal. Due to inheritance Cat also implements Comparable<Mammal>, and, as you said, it can compare to all mammals (including cats, of course) due to the compareTo(Mammal) method that it inherited from Mammal.
But now the problem is that Cat does not work with the bound <T extends Comparable<T>>, because Cat does not implement Comparable<Cat>. You cannot solve this by having Cat implement Comparable<Cat>, because you can only implement an interface with one type parameter.
But conceptually, there is no problem with sorting a list of Cat, since Cats can compare to other Cats (they can compare to all mammals, which is more general; but the point is that they can compare to cats). So the problem is that our bound is too restrictive.
<T extends Comparable<? super T>> solves this problem, and allows Cat to be used. Recall the PECS rule -- Producer extends Consumer super. Well, the Comparable is a consumer and not a producer, because you pass an argument of type T into its compareTo method (consume), but no methods needs to return type T (produce). Hence, a super wildcard is appropriate.