CellLayout.java revision 65d076b2ffe7ca96f014a95bd362c7d1ce004b97 
1/*
2 * Copyright (C) 2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.launcher3;
18
19import android.animation.Animator;
20import android.animation.AnimatorListenerAdapter;
21import android.animation.AnimatorSet;
22import android.animation.TimeInterpolator;
23import android.animation.ValueAnimator;
24import android.animation.ValueAnimator.AnimatorUpdateListener;
25import android.annotation.TargetApi;
26import android.content.Context;
27import android.content.res.Resources;
28import android.content.res.TypedArray;
29import android.graphics.Bitmap;
30import android.graphics.Canvas;
31import android.graphics.Color;
32import android.graphics.Paint;
33import android.graphics.Point;
34import android.graphics.Rect;
35import android.graphics.drawable.ColorDrawable;
36import android.graphics.drawable.Drawable;
37import android.os.Build;
38import android.os.Parcelable;
39import android.support.v4.view.ViewCompat;
40import android.util.AttributeSet;
41import android.util.Log;
42import android.util.SparseArray;
43import android.view.MotionEvent;
44import android.view.View;
45import android.view.ViewDebug;
46import android.view.ViewGroup;
47import android.view.accessibility.AccessibilityEvent;
48import android.view.animation.DecelerateInterpolator;
49
50import com.android.launcher3.FolderIcon.FolderRingAnimator;
51import com.android.launcher3.accessibility.DragAndDropAccessibilityDelegate;
52import com.android.launcher3.accessibility.FolderAccessibilityHelper;
53import com.android.launcher3.accessibility.WorkspaceAccessibilityHelper;
54import com.android.launcher3.util.Thunk;
55import com.android.launcher3.widget.PendingAddWidgetInfo;
56
57import java.util.ArrayList;
58import java.util.Arrays;
59import java.util.Collections;
60import java.util.Comparator;
61import java.util.HashMap;
62import java.util.Stack;
63
64public class CellLayout extends ViewGroup {
65    public static final int WORKSPACE_ACCESSIBILITY_DRAG = 2;
66    public static final int FOLDER_ACCESSIBILITY_DRAG = 1;
67
68    static final String TAG = "CellLayout";
69
70    private Launcher mLauncher;
71    @Thunk int mCellWidth;
72    @Thunk int mCellHeight;
73    private int mFixedCellWidth;
74    private int mFixedCellHeight;
75
76    @Thunk int mCountX;
77    @Thunk int mCountY;
78
79    private int mOriginalWidthGap;
80    private int mOriginalHeightGap;
81    @Thunk int mWidthGap;
82    @Thunk int mHeightGap;
83    private int mMaxGap;
84    private boolean mDropPending = false;
85    private boolean mIsDragTarget = true;
86
87    // These are temporary variables to prevent having to allocate a new object just to
88    // return an (x, y) value from helper functions. Do NOT use them to maintain other state.
89    private final int[] mTmpXY = new int[2];
90    @Thunk final int[] mTmpPoint = new int[2];
91    int[] mTempLocation = new int[2];
92
93    boolean[][] mOccupied;
94    boolean[][] mTmpOccupied;
95    private boolean mLastDownOnOccupiedCell = false;
96
97    private OnTouchListener mInterceptTouchListener;
98
99    private ArrayList<FolderRingAnimator> mFolderOuterRings = new ArrayList<FolderRingAnimator>();
100    private int[] mFolderLeaveBehindCell = {-1, -1};
101
102    private float FOREGROUND_ALPHA_DAMPER = 0.65f;
103    private int mForegroundAlpha = 0;
104    private float mBackgroundAlpha;
105    private float mBackgroundAlphaMultiplier = 1.0f;
106    private boolean mDrawBackground = true;
107
108    private Drawable mNormalBackground;
109    private Drawable mActiveGlowBackground;
110    private Drawable mOverScrollForegroundDrawable;
111    private Drawable mOverScrollLeft;
112    private Drawable mOverScrollRight;
113    private Rect mBackgroundRect;
114    private Rect mForegroundRect;
115    private int mForegroundPadding;
116
117    // These values allow a fixed measurement to be set on the CellLayout.
118    private int mFixedWidth = -1;
119    private int mFixedHeight = -1;
120
121    // If we're actively dragging something over this screen, mIsDragOverlapping is true
122    private boolean mIsDragOverlapping = false;
123
124    // These arrays are used to implement the drag visualization on x-large screens.
125    // They are used as circular arrays, indexed by mDragOutlineCurrent.
126    @Thunk Rect[] mDragOutlines = new Rect[4];
127    @Thunk float[] mDragOutlineAlphas = new float[mDragOutlines.length];
128    private InterruptibleInOutAnimator[] mDragOutlineAnims =
129            new InterruptibleInOutAnimator[mDragOutlines.length];
130
131    // Used as an index into the above 3 arrays; indicates which is the most current value.
132    private int mDragOutlineCurrent = 0;
133    private final Paint mDragOutlinePaint = new Paint();
134
135    private final FastBitmapView mTouchFeedbackView;
136
137    @Thunk HashMap<CellLayout.LayoutParams, Animator> mReorderAnimators = new
138            HashMap<CellLayout.LayoutParams, Animator>();
139    private HashMap<View, ReorderPreviewAnimation>
140            mShakeAnimators = new HashMap<View, ReorderPreviewAnimation>();
141
142    private boolean mItemPlacementDirty = false;
143
144    // When a drag operation is in progress, holds the nearest cell to the touch point
145    private final int[] mDragCell = new int[2];
146
147    private boolean mDragging = false;
148
149    private TimeInterpolator mEaseOutInterpolator;
150    private ShortcutAndWidgetContainer mShortcutsAndWidgets;
151
152    private boolean mIsHotseat = false;
153    private float mHotseatScale = 1f;
154
155    public static final int MODE_SHOW_REORDER_HINT = 0;
156    public static final int MODE_DRAG_OVER = 1;
157    public static final int MODE_ON_DROP = 2;
158    public static final int MODE_ON_DROP_EXTERNAL = 3;
159    public static final int MODE_ACCEPT_DROP = 4;
160    private static final boolean DESTRUCTIVE_REORDER = false;
161    private static final boolean DEBUG_VISUALIZE_OCCUPIED = false;
162
163    static final int LANDSCAPE = 0;
164    static final int PORTRAIT = 1;
165
166    private static final float REORDER_PREVIEW_MAGNITUDE = 0.12f;
167    private static final int REORDER_ANIMATION_DURATION = 150;
168    @Thunk float mReorderPreviewAnimationMagnitude;
169
170    private ArrayList<View> mIntersectingViews = new ArrayList<View>();
171    private Rect mOccupiedRect = new Rect();
172    private int[] mDirectionVector = new int[2];
173    int[] mPreviousReorderDirection = new int[2];
174    private static final int INVALID_DIRECTION = -100;
175    private DropTarget.DragEnforcer mDragEnforcer;
176
177    private Rect mTempRect = new Rect();
178
179    private final static Paint sPaint = new Paint();
180
181    // Related to accessible drag and drop
182    private DragAndDropAccessibilityDelegate mTouchHelper;
183    private boolean mUseTouchHelper = false;
184
185    public CellLayout(Context context) {
186        this(context, null);
187    }
188
189    public CellLayout(Context context, AttributeSet attrs) {
190        this(context, attrs, 0);
191    }
192
193    public CellLayout(Context context, AttributeSet attrs, int defStyle) {
194        super(context, attrs, defStyle);
195        mDragEnforcer = new DropTarget.DragEnforcer(context);
196
197        // A ViewGroup usually does not draw, but CellLayout needs to draw a rectangle to show
198        // the user where a dragged item will land when dropped.
199        setWillNotDraw(false);
200        setClipToPadding(false);
201        mLauncher = (Launcher) context;
202
203        LauncherAppState app = LauncherAppState.getInstance();
204        DeviceProfile grid = app.getDynamicGrid().getDeviceProfile();
205        TypedArray a = context.obtainStyledAttributes(attrs, R.styleable.CellLayout, defStyle, 0);
206
207        mCellWidth = mCellHeight = -1;
208        mFixedCellWidth = mFixedCellHeight = -1;
209        mWidthGap = mOriginalWidthGap = 0;
210        mHeightGap = mOriginalHeightGap = 0;
211        mMaxGap = Integer.MAX_VALUE;
212        mCountX = (int) grid.numColumns;
213        mCountY = (int) grid.numRows;
214        mOccupied = new boolean[mCountX][mCountY];
215        mTmpOccupied = new boolean[mCountX][mCountY];
216        mPreviousReorderDirection[0] = INVALID_DIRECTION;
217        mPreviousReorderDirection[1] = INVALID_DIRECTION;
218
219        a.recycle();
220
221        setAlwaysDrawnWithCacheEnabled(false);
222
223        final Resources res = getResources();
224        mHotseatScale = (float) grid.hotseatIconSizePx / grid.iconSizePx;
225
226        mNormalBackground = res.getDrawable(R.drawable.screenpanel);
227        mActiveGlowBackground = res.getDrawable(R.drawable.screenpanel_hover);
228
229        mOverScrollLeft = res.getDrawable(R.drawable.overscroll_glow_left);
230        mOverScrollRight = res.getDrawable(R.drawable.overscroll_glow_right);
231        mForegroundPadding =
232                res.getDimensionPixelSize(R.dimen.workspace_overscroll_drawable_padding);
233
234        mReorderPreviewAnimationMagnitude = (REORDER_PREVIEW_MAGNITUDE *
235                grid.iconSizePx);
236
237        mNormalBackground.setFilterBitmap(true);
238        mActiveGlowBackground.setFilterBitmap(true);
239
240        // Initialize the data structures used for the drag visualization.
241        mEaseOutInterpolator = new DecelerateInterpolator(2.5f); // Quint ease out
242        mDragCell[0] = mDragCell[1] = -1;
243        for (int i = 0; i < mDragOutlines.length; i++) {
244            mDragOutlines[i] = new Rect(-1, -1, -1, -1);
245        }
246
247        // When dragging things around the home screens, we show a green outline of
248        // where the item will land. The outlines gradually fade out, leaving a trail
249        // behind the drag path.
250        // Set up all the animations that are used to implement this fading.
251        final int duration = res.getInteger(R.integer.config_dragOutlineFadeTime);
252        final float fromAlphaValue = 0;
253        final float toAlphaValue = (float)res.getInteger(R.integer.config_dragOutlineMaxAlpha);
254
255        Arrays.fill(mDragOutlineAlphas, fromAlphaValue);
256
257        for (int i = 0; i < mDragOutlineAnims.length; i++) {
258            final InterruptibleInOutAnimator anim =
259                new InterruptibleInOutAnimator(this, duration, fromAlphaValue, toAlphaValue);
260            anim.getAnimator().setInterpolator(mEaseOutInterpolator);
261            final int thisIndex = i;
262            anim.getAnimator().addUpdateListener(new AnimatorUpdateListener() {
263                public void onAnimationUpdate(ValueAnimator animation) {
264                    final Bitmap outline = (Bitmap)anim.getTag();
265
266                    // If an animation is started and then stopped very quickly, we can still
267                    // get spurious updates we've cleared the tag. Guard against this.
268                    if (outline == null) {
269                        @SuppressWarnings("all") // suppress dead code warning
270                        final boolean debug = false;
271                        if (debug) {
272                            Object val = animation.getAnimatedValue();
273                            Log.d(TAG, "anim " + thisIndex + " update: " + val +
274                                     ", isStopped " + anim.isStopped());
275                        }
276                        // Try to prevent it from continuing to run
277                        animation.cancel();
278                    } else {
279                        mDragOutlineAlphas[thisIndex] = (Float) animation.getAnimatedValue();
280                        CellLayout.this.invalidate(mDragOutlines[thisIndex]);
281                    }
282                }
283            });
284            // The animation holds a reference to the drag outline bitmap as long is it's
285            // running. This way the bitmap can be GCed when the animations are complete.
286            anim.getAnimator().addListener(new AnimatorListenerAdapter() {
287                @Override
288                public void onAnimationEnd(Animator animation) {
289                    if ((Float) ((ValueAnimator) animation).getAnimatedValue() == 0f) {
290                        anim.setTag(null);
291                    }
292                }
293            });
294            mDragOutlineAnims[i] = anim;
295        }
296
297        mBackgroundRect = new Rect();
298        mForegroundRect = new Rect();
299
300        mShortcutsAndWidgets = new ShortcutAndWidgetContainer(context);
301        mShortcutsAndWidgets.setCellDimensions(mCellWidth, mCellHeight, mWidthGap, mHeightGap,
302                mCountX, mCountY);
303
304        mTouchFeedbackView = new FastBitmapView(context);
305        // Make the feedback view large enough to hold the blur bitmap.
306        addView(mTouchFeedbackView, (int) (grid.cellWidthPx * 1.5), (int) (grid.cellHeightPx * 1.5));
307        addView(mShortcutsAndWidgets);
308    }
309
310    @TargetApi(Build.VERSION_CODES.LOLLIPOP)
311    public void enableAccessibleDrag(boolean enable, int dragType) {
312        mUseTouchHelper = enable;
313        Log.e("HIGHRES", getParent() + "  " + enable + "  " + dragType, new Exception());
314        if (!enable) {
315            ViewCompat.setAccessibilityDelegate(this, null);
316            setImportantForAccessibility(IMPORTANT_FOR_ACCESSIBILITY_NO);
317            getShortcutsAndWidgets().setImportantForAccessibility(IMPORTANT_FOR_ACCESSIBILITY_NO);
318            setOnClickListener(mLauncher);
319        } else {
320            if (dragType == WORKSPACE_ACCESSIBILITY_DRAG &&
321                    !(mTouchHelper instanceof WorkspaceAccessibilityHelper)) {
322                mTouchHelper = new WorkspaceAccessibilityHelper(this);
323            } else if (dragType == FOLDER_ACCESSIBILITY_DRAG &&
324                    !(mTouchHelper instanceof FolderAccessibilityHelper)) {
325                mTouchHelper = new FolderAccessibilityHelper(this);
326            }
327            ViewCompat.setAccessibilityDelegate(this, mTouchHelper);
328            setImportantForAccessibility(IMPORTANT_FOR_ACCESSIBILITY_YES);
329            getShortcutsAndWidgets().setImportantForAccessibility(IMPORTANT_FOR_ACCESSIBILITY_YES);
330            setOnClickListener(mTouchHelper);
331        }
332
333        // Invalidate the accessibility hierarchy
334        if (getParent() != null) {
335            getParent().notifySubtreeAccessibilityStateChanged(
336                    this, this, AccessibilityEvent.CONTENT_CHANGE_TYPE_SUBTREE);
337        }
338    }
339
340    @Override
341    public boolean dispatchHoverEvent(MotionEvent event) {
342        // Always attempt to dispatch hover events to accessibility first.
343        if (mUseTouchHelper && mTouchHelper.dispatchHoverEvent(event)) {
344            return true;
345        }
346        return super.dispatchHoverEvent(event);
347    }
348
349    @Override
350    public boolean onInterceptTouchEvent(MotionEvent ev) {
351        if (mUseTouchHelper ||
352                (mInterceptTouchListener != null && mInterceptTouchListener.onTouch(this, ev))) {
353            return true;
354        }
355        return false;
356    }
357
358    public void enableHardwareLayer(boolean hasLayer) {
359        mShortcutsAndWidgets.setLayerType(hasLayer ? LAYER_TYPE_HARDWARE : LAYER_TYPE_NONE, sPaint);
360    }
361
362    public void buildHardwareLayer() {
363        mShortcutsAndWidgets.buildLayer();
364    }
365
366    public float getChildrenScale() {
367        return mIsHotseat ? mHotseatScale : 1.0f;
368    }
369
370    public void setCellDimensions(int width, int height) {
371        mFixedCellWidth = mCellWidth = width;
372        mFixedCellHeight = mCellHeight = height;
373        mShortcutsAndWidgets.setCellDimensions(mCellWidth, mCellHeight, mWidthGap, mHeightGap,
374                mCountX, mCountY);
375    }
376
377    public void setGridSize(int x, int y) {
378        mCountX = x;
379        mCountY = y;
380        mOccupied = new boolean[mCountX][mCountY];
381        mTmpOccupied = new boolean[mCountX][mCountY];
382        mTempRectStack.clear();
383        mShortcutsAndWidgets.setCellDimensions(mCellWidth, mCellHeight, mWidthGap, mHeightGap,
384                mCountX, mCountY);
385        requestLayout();
386    }
387
388    // Set whether or not to invert the layout horizontally if the layout is in RTL mode.
389    public void setInvertIfRtl(boolean invert) {
390        mShortcutsAndWidgets.setInvertIfRtl(invert);
391    }
392
393    public void setDropPending(boolean pending) {
394        mDropPending = pending;
395    }
396
397    public boolean isDropPending() {
398        return mDropPending;
399    }
400
401    void setOverScrollAmount(float r, boolean left) {
402        if (left && mOverScrollForegroundDrawable != mOverScrollLeft) {
403            mOverScrollForegroundDrawable = mOverScrollLeft;
404        } else if (!left && mOverScrollForegroundDrawable != mOverScrollRight) {
405            mOverScrollForegroundDrawable = mOverScrollRight;
406        }
407
408        r *= FOREGROUND_ALPHA_DAMPER;
409        mForegroundAlpha = (int) Math.round((r * 255));
410        mOverScrollForegroundDrawable.setAlpha(mForegroundAlpha);
411        invalidate();
412    }
413
414    void setPressedIcon(BubbleTextView icon, Bitmap background, int padding) {
415        if (icon == null || background == null) {
416            mTouchFeedbackView.setBitmap(null);
417            mTouchFeedbackView.animate().cancel();
418        } else {
419            int offset = getMeasuredWidth() - getPaddingLeft() - getPaddingRight()
420                    - (mCountX * mCellWidth);
421            mTouchFeedbackView.setTranslationX(icon.getLeft() + (int) Math.ceil(offset / 2f)
422                    - padding);
423            mTouchFeedbackView.setTranslationY(icon.getTop() - padding);
424            if (mTouchFeedbackView.setBitmap(background)) {
425                mTouchFeedbackView.setAlpha(0);
426                mTouchFeedbackView.animate().alpha(1)
427                    .setDuration(FastBitmapDrawable.CLICK_FEEDBACK_DURATION)
428                    .setInterpolator(FastBitmapDrawable.CLICK_FEEDBACK_INTERPOLATOR)
429                    .start();
430            }
431        }
432    }
433
434    void disableBackground() {
435        mDrawBackground = false;
436    }
437
438    void disableDragTarget() {
439        mIsDragTarget = false;
440    }
441
442    boolean isDragTarget() {
443        return mIsDragTarget;
444    }
445
446    void setIsDragOverlapping(boolean isDragOverlapping) {
447        if (mIsDragOverlapping != isDragOverlapping) {
448            mIsDragOverlapping = isDragOverlapping;
449            invalidate();
450        }
451    }
452
453    boolean getIsDragOverlapping() {
454        return mIsDragOverlapping;
455    }
456
457    @Override
458    protected void onDraw(Canvas canvas) {
459        // When we're large, we are either drawn in a "hover" state (ie when dragging an item to
460        // a neighboring page) or with just a normal background (if backgroundAlpha > 0.0f)
461        // When we're small, we are either drawn normally or in the "accepts drops" state (during
462        // a drag). However, we also drag the mini hover background *over* one of those two
463        // backgrounds
464        if (mDrawBackground && mBackgroundAlpha > 0.0f) {
465            Drawable bg;
466
467            if (mIsDragOverlapping) {
468                // In the mini case, we draw the active_glow bg *over* the active background
469                bg = mActiveGlowBackground;
470            } else {
471                bg = mNormalBackground;
472            }
473
474            bg.setAlpha((int) (mBackgroundAlpha * mBackgroundAlphaMultiplier * 255));
475            bg.setBounds(mBackgroundRect);
476            bg.draw(canvas);
477        }
478
479        final Paint paint = mDragOutlinePaint;
480        for (int i = 0; i < mDragOutlines.length; i++) {
481            final float alpha = mDragOutlineAlphas[i];
482            if (alpha > 0) {
483                final Rect r = mDragOutlines[i];
484                mTempRect.set(r);
485                Utilities.scaleRectAboutCenter(mTempRect, getChildrenScale());
486                final Bitmap b = (Bitmap) mDragOutlineAnims[i].getTag();
487                paint.setAlpha((int)(alpha + .5f));
488                canvas.drawBitmap(b, null, mTempRect, paint);
489            }
490        }
491
492        if (DEBUG_VISUALIZE_OCCUPIED) {
493            int[] pt = new int[2];
494            ColorDrawable cd = new ColorDrawable(Color.RED);
495            cd.setBounds(0, 0,  mCellWidth, mCellHeight);
496            for (int i = 0; i < mCountX; i++) {
497                for (int j = 0; j < mCountY; j++) {
498                    if (mOccupied[i][j]) {
499                        cellToPoint(i, j, pt);
500                        canvas.save();
501                        canvas.translate(pt[0], pt[1]);
502                        cd.draw(canvas);
503                        canvas.restore();
504                    }
505                }
506            }
507        }
508
509        int previewOffset = FolderRingAnimator.sPreviewSize;
510
511        // The folder outer / inner ring image(s)
512        LauncherAppState app = LauncherAppState.getInstance();
513        DeviceProfile grid = app.getDynamicGrid().getDeviceProfile();
514        for (int i = 0; i < mFolderOuterRings.size(); i++) {
515            FolderRingAnimator fra = mFolderOuterRings.get(i);
516
517            Drawable d;
518            int width, height;
519            cellToPoint(fra.mCellX, fra.mCellY, mTempLocation);
520            View child = getChildAt(fra.mCellX, fra.mCellY);
521
522            if (child != null) {
523                int centerX = mTempLocation[0] + mCellWidth / 2;
524                int centerY = mTempLocation[1] + previewOffset / 2 +
525                        child.getPaddingTop() + grid.folderBackgroundOffset;
526
527                // Draw outer ring, if it exists
528                if (FolderIcon.HAS_OUTER_RING) {
529                    d = FolderRingAnimator.sSharedOuterRingDrawable;
530                    width = (int) (fra.getOuterRingSize() * getChildrenScale());
531                    height = width;
532                    canvas.save();
533                    canvas.translate(centerX - width / 2, centerY - height / 2);
534                    d.setBounds(0, 0, width, height);
535                    d.draw(canvas);
536                    canvas.restore();
537                }
538
539                // Draw inner ring
540                d = FolderRingAnimator.sSharedInnerRingDrawable;
541                width = (int) (fra.getInnerRingSize() * getChildrenScale());
542                height = width;
543                canvas.save();
544                canvas.translate(centerX - width / 2, centerY - width / 2);
545                d.setBounds(0, 0, width, height);
546                d.draw(canvas);
547                canvas.restore();
548            }
549        }
550
551        if (mFolderLeaveBehindCell[0] >= 0 && mFolderLeaveBehindCell[1] >= 0) {
552            Drawable d = FolderIcon.sSharedFolderLeaveBehind;
553            int width = d.getIntrinsicWidth();
554            int height = d.getIntrinsicHeight();
555
556            cellToPoint(mFolderLeaveBehindCell[0], mFolderLeaveBehindCell[1], mTempLocation);
557            View child = getChildAt(mFolderLeaveBehindCell[0], mFolderLeaveBehindCell[1]);
558            if (child != null) {
559                int centerX = mTempLocation[0] + mCellWidth / 2;
560                int centerY = mTempLocation[1] + previewOffset / 2 +
561                        child.getPaddingTop() + grid.folderBackgroundOffset;
562
563                canvas.save();
564                canvas.translate(centerX - width / 2, centerY - width / 2);
565                d.setBounds(0, 0, width, height);
566                d.draw(canvas);
567                canvas.restore();
568            }
569        }
570    }
571
572    @Override
573    protected void dispatchDraw(Canvas canvas) {
574        super.dispatchDraw(canvas);
575        if (mForegroundAlpha > 0) {
576            mOverScrollForegroundDrawable.setBounds(mForegroundRect);
577            mOverScrollForegroundDrawable.draw(canvas);
578        }
579    }
580
581    public void showFolderAccept(FolderRingAnimator fra) {
582        mFolderOuterRings.add(fra);
583    }
584
585    public void hideFolderAccept(FolderRingAnimator fra) {
586        if (mFolderOuterRings.contains(fra)) {
587            mFolderOuterRings.remove(fra);
588        }
589        invalidate();
590    }
591
592    public void setFolderLeaveBehindCell(int x, int y) {
593        mFolderLeaveBehindCell[0] = x;
594        mFolderLeaveBehindCell[1] = y;
595        invalidate();
596    }
597
598    public void clearFolderLeaveBehind() {
599        mFolderLeaveBehindCell[0] = -1;
600        mFolderLeaveBehindCell[1] = -1;
601        invalidate();
602    }
603
604    @Override
605    public boolean shouldDelayChildPressedState() {
606        return false;
607    }
608
609    public void restoreInstanceState(SparseArray<Parcelable> states) {
610        try {
611            dispatchRestoreInstanceState(states);
612        } catch (IllegalArgumentException ex) {
613            if (LauncherAppState.isDogfoodBuild()) {
614                throw ex;
615            }
616            // Mismatched viewId / viewType preventing restore. Skip restore on production builds.
617            Log.e(TAG, "Ignoring an error while restoring a view instance state", ex);
618        }
619    }
620
621    @Override
622    public void cancelLongPress() {
623        super.cancelLongPress();
624
625        // Cancel long press for all children
626        final int count = getChildCount();
627        for (int i = 0; i < count; i++) {
628            final View child = getChildAt(i);
629            child.cancelLongPress();
630        }
631    }
632
633    public void setOnInterceptTouchListener(View.OnTouchListener listener) {
634        mInterceptTouchListener = listener;
635    }
636
637    public int getCountX() {
638        return mCountX;
639    }
640
641    public int getCountY() {
642        return mCountY;
643    }
644
645    public void setIsHotseat(boolean isHotseat) {
646        mIsHotseat = isHotseat;
647        mShortcutsAndWidgets.setIsHotseat(isHotseat);
648    }
649
650    public boolean isHotseat() {
651        return mIsHotseat;
652    }
653
654    public boolean addViewToCellLayout(View child, int index, int childId, LayoutParams params,
655            boolean markCells) {
656        final LayoutParams lp = params;
657
658        // Hotseat icons - remove text
659        if (child instanceof BubbleTextView) {
660            BubbleTextView bubbleChild = (BubbleTextView) child;
661            bubbleChild.setTextVisibility(!mIsHotseat);
662        }
663
664        child.setScaleX(getChildrenScale());
665        child.setScaleY(getChildrenScale());
666
667        // Generate an id for each view, this assumes we have at most 256x256 cells
668        // per workspace screen
669        if (lp.cellX >= 0 && lp.cellX <= mCountX - 1 && lp.cellY >= 0 && lp.cellY <= mCountY - 1) {
670            // If the horizontal or vertical span is set to -1, it is taken to
671            // mean that it spans the extent of the CellLayout
672            if (lp.cellHSpan < 0) lp.cellHSpan = mCountX;
673            if (lp.cellVSpan < 0) lp.cellVSpan = mCountY;
674
675            child.setId(childId);
676            mShortcutsAndWidgets.addView(child, index, lp);
677
678            if (markCells) markCellsAsOccupiedForView(child);
679
680            return true;
681        }
682        return false;
683    }
684
685    @Override
686    public void removeAllViews() {
687        clearOccupiedCells();
688        mShortcutsAndWidgets.removeAllViews();
689    }
690
691    @Override
692    public void removeAllViewsInLayout() {
693        if (mShortcutsAndWidgets.getChildCount() > 0) {
694            clearOccupiedCells();
695            mShortcutsAndWidgets.removeAllViewsInLayout();
696        }
697    }
698
699    @Override
700    public void removeView(View view) {
701        markCellsAsUnoccupiedForView(view);
702        mShortcutsAndWidgets.removeView(view);
703    }
704
705    @Override
706    public void removeViewAt(int index) {
707        markCellsAsUnoccupiedForView(mShortcutsAndWidgets.getChildAt(index));
708        mShortcutsAndWidgets.removeViewAt(index);
709    }
710
711    @Override
712    public void removeViewInLayout(View view) {
713        markCellsAsUnoccupiedForView(view);
714        mShortcutsAndWidgets.removeViewInLayout(view);
715    }
716
717    @Override
718    public void removeViews(int start, int count) {
719        for (int i = start; i < start + count; i++) {
720            markCellsAsUnoccupiedForView(mShortcutsAndWidgets.getChildAt(i));
721        }
722        mShortcutsAndWidgets.removeViews(start, count);
723    }
724
725    @Override
726    public void removeViewsInLayout(int start, int count) {
727        for (int i = start; i < start + count; i++) {
728            markCellsAsUnoccupiedForView(mShortcutsAndWidgets.getChildAt(i));
729        }
730        mShortcutsAndWidgets.removeViewsInLayout(start, count);
731    }
732
733    /**
734     * Given a point, return the cell that strictly encloses that point
735     * @param x X coordinate of the point
736     * @param y Y coordinate of the point
737     * @param result Array of 2 ints to hold the x and y coordinate of the cell
738     */
739    public void pointToCellExact(int x, int y, int[] result) {
740        final int hStartPadding = getPaddingLeft();
741        final int vStartPadding = getPaddingTop();
742
743        result[0] = (x - hStartPadding) / (mCellWidth + mWidthGap);
744        result[1] = (y - vStartPadding) / (mCellHeight + mHeightGap);
745
746        final int xAxis = mCountX;
747        final int yAxis = mCountY;
748
749        if (result[0] < 0) result[0] = 0;
750        if (result[0] >= xAxis) result[0] = xAxis - 1;
751        if (result[1] < 0) result[1] = 0;
752        if (result[1] >= yAxis) result[1] = yAxis - 1;
753    }
754
755    /**
756     * Given a point, return the cell that most closely encloses that point
757     * @param x X coordinate of the point
758     * @param y Y coordinate of the point
759     * @param result Array of 2 ints to hold the x and y coordinate of the cell
760     */
761    void pointToCellRounded(int x, int y, int[] result) {
762        pointToCellExact(x + (mCellWidth / 2), y + (mCellHeight / 2), result);
763    }
764
765    /**
766     * Given a cell coordinate, return the point that represents the upper left corner of that cell
767     *
768     * @param cellX X coordinate of the cell
769     * @param cellY Y coordinate of the cell
770     *
771     * @param result Array of 2 ints to hold the x and y coordinate of the point
772     */
773    void cellToPoint(int cellX, int cellY, int[] result) {
774        final int hStartPadding = getPaddingLeft();
775        final int vStartPadding = getPaddingTop();
776
777        result[0] = hStartPadding + cellX * (mCellWidth + mWidthGap);
778        result[1] = vStartPadding + cellY * (mCellHeight + mHeightGap);
779    }
780
781    /**
782     * Given a cell coordinate, return the point that represents the center of the cell
783     *
784     * @param cellX X coordinate of the cell
785     * @param cellY Y coordinate of the cell
786     *
787     * @param result Array of 2 ints to hold the x and y coordinate of the point
788     */
789    void cellToCenterPoint(int cellX, int cellY, int[] result) {
790        regionToCenterPoint(cellX, cellY, 1, 1, result);
791    }
792
793    /**
794     * Given a cell coordinate and span return the point that represents the center of the regio
795     *
796     * @param cellX X coordinate of the cell
797     * @param cellY Y coordinate of the cell
798     *
799     * @param result Array of 2 ints to hold the x and y coordinate of the point
800     */
801    void regionToCenterPoint(int cellX, int cellY, int spanX, int spanY, int[] result) {
802        final int hStartPadding = getPaddingLeft();
803        final int vStartPadding = getPaddingTop();
804        result[0] = hStartPadding + cellX * (mCellWidth + mWidthGap) +
805                (spanX * mCellWidth + (spanX - 1) * mWidthGap) / 2;
806        result[1] = vStartPadding + cellY * (mCellHeight + mHeightGap) +
807                (spanY * mCellHeight + (spanY - 1) * mHeightGap) / 2;
808    }
809
810     /**
811     * Given a cell coordinate and span fills out a corresponding pixel rect
812     *
813     * @param cellX X coordinate of the cell
814     * @param cellY Y coordinate of the cell
815     * @param result Rect in which to write the result
816     */
817     void regionToRect(int cellX, int cellY, int spanX, int spanY, Rect result) {
818        final int hStartPadding = getPaddingLeft();
819        final int vStartPadding = getPaddingTop();
820        final int left = hStartPadding + cellX * (mCellWidth + mWidthGap);
821        final int top = vStartPadding + cellY * (mCellHeight + mHeightGap);
822        result.set(left, top, left + (spanX * mCellWidth + (spanX - 1) * mWidthGap),
823                top + (spanY * mCellHeight + (spanY - 1) * mHeightGap));
824    }
825
826    public float getDistanceFromCell(float x, float y, int[] cell) {
827        cellToCenterPoint(cell[0], cell[1], mTmpPoint);
828        return (float) Math.hypot(x - mTmpPoint[0], y - mTmpPoint[1]);
829    }
830
831    int getCellWidth() {
832        return mCellWidth;
833    }
834
835    int getCellHeight() {
836        return mCellHeight;
837    }
838
839    int getWidthGap() {
840        return mWidthGap;
841    }
842
843    int getHeightGap() {
844        return mHeightGap;
845    }
846
847    public void setFixedSize(int width, int height) {
848        mFixedWidth = width;
849        mFixedHeight = height;
850    }
851
852    @Override
853    protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
854        LauncherAppState app = LauncherAppState.getInstance();
855        DeviceProfile grid = app.getDynamicGrid().getDeviceProfile();
856
857        int widthSpecMode = MeasureSpec.getMode(widthMeasureSpec);
858        int heightSpecMode = MeasureSpec.getMode(heightMeasureSpec);
859        int widthSize = MeasureSpec.getSize(widthMeasureSpec);
860        int heightSize =  MeasureSpec.getSize(heightMeasureSpec);
861        int childWidthSize = widthSize - (getPaddingLeft() + getPaddingRight());
862        int childHeightSize = heightSize - (getPaddingTop() + getPaddingBottom());
863        if (mFixedCellWidth < 0 || mFixedCellHeight < 0) {
864            int cw = grid.calculateCellWidth(childWidthSize, mCountX);
865            int ch = grid.calculateCellHeight(childHeightSize, mCountY);
866            if (cw != mCellWidth || ch != mCellHeight) {
867                mCellWidth = cw;
868                mCellHeight = ch;
869                mShortcutsAndWidgets.setCellDimensions(mCellWidth, mCellHeight, mWidthGap,
870                        mHeightGap, mCountX, mCountY);
871            }
872        }
873
874        int newWidth = childWidthSize;
875        int newHeight = childHeightSize;
876        if (mFixedWidth > 0 && mFixedHeight > 0) {
877            newWidth = mFixedWidth;
878            newHeight = mFixedHeight;
879        } else if (widthSpecMode == MeasureSpec.UNSPECIFIED || heightSpecMode == MeasureSpec.UNSPECIFIED) {
880            throw new RuntimeException("CellLayout cannot have UNSPECIFIED dimensions");
881        }
882
883        int numWidthGaps = mCountX - 1;
884        int numHeightGaps = mCountY - 1;
885
886        if (mOriginalWidthGap < 0 || mOriginalHeightGap < 0) {
887            int hSpace = childWidthSize;
888            int vSpace = childHeightSize;
889            int hFreeSpace = hSpace - (mCountX * mCellWidth);
890            int vFreeSpace = vSpace - (mCountY * mCellHeight);
891            mWidthGap = Math.min(mMaxGap, numWidthGaps > 0 ? (hFreeSpace / numWidthGaps) : 0);
892            mHeightGap = Math.min(mMaxGap,numHeightGaps > 0 ? (vFreeSpace / numHeightGaps) : 0);
893            mShortcutsAndWidgets.setCellDimensions(mCellWidth, mCellHeight, mWidthGap,
894                    mHeightGap, mCountX, mCountY);
895        } else {
896            mWidthGap = mOriginalWidthGap;
897            mHeightGap = mOriginalHeightGap;
898        }
899        int count = getChildCount();
900        int maxWidth = 0;
901        int maxHeight = 0;
902        for (int i = 0; i < count; i++) {
903            View child = getChildAt(i);
904            int childWidthMeasureSpec = MeasureSpec.makeMeasureSpec(newWidth,
905                    MeasureSpec.EXACTLY);
906            int childheightMeasureSpec = MeasureSpec.makeMeasureSpec(newHeight,
907                    MeasureSpec.EXACTLY);
908            child.measure(childWidthMeasureSpec, childheightMeasureSpec);
909            maxWidth = Math.max(maxWidth, child.getMeasuredWidth());
910            maxHeight = Math.max(maxHeight, child.getMeasuredHeight());
911        }
912        if (mFixedWidth > 0 && mFixedHeight > 0) {
913            setMeasuredDimension(maxWidth, maxHeight);
914        } else {
915            setMeasuredDimension(widthSize, heightSize);
916        }
917    }
918
919    @Override
920    protected void onLayout(boolean changed, int l, int t, int r, int b) {
921        int offset = getMeasuredWidth() - getPaddingLeft() - getPaddingRight() -
922                (mCountX * mCellWidth);
923        int left = getPaddingLeft() + (int) Math.ceil(offset / 2f);
924        int top = getPaddingTop();
925        int count = getChildCount();
926        for (int i = 0; i < count; i++) {
927            View child = getChildAt(i);
928            child.layout(left, top,
929                    left + r - l,
930                    top + b - t);
931        }
932    }
933
934    @Override
935    protected void onSizeChanged(int w, int h, int oldw, int oldh) {
936        super.onSizeChanged(w, h, oldw, oldh);
937
938        // Expand the background drawing bounds by the padding baked into the background drawable
939        Rect padding = new Rect();
940        mNormalBackground.getPadding(padding);
941        mBackgroundRect.set(-padding.left, -padding.top, w + padding.right, h + padding.bottom);
942
943        mForegroundRect.set(mForegroundPadding, mForegroundPadding,
944                w - mForegroundPadding, h - mForegroundPadding);
945    }
946
947    @Override
948    protected void setChildrenDrawingCacheEnabled(boolean enabled) {
949        mShortcutsAndWidgets.setChildrenDrawingCacheEnabled(enabled);
950    }
951
952    @Override
953    protected void setChildrenDrawnWithCacheEnabled(boolean enabled) {
954        mShortcutsAndWidgets.setChildrenDrawnWithCacheEnabled(enabled);
955    }
956
957    public float getBackgroundAlpha() {
958        return mBackgroundAlpha;
959    }
960
961    public void setBackgroundAlphaMultiplier(float multiplier) {
962        if (mBackgroundAlphaMultiplier != multiplier) {
963            mBackgroundAlphaMultiplier = multiplier;
964            invalidate();
965        }
966    }
967
968    public float getBackgroundAlphaMultiplier() {
969        return mBackgroundAlphaMultiplier;
970    }
971
972    public void setBackgroundAlpha(float alpha) {
973        if (mBackgroundAlpha != alpha) {
974            mBackgroundAlpha = alpha;
975            invalidate();
976        }
977    }
978
979    public void setShortcutAndWidgetAlpha(float alpha) {
980        mShortcutsAndWidgets.setAlpha(alpha);
981    }
982
983    public ShortcutAndWidgetContainer getShortcutsAndWidgets() {
984        return mShortcutsAndWidgets;
985    }
986
987    public View getChildAt(int x, int y) {
988        return mShortcutsAndWidgets.getChildAt(x, y);
989    }
990
991    public boolean animateChildToPosition(final View child, int cellX, int cellY, int duration,
992            int delay, boolean permanent, boolean adjustOccupied) {
993        ShortcutAndWidgetContainer clc = getShortcutsAndWidgets();
994        boolean[][] occupied = mOccupied;
995        if (!permanent) {
996            occupied = mTmpOccupied;
997        }
998
999        if (clc.indexOfChild(child) != -1) {
1000            final LayoutParams lp = (LayoutParams) child.getLayoutParams();
1001            final ItemInfo info = (ItemInfo) child.getTag();
1002
1003            // We cancel any existing animations
1004            if (mReorderAnimators.containsKey(lp)) {
1005                mReorderAnimators.get(lp).cancel();
1006                mReorderAnimators.remove(lp);
1007            }
1008
1009            final int oldX = lp.x;
1010            final int oldY = lp.y;
1011            if (adjustOccupied) {
1012                occupied[lp.cellX][lp.cellY] = false;
1013                occupied[cellX][cellY] = true;
1014            }
1015            lp.isLockedToGrid = true;
1016            if (permanent) {
1017                lp.cellX = info.cellX = cellX;
1018                lp.cellY = info.cellY = cellY;
1019            } else {
1020                lp.tmpCellX = cellX;
1021                lp.tmpCellY = cellY;
1022            }
1023            clc.setupLp(lp);
1024            lp.isLockedToGrid = false;
1025            final int newX = lp.x;
1026            final int newY = lp.y;
1027
1028            lp.x = oldX;
1029            lp.y = oldY;
1030
1031            // Exit early if we're not actually moving the view
1032            if (oldX == newX && oldY == newY) {
1033                lp.isLockedToGrid = true;
1034                return true;
1035            }
1036
1037            ValueAnimator va = LauncherAnimUtils.ofFloat(child, 0f, 1f);
1038            va.setDuration(duration);
1039            mReorderAnimators.put(lp, va);
1040
1041            va.addUpdateListener(new AnimatorUpdateListener() {
1042                @Override
1043                public void onAnimationUpdate(ValueAnimator animation) {
1044                    float r = ((Float) animation.getAnimatedValue()).floatValue();
1045                    lp.x = (int) ((1 - r) * oldX + r * newX);
1046                    lp.y = (int) ((1 - r) * oldY + r * newY);
1047                    child.requestLayout();
1048                }
1049            });
1050            va.addListener(new AnimatorListenerAdapter() {
1051                boolean cancelled = false;
1052                public void onAnimationEnd(Animator animation) {
1053                    // If the animation was cancelled, it means that another animation
1054                    // has interrupted this one, and we don't want to lock the item into
1055                    // place just yet.
1056                    if (!cancelled) {
1057                        lp.isLockedToGrid = true;
1058                        child.requestLayout();
1059                    }
1060                    if (mReorderAnimators.containsKey(lp)) {
1061                        mReorderAnimators.remove(lp);
1062                    }
1063                }
1064                public void onAnimationCancel(Animator animation) {
1065                    cancelled = true;
1066                }
1067            });
1068            va.setStartDelay(delay);
1069            va.start();
1070            return true;
1071        }
1072        return false;
1073    }
1074
1075    void visualizeDropLocation(View v, Bitmap dragOutline, int originX, int originY, int cellX,
1076            int cellY, int spanX, int spanY, boolean resize, Point dragOffset, Rect dragRegion) {
1077        final int oldDragCellX = mDragCell[0];
1078        final int oldDragCellY = mDragCell[1];
1079
1080        if (dragOutline == null && v == null) {
1081            return;
1082        }
1083
1084        if (cellX != oldDragCellX || cellY != oldDragCellY) {
1085            mDragCell[0] = cellX;
1086            mDragCell[1] = cellY;
1087            // Find the top left corner of the rect the object will occupy
1088            final int[] topLeft = mTmpPoint;
1089            cellToPoint(cellX, cellY, topLeft);
1090
1091            int left = topLeft[0];
1092            int top = topLeft[1];
1093
1094            if (v != null && dragOffset == null) {
1095                // When drawing the drag outline, it did not account for margin offsets
1096                // added by the view's parent.
1097                MarginLayoutParams lp = (MarginLayoutParams) v.getLayoutParams();
1098                left += lp.leftMargin;
1099                top += lp.topMargin;
1100
1101                // Offsets due to the size difference between the View and the dragOutline.
1102                // There is a size difference to account for the outer blur, which may lie
1103                // outside the bounds of the view.
1104                top += (v.getHeight() - dragOutline.getHeight()) / 2;
1105                // We center about the x axis
1106                left += ((mCellWidth * spanX) + ((spanX - 1) * mWidthGap)
1107                        - dragOutline.getWidth()) / 2;
1108            } else {
1109                if (dragOffset != null && dragRegion != null) {
1110                    // Center the drag region *horizontally* in the cell and apply a drag
1111                    // outline offset
1112                    left += dragOffset.x + ((mCellWidth * spanX) + ((spanX - 1) * mWidthGap)
1113                             - dragRegion.width()) / 2;
1114                    int cHeight = getShortcutsAndWidgets().getCellContentHeight();
1115                    int cellPaddingY = (int) Math.max(0, ((mCellHeight - cHeight) / 2f));
1116                    top += dragOffset.y + cellPaddingY;
1117                } else {
1118                    // Center the drag outline in the cell
1119                    left += ((mCellWidth * spanX) + ((spanX - 1) * mWidthGap)
1120                            - dragOutline.getWidth()) / 2;
1121                    top += ((mCellHeight * spanY) + ((spanY - 1) * mHeightGap)
1122                            - dragOutline.getHeight()) / 2;
1123                }
1124            }
1125            final int oldIndex = mDragOutlineCurrent;
1126            mDragOutlineAnims[oldIndex].animateOut();
1127            mDragOutlineCurrent = (oldIndex + 1) % mDragOutlines.length;
1128            Rect r = mDragOutlines[mDragOutlineCurrent];
1129            r.set(left, top, left + dragOutline.getWidth(), top + dragOutline.getHeight());
1130            if (resize) {
1131                cellToRect(cellX, cellY, spanX, spanY, r);
1132            }
1133
1134            mDragOutlineAnims[mDragOutlineCurrent].setTag(dragOutline);
1135            mDragOutlineAnims[mDragOutlineCurrent].animateIn();
1136        }
1137    }
1138
1139    public void clearDragOutlines() {
1140        final int oldIndex = mDragOutlineCurrent;
1141        mDragOutlineAnims[oldIndex].animateOut();
1142        mDragCell[0] = mDragCell[1] = -1;
1143    }
1144
1145    /**
1146     * Find a vacant area that will fit the given bounds nearest the requested
1147     * cell location. Uses Euclidean distance to score multiple vacant areas.
1148     *
1149     * @param pixelX The X location at which you want to search for a vacant area.
1150     * @param pixelY The Y location at which you want to search for a vacant area.
1151     * @param spanX Horizontal span of the object.
1152     * @param spanY Vertical span of the object.
1153     * @param result Array in which to place the result, or null (in which case a new array will
1154     *        be allocated)
1155     * @return The X, Y cell of a vacant area that can contain this object,
1156     *         nearest the requested location.
1157     */
1158    int[] findNearestVacantArea(int pixelX, int pixelY, int spanX, int spanY, int[] result) {
1159        return findNearestVacantArea(pixelX, pixelY, spanX, spanY, spanX, spanY, result, null);
1160    }
1161
1162    /**
1163     * Find a vacant area that will fit the given bounds nearest the requested
1164     * cell location. Uses Euclidean distance to score multiple vacant areas.
1165     *
1166     * @param pixelX The X location at which you want to search for a vacant area.
1167     * @param pixelY The Y location at which you want to search for a vacant area.
1168     * @param minSpanX The minimum horizontal span required
1169     * @param minSpanY The minimum vertical span required
1170     * @param spanX Horizontal span of the object.
1171     * @param spanY Vertical span of the object.
1172     * @param result Array in which to place the result, or null (in which case a new array will
1173     *        be allocated)
1174     * @return The X, Y cell of a vacant area that can contain this object,
1175     *         nearest the requested location.
1176     */
1177    int[] findNearestVacantArea(int pixelX, int pixelY, int minSpanX, int minSpanY, int spanX,
1178            int spanY, int[] result, int[] resultSpan) {
1179        return findNearestArea(pixelX, pixelY, minSpanX, minSpanY, spanX, spanY, true,
1180                result, resultSpan);
1181    }
1182
1183    private final Stack<Rect> mTempRectStack = new Stack<Rect>();
1184    private void lazyInitTempRectStack() {
1185        if (mTempRectStack.isEmpty()) {
1186            for (int i = 0; i < mCountX * mCountY; i++) {
1187                mTempRectStack.push(new Rect());
1188            }
1189        }
1190    }
1191
1192    private void recycleTempRects(Stack<Rect> used) {
1193        while (!used.isEmpty()) {
1194            mTempRectStack.push(used.pop());
1195        }
1196    }
1197
1198    /**
1199     * Find a vacant area that will fit the given bounds nearest the requested
1200     * cell location. Uses Euclidean distance to score multiple vacant areas.
1201     *
1202     * @param pixelX The X location at which you want to search for a vacant area.
1203     * @param pixelY The Y location at which you want to search for a vacant area.
1204     * @param minSpanX The minimum horizontal span required
1205     * @param minSpanY The minimum vertical span required
1206     * @param spanX Horizontal span of the object.
1207     * @param spanY Vertical span of the object.
1208     * @param ignoreOccupied If true, the result can be an occupied cell
1209     * @param result Array in which to place the result, or null (in which case a new array will
1210     *        be allocated)
1211     * @return The X, Y cell of a vacant area that can contain this object,
1212     *         nearest the requested location.
1213     */
1214    private int[] findNearestArea(int pixelX, int pixelY, int minSpanX, int minSpanY, int spanX,
1215            int spanY, boolean ignoreOccupied, int[] result, int[] resultSpan) {
1216        lazyInitTempRectStack();
1217
1218        // For items with a spanX / spanY > 1, the passed in point (pixelX, pixelY) corresponds
1219        // to the center of the item, but we are searching based on the top-left cell, so
1220        // we translate the point over to correspond to the top-left.
1221        pixelX -= (mCellWidth + mWidthGap) * (spanX - 1) / 2f;
1222        pixelY -= (mCellHeight + mHeightGap) * (spanY - 1) / 2f;
1223
1224        // Keep track of best-scoring drop area
1225        final int[] bestXY = result != null ? result : new int[2];
1226        double bestDistance = Double.MAX_VALUE;
1227        final Rect bestRect = new Rect(-1, -1, -1, -1);
1228        final Stack<Rect> validRegions = new Stack<Rect>();
1229
1230        final int countX = mCountX;
1231        final int countY = mCountY;
1232
1233        if (minSpanX <= 0 || minSpanY <= 0 || spanX <= 0 || spanY <= 0 ||
1234                spanX < minSpanX || spanY < minSpanY) {
1235            return bestXY;
1236        }
1237
1238        for (int y = 0; y < countY - (minSpanY - 1); y++) {
1239            inner:
1240            for (int x = 0; x < countX - (minSpanX - 1); x++) {
1241                int ySize = -1;
1242                int xSize = -1;
1243                if (ignoreOccupied) {
1244                    // First, let's see if this thing fits anywhere
1245                    for (int i = 0; i < minSpanX; i++) {
1246                        for (int j = 0; j < minSpanY; j++) {
1247                            if (mOccupied[x + i][y + j]) {
1248                                continue inner;
1249                            }
1250                        }
1251                    }
1252                    xSize = minSpanX;
1253                    ySize = minSpanY;
1254
1255                    // We know that the item will fit at _some_ acceptable size, now let's see
1256                    // how big we can make it. We'll alternate between incrementing x and y spans
1257                    // until we hit a limit.
1258                    boolean incX = true;
1259                    boolean hitMaxX = xSize >= spanX;
1260                    boolean hitMaxY = ySize >= spanY;
1261                    while (!(hitMaxX && hitMaxY)) {
1262                        if (incX && !hitMaxX) {
1263                            for (int j = 0; j < ySize; j++) {
1264                                if (x + xSize > countX -1 || mOccupied[x + xSize][y + j]) {
1265                                    // We can't move out horizontally
1266                                    hitMaxX = true;
1267                                }
1268                            }
1269                            if (!hitMaxX) {
1270                                xSize++;
1271                            }
1272                        } else if (!hitMaxY) {
1273                            for (int i = 0; i < xSize; i++) {
1274                                if (y + ySize > countY - 1 || mOccupied[x + i][y + ySize]) {
1275                                    // We can't move out vertically
1276                                    hitMaxY = true;
1277                                }
1278                            }
1279                            if (!hitMaxY) {
1280                                ySize++;
1281                            }
1282                        }
1283                        hitMaxX |= xSize >= spanX;
1284                        hitMaxY |= ySize >= spanY;
1285                        incX = !incX;
1286                    }
1287                    incX = true;
1288                    hitMaxX = xSize >= spanX;
1289                    hitMaxY = ySize >= spanY;
1290                }
1291                final int[] cellXY = mTmpXY;
1292                cellToCenterPoint(x, y, cellXY);
1293
1294                // We verify that the current rect is not a sub-rect of any of our previous
1295                // candidates. In this case, the current rect is disqualified in favour of the
1296                // containing rect.
1297                Rect currentRect = mTempRectStack.pop();
1298                currentRect.set(x, y, x + xSize, y + ySize);
1299                boolean contained = false;
1300                for (Rect r : validRegions) {
1301                    if (r.contains(currentRect)) {
1302                        contained = true;
1303                        break;
1304                    }
1305                }
1306                validRegions.push(currentRect);
1307                double distance = Math.hypot(cellXY[0] - pixelX,  cellXY[1] - pixelY);
1308
1309                if ((distance <= bestDistance && !contained) ||
1310                        currentRect.contains(bestRect)) {
1311                    bestDistance = distance;
1312                    bestXY[0] = x;
1313                    bestXY[1] = y;
1314                    if (resultSpan != null) {
1315                        resultSpan[0] = xSize;
1316                        resultSpan[1] = ySize;
1317                    }
1318                    bestRect.set(currentRect);
1319                }
1320            }
1321        }
1322
1323        // Return -1, -1 if no suitable location found
1324        if (bestDistance == Double.MAX_VALUE) {
1325            bestXY[0] = -1;
1326            bestXY[1] = -1;
1327        }
1328        recycleTempRects(validRegions);
1329        return bestXY;
1330    }
1331
1332     /**
1333     * Find a vacant area that will fit the given bounds nearest the requested
1334     * cell location, and will also weigh in a suggested direction vector of the
1335     * desired location. This method computers distance based on unit grid distances,
1336     * not pixel distances.
1337     *
1338     * @param cellX The X cell nearest to which you want to search for a vacant area.
1339     * @param cellY The Y cell nearest which you want to search for a vacant area.
1340     * @param spanX Horizontal span of the object.
1341     * @param spanY Vertical span of the object.
1342     * @param direction The favored direction in which the views should move from x, y
1343     * @param exactDirectionOnly If this parameter is true, then only solutions where the direction
1344     *        matches exactly. Otherwise we find the best matching direction.
1345     * @param occoupied The array which represents which cells in the CellLayout are occupied
1346     * @param blockOccupied The array which represents which cells in the specified block (cellX,
1347     *        cellY, spanX, spanY) are occupied. This is used when try to move a group of views.
1348     * @param result Array in which to place the result, or null (in which case a new array will
1349     *        be allocated)
1350     * @return The X, Y cell of a vacant area that can contain this object,
1351     *         nearest the requested location.
1352     */
1353    private int[] findNearestArea(int cellX, int cellY, int spanX, int spanY, int[] direction,
1354            boolean[][] occupied, boolean blockOccupied[][], int[] result) {
1355        // Keep track of best-scoring drop area
1356        final int[] bestXY = result != null ? result : new int[2];
1357        float bestDistance = Float.MAX_VALUE;
1358        int bestDirectionScore = Integer.MIN_VALUE;
1359
1360        final int countX = mCountX;
1361        final int countY = mCountY;
1362
1363        for (int y = 0; y < countY - (spanY - 1); y++) {
1364            inner:
1365            for (int x = 0; x < countX - (spanX - 1); x++) {
1366                // First, let's see if this thing fits anywhere
1367                for (int i = 0; i < spanX; i++) {
1368                    for (int j = 0; j < spanY; j++) {
1369                        if (occupied[x + i][y + j] && (blockOccupied == null || blockOccupied[i][j])) {
1370                            continue inner;
1371                        }
1372                    }
1373                }
1374
1375                float distance = (float) Math.hypot(x - cellX, y - cellY);
1376                int[] curDirection = mTmpPoint;
1377                computeDirectionVector(x - cellX, y - cellY, curDirection);
1378                // The direction score is just the dot product of the two candidate direction
1379                // and that passed in.
1380                int curDirectionScore = direction[0] * curDirection[0] +
1381                        direction[1] * curDirection[1];
1382                boolean exactDirectionOnly = false;
1383                boolean directionMatches = direction[0] == curDirection[0] &&
1384                        direction[0] == curDirection[0];
1385                if ((directionMatches || !exactDirectionOnly) &&
1386                        Float.compare(distance,  bestDistance) < 0 || (Float.compare(distance,
1387                        bestDistance) == 0 && curDirectionScore > bestDirectionScore)) {
1388                    bestDistance = distance;
1389                    bestDirectionScore = curDirectionScore;
1390                    bestXY[0] = x;
1391                    bestXY[1] = y;
1392                }
1393            }
1394        }
1395
1396        // Return -1, -1 if no suitable location found
1397        if (bestDistance == Float.MAX_VALUE) {
1398            bestXY[0] = -1;
1399            bestXY[1] = -1;
1400        }
1401        return bestXY;
1402    }
1403
1404    private boolean addViewToTempLocation(View v, Rect rectOccupiedByPotentialDrop,
1405            int[] direction, ItemConfiguration currentState) {
1406        CellAndSpan c = currentState.map.get(v);
1407        boolean success = false;
1408        markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, false);
1409        markCellsForRect(rectOccupiedByPotentialDrop, mTmpOccupied, true);
1410
1411        findNearestArea(c.x, c.y, c.spanX, c.spanY, direction, mTmpOccupied, null, mTempLocation);
1412
1413        if (mTempLocation[0] >= 0 && mTempLocation[1] >= 0) {
1414            c.x = mTempLocation[0];
1415            c.y = mTempLocation[1];
1416            success = true;
1417        }
1418        markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, true);
1419        return success;
1420    }
1421
1422    /**
1423     * This helper class defines a cluster of views. It helps with defining complex edges
1424     * of the cluster and determining how those edges interact with other views. The edges
1425     * essentially define a fine-grained boundary around the cluster of views -- like a more
1426     * precise version of a bounding box.
1427     */
1428    private class ViewCluster {
1429        final static int LEFT = 0;
1430        final static int TOP = 1;
1431        final static int RIGHT = 2;
1432        final static int BOTTOM = 3;
1433
1434        ArrayList<View> views;
1435        ItemConfiguration config;
1436        Rect boundingRect = new Rect();
1437
1438        int[] leftEdge = new int[mCountY];
1439        int[] rightEdge = new int[mCountY];
1440        int[] topEdge = new int[mCountX];
1441        int[] bottomEdge = new int[mCountX];
1442        boolean leftEdgeDirty, rightEdgeDirty, topEdgeDirty, bottomEdgeDirty, boundingRectDirty;
1443
1444        @SuppressWarnings("unchecked")
1445        public ViewCluster(ArrayList<View> views, ItemConfiguration config) {
1446            this.views = (ArrayList<View>) views.clone();
1447            this.config = config;
1448            resetEdges();
1449        }
1450
1451        void resetEdges() {
1452            for (int i = 0; i < mCountX; i++) {
1453                topEdge[i] = -1;
1454                bottomEdge[i] = -1;
1455            }
1456            for (int i = 0; i < mCountY; i++) {
1457                leftEdge[i] = -1;
1458                rightEdge[i] = -1;
1459            }
1460            leftEdgeDirty = true;
1461            rightEdgeDirty = true;
1462            bottomEdgeDirty = true;
1463            topEdgeDirty = true;
1464            boundingRectDirty = true;
1465        }
1466
1467        void computeEdge(int which, int[] edge) {
1468            int count = views.size();
1469            for (int i = 0; i < count; i++) {
1470                CellAndSpan cs = config.map.get(views.get(i));
1471                switch (which) {
1472                    case LEFT:
1473                        int left = cs.x;
1474                        for (int j = cs.y; j < cs.y + cs.spanY; j++) {
1475                            if (left < edge[j] || edge[j] < 0) {
1476                                edge[j] = left;
1477                            }
1478                        }
1479                        break;
1480                    case RIGHT:
1481                        int right = cs.x + cs.spanX;
1482                        for (int j = cs.y; j < cs.y + cs.spanY; j++) {
1483                            if (right > edge[j]) {
1484                                edge[j] = right;
1485                            }
1486                        }
1487                        break;
1488                    case TOP:
1489                        int top = cs.y;
1490                        for (int j = cs.x; j < cs.x + cs.spanX; j++) {
1491                            if (top < edge[j] || edge[j] < 0) {
1492                                edge[j] = top;
1493                            }
1494                        }
1495                        break;
1496                    case BOTTOM:
1497                        int bottom = cs.y + cs.spanY;
1498                        for (int j = cs.x; j < cs.x + cs.spanX; j++) {
1499                            if (bottom > edge[j]) {
1500                                edge[j] = bottom;
1501                            }
1502                        }
1503                        break;
1504                }
1505            }
1506        }
1507
1508        boolean isViewTouchingEdge(View v, int whichEdge) {
1509            CellAndSpan cs = config.map.get(v);
1510
1511            int[] edge = getEdge(whichEdge);
1512
1513            switch (whichEdge) {
1514                case LEFT:
1515                    for (int i = cs.y; i < cs.y + cs.spanY; i++) {
1516                        if (edge[i] == cs.x + cs.spanX) {
1517                            return true;
1518                        }
1519                    }
1520                    break;
1521                case RIGHT:
1522                    for (int i = cs.y; i < cs.y + cs.spanY; i++) {
1523                        if (edge[i] == cs.x) {
1524                            return true;
1525                        }
1526                    }
1527                    break;
1528                case TOP:
1529                    for (int i = cs.x; i < cs.x + cs.spanX; i++) {
1530                        if (edge[i] == cs.y + cs.spanY) {
1531                            return true;
1532                        }
1533                    }
1534                    break;
1535                case BOTTOM:
1536                    for (int i = cs.x; i < cs.x + cs.spanX; i++) {
1537                        if (edge[i] == cs.y) {
1538                            return true;
1539                        }
1540                    }
1541                    break;
1542            }
1543            return false;
1544        }
1545
1546        void shift(int whichEdge, int delta) {
1547            for (View v: views) {
1548                CellAndSpan c = config.map.get(v);
1549                switch (whichEdge) {
1550                    case LEFT:
1551                        c.x -= delta;
1552                        break;
1553                    case RIGHT:
1554                        c.x += delta;
1555                        break;
1556                    case TOP:
1557                        c.y -= delta;
1558                        break;
1559                    case BOTTOM:
1560                    default:
1561                        c.y += delta;
1562                        break;
1563                }
1564            }
1565            resetEdges();
1566        }
1567
1568        public void addView(View v) {
1569            views.add(v);
1570            resetEdges();
1571        }
1572
1573        public Rect getBoundingRect() {
1574            if (boundingRectDirty) {
1575                boolean first = true;
1576                for (View v: views) {
1577                    CellAndSpan c = config.map.get(v);
1578                    if (first) {
1579                        boundingRect.set(c.x, c.y, c.x + c.spanX, c.y + c.spanY);
1580                        first = false;
1581                    } else {
1582                        boundingRect.union(c.x, c.y, c.x + c.spanX, c.y + c.spanY);
1583                    }
1584                }
1585            }
1586            return boundingRect;
1587        }
1588
1589        public int[] getEdge(int which) {
1590            switch (which) {
1591                case LEFT:
1592                    return getLeftEdge();
1593                case RIGHT:
1594                    return getRightEdge();
1595                case TOP:
1596                    return getTopEdge();
1597                case BOTTOM:
1598                default:
1599                    return getBottomEdge();
1600            }
1601        }
1602
1603        public int[] getLeftEdge() {
1604            if (leftEdgeDirty) {
1605                computeEdge(LEFT, leftEdge);
1606            }
1607            return leftEdge;
1608        }
1609
1610        public int[] getRightEdge() {
1611            if (rightEdgeDirty) {
1612                computeEdge(RIGHT, rightEdge);
1613            }
1614            return rightEdge;
1615        }
1616
1617        public int[] getTopEdge() {
1618            if (topEdgeDirty) {
1619                computeEdge(TOP, topEdge);
1620            }
1621            return topEdge;
1622        }
1623
1624        public int[] getBottomEdge() {
1625            if (bottomEdgeDirty) {
1626                computeEdge(BOTTOM, bottomEdge);
1627            }
1628            return bottomEdge;
1629        }
1630
1631        PositionComparator comparator = new PositionComparator();
1632        class PositionComparator implements Comparator<View> {
1633            int whichEdge = 0;
1634            public int compare(View left, View right) {
1635                CellAndSpan l = config.map.get(left);
1636                CellAndSpan r = config.map.get(right);
1637                switch (whichEdge) {
1638                    case LEFT:
1639                        return (r.x + r.spanX) - (l.x + l.spanX);
1640                    case RIGHT:
1641                        return l.x - r.x;
1642                    case TOP:
1643                        return (r.y + r.spanY) - (l.y + l.spanY);
1644                    case BOTTOM:
1645                    default:
1646                        return l.y - r.y;
1647                }
1648            }
1649        }
1650
1651        public void sortConfigurationForEdgePush(int edge) {
1652            comparator.whichEdge = edge;
1653            Collections.sort(config.sortedViews, comparator);
1654        }
1655    }
1656
1657    private boolean pushViewsToTempLocation(ArrayList<View> views, Rect rectOccupiedByPotentialDrop,
1658            int[] direction, View dragView, ItemConfiguration currentState) {
1659
1660        ViewCluster cluster = new ViewCluster(views, currentState);
1661        Rect clusterRect = cluster.getBoundingRect();
1662        int whichEdge;
1663        int pushDistance;
1664        boolean fail = false;
1665
1666        // Determine the edge of the cluster that will be leading the push and how far
1667        // the cluster must be shifted.
1668        if (direction[0] < 0) {
1669            whichEdge = ViewCluster.LEFT;
1670            pushDistance = clusterRect.right - rectOccupiedByPotentialDrop.left;
1671        } else if (direction[0] > 0) {
1672            whichEdge = ViewCluster.RIGHT;
1673            pushDistance = rectOccupiedByPotentialDrop.right - clusterRect.left;
1674        } else if (direction[1] < 0) {
1675            whichEdge = ViewCluster.TOP;
1676            pushDistance = clusterRect.bottom - rectOccupiedByPotentialDrop.top;
1677        } else {
1678            whichEdge = ViewCluster.BOTTOM;
1679            pushDistance = rectOccupiedByPotentialDrop.bottom - clusterRect.top;
1680        }
1681
1682        // Break early for invalid push distance.
1683        if (pushDistance <= 0) {
1684            return false;
1685        }
1686
1687        // Mark the occupied state as false for the group of views we want to move.
1688        for (View v: views) {
1689            CellAndSpan c = currentState.map.get(v);
1690            markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, false);
1691        }
1692
1693        // We save the current configuration -- if we fail to find a solution we will revert
1694        // to the initial state. The process of finding a solution modifies the configuration
1695        // in place, hence the need for revert in the failure case.
1696        currentState.save();
1697
1698        // The pushing algorithm is simplified by considering the views in the order in which
1699        // they would be pushed by the cluster. For example, if the cluster is leading with its
1700        // left edge, we consider sort the views by their right edge, from right to left.
1701        cluster.sortConfigurationForEdgePush(whichEdge);
1702
1703        while (pushDistance > 0 && !fail) {
1704            for (View v: currentState.sortedViews) {
1705                // For each view that isn't in the cluster, we see if the leading edge of the
1706                // cluster is contacting the edge of that view. If so, we add that view to the
1707                // cluster.
1708                if (!cluster.views.contains(v) && v != dragView) {
1709                    if (cluster.isViewTouchingEdge(v, whichEdge)) {
1710                        LayoutParams lp = (LayoutParams) v.getLayoutParams();
1711                        if (!lp.canReorder) {
1712                            // The push solution includes the all apps button, this is not viable.
1713                            fail = true;
1714                            break;
1715                        }
1716                        cluster.addView(v);
1717                        CellAndSpan c = currentState.map.get(v);
1718
1719                        // Adding view to cluster, mark it as not occupied.
1720                        markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, false);
1721                    }
1722                }
1723            }
1724            pushDistance--;
1725
1726            // The cluster has been completed, now we move the whole thing over in the appropriate
1727            // direction.
1728            cluster.shift(whichEdge, 1);
1729        }
1730
1731        boolean foundSolution = false;
1732        clusterRect = cluster.getBoundingRect();
1733
1734        // Due to the nature of the algorithm, the only check required to verify a valid solution
1735        // is to ensure that completed shifted cluster lies completely within the cell layout.
1736        if (!fail && clusterRect.left >= 0 && clusterRect.right <= mCountX && clusterRect.top >= 0 &&
1737                clusterRect.bottom <= mCountY) {
1738            foundSolution = true;
1739        } else {
1740            currentState.restore();
1741        }
1742
1743        // In either case, we set the occupied array as marked for the location of the views
1744        for (View v: cluster.views) {
1745            CellAndSpan c = currentState.map.get(v);
1746            markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, true);
1747        }
1748
1749        return foundSolution;
1750    }
1751
1752    private boolean addViewsToTempLocation(ArrayList<View> views, Rect rectOccupiedByPotentialDrop,
1753            int[] direction, View dragView, ItemConfiguration currentState) {
1754        if (views.size() == 0) return true;
1755
1756        boolean success = false;
1757        Rect boundingRect = null;
1758        // We construct a rect which represents the entire group of views passed in
1759        for (View v: views) {
1760            CellAndSpan c = currentState.map.get(v);
1761            if (boundingRect == null) {
1762                boundingRect = new Rect(c.x, c.y, c.x + c.spanX, c.y + c.spanY);
1763            } else {
1764                boundingRect.union(c.x, c.y, c.x + c.spanX, c.y + c.spanY);
1765            }
1766        }
1767
1768        // Mark the occupied state as false for the group of views we want to move.
1769        for (View v: views) {
1770            CellAndSpan c = currentState.map.get(v);
1771            markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, false);
1772        }
1773
1774        boolean[][] blockOccupied = new boolean[boundingRect.width()][boundingRect.height()];
1775        int top = boundingRect.top;
1776        int left = boundingRect.left;
1777        // We mark more precisely which parts of the bounding rect are truly occupied, allowing
1778        // for interlocking.
1779        for (View v: views) {
1780            CellAndSpan c = currentState.map.get(v);
1781            markCellsForView(c.x - left, c.y - top, c.spanX, c.spanY, blockOccupied, true);
1782        }
1783
1784        markCellsForRect(rectOccupiedByPotentialDrop, mTmpOccupied, true);
1785
1786        findNearestArea(boundingRect.left, boundingRect.top, boundingRect.width(),
1787                boundingRect.height(), direction, mTmpOccupied, blockOccupied, mTempLocation);
1788
1789        // If we successfuly found a location by pushing the block of views, we commit it
1790        if (mTempLocation[0] >= 0 && mTempLocation[1] >= 0) {
1791            int deltaX = mTempLocation[0] - boundingRect.left;
1792            int deltaY = mTempLocation[1] - boundingRect.top;
1793            for (View v: views) {
1794                CellAndSpan c = currentState.map.get(v);
1795                c.x += deltaX;
1796                c.y += deltaY;
1797            }
1798            success = true;
1799        }
1800
1801        // In either case, we set the occupied array as marked for the location of the views
1802        for (View v: views) {
1803            CellAndSpan c = currentState.map.get(v);
1804            markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, true);
1805        }
1806        return success;
1807    }
1808
1809    private void markCellsForRect(Rect r, boolean[][] occupied, boolean value) {
1810        markCellsForView(r.left, r.top, r.width(), r.height(), occupied, value);
1811    }
1812
1813    // This method tries to find a reordering solution which satisfies the push mechanic by trying
1814    // to push items in each of the cardinal directions, in an order based on the direction vector
1815    // passed.
1816    private boolean attemptPushInDirection(ArrayList<View> intersectingViews, Rect occupied,
1817            int[] direction, View ignoreView, ItemConfiguration solution) {
1818        if ((Math.abs(direction[0]) + Math.abs(direction[1])) > 1) {
1819            // If the direction vector has two non-zero components, we try pushing
1820            // separately in each of the components.
1821            int temp = direction[1];
1822            direction[1] = 0;
1823
1824            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
1825                    ignoreView, solution)) {
1826                return true;
1827            }
1828            direction[1] = temp;
1829            temp = direction[0];
1830            direction[0] = 0;
1831
1832            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
1833                    ignoreView, solution)) {
1834                return true;
1835            }
1836            // Revert the direction
1837            direction[0] = temp;
1838
1839            // Now we try pushing in each component of the opposite direction
1840            direction[0] *= -1;
1841            direction[1] *= -1;
1842            temp = direction[1];
1843            direction[1] = 0;
1844            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
1845                    ignoreView, solution)) {
1846                return true;
1847            }
1848
1849            direction[1] = temp;
1850            temp = direction[0];
1851            direction[0] = 0;
1852            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
1853                    ignoreView, solution)) {
1854                return true;
1855            }
1856            // revert the direction
1857            direction[0] = temp;
1858            direction[0] *= -1;
1859            direction[1] *= -1;
1860
1861        } else {
1862            // If the direction vector has a single non-zero component, we push first in the
1863            // direction of the vector
1864            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
1865                    ignoreView, solution)) {
1866                return true;
1867            }
1868            // Then we try the opposite direction
1869            direction[0] *= -1;
1870            direction[1] *= -1;
1871            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
1872                    ignoreView, solution)) {
1873                return true;
1874            }
1875            // Switch the direction back
1876            direction[0] *= -1;
1877            direction[1] *= -1;
1878
1879            // If we have failed to find a push solution with the above, then we try
1880            // to find a solution by pushing along the perpendicular axis.
1881
1882            // Swap the components
1883            int temp = direction[1];
1884            direction[1] = direction[0];
1885            direction[0] = temp;
1886            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
1887                    ignoreView, solution)) {
1888                return true;
1889            }
1890
1891            // Then we try the opposite direction
1892            direction[0] *= -1;
1893            direction[1] *= -1;
1894            if (pushViewsToTempLocation(intersectingViews, occupied, direction,
1895                    ignoreView, solution)) {
1896                return true;
1897            }
1898            // Switch the direction back
1899            direction[0] *= -1;
1900            direction[1] *= -1;
1901
1902            // Swap the components back
1903            temp = direction[1];
1904            direction[1] = direction[0];
1905            direction[0] = temp;
1906        }
1907        return false;
1908    }
1909
1910    private boolean rearrangementExists(int cellX, int cellY, int spanX, int spanY, int[] direction,
1911            View ignoreView, ItemConfiguration solution) {
1912        // Return early if get invalid cell positions
1913        if (cellX < 0 || cellY < 0) return false;
1914
1915        mIntersectingViews.clear();
1916        mOccupiedRect.set(cellX, cellY, cellX + spanX, cellY + spanY);
1917
1918        // Mark the desired location of the view currently being dragged.
1919        if (ignoreView != null) {
1920            CellAndSpan c = solution.map.get(ignoreView);
1921            if (c != null) {
1922                c.x = cellX;
1923                c.y = cellY;
1924            }
1925        }
1926        Rect r0 = new Rect(cellX, cellY, cellX + spanX, cellY + spanY);
1927        Rect r1 = new Rect();
1928        for (View child: solution.map.keySet()) {
1929            if (child == ignoreView) continue;
1930            CellAndSpan c = solution.map.get(child);
1931            LayoutParams lp = (LayoutParams) child.getLayoutParams();
1932            r1.set(c.x, c.y, c.x + c.spanX, c.y + c.spanY);
1933            if (Rect.intersects(r0, r1)) {
1934                if (!lp.canReorder) {
1935                    return false;
1936                }
1937                mIntersectingViews.add(child);
1938            }
1939        }
1940
1941        solution.intersectingViews = new ArrayList<View>(mIntersectingViews);
1942
1943        // First we try to find a solution which respects the push mechanic. That is,
1944        // we try to find a solution such that no displaced item travels through another item
1945        // without also displacing that item.
1946        if (attemptPushInDirection(mIntersectingViews, mOccupiedRect, direction, ignoreView,
1947                solution)) {
1948            return true;
1949        }
1950
1951        // Next we try moving the views as a block, but without requiring the push mechanic.
1952        if (addViewsToTempLocation(mIntersectingViews, mOccupiedRect, direction, ignoreView,
1953                solution)) {
1954            return true;
1955        }
1956
1957        // Ok, they couldn't move as a block, let's move them individually
1958        for (View v : mIntersectingViews) {
1959            if (!addViewToTempLocation(v, mOccupiedRect, direction, solution)) {
1960                return false;
1961            }
1962        }
1963        return true;
1964    }
1965
1966    /*
1967     * Returns a pair (x, y), where x,y are in {-1, 0, 1} corresponding to vector between
1968     * the provided point and the provided cell
1969     */
1970    private void computeDirectionVector(float deltaX, float deltaY, int[] result) {
1971        double angle = Math.atan(((float) deltaY) / deltaX);
1972
1973        result[0] = 0;
1974        result[1] = 0;
1975        if (Math.abs(Math.cos(angle)) > 0.5f) {
1976            result[0] = (int) Math.signum(deltaX);
1977        }
1978        if (Math.abs(Math.sin(angle)) > 0.5f) {
1979            result[1] = (int) Math.signum(deltaY);
1980        }
1981    }
1982
1983    private void copyOccupiedArray(boolean[][] occupied) {
1984        for (int i = 0; i < mCountX; i++) {
1985            for (int j = 0; j < mCountY; j++) {
1986                occupied[i][j] = mOccupied[i][j];
1987            }
1988        }
1989    }
1990
1991    private ItemConfiguration findReorderSolution(int pixelX, int pixelY, int minSpanX, int minSpanY,
1992            int spanX, int spanY, int[] direction, View dragView, boolean decX,
1993            ItemConfiguration solution) {
1994        // Copy the current state into the solution. This solution will be manipulated as necessary.
1995        copyCurrentStateToSolution(solution, false);
1996        // Copy the current occupied array into the temporary occupied array. This array will be
1997        // manipulated as necessary to find a solution.
1998        copyOccupiedArray(mTmpOccupied);
1999
2000        // We find the nearest cell into which we would place the dragged item, assuming there's
2001        // nothing in its way.
2002        int result[] = new int[2];
2003        result = findNearestArea(pixelX, pixelY, spanX, spanY, result);
2004
2005        boolean success = false;
2006        // First we try the exact nearest position of the item being dragged,
2007        // we will then want to try to move this around to other neighbouring positions
2008        success = rearrangementExists(result[0], result[1], spanX, spanY, direction, dragView,
2009                solution);
2010
2011        if (!success) {
2012            // We try shrinking the widget down to size in an alternating pattern, shrink 1 in
2013            // x, then 1 in y etc.
2014            if (spanX > minSpanX && (minSpanY == spanY || decX)) {
2015                return findReorderSolution(pixelX, pixelY, minSpanX, minSpanY, spanX - 1, spanY,
2016                        direction, dragView, false, solution);
2017            } else if (spanY > minSpanY) {
2018                return findReorderSolution(pixelX, pixelY, minSpanX, minSpanY, spanX, spanY - 1,
2019                        direction, dragView, true, solution);
2020            }
2021            solution.isSolution = false;
2022        } else {
2023            solution.isSolution = true;
2024            solution.dragViewX = result[0];
2025            solution.dragViewY = result[1];
2026            solution.dragViewSpanX = spanX;
2027            solution.dragViewSpanY = spanY;
2028        }
2029        return solution;
2030    }
2031
2032    private void copyCurrentStateToSolution(ItemConfiguration solution, boolean temp) {
2033        int childCount = mShortcutsAndWidgets.getChildCount();
2034        for (int i = 0; i < childCount; i++) {
2035            View child = mShortcutsAndWidgets.getChildAt(i);
2036            LayoutParams lp = (LayoutParams) child.getLayoutParams();
2037            CellAndSpan c;
2038            if (temp) {
2039                c = new CellAndSpan(lp.tmpCellX, lp.tmpCellY, lp.cellHSpan, lp.cellVSpan);
2040            } else {
2041                c = new CellAndSpan(lp.cellX, lp.cellY, lp.cellHSpan, lp.cellVSpan);
2042            }
2043            solution.add(child, c);
2044        }
2045    }
2046
2047    private void copySolutionToTempState(ItemConfiguration solution, View dragView) {
2048        for (int i = 0; i < mCountX; i++) {
2049            for (int j = 0; j < mCountY; j++) {
2050                mTmpOccupied[i][j] = false;
2051            }
2052        }
2053
2054        int childCount = mShortcutsAndWidgets.getChildCount();
2055        for (int i = 0; i < childCount; i++) {
2056            View child = mShortcutsAndWidgets.getChildAt(i);
2057            if (child == dragView) continue;
2058            LayoutParams lp = (LayoutParams) child.getLayoutParams();
2059            CellAndSpan c = solution.map.get(child);
2060            if (c != null) {
2061                lp.tmpCellX = c.x;
2062                lp.tmpCellY = c.y;
2063                lp.cellHSpan = c.spanX;
2064                lp.cellVSpan = c.spanY;
2065                markCellsForView(c.x, c.y, c.spanX, c.spanY, mTmpOccupied, true);
2066            }
2067        }
2068        markCellsForView(solution.dragViewX, solution.dragViewY, solution.dragViewSpanX,
2069                solution.dragViewSpanY, mTmpOccupied, true);
2070    }
2071
2072    private void animateItemsToSolution(ItemConfiguration solution, View dragView, boolean
2073            commitDragView) {
2074
2075        boolean[][] occupied = DESTRUCTIVE_REORDER ? mOccupied : mTmpOccupied;
2076        for (int i = 0; i < mCountX; i++) {
2077            for (int j = 0; j < mCountY; j++) {
2078                occupied[i][j] = false;
2079            }
2080        }
2081
2082        int childCount = mShortcutsAndWidgets.getChildCount();
2083        for (int i = 0; i < childCount; i++) {
2084            View child = mShortcutsAndWidgets.getChildAt(i);
2085            if (child == dragView) continue;
2086            CellAndSpan c = solution.map.get(child);
2087            if (c != null) {
2088                animateChildToPosition(child, c.x, c.y, REORDER_ANIMATION_DURATION, 0,
2089                        DESTRUCTIVE_REORDER, false);
2090                markCellsForView(c.x, c.y, c.spanX, c.spanY, occupied, true);
2091            }
2092        }
2093        if (commitDragView) {
2094            markCellsForView(solution.dragViewX, solution.dragViewY, solution.dragViewSpanX,
2095                    solution.dragViewSpanY, occupied, true);
2096        }
2097    }
2098
2099
2100    // This method starts or changes the reorder preview animations
2101    private void beginOrAdjustReorderPreviewAnimations(ItemConfiguration solution,
2102            View dragView, int delay, int mode) {
2103        int childCount = mShortcutsAndWidgets.getChildCount();
2104        for (int i = 0; i < childCount; i++) {
2105            View child = mShortcutsAndWidgets.getChildAt(i);
2106            if (child == dragView) continue;
2107            CellAndSpan c = solution.map.get(child);
2108            boolean skip = mode == ReorderPreviewAnimation.MODE_HINT && solution.intersectingViews
2109                    != null && !solution.intersectingViews.contains(child);
2110
2111            LayoutParams lp = (LayoutParams) child.getLayoutParams();
2112            if (c != null && !skip) {
2113                ReorderPreviewAnimation rha = new ReorderPreviewAnimation(child, mode, lp.cellX,
2114                        lp.cellY, c.x, c.y, c.spanX, c.spanY);
2115                rha.animate();
2116            }
2117        }
2118    }
2119
2120    // Class which represents the reorder preview animations. These animations show that an item is
2121    // in a temporary state, and hint at where the item will return to.
2122    class ReorderPreviewAnimation {
2123        View child;
2124        float finalDeltaX;
2125        float finalDeltaY;
2126        float initDeltaX;
2127        float initDeltaY;
2128        float finalScale;
2129        float initScale;
2130        int mode;
2131        boolean repeating = false;
2132        private static final int PREVIEW_DURATION = 300;
2133        private static final int HINT_DURATION = Workspace.REORDER_TIMEOUT;
2134
2135        public static final int MODE_HINT = 0;
2136        public static final int MODE_PREVIEW = 1;
2137
2138        Animator a;
2139
2140        public ReorderPreviewAnimation(View child, int mode, int cellX0, int cellY0, int cellX1,
2141                int cellY1, int spanX, int spanY) {
2142            regionToCenterPoint(cellX0, cellY0, spanX, spanY, mTmpPoint);
2143            final int x0 = mTmpPoint[0];
2144            final int y0 = mTmpPoint[1];
2145            regionToCenterPoint(cellX1, cellY1, spanX, spanY, mTmpPoint);
2146            final int x1 = mTmpPoint[0];
2147            final int y1 = mTmpPoint[1];
2148            final int dX = x1 - x0;
2149            final int dY = y1 - y0;
2150            finalDeltaX = 0;
2151            finalDeltaY = 0;
2152            int dir = mode == MODE_HINT ? -1 : 1;
2153            if (dX == dY && dX == 0) {
2154            } else {
2155                if (dY == 0) {
2156                    finalDeltaX = - dir * Math.signum(dX) * mReorderPreviewAnimationMagnitude;
2157                } else if (dX == 0) {
2158                    finalDeltaY = - dir * Math.signum(dY) * mReorderPreviewAnimationMagnitude;
2159                } else {
2160                    double angle = Math.atan( (float) (dY) / dX);
2161                    finalDeltaX = (int) (- dir * Math.signum(dX) *
2162                            Math.abs(Math.cos(angle) * mReorderPreviewAnimationMagnitude));
2163                    finalDeltaY = (int) (- dir * Math.signum(dY) *
2164                            Math.abs(Math.sin(angle) * mReorderPreviewAnimationMagnitude));
2165                }
2166            }
2167            this.mode = mode;
2168            initDeltaX = child.getTranslationX();
2169            initDeltaY = child.getTranslationY();
2170            finalScale = getChildrenScale() - 4.0f / child.getWidth();
2171            initScale = child.getScaleX();
2172            this.child = child;
2173        }
2174
2175        void animate() {
2176            if (mShakeAnimators.containsKey(child)) {
2177                ReorderPreviewAnimation oldAnimation = mShakeAnimators.get(child);
2178                oldAnimation.cancel();
2179                mShakeAnimators.remove(child);
2180                if (finalDeltaX == 0 && finalDeltaY == 0) {
2181                    completeAnimationImmediately();
2182                    return;
2183                }
2184            }
2185            if (finalDeltaX == 0 && finalDeltaY == 0) {
2186                return;
2187            }
2188            ValueAnimator va = LauncherAnimUtils.ofFloat(child, 0f, 1f);
2189            a = va;
2190            va.setRepeatMode(ValueAnimator.REVERSE);
2191            va.setRepeatCount(ValueAnimator.INFINITE);
2192            va.setDuration(mode == MODE_HINT ? HINT_DURATION : PREVIEW_DURATION);
2193            va.setStartDelay((int) (Math.random() * 60));
2194            va.addUpdateListener(new AnimatorUpdateListener() {
2195                @Override
2196                public void onAnimationUpdate(ValueAnimator animation) {
2197                    float r = ((Float) animation.getAnimatedValue()).floatValue();
2198                    float r1 = (mode == MODE_HINT && repeating) ? 1.0f : r;
2199                    float x = r1 * finalDeltaX + (1 - r1) * initDeltaX;
2200                    float y = r1 * finalDeltaY + (1 - r1) * initDeltaY;
2201                    child.setTranslationX(x);
2202                    child.setTranslationY(y);
2203                    float s = r * finalScale + (1 - r) * initScale;
2204                    child.setScaleX(s);
2205                    child.setScaleY(s);
2206                }
2207            });
2208            va.addListener(new AnimatorListenerAdapter() {
2209                public void onAnimationRepeat(Animator animation) {
2210                    // We make sure to end only after a full period
2211                    initDeltaX = 0;
2212                    initDeltaY = 0;
2213                    initScale = getChildrenScale();
2214                    repeating = true;
2215                }
2216            });
2217            mShakeAnimators.put(child, this);
2218            va.start();
2219        }
2220
2221        private void cancel() {
2222            if (a != null) {
2223                a.cancel();
2224            }
2225        }
2226
2227        @Thunk void completeAnimationImmediately() {
2228            if (a != null) {
2229                a.cancel();
2230            }
2231
2232            AnimatorSet s = LauncherAnimUtils.createAnimatorSet();
2233            a = s;
2234            s.playTogether(
2235                LauncherAnimUtils.ofFloat(child, "scaleX", getChildrenScale()),
2236                LauncherAnimUtils.ofFloat(child, "scaleY", getChildrenScale()),
2237                LauncherAnimUtils.ofFloat(child, "translationX", 0f),
2238                LauncherAnimUtils.ofFloat(child, "translationY", 0f)
2239            );
2240            s.setDuration(REORDER_ANIMATION_DURATION);
2241            s.setInterpolator(new android.view.animation.DecelerateInterpolator(1.5f));
2242            s.start();
2243        }
2244    }
2245
2246    private void completeAndClearReorderPreviewAnimations() {
2247        for (ReorderPreviewAnimation a: mShakeAnimators.values()) {
2248            a.completeAnimationImmediately();
2249        }
2250        mShakeAnimators.clear();
2251    }
2252
2253    private void commitTempPlacement() {
2254        for (int i = 0; i < mCountX; i++) {
2255            for (int j = 0; j < mCountY; j++) {
2256                mOccupied[i][j] = mTmpOccupied[i][j];
2257            }
2258        }
2259        int childCount = mShortcutsAndWidgets.getChildCount();
2260        for (int i = 0; i < childCount; i++) {
2261            View child = mShortcutsAndWidgets.getChildAt(i);
2262            LayoutParams lp = (LayoutParams) child.getLayoutParams();
2263            ItemInfo info = (ItemInfo) child.getTag();
2264            // We do a null check here because the item info can be null in the case of the
2265            // AllApps button in the hotseat.
2266            if (info != null) {
2267                if (info.cellX != lp.tmpCellX || info.cellY != lp.tmpCellY ||
2268                        info.spanX != lp.cellHSpan || info.spanY != lp.cellVSpan) {
2269                    info.requiresDbUpdate = true;
2270                }
2271                info.cellX = lp.cellX = lp.tmpCellX;
2272                info.cellY = lp.cellY = lp.tmpCellY;
2273                info.spanX = lp.cellHSpan;
2274                info.spanY = lp.cellVSpan;
2275            }
2276        }
2277        mLauncher.getWorkspace().updateItemLocationsInDatabase(this);
2278    }
2279
2280    private void setUseTempCoords(boolean useTempCoords) {
2281        int childCount = mShortcutsAndWidgets.getChildCount();
2282        for (int i = 0; i < childCount; i++) {
2283            LayoutParams lp = (LayoutParams) mShortcutsAndWidgets.getChildAt(i).getLayoutParams();
2284            lp.useTmpCoords = useTempCoords;
2285        }
2286    }
2287
2288    private ItemConfiguration findConfigurationNoShuffle(int pixelX, int pixelY, int minSpanX, int minSpanY,
2289            int spanX, int spanY, View dragView, ItemConfiguration solution) {
2290        int[] result = new int[2];
2291        int[] resultSpan = new int[2];
2292        findNearestVacantArea(pixelX, pixelY, minSpanX, minSpanY, spanX, spanY, result,
2293                resultSpan);
2294        if (result[0] >= 0 && result[1] >= 0) {
2295            copyCurrentStateToSolution(solution, false);
2296            solution.dragViewX = result[0];
2297            solution.dragViewY = result[1];
2298            solution.dragViewSpanX = resultSpan[0];
2299            solution.dragViewSpanY = resultSpan[1];
2300            solution.isSolution = true;
2301        } else {
2302            solution.isSolution = false;
2303        }
2304        return solution;
2305    }
2306
2307    public void prepareChildForDrag(View child) {
2308        markCellsAsUnoccupiedForView(child);
2309    }
2310
2311    /* This seems like it should be obvious and straight-forward, but when the direction vector
2312    needs to match with the notion of the dragView pushing other views, we have to employ
2313    a slightly more subtle notion of the direction vector. The question is what two points is
2314    the vector between? The center of the dragView and its desired destination? Not quite, as
2315    this doesn't necessarily coincide with the interaction of the dragView and items occupying
2316    those cells. Instead we use some heuristics to often lock the vector to up, down, left
2317    or right, which helps make pushing feel right.
2318    */
2319    private void getDirectionVectorForDrop(int dragViewCenterX, int dragViewCenterY, int spanX,
2320            int spanY, View dragView, int[] resultDirection) {
2321        int[] targetDestination = new int[2];
2322
2323        findNearestArea(dragViewCenterX, dragViewCenterY, spanX, spanY, targetDestination);
2324        Rect dragRect = new Rect();
2325        regionToRect(targetDestination[0], targetDestination[1], spanX, spanY, dragRect);
2326        dragRect.offset(dragViewCenterX - dragRect.centerX(), dragViewCenterY - dragRect.centerY());
2327
2328        Rect dropRegionRect = new Rect();
2329        getViewsIntersectingRegion(targetDestination[0], targetDestination[1], spanX, spanY,
2330                dragView, dropRegionRect, mIntersectingViews);
2331
2332        int dropRegionSpanX = dropRegionRect.width();
2333        int dropRegionSpanY = dropRegionRect.height();
2334
2335        regionToRect(dropRegionRect.left, dropRegionRect.top, dropRegionRect.width(),
2336                dropRegionRect.height(), dropRegionRect);
2337
2338        int deltaX = (dropRegionRect.centerX() - dragViewCenterX) / spanX;
2339        int deltaY = (dropRegionRect.centerY() - dragViewCenterY) / spanY;
2340
2341        if (dropRegionSpanX == mCountX || spanX == mCountX) {
2342            deltaX = 0;
2343        }
2344        if (dropRegionSpanY == mCountY || spanY == mCountY) {
2345            deltaY = 0;
2346        }
2347
2348        if (deltaX == 0 && deltaY == 0) {
2349            // No idea what to do, give a random direction.
2350            resultDirection[0] = 1;
2351            resultDirection[1] = 0;
2352        } else {
2353            computeDirectionVector(deltaX, deltaY, resultDirection);
2354        }
2355    }
2356
2357    // For a given cell and span, fetch the set of views intersecting the region.
2358    private void getViewsIntersectingRegion(int cellX, int cellY, int spanX, int spanY,
2359            View dragView, Rect boundingRect, ArrayList<View> intersectingViews) {
2360        if (boundingRect != null) {
2361            boundingRect.set(cellX, cellY, cellX + spanX, cellY + spanY);
2362        }
2363        intersectingViews.clear();
2364        Rect r0 = new Rect(cellX, cellY, cellX + spanX, cellY + spanY);
2365        Rect r1 = new Rect();
2366        final int count = mShortcutsAndWidgets.getChildCount();
2367        for (int i = 0; i < count; i++) {
2368            View child = mShortcutsAndWidgets.getChildAt(i);
2369            if (child == dragView) continue;
2370            LayoutParams lp = (LayoutParams) child.getLayoutParams();
2371            r1.set(lp.cellX, lp.cellY, lp.cellX + lp.cellHSpan, lp.cellY + lp.cellVSpan);
2372            if (Rect.intersects(r0, r1)) {
2373                mIntersectingViews.add(child);
2374                if (boundingRect != null) {
2375                    boundingRect.union(r1);
2376                }
2377            }
2378        }
2379    }
2380
2381    boolean isNearestDropLocationOccupied(int pixelX, int pixelY, int spanX, int spanY,
2382            View dragView, int[] result) {
2383        result = findNearestArea(pixelX, pixelY, spanX, spanY, result);
2384        getViewsIntersectingRegion(result[0], result[1], spanX, spanY, dragView, null,
2385                mIntersectingViews);
2386        return !mIntersectingViews.isEmpty();
2387    }
2388
2389    void revertTempState() {
2390        completeAndClearReorderPreviewAnimations();
2391        if (isItemPlacementDirty() && !DESTRUCTIVE_REORDER) {
2392            final int count = mShortcutsAndWidgets.getChildCount();
2393            for (int i = 0; i < count; i++) {
2394                View child = mShortcutsAndWidgets.getChildAt(i);
2395                LayoutParams lp = (LayoutParams) child.getLayoutParams();
2396                if (lp.tmpCellX != lp.cellX || lp.tmpCellY != lp.cellY) {
2397                    lp.tmpCellX = lp.cellX;
2398                    lp.tmpCellY = lp.cellY;
2399                    animateChildToPosition(child, lp.cellX, lp.cellY, REORDER_ANIMATION_DURATION,
2400                            0, false, false);
2401                }
2402            }
2403            setItemPlacementDirty(false);
2404        }
2405    }
2406
2407    boolean createAreaForResize(int cellX, int cellY, int spanX, int spanY,
2408            View dragView, int[] direction, boolean commit) {
2409        int[] pixelXY = new int[2];
2410        regionToCenterPoint(cellX, cellY, spanX, spanY, pixelXY);
2411
2412        // First we determine if things have moved enough to cause a different layout
2413        ItemConfiguration swapSolution = findReorderSolution(pixelXY[0], pixelXY[1], spanX, spanY,
2414                 spanX,  spanY, direction, dragView,  true,  new ItemConfiguration());
2415
2416        setUseTempCoords(true);
2417        if (swapSolution != null && swapSolution.isSolution) {
2418            // If we're just testing for a possible location (MODE_ACCEPT_DROP), we don't bother
2419            // committing anything or animating anything as we just want to determine if a solution
2420            // exists
2421            copySolutionToTempState(swapSolution, dragView);
2422            setItemPlacementDirty(true);
2423            animateItemsToSolution(swapSolution, dragView, commit);
2424
2425            if (commit) {
2426                commitTempPlacement();
2427                completeAndClearReorderPreviewAnimations();
2428                setItemPlacementDirty(false);
2429            } else {
2430                beginOrAdjustReorderPreviewAnimations(swapSolution, dragView,
2431                        REORDER_ANIMATION_DURATION, ReorderPreviewAnimation.MODE_PREVIEW);
2432            }
2433            mShortcutsAndWidgets.requestLayout();
2434        }
2435        return swapSolution.isSolution;
2436    }
2437
2438    int[] performReorder(int pixelX, int pixelY, int minSpanX, int minSpanY, int spanX, int spanY,
2439            View dragView, int[] result, int resultSpan[], int mode) {
2440        // First we determine if things have moved enough to cause a different layout
2441        result = findNearestArea(pixelX, pixelY, spanX, spanY, result);
2442
2443        if (resultSpan == null) {
2444            resultSpan = new int[2];
2445        }
2446
2447        // When we are checking drop validity or actually dropping, we don't recompute the
2448        // direction vector, since we want the solution to match the preview, and it's possible
2449        // that the exact position of the item has changed to result in a new reordering outcome.
2450        if ((mode == MODE_ON_DROP || mode == MODE_ON_DROP_EXTERNAL || mode == MODE_ACCEPT_DROP)
2451               && mPreviousReorderDirection[0] != INVALID_DIRECTION) {
2452            mDirectionVector[0] = mPreviousReorderDirection[0];
2453            mDirectionVector[1] = mPreviousReorderDirection[1];
2454            // We reset this vector after drop
2455            if (mode == MODE_ON_DROP || mode == MODE_ON_DROP_EXTERNAL) {
2456                mPreviousReorderDirection[0] = INVALID_DIRECTION;
2457                mPreviousReorderDirection[1] = INVALID_DIRECTION;
2458            }
2459        } else {
2460            getDirectionVectorForDrop(pixelX, pixelY, spanX, spanY, dragView, mDirectionVector);
2461            mPreviousReorderDirection[0] = mDirectionVector[0];
2462            mPreviousReorderDirection[1] = mDirectionVector[1];
2463        }
2464
2465        // Find a solution involving pushing / displacing any items in the way
2466        ItemConfiguration swapSolution = findReorderSolution(pixelX, pixelY, minSpanX, minSpanY,
2467                 spanX,  spanY, mDirectionVector, dragView,  true,  new ItemConfiguration());
2468
2469        // We attempt the approach which doesn't shuffle views at all
2470        ItemConfiguration noShuffleSolution = findConfigurationNoShuffle(pixelX, pixelY, minSpanX,
2471                minSpanY, spanX, spanY, dragView, new ItemConfiguration());
2472
2473        ItemConfiguration finalSolution = null;
2474
2475        // If the reorder solution requires resizing (shrinking) the item being dropped, we instead
2476        // favor a solution in which the item is not resized, but
2477        if (swapSolution.isSolution && swapSolution.area() >= noShuffleSolution.area()) {
2478            finalSolution = swapSolution;
2479        } else if (noShuffleSolution.isSolution) {
2480            finalSolution = noShuffleSolution;
2481        }
2482
2483        if (mode == MODE_SHOW_REORDER_HINT) {
2484            if (finalSolution != null) {
2485                beginOrAdjustReorderPreviewAnimations(finalSolution, dragView, 0,
2486                        ReorderPreviewAnimation.MODE_HINT);
2487                result[0] = finalSolution.dragViewX;
2488                result[1] = finalSolution.dragViewY;
2489                resultSpan[0] = finalSolution.dragViewSpanX;
2490                resultSpan[1] = finalSolution.dragViewSpanY;
2491            } else {
2492                result[0] = result[1] = resultSpan[0] = resultSpan[1] = -1;
2493            }
2494            return result;
2495        }
2496
2497        boolean foundSolution = true;
2498        if (!DESTRUCTIVE_REORDER) {
2499            setUseTempCoords(true);
2500        }
2501
2502        if (finalSolution != null) {
2503            result[0] = finalSolution.dragViewX;
2504            result[1] = finalSolution.dragViewY;
2505            resultSpan[0] = finalSolution.dragViewSpanX;
2506            resultSpan[1] = finalSolution.dragViewSpanY;
2507
2508            // If we're just testing for a possible location (MODE_ACCEPT_DROP), we don't bother
2509            // committing anything or animating anything as we just want to determine if a solution
2510            // exists
2511            if (mode == MODE_DRAG_OVER || mode == MODE_ON_DROP || mode == MODE_ON_DROP_EXTERNAL) {
2512                if (!DESTRUCTIVE_REORDER) {
2513                    copySolutionToTempState(finalSolution, dragView);
2514                }
2515                setItemPlacementDirty(true);
2516                animateItemsToSolution(finalSolution, dragView, mode == MODE_ON_DROP);
2517
2518                if (!DESTRUCTIVE_REORDER &&
2519                        (mode == MODE_ON_DROP || mode == MODE_ON_DROP_EXTERNAL)) {
2520                    commitTempPlacement();
2521                    completeAndClearReorderPreviewAnimations();
2522                    setItemPlacementDirty(false);
2523                } else {
2524                    beginOrAdjustReorderPreviewAnimations(finalSolution, dragView,
2525                            REORDER_ANIMATION_DURATION,  ReorderPreviewAnimation.MODE_PREVIEW);
2526                }
2527            }
2528        } else {
2529            foundSolution = false;
2530            result[0] = result[1] = resultSpan[0] = resultSpan[1] = -1;
2531        }
2532
2533        if ((mode == MODE_ON_DROP || !foundSolution) && !DESTRUCTIVE_REORDER) {
2534            setUseTempCoords(false);
2535        }
2536
2537        mShortcutsAndWidgets.requestLayout();
2538        return result;
2539    }
2540
2541    void setItemPlacementDirty(boolean dirty) {
2542        mItemPlacementDirty = dirty;
2543    }
2544    boolean isItemPlacementDirty() {
2545        return mItemPlacementDirty;
2546    }
2547
2548    @Thunk class ItemConfiguration {
2549        HashMap<View, CellAndSpan> map = new HashMap<View, CellAndSpan>();
2550        private HashMap<View, CellAndSpan> savedMap = new HashMap<View, CellAndSpan>();
2551        ArrayList<View> sortedViews = new ArrayList<View>();
2552        ArrayList<View> intersectingViews;
2553        boolean isSolution = false;
2554        int dragViewX, dragViewY, dragViewSpanX, dragViewSpanY;
2555
2556        void save() {
2557            // Copy current state into savedMap
2558            for (View v: map.keySet()) {
2559                map.get(v).copy(savedMap.get(v));
2560            }
2561        }
2562
2563        void restore() {
2564            // Restore current state from savedMap
2565            for (View v: savedMap.keySet()) {
2566                savedMap.get(v).copy(map.get(v));
2567            }
2568        }
2569
2570        void add(View v, CellAndSpan cs) {
2571            map.put(v, cs);
2572            savedMap.put(v, new CellAndSpan());
2573            sortedViews.add(v);
2574        }
2575
2576        int area() {
2577            return dragViewSpanX * dragViewSpanY;
2578        }
2579    }
2580
2581    private class CellAndSpan {
2582        int x, y;
2583        int spanX, spanY;
2584
2585        public CellAndSpan() {
2586        }
2587
2588        public void copy(CellAndSpan copy) {
2589            copy.x = x;
2590            copy.y = y;
2591            copy.spanX = spanX;
2592            copy.spanY = spanY;
2593        }
2594
2595        public CellAndSpan(int x, int y, int spanX, int spanY) {
2596            this.x = x;
2597            this.y = y;
2598            this.spanX = spanX;
2599            this.spanY = spanY;
2600        }
2601
2602        public String toString() {
2603            return "(" + x + ", " + y + ": " + spanX + ", " + spanY + ")";
2604        }
2605
2606    }
2607
2608    /**
2609     * Find a starting cell position that will fit the given bounds nearest the requested
2610     * cell location. Uses Euclidean distance to score multiple vacant areas.
2611     *
2612     * @param pixelX The X location at which you want to search for a vacant area.
2613     * @param pixelY The Y location at which you want to search for a vacant area.
2614     * @param spanX Horizontal span of the object.
2615     * @param spanY Vertical span of the object.
2616     * @param ignoreView Considers space occupied by this view as unoccupied
2617     * @param result Previously returned value to possibly recycle.
2618     * @return The X, Y cell of a vacant area that can contain this object,
2619     *         nearest the requested location.
2620     */
2621    int[] findNearestArea(int pixelX, int pixelY, int spanX, int spanY, int[] result) {
2622        return findNearestArea(pixelX, pixelY, spanX, spanY, spanX, spanY, false, result, null);
2623    }
2624
2625    boolean existsEmptyCell() {
2626        return findCellForSpan(null, 1, 1);
2627    }
2628
2629    /**
2630     * Finds the upper-left coordinate of the first rectangle in the grid that can
2631     * hold a cell of the specified dimensions. If intersectX and intersectY are not -1,
2632     * then this method will only return coordinates for rectangles that contain the cell
2633     * (intersectX, intersectY)
2634     *
2635     * @param cellXY The array that will contain the position of a vacant cell if such a cell
2636     *               can be found.
2637     * @param spanX The horizontal span of the cell we want to find.
2638     * @param spanY The vertical span of the cell we want to find.
2639     *
2640     * @return True if a vacant cell of the specified dimension was found, false otherwise.
2641     */
2642    public boolean findCellForSpan(int[] cellXY, int spanX, int spanY) {
2643        boolean foundCell = false;
2644        final int endX = mCountX - (spanX - 1);
2645        final int endY = mCountY - (spanY - 1);
2646
2647        for (int y = 0; y < endY && !foundCell; y++) {
2648            inner:
2649            for (int x = 0; x < endX; x++) {
2650                for (int i = 0; i < spanX; i++) {
2651                    for (int j = 0; j < spanY; j++) {
2652                        if (mOccupied[x + i][y + j]) {
2653                            // small optimization: we can skip to after the column we just found
2654                            // an occupied cell
2655                            x += i;
2656                            continue inner;
2657                        }
2658                    }
2659                }
2660                if (cellXY != null) {
2661                    cellXY[0] = x;
2662                    cellXY[1] = y;
2663                }
2664                foundCell = true;
2665                break;
2666            }
2667        }
2668
2669        return foundCell;
2670    }
2671
2672    /**
2673     * A drag event has begun over this layout.
2674     * It may have begun over this layout (in which case onDragChild is called first),
2675     * or it may have begun on another layout.
2676     */
2677    void onDragEnter() {
2678        mDragEnforcer.onDragEnter();
2679        mDragging = true;
2680    }
2681
2682    /**
2683     * Called when drag has left this CellLayout or has been completed (successfully or not)
2684     */
2685    void onDragExit() {
2686        mDragEnforcer.onDragExit();
2687        // This can actually be called when we aren't in a drag, e.g. when adding a new
2688        // item to this layout via the customize drawer.
2689        // Guard against that case.
2690        if (mDragging) {
2691            mDragging = false;
2692        }
2693
2694        // Invalidate the drag data
2695        mDragCell[0] = mDragCell[1] = -1;
2696        mDragOutlineAnims[mDragOutlineCurrent].animateOut();
2697        mDragOutlineCurrent = (mDragOutlineCurrent + 1) % mDragOutlineAnims.length;
2698        revertTempState();
2699        setIsDragOverlapping(false);
2700    }
2701
2702    /**
2703     * Mark a child as having been dropped.
2704     * At the beginning of the drag operation, the child may have been on another
2705     * screen, but it is re-parented before this method is called.
2706     *
2707     * @param child The child that is being dropped
2708     */
2709    void onDropChild(View child) {
2710        if (child != null) {
2711            LayoutParams lp = (LayoutParams) child.getLayoutParams();
2712            lp.dropped = true;
2713            child.requestLayout();
2714        }
2715    }
2716
2717    /**
2718     * Computes a bounding rectangle for a range of cells
2719     *
2720     * @param cellX X coordinate of upper left corner expressed as a cell position
2721     * @param cellY Y coordinate of upper left corner expressed as a cell position
2722     * @param cellHSpan Width in cells
2723     * @param cellVSpan Height in cells
2724     * @param resultRect Rect into which to put the results
2725     */
2726    public void cellToRect(int cellX, int cellY, int cellHSpan, int cellVSpan, Rect resultRect) {
2727        final int cellWidth = mCellWidth;
2728        final int cellHeight = mCellHeight;
2729        final int widthGap = mWidthGap;
2730        final int heightGap = mHeightGap;
2731
2732        final int hStartPadding = getPaddingLeft();
2733        final int vStartPadding = getPaddingTop();
2734
2735        int width = cellHSpan * cellWidth + ((cellHSpan - 1) * widthGap);
2736        int height = cellVSpan * cellHeight + ((cellVSpan - 1) * heightGap);
2737
2738        int x = hStartPadding + cellX * (cellWidth + widthGap);
2739        int y = vStartPadding + cellY * (cellHeight + heightGap);
2740
2741        resultRect.set(x, y, x + width, y + height);
2742    }
2743
2744    /**
2745     * Computes the required horizontal and vertical cell spans to always
2746     * fit the given rectangle.
2747     *
2748     * @param width Width in pixels
2749     * @param height Height in pixels
2750     * @param result An array of length 2 in which to store the result (may be null).
2751     */
2752    public static int[] rectToCell(int width, int height, int[] result) {
2753        LauncherAppState app = LauncherAppState.getInstance();
2754        DeviceProfile grid = app.getDynamicGrid().getDeviceProfile();
2755        Rect padding = grid.getWorkspacePadding(grid.isLandscape ?
2756                CellLayout.LANDSCAPE : CellLayout.PORTRAIT);
2757
2758        // Always assume we're working with the smallest span to make sure we
2759        // reserve enough space in both orientations.
2760        int parentWidth = grid.calculateCellWidth(grid.widthPx
2761                - padding.left - padding.right, (int) grid.numColumns);
2762        int parentHeight = grid.calculateCellHeight(grid.heightPx
2763                - padding.top - padding.bottom, (int) grid.numRows);
2764        int smallerSize = Math.min(parentWidth, parentHeight);
2765
2766        // Always round up to next largest cell
2767        int spanX = (int) Math.ceil(width / (float) smallerSize);
2768        int spanY = (int) Math.ceil(height / (float) smallerSize);
2769
2770        if (result == null) {
2771            return new int[] { spanX, spanY };
2772        }
2773        result[0] = spanX;
2774        result[1] = spanY;
2775        return result;
2776    }
2777
2778    /**
2779     * Calculate the grid spans needed to fit given item
2780     */
2781    public void calculateSpans(ItemInfo info) {
2782        final int minWidth;
2783        final int minHeight;
2784
2785        if (info instanceof LauncherAppWidgetInfo) {
2786            minWidth = ((LauncherAppWidgetInfo) info).minWidth;
2787            minHeight = ((LauncherAppWidgetInfo) info).minHeight;
2788        } else if (info instanceof PendingAddWidgetInfo) {
2789            minWidth = ((PendingAddWidgetInfo) info).minWidth;
2790            minHeight = ((PendingAddWidgetInfo) info).minHeight;
2791        } else {
2792            // It's not a widget, so it must be 1x1
2793            info.spanX = info.spanY = 1;
2794            return;
2795        }
2796        int[] spans = rectToCell(minWidth, minHeight, null);
2797        info.spanX = spans[0];
2798        info.spanY = spans[1];
2799    }
2800
2801    private void clearOccupiedCells() {
2802        for (int x = 0; x < mCountX; x++) {
2803            for (int y = 0; y < mCountY; y++) {
2804                mOccupied[x][y] = false;
2805            }
2806        }
2807    }
2808
2809    public void markCellsAsOccupiedForView(View view) {
2810        if (view == null || view.getParent() != mShortcutsAndWidgets) return;
2811        LayoutParams lp = (LayoutParams) view.getLayoutParams();
2812        markCellsForView(lp.cellX, lp.cellY, lp.cellHSpan, lp.cellVSpan, mOccupied, true);
2813    }
2814
2815    public void markCellsAsUnoccupiedForView(View view) {
2816        if (view == null || view.getParent() != mShortcutsAndWidgets) return;
2817        LayoutParams lp = (LayoutParams) view.getLayoutParams();
2818        markCellsForView(lp.cellX, lp.cellY, lp.cellHSpan, lp.cellVSpan, mOccupied, false);
2819    }
2820
2821    private void markCellsForView(int cellX, int cellY, int spanX, int spanY, boolean[][] occupied,
2822            boolean value) {
2823        if (cellX < 0 || cellY < 0) return;
2824        for (int x = cellX; x < cellX + spanX && x < mCountX; x++) {
2825            for (int y = cellY; y < cellY + spanY && y < mCountY; y++) {
2826                occupied[x][y] = value;
2827            }
2828        }
2829    }
2830
2831    public int getDesiredWidth() {
2832        return getPaddingLeft() + getPaddingRight() + (mCountX * mCellWidth) +
2833                (Math.max((mCountX - 1), 0) * mWidthGap);
2834    }
2835
2836    public int getDesiredHeight()  {
2837        return getPaddingTop() + getPaddingBottom() + (mCountY * mCellHeight) +
2838                (Math.max((mCountY - 1), 0) * mHeightGap);
2839    }
2840
2841    public boolean isOccupied(int x, int y) {
2842        if (x < mCountX && y < mCountY) {
2843            return mOccupied[x][y];
2844        } else {
2845            throw new RuntimeException("Position exceeds the bound of this CellLayout");
2846        }
2847    }
2848
2849    @Override
2850    public ViewGroup.LayoutParams generateLayoutParams(AttributeSet attrs) {
2851        return new CellLayout.LayoutParams(getContext(), attrs);
2852    }
2853
2854    @Override
2855    protected boolean checkLayoutParams(ViewGroup.LayoutParams p) {
2856        return p instanceof CellLayout.LayoutParams;
2857    }
2858
2859    @Override
2860    protected ViewGroup.LayoutParams generateLayoutParams(ViewGroup.LayoutParams p) {
2861        return new CellLayout.LayoutParams(p);
2862    }
2863
2864    public static class LayoutParams extends ViewGroup.MarginLayoutParams {
2865        /**
2866         * Horizontal location of the item in the grid.
2867         */
2868        @ViewDebug.ExportedProperty
2869        public int cellX;
2870
2871        /**
2872         * Vertical location of the item in the grid.
2873         */
2874        @ViewDebug.ExportedProperty
2875        public int cellY;
2876
2877        /**
2878         * Temporary horizontal location of the item in the grid during reorder
2879         */
2880        public int tmpCellX;
2881
2882        /**
2883         * Temporary vertical location of the item in the grid during reorder
2884         */
2885        public int tmpCellY;
2886
2887        /**
2888         * Indicates that the temporary coordinates should be used to layout the items
2889         */
2890        public boolean useTmpCoords;
2891
2892        /**
2893         * Number of cells spanned horizontally by the item.
2894         */
2895        @ViewDebug.ExportedProperty
2896        public int cellHSpan;
2897
2898        /**
2899         * Number of cells spanned vertically by the item.
2900         */
2901        @ViewDebug.ExportedProperty
2902        public int cellVSpan;
2903
2904        /**
2905         * Indicates whether the item will set its x, y, width and height parameters freely,
2906         * or whether these will be computed based on cellX, cellY, cellHSpan and cellVSpan.
2907         */
2908        public boolean isLockedToGrid = true;
2909
2910        /**
2911         * Indicates that this item should use the full extents of its parent.
2912         */
2913        public boolean isFullscreen = false;
2914
2915        /**
2916         * Indicates whether this item can be reordered. Always true except in the case of the
2917         * the AllApps button.
2918         */
2919        public boolean canReorder = true;
2920
2921        // X coordinate of the view in the layout.
2922        @ViewDebug.ExportedProperty
2923        int x;
2924        // Y coordinate of the view in the layout.
2925        @ViewDebug.ExportedProperty
2926        int y;
2927
2928        boolean dropped;
2929
2930        public LayoutParams(Context c, AttributeSet attrs) {
2931            super(c, attrs);
2932            cellHSpan = 1;
2933            cellVSpan = 1;
2934        }
2935
2936        public LayoutParams(ViewGroup.LayoutParams source) {
2937            super(source);
2938            cellHSpan = 1;
2939            cellVSpan = 1;
2940        }
2941
2942        public LayoutParams(LayoutParams source) {
2943            super(source);
2944            this.cellX = source.cellX;
2945            this.cellY = source.cellY;
2946            this.cellHSpan = source.cellHSpan;
2947            this.cellVSpan = source.cellVSpan;
2948        }
2949
2950        public LayoutParams(int cellX, int cellY, int cellHSpan, int cellVSpan) {
2951            super(LayoutParams.MATCH_PARENT, LayoutParams.MATCH_PARENT);
2952            this.cellX = cellX;
2953            this.cellY = cellY;
2954            this.cellHSpan = cellHSpan;
2955            this.cellVSpan = cellVSpan;
2956        }
2957
2958        public void setup(int cellWidth, int cellHeight, int widthGap, int heightGap,
2959                boolean invertHorizontally, int colCount) {
2960            if (isLockedToGrid) {
2961                final int myCellHSpan = cellHSpan;
2962                final int myCellVSpan = cellVSpan;
2963                int myCellX = useTmpCoords ? tmpCellX : cellX;
2964                int myCellY = useTmpCoords ? tmpCellY : cellY;
2965
2966                if (invertHorizontally) {
2967                    myCellX = colCount - myCellX - cellHSpan;
2968                }
2969
2970                width = myCellHSpan * cellWidth + ((myCellHSpan - 1) * widthGap) -
2971                        leftMargin - rightMargin;
2972                height = myCellVSpan * cellHeight + ((myCellVSpan - 1) * heightGap) -
2973                        topMargin - bottomMargin;
2974                x = (int) (myCellX * (cellWidth + widthGap) + leftMargin);
2975                y = (int) (myCellY * (cellHeight + heightGap) + topMargin);
2976            }
2977        }
2978
2979        public String toString() {
2980            return "(" + this.cellX + ", " + this.cellY + ")";
2981        }
2982
2983        public void setWidth(int width) {
2984            this.width = width;
2985        }
2986
2987        public int getWidth() {
2988            return width;
2989        }
2990
2991        public void setHeight(int height) {
2992            this.height = height;
2993        }
2994
2995        public int getHeight() {
2996            return height;
2997        }
2998
2999        public void setX(int x) {
3000            this.x = x;
3001        }
3002
3003        public int getX() {
3004            return x;
3005        }
3006
3007        public void setY(int y) {
3008            this.y = y;
3009        }
3010
3011        public int getY() {
3012            return y;
3013        }
3014    }
3015
3016    // This class stores info for two purposes:
3017    // 1. When dragging items (mDragInfo in Workspace), we store the View, its cellX & cellY,
3018    //    its spanX, spanY, and the screen it is on
3019    // 2. When long clicking on an empty cell in a CellLayout, we save information about the
3020    //    cellX and cellY coordinates and which page was clicked. We then set this as a tag on
3021    //    the CellLayout that was long clicked
3022    static final class CellInfo {
3023        View cell;
3024        int cellX = -1;
3025        int cellY = -1;
3026        int spanX;
3027        int spanY;
3028        long screenId;
3029        long container;
3030
3031        CellInfo(View v, ItemInfo info) {
3032            cell = v;
3033            cellX = info.cellX;
3034            cellY = info.cellY;
3035            spanX = info.spanX;
3036            spanY = info.spanY;
3037            screenId = info.screenId;
3038            container = info.container;
3039        }
3040
3041        @Override
3042        public String toString() {
3043            return "Cell[view=" + (cell == null ? "null" : cell.getClass())
3044                    + ", x=" + cellX + ", y=" + cellY + "]";
3045        }
3046    }
3047
3048    public boolean lastDownOnOccupiedCell() {
3049        return mLastDownOnOccupiedCell;
3050    }
3051
3052    public boolean findVacantCell(int spanX, int spanY, int[] outXY) {
3053        return Utilities.findVacantCell(outXY, spanX, spanY, mCountX, mCountY, mOccupied);
3054    }
3055}
3056