Generic tree, self bounded-generics

Question

I am to adding genericity to one of my projects. I love generics as this makes my code more robust, self-documented and erases all those ugly casts.

However, I came across a tough case and have some issues trying to express a "recursive" constraint for one of my structures.

This is basically some kind of "generic" tree, with double links (to children and parent). I have simplified the class at maximum to show the issue :

public class GenericTree<
    ParentClass extends GenericTree<?, ?>, 
    ChildClass extends GenericTree<?, ?>> 
{
    // Attributes
    private ArrayList<ChildClass> children = new ArrayList<ChildClass>();
    private ParentClass parent = null;

    // Methods 
    public void setParent(ParentClass parent) {
        this.parent = parent;
    }

    public void addChild(ChildClass child) {
        child.setParent(this);
        this.children.add(child);
    }
}

The problem is for the instruction : child.setParent(this).

Java gives the following error :

Bound mismatch: The method setParent(?) of type ChildClass is not applicable for the
arguments (GenericTree). The wildcard parameter ? has no lower bound, and may actually be more restrictive than argument GenericTree

What I would like is to be able to express something like :

public class GenericTree<
    ParentClass extends GenericTree<?, ?>, 
    ChildClass extends GenericTree<[THIS_VERY_CLASS], ?>> 

To say that the parent class of the child class should be itself ...

I have looked at some articles about the self bounding generics, but I don't know how to apply it in this case.

Any help would be appreciated.

Ostler

Why isn't the tree homogeneous with respect to node types? I see no reason for specifying child node type and parent node type separately. I do understand however if you make a distinction between leaves and inner nodes. – Crossgarnet

Also, if this cannot be achieved, I would like at least to be able to use a cast. For that I need to be able to refer to the third wildcard (?) class of my declaration. Is it possible ? – Ostler

Because that would be too simple. Here, we have trees that use Country -> Location -> Building -> Room and the only common attribute is "name". I have the feeling that this isn't possible with generics... – Clubhouse

To be able to cast, you must first cast to the non-generic type, like so: return (GenericTree<Type>)((GenericTree)obj); Needs SuppressWarning({"unsecure", "rawtypes"}) – Clubhouse

@Eyal: Yes the actual tree has heterogeneous node types. Something like : Aggregation of Wind Farms WindFarm Wind Turbines Cluster Wind Turbine So, for example, the declaration of the wind cluster class would look like : class WindCluster<WindFarm, WindTurbine> ... And no, leaves are not separated from inner nodes. – Ostler

Answer 1

The closest I could get is to follow Enum's pattern of self reference. It still requires an unchecked cast, but assuming your subclasses define T correctly, it should be safe.

public class GenericTree<T extends GenericTree<T, P, C>, P extends GenericTree<P, ?, T>, C extends GenericTree<C, T, ?>> {

    // Attributes
    private ArrayList<C> children = new ArrayList<C>();
    private P parent = null;

    // Methods
    public void setParent(P parent) {
        this.parent = parent;
    }

    public void addChild(C child) {
        @SuppressWarnings("unchecked")
        final T thisAsType = (T) this;
        child.setParent(thisAsType);
        this.children.add(child);
    }
}

Edit: Implementation example

public static class SingleTypeTree<T> extends
    GenericTree<SingleTypeTree<T>, SingleTypeTree<T>, SingleTypeTree<T>> {

}

Kutz

Would it be possible for you to provide a demonstration of a class implementing this; I know I must be missing something obvious, but it seems like an infinite regression to me when trying to define a root or leaf (i.e. a class which has no parent or child type). facepalm – Corinnacorinne

I don't think it is possible to use this solution: The Enum self referencing pattern is not compiler friendly. Take for example the code here mindprod.com/jgloss/enum.html showing decompiled from an enum and how it references the parent Enum type; this decompiled code will not recompile. – Corinnacorinne

I am not sure if your proposed implementation example above is the solution you spoke of; I would like to see a proposed solution which works for the WindCluster/WindFarm and WindTurbine example given in the Question. Specifically in the case where it is not a Tree of a single type. – Corinnacorinne

Answer 2

Don't use generics for inhomogeneous trees, use interfaces and casts.

While you can solve some of the problems with generics, the resulting code will be brittle, show you error messages like you've never seen before, fixing bugs will usually lead to try&error and even if you get it to compile, you won't know why ;-)

[EDIT2] Added addChild() and a usage example below.

[EDIT] Still with me? If you really must, use this API:

interface ParentNode<Child> {
    List<Child> getChildren();
    void addChild(Child child);
}
interface ChildNode<Parent> {
    void setParent(Parent parent);
    Parent getParent();
}
// There is no way to avoid this because we would need to define
// "Node" recursively.
@SuppressWarnings( "rawtypes" )
class Node<
    Parent extends ParentNode<? extends Node>,
    Child extends ChildNode<? extends Node>
>
implements
    ParentNode<Child>,
    ChildNode<Parent>
{
    private Parent parent;
    public Parent getParent() { return parent; }
    public void setParent(Parent parent) { 
        this.parent = parent;
        // Here, we must case the child to a type that will accept Node
        @SuppressWarnings( "unchecked" )
        ParentNode<Node> cast = (ParentNode)parent;
        cast.addChild(this); // Note: Either add the child here ...
    }

    private List<Child> children;
    public List<Child> getChildren() { return children; }
    public void addChild( Child child ) { 
        children.add(child);
        // Here, we must case the child to a type that will accept Node
        @SuppressWarnings( "unchecked" )
        ChildNode<Node> cast = (ChildNode)child;
        cast.setParent(this); // ... or here but not twice :-)
    }
}

i.e. split the two functions (look upwards and look downwards) into two interfaces and then create a node type which implements both. This allows you to define leaves and root nodes as special nodes (without one of the two APIs) or you can define them just like any other node and return null in the "unsupported" method.

Usage:

public class DirFileNode extends Node<DirFileNode, DirFileNode> {
}
public class TreeUsage {
    public static void main( String[] args ) {
        DirFileNode node = new DirFileNode();
        DirFileNode node2 = new DirFileNode();
        node.addChild( node2 );
        // Why yes, I do love infinite loops. How can you tell?
        node2.addChild( node );
    }
}

What you can see is that the API makes sure that everything is type safe but internally, you have to cast. And this is only simple as long as you don't use generic types in the nodes. If you do, the declarations which grow into a huge mess.

Clubhouse

I like what you did with the API, that's a nice example of interface segregation, but on another note - since Node is not abstract, wouldn't that mean that you wouldn't be able to use Node itself in the tree, since the ? extends Node limits instances to Node subclasses only? – Transcription

I'm not 100% sure about the limits but since heterogeneous trees will always use subtypes as nodes anyway, that shouldn't be an issue. If it is, just create an SimpleNode extends Node and you're good. – Clubhouse

Even if the author creates SimpleNode he/she still cannot call child.setParent(this); this.children.add(child); until type erasure is known. Does this mean that addChild would need to be provided at every SimpleNode implementation? – Corinnacorinne

@Syntax: No, see my edits. You must use unchecked casts in setParent()/add() but you can reuse them. – Clubhouse

Thanks. This still requires a cast, but it is ok. And the idea of splitting the Parent and Child interface is a good one. – Ostler