[Mulgara-svn] r750 - projects/xa2/object-pool/scratch
andrae at mulgara.org
andrae at mulgara.org
Wed Apr 9 10:05:34 UTC 2008
Author: andrae
Date: 2008-04-09 03:05:33 -0700 (Wed, 09 Apr 2008)
New Revision: 750
Modified:
projects/xa2/object-pool/scratch/TrieTest.java
Log:
Further work on clarifying the Trie structure.
Modified: projects/xa2/object-pool/scratch/TrieTest.java
===================================================================
--- projects/xa2/object-pool/scratch/TrieTest.java 2008-04-09 09:12:59 UTC (rev 749)
+++ projects/xa2/object-pool/scratch/TrieTest.java 2008-04-09 10:05:33 UTC (rev 750)
@@ -9,13 +9,49 @@
*/
public class TrieTest {
- public static class TrieNode {
+ public static class NotFound extends Exception {};
+
+ public static class Trie {
+ TrieBranch root;
+
+ public Trie() {
+ this.root = null;
+ }
+
+ public void insert(String key, long value) {
+ if (root == null) {
+ root = new TrieBranch(key, value);
+ } else {
+ try {
+ root.insert(key, value);
+ } catch (TrieNode.InsertAbove k) {
+ root = new TrieBranch(root, key, value);
+ }
+ }
+ }
+
+ public long lookup(String key) throws NotFound {
+ if (root == null) {
+ throw NotFound();
+ }
+
+ return root.lookup(key);
+ }
+ }
+
+ public abstract static class TrieNode {
+ public static class InsertAbove extends Exception {} ;
+ protected static final InsertAbove cont = new InsertAbove();
+
int type;
TrieLeaf least;
public TrieNode() {
type = this.getClass().identityHashCode();
}
+
+ protected abstract void insert(TrieNode node, int parentLcd);
+ protected abstract long lookup(String str, int parentLcd) throws NotFound;
}
public static class TrieBranch extends TrieNode {
@@ -24,33 +60,35 @@
int offset;
Map<char, TrieNode> children;
- public TrieBranch(String str, long id) {
+ public TrieBranch(String str, long value) {
super();
this.offset = str.length;
this.children = new HashMap<char, TrieNode>();
- this.least = new TrieLeaf(str, id);
+ this.least = new TrieLeaf(str, value);
this.children.put(null, this.least);
}
- public TrieBranch(String lhs, long lhsId, String rhs, long rhsId) {
- this(lhs, new TrieLeaf(lhs, lhsId), rhs, new TrieLeaf(rhs, rhsId));
- }
-
- public TrieBranch(String lhs, TrieNode lhsNode, String rhs, TrieNode rhsNode) {
+ public TrieBranch(TrieBranch oldRoot, String key, long value) {
super();
- assert lhs != null && lhs.length > 0;
- assert rhs != null && rhs.length > 0;
+ assert oldRoot != null;
+ assert key != null;
+ assert value != null;
+ TrieLeaf newNode = new TrieLeaf(key, value);
+
children = new HashMap<char, TrieNode>();
+ String lhs = oldRoot.least.key;
+ String rhs = newNode.key;
+
int i = 0;
while (i < lhs.length && i < rhs.length) {
if (lhs[i] != rhs[i]) {
offset = i;
- children.put(lhs[i], lhsNode);
- children.put(rhs[i], rhsNode);
+ children.put(lhs[i], oldRoot);
+ children.put(rhs[i], newNode);
- least = lhs[i] < rhs[i] ? lhsNode.least : rhsNode.least;
+ least = lhs[i] < rhs[i] ? oldRoot.least : newNode;
return; // Escape here.
}
@@ -59,85 +97,82 @@
assert lhs.length != rhs.length; // Strings can't be equal.
- // If we reach this point one of the strings is a prefix of the other.
+ // If we reach this point the leaf had better be a prefix of the old-root or something has gone wrong.
if (i < lhs.length) {
- children.put(lhs[i], lhsNode);
- children.put(null, rhsNode);
- least = rhsNode.least;
+ children.put(lhs[i], oldRoot);
+ children.put(null, newNode);
+ least = newNode
} else {
- children.put(null, lhsNode);
- children.put(rhs[i], rhsNode);
- least = lhsNode.least;
+ throw new IllegalStateException("Attempt to create new root node with leaf > root.
}
}
- public insert(String str, long id) {
- return insert(new TrieLeaf(str, id));
+ public insert(String str, long value) {
+ return insert(new TrieLeaf(str, value), 0);
}
- private insert(TrieLeaf node) {
- if (!least.value.regionMatches(0, node.least.value, 0, offset - 1)) {
- return REPLACE;
+ public long lookup(String str) throws NotFound {
+ return lookup(str, 0);
+ }
+
+ protected insert(TrieLeaf node, int parentLcp) throws InsertAbove {
+ if (!least.key.regionMatches(parentLcp, node.least.key, parentLcp, offset - 1)) {
+ throw cont;
} else {
// new node matches the lcp of this node.
TrieNode child;
- if (node.least.value.length == offset) {
+ if (node.least.key.length == offset) {
// new node is expected to terminate here.
child = children.get(null);
} else {
// new node is expected to terminate in one of this nodes children.
- child = children.get(node.least.value[offset]);
+ child = children.get(node.least.key[offset]);
}
if (child == null) {
- // this is the first node to be inserted on this branching value.
- children.put(node.least.value[offset], node);
+ // this is the first node to be inserted on this branching key.
+ children.put(node.least.key[offset], node);
return SUCCESS;
} else {
- // there is an existing child node branching on this branching value.
- switch (child.insert(node, id)) {
- case SUCCESS: return SUCCESS;
- case DUPLICATE: return DUPLICATE;
- case REPLACE:
+ try {
+ // there is an existing child node branching on this branching key.
+ child.insert(node, offset);
+ } catch (EscapeContinuation k) {
// as every child node shares a common lcp, any child will suffice when preparing the new
// lcp/offset of the new node. The least node is only required as the new parent's least node
// will be the smallest of the inserted node and this node's least node.
- children.put(node.least.value[offset],
- new TrieBranch(child, child.least.value, node, node.least.value));
+ children.put(node.least.key[offset],
+ new TrieBranch(child, child.least.key, node, node.least.key));
}
}
}
}
- public long lookup(String str) throws NotFound {
- if (!least.value.regionMatches(0, node.least.value, 0, offset - 1)) {
+ protected long lookup(String str, int parentLcd) throws NotFound {
+ if (!least.key.regionMatches(parentLcd, str, parentLcd, offset - 1)) {
throw new NotFound();
} else {
// new node matches the lcp of this node.
TrieNode child;
- if (node.least.value.length == offset) {
+ if (str.length == offset) {
// new node is expected to terminate here.
child = children.get(null);
if (child != null) {
switch (child.type) {
- case TrieLeaf.TYPE: return ((TrieLeaf)child).id;
+ case TrieLeaf.TYPE: return ((TrieLeaf)child).value;
case TrieBranch.TYPE: throw new IllegalStateException("Trie entry terminated in a branch");
default: throw new IllegalStateException("Unknown trie node type");
}
} else {
- throw NotFound();
+ throw new NotFound();
}
} else {
// new node is expected to terminate in one of this nodes children.
- child = children.get(node.least.value[offset]);
+ child = children.get(str[offset]);
if (child != null) {
- switch (child.type) {
- case TrieLeaf.TYPE: return ((TrieLeaf)child).id;
- case TrieBranch.TYPE: return ((TrieBranch)child).lookup(str);
- default: throw new IllegalStateException("Unknown trie node type");
- }
+ child.lookup(str, offset);
} else {
- throw NotFound();
+ throw new NotFound();
}
}
}
@@ -148,26 +183,31 @@
public static class TrieLeaf {
static final int TYPE = TrieBranch.class.identityHashCode();
- final String value;
- final long id;
+ final String key;
+ final long value;
- TrieLeaf(String value, long id) {
+ TrieLeaf(String key, long value) {
super();
+ this.key = key;
this.value = value;
- this.id = id;
this.least = this;
}
- public insert(TrieNode node, long id) {
+ protected void insert(TrieNode node, int parentLcd) throws InsertAbove {
switch (node.type) {
case TrieLeaf.TYPE:
- assert value.equals(node.least.value);
- return DUPLICATE;
+ assert key.equals(node.least.key);
+ return;
case TrieBranch.TYPE:
- return REPLACE;
+ throw cont;
default:
throw new IllegalStateException("Attempt to insert unknown node-type into leaf");
}
}
+
+ protected long lookup(String str, int parentLcd) {
+ assert key.equals(str);
+ return value;
+ }
}
}
More information about the Mulgara-svn
mailing list