Confusing explanation of Java binary search tree type parameter constraint

Question

I am new to generics (both Java and Stack Overflow), and it makes sense in a tutorial that I study when it discusses the implementation of a generic binary search tree (excerpt below).

The Comparable interface is general, therefore, we will consider the possibility of storing the following type of elements in our search tree:

<T extends Comparable <T →

This is still causing the problem. Assume that both Dog and Cat are subclasses of the Mammal class and that the Mammal class implements the Comparable interface. Now, if we create a binary search tree in which Mammal objects are stored, then Dog and cat can be added, but are not really comparable with each other. So, this solution, if used this way, has the same problem as using the inorganic version of Comparable. A more comprehensive solution, although not intellectually satisfying, is to write a generic type like:

<T expands comparable <? super T →

This declaration limits the element's comparable nature to any superclass of T.

So, I understand why the type parameter should be Comparable< T> , but then the book claims that this can cause problems if the Mammal tree contains different subtypes that try to call the compareTo() method for each other. Well, if the reference type for the Cat and Dog objects in the Mammal tree, will it not refer to the Mammal compareTo() method in any case (being Comparable< Mammal> ), making it a valid comparison (only at the Mammal level)?

I don’t understand what difference is Comparable< ? super T> Comparable< ? super T> because it is not the same, except if, perhaps, if Mammal not Comparable , then it returns to the Comparable superclass, for example, to the Animal class or something else?

I probably missed something, for example, some unpleasant coincidence of type erasure or something that would lead to comparisons not working, as if I think they would.

Answer 1

So, you understand that <T extends Comparable<T>> works with this class:

 class Mammal extends Comparable<Mammal> 

You now have a subclass of Mammal , Cat : class Cat extends Mammal . Because of inheritance, Cat also implements Comparable<Mammal> , and, as you said, it can compare with all mammals (including cats, of course) because of the compareTo(Mammal) method that it inherited from Mammal .

But now the problem is that Cat does not work with the <T extends Comparable<T>> binding, because Cat does not implement Comparable<Cat> . You cannot solve this problem if Cat implement Comparable<Cat> because you can implement an interface with only one type parameter.

But conceptually there is no problem sorting the Cat list, since Cat can be compared to another Cat (they can be compared to all mammals, which is more general, but the fact is that they can be compared to cats). Therefore, the problem is that our border is too restrictive.

<T extends Comparable<? super T>> <T extends Comparable<? super T>> solves this problem and allows you to use Cat . Recall the PECS rule - Manufacturer extends consumer super . Well, Comparable is a consumer, not a manufacturer, because you pass an argument of type T to its compareTo method (consume), but no methods should return a type T (produce). Therefore, the super pattern is suitable.

Answer 2

Sorry to rewrite this to make me more clear

Consider the interface

 < T extends Comparable<T> > 

and then consider your subclass of Cat

 Cat extends Comparable<Cat> 

This breaks down a lot of things in the binary search tree if there are other classes like Dog, because Comparable needs two of the same types. Cat should look like this and then

 Cat extends Comparable<Animal> 

The author changes this to

 < T extends Comparable<? super T> > 

so that we can now add objects such as

 Cat extends Comparable<Animal> 

because the parameter going to Comparable must be a superclass, not the class itself. So it could be a mammal -> Animal -> Object, but not, say, String

Answer 3

The main thing is that. The class you choose must either implement a Comparable interface with a parameter like It Self , or it can be any other superclass that accepts the base class class as a comparable parameter.