Dear Listners,

I have attached the latest iteration of Tree.java.  I saw that Mark was 
bypassing part of the FO tree, I think it was.  At any rate, with 
dynamic rendering, there was a need to be able to delete a subtree.  The 
methods are deleteSubTree and delete.

Looking at applying Tree to the FO tree, I quickly ran into the 
limitations of my Java knowledge.  Tree at the moment is a top-level 
class with a member class Node.  Node, in turn, has member classes which 
  provide the various Iterators.  It seemed a good idea at the time, 
Iterators being all the rage.

When I came to look at the application of this, I thought that making 
classes FOTree and FONode, where FONode is a member class of FOTree, 
would be useful.  The problem is that I can't seem to arrange to inherit 
from a member class unless I that inheritance occurs within the context 
of an enclosing class which inherits from the parallel enclosing class. 
  I.e., given Tree with a member class Node, I can have a class FONode 
inherit from Node, provided FONode is a member class of FOTree, which 
inherits from Tree.

Currently FONode is an abstract class, the foundation of all of the FObj 
classes.  Every time I want to subclass FONode, I would have to do it as 
an member class of a subclass of FOTree.

There seems to be two alternatives.

One is to split Tree and Node, prohibiting orphan Nodes by having only 
constructors with a reference to a Tree as an argument.  Node can then 
be inherited, with all of the tree manipulation being done back in the 
superclass.  One advantage of this is that "Object contents" can be 
ignored, and FONode and its subclasses defined in much the same way. 
(Except that all the implicit tree operations must be re-specified in 
terms of Tree and Node.)  One question that arises from this is whether 
to retain the classes which implement the tree traversal iterators, of 
to recast them as Node methods.

The other alternative is to use the generic Tree/Node class directly to 
define both the FOTree and the AreaTree.  All of the inheritance would 
then be done throught the "contents" object, which would require a 
reference to its enclosing Node.  The object and its wrapper Node would 
have to be created in two operations at the time of creation of the object.

As I write this, the former option sounds better.

Any comments?

Peter
-- 
Peter B. West  [EMAIL PROTECTED]  http://powerup.com.au/~pbwest
"Lord, to whom shall we go?"
/*
 * $Id: Tree.java,v 1.20 2001-08-07 15:43:57+10 pbw Exp pbw $
 * Copyright (C) 2001 The Apache Software Foundation. All rights reserved.
 * For details on use and redistribution please refer to the
 * LICENSE file included with these sources.
 */

//package org.apache.fop.datatypes;

import java.util.*;

// TODO:
// Should I provide a separate or supplementary exception for CoMods appends
// on the trailing edge of the tree?  I.e., for each append, check if it is an
// append to a node which is the final sibling at any level of the tree.
// If so, set a copy the modCount value as the trailingEdgeModAge.
// If a ConcurrentModificationException is about to be thrown, check whether
// the trailingEdgeModAge is the same as the modCount.  If so, throw a
// ConcurrentTreeAppendException instead.  Probably, make that a subclass of
// ConcurrentModificationException so that the check can be done on the
// catch of the CoModEx.

/**
 * 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>.
 *
 * @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 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 Node getRoot() {
        return root;
    }

    public void unsetRoot() {
        root = null;
    }


    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) content ->      |
     * | 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 content;

        /**
         * 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();
            content = null;
        }

        /**
         * @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>.
         * @param index  int index of child in parent.
         */

        public Node(Node parent, int index)
            throws TreeException, IndexOutOfBoundsException {
            children = new ArrayList();
            content = 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(index, this);
            }
        }

        /**
         * @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, IndexOutOfBoundsException {
            children = new ArrayList();
            content = 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);
            }
        }


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

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

        /**
         * @param parent  The parent <tt>Node</tt> of this Node.  If null,
         *                this must be the root node.
         * @param index   int index of this child in the parent node.
         * @param content An object which is the actual content of this node;
         *                the contents of the Node.
         */

        public Node(Node parent, int index, Object content)
            throws TreeException, IndexOutOfBoundsException {
            this(parent, index);
            this.content = content;
        }

        /**
         * 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();
            }
        }

        /**
         * Adds a child <tt>Node</tt> in this node at a specified index
         * position.
         * 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 index  int position of new child
         * @param child  Node to be added.
         */

        public void addChild(int index, Node child)
            throws IndexOutOfBoundsException {
            synchronized (Tree.this) {
                children.add(index, (Object) child);
                Tree.this.modified();
            }
        }

        /**
         * Copies a subtree of this tree as a new child of 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>.
         *
         * Note that it is illegal to try to copy a subtree to one of
         * its own descendents or itself.  (This restriction could be lifted
         * by creating a new Tree containing the subtree, and defining an
         * attachTree() method to attach one Tree to another.)
         *
         * This is the public entry to copyCheckSubTree.  It will always
         * perform a check for the attempt to copy onto a descendent or
         * self.  It calls copyCheckSubTree.
         *
         * @param subtree Node at the root of the subtree to be added.
         * @param index int index of child position in Node's children
         */

        public void copySubTree(Node subtree, int index)
            throws TreeException, ConcurrentModificationException {
            copyCheckSubTree(subtree, index, true);
        }

        /**
         * Copies a subtree of this tree as a new child of 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>.
         *
         * Note that it is illegal to try to copy a subtree to one of
         * its own descendents or itself.  (This restriction could be lifted
         * by creating a new Tree containing the subtree, and defining an
         * attachTree() method to attach one Tree to another.)
         *
         * @param subtree Node at the root of the subtree to be added.
         * @param index int index of child position in Node's children
         * @param checkLoops boolean - should the copy been checked for
         *                     loops.  Set this to true on the first
         *                     call.
         */

        private void copyCheckSubTree(
                Node subtree, int index, boolean checkLoops)
            throws TreeException, ConcurrentModificationException {
            synchronized (Tree.this) {
                if (checkLoops) {
                    checkLoops = false;
                    if (subtree == this) {
                        throw new TreeException
                                ("Copying subtree onto itself.");
                    }
                
                    // Check that subtree is not an ancestor of this.
                    Ancestor ancestors =
                            new Ancestor(Tree.this.getModCount());
                    while (ancestors.hasNext()) {
                        if ((Node)ancestors.next() == subtree) {
                            throw new TreeException
                                    ("Copying subtree onto descendent.");
                        }
                    }
                }
                
                Node newNode = new Node(this, index, subtree.getContent());
                // Now iterate over the children of the root of the
                // subtree, adding a copy to the newly created Node
                Iterator iterator = subtree.nodeChildren();
                while (iterator.hasNext()) {
                    newNode.copyCheckSubTree((Node)iterator.next(),
                                             newNode.numChildren(),
                                             checkLoops);
                }
                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;
            }
        }

        /**
         * Deletes the entire subtree rooted on <tt>this</tt> from the 
         * <tt>Tree</tt>.  The Tree is
         * traversed in PostOrder, and each Node is removed in PostOrder.
         * @return int count of Nodes deleted.
         */
        public int deleteSubTree() {
            synchronized (Tree.this) {
                int count = delete(this);
                Tree.this.modified();
                return count;
            }
        }

        /**
         * N.B. this private method must only be called from the deleteSubTree
         * method, which is synchronized.  In itself, it is not synchronized.
         * @param subtree Node at the root of the subtree to be deleted.
         * @return int count of Nodes deleted.
         */
        private int delete(Node subtree) {
            int count = 0;
            
            while (subtree.numChildren() > 0) {
                //System.out.println("# children "+subtree.numChildren());
                
                count += delete((Node)subtree.children.get(0));
            }
            // Delete this node
            // nullify the parent reference
            if (subtree.getTree().getRoot() != subtree) {
                // Not the root node - remove from parent
                subtree.getParent().removeChild(subtree);
                subtree.unsetParent();
            } else {
                subtree.getTree().unsetRoot();
            } // end of else
            // nullify the content reference; cut content adrift
            subtree.unsetContent();
            return ++count;
        }

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

        public Node getParent() {
            return (Node) parent;
        }

        public void unsetParent() {
            parent = null;
        }

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

        public Object getContent() {
            return content;
        }

        public void setContent(Object content) {
            this.content = content;
        }

        public void unsetContent() {
            this.content = null;
        }

        public Iterator nodeChildren() {
            return children.iterator();
        }

        public int numChildren() {
            return children.size();
        }

        /**
         * 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;
         * at each node, a PreOrder object is instantiated to handle the
         * node itself and to trigger the handing of the node's children.
         * The node is returned first, and then for each child, a new
         * PreOrder is instantiated.  That iterator will terminate when the
         * last descendant of that child has been returned.
         *
         * 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;
         * at each node, a PostOrder object is instantiated to handle the
         * node itself and to trigger the handing of the node's children.
         * Firstly, for each child a new PostOrder is instantiated.
         * That iterator will terminate when the last descendant of that
         * child has been returned.  finally, the node itself is returned.
         *
         * 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.7 2001-07-30 23:03:36+10 pbw Exp pbw $ * @author Peter B. West * @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()); // Check the copySubTree function System.out.println("copySubTree child3 to child2_1"); child2_1.copySubTree(child3, 0); System.out.println("Pre-order traversal:root:"); preorder(root, tree.getModCount()); System.out.println("copySubTree child3_3 to root"); try { root.copySubTree(child3_3, 0); } catch (Tree.TreeException e) { System.out.println("Caught TreeException: " + e.getMessage()); } System.out.println("Pre-order traversal:root:"); preorder(root, tree.getModCount()); System.out.println("copySubTree child3 to child3_3"); try { child3_3.copySubTree(child3, 0); } catch (Tree.TreeException e) { System.out.println("Caught TreeException: " + e.getMessage()); } System.out.println("Pre-order traversal:root:"); preorder(root, tree.getModCount()); // Test the deleteSubTree method System.out.println("deleteSubTree child2_1"); int delcount = child2_1.deleteSubTree(); System.out.println("# deleted: "+delcount); 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.getContent()); } } 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.getContent()); } } 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.getContent()); } } catch (ConcurrentModificationException e) { System.out.println("Comod exception caught"); } System.out.println("Delete all nodes"); delcount = root.deleteSubTree(); System.out.println("# deleted: "+delcount); System.out.println("Pre-order traversal:root:"); preorder(tree.getRoot(), tree.getModCount()); } 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.getContent()); } } 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.getContent()); } } 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.getContent()); } } 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.getContent()); } } 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.getContent()); } } } // TreeTest
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, email: [EMAIL PROTECTED]

Reply via email to