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