Home | History | Annotate | Download | only in dictionary 
      1 /*
      2  * Copyright (C) 2013, The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *     http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #ifndef LATINIME_DYNAMIC_PATRICIA_TRIE_READING_HELPER_H
     18 #define LATINIME_DYNAMIC_PATRICIA_TRIE_READING_HELPER_H
     19 
     20 #include <cstddef>
     21 #include <vector>
     22 
     23 #include "defines.h"
     24 #include "suggest/policyimpl/dictionary/dynamic_patricia_trie_node_reader.h"
     25 #include "suggest/policyimpl/dictionary/dynamic_patricia_trie_reading_utils.h"
     26 #include "suggest/policyimpl/dictionary/patricia_trie_reading_utils.h"
     27 
     28 namespace latinime {
     29 
     30 class BufferWithExtendableBuffer;
     31 class DictionaryBigramsStructurePolicy;
     32 class DictionaryShortcutsStructurePolicy;
     33 
     34 /*
     35  * This class is used for traversing dynamic patricia trie. This class supports iterating nodes and
     36  * dealing with additional buffer. This class counts nodes and node arrays to avoid infinite loop.
     37  */
     38 class DynamicPatriciaTrieReadingHelper {
     39  public:
     40     class TraversingEventListener {
     41      public:
     42         virtual ~TraversingEventListener() {};
     43 
     44         // Returns whether the event handling was succeeded or not.
     45         virtual bool onAscend() = 0;
     46 
     47         // Returns whether the event handling was succeeded or not.
     48         virtual bool onDescend(const int ptNodeArrayPos) = 0;
     49 
     50         // Returns whether the event handling was succeeded or not.
     51         virtual bool onReadingPtNodeArrayTail() = 0;
     52 
     53         // Returns whether the event handling was succeeded or not.
     54         virtual bool onVisitingPtNode(const DynamicPatriciaTrieNodeReader *const node,
     55                 const int *const nodeCodePoints) = 0;
     56 
     57      protected:
     58         TraversingEventListener() {};
     59 
     60      private:
     61         DISALLOW_COPY_AND_ASSIGN(TraversingEventListener);
     62     };
     63 
     64     DynamicPatriciaTrieReadingHelper(const BufferWithExtendableBuffer *const buffer,
     65             const DictionaryBigramsStructurePolicy *const bigramsPolicy,
     66             const DictionaryShortcutsStructurePolicy *const shortcutsPolicy)
     67             : mIsError(false), mReadingState(), mBuffer(buffer),
     68               mNodeReader(mBuffer, bigramsPolicy, shortcutsPolicy), mReadingStateStack() {}
     69 
     70     ~DynamicPatriciaTrieReadingHelper() {}
     71 
     72     AK_FORCE_INLINE bool isError() const {
     73         return mIsError;
     74     }
     75 
     76     AK_FORCE_INLINE bool isEnd() const {
     77         return mReadingState.mPos == NOT_A_DICT_POS;
     78     }
     79 
     80     // Initialize reading state with the head position of a PtNode array.
     81     AK_FORCE_INLINE void initWithPtNodeArrayPos(const int ptNodeArrayPos) {
     82         if (ptNodeArrayPos == NOT_A_DICT_POS) {
     83             mReadingState.mPos = NOT_A_DICT_POS;
     84         } else {
     85             mIsError = false;
     86             mReadingState.mPos = ptNodeArrayPos;
     87             mReadingState.mPrevTotalCodePointCount = 0;
     88             mReadingState.mTotalNodeCount = 0;
     89             mReadingState.mNodeArrayCount = 0;
     90             mReadingState.mPosOfLastForwardLinkField = NOT_A_DICT_POS;
     91             mReadingStateStack.clear();
     92             nextPtNodeArray();
     93             if (!isEnd()) {
     94                 fetchPtNodeInfo();
     95             }
     96         }
     97     }
     98 
     99     // Initialize reading state with the head position of a node.
    100     AK_FORCE_INLINE void initWithPtNodePos(const int ptNodePos) {
    101         if (ptNodePos == NOT_A_DICT_POS) {
    102             mReadingState.mPos = NOT_A_DICT_POS;
    103         } else {
    104             mIsError = false;
    105             mReadingState.mPos = ptNodePos;
    106             mReadingState.mNodeCount = 1;
    107             mReadingState.mPrevTotalCodePointCount = 0;
    108             mReadingState.mTotalNodeCount = 1;
    109             mReadingState.mNodeArrayCount = 1;
    110             mReadingState.mPosOfLastForwardLinkField = NOT_A_DICT_POS;
    111             mReadingState.mPosOfLastPtNodeArrayHead = NOT_A_DICT_POS;
    112             mReadingStateStack.clear();
    113             fetchPtNodeInfo();
    114         }
    115     }
    116 
    117     AK_FORCE_INLINE const DynamicPatriciaTrieNodeReader* getNodeReader() const {
    118         return &mNodeReader;
    119     }
    120 
    121     AK_FORCE_INLINE bool isValidTerminalNode() const {
    122         return !isEnd() && !mNodeReader.isDeleted() && mNodeReader.isTerminal();
    123     }
    124 
    125     AK_FORCE_INLINE bool isMatchedCodePoint(const int index, const int codePoint) const {
    126         return mMergedNodeCodePoints[index] == codePoint;
    127     }
    128 
    129     // Return code point count exclude the last read node's code points.
    130     AK_FORCE_INLINE int getPrevTotalCodePointCount() const {
    131         return mReadingState.mPrevTotalCodePointCount;
    132     }
    133 
    134     // Return code point count include the last read node's code points.
    135     AK_FORCE_INLINE int getTotalCodePointCount() const {
    136         return mReadingState.mPrevTotalCodePointCount + mNodeReader.getCodePointCount();
    137     }
    138 
    139     AK_FORCE_INLINE void fetchMergedNodeCodePointsInReverseOrder(
    140             const int index, int *const outCodePoints) const {
    141         const int nodeCodePointCount = mNodeReader.getCodePointCount();
    142         for (int i =  0; i < nodeCodePointCount; ++i) {
    143             outCodePoints[index + i] = mMergedNodeCodePoints[nodeCodePointCount - 1 - i];
    144         }
    145     }
    146 
    147     AK_FORCE_INLINE const int *getMergedNodeCodePoints() const {
    148         return mMergedNodeCodePoints;
    149     }
    150 
    151     AK_FORCE_INLINE void readNextSiblingNode() {
    152         mReadingState.mNodeCount -= 1;
    153         mReadingState.mPos = mNodeReader.getSiblingNodePos();
    154         if (mReadingState.mNodeCount <= 0) {
    155             // All nodes in the current node array have been read.
    156             followForwardLink();
    157             if (!isEnd()) {
    158                 fetchPtNodeInfo();
    159             }
    160         } else {
    161             fetchPtNodeInfo();
    162         }
    163     }
    164 
    165     // Read the first child node of the current node.
    166     AK_FORCE_INLINE void readChildNode() {
    167         if (mNodeReader.hasChildren()) {
    168             mReadingState.mPrevTotalCodePointCount += mNodeReader.getCodePointCount();
    169             mReadingState.mTotalNodeCount = 0;
    170             mReadingState.mNodeArrayCount = 0;
    171             mReadingState.mPos = mNodeReader.getChildrenPos();
    172             mReadingState.mPosOfLastForwardLinkField = NOT_A_DICT_POS;
    173             // Read children node array.
    174             nextPtNodeArray();
    175             if (!isEnd()) {
    176                 fetchPtNodeInfo();
    177             }
    178         } else {
    179             mReadingState.mPos = NOT_A_DICT_POS;
    180         }
    181     }
    182 
    183     // Read the parent node of the current node.
    184     AK_FORCE_INLINE void readParentNode() {
    185         if (mNodeReader.getParentPos() != NOT_A_DICT_POS) {
    186             mReadingState.mPrevTotalCodePointCount += mNodeReader.getCodePointCount();
    187             mReadingState.mTotalNodeCount = 1;
    188             mReadingState.mNodeArrayCount = 1;
    189             mReadingState.mNodeCount = 1;
    190             mReadingState.mPos = mNodeReader.getParentPos();
    191             mReadingState.mPosOfLastForwardLinkField = NOT_A_DICT_POS;
    192             mReadingState.mPosOfLastPtNodeArrayHead = NOT_A_DICT_POS;
    193             fetchPtNodeInfo();
    194         } else {
    195             mReadingState.mPos = NOT_A_DICT_POS;
    196         }
    197     }
    198 
    199     AK_FORCE_INLINE int getPosOfLastForwardLinkField() const {
    200         return mReadingState.mPosOfLastForwardLinkField;
    201     }
    202 
    203     AK_FORCE_INLINE int getPosOfLastPtNodeArrayHead() const {
    204         return mReadingState.mPosOfLastPtNodeArrayHead;
    205     }
    206 
    207     AK_FORCE_INLINE void reloadCurrentPtNodeInfo() {
    208         if (!isEnd()) {
    209             fetchPtNodeInfo();
    210         }
    211     }
    212 
    213     bool traverseAllPtNodesInPostorderDepthFirstManner(TraversingEventListener *const listener);
    214 
    215     bool traverseAllPtNodesInPtNodeArrayLevelPreorderDepthFirstManner(
    216             TraversingEventListener *const listener);
    217 
    218  private:
    219     DISALLOW_COPY_AND_ASSIGN(DynamicPatriciaTrieReadingHelper);
    220 
    221     class ReadingState {
    222      public:
    223         // Note that copy constructor and assignment operator are used for this class to use
    224         // std::vector.
    225         ReadingState() : mPos(NOT_A_DICT_POS), mNodeCount(0), mPrevTotalCodePointCount(0),
    226                 mTotalNodeCount(0), mNodeArrayCount(0), mPosOfLastForwardLinkField(NOT_A_DICT_POS),
    227                 mPosOfLastPtNodeArrayHead(NOT_A_DICT_POS) {}
    228 
    229         int mPos;
    230         // Node count of a node array.
    231         int mNodeCount;
    232         int mPrevTotalCodePointCount;
    233         int mTotalNodeCount;
    234         int mNodeArrayCount;
    235         int mPosOfLastForwardLinkField;
    236         int mPosOfLastPtNodeArrayHead;
    237     };
    238 
    239     static const int MAX_CHILD_COUNT_TO_AVOID_INFINITE_LOOP;
    240     static const int MAX_NODE_ARRAY_COUNT_TO_AVOID_INFINITE_LOOP;
    241     static const size_t MAX_READING_STATE_STACK_SIZE;
    242 
    243     // TODO: Introduce error code to track what caused the error.
    244     bool mIsError;
    245     ReadingState mReadingState;
    246     const BufferWithExtendableBuffer *const mBuffer;
    247     DynamicPatriciaTrieNodeReader mNodeReader;
    248     int mMergedNodeCodePoints[MAX_WORD_LENGTH];
    249     std::vector<ReadingState> mReadingStateStack;
    250 
    251     void nextPtNodeArray();
    252 
    253     void followForwardLink();
    254 
    255     AK_FORCE_INLINE void fetchPtNodeInfo() {
    256         mNodeReader.fetchNodeInfoInBufferFromPtNodePosAndGetNodeCodePoints(mReadingState.mPos,
    257                 MAX_WORD_LENGTH, mMergedNodeCodePoints);
    258         if (mNodeReader.getCodePointCount() <= 0) {
    259             // Empty node is not allowed.
    260             mIsError = true;
    261             mReadingState.mPos = NOT_A_DICT_POS;
    262         }
    263     }
    264 
    265     AK_FORCE_INLINE void pushReadingStateToStack() {
    266         if (mReadingStateStack.size() > MAX_READING_STATE_STACK_SIZE) {
    267             AKLOGI("Reading state stack overflow. Max size: %zd", MAX_READING_STATE_STACK_SIZE);
    268             ASSERT(false);
    269             mIsError = true;
    270             mReadingState.mPos = NOT_A_DICT_POS;
    271         } else {
    272             mReadingStateStack.push_back(mReadingState);
    273         }
    274     }
    275 
    276     AK_FORCE_INLINE void popReadingStateFromStack() {
    277         if (mReadingStateStack.empty()) {
    278             mReadingState.mPos = NOT_A_DICT_POS;
    279         } else {
    280             mReadingState = mReadingStateStack.back();
    281             mReadingStateStack.pop_back();
    282             if (!isEnd()) {
    283                 fetchPtNodeInfo();
    284             }
    285         }
    286     }
    287 };
    288 } // namespace latinime
    289 #endif /* LATINIME_DYNAMIC_PATRICIA_TRIE_READING_HELPER_H */
    290