Using Java 5.0 generics

[Steven Davies]

Hi,

I'm having my first go at wrestling with parameterised types in Java and
I've come across something which I can't quite get my head around, or at
least I don't know how I could implement it:

I need to write a binary tree class which can store a lot of the same
item (hence the generics), which all implement the Comparable interface
to make it easier to insert them into the tree.

I don't have a problem with writing the actual insert/find/remove
algorithms, but I can't work out how to define a BinaryTree class that
can only take Comparable elements of a certain class - something like:

public class BinaryTree<E implements Comparable> {}

...and then have a TreeNode class which takes the same object type as the
BinaryTree and stores a reference to that particular object and pointers
to the parent/left/right nodes in the tree.

I know I could implement it by creating a BinaryTree of Comparables, but
then someone could accidentally insert a different element into the
tree, causing ClassCastExceptions all over the place. Another
alternative would be to hard-code the classes to the one I'm using for
this project, which I know includes compareTo, but that's not very
extensible..

If that makes any sense to anyone, can you describe if and how it could
be done please?

Thanks,
Steven Davies

 

[Oscar kind]

I need to write a binary tree class which can store a lot of the same
item (hence the generics), which all implement the Comparable interface
to make it easier to insert them into the tree.

I don't have a problem with writing the actual insert/find/remove
algorithms, but I can't work out how to define a BinaryTree class that
can only take Comparable elements of a certain class - something like:

public class BinaryTree<E implements Comparable> {}

..and then have a TreeNode class which takes the same object type as the
BinaryTree and stores a reference to that particular object and pointers
to the parent/left/right nodes in the tree.

As the nodes are part of the internal representation of the tree, the tree
will be the only object instantiating them: you have therefore complete
control and can use the syntax you gave above. Personally, I'd even prefer
to make the node class an inner class.


[...]

If that makes any sense to anyone, can you describe if and how it could
be done please?

By applying OO principles. In your case, this means:
- The tree will be the only one to alter it's state.
- Only the tree knows about it's internal structure; no other class needs
to know about the nodes, nor may it have write access to them.

Otherwise, I think you're on the right track.

 

[Chris Smith]

I don't have a problem with writing the actual insert/find/remove
algorithms, but I can't work out how to define a BinaryTree class that
can only take Comparable elements of a certain class - something like:

public class BinaryTree<E implements Comparable> {}

..and then have a TreeNode class which takes the same object type as the
BinaryTree and stores a reference to that particular object and pointers
to the parent/left/right nodes in the tree.

From within the BinaryTree class, you would just use a TreeNode<E>, and
define a TreeNode<T extends Comparable> to have references of type T for
the object, and TreeNode<T> for the parent, left, and right pointers.

I only chose a different type parameter name -- T -- to avoid confusion.
Unless TreeNode is a nested class, you may use E instead. If TreeNode
is a nested class, then you probably want to pick unique names as well
in order to be clear.

Is that your question?

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Steven Davies]

From within the BinaryTree class, you would just use a TreeNode<E>, and
define a TreeNode<T extends Comparable> to have references of type T for
the object, and TreeNode<T> for the parent, left, and right pointers.

I only chose a different type parameter name -- T -- to avoid confusion.
Unless TreeNode is a nested class, you may use E instead. If TreeNode
is a nested class, then you probably want to pick unique names as well
in order to be clear.

Is that your question?

Yes, thanks, I realised that in my BinaryTree class definition I had said:

public class BinaryTree<E extends Comparable> instead of
public class BinaryTree<E extends Comparable<E>>.

I had made the same mistake in defining TreeNode - by saying it
implements Comparable<TreeNode> instead of implementing
Comparable<TreeNode<E>>.

Thanks again

Now back to programming the thing

 

[John C. Bollinger]

Yes, thanks, I realised that in my BinaryTree class definition I had said:

public class BinaryTree<E extends Comparable> instead of
public class BinaryTree<E extends Comparable<E>>.

I had made the same mistake in defining TreeNode - by saying it
implements Comparable<TreeNode> instead of implementing
Comparable<TreeNode<E>>.

For full generality you should be using Comparable<? super E>. This
provides for the case where you want to store objects of classes that
extend a Comparable class. If you don't want to worry about that,
though, then what you've chosen will cover most cases.

 

[Steven Davies]

For full generality you should be using Comparable<? super E>. This
provides for the case where you want to store objects of classes that
extend a Comparable class. If you don't want to worry about that,
though, then what you've chosen will cover most cases.

If I did use that syntax, how would I reference the ? in the program?
Would I define a class as:

public class BinaryTree<E extends Comparable<? super E>>

And then how would I go about using it later on? Just carry on using the E?

Thinking about it, that line above reads as "public class BinaryTree of
type E, where E extends (implements) Comparable, and is comparable to
anything which is an E or a subclass thereof." Am I right there?

Thanks

PS sorry John, I sent it via email by mistake.

 

[John C. Bollinger]

If I did use that syntax, how would I reference the ? in the program?
Would I define a class as:

public class BinaryTree<E extends Comparable<? super E>>

Yes, exactly so.

And then how would I go about using it later on? Just carry on using
the E?

Yes, unless you do something strange that requires assigning an E to a
variable of type Comparable. Then you would need to describe the

Thinking about it, that line above reads as "public class BinaryTree of
type E, where E extends (implements) Comparable, and is comparable to
anything which is an E or a subclass thereof." Am I right there?

No, more like this: "a class named BinaryTree and characterized by a
type that is Comparable to itself or to some superclass of itself."
Note one important thing here: E is comparable to some *specific* type,
which, though not precisely known at compile time (for this class), must
be either E itself or one of its superclasses. Note also that any
implementation of Comparable<E> is already comparable to instances of
E's subclasses. What the wildcard gains you is the ability to use a
type parameter (when you declare a BinaryTree reference) where the type

PS sorry John, I sent it via email by mistake.

Duly ignored.

 

[Steven Davies]

Yes, exactly so.



Yes, unless you do something strange that requires assigning an E to a
variable of type Comparable. Then you would need to describe the



No, more like this: "a class named BinaryTree and characterized by a
type that is Comparable to itself or to some superclass of itself." Note
one important thing here: E is comparable to some *specific* type,
which, though not precisely known at compile time (for this class), must
be either E itself or one of its superclasses. Note also that any
implementation of Comparable<E> is already comparable to instances of
E's subclasses. What the wildcard gains you is the ability to use a
type parameter (when you declare a BinaryTree reference) where the type
inherits Comparable<T> from a superclass T; the non-wildcard version
will not permit that.

Sorry, you lost me there ;-)

Do you mean that if I use Comparable<E>, only subclasses of Object which
implement Comparable can be inserted into the structure, but if I use
Comparable<? super E> then I could insert anything which subclasses
anything which implements Comparable, or anything which implements
Comparable itself?

Now, when I change my BinaryTree class definition to:

public class BinaryTree<E extends Comparable<? super E>>

And my TreeNode definition to:

public class TreeNode<E extends Comparable<? super E>> implements
Comparable<TreeNode<? super E>>

Then javac complains I haven't got a compareTo method for a <? super E>
type..but how would I define one? The error is below:

analyser/TreeNode.java:11: analyser.TreeNode is not abstract and does
not override abstract method compareTo(analyser.TreeNode<? super E>) in
java.lang.Comparable

If I change the definition of compareTo to:

public int compareTo (TreeNode<? super E> otherNode)

Then I get the following error:

analyser/TreeNode.java:25: compareTo(? super E) in
java.lang.Comparable<? super E> cannot be applied to
java.lang.Comparable<capture of ? super E>)
return data.compareTo (otherNode.getData());
^
Any ideas?

Thanks

 

[John C. Bollinger]

Sorry, you lost me there ;-)

Do you mean that if I use Comparable<E>, only subclasses of Object which
implement Comparable can be inserted into the structure, but if I use
Comparable<? super E> then I could insert anything which subclasses
anything which implements Comparable, or anything which implements
Comparable itself?

Yes, if I understand you correctly that's what I mean. For instance,
suppose you wanted something like this:

public abstract class AbstractElement implements
Comparable<AbstractElement> {

// ...
}

public class IntegerElement extends AbstractElement {
// ...
}

public class DoubleElementextends AbstractElement {
// ...
}

Without a the wildcard, you could declare a BinaryTree<AbstractElement>
but not a BinaryTree<IntegerElement>, because IntegerElement does not

Now, when I change my BinaryTree class definition to:

public class BinaryTree<E extends Comparable<? super E>>

And my TreeNode definition to:

public class TreeNode<E extends Comparable<? super
E>> implements Comparable<TreeNode<? super E>>

I'd recommend that you make TreeNode an inner class, in which case it is
within the scope of the containing class' type parameter:

public class BinaryTree<E extends Comparable<? super E>> {

// ...

private class TreeNode implements Comparable<TreeNode> {

private final E myElement;

// ...

E getElement() {
return myElement;
}

public int compareTo(TreeNode node) {
return this.getElement().compareTo(node.getElement());
}
}
}

Then javac complains I haven't got a compareTo method for a <? super E>
type..but how would I define one? The error is below:

analyser/TreeNode.java:11: analyser.TreeNode is not abstract and
does not override abstract method compareTo(analyser.TreeNode<? super
E>) in java.lang.Comparable

If I change the definition of compareTo to:

public int compareTo (TreeNode<? super E> otherNode)

Then I get the following error:

analyser/TreeNode.java:25: compareTo(? super E) in
java.lang.Comparable<? super E> cannot be applied to
java.lang.Comparable<capture of ? super E>)
return data.compareTo (otherNode.getData());

If you must make TreeNode a top-level class, and if it must implement
Comparable (not a given), then you need to declare it so:

public class TreeNode<E extends Comparable<? super E>> implements
Comparable<TreeNode<E extends Comparable<? super E>>>

Pretty ugly, huh? Since TreeNodes ought to be the exclusive province of
the tree to which they belong, making the class an inner class of
BinaryTree is a pretty reasonable thing to do. And it improves the
declaration syntax tremendously.

 

[Steven Davies]

John C. Bollinger wrote:

<lots of interesting stuff>

Re: implementing the TreeNode as an inner class, I was going to do it..
I just didn't think it'd be *that* much harder to write it as a spearate
class.

Thanks for all your help,

 

[John C. Bollinger]

If you must make TreeNode a top-level class, and if it must implement
Comparable (not a given), then you need to declare it so:

public class TreeNode<E extends Comparable<? super E>> implements
Comparable<TreeNode<E extends Comparable<? super E>>>

Pretty ugly, huh? Since TreeNodes ought to be the exclusive province of
the tree to which they belong, making the class an inner class of
BinaryTree is a pretty reasonable thing to do. And it improves the
declaration syntax tremendously.

On reflection, that's worse than it needs to be. This is much nicer,
makes sense, and in fact seems to work:

public class TreeNode<E extends Comparable<? super E>>
implements Comparable<TreeNode<E>> {

private final E myElement;

// ...

public E getElement() {
return myElement;
}

public int compareTo(TreeNode<E> node) {
return this.getElement().compareTo(node.getElement());
}
}

The bounds on E need only be specified once, where E is declared;
thereafter E can be used without explicitly giving its bounds.