ecl3ctic ecl3ctic - 7 months ago 16
Java Question

Confusing explanation of limiting the type parameter of a generic binary search tree in Java

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
Mammal
s 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
Mammal
s 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.

Answer

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.