Generic tree, self bounded-generics

Question

Hi,

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.

Regards, Raphael

Answer 1

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.

Answer 2

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

}