Increase target size of preferred letters while typing.

This increases the chance of hitting the correct letter when typing a word
that exists in the dictionary, rather than only correct it after the fact.
It is most effective after 2 or 3 letters of a word have been typed and gets
more accurate with more typed letters in the word.

If 2 adjacent letters have similar probabilities of occuring, then there is no
hit correction applied.

9 files changed, 179 insertions, 15 deletions

diff --git a/src/com/android/inputmethod/latin/BinaryDictionary.java b/src/com/android/inputmethod/latin/BinaryDictionary.java
index 68d8b740c..ec467c88d 100644
--- a/src/com/android/inputmethod/latin/BinaryDictionary.java
+++ b/src/com/android/inputmethod/latin/BinaryDictionary.java
@@ -65,7 +65,8 @@ public class BinaryDictionary extends Dictionary {
     private native boolean isValidWordNative(int nativeData, char[] word, int wordLength);
     private native int getSuggestionsNative(int dict, int[] inputCodes, int codesSize, 
             char[] outputChars, int[] frequencies,
-            int maxWordLength, int maxWords, int maxAlternatives, int skipPos);
+            int maxWordLength, int maxWords, int maxAlternatives, int skipPos,
+            int[] nextLettersFrequencies, int nextLettersSize);
 
     private final void loadDictionary(Context context, int resId) {
         AssetManager am = context.getResources().getAssets();
@@ -74,7 +75,8 @@ public class BinaryDictionary extends Dictionary {
     }
 
     @Override
-    public void getWords(final WordComposer codes, final WordCallback callback) {
+    public void getWords(final WordComposer codes, final WordCallback callback,
+            int[] nextLettersFrequencies) {
         final int codesSize = codes.size();
         // Wont deal with really long words.
         if (codesSize > MAX_WORD_LENGTH - 1) return;
@@ -90,7 +92,9 @@ public class BinaryDictionary extends Dictionary {
 
         int count = getSuggestionsNative(mNativeDict, mInputCodes, codesSize,
                 mOutputChars, mFrequencies,
-                MAX_WORD_LENGTH, MAX_WORDS, MAX_ALTERNATIVES, -1);
+                MAX_WORD_LENGTH, MAX_WORDS, MAX_ALTERNATIVES, -1,
+                nextLettersFrequencies,
+                nextLettersFrequencies != null ? nextLettersFrequencies.length : 0);
 
         // If there aren't sufficient suggestions, search for words by allowing wild cards at
         // the different character positions. This feature is not ready for prime-time as we need
@@ -100,7 +104,8 @@ public class BinaryDictionary extends Dictionary {
             for (int skip = 0; skip < codesSize; skip++) {
                 int tempCount = getSuggestionsNative(mNativeDict, mInputCodes, codesSize,
                         mOutputChars, mFrequencies,
-                        MAX_WORD_LENGTH, MAX_WORDS, MAX_ALTERNATIVES, skip);
+                        MAX_WORD_LENGTH, MAX_WORDS, MAX_ALTERNATIVES, skip,
+                        null, 0);
                 count = Math.max(count, tempCount);
                 if (tempCount > 0) break;
             }
diff --git a/src/com/android/inputmethod/latin/ContactsDictionary.java b/src/com/android/inputmethod/latin/ContactsDictionary.java
index fd7ba55fc..f53ebf3f5 100644
--- a/src/com/android/inputmethod/latin/ContactsDictionary.java
+++ b/src/com/android/inputmethod/latin/ContactsDictionary.java
@@ -84,14 +84,15 @@ public class ContactsDictionary extends ExpandableDictionary {
     }
 
     @Override
-    public synchronized void getWords(final WordComposer codes, final WordCallback callback) {
+    public synchronized void getWords(final WordComposer codes, final WordCallback callback,
+            int[] nextLettersFrequencies) {
         synchronized (mUpdatingLock) {
             // If we need to update, start off a background task
             if (mRequiresReload) loadDictionaryAsyncLocked();
             // Currently updating contacts, don't return any results.
             if (mUpdatingContacts) return;
         }
-        super.getWords(codes, callback);
+        super.getWords(codes, callback, nextLettersFrequencies);
     }
 
     @Override
diff --git a/src/com/android/inputmethod/latin/Dictionary.java b/src/com/android/inputmethod/latin/Dictionary.java
index 6c1c856e7..b656d04dc 100644
--- a/src/com/android/inputmethod/latin/Dictionary.java
+++ b/src/com/android/inputmethod/latin/Dictionary.java
@@ -55,9 +55,14 @@ abstract public class Dictionary {
      * words are added through the callback object.
      * @param composer the key sequence to match
      * @param callback the callback object to send matched words to as possible candidates
+     * @param nextLettersFrequencies array of frequencies of next letters that could follow the
+     *        word so far. For instance, "bracke" can be followed by "t", so array['t'] will have
+     *        a non-zero value on returning from this method. 
+     *        Pass in null if you don't want the dictionary to look up next letters.
      * @see WordCallback#addWord(char[], int, int)
      */
-    abstract public void getWords(final WordComposer composer, final WordCallback callback);
+    abstract public void getWords(final WordComposer composer, final WordCallback callback,
+            int[] nextLettersFrequencies);
 
     /**
      * Checks if the given word occurs in the dictionary
diff --git a/src/com/android/inputmethod/latin/ExpandableDictionary.java b/src/com/android/inputmethod/latin/ExpandableDictionary.java
index 1589168ee..648f577ca 100644
--- a/src/com/android/inputmethod/latin/ExpandableDictionary.java
+++ b/src/com/android/inputmethod/latin/ExpandableDictionary.java
@@ -27,6 +27,7 @@ public class ExpandableDictionary extends Dictionary {
     private char[] mWordBuilder = new char[MAX_WORD_LENGTH];
     private int mMaxDepth;
     private int mInputLength;
+    private int[] mNextLettersFrequencies;
 
     public static final int MAX_WORD_LENGTH = 32;
     private static final char QUOTE = '\'';
@@ -116,8 +117,10 @@ public class ExpandableDictionary extends Dictionary {
     }
 
     @Override
-    public void getWords(final WordComposer codes, final WordCallback callback) {
+    public void getWords(final WordComposer codes, final WordCallback callback,
+            int[] nextLettersFrequencies) {
         mInputLength = codes.size();
+        mNextLettersFrequencies = nextLettersFrequencies;
         if (mCodes.length < mInputLength) mCodes = new int[mInputLength][];
         // Cache the codes so that we don't have to lookup an array list
         for (int i = 0; i < mInputLength; i++) {
@@ -216,6 +219,11 @@ public class ExpandableDictionary extends Dictionary {
                     if (!callback.addWord(word, 0, depth + 1, freq * snr)) {
                         return;
                     }
+                    // Add to frequency of next letters for predictive correction
+                    if (mNextLettersFrequencies != null && depth >= inputIndex && skipPos < 0
+                            && mNextLettersFrequencies.length > word[inputIndex]) {
+                        mNextLettersFrequencies[word[inputIndex]]++;
+                    }
                 }
                 if (children != null) {
                     getWordsRec(children, codes, word, depth + 1, completion, snr, inputIndex,
diff --git a/src/com/android/inputmethod/latin/LatinIME.java b/src/com/android/inputmethod/latin/LatinIME.java
index 56971a534..470b0048e 100644
--- a/src/com/android/inputmethod/latin/LatinIME.java
+++ b/src/com/android/inputmethod/latin/LatinIME.java
@@ -1340,6 +1340,8 @@ public class LatinIME extends InputMethodService
     private void updateSuggestions() {
         mSuggestionShouldReplaceCurrentWord = false;
 
+        ((LatinKeyboard) mInputView.getKeyboard()).setPreferredLetters(null);
+
         // Check if we have a suggestion engine attached.
         if ((mSuggest == null || !isPredictionOn()) && !mVoiceInputHighlighted) {
             return;
@@ -1351,6 +1353,10 @@ public class LatinIME extends InputMethodService
         }
 
         List<CharSequence> stringList = mSuggest.getSuggestions(mInputView, mWord, false);
+        int[] nextLettersFrequencies = mSuggest.getNextLettersFrequencies();
+
+        ((LatinKeyboard) mInputView.getKeyboard()).setPreferredLetters(nextLettersFrequencies);
+
         boolean correctionAvailable = mSuggest.hasMinimalCorrection();
         //|| mCorrectionMode == mSuggest.CORRECTION_FULL;
         CharSequence typedWord = mWord.getTypedWord();
diff --git a/src/com/android/inputmethod/latin/LatinKeyboard.java b/src/com/android/inputmethod/latin/LatinKeyboard.java
index 64b4529f3..9b742a5f9 100644
--- a/src/com/android/inputmethod/latin/LatinKeyboard.java
+++ b/src/com/android/inputmethod/latin/LatinKeyboard.java
@@ -35,11 +35,15 @@ import android.graphics.drawable.BitmapDrawable;
 import android.graphics.drawable.Drawable;
 import android.inputmethodservice.Keyboard;
 import android.text.TextPaint;
+import android.util.Log;
 import android.view.ViewConfiguration;
 import android.view.inputmethod.EditorInfo;
 
 public class LatinKeyboard extends Keyboard {
 
+    private static final boolean DEBUG_PREFERRED_LETTER = false;
+    private static final String TAG = "LatinKeyboard";
+
     private Drawable mShiftLockIcon;
     private Drawable mShiftLockPreviewIcon;
     private Drawable mOldShiftIcon;
@@ -69,6 +73,12 @@ public class LatinKeyboard extends Keyboard {
     private boolean mCurrentlyInSpace;
     private SlidingLocaleDrawable mSlidingLocaleIcon;
     private Rect mBounds = new Rect();
+    private int[] mPrefLetterFrequencies;
+    private boolean mPreemptiveCorrection;
+    private int mPrefLetter;
+    private int mPrefLetterX;
+    private int mPrefLetterY;
+    private int mPrefDistance;
 
     private int mExtensionResId; 
     
@@ -79,6 +89,8 @@ public class LatinKeyboard extends Keyboard {
     private int mShiftState = SHIFT_OFF;
 
     private static final float SPACEBAR_DRAG_THRESHOLD = 0.8f;
+    private static final float OVERLAP_PERCENTAGE_LOW_PROB = 0.70f;
+    private static final float OVERLAP_PERCENTAGE_HIGH_PROB = 0.85f;
 
     static int sSpacebarVerticalCorrection;
 
@@ -409,9 +421,18 @@ public class LatinKeyboard extends Keyboard {
         return mCurrentlyInSpace;
     }
 
+    void setPreferredLetters(int[] frequencies) {
+        mPrefLetterFrequencies = frequencies;
+        mPrefLetter = 0;
+    }
+
     void keyReleased() {
         mCurrentlyInSpace = false;
         mSpaceDragLastDiff = 0;
+        mPrefLetter = 0;
+        mPrefLetterX = 0;
+        mPrefLetterY = 0;
+        mPrefDistance = Integer.MAX_VALUE;
         if (mSpaceKey != null) {
             updateLocaleDrag(Integer.MAX_VALUE);
         }
@@ -448,6 +469,79 @@ public class LatinKeyboard extends Keyboard {
                     return insideSpace;
                 }
             }
+        } else if (mPrefLetterFrequencies != null) {
+            // New coordinate? Reset
+            if (mPrefLetterX != x || mPrefLetterY != y) {
+                mPrefLetter = 0;
+                mPrefDistance = Integer.MAX_VALUE;
+            }
+            // Handle preferred next letter
+            final int[] pref = mPrefLetterFrequencies;
+            if (mPrefLetter > 0) {
+                if (DEBUG_PREFERRED_LETTER && mPrefLetter == code
+                        && !key.isInsideSuper(x, y)) {
+                    Log.d(TAG, "CORRECTED !!!!!!");
+                }
+                return mPrefLetter == code;
+            } else {
+                final boolean inside = key.isInsideSuper(x, y);
+                int[] nearby = getNearestKeys(x, y);
+                List<Key> nearbyKeys = getKeys();
+                if (inside) {
+                    // If it's a preferred letter
+                    if (inPrefList(code, pref)) {
+                        // Check if its frequency is much lower than a nearby key
+                        mPrefLetter = code;
+                        mPrefLetterX = x;
+                        mPrefLetterY = y;
+                        for (int i = 0; i < nearby.length; i++) {
+                            Key k = nearbyKeys.get(nearby[i]);
+                            if (k != key && inPrefList(k.codes[0], pref)) {
+                                final int dist = distanceFrom(k, x, y);
+                                if (dist < (int) (k.width * OVERLAP_PERCENTAGE_LOW_PROB) &&
+                                        (pref[k.codes[0]] > pref[mPrefLetter] * 3))  {
+                                    mPrefLetter = k.codes[0];
+                                    mPrefDistance = dist;
+                                    if (DEBUG_PREFERRED_LETTER) {
+                                        Log.d(TAG, "CORRECTED ALTHOUGH PREFERRED !!!!!!");
+                                    }
+                                    break;
+                                }
+                            }
+                        }
+
+                        return mPrefLetter == code;
+                    }
+                }
+
+                // Get the surrounding keys and intersect with the preferred list
+                // For all in the intersection
+                //   if distance from touch point is within a reasonable distance
+                //       make this the pref letter
+                // If no pref letter
+                //   return inside;
+                // else return thiskey == prefletter;
+
+                for (int i = 0; i < nearby.length; i++) {
+                    Key k = nearbyKeys.get(nearby[i]);
+                    if (inPrefList(k.codes[0], pref)) {
+                        final int dist = distanceFrom(k, x, y);
+                        if (dist < (int) (k.width * OVERLAP_PERCENTAGE_HIGH_PROB)
+                                && dist < mPrefDistance)  {
+                            mPrefLetter = k.codes[0];
+                            mPrefLetterX = x;
+                            mPrefLetterY = y;
+                            mPrefDistance = dist;
+                        }
+                    }
+                }
+                // Didn't find any
+                if (mPrefLetter == 0) {
+                    return inside;
+                } else {
+                    return mPrefLetter == code;
+                }
+            }
         }
 
         // Lock into the spacebar
@@ -456,6 +550,19 @@ public class LatinKeyboard extends Keyboard {
         return key.isInsideSuper(x, y);
     }
 
+    private boolean inPrefList(int code, int[] pref) {
+        if (code < pref.length && code >= 0) return pref[code] > 0;
+        return false;
+    }
+
+    private int distanceFrom(Key k, int x, int y) {
+        if (y > k.y && y < k.y + k.height) {
+            return Math.abs(k.x + k.width / 2 - x);
+        } else {
+            return Integer.MAX_VALUE;
+        }
+    }
+
     @Override
     public int[] getNearestKeys(int x, int y) {
         if (mCurrentlyInSpace) {
@@ -512,7 +619,8 @@ public class LatinKeyboard extends Keyboard {
          */
         @Override
         public boolean isInside(int x, int y) {
-            return LatinKeyboard.this.isInside(this, x, y);
+            boolean result = LatinKeyboard.this.isInside(this, x, y);
+            return result;
         }
 
         boolean isInsideSuper(int x, int y) {
diff --git a/src/com/android/inputmethod/latin/LatinKeyboardView.java b/src/com/android/inputmethod/latin/LatinKeyboardView.java
index 05f8aff36..bdac4a5b5 100644
--- a/src/com/android/inputmethod/latin/LatinKeyboardView.java
+++ b/src/com/android/inputmethod/latin/LatinKeyboardView.java
@@ -20,6 +20,7 @@ import java.util.List;
 
 import android.content.Context;
 import android.graphics.Canvas;
+import android.graphics.Paint;
 import android.inputmethodservice.Keyboard;
 import android.inputmethodservice.KeyboardView;
 import android.inputmethodservice.Keyboard.Key;
@@ -80,6 +81,11 @@ public class LatinKeyboardView extends KeyboardView {
     @Override
     public boolean onTouchEvent(MotionEvent me) {
         LatinKeyboard keyboard = (LatinKeyboard) getKeyboard();
+        if (DEBUG_LINE) {
+            mLastX = (int) me.getX();
+            mLastY = (int) me.getY();
+            invalidate();
+        }
         // Reset any bounding box controls in the keyboard
         if (me.getAction() == MotionEvent.ACTION_DOWN) {
             keyboard.keyReleased();
@@ -203,6 +209,7 @@ public class LatinKeyboardView extends KeyboardView {
     /****************************  INSTRUMENTATION  *******************************/
 
     static final boolean DEBUG_AUTO_PLAY = false;
+    static final boolean DEBUG_LINE = false;
     private static final int MSG_TOUCH_DOWN = 1;
     private static final int MSG_TOUCH_UP = 2;
     
@@ -213,6 +220,9 @@ public class LatinKeyboardView extends KeyboardView {
     private boolean mDownDelivered;
     private Key[] mAsciiKeys = new Key[256];
     private boolean mPlaying;
+    private int mLastX;
+    private int mLastY;
+    private Paint mPaint;
 
     @Override
     public void setKeyboard(Keyboard k) {
@@ -309,5 +319,14 @@ public class LatinKeyboardView extends KeyboardView {
                 mHandler2.sendEmptyMessageDelayed(MSG_TOUCH_DOWN, 20);
             }
         }
+        if (DEBUG_LINE) {
+            if (mPaint == null) {
+                mPaint = new Paint();
+                mPaint.setColor(0x80FFFFFF);
+                mPaint.setAntiAlias(false);
+            }
+            c.drawLine(mLastX, 0, mLastX, getHeight(), mPaint);
+            c.drawLine(0, mLastY, getWidth(), mLastY, mPaint);
+        }
     }
 }
diff --git a/src/com/android/inputmethod/latin/Suggest.java b/src/com/android/inputmethod/latin/Suggest.java
index c3fe99635..5833c02a5 100755
--- a/src/com/android/inputmethod/latin/Suggest.java
+++ b/src/com/android/inputmethod/latin/Suggest.java
@@ -52,6 +52,12 @@ public class Suggest implements Dictionary.WordCallback {
     private int mPrefMaxSuggestions = 12;
 
     private int[] mPriorities = new int[mPrefMaxSuggestions];
+    // Handle predictive correction for only the first 1280 characters for performance reasons
+    // If we support scripts that need latin characters beyond that, we should probably use some
+    // kind of a sparse array or language specific list with a mapping lookup table.
+    // 1280 is the size of the BASE_CHARS array in ExpandableDictionary, which is a basic set of
+    // latin characters.
+    private int[] mNextLettersFrequencies = new int[1280];
     private ArrayList<CharSequence> mSuggestions = new ArrayList<CharSequence>();
     private ArrayList<CharSequence> mStringPool = new ArrayList<CharSequence>();
     private boolean mHaveCorrection;
@@ -162,7 +168,8 @@ public class Suggest implements Dictionary.WordCallback {
         mCapitalize = wordComposer.isCapitalized();
         collectGarbage();
         Arrays.fill(mPriorities, 0);
-        
+        Arrays.fill(mNextLettersFrequencies, 0);
+
         // Save a lowercase version of the original word
         mOriginalWord = wordComposer.getTypedWord();
         if (mOriginalWord != null) {
@@ -175,17 +182,17 @@ public class Suggest implements Dictionary.WordCallback {
         if (wordComposer.size() > 1) {
             if (mUserDictionary != null || mContactsDictionary != null) {
                 if (mUserDictionary != null) {
-                    mUserDictionary.getWords(wordComposer, this);
+                    mUserDictionary.getWords(wordComposer, this, mNextLettersFrequencies);
                 }
                 if (mContactsDictionary != null) {
-                    mContactsDictionary.getWords(wordComposer, this);
+                    mContactsDictionary.getWords(wordComposer, this, mNextLettersFrequencies);
                 }
 
                 if (mSuggestions.size() > 0 && isValidWord(mOriginalWord)) {
                     mHaveCorrection = true;
                 }
             }
-            mMainDict.getWords(wordComposer, this);
+            mMainDict.getWords(wordComposer, this, mNextLettersFrequencies);
             if (mCorrectionMode == CORRECTION_FULL && mSuggestions.size() > 0) {
                 mHaveCorrection = true;
             }
@@ -229,6 +236,10 @@ public class Suggest implements Dictionary.WordCallback {
         return mSuggestions;
     }
 
+    public int[] getNextLettersFrequencies() {
+        return mNextLettersFrequencies;
+    }
+
     private void removeDupes() {
         final ArrayList<CharSequence> suggestions = mSuggestions;
         if (suggestions.size() < 2) return;
diff --git a/src/com/android/inputmethod/latin/UserDictionary.java b/src/com/android/inputmethod/latin/UserDictionary.java
index 2f3447abd..edd82aaa3 100644
--- a/src/com/android/inputmethod/latin/UserDictionary.java
+++ b/src/com/android/inputmethod/latin/UserDictionary.java
@@ -94,9 +94,10 @@ public class UserDictionary extends ExpandableDictionary {
     }
 
     @Override
-    public synchronized void getWords(final WordComposer codes, final WordCallback callback) {
+    public synchronized void getWords(final WordComposer codes, final WordCallback callback,
+            int[] nextLettersFrequencies) {
         if (mRequiresReload) loadDictionary();
-        super.getWords(codes, callback);
+        super.getWords(codes, callback, nextLettersFrequencies);
     }
 
     @Override