From c28de51eedb26848abf9245ddd19e021d30be318 Mon Sep 17 00:00:00 2001 From: Michael Jurka Date: Fri, 13 Aug 2010 11:27:44 -0700 Subject: 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 --- src/com/android/launcher2/CellLayout.java | 332 +++++++++--------------------- src/com/android/launcher2/Launcher.java | 8 +- src/com/android/launcher2/Workspace.java | 55 ++--- 3 files changed, 112 insertions(+), 283 deletions(-) (limited to 'src') 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 @@ public class CellLayout extends ViewGroup { 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 @@ public class CellLayout extends ViewGroup { 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 @@ public class CellLayout extends ViewGroup { 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 @@ public class CellLayout extends ViewGroup { 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 @@ public class CellLayout extends ViewGroup { 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; - - 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.updateOccupiedCells(occupied, mCountX, mCountY); - 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 @@ public class CellLayout extends ViewGroup { 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; - } - - // 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; + 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); + + 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 @@ out: for (int i = x; i < x + spanX - 1 && x < xCount; i++) { } 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 vacantCells = new ArrayList(VacantCell.POOL_LIMIT); - int maxVacantSpanX; - int maxVacantSpanXSpanY; - int maxVacantSpanY; - int maxVacantSpanYSpanX; - final Rect current = new Rect(); - - void clearVacantCells() { - final ArrayList 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 @@ out: for (int i = x; i < x + spanX - 1 && x < xCount; i++) { * @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 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; - } - // 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; + if (this.cell == null && this.spanX >= spanX && this.spanY >= spanY) { + if (cellXY != null) { + cellXY[0] = cellX; + cellXY[1] = cellY; } + 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; - } + int startX = 0; + if (intersectX >= 0) { + startX = Math.max(startX, intersectX - (spanX - 1)); } - - if (clear) { - clearVacantCells(); + 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)); } - return found; + 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; + } + } + 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 @@ public final class Launcher extends Activity 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 @@ public final class Launcher extends Activity // 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 @@ public final class Launcher extends Activity // 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 @@ public final class Launcher extends Activity 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.View; 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 @@ public class Workspace extends ViewGroup 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 @@ public class Workspace extends ViewGroup 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 @@ public class Workspace extends ViewGroup return; } - clearVacantCache(); - final CellLayout group = (CellLayout) getChildAt(screen); CellLayout.LayoutParams lp = (CellLayout.LayoutParams) child.getLayoutParams(); if (lp == null) { @@ -467,21 +456,14 @@ public class Workspace extends ViewGroup } } - 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 @@ public class Workspace extends ViewGroup whichScreen = Math.max(0, Math.min(whichScreen, getChildCount() - 1)); - clearVacantCache(); enableChildrenCache(mCurrentScreen, whichScreen); mNextScreen = whichScreen; @@ -1349,7 +1330,6 @@ public class Workspace extends ViewGroup 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 class Workspace extends ViewGroup 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 class Workspace extends ViewGroup 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 @@ public class Workspace extends ViewGroup 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 class Workspace extends ViewGroup } 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 class Workspace extends ViewGroup } public void scrollLeft() { - clearVacantCache(); if (mScroller.isFinished()) { if (mCurrentScreen > 0) snapToScreen(mCurrentScreen - 1); @@ -1623,7 +1593,6 @@ public class Workspace extends ViewGroup } public void scrollRight() { - clearVacantCache(); if (mScroller.isFinished()) { if (mCurrentScreen < getChildCount() - 1) snapToScreen(mCurrentScreen + 1); -- cgit v1.1