[FOray-commit] SF.net SVN: foray:[11540] trunk/foray/foray-common/src

Revision: 11540
          http://sourceforge.net/p/foray/code/11540
Author:   victormote
Date:     2019-03-23 01:09:37 +0000 (Sat, 23 Mar 2019)
Log Message:
-----------
Add tests and test-oriented helper code. Rewrite the TernaryTree getter logic.

Modified Paths:
--------------
    trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java
    trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesChar.java
    trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesInt.java
    trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.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	2019-03-22 16:41:53 UTC (rev 11539)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java	2019-03-23 01:09:37 UTC (rev 11540)
@@ -28,6 +28,9 @@
 
 package org.foray.common.data;
 
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
 import java.io.Serializable;
 import java.util.Arrays;
 
@@ -48,6 +51,9 @@
     /** Allocation size for arrays. */
     public static final int DEFAULT_BLOCK_SIZE = 2048;
 
+    /** The index to the root node. */
+    public static final int ROOT_NODE_INDEX = 1;
+
     /** SWAG of the maximum number of key-value pairs that can be stored in a nodes structure that uses chars for the
      * index storage. This may be used by applications that need to guess which {@link TernaryNodes} implementation to
      * choose. */
@@ -119,8 +125,13 @@
 
         @Override
         public String toString() {
-          return String.format("index: %5d,   low: %5d,   equal: %5d,   high: %5d,   key: %4x",
-                  this.index, this.low, this.equal, this.high, (int) this.keyChar);
+            char printableChar = this.keyChar;
+            if (printableChar < ' '
+                    || printableChar == Character.MAX_VALUE) {
+                printableChar = ' ';
+            }
+            return String.format("index: %5d,   low: %5d,   equal: %5d,   high: %5d,   key: %4x  %s",
+                  this.index, this.low, this.equal, this.high, (int) this.keyChar, printableChar);
         }
 
         @Override
@@ -328,7 +339,7 @@
             /* If we haven't created any nodes, yet, this is a special case. */
             return 0;
         }
-        return 1;
+        return ROOT_NODE_INDEX;
     }
 
     /**
@@ -344,9 +355,9 @@
      * @return The index to the new node.
      */
     int createNode() {
-        if (this.freenode >= Character.MAX_VALUE) {
+        if (this.freenode >= getMaximumCapacity()) {
             throw new IllegalStateException("Node capacity of " + this.getClass().getName() + " is limited to "
-                    + Integer.toString(Character.MAX_VALUE + 1));
+                    + getMaximumCapacity());
         }
         final int newNode = this.freenode;
         this.freenode ++;
@@ -353,4 +364,103 @@
         return newNode;
     }
 
+    /**
+     * Indicates whether a given node is a compressed node.
+     * @param index The index of the node to be tested.
+     * @return True if and only if the node is a compressed node.
+     */
+    boolean isCompressedNode(final int index) {
+        return getKeyChar(index) == Character.MAX_VALUE;
+    }
+
+    /**
+     * Indicates whether a given node is a terminating node.
+     * @param index The index of the node to be tested.
+     * @return True if and only if the node is a terminating node.
+     */
+    boolean isTerminatingNode(final int index) {
+        return getKeyChar(index) == Character.MIN_VALUE;
+    }
+
+    /**
+     * Indicates whether a given node has a key value equal to a specified char.
+     * @param index The index of the node to be tested.
+     * @param theChar The character being sought in the tree.
+     * @return True if and only if the node is an uncompressed node matching the {@code theChar}.
+     */
+    boolean isCharNode(final int index, final char theChar) {
+        return getKeyChar(index) == theChar;
+    }
+
+    /**
+     * Recursively finds the descendant-or-self node that matches a given char, starting at a given index.
+     * If a compressed branch is reached in the search, that branch index is returned.
+     * Please note that it may or may not match the string being sought.
+     * It is the responsibility of client code to determine whether the compressed branch should be used or not.
+     * @param startingIndex The index of the node at which the search should begin.
+     * Presumably, this should either be the {@link #ROOT_NODE_INDEX}, or the {@link #getEqual(int)} value from a
+     * previously-found node.
+     * @param theChar The character being sought in the tree.
+     * @return Either {@code startingIndex}, the index to one of its descendants, or -1 if no match is found.
+     */
+    int findCharNode(final int startingIndex, final char theChar) {
+        if (startingIndex < 1) {
+            /* We are at index 0, which points nowhere. */
+            return -1;
+        }
+
+        final char keyChar = getKeyChar(startingIndex);
+
+        /* If the character at startingIndex marks a compressed branch return it. */
+        if (keyChar == Character.MAX_VALUE) {
+            return startingIndex;
+        }
+
+        /* Pick which of the three branches to follow. */
+        final int difference = theChar - keyChar;
+        if (difference == 0) {
+            return startingIndex;
+        }
+        if (difference < 0) {
+            return findCharNode(getLow(startingIndex), theChar);
+        }
+        /* difference > 0. */
+        return findCharNode(getHigh(startingIndex), theChar);
+    }
+
+    /**
+     * Returns the highest index whose node has values in it.
+     * Useful mainly for testing the value in {@link #freenode}.
+     * @return The highest index whose node has value.
+     */
+    int getLastNonNullIndex() {
+        for (int index = this.keyChar.length - 1; index > -1; index --) {
+            if (this.keyChar[index] != 0
+                    || getLow(index) != 0
+                    || getEqual(index) != 0
+                    || getHigh(index) != 0) {
+                return index;
+            }
+        }
+        return -1;
+    }
+
+    /**
+     * Dumps the content of the tree to a logger.
+     * Useful for tests.
+     */
+    public void dumpTree() {
+        final Logger logger = LoggerFactory.getLogger(this.getClass());
+        for (int index = 0; index < this.length(); index ++) {
+            final Node node = createNotionalNode(index);
+            logger.info(node.toString());
+        }
+    }
+
+    /**
+     * Returns the maximum capacity of this data structure.
+     * @return The maximum capacity of this data structure.
+     */
+    public abstract int getMaximumCapacity();
+
 }

Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesChar.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesChar.java	2019-03-22 16:41:53 UTC (rev 11539)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesChar.java	2019-03-23 01:09:37 UTC (rev 11540)
@@ -105,4 +105,9 @@
         this.equal = Arrays.copyOf(this.equal, newSize);
     }
 
+    @Override
+    public int getMaximumCapacity() {
+        return Character.MAX_VALUE;
+    }
+
 }

Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesInt.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesInt.java	2019-03-22 16:41:53 UTC (rev 11539)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesInt.java	2019-03-23 01:09:37 UTC (rev 11540)
@@ -105,4 +105,9 @@
         this.equal = Arrays.copyOf(this.equal, newSize);
     }
 
+    @Override
+    public int getMaximumCapacity() {
+        return Integer.MAX_VALUE;
+    }
+
 }

Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java	2019-03-22 16:41:53 UTC (rev 11539)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java	2019-03-23 01:09:37 UTC (rev 11540)
@@ -422,35 +422,34 @@
     int getNodeIndex(final CharSequence key, final int start, final int end) {
         int currentNodeIndex = this.nodes.getRootNodeIndex();
         int i = start;
-        char c;
 
-        while (currentNodeIndex != 0) {
-            if (this.nodes.getKeyChar(currentNodeIndex) == Character.MAX_VALUE) {
+        while (i < end) {
+            final char c = key.charAt(i);
+            final int charNodeIndex = this.nodes.findCharNode(currentNodeIndex, c);
+            if (charNodeIndex < 0) {
+                return -1;
+            }
+
+            if (this.nodes.isCompressedNode(charNodeIndex)) {
                 if (CharSequenceUtils.compareNullTerminated(
-                        this.compressedKeys, this.nodes.getLow(currentNodeIndex), key, i, end) == 0) {
-                    return currentNodeIndex;
+                        this.compressedKeys, this.nodes.getLow(charNodeIndex), key, i, end) == 0) {
+                    return charNodeIndex;
                 }
                 return -1;
             }
-            if (i >= end) {
-                /* If we are past the end of the key, then pretend like we have a
-                 * null-terminator. */
-                c = 0;
-            } else {
-                c = key.charAt(i);
-            }
-            final int difference = c - this.nodes.getKeyChar(currentNodeIndex);
-            if (difference == 0) {
-                if (c == 0) {
-                    return currentNodeIndex;
+
+            /* If we are at the end of the word, see if there is a terminating node for it. */
+            if (i == end - 1) {
+                final int targetNodeIndex = this.nodes.getEqual(charNodeIndex);
+                if (this.nodes.isTerminatingNode(targetNodeIndex)) {
+                    return targetNodeIndex;
                 }
-                i++;
-                currentNodeIndex = this.nodes.getEqual(currentNodeIndex);
-            } else if (difference < 0) {
-                currentNodeIndex = this.nodes.getLow(currentNodeIndex);
-            } else {
-                currentNodeIndex = this.nodes.getHigh(currentNodeIndex);
+                return -1;
             }
+
+            currentNodeIndex = this.nodes.getEqual(charNodeIndex);
+            i++;
+
         }
         return -1;
     }

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	2019-03-22 16:41:53 UTC (rev 11539)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java	2019-03-23 01:09:37 UTC (rev 11540)
@@ -192,13 +192,13 @@
     @Test
     public void testPut01() {
         final TernaryTree map = new TernaryTree(new TernaryNodesChar());
-        map.put("40", '1');
-        map.put("45", '2');
-        map.put("4", '3');
+        map.put("40", 1);
+        map.put("45", 2);
+        map.put("4", 3);
 
-        Assert.assertEquals('1', (char) map.get("40"));
-        Assert.assertEquals('2', (char) map.get("45"));
-        Assert.assertEquals('3', (char) map.get("4"));
+        Assert.assertEquals(1, map.get("40"));
+        Assert.assertEquals(2, map.get("45"));
+        Assert.assertEquals(3, map.get("4"));
     }
 
     /** Test of retrieving the value for a key that is not in the map. */
@@ -315,4 +315,54 @@
         Assert.assertEquals(9, map.getNodeIndex("sup", 0, "sup".length()));
     }
 
+    /**
+     * Test of {@link TernaryNodes#findCharNode(int, char)}.
+     */
+    @SuppressWarnings("javadoc")
+    @Test
+    public void testFindCharNode() {
+        final TernaryTree map = new TernaryTree(new TernaryNodesChar());
+        map.put("bread", 1);
+        map.put("brave", 2);
+        map.put("bravo", 3);
+        map.put("braver", 4);
+        map.put("bravery", 5);
+
+        Assert.assertEquals(13, map.getNodes().getNodeCount());
+        testNode(map,  0,  0,  0,  0, Character.MIN_VALUE);
+        testNode(map,  1,  0,  2,  0, 'b');
+        testNode(map,  2,  0,  3,  0, 'r');
+        testNode(map,  3,  5,  4,  0, 'e');
+        testNode(map,  4,  3,  1,  0, Character.MAX_VALUE);
+        testNode(map,  5,  0,  6,  0, 'a');
+        testNode(map,  6,  0,  7,  0, 'v');
+        testNode(map,  7,  0,  8,  9, 'e');
+        testNode(map,  8,  0,  2, 10, Character.MIN_VALUE);
+        testNode(map,  9, 10,  3,  0, Character.MAX_VALUE);
+        testNode(map, 10,  0, 11,  0, 'r');
+        testNode(map, 11,  0,  4, 12, Character.MIN_VALUE);
+        testNode(map, 12, 14,  5,  0, Character.MAX_VALUE);
+        Assert.assertEquals("bread\u0000ave\u0000o\u0000r\u0000y\u0000", map.getCompressedKeys());
+
+        Assert.assertEquals(1, map.getNodes().findCharNode(1, 'b'));
+        Assert.assertEquals(-1, map.getNodes().findCharNode(1, 'q'));
+
+        /* Find the 'a' in "bravo". We have already found "br", and therefore start at the equal branch of "r". */
+        Assert.assertEquals(5, map.getNodes().findCharNode(3, 'a'));
+        /* Find the 'v' in "bravo". We have already found "bra", and therefore start at the equal branch of "a". */
+        Assert.assertEquals(6, map.getNodes().findCharNode(6, 'v'));
+        /* Find the 'o' in "bravo". We have already found "brav", and therefore start at the equal branch of "v". */
+        Assert.assertEquals(9, map.getNodes().findCharNode(7, 'o'));
+
+        /* Find the 'e' in "brave". We have already found "brav", and therefore start at the equal branch of "v". */
+        Assert.assertEquals(7, map.getNodes().findCharNode(7, 'e'));
+
+        /* Find the 'a' in "bread". We have already found "bre", and therefore start at the equal branch of "e". */
+        Assert.assertEquals(4, map.getNodes().findCharNode(4, 'a'));
+
+        /* Find the second 'r' in "braver" and "bravery". We have already found "brave", and therefore start at the
+         * equal branch of "e". */
+        Assert.assertEquals(10, map.getNodes().findCharNode(8, 'r'));
+    }
+
 }

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