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

   1 // Copyright 2011 Google Inc. All Rights Reserved.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 /**
  16  *
  17  */
  18 package com.hughes.android.dictionary.engine;
  19
  20 import java.io.IOException;
  21 import java.io.PrintStream;
  22 import java.io.RandomAccessFile;
  23 import java.util.ArrayList;
  24 import java.util.Collection;
  25 import java.util.EnumMap;
  26 import java.util.LinkedHashSet;
  27 import java.util.List;
  28 import java.util.Map;
  29 import java.util.Set;
  30 import java.util.concurrent.atomic.AtomicBoolean;
  31
  32 import com.hughes.android.dictionary.DictionaryInfo;
  33 import com.hughes.android.dictionary.DictionaryInfo.IndexInfo;
  34 import com.hughes.util.CachingList;
  35 import com.hughes.util.raf.RAFList;
  36 import com.hughes.util.raf.RAFSerializable;
  37 import com.hughes.util.raf.RAFSerializer;
  38 import com.hughes.util.raf.UniformRAFList;
  39 import com.ibm.icu.text.Collator;
  40 import com.ibm.icu.text.Transliterator;
  41
  42 public final class Index implements RAFSerializable<Index> {
  43
  44   static final int CACHE_SIZE = 5000;
  45
  46   final Dictionary dict;
  47
  48   public final String shortName;  // Typically the ISO code for the language.
  49   public final String longName;
  50
  51   // persisted: tells how the entries are sorted.
  52   public final Language sortLanguage;
  53   final String normalizerRules;
  54
  55   // Built from the two above.
  56   private Transliterator normalizer;
  57
  58   // persisted
  59   public final List<IndexEntry> sortedIndexEntries;
  60
  61   // One big list!
  62   // Various sub-types.
  63   // persisted
  64   public final List<RowBase> rows;
  65   public final boolean swapPairEntries;
  66
  67   // Version 2:
  68   int mainTokenCount = -1;
  69
  70   // --------------------------------------------------------------------------
  71
  72   public Index(final Dictionary dict, final String shortName, final String longName, final Language sortLanguage, final String normalizerRules, final boolean swapPairEntries) {
  73     this.dict = dict;
  74     this.shortName = shortName;
  75     this.longName = longName;
  76     this.sortLanguage = sortLanguage;
  77     this.normalizerRules = normalizerRules;
  78     this.swapPairEntries = swapPairEntries;
  79     sortedIndexEntries = new ArrayList<IndexEntry>();
  80     rows = new ArrayList<RowBase>();
  81
  82     normalizer = null;
  83   }
  84
  85   public synchronized Transliterator normalizer() {
  86     if (normalizer == null) {
  87       normalizer = Transliterator.createFromRules("", normalizerRules, Transliterator.FORWARD);
  88     }
  89     return normalizer;
  90   }
  91
  92   public Index(final Dictionary dict, final RandomAccessFile raf) throws IOException {
  93     this.dict = dict;
  94     shortName = raf.readUTF();
  95     longName = raf.readUTF();
  96     final String languageCode = raf.readUTF();
  97     sortLanguage = Language.lookup(languageCode);
  98     normalizerRules = raf.readUTF();
  99     swapPairEntries = raf.readBoolean();
 100     if (sortLanguage == null) {
 101       throw new IOException("Unsupported language: " + languageCode);
 102     }
 103     if (dict.dictFileVersion >= 2) {
 104       mainTokenCount = raf.readInt();
 105     }
 106     sortedIndexEntries = CachingList.create(RAFList.create(raf, IndexEntry.SERIALIZER, raf.getFilePointer()), CACHE_SIZE);
 107     rows = CachingList.create(UniformRAFList.create(raf, new RowBase.Serializer(this), raf.getFilePointer()), CACHE_SIZE);
 108   }
 109
 110   @Override
 111   public void write(final RandomAccessFile raf) throws IOException {
 112     raf.writeUTF(shortName);
 113     raf.writeUTF(longName);
 114     raf.writeUTF(sortLanguage.getIsoCode());
 115     raf.writeUTF(normalizerRules);
 116     raf.writeBoolean(swapPairEntries);
 117     if (dict.dictFileVersion >= 2) {
 118       raf.writeInt(mainTokenCount);
 119     }
 120     RAFList.write(raf, sortedIndexEntries, IndexEntry.SERIALIZER);
 121     UniformRAFList.write(raf, (Collection<RowBase>) rows, new RowBase.Serializer(this), 5);
 122   }
 123
 124   public void print(final PrintStream out) {
 125     for (final RowBase row : rows) {
 126       row.print(out);
 127     }
 128   }
 129
 130   public static final class IndexEntry implements RAFSerializable<Index.IndexEntry> {
 131     public final String token;
 132     private final String normalizedToken;
 133     public final int startRow;
 134     public final int numRows;
 135
 136
 137     static final RAFSerializer<IndexEntry> SERIALIZER = new RAFSerializer<IndexEntry> () {
 138       @Override
 139       public IndexEntry read(RandomAccessFile raf) throws IOException {
 140         return new IndexEntry(raf);
 141       }
 142       @Override
 143       public void write(RandomAccessFile raf, IndexEntry t) throws IOException {
 144         t.write(raf);
 145       }};
 146
 147     public IndexEntry(final String token, final String normalizedToken, final int startRow, final int numRows) {
 148       assert token.equals(token.trim());
 149       assert token.length() > 0;
 150       this.token = token;
 151       this.normalizedToken = normalizedToken;
 152       this.startRow = startRow;
 153       this.numRows = numRows;
 154     }
 155
 156     public IndexEntry(final RandomAccessFile raf) throws IOException {
 157       token = raf.readUTF();
 158       startRow = raf.readInt();
 159       numRows = raf.readInt();
 160       final boolean hasNormalizedForm = raf.readBoolean();
 161       normalizedToken = hasNormalizedForm ? raf.readUTF() : token;
 162     }
 163
 164     public void write(RandomAccessFile raf) throws IOException {
 165       raf.writeUTF(token);
 166       raf.writeInt(startRow);
 167       raf.writeInt(numRows);
 168       final boolean hasNormalizedForm = !token.equals(normalizedToken);
 169       raf.writeBoolean(hasNormalizedForm);
 170       if (hasNormalizedForm) {
 171         raf.writeUTF(normalizedToken);
 172       }
 173     }
 174
 175     public String toString() {
 176       return String.format("%s@%d(%d)", token, startRow, numRows);
 177     }
 178
 179     public String normalizedToken() {
 180       return normalizedToken;
 181     }
 182   }
 183
 184   public IndexEntry findInsertionPoint(String token, final AtomicBoolean interrupted) {
 185     final int index = findInsertionPointIndex(token, interrupted);
 186     return index != -1 ? sortedIndexEntries.get(index) : null;
 187   }
 188
 189   public int findInsertionPointIndex(String token, final AtomicBoolean interrupted) {
 190     token = normalizeToken(token);
 191
 192     int start = 0;
 193     int end = sortedIndexEntries.size();
 194
 195     final Collator sortCollator = sortLanguage.getCollator();
 196     while (start < end) {
 197       final int mid = (start + end) / 2;
 198       if (interrupted.get()) {
 199         return -1;
 200       }
 201       final IndexEntry midEntry = sortedIndexEntries.get(mid);
 202
 203       final int comp = sortCollator.compare(token, midEntry.normalizedToken());
 204       if (comp == 0) {
 205         final int result = windBackCase(token, mid, interrupted);
 206         return result;
 207       } else if (comp < 0) {
 208         //System.out.println("Upper bound: " + midEntry + ", norm=" + midEntry.normalizedToken() + ", mid=" + mid);
 209         end = mid;
 210       } else {
 211         //System.out.println("Lower bound: " + midEntry + ", norm=" + midEntry.normalizedToken() + ", mid=" + mid);
 212         start = mid + 1;
 213       }
 214     }
 215
 216     // If we search for a substring of a string that's in there, return that.
 217     int result = Math.min(start, sortedIndexEntries.size() - 1);
 218     result = windBackCase(sortedIndexEntries.get(result).normalizedToken(), result, interrupted);
 219     return result;
 220   }
 221
 222   private final int windBackCase(final String token, int result, final AtomicBoolean interrupted) {
 223     while (result > 0 && sortedIndexEntries.get(result - 1).normalizedToken().equals(token)) {
 224       --result;
 225       if (interrupted.get()) {
 226         return result;
 227       }
 228     }
 229     return result;
 230   }
 231
 232   public IndexInfo getIndexInfo() {
 233     return new DictionaryInfo.IndexInfo(shortName, sortedIndexEntries.size(), mainTokenCount);
 234   }
 235
 236   final List<RowBase> multiWordSearch(final List<String> searchTokens, final AtomicBoolean interrupted) {
 237     final List<RowBase> result = new ArrayList<RowBase>();
 238
 239     // Heuristic: use the longest searchToken as the base.
 240     String searchToken = null;
 241     for (int i = 0; i < searchTokens.size(); ++i) {
 242       if (interrupted.get()) { return null; }
 243       final String normalized = normalizeToken(searchTokens.get(i));
 244       // Normalize them all.
 245       searchTokens.set(i, normalized);
 246       if (searchToken == null || normalized.length() > searchToken.length()) {
 247         searchToken = normalized;
 248       }
 249     }
 250
 251     final int insertionPointIndex = findInsertionPointIndex(searchToken, interrupted);
 252     if (insertionPointIndex == -1 || interrupted.get()) {
 253       return null;
 254     }
 255
 256     // The things that match.
 257     // TODO: use a key
 258     final Map<RowMatchType,Set<RowBase>> matches = new EnumMap<RowMatchType, Set<RowBase>>(RowMatchType.class);
 259     for (final RowMatchType rowMatchType : RowMatchType.values()) {
 260       matches.put(rowMatchType, new LinkedHashSet<RowBase>());
 261     }
 262
 263     for (int index = insertionPointIndex; index < sortedIndexEntries.size(); ++index) {
 264       if (interrupted.get()) { return null; }
 265       final IndexEntry indexEntry = sortedIndexEntries.get(index);
 266       if (!indexEntry.normalizedToken.equals(searchToken)) {
 267         break;
 268       }
 269
 270       for (int rowIndex = indexEntry.startRow; rowIndex < indexEntry.startRow + indexEntry.numRows; ++rowIndex) {
 271         if (interrupted.get()) { return null; }
 272         final RowBase row = rows.get(rowIndex);
 273         final RowMatchType matchType = row.matches(searchTokens, normalizer, swapPairEntries);
 274         if (matchType != RowMatchType.NO_MATCH) {
 275           matches.get(matchType).add(row);
 276         }
 277       }
 278     }
 279
 280     for (final Set<RowBase> rows : matches.values()) {
 281       result.addAll(rows);
 282     }
 283
 284     return result;
 285   }
 286
 287   private String normalizeToken(final String searchToken) {
 288     if (TransliteratorManager.init(null)) {
 289       final Transliterator normalizer = normalizer();
 290       return normalizer.transliterate(searchToken);
 291     } else {
 292       // Do our best since the Transliterators aren't up yet.
 293       return searchToken.toLowerCase();
 294     }
 295   }
 296
 297 }