1 /* 2 * Copyright 2020 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 com.android.car.rotary; 18 19 import android.graphics.Rect; 20 import android.view.View; 21 22 import androidx.annotation.VisibleForTesting; 23 24 /** 25 * The algorithm used for finding the next focusable view in a given direction from a view that 26 * currently has focus. Most of the methods are copied from {@link android.view.FocusFinder}. 27 */ 28 class FocusFinder { 29 30 /** 31 * How much to bias the major axis over the minor axis in {@link #getWeightedDistanceFor}. 32 * Warning: this fudge factor is finely tuned. Be sure to run all focus tests if you dare 33 * tweak it. 34 */ 35 private static final long MAJOR_AXIS_BIAS = 13; 36 37 private static final int[] DIRECTIONS = new int[]{ 38 View.FOCUS_LEFT, View.FOCUS_RIGHT, View.FOCUS_UP, View.FOCUS_DOWN 39 }; 40 41 /** 42 * Returns whether part of {@code destRect} is in {@code direction} of part of {@code srcRect}. 43 * 44 * @param srcRect the source rectangle 45 * @param destRect the destination rectangle 46 * @param direction must be {@link View#FOCUS_UP}, {@link View#FOCUS_DOWN}, 47 * {@link View#FOCUS_LEFT}, or {@link View#FOCUS_RIGHT} 48 */ isPartiallyInDirection(Rect srcRect, Rect destRect, int direction)49 static boolean isPartiallyInDirection(Rect srcRect, Rect destRect, int direction) { 50 switch (direction) { 51 case View.FOCUS_LEFT: 52 return destRect.left < srcRect.right; 53 case View.FOCUS_RIGHT: 54 return destRect.right > srcRect.left; 55 case View.FOCUS_UP: 56 return destRect.top < srcRect.bottom; 57 case View.FOCUS_DOWN: 58 return destRect.bottom > srcRect.top; 59 } 60 throw new IllegalArgumentException("direction must be " 61 + "FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, or FOCUS_RIGHT."); 62 } 63 64 /** 65 * Returns whether part of {@code destRect} is in {@code direction} of {@code srcRect} and 66 * {@code destRect} is not strictly in any of other 3 directions of {@code srcRect}. 67 * 68 * @param srcRect the source rectangle 69 * @param destRect the destination rectangle 70 * @param direction must be {@link View#FOCUS_UP}, {@link View#FOCUS_DOWN}, 71 * {@link View#FOCUS_LEFT}, or {@link View#FOCUS_RIGHT} 72 */ isInDirection(Rect srcRect, Rect destRect, int direction)73 static boolean isInDirection(Rect srcRect, Rect destRect, int direction) { 74 // If destRect is strictly in the given direction of srcRect, destRect is in the given 75 // direction of srcRect. 76 if (isStrictlyInDirection(srcRect, destRect, direction)) { 77 return true; 78 } 79 80 // If destRect is strictly in any of the other directions of srcRect, destRect is not in 81 // the given direction of srcRect. 82 for (int i = 0; i < DIRECTIONS.length; i++) { 83 if (direction != DIRECTIONS[i] 84 && isStrictlyInDirection(srcRect, destRect, DIRECTIONS[i])) { 85 return false; 86 } 87 } 88 89 // Otherwise check whether part of destRect is in the given direction of srcRect. 90 switch (direction) { 91 case View.FOCUS_LEFT: 92 return destRect.left < srcRect.left; 93 case View.FOCUS_RIGHT: 94 return destRect.right > srcRect.right; 95 case View.FOCUS_UP: 96 return destRect.top < srcRect.top; 97 case View.FOCUS_DOWN: 98 return destRect.bottom > srcRect.bottom; 99 } 100 throw new IllegalArgumentException("direction must be " 101 + "FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, or FOCUS_RIGHT."); 102 } 103 104 /** 105 * Returns whether {@code destRect} is a candidate for the next focus given the {@code 106 * direction}. 107 * 108 * For example, iff {@code destRect} is a candidate for {@link View#FOCUS_LEFT}, the following 109 * conditions must be true: 110 * <ul> 111 * <li> {@code destRect.left} is on the left of {@code srcRect.left} 112 * <li> and one of the following conditions must be true: 113 * <ul> 114 * <li> {@code destRect.right} is on the left of {@code srcRect.right} 115 * <li> {@code destRect.right} equals or is on the left of {@code srcRect.left} (an edge case 116 * for an empty {@code srcRect}, which is used in some cases when searching from a point 117 * on the screen) 118 * </ul> 119 * </ul> 120 * 121 * @param srcRect the source rectangle we are searching from 122 * @param destRect the candidate rectangle 123 * @param direction must be {@link View#FOCUS_UP},{@link View#FOCUS_DOWN}, 124 * {@link View#FOCUS_LEFT},or {@link View#FOCUS_RIGHT} 125 */ isCandidate(Rect srcRect, Rect destRect, int direction)126 static boolean isCandidate(Rect srcRect, Rect destRect, int direction) { 127 switch (direction) { 128 case View.FOCUS_LEFT: 129 return (srcRect.right > destRect.right || srcRect.left >= destRect.right) 130 && srcRect.left > destRect.left; 131 case View.FOCUS_RIGHT: 132 return (srcRect.left < destRect.left || srcRect.right <= destRect.left) 133 && srcRect.right < destRect.right; 134 case View.FOCUS_UP: 135 return (srcRect.bottom > destRect.bottom || srcRect.top >= destRect.bottom) 136 && srcRect.top > destRect.top; 137 case View.FOCUS_DOWN: 138 return (srcRect.top < destRect.top || srcRect.bottom <= destRect.top) 139 && srcRect.bottom < destRect.bottom; 140 } 141 throw new IllegalArgumentException("direction must be one of " 142 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 143 } 144 145 /** 146 * Returns whether {@code rect1} is a better candidate than {@code rect2} for a focus search in 147 * a particular {@code direction} from a {@code source} rect. This is the core routine that 148 * determines the order of focus searching. 149 * <p> 150 * Note: this method doesn't check whether {@code rect1} and {@code rect2} are candidates in the 151 * first place, because the strategy to determine a candidate varies: geometry is used for 152 * focusable views, while view hierarchy and geometry are used for focus areas. The caller is 153 * responsible for using a proper strategy to exclude the non-candidates before calling this 154 * method. 155 * 156 * @param direction must be {@link View#FOCUS_UP},{@link View#FOCUS_DOWN}, 157 * {@link View#FOCUS_LEFT},or {@link View#FOCUS_RIGHT} 158 * @param source the source rectangle we are searching from 159 * @param rect1 the candidate rectangle 160 * @param rect2 the current best candidate 161 */ isBetterCandidate(int direction, Rect source, Rect rect1, Rect rect2)162 static boolean isBetterCandidate(int direction, Rect source, Rect rect1, Rect rect2) { 163 // If rect1 is better by beam, it wins. 164 if (beamBeats(direction, source, rect1, rect2)) { 165 return true; 166 } 167 168 // If rect2 is better by beam, then rect1 can't be. 169 if (beamBeats(direction, source, rect2, rect1)) { 170 return false; 171 } 172 173 // Otherwise, do fudge-tastic comparison of the major and minor axis. 174 return getWeightedDistanceFor( 175 majorAxisDistance(direction, source, rect1), 176 minorAxisDistance(direction, source, rect1)) 177 < getWeightedDistanceFor( 178 majorAxisDistance(direction, source, rect2), 179 minorAxisDistance(direction, source, rect2)); 180 } 181 getWeightedDistanceFor(long majorAxisDistance, long minorAxisDistance)182 private static long getWeightedDistanceFor(long majorAxisDistance, long minorAxisDistance) { 183 return MAJOR_AXIS_BIAS * majorAxisDistance * majorAxisDistance 184 + minorAxisDistance * minorAxisDistance; 185 } 186 187 /** 188 * Finds the distance on the minor axis (w.r.t the direction to the nearest edge of the 189 * destination rectangle). 190 */ minorAxisDistance(int direction, Rect source, Rect dest)191 private static int minorAxisDistance(int direction, Rect source, Rect dest) { 192 switch (direction) { 193 case View.FOCUS_LEFT: 194 case View.FOCUS_RIGHT: 195 // The distance between the center verticals. 196 return Math.abs( 197 ((source.top + source.height() / 2) - ((dest.top + dest.height() / 2)))); 198 case View.FOCUS_UP: 199 case View.FOCUS_DOWN: 200 // The distance between the center horizontals. 201 return Math.abs( 202 ((source.left + source.width() / 2) - ((dest.left + dest.width() / 2)))); 203 } 204 throw new IllegalArgumentException("direction must be one of " 205 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 206 } 207 208 /** 209 * Returns whether {@code rect1} is a better candidate than {@code rect2} by virtue of it being 210 * in {@code source}'s beam. 211 */ 212 @VisibleForTesting beamBeats(int direction, Rect source, Rect rect1, Rect rect2)213 static boolean beamBeats(int direction, Rect source, Rect rect1, Rect rect2) { 214 final boolean rect1InSrcBeam = beamsOverlap(direction, source, rect1); 215 final boolean rect2InSrcBeam = beamsOverlap(direction, source, rect2); 216 217 // If rect1 isn't exclusively in the src beam, it doesn't win. 218 if (rect2InSrcBeam || !rect1InSrcBeam) { 219 return false; 220 } 221 222 // We know rect1 is in the beam, and rect2 is not. If rect1 is to the direction of, and 223 // rect2 is not, rect1 wins. For example, for direction left, if rect1 is to the left of 224 // the source and rect2 is below, then we always prefer the in beam rect1, since rect2 225 // could be reached by going down. 226 if (!isToDirectionOf(direction, source, rect2)) { 227 return true; 228 } 229 230 // For horizontal directions, being exclusively in beam always wins. 231 if ((direction == View.FOCUS_LEFT || direction == View.FOCUS_RIGHT)) { 232 return true; 233 } 234 235 // For vertical directions, beams only beat up to a point: as long as rect2 isn't 236 // completely closer, rect1 wins. E.g., for direction down, completely closer means for 237 // rect2's top edge to be closer to the source's top edge than rect1's bottom edge. 238 return majorAxisDistance(direction, source, rect1) 239 < majorAxisDistanceToFarEdge(direction, source, rect2); 240 } 241 242 /** 243 * Returns whether the "beams" (w.r.t the given {@code direction}'s axis of {@code rect1} and 244 * {@code rect2}) overlap. 245 */ 246 @VisibleForTesting beamsOverlap(int direction, Rect rect1, Rect rect2)247 static boolean beamsOverlap(int direction, Rect rect1, Rect rect2) { 248 switch (direction) { 249 case View.FOCUS_LEFT: 250 case View.FOCUS_RIGHT: 251 return (rect2.bottom > rect1.top) && (rect2.top < rect1.bottom); 252 case View.FOCUS_UP: 253 case View.FOCUS_DOWN: 254 return (rect2.right > rect1.left) && (rect2.left < rect1.right); 255 } 256 throw new IllegalArgumentException("direction must be one of " 257 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 258 } 259 260 /** 261 * Returns whether {@code dest} is to the {@code direction} of {@code src}. 262 */ isToDirectionOf(int direction, Rect src, Rect dest)263 private static boolean isToDirectionOf(int direction, Rect src, Rect dest) { 264 switch (direction) { 265 case View.FOCUS_LEFT: 266 return src.left >= dest.right; 267 case View.FOCUS_RIGHT: 268 return src.right <= dest.left; 269 case View.FOCUS_UP: 270 return src.top >= dest.bottom; 271 case View.FOCUS_DOWN: 272 return src.bottom <= dest.top; 273 } 274 throw new IllegalArgumentException("direction must be one of " 275 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 276 } 277 278 /** 279 * Returns the distance from the edge furthest in the given {@code direction} of {@code source} 280 * to the edge nearest in the given {@code direction} of {@code dest}. If the {@code dest} is 281 * not in the {@code direction} from {@code source}, returns 0. 282 */ 283 @VisibleForTesting majorAxisDistance(int direction, Rect source, Rect dest)284 static int majorAxisDistance(int direction, Rect source, Rect dest) { 285 return Math.max(0, majorAxisDistanceRaw(direction, source, dest)); 286 } 287 majorAxisDistanceRaw(int direction, Rect source, Rect dest)288 private static int majorAxisDistanceRaw(int direction, Rect source, Rect dest) { 289 switch (direction) { 290 case View.FOCUS_LEFT: 291 return source.left - dest.right; 292 case View.FOCUS_RIGHT: 293 return dest.left - source.right; 294 case View.FOCUS_UP: 295 return source.top - dest.bottom; 296 case View.FOCUS_DOWN: 297 return dest.top - source.bottom; 298 } 299 throw new IllegalArgumentException("direction must be one of " 300 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 301 } 302 303 /** 304 * Returns the distance along the major axis (w.r.t the {@code direction} from the edge of 305 * {@code source} to the far edge of {@code dest}). If the {@code dest} is not in the {@code 306 * direction} from {@code source}, returns 1 (to break ties with {@link #majorAxisDistance}). 307 */ 308 @VisibleForTesting majorAxisDistanceToFarEdge(int direction, Rect source, Rect dest)309 static int majorAxisDistanceToFarEdge(int direction, Rect source, Rect dest) { 310 return Math.max(1, majorAxisDistanceToFarEdgeRaw(direction, source, dest)); 311 } 312 majorAxisDistanceToFarEdgeRaw(int direction, Rect source, Rect dest)313 private static int majorAxisDistanceToFarEdgeRaw(int direction, Rect source, Rect dest) { 314 switch (direction) { 315 case View.FOCUS_LEFT: 316 return source.left - dest.left; 317 case View.FOCUS_RIGHT: 318 return dest.right - source.right; 319 case View.FOCUS_UP: 320 return source.top - dest.top; 321 case View.FOCUS_DOWN: 322 return dest.bottom - source.bottom; 323 } 324 throw new IllegalArgumentException("direction must be one of " 325 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 326 } 327 328 /** 329 * Returns whether {@code destRect} is strictly in {@code direction} of {@code srcRect}. 330 * <p> 331 * For example, iff {@code destRect} is strictly to the {@link View#FOCUS_LEFT} of {@code 332 * srcRect}, the following conditions must be true: 333 * <ul> 334 * <li> {@code destRect.left} is on the left of {@code srcRect.left} 335 * <li> {@code destRect.right} overlaps with or is on the left of {@code srcRect.right} 336 * <li> [{@code destRect.top}, {@code destRect.bottom}] contains or is contained by 337 * [{@code srcRect.top}, {@code srcRect.bottom}] 338 * </ul> 339 * 340 * @param srcRect the source rectangle 341 * @param destRect the destination rectangle 342 * @param direction must be {@link View#FOCUS_UP}, {@link View#FOCUS_DOWN}, 343 * {@link View#FOCUS_LEFT}, or {@link View#FOCUS_RIGHT} 344 */ isStrictlyInDirection(Rect srcRect, Rect destRect, int direction)345 private static boolean isStrictlyInDirection(Rect srcRect, Rect destRect, int direction) { 346 switch (direction) { 347 case View.FOCUS_LEFT: 348 return destRect.left < srcRect.left && destRect.right <= srcRect.right 349 && containsOrIsContainedVertically(srcRect, destRect); 350 case View.FOCUS_RIGHT: 351 return destRect.right > srcRect.right && destRect.left >= srcRect.left 352 && containsOrIsContainedVertically(srcRect, destRect); 353 case View.FOCUS_UP: 354 return destRect.top < srcRect.top && destRect.bottom <= srcRect.bottom 355 && containsOrIsContainedHorizontally(srcRect, destRect); 356 case View.FOCUS_DOWN: 357 return destRect.bottom > srcRect.bottom && destRect.top >= srcRect.top 358 && containsOrIsContainedHorizontally(srcRect, destRect); 359 } 360 throw new IllegalArgumentException("direction must be " 361 + "FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, or FOCUS_RIGHT."); 362 } 363 364 /** 365 * Returns true if the projection of {@code rect1} on the Y-axis contains or is contained by the 366 * projection of {@code rect2} on the Y-axis. 367 */ containsOrIsContainedVertically(Rect rect1, Rect rect2)368 private static boolean containsOrIsContainedVertically(Rect rect1, Rect rect2) { 369 return (rect1.top <= rect2.top && rect1.bottom >= rect2.bottom) 370 || (rect2.top <= rect1.top && rect2.bottom >= rect1.bottom); 371 } 372 373 /** 374 * Returns true if the projection of {@code rect1} on the X-axis contains or is contained by the 375 * projection of {@code rect2} on the X-axis. 376 */ containsOrIsContainedHorizontally(Rect rect1, Rect rect2)377 private static boolean containsOrIsContainedHorizontally(Rect rect1, Rect rect2) { 378 return (rect1.left <= rect2.left && rect1.right >= rect2.right) 379 || (rect2.left <= rect1.left && rect2.right >= rect1.right); 380 } 381 } 382