1 package com.hughes.android.dictionary;
\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
9 import com.hughes.util.LRUCacheMap;
\r
12 public final class Index {
\r
14 final String filename;
\r
15 final RandomAccessFile file;
\r
18 final Map<Integer,Node> indexOffsetToNode = new LRUCacheMap<Integer,Node>(5000);
\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
27 public Node lookup(final String text) throws IOException {
\r
28 return lookup(text, 0, root);
\r
31 private Node lookup(final String text, final int pos, final Node node) throws IOException {
\r
32 if (pos == text.length()) {
\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 = node.children.get(text.substring(pos, i));
\r
39 if (child != null) {
\r
40 return lookup(text, i, getNode(text.substring(0, i), child));
\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 : node.children.entrySet()) {
\r
47 if (childEntry.getKey().startsWith(remainder)) {
\r
48 return getNode(node.text + childEntry.getKey(), childEntry.getValue());
\r
55 private Node getNode(final String text, final int indexOffset) throws IOException {
\r
56 Node node = indexOffsetToNode.get(indexOffset);
\r
58 node = new Node(text, indexOffset);
\r
59 indexOffsetToNode.put(indexOffset, node);
\r
66 final int indexOffset;
\r
67 final TreeMap<String,Integer> children;
\r
68 final int[] offsets;
\r
70 Node(final String text, final int indexOffset) throws IOException {
\r
72 this.indexOffset = indexOffset;
\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
82 children.put(chunk, file.readInt());
\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
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
97 entryOffsets.add(offsets[i]);
\r
99 if (entryOffsets.size() >= maxSize) {
\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