I have attempted to make Tree class operations thread-safe, and have added a subclass TreeRoot in an attempt to support fail-fast iterators as in AbstractList and its subclasses. Comments from more experienced Java folks would be welcome. My motivation, apart from the perceived need to give direct expression to the trees in use, was to provide a platform for some of the tree flattening operations which werer talked about here briefly. My concerns about the relationship between the final form of layout and the tree structure have tended to resolve in favour of virtual operations on an underlying tree, because the trees express so eloquently the relationships between the various layout components. If virtual flattening operations on trees are to be implemented, they will have to have well defined trees to work with, I should think. I still haven't looked in depth into the code, but it also occurs to me that, in association with the FO and area trees, a context stack would be a very useful way of keeping track of a lot of information that is relevant to the layout process. Some such stack or stacks may already be present in the code, explicitly or implicitly. Can someone point me in the right direction? 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.*; /** * Tree.java * * $Id: Tree.java,v 1.7 2001-07-10 14:08:30+10 pbw Exp pbw $ * @author <a href="mailto:[EMAIL PROTECTED]";>Peter B. West</a> * @version */ public class Tree { private Tree parent; private ArrayList children; // ArrayList of Tree protected Object payload; protected Tree root; // A general-purpose tree structure // // Tree // +-------------------------+ // |(Tree) parent | // +-------------------------+ // |ArrayList | // |+-----------------------+| // ||(Tree) child 0 || // |+-----------------------+| // |: :| // |+-----------------------+| // ||(Tree) child n || // |+-----------------------+| // +-------------------------+ // |(Object) holding | // | contents of this node | // +-------------------------+ // Pre- and Post-Order iterators are provided. // Constructing and iterator for this tree node involves // (for preorder) returning (this) node // constructing an iterator for the vector containing the children // iterating through the vector by // constructing an iterator on each of the children in turn // exhausting that iterator // The root may be another Tree structure, or it may be an instance of // the TreeRoot subclass of Tree. In the latter case, fast-fail // iterators will be provided using the modCount field of the TreeRoot // object. public Tree() { parent = null; root = this; children = new ArrayList(); payload = null; } public Tree(Tree parent) { this(); this.parent = parent; // connect me to my parent if (parent != null) { parent.addChild(this); root = parent.getRoot(); } } public Tree(Tree parent, Object payload) { this(parent); this.payload = payload; } public Tree getRoot() { return root; } public void addChild(Tree child) { synchronized (root) { children.add((Object) child); root.modified(); } } public Tree removeChildAtIndex(int index) { synchronized (root) { Tree tmpTree = (Tree) children.remove(index); root.modified(); return tmpTree; } } public Tree removeChild(Tree child) throws NoSuchElementException { synchronized (root) { int index = children.indexOf((Object) child); if (index == -1) { throw new NoSuchElementException(); } Tree tmpTree = removeChildAtIndex(index); // Note - no call to root.modified() here - // done in removeChildAtindex() return tmpTree; } } public Tree getChild(int index) { return (Tree) children.get(index); } public Object getPayload() { return payload; } public void setPayload(Object payload) { this.payload = payload; } // The following functions are dummies for the case where no // TreeRoot has been instantiated and the root node is a Tree. public int modified() { return 0; // Do nothing much } public int getCount() { return 0; // Do nothing much } public boolean countEqualTo(int value) { return true; // Do nothing much } 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; public PreOrder(int age) throws ConcurrentModificationException { this.age = age; if (! root.countEqualTo(age)) { throw new ConcurrentModificationException(); } } public boolean hasNext() throws ConcurrentModificationException { // synchronize this against possible changes to the tree synchronized (root) { if (! root.countEqualTo(age)) { throw new ConcurrentModificationException(); } if (selfNotReturned) { return true; } // self has been returned - are there any children? // if so, we must always have an iterator available // even if 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, 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 (root) { // synchronize the whole against changes to the tree // no need to perfom age check as this is done in hasNext() if (! hasNext()) { throw new NoSuchElementException(); } if (selfNotReturned) { selfNotReturned = false; if (nextChildIndex < children.size()) { // We have children - create an iterator // for the first one nextChildIterator = ((Tree)(children.get(nextChildIndex))).new PreOrder(age); } // else do nothing; the nextChildIndex test in hasNext() // will prevent us from getting into trouble return Tree.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 tempTree = nextChildIterator.next(); // Check for exhaustion of the child if (! nextChildIterator.hasNext()) { // child iterator empty - another child? if (++nextChildIndex < children.size()) { nextChildIterator = ((Tree)(children.get(nextChildIndex))).new PreOrder(age); } // else leave iterator on empty } return (Tree) tempTree; } } } public void remove() throws UnsupportedOperationException { throw new UnsupportedOperationException(); } } 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; public PostOrder(int age) throws ConcurrentModificationException { this.age = age; if (! root.countEqualTo(age)) { throw new ConcurrentModificationException(); } } public boolean hasNext() throws ConcurrentModificationException { // Synchronize this against changes in the tree synchronized (root) { if (! root.countEqualTo(age)) { throw new ConcurrentModificationException(); } // 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 = ((Tree)(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 (root) { // synchronize the whole against changes to the tree // no need to perfom age check as this is done in hasNext() 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 tempTree = nextChildIterator.next(); // now check for exhaustion of the iterator if (! nextChildIterator.hasNext()) { if (++nextChildIndex < children.size()) { nextChildIterator = ((Tree) (children.get(nextChildIndex))).new PostOrder(age); } // else leave the iterator bumping on empty // next call will return self } // else iterator not exhausted // return the Tree return (Tree) tempTree; } // else children exhausted - fall through } // No children - return self object selfReturned = true; return Tree.this; } } public void remove() throws UnsupportedOperationException { throw new UnsupportedOperationException(); } } }
//package org.apache.fop.datatypes; import java.util.*; /** * TreeRoot.java * * $Id: TreeRoot.java,v 1.2 2001-07-10 14:09:17+10 pbw Exp pbw $ * @author <a href="mailto:[EMAIL PROTECTED]";>Peter B. West</a> * @version */ public class TreeRoot extends Tree { private int modCount; public TreeRoot() { super(); } public TreeRoot (Object payload) { super(); this.payload = payload; } public int modified() { // In the TreeRoot class, this function updates the modCount // N.B. This method is always called from within a synchronized // method. return ++modCount; } public int getCount() { synchronized (root) { return modCount; } } public boolean countEqualTo(int value) { synchronized (root) { return value == modCount; } } }
//package org.apache.fop.datatypes; /** * TreeTest.java * * $Id: TreeTest.java,v 1.3 2001-07-10 14:10:24+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){ TreeRoot root = new TreeRoot("Root"); new Tree(root, "1-1"); Tree child2 = new Tree(root, "1-2"); new Tree(root, "1-3"); new Tree(root.getChild(1), "1-2-1"); new Tree(root.getChild(1), "1-2-2"); new Tree(root.getChild(2), "1-3-1"); new Tree(root.getChild(2), "1-3-2"); new Tree(root.getChild(2), "1-3-3"); new Tree(root.getChild(0), "1-1-1"); System.out.println("Pre-order traversal:"); preorder(root, root.getCount()); System.out.println("Post-order traversal:"); postorder(root, root.getCount()); root.removeChild(child2); System.out.println("Pre-order traversal:"); preorder(root, root.getCount()); System.out.println("Post-order traversal:"); postorder(root, root.getCount()); } private static void preorder(Tree node, int age) { Tree.PreOrder iterator = node.new PreOrder(age); while (iterator.hasNext()) { Tree next = (Tree) iterator.next(); System.out.println((String)next.getPayload()); } } private static void postorder(Tree node, int age) { Tree.PostOrder iterator = node.new PostOrder(age); while (iterator.hasNext()) { Tree next = (Tree) iterator.next(); System.out.println((String)next.getPayload()); } } } // TreeTest
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, email: [EMAIL PROTECTED]
