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