[FOray-commit] SF.net SVN: foray: [9668] trunk/foray

[<vic...@us...>]

Revision: 9668
          http://svn.sourceforge.net/foray/?rev=9668&view=rev
Author:   victormote
Date:     2007-05-30 13:30:23 -0700 (Wed, 30 May 2007)

Log Message:
-----------
Add and use a post-order node iterator to find the descendant leader instances.

Modified Paths:
--------------
    trunk/foray/foray-areatree/src/java/org/foray/area/LineArea.java
    trunk/foray/foray-common/src/java/org/foray/common/OrderedTreeNode.java

Modified: trunk/foray/foray-areatree/src/java/org/foray/area/LineArea.java
===================================================================
--- trunk/foray/foray-areatree/src/java/org/foray/area/LineArea.java	2007-05-30 19:14:25 UTC (rev 9667)
+++ trunk/foray/foray-areatree/src/java/org/foray/area/LineArea.java	2007-05-30 20:30:23 UTC (rev 9668)
@@ -28,6 +28,8 @@
 
 package org.foray.area;
 
+import org.foray.common.OrderedTreeNode;
+
 import org.axsl.areaR.RenderVisitor;
 import org.axsl.areaW.AreaWException;
 import org.axsl.common.value.AbsoluteAxis;
@@ -53,6 +55,7 @@
 import org.axsl.fontR.Font;
 
 import java.util.ArrayList;
+import java.util.Iterator;
 import java.util.List;
 
 /**
@@ -213,8 +216,10 @@
         if (leaderSpaceAvailable == 0) {
             return;
         }
-        for (int i = 0; i < getChildren().size(); i++) {
-            final Object object = getChildren().get(i);
+        final Iterator<? extends OrderedTreeNode> iterator =
+            this.postOrderDescendantIterator();
+        while (iterator.hasNext()) {
+            final OrderedTreeNode object = iterator.next();
             if (object instanceof LeaderArea) {
                 final LeaderArea leader = (LeaderArea) object;
                 boolean prorating = false;
@@ -239,8 +244,10 @@
     private int computeLeaderCapacity(final int unusedSpace) {
         // First, compute how much capacity the leaders have.
         int leaderSpaceAvailable = 0;
-        for (int i = 0; i < getChildren().size(); i++) {
-            final Object object = getChildren().get(i);
+        final Iterator<? extends OrderedTreeNode> iterator =
+                this.postOrderDescendantIterator();
+        while (iterator.hasNext()) {
+            final OrderedTreeNode object = iterator.next();
             if (object instanceof LeaderArea) {
                 final LeaderArea leader = (LeaderArea) object;
                 if (unusedSpace > 0) {

Modified: trunk/foray/foray-common/src/java/org/foray/common/OrderedTreeNode.java
===================================================================
--- trunk/foray/foray-common/src/java/org/foray/common/OrderedTreeNode.java	2007-05-30 19:14:25 UTC (rev 9667)
+++ trunk/foray/foray-common/src/java/org/foray/common/OrderedTreeNode.java	2007-05-30 20:30:23 UTC (rev 9668)
@@ -30,17 +30,19 @@
 
 import java.util.Collections;
 import java.util.Enumeration;
+import java.util.Iterator;
 import java.util.List;
+import java.util.NoSuchElementException;
 
 import javax.swing.tree.DefaultMutableTreeNode;
 import javax.swing.tree.TreeNode;
 
 /**
- * An implementation of the TreeNode interface that provides methods for various
- * traversal needs.
+ * An implementation of the {@link TreeNode} interface that provides methods for
+ * various traversal needs.
  *
- * <p>Consideration was given to using
- * {@link DefaultMutableTreeNode} instead of creating this class.
+ * <p>Consideration was given to using {@link DefaultMutableTreeNode} instead of
+ * creating this class.
  * However, the data portion of that class was not deemed suitable.</p>
  */
 public abstract class OrderedTreeNode
@@ -60,6 +62,15 @@
     }
 
     /**
+     * Returns an iterator that will iterate the descendant nodes of this node
+     * in post-traversal (depth-first) order.
+     * @return A post-traversal iterator of this node's descendants.
+     */
+    public Iterator<? extends OrderedTreeNode> postOrderDescendantIterator() {
+        return new PostOrderDescendantIterator(this);
+    }
+
+    /**
      * Return the List of this node's children.
      * @return The List of this node's children.
      */
@@ -223,6 +234,24 @@
     }
 
     /**
+     * Returns the next node in the tree relative to the current node, in
+     * post-order traversal order. This is also known as depth-first order.
+     * @return The next post-order node, or null if there is none.
+     */
+    public OrderedTreeNode nextPostOrderNode() {
+        /* All of the children would come before this. */
+        /* If there are siblings, they or their descendants come next. */
+        final OrderedTreeNode nextSibling = this.getNextSibling();
+        if (nextSibling != null) {
+            return nextSibling.getFirstLeaf();
+        }
+        /* If there are no siblings, then the parent's children are all
+         * processed, and the parent is the next node. If that happens to be
+         * null, then we are done, and null is what should be returned. */
+        return this.getParent();
+    }
+
+    /**
      * {@inheritDoc}
      * This implementation was liberated from {@link DefaultMutableTreeNode}).
      */
@@ -412,4 +441,74 @@
         return levels;
     }
 
+    /**
+     * A post-order iterator over the descendants of a given node.
+     */
+    public final class PostOrderDescendantIterator
+            implements java.util.Iterator<OrderedTreeNode> {
+
+        /** The root node whose descendants are being iterated. */
+        private OrderedTreeNode root;
+
+        /** The next post-order node to be returned. */
+        private OrderedTreeNode nextPostOrderNode;
+
+        /**
+         * Private constructor.
+         * @param root The node whose descendants should be iterated by this
+         * iterator.
+         */
+        private PostOrderDescendantIterator(final OrderedTreeNode root) {
+            this.root = root;
+            if (root.getChildCount() < 1) {
+                this.nextPostOrderNode = null;
+            } else {
+                this.nextPostOrderNode =
+                        this.root.getFirstChild().getFirstLeaf();
+            }
+        }
+
+        /**
+         * {@inheritDoc}
+         */
+        public boolean hasNext() {
+            return this.nextPostOrderNode != null;
+        }
+
+        /**
+         * {@inheritDoc}
+         */
+        public OrderedTreeNode next() {
+            if (this.nextPostOrderNode == null) {
+                throw new NoSuchElementException("This iterator has no more "
+                        + "nodes.");
+            }
+            final OrderedTreeNode returnNode = this.nextPostOrderNode;
+            this.setNextNode();
+            return returnNode;
+        }
+
+        /**
+         * Finds and records the next node to be returned by the iterator.
+         */
+        private void setNextNode() {
+            final OrderedTreeNode provisionalNextNode =
+                    this.nextPostOrderNode.nextPostOrderNode();
+            if (provisionalNextNode.isNodeAncestor(this.root)) {
+                this.nextPostOrderNode = provisionalNextNode;
+            } else {
+                this.nextPostOrderNode = null;
+            }
+        }
+
+        /**
+         * {@inheritDoc}
+         */
+        public void remove() {
+            throw new UnsupportedOperationException("The \"remove\" operation "
+                    + "is not supported by this iterator.");
+        }
+
+    }
+
 }


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.