4

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.

Improve this question
0

3 Answers 3

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Okay, after an hour or so of pondering and wonderful responses to my question I think I've got this. For < T extends Comparable< T>, a BST of Mammals will work just fine if it is full of Cats and Dogs (which are Comparable< Mammal> via inheritance). But if you want a BST of Cats, then this won't work because the Cats are only Comparable on the Mammal level. Therefore if we restrict the type argument for a BST to be < T extends Comparable< ? super T>, then we can have BST of Mammals like before, but we can ALSO have a BST of Cats, because the Cats will then be compared on the superclass level.
2

Sorry, rewriting this to make i more clear

Consider the interface 

< T extends Comparable<T> >

and then consider your subclass Cat

Cat extends Comparable<Cat>

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

Cat extends Comparable<Animal>

The author changes this to 

< T extends Comparable<? super T> >

so that now we can add objects like 

Cat extends Comparable<Animal>

because the parameter going into Comparable must be a superclass instead of the class itself. So it can be a Mammal -> Animal -> Object, but not, say a String

Improve this answer

2 Comments

I'm sorry, I'm struggling to find the context to which your answer is applying. I was talking purely about the binary search tree's type parameter < T extends Comparable(something)> and it seems here you're talking about the Cat's implementing of the Comparable interface? Your answer is a little too concise and I'm new to generics so to me, it sounds like you're talking about something different :\
sorry, what i wrote was confusing, see if htis version makes sense
0

The main point is this. The class which you are choosing, should either implement a Comparable interface with the parameter as It Self or it can be any other super class which takes in class the Base class as the comparable parameter.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.