From aed2f710bc397ea7e7243512d40770ee61adf4ee Mon Sep 17 00:00:00 2001 From: Peter Bernard West Date: Thu, 29 Jan 2004 02:53:37 +0000 Subject: [PATCH] Added: getPrecedingSibling getFollowingSibling precedingLeaf followingLeaf to support resolution of keeps and space-specifiers. git-svn-id: https://svn.apache.org/repos/asf/xmlgraphics/fop/branches/FOP_0-20-0_Alt-Design@197284 13f79535-47bb-0310-9956-ffa450edef68 --- src/java/org/apache/fop/datastructs/Node.java | 161 ++++++++++++++++-- 1 file changed, 151 insertions(+), 10 deletions(-) diff --git a/src/java/org/apache/fop/datastructs/Node.java b/src/java/org/apache/fop/datastructs/Node.java index d05f23955..ee48219c1 100644 --- a/src/java/org/apache/fop/datastructs/Node.java +++ b/src/java/org/apache/fop/datastructs/Node.java @@ -181,7 +181,7 @@ public class Node implements Cloneable { } /** - * Insert a subtree at a specified index position in the child list. + * Inserts a subtree at a specified index position in the child list. * @param index position of subtree within children * @param subtree to insert * @throws IndexOutOfBoundsException @@ -194,7 +194,7 @@ public class Node implements Cloneable { } /** - * Add a subtree to the child list. + * Adds a subtree to the child list. * @param subtree to insert * @throws IndexOutOfBoundsException */ @@ -382,7 +382,7 @@ public class Node implements Cloneable { } /** - * Delete this subtree and return a count of the deleted + * Deletes this subtree and returns a count of the deleted * nodes. The deletion is effected by cutting the references between * this and its parent (if any). All other relationships * within the subtree are maintained. @@ -430,7 +430,7 @@ public class Node implements Cloneable { } /** - * Get the parent of this Node. + * Gets the parent of this Node. * @return the parent Node. */ public Node getParent() { @@ -443,7 +443,7 @@ public class Node implements Cloneable { } /** - * Set the parent field of this node. + * Sets the parent field of this node. * @param parent the reference to set */ public void setParent(Node parent) { @@ -457,7 +457,7 @@ public class Node implements Cloneable { } /** - * Nullify the parent Node of this node. + * Nullifies the parent Node of this node. */ public void unsetParent() { if (synchronize) { @@ -469,7 +469,7 @@ public class Node implements Cloneable { } /** - * Get the n'th child of this node. + * Gets the n'th child of this node. * @param n - the int index of the child to return. * @return the Node reference to the n'th child. */ @@ -485,7 +485,7 @@ public class Node implements Cloneable { } /** - * Get an Iterator over the children of this node. + * Gets an Iterator over the children of this node. * @return the Iterator. */ public Iterator nodeChildren() { @@ -500,7 +500,7 @@ public class Node implements Cloneable { } /** - * Get the number of children of this node. + * Gets the number of children of this node. * @return the int number of children. */ public int numChildren() { @@ -513,7 +513,148 @@ public class Node implements Cloneable { if (children == null) return 0; return children.size(); } - + + /** + * Gets the preceding sibling of this Node, + * or null if none. + * @return the sibling node + */ + public Node getPrecedingSibling() { + if (synchronize) { + synchronized (this) { + if (this.parent == null) return null; + int thisChild = parent.children.indexOf(this); + if (thisChild == 0) return null; + return parent.getChild(--thisChild); + } + } + if (this.parent == null) return null; + int thisChild = parent.children.indexOf(this); + if (thisChild == 0) return null; + return parent.getChild(--thisChild); + } + + /** + * Gets the following sibling of this Node, + * or null if none. + * @return the sibling node + */ + public Node getFollowingSibling() { + if (synchronize) { + synchronized (this) { + if (this.parent == null) return null; + int thisChild = parent.children.indexOf(this); + if (++thisChild >= parent.numChildren()) return null; + return parent.getChild(thisChild); + } + } + if (this.parent == null) return null; + int thisChild = parent.children.indexOf(this); + if (++thisChild >= parent.numChildren()) return null; + return parent.getChild(thisChild); + } + + /** + * Gets the leaf Node immediately preceding this node in the + * pre-order tree rooted on the nominalRoot, or, if the + * nominal root is not encountered, the actual root. + * In a pre-order tree, all children follow their parent. + * @param nominalRoot the root node for the purposes of this operation + * @return the preceding leaf node or null + */ + public Node precedingLeaf(Node nominalRoot) { + if (synchronize) { + synchronized (this) { + return getPrecedingLeaf(nominalRoot); + } + } + return getPrecedingLeaf(nominalRoot); + } + + /** + * Realizes precedingLeaf(). Climbs the tree rooted at + * nominalRoot from this, searching for an + * ancestor with a branch preceding this. + * If none is found, there is no preceding leaf node. + * If one is found, it is descended to the last pre-order node, + * i.e. the leaf most closely preceding this. + * @param nominalRoot the root node for the purposes of this operation + * @return the preceding leaf node or null + */ + private Node getPrecedingLeaf(Node nominalRoot) { + if (this == nominalRoot || this.parent == null) { + return null; + } + Node sibling = null; + Node pivot = this.parent; + while (pivot != nominalRoot) { + if ((sibling = pivot.getPrecedingSibling()) != null) { + break; + } + pivot = pivot.parent; + } + if (pivot == nominalRoot) { // No preceding leaf node + return null; + } + // We have the pivot preceding sibling - now descend the + // preceding subtree to the last leaf + int numChildren; + while ((numChildren = sibling.numChildren()) > 0) { + sibling = sibling.getChild(--numChildren); + } + return sibling; + } + + /** + * Gets the leaf Node immediately following this node in the + * post-order tree rooted on the nominalRoot, or, if the + * nominal root is not encountered, the actual root. + * In a post-order tree, all children precede their parent. + * @param nominalRoot the root node for the purposes of this operation + * @return the following leaf node or null + */ + public Node followingLeaf(Node nominalRoot) { + if (synchronize) { + synchronized (this) { + return getFollowingLeaf(nominalRoot); + } + } + return getFollowingLeaf(nominalRoot); + } + + /** + * Realizes followingLeaf(). Climbs the tree rooted at + * nominalRoot from this, searching for an + * ancestor with a branch following this. + * If none is found, there is no following leaf node. + * If one is found, it is descended to the first post-order node, + * i.e. the leaf most closely following this. + * @param nominalRoot the root node for the purposes of this operation + * @return the following leaf node or null + */ + private Node getFollowingLeaf(Node nominalRoot) { + if (this == nominalRoot || this.parent == null) { + return null; + } + Node sibling = null; + Node pivot = this.parent; + while (pivot != nominalRoot) { + if ((sibling = pivot.getFollowingSibling()) != null) { + break; + } + pivot = pivot.parent; + } + if (pivot == nominalRoot) { // No preceding leaf node + return null; + } + // We have the pivot following sibling - now descend the + // following subtree to the first leaf + while (sibling.numChildren() > 0) { + sibling = sibling.getChild(0); + } + return sibling; + } + /** * Class PreOrder is a member class of Node. * -- 2.39.5