src/com/hughes/android/dictionary/Index.java

   1 package com.hughes.android.dictionary;\r
   2 \r
   3 import java.io.IOException;\r
   4 import java.io.RandomAccessFile;\r
   5 import java.util.Map;\r
   6 import java.util.TreeMap;\r
   7 \r
   8 import com.hughes.util.LRUCacheMap;\r
   9 \r
  10 \r
  11 public final class Index {\r
  12   \r
  13   final String filename;\r
  14   final RandomAccessFile file;\r
  15   \r
  16   final Node root;\r
  17   final Map<Integer,Node> locationToNode = new LRUCacheMap<Integer,Node>(5000);\r
  18   \r
  19   \r
  20   public Index(final String filename) throws IOException {\r
  21     this.filename = filename;\r
  22     file = new RandomAccessFile(filename, "r");\r
  23     root = getNode("", 0);\r
  24   }\r
  25   \r
  26   public Node lookup(final String text) throws IOException {\r
  27     return lookup(text, 0, root);\r
  28   }\r
  29   \r
  30   private Node lookup(final String text, final int pos, final Node n) throws IOException {\r
  31     if (pos == text.length()) {\r
  32       return n;\r
  33     }\r
  34     for (int i = pos + 1; i <= text.length(); ++i) {\r
  35       final Integer child = n.children.get(text.substring(pos, i));\r
  36       if (child != null) {\r
  37         return lookup(text, i, getNode(text.substring(0, i), child));\r
  38       }\r
  39     }\r
  40     return n;\r
  41   }\r
  42   \r
  43   private Node getNode(final String text, final int location) throws IOException {\r
  44     Node node = locationToNode.get(location);\r
  45     if (node == null) {\r
  46       node = new Node(text, location);\r
  47       locationToNode.put(location, node);\r
  48     }\r
  49     return node;\r
  50   }\r
  51 \r
  52   final class Node {\r
  53     final String text;\r
  54     final int location;\r
  55     final TreeMap<String,Integer> children;\r
  56     final int[] offsets;\r
  57     \r
  58     Node(final String text, final int location) throws IOException {\r
  59       this.text = text;\r
  60       this.location = location;\r
  61       \r
  62       file.seek(location);\r
  63       final int numChildren = file.readInt();\r
  64       children = new TreeMap<String, Integer>();\r
  65       for (int i = 0; i < numChildren; ++i) {\r
  66         final String chunk = file.readUTF().intern();\r
  67         if (chunk.length() == 0) {\r
  68           throw new IOException("Empty string chunk.");\r
  69         }\r
  70         children.put(chunk, file.readInt());\r
  71       }\r
  72       \r
  73       final int numOffsets = file.readInt();\r
  74       offsets = new int[numOffsets];\r
  75       for (int i = 0; i < offsets.length; ++i) {\r
  76         offsets[i] = file.readInt();\r
  77       }\r
  78     }\r
  79   }\r
  80 \r
  81 }\r