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.annotation.NonNull; 20 import android.annotation.Nullable; 21 import android.annotation.TestApi; 22 import android.content.pm.PackageManager; 23 import android.graphics.Rect; 24 import android.util.ArrayMap; 25 import android.util.ArraySet; 26 27 import java.util.ArrayList; 28 import java.util.Arrays; 29 import java.util.Collections; 30 import java.util.Comparator; 31 import java.util.HashMap; 32 import java.util.List; 33 34 /** 35 * The algorithm used for finding the next focusable view in a given direction 36 * from a view that currently has focus. 37 */ 38 public class FocusFinder { 39 40 private static final ThreadLocal<FocusFinder> tlFocusFinder = 41 new ThreadLocal<FocusFinder>() { 42 @Override 43 protected FocusFinder initialValue() { 44 return new FocusFinder(); 45 } 46 }; 47 48 /** 49 * Get the focus finder for this thread. 50 */ 51 public static FocusFinder getInstance() { 52 return tlFocusFinder.get(); 53 } 54 55 final Rect mFocusedRect = new Rect(); 56 final Rect mOtherRect = new Rect(); 57 final Rect mBestCandidateRect = new Rect(); 58 private final UserSpecifiedFocusComparator mUserSpecifiedFocusComparator = 59 new UserSpecifiedFocusComparator((r, v) -> isValidId(v.getNextFocusForwardId()) 60 ? v.findUserSetNextFocus(r, View.FOCUS_FORWARD) : null); 61 private final UserSpecifiedFocusComparator mUserSpecifiedClusterComparator = 62 new UserSpecifiedFocusComparator((r, v) -> isValidId(v.getNextClusterForwardId()) 63 ? v.findUserSetNextKeyboardNavigationCluster(r, View.FOCUS_FORWARD) : null); 64 private final FocusSorter mFocusSorter = new FocusSorter(); 65 66 private final ArrayList<View> mTempList = new ArrayList<View>(); 67 68 // enforce thread local access 69 private FocusFinder() {} 70 71 /** 72 * Find the next view to take focus in root's descendants, starting from the view 73 * that currently is focused. 74 * @param root Contains focused. Cannot be null. 75 * @param focused Has focus now. 76 * @param direction Direction to look. 77 * @return The next focusable view, or null if none exists. 78 */ 79 public final View findNextFocus(ViewGroup root, View focused, int direction) { 80 return findNextFocus(root, focused, null, direction); 81 } 82 83 /** 84 * Find the next view to take focus in root's descendants, searching from 85 * a particular rectangle in root's coordinates. 86 * @param root Contains focusedRect. Cannot be null. 87 * @param focusedRect The starting point of the search. 88 * @param direction Direction to look. 89 * @return The next focusable view, or null if none exists. 90 */ 91 public View findNextFocusFromRect(ViewGroup root, Rect focusedRect, int direction) { 92 mFocusedRect.set(focusedRect); 93 return findNextFocus(root, null, mFocusedRect, direction); 94 } 95 96 private View findNextFocus(ViewGroup root, View focused, Rect focusedRect, int direction) { 97 View next = null; 98 ViewGroup effectiveRoot = getEffectiveRoot(root, focused); 99 if (focused != null) { 100 next = findNextUserSpecifiedFocus(effectiveRoot, focused, direction); 101 } 102 if (next != null) { 103 return next; 104 } 105 ArrayList<View> focusables = mTempList; 106 try { 107 focusables.clear(); 108 effectiveRoot.addFocusables(focusables, direction); 109 if (!focusables.isEmpty()) { 110 next = findNextFocus(effectiveRoot, focused, focusedRect, direction, focusables); 111 } 112 } finally { 113 focusables.clear(); 114 } 115 return next; 116 } 117 118 /** 119 * Returns the "effective" root of a view. The "effective" root is the closest ancestor 120 * within-which focus should cycle. 121 * <p> 122 * For example: normal focus navigation would stay within a ViewGroup marked as 123 * touchscreenBlocksFocus and keyboardNavigationCluster until a cluster-jump out. 124 * @return the "effective" root of {@param focused} 125 */ 126 private ViewGroup getEffectiveRoot(ViewGroup root, View focused) { 127 if (focused == null || focused == root) { 128 return root; 129 } 130 ViewGroup effective = null; 131 ViewParent nextParent = focused.getParent(); 132 do { 133 if (nextParent == root) { 134 return effective != null ? effective : root; 135 } 136 ViewGroup vg = (ViewGroup) nextParent; 137 if (vg.getTouchscreenBlocksFocus() 138 && focused.getContext().getPackageManager().hasSystemFeature( 139 PackageManager.FEATURE_TOUCHSCREEN) 140 && vg.isKeyboardNavigationCluster()) { 141 // Don't stop and return here because the cluster could be nested and we only 142 // care about the top-most one. 143 effective = vg; 144 } 145 nextParent = nextParent.getParent(); 146 } while (nextParent instanceof ViewGroup); 147 return root; 148 } 149 150 /** 151 * Find the root of the next keyboard navigation cluster after the current one. 152 * @param root The view tree to look inside. Cannot be null 153 * @param currentCluster The starting point of the search. Null means the default cluster 154 * @param direction Direction to look 155 * @return The next cluster, or null if none exists 156 */ 157 public View findNextKeyboardNavigationCluster( 158 @NonNull View root, 159 @Nullable View currentCluster, 160 @View.FocusDirection int direction) { 161 View next = null; 162 if (currentCluster != null) { 163 next = findNextUserSpecifiedKeyboardNavigationCluster(root, currentCluster, direction); 164 if (next != null) { 165 return next; 166 } 167 } 168 169 final ArrayList<View> clusters = mTempList; 170 try { 171 clusters.clear(); 172 root.addKeyboardNavigationClusters(clusters, direction); 173 if (!clusters.isEmpty()) { 174 next = findNextKeyboardNavigationCluster( 175 root, currentCluster, clusters, direction); 176 } 177 } finally { 178 clusters.clear(); 179 } 180 return next; 181 } 182 183 private View findNextUserSpecifiedKeyboardNavigationCluster(View root, View currentCluster, 184 int direction) { 185 View userSetNextCluster = 186 currentCluster.findUserSetNextKeyboardNavigationCluster(root, direction); 187 if (userSetNextCluster != null && userSetNextCluster.hasFocusable()) { 188 return userSetNextCluster; 189 } 190 return null; 191 } 192 193 private View findNextUserSpecifiedFocus(ViewGroup root, View focused, int direction) { 194 // check for user specified next focus 195 View userSetNextFocus = focused.findUserSetNextFocus(root, direction); 196 View cycleCheck = userSetNextFocus; 197 boolean cycleStep = true; // we want the first toggle to yield false 198 while (userSetNextFocus != null) { 199 if (userSetNextFocus.isFocusable() 200 && userSetNextFocus.getVisibility() == View.VISIBLE 201 && (!userSetNextFocus.isInTouchMode() 202 || userSetNextFocus.isFocusableInTouchMode())) { 203 return userSetNextFocus; 204 } 205 userSetNextFocus = userSetNextFocus.findUserSetNextFocus(root, direction); 206 if (cycleStep = !cycleStep) { 207 cycleCheck = cycleCheck.findUserSetNextFocus(root, direction); 208 if (cycleCheck == userSetNextFocus) { 209 // found a cycle, user-specified focus forms a loop and none of the views 210 // are currently focusable. 211 break; 212 } 213 } 214 } 215 return null; 216 } 217 218 private View findNextFocus(ViewGroup root, View focused, Rect focusedRect, 219 int direction, ArrayList<View> focusables) { 220 if (focused != null) { 221 if (focusedRect == null) { 222 focusedRect = mFocusedRect; 223 } 224 // fill in interesting rect from focused 225 focused.getFocusedRect(focusedRect); 226 root.offsetDescendantRectToMyCoords(focused, focusedRect); 227 } else { 228 if (focusedRect == null) { 229 focusedRect = mFocusedRect; 230 // make up a rect at top left or bottom right of root 231 switch (direction) { 232 case View.FOCUS_RIGHT: 233 case View.FOCUS_DOWN: 234 setFocusTopLeft(root, focusedRect); 235 break; 236 case View.FOCUS_FORWARD: 237 if (root.isLayoutRtl()) { 238 setFocusBottomRight(root, focusedRect); 239 } else { 240 setFocusTopLeft(root, focusedRect); 241 } 242 break; 243 244 case View.FOCUS_LEFT: 245 case View.FOCUS_UP: 246 setFocusBottomRight(root, focusedRect); 247 break; 248 case View.FOCUS_BACKWARD: 249 if (root.isLayoutRtl()) { 250 setFocusTopLeft(root, focusedRect); 251 } else { 252 setFocusBottomRight(root, focusedRect); 253 break; 254 } 255 } 256 } 257 } 258 259 switch (direction) { 260 case View.FOCUS_FORWARD: 261 case View.FOCUS_BACKWARD: 262 return findNextFocusInRelativeDirection(focusables, root, focused, focusedRect, 263 direction); 264 case View.FOCUS_UP: 265 case View.FOCUS_DOWN: 266 case View.FOCUS_LEFT: 267 case View.FOCUS_RIGHT: 268 return findNextFocusInAbsoluteDirection(focusables, root, focused, 269 focusedRect, direction); 270 default: 271 throw new IllegalArgumentException("Unknown direction: " + direction); 272 } 273 } 274 275 private View findNextKeyboardNavigationCluster( 276 View root, 277 View currentCluster, 278 List<View> clusters, 279 @View.FocusDirection int direction) { 280 try { 281 // Note: This sort is stable. 282 mUserSpecifiedClusterComparator.setFocusables(clusters, root); 283 Collections.sort(clusters, mUserSpecifiedClusterComparator); 284 } finally { 285 mUserSpecifiedClusterComparator.recycle(); 286 } 287 final int count = clusters.size(); 288 289 switch (direction) { 290 case View.FOCUS_FORWARD: 291 case View.FOCUS_DOWN: 292 case View.FOCUS_RIGHT: 293 return getNextKeyboardNavigationCluster(root, currentCluster, clusters, count); 294 case View.FOCUS_BACKWARD: 295 case View.FOCUS_UP: 296 case View.FOCUS_LEFT: 297 return getPreviousKeyboardNavigationCluster(root, currentCluster, clusters, count); 298 default: 299 throw new IllegalArgumentException("Unknown direction: " + direction); 300 } 301 } 302 303 private View findNextFocusInRelativeDirection(ArrayList<View> focusables, ViewGroup root, 304 View focused, Rect focusedRect, int direction) { 305 try { 306 // Note: This sort is stable. 307 mUserSpecifiedFocusComparator.setFocusables(focusables, root); 308 Collections.sort(focusables, mUserSpecifiedFocusComparator); 309 } finally { 310 mUserSpecifiedFocusComparator.recycle(); 311 } 312 313 final int count = focusables.size(); 314 switch (direction) { 315 case View.FOCUS_FORWARD: 316 return getNextFocusable(focused, focusables, count); 317 case View.FOCUS_BACKWARD: 318 return getPreviousFocusable(focused, focusables, count); 319 } 320 return focusables.get(count - 1); 321 } 322 323 private void setFocusBottomRight(ViewGroup root, Rect focusedRect) { 324 final int rootBottom = root.getScrollY() + root.getHeight(); 325 final int rootRight = root.getScrollX() + root.getWidth(); 326 focusedRect.set(rootRight, rootBottom, rootRight, rootBottom); 327 } 328 329 private void setFocusTopLeft(ViewGroup root, Rect focusedRect) { 330 final int rootTop = root.getScrollY(); 331 final int rootLeft = root.getScrollX(); 332 focusedRect.set(rootLeft, rootTop, rootLeft, rootTop); 333 } 334 335 View findNextFocusInAbsoluteDirection(ArrayList<View> focusables, ViewGroup root, View focused, 336 Rect focusedRect, int direction) { 337 // initialize the best candidate to something impossible 338 // (so the first plausible view will become the best choice) 339 mBestCandidateRect.set(focusedRect); 340 switch(direction) { 341 case View.FOCUS_LEFT: 342 mBestCandidateRect.offset(focusedRect.width() + 1, 0); 343 break; 344 case View.FOCUS_RIGHT: 345 mBestCandidateRect.offset(-(focusedRect.width() + 1), 0); 346 break; 347 case View.FOCUS_UP: 348 mBestCandidateRect.offset(0, focusedRect.height() + 1); 349 break; 350 case View.FOCUS_DOWN: 351 mBestCandidateRect.offset(0, -(focusedRect.height() + 1)); 352 } 353 354 View closest = null; 355 356 int numFocusables = focusables.size(); 357 for (int i = 0; i < numFocusables; i++) { 358 View focusable = focusables.get(i); 359 360 // only interested in other non-root views 361 if (focusable == focused || focusable == root) continue; 362 363 // get focus bounds of other view in same coordinate system 364 focusable.getFocusedRect(mOtherRect); 365 root.offsetDescendantRectToMyCoords(focusable, mOtherRect); 366 367 if (isBetterCandidate(direction, focusedRect, mOtherRect, mBestCandidateRect)) { 368 mBestCandidateRect.set(mOtherRect); 369 closest = focusable; 370 } 371 } 372 return closest; 373 } 374 375 private static View getNextFocusable(View focused, ArrayList<View> focusables, int count) { 376 if (focused != null) { 377 int position = focusables.lastIndexOf(focused); 378 if (position >= 0 && position + 1 < count) { 379 return focusables.get(position + 1); 380 } 381 } 382 if (!focusables.isEmpty()) { 383 return focusables.get(0); 384 } 385 return null; 386 } 387 388 private static View getPreviousFocusable(View focused, ArrayList<View> focusables, int count) { 389 if (focused != null) { 390 int position = focusables.indexOf(focused); 391 if (position > 0) { 392 return focusables.get(position - 1); 393 } 394 } 395 if (!focusables.isEmpty()) { 396 return focusables.get(count - 1); 397 } 398 return null; 399 } 400 401 private static View getNextKeyboardNavigationCluster( 402 View root, 403 View currentCluster, 404 List<View> clusters, 405 int count) { 406 if (currentCluster == null) { 407 // The current cluster is the default one. 408 // The next cluster after the default one is the first one. 409 // Note that the caller guarantees that 'clusters' is not empty. 410 return clusters.get(0); 411 } 412 413 final int position = clusters.lastIndexOf(currentCluster); 414 if (position >= 0 && position + 1 < count) { 415 // Return the next non-default cluster if we can find it. 416 return clusters.get(position + 1); 417 } 418 419 // The current cluster is the last one. The next one is the default one, i.e. the 420 // root. 421 return root; 422 } 423 424 private static View getPreviousKeyboardNavigationCluster( 425 View root, 426 View currentCluster, 427 List<View> clusters, 428 int count) { 429 if (currentCluster == null) { 430 // The current cluster is the default one. 431 // The previous cluster before the default one is the last one. 432 // Note that the caller guarantees that 'clusters' is not empty. 433 return clusters.get(count - 1); 434 } 435 436 final int position = clusters.indexOf(currentCluster); 437 if (position > 0) { 438 // Return the previous non-default cluster if we can find it. 439 return clusters.get(position - 1); 440 } 441 442 // The current cluster is the first one. The previous one is the default one, i.e. 443 // the root. 444 return root; 445 } 446 447 /** 448 * Is rect1 a better candidate than rect2 for a focus search in a particular 449 * direction from a source rect? This is the core routine that determines 450 * the order of focus searching. 451 * @param direction the direction (up, down, left, right) 452 * @param source The source we are searching from 453 * @param rect1 The candidate rectangle 454 * @param rect2 The current best candidate. 455 * @return Whether the candidate is the new best. 456 */ 457 boolean isBetterCandidate(int direction, Rect source, Rect rect1, Rect rect2) { 458 459 // to be a better candidate, need to at least be a candidate in the first 460 // place :) 461 if (!isCandidate(source, rect1, direction)) { 462 return false; 463 } 464 465 // we know that rect1 is a candidate.. if rect2 is not a candidate, 466 // rect1 is better 467 if (!isCandidate(source, rect2, direction)) { 468 return true; 469 } 470 471 // if rect1 is better by beam, it wins 472 if (beamBeats(direction, source, rect1, rect2)) { 473 return true; 474 } 475 476 // if rect2 is better, then rect1 cant' be :) 477 if (beamBeats(direction, source, rect2, rect1)) { 478 return false; 479 } 480 481 // otherwise, do fudge-tastic comparison of the major and minor axis 482 return (getWeightedDistanceFor( 483 majorAxisDistance(direction, source, rect1), 484 minorAxisDistance(direction, source, rect1)) 485 < getWeightedDistanceFor( 486 majorAxisDistance(direction, source, rect2), 487 minorAxisDistance(direction, source, rect2))); 488 } 489 490 /** 491 * One rectangle may be another candidate than another by virtue of being 492 * exclusively in the beam of the source rect. 493 * @return Whether rect1 is a better candidate than rect2 by virtue of it being in src's 494 * beam 495 */ 496 boolean beamBeats(int direction, Rect source, Rect rect1, Rect rect2) { 497 final boolean rect1InSrcBeam = beamsOverlap(direction, source, rect1); 498 final boolean rect2InSrcBeam = beamsOverlap(direction, source, rect2); 499 500 // if rect1 isn't exclusively in the src beam, it doesn't win 501 if (rect2InSrcBeam || !rect1InSrcBeam) { 502 return false; 503 } 504 505 // we know rect1 is in the beam, and rect2 is not 506 507 // if rect1 is to the direction of, and rect2 is not, rect1 wins. 508 // for example, for direction left, if rect1 is to the left of the source 509 // and rect2 is below, then we always prefer the in beam rect1, since rect2 510 // could be reached by going down. 511 if (!isToDirectionOf(direction, source, rect2)) { 512 return true; 513 } 514 515 // for horizontal directions, being exclusively in beam always wins 516 if ((direction == View.FOCUS_LEFT || direction == View.FOCUS_RIGHT)) { 517 return true; 518 } 519 520 // for vertical directions, beams only beat up to a point: 521 // now, as long as rect2 isn't completely closer, rect1 wins 522 // e.g for direction down, completely closer means for rect2's top 523 // edge to be closer to the source's top edge than rect1's bottom edge. 524 return (majorAxisDistance(direction, source, rect1) 525 < majorAxisDistanceToFarEdge(direction, source, rect2)); 526 } 527 528 /** 529 * Fudge-factor opportunity: how to calculate distance given major and minor 530 * axis distances. Warning: this fudge factor is finely tuned, be sure to 531 * run all focus tests if you dare tweak it. 532 */ 533 long getWeightedDistanceFor(long majorAxisDistance, long minorAxisDistance) { 534 return 13 * majorAxisDistance * majorAxisDistance 535 + minorAxisDistance * minorAxisDistance; 536 } 537 538 /** 539 * Is destRect a candidate for the next focus given the direction? This 540 * checks whether the dest is at least partially to the direction of (e.g left of) 541 * from source. 542 * 543 * Includes an edge case for an empty rect (which is used in some cases when 544 * searching from a point on the screen). 545 */ 546 boolean isCandidate(Rect srcRect, Rect destRect, int direction) { 547 switch (direction) { 548 case View.FOCUS_LEFT: 549 return (srcRect.right > destRect.right || srcRect.left >= destRect.right) 550 && srcRect.left > destRect.left; 551 case View.FOCUS_RIGHT: 552 return (srcRect.left < destRect.left || srcRect.right <= destRect.left) 553 && srcRect.right < destRect.right; 554 case View.FOCUS_UP: 555 return (srcRect.bottom > destRect.bottom || srcRect.top >= destRect.bottom) 556 && srcRect.top > destRect.top; 557 case View.FOCUS_DOWN: 558 return (srcRect.top < destRect.top || srcRect.bottom <= destRect.top) 559 && srcRect.bottom < destRect.bottom; 560 } 561 throw new IllegalArgumentException("direction must be one of " 562 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 563 } 564 565 566 /** 567 * Do the "beams" w.r.t the given direction's axis of rect1 and rect2 overlap? 568 * @param direction the direction (up, down, left, right) 569 * @param rect1 The first rectangle 570 * @param rect2 The second rectangle 571 * @return whether the beams overlap 572 */ 573 boolean beamsOverlap(int direction, Rect rect1, Rect rect2) { 574 switch (direction) { 575 case View.FOCUS_LEFT: 576 case View.FOCUS_RIGHT: 577 return (rect2.bottom > rect1.top) && (rect2.top < rect1.bottom); 578 case View.FOCUS_UP: 579 case View.FOCUS_DOWN: 580 return (rect2.right > rect1.left) && (rect2.left < rect1.right); 581 } 582 throw new IllegalArgumentException("direction must be one of " 583 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 584 } 585 586 /** 587 * e.g for left, is 'to left of' 588 */ 589 boolean isToDirectionOf(int direction, Rect src, Rect dest) { 590 switch (direction) { 591 case View.FOCUS_LEFT: 592 return src.left >= dest.right; 593 case View.FOCUS_RIGHT: 594 return src.right <= dest.left; 595 case View.FOCUS_UP: 596 return src.top >= dest.bottom; 597 case View.FOCUS_DOWN: 598 return src.bottom <= dest.top; 599 } 600 throw new IllegalArgumentException("direction must be one of " 601 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 602 } 603 604 /** 605 * @return The distance from the edge furthest in the given direction 606 * of source to the edge nearest in the given direction of dest. If the 607 * dest is not in the direction from source, return 0. 608 */ 609 static int majorAxisDistance(int direction, Rect source, Rect dest) { 610 return Math.max(0, majorAxisDistanceRaw(direction, source, dest)); 611 } 612 613 static int majorAxisDistanceRaw(int direction, Rect source, Rect dest) { 614 switch (direction) { 615 case View.FOCUS_LEFT: 616 return source.left - dest.right; 617 case View.FOCUS_RIGHT: 618 return dest.left - source.right; 619 case View.FOCUS_UP: 620 return source.top - dest.bottom; 621 case View.FOCUS_DOWN: 622 return dest.top - source.bottom; 623 } 624 throw new IllegalArgumentException("direction must be one of " 625 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 626 } 627 628 /** 629 * @return The distance along the major axis w.r.t the direction from the 630 * edge of source to the far edge of dest. If the 631 * dest is not in the direction from source, return 1 (to break ties with 632 * {@link #majorAxisDistance}). 633 */ 634 static int majorAxisDistanceToFarEdge(int direction, Rect source, Rect dest) { 635 return Math.max(1, majorAxisDistanceToFarEdgeRaw(direction, source, dest)); 636 } 637 638 static int majorAxisDistanceToFarEdgeRaw(int direction, Rect source, Rect dest) { 639 switch (direction) { 640 case View.FOCUS_LEFT: 641 return source.left - dest.left; 642 case View.FOCUS_RIGHT: 643 return dest.right - source.right; 644 case View.FOCUS_UP: 645 return source.top - dest.top; 646 case View.FOCUS_DOWN: 647 return dest.bottom - source.bottom; 648 } 649 throw new IllegalArgumentException("direction must be one of " 650 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 651 } 652 653 /** 654 * Find the distance on the minor axis w.r.t the direction to the nearest 655 * edge of the destination rectangle. 656 * @param direction the direction (up, down, left, right) 657 * @param source The source rect. 658 * @param dest The destination rect. 659 * @return The distance. 660 */ 661 static int minorAxisDistance(int direction, Rect source, Rect dest) { 662 switch (direction) { 663 case View.FOCUS_LEFT: 664 case View.FOCUS_RIGHT: 665 // the distance between the center verticals 666 return Math.abs( 667 ((source.top + source.height() / 2) - 668 ((dest.top + dest.height() / 2)))); 669 case View.FOCUS_UP: 670 case View.FOCUS_DOWN: 671 // the distance between the center horizontals 672 return Math.abs( 673 ((source.left + source.width() / 2) - 674 ((dest.left + dest.width() / 2)))); 675 } 676 throw new IllegalArgumentException("direction must be one of " 677 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 678 } 679 680 /** 681 * Find the nearest touchable view to the specified view. 682 * 683 * @param root The root of the tree in which to search 684 * @param x X coordinate from which to start the search 685 * @param y Y coordinate from which to start the search 686 * @param direction Direction to look 687 * @param deltas Offset from the <x, y> to the edge of the nearest view. Note that this array 688 * may already be populated with values. 689 * @return The nearest touchable view, or null if none exists. 690 */ 691 public View findNearestTouchable(ViewGroup root, int x, int y, int direction, int[] deltas) { 692 ArrayList<View> touchables = root.getTouchables(); 693 int minDistance = Integer.MAX_VALUE; 694 View closest = null; 695 696 int numTouchables = touchables.size(); 697 698 int edgeSlop = ViewConfiguration.get(root.mContext).getScaledEdgeSlop(); 699 700 Rect closestBounds = new Rect(); 701 Rect touchableBounds = mOtherRect; 702 703 for (int i = 0; i < numTouchables; i++) { 704 View touchable = touchables.get(i); 705 706 // get visible bounds of other view in same coordinate system 707 touchable.getDrawingRect(touchableBounds); 708 709 root.offsetRectBetweenParentAndChild(touchable, touchableBounds, true, true); 710 711 if (!isTouchCandidate(x, y, touchableBounds, direction)) { 712 continue; 713 } 714 715 int distance = Integer.MAX_VALUE; 716 717 switch (direction) { 718 case View.FOCUS_LEFT: 719 distance = x - touchableBounds.right + 1; 720 break; 721 case View.FOCUS_RIGHT: 722 distance = touchableBounds.left; 723 break; 724 case View.FOCUS_UP: 725 distance = y - touchableBounds.bottom + 1; 726 break; 727 case View.FOCUS_DOWN: 728 distance = touchableBounds.top; 729 break; 730 } 731 732 if (distance < edgeSlop) { 733 // Give preference to innermost views 734 if (closest == null || 735 closestBounds.contains(touchableBounds) || 736 (!touchableBounds.contains(closestBounds) && distance < minDistance)) { 737 minDistance = distance; 738 closest = touchable; 739 closestBounds.set(touchableBounds); 740 switch (direction) { 741 case View.FOCUS_LEFT: 742 deltas[0] = -distance; 743 break; 744 case View.FOCUS_RIGHT: 745 deltas[0] = distance; 746 break; 747 case View.FOCUS_UP: 748 deltas[1] = -distance; 749 break; 750 case View.FOCUS_DOWN: 751 deltas[1] = distance; 752 break; 753 } 754 } 755 } 756 } 757 return closest; 758 } 759 760 761 /** 762 * Is destRect a candidate for the next touch given the direction? 763 */ 764 private boolean isTouchCandidate(int x, int y, Rect destRect, int direction) { 765 switch (direction) { 766 case View.FOCUS_LEFT: 767 return destRect.left <= x && destRect.top <= y && y <= destRect.bottom; 768 case View.FOCUS_RIGHT: 769 return destRect.left >= x && destRect.top <= y && y <= destRect.bottom; 770 case View.FOCUS_UP: 771 return destRect.top <= y && destRect.left <= x && x <= destRect.right; 772 case View.FOCUS_DOWN: 773 return destRect.top >= y && destRect.left <= x && x <= destRect.right; 774 } 775 throw new IllegalArgumentException("direction must be one of " 776 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 777 } 778 779 private static final boolean isValidId(final int id) { 780 return id != 0 && id != View.NO_ID; 781 } 782 783 static final class FocusSorter { 784 private ArrayList<Rect> mRectPool = new ArrayList<>(); 785 private int mLastPoolRect; 786 private int mRtlMult; 787 private HashMap<View, Rect> mRectByView = null; 788 789 private Comparator<View> mTopsComparator = (first, second) -> { 790 if (first == second) { 791 return 0; 792 } 793 794 Rect firstRect = mRectByView.get(first); 795 Rect secondRect = mRectByView.get(second); 796 797 int result = firstRect.top - secondRect.top; 798 if (result == 0) { 799 return firstRect.bottom - secondRect.bottom; 800 } 801 return result; 802 }; 803 804 private Comparator<View> mSidesComparator = (first, second) -> { 805 if (first == second) { 806 return 0; 807 } 808 809 Rect firstRect = mRectByView.get(first); 810 Rect secondRect = mRectByView.get(second); 811 812 int result = firstRect.left - secondRect.left; 813 if (result == 0) { 814 return firstRect.right - secondRect.right; 815 } 816 return mRtlMult * result; 817 }; 818 819 public void sort(View[] views, int start, int end, ViewGroup root, boolean isRtl) { 820 int count = end - start; 821 if (count < 2) { 822 return; 823 } 824 if (mRectByView == null) { 825 mRectByView = new HashMap<>(); 826 } 827 mRtlMult = isRtl ? -1 : 1; 828 for (int i = mRectPool.size(); i < count; ++i) { 829 mRectPool.add(new Rect()); 830 } 831 for (int i = start; i < end; ++i) { 832 Rect next = mRectPool.get(mLastPoolRect++); 833 views[i].getDrawingRect(next); 834 root.offsetDescendantRectToMyCoords(views[i], next); 835 mRectByView.put(views[i], next); 836 } 837 838 // Sort top-to-bottom 839 Arrays.sort(views, start, count, mTopsComparator); 840 // Sweep top-to-bottom to identify rows 841 int sweepBottom = mRectByView.get(views[start]).bottom; 842 int rowStart = start; 843 int sweepIdx = start + 1; 844 for (; sweepIdx < end; ++sweepIdx) { 845 Rect currRect = mRectByView.get(views[sweepIdx]); 846 if (currRect.top >= sweepBottom) { 847 // Next view is on a new row, sort the row we've just finished left-to-right. 848 if ((sweepIdx - rowStart) > 1) { 849 Arrays.sort(views, rowStart, sweepIdx, mSidesComparator); 850 } 851 sweepBottom = currRect.bottom; 852 rowStart = sweepIdx; 853 } else { 854 // Next view vertically overlaps, we need to extend our "row height" 855 sweepBottom = Math.max(sweepBottom, currRect.bottom); 856 } 857 } 858 // Sort whatever's left (final row) left-to-right 859 if ((sweepIdx - rowStart) > 1) { 860 Arrays.sort(views, rowStart, sweepIdx, mSidesComparator); 861 } 862 863 mLastPoolRect = 0; 864 mRectByView.clear(); 865 } 866 } 867 868 /** 869 * Public for testing. 870 * 871 * @hide 872 */ 873 @TestApi 874 public static void sort(View[] views, int start, int end, ViewGroup root, boolean isRtl) { 875 getInstance().mFocusSorter.sort(views, start, end, root, isRtl); 876 } 877 878 /** 879 * Sorts views according to any explicitly-specified focus-chains. If there are no explicitly 880 * specified focus chains (eg. no nextFocusForward attributes defined), this should be a no-op. 881 */ 882 private static final class UserSpecifiedFocusComparator implements Comparator<View> { 883 private final ArrayMap<View, View> mNextFoci = new ArrayMap<>(); 884 private final ArraySet<View> mIsConnectedTo = new ArraySet<>(); 885 private final ArrayMap<View, View> mHeadsOfChains = new ArrayMap<View, View>(); 886 private final ArrayMap<View, Integer> mOriginalOrdinal = new ArrayMap<>(); 887 private final NextFocusGetter mNextFocusGetter; 888 private View mRoot; 889 890 public interface NextFocusGetter { 891 View get(View root, View view); 892 } 893 894 UserSpecifiedFocusComparator(NextFocusGetter nextFocusGetter) { 895 mNextFocusGetter = nextFocusGetter; 896 } 897 898 public void recycle() { 899 mRoot = null; 900 mHeadsOfChains.clear(); 901 mIsConnectedTo.clear(); 902 mOriginalOrdinal.clear(); 903 mNextFoci.clear(); 904 } 905 906 public void setFocusables(List<View> focusables, View root) { 907 mRoot = root; 908 for (int i = 0; i < focusables.size(); ++i) { 909 mOriginalOrdinal.put(focusables.get(i), i); 910 } 911 912 for (int i = focusables.size() - 1; i >= 0; i--) { 913 final View view = focusables.get(i); 914 final View next = mNextFocusGetter.get(mRoot, view); 915 if (next != null && mOriginalOrdinal.containsKey(next)) { 916 mNextFoci.put(view, next); 917 mIsConnectedTo.add(next); 918 } 919 } 920 921 for (int i = focusables.size() - 1; i >= 0; i--) { 922 final View view = focusables.get(i); 923 final View next = mNextFoci.get(view); 924 if (next != null && !mIsConnectedTo.contains(view)) { 925 setHeadOfChain(view); 926 } 927 } 928 } 929 930 private void setHeadOfChain(View head) { 931 for (View view = head; view != null; view = mNextFoci.get(view)) { 932 final View otherHead = mHeadsOfChains.get(view); 933 if (otherHead != null) { 934 if (otherHead == head) { 935 return; // This view has already had its head set properly 936 } 937 // A hydra -- multi-headed focus chain (e.g. A->C and B->C) 938 // Use the one we've already chosen instead and reset this chain. 939 view = head; 940 head = otherHead; 941 } 942 mHeadsOfChains.put(view, head); 943 } 944 } 945 946 public int compare(View first, View second) { 947 if (first == second) { 948 return 0; 949 } 950 // Order between views within a chain is immaterial -- next/previous is 951 // within a chain is handled elsewhere. 952 View firstHead = mHeadsOfChains.get(first); 953 View secondHead = mHeadsOfChains.get(second); 954 if (firstHead == secondHead && firstHead != null) { 955 if (first == firstHead) { 956 return -1; // first is the head, it should be first 957 } else if (second == firstHead) { 958 return 1; // second is the head, it should be first 959 } else if (mNextFoci.get(first) != null) { 960 return -1; // first is not the end of the chain 961 } else { 962 return 1; // first is end of chain 963 } 964 } 965 boolean involvesChain = false; 966 if (firstHead != null) { 967 first = firstHead; 968 involvesChain = true; 969 } 970 if (secondHead != null) { 971 second = secondHead; 972 involvesChain = true; 973 } 974 975 if (involvesChain) { 976 // keep original order between chains 977 return mOriginalOrdinal.get(first) < mOriginalOrdinal.get(second) ? -1 : 1; 978 } else { 979 return 0; 980 } 981 } 982 } 983 } 984
