foray-commit Mailing List for FOray (Page 78)
Modular XSL-FO Implementation for Java.
Status: Alpha
Brought to you by:
victormote
You can subscribe to this list here.
| 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
|
|
From: <vic...@us...> - 2021-10-26 23:47:08
|
Revision: 11945
http://sourceforge.net/p/foray/code/11945
Author: victormote
Date: 2021-10-26 23:47:05 +0000 (Tue, 26 Oct 2021)
Log Message:
-----------
Improvements to spell-checker & English dictionary.
Modified Paths:
--------------
trunk/foray/foray-hyphen/src/main/data/word-lists/eng-word-list-moby.txt
trunk/foray/foray-hyphen/src/main/java/org/foray/hyphen/SpellChecker.java
Modified: trunk/foray/foray-hyphen/src/main/data/word-lists/eng-word-list-moby.txt
===================================================================
--- trunk/foray/foray-hyphen/src/main/data/word-lists/eng-word-list-moby.txt 2021-10-26 19:17:20 UTC (rev 11944)
+++ trunk/foray/foray-hyphen/src/main/data/word-lists/eng-word-list-moby.txt 2021-10-26 23:47:05 UTC (rev 11945)
@@ -37,6 +37,7 @@
# readable as the bullet symbol, and is unlikely to be used for any other purpose.
#
#
+a
a cap"pel"la
a for"ti"o"ri
a go"go
@@ -3556,6 +3557,7 @@
Al"ys
Al"y"at"tes
Al"y"son
+am
ambs"ace
ames"ace
Ames"bur"y
@@ -7839,6 +7841,7 @@
ar"y"te"noi"dal
ar"y"te"no"ep"i"glot"tic
Ar"za"chel
+as
ascetic
asdic
ash
@@ -8437,6 +8440,7 @@
as"ymp"tot"i"cal"ly
as"yn"det"ic
as"yn"det"i"cal"ly
+at
at-home
Atch"e"son
Atch"i"son
@@ -10980,6 +10984,7 @@
A"my"clas
a"my"o"to"ni"a
A"mé"dée
+an
a"na
a"nab"a"sine
a"nab"a"sis
@@ -14172,6 +14177,7 @@
bdl
BDS
bds
+be
Bea
BEA
Beach
@@ -21226,6 +21232,7 @@
BVM
bwa"na
BWG
+by
by-bid"der
by-bid"ding
by-e"lec"tion
@@ -43924,6 +43931,7 @@
Dnies"ter
Dnie"per
Dnie"ster
+do
do o"ver
do with"out
do-all
@@ -45037,6 +45045,7 @@
DPP
dpt
DPW
+Dr
drab
drab"ber
drab"best
@@ -62736,6 +62745,7 @@
GNP
gns
gnu
+go
go a"bout
go a"gainst
go a"head
@@ -67629,6 +67639,7 @@
hcf
hdbk
hdqrs
+he
he'd
he'll
he's
@@ -73530,6 +73541,7 @@
IEE
ier"pe"tra"ble
Ie"per
+if
IFC
IFS
if"fy
@@ -74697,6 +74709,7 @@
im"pu"tres"ci"ble
Im"re
Im"roz
+in
in ab"sen"ti"a
in ae"ter"num
in cam"er"a
@@ -80119,6 +80132,7 @@
I"rus
I"rène
I"r"kli"on
+is
I"s
I"saac
I"saacs
@@ -80384,6 +80398,7 @@
i"sta"na
I"sus
I"sère
+it
I"tal"ian
I"tal"ian East Af"ri"ca
I"tal"ian sixth
@@ -93241,6 +93256,7 @@
Mc"Teague
MDS
mdse
+me
me-too
me-too"ism
Mead
@@ -98470,6 +98486,7 @@
MRA
MRC
mri"dang
+Mr
Mrs
Ms-Th
MSc
@@ -99350,6 +99367,7 @@
Mwan"za
mwa"li"mu
Mwe"ru
+my
mycol
Myc"e"ri"nus
myd"ri"at"ic
@@ -101800,6 +101818,7 @@
Nnam"di
NNE
NNW
+no
no-ac"count
no-ball
no-claim bo"nus
@@ -109323,6 +109342,7 @@
op"u"lent
op"u"lent"ly
op"u"len"cy
+or
orb
orc
orch
@@ -111393,6 +111413,7 @@
o"dyl"ic
O"dys"seus
O"dys"se"us
+of
o"fay
O"gal"lal"a
O"ga"sa"wa"ra Gun"to
@@ -111538,6 +111559,7 @@
o"mo"pha"gi"a
o"mo"pho"ri"on
O"mu"ta
+on
O"na
o"nan"ism
o"nan"ist
@@ -149487,6 +149509,7 @@
sny
snye
sny"ing
+so
so-so
soak
soak"age
@@ -163046,6 +163069,7 @@
tme"sis
tng
TNT
+to
to-be
to-do
to-mor"row
@@ -178731,6 +178755,7 @@
un"zone
un"zoned
un"zon"ing
+up
up-and-com"ing
up-and-o"ver
up-and-un"der
@@ -179420,6 +179445,7 @@
U"ru"guay"an
U"ru"gua"ia"na
u"ru"shi"ol
+us
u"shab"ti
u"shab"tis
u"shab"ti"u
@@ -183011,6 +183037,7 @@
WBC
WCC
WCTU
+we
we'd
we'll
we're
@@ -186281,6 +186308,7 @@
Ya"va"r
Ya"wa"ta
ya"za"ta
+ye
ye'se
yea
yeah
Modified: trunk/foray/foray-hyphen/src/main/java/org/foray/hyphen/SpellChecker.java
===================================================================
--- trunk/foray/foray-hyphen/src/main/java/org/foray/hyphen/SpellChecker.java 2021-10-26 19:17:20 UTC (rev 11944)
+++ trunk/foray/foray-hyphen/src/main/java/org/foray/hyphen/SpellChecker.java 2021-10-26 23:47:05 UTC (rev 11945)
@@ -64,9 +64,12 @@
import java.io.InputStream;
import java.io.PrintStream;
import java.net.URL;
+import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
+import java.util.regex.Matcher;
+import java.util.regex.Pattern;
import javax.xml.parsers.ParserConfigurationException;
import javax.xml.parsers.SAXParserFactory;
@@ -127,6 +130,21 @@
/** Command-line return status constant indicating that there was an error parsing the input file. */
public static final byte STATUS_PARSING_ERROR = 3;
+ /** The list of patterns for which matching words should NOT be considered as misspelled. */
+ private static final List<Pattern> VALID_WORD_PATTERNS = new ArrayList<Pattern>();
+ static {
+ /* The word is all Arabic digits. */
+ VALID_WORD_PATTERNS.add(Pattern.compile("^[0-9]+$"));
+ /* The word is all uppercase Roman numeral characters. */
+ VALID_WORD_PATTERNS.add(Pattern.compile("^[IVXLCDM]+$"));
+ /* The word is all lowercase Roman numeral characters. */
+ VALID_WORD_PATTERNS.add(Pattern.compile("^[ivxlcdm]+$"));
+ /* The word is currency. */
+ VALID_WORD_PATTERNS.add(Pattern.compile("^[$\xA3][0-9]+[0-9,\\.]*$"));
+ /* The word is a single capital letter, such as a person's initial. */
+ VALID_WORD_PATTERNS.add(Pattern.compile("^[A-Z]$"));
+ }
+
/** The input source to be pretty-printed. */
private InputSource input;
@@ -162,6 +180,9 @@
/** The list of dictionaries that are currently active, i.e. that match the current orthography. */
// private List<Dictionary> currentDictionaries;
+ /** The counter for "Not found" words. */
+ private int notFoundCounter = 0;
+
/**
* Constructor.
* @param input The input source encapsulating the document to be spell-checked.
@@ -272,6 +293,7 @@
@Override
public void endDocument() throws SAXException {
+ this.output.println("Count of \"Not found\" items: " + this.notFoundCounter);
}
@@ -385,6 +407,7 @@
} else {
if (flagThisWord(dictionary, word)) {
this.output.println("Not found: " + word);
+ this.notFoundCounter ++;
}
}
}
@@ -424,10 +447,51 @@
* word for any other reason.
*/
private boolean flagThisWord(final SegmentDictionary dictionary, final CharSequence word) {
- final Word dictWord = dictionary.getWord(word);
+ /* TODO: This is all eng-us-lat specific. Need to think about how plurals and other almost-the-same cases should
+ * be handled. */
+
+ /* Is the word itself directly in the dictionary. */
+ Word dictWord = dictionary.getWord(word);
if (dictWord != null) {
return false;
}
+
+ /* Check against patterns that are considered to be valid words, but that are not in the dictionary. */
+ for (int index = 0; index < VALID_WORD_PATTERNS.size(); index ++) {
+ final Pattern pattern = VALID_WORD_PATTERNS.get(index);
+ final Matcher matcher = pattern.matcher(word);
+ if (matcher.matches()) {
+ return false;
+ }
+ }
+
+ /* Starting here, we will change the word content in various ways, looking for a match. The changes are
+ * cumulative. */
+ final StringBuilder builder = new StringBuilder(word);
+
+ /* If the first character is capitalized, convert to lowercase & check again. */
+ if (Character.isUpperCase(builder.charAt(0))) {
+ builder.setCharAt(0, Character.toLowerCase(builder.charAt(0)));
+ dictWord = dictionary.getWord(builder);
+ }
+ if (dictWord != null) {
+ return false;
+ }
+
+ /* If the last character is a lowercase "s" or "'s" (apostrophe "s"), this may be a plural noun, a
+ * present-tense verb, or a possessive. Remove them and try again. */
+ if (builder.charAt(builder.length() - 1) == 's') {
+ builder.deleteCharAt(builder.length() - 1);
+ if (builder.length() > 0
+ && builder.charAt(builder.length() - 1) == '\x92') {
+ builder.deleteCharAt(builder.length() - 1);
+ }
+ dictWord = dictionary.getWord(builder);
+ }
+ if (dictWord != null) {
+ return false;
+ }
+
return true;
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-26 19:17:22
|
Revision: 11944
http://sourceforge.net/p/foray/code/11944
Author: victormote
Date: 2021-10-26 19:17:20 +0000 (Tue, 26 Oct 2021)
Log Message:
-----------
Replace the key/value iterator code with code using the depth-first node iterator.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeIterator.java
Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeIterator.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeIterator.java 2021-10-26 18:56:23 UTC (rev 11943)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeIterator.java 2021-10-26 19:17:20 UTC (rev 11944)
@@ -29,7 +29,7 @@
package org.foray.common.data;
import java.util.Iterator;
-import java.util.Stack;
+import java.util.NoSuchElementException;
/**
* An iterator over the conceptual nodes in this tree.
@@ -43,196 +43,57 @@
/** The tree being iterated. */
private TernaryTree tree;
- /** Current node index. */
- private int cur;
+ /** The iterator over the native nodes in the tree. We simply select which of those nodes should be returned by
+ * this iterator. */
+ private TernaryNodesIterator innerIterator;
- /** Current key. */
- private String curkey;
+ /** The next node to be returned by this iterator. After initialization, if variable is null, the iterator is
+ * empty. */
+ private TernaryTreeNode next;
/**
- * Inner class Cloneable implementation.
- */
- private class Item implements Cloneable {
- /** The parent char of the Item. */
- private int parent;
-
- /** The child char of the Item. */
- private int child;
-
- /**
- * No-argument constructor.
- */
- Item() {
- this.parent = 0;
- this.child = 0;
- }
-
- /**
- * Constructor.
- * @param parent Index to the parent node.
- * @param child Index to the child node.
- */
- Item(final int parent, final int child) {
- this.parent = parent;
- this.child = child;
- }
-
- @Override
- public Item clone() {
- return new Item(this.parent, this.child);
- }
-
- }
-
- /** Node stack. */
- private Stack<Item> ns;
-
- /** Key stack implemented with a StringBuffer. */
- private StringBuilder ks;
-
- /**
* Constructor.
* @param tree The tree to be iterated.
*/
public TernaryTreeIterator(final TernaryTree tree) {
this.tree = tree;
- this.cur = -1;
- this.ns = new Stack<Item>();
- this.ks = new StringBuilder();
- rewind();
+ this.innerIterator = new TernaryNodesIterator(tree.getNodes());
+ this.next = findNext();
}
- /**
- * Rewinds the iterator to point to its first item.
- */
- public void rewind() {
- this.ns.removeAllElements();
- this.ks.setLength(0);
- this.cur = tree.getNodes().getRootNodeIndex();
- run();
+ @Override
+ public boolean hasNext() {
+ return this.next != null;
}
- /**
- * Move up one level in the tree??
- * @return The index to the next level up in the tree??
- */
- private int up() {
- Item i = new Item();
- int res = 0;
-
- if (this.ns.empty()) {
- return -1;
+ @Override
+ public TernaryTreeNode next() {
+ if (! hasNext()) {
+ throw new NoSuchElementException();
}
- if (this.cur != 0
- && tree.getNodes().getKeyChar(this.cur) == 0) {
- return tree.getNodes().getLow(this.cur);
- }
-
- boolean climb = true;
-
- while (climb) {
- i = this.ns.pop();
- i.child++;
- switch (i.child) {
- case 1:
- if (tree.getNodes().getKeyChar(i.parent) != 0) {
- res = tree.getNodes().getEqual(i.parent);
- this.ns.push(i.clone());
- this.ks.append(tree.getNodes().getKeyChar(i.parent));
- } else {
- i.child++;
- this.ns.push(i.clone());
- res = tree.getNodes().getHigh(i.parent);
- }
- climb = false;
- break;
-
- case 2:
- res = tree.getNodes().getHigh(i.parent);
- this.ns.push(i.clone());
- if (this.ks.length() > 0) {
- this.ks.setLength(this.ks.length() - 1); // pop
- }
- climb = false;
- break;
-
- default:
- if (this.ns.empty()) {
- return -1;
- }
- climb = true;
- break;
- }
- }
- return res;
+ final TernaryTreeNode returnValue = this.next;
+ this.next = findNext();
+ return returnValue;
}
- /**
- * Traverse the tree to find next key.
- * @return The index to the next item in the map??
- */
- private int run() {
- if (this.cur == -1) {
- return -1;
- }
-
- boolean leaf = false;
- final TernaryNodes nodes = tree.getNodes();
- for (;;) {
- // first go down on low branch until leaf or compressed branch
- while (this.cur != 0) {
- if (nodes.getKeyChar(this.cur) == Character.MAX_VALUE) {
- leaf = true;
- break;
+ private TernaryTreeNode findNext() {
+ while (this.innerIterator.hasNext()) {
+ final TernaryNode node = this.innerIterator.next();
+ if (node.getIndex() != 0) {
+ if (node.getValue() > -1) {
+ final CharSequence key = node.getKey(this.tree);
+ final int value = node.getValue();
+ return new TernaryTreeNode(key.toString(), value);
}
- this.ns.push(new Item(this.cur, '\u0000'));
- if (nodes.getKeyChar(this.cur) == 0) {
- leaf = true;
- break;
- }
- this.cur = nodes.getLow(this.cur);
}
- if (leaf) {
- break;
- }
- // nothing found, go up one node and try again
- this.cur = up();
- if (this.cur == -1) {
- return -1;
- }
}
- // The current node should be a data node and
- // the key should be in the key stack (at least partially)
- final StringBuilder buf = new StringBuilder(this.ks.toString());
- if (nodes.getKeyChar(this.cur) == Character.MAX_VALUE) {
- final String suffix = tree.getSuffix(nodes.getHigh(this.cur));
- final int p = nodes.getLow(this.cur);
- buf.append(suffix.substring(p));
- }
- this.curkey = buf.toString();
- return 0;
+ return null;
}
@Override
- public boolean hasNext() {
- return this.cur != -1;
- }
-
- @Override
- public TernaryTreeNode next() {
- final String key = new String(this.curkey);
- final int value = tree.getNodes().getEqual(this.cur);
- final TernaryTreeNode node = new TernaryTreeNode(key, value);
- this.cur = up();
- run();
- return node;
- }
-
- @Override
public void remove() {
- /* TODO: Implement this. */
- throw new UnsupportedOperationException();
+ throw new UnsupportedOperationException("There are no plans to ever implement this method.");
}
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-26 18:56:25
|
Revision: 11943
http://sourceforge.net/p/foray/code/11943
Author: victormote
Date: 2021-10-26 18:56:23 +0000 (Tue, 26 Oct 2021)
Log Message:
-----------
Improvements to key and value retrieval.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.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/TernaryNodesIteratorTests.java
Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java 2021-10-26 13:58:25 UTC (rev 11942)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java 2021-10-26 18:56:23 UTC (rev 11943)
@@ -183,6 +183,10 @@
return -1;
}
+ public CharSequence getKey(final TernaryTree tree) {
+ return tree.getKey(this.index, this.rawKey);
+ }
+
@Override
public String toString() {
char printableChar = this.keyChar;
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-26 13:58:25 UTC (rev 11942)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java 2021-10-26 18:56:23 UTC (rev 11943)
@@ -112,8 +112,8 @@
* If {@link #getKeyChar(int)} is a valid Unicode character, this array contains the index to the node containing
* the "equal" branch, that is the branch that should be traversed to find a char that is equal to
* {@link #getKeyChar(int)}.
- * If {@link #getKeyChar(int)} is equal to U+0000, the string terminator, then this array instead contains value for
- * this map element.
+ * If {@link #getKeyChar(int)} is equal to U+0000, the string terminator, or U+FFFF, the compressed branch
+ * indicator, then this array instead contains the value for this map element.
* @param index The node index.
* @return The "equal" value of the node at {@code index}.
*/
@@ -307,10 +307,26 @@
* @return True if and only if the node is a terminating node.
*/
boolean isUncompressedValueNode(final int index) {
+ if (index == 0) {
+ return false;
+ }
return getKeyChar(index) == Character.MIN_VALUE;
}
/**
+ * Returns the value for the node at {@code index} if it has one.
+ * @param index The index for which the value is wanted.
+ * @return The value for the node at {@code index}, or -1 if that node does not contain a value.
+ */
+ public int getValue(final int index) {
+ if (isCompressedValueNode(index)
+ || isUncompressedValueNode(index)) {
+ return getEqual(index);
+ }
+ return -1;
+ }
+
+ /**
* Indicates whether a given node is a char node, i.e. a node whose char key value is a character.
* @param index The index of the node to be tested.
* @return True if and only if the node is an uncompressed node matching the {@code theChar}.
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 2021-10-26 13:58:25 UTC (rev 11942)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java 2021-10-26 18:56:23 UTC (rev 11943)
@@ -763,4 +763,44 @@
}
}
+
+ /**
+ * Returns the key for the node at {@code index}.
+ * The key is not, as such, stored directly in the tree.
+ * It can be obtained one of two ways:
+ * 1. Spending the memory to track the parent of each node.
+ * This approach is used in {@link #recoverKey(TernaryNodeParents, int).
+ * 2. As an iterator traverses the tree, it can accumulate the keyChars from each node, which is the approach
+ * assumed by this method.
+ * The accumulated keyChars are passed to this method as {@code cumulativeKey}.
+ * @param index The index for which the key is wanted.
+ * @param cumulativeKey The cumulative key for the node at {@code index}.
+ * @return The key for the node at {@code index}.
+ */
+ public CharSequence getKey(final int index, final CharSequence cumulativeKey) {
+ final StringBuilder builder = new StringBuilder();
+
+ if (nodes.isCompressedValueNode(index)) {
+ builder.append(cumulativeKey.subSequence(0, cumulativeKey.length() - 1));
+ final String suffix = this.suffixes.get(nodes.getHigh(index));
+ final int start = nodes.getLow(index);
+ builder.append(suffix.substring(start));
+ } else if (nodes.isUncompressedValueNode(index)) {
+ builder.append(cumulativeKey.subSequence(0, cumulativeKey.length() - 1));
+ } else if (nodes.isCharNode(index)) {
+ builder.append(cumulativeKey);
+ }
+
+ return builder.toString();
+ }
+
+ /**
+ * Returns the value for the node at {@code index} if it has one.
+ * @param index The index for which the value is wanted.
+ * @return The value for the node at {@code index}, or -1 if that node does not contain a value.
+ */
+ public int getValue(final int index) {
+ return this.nodes.getValue(index);
+ }
+
}
Modified: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java 2021-10-26 13:58:25 UTC (rev 11942)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java 2021-10-26 18:56:23 UTC (rev 11943)
@@ -52,6 +52,40 @@
map.put("bravery", 1005);
Assert.assertEquals(13, map.getNodes().size());
+/*
+ Dump of nodes:
+ index: 0, low: 0, equal: 0, high: 0, key char: 0
+ index: 1, low: 0, equal: 2, high: 0, key char: 62 b
+ index: 2, low: 0, equal: 3, high: 0, key char: 72 r
+ index: 3, low: 5, equal: 4, high: 0, key char: 65 e
+ index: 4, low: 3, equal: 1001, high: 0, key char: ffff
+ index: 5, low: 0, equal: 6, high: 0, key char: 61 a
+ index: 6, low: 0, equal: 7, high: 0, key char: 76 v
+ index: 7, low: 0, equal: 8, high: 9, key char: 65 e
+ index: 8, low: 0, equal: 1002, high: 10, key char: 0
+ index: 9, low: 0, equal: 1003, high: 2, key char: ffff
+ index: 10, low: 0, equal: 11, high: 0, key char: 72 r
+ index: 11, low: 0, equal: 1004, high: 12, key char: 0
+ index: 12, low: 0, equal: 1005, high: 4, key char: ffff
+*/
+
+ /* The assertions in this next section are against the original tree, not the list of nodes dumped by the
+ * iterator below.
+ * In other words, we are testing them in their native order instead of their logical/alphabetical order. */
+ Assert.assertEquals(-1, map.getValue(0));
+ Assert.assertEquals(-1, map.getValue(1));
+ Assert.assertEquals(-1, map.getValue(2));
+ Assert.assertEquals(-1, map.getValue(3));
+ Assert.assertEquals(1001, map.getValue(4));
+ Assert.assertEquals(-1, map.getValue(5));
+ Assert.assertEquals(-1, map.getValue(6));
+ Assert.assertEquals(-1, map.getValue(7));
+ Assert.assertEquals(1002, map.getValue(8));
+ Assert.assertEquals(1003, map.getValue(9));
+ Assert.assertEquals(-1, map.getValue(10));
+ Assert.assertEquals(1004, map.getValue(11));
+ Assert.assertEquals(1005, map.getValue(12));
+
/* Use the iterator under test to create a list, to make testing easier. */
final List<TernaryNode> actual = new ArrayList<TernaryNode>();
final TernaryNodesIterator out = new TernaryNodesIterator(map.getNodes());
@@ -102,6 +136,21 @@
Assert.assertEquals("brav\uFFFF", actual.get(10).getRawKey());
Assert.assertEquals("bre", actual.get(11).getRawKey());
Assert.assertEquals("bre\uFFFF", actual.get(12).getRawKey());
+
+ Assert.assertEquals("", actual.get(0).getKey(map));
+ Assert.assertEquals("b", actual.get(1).getKey(map));
+ Assert.assertEquals("br", actual.get(2).getKey(map));
+ Assert.assertEquals("bra", actual.get(3).getKey(map));
+ Assert.assertEquals("brav", actual.get(4).getKey(map));
+ Assert.assertEquals("brave", actual.get(5).getKey(map));
+ Assert.assertEquals("brave", actual.get(6).getKey(map));
+ Assert.assertEquals("braver", actual.get(7).getKey(map));
+ Assert.assertEquals("braver", actual.get(8).getKey(map));
+ Assert.assertEquals("bravery", actual.get(9).getKey(map));
+ Assert.assertEquals("bravo", actual.get(10).getKey(map));
+ Assert.assertEquals("bre", actual.get(11).getKey(map));
+ Assert.assertEquals("bread", actual.get(12).getKey(map));
+
}
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-26 13:58:28
|
Revision: 11942
http://sourceforge.net/p/foray/code/11942
Author: victormote
Date: 2021-10-26 13:58:25 +0000 (Tue, 26 Oct 2021)
Log Message:
-----------
Minor simplification of the key building.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeIterator.java
Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeIterator.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeIterator.java 2021-10-26 13:20:14 UTC (rev 11941)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeIterator.java 2021-10-26 13:58:25 UTC (rev 11942)
@@ -178,19 +178,20 @@
}
boolean leaf = false;
+ final TernaryNodes nodes = tree.getNodes();
for (;;) {
// first go down on low branch until leaf or compressed branch
while (this.cur != 0) {
- if (tree.getNodes().getKeyChar(this.cur) == Character.MAX_VALUE) {
+ if (nodes.getKeyChar(this.cur) == Character.MAX_VALUE) {
leaf = true;
break;
}
this.ns.push(new Item(this.cur, '\u0000'));
- if (tree.getNodes().getKeyChar(this.cur) == 0) {
+ if (nodes.getKeyChar(this.cur) == 0) {
leaf = true;
break;
}
- this.cur = tree.getNodes().getLow(this.cur);
+ this.cur = nodes.getLow(this.cur);
}
if (leaf) {
break;
@@ -204,9 +205,9 @@
// The current node should be a data node and
// the key should be in the key stack (at least partially)
final StringBuilder buf = new StringBuilder(this.ks.toString());
- if (tree.getNodes().getKeyChar(this.cur) == Character.MAX_VALUE) {
- final String suffix = tree.getSuffix(tree.getNodes().getHigh(this.cur));
- final int p = tree.getNodes().getLow(this.cur);
+ if (nodes.getKeyChar(this.cur) == Character.MAX_VALUE) {
+ final String suffix = tree.getSuffix(nodes.getHigh(this.cur));
+ final int p = nodes.getLow(this.cur);
buf.append(suffix.substring(p));
}
this.curkey = buf.toString();
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-26 13:20:17
|
Revision: 11941
http://sourceforge.net/p/foray/code/11941
Author: victormote
Date: 2021-10-26 13:20:14 +0000 (Tue, 26 Oct 2021)
Log Message:
-----------
Rename "key" to "rawKey" to distinguish between it and the complete key, to be added later.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java
Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java 2021-10-26 02:08:34 UTC (rev 11940)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java 2021-10-26 13:20:14 UTC (rev 11941)
@@ -73,17 +73,17 @@
/** 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;
+ /** The raw key, i.e. the cumulative keyChar items for this node, which may end with 0x0000 or 0xFFFF. */
+ private CharSequence rawKey;
/**
* Constructor.
* @param nodes The container of the node data.
* @param index The index for which a notional nodes is wanted.
- * @param key The cumulative keyChar for this node.
+ * @param rawKey The cumulative keyChar for this node.
* @param parents The {@link TernaryNodeParents} instance. This can be null.
*/
- public TernaryNode(final TernaryNodes nodes, final int index, final CharSequence key,
+ public TernaryNode(final TernaryNodes nodes, final int index, final CharSequence rawKey,
final TernaryNodeParents parents) {
this.index = index;
this.low = nodes.getLow(index);
@@ -90,7 +90,7 @@
this.equal = nodes.getEqual(index);
this.high = nodes.getHigh(index);
this.keyChar = nodes.getKeyChar(index);
- this.key = key;
+ this.rawKey = rawKey;
if (parents != null) {
this.parent = parents.getParent(index);
}
@@ -145,11 +145,12 @@
}
/**
- * Returns the key.
- * @return The key. This can be null if the node was not created by the iterator.
+ * Returns the raw key, or accumulated keyChar from the ancestor nodes in the tree.
+ * Note that this may end with 0x0000 or 0xFFFF.
+ * @return The raw key. This can be null if the node was not created by the iterator.
*/
- public CharSequence getKey() {
- return this.key;
+ public CharSequence getRawKey() {
+ return this.rawKey;
}
/**
@@ -191,7 +192,7 @@
}
return String.format(TO_STRING_FORMAT,
this.index, this.low, this.equal, this.high, (int) this.keyChar, printableChar, this.parent,
- this.key);
+ this.rawKey);
}
@Override
Modified: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java 2021-10-26 02:08:34 UTC (rev 11940)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java 2021-10-26 13:20:14 UTC (rev 11941)
@@ -89,19 +89,19 @@
Assert.assertEquals('e', actual.get(11).getKeyChar());
Assert.assertEquals('\uFFFF', actual.get(12).getKeyChar());
- Assert.assertEquals("", actual.get(0).getKey());
- Assert.assertEquals("b", actual.get(1).getKey());
- Assert.assertEquals("br", actual.get(2).getKey());
- Assert.assertEquals("bra", actual.get(3).getKey());
- Assert.assertEquals("brav", actual.get(4).getKey());
- Assert.assertEquals("brave", actual.get(5).getKey());
- Assert.assertEquals("brave\u0000", actual.get(6).getKey());
- Assert.assertEquals("braver", actual.get(7).getKey());
- Assert.assertEquals("braver\u0000", actual.get(8).getKey());
- Assert.assertEquals("braver\uFFFF", actual.get(9).getKey());
- Assert.assertEquals("brav\uFFFF", actual.get(10).getKey());
- Assert.assertEquals("bre", actual.get(11).getKey());
- Assert.assertEquals("bre\uFFFF", actual.get(12).getKey());
+ Assert.assertEquals("", actual.get(0).getRawKey());
+ Assert.assertEquals("b", actual.get(1).getRawKey());
+ Assert.assertEquals("br", actual.get(2).getRawKey());
+ Assert.assertEquals("bra", actual.get(3).getRawKey());
+ Assert.assertEquals("brav", actual.get(4).getRawKey());
+ Assert.assertEquals("brave", actual.get(5).getRawKey());
+ Assert.assertEquals("brave\u0000", actual.get(6).getRawKey());
+ Assert.assertEquals("braver", actual.get(7).getRawKey());
+ Assert.assertEquals("braver\u0000", actual.get(8).getRawKey());
+ Assert.assertEquals("braver\uFFFF", actual.get(9).getRawKey());
+ Assert.assertEquals("brav\uFFFF", actual.get(10).getRawKey());
+ Assert.assertEquals("bre", actual.get(11).getRawKey());
+ Assert.assertEquals("bre\uFFFF", actual.get(12).getRawKey());
}
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-26 02:08:36
|
Revision: 11940
http://sourceforge.net/p/foray/code/11940
Author: victormote
Date: 2021-10-26 02:08:34 +0000 (Tue, 26 Oct 2021)
Log Message:
-----------
Add methods to be used in new iterator.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java
Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java 2021-10-25 18:49:40 UTC (rev 11939)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java 2021-10-26 02:08:34 UTC (rev 11940)
@@ -152,6 +152,36 @@
return this.key;
}
+ /**
+ * Indicates whether this node is a compressed node.
+ * @return True if and only if the node is a compressed node.
+ */
+ public boolean isCompressedValueNode() {
+ return this.keyChar == Character.MAX_VALUE;
+ }
+
+ /**
+ * Indicates whether a given node is a terminating node.
+ * @return True if and only if the node is a terminating node.
+ */
+ public boolean isUncompressedValueNode() {
+ return this.keyChar == Character.MIN_VALUE;
+ }
+
+ /**
+ * Returns the value for this node.
+ * @return The value of this node, or -1 if this is not a node that contains a value.
+ */
+ public int getValue() {
+ if (this.keyChar == Character.MIN_VALUE) {
+ return this.equal;
+ }
+ if (this.keyChar == Character.MAX_VALUE) {
+ return this.equal;
+ }
+ return -1;
+ }
+
@Override
public String toString() {
char printableChar = this.keyChar;
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-25 18:49:43
|
Revision: 11939
http://sourceforge.net/p/foray/code/11939
Author: victormote
Date: 2021-10-25 18:49:40 +0000 (Mon, 25 Oct 2021)
Log Message:
-----------
1. Make useful method public. 2. Remove to-do item related to it.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java
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 2021-10-25 18:44:50 UTC (rev 11938)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java 2021-10-25 18:49:40 UTC (rev 11939)
@@ -96,12 +96,6 @@
* 2. TODO: 0xFFFF currently has special meaning, marking the compressed branches.
* It would be good to eliminate this limitation, possibly by adding a boolean array to the data structures that
* marks whether the data in that node is compressed or not.
- * 3. TODO: We miss an opportunity by using the branch compression.
- * The good news is that it saves nodes, but the bad news is that it saves nodes.
- * It might be useful, in addition to returning mapped values, to return the node number that contains the
- * mapped value.
- * This would allow client applications to incrementally traverse the tree, and might provide more flexibility
- * for doing things like wildcard searches.
*/
/** Constant used for serialization. */
@@ -469,7 +463,7 @@
* considered part of the key.
* @return The index to the node containing the value of {@code key} if it is in the map. Otherwise, returns -1.
*/
- int getNodeIndex(final CharSequence key, final int start, final int end) {
+ public int getNodeIndex(final CharSequence key, final int start, final int end) {
int currentNodeIndex = this.nodes.getRootNodeIndex();
int i = start;
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-25 18:44:52
|
Revision: 11938
http://sourceforge.net/p/foray/code/11938
Author: victormote
Date: 2021-10-25 18:44:50 +0000 (Mon, 25 Oct 2021)
Log Message:
-----------
Remove alread-completed to-do item.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java
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 2021-10-25 18:33:45 UTC (rev 11937)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java 2021-10-25 18:44:50 UTC (rev 11938)
@@ -102,8 +102,6 @@
* mapped value.
* This would allow client applications to incrementally traverse the tree, and might provide more flexibility
* for doing things like wildcard searches.
- * Instead of removing branch compression, perhaps it would be sufficient to simply indicate whether a given
- * node index represents a compressed node.
*/
/** Constant used for serialization. */
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-25 18:33:47
|
Revision: 11937
http://sourceforge.net/p/foray/code/11937
Author: victormote
Date: 2021-10-25 18:33:45 +0000 (Mon, 25 Oct 2021)
Log Message:
-----------
Get the key building process working.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java
Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java 2021-10-25 17:23:40 UTC (rev 11936)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java 2021-10-25 18:33:45 UTC (rev 11937)
@@ -111,7 +111,6 @@
if (nodes.size() > 1) {
this.currentIndexStack.push(1);
this.currentBranchStack.push(BRANCH_NOT_STARTED);
- this.charStack.push(nodes.getKeyChar(1));
} else {
this.nextIndex = -1;
}
@@ -135,6 +134,8 @@
break;
}
case BRANCH_CURRENT: {
+ /* Push the keyChar onto the stack only while processing the current and equal branches. */
+ this.charStack.push(nodes.getKeyChar(currentIndex));
if (currentIndex == returnValue.getIndex()) {
break;
} else {
@@ -147,6 +148,8 @@
break;
}
case BRANCH_HIGH: {
+ /* Pop the keyChar after the current and equal branches are complete. */
+ this.charStack.pop();
branchIndex = this.nodes.getHighPointer(currentIndex);
break;
}
@@ -153,7 +156,6 @@
case BRANCH_COMPLETED: {
this.currentIndexStack.pop();
this.currentBranchStack.pop();
- this.charStack.pop();
break branchLoop;
}
default: {
@@ -160,11 +162,11 @@
throw new IllegalStateException("Unexpected branch value: " + this.currentBranchStack.peek());
}
}
+
if (branchIndex > 0) {
/* Push the found index onto the index stack. */
this.currentIndexStack.push(branchIndex);
this.currentBranchStack.push(BRANCH_NOT_STARTED);
- this.charStack.push(this.nodes.getKeyChar(branchIndex));
break branchLoop;
} else {
Modified: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java 2021-10-25 17:23:40 UTC (rev 11936)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java 2021-10-25 18:33:45 UTC (rev 11937)
@@ -75,19 +75,33 @@
Assert.assertEquals(3, actual.get(11).getIndex());
Assert.assertEquals(4, actual.get(12).getIndex());
- Assert.assertEquals(0, actual.get(0).getKeyChar());
- Assert.assertEquals('b', actual.get(1).getKeyChar());
- Assert.assertEquals('r', actual.get(2).getKeyChar());
- Assert.assertEquals('a', actual.get(3).getKeyChar());
- Assert.assertEquals('v', actual.get(4).getKeyChar());
- Assert.assertEquals('e', actual.get(5).getKeyChar());
- Assert.assertEquals(Character.MIN_VALUE, actual.get(6).getKeyChar());
- Assert.assertEquals('r', actual.get(7).getKeyChar());
- Assert.assertEquals(Character.MIN_VALUE, actual.get(8).getKeyChar());
- Assert.assertEquals(Character.MAX_VALUE, actual.get(9).getKeyChar());
- Assert.assertEquals(Character.MAX_VALUE, actual.get(10).getKeyChar());
- Assert.assertEquals('e', actual.get(11).getKeyChar());
- Assert.assertEquals(Character.MAX_VALUE, actual.get(12).getKeyChar());
+ Assert.assertEquals(0, actual.get(0).getKeyChar());
+ Assert.assertEquals('b', actual.get(1).getKeyChar());
+ Assert.assertEquals('r', actual.get(2).getKeyChar());
+ Assert.assertEquals('a', actual.get(3).getKeyChar());
+ Assert.assertEquals('v', actual.get(4).getKeyChar());
+ Assert.assertEquals('e', actual.get(5).getKeyChar());
+ Assert.assertEquals('\u0000', actual.get(6).getKeyChar());
+ Assert.assertEquals('r', actual.get(7).getKeyChar());
+ Assert.assertEquals('\u0000', actual.get(8).getKeyChar());
+ Assert.assertEquals('\uFFFF', actual.get(9).getKeyChar());
+ Assert.assertEquals('\uFFFF', actual.get(10).getKeyChar());
+ Assert.assertEquals('e', actual.get(11).getKeyChar());
+ Assert.assertEquals('\uFFFF', actual.get(12).getKeyChar());
+
+ Assert.assertEquals("", actual.get(0).getKey());
+ Assert.assertEquals("b", actual.get(1).getKey());
+ Assert.assertEquals("br", actual.get(2).getKey());
+ Assert.assertEquals("bra", actual.get(3).getKey());
+ Assert.assertEquals("brav", actual.get(4).getKey());
+ Assert.assertEquals("brave", actual.get(5).getKey());
+ Assert.assertEquals("brave\u0000", actual.get(6).getKey());
+ Assert.assertEquals("braver", actual.get(7).getKey());
+ Assert.assertEquals("braver\u0000", actual.get(8).getKey());
+ Assert.assertEquals("braver\uFFFF", actual.get(9).getKey());
+ Assert.assertEquals("brav\uFFFF", actual.get(10).getKey());
+ Assert.assertEquals("bre", actual.get(11).getKey());
+ Assert.assertEquals("bre\uFFFF", actual.get(12).getKey());
}
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-25 17:23:43
|
Revision: 11936
http://sourceforge.net/p/foray/code/11936
Author: victormote
Date: 2021-10-25 17:23:40 +0000 (Mon, 25 Oct 2021)
Log Message:
-----------
Improvements to node iterator.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java
Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java 2021-10-25 13:28:10 UTC (rev 11935)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java 2021-10-25 17:23:40 UTC (rev 11936)
@@ -36,8 +36,7 @@
/**
* Iterates over the nodes of a {@link TernaryNodes} instance in depth-first order, going first to the low branch, then
- * the equal branch, then the high branch.
- * Nodes are returned only when they are first encountered.
+ * to the node itself, then to the equal branch, then the high branch.
* The data returned is <em>not</em> the key/value pairs placed in the tree, but is instead the raw nodes, including
* all nodes that are merely connective.
* @see TernaryTreeIterator for an iterator over the key/value pairs placed in a tree.
@@ -44,6 +43,24 @@
*/
public class TernaryNodesIterator implements Iterator<TernaryNode> {
+ /** Constant indicating that the no branches for the corresponding node have yet been processed. */
+ private static final int BRANCH_NOT_STARTED = 101;
+
+ /** Constant indicating that the low branch of the corresponding node is being processed. */
+ private static final int BRANCH_LOW = 102;
+
+ /** Constant indicating that the node itself is being processed. */
+ private static final int BRANCH_CURRENT = 103;
+
+ /** Constant indicating that the equal branch of the corresponding node is being processed. */
+ private static final int BRANCH_EQUAL = 104;
+
+ /** Constant indicating that the high branch of the corresponding node is being processed. */
+ private static final int BRANCH_HIGH = 105;
+
+ /** Constant indicating that all branches of the corresponding node have been processed. */
+ private static final int BRANCH_COMPLETED = 106;
+
/** The nodes being iterated. */
private TernaryNodes nodes;
@@ -86,22 +103,20 @@
throw new NoSuchElementException();
}
+ final TernaryNode returnValue = new TernaryNode(this.nodes, this.nextIndex, this.charStack.toString(), null);
+
/* Node zero does not contain data, and must therefore be handled specially. */
if (this.nextIndex == 0) {
- final TernaryNode returnValue = new TernaryNode(this.nodes, this.nextIndex,
- this.charStack.toString(), null);
+ /* Prime the pump with index 1 if it exists. */
if (nodes.size() > 1) {
- this.nextIndex = 1;
this.currentIndexStack.push(1);
- this.currentBranchStack.push(-1 - 1);
+ this.currentBranchStack.push(BRANCH_NOT_STARTED);
this.charStack.push(nodes.getKeyChar(1));
+ } else {
+ this.nextIndex = -1;
}
- return returnValue;
}
- final TernaryNode returnValue = new TernaryNode(this.nodes, this.nextIndex,
- this.charStack.toString(), null);
-
/* Tee up the one after this, if any. */
this.nextIndex = -1;
@@ -109,52 +124,68 @@
while (this.currentIndexStack.length() > 0
&& this.nextIndex < 0) {
final int currentIndex = this.currentIndexStack.peek();
- int currentBranch = this.currentBranchStack.pop();
- currentBranch ++;
- this.currentBranchStack.push(currentBranch);
+ incrementCurrentBranch();
- while (currentBranch < 2) {
+ branchLoop:
+ while (this.currentBranchStack.peek() <= BRANCH_COMPLETED) {
int branchIndex = -1;
switch (this.currentBranchStack.peek()) {
- case -1: {
+ case BRANCH_LOW: {
branchIndex = this.nodes.getLowPointer(currentIndex);
break;
}
- case 0: {
+ case BRANCH_CURRENT: {
+ if (currentIndex == returnValue.getIndex()) {
+ break;
+ } else {
+ this.nextIndex = currentIndex;
+ break indexLoop;
+ }
+ }
+ case BRANCH_EQUAL: {
branchIndex = this.nodes.getEqualPointer(currentIndex);
break;
}
- case 1: {
+ case BRANCH_HIGH: {
branchIndex = this.nodes.getHighPointer(currentIndex);
break;
}
+ case BRANCH_COMPLETED: {
+ this.currentIndexStack.pop();
+ this.currentBranchStack.pop();
+ this.charStack.pop();
+ break branchLoop;
+ }
default: {
throw new IllegalStateException("Unexpected branch value: " + this.currentBranchStack.peek());
}
}
if (branchIndex > 0) {
- /* Push the found index onto the stack. */
+ /* Push the found index onto the index stack. */
this.currentIndexStack.push(branchIndex);
- this.currentBranchStack.push(-1 - 1);
+ this.currentBranchStack.push(BRANCH_NOT_STARTED);
this.charStack.push(this.nodes.getKeyChar(branchIndex));
- /* The new index is the next item to be processed. */
- this.nextIndex = branchIndex;
- break indexLoop;
+
+ break branchLoop;
} else {
- /* Increment the current branch. */
- currentBranch = this.currentBranchStack.pop() + 1;
- this.currentBranchStack.push(currentBranch);
+ incrementCurrentBranch();
}
}
- /* We have processed all of the branches on the current index. Pop all stacks. */
- this.currentIndexStack.pop();
- this.currentBranchStack.pop();
- this.charStack.pop();
}
return returnValue;
}
+ /**
+ * Increments the top item on {@link #currentBranchStack}.
+ */
+ private void incrementCurrentBranch() {
+ int currentBranch = this.currentBranchStack.pop();
+ currentBranch ++;
+ this.currentBranchStack.push(currentBranch);
+
+ }
+
@Override
public void remove() {
throw new UnsupportedOperationException();
Modified: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java 2021-10-25 13:28:10 UTC (rev 11935)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java 2021-10-25 17:23:40 UTC (rev 11936)
@@ -60,19 +60,34 @@
}
Assert.assertEquals(13, actual.size());
+
Assert.assertEquals(0, actual.get(0).getIndex());
Assert.assertEquals(1, actual.get(1).getIndex());
Assert.assertEquals(2, actual.get(2).getIndex());
- Assert.assertEquals(3, actual.get(3).getIndex());
- Assert.assertEquals(5, actual.get(4).getIndex());
- Assert.assertEquals(6, actual.get(5).getIndex());
- Assert.assertEquals(7, actual.get(6).getIndex());
- Assert.assertEquals(8, actual.get(7).getIndex());
- Assert.assertEquals(10, actual.get(8).getIndex());
- Assert.assertEquals(11, actual.get(9).getIndex());
- Assert.assertEquals(12, actual.get(10).getIndex());
- Assert.assertEquals(9, actual.get(11).getIndex());
+ Assert.assertEquals(5, actual.get(3).getIndex());
+ Assert.assertEquals(6, actual.get(4).getIndex());
+ Assert.assertEquals(7, actual.get(5).getIndex());
+ Assert.assertEquals(8, actual.get(6).getIndex());
+ Assert.assertEquals(10, actual.get(7).getIndex());
+ Assert.assertEquals(11, actual.get(8).getIndex());
+ Assert.assertEquals(12, actual.get(9).getIndex());
+ Assert.assertEquals(9, actual.get(10).getIndex());
+ Assert.assertEquals(3, actual.get(11).getIndex());
Assert.assertEquals(4, actual.get(12).getIndex());
+
+ Assert.assertEquals(0, actual.get(0).getKeyChar());
+ Assert.assertEquals('b', actual.get(1).getKeyChar());
+ Assert.assertEquals('r', actual.get(2).getKeyChar());
+ Assert.assertEquals('a', actual.get(3).getKeyChar());
+ Assert.assertEquals('v', actual.get(4).getKeyChar());
+ Assert.assertEquals('e', actual.get(5).getKeyChar());
+ Assert.assertEquals(Character.MIN_VALUE, actual.get(6).getKeyChar());
+ Assert.assertEquals('r', actual.get(7).getKeyChar());
+ Assert.assertEquals(Character.MIN_VALUE, actual.get(8).getKeyChar());
+ Assert.assertEquals(Character.MAX_VALUE, actual.get(9).getKeyChar());
+ Assert.assertEquals(Character.MAX_VALUE, actual.get(10).getKeyChar());
+ Assert.assertEquals('e', actual.get(11).getKeyChar());
+ Assert.assertEquals(Character.MAX_VALUE, actual.get(12).getKeyChar());
}
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-25 13:28:13
|
Revision: 11935
http://sourceforge.net/p/foray/code/11935
Author: victormote
Date: 2021-10-25 13:28:10 +0000 (Mon, 25 Oct 2021)
Log Message:
-----------
1. Return index zero from the nodes iterator. 2. Put related test in correct class.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesTests.java
Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java 2021-10-25 13:04:53 UTC (rev 11934)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java 2021-10-25 13:28:10 UTC (rev 11935)
@@ -70,11 +70,8 @@
*/
public TernaryNodesIterator(final TernaryNodes nodes) {
this.nodes = nodes;
- if (nodes.size() > 1) {
- this.currentIndexStack.push(1);
- this.nextIndex = 1;
- this.currentBranchStack.push(-1 - 1);
- this.charStack.push(nodes.getKeyChar(1));
+ if (nodes.size() > 0) {
+ this.nextIndex = 0;
}
}
@@ -89,6 +86,19 @@
throw new NoSuchElementException();
}
+ /* Node zero does not contain data, and must therefore be handled specially. */
+ if (this.nextIndex == 0) {
+ final TernaryNode returnValue = new TernaryNode(this.nodes, this.nextIndex,
+ this.charStack.toString(), null);
+ if (nodes.size() > 1) {
+ this.nextIndex = 1;
+ this.currentIndexStack.push(1);
+ this.currentBranchStack.push(-1 - 1);
+ this.charStack.push(nodes.getKeyChar(1));
+ }
+ return returnValue;
+ }
+
final TernaryNode returnValue = new TernaryNode(this.nodes, this.nextIndex,
this.charStack.toString(), null);
Modified: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java 2021-10-25 13:04:53 UTC (rev 11934)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java 2021-10-25 13:28:10 UTC (rev 11935)
@@ -53,12 +53,26 @@
Assert.assertEquals(13, map.getNodes().size());
/* Use the iterator under test to create a list, to make testing easier. */
- final List<TernaryNode> nodeList = new ArrayList<TernaryNode>();
+ final List<TernaryNode> actual = new ArrayList<TernaryNode>();
final TernaryNodesIterator out = new TernaryNodesIterator(map.getNodes());
while (out.hasNext()) {
- nodeList.add(out.next());
+ actual.add(out.next());
}
-// Assert.assertEquals(13, nodeList.size());
+
+ Assert.assertEquals(13, actual.size());
+ Assert.assertEquals(0, actual.get(0).getIndex());
+ Assert.assertEquals(1, actual.get(1).getIndex());
+ Assert.assertEquals(2, actual.get(2).getIndex());
+ Assert.assertEquals(3, actual.get(3).getIndex());
+ Assert.assertEquals(5, actual.get(4).getIndex());
+ Assert.assertEquals(6, actual.get(5).getIndex());
+ Assert.assertEquals(7, actual.get(6).getIndex());
+ Assert.assertEquals(8, actual.get(7).getIndex());
+ Assert.assertEquals(10, actual.get(8).getIndex());
+ Assert.assertEquals(11, actual.get(9).getIndex());
+ Assert.assertEquals(12, actual.get(10).getIndex());
+ Assert.assertEquals(9, actual.get(11).getIndex());
+ Assert.assertEquals(4, actual.get(12).getIndex());
}
}
Modified: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesTests.java 2021-10-25 13:04:53 UTC (rev 11934)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesTests.java 2021-10-25 13:28:10 UTC (rev 11935)
@@ -31,10 +31,6 @@
import org.junit.Assert;
import org.junit.Test;
-import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.List;
-
public class TernaryNodesTests extends TernaryTreeTestsHelper {
/**
@@ -90,27 +86,6 @@
* equal branch of "e". */
Assert.assertEquals(10, map.getNodes().findCharNode(8, 'r'));
- /* Test the iterator. */
- final Iterator<TernaryNode> nodeIterator = map.getNodes().nodeIterator();
- final List<TernaryNode> actual = new ArrayList<TernaryNode>();
- while (nodeIterator.hasNext()) {
- actual.add(nodeIterator.next());
- }
- /* The zero nodes does not get returned by the iterator, so we should have n - 1. */
- Assert.assertEquals(12, actual.size());
- Assert.assertEquals(1, actual.get(0).getIndex());
- Assert.assertEquals(2, actual.get(1).getIndex());
- Assert.assertEquals(3, actual.get(2).getIndex());
- Assert.assertEquals(5, actual.get(3).getIndex());
- Assert.assertEquals(6, actual.get(4).getIndex());
- Assert.assertEquals(7, actual.get(5).getIndex());
- Assert.assertEquals(8, actual.get(6).getIndex());
- Assert.assertEquals(10, actual.get(7).getIndex());
- Assert.assertEquals(11, actual.get(8).getIndex());
- Assert.assertEquals(12, actual.get(9).getIndex());
- Assert.assertEquals(9, actual.get(10).getIndex());
- Assert.assertEquals(4, actual.get(11).getIndex());
-
/* Test the WithParent. */
final TernaryNodeParents parents = map.getNodes().getParents();
Assert.assertEquals(0, parents.getParent(0));
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-25 13:04:55
|
Revision: 11934
http://sourceforge.net/p/foray/code/11934
Author: victormote
Date: 2021-10-25 13:04:53 +0000 (Mon, 25 Oct 2021)
Log Message:
-----------
Add javadoc explaining why the zero index is never used for data.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.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-25 12:35:10 UTC (rev 11933)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java 2021-10-25 13:04:53 UTC (rev 11934)
@@ -48,6 +48,9 @@
* of the serialized instance, and therefore presumably does approximately the same to memory consumption.
* Since a light memory footprint is one of the main design considerations for this class, we will use the original
* parallel arrays instead.</p>
+ *
+ * <p>Note that index zero (0) in all implementations is not used in order to preserve it as the "not set" index for
+ * implmentations that do not have negative values. See {@link TernaryNodes#ROOT_NODE_INDEX}.</p>
*/
public abstract class TernaryNodes implements Serializable, Cloneable {
@@ -54,9 +57,15 @@
/** Allocation size for arrays. */
public static final int DEFAULT_BLOCK_SIZE = 2048;
- /** The index to the root node. */
+ /**
+ * The index to the root node. This is one (1) instead of zero (0) as might be expected, because zero is reserved
+ * to mean "invalid" or "not set".
+ * Normally a "not set" value for an index would be negative one (-1).
+ * However, some implementations may use an unsigned value (such as char) to store the indexes, and we therefore
+ * use zero (0) for all implementations instead.
+ * The node at index zero (0) is therefore always "wasted".
+ */
public static final int ROOT_NODE_INDEX = 1;
- /* TODO: Either change this value to zero or document why that cannot be done. */
/** Constant needed for serialization. */
private static final long serialVersionUID = 2866689417641820196L;
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-25 12:35:13
|
Revision: 11933
http://sourceforge.net/p/foray/code/11933
Author: victormote
Date: 2021-10-25 12:35:10 +0000 (Mon, 25 Oct 2021)
Log Message:
-----------
Move validity tests out of the recursive method, for performance.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java
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 2021-10-25 12:09:45 UTC (rev 11932)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java 2021-10-25 12:35:10 UTC (rev 11933)
@@ -228,6 +228,23 @@
* @param value The value.
*/
public void put(final CharSequence key, final int start, final int end, final int value) {
+ if (start > key.length()) {
+ throw new IllegalArgumentException("Invalid start (" + start + ") in word: " + key);
+ }
+ if (end > key.length()
+ || end < start) {
+ throw new IllegalArgumentException("Invalid end (" + end + ") in word: " + key);
+ }
+
+ for (int index = start; index < end; index ++) {
+ if (key.charAt(index) == Character.MIN_VALUE) {
+ throw new IllegalArgumentException("Illegal Unicode value \\0000 in key: " + key);
+ }
+ if (key.charAt(index) == Character.MAX_VALUE) {
+ throw new IllegalArgumentException("Illegal Unicode value \\FFFF in key: " + key);
+ }
+ }
+
final int newCapacity = this.nodes.size() + end - start + 1;
this.nodes.ensureCapacity(newCapacity);
@@ -249,23 +266,10 @@
*/
private int put(final int startingNodeIndex, final CharSequence key, final int start, final int end,
final int value) {
- if (start > key.length()) {
- throw new IllegalArgumentException("Invalid start (" + start + ") in word: " + key);
- }
- if (end > key.length()
- || end < start) {
- throw new IllegalArgumentException("Invalid end (" + end + ") in word: " + key);
- }
-
- for (int index = start; index < end; index ++) {
- if (key.charAt(index) == Character.MIN_VALUE) {
- throw new IllegalArgumentException("Illegal Unicode value \\0000 in key: " + key);
- }
- if (key.charAt(index) == Character.MAX_VALUE) {
- throw new IllegalArgumentException("Illegal Unicode value \\FFFF in key: " + key);
- }
- }
-
+ /* Since this method is recursive, validity of start and end are checked only once in
+ * put(CharSequence, int, int, int). */
+ /* Since this method is recursive, illegal characters in key are checked only once in
+ * put(CharSequence, int, int, int). */
int currentNodeIndex = startingNodeIndex;
final int len = end - start;
if (currentNodeIndex == 0) {
@@ -303,13 +307,15 @@
final char searchCharacter = key.charAt(start);
final char keyCharacter = this.nodes.getKeyChar(currentNodeIndex);
if (searchCharacter < keyCharacter) {
- this.nodes.setLow(currentNodeIndex, put(this.nodes.getLow(currentNodeIndex), key, start, end, value));
+ final int newLow = put(this.nodes.getLow(currentNodeIndex), key, start, end, value);
+ this.nodes.setLow(currentNodeIndex, newLow);
} else if (searchCharacter == keyCharacter) {
- this.nodes.setEqual(currentNodeIndex,
- put(this.nodes.getEqual(currentNodeIndex), key, start + 1, end, value));
+ final int newEqual = put(this.nodes.getEqual(currentNodeIndex), key, start + 1, end, value);
+ this.nodes.setEqual(currentNodeIndex, newEqual);
} else {
assert searchCharacter > keyCharacter : "searchCharacter must be > keyCharacter.";
- this.nodes.setHigh(currentNodeIndex, put(this.nodes.getHigh(currentNodeIndex), key, start, end, value));
+ final int newHigh = put(this.nodes.getHigh(currentNodeIndex), key, start, end, value);
+ this.nodes.setHigh(currentNodeIndex, newHigh);
}
return currentNodeIndex;
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-25 12:09:47
|
Revision: 11932
http://sourceforge.net/p/foray/code/11932
Author: victormote
Date: 2021-10-25 12:09:45 +0000 (Mon, 25 Oct 2021)
Log Message:
-----------
Throw exception when iterator is empty.
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/TernaryNodesIterator.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-25 11:25:36 UTC (rev 11931)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java 2021-10-25 12:09:45 UTC (rev 11932)
@@ -56,6 +56,7 @@
/** The index to the root node. */
public static final int ROOT_NODE_INDEX = 1;
+ /* TODO: Either change this value to zero or document why that cannot be done. */
/** Constant needed for serialization. */
private static final long serialVersionUID = 2866689417641820196L;
Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java 2021-10-25 11:25:36 UTC (rev 11931)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java 2021-10-25 12:09:45 UTC (rev 11932)
@@ -32,6 +32,7 @@
import org.foray.common.sequence.IntArrayBuilder;
import java.util.Iterator;
+import java.util.NoSuchElementException;
/**
* Iterates over the nodes of a {@link TernaryNodes} instance in depth-first order, going first to the low branch, then
@@ -84,6 +85,10 @@
@Override
public TernaryNode next() {
+ if (! hasNext()) {
+ throw new NoSuchElementException();
+ }
+
final TernaryNode returnValue = new TernaryNode(this.nodes, this.nextIndex,
this.charStack.toString(), null);
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-25 11:25:38
|
Revision: 11931
http://sourceforge.net/p/foray/code/11931
Author: victormote
Date: 2021-10-25 11:25:36 +0000 (Mon, 25 Oct 2021)
Log Message:
-----------
Rough-in a test class for the nodes iterator.
Added Paths:
-----------
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java
Added: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java (rev 0)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java 2021-10-25 11:25:36 UTC (rev 11931)
@@ -0,0 +1,64 @@
+/*
+ * Copyright 2021 The FOray Project.
+ * http://www.foray.org
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * This work is in part derived from the following work(s), used with the
+ * permission of the licensor:
+ * Apache FOP, licensed by the Apache Software Foundation
+ *
+ */
+
+/*
+ * $LastChangedRevision$
+ * $LastChangedDate$
+ * $LastChangedBy$
+ */
+
+package org.foray.common.data;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Tests of {@link TernaryNodesIterator}.
+ */
+public class TernaryNodesIteratorTests {
+
+ /**
+ * Basic Test.
+ */
+ @Test
+ public void test001() {
+ final TernaryTree map = new TernaryTree();
+ map.put("bread", 1001);
+ map.put("brave", 1002);
+ map.put("bravo", 1003);
+ map.put("braver", 1004);
+ map.put("bravery", 1005);
+ Assert.assertEquals(13, map.getNodes().size());
+
+ /* Use the iterator under test to create a list, to make testing easier. */
+ final List<TernaryNode> nodeList = new ArrayList<TernaryNode>();
+ final TernaryNodesIterator out = new TernaryNodesIterator(map.getNodes());
+ while (out.hasNext()) {
+ nodeList.add(out.next());
+ }
+// Assert.assertEquals(13, nodeList.size());
+ }
+
+}
Property changes on: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesIteratorTests.java
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Rev
\ No newline at end of property
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-25 10:12:08
|
Revision: 11930
http://sourceforge.net/p/foray/code/11930
Author: victormote
Date: 2021-10-25 10:12:06 +0000 (Mon, 25 Oct 2021)
Log Message:
-----------
1. Rename instance variable for clarity. 2. Remove unused and unneeded method.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.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 23:21:19 UTC (rev 11929)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java 2021-10-25 10:12:06 UTC (rev 11930)
@@ -63,8 +63,8 @@
/** The logger. */
private transient Logger logger = LoggerFactory.getLogger(this.getClass());
- /** The index to the next available node. */
- private int freenode;
+ /** The number of nodes in this data structure. This also corresponds to the index of the next available node. */
+ private int length;
/** The array of chars representing the "key". */
private char[] keyChar;
@@ -131,7 +131,7 @@
* Initialize the data structure.
*/
protected void init() {
- this.freenode = 1;
+ this.length = 1;
this.keyChar = new char[TernaryNodes.DEFAULT_BLOCK_SIZE];
initIndexes(TernaryNodes.DEFAULT_BLOCK_SIZE);
}
@@ -189,7 +189,7 @@
newNodes.setHigh(index, getHigh(index));
newNodes.setKeyChar(index, getKeyChar(index));
}
- ((TernaryNodes) newNodes).freenode = this.freenode;
+ ((TernaryNodes) newNodes).length = this.length;
return newNodes;
}
@@ -196,7 +196,7 @@
@Override
public TernaryNodes clone() {
final TernaryNodes clone = forceClone();
- clone.freenode = this.freenode;
+ clone.length = this.length;
return clone;
}
@@ -238,7 +238,7 @@
* Packs the arrays to their current size, i.e. removes any unused array elements..
*/
public void pack() {
- resize(this.freenode);
+ resize(this.length);
}
/**
@@ -267,7 +267,7 @@
* @return The index to the root node of the tree.
*/
public int getRootNodeIndex() {
- if (this.freenode == 1) {
+ if (this.length == 1) {
/* If we haven't created any nodes, yet, this is a special case. */
return 0;
}
@@ -279,7 +279,7 @@
* @return The number of nodes in the tree.
*/
public int size() {
- return this.freenode;
+ return this.length;
}
/**
@@ -362,23 +362,6 @@
}
/**
- * 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.
*/
@@ -402,7 +385,7 @@
* @return True if and only if creating a new node would exceed the capacity of this data structure.
*/
public boolean isCapacityExceeded() {
- return this.freenode >= getMaximumCapacity();
+ return this.length >= getMaximumCapacity();
}
/**
@@ -410,8 +393,8 @@
* @return The new node index.
*/
public int allocateNewNode() {
- final int newNode = this.freenode;
- this.freenode ++;
+ final int newNode = this.length;
+ this.length ++;
return newNode;
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-23 23:21:22
|
Revision: 11929
http://sourceforge.net/p/foray/code/11929
Author: victormote
Date: 2021-10-23 23:21:19 +0000 (Sat, 23 Oct 2021)
Log Message:
-----------
Sort some tests by class better.
Modified Paths:
--------------
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java
Added Paths:
-----------
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeIteratorTests.java
Added: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeIteratorTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeIteratorTests.java (rev 0)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeIteratorTests.java 2021-10-23 23:21:19 UTC (rev 11929)
@@ -0,0 +1,70 @@
+/*
+ * Copyright 2021 The FOray Project.
+ * http://www.foray.org
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * This work is in part derived from the following work(s), used with the
+ * permission of the licensor:
+ * Apache FOP, licensed by the Apache Software Foundation
+ *
+ */
+
+/*
+ * $LastChangedRevision$
+ * $LastChangedDate$
+ * $LastChangedBy$
+ */
+
+package org.foray.common.data;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+public class TernaryTreeIteratorTests {
+
+ /**
+ * Test of the iterator.
+ */
+ @Test
+ public void iteratorTest() {
+ final TernaryTree map = new TernaryTree();
+ map.put("Julius Caesar", 'a');
+ map.put("Hamlet", 'b');
+ map.put("The Tempest", 'c');
+ map.put("Henry V", 'd');
+ map.optimize();
+
+ final Iterator<TernaryTreeNode> iterator = map.getIterator();
+ final List<TernaryTreeNode> actual = new ArrayList<TernaryTreeNode>();
+ while (iterator.hasNext()) {
+ actual.add(iterator.next());
+ }
+ Assert.assertEquals(4, actual.size());
+ /* The iterator should return the elements in alphabetical order. */
+ Assert.assertEquals("Hamlet", actual.get(0).getKey());
+ Assert.assertEquals("Henry V", actual.get(1).getKey());
+ Assert.assertEquals("Julius Caesar", actual.get(2).getKey());
+ Assert.assertEquals("The Tempest", actual.get(3).getKey());
+
+ Assert.assertEquals('b', actual.get(0).getValue());
+ Assert.assertEquals('d', actual.get(1).getValue());
+ Assert.assertEquals('a', actual.get(2).getValue());
+ Assert.assertEquals('c', actual.get(3).getValue());
+ }
+
+}
Property changes on: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeIteratorTests.java
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Rev
\ No newline at end of property
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 18:23:02 UTC (rev 11928)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java 2021-10-23 23:21:19 UTC (rev 11929)
@@ -31,10 +31,6 @@
import org.junit.Assert;
import org.junit.Test;
-import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.List;
-
/**
* JUnit test class for the class {@link TernaryTree}.
*/
@@ -217,36 +213,6 @@
}
/**
- * Test of the iterator.
- */
- @Test
- public void iteratorTest() {
- final TernaryTree map = new TernaryTree();
- map.put("Julius Caesar", 'a');
- map.put("Hamlet", 'b');
- map.put("The Tempest", 'c');
- map.put("Henry V", 'd');
- map.optimize();
-
- final Iterator<TernaryTreeNode> iterator = map.getIterator();
- final List<TernaryTreeNode> actual = new ArrayList<TernaryTreeNode>();
- while (iterator.hasNext()) {
- actual.add(iterator.next());
- }
- Assert.assertEquals(4, actual.size());
- /* The iterator should return the elements in order. */
- Assert.assertEquals("Hamlet", actual.get(0).getKey());
- Assert.assertEquals("Henry V", actual.get(1).getKey());
- Assert.assertEquals("Julius Caesar", actual.get(2).getKey());
- Assert.assertEquals("The Tempest", actual.get(3).getKey());
-
- Assert.assertEquals('b', actual.get(0).getValue());
- Assert.assertEquals('d', actual.get(1).getValue());
- Assert.assertEquals('a', actual.get(2).getValue());
- Assert.assertEquals('c', actual.get(3).getValue());
- }
-
- /**
* Test of a longer key first, following by a shorter word that is a subset of the longer.
*/
@Test
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-23 18:23:05
|
Revision: 11928
http://sourceforge.net/p/foray/code/11928
Author: victormote
Date: 2021-10-23 18:23:02 +0000 (Sat, 23 Oct 2021)
Log Message:
-----------
1. Disable some unneeded methods. 2. Add missing test.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeMap.java
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeMapTests.java
trunk/foray/foray-common/src/test/java/org/foray/common/primitive/StringLatin1Tests.java
Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeMap.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeMap.java 2021-10-23 17:55:41 UTC (rev 11927)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeMap.java 2021-10-23 18:23:02 UTC (rev 11928)
@@ -138,13 +138,14 @@
@Override
public V remove(final Object key) {
- /* TODO: Implement this. */
throw new UnsupportedOperationException("Operation not supported: remove");
}
@Override
public void putAll(final Map<? extends CharSequence, ? extends V> m) {
- /* TODO: Implement this. */
+ for (Map.Entry<? extends CharSequence, ? extends V> entry : m.entrySet()) {
+ this.put(entry.getKey(), entry.getValue());
+ }
}
@Override
@@ -154,8 +155,7 @@
@Override
public Set<CharSequence> keySet() {
- /* TODO: Implement this. */
- return Collections.emptySet();
+ throw new UnsupportedOperationException("Operation not supported: keySet");
}
@Override
@@ -165,8 +165,7 @@
@Override
public Set<Entry<CharSequence, V>> entrySet() {
- /* TODO: Implement this. */
- return Collections.emptySet();
+ throw new UnsupportedOperationException("Operation not supported: entrySet");
}
/**
Modified: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeMapTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeMapTests.java 2021-10-23 17:55:41 UTC (rev 11927)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeMapTests.java 2021-10-23 18:23:02 UTC (rev 11928)
@@ -30,10 +30,11 @@
import org.junit.Assert;
import org.junit.Before;
-import org.junit.Ignore;
import org.junit.Test;
import java.util.Collection;
+import java.util.HashMap;
+import java.util.Map;
/**
* Tests of {@link TernaryTreeMap}.
@@ -113,9 +114,13 @@
* Test method for {@link org.foray.common.data.TernaryTreeMap#remove(java.lang.Object)}.
*/
@Test
- @Ignore
public void testRemove() {
- Assert.fail("Not yet implemented");
+ try {
+ this.out.remove("Key 1");
+ Assert.fail("Expected an UnsupportedOperationException.");
+ } catch (final UnsupportedOperationException e) {
+ /* This is the expected path. */
+ }
}
/**
@@ -122,9 +127,15 @@
* Test method for {@link org.foray.common.data.TernaryTreeMap#putAll(java.util.Map)}.
*/
@Test
- @Ignore
public void testPutAll() {
- Assert.fail("Not yet implemented");
+ final Map<CharSequence, String> otherMap = new HashMap<CharSequence, String>();
+ otherMap.put("Key 100", "Value 100");
+ otherMap.put("Key 2001", "Value 2001");
+ this.out.putAll(otherMap);
+ Assert.assertEquals(7, out.size());
+ Assert.assertEquals("Value 2", out.get("Key 2"));
+ Assert.assertEquals("Value 100", out.get("Key 100"));
+ Assert.assertEquals("Value 2001", out.get("Key 2001"));
}
/**
@@ -142,9 +153,13 @@
* Test method for {@link org.foray.common.data.TernaryTreeMap#keySet()}.
*/
@Test
- @Ignore
public void testKeySet() {
- Assert.fail("Not yet implemented");
+ try {
+ this.out.keySet();
+ Assert.fail("Expected an UnsupportedOperationException.");
+ } catch (final UnsupportedOperationException e) {
+ /* This is the expected path. */
+ }
}
/**
@@ -162,9 +177,13 @@
* Test method for {@link org.foray.common.data.TernaryTreeMap#entrySet()}.
*/
@Test
- @Ignore
public void testEntrySet() {
- Assert.fail("Not yet implemented");
+ try {
+ this.out.entrySet();
+ Assert.fail("Expected an UnsupportedOperationException.");
+ } catch (final UnsupportedOperationException e) {
+ /* This is the expected path. */
+ }
}
}
Modified: trunk/foray/foray-common/src/test/java/org/foray/common/primitive/StringLatin1Tests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/primitive/StringLatin1Tests.java 2021-10-23 17:55:41 UTC (rev 11927)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/primitive/StringLatin1Tests.java 2021-10-23 18:23:02 UTC (rev 11928)
@@ -29,7 +29,6 @@
package org.foray.common.primitive;
import org.junit.Assert;
-import org.junit.Ignore;
import org.junit.Test;
/**
@@ -41,7 +40,6 @@
* Test of storing and retrieving a Latin-1 string.
*/
@Test
- @Ignore
/* @TODO: This test fails in Java 8, probably because of the new String features, which I think store the
"testString" internally as bytes instead of chars. */
public void test01() {
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-23 17:55:44
|
Revision: 11927
http://sourceforge.net/p/foray/code/11927
Author: victormote
Date: 2021-10-23 17:55:41 +0000 (Sat, 23 Oct 2021)
Log Message:
-----------
Sort some tests by class better. Change helper class to a superclass, so code can be shared.
Modified Paths:
--------------
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesCharTests.java
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTestsHelper.java
Added Paths:
-----------
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesTests.java
Modified: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesCharTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesCharTests.java 2021-10-23 17:37:46 UTC (rev 11926)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesCharTests.java 2021-10-23 17:55:41 UTC (rev 11927)
@@ -34,7 +34,7 @@
/**
* Tests of {@link TernaryNodesChar}.
*/
-public class TernaryNodesCharTests {
+public class TernaryNodesCharTests extends TernaryTreeTestsHelper {
/**
* Test of {@link TernaryNodesChar#cloneAsInt()}.
@@ -46,17 +46,17 @@
map.put("Two", 2);
final TernaryNodesChar charNodes = (TernaryNodesChar) map.getNodes();
Assert.assertEquals(4, charNodes.size());
- TernaryTreeTestsHelper.testNode(charNodes, 0, 0, 0, 0, Character.MIN_VALUE);
- TernaryTreeTestsHelper.testNode(charNodes, 1, 0, 2, 3, 'O');
- TernaryTreeTestsHelper.testNode(charNodes, 2, 1, 1, 0, Character.MAX_VALUE);
- TernaryTreeTestsHelper.testNode(charNodes, 3, 0, 2, 1, Character.MAX_VALUE);
+ testNode(charNodes, 0, 0, 0, 0, Character.MIN_VALUE);
+ testNode(charNodes, 1, 0, 2, 3, 'O');
+ testNode(charNodes, 2, 1, 1, 0, Character.MAX_VALUE);
+ testNode(charNodes, 3, 0, 2, 1, Character.MAX_VALUE);
final TernaryNodesInt intNodes = charNodes.cloneAsInt();
Assert.assertEquals(4, charNodes.size());
- TernaryTreeTestsHelper.testNode(intNodes, 0, 0, 0, 0, Character.MIN_VALUE);
- TernaryTreeTestsHelper.testNode(intNodes, 1, 0, 2, 3, 'O');
- TernaryTreeTestsHelper.testNode(intNodes, 2, 1, 1, 0, Character.MAX_VALUE);
- TernaryTreeTestsHelper.testNode(intNodes, 3, 0, 2, 1, Character.MAX_VALUE);
+ testNode(intNodes, 0, 0, 0, 0, Character.MIN_VALUE);
+ testNode(intNodes, 1, 0, 2, 3, 'O');
+ testNode(intNodes, 2, 1, 1, 0, Character.MAX_VALUE);
+ testNode(intNodes, 3, 0, 2, 1, Character.MAX_VALUE);
}
}
Added: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesTests.java (rev 0)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesTests.java 2021-10-23 17:55:41 UTC (rev 11927)
@@ -0,0 +1,145 @@
+/*
+ * Copyright 2019 The FOray Project.
+ * http://www.foray.org
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * This work is in part derived from the following work(s), used with the
+ * permission of the licensor:
+ * Apache FOP, licensed by the Apache Software Foundation
+ *
+ */
+
+/*
+ * $LastChangedRevision$
+ * $LastChangedDate$
+ * $LastChangedBy$
+ */
+
+package org.foray.common.data;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+public class TernaryNodesTests extends TernaryTreeTestsHelper {
+
+ /**
+ * Test of {@link TernaryNodes#findCharNode(int, char)}.
+ */
+ @Test
+ public void testFindCharNode() {
+ final TernaryTree map = new TernaryTree();
+ map.put("bread", 1001);
+ map.put("brave", 1002);
+ map.put("bravo", 1003);
+ map.put("braver", 1004);
+ map.put("bravery", 1005);
+
+ Assert.assertEquals(13, map.getNodes().size());
+ 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, 1001, 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, 1002, 10, Character.MIN_VALUE);
+ testNode(map, 9, 0, 1003, 2, Character.MAX_VALUE);
+ testNode(map, 10, 0, 11, 0, 'r');
+ testNode(map, 11, 0, 1004, 12, Character.MIN_VALUE);
+ testNode(map, 12, 0, 1005, 4, Character.MAX_VALUE);
+ Assert.assertEquals(5, map.getQtySuffixes());
+ Assert.assertEquals("bread", map.getSuffix(0));
+ Assert.assertEquals("ave", map.getSuffix(1));
+ Assert.assertEquals("o", map.getSuffix(2));
+ Assert.assertEquals("r", map.getSuffix(3));
+ Assert.assertEquals("y", map.getSuffix(4));
+
+ 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'));
+
+ /* Test the iterator. */
+ final Iterator<TernaryNode> nodeIterator = map.getNodes().nodeIterator();
+ final List<TernaryNode> actual = new ArrayList<TernaryNode>();
+ while (nodeIterator.hasNext()) {
+ actual.add(nodeIterator.next());
+ }
+ /* The zero nodes does not get returned by the iterator, so we should have n - 1. */
+ Assert.assertEquals(12, actual.size());
+ Assert.assertEquals(1, actual.get(0).getIndex());
+ Assert.assertEquals(2, actual.get(1).getIndex());
+ Assert.assertEquals(3, actual.get(2).getIndex());
+ Assert.assertEquals(5, actual.get(3).getIndex());
+ Assert.assertEquals(6, actual.get(4).getIndex());
+ Assert.assertEquals(7, actual.get(5).getIndex());
+ Assert.assertEquals(8, actual.get(6).getIndex());
+ Assert.assertEquals(10, actual.get(7).getIndex());
+ Assert.assertEquals(11, actual.get(8).getIndex());
+ Assert.assertEquals(12, actual.get(9).getIndex());
+ Assert.assertEquals(9, actual.get(10).getIndex());
+ Assert.assertEquals(4, actual.get(11).getIndex());
+
+ /* Test the WithParent. */
+ final TernaryNodeParents parents = map.getNodes().getParents();
+ Assert.assertEquals(0, parents.getParent(0));
+ Assert.assertEquals(0, parents.getParent(1));
+ Assert.assertEquals(1, parents.getParent(2));
+ Assert.assertEquals(2, parents.getParent(3));
+ Assert.assertEquals(3, parents.getParent(4));
+ Assert.assertEquals(3, parents.getParent(5));
+ Assert.assertEquals(5, parents.getParent(6));
+ Assert.assertEquals(6, parents.getParent(7));
+ Assert.assertEquals(7, parents.getParent(8));
+ Assert.assertEquals(7, parents.getParent(9));
+ Assert.assertEquals(8, parents.getParent(10));
+ Assert.assertEquals(10, parents.getParent(11));
+ Assert.assertEquals(11, parents.getParent(12));
+
+ Assert.assertEquals("", map.recoverKey(parents, 0));
+ Assert.assertEquals("b", map.recoverKey(parents, 1));
+ Assert.assertEquals("br", map.recoverKey(parents, 2));
+ Assert.assertEquals("bre", map.recoverKey(parents, 3));
+ Assert.assertEquals("bread", map.recoverKey(parents, 4));
+ Assert.assertEquals("bra", map.recoverKey(parents, 5));
+ Assert.assertEquals("brav", map.recoverKey(parents, 6));
+ Assert.assertEquals("brave", map.recoverKey(parents, 7));
+ Assert.assertEquals("brave", map.recoverKey(parents, 8));
+ Assert.assertEquals("bravo", map.recoverKey(parents, 9));
+ Assert.assertEquals("braver", map.recoverKey(parents, 10));
+ Assert.assertEquals("braver", map.recoverKey(parents, 11));
+ Assert.assertEquals("bravery", map.recoverKey(parents, 12));
+ }
+
+}
Property changes on: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesTests.java
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Rev
\ No newline at end of property
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 17:37:46 UTC (rev 11926)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java 2021-10-23 17:55:41 UTC (rev 11927)
@@ -38,7 +38,7 @@
/**
* JUnit test class for the class {@link TernaryTree}.
*/
-public class TernaryTreeTests {
+public class TernaryTreeTests extends TernaryTreeTestsHelper {
/**
* Functional test which adds some key-value pairs to a TernaryTree, then queries the tree, testing the output.
@@ -247,25 +247,6 @@
}
/**
- * Makes assertions about a given node.
- * @param map The tree being tested.
- * @param index The index into {@code map}.
- * @param expectedLow The expected low.
- * @param expectedEqual The expected equal.
- * @param expectedHigh The expected high.
- * @param expectedKeyChar The expected keyChar value.
- */
- private void testNode(final TernaryTree map, final int index, final int expectedLow, final int expectedEqual,
- final int expectedHigh, final char expectedKeyChar) {
- final TernaryNode node = map.getNodes().createNotionalNode(index, null, null);
- Assert.assertEquals(index, node.getIndex());
- Assert.assertEquals(expectedLow, node.getLow());
- Assert.assertEquals(expectedEqual, node.getEqual());
- Assert.assertEquals(expectedHigh, node.getHigh());
- Assert.assertEquals(expectedKeyChar, node.getKeyChar());
- }
-
- /**
* Test of a longer key first, following by a shorter word that is a subset of the longer.
*/
@Test
@@ -319,114 +300,9 @@
}
/**
- * Test of {@link TernaryNodes#findCharNode(int, char)}.
+ * Test of {@link TernaryTree#uncompressNode(int)}.
*/
@Test
- public void testFindCharNode() {
- final TernaryTree map = new TernaryTree();
- map.put("bread", 1001);
- map.put("brave", 1002);
- map.put("bravo", 1003);
- map.put("braver", 1004);
- map.put("bravery", 1005);
-
- Assert.assertEquals(13, map.getNodes().size());
- 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, 1001, 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, 1002, 10, Character.MIN_VALUE);
- testNode(map, 9, 0, 1003, 2, Character.MAX_VALUE);
- testNode(map, 10, 0, 11, 0, 'r');
- testNode(map, 11, 0, 1004, 12, Character.MIN_VALUE);
- testNode(map, 12, 0, 1005, 4, Character.MAX_VALUE);
- Assert.assertEquals(5, map.getQtySuffixes());
- Assert.assertEquals("bread", map.getSuffix(0));
- Assert.assertEquals("ave", map.getSuffix(1));
- Assert.assertEquals("o", map.getSuffix(2));
- Assert.assertEquals("r", map.getSuffix(3));
- Assert.assertEquals("y", map.getSuffix(4));
-
- 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'));
-
- /* Test the iterator. */
- final Iterator<TernaryNode> nodeIterator = map.getNodes().nodeIterator();
- final List<TernaryNode> actual = new ArrayList<TernaryNode>();
- while (nodeIterator.hasNext()) {
- actual.add(nodeIterator.next());
- }
- /* The zero nodes does not get returned by the iterator, so we should have n - 1. */
- Assert.assertEquals(12, actual.size());
- Assert.assertEquals(1, actual.get(0).getIndex());
- Assert.assertEquals(2, actual.get(1).getIndex());
- Assert.assertEquals(3, actual.get(2).getIndex());
- Assert.assertEquals(5, actual.get(3).getIndex());
- Assert.assertEquals(6, actual.get(4).getIndex());
- Assert.assertEquals(7, actual.get(5).getIndex());
- Assert.assertEquals(8, actual.get(6).getIndex());
- Assert.assertEquals(10, actual.get(7).getIndex());
- Assert.assertEquals(11, actual.get(8).getIndex());
- Assert.assertEquals(12, actual.get(9).getIndex());
- Assert.assertEquals(9, actual.get(10).getIndex());
- Assert.assertEquals(4, actual.get(11).getIndex());
-
- /* Test the WithParent. */
- final TernaryNodeParents parents = map.getNodes().getParents();
- Assert.assertEquals(0, parents.getParent(0));
- Assert.assertEquals(0, parents.getParent(1));
- Assert.assertEquals(1, parents.getParent(2));
- Assert.assertEquals(2, parents.getParent(3));
- Assert.assertEquals(3, parents.getParent(4));
- Assert.assertEquals(3, parents.getParent(5));
- Assert.assertEquals(5, parents.getParent(6));
- Assert.assertEquals(6, parents.getParent(7));
- Assert.assertEquals(7, parents.getParent(8));
- Assert.assertEquals(7, parents.getParent(9));
- Assert.assertEquals(8, parents.getParent(10));
- Assert.assertEquals(10, parents.getParent(11));
- Assert.assertEquals(11, parents.getParent(12));
-
- Assert.assertEquals("", map.recoverKey(parents, 0));
- Assert.assertEquals("b", map.recoverKey(parents, 1));
- Assert.assertEquals("br", map.recoverKey(parents, 2));
- Assert.assertEquals("bre", map.recoverKey(parents, 3));
- Assert.assertEquals("bread", map.recoverKey(parents, 4));
- Assert.assertEquals("bra", map.recoverKey(parents, 5));
- Assert.assertEquals("brav", map.recoverKey(parents, 6));
- Assert.assertEquals("brave", map.recoverKey(parents, 7));
- Assert.assertEquals("brave", map.recoverKey(parents, 8));
- Assert.assertEquals("bravo", map.recoverKey(parents, 9));
- Assert.assertEquals("braver", map.recoverKey(parents, 10));
- Assert.assertEquals("braver", map.recoverKey(parents, 11));
- Assert.assertEquals("bravery", map.recoverKey(parents, 12));
- }
-
- /**
- * Test of {@link TernaryNodes#uncompressNode(int)}.
- */
- @Test
public void testUncompressNode() {
/* First some tests with uncompressNode in isolation. */
Modified: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTestsHelper.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTestsHelper.java 2021-10-23 17:37:46 UTC (rev 11926)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTestsHelper.java 2021-10-23 17:55:41 UTC (rev 11927)
@@ -31,13 +31,10 @@
import org.junit.Assert;
/**
- * Helper class for tests of ternary tree classes.
+ * Helper superclass for tests of ternary tree classes.
*/
-public final class TernaryTreeTestsHelper {
+public class TernaryTreeTestsHelper {
- /** Private constructor, should never be instantiated. */
- private TernaryTreeTestsHelper() { }
-
/**
* Makes assertions about a given node.
* @param nodes The nodes being tested.
@@ -47,7 +44,7 @@
* @param expectedHigh The expected high.
* @param expectedKeyChar The expected keyChar value.
*/
- public static void testNode(final TernaryNodes nodes, final int index, final int expectedLow,
+ public void testNode(final TernaryNodes nodes, final int index, final int expectedLow,
final int expectedEqual, final int expectedHigh, final char expectedKeyChar) {
final TernaryNode node = nodes.createNotionalNode(index, null, null);
Assert.assertEquals(index, node.getIndex());
@@ -57,4 +54,23 @@
Assert.assertEquals(expectedKeyChar, node.getKeyChar());
}
+ /**
+ * Makes assertions about a given node.
+ * @param map The tree being tested.
+ * @param index The index into {@code map}.
+ * @param expectedLow The expected low.
+ * @param expectedEqual The expected equal.
+ * @param expectedHigh The expected high.
+ * @param expectedKeyChar The expected keyChar value.
+ */
+ public void testNode(final TernaryTree map, final int index, final int expectedLow, final int expectedEqual,
+ final int expectedHigh, final char expectedKeyChar) {
+ final TernaryNode node = map.getNodes().createNotionalNode(index, null, null);
+ Assert.assertEquals(index, node.getIndex());
+ Assert.assertEquals(expectedLow, node.getLow());
+ Assert.assertEquals(expectedEqual, node.getEqual());
+ Assert.assertEquals(expectedHigh, node.getHigh());
+ Assert.assertEquals(expectedKeyChar, node.getKeyChar());
+ }
+
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-23 17:37:48
|
Revision: 11926
http://sourceforge.net/p/foray/code/11926
Author: victormote
Date: 2021-10-23 17:37:46 +0000 (Sat, 23 Oct 2021)
Log Message:
-----------
Sort some tests by class better.
Modified Paths:
--------------
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java
Added Paths:
-----------
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesCharTests.java
trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTestsHelper.java
Added: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesCharTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesCharTests.java (rev 0)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesCharTests.java 2021-10-23 17:37:46 UTC (rev 11926)
@@ -0,0 +1,62 @@
+/*
+ * Copyright 2021 The FOray Project.
+ * http://www.foray.org
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * This work is in part derived from the following work(s), used with the
+ * permission of the licensor:
+ * Apache FOP, licensed by the Apache Software Foundation
+ *
+ */
+
+/*
+ * $LastChangedRevision$
+ * $LastChangedDate$
+ * $LastChangedBy$
+ */
+
+package org.foray.common.data;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * Tests of {@link TernaryNodesChar}.
+ */
+public class TernaryNodesCharTests {
+
+ /**
+ * Test of {@link TernaryNodesChar#cloneAsInt()}.
+ */
+ @Test
+ public void testCloneAsInt() {
+ final TernaryTree map = new TernaryTree();
+ map.put("One", 1);
+ map.put("Two", 2);
+ final TernaryNodesChar charNodes = (TernaryNodesChar) map.getNodes();
+ Assert.assertEquals(4, charNodes.size());
+ TernaryTreeTestsHelper.testNode(charNodes, 0, 0, 0, 0, Character.MIN_VALUE);
+ TernaryTreeTestsHelper.testNode(charNodes, 1, 0, 2, 3, 'O');
+ TernaryTreeTestsHelper.testNode(charNodes, 2, 1, 1, 0, Character.MAX_VALUE);
+ TernaryTreeTestsHelper.testNode(charNodes, 3, 0, 2, 1, Character.MAX_VALUE);
+
+ final TernaryNodesInt intNodes = charNodes.cloneAsInt();
+ Assert.assertEquals(4, charNodes.size());
+ TernaryTreeTestsHelper.testNode(intNodes, 0, 0, 0, 0, Character.MIN_VALUE);
+ TernaryTreeTestsHelper.testNode(intNodes, 1, 0, 2, 3, 'O');
+ TernaryTreeTestsHelper.testNode(intNodes, 2, 1, 1, 0, Character.MAX_VALUE);
+ TernaryTreeTestsHelper.testNode(intNodes, 3, 0, 2, 1, Character.MAX_VALUE);
+ }
+
+}
Property changes on: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryNodesCharTests.java
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Rev
\ No newline at end of property
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 17:21:06 UTC (rev 11925)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java 2021-10-23 17:37:46 UTC (rev 11926)
@@ -266,25 +266,6 @@
}
/**
- * Makes assertions about a given node.
- * @param nodes The nodes being tested.
- * @param index The index into {@code map}.
- * @param expectedLow The expected low.
- * @param expectedEqual The expected equal.
- * @param expectedHigh The expected high.
- * @param expectedKeyChar The expected keyChar value.
- */
- private void testNode(final TernaryNodes nodes, final int index, final int expectedLow, final int expectedEqual,
- final int expectedHigh, final char expectedKeyChar) {
- final TernaryNode node = nodes.createNotionalNode(index, null, null);
- Assert.assertEquals(index, node.getIndex());
- Assert.assertEquals(expectedLow, node.getLow());
- Assert.assertEquals(expectedEqual, node.getEqual());
- Assert.assertEquals(expectedHigh, node.getHigh());
- Assert.assertEquals(expectedKeyChar, node.getKeyChar());
- }
-
- /**
* Test of a longer key first, following by a shorter word that is a subset of the longer.
*/
@Test
@@ -546,27 +527,4 @@
Assert.assertEquals("a", map.getSuffix(1));
}
- /**
- * Test of {@link TernaryNodesChar#cloneAsInt()}.
- */
- @Test
- public void testCloneAsInt() {
- final TernaryTree map = new TernaryTree();
- map.put("One", 1);
- map.put("Two", 2);
- final TernaryNodesChar charNodes = (TernaryNodesChar) map.getNodes();
- Assert.assertEquals(4, charNodes.size());
- testNode(charNodes, 0, 0, 0, 0, Character.MIN_VALUE);
- testNode(charNodes, 1, 0, 2, 3, 'O');
- testNode(charNodes, 2, 1, 1, 0, Character.MAX_VALUE);
- testNode(charNodes, 3, 0, 2, 1, Character.MAX_VALUE);
-
- final TernaryNodesInt intNodes = charNodes.cloneAsInt();
- Assert.assertEquals(4, charNodes.size());
- testNode(intNodes, 0, 0, 0, 0, Character.MIN_VALUE);
- testNode(intNodes, 1, 0, 2, 3, 'O');
- testNode(intNodes, 2, 1, 1, 0, Character.MAX_VALUE);
- testNode(intNodes, 3, 0, 2, 1, Character.MAX_VALUE);
- }
-
}
Added: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTestsHelper.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTestsHelper.java (rev 0)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTestsHelper.java 2021-10-23 17:37:46 UTC (rev 11926)
@@ -0,0 +1,60 @@
+/*
+ * Copyright 2021 The FOray Project.
+ * http://www.foray.org
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * This work is in part derived from the following work(s), used with the
+ * permission of the licensor:
+ * Apache FOP, licensed by the Apache Software Foundation
+ *
+ */
+
+/*
+ * $LastChangedRevision$
+ * $LastChangedDate$
+ * $LastChangedBy$
+ */
+
+package org.foray.common.data;
+
+import org.junit.Assert;
+
+/**
+ * Helper class for tests of ternary tree classes.
+ */
+public final class TernaryTreeTestsHelper {
+
+ /** Private constructor, should never be instantiated. */
+ private TernaryTreeTestsHelper() { }
+
+ /**
+ * Makes assertions about a given node.
+ * @param nodes The nodes being tested.
+ * @param index The index into {@code map}.
+ * @param expectedLow The expected low.
+ * @param expectedEqual The expected equal.
+ * @param expectedHigh The expected high.
+ * @param expectedKeyChar The expected keyChar value.
+ */
+ public static void testNode(final TernaryNodes nodes, final int index, final int expectedLow,
+ final int expectedEqual, final int expectedHigh, final char expectedKeyChar) {
+ final TernaryNode node = nodes.createNotionalNode(index, null, null);
+ Assert.assertEquals(index, node.getIndex());
+ Assert.assertEquals(expectedLow, node.getLow());
+ Assert.assertEquals(expectedEqual, node.getEqual());
+ Assert.assertEquals(expectedHigh, node.getHigh());
+ Assert.assertEquals(expectedKeyChar, node.getKeyChar());
+ }
+
+}
Property changes on: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTestsHelper.java
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Rev
\ No newline at end of property
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-23 17:21:09
|
Revision: 11925
http://sourceforge.net/p/foray/code/11925
Author: victormote
Date: 2021-10-23 17:21:06 +0000 (Sat, 23 Oct 2021)
Log Message:
-----------
Extract remaining iterator and notional node classes.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.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
Added Paths:
-----------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeIterator.java
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeNode.java
Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java 2021-10-23 16:37:09 UTC (rev 11924)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java 2021-10-23 17:21:06 UTC (rev 11925)
@@ -37,6 +37,9 @@
* Iterates over the nodes of a {@link TernaryNodes} instance in depth-first order, going first to the low branch, then
* the equal branch, then the high branch.
* Nodes are returned only when they are first encountered.
+ * The data returned is <em>not</em> the key/value pairs placed in the tree, but is instead the raw nodes, including
+ * all nodes that are merely connective.
+ * @see TernaryTreeIterator for an iterator over the key/value pairs placed in a tree.
*/
public class TernaryNodesIterator implements Iterator<TernaryNode> {
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 2021-10-23 16:37:09 UTC (rev 11924)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java 2021-10-23 17:21:06 UTC (rev 11925)
@@ -45,7 +45,6 @@
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
-import java.util.Stack;
/**
* <p>A map whose key is always a {@link CharSequence} (usually a {@link String}), and whose value is a char or other
@@ -559,19 +558,16 @@
final String[] keysDump = new String[this.length];
final int[] valuesDump = new int[this.length];
- final KeyValueIterator iter = new KeyValueIterator();
+ final TernaryTreeIterator iter = new TernaryTreeIterator(this);
int i = 0;
while (iter.hasNext()) {
- final KeyValue kv = iter.next();
- valuesDump[i] = kv.getValue();
- keysDump[i] = kv.getKey();
+ final TernaryTreeNode node = iter.next();
+ valuesDump[i] = node.getValue();
+ keysDump[i] = node.getKey();
i++;
}
-
-
-
-
+ /* Reset the data structures, then push the dumped arrays back in, using a balancing algorithm. */
init();
insertBalanced(keysDump, valuesDump, 0, keysDump.length);
// With uniform letter distribution sc[root] should be around 'm'
@@ -701,240 +697,11 @@
* Returns an iterator.
* @return An iterator.
*/
- public Iterator<KeyValue> getIterator() {
- return new KeyValueIterator();
+ public Iterator<TernaryTreeNode> getIterator() {
+ return new TernaryTreeIterator(this);
}
/**
- * A notional Node for the {@link TernaryTree}, just a key-value pair.
- * Instances of this class are expected to be short-lived, and used only by the
- * {@link TernaryTree.KeyValueIterator}.
- */
- public class KeyValue {
-
- /** The key for this node. */
- private String key;
-
- /** The value for this node. */
- private int value;
-
- /**
- * Returns the key.
- * @return The key.
- */
- public String getKey() {
- return this.key;
- }
-
- /**
- * Returns the value.
- * @return The value.
- */
- public int getValue() {
- return this.value;
- }
-
- }
-
- /**
- * An iterator over the conceptual nodes in this tree.
- * Returns the content in order, that is, in Unicode code point order.
- */
- public class KeyValueIterator implements Iterator<KeyValue> {
-
- /** Current node index. */
- private int cur;
-
- /** Current key. */
- private String curkey;
-
- /**
- * Inner class Cloneable implementation.
- */
- private class Item implements Cloneable {
- /** The parent char of the Item. */
- private int parent;
-
- /** The child char of the Item. */
- private int child;
-
- /**
- * No-argument constructor.
- */
- Item() {
- this.parent = 0;
- this.child = 0;
- }
-
- /**
- * Constructor.
- * @param parent Index to the parent node.
- * @param child Index to the child node.
- */
- Item(final int parent, final int child) {
- this.parent = parent;
- this.child = child;
- }
-
- @Override
- public Item clone() {
- return new Item(this.parent, this.child);
- }
-
- }
-
- /** Node stack. */
- private Stack<TernaryTree.KeyValueIterator.Item> ns;
-
- /** Key stack implemented with a StringBuffer. */
- private StringBuilder ks;
-
- /**
- * Constructor.
- */
- public KeyValueIterator() {
- this.cur = -1;
- this.ns = new Stack<TernaryTree.KeyValueIterator.Item>();
- this.ks = new StringBuilder();
- rewind();
- }
-
- /**
- * Rewinds the iterator to point to its first item.
- */
- public void rewind() {
- this.ns.removeAllElements();
- this.ks.setLength(0);
- this.cur = TernaryTree.this.nodes.getRootNodeIndex();
- run();
- }
-
- /**
- * Move up one level in the tree??
- * @return The index to the next level up in the tree??
- */
- private int up() {
- Item i = new Item();
- int res = 0;
-
- if (this.ns.empty()) {
- return -1;
- }
-
- if (this.cur != 0
- && TernaryTree.this.nodes.getKeyChar(this.cur) == 0) {
- return TernaryTree.this.nodes.getLow(this.cur);
- }
-
- boolean climb = true;
-
- while (climb) {
- i = this.ns.pop();
- i.child++;
- switch (i.child) {
- case 1:
- if (TernaryTree.this.nodes.getKeyChar(i.parent) != 0) {
- res = TernaryTree.this.nodes.getEqual(i.parent);
- this.ns.push(i.clone());
- this.ks.append(TernaryTree.this.nodes.getKeyChar(i.parent));
- } else {
- i.child++;
- this.ns.push(i.clone());
- res = TernaryTree.this.nodes.getHigh(i.parent);
- }
- climb = false;
- break;
-
- case 2:
- res = TernaryTree.this.nodes.getHigh(i.parent);
- this.ns.push(i.clone());
- if (this.ks.length() > 0) {
- this.ks.setLength(this.ks.length() - 1); // pop
- }
- climb = false;
- break;
-
- default:
- if (this.ns.empty()) {
- return -1;
- }
- climb = true;
- break;
- }
- }
- return res;
- }
-
- /**
- * Traverse the tree to find next key.
- * @return The index to the next item in the map??
- */
- private int run() {
- if (this.cur == -1) {
- return -1;
- }
-
- boolean leaf = false;
- for (;;) {
- // first go down on low branch until leaf or compressed branch
- while (this.cur != 0) {
- if (TernaryTree.this.nodes.getKeyChar(this.cur) == Character.MAX_VALUE) {
- leaf = true;
- break;
- }
- this.ns.push(new Item(this.cur, '\u0000'));
- if (TernaryTree.this.nodes.getKeyChar(this.cur) == 0) {
- leaf = true;
- break;
- }
- this.cur = TernaryTree.this.nodes.getLow(this.cur);
- }
- if (leaf) {
- break;
- }
- // nothing found, go up one node and try again
- this.cur = up();
- if (this.cur == -1) {
- return -1;
- }
- }
- // The current node should be a data node and
- // the key should be in the key stack (at least partially)
- final StringBuilder buf = new StringBuilder(this.ks.toString());
- if (TernaryTree.this.nodes.getKeyChar(this.cur) == Character.MAX_VALUE) {
- final String suffix = TernaryTree.this.suffixes.get(TernaryTree.this.nodes.getHigh(this.cur));
- final int p = TernaryTree.this.nodes.getLow(this.cur);
- buf.append(suffix.substring(p));
- }
- this.curkey = buf.toString();
- return 0;
- }
-
- @Override
- public boolean hasNext() {
- return this.cur != -1;
- }
-
- @Override
- public KeyValue next() {
- final String res = new String(this.curkey);
- final KeyValue kv = new KeyValue();
- kv.key = res;
- kv.value = TernaryTree.this.nodes.getEqual(this.cur);
- this.cur = up();
- run();
- return kv;
- }
-
- @Override
- public void remove() {
- /* TODO: Implement this. */
- throw new UnsupportedOperationException();
- }
-
- }
-
- /**
* Returns the number of suffixes stored in this tree.
* @return The number of suffixes stored in this tree.
*/
Added: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeIterator.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeIterator.java (rev 0)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeIterator.java 2021-10-23 17:21:06 UTC (rev 11925)
@@ -0,0 +1,237 @@
+/*
+ * Copyright 2021 The FOray Project.
+ * http://www.foray.org
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * This work is in part derived from the following work(s), used with the
+ * permission of the licensor:
+ * Apache FOP, licensed by the Apache Software Foundation
+ *
+ */
+
+/*
+ * $LastChangedRevision$
+ * $LastChangedDate$
+ * $LastChangedBy$
+ */
+
+package org.foray.common.data;
+
+import java.util.Iterator;
+import java.util.Stack;
+
+/**
+ * An iterator over the conceptual nodes in this tree.
+ * The data returned is the key/value pairs that were put into the tree.
+ * This is <em>not</em> the same as the nodes that make up the tree itself, as many of those are connective only.
+ * Returns the content in order, that is, in Unicode code point order.
+ * @see TernaryNodesIterator for an iterator over the actual nodes in the tree itself.
+ */
+public class TernaryTreeIterator implements Iterator<TernaryTreeNode> {
+
+ /** The tree being iterated. */
+ private TernaryTree tree;
+
+ /** Current node index. */
+ private int cur;
+
+ /** Current key. */
+ private String curkey;
+
+ /**
+ * Inner class Cloneable implementation.
+ */
+ private class Item implements Cloneable {
+ /** The parent char of the Item. */
+ private int parent;
+
+ /** The child char of the Item. */
+ private int child;
+
+ /**
+ * No-argument constructor.
+ */
+ Item() {
+ this.parent = 0;
+ this.child = 0;
+ }
+
+ /**
+ * Constructor.
+ * @param parent Index to the parent node.
+ * @param child Index to the child node.
+ */
+ Item(final int parent, final int child) {
+ this.parent = parent;
+ this.child = child;
+ }
+
+ @Override
+ public Item clone() {
+ return new Item(this.parent, this.child);
+ }
+
+ }
+
+ /** Node stack. */
+ private Stack<Item> ns;
+
+ /** Key stack implemented with a StringBuffer. */
+ private StringBuilder ks;
+
+ /**
+ * Constructor.
+ * @param tree The tree to be iterated.
+ */
+ public TernaryTreeIterator(final TernaryTree tree) {
+ this.tree = tree;
+ this.cur = -1;
+ this.ns = new Stack<Item>();
+ this.ks = new StringBuilder();
+ rewind();
+ }
+
+ /**
+ * Rewinds the iterator to point to its first item.
+ */
+ public void rewind() {
+ this.ns.removeAllElements();
+ this.ks.setLength(0);
+ this.cur = tree.getNodes().getRootNodeIndex();
+ run();
+ }
+
+ /**
+ * Move up one level in the tree??
+ * @return The index to the next level up in the tree??
+ */
+ private int up() {
+ Item i = new Item();
+ int res = 0;
+
+ if (this.ns.empty()) {
+ return -1;
+ }
+
+ if (this.cur != 0
+ && tree.getNodes().getKeyChar(this.cur) == 0) {
+ return tree.getNodes().getLow(this.cur);
+ }
+
+ boolean climb = true;
+
+ while (climb) {
+ i = this.ns.pop();
+ i.child++;
+ switch (i.child) {
+ case 1:
+ if (tree.getNodes().getKeyChar(i.parent) != 0) {
+ res = tree.getNodes().getEqual(i.parent);
+ this.ns.push(i.clone());
+ this.ks.append(tree.getNodes().getKeyChar(i.parent));
+ } else {
+ i.child++;
+ this.ns.push(i.clone());
+ res = tree.getNodes().getHigh(i.parent);
+ }
+ climb = false;
+ break;
+
+ case 2:
+ res = tree.getNodes().getHigh(i.parent);
+ this.ns.push(i.clone());
+ if (this.ks.length() > 0) {
+ this.ks.setLength(this.ks.length() - 1); // pop
+ }
+ climb = false;
+ break;
+
+ default:
+ if (this.ns.empty()) {
+ return -1;
+ }
+ climb = true;
+ break;
+ }
+ }
+ return res;
+ }
+
+ /**
+ * Traverse the tree to find next key.
+ * @return The index to the next item in the map??
+ */
+ private int run() {
+ if (this.cur == -1) {
+ return -1;
+ }
+
+ boolean leaf = false;
+ for (;;) {
+ // first go down on low branch until leaf or compressed branch
+ while (this.cur != 0) {
+ if (tree.getNodes().getKeyChar(this.cur) == Character.MAX_VALUE) {
+ leaf = true;
+ break;
+ }
+ this.ns.push(new Item(this.cur, '\u0000'));
+ if (tree.getNodes().getKeyChar(this.cur) == 0) {
+ leaf = true;
+ break;
+ }
+ this.cur = tree.getNodes().getLow(this.cur);
+ }
+ if (leaf) {
+ break;
+ }
+ // nothing found, go up one node and try again
+ this.cur = up();
+ if (this.cur == -1) {
+ return -1;
+ }
+ }
+ // The current node should be a data node and
+ // the key should be in the key stack (at least partially)
+ final StringBuilder buf = new StringBuilder(this.ks.toString());
+ if (tree.getNodes().getKeyChar(this.cur) == Character.MAX_VALUE) {
+ final String suffix = tree.getSuffix(tree.getNodes().getHigh(this.cur));
+ final int p = tree.getNodes().getLow(this.cur);
+ buf.append(suffix.substring(p));
+ }
+ this.curkey = buf.toString();
+ return 0;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return this.cur != -1;
+ }
+
+ @Override
+ public TernaryTreeNode next() {
+ final String key = new String(this.curkey);
+ final int value = tree.getNodes().getEqual(this.cur);
+ final TernaryTreeNode node = new TernaryTreeNode(key, value);
+ this.cur = up();
+ run();
+ return node;
+ }
+
+ @Override
+ public void remove() {
+ /* TODO: Implement this. */
+ throw new UnsupportedOperationException();
+ }
+
+}
Property changes on: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeIterator.java
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Rev
\ No newline at end of property
Added: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeNode.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeNode.java (rev 0)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeNode.java 2021-10-23 17:21:06 UTC (rev 11925)
@@ -0,0 +1,70 @@
+/*
+ * Copyright 2021 The FOray Project.
+ * http://www.foray.org
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * This work is in part derived from the following work(s), used with the
+ * permission of the licensor:
+ * Apache FOP, licensed by the Apache Software Foundation
+ *
+ */
+
+/*
+ * $LastChangedRevision$
+ * $LastChangedDate$
+ * $LastChangedBy$
+ */
+
+package org.foray.common.data;
+
+/**
+ * A notional Node for the {@link TernaryTree}, just a key-value pair.
+ * Instances of this class are expected to be short-lived, and used only by the
+ * {@link TernaryTreeIterator}.
+ */
+public class TernaryTreeNode {
+
+ /** The key for this node. */
+ private String key;
+
+ /** The value for this node. */
+ private int value;
+
+ /**
+ * Constructor.
+ * @param key The key to this notional node.
+ * @param value The value of this notional node.
+ */
+ public TernaryTreeNode(final String key, final int value) {
+ this.key = key;
+ this.value = value;
+ }
+
+ /**
+ * Returns the key.
+ * @return The key.
+ */
+ public String getKey() {
+ return this.key;
+ }
+
+ /**
+ * Returns the value.
+ * @return The value.
+ */
+ public int getValue() {
+ return this.value;
+ }
+
+}
Property changes on: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeNode.java
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Rev
\ No newline at end of property
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 16:37:09 UTC (rev 11924)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java 2021-10-23 17:21:06 UTC (rev 11925)
@@ -228,8 +228,8 @@
map.put("Henry V", 'd');
map.optimize();
- final Iterator<TernaryTree.KeyValue> iterator = map.getIterator();
- final List<TernaryTree.KeyValue> actual = new ArrayList<TernaryTree.KeyValue>();
+ final Iterator<TernaryTreeNode> iterator = map.getIterator();
+ final List<TernaryTreeNode> actual = new ArrayList<TernaryTreeNode>();
while (iterator.hasNext()) {
actual.add(iterator.next());
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-23 16:37:11
|
Revision: 11924
http://sourceforge.net/p/foray/code/11924
Author: victormote
Date: 2021-10-23 16:37:09 +0000 (Sat, 23 Oct 2021)
Log Message:
-----------
Extract WithParents class into a separate file.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.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
Added Paths:
-----------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodeParents.java
Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java 2021-10-23 16:11:49 UTC (rev 11923)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java 2021-10-23 16:37:09 UTC (rev 11924)
@@ -28,7 +28,6 @@
package org.foray.common.data;
-import org.foray.common.data.TernaryNodes.WithParents;
import org.foray.common.primitive.CharacterUtils;
/**
@@ -82,10 +81,10 @@
* @param nodes The container of the node data.
* @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.
+ * @param parents The {@link TernaryNodeParents} instance. This can be null.
*/
public TernaryNode(final TernaryNodes nodes, final int index, final CharSequence key,
- final WithParents withParents) {
+ final TernaryNodeParents parents) {
this.index = index;
this.low = nodes.getLow(index);
this.equal = nodes.getEqual(index);
@@ -92,8 +91,8 @@
this.high = nodes.getHigh(index);
this.keyChar = nodes.getKeyChar(index);
this.key = key;
- if (withParents != null) {
- this.parent = withParents.getParent(index);
+ if (parents != null) {
+ this.parent = parents.getParent(index);
}
}
Added: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodeParents.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodeParents.java (rev 0)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodeParents.java 2021-10-23 16:37:09 UTC (rev 11924)
@@ -0,0 +1,136 @@
+/*
+ * Copyright 2021 The FOray Project.
+ * http://www.foray.org
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * This work is in part derived from the following work(s), used with the
+ * permission of the licensor:
+ * Apache FOP, licensed by the Apache Software Foundation
+ *
+ */
+
+/*
+ * $LastChangedRevision$
+ * $LastChangedDate$
+ * $LastChangedBy$
+ */
+
+package org.foray.common.data;
+
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * Sister class for {@link TernaryNodes} that provides the parent for each node in that tree.
+ * This is probably only useful for debugging, as we would ordinarily not want to spend the memory to keep track of
+ * the parent node.
+ */
+public class TernaryNodeParents {
+
+ /** The array of parent values. */
+ private int[] parents;
+
+ /** The logger. */
+ private transient Logger logger = LoggerFactory.getLogger(this.getClass());
+
+ /**
+ * Constructor.
+ * Finds the parent for each node.
+ * @param nodes The nodes for which parent data should be gathered.
+ */
+ public TernaryNodeParents(final TernaryNodes nodes) {
+ final String multipleParentFormat = "Index %d, referenced from Index %d, already has parent Index %d";
+ this.parents = new int[nodes.size()];
+
+ /* Start at index 1. Index 0 doesn't point anywhere. */
+ for (int index = 1; index < this.parents.length; index++) {
+ final int lowPointer = nodes.getLowPointer(index);
+ if (lowPointer != 0) {
+ if (this.parents[lowPointer] == 0) {
+ this.parents[lowPointer] = index;
+ } else {
+ this.logger.error(
+ String.format(multipleParentFormat, lowPointer, index, this.parents[lowPointer]));
+ }
+ }
+ final int equalPointer = nodes.getEqualPointer(index);
+ if (equalPointer != 0) {
+ if (this.parents[equalPointer] == 0) {
+ this.parents[equalPointer] = index;
+ } else {
+ this.logger.error(
+ String.format(multipleParentFormat, equalPointer, index, this.parents[equalPointer]));
+ }
+ }
+ final int highPointer = nodes.getHighPointer(index);
+ if (highPointer != 0) {
+ if (this.parents[highPointer] == 0) {
+ this.parents[highPointer] = index;
+ } else {
+ this.logger.error(
+ String.format(multipleParentFormat, highPointer, index, this.parents[highPointer]));
+ }
+ }
+ }
+
+ /* Nodes 0 and 1 should not have parents... */
+ if (parents[0] != 0) {
+ this.logger.error("Index 0 should have no parent.");
+ }
+ if (parents[1] != 0) {
+ this.logger.error("Index 1 should have no parent.");
+ }
+
+ /* ... but everybody else should, unless they are orphaned. */
+ int start = -1;
+ int end = -1;
+ for (int index = 2; index < this.parents.length; index ++) {
+ if (parents[index] == 0) {
+ if (start < 0) {
+ start = index;
+ end = index;
+ } else if (index == end + 1) {
+ end = index;
+ } else if (start == end) {
+ this.logger.error("Index " + start + " has no parent.");
+ start = index;
+ end = index;
+ } else {
+ this.logger.error(
+ "Indexes " + start + " through " + end + " have no parent.");
+ start = index;
+ end = index;
+ }
+ }
+ }
+ if (start > -1) {
+ if (start == end) {
+ this.logger.error("Index " + start + " has no parent.");
+ } else {
+ this.logger.error("Indexes " + start + " through " + end + " have no parent.");
+ }
+
+ }
+ }
+
+ /**
+ * Returns the parent index for a given index.
+ * @param index The index of the child whose parent should be returned.
+ * @return The index to the parent of the child at {@code index}.
+ */
+ public int getParent(final int index) {
+ return this.parents[index];
+ }
+
+}
Property changes on: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodeParents.java
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Rev
\ No newline at end of property
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 16:11:49 UTC (rev 11923)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java 2021-10-23 16:37:09 UTC (rev 11924)
@@ -63,105 +63,6 @@
/** The logger. */
private transient Logger logger = LoggerFactory.getLogger(this.getClass());
- /**
- * Sister class for {@link TernaryNodes} that provides the parent for each node in that tree.
- * This is probably only useful for debugging, as we would ordinarily not want to spend the memory to keep track of
- * the parent node.
- */
- public class WithParents {
-
- /** The array of parent values. */
- private int[] parents = new int[TernaryNodes.this.size()];
-
- /**
- * Constructor.
- * Finds the parent for each node.
- */
- public WithParents() {
- final String multipleParentFormat = "Index %d, referenced from Index %d, already has parent Index %d";
-
- /* Start at index 1. Index 0 doesn't point anywhere. */
- for (int index = 1; index < this.parents.length; index++) {
- final int lowPointer = TernaryNodes.this.getLowPointer(index);
- if (lowPointer != 0) {
- if (this.parents[lowPointer] == 0) {
- this.parents[lowPointer] = index;
- } else {
- TernaryNodes.this.logger.error(
- String.format(multipleParentFormat, lowPointer, index, this.parents[lowPointer]));
- }
- }
- final int equalPointer = TernaryNodes.this.getEqualPointer(index);
- if (equalPointer != 0) {
- if (this.parents[equalPointer] == 0) {
- this.parents[equalPointer] = index;
- } else {
- TernaryNodes.this.logger.error(
- String.format(multipleParentFormat, equalPointer, index, this.parents[equalPointer]));
- }
- }
- final int highPointer = TernaryNodes.this.getHighPointer(index);
- if (highPointer != 0) {
- if (this.parents[highPointer] == 0) {
- this.parents[highPointer] = index;
- } else {
- TernaryNodes.this.logger.error(
- String.format(multipleParentFormat, highPointer, index, this.parents[highPointer]));
- }
- }
- }
-
- /* Nodes 0 and 1 should not have parents... */
- if (parents[0] != 0) {
- TernaryNodes.this.logger.error("Index 0 should have no parent.");
- }
- if (parents[1] != 0) {
- TernaryNodes.this.logger.error("Index 1 should have no parent.");
- }
-
- /* ... but everybody else should, unless they are orphaned. */
- int start = -1;
- int end = -1;
- for (int index = 2; index < this.parents.length; index ++) {
- if (parents[index] == 0) {
- if (start < 0) {
- start = index;
- end = index;
- } else if (index == end + 1) {
- end = index;
- } else if (start == end) {
- TernaryNodes.this.logger.error("Index " + start + " has no parent.");
- start = index;
- end = index;
- } else {
- TernaryNodes.this.logger.error(
- "Indexes " + start + " through " + end + " have no parent.");
- start = index;
- end = index;
- }
- }
- }
- if (start > -1) {
- if (start == end) {
- TernaryNodes.this.logger.error("Index " + start + " has no parent.");
- } else {
- TernaryNodes.this.logger.error("Indexes " + start + " through " + end + " have no parent.");
- }
-
- }
- }
-
- /**
- * Returns the parent index for a given index.
- * @param index The index of the child whose parent should be returned.
- * @return The index to the parent of the child at {@code index}.
- */
- public int getParent(final int index) {
- return this.parents[index];
- }
-
- }
-
/** The index to the next available node. */
private int freenode;
@@ -354,11 +255,11 @@
* 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.
+ * @param parents An optional {@link TernaryNodeParents}. This can be null.
* @return A new Node instance containing the data for the reqested node.
*/
- TernaryNode createNotionalNode(final int index, final CharSequence key, final WithParents withParents) {
- return new TernaryNode(this, index, key, withParents);
+ TernaryNode createNotionalNode(final int index, final CharSequence key, final TernaryNodeParents parents) {
+ return new TernaryNode(this, index, key, parents);
}
/**
@@ -482,10 +383,9 @@
* Useful for tests.
*/
public void dumpTree() {
- WithParents withParents = null;
- withParents = withParents();
+ final TernaryNodeParents parents = getParents();
for (int index = 0; index < size(); index ++) {
- final TernaryNode node = createNotionalNode(index, null, withParents);
+ final TernaryNode node = createNotionalNode(index, null, parents);
this.logger.info(node.toString());
}
this.logger.info("-----------------------------------------------------------------------------------------");
@@ -541,8 +441,8 @@
* Returns an object containing the parents for each node in this instance.
* @return The parents.
*/
- public WithParents withParents() {
- return new WithParents();
+ public TernaryNodeParents getParents() {
+ return new TernaryNodeParents(this);
}
/**
@@ -611,9 +511,9 @@
return false;
}
}
- /* For now, most of the testing is done with the WithParents class. Just create an instance of it and catch
- * Exceptions thrown by it. */
- this.withParents();
+ /* For now, most of the testing is done with the TernaryNodeParents class. Just create an instance of it and
+ * catch Exceptions thrown by it. */
+ this.getParents();
return true;
}
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 2021-10-23 16:11:49 UTC (rev 11923)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java 2021-10-23 16:37:09 UTC (rev 11924)
@@ -955,11 +955,11 @@
/**
* Recovers the key to a given node by first finding the parents for each node, then going back up the tree to
* reconstruct the String.
- * @param withParents The nodes, along with their parents, needed to recover the key.
+ * @param parents The nodes, along with their parents, needed to recover the key.
* @param index The index whose key is wanted.
* @return The String that is the key to {@code index}.
*/
- public String recoverKey(final TernaryNodes.WithParents withParents, final int index) {
+ public String recoverKey(final TernaryNodeParents parents, final int index) {
final StringBuilder builder = new StringBuilder();
final TernaryNodes nodes = this.getNodes();
int currentIndex = index;
@@ -972,10 +972,10 @@
builder.insert(0, nodes.getKeyChar(currentIndex));
}
- int parentIndex = withParents.getParent(currentIndex);
+ int parentIndex = parents.getParent(currentIndex);
while (currentIndex != nodes.getEqual(parentIndex)) {
currentIndex = parentIndex;
- parentIndex = withParents.getParent(currentIndex);
+ parentIndex = parents.getParent(currentIndex);
}
currentIndex = parentIndex;
}
@@ -984,17 +984,17 @@
/**
* For a given index, recovers its key, then iteratively recovers its parent keys until it reaches the root.
- * @param withParents The nodes, along with their parents, needed to recover the keys.
+ * @param parents The nodes, along with their parents, needed to recover the keys.
* @param index The starting index.
*/
- public void dumpKeyPath(final TernaryNodes.WithParents withParents, final int index) {
+ public void dumpKeyPath(final TernaryNodeParents parents, final int index) {
final String format = "Index: %6d, Key: %s";
int nextIndex = index;
while (nextIndex > 0) {
- final String key = this.recoverKey(withParents, nextIndex);
+ final String key = this.recoverKey(parents, nextIndex);
final String message = String.format(format, nextIndex, key);
logger.info(message);
- nextIndex = withParents.getParent(nextIndex);
+ nextIndex = parents.getParent(nextIndex);
}
}
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 16:11:49 UTC (rev 11923)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java 2021-10-23 16:37:09 UTC (rev 11924)
@@ -412,34 +412,34 @@
Assert.assertEquals(4, actual.get(11).getIndex());
/* Test the WithParent. */
- final TernaryNodes.WithParents withParents = map.getNodes().withParents();
- Assert.assertEquals(0, withParents.getParent(0));
- Assert.assertEquals(0, withParents.getParent(1));
- Assert.assertEquals(1, withParents.getParent(2));
- Assert.assertEquals(2, withParents.getParent(3));
- Assert.assertEquals(3, withParents.getParent(4));
- Assert.assertEquals(3, withParents.getParent(5));
- Assert.assertEquals(5, withParents.getParent(6));
- Assert.assertEquals(6, withParents.getParent(7));
- Assert.assertEquals(7, withParents.getParent(8));
- Assert.assertEquals(7, withParents.getParent(9));
- Assert.assertEquals(8, withParents.getParent(10));
- Assert.assertEquals(10, withParents.getParent(11));
- Assert.assertEquals(11, withParents.getParent(12));
+ final TernaryNodeParents parents = map.getNodes().getParents();
+ Assert.assertEquals(0, parents.getParent(0));
+ Assert.assertEquals(0, parents.getParent(1));
+ Assert.assertEquals(1, parents.getParent(2));
+ Assert.assertEquals(2, parents.getParent(3));
+ Assert.assertEquals(3, parents.getParent(4));
+ Assert.assertEquals(3, parents.getParent(5));
+ Assert.assertEquals(5, parents.getParent(6));
+ Assert.assertEquals(6, parents.getParent(7));
+ Assert.assertEquals(7, parents.getParent(8));
+ Assert.assertEquals(7, parents.getParent(9));
+ Assert.assertEquals(8, parents.getParent(10));
+ Assert.assertEquals(10, parents.getParent(11));
+ Assert.assertEquals(11, parents.getParent(12));
- Assert.assertEquals("", map.recoverKey(withParents, 0));
- Assert.assertEquals("b", map.recoverKey(withParents, 1));
- Assert.assertEquals("br", map.recoverKey(withParents, 2));
- Assert.assertEquals("bre", map.recoverKey(withParents, 3));
- Assert.assertEquals("bread", map.recoverKey(withParents, 4));
- Assert.assertEquals("bra", map.recoverKey(withParents, 5));
- Assert.assertEquals("brav", map.recoverKey(withParents, 6));
- Assert.assertEquals("brave", map.recoverKey(withParents, 7));
- Assert.assertEquals("brave", map.recoverKey(withParents, 8));
- Assert.assertEquals("bravo", map.recoverKey(withParents, 9));
- Assert.assertEquals("braver", map.recoverKey(withParents, 10));
- Assert.assertEquals("braver", map.recoverKey(withParents, 11));
- Assert.assertEquals("bravery", map.recoverKey(withParents, 12));
+ Assert.assertEquals("", map.recoverKey(parents, 0));
+ Assert.assertEquals("b", map.recoverKey(parents, 1));
+ Assert.assertEquals("br", map.recoverKey(parents, 2));
+ Assert.assertEquals("bre", map.recoverKey(parents, 3));
+ Assert.assertEquals("bread", map.recoverKey(parents, 4));
+ Assert.assertEquals("bra", map.recoverKey(parents, 5));
+ Assert.assertEquals("brav", map.recoverKey(parents, 6));
+ Assert.assertEquals("brave", map.recoverKey(parents, 7));
+ Assert.assertEquals("brave", map.recoverKey(parents, 8));
+ Assert.assertEquals("bravo", map.recoverKey(parents, 9));
+ Assert.assertEquals("braver", map.recoverKey(parents, 10));
+ Assert.assertEquals("braver", map.recoverKey(parents, 11));
+ Assert.assertEquals("bravery", map.recoverKey(parents, 12));
}
/**
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-23 16:11:52
|
Revision: 11923
http://sourceforge.net/p/foray/code/11923
Author: victormote
Date: 2021-10-23 16:11:49 +0000 (Sat, 23 Oct 2021)
Log Message:
-----------
Extract iterator class.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java
Added Paths:
-----------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.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 15:49:47 UTC (rev 11922)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java 2021-10-23 16:11:49 UTC (rev 11923)
@@ -28,9 +28,6 @@
package org.foray.common.data;
-import org.foray.common.sequence.CharArrayBuilder;
-import org.foray.common.sequence.IntArrayBuilder;
-
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
@@ -67,111 +64,6 @@
private transient Logger logger = LoggerFactory.getLogger(this.getClass());
/**
- * 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<TernaryNode> {
-
- /** The stack of indexes. Index 1 should be at the bottom of the stack until finished. The current index is at
- * the top. */
- private IntArrayBuilder currentIndexStack = new IntArrayBuilder();
-
- /** 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;
-
- /**
- * Constructor.
- */
- public DepthFirstIterator() {
- if (TernaryNodes.this.size() > 1) {
- this.currentIndexStack.push(1);
- this.nextIndex = 1;
- this.currentBranchStack.push(-1 - 1);
- this.charStack.push(TernaryNodes.this.keyChar[1]);
- }
- }
-
- @Override
- public boolean hasNext() {
- return this.nextIndex > -1;
- }
-
- @Override
- public TernaryNode next() {
- final TernaryNode returnValue = new TernaryNode(TernaryNodes.this, this.nextIndex,
- this.charStack.toString(), null);
-
- /* Tee up the one after this, if any. */
- this.nextIndex = -1;
-
- indexLoop:
- while (this.currentIndexStack.length() > 0
- && this.nextIndex < 0) {
- final int currentIndex = this.currentIndexStack.peek();
- int currentBranch = this.currentBranchStack.pop();
- currentBranch ++;
- this.currentBranchStack.push(currentBranch);
-
- while (currentBranch < 2) {
- int branchIndex = -1;
- switch (this.currentBranchStack.peek()) {
- case -1: {
- branchIndex = TernaryNodes.this.getLowPointer(currentIndex);
- break;
- }
- case 0: {
- branchIndex = TernaryNodes.this.getEqualPointer(currentIndex);
- break;
- }
- case 1: {
- branchIndex = TernaryNodes.this.getHighPointer(currentIndex);
- break;
- }
- default: {
- throw new IllegalStateException("Unexpected branch value: " + this.currentBranchStack.peek());
- }
- }
- if (branchIndex > 0) {
- /* 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;
- } else {
- /* Increment the current branch. */
- currentBranch = this.currentBranchStack.pop() + 1;
- this.currentBranchStack.push(currentBranch);
- }
- }
- /* We have processed all of the branches on the current index. Pop all stacks. */
- this.currentIndexStack.pop();
- this.currentBranchStack.pop();
- this.charStack.pop();
- }
-
- return returnValue;
- }
-
- @Override
- public void remove() {
- throw new UnsupportedOperationException();
- }
-
- }
-
- /**
* Sister class for {@link TernaryNodes} that provides the parent for each node in that tree.
* This is probably only useful for debugging, as we would ordinarily not want to spend the memory to keep track of
* the parent node.
@@ -642,7 +534,7 @@
* @return A new iterator.
*/
public Iterator<TernaryNode> nodeIterator() {
- return new DepthFirstIterator();
+ return new TernaryNodesIterator(this);
}
/**
Added: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java (rev 0)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java 2021-10-23 16:11:49 UTC (rev 11923)
@@ -0,0 +1,145 @@
+/*
+ * Copyright 2021 The FOray Project.
+ * http://www.foray.org
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * This work is in part derived from the following work(s), used with the
+ * permission of the licensor:
+ * Apache FOP, licensed by the Apache Software Foundation
+ *
+ */
+
+/*
+ * $LastChangedRevision$
+ * $LastChangedDate$
+ * $LastChangedBy$
+ */
+
+package org.foray.common.data;
+
+import org.foray.common.sequence.CharArrayBuilder;
+import org.foray.common.sequence.IntArrayBuilder;
+
+import java.util.Iterator;
+
+/**
+ * Iterates over the nodes of a {@link TernaryNodes} instance in depth-first order, going first to the low branch, then
+ * the equal branch, then the high branch.
+ * Nodes are returned only when they are first encountered.
+ */
+public class TernaryNodesIterator implements Iterator<TernaryNode> {
+
+ /** The nodes being iterated. */
+ private TernaryNodes nodes;
+
+ /** The stack of indexes. Index 1 should be at the bottom of the stack until finished. The current index is at
+ * the top. */
+ private IntArrayBuilder currentIndexStack = new IntArrayBuilder();
+
+ /** 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;
+
+ /**
+ * Constructor.
+ * @param nodes The nodes being iterated.
+ */
+ public TernaryNodesIterator(final TernaryNodes nodes) {
+ this.nodes = nodes;
+ if (nodes.size() > 1) {
+ this.currentIndexStack.push(1);
+ this.nextIndex = 1;
+ this.currentBranchStack.push(-1 - 1);
+ this.charStack.push(nodes.getKeyChar(1));
+ }
+ }
+
+ @Override
+ public boolean hasNext() {
+ return this.nextIndex > -1;
+ }
+
+ @Override
+ public TernaryNode next() {
+ final TernaryNode returnValue = new TernaryNode(this.nodes, this.nextIndex,
+ this.charStack.toString(), null);
+
+ /* Tee up the one after this, if any. */
+ this.nextIndex = -1;
+
+ indexLoop:
+ while (this.currentIndexStack.length() > 0
+ && this.nextIndex < 0) {
+ final int currentIndex = this.currentIndexStack.peek();
+ int currentBranch = this.currentBranchStack.pop();
+ currentBranch ++;
+ this.currentBranchStack.push(currentBranch);
+
+ while (currentBranch < 2) {
+ int branchIndex = -1;
+ switch (this.currentBranchStack.peek()) {
+ case -1: {
+ branchIndex = this.nodes.getLowPointer(currentIndex);
+ break;
+ }
+ case 0: {
+ branchIndex = this.nodes.getEqualPointer(currentIndex);
+ break;
+ }
+ case 1: {
+ branchIndex = this.nodes.getHighPointer(currentIndex);
+ break;
+ }
+ default: {
+ throw new IllegalStateException("Unexpected branch value: " + this.currentBranchStack.peek());
+ }
+ }
+ if (branchIndex > 0) {
+ /* Push the found index onto the stack. */
+ this.currentIndexStack.push(branchIndex);
+ this.currentBranchStack.push(-1 - 1);
+ this.charStack.push(this.nodes.getKeyChar(branchIndex));
+ /* The new index is the next item to be processed. */
+ this.nextIndex = branchIndex;
+ break indexLoop;
+ } else {
+ /* Increment the current branch. */
+ currentBranch = this.currentBranchStack.pop() + 1;
+ this.currentBranchStack.push(currentBranch);
+ }
+ }
+ /* We have processed all of the branches on the current index. Pop all stacks. */
+ this.currentIndexStack.pop();
+ this.currentBranchStack.pop();
+ this.charStack.pop();
+ }
+
+ return returnValue;
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+}
Property changes on: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesIterator.java
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Rev
\ No newline at end of property
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-23 15:49:49
|
Revision: 11922
http://sourceforge.net/p/foray/code/11922
Author: victormote
Date: 2021-10-23 15:49:47 +0000 (Sat, 23 Oct 2021)
Log Message:
-----------
1. Move NodeType enum to the Node class. 2. Remove unused Exception class.
Modified Paths:
--------------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java
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/TernaryNode.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java 2021-10-23 15:31:49 UTC (rev 11921)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java 2021-10-23 15:49:47 UTC (rev 11922)
@@ -37,6 +37,21 @@
*/
public class TernaryNode {
+ /**
+ * Enumeration of the valid node types.
+ */
+ public enum Type {
+
+ /** The key char in the node is a valid Unicode character. */
+ CHARACTER,
+
+ /** The key char in the node is 0xFFFF, marking a compressed key node. */
+ COMPRESSED_VALUE,
+
+ /** The key char in the node is 0x0000, marking an uncompressed value node. */
+ UNCOMPRESSED_VALUE;
+ }
+
/** Format string for {@link #toString()}. */
private static final String TO_STRING_FORMAT =
"index: %5d, low: %5d, equal: %5d, high: %5d, key char: %4x %s, parent: %5d, key: %6s";
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 15:31:49 UTC (rev 11921)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java 2021-10-23 15:49:47 UTC (rev 11922)
@@ -67,53 +67,6 @@
private transient Logger logger = LoggerFactory.getLogger(this.getClass());
/**
- * Enumeration of the valid node types.
- */
- public enum NodeType {
-
- /** The key char in the node is a valid Unicode character. */
- CHARACTER,
-
- /** The key char in the node is 0xFFFF, marking a compressed key node. */
- COMPRESSED_VALUE,
-
- /** The key char in the node is 0x0000, marking an uncompressed value node. */
- UNCOMPRESSED_VALUE;
- }
-
- /**
- * Exception class that can be used to report a consistency problem in the tree.
- */
- public class InconsistentTreeException extends Exception {
-
- /** Constant needed for serialization. */
- private static final long serialVersionUID = -7811983575599941811L;
-
- /**
- * See superclass doc.
- */
- public InconsistentTreeException() {
- super();
- }
-
- /**
- * See superclass doc.
- * @param message The message for the exception.
- */
- public InconsistentTreeException(final String message) {
- super(message);
- }
- }
-
- /**
- * A notional Node for {@link TernaryNodes}, useful mostly for iterators and debugging.
- * Instances of this class are expected to be short-lived and used only for those purposes.
- */
- public class Node {
-
- }
-
- /**
* Iterates over the nodes in depth-first order, going first to the low branch, then the equal branch, then the
* high branch.
*/
@@ -560,7 +513,7 @@
* @return True if and only if the node is an uncompressed node matching the {@code theChar}.
*/
boolean isCharNode(final int index) {
- return getNodeType(index) == NodeType.CHARACTER;
+ return getNodeType(index) == TernaryNode.Type.CHARACTER;
}
/**
@@ -609,7 +562,7 @@
}
}
if (returnValue != -1
- && getNodeType(returnValue) == NodeType.UNCOMPRESSED_VALUE) {
+ && getNodeType(returnValue) == TernaryNode.Type.UNCOMPRESSED_VALUE) {
throw new IllegalStateException();
}
return returnValue;
@@ -638,11 +591,7 @@
*/
public void dumpTree() {
WithParents withParents = null;
- try {
- withParents = withParents();
- } catch (final InconsistentTreeException e) {
- this.logger.error("Inconsistent Tree", e);
- }
+ withParents = withParents();
for (int index = 0; index < size(); index ++) {
final TernaryNode node = createNotionalNode(index, null, withParents);
this.logger.info(node.toString());
@@ -679,12 +628,12 @@
* @param index The node index.
* @return The type of node at {@code index}.
*/
- public NodeType getNodeType(final int index) {
+ public TernaryNode.Type getNodeType(final int index) {
final char keyChar = this.keyChar[index];
switch(keyChar) {
- case Character.MIN_VALUE: return NodeType.UNCOMPRESSED_VALUE;
- case Character.MAX_VALUE: return NodeType.COMPRESSED_VALUE;
- default: return NodeType.CHARACTER;
+ case Character.MIN_VALUE: return TernaryNode.Type.UNCOMPRESSED_VALUE;
+ case Character.MAX_VALUE: return TernaryNode.Type.COMPRESSED_VALUE;
+ default: return TernaryNode.Type.CHARACTER;
}
}
@@ -699,9 +648,8 @@
/**
* Returns an object containing the parents for each node in this instance.
* @return The parents.
- * @throws InconsistentTreeException If exceptions are found while walking the tree.
*/
- public WithParents withParents() throws InconsistentTreeException {
+ public WithParents withParents() {
return new WithParents();
}
@@ -773,12 +721,7 @@
}
/* For now, most of the testing is done with the WithParents class. Just create an instance of it and catch
* Exceptions thrown by it. */
- try {
- this.withParents();
- } catch (final InconsistentTreeException e) {
- this.logger.error("", e);
- return false;
- }
+ this.withParents();
return true;
}
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 15:31:49 UTC (rev 11921)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java 2021-10-23 15:49:47 UTC (rev 11922)
@@ -28,8 +28,6 @@
package org.foray.common.data;
-import org.foray.common.data.TernaryNodes.InconsistentTreeException;
-
import org.junit.Assert;
import org.junit.Test;
@@ -341,10 +339,9 @@
/**
* Test of {@link TernaryNodes#findCharNode(int, char)}.
- * @throws InconsistentTreeException Not expected here.
*/
@Test
- public void testFindCharNode() throws InconsistentTreeException {
+ public void testFindCharNode() {
final TernaryTree map = new TernaryTree();
map.put("bread", 1001);
map.put("brave", 1002);
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <vic...@us...> - 2021-10-23 15:31:52
|
Revision: 11921
http://sourceforge.net/p/foray/code/11921
Author: victormote
Date: 2021-10-23 15:31:49 +0000 (Sat, 23 Oct 2021)
Log Message:
-----------
Extract the notional Node class into a separate file.
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
Added Paths:
-----------
trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java
Added: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java (rev 0)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java 2021-10-23 15:31:49 UTC (rev 11921)
@@ -0,0 +1,172 @@
+/*
+ * Copyright 2021 The FOray Project.
+ * http://www.foray.org
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * This work is in part derived from the following work(s), used with the
+ * permission of the licensor:
+ * Apache FOP, licensed by the Apache Software Foundation
+ *
+ */
+
+/*
+ * $LastChangedRevision$
+ * $LastChangedDate$
+ * $LastChangedBy$
+ */
+
+package org.foray.common.data;
+
+import org.foray.common.data.TernaryNodes.WithParents;
+import org.foray.common.primitive.CharacterUtils;
+
+/**
+ * A notional Node for {@link TernaryNodes}, useful mostly for iterators and debugging.
+ * Instances of this class are expected to be short-lived and used only for those purposes.
+ */
+public class TernaryNode {
+
+ /** Format string for {@link #toString()}. */
+ private static final String TO_STRING_FORMAT =
+ "index: %5d, low: %5d, equal: %5d, high: %5d, key char: %4x %s, parent: %5d, key: %6s";
+
+ /** The index for this node. */
+ private int index;
+
+ /** The low for this node. */
+ private int low;
+
+ /** The equal for this node. */
+ private int equal;
+
+ /** The high for this node. */
+ private int high;
+
+ /** The keyChar for this node. */
+ private char keyChar;
+
+ /** 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 nodes The container of the node data.
+ * @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 TernaryNode(final TernaryNodes nodes, final int index, final CharSequence key,
+ final WithParents withParents) {
+ this.index = index;
+ this.low = nodes.getLow(index);
+ this.equal = nodes.getEqual(index);
+ this.high = nodes.getHigh(index);
+ this.keyChar = nodes.getKeyChar(index);
+ this.key = key;
+ if (withParents != null) {
+ this.parent = withParents.getParent(index);
+ }
+ }
+
+ /**
+ * Returns the index.
+ * @return The index.
+ */
+ public int getIndex() {
+ return this.index;
+ }
+
+ /**
+ * Returns the low.
+ * @return The low.
+ */
+ public int getLow() {
+ return this.low;
+ }
+
+ /**
+ * Returns the equal.
+ * @return The equal.
+ */
+ public int getEqual() {
+ return this.equal;
+ }
+
+ /**
+ * Returns the high.
+ * @return The high.
+ */
+ public int getHigh() {
+ return this.high;
+ }
+
+ /**
+ * Returns the keyChar.
+ * @return The keyChar.
+ */
+ public char getKeyChar() {
+ return this.keyChar;
+ }
+
+ /**
+ * Returns the index to the parent node, if known.
+ * @return The high.
+ */
+ public int getParent() {
+ 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;
+ if (printableChar < ' '
+ || printableChar > CharacterUtils.MAX_PRINTABLE_ASCII_CHAR) {
+ printableChar = ' ';
+ }
+ return String.format(TO_STRING_FORMAT,
+ this.index, this.low, this.equal, this.high, (int) this.keyChar, printableChar, this.parent,
+ this.key);
+ }
+
+ @Override
+ public boolean equals(final Object other) {
+ if (other == this) {
+ return true;
+ }
+ if (! (other instanceof TernaryNode)) {
+ return false;
+ }
+ final TernaryNode otherNode = (TernaryNode) other;
+ if (this.index != otherNode.index
+ || this.low != otherNode.low
+ || this.equal != otherNode.equal
+ || this.high != otherNode.high
+ || this.keyChar != otherNode.keyChar) {
+ return false;
+ }
+ return true;
+ }
+
+}
Property changes on: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNode.java
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Rev
\ No newline at end of property
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 15:03:35 UTC (rev 11920)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodes.java 2021-10-23 15:31:49 UTC (rev 11921)
@@ -28,7 +28,6 @@
package org.foray.common.data;
-import org.foray.common.primitive.CharacterUtils;
import org.foray.common.sequence.CharArrayBuilder;
import org.foray.common.sequence.IntArrayBuilder;
@@ -112,135 +111,6 @@
*/
public class Node {
- /** Format string for {@link #toString()}. */
- private static final String TO_STRING_FORMAT =
- "index: %5d, low: %5d, equal: %5d, high: %5d, key char: %4x %s, parent: %5d, key: %6s";
-
- /** The index for this node. */
- private int index;
-
- /** The low for this node. */
- private int low;
-
- /** The equal for this node. */
- private int equal;
-
- /** The high for this node. */
- private int high;
-
- /** The keyChar for this node. */
- private char keyChar;
-
- /** 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 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);
- }
- }
-
- /**
- * Returns the index.
- * @return The index.
- */
- public int getIndex() {
- return this.index;
- }
-
- /**
- * Returns the low.
- * @return The low.
- */
- public int getLow() {
- return this.low;
- }
-
- /**
- * Returns the equal.
- * @return The equal.
- */
- public int getEqual() {
- return this.equal;
- }
-
- /**
- * Returns the high.
- * @return The high.
- */
- public int getHigh() {
- return this.high;
- }
-
- /**
- * Returns the keyChar.
- * @return The keyChar.
- */
- public char getKeyChar() {
- return this.keyChar;
- }
-
- /**
- * Returns the index to the parent node, if known.
- * @return The high.
- */
- public int getParent() {
- 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;
- if (printableChar < ' '
- || printableChar > CharacterUtils.MAX_PRINTABLE_ASCII_CHAR) {
- printableChar = ' ';
- }
- return String.format(TO_STRING_FORMAT,
- this.index, this.low, this.equal, this.high, (int) this.keyChar, printableChar, this.parent,
- this.key);
- }
-
- @Override
- public boolean equals(final Object other) {
- if (other == this) {
- return true;
- }
- if (! (other instanceof Node)) {
- return false;
- }
- final Node otherNode = (Node) other;
- if (this.index != otherNode.index
- || this.low != otherNode.low
- || this.equal != otherNode.equal
- || this.high != otherNode.high
- || this.keyChar != otherNode.keyChar) {
- return false;
- }
- return true;
- }
}
/**
@@ -247,7 +117,7 @@
* 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> {
+ public class DepthFirstIterator implements Iterator<TernaryNode> {
/** The stack of indexes. Index 1 should be at the bottom of the stack until finished. The current index is at
* the top. */
@@ -284,8 +154,9 @@
}
@Override
- public Node next() {
- final Node returnValue = new Node(this.nextIndex, this.charStack.toString(), null);
+ public TernaryNode next() {
+ final TernaryNode returnValue = new TernaryNode(TernaryNodes.this, this.nextIndex,
+ this.charStack.toString(), null);
/* Tee up the one after this, if any. */
this.nextIndex = -1;
@@ -641,8 +512,8 @@
* @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 CharSequence key, final WithParents withParents) {
- return new Node(index, key, withParents);
+ TernaryNode createNotionalNode(final int index, final CharSequence key, final WithParents withParents) {
+ return new TernaryNode(this, index, key, withParents);
}
/**
@@ -773,7 +644,7 @@
this.logger.error("Inconsistent Tree", e);
}
for (int index = 0; index < size(); index ++) {
- final Node node = createNotionalNode(index, null, withParents);
+ final TernaryNode node = createNotionalNode(index, null, withParents);
this.logger.info(node.toString());
}
this.logger.info("-----------------------------------------------------------------------------------------");
@@ -821,7 +692,7 @@
* Returns a depth-first iterator over all nodes in the tree.
* @return A new iterator.
*/
- public Iterator<TernaryNodes.Node> nodeIterator() {
+ public Iterator<TernaryNode> nodeIterator() {
return new DepthFirstIterator();
}
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 15:03:35 UTC (rev 11920)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeTests.java 2021-10-23 15:31:49 UTC (rev 11921)
@@ -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, null);
+ final TernaryNode 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, null);
+ final TernaryNode node = nodes.createNotionalNode(index, null, null);
Assert.assertEquals(index, node.getIndex());
Assert.assertEquals(expectedLow, node.getLow());
Assert.assertEquals(expectedEqual, node.getEqual());
@@ -394,8 +394,8 @@
Assert.assertEquals(10, map.getNodes().findCharNode(8, 'r'));
/* Test the iterator. */
- final Iterator<TernaryNodes.Node> nodeIterator = map.getNodes().nodeIterator();
- final List<TernaryNodes.Node> actual = new ArrayList<TernaryNodes.Node>();
+ final Iterator<TernaryNode> nodeIterator = map.getNodes().nodeIterator();
+ final List<TernaryNode> actual = new ArrayList<TernaryNode>();
while (nodeIterator.hasNext()) {
actual.add(nodeIterator.next());
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|