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_PROXIMITY_INFO_UTILS_H 18 #define LATINIME_PROXIMITY_INFO_UTILS_H 19 20 #include <cmath> 21 22 #include "defines.h" 23 #include "suggest/core/layout/additional_proximity_chars.h" 24 #include "suggest/core/layout/geometry_utils.h" 25 #include "utils/char_utils.h" 26 #include "utils/hash_map_compat.h" 27 28 namespace latinime { 29 class ProximityInfoUtils { 30 public: 31 static AK_FORCE_INLINE int getKeyIndexOf(const int keyCount, const int c, 32 const hash_map_compat<int, int> *const codeToKeyMap) { 33 if (keyCount == 0) { 34 // We do not have the coordinate data 35 return NOT_AN_INDEX; 36 } 37 if (c == NOT_A_CODE_POINT) { 38 return NOT_AN_INDEX; 39 } 40 const int lowerCode = CharUtils::toLowerCase(c); 41 hash_map_compat<int, int>::const_iterator mapPos = codeToKeyMap->find(lowerCode); 42 if (mapPos != codeToKeyMap->end()) { 43 return mapPos->second; 44 } 45 return NOT_AN_INDEX; 46 } 47 48 static AK_FORCE_INLINE void initializeProximities(const int *const inputCodes, 49 const int *const inputXCoordinates, const int *const inputYCoordinates, 50 const int inputSize, const int *const keyXCoordinates, 51 const int *const keyYCoordinates, const int *const keyWidths, const int *keyHeights, 52 const int *const proximityCharsArray, const int cellHeight, const int cellWidth, 53 const int gridWidth, const int mostCommonKeyWidth, const int keyCount, 54 const char *const localeStr, 55 const hash_map_compat<int, int> *const codeToKeyMap, int *inputProximities) { 56 // Initialize 57 // - mInputCodes 58 // - mNormalizedSquaredDistances 59 // TODO: Merge 60 for (int i = 0; i < inputSize; ++i) { 61 const int primaryKey = inputCodes[i]; 62 const int x = inputXCoordinates[i]; 63 const int y = inputYCoordinates[i]; 64 int *proximities = &inputProximities[i * MAX_PROXIMITY_CHARS_SIZE]; 65 calculateProximities(keyXCoordinates, keyYCoordinates, keyWidths, keyHeights, 66 proximityCharsArray, cellHeight, cellWidth, gridWidth, mostCommonKeyWidth, 67 keyCount, x, y, primaryKey, localeStr, codeToKeyMap, proximities); 68 } 69 70 if (DEBUG_PROXIMITY_CHARS) { 71 for (int i = 0; i < inputSize; ++i) { 72 AKLOGI("---"); 73 for (int j = 0; j < MAX_PROXIMITY_CHARS_SIZE; ++j) { 74 int proximityChar = 75 inputProximities[i * MAX_PROXIMITY_CHARS_SIZE + j]; 76 proximityChar += 0; 77 AKLOGI("--- (%d)%c", i, proximityChar); 78 } 79 } 80 } 81 } 82 83 static AK_FORCE_INLINE int getStartIndexFromCoordinates(const int x, const int y, 84 const int cellHeight, const int cellWidth, const int gridWidth) { 85 return ((y / cellHeight) * gridWidth + (x / cellWidth)) * MAX_PROXIMITY_CHARS_SIZE; 86 } 87 88 static inline float getSquaredDistanceFloat(const float x1, const float y1, const float x2, 89 const float y2) { 90 return GeometryUtils::SQUARE_FLOAT(x1 - x2) + GeometryUtils::SQUARE_FLOAT(y1 - y2); 91 } 92 93 static inline float pointToLineSegSquaredDistanceFloat(const float x, const float y, 94 const float x1, const float y1, const float x2, const float y2, const bool extend) { 95 const float ray1x = x - x1; 96 const float ray1y = y - y1; 97 const float ray2x = x2 - x1; 98 const float ray2y = y2 - y1; 99 100 const float dotProduct = ray1x * ray2x + ray1y * ray2y; 101 const float lineLengthSqr = GeometryUtils::SQUARE_FLOAT(ray2x) 102 + GeometryUtils::SQUARE_FLOAT(ray2y); 103 const float projectionLengthSqr = dotProduct / lineLengthSqr; 104 105 float projectionX; 106 float projectionY; 107 if (!extend && projectionLengthSqr < 0.0f) { 108 projectionX = x1; 109 projectionY = y1; 110 } else if (!extend && projectionLengthSqr > 1.0f) { 111 projectionX = x2; 112 projectionY = y2; 113 } else { 114 projectionX = x1 + projectionLengthSqr * ray2x; 115 projectionY = y1 + projectionLengthSqr * ray2y; 116 } 117 return getSquaredDistanceFloat(x, y, projectionX, projectionY); 118 } 119 120 static AK_FORCE_INLINE bool isMatchOrProximityChar(const ProximityType type) { 121 return type == MATCH_CHAR || type == PROXIMITY_CHAR || type == ADDITIONAL_PROXIMITY_CHAR; 122 } 123 124 // Normal distribution N(u, sigma^2). 125 struct NormalDistribution { 126 public: 127 NormalDistribution(const float u, const float sigma) 128 : mU(u), mSigma(sigma), 129 mPreComputedNonExpPart(1.0f / sqrtf(2.0f * M_PI_F 130 * GeometryUtils::SQUARE_FLOAT(sigma))), 131 mPreComputedExponentPart(-1.0f / (2.0f * GeometryUtils::SQUARE_FLOAT(sigma))) {} 132 133 float getProbabilityDensity(const float x) const { 134 const float shiftedX = x - mU; 135 return mPreComputedNonExpPart 136 * expf(mPreComputedExponentPart * GeometryUtils::SQUARE_FLOAT(shiftedX)); 137 } 138 139 private: 140 DISALLOW_IMPLICIT_CONSTRUCTORS(NormalDistribution); 141 const float mU; // mean value 142 const float mSigma; // standard deviation 143 const float mPreComputedNonExpPart; // = 1 / sqrt(2 * PI * sigma^2) 144 const float mPreComputedExponentPart; // = -1 / (2 * sigma^2) 145 }; // struct NormalDistribution 146 147 private: 148 DISALLOW_IMPLICIT_CONSTRUCTORS(ProximityInfoUtils); 149 150 static bool isOnKey(const int *const keyXCoordinates, const int *const keyYCoordinates, 151 const int *const keyWidths, const int *keyHeights, const int keyId, const int x, 152 const int y) { 153 if (keyId < 0) return true; // NOT_A_ID is -1, but return whenever < 0 just in case 154 const int left = keyXCoordinates[keyId]; 155 const int top = keyYCoordinates[keyId]; 156 const int right = left + keyWidths[keyId] + 1; 157 const int bottom = top + keyHeights[keyId]; 158 return left < right && top < bottom && x >= left && x < right && y >= top && y < bottom; 159 } 160 161 static AK_FORCE_INLINE void calculateProximities(const int *const keyXCoordinates, 162 const int *const keyYCoordinates, const int *const keyWidths, const int *keyHeights, 163 const int *const proximityCharsArray, const int cellHeight, const int cellWidth, 164 const int gridWidth, const int mostCommonKeyWidth, const int keyCount, 165 const int x, const int y, const int primaryKey, const char *const localeStr, 166 const hash_map_compat<int, int> *const codeToKeyMap, int *proximities) { 167 const int mostCommonKeyWidthSquare = mostCommonKeyWidth * mostCommonKeyWidth; 168 int insertPos = 0; 169 proximities[insertPos++] = primaryKey; 170 const int startIndex = getStartIndexFromCoordinates(x, y, cellHeight, cellWidth, gridWidth); 171 if (startIndex >= 0) { 172 for (int i = 0; i < MAX_PROXIMITY_CHARS_SIZE; ++i) { 173 const int c = proximityCharsArray[startIndex + i]; 174 if (c < KEYCODE_SPACE || c == primaryKey) { 175 continue; 176 } 177 const int keyIndex = getKeyIndexOf(keyCount, c, codeToKeyMap); 178 const bool onKey = isOnKey(keyXCoordinates, keyYCoordinates, keyWidths, keyHeights, 179 keyIndex, x, y); 180 const int distance = squaredLengthToEdge(keyXCoordinates, keyYCoordinates, 181 keyWidths, keyHeights, keyIndex, x, y); 182 if (onKey || distance < mostCommonKeyWidthSquare) { 183 proximities[insertPos++] = c; 184 if (insertPos >= MAX_PROXIMITY_CHARS_SIZE) { 185 if (DEBUG_DICT) { 186 ASSERT(false); 187 } 188 return; 189 } 190 } 191 } 192 const int additionalProximitySize = 193 AdditionalProximityChars::getAdditionalCharsSize(localeStr, primaryKey); 194 if (additionalProximitySize > 0) { 195 proximities[insertPos++] = ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE; 196 if (insertPos >= MAX_PROXIMITY_CHARS_SIZE) { 197 if (DEBUG_DICT) { 198 ASSERT(false); 199 } 200 return; 201 } 202 203 const int *additionalProximityChars = 204 AdditionalProximityChars::getAdditionalChars(localeStr, primaryKey); 205 for (int j = 0; j < additionalProximitySize; ++j) { 206 const int ac = additionalProximityChars[j]; 207 int k = 0; 208 for (; k < insertPos; ++k) { 209 if (ac == proximities[k]) { 210 break; 211 } 212 } 213 if (k < insertPos) { 214 continue; 215 } 216 proximities[insertPos++] = ac; 217 if (insertPos >= MAX_PROXIMITY_CHARS_SIZE) { 218 if (DEBUG_DICT) { 219 ASSERT(false); 220 } 221 return; 222 } 223 } 224 } 225 } 226 // Add a delimiter for the proximity characters 227 for (int i = insertPos; i < MAX_PROXIMITY_CHARS_SIZE; ++i) { 228 proximities[i] = NOT_A_CODE_POINT; 229 } 230 } 231 232 static int squaredLengthToEdge(const int *const keyXCoordinates, 233 const int *const keyYCoordinates, const int *const keyWidths, const int *keyHeights, 234 const int keyId, const int x, const int y) { 235 // NOT_A_ID is -1, but return whenever < 0 just in case 236 if (keyId < 0) return MAX_VALUE_FOR_WEIGHTING; 237 const int left = keyXCoordinates[keyId]; 238 const int top = keyYCoordinates[keyId]; 239 const int right = left + keyWidths[keyId]; 240 const int bottom = top + keyHeights[keyId]; 241 const int edgeX = x < left ? left : (x > right ? right : x); 242 const int edgeY = y < top ? top : (y > bottom ? bottom : y); 243 const int dx = x - edgeX; 244 const int dy = y - edgeY; 245 return dx * dx + dy * dy; 246 } 247 }; 248 } // namespace latinime 249 #endif // LATINIME_PROXIMITY_INFO_UTILS_H 250
