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.Set;\r
   7 import java.util.TreeMap;\r
   8 \r
   9 import com.hughes.util.LRUCacheMap;\r
  10 \r
  11 \r
  12 public final class Index {\r
  13   \r
  14   final String filename;\r
  15   final RandomAccessFile file;\r
  16   \r
  17   final Node root;\r
  18   final Map<Integer,Node> indexOffsetToNode = new LRUCacheMap<Integer,Node>(5000);\r
  19   \r
  20   \r
  21   public Index(final String filename) throws IOException {\r
  22     this.filename = filename;\r
  23     file = new RandomAccessFile(filename, "r");\r
  24     root = getNode("", 0);\r
  25   }\r
  26   \r
  27   public Node lookup(final String text) throws IOException {\r
  28     return lookup(text, 0, root);\r
  29   }\r
  30   \r
  31   private Node lookup(final String text, final int pos, final Node n) throws IOException {\r
  32     if (pos == text.length()) {\r
  33       return n;\r
  34     }\r
  35     \r
  36     // Check whether any prefix of text is a child.\r
  37     for (int i = pos + 1; i <= text.length(); ++i) {\r
  38       final Integer child = n.children.get(text.substring(pos, i));\r
  39       if (child != null) {\r
  40         return lookup(text, i, getNode(text.substring(0, i), child));\r
  41       }\r
  42     }\r
  43     \r
  44     // Check whether any child starts with what's left of text.\r
  45     final String remainder = text.substring(pos);\r
  46     for (final Map.Entry<String, Integer> childEntry : n.children.entrySet()) {\r
  47       if (childEntry.getKey().startsWith(remainder)) {\r
  48         return getNode(n.text + childEntry.getKey(), childEntry.getValue());\r
  49       }\r
  50     }\r
  51     \r
  52     return n;\r
  53   }\r
  54   \r
  55   private Node getNode(final String text, final int indexOffset) throws IOException {\r
  56     Node node = indexOffsetToNode.get(indexOffset);\r
  57     if (node == null) {\r
  58       node = new Node(text, indexOffset);\r
  59       indexOffsetToNode.put(indexOffset, node);\r
  60     }\r
  61     return node;\r
  62   }\r
  63 \r
  64   final class Node {\r
  65     final String text;\r
  66     final int indexOffset;\r
  67     final TreeMap<String,Integer> children;\r
  68     final int[] offsets;\r
  69     \r
  70     Node(final String text, final int indexOffset) throws IOException {\r
  71       this.text = text;\r
  72       this.indexOffset = indexOffset;\r
  73       \r
  74       file.seek(indexOffset);\r
  75       final int numChildren = file.readInt();\r
  76       children = new TreeMap<String, Integer>();\r
  77       for (int i = 0; i < numChildren; ++i) {\r
  78         final String chunk = file.readUTF().intern();\r
  79         if (chunk.length() == 0) {\r
  80           throw new IOException("Empty string chunk.");\r
  81         }\r
  82         children.put(chunk, file.readInt());\r
  83       }\r
  84       \r
  85       final int numOffsets = file.readInt();\r
  86       offsets = new int[numOffsets];\r
  87       for (int i = 0; i < offsets.length; ++i) {\r
  88         offsets[i] = file.readInt();\r
  89       }\r
  90     }\r
  91 \r
  92     public void getDescendantEntryOffsets(final Set<Integer> entryOffsets, int maxSize) throws IOException {\r
  93       for (int i = 0; i < offsets.length; ++i) {\r
  94         if (entryOffsets.size() >= maxSize) {\r
  95           return;\r
  96         }\r
  97         entryOffsets.add(offsets[i]);\r
  98       }\r
  99       if (entryOffsets.size() >= maxSize) {\r
 100         return;\r
 101       }\r
 102       for (final Map.Entry<String, Integer> childEntry : children.entrySet()) {\r
 103         final Node child = getNode(text + childEntry.getKey(), childEntry.getValue());\r
 104         child.getDescendantEntryOffsets(entryOffsets, maxSize);\r
 105         if (entryOffsets.size() >= maxSize) {\r
 106           return;\r
 107         }\r
 108       }\r
 109     }\r
 110   }\r
 111 \r
 112 }\r