1 /* 2 * Copyright (C) 2011 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_WORDS_PRIORITY_QUEUE_H 18 #define LATINIME_WORDS_PRIORITY_QUEUE_H 19 20 #include <cstring> // for memcpy() 21 #include <queue> 22 23 #include "correction.h" 24 #include "defines.h" 25 26 namespace latinime { 27 28 class WordsPriorityQueue { 29 public: 30 struct SuggestedWord { 31 int mScore; 32 int mWord[MAX_WORD_LENGTH]; 33 int mWordLength; 34 bool mUsed; 35 int mType; 36 37 void setParams(int score, int *word, int wordLength, int type) { 38 mScore = score; 39 mWordLength = wordLength; 40 memcpy(mWord, word, sizeof(mWord[0]) * wordLength); 41 mUsed = true; 42 mType = type; 43 } 44 }; 45 46 WordsPriorityQueue(int maxWords) 47 : mSuggestions(), MAX_WORDS(maxWords), 48 mSuggestedWords(new SuggestedWord[MAX_WORD_LENGTH]), mHighestSuggestedWord(0) { 49 for (int i = 0; i < MAX_WORD_LENGTH; ++i) { 50 mSuggestedWords[i].mUsed = false; 51 } 52 } 53 54 // Non virtual inline destructor -- never inherit this class 55 AK_FORCE_INLINE ~WordsPriorityQueue() { 56 delete[] mSuggestedWords; 57 } 58 59 void push(int score, int *word, int wordLength, int type) { 60 SuggestedWord *sw = 0; 61 if (size() >= MAX_WORDS) { 62 sw = mSuggestions.top(); 63 const int minScore = sw->mScore; 64 if (minScore >= score) { 65 return; 66 } 67 sw->mUsed = false; 68 mSuggestions.pop(); 69 } 70 if (sw == 0) { 71 sw = getFreeSuggestedWord(score, word, wordLength, type); 72 } else { 73 sw->setParams(score, word, wordLength, type); 74 } 75 if (sw == 0) { 76 AKLOGE("SuggestedWord is accidentally null."); 77 return; 78 } 79 if (DEBUG_WORDS_PRIORITY_QUEUE) { 80 AKLOGI("Push word. %d, %d", score, wordLength); 81 DUMP_WORD(word, wordLength); 82 } 83 mSuggestions.push(sw); 84 if (!mHighestSuggestedWord || mHighestSuggestedWord->mScore < sw->mScore) { 85 mHighestSuggestedWord = sw; 86 } 87 } 88 89 SuggestedWord *top() const { 90 if (mSuggestions.empty()) return 0; 91 SuggestedWord *sw = mSuggestions.top(); 92 return sw; 93 } 94 95 int size() const { 96 return static_cast<int>(mSuggestions.size()); 97 } 98 99 AK_FORCE_INLINE void clear() { 100 mHighestSuggestedWord = 0; 101 while (!mSuggestions.empty()) { 102 SuggestedWord *sw = mSuggestions.top(); 103 if (DEBUG_WORDS_PRIORITY_QUEUE) { 104 AKLOGI("Clear word. %d", sw->mScore); 105 DUMP_WORD(sw->mWord, sw->mWordLength); 106 } 107 sw->mUsed = false; 108 mSuggestions.pop(); 109 } 110 } 111 112 AK_FORCE_INLINE void dumpTopWord() const { 113 if (size() <= 0) { 114 return; 115 } 116 DUMP_WORD(mHighestSuggestedWord->mWord, mHighestSuggestedWord->mWordLength); 117 } 118 119 AK_FORCE_INLINE float getHighestNormalizedScore(const int *before, const int beforeLength, 120 int **outWord, int *outScore, int *outLength) const { 121 if (!mHighestSuggestedWord) { 122 return 0.0f; 123 } 124 return getNormalizedScore(mHighestSuggestedWord, before, beforeLength, outWord, outScore, 125 outLength); 126 } 127 128 int outputSuggestions(const int *before, const int beforeLength, int *frequencies, 129 int *outputCodePoints, int* outputTypes); 130 131 private: 132 DISALLOW_IMPLICIT_CONSTRUCTORS(WordsPriorityQueue); 133 struct wordComparator { 134 bool operator ()(SuggestedWord * left, SuggestedWord * right) { 135 return left->mScore > right->mScore; 136 } 137 }; 138 139 SuggestedWord *getFreeSuggestedWord(int score, int *word, int wordLength, int type) const { 140 for (int i = 0; i < MAX_WORD_LENGTH; ++i) { 141 if (!mSuggestedWords[i].mUsed) { 142 mSuggestedWords[i].setParams(score, word, wordLength, type); 143 return &mSuggestedWords[i]; 144 } 145 } 146 return 0; 147 } 148 149 static float getNormalizedScore(SuggestedWord *sw, const int *before, const int beforeLength, 150 int **outWord, int *outScore, int *outLength) { 151 const int score = sw->mScore; 152 int *word = sw->mWord; 153 const int wordLength = sw->mWordLength; 154 if (outScore) { 155 *outScore = score; 156 } 157 if (outWord) { 158 *outWord = word; 159 } 160 if (outLength) { 161 *outLength = wordLength; 162 } 163 return Correction::RankingAlgorithm::calcNormalizedScore(before, beforeLength, word, 164 wordLength, score); 165 } 166 167 typedef std::priority_queue<SuggestedWord *, std::vector<SuggestedWord *>, 168 wordComparator> Suggestions; 169 Suggestions mSuggestions; 170 const int MAX_WORDS; 171 SuggestedWord *mSuggestedWords; 172 SuggestedWord *mHighestSuggestedWord; 173 }; 174 } // namespace latinime 175 #endif // LATINIME_WORDS_PRIORITY_QUEUE_H 176