foray-commit Mailing List for FOray (Page 79)

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Revision: 11920
          http://sourceforge.net/p/foray/code/11920
Author:   victormote
Date:     2021-10-23 15:03:35 +0000 (Sat, 23 Oct 2021)
Log Message:
-----------
Steps toward an improved node iterator.

Modified Paths:
--------------
    trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java
    trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java

Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java
===================================================================

--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java	2021-10-23 14:54:38 UTC (rev 11919)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java	2021-10-23 15:03:35 UTC (rev 11920)
@@ -29,6 +29,7 @@
 package org.foray.common.data;
 
 import org.foray.common.primitive.CharacterUtils;
+import org.foray.common.sequence.CharArrayBuilder;
 import org.foray.common.sequence.IntArrayBuilder;
 
 import org.slf4j.Logger;
@@ -113,7 +114,7 @@
 
         /** Format string for {@link #toString()}. */
         private static final String TO_STRING_FORMAT =
-                "index: %5d,   low: %5d,   equal: %5d,   high: %5d,   key: %4x  %s, parent: %5d";
+                "index: %5d,   low: %5d,   equal: %5d,   high: %5d,   key char: %4x  %s, parent: %5d, key: %6s";
 
         /** The index for this node. */
         private int index;
@@ -133,17 +134,22 @@
         /** The index to the parent of this node. */
         private int parent = -1;
 
+        /** The key, i.e. the cumulative keyChar items for this node. */
+        private CharSequence key;
+
         /**
          * Constructor.
          * @param index The index for which a notional nodes is wanted.
+         * @param key The cumulative keyChar for this node.
          * @param withParents The {@link TernaryNodes.WithParents} instance. This can be null.
          */
-        public Node(final int index, final WithParents withParents) {
+        public Node(final int index, final CharSequence key, final WithParents withParents) {
             this.index = index;
             this.low = TernaryNodes.this.getLow(index);
             this.equal = TernaryNodes.this.getEqual(index);
             this.high = TernaryNodes.this.getHigh(index);
             this.keyChar = TernaryNodes.this.getKeyChar(index);
+            this.key = key;
             if (withParents != null) {
                 this.parent = withParents.getParent(index);
             }
@@ -197,6 +203,14 @@
             return this.parent;
         }
 
+        /**
+         * Returns the key.
+         * @return The key. This can be null if the node was not created by the iterator.
+         */
+        public CharSequence getKey() {
+            return this.key;
+        }
+
         @Override
         public String toString() {
             char printableChar = this.keyChar;
@@ -205,7 +219,8 @@
                 printableChar = ' ';
             }
             return String.format(TO_STRING_FORMAT,
-                  this.index, this.low, this.equal, this.high, (int) this.keyChar, printableChar, this.parent);
+                  this.index, this.low, this.equal, this.high, (int) this.keyChar, printableChar, this.parent,
+                  this.key);
         }
 
         @Override
@@ -229,7 +244,7 @@
     }
 
     /**
-     * Iterates over the nodes in depth-first order, going now first the left branch, then the equal branch, then the
+     * Iterates over the nodes in depth-first order, going first to the low branch, then the equal branch, then the
      * high branch.
      */
     public class DepthFirstIterator implements Iterator<TernaryNodes.Node> {
@@ -238,11 +253,16 @@
          * the top. */
         private IntArrayBuilder currentIndexStack = new IntArrayBuilder();
 
-        /** Parallel stack to indexStack -- this should always have the same number of element in it as indexStack.
+        /** Parallel stack to indexStack -- this should always have the same number of elements in it as indexStack.
          * This keeps track of which branch of the related index is being processed.
          * Low is -1, equal is 0, and high is +1. */
         private IntArrayBuilder currentBranchStack = new IntArrayBuilder();
 
+        /** Parallel stack to indexStack -- this should always have the same number of elements in it as indexStack.
+         * This keeps track of the "word" (sequence of characters) represented by the current location of the
+         * iterator. */
+        private CharArrayBuilder charStack = new CharArrayBuilder();
+
         /** The next index to return. */
         private int nextIndex = Integer.MIN_VALUE;
 
@@ -254,6 +274,7 @@
                 this.currentIndexStack.push(1);
                 this.nextIndex = 1;
                 this.currentBranchStack.push(-1 - 1);
+                this.charStack.push(TernaryNodes.this.keyChar[1]);
             }
         }
 
@@ -264,7 +285,9 @@
 
         @Override
         public Node next() {
-            final int returnValue = this.nextIndex;
+            final Node returnValue = new Node(this.nextIndex, this.charStack.toString(), null);
+
+            /* Tee up the one after this, if any. */
             this.nextIndex = -1;
 
             indexLoop:
@@ -298,6 +321,7 @@
                         /* Push the found index onto the stack. */
                         this.currentIndexStack.push(branchIndex);
                         this.currentBranchStack.push(-1 - 1);
+                        this.charStack.push(TernaryNodes.this.keyChar[branchIndex]);
                         /* The new index is the next item to be processed. */
                         this.nextIndex = branchIndex;
                         break indexLoop;
@@ -307,12 +331,13 @@
                         this.currentBranchStack.push(currentBranch);
                     }
                 }
-                /* We have processed all of the branches on the current index. Pop both stacks. */
+                /* We have processed all of the branches on the current index. Pop all stacks. */
                 this.currentIndexStack.pop();
                 this.currentBranchStack.pop();
+                this.charStack.pop();
             }
 
-            return new Node(returnValue, null);
+            return returnValue;
         }
 
         @Override
@@ -612,11 +637,12 @@
      * Use the getters and setters for ordinary processing.
      * It is expected that this method should be used ONLY for testing and iteration.
      * @param index The index to the node.
+     * @param key The chars making up the key to the node. This can be null.
      * @param withParents An optional {@link TernaryNodes.WithParents}. This can be null.
      * @return A new Node instance containing the data for the reqested node.
      */
-    Node createNotionalNode(final int index, final WithParents withParents) {
-        return new Node(index, withParents);
+    Node createNotionalNode(final int index, final CharSequence key, final WithParents withParents) {
+        return new Node(index, key, withParents);
     }
 
     /**
@@ -747,7 +773,7 @@
             this.logger.error("Inconsistent Tree", e);
         }
         for (int index = 0; index < size(); index ++) {
-            final Node node = createNotionalNode(index, withParents);
+            final Node node = createNotionalNode(index, null, withParents);
             this.logger.info(node.toString());
         }
         this.logger.info("-----------------------------------------------------------------------------------------");

Modified: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java	2021-10-23 14:54:38 UTC (rev 11919)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java	2021-10-23 15:03:35 UTC (rev 11920)
@@ -259,7 +259,7 @@
      */
     private void testNode(final TernaryTree map, final int index, final int expectedLow, final int expectedEqual,
             final int expectedHigh, final char expectedKeyChar) {
-        final TernaryNodes.Node node = map.getNodes().createNotionalNode(index, null);
+        final TernaryNodes.Node node = map.getNodes().createNotionalNode(index, null, null);
         Assert.assertEquals(index,           node.getIndex());
         Assert.assertEquals(expectedLow,     node.getLow());
         Assert.assertEquals(expectedEqual,   node.getEqual());
@@ -278,7 +278,7 @@
      */
     private void testNode(final TernaryNodes nodes, final int index, final int expectedLow, final int expectedEqual,
             final int expectedHigh, final char expectedKeyChar) {
-        final TernaryNodes.Node node =       nodes.createNotionalNode(index, null);
+        final TernaryNodes.Node node =       nodes.createNotionalNode(index, null, null);
         Assert.assertEquals(index,           node.getIndex());
         Assert.assertEquals(expectedLow,     node.getLow());
         Assert.assertEquals(expectedEqual,   node.getEqual());

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





2006	Jan	Feb	Mar (139)	Apr (98)	May (250)	Jun (394)	Jul (84)	Aug (13)	Sep (420)	Oct (186)	Nov (1)	Dec (3)
2007	Jan (108)	Feb (202)	Mar (291)	Apr (247)	May (374)	Jun (227)	Jul (231)	Aug (60)	Sep (31)	Oct (45)	Nov (18)	Dec
2008	Jan (38)	Feb (71)	Mar (142)	Apr	May (59)	Jun (6)	Jul (10)	Aug	Sep	Oct	Nov	Dec
2009	Jan (12)	Feb (4)	Mar (88)	Apr (121)	May (17)	Jun (30)	Jul	Aug (5)	Sep	Oct (1)	Nov	Dec
2010	Jan (11)	Feb (76)	Mar (11)	Apr	May (11)	Jun	Jul	Aug (44)	Sep (14)	Oct (7)	Nov	Dec
2011	Jan	Feb	Mar	Apr	May (9)	Jun	Jul	Aug	Sep	Oct (10)	Nov	Dec
2012	Jan	Feb	Mar	Apr	May	Jun (3)	Jul (4)	Aug	Sep	Oct	Nov	Dec
2016	Jan	Feb	Mar	Apr	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec (168)
2017	Jan (77)	Feb (11)	Mar	Apr	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec
2018	Jan	Feb	Mar (1)	Apr (6)	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec
2019	Jan	Feb (88)	Mar (118)	Apr (1)	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec
2020	Jan	Feb	Mar	Apr	May (6)	Jun	Jul	Aug	Sep	Oct	Nov	Dec (141)
2021	Jan (170)	Feb (20)	Mar	Apr	May	Jun	Jul (1)	Aug	Sep	Oct (62)	Nov (189)	Dec (162)
2022	Jan (201)	Feb (118)	Mar (8)	Apr	May (2)	Jun (47)	Jul (19)	Aug (14)	Sep (3)	Oct	Nov (28)	Dec (235)
2023	Jan (112)	Feb (23)	Mar (2)	Apr (2)	May	Jun (1)	Jul	Aug (70)	Sep (92)	Oct (20)	Nov (1)	Dec (1)
2024	Jan	Feb	Mar (1)	Apr (1)	May (14)	Jun (11)	Jul (1)	Aug	Sep	Oct	Nov	Dec
2025	Jan (10)	Feb (29)	Mar	Apr (162)	May (245)	Jun (83)	Jul	Aug (1)	Sep	Oct	Nov (4)	Dec

foray-commit Mailing List for FOray (Page 79)

Modular XSL-FO Implementation for Java.

foray-commit — FOray repository commit log messages