19066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* 29066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 39066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 49066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 59066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * you may not use this file except in compliance with the License. 69066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * You may obtain a copy of the License at 79066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 89066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 99066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * See the License for the specific language governing permissions and 149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * limitations under the License. 159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpackage android.view; 189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1901b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshevimport android.annotation.NonNull; 2001b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshevimport android.annotation.Nullable; 21d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Roskyimport android.annotation.TestApi; 2218b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Roskyimport android.content.pm.PackageManager; 239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport android.graphics.Rect; 24140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mountimport android.util.ArrayMap; 258448523665d682efaab93d2b76ef30e36f54c652Evan Roskyimport android.util.ArraySet; 269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport java.util.ArrayList; 28d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Roskyimport java.util.Arrays; 294e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brownimport java.util.Collections; 304e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brownimport java.util.Comparator; 31d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Roskyimport java.util.HashMap; 3201b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshevimport java.util.List; 339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/** 359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * The algorithm used for finding the next focusable view in a given direction 369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * from a view that currently has focus. 379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpublic class FocusFinder { 399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4076f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov private static final ThreadLocal<FocusFinder> tlFocusFinder = 419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project new ThreadLocal<FocusFinder>() { 424213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov @Override 439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project protected FocusFinder initialValue() { 449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return new FocusFinder(); 459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project }; 479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Get the focus finder for this thread. 509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static FocusFinder getInstance() { 529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return tlFocusFinder.get(); 539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5576f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov final Rect mFocusedRect = new Rect(); 5676f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov final Rect mOtherRect = new Rect(); 5776f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov final Rect mBestCandidateRect = new Rect(); 583b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky private final UserSpecifiedFocusComparator mUserSpecifiedFocusComparator = 598448523665d682efaab93d2b76ef30e36f54c652Evan Rosky new UserSpecifiedFocusComparator((r, v) -> isValidId(v.getNextFocusForwardId()) 608448523665d682efaab93d2b76ef30e36f54c652Evan Rosky ? v.findUserSetNextFocus(r, View.FOCUS_FORWARD) : null); 61bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky private final UserSpecifiedFocusComparator mUserSpecifiedClusterComparator = 628448523665d682efaab93d2b76ef30e36f54c652Evan Rosky new UserSpecifiedFocusComparator((r, v) -> isValidId(v.getNextClusterForwardId()) 638448523665d682efaab93d2b76ef30e36f54c652Evan Rosky ? v.findUserSetNextKeyboardNavigationCluster(r, View.FOCUS_FORWARD) : null); 64d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky private final FocusSorter mFocusSorter = new FocusSorter(); 659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 664213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov private final ArrayList<View> mTempList = new ArrayList<View>(); 674213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov 689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // enforce thread local access 699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private FocusFinder() {} 709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Find the next view to take focus in root's descendants, starting from the view 739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * that currently is focused. 747e0a372978eddf21808bf7fdfe36c1baa7f77e7cFabrice Di Meglio * @param root Contains focused. Cannot be null. 759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param focused Has focus now. 769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param direction Direction to look. 779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @return The next focusable view, or null if none exists. 789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public final View findNextFocus(ViewGroup root, View focused, int direction) { 80951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov return findNextFocus(root, focused, null, direction); 814213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov } 829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 834213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov /** 844213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov * Find the next view to take focus in root's descendants, searching from 854213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov * a particular rectangle in root's coordinates. 864213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov * @param root Contains focusedRect. Cannot be null. 874213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov * @param focusedRect The starting point of the search. 884213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov * @param direction Direction to look. 894213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov * @return The next focusable view, or null if none exists. 904213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov */ 914213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov public View findNextFocusFromRect(ViewGroup root, Rect focusedRect, int direction) { 9276f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov mFocusedRect.set(focusedRect); 9376f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov return findNextFocus(root, null, mFocusedRect, direction); 944213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov } 954213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov 964213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov private View findNextFocus(ViewGroup root, View focused, Rect focusedRect, int direction) { 9776f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov View next = null; 9818b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky ViewGroup effectiveRoot = getEffectiveRoot(root, focused); 999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (focused != null) { 10018b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky next = findNextUserSpecifiedFocus(effectiveRoot, focused, direction); 10176f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov } 10276f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov if (next != null) { 10376f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov return next; 10476f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov } 10576f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov ArrayList<View> focusables = mTempList; 10676f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov try { 10776f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov focusables.clear(); 10818b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky effectiveRoot.addFocusables(focusables, direction); 10976f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov if (!focusables.isEmpty()) { 11018b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky next = findNextFocus(effectiveRoot, focused, focusedRect, direction, focusables); 1119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 11276f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov } finally { 11376f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov focusables.clear(); 11476f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov } 11576f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov return next; 11676f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov } 11776f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov 11801b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev /** 11918b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky * Returns the "effective" root of a view. The "effective" root is the closest ancestor 12018b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky * within-which focus should cycle. 12118b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky * <p> 12218b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky * For example: normal focus navigation would stay within a ViewGroup marked as 12318b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky * touchscreenBlocksFocus and keyboardNavigationCluster until a cluster-jump out. 12418b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky * @return the "effective" root of {@param focused} 12518b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky */ 12618b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky private ViewGroup getEffectiveRoot(ViewGroup root, View focused) { 127e55f4a611eec44714cb39f57f2cb66c33da791d9Evan Rosky if (focused == null || focused == root) { 12818b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky return root; 12918b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky } 1300e8a6832947b074e36834736f55d63f445f604b1Evan Rosky ViewGroup effective = null; 1310e8a6832947b074e36834736f55d63f445f604b1Evan Rosky ViewParent nextParent = focused.getParent(); 13218b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky do { 1330e8a6832947b074e36834736f55d63f445f604b1Evan Rosky if (nextParent == root) { 1340e8a6832947b074e36834736f55d63f445f604b1Evan Rosky return effective != null ? effective : root; 13518b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky } 1360e8a6832947b074e36834736f55d63f445f604b1Evan Rosky ViewGroup vg = (ViewGroup) nextParent; 13718b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky if (vg.getTouchscreenBlocksFocus() 13818b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky && focused.getContext().getPackageManager().hasSystemFeature( 13918b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky PackageManager.FEATURE_TOUCHSCREEN) 14018b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky && vg.isKeyboardNavigationCluster()) { 1410e8a6832947b074e36834736f55d63f445f604b1Evan Rosky // Don't stop and return here because the cluster could be nested and we only 1420e8a6832947b074e36834736f55d63f445f604b1Evan Rosky // care about the top-most one. 1430e8a6832947b074e36834736f55d63f445f604b1Evan Rosky effective = vg; 14418b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky } 1450e8a6832947b074e36834736f55d63f445f604b1Evan Rosky nextParent = nextParent.getParent(); 1460e8a6832947b074e36834736f55d63f445f604b1Evan Rosky } while (nextParent instanceof ViewGroup); 14718b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky return root; 14818b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky } 14918b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky 15018b886e8b2fa9d02869132a2e8f1eca997b22f6fEvan Rosky /** 151b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev * Find the root of the next keyboard navigation cluster after the current one. 1528957f2ddda08e891475e64552ffa225ca2fccedbVadim Tryshev * @param root The view tree to look inside. Cannot be null 153b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev * @param currentCluster The starting point of the search. Null means the default cluster 15401b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev * @param direction Direction to look 155b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev * @return The next cluster, or null if none exists 15601b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev */ 157b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev public View findNextKeyboardNavigationCluster( 1588957f2ddda08e891475e64552ffa225ca2fccedbVadim Tryshev @NonNull View root, 159b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev @Nullable View currentCluster, 1605722331efeaa362e27585026e953c2fda677c516Evan Rosky @View.FocusDirection int direction) { 16101b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev View next = null; 162bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky if (currentCluster != null) { 163bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky next = findNextUserSpecifiedKeyboardNavigationCluster(root, currentCluster, direction); 164bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky if (next != null) { 165bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky return next; 166bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky } 167bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky } 16801b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev 169b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev final ArrayList<View> clusters = mTempList; 17001b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev try { 171b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev clusters.clear(); 172b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev root.addKeyboardNavigationClusters(clusters, direction); 173b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev if (!clusters.isEmpty()) { 174b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev next = findNextKeyboardNavigationCluster( 175b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev root, currentCluster, clusters, direction); 17601b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev } 17701b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev } finally { 178b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev clusters.clear(); 17901b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev } 18001b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev return next; 18101b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev } 18201b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev 183bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky private View findNextUserSpecifiedKeyboardNavigationCluster(View root, View currentCluster, 184bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky int direction) { 185bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky View userSetNextCluster = 186bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky currentCluster.findUserSetNextKeyboardNavigationCluster(root, direction); 187bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky if (userSetNextCluster != null && userSetNextCluster.hasFocusable()) { 188bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky return userSetNextCluster; 189bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky } 190bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky return null; 191bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky } 192bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky 19327e2da7c171afa39358bbead18fbe3e6b8ea6637Svetoslav Ganov private View findNextUserSpecifiedFocus(ViewGroup root, View focused, int direction) { 19476f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov // check for user specified next focus 19576f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov View userSetNextFocus = focused.findUserSetNextFocus(root, direction); 1969d93486ed6a62a4c114a4d79796f9cfd117eff98Evan Rosky View cycleCheck = userSetNextFocus; 1979d93486ed6a62a4c114a4d79796f9cfd117eff98Evan Rosky boolean cycleStep = true; // we want the first toggle to yield false 198ca6b876575d2c0d8bf93fd9b2c395235ffb63016Evan Rosky while (userSetNextFocus != null) { 199ca6b876575d2c0d8bf93fd9b2c395235ffb63016Evan Rosky if (userSetNextFocus.isFocusable() 200ca6b876575d2c0d8bf93fd9b2c395235ffb63016Evan Rosky && userSetNextFocus.getVisibility() == View.VISIBLE 201ca6b876575d2c0d8bf93fd9b2c395235ffb63016Evan Rosky && (!userSetNextFocus.isInTouchMode() 202ca6b876575d2c0d8bf93fd9b2c395235ffb63016Evan Rosky || userSetNextFocus.isFocusableInTouchMode())) { 203ca6b876575d2c0d8bf93fd9b2c395235ffb63016Evan Rosky return userSetNextFocus; 204ca6b876575d2c0d8bf93fd9b2c395235ffb63016Evan Rosky } 205ca6b876575d2c0d8bf93fd9b2c395235ffb63016Evan Rosky userSetNextFocus = userSetNextFocus.findUserSetNextFocus(root, direction); 2069d93486ed6a62a4c114a4d79796f9cfd117eff98Evan Rosky if (cycleStep = !cycleStep) { 2079d93486ed6a62a4c114a4d79796f9cfd117eff98Evan Rosky cycleCheck = cycleCheck.findUserSetNextFocus(root, direction); 2089d93486ed6a62a4c114a4d79796f9cfd117eff98Evan Rosky if (cycleCheck == userSetNextFocus) { 2099d93486ed6a62a4c114a4d79796f9cfd117eff98Evan Rosky // found a cycle, user-specified focus forms a loop and none of the views 2109d93486ed6a62a4c114a4d79796f9cfd117eff98Evan Rosky // are currently focusable. 2119d93486ed6a62a4c114a4d79796f9cfd117eff98Evan Rosky break; 2129d93486ed6a62a4c114a4d79796f9cfd117eff98Evan Rosky } 2139d93486ed6a62a4c114a4d79796f9cfd117eff98Evan Rosky } 21476f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov } 21576f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov return null; 21676f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov } 2179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 21876f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov private View findNextFocus(ViewGroup root, View focused, Rect focusedRect, 21976f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov int direction, ArrayList<View> focusables) { 22076f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov if (focused != null) { 221951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov if (focusedRect == null) { 222951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov focusedRect = mFocusedRect; 223951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov } 2249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // fill in interesting rect from focused 22576f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov focused.getFocusedRect(focusedRect); 22676f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov root.offsetDescendantRectToMyCoords(focused, focusedRect); 2279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 228951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov if (focusedRect == null) { 229951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov focusedRect = mFocusedRect; 230951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov // make up a rect at top left or bottom right of root 23127e2da7c171afa39358bbead18fbe3e6b8ea6637Svetoslav Ganov switch (direction) { 232951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov case View.FOCUS_RIGHT: 233951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov case View.FOCUS_DOWN: 23476f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov setFocusTopLeft(root, focusedRect); 235951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov break; 236951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov case View.FOCUS_FORWARD: 237951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov if (root.isLayoutRtl()) { 238951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov setFocusBottomRight(root, focusedRect); 239951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov } else { 240951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov setFocusTopLeft(root, focusedRect); 241951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov } 242951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov break; 243951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov 244951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov case View.FOCUS_LEFT: 245951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov case View.FOCUS_UP: 24676f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov setFocusBottomRight(root, focusedRect); 247951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov break; 248951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov case View.FOCUS_BACKWARD: 249951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov if (root.isLayoutRtl()) { 250951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov setFocusTopLeft(root, focusedRect); 251951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov } else { 252951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov setFocusBottomRight(root, focusedRect); 253951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov break; 254951bb421668b82ca014f75d265b161f6ff64d36bSvetoslav Ganov } 255702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio } 2569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 25927e2da7c171afa39358bbead18fbe3e6b8ea6637Svetoslav Ganov switch (direction) { 26076f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov case View.FOCUS_FORWARD: 26176f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov case View.FOCUS_BACKWARD: 26227e2da7c171afa39358bbead18fbe3e6b8ea6637Svetoslav Ganov return findNextFocusInRelativeDirection(focusables, root, focused, focusedRect, 26327e2da7c171afa39358bbead18fbe3e6b8ea6637Svetoslav Ganov direction); 26476f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov case View.FOCUS_UP: 26576f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov case View.FOCUS_DOWN: 26676f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov case View.FOCUS_LEFT: 26776f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov case View.FOCUS_RIGHT: 26827e2da7c171afa39358bbead18fbe3e6b8ea6637Svetoslav Ganov return findNextFocusInAbsoluteDirection(focusables, root, focused, 26927e2da7c171afa39358bbead18fbe3e6b8ea6637Svetoslav Ganov focusedRect, direction); 27076f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov default: 27127e2da7c171afa39358bbead18fbe3e6b8ea6637Svetoslav Ganov throw new IllegalArgumentException("Unknown direction: " + direction); 2724213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov } 273702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio } 274702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio 275b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev private View findNextKeyboardNavigationCluster( 2768957f2ddda08e891475e64552ffa225ca2fccedbVadim Tryshev View root, 277b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev View currentCluster, 278b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev List<View> clusters, 2795722331efeaa362e27585026e953c2fda677c516Evan Rosky @View.FocusDirection int direction) { 280bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky try { 281bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky // Note: This sort is stable. 2828448523665d682efaab93d2b76ef30e36f54c652Evan Rosky mUserSpecifiedClusterComparator.setFocusables(clusters, root); 283bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky Collections.sort(clusters, mUserSpecifiedClusterComparator); 284bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky } finally { 285bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky mUserSpecifiedClusterComparator.recycle(); 286bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky } 287b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev final int count = clusters.size(); 28801b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev 28901b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev switch (direction) { 29001b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev case View.FOCUS_FORWARD: 29101b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev case View.FOCUS_DOWN: 29201b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev case View.FOCUS_RIGHT: 293b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev return getNextKeyboardNavigationCluster(root, currentCluster, clusters, count); 29401b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev case View.FOCUS_BACKWARD: 29501b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev case View.FOCUS_UP: 29601b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev case View.FOCUS_LEFT: 297b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev return getPreviousKeyboardNavigationCluster(root, currentCluster, clusters, count); 29801b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev default: 29901b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev throw new IllegalArgumentException("Unknown direction: " + direction); 30001b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev } 30101b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev } 30201b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev 30327e2da7c171afa39358bbead18fbe3e6b8ea6637Svetoslav Ganov private View findNextFocusInRelativeDirection(ArrayList<View> focusables, ViewGroup root, 3044213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov View focused, Rect focusedRect, int direction) { 3054213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov try { 3064213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov // Note: This sort is stable. 3078448523665d682efaab93d2b76ef30e36f54c652Evan Rosky mUserSpecifiedFocusComparator.setFocusables(focusables, root); 3083b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky Collections.sort(focusables, mUserSpecifiedFocusComparator); 3094213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov } finally { 3103b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky mUserSpecifiedFocusComparator.recycle(); 3114e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown } 3129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3134213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov final int count = focusables.size(); 3144213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov switch (direction) { 3154213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov case View.FOCUS_FORWARD: 3163167c88c2c18eaadb046d41e2108bf45eae0d289Fabrice Di Meglio return getNextFocusable(focused, focusables, count); 3174213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov case View.FOCUS_BACKWARD: 3183167c88c2c18eaadb046d41e2108bf45eae0d289Fabrice Di Meglio return getPreviousFocusable(focused, focusables, count); 3194213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov } 3204213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov return focusables.get(count - 1); 3214213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov } 3224213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov 32376f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov private void setFocusBottomRight(ViewGroup root, Rect focusedRect) { 3244213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov final int rootBottom = root.getScrollY() + root.getHeight(); 3254213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov final int rootRight = root.getScrollX() + root.getWidth(); 32676f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov focusedRect.set(rootRight, rootBottom, rootRight, rootBottom); 3274213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov } 3284213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov 32976f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov private void setFocusTopLeft(ViewGroup root, Rect focusedRect) { 3304213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov final int rootTop = root.getScrollY(); 3314213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov final int rootLeft = root.getScrollX(); 33276f287e416ded85734b610f316e38d243d2ddb09Svetoslav Ganov focusedRect.set(rootLeft, rootTop, rootLeft, rootTop); 3334213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov } 3344213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov 33527e2da7c171afa39358bbead18fbe3e6b8ea6637Svetoslav Ganov View findNextFocusInAbsoluteDirection(ArrayList<View> focusables, ViewGroup root, View focused, 3364213804541a8b05cd0587b138a2fd9a3b7fd9350Svetoslav Ganov Rect focusedRect, int direction) { 3379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // initialize the best candidate to something impossible 3389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // (so the first plausible view will become the best choice) 3399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mBestCandidateRect.set(focusedRect); 3409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project switch(direction) { 3419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_LEFT: 3429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mBestCandidateRect.offset(focusedRect.width() + 1, 0); 3439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 3449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_RIGHT: 3459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mBestCandidateRect.offset(-(focusedRect.width() + 1), 0); 3469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 3479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_UP: 3489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mBestCandidateRect.offset(0, focusedRect.height() + 1); 3499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 3509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_DOWN: 3519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mBestCandidateRect.offset(0, -(focusedRect.height() + 1)); 3529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project View closest = null; 3559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int numFocusables = focusables.size(); 3579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (int i = 0; i < numFocusables; i++) { 3589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project View focusable = focusables.get(i); 3599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // only interested in other non-root views 3619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (focusable == focused || focusable == root) continue; 3629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 363defdb1e49172fe7c9737347489dbb77361af955aTobias Dubois // get focus bounds of other view in same coordinate system 364c11f77fbae8391ca3c2d3ec93d024cba0be5cf55Fabrice Di Meglio focusable.getFocusedRect(mOtherRect); 3659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project root.offsetDescendantRectToMyCoords(focusable, mOtherRect); 3669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (isBetterCandidate(direction, focusedRect, mOtherRect, mBestCandidateRect)) { 3689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mBestCandidateRect.set(mOtherRect); 3699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project closest = focusable; 3709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return closest; 3739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3757e0a372978eddf21808bf7fdfe36c1baa7f77e7cFabrice Di Meglio private static View getNextFocusable(View focused, ArrayList<View> focusables, int count) { 376702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio if (focused != null) { 377702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio int position = focusables.lastIndexOf(focused); 378702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio if (position >= 0 && position + 1 < count) { 379702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio return focusables.get(position + 1); 380702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio } 381702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio } 382e5dfa47d84668376b84074c04570fb961870adebSvetoslav Ganov if (!focusables.isEmpty()) { 383e5dfa47d84668376b84074c04570fb961870adebSvetoslav Ganov return focusables.get(0); 384e5dfa47d84668376b84074c04570fb961870adebSvetoslav Ganov } 385e5dfa47d84668376b84074c04570fb961870adebSvetoslav Ganov return null; 386702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio } 387702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio 3887e0a372978eddf21808bf7fdfe36c1baa7f77e7cFabrice Di Meglio private static View getPreviousFocusable(View focused, ArrayList<View> focusables, int count) { 389702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio if (focused != null) { 390702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio int position = focusables.indexOf(focused); 391702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio if (position > 0) { 392702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio return focusables.get(position - 1); 393702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio } 394702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio } 395e5dfa47d84668376b84074c04570fb961870adebSvetoslav Ganov if (!focusables.isEmpty()) { 396e5dfa47d84668376b84074c04570fb961870adebSvetoslav Ganov return focusables.get(count - 1); 397e5dfa47d84668376b84074c04570fb961870adebSvetoslav Ganov } 398e5dfa47d84668376b84074c04570fb961870adebSvetoslav Ganov return null; 399702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio } 400702e8f9b9294d8227deae6e1f125a768ee4a28d4Fabrice Di Meglio 401b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev private static View getNextKeyboardNavigationCluster( 4028957f2ddda08e891475e64552ffa225ca2fccedbVadim Tryshev View root, 403b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev View currentCluster, 404b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev List<View> clusters, 4058957f2ddda08e891475e64552ffa225ca2fccedbVadim Tryshev int count) { 406b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev if (currentCluster == null) { 407b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev // The current cluster is the default one. 408b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev // The next cluster after the default one is the first one. 409b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev // Note that the caller guarantees that 'clusters' is not empty. 410b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev return clusters.get(0); 41101b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev } 41201b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev 413b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev final int position = clusters.lastIndexOf(currentCluster); 41401b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev if (position >= 0 && position + 1 < count) { 415b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev // Return the next non-default cluster if we can find it. 416b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev return clusters.get(position + 1); 41701b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev } 41801b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev 419b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev // The current cluster is the last one. The next one is the default one, i.e. the 420b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev // root. 421b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev return root; 42201b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev } 42301b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev 424b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev private static View getPreviousKeyboardNavigationCluster( 4258957f2ddda08e891475e64552ffa225ca2fccedbVadim Tryshev View root, 426b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev View currentCluster, 427b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev List<View> clusters, 4288957f2ddda08e891475e64552ffa225ca2fccedbVadim Tryshev int count) { 429b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev if (currentCluster == null) { 430b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev // The current cluster is the default one. 431b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev // The previous cluster before the default one is the last one. 432b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev // Note that the caller guarantees that 'clusters' is not empty. 433b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev return clusters.get(count - 1); 43401b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev } 43501b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev 436b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev final int position = clusters.indexOf(currentCluster); 43701b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev if (position > 0) { 438b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev // Return the previous non-default cluster if we can find it. 439b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev return clusters.get(position - 1); 44001b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev } 44101b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev 442b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev // The current cluster is the first one. The previous one is the default one, i.e. 443b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev // the root. 444b5ced2200767280026ee57857edaebc02d081216Vadim Tryshev return root; 44501b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev } 44601b0c9ed4e173f0c140a6575049e2964ae1a919fVadim Tryshev 4479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 4489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Is rect1 a better candidate than rect2 for a focus search in a particular 4499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * direction from a source rect? This is the core routine that determines 4509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * the order of focus searching. 4519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param direction the direction (up, down, left, right) 4529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param source The source we are searching from 4539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param rect1 The candidate rectangle 4549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param rect2 The current best candidate. 4559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @return Whether the candidate is the new best. 4569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 4579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project boolean isBetterCandidate(int direction, Rect source, Rect rect1, Rect rect2) { 4589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // to be a better candidate, need to at least be a candidate in the first 4609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // place :) 4619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!isCandidate(source, rect1, direction)) { 4629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return false; 4639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // we know that rect1 is a candidate.. if rect2 is not a candidate, 4669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // rect1 is better 4679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!isCandidate(source, rect2, direction)) { 4689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return true; 4699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // if rect1 is better by beam, it wins 4729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (beamBeats(direction, source, rect1, rect2)) { 4739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return true; 4749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // if rect2 is better, then rect1 cant' be :) 4779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (beamBeats(direction, source, rect2, rect1)) { 4789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return false; 4799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // otherwise, do fudge-tastic comparison of the major and minor axis 4829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (getWeightedDistanceFor( 4839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project majorAxisDistance(direction, source, rect1), 4849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project minorAxisDistance(direction, source, rect1)) 4859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project < getWeightedDistanceFor( 4869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project majorAxisDistance(direction, source, rect2), 4879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project minorAxisDistance(direction, source, rect2))); 4889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 4919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * One rectangle may be another candidate than another by virtue of being 4929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * exclusively in the beam of the source rect. 4939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @return Whether rect1 is a better candidate than rect2 by virtue of it being in src's 4949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * beam 4959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 4969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project boolean beamBeats(int direction, Rect source, Rect rect1, Rect rect2) { 4979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project final boolean rect1InSrcBeam = beamsOverlap(direction, source, rect1); 4989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project final boolean rect2InSrcBeam = beamsOverlap(direction, source, rect2); 4999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // if rect1 isn't exclusively in the src beam, it doesn't win 5019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (rect2InSrcBeam || !rect1InSrcBeam) { 5029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return false; 5039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // we know rect1 is in the beam, and rect2 is not 5069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // if rect1 is to the direction of, and rect2 is not, rect1 wins. 5089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // for example, for direction left, if rect1 is to the left of the source 5099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // and rect2 is below, then we always prefer the in beam rect1, since rect2 5109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // could be reached by going down. 5119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!isToDirectionOf(direction, source, rect2)) { 5129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return true; 5139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // for horizontal directions, being exclusively in beam always wins 5169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if ((direction == View.FOCUS_LEFT || direction == View.FOCUS_RIGHT)) { 5179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return true; 5189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // for vertical directions, beams only beat up to a point: 5219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // now, as long as rect2 isn't completely closer, rect1 wins 5229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // e.g for direction down, completely closer means for rect2's top 5239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // edge to be closer to the source's top edge than rect1's bottom edge. 5249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (majorAxisDistance(direction, source, rect1) 5259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project < majorAxisDistanceToFarEdge(direction, source, rect2)); 5269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 5299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Fudge-factor opportunity: how to calculate distance given major and minor 5309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * axis distances. Warning: this fudge factor is finely tuned, be sure to 5319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * run all focus tests if you dare tweak it. 5329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 5339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int getWeightedDistanceFor(int majorAxisDistance, int minorAxisDistance) { 5349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 13 * majorAxisDistance * majorAxisDistance 5359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project + minorAxisDistance * minorAxisDistance; 5369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 5399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Is destRect a candidate for the next focus given the direction? This 5409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * checks whether the dest is at least partially to the direction of (e.g left of) 5419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * from source. 5429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 5439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Includes an edge case for an empty rect (which is used in some cases when 5449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * searching from a point on the screen). 5459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 5469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project boolean isCandidate(Rect srcRect, Rect destRect, int direction) { 5479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project switch (direction) { 5489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_LEFT: 5499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (srcRect.right > destRect.right || srcRect.left >= destRect.right) 5509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project && srcRect.left > destRect.left; 5519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_RIGHT: 5529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (srcRect.left < destRect.left || srcRect.right <= destRect.left) 5539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project && srcRect.right < destRect.right; 5549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_UP: 5559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (srcRect.bottom > destRect.bottom || srcRect.top >= destRect.bottom) 5569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project && srcRect.top > destRect.top; 5579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_DOWN: 5589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (srcRect.top < destRect.top || srcRect.bottom <= destRect.top) 5599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project && srcRect.bottom < destRect.bottom; 5609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project throw new IllegalArgumentException("direction must be one of " 5629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 5639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 5677e0a372978eddf21808bf7fdfe36c1baa7f77e7cFabrice Di Meglio * Do the "beams" w.r.t the given direction's axis of rect1 and rect2 overlap? 5689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param direction the direction (up, down, left, right) 5699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param rect1 The first rectangle 5709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param rect2 The second rectangle 5719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @return whether the beams overlap 5729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 5739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project boolean beamsOverlap(int direction, Rect rect1, Rect rect2) { 5749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project switch (direction) { 5759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_LEFT: 5769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_RIGHT: 577815fb1f40cdfa7d546da38d16223967954d9ffdfEvan Rosky return (rect2.bottom > rect1.top) && (rect2.top < rect1.bottom); 5789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_UP: 5799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_DOWN: 580815fb1f40cdfa7d546da38d16223967954d9ffdfEvan Rosky return (rect2.right > rect1.left) && (rect2.left < rect1.right); 5819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project throw new IllegalArgumentException("direction must be one of " 5839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 5849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 5859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 5879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * e.g for left, is 'to left of' 5889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 5899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project boolean isToDirectionOf(int direction, Rect src, Rect dest) { 5909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project switch (direction) { 5919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_LEFT: 5929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return src.left >= dest.right; 5939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_RIGHT: 5949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return src.right <= dest.left; 5959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_UP: 5969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return src.top >= dest.bottom; 5979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_DOWN: 5989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return src.bottom <= dest.top; 5999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project throw new IllegalArgumentException("direction must be one of " 6019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 6029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 6059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @return The distance from the edge furthest in the given direction 6069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * of source to the edge nearest in the given direction of dest. If the 6079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * dest is not in the direction from source, return 0. 6089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 6099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project static int majorAxisDistance(int direction, Rect source, Rect dest) { 6109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return Math.max(0, majorAxisDistanceRaw(direction, source, dest)); 6119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project static int majorAxisDistanceRaw(int direction, Rect source, Rect dest) { 6149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project switch (direction) { 6159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_LEFT: 6169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return source.left - dest.right; 6179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_RIGHT: 6189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return dest.left - source.right; 6199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_UP: 6209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return source.top - dest.bottom; 6219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_DOWN: 6229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return dest.top - source.bottom; 6239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project throw new IllegalArgumentException("direction must be one of " 6259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 6269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 6299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @return The distance along the major axis w.r.t the direction from the 6309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * edge of source to the far edge of dest. If the 6319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * dest is not in the direction from source, return 1 (to break ties with 6329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * {@link #majorAxisDistance}). 6339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 6349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project static int majorAxisDistanceToFarEdge(int direction, Rect source, Rect dest) { 6359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return Math.max(1, majorAxisDistanceToFarEdgeRaw(direction, source, dest)); 6369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project static int majorAxisDistanceToFarEdgeRaw(int direction, Rect source, Rect dest) { 6399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project switch (direction) { 6409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_LEFT: 6419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return source.left - dest.left; 6429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_RIGHT: 6439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return dest.right - source.right; 6449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_UP: 6459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return source.top - dest.top; 6469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_DOWN: 6479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return dest.bottom - source.bottom; 6489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project throw new IllegalArgumentException("direction must be one of " 6509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 6519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 6549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Find the distance on the minor axis w.r.t the direction to the nearest 6557e0a372978eddf21808bf7fdfe36c1baa7f77e7cFabrice Di Meglio * edge of the destination rectangle. 6569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param direction the direction (up, down, left, right) 6579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param source The source rect. 6589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param dest The destination rect. 6599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @return The distance. 6609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 6619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project static int minorAxisDistance(int direction, Rect source, Rect dest) { 6629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project switch (direction) { 6639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_LEFT: 6649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_RIGHT: 6659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // the distance between the center verticals 6669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return Math.abs( 6679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ((source.top + source.height() / 2) - 6689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ((dest.top + dest.height() / 2)))); 6699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_UP: 6709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_DOWN: 6719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // the distance between the center horizontals 6729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return Math.abs( 6739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ((source.left + source.width() / 2) - 6749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ((dest.left + dest.width() / 2)))); 6759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project throw new IllegalArgumentException("direction must be one of " 6779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 6789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 6799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 6819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Find the nearest touchable view to the specified view. 6829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 6839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param root The root of the tree in which to search 6849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param x X coordinate from which to start the search 6859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param y Y coordinate from which to start the search 6869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param direction Direction to look 6879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param deltas Offset from the <x, y> to the edge of the nearest view. Note that this array 6889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * may already be populated with values. 6899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @return The nearest touchable view, or null if none exists. 6909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 6919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public View findNearestTouchable(ViewGroup root, int x, int y, int direction, int[] deltas) { 6929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ArrayList<View> touchables = root.getTouchables(); 6939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int minDistance = Integer.MAX_VALUE; 6949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project View closest = null; 6959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int numTouchables = touchables.size(); 6979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int edgeSlop = ViewConfiguration.get(root.mContext).getScaledEdgeSlop(); 6999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Rect closestBounds = new Rect(); 7019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Rect touchableBounds = mOtherRect; 7029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (int i = 0; i < numTouchables; i++) { 7049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project View touchable = touchables.get(i); 7059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // get visible bounds of other view in same coordinate system 7079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project touchable.getDrawingRect(touchableBounds); 7089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project root.offsetRectBetweenParentAndChild(touchable, touchableBounds, true, true); 7109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!isTouchCandidate(x, y, touchableBounds, direction)) { 7129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project continue; 7139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int distance = Integer.MAX_VALUE; 7169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project switch (direction) { 7189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_LEFT: 7199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project distance = x - touchableBounds.right + 1; 7209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 7219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_RIGHT: 7229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project distance = touchableBounds.left; 7239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 7249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_UP: 7259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project distance = y - touchableBounds.bottom + 1; 7269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 7279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_DOWN: 7289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project distance = touchableBounds.top; 7299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 7309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (distance < edgeSlop) { 7339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Give preference to innermost views 7349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (closest == null || 7359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project closestBounds.contains(touchableBounds) || 7369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project (!touchableBounds.contains(closestBounds) && distance < minDistance)) { 7379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project minDistance = distance; 7389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project closest = touchable; 7399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project closestBounds.set(touchableBounds); 7409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project switch (direction) { 7419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_LEFT: 7429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project deltas[0] = -distance; 7439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 7449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_RIGHT: 7459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project deltas[0] = distance; 7469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 7479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_UP: 7489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project deltas[1] = -distance; 7499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 7509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_DOWN: 7519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project deltas[1] = distance; 7529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 7539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return closest; 7589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 7619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 7629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Is destRect a candidate for the next touch given the direction? 7639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 7649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private boolean isTouchCandidate(int x, int y, Rect destRect, int direction) { 7659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project switch (direction) { 7669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_LEFT: 7679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return destRect.left <= x && destRect.top <= y && y <= destRect.bottom; 7689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_RIGHT: 7699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return destRect.left >= x && destRect.top <= y && y <= destRect.bottom; 7709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_UP: 7719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return destRect.top <= y && destRect.left <= x && x <= destRect.right; 7729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case View.FOCUS_DOWN: 7739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return destRect.top >= y && destRect.left <= x && x <= destRect.right; 7749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project throw new IllegalArgumentException("direction must be one of " 7769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project + "{FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, FOCUS_RIGHT}."); 7779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 7784e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown 779140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount private static final boolean isValidId(final int id) { 780140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount return id != 0 && id != View.NO_ID; 781140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 782140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount 783d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky static final class FocusSorter { 784d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky private ArrayList<Rect> mRectPool = new ArrayList<>(); 785d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky private int mLastPoolRect; 786d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky private int mRtlMult; 787d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky private HashMap<View, Rect> mRectByView = null; 7883b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky 789d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky private Comparator<View> mTopsComparator = (first, second) -> { 790d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky if (first == second) { 791d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky return 0; 792d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky } 7933b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky 794d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky Rect firstRect = mRectByView.get(first); 795d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky Rect secondRect = mRectByView.get(second); 7963b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky 797d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky int result = firstRect.top - secondRect.top; 798d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky if (result == 0) { 799d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky return firstRect.bottom - secondRect.bottom; 800d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky } 801d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky return result; 802d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky }; 8033b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky 804d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky private Comparator<View> mSidesComparator = (first, second) -> { 8053b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky if (first == second) { 8063b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky return 0; 8073b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky } 8083b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky 809d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky Rect firstRect = mRectByView.get(first); 810d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky Rect secondRect = mRectByView.get(second); 811d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky 812d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky int result = firstRect.left - secondRect.left; 813d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky if (result == 0) { 814d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky return firstRect.right - secondRect.right; 8153b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky } 816d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky return mRtlMult * result; 817d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky }; 8183b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky 819d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky public void sort(View[] views, int start, int end, ViewGroup root, boolean isRtl) { 820d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky int count = end - start; 821d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky if (count < 2) { 822d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky return; 823d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky } 824d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky if (mRectByView == null) { 825d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky mRectByView = new HashMap<>(); 826d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky } 827d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky mRtlMult = isRtl ? -1 : 1; 828d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky for (int i = mRectPool.size(); i < count; ++i) { 829d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky mRectPool.add(new Rect()); 830d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky } 831d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky for (int i = start; i < end; ++i) { 832d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky Rect next = mRectPool.get(mLastPoolRect++); 833d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky views[i].getDrawingRect(next); 834d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky root.offsetDescendantRectToMyCoords(views[i], next); 835d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky mRectByView.put(views[i], next); 836d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky } 837d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky 838d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky // Sort top-to-bottom 839d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky Arrays.sort(views, start, count, mTopsComparator); 840d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky // Sweep top-to-bottom to identify rows 841d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky int sweepBottom = mRectByView.get(views[start]).bottom; 842d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky int rowStart = start; 843d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky int sweepIdx = start + 1; 844d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky for (; sweepIdx < end; ++sweepIdx) { 845d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky Rect currRect = mRectByView.get(views[sweepIdx]); 846d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky if (currRect.top >= sweepBottom) { 847d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky // Next view is on a new row, sort the row we've just finished left-to-right. 848d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky if ((sweepIdx - rowStart) > 1) { 849d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky Arrays.sort(views, rowStart, sweepIdx, mSidesComparator); 850d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky } 851d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky sweepBottom = currRect.bottom; 852d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky rowStart = sweepIdx; 853d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky } else { 854d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky // Next view vertically overlaps, we need to extend our "row height" 855d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky sweepBottom = Math.max(sweepBottom, currRect.bottom); 856d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky } 857d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky } 858d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky // Sort whatever's left (final row) left-to-right 859d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky if ((sweepIdx - rowStart) > 1) { 860d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky Arrays.sort(views, rowStart, sweepIdx, mSidesComparator); 861d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky } 862d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky 863d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky mLastPoolRect = 0; 864d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky mRectByView.clear(); 8653b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky } 8663b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky } 8673b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky 8683b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky /** 869d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky * Public for testing. 870d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky * 871d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky * @hide 872d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky */ 873d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky @TestApi 874d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky public static void sort(View[] views, int start, int end, ViewGroup root, boolean isRtl) { 875d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky getInstance().mFocusSorter.sort(views, start, end, root, isRtl); 876d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky } 877d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky 878d114e0fc59dc57cc90694dd8634c6ab8c473819cEvan Rosky /** 8793b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky * Sorts views according to any explicitly-specified focus-chains. If there are no explicitly 8803b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky * specified focus chains (eg. no nextFocusForward attributes defined), this should be a no-op. 8813b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky */ 8823b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky private static final class UserSpecifiedFocusComparator implements Comparator<View> { 8838448523665d682efaab93d2b76ef30e36f54c652Evan Rosky private final ArrayMap<View, View> mNextFoci = new ArrayMap<>(); 8848448523665d682efaab93d2b76ef30e36f54c652Evan Rosky private final ArraySet<View> mIsConnectedTo = new ArraySet<>(); 885140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount private final ArrayMap<View, View> mHeadsOfChains = new ArrayMap<View, View>(); 8863b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky private final ArrayMap<View, Integer> mOriginalOrdinal = new ArrayMap<>(); 8878448523665d682efaab93d2b76ef30e36f54c652Evan Rosky private final NextFocusGetter mNextFocusGetter; 8888448523665d682efaab93d2b76ef30e36f54c652Evan Rosky private View mRoot; 889bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky 8908448523665d682efaab93d2b76ef30e36f54c652Evan Rosky public interface NextFocusGetter { 8918448523665d682efaab93d2b76ef30e36f54c652Evan Rosky View get(View root, View view); 892bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky } 893bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky 8948448523665d682efaab93d2b76ef30e36f54c652Evan Rosky UserSpecifiedFocusComparator(NextFocusGetter nextFocusGetter) { 8958448523665d682efaab93d2b76ef30e36f54c652Evan Rosky mNextFocusGetter = nextFocusGetter; 896bd10c52f5efc73f7ffdd611beb14cdd7ce785016Evan Rosky } 8974e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown 8984e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown public void recycle() { 8998448523665d682efaab93d2b76ef30e36f54c652Evan Rosky mRoot = null; 900140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount mHeadsOfChains.clear(); 901140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount mIsConnectedTo.clear(); 9023b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky mOriginalOrdinal.clear(); 9038448523665d682efaab93d2b76ef30e36f54c652Evan Rosky mNextFoci.clear(); 9043167c88c2c18eaadb046d41e2108bf45eae0d289Fabrice Di Meglio } 9053167c88c2c18eaadb046d41e2108bf45eae0d289Fabrice Di Meglio 9068448523665d682efaab93d2b76ef30e36f54c652Evan Rosky public void setFocusables(List<View> focusables, View root) { 9078448523665d682efaab93d2b76ef30e36f54c652Evan Rosky mRoot = root; 9088448523665d682efaab93d2b76ef30e36f54c652Evan Rosky for (int i = 0; i < focusables.size(); ++i) { 9098448523665d682efaab93d2b76ef30e36f54c652Evan Rosky mOriginalOrdinal.put(focusables.get(i), i); 9108448523665d682efaab93d2b76ef30e36f54c652Evan Rosky } 9118448523665d682efaab93d2b76ef30e36f54c652Evan Rosky 912140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount for (int i = focusables.size() - 1; i >= 0; i--) { 913140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount final View view = focusables.get(i); 9148448523665d682efaab93d2b76ef30e36f54c652Evan Rosky final View next = mNextFocusGetter.get(mRoot, view); 9158448523665d682efaab93d2b76ef30e36f54c652Evan Rosky if (next != null && mOriginalOrdinal.containsKey(next)) { 9168448523665d682efaab93d2b76ef30e36f54c652Evan Rosky mNextFoci.put(view, next); 9178448523665d682efaab93d2b76ef30e36f54c652Evan Rosky mIsConnectedTo.add(next); 918140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 919140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 920140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount 921140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount for (int i = focusables.size() - 1; i >= 0; i--) { 922140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount final View view = focusables.get(i); 9238448523665d682efaab93d2b76ef30e36f54c652Evan Rosky final View next = mNextFoci.get(view); 9248448523665d682efaab93d2b76ef30e36f54c652Evan Rosky if (next != null && !mIsConnectedTo.contains(view)) { 925140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount setHeadOfChain(view); 926140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 927140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 928140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 929140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount 930140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount private void setHeadOfChain(View head) { 9318448523665d682efaab93d2b76ef30e36f54c652Evan Rosky for (View view = head; view != null; view = mNextFoci.get(view)) { 932140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount final View otherHead = mHeadsOfChains.get(view); 933140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount if (otherHead != null) { 934140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount if (otherHead == head) { 935140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount return; // This view has already had its head set properly 936140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 937140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount // A hydra -- multi-headed focus chain (e.g. A->C and B->C) 938140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount // Use the one we've already chosen instead and reset this chain. 939140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount view = head; 940140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount head = otherHead; 941140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 942140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount mHeadsOfChains.put(view, head); 943140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 944140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 945140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount 9464e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown public int compare(View first, View second) { 9474e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown if (first == second) { 9484e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown return 0; 9494e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown } 950140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount // Order between views within a chain is immaterial -- next/previous is 951140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount // within a chain is handled elsewhere. 952140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount View firstHead = mHeadsOfChains.get(first); 953140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount View secondHead = mHeadsOfChains.get(second); 954140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount if (firstHead == secondHead && firstHead != null) { 955140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount if (first == firstHead) { 956140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount return -1; // first is the head, it should be first 957140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } else if (second == firstHead) { 958140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount return 1; // second is the head, it should be first 9598448523665d682efaab93d2b76ef30e36f54c652Evan Rosky } else if (mNextFoci.get(first) != null) { 960140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount return -1; // first is not the end of the chain 961140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } else { 962140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount return 1; // first is end of chain 963140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 964140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 9653b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky boolean involvesChain = false; 966140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount if (firstHead != null) { 967140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount first = firstHead; 9683b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky involvesChain = true; 969140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 970140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount if (secondHead != null) { 971140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount second = secondHead; 9723b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky involvesChain = true; 973140ea62c385cfe0b9ab28b8c2b78d0f61a118adaGeorge Mount } 9744e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown 9753b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky if (involvesChain) { 9763b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky // keep original order between chains 9773b94bf5c3e607a47ed60c13a2e96d1873177b659Evan Rosky return mOriginalOrdinal.get(first) < mOriginalOrdinal.get(second) ? -1 : 1; 9784e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown } else { 9794e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown return 0; 9804e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown } 9814e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown } 9824e6319b73c85082e18d1c532b86336ddd1f8cfaaJeff Brown } 9839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 984