1/* 2 * Copyright (C) 2015 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.support.v4.widget; 18 19import android.graphics.Rect; 20import android.support.annotation.NonNull; 21import android.support.annotation.Nullable; 22import android.view.View; 23 24import android.support.v4.view.ViewCompat.FocusRealDirection; 25import android.support.v4.view.ViewCompat.FocusRelativeDirection; 26 27import java.util.ArrayList; 28import java.util.Collections; 29import java.util.Comparator; 30 31/** 32 * Implements absolute and relative focus movement strategies. Adapted from 33 * android.view.FocusFinder to work with generic collections of bounded items. 34 */ 35class FocusStrategy { 36 public static <L,T> T findNextFocusInRelativeDirection(@NonNull L focusables, 37 @NonNull CollectionAdapter<L,T> collectionAdapter, @NonNull BoundsAdapter<T> adapter, 38 @Nullable T focused, @FocusRelativeDirection int direction, boolean isLayoutRtl, 39 boolean wrap) { 40 final int count = collectionAdapter.size(focusables); 41 final ArrayList<T> sortedFocusables = new ArrayList<>(count); 42 for (int i = 0; i < count; i++) { 43 sortedFocusables.add(collectionAdapter.get(focusables, i)); 44 } 45 46 final SequentialComparator<T> comparator = new SequentialComparator<>(isLayoutRtl, adapter); 47 Collections.sort(sortedFocusables, comparator); 48 49 switch (direction) { 50 case View.FOCUS_FORWARD: 51 return getNextFocusable(focused, sortedFocusables, wrap); 52 case View.FOCUS_BACKWARD: 53 return getPreviousFocusable(focused, sortedFocusables, wrap); 54 default: 55 throw new IllegalArgumentException("direction must be one of " 56 + "{FOCUS_FORWARD, FOCUS_BACKWARD}."); 57 } 58 } 59 60 private static <T> T getNextFocusable(T focused, ArrayList<T> focusables, boolean wrap) { 61 final int count = focusables.size(); 62 63 // The position of the next focusable item, which is the first item if 64 // no item is currently focused. 65 final int position = (focused == null ? -1 : focusables.lastIndexOf(focused)) + 1; 66 if (position < count) { 67 return focusables.get(position); 68 } else if (wrap && count > 0) { 69 return focusables.get(0); 70 } else { 71 return null; 72 } 73 } 74 75 private static <T> T getPreviousFocusable(T focused, ArrayList<T> focusables, boolean wrap) { 76 final int count = focusables.size(); 77 78 // The position of the previous focusable item, which is the last item 79 // if no item is currently focused. 80 final int position = (focused == null ? count : focusables.indexOf(focused)) - 1; 81 if (position >= 0) { 82 return focusables.get(position); 83 } else if (wrap && count > 0) { 84 return focusables.get(count - 1); 85 } else { 86 return null; 87 } 88 } 89 90 /** 91 * Sorts views according to their visual layout and geometry for default tab order. 92 * This is used for sequential focus traversal. 93 */ 94 private static class SequentialComparator<T> implements Comparator<T> { 95 private final Rect mTemp1 = new Rect(); 96 private final Rect mTemp2 = new Rect(); 97 98 private final boolean mIsLayoutRtl; 99 private final BoundsAdapter<T> mAdapter; 100 101 public SequentialComparator(boolean isLayoutRtl, BoundsAdapter<T> adapter) { 102 mIsLayoutRtl = isLayoutRtl; 103 mAdapter = adapter; 104 } 105 106 public int compare(T first, T second) { 107 final Rect firstRect = mTemp1; 108 final Rect secondRect = mTemp2; 109 110 mAdapter.obtainBounds(first, firstRect); 111 mAdapter.obtainBounds(second, secondRect); 112 113 if (firstRect.top < secondRect.top) { 114 return -1; 115 } else if (firstRect.top > secondRect.top) { 116 return 1; 117 } else if (firstRect.left < secondRect.left) { 118 return mIsLayoutRtl ? 1 : -1; 119 } else if (firstRect.left > secondRect.left) { 120 return mIsLayoutRtl ? -1 : 1; 121 } else if (firstRect.bottom < secondRect.bottom) { 122 return -1; 123 } else if (firstRect.bottom > secondRect.bottom) { 124 return 1; 125 } else if (firstRect.right < secondRect.right) { 126 return mIsLayoutRtl ? 1 : -1; 127 } else if (firstRect.right > secondRect.right) { 128 return mIsLayoutRtl ? -1 : 1; 129 } else { 130 // The view are distinct but completely coincident so we 131 // consider them equal for our purposes. Since the sort is 132 // stable, this means that the views will retain their 133 // layout order relative to one another. 134 return 0; 135 } 136 } 137 } 138 139 public static <L,T> T findNextFocusInAbsoluteDirection(@NonNull L focusables, 140 @NonNull CollectionAdapter<L,T> collectionAdapter, @NonNull BoundsAdapter<T> adapter, 141 @Nullable T focused, @NonNull Rect focusedRect, int direction) { 142 // Initialize the best candidate to something impossible so that 143 // the first plausible view will become the best choice. 144 final Rect bestCandidateRect = new Rect(focusedRect); 145 146 switch (direction) { 147 case View.FOCUS_LEFT: 148 bestCandidateRect.offset(focusedRect.width() + 1, 0); 149 break; 150 case View.FOCUS_RIGHT: 151 bestCandidateRect.offset(-(focusedRect.width() + 1), 0); 152 break; 153 case View.FOCUS_UP: 154 bestCandidateRect.offset(0, focusedRect.height() + 1); 155 break; 156 case View.FOCUS_DOWN: 157 bestCandidateRect.offset(0, -(focusedRect.height() + 1)); 158 break; 159 default: 160 throw new IllegalArgumentException("direction must be one of " 161 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 162 } 163 164 T closest = null; 165 166 final int count = collectionAdapter.size(focusables); 167 final Rect focusableRect = new Rect(); 168 for (int i = 0; i < count; i++) { 169 final T focusable = collectionAdapter.get(focusables, i); 170 if (focusable == focused) { 171 continue; 172 } 173 174 // get focus bounds of other view 175 adapter.obtainBounds(focusable, focusableRect); 176 if (isBetterCandidate(direction, focusedRect, focusableRect, bestCandidateRect)) { 177 bestCandidateRect.set(focusableRect); 178 closest = focusable; 179 } 180 } 181 182 return closest; 183 } 184 185 /** 186 * Is candidate a better candidate than currentBest for a focus search 187 * in a particular direction from a source rect? This is the core 188 * routine that determines the order of focus searching. 189 * 190 * @param direction the direction (up, down, left, right) 191 * @param source the source from which we are searching 192 * @param candidate the candidate rectangle 193 * @param currentBest the current best rectangle 194 * @return {@code true} if the candidate rectangle is a better than the 195 * current best rectangle, {@code false} otherwise 196 */ 197 private static boolean isBetterCandidate( 198 @FocusRealDirection int direction, @NonNull Rect source, 199 @NonNull Rect candidate, @NonNull Rect currentBest) { 200 // To be a better candidate, need to at least be a candidate in the 201 // first place. :) 202 if (!isCandidate(source, candidate, direction)) { 203 return false; 204 } 205 206 // We know that candidateRect is a candidate. If currentBest is not 207 // a candidate, candidateRect is better. 208 if (!isCandidate(source, currentBest, direction)) { 209 return true; 210 } 211 212 // If candidateRect is better by beam, it wins. 213 if (beamBeats(direction, source, candidate, currentBest)) { 214 return true; 215 } 216 217 // If currentBest is better, then candidateRect cant' be. :) 218 if (beamBeats(direction, source, currentBest, candidate)) { 219 return false; 220 } 221 222 // Otherwise, do fudge-tastic comparison of the major and minor 223 // axis. 224 final int candidateDist = getWeightedDistanceFor( 225 majorAxisDistance(direction, source, candidate), 226 minorAxisDistance(direction, source, candidate)); 227 final int currentBestDist = getWeightedDistanceFor( 228 majorAxisDistance(direction, source, currentBest), 229 minorAxisDistance(direction, source, currentBest)); 230 return candidateDist < currentBestDist; 231 } 232 233 /** 234 * One rectangle may be another candidate than another by virtue of 235 * being exclusively in the beam of the source rect. 236 * 237 * @return whether rect1 is a better candidate than rect2 by virtue of 238 * it being in source's beam 239 */ 240 private static boolean beamBeats(@FocusRealDirection int direction, 241 @NonNull Rect source, @NonNull Rect rect1, @NonNull Rect rect2) { 242 final boolean rect1InSrcBeam = beamsOverlap(direction, source, rect1); 243 final boolean rect2InSrcBeam = beamsOverlap(direction, source, rect2); 244 245 // If rect1 isn't exclusively in the src beam, it doesn't win. 246 if (rect2InSrcBeam || !rect1InSrcBeam) { 247 return false; 248 } 249 250 // We know rect1 is in the beam, and rect2 is not. 251 252 // If rect1 is to the direction of, and rect2 is not, rect1 wins. 253 // For example, for direction left, if rect1 is to the left of the 254 // source and rect2 is below, then we always prefer the in beam 255 // rect1, since rect2 could be reached by going down. 256 if (!isToDirectionOf(direction, source, rect2)) { 257 return true; 258 } 259 260 // For horizontal directions, being exclusively in beam always 261 // wins. 262 if (direction == View.FOCUS_LEFT || direction == View.FOCUS_RIGHT) { 263 return true; 264 } 265 266 // For vertical directions, beams only beat up to a point: now, as 267 // long as rect2 isn't completely closer, rect1 wins, e.g. for 268 // direction down, completely closer means for rect2's top edge to 269 // be closer to the source's top edge than rect1's bottom edge. 270 return majorAxisDistance(direction, source, rect1) 271 < majorAxisDistanceToFarEdge(direction, source, rect2); 272 } 273 274 /** 275 * Fudge-factor opportunity: how to calculate distance given major and 276 * minor axis distances. 277 * <p/> 278 * Warning: this fudge factor is finely tuned, be sure to run all focus 279 * tests if you dare tweak it. 280 */ 281 private static int getWeightedDistanceFor(int majorAxisDistance, int minorAxisDistance) { 282 return 13 * majorAxisDistance * majorAxisDistance 283 + minorAxisDistance * minorAxisDistance; 284 } 285 286 /** 287 * Is destRect a candidate for the next focus given the direction? This 288 * checks whether the dest is at least partially to the direction of 289 * (e.g. left of) from source. 290 * <p/> 291 * Includes an edge case for an empty rect,which is used in some cases 292 * when searching from a point on the screen. 293 */ 294 private static boolean isCandidate(@NonNull Rect srcRect, @NonNull Rect destRect, 295 @FocusRealDirection int direction) { 296 switch (direction) { 297 case View.FOCUS_LEFT: 298 return (srcRect.right > destRect.right || srcRect.left >= destRect.right) 299 && srcRect.left > destRect.left; 300 case View.FOCUS_RIGHT: 301 return (srcRect.left < destRect.left || srcRect.right <= destRect.left) 302 && srcRect.right < destRect.right; 303 case View.FOCUS_UP: 304 return (srcRect.bottom > destRect.bottom || srcRect.top >= destRect.bottom) 305 && srcRect.top > destRect.top; 306 case View.FOCUS_DOWN: 307 return (srcRect.top < destRect.top || srcRect.bottom <= destRect.top) 308 && srcRect.bottom < destRect.bottom; 309 } 310 throw new IllegalArgumentException("direction must be one of " 311 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 312 } 313 314 315 /** 316 * Do the "beams" w.r.t the given direction's axis of rect1 and rect2 overlap? 317 * 318 * @param direction the direction (up, down, left, right) 319 * @param rect1 the first rectangle 320 * @param rect2 the second rectangle 321 * @return whether the beams overlap 322 */ 323 private static boolean beamsOverlap(@FocusRealDirection int direction, 324 @NonNull Rect rect1, @NonNull Rect rect2) { 325 switch (direction) { 326 case View.FOCUS_LEFT: 327 case View.FOCUS_RIGHT: 328 return (rect2.bottom >= rect1.top) && (rect2.top <= rect1.bottom); 329 case View.FOCUS_UP: 330 case View.FOCUS_DOWN: 331 return (rect2.right >= rect1.left) && (rect2.left <= rect1.right); 332 } 333 throw new IllegalArgumentException("direction must be one of " 334 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 335 } 336 337 /** 338 * e.g for left, is 'to left of' 339 */ 340 private static boolean isToDirectionOf(@FocusRealDirection int direction, 341 @NonNull Rect src, @NonNull Rect dest) { 342 switch (direction) { 343 case View.FOCUS_LEFT: 344 return src.left >= dest.right; 345 case View.FOCUS_RIGHT: 346 return src.right <= dest.left; 347 case View.FOCUS_UP: 348 return src.top >= dest.bottom; 349 case View.FOCUS_DOWN: 350 return src.bottom <= dest.top; 351 } 352 throw new IllegalArgumentException("direction must be one of " 353 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 354 } 355 356 /** 357 * @return the distance from the edge furthest in the given direction 358 * of source to the edge nearest in the given direction of 359 * dest. If the dest is not in the direction from source, 360 * returns 0. 361 */ 362 private static int majorAxisDistance(@FocusRealDirection int direction, 363 @NonNull Rect source, @NonNull Rect dest) { 364 return Math.max(0, majorAxisDistanceRaw(direction, source, dest)); 365 } 366 367 private static int majorAxisDistanceRaw(@FocusRealDirection int direction, 368 @NonNull Rect source, @NonNull Rect dest) { 369 switch (direction) { 370 case View.FOCUS_LEFT: 371 return source.left - dest.right; 372 case View.FOCUS_RIGHT: 373 return dest.left - source.right; 374 case View.FOCUS_UP: 375 return source.top - dest.bottom; 376 case View.FOCUS_DOWN: 377 return dest.top - source.bottom; 378 } 379 throw new IllegalArgumentException("direction must be one of " 380 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 381 } 382 383 /** 384 * @return the distance along the major axis w.r.t the direction from 385 * the edge of source to the far edge of dest. If the dest is 386 * not in the direction from source, returns 1 to break ties 387 * with {@link #majorAxisDistance}. 388 */ 389 private static int majorAxisDistanceToFarEdge(@FocusRealDirection int direction, 390 @NonNull Rect source, @NonNull Rect dest) { 391 return Math.max(1, majorAxisDistanceToFarEdgeRaw(direction, source, dest)); 392 } 393 394 private static int majorAxisDistanceToFarEdgeRaw( 395 @FocusRealDirection int direction, @NonNull Rect source, 396 @NonNull Rect dest) { 397 switch (direction) { 398 case View.FOCUS_LEFT: 399 return source.left - dest.left; 400 case View.FOCUS_RIGHT: 401 return dest.right - source.right; 402 case View.FOCUS_UP: 403 return source.top - dest.top; 404 case View.FOCUS_DOWN: 405 return dest.bottom - source.bottom; 406 } 407 throw new IllegalArgumentException("direction must be one of " 408 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 409 } 410 411 /** 412 * Finds the distance on the minor axis w.r.t the direction to the 413 * nearest edge of the destination rectangle. 414 * 415 * @param direction the direction (up, down, left, right) 416 * @param source the source rect 417 * @param dest the destination rect 418 * @return the distance 419 */ 420 private static int minorAxisDistance(@FocusRealDirection int direction, @NonNull Rect source, 421 @NonNull Rect dest) { 422 switch (direction) { 423 case View.FOCUS_LEFT: 424 case View.FOCUS_RIGHT: 425 // the distance between the center verticals 426 return Math.abs( 427 ((source.top + source.height() / 2) - 428 ((dest.top + dest.height() / 2)))); 429 case View.FOCUS_UP: 430 case View.FOCUS_DOWN: 431 // the distance between the center horizontals 432 return Math.abs( 433 ((source.left + source.width() / 2) - 434 ((dest.left + dest.width() / 2)))); 435 } 436 throw new IllegalArgumentException("direction must be one of " 437 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 438 } 439 440 /** 441 * Adapter used to obtain bounds from a generic data type. 442 */ 443 public interface BoundsAdapter<T> { 444 void obtainBounds(T data, Rect outBounds); 445 } 446 447 /** 448 * Adapter used to obtain items from a generic collection type. 449 */ 450 public interface CollectionAdapter<T, V> { 451 V get(T collection, int index); 452 int size(T collection); 453 } 454} 455