1 files changed, 322 insertions, 176 deletions

diff --git a/native/src/unigram_dictionary.cpp b/native/src/unigram_dictionary.cpp
index 8eb5a9700..e998ee486 100644
--- a/native/src/unigram_dictionary.cpp
+++ b/native/src/unigram_dictionary.cpp
@@ -25,6 +25,7 @@
 #include "unigram_dictionary.h"
 
 #include "binary_format.h"
+#include "terminal_attributes.h"
 
 namespace latinime {
 
@@ -46,21 +47,25 @@ UnigramDictionary::UnigramDictionary(const uint8_t* const streamStart, int typed
     BYTES_IN_ONE_CHAR(MAX_PROXIMITY_CHARS * sizeof(int)),
     MAX_UMLAUT_SEARCH_DEPTH(DEFAULT_MAX_UMLAUT_SEARCH_DEPTH) {
     if (DEBUG_DICT) {
-        LOGI("UnigramDictionary - constructor");
+        AKLOGI("UnigramDictionary - constructor");
     }
-    mCorrection = new Correction(typedLetterMultiplier, fullWordMultiplier);
 }
 
 UnigramDictionary::~UnigramDictionary() {
-    delete mCorrection;
 }
 
-static inline unsigned int getCodesBufferSize(const int* codes, const int codesSize,
+static inline unsigned int getCodesBufferSize(const int *codes, const int codesSize,
         const int MAX_PROXIMITY_CHARS) {
     return sizeof(*codes) * MAX_PROXIMITY_CHARS * codesSize;
 }
 
-bool UnigramDictionary::isDigraph(const int* codes, const int i, const int codesSize) const {
+// TODO: This needs to take an const unsigned short* and not tinker with its contents
+static inline void addWord(
+        unsigned short *word, int length, int frequency, WordsPriorityQueue *queue) {
+    queue->push(frequency, word, length);
+}
+
+bool UnigramDictionary::isDigraph(const int *codes, const int i, const int codesSize) const {
 
     // There can't be a digraph if we don't have at least 2 characters to examine
     if (i + 2 > codesSize) return false;
@@ -86,9 +91,10 @@ bool UnigramDictionary::isDigraph(const int* codes, const int i, const int codes
 // codesSrc is the current point in the user-input, original, content-unmodified buffer.
 // codesRemain is the remaining size in codesSrc.
 void UnigramDictionary::getWordWithDigraphSuggestionsRec(ProximityInfo *proximityInfo,
-        const int *xcoordinates, const int* ycoordinates, const int *codesBuffer,
-        const int codesBufferSize, const int flags, const int* codesSrc, const int codesRemain,
-        const int currentDepth, int* codesDest, unsigned short* outWords, int* frequencies) {
+        const int *xcoordinates, const int *ycoordinates, const int *codesBuffer,
+        const int codesBufferSize, const int flags, const int *codesSrc,
+        const int codesRemain, const int currentDepth, int *codesDest, Correction *correction,
+        WordsPriorityQueuePool *queuePool) {
 
     if (currentDepth < MAX_UMLAUT_SEARCH_DEPTH) {
         for (int i = 0; i < codesRemain; ++i) {
@@ -105,8 +111,8 @@ void UnigramDictionary::getWordWithDigraphSuggestionsRec(ProximityInfo *proximit
                 getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates,
                         codesBuffer, codesBufferSize, flags,
                         codesSrc + (i + 1) * MAX_PROXIMITY_CHARS, codesRemain - i - 1,
-                        currentDepth + 1, codesDest + i * MAX_PROXIMITY_CHARS, outWords,
-                        frequencies);
+                        currentDepth + 1, codesDest + i * MAX_PROXIMITY_CHARS, correction,
+                        queuePool);
 
                 // Copy the second char of the digraph in place, then continue processing on
                 // the remaining part of the word.
@@ -114,9 +120,9 @@ void UnigramDictionary::getWordWithDigraphSuggestionsRec(ProximityInfo *proximit
                 memcpy(codesDest + i * MAX_PROXIMITY_CHARS, codesSrc + i * MAX_PROXIMITY_CHARS,
                         BYTES_IN_ONE_CHAR);
                 getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates,
-                        codesBuffer, codesBufferSize, flags, codesSrc + i * MAX_PROXIMITY_CHARS,
-                        codesRemain - i, currentDepth + 1, codesDest + i * MAX_PROXIMITY_CHARS,
-                        outWords, frequencies);
+                        codesBuffer, codesBufferSize, flags,
+                        codesSrc + i * MAX_PROXIMITY_CHARS, codesRemain - i, currentDepth + 1,
+                        codesDest + i * MAX_PROXIMITY_CHARS, correction, queuePool);
                 return;
             }
         }
@@ -132,40 +138,39 @@ void UnigramDictionary::getWordWithDigraphSuggestionsRec(ProximityInfo *proximit
         memcpy(codesDest, codesSrc, remainingBytes);
 
     getWordSuggestions(proximityInfo, xcoordinates, ycoordinates, codesBuffer,
-            (codesDest - codesBuffer) / MAX_PROXIMITY_CHARS + codesRemain, outWords, frequencies,
-            flags);
+            (codesDest - codesBuffer) / MAX_PROXIMITY_CHARS + codesRemain, flags, correction,
+            queuePool);
 }
 
-int UnigramDictionary::getSuggestions(ProximityInfo *proximityInfo, const int *xcoordinates,
+int UnigramDictionary::getSuggestions(ProximityInfo *proximityInfo,
+        WordsPriorityQueuePool *queuePool, Correction *correction, const int *xcoordinates,
         const int *ycoordinates, const int *codes, const int codesSize, const int flags,
         unsigned short *outWords, int *frequencies) {
 
+    Correction* masterCorrection = correction;
     if (REQUIRES_GERMAN_UMLAUT_PROCESSING & flags)
     { // Incrementally tune the word and try all possibilities
         int codesBuffer[getCodesBufferSize(codes, codesSize, MAX_PROXIMITY_CHARS)];
         getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, codesBuffer,
-                codesSize, flags, codes, codesSize, 0, codesBuffer, outWords, frequencies);
+                codesSize, flags, codes, codesSize, 0, codesBuffer, masterCorrection, queuePool);
     } else { // Normal processing
-        getWordSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, codesSize,
-                outWords, frequencies, flags);
+        getWordSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, codesSize, flags,
+                masterCorrection, queuePool);
     }
 
     PROF_START(20);
-    // Get the word count
-    int suggestedWordsCount = 0;
-    while (suggestedWordsCount < MAX_WORDS && mFrequencies[suggestedWordsCount] > 0) {
-        suggestedWordsCount++;
-    }
+    const int suggestedWordsCount =
+            queuePool->getMasterQueue()->outputSuggestions(frequencies, outWords);
 
     if (DEBUG_DICT) {
-        LOGI("Returning %d words", suggestedWordsCount);
+        AKLOGI("Returning %d words", suggestedWordsCount);
         /// Print the returned words
         for (int j = 0; j < suggestedWordsCount; ++j) {
 #ifdef FLAG_DBG
-            short unsigned int* w = mOutputChars + j * MAX_WORD_LENGTH;
+            short unsigned int* w = outWords + j * MAX_WORD_LENGTH;
             char s[MAX_WORD_LENGTH];
             for (int i = 0; i <= MAX_WORD_LENGTH; i++) s[i] = w[i];
-            LOGI("%s %i", s, mFrequencies[j]);
+            AKLOGI("%s %i", s, frequencies[j]);
 #endif
         }
     }
@@ -175,23 +180,19 @@ int UnigramDictionary::getSuggestions(ProximityInfo *proximityInfo, const int *x
 }
 
 void UnigramDictionary::getWordSuggestions(ProximityInfo *proximityInfo,
-        const int *xcoordinates, const int *ycoordinates, const int *codes, const int codesSize,
-        unsigned short *outWords, int *frequencies, const int flags) {
+        const int *xcoordinates, const int *ycoordinates, const int *codes,
+        const int inputLength, const int flags, Correction *correction,
+        WordsPriorityQueuePool *queuePool) {
 
     PROF_OPEN;
     PROF_START(0);
-    initSuggestions(
-            proximityInfo, xcoordinates, ycoordinates, codes, codesSize, outWords, frequencies);
-    if (DEBUG_DICT) assert(codesSize == mInputLength);
-
-    const int maxDepth = min(mInputLength * MAX_DEPTH_MULTIPLIER, MAX_WORD_LENGTH);
-    mCorrection->initCorrection(mProximityInfo, mInputLength, maxDepth);
+    queuePool->clearAll();
     PROF_END(0);
 
-    const bool useFullEditDistance = USE_FULL_EDIT_DISTANCE & flags;
-    // TODO: remove
     PROF_START(1);
-    getSuggestionCandidates(useFullEditDistance);
+    const bool useFullEditDistance = USE_FULL_EDIT_DISTANCE & flags;
+    getOneWordSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, useFullEditDistance,
+            inputLength, correction, queuePool);
     PROF_END(1);
 
     PROF_START(2);
@@ -209,12 +210,13 @@ void UnigramDictionary::getWordSuggestions(ProximityInfo *proximityInfo,
     PROF_START(5);
     // Suggestions with missing space
     if (SUGGEST_WORDS_WITH_MISSING_SPACE_CHARACTER
-            && mInputLength >= MIN_USER_TYPED_LENGTH_FOR_MISSING_SPACE_SUGGESTION) {
-        for (int i = 1; i < codesSize; ++i) {
+            && inputLength >= MIN_USER_TYPED_LENGTH_FOR_MISSING_SPACE_SUGGESTION) {
+        for (int i = 1; i < inputLength; ++i) {
             if (DEBUG_DICT) {
-                LOGI("--- Suggest missing space characters %d", i);
+                AKLOGI("--- Suggest missing space characters %d", i);
             }
-            getMissingSpaceWords(mInputLength, i, mCorrection, useFullEditDistance);
+            getMissingSpaceWords(proximityInfo, xcoordinates, ycoordinates, codes,
+                    useFullEditDistance, inputLength, i, correction, queuePool);
         }
     }
     PROF_END(5);
@@ -222,172 +224,297 @@ void UnigramDictionary::getWordSuggestions(ProximityInfo *proximityInfo,
     PROF_START(6);
     if (SUGGEST_WORDS_WITH_SPACE_PROXIMITY && proximityInfo) {
         // The first and last "mistyped spaces" are taken care of by excessive character handling
-        for (int i = 1; i < codesSize - 1; ++i) {
+        for (int i = 1; i < inputLength - 1; ++i) {
             if (DEBUG_DICT) {
-                LOGI("--- Suggest words with proximity space %d", i);
+                AKLOGI("--- Suggest words with proximity space %d", i);
             }
             const int x = xcoordinates[i];
             const int y = ycoordinates[i];
             if (DEBUG_PROXIMITY_INFO) {
-                LOGI("Input[%d] x = %d, y = %d, has space proximity = %d",
+                AKLOGI("Input[%d] x = %d, y = %d, has space proximity = %d",
                         i, x, y, proximityInfo->hasSpaceProximity(x, y));
             }
             if (proximityInfo->hasSpaceProximity(x, y)) {
-                getMistypedSpaceWords(mInputLength, i, mCorrection, useFullEditDistance);
+                getMistypedSpaceWords(proximityInfo, xcoordinates, ycoordinates, codes,
+                        useFullEditDistance, inputLength, i, correction, queuePool);
             }
         }
     }
     PROF_END(6);
-}
-
-void UnigramDictionary::initSuggestions(ProximityInfo *proximityInfo, const int *xCoordinates,
-        const int *yCoordinates, const int *codes, const int codesSize,
-        unsigned short *outWords, int *frequencies) {
     if (DEBUG_DICT) {
-        LOGI("initSuggest");
-    }
-    mFrequencies = frequencies;
-    mOutputChars = outWords;
-    mInputLength = codesSize;
-    proximityInfo->setInputParams(codes, codesSize, xCoordinates, yCoordinates);
-    mProximityInfo = proximityInfo;
-}
-
-static inline void registerNextLetter(unsigned short c, int *nextLetters, int nextLettersSize) {
-    if (c < nextLettersSize) {
-        nextLetters[c]++;
-    }
-}
-
-// TODO: We need to optimize addWord by using STL or something
-// TODO: This needs to take an const unsigned short* and not tinker with its contents
-bool UnigramDictionary::addWord(unsigned short *word, int length, int frequency) {
-    word[length] = 0;
-    if (DEBUG_DICT && DEBUG_SHOW_FOUND_WORD) {
-#ifdef FLAG_DBG
-        char s[length + 1];
-        for (int i = 0; i <= length; i++) s[i] = word[i];
-        LOGI("Found word = %s, freq = %d", s, frequency);
-#endif
-    }
-    if (length > MAX_WORD_LENGTH) {
-        if (DEBUG_DICT) {
-            LOGI("Exceeded max word length.");
+        queuePool->dumpSubQueue1TopSuggestions();
+        for (int i = 0; i < SUB_QUEUE_MAX_COUNT; ++i) {
+            WordsPriorityQueue* queue = queuePool->getSubQueue1(i);
+            if (queue->size() > 0) {
+                WordsPriorityQueue::SuggestedWord* sw = queue->top();
+                const int score = sw->mScore;
+                const unsigned short* word = sw->mWord;
+                const int wordLength = sw->mWordLength;
+                double ns = Correction::RankingAlgorithm::calcNormalizedScore(
+                        proximityInfo->getPrimaryInputWord(), i, word, wordLength, score);
+                ns += 0;
+                AKLOGI("--- TOP SUB WORDS for %d --- %d %f [%d]", i, score, ns,
+                        (ns > TWO_WORDS_CORRECTION_WITH_OTHER_ERROR_THRESHOLD));
+                DUMP_WORD(proximityInfo->getPrimaryInputWord(), i);
+                DUMP_WORD(word, wordLength);
+            }
         }
-        return false;
     }
+}
 
-    // Find the right insertion point
-    int insertAt = 0;
-    while (insertAt < MAX_WORDS) {
-        // TODO: How should we sort words with the same frequency?
-        if (frequency > mFrequencies[insertAt]) {
-            break;
-        }
-        insertAt++;
-    }
-    if (insertAt < MAX_WORDS) {
-        if (DEBUG_DICT) {
-#ifdef FLAG_DBG
-            char s[length + 1];
-            for (int i = 0; i <= length; i++) s[i] = word[i];
-            LOGI("Added word = %s, freq = %d, %d", s, frequency, S_INT_MAX);
-#endif
-        }
-        memmove((char*) mFrequencies + (insertAt + 1) * sizeof(mFrequencies[0]),
-               (char*) mFrequencies + insertAt * sizeof(mFrequencies[0]),
-               (MAX_WORDS - insertAt - 1) * sizeof(mFrequencies[0]));
-        mFrequencies[insertAt] = frequency;
-        memmove((char*) mOutputChars + (insertAt + 1) * MAX_WORD_LENGTH * sizeof(short),
-               (char*) mOutputChars + insertAt * MAX_WORD_LENGTH * sizeof(short),
-               (MAX_WORDS - insertAt - 1) * sizeof(short) * MAX_WORD_LENGTH);
-        unsigned short *dest = mOutputChars + insertAt * MAX_WORD_LENGTH;
-        while (length--) {
-            *dest++ = *word++;
-        }
-        *dest = 0; // NULL terminate
-        if (DEBUG_DICT) {
-            LOGI("Added word at %d", insertAt);
-        }
-        return true;
+void UnigramDictionary::initSuggestions(ProximityInfo *proximityInfo, const int *xCoordinates,
+        const int *yCoordinates, const int *codes, const int inputLength, Correction *correction) {
+    if (DEBUG_DICT) {
+        AKLOGI("initSuggest");
     }
-    return false;
+    proximityInfo->setInputParams(codes, inputLength, xCoordinates, yCoordinates);
+    const int maxDepth = min(inputLength * MAX_DEPTH_MULTIPLIER, MAX_WORD_LENGTH);
+    correction->initCorrection(proximityInfo, inputLength, maxDepth);
 }
 
 static const char QUOTE = '\'';
 static const char SPACE = ' ';
 
-void UnigramDictionary::getSuggestionCandidates(const bool useFullEditDistance) {
+void UnigramDictionary::getOneWordSuggestions(ProximityInfo *proximityInfo,
+        const int *xcoordinates, const int *ycoordinates, const int *codes,
+        const bool useFullEditDistance, const int inputLength, Correction *correction,
+        WordsPriorityQueuePool *queuePool) {
+    initSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, inputLength, correction);
+    getSuggestionCandidates(useFullEditDistance, inputLength, correction, queuePool,
+            true /* doAutoCompletion */, DEFAULT_MAX_ERRORS);
+}
+
+void UnigramDictionary::getSuggestionCandidates(const bool useFullEditDistance,
+        const int inputLength, Correction *correction, WordsPriorityQueuePool *queuePool,
+        const bool doAutoCompletion, const int maxErrors) {
     // TODO: Remove setCorrectionParams
-    mCorrection->setCorrectionParams(0, 0, 0,
-            -1 /* spaceProximityPos */, -1 /* missingSpacePos */, useFullEditDistance);
+    correction->setCorrectionParams(0, 0, 0,
+            -1 /* spaceProximityPos */, -1 /* missingSpacePos */, useFullEditDistance,
+            doAutoCompletion, maxErrors);
     int rootPosition = ROOT_POS;
     // Get the number of children of root, then increment the position
-    int childCount = Dictionary::getCount(DICT_ROOT, &rootPosition);
+    int childCount = BinaryFormat::getGroupCountAndForwardPointer(DICT_ROOT, &rootPosition);
     int outputIndex = 0;
 
-    mCorrection->initCorrectionState(rootPosition, childCount, (mInputLength <= 0));
+    correction->initCorrectionState(rootPosition, childCount, (inputLength <= 0));
 
     // Depth first search
     while (outputIndex >= 0) {
-        if (mCorrection->initProcessState(outputIndex)) {
-            int siblingPos = mCorrection->getTreeSiblingPos(outputIndex);
+        if (correction->initProcessState(outputIndex)) {
+            int siblingPos = correction->getTreeSiblingPos(outputIndex);
             int firstChildPos;
 
             const bool needsToTraverseChildrenNodes = processCurrentNode(siblingPos,
-                    mCorrection, &childCount, &firstChildPos, &siblingPos);
+                    correction, &childCount, &firstChildPos, &siblingPos, queuePool);
             // Update next sibling pos
-            mCorrection->setTreeSiblingPos(outputIndex, siblingPos);
+            correction->setTreeSiblingPos(outputIndex, siblingPos);
 
             if (needsToTraverseChildrenNodes) {
                 // Goes to child node
-                outputIndex = mCorrection->goDownTree(outputIndex, childCount, firstChildPos);
+                outputIndex = correction->goDownTree(outputIndex, childCount, firstChildPos);
             }
         } else {
             // Goes to parent sibling node
-            outputIndex = mCorrection->getTreeParentIndex(outputIndex);
+            outputIndex = correction->getTreeParentIndex(outputIndex);
         }
     }
 }
 
-void UnigramDictionary::getMissingSpaceWords(
+void UnigramDictionary::getMissingSpaceWords(ProximityInfo *proximityInfo, const int *xcoordinates,
+        const int *ycoordinates, const int *codes, const bool useFullEditDistance,
         const int inputLength, const int missingSpacePos, Correction *correction,
-        const bool useFullEditDistance) {
-    correction->setCorrectionParams(-1 /* skipPos */, -1 /* excessivePos */,
-            -1 /* transposedPos */, -1 /* spaceProximityPos */, missingSpacePos,
-            useFullEditDistance);
-    getSplitTwoWordsSuggestion(inputLength, correction);
+        WordsPriorityQueuePool* queuePool) {
+    getSplitTwoWordsSuggestions(proximityInfo, xcoordinates, ycoordinates, codes,
+            useFullEditDistance, inputLength, missingSpacePos, -1/* spaceProximityPos */,
+            correction, queuePool);
 }
 
-void UnigramDictionary::getMistypedSpaceWords(
+void UnigramDictionary::getMistypedSpaceWords(ProximityInfo *proximityInfo, const int *xcoordinates,
+        const int *ycoordinates, const int *codes, const bool useFullEditDistance,
         const int inputLength, const int spaceProximityPos, Correction *correction,
-        const bool useFullEditDistance) {
-    correction->setCorrectionParams(-1 /* skipPos */, -1 /* excessivePos */,
-            -1 /* transposedPos */, spaceProximityPos, -1 /* missingSpacePos */,
-            useFullEditDistance);
-    getSplitTwoWordsSuggestion(inputLength, correction);
+        WordsPriorityQueuePool* queuePool) {
+    getSplitTwoWordsSuggestions(proximityInfo, xcoordinates, ycoordinates, codes,
+            useFullEditDistance, inputLength, -1 /* missingSpacePos */, spaceProximityPos,
+            correction, queuePool);
 }
 
-inline bool UnigramDictionary::needsToSkipCurrentNode(const unsigned short c,
-        const int inputIndex, const int skipPos, const int depth) {
-    const unsigned short userTypedChar = mProximityInfo->getPrimaryCharAt(inputIndex);
-    // Skip the ' or other letter and continue deeper
-    return (c == QUOTE && userTypedChar != QUOTE) || skipPos == depth;
-}
+inline void UnigramDictionary::onTerminal(const int freq,
+        const TerminalAttributes& terminalAttributes, Correction *correction,
+        WordsPriorityQueuePool *queuePool, const bool addToMasterQueue) {
+    const int inputIndex = correction->getInputIndex();
+    const bool addToSubQueue = inputIndex < SUB_QUEUE_MAX_COUNT;
 
-inline void UnigramDictionary::onTerminal(const int freq, Correction *correction) {
     int wordLength;
     unsigned short* wordPointer;
-    const int finalFreq = correction->getFinalFreq(freq, &wordPointer, &wordLength);
-    if (finalFreq >= 0) {
-        addWord(wordPointer, wordLength, finalFreq);
+
+    if (addToMasterQueue) {
+        WordsPriorityQueue *masterQueue = queuePool->getMasterQueue();
+        const int finalFreq = correction->getFinalFreq(freq, &wordPointer, &wordLength);
+        if (finalFreq != NOT_A_FREQUENCY) {
+            if (!terminalAttributes.isShortcutOnly()) {
+                addWord(wordPointer, wordLength, finalFreq, masterQueue);
+            }
+
+            // Please note that the shortcut candidates will be added to the master queue only.
+            TerminalAttributes::ShortcutIterator iterator =
+                    terminalAttributes.getShortcutIterator();
+            while (iterator.hasNextShortcutTarget()) {
+                // TODO: addWord only supports weak ordering, meaning we have no means
+                // to control the order of the shortcuts relative to one another or to the word.
+                // We need to either modulate the frequency of each shortcut according
+                // to its own shortcut frequency or to make the queue
+                // so that the insert order is protected inside the queue for words
+                // with the same score.
+                uint16_t shortcutTarget[MAX_WORD_LENGTH_INTERNAL];
+                const int shortcutTargetStringLength = iterator.getNextShortcutTarget(
+                        MAX_WORD_LENGTH_INTERNAL, shortcutTarget);
+                addWord(shortcutTarget, shortcutTargetStringLength, finalFreq, masterQueue);
+            }
+        }
+    }
+
+    // We only allow two words + other error correction for words with SUB_QUEUE_MIN_WORD_LENGTH
+    // or more length.
+    if (inputIndex >= SUB_QUEUE_MIN_WORD_LENGTH && addToSubQueue) {
+        // TODO: Check the validity of "inputIndex == wordLength"
+        //if (addToSubQueue && inputIndex == wordLength) {
+        WordsPriorityQueue *subQueue = queuePool->getSubQueue1(inputIndex);
+        const int finalFreq = correction->getFinalFreqForSubQueue(freq, &wordPointer, &wordLength,
+                inputIndex);
+        addWord(wordPointer, wordLength, finalFreq, subQueue);
+    }
+}
+
+void UnigramDictionary::getSplitTwoWordsSuggestions(ProximityInfo *proximityInfo,
+        const int *xcoordinates, const int *ycoordinates, const int *codes,
+        const bool useFullEditDistance, const int inputLength, const int missingSpacePos,
+        const int  spaceProximityPos, Correction *correction, WordsPriorityQueuePool* queuePool) {
+    if (inputLength >= MAX_WORD_LENGTH) return;
+    if (DEBUG_DICT) {
+        int inputCount = 0;
+        if (spaceProximityPos >= 0) ++inputCount;
+        if (missingSpacePos >= 0) ++inputCount;
+        assert(inputCount <= 1);
+    }
+
+    WordsPriorityQueue *masterQueue = queuePool->getMasterQueue();
+
+    const bool isSpaceProximity = spaceProximityPos >= 0;
+
+    // First word
+    const int firstInputWordStartPos = 0;
+    const int firstInputWordLength = isSpaceProximity ? spaceProximityPos : missingSpacePos;
+    int firstFreq = getMostFrequentWordLike(
+            firstInputWordStartPos, firstInputWordLength, proximityInfo, mWord);
+    unsigned short* firstOutputWord = 0;
+    int firstOutputWordLength = 0;
+    if (firstFreq > 0) {
+        firstOutputWordLength = firstInputWordLength;
+        firstOutputWord = mWord;
+    } else {
+        if (masterQueue->size() > 0) {
+            double nsForMaster = masterQueue->getHighestNormalizedScore(
+                    proximityInfo->getPrimaryInputWord(), inputLength, 0, 0, 0);
+            if (nsForMaster > START_TWO_WORDS_CORRECTION_THRESHOLD) {
+                // Do nothing if the highest suggestion exceeds the threshold.
+                return;
+            }
+        }
+        WordsPriorityQueue* firstWordQueue = queuePool->getSubQueue1(firstInputWordLength);
+        if (firstWordQueue->size() < 1) {
+            return;
+        }
+        int score = 0;
+        const double ns = firstWordQueue->getHighestNormalizedScore(
+                proximityInfo->getPrimaryInputWord(), firstInputWordLength,
+                &firstOutputWord, &score, &firstOutputWordLength);
+        // Two words correction won't be done if the score of the first word doesn't exceed the
+        // threshold.
+        if (ns < TWO_WORDS_CORRECTION_WITH_OTHER_ERROR_THRESHOLD) {
+            return;
+        }
+        firstFreq = score >> (firstOutputWordLength
+                + TWO_WORDS_PLUS_OTHER_ERROR_CORRECTION_DEMOTION_DIVIDER);
+    }
+
+    if (DEBUG_DICT) {
+        AKLOGI("First freq: %d", firstFreq);
+    }
+
+    if (firstFreq <= 0 || firstOutputWordLength <= 0 || MAX_WORD_LENGTH <= firstOutputWordLength) {
+        return;
     }
+
+    // Allocating fixed length array on stack
+    unsigned short outputWord[MAX_WORD_LENGTH];
+    int outputWordLength = 0;
+
+    for (int i = 0; i < firstOutputWordLength; ++i) {
+        outputWord[i] = firstOutputWord[i];
+    }
+
+    outputWord[firstOutputWordLength] = SPACE;
+    outputWordLength = firstOutputWordLength + 1;
+
+    //const int outputWordLength = firstOutputWordLength + secondWordLength + 1;
+    // Space proximity preparation
+    //WordsPriorityQueue *subQueue = queuePool->getSubQueue1();
+    //initSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, firstOutputWordLength,
+    //subQueue, correction);
+    //getSuggestionCandidates(useFullEditDistance, firstOutputWordLength, correction, subQueue,
+    //false, MAX_ERRORS_FOR_TWO_WORDS);
+
+    // Second word
+    const int secondInputWordLength = isSpaceProximity
+            ? (inputLength - spaceProximityPos - 1)
+            : (inputLength - missingSpacePos);
+    const int secondInputWordStartPos =
+            isSpaceProximity ? (spaceProximityPos + 1) : missingSpacePos;
+    int secondFreq = getMostFrequentWordLike(
+            secondInputWordStartPos, secondInputWordLength, proximityInfo, mWord);
+    unsigned short* secondOutputWord = 0;
+    int secondOutputWordLength = 0;
+
+    if (secondFreq > 0) {
+        secondOutputWordLength = secondInputWordLength;
+        secondOutputWord = mWord;
+    }
+
+    if (DEBUG_DICT) {
+        AKLOGI("Second freq: %d", secondFreq);
+    }
+
+    if (secondFreq <= 0 || secondOutputWordLength <= 0
+            || MAX_WORD_LENGTH <= (firstOutputWordLength + 1 + secondOutputWordLength)) {
+        return;
+    }
+
+    for (int i = 0; i < secondOutputWordLength; ++i) {
+        outputWord[firstOutputWordLength + 1 + i] = secondOutputWord[i];
+    }
+
+    outputWordLength += secondOutputWordLength;
+
+    // TODO: Remove initSuggestions and correction->setCorrectionParams
+    initSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, inputLength, correction);
+
+    correction->setCorrectionParams(-1 /* skipPos */, -1 /* excessivePos */,
+            -1 /* transposedPos */, spaceProximityPos, missingSpacePos,
+            useFullEditDistance, false /* doAutoCompletion */, MAX_ERRORS_FOR_TWO_WORDS);
+    const int pairFreq = correction->getFreqForSplitTwoWords(firstFreq, secondFreq, outputWord);
+    if (DEBUG_DICT) {
+        AKLOGI("Split two words:  %d, %d, %d, %d", firstFreq, secondFreq, pairFreq, inputLength);
+    }
+    addWord(outputWord, outputWordLength, pairFreq, masterQueue);
+    return;
 }
 
-void UnigramDictionary::getSplitTwoWordsSuggestion(
-        const int inputLength, Correction* correction) {
-    const int spaceProximityPos = correction->getSpaceProximityPos();
-    const int missingSpacePos = correction->getMissingSpacePos();
+void UnigramDictionary::getSplitTwoWordsSuggestionsOld(ProximityInfo *proximityInfo,
+        const int *xcoordinates, const int *ycoordinates, const int *codes,
+        const bool useFullEditDistance, const int inputLength, const int missingSpacePos,
+        const int  spaceProximityPos, Correction *correction, WordsPriorityQueuePool* queuePool) {
+    WordsPriorityQueue *masterQueue = queuePool->getMasterQueue();
+
     if (DEBUG_DICT) {
         int inputCount = 0;
         if (spaceProximityPos >= 0) ++inputCount;
@@ -408,11 +535,21 @@ void UnigramDictionary::getSplitTwoWordsSuggestion(
         return;
 
     const int newWordLength = firstWordLength + secondWordLength + 1;
+
+
+    // Space proximity preparation
+    //WordsPriorityQueue *subQueue = queuePool->getSubQueue1();
+    //initSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, firstWordLength, subQueue,
+    //correction);
+    //getSuggestionCandidates(useFullEditDistance, firstWordLength, correction, subQueue, false,
+    //MAX_ERRORS_FOR_TWO_WORDS);
+
     // Allocating variable length array on stack
     unsigned short word[newWordLength];
-    const int firstFreq = getMostFrequentWordLike(firstWordStartPos, firstWordLength, mWord);
+    const int firstFreq = getMostFrequentWordLike(
+            firstWordStartPos, firstWordLength, proximityInfo, mWord);
     if (DEBUG_DICT) {
-        LOGI("First freq: %d", firstFreq);
+        AKLOGI("First freq: %d", firstFreq);
     }
     if (firstFreq <= 0) return;
 
@@ -420,9 +557,10 @@ void UnigramDictionary::getSplitTwoWordsSuggestion(
         word[i] = mWord[i];
     }
 
-    const int secondFreq = getMostFrequentWordLike(secondWordStartPos, secondWordLength, mWord);
+    const int secondFreq = getMostFrequentWordLike(
+            secondWordStartPos, secondWordLength, proximityInfo, mWord);
     if (DEBUG_DICT) {
-        LOGI("Second  freq:  %d", secondFreq);
+        AKLOGI("Second  freq:  %d", secondFreq);
     }
     if (secondFreq <= 0) return;
 
@@ -431,22 +569,28 @@ void UnigramDictionary::getSplitTwoWordsSuggestion(
         word[i] = mWord[i - firstWordLength - 1];
     }
 
-    const int pairFreq = mCorrection->getFreqForSplitTwoWords(firstFreq, secondFreq, word);
+    // TODO: Remove initSuggestions and correction->setCorrectionParams
+    initSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, inputLength, correction);
+
+    correction->setCorrectionParams(-1 /* skipPos */, -1 /* excessivePos */,
+            -1 /* transposedPos */, spaceProximityPos, missingSpacePos,
+            useFullEditDistance, false /* doAutoCompletion */, MAX_ERRORS_FOR_TWO_WORDS);
+    const int pairFreq = correction->getFreqForSplitTwoWords(firstFreq, secondFreq, word);
     if (DEBUG_DICT) {
-        LOGI("Split two words:  %d, %d, %d, %d", firstFreq, secondFreq, pairFreq, inputLength);
+        AKLOGI("Split two words:  %d, %d, %d, %d", firstFreq, secondFreq, pairFreq, inputLength);
     }
-    addWord(word, newWordLength, pairFreq);
+    addWord(word, newWordLength, pairFreq, masterQueue);
     return;
 }
 
 // Wrapper for getMostFrequentWordLikeInner, which matches it to the previous
 // interface.
 inline int UnigramDictionary::getMostFrequentWordLike(const int startInputIndex,
-        const int inputLength, unsigned short *word) {
+        const int inputLength, ProximityInfo *proximityInfo, unsigned short *word) {
     uint16_t inWord[inputLength];
 
     for (int i = 0; i < inputLength; ++i) {
-        inWord[i] = (uint16_t)mProximityInfo->getPrimaryCharAt(startInputIndex + i);
+        inWord[i] = (uint16_t)proximityInfo->getPrimaryCharAt(startInputIndex + i);
     }
     return getMostFrequentWordLikeInner(inWord, inputLength, word);
 }
@@ -470,8 +614,8 @@ static inline bool testCharGroupForContinuedLikeness(const uint8_t flags,
     const bool hasMultipleChars = (0 != (UnigramDictionary::FLAG_HAS_MULTIPLE_CHARS & flags));
     int pos = startPos;
     int32_t character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos);
-    int32_t baseChar = Dictionary::toBaseLowerCase(character);
-    const uint16_t wChar = Dictionary::toBaseLowerCase(inWord[startInputIndex]);
+    int32_t baseChar = toBaseLowerCase(character);
+    const uint16_t wChar = toBaseLowerCase(inWord[startInputIndex]);
 
     if (baseChar != wChar) {
         *outPos = hasMultipleChars ? BinaryFormat::skipOtherCharacters(root, pos) : pos;
@@ -483,8 +627,8 @@ static inline bool testCharGroupForContinuedLikeness(const uint8_t flags,
     if (hasMultipleChars) {
         character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos);
         while (NOT_A_CHARACTER != character) {
-            baseChar = Dictionary::toBaseLowerCase(character);
-            if (Dictionary::toBaseLowerCase(inWord[++inputIndex]) != baseChar) {
+            baseChar = toBaseLowerCase(character);
+            if (toBaseLowerCase(inWord[++inputIndex]) != baseChar) {
                 *outPos = BinaryFormat::skipOtherCharacters(root, pos);
                 *outInputIndex = startInputIndex;
                 return false;
@@ -521,9 +665,10 @@ int UnigramDictionary::getMostFrequentWordLikeInner(const uint16_t * const inWor
     int maxFreq = -1;
     const uint8_t* const root = DICT_ROOT;
 
-    mStackChildCount[0] = root[0];
+    int startPos = 0;
+    mStackChildCount[0] = BinaryFormat::getGroupCountAndForwardPointer(root, &startPos);
     mStackInputIndex[0] = 0;
-    mStackSiblingPos[0] = 1;
+    mStackSiblingPos[0] = startPos;
     while (depth >= 0) {
         const int charGroupCount = mStackChildCount[depth];
         int pos = mStackSiblingPos[depth];
@@ -597,7 +742,7 @@ int UnigramDictionary::getBigramPosition(int pos, unsigned short *word, int offs
 // given level, as output into newCount when traversing this level's parent.
 inline bool UnigramDictionary::processCurrentNode(const int initialPos,
         Correction *correction, int *newCount,
-        int *newChildrenPosition, int *nextSiblingPosition) {
+        int *newChildrenPosition, int *nextSiblingPosition, WordsPriorityQueuePool *queuePool) {
     if (DEBUG_DICT) {
         correction->checkState();
     }
@@ -648,7 +793,7 @@ inline bool UnigramDictionary::processCurrentNode(const int initialPos,
         if (stateType == Correction::TRAVERSE_ALL_ON_TERMINAL
                 || stateType == Correction::ON_TERMINAL) {
             needsToInvokeOnTerminal = true;
-        } else if (stateType == Correction::UNRELATED) {
+        } else if (stateType == Correction::UNRELATED || correction->needsToPrune()) {
             // We found that this is an unrelated character, so we should give up traversing
             // this node and its children entirely.
             // However we may not be on the last virtual node yet so we skip the remaining
@@ -672,12 +817,13 @@ inline bool UnigramDictionary::processCurrentNode(const int initialPos,
     } while (NOT_A_CHARACTER != c);
 
     if (isTerminalNode) {
-        if (needsToInvokeOnTerminal) {
-            // The frequency should be here, because we come here only if this is actually
-            // a terminal node, and we are on its last char.
-            const int freq = BinaryFormat::readFrequencyWithoutMovingPointer(DICT_ROOT, pos);
-            onTerminal(freq, mCorrection);
-        }
+        // The frequency should be here, because we come here only if this is actually
+        // a terminal node, and we are on its last char.
+        const int freq = BinaryFormat::readFrequencyWithoutMovingPointer(DICT_ROOT, pos);
+        const int childrenAddressPos = BinaryFormat::skipFrequency(flags, pos);
+        const int attributesPos = BinaryFormat::skipChildrenPosition(flags, childrenAddressPos);
+        TerminalAttributes terminalAttributes(DICT_ROOT, flags, attributesPos);
+        onTerminal(freq, terminalAttributes, correction, queuePool, needsToInvokeOnTerminal);
 
         // If there are more chars in this node, then this virtual node has children.
         // If we are on the last char, this virtual node has children if this node has.
@@ -702,7 +848,7 @@ inline bool UnigramDictionary::processCurrentNode(const int initialPos,
             *nextSiblingPosition =
                     BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos);
             if (DEBUG_DICT_FULL) {
-                LOGI("Traversing was pruned.");
+                AKLOGI("Traversing was pruned.");
             }
             return false;
         }