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
  21 public final class Index implements RAFSerializable<Index> {
  22
  23   static final int CACHE_SIZE = 5000;
  24
  25   final Dictionary dict;
  26
  27   public final String shortName;
  28   public final String longName;
  29
  30   // persisted: tells how the entries are sorted.
  31   public final Language sortLanguage;
  32
  33   // persisted
  34   public final List<IndexEntry> sortedIndexEntries;
  35
  36   // One big list!
  37   // Various sub-types.
  38   // persisted
  39   public final List<RowBase> rows;
  40
  41   public final boolean swapPairEntries;
  42
  43   // --------------------------------------------------------------------------
  44
  45   public Index(final Dictionary dict, final String shortName, final String longName, final Language sortLanguage, final boolean swapPairEntries) {
  46     this.dict = dict;
  47     this.shortName = shortName;
  48     this.longName = longName;
  49     this.sortLanguage = sortLanguage;
  50     this.swapPairEntries = swapPairEntries;
  51     sortedIndexEntries = new ArrayList<IndexEntry>();
  52     rows = new ArrayList<RowBase>();
  53   }
  54
  55   public Index(final Dictionary dict, final RandomAccessFile raf) throws IOException {
  56     this.dict = dict;
  57     shortName = raf.readUTF();
  58     longName = raf.readUTF();
  59     final String languageCode = raf.readUTF();
  60     sortLanguage = Language.lookup(languageCode);
  61     swapPairEntries = raf.readBoolean();
  62     if (sortLanguage == null) {
  63       throw new IOException("Unsupported language: " + languageCode);
  64     }
  65     sortedIndexEntries = CachingList.create(RAFList.create(raf, IndexEntry.SERIALIZER, raf.getFilePointer()), CACHE_SIZE);
  66     rows = CachingList.create(UniformRAFList.create(raf, new RowBase.Serializer(this), raf.getFilePointer()), CACHE_SIZE);
  67   }
  68
  69   @Override
  70   public void write(final RandomAccessFile raf) throws IOException {
  71     raf.writeUTF(shortName);
  72     raf.writeUTF(longName);
  73     raf.writeUTF(sortLanguage.getSymbol());
  74     raf.writeBoolean(swapPairEntries);
  75     RAFList.write(raf, sortedIndexEntries, IndexEntry.SERIALIZER);
  76     UniformRAFList.write(raf, (Collection<RowBase>) rows, new RowBase.Serializer(this), 5);
  77   }
  78
  79   public void print(final PrintStream out) {
  80     for (final RowBase row : rows) {
  81       row.print(out);
  82     }
  83   }
  84
  85   public static final class IndexEntry implements RAFSerializable<Index.IndexEntry> {
  86     public final String token;
  87     public final int startRow;
  88     public final int numRows;
  89
  90     static final RAFSerializer<IndexEntry> SERIALIZER = new RAFSerializer<IndexEntry> () {
  91       @Override
  92       public IndexEntry read(RandomAccessFile raf) throws IOException {
  93         return new IndexEntry(raf);
  94       }
  95       @Override
  96       public void write(RandomAccessFile raf, IndexEntry t) throws IOException {
  97         t.write(raf);
  98       }};
  99
 100     public IndexEntry(final String token, final int startRow, final int numRows) {
 101       assert token.equals(token.trim());
 102       assert token.length() > 0;
 103       this.token = token;
 104       this.startRow = startRow;
 105       this.numRows = numRows;
 106     }
 107
 108     public IndexEntry(final RandomAccessFile raf) throws IOException {
 109       token = raf.readUTF();
 110       startRow = raf.readInt();
 111       numRows = raf.readInt();
 112     }
 113
 114     public void write(RandomAccessFile raf) throws IOException {
 115       raf.writeUTF(token);
 116       raf.writeInt(startRow);
 117       raf.writeInt(numRows);
 118     }
 119
 120     public String toString() {
 121       return String.format("%s@%d(%d)", token, startRow, numRows);
 122     }
 123   }
 124
 125   public IndexEntry findInsertionPoint(String token, final AtomicBoolean interrupted) {
 126     token = sortLanguage.textNorm(token, true);
 127
 128     int start = 0;
 129     int end = sortedIndexEntries.size();
 130
 131     final Collator sortCollator = sortLanguage.getSortCollator();
 132     while (start < end) {
 133       final int mid = (start + end) / 2;
 134       if (interrupted.get()) {
 135         return null;
 136       }
 137       final IndexEntry midEntry = sortedIndexEntries.get(mid);
 138
 139       final int comp = sortCollator.compare(token, sortLanguage.textNorm(midEntry.token, true));
 140       if (comp == 0) {
 141         final int result = windBackCase(token, mid, sortCollator, interrupted);
 142         return sortedIndexEntries.get(result);
 143       } else if (comp < 0) {
 144 //        Log.d("THAD", "Upper bound: " + midEntry);
 145         end = mid;
 146       } else {
 147 //        Log.d("THAD", "Lower bound: " + midEntry);
 148         start = mid + 1;
 149       }
 150     }
 151
 152     // If we search for a substring of a string that's in there, return that.
 153     int result = Math.min(start, sortedIndexEntries.size() - 1);
 154     result = windBackCase(sortLanguage.textNorm(sortedIndexEntries.get(result).token, true), result, sortCollator, interrupted);
 155     return sortedIndexEntries.get(result);
 156   }
 157
 158   public static final class SearchResult {
 159     public final IndexEntry insertionPoint;
 160     public final IndexEntry longestPrefix;
 161     public final String longestPrefixString;
 162     public final boolean success;
 163
 164     public SearchResult(IndexEntry insertionPoint, IndexEntry longestPrefix,
 165         String longestPrefixString, boolean success) {
 166       this.insertionPoint = insertionPoint;
 167       this.longestPrefix = longestPrefix;
 168       this.longestPrefixString = longestPrefixString;
 169       this.success = success;
 170     }
 171
 172     @Override
 173     public String toString() {
 174       return String.format("inerstionPoint=%s,longestPrefix=%s,longestPrefixString=%s,success=%b", insertionPoint.toString(), longestPrefix.toString(), longestPrefixString, success);
 175     }
 176   }
 177
 178   public SearchResult findLongestSubstring(String token, final AtomicBoolean interrupted) {
 179     if (token.length() == 0) {
 180       return new SearchResult(sortedIndexEntries.get(0), sortedIndexEntries.get(0), "", true);
 181     }
 182     IndexEntry insertionPoint = null;
 183     IndexEntry result = null;
 184     boolean unmodified = true;
 185     while (!interrupted.get() && token.length() > 0) {
 186       result = findInsertionPoint(token, interrupted);
 187       if (result == null) {
 188         return null;
 189       }
 190       if (unmodified) {
 191         insertionPoint = result;
 192       }
 193       if (sortLanguage.textNorm(result.token, true).startsWith(sortLanguage.textNorm(token, true))) {
 194         return new SearchResult(insertionPoint, result, token, unmodified);
 195       }
 196       unmodified = false;
 197       token = token.substring(0, token.length() - 1);
 198     }
 199     return new SearchResult(insertionPoint, sortedIndexEntries.get(0), "", false);
 200   }
 201
 202   private final int windBackCase(final String token, int result, final Collator sortCollator, final AtomicBoolean interrupted) {
 203     while (result > 0 && sortCollator.compare(sortLanguage.textNorm(sortedIndexEntries.get(result - 1).token, true), token) >= 0) {
 204       --result;
 205       if (interrupted.get()) {
 206         return result;
 207       }
 208     }
 209     return result;
 210   }
 211
 212
 213 }