How to use Java generic type parameter in polymorphic tree

Question

I have a large data structure that looks like a tree. I have a root class TreeElement that implements all the tree behaviors, linking, unlinking, navigating, etc. Actual nodes within the tree will be specialized subclasses of the TreeElement class. A given parent node, will have more than one type of child. Here is a sample tree:

NodeTypeA
+ NodeTypeB
  + NodeTypeC
  + NodeTypeC
+ NodeTypeB
  + NodeTypeC
+ NodeTypeD
  + NodeTypeE

As you can see, NodeTypeA has children of types B and D (and possibly others), while NodeTypeB has children of C (and possibly others). NodeTypeD has children of type E (and possibly others). All of these are subclasses of TreeElement. The specialized subclasses have some knowledge of the kinds of children that they are allowed to have.

The base type TreeElement has a method

Vector getChildren(String kind, Class nodeType);

This returns a vector filled with all the children marked with the value of kind, and of class specified with the class passed in. The vector returned will always contain elements of the class passed in. The problem is that I am trying to implement the right kind of type safety, and it is not clear to me how to use the dynamic typing capabilities of java for this.

In the class NodeTypeA, I would like a method like this that gets children of NodeTypeB:

Vector<NodeTypeB> getSpecialChildren() {
    Vector<NodeTypeB> vb = getChildren("special", NodeTypeB.class);
    return vb;
}

When I write the above, I get a warning in Eclipse that a type cast is needed. So I can add a type cast:

Vector<NodeTypeB> getSpecialChildren() {
    Vector<NodeTypeB> vb = (Vector<NodeTypeB>) getChildren("special", NodeTypeB.class);
    return vb;
}

But, I also have the feature of Eclipse to "remove unnecessary casts" and this feature removes this cast. That seems kind of strange that Eclipse considers it unnecessary, but warns if it is not there. But that is just an annoyance.

What I really want to do is to use the dynamic type mechanism (is this the 'bounded type parameters'???) of Java to make this work right. I simply can't figure out how to declare the getChildren method in the TreeElement class to accomplish this mechanism with full type safety -- and I assume eliminating the class parameter. Any help would be appreciated.

Answer 1

The way to fix the declaration of getChildren is:

public <T extends TreeElement> Vector<T> getChildren(String string, Class<T> nodeType)

That will get the compiler to leave you alone with the type warnings when you use.

The implementation of that method will still have some warnings in it, since generics are a compile-time feature and you're supplying a run-time type argument, but the warnings will at least be isolated inside that method.

Answer 2

You should consider doing an implementation of either Nested Set Trees or Adjacency Trees. I did some classes for Nested Set Trees that used generics that are very useful, and easily repurposed.

The core of it is going to look something like:

public class NestedSetTree<? extends NestedSetTree<T>> 

Then the nodes are just T. You can implement all the basics like getParent(), getAncestorOfType(NodeType type), etc.