2
\$\begingroup\$

My implementation of generic Tree structure:

/**
 * Tree data structure
 */
public class Tree<T> {

    private T value;

    private Tree<T> parent;

    protected List<Tree<T>> children = Collections.emptyList();

    public Tree(T value) {
        this.value = value;
    }

    public Tree() {
    }

    /**
     * @return the value
     */
    public T getValue() {
        return value;
    }

    /**
     * @param value
     *            the value to set
     */
    public void setValue(T value) {
        this.value = value;
    }

    /**
     * Adds children
     * 
     * @param children
     * @return this
     */
    public final Tree<T> addChildren(List<Tree<T>> newChildren) {

        if (children == Collections.EMPTY_LIST) {
            children = new ArrayList<>();
        }

        for (Tree<T> child : newChildren) {
            if (children.add(child)) {
                child.setParent(this);
            }
        }
        return this;
    }

    /**
     * Adds children
     * 
     * @param children
     * @return this
     */
    @SafeVarargs
    public final Tree<T> addChildren(Tree<T>... children) {
        return addChildren(Arrays.asList(children));
    }

    /**
     * Removes children
     * 
     * @param children
     * @return this
     */
    public final Tree<T> removeChildren(List<Tree<T>> children) {
        for (Tree<T> child : children) {
            if (this.children.remove(child)) {
                child.setParent(null);
            }
        }
        return this;
    }

    /**
     * Removes children
     * 
     * @param children
     * @return this
     */
    @SafeVarargs
    public final Tree<T> removeChildren(Tree<T>... children) {
        return removeChildren(Arrays.asList(children));
    }

    /**
     * @return the parent
     */
    public Tree<T> getParent() {
        return parent;
    }

    /**
     * @param parent
     *            the parent to set
     */
    public void setParent(Tree<T> parent) {
        this.parent = parent;
    }

    /**
     * @return the tree root
     */
    public Tree<T> getRoot() {
        return parent == null ? this : parent.getRoot();
    }

    /**
     * @return children
     */
    public final List<Tree<T>> getChildren() {
        return children;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        buildString(sb, "", true);
        return sb.toString();
    }

    private void buildString(StringBuilder sb, String prefix, boolean isTail) {
        sb.append(prefix).append(isTail ? "└── " : "├── ").append(getValue()).append(System.lineSeparator());
        prefix += (isTail ? "    " : "│   ");

        for (int i = 0; i < children.size(); i++) {
            children.get(i).buildString(sb, prefix, (i == children.size() - 1));
        }
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (!(obj instanceof Tree<?>))
            return false;

        Tree<?> other = (Tree<?>) obj;

        if (this.children.size() != other.children.size())
            return false;

        for (int i = 0; i < this.children.size(); i++) {
            if (!(children.get(i).equals(other.children.get(i))))
                return false;
        }

        return true;
    }

}

Any suggestions to make this better?

\$\endgroup\$
3
\$\begingroup\$
  1. Your use of generics may be limiting. You may want to consider using the extends/super keywords to allow subtypes in the tree.
  2. The Tree class should be final.
  3. Perhaps TreeNode is a better name? Conceptually, it's a node, not a tree.
  4. The children instance variable should be private. There's also no reason to use Collections.emptyList(). Just assign it to be a new ArrayList. You should really consider using a LinkedList, because you're not really doing random access on the list.
  5. addChildren(List) should be addChildren(Collection). Sets need love, too. Whether the order is important or not should be left up to the client.
  6. Your documentation for addChildren() and removeChildren() should make it clear that they modify the incoming children as a side effect.
  7. It's not at all clear to me that it's desirable to return this from addChildren() and removeChildren(), but you certainly know more than I do about client needs.
  8. setParent() needs to be private, or a client is going to change it manually and break your internals. Specifically, the node that used to be the parent will still have a reference to the node that just got its parent changed - you'll have two different one-way relationships, such that X's parent does not have X as its child.
  9. getChildren() needs to return a (preferably immutable) copy of the children list, not the list itself. Otherwise a client can call removeAll() on the response and your internals are broken.
  10. If you override equals(), you should also override hashCode(), or you may see strange behaviours, especially with collections. Are you sure you really need equals()?
  11. The tree is thread-hostile. That is probably okay, given that this is most likely not production code, but it's something to be aware of.
\$\endgroup\$
5
  • \$\begingroup\$ The Tree class should not be final. The final specifier on classes and methods have very limited use and should be avoided unless there is a real need to stop some one from inheriting as it would break your program. One can well imagine basing a BalancedBinaryTree or a RedBlackTree of this generic tree implementation. Much the same way as HashMap and TreeMap are both Maps. -1 \$\endgroup\$ – Emily L. Jan 15 '15 at 18:01
  • 1
    \$\begingroup\$ Map is an interface. Tree is a concrete class. You are comparing apples and oranges. Designing for Extension is a well-known software development paradigm that prevents a difficult-to-diagnose set of bugs. It also helps keep the iterative design of large applications on the right path. Allowing concrete inheritance is much more likely to "break your program" than forbidding it. Look up the Liskov Substitution Principle and Design for Extension for examples. \$\endgroup\$ – Eric Stein Jan 15 '15 at 18:09
  • \$\begingroup\$ I was not comparing anything, I made an analogy. There is no violation of the LSP by not using final. Violation of LSP occurs only after someone makes a subclass that does not adhere to the super class's interface contract. There is at least one protected member which implies that inheritance is planned for. \$\endgroup\$ – Emily L. Jan 15 '15 at 18:31
  • \$\begingroup\$ @EmilyL. If you look at that implementation and think that inheritance is planned for, I don't think there's any further room for discussion. \$\endgroup\$ – Eric Stein Jan 15 '15 at 18:32
  • \$\begingroup\$ It is feasible that they may have planned to inherit from the class at some point. Whether or not that is a good idea I will not comment on. But it is very possible they may wish to do so and do it without violating the LSP. I believe you are being too sure of your self and narrow minded here, I do believe that OP knows the difference between protected and private as both are being used. That said it may also have been an oversight. \$\endgroup\$ – Emily L. Jan 15 '15 at 19:02
1
\$\begingroup\$

You need to decide if you want to document your methods or not. What you have provides no benefit and has some errors. Most of the time there is not method description, when there is one it just repeats the method name. The documentation for addChildren() says the variable name is different from the actual name. Simply using this for the return seems lazy.

For the case of a getter and a setter, documentation is not required. However, it should only be omitted when it is completely clear what the value being operated on. In this case value is straight forward, but the time it would take to write "value associated with this node" is negligible and more explicit.

Good documentation makes code so much easier to work with. Even when it is code you wrote yourself, one sentence describing a method you wrote a month ago can get you back up to speed faster. If you are intending for your code to be used as a library, documentation is even more important. You might think all of the names make sense, but that doesn't mean everyone will fully understand it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.