Home > Back-end >  Tree-Structure does not inherit generics
Tree-Structure does not inherit generics

Time:07-16

My goal is to create a tree-like object structure.

For this i created a class named Node (I removed the implementation because the problem still persists without it):

public class Node<S> {
    public Node<S> addChild(Node<S> node) {
        return this;
    }
}

Important to know is that i want to define the generic type S only in the root node, all child nodes should automatically inherit from the root node.

Something like this:

new Node<String>().addChild(
    new Node<>().addChild(
        new Node<>()
    )
)

I restricted the addChild method to only accept Nodes with the same generic type S, so as far as i know my child node should know that it's generic type S has to be (in this example) String. However it seems like the generic type S gets lost after instantiating a new Node, because it gives me the following Exception:

error: incompatible types: Node<Object> cannot be converted to Node<String>

CodePudding user response:

What you are trying to do is something like this

public class Node<T> {
    
    private Node<T> child;
    private T data = null;
    
    public Node (T data) {
        this.data = data;
    }
    
    public T getData() {
        return data;
    }
    
    public Node<T> getChild() {
        return child;
    }

    public void addChild(Node<T> child) {
        this.child = child;
    }
    
    @Override
    public String toString() {
        return "this node's data: "   data   "; has child? "   (child != null);
    }

    public static void main(String[] args) {
        Node<String> root = new Node<> ("parent");
        Node<String> child = new Node<>("child");
        root.addChild(child);
        System.out.println(root);
        System.out.println(child);
    }
}

If you were to execute this, it will output

this node's data: parent; has child? true
this node's data: child; has child? false
this node's data: 0; has child? false
this node's data: 1; has child? false

Notice how I can create nodes of type String and Integer. However, this class is incomplete if you want to create a tree structure. The implementation of "tree" will depend on what kind of tree you are talking about. For example, a simple binary tree will have two children at most. Other types of trees could have more children. Also, adding nodes to a tree might require balancing the tree.

Now, to your question, this answer suffices. I was able to demonstrate the use of generics to create Node objects of type T.

CodePudding user response:

The use of <> requires type inference, and the argument of the first addChild must be a Node, and just passing new Node<>() would do - infering from the return type. But chaining to .addChild(new Node<>()) cannot infer anything, can only provide Node<Object>. So: one cannot use <>.

The problem is (of course) that you want addChild to return the head of the list, and keep adding to the tail of the list.

Normal practice is not to create Node instances, but just use the S values.

public class Node<S> {
    private S value;
    private Node<S> next;

    public Node(S value) {
        this.value = value;
    }

    public static <T> void print(Node<T> root) {
        if (root == null) {
            System.out.println("empty");
            return;
        }
        System.out.print(root.value);
        System.out.print(" --> ");
        print(root.next);
    }

    public static <T> Node<T> addAll(T... values) {
        Node<T> root = null;
        Node<T> previous = null;
        for (T value : values) {
            Node<T> current = new Node<>(value);
            if (root == null) {
                root = current;
            } else {
                previous.next = current;
            }
            previous = current;
        }
        return root;
    }

    public static void main(String[] args) {
        Node<String> root = Node.addAll("a", "b", "c", "d");
        print(root);
    }
}

Comparable to Collections.addAll or List.of. If you keep a Node<S> last field, you could indeed create something like:

    public void addLast(S value) {
        last.next = new Node<>(value);
    }

This also shows a serious problem of the class: an empty list is not a Node. One could use Optional<Node<S>> or a special constant for an empty list EMPTY - without value.

The normal solution is to have a container:

public class List<S> {
    private class Node {
        ...
    }
    private Node<S> root;
    private Node<S> last;
    private int size;

    public List<S> addLast(S value) {
        Node<S> current = new Node<>(value);
        if (root == null) {
            root = current;
            last = current;
        } else {
            last.next = current;
        }
        last = current;
          size;
        return this;
    }

    private int size() {
        return size;
    }

    ...
}

Now everything fits.

List<String> nodes = new List<>()
    .addLast("a")
    .addLast("b")
    .addLast("c")
    .addLast("d");
  • Related