[Mulgara-svn] r749 - projects/xa2/object-pool/scratch

[andrae at mulgara.org]

Author: andrae
Date: 2008-04-09 02:12:59 -0700 (Wed, 09 Apr 2008)
New Revision: 749

Added:
   projects/xa2/object-pool/scratch/TrieTest.java
Log:
More experimenting with Tries.



Added: projects/xa2/object-pool/scratch/TrieTest.java
===================================================================
--- projects/xa2/object-pool/scratch/TrieTest.java	                        (rev 0)
+++ projects/xa2/object-pool/scratch/TrieTest.java	2008-04-09 09:12:59 UTC (rev 749)
@@ -0,0 +1,173 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 9th April 2008
+ */
+
+/**
+ * Simple test class to help crystalise my thinking on tries.
+ */
+
+public class TrieTest {
+  public static class TrieNode {
+    int type;
+    TrieLeaf least;
+
+    public TrieNode() {
+      type = this.getClass().identityHashCode();
+    }
+  }
+
+  public static class TrieBranch extends TrieNode {
+    public static final int TYPE = TrieBranch.class.identityHashCode();
+
+    int offset;
+    Map<char, TrieNode> children;
+
+    public TrieBranch(String str, long id) {
+      super();
+      this.offset = str.length;
+      this.children = new HashMap<char, TrieNode>();
+      this.least = new TrieLeaf(str, id);
+      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) {
+      super();
+      assert lhs != null && lhs.length > 0;
+      assert rhs != null && rhs.length > 0;
+
+      children = new HashMap<char, TrieNode>();
+
+      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);
+
+          least = lhs[i] < rhs[i] ? lhsNode.least : rhsNode.least;
+
+          return; // Escape here.
+        }
+        i++;
+      }
+
+      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 (i < lhs.length) {
+        children.put(lhs[i], lhsNode);
+        children.put(null, rhsNode);
+        least = rhsNode.least;
+      } else {
+        children.put(null, lhsNode);
+        children.put(rhs[i], rhsNode);
+        least = lhsNode.least;
+      }
+    }
+
+    public insert(String str, long id) {
+      return insert(new TrieLeaf(str, id));
+    }
+
+    private insert(TrieLeaf node) {
+      if (!least.value.regionMatches(0, node.least.value, 0, offset - 1)) {
+        return REPLACE;
+      } else {
+        // new node matches the lcp of this node.
+        TrieNode child;
+        if (node.least.value.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]);
+        }
+
+        if (child == null) {
+          // this is the first node to be inserted on this branching value.
+          children.put(node.least.value[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:
+              // 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));
+          }
+        }
+      }
+    }
+
+    public long lookup(String str) throws NotFound {
+      if (!least.value.regionMatches(0, node.least.value, 0, offset - 1)) {
+        throw new NotFound();
+      } else {
+        // new node matches the lcp of this node.
+        TrieNode child;
+        if (node.least.value.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 TrieBranch.TYPE: throw new IllegalStateException("Trie entry terminated in a branch");
+              default: throw new IllegalStateException("Unknown trie node type");
+            }
+          } else {
+            throw NotFound();
+          }
+        } else {
+          // new node is expected to terminate in one of this nodes children.
+          child = children.get(node.least.value[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");
+            }
+          } else {
+            throw NotFound();
+          }
+        }
+      }
+    }
+  }
+
+
+  public static class TrieLeaf {
+    static final int TYPE = TrieBranch.class.identityHashCode();
+
+    final String value;
+    final long id;
+
+    TrieLeaf(String value, long id) {
+      super();
+      this.value = value;
+      this.id = id;
+      this.least = this;
+    }
+
+    public insert(TrieNode node, long id) {
+      switch (node.type) {
+        case TrieLeaf.TYPE:
+          assert value.equals(node.least.value);
+          return DUPLICATE;
+        case TrieBranch.TYPE:
+          return REPLACE;
+        default:
+          throw new IllegalStateException("Attempt to insert unknown node-type into leaf");
+      }
+    }
+  }
+}