Arved, A little progress on the Tree class. I have added a copySubTree method to Node to allow for the copying of a subtree to another place in the tree. void copySubTree(Node subtree, int index) The subtree is copied as a child of this at the specified index position. This version works fairly directly, so attempts to copy a subtree as a child of itself or as a child of any of its descendants throw a TreeException. The whole operation is synchronized on the containing Tree. Of course, contrary to what I said before, the same subtree cannot occur in more than one place in a tree, unless you want to sacrifice parent links, which rather defeats the purpose. I will be looking at the setup of the FO and Area trees to see how much is involved in levering Tree in there. 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.14 2001-07-30 23:02:29+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; } /** * @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(); 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(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(); 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); } } /** * @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; } /** * @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 payload An object which is the actual payload of this node; * the contents of the Node. */ public Node(Node parent, int index, Object payload) throws TreeException, IndexOutOfBoundsException { this(parent, index); 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(); } } /** * 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.getPayload()); // 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; } } public Tree getTree() { return Tree.this; } public Node getParent() { return (Node) parent; } public Node getChild(int index) { return (Node) children.get(index); } public Object getPayload() { return payload; } public void setPayload(Object payload) { this.payload = payload; } 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; 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.7 2001-07-30 23:03:36+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()); // 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()); 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]
