[FOray-commit] SF.net SVN: foray:[11540] trunk/foray/foray-common/src
Modular XSL-FO Implementation for Java.
Status: Alpha
Brought to you by:
victormote
|
From: <vic...@us...> - 2019-03-23 01:09:46
|
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.
|