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