Merge "Record number of words entered"
diff --git a/dictionaries/cs_wordlist.combined.gz b/dictionaries/cs_wordlist.combined.gz
index b8d4d60..d69ef64 100644
--- a/dictionaries/cs_wordlist.combined.gz
+++ b/dictionaries/cs_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/de_wordlist.combined.gz b/dictionaries/de_wordlist.combined.gz
index 8d0eb6c..f5cce9d 100644
--- a/dictionaries/de_wordlist.combined.gz
+++ b/dictionaries/de_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/en_GB_wordlist.combined.gz b/dictionaries/en_GB_wordlist.combined.gz
index 93c5f3d..5e2a9df 100644
--- a/dictionaries/en_GB_wordlist.combined.gz
+++ b/dictionaries/en_GB_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/en_US_wordlist.combined.gz b/dictionaries/en_US_wordlist.combined.gz
index c2421dc..33ef1c1 100644
--- a/dictionaries/en_US_wordlist.combined.gz
+++ b/dictionaries/en_US_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/en_wordlist.combined.gz b/dictionaries/en_wordlist.combined.gz
index 3732993..c39f052 100644
--- a/dictionaries/en_wordlist.combined.gz
+++ b/dictionaries/en_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/es_wordlist.combined.gz b/dictionaries/es_wordlist.combined.gz
index e7f9125..bf72810 100644
--- a/dictionaries/es_wordlist.combined.gz
+++ b/dictionaries/es_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/fr_wordlist.combined.gz b/dictionaries/fr_wordlist.combined.gz
index 7de4625..4b55261 100644
--- a/dictionaries/fr_wordlist.combined.gz
+++ b/dictionaries/fr_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/hr_wordlist.combined.gz b/dictionaries/hr_wordlist.combined.gz
index 68b15c2..7694a2a 100644
--- a/dictionaries/hr_wordlist.combined.gz
+++ b/dictionaries/hr_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/it_wordlist.combined.gz b/dictionaries/it_wordlist.combined.gz
index 187e3b2..3b84cd7 100644
--- a/dictionaries/it_wordlist.combined.gz
+++ b/dictionaries/it_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/lt_wordlist.combined.gz b/dictionaries/lt_wordlist.combined.gz
index 0197616..316a5af 100644
--- a/dictionaries/lt_wordlist.combined.gz
+++ b/dictionaries/lt_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/lv_wordlist.combined.gz b/dictionaries/lv_wordlist.combined.gz
index f2338c2..b036ac2 100644
--- a/dictionaries/lv_wordlist.combined.gz
+++ b/dictionaries/lv_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/nb_wordlist.combined.gz b/dictionaries/nb_wordlist.combined.gz
index f663bbe..b6e0d42 100644
--- a/dictionaries/nb_wordlist.combined.gz
+++ b/dictionaries/nb_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/nl_wordlist.combined.gz b/dictionaries/nl_wordlist.combined.gz
index 7b4843f..48ab0f4 100644
--- a/dictionaries/nl_wordlist.combined.gz
+++ b/dictionaries/nl_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/ru_wordlist.combined.gz b/dictionaries/ru_wordlist.combined.gz
index 8b67e7c..1c85d66 100644
--- a/dictionaries/ru_wordlist.combined.gz
+++ b/dictionaries/ru_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/sl_wordlist.combined.gz b/dictionaries/sl_wordlist.combined.gz
index c12e7cb..41a576b 100644
--- a/dictionaries/sl_wordlist.combined.gz
+++ b/dictionaries/sl_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/sr_wordlist.combined.gz b/dictionaries/sr_wordlist.combined.gz
index bb85796..dec6ae8 100644
--- a/dictionaries/sr_wordlist.combined.gz
+++ b/dictionaries/sr_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/sv_wordlist.combined.gz b/dictionaries/sv_wordlist.combined.gz
index c107ca9..0471772 100644
--- a/dictionaries/sv_wordlist.combined.gz
+++ b/dictionaries/sv_wordlist.combined.gz
Binary files differ
diff --git a/dictionaries/tr_wordlist.combined.gz b/dictionaries/tr_wordlist.combined.gz
index b330415..fae79ca 100644
--- a/dictionaries/tr_wordlist.combined.gz
+++ b/dictionaries/tr_wordlist.combined.gz
Binary files differ
diff --git a/java/proguard.flags b/java/proguard.flags
index 4da182b..c08a968 100644
--- a/java/proguard.flags
+++ b/java/proguard.flags
@@ -1,16 +1,16 @@
 # Keep classes and methods that have the @UsedForTesting annotation
 -keep @com.android.inputmethod.annotations.UsedForTesting class *
 -keepclassmembers class * {
-@com.android.inputmethod.annotations.UsedForTesting *;
+    @com.android.inputmethod.annotations.UsedForTesting *;
 }
 
 # Keep classes and methods that have the @ExternallyReferenced annotation
 -keep @com.android.inputmethod.annotations.ExternallyReferenced class *
 -keepclassmembers class * {
-@com.android.inputmethod.annotations.ExternallyReferenced *;
+    @com.android.inputmethod.annotations.ExternallyReferenced *;
 }
 
 # Keep native methods
--keep class * {
-native <methods>;
+-keepclassmembers class * {
+    native <methods>;
 }
diff --git a/java/res/raw/main_de.dict b/java/res/raw/main_de.dict
index a59f782..5d35e64 100644
--- a/java/res/raw/main_de.dict
+++ b/java/res/raw/main_de.dict
Binary files differ
diff --git a/java/res/raw/main_en.dict b/java/res/raw/main_en.dict
index 086874d..120e19b 100644
--- a/java/res/raw/main_en.dict
+++ b/java/res/raw/main_en.dict
Binary files differ
diff --git a/java/res/raw/main_es.dict b/java/res/raw/main_es.dict
index ac15d39..efc5075 100644
--- a/java/res/raw/main_es.dict
+++ b/java/res/raw/main_es.dict
Binary files differ
diff --git a/java/res/raw/main_fr.dict b/java/res/raw/main_fr.dict
index 9044c7e..fb43a1a 100644
--- a/java/res/raw/main_fr.dict
+++ b/java/res/raw/main_fr.dict
Binary files differ
diff --git a/java/res/raw/main_it.dict b/java/res/raw/main_it.dict
index e289cef..523f645 100644
--- a/java/res/raw/main_it.dict
+++ b/java/res/raw/main_it.dict
Binary files differ
diff --git a/java/res/raw/main_ru.dict b/java/res/raw/main_ru.dict
index 3e23617..86c368e 100644
--- a/java/res/raw/main_ru.dict
+++ b/java/res/raw/main_ru.dict
Binary files differ
diff --git a/java/src/com/android/inputmethod/latin/BinaryDictionaryFileDumper.java b/java/src/com/android/inputmethod/latin/BinaryDictionaryFileDumper.java
index 321e806..4b5d027 100644
--- a/java/src/com/android/inputmethod/latin/BinaryDictionaryFileDumper.java
+++ b/java/src/com/android/inputmethod/latin/BinaryDictionaryFileDumper.java
@@ -439,7 +439,6 @@
             final ContentProviderClient client, final String clientId) throws RemoteException {
         final String metadataFileUri = MetadataFileUriGetter.getMetadataUri(context);
         final String metadataAdditionalId = MetadataFileUriGetter.getMetadataAdditionalId(context);
-        if (TextUtils.isEmpty(metadataFileUri)) return;
         // Tell the content provider to reset all information about this client id
         final Uri metadataContentUri = getProviderUriBuilder(clientId)
                 .appendPath(QUERY_PATH_METADATA)
diff --git a/java/src/com/android/inputmethod/latin/BinaryDictionaryGetter.java b/java/src/com/android/inputmethod/latin/BinaryDictionaryGetter.java
index d0af59d..51dc852 100644
--- a/java/src/com/android/inputmethod/latin/BinaryDictionaryGetter.java
+++ b/java/src/com/android/inputmethod/latin/BinaryDictionaryGetter.java
@@ -19,11 +19,9 @@
 import android.content.Context;
 import android.content.SharedPreferences;
 import android.content.pm.PackageManager;
-import android.content.pm.PackageManager.NameNotFoundException;
 import android.content.res.AssetFileDescriptor;
 import android.util.Log;
 
-import com.android.inputmethod.latin.define.ProductionFlag;
 import com.android.inputmethod.latin.makedict.BinaryDictInputOutput;
 import com.android.inputmethod.latin.makedict.FormatSpec;
 import com.android.inputmethod.latin.utils.CollectionUtils;
@@ -293,13 +291,8 @@
             final Context context) {
 
         final boolean hasDefaultWordList = DictionaryFactory.isDictionaryAvailable(context, locale);
-        // We need internet access to do the following. Only do this if the package actually
-        // has the permission.
-        if (context.checkCallingOrSelfPermission(android.Manifest.permission.INTERNET)
-                == PackageManager.PERMISSION_GRANTED) {
-            BinaryDictionaryFileDumper.cacheWordListsFromContentProvider(locale, context,
-                    hasDefaultWordList);
-        }
+        BinaryDictionaryFileDumper.cacheWordListsFromContentProvider(locale, context,
+                hasDefaultWordList);
         final File[] cachedWordLists = getCachedWordLists(locale.toString(), context);
         final String mainDictId = DictionaryInfoUtils.getMainDictId(locale);
         final DictPackSettings dictPackSettings = new DictPackSettings(context);
diff --git a/java/src/com/android/inputmethod/latin/DebugSettings.java b/java/src/com/android/inputmethod/latin/DebugSettings.java
index d1cb39c..01ec7f9 100644
--- a/java/src/com/android/inputmethod/latin/DebugSettings.java
+++ b/java/src/com/android/inputmethod/latin/DebugSettings.java
@@ -16,21 +16,16 @@
 
 package com.android.inputmethod.latin;
 
-import android.content.Context;
 import android.content.SharedPreferences;
-import android.content.pm.PackageInfo;
-import android.content.pm.PackageManager.NameNotFoundException;
 import android.os.Bundle;
 import android.os.Process;
 import android.preference.CheckBoxPreference;
 import android.preference.Preference;
 import android.preference.PreferenceFragment;
 import android.preference.PreferenceScreen;
-import android.util.Log;
 
 import com.android.inputmethod.keyboard.KeyboardSwitcher;
 import com.android.inputmethod.latin.utils.Utils;
-import com.android.inputmethod.research.ResearchLogger;
 
 public final class DebugSettings extends PreferenceFragment
         implements SharedPreferences.OnSharedPreferenceChangeListener {
diff --git a/java/src/com/android/inputmethod/latin/ExternalDictionaryGetterForDebug.java b/java/src/com/android/inputmethod/latin/ExternalDictionaryGetterForDebug.java
index 18f4920..47d9bf3 100644
--- a/java/src/com/android/inputmethod/latin/ExternalDictionaryGetterForDebug.java
+++ b/java/src/com/android/inputmethod/latin/ExternalDictionaryGetterForDebug.java
@@ -19,6 +19,7 @@
 import android.app.AlertDialog;
 import android.content.Context;
 import android.content.DialogInterface;
+import android.content.DialogInterface.OnCancelListener;
 import android.content.DialogInterface.OnClickListener;
 import android.os.Environment;
 
@@ -59,7 +60,7 @@
         if (0 == fileNames.length) {
             showNoFileDialog(context);
         } else if (1 == fileNames.length) {
-            askInstallFile(context, fileNames[0]);
+            askInstallFile(context, SOURCE_FOLDER, fileNames[0], null /* completeRunnable */);
         } else {
             showChooseFileDialog(context, fileNames);
         }
@@ -82,14 +83,19 @@
                 .setItems(fileNames, new OnClickListener() {
                     @Override
                     public void onClick(final DialogInterface dialog, final int which) {
-                        askInstallFile(context, fileNames[which]);
+                        askInstallFile(context, SOURCE_FOLDER, fileNames[which],
+                                null /* completeRunnable */);
                     }
                 })
                 .create().show();
     }
 
-    private static void askInstallFile(final Context context, final String fileName) {
-        final File file = new File(SOURCE_FOLDER, fileName.toString());
+    /**
+     * Shows a dialog which offers the user to install the external dictionary.
+     */
+    public static void askInstallFile(final Context context, final String dirPath,
+            final String fileName, final Runnable completeRunnable) {
+        final File file = new File(dirPath, fileName.toString());
         final FileHeader header = DictionaryInfoUtils.getDictionaryFileHeaderOrNull(file);
         final StringBuilder message = new StringBuilder();
         final String locale = header.getLocaleString();
@@ -109,12 +115,26 @@
                     @Override
                     public void onClick(final DialogInterface dialog, final int which) {
                         dialog.dismiss();
+                        if (completeRunnable != null) {
+                            completeRunnable.run();
+                        }
                     }
                 }).setPositiveButton(android.R.string.ok, new OnClickListener() {
                     @Override
                     public void onClick(final DialogInterface dialog, final int which) {
                         installFile(context, file, header);
                         dialog.dismiss();
+                        if (completeRunnable != null) {
+                            completeRunnable.run();
+                        }
+                    }
+                }).setOnCancelListener(new OnCancelListener() {
+                    @Override
+                    public void onCancel(DialogInterface dialog) {
+                        // Canceled by the user by hitting the back key
+                        if (completeRunnable != null) {
+                            completeRunnable.run();
+                        }
                     }
                 }).create().show();
     }
diff --git a/java/src/com/android/inputmethod/latin/LatinIME.java b/java/src/com/android/inputmethod/latin/LatinIME.java
index c867436..0560cf5 100644
--- a/java/src/com/android/inputmethod/latin/LatinIME.java
+++ b/java/src/com/android/inputmethod/latin/LatinIME.java
@@ -43,7 +43,6 @@
 import android.os.SystemClock;
 import android.preference.PreferenceManager;
 import android.text.InputType;
-import android.text.Spanned;
 import android.text.TextUtils;
 import android.text.style.SuggestionSpan;
 import android.util.Log;
@@ -778,6 +777,7 @@
         // span, so we should reset our state unconditionally, even if restarting is true.
         mEnteredText = null;
         resetComposingState(true /* alsoResetLastComposedWord */);
+        if (isDifferentTextField) mHandler.postResumeSuggestions();
         mDeleteCount = 0;
         mSpaceState = SPACE_STATE_NONE;
         mRecapitalizeStatus.deactivate();
@@ -2522,21 +2522,15 @@
         final int numberOfCharsInWordBeforeCursor = range.getNumberOfCharsInWordBeforeCursor();
         if (numberOfCharsInWordBeforeCursor > mLastSelectionStart) return;
         final ArrayList<SuggestedWordInfo> suggestions = CollectionUtils.newArrayList();
-        final CharSequence word = range.mWord;
-        final String typedWord = word.toString();
-        if (word instanceof Spanned) {
-            final Spanned spanned = (Spanned)word;
-            int i = 0;
-            for (Object object : spanned.getSpans(0, spanned.length(),
-                    SuggestionSpan.class)) {
-                SuggestionSpan span = (SuggestionSpan)object;
-                for (String s : span.getSuggestions()) {
-                    ++i;
-                    if (!TextUtils.equals(s, typedWord)) {
-                        suggestions.add(new SuggestedWordInfo(s,
-                                SuggestionStripView.MAX_SUGGESTIONS - i,
-                                SuggestedWordInfo.KIND_RESUMED, Dictionary.TYPE_RESUMED));
-                    }
+        final String typedWord = range.mWord.toString();
+        int i = 0;
+        for (final SuggestionSpan span : range.getSuggestionSpansAtWord()) {
+            for (final String s : span.getSuggestions()) {
+                ++i;
+                if (!TextUtils.equals(s, typedWord)) {
+                    suggestions.add(new SuggestedWordInfo(s,
+                            SuggestionStripView.MAX_SUGGESTIONS - i,
+                            SuggestedWordInfo.KIND_RESUMED, Dictionary.TYPE_RESUMED));
                 }
             }
         }
diff --git a/java/src/com/android/inputmethod/latin/RichInputConnection.java b/java/src/com/android/inputmethod/latin/RichInputConnection.java
index 5391b13..6b22cb1 100644
--- a/java/src/com/android/inputmethod/latin/RichInputConnection.java
+++ b/java/src/com/android/inputmethod/latin/RichInputConnection.java
@@ -17,7 +17,9 @@
 package com.android.inputmethod.latin;
 
 import android.inputmethodservice.InputMethodService;
+import android.text.Spanned;
 import android.text.TextUtils;
+import android.text.style.SuggestionSpan;
 import android.util.Log;
 import android.view.KeyEvent;
 import android.view.inputmethod.CompletionInfo;
@@ -32,6 +34,7 @@
 import com.android.inputmethod.latin.utils.StringUtils;
 import com.android.inputmethod.research.ResearchLogger;
 
+import java.util.Arrays;
 import java.util.Locale;
 import java.util.regex.Pattern;
 
@@ -457,6 +460,66 @@
             return mWordAtCursorEndIndex - mCursorIndex;
         }
 
+        /**
+         * Gets the suggestion spans that are put squarely on the word, with the exact start
+         * and end of the span matching the boundaries of the word.
+         * @return the list of spans.
+         */
+        public SuggestionSpan[] getSuggestionSpansAtWord() {
+            if (!(mTextAtCursor instanceof Spanned && mWord instanceof Spanned)) {
+                return new SuggestionSpan[0];
+            }
+            final Spanned text = (Spanned)mTextAtCursor;
+            // Note: it's fine to pass indices negative or greater than the length of the string
+            // to the #getSpans() method. The reason we need to get from -1 to +1 is that, the
+            // spans were cut at the cursor position, and #getSpans(start, end) does not return
+            // spans that end at `start' or begin at `end'. Consider the following case:
+            //              this| is          (The | symbolizes the cursor position
+            //              ---- ---
+            // In this case, the cursor is in position 4, so the 0~7 span has been split into
+            // a 0~4 part and a 4~7 part.
+            // If we called #getSpans(0, 4) in this case, we would only get the part from 0 to 4
+            // of the span, and not the part from 4 to 7, so we would not realize the span actually
+            // extends from 0 to 7. But if we call #getSpans(-1, 5) we'll get both the 0~4 and
+            // the 4~7 spans and we can merge them accordingly.
+            // Any span starting more than 1 char away from the word boundaries in any direction
+            // does not touch the word, so we don't need to consider it. That's why requesting
+            // -1 ~ +1 is enough.
+            // Of course this is only relevant if the cursor is at one end of the word. If it's
+            // in the middle, the -1 and +1 are not necessary, but they are harmless.
+            final SuggestionSpan[] spans = text.getSpans(mWordAtCursorStartIndex - 1,
+                    mWordAtCursorEndIndex + 1, SuggestionSpan.class);
+            int readIndex = 0;
+            int writeIndex = 0;
+            for (; readIndex < spans.length; ++readIndex) {
+                final SuggestionSpan span = spans[readIndex];
+                // The span may be null, as we null them when we find duplicates. Cf a few lines
+                // down.
+                if (null == span) continue;
+                // Tentative span start and end. This may be modified later if we realize the
+                // same span is also applied to other parts of the string.
+                int spanStart = text.getSpanStart(span);
+                int spanEnd = text.getSpanEnd(span);
+                for (int i = readIndex + 1; i < spans.length; ++i) {
+                    if (span.equals(spans[i])) {
+                        // We found the same span somewhere else. Read the new extent of this
+                        // span, and adjust our values accordingly.
+                        spanStart = Math.min(spanStart, text.getSpanStart(spans[i]));
+                        spanEnd = Math.max(spanEnd, text.getSpanEnd(spans[i]));
+                        // ...and mark the span as processed.
+                        spans[i] = null;
+                    }
+                }
+                if (spanStart == mWordAtCursorStartIndex && spanEnd == mWordAtCursorEndIndex) {
+                    // If the span does not start and stop here, we ignore it. It probably extends
+                    // past the start or end of the word, as happens in missing space correction
+                    // or EasyEditSpans put by voice input.
+                    spans[writeIndex++] = spans[readIndex];
+                }
+            }
+            return writeIndex == readIndex ? spans : Arrays.copyOfRange(spans, 0, writeIndex);
+        }
+
         public Range(final CharSequence textAtCursor, final int wordAtCursorStartIndex,
                 final int wordAtCursorEndIndex, final int cursorIndex) {
             if (wordAtCursorStartIndex < 0 || cursorIndex < wordAtCursorStartIndex
diff --git a/java/src/com/android/inputmethod/latin/SettingsFragment.java b/java/src/com/android/inputmethod/latin/SettingsFragment.java
index 46fa191..f52e564 100644
--- a/java/src/com/android/inputmethod/latin/SettingsFragment.java
+++ b/java/src/com/android/inputmethod/latin/SettingsFragment.java
@@ -25,6 +25,7 @@
 import android.content.pm.ResolveInfo;
 import android.content.res.Resources;
 import android.media.AudioManager;
+import android.os.Build;
 import android.os.Bundle;
 import android.preference.CheckBoxPreference;
 import android.preference.ListPreference;
@@ -51,7 +52,10 @@
 public final class SettingsFragment extends InputMethodSettingsFragment
         implements SharedPreferences.OnSharedPreferenceChangeListener {
     private static final String TAG = SettingsFragment.class.getSimpleName();
-    private static final boolean DBG_USE_INTERNAL_USER_DICTIONARY_SETTINGS = false;
+    private static final boolean DBG_USE_INTERNAL_PERSONAL_DICTIONARY_SETTINGS = false;
+    private static final boolean USE_INTERNAL_PERSONAL_DICTIONARY_SETTIGS =
+            DBG_USE_INTERNAL_PERSONAL_DICTIONARY_SETTINGS
+                    || Build.VERSION.SDK_INT <= 18 /* Build.VERSION.JELLY_BEAN_MR2 */;
 
     private ListPreference mVoicePreference;
     private ListPreference mShowCorrectionSuggestionsPreference;
@@ -212,10 +216,11 @@
         final Preference editPersonalDictionary =
                 findPreference(Settings.PREF_EDIT_PERSONAL_DICTIONARY);
         final Intent editPersonalDictionaryIntent = editPersonalDictionary.getIntent();
-        final ResolveInfo ri = context.getPackageManager().resolveActivity(
-                editPersonalDictionaryIntent, PackageManager.MATCH_DEFAULT_ONLY);
-        if (DBG_USE_INTERNAL_USER_DICTIONARY_SETTINGS || ri == null) {
-            updateUserDictionaryPreference(editPersonalDictionary);
+        final ResolveInfo ri = USE_INTERNAL_PERSONAL_DICTIONARY_SETTIGS ? null
+                : context.getPackageManager().resolveActivity(
+                        editPersonalDictionaryIntent, PackageManager.MATCH_DEFAULT_ONLY);
+        if (ri == null) {
+            overwriteUserDictionaryPreference(editPersonalDictionary);
         }
 
         if (!Settings.readFromBuildConfigIfGestureInputEnabled(res)) {
@@ -470,7 +475,7 @@
         });
     }
 
-    private void updateUserDictionaryPreference(Preference userDictionaryPreference) {
+    private void overwriteUserDictionaryPreference(Preference userDictionaryPreference) {
         final Activity activity = getActivity();
         final TreeSet<String> localeList = UserDictionaryList.getUserDictionaryLocalesSet(activity);
         if (null == localeList) {
diff --git a/java/src/com/android/inputmethod/latin/SettingsValues.java b/java/src/com/android/inputmethod/latin/SettingsValues.java
index 8eadf73..2d325a4 100644
--- a/java/src/com/android/inputmethod/latin/SettingsValues.java
+++ b/java/src/com/android/inputmethod/latin/SettingsValues.java
@@ -34,7 +34,7 @@
 
 /**
  * When you call the constructor of this class, you may want to change the current system locale by
- * using {@link LocaleUtils.RunInLocale}.
+ * using {@link com.android.inputmethod.latin.utils.LocaleUtils.RunInLocale}.
  */
 public final class SettingsValues {
     private static final String TAG = SettingsValues.class.getSimpleName();
diff --git a/java/src/com/android/inputmethod/latin/userdictionary/UserDictionaryList.java b/java/src/com/android/inputmethod/latin/userdictionary/UserDictionaryList.java
index e7cf0d3..37c390d 100644
--- a/java/src/com/android/inputmethod/latin/userdictionary/UserDictionaryList.java
+++ b/java/src/com/android/inputmethod/latin/userdictionary/UserDictionaryList.java
@@ -17,6 +17,7 @@
 package com.android.inputmethod.latin.userdictionary;
 
 import android.app.Activity;
+import android.content.Context;
 import android.content.Intent;
 import android.database.Cursor;
 import android.os.Bundle;
@@ -25,10 +26,14 @@
 import android.preference.PreferenceGroup;
 import android.provider.UserDictionary;
 import android.text.TextUtils;
+import android.view.inputmethod.InputMethodInfo;
+import android.view.inputmethod.InputMethodManager;
+import android.view.inputmethod.InputMethodSubtype;
 
 import com.android.inputmethod.latin.R;
 import com.android.inputmethod.latin.utils.LocaleUtils;
 
+import java.util.List;
 import java.util.Locale;
 import java.util.TreeSet;
 
@@ -52,8 +57,7 @@
         final Cursor cursor = activity.managedQuery(UserDictionary.Words.CONTENT_URI,
                 new String[] { UserDictionary.Words.LOCALE },
                 null, null, null);
-        final TreeSet<String> localeList = new TreeSet<String>();
-        boolean addedAllLocale = false;
+        final TreeSet<String> localeSet = new TreeSet<String>();
         if (null == cursor) {
             // The user dictionary service is not present or disabled. Return null.
             return null;
@@ -61,20 +65,39 @@
             final int columnIndex = cursor.getColumnIndex(UserDictionary.Words.LOCALE);
             do {
                 final String locale = cursor.getString(columnIndex);
-                final boolean allLocale = TextUtils.isEmpty(locale);
-                localeList.add(allLocale ? "" : locale);
-                if (allLocale) {
-                    addedAllLocale = true;
-                }
+                localeSet.add(null != locale ? locale : "");
             } while (cursor.moveToNext());
         }
-        if (!UserDictionarySettings.IS_SHORTCUT_API_SUPPORTED && !addedAllLocale) {
+        if (!UserDictionarySettings.IS_SHORTCUT_API_SUPPORTED) {
             // For ICS, we need to show "For all languages" in case that the keyboard locale
             // is different from the system locale
-            localeList.add("");
+            localeSet.add("");
         }
-        localeList.add(Locale.getDefault().toString());
-        return localeList;
+
+        final InputMethodManager imm =
+                (InputMethodManager)activity.getSystemService(Context.INPUT_METHOD_SERVICE);
+        final List<InputMethodInfo> imis = imm.getEnabledInputMethodList();
+        for (final InputMethodInfo imi : imis) {
+            final List<InputMethodSubtype> subtypes =
+                    imm.getEnabledInputMethodSubtypeList(
+                            imi, true /* allowsImplicitlySelectedSubtypes */);
+            for (InputMethodSubtype subtype : subtypes) {
+                final String locale = subtype.getLocale();
+                if (!TextUtils.isEmpty(locale)) {
+                    localeSet.add(locale);
+                }
+            }
+        }
+
+        // We come here after we have collected locales from existing user dictionary entries and
+        // enabled subtypes. If we already have the locale-without-country version of the system
+        // locale, we don't add the system locale to avoid confusion even though it's technically
+        // correct to add it.
+        if (!localeSet.contains(Locale.getDefault().getLanguage().toString())) {
+            localeSet.add(Locale.getDefault().toString());
+        }
+
+        return localeSet;
     }
 
     /**
diff --git a/java/src/com/android/inputmethod/research/FeedbackActivity.java b/java/src/com/android/inputmethod/research/FeedbackActivity.java
index b985fda..520b88d 100644
--- a/java/src/com/android/inputmethod/research/FeedbackActivity.java
+++ b/java/src/com/android/inputmethod/research/FeedbackActivity.java
@@ -18,7 +18,6 @@
 
 import android.app.Activity;
 import android.os.Bundle;
-import android.widget.CheckBox;
 
 import com.android.inputmethod.latin.R;
 
diff --git a/java/src/com/android/inputmethod/research/FeedbackFragment.java b/java/src/com/android/inputmethod/research/FeedbackFragment.java
index a073829..75fbbf1 100644
--- a/java/src/com/android/inputmethod/research/FeedbackFragment.java
+++ b/java/src/com/android/inputmethod/research/FeedbackFragment.java
@@ -16,7 +16,6 @@
 
 package com.android.inputmethod.research;
 
-import android.app.Activity;
 import android.app.Fragment;
 import android.os.Bundle;
 import android.text.Editable;
diff --git a/java/src/com/android/inputmethod/research/ResearchLog.java b/java/src/com/android/inputmethod/research/ResearchLog.java
index fde2798..88207c0 100644
--- a/java/src/com/android/inputmethod/research/ResearchLog.java
+++ b/java/src/com/android/inputmethod/research/ResearchLog.java
@@ -27,7 +27,6 @@
 import java.io.File;
 import java.io.FileNotFoundException;
 import java.io.IOException;
-import java.io.OutputStream;
 import java.io.OutputStreamWriter;
 import java.util.concurrent.Callable;
 import java.util.concurrent.Executors;
diff --git a/java/src/com/android/inputmethod/research/UploaderService.java b/java/src/com/android/inputmethod/research/UploaderService.java
index d2db349..8bd46c1 100644
--- a/java/src/com/android/inputmethod/research/UploaderService.java
+++ b/java/src/com/android/inputmethod/research/UploaderService.java
@@ -24,8 +24,6 @@
 import android.os.Bundle;
 import android.os.SystemClock;
 
-import com.android.inputmethod.latin.define.ProductionFlag;
-
 /**
  * Service to invoke the uploader.
  *
@@ -33,8 +31,6 @@
  */
 public final class UploaderService extends IntentService {
     private static final String TAG = UploaderService.class.getSimpleName();
-    private static final boolean DEBUG = false
-            && ProductionFlag.USES_DEVELOPMENT_ONLY_DIAGNOSTICS_DEBUG;
     public static final long RUN_INTERVAL = AlarmManager.INTERVAL_HOUR;
     public static final String EXTRA_UPLOAD_UNCONDITIONALLY = UploaderService.class.getName()
             + ".extra.UPLOAD_UNCONDITIONALLY";
diff --git a/native/jni/Android.mk b/native/jni/Android.mk
index d5df6b6..f89eea7 100644
--- a/native/jni/Android.mk
+++ b/native/jni/Android.mk
@@ -70,6 +70,7 @@
         proximity_info_state_utils.cpp) \
     suggest/core/policy/weighting.cpp \
     suggest/core/session/dic_traverse_session.cpp \
+    suggest/policyimpl/dictionary/patricia_trie_policy.cpp \
     suggest/policyimpl/gesture/gesture_suggest_policy_factory.cpp \
     $(addprefix suggest/policyimpl/typing/, \
         scoring_params.cpp \
diff --git a/native/jni/com_android_inputmethod_latin_BinaryDictionary.cpp b/native/jni/com_android_inputmethod_latin_BinaryDictionary.cpp
index 33b6a6f..a93bbeb 100644
--- a/native/jni/com_android_inputmethod_latin_BinaryDictionary.cpp
+++ b/native/jni/com_android_inputmethod_latin_BinaryDictionary.cpp
@@ -37,7 +37,17 @@
 
 class ProximityInfo;
 
-static void releaseDictBuf(const void *dictBuf, const size_t length, const int fd);
+// Helper method
+static void releaseDictBuf(const void *dictBuf, const size_t length, const int fd) {
+    int ret = munmap(const_cast<void *>(dictBuf), length);
+    if (ret != 0) {
+        AKLOGE("DICT: Failure in munmap. ret=%d errno=%d", ret, errno);
+    }
+    ret = close(fd);
+    if (ret != 0) {
+        AKLOGE("DICT: Failure in close. ret=%d errno=%d", ret, errno);
+    }
+}
 
 static jlong latinime_BinaryDictionary_open(JNIEnv *env, jclass clazz, jstring sourceDir,
         jlong dictOffset, jlong dictSize, jboolean isUpdatable) {
@@ -77,8 +87,8 @@
         return 0;
     }
     Dictionary *dictionary = 0;
-    if (BinaryDictionaryFormat::UNKNOWN_VERSION
-            == BinaryDictionaryFormat::detectFormatVersion(static_cast<uint8_t *>(dictBuf),
+    if (BinaryDictionaryFormatUtils::UNKNOWN_VERSION
+            == BinaryDictionaryFormatUtils::detectFormatVersion(static_cast<uint8_t *>(dictBuf),
                     static_cast<int>(dictSize))) {
         AKLOGE("DICT: dictionary format is unknown, bad magic number");
         releaseDictBuf(static_cast<const char *>(dictBuf) - offset, adjDictSize, fd);
@@ -91,6 +101,19 @@
     return reinterpret_cast<jlong>(dictionary);
 }
 
+static void latinime_BinaryDictionary_close(JNIEnv *env, jclass clazz, jlong dict) {
+    Dictionary *dictionary = reinterpret_cast<Dictionary *>(dict);
+    if (!dictionary) return;
+    const BinaryDictionaryInfo *const binaryDictionaryInfo = dictionary->getBinaryDictionaryInfo();
+    const int dictBufOffset = binaryDictionaryInfo->getDictBufOffset();
+    const void *dictBuf = binaryDictionaryInfo->getDictBuf();
+    if (!dictBuf) return;
+    releaseDictBuf(static_cast<const char *>(dictBuf) - dictBufOffset,
+            binaryDictionaryInfo->getDictSize() + dictBufOffset,
+            binaryDictionaryInfo->getMmapFd());
+    delete dictionary;
+}
+
 static int latinime_BinaryDictionary_getSuggestions(JNIEnv *env, jclass clazz, jlong dict,
         jlong proximityInfo, jlong dicTraverseSession, jintArray xCoordinatesArray,
         jintArray yCoordinatesArray, jintArray timesArray, jintArray pointerIdsArray,
@@ -222,30 +245,6 @@
             afterCodePoints, afterLength);
 }
 
-static void latinime_BinaryDictionary_close(JNIEnv *env, jclass clazz, jlong dict) {
-    Dictionary *dictionary = reinterpret_cast<Dictionary *>(dict);
-    if (!dictionary) return;
-    const BinaryDictionaryInfo *const binaryDictionaryInfo = dictionary->getBinaryDictionaryInfo();
-    const int dictBufOffset = binaryDictionaryInfo->getDictBufOffset();
-    const void *dictBuf = binaryDictionaryInfo->getDictBuf();
-    if (!dictBuf) return;
-    releaseDictBuf(static_cast<const char *>(dictBuf) - dictBufOffset,
-            binaryDictionaryInfo->getDictSize() + dictBufOffset,
-            binaryDictionaryInfo->getMmapFd());
-    delete dictionary;
-}
-
-static void releaseDictBuf(const void *dictBuf, const size_t length, const int fd) {
-    int ret = munmap(const_cast<void *>(dictBuf), length);
-    if (ret != 0) {
-        AKLOGE("DICT: Failure in munmap. ret=%d errno=%d", ret, errno);
-    }
-    ret = close(fd);
-    if (ret != 0) {
-        AKLOGE("DICT: Failure in close. ret=%d errno=%d", ret, errno);
-    }
-}
-
 static void latinime_BinaryDictionary_addUnigramWord(JNIEnv *env, jclass clazz, jlong dict,
         jintArray word, jint probability) {
     Dictionary *dictionary = reinterpret_cast<Dictionary *>(dict);
diff --git a/native/jni/src/defines.h b/native/jni/src/defines.h
index e349aed..cb66814 100644
--- a/native/jni/src/defines.h
+++ b/native/jni/src/defines.h
@@ -270,6 +270,7 @@
 #define NOT_A_COORDINATE (-1)
 #define NOT_AN_INDEX (-1)
 #define NOT_A_PROBABILITY (-1)
+#define NOT_A_DICT_POS (S_INT_MIN)
 
 #define KEYCODE_SPACE ' '
 #define KEYCODE_SINGLE_QUOTE '\''
diff --git a/native/jni/src/suggest/core/dicnode/dic_node.h b/native/jni/src/suggest/core/dicnode/dic_node.h
index c700b01..52db8e9 100644
--- a/native/jni/src/suggest/core/dicnode/dic_node.h
+++ b/native/jni/src/suggest/core/dicnode/dic_node.h
@@ -97,7 +97,6 @@
     DicNode &operator=(const DicNode &dicNode);
     virtual ~DicNode() {}
 
-    // TODO: minimize arguments by looking binary_format
     // Init for copy
     void initByCopy(const DicNode *dicNode) {
         mIsUsed = true;
@@ -107,14 +106,15 @@
         PROF_NODE_COPY(&dicNode->mProfiler, mProfiler);
     }
 
-    // TODO: minimize arguments by looking binary_format
     // Init for root with prevWordNodePos which is used for bigram
-    void initAsRoot(const int pos, const int childrenPos, const int childrenCount,
-            const int prevWordNodePos) {
+    void initAsRoot(const int rootGroupPos, const int prevWordNodePos) {
         mIsUsed = true;
         mIsCachedForNextSuggestion = false;
         mDicNodeProperties.init(
-                pos, 0, childrenPos, 0, 0, 0, childrenCount, 0, 0, false, false, true, 0, 0);
+                NOT_A_DICT_POS, 0 /* flags */, rootGroupPos, NOT_A_DICT_POS /* attributesPos */,
+                NOT_A_CODE_POINT /* nodeCodePoint */, NOT_A_PROBABILITY /* probability */,
+                false /* isTerminal */, true /* hasChildren */, 0 /* depth */,
+                0 /* terminalDepth */);
         mDicNodeState.init(prevWordNodePos);
         PROF_NODE_RESET(mProfiler);
     }
@@ -128,14 +128,15 @@
         PROF_NODE_COPY(&parentNode->mProfiler, mProfiler);
     }
 
-    // TODO: minimize arguments by looking binary_format
     // Init for root with previous word
-    void initAsRootWithPreviousWord(DicNode *dicNode, const int pos, const int childrenPos,
-            const int childrenCount) {
+    void initAsRootWithPreviousWord(DicNode *dicNode, const int rootGroupPos) {
         mIsUsed = true;
         mIsCachedForNextSuggestion = dicNode->mIsCachedForNextSuggestion;
         mDicNodeProperties.init(
-                pos, 0, childrenPos, 0, 0, 0, childrenCount, 0, 0, false, false, true, 0, 0);
+                NOT_A_DICT_POS,  0 /* flags */, rootGroupPos, NOT_A_DICT_POS /* attributesPos */,
+                NOT_A_CODE_POINT /* nodeCodePoint */, NOT_A_PROBABILITY /* probability */,
+                false /* isTerminal */, true /* hasChildren */, 0 /* depth */,
+                0 /* terminalDepth */);
         // TODO: Move to dicNodeState?
         mDicNodeState.mDicNodeStateOutput.init(); // reset for next word
         mDicNodeState.mDicNodeStateInput.init(
@@ -157,19 +158,18 @@
 
     // TODO: minimize arguments by looking binary_format
     void initAsChild(DicNode *dicNode, const int pos, const uint8_t flags, const int childrenPos,
-            const int attributesPos, const int siblingPos, const int nodeCodePoint,
-            const int childrenCount, const int probability, const int bigramProbability,
-            const bool isTerminal, const bool hasMultipleChars, const bool hasChildren,
-            const uint16_t additionalSubwordLength, const int *additionalSubword) {
+            const int attributesPos, const int probability, const bool isTerminal,
+            const bool hasChildren, const uint16_t mergedNodeCodePointCount,
+            const int *const mergedNodeCodePoints) {
         mIsUsed = true;
         uint16_t newDepth = static_cast<uint16_t>(dicNode->getNodeCodePointCount() + 1);
         mIsCachedForNextSuggestion = dicNode->mIsCachedForNextSuggestion;
         const uint16_t newLeavingDepth = static_cast<uint16_t>(
-                dicNode->mDicNodeProperties.getLeavingDepth() + additionalSubwordLength);
-        mDicNodeProperties.init(pos, flags, childrenPos, attributesPos, siblingPos, nodeCodePoint,
-                childrenCount, probability, bigramProbability, isTerminal, hasMultipleChars,
-                hasChildren, newDepth, newLeavingDepth);
-        mDicNodeState.init(&dicNode->mDicNodeState, additionalSubwordLength, additionalSubword);
+                dicNode->mDicNodeProperties.getLeavingDepth() + mergedNodeCodePointCount);
+        mDicNodeProperties.init(pos, flags, childrenPos, attributesPos, mergedNodeCodePoints[0],
+                probability, isTerminal, hasChildren, newDepth, newLeavingDepth);
+        mDicNodeState.init(&dicNode->mDicNodeState, mergedNodeCodePointCount,
+                mergedNodeCodePoints);
         PROF_NODE_COPY(&dicNode->mProfiler, mProfiler);
     }
 
@@ -193,8 +193,8 @@
     }
 
     bool isLeavingNode() const {
-        ASSERT(getNodeCodePointCount() <= getLeavingDepth());
-        return getNodeCodePointCount() == getLeavingDepth();
+        ASSERT(getNodeCodePointCount() <= mDicNodeProperties.getLeavingDepth());
+        return getNodeCodePointCount() == mDicNodeProperties.getLeavingDepth();
     }
 
     AK_FORCE_INLINE bool isFirstLetter() const {
@@ -256,12 +256,6 @@
         return mDicNodeProperties.getChildrenPos();
     }
 
-    // Used in DicNodeUtils
-    int getChildrenCount() const {
-        return mDicNodeProperties.getChildrenCount();
-    }
-
-    // Used in DicNodeUtils
     int getProbability() const {
         return mDicNodeProperties.getProbability();
     }
@@ -280,10 +274,6 @@
         return !(currentDepth > 0 && (currentDepth != 1 || prevWordLen != 1));
     }
 
-    uint16_t getLeavingDepth() const {
-        return mDicNodeProperties.getLeavingDepth();
-    }
-
     bool isTotalInputSizeExceedingLimit() const {
         const int prevWordsLen = mDicNodeState.mDicNodeStatePrevWord.getPrevWordLength();
         const int currentWordDepth = getNodeCodePointCount();
@@ -370,7 +360,7 @@
     }
 
     AK_FORCE_INLINE const int *getOutputWordBuf() const {
-        return mDicNodeState.mDicNodeStateOutput.mWordBuf;
+        return mDicNodeState.mDicNodeStateOutput.mCodePointsBuf;
     }
 
     int getPrevCodePointG(int pointerId) const {
diff --git a/native/jni/src/suggest/core/dicnode/dic_node_properties.h b/native/jni/src/suggest/core/dicnode/dic_node_properties.h
index d2f87c1..7e8aa49 100644
--- a/native/jni/src/suggest/core/dicnode/dic_node_properties.h
+++ b/native/jni/src/suggest/core/dicnode/dic_node_properties.h
@@ -27,37 +27,31 @@
 /**
  * Node for traversing the lexicon trie.
  */
+// TODO: Introduce a dictionary node class which has attribute members required to understand the
+// dictionary structure.
 class DicNodeProperties {
  public:
     AK_FORCE_INLINE DicNodeProperties()
-            : mPos(0), mFlags(0), mChildrenPos(0), mAttributesPos(0), mSiblingPos(0),
-              mChildrenCount(0), mProbability(0), mBigramProbability(0), mNodeCodePoint(0),
-              mDepth(0), mLeavingDepth(0), mIsTerminal(false), mHasMultipleChars(false),
-              mHasChildren(false) {
-    }
+            : mPos(0), mFlags(0), mChildrenPos(0), mAttributesPos(0), mProbability(0),
+              mNodeCodePoint(0), mDepth(0), mLeavingDepth(0), mIsTerminal(false),
+              mHasChildren(false) {}
 
     virtual ~DicNodeProperties() {}
 
     // Should be called only once per DicNode is initialized.
     void init(const int pos, const uint8_t flags, const int childrenPos, const int attributesPos,
-            const int siblingPos, const int nodeCodePoint, const int childrenCount,
-            const int probability, const int bigramProbability, const bool isTerminal,
-            const bool hasMultipleChars, const bool hasChildren, const uint16_t depth,
-            const uint16_t terminalDepth) {
+            const int nodeCodePoint, const int probability, const bool isTerminal,
+            const bool hasChildren, const uint16_t depth, const uint16_t leavingDepth) {
         mPos = pos;
         mFlags = flags;
         mChildrenPos = childrenPos;
         mAttributesPos = attributesPos;
-        mSiblingPos = siblingPos;
         mNodeCodePoint = nodeCodePoint;
-        mChildrenCount = childrenCount;
         mProbability = probability;
-        mBigramProbability = bigramProbability;
         mIsTerminal = isTerminal;
-        mHasMultipleChars = hasMultipleChars;
         mHasChildren = hasChildren;
         mDepth = depth;
-        mLeavingDepth = terminalDepth;
+        mLeavingDepth = leavingDepth;
     }
 
     // Init for copy
@@ -66,13 +60,9 @@
         mFlags = nodeProp->mFlags;
         mChildrenPos = nodeProp->mChildrenPos;
         mAttributesPos = nodeProp->mAttributesPos;
-        mSiblingPos = nodeProp->mSiblingPos;
         mNodeCodePoint = nodeProp->mNodeCodePoint;
-        mChildrenCount = nodeProp->mChildrenCount;
         mProbability = nodeProp->mProbability;
-        mBigramProbability = nodeProp->mBigramProbability;
         mIsTerminal = nodeProp->mIsTerminal;
-        mHasMultipleChars = nodeProp->mHasMultipleChars;
         mHasChildren = nodeProp->mHasChildren;
         mDepth = nodeProp->mDepth;
         mLeavingDepth = nodeProp->mLeavingDepth;
@@ -84,13 +74,9 @@
         mFlags = nodeProp->mFlags;
         mChildrenPos = nodeProp->mChildrenPos;
         mAttributesPos = nodeProp->mAttributesPos;
-        mSiblingPos = nodeProp->mSiblingPos;
         mNodeCodePoint = codePoint; // Overwrite the node char of a passing child
-        mChildrenCount = nodeProp->mChildrenCount;
         mProbability = nodeProp->mProbability;
-        mBigramProbability = nodeProp->mBigramProbability;
         mIsTerminal = nodeProp->mIsTerminal;
-        mHasMultipleChars = nodeProp->mHasMultipleChars;
         mHasChildren = nodeProp->mHasChildren;
         mDepth = nodeProp->mDepth + 1; // Increment the depth of a passing child
         mLeavingDepth = nodeProp->mLeavingDepth;
@@ -112,10 +98,6 @@
         return mAttributesPos;
     }
 
-    int getChildrenCount() const {
-        return mChildrenCount;
-    }
-
     int getProbability() const {
         return mProbability;
     }
@@ -137,12 +119,8 @@
         return mIsTerminal;
     }
 
-    bool hasMultipleChars() const {
-        return mHasMultipleChars;
-    }
-
     bool hasChildren() const {
-        return mChildrenCount > 0 || mDepth != mLeavingDepth;
+        return mHasChildren || mDepth != mLeavingDepth;
     }
 
     bool hasBlacklistedOrNotAWordFlag() const {
@@ -153,25 +131,15 @@
     // Caution!!!
     // Use a default copy constructor and an assign operator because shallow copies are ok
     // for this class
-
-    // Not used
-    int getSiblingPos() const {
-        return mSiblingPos;
-    }
-
     int mPos;
     uint8_t mFlags;
     int mChildrenPos;
     int mAttributesPos;
-    int mSiblingPos;
-    int mChildrenCount;
     int mProbability;
-    int mBigramProbability; // not used for now
     int mNodeCodePoint;
     uint16_t mDepth;
     uint16_t mLeavingDepth;
     bool mIsTerminal;
-    bool mHasMultipleChars;
     bool mHasChildren;
 };
 } // namespace latinime
diff --git a/native/jni/src/suggest/core/dicnode/dic_node_state.h b/native/jni/src/suggest/core/dicnode/dic_node_state.h
index d35e7d7..b1b6266 100644
--- a/native/jni/src/suggest/core/dicnode/dic_node_state.h
+++ b/native/jni/src/suggest/core/dicnode/dic_node_state.h
@@ -55,11 +55,12 @@
         mDicNodeStateScoring.init(&src->mDicNodeStateScoring);
     }
 
-    // Init by copy and adding subword
-    void init(const DicNodeState *const src, const uint16_t additionalSubwordLength,
-            const int *const additionalSubword) {
+    // Init by copy and adding merged node code points.
+    void init(const DicNodeState *const src, const uint16_t mergedNodeCodePointCount,
+            const int *const mergedNodeCodePoints) {
         init(src);
-        mDicNodeStateOutput.addSubword(additionalSubwordLength, additionalSubword);
+        mDicNodeStateOutput.addMergedNodeCodePoints(
+                mergedNodeCodePointCount, mergedNodeCodePoints);
     }
 
  private:
diff --git a/native/jni/src/suggest/core/dicnode/dic_node_state_output.h b/native/jni/src/suggest/core/dicnode/dic_node_state_output.h
index 1d4f50a..45c7f5c 100644
--- a/native/jni/src/suggest/core/dicnode/dic_node_state_output.h
+++ b/native/jni/src/suggest/core/dicnode/dic_node_state_output.h
@@ -26,50 +26,52 @@
 
 class DicNodeStateOutput {
  public:
-    DicNodeStateOutput() : mOutputtedLength(0) {
+    DicNodeStateOutput() : mOutputtedCodePointCount(0) {
         init();
     }
 
     virtual ~DicNodeStateOutput() {}
 
     void init() {
-        mOutputtedLength = 0;
-        mWordBuf[0] = 0;
+        mOutputtedCodePointCount = 0;
+        mCodePointsBuf[0] = 0;
     }
 
     void init(const DicNodeStateOutput *const stateOutput) {
-        memcpy(mWordBuf, stateOutput->mWordBuf,
-                stateOutput->mOutputtedLength * sizeof(mWordBuf[0]));
-        mOutputtedLength = stateOutput->mOutputtedLength;
-        if (mOutputtedLength < MAX_WORD_LENGTH) {
-            mWordBuf[mOutputtedLength] = 0;
+        memcpy(mCodePointsBuf, stateOutput->mCodePointsBuf,
+                stateOutput->mOutputtedCodePointCount * sizeof(mCodePointsBuf[0]));
+        mOutputtedCodePointCount = stateOutput->mOutputtedCodePointCount;
+        if (mOutputtedCodePointCount < MAX_WORD_LENGTH) {
+            mCodePointsBuf[mOutputtedCodePointCount] = 0;
         }
     }
 
-    void addSubword(const uint16_t additionalSubwordLength, const int *const additionalSubword) {
-        if (additionalSubword) {
-            memcpy(&mWordBuf[mOutputtedLength], additionalSubword,
-                    additionalSubwordLength * sizeof(mWordBuf[0]));
-            mOutputtedLength = static_cast<uint16_t>(mOutputtedLength + additionalSubwordLength);
-            if (mOutputtedLength < MAX_WORD_LENGTH) {
-                mWordBuf[mOutputtedLength] = 0;
+    void addMergedNodeCodePoints(const uint16_t mergedNodeCodePointCount,
+            const int *const mergedNodeCodePoints) {
+        if (mergedNodeCodePoints) {
+            memcpy(&mCodePointsBuf[mOutputtedCodePointCount], mergedNodeCodePoints,
+                    mergedNodeCodePointCount * sizeof(mCodePointsBuf[0]));
+            mOutputtedCodePointCount = static_cast<uint16_t>(
+                    mOutputtedCodePointCount + mergedNodeCodePointCount);
+            if (mOutputtedCodePointCount < MAX_WORD_LENGTH) {
+                mCodePointsBuf[mOutputtedCodePointCount] = 0;
             }
         }
     }
 
     // TODO: Remove
-    int getCodePointAt(const int id) const {
-        return mWordBuf[id];
+    int getCodePointAt(const int index) const {
+        return mCodePointsBuf[index];
     }
 
     // TODO: Move to private
-    int mWordBuf[MAX_WORD_LENGTH];
+    int mCodePointsBuf[MAX_WORD_LENGTH];
 
  private:
     // Caution!!!
     // Use a default copy constructor and an assign operator because shallow copies are ok
     // for this class
-    uint16_t mOutputtedLength;
+    uint16_t mOutputtedCodePointCount;
 };
 } // namespace latinime
 #endif // LATINIME_DIC_NODE_STATE_OUTPUT_H
diff --git a/native/jni/src/suggest/core/dicnode/dic_node_utils.cpp b/native/jni/src/suggest/core/dicnode/dic_node_utils.cpp
index f0f26c7..9bf7ece 100644
--- a/native/jni/src/suggest/core/dicnode/dic_node_utils.cpp
+++ b/native/jni/src/suggest/core/dicnode/dic_node_utils.cpp
@@ -26,6 +26,7 @@
 #include "suggest/core/dictionary/probability_utils.h"
 #include "suggest/core/layout/proximity_info.h"
 #include "suggest/core/layout/proximity_info_state.h"
+#include "suggest/core/policy/dictionary_structure_policy.h"
 #include "utils/char_utils.h"
 
 namespace latinime {
@@ -36,23 +37,15 @@
 
 /* static */ void DicNodeUtils::initAsRoot(const BinaryDictionaryInfo *const binaryDictionaryInfo,
         const int prevWordNodePos, DicNode *const newRootNode) {
-    int curPos = binaryDictionaryInfo->getRootPosition();
-    const int pos = curPos;
-    const int childrenCount = BinaryFormat::getGroupCountAndForwardPointer(
-            binaryDictionaryInfo->getDictRoot(), &curPos);
-    const int childrenPos = curPos;
-    newRootNode->initAsRoot(pos, childrenPos, childrenCount, prevWordNodePos);
+    newRootNode->initAsRoot(binaryDictionaryInfo->getStructurePolicy()->getRootPosition(),
+            prevWordNodePos);
 }
 
 /*static */ void DicNodeUtils::initAsRootWithPreviousWord(
         const BinaryDictionaryInfo *const binaryDictionaryInfo,
         DicNode *const prevWordLastNode, DicNode *const newRootNode) {
-    int curPos = binaryDictionaryInfo->getRootPosition();
-    const int pos = curPos;
-    const int childrenCount = BinaryFormat::getGroupCountAndForwardPointer(
-            binaryDictionaryInfo->getDictRoot(), &curPos);
-    const int childrenPos = curPos;
-    newRootNode->initAsRootWithPreviousWord(prevWordLastNode, pos, childrenPos, childrenCount);
+    newRootNode->initAsRootWithPreviousWord(
+            prevWordLastNode, binaryDictionaryInfo->getStructurePolicy()->getRootPosition());
 }
 
 /* static */ void DicNodeUtils::initByCopy(DicNode *srcNode, DicNode *destNode) {
@@ -76,7 +69,7 @@
 }
 
 /* static */ int DicNodeUtils::createAndGetLeavingChildNode(DicNode *dicNode, int pos,
-        const BinaryDictionaryInfo *const binaryDictionaryInfo, const int terminalDepth,
+        const BinaryDictionaryInfo *const binaryDictionaryInfo,
         const ProximityInfoState *pInfoState, const int pointIndex, const bool exactOnly,
         const std::vector<int> *const codePointsFilter, const ProximityInfo *const pInfo,
         DicNodeVector *childDicNodes) {
@@ -86,15 +79,15 @@
     const bool hasMultipleChars = (0 != (BinaryFormat::FLAG_HAS_MULTIPLE_CHARS & flags));
     const bool isTerminal = (0 != (BinaryFormat::FLAG_IS_TERMINAL & flags));
     const bool hasChildren = BinaryFormat::hasChildrenInFlags(flags);
+    const bool hasShortcuts = (0 != (BinaryFormat::FLAG_HAS_SHORTCUT_TARGETS & flags));
 
     int codePoint = BinaryFormat::getCodePointAndForwardPointer(
             binaryDictionaryInfo->getDictRoot(), &pos);
     ASSERT(NOT_A_CODE_POINT != codePoint);
-    const int nodeCodePoint = codePoint;
     // TODO: optimize this
-    int additionalWordBuf[MAX_WORD_LENGTH];
-    uint16_t additionalSubwordLength = 0;
-    additionalWordBuf[additionalSubwordLength++] = codePoint;
+    int mergedNodeCodePoints[MAX_WORD_LENGTH];
+    uint16_t mergedNodeCodePointCount = 0;
+    mergedNodeCodePoints[mergedNodeCodePointCount++] = codePoint;
 
     do {
         const int nextCodePoint = hasMultipleChars
@@ -102,31 +95,29 @@
                         binaryDictionaryInfo->getDictRoot(), &pos) : NOT_A_CODE_POINT;
         const bool isLastChar = (NOT_A_CODE_POINT == nextCodePoint);
         if (!isLastChar) {
-            additionalWordBuf[additionalSubwordLength++] = nextCodePoint;
+            mergedNodeCodePoints[mergedNodeCodePointCount++] = nextCodePoint;
         }
         codePoint = nextCodePoint;
     } while (NOT_A_CODE_POINT != codePoint);
 
     const int probability = isTerminal ? BinaryFormat::readProbabilityWithoutMovingPointer(
-            binaryDictionaryInfo->getDictRoot(), pos) : -1;
+            binaryDictionaryInfo->getDictRoot(), pos) : NOT_A_PROBABILITY;
     pos = BinaryFormat::skipProbability(flags, pos);
     int childrenPos = hasChildren ? BinaryFormat::readChildrenPosition(
-            binaryDictionaryInfo->getDictRoot(), flags, pos) : 0;
-    const int attributesPos = BinaryFormat::skipChildrenPosition(flags, pos);
+            binaryDictionaryInfo->getDictRoot(), flags, pos) : NOT_A_DICT_POS;
+    const int attributesPos =
+            hasShortcuts ? BinaryFormat::skipChildrenPosition(flags, pos) : NOT_A_DICT_POS;
     const int siblingPos = BinaryFormat::skipChildrenPosAndAttributes(
             binaryDictionaryInfo->getDictRoot(), flags, pos);
 
-    if (isDicNodeFilteredOut(nodeCodePoint, pInfo, codePointsFilter)) {
+    if (isDicNodeFilteredOut(mergedNodeCodePoints[0], pInfo, codePointsFilter)) {
         return siblingPos;
     }
-    if (!isMatchedNodeCodePoint(pInfoState, pointIndex, exactOnly, nodeCodePoint)) {
+    if (!isMatchedNodeCodePoint(pInfoState, pointIndex, exactOnly, mergedNodeCodePoints[0])) {
         return siblingPos;
     }
-    const int childrenCount = hasChildren ? BinaryFormat::getGroupCountAndForwardPointer(
-            binaryDictionaryInfo->getDictRoot(), &childrenPos) : 0;
-    childDicNodes->pushLeavingChild(dicNode, nextPos, flags, childrenPos, attributesPos, siblingPos,
-            nodeCodePoint, childrenCount, probability, -1 /* bigramProbability */, isTerminal,
-            hasMultipleChars, hasChildren, additionalSubwordLength, additionalWordBuf);
+    childDicNodes->pushLeavingChild(dicNode, nextPos, flags, childrenPos, attributesPos,
+            probability, isTerminal, hasChildren, mergedNodeCodePointCount, mergedNodeCodePoints);
     return siblingPos;
 }
 
@@ -163,13 +154,16 @@
         const ProximityInfoState *pInfoState, const int pointIndex, const bool exactOnly,
         const std::vector<int> *const codePointsFilter, const ProximityInfo *const pInfo,
         DicNodeVector *childDicNodes) {
-    const int terminalDepth = dicNode->getLeavingDepth();
-    const int childCount = dicNode->getChildrenCount();
+    if (!dicNode->hasChildren()) {
+        return;
+    }
     int nextPos = dicNode->getChildrenPos();
+    const int childCount = BinaryFormat::getGroupCountAndForwardPointer(
+            binaryDictionaryInfo->getDictRoot(), &nextPos);
     for (int i = 0; i < childCount; i++) {
         const int filterSize = codePointsFilter ? codePointsFilter->size() : 0;
         nextPos = createAndGetLeavingChildNode(dicNode, nextPos, binaryDictionaryInfo,
-                terminalDepth, pInfoState, pointIndex, exactOnly, codePointsFilter, pInfo,
+                pInfoState, pointIndex, exactOnly, codePointsFilter, pInfo,
                 childDicNodes);
         if (!pInfo && filterSize > 0 && childDicNodes->exceeds(filterSize)) {
             // All code points have been found.
diff --git a/native/jni/src/suggest/core/dicnode/dic_node_utils.h b/native/jni/src/suggest/core/dicnode/dic_node_utils.h
index e198d61..d526975 100644
--- a/native/jni/src/suggest/core/dicnode/dic_node_utils.h
+++ b/native/jni/src/suggest/core/dicnode/dic_node_utils.h
@@ -72,7 +72,7 @@
             const std::vector<int> *const codePointsFilter,
             const ProximityInfo *const pInfo, DicNodeVector *childDicNodes);
     static int createAndGetLeavingChildNode(DicNode *dicNode, int pos,
-            const BinaryDictionaryInfo *const binaryDictionaryInfo, const int terminalDepth,
+            const BinaryDictionaryInfo *const binaryDictionaryInfo,
             const ProximityInfoState *pInfoState, const int pointIndex,
             const bool exactOnly, const std::vector<int> *const codePointsFilter,
             const ProximityInfo *const pInfo, DicNodeVector *childDicNodes);
diff --git a/native/jni/src/suggest/core/dicnode/dic_node_vector.h b/native/jni/src/suggest/core/dicnode/dic_node_vector.h
index e23c411..9641cc1 100644
--- a/native/jni/src/suggest/core/dicnode/dic_node_vector.h
+++ b/native/jni/src/suggest/core/dicnode/dic_node_vector.h
@@ -63,16 +63,13 @@
     }
 
     void pushLeavingChild(DicNode *dicNode, const int pos, const uint8_t flags,
-            const int childrenPos, const int attributesPos, const int siblingPos,
-            const int nodeCodePoint, const int childrenCount, const int probability,
-            const int bigramProbability, const bool isTerminal, const bool hasMultipleChars,
-            const bool hasChildren, const uint16_t additionalSubwordLength,
-            const int *additionalSubword) {
+            const int childrenPos, const int attributesPos, const int probability,
+            const bool isTerminal, const bool hasChildren, const uint16_t mergedNodeCodePointCount,
+            const int *const mergedNodeCodePoints) {
         ASSERT(!mLock);
         mDicNodes.push_back(mEmptyNode);
-        mDicNodes.back().initAsChild(dicNode, pos, flags, childrenPos, attributesPos, siblingPos,
-                nodeCodePoint, childrenCount, probability, -1 /* bigramProbability */, isTerminal,
-                hasMultipleChars, hasChildren, additionalSubwordLength, additionalSubword);
+        mDicNodes.back().initAsChild(dicNode, pos, flags, childrenPos, attributesPos, probability,
+                isTerminal, hasChildren, mergedNodeCodePointCount, mergedNodeCodePoints);
     }
 
     DicNode *operator[](const int id) {
diff --git a/native/jni/src/suggest/core/dictionary/bigram_dictionary.cpp b/native/jni/src/suggest/core/dictionary/bigram_dictionary.cpp
index 242a9bd..ff304d2 100644
--- a/native/jni/src/suggest/core/dictionary/bigram_dictionary.cpp
+++ b/native/jni/src/suggest/core/dictionary/bigram_dictionary.cpp
@@ -150,11 +150,10 @@
 int BigramDictionary::getBigramListPositionForWord(const int *prevWord, const int prevWordLength,
         const bool forceLowerCaseSearch) const {
     if (0 >= prevWordLength) return 0;
-    const uint8_t *const root = mBinaryDictionaryInfo->getDictRoot();
-    int pos = BinaryFormat::getTerminalPosition(root, prevWord, prevWordLength,
-            forceLowerCaseSearch);
-
+    int pos = mBinaryDictionaryInfo->getStructurePolicy()->getTerminalNodePositionOfWord(
+            mBinaryDictionaryInfo, prevWord, prevWordLength, forceLowerCaseSearch);
     if (NOT_VALID_WORD == pos) return 0;
+    const uint8_t *const root = mBinaryDictionaryInfo->getDictRoot();
     const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos);
     if (0 == (flags & BinaryFormat::FLAG_HAS_BIGRAMS)) return 0;
     if (0 == (flags & BinaryFormat::FLAG_HAS_MULTIPLE_CHARS)) {
@@ -189,8 +188,8 @@
     int pos = getBigramListPositionForWord(word0, length0, false /* forceLowerCaseSearch */);
     // getBigramListPositionForWord returns 0 if this word isn't in the dictionary or has no bigrams
     if (0 == pos) return false;
-    int nextWordPos = BinaryFormat::getTerminalPosition(mBinaryDictionaryInfo->getDictRoot(),
-            word1, length1, false /* forceLowerCaseSearch */);
+    int nextWordPos = mBinaryDictionaryInfo->getStructurePolicy()->getTerminalNodePositionOfWord(
+            mBinaryDictionaryInfo, word1, length1, false /* forceLowerCaseSearch */);
     if (NOT_VALID_WORD == nextWordPos) return false;
 
     for (BinaryDictionaryBigramsIterator bigramsIt(mBinaryDictionaryInfo, pos);
diff --git a/native/jni/src/suggest/core/dictionary/binary_dictionary_format_utils.cpp b/native/jni/src/suggest/core/dictionary/binary_dictionary_format_utils.cpp
index 737df63..bbb4ca3 100644
--- a/native/jni/src/suggest/core/dictionary/binary_dictionary_format_utils.cpp
+++ b/native/jni/src/suggest/core/dictionary/binary_dictionary_format_utils.cpp
@@ -22,7 +22,7 @@
  * Dictionary size
  */
 // Any file smaller than this is not a dictionary.
-const int BinaryDictionaryFormat::DICTIONARY_MINIMUM_SIZE = 4;
+const int BinaryDictionaryFormatUtils::DICTIONARY_MINIMUM_SIZE = 4;
 
 /**
  * Format versions
@@ -30,17 +30,18 @@
 // Originally, format version 1 had a 16-bit magic number, then the version number `01'
 // then options that must be 0. Hence the first 32-bits of the format are always as follow
 // and it's okay to consider them a magic number as a whole.
-const uint32_t BinaryDictionaryFormat::FORMAT_VERSION_1_MAGIC_NUMBER = 0x78B10100;
+const uint32_t BinaryDictionaryFormatUtils::FORMAT_VERSION_1_MAGIC_NUMBER = 0x78B10100;
 
 // The versions of Latin IME that only handle format version 1 only test for the magic
 // number, so we had to change it so that version 2 files would be rejected by older
 // implementations. On this occasion, we made the magic number 32 bits long.
-const uint32_t BinaryDictionaryFormat::FORMAT_VERSION_2_MAGIC_NUMBER = 0x9BC13AFE;
+const uint32_t BinaryDictionaryFormatUtils::FORMAT_VERSION_2_MAGIC_NUMBER = 0x9BC13AFE;
 // Magic number (4 bytes), version (2 bytes), options (2 bytes), header size (4 bytes) = 12
-const int BinaryDictionaryFormat::FORMAT_VERSION_2_MINIMUM_SIZE = 12;
+const int BinaryDictionaryFormatUtils::FORMAT_VERSION_2_MINIMUM_SIZE = 12;
 
-/* static */ BinaryDictionaryFormat::FORMAT_VERSION BinaryDictionaryFormat::detectFormatVersion(
-        const uint8_t *const dict, const int dictSize) {
+/* static */ BinaryDictionaryFormatUtils::FORMAT_VERSION
+        BinaryDictionaryFormatUtils::detectFormatVersion(const uint8_t *const dict,
+                const int dictSize) {
     // The magic number is stored big-endian.
     // If the dictionary is less than 4 bytes, we can't even read the magic number, so we don't
     // understand this format.
diff --git a/native/jni/src/suggest/core/dictionary/binary_dictionary_format_utils.h b/native/jni/src/suggest/core/dictionary/binary_dictionary_format_utils.h
index c0fd561..33618b9 100644
--- a/native/jni/src/suggest/core/dictionary/binary_dictionary_format_utils.h
+++ b/native/jni/src/suggest/core/dictionary/binary_dictionary_format_utils.h
@@ -31,7 +31,7 @@
  * reading methods and utility methods for various purposes.
  * On the other hand, this file deals with only about dictionary format version.
  */
-class BinaryDictionaryFormat {
+class BinaryDictionaryFormatUtils {
  public:
     // TODO: Remove obsolete version logic
     enum FORMAT_VERSION {
@@ -43,7 +43,7 @@
     static FORMAT_VERSION detectFormatVersion(const uint8_t *const dict, const int dictSize);
 
  private:
-    DISALLOW_IMPLICIT_CONSTRUCTORS(BinaryDictionaryFormat);
+    DISALLOW_IMPLICIT_CONSTRUCTORS(BinaryDictionaryFormatUtils);
 
     static const int DICTIONARY_MINIMUM_SIZE;
     static const uint32_t FORMAT_VERSION_1_MAGIC_NUMBER;
diff --git a/native/jni/src/suggest/core/dictionary/binary_dictionary_header.cpp b/native/jni/src/suggest/core/dictionary/binary_dictionary_header.cpp
index 04bb81f..91c643a 100644
--- a/native/jni/src/suggest/core/dictionary/binary_dictionary_header.cpp
+++ b/native/jni/src/suggest/core/dictionary/binary_dictionary_header.cpp
@@ -29,12 +29,12 @@
 BinaryDictionaryHeader::BinaryDictionaryHeader(
         const BinaryDictionaryInfo *const binaryDictionaryInfo)
         : mBinaryDictionaryInfo(binaryDictionaryInfo),
-          mDictionaryFlags(BinaryDictionaryHeaderReader::getFlags(binaryDictionaryInfo)),
-          mSize(BinaryDictionaryHeaderReader::getHeaderSize(binaryDictionaryInfo)),
+          mDictionaryFlags(BinaryDictionaryHeaderReadingUtils::getFlags(binaryDictionaryInfo)),
+          mSize(BinaryDictionaryHeaderReadingUtils::getHeaderSize(binaryDictionaryInfo)),
           mMultiWordCostMultiplier(readMultiWordCostMultiplier()) {}
 
 float BinaryDictionaryHeader::readMultiWordCostMultiplier() const {
-    const int headerValue = BinaryDictionaryHeaderReader::readHeaderValueInt(
+    const int headerValue = BinaryDictionaryHeaderReadingUtils::readHeaderValueInt(
             mBinaryDictionaryInfo, MULTIPLE_WORDS_DEMOTION_RATE_KEY);
     if (headerValue == S_INT_MIN) {
         // not found
diff --git a/native/jni/src/suggest/core/dictionary/binary_dictionary_header.h b/native/jni/src/suggest/core/dictionary/binary_dictionary_header.h
index 9db0003..6dba0b2 100644
--- a/native/jni/src/suggest/core/dictionary/binary_dictionary_header.h
+++ b/native/jni/src/suggest/core/dictionary/binary_dictionary_header.h
@@ -37,15 +37,16 @@
     }
 
     AK_FORCE_INLINE bool supportsDynamicUpdate() const {
-        return BinaryDictionaryHeaderReader::supportsDynamicUpdate(mDictionaryFlags);
+        return BinaryDictionaryHeaderReadingUtils::supportsDynamicUpdate(mDictionaryFlags);
     }
 
     AK_FORCE_INLINE bool requiresGermanUmlautProcessing() const {
-        return BinaryDictionaryHeaderReader::requiresGermanUmlautProcessing(mDictionaryFlags);
+        return BinaryDictionaryHeaderReadingUtils::requiresGermanUmlautProcessing(mDictionaryFlags);
     }
 
     AK_FORCE_INLINE bool requiresFrenchLigatureProcessing() const {
-        return BinaryDictionaryHeaderReader::requiresFrenchLigatureProcessing(mDictionaryFlags);
+        return BinaryDictionaryHeaderReadingUtils::requiresFrenchLigatureProcessing(
+                mDictionaryFlags);
     }
 
     AK_FORCE_INLINE float getMultiWordCostMultiplier() const {
@@ -60,7 +61,7 @@
     static const float MULTI_WORD_COST_MULTIPLIER_SCALE;
 
     const BinaryDictionaryInfo *const mBinaryDictionaryInfo;
-    const BinaryDictionaryHeaderReader::DictionaryFlags mDictionaryFlags;
+    const BinaryDictionaryHeaderReadingUtils::DictionaryFlags mDictionaryFlags;
     const int mSize;
     const float mMultiWordCostMultiplier;
 
diff --git a/native/jni/src/suggest/core/dictionary/binary_dictionary_header_reading_utils.cpp b/native/jni/src/suggest/core/dictionary/binary_dictionary_header_reading_utils.cpp
index c09a78f..2c95931 100644
--- a/native/jni/src/suggest/core/dictionary/binary_dictionary_header_reading_utils.cpp
+++ b/native/jni/src/suggest/core/dictionary/binary_dictionary_header_reading_utils.cpp
@@ -24,32 +24,33 @@
 
 namespace latinime {
 
-const int BinaryDictionaryHeaderReader::MAX_OPTION_KEY_LENGTH = 256;
+const int BinaryDictionaryHeaderReadingUtils::MAX_OPTION_KEY_LENGTH = 256;
 
-const int BinaryDictionaryHeaderReader::FORMAT_VERSION_1_HEADER_SIZE = 5;
+const int BinaryDictionaryHeaderReadingUtils::FORMAT_VERSION_1_HEADER_SIZE = 5;
 
-const int BinaryDictionaryHeaderReader::VERSION_2_MAGIC_NUMBER_SIZE = 4;
-const int BinaryDictionaryHeaderReader::VERSION_2_DICTIONARY_VERSION_SIZE = 2;
-const int BinaryDictionaryHeaderReader::VERSION_2_DICTIONARY_FLAG_SIZE = 2;
-const int BinaryDictionaryHeaderReader::VERSION_2_DICTIONARY_HEADER_SIZE_SIZE = 4;
+const int BinaryDictionaryHeaderReadingUtils::VERSION_2_MAGIC_NUMBER_SIZE = 4;
+const int BinaryDictionaryHeaderReadingUtils::VERSION_2_DICTIONARY_VERSION_SIZE = 2;
+const int BinaryDictionaryHeaderReadingUtils::VERSION_2_DICTIONARY_FLAG_SIZE = 2;
+const int BinaryDictionaryHeaderReadingUtils::VERSION_2_DICTIONARY_HEADER_SIZE_SIZE = 4;
 
-const BinaryDictionaryHeaderReader::DictionaryFlags BinaryDictionaryHeaderReader::NO_FLAGS = 0;
+const BinaryDictionaryHeaderReadingUtils::DictionaryFlags
+        BinaryDictionaryHeaderReadingUtils::NO_FLAGS = 0;
 // Flags for special processing
 // Those *must* match the flags in makedict (BinaryDictInputOutput#*_PROCESSING_FLAG) or
 // something very bad (like, the apocalypse) will happen. Please update both at the same time.
-const BinaryDictionaryHeaderReader::DictionaryFlags
-        BinaryDictionaryHeaderReader::GERMAN_UMLAUT_PROCESSING_FLAG = 0x1;
-const BinaryDictionaryHeaderReader::DictionaryFlags
-        BinaryDictionaryHeaderReader::SUPPORTS_DYNAMIC_UPDATE_FLAG = 0x2;
-const BinaryDictionaryHeaderReader::DictionaryFlags
-        BinaryDictionaryHeaderReader::FRENCH_LIGATURE_PROCESSING_FLAG = 0x4;
+const BinaryDictionaryHeaderReadingUtils::DictionaryFlags
+        BinaryDictionaryHeaderReadingUtils::GERMAN_UMLAUT_PROCESSING_FLAG = 0x1;
+const BinaryDictionaryHeaderReadingUtils::DictionaryFlags
+        BinaryDictionaryHeaderReadingUtils::SUPPORTS_DYNAMIC_UPDATE_FLAG = 0x2;
+const BinaryDictionaryHeaderReadingUtils::DictionaryFlags
+        BinaryDictionaryHeaderReadingUtils::FRENCH_LIGATURE_PROCESSING_FLAG = 0x4;
 
-/* static */ int BinaryDictionaryHeaderReader::getHeaderSize(
+/* static */ int BinaryDictionaryHeaderReadingUtils::getHeaderSize(
         const BinaryDictionaryInfo *const binaryDictionaryInfo) {
     switch (binaryDictionaryInfo->getFormat()) {
-        case BinaryDictionaryFormat::VERSION_1:
+        case BinaryDictionaryFormatUtils::VERSION_1:
             return FORMAT_VERSION_1_HEADER_SIZE;
-        case BinaryDictionaryFormat::VERSION_2:
+        case BinaryDictionaryFormatUtils::VERSION_2:
             // See the format of the header in the comment in
             // BinaryDictionaryFormatUtils::detectFormatVersion()
             return ByteArrayUtils::readUint32(binaryDictionaryInfo->getDictBuf(),
@@ -60,12 +61,13 @@
     }
 }
 
-/* static */ BinaryDictionaryHeaderReader::DictionaryFlags BinaryDictionaryHeaderReader::getFlags(
-        const BinaryDictionaryInfo *const binaryDictionaryInfo) {
+/* static */ BinaryDictionaryHeaderReadingUtils::DictionaryFlags
+        BinaryDictionaryHeaderReadingUtils::getFlags(
+                const BinaryDictionaryInfo *const binaryDictionaryInfo) {
     switch (binaryDictionaryInfo->getFormat()) {
-        case BinaryDictionaryFormat::VERSION_1:
+        case BinaryDictionaryFormatUtils::VERSION_1:
             return NO_FLAGS;
-        case BinaryDictionaryFormat::VERSION_2:
+        case BinaryDictionaryFormatUtils::VERSION_2:
             return ByteArrayUtils::readUint16(binaryDictionaryInfo->getDictBuf(),
                     VERSION_2_MAGIC_NUMBER_SIZE + VERSION_2_DICTIONARY_VERSION_SIZE);
         default:
@@ -74,7 +76,7 @@
 }
 
 // Returns if the key is found or not and reads the found value into outValue.
-/* static */ bool BinaryDictionaryHeaderReader::readHeaderValue(
+/* static */ bool BinaryDictionaryHeaderReadingUtils::readHeaderValue(
         const BinaryDictionaryInfo *const binaryDictionaryInfo,
         const char *const key, int *outValue, const int outValueSize) {
     if (outValueSize <= 0 || !hasHeaderAttributes(binaryDictionaryInfo->getFormat())) {
@@ -97,7 +99,7 @@
     return false;
 }
 
-/* static */ int BinaryDictionaryHeaderReader::readHeaderValueInt(
+/* static */ int BinaryDictionaryHeaderReadingUtils::readHeaderValueInt(
         const BinaryDictionaryInfo *const binaryDictionaryInfo, const char *const key) {
     const int bufferSize = LARGEST_INT_DIGIT_COUNT;
     int intBuffer[bufferSize];
diff --git a/native/jni/src/suggest/core/dictionary/binary_dictionary_header_reading_utils.h b/native/jni/src/suggest/core/dictionary/binary_dictionary_header_reading_utils.h
index 6e9dca7..49ed2b9 100644
--- a/native/jni/src/suggest/core/dictionary/binary_dictionary_header_reading_utils.h
+++ b/native/jni/src/suggest/core/dictionary/binary_dictionary_header_reading_utils.h
@@ -26,7 +26,7 @@
 
 class BinaryDictionaryInfo;
 
-class BinaryDictionaryHeaderReader {
+class BinaryDictionaryHeaderReadingUtils {
  public:
     typedef uint16_t DictionaryFlags;
 
@@ -49,10 +49,10 @@
     }
 
     static AK_FORCE_INLINE bool hasHeaderAttributes(
-            const BinaryDictionaryFormat::FORMAT_VERSION format) {
+            const BinaryDictionaryFormatUtils::FORMAT_VERSION format) {
         // Only format 2 and above have header attributes as {key,value} string pairs.
         switch (format) {
-        case BinaryDictionaryFormat::VERSION_2:
+        case BinaryDictionaryFormatUtils::VERSION_2:
             return  true;
             break;
         default:
@@ -61,9 +61,9 @@
     }
 
     static AK_FORCE_INLINE int getHeaderOptionsPosition(
-            const BinaryDictionaryFormat::FORMAT_VERSION format) {
+            const BinaryDictionaryFormatUtils::FORMAT_VERSION format) {
         switch (format) {
-        case BinaryDictionaryFormat::VERSION_2:
+        case BinaryDictionaryFormatUtils::VERSION_2:
             return VERSION_2_MAGIC_NUMBER_SIZE + VERSION_2_DICTIONARY_VERSION_SIZE
                     + VERSION_2_DICTIONARY_FLAG_SIZE + VERSION_2_DICTIONARY_HEADER_SIZE_SIZE;
             break;
@@ -80,7 +80,7 @@
             const BinaryDictionaryInfo *const binaryDictionaryInfo, const char *const key);
 
  private:
-    DISALLOW_IMPLICIT_CONSTRUCTORS(BinaryDictionaryHeaderReader);
+    DISALLOW_IMPLICIT_CONSTRUCTORS(BinaryDictionaryHeaderReadingUtils);
 
     static const int FORMAT_VERSION_1_HEADER_SIZE;
 
diff --git a/native/jni/src/suggest/core/dictionary/binary_dictionary_info.h b/native/jni/src/suggest/core/dictionary/binary_dictionary_info.h
index e0b5835..7cb3144 100644
--- a/native/jni/src/suggest/core/dictionary/binary_dictionary_info.h
+++ b/native/jni/src/suggest/core/dictionary/binary_dictionary_info.h
@@ -22,19 +22,21 @@
 #include "defines.h"
 #include "suggest/core/dictionary/binary_dictionary_format_utils.h"
 #include "suggest/core/dictionary/binary_dictionary_header.h"
+#include "suggest/policyimpl/dictionary/dictionary_structure_policy_factory.h"
 
 namespace latinime {
 
-class BinaryDictionaryHeader;
-
 class BinaryDictionaryInfo {
  public:
     BinaryDictionaryInfo(const uint8_t *const dictBuf, const int dictSize, const int mmapFd,
             const int dictBufOffset, const bool isUpdatable)
             : mDictBuf(dictBuf), mDictSize(dictSize), mMmapFd(mmapFd),
               mDictBufOffset(dictBufOffset), mIsUpdatable(isUpdatable),
-              mDictionaryFormat(BinaryDictionaryFormat::detectFormatVersion(mDictBuf, mDictSize)),
-              mDictionaryHeader(this), mDictRoot(mDictBuf + mDictionaryHeader.getSize()) {}
+              mDictionaryFormat(BinaryDictionaryFormatUtils::detectFormatVersion(
+                      mDictBuf, mDictSize)),
+              mDictionaryHeader(this), mDictRoot(mDictBuf + mDictionaryHeader.getSize()),
+              mStructurePolicy(DictionaryStructurePolicyFactory::getDictionaryStructurePolicy(
+                      mDictionaryFormat)) {}
 
     AK_FORCE_INLINE const uint8_t *getDictBuf() const {
         return mDictBuf;
@@ -56,14 +58,10 @@
         return mDictRoot;
     }
 
-    AK_FORCE_INLINE BinaryDictionaryFormat::FORMAT_VERSION getFormat() const {
+    AK_FORCE_INLINE BinaryDictionaryFormatUtils::FORMAT_VERSION getFormat() const {
         return mDictionaryFormat;
     }
 
-    AK_FORCE_INLINE int getRootPosition() const {
-        return 0;
-    }
-
     AK_FORCE_INLINE const BinaryDictionaryHeader *getHeader() const {
         return &mDictionaryHeader;
     }
@@ -74,6 +72,10 @@
         return mIsUpdatable && isUpdatableDictionaryFormat;
     }
 
+    AK_FORCE_INLINE const DictionaryStructurePolicy *getStructurePolicy() const {
+        return mStructurePolicy;
+    }
+
  private:
     DISALLOW_COPY_AND_ASSIGN(BinaryDictionaryInfo);
 
@@ -82,9 +84,10 @@
     const int mMmapFd;
     const int mDictBufOffset;
     const bool mIsUpdatable;
-    const BinaryDictionaryFormat::FORMAT_VERSION mDictionaryFormat;
+    const BinaryDictionaryFormatUtils::FORMAT_VERSION mDictionaryFormat;
     const BinaryDictionaryHeader mDictionaryHeader;
     const uint8_t *const mDictRoot;
+    const DictionaryStructurePolicy *const mStructurePolicy;
 };
 }
 #endif /* LATINIME_BINARY_DICTIONARY_INFO_H */
diff --git a/native/jni/src/suggest/core/dictionary/dictionary.cpp b/native/jni/src/suggest/core/dictionary/dictionary.cpp
index 51f23dc..675b549 100644
--- a/native/jni/src/suggest/core/dictionary/dictionary.cpp
+++ b/native/jni/src/suggest/core/dictionary/dictionary.cpp
@@ -83,27 +83,14 @@
 }
 
 int Dictionary::getProbability(const int *word, int length) const {
-    const uint8_t *const root = mBinaryDictionaryInfo.getDictRoot();
-    int pos = BinaryFormat::getTerminalPosition(root, word, length,
+    const DictionaryStructurePolicy *const structurePolicy =
+            mBinaryDictionaryInfo.getStructurePolicy();
+    int pos = structurePolicy->getTerminalNodePositionOfWord(&mBinaryDictionaryInfo, word, length,
             false /* forceLowerCaseSearch */);
     if (NOT_VALID_WORD == pos) {
         return NOT_A_PROBABILITY;
     }
-    const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos);
-    if (flags & (BinaryFormat::FLAG_IS_BLACKLISTED | BinaryFormat::FLAG_IS_NOT_A_WORD)) {
-        // If this is not a word, or if it's a blacklisted entry, it should behave as
-        // having no probability outside of the suggestion process (where it should be used
-        // for shortcuts).
-        return NOT_A_PROBABILITY;
-    }
-    const bool hasMultipleChars = (0 != (BinaryFormat::FLAG_HAS_MULTIPLE_CHARS & flags));
-    if (hasMultipleChars) {
-        pos = BinaryFormat::skipOtherCharacters(root, pos);
-    } else {
-        BinaryFormat::getCodePointAndForwardPointer(root, &pos);
-    }
-    const int unigramProbability = BinaryFormat::readProbabilityWithoutMovingPointer(root, pos);
-    return unigramProbability;
+    return structurePolicy->getUnigramProbability(&mBinaryDictionaryInfo, pos);
 }
 
 bool Dictionary::isValidBigram(const int *word0, int length0, const int *word1, int length1) const {
diff --git a/native/jni/src/suggest/core/policy/dictionary_structure_policy.h b/native/jni/src/suggest/core/policy/dictionary_structure_policy.h
new file mode 100644
index 0000000..ab42c13
--- /dev/null
+++ b/native/jni/src/suggest/core/policy/dictionary_structure_policy.h
@@ -0,0 +1,72 @@
+/*
+ * Copyright (C) 2013, The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef LATINIME_DICTIONARY_STRUCTURE_POLICY_H
+#define LATINIME_DICTIONARY_STRUCTURE_POLICY_H
+
+#include "defines.h"
+
+namespace latinime {
+
+class BinaryDictionaryInfo;
+class DicNode;
+class DicNodeVector;
+
+/*
+ * This class abstracts structure of dictionaries.
+ * Implement this policy to support additional dictionaries.
+ */
+class DictionaryStructurePolicy {
+ public:
+    // This provides a filtering method for filtering new node.
+    class NodeFilter {
+     public:
+        virtual bool isFilteredOut(const int codePoint) const = 0;
+
+     protected:
+        NodeFilter() {}
+        virtual ~NodeFilter() {}
+
+     private:
+        DISALLOW_COPY_AND_ASSIGN(NodeFilter);
+    };
+
+    virtual int getRootPosition() const = 0;
+
+    virtual void createAndGetAllChildNodes(const DicNode *const dicNode,
+            const BinaryDictionaryInfo *const binaryDictionaryInfo,
+            const NodeFilter *const nodeFilter, DicNodeVector *const childDicNodes) const = 0;
+
+    virtual void getWordAtPosition(const BinaryDictionaryInfo *const binaryDictionaryInfo,
+            const int terminalNodePos, const int maxDepth, int *const outWord,
+            int *const outUnigramProbability) const = 0;
+
+    virtual int getTerminalNodePositionOfWord(
+            const BinaryDictionaryInfo *const binaryDictionaryInfo, const int *const inWord,
+            const int length, const bool forceLowerCaseSearch) const = 0;
+
+    virtual int getUnigramProbability(const BinaryDictionaryInfo *const binaryDictionaryInfo,
+            const int nodePos) const = 0;
+
+ protected:
+    DictionaryStructurePolicy() {}
+    virtual ~DictionaryStructurePolicy() {}
+
+ private:
+    DISALLOW_COPY_AND_ASSIGN(DictionaryStructurePolicy);
+};
+} // namespace latinime
+#endif /* LATINIME_DICTIONARY_STRUCTURE_POLICY_H */
diff --git a/native/jni/src/suggest/policyimpl/dictionary/dictionary_structure_policy_factory.h b/native/jni/src/suggest/policyimpl/dictionary/dictionary_structure_policy_factory.h
new file mode 100644
index 0000000..5070651
--- /dev/null
+++ b/native/jni/src/suggest/policyimpl/dictionary/dictionary_structure_policy_factory.h
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef LATINIME_DICTIONARY_STRUCTURE_POLICY_FACTORY_H
+#define LATINIME_DICTIONARY_STRUCTURE_POLICY_FACTORY_H
+
+#include "defines.h"
+#include "suggest/core/dictionary/binary_dictionary_format_utils.h"
+#include "suggest/policyimpl/dictionary/patricia_trie_policy.h"
+
+namespace latinime {
+
+class DictionaryStructurePolicy;
+
+class DictionaryStructurePolicyFactory {
+ public:
+    static const DictionaryStructurePolicy *getDictionaryStructurePolicy(
+            const BinaryDictionaryFormatUtils::FORMAT_VERSION dictionaryFormat) {
+        switch (dictionaryFormat) {
+            case BinaryDictionaryFormatUtils::VERSION_1:
+                // Fall through
+            case BinaryDictionaryFormatUtils::VERSION_2:
+                return PatriciaTriePolicy::getInstance();
+            default:
+                ASSERT(false);
+                return 0;
+        }
+    }
+
+ private:
+    DISALLOW_IMPLICIT_CONSTRUCTORS(DictionaryStructurePolicyFactory);
+};
+} // namespace latinime
+#endif // LATINIME_DICTIONARY_STRUCTURE_POLICY_FACTORY_H
diff --git a/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.cpp b/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.cpp
new file mode 100644
index 0000000..c995af9
--- /dev/null
+++ b/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.cpp
@@ -0,0 +1,70 @@
+/*
+ * Copyright (C) 2013, The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+#include "suggest/policyimpl/dictionary/patricia_trie_policy.h"
+
+#include "defines.h"
+#include "suggest/core/dicnode/dic_node.h"
+#include "suggest/core/dicnode/dic_node_vector.h"
+#include "suggest/core/dictionary/binary_dictionary_info.h"
+#include "suggest/core/dictionary/binary_format.h"
+
+namespace latinime {
+
+const PatriciaTriePolicy PatriciaTriePolicy::sInstance;
+
+void PatriciaTriePolicy::createAndGetAllChildNodes(const DicNode *const dicNode,
+        const BinaryDictionaryInfo *const binaryDictionaryInfo,
+        const NodeFilter *const nodeFilter, DicNodeVector *const childDicNodes) const {
+    // TODO: Move children creating methods form DicNodeUtils.
+}
+
+void PatriciaTriePolicy::getWordAtPosition(const BinaryDictionaryInfo *const binaryDictionaryInfo,
+        const int terminalNodePos, const int maxDepth, int *const outWord,
+        int *const outUnigramProbability) const {
+    BinaryFormat::getWordAtAddress(binaryDictionaryInfo->getDictRoot(), terminalNodePos,
+            maxDepth, outWord, outUnigramProbability);
+}
+
+int PatriciaTriePolicy::getTerminalNodePositionOfWord(
+        const BinaryDictionaryInfo *const binaryDictionaryInfo, const int *const inWord,
+        const int length, const bool forceLowerCaseSearch) const {
+    return BinaryFormat::getTerminalPosition(binaryDictionaryInfo->getDictRoot(), inWord,
+            length, forceLowerCaseSearch);
+}
+
+int PatriciaTriePolicy::getUnigramProbability(
+        const BinaryDictionaryInfo *const binaryDictionaryInfo, const int nodePos) const {
+    const uint8_t *const root = binaryDictionaryInfo->getDictRoot();
+    int pos = nodePos;
+    const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos);
+    if (flags & (BinaryFormat::FLAG_IS_BLACKLISTED | BinaryFormat::FLAG_IS_NOT_A_WORD)) {
+        // If this is not a word, or if it's a blacklisted entry, it should behave as
+        // having no probability outside of the suggestion process (where it should be used
+        // for shortcuts).
+        return NOT_A_PROBABILITY;
+    }
+    const bool hasMultipleChars = (0 != (BinaryFormat::FLAG_HAS_MULTIPLE_CHARS & flags));
+    if (hasMultipleChars) {
+        pos = BinaryFormat::skipOtherCharacters(root, pos);
+    } else {
+        BinaryFormat::getCodePointAndForwardPointer(root, &pos);
+    }
+    return BinaryFormat::readProbabilityWithoutMovingPointer(root, pos);
+}
+
+} // namespace latinime
diff --git a/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.h b/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.h
new file mode 100644
index 0000000..9b93381
--- /dev/null
+++ b/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.h
@@ -0,0 +1,58 @@
+/*
+ * Copyright (C) 2013, The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef LATINIME_PATRICIA_TRIE_POLICY_H
+#define LATINIME_PATRICIA_TRIE_POLICY_H
+
+#include "defines.h"
+#include "suggest/core/policy/dictionary_structure_policy.h"
+
+namespace latinime {
+
+class PatriciaTriePolicy : public DictionaryStructurePolicy {
+ public:
+    static AK_FORCE_INLINE const PatriciaTriePolicy *getInstance() {
+        return &sInstance;
+    }
+
+    AK_FORCE_INLINE int getRootPosition() const {
+        return 0;
+    }
+
+    void createAndGetAllChildNodes(const DicNode *const dicNode,
+            const BinaryDictionaryInfo *const binaryDictionaryInfo,
+            const NodeFilter *const nodeFilter, DicNodeVector *const childDicNodes) const;
+
+    void getWordAtPosition(const BinaryDictionaryInfo *const binaryDictionaryInfo,
+            const int terminalNodePos, const int maxDepth, int *const outWord,
+            int *const outUnigramProbability) const;
+
+    int getTerminalNodePositionOfWord(
+            const BinaryDictionaryInfo *const binaryDictionaryInfo, const int *const inWord,
+            const int length, const bool forceLowerCaseSearch) const;
+
+    int getUnigramProbability(const BinaryDictionaryInfo *const binaryDictionaryInfo,
+            const int nodePos) const;
+
+ private:
+    DISALLOW_COPY_AND_ASSIGN(PatriciaTriePolicy);
+    static const PatriciaTriePolicy sInstance;
+
+    PatriciaTriePolicy() {}
+    ~PatriciaTriePolicy() {}
+};
+} // namespace latinime
+#endif // LATINIME_PATRICIA_TRIE_POLICY_H
diff --git a/tests/src/com/android/inputmethod/latin/RichInputConnectionAndTextRangeTests.java b/tests/src/com/android/inputmethod/latin/RichInputConnectionAndTextRangeTests.java
new file mode 100644
index 0000000..0e077bb
--- /dev/null
+++ b/tests/src/com/android/inputmethod/latin/RichInputConnectionAndTextRangeTests.java
@@ -0,0 +1,312 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.inputmethod.latin;
+
+import android.inputmethodservice.InputMethodService;
+import android.os.Parcel;
+import android.test.AndroidTestCase;
+import android.test.MoreAsserts;
+import android.test.suitebuilder.annotation.SmallTest;
+import android.text.SpannableString;
+import android.text.Spanned;
+import android.text.TextUtils;
+import android.text.style.SuggestionSpan;
+import android.view.inputmethod.ExtractedText;
+import android.view.inputmethod.ExtractedTextRequest;
+import android.view.inputmethod.InputConnection;
+import android.view.inputmethod.InputConnectionWrapper;
+
+import com.android.inputmethod.latin.RichInputConnection.Range;
+
+import java.util.Locale;
+
+@SmallTest
+public class RichInputConnectionAndTextRangeTests extends AndroidTestCase {
+
+    // The following is meant to be a reasonable default for
+    // the "word_separators" resource.
+    private static final String sSeparators = ".,:;!?-";
+
+    @Override
+    protected void setUp() throws Exception {
+        super.setUp();
+    }
+
+    private class MockConnection extends InputConnectionWrapper {
+        final CharSequence mTextBefore;
+        final CharSequence mTextAfter;
+        final ExtractedText mExtractedText;
+
+        public MockConnection(final CharSequence text, final int cursorPosition) {
+            super(null, false);
+            // Interaction of spans with Parcels is completely non-trivial, but in the actual case
+            // the CharSequences do go through Parcels because they go through IPC. There
+            // are some significant differences between the behavior of Spanned objects that
+            // have and that have not gone through parceling, so it's much easier to simulate
+            // the environment with Parcels than try to emulate things by hand.
+            final Parcel p = Parcel.obtain();
+            TextUtils.writeToParcel(text.subSequence(0, cursorPosition), p, 0 /* flags */);
+            TextUtils.writeToParcel(text.subSequence(cursorPosition, text.length()), p,
+                    0 /* flags */);
+            final byte[] marshalled = p.marshall();
+            p.unmarshall(marshalled, 0, marshalled.length);
+            p.setDataPosition(0);
+            mTextBefore = TextUtils.CHAR_SEQUENCE_CREATOR.createFromParcel(p);
+            mTextAfter = TextUtils.CHAR_SEQUENCE_CREATOR.createFromParcel(p);
+            mExtractedText = null;
+            p.recycle();
+        }
+
+        public MockConnection(String textBefore, String textAfter, ExtractedText extractedText) {
+            super(null, false);
+            mTextBefore = textBefore;
+            mTextAfter = textAfter;
+            mExtractedText = extractedText;
+        }
+
+        /* (non-Javadoc)
+         * @see android.view.inputmethod.InputConnectionWrapper#getTextBeforeCursor(int, int)
+         */
+        @Override
+        public CharSequence getTextBeforeCursor(int n, int flags) {
+            return mTextBefore;
+        }
+
+        /* (non-Javadoc)
+         * @see android.view.inputmethod.InputConnectionWrapper#getTextAfterCursor(int, int)
+         */
+        @Override
+        public CharSequence getTextAfterCursor(int n, int flags) {
+            return mTextAfter;
+        }
+
+        /* (non-Javadoc)
+         * @see android.view.inputmethod.InputConnectionWrapper#getExtractedText(
+         *         ExtractedTextRequest, int)
+         */
+        @Override
+        public ExtractedText getExtractedText(ExtractedTextRequest request, int flags) {
+            return mExtractedText;
+        }
+
+        @Override
+        public boolean beginBatchEdit() {
+            return true;
+        }
+
+        @Override
+        public boolean endBatchEdit() {
+            return true;
+        }
+
+        @Override
+        public boolean finishComposingText() {
+            return true;
+        }
+    }
+
+    private class MockInputMethodService extends InputMethodService {
+        InputConnection mInputConnection;
+        public void setInputConnection(final InputConnection inputConnection) {
+            mInputConnection = inputConnection;
+        }
+        @Override
+        public InputConnection getCurrentInputConnection() {
+            return mInputConnection;
+        }
+    }
+
+    /************************** Tests ************************/
+
+    /**
+     * Test for getting previous word (for bigram suggestions)
+     */
+    public void testGetPreviousWord() {
+        // If one of the following cases breaks, the bigram suggestions won't work.
+        assertEquals(RichInputConnection.getNthPreviousWord("abc def", sSeparators, 2), "abc");
+        assertNull(RichInputConnection.getNthPreviousWord("abc", sSeparators, 2));
+        assertNull(RichInputConnection.getNthPreviousWord("abc. def", sSeparators, 2));
+
+        // The following tests reflect the current behavior of the function
+        // RichInputConnection#getNthPreviousWord.
+        // TODO: However at this time, the code does never go
+        // into such a path, so it should be safe to change the behavior of
+        // this function if needed - especially since it does not seem very
+        // logical. These tests are just there to catch any unintentional
+        // changes in the behavior of the RichInputConnection#getPreviousWord method.
+        assertEquals(RichInputConnection.getNthPreviousWord("abc def ", sSeparators, 2), "abc");
+        assertEquals(RichInputConnection.getNthPreviousWord("abc def.", sSeparators, 2), "abc");
+        assertEquals(RichInputConnection.getNthPreviousWord("abc def .", sSeparators, 2), "def");
+        assertNull(RichInputConnection.getNthPreviousWord("abc ", sSeparators, 2));
+
+        assertEquals(RichInputConnection.getNthPreviousWord("abc def", sSeparators, 1), "def");
+        assertEquals(RichInputConnection.getNthPreviousWord("abc def ", sSeparators, 1), "def");
+        assertNull(RichInputConnection.getNthPreviousWord("abc def.", sSeparators, 1));
+        assertNull(RichInputConnection.getNthPreviousWord("abc def .", sSeparators, 1));
+    }
+
+    /**
+     * Test logic in getting the word range at the cursor.
+     */
+    public void testGetWordRangeAtCursor() {
+        ExtractedText et = new ExtractedText();
+        final MockInputMethodService mockInputMethodService = new MockInputMethodService();
+        final RichInputConnection ic = new RichInputConnection(mockInputMethodService);
+        mockInputMethodService.setInputConnection(new MockConnection("word wo", "rd", et));
+        et.startOffset = 0;
+        et.selectionStart = 7;
+        Range r;
+
+        ic.beginBatchEdit();
+        // basic case
+        r = ic.getWordRangeAtCursor(" ", 0);
+        assertTrue(TextUtils.equals("word", r.mWord));
+
+        // more than one word
+        r = ic.getWordRangeAtCursor(" ", 1);
+        assertTrue(TextUtils.equals("word word", r.mWord));
+        ic.endBatchEdit();
+
+        // tab character instead of space
+        mockInputMethodService.setInputConnection(new MockConnection("one\tword\two", "rd", et));
+        ic.beginBatchEdit();
+        r = ic.getWordRangeAtCursor("\t", 1);
+        ic.endBatchEdit();
+        assertTrue(TextUtils.equals("word\tword", r.mWord));
+
+        // only one word doesn't go too far
+        mockInputMethodService.setInputConnection(new MockConnection("one\tword\two", "rd", et));
+        ic.beginBatchEdit();
+        r = ic.getWordRangeAtCursor("\t", 1);
+        ic.endBatchEdit();
+        assertTrue(TextUtils.equals("word\tword", r.mWord));
+
+        // tab or space
+        mockInputMethodService.setInputConnection(new MockConnection("one word\two", "rd", et));
+        ic.beginBatchEdit();
+        r = ic.getWordRangeAtCursor(" \t", 1);
+        ic.endBatchEdit();
+        assertTrue(TextUtils.equals("word\tword", r.mWord));
+
+        // tab or space multiword
+        mockInputMethodService.setInputConnection(new MockConnection("one word\two", "rd", et));
+        ic.beginBatchEdit();
+        r = ic.getWordRangeAtCursor(" \t", 2);
+        ic.endBatchEdit();
+        assertTrue(TextUtils.equals("one word\tword", r.mWord));
+
+        // splitting on supplementary character
+        final String supplementaryChar = "\uD840\uDC8A";
+        mockInputMethodService.setInputConnection(
+                new MockConnection("one word" + supplementaryChar + "wo", "rd", et));
+        ic.beginBatchEdit();
+        r = ic.getWordRangeAtCursor(supplementaryChar, 0);
+        ic.endBatchEdit();
+        assertTrue(TextUtils.equals("word", r.mWord));
+    }
+
+    /**
+     * Test logic in getting the word range at the cursor.
+     */
+    public void testGetSuggestionSpansAtWord() {
+        helpTestGetSuggestionSpansAtWord(10);
+        helpTestGetSuggestionSpansAtWord(12);
+        helpTestGetSuggestionSpansAtWord(15);
+        helpTestGetSuggestionSpansAtWord(16);
+    }
+
+    private void helpTestGetSuggestionSpansAtWord(final int cursorPos) {
+        final MockInputMethodService mockInputMethodService = new MockInputMethodService();
+        final RichInputConnection ic = new RichInputConnection(mockInputMethodService);
+
+        final String[] SUGGESTIONS1 = { "swing", "strong" };
+        final String[] SUGGESTIONS2 = { "storing", "strung" };
+
+        // Test the usual case.
+        SpannableString text = new SpannableString("This is a string for test");
+        text.setSpan(new SuggestionSpan(Locale.ENGLISH, SUGGESTIONS1, 0 /* flags */),
+                10 /* start */, 16 /* end */, 0 /* flags */);
+        mockInputMethodService.setInputConnection(new MockConnection(text, cursorPos));
+        Range r;
+        SuggestionSpan[] suggestions;
+
+        r = ic.getWordRangeAtCursor(" ", 0);
+        suggestions = r.getSuggestionSpansAtWord();
+        assertEquals(suggestions.length, 1);
+        MoreAsserts.assertEquals(suggestions[0].getSuggestions(), SUGGESTIONS1);
+
+        // Test the case with 2 suggestion spans in the same place.
+        text = new SpannableString("This is a string for test");
+        text.setSpan(new SuggestionSpan(Locale.ENGLISH, SUGGESTIONS1, 0 /* flags */),
+                10 /* start */, 16 /* end */, 0 /* flags */);
+        text.setSpan(new SuggestionSpan(Locale.ENGLISH, SUGGESTIONS2, 0 /* flags */),
+                10 /* start */, 16 /* end */, 0 /* flags */);
+        mockInputMethodService.setInputConnection(new MockConnection(text, cursorPos));
+        r = ic.getWordRangeAtCursor(" ", 0);
+        suggestions = r.getSuggestionSpansAtWord();
+        assertEquals(suggestions.length, 2);
+        MoreAsserts.assertEquals(suggestions[0].getSuggestions(), SUGGESTIONS1);
+        MoreAsserts.assertEquals(suggestions[1].getSuggestions(), SUGGESTIONS2);
+
+        // Test a case with overlapping spans, 2nd extending past the start of the word
+        text = new SpannableString("This is a string for test");
+        text.setSpan(new SuggestionSpan(Locale.ENGLISH, SUGGESTIONS1, 0 /* flags */),
+                10 /* start */, 16 /* end */, 0 /* flags */);
+        text.setSpan(new SuggestionSpan(Locale.ENGLISH, SUGGESTIONS2, 0 /* flags */),
+                5 /* start */, 16 /* end */, 0 /* flags */);
+        mockInputMethodService.setInputConnection(new MockConnection(text, cursorPos));
+        r = ic.getWordRangeAtCursor(" ", 0);
+        suggestions = r.getSuggestionSpansAtWord();
+        assertEquals(suggestions.length, 1);
+        MoreAsserts.assertEquals(suggestions[0].getSuggestions(), SUGGESTIONS1);
+
+        // Test a case with overlapping spans, 2nd extending past the end of the word
+        text = new SpannableString("This is a string for test");
+        text.setSpan(new SuggestionSpan(Locale.ENGLISH, SUGGESTIONS1, 0 /* flags */),
+                10 /* start */, 16 /* end */, 0 /* flags */);
+        text.setSpan(new SuggestionSpan(Locale.ENGLISH, SUGGESTIONS2, 0 /* flags */),
+                10 /* start */, 20 /* end */, 0 /* flags */);
+        mockInputMethodService.setInputConnection(new MockConnection(text, cursorPos));
+        r = ic.getWordRangeAtCursor(" ", 0);
+        suggestions = r.getSuggestionSpansAtWord();
+        assertEquals(suggestions.length, 1);
+        MoreAsserts.assertEquals(suggestions[0].getSuggestions(), SUGGESTIONS1);
+
+        // Test a case with overlapping spans, 2nd extending past both ends of the word
+        text = new SpannableString("This is a string for test");
+        text.setSpan(new SuggestionSpan(Locale.ENGLISH, SUGGESTIONS1, 0 /* flags */),
+                10 /* start */, 16 /* end */, 0 /* flags */);
+        text.setSpan(new SuggestionSpan(Locale.ENGLISH, SUGGESTIONS2, 0 /* flags */),
+                5 /* start */, 20 /* end */, 0 /* flags */);
+        mockInputMethodService.setInputConnection(new MockConnection(text, cursorPos));
+        r = ic.getWordRangeAtCursor(" ", 0);
+        suggestions = r.getSuggestionSpansAtWord();
+        assertEquals(suggestions.length, 1);
+        MoreAsserts.assertEquals(suggestions[0].getSuggestions(), SUGGESTIONS1);
+
+        // Test a case with overlapping spans, none right on the word
+        text = new SpannableString("This is a string for test");
+        text.setSpan(new SuggestionSpan(Locale.ENGLISH, SUGGESTIONS1, 0 /* flags */),
+                5 /* start */, 16 /* end */, 0 /* flags */);
+        text.setSpan(new SuggestionSpan(Locale.ENGLISH, SUGGESTIONS2, 0 /* flags */),
+                5 /* start */, 20 /* end */, 0 /* flags */);
+        mockInputMethodService.setInputConnection(new MockConnection(text, cursorPos));
+        r = ic.getWordRangeAtCursor(" ", 0);
+        suggestions = r.getSuggestionSpansAtWord();
+        assertEquals(suggestions.length, 0);
+    }
+}
diff --git a/tests/src/com/android/inputmethod/latin/RichInputConnectionTests.java b/tests/src/com/android/inputmethod/latin/RichInputConnectionTests.java
deleted file mode 100644
index aacd60f..0000000
--- a/tests/src/com/android/inputmethod/latin/RichInputConnectionTests.java
+++ /dev/null
@@ -1,194 +0,0 @@
-/*
- * Copyright (C) 2012 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.android.inputmethod.latin;
-
-import android.inputmethodservice.InputMethodService;
-import android.test.AndroidTestCase;
-import android.test.suitebuilder.annotation.SmallTest;
-import android.text.TextUtils;
-import android.view.inputmethod.ExtractedText;
-import android.view.inputmethod.ExtractedTextRequest;
-import android.view.inputmethod.InputConnection;
-import android.view.inputmethod.InputConnectionWrapper;
-
-import com.android.inputmethod.latin.RichInputConnection.Range;
-
-@SmallTest
-public class RichInputConnectionTests extends AndroidTestCase {
-
-    // The following is meant to be a reasonable default for
-    // the "word_separators" resource.
-    private static final String sSeparators = ".,:;!?-";
-
-    @Override
-    protected void setUp() throws Exception {
-        super.setUp();
-    }
-
-    private class MockConnection extends InputConnectionWrapper {
-        final String mTextBefore;
-        final String mTextAfter;
-        final ExtractedText mExtractedText;
-
-        public MockConnection(String textBefore, String textAfter, ExtractedText extractedText) {
-            super(null, false);
-            mTextBefore = textBefore;
-            mTextAfter = textAfter;
-            mExtractedText = extractedText;
-        }
-
-        /* (non-Javadoc)
-         * @see android.view.inputmethod.InputConnectionWrapper#getTextBeforeCursor(int, int)
-         */
-        @Override
-        public CharSequence getTextBeforeCursor(int n, int flags) {
-            return mTextBefore;
-        }
-
-        /* (non-Javadoc)
-         * @see android.view.inputmethod.InputConnectionWrapper#getTextAfterCursor(int, int)
-         */
-        @Override
-        public CharSequence getTextAfterCursor(int n, int flags) {
-            return mTextAfter;
-        }
-
-        /* (non-Javadoc)
-         * @see android.view.inputmethod.InputConnectionWrapper#getExtractedText(
-         *         ExtractedTextRequest, int)
-         */
-        @Override
-        public ExtractedText getExtractedText(ExtractedTextRequest request, int flags) {
-            return mExtractedText;
-        }
-
-        @Override
-        public boolean beginBatchEdit() {
-            return true;
-        }
-
-        @Override
-        public boolean endBatchEdit() {
-            return true;
-        }
-
-        @Override
-        public boolean finishComposingText() {
-            return true;
-        }
-    }
-
-    private class MockInputMethodService extends InputMethodService {
-        InputConnection mInputConnection;
-        public void setInputConnection(final InputConnection inputConnection) {
-            mInputConnection = inputConnection;
-        }
-        @Override
-        public InputConnection getCurrentInputConnection() {
-            return mInputConnection;
-        }
-    }
-
-    /************************** Tests ************************/
-
-    /**
-     * Test for getting previous word (for bigram suggestions)
-     */
-    public void testGetPreviousWord() {
-        // If one of the following cases breaks, the bigram suggestions won't work.
-        assertEquals(RichInputConnection.getNthPreviousWord("abc def", sSeparators, 2), "abc");
-        assertNull(RichInputConnection.getNthPreviousWord("abc", sSeparators, 2));
-        assertNull(RichInputConnection.getNthPreviousWord("abc. def", sSeparators, 2));
-
-        // The following tests reflect the current behavior of the function
-        // RichInputConnection#getNthPreviousWord.
-        // TODO: However at this time, the code does never go
-        // into such a path, so it should be safe to change the behavior of
-        // this function if needed - especially since it does not seem very
-        // logical. These tests are just there to catch any unintentional
-        // changes in the behavior of the RichInputConnection#getPreviousWord method.
-        assertEquals(RichInputConnection.getNthPreviousWord("abc def ", sSeparators, 2), "abc");
-        assertEquals(RichInputConnection.getNthPreviousWord("abc def.", sSeparators, 2), "abc");
-        assertEquals(RichInputConnection.getNthPreviousWord("abc def .", sSeparators, 2), "def");
-        assertNull(RichInputConnection.getNthPreviousWord("abc ", sSeparators, 2));
-
-        assertEquals(RichInputConnection.getNthPreviousWord("abc def", sSeparators, 1), "def");
-        assertEquals(RichInputConnection.getNthPreviousWord("abc def ", sSeparators, 1), "def");
-        assertNull(RichInputConnection.getNthPreviousWord("abc def.", sSeparators, 1));
-        assertNull(RichInputConnection.getNthPreviousWord("abc def .", sSeparators, 1));
-    }
-
-    /**
-     * Test logic in getting the word range at the cursor.
-     */
-    public void testGetWordRangeAtCursor() {
-        ExtractedText et = new ExtractedText();
-        final MockInputMethodService mockInputMethodService = new MockInputMethodService();
-        final RichInputConnection ic = new RichInputConnection(mockInputMethodService);
-        mockInputMethodService.setInputConnection(new MockConnection("word wo", "rd", et));
-        et.startOffset = 0;
-        et.selectionStart = 7;
-        Range r;
-
-        ic.beginBatchEdit();
-        // basic case
-        r = ic.getWordRangeAtCursor(" ", 0);
-        assertTrue(TextUtils.equals("word", r.mWord));
-
-        // more than one word
-        r = ic.getWordRangeAtCursor(" ", 1);
-        assertTrue(TextUtils.equals("word word", r.mWord));
-        ic.endBatchEdit();
-
-        // tab character instead of space
-        mockInputMethodService.setInputConnection(new MockConnection("one\tword\two", "rd", et));
-        ic.beginBatchEdit();
-        r = ic.getWordRangeAtCursor("\t", 1);
-        ic.endBatchEdit();
-        assertTrue(TextUtils.equals("word\tword", r.mWord));
-
-        // only one word doesn't go too far
-        mockInputMethodService.setInputConnection(new MockConnection("one\tword\two", "rd", et));
-        ic.beginBatchEdit();
-        r = ic.getWordRangeAtCursor("\t", 1);
-        ic.endBatchEdit();
-        assertTrue(TextUtils.equals("word\tword", r.mWord));
-
-        // tab or space
-        mockInputMethodService.setInputConnection(new MockConnection("one word\two", "rd", et));
-        ic.beginBatchEdit();
-        r = ic.getWordRangeAtCursor(" \t", 1);
-        ic.endBatchEdit();
-        assertTrue(TextUtils.equals("word\tword", r.mWord));
-
-        // tab or space multiword
-        mockInputMethodService.setInputConnection(new MockConnection("one word\two", "rd", et));
-        ic.beginBatchEdit();
-        r = ic.getWordRangeAtCursor(" \t", 2);
-        ic.endBatchEdit();
-        assertTrue(TextUtils.equals("one word\tword", r.mWord));
-
-        // splitting on supplementary character
-        final String supplementaryChar = "\uD840\uDC8A";
-        mockInputMethodService.setInputConnection(
-                new MockConnection("one word" + supplementaryChar + "wo", "rd", et));
-        ic.beginBatchEdit();
-        r = ic.getWordRangeAtCursor(supplementaryChar, 0);
-        ic.endBatchEdit();
-        assertTrue(TextUtils.equals("word", r.mWord));
-    }
-}