Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Using Java 5.0 generics

Reply
Thread Tools

Using Java 5.0 generics

 
 
Steven Davies
Guest
Posts: n/a
 
      03-13-2005
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
--
Steven Davies
 
Reply With Quote
 
 
 
 
Oscar kind
Guest
Posts: n/a
 
      03-13-2005
Steven Davies <(E-Mail Removed)> wrote:
> 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.


--
Oscar Kind http://home.hccnet.nl/okind/
Software Developer for contact information, see website

PGP Key fingerprint: 91F3 6C72 F465 5E98 C246 61D9 2C32 8E24 097B B4E2
 
Reply With Quote
 
 
 
 
Chris Smith
Guest
Posts: n/a
 
      03-13-2005
Steven Davies <(E-Mail Removed)> wrote:
> 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
 
Reply With Quote
 
Steven Davies
Guest
Posts: n/a
 
      03-13-2005
Chris Smith wrote:
> Steven Davies <(E-Mail Removed)> wrote:
>
>>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?


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
--
Steven Davies
 
Reply With Quote
 
John C. Bollinger
Guest
Posts: n/a
 
      03-14-2005
Steven Davies wrote:
> 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.

--
John Bollinger
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
Steven Davies
Guest
Posts: n/a
 
      03-14-2005
John C. Bollinger wrote:
> Steven Davies wrote:
>
>> 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.


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.
--
Steven Davies
 
Reply With Quote
 
John C. Bollinger
Guest
Posts: n/a
 
      03-14-2005
Steven Davies wrote:

> John C. Bollinger wrote:
>
>> Steven Davies wrote:
>>
>>> 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.

>
>
> 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
Comparable as "Comparable<? super E>" to avoid a type safety warning.

> 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
inherits Comparable<T> from a superclass T; the non-wildcard version
will not permit that.

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


Duly ignored.

--
John Bollinger
(E-Mail Removed)
 
Reply With Quote
 
Steven Davies
Guest
Posts: n/a
 
      03-15-2005
John C. Bollinger wrote:
> Steven Davies wrote:
>
>> John C. Bollinger wrote:
>>
>>> Steven Davies wrote:
>>>
>>>> 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.

>>
>>
>>
>> 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
> Comparable as "Comparable<? super E>" to avoid a type safety warning.
>
>> 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
> 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
--
Steven Davies
 
Reply With Quote
 
John C. Bollinger
Guest
Posts: n/a
 
      03-15-2005
Steven Davies wrote:

> John C. Bollinger wrote:
>
>> Steven Davies wrote:
>>
>>> John C. Bollinger wrote:
>>>
>>>> Steven Davies wrote:
>>>>
>>>>> 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.
>>>
>>>
>>>
>>>
>>> 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
>> Comparable as "Comparable<? super E>" to avoid a type safety warning.
>>
>>> 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 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?


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
implement Comparable<IntegerElement>, rather it implements
Comparable<AbstractElement>.

>
> 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.

--
John Bollinger
(E-Mail Removed)
 
Reply With Quote
 
Steven Davies
Guest
Posts: n/a
 
      03-15-2005
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,
--
Steven Davies
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
generics depending on generics Soul VHDL 0 02-02-2009 09:14 AM
Generics in Java 1.5 ( or is it java 5.0 ?... I always haveconfusion) Vikram Java 4 06-13-2008 11:40 AM
Any tool to convert java raw code (a la java 1.4) into generics code Royan Java 8 02-15-2008 02:35 PM
Can't convert a generics list of objects into a generics list ofinterfaces Juergen Berchtel Java 1 05-20-2005 02:07 PM
Java Generics: limitations? Hung Jung Lu Java 4 11-24-2003 05:13 PM



Advertisments