How to handle self reference and inheritance in Java

Question

I would like the field "children" to contain a list of objects with the containing object's type. However, when inherited, I get errors because of downcasting. What strategies can I use to keep the hierarchy, yet be able to access the child objects appropriately?

public class Node<T>{

    protected T value;
    protected Node<T> parent;
    private ArrayList<Node<T>> children;

    public Node(T value){
        this.value = value;
        this.children = new ArrayList<Node<T>>();
    }

    public ArrayList<Node<T>> getChildren(){
        return this.children;
    }

    //...other methods...//

}

When I try to call getChildren() in this class, I get a "type mismatch" error because it's trying to downcast.

public class DecidableTree<T extends Decidable<T>> extends Node<T>{

    public DecidableTree(T value) {
        super(value);
    }

    public randomInvolvedFunction(){
        //...other code...//
        for(DecidableTree<T> child : this.getChildren()){
            child.decidableTreeSpecificMethod();
        }
        //...other code...//
    }

    //...other methods...//

}

Unfortunately I can't just override the getChildren() function because the return types have to match.

Answer 1

The Problem

The problem you are having is that you are indeed downcasting, you are attempting to treat any given instance of Node as a DecidableTree. While it is true that you can of course treat any instance of DecidableTree as a Node because it inherits from Node, this does not work the other way around.

The Solution

The Bad Way

You could of course directly check that the instance is the correct type using the instanceOf operator, but there is a cleaner way to do this.

The Clean way

You could do this by parametrizing the Node class by two generic values. One V is for the value held at the given Node, and the other T is represents the actual concrete instance of the Node.

For instance,

public abstract class Node<T, V> {
    protected V value;
    protected Node<T,V> parent;
    private List<T> children;

    public Node(V value){
        this.value = value;
        this.children = new ArrayList<T>();
    }

    public List<T> getChildren(){
        return this.children;
    }

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

    public V getVal(){
        return this.value;
    }
}

Breaking this Apart

By parametrizing Node by the extra type variable, T, this allows us to return values that of the given concrete type in the parent class, without actually knowing what that concrete type will be. If this is still confusing, considering our new instance of DecidableTree may help you understand what is going on,

public class DecidableTree<V> extends Node<DecidableTree<V>, V> {

    public DecidableTree(V value) {
        super(value);
    }

    public void randomInvolvedFunction(){
        for(DecidableTree<V> child : this.getChildren()){
            System.out.println(child.getVal());
        }
    }
}

DecidableTree is still generic with respect to the actual value type, but it is not generic with respect to T. It says that a T is an instance of itself. This allows us to get the values out of the parent without downcasting.

This will compile and work just fine, and now you can describe all your types directly in terms of the generics. Note I added some methods so that you can do some meaningful testing.

One Final Note

In your example, I also change Node to be abstract and ArrayList to be List everywhere besides the line on which it is instantiated. I assume that you will never be creating instances of Node directly, so it should be abstract. As far as the ArrayList, it is best practice to refer to you data structure by the interface, in this case List, rather than by the actual implementation (unless there is some very specific reason not to). This allows you to change you data structures very easily in the future, by only changing one line of code.