Using Java 5.0 generics

Discussion in 'Java' started by Steven Davies, Mar 13, 2005.

  1. 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
     
    Steven Davies, Mar 13, 2005
    #1
    1. Advertising

  2. Steven Davies

    Oscar kind Guest

    Steven Davies <> 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
     
    Oscar kind, Mar 13, 2005
    #2
    1. Advertising

  3. Steven Davies

    Chris Smith Guest

    Steven Davies <> 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
     
    Chris Smith, Mar 13, 2005
    #3
  4. Chris Smith wrote:
    > Steven Davies <> 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
     
    Steven Davies, Mar 13, 2005
    #4
  5. 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
     
    John C. Bollinger, Mar 14, 2005
    #5
  6. 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
     
    Steven Davies, Mar 14, 2005
    #6
  7. 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
     
    John C. Bollinger, Mar 14, 2005
    #7
  8. 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
     
    Steven Davies, Mar 15, 2005
    #8
  9. 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
     
    John C. Bollinger, Mar 15, 2005
    #9
  10. 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
     
    Steven Davies, Mar 15, 2005
    #10
  11. I wrote:
    > 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.

    --
    John Bollinger
     
    John C. Bollinger, Mar 15, 2005
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hung Jung Lu

    Java Generics: limitations?

    Hung Jung Lu, Nov 21, 2003, in forum: Java
    Replies:
    4
    Views:
    567
    Tor Iver Wilhelmsen
    Nov 24, 2003
  2. Juergen Berchtel
    Replies:
    1
    Views:
    6,099
    John C. Bollinger
    May 20, 2005
  3. Royan
    Replies:
    8
    Views:
    774
    Patricia Shanahan
    Feb 15, 2008
  4. Vikram
    Replies:
    4
    Views:
    546
    Vikram
    Jun 13, 2008
  5. Soul
    Replies:
    0
    Views:
    551
Loading...

Share This Page