From f3900c287cd92f61863cbecab87d5513e48b7b09 Mon Sep 17 00:00:00 2001 From: Adam Cohen Date: Fri, 16 Nov 2012 18:28:11 -0800 Subject: 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 --- src/com/android/launcher2/CellLayout.java | 521 +++++++++++++++++++++--------- 1 file changed, 366 insertions(+), 155 deletions(-) (limited to 'src') 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 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 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 views, ItemConfiguration config) { + this.views = (ArrayList) 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 { + 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 views, Rect boundingRect, int[] direction, - boolean[][] occupied, View dragView, ItemConfiguration currentState) { - Rect r0 = new Rect(boundingRect); - int minRuns = 0; + private boolean pushViewsToTempLocation(ArrayList 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 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 dup = (ArrayList) 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 map = new HashMap(); + private HashMap savedMap = new HashMap(); + ArrayList sortedViews = new ArrayList(); 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 + ")"; + } + } /** -- cgit v1.2.3