pbwest 2002/11/04 07:17:10 Modified: src/org/apache/fop/datastructs Tag: FOP_0-20-0_Alt-Design Tree.java Added: src/org/apache/fop/datastructs Tag: FOP_0-20-0_Alt-Design Node.java TreeException.java Log: Node and TreeException externalised from Tree. Revision Changes Path No revision No revision 1.1.2.3 +48 -967 xml-fop/src/org/apache/fop/datastructs/Attic/Tree.java Index: Tree.java =================================================================== RCS file: /home/cvs/xml-fop/src/org/apache/fop/datastructs/Attic/Tree.java,v retrieving revision 1.1.2.2 retrieving revision 1.1.2.3 diff -u -r1.1.2.2 -r1.1.2.3 --- Tree.java 24 Oct 2002 14:16:53 -0000 1.1.2.2 +++ Tree.java 4 Nov 2002 15:17:10 -0000 1.1.2.3 @@ -9,40 +9,18 @@ package org.apache.fop.datastructs; -import java.util.ArrayList; -import java.util.ConcurrentModificationException; -import java.util.NoSuchElementException; -import java.util.Iterator; -import java.util.ListIterator; - -// 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. /** - * A generalised tree class with traversal <tt>Iterator</tt>s. + * A generalised tree class. * * <p>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.</p> + * may be collected for manipulation. * * <p>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.</p> - * - * <p>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>.</p> + * elements. * * @author <a href="mailto:pbwest@;powerup.com.au">Peter B. West</a> * @version $Revision$ $Name$ @@ -56,9 +34,16 @@ * <tt>AbstractList</tt>. */ protected int modCount = 0; + + /** + * Count of the nodes in this tree. + */ protected int nodeCount = 0; - protected Node root; + /** + * The root node of this tree. + */ + protected Node root = null; public Tree() {} @@ -71,970 +56,66 @@ } } + /** + * Get the value of the <i>modCount</i> field, used to warn of concurrent + * modification of the tree during certain unsynchronized operations. + * @return - the <tt>int</tt> <i>modCount</i>. + */ public int getModCount() { synchronized (this) { return modCount; } } + /** + * Test the <i>modCount</i> field value. + * @param value - the value to test against <i>modCount</i>. + * @return <tt>boolean</tt> test result. + */ public boolean modCountEqualTo(int value) { synchronized (this) { return value == modCount; } } + /** + * Get the number of nodes in the tree. + * @return the number of nodes. + */ public int size() { return nodeCount; } + /** + * Is the tree empty? + * @return <tt>boolean</tt> answer to the question. Tests whether the + * root node is <tt>null</tt>. + */ public boolean isEmpty() { - return nodeCount == 0; + return root == null; } - public Node getRoot() { - return root; - } - - public void unsetRoot() { - root = null; + /** + * Set the <i>root</i> field. + * @param root the <tt>Node</tt> which is to be the root of the tree. + */ + public void setRoot(Node root) { + this.root = root; } - - public class TreeException extends Exception { - public TreeException(String message) { - super(message); - } - + /** + * Get the root node of the tree. + * @return the root <tt>Node</tt>. + */ + public Node getRoot() { + return root; } /** - * <p>Member class <tt>Node</tt> of class <tt>Tree</tt> provides the - * structure for a general-purpose tree.</p> - * <pre> - * Node - * +-------------------------+ - * |(Node) parent | - * +-------------------------+ - * |ArrayList | - * |+-----------------------+| - * ||(Node) child 0 || - * |+-----------------------+| - * |: :| - * |+-----------------------+| - * ||(Node) child n || - * |+-----------------------+| - * +-------------------------+ - * </pre> - * <p><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.</p> - * - * <p>Note that there is no payload carried by the Node. This class must - * be subclassed to carry any actual node contents.</p> - * - * <p>See <tt>Tree</tt> for the tree-wide support methods and fields.</p> + * Clear the <i>root</i> field. I.e., empty the tree. */ - - public class Node implements Cloneable { - - 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); - } - } - - - /** - * 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.) - * - * WARNING: this version of the method assumes that <tt>Tree.Node</tt> - * will be subclassed; <tt>Tree.Node</tt> has no contents, so for - * the tree to carry any data the Node must be subclassed. As a - * result, this method copies nodes by performing a <tt>clone()</tt> - * operation on the nodes being copied, rather than issuing a - * <tt>new Tree.Node(..)</tt> call. It then adjusts the necessary - * references to position the cloned node under the correct parent. - * As part of this process, the method must create a new empty - * <i>children</i> <tt>ArrayList</tt>. if this is not done, - * subsequent <tt>addChild()</tt> operations on the node will affect - * the original <i>children</i> array. - * - * This warning applies to the contents of any subclassed - * <tt>Tree.Node</tt>. All references in the copied subtree will be to - * the objects from the original subtree. If this has undesirable - * effects, the method must be overridden so that the copied subtree - * can have its references adjusted after the copy. - * - * @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) { - Node newNode = null; - 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()); - // Clone (shallow copy) the head of the subtree - try { - newNode = (Node)subtree.clone(); - } catch (CloneNotSupportedException e) { - throw new TreeException( - "clone() not supported on Tree.Node"); - } - - // Attach the clone to this at the indicated child index - newNode.parent = this; - this.addChild(index, newNode); - // Clear the children arrayList - newNode.children = new ArrayList(newNode.numChildren()); - // 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 - 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 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(); - } - } - + public void unsetRoot() { + root = null; } } No revision No revision 1.1.2.1 +959 -0 xml-fop/src/org/apache/fop/datastructs/Attic/Node.java 1.1.2.1 +32 -0 xml-fop/src/org/apache/fop/datastructs/Attic/TreeException.java
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]