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

   1 /**
   2  *
   3  */
   4 package com.hughes.android.dictionary.engine;
   5
   6 import java.io.IOException;
   7 import java.io.PrintStream;
   8 import java.io.RandomAccessFile;
   9 import java.util.ArrayList;
  10 import java.util.Collection;
  11 import java.util.List;
  12 import java.util.concurrent.atomic.AtomicBoolean;
  13
  14 import com.hughes.util.CachingList;
  15 import com.hughes.util.raf.RAFList;
  16 import com.hughes.util.raf.RAFSerializable;
  17 import com.hughes.util.raf.RAFSerializer;
  18 import com.hughes.util.raf.UniformRAFList;
  19 import com.ibm.icu.text.Collator;
  20 import com.ibm.icu.text.Transliterator;
  21
  22 public final class Index implements RAFSerializable<Index> {
  23
  24   static final int CACHE_SIZE = 5000;
  25
  26   final Dictionary dict;
  27
  28   public final String shortName;
  29   public final String longName;
  30
  31   // persisted: tells how the entries are sorted.
  32   public final Language sortLanguage;
  33   final String normalizerRules;
  34
  35   // Built from the two above.
  36   private Transliterator normalizer;
  37
  38   // persisted
  39   public final List<IndexEntry> sortedIndexEntries;
  40
  41   // One big list!
  42   // Various sub-types.
  43   // persisted
  44   public final List<RowBase> rows;
  45
  46   public final boolean swapPairEntries;
  47
  48   // --------------------------------------------------------------------------
  49
  50   public Index(final Dictionary dict, final String shortName, final String longName, final Language sortLanguage, final String normalizerRules, final boolean swapPairEntries) {
  51     this.dict = dict;
  52     this.shortName = shortName;
  53     this.longName = longName;
  54     this.sortLanguage = sortLanguage;
  55     this.normalizerRules = normalizerRules;
  56     this.swapPairEntries = swapPairEntries;
  57     sortedIndexEntries = new ArrayList<IndexEntry>();
  58     rows = new ArrayList<RowBase>();
  59
  60     normalizer = null;
  61   }
  62
  63   public synchronized Transliterator normalizer() {
  64     if (normalizer == null) {
  65       normalizer = Transliterator.createFromRules("", normalizerRules, Transliterator.FORWARD);
  66     }
  67     return normalizer;
  68   }
  69
  70   public Index(final Dictionary dict, final RandomAccessFile raf) throws IOException {
  71     this.dict = dict;
  72     shortName = raf.readUTF();
  73     longName = raf.readUTF();
  74     final String languageCode = raf.readUTF();
  75     sortLanguage = Language.lookup(languageCode);
  76     normalizerRules = raf.readUTF();
  77     swapPairEntries = raf.readBoolean();
  78     if (sortLanguage == null) {
  79       throw new IOException("Unsupported language: " + languageCode);
  80     }
  81     sortedIndexEntries = CachingList.create(RAFList.create(raf, IndexEntry.SERIALIZER, raf.getFilePointer()), CACHE_SIZE);
  82     rows = CachingList.create(UniformRAFList.create(raf, new RowBase.Serializer(this), raf.getFilePointer()), CACHE_SIZE);
  83   }
  84
  85   @Override
  86   public void write(final RandomAccessFile raf) throws IOException {
  87     raf.writeUTF(shortName);
  88     raf.writeUTF(longName);
  89     raf.writeUTF(sortLanguage.getSymbol());
  90     raf.writeUTF(normalizerRules);
  91     raf.writeBoolean(swapPairEntries);
  92     RAFList.write(raf, sortedIndexEntries, IndexEntry.SERIALIZER);
  93     UniformRAFList.write(raf, (Collection<RowBase>) rows, new RowBase.Serializer(this), 5);
  94   }
  95
  96   public void print(final PrintStream out) {
  97     for (final RowBase row : rows) {
  98       row.print(out);
  99     }
 100   }
 101
 102   public static final class IndexEntry implements RAFSerializable<Index.IndexEntry> {
 103     public final String token;
 104     private final String normalizedToken;
 105     public final int startRow;
 106     public final int numRows;
 107
 108
 109     static final RAFSerializer<IndexEntry> SERIALIZER = new RAFSerializer<IndexEntry> () {
 110       @Override
 111       public IndexEntry read(RandomAccessFile raf) throws IOException {
 112         return new IndexEntry(raf);
 113       }
 114       @Override
 115       public void write(RandomAccessFile raf, IndexEntry t) throws IOException {
 116         t.write(raf);
 117       }};
 118
 119     public IndexEntry(final String token, final String normalizedToken, final int startRow, final int numRows) {
 120       assert token.equals(token.trim());
 121       assert token.length() > 0;
 122       this.token = token;
 123       this.normalizedToken = normalizedToken;
 124       this.startRow = startRow;
 125       this.numRows = numRows;
 126     }
 127
 128     public IndexEntry(final RandomAccessFile raf) throws IOException {
 129       token = raf.readUTF();
 130       startRow = raf.readInt();
 131       numRows = raf.readInt();
 132       final boolean hasNormalizedForm = raf.readBoolean();
 133       normalizedToken = hasNormalizedForm ? raf.readUTF() : token;
 134     }
 135
 136     public void write(RandomAccessFile raf) throws IOException {
 137       raf.writeUTF(token);
 138       raf.writeInt(startRow);
 139       raf.writeInt(numRows);
 140       final boolean hasNormalizedForm = !token.equals(normalizedToken);
 141       raf.writeBoolean(hasNormalizedForm);
 142       if (hasNormalizedForm) {
 143         raf.writeUTF(normalizedToken);
 144       }
 145     }
 146
 147     public String toString() {
 148       return String.format("%s@%d(%d)", token, startRow, numRows);
 149     }
 150
 151     public String normalizedToken() {
 152       return normalizedToken;
 153     }
 154   }
 155
 156   public IndexEntry findInsertionPoint(String token, final AtomicBoolean interrupted) {
 157     final Transliterator normalizer = normalizer();
 158     if (TransliteratorManager.init(null)) {
 159       token = normalizer.transliterate(token);
 160     } else {
 161       // Do our best since the Transliterators aren't up yet.
 162       token = token.toLowerCase();
 163     }
 164
 165     int start = 0;
 166     int end = sortedIndexEntries.size();
 167
 168     final Collator sortCollator = sortLanguage.getCollator();
 169     while (start < end) {
 170       final int mid = (start + end) / 2;
 171       if (interrupted.get()) {
 172         return null;
 173       }
 174       final IndexEntry midEntry = sortedIndexEntries.get(mid);
 175
 176       final int comp = sortCollator.compare(token, midEntry.normalizedToken());
 177       if (comp == 0) {
 178         final int result = windBackCase(token, mid, interrupted);
 179         return sortedIndexEntries.get(result);
 180       } else if (comp < 0) {
 181         //System.out.println("Upper bound: " + midEntry + ", norm=" + midEntry.normalizedToken() + ", mid=" + mid);
 182         end = mid;
 183       } else {
 184         //System.out.println("Lower bound: " + midEntry + ", norm=" + midEntry.normalizedToken() + ", mid=" + mid);
 185         start = mid + 1;
 186       }
 187     }
 188
 189     // If we search for a substring of a string that's in there, return that.
 190     int result = Math.min(start, sortedIndexEntries.size() - 1);
 191     result = windBackCase(sortedIndexEntries.get(result).normalizedToken(), result, interrupted);
 192     return sortedIndexEntries.get(result);
 193   }
 194
 195   public static final class SearchResult {
 196     public final IndexEntry insertionPoint;
 197     public final IndexEntry longestPrefix;
 198     public final String longestPrefixString;
 199     public final boolean success;
 200
 201     public SearchResult(IndexEntry insertionPoint, IndexEntry longestPrefix,
 202         String longestPrefixString, boolean success) {
 203       this.insertionPoint = insertionPoint;
 204       this.longestPrefix = longestPrefix;
 205       this.longestPrefixString = longestPrefixString;
 206       this.success = success;
 207     }
 208
 209     @Override
 210     public String toString() {
 211       return String.format("inerstionPoint=%s,longestPrefix=%s,longestPrefixString=%s,success=%b", insertionPoint.toString(), longestPrefix.toString(), longestPrefixString, success);
 212     }
 213   }
 214
 215 //  public SearchResult findLongestSubstring(String token, final AtomicBoolean interrupted) {
 216 //    token = normalizer.transliterate(token);
 217 //    if (token.length() == 0) {
 218 //      return new SearchResult(sortedIndexEntries.get(0), sortedIndexEntries.get(0), "", true);
 219 //    }
 220 //    IndexEntry insertionPoint = null;
 221 //    IndexEntry result = null;
 222 //    boolean unmodified = true;
 223 //    while (!interrupted.get() && token.length() > 0) {
 224 //      result = findInsertionPoint(token, interrupted);
 225 //      if (result == null) {
 226 //        return null;
 227 //      }
 228 //      if (unmodified) {
 229 //        insertionPoint = result;
 230 //      }
 231 //      if (result.normalizedToken(normalizer).startsWith(token)) {
 232 //        return new SearchResult(insertionPoint, result, token, unmodified);
 233 //      }
 234 //      unmodified = false;
 235 //      token = token.substring(0, token.length() - 1);
 236 //    }
 237 //    return new SearchResult(insertionPoint, sortedIndexEntries.get(0), "", false);
 238 //  }
 239
 240   private final int windBackCase(final String token, int result, final AtomicBoolean interrupted) {
 241     while (result > 0 && sortedIndexEntries.get(result - 1).normalizedToken().equals(token)) {
 242       --result;
 243       if (interrupted.get()) {
 244         return result;
 245       }
 246     }
 247     return result;
 248   }
 249
 250   /*
 251   public int tokenRowBinarySearch(final int rowIndex) {
 252     int start = 0;
 253     int end = sortedIndexEntries.size();
 254     while (start < end) {
 255       final int mid = (start + end) / 2;
 256       final int midRowIndex = sortedIndexEntries.get(mid).startRow;
 257       if (midRowIndex == rowIndex) {
 258         return mid;
 259       }
 260       if ()
 261     }
 262   }
 263   */
 264
 265 }