Initial implementation of CellLayout auto-reordering

Change-Id: Id5b5080e846907a7d9cd6535f6e7285e83a0ff71

5 files changed, 836 insertions, 158 deletions

diff --git a/src/com/android/launcher2/CellLayout.java b/src/com/android/launcher2/CellLayout.java
index 528984a59..d30940e7d 100644
--- a/src/com/android/launcher2/CellLayout.java
+++ b/src/com/android/launcher2/CellLayout.java
@@ -35,6 +35,7 @@ import android.graphics.PointF;
 import android.graphics.PorterDuff;
 import android.graphics.PorterDuffXfermode;
 import android.graphics.Rect;
+import android.graphics.drawable.ColorDrawable;
 import android.graphics.drawable.Drawable;
 import android.graphics.drawable.NinePatchDrawable;
 import android.util.AttributeSet;
@@ -84,6 +85,7 @@ public class CellLayout extends ViewGroup {
     int[] mTempLocation = new int[2];
 
     boolean[][] mOccupied;
+    boolean[][] mTmpOccupied;
     private boolean mLastDownOnOccupiedCell = false;
 
     private OnTouchListener mInterceptTouchListener;
@@ -125,13 +127,14 @@ public class CellLayout extends ViewGroup {
     private InterruptibleInOutAnimator mCrosshairsAnimator = null;
     private float mCrosshairsVisibility = 0.0f;
 
-    private HashMap<CellLayout.LayoutParams, ObjectAnimator> mReorderAnimators = new
-            HashMap<CellLayout.LayoutParams, ObjectAnimator>();
+    private HashMap<CellLayout.LayoutParams, Animator> mReorderAnimators = new
+            HashMap<CellLayout.LayoutParams, Animator>();
 
     // When a drag operation is in progress, holds the nearest cell to the touch point
     private final int[] mDragCell = new int[2];
 
     private boolean mDragging = false;
+    private boolean mItemLocationsDirty = false;
 
     private TimeInterpolator mEaseOutInterpolator;
     private CellLayoutChildren mChildren;
@@ -140,6 +143,17 @@ public class CellLayout extends ViewGroup {
     private float mChildScale = 1f;
     private float mHotseatChildScale = 1f;
 
+    public static final int MODE_DRAG_OVER = 0;
+    public static final int MODE_ON_DROP = 1;
+    public static final int MODE_ON_DROP_EXTERNAL = 2;
+    public static final int MODE_ACCEPT_DROP = 3;
+    private static final boolean DESTRUCTIVE_REORDER = true;
+    private static final boolean DEBUG_VISUALIZE_OCCUPIED = false;
+
+    private ArrayList<View> mIntersectingViews = new ArrayList<View>();
+    private Rect mOccupiedRect = new Rect();
+    private int[] mDirectionVector = new int[2];
+
     public CellLayout(Context context) {
         this(context, null);
     }
@@ -167,6 +181,7 @@ public class CellLayout extends ViewGroup {
         mCountX = LauncherModel.getCellCountX();
         mCountY = LauncherModel.getCellCountY();
         mOccupied = new boolean[mCountX][mCountY];
+        mTmpOccupied = new boolean[mCountX][mCountY];
 
         a.recycle();
 
@@ -301,6 +316,7 @@ public class CellLayout extends ViewGroup {
         mCountX = x;
         mCountY = y;
         mOccupied = new boolean[mCountX][mCountY];
+        mTmpOccupied = new boolean[mCountX][mCountY];
         requestLayout();
     }
 
@@ -450,6 +466,23 @@ public class CellLayout extends ViewGroup {
             }
         }
 
+        if (DEBUG_VISUALIZE_OCCUPIED) {
+            int[] pt = new int[2];
+            ColorDrawable cd = new ColorDrawable(Color.RED);
+            cd.setBounds(0, 0, 80, 80);
+            for (int i = 0; i < mCountX; i++) {
+                for (int j = 0; j < mCountY; j++) {
+                    if (mOccupied[i][j]) {
+                        cellToPoint(i, j, pt);
+                        canvas.save();
+                        canvas.translate(pt[0], pt[1]);
+                        cd.draw(canvas);
+                        canvas.restore();
+                    }
+                }
+            }
+        }
+
         // The folder outer / inner ring image(s)
         for (int i = 0; i < mFolderOuterRings.size(); i++) {
             FolderRingAnimator fra = mFolderOuterRings.get(i);
@@ -847,7 +880,7 @@ public class CellLayout extends ViewGroup {
     }
 
     /**
-     * Given a cell coordinate, return the point that represents the upper left corner of that cell
+     * Given a cell coordinate, return the point that represents the center of the cell
      *
      * @param cellX X coordinate of the cell
      * @param cellY Y coordinate of the cell
@@ -862,6 +895,13 @@ public class CellLayout extends ViewGroup {
         result[1] = vStartPadding + cellY * (mCellHeight + mHeightGap) + mCellHeight / 2;
     }
 
+    public float getDistanceFromCell(float x, float y, int[] cell) {
+        cellToCenterPoint(cell[0], cell[1], mTmpPoint);
+        float distance = (float) Math.sqrt( Math.pow(x - mTmpPoint[0], 2) +
+                Math.pow(y - mTmpPoint[1], 2));
+        return distance;
+    }
+
     int getCellWidth() {
         return mCellWidth;
     }
@@ -1016,9 +1056,14 @@ public class CellLayout extends ViewGroup {
     }
 
     public boolean animateChildToPosition(final View child, int cellX, int cellY, int duration,
-            int delay) {
+            int delay, boolean permanent, boolean adjustOccupied) {
         CellLayoutChildren clc = getChildrenLayout();
-        if (clc.indexOfChild(child) != -1 && !mOccupied[cellX][cellY]) {
+        boolean[][] occupied = mOccupied;
+        if (!permanent) {
+            occupied = mTmpOccupied;
+        }
+
+        if (clc.indexOfChild(child) != -1 && !occupied[cellX][cellY]) {
             final LayoutParams lp = (LayoutParams) child.getLayoutParams();
             final ItemInfo info = (ItemInfo) child.getTag();
 
@@ -1028,41 +1073,57 @@ public class CellLayout extends ViewGroup {
                 mReorderAnimators.remove(lp);
             }
 
-            int oldX = lp.x;
-            int oldY = lp.y;
-            mOccupied[lp.cellX][lp.cellY] = false;
-            mOccupied[cellX][cellY] = true;
-
+            final int oldX = lp.x;
+            final int oldY = lp.y;
+            if (adjustOccupied) {
+                occupied[lp.cellX][lp.cellY] = false;
+                occupied[cellX][cellY] = true;
+            }
             lp.isLockedToGrid = true;
-            lp.cellX = info.cellX = cellX;
-            lp.cellY = info.cellY = cellY;
+            if (permanent) {
+                lp.cellX = info.cellX = cellX;
+                lp.cellY = info.cellY = cellY;
+            } else {
+                lp.tmpCellX = cellX;
+                lp.tmpCellY = cellY;
+            }
             clc.setupLp(lp);
             lp.isLockedToGrid = false;
-            int newX = lp.x;
-            int newY = lp.y;
+            final int newX = lp.x;
+            final int newY = lp.y;
 
             lp.x = oldX;
             lp.y = oldY;
-            child.requestLayout();
 
-            PropertyValuesHolder x = PropertyValuesHolder.ofInt("x", oldX, newX);
-            PropertyValuesHolder y = PropertyValuesHolder.ofInt("y", oldY, newY);
-            ObjectAnimator oa = ObjectAnimator.ofPropertyValuesHolder(lp, x, y);
-            oa.setDuration(duration);
-            mReorderAnimators.put(lp, oa);
-            oa.addUpdateListener(new AnimatorUpdateListener() {
+            // Exit early if we're not actually moving the view
+            if (oldX == newX && oldY == newY) {
+                lp.isLockedToGrid = true;
+                return true;
+            }
+
+            ValueAnimator va = ValueAnimator.ofFloat(0f, 1f);
+            va.setDuration(duration);
+            mReorderAnimators.put(lp, va);
+
+            va.addUpdateListener(new AnimatorUpdateListener() {
+                @Override
                 public void onAnimationUpdate(ValueAnimator animation) {
-                    child.requestLayout();
+                    float r = ((Float) animation.getAnimatedValue()).floatValue();
+                    child.setTranslationX(r * (newX - oldX));
+                    child.setTranslationY(r * (newY - oldY));
                 }
             });
-            oa.addListener(new AnimatorListenerAdapter() {
+            va.addListener(new AnimatorListenerAdapter() {
                 boolean cancelled = false;
                 public void onAnimationEnd(Animator animation) {
                     // If the animation was cancelled, it means that another animation
                     // has interrupted this one, and we don't want to lock the item into
                     // place just yet.
                     if (!cancelled) {
+                        child.setTranslationX(0);
+                        child.setTranslationY(0);
                         lp.isLockedToGrid = true;
+                        child.requestLayout();
                     }
                     if (mReorderAnimators.containsKey(lp)) {
                         mReorderAnimators.remove(lp);
@@ -1072,8 +1133,8 @@ public class CellLayout extends ViewGroup {
                     cancelled = true;
                 }
             });
-            oa.setStartDelay(delay);
-            oa.start();
+            va.setStartDelay(delay);
+            va.start();
             return true;
         }
         return false;
@@ -1109,17 +1170,11 @@ public class CellLayout extends ViewGroup {
         result[1] = Math.max(0, result[1]); // Snap to top
     }
 
-    void visualizeDropLocation(View v, Bitmap dragOutline, int originX, int originY,
-            int minSpanX, int minSpanY, int spanX, int spanY, Point dragOffset, Rect dragRegion) {
-
+    void visualizeDropLocation(View v, Bitmap dragOutline, int originX, int originY, int cellX,
+            int cellY, int spanX, int spanY, boolean resize, Point dragOffset, Rect dragRegion) {
         final int oldDragCellX = mDragCell[0];
         final int oldDragCellY = mDragCell[1];
-        int[] resultSpan = new int[2];
-        final int[] nearest = findNearestVacantArea(originX, originY, minSpanX, minSpanY,
-                spanX, spanY, v, mDragCell, resultSpan);
-        boolean resize = spanX > resultSpan[0] || spanY > resultSpan[1];
-        spanX = resultSpan[0];
-        spanY = resultSpan[1];
+
         if (v != null && dragOffset == null) {
             mDragCenter.set(originX + (v.getWidth() / 2), originY + (v.getHeight() / 2));
         } else {
@@ -1133,10 +1188,12 @@ public class CellLayout extends ViewGroup {
             return;
         }
 
-        if (nearest != null && (nearest[0] != oldDragCellX || nearest[1] != oldDragCellY)) {
+        if (cellX != oldDragCellX || cellY != oldDragCellY) {
+            mDragCell[0] = cellX;
+            mDragCell[1] = cellY;
             // Find the top left corner of the rect the object will occupy
             final int[] topLeft = mTmpPoint;
-            cellToPoint(nearest[0], nearest[1], topLeft);
+            cellToPoint(cellX, cellY, topLeft);
 
             int left = topLeft[0];
             int top = topLeft[1];
@@ -1176,7 +1233,7 @@ public class CellLayout extends ViewGroup {
             Rect r = mDragOutlines[mDragOutlineCurrent];
             r.set(left, top, left + dragOutline.getWidth(), top + dragOutline.getHeight());
             if (resize) {
-                cellToRect(nearest[0], nearest[1], spanX, spanY, r);
+                cellToRect(cellX, cellY, spanX, spanY, r);
             }
 
             mDragOutlineAnims[mDragOutlineCurrent].setTag(dragOutline);
@@ -1251,7 +1308,7 @@ public class CellLayout extends ViewGroup {
     int[] findNearestArea(int pixelX, int pixelY, int spanX, int spanY, View ignoreView,
             boolean ignoreOccupied, int[] result) {
         return findNearestArea(pixelX, pixelY, spanX, spanY,
-                spanX, spanY, ignoreView, ignoreOccupied, result, null);
+                spanX, spanY, ignoreView, ignoreOccupied, result, null, mOccupied);
     }
 
     private final Stack<Rect> mTempRectStack = new Stack<Rect>();
@@ -1262,6 +1319,7 @@ public class CellLayout extends ViewGroup {
             }
         }
     }
+
     private void recycleTempRects(Stack<Rect> used) {
         while (!used.isEmpty()) {
             mTempRectStack.push(used.pop());
@@ -1285,10 +1343,11 @@ public class CellLayout extends ViewGroup {
      *         nearest the requested location.
      */
     int[] findNearestArea(int pixelX, int pixelY, int minSpanX, int minSpanY, int spanX, int spanY,
-            View ignoreView, boolean ignoreOccupied, int[] result, int[] resultSpan) {
+            View ignoreView, boolean ignoreOccupied, int[] result, int[] resultSpan,
+            boolean[][] occupied) {
         lazyInitTempRectStack();
         // mark space take by ignoreView as available (method checks if ignoreView is null)
-        markCellsAsUnoccupiedForView(ignoreView);
+        markCellsAsUnoccupiedForView(ignoreView, occupied);
 
         // For items with a spanX / spanY > 1, the passed in point (pixelX, pixelY) corresponds
         // to the center of the item, but we are searching based on the top-left cell, so
@@ -1304,7 +1363,6 @@ public class CellLayout extends ViewGroup {
 
         final int countX = mCountX;
         final int countY = mCountY;
-        final boolean[][] occupied = mOccupied;
 
         if (minSpanX <= 0 || minSpanY <= 0 || spanX <= 0 || spanY <= 0 ||
                 spanX < minSpanX || spanY < minSpanY) {
@@ -1382,6 +1440,7 @@ public class CellLayout extends ViewGroup {
                 validRegions.push(currentRect);
                 double distance = Math.sqrt(Math.pow(cellXY[0] - pixelX, 2)
                         + Math.pow(cellXY[1] - pixelY, 2));
+
                 if ((distance <= bestDistance && !contained) ||
                         currentRect.contains(bestRect)) {
                     bestDistance = distance;
@@ -1396,7 +1455,7 @@ public class CellLayout extends ViewGroup {
             }
         }
         // re-mark space taken by ignoreView as occupied
-        markCellsAsOccupiedForView(ignoreView);
+        markCellsAsOccupiedForView(ignoreView, occupied);
 
         // Return -1, -1 if no suitable location found
         if (bestDistance == Double.MAX_VALUE) {
@@ -1407,6 +1466,461 @@ public class CellLayout extends ViewGroup {
         return bestXY;
     }
 
+     /**
+     * Find a vacant area that will fit the given bounds nearest the requested
+     * cell location, and will also weigh in a suggested direction vector of the
+     * desired location. This method computers distance based on unit grid distances,
+     * not pixel distances.
+     *
+     * @param pixelX The X location at which you want to search for a vacant area.
+     * @param pixelY The Y location at which you want to search for a vacant area.
+     * @param minSpanX The minimum horizontal span required
+     * @param minSpanY The minimum vertical span required
+     * @param spanX Horizontal span of the object.
+     * @param spanY Vertical span of the object.
+     * @param ignoreOccupied If true, the result can be an occupied cell
+     * @param result Array in which to place the result, or null (in which case a new array will
+     *        be allocated)
+     * @return The X, Y cell of a vacant area that can contain this object,
+     *         nearest the requested location.
+     */
+    private int[] findNearestArea(int cellX, int cellY, int spanX, int spanY, int[] direction,
+            boolean[][] occupied, int[] result) {
+        // Keep track of best-scoring drop area
+        final int[] bestXY = result != null ? result : new int[2];
+        float bestDistance = Float.MAX_VALUE;
+        int bestDirectionScore = Integer.MIN_VALUE;
+
+        final int countX = mCountX;
+        final int countY = mCountY;
+
+        for (int y = 0; y < countY - (spanY - 1); y++) {
+            inner:
+            for (int x = 0; x < countX - (spanX - 1); x++) {
+                // First, let's see if this thing fits anywhere
+                for (int i = 0; i < spanX; i++) {
+                    for (int j = 0; j < spanY; j++) {
+                        if (occupied[x + i][y + j]) {
+                            continue inner;
+                        }
+                    }
+                }
+
+                float distance = (float)
+                        Math.sqrt((x - cellX) * (x - cellX) + (y - cellY) * (y - cellY));
+                int[] curDirection = mTmpPoint;
+                computeDirectionVector(cellX, cellY, x, y, curDirection);
+                int curDirectionScore = direction[0] * curDirection[0] +
+                        direction[1] * curDirection[1];
+
+                if (Float.compare(distance,  bestDistance) < 0 || (Float.compare(distance,
+                        bestDistance) == 0 && curDirectionScore > bestDirectionScore)) {
+                    bestDistance = distance;
+                    bestDirectionScore = curDirectionScore;
+                    bestXY[0] = x;
+                    bestXY[1] = y;
+                }
+            }
+        }
+
+        // Return -1, -1 if no suitable location found
+        if (bestDistance == Float.MAX_VALUE) {
+            bestXY[0] = -1;
+            bestXY[1] = -1;
+        }
+        return bestXY;
+    }
+
+    private boolean addViewToTempLocation(View v, Rect rectOccupiedByPotentialDrop,
+            int[] direction) {
+        LayoutParams lp = (LayoutParams) v.getLayoutParams();
+        boolean success = false;
+        markCellsForView(lp.tmpCellX, lp.tmpCellY, lp.cellHSpan,
+                lp.cellVSpan, mTmpOccupied, false);
+        markCellsForRect(rectOccupiedByPotentialDrop, mTmpOccupied, true);
+
+        findNearestArea(lp.tmpCellX, lp.tmpCellY, lp.cellHSpan, lp.cellVSpan,
+                direction, mTmpOccupied, mTempLocation);
+
+        if (mTempLocation[0] >= 0 && mTempLocation[1] >= 0) {
+            lp.tmpCellX = mTempLocation[0];
+            lp.tmpCellY = mTempLocation[1];
+            success = true;
+
+        }
+        markCellsForView(lp.tmpCellX, lp.tmpCellY, lp.cellHSpan,
+                lp.cellVSpan, mTmpOccupied, true);
+        return success;
+    }
+
+    private boolean addViewsToTempLocation(ArrayList<View> views, Rect rectOccupiedByPotentialDrop,
+            int[] direction) {
+        if (views.size() == 0) return true;
+        boolean success = false;
+
+        // We construct a rect which represents the entire group of views
+        Rect boundingRect = null;
+        for (View v: views) {
+            LayoutParams lp = (LayoutParams) v.getLayoutParams();
+            markCellsForView(lp.tmpCellX, lp.tmpCellY, lp.cellHSpan,
+                    lp.cellVSpan, mTmpOccupied, false);
+            if (boundingRect == null) {
+                boundingRect = new Rect(lp.tmpCellX, lp.tmpCellY, lp.tmpCellX + lp.cellHSpan,
+                        lp.tmpCellY + lp.cellVSpan);
+            } else {
+                boundingRect.union(lp.tmpCellX, lp.tmpCellY, lp.tmpCellX + lp.cellHSpan,
+                        lp.tmpCellY + lp.cellVSpan);
+            }
+        }
+        markCellsForRect(rectOccupiedByPotentialDrop, mTmpOccupied, true);
+
+        // TODO: this bounding rect may not be completely filled, lets be more precise about this
+        // check.
+        findNearestArea(boundingRect.left, boundingRect.top, boundingRect.width(), boundingRect.height(),
+                direction, mTmpOccupied, mTempLocation);
+
+        int deltaX = mTempLocation[0] - boundingRect.left;
+        int deltaY = mTempLocation[1] - boundingRect.top;
+        if (mTempLocation[0] >= 0 && mTempLocation[1] >= 0) {
+            for (View v: views) {
+                LayoutParams lp = (LayoutParams) v.getLayoutParams();
+                lp.tmpCellX += deltaX;
+                lp.tmpCellY += deltaY;
+            }
+            success = true;
+        }
+        for (View v: views) {
+            LayoutParams lp = (LayoutParams) v.getLayoutParams();
+            markCellsForView(lp.tmpCellX, lp.tmpCellY, lp.cellHSpan,
+                    lp.cellVSpan, mTmpOccupied, true);
+        }
+        return success;
+    }
+
+    private void markCellsForRect(Rect r, boolean[][] occupied, boolean value) {
+        markCellsForView(r.left, r.top, r.width(), r.height(), occupied, value);
+    }
+
+    private boolean rearrangementExists(int cellX, int cellY, int spanX, int spanY, int[] direction,
+            View ignoreView) {
+        mIntersectingViews.clear();
+
+        mOccupiedRect.set(cellX, cellY, cellX + spanX, cellY + spanY);
+        markCellsForRect(mOccupiedRect, mTmpOccupied, true);
+
+        if (ignoreView != null) {
+            LayoutParams lp = (LayoutParams) ignoreView.getLayoutParams();
+            lp.tmpCellX = cellX;
+            lp.tmpCellY = cellY;
+        }
+
+        int childCount = mChildren.getChildCount();
+        Rect r0 = new Rect(cellX, cellY, cellX + spanX, cellY + spanY);
+        Rect r1 = new Rect();
+        for (int i = 0; i < childCount; i++) {
+            View child = mChildren.getChildAt(i);
+            if (child == ignoreView) continue;
+            LayoutParams lp = (LayoutParams) child.getLayoutParams();
+            r1.set(lp.cellX, lp.cellY, lp.cellX + lp.cellHSpan, lp.cellY + lp.cellVSpan);
+            if (Rect.intersects(r0, r1)) {
+                if (!lp.canReorder) {
+                    return false;
+                }
+                mIntersectingViews.add(child);
+            }
+        }
+        // First we try moving the views as a block
+        if (addViewsToTempLocation(mIntersectingViews, mOccupiedRect, direction)) {
+            return true;
+        }
+        // Ok, they couldn't move as a block, let's move them individually
+        for (View v : mIntersectingViews) {
+            if (!addViewToTempLocation(v, mOccupiedRect, direction)) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /*
+     * Returns a pair (x, y), where x,y are in {-1, 0, 1} corresponding to vector between
+     * the provided point and the provided cell
+     */
+    private void computeDirectionVector(int x0, int y0, int x1, int y1, int[] result) {
+        int deltaX = x1 - x0;
+        int deltaY = y1 - y0;
+
+        double angle = Math.atan(((float) deltaY) / deltaX);
+
+        result[0] = 0;
+        result[1] = 0;
+        if (Math.abs(Math.cos(angle)) > 0.5f) {
+            result[0] = (int) Math.signum(deltaX);
+        }
+        if (Math.abs(Math.sin(angle)) > 0.5f) {
+            result[1] = (int) Math.signum(deltaY);
+        }
+    }
+
+    ItemConfiguration simpleSwap(int pixelX, int pixelY, int minSpanX, int minSpanY, int spanX,
+            int spanY, int[] direction, View dragView, boolean decX, ItemConfiguration solution) {
+        // This creates a copy of the current occupied array, omitting the current view being
+        // dragged
+        resetTempLayoutToCurrent(dragView);
+
+        // We find the nearest cell into which we would place the dragged item, assuming there's
+        // nothing in its way.
+        int result[] = new int[2];
+        result = findNearestArea(pixelX, pixelY, spanX, spanY, result);
+
+        boolean success = false;
+        // First we try the exact nearest position of the item being dragged,
+        // we will then want to try to move this around to other neighbouring positions
+        success = rearrangementExists(result[0], result[1], spanX, spanY, direction, dragView);
+
+        if (!success) {
+            // We try shrinking the widget down to size in an alternating pattern, shrink 1 in
+            // x, then 1 in y etc.
+            if (spanX > minSpanX && (minSpanY == spanY || decX)) {
+                return simpleSwap(pixelX, pixelY, minSpanX, minSpanY, spanX - 1, spanY, direction,
+                        dragView, false, solution);
+            } else if (spanY > minSpanY) {
+                return simpleSwap(pixelX, pixelY, minSpanX, minSpanY, spanX, spanY - 1, direction,
+                        dragView, true, solution);
+            }
+            solution.isSolution = false;
+        } else {
+            solution.isSolution = true;
+            solution.dragViewX = result[0];
+            solution.dragViewY = result[1];
+            solution.dragViewSpanX = spanX;
+            solution.dragViewSpanY = spanY;
+            copyCurrentStateToSolution(solution, true);
+        }
+        return solution;
+    }
+
+    private void copyCurrentStateToSolution(ItemConfiguration solution, boolean temp) {
+        int childCount = mChildren.getChildCount();
+        for (int i = 0; i < childCount; i++) {
+            View child = mChildren.getChildAt(i);
+            LayoutParams lp = (LayoutParams) child.getLayoutParams();
+            Point p;
+            if (temp) {
+                p = new Point(lp.tmpCellX, lp.tmpCellY);
+            } else {
+                p = new Point(lp.cellX, lp.cellY);
+            }
+            solution.map.put(child, p);
+        }
+    }
+
+    private void copySolutionToTempState(ItemConfiguration solution, View dragView) {
+        for (int i = 0; i < mCountX; i++) {
+            for (int j = 0; j < mCountY; j++) {
+                mTmpOccupied[i][j] = false;
+            }
+        }
+
+        int childCount = mChildren.getChildCount();
+        for (int i = 0; i < childCount; i++) {
+            View child = mChildren.getChildAt(i);
+            if (child == dragView) continue;
+            LayoutParams lp = (LayoutParams) child.getLayoutParams();
+            Point p = solution.map.get(child);
+            if (p != null) {
+                lp.tmpCellX = p.x;
+                lp.tmpCellY = p.y;
+                markCellsForView(lp.tmpCellX, lp.tmpCellY, lp.cellHSpan, lp.cellVSpan,
+                        mTmpOccupied, true);
+            }
+        }
+        markCellsForView(solution.dragViewX, solution.dragViewY, solution.dragViewSpanX,
+                solution.dragViewSpanY, mTmpOccupied, true);
+    }
+
+    private void animateItemsToSolution(ItemConfiguration solution, View dragView, boolean
+            commitDragView) {
+
+        boolean[][] occupied = DESTRUCTIVE_REORDER ? mOccupied : mTmpOccupied;
+        for (int i = 0; i < mCountX; i++) {
+            for (int j = 0; j < mCountY; j++) {
+                occupied[i][j] = false;
+            }
+        }
+
+        int childCount = mChildren.getChildCount();
+        for (int i = 0; i < childCount; i++) {
+            View child = mChildren.getChildAt(i);
+            if (child == dragView) continue;
+            LayoutParams lp = (LayoutParams) child.getLayoutParams();
+            Point p = solution.map.get(child);
+            if (p != null) {
+                if (lp.cellX != p.x || lp.cellY != p.y) {
+                    animateChildToPosition(child, p.x, p.y, 150, 0, DESTRUCTIVE_REORDER, false);
+                }
+                markCellsForView(p.x, p.y, lp.cellHSpan, lp.cellVSpan, occupied, true);
+            }
+        }
+        if (commitDragView) {
+            markCellsForView(solution.dragViewX, solution.dragViewY, solution.dragViewSpanX,
+                    solution.dragViewSpanY, occupied, true);
+        }
+    }
+
+    private void commitTempPlacement() {
+        for (int i = 0; i < mCountX; i++) {
+            for (int j = 0; j < mCountY; j++) {
+                mOccupied[i][j] = mTmpOccupied[i][j];
+            }
+        }
+        int childCount = mChildren.getChildCount();
+        for (int i = 0; i < childCount; i++) {
+            LayoutParams lp = (LayoutParams) mChildren.getChildAt(i).getLayoutParams();
+            lp.cellX = lp.tmpCellX;
+            lp.cellY = lp.tmpCellY;
+        }
+    }
+
+    public void setUseTempCoords(boolean useTempCoords) {
+        int childCount = mChildren.getChildCount();
+        for (int i = 0; i < childCount; i++) {
+            LayoutParams lp = (LayoutParams) mChildren.getChildAt(i).getLayoutParams();
+            lp.useTmpCoords = useTempCoords;
+        }
+    }
+
+    private void resetTempLayoutToCurrent(View ignoreView) {
+        for (int i = 0; i < mCountX; i++) {
+            for (int j = 0; j < mCountY; j++) {
+                mTmpOccupied[i][j] = mOccupied[i][j];
+            }
+        }
+        int childCount = mChildren.getChildCount();
+        for (int i = 0; i < childCount; i++) {
+            View child = mChildren.getChildAt(i);
+            if (child == ignoreView) continue;
+            LayoutParams lp = (LayoutParams) child.getLayoutParams();
+            lp.tmpCellX = lp.cellX;
+            lp.tmpCellY = lp.cellY;
+        }
+    }
+
+    ItemConfiguration findConfigurationNoShuffle(int pixelX, int pixelY, int minSpanX, int minSpanY,
+            int spanX, int spanY, View dragView, ItemConfiguration solution) {
+        int[] result = new int[2];
+        int[] resultSpan = new int[2];
+        findNearestVacantArea(pixelX, pixelY, minSpanX, minSpanY, spanX, spanY, null, result,
+                resultSpan);
+        if (result[0] >= 0 && result[1] >= 0) {
+            copyCurrentStateToSolution(solution, false);
+            solution.dragViewX = result[0];
+            solution.dragViewY = result[1];
+            solution.dragViewSpanX = resultSpan[0];
+            solution.dragViewSpanY = resultSpan[1];
+            solution.isSolution = true;
+        } else {
+            solution.isSolution = false;
+        }
+        return solution;
+    }
+
+    public void prepareChildForDrag(View child) {
+        markCellsAsUnoccupiedForView(child);
+        LayoutParams lp = (LayoutParams) child.getLayoutParams();
+        lp.cellX = -1;
+        lp.cellY = -1;
+
+    }
+
+    int[] createArea(int pixelX, int pixelY, int minSpanX, int minSpanY, int spanX, int spanY,
+            View dragView, int[] result, int resultSpan[], int mode) {
+
+        // First we determine if things have moved enough to cause a different layout
+        result = findNearestArea(pixelX, pixelY, 1, 1, result);
+
+        if (resultSpan == null) {
+            resultSpan = new int[2];
+        }
+
+        // We attempt the first algorithm
+        cellToCenterPoint(result[0], result[1], mTmpPoint);
+        computeDirectionVector(pixelX, pixelY, mTmpPoint[0], mTmpPoint[1], mDirectionVector);
+        ItemConfiguration swapSolution = simpleSwap(pixelX, pixelY, minSpanX, minSpanY,
+                 spanX,  spanY, mDirectionVector, dragView,  true,  new ItemConfiguration());
+
+        // We attempt the approach which doesn't shuffle views at all
+        ItemConfiguration noShuffleSolution = findConfigurationNoShuffle(pixelX, pixelY, minSpanX,
+                minSpanY, spanX, spanY, dragView, new ItemConfiguration());
+
+        ItemConfiguration finalSolution = null;
+        if (swapSolution.isSolution && swapSolution.area() >= noShuffleSolution.area()) {
+            finalSolution = swapSolution;
+        } else if (noShuffleSolution.isSolution) {
+            finalSolution = noShuffleSolution;
+        }
+
+        boolean foundSolution = true;
+        if (!DESTRUCTIVE_REORDER) {
+            setUseTempCoords(true);
+        }
+
+        if (finalSolution != null) {
+            result[0] = finalSolution.dragViewX;
+            result[1] = finalSolution.dragViewY;
+            resultSpan[0] = finalSolution.dragViewSpanX;
+            resultSpan[1] = finalSolution.dragViewSpanY;
+
+            // If we're just testing for a possible location (MODE_ACCEPT_DROP), we don't bother
+            // committing anything or animating anything as we just want to determine if a solution
+            // exists
+            if (mode == MODE_DRAG_OVER || mode == MODE_ON_DROP || mode == MODE_ON_DROP_EXTERNAL) {
+                if (!DESTRUCTIVE_REORDER) {
+                    copySolutionToTempState(finalSolution, dragView);
+                }
+                setItemPlacementDirty(true);
+                animateItemsToSolution(finalSolution, dragView, mode == MODE_ON_DROP);
+
+                if (!DESTRUCTIVE_REORDER && mode == MODE_ON_DROP) {
+                    commitTempPlacement();
+                }
+            }
+        } else {
+            foundSolution = false;
+            result[0] = result[1] = resultSpan[0] = resultSpan[1] = -1;
+        }
+
+        if ((mode == MODE_ON_DROP || !foundSolution) && !DESTRUCTIVE_REORDER) {
+            setUseTempCoords(false);
+        }
+        boolean[][] occupied = mOccupied;
+
+        mChildren.requestLayout();
+        return result;
+    }
+
+    public boolean isItemPlacementDirty() {
+        return mItemLocationsDirty;
+    }
+
+    public void setItemPlacementDirty(boolean dirty) {
+        mItemLocationsDirty = dirty;
+    }
+
+    private class ItemConfiguration {
+        HashMap<View, Point> map = new HashMap<View, Point>();
+        boolean isSolution = false;
+        int dragViewX, dragViewY, dragViewSpanX, dragViewSpanY;
+
+        int area() {
+            return dragViewSpanX * dragViewSpanY;
+        }
+        void clear() {
+            map.clear();
+            isSolution = false;
+        }
+    }
+
     /**
      * Find a vacant area that will fit the given bounds nearest the requested
      * cell location. Uses Euclidean distance to score multiple vacant areas.
@@ -1442,8 +1956,8 @@ public class CellLayout extends ViewGroup {
      */
     int[] findNearestVacantArea(int pixelX, int pixelY, int minSpanX, int minSpanY,
             int spanX, int spanY, View ignoreView, int[] result, int[] resultSpan) {
-        return findNearestArea(pixelX, pixelY, minSpanX, minSpanY,
-                spanX, spanY, ignoreView, true, result, resultSpan);
+        return findNearestArea(pixelX, pixelY, minSpanX, minSpanY, spanX, spanY, ignoreView, true,
+                result, resultSpan, mOccupied);
     }
 
     /**
@@ -1482,7 +1996,7 @@ public class CellLayout extends ViewGroup {
      * @return True if a vacant cell of the specified dimension was found, false otherwise.
      */
     boolean findCellForSpan(int[] cellXY, int spanX, int spanY) {
-        return findCellForSpanThatIntersectsIgnoring(cellXY, spanX, spanY, -1, -1, null);
+        return findCellForSpanThatIntersectsIgnoring(cellXY, spanX, spanY, -1, -1, null, mOccupied);
     }
 
     /**
@@ -1496,7 +2010,8 @@ public class CellLayout extends ViewGroup {
      * @return
      */
     boolean findCellForSpanIgnoring(int[] cellXY, int spanX, int spanY, View ignoreView) {
-        return findCellForSpanThatIntersectsIgnoring(cellXY, spanX, spanY, -1, -1, ignoreView);
+        return findCellForSpanThatIntersectsIgnoring(cellXY, spanX, spanY, -1, -1,
+                ignoreView, mOccupied);
     }
 
     /**
@@ -1514,16 +2029,16 @@ public class CellLayout extends ViewGroup {
     boolean findCellForSpanThatIntersects(int[] cellXY, int spanX, int spanY,
             int intersectX, int intersectY) {
         return findCellForSpanThatIntersectsIgnoring(
-                cellXY, spanX, spanY, intersectX, intersectY, null);
+                cellXY, spanX, spanY, intersectX, intersectY, null, mOccupied);
     }
 
     /**
      * The superset of the above two methods
      */
     boolean findCellForSpanThatIntersectsIgnoring(int[] cellXY, int spanX, int spanY,
-            int intersectX, int intersectY, View ignoreView) {
+            int intersectX, int intersectY, View ignoreView, boolean occupied[][]) {
         // mark space take by ignoreView as available (method checks if ignoreView is null)
-        markCellsAsUnoccupiedForView(ignoreView);
+        markCellsAsUnoccupiedForView(ignoreView, occupied);
 
         boolean foundCell = false;
         while (true) {
@@ -1549,7 +2064,7 @@ public class CellLayout extends ViewGroup {
                 for (int x = startX; x < endX; x++) {
                     for (int i = 0; i < spanX; i++) {
                         for (int j = 0; j < spanY; j++) {
-                            if (mOccupied[x + i][y + j]) {
+                            if (occupied[x + i][y + j]) {
                                 // small optimization: we can skip to after the column we just found
                                 // an occupied cell
                                 x += i;
@@ -1577,7 +2092,7 @@ public class CellLayout extends ViewGroup {
         }
 
         // re-mark space taken by ignoreView as occupied
-        markCellsAsOccupiedForView(ignoreView);
+        markCellsAsOccupiedForView(ignoreView, occupied);
         return foundCell;
     }
 
@@ -1820,27 +2335,34 @@ out:            for (int i = x; i < x + spanX - 1 && x < xCount; i++) {
     }
 
     public void onMove(View view, int newCellX, int newCellY, int newSpanX, int newSpanY) {
-        LayoutParams lp = (LayoutParams) view.getLayoutParams();
         markCellsAsUnoccupiedForView(view);
-        markCellsForView(newCellX, newCellY, newSpanX, newSpanY, true);
+        markCellsForView(newCellX, newCellY, newSpanX, newSpanY, mOccupied, true);
     }
 
     public void markCellsAsOccupiedForView(View view) {
+        markCellsAsOccupiedForView(view, mOccupied);
+    }
+    public void markCellsAsOccupiedForView(View view, boolean[][] occupied) {
         if (view == null || view.getParent() != mChildren) return;
         LayoutParams lp = (LayoutParams) view.getLayoutParams();
-        markCellsForView(lp.cellX, lp.cellY, lp.cellHSpan, lp.cellVSpan, true);
+        markCellsForView(lp.cellX, lp.cellY, lp.cellHSpan, lp.cellVSpan, occupied, true);
     }
 
     public void markCellsAsUnoccupiedForView(View view) {
+        markCellsAsUnoccupiedForView(view, mOccupied);
+    }
+    public void markCellsAsUnoccupiedForView(View view, boolean occupied[][]) {
         if (view == null || view.getParent() != mChildren) return;
         LayoutParams lp = (LayoutParams) view.getLayoutParams();
-        markCellsForView(lp.cellX, lp.cellY, lp.cellHSpan, lp.cellVSpan, false);
+        markCellsForView(lp.cellX, lp.cellY, lp.cellHSpan, lp.cellVSpan, occupied, false);
     }
 
-    private void markCellsForView(int cellX, int cellY, int spanX, int spanY, boolean value) {
+    private void markCellsForView(int cellX, int cellY, int spanX, int spanY, boolean[][] occupied,
+            boolean value) {
+        if (cellX < 0 || cellY < 0) return;
         for (int x = cellX; x < cellX + spanX && x < mCountX; x++) {
             for (int y = cellY; y < cellY + spanY && y < mCountY; y++) {
-                mOccupied[x][y] = value;
+                occupied[x][y] = value;
             }
         }
     }
@@ -1903,6 +2425,21 @@ out:            for (int i = x; i < x + spanX - 1 && x < xCount; i++) {
         public int cellY;
 
         /**
+         * Temporary horizontal location of the item in the grid during reorder
+         */
+        public int tmpCellX;
+
+        /**
+         * Temporary vertical location of the item in the grid during reorder
+         */
+        public int tmpCellY;
+
+        /**
+         * Indicates that the temporary coordinates should be used to layout the items
+         */
+        public boolean useTmpCoords;
+
+        /**
          * Number of cells spanned horizontally by the item.
          */
         @ViewDebug.ExportedProperty
@@ -1920,6 +2457,12 @@ out:            for (int i = x; i < x + spanX - 1 && x < xCount; i++) {
          */
         public boolean isLockedToGrid = true;
 
+        /**
+         * Indicates whether this item can be reordered. Always true except in the case of the
+         * the AllApps button.
+         */
+        public boolean canReorder = true;
+
         // X coordinate of the view in the layout.
         @ViewDebug.ExportedProperty
         int x;
@@ -1961,8 +2504,8 @@ out:            for (int i = x; i < x + spanX - 1 && x < xCount; i++) {
             if (isLockedToGrid) {
                 final int myCellHSpan = cellHSpan;
                 final int myCellVSpan = cellVSpan;
-                final int myCellX = cellX;
-                final int myCellY = cellY;
+                final int myCellX = useTmpCoords ? tmpCellX : cellX;
+                final int myCellY = useTmpCoords ? tmpCellY : cellY;
 
                 width = myCellHSpan * cellWidth + ((myCellHSpan - 1) * widthGap) -
                         leftMargin - rightMargin;
diff --git a/src/com/android/launcher2/Folder.java b/src/com/android/launcher2/Folder.java
index 08d33159f..07e76c9ef 100644
--- a/src/com/android/launcher2/Folder.java
+++ b/src/com/android/launcher2/Folder.java
@@ -528,7 +528,7 @@ public class Folder extends LinearLayout implements DragSource, View.OnClickList
                 for (int x = startX; x <= endX; x++) {
                     View v = mContent.getChildAt(x,y);
                     if (mContent.animateChildToPosition(v, empty[0], empty[1],
-                            REORDER_ANIMATION_DURATION, delay)) {
+                            REORDER_ANIMATION_DURATION, delay, true, true)) {
                         empty[0] = x;
                         empty[1] = y;
                         delay += delayAmount;
@@ -545,7 +545,7 @@ public class Folder extends LinearLayout implements DragSource, View.OnClickList
                 for (int x = startX; x >= endX; x--) {
                     View v = mContent.getChildAt(x,y);
                     if (mContent.animateChildToPosition(v, empty[0], empty[1],
-                            REORDER_ANIMATION_DURATION, delay)) {
+                            REORDER_ANIMATION_DURATION, delay, true, true)) {
                         empty[0] = x;
                         empty[1] = y;
                         delay += delayAmount;
diff --git a/src/com/android/launcher2/Hotseat.java b/src/com/android/launcher2/Hotseat.java
index add62c004..9e525bd5a 100644
--- a/src/com/android/launcher2/Hotseat.java
+++ b/src/com/android/launcher2/Hotseat.java
@@ -130,7 +130,8 @@ public class Hotseat extends FrameLayout {
         // the hotseat in order regardless of which orientation they were added
         int x = getCellXFromOrder(mAllAppsButtonRank);
         int y = getCellYFromOrder(mAllAppsButtonRank);
-        mContent.addViewToCellLayout(allAppsButton, -1, 0, new CellLayout.LayoutParams(x,y,1,1),
-                true, true);
+        CellLayout.LayoutParams lp = new CellLayout.LayoutParams(x,y,1,1);
+        lp.canReorder = false;
+        mContent.addViewToCellLayout(allAppsButton, -1, 0, lp, true, true);
     }
 }
diff --git a/src/com/android/launcher2/Launcher.java b/src/com/android/launcher2/Launcher.java
index b7d4c8bc9..0c1b76f8e 100644
--- a/src/com/android/launcher2/Launcher.java
+++ b/src/com/android/launcher2/Launcher.java
@@ -912,13 +912,14 @@ public final class Launcher extends Activity
             foundCellSpan = true;
 
             // If appropriate, either create a folder or add to an existing folder
-            if (mWorkspace.createUserFolderIfNecessary(view, container, layout, cellXY,
+            if (mWorkspace.createUserFolderIfNecessary(view, container, layout, cellXY, 0,
                     true, null,null)) {
                 return;
             }
             DragObject dragObject = new DragObject();
             dragObject.dragInfo = info;
-            if (mWorkspace.addToExistingFolderIfNecessary(view, layout, cellXY, dragObject, true)) {
+            if (mWorkspace.addToExistingFolderIfNecessary(view, layout, cellXY, 0, dragObject,
+                    true)) {
                 return;
             }
         } else if (touchXY != null) {
diff --git a/src/com/android/launcher2/Workspace.java b/src/com/android/launcher2/Workspace.java
index cfe0df4ba..76070c4f7 100644
--- a/src/com/android/launcher2/Workspace.java
+++ b/src/com/android/launcher2/Workspace.java
@@ -17,18 +17,15 @@
 package com.android.launcher2;
 
 import android.animation.Animator;
-import android.animation.AnimatorListenerAdapter;
 import android.animation.AnimatorSet;
 import android.animation.ObjectAnimator;
 import android.animation.TimeInterpolator;
 import android.animation.ValueAnimator;
 import android.animation.ValueAnimator.AnimatorUpdateListener;
-import android.app.AlertDialog;
 import android.app.WallpaperManager;
 import android.appwidget.AppWidgetHostView;
 import android.appwidget.AppWidgetManager;
 import android.appwidget.AppWidgetProviderInfo;
-import android.content.ClipData;
 import android.content.ClipDescription;
 import android.content.ComponentName;
 import android.content.Context;
@@ -42,7 +39,6 @@ import android.graphics.Matrix;
 import android.graphics.Paint;
 import android.graphics.Point;
 import android.graphics.Rect;
-import android.graphics.RectF;
 import android.graphics.Region.Op;
 import android.graphics.drawable.Drawable;
 import android.os.IBinder;
@@ -55,18 +51,16 @@ import android.view.Display;
 import android.view.DragEvent;
 import android.view.MotionEvent;
 import android.view.View;
-import android.view.ViewConfiguration;
 import android.view.ViewGroup;
-import android.view.View.MeasureSpec;
 import android.view.animation.AccelerateInterpolator;
 import android.view.animation.DecelerateInterpolator;
 import android.widget.ImageView;
 import android.widget.TextView;
-import android.widget.Toast;
 
 import com.android.launcher.R;
 import com.android.launcher2.FolderIcon.FolderRingAnimator;
 import com.android.launcher2.InstallWidgetReceiver.WidgetMimeTypeHandlerData;
+import com.android.launcher2.LauncherSettings.Favorites;
 
 import java.util.ArrayList;
 import java.util.HashSet;
@@ -96,6 +90,8 @@ public class Workspace extends SmoothPagedView
     private static final int ADJACENT_SCREEN_DROP_DURATION = 300;
     private static final int FLING_THRESHOLD_VELOCITY = 500;
 
+    private float mMaxDistanceForFolderCreation = 50.0f;
+
     // These animators are used to fade the children's outlines
     private ObjectAnimator mChildrenOutlineFadeInAnimation;
     private ObjectAnimator mChildrenOutlineFadeOutAnimation;
@@ -192,8 +188,10 @@ public class Workspace extends SmoothPagedView
     private int mWallpaperTravelWidth;
 
     // Variables relating to the creation of user folders by hovering shortcuts over shortcuts
-    private static final int FOLDER_CREATION_TIMEOUT = 250;
+    private static final int FOLDER_CREATION_TIMEOUT = 0;
+    private static final int REORDER_TIMEOUT = 250;
     private final Alarm mFolderCreationAlarm = new Alarm();
+    private final Alarm mReorderAlarm = new Alarm();
     private FolderRingAnimator mDragFolderRingAnimator = null;
     private View mLastDragOverView = null;
     private boolean mCreateUserFolderOnDrop = false;
@@ -212,6 +210,15 @@ public class Workspace extends SmoothPagedView
     public static final int COMPLETE_TWO_STAGE_WIDGET_DROP_ANIMATION = 3;
     public static final int CANCEL_TWO_STAGE_WIDGET_DROP_ANIMATION = 4;
 
+    // Related to dragging, folder creation and reordering
+    private static final int DRAG_MODE_NONE = 0;
+    private static final int DRAG_MODE_CREATE_FOLDER = 1;
+    private static final int DRAG_MODE_ADD_TO_FOLDER = 2;
+    private static final int DRAG_MODE_REORDER = 3;
+    private int mDragMode = DRAG_MODE_NONE;
+    private int mLastReorderX = -1;
+    private int mLastReorderY = -1;
+
     // Relating to workspace drag fade out
     private float mDragFadeOutAlpha;
     private int mDragFadeOutDuration;
@@ -405,8 +412,8 @@ public class Workspace extends SmoothPagedView
         setWillNotDraw(false);
         setChildrenDrawnWithCacheEnabled(true);
 
+        final Resources res = getResources();
         try {
-            final Resources res = getResources();
             mBackground = res.getDrawable(R.drawable.apps_customize_bg);
         } catch (Resources.NotFoundException e) {
             // In this case, we will skip drawing background protection
@@ -419,8 +426,8 @@ public class Workspace extends SmoothPagedView
         mWallpaperTravelWidth = (int) (mDisplayWidth *
                 wallpaperTravelToScreenWidthRatio(mDisplayWidth, mDisplayHeight));
 
+        mMaxDistanceForFolderCreation = (0.5f * res.getDimension(R.dimen.app_icon_size));
         mFlingThresholdVelocity = (int) (FLING_THRESHOLD_VELOCITY * mDensity);
-
     }
 
     @Override
@@ -1884,6 +1891,8 @@ public class Workspace extends SmoothPagedView
 
         mDragInfo = cellInfo;
         child.setVisibility(INVISIBLE);
+        CellLayout layout = (CellLayout) child.getParent().getParent();
+        layout.prepareChildForDrag(child);
 
         child.clearFocus();
         child.setPressed(false);
@@ -2002,19 +2011,29 @@ public class Workspace extends SmoothPagedView
                 minSpanX = ((PendingAddWidgetInfo) d.dragInfo).minSpanX;
                 minSpanY = ((PendingAddWidgetInfo) d.dragInfo).minSpanY;
             }
+
             mTargetCell = findNearestArea((int) mDragViewVisualCenter[0],
                     (int) mDragViewVisualCenter[1], minSpanX, minSpanY, mDragTargetLayout,
                     mTargetCell);
-            if (willCreateUserFolder((ItemInfo) d.dragInfo, mDragTargetLayout, mTargetCell, true)) {
+            float distance = mDragTargetLayout.getDistanceFromCell(mDragViewVisualCenter[0],
+                    mDragViewVisualCenter[1], mTargetCell);
+            if (willCreateUserFolder((ItemInfo) d.dragInfo, mDragTargetLayout,
+                    mTargetCell, distance, true)) {
                 return true;
             }
             if (willAddToExistingUserFolder((ItemInfo) d.dragInfo, mDragTargetLayout,
-                    mTargetCell)) {
+                    mTargetCell, distance)) {
                 return true;
             }
 
+            int[] resultSpan = new int[2];
+            mTargetCell = mDragTargetLayout.createArea((int) mDragViewVisualCenter[0],
+                    (int) mDragViewVisualCenter[1], minSpanX, minSpanY, spanX, spanY,
+                    null, mTargetCell, resultSpan, CellLayout.MODE_ACCEPT_DROP);
+            boolean foundCell = mTargetCell[0] >= 0 && mTargetCell[1] >= 0;
+
             // Don't accept the drop if there's no room for the item
-            if (!mDragTargetLayout.findCellForSpanIgnoring(null, minSpanX, minSpanY, ignoreView)) {
+            if (!foundCell) {
                 // Don't show the message if we are dropping on the AllApps button and the hotseat
                 // is full
                 if (mTargetCell != null && mLauncher.isHotseatLayout(mDragTargetLayout)) {
@@ -2032,15 +2051,15 @@ public class Workspace extends SmoothPagedView
         return true;
     }
 
-    boolean willCreateUserFolder(ItemInfo info, CellLayout target, int[] targetCell,
-            boolean considerTimeout) {
+    boolean willCreateUserFolder(ItemInfo info, CellLayout target, int[] targetCell, float
+            distance, boolean considerTimeout) {
+        if (distance > mMaxDistanceForFolderCreation) return false;
+
         View dropOverView = target.getChildAt(targetCell[0], targetCell[1]);
 
         boolean hasntMoved = false;
         if (mDragInfo != null) {
-            CellLayout cellParent = getParentCellLayoutForView(mDragInfo.cell);
-            hasntMoved = (mDragInfo.cellX == targetCell[0] &&
-                    mDragInfo.cellY == targetCell[1]) && (cellParent == target);
+            hasntMoved = dropOverView == mDragInfo.cell;
         }
 
         if (dropOverView == null || hasntMoved || (considerTimeout && !mCreateUserFolderOnDrop)) {
@@ -2055,7 +2074,10 @@ public class Workspace extends SmoothPagedView
         return (aboveShortcut && willBecomeShortcut);
     }
 
-    boolean willAddToExistingUserFolder(Object dragInfo, CellLayout target, int[] targetCell) {
+    boolean willAddToExistingUserFolder(Object dragInfo, CellLayout target, int[] targetCell,
+            float distance) {
+        if (distance > mMaxDistanceForFolderCreation) return false;
+
         View dropOverView = target.getChildAt(targetCell[0], targetCell[1]);
         if (dropOverView instanceof FolderIcon) {
             FolderIcon fi = (FolderIcon) dropOverView;
@@ -2067,7 +2089,9 @@ public class Workspace extends SmoothPagedView
     }
 
     boolean createUserFolderIfNecessary(View newView, long container, CellLayout target,
-            int[] targetCell, boolean external, DragView dragView, Runnable postAnimationRunnable) {
+            int[] targetCell, float distance, boolean external, DragView dragView,
+            Runnable postAnimationRunnable) {
+        if (distance > mMaxDistanceForFolderCreation) return false;
         View v = target.getChildAt(targetCell[0], targetCell[1]);
         boolean hasntMoved = false;
         if (mDragInfo != null) {
@@ -2117,7 +2141,9 @@ public class Workspace extends SmoothPagedView
     }
 
     boolean addToExistingFolderIfNecessary(View newView, CellLayout target, int[] targetCell,
-            DragObject d, boolean external) {
+            float distance, DragObject d, boolean external) {
+        if (distance > mMaxDistanceForFolderCreation) return false;
+
         View dropOverView = target.getChildAt(targetCell[0], targetCell[1]);
         if (dropOverView instanceof FolderIcon) {
             FolderIcon fi = (FolderIcon) dropOverView;
@@ -2172,16 +2198,21 @@ public class Workspace extends SmoothPagedView
                 int spanY = mDragInfo != null ? mDragInfo.spanY : 1;
                 // First we find the cell nearest to point at which the item is
                 // dropped, without any consideration to whether there is an item there.
+
                 mTargetCell = findNearestArea((int) mDragViewVisualCenter[0], (int)
                         mDragViewVisualCenter[1], spanX, spanY, dropTargetLayout, mTargetCell);
+                float distance = dropTargetLayout.getDistanceFromCell(mDragViewVisualCenter[0],
+                        mDragViewVisualCenter[1], mTargetCell);
+
                 // If the item being dropped is a shortcut and the nearest drop
                 // cell also contains a shortcut, then create a folder with the two shortcuts.
                 if (!mInScrollArea && createUserFolderIfNecessary(cell, container,
-                        dropTargetLayout, mTargetCell, false, d.dragView, null)) {
+                        dropTargetLayout, mTargetCell, distance, false, d.dragView, null)) {
                     return;
                 }
 
-                if (addToExistingFolderIfNecessary(cell, dropTargetLayout, mTargetCell, d, false)) {
+                if (addToExistingFolderIfNecessary(cell, dropTargetLayout, mTargetCell,
+                        distance, d, false)) {
                     return;
                 }
 
@@ -2194,10 +2225,12 @@ public class Workspace extends SmoothPagedView
                     minSpanX = item.minSpanX;
                     minSpanY = item.minSpanY;
                 }
+
                 int[] resultSpan = new int[2];
-                mTargetCell = findNearestVacantArea((int) mDragViewVisualCenter[0],
-                        (int) mDragViewVisualCenter[1], minSpanX, minSpanY, mDragInfo.spanX,
-                        mDragInfo.spanY, cell, dropTargetLayout, mTargetCell, resultSpan);
+                mTargetCell = mDragTargetLayout.createArea((int) mDragViewVisualCenter[0],
+                        (int) mDragViewVisualCenter[1], minSpanX, minSpanY, spanX, spanY, cell,
+                        mTargetCell, resultSpan, CellLayout.MODE_ON_DROP);
+
                 boolean foundCell = mTargetCell[0] >= 0 && mTargetCell[1] >= 0;
                 if (foundCell && (resultSpan[0] != item.spanX || resultSpan[1] != item.spanY)) {
                     resizeOnDrop = true;
@@ -2221,8 +2254,6 @@ public class Workspace extends SmoothPagedView
 
                     // update the item's position after drop
                     CellLayout.LayoutParams lp = (CellLayout.LayoutParams) cell.getLayoutParams();
-                    dropTargetLayout.onMove(cell, mTargetCell[0], mTargetCell[1],
-                            item.spanX, item.spanY);
                     lp.cellX = mTargetCell[0];
                     lp.cellY = mTargetCell[1];
                     lp.cellHSpan = item.spanX;
@@ -2358,6 +2389,13 @@ public class Workspace extends SmoothPagedView
         // Clean up folders
         cleanupFolderCreation(d);
 
+        // Clean up reorder
+        if (mReorderAlarm != null) {
+            mReorderAlarm.cancelAlarm();
+            mLastReorderX = -1;
+            mLastReorderY = -1;
+        }
+
         // Reset the scroll area and previous drag target
         onResetScrollArea();
 
@@ -2366,6 +2404,7 @@ public class Workspace extends SmoothPagedView
             mDragTargetLayout.onDragExit();
         }
         mLastDragOverView = null;
+        mDragMode = DRAG_MODE_NONE;
         mSpringLoadedDragController.cancel();
 
         if (!mIsPageMoving) {
@@ -2617,6 +2656,7 @@ public class Workspace extends SmoothPagedView
         mDragViewVisualCenter = getDragViewVisualCenter(d.x, d.y, d.xOffset, d.yOffset,
             d.dragView, mDragViewVisualCenter);
 
+        final View child = (mDragInfo == null) ? null : mDragInfo.cell;
         // Identify whether we have dragged over a side page
         if (isSmall()) {
             if (mLauncher.getHotseat() != null && !isExternalDragWidget(d)) {
@@ -2642,6 +2682,7 @@ public class Workspace extends SmoothPagedView
                     mDragTargetLayout.onDragEnter();
                 } else {
                     mLastDragOverView = null;
+                    mDragMode = DRAG_MODE_NONE;
                 }
 
                 boolean isInSpringLoadedMode = (mState == State.SPRING_LOADED);
@@ -2677,8 +2718,6 @@ public class Workspace extends SmoothPagedView
 
         // Handle the drag over
         if (mDragTargetLayout != null) {
-            final View child = (mDragInfo == null) ? null : mDragInfo.cell;
-
             // We want the point to be mapped to the dragTarget.
             if (mLauncher.isHotseatLayout(mDragTargetLayout)) {
                 mapPointFromSelfToSibling(mLauncher.getHotseat(), mDragViewVisualCenter);
@@ -2689,48 +2728,91 @@ public class Workspace extends SmoothPagedView
 
             mTargetCell = findNearestArea((int) mDragViewVisualCenter[0],
                     (int) mDragViewVisualCenter[1], 1, 1, mDragTargetLayout, mTargetCell);
+            float targetCellDistance = mDragTargetLayout.getDistanceFromCell(
+                    mDragViewVisualCenter[0], mDragViewVisualCenter[1], mTargetCell);
+
             final View dragOverView = mDragTargetLayout.getChildAt(mTargetCell[0],
                     mTargetCell[1]);
 
-            boolean userFolderPending = willCreateUserFolder(info, mDragTargetLayout,
-                    mTargetCell, false);
-            boolean isOverFolder = dragOverView instanceof FolderIcon;
-            if (dragOverView != mLastDragOverView) {
-                cancelFolderCreation();
-                if (mLastDragOverView != null && mLastDragOverView instanceof FolderIcon) {
-                    ((FolderIcon) mLastDragOverView).onDragExit(d.dragInfo);
+            final View lastDragOverView = mLastDragOverView;
+            if (mLastDragOverView != dragOverView) {
+                mDragMode = DRAG_MODE_NONE;
+                mLastDragOverView = dragOverView;
+                if (mReorderAlarm != null) {
+                    mReorderAlarm.cancelAlarm();
                 }
             }
 
-            if (userFolderPending && dragOverView != mLastDragOverView) {
-                mFolderCreationAlarm.setOnAlarmListener(new
-                        FolderCreationAlarmListener(mDragTargetLayout, mTargetCell[0], mTargetCell[1]));
-                mFolderCreationAlarm.setAlarm(FOLDER_CREATION_TIMEOUT);
-            }
+            boolean folder = willCreateOrAddToFolder(info, mDragTargetLayout, mTargetCell,
+                    targetCellDistance, dragOverView, lastDragOverView);
 
-            if (dragOverView != mLastDragOverView && isOverFolder) {
-                ((FolderIcon) dragOverView).onDragEnter(d.dragInfo);
-                if (mDragTargetLayout != null) {
-                    mDragTargetLayout.clearDragOutlines();
-                }
+            int minSpanX = item.spanX;
+            int minSpanY = item.spanY;
+            if (item.minSpanX > 0 && item.minSpanY > 0) {
+                minSpanX = item.minSpanX;
+                minSpanY = item.minSpanY;
             }
-            mLastDragOverView = dragOverView;
 
-            if (!mCreateUserFolderOnDrop && !isOverFolder) {
-                int minSpanX = item.spanX;
-                int minSpanY = item.spanY;
-                if (item.minSpanX > 0 && item.minSpanY > 0) {
-                    minSpanX = item.minSpanX;
-                    minSpanY = item.minSpanY;
+            if (!folder && !mReorderAlarm.alarmPending() && (mLastReorderX != mTargetCell[0] ||
+                    mLastReorderY != mTargetCell[1])) {
+                cancelFolderCreation();
+                ReorderAlarmListener listener = new ReorderAlarmListener(mDragViewVisualCenter,
+                        minSpanX, minSpanY, item.spanX, item.spanY, d.dragView, child);
+                mReorderAlarm.setOnAlarmListener(listener);
+                mReorderAlarm.setAlarm(REORDER_TIMEOUT);
+            } else if (folder) {
+                if (mReorderAlarm != null) {
+                    mReorderAlarm.cancelAlarm();
                 }
+            }
+            // TODO: need to determine what we're going to about visualizing drop locations
+            /*
+            boolean resize = resultSpan[0] != info.spanX || resultSpan[1] != info.spanY;
+            if (!folder) {
                 mDragTargetLayout.visualizeDropLocation(child, mDragOutline,
                         (int) mDragViewVisualCenter[0], (int) mDragViewVisualCenter[1],
-                        minSpanX, minSpanY, item.spanX, item.spanY,
+                        mTargetCell[0], mTargetCell[1], resultSpan[0], resultSpan[1], resize,
                         d.dragView.getDragVisualizeOffset(), d.dragView.getDragRegion());
+
             }
+            */
         }
     }
 
+    private boolean willCreateOrAddToFolder(ItemInfo info, CellLayout targetLayout,
+            int[] targetCell, float distance, View dragOverView, View lastDragOverView) {
+        boolean userFolderPending = willCreateUserFolder(info, targetLayout, targetCell, distance,
+                false);
+
+        if (userFolderPending && mDragMode == DRAG_MODE_NONE) {
+            mFolderCreationAlarm.setOnAlarmListener(new
+                    FolderCreationAlarmListener(targetLayout, targetCell[0], targetCell[1]));
+            mFolderCreationAlarm.setAlarm(FOLDER_CREATION_TIMEOUT);
+        }
+
+        boolean willAddToFolder =
+                willAddToExistingUserFolder(info, targetLayout, targetCell, distance);
+
+        if (willAddToFolder && mDragMode == DRAG_MODE_NONE) {
+            FolderIcon fi = ((FolderIcon) dragOverView);
+            mDragMode = DRAG_MODE_ADD_TO_FOLDER;
+            fi.onDragEnter(info);
+            if (targetLayout != null) {
+                targetLayout.clearDragOutlines();
+            }
+        }
+
+        if (dragOverView != lastDragOverView || (mCreateUserFolderOnDrop && !userFolderPending)
+                || (!willAddToFolder && mDragMode == DRAG_MODE_ADD_TO_FOLDER)) {
+            cancelFolderCreation();
+            if (lastDragOverView != null && lastDragOverView instanceof FolderIcon) {
+                ((FolderIcon) lastDragOverView).onDragExit(info);
+            }
+        }
+
+        return willAddToFolder || userFolderPending;
+    }
+
     private void cleanupFolderCreation(DragObject d) {
         if (mDragFolderRingAnimator != null && mCreateUserFolderOnDrop) {
             mDragFolderRingAnimator.animateToNaturalState();
@@ -2772,6 +2854,48 @@ public class Workspace extends SmoothPagedView
             layout.showFolderAccept(mDragFolderRingAnimator);
             layout.clearDragOutlines();
             mCreateUserFolderOnDrop = true;
+            mDragMode = DRAG_MODE_CREATE_FOLDER;
+        }
+    }
+
+    class ReorderAlarmListener implements OnAlarmListener {
+        float[] dragViewCenter;
+        int minSpanX, minSpanY, spanX, spanY;
+        DragView dragView;
+        View child;
+
+        public ReorderAlarmListener(float[] dragViewCenter, int minSpanX, int minSpanY, int spanX,
+                int spanY, DragView dragView, View child) {
+            this.dragViewCenter = dragViewCenter;
+            this.minSpanX = minSpanX;
+            this.minSpanY = minSpanY;
+            this.spanX = spanX;
+            this.spanY = spanY;
+            this.child = child;
+            this.dragView = dragView;
+        }
+
+        public void onAlarm(Alarm alarm) {
+            int[] resultSpan = new int[2];
+            mTargetCell = mDragTargetLayout.createArea((int) mDragViewVisualCenter[0],
+                (int) mDragViewVisualCenter[1], minSpanX, minSpanY, spanX, spanY,
+                child, mTargetCell, resultSpan, CellLayout.MODE_DRAG_OVER);
+
+            mLastReorderX = mTargetCell[0];
+            mLastReorderY = mTargetCell[1];
+
+            if (mDragMode == DRAG_MODE_ADD_TO_FOLDER) {
+            }
+            mDragMode = DRAG_MODE_REORDER;
+
+            // TODO: need to determine what we're going to about visualizing drop locations
+            /*
+            boolean resize = resultSpan[0] != spanX || resultSpan[1] != spanY;
+            mDragTargetLayout.visualizeDropLocation(child, mDragOutline,
+                (int) mDragViewVisualCenter[0], (int) mDragViewVisualCenter[1],
+                mTargetCell[0], mTargetCell[1], resultSpan[0], resultSpan[1], resize,
+                dragView.getDragVisualizeOffset(), dragView.getDragRegion());
+            */
         }
     }
 
@@ -2841,23 +2965,27 @@ public class Workspace extends SmoothPagedView
             if (pendingInfo.itemType == LauncherSettings.Favorites.ITEM_TYPE_SHORTCUT) {
                 mTargetCell = findNearestArea((int) touchXY[0], (int) touchXY[1], spanX, spanY,
                         cellLayout, mTargetCell);
+                float distance = cellLayout.getDistanceFromCell(mDragViewVisualCenter[0],
+                        mDragViewVisualCenter[1], mTargetCell);
                 if (willCreateUserFolder((ItemInfo) d.dragInfo, mDragTargetLayout, mTargetCell,
-                        true) || willAddToExistingUserFolder((ItemInfo) d.dragInfo,
-                                mDragTargetLayout, mTargetCell)) {
+                        distance, true) || willAddToExistingUserFolder((ItemInfo) d.dragInfo,
+                                mDragTargetLayout, mTargetCell, distance)) {
                     findNearestVacantCell = false;
                 }
             }
+
             final ItemInfo item = (ItemInfo) d.dragInfo;
-            int minSpanX = item.spanX;
-            int minSpanY = item.spanY;
-            if (item.minSpanX > 0 && item.minSpanY > 0) {
-                minSpanX = item.minSpanX;
-                minSpanY = item.minSpanY;
-            }
             if (findNearestVacantCell) {
+                int minSpanX = item.spanX;
+                int minSpanY = item.spanY;
+                if (item.minSpanX > 0 && item.minSpanY > 0) {
+                    minSpanX = item.minSpanX;
+                    minSpanY = item.minSpanY;
+                }
                 int[] resultSpan = new int[2];
-                mTargetCell = findNearestVacantArea(touchXY[0], touchXY[1], minSpanX, minSpanY,
-                        spanX, spanY, null, cellLayout, mTargetCell, resultSpan);
+                mTargetCell = mDragTargetLayout.createArea((int) mDragViewVisualCenter[0],
+                        (int) mDragViewVisualCenter[1], minSpanX, minSpanY, info.spanX, info.spanY,
+                        null, mTargetCell, resultSpan, CellLayout.MODE_ON_DROP_EXTERNAL);
                 item.spanX = resultSpan[0];
                 item.spanY = resultSpan[1];
             }
@@ -2922,20 +3050,24 @@ public class Workspace extends SmoothPagedView
             if (touchXY != null) {
                 mTargetCell = findNearestArea((int) touchXY[0], (int) touchXY[1], spanX, spanY,
                         cellLayout, mTargetCell);
+                float distance = cellLayout.getDistanceFromCell(mDragViewVisualCenter[0],
+                        mDragViewVisualCenter[1], mTargetCell);
                 d.postAnimationRunnable = exitSpringLoadedRunnable;
-                if (createUserFolderIfNecessary(view, container, cellLayout, mTargetCell, true,
-                        d.dragView, d.postAnimationRunnable)) {
+                if (createUserFolderIfNecessary(view, container, cellLayout, mTargetCell, distance,
+                        true, d.dragView, d.postAnimationRunnable)) {
                     return;
                 }
-                if (addToExistingFolderIfNecessary(view, cellLayout, mTargetCell, d, true)) {
+                if (addToExistingFolderIfNecessary(view, cellLayout, mTargetCell, distance, d,
+                        true)) {
                     return;
                 }
             }
 
             if (touchXY != null) {
                 // when dragging and dropping, just find the closest free spot
-                mTargetCell = findNearestVacantArea(touchXY[0], touchXY[1], 1, 1, null,
-                        cellLayout, mTargetCell);
+                mTargetCell = mDragTargetLayout.createArea((int) mDragViewVisualCenter[0],
+                        (int) mDragViewVisualCenter[1], 1, 1, 1, 1,
+                        null, mTargetCell, null, CellLayout.MODE_ON_DROP);
             } else {
                 cellLayout.findCellForSpan(mTargetCell, 1, 1);
             }
@@ -3117,29 +3249,6 @@ public class Workspace extends SmoothPagedView
      *
      * pixelX and pixelY should be in the coordinate system of layout
      */
-    private int[] findNearestVacantArea(int pixelX, int pixelY,
-            int spanX, int spanY, View ignoreView, CellLayout layout, int[] recycle) {
-        return layout.findNearestVacantArea(
-                pixelX, pixelY, spanX, spanY, spanX, spanY, ignoreView, recycle, null);
-    }
-
-    /**
-     * Calculate the nearest cell where the given object would be dropped.
-     *
-     * pixelX and pixelY should be in the coordinate system of layout
-     */
-    private int[] findNearestVacantArea(int pixelX, int pixelY, int minSpanX, int minSpanY,
-            int spanX, int spanY, View ignoreView, CellLayout layout, int[] recycle,
-            int[] returnSpan) {
-        return layout.findNearestVacantArea(
-                pixelX, pixelY, minSpanX, minSpanY, spanX, spanY, ignoreView, recycle, returnSpan);
-    }
-
-    /**
-     * Calculate the nearest cell where the given object would be dropped.
-     *
-     * pixelX and pixelY should be in the coordinate system of layout
-     */
     private int[] findNearestArea(int pixelX, int pixelY,
             int spanX, int spanY, CellLayout layout, int[] recycle) {
         return layout.findNearestArea(
@@ -3188,10 +3297,34 @@ public class Workspace extends SmoothPagedView
         mDragOutline = null;
         mDragInfo = null;
 
+        saveWorkspaceStateToDb();
         // Hide the scrolling indicator after you pick up an item
         hideScrollingIndicator(false);
     }
 
+    public void saveWorkspaceStateToDb() {
+        int count = getChildCount();
+        for (int i = 0; i < count; i++) {
+            CellLayout cl = (CellLayout) getChildAt(i);
+            if (cl.isItemPlacementDirty()) {
+                updateItemLocationsInDatabase(cl);
+                cl.setItemPlacementDirty(false);
+            }
+        }
+    }
+
+    private void updateItemLocationsInDatabase(CellLayout cl) {
+        int count = cl.getChildrenLayout().getChildCount();
+        int screen = indexOfChild(cl);
+        for (int i = 0; i < count; i++) {
+            View v = cl.getChildrenLayout().getChildAt(i);
+            ItemInfo info = (ItemInfo) v.getTag();
+
+            LauncherModel.moveItemInDatabase(mLauncher, info, Favorites.CONTAINER_DESKTOP, screen,
+                        info.cellX, info.cellY);
+        }
+    }
+
     public boolean isDropEnabled() {
         return true;
     }