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 <iostream> 22 #include <queue> 23 #include "defines.h" 24 25 namespace latinime { 26 27 class WordsPriorityQueue { 28 public: 29 class SuggestedWord { 30 public: 31 int mScore; 32 unsigned short mWord[MAX_WORD_LENGTH_INTERNAL]; 33 int mWordLength; 34 bool mUsed; 35 36 void setParams(int score, unsigned short* word, int wordLength) { 37 mScore = score; 38 mWordLength = wordLength; 39 memcpy(mWord, word, sizeof(unsigned short) * wordLength); 40 mUsed = true; 41 } 42 }; 43 44 WordsPriorityQueue(int maxWords, int maxWordLength) : 45 MAX_WORDS((unsigned int) maxWords), MAX_WORD_LENGTH( 46 (unsigned int) maxWordLength) { 47 mSuggestedWords = new SuggestedWord[maxWordLength]; 48 for (int i = 0; i < maxWordLength; ++i) { 49 mSuggestedWords[i].mUsed = false; 50 } 51 mHighestSuggestedWord = 0; 52 } 53 54 ~WordsPriorityQueue() { 55 delete[] mSuggestedWords; 56 } 57 58 void push(int score, unsigned short* word, int wordLength) { 59 SuggestedWord* sw = 0; 60 if (mSuggestions.size() >= MAX_WORDS) { 61 sw = mSuggestions.top(); 62 const int minScore = sw->mScore; 63 if (minScore >= score) { 64 return; 65 } else { 66 sw->mUsed = false; 67 mSuggestions.pop(); 68 } 69 } 70 if (sw == 0) { 71 sw = getFreeSuggestedWord(score, word, wordLength); 72 } else { 73 sw->setParams(score, word, wordLength); 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() { 90 if (mSuggestions.empty()) return 0; 91 SuggestedWord* sw = mSuggestions.top(); 92 return sw; 93 } 94 95 int outputSuggestions(const unsigned short* before, const int beforeLength, 96 int *frequencies, unsigned short *outputChars) { 97 mHighestSuggestedWord = 0; 98 const unsigned int size = min( 99 MAX_WORDS, static_cast<unsigned int>(mSuggestions.size())); 100 SuggestedWord* swBuffer[size]; 101 int index = size - 1; 102 while (!mSuggestions.empty() && index >= 0) { 103 SuggestedWord* sw = mSuggestions.top(); 104 if (DEBUG_WORDS_PRIORITY_QUEUE) { 105 AKLOGI("dump word. %d", sw->mScore); 106 DUMP_WORD(sw->mWord, sw->mWordLength); 107 } 108 swBuffer[index] = sw; 109 mSuggestions.pop(); 110 --index; 111 } 112 if (size >= 2) { 113 SuggestedWord* nsMaxSw = 0; 114 unsigned int maxIndex = 0; 115 float maxNs = 0; 116 for (unsigned int i = 0; i < size; ++i) { 117 SuggestedWord* tempSw = swBuffer[i]; 118 if (!tempSw) { 119 continue; 120 } 121 const float tempNs = getNormalizedScore(tempSw, before, beforeLength, 0, 0, 0); 122 if (tempNs >= maxNs) { 123 maxNs = tempNs; 124 maxIndex = i; 125 nsMaxSw = tempSw; 126 } 127 } 128 if (maxIndex > 0 && nsMaxSw) { 129 memmove(&swBuffer[1], &swBuffer[0], maxIndex * sizeof(SuggestedWord*)); 130 swBuffer[0] = nsMaxSw; 131 } 132 } 133 for (unsigned int i = 0; i < size; ++i) { 134 SuggestedWord* sw = swBuffer[i]; 135 if (!sw) { 136 AKLOGE("SuggestedWord is null %d", i); 137 continue; 138 } 139 const unsigned int wordLength = sw->mWordLength; 140 char* targetAdr = (char*) outputChars + i * MAX_WORD_LENGTH * sizeof(short); 141 frequencies[i] = sw->mScore; 142 memcpy(targetAdr, sw->mWord, (wordLength) * sizeof(short)); 143 if (wordLength < MAX_WORD_LENGTH) { 144 ((unsigned short*) targetAdr)[wordLength] = 0; 145 } 146 sw->mUsed = false; 147 } 148 return size; 149 } 150 151 int size() const { 152 return mSuggestions.size(); 153 } 154 155 void clear() { 156 mHighestSuggestedWord = 0; 157 while (!mSuggestions.empty()) { 158 SuggestedWord* sw = mSuggestions.top(); 159 if (DEBUG_WORDS_PRIORITY_QUEUE) { 160 AKLOGI("Clear word. %d", sw->mScore); 161 DUMP_WORD(sw->mWord, sw->mWordLength); 162 } 163 sw->mUsed = false; 164 mSuggestions.pop(); 165 } 166 } 167 168 void dumpTopWord() { 169 if (size() <= 0) { 170 return; 171 } 172 DUMP_WORD(mHighestSuggestedWord->mWord, mHighestSuggestedWord->mWordLength); 173 } 174 175 float getHighestNormalizedScore(const unsigned short* before, const int beforeLength, 176 unsigned short** outWord, int *outScore, int *outLength) { 177 if (!mHighestSuggestedWord) { 178 return 0.0; 179 } 180 return getNormalizedScore( 181 mHighestSuggestedWord, before, beforeLength, outWord, outScore, outLength); 182 } 183 184 private: 185 struct wordComparator { 186 bool operator ()(SuggestedWord * left, SuggestedWord * right) { 187 return left->mScore > right->mScore; 188 } 189 }; 190 191 SuggestedWord* getFreeSuggestedWord(int score, unsigned short* word, 192 int wordLength) { 193 for (unsigned int i = 0; i < MAX_WORD_LENGTH; ++i) { 194 if (!mSuggestedWords[i].mUsed) { 195 mSuggestedWords[i].setParams(score, word, wordLength); 196 return &mSuggestedWords[i]; 197 } 198 } 199 return 0; 200 } 201 202 static float getNormalizedScore(SuggestedWord* sw, const unsigned short* before, 203 const int beforeLength, unsigned short** outWord, int *outScore, int *outLength) { 204 const int score = sw->mScore; 205 unsigned short* word = sw->mWord; 206 const int wordLength = sw->mWordLength; 207 if (outScore) { 208 *outScore = score; 209 } 210 if (outWord) { 211 *outWord = word; 212 } 213 if (outLength) { 214 *outLength = wordLength; 215 } 216 return Correction::RankingAlgorithm::calcNormalizedScore( 217 before, beforeLength, word, wordLength, score); 218 } 219 220 typedef std::priority_queue<SuggestedWord*, std::vector<SuggestedWord*>, 221 wordComparator> Suggestions; 222 Suggestions mSuggestions; 223 const unsigned int MAX_WORDS; 224 const unsigned int MAX_WORD_LENGTH; 225 SuggestedWord* mSuggestedWords; 226 SuggestedWord* mHighestSuggestedWord; 227 }; 228 } 229 230 #endif // LATINIME_WORDS_PRIORITY_QUEUE_H 231
