Merge "Regenerate old version dictionaries using new format."
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/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/dictionarypack/DictionaryService.java b/java/src/com/android/inputmethod/dictionarypack/DictionaryService.java
index 6e3dd71..3b00723 100644
--- a/java/src/com/android/inputmethod/dictionarypack/DictionaryService.java
+++ b/java/src/com/android/inputmethod/dictionarypack/DictionaryService.java
@@ -170,7 +170,7 @@
             checkTimeAndMaybeSetupUpdateAlarm(context);
         } else if (DictionaryPackConstants.UPDATE_NOW_INTENT_ACTION.equals(intent.getAction())) {
             // Intent to trigger an update now.
-            UpdateHandler.update(context, false);
+            UpdateHandler.tryUpdate(context, false);
         } else {
             UpdateHandler.downloadFinished(context, intent);
         }
@@ -221,7 +221,7 @@
      */
     public static void updateNowIfNotUpdatedInAVeryLongTime(final Context context) {
         if (!isLastUpdateAtLeastThisOld(context, VERY_LONG_TIME)) return;
-        UpdateHandler.update(context, false);
+        UpdateHandler.tryUpdate(context, false);
     }
 
     /**
diff --git a/java/src/com/android/inputmethod/dictionarypack/DictionarySettingsFragment.java b/java/src/com/android/inputmethod/dictionarypack/DictionarySettingsFragment.java
index 4b89d20..7bbd041 100644
--- a/java/src/com/android/inputmethod/dictionarypack/DictionarySettingsFragment.java
+++ b/java/src/com/android/inputmethod/dictionarypack/DictionarySettingsFragment.java
@@ -30,6 +30,7 @@
 import android.preference.Preference;
 import android.preference.PreferenceFragment;
 import android.preference.PreferenceGroup;
+import android.text.TextUtils;
 import android.text.format.DateUtils;
 import android.util.Log;
 import android.view.animation.AnimationUtils;
@@ -104,9 +105,16 @@
 
     @Override
     public void onCreateOptionsMenu(final Menu menu, final MenuInflater inflater) {
-        mUpdateNowMenu = menu.add(Menu.NONE, MENU_UPDATE_NOW, 0, R.string.check_for_updates_now);
-        mUpdateNowMenu.setShowAsAction(MenuItem.SHOW_AS_ACTION_IF_ROOM);
-        refreshNetworkState();
+        final String metadataUri =
+                MetadataDbHelper.getMetadataUriAsString(getActivity(), mClientId);
+        // We only add the "Refresh" button if we have a non-empty URL to refresh from. If the
+        // URL is empty, of course we can't refresh so it makes no sense to display this.
+        if (!TextUtils.isEmpty(metadataUri)) {
+            mUpdateNowMenu =
+                    menu.add(Menu.NONE, MENU_UPDATE_NOW, 0, R.string.check_for_updates_now);
+            mUpdateNowMenu.setShowAsAction(MenuItem.SHOW_AS_ACTION_IF_ROOM);
+            refreshNetworkState();
+        }
     }
 
     @Override
@@ -353,7 +361,12 @@
         new Thread("updateByHand") {
             @Override
             public void run() {
-                UpdateHandler.update(activity, true);
+                // We call tryUpdate(), which returns whether we could successfully start an update.
+                // If we couldn't, we'll never receive the end callback, so we stop the loading
+                // animation and return to the previous screen.
+                if (!UpdateHandler.tryUpdate(activity, true)) {
+                    stopLoadingAnimation();
+                }
             }
         }.start();
     }
@@ -368,7 +381,9 @@
     private void startLoadingAnimation() {
         mLoadingView.setVisibility(View.VISIBLE);
         getView().setVisibility(View.GONE);
-        mUpdateNowMenu.setTitle(R.string.cancel);
+        // We come here when the menu element is pressed so presumably it can't be null. But
+        // better safe than sorry.
+        if (null != mUpdateNowMenu) mUpdateNowMenu.setTitle(R.string.cancel);
     }
 
     private void stopLoadingAnimation() {
diff --git a/java/src/com/android/inputmethod/dictionarypack/UpdateHandler.java b/java/src/com/android/inputmethod/dictionarypack/UpdateHandler.java
index 719f24e..8a23acd 100644
--- a/java/src/com/android/inputmethod/dictionarypack/UpdateHandler.java
+++ b/java/src/com/android/inputmethod/dictionarypack/UpdateHandler.java
@@ -173,14 +173,15 @@
      * Download latest metadata from the server through DownloadManager for all known clients
      * @param context The context for retrieving resources
      * @param updateNow Whether we should update NOW, or respect bandwidth policies
+     * @return true if an update successfully started, false otherwise.
      */
-    public static void update(final Context context, final boolean updateNow) {
+    public static boolean tryUpdate(final Context context, final boolean updateNow) {
         // TODO: loop through all clients instead of only doing the default one.
         final TreeSet<String> uris = new TreeSet<String>();
         final Cursor cursor = MetadataDbHelper.queryClientIds(context);
-        if (null == cursor) return;
+        if (null == cursor) return false;
         try {
-            if (!cursor.moveToFirst()) return;
+            if (!cursor.moveToFirst()) return false;
             do {
                 final String clientId = cursor.getString(0);
                 final String metadataUri =
@@ -192,6 +193,7 @@
         } finally {
             cursor.close();
         }
+        boolean started = false;
         for (final String metadataUri : uris) {
             if (!TextUtils.isEmpty(metadataUri)) {
                 // If the metadata URI is empty, that means we should never update it at all.
@@ -200,8 +202,10 @@
                 // is a bug and it happens anyway, doing nothing is the right thing to do.
                 // For more information, {@see DictionaryProvider#insert(Uri, ContentValues)}.
                 updateClientsWithMetadataUri(context, updateNow, metadataUri);
+                started = true;
             }
         }
+        return started;
     }
 
     /**
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 2e1e661..31a892e 100644
--- a/java/src/com/android/inputmethod/latin/BinaryDictionaryGetter.java
+++ b/java/src/com/android/inputmethod/latin/BinaryDictionaryGetter.java
@@ -287,13 +287,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/LatinIME.java b/java/src/com/android/inputmethod/latin/LatinIME.java
index 0560cf5..f3fc317 100644
--- a/java/src/com/android/inputmethod/latin/LatinIME.java
+++ b/java/src/com/android/inputmethod/latin/LatinIME.java
@@ -961,7 +961,11 @@
             // TODO: is it still necessary to test for composingSpan related stuff?
             final boolean selectionChangedOrSafeToReset = selectionChanged
                     || (!mWordComposer.isComposingWord()) || noComposingSpan;
-            if (selectionChangedOrSafeToReset) {
+            final boolean hasOrHadSelection = (oldSelStart != oldSelEnd
+                    || newSelStart != newSelEnd);
+            final int moveAmount = newSelStart - oldSelStart;
+            if (selectionChangedOrSafeToReset && (hasOrHadSelection
+                    || !mWordComposer.moveCursorByAndReturnIfInsideComposingWord(moveAmount))) {
                 // If we are composing a word and moving the cursor, we would want to set a
                 // suggestion span for recorrection to work correctly. Unfortunately, that
                 // would involve the keyboard committing some new text, which would move the
@@ -2535,6 +2539,7 @@
             }
         }
         mWordComposer.setComposingWord(typedWord, mKeyboardSwitcher.getKeyboard());
+        // TODO: this is in chars but the callee expects code points!
         mWordComposer.setCursorPositionWithinWord(numberOfCharsInWordBeforeCursor);
         mConnection.setComposingRegion(
                 mLastSelectionStart - numberOfCharsInWordBeforeCursor,
diff --git a/java/src/com/android/inputmethod/latin/WordComposer.java b/java/src/com/android/inputmethod/latin/WordComposer.java
index e078f03..2babe8b 100644
--- a/java/src/com/android/inputmethod/latin/WordComposer.java
+++ b/java/src/com/android/inputmethod/latin/WordComposer.java
@@ -192,6 +192,40 @@
         return mCursorPositionWithinWord != mCodePointSize;
     }
 
+    /**
+     * When the cursor is moved by the user, we need to update its position.
+     * If it falls inside the currently composing word, we don't reset the composition, and
+     * only update the cursor position.
+     *
+     * @param expectedMoveAmount How many java chars to move the cursor. Negative values move
+     * the cursor backward, positive values move the cursor forward.
+     * @return true if the cursor is still inside the composing word, false otherwise.
+     */
+    public boolean moveCursorByAndReturnIfInsideComposingWord(final int expectedMoveAmount) {
+        int actualMoveAmountWithinWord = 0;
+        int cursorPos = mCursorPositionWithinWord;
+        if (expectedMoveAmount >= 0) {
+            // Moving the cursor forward for the expected amount or until the end of the word has
+            // been reached, whichever comes first.
+            while (actualMoveAmountWithinWord < expectedMoveAmount && cursorPos < mCodePointSize) {
+                actualMoveAmountWithinWord += Character.charCount(mPrimaryKeyCodes[cursorPos]);
+                ++cursorPos;
+            }
+        } else {
+            // Moving the cursor backward for the expected amount or until the start of the word
+            // has been reached, whichever comes first.
+            while (actualMoveAmountWithinWord > expectedMoveAmount && cursorPos > 0) {
+                --cursorPos;
+                actualMoveAmountWithinWord -= Character.charCount(mPrimaryKeyCodes[cursorPos]);
+            }
+        }
+        // If the actual and expected amounts differ, we crossed the start or the end of the word
+        // so the result would not be inside the composing word.
+        if (actualMoveAmountWithinWord != expectedMoveAmount) return false;
+        mCursorPositionWithinWord = cursorPos;
+        return true;
+    }
+
     public void setBatchInputPointers(final InputPointers batchPointers) {
         mInputPointers.set(batchPointers);
         mIsBatchMode = true;
diff --git a/java/src/com/android/inputmethod/research/LogUnit.java b/java/src/com/android/inputmethod/research/LogUnit.java
index 164c7e8..3366df1 100644
--- a/java/src/com/android/inputmethod/research/LogUnit.java
+++ b/java/src/com/android/inputmethod/research/LogUnit.java
@@ -146,7 +146,8 @@
         if (size != 0) {
             // Note that jsonWriter is only set to a non-null value if the logUnit start text is
             // output and at least one logStatement is output.
-            JsonWriter jsonWriter = null;
+            JsonWriter jsonWriter = researchLog.getInitializedJsonWriterLocked();
+            outputLogUnitStart(jsonWriter, canIncludePrivateData);
             for (int i = 0; i < size; i++) {
                 final LogStatement logStatement = mLogStatementList.get(i);
                 if (!canIncludePrivateData && logStatement.isPotentiallyPrivate()) {
@@ -155,42 +156,35 @@
                 if (mIsPartOfMegaword && logStatement.isPotentiallyRevealing()) {
                     continue;
                 }
-                // Only retrieve the jsonWriter if we need to.  If we don't get this far, then
-                // researchLog.getInitializedJsonWriterLocked() will not ever be called, and the
-                // file will not have been opened for writing.
-                if (jsonWriter == null) {
-                    jsonWriter = researchLog.getInitializedJsonWriterLocked();
-                    outputLogUnitStart(jsonWriter, canIncludePrivateData);
-                }
                 logStatement.outputToLocked(jsonWriter, mTimeList.get(i), mValuesList.get(i));
             }
-            if (jsonWriter != null) {
-                // We must have called logUnitStart earlier, so emit a logUnitStop.
-                outputLogUnitStop(jsonWriter);
-            }
+            outputLogUnitStop(jsonWriter);
         }
     }
 
     private static final String WORD_KEY = "_wo";
+    private static final String NUM_WORDS_KEY = "_nw";
     private static final String CORRECTION_TYPE_KEY = "_corType";
     private static final String LOG_UNIT_BEGIN_KEY = "logUnitStart";
     private static final String LOG_UNIT_END_KEY = "logUnitEnd";
 
     final LogStatement LOGSTATEMENT_LOG_UNIT_BEGIN_WITH_PRIVATE_DATA =
             new LogStatement(LOG_UNIT_BEGIN_KEY, false /* isPotentiallyPrivate */,
-                    false /* isPotentiallyRevealing */, WORD_KEY, CORRECTION_TYPE_KEY);
+                    false /* isPotentiallyRevealing */, WORD_KEY, CORRECTION_TYPE_KEY,
+                    NUM_WORDS_KEY);
     final LogStatement LOGSTATEMENT_LOG_UNIT_BEGIN_WITHOUT_PRIVATE_DATA =
             new LogStatement(LOG_UNIT_BEGIN_KEY, false /* isPotentiallyPrivate */,
-                    false /* isPotentiallyRevealing */);
+                    false /* isPotentiallyRevealing */, NUM_WORDS_KEY);
     private void outputLogUnitStart(final JsonWriter jsonWriter,
             final boolean canIncludePrivateData) {
         final LogStatement logStatement;
         if (canIncludePrivateData) {
             LOGSTATEMENT_LOG_UNIT_BEGIN_WITH_PRIVATE_DATA.outputToLocked(jsonWriter,
-                    SystemClock.uptimeMillis(), getWordsAsString(), getCorrectionType());
+                    SystemClock.uptimeMillis(), getWordsAsString(), getCorrectionType(),
+                    getNumWords());
         } else {
             LOGSTATEMENT_LOG_UNIT_BEGIN_WITHOUT_PRIVATE_DATA.outputToLocked(jsonWriter,
-                    SystemClock.uptimeMillis());
+                    SystemClock.uptimeMillis(), getNumWords());
         }
     }
 
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/src/suggest/core/dicnode/dic_node_utils.cpp b/native/jni/src/suggest/core/dicnode/dic_node_utils.cpp
index 2063c39..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,14 +37,15 @@
 
 /* static */ void DicNodeUtils::initAsRoot(const BinaryDictionaryInfo *const binaryDictionaryInfo,
         const int prevWordNodePos, DicNode *const newRootNode) {
-    newRootNode->initAsRoot(binaryDictionaryInfo->getRootPosition(), prevWordNodePos);
+    newRootNode->initAsRoot(binaryDictionaryInfo->getStructurePolicy()->getRootPosition(),
+            prevWordNodePos);
 }
 
 /*static */ void DicNodeUtils::initAsRootWithPreviousWord(
         const BinaryDictionaryInfo *const binaryDictionaryInfo,
         DicNode *const prevWordLastNode, DicNode *const newRootNode) {
     newRootNode->initAsRootWithPreviousWord(
-            prevWordLastNode, binaryDictionaryInfo->getRootPosition());
+            prevWordLastNode, binaryDictionaryInfo->getStructurePolicy()->getRootPosition());
 }
 
 /* static */ void DicNodeUtils::initByCopy(DicNode *srcNode, DicNode *destNode) {
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_info.h b/native/jni/src/suggest/core/dictionary/binary_dictionary_info.h
index c921236..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,11 +22,10 @@
 #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,
@@ -35,7 +34,9 @@
               mDictBufOffset(dictBufOffset), mIsUpdatable(isUpdatable),
               mDictionaryFormat(BinaryDictionaryFormatUtils::detectFormatVersion(
                       mDictBuf, mDictSize)),
-              mDictionaryHeader(this), mDictRoot(mDictBuf + mDictionaryHeader.getSize()) {}
+              mDictionaryHeader(this), mDictRoot(mDictBuf + mDictionaryHeader.getSize()),
+              mStructurePolicy(DictionaryStructurePolicyFactory::getDictionaryStructurePolicy(
+                      mDictionaryFormat)) {}
 
     AK_FORCE_INLINE const uint8_t *getDictBuf() const {
         return mDictBuf;
@@ -61,10 +62,6 @@
         return mDictionaryFormat;
     }
 
-    AK_FORCE_INLINE int getRootPosition() const {
-        return 0;
-    }
-
     AK_FORCE_INLINE const BinaryDictionaryHeader *getHeader() const {
         return &mDictionaryHeader;
     }
@@ -75,6 +72,10 @@
         return mIsUpdatable && isUpdatableDictionaryFormat;
     }
 
+    AK_FORCE_INLINE const DictionaryStructurePolicy *getStructurePolicy() const {
+        return mStructurePolicy;
+    }
+
  private:
     DISALLOW_COPY_AND_ASSIGN(BinaryDictionaryInfo);
 
@@ -86,6 +87,7 @@
     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/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/WordComposerTests.java b/tests/src/com/android/inputmethod/latin/WordComposerTests.java
new file mode 100644
index 0000000..1434c6b
--- /dev/null
+++ b/tests/src/com/android/inputmethod/latin/WordComposerTests.java
@@ -0,0 +1,93 @@
+/*
+ * 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.
+ */
+
+package com.android.inputmethod.latin;
+
+import android.test.AndroidTestCase;
+import android.test.suitebuilder.annotation.SmallTest;
+
+/**
+ * Unit tests for WordComposer.
+ */
+@SmallTest
+public class WordComposerTests extends AndroidTestCase {
+    public void testMoveCursor() {
+        final WordComposer wc = new WordComposer();
+        final String STR_WITHIN_BMP = "abcdef";
+        wc.setComposingWord(STR_WITHIN_BMP, null);
+        assertEquals(wc.size(),
+                STR_WITHIN_BMP.codePointCount(0, STR_WITHIN_BMP.length()));
+        assertFalse(wc.isCursorFrontOrMiddleOfComposingWord());
+        wc.setCursorPositionWithinWord(2);
+        assertTrue(wc.isCursorFrontOrMiddleOfComposingWord());
+        // Move the cursor to after the 'd'
+        assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(2));
+        assertTrue(wc.isCursorFrontOrMiddleOfComposingWord());
+        // Move the cursor to after the 'e'
+        assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(1));
+        assertTrue(wc.isCursorFrontOrMiddleOfComposingWord());
+        assertEquals(wc.size(), 6);
+        // Move the cursor to after the 'f'
+        assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(1));
+        assertFalse(wc.isCursorFrontOrMiddleOfComposingWord());
+        // Move the cursor past the end of the word
+        assertFalse(wc.moveCursorByAndReturnIfInsideComposingWord(1));
+        assertFalse(wc.moveCursorByAndReturnIfInsideComposingWord(15));
+
+        // \uD861\uDED7 is 𨛗, a character outside the BMP
+        final String STR_WITH_SUPPLEMENTARY_CHAR = "abcde\uD861\uDED7fgh";
+        wc.setComposingWord(STR_WITH_SUPPLEMENTARY_CHAR, null);
+        assertEquals(wc.size(), STR_WITH_SUPPLEMENTARY_CHAR.codePointCount(0,
+                        STR_WITH_SUPPLEMENTARY_CHAR.length()));
+        assertFalse(wc.isCursorFrontOrMiddleOfComposingWord());
+        wc.setCursorPositionWithinWord(3);
+        assertTrue(wc.isCursorFrontOrMiddleOfComposingWord());
+        assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(6));
+        assertTrue(wc.isCursorFrontOrMiddleOfComposingWord());
+        assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(1));
+        assertFalse(wc.isCursorFrontOrMiddleOfComposingWord());
+
+        wc.setComposingWord(STR_WITH_SUPPLEMENTARY_CHAR, null);
+        wc.setCursorPositionWithinWord(3);
+        assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(7));
+
+        wc.setComposingWord(STR_WITH_SUPPLEMENTARY_CHAR, null);
+        wc.setCursorPositionWithinWord(3);
+        assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(7));
+
+        wc.setComposingWord(STR_WITH_SUPPLEMENTARY_CHAR, null);
+        wc.setCursorPositionWithinWord(3);
+        assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(-3));
+        assertFalse(wc.moveCursorByAndReturnIfInsideComposingWord(-1));
+
+        wc.setComposingWord(STR_WITH_SUPPLEMENTARY_CHAR, null);
+        wc.setCursorPositionWithinWord(3);
+        assertFalse(wc.moveCursorByAndReturnIfInsideComposingWord(-9));
+
+        wc.setComposingWord(STR_WITH_SUPPLEMENTARY_CHAR, null);
+        assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(-10));
+
+        wc.setComposingWord(STR_WITH_SUPPLEMENTARY_CHAR, null);
+        assertFalse(wc.moveCursorByAndReturnIfInsideComposingWord(-11));
+
+        wc.setComposingWord(STR_WITH_SUPPLEMENTARY_CHAR, null);
+        assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(0));
+
+        wc.setComposingWord(STR_WITH_SUPPLEMENTARY_CHAR, null);
+        wc.setCursorPositionWithinWord(2);
+        assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(0));
+    }
+}