cvs commit: xml-fop/src/org/apache/fop/datastructs Node.java
pbwest 2002/12/02 23:19:18
Modified:src/org/apache/fop/datastructs Tag: FOP_0-20-0_Alt-Design
Node.java
Log:
Iterator classes made public.
Revision ChangesPath
No revision
No revision
1.1.2.3 +7 -7 xml-fop/src/org/apache/fop/datastructs/Attic/Node.java
Index: Node.java
===
RCS file: /home/cvs/xml-fop/src/org/apache/fop/datastructs/Attic/Node.java,v
retrieving revision 1.1.2.2
retrieving revision 1.1.2.3
diff -u -r1.1.2.2 -r1.1.2.3
--- Node.java 5 Nov 2002 14:42:36 - 1.1.2.2
+++ Node.java 3 Dec 2002 07:19:18 - 1.1.2.3
@@ -565,7 +565,7 @@
* containing Tree instance.
*/
-class PreOrder implements Iterator {
+public 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.
@@ -709,7 +709,7 @@
* containing Tree instance.
*/
-class PostOrder implements Iterator {
+public 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.
@@ -827,7 +827,7 @@
* containing Tree instance.
*/
-class Ancestor implements Iterator {
+public class Ancestor implements Iterator {
private Node nextAncestor;
private int age;
@@ -896,7 +896,7 @@
* behaviour.
*/
-class FollowingSibling implements ListIterator {
+public class FollowingSibling implements ListIterator {
private ListIterator listIterator;
private ArrayList rootDummy = new ArrayList();
@@ -1008,7 +1008,7 @@
* behaviour.
*/
-class PrecedingSibling implements ListIterator {
+public class PrecedingSibling implements ListIterator {
private ListIterator listIterator;
private ArrayList rootDummy = new ArrayList();
-
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
cvs commit: xml-fop/src/org/apache/fop/datastructs Node.java
pbwest 2002/11/05 06:42:36
Modified:src/org/apache/fop/datastructs Tag: FOP_0-20-0_Alt-Design
Node.java
Log:
Added addSubTree() & setSubTreeTree() methods.
Added cutSubTree(). Changed delete() to preserve internal subtree structure for
cutSubTree().
Added setTree(), setParent() and unsetTree().
Removed unreachable code check in PreOrder Iterator.
Modified Iterators to account for possible null children ArrayList.
Revision ChangesPath
No revision
No revision
1.1.2.2 +170 -32 xml-fop/src/org/apache/fop/datastructs/Attic/Node.java
Index: Node.java
===
RCS file: /home/cvs/xml-fop/src/org/apache/fop/datastructs/Attic/Node.java,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -u -r1.1.2.1 -r1.1.2.2
--- Node.java 4 Nov 2002 15:17:10 - 1.1.2.1
+++ Node.java 5 Nov 2002 14:42:36 - 1.1.2.2
@@ -50,8 +50,8 @@
public class Node implements Cloneable {
-private Tree tree;
-private Node parent;
+protected Tree tree;
+protected Node parent;
private ArrayList children; // ArrayList of Node
/** Creation size of the children ArrayList. */
private static final int FAMILYSIZE = 4;
@@ -144,8 +144,8 @@
* Appends a child Node to this node. Synchronized on the
* containing Tree object.
*
- * Calls the modified method of the containing Tree to
- * maintain the value of modCount.
+ * Calls the modified method of the containing Tree to
+ * maintain the value of modCount.
*
* @param child Node to be added.
*/
@@ -164,8 +164,8 @@
* position.
* Synchronized on the containing Tree object.
*
- * Calls the modified method of the containing Tree to
- * maintain the value of modCount.
+ * Calls the modified method of the containing Tree to
+ * maintain the value of modCount.
*
* @param index int position of new child
* @param child Node to be added.
@@ -182,6 +182,51 @@
}
/**
+ * Insert a subtree at a specified index position in the child list.
+ * Takes advantage of the synchronization on the associated Tree
+ * object of the actual addChild call.
+ * Calls the modified method of the tree to maintain the
+ * value of modCount.
+ */
+public void addSubTree(int index, Node subtree)
+throws IndexOutOfBoundsException
+{
+// The subtree must be traversed, and the tree references set
+// to the Tree of this node.
+subtree.setSubTreeTree(tree);
+subtree.setParent(this);
+addChild(index, subtree);
+}
+
+/**
+ * Add a subtree to the child list.
+ * Takes advantage of the synchronization on the associated Tree
+ * object of the actual addChild call.
+ * Calls the modified method of the tree to maintain the
+ * value of modCount.
+ */
+public void addSubTree(Node subtree)
+throws IndexOutOfBoundsException
+{
+// The subtree must be traversed, and the tree references set
+// to the Tree of this node.
+subtree.setSubTreeTree(tree);
+subtree.setParent(this);
+addChild(subtree);
+}
+
+/**
+ * Set all of the tree references in a subtree to the given
+ * value.
+ * @param tree - the reference to set.
+ */
+public void setSubTreeTree(Tree tree) {
+for (int i = 0; i < numChildren(); i++)
+getChild(i).setSubTreeTree(tree);
+this.tree = tree;
+}
+
+/**
* Copies a subtree of this tree as a new child of this node.
* Synchronized on the containing Tree object.
*
@@ -341,65 +386,156 @@
/**
* Deletes the entire subtree rooted on this from the
- * Tree. The Tree is
- * traversed in PostOrder, and each Node is removed in PostOrder.
+ * Tree. The Tree is traversed in PostOrder, and each
+ * encountered Node has its Tree reference
+ * nullified. The parent field, and the parent's child reference
+ * to this, are nullified only at the top of the subtree.
+ * As a result, any remaining reference to any element in the
+ * subtree will keep the whole subtree from being GCed.
* @return int count of Nodes deleted.
*/
public int deleteSubTree() {
synchronized (tree) {
+Tree ttree = tree;
int count = delete(this);
-tree.modified();
+// At this point, the tree reference has been nullified.
+// nullify the parent reference
+if (ttree.getRoot() != this) {
+// Not the root node
cvs commit: xml-fop/src/org/apache/fop/datastructs Node.java TreeException.java Tree.java
pbwest 2002/11/04 07:17:10
Modified:src/org/apache/fop/datastructs Tag: FOP_0-20-0_Alt-Design
Tree.java
Added: src/org/apache/fop/datastructs Tag: FOP_0-20-0_Alt-Design
Node.java TreeException.java
Log:
Node and TreeException externalised from Tree.
Revision ChangesPath
No revision
No revision
1.1.2.3 +48 -967 xml-fop/src/org/apache/fop/datastructs/Attic/Tree.java
Index: Tree.java
===
RCS file: /home/cvs/xml-fop/src/org/apache/fop/datastructs/Attic/Tree.java,v
retrieving revision 1.1.2.2
retrieving revision 1.1.2.3
diff -u -r1.1.2.2 -r1.1.2.3
--- Tree.java 24 Oct 2002 14:16:53 - 1.1.2.2
+++ Tree.java 4 Nov 2002 15:17:10 - 1.1.2.3
@@ -9,40 +9,18 @@
package org.apache.fop.datastructs;
-import java.util.ArrayList;
-import java.util.ConcurrentModificationException;
-import java.util.NoSuchElementException;
-import java.util.Iterator;
-import java.util.ListIterator;
-
-// TODO:
-// Should I provide a separate or supplementary exception for CoMods appends
-// on the trailing edge of the tree? I.e., for each append, check if it is an
-// append to a node which is the final sibling at any level of the tree.
-// If so, set a copy the modCount value as the trailingEdgeModAge.
-// If a ConcurrentModificationException is about to be thrown, check whether
-// the trailingEdgeModAge is the same as the modCount. If so, throw a
-// ConcurrentTreeAppendException instead. Probably, make that a subclass of
-// ConcurrentModificationException so that the check can be done on the
-// catch of the CoModEx.
/**
- * A generalised tree class with traversal Iterators.
+ * A generalised tree class.
*
* 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.
+ * 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.
+ * elements.
*
* @author mailto:pbwest@;powerup.com.au">Peter B. West
* @version $Revision$ $Name$
@@ -56,9 +34,16 @@
* AbstractList.
*/
protected int modCount = 0;
+
+/**
+ * Count of the nodes in this tree.
+ */
protected int nodeCount = 0;
-protected Node root;
+/**
+ * The root node of this tree.
+ */
+protected Node root = null;
public Tree() {}
@@ -71,970 +56,66 @@
}
}
+/**
+ * Get the value of the modCount field, used to warn of concurrent
+ * modification of the tree during certain unsynchronized operations.
+ * @return - the int modCount.
+ */
public int getModCount() {
synchronized (this) {
return modCount;
}
}
+/**
+ * Test the modCount field value.
+ * @param value - the value to test against modCount.
+ * @return boolean test result.
+ */
public boolean modCountEqualTo(int value) {
synchronized (this) {
return value == modCount;
}
}
+/**
+ * Get the number of nodes in the tree.
+ * @return the number of nodes.
+ */
public int size() {
return nodeCount;
}
+/**
+ * Is the tree empty?
+ * @return boolean answer to the question. Tests whether the
+ * root node is null.
+ */
public boolean isEmpty() {
-return nodeCount == 0;
+return root == null;
}
-public Node getRoot() {
-return root;
-}
-
-public void unsetRoot() {
-root = null;
+/**
+ * Set the root field.
+ * @param root the Node which is to be the root of the tree.
+ */
+public void setRoot(Node root) {
+this.root = root;
}
-
-public class TreeException extends Exception {
-public TreeException(String message) {
-super(message);
-}
-
+/**
+ * Get the root node of the tree.
+ * @return the root Node.
+ */
+public Node getRoot() {
+return root;
}
/**
- * Member class Node of class Tree provides the
