Generic Binary Search Tree, Allowing Only Comparable Elements

[X-Malleus]

Hi, everyone. I'm new to generics, and I can't figure out exactly how to do this. I need to implement a binary search tree. This is easy enough to do if I only allow it to contain integers, but I want it to accept any object that implements Comparable. So normally, the class definition would look something like this:

public class BinarySearchTree {
...
}

I want to make it a BinarySearchTree that can, and must, be assigned to a particular Comparable type. Something like this:

public class BinarySearchTree<Comparable> {
...
}

I know that this isn't the correct way to do it, though. How can I do this?

[iluxa]

public class BinarySearchTree<T extends Comparable> {
...
}

[X-Malleus]

public class BinarySearchTree<T extends Comparable> {
...
}

I found things looking like this in searching for the answer to this problem. I must admit that I'm confused by it, though. From what I understand, extends causes the subclass to inherit all methods and variables from the superclass. Comparable is an interface, though, so doesn't that mean that anything that extends Comparable is also an interface? I'm sure that I'm missing something here, but my line of thinking is that if T extends Comparable, then T is an interface, but I want to pass a class, such as Integer, when I create a new BinarySearchTree. Something in my understanding of one or more of these ideas must be incorrect.

[iluxa]

actually, when applied to interfaces, extends behaves a bit different:

interface A {
...
}
interface B extends A {
...
}

in my code snippet,

T extends Comparable

means you'll be able to use any type as long as its a sub-type of Comparable. Since Integer implements Comparable, you can use Integer.

[X-Malleus]

Ah, well now I think I understand it better. Thankfully, my code will now compile, but I do get a warning when I do this:

public class BinarySearchTree<T extends Comparable> {
...
}

The warning is this:

Comparable is a raw type. References to generic type Comparable<T> should be parameterized.

I fixed this by using BinarySearchTree<T extends Comparable<T>> instead. Will this produce the results that I'm looking for?

[iluxa]

I think so... Your general approach is correct, the syntax technicalities of Java generics though are not for mere mortals... I mean take a look here:

Enum (Java 2 Platform SE 5.0)

public abstract class Enum<E extends Enum<E>>

!!!

[X-Malleus]

Hahah wow! That is indeed a bit crazy-looking. In any case, it seems that I've gotten what I need. Thanks so much for your help!