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 SequentialComparator(boolean isLayoutRtl, BoundsAdapter<T> adapter) { 102 mIsLayoutRtl = isLayoutRtl; 103 mAdapter = adapter; 104 } 105 106 @Override 107 public int compare(T first, T second) { 108 final Rect firstRect = mTemp1; 109 final Rect secondRect = mTemp2; 110 111 mAdapter.obtainBounds(first, firstRect); 112 mAdapter.obtainBounds(second, secondRect); 113 114 if (firstRect.top < secondRect.top) { 115 return -1; 116 } else if (firstRect.top > secondRect.top) { 117 return 1; 118 } else if (firstRect.left < secondRect.left) { 119 return mIsLayoutRtl ? 1 : -1; 120 } else if (firstRect.left > secondRect.left) { 121 return mIsLayoutRtl ? -1 : 1; 122 } else if (firstRect.bottom < secondRect.bottom) { 123 return -1; 124 } else if (firstRect.bottom > secondRect.bottom) { 125 return 1; 126 } else if (firstRect.right < secondRect.right) { 127 return mIsLayoutRtl ? 1 : -1; 128 } else if (firstRect.right > secondRect.right) { 129 return mIsLayoutRtl ? -1 : 1; 130 } else { 131 // The view are distinct but completely coincident so we 132 // consider them equal for our purposes. Since the sort is 133 // stable, this means that the views will retain their 134 // layout order relative to one another. 135 return 0; 136 } 137 } 138 } 139 140 public static <L, T> T findNextFocusInAbsoluteDirection(@NonNull L focusables, 141 @NonNull CollectionAdapter<L, T> collectionAdapter, @NonNull BoundsAdapter<T> adapter, 142 @Nullable T focused, @NonNull Rect focusedRect, int direction) { 143 // Initialize the best candidate to something impossible so that 144 // the first plausible view will become the best choice. 145 final Rect bestCandidateRect = new Rect(focusedRect); 146 147 switch (direction) { 148 case View.FOCUS_LEFT: 149 bestCandidateRect.offset(focusedRect.width() + 1, 0); 150 break; 151 case View.FOCUS_RIGHT: 152 bestCandidateRect.offset(-(focusedRect.width() + 1), 0); 153 break; 154 case View.FOCUS_UP: 155 bestCandidateRect.offset(0, focusedRect.height() + 1); 156 break; 157 case View.FOCUS_DOWN: 158 bestCandidateRect.offset(0, -(focusedRect.height() + 1)); 159 break; 160 default: 161 throw new IllegalArgumentException("direction must be one of " 162 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 163 } 164 165 T closest = null; 166 167 final int count = collectionAdapter.size(focusables); 168 final Rect focusableRect = new Rect(); 169 for (int i = 0; i < count; i++) { 170 final T focusable = collectionAdapter.get(focusables, i); 171 if (focusable == focused) { 172 continue; 173 } 174 175 // get focus bounds of other view 176 adapter.obtainBounds(focusable, focusableRect); 177 if (isBetterCandidate(direction, focusedRect, focusableRect, bestCandidateRect)) { 178 bestCandidateRect.set(focusableRect); 179 closest = focusable; 180 } 181 } 182 183 return closest; 184 } 185 186 /** 187 * Is candidate a better candidate than currentBest for a focus search 188 * in a particular direction from a source rect? This is the core 189 * routine that determines the order of focus searching. 190 * 191 * @param direction the direction (up, down, left, right) 192 * @param source the source from which we are searching 193 * @param candidate the candidate rectangle 194 * @param currentBest the current best rectangle 195 * @return {@code true} if the candidate rectangle is a better than the 196 * current best rectangle, {@code false} otherwise 197 */ 198 private static boolean isBetterCandidate( 199 @FocusRealDirection int direction, @NonNull Rect source, 200 @NonNull Rect candidate, @NonNull Rect currentBest) { 201 // To be a better candidate, need to at least be a candidate in the 202 // first place. :) 203 if (!isCandidate(source, candidate, direction)) { 204 return false; 205 } 206 207 // We know that candidateRect is a candidate. If currentBest is not 208 // a candidate, candidateRect is better. 209 if (!isCandidate(source, currentBest, direction)) { 210 return true; 211 } 212 213 // If candidateRect is better by beam, it wins. 214 if (beamBeats(direction, source, candidate, currentBest)) { 215 return true; 216 } 217 218 // If currentBest is better, then candidateRect cant' be. :) 219 if (beamBeats(direction, source, currentBest, candidate)) { 220 return false; 221 } 222 223 // Otherwise, do fudge-tastic comparison of the major and minor 224 // axis. 225 final int candidateDist = getWeightedDistanceFor( 226 majorAxisDistance(direction, source, candidate), 227 minorAxisDistance(direction, source, candidate)); 228 final int currentBestDist = getWeightedDistanceFor( 229 majorAxisDistance(direction, source, currentBest), 230 minorAxisDistance(direction, source, currentBest)); 231 return candidateDist < currentBestDist; 232 } 233 234 /** 235 * One rectangle may be another candidate than another by virtue of 236 * being exclusively in the beam of the source rect. 237 * 238 * @return whether rect1 is a better candidate than rect2 by virtue of 239 * it being in source's beam 240 */ 241 private static boolean beamBeats(@FocusRealDirection int direction, 242 @NonNull Rect source, @NonNull Rect rect1, @NonNull Rect rect2) { 243 final boolean rect1InSrcBeam = beamsOverlap(direction, source, rect1); 244 final boolean rect2InSrcBeam = beamsOverlap(direction, source, rect2); 245 246 // If rect1 isn't exclusively in the src beam, it doesn't win. 247 if (rect2InSrcBeam || !rect1InSrcBeam) { 248 return false; 249 } 250 251 // We know rect1 is in the beam, and rect2 is not. 252 253 // If rect1 is to the direction of, and rect2 is not, rect1 wins. 254 // For example, for direction left, if rect1 is to the left of the 255 // source and rect2 is below, then we always prefer the in beam 256 // rect1, since rect2 could be reached by going down. 257 if (!isToDirectionOf(direction, source, rect2)) { 258 return true; 259 } 260 261 // For horizontal directions, being exclusively in beam always 262 // wins. 263 if (direction == View.FOCUS_LEFT || direction == View.FOCUS_RIGHT) { 264 return true; 265 } 266 267 // For vertical directions, beams only beat up to a point: now, as 268 // long as rect2 isn't completely closer, rect1 wins, e.g. for 269 // direction down, completely closer means for rect2's top edge to 270 // be closer to the source's top edge than rect1's bottom edge. 271 return majorAxisDistance(direction, source, rect1) 272 < majorAxisDistanceToFarEdge(direction, source, rect2); 273 } 274 275 /** 276 * Fudge-factor opportunity: how to calculate distance given major and 277 * minor axis distances. 278 * <p/> 279 * Warning: this fudge factor is finely tuned, be sure to run all focus 280 * tests if you dare tweak it. 281 */ 282 private static int getWeightedDistanceFor(int majorAxisDistance, int minorAxisDistance) { 283 return 13 * majorAxisDistance * majorAxisDistance 284 + minorAxisDistance * minorAxisDistance; 285 } 286 287 /** 288 * Is destRect a candidate for the next focus given the direction? This 289 * checks whether the dest is at least partially to the direction of 290 * (e.g. left of) from source. 291 * <p/> 292 * Includes an edge case for an empty rect,which is used in some cases 293 * when searching from a point on the screen. 294 */ 295 private static boolean isCandidate(@NonNull Rect srcRect, @NonNull Rect destRect, 296 @FocusRealDirection int direction) { 297 switch (direction) { 298 case View.FOCUS_LEFT: 299 return (srcRect.right > destRect.right || srcRect.left >= destRect.right) 300 && srcRect.left > destRect.left; 301 case View.FOCUS_RIGHT: 302 return (srcRect.left < destRect.left || srcRect.right <= destRect.left) 303 && srcRect.right < destRect.right; 304 case View.FOCUS_UP: 305 return (srcRect.bottom > destRect.bottom || srcRect.top >= destRect.bottom) 306 && srcRect.top > destRect.top; 307 case View.FOCUS_DOWN: 308 return (srcRect.top < destRect.top || srcRect.bottom <= destRect.top) 309 && srcRect.bottom < destRect.bottom; 310 } 311 throw new IllegalArgumentException("direction must be one of " 312 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 313 } 314 315 316 /** 317 * Do the "beams" w.r.t the given direction's axis of rect1 and rect2 overlap? 318 * 319 * @param direction the direction (up, down, left, right) 320 * @param rect1 the first rectangle 321 * @param rect2 the second rectangle 322 * @return whether the beams overlap 323 */ 324 private static boolean beamsOverlap(@FocusRealDirection int direction, 325 @NonNull Rect rect1, @NonNull Rect rect2) { 326 switch (direction) { 327 case View.FOCUS_LEFT: 328 case View.FOCUS_RIGHT: 329 return (rect2.bottom >= rect1.top) && (rect2.top <= rect1.bottom); 330 case View.FOCUS_UP: 331 case View.FOCUS_DOWN: 332 return (rect2.right >= rect1.left) && (rect2.left <= rect1.right); 333 } 334 throw new IllegalArgumentException("direction must be one of " 335 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 336 } 337 338 /** 339 * e.g for left, is 'to left of' 340 */ 341 private static boolean isToDirectionOf(@FocusRealDirection int direction, 342 @NonNull Rect src, @NonNull Rect dest) { 343 switch (direction) { 344 case View.FOCUS_LEFT: 345 return src.left >= dest.right; 346 case View.FOCUS_RIGHT: 347 return src.right <= dest.left; 348 case View.FOCUS_UP: 349 return src.top >= dest.bottom; 350 case View.FOCUS_DOWN: 351 return src.bottom <= dest.top; 352 } 353 throw new IllegalArgumentException("direction must be one of " 354 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 355 } 356 357 /** 358 * @return the distance from the edge furthest in the given direction 359 * of source to the edge nearest in the given direction of 360 * dest. If the dest is not in the direction from source, 361 * returns 0. 362 */ 363 private static int majorAxisDistance(@FocusRealDirection int direction, 364 @NonNull Rect source, @NonNull Rect dest) { 365 return Math.max(0, majorAxisDistanceRaw(direction, source, dest)); 366 } 367 368 private static int majorAxisDistanceRaw(@FocusRealDirection int direction, 369 @NonNull Rect source, @NonNull Rect dest) { 370 switch (direction) { 371 case View.FOCUS_LEFT: 372 return source.left - dest.right; 373 case View.FOCUS_RIGHT: 374 return dest.left - source.right; 375 case View.FOCUS_UP: 376 return source.top - dest.bottom; 377 case View.FOCUS_DOWN: 378 return dest.top - source.bottom; 379 } 380 throw new IllegalArgumentException("direction must be one of " 381 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 382 } 383 384 /** 385 * @return the distance along the major axis w.r.t the direction from 386 * the edge of source to the far edge of dest. If the dest is 387 * not in the direction from source, returns 1 to break ties 388 * with {@link #majorAxisDistance}. 389 */ 390 private static int majorAxisDistanceToFarEdge(@FocusRealDirection int direction, 391 @NonNull Rect source, @NonNull Rect dest) { 392 return Math.max(1, majorAxisDistanceToFarEdgeRaw(direction, source, dest)); 393 } 394 395 private static int majorAxisDistanceToFarEdgeRaw( 396 @FocusRealDirection int direction, @NonNull Rect source, 397 @NonNull Rect dest) { 398 switch (direction) { 399 case View.FOCUS_LEFT: 400 return source.left - dest.left; 401 case View.FOCUS_RIGHT: 402 return dest.right - source.right; 403 case View.FOCUS_UP: 404 return source.top - dest.top; 405 case View.FOCUS_DOWN: 406 return dest.bottom - source.bottom; 407 } 408 throw new IllegalArgumentException("direction must be one of " 409 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 410 } 411 412 /** 413 * Finds the distance on the minor axis w.r.t the direction to the 414 * nearest edge of the destination rectangle. 415 * 416 * @param direction the direction (up, down, left, right) 417 * @param source the source rect 418 * @param dest the destination rect 419 * @return the distance 420 */ 421 private static int minorAxisDistance(@FocusRealDirection int direction, @NonNull Rect source, 422 @NonNull Rect dest) { 423 switch (direction) { 424 case View.FOCUS_LEFT: 425 case View.FOCUS_RIGHT: 426 // the distance between the center verticals 427 return Math.abs( 428 ((source.top + source.height() / 2) - ((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