Using generics and the Comparable interface to implement a node

[Chris Waguespack]

Hello everyone. It's been a while since I've been to the forums, but I have a problem I just can't figure out.

I'm trying to implement a node for a tree-based data structure (just a binary search tree to start with), and I want this node to have a key that is comparable. I would also like the node to be comparable, using its key to determine the result. My problem deals with combining generics and the comparable interface (mainly my lack of experience using them :P). Please see the code below (constructors/getters/setters omitted).

When I try to run this, it says "The type BSTNode<K> must implement the inherited abstract method Comparable<BSTNode>.compareTo(BSTNode)" and "The method compareTo(BSTNode<K>) of type BSTNode<K> must override or implement a supertype method".
If I remove the "<K>" from the method's parameter type, those errors go away, but I'm given the error "The method compareTo(K) in the type Comparable<K> is not applicable for the arguments (Comparable)". When I look at the return type for getKey(), this.getKey() returns K, while node.getKey() returns Comparable. I know this has something to do with how generics work, but I still can't figure it out, even after reading Oracle's generics tutorial.

So, after all that, my questions are:
First, am I even doing this right for what I want to accomplish?
Second, is there a better way of doing this?
Third, if I am doing this correctly, how do I fix my errors?

Thank you for help!

/**
 * Node for a binary search tree. This node can use any key that is comparable.
 * 
 * @author Chris Waguespack
 */
public class BSTNode<K extends Comparable<K>> implements Comparable<BSTNode> {
	
	private K key;
	private BSTNode<K> leftChild;
	private BSTNode<K> parent;
	private BSTNode<K> rightChild;
	
	// Constructors
	// Getters
	// Setters
	
	@Override
	public int compareTo(final BSTNode<K> node) {
		return this.getKey().compareTo(node.getKey());
	}
}

[Rob Spoor]

Your class implements Comparable<BSTNode> so the compiler demands a public int compareTo(BSTNode) method. The solution is simple:

public class BSTNode<K extends Comparable<K>> implements Comparable<BSTNode<K>>

I would like to make one other improvement though:

public class BSTNode<K extends Comparable<? super K>> implements Comparable<BSTNode<K>>

If you leave out the ? super part you will only allow types that are comparable to objects of the exact same type. java.lang.Timestamp could not be used though, as it does not implement Comparable<Timestamp> but through inheritance Comparable<Date>. The ? super part makes sure that classes like Timestamp can also be used.

[Chris Waguespack]

Ah! Thank you! I can't believe I didn't spot that earlier.

Rob Spoor wrote:I would like to make one other improvement though:

public class BSTNode<K extends Comparable<? super K>> implements Comparable<BSTNode<K>>

If you leave out the ? super part you will only allow types that are comparable to objects of the exact same type. java.lang.Timestamp could not be used though, as it does not implement Comparable<Timestamp> but through inheritance Comparable<Date>. The ? super part makes sure that classes like Timestamp can also be used.

Ok, I remember seeing something like that in the tutorial, but I couldn't figure out exactly why it was needed. Thank you for clearing this up for me.

[Rob Spoor]

You're welcome.