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 /** 38 * Returns whether part of {@code destRect} is in {@code direction} of part of {@code srcRect}. 39 * 40 * @param srcRect the source rectangle 41 * @param destRect the destination rectangle 42 * @param direction must be {@link View#FOCUS_UP}, {@link View#FOCUS_DOWN}, 43 * {@link View#FOCUS_LEFT}, or {@link View#FOCUS_RIGHT} 44 */ isPartiallyInDirection(Rect srcRect, Rect destRect, int direction)45 static boolean isPartiallyInDirection(Rect srcRect, Rect destRect, int direction) { 46 switch (direction) { 47 case View.FOCUS_LEFT: 48 return destRect.left < srcRect.right; 49 case View.FOCUS_RIGHT: 50 return destRect.right > srcRect.left; 51 case View.FOCUS_UP: 52 return destRect.top < srcRect.bottom; 53 case View.FOCUS_DOWN: 54 return destRect.bottom > srcRect.top; 55 } 56 throw new IllegalArgumentException("direction must be " 57 + "FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, or FOCUS_RIGHT."); 58 } 59 60 /** 61 * Returns whether {@code destRect} is a candidate for the next focus given the {@code 62 * direction}. 63 * 64 * For example, iff {@code destRect} is a candidate for {@link View#FOCUS_LEFT}, the following 65 * conditions must be true: 66 * <ul> 67 * <li> {@code destRect.left} is on the left of {@code srcRect.left} 68 * <li> and one of the following conditions must be true: 69 * <ul> 70 * <li> {@code destRect.right} is on the left of {@code srcRect.right} 71 * <li> {@code destRect.right} equals {@code srcRect.right}, and {@code destRect} and {@code 72 * srcRect} overlap in Y axis (an edge case) 73 * <li> {@code destRect.right} equals or is on the left of {@code srcRect.left} (an edge case 74 * for an empty {@code srcRect}, which is used in some cases when searching from a point 75 * on the screen) 76 * </ul> 77 * </ul> 78 * 79 * @param srcRect the source rectangle we are searching from 80 * @param destRect the candidate rectangle 81 * @param direction must be {@link View#FOCUS_UP},{@link View#FOCUS_DOWN}, 82 * {@link View#FOCUS_LEFT},or {@link View#FOCUS_RIGHT} 83 */ isCandidate(Rect srcRect, Rect destRect, int direction)84 static boolean isCandidate(Rect srcRect, Rect destRect, int direction) { 85 switch (direction) { 86 case View.FOCUS_LEFT: 87 return srcRect.left > destRect.left 88 && (srcRect.right > destRect.right 89 || (srcRect.right == destRect.right && overlapOnYAxis(srcRect, 90 destRect)) 91 || srcRect.left >= destRect.right); 92 case View.FOCUS_RIGHT: 93 return srcRect.right < destRect.right 94 && (srcRect.left < destRect.left 95 || (srcRect.left == destRect.left && overlapOnYAxis(srcRect, destRect)) 96 || srcRect.right <= destRect.left); 97 case View.FOCUS_UP: 98 return srcRect.top > destRect.top 99 && (srcRect.bottom > destRect.bottom 100 || (srcRect.bottom == destRect.bottom && overlapOnXAxis(srcRect, 101 destRect)) 102 || srcRect.top >= destRect.bottom); 103 case View.FOCUS_DOWN: 104 return srcRect.bottom < destRect.bottom 105 && (srcRect.top < destRect.top 106 || (srcRect.top == destRect.top && overlapOnXAxis(srcRect, destRect)) 107 || srcRect.bottom <= destRect.top); 108 } 109 throw new IllegalArgumentException("direction must be one of " 110 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 111 } 112 113 /** 114 * Returns whether {@code rect1} is a better candidate than {@code rect2} for a focus search in 115 * a particular {@code direction} from a {@code source} rect. This is the core routine that 116 * determines the order of focus searching. 117 * 118 * @param direction must be {@link View#FOCUS_UP},{@link View#FOCUS_DOWN}, 119 * {@link View#FOCUS_LEFT},or {@link View#FOCUS_RIGHT} 120 * @param source the source rectangle we are searching from 121 * @param rect1 the candidate rectangle 122 * @param rect2 the current best candidate 123 */ isBetterCandidate(int direction, Rect source, Rect rect1, Rect rect2)124 static boolean isBetterCandidate(int direction, Rect source, Rect rect1, Rect rect2) { 125 // To be a better candidate, need to at least be a candidate in the first place. 126 if (!isCandidate(source, rect1, direction)) { 127 return false; 128 } 129 130 // We know that rect1 is a candidate. If rect2 is not a candidate, rect1 is better. 131 if (!isCandidate(source, rect2, direction)) { 132 return true; 133 } 134 135 // If rect1 is better by beam, it wins. 136 if (beamBeats(direction, source, rect1, rect2)) { 137 return true; 138 } 139 140 // If rect2 is better by beam, then rect1 can't be. 141 if (beamBeats(direction, source, rect2, rect1)) { 142 return false; 143 } 144 145 // Otherwise, do fudge-tastic comparison of the major and minor axis. 146 return getWeightedDistanceFor( 147 majorAxisDistance(direction, source, rect1), 148 minorAxisDistance(direction, source, rect1)) 149 < getWeightedDistanceFor( 150 majorAxisDistance(direction, source, rect2), 151 minorAxisDistance(direction, source, rect2)); 152 } 153 getWeightedDistanceFor(long majorAxisDistance, long minorAxisDistance)154 private static long getWeightedDistanceFor(long majorAxisDistance, long minorAxisDistance) { 155 return MAJOR_AXIS_BIAS * majorAxisDistance * majorAxisDistance 156 + minorAxisDistance * minorAxisDistance; 157 } 158 159 /** 160 * Finds the distance on the minor axis (w.r.t the direction to the nearest edge of the 161 * destination rectangle). 162 */ minorAxisDistance(int direction, Rect source, Rect dest)163 private static int minorAxisDistance(int direction, Rect source, Rect dest) { 164 switch (direction) { 165 case View.FOCUS_LEFT: 166 case View.FOCUS_RIGHT: 167 // The distance between the center verticals. 168 return Math.abs( 169 ((source.top + source.height() / 2) - ((dest.top + dest.height() / 2)))); 170 case View.FOCUS_UP: 171 case View.FOCUS_DOWN: 172 // The distance between the center horizontals. 173 return Math.abs( 174 ((source.left + source.width() / 2) - ((dest.left + dest.width() / 2)))); 175 } 176 throw new IllegalArgumentException("direction must be one of " 177 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 178 } 179 180 /** 181 * Returns whether {@code rect1} is a better candidate than {@code rect2} by virtue of it being 182 * in {@code source}'s beam. 183 */ 184 @VisibleForTesting beamBeats(int direction, Rect source, Rect rect1, Rect rect2)185 static boolean beamBeats(int direction, Rect source, Rect rect1, Rect rect2) { 186 final boolean rect1InSrcBeam = beamsOverlap(direction, source, rect1); 187 final boolean rect2InSrcBeam = beamsOverlap(direction, source, rect2); 188 189 // If rect1 isn't exclusively in the src beam, it doesn't win. 190 if (rect2InSrcBeam || !rect1InSrcBeam) { 191 return false; 192 } 193 194 // We know rect1 is in the beam, and rect2 is not. If rect1 is to the direction of, and 195 // rect2 is not, rect1 wins. For example, for direction left, if rect1 is to the left of 196 // the source and rect2 is below, then we always prefer the in beam rect1, since rect2 197 // could be reached by going down. 198 if (!isToDirectionOf(direction, source, rect2)) { 199 return true; 200 } 201 202 // For horizontal directions, being exclusively in beam always wins. 203 if ((direction == View.FOCUS_LEFT || direction == View.FOCUS_RIGHT)) { 204 return true; 205 } 206 207 // For vertical directions, beams only beat up to a point: as long as rect2 isn't 208 // completely closer, rect1 wins. E.g., for direction down, completely closer means for 209 // rect2's top edge to be closer to the source's top edge than rect1's bottom edge. 210 return majorAxisDistance(direction, source, rect1) 211 < majorAxisDistanceToFarEdge(direction, source, rect2); 212 } 213 214 /** 215 * Returns whether the "beams" (w.r.t the given {@code direction}'s axis of {@code rect1} and 216 * {@code rect2}) overlap. 217 */ 218 @VisibleForTesting beamsOverlap(int direction, Rect rect1, Rect rect2)219 static boolean beamsOverlap(int direction, Rect rect1, Rect rect2) { 220 switch (direction) { 221 case View.FOCUS_LEFT: 222 case View.FOCUS_RIGHT: 223 return (rect2.bottom > rect1.top) && (rect2.top < rect1.bottom); 224 case View.FOCUS_UP: 225 case View.FOCUS_DOWN: 226 return (rect2.right > rect1.left) && (rect2.left < rect1.right); 227 } 228 throw new IllegalArgumentException("direction must be one of " 229 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 230 } 231 232 /** 233 * Returns whether {@code dest} is to the {@code direction} of {@code src}. 234 */ isToDirectionOf(int direction, Rect src, Rect dest)235 private static boolean isToDirectionOf(int direction, Rect src, Rect dest) { 236 switch (direction) { 237 case View.FOCUS_LEFT: 238 return src.left >= dest.right; 239 case View.FOCUS_RIGHT: 240 return src.right <= dest.left; 241 case View.FOCUS_UP: 242 return src.top >= dest.bottom; 243 case View.FOCUS_DOWN: 244 return src.bottom <= dest.top; 245 } 246 throw new IllegalArgumentException("direction must be one of " 247 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 248 } 249 250 /** 251 * Returns the distance from the edge furthest in the given {@code direction} of {@code source} 252 * to the edge nearest in the given {@code direction} of {@code dest}. If the {@code dest} is 253 * not in the {@code direction} from {@code source}, returns 0. 254 */ 255 @VisibleForTesting majorAxisDistance(int direction, Rect source, Rect dest)256 static int majorAxisDistance(int direction, Rect source, Rect dest) { 257 return Math.max(0, majorAxisDistanceRaw(direction, source, dest)); 258 } 259 majorAxisDistanceRaw(int direction, Rect source, Rect dest)260 private static int majorAxisDistanceRaw(int direction, Rect source, Rect dest) { 261 switch (direction) { 262 case View.FOCUS_LEFT: 263 return source.left - dest.right; 264 case View.FOCUS_RIGHT: 265 return dest.left - source.right; 266 case View.FOCUS_UP: 267 return source.top - dest.bottom; 268 case View.FOCUS_DOWN: 269 return dest.top - source.bottom; 270 } 271 throw new IllegalArgumentException("direction must be one of " 272 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 273 } 274 275 /** 276 * Returns the distance along the major axis (w.r.t the {@code direction} from the edge of 277 * {@code source} to the far edge of {@code dest}). If the {@code dest} is not in the {@code 278 * direction} from {@code source}, returns 1 (to break ties with {@link #majorAxisDistance}). 279 */ 280 @VisibleForTesting majorAxisDistanceToFarEdge(int direction, Rect source, Rect dest)281 static int majorAxisDistanceToFarEdge(int direction, Rect source, Rect dest) { 282 return Math.max(1, majorAxisDistanceToFarEdgeRaw(direction, source, dest)); 283 } 284 majorAxisDistanceToFarEdgeRaw(int direction, Rect source, Rect dest)285 private static int majorAxisDistanceToFarEdgeRaw(int direction, Rect source, Rect dest) { 286 switch (direction) { 287 case View.FOCUS_LEFT: 288 return source.left - dest.left; 289 case View.FOCUS_RIGHT: 290 return dest.right - source.right; 291 case View.FOCUS_UP: 292 return source.top - dest.top; 293 case View.FOCUS_DOWN: 294 return dest.bottom - source.bottom; 295 } 296 throw new IllegalArgumentException("direction must be one of " 297 + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 298 } 299 300 /** 301 * Projects {@code rect1} and {@code rect2} onto Y axis, and returns whether the two projected 302 * intervals overlap. The overlap length must be > 0, otherwise it's not considered overlap. 303 */ overlapOnYAxis(Rect rect1, Rect rect2)304 private static boolean overlapOnYAxis(Rect rect1, Rect rect2) { 305 return rect1.bottom > rect2.top && rect1.top < rect2.bottom; 306 } 307 308 /** 309 * Projects {@code rect1} and {@code rect2} onto X axis, and returns whether the two projected 310 * intervals overlap. The overlap length must be > 0, otherwise it's not considered overlap. 311 */ overlapOnXAxis(Rect rect1, Rect rect2)312 private static boolean overlapOnXAxis(Rect rect1, Rect rect2) { 313 return rect1.left < rect2.right && rect1.right > rect2.left; 314 } 315 } 316