Teleportation between clusters.

Per the UX spec, key combos for quickly jumping between clusters are
Meta+Right and Meta+Left. However, these events don’t get delivered
to the app, and I’ll have to implement this plumbing after the
feature freeze. For now, the temporary combos are Ctrl-Shift-”-”
and Ctrl-Shift-”+”.

In addition to the key combo processing, the CL adds public APIs for
teleportation; they are similar to the API for moving the focus.

Bug: 32151632
Test: Manually checking that teleportation works. CTS test will be
added after the feature freeze.

Change-Id: I622156b9e4cc7c44e61623081d6d079bbe04fd02

8 files changed, 306 insertions, 63 deletions

diff --git a/api/current.txt b/api/current.txt
index 66390e8177cc..983bc33bf116 100644
--- a/api/current.txt
+++ b/api/current.txt
@@ -41617,6 +41617,7 @@ package android.view {
     method public android.view.View findNearestTouchable(android.view.ViewGroup, int, int, int, int[]);
     method public final android.view.View findNextFocus(android.view.ViewGroup, android.view.View, int);
     method public android.view.View findNextFocusFromRect(android.view.ViewGroup, android.graphics.Rect, int);
+    method public android.view.View findNextKeyboardNavigationCluster(android.view.ViewGroup, android.view.View, int);
     method public static android.view.FocusFinder getInstance();
   }
 
@@ -42909,6 +42910,7 @@ package android.view {
     method public void addChildrenForAccessibility(java.util.ArrayList<android.view.View>);
     method public void addFocusables(java.util.ArrayList<android.view.View>, int);
     method public void addFocusables(java.util.ArrayList<android.view.View>, int, int);
+    method public void addKeyboardNavigationClusters(java.util.Collection<android.view.View>, int);
     method public void addOnAttachStateChangeListener(android.view.View.OnAttachStateChangeListener);
     method public void addOnLayoutChangeListener(android.view.View.OnLayoutChangeListener);
     method public void addTouchables(java.util.ArrayList<android.view.View>);
@@ -43196,6 +43198,7 @@ package android.view {
     method public boolean isVerticalFadingEdgeEnabled();
     method public boolean isVerticalScrollBarEnabled();
     method public void jumpDrawablesToCurrentState();
+    method public android.view.View keyboardNavigationClusterSearch(int);
     method public void layout(int, int, int, int);
     method public final void measure(int, int);
     method protected static int[] mergeDrawableStates(int[], int[]);
@@ -43843,6 +43846,7 @@ package android.view {
     method protected deprecated boolean isChildrenDrawnWithCacheEnabled();
     method public boolean isMotionEventSplittingEnabled();
     method public boolean isTransitionGroup();
+    method public android.view.View keyboardNavigationClusterSearch(android.view.View, int);
     method public final void layout(int, int, int, int);
     method protected void measureChild(android.view.View, int, int);
     method protected void measureChildWithMargins(android.view.View, int, int, int, int);
@@ -44005,6 +44009,7 @@ package android.view {
     method public abstract boolean isLayoutRequested();
     method public abstract boolean isTextAlignmentResolved();
     method public abstract boolean isTextDirectionResolved();
+    method public abstract android.view.View keyboardNavigationClusterSearch(android.view.View, int);
     method public abstract void notifySubtreeAccessibilityStateChanged(android.view.View, android.view.View, int);
     method public abstract boolean onNestedFling(android.view.View, float, float, boolean);
     method public abstract boolean onNestedPreFling(android.view.View, float, float);
diff --git a/api/system-current.txt b/api/system-current.txt
index 6d45b6ce71ce..9b8c441cb58f 100644
--- a/api/system-current.txt
+++ b/api/system-current.txt
@@ -44814,6 +44814,7 @@ package android.view {
     method public android.view.View findNearestTouchable(android.view.ViewGroup, int, int, int, int[]);
     method public final android.view.View findNextFocus(android.view.ViewGroup, android.view.View, int);
     method public android.view.View findNextFocusFromRect(android.view.ViewGroup, android.graphics.Rect, int);
+    method public android.view.View findNextKeyboardNavigationCluster(android.view.ViewGroup, android.view.View, int);
     method public static android.view.FocusFinder getInstance();
   }
 
@@ -46106,6 +46107,7 @@ package android.view {
     method public void addChildrenForAccessibility(java.util.ArrayList<android.view.View>);
     method public void addFocusables(java.util.ArrayList<android.view.View>, int);
     method public void addFocusables(java.util.ArrayList<android.view.View>, int, int);
+    method public void addKeyboardNavigationClusters(java.util.Collection<android.view.View>, int);
     method public void addOnAttachStateChangeListener(android.view.View.OnAttachStateChangeListener);
     method public void addOnLayoutChangeListener(android.view.View.OnLayoutChangeListener);
     method public void addTouchables(java.util.ArrayList<android.view.View>);
@@ -46393,6 +46395,7 @@ package android.view {
     method public boolean isVerticalFadingEdgeEnabled();
     method public boolean isVerticalScrollBarEnabled();
     method public void jumpDrawablesToCurrentState();
+    method public android.view.View keyboardNavigationClusterSearch(int);
     method public void layout(int, int, int, int);
     method public final void measure(int, int);
     method protected static int[] mergeDrawableStates(int[], int[]);
@@ -47040,6 +47043,7 @@ package android.view {
     method protected deprecated boolean isChildrenDrawnWithCacheEnabled();
     method public boolean isMotionEventSplittingEnabled();
     method public boolean isTransitionGroup();
+    method public android.view.View keyboardNavigationClusterSearch(android.view.View, int);
     method public final void layout(int, int, int, int);
     method protected void measureChild(android.view.View, int, int);
     method protected void measureChildWithMargins(android.view.View, int, int, int, int);
@@ -47202,6 +47206,7 @@ package android.view {
     method public abstract boolean isLayoutRequested();
     method public abstract boolean isTextAlignmentResolved();
     method public abstract boolean isTextDirectionResolved();
+    method public abstract android.view.View keyboardNavigationClusterSearch(android.view.View, int);
     method public abstract void notifySubtreeAccessibilityStateChanged(android.view.View, android.view.View, int);
     method public abstract boolean onNestedFling(android.view.View, float, float, boolean);
     method public abstract boolean onNestedPreFling(android.view.View, float, float);
diff --git a/api/test-current.txt b/api/test-current.txt
index 239863ab05ca..2dec82e95b87 100644
--- a/api/test-current.txt
+++ b/api/test-current.txt
@@ -41883,6 +41883,7 @@ package android.view {
     method public android.view.View findNearestTouchable(android.view.ViewGroup, int, int, int, int[]);
     method public final android.view.View findNextFocus(android.view.ViewGroup, android.view.View, int);
     method public android.view.View findNextFocusFromRect(android.view.ViewGroup, android.graphics.Rect, int);
+    method public android.view.View findNextKeyboardNavigationCluster(android.view.ViewGroup, android.view.View, int);
     method public static android.view.FocusFinder getInstance();
   }
 
@@ -43177,6 +43178,7 @@ package android.view {
     method public void addChildrenForAccessibility(java.util.ArrayList<android.view.View>);
     method public void addFocusables(java.util.ArrayList<android.view.View>, int);
     method public void addFocusables(java.util.ArrayList<android.view.View>, int, int);
+    method public void addKeyboardNavigationClusters(java.util.Collection<android.view.View>, int);
     method public void addOnAttachStateChangeListener(android.view.View.OnAttachStateChangeListener);
     method public void addOnLayoutChangeListener(android.view.View.OnLayoutChangeListener);
     method public void addTouchables(java.util.ArrayList<android.view.View>);
@@ -43465,6 +43467,7 @@ package android.view {
     method public boolean isVerticalFadingEdgeEnabled();
     method public boolean isVerticalScrollBarEnabled();
     method public void jumpDrawablesToCurrentState();
+    method public android.view.View keyboardNavigationClusterSearch(int);
     method public void layout(int, int, int, int);
     method public final void measure(int, int);
     method protected static int[] mergeDrawableStates(int[], int[]);
@@ -44116,6 +44119,7 @@ package android.view {
     method protected deprecated boolean isChildrenDrawnWithCacheEnabled();
     method public boolean isMotionEventSplittingEnabled();
     method public boolean isTransitionGroup();
+    method public android.view.View keyboardNavigationClusterSearch(android.view.View, int);
     method public final void layout(int, int, int, int);
     method protected void measureChild(android.view.View, int, int);
     method protected void measureChildWithMargins(android.view.View, int, int, int, int);
@@ -44278,6 +44282,7 @@ package android.view {
     method public abstract boolean isLayoutRequested();
     method public abstract boolean isTextAlignmentResolved();
     method public abstract boolean isTextDirectionResolved();
+    method public abstract android.view.View keyboardNavigationClusterSearch(android.view.View, int);
     method public abstract void notifySubtreeAccessibilityStateChanged(android.view.View, android.view.View, int);
     method public abstract boolean onNestedFling(android.view.View, float, float, boolean);
     method public abstract boolean onNestedPreFling(android.view.View, float, float);
diff --git a/core/java/android/view/FocusFinder.java b/core/java/android/view/FocusFinder.java
index d563f5110600..3f3d5190fac7 100644
--- a/core/java/android/view/FocusFinder.java
+++ b/core/java/android/view/FocusFinder.java
@@ -16,6 +16,8 @@
 
 package android.view;
 
+import android.annotation.NonNull;
+import android.annotation.Nullable;
 import android.graphics.Rect;
 import android.util.ArrayMap;
 import android.util.SparseArray;
@@ -24,6 +26,7 @@ import android.util.SparseBooleanArray;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Comparator;
+import java.util.List;
 
 /**
  * The algorithm used for finding the next focusable view in a given direction
@@ -102,6 +105,30 @@ public class FocusFinder {
         return next;
     }
 
+    /**
+     * Find the root of the next keyboard navigation cluster after the current one.
+     * @param root Thew view tree to look inside. Cannot be null
+     * @param currentCluster The starting point of the search. Null means the default cluster
+     * @param direction Direction to look
+     * @return The next cluster, or null if none exists
+     */
+    public View findNextKeyboardNavigationCluster(
+            @NonNull ViewGroup root, @Nullable View currentCluster, int direction) {
+        View next = null;
+
+        final ArrayList<View> clusters = mTempList;
+        try {
+            clusters.clear();
+            root.addKeyboardNavigationClusters(clusters, direction);
+            if (!clusters.isEmpty()) {
+                next = findNextKeyboardNavigationCluster(root, currentCluster, clusters, direction);
+            }
+        } finally {
+            clusters.clear();
+        }
+        return next;
+    }
+
     private View findNextUserSpecifiedFocus(ViewGroup root, View focused, int direction) {
         // check for user specified next focus
         View userSetNextFocus = focused.findUserSetNextFocus(root, direction);
@@ -170,6 +197,24 @@ public class FocusFinder {
         }
     }
 
+    private View findNextKeyboardNavigationCluster(ViewGroup root, View currentCluster,
+            List<View> clusters, int direction) {
+        final int count = clusters.size();
+
+        switch (direction) {
+            case View.FOCUS_FORWARD:
+            case View.FOCUS_DOWN:
+            case View.FOCUS_RIGHT:
+                return getNextKeyboardNavigationCluster(root, currentCluster, clusters, count);
+            case View.FOCUS_BACKWARD:
+            case View.FOCUS_UP:
+            case View.FOCUS_LEFT:
+                return getPreviousKeyboardNavigationCluster(root, currentCluster, clusters, count);
+            default:
+                throw new IllegalArgumentException("Unknown direction: " + direction);
+        }
+    }
+
     private View findNextFocusInRelativeDirection(ArrayList<View> focusables, ViewGroup root,
             View focused, Rect focusedRect, int direction) {
         try {
@@ -270,6 +315,45 @@ public class FocusFinder {
         return null;
     }
 
+    private static View getNextKeyboardNavigationCluster(ViewGroup root, View currentCluster,
+            List<View> clusters, int count) {
+        if (currentCluster == null) {
+            // The current cluster is the default one.
+            // The next cluster after the default one is the first one.
+            // Note that the caller guarantees that 'clusters' is not empty.
+            return clusters.get(0);
+        }
+
+        final int position = clusters.lastIndexOf(currentCluster);
+        if (position >= 0 && position + 1 < count) {
+            // Return the next non-default cluster if we can find it.
+            return clusters.get(position + 1);
+        }
+
+        // The current cluster is the last one. The next one is the default one, i.e. the root.
+        return root;
+    }
+
+    private static View getPreviousKeyboardNavigationCluster(ViewGroup root, View currentCluster,
+            List<View> clusters, int count) {
+        if (currentCluster == null) {
+            // The current cluster is the default one.
+            // The previous cluster before the default one is the last one.
+            // Note that the caller guarantees that 'clusters' is not empty.
+            return clusters.get(count - 1);
+        }
+
+        final int position = clusters.indexOf(currentCluster);
+        if (position > 0) {
+            // Return the previous non-default cluster if we can find it.
+            return clusters.get(position - 1);
+        }
+
+        // The current cluster is the first one. The previous one is the default one, i.e. the
+        // root.
+        return root;
+    }
+
     /**
      * Is rect1 a better candidate than rect2 for a focus search in a particular
      * direction from a source rect?  This is the core routine that determines
diff --git a/core/java/android/view/View.java b/core/java/android/view/View.java
index 9e4bb4ca38e7..47a0b24c31b0 100644
--- a/core/java/android/view/View.java
+++ b/core/java/android/view/View.java
@@ -128,6 +128,7 @@ import java.lang.reflect.Method;
 import java.lang.reflect.Modifier;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.List;
@@ -9086,6 +9087,24 @@ public class View implements Drawable.Callback, KeyEvent.Callback,
     }
 
     /**
+     * Find the nearest keyboard navigation cluster in the specified direction.
+     * This does not actually give focus to that cluster.
+     *
+     * @param direction Direction to look
+     *
+     * @return The nearest keyboard navigation cluster in the specified direction, or null if none
+     *         can be found
+     */
+    public View keyboardNavigationClusterSearch(int direction) {
+        if (mParent != null) {
+            final View currentCluster = isKeyboardNavigationCluster() ? this : null;
+            return mParent.keyboardNavigationClusterSearch(currentCluster, direction);
+        } else {
+            return null;
+        }
+    }
+
+    /**
      * This method is the last chance for the focused view and its ancestors to
      * respond to an arrow key. This is called when the focused view did not
      * consume the key internally, nor could the view system find a new view in
@@ -9208,6 +9227,20 @@ public class View implements Drawable.Callback, KeyEvent.Callback,
     }
 
     /**
+     * Adds any keyboard navigation cluster roots that are descendants of this view (possibly
+     * including this view if it is a cluster root itself) to views.
+     *
+     * @param views Cluster roots found so far
+     * @param direction Direction to look
+     */
+    public void addKeyboardNavigationClusters(@NonNull Collection<View> views, int direction) {
+        if (!isKeyboardNavigationCluster()) {
+            return;
+        }
+        views.add(this);
+    }
+
+    /**
      * Finds the Views that contain given text. The containment is case insensitive.
      * The search is performed by either the text that the View renders or the content
      * description that describes the view for accessibility purposes and the view does
diff --git a/core/java/android/view/ViewGroup.java b/core/java/android/view/ViewGroup.java
index ff797d197535..c83298b873a2 100644
--- a/core/java/android/view/ViewGroup.java
+++ b/core/java/android/view/ViewGroup.java
@@ -59,6 +59,7 @@ import com.android.internal.R;
 import com.android.internal.util.Predicate;
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.HashSet;
 import java.util.List;
@@ -880,6 +881,23 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
     }
 
     @Override
+    public View keyboardNavigationClusterSearch(View currentCluster, int direction) {
+        if (isKeyboardNavigationCluster()) {
+            currentCluster = this;
+        }
+        if (isRootNamespace()) {
+            // root namespace means we should consider ourselves the top of the
+            // tree for cluster searching; otherwise we could be focus searching
+            // into other tabs.  see LocalActivityManager and TabHost for more info
+            return FocusFinder.getInstance().findNextKeyboardNavigationCluster(
+                    this, currentCluster, direction);
+        } else if (mParent != null) {
+            return mParent.keyboardNavigationClusterSearch(currentCluster, direction);
+        }
+        return null;
+    }
+
+    @Override
     public boolean requestChildRectangleOnScreen(View child, Rect rectangle, boolean immediate) {
         return false;
     }
@@ -1118,6 +1136,32 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
         }
     }
 
+    @Override
+    public void addKeyboardNavigationClusters(Collection<View> views, int direction) {
+        final int focusableCount = views.size();
+
+        super.addKeyboardNavigationClusters(views, direction);
+
+        if (focusableCount != views.size()) {
+            // No need to look for clusters inside a cluster.
+            return;
+        }
+
+        if (getDescendantFocusability() == FOCUS_BLOCK_DESCENDANTS) {
+            return;
+        }
+
+        final int count = mChildrenCount;
+        final View[] children = mChildren;
+
+        for (int i = 0; i < count; i++) {
+            final View child = children[i];
+            if ((child.mViewFlags & VISIBILITY_MASK) == VISIBLE) {
+                child.addKeyboardNavigationClusters(views, direction);
+            }
+        }
+    }
+
     /**
      * Set whether this ViewGroup should ignore focus requests for itself and its children.
      * If this option is enabled and the ViewGroup or a descendant currently has focus, focus
diff --git a/core/java/android/view/ViewParent.java b/core/java/android/view/ViewParent.java
index 849c8b93fd6b..79b05cdb6e50 100644
--- a/core/java/android/view/ViewParent.java
+++ b/core/java/android/view/ViewParent.java
@@ -147,6 +147,19 @@ public interface ViewParent {
     public View focusSearch(View v, int direction);
 
     /**
+     * Find the nearest keyboard navigation cluster in the specified direction.
+     * This does not actually give focus to that cluster.
+     *
+     * @param currentCluster The starting point of the search. Null means the current cluster is not
+     *                       found yet
+     * @param direction Direction to look
+     *
+     * @return The nearest keyboard navigation cluster in the specified direction, or null if none
+     *         can be found
+     */
+    View keyboardNavigationClusterSearch(View currentCluster, int direction);
+
+    /**
      * Change the z order of the child so it's on top of all other children.
      * This ordering change may affect layout, if this container
      * uses an order-dependent layout scheme (e.g., LinearLayout). Prior
diff --git a/core/java/android/view/ViewRootImpl.java b/core/java/android/view/ViewRootImpl.java
index e030e767732e..2cebeedda762 100644
--- a/core/java/android/view/ViewRootImpl.java
+++ b/core/java/android/view/ViewRootImpl.java
@@ -4324,6 +4324,87 @@ public final class ViewRootImpl implements ViewParent,
             super.onDeliverToNext(q);
         }
 
+        private boolean performFocusNavigation(KeyEvent event) {
+            int direction = 0;
+            switch (event.getKeyCode()) {
+                case KeyEvent.KEYCODE_DPAD_LEFT:
+                    if (event.hasNoModifiers()) {
+                        direction = View.FOCUS_LEFT;
+                    }
+                    break;
+                case KeyEvent.KEYCODE_DPAD_RIGHT:
+                    if (event.hasNoModifiers()) {
+                        direction = View.FOCUS_RIGHT;
+                    }
+                    break;
+                case KeyEvent.KEYCODE_DPAD_UP:
+                    if (event.hasNoModifiers()) {
+                        direction = View.FOCUS_UP;
+                    }
+                    break;
+                case KeyEvent.KEYCODE_DPAD_DOWN:
+                    if (event.hasNoModifiers()) {
+                        direction = View.FOCUS_DOWN;
+                    }
+                    break;
+                case KeyEvent.KEYCODE_TAB:
+                    if (event.hasNoModifiers()) {
+                        direction = View.FOCUS_FORWARD;
+                    } else if (event.hasModifiers(KeyEvent.META_SHIFT_ON)) {
+                        direction = View.FOCUS_BACKWARD;
+                    }
+                    break;
+            }
+            if (direction != 0) {
+                View focused = mView.findFocus();
+                if (focused != null) {
+                    View v = focused.focusSearch(direction);
+                    if (v != null && v != focused) {
+                        // do the math the get the interesting rect
+                        // of previous focused into the coord system of
+                        // newly focused view
+                        focused.getFocusedRect(mTempRect);
+                        if (mView instanceof ViewGroup) {
+                            ((ViewGroup) mView).offsetDescendantRectToMyCoords(
+                                    focused, mTempRect);
+                            ((ViewGroup) mView).offsetRectIntoDescendantCoords(
+                                    v, mTempRect);
+                        }
+                        if (v.requestFocus(direction, mTempRect)) {
+                            playSoundEffect(SoundEffectConstants
+                                    .getContantForFocusDirection(direction));
+                            return true;
+                        }
+                    }
+
+                    // Give the focused view a last chance to handle the dpad key.
+                    if (mView.dispatchUnhandledMove(focused, direction)) {
+                        return true;
+                    }
+                } else {
+                    // find the best view to give focus to in this non-touch-mode with no-focus
+                    View v = focusSearch(null, direction);
+                    if (v != null && v.requestFocus(direction)) {
+                        return true;
+                    }
+                }
+            }
+            return false;
+        }
+
+        private boolean performClusterNavigation(int direction) {
+            final View focused = mView.findFocus();
+            final View cluster = focused != null
+                    ? focused.keyboardNavigationClusterSearch(direction)
+                    : keyboardNavigationClusterSearch(null, direction);
+
+            if (cluster != null && cluster.requestFocus()) {
+                return true;
+            }
+
+            return false;
+        }
+
         private int processKeyEvent(QueuedInputEvent q) {
             final KeyEvent event = (KeyEvent)q.mEvent;
 
@@ -4336,11 +4417,26 @@ public final class ViewRootImpl implements ViewParent,
                 return FINISH_NOT_HANDLED;
             }
 
+            int clusterNavigationDirection = 0;
+
+            if (event.getAction() == KeyEvent.ACTION_DOWN && event.isCtrlPressed()) {
+                final int character =
+                        event.getUnicodeChar(event.getMetaState() & ~KeyEvent.META_CTRL_MASK);
+                if (character == '+') {
+                    clusterNavigationDirection = View.FOCUS_FORWARD;
+                }
+
+                if (character == '_') {
+                    clusterNavigationDirection = View.FOCUS_BACKWARD;
+                }
+            }
+
             // If the Control modifier is held, try to interpret the key as a shortcut.
             if (event.getAction() == KeyEvent.ACTION_DOWN
                     && event.isCtrlPressed()
                     && event.getRepeatCount() == 0
-                    && !KeyEvent.isModifierKey(event.getKeyCode())) {
+                    && !KeyEvent.isModifierKey(event.getKeyCode())
+                    && clusterNavigationDirection == 0) {
                 if (mView.dispatchKeyShortcutEvent(event)) {
                     return FINISH_HANDLED;
                 }
@@ -4359,68 +4455,13 @@ public final class ViewRootImpl implements ViewParent,
 
             // Handle automatic focus changes.
             if (event.getAction() == KeyEvent.ACTION_DOWN) {
-                int direction = 0;
-                switch (event.getKeyCode()) {
-                    case KeyEvent.KEYCODE_DPAD_LEFT:
-                        if (event.hasNoModifiers()) {
-                            direction = View.FOCUS_LEFT;
-                        }
-                        break;
-                    case KeyEvent.KEYCODE_DPAD_RIGHT:
-                        if (event.hasNoModifiers()) {
-                            direction = View.FOCUS_RIGHT;
-                        }
-                        break;
-                    case KeyEvent.KEYCODE_DPAD_UP:
-                        if (event.hasNoModifiers()) {
-                            direction = View.FOCUS_UP;
-                        }
-                        break;
-                    case KeyEvent.KEYCODE_DPAD_DOWN:
-                        if (event.hasNoModifiers()) {
-                            direction = View.FOCUS_DOWN;
-                        }
-                        break;
-                    case KeyEvent.KEYCODE_TAB:
-                        if (event.hasNoModifiers()) {
-                            direction = View.FOCUS_FORWARD;
-                        } else if (event.hasModifiers(KeyEvent.META_SHIFT_ON)) {
-                            direction = View.FOCUS_BACKWARD;
-                        }
-                        break;
-                }
-                if (direction != 0) {
-                    View focused = mView.findFocus();
-                    if (focused != null) {
-                        View v = focused.focusSearch(direction);
-                        if (v != null && v != focused) {
-                            // do the math the get the interesting rect
-                            // of previous focused into the coord system of
-                            // newly focused view
-                            focused.getFocusedRect(mTempRect);
-                            if (mView instanceof ViewGroup) {
-                                ((ViewGroup) mView).offsetDescendantRectToMyCoords(
-                                        focused, mTempRect);
-                                ((ViewGroup) mView).offsetRectIntoDescendantCoords(
-                                        v, mTempRect);
-                            }
-                            if (v.requestFocus(direction, mTempRect)) {
-                                playSoundEffect(SoundEffectConstants
-                                        .getContantForFocusDirection(direction));
-                                return FINISH_HANDLED;
-                            }
-                        }
-
-                        // Give the focused view a last chance to handle the dpad key.
-                        if (mView.dispatchUnhandledMove(focused, direction)) {
-                            return FINISH_HANDLED;
-                        }
-                    } else {
-                        // find the best view to give focus to in this non-touch-mode with no-focus
-                        View v = focusSearch(null, direction);
-                        if (v != null && v.requestFocus(direction)) {
-                            return FINISH_HANDLED;
-                        }
+                if (clusterNavigationDirection != 0) {
+                    if (performClusterNavigation(clusterNavigationDirection)) {
+                        return FINISH_HANDLED;
+                    }
+                } else {
+                    if (performFocusNavigation(event)) {
+                        return FINISH_HANDLED;
                     }
                 }
             }
@@ -5842,6 +5883,19 @@ public final class ViewRootImpl implements ViewParent,
         return FocusFinder.getInstance().findNextFocus((ViewGroup) mView, focused, direction);
     }
 
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public View keyboardNavigationClusterSearch(View currentCluster, int direction) {
+        checkThread();
+        if (!(mView instanceof ViewGroup)) {
+            return null;
+        }
+        return FocusFinder.getInstance().findNextKeyboardNavigationCluster(
+                (ViewGroup) mView, currentCluster, direction);
+    }
+
     public void debug() {
         mView.debug();
     }