Re: Tree class
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 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.
*
* 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 Node
* elements.
*
*
* The primary reasons for the existence of a separate Tree
* class is to provide an object for tree-wide synchronization, and to
* have a home for modCount for the provision of
* fast-fail iterators. For more details, see the
* discussion of modCount in AbstractList.
*
* $Id: Tree.java,v 1.14 2001-07-30 23:02:29+10 pbw Exp pbw $
* @author mailto:[EMAIL PROTECTED]";>Peter B. West
* @version
*/
public class Tree {
/**
* The number of times the tree has been structurally modified.
* See the discussion of the modCount field in
* AbstractList.
*/
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 Node of class Tree provides the
* structure for a general-purpose tree.
*
* Node
* +-+
* |(Node) parent|
* +-+
* |ArrayList|
* |+---+|
* ||(Node) child 0 ||
* |+---+|
* |: :|
* |+---+|
* ||(Node) child n ||
* |+---+|
* +-+
* |(Object) payload -> |
* | contents of this node |
* +-+
*
* ArrayList is used for the list of children because the
* synchronization is performed "manually" within the individual methods,
* and beause the fail-fast characteristics of the ArrayList
* iterator and listIterators is desired.
*
* See Tree 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
* TreeException when the root node in the enclosing
* Tree 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 No
Re: Tree class
I have added the Ancestor iterator class. The main outstanding task
with Tree is to think through the full impact of changes to the tree,
particularly deletions, on the iterators. Should a removal descend the
subtree recursively deleting, for example.
The current situation is that any change in the tree throws a
ConcurrentModificationException on PreOrder, PostOrder and Ancestor, but
the current state of the iterator is otherwise unchanged. Under what
circumstances, if any, might it be reasonable to pick up the iterator
after a Comod exception?
The Preceding/FollowingSibling iterators only throw Comod exceptions on
changes to the parents 'chldren' ArrayList - other changes in the Tree
go unnoticed.
Off the top of my head, I think that XSL-style tree partitioning
(Ancestors, Children, Preceding and Following) can be achieved with
little extra effort on the basis of the existing iterators, if such is
required.
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 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.
*
* 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 Node
* elements.
*
*
* The primary reasons for the existence of a separate Tree
* class is to provide an object for tree-wide synchronization, and to
* have a home for modCount for the provision of
* fast-fail iterators. For more details, see the
* discussion of modCount in AbstractList.
*
* $Id: Tree.java,v 1.13 2001-07-22 16:38:42+10 pbw Exp pbw $
* @author mailto:[EMAIL PROTECTED]";>Peter B. West
* @version
*/
public class Tree {
/**
* The number of times the tree has been structurally modified.
* See the discussion of the modCount field in
* AbstractList.
*/
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 Node of class Tree provides the
* structure for a general-purpose tree.
*
* Node
* +-+
* |(Node) parent|
* +-+
* |ArrayList|
* |+---+|
* ||(Node) child 0 ||
* |+---+|
* |: :|
* |+---+|
* ||(Node) child n ||
* |+---+|
* +-+
* |(Object) payload -> |
* | contents of this node |
* +-+
*
* ArrayList is used for the list of children because the
* synchronization is performed "manually" within the individual methods,
* and beause the fail-fast characteristics of the ArrayList
* iterator and listIterators is desired.
*
* See Tree 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
* TreeException when the root node in the enclosing
* Tree 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;
Re: Tree class
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 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. * * 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 Node * elements. * * * The primary reasons for the existence of a separate Tree * class is to provide an object for tree-wide synchronization, and to * have a home for modCount for the provision of * fast-
Re: Tree class
Arved, Thanks for the feedback, and thanks for giving me some directions. I'll try to chase some of them down in the next week of so. Peter Arved Sandstrom wrote: > On Tuesday 10 July 2001 04:27, Peter B. West wrote: > > >>>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 >> > > 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?" - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, email: [EMAIL PROTECTED]
Re: Tree class
On Tuesday 10 July 2001 04:27, Peter B. West wrote: > > 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 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 -- Fairly Senior Software Type e-plicity (http://www.e-plicity.com) Halifax, Nova Scotia Wireless * B2B * J2EE * XML - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, email: [EMAIL PROTECTED]
Re: Tree class
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 mailto:[EMAIL PROTECTED]";>Peter B. West
* @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 nextChildInde
