Refactoring push reordering (issue 7139335)

-> This new approach is actually correct in emulating cascaded  pushing of
   items left, right, up and down.
-> Takes care of a couple crashes and some instances where reordering
   was not doing the right thing.

Change-Id: I016120e62f5d6fa1a2a6289c3badcb6ec230b2a3

1 files changed, 366 insertions, 155 deletions

diff --git a/src/com/android/launcher2/CellLayout.java b/src/com/android/launcher2/CellLayout.java
index f742255cc..7818da435 100644
--- a/src/com/android/launcher2/CellLayout.java
+++ b/src/com/android/launcher2/CellLayout.java
@@ -53,6 +53,8 @@ import com.android.launcher2.FolderIcon.FolderRingAnimator;
 
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.Stack;
 
@@ -1554,48 +1556,6 @@ public class CellLayout extends ViewGroup {
         return bestXY;
     }
 
-    private int[] findNearestAreaInDirection(int cellX, int cellY, int spanX, int spanY, 
-            int[] direction,boolean[][] occupied,
-            boolean blockOccupied[][], int[] result) {
-        // Keep track of best-scoring drop area
-        final int[] bestXY = result != null ? result : new int[2];
-        bestXY[0] = -1;
-        bestXY[1] = -1;
-        float bestDistance = Float.MAX_VALUE;
-
-        // We use this to march in a single direction
-        if ((direction[0] != 0 && direction[1] != 0) ||
-                (direction[0] == 0 && direction[1] == 0)) {
-            return bestXY;
-        }
-
-        // This will only incrememnet one of x or y based on the assertion above
-        int x = cellX + direction[0];
-        int y = cellY + direction[1];
-        while (x >= 0 && x + spanX <= mCountX && y >= 0 && y + spanY <= mCountY) {
-            boolean fail = false;
-            for (int i = 0; i < spanX; i++) {
-                for (int j = 0; j < spanY; j++) {
-                    if (occupied[x + i][y + j] && (blockOccupied == null || blockOccupied[i][j])) {
-                        fail = true;                    
-                    }
-                }
-            }
-            if (!fail) {
-                float distance = (float)
-                        Math.sqrt((x - cellX) * (x - cellX) + (y - cellY) * (y - cellY));
-                if (Float.compare(distance,  bestDistance) < 0) {
-                    bestDistance = distance;
-                    bestXY[0] = x;
-                    bestXY[1] = y;
-                }
-            }
-            x += direction[0];
-            y += direction[1];
-        }
-        return bestXY;
-    }
-
     private boolean addViewToTempLocation(View v, Rect rectOccupiedByPotentialDrop,
             int[] direction, ItemConfiguration currentState) {
         CellAndSpan c = currentState.map.get(v);
@@ -1609,118 +1569,343 @@ public class CellLayout extends ViewGroup {
             c.x = mTempLocation[0];
             c.y = mTempLocation[1];
             success = true;
-
         }
         markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, true);
         return success;
     }
 
-    // This method looks in the specified direction to see if there are additional views adjacent
-    // to the current set of views. If there are, then these views are added to the current
-    // set of views. This is performed iteratively, giving a cascading push behaviour.
-    private boolean addViewInDirection(ArrayList<View> views, Rect boundingRect, int[] direction,
-            boolean[][] occupied, View dragView, ItemConfiguration currentState) {
-        boolean found = false;
+    /**
+     * This helper class defines a cluster of views. It helps with defining complex edges
+     * of the cluster and determining how those edges interact with other views. The edges
+     * essentially define a fine-grained boundary around the cluster of views -- like a more
+     * precise version of a bounding box.
+     */
+    private class ViewCluster {
+        final static int LEFT = 0;
+        final static int TOP = 1;
+        final static int RIGHT = 2;
+        final static int BOTTOM = 3;
+
+        ArrayList<View> views;
+        ItemConfiguration config;
+        Rect boundingRect = new Rect();
+
+        int[] leftEdge = new int[mCountY];
+        int[] rightEdge = new int[mCountY];
+        int[] topEdge = new int[mCountX];
+        int[] bottomEdge = new int[mCountX];
+        boolean leftEdgeDirty, rightEdgeDirty, topEdgeDirty, bottomEdgeDirty, boundingRectDirty;
 
-        int childCount = mShortcutsAndWidgets.getChildCount();
-        Rect r0 = new Rect(boundingRect);
-        Rect r1 = new Rect();
+        @SuppressWarnings("unchecked")
+        public ViewCluster(ArrayList<View> views, ItemConfiguration config) {
+            this.views = (ArrayList<View>) views.clone();
+            this.config = config;
+            resetEdges();
+        }
 
-        // First, we consider the rect of the views that we are trying to translate
-        int deltaX = 0;
-        int deltaY = 0;
-        if (direction[1] < 0) {
-            r0.set(r0.left, r0.top - 1, r0.right, r0.bottom - 1);
-            deltaY = -1;
-        } else if (direction[1] > 0) {
-            r0.set(r0.left, r0.top + 1, r0.right, r0.bottom + 1);
-            deltaY = 1;
-        } else if (direction[0] < 0) {
-            r0.set(r0.left - 1, r0.top, r0.right - 1, r0.bottom);
-            deltaX = -1;
-        } else if (direction[0] > 0) {
-            r0.set(r0.left + 1, r0.top, r0.right + 1, r0.bottom);
-            deltaX = 1;
+        void resetEdges() {
+            for (int i = 0; i < mCountX; i++) {
+                topEdge[i] = -1;
+                bottomEdge[i] = -1;
+            }
+            for (int i = 0; i < mCountY; i++) {
+                leftEdge[i] = -1;
+                rightEdge[i] = -1;
+            }
+            leftEdgeDirty = true;
+            rightEdgeDirty = true;
+            bottomEdgeDirty = true;
+            topEdgeDirty = true;
+            boundingRectDirty = true;
+        }
+
+        void computeEdge(int which, int[] edge) {
+            int count = views.size();
+            for (int i = 0; i < count; i++) {
+                CellAndSpan cs = config.map.get(views.get(i));
+                switch (which) {
+                    case LEFT:
+                        int left = cs.x;
+                        for (int j = cs.y; j < cs.y + cs.spanY; j++) {
+                            if (left < edge[j] || edge[j] < 0) {
+                                edge[j] = left;
+                            }
+                        }
+                        break;
+                    case RIGHT:
+                        int right = cs.x + cs.spanX;
+                        for (int j = cs.y; j < cs.y + cs.spanY; j++) {
+                            if (right > edge[j]) {
+                                edge[j] = right;
+                            }
+                        }
+                        break;
+                    case TOP:
+                        int top = cs.y;
+                        for (int j = cs.x; j < cs.x + cs.spanX; j++) {
+                            if (top < edge[j] || edge[j] < 0) {
+                                edge[j] = top;
+                            }
+                        }
+                        break;
+                    case BOTTOM:
+                        int bottom = cs.y + cs.spanY;
+                        for (int j = cs.x; j < cs.x + cs.spanX; j++) {
+                            if (bottom > edge[j]) {
+                                edge[j] = bottom;
+                            }
+                        }
+                        break;
+                }
+            }
         }
 
-        // Now we see which views, if any, are being overlapped by shifting the current group
-        // of views in the desired direction.
-        for (int i = 0; i < childCount; i++) {
-            // We don't need to worry about views already in our group, or the current drag view.
-            View child = mShortcutsAndWidgets.getChildAt(i);
-            if (views.contains(child) || child == dragView) continue;
-            CellAndSpan c = currentState.map.get(child);
+        boolean isViewTouchingEdge(View v, int whichEdge) {
+            CellAndSpan cs = config.map.get(v);
 
-            LayoutParams lp = (LayoutParams) child.getLayoutParams();
-            r1.set(c.x, c.y, c.x + c.spanX, c.y + c.spanY);
-            if (Rect.intersects(r0, r1)) {
-                if (!lp.canReorder) {
-                    return false;
-                }
-                // First we verify that the view in question is at the border of the extents
-                // of the block of items we are pushing
-                if ((direction[0] < 0 && c.x == r0.left) ||
-                        (direction[0] > 0 && c.x == r0.right - 1) ||
-                        (direction[1] < 0 && c.y == r0.top) ||
-                        (direction[1] > 0 && c.y == r0.bottom - 1)) {
-                    boolean pushed = false;
-                    // Since the bounding rect is a coarse description of the region (there can
-                    // be holes at the edge of the block), we need to check to verify that a solid
-                    // piece is intersecting. This ensures that interlocking is possible.
-                    for (int x = c.x; x < c.x + c.spanX; x++) {
-                        for (int y = c.y; y < c.y + c.spanY; y++) {
-                            if (occupied[x - deltaX][y - deltaY]) {
-                                pushed = true;
-                                break;
-                            }
-                            if (pushed) break;
+            int[] edge = getEdge(whichEdge);
+
+            switch (whichEdge) {
+                case LEFT:
+                    for (int i = cs.y; i < cs.y + cs.spanY; i++) {
+                        if (edge[i] == cs.x + cs.spanX) {
+                            return true;
                         }
                     }
-                    if (pushed) {
-                        views.add(child);
+                    break;
+                case RIGHT:
+                    for (int i = cs.y; i < cs.y + cs.spanY; i++) {
+                        if (edge[i] == cs.x) {
+                            return true;
+                        }
+                    }
+                    break;
+                case TOP:
+                    for (int i = cs.x; i < cs.x + cs.spanX; i++) {
+                        if (edge[i] == cs.y + cs.spanY) {
+                            return true;
+                        }
+                    }
+                    break;
+                case BOTTOM:
+                    for (int i = cs.x; i < cs.x + cs.spanX; i++) {
+                        if (edge[i] == cs.y) {
+                            return true;
+                        }
+                    }
+                    break;
+            }
+            return false;
+        }
+
+        void shift(int whichEdge, int delta) {
+            for (View v: views) {
+                CellAndSpan c = config.map.get(v);
+                switch (whichEdge) {
+                    case LEFT:
+                        c.x -= delta;
+                        break;
+                    case RIGHT:
+                        c.x += delta;
+                        break;
+                    case TOP:
+                        c.y -= delta;
+                        break;
+                    case BOTTOM:
+                    default:
+                        c.y += delta;
+                        break;
+                }
+            }
+            resetEdges();
+        }
+
+        public void addView(View v) {
+            views.add(v);
+            resetEdges();
+        }
+
+        public Rect getBoundingRect() {
+            if (boundingRectDirty) {
+                boolean first = true;
+                for (View v: views) {
+                    CellAndSpan c = config.map.get(v);
+                    if (first) {
+                        boundingRect.set(c.x, c.y, c.x + c.spanX, c.y + c.spanY);
+                        first = false;
+                    } else {
                         boundingRect.union(c.x, c.y, c.x + c.spanX, c.y + c.spanY);
-                        found = true;
                     }
                 }
             }
+            return boundingRect;
+        }
+
+        public int[] getEdge(int which) {
+            switch (which) {
+                case LEFT:
+                    return getLeftEdge();
+                case RIGHT:
+                    return getRightEdge();
+                case TOP:
+                    return getTopEdge();
+                case BOTTOM:
+                default:
+                    return getBottomEdge();
+            }
+        }
+
+        public int[] getLeftEdge() {
+            if (leftEdgeDirty) {
+                computeEdge(LEFT, leftEdge);
+            }
+            return leftEdge;
+        }
+
+        public int[] getRightEdge() {
+            if (rightEdgeDirty) {
+                computeEdge(RIGHT, rightEdge);
+            }
+            return rightEdge;
+        }
+
+        public int[] getTopEdge() {
+            if (topEdgeDirty) {
+                computeEdge(TOP, topEdge);
+            }
+            return topEdge;
+        }
+
+        public int[] getBottomEdge() {
+            if (bottomEdgeDirty) {
+                computeEdge(BOTTOM, bottomEdge);
+            }
+            return bottomEdge;
+        }
+
+        PositionComparator comparator = new PositionComparator();
+        class PositionComparator implements Comparator<View> {
+            int whichEdge = 0;
+            public int compare(View left, View right) {
+                CellAndSpan l = config.map.get(left);
+                CellAndSpan r = config.map.get(right);
+                switch (whichEdge) {
+                    case LEFT:
+                        return (r.x + r.spanX) - (l.x + l.spanX);
+                    case RIGHT:
+                        return l.x - r.x;
+                    case TOP:
+                        return (r.y + r.spanY) - (l.y + l.spanY);
+                    case BOTTOM:
+                    default:
+                        return l.y - r.y;
+                }
+            }
+        }
+
+        public void sortConfigurationForEdgePush(int edge) {
+            comparator.whichEdge = edge;
+            Collections.sort(config.sortedViews, comparator);
         }
-        return found;
     }
 
-    private void completeSetOfViewsToMove(ArrayList<View> views, Rect boundingRect, int[] direction,
-            boolean[][] occupied, View dragView, ItemConfiguration currentState) {
-        Rect r0 = new Rect(boundingRect);
-        int minRuns = 0;
+    private boolean pushViewsToTempLocation(ArrayList<View> views, Rect rectOccupiedByPotentialDrop,
+            int[] direction, View dragView, ItemConfiguration currentState) {
+
+        ViewCluster cluster = new ViewCluster(views, currentState);
+        Rect clusterRect = cluster.getBoundingRect();
+        int whichEdge;
+        int pushDistance;
+        boolean fail = false;
 
-        // The first thing we do is to reduce the bounding rect to first or last row or column,
-        // depending on the direction. Then, we add any necessary views that are already contained
-        // by the bounding rect, but aren't in the list of intersecting views, and will be pushed
-        // by something already in the intersecting views.
-        if (direction[1] < 0) {
-            r0.set(r0.left, r0.bottom - 1, r0.right, r0.bottom);
-        } else if (direction[1] > 0) {
-            r0.set(r0.left, r0.top, r0.right, r0.top + 1);
-        } else if (direction[0] < 0) {
-            r0.set(r0.right - 1, r0.top, r0.right, r0.bottom);
+        // Determine the edge of the cluster that will be leading the push and how far
+        // the cluster must be shifted.
+        if (direction[0] < 0) {
+            whichEdge = ViewCluster.LEFT;
+            pushDistance = clusterRect.right - rectOccupiedByPotentialDrop.left;
         } else if (direction[0] > 0) {
-            r0.set(r0.left, r0.top, r0.left + 1, r0.bottom);
+            whichEdge = ViewCluster.RIGHT;
+            pushDistance = rectOccupiedByPotentialDrop.right - clusterRect.left;
+        } else if (direction[1] < 0) {
+            whichEdge = ViewCluster.TOP;
+            pushDistance = clusterRect.bottom - rectOccupiedByPotentialDrop.top;
+        } else {
+            whichEdge = ViewCluster.BOTTOM;
+            pushDistance = rectOccupiedByPotentialDrop.bottom - clusterRect.top;
+        }
+
+        // Break early for invalid push distance.
+        if (pushDistance <= 0) {
+            return false;
         }
 
-        minRuns = Math.max(Math.abs(boundingRect.width() - r0.width()),
-                Math.abs(boundingRect.height() - r0.height())) + 1;
+        // Mark the occupied state as false for the group of views we want to move.
+        for (View v: views) {
+            CellAndSpan c = currentState.map.get(v);
+            markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, false);
+        }
+
+        // We save the current configuration -- if we fail to find a solution we will revert
+        // to the initial state. The process of finding a solution modifies the configuration
+        // in place, hence the need for revert in the failure case.
+        currentState.save();
+
+        // The pushing algorithm is simplified by considering the views in the order in which
+        // they would be pushed by the cluster. For example, if the cluster is leading with its
+        // left edge, we consider sort the views by their right edge, from right to left.
+        cluster.sortConfigurationForEdgePush(whichEdge);
+
+        while (pushDistance > 0 && !fail) {
+            for (View v: currentState.sortedViews) {
+                // For each view that isn't in the cluster, we see if the leading edge of the
+                // cluster is contacting the edge of that view. If so, we add that view to the
+                // cluster.
+                if (!cluster.views.contains(v) && v != dragView) {
+                    if (cluster.isViewTouchingEdge(v, whichEdge)) {
+                        LayoutParams lp = (LayoutParams) v.getLayoutParams();
+                        if (!lp.canReorder) {
+                            // The push solution includes the all apps button, this is not viable.
+                            fail = true;
+                            break;
+                        }
+                        cluster.addView(v);
+                        CellAndSpan c = currentState.map.get(v);
+
+                        // Adding view to cluster, mark it as not occupied.
+                        markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, false);
+                    }
+                }
+            }
+            pushDistance--;
 
-        // Here the first number of runs (minRuns) accounts for the the comment above, and
-        // further runs execute based on whether the intersecting views / bounding rect need
-        // to be expanded to include other views that will be pushed.
-        while (addViewInDirection(views, r0, direction, mTmpOccupied,
-                dragView, currentState) || minRuns > 0) {
-            minRuns--;
+            // The cluster has been completed, now we move the whole thing over in the appropriate
+            // direction.
+            cluster.shift(whichEdge, 1);
         }
-        boundingRect.union(r0);
+
+        boolean foundSolution = false;
+        clusterRect = cluster.getBoundingRect();
+
+        // Due to the nature of the algorithm, the only check required to verify a valid solution
+        // is to ensure that completed shifted cluster lies completely within the cell layout.
+        if (!fail && clusterRect.left >= 0 && clusterRect.right <= mCountX && clusterRect.top >= 0 &&
+                clusterRect.bottom <= mCountY) {
+            foundSolution = true;
+        } else {
+            currentState.restore();
+        }
+
+        // In either case, we set the occupied array as marked for the location of the views
+        for (View v: cluster.views) {
+            CellAndSpan c = currentState.map.get(v);
+            markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, true);
+        }
+
+        return foundSolution;
     }
 
     private boolean addViewsToTempLocation(ArrayList<View> views, Rect rectOccupiedByPotentialDrop,
-            int[] direction, boolean push, View dragView, ItemConfiguration currentState) {
+            int[] direction, View dragView, ItemConfiguration currentState) {
         if (views.size() == 0) return true;
 
         boolean success = false;
@@ -1735,15 +1920,8 @@ public class CellLayout extends ViewGroup {
             }
         }
 
-        @SuppressWarnings("unchecked")
-        ArrayList<View> dup = (ArrayList<View>) views.clone();
-        if (push) {
-            completeSetOfViewsToMove(dup, boundingRect, direction, mTmpOccupied, dragView,
-                    currentState);
-        }
-
         // Mark the occupied state as false for the group of views we want to move.
-        for (View v: dup) {
+        for (View v: views) {
             CellAndSpan c = currentState.map.get(v);
             markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, false);
         }
@@ -1753,26 +1931,21 @@ public class CellLayout extends ViewGroup {
         int left = boundingRect.left;
         // We mark more precisely which parts of the bounding rect are truly occupied, allowing
         // for interlocking.
-        for (View v: dup) {
+        for (View v: views) {
             CellAndSpan c = currentState.map.get(v);
             markCellsForView(c.x - left, c.y - top, c.spanX, c.spanY, blockOccupied, true);
         }
 
         markCellsForRect(rectOccupiedByPotentialDrop, mTmpOccupied, true);
 
-        if (push) {
-            findNearestAreaInDirection(boundingRect.left, boundingRect.top, boundingRect.width(),
-                    boundingRect.height(), direction, mTmpOccupied, blockOccupied, mTempLocation);
-        } else {
-            findNearestArea(boundingRect.left, boundingRect.top, boundingRect.width(),
-                    boundingRect.height(), direction, mTmpOccupied, blockOccupied, mTempLocation);
-        }
+        findNearestArea(boundingRect.left, boundingRect.top, boundingRect.width(),
+                boundingRect.height(), direction, mTmpOccupied, blockOccupied, mTempLocation);
 
         // If we successfuly found a location by pushing the block of views, we commit it
         if (mTempLocation[0] >= 0 && mTempLocation[1] >= 0) {
             int deltaX = mTempLocation[0] - boundingRect.left;
             int deltaY = mTempLocation[1] - boundingRect.top;
-            for (View v: dup) {
+            for (View v: views) {
                 CellAndSpan c = currentState.map.get(v);
                 c.x += deltaX;
                 c.y += deltaY;
@@ -1781,7 +1954,7 @@ public class CellLayout extends ViewGroup {
         }
 
         // In either case, we set the occupied array as marked for the location of the views
-        for (View v: dup) {
+        for (View v: views) {
             CellAndSpan c = currentState.map.get(v);
             markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, true);
         }
@@ -1802,14 +1975,16 @@ public class CellLayout extends ViewGroup {
             // separately in each of the components.
             int temp = direction[1];
             direction[1] = 0;
-            if (addViewsToTempLocation(intersectingViews, occupied, direction, true,
+
+            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
                     ignoreView, solution)) {
                 return true;
             }
             direction[1] = temp;
             temp = direction[0];
             direction[0] = 0;
-            if (addViewsToTempLocation(intersectingViews, occupied, direction, true,
+
+            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
                     ignoreView, solution)) {
                 return true;
             }
@@ -1821,7 +1996,7 @@ public class CellLayout extends ViewGroup {
             direction[1] *= -1;
             temp = direction[1];
             direction[1] = 0;
-            if (addViewsToTempLocation(intersectingViews, occupied, direction, true,
+            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
                     ignoreView, solution)) {
                 return true;
             }
@@ -1829,7 +2004,7 @@ public class CellLayout extends ViewGroup {
             direction[1] = temp;
             temp = direction[0];
             direction[0] = 0;
-            if (addViewsToTempLocation(intersectingViews, occupied, direction, true,
+            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
                     ignoreView, solution)) {
                 return true;
             }
@@ -1841,15 +2016,14 @@ public class CellLayout extends ViewGroup {
         } else {
             // If the direction vector has a single non-zero component, we push first in the
             // direction of the vector
-            if (addViewsToTempLocation(intersectingViews, occupied, direction, true,
+            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
                     ignoreView, solution)) {
                 return true;
             }
-
             // Then we try the opposite direction
             direction[0] *= -1;
             direction[1] *= -1;
-            if (addViewsToTempLocation(intersectingViews, occupied, direction, true,
+            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
                     ignoreView, solution)) {
                 return true;
             }
@@ -1864,7 +2038,7 @@ public class CellLayout extends ViewGroup {
             int temp = direction[1];
             direction[1] = direction[0];
             direction[0] = temp;
-            if (addViewsToTempLocation(intersectingViews, occupied, direction, true,
+            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
                     ignoreView, solution)) {
                 return true;
             }
@@ -1872,7 +2046,7 @@ public class CellLayout extends ViewGroup {
             // Then we try the opposite direction
             direction[0] *= -1;
             direction[1] *= -1;
-            if (addViewsToTempLocation(intersectingViews, occupied, direction, true,
+            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
                     ignoreView, solution)) {
                 return true;
             }
@@ -1928,7 +2102,7 @@ public class CellLayout extends ViewGroup {
         }
 
         // Next we try moving the views as a block, but without requiring the push mechanic.
-        if (addViewsToTempLocation(mIntersectingViews, mOccupiedRect, direction, false, ignoreView,
+        if (addViewsToTempLocation(mIntersectingViews, mOccupiedRect, direction, ignoreView,
                 solution)) {
             return true;
         }
@@ -2018,7 +2192,7 @@ public class CellLayout extends ViewGroup {
             } else {
                 c = new CellAndSpan(lp.cellX, lp.cellY, lp.cellHSpan, lp.cellVSpan);
             }
-            solution.map.put(child, c);
+            solution.add(child, c);
         }
     }
 
@@ -2490,9 +2664,31 @@ public class CellLayout extends ViewGroup {
 
     private class ItemConfiguration {
         HashMap<View, CellAndSpan> map = new HashMap<View, CellAndSpan>();
+        private HashMap<View, CellAndSpan> savedMap = new HashMap<View, CellAndSpan>();
+        ArrayList<View> sortedViews = new ArrayList<View>();
         boolean isSolution = false;
         int dragViewX, dragViewY, dragViewSpanX, dragViewSpanY;
 
+        void save() {
+            // Copy current state into savedMap
+            for (View v: map.keySet()) {
+                map.get(v).copy(savedMap.get(v));
+            }
+        }
+
+        void restore() {
+            // Restore current state from savedMap
+            for (View v: savedMap.keySet()) {
+                savedMap.get(v).copy(map.get(v));
+            }
+        }
+
+        void add(View v, CellAndSpan cs) {
+            map.put(v, cs);
+            savedMap.put(v, new CellAndSpan());
+            sortedViews.add(v);
+        }
+
         int area() {
             return dragViewSpanX * dragViewSpanY;
         }
@@ -2502,12 +2698,27 @@ public class CellLayout extends ViewGroup {
         int x, y;
         int spanX, spanY;
 
+        public CellAndSpan() {
+        }
+
+        public void copy(CellAndSpan copy) {
+            copy.x = x;
+            copy.y = y;
+            copy.spanX = spanX;
+            copy.spanY = spanY;
+        }
+
         public CellAndSpan(int x, int y, int spanX, int spanY) {
             this.x = x;
             this.y = y;
             this.spanX = spanX;
             this.spanY = spanY;
         }
+
+        public String toString() {
+            return "(" + x + ", " + y + ": " + spanX + ", " + spanY + ")";
+        }
+
     }
 
     /**