Extendable double-linked tree implementation in Java

Question

I want to extend an existing double-linked tree implementation by some extra data.

Therefor I could refactor the basic TreeNode implementation, but I want to have a separate extended TreeNode implementation, because in my real-world szenario building-up an ExtandedTreeNode will be much more expensive than building-up the basic TreeNode, and the extra data is only necessary for some use-cases.

Rudimental Code

Here my first rudimental approach for an extendable double-linked tree implementation in Java:

Basic tree node interface:

interface TreeNode
{
    // tree node getters:

    TreeNode getParent();

    List<? extends TreeNode> getChildren();

    // tree node setters:

    void setParent(TreeNode parentNode);

    void addChild(TreeNode childNode);

    // some basic operations:

    boolean isSelectable();

    // [...]
}

Extended tree node interface:

interface ExtandedTreeNode extends TreeNode
{
    // narrow types of tree node getters of super-interface:

    @Override
    ExtandedTreeNode getParent();

    @Override
    List<? extends ExtandedTreeNode> getChildren();

    // narrowing types of tree node setters of super-interface is not possible!

    // some additional operations:

    boolean isRemoveable();

    // [...]
}

Basic tree node implementation:

class TreeNodeImpl implements TreeNode
{
    private TreeNode parent;

    private List<TreeNode> children = new ArrayList<TreeNode>();

    private boolean isSelectable;

    //
    // implement tree node getters:
    //

    @Override
    public TreeNode getParent()
    {
        return parent;
    }

    @Override
    public List<? extends TreeNode> getChildren()
    {
        return children;
    }

    //
    // implement tree node setters:
    //

    @Override
    public void setParent(TreeNode parent)
    {
        this.parent = parent;
    }

    @Override
    public void addChild(TreeNode childNode)
    {
        children.add(childNode);
    }

    //
    // implement basic operations:
    //

    @Override
    public boolean isSelectable()
    {
        return isSelectable;
    }

    // [...]
}

Extended tree node implementation:

class ExtandedTreeNodeImpl implements ExtandedTreeNode
{
    private ExtandedTreeNode parent;

    private List<ExtandedTreeNode> children = new ArrayList<ExtandedTreeNode>();

    private TreeNode treeNode;

    private boolean isRemoveable;

    public ExtandedTreeNodeImpl()
    {
        treeNode = new TreeNodeImpl();
    }

    //
    // implement tree node getters:
    //

    @Override
    public ExtandedTreeNode getParent()
    {
        return parent;
    }

    @Override
    public List<? extends ExtandedTreeNode> getChildren()
    {
        return children;
    }

    //
    // implement tree node setters:
    //

    @Override
    public void setParent(TreeNode parent)
    {
        this.parent = (ExtandedTreeNode) parent; // <--- How to avoid this type cast!!
    }

    @Override
    public void addChild(TreeNode childNode)
    {
        children.add((ExtandedTreeNode) childNode); // <--- How to avoid this type cast!!
    }

    //
    // implement basic operations by delegating to composite TreeNode:
    //

    public boolean isSelectable()
    {
        return treeNode.isSelectable();
    }

    // [...]

    //
    // implement additional operations:
    //

    @Override
    public boolean isRemoveable()
    {
        return isRemoveable;
    }

    // [...]
}

Question

For me the type hierarchy looks great for the read-only and non-tree-node-specific methods, but it leaks for the setters setParent(..) and addChild(..). Particularly the risky typecast to ExtandedTreeNode is quite evil and I want to get rid of it.

I thought about extracting the setParent(..) and addChild(..) methods to another two separate Interfaces like TreeNodeWriteable and ExtandedTreeNodeWriteable, but maybe there are some better design solutions.

Does anyone know a design pattern or blue print which could solve my problem with the writeable tree-node-specific setters?

Answer 1

You can use generics. Define your tree node as the following:

interface TreeNode<N extends TreeNode> {

    N getParent();

    List<N> getChildren();

    void setParent(N parentNode);

    void addChild(N childNode);

}

Now your TreeNodeImpl will look like: class TreeNodeImpl implements TreeNode<TreeNode>

While ExtendedTreeNodeImpl will be defined like follows:

class ExtendedTreeNodeImpl implements ExtendedTreeNode<ExtendedTreeNode>

The parametrized methods into these classes will use specific types: TreeNode and ExtendedTreeNode, so no casting is needed.

Answer 2

You could use the self type pattern. The downside is that all your code gets littered with type arguments that (most of the time) you don't really need.

Example:

interface TreeNode<S extends Node<S>> { // S is the self type
    void setParent(S parent);
    void addChild(S child);
}
interface ExtendedTreeNode extends Node<ExtendedTreeNode> {}

Edit: Related blog post by Stephen Colebourne