- separate dict (uses xml)

- retrieve bigrams that only starts with character typed and neighbor keys
- contacts bigram
- performance measure

bug: 2873133

Change-Id: If97c005b18c82f3fafef50009dd2dfd972b0ab8f

1 files changed, 160 insertions, 33 deletions

diff --git a/java/src/com/android/inputmethod/latin/ExpandableDictionary.java b/java/src/com/android/inputmethod/latin/ExpandableDictionary.java
index d8a9547c1..53f9ed8c8 100644
--- a/java/src/com/android/inputmethod/latin/ExpandableDictionary.java
+++ b/java/src/com/android/inputmethod/latin/ExpandableDictionary.java
@@ -16,22 +16,32 @@
 
 package com.android.inputmethod.latin;
 
+import java.util.LinkedList;
+
 import android.content.Context;
 import android.os.AsyncTask;
+import android.os.SystemClock;
+import android.util.Log;
 
 /**
  * Base class for an in-memory dictionary that can grow dynamically and can
  * be searched for suggestions and valid words.
  */
 public class ExpandableDictionary extends Dictionary {
+    /**
+     * There is difference between what java and native code can handle.
+     * It uses 32 because Java stack overflows when greater value is used.
+     */
+    protected static final int MAX_WORD_LENGTH = 32;
+
     private Context mContext;
     private char[] mWordBuilder = new char[MAX_WORD_LENGTH];
     private int mDicTypeId;
     private int mMaxDepth;
     private int mInputLength;
     private int[] mNextLettersFrequencies;
+    private StringBuilder sb = new StringBuilder(MAX_WORD_LENGTH);
 
-    public static final int MAX_WORD_LENGTH = 32;
     private static final char QUOTE = '\'';
 
     private boolean mRequiresReload;
@@ -45,7 +55,9 @@ public class ExpandableDictionary extends Dictionary {
         char code;
         int frequency;
         boolean terminal;
+        Node parent;
         NodeArray children;
+        LinkedList<NextWord> ngrams; // Supports ngram
     }
 
     static class NodeArray {
@@ -69,6 +81,18 @@ public class ExpandableDictionary extends Dictionary {
         }
     }
 
+    static class NextWord {
+        Node word;
+        NextWord nextWord;
+        int frequency;
+
+        NextWord(Node word, int frequency) {
+            this.word = word;
+            this.frequency = frequency;
+        }
+    }
+
+
     private NodeArray mRoots;
 
     private int[][] mCodes;
@@ -117,12 +141,11 @@ public class ExpandableDictionary extends Dictionary {
     }
 
     public void addWord(String word, int frequency) {
-        addWordRec(mRoots, word, 0, frequency);
+        addWordRec(mRoots, word, 0, frequency, null);
     }
 
-    private void addWordRec(NodeArray children, final String word,
-            final int depth, final int frequency) {
-        
+    private void addWordRec(NodeArray children, final String word, final int depth,
+            final int frequency, Node parentNode) {
         final int wordLength = word.length();
         final char c = word.charAt(depth);
         // Does children have the current character?
@@ -139,6 +162,7 @@ public class ExpandableDictionary extends Dictionary {
         if (!found) {
             childNode = new Node();
             childNode.code = c;
+            childNode.parent = parentNode;
             children.add(childNode);
         }
         if (wordLength == depth + 1) {
@@ -151,7 +175,7 @@ public class ExpandableDictionary extends Dictionary {
         if (childNode.children == null) {
             childNode.children = new NodeArray();
         }
-        addWordRec(childNode.children, word, depth + 1, frequency);
+        addWordRec(childNode.children, word, depth + 1, frequency, childNode);
     }
 
     @Override
@@ -185,7 +209,7 @@ public class ExpandableDictionary extends Dictionary {
             if (mRequiresReload) startDictionaryLoadingTaskLocked();
             if (mUpdatingDictionary) return false;
         }
-        final int freq = getWordFrequencyRec(mRoots, word, 0, word.length());
+        final int freq = getWordFrequency(word);
         return freq > -1;
     }
 
@@ -193,32 +217,8 @@ public class ExpandableDictionary extends Dictionary {
      * Returns the word's frequency or -1 if not found
      */
     public int getWordFrequency(CharSequence word) {
-        return getWordFrequencyRec(mRoots, word, 0, word.length());
-    }
-
-    /**
-     * Returns the word's frequency or -1 if not found
-     */
-    private int getWordFrequencyRec(final NodeArray children, final CharSequence word, 
-            final int offset, final int length) {
-        final int count = children.length;
-        char currentChar = word.charAt(offset);
-        for (int j = 0; j < count; j++) {
-            final Node node = children.data[j];
-            if (node.code == currentChar) {
-                if (offset == length - 1) {
-                    if (node.terminal) {
-                        return node.frequency;
-                    }
-                } else {
-                    if (node.children != null) {
-                        int freq = getWordFrequencyRec(node.children, word, offset + 1, length);
-                        if (freq > -1) return freq;
-                    }
-                }
-            }
-        }
-        return -1;
+        Node node = searchNode(mRoots, word, 0, word.length());
+        return (node == null) ? -1 : node.frequency;
     }
 
     /**
@@ -325,6 +325,133 @@ public class ExpandableDictionary extends Dictionary {
         }
     }
 
+    /**
+     * Adds bigrams to the in-memory trie structure that is being used to retrieve any word
+     * @param addFrequency adding frequency of the pair
+     * @return returns the final frequency
+     */
+    protected int addBigrams(String word1, String word2, int addFrequency) {
+        Node firstWord = searchWord(mRoots, word1, 0, null);
+        Node secondWord = searchWord(mRoots, word2, 0, null);
+        LinkedList<NextWord> bigram = firstWord.ngrams;
+        if (bigram == null || bigram.size() == 0) {
+            firstWord.ngrams = new LinkedList<NextWord>();
+            bigram = firstWord.ngrams;
+        } else {
+            for (NextWord nw : bigram) {
+                if (nw.word == secondWord) {
+                    nw.frequency += addFrequency;
+                    return nw.frequency;
+                }
+            }
+        }
+        NextWord nw = new NextWord(secondWord, addFrequency);
+        firstWord.ngrams.add(nw);
+        return addFrequency;
+    }
+
+    /**
+     * Searches for the word and add the word if it does not exist.
+     * @return Returns the terminal node of the word we are searching for.
+     */
+    private Node searchWord(NodeArray children, String word, int depth, Node parentNode) {
+        final int wordLength = word.length();
+        final char c = word.charAt(depth);
+        // Does children have the current character?
+        final int childrenLength = children.length;
+        Node childNode = null;
+        boolean found = false;
+        for (int i = 0; i < childrenLength; i++) {
+            childNode = children.data[i];
+            if (childNode.code == c) {
+                found = true;
+                break;
+            }
+        }
+        if (!found) {
+            childNode = new Node();
+            childNode.code = c;
+            childNode.parent = parentNode;
+            children.add(childNode);
+        }
+        if (wordLength == depth + 1) {
+            // Terminate this word
+            childNode.terminal = true;
+            return childNode;
+        }
+        if (childNode.children == null) {
+            childNode.children = new NodeArray();
+        }
+        return searchWord(childNode.children, word, depth + 1, childNode);
+    }
+
+    @Override
+    public void getBigrams(final WordComposer codes, final CharSequence previousWord,
+            final WordCallback callback, int[] nextLettersFrequencies) {
+        synchronized (mUpdatingLock) {
+            // If we need to update, start off a background task
+            if (mRequiresReload) startDictionaryLoadingTaskLocked();
+            // Currently updating contacts, don't return any results.
+            if (mUpdatingDictionary) return;
+        }
+
+        Node prevWord = searchNode(mRoots, previousWord, 0, previousWord.length());
+        if (prevWord != null && prevWord.ngrams != null) {
+            reverseLookUp(prevWord.ngrams, callback);
+        }
+    }
+
+    /**
+     * reverseLookUp retrieves the full word given a list of terminal nodes and adds those words
+     * through callback.
+     * @param terminalNodes list of terminal nodes we want to add
+     */
+    private void reverseLookUp(LinkedList<NextWord> terminalNodes,
+            final WordCallback callback) {
+        Node node;
+        int freq;
+        for (NextWord nextWord : terminalNodes) {
+            node = nextWord.word;
+            freq = nextWord.frequency;
+            sb.setLength(0);
+            do {
+                sb.insert(0, node.code);
+                node = node.parent;
+            } while(node != null);
+
+            // TODO better way to feed char array?
+            callback.addWord(sb.toString().toCharArray(), 0, sb.length(), freq, mDicTypeId,
+                    DataType.BIGRAM);
+        }
+    }
+
+    /**
+     * Search for the terminal node of the word
+     * @return Returns the terminal node of the word if the word exists
+     */
+    private Node searchNode(final NodeArray children, final CharSequence word, final int offset,
+            final int length) {
+        // TODO Consider combining with addWordRec
+        final int count = children.length;
+        char currentChar = word.charAt(offset);
+        for (int j = 0; j < count; j++) {
+            final Node node = children.data[j];
+            if (node.code == currentChar) {
+                if (offset == length - 1) {
+                    if (node.terminal) {
+                        return node;
+                    }
+                } else {
+                    if (node.children != null) {
+                        Node returnNode = searchNode(node.children, word, offset + 1, length);
+                        if (returnNode != null) return returnNode;
+                    }
+                }
+            }
+        }
+        return null;
+    }
+
     protected void clearDictionary() {
         mRoots = new NodeArray();
     }