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