Arved, I have been rethinking the structure of the Tree class, and the issues surrounding fast-fail iterators and synchronization. I have stayed with ArrayList as the representation of the children list, and am relying on the fast-fail built into the implementation of ArrayList for the new FollowingSibling and PrecedingSibling ListIterators. All of the tree modifying operations are wrapped in a synchronization on the Tree object itself, which now contains no nodes itself, thus allowing for removal of all nodes, although I have yet to implement node removal, as opposed to child removal. I mention the synchronization issues because of the recent discussion about multi-threading, the complaints about performance, and the fact that Karen is planning to implement a multi-thread layout engine. The specifics you mention below I have not yet addressed, apart from introducing the sibling ListIterators. I will proceed onto some of those topics now. Attached are the new all-singing, all-dancing Tree.java, and an extended version of TreeTest.java (which is completely unintegrated into any test framework.) Peter P.S. I notice that sometimes your Reply-To gives your personal address, and at others the fop-dev address. Arved Sandstrom wrote: > > Hi, Peter > > Your Tree class efforts have not gone unnoticed. I've been mulling them over, > anyway. > > My interest in what you are doing is not related to flattening, per se, > although this mechanism may simplify answering questions that we need to ask. > The kinds of questions that routinely come up are: > > 1. Is this area leading or trailing in context (page, even-page, odd-page, > column)? > 2. Is this area first or last in a reference-area or page-sequence? > 3. Get me the preceding or succeeding sibling. Get me all siblings and/or > ancestors that have this or that constraint (e.g. particular keep); > 4. Tell me if there is a stacking constraint before or after this area? If > so, what is it? > > There are convoluted mechanisms for doing some of this. Answering questions > about trailing conditions (is this area trailing in context? is this the last > area in the page sequence?) are currently not so easy. I don't want to even > think about trying to answer question 4 for all the different situations - > anything your efforts can do to simplify that would be great. I know that you > have taken an interest in space-specifier resolution; the first step of > course is just to figure out what the sequence of space specifiers is, > assuming a stacking constraint exists, and right now that would be a serious > pain in the butt. > > I would recommend familiarizing with our current area hierarchy, assuming you > have not already done so. Basically Pages are flat within the area tree > (AreaTree); each page contains 5 AreaContainers (for the regions), and the > region-body itself is a container for 3 AreaContainers. One of those, the > main-reference-area, is a container for span-area AreaContainers, and > finally, span-areas contain ColumnAreas, which are also AreaContainers (and > represent normal-flow-areas). So you see that we are pretty closely following > the abstract model in the spec. > > ColumnAreas contain all the actual normal flow stuff. > > I cannot really say that there are any context stacks. Areas maintain a list > of their children, as a Vector. There is just no other context information > easily to be had, for example related to easily answering questions like the > above. If you look at the checkBreakBefore() method in PropertyManager, > you'll see the kinds of hoops we have to jump through right now to answer > basic questions...it would be nice to obviate the necessity for that. > > Any insight you can bring to bear on this would be appreciated. I'd > personally be happy to assist with integrating your tree stuff into FOP. > > Regards, > Arved > > -- 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.12 2001-07-19 01:42:38+10 pbw Exp pbw $ * @author <a href="mailto:[EMAIL PROTECTED]";>Peter B. West</a> * @version */ public class Tree { /** * The number of times the tree has been <i>structurally modified</i>. * See the discussion of the <tt>modCount</tt> field in * <tt>AbstractList</tt>. */ protected int modCount = 0; protected int nodeCount = 0; protected Node root; public Tree() {} public Tree(Node root) { this.root = root; } public int modified() { // In the Tree class, this function updates the modCount // N.B. This method is always called from within a synchronized // method. synchronized (this) { return ++modCount; } } public int getModCount() { synchronized (this) { return modCount; } } public boolean modCountEqualTo(int value) { synchronized (this) { return value == modCount; } } public int size() { return nodeCount; } public boolean isEmpty() { return nodeCount == 0; } public class TreeException extends Exception { public TreeException(String message) { super(message); } } /** * Member class <tt>Node</tt> of class <tt>Tree</tt> provides the * structure for a general-purpose tree. * * Node * +-------------------------+ * |(Node) parent | * +-------------------------+ * |ArrayList | * |+-----------------------+| * ||(Node) child 0 || * |+-----------------------+| * |: :| * |+-----------------------+| * ||(Node) child n || * |+-----------------------+| * +-------------------------+ * |(Object) payload -> | * | contents of this node | * +-------------------------+ * * <tt>ArrayList</tt> is used for the list of children because the * synchronization is performed "manually" within the individual methods, * and beause the <i>fail-fast</i> characteristics of the ArrayList * iterator and listIterators is desired. * * See <tt>Tree</tt> for the tree-wide support methods and fields. */ public class Node { private Node parent; private ArrayList children; // ArrayList of Node protected Object payload; /** * No argument constructor. * * Assumes that this node is the root, and so will throw a * <tt>TreeException</tt> when the root node in the enclosing * <tt>Tree</tt> object is non-null. */ public Node() throws TreeException { if (Tree.this.root != null) { throw new TreeException( "No arg constructor invalid when root exists"); } parent = null; Tree.this.root = this; children = new ArrayList(); payload = null; } /** * Constructor with one parameter. * @param parent Node which is the parent of this Node. if this is * null, the generated Node is assumed to be the root * node. If the Tree root node is already set, throws * a <tt>TreeException</tt>. */ public Node(Node parent) throws TreeException { children = new ArrayList(); payload = null; if (parent == null) { if (Tree.this.root != null) { throw new TreeException("Null Node constructor " + "invalid when root exists"); } this.parent = null; Tree.this.root = this; } else { // The parent must be a node in the current tree if (parent.getTree() != Tree.this) { throw new TreeException("Parent not in same tree"); } this.parent = parent; // connect me to my parent parent.addChild(this); } } /** * Two argument constructor. * @param parent The parent <tt>Node</tt> of this Node. If null, * this must be the root node. * @param payload An object which is the actual payload of this node; * the contents of the Node. */ public Node(Node parent, Object payload) throws TreeException { this(parent); this.payload = payload; } public Node getRoot() { return Tree.this.root; } /** * Appends a child <tt>Node</tt> to this node. Synchronized on the * containing <tt>Tree</tt> object. * * Calls the <tt>modified</tt> method of the containing Tree to * maintain the value of <tt>modCount</tt>. * * @param child Node to be added. */ public void addChild(Node child) { synchronized (Tree.this) { children.add((Object) child); Tree.this.modified(); } } /** * Removes the child <tt>Node</tt> at the specified index in the * ArrayList. Synchronized on the enclosing <tt>Tree</tt> object. * * Calls the <tt>modified</tt> method of the containing Tree to * maintain the value of <tt>modCount</tt>. * * @param index The int index of the child to be removed. * @return the node removed. */ public Node removeChildAtIndex(int index) { synchronized (Tree.this) { Node tmpNode = (Node) children.remove(index); Tree.this.modified(); return tmpNode; } } /** * Removes the specified child <tt>Node</tt> from the children * ArrayList. Synchronized on the enclosing <tt>Tree</tt> object. * * Implemented by calling <tt>removeChildAtIndex()</tt>. Relies * on that method to call the <tt>modified</tt> method of the * containing Tree to maintain the value of <tt>modCount</tt>. * * @param child The child node to be removed. * @return the node removed. */ public Node removeChild(Node child) throws NoSuchElementException { synchronized (Tree.this) { int index = children.indexOf((Object) child); if (index == -1) { throw new NoSuchElementException(); } Node tmpNode = removeChildAtIndex(index); // Note - no call to Tree.this.modified() here - // done in removeChildAtindex() return tmpNode; } } public Tree getTree() { return Tree.this; } public Node getChild(int index) { return (Node) children.get(index); } public Object getPayload() { return payload; } public void setPayload(Object payload) { this.payload = payload; } /** * Class <tt>PreOrder</tt> is a member class of <tt>Node</tt>. * * It implements the <tt>Iterator</tt> interface, excluding the * optional <tt>remove</tt> method. The iterator traverses its * containing <tt>Tree</tt> from its containing Node in * preorder order. * * The method is implemented recursively; a PreOrder object is * instantiated at every level of the tree to handle the children at * that level. * * The iterator is <i>fast-fail</i>. if any 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 <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>. 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 <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>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.5 2001-07-18 23:50:58+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()); 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()); } // end of while (iterator.hasNext()) } 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 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]
