Saturday, February 10, 2007

TreeList, a Java collection

One hole in the Java collection classes is no tree. I have seen in production code in a prior job in non-UI software developers choose to use Swing JTree as a replacement collection for a tree data structure.

Rather than take that tortured path, here is a straight-forward tree interface:

/**
* {@code TreeList} is a list with left-to-right, depth-first traversal over a
* tree.  There is no limitation to the number of child nodes for a given node.
* <p/>
* Ordinary {@code List} operations behave as if they were operation on a list
* of node values.  For example, given a any tree list node, say
* <var>node</var>, then {@code node.getValue()} and {@code node.get(0)} are the
* same object.
*
* @author <a href="mailto:binkley@alumni.rice.edu">B. K. Oxley (binkley)</a>
*/
public interface TreeList<E>
       extends List<E> {
   /**
    * Checks if this node is a root node, this is, has no parent.
    *
    * @return {@code true} if a root node
    */
   boolean isRoot();

   /**
    * Gets the parent of this node or throw {@code NoSuchElementException} if
    * this is a root node, hence, never {@code null}.
    *
    * @return the node parent, if any
    *
    * @throws NoSuchElementException if this is a root node
    * @see #isRoot()
    */
   TreeList<E> getParent();

   /**
    * Checks if this node is a leaf node, that is, has no children.
    *
    * @return {@code true} if a leaf node
    */
   boolean isLeaf();

   /**
    * Gets the list of child nodes or an empty list if none, hence, never
    * {@code null}.
    * <p/>
    * The list is read-write.  Changes to the list are reflected in the tree.
    *
    * @return the child nodes, if any, or the empty list
    */
   List<TreeList<E>> children();

   /**
    * Adds a child node to this node with the given <var>value</var> to the end
    * of the list of children.  The new node has this node as its parent.
    *
    * @param value the new child node value
    *
    * @return the child node
    */
   TreeList<E> addChild(final E value);

   /**
    * Adds a child node to this node with the given <var>value</var> to the
    * <var>index</var> position in the list of children.  The new node has this
    * node as its parent.
    *
    * @param index the new child position, 0-based
    * @param value the new child node value
    *
    * @return the child node
    *
    * @throws IndexOutOfBoundsException if <var>index</var> is negative or
    * larger than the count of children of this node
    */
   TreeList<E> addChild(final int index, final E value);

   /**
    * Removes the given <var>child</var> node from this node.
    *
    * @param child the child node to remove
    *
    * @throws NoSuchElementException if <var>child</var> is not a child of this
    * node
    */
   void removeChild(final TreeList<E> child);

   /**
    * Removes the child node at the given <var>index</var> position from this
    * node, and returns it.  Afterwards, the returned node is a <em>root
    * node</em>.
    *
    * @param index the child position, 0-based
    *
    * @return the removed node
    *
    * @throws IndexOutOfBoundsException if <var>index</var> is negative or
    * larger than the count of children of this node
    */
   TreeList<E> removeChild(final int index);

   /**
    * Removes the children nodes in the given collection, <var>c</var>.
    *
    * @param c the child nodes to remove
    *
    * @return {@code true} if the tree changed as a result of this call
    */
   boolean removeAllChildren(final Collection<TreeList<E>> c);

   /**
    * Removes all but the children nodes in the given collection,
    * <var>c</var>.
    *
    * @param c the child nodes to retain
    *
    * @return {@code true} if the tree changed as a result of this call
    */
   boolean retainAllChildren(final Collection<TreeList<E>> c);

   /**
    * Gets the value of this node.  Ordinary {@code List} operations behave as
    * if they were operation on a list of node values.
    *
    * @return the node value
    */
   E getValue();

   /**
    * Sets the value of this node to the given <var>value</var>.   Ordinary
    * {@code List} operations behave as if they were operation on a list of
    * node values.
    *
    * @param value the new value
    */
   void setValue(final E value);
}

An implementation to follow in a later post.

Post a Comment