diff --git a/quickstep/src/com/android/launcher3/uioverrides/QuickstepLauncher.java b/quickstep/src/com/android/launcher3/uioverrides/QuickstepLauncher.java
index 165ed80..5b0c8c3 100644
--- a/quickstep/src/com/android/launcher3/uioverrides/QuickstepLauncher.java
+++ b/quickstep/src/com/android/launcher3/uioverrides/QuickstepLauncher.java
@@ -480,7 +480,11 @@
 
     @Override
     public void onDestroy() {
-        mAppTransitionManager.onActivityDestroyed();
+        if (mAppTransitionManager != null) {
+            mAppTransitionManager.onActivityDestroyed();
+        }
+        mAppTransitionManager = null;
+
         if (mUnfoldTransitionProgressProvider != null) {
             SystemUiProxy.INSTANCE.get(this).setUnfoldAnimationListener(null);
             mUnfoldTransitionProgressProvider.destroy();
diff --git a/quickstep/src/com/android/quickstep/util/TaskKeyByLastActiveTimeCache.java b/quickstep/src/com/android/quickstep/util/TaskKeyByLastActiveTimeCache.java
index 79ca076..21c9e09 100644
--- a/quickstep/src/com/android/quickstep/util/TaskKeyByLastActiveTimeCache.java
+++ b/quickstep/src/com/android/quickstep/util/TaskKeyByLastActiveTimeCache.java
@@ -44,7 +44,7 @@
     private final PriorityQueue<Task.TaskKey> mQueue;
 
     public TaskKeyByLastActiveTimeCache(int maxSize) {
-        mMap = new HashMap(maxSize);
+        mMap = new HashMap(0);
         mQueue = new PriorityQueue<>(Comparator.comparingLong(t -> t.lastActiveTime));
         mMaxSize = new AtomicInteger(maxSize);
     }
@@ -106,7 +106,8 @@
     }
 
     /**
-     * Adds an entry to the cache, optionally evicting the last accessed entry
+     * Adds an entry to the cache, optionally evicting the last accessed entry excluding the newly
+     * added entry
      */
     @Override
     public final synchronized void put(Task.TaskKey key, V value) {
@@ -117,9 +118,9 @@
                 mQueue.remove(entry.mKey);
             }
 
+            removeExcessIfNeeded(mMaxSize.get() - 1);
             mMap.put(key.id, new Entry<>(key, value));
             mQueue.add(key);
-            removeExcessIfNeeded();
         } else {
             Log.e(TAG, "Unexpected null key or value: " + key + ", " + value);
         }
@@ -143,11 +144,11 @@
     @Override
     public synchronized void updateCacheSizeAndRemoveExcess(int cacheSize) {
         mMaxSize.compareAndSet(mMaxSize.get(), cacheSize);
-        removeExcessIfNeeded();
+        removeExcessIfNeeded(mMaxSize.get());
     }
 
-    private synchronized void removeExcessIfNeeded() {
-        while (mQueue.size() > mMaxSize.get() && !mQueue.isEmpty()) {
+    private synchronized void removeExcessIfNeeded(int maxSize) {
+        while (mQueue.size() > maxSize && !mQueue.isEmpty()) {
             Task.TaskKey key = mQueue.poll();
             mMap.remove(key.id);
         }
diff --git a/quickstep/tests/src/com/android/quickstep/StartLauncherViaGestureTests.java b/quickstep/tests/src/com/android/quickstep/StartLauncherViaGestureTests.java
index a89eab5..3a89278 100644
--- a/quickstep/tests/src/com/android/quickstep/StartLauncherViaGestureTests.java
+++ b/quickstep/tests/src/com/android/quickstep/StartLauncherViaGestureTests.java
@@ -49,6 +49,8 @@
 
     @Test
     @NavigationModeSwitch
+    // Stress tests are long. We permanently demote them from presubmit to match the presubmit SLO.
+    @Stability(flavors = LOCAL | PLATFORM_POSTSUBMIT)
     public void testStressPressHome() {
         for (int i = 0; i < STRESS_REPEAT_COUNT; ++i) {
             // Destroy Launcher activity.
@@ -61,7 +63,8 @@
 
     @Test
     @NavigationModeSwitch
-    @Stability(flavors = LOCAL | PLATFORM_POSTSUBMIT) // b/187761685
+    // Stress tests are long. We permanently demote them from presubmit to match the presubmit SLO.
+    @Stability(flavors = LOCAL | PLATFORM_POSTSUBMIT)
     public void testStressSwipeToOverview() {
         for (int i = 0; i < STRESS_REPEAT_COUNT; ++i) {
             // Destroy Launcher activity.
diff --git a/res/values/attrs.xml b/res/values/attrs.xml
index 20e7089..8d84c90 100644
--- a/res/values/attrs.xml
+++ b/res/values/attrs.xml
@@ -164,7 +164,19 @@
 
         <!-- numFolderRows & numFolderColumns defaults to numRows & numColumns, if not specified -->
         <attr name="numFolderRows" format="integer" />
+        <!-- defaults to numFolderRows, if not specified -->
+        <attr name="numFolderRowsLandscape" format="integer" />
+        <!-- defaults to numFolderRows, if not specified -->
+        <attr name="numFolderRowsTwoPanelLandscape" format="integer" />
+        <!-- defaults to numFolderRows, if not specified -->
+        <attr name="numFolderRowsTwoPanelPortrait" format="integer" />
         <attr name="numFolderColumns" format="integer" />
+        <!-- defaults to numFolderColumns, if not specified -->
+        <attr name="numFolderColumnsLandscape" format="integer" />
+        <!-- defaults to numFolderColumns, if not specified -->
+        <attr name="numFolderColumnsTwoPanelLandscape" format="integer" />
+        <!-- defaults to numFolderColumns, if not specified -->
+        <attr name="numFolderColumnsTwoPanelPortrait" format="integer" />
         <!-- Support attributes in FolderStyle -->
         <attr name="folderStyle" format="reference" />
 
diff --git a/src/com/android/launcher3/DeviceProfile.java b/src/com/android/launcher3/DeviceProfile.java
index 7ca8b82..badd1c4 100644
--- a/src/com/android/launcher3/DeviceProfile.java
+++ b/src/com/android/launcher3/DeviceProfile.java
@@ -439,8 +439,8 @@
         }
 
         folderLabelTextScale = res.getFloat(R.dimen.folder_label_text_scale);
-        numFolderRows = inv.numFolderRows;
-        numFolderColumns = inv.numFolderColumns;
+        numFolderRows = inv.numFolderRows[mTypeIndex];
+        numFolderColumns = inv.numFolderColumns[mTypeIndex];
 
         if (mIsScalableGrid && inv.folderStyle != INVALID_RESOURCE_HANDLE) {
             TypedArray folderStyle = context.obtainStyledAttributes(inv.folderStyle,
diff --git a/src/com/android/launcher3/InvariantDeviceProfile.java b/src/com/android/launcher3/InvariantDeviceProfile.java
index 567d0c5..dfbbcaa 100644
--- a/src/com/android/launcher3/InvariantDeviceProfile.java
+++ b/src/com/android/launcher3/InvariantDeviceProfile.java
@@ -122,8 +122,8 @@
     /**
      * Number of icons per row and column in the folder.
      */
-    public int numFolderRows;
-    public int numFolderColumns;
+    public int[] numFolderRows;
+    public int[] numFolderColumns;
     public float[] iconSize;
     public float[] iconTextSize;
     public int iconBitmapSize;
@@ -810,8 +810,8 @@
         public final int numSearchContainerColumns;
         public final int deviceCategory;
 
-        private final int numFolderRows;
-        private final int numFolderColumns;
+        private final int[] numFolderRows = new int[COUNT_SIZES];
+        private final int[] numFolderColumns = new int[COUNT_SIZES];
         private final @StyleRes int folderStyle;
         private final @StyleRes int cellStyle;
 
@@ -888,11 +888,39 @@
                     a.getResourceId(R.styleable.GridDisplayOption_inlineNavButtonsEndSpacing,
                             R.dimen.taskbar_button_margin_default);
 
-            numFolderRows = a.getInt(
+            numFolderRows[INDEX_DEFAULT] = a.getInt(
                     R.styleable.GridDisplayOption_numFolderRows, numRows);
-            numFolderColumns = a.getInt(
+            numFolderColumns[INDEX_DEFAULT] = a.getInt(
                     R.styleable.GridDisplayOption_numFolderColumns, numColumns);
 
+            if (FeatureFlags.enableResponsiveWorkspace()) {
+                numFolderRows[INDEX_LANDSCAPE] = a.getInt(
+                        R.styleable.GridDisplayOption_numFolderRowsLandscape,
+                        numFolderRows[INDEX_DEFAULT]);
+                numFolderColumns[INDEX_LANDSCAPE] = a.getInt(
+                        R.styleable.GridDisplayOption_numFolderColumnsLandscape,
+                        numFolderColumns[INDEX_DEFAULT]);
+                numFolderRows[INDEX_TWO_PANEL_PORTRAIT] = a.getInt(
+                        R.styleable.GridDisplayOption_numFolderRowsTwoPanelPortrait,
+                        numFolderRows[INDEX_DEFAULT]);
+                numFolderColumns[INDEX_TWO_PANEL_PORTRAIT] = a.getInt(
+                        R.styleable.GridDisplayOption_numFolderColumnsTwoPanelPortrait,
+                        numFolderColumns[INDEX_DEFAULT]);
+                numFolderRows[INDEX_TWO_PANEL_LANDSCAPE] = a.getInt(
+                        R.styleable.GridDisplayOption_numFolderRowsTwoPanelLandscape,
+                        numFolderRows[INDEX_DEFAULT]);
+                numFolderColumns[INDEX_TWO_PANEL_LANDSCAPE] = a.getInt(
+                        R.styleable.GridDisplayOption_numFolderColumnsTwoPanelLandscape,
+                        numFolderColumns[INDEX_DEFAULT]);
+            } else {
+                numFolderRows[INDEX_LANDSCAPE] = numFolderRows[INDEX_DEFAULT];
+                numFolderColumns[INDEX_LANDSCAPE] = numFolderColumns[INDEX_DEFAULT];
+                numFolderRows[INDEX_TWO_PANEL_PORTRAIT] = numFolderRows[INDEX_DEFAULT];
+                numFolderColumns[INDEX_TWO_PANEL_PORTRAIT] = numFolderColumns[INDEX_DEFAULT];
+                numFolderRows[INDEX_TWO_PANEL_LANDSCAPE] = numFolderRows[INDEX_DEFAULT];
+                numFolderColumns[INDEX_TWO_PANEL_LANDSCAPE] = numFolderColumns[INDEX_DEFAULT];
+            }
+
             folderStyle = a.getResourceId(R.styleable.GridDisplayOption_folderStyle,
                     INVALID_RESOURCE_HANDLE);
 
diff --git a/src/com/android/launcher3/Launcher.java b/src/com/android/launcher3/Launcher.java
index 0099806..9f7575d 100644
--- a/src/com/android/launcher3/Launcher.java
+++ b/src/com/android/launcher3/Launcher.java
@@ -528,6 +528,7 @@
         mAppWidgetManager = new WidgetManagerHelper(this);
         mAppWidgetHolder = createAppWidgetHolder();
         mAppWidgetHolder.startListening();
+        mAppWidgetHolder.addProviderChangeListener(() -> refreshAndBindWidgetsForPackageUser(null));
 
         mPopupDataProvider = new PopupDataProvider(this::updateNotificationDots);
 
diff --git a/src/com/android/launcher3/celllayout/MulticellReorderAlgorithm.java b/src/com/android/launcher3/celllayout/MulticellReorderAlgorithm.java
index b7d8093..7deb653 100644
--- a/src/com/android/launcher3/celllayout/MulticellReorderAlgorithm.java
+++ b/src/com/android/launcher3/celllayout/MulticellReorderAlgorithm.java
@@ -38,8 +38,8 @@
         mSeam = new View(cellLayout.getContext());
     }
 
-    private ItemConfiguration removeSeamFromSolution(
-            ItemConfiguration solution) {
+    public ItemConfiguration removeSeamFromSolution(ItemConfiguration solution) {
+        solution.map.remove(mSeam);
         solution.map.forEach((view, cell) -> cell.cellX =
                 cell.cellX > mCellLayout.getCountX() / 2 ? cell.cellX - 1 : cell.cellX);
         solution.cellX =
@@ -48,9 +48,8 @@
     }
 
     @Override
-    public ItemConfiguration closestEmptySpaceReorder(int pixelX, int pixelY,
-            int minSpanX, int minSpanY,
-            int spanX, int spanY) {
+    public ItemConfiguration closestEmptySpaceReorder(int pixelX, int pixelY, int minSpanX,
+            int minSpanY, int spanX, int spanY) {
         return removeSeamFromSolution(simulateSeam(
                 () -> super.closestEmptySpaceReorder(pixelX, pixelY, minSpanX, minSpanY, spanX,
                         spanY)));
diff --git a/src/com/android/launcher3/celllayout/ReorderAlgorithm.java b/src/com/android/launcher3/celllayout/ReorderAlgorithm.java
index 05bd13d..0f6464b 100644
--- a/src/com/android/launcher3/celllayout/ReorderAlgorithm.java
+++ b/src/com/android/launcher3/celllayout/ReorderAlgorithm.java
@@ -62,6 +62,14 @@
     public ItemConfiguration findReorderSolution(int pixelX, int pixelY, int minSpanX,
             int minSpanY, int spanX, int spanY, int[] direction, View dragView, boolean decX,
             ItemConfiguration solution) {
+        return findReorderSolutionRecursive(pixelX, pixelY, minSpanX, minSpanY, spanX, spanY,
+                direction, dragView, decX, solution);
+    }
+
+
+    private ItemConfiguration findReorderSolutionRecursive(int pixelX, int pixelY,
+            int minSpanX, int minSpanY, int spanX, int spanY, int[] direction, View dragView,
+            boolean decX, ItemConfiguration solution) {
         // Copy the current state into the solution. This solution will be manipulated as necessary.
         mCellLayout.copyCurrentStateToSolution(solution, false);
         // Copy the current occupied array into the temporary occupied array. This array will be
@@ -83,11 +91,11 @@
             // We try shrinking the widget down to size in an alternating pattern, shrink 1 in
             // x, then 1 in y etc.
             if (spanX > minSpanX && (minSpanY == spanY || decX)) {
-                return findReorderSolution(pixelX, pixelY, minSpanX, minSpanY, spanX - 1, spanY,
-                        direction, dragView, false, solution);
+                return findReorderSolutionRecursive(pixelX, pixelY, minSpanX, minSpanY, spanX - 1,
+                        spanY, direction, dragView, false, solution);
             } else if (spanY > minSpanY) {
-                return findReorderSolution(pixelX, pixelY, minSpanX, minSpanY, spanX, spanY - 1,
-                        direction, dragView, true, solution);
+                return findReorderSolutionRecursive(pixelX, pixelY, minSpanX, minSpanY, spanX,
+                        spanY - 1, direction, dragView, true, solution);
             }
             solution.isSolution = false;
         } else {
@@ -193,8 +201,7 @@
         mCellLayout.getDirectionVectorForDrop(pixelX, pixelY, spanX, spanY, dragView,
                 mCellLayout.mDirectionVector);
 
-        ItemConfiguration dropInPlaceSolution = dropInPlaceSolution(pixelX, pixelY,
-                spanX, spanY,
+        ItemConfiguration dropInPlaceSolution = dropInPlaceSolution(pixelX, pixelY, spanX, spanY,
                 dragView);
 
         // Find a solution involving pushing / displacing any items in the way
@@ -203,8 +210,8 @@
                 new ItemConfiguration());
 
         // We attempt the approach which doesn't shuffle views at all
-        ItemConfiguration closestSpaceSolution = closestEmptySpaceReorder(
-                pixelX, pixelY, minSpanX, minSpanY, spanX, spanY);
+        ItemConfiguration closestSpaceSolution = closestEmptySpaceReorder(pixelX, pixelY, minSpanX,
+                minSpanY, spanX, spanY);
 
         // If the reorder solution requires resizing (shrinking) the item being dropped, we instead
         // favor a solution in which the item is not resized, but
diff --git a/src/com/android/launcher3/model/PackageUpdatedTask.java b/src/com/android/launcher3/model/PackageUpdatedTask.java
index 9a0a6eb..4f2d398 100644
--- a/src/com/android/launcher3/model/PackageUpdatedTask.java
+++ b/src/com/android/launcher3/model/PackageUpdatedTask.java
@@ -34,7 +34,6 @@
 import androidx.annotation.NonNull;
 
 import com.android.launcher3.Flags;
-import com.android.launcher3.Launcher;
 import com.android.launcher3.LauncherAppState;
 import com.android.launcher3.LauncherSettings;
 import com.android.launcher3.LauncherSettings.Favorites;
@@ -136,14 +135,6 @@
                         iconCache.updateIconsForPkg(packages[i], mUser);
                         activitiesLists.put(
                                 packages[i], appsList.updatePackage(context, packages[i], mUser));
-
-                        // The update may have changed which shortcuts/widgets are available.
-                        // Refresh the widgets for the package if we have an activity running.
-                        Launcher launcher = Launcher.ACTIVITY_TRACKER.getCreatedActivity();
-                        if (launcher != null) {
-                            launcher.refreshAndBindWidgetsForPackageUser(
-                                    new PackageUserKey(packages[i], mUser));
-                        }
                     }
                 }
                 // Since package was just updated, the target must be available now.
diff --git a/src/com/android/launcher3/touch/ItemLongClickListener.java b/src/com/android/launcher3/touch/ItemLongClickListener.java
index 96cc412..9e7d4dc 100644
--- a/src/com/android/launcher3/touch/ItemLongClickListener.java
+++ b/src/com/android/launcher3/touch/ItemLongClickListener.java
@@ -24,9 +24,12 @@
 import static com.android.launcher3.LauncherState.OVERVIEW;
 import static com.android.launcher3.logging.StatsLogManager.LauncherEvent.LAUNCHER_ALLAPPS_ITEM_LONG_PRESSED;
 
+import android.graphics.Point;
+import android.graphics.Rect;
 import android.view.View;
 import android.view.View.OnLongClickListener;
 
+import com.android.launcher3.DragSource;
 import com.android.launcher3.DropTarget;
 import com.android.launcher3.Launcher;
 import com.android.launcher3.celllayout.CellInfo;
@@ -40,6 +43,10 @@
 import com.android.launcher3.testing.shared.TestProtocol;
 import com.android.launcher3.views.BubbleTextHolder;
 import com.android.launcher3.widget.LauncherAppWidgetHostView;
+import com.android.launcher3.widget.NavigableAppWidgetHostView;
+import com.android.launcher3.widget.PendingItemDragHelper;
+import com.android.launcher3.widget.WidgetCell;
+import com.android.launcher3.widget.WidgetImageView;
 
 /**
  * Class to handle long-clicks on workspace items and start drag as a result.
@@ -91,7 +98,46 @@
         launcher.getWorkspace().startDrag(longClickCellInfo, dragOptions);
     }
 
+    private static boolean onWidgetItemLongClick(WidgetCell v) {
+        // Get the widget preview as the drag representation
+        WidgetImageView image = v.getWidgetView();
+        Launcher launcher = Launcher.getLauncher(v.getContext());
+        DragSource dragSource = (target, dragObject, success) -> { };
+
+        // If the ImageView doesn't have a drawable yet, the widget preview hasn't been loaded and
+        // we abort the drag.
+        if (image.getDrawable() == null && v.getAppWidgetHostViewPreview() == null) {
+            return false;
+        }
+
+        PendingItemDragHelper dragHelper = new PendingItemDragHelper(v);
+        // RemoteViews are being rendered in AppWidgetHostView in WidgetCell. And thus, the scale of
+        // RemoteViews is equivalent to the AppWidgetHostView scale.
+        dragHelper.setRemoteViewsPreview(v.getRemoteViewsPreview(), v.getAppWidgetHostViewScale());
+        dragHelper.setAppWidgetHostViewPreview(v.getAppWidgetHostViewPreview());
+
+        if (image.getDrawable() != null) {
+            int[] loc = new int[2];
+            launcher.getDragLayer().getLocationInDragLayer(image, loc);
+
+            dragHelper.startDrag(image.getBitmapBounds(), image.getDrawable().getIntrinsicWidth(),
+                    image.getWidth(), new Point(loc[0], loc[1]), dragSource, new DragOptions());
+        } else {
+            NavigableAppWidgetHostView preview = v.getAppWidgetHostViewPreview();
+            int[] loc = new int[2];
+            launcher.getDragLayer().getLocationInDragLayer(preview, loc);
+            Rect r = new Rect();
+            preview.getWorkspaceVisualDragBounds(r);
+            dragHelper.startDrag(r, preview.getMeasuredWidth(), preview.getMeasuredWidth(),
+                    new Point(loc[0], loc[1]), dragSource, new DragOptions());
+        }
+        return true;
+    }
+
     private static boolean onAllAppsItemLongClick(View view) {
+        if (view instanceof WidgetCell wc) {
+            return onWidgetItemLongClick(wc);
+        }
         TestLogging.recordEvent(TestProtocol.SEQUENCE_MAIN, "onAllAppsItemLongClick");
         view.cancelLongPress();
         View v = (view instanceof BubbleTextHolder)
diff --git a/src/com/android/launcher3/views/WidgetsEduView.java b/src/com/android/launcher3/views/WidgetsEduView.java
index e70b1cb..40c6115 100644
--- a/src/com/android/launcher3/views/WidgetsEduView.java
+++ b/src/com/android/launcher3/views/WidgetsEduView.java
@@ -20,15 +20,15 @@
 import android.util.AttributeSet;
 import android.view.LayoutInflater;
 
+import com.android.launcher3.BaseActivity;
 import com.android.launcher3.DeviceProfile;
 import com.android.launcher3.Insettable;
-import com.android.launcher3.Launcher;
 import com.android.launcher3.R;
 
 /**
  * Education view about widgets.
  */
-public class WidgetsEduView extends AbstractSlideInView<Launcher> implements Insettable {
+public class WidgetsEduView extends AbstractSlideInView<BaseActivity> implements Insettable {
 
     private static final int DEFAULT_CLOSE_DURATION = 200;
 
@@ -124,10 +124,10 @@
     }
 
     /** Shows widget education dialog. */
-    public static WidgetsEduView showEducationDialog(Launcher launcher) {
-        LayoutInflater layoutInflater = LayoutInflater.from(launcher);
+    public static WidgetsEduView showEducationDialog(BaseActivity activity) {
+        LayoutInflater layoutInflater = LayoutInflater.from(activity);
         WidgetsEduView v = (WidgetsEduView) layoutInflater.inflate(
-                R.layout.widgets_edu, launcher.getDragLayer(), false);
+                R.layout.widgets_edu, activity.getDragLayer(), false);
         v.show();
         return v;
     }
diff --git a/src/com/android/launcher3/widget/BaseWidgetSheet.java b/src/com/android/launcher3/widget/BaseWidgetSheet.java
index fc9c774..26e191d 100644
--- a/src/com/android/launcher3/widget/BaseWidgetSheet.java
+++ b/src/com/android/launcher3/widget/BaseWidgetSheet.java
@@ -21,7 +21,6 @@
 import android.content.Context;
 import android.graphics.Canvas;
 import android.graphics.Paint;
-import android.graphics.Point;
 import android.graphics.Rect;
 import android.util.AttributeSet;
 import android.view.View;
@@ -35,32 +34,28 @@
 import androidx.annotation.Px;
 import androidx.core.view.ViewCompat;
 
+import com.android.launcher3.BaseActivity;
 import com.android.launcher3.DeviceProfile;
 import com.android.launcher3.DeviceProfile.OnDeviceProfileChangeListener;
-import com.android.launcher3.DragSource;
-import com.android.launcher3.DropTarget.DragObject;
 import com.android.launcher3.Insettable;
 import com.android.launcher3.Launcher;
 import com.android.launcher3.LauncherPrefs;
 import com.android.launcher3.R;
 import com.android.launcher3.Utilities;
-import com.android.launcher3.dragndrop.DragOptions;
 import com.android.launcher3.popup.PopupDataProvider;
 import com.android.launcher3.testing.TestLogging;
 import com.android.launcher3.testing.shared.TestProtocol;
-import com.android.launcher3.touch.ItemLongClickListener;
 import com.android.launcher3.util.SystemUiController;
 import com.android.launcher3.util.Themes;
 import com.android.launcher3.util.window.WindowManagerProxy;
 import com.android.launcher3.views.AbstractSlideInView;
-import com.android.launcher3.views.ActivityContext;
 import com.android.launcher3.views.ArrowTipView;
 
 /**
  * Base class for various widgets popup
  */
-public abstract class BaseWidgetSheet extends AbstractSlideInView<Launcher>
-        implements OnClickListener, OnLongClickListener, DragSource,
+public abstract class BaseWidgetSheet extends AbstractSlideInView<BaseActivity>
+        implements OnClickListener, OnLongClickListener,
         PopupDataProvider.PopupDataChangeListener, Insettable, OnDeviceProfileChangeListener {
     /** The default number of cells that can fit horizontally in a widget sheet. */
     public static final int DEFAULT_MAX_HORIZONTAL_SPANS = 4;
@@ -129,21 +124,25 @@
         } else {
             mWidgetInstructionToast = showWidgetToast(getContext(), mWidgetInstructionToast);
         }
-
     }
 
     @Override
     public boolean onLongClick(View v) {
         TestLogging.recordEvent(TestProtocol.SEQUENCE_MAIN, "Widgets.onLongClick");
         v.cancelLongPress();
-        if (!ItemLongClickListener.canStartDrag(mActivityContext)) return false;
 
+        boolean result = false;
         if (v instanceof WidgetCell) {
-            return beginDraggingWidget((WidgetCell) v);
-        } else if (v.getParent() instanceof WidgetCell) {
-            return beginDraggingWidget((WidgetCell) v.getParent());
+            result = mActivityContext.getAllAppsItemLongClickListener().onLongClick(v);
+        } else if (v.getParent() instanceof WidgetCell wc) {
+            result = mActivityContext.getAllAppsItemLongClickListener().onLongClick(wc);
+        } else {
+            return true;
         }
-        return true;
+        if (result) {
+            close(true);
+        }
+        return result;
     }
 
     @Override
@@ -212,55 +211,12 @@
                 MeasureSpec.getSize(heightMeasureSpec));
     }
 
-    private boolean beginDraggingWidget(WidgetCell v) {
-        // Get the widget preview as the drag representation
-        WidgetImageView image = v.getWidgetView();
-
-        // If the ImageView doesn't have a drawable yet, the widget preview hasn't been loaded and
-        // we abort the drag.
-        if (image.getDrawable() == null && v.getAppWidgetHostViewPreview() == null) {
-            return false;
-        }
-
-        PendingItemDragHelper dragHelper = new PendingItemDragHelper(v);
-        // RemoteViews are being rendered in AppWidgetHostView in WidgetCell. And thus, the scale of
-        // RemoteViews is equivalent to the AppWidgetHostView scale.
-        dragHelper.setRemoteViewsPreview(v.getRemoteViewsPreview(), v.getAppWidgetHostViewScale());
-        dragHelper.setAppWidgetHostViewPreview(v.getAppWidgetHostViewPreview());
-
-        if (image.getDrawable() != null) {
-            int[] loc = new int[2];
-            getPopupContainer().getLocationInDragLayer(image, loc);
-
-            dragHelper.startDrag(image.getBitmapBounds(), image.getDrawable().getIntrinsicWidth(),
-                    image.getWidth(), new Point(loc[0], loc[1]), this, new DragOptions());
-        } else {
-            NavigableAppWidgetHostView preview = v.getAppWidgetHostViewPreview();
-            int[] loc = new int[2];
-            getPopupContainer().getLocationInDragLayer(preview, loc);
-            Rect r = new Rect();
-            preview.getWorkspaceVisualDragBounds(r);
-            dragHelper.startDrag(r, preview.getMeasuredWidth(), preview.getMeasuredWidth(),
-                    new Point(loc[0], loc[1]), this, new DragOptions());
-        }
-        close(true);
-        return true;
-    }
-
     @Override
     protected Interpolator getIdleInterpolator() {
         return mActivityContext.getDeviceProfile().isTablet
                 ? EMPHASIZED : super.getIdleInterpolator();
     }
 
-    //
-    // Drag related handling methods that implement {@link DragSource} interface.
-    //
-
-    @Override
-    public void onDropCompleted(View target, DragObject d, boolean success) { }
-
-
     protected void onCloseComplete() {
         super.onCloseComplete();
         clearNavBarColor();
@@ -344,7 +300,8 @@
     @Override
     protected void setTranslationShift(float translationShift) {
         super.setTranslationShift(translationShift);
-        Launcher launcher = ActivityContext.lookupContext(getContext());
-        launcher.onWidgetsTransition(1 - translationShift);
+        if (mActivityContext instanceof Launcher ls) {
+            ls.onWidgetsTransition(1 - translationShift);
+        }
     }
 }
diff --git a/src/com/android/launcher3/widget/picker/WidgetsFullSheet.java b/src/com/android/launcher3/widget/picker/WidgetsFullSheet.java
index af77d03..953ecda 100644
--- a/src/com/android/launcher3/widget/picker/WidgetsFullSheet.java
+++ b/src/com/android/launcher3/widget/picker/WidgetsFullSheet.java
@@ -55,8 +55,9 @@
 import androidx.recyclerview.widget.DefaultItemAnimator;
 import androidx.recyclerview.widget.RecyclerView;
 
+import com.android.launcher3.BaseActivity;
 import com.android.launcher3.DeviceProfile;
-import com.android.launcher3.Launcher;
+import com.android.launcher3.LauncherAppState;
 import com.android.launcher3.LauncherPrefs;
 import com.android.launcher3.R;
 import com.android.launcher3.Utilities;
@@ -72,7 +73,6 @@
 import com.android.launcher3.views.StickyHeaderLayout;
 import com.android.launcher3.views.WidgetsEduView;
 import com.android.launcher3.widget.BaseWidgetSheet;
-import com.android.launcher3.widget.LauncherWidgetHolder.ProviderChangedListener;
 import com.android.launcher3.widget.model.WidgetsListBaseEntry;
 import com.android.launcher3.widget.picker.search.SearchModeListener;
 import com.android.launcher3.widget.picker.search.WidgetsSearchBar;
@@ -89,7 +89,7 @@
  * Popup for showing the full list of available widgets
  */
 public class WidgetsFullSheet extends BaseWidgetSheet
-        implements ProviderChangedListener, OnActivePageChangedListener,
+        implements OnActivePageChangedListener,
         WidgetsRecyclerView.HeaderViewDimensionsProvider, SearchModeListener {
 
     private static final long FADE_IN_DURATION = 150;
@@ -166,7 +166,7 @@
     private boolean mIsInSearchMode;
     private boolean mIsNoWidgetsViewNeeded;
     @Px private int mMaxSpanPerRow;
-    private DeviceProfile mDeviceProfile;
+    private final DeviceProfile mDeviceProfile;
 
     private int mOrientation;
 
@@ -181,7 +181,7 @@
 
     public WidgetsFullSheet(Context context, AttributeSet attrs, int defStyleAttr) {
         super(context, attrs, defStyleAttr);
-        mDeviceProfile = Launcher.getLauncher(context).getDeviceProfile();
+        mDeviceProfile = mActivityContext.getDeviceProfile();
         mHasWorkProfile = context.getSystemService(LauncherApps.class).getProfiles().size() > 1;
         mOrientation = context.getResources().getConfiguration().orientation;
         mAdapters.put(AdapterHolder.PRIMARY, new AdapterHolder(AdapterHolder.PRIMARY));
@@ -353,15 +353,14 @@
     @Override
     protected void onAttachedToWindow() {
         super.onAttachedToWindow();
-        mActivityContext.getAppWidgetHolder().addProviderChangeListener(this);
-        notifyWidgetProvidersChanged();
+        LauncherAppState.getInstance(mActivityContext).getModel()
+                .refreshAndBindWidgetsAndShortcuts(null);
         onRecommendedWidgetsBound();
     }
 
     @Override
     protected void onDetachedFromWindow() {
         super.onDetachedFromWindow();
-        mActivityContext.getAppWidgetHolder().removeProviderChangeListener(this);
         mAdapters.get(AdapterHolder.PRIMARY).mWidgetsRecyclerView
                 .removeOnAttachStateChangeListener(mBindScrollbarInSearchMode);
         if (mHasWorkProfile) {
@@ -482,11 +481,6 @@
     }
 
     @Override
-    public void notifyWidgetProvidersChanged() {
-        mActivityContext.refreshAndBindWidgetsForPackageUser(null);
-    }
-
-    @Override
     public void onWidgetsBound() {
         if (mIsInSearchMode) {
             return;
@@ -682,22 +676,22 @@
     }
 
     /** Shows the {@link WidgetsFullSheet} on the launcher. */
-    public static WidgetsFullSheet show(Launcher launcher, boolean animate) {
-        boolean isTwoPane = launcher.getDeviceProfile().isTablet
-                && launcher.getDeviceProfile().isLandscape
-                && (!launcher.getDeviceProfile().isTwoPanels
+    public static WidgetsFullSheet show(BaseActivity activity, boolean animate) {
+        boolean isTwoPane = activity.getDeviceProfile().isTablet
+                && activity.getDeviceProfile().isLandscape
+                && (!activity.getDeviceProfile().isTwoPanels
                     || FeatureFlags.UNFOLDED_WIDGET_PICKER.get());
 
         WidgetsFullSheet sheet;
         if (isTwoPane) {
-            sheet = (WidgetsTwoPaneSheet) launcher.getLayoutInflater().inflate(
+            sheet = (WidgetsTwoPaneSheet) activity.getLayoutInflater().inflate(
                     R.layout.widgets_two_pane_sheet,
-                    launcher.getDragLayer(),
+                    activity.getDragLayer(),
                     false);
         } else {
-            sheet = (WidgetsFullSheet) launcher.getLayoutInflater().inflate(
+            sheet = (WidgetsFullSheet) activity.getLayoutInflater().inflate(
                     R.layout.widgets_full_sheet,
-                    launcher.getDragLayer(),
+                    activity.getDragLayer(),
                     false);
         }
 
@@ -754,7 +748,7 @@
 
     /** Gets the {@link WidgetsRecyclerView} which shows all widgets in {@link WidgetsFullSheet}. */
     @VisibleForTesting
-    public static WidgetsRecyclerView getWidgetsView(Launcher launcher) {
+    public static WidgetsRecyclerView getWidgetsView(BaseActivity launcher) {
         return launcher.findViewById(R.id.primary_widgets_list_view);
     }
 
@@ -803,7 +797,7 @@
             mOrientation = newConfig.orientation;
             if (mDeviceProfile.isTablet && !mDeviceProfile.isTwoPanels) {
                 handleClose(false);
-                show(Launcher.getLauncher(getContext()), false);
+                show(BaseActivity.fromContext(getContext()), false);
             } else {
                 reset();
             }
diff --git a/tests/src/com/android/launcher3/FakeInvariantDeviceProfileTest.kt b/tests/src/com/android/launcher3/FakeInvariantDeviceProfileTest.kt
index a421006..30b5663 100644
--- a/tests/src/com/android/launcher3/FakeInvariantDeviceProfileTest.kt
+++ b/tests/src/com/android/launcher3/FakeInvariantDeviceProfileTest.kt
@@ -121,8 +121,8 @@
                     listOf(PointF(16f, 16f), PointF(16f, 16f), PointF(16f, 16f), PointF(16f, 16f))
                         .toTypedArray()
 
-                numFolderRows = 3
-                numFolderColumns = 3
+                numFolderRows = intArrayOf(3, 3, 3, 3)
+                numFolderColumns = intArrayOf(3, 3, 3, 3)
                 folderStyle = R.style.FolderStyleDefault
 
                 inlineNavButtonsEndSpacing = R.dimen.taskbar_button_margin_split
@@ -204,8 +204,8 @@
                     listOf(PointF(16f, 64f), PointF(64f, 16f), PointF(16f, 64f), PointF(16f, 64f))
                         .toTypedArray()
 
-                numFolderRows = 3
-                numFolderColumns = 3
+                numFolderRows = intArrayOf(3, 3, 3, 3)
+                numFolderColumns = intArrayOf(3, 3, 3, 3)
                 folderStyle = R.style.FolderStyleDefault
 
                 inlineNavButtonsEndSpacing = R.dimen.taskbar_button_margin_6_5
@@ -288,8 +288,8 @@
                     listOf(PointF(16f, 16f), PointF(16f, 16f), PointF(16f, 20f), PointF(20f, 20f))
                         .toTypedArray()
 
-                numFolderRows = 3
-                numFolderColumns = 3
+                numFolderRows = intArrayOf(3, 3, 3, 3)
+                numFolderColumns = intArrayOf(3, 3, 3, 3)
                 folderStyle = R.style.FolderStyleDefault
 
                 inlineNavButtonsEndSpacing = R.dimen.taskbar_button_margin_split
diff --git a/tests/src/com/android/launcher3/celllayout/CellLayoutTestUtils.java b/tests/src/com/android/launcher3/celllayout/CellLayoutTestUtils.java
index 1fe02b2..d8ae74b 100644
--- a/tests/src/com/android/launcher3/celllayout/CellLayoutTestUtils.java
+++ b/tests/src/com/android/launcher3/celllayout/CellLayoutTestUtils.java
@@ -61,9 +61,7 @@
     }
 
     public static CellLayoutBoard viewsToBoard(List<View> views, int width, int height) {
-        CellLayoutBoard board = new CellLayoutBoard();
-        board.mWidth = width;
-        board.mHeight = height;
+        CellLayoutBoard board = new CellLayoutBoard(width, height);
 
         for (View callView : views) {
             CellLayoutLayoutParams params = (CellLayoutLayoutParams) callView.getLayoutParams();
diff --git a/tests/src/com/android/launcher3/celllayout/ReorderAlgorithmUnitTest.java b/tests/src/com/android/launcher3/celllayout/ReorderAlgorithmUnitTest.java
index 88f54a2..bd52bda 100644
--- a/tests/src/com/android/launcher3/celllayout/ReorderAlgorithmUnitTest.java
+++ b/tests/src/com/android/launcher3/celllayout/ReorderAlgorithmUnitTest.java
@@ -22,7 +22,7 @@
 
 import android.content.Context;
 import android.graphics.Point;
-import android.graphics.Rect;
+import android.util.Log;
 import android.view.View;
 
 import androidx.test.ext.junit.runners.AndroidJUnit4;
@@ -31,9 +31,13 @@
 import com.android.launcher3.CellLayout;
 import com.android.launcher3.DeviceProfile;
 import com.android.launcher3.InvariantDeviceProfile;
+import com.android.launcher3.MultipageCellLayout;
 import com.android.launcher3.celllayout.board.CellLayoutBoard;
 import com.android.launcher3.celllayout.board.IconPoint;
+import com.android.launcher3.celllayout.board.PermutedBoardComparator;
 import com.android.launcher3.celllayout.board.WidgetRect;
+import com.android.launcher3.celllayout.testgenerator.RandomBoardGenerator;
+import com.android.launcher3.celllayout.testgenerator.RandomMultiBoardGenerator;
 import com.android.launcher3.util.ActivityContextWrapper;
 import com.android.launcher3.views.DoubleShadowBubbleTextView;
 
@@ -53,10 +57,25 @@
 @SmallTest
 @RunWith(AndroidJUnit4.class)
 public class ReorderAlgorithmUnitTest {
+
+    private static final String TAG = "ReorderAlgorithmUnitTest";
+    private static final char MAIN_WIDGET_TYPE = 'z';
+
+    // There is nothing special about this numbers, the random seed is just to be able to reproduce
+    // the test cases and the height and width is a random number similar to what users expect on
+    // their devices
+    private static final int SEED = 897;
+    private static final int MAX_BOARD_SIZE = 13;
+
+    private static final int TOTAL_OF_CASES_GENERATED = 300;
     private Context mApplicationContext;
 
     private int mPrevNumColumns, mPrevNumRows;
 
+    /**
+     * This test reads existing test cases and makes sure the CellLayout produces the same
+     * output for each of them for a given input.
+     */
     @Test
     public void testAllCases() throws IOException {
         List<ReorderAlgorithmUnitTestCase> testCases = getTestCases(
@@ -65,7 +84,7 @@
         List<Integer> failingCases = new ArrayList<>();
         for (int i = 0; i < testCases.size(); i++) {
             try {
-                evaluateTestCase(testCases.get(i));
+                evaluateTestCase(testCases.get(i), false);
             } catch (AssertionError e) {
                 e.printStackTrace();
                 failingCases.add(i);
@@ -75,6 +94,47 @@
                 failingCases.size());
     }
 
+    /**
+     * This test generates random CellLayout configurations and then try to reorder it and makes
+     * sure the result is a valid board meaning it didn't remove any widget or icon.
+     */
+    @Test
+    public void generateValidTests() {
+        Random generator = new Random(SEED);
+        mApplicationContext = new ActivityContextWrapper(getApplicationContext());
+        for (int i = 0; i < TOTAL_OF_CASES_GENERATED; i++) {
+            // Using a new seed so that we can replicate the same test cases.
+            int seed = generator.nextInt();
+            Log.d(TAG, "Seed = " + seed);
+            ReorderAlgorithmUnitTestCase testCase = generateRandomTestCase(
+                    new RandomBoardGenerator(new Random(seed))
+            );
+            Log.d(TAG, "testCase = " + testCase);
+            assertTrue("invalid case " + i,
+                    validateIntegrity(testCase.startBoard, testCase.endBoard, testCase));
+        }
+    }
+
+    /**
+     * Same as above but testing the Multipage CellLayout.
+     */
+    @Test
+    public void generateValidTests_Multi() {
+        Random generator = new Random(SEED);
+        mApplicationContext = new ActivityContextWrapper(getApplicationContext());
+        for (int i = 0; i < TOTAL_OF_CASES_GENERATED; i++) {
+            // Using a new seed so that we can replicate the same test cases.
+            int seed = generator.nextInt();
+            Log.d(TAG, "Seed = " + seed);
+            ReorderAlgorithmUnitTestCase testCase = generateRandomTestCase(
+                    new RandomMultiBoardGenerator(new Random(seed))
+            );
+            Log.d(TAG, "testCase = " + testCase);
+            assertTrue("invalid case " + i,
+                    validateIntegrity(testCase.startBoard, testCase.endBoard, testCase));
+        }
+    }
+
     private void addViewInCellLayout(CellLayout cellLayout, int cellX, int cellY, int spanX,
             int spanY, boolean isWidget) {
         View cell = isWidget ? new View(mApplicationContext) : new DoubleShadowBubbleTextView(
@@ -84,15 +144,16 @@
                 (CellLayoutLayoutParams) cell.getLayoutParams(), true);
     }
 
-    public CellLayout createCellLayout(int width, int height) {
+    public CellLayout createCellLayout(int width, int height, boolean isMulti) {
         Context c = mApplicationContext;
         DeviceProfile dp = InvariantDeviceProfile.INSTANCE.get(c).getDeviceProfile(c).copy(c);
         // modify the device profile.
-        dp.inv.numColumns = width;
+        dp.inv.numColumns = isMulti ? width / 2 : width;
         dp.inv.numRows = height;
         dp.cellLayoutBorderSpacePx = new Point(0, 0);
 
-        CellLayout cl = new CellLayout(getWrappedContext(c, dp));
+        CellLayout cl = isMulti ? new MultipageCellLayout(getWrappedContext(c, dp))
+                : new CellLayout(getWrappedContext(c, dp));
         // I put a very large number for width and height so that all the items can fit, it doesn't
         // need to be exact, just bigger than the sum of cell border
         cl.measure(View.MeasureSpec.makeMeasureSpec(10000, View.MeasureSpec.EXACTLY),
@@ -109,8 +170,8 @@
     }
 
     public ItemConfiguration solve(CellLayoutBoard board, int x, int y, int spanX,
-            int spanY, int minSpanX, int minSpanY) {
-        CellLayout cl = createCellLayout(board.getWidth(), board.getHeight());
+            int spanY, int minSpanX, int minSpanY, boolean isMulti) {
+        CellLayout cl = createCellLayout(board.getWidth(), board.getHeight(), isMulti);
 
         // The views have to be sorted or the result can vary
         board.getIcons()
@@ -118,11 +179,15 @@
                 .map(IconPoint::getCoord)
                 .sorted(Comparator.comparing(p -> ((Point) p).x).thenComparing(p -> ((Point) p).y))
                 .forEach(p -> addViewInCellLayout(cl, p.x, p.y, 1, 1, false));
-        board.getWidgets().stream()
-                .sorted(Comparator.comparing(WidgetRect::getCellX)
-                        .thenComparing(WidgetRect::getCellY))
-                .forEach(widget -> addViewInCellLayout(cl, widget.getCellX(), widget.getCellY(),
-                        widget.getSpanX(), widget.getSpanY(), true));
+        board.getWidgets()
+                .stream()
+                .sorted(Comparator
+                        .comparing(WidgetRect::getCellX)
+                        .thenComparing(WidgetRect::getCellY)
+                ).forEach(
+                        widget -> addViewInCellLayout(cl, widget.getCellX(), widget.getCellY(),
+                                widget.getSpanX(), widget.getSpanY(), true)
+                );
 
         int[] testCaseXYinPixels = new int[2];
         cl.regionToCenterPoint(x, y, spanX, spanY, testCaseXYinPixels);
@@ -133,6 +198,15 @@
             solution = new ItemConfiguration();
             solution.isSolution = false;
         }
+        if (!solution.isSolution) {
+            cl.copyCurrentStateToSolution(solution, false);
+            if (cl instanceof MultipageCellLayout) {
+                solution =
+                        ((MultipageCellLayout) cl).createReorderAlgorithm().removeSeamFromSolution(
+                                solution);
+            }
+            solution.isSolution = false;
+        }
         return solution;
     }
 
@@ -143,17 +217,18 @@
                 new CellLayoutLayoutParams(val.cellX, val.cellY, val.spanX, val.spanY)));
         CellLayoutBoard board = CellLayoutTestUtils.viewsToBoard(
                 new ArrayList<>(solution.map.keySet()), width, height);
-        board.addWidget(solution.cellX, solution.cellY, solution.spanX, solution.spanY,
-                'z');
+        if (solution.isSolution) {
+            board.addWidget(solution.cellX, solution.cellY, solution.spanX, solution.spanY,
+                    MAIN_WIDGET_TYPE);
+        }
         return board;
     }
 
-    public void evaluateTestCase(ReorderAlgorithmUnitTestCase testCase) {
-        ItemConfiguration solution = solve(testCase.startBoard, testCase.x,
-                testCase.y, testCase.spanX, testCase.spanY, testCase.minSpanX,
-                testCase.minSpanY);
-        assertEquals("should be a valid solution", solution.isSolution,
-                testCase.isValidSolution);
+    public void evaluateTestCase(ReorderAlgorithmUnitTestCase testCase, boolean isMultiCellLayout) {
+        ItemConfiguration solution = solve(testCase.startBoard, testCase.x, testCase.y,
+                testCase.spanX, testCase.spanY, testCase.minSpanX, testCase.minSpanY,
+                isMultiCellLayout);
+        assertEquals("should be a valid solution", solution.isSolution, testCase.isValidSolution);
         if (testCase.isValidSolution) {
             CellLayoutBoard finishBoard = boardFromSolution(solution,
                     testCase.startBoard.getWidth(), testCase.startBoard.getHeight());
@@ -178,36 +253,35 @@
         dp.inv.numRows = mPrevNumRows;
     }
 
-    @SuppressWarnings("UnusedMethod")
-    /**
-     * Utility function used to generate all the test cases
-     */
-    private ReorderAlgorithmUnitTestCase generateRandomTestCase() {
+    private ReorderAlgorithmUnitTestCase generateRandomTestCase(
+            RandomBoardGenerator boardGenerator) {
         ReorderAlgorithmUnitTestCase testCase = new ReorderAlgorithmUnitTestCase();
 
-        int width = getRandom(3, 8);
-        int height = getRandom(3, 8);
+        boolean isMultiCellLayout = boardGenerator instanceof RandomMultiBoardGenerator;
 
-        int targetWidth = getRandom(1, width - 2);
-        int targetHeight = getRandom(1, height - 2);
+        int width = isMultiCellLayout
+                ? boardGenerator.getRandom(3, MAX_BOARD_SIZE / 2) * 2
+                : boardGenerator.getRandom(3, MAX_BOARD_SIZE);
+        int height = boardGenerator.getRandom(3, MAX_BOARD_SIZE);
 
-        int minTargetWidth = getRandom(1, targetWidth);
-        int minTargetHeight = getRandom(1, targetHeight);
+        int targetWidth = boardGenerator.getRandom(1, width - 2);
+        int targetHeight = boardGenerator.getRandom(1, height - 2);
 
-        int x = getRandom(0, width - targetWidth);
-        int y = getRandom(0, height - targetHeight);
+        int minTargetWidth = boardGenerator.getRandom(1, targetWidth);
+        int minTargetHeight = boardGenerator.getRandom(1, targetHeight);
 
-        CellLayoutBoard board = generateBoard(new CellLayoutBoard(width, height),
-                new Rect(0, 0, width, height), targetWidth * targetHeight);
+        int x = boardGenerator.getRandom(0, width - targetWidth);
+        int y = boardGenerator.getRandom(0, height - targetHeight);
+
+        CellLayoutBoard board = boardGenerator.generateBoard(width, height,
+                targetWidth * targetHeight);
 
         ItemConfiguration solution = solve(board, x, y, targetWidth, targetHeight,
-                minTargetWidth, minTargetHeight);
+                minTargetWidth, minTargetHeight, isMultiCellLayout);
 
-        CellLayoutBoard finishBoard = solution.isSolution ? boardFromSolution(solution,
-                board.getWidth(), board.getHeight()) : new CellLayoutBoard(board.getWidth(),
+        CellLayoutBoard finishBoard = boardFromSolution(solution, board.getWidth(),
                 board.getHeight());
 
-
         testCase.startBoard = board;
         testCase.endBoard = finishBoard;
         testCase.isValidSolution = solution.isSolution;
@@ -222,39 +296,24 @@
         return testCase;
     }
 
-    private int getRandom(int start, int end) {
-        int random = end == 0 ? 0 : new Random().nextInt(end);
-        return start + random;
-    }
-
-    private CellLayoutBoard generateBoard(CellLayoutBoard board, Rect area,
-            int emptySpaces) {
-        if (area.height() * area.width() <= 0) return board;
-
-        int width = getRandom(1, area.width() - 1);
-        int height = getRandom(1, area.height() - 1);
-
-        int x = area.left + getRandom(0, area.width() - width);
-        int y = area.top + getRandom(0, area.height() - height);
-
-        if (emptySpaces > 0) {
-            emptySpaces -= width * height;
-        } else if (width * height > 1) {
-            board.addWidget(x, y, width, height);
-        } else {
-            board.addIcon(x, y);
+    /**
+     * Makes sure the final solution has valid integrity meaning that the number and sizes of
+     * widgets is the expect and there are no missing widgets.
+     */
+    public boolean validateIntegrity(CellLayoutBoard startBoard, CellLayoutBoard finishBoard,
+            ReorderAlgorithmUnitTestCase testCase) {
+        if (!testCase.isValidSolution) {
+            // if we couldn't place the widget then the solution should be identical to the board
+            return startBoard.compareTo(finishBoard) == 0;
         }
-
-        generateBoard(board,
-                new Rect(area.left, area.top, area.right, y), emptySpaces);
-        generateBoard(board,
-                new Rect(area.left, y, x, area.bottom), emptySpaces);
-        generateBoard(board,
-                new Rect(x, y + height, area.right, area.bottom), emptySpaces);
-        generateBoard(board,
-                new Rect(x + width, y, area.right, y + height), emptySpaces);
-
-        return board;
+        WidgetRect addedWidget = finishBoard.getWidgetOfType(MAIN_WIDGET_TYPE);
+        finishBoard.removeItem(MAIN_WIDGET_TYPE);
+        Comparator<CellLayoutBoard> comparator = new PermutedBoardComparator();
+        if (comparator.compare(startBoard, finishBoard) != 0) {
+            return false;
+        }
+        return addedWidget.getSpanX() >= testCase.minSpanX
+                && addedWidget.getSpanY() >= testCase.minSpanY;
     }
 
     private static List<ReorderAlgorithmUnitTestCase> getTestCases(String testPath)
diff --git a/tests/src/com/android/launcher3/celllayout/board/CellLayoutBoard.java b/tests/src/com/android/launcher3/celllayout/board/CellLayoutBoard.java
index e90e145..dbbdcf5 100644
--- a/tests/src/com/android/launcher3/celllayout/board/CellLayoutBoard.java
+++ b/tests/src/com/android/launcher3/celllayout/board/CellLayoutBoard.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2023 The Android Open Source Project
+ * Copyright (C) 2022 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -18,8 +18,11 @@
 import android.graphics.Point;
 import android.graphics.Rect;
 
+import androidx.annotation.NonNull;
+
 import java.util.ArrayDeque;
 import java.util.ArrayList;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.List;
@@ -31,73 +34,13 @@
 
 public class CellLayoutBoard implements Comparable<CellLayoutBoard> {
 
-    private boolean intersects(Rect r1, Rect r2) {
-        // If one rectangle is on left side of other
-        if (r1.left > r2.right || r2.left > r1.right) {
-            return false;
-        }
-
-        // If one rectangle is above other
-        if (r1.bottom > r2.top || r2.bottom > r1.top) {
-            return false;
-        }
-
-        return true;
-    }
-
-    private boolean overlapsWithIgnored(Set<Rect> ignoredRectangles, Rect rect) {
-        for (Rect ignoredRect : ignoredRectangles) {
-            // Using the built in intersects doesn't work because it doesn't account for area 0
-            if (intersects(ignoredRect, rect)) {
-                return true;
-            }
-        }
-        return false;
-    }
+    public static final Comparator<CellLayoutBoard> COMPARATOR = new IdenticalBoardComparator();
 
     @Override
-    public int compareTo(CellLayoutBoard cellLayoutBoard) {
-        // to be equal they need to have the same number of widgets and the same dimensions
-        // their order can be different
-        Set<Rect> widgetsSet = new HashSet<>();
-        Set<Rect> ignoredRectangles = new HashSet<>();
-        for (WidgetRect rect : mWidgetsRects) {
-            if (rect.shouldIgnore()) {
-                ignoredRectangles.add(rect.mBounds);
-            } else {
-                widgetsSet.add(rect.mBounds);
-            }
-        }
-        for (WidgetRect rect : cellLayoutBoard.mWidgetsRects) {
-            // ignore rectangles overlapping with the area marked by x
-            if (overlapsWithIgnored(ignoredRectangles, rect.mBounds)) {
-                continue;
-            }
-            if (!widgetsSet.contains(rect.mBounds)) {
-                return -1;
-            }
-            widgetsSet.remove(rect.mBounds);
-        }
-        if (!widgetsSet.isEmpty()) {
-            return 1;
-        }
-
-        // to be equal they need to have the same number of icons their order can be different
-        Set<Point> iconsSet = new HashSet<>();
-        mIconPoints.forEach(icon -> iconsSet.add(icon.getCoord()));
-        for (IconPoint icon : cellLayoutBoard.mIconPoints) {
-            if (!iconsSet.contains(icon.getCoord())) {
-                return -1;
-            }
-            iconsSet.remove(icon.getCoord());
-        }
-        if (!iconsSet.isEmpty()) {
-            return 1;
-        }
-        return 0;
+    public int compareTo(@NonNull CellLayoutBoard cellLayoutBoard) {
+        return COMPARATOR.compare(this, cellLayoutBoard);
     }
 
-
     private HashSet<Character> mUsedWidgetTypes = new HashSet<>();
 
     static final int INFINITE = 99999;
@@ -112,7 +55,7 @@
 
     WidgetRect mMain = null;
 
-    public int mWidth, mHeight;
+    int mWidth, mHeight;
 
     public CellLayoutBoard() {
         for (int x = 0; x < mWidget.length; x++) {
@@ -123,7 +66,7 @@
     }
 
     public CellLayoutBoard(int width, int height) {
-        mWidget = new char[width][height];
+        mWidget = new char[width + 1][height + 1];
         this.mWidth = width;
         this.mHeight = height;
         for (int x = 0; x < mWidget.length; x++) {
@@ -139,6 +82,15 @@
         return isXInRect && isYInRect;
     }
 
+    public WidgetRect getWidgetAt(Point p) {
+        return getWidgetAt(p.x, p.y);
+    }
+
+    public WidgetRect getWidgetOfType(char type) {
+        return mWidgetsRects.stream()
+                .filter(widgetRect -> widgetRect.mType == type).findFirst().orElse(null);
+    }
+
     public WidgetRect getWidgetAt(int x, int y) {
         return mWidgetsRects.stream()
                 .filter(widgetRect -> pointInsideRect(x, y, widgetRect)).findFirst().orElse(null);
@@ -165,8 +117,8 @@
     }
 
     private void removeWidgetFromBoard(WidgetRect widget) {
-        for (int xi = widget.mBounds.left; xi < widget.mBounds.right; xi++) {
-            for (int yi = widget.mBounds.top; yi < widget.mBounds.bottom; yi++) {
+        for (int xi = widget.mBounds.left; xi <= widget.mBounds.right; xi++) {
+            for (int yi = widget.mBounds.bottom; yi <= widget.mBounds.top; yi++) {
                 mWidget[xi][yi] = '-';
             }
         }
@@ -207,7 +159,7 @@
     private void removeOverlappingItems(Point p) {
         // Remove overlapping widgets and remove them from the board
         mWidgetsRects = mWidgetsRects.stream().filter(widget -> {
-            if (widget.mBounds.contains(p.x, p.y)) {
+            if (IdenticalBoardComparator.Companion.touchesPoint(widget.mBounds, p)) {
                 removeWidgetFromBoard(widget);
                 return false;
             }
@@ -237,8 +189,9 @@
     }
 
     private char getNextWidgetType() {
-        for (char type = 'a'; type <= 'z'; type++) {
-            if (type == 'i') continue;
+        for (char type = 'a'; type < 'z'; type++) {
+            if (type == CellType.ICON) continue;
+            if (type == CellType.IGNORE) continue;
             if (mUsedWidgetTypes.contains(type)) continue;
             mUsedWidgetTypes.add(type);
             return type;
@@ -258,6 +211,17 @@
         }
     }
 
+    public void removeItem(char type) {
+        mWidgetsRects.stream()
+                .filter(widgetRect -> widgetRect.mType == type)
+                .forEach(widgetRect -> removeOverlappingItems(
+                        new Point(widgetRect.getCellX(), widgetRect.getCellY())));
+    }
+
+    public void removeItem(Point p) {
+        removeOverlappingItems(p);
+    }
+
     public void addWidget(int x, int y, int spanX, int spanY) {
         addWidget(x, y, spanX, spanY, getNextWidgetType());
     }
@@ -407,8 +371,8 @@
         s.append("\n");
         maxX = Math.min(maxX, mWidget.length);
         maxY = Math.min(maxY, mWidget[0].length);
-        for (int y = 0; y < maxY; y++) {
-            for (int x = 0; x < maxX; x++) {
+        for (int y = 0; y <= maxY; y++) {
+            for (int x = 0; x <= maxX; x++) {
                 s.append(mWidget[x][y]);
             }
             s.append('\n');
diff --git a/tests/src/com/android/launcher3/celllayout/board/IdenticalBoardComparator.kt b/tests/src/com/android/launcher3/celllayout/board/IdenticalBoardComparator.kt
new file mode 100644
index 0000000..a4a420c
--- /dev/null
+++ b/tests/src/com/android/launcher3/celllayout/board/IdenticalBoardComparator.kt
@@ -0,0 +1,101 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.android.launcher3.celllayout.board
+
+import android.graphics.Point
+import android.graphics.Rect
+
+/**
+ * Compares two [CellLayoutBoard] and returns 0 if they are identical, meaning they have the same
+ * widget and icons in the same place, they can be different letters tough.
+ */
+class IdenticalBoardComparator : Comparator<CellLayoutBoard> {
+
+    /** Converts a list of WidgetRect into a map of the count of different widget.bounds */
+    private fun widgetsToBoundsMap(widgets: List<WidgetRect>) =
+        widgets.groupingBy { it.mBounds }.eachCount()
+
+    /** Converts a list of IconPoint into a map of the count of different icon.coord */
+    private fun iconsToPosCountMap(widgets: List<IconPoint>) =
+        widgets.groupingBy { it.getCoord() }.eachCount()
+
+    override fun compare(
+        cellLayoutBoard: CellLayoutBoard,
+        otherCellLayoutBoard: CellLayoutBoard
+    ): Int {
+        // to be equal they need to have the same number of widgets and the same dimensions
+        // their order can be different
+        val widgetsMap: Map<Rect, Int> =
+            widgetsToBoundsMap(cellLayoutBoard.widgets.filter { !it.shouldIgnore() })
+        val ignoredRectangles: Map<Rect, Int> =
+            widgetsToBoundsMap(cellLayoutBoard.widgets.filter { it.shouldIgnore() })
+
+        val otherWidgetMap: Map<Rect, Int> =
+            widgetsToBoundsMap(
+                otherCellLayoutBoard.widgets
+                    .filter { !it.shouldIgnore() }
+                    .filter { !overlapsWithIgnored(ignoredRectangles, it.mBounds) }
+            )
+
+        if (widgetsMap != otherWidgetMap) {
+            return -1
+        }
+
+        // to be equal they need to have the same number of icons their order can be different
+        return if (
+            iconsToPosCountMap(cellLayoutBoard.icons) ==
+                iconsToPosCountMap(otherCellLayoutBoard.icons)
+        ) {
+            0
+        } else {
+            1
+        }
+    }
+
+    private fun overlapsWithIgnored(ignoredRectangles: Map<Rect, Int>, rect: Rect): Boolean {
+        for (ignoredRect in ignoredRectangles.keys) {
+            // Using the built in intersects doesn't work because it doesn't account for area 0
+            if (touches(ignoredRect, rect)) {
+                return true
+            }
+        }
+        return false
+    }
+
+    companion object {
+        /**
+         * Similar function to {@link Rect#intersects} but this one returns true if the rectangles
+         * are intersecting or touching whereas {@link Rect#intersects} doesn't return true when
+         * they are touching.
+         */
+        fun touches(r1: Rect, r2: Rect): Boolean {
+            // If one rectangle is on left side of other
+            return if (r1.left > r2.right || r2.left > r1.right) {
+                false
+            } else r1.bottom <= r2.top && r2.bottom <= r1.top
+
+            // If one rectangle is above other
+        }
+
+        /**
+         * Similar function to {@link Rect#contains} but this one returns true if {link @Point} is
+         * intersecting or touching the {@link Rect}. Similar to {@link touches}.
+         */
+        fun touchesPoint(r1: Rect, p: Point): Boolean {
+            return r1.left <= p.x && p.x <= r1.right && r1.bottom <= p.y && p.y <= r1.top
+        }
+    }
+}
diff --git a/tests/src/com/android/launcher3/celllayout/board/PermutedBoardComparator.kt b/tests/src/com/android/launcher3/celllayout/board/PermutedBoardComparator.kt
new file mode 100644
index 0000000..c3d13a5
--- /dev/null
+++ b/tests/src/com/android/launcher3/celllayout/board/PermutedBoardComparator.kt
@@ -0,0 +1,43 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.android.launcher3.celllayout.board
+
+import android.graphics.Point
+
+/**
+ * Compares two [CellLayoutBoard] and returns 0 if they contain the same widgets and icons even if
+ * they are in different positions i.e. in a different permutation.
+ */
+class PermutedBoardComparator : Comparator<CellLayoutBoard> {
+
+    /**
+     * The key for the set is the span since the widgets could change location but shouldn't change
+     * size
+     */
+    private fun boardToSpanCountMap(widgets: List<WidgetRect>) =
+        widgets.groupingBy { Point(it.spanX, it.spanY) }.eachCount()
+    override fun compare(
+        cellLayoutBoard: CellLayoutBoard,
+        otherCellLayoutBoard: CellLayoutBoard
+    ): Int {
+        return if (
+            boardToSpanCountMap(cellLayoutBoard.widgets) !=
+                boardToSpanCountMap(otherCellLayoutBoard.widgets)
+        ) {
+            1
+        } else cellLayoutBoard.icons.size.compareTo(otherCellLayoutBoard.icons.size)
+    }
+}
diff --git a/tests/src/com/android/launcher3/celllayout/testgenerator/DeterministicRandomGenerator.kt b/tests/src/com/android/launcher3/celllayout/testgenerator/DeterministicRandomGenerator.kt
new file mode 100644
index 0000000..e582973
--- /dev/null
+++ b/tests/src/com/android/launcher3/celllayout/testgenerator/DeterministicRandomGenerator.kt
@@ -0,0 +1,22 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.android.launcher3.celllayout.testgenerator
+
+import java.util.Random
+
+abstract class DeterministicRandomGenerator(private val generator: Random) {
+    fun getRandom(start: Int, end: Int): Int = start + (if (end == 0) 0 else generator.nextInt(end))
+}
diff --git a/tests/src/com/android/launcher3/celllayout/testgenerator/RandomBoardGenerator.kt b/tests/src/com/android/launcher3/celllayout/testgenerator/RandomBoardGenerator.kt
new file mode 100644
index 0000000..770024f
--- /dev/null
+++ b/tests/src/com/android/launcher3/celllayout/testgenerator/RandomBoardGenerator.kt
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.android.launcher3.celllayout.testgenerator
+
+import android.graphics.Rect
+import com.android.launcher3.celllayout.board.CellLayoutBoard
+import java.util.Random
+
+/** Generates a random CellLayoutBoard. */
+open class RandomBoardGenerator(generator: Random) : DeterministicRandomGenerator(generator) {
+    /**
+     * @param remainingEmptySpaces the maximum number of spaces we will fill with icons and widgets
+     *   meaning that if the number is 100 we will try to fill the board with at most 100 spaces
+     *   usually less than 100.
+     * @return a randomly generated board filled with icons and widgets.
+     */
+    open fun generateBoard(width: Int, height: Int, remainingEmptySpaces: Int): CellLayoutBoard? {
+        val cellLayoutBoard = CellLayoutBoard(width, height)
+        return fillBoard(cellLayoutBoard, Rect(0, 0, width, height), remainingEmptySpaces)
+    }
+
+    protected fun fillBoard(
+        board: CellLayoutBoard,
+        area: Rect,
+        remainingEmptySpacesArg: Int
+    ): CellLayoutBoard {
+        var remainingEmptySpaces = remainingEmptySpacesArg
+        if (area.height() * area.width() <= 0) return board
+        val width = getRandom(1, area.width() - 1)
+        val height = getRandom(1, area.height() - 1)
+        val x = area.left + getRandom(0, area.width() - width)
+        val y = area.top + getRandom(0, area.height() - height)
+        if (remainingEmptySpaces > 0) {
+            remainingEmptySpaces -= width * height
+        } else if (board.widgets.size <= 22 && width * height > 1) {
+            board.addWidget(x, y, width, height)
+        } else {
+            board.addIcon(x, y)
+        }
+        fillBoard(board, Rect(area.left, area.top, area.right, y), remainingEmptySpaces)
+        fillBoard(board, Rect(area.left, y, x, area.bottom), remainingEmptySpaces)
+        fillBoard(board, Rect(x, y + height, area.right, area.bottom), remainingEmptySpaces)
+        fillBoard(board, Rect(x + width, y, area.right, y + height), remainingEmptySpaces)
+        return board
+    }
+}
diff --git a/tests/src/com/android/launcher3/celllayout/testgenerator/RandomMultiBoardGenerator.kt b/tests/src/com/android/launcher3/celllayout/testgenerator/RandomMultiBoardGenerator.kt
new file mode 100644
index 0000000..da4de7d
--- /dev/null
+++ b/tests/src/com/android/launcher3/celllayout/testgenerator/RandomMultiBoardGenerator.kt
@@ -0,0 +1,36 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.android.launcher3.celllayout.testgenerator
+
+import android.graphics.Rect
+import com.android.launcher3.celllayout.board.CellLayoutBoard
+import java.util.Random
+
+class RandomMultiBoardGenerator(generator: Random) : RandomBoardGenerator(generator) {
+    override fun generateBoard(
+        width: Int,
+        height: Int,
+        remainingEmptySpaces: Int
+    ): CellLayoutBoard {
+        val cellLayoutBoard = CellLayoutBoard(width, height)
+        fillBoard(cellLayoutBoard, Rect(0, 0, width / 2, height), remainingEmptySpaces / 2)
+        return fillBoard(
+            cellLayoutBoard,
+            Rect(width / 2, 0, width, height),
+            remainingEmptySpaces / 2
+        )
+    }
+}