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