Add spellcheck and word suggestion to the prediction service

third_party/android_prediction/suggest/policyimpl/dictionary/structure/pt_common/dynamic_pt_reading_helper.h

Index: third_party/android_prediction/suggest/policyimpl/dictionary/structure/pt_common/dynamic_pt_reading_helper.h
diff --git a/third_party/android_prediction/suggest/policyimpl/dictionary/structure/pt_common/dynamic_pt_reading_helper.h b/third_party/android_prediction/suggest/policyimpl/dictionary/structure/pt_common/dynamic_pt_reading_helper.h
new file mode 100644
index 0000000000000000000000000000000000000000..c6a609198ea6de5ad26c67e6e301c114c2878686
--- /dev/null
+++ b/third_party/android_prediction/suggest/policyimpl/dictionary/structure/pt_common/dynamic_pt_reading_helper.h
@@ -0,0 +1,283 @@
+/*
+ * 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_DYNAMIC_PT_READING_HELPER_H
+#define LATINIME_DYNAMIC_PT_READING_HELPER_H
+
+#include <cstddef>
+#include <vector>
+
+#include "third_party/android_prediction/defines.h"
+#include "third_party/android_prediction/suggest/policyimpl/dictionary/structure/pt_common/pt_node_params.h"
+#include "third_party/android_prediction/suggest/policyimpl/dictionary/structure/pt_common/pt_node_reader.h"
+
+namespace latinime {
+
+class DictionaryShortcutsStructurePolicy;
+class PtNodeArrayReader;
+
+/*
+ * This class is used for traversing dynamic patricia trie. This class supports iterating nodes and
+ * dealing with additional buffer. This class counts nodes and node arrays to avoid infinite loop.
+ */
+class DynamicPtReadingHelper {
+ public:
+    class TraversingEventListener {
+     public:
+        virtual ~TraversingEventListener() {};
+
+        // Returns whether the event handling was succeeded or not.
+        virtual bool onAscend() = 0;
+
+        // Returns whether the event handling was succeeded or not.
+        virtual bool onDescend(const int ptNodeArrayPos) = 0;
+
+        // Returns whether the event handling was succeeded or not.
+        virtual bool onReadingPtNodeArrayTail() = 0;
+
+        // Returns whether the event handling was succeeded or not.
+        virtual bool onVisitingPtNode(const PtNodeParams *const node) = 0;
+
+     protected:
+        TraversingEventListener() {};
+
+     private:
+        DISALLOW_COPY_AND_ASSIGN(TraversingEventListener);
+    };
+
+    class TraversePolicyToGetAllTerminalPtNodePositions : public TraversingEventListener {
+     public:
+        TraversePolicyToGetAllTerminalPtNodePositions(std::vector<int> *const terminalPositions)
+                : mTerminalPositions(terminalPositions) {}
+        bool onAscend() { return true; }
+        bool onDescend(const int ptNodeArrayPos) { return true; }
+        bool onReadingPtNodeArrayTail() { return true; }
+        bool onVisitingPtNode(const PtNodeParams *const ptNodeParams);
+
+     private:
+        DISALLOW_IMPLICIT_CONSTRUCTORS(TraversePolicyToGetAllTerminalPtNodePositions);
+
+        std::vector<int> *const mTerminalPositions;
+    };
+
+    DynamicPtReadingHelper(const PtNodeReader *const ptNodeReader,
+            const PtNodeArrayReader *const ptNodeArrayReader)
+            : mIsError(false), mReadingState(), mPtNodeReader(ptNodeReader),
+              mPtNodeArrayReader(ptNodeArrayReader), mReadingStateStack() {}
+
+    ~DynamicPtReadingHelper() {}
+
+    AK_FORCE_INLINE bool isError() const {
+        return mIsError;
+    }
+
+    AK_FORCE_INLINE bool isEnd() const {
+        return mReadingState.mPos == NOT_A_DICT_POS;
+    }
+
+    // Initialize reading state with the head position of a PtNode array.
+    AK_FORCE_INLINE void initWithPtNodeArrayPos(const int ptNodeArrayPos) {
+        if (ptNodeArrayPos == NOT_A_DICT_POS) {
+            mReadingState.mPos = NOT_A_DICT_POS;
+        } else {
+            mIsError = false;
+            mReadingState.mPos = ptNodeArrayPos;
+            mReadingState.mTotalCodePointCountSinceInitialization = 0;
+            mReadingState.mTotalPtNodeIndexInThisArrayChain = 0;
+            mReadingState.mPtNodeArrayIndexInThisArrayChain = 0;
+            mReadingState.mPosOfLastForwardLinkField = NOT_A_DICT_POS;
+            mReadingStateStack.clear();
+            nextPtNodeArray();
+        }
+    }
+
+    // Initialize reading state with the head position of a node.
+    AK_FORCE_INLINE void initWithPtNodePos(const int ptNodePos) {
+        if (ptNodePos == NOT_A_DICT_POS) {
+            mReadingState.mPos = NOT_A_DICT_POS;
+        } else {
+            mIsError = false;
+            mReadingState.mPos = ptNodePos;
+            mReadingState.mRemainingPtNodeCountInThisArray = 1;
+            mReadingState.mTotalCodePointCountSinceInitialization = 0;
+            mReadingState.mTotalPtNodeIndexInThisArrayChain = 1;
+            mReadingState.mPtNodeArrayIndexInThisArrayChain = 1;
+            mReadingState.mPosOfLastForwardLinkField = NOT_A_DICT_POS;
+            mReadingState.mPosOfThisPtNodeArrayHead = NOT_A_DICT_POS;
+            mReadingStateStack.clear();
+        }
+    }
+
+    AK_FORCE_INLINE const PtNodeParams getPtNodeParams() const {
+        if (isEnd()) {
+            return PtNodeParams();
+        }
+        return mPtNodeReader->fetchPtNodeParamsInBufferFromPtNodePos(mReadingState.mPos);
+    }
+
+    AK_FORCE_INLINE bool isValidTerminalNode(const PtNodeParams &ptNodeParams) const {
+        return !isEnd() && !ptNodeParams.isDeleted() && ptNodeParams.isTerminal();
+    }
+
+    AK_FORCE_INLINE bool isMatchedCodePoint(const PtNodeParams &ptNodeParams, const int index,
+            const int codePoint) const {
+        return ptNodeParams.getCodePoints()[index] == codePoint;
+    }
+
+    // Return code point count exclude the last read node's code points.
+    AK_FORCE_INLINE int getPrevTotalCodePointCount() const {
+        return mReadingState.mTotalCodePointCountSinceInitialization;
+    }
+
+    // Return code point count include the last read node's code points.
+    AK_FORCE_INLINE int getTotalCodePointCount(const PtNodeParams &ptNodeParams) const {
+        return mReadingState.mTotalCodePointCountSinceInitialization
+                + ptNodeParams.getCodePointCount();
+    }
+
+    AK_FORCE_INLINE void fetchMergedNodeCodePointsInReverseOrder(const PtNodeParams &ptNodeParams,
+            const int index, int *const outCodePoints) const {
+        const int nodeCodePointCount = ptNodeParams.getCodePointCount();
+        const int *const nodeCodePoints = ptNodeParams.getCodePoints();
+        for (int i =  0; i < nodeCodePointCount; ++i) {
+            outCodePoints[index + i] = nodeCodePoints[nodeCodePointCount - 1 - i];
+        }
+    }
+
+    AK_FORCE_INLINE void readNextSiblingNode(const PtNodeParams &ptNodeParams) {
+        mReadingState.mRemainingPtNodeCountInThisArray -= 1;
+        mReadingState.mPos = ptNodeParams.getSiblingNodePos();
+        if (mReadingState.mRemainingPtNodeCountInThisArray <= 0) {
+            // All nodes in the current node array have been read.
+            followForwardLink();
+        }
+    }
+
+    // Read the first child node of the current node.
+    AK_FORCE_INLINE void readChildNode(const PtNodeParams &ptNodeParams) {
+        if (ptNodeParams.hasChildren()) {
+            mReadingState.mTotalCodePointCountSinceInitialization +=
+                    ptNodeParams.getCodePointCount();
+            mReadingState.mTotalPtNodeIndexInThisArrayChain = 0;
+            mReadingState.mPtNodeArrayIndexInThisArrayChain = 0;
+            mReadingState.mPos = ptNodeParams.getChildrenPos();
+            mReadingState.mPosOfLastForwardLinkField = NOT_A_DICT_POS;
+            // Read children node array.
+            nextPtNodeArray();
+        } else {
+            mReadingState.mPos = NOT_A_DICT_POS;
+        }
+    }
+
+    // Read the parent node of the current node.
+    AK_FORCE_INLINE void readParentNode(const PtNodeParams &ptNodeParams) {
+        if (ptNodeParams.getParentPos() != NOT_A_DICT_POS) {
+            mReadingState.mTotalCodePointCountSinceInitialization +=
+                    ptNodeParams.getCodePointCount();
+            mReadingState.mTotalPtNodeIndexInThisArrayChain = 1;
+            mReadingState.mPtNodeArrayIndexInThisArrayChain = 1;
+            mReadingState.mRemainingPtNodeCountInThisArray = 1;
+            mReadingState.mPos = ptNodeParams.getParentPos();
+            mReadingState.mPosOfLastForwardLinkField = NOT_A_DICT_POS;
+            mReadingState.mPosOfThisPtNodeArrayHead = NOT_A_DICT_POS;
+        } else {
+            mReadingState.mPos = NOT_A_DICT_POS;
+        }
+    }
+
+    AK_FORCE_INLINE int getPosOfLastForwardLinkField() const {
+        return mReadingState.mPosOfLastForwardLinkField;
+    }
+
+    AK_FORCE_INLINE int getPosOfLastPtNodeArrayHead() const {
+        return mReadingState.mPosOfThisPtNodeArrayHead;
+    }
+
+    bool traverseAllPtNodesInPostorderDepthFirstManner(TraversingEventListener *const listener);
+
+    bool traverseAllPtNodesInPtNodeArrayLevelPreorderDepthFirstManner(
+            TraversingEventListener *const listener);
+
+    int getCodePointsAndProbabilityAndReturnCodePointCount(const int maxCodePointCount,
+            int *const outCodePoints, int *const outUnigramProbability);
+
+    int getTerminalPtNodePositionOfWord(const int *const inWord, const int length,
+            const bool forceLowerCaseSearch);
+
+ private:
+    DISALLOW_COPY_AND_ASSIGN(DynamicPtReadingHelper);
+
+    // This class encapsulates the reading state of a position in the dictionary. It points at a
+    // specific PtNode in the dictionary.
+    class PtNodeReadingState {
+     public:
+        // Note that copy constructor and assignment operator are used for this class to use
+        // std::vector.
+        PtNodeReadingState() : mPos(NOT_A_DICT_POS), mRemainingPtNodeCountInThisArray(0),
+                mTotalCodePointCountSinceInitialization(0), mTotalPtNodeIndexInThisArrayChain(0),
+                mPtNodeArrayIndexInThisArrayChain(0), mPosOfLastForwardLinkField(NOT_A_DICT_POS),
+                mPosOfThisPtNodeArrayHead(NOT_A_DICT_POS) {}
+
+        int mPos;
+        // Remaining node count in the current array.
+        int mRemainingPtNodeCountInThisArray;
+        int mTotalCodePointCountSinceInitialization;
+        // Counter of PtNodes used to avoid infinite loops caused by broken or malicious links.
+        int mTotalPtNodeIndexInThisArrayChain;
+        // Counter of PtNode arrays used to avoid infinite loops caused by cyclic links of empty
+        // PtNode arrays.
+        int mPtNodeArrayIndexInThisArrayChain;
+        int mPosOfLastForwardLinkField;
+        int mPosOfThisPtNodeArrayHead;
+    };
+
+    static const int MAX_CHILD_COUNT_TO_AVOID_INFINITE_LOOP;
+    static const int MAX_PT_NODE_ARRAY_COUNT_TO_AVOID_INFINITE_LOOP;
+    static const size_t MAX_READING_STATE_STACK_SIZE;
+
+    // TODO: Introduce error code to track what caused the error.
+    bool mIsError;
+    PtNodeReadingState mReadingState;
+    const PtNodeReader *const mPtNodeReader;
+    const PtNodeArrayReader *const mPtNodeArrayReader;
+    std::vector<PtNodeReadingState> mReadingStateStack;
+
+    void nextPtNodeArray();
+
+    void followForwardLink();
+
+    AK_FORCE_INLINE void pushReadingStateToStack() {
+        if (mReadingStateStack.size() > MAX_READING_STATE_STACK_SIZE) {
+            AKLOGI("Reading state stack overflow. Max size: %zd", MAX_READING_STATE_STACK_SIZE);
+            ASSERT(false);
+            mIsError = true;
+            mReadingState.mPos = NOT_A_DICT_POS;
+        } else {
+            mReadingStateStack.push_back(mReadingState);
+        }
+    }
+
+    AK_FORCE_INLINE void popReadingStateFromStack() {
+        if (mReadingStateStack.empty()) {
+            mReadingState.mPos = NOT_A_DICT_POS;
+        } else {
+            mReadingState = mReadingStateStack.back();
+            mReadingStateStack.pop_back();
+        }
+    }
+};
+} // namespace latinime
+#endif /* LATINIME_DYNAMIC_PT_READING_HELPER_H */