1 /* 2 * Copyright (C) 2007 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 android.view; 18 19 import android.graphics.Rect; 20 21 import java.util.ArrayList; 22 23 /** 24 * The algorithm used for finding the next focusable view in a given direction 25 * from a view that currently has focus. 26 */ 27 public class FocusFinder { 28 29 private static ThreadLocal<FocusFinder> tlFocusFinder = 30 new ThreadLocal<FocusFinder>() { 31 32 protected FocusFinder initialValue() { 33 return new FocusFinder(); 34 } 35 }; 36 37 /** 38 * Get the focus finder for this thread. 39 */ getInstance()40 public static FocusFinder getInstance() { 41 return tlFocusFinder.get(); 42 } 43 44 Rect mFocusedRect = new Rect(); 45 Rect mOtherRect = new Rect(); 46 Rect mBestCandidateRect = new Rect(); 47 48 // enforce thread local access FocusFinder()49 private FocusFinder() {} 50 51 /** 52 * Find the next view to take focus in root's descendants, starting from the view 53 * that currently is focused. 54 * @param root Contains focused 55 * @param focused Has focus now. 56 * @param direction Direction to look. 57 * @return The next focusable view, or null if none exists. 58 */ findNextFocus(ViewGroup root, View focused, int direction)59 public final View findNextFocus(ViewGroup root, View focused, int direction) { 60 61 if (focused != null) { 62 // check for user specified next focus 63 View userSetNextFocus = focused.findUserSetNextFocus(root, direction); 64 if (userSetNextFocus != null && 65 userSetNextFocus.isFocusable() && 66 (!userSetNextFocus.isInTouchMode() || 67 userSetNextFocus.isFocusableInTouchMode())) { 68 return userSetNextFocus; 69 } 70 71 // fill in interesting rect from focused 72 focused.getFocusedRect(mFocusedRect); 73 root.offsetDescendantRectToMyCoords(focused, mFocusedRect); 74 } else { 75 // make up a rect at top left or bottom right of root 76 switch (direction) { 77 case View.FOCUS_RIGHT: 78 case View.FOCUS_DOWN: 79 final int rootTop = root.getScrollY(); 80 final int rootLeft = root.getScrollX(); 81 mFocusedRect.set(rootLeft, rootTop, rootLeft, rootTop); 82 break; 83 84 case View.FOCUS_LEFT: 85 case View.FOCUS_UP: 86 final int rootBottom = root.getScrollY() + root.getHeight(); 87 final int rootRight = root.getScrollX() + root.getWidth(); 88 mFocusedRect.set(rootRight, rootBottom, 89 rootRight, rootBottom); 90 break; 91 } 92 } 93 return findNextFocus(root, focused, mFocusedRect, direction); 94 } 95 96 /** 97 * Find the next view to take focus in root's descendants, searching from 98 * a particular rectangle in root's coordinates. 99 * @param root Contains focusedRect. 100 * @param focusedRect The starting point of the search. 101 * @param direction Direction to look. 102 * @return The next focusable view, or null if none exists. 103 */ findNextFocusFromRect(ViewGroup root, Rect focusedRect, int direction)104 public View findNextFocusFromRect(ViewGroup root, Rect focusedRect, int direction) { 105 return findNextFocus(root, null, focusedRect, direction); 106 } 107 findNextFocus(ViewGroup root, View focused, Rect focusedRect, int direction)108 private View findNextFocus(ViewGroup root, View focused, Rect focusedRect, int direction) { 109 ArrayList<View> focusables = root.getFocusables(direction); 110 111 // initialize the best candidate to something impossible 112 // (so the first plausible view will become the best choice) 113 mBestCandidateRect.set(focusedRect); 114 switch(direction) { 115 case View.FOCUS_LEFT: 116 mBestCandidateRect.offset(focusedRect.width() + 1, 0); 117 break; 118 case View.FOCUS_RIGHT: 119 mBestCandidateRect.offset(-(focusedRect.width() + 1), 0); 120 break; 121 case View.FOCUS_UP: 122 mBestCandidateRect.offset(0, focusedRect.height() + 1); 123 break; 124 case View.FOCUS_DOWN: 125 mBestCandidateRect.offset(0, -(focusedRect.height() + 1)); 126 } 127 128 View closest = null; 129 130 int numFocusables = focusables.size(); 131 for (int i = 0; i < numFocusables; i++) { 132 View focusable = focusables.get(i); 133 134 // only interested in other non-root views 135 if (focusable == focused || focusable == root) continue; 136 137 // get visible bounds of other view in same coordinate system 138 focusable.getDrawingRect(mOtherRect); 139 root.offsetDescendantRectToMyCoords(focusable, mOtherRect); 140 141 if (isBetterCandidate(direction, focusedRect, mOtherRect, mBestCandidateRect)) { 142 mBestCandidateRect.set(mOtherRect); 143 closest = focusable; 144 } 145 } 146 return closest; 147 } 148 149 /** 150 * Is rect1 a better candidate than rect2 for a focus search in a particular 151 * direction from a source rect? This is the core routine that determines 152 * the order of focus searching. 153 * @param direction the direction (up, down, left, right) 154 * @param source The source we are searching from 155 * @param rect1 The candidate rectangle 156 * @param rect2 The current best candidate. 157 * @return Whether the candidate is the new best. 158 */ isBetterCandidate(int direction, Rect source, Rect rect1, Rect rect2)159 boolean isBetterCandidate(int direction, Rect source, Rect rect1, Rect rect2) { 160 161 // to be a better candidate, need to at least be a candidate in the first 162 // place :) 163 if (!isCandidate(source, rect1, direction)) { 164 return false; 165 } 166 167 // we know that rect1 is a candidate.. if rect2 is not a candidate, 168 // rect1 is better 169 if (!isCandidate(source, rect2, direction)) { 170 return true; 171 } 172 173 // if rect1 is better by beam, it wins 174 if (beamBeats(direction, source, rect1, rect2)) { 175 return true; 176 } 177 178 // if rect2 is better, then rect1 cant' be :) 179 if (beamBeats(direction, source, rect2, rect1)) { 180 return false; 181 } 182 183 // otherwise, do fudge-tastic comparison of the major and minor axis 184 return (getWeightedDistanceFor( 185 majorAxisDistance(direction, source, rect1), 186 minorAxisDistance(direction, source, rect1)) 187 < getWeightedDistanceFor( 188 majorAxisDistance(direction, source, rect2), 189 minorAxisDistance(direction, source, rect2))); 190 } 191 192 /** 193 * One rectangle may be another candidate than another by virtue of being 194 * exclusively in the beam of the source rect. 195 * @return Whether rect1 is a better candidate than rect2 by virtue of it being in src's 196 * beam 197 */ beamBeats(int direction, Rect source, Rect rect1, Rect rect2)198 boolean beamBeats(int direction, Rect source, Rect rect1, Rect rect2) { 199 final boolean rect1InSrcBeam = beamsOverlap(direction, source, rect1); 200 final boolean rect2InSrcBeam = beamsOverlap(direction, source, rect2); 201 202 // if rect1 isn't exclusively in the src beam, it doesn't win 203 if (rect2InSrcBeam || !rect1InSrcBeam) { 204 return false; 205 } 206 207 // we know rect1 is in the beam, and rect2 is not 208 209 // if rect1 is to the direction of, and rect2 is not, rect1 wins. 210 // for example, for direction left, if rect1 is to the left of the source 211 // and rect2 is below, then we always prefer the in beam rect1, since rect2 212 // could be reached by going down. 213 if (!isToDirectionOf(direction, source, rect2)) { 214 return true; 215 } 216 217 // for horizontal directions, being exclusively in beam always wins 218 if ((direction == View.FOCUS_LEFT || direction == View.FOCUS_RIGHT)) { 219 return true; 220 } 221 222 // for vertical directions, beams only beat up to a point: 223 // now, as long as rect2 isn't completely closer, rect1 wins 224 // e.g for direction down, completely closer means for rect2's top 225 // edge to be closer to the source's top edge than rect1's bottom edge. 226 return (majorAxisDistance(direction, source, rect1) 227 < majorAxisDistanceToFarEdge(direction, source, rect2)); 228 } 229 230 /** 231 * Fudge-factor opportunity: how to calculate distance given major and minor 232 * axis distances. Warning: this fudge factor is finely tuned, be sure to 233 * run all focus tests if you dare tweak it. 234 */ getWeightedDistanceFor(int majorAxisDistance, int minorAxisDistance)235 int getWeightedDistanceFor(int majorAxisDistance, int minorAxisDistance) { 236 return 13 * majorAxisDistance * majorAxisDistance 237 + minorAxisDistance * minorAxisDistance; 238 } 239 240 /** 241 * Is destRect a candidate for the next focus given the direction? This 242 * checks whether the dest is at least partially to the direction of (e.g left of) 243 * from source. 244 * 245 * Includes an edge case for an empty rect (which is used in some cases when 246 * searching from a point on the screen). 247 */ isCandidate(Rect srcRect, Rect destRect, int direction)248 boolean isCandidate(Rect srcRect, Rect destRect, int direction) { 249 switch (direction) { 250 case View.FOCUS_LEFT: 251 return (srcRect.right > destRect.right || srcRect.left >= destRect.right) 252 && srcRect.left > destRect.left; 253 case View.FOCUS_RIGHT: 254 return (srcRect.left < destRect.left || srcRect.right <= destRect.left) 255 && srcRect.right < destRect.right; 256 case View.FOCUS_UP: 257 return (srcRect.bottom > destRect.bottom || srcRect.top >= destRect.bottom) 258 && srcRect.top > destRect.top; 259 case View.FOCUS_DOWN: 260 return (srcRect.top < destRect.top || srcRect.bottom <= destRect.top) 261 && srcRect.bottom < destRect.bottom; 262 } 263 throw new IllegalArgumentException("direction must be one of " 264 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 265 } 266 267 268 /** 269 * Do the "beams" w.r.t the given direcition's axos of rect1 and rect2 overlap? 270 * @param direction the direction (up, down, left, right) 271 * @param rect1 The first rectangle 272 * @param rect2 The second rectangle 273 * @return whether the beams overlap 274 */ beamsOverlap(int direction, Rect rect1, Rect rect2)275 boolean beamsOverlap(int direction, Rect rect1, Rect rect2) { 276 switch (direction) { 277 case View.FOCUS_LEFT: 278 case View.FOCUS_RIGHT: 279 return (rect2.bottom >= rect1.top) && (rect2.top <= rect1.bottom); 280 case View.FOCUS_UP: 281 case View.FOCUS_DOWN: 282 return (rect2.right >= rect1.left) && (rect2.left <= rect1.right); 283 } 284 throw new IllegalArgumentException("direction must be one of " 285 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 286 } 287 288 /** 289 * e.g for left, is 'to left of' 290 */ isToDirectionOf(int direction, Rect src, Rect dest)291 boolean isToDirectionOf(int direction, Rect src, Rect dest) { 292 switch (direction) { 293 case View.FOCUS_LEFT: 294 return src.left >= dest.right; 295 case View.FOCUS_RIGHT: 296 return src.right <= dest.left; 297 case View.FOCUS_UP: 298 return src.top >= dest.bottom; 299 case View.FOCUS_DOWN: 300 return src.bottom <= dest.top; 301 } 302 throw new IllegalArgumentException("direction must be one of " 303 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 304 } 305 306 /** 307 * @return The distance from the edge furthest in the given direction 308 * of source to the edge nearest in the given direction of dest. If the 309 * dest is not in the direction from source, return 0. 310 */ majorAxisDistance(int direction, Rect source, Rect dest)311 static int majorAxisDistance(int direction, Rect source, Rect dest) { 312 return Math.max(0, majorAxisDistanceRaw(direction, source, dest)); 313 } 314 majorAxisDistanceRaw(int direction, Rect source, Rect dest)315 static int majorAxisDistanceRaw(int direction, Rect source, Rect dest) { 316 switch (direction) { 317 case View.FOCUS_LEFT: 318 return source.left - dest.right; 319 case View.FOCUS_RIGHT: 320 return dest.left - source.right; 321 case View.FOCUS_UP: 322 return source.top - dest.bottom; 323 case View.FOCUS_DOWN: 324 return dest.top - source.bottom; 325 } 326 throw new IllegalArgumentException("direction must be one of " 327 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 328 } 329 330 /** 331 * @return The distance along the major axis w.r.t the direction from the 332 * edge of source to the far edge of dest. If the 333 * dest is not in the direction from source, return 1 (to break ties with 334 * {@link #majorAxisDistance}). 335 */ majorAxisDistanceToFarEdge(int direction, Rect source, Rect dest)336 static int majorAxisDistanceToFarEdge(int direction, Rect source, Rect dest) { 337 return Math.max(1, majorAxisDistanceToFarEdgeRaw(direction, source, dest)); 338 } 339 majorAxisDistanceToFarEdgeRaw(int direction, Rect source, Rect dest)340 static int majorAxisDistanceToFarEdgeRaw(int direction, Rect source, Rect dest) { 341 switch (direction) { 342 case View.FOCUS_LEFT: 343 return source.left - dest.left; 344 case View.FOCUS_RIGHT: 345 return dest.right - source.right; 346 case View.FOCUS_UP: 347 return source.top - dest.top; 348 case View.FOCUS_DOWN: 349 return dest.bottom - source.bottom; 350 } 351 throw new IllegalArgumentException("direction must be one of " 352 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 353 } 354 355 /** 356 * Find the distance on the minor axis w.r.t the direction to the nearest 357 * edge of the destination rectange. 358 * @param direction the direction (up, down, left, right) 359 * @param source The source rect. 360 * @param dest The destination rect. 361 * @return The distance. 362 */ minorAxisDistance(int direction, Rect source, Rect dest)363 static int minorAxisDistance(int direction, Rect source, Rect dest) { 364 switch (direction) { 365 case View.FOCUS_LEFT: 366 case View.FOCUS_RIGHT: 367 // the distance between the center verticals 368 return Math.abs( 369 ((source.top + source.height() / 2) - 370 ((dest.top + dest.height() / 2)))); 371 case View.FOCUS_UP: 372 case View.FOCUS_DOWN: 373 // the distance between the center horizontals 374 return Math.abs( 375 ((source.left + source.width() / 2) - 376 ((dest.left + dest.width() / 2)))); 377 } 378 throw new IllegalArgumentException("direction must be one of " 379 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 380 } 381 382 /** 383 * Find the nearest touchable view to the specified view. 384 * 385 * @param root The root of the tree in which to search 386 * @param x X coordinate from which to start the search 387 * @param y Y coordinate from which to start the search 388 * @param direction Direction to look 389 * @param deltas Offset from the <x, y> to the edge of the nearest view. Note that this array 390 * may already be populated with values. 391 * @return The nearest touchable view, or null if none exists. 392 */ findNearestTouchable(ViewGroup root, int x, int y, int direction, int[] deltas)393 public View findNearestTouchable(ViewGroup root, int x, int y, int direction, int[] deltas) { 394 ArrayList<View> touchables = root.getTouchables(); 395 int minDistance = Integer.MAX_VALUE; 396 View closest = null; 397 398 int numTouchables = touchables.size(); 399 400 int edgeSlop = ViewConfiguration.get(root.mContext).getScaledEdgeSlop(); 401 402 Rect closestBounds = new Rect(); 403 Rect touchableBounds = mOtherRect; 404 405 for (int i = 0; i < numTouchables; i++) { 406 View touchable = touchables.get(i); 407 408 // get visible bounds of other view in same coordinate system 409 touchable.getDrawingRect(touchableBounds); 410 411 root.offsetRectBetweenParentAndChild(touchable, touchableBounds, true, true); 412 413 if (!isTouchCandidate(x, y, touchableBounds, direction)) { 414 continue; 415 } 416 417 int distance = Integer.MAX_VALUE; 418 419 switch (direction) { 420 case View.FOCUS_LEFT: 421 distance = x - touchableBounds.right + 1; 422 break; 423 case View.FOCUS_RIGHT: 424 distance = touchableBounds.left; 425 break; 426 case View.FOCUS_UP: 427 distance = y - touchableBounds.bottom + 1; 428 break; 429 case View.FOCUS_DOWN: 430 distance = touchableBounds.top; 431 break; 432 } 433 434 if (distance < edgeSlop) { 435 // Give preference to innermost views 436 if (closest == null || 437 closestBounds.contains(touchableBounds) || 438 (!touchableBounds.contains(closestBounds) && distance < minDistance)) { 439 minDistance = distance; 440 closest = touchable; 441 closestBounds.set(touchableBounds); 442 switch (direction) { 443 case View.FOCUS_LEFT: 444 deltas[0] = -distance; 445 break; 446 case View.FOCUS_RIGHT: 447 deltas[0] = distance; 448 break; 449 case View.FOCUS_UP: 450 deltas[1] = -distance; 451 break; 452 case View.FOCUS_DOWN: 453 deltas[1] = distance; 454 break; 455 } 456 } 457 } 458 } 459 return closest; 460 } 461 462 463 /** 464 * Is destRect a candidate for the next touch given the direction? 465 */ isTouchCandidate(int x, int y, Rect destRect, int direction)466 private boolean isTouchCandidate(int x, int y, Rect destRect, int direction) { 467 switch (direction) { 468 case View.FOCUS_LEFT: 469 return destRect.left <= x && destRect.top <= y && y <= destRect.bottom; 470 case View.FOCUS_RIGHT: 471 return destRect.left >= x && destRect.top <= y && y <= destRect.bottom; 472 case View.FOCUS_UP: 473 return destRect.top <= y && destRect.left <= x && x <= destRect.right; 474 case View.FOCUS_DOWN: 475 return destRect.top >= y && destRect.left <= x && x <= destRect.right; 476 } 477 throw new IllegalArgumentException("direction must be one of " 478 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 479 } 480 } 481