proximity_info.cpp revision 9fb6f47a6a11f62d134d4d6259181ac987fc1ad3
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#include <assert.h> 18#include <stdio.h> 19#include <string.h> 20 21#define LOG_TAG "LatinIME: proximity_info.cpp" 22 23#include "dictionary.h" 24#include "proximity_info.h" 25 26namespace latinime { 27 28inline void copyOrFillZero(void *to, const void *from, size_t size) { 29 if (from) { 30 memcpy(to, from, size); 31 } else { 32 memset(to, 0, size); 33 } 34} 35 36ProximityInfo::ProximityInfo(const int maxProximityCharsSize, const int keyboardWidth, 37 const int keyboardHeight, const int gridWidth, const int gridHeight, 38 const uint32_t *proximityCharsArray, const int keyCount, const int32_t *keyXCoordinates, 39 const int32_t *keyYCoordinates, const int32_t *keyWidths, const int32_t *keyHeights, 40 const int32_t *keyCharCodes, const float *sweetSpotCenterXs, const float *sweetSpotCenterYs, 41 const float *sweetSpotRadii) 42 : MAX_PROXIMITY_CHARS_SIZE(maxProximityCharsSize), KEYBOARD_WIDTH(keyboardWidth), 43 KEYBOARD_HEIGHT(keyboardHeight), GRID_WIDTH(gridWidth), GRID_HEIGHT(gridHeight), 44 CELL_WIDTH((keyboardWidth + gridWidth - 1) / gridWidth), 45 CELL_HEIGHT((keyboardHeight + gridHeight - 1) / gridHeight), 46 KEY_COUNT(min(keyCount, MAX_KEY_COUNT_IN_A_KEYBOARD)), 47 HAS_TOUCH_POSITION_CORRECTION_DATA(keyCount > 0 && keyXCoordinates && keyYCoordinates 48 && keyWidths && keyHeights && keyCharCodes && sweetSpotCenterXs 49 && sweetSpotCenterYs && sweetSpotRadii), 50 mInputXCoordinates(0), mInputYCoordinates(0), 51 mTouchPositionCorrectionEnabled(false) { 52 const int proximityGridLength = GRID_WIDTH * GRID_HEIGHT * MAX_PROXIMITY_CHARS_SIZE; 53 mProximityCharsArray = new uint32_t[proximityGridLength]; 54 if (DEBUG_PROXIMITY_INFO) { 55 AKLOGI("Create proximity info array %d", proximityGridLength); 56 } 57 memcpy(mProximityCharsArray, proximityCharsArray, 58 proximityGridLength * sizeof(mProximityCharsArray[0])); 59 const int normalizedSquaredDistancesLength = 60 MAX_PROXIMITY_CHARS_SIZE * MAX_WORD_LENGTH_INTERNAL; 61 mNormalizedSquaredDistances = new int[normalizedSquaredDistancesLength]; 62 for (int i = 0; i < normalizedSquaredDistancesLength; ++i) { 63 mNormalizedSquaredDistances[i] = NOT_A_DISTANCE; 64 } 65 66 copyOrFillZero(mKeyXCoordinates, keyXCoordinates, KEY_COUNT * sizeof(mKeyXCoordinates[0])); 67 copyOrFillZero(mKeyYCoordinates, keyYCoordinates, KEY_COUNT * sizeof(mKeyYCoordinates[0])); 68 copyOrFillZero(mKeyWidths, keyWidths, KEY_COUNT * sizeof(mKeyWidths[0])); 69 copyOrFillZero(mKeyHeights, keyHeights, KEY_COUNT * sizeof(mKeyHeights[0])); 70 copyOrFillZero(mKeyCharCodes, keyCharCodes, KEY_COUNT * sizeof(mKeyCharCodes[0])); 71 copyOrFillZero(mSweetSpotCenterXs, sweetSpotCenterXs, 72 KEY_COUNT * sizeof(mSweetSpotCenterXs[0])); 73 copyOrFillZero(mSweetSpotCenterYs, sweetSpotCenterYs, 74 KEY_COUNT * sizeof(mSweetSpotCenterYs[0])); 75 copyOrFillZero(mSweetSpotRadii, sweetSpotRadii, KEY_COUNT * sizeof(mSweetSpotRadii[0])); 76 77 initializeCodeToKeyIndex(); 78} 79 80// Build the reversed look up table from the char code to the index in mKeyXCoordinates, 81// mKeyYCoordinates, mKeyWidths, mKeyHeights, mKeyCharCodes. 82void ProximityInfo::initializeCodeToKeyIndex() { 83 memset(mCodeToKeyIndex, -1, (MAX_CHAR_CODE + 1) * sizeof(mCodeToKeyIndex[0])); 84 for (int i = 0; i < KEY_COUNT; ++i) { 85 const int code = mKeyCharCodes[i]; 86 if (0 <= code && code <= MAX_CHAR_CODE) { 87 mCodeToKeyIndex[code] = i; 88 } 89 } 90} 91 92ProximityInfo::~ProximityInfo() { 93 delete[] mNormalizedSquaredDistances; 94 delete[] mProximityCharsArray; 95} 96 97inline int ProximityInfo::getStartIndexFromCoordinates(const int x, const int y) const { 98 return ((y / CELL_HEIGHT) * GRID_WIDTH + (x / CELL_WIDTH)) 99 * MAX_PROXIMITY_CHARS_SIZE; 100} 101 102bool ProximityInfo::hasSpaceProximity(const int x, const int y) const { 103 if (x < 0 || y < 0) { 104 if (DEBUG_DICT) { 105 AKLOGI("HasSpaceProximity: Illegal coordinates (%d, %d)", x, y); 106 assert(false); 107 } 108 return false; 109 } 110 111 const int startIndex = getStartIndexFromCoordinates(x, y); 112 if (DEBUG_PROXIMITY_INFO) { 113 AKLOGI("hasSpaceProximity: index %d, %d, %d", startIndex, x, y); 114 } 115 for (int i = 0; i < MAX_PROXIMITY_CHARS_SIZE; ++i) { 116 if (DEBUG_PROXIMITY_INFO) { 117 AKLOGI("Index: %d", mProximityCharsArray[startIndex + i]); 118 } 119 if (mProximityCharsArray[startIndex + i] == KEYCODE_SPACE) { 120 return true; 121 } 122 } 123 return false; 124} 125 126// TODO: Calculate nearby codes here. 127void ProximityInfo::setInputParams(const int* inputCodes, const int inputLength, 128 const int* xCoordinates, const int* yCoordinates) { 129 mInputCodes = inputCodes; 130 mInputXCoordinates = xCoordinates; 131 mInputYCoordinates = yCoordinates; 132 mTouchPositionCorrectionEnabled = 133 HAS_TOUCH_POSITION_CORRECTION_DATA && xCoordinates && yCoordinates; 134 mInputLength = inputLength; 135 for (int i = 0; i < inputLength; ++i) { 136 mPrimaryInputWord[i] = getPrimaryCharAt(i); 137 } 138 mPrimaryInputWord[inputLength] = 0; 139 for (int i = 0; i < mInputLength; ++i) { 140 const int *proximityChars = getProximityCharsAt(i); 141 for (int j = 0; j < MAX_PROXIMITY_CHARS_SIZE && proximityChars[j] > 0; ++j) { 142 const int currentChar = proximityChars[j]; 143 const int keyIndex = getKeyIndex(currentChar); 144 const float squaredDistance = calculateNormalizedSquaredDistance(keyIndex, i); 145 if (squaredDistance >= 0.0f) { 146 mNormalizedSquaredDistances[i * MAX_PROXIMITY_CHARS_SIZE + j] = 147 (int)(squaredDistance * NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR); 148 } else { 149 mNormalizedSquaredDistances[i * MAX_PROXIMITY_CHARS_SIZE + j] = (j == 0) 150 ? EQUIVALENT_CHAR_WITHOUT_DISTANCE_INFO 151 : PROXIMITY_CHAR_WITHOUT_DISTANCE_INFO; 152 } 153 } 154 } 155} 156 157inline float square(const float x) { return x * x; } 158 159float ProximityInfo::calculateNormalizedSquaredDistance( 160 const int keyIndex, const int inputIndex) const { 161 static const float NOT_A_DISTANCE_FLOAT = -1.0f; 162 if (keyIndex == NOT_A_INDEX) { 163 return NOT_A_DISTANCE_FLOAT; 164 } 165 if (!hasSweetSpotData(keyIndex)) { 166 return NOT_A_DISTANCE_FLOAT; 167 } 168 const float squaredDistance = calculateSquaredDistanceFromSweetSpotCenter(keyIndex, inputIndex); 169 const float squaredRadius = square(mSweetSpotRadii[keyIndex]); 170 return squaredDistance / squaredRadius; 171} 172 173int ProximityInfo::getKeyIndex(const int c) const { 174 if (KEY_COUNT == 0 || !mInputXCoordinates || !mInputYCoordinates) { 175 // We do not have the coordinate data 176 return NOT_A_INDEX; 177 } 178 const unsigned short baseLowerC = toBaseLowerCase(c); 179 if (baseLowerC > MAX_CHAR_CODE) { 180 return NOT_A_INDEX; 181 } 182 return mCodeToKeyIndex[baseLowerC]; 183} 184 185float ProximityInfo::calculateSquaredDistanceFromSweetSpotCenter( 186 const int keyIndex, const int inputIndex) const { 187 const float sweetSpotCenterX = mSweetSpotCenterXs[keyIndex]; 188 const float sweetSpotCenterY = mSweetSpotCenterYs[keyIndex]; 189 const float inputX = (float)mInputXCoordinates[inputIndex]; 190 const float inputY = (float)mInputYCoordinates[inputIndex]; 191 return square(inputX - sweetSpotCenterX) + square(inputY - sweetSpotCenterY); 192} 193 194inline const int* ProximityInfo::getProximityCharsAt(const int index) const { 195 return mInputCodes + (index * MAX_PROXIMITY_CHARS_SIZE); 196} 197 198unsigned short ProximityInfo::getPrimaryCharAt(const int index) const { 199 return getProximityCharsAt(index)[0]; 200} 201 202inline bool ProximityInfo::existsCharInProximityAt(const int index, const int c) const { 203 const int *chars = getProximityCharsAt(index); 204 int i = 0; 205 while (chars[i] > 0 && i < MAX_PROXIMITY_CHARS_SIZE) { 206 if (chars[i++] == c) { 207 return true; 208 } 209 } 210 return false; 211} 212 213bool ProximityInfo::existsAdjacentProximityChars(const int index) const { 214 if (index < 0 || index >= mInputLength) return false; 215 const int currentChar = getPrimaryCharAt(index); 216 const int leftIndex = index - 1; 217 if (leftIndex >= 0 && existsCharInProximityAt(leftIndex, currentChar)) { 218 return true; 219 } 220 const int rightIndex = index + 1; 221 if (rightIndex < mInputLength && existsCharInProximityAt(rightIndex, currentChar)) { 222 return true; 223 } 224 return false; 225} 226 227// In the following function, c is the current character of the dictionary word 228// currently examined. 229// currentChars is an array containing the keys close to the character the 230// user actually typed at the same position. We want to see if c is in it: if so, 231// then the word contains at that position a character close to what the user 232// typed. 233// What the user typed is actually the first character of the array. 234// proximityIndex is a pointer to the variable where getMatchedProximityId returns 235// the index of c in the proximity chars of the input index. 236// Notice : accented characters do not have a proximity list, so they are alone 237// in their list. The non-accented version of the character should be considered 238// "close", but not the other keys close to the non-accented version. 239ProximityInfo::ProximityType ProximityInfo::getMatchedProximityId(const int index, 240 const unsigned short c, const bool checkProximityChars, int *proximityIndex) const { 241 const int *currentChars = getProximityCharsAt(index); 242 const int firstChar = currentChars[0]; 243 const unsigned short baseLowerC = toBaseLowerCase(c); 244 245 // The first char in the array is what user typed. If it matches right away, 246 // that means the user typed that same char for this pos. 247 if (firstChar == baseLowerC || firstChar == c) { 248 return EQUIVALENT_CHAR; 249 } 250 251 if (!checkProximityChars) return UNRELATED_CHAR; 252 253 // If the non-accented, lowercased version of that first character matches c, 254 // then we have a non-accented version of the accented character the user 255 // typed. Treat it as a close char. 256 if (toBaseLowerCase(firstChar) == baseLowerC) 257 return NEAR_PROXIMITY_CHAR; 258 259 // Not an exact nor an accent-alike match: search the list of close keys 260 int j = 1; 261 while (j < MAX_PROXIMITY_CHARS_SIZE && currentChars[j] > 0) { 262 const bool matched = (currentChars[j] == baseLowerC || currentChars[j] == c); 263 if (matched) { 264 if (proximityIndex) { 265 *proximityIndex = j; 266 } 267 return NEAR_PROXIMITY_CHAR; 268 } 269 ++j; 270 } 271 272 // Was not included, signal this as an unrelated character. 273 return UNRELATED_CHAR; 274} 275 276bool ProximityInfo::sameAsTyped(const unsigned short *word, int length) const { 277 if (length != mInputLength) { 278 return false; 279 } 280 const int *inputCodes = mInputCodes; 281 while (length--) { 282 if ((unsigned int) *inputCodes != (unsigned int) *word) { 283 return false; 284 } 285 inputCodes += MAX_PROXIMITY_CHARS_SIZE; 286 word++; 287 } 288 return true; 289} 290 291const int ProximityInfo::NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR_LOG_2; 292const int ProximityInfo::NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR; 293const int ProximityInfo::MAX_KEY_COUNT_IN_A_KEYBOARD; 294const int ProximityInfo::MAX_CHAR_CODE; 295 296} // namespace latinime 297