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