fixed crash in addVacantCell
No longer precalculating vacant cells
The previous way of finding empty cells for
widgets/icons etc. precalculated all the possible
empty spaces. Now that we have an 8x7 grid in
tablet, there are too many possible empty spaces.
Change-Id: Ib39113fdf755935bfad257843e1618c680ed9e72
diff --git a/src/com/android/launcher2/CellLayout.java b/src/com/android/launcher2/CellLayout.java
index 2488e6e..e86b305 100644
--- a/src/com/android/launcher2/CellLayout.java
+++ b/src/com/android/launcher2/CellLayout.java
@@ -267,6 +267,8 @@
cellInfo.cellY = lp.cellY;
cellInfo.spanX = lp.cellHSpan;
cellInfo.spanY = lp.cellVSpan;
+ cellInfo.intersectX = lp.cellX;
+ cellInfo.intersectY = lp.cellY;
cellInfo.valid = true;
found = true;
mDirtyTag = false;
@@ -293,6 +295,8 @@
cellInfo.cellY = cellXY[1];
cellInfo.spanX = 1;
cellInfo.spanY = 1;
+ cellInfo.intersectX = cellXY[0];
+ cellInfo.intersectY = cellXY[1];
cellInfo.valid = cellXY[0] >= 0 && cellXY[1] >= 0 && cellXY[0] < xCount &&
cellXY[1] < yCount && !occupied[cellXY[0]][cellXY[1]];
@@ -341,86 +345,13 @@
final boolean[][] occupied = mOccupied;
findOccupiedCells(xCount, yCount, occupied, null, true);
- findIntersectingVacantCells(info, info.cellX, info.cellY, xCount, yCount, occupied);
+ info.updateOccupiedCells(occupied, mCountX, mCountY);
mDirtyTag = false;
}
return info;
}
- private static void findIntersectingVacantCells(CellInfo cellInfo, int x,
- int y, int xCount, int yCount, boolean[][] occupied) {
-
- cellInfo.maxVacantSpanX = Integer.MIN_VALUE;
- cellInfo.maxVacantSpanXSpanY = Integer.MIN_VALUE;
- cellInfo.maxVacantSpanY = Integer.MIN_VALUE;
- cellInfo.maxVacantSpanYSpanX = Integer.MIN_VALUE;
- cellInfo.clearVacantCells();
-
- if (occupied[x][y]) {
- return;
- }
-
- cellInfo.current.set(x, y, x, y);
-
- findVacantCell(cellInfo.current, xCount, yCount, occupied, cellInfo);
- }
-
- private static void findVacantCell(Rect current, int xCount, int yCount, boolean[][] occupied,
- CellInfo cellInfo) {
-
- addVacantCell(current, cellInfo);
-
- if (current.left > 0) {
- if (isColumnEmpty(current.left - 1, current.top, current.bottom, occupied)) {
- current.left--;
- findVacantCell(current, xCount, yCount, occupied, cellInfo);
- current.left++;
- }
- }
-
- if (current.right < xCount - 1) {
- if (isColumnEmpty(current.right + 1, current.top, current.bottom, occupied)) {
- current.right++;
- findVacantCell(current, xCount, yCount, occupied, cellInfo);
- current.right--;
- }
- }
-
- if (current.top > 0) {
- if (isRowEmpty(current.top - 1, current.left, current.right, occupied)) {
- current.top--;
- findVacantCell(current, xCount, yCount, occupied, cellInfo);
- current.top++;
- }
- }
-
- if (current.bottom < yCount - 1) {
- if (isRowEmpty(current.bottom + 1, current.left, current.right, occupied)) {
- current.bottom++;
- findVacantCell(current, xCount, yCount, occupied, cellInfo);
- current.bottom--;
- }
- }
- }
-
- private static void addVacantCell(Rect current, CellInfo cellInfo) {
- CellInfo.VacantCell cell = CellInfo.VacantCell.acquire();
- cell.cellX = current.left;
- cell.cellY = current.top;
- cell.spanX = current.right - current.left + 1;
- cell.spanY = current.bottom - current.top + 1;
- if (cell.spanX > cellInfo.maxVacantSpanX) {
- cellInfo.maxVacantSpanX = cell.spanX;
- cellInfo.maxVacantSpanXSpanY = cell.spanY;
- }
- if (cell.spanY > cellInfo.maxVacantSpanY) {
- cellInfo.maxVacantSpanY = cell.spanY;
- cellInfo.maxVacantSpanYSpanX = cell.spanX;
- }
- cellInfo.vacantCells.add(cell);
- }
-
/**
* Check if the column 'x' is empty from rows 'top' to 'bottom', inclusive.
*/
@@ -445,7 +376,7 @@
return true;
}
- CellInfo findAllVacantCells(boolean[] occupiedCells, View ignoreView) {
+ CellInfo updateOccupiedCells(boolean[] occupiedCells, View ignoreView) {
final int xCount = mCountX;
final int yCount = mCountY;
@@ -465,27 +396,15 @@
cellInfo.cellX = -1;
cellInfo.cellY = -1;
+ cellInfo.intersectX = -1;
+ cellInfo.intersectY = -1;
cellInfo.spanY = 0;
cellInfo.spanX = 0;
- cellInfo.maxVacantSpanX = Integer.MIN_VALUE;
- cellInfo.maxVacantSpanXSpanY = Integer.MIN_VALUE;
- cellInfo.maxVacantSpanY = Integer.MIN_VALUE;
- cellInfo.maxVacantSpanYSpanX = Integer.MIN_VALUE;
cellInfo.screen = mCellInfo.screen;
- Rect current = cellInfo.current;
+ cellInfo.updateOccupiedCells(occupied, mCountX, mCountY);
- for (int x = 0; x < xCount; x++) {
- for (int y = 0; y < yCount; y++) {
- if (!occupied[x][y]) {
- current.set(x, y, x, y);
- findVacantCell(current, xCount, yCount, occupied, cellInfo);
- occupied[x][y] = true;
- }
- }
- }
-
- cellInfo.valid = cellInfo.vacantCells.size() > 0;
+ cellInfo.valid = cellInfo.existsEmptyCell();
// Assume the caller will perform their own cell searching, otherwise we
// risk causing an unnecessary rebuild after findCellForSpan()
@@ -837,31 +756,29 @@
final int[] bestXY = recycle != null ? recycle : new int[2];
double bestDistance = Double.MAX_VALUE;
- // Bail early if vacant cells aren't valid
- if (!vacantCells.valid) {
- return null;
- }
+ for (int x = 0; x < mCountX - (spanX - 1); x++) {
+ inner:
+ for (int y = 0; y < mCountY - (spanY - 1); y++) {
+ for (int i = 0; i < spanX; i++) {
+ for (int j = 0; j < spanY; j++) {
+ if (mOccupied[x + i][y + j]) {
+ // small optimization: we can skip to below the row we just found
+ // an occupied cell
+ y += j;
+ continue inner;
+ }
+ }
+ }
+ final int[] cellXY = mTmpCellXY;
+ cellToPoint(x, y, cellXY);
- // Look across all vacant cells for best fit
- final int size = vacantCells.vacantCells.size();
- for (int i = 0; i < size; i++) {
- final CellInfo.VacantCell cell = vacantCells.vacantCells.get(i);
-
- // Reject if vacant cell isn't our exact size
- if (cell.spanX != spanX || cell.spanY != spanY) {
- continue;
- }
-
- // Score is distance from requested pixel to the top left of each cell
- final int[] cellXY = mTmpCellXY;
- cellToPoint(cell.cellX, cell.cellY, cellXY);
-
- double distance = Math.sqrt(Math.pow(cellXY[0] - pixelX, 2)
- + Math.pow(cellXY[1] - pixelY, 2));
- if (distance <= bestDistance) {
- bestDistance = distance;
- bestXY[0] = cell.cellX;
- bestXY[1] = cell.cellY;
+ double distance = Math.sqrt(Math.pow(cellXY[0] - pixelX, 2)
+ + Math.pow(cellXY[1] - pixelY, 2));
+ if (distance <= bestDistance) {
+ bestDistance = distance;
+ bestXY[0] = x;
+ bestXY[1] = y;
+ }
}
}
@@ -1183,110 +1100,48 @@
}
static final class CellInfo implements ContextMenu.ContextMenuInfo {
- /**
- * See View.AttachInfo.InvalidateInfo for futher explanations about the
- * recycling mechanism. In this case, we recycle the vacant cells
- * instances because up to several hundreds can be instanciated when the
- * user long presses an empty cell.
- */
- static final class VacantCell {
- int cellX;
- int cellY;
- int spanX;
- int spanY;
-
- // We can create up to 523 vacant cells on a 4x4 grid, 100 seems
- // like a reasonable compromise given the size of a VacantCell and
- // the fact that the user is not likely to touch an empty 4x4 grid
- // very often
- private static final int POOL_LIMIT = 100;
- private static final Object sLock = new Object();
-
- private static int sAcquiredCount = 0;
- private static VacantCell sRoot;
-
- private VacantCell next;
-
- static VacantCell acquire() {
- synchronized (sLock) {
- if (sRoot == null) {
- return new VacantCell();
- }
-
- VacantCell info = sRoot;
- sRoot = info.next;
- sAcquiredCount--;
-
- return info;
- }
- }
-
- void release() {
- synchronized (sLock) {
- if (sAcquiredCount < POOL_LIMIT) {
- sAcquiredCount++;
- next = sRoot;
- sRoot = this;
- }
- }
- }
-
- @Override
- public String toString() {
- return "VacantCell[x=" + cellX + ", y=" + cellY + ", spanX="
- + spanX + ", spanY=" + spanY + "]";
- }
- }
-
+ private boolean[][] mOccupied;
+ private int mCountX;
+ private int mCountY;
View cell;
int cellX;
int cellY;
+ // intersectX and intersectY constrain the results of findCellForSpan; any empty space
+ // it results must include this point (unless intersectX and intersectY are -1)
+ int intersectX;
+ int intersectY;
int spanX;
int spanY;
int screen;
boolean valid;
- final ArrayList<VacantCell> vacantCells = new ArrayList<VacantCell>(VacantCell.POOL_LIMIT);
- int maxVacantSpanX;
- int maxVacantSpanXSpanY;
- int maxVacantSpanY;
- int maxVacantSpanYSpanX;
- final Rect current = new Rect();
-
- void clearVacantCells() {
- final ArrayList<VacantCell> list = vacantCells;
- final int count = list.size();
-
- for (int i = 0; i < count; i++) {
- list.get(i).release();
- }
-
- list.clear();
+ void updateOccupiedCells(boolean[][] occupied, int xCount, int yCount) {
+ mOccupied = occupied.clone();
+ mCountX = xCount;
+ mCountY = yCount;
}
- void findVacantCellsFromOccupied(boolean[] occupied, int xCount, int yCount) {
- if (cellX < 0 || cellY < 0) {
- maxVacantSpanX = maxVacantSpanXSpanY = Integer.MIN_VALUE;
- maxVacantSpanY = maxVacantSpanYSpanX = Integer.MIN_VALUE;
- clearVacantCells();
- return;
+ void updateOccupiedCells(boolean[] occupied, int xCount, int yCount) {
+ if (mOccupied == null || mCountX != xCount || mCountY != yCount) {
+ mOccupied = new boolean[xCount][yCount];
}
-
- final boolean[][] unflattened = new boolean[xCount][yCount];
+ mCountX = xCount;
+ mCountY = yCount;
for (int y = 0; y < yCount; y++) {
for (int x = 0; x < xCount; x++) {
- unflattened[x][y] = occupied[y * xCount + x];
+ mOccupied[x][y] = occupied[y * xCount + x];
}
}
- CellLayout.findIntersectingVacantCells(this, cellX, cellY, xCount, yCount, unflattened);
}
+ boolean existsEmptyCell() {
+ return findCellForSpan(null, 1, 1);
+ }
/**
- * This method can be called only once! Calling #findVacantCellsFromOccupied will
- * restore the ability to call this method.
- *
* Finds the upper-left coordinate of the first rectangle in the grid that can
- * hold a cell of the specified dimensions.
+ * hold a cell of the specified dimensions. If intersectX and intersectY are not -1,
+ * then this method will only return coordinates for rectangles that contain the cell
+ * (intersectX, intersectY)
*
* @param cellXY The array that will contain the position of a vacant cell if such a cell
* can be found.
@@ -1296,50 +1151,55 @@
* @return True if a vacant cell of the specified dimension was found, false otherwise.
*/
boolean findCellForSpan(int[] cellXY, int spanX, int spanY) {
- return findCellForSpan(cellXY, spanX, spanY, true);
- }
-
- boolean findCellForSpan(int[] cellXY, int spanX, int spanY, boolean clear) {
- final ArrayList<VacantCell> list = vacantCells;
- final int count = list.size();
-
- boolean found = false;
-
// return the span represented by the CellInfo only there is no view there
// (this.cell == null) and there is enough space
+
if (this.cell == null && this.spanX >= spanX && this.spanY >= spanY) {
- cellXY[0] = cellX;
- cellXY[1] = cellY;
- found = true;
+ if (cellXY != null) {
+ cellXY[0] = cellX;
+ cellXY[1] = cellY;
+ }
+ return true;
}
- // Look for an exact match first
- for (int i = 0; i < count; i++) {
- VacantCell cell = list.get(i);
- if (cell.spanX == spanX && cell.spanY == spanY) {
- cellXY[0] = cell.cellX;
- cellXY[1] = cell.cellY;
- found = true;
- break;
+ int startX = 0;
+ if (intersectX >= 0) {
+ startX = Math.max(startX, intersectX - (spanX - 1));
+ }
+ int endX = mCountX - (spanX - 1);
+ if (intersectX >= 0) {
+ endX = Math.min(endX, intersectX + (spanX - 1));
+ }
+ int startY = 0;
+ if (intersectY >= 0) {
+ startY = Math.max(startY, intersectY - (spanY - 1));
+ }
+ int endY = mCountY - (spanY - 1);
+ if (intersectY >= 0) {
+ endY = Math.min(endY, intersectY + (spanY - 1));
+ }
+
+ for (int x = startX; x < endX + 1; x++) {
+ inner:
+ for (int y = startY; y < endY; y++) {
+ for (int i = 0; i < spanX; i++) {
+ for (int j = 0; j < spanY; j++) {
+ if (mOccupied[x + i][y + j]) {
+ // small optimization: we can skip to below the row we just found
+ // an occupied cell
+ y += j;
+ continue inner;
+ }
+ }
+ }
+ if (cellXY != null) {
+ cellXY[0] = x;
+ cellXY[1] = y;
+ }
+ return true;
}
}
-
- // Look for the first cell large enough
- for (int i = 0; i < count; i++) {
- VacantCell cell = list.get(i);
- if (cell.spanX >= spanX && cell.spanY >= spanY) {
- cellXY[0] = cell.cellX;
- cellXY[1] = cell.cellY;
- found = true;
- break;
- }
- }
-
- if (clear) {
- clearVacantCells();
- }
-
- return found;
+ return false;
}
@Override
diff --git a/src/com/android/launcher2/Launcher.java b/src/com/android/launcher2/Launcher.java
index d7ce6f2..ccd6f65 100644
--- a/src/com/android/launcher2/Launcher.java
+++ b/src/com/android/launcher2/Launcher.java
@@ -722,7 +722,7 @@
addItemCellInfo.cellY = savedState.getInt(RUNTIME_STATE_PENDING_ADD_CELL_Y);
addItemCellInfo.spanX = savedState.getInt(RUNTIME_STATE_PENDING_ADD_SPAN_X);
addItemCellInfo.spanY = savedState.getInt(RUNTIME_STATE_PENDING_ADD_SPAN_Y);
- addItemCellInfo.findVacantCellsFromOccupied(
+ addItemCellInfo.updateOccupiedCells(
savedState.getBooleanArray(RUNTIME_STATE_PENDING_ADD_OCCUPIED_CELLS),
savedState.getInt(RUNTIME_STATE_PENDING_ADD_COUNT_X),
savedState.getInt(RUNTIME_STATE_PENDING_ADD_COUNT_Y));
@@ -1229,7 +1229,7 @@
// Disable add if the workspace is full.
if (visible) {
- mMenuAddInfo = mWorkspace.findAllVacantCells(null);
+ mMenuAddInfo = mWorkspace.updateOccupiedCells(null);
menu.setGroupEnabled(MENU_GROUP_ADD, mMenuAddInfo != null && mMenuAddInfo.valid);
}
@@ -1239,7 +1239,7 @@
// we need to initialize mAddItemCellInfo before adding something to the homescreen -- when
// using the settings menu to add an item, something similar happens in showAddDialog
public void prepareAddItemFromHomeCustomizationDrawer() {
- mMenuAddInfo = mWorkspace.findAllVacantCells(null);
+ mMenuAddInfo = mWorkspace.updateOccupiedCells(null);
mAddItemCellInfo = mMenuAddInfo;
}
@@ -1447,7 +1447,7 @@
if (!cellInfo.findCellForSpan(xy, spanX, spanY)) {
boolean[] occupied = mSavedState != null ?
mSavedState.getBooleanArray(RUNTIME_STATE_PENDING_ADD_OCCUPIED_CELLS) : null;
- cellInfo = mWorkspace.findAllVacantCells(occupied);
+ cellInfo = mWorkspace.updateOccupiedCells(occupied);
if (!cellInfo.findCellForSpan(xy, spanX, spanY)) {
Toast.makeText(this, getString(R.string.out_of_space), Toast.LENGTH_SHORT).show();
return false;
diff --git a/src/com/android/launcher2/Workspace.java b/src/com/android/launcher2/Workspace.java
index bc3285d..aa74f70 100644
--- a/src/com/android/launcher2/Workspace.java
+++ b/src/com/android/launcher2/Workspace.java
@@ -17,13 +17,12 @@
package com.android.launcher2;
import com.android.launcher.R;
+import com.android.launcher2.CellLayout.CellInfo;
import android.animation.Animatable;
-import android.animation.Animatable.AnimatableListener;
-import android.animation.Animator;
-import android.animation.Animator.AnimatorUpdateListener;
import android.animation.PropertyAnimator;
import android.animation.Sequencer;
+import android.animation.Animatable.AnimatableListener;
import android.app.WallpaperManager;
import android.appwidget.AppWidgetManager;
import android.appwidget.AppWidgetProviderInfo;
@@ -50,10 +49,7 @@
import android.view.ViewConfiguration;
import android.view.ViewGroup;
import android.view.ViewParent;
-import android.view.animation.Animation;
-import android.view.animation.Animation.AnimationListener;
import android.view.animation.Interpolator;
-import android.view.animation.RotateAnimation;
import android.widget.Scroller;
import android.widget.TextView;
import android.widget.Toast;
@@ -122,10 +118,6 @@
private IconCache mIconCache;
private DragController mDragController;
- /**
- * Cache of vacant cells, used during drag events and invalidated as needed.
- */
- private CellLayout.CellInfo mVacantCache = null;
private int[] mTempCell = new int[2];
private int[] mTempEstimate = new int[2];
@@ -354,7 +346,6 @@
void setCurrentScreen(int currentScreen, boolean animateScrolling, int screenWidth) {
if (!mScroller.isFinished())
mScroller.abortAnimation();
- clearVacantCache();
mCurrentScreen = Math.max(0, Math.min(currentScreen, getChildCount() - 1));
if (mPreviousIndicator != null) {
mPreviousIndicator.setLevel(mCurrentScreen);
@@ -436,8 +427,6 @@
return;
}
- clearVacantCache();
-
final CellLayout group = (CellLayout) getChildAt(screen);
CellLayout.LayoutParams lp = (CellLayout.LayoutParams) child.getLayoutParams();
if (lp == null) {
@@ -467,21 +456,14 @@
}
}
- CellLayout.CellInfo findAllVacantCells(boolean[] occupied) {
+ CellLayout.CellInfo updateOccupiedCells(boolean[] occupied) {
CellLayout group = (CellLayout) getChildAt(mCurrentScreen);
if (group != null) {
- return group.findAllVacantCells(occupied, null);
+ return group.updateOccupiedCells(occupied, null);
}
return null;
}
- private void clearVacantCache() {
- if (mVacantCache != null) {
- mVacantCache.clearVacantCells();
- mVacantCache = null;
- }
- }
-
public boolean onTouch(View v, MotionEvent event) {
// this is an intercepted event being forwarded from a cell layout
if (mIsSmall) {
@@ -1220,7 +1202,6 @@
whichScreen = Math.max(0, Math.min(whichScreen, getChildCount() - 1));
- clearVacantCache();
enableChildrenCache(mCurrentScreen, whichScreen);
mNextScreen = whichScreen;
@@ -1349,7 +1330,6 @@
public void onDragEnter(DragSource source, int x, int y, int xOffset,
int yOffset, DragView dragView, Object dragInfo) {
- clearVacantCache();
}
public DropTarget getDropTargetDelegate(DragSource source, int x, int y, int xOffset, int yOffset,
@@ -1431,7 +1411,6 @@
public void onDragExit(DragSource source, int x, int y, int xOffset,
int yOffset, DragView dragView, Object dragInfo) {
- clearVacantCache();
if (mDragTargetLayout != null) {
mDragTargetLayout.onDragComplete();
mDragTargetLayout = null;
@@ -1505,16 +1484,14 @@
public boolean acceptDrop(DragSource source, int x, int y,
int xOffset, int yOffset, DragView dragView, Object dragInfo) {
final CellLayout layout = getCurrentDropLayout();
- final CellLayout.CellInfo cellInfo = mDragInfo;
- final int spanX = cellInfo == null ? 1 : cellInfo.spanX;
- final int spanY = cellInfo == null ? 1 : cellInfo.spanY;
+ final CellLayout.CellInfo dragCellInfo = mDragInfo;
+ final int spanX = dragCellInfo == null ? 1 : dragCellInfo.spanX;
+ final int spanY = dragCellInfo == null ? 1 : dragCellInfo.spanY;
- if (mVacantCache == null) {
- final View ignoreView = cellInfo == null ? null : cellInfo.cell;
- mVacantCache = layout.findAllVacantCells(null, ignoreView);
- }
+ final View ignoreView = dragCellInfo == null ? null : dragCellInfo.cell;
+ final CellLayout.CellInfo cellInfo = layout.updateOccupiedCells(null, ignoreView);
- if (mVacantCache.findCellForSpan(mTempEstimate, spanX, spanY, false)) {
+ if (cellInfo.findCellForSpan(mTempEstimate, spanX, spanY)) {
return true;
} else {
Toast.makeText(getContext(), getContext().getString(R.string.out_of_space), Toast.LENGTH_SHORT).show();
@@ -1565,13 +1542,9 @@
layout.estimateDropCell(pixelX, pixelY, spanX, spanY, cellXY);
layout.cellToPoint(cellXY[0], cellXY[1], mTempEstimate);
- // Create vacant cell cache if none exists
- if (mVacantCache == null) {
- mVacantCache = layout.findAllVacantCells(null, ignoreView);
- }
-
+ final CellLayout.CellInfo cellInfo = layout.updateOccupiedCells(null, ignoreView);
// Find the best target drop location
- return layout.findNearestVacantArea(mTempEstimate[0], mTempEstimate[1], spanX, spanY, mVacantCache, recycle);
+ return layout.findNearestVacantArea(mTempEstimate[0], mTempEstimate[1], spanX, spanY, cellInfo, recycle);
}
/**
@@ -1590,8 +1563,6 @@
}
public void onDropCompleted(View target, boolean success) {
- clearVacantCache();
-
if (success) {
if (target != this && mDragInfo != null) {
final CellLayout cellLayout = (CellLayout) getChildAt(mDragInfo.screen);
@@ -1612,7 +1583,6 @@
}
public void scrollLeft() {
- clearVacantCache();
if (mScroller.isFinished()) {
if (mCurrentScreen > 0)
snapToScreen(mCurrentScreen - 1);
@@ -1623,7 +1593,6 @@
}
public void scrollRight() {
- clearVacantCache();
if (mScroller.isFinished()) {
if (mCurrentScreen < getChildCount() - 1)
snapToScreen(mCurrentScreen + 1);