I have added the Ancestor iterator class.  The main outstanding task 
with Tree is to think through the full impact of changes to the tree, 
particularly deletions, on the iterators.  Should a removal descend the 
subtree recursively deleting, for example.

The current situation is that any change in the tree throws a 
ConcurrentModificationException on PreOrder, PostOrder and Ancestor, but 
the current state of the iterator is otherwise unchanged.  Under what 
circumstances, if any, might it be reasonable to pick up the iterator 
after a Comod exception?

The Preceding/FollowingSibling iterators only throw Comod exceptions on 
changes to the parents 'chldren' ArrayList - other changes in the Tree 
go unnoticed.

Off the top of my head, I think that XSL-style tree partitioning 
(Ancestors, Children, Preceding and Following) can be achieved with 
little extra effort on the basis of the existing iterators, if such is 
required.

Peter
-- 
Peter B. West  [EMAIL PROTECTED]  http://powerup.com.au/~pbwest
"Lord, to whom shall we go?"
//package org.apache.fop.datatypes;

import java.util.*;

// The Tree class is analogous to one of the Collection classes.  It
// provides a bag with a certain structure into which objects may be collected
// for manipulation.  This is the level of at which those operations and
// fields are defined which allow for manipulation of the tree as a whole.

/**
 * Tree.java
 *
 * The <tt>Tree</tt> class is analogous to one of the <tt>Collection</tt>
 * classes.  It provides a bag with a certain structure into which objects
 * may be collected for manipulation.
 *
 * The outer class, Tree, is the level at which are defined those fields
 * and methods which are provided for the manipulation of the tree as a
 * whole.  The tree is actually comprised of a collection of <tt>Node</tt>
 * elements.
 *
 *
 * The primary reasons for the existence of a separate <tt>Tree</tt>
 * class is to provide an object for tree-wide synchronization, and to
 * have a home for <tt>modCount</tt> for the provision of
 * <i>fast-fail</i> iterators.  For more details, see the
 * discussion of <tt>modCount</tt> in <tt>AbstractList</tt>.
 *
 * $Id: Tree.java,v 1.13 2001-07-22 16:38:42+10 pbw Exp pbw $
 * @author <a href="mailto:[EMAIL PROTECTED]";>Peter B. West</a>
 * @version
 */

public class Tree {

    /**
     * The number of times the tree has been <i>structurally modified</i>.
     * See the discussion of the <tt>modCount</tt> field in
     * <tt>AbstractList</tt>.
     */
    protected int modCount = 0;
    protected int nodeCount = 0;
    
    protected Node root;

    public Tree() {}

    public Tree(Node root) {
        this.root = root;
    }

    public int modified() {
        // In the Tree class, this function updates the modCount
        // N.B. This method is always called from within a synchronized
        // method.
        synchronized (this) {
            return ++modCount;
        }
    }

    public int getModCount() {
        synchronized (this) {
            return modCount;
        }
    }

    public boolean modCountEqualTo(int value) {
        synchronized (this) {
            return value == modCount;
        }
    }

    public int size() {
        return nodeCount;
    }

    public boolean isEmpty() {
        return nodeCount == 0;
    }


    public class TreeException extends Exception {
        public TreeException(String message) {
            super(message);
        }
            
    }

    /**
     * Member class <tt>Node</tt> of class <tt>Tree</tt> provides the
     * structure for a general-purpose tree.
     *
     * Node
     * +-------------------------+
     * |(Node) parent            |
     * +-------------------------+
     * |ArrayList                |
     * |+-----------------------+|
     * ||(Node) child 0         ||
     * |+-----------------------+|
     * |:                       :|
     * |+-----------------------+|
     * ||(Node) child n         ||
     * |+-----------------------+|
     * +-------------------------+
     * |(Object) payload ->      |
     * | contents of this node   |
     * +-------------------------+
     *
     * <tt>ArrayList</tt> is used for the list of children because the
     * synchronization is performed "manually" within the individual methods,
     * and beause the <i>fail-fast</i> characteristics of the ArrayList
     * iterator and listIterators is desired.
     *
     * See <tt>Tree</tt> for the tree-wide support methods and fields.
     */

    public class Node {

        private Node parent;
        private ArrayList children;     // ArrayList of Node
        protected Object payload;

        /**
         * No argument constructor.
         *
         * Assumes that this node is the root, and so will throw a
         * <tt>TreeException</tt> when the root node in the enclosing
         * <tt>Tree</tt> object is non-null.
         */

        public Node()
            throws TreeException {
            if (Tree.this.root != null) {
                throw new TreeException(
                        "No arg constructor invalid when root exists");
            }
            parent = null;
            Tree.this.root = this;
            children = new ArrayList();
            payload = null;
        }

        /**
         * Constructor with one parameter.
         * @param parent Node which is the parent of this Node.  if this is
         *               null, the generated Node is assumed to be the root
         *               node.  If the Tree root node is already set, throws
         *               a <tt>TreeException</tt>.
         */

        public Node(Node parent)
            throws TreeException {
            children = new ArrayList();
            payload = null;
            if (parent == null) {
                if (Tree.this.root != null) {
                    throw new TreeException("Null Node constructor "
                                            + "invalid when root exists");
                }
                this.parent = null;
                Tree.this.root = this;
            }
            else {
                // The parent must be a node in the current tree
                if (parent.getTree() != Tree.this) {
                    throw new TreeException("Parent not in same tree");
                }
                this.parent = parent;
                // connect me to my parent
                parent.addChild(this);
            }
        }

        /**
         * Two argument constructor.
         * @param parent  The parent <tt>Node</tt> of this Node.  If null,
         *                this must be the root node.
         * @param payload An object which is the actual payload of this node;
         *                the contents of the Node.
         */

        public Node(Node parent, Object payload)
            throws TreeException {
            this(parent);
            this.payload = payload;
        }

        public Node getRoot() {
            return Tree.this.root;
        }

        /**
         * Appends a child <tt>Node</tt> to this node.  Synchronized on the
         * containing <tt>Tree</tt> object.
         *
         * Calls the <tt>modified</tt> method of the containing Tree to
         * maintain the value of <tt>modCount</tt>.
         *
         * @param child  Node to be added.
         */

        public void addChild(Node child) {
            synchronized (Tree.this) {
                children.add((Object) child);
                Tree.this.modified();
            }
        }

        /**
         * Removes the child <tt>Node</tt> at the specified index in the
         * ArrayList.  Synchronized on the enclosing <tt>Tree</tt> object.
         *
         * Calls the <tt>modified</tt> method of the containing Tree to
         * maintain the value of <tt>modCount</tt>.
         *
         * @param index  The int index of the child to be removed.
         * @return the node removed.
         */

        public Node removeChildAtIndex(int index) {
            synchronized (Tree.this) {
                Node tmpNode = (Node) children.remove(index);
                Tree.this.modified();
                return tmpNode;
            }
        }

        /**
         * Removes the specified child <tt>Node</tt> from the children
         * ArrayList.  Synchronized on the enclosing <tt>Tree</tt> object.
         *
         * Implemented by calling <tt>removeChildAtIndex()</tt>.  Relies
         * on that method to call the <tt>modified</tt> method of the
         * containing Tree to maintain the value of <tt>modCount</tt>.
         *
         * @param child  The child node to be removed.
         * @return the node removed.
         */

        public Node removeChild(Node child)
            throws NoSuchElementException {
            synchronized (Tree.this) {
                int index = children.indexOf((Object) child);
                if (index == -1) {
                    throw new NoSuchElementException();
                }
                Node tmpNode = removeChildAtIndex(index);
                // Note - no call to Tree.this.modified() here -
                // done in removeChildAtindex()
                return tmpNode;
            }
        }

        public Tree getTree() {
            return Tree.this;
        }

        public Node getChild(int index) {
            return (Node) children.get(index);
        }

        public Object getPayload() {
            return payload;
        }

        public void setPayload(Object payload) {
            this.payload = payload;
        }


        /**
         * Class <tt>PreOrder</tt> is a member class of <tt>Node</tt>.
         *
         * It implements the <tt>Iterator</tt> interface, excluding the
         * optional <tt>remove</tt> method.  The iterator traverses its
         * containing <tt>Tree</tt> from its containing Node in
         * preorder order.
         *
         * The method is implemented recursively; a PreOrder object is
         * instantiated at every level of the tree to handle the children at
         * that level.
         *
         * The iterator is <i>fast-fail</i>.  If any modifications occur to
         * the tree as a whole during the lifetime of the iterator, a
         * subsequent call to next() will throw a
         * ConcurrentModificationException.  See the discussion of
         * fast-fail iterators in <tt>AbstractList</tt>.
         *
         * The <tt>modCount</tt> field used to maintain information about
         * structural modifcations is maintained for all nodes in the
         * containing Tree instance.
         */

        class PreOrder implements Iterator {
            private boolean selfNotReturned = true;
            private int nextChildIndex = 0;     // N.B. this must be kept as
            // the index of the active child until that child is exhausted.
            // At the start of proceedings, it may already point past the
            // end of the (empty) child vector

            private int age;
            private PreOrder nextChildIterator;

            /**
             * Constructor
             *
             * @param age  the current value of the modCount field in the
             * <tt>Tree</tt> instance which includes this class instance.
             */
            public PreOrder(int age) {
                this.age = age;
                hasNext();  // A call to set up the initial iterators
                // so that a call to next() without a preceding call to
                // hasNext() will behave sanely
            }

            public boolean hasNext() {
                // synchronize this against possible changes to the tree
                synchronized (Tree.this) {
                    if (selfNotReturned) {
                        return true;
                    }
                    // self has been returned - are there any children?
                    // if so, we must always have an iterator available
                    // even unless it is exhausted.  Assume it is set up this 
                    // way by next().  The iterator has a chance to do this 
                    // because self will always be returned first.
                    // The test of nextChildIndex must always be made because
                    // there may be no children, or the last child may be
                    // exhausted, hence no possibility of an
                    // iterator on the children of any child.
                    if (nextChildIndex < children.size()) {
                        return nextChildIterator.hasNext(); 
                    }
                    else { // no kiddies
                        return false;
                    }
                }
            }

            public Object next()
                throws NoSuchElementException,
                       ConcurrentModificationException {
                synchronized (Tree.this) {
                    // synchronize the whole against changes to the tree

                    // Check for ConcurrentModification
                    if (! Tree.this.modCountEqualTo(age)) {
                        throw new ConcurrentModificationException();
                    }

                    if (! hasNext()) {
                        throw new NoSuchElementException();
                    }
                    if (selfNotReturned) {
                        selfNotReturned = false;
                        if (nextChildIndex < children.size()) {
                            // We have children - create an iterator
                            // for the first one
                            nextChildIterator =
                                    ((Node)
                                     (children.get(nextChildIndex))).new
                                    PreOrder(age);
                        }
                        // else do nothing;
                        // the nextChildIndex test in hasNext()
                        // will prevent us from getting into trouble
                        return Node.this;
                    }
                    else { // self has been returned
                        // there must be a next available, or we would not have
                        // come this far
                        if (! nextChildIterator.hasNext()) {
                            // last iterator was exhausted;
                            // if there was another child available, an
                            //iterator would already have been set up.
                            // Every iterator will return at least one node -
                            // the node on which it is defined.
                            // So why did the initial hasNext succeed?
                            throw new NoSuchElementException(
                                    "Cannot reach this");
                        }
                        Object tempNode = nextChildIterator.next();
                        // Check for exhaustion of the child
                        if (! nextChildIterator.hasNext()) {
                            // child iterator empty - another child?
                            if (++nextChildIndex < children.size()) {
                                nextChildIterator =
                                        ((Node)
                                         (children.get(nextChildIndex))).new
                                        PreOrder(age);
                            }
                            else {
                                // nullify the iterator
                                nextChildIterator = null;
                            }
                        }
                        return (Node) tempNode;
                    }
                }
            }

            public void remove()
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }
        }


        /**
         * Class <tt>PostOrder</tt> is a member class of <tt>Node</tt>.
         *
         * It implements the <tt>Iterator</tt> interface, excluding the
         * optional <tt>remove</tt> method.  The iterator traverses its
         * containing <tt>Tree</tt> from its containing Node in
         * postorder order.
         *
         * The method is implemented recursively; a PostOrder object is
         * instantiated at every level of the tree to handle the children at
         * that level.
         *
         * The iterator is <i>fast-fail</i>.  iI any modifications occur to
         * the tree as a whole during the lifetime of the iterator, a
         * subsequent call to next() will throw a
         * ConcurrentModificationException.  See the discussion of
         * fast-fail iterators in <tt>AbstractList</tt>.
         *
         * The <tt>modCount</tt> field used to maintain information about
         * structural modifcations is maintained for all nodes in the
         * containing Tree instance.
         */

        class PostOrder implements Iterator {
            private boolean selfReturned = false;
            private int nextChildIndex = 0;     // N.B. this must be kept as
            // the index of the active child until that child is exhausted.
            // At the start of proceedings, it may already point past the
            // end of the (empty) child vector

            private int age;
            private PostOrder nextChildIterator;

            /**
             * Constructor
             *
             * @param age  the current value of the modCount field in the
             * <tt>Tree</tt> instance which includes this class instance.
             */
            public PostOrder(int age) {
                this.age = age;
                hasNext();  // A call to set up the initial iterators
                // so that a call to next() without a preceding call to
                // hasNext() will behave sanely
            }

            public boolean hasNext() {
                // Synchronize this against changes in the tree
                synchronized (Tree.this) {
                    // self is always the last to go
                    if (selfReturned) { // nothing left
                        return false;
                    }
            
                    // Check first for children, and set up an iterator if so
                    if (nextChildIndex < children.size()) {
                        if (nextChildIterator == null) {
                            nextChildIterator =
                                    ((Node)
                                    (children.get(nextChildIndex))).new
                                    PostOrder(age);
                        }
                        // else an iterator exists.
                        // Assume that the next() method
                        // will keep the iterator current
                    } // end of Any children?
            
                    return true;
                }
            }

            public Object next()
                throws NoSuchElementException,
                       ConcurrentModificationException {
                synchronized (Tree.this) {
                    // synchronize the whole against changes to the tree

                    // Check for ConcurrentModification
                    if (! Tree.this.modCountEqualTo(age)) {
                        throw new ConcurrentModificationException();
                    }

                    if (! hasNext()) {
                        throw new NoSuchElementException();
                    }
                    // Are there any children?
                    if (nextChildIndex < children.size()) {
                        // There will be an active iterator.  Is it empty?
                        if (nextChildIterator.hasNext()) {
                            // children remain
                            Object tempNode = nextChildIterator.next();
                            // now check for exhaustion of the iterator
                            if (! nextChildIterator.hasNext()) {
                                if (++nextChildIndex < children.size()) {
                                    nextChildIterator =
                                            ((Node)
                                            (children.get(nextChildIndex))).new
                                            PostOrder(age);
                                }
                                // else leave the iterator bumping on empty
                                // next call will return self
                            }
                            // else iterator not exhausted
                            // return the Node
                            return (Node) tempNode;
                        }
                        // else children exhausted - fall through
                    }
                    // No children - return self object
                    selfReturned = true;
                    nextChildIterator = null;
                    return Node.this;
                }
            }

            public void remove()
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }
        }


        /**
         * Class <tt>Ancestor</tt> is a member class of <tt>Node</tt>.
         *
         * It implements the <tt>Iterator</tt> interface, excluding the
         * optional <tt>remove</tt> method.  The iterator traverses the
         * ancestors of its containing Node from the Node's immediate
         * parent back to tge root Node of the containing <tt>Tree</tt>.
         *
         * The iterator is <i>fast-fail</i>.  If any modifications occur to
         * the tree as a whole during the lifetime of the iterator, a
         * subsequent call to next() will throw a
         * ConcurrentModificationException.  See the discussion of
         * fast-fail iterators in <tt>AbstractList</tt>.
         *
         * The <tt>modCount</tt> field used to maintain information about
         * structural modifcations is maintained for all nodes in the
         * containing Tree instance.
         */

        class Ancestor implements Iterator {
            private Tree.Node nextAncestor;
            private int age;

            /**
             * Constructor
             *
             * @param age  the current value of the modCount field in the
             * <tt>Tree</tt> instance which includes this class instance.
             */

            public Ancestor(int age) {
                this.age = age;
                nextAncestor = Node.this.parent;
            }

            public boolean hasNext() {
                return nextAncestor != null;
            }

            public Object next()
                throws NoSuchElementException,
                       ConcurrentModificationException {
                synchronized (Tree.this) {
                    // The tree is a
                    // potentially dymanic structure, which could be
                    // undergoing modification as this method is being
                    // executed, and it is possible that the Comod exception
                    // could be set to trigger while this call is in process.
                    if (! Tree.this.modCountEqualTo(age)) {
                        throw new ConcurrentModificationException();
                    }
                    Tree.Node tmpNode = nextAncestor;
                    nextAncestor = tmpNode.parent;
                    return tmpNode;
                }
            }

            public void remove()
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }
        }


        /**
         * Class <tt>FollowingSibling</tt> is a member class of <tt>Node</tt>.
         *
         * It implements the <tt>ListIterator</tt> interface, but has reports
         * UnsupportedOperationException for all methods except
         * <tt>hasNext()</tt>, <tt>next()</tt> and <tt>nextIndex()</tt>.
         * These methods are implemented as synchronized wrappers around the
         * underlying ArrayList methods.
         *
         * The listIterator traverses those children in the parent node's
         * <tt>children</tt> <tt>ArrayList</tt> which follow the subject
         * node's entry in that array, using the <tt>next()</tt> method.
         *
         * The iterator is <i>fail-fast</i>.  if any modification occur to
         * the tree as a whole during the lifetime of the iterator, a
         * subsequent call to next() will throw a
         * ConcurrentModificationException.  See the discussion of
         * fast-fail iterators in <tt>AbstractList</tt>.
         *
         * The fail-fast ListIterator in ArrayList is the underlying
         * mechanism for both the listIterator and the fail-fast
         * behaviour.
         */

        class FollowingSibling implements ListIterator {

            private ListIterator listIterator;
            private ArrayList rootDummy = new ArrayList();
            // An empty ArrayList for the root listIterator
            // hasNext() will always return false

            public FollowingSibling() {
                synchronized (Tree.this) {
                    // Set up iterator on the parent's arrayList of children
                    Tree.Node refNode = Node.this.parent;
                    if (refNode != null) {
                        // Not the root node; siblings may exist
                        // Set up iterator on the parent's children ArrayList
                        ArrayList siblings = refNode.children;
                        int index = siblings.indexOf((Object) Node.this);
                        // if this is invalid, we are in serious trouble
                        listIterator = siblings.listIterator(index + 1);
                    } // end of if (Node.this.parent != null)
                    else {
                        // Root node - no siblings
                        listIterator = rootDummy.listIterator();
                    }
                }
            }

            public boolean hasNext() {
                // Any CoMod exception will be thrown by the listIterator
                // provided with ArrayList.  It does not throw such exceptions
                // on calls to hasNext();
                synchronized (Tree.this) {
                    return listIterator.hasNext();
                }
            }

            public Object next()
                throws NoSuchElementException,
                       ConcurrentModificationException {
                synchronized (Tree.this) {
                    // N.B. synchronization here is still on the Tree
                    // rather than on the Node containing the children
                    // ArryList of interest.  Other ArrayList operations
                    // throughout the Tree are synchronized on the Tree object
                    // itself, so exceptions cannot be made for these more
                    // directly Nodal operations.
                    return listIterator.next();
                }
            }

            public int nextIndex() {
                synchronized (Tree.this) {
                    return listIterator.nextIndex();
                }
            }

            public void add(Object o)
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }

            public void remove()
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }

            public boolean hasPrevious()
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }

            public Object previous()
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }

            public int previousIndex()
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }

            public void set(Object o)
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }
        }

        /**
         * Class <tt>PrecedingSibling</tt> is a member class of <tt>Node</tt>.
         *
         * It implements the <tt>ListIterator</tt> interface, but has reports
         * UnsupportedOperationException for all methods except
         * <tt>hasPrevious()</tt>, <tt>previous()</tt> and
         * <tt>previousIndex()</tt>.
         * These methods are implemented as synchronized wrappers around the
         * underlying ArrayList methods.
         *
         * The listIterator traverses those children in the parent node's
         * <tt>children</tt> <tt>ArrayList</tt> which precede the subject
         * node's entry in that array, using the <tt>previous()</tt> method.
         * I.e., siblings are produced in reverse sibling order.
         *
         * The iterator is <i>fail-fast</i>.  if any modification occur to
         * the tree as a whole during the lifetime of the iterator, a
         * subsequent call to previous() will throw a
         * ConcurrentModificationException.  See the discussion of
         * fast-fail iterators in <tt>AbstractList</tt>.
         *
         * The fail-fast ListIterator in ArrayList is the underlying
         * mechanism for both the listIterator and the fail-fast
         * behaviour.
         */

        class PrecedingSibling implements ListIterator {

            private ListIterator listIterator;
            private ArrayList rootDummy = new ArrayList();
            // An empty ArrayList for the root listIterator
            // hasNext() will always return false

            public PrecedingSibling() {
                synchronized (Tree.this) {
                    // Set up iterator on the parent's arrayList of children
                    Tree.Node refNode = Node.this.parent;
                    if (refNode != null) {
                        // Not the root node; siblings may exist
                        // Set up iterator on the parent's children ArrayList
                        ArrayList siblings = refNode.children;
                        int index = siblings.indexOf((Object) Node.this);
                        // if this is invalid, we are in serious trouble
                        listIterator = siblings.listIterator(index);
                    } // end of if (Node.this.parent != null)
                    else {
                        // Root node - no siblings
                        listIterator = rootDummy.listIterator();
                    }
                }
            }

            public boolean hasPrevious() {
                // Any CoMod exception will be thrown by the listIterator
                // provided with ArrayList.  It does not throw such exceptions
                // on calls to hasNext();
                synchronized (Tree.this) {
                    return listIterator.hasPrevious();
                }
            }

            public Object previous()
                throws NoSuchElementException,
                       ConcurrentModificationException {
                synchronized (Tree.this) {
                    // N.B. synchronization here is still on the Tree
                    // rather than on the Node containing the children
                    // ArryList of interest.  Other ArrayList operations
                    // throughout the Tree are synchronized on the Tree object
                    // itself, so exceptions cannot be made for these more
                    // directly Nodal operations.
                    return listIterator.previous();
                }
            }

            public int previousIndex() {
                synchronized (Tree.this) {
                    return listIterator.previousIndex();
                }
            }

            public void add(Object o)
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }

            public void remove()
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }

            public boolean hasNext()
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }

            public Object next()
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }

            public int nextIndex()
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }

            public void set(Object o)
                throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
            }
        }

    }

}
//package org.apache.fop.datatypes;

import java.util.*;

/**
 * TreeTest.java
 *
 * $Id: TreeTest.java,v 1.6 2001-07-22 16:38:05+10 pbw Exp pbw $
 * @author <a href="mailto:[EMAIL PROTECTED]";>Peter B. West</a>
 * @version
 */

public class TreeTest{
    public TreeTest (){}
    
    public static void main(String[] args)
        throws Tree.TreeException {
        Tree tree = new Tree();
        Tree.Node root = tree.new Node(null, "Root");
        Tree.Node child1 = tree.new Node(root, "1-1");
        Tree.Node child2 = tree.new Node(root, "1-2");
        Tree.Node child3 = tree.new Node(root, "1-3");
        Tree.Node child2_1 = tree.new Node(root.getChild(1), "1-2-1");
        Tree.Node child2_2 = tree.new Node(root.getChild(1), "1-2-2");
        Tree.Node child3_1 = tree.new Node(root.getChild(2), "1-3-1");
        Tree.Node child3_2 = tree.new Node(root.getChild(2), "1-3-2");
        Tree.Node child3_3 = tree.new Node(root.getChild(2), "1-3-3");
        Tree.Node child1_1 = tree.new Node(root.getChild(0), "1-1-1");
        System.out.println("Pre-order traversal:root:");
        preorder(root, tree.getModCount());
        System.out.println("Post-order traversal:root:");
        postorder(root, tree.getModCount());
        System.out.println("Preceding siblings 3-2");
        precedingsibling(child3_2);
        System.out.println("Following siblings 3-2");
        followingsibling(child3_2);
        System.out.println("Preceding siblings 2-2");
        precedingsibling(child2_2);
        System.out.println("Following siblings 2-2");
        followingsibling(child2_2);
        System.out.println("Preceding siblings 1");
        precedingsibling(child1);
        System.out.println("Following siblings 1");
        followingsibling(child1);
        System.out.println("Preceding siblings root");
        precedingsibling(root);
        System.out.println("Following siblings root");
        followingsibling(root);
        System.out.println("Pre-order traversal:2:");
        preorder(child2, tree.getModCount());
        System.out.println("Post-order traversal:3:");
        postorder(child3, tree.getModCount());
        System.out.println("Ancestors:3-2");
        ancestors(child3_2, tree.getModCount());
        root.removeChild(child2);
        System.out.println("Removing child2");
        System.out.println("Pre-order traversal:root:");
        preorder(root, tree.getModCount());
        System.out.println("Post-order traversal:root:");
        postorder(root, tree.getModCount());
        // Test for fast-fail
        System.out.println("Setting up PreOrder iterator");
        Tree.Node.PreOrder iterator = root.new PreOrder(tree.getModCount());
        System.out.println("Adding child4");
        Tree.Node child4 = tree.new Node(root, "1-4");
        System.out.println("Iterating");
        try {
            while (iterator.hasNext()) {
                Tree.Node next = (Tree.Node) iterator.next();
                System.out.println((String)next.getPayload());
            }
        } catch (ConcurrentModificationException e) {
            System.out.println("Comod exception caught");
        } // end of try-catch
        System.out.println("Setting up FollowingSibling listIterator on 3-2");
        Tree.Node.FollowingSibling listiterator =
                child3_2.new FollowingSibling();
        System.out.println("Perturbing child3-2 parent; adding 3-4");
        Tree.Node child3_4 = tree.new Node(child3, "1-3-3");
        try {
            while (listiterator.hasNext()) {
                Tree.Node next = (Tree.Node) listiterator.next();
                System.out.println((String)next.getPayload());
            }
        } catch (ConcurrentModificationException e) {
            System.out.println("Comod exception caught");
        }

        System.out.println("Setting up Ancestor Iterator on 1-1");
        Tree.Node.Ancestor aiterator =
                child1_1.new Ancestor(tree.getModCount());
        System.out.println("Perturbing root; adding 5");
        Tree.Node child5 = tree.new Node(root, "1-5");
        try {
            while (aiterator.hasNext()) {
                Tree.Node next = (Tree.Node) aiterator.next();
                System.out.println((String)next.getPayload());
            }
        } catch (ConcurrentModificationException e) {
            System.out.println("Comod exception caught");
        }
        
    }

    private static void preorder(Tree.Node node, int age) {
        Tree.Node.PreOrder iterator = node.new PreOrder(age);
        while (iterator.hasNext()) {
            Tree.Node next = (Tree.Node) iterator.next();
            System.out.println((String)next.getPayload());
        }
    }

    private static void postorder(Tree.Node node, int age) {
        Tree.Node.PostOrder iterator = node.new PostOrder(age);
        while (iterator.hasNext()) {
            Tree.Node next = (Tree.Node) iterator.next();
            System.out.println((String)next.getPayload());
        }
    }

    private static void ancestors(Tree.Node node, int age) {
        Tree.Node.Ancestor iterator = node.new Ancestor(age);
        while (iterator.hasNext()) {
            Tree.Node next = (Tree.Node) iterator.next();
            System.out.println((String)next.getPayload());
        }
    }
        
    private static void followingsibling(Tree.Node node) {
        Tree.Node.FollowingSibling iterator =
                node.new FollowingSibling();
        while (iterator.hasNext()) {
            Tree.Node next = (Tree.Node) iterator.next();
            System.out.println((String)next.getPayload());
        }
    }

    private static void precedingsibling(Tree.Node node) {
        Tree.Node.PrecedingSibling iterator =
                node.new PrecedingSibling();
        while (iterator.hasPrevious()) {
            Tree.Node previous = (Tree.Node) iterator.previous();
            System.out.println((String)previous.getPayload());
        }
    }

} // TreeTest

---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, email: [EMAIL PROTECTED]

Reply via email to