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 package com.android.inputmethod.keyboard; 18 19 import android.graphics.Rect; 20 import android.text.TextUtils; 21 import android.util.Log; 22 23 import com.android.inputmethod.keyboard.internal.TouchPositionCorrection; 24 import com.android.inputmethod.latin.Constants; 25 import com.android.inputmethod.latin.utils.JniUtils; 26 27 import java.util.Arrays; 28 29 public class ProximityInfo { 30 private static final String TAG = ProximityInfo.class.getSimpleName(); 31 private static final boolean DEBUG = false; 32 33 // Must be equal to MAX_PROXIMITY_CHARS_SIZE in native/jni/src/defines.h 34 public static final int MAX_PROXIMITY_CHARS_SIZE = 16; 35 /** Number of key widths from current touch point to search for nearest keys. */ 36 private static final float SEARCH_DISTANCE = 1.2f; 37 private static final Key[] EMPTY_KEY_ARRAY = new Key[0]; 38 private static final float DEFAULT_TOUCH_POSITION_CORRECTION_RADIUS = 0.15f; 39 40 private final int mGridWidth; 41 private final int mGridHeight; 42 private final int mGridSize; 43 private final int mCellWidth; 44 private final int mCellHeight; 45 // TODO: Find a proper name for mKeyboardMinWidth 46 private final int mKeyboardMinWidth; 47 private final int mKeyboardHeight; 48 private final int mMostCommonKeyWidth; 49 private final int mMostCommonKeyHeight; 50 private final Key[] mKeys; 51 private final Key[][] mGridNeighbors; 52 private final String mLocaleStr; 53 54 ProximityInfo(final String localeStr, final int gridWidth, final int gridHeight, 55 final int minWidth, final int height, final int mostCommonKeyWidth, 56 final int mostCommonKeyHeight, final Key[] keys, 57 final TouchPositionCorrection touchPositionCorrection) { 58 if (TextUtils.isEmpty(localeStr)) { 59 mLocaleStr = ""; 60 } else { 61 mLocaleStr = localeStr; 62 } 63 mGridWidth = gridWidth; 64 mGridHeight = gridHeight; 65 mGridSize = mGridWidth * mGridHeight; 66 mCellWidth = (minWidth + mGridWidth - 1) / mGridWidth; 67 mCellHeight = (height + mGridHeight - 1) / mGridHeight; 68 mKeyboardMinWidth = minWidth; 69 mKeyboardHeight = height; 70 mMostCommonKeyHeight = mostCommonKeyHeight; 71 mMostCommonKeyWidth = mostCommonKeyWidth; 72 mKeys = keys; 73 mGridNeighbors = new Key[mGridSize][]; 74 if (minWidth == 0 || height == 0) { 75 // No proximity required. Keyboard might be more keys keyboard. 76 return; 77 } 78 computeNearestNeighbors(); 79 mNativeProximityInfo = createNativeProximityInfo(touchPositionCorrection); 80 } 81 82 private long mNativeProximityInfo; 83 static { 84 JniUtils.loadNativeLibrary(); 85 } 86 87 // TODO: Stop passing proximityCharsArray 88 private static native long setProximityInfoNative(String locale, 89 int displayWidth, int displayHeight, int gridWidth, int gridHeight, 90 int mostCommonKeyWidth, int mostCommonKeyHeight, int[] proximityCharsArray, 91 int keyCount, int[] keyXCoordinates, int[] keyYCoordinates, int[] keyWidths, 92 int[] keyHeights, int[] keyCharCodes, float[] sweetSpotCenterXs, 93 float[] sweetSpotCenterYs, float[] sweetSpotRadii); 94 95 private static native void releaseProximityInfoNative(long nativeProximityInfo); 96 97 private static boolean needsProximityInfo(final Key key) { 98 // Don't include special keys into ProximityInfo. 99 return key.getCode() >= Constants.CODE_SPACE; 100 } 101 102 private static int getProximityInfoKeysCount(final Key[] keys) { 103 int count = 0; 104 for (final Key key : keys) { 105 if (needsProximityInfo(key)) { 106 count++; 107 } 108 } 109 return count; 110 } 111 112 private long createNativeProximityInfo(final TouchPositionCorrection touchPositionCorrection) { 113 final Key[][] gridNeighborKeys = mGridNeighbors; 114 final int[] proximityCharsArray = new int[mGridSize * MAX_PROXIMITY_CHARS_SIZE]; 115 Arrays.fill(proximityCharsArray, Constants.NOT_A_CODE); 116 for (int i = 0; i < mGridSize; ++i) { 117 final int proximityCharsLength = gridNeighborKeys[i].length; 118 int infoIndex = i * MAX_PROXIMITY_CHARS_SIZE; 119 for (int j = 0; j < proximityCharsLength; ++j) { 120 final Key neighborKey = gridNeighborKeys[i][j]; 121 // Excluding from proximityCharsArray 122 if (!needsProximityInfo(neighborKey)) { 123 continue; 124 } 125 proximityCharsArray[infoIndex] = neighborKey.getCode(); 126 infoIndex++; 127 } 128 } 129 if (DEBUG) { 130 final StringBuilder sb = new StringBuilder(); 131 for (int i = 0; i < mGridSize; i++) { 132 sb.setLength(0); 133 for (int j = 0; j < MAX_PROXIMITY_CHARS_SIZE; j++) { 134 final int code = proximityCharsArray[i * MAX_PROXIMITY_CHARS_SIZE + j]; 135 if (code == Constants.NOT_A_CODE) { 136 break; 137 } 138 if (sb.length() > 0) sb.append(" "); 139 sb.append(Constants.printableCode(code)); 140 } 141 Log.d(TAG, "proxmityChars["+i+"]: " + sb); 142 } 143 } 144 145 final Key[] keys = mKeys; 146 final int keyCount = getProximityInfoKeysCount(keys); 147 final int[] keyXCoordinates = new int[keyCount]; 148 final int[] keyYCoordinates = new int[keyCount]; 149 final int[] keyWidths = new int[keyCount]; 150 final int[] keyHeights = new int[keyCount]; 151 final int[] keyCharCodes = new int[keyCount]; 152 final float[] sweetSpotCenterXs; 153 final float[] sweetSpotCenterYs; 154 final float[] sweetSpotRadii; 155 156 for (int infoIndex = 0, keyIndex = 0; keyIndex < keys.length; keyIndex++) { 157 final Key key = keys[keyIndex]; 158 // Excluding from key coordinate arrays 159 if (!needsProximityInfo(key)) { 160 continue; 161 } 162 keyXCoordinates[infoIndex] = key.getX(); 163 keyYCoordinates[infoIndex] = key.getY(); 164 keyWidths[infoIndex] = key.getWidth(); 165 keyHeights[infoIndex] = key.getHeight(); 166 keyCharCodes[infoIndex] = key.getCode(); 167 infoIndex++; 168 } 169 170 if (touchPositionCorrection != null && touchPositionCorrection.isValid()) { 171 if (DEBUG) { 172 Log.d(TAG, "touchPositionCorrection: ON"); 173 } 174 sweetSpotCenterXs = new float[keyCount]; 175 sweetSpotCenterYs = new float[keyCount]; 176 sweetSpotRadii = new float[keyCount]; 177 final int rows = touchPositionCorrection.getRows(); 178 final float defaultRadius = DEFAULT_TOUCH_POSITION_CORRECTION_RADIUS 179 * (float)Math.hypot(mMostCommonKeyWidth, mMostCommonKeyHeight); 180 for (int infoIndex = 0, keyIndex = 0; keyIndex < keys.length; keyIndex++) { 181 final Key key = keys[keyIndex]; 182 // Excluding from touch position correction arrays 183 if (!needsProximityInfo(key)) { 184 continue; 185 } 186 final Rect hitBox = key.getHitBox(); 187 sweetSpotCenterXs[infoIndex] = hitBox.exactCenterX(); 188 sweetSpotCenterYs[infoIndex] = hitBox.exactCenterY(); 189 sweetSpotRadii[infoIndex] = defaultRadius; 190 final int row = hitBox.top / mMostCommonKeyHeight; 191 if (row < rows) { 192 final int hitBoxWidth = hitBox.width(); 193 final int hitBoxHeight = hitBox.height(); 194 final float hitBoxDiagonal = (float)Math.hypot(hitBoxWidth, hitBoxHeight); 195 sweetSpotCenterXs[infoIndex] += 196 touchPositionCorrection.getX(row) * hitBoxWidth; 197 sweetSpotCenterYs[infoIndex] += 198 touchPositionCorrection.getY(row) * hitBoxHeight; 199 sweetSpotRadii[infoIndex] = 200 touchPositionCorrection.getRadius(row) * hitBoxDiagonal; 201 } 202 if (DEBUG) { 203 Log.d(TAG, String.format( 204 " [%2d] row=%d x/y/r=%7.2f/%7.2f/%5.2f %s code=%s", infoIndex, row, 205 sweetSpotCenterXs[infoIndex], sweetSpotCenterYs[infoIndex], 206 sweetSpotRadii[infoIndex], (row < rows ? "correct" : "default"), 207 Constants.printableCode(key.getCode()))); 208 } 209 infoIndex++; 210 } 211 } else { 212 sweetSpotCenterXs = sweetSpotCenterYs = sweetSpotRadii = null; 213 if (DEBUG) { 214 Log.d(TAG, "touchPositionCorrection: OFF"); 215 } 216 } 217 218 // TODO: Stop passing proximityCharsArray 219 return setProximityInfoNative(mLocaleStr, mKeyboardMinWidth, mKeyboardHeight, 220 mGridWidth, mGridHeight, mMostCommonKeyWidth, mMostCommonKeyHeight, 221 proximityCharsArray, keyCount, keyXCoordinates, keyYCoordinates, keyWidths, 222 keyHeights, keyCharCodes, sweetSpotCenterXs, sweetSpotCenterYs, sweetSpotRadii); 223 } 224 225 public long getNativeProximityInfo() { 226 return mNativeProximityInfo; 227 } 228 229 @Override 230 protected void finalize() throws Throwable { 231 try { 232 if (mNativeProximityInfo != 0) { 233 releaseProximityInfoNative(mNativeProximityInfo); 234 mNativeProximityInfo = 0; 235 } 236 } finally { 237 super.finalize(); 238 } 239 } 240 241 private void computeNearestNeighbors() { 242 final int defaultWidth = mMostCommonKeyWidth; 243 final int keyCount = mKeys.length; 244 final int gridSize = mGridNeighbors.length; 245 final int threshold = (int) (defaultWidth * SEARCH_DISTANCE); 246 final int thresholdSquared = threshold * threshold; 247 // Round-up so we don't have any pixels outside the grid 248 final int lastPixelXCoordinate = mGridWidth * mCellWidth - 1; 249 final int lastPixelYCoordinate = mGridHeight * mCellHeight - 1; 250 251 // For large layouts, 'neighborsFlatBuffer' is about 80k of memory: gridSize is usually 512, 252 // keycount is about 40 and a pointer to a Key is 4 bytes. This contains, for each cell, 253 // enough space for as many keys as there are on the keyboard. Hence, every 254 // keycount'th element is the start of a new cell, and each of these virtual subarrays 255 // start empty with keycount spaces available. This fills up gradually in the loop below. 256 // Since in the practice each cell does not have a lot of neighbors, most of this space is 257 // actually just empty padding in this fixed-size buffer. 258 final Key[] neighborsFlatBuffer = new Key[gridSize * keyCount]; 259 final int[] neighborCountPerCell = new int[gridSize]; 260 final int halfCellWidth = mCellWidth / 2; 261 final int halfCellHeight = mCellHeight / 2; 262 for (final Key key : mKeys) { 263 if (key.isSpacer()) continue; 264 265 /* HOW WE PRE-SELECT THE CELLS (iterate over only the relevant cells, instead of all of them) 266 267 We want to compute the distance for keys that are in the cells that are close enough to the 268 key border, as this method is performance-critical. These keys are represented with 'star' 269 background on the diagram below. Let's consider the Y case first. 270 271 We want to select the cells which center falls between the top of the key minus the threshold, 272 and the bottom of the key plus the threshold. 273 topPixelWithinThreshold is key.mY - threshold, and bottomPixelWithinThreshold is 274 key.mY + key.mHeight + threshold. 275 276 Then we need to compute the center of the top row that we need to evaluate, as we'll iterate 277 from there. 278 279 (0,0)----> x 280 | .-------------------------------------------. 281 | | | | | | | | | | | | | 282 | |---+---+---+---+---+---+---+---+---+---+---| .- top of top cell (aligned on the grid) 283 | | | | | | | | | | | | | | 284 | |-----------+---+---+---+---+---+---+---+---|---' v 285 | | | | |***|***|*_________________________ topPixelWithinThreshold | yDeltaToGrid 286 | |---+---+---+-----^-+-|-+---+---+---+---+---| ^ 287 | | | | |***|*|*|*|*|***|***| | | | ______________________________________ 288 v |---+---+--threshold--|-+---+---+---+---+---| | 289 | | | |***|*|*|*|*|***|***| | | | | Starting from key.mY, we substract 290 y |---+---+---+---+-v-+-|-+---+---+---+---+---| | thresholdBase and get the top pixel 291 | | | |***|**########------------------- key.mY | within the threshold. We align that on 292 |---+---+---+---+--#+---+-#-+---+---+---+---| | the grid by computing the delta to the 293 | | | |***|**#|***|*#*|***| | | | | grid, and get the top of the top cell. 294 |---+---+---+---+--#+---+-#-+---+---+---+---| | 295 | | | |***|**########*|***| | | | | Adding half the cell height to the top 296 |---+---+---+---+---+-|-+---+---+---+---+---| | of the top cell, we get the middle of 297 | | | |***|***|*|*|***|***| | | | | the top cell (yMiddleOfTopCell). 298 |---+---+---+---+---+-|-+---+---+---+---+---| | 299 | | | |***|***|*|*|***|***| | | | | 300 |---+---+---+---+---+-|________________________ yEnd | Since we only want to add the key to 301 | | | | | | | (bottomPixelWithinThreshold) | the proximity if it's close enough to 302 |---+---+---+---+---+---+---+---+---+---+---| | the center of the cell, we only need 303 | | | | | | | | | | | | | to compute for these cells where 304 '---'---'---'---'---'---'---'---'---'---'---' | topPixelWithinThreshold is above the 305 (positive x,y) | center of the cell. This is the case 306 | when yDeltaToGrid is less than half 307 [Zoomed in diagram] | the height of the cell. 308 +-------+-------+-------+-------+-------+ | 309 | | | | | | | On the zoomed in diagram, on the right 310 | | | | | | | the topPixelWithinThreshold (represented 311 | | | | | | top of | with an = sign) is below and we can skip 312 +-------+-------+-------+--v----+-------+ .. top cell | this cell, while on the left it's above 313 | | = topPixelWT | | yDeltaToGrid | and we need to compute for this cell. 314 |..yStart.|.....|.......|..|....|.......|... y middle | Thus, if yDeltaToGrid is more than half 315 | (left)| | | ^ = | | of top cell | the height of the cell, we start the 316 +-------+-|-----+-------+----|--+-------+ | iteration one cell below the top cell, 317 | | | | | | | | | else we start it on the top cell. This 318 |.......|.|.....|.......|....|..|.....yStart (right) | is stored in yStart. 319 320 Since we only want to go up to bottomPixelWithinThreshold, and we only iterate on the center 321 of the keys, we can stop as soon as the y value exceeds bottomPixelThreshold, so we don't 322 have to align this on the center of the key. Hence, we don't need a separate value for 323 bottomPixelWithinThreshold and call this yEnd right away. 324 */ 325 final int keyX = key.getX(); 326 final int keyY = key.getY(); 327 final int topPixelWithinThreshold = keyY - threshold; 328 final int yDeltaToGrid = topPixelWithinThreshold % mCellHeight; 329 final int yMiddleOfTopCell = topPixelWithinThreshold - yDeltaToGrid + halfCellHeight; 330 final int yStart = Math.max(halfCellHeight, 331 yMiddleOfTopCell + (yDeltaToGrid <= halfCellHeight ? 0 : mCellHeight)); 332 final int yEnd = Math.min(lastPixelYCoordinate, keyY + key.getHeight() + threshold); 333 334 final int leftPixelWithinThreshold = keyX - threshold; 335 final int xDeltaToGrid = leftPixelWithinThreshold % mCellWidth; 336 final int xMiddleOfLeftCell = leftPixelWithinThreshold - xDeltaToGrid + halfCellWidth; 337 final int xStart = Math.max(halfCellWidth, 338 xMiddleOfLeftCell + (xDeltaToGrid <= halfCellWidth ? 0 : mCellWidth)); 339 final int xEnd = Math.min(lastPixelXCoordinate, keyX + key.getWidth() + threshold); 340 341 int baseIndexOfCurrentRow = (yStart / mCellHeight) * mGridWidth + (xStart / mCellWidth); 342 for (int centerY = yStart; centerY <= yEnd; centerY += mCellHeight) { 343 int index = baseIndexOfCurrentRow; 344 for (int centerX = xStart; centerX <= xEnd; centerX += mCellWidth) { 345 if (key.squaredDistanceToEdge(centerX, centerY) < thresholdSquared) { 346 neighborsFlatBuffer[index * keyCount + neighborCountPerCell[index]] = key; 347 ++neighborCountPerCell[index]; 348 } 349 ++index; 350 } 351 baseIndexOfCurrentRow += mGridWidth; 352 } 353 } 354 355 for (int i = 0; i < gridSize; ++i) { 356 final int base = i * keyCount; 357 mGridNeighbors[i] = 358 Arrays.copyOfRange(neighborsFlatBuffer, base, base + neighborCountPerCell[i]); 359 } 360 } 361 362 public void fillArrayWithNearestKeyCodes(final int x, final int y, final int primaryKeyCode, 363 final int[] dest) { 364 final int destLength = dest.length; 365 if (destLength < 1) { 366 return; 367 } 368 int index = 0; 369 if (primaryKeyCode > Constants.CODE_SPACE) { 370 dest[index++] = primaryKeyCode; 371 } 372 final Key[] nearestKeys = getNearestKeys(x, y); 373 for (Key key : nearestKeys) { 374 if (index >= destLength) { 375 break; 376 } 377 final int code = key.getCode(); 378 if (code <= Constants.CODE_SPACE) { 379 break; 380 } 381 dest[index++] = code; 382 } 383 if (index < destLength) { 384 dest[index] = Constants.NOT_A_CODE; 385 } 386 } 387 388 public Key[] getNearestKeys(final int x, final int y) { 389 if (mGridNeighbors == null) { 390 return EMPTY_KEY_ARRAY; 391 } 392 if (x >= 0 && x < mKeyboardMinWidth && y >= 0 && y < mKeyboardHeight) { 393 int index = (y / mCellHeight) * mGridWidth + (x / mCellWidth); 394 if (index < mGridSize) { 395 return mGridNeighbors[index]; 396 } 397 } 398 return EMPTY_KEY_ARRAY; 399 } 400 } 401
