[Mulgara-svn] r787 - projects/xa2/object-pool/src

[andrae at mulgara.org]

Author: andrae
Date: 2008-04-14 23:02:06 -0700 (Mon, 14 Apr 2008)
New Revision: 787

Modified:
   projects/xa2/object-pool/src/CompMemTrie.java
Log:
Untested but compiles.  Migrated to use ByteMap.



Modified: projects/xa2/object-pool/src/CompMemTrie.java
===================================================================
--- projects/xa2/object-pool/src/CompMemTrie.java	2008-04-15 05:57:17 UTC (rev 786)
+++ projects/xa2/object-pool/src/CompMemTrie.java	2008-04-15 06:02:06 UTC (rev 787)
@@ -1,28 +1,25 @@
 /*
  * Copyright Topaz Foundation 2008
  * Author Andrae Muys
- * Date 9th April 2008
+ * Date 15th April 2008
  */
 
 import java.util.Arrays;
-import java.util.HashMap;
-import java.util.Map;
 
 /**
- * Implements a basic in-memory trie - uses HashMaps to implement trie nodes.
+ * Implements an in-memory trie - uses ByteMaps to implement trie nodes.
  */
-public class MemoryTrie {
+public class CompMemTrie {
   @SuppressWarnings("serial")
   public static class NotFound extends Exception {};
 
   private TrieBranch root;
 
-  public MemoryTrie() {
+  public CompMemTrie() {
     this.root = null;
   }
 
   public void insert(byte[] key, long value) {
-//    System.err.println("MemoryTrie # Inserting: " + Arrays.hashCode(key) + " :: " + value);
     if (root == null) {
       root = new TrieBranch(key, value);
     } else {
@@ -35,7 +32,6 @@
   }
 
   public long lookup(byte[] key) throws NotFound {
-//    System.err.println("MemoryTrie # Lookup: " + Arrays.hashCode(key));
     if (root == null) {
       throw new NotFound();
     }
@@ -70,12 +66,12 @@
 
   private static class TrieBranch extends TrieNode {
     private int offset;
-    private Map<Byte, TrieNode> children;
+    private ByteMap<TrieNode> children;
     private TrieLeaf term;
     
     public TrieBranch(byte[] key, long value) {
       super();
-      this.children = new HashMap<Byte, TrieNode>();
+      this.children = new ByteMap<TrieNode>();
       this.term = new TrieLeaf(key, value);
       this.offset = term.key.length;
       this.least = this.term;
@@ -91,7 +87,7 @@
       assert newNode != null;
 
       offset = 0;
-      children = new HashMap<Byte, TrieNode>();
+      children = new ByteMap<TrieNode>();
       term = null;
       least = null;
 
@@ -102,8 +98,8 @@
       while (i < lhs.length && i < rhs.length) {
         if (lhs[i] != rhs[i]) {
           offset = i;
-          children.put(lhs[i], oldNode);
-          children.put(rhs[i], newNode);
+          children.insert(lhs[i], oldNode);
+          children.insert(rhs[i], newNode);
 
           least = lhs[i] < rhs[i] ? oldNode.least : newNode;
 
@@ -114,13 +110,13 @@
 
       if (i < lhs.length) {
         offset = i;
-        children.put(lhs[i], oldNode);
+        children.insert(lhs[i], oldNode);
         term = newNode;
         least = newNode;
       } else if (i < rhs.length) {
         if (oldNode instanceof TrieLeaf) {
           offset = i;
-          children.put(rhs[i], newNode);
+          children.insert(rhs[i], newNode);
           term = (TrieLeaf)oldNode;
           least = (TrieLeaf)oldNode;
         } else {
@@ -154,10 +150,10 @@
           }
         } else {
           // new node is expected to terminate in one of this nodes children.
-          TrieNode child = children.get(node.key[offset]);
+          TrieNode child = children.lookup(node.key[offset]);
           if (child == null) {
             // this is the first node to be inserted on this branching key.
-            children.put(node.key[offset], node);
+            children.insert(node.key[offset], node);
           } else {
             try {
               // there is an existing child node branching on this branching key.
@@ -166,7 +162,7 @@
                 // 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.key[offset], new TrieBranch(child, node));
+                children.insert(node.key[offset], new TrieBranch(child, node));
             }
           }
         }
@@ -188,7 +184,7 @@
           }
         } else {
           // new node is expected to terminate in one of this nodes children.
-          child = children.get(key[offset]);
+          child = children.lookup(key[offset]);
           if (child != null) {
             return child.lookup(key, offset);
           } else {
@@ -199,7 +195,7 @@
     }
     
     public String toString() {
-      return "Trie-BRANCH[" + (term != null) + " on " + offset + " with " + children.size() + " and least[" + least + "]";
+      return "Trie-BRANCH[" + (term != null) + " on " + offset + " and least[" + least + "]";
     }
   }