[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