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

[andrae at mulgara.org]

Author: andrae
Date: 2008-04-10 20:10:23 -0700 (Thu, 10 Apr 2008)
New Revision: 770

Added:
   projects/xa2/object-pool/src/MemoryTrieTest.java
Modified:
   projects/xa2/object-pool/src/MemoryTrie.java
Log:
Split Test from Datastructure.



Modified: projects/xa2/object-pool/src/MemoryTrie.java
===================================================================
--- projects/xa2/object-pool/src/MemoryTrie.java	2008-04-11 02:58:30 UTC (rev 769)
+++ projects/xa2/object-pool/src/MemoryTrie.java	2008-04-11 03:10:23 UTC (rev 770)
@@ -7,48 +7,43 @@
 import java.util.Arrays;
 import java.util.HashMap;
 import java.util.Map;
-import java.io.BufferedReader;
-import java.io.File;
-import java.io.FileReader;
 
 /**
- * Simple test class to help crystalise my thinking on tries.
+ * Implements a basic in-memory trie - uses HashMaps to implement trie nodes.
  */
-public class TrieTest {
+public class MemoryTrie {
   @SuppressWarnings("serial")
   public static class NotFound extends Exception {};
 
-  public static class Trie {
-    TrieBranch root;
+  private TrieBranch root;
 
-    public Trie() {
-      this.root = null;
-    }
+  public MemoryTrie() {
+    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 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 new NotFound();
-      }
-
-      return root.lookup(key);
+  public long lookup(String key) throws NotFound {
+    if (root == null) {
+      throw new NotFound();
     }
+
+    return root.lookup(key);
   }
 
-  public abstract static class TrieNode {
+  private abstract static class TrieNode {
     @SuppressWarnings("serial")
-	public static class InsertAbove extends Exception {} ;
+    protected static class InsertAbove extends Exception {} ;
     protected static final InsertAbove cont = new InsertAbove();
 
     protected TrieLeaf least;
@@ -56,7 +51,7 @@
     protected abstract void insert(TrieLeaf node, int parentLcd) throws InsertAbove;
     protected abstract long lookup(byte[] key, int parentLcd) throws NotFound;
 
-    public static boolean regionMatches(byte[] lhs, int lhsOff, byte[] rhs, int rhsOff, int len) {
+    protected static boolean regionMatches(byte[] lhs, int lhsOff, byte[] rhs, int rhsOff, int len) {
       if (lhsOff < 0 || rhsOff < 0) {
         return false;
       }
@@ -71,10 +66,10 @@
     }
   }
 
-  public static class TrieBranch extends TrieNode {
-    int offset;
-    Map<Byte, TrieNode> children;
-    TrieLeaf term;
+  private static class TrieBranch extends TrieNode {
+    private int offset;
+    private Map<Byte, TrieNode> children;
+    private TrieLeaf term;
 
     public TrieBranch(String str, long value) {
       super();
@@ -88,7 +83,7 @@
       this(oldRoot, new TrieLeaf(key, value));
     }
 
-    protected TrieBranch(TrieNode oldNode, TrieLeaf newNode) {
+    private TrieBranch(TrieNode oldNode, TrieLeaf newNode) {
       super();
       assert oldNode != null;
       assert newNode != null;
@@ -202,11 +197,11 @@
     }
   }
 
-  public static class TrieLeaf extends TrieNode {
+  private static class TrieLeaf extends TrieNode {
     final byte[] key;
     final long value;
 
-    TrieLeaf(String key, long value) {
+    public TrieLeaf(String key, long value) {
       super();
       this.key = key.getBytes();
       this.value = value;
@@ -230,38 +225,4 @@
       return value;
     }
   }
-
-
-  public static void main(String[] args) throws Exception {
-    testWithFile(new File("./propernames.uniq"));
-    testWithFile(new File("./connectives.uniq"));
-    testWithFile(new File("./web2a.uniq"));
-    testWithFile(new File("./web2.uniq"));
-  }
-
-  public static void testWithFile(File file) throws Exception {
-    Map<String, Long> namesMap = new HashMap<String, Long>();
-    Trie namesTrie = new Trie();
-
-    System.out.println("Inserting lines from " + file);
-    BufferedReader names = new BufferedReader(new FileReader(file));
-    long n = 0;
-    String name = names.readLine();
-    while (name != null) {
-      namesMap.put(name, n);
-      namesTrie.insert(name, n);
-      name = names.readLine();
-      n++;
-    }
-    names.close();
-
-    System.out.println("Checking lines from " + file);
-    for (String key : namesMap.keySet()) {
-      if (namesTrie.lookup(key) != namesMap.get(key)) {
-        throw new IllegalStateException("Trie doesn't match Map");
-      }
-    }
-    
-    System.out.println("Test Succeeded with " + file);
-  }
 }

Copied: projects/xa2/object-pool/src/MemoryTrieTest.java (from rev 769, projects/xa2/object-pool/src/MemoryTrie.java)
===================================================================
--- projects/xa2/object-pool/src/MemoryTrieTest.java	                        (rev 0)
+++ projects/xa2/object-pool/src/MemoryTrieTest.java	2008-04-11 03:10:23 UTC (rev 770)
@@ -0,0 +1,49 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 9th April 2008
+ */
+
+import java.util.HashMap;
+import java.util.Map;
+import java.io.BufferedReader;
+import java.io.File;
+import java.io.FileReader;
+
+/**
+ * Basic tests of the MemoryTrie.
+ */
+public class MemoryTrieTest {
+  public static void main(String[] args) throws Exception {
+    testWithFile(new File("../scratch/propernames.uniq"));
+    testWithFile(new File("../scratch/connectives.uniq"));
+    testWithFile(new File("../scratch/web2a.uniq"));
+    testWithFile(new File("../scratch/web2.uniq"));
+  }
+
+  public static void testWithFile(File file) throws Exception {
+    Map<String, Long> namesMap = new HashMap<String, Long>();
+    MemoryTrie namesTrie = new MemoryTrie();
+
+    System.out.println("Inserting lines from " + file);
+    BufferedReader names = new BufferedReader(new FileReader(file));
+    long n = 0;
+    String name = names.readLine();
+    while (name != null) {
+      namesMap.put(name, n);
+      namesTrie.insert(name, n);
+      name = names.readLine();
+      n++;
+    }
+    names.close();
+
+    System.out.println("Checking lines from " + file);
+    for (String key : namesMap.keySet()) {
+      if (namesTrie.lookup(key) != namesMap.get(key)) {
+        throw new IllegalStateException("Trie doesn't match Map");
+      }
+    }
+    
+    System.out.println("Test Succeeded with " + file);
+  }
+}