[key event focus handling] Cleanup/Refactor/Feature

1) Focus navigation handling is refactored to Focus utility class.
New 2 step dpad navigation algorithm is inside Focus class
2) Introduced a map (or matrix) that indicates where sparse icons are located inside a grid.
This enables getting rid of the icon sorting logic which was costly.
3) Unified all the dpad handling logic inside the handleXXKeyEvent methods
4) DOWN/UP key will allow navigation between workspace icons and the hotseat
5) Folder icons allow DOWN/UP to navigate to the title

b/19381790

Change-Id: Id45b3f215ef7c1ca5f99b08e3d721e219298627a

3 files changed, 732 insertions, 532 deletions

diff --git a/src/com/android/launcher3/CellLayout.java b/src/com/android/launcher3/CellLayout.java
index e6865b2e6..72e28918f 100644
--- a/src/com/android/launcher3/CellLayout.java
+++ b/src/com/android/launcher3/CellLayout.java
@@ -578,11 +578,11 @@ public class CellLayout extends ViewGroup {
         mInterceptTouchListener = listener;
     }
 
-    int getCountX() {
+    public int getCountX() {
         return mCountX;
     }
 
-    int getCountY() {
+    public int getCountY() {
         return mCountY;
     }
 
diff --git a/src/com/android/launcher3/FocusHelper.java b/src/com/android/launcher3/FocusHelper.java
index e60704718..c02d73cb6 100644
--- a/src/com/android/launcher3/FocusHelper.java
+++ b/src/com/android/launcher3/FocusHelper.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011 The Android Open Source Project
+ * Copyright (C) 2015 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -17,20 +17,20 @@
 package com.android.launcher3;
 
 import android.content.res.Configuration;
+import android.util.Log;
 import android.view.KeyEvent;
 import android.view.SoundEffectConstants;
 import android.view.View;
 import android.view.ViewGroup;
 import android.widget.ScrollView;
 
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
+import com.android.launcher3.util.FocusLogic;
 
 /**
  * A keyboard listener we set on all the workspace icons.
  */
 class IconKeyEventListener implements View.OnKeyListener {
+    @Override
     public boolean onKey(View v, int keyCode, KeyEvent event) {
         return FocusHelper.handleIconKeyEvent(v, keyCode, event);
     }
@@ -40,6 +40,7 @@ class IconKeyEventListener implements View.OnKeyListener {
  * A keyboard listener we set on all the workspace icons.
  */
 class FolderKeyEventListener implements View.OnKeyListener {
+    @Override
     public boolean onKey(View v, int keyCode, KeyEvent event) {
         return FocusHelper.handleFolderKeyEvent(v, keyCode, event);
     }
@@ -49,30 +50,35 @@ class FolderKeyEventListener implements View.OnKeyListener {
  * A keyboard listener we set on all the hotseat buttons.
  */
 class HotseatIconKeyEventListener implements View.OnKeyListener {
+    @Override
     public boolean onKey(View v, int keyCode, KeyEvent event) {
-        final Configuration configuration = v.getResources().getConfiguration();
-        return FocusHelper.handleHotseatButtonKeyEvent(v, keyCode, event, configuration.orientation);
+        return FocusHelper.handleHotseatButtonKeyEvent(v, keyCode, event);
     }
 }
 
 public class FocusHelper {
 
-    /**
-     * Returns the Viewgroup containing page contents for the page at the index specified.
-     */
-    private static ViewGroup getAppsCustomizePage(ViewGroup container, int index) {
-        ViewGroup page = (ViewGroup) ((PagedView) container).getPageAt(index);
-        if (page instanceof CellLayout) {
-            // There are two layers, a PagedViewCellLayout and PagedViewCellLayoutChildren
-            page = ((CellLayout) page).getShortcutsAndWidgets();
-        }
-        return page;
-    }
+    private static final String TAG = "FocusHelper";
+    private static final boolean DEBUG = false;
+
+    //
+    // Key code handling methods.
+    //
 
     /**
-     * Handles key events in a PageViewCellLayout containing PagedViewIcons.
+     * Handles key events in the all apps screen.
      */
     static boolean handleAppsCustomizeKeyEvent(View v, int keyCode, KeyEvent e) {
+        boolean consume = FocusLogic.shouldConsume(keyCode);
+        if (e.getAction() == KeyEvent.ACTION_UP) {
+            return consume;
+        }
+        if (DEBUG) {
+            Log.v(TAG, String.format("Handle ALL APPS keyevent=[%s].",
+                    KeyEvent.keyCodeToString(keyCode)));
+        }
+
+        // Initialize variables.
         ViewGroup parentLayout;
         ViewGroup itemContainer;
         int countX;
@@ -82,341 +88,159 @@ public class FocusHelper {
             parentLayout = (ViewGroup) itemContainer.getParent();
             countX = ((CellLayout) parentLayout).getCountX();
             countY = ((CellLayout) parentLayout).getCountY();
-        } else {
+        } else if (v.getParent() instanceof ViewGroup) {
             itemContainer = parentLayout = (ViewGroup) v.getParent();
             countX = ((PagedViewGridLayout) parentLayout).getCellCountX();
             countY = ((PagedViewGridLayout) parentLayout).getCellCountY();
+        } else {
+            throw new IllegalStateException(
+                    "Parent of the focused item inside all apps screen is not a supported type.");
         }
-
-        // Note we have an extra parent because of the
-        // PagedViewCellLayout/PagedViewCellLayoutChildren relationship
-        final PagedView container = (PagedView) parentLayout.getParent();
         final int iconIndex = itemContainer.indexOfChild(v);
-        final int itemCount = itemContainer.getChildCount();
-        final int pageIndex = ((PagedView) container).indexToPage(container.indexOfChild(parentLayout));
+        final PagedView container = (PagedView) parentLayout.getParent();
+        final int pageIndex = container.indexToPage(container.indexOfChild(parentLayout));
         final int pageCount = container.getChildCount();
-
-        final int x = iconIndex % countX;
-        final int y = iconIndex / countX;
-
-        final int action = e.getAction();
-        final boolean handleKeyEvent = (action != KeyEvent.ACTION_UP);
         ViewGroup newParent = null;
-        // Side pages do not always load synchronously, so check before focusing child siblings
-        // willy-nilly
         View child = null;
-        boolean wasHandled = false;
-        switch (keyCode) {
-            case KeyEvent.KEYCODE_DPAD_LEFT:
-                if (handleKeyEvent) {
-                    // Select the previous icon or the last icon on the previous page
-                    if (iconIndex > 0) {
-                        itemContainer.getChildAt(iconIndex - 1).requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_LEFT);
-                    } else {
-                        if (pageIndex > 0) {
-                            newParent = getAppsCustomizePage(container, pageIndex - 1);
-                            if (newParent != null) {
-                                container.snapToPage(pageIndex - 1);
-                                child = newParent.getChildAt(newParent.getChildCount() - 1);
-                                if (child != null) {
-                                    child.requestFocus();
-                                    v.playSoundEffect(SoundEffectConstants.NAVIGATION_LEFT);
-                                }
-                            }
-                        }
-                    }
+        int[][] matrix = FocusLogic.createFullMatrix(countX, countY, true);
+
+        // Process focus.
+        int newIconIndex = FocusLogic.handleKeyEvent(keyCode, countX, countY, matrix,
+                iconIndex, pageIndex, pageCount);
+        if (newIconIndex == FocusLogic.NOOP) {
+            return consume;
+        }
+        switch (newIconIndex) {
+            case FocusLogic.PREVIOUS_PAGE_FIRST_ITEM:
+                newParent = getAppsCustomizePage(container, pageIndex - 1);
+                if (newParent != null) {
+                    container.snapToPage(pageIndex - 1);
+                    child = newParent.getChildAt(0);
                 }
-                wasHandled = true;
-                break;
-            case KeyEvent.KEYCODE_DPAD_RIGHT:
-                if (handleKeyEvent) {
-                    // Select the next icon or the first icon on the next page
-                    if (iconIndex < (itemCount - 1)) {
-                        itemContainer.getChildAt(iconIndex + 1).requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_RIGHT);
-                    } else {
-                        if (pageIndex < (pageCount - 1)) {
-                            newParent = getAppsCustomizePage(container, pageIndex + 1);
-                            if (newParent != null) {
-                                container.snapToPage(pageIndex + 1);
-                                child = newParent.getChildAt(0);
-                                if (child != null) {
-                                    child.requestFocus();
-                                    v.playSoundEffect(SoundEffectConstants.NAVIGATION_RIGHT);
-                                }
-                            }
-                        }
-                    }
+            case FocusLogic.PREVIOUS_PAGE_LAST_ITEM:
+                newParent = getAppsCustomizePage(container, pageIndex - 1);
+                if (newParent != null) {
+                    container.snapToPage(pageIndex - 1);
+                    child = newParent.getChildAt(newParent.getChildCount() - 1);
                 }
-                wasHandled = true;
                 break;
-            case KeyEvent.KEYCODE_DPAD_UP:
-                if (handleKeyEvent) {
-                    // Select the closest icon in the previous row, otherwise select the tab bar
-                    if (y > 0) {
-                        int newiconIndex = ((y - 1) * countX) + x;
-                        itemContainer.getChildAt(newiconIndex).requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_UP);
-                    }
+            case FocusLogic.NEXT_PAGE_FIRST_ITEM:
+                newParent = getAppsCustomizePage(container, pageIndex + 1);
+                if (newParent != null) {
+                    container.snapToPage(pageIndex + 1);
+                    child = newParent.getChildAt(0);
                 }
-                wasHandled = true;
                 break;
-            case KeyEvent.KEYCODE_DPAD_DOWN:
-                if (handleKeyEvent) {
-                    // Select the closest icon in the next row, otherwise do nothing
-                    if (y < (countY - 1)) {
-                        int newiconIndex = Math.min(itemCount - 1, ((y + 1) * countX) + x);
-                        int newIconY = newiconIndex / countX;
-                        if (newIconY != y) {
-                            itemContainer.getChildAt(newiconIndex).requestFocus();
-                            v.playSoundEffect(SoundEffectConstants.NAVIGATION_DOWN);
-                        }
-                    }
-                }
-                wasHandled = true;
+            case FocusLogic.CURRENT_PAGE_FIRST_ITEM:
+                child = container.getChildAt(0);
                 break;
-            case KeyEvent.KEYCODE_PAGE_UP:
-                if (handleKeyEvent) {
-                    // Select the first icon on the previous page, or the first icon on this page
-                    // if there is no previous page
-                    if (pageIndex > 0) {
-                        newParent = getAppsCustomizePage(container, pageIndex - 1);
-                        if (newParent != null) {
-                            container.snapToPage(pageIndex - 1);
-                            child = newParent.getChildAt(0);
-                            if (child != null) {
-                                child.requestFocus();
-                                v.playSoundEffect(SoundEffectConstants.NAVIGATION_UP);
-                            }
-                        }
-                    } else {
-                        itemContainer.getChildAt(0).requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_UP);
-                    }
-                }
-                wasHandled = true;
-                break;
-            case KeyEvent.KEYCODE_PAGE_DOWN:
-                if (handleKeyEvent) {
-                    // Select the first icon on the next page, or the last icon on this page
-                    // if there is no next page
-                    if (pageIndex < (pageCount - 1)) {
-                        newParent = getAppsCustomizePage(container, pageIndex + 1);
-                        if (newParent != null) {
-                            container.snapToPage(pageIndex + 1);
-                            child = newParent.getChildAt(0);
-                            if (child != null) {
-                                child.requestFocus();
-                                v.playSoundEffect(SoundEffectConstants.NAVIGATION_DOWN);
-                            }
-                        }
-                    } else {
-                        itemContainer.getChildAt(itemCount - 1).requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_DOWN);
-                    }
-                }
-                wasHandled = true;
-                break;
-            case KeyEvent.KEYCODE_MOVE_HOME:
-                if (handleKeyEvent) {
-                    // Select the first icon on this page
-                    itemContainer.getChildAt(0).requestFocus();
-                    v.playSoundEffect(SoundEffectConstants.NAVIGATION_UP);
-                }
-                wasHandled = true;
+            case FocusLogic.CURRENT_PAGE_LAST_ITEM:
+                child = itemContainer.getChildAt(itemContainer.getChildCount() - 1);
                 break;
-            case KeyEvent.KEYCODE_MOVE_END:
-                if (handleKeyEvent) {
-                    // Select the last icon on this page
-                    itemContainer.getChildAt(itemCount - 1).requestFocus();
-                    v.playSoundEffect(SoundEffectConstants.NAVIGATION_DOWN);
-                }
-                wasHandled = true;
+            default: // Go to some item on the current page.
+                child = itemContainer.getChildAt(newIconIndex);
                 break;
-            default: break;
         }
-        return wasHandled;
+        if (child != null) {
+            child.requestFocus();
+            playSoundEffect(keyCode, v);
+        }
+        return consume;
     }
 
     /**
-     * Handles key events in the workspace hotseat (bottom of the screen).
+     * Handles key events in the workspace hot seat (bottom of the screen).
+     * <p>Currently we don't special case for the phone UI in different orientations, even though
+     * the hotseat is on the side in landscape mode. This is to ensure that accessibility
+     * consistency is maintained across rotations.
      */
-    static boolean handleHotseatButtonKeyEvent(View v, int keyCode, KeyEvent e, int orientation) {
-        ShortcutAndWidgetContainer parent = (ShortcutAndWidgetContainer) v.getParent();
-        final CellLayout layout = (CellLayout) parent.getParent();
+    static boolean handleHotseatButtonKeyEvent(View v, int keyCode, KeyEvent e) {
+        boolean consume = FocusLogic.shouldConsume(keyCode);
+        if (e.getAction() == KeyEvent.ACTION_UP || !consume) {
+            return consume;
+        }
+        int orientation = v.getResources().getConfiguration().orientation;
 
-        // NOTE: currently we don't special case for the phone UI in different
-        // orientations, even though the hotseat is on the side in landscape mode. This
-        // is to ensure that accessibility consistency is maintained across rotations.
-        final int action = e.getAction();
-        final boolean handleKeyEvent = (action != KeyEvent.ACTION_UP);
-        boolean wasHandled = false;
-        switch (keyCode) {
-            case KeyEvent.KEYCODE_DPAD_LEFT:
-                if (handleKeyEvent) {
-                    ArrayList<View> views = getCellLayoutChildrenSortedSpatially(layout, parent);
-                    int myIndex = views.indexOf(v);
-                    // Select the previous button, otherwise do nothing
-                    if (myIndex > 0) {
-                        views.get(myIndex - 1).requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_LEFT);
-                    }
-                }
-                wasHandled = true;
-                break;
-            case KeyEvent.KEYCODE_DPAD_RIGHT:
-                if (handleKeyEvent) {
-                    ArrayList<View> views = getCellLayoutChildrenSortedSpatially(layout, parent);
-                    int myIndex = views.indexOf(v);
-                    // Select the next button, otherwise do nothing
-                    if (myIndex < views.size() - 1) {
-                        views.get(myIndex + 1).requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_RIGHT);
-                    }
-                }
-                wasHandled = true;
-                break;
-            case KeyEvent.KEYCODE_DPAD_UP:
-                if (handleKeyEvent) {
-                    final Workspace workspace = (Workspace)
-                            v.getRootView().findViewById(R.id.workspace);
-                    if (workspace != null) {
-                        int pageIndex = workspace.getCurrentPage();
-                        CellLayout topLayout = (CellLayout) workspace.getChildAt(pageIndex);
-                        ShortcutAndWidgetContainer children = topLayout.getShortcutsAndWidgets();
-                        final View newIcon = getIconInDirection(layout, children, -1, 1);
-                        // Select the first bubble text view in the current page of the workspace
-                        if (newIcon != null) {
-                            newIcon.requestFocus();
-                            v.playSoundEffect(SoundEffectConstants.NAVIGATION_UP);
-                        } else {
-                            workspace.requestFocus();
-                        }
-                    }
-                }
-                wasHandled = true;
-                break;
-            case KeyEvent.KEYCODE_DPAD_DOWN:
-                // Do nothing
-                wasHandled = true;
-                break;
-            default: break;
+        if (DEBUG) {
+            Log.v(TAG, String.format(
+                    "Handle HOTSEAT BUTTONS keyevent=[%s] on hotseat buttons, orientation=%d",
+                    KeyEvent.keyCodeToString(keyCode), orientation));
         }
-        return wasHandled;
-    }
 
-    /**
-     * Private helper method to get the CellLayoutChildren given a CellLayout index.
-     */
-    private static ShortcutAndWidgetContainer getCellLayoutChildrenForIndex(
-            ViewGroup container, int i) {
-        CellLayout parent = (CellLayout) container.getChildAt(i);
-        return parent.getShortcutsAndWidgets();
-    }
+        // Initialize the variables.
+        final ShortcutAndWidgetContainer hotseatParent = (ShortcutAndWidgetContainer) v.getParent();
+        final CellLayout hotseatLayout = (CellLayout) hotseatParent.getParent();
+        Workspace workspace = (Workspace) v.getRootView().findViewById(R.id.workspace);
+        int pageIndex = workspace.getCurrentPage();
+        int pageCount = workspace.getChildCount();
+        int countX, countY;
+        int iconIndex = findIndexOfView(hotseatParent, v);
+
+        final CellLayout iconLayout = (CellLayout) workspace.getChildAt(pageIndex);
+        final ViewGroup iconParent = iconLayout.getShortcutsAndWidgets();
+
+        ViewGroup parent = null;
+        int[][] matrix;
+
+        if (keyCode == KeyEvent.KEYCODE_DPAD_UP &&
+                orientation == Configuration.ORIENTATION_PORTRAIT) {
+            matrix = FocusLogic.createSparseMatrix(iconLayout, hotseatLayout, orientation);
+            // TODO: hotseat indexing should be symmetric.
+            iconIndex += iconParent.getChildCount();
+            countX = iconLayout.getCountX();
+            countY = iconLayout.getCountY() + hotseatLayout.getCountY();
+            parent = iconParent;
+        } else if (keyCode == KeyEvent.KEYCODE_DPAD_LEFT &&
+                orientation == Configuration.ORIENTATION_LANDSCAPE) {
+            matrix = FocusLogic.createSparseMatrix(iconLayout, hotseatLayout, orientation);
+            // TODO: hotseat indexing should be symmetric.
+            iconIndex += iconParent.getChildCount();
+            countX = iconLayout.getCountX() + hotseatLayout.getCountX();
+            countY = iconLayout.getCountY();
+            parent = iconParent;
+        } else {
+            // For other KEYCODE_DPAD_LEFT and KEYCODE_DPAD_RIGHT navigation, do not use the
+            // matrix extended with hotseat.
+            matrix = FocusLogic.createSparseMatrix(hotseatLayout);
+            parent = hotseatParent;
+            countX = hotseatLayout.getCountX();
+            countY = hotseatLayout.getCountY();
 
-    /**
-     * Private helper method to sort all the CellLayout children in order of their (x,y) spatially
-     * from top left to bottom right.
-     */
-    private static ArrayList<View> getCellLayoutChildrenSortedSpatially(CellLayout layout,
-            ViewGroup parent) {
-        // First we order each the CellLayout children by their x,y coordinates
-        final int cellCountX = layout.getCountX();
-        final int count = parent.getChildCount();
-        ArrayList<View> views = new ArrayList<View>();
-        for (int j = 0; j < count; ++j) {
-            views.add(parent.getChildAt(j));
         }
-        Collections.sort(views, new Comparator<View>() {
-            @Override
-            public int compare(View lhs, View rhs) {
-                CellLayout.LayoutParams llp = (CellLayout.LayoutParams) lhs.getLayoutParams();
-                CellLayout.LayoutParams rlp = (CellLayout.LayoutParams) rhs.getLayoutParams();
-                int lvIndex = (llp.cellY * cellCountX) + llp.cellX;
-                int rvIndex = (rlp.cellY * cellCountX) + rlp.cellX;
-                return lvIndex - rvIndex;
-            }
-        });
-        return views;
-    }
-    /**
-     * Private helper method to find the index of the next BubbleTextView or FolderIcon in the 
-     * direction delta.
-     * 
-     * @param delta either -1 or 1 depending on the direction we want to search
-     */
-    private static View findIndexOfIcon(ArrayList<View> views, int i, int delta) {
-        // Then we find the next BubbleTextView offset by delta from i
-        final int count = views.size();
-        int newI = i + delta;
-        while (0 <= newI && newI < count) {
-            View newV = views.get(newI);
-            if (newV instanceof BubbleTextView || newV instanceof FolderIcon) {
-                return newV;
-            }
-            newI += delta;
+
+        // Process the focus.
+        int newIconIndex = FocusLogic.handleKeyEvent(keyCode, countX, countY, matrix,
+                iconIndex, pageIndex, pageCount);
+
+        if (iconParent.getChildCount() <= newIconIndex &&
+                newIconIndex < iconParent.getChildCount() + hotseatParent.getChildCount()) {
+            newIconIndex -= iconParent.getChildCount();
         }
-        return null;
-    }
-    private static View getIconInDirection(CellLayout layout, ViewGroup parent, int i,
-            int delta) {
-        final ArrayList<View> views = getCellLayoutChildrenSortedSpatially(layout, parent);
-        return findIndexOfIcon(views, i, delta);
-    }
-    private static View getIconInDirection(CellLayout layout, ViewGroup parent, View v,
-            int delta) {
-        final ArrayList<View> views = getCellLayoutChildrenSortedSpatially(layout, parent);
-        return findIndexOfIcon(views, views.indexOf(v), delta);
-    }
-    /**
-     * Private helper method to find the next closest BubbleTextView or FolderIcon in the direction 
-     * delta on the next line.
-     * 
-     * @param delta either -1 or 1 depending on the line and direction we want to search
-     */
-    private static View getClosestIconOnLine(CellLayout layout, ViewGroup parent, View v,
-            int lineDelta) {
-        final ArrayList<View> views = getCellLayoutChildrenSortedSpatially(layout, parent);
-        final CellLayout.LayoutParams lp = (CellLayout.LayoutParams) v.getLayoutParams();
-        final int cellCountY = layout.getCountY();
-        final int row = lp.cellY;
-        final int newRow = row + lineDelta;
-        if (0 <= newRow && newRow < cellCountY) {
-            float closestDistance = Float.MAX_VALUE;
-            int closestIndex = -1;
-            int index = views.indexOf(v);
-            int endIndex = (lineDelta < 0) ? -1 : views.size();
-            while (index != endIndex) {
-                View newV = views.get(index);
-                CellLayout.LayoutParams tmpLp = (CellLayout.LayoutParams) newV.getLayoutParams();
-                boolean satisfiesRow = (lineDelta < 0) ? (tmpLp.cellY < row) : (tmpLp.cellY > row);
-                if (satisfiesRow &&
-                        (newV instanceof BubbleTextView || newV instanceof FolderIcon)) {
-                    float tmpDistance = (float) Math.sqrt(Math.pow(tmpLp.cellX - lp.cellX, 2) +
-                            Math.pow(tmpLp.cellY - lp.cellY, 2));
-                    if (tmpDistance < closestDistance) {
-                        closestIndex = index;
-                        closestDistance = tmpDistance;
-                    }
-                }
-                if (index <= endIndex) {
-                    ++index;
-                } else {
-                    --index;
-                }
-            }
-            if (closestIndex > -1) {
-                return views.get(closestIndex);
+        if (parent != null) {
+            View newIcon = parent.getChildAt(newIconIndex);
+            if (newIcon != null) {
+                newIcon.requestFocus();
+                playSoundEffect(keyCode, v);
             }
         }
-        return null;
+        return consume;
     }
 
     /**
-     * Handles key events in a Workspace containing.
+     * Handles key events in a workspace containing icons.
      */
     static boolean handleIconKeyEvent(View v, int keyCode, KeyEvent e) {
+        boolean consume = FocusLogic.shouldConsume(keyCode);
+        if (e.getAction() == KeyEvent.ACTION_UP || !consume) {
+            return consume;
+        }
+        int orientation = v.getResources().getConfiguration().orientation;
+        if (DEBUG) {
+            Log.v(TAG, String.format("Handle WORKSPACE ICONS keyevent=[%s] orientation=%d",
+                    KeyEvent.keyCodeToString(keyCode), orientation));
+        }
+
+        // Initialize the variables.
         ShortcutAndWidgetContainer parent = (ShortcutAndWidgetContainer) v.getParent();
         final CellLayout layout = (CellLayout) parent.getParent();
         final Workspace workspace = (Workspace) layout.getParent();
@@ -425,249 +249,191 @@ public class FocusHelper {
         final ViewGroup hotseat = (ViewGroup) launcher.findViewById(R.id.hotseat);
         int pageIndex = workspace.indexOfChild(layout);
         int pageCount = workspace.getChildCount();
+        final int countX = layout.getCountX();
+        int countY = layout.getCountY();
+        final int iconIndex = findIndexOfView(parent, v);
 
-        final int action = e.getAction();
-        final boolean handleKeyEvent = (action != KeyEvent.ACTION_UP);
-        boolean wasHandled = false;
-        switch (keyCode) {
-            case KeyEvent.KEYCODE_DPAD_LEFT:
-                if (handleKeyEvent) {
-                    // Select the previous icon or the last icon on the previous page if possible
-                    View newIcon = getIconInDirection(layout, parent, v, -1);
-                    if (newIcon != null) {
-                        newIcon.requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_LEFT);
-                    } else {
-                        if (pageIndex > 0) {
-                            parent = getCellLayoutChildrenForIndex(workspace, pageIndex - 1);
-                            newIcon = getIconInDirection(layout, parent,
-                                    parent.getChildCount(), -1);
-                            if (newIcon != null) {
-                                newIcon.requestFocus();
-                            } else {
-                                // Snap to the previous page
-                                workspace.snapToPage(pageIndex - 1);
-                            }
-                            v.playSoundEffect(SoundEffectConstants.NAVIGATION_LEFT);
-                        }
-                    }
-                }
-                wasHandled = true;
-                break;
-            case KeyEvent.KEYCODE_DPAD_RIGHT:
-                if (handleKeyEvent) {
-                    // Select the next icon or the first icon on the next page if possible
-                    View newIcon = getIconInDirection(layout, parent, v, 1);
-                    if (newIcon != null) {
-                        newIcon.requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_RIGHT);
-                    } else {
-                        if (pageIndex < (pageCount - 1)) {
-                            parent = getCellLayoutChildrenForIndex(workspace, pageIndex + 1);
-                            newIcon = getIconInDirection(layout, parent, -1, 1);
-                            if (newIcon != null) {
-                                newIcon.requestFocus();
-                            } else {
-                                // Snap to the next page
-                                workspace.snapToPage(pageIndex + 1);
-                            }
-                            v.playSoundEffect(SoundEffectConstants.NAVIGATION_RIGHT);
-                        }
-                    }
-                }
-                wasHandled = true;
-                break;
-            case KeyEvent.KEYCODE_DPAD_UP:
-                if (handleKeyEvent) {
-                    // Select the closest icon in the previous line, otherwise select the tab bar
-                    View newIcon = getClosestIconOnLine(layout, parent, v, -1);
-                    if (newIcon != null) {
-                        newIcon.requestFocus();
-                        wasHandled = true;
-                    } else {
-                        tabs.requestFocus();
-                    }
-                    v.playSoundEffect(SoundEffectConstants.NAVIGATION_UP);
+        CellLayout hotseatLayout = (CellLayout) hotseat.getChildAt(0);
+        ShortcutAndWidgetContainer hotseatParent = hotseatLayout.getShortcutsAndWidgets();
+        int[][] matrix;
+
+        // KEYCODE_DPAD_DOWN in portrait (KEYCODE_DPAD_LEFT in landscape) is the only key allowed
+        // to take a user to the hotseat. For other dpad navigation, do not use the matrix extended
+        // with the hotseat.
+        if (keyCode == KeyEvent.KEYCODE_DPAD_DOWN &&
+                orientation == Configuration.ORIENTATION_PORTRAIT) {
+            matrix = FocusLogic.createSparseMatrix(layout, hotseatLayout, orientation);
+            countY = countY + 1;
+        } else if (keyCode == KeyEvent.KEYCODE_DPAD_LEFT &&
+                orientation == Configuration.ORIENTATION_LANDSCAPE) {
+            matrix = FocusLogic.createSparseMatrix(layout, hotseatLayout, orientation);
+            countY = countY + 1;
+        } else {
+            matrix = FocusLogic.createSparseMatrix(layout);
+        }
+
+        // Process the focus.
+        int newIconIndex = FocusLogic.handleKeyEvent(keyCode, countX, countY, matrix,
+                iconIndex, pageIndex, pageCount);
+        View newIcon = null;
+        switch (newIconIndex) {
+            case FocusLogic.NOOP:
+                if (keyCode == KeyEvent.KEYCODE_DPAD_UP) {
+                    newIcon = tabs;
                 }
                 break;
-            case KeyEvent.KEYCODE_DPAD_DOWN:
-                if (handleKeyEvent) {
-                    // Select the closest icon in the next line, otherwise select the button bar
-                    View newIcon = getClosestIconOnLine(layout, parent, v, 1);
-                    if (newIcon != null) {
-                        newIcon.requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_DOWN);
-                        wasHandled = true;
-                    } else if (hotseat != null) {
-                        hotseat.requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_DOWN);
-                    }
-                }
+            case FocusLogic.PREVIOUS_PAGE_FIRST_ITEM:
+                parent = getCellLayoutChildrenForIndex(workspace, pageIndex - 1);
+                newIcon = parent.getChildAt(0);
+                workspace.snapToPage(pageIndex - 1);
+            case FocusLogic.PREVIOUS_PAGE_LAST_ITEM:
+                parent = getCellLayoutChildrenForIndex(workspace, pageIndex - 1);
+                newIcon = parent.getChildAt(parent.getChildCount() - 1);
+                workspace.snapToPage(pageIndex - 1);
                 break;
-            case KeyEvent.KEYCODE_PAGE_UP:
-                if (handleKeyEvent) {
-                    // Select the first icon on the previous page or the first icon on this page
-                    // if there is no previous page
-                    if (pageIndex > 0) {
-                        parent = getCellLayoutChildrenForIndex(workspace, pageIndex - 1);
-                        View newIcon = getIconInDirection(layout, parent, -1, 1);
-                        if (newIcon != null) {
-                            newIcon.requestFocus();
-                        } else {
-                            // Snap to the previous page
-                            workspace.snapToPage(pageIndex - 1);
-                        }
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_UP);
-                    } else {
-                        View newIcon = getIconInDirection(layout, parent, -1, 1);
-                        if (newIcon != null) {
-                            newIcon.requestFocus();
-                            v.playSoundEffect(SoundEffectConstants.NAVIGATION_UP);
-                        }
-                    }
-                }
-                wasHandled = true;
+            case FocusLogic.NEXT_PAGE_FIRST_ITEM:
+                parent = getCellLayoutChildrenForIndex(workspace, pageIndex + 1);
+                newIcon = parent.getChildAt(0);
+                workspace.snapToPage(pageIndex - 1);
                 break;
-            case KeyEvent.KEYCODE_PAGE_DOWN:
-                if (handleKeyEvent) {
-                    // Select the first icon on the next page or the last icon on this page
-                    // if there is no previous page
-                    if (pageIndex < (pageCount - 1)) {
-                        parent = getCellLayoutChildrenForIndex(workspace, pageIndex + 1);
-                        View newIcon = getIconInDirection(layout, parent, -1, 1);
-                        if (newIcon != null) {
-                            newIcon.requestFocus();
-                        } else {
-                            // Snap to the next page
-                            workspace.snapToPage(pageIndex + 1);
-                        }
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_DOWN);
-                    } else {
-                        View newIcon = getIconInDirection(layout, parent,
-                                parent.getChildCount(), -1);
-                        if (newIcon != null) {
-                            newIcon.requestFocus();
-                            v.playSoundEffect(SoundEffectConstants.NAVIGATION_DOWN);
-                        }
-                    }
-                }
-                wasHandled = true;
+            case FocusLogic.CURRENT_PAGE_FIRST_ITEM:
+                newIcon = parent.getChildAt(0);
                 break;
-            case KeyEvent.KEYCODE_MOVE_HOME:
-                if (handleKeyEvent) {
-                    // Select the first icon on this page
-                    View newIcon = getIconInDirection(layout, parent, -1, 1);
-                    if (newIcon != null) {
-                        newIcon.requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_UP);
-                    }
-                }
-                wasHandled = true;
+            case FocusLogic.CURRENT_PAGE_LAST_ITEM:
+                newIcon = parent.getChildAt(parent.getChildCount() - 1);
                 break;
-            case KeyEvent.KEYCODE_MOVE_END:
-                if (handleKeyEvent) {
-                    // Select the last icon on this page
-                    View newIcon = getIconInDirection(layout, parent,
-                            parent.getChildCount(), -1);
-                    if (newIcon != null) {
-                        newIcon.requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_DOWN);
-                    }
+            default:
+                // current page, some item.
+                if (0 <= newIconIndex && newIconIndex < parent.getChildCount()) {
+                    newIcon = parent.getChildAt(newIconIndex);
+                } else if (parent.getChildCount() <= newIconIndex &&
+                        newIconIndex < parent.getChildCount() + hotseatParent.getChildCount()) {
+                    newIcon = hotseatParent.getChildAt(newIconIndex - parent.getChildCount());
                 }
-                wasHandled = true;
                 break;
-            default: break;
         }
-        return wasHandled;
+        if (newIcon != null) {
+            newIcon.requestFocus();
+            playSoundEffect(keyCode, v);
+        }
+        return consume;
     }
 
     /**
      * Handles key events for items in a Folder.
      */
     static boolean handleFolderKeyEvent(View v, int keyCode, KeyEvent e) {
+        boolean consume = FocusLogic.shouldConsume(keyCode);
+        if (e.getAction() == KeyEvent.ACTION_UP || !consume) {
+            return consume;
+        }
+        if (DEBUG) {
+            Log.v(TAG, String.format("Handle FOLDER keyevent=[%s].",
+                    KeyEvent.keyCodeToString(keyCode)));
+        }
+
+        // Initialize the variables.
         ShortcutAndWidgetContainer parent = (ShortcutAndWidgetContainer) v.getParent();
         final CellLayout layout = (CellLayout) parent.getParent();
         final ScrollView scrollView = (ScrollView) layout.getParent();
         final Folder folder = (Folder) scrollView.getParent();
         View title = folder.mFolderName;
+        Workspace workspace = (Workspace) v.getRootView().findViewById(R.id.workspace);
+        final int countX = layout.getCountX();
+        final int countY = layout.getCountY();
+        final int iconIndex = findIndexOfView(parent, v);
+        int pageIndex = workspace.indexOfChild(layout);
+        int pageCount = workspace.getChildCount();
+        int[][] map = FocusLogic.createFullMatrix(countX, countY, true /* incremental order index */
+                );
 
-        final int action = e.getAction();
-        final boolean handleKeyEvent = (action != KeyEvent.ACTION_UP);
-        boolean wasHandled = false;
-        switch (keyCode) {
-            case KeyEvent.KEYCODE_DPAD_LEFT:
-                if (handleKeyEvent) {
-                    // Select the previous icon
-                    View newIcon = getIconInDirection(layout, parent, v, -1);
-                    if (newIcon != null) {
-                        newIcon.requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_LEFT);
-                    }
+        // Process the focus.
+        int newIconIndex = FocusLogic.handleKeyEvent(keyCode, countX, countY, map, iconIndex,
+                pageIndex, pageCount);
+        View newIcon = null;
+        switch (newIconIndex) {
+            case FocusLogic.NOOP:
+                if (keyCode == KeyEvent.KEYCODE_DPAD_DOWN) {
+                    newIcon = title;
                 }
-                wasHandled = true;
                 break;
-            case KeyEvent.KEYCODE_DPAD_RIGHT:
-                if (handleKeyEvent) {
-                    // Select the next icon
-                    View newIcon = getIconInDirection(layout, parent, v, 1);
-                    if (newIcon != null) {
-                        newIcon.requestFocus();
-                    } else {
-                        title.requestFocus();
-                    }
-                    v.playSoundEffect(SoundEffectConstants.NAVIGATION_RIGHT);
+            case FocusLogic.PREVIOUS_PAGE_FIRST_ITEM:
+            case FocusLogic.PREVIOUS_PAGE_LAST_ITEM:
+            case FocusLogic.NEXT_PAGE_FIRST_ITEM:
+            case FocusLogic.CURRENT_PAGE_FIRST_ITEM:
+            case FocusLogic.CURRENT_PAGE_LAST_ITEM:
+                if (DEBUG) {
+                    Log.v(TAG, "Page advance handling not supported on folder icons.");
                 }
-                wasHandled = true;
                 break;
-            case KeyEvent.KEYCODE_DPAD_UP:
-                if (handleKeyEvent) {
-                    // Select the closest icon in the previous line
-                    View newIcon = getClosestIconOnLine(layout, parent, v, -1);
-                    if (newIcon != null) {
-                        newIcon.requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_UP);
-                    }
-                }
-                wasHandled = true;
+            default: // current page some item.
+                newIcon = parent.getChildAt(newIconIndex);
+                break;
+        }
+        if (newIcon != null) {
+            newIcon.requestFocus();
+            playSoundEffect(keyCode, v);
+        }
+        return consume;
+    }
+
+    //
+    // Helper methods.
+    //
+
+    /**
+     * Returns the Viewgroup containing page contents for the page at the index specified.
+     */
+    private static ViewGroup getAppsCustomizePage(ViewGroup container, int index) {
+        ViewGroup page = (ViewGroup) ((PagedView) container).getPageAt(index);
+        if (page instanceof CellLayout) {
+            // There are two layers, a PagedViewCellLayout and PagedViewCellLayoutChildren
+            page = ((CellLayout) page).getShortcutsAndWidgets();
+        }
+        return page;
+    }
+
+    /**
+     * Private helper method to get the CellLayoutChildren given a CellLayout index.
+     */
+    private static ShortcutAndWidgetContainer getCellLayoutChildrenForIndex(
+            ViewGroup container, int i) {
+        CellLayout parent = (CellLayout) container.getChildAt(i);
+        return parent.getShortcutsAndWidgets();
+    }
+
+    private static int findIndexOfView(ViewGroup parent, View v) {
+        for (int i = 0; i < parent.getChildCount(); i++) {
+            if (v != null && v.equals(parent.getChildAt(i))) {
+                return i;
+            }
+        }
+        return -1;
+    }
+
+    /**
+     * Helper method to be used for playing sound effects.
+     */
+    private static void playSoundEffect(int keyCode, View v) {
+        switch (keyCode) {
+            case KeyEvent.KEYCODE_DPAD_LEFT:
+                v.playSoundEffect(SoundEffectConstants.NAVIGATION_LEFT);
+                break;
+            case KeyEvent.KEYCODE_DPAD_RIGHT:
+                v.playSoundEffect(SoundEffectConstants.NAVIGATION_RIGHT);
                 break;
             case KeyEvent.KEYCODE_DPAD_DOWN:
-                if (handleKeyEvent) {
-                    // Select the closest icon in the next line
-                    View newIcon = getClosestIconOnLine(layout, parent, v, 1);
-                    if (newIcon != null) {
-                        newIcon.requestFocus();
-                    } else {
-                        title.requestFocus();
-                    }
-                    v.playSoundEffect(SoundEffectConstants.NAVIGATION_DOWN);
-                }
-                wasHandled = true;
+            case KeyEvent.KEYCODE_PAGE_DOWN:
+            case KeyEvent.KEYCODE_MOVE_END:
+                v.playSoundEffect(SoundEffectConstants.NAVIGATION_DOWN);
                 break;
+            case KeyEvent.KEYCODE_DPAD_UP:
+            case KeyEvent.KEYCODE_PAGE_UP:
             case KeyEvent.KEYCODE_MOVE_HOME:
-                if (handleKeyEvent) {
-                    // Select the first icon on this page
-                    View newIcon = getIconInDirection(layout, parent, -1, 1);
-                    if (newIcon != null) {
-                        newIcon.requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_UP);
-                    }
-                }
-                wasHandled = true;
+                v.playSoundEffect(SoundEffectConstants.NAVIGATION_UP);
                 break;
-            case KeyEvent.KEYCODE_MOVE_END:
-                if (handleKeyEvent) {
-                    // Select the last icon on this page
-                    View newIcon = getIconInDirection(layout, parent,
-                            parent.getChildCount(), -1);
-                    if (newIcon != null) {
-                        newIcon.requestFocus();
-                        v.playSoundEffect(SoundEffectConstants.NAVIGATION_DOWN);
-                    }
-                }
-                wasHandled = true;
+            default:
                 break;
-            default: break;
         }
-        return wasHandled;
     }
 }
diff --git a/src/com/android/launcher3/util/FocusLogic.java b/src/com/android/launcher3/util/FocusLogic.java
new file mode 100644
index 000000000..23375dc43
--- /dev/null
+++ b/src/com/android/launcher3/util/FocusLogic.java
@@ -0,0 +1,434 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.launcher3.util;
+
+import android.content.res.Configuration;
+import android.util.Log;
+import android.view.KeyEvent;
+import android.view.ViewGroup;
+
+import com.android.launcher3.CellLayout;
+
+/**
+ * Calculates the next item that a {@link KeyEvent} should change the focus to.
+ *<p>
+ * Note, this utility class calculates everything regards to icon index and its (x,y) coordinates.
+ * Currently supports:
+ * <ul>
+ *  <li> full matrix of cells that are 1x1
+ *  <li> sparse matrix of cells that are 1x1
+ *     [ 1][  ][ 2][  ]
+ *     [  ][  ][ 3][  ]
+ *     [  ][ 4][  ][  ]
+ *     [  ][ 5][ 6][ 7]
+ * </ul>
+ * *<p>
+ * For testing, one can use a BT keyboard, or use following adb command.
+ * ex. $ adb shell input keyevent 20 // KEYCODE_DPAD_LEFT
+ */
+public class FocusLogic {
+
+    private static final String TAG = "Focus";
+    private static final boolean DEBUG = false;
+
+    // Item and page index related constant used by {@link #handleKeyEvent}.
+    public static final int NOOP = -1;
+    public static final int PREVIOUS_PAGE_FIRST_ITEM    = -2;
+    public static final int PREVIOUS_PAGE_LAST_ITEM     = -3;
+    public static final int CURRENT_PAGE_FIRST_ITEM     = -4;
+    public static final int CURRENT_PAGE_LAST_ITEM      = -5;
+    public static final int NEXT_PAGE_FIRST_ITEM        = -6;
+
+    // Matrix related constant.
+    public static final int EMPTY = -1;
+
+    /**
+     * Returns true only if this utility class handles the key code.
+     */
+    public static boolean shouldConsume(int keyCode) {
+        if (keyCode == KeyEvent.KEYCODE_DPAD_LEFT || keyCode == KeyEvent.KEYCODE_DPAD_RIGHT ||
+                keyCode == KeyEvent.KEYCODE_DPAD_UP || keyCode == KeyEvent.KEYCODE_DPAD_DOWN ||
+                keyCode == KeyEvent.KEYCODE_MOVE_HOME || keyCode == KeyEvent.KEYCODE_MOVE_END ||
+                keyCode == KeyEvent.KEYCODE_PAGE_UP || keyCode == KeyEvent.KEYCODE_PAGE_DOWN) {
+            return true;
+        }
+        return false;
+    }
+
+    public static int handleKeyEvent(int keyCode, int cntX, int cntY, int [][] map,
+            int iconIdx, int pageIndex, int pageCount) {
+
+        if (DEBUG) {
+            Log.v(TAG, String.format(
+                    "handleKeyEvent START: cntX=%d, cntY=%d, iconIdx=%d, pageIdx=%d, pageCnt=%d",
+                    cntX, cntY, iconIdx, pageIndex, pageCount));
+        }
+
+        int newIndex = NOOP;
+        switch (keyCode) {
+            case KeyEvent.KEYCODE_DPAD_LEFT:
+                newIndex = handleDpadHorizontal(iconIdx, cntX, cntY, map, -1 /*increment*/);
+                if (newIndex == NOOP && pageIndex > 0) {
+                    return PREVIOUS_PAGE_LAST_ITEM;
+                }
+                break;
+            case KeyEvent.KEYCODE_DPAD_RIGHT:
+                newIndex = handleDpadHorizontal(iconIdx, cntX, cntY, map, 1 /*increment*/);
+                if (newIndex == NOOP && pageIndex < pageCount - 1) {
+                    return NEXT_PAGE_FIRST_ITEM;
+                }
+                break;
+            case KeyEvent.KEYCODE_DPAD_DOWN:
+                newIndex = handleDpadVertical(iconIdx, cntX, cntY, map, 1  /*increment*/);
+                break;
+            case KeyEvent.KEYCODE_DPAD_UP:
+                newIndex = handleDpadVertical(iconIdx, cntX, cntY, map, -1  /*increment*/);
+                break;
+            case KeyEvent.KEYCODE_MOVE_HOME:
+                newIndex = handleMoveHome();
+                break;
+            case KeyEvent.KEYCODE_MOVE_END:
+                newIndex = handleMoveEnd();
+                break;
+            case KeyEvent.KEYCODE_PAGE_DOWN:
+                newIndex = handlePageDown(pageIndex, pageCount);
+                break;
+            case KeyEvent.KEYCODE_PAGE_UP:
+                newIndex = handlePageUp(pageIndex);
+                break;
+            default:
+                break;
+        }
+
+        if (DEBUG) {
+            Log.v(TAG, String.format("handleKeyEvent FINISH: index [%d -> %s]",
+                    iconIdx, getStringIndex(newIndex)));
+        }
+        return newIndex;
+    }
+
+    /**
+     * Returns a matrix of size (m x n) that has been initialized with incremental index starting
+     * with 0 or a matrix where all the values are initialized to {@link #EMPTY}.
+     *
+     * @param m                 number of columns in the matrix
+     * @param n                 number of rows in the matrix
+     * @param incrementOrder    {@code true} if the matrix contents should increment in reading
+     *                          order with 0 indexing. {@code false} if each cell should be
+     *                          initialized to {@link #EMPTY};
+     */
+    // TODO: get rid of dynamic matrix creation.
+    public static int[][] createFullMatrix(int m, int n, boolean incrementOrder) {
+        int[][] matrix = new int [m][n];
+        for (int i=0; i < m;i++) {
+            for (int j=0; j < n; j++) {
+                if (incrementOrder) {
+                    matrix[i][j] = j * m + i;
+                } else {
+                    matrix[i][j] = EMPTY;
+                }
+            }
+        }
+        return matrix;
+    }
+
+    /**
+     * Returns a matrix of size same as the {@link CellLayout} dimension that is initialized with the
+     * index of the child view.
+     */
+    // TODO: get rid of the dynamic matrix creation
+    public static int[][] createSparseMatrix(CellLayout layout) {
+        ViewGroup parent = layout.getShortcutsAndWidgets();
+        final int m = layout.getCountX();
+        final int n = layout.getCountY();
+
+        int[][] matrix = createFullMatrix(m, n, false /* initialize to #EMPTY */);
+
+        // Iterate thru the children.
+        for (int i = 0; i < parent.getChildCount(); i++ ) {
+            int cx = ((CellLayout.LayoutParams) parent.getChildAt(i).getLayoutParams()).cellX;
+            int cy = ((CellLayout.LayoutParams) parent.getChildAt(i).getLayoutParams()).cellY;
+            matrix[cx][cy] = i;
+        }
+        if (DEBUG) {
+            printMatrix(matrix, m, n);
+        }
+        return matrix;
+    }
+
+    /**
+     * Creates a sparse matrix that merges the icon and hotseat view group using the cell layout.
+     * The size of the returning matrix is [icon column count x (icon + hotseat row count)]
+     * in portrait orientation. In landscape, [(icon + hotseat) column count x (icon row count)]
+     */
+ // TODO: get rid of the dynamic matrix creation
+    public static int[][] createSparseMatrix(CellLayout iconLayout, CellLayout hotseatLayout,
+            int orientation) {
+
+        ViewGroup iconParent = iconLayout.getShortcutsAndWidgets();
+        ViewGroup hotseatParent = hotseatLayout.getShortcutsAndWidgets();
+
+        int m, n;
+        if (orientation == Configuration.ORIENTATION_PORTRAIT) {
+            m = iconLayout.getCountX();
+            n = iconLayout.getCountY() + hotseatLayout.getCountY();
+        } else if (orientation == Configuration.ORIENTATION_LANDSCAPE) {
+            m = iconLayout.getCountX() + hotseatLayout.getCountX();
+            n = iconLayout.getCountY();
+        } else {
+            throw new IllegalStateException(String.format(
+                    "orientation type=%d is not supported for key board events.", orientation));
+        }
+        int[][] matrix = createFullMatrix(m, n, false /* set all cell to empty */);
+
+        // Iterate thru the children of the top parent.
+        for (int i = 0; i < iconParent.getChildCount(); i++) {
+            int cx = ((CellLayout.LayoutParams) iconParent.getChildAt(i).getLayoutParams()).cellX;
+            int cy = ((CellLayout.LayoutParams) iconParent.getChildAt(i).getLayoutParams()).cellY;
+            matrix[cx][cy] = i;
+        }
+
+        // Iterate thru the children of the bottom parent
+        for(int i = 0; i < hotseatParent.getChildCount(); i++) {
+            // If the hotseat view group contains more items than topColumnCnt, then just
+            // discard them.
+            // TODO: make this more elegant. (look at DynamicGrid)
+            if (orientation == Configuration.ORIENTATION_PORTRAIT) {
+                int cx = ((CellLayout.LayoutParams)
+                        hotseatParent.getChildAt(i).getLayoutParams()).cellX;
+                if (cx < iconLayout.getCountX()) {
+                    matrix[cx][iconLayout.getCountY()] = iconParent.getChildCount() + i;
+                }
+            } else if (orientation == Configuration.ORIENTATION_LANDSCAPE) {
+                int cy = ((CellLayout.LayoutParams)
+                        hotseatParent.getChildAt(i).getLayoutParams()).cellY;
+                if (cy < iconLayout.getCountY()) {
+                    matrix[iconLayout.getCountX()][cy] = iconParent.getChildCount() + i;
+                }
+            }
+        }
+        if (DEBUG) {
+            printMatrix(matrix, m, n);
+        }
+        return matrix;
+    }
+
+    //
+    // key event handling methods.
+    //
+
+    /**
+     * Calculates icon that has is closest to the horizontal axis in reference to the cur icon.
+     *
+     * Example of the check order for KEYCODE_DPAD_RIGHT:
+     * [  ][  ][13][14][15]
+     * [  ][ 6][ 8][10][12]
+     * [ X][ 1][ 2][ 3][ 4]
+     * [  ][ 5][ 7][ 9][11]
+     */
+    // TODO: add unit tests to verify all permutation.
+    private static int handleDpadHorizontal(int iconIdx, int cntX, int cntY,
+            int[][] matrix, int increment) {
+        if(matrix == null) {
+            throw new IllegalStateException("Dpad navigation requires a matrix.");
+        }
+        int newIconIndex = NOOP;
+
+        int xPos = -1;
+        int yPos = -1;
+        // Figure out the location of the icon.
+        for (int i = 0; i < cntX; i++) {
+            for (int j = 0; j < cntY; j++) {
+                if (matrix[i][j] == iconIdx) {
+                    xPos = i;
+                    yPos = j;
+                }
+            }
+        }
+        if (DEBUG) {
+            Log.v(TAG, String.format("\thandleDpadHorizontal: \t[x, y]=[%d, %d] iconIndex=%d",
+                    xPos, yPos, iconIdx));
+        }
+
+        // Rule1: check first in the horizontal direction
+        for (int i = xPos + increment; 0 <= i && i < cntX; i = i + increment) {
+            if (DEBUG) {
+                Log.v(TAG, String.format("\t\tsearch: \t[x, y]=[%d, %d] iconIndex=%d",
+                        i, yPos, matrix[i][yPos]));
+            }
+            if (matrix[i][yPos] != -1) {
+                newIconIndex = matrix[i][yPos];
+                return newIconIndex;
+            }
+        }
+
+        // Rule2: check (x1-n, yPos + increment),   (x1-n, yPos - increment)
+        //              (x2-n, yPos + 2*increment), (x2-n, yPos - 2*increment)
+        int nextYPos1;
+        int nextYPos2;
+        int i = -1;
+        for (int coeff = 1; coeff < cntY; coeff++) {
+            nextYPos1 = yPos + coeff * increment;
+            nextYPos2 = yPos - coeff * increment;
+            for (i = xPos + increment * coeff; 0 <= i && i < cntX; i = i + increment) {
+                if ((newIconIndex = inspectMatrix(i, nextYPos1, cntX, cntY, matrix)) != NOOP) {
+                    return newIconIndex;
+                }
+                if ((newIconIndex = inspectMatrix(i, nextYPos2, cntX, cntY, matrix)) != NOOP) {
+                    return newIconIndex;
+                }
+            }
+        }
+        return newIconIndex;
+    }
+
+    /**
+     * Calculates icon that is closest to the vertical axis in reference to the current icon.
+     *
+     * Example of the check order for KEYCODE_DPAD_DOWN:
+     * [  ][  ][  ][ X][  ][  ][  ]
+     * [  ][  ][ 5][ 1][ 4][  ][  ]
+     * [  ][10][ 7][ 2][ 6][ 9][  ]
+     * [14][12][ 9][ 3][ 8][11][13]
+     */
+    // TODO: add unit tests to verify all permutation.
+    private static int handleDpadVertical(int iconIndex, int cntX, int cntY,
+            int [][] matrix, int increment) {
+        int newIconIndex = NOOP;
+        if(matrix == null) {
+            throw new IllegalStateException("Dpad navigation requires a matrix.");
+        }
+
+        int xPos = -1;
+        int yPos = -1;
+        // Figure out the location of the icon.
+        for (int i = 0; i< cntX; i++) {
+            for (int j = 0; j < cntY; j++) {
+                if (matrix[i][j] == iconIndex) {
+                    xPos = i;
+                    yPos = j;
+                }
+            }
+        }
+
+        if (DEBUG) {
+            Log.v(TAG, String.format("\thandleDpadVertical: \t[x, y]=[%d, %d] iconIndex=%d",
+                    xPos, yPos, iconIndex));
+        }
+
+        // Rule1: check first in the dpad direction
+        for (int j = yPos + increment; 0 <= j && j <cntY && 0 <= j; j = j + increment) {
+            if (DEBUG) {
+                Log.v(TAG, String.format("\t\tsearch: \t[x, y]=[%d, %d] iconIndex=%d",
+                        xPos, j, matrix[xPos][j]));
+            }
+            if (matrix[xPos][j] != -1) {
+                newIconIndex = matrix[xPos][j];
+                return newIconIndex;
+            }
+        }
+
+        // Rule2: check (xPos + increment, y_(1-n)),   (xPos - increment, y_(1-n))
+        //              (xPos + 2*increment, y_(2-n))), (xPos - 2*increment, y_(2-n))
+        int nextXPos1;
+        int nextXPos2;
+        int j = -1;
+        for (int coeff = 1; coeff < cntX; coeff++) {
+            nextXPos1 = xPos + coeff * increment;
+            nextXPos2 = xPos - coeff * increment;
+            for (j = yPos + increment * coeff; 0 <= j && j < cntY; j = j + increment) {
+                if ((newIconIndex = inspectMatrix(nextXPos1, j, cntX, cntY, matrix)) != NOOP) {
+                    return newIconIndex;
+                }
+                if ((newIconIndex = inspectMatrix(nextXPos2, j, cntX, cntY, matrix)) != NOOP) {
+                    return newIconIndex;
+                }
+            }
+        }
+        return newIconIndex;
+    }
+
+    private static int handleMoveHome() {
+        return CURRENT_PAGE_FIRST_ITEM;
+    }
+
+    private static int handleMoveEnd() {
+        return CURRENT_PAGE_LAST_ITEM;
+    }
+
+    private static int handlePageDown(int pageIndex, int pageCount) {
+        if (pageIndex < pageCount -1) {
+            return NEXT_PAGE_FIRST_ITEM;
+        }
+        return CURRENT_PAGE_LAST_ITEM;
+    }
+
+    private static int handlePageUp(int pageIndex) {
+        if (pageIndex > 0) {
+            return PREVIOUS_PAGE_FIRST_ITEM;
+        } else {
+            return CURRENT_PAGE_FIRST_ITEM;
+        }
+    }
+
+    //
+    // Helper methods.
+    //
+
+    private static boolean isValid(int xPos, int yPos, int countX, int countY) {
+        return (0 <= xPos && xPos < countX && 0 <= yPos && yPos < countY);
+    }
+
+    private static int inspectMatrix(int x, int y, int cntX, int cntY, int[][] matrix) {
+        int newIconIndex = NOOP;
+        if (isValid(x, y, cntX, cntY)) {
+            if (matrix[x][y] != -1) {
+                newIconIndex = matrix[x][y];
+                if (DEBUG) {
+                    Log.v(TAG, String.format("\t\tinspect: \t[x, y]=[%d, %d] %d",
+                            x, y, matrix[x][y]));
+                }
+                return newIconIndex;
+            }
+        }
+        return newIconIndex;
+    }
+
+    private static String getStringIndex(int index) {
+        switch(index) {
+            case NOOP: return "NOOP";
+            case PREVIOUS_PAGE_FIRST_ITEM:  return "PREVIOUS_PAGE_FIRST";
+            case PREVIOUS_PAGE_LAST_ITEM:   return "PREVIOUS_PAGE_LAST";
+            case CURRENT_PAGE_FIRST_ITEM:   return "CURRENT_PAGE_FIRST";
+            case CURRENT_PAGE_LAST_ITEM:    return "CURRENT_PAGE_LAST";
+            case NEXT_PAGE_FIRST_ITEM:      return "NEXT_PAGE_FIRST";
+            default:
+                return Integer.toString(index);
+        }
+    }
+
+    private static void printMatrix(int[][] matrix, int m, int n) {
+        Log.v(TAG, "\tprintMap:");
+        for (int j=0; j < n; j++) {
+            String colY = "\t\t";
+            for (int i=0; i < m; i++) {
+                colY +=  String.format("%3d",matrix[i][j]);
+            }
+            Log.v(TAG, colY);
+        }
+    }
+}