Saturday, February 17, 2007

A TreeList implementation

Following up on my previous post for a tree list collection in Java, here is an implementation in two parts.

First is an abstract base for tree lists along the lines of AbstractSequentialList, but with an important difference.

For the standard Collection classes, the elements of the collection are the only objects under consideration, and all elements are explicitly manipulated by calls to the collection: addition, ordering and removal. In contrast, TreeList considers both the elements themselves—the values—and the nodes which refer to those elements.

Because of this dual life, Treelist must manipulate nodes implicitly to shadow elements manipulated explicitly. And to preserve proper typing, TreeList must have a way to create nodes beyond what is possible presently with straight-forward generics.

Why? To permit subclassing of TreeList classes. Unfortunately, that effort is the cause of the several TODO markers in the sample code. Soon, I think, I will revisit this point with Gafter's Gadget.

(Yes, the repeated reference around the same material is intentional. Gafter was rather inspired for his idea, and it points to a near certain improvement in the language for Java 7.)

Problems aside, this code illustrates the good design of the Java Collections and relies heavily on the extension points provided for collection implementors.

Without further ado:

/**
* {@code LinkedTreeList} is a linked node implementation of {@code TreeList}
* using an array list of children.  It does not support mixing nodes between it
* and other implementations of {@code TreeList}.
* <p/>
* It a <em>sequential list</em>, not a random-access one.  Although it supports
* all list operations, {@code LinkedTreeList} performs similarly to {@link
* LinkedList} rather than {@link ArrayList}.  For example, {@link #size()} is
* an <em>O(N)</em> operation rather than <em>O(1)</em>.  In constrast,
* insertion and deletion are very efficient.
*
* @author <a href="mailto:binkley@alumni.rice.edu">B. K. Oxley (binkley)</a>
* @todo How to make extension type-safe w/o hosing generics syntax?
*/
public abstract class AbstractTreeList<E, C extends AbstractTreeList<E, C>>
       extends AbstractSequentialList<E>
       implements com.jpmorgan.eggplant.util.TreeList<E> {
   private final List<C> children = new ArrayList<C>();

   private C parent;
   private E value;

   protected AbstractTreeList(final E rootValue) {
       this(null, rootValue);
   }

   protected AbstractTreeList(final C parent, final E value) {
       setParent(parent);
       setValue(value);
   }

   protected AbstractTreeList(final C parent, final int index, final E value) {
       setParent(parent, index);
       setValue(value);
   }

   /**
    * @todo Smell.
    */
   protected abstract C newInstance(final C parent, final E value);

   /**
    * @todo Smell.
    */
   protected abstract C newInstance(final C parent, final int index,
           final E value);

   // TreeList

   public boolean isRoot() {
       return null == parent;
   }

   public C getParent() {
       if (isRoot())
           throw new NoSuchElementException();

       return parent;
   }

   public boolean isLeaf() {
       return children.isEmpty();
   }

   public List<TreeList<E>> children() {
       // TODO: How to avoid wonky cast?
       return (List) new Children();
   }

   public TreeList<E> addChild(final E value) {
       return newInstance(self(), value);
   }

   public TreeList<E> addChild(final int index, final E value) {
       return newInstance(self(), index, value);
   }

   /**
    * @todo Merge with {@link Children#remove}.
    */
   public void removeChild(final TreeList<E> child) {
       if (!(child instanceof AbstractTreeList))
           throw new NoSuchElementException();

       ((C) child).setParent(null);
   }

   public TreeList<E> removeChild(final int index) {
       return children().remove(index);
   }

   public boolean removeAllChildren(final Collection<TreeList<E>> c) {
       return children().removeAll(c);
   }

   public boolean retainAllChildren(final Collection<TreeList<E>> c) {
       return children().retainAll(c);
   }

   public E getValue() {
       return value;
   }

   public void setValue(final E value) {
       this.value = value;
   }

   // AbstractSequentialList

   @Override
   public ListIterator<E> listIterator(final int index) {
       if (0 > index)
           throw new IndexOutOfBoundsException();

       final RootValueListIterator lit = new RootValueListIterator();

       for (int i = 0; i < index; ++i)
           if (lit.hasNext())
               lit.next();
           else
               throw new IndexOutOfBoundsException();

       return lit;
   }

   // AbstractCollection

   @Override
   public int size() {
       final ListIterator<E> lit = listIterator();

       while (lit.hasNext())
           lit.next();

       return lit.nextIndex();
   }

   private C self() {
       return (C) this;
   }

   private void adopt(final C parent, final Adopter<C> adopter) {
       if (this.parent == parent)
           return;

       if (this == parent)
           throw new IllegalArgumentException();

       if (null != this.parent)
           siblings().remove(this);

       if (null != (this.parent = parent))
           adopter.adopt(self());
   }

   private List<C> siblings() {
       return parent.children;
   }

   private void setParent(final C parent) {
       adopt(parent, new Adopter<C>() {
           public void adopt(final C child) {
               siblings().add(self());
           }
       });
   }

   private void setParent(final C parent, final int index) {
       adopt(parent, new Adopter<C>() {
           public void adopt(final C child) {
               siblings().add(index, self());
           }
       });
   }

   private interface Adopter<C> {
       void adopt(final C child);
   }

   private class RootValueListIterator
           implements ListIterator<E> {
       private final List<ListIterator<C>> previousNodeIts
               = new ArrayList<ListIterator<C>>();
       private ListIterator<C> currentNodeIt = (ListIterator<C>) singletonList(
               AbstractTreeList.this).listIterator();
       private ListIterator<C> nextNodeIt = (ListIterator<C>) children()
               .listIterator();
       private C currentNode = (C) AbstractTreeList.this;

       private int index;

       public boolean hasNext() {
           return currentNodeIt.hasNext() || nextNodeIt.hasNext();
       }

       public E next() {
           ++index;

           if (currentNodeIt.hasNext())
               return (currentNode = currentNodeIt.next()).getValue();

           if (!nextNodeIt.hasNext())
               throw new NoSuchElementException();

           previousNodeIts.add(currentNodeIt);
           currentNodeIt = nextNodeIt;

           if (!currentNodeIt.hasNext())
               throw new NoSuchElementException();

           currentNode = currentNodeIt.next();
           nextNodeIt = (ListIterator<C>) currentNode.children().listIterator();

           return currentNode.getValue();
       }

       public boolean hasPrevious() {
           return currentNodeIt.hasPrevious()
                   || !previousNodeIts.isEmpty() && previousNodeIts
                   .get(previousNodeIts.size() - 1).hasPrevious();
       }

       public E previous() {
           --index;

           if (currentNodeIt.hasPrevious())
               return (currentNode = currentNodeIt.previous()).getValue();

           if (previousNodeIts.isEmpty())
               throw new NoSuchElementException();

           nextNodeIt = currentNodeIt;
           currentNodeIt = previousNodeIts.remove(previousNodeIts.size() - 1);

           if (!currentNodeIt.hasPrevious())
               throw new NoSuchElementException();

           return (currentNode = currentNodeIt.previous()).getValue();
       }

       public int nextIndex() {
           return index;
       }

       public int previousIndex() {
           return index - 1;
       }

       public void remove() {
           final C remove = currentNode;

           // TODO: Testing, thinking, testing!
           if (hasPrevious()) {
               previous();
               remove.setParent(null);
               if (hasNext())
                   next();
           } else if (hasNext()) {
               next();
               remove.setParent(null);
               if (hasPrevious())
                   previous();
           } else {
               throw new UnsupportedOperationException(
                       "Cannot remove only node.");
           }

           // For fail-fast iterators - see {@link #modCount}.
           ++modCount;
       }

       public void set(final E o) {
           currentNode.setValue(o);
       }

       public void add(final E o) {
           currentNode.addChild(0, o);

           // For fail-fast iterators - see {@link #modCount}.
           ++modCount;
       }
   }

   private class Children
           extends AbstractList<C> {
       @Override
       public C get(final int index) {
           return children.get(index);
       }

       @Override
       public int size() {
           return children.size();
       }

       @Override
       public void add(final int index, final C element) {
           if (null == element)
               throw new NullPointerException();
           if (children.contains(element))
               throw new IllegalArgumentException();

           element.setParent(self(), index);
       }

       @Override
       public C set(final int index, final C element) {
           if (null == element)
               throw new NullPointerException();
           if (children.contains(element))
               throw new IllegalArgumentException();

           final C oldChild = get(index);

           oldChild.setParent(null);
           element.setParent(self(), index);

           return oldChild;
       }

       @Override
       public C remove(final int index) {
           final C child = get(index);

           child.setParent(null);

           return child;
       }
   }
}

Finally is a concrete class putting it all together:

/**
* {@code LinkedTreeList} is a linked node implementation of {@code TreeList}
* using an array list of children.  It does not support mixing nodes between it
* and other implementations of {@code TreeList}.
* <p/>
* It a <em>sequential list</em>, not a random-access one.  Although it supports
* all list operations, {@code LinkedTreeList} performs similarly to {@link
* LinkedList} rather than {@link ArrayList}.  For example, {@link #size()} is
* an <em>O(N)</em> operation rather than <em>O(1)</em>.  In constrast,
* insertion and deletion are very efficient.
*
* @author <a href="mailto:binkley@alumni.rice.edu">B. K. Oxley (binkley)</a>
* @todo How to make extension type-safe w/o hosing generics syntax?
*/
public class LinkedTreeList<E>
       extends AbstractTreeList<E, LinkedTreeList<E>> {
   public LinkedTreeList(final E rootValue) {
       super(rootValue);
   }

   protected LinkedTreeList(final LinkedTreeList<E> parent, final E value) {
       super(parent, value);
   }

   protected LinkedTreeList(final LinkedTreeList<E> parent, final int index,
           final E value) {
       super(parent, index, value);
   }

   @Override
   protected LinkedTreeList<E> newInstance(final LinkedTreeList<E> self,
           final E value) {
       return new LinkedTreeList<E>(self, value);
   }

   @Override
   protected LinkedTreeList<E> newInstance(final LinkedTreeList<E> self,
           final int index, final E value) {
       return new LinkedTreeList<E>(self, index, value);
   }
}

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.

Thursday, February 01, 2007

Outstanding post on closures

Neal Gafter, a co-author of the closure proposal, has just posted an outstanding entry on closures.

In it he describes not just what is happening for Java, but the history of closures, touching on LISP, Scheme and Smalltalk. A tour de force of a technical blog post.