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