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