I am writing a collection of collection classes for different types of trees. I am doing this as a training exercise, and I also hope that this proves to be something useful. I really want to do it right, and so I read Effective Java , and I also looked at how Joshua Bloch implemented collection classes by looking at the source. I seem to have a fair idea of what is being done, but I still have something to figure out.
I have a Node<T> interface and an AbstractNode<T> class that implements the Node interface. Then I created a GenericNode<T> (a node that can hold from 0 to n children, and which is part of an n-ary tree) that extends AbstractNode<T> and implements Node<T> . This part was simple.
Then I created the Tree<T> interface and the AbstractTree<T> class, which implements the Tree<T> interface. After that, I started writing the GenericTree<T> class, which extends AbstractTree<T> and implements Tree<T> . Here I began to experience problems.
As for design, GenericTree<T> can consist only of nodes of type GenericTreeNode<T> . This includes the root. In my Tree<T> interface, I have:
public interface Tree<T> { void setRoot(Node<T> root); Node<T> getRoot(); List<Node<T>> postOrder(); ... rest omitted ... }
And, AbstractTree<T> implements this interface:
public abstract class AbstractTree<T> implements Tree<T> { protected Node<T> root; protected AbstractTree() { } protected AbstractTree(Node<T> root) { this.root = root; } public void setRoot(Node<T> root) { this.root = root; } public Node<T> getRoot() { return this.root; } ... rest omitted ... }
In GenericTree<T> I can have:
public GenericTree(Node<T> root) { super(root); }
But this means that you can create a common tree using any subtype of Node<T> . You can also set the root of the tree for any subtype of Node<T> . I want to be able to restrict the type of node to the type of tree that it can represent. To fix this, I can do this:
public GenericTree(GenericNode<T> root) { super(root); }
However, setRoot still accepts a parameter of type Node<T> . This means that the user can still create a tree with the wrong root type node. How to enforce this restriction? The only way I can think of is to either:
- Make
instanceof , which limits the check to runtime. I am not a big fan of this. - Remove
setRoot from the interface and the base class implements this method. This means that it is not part of the contract, and anyone who wants to create a new type of tree should remember to implement this method.
Is there a better way?
The second question I have is regarding the postOrder return postOrder , which is List<Node<T>> . This means that if the user works with the GenericTree<T> object and calls postOrder , he gets a list consisting of Node<T> objects. This means that when iterating through (using the foreach construct), they would cast explicitly to the GenericNode<T> if they wanted to use methods that are defined only in this class. I do not like to put this burden on the user. What are my options in this case? I can only think about removing the method from the interface, and subclass implement this method, making sure that it returns a list of the corresponding subtype Node<T> . However, this once again removes it from the contract, and anyone who wants to create a new type of tree should remember to implement this method. Is there a better way?