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:
getKeyIndexOf(const int keyCount,const int c,const std::unordered_map<int,int> * const codeToKeyMap)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 
initializeProximities(const int * const inputCodes,const int * const inputXCoordinates,const int * const inputYCoordinates,const int inputSize,const int * const keyXCoordinates,const int * const keyYCoordinates,const int * const keyWidths,const int * keyHeights,const int * const proximityCharsArray,const int cellHeight,const int cellWidth,const int gridWidth,const int mostCommonKeyWidth,const int keyCount,const std::vector<int> * locale,const std::unordered_map<int,int> * const codeToKeyMap,int * inputProximities)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 
getStartIndexFromCoordinates(const int x,const int y,const int cellHeight,const int cellWidth,const int gridWidth)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 
getSquaredDistanceFloat(const float x1,const float y1,const float x2,const float y2)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 
pointToLineSegSquaredDistanceFloat(const float x,const float y,const float x1,const float y1,const float x2,const float y2,const bool extend)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 
isMatchOrProximityChar(const ProximityType type)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 
isOnKey(const int * const keyXCoordinates,const int * const keyYCoordinates,const int * const keyWidths,const int * keyHeights,const int keyId,const int x,const int y)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 
calculateProximities(const int * const keyXCoordinates,const int * const keyYCoordinates,const int * const keyWidths,const int * keyHeights,const int * const proximityCharsArray,const int cellHeight,const int cellWidth,const int gridWidth,const int mostCommonKeyWidth,const int keyCount,const int x,const int y,const int primaryKey,const std::vector<int> * locale,const std::unordered_map<int,int> * const codeToKeyMap,int * proximities)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 
squaredLengthToEdge(const int * const keyXCoordinates,const int * const keyYCoordinates,const int * const keyWidths,const int * keyHeights,const int keyId,const int x,const int y)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