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