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);
   }
}