Homescreen migration from a larger grid to a smaller grid.
Adding support for restoring from a larger device, if the grid size
difference is not more that 1.
During restore add all the items in the DB, and run a one-time migration
the next time launcher starts.
The migration strategy is defined in ShrinkWorkspaceTask.java which involves
resizing, moving and removing some items.
Change-Id: I6ee411f6db5bf0152b527e16146a88c56dec2d97
diff --git a/src/com/android/launcher3/LauncherAppState.java b/src/com/android/launcher3/LauncherAppState.java
index 0b7b1fd..ecaf801 100644
--- a/src/com/android/launcher3/LauncherAppState.java
+++ b/src/com/android/launcher3/LauncherAppState.java
@@ -17,7 +17,6 @@
package com.android.launcher3;
import android.app.SearchManager;
-import android.content.ComponentName;
import android.content.Context;
import android.content.Intent;
import android.content.IntentFilter;
@@ -147,7 +146,7 @@
sLauncherProvider = new WeakReference<LauncherProvider>(provider);
}
- static LauncherProvider getLauncherProvider() {
+ public static LauncherProvider getLauncherProvider() {
return sLauncherProvider.get();
}
diff --git a/src/com/android/launcher3/LauncherAppWidgetProviderInfo.java b/src/com/android/launcher3/LauncherAppWidgetProviderInfo.java
index 85af92f..9ba7853 100644
--- a/src/com/android/launcher3/LauncherAppWidgetProviderInfo.java
+++ b/src/com/android/launcher3/LauncherAppWidgetProviderInfo.java
@@ -5,6 +5,7 @@
import android.content.ComponentName;
import android.content.Context;
import android.content.pm.PackageManager;
+import android.graphics.Point;
import android.graphics.drawable.Drawable;
import android.os.Build;
import android.os.Parcel;
@@ -110,4 +111,15 @@
mMinSpanY = minResizeSpan[1];
}
}
+
+ public Point getMinSpans(InvariantDeviceProfile idp, Context context) {
+ // Calculate the spans corresponding to any one of the orientations as it should not change
+ // based on orientation.
+ // TODO: Use the max of both profiles
+ int[] minSpans = CellLayout.rectToCell(
+ idp.portraitProfile, context, minResizeWidth, minResizeHeight, null);
+ return new Point(
+ (resizeMode & RESIZE_HORIZONTAL) != 0 ? minSpans[0] : -1,
+ (resizeMode & RESIZE_VERTICAL) != 0 ? minSpans[1] : -1);
+ }
}
diff --git a/src/com/android/launcher3/LauncherBackupAgentHelper.java b/src/com/android/launcher3/LauncherBackupAgentHelper.java
index b7860d4..611ab2e 100644
--- a/src/com/android/launcher3/LauncherBackupAgentHelper.java
+++ b/src/com/android/launcher3/LauncherBackupAgentHelper.java
@@ -24,6 +24,8 @@
import android.os.ParcelFileDescriptor;
import android.util.Log;
+import com.android.launcher3.model.MigrateFromRestoreTask;
+
import java.io.IOException;
public class LauncherBackupAgentHelper extends BackupAgentHelper {
@@ -96,6 +98,13 @@
LauncherAppState.getLauncherProvider().updateFolderItemsRank();
}
+ if (mHelper.shouldAttemptWorkspaceMigration()) {
+ MigrateFromRestoreTask.markForMigration(getApplicationContext(),
+ (int) mHelper.migrationCompatibleProfileData.desktopCols,
+ (int) mHelper.migrationCompatibleProfileData.desktopRows,
+ mHelper.widgetSizes);
+ }
+
LauncherAppState.getLauncherProvider().convertShortcutsToLauncherActivities();
} else {
if (VERBOSE) Log.v(TAG, "Nothing was restored, clearing DB");
diff --git a/src/com/android/launcher3/LauncherBackupHelper.java b/src/com/android/launcher3/LauncherBackupHelper.java
index 39603ad..136556b 100644
--- a/src/com/android/launcher3/LauncherBackupHelper.java
+++ b/src/com/android/launcher3/LauncherBackupHelper.java
@@ -32,6 +32,7 @@
import android.database.Cursor;
import android.graphics.Bitmap;
import android.graphics.BitmapFactory;
+import android.graphics.Point;
import android.graphics.drawable.Drawable;
import android.os.ParcelFileDescriptor;
import android.text.TextUtils;
@@ -152,6 +153,9 @@
private DeviceProfieData mDeviceProfileData;
private InvariantDeviceProfile mIdp;
+ DeviceProfieData migrationCompatibleProfileData;
+ HashSet<String> widgetSizes = new HashSet<>();
+
boolean restoreSuccessful;
int restoredBackupVersion = 1;
@@ -288,9 +292,9 @@
return true;
}
- boolean isHotsetCompatible = false;
+ boolean isHotseatCompatible = false;
if (currentProfile.allappsRank >= oldProfile.hotseatCount) {
- isHotsetCompatible = true;
+ isHotseatCompatible = true;
mHotseatShift = 0;
}
@@ -298,12 +302,28 @@
&& ((currentProfile.hotseatCount - currentProfile.allappsRank) >=
(oldProfile.hotseatCount - oldProfile.allappsRank))) {
// There is enough space on both sides of the hotseat.
- isHotsetCompatible = true;
+ isHotseatCompatible = true;
mHotseatShift = currentProfile.allappsRank - oldProfile.allappsRank;
}
- return isHotsetCompatible && (currentProfile.desktopCols >= oldProfile.desktopCols)
- && (currentProfile.desktopRows >= oldProfile.desktopRows);
+ if (!isHotseatCompatible) {
+ return false;
+ }
+ if ((currentProfile.desktopCols >= oldProfile.desktopCols)
+ && (currentProfile.desktopRows >= oldProfile.desktopRows)) {
+ return true;
+ }
+
+ if ((oldProfile.desktopCols - currentProfile.desktopCols <= 1) &&
+ (oldProfile.desktopRows - currentProfile.desktopRows <= 1)) {
+ // Allow desktop migration when row and/or column count contracts by 1.
+
+ migrationCompatibleProfileData = initDeviceProfileData(mIdp);
+ migrationCompatibleProfileData.desktopCols = oldProfile.desktopCols;
+ migrationCompatibleProfileData.desktopRows = oldProfile.desktopRows;
+ return true;
+ }
+ return false;
}
/**
@@ -706,7 +726,8 @@
}
}
- // future site of widget table mutation
+ // Cache widget min sizes incase migration is required.
+ widgetSizes.add(widget.provider + "#" + widget.minSpanX + "," + widget.minSpanY);
}
/** create a new key, with an integer ID.
@@ -904,7 +925,11 @@
UserManagerCompat.getInstance(mContext).getSerialNumberForUser(myUserHandle);
values.put(LauncherSettings.Favorites.PROFILE_ID, userSerialNumber);
- DeviceProfieData currentProfile = mDeviceProfileData;
+ // If we will attempt grid resize, use the original profile to validate grid size, as
+ // anything which fits in the original grid should fit in the current grid after
+ // grid migration.
+ DeviceProfieData currentProfile = migrationCompatibleProfileData == null
+ ? mDeviceProfileData : migrationCompatibleProfileData;
if (favorite.itemType == Favorites.ITEM_TYPE_APPWIDGET) {
if (!TextUtils.isEmpty(favorite.appWidgetProvider)) {
@@ -996,14 +1021,9 @@
widget.icon.dpi = dpi;
}
- // Calculate the spans corresponding to any one of the orientations as it should not change
- // based on orientation.
- int[] minSpans = CellLayout.rectToCell(
- mIdp.portraitProfile, mContext, info.minResizeWidth, info.minResizeHeight, null);
- widget.minSpanX = (info.resizeMode & LauncherAppWidgetProviderInfo.RESIZE_HORIZONTAL) != 0
- ? minSpans[0] : -1;
- widget.minSpanY = (info.resizeMode & LauncherAppWidgetProviderInfo.RESIZE_VERTICAL) != 0
- ? minSpans[1] : -1;
+ Point spans = info.getMinSpans(mIdp, mContext);
+ widget.minSpanX = spans.x;
+ widget.minSpanY = spans.y;
return widget;
}
@@ -1188,6 +1208,10 @@
}
}
+ public boolean shouldAttemptWorkspaceMigration() {
+ return migrationCompatibleProfileData != null;
+ }
+
/**
* A class to check if an activity can handle one of the intents from a list of
* predefined intents.
diff --git a/src/com/android/launcher3/LauncherModel.java b/src/com/android/launcher3/LauncherModel.java
index 0b67310..7e75f97 100644
--- a/src/com/android/launcher3/LauncherModel.java
+++ b/src/com/android/launcher3/LauncherModel.java
@@ -27,6 +27,7 @@
import android.content.Intent;
import android.content.Intent.ShortcutIconResource;
import android.content.IntentFilter;
+import android.content.SharedPreferences;
import android.content.pm.PackageManager;
import android.content.pm.ProviderInfo;
import android.content.pm.ResolveInfo;
@@ -55,6 +56,7 @@
import com.android.launcher3.compat.PackageInstallerCompat.PackageInstallInfo;
import com.android.launcher3.compat.UserHandleCompat;
import com.android.launcher3.compat.UserManagerCompat;
+import com.android.launcher3.model.MigrateFromRestoreTask;
import com.android.launcher3.model.WidgetsModel;
import com.android.launcher3.util.ComponentKey;
import com.android.launcher3.util.CursorIconInfo;
@@ -1133,7 +1135,7 @@
* Update the order of the workspace screens in the database. The array list contains
* a list of screen ids in the order that they should appear.
*/
- void updateWorkspaceScreenOrder(Context context, final ArrayList<Long> screens) {
+ public void updateWorkspaceScreenOrder(Context context, final ArrayList<Long> screens) {
final ArrayList<Long> screensCopy = new ArrayList<Long>(screens);
final ContentResolver cr = context.getContentResolver();
final Uri uri = LauncherSettings.WorkspaceScreens.CONTENT_URI;
@@ -1411,7 +1413,7 @@
/**
* Loads the workspace screen ids in an ordered list.
*/
- @Thunk static ArrayList<Long> loadWorkspaceScreensDb(Context context) {
+ public static ArrayList<Long> loadWorkspaceScreensDb(Context context) {
final ContentResolver contentResolver = context.getContentResolver();
final Uri screensUri = LauncherSettings.WorkspaceScreens.CONTENT_URI;
@@ -1757,6 +1759,22 @@
int countX = (int) profile.numColumns;
int countY = (int) profile.numRows;
+
+ if (MigrateFromRestoreTask.shouldRunTask(mContext)) {
+ try {
+ MigrateFromRestoreTask task = new MigrateFromRestoreTask(mContext);
+ // Clear the flags before starting the task, so that we do not run the task
+ // again, in case there was an uncaught error.
+ MigrateFromRestoreTask.clearFlags(mContext);
+ task.execute();
+ } catch (Exception e) {
+ Log.e(TAG, "Error during grid migration", e);
+
+ // Clear workspace.
+ mFlags = mFlags | LOADER_FLAG_CLEAR_WORKSPACE;
+ }
+ }
+
if ((mFlags & LOADER_FLAG_CLEAR_WORKSPACE) != 0) {
Launcher.addDumpLog(TAG, "loadWorkspace: resetting launcher database", true);
LauncherAppState.getLauncherProvider().deleteDatabase();
diff --git a/src/com/android/launcher3/LauncherProvider.java b/src/com/android/launcher3/LauncherProvider.java
index cc5e18b..6cbb267 100644
--- a/src/com/android/launcher3/LauncherProvider.java
+++ b/src/com/android/launcher3/LauncherProvider.java
@@ -71,7 +71,7 @@
private static final int DATABASE_VERSION = 26;
static final String OLD_AUTHORITY = "com.android.launcher2.settings";
- static final String AUTHORITY = ProviderConfig.AUTHORITY;
+ public static final String AUTHORITY = ProviderConfig.AUTHORITY;
static final String TABLE_FAVORITES = LauncherSettings.Favorites.TABLE_NAME;
static final String TABLE_WORKSPACE_SCREENS = LauncherSettings.WorkspaceScreens.TABLE_NAME;
diff --git a/src/com/android/launcher3/LauncherSettings.java b/src/com/android/launcher3/LauncherSettings.java
index f2c85a1..8a5804f 100644
--- a/src/com/android/launcher3/LauncherSettings.java
+++ b/src/com/android/launcher3/LauncherSettings.java
@@ -143,7 +143,7 @@
*
* @return The unique content URL for the specified row.
*/
- static Uri getContentUri(long id) {
+ public static Uri getContentUri(long id) {
return Uri.parse("content://" + ProviderConfig.AUTHORITY +
"/" + TABLE_NAME + "/" + id);
}
diff --git a/src/com/android/launcher3/model/MigrateFromRestoreTask.java b/src/com/android/launcher3/model/MigrateFromRestoreTask.java
new file mode 100644
index 0000000..cb90c8b
--- /dev/null
+++ b/src/com/android/launcher3/model/MigrateFromRestoreTask.java
@@ -0,0 +1,765 @@
+package com.android.launcher3.model;
+
+import android.content.ComponentName;
+import android.content.ContentProviderOperation;
+import android.content.ContentValues;
+import android.content.Context;
+import android.content.Intent;
+import android.content.SharedPreferences;
+import android.content.pm.PackageInfo;
+import android.database.Cursor;
+import android.graphics.Point;
+import android.text.TextUtils;
+import android.util.Log;
+
+import com.android.launcher3.InvariantDeviceProfile;
+import com.android.launcher3.ItemInfo;
+import com.android.launcher3.LauncherAppState;
+import com.android.launcher3.LauncherAppWidgetProviderInfo;
+import com.android.launcher3.LauncherModel;
+import com.android.launcher3.LauncherProvider;
+import com.android.launcher3.LauncherSettings;
+import com.android.launcher3.LauncherSettings.Favorites;
+import com.android.launcher3.Utilities;
+import com.android.launcher3.compat.PackageInstallerCompat;
+import com.android.launcher3.compat.UserHandleCompat;
+import com.android.launcher3.util.LongArrayMap;
+import com.android.launcher3.util.Thunk;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+
+/**
+ * This class takes care of shrinking the workspace (by maximum of one row and one column), as a
+ * result of restoring from a larger device.
+ */
+public class MigrateFromRestoreTask {
+
+ private static final String TAG = "MigrateFromRestoreTask";
+ private static final boolean DEBUG = false;
+
+ private static final String KEY_MIGRATION_SOURCE_SIZE = "migration_restore_src_size";
+ private static final String KEY_MIGRATION_WIDGET_MINSIZE = "migration_widget_min_size";
+
+ // These are carefully selected weights for various item types (Math.random?), to allow for
+ // the lease absurd migration experience.
+ private static final float WT_SHORTCUT = 1;
+ private static final float WT_APPLICATION = 0.8f;
+ private static final float WT_WIDGET_MIN = 2;
+ private static final float WT_WIDGET_FACTOR = 0.6f;
+ private static final float WT_FOLDER_FACTOR = 0.5f;
+
+ private final Context mContext;
+ private final ContentValues mTempValues = new ContentValues();
+ private final HashMap<String, Point> mWidgetMinSize;
+ private final InvariantDeviceProfile mIdp;
+
+ private HashSet<String> mValidPackages;
+ public ArrayList<Long> mEntryToRemove;
+ private ArrayList<ContentProviderOperation> mUpdateOperations;
+
+ private ArrayList<DbEntry> mCarryOver;
+
+ private final int mSrcX, mSrcY;
+ @Thunk final int mTrgX, mTrgY;
+ private final boolean mShouldRemoveX, mShouldRemoveY;
+
+ public MigrateFromRestoreTask(Context context) {
+ mContext = context;
+
+ SharedPreferences prefs = prefs(context);
+ Point sourceSize = parsePoint(prefs.getString(KEY_MIGRATION_SOURCE_SIZE, ""));
+ mSrcX = sourceSize.x;
+ mSrcY = sourceSize.y;
+
+ mWidgetMinSize = new HashMap<String, Point>();
+ for (String s : prefs.getStringSet(KEY_MIGRATION_WIDGET_MINSIZE,
+ Collections.<String>emptySet())) {
+ String[] parts = s.split("#");
+ mWidgetMinSize.put(parts[0], parsePoint(parts[1]));
+ }
+
+ mIdp = LauncherAppState.getInstance().getInvariantDeviceProfile();
+ mTrgX = mIdp.numColumns;
+ mTrgY = mIdp.numRows;
+ mShouldRemoveX = mTrgX < mSrcX;
+ mShouldRemoveY = mTrgY < mSrcY;
+ }
+
+ public void execute() throws Exception {
+ mEntryToRemove = new ArrayList<>();
+ mCarryOver = new ArrayList<>();
+ mUpdateOperations = new ArrayList<>();
+
+ // Initialize list of valid packages. This contain all the packages which are already on
+ // the device and packages which are being installed. Any item which doesn't belong to
+ // this set is removed.
+ // Since the loader removes such items anyway, removing these items here doesn't cause any
+ // extra data loss and gives us more free space on the grid for better migration.
+ mValidPackages = new HashSet<>();
+ for (PackageInfo info : mContext.getPackageManager().getInstalledPackages(0)) {
+ mValidPackages.add(info.packageName);
+ }
+ mValidPackages.addAll(PackageInstallerCompat.getInstance(mContext)
+ .updateAndGetActiveSessionCache().keySet());
+
+ ArrayList<Long> allScreens = LauncherModel.loadWorkspaceScreensDb(mContext);
+ if (allScreens.isEmpty()) {
+ throw new Exception("Unable to get workspace screens");
+ }
+
+ for (long screenId : allScreens) {
+ if (DEBUG) {
+ Log.d(TAG, "Migrating " + screenId);
+ }
+ migrateScreen(screenId);
+ }
+
+ if (!mCarryOver.isEmpty()) {
+ LongArrayMap<DbEntry> itemMap = new LongArrayMap<>();
+ for (DbEntry e : mCarryOver) {
+ itemMap.put(e.id, e);
+ }
+
+ do {
+ // Some items are still remaining. Try adding a few new screens.
+
+ // At every iteration, make sure that at least one item is removed from
+ // {@link #mCarryOver}, to prevent an infinite loop. If no item could be removed,
+ // break the loop and abort migration by throwing an exception.
+ OptimalPlacementSolution placement = new OptimalPlacementSolution(
+ new boolean[mTrgX][mTrgY], deepCopy(mCarryOver), true);
+ placement.find();
+ if (placement.finalPlacedItems.size() > 0) {
+ long newScreenId = LauncherAppState.getLauncherProvider().generateNewScreenId();
+ allScreens.add(newScreenId);
+ for (DbEntry item : placement.finalPlacedItems) {
+ if (!mCarryOver.remove(itemMap.get(item.id))) {
+ throw new Exception("Unable to find matching items");
+ }
+ item.screenId = newScreenId;
+ update(item);
+ }
+ } else {
+ throw new Exception("None of the items can be placed on an empty screen");
+ }
+
+ } while (!mCarryOver.isEmpty());
+
+
+ LauncherAppState.getInstance().getModel()
+ .updateWorkspaceScreenOrder(mContext, allScreens);
+ }
+
+ // Update items
+ mContext.getContentResolver().applyBatch(LauncherProvider.AUTHORITY, mUpdateOperations);
+
+ if (!mEntryToRemove.isEmpty()) {
+ if (DEBUG) {
+ Log.d(TAG, "Removing items: " + TextUtils.join(", ", mEntryToRemove));
+ }
+ mContext.getContentResolver().delete(LauncherSettings.Favorites.CONTENT_URI,
+ Utilities.createDbSelectionQuery(
+ LauncherSettings.Favorites._ID, mEntryToRemove), null);
+ }
+
+ // Make sure we haven't removed everything.
+ final Cursor c = mContext.getContentResolver().query(
+ LauncherSettings.Favorites.CONTENT_URI, null, null, null, null);
+ boolean hasData = c.moveToNext();
+ c.close();
+ if (!hasData) {
+ throw new Exception("Removed every thing during grid resize");
+ }
+ }
+
+ /**
+ * Migrate a particular screen id.
+ * Strategy:
+ * 1) For all possible combinations of row and column, pick the one which causes the least
+ * data loss: {@link #tryRemove(int, int, ArrayList, float[])}
+ * 2) Maintain a list of all lost items before this screen, and add any new item lost from
+ * this screen to that list as well.
+ * 3) If all those items from the above list can be placed on this screen, place them
+ * (otherwise they are placed on a new screen).
+ */
+ private void migrateScreen(long screenId) {
+ ArrayList<DbEntry> items = loadEntries(screenId);
+
+ int removedCol = Integer.MAX_VALUE;
+ int removedRow = Integer.MAX_VALUE;
+
+ // removeWt represents the cost function for loss of items during migration, and moveWt
+ // represents the cost function for repositioning the items. moveWt is only considered if
+ // removeWt is same for two different configurations.
+ // Start with Float.MAX_VALUE (assuming full data) and pick the configuration with least
+ // cost.
+ float removeWt = Float.MAX_VALUE;
+ float moveWt = Float.MAX_VALUE;
+ float[] outLoss = new float[2];
+ ArrayList<DbEntry> finalItems = null;
+
+ // Try removing all possible combinations
+ for (int x = 0; x < mSrcX; x++) {
+ for (int y = 0; y < mSrcY; y++) {
+ // Use a deep copy when trying out a particular combination as it can change
+ // the underlying object.
+ ArrayList<DbEntry> itemsOnScreen = tryRemove(x, y, deepCopy(items), outLoss);
+
+ if ((outLoss[0] < removeWt) || ((outLoss[0] == removeWt) && (outLoss[1] < moveWt))) {
+ removeWt = outLoss[0];
+ moveWt = outLoss[1];
+ removedCol = mShouldRemoveX ? x : removedCol;
+ removedRow = mShouldRemoveY ? y : removedRow;
+ finalItems = itemsOnScreen;
+ }
+
+ // No need to loop over all rows, if a row removal is not needed.
+ if (!mShouldRemoveY) {
+ break;
+ }
+ }
+
+ if (!mShouldRemoveX) {
+ break;
+ }
+ }
+
+ if (DEBUG) {
+ Log.d(TAG, String.format("Removing row %d, column %d on screen %d",
+ removedRow, removedCol, screenId));
+ }
+
+ LongArrayMap<DbEntry> itemMap = new LongArrayMap<>();
+ for (DbEntry e : deepCopy(items)) {
+ itemMap.put(e.id, e);
+ }
+
+ for (DbEntry item : finalItems) {
+ DbEntry org = itemMap.get(item.id);
+ itemMap.remove(item.id);
+
+ // Check if update is required
+ if (!item.columnsSame(org)) {
+ update(item);
+ }
+ }
+
+ // The remaining items in {@link #itemMap} are those which didn't get placed.
+ for (DbEntry item : itemMap) {
+ mCarryOver.add(item);
+ }
+
+ if (!mCarryOver.isEmpty() && removeWt == 0) {
+ // No new items were removed in this step. Try placing all the items on this screen.
+ boolean[][] occupied = new boolean[mTrgX][mTrgY];
+ for (DbEntry item : finalItems) {
+ markCells(occupied, item, true);
+ }
+
+ OptimalPlacementSolution placement = new OptimalPlacementSolution(occupied,
+ deepCopy(mCarryOver), true);
+ placement.find();
+ if (placement.lowestWeightLoss == 0) {
+ // All items got placed
+
+ for (DbEntry item : placement.finalPlacedItems) {
+ item.screenId = screenId;
+ update(item);
+ }
+
+ mCarryOver.clear();
+ }
+ }
+ }
+
+ /**
+ * Updates an item in the DB.
+ */
+ private void update(DbEntry item) {
+ mTempValues.clear();
+ item.addToContentValues(mTempValues);
+ mUpdateOperations.add(ContentProviderOperation
+ .newUpdate(LauncherSettings.Favorites.getContentUri(item.id))
+ .withValues(mTempValues).build());
+ }
+
+ /**
+ * Tries the remove the provided row and column.
+ * @param items all the items on the screen under operation
+ * @param outLoss array of size 2. The first entry is filled with weight loss, and the second
+ * with the overall item movement.
+ */
+ private ArrayList<DbEntry> tryRemove(int col, int row, ArrayList<DbEntry> items,
+ float[] outLoss) {
+ boolean[][] occupied = new boolean[mTrgX][mTrgY];
+
+ col = mShouldRemoveX ? col : Integer.MAX_VALUE;
+ row = mShouldRemoveY ? row : Integer.MAX_VALUE;
+
+ ArrayList<DbEntry> finalItems = new ArrayList<>();
+ ArrayList<DbEntry> removedItems = new ArrayList<>();
+
+ for (DbEntry item : items) {
+ if ((item.cellX <= col && (item.spanX + item.cellX) > col)
+ || (item.cellY <= row && (item.spanY + item.cellY) > row)) {
+ removedItems.add(item);
+ if (item.cellX >= col) item.cellX --;
+ if (item.cellY >= row) item.cellY --;
+ } else {
+ if (item.cellX > col) item.cellX --;
+ if (item.cellY > row) item.cellY --;
+ finalItems.add(item);
+ markCells(occupied, item, true);
+ }
+ }
+
+ OptimalPlacementSolution placement = new OptimalPlacementSolution(occupied, removedItems);
+ placement.find();
+ finalItems.addAll(placement.finalPlacedItems);
+ outLoss[0] = placement.lowestWeightLoss;
+ outLoss[1] = placement.lowestMoveCost;
+ return finalItems;
+ }
+
+ @Thunk void markCells(boolean[][] occupied, DbEntry item, boolean val) {
+ for (int i = item.cellX; i < (item.cellX + item.spanX); i++) {
+ for (int j = item.cellY; j < (item.cellY + item.spanY); j++) {
+ occupied[i][j] = val;
+ }
+ }
+ }
+
+ @Thunk boolean isVacant(boolean[][] occupied, int x, int y, int w, int h) {
+ if (x + w > mTrgX) return false;
+ if (y + h > mTrgY) return false;
+
+ for (int i = 0; i < w; i++) {
+ for (int j = 0; j < h; j++) {
+ if (occupied[i + x][j + y]) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
+ private class OptimalPlacementSolution {
+ private final ArrayList<DbEntry> itemsToPlace;
+ private final boolean[][] occupied;
+
+ // If set to true, item movement are not considered in move cost, leading to a more
+ // linear placement.
+ private final boolean ignoreMove;
+
+ float lowestWeightLoss = Float.MAX_VALUE;
+ float lowestMoveCost = Float.MAX_VALUE;
+ ArrayList<DbEntry> finalPlacedItems;
+
+ public OptimalPlacementSolution(boolean[][] occupied, ArrayList<DbEntry> itemsToPlace) {
+ this(occupied, itemsToPlace, false);
+ }
+
+ public OptimalPlacementSolution(boolean[][] occupied, ArrayList<DbEntry> itemsToPlace,
+ boolean ignoreMove) {
+ this.occupied = occupied;
+ this.itemsToPlace = itemsToPlace;
+ this.ignoreMove = ignoreMove;
+
+ // Sort the items such that larger widgets appear first followed by 1x1 items
+ Collections.sort(this.itemsToPlace);
+ }
+
+ public void find() {
+ find(0, 0, 0, new ArrayList<DbEntry>());
+ }
+
+ /**
+ * Recursively finds a placement for the provided items.
+ * @param index the position in {@link #itemsToPlace} to start looking at.
+ * @param weightLoss total weight loss upto this point
+ * @param moveCost total move cost upto this point
+ * @param itemsPlaced all the items already placed upto this point
+ */
+ public void find(int index, float weightLoss, float moveCost,
+ ArrayList<DbEntry> itemsPlaced) {
+ if ((weightLoss >= lowestWeightLoss) ||
+ ((weightLoss == lowestWeightLoss) && (moveCost >= lowestMoveCost))) {
+ // Abort, as we already have a better solution.
+ return;
+
+ } else if (index >= itemsToPlace.size()) {
+ // End loop.
+ lowestWeightLoss = weightLoss;
+ lowestMoveCost = moveCost;
+
+ // Keep a deep copy of current configuration as it can change during recursion.
+ finalPlacedItems = deepCopy(itemsPlaced);
+ return;
+ }
+
+ DbEntry me = itemsToPlace.get(index);
+ int myX = me.cellX;
+ int myY = me.cellY;
+
+ // List of items to pass over if this item was placed.
+ ArrayList<DbEntry> itemsIncludingMe = new ArrayList<>(itemsPlaced.size() + 1);
+ itemsIncludingMe.addAll(itemsPlaced);
+ itemsIncludingMe.add(me);
+
+ if (me.spanX > 1 || me.spanY > 1) {
+ // If the current item is a widget (and it greater than 1x1), try to place it at
+ // all possible positions. This is because a widget placed at one position can
+ // affect the placement of a different widget.
+ int myW = me.spanX;
+ int myH = me.spanY;
+
+ for (int y = 0; y < mTrgY; y++) {
+ for (int x = 0; x < mTrgX; x++) {
+ float newMoveCost = moveCost;
+ if (x != myX) {
+ me.cellX = x;
+ newMoveCost ++;
+ }
+ if (y != myY) {
+ me.cellY = y;
+ newMoveCost ++;
+ }
+ if (ignoreMove) {
+ newMoveCost = moveCost;
+ }
+
+ if (isVacant(occupied, x, y, myW, myH)) {
+ // place at this position and continue search.
+ markCells(occupied, me, true);
+ find(index + 1, weightLoss, newMoveCost, itemsIncludingMe);
+ markCells(occupied, me, false);
+ }
+
+ // Try resizing horizontally
+ if (myW > me.minSpanX && isVacant(occupied, x, y, myW - 1, myH)) {
+ me.spanX --;
+ markCells(occupied, me, true);
+ // 1 extra move cost
+ find(index + 1, weightLoss, newMoveCost + 1, itemsIncludingMe);
+ markCells(occupied, me, false);
+ me.spanX ++;
+ }
+
+ // Try resizing vertically
+ if (myH > me.minSpanY && isVacant(occupied, x, y, myW, myH - 1)) {
+ me.spanY --;
+ markCells(occupied, me, true);
+ // 1 extra move cost
+ find(index + 1, weightLoss, newMoveCost + 1, itemsIncludingMe);
+ markCells(occupied, me, false);
+ me.spanY ++;
+ }
+
+ // Try resizing horizontally & vertically
+ if (myH > me.minSpanY && myW > me.minSpanX &&
+ isVacant(occupied, x, y, myW - 1, myH - 1)) {
+ me.spanX --;
+ me.spanY --;
+ markCells(occupied, me, true);
+ // 2 extra move cost
+ find(index + 1, weightLoss, newMoveCost + 2, itemsIncludingMe);
+ markCells(occupied, me, false);
+ me.spanX ++;
+ me.spanY ++;
+ }
+ me.cellX = myX;
+ me.cellY = myY;
+ }
+ }
+
+ // Finally also try a solution when this item is not included. Trying it in the end
+ // causes it to get skipped in most cases due to higher weight loss, and prevents
+ // unnecessary deep copies of various configurations.
+ find(index + 1, weightLoss + me.weight, moveCost, itemsPlaced);
+ } else {
+ // Since this is a 1x1 item and all the following items are also 1x1, just place
+ // it at 'the most appropriate position' and hope for the best.
+ // The most appropriate position: one with lease straight line distance
+ int newDistance = Integer.MAX_VALUE;
+ int newX = Integer.MAX_VALUE, newY = Integer.MAX_VALUE;
+
+ for (int y = 0; y < mTrgY; y++) {
+ for (int x = 0; x < mTrgX; x++) {
+ if (!occupied[x][y]) {
+ int dist = ignoreMove ? 0 :
+ ((me.cellX - x) * (me.cellX - x) + (me.cellY - y) * (me.cellY - y));
+ if (dist < newDistance) {
+ newX = x;
+ newY = y;
+ newDistance = dist;
+ }
+ }
+ }
+ }
+
+ if (newX < mTrgX && newY < mTrgY) {
+ float newMoveCost = moveCost;
+ if (newX != myX) {
+ me.cellX = newX;
+ newMoveCost ++;
+ }
+ if (newY != myY) {
+ me.cellY = newY;
+ newMoveCost ++;
+ }
+ if (ignoreMove) {
+ newMoveCost = moveCost;
+ }
+ markCells(occupied, me, true);
+ find(index + 1, weightLoss, newMoveCost, itemsIncludingMe);
+ markCells(occupied, me, false);
+ me.cellX = myX;
+ me.cellY = myY;
+
+ // Try to find a solution without this item, only if
+ // 1) there was at least one space, i.e., we were able to place this item
+ // 2) if the next item has the same weight (all items are already sorted), as
+ // if it has lower weight, that solution will automatically get discarded.
+ // 3) ignoreMove false otherwise, move cost is ignored and the weight will
+ // anyway be same.
+ if (index + 1 < itemsToPlace.size()
+ && itemsToPlace.get(index + 1).weight >= me.weight && !ignoreMove) {
+ find(index + 1, weightLoss + me.weight, moveCost, itemsPlaced);
+ }
+ } else {
+ // No more space. Jump to the end.
+ for (int i = index + 1; i < itemsToPlace.size(); i++) {
+ weightLoss += itemsToPlace.get(i).weight;
+ }
+ find(itemsToPlace.size(), weightLoss + me.weight, moveCost, itemsPlaced);
+ }
+ }
+ }
+ }
+
+ /**
+ * Loads entries for a particular screen id.
+ */
+ public ArrayList<DbEntry> loadEntries(long screen) {
+ Cursor c = mContext.getContentResolver().query(LauncherSettings.Favorites.CONTENT_URI,
+ new String[] {
+ Favorites._ID, // 0
+ Favorites.ITEM_TYPE, // 1
+ Favorites.CELLX, // 2
+ Favorites.CELLY, // 3
+ Favorites.SPANX, // 4
+ Favorites.SPANY, // 5
+ Favorites.INTENT, // 6
+ Favorites.APPWIDGET_PROVIDER}, // 7
+ Favorites.CONTAINER + " = " + Favorites.CONTAINER_DESKTOP
+ + " AND " + Favorites.SCREEN + " = " + screen, null, null, null);
+
+ final int indexId = c.getColumnIndexOrThrow(Favorites._ID);
+ final int indexItemType = c.getColumnIndexOrThrow(Favorites.ITEM_TYPE);
+ final int indexCellX = c.getColumnIndexOrThrow(Favorites.CELLX);
+ final int indexCellY = c.getColumnIndexOrThrow(Favorites.CELLY);
+ final int indexSpanX = c.getColumnIndexOrThrow(Favorites.SPANX);
+ final int indexSpanY = c.getColumnIndexOrThrow(Favorites.SPANY);
+ final int indexIntent = c.getColumnIndexOrThrow(Favorites.INTENT);
+ final int indexAppWidgetProvider = c.getColumnIndexOrThrow(Favorites.APPWIDGET_PROVIDER);
+
+ ArrayList<DbEntry> entries = new ArrayList<>();
+ while (c.moveToNext()) {
+ DbEntry entry = new DbEntry();
+ entry.id = c.getLong(indexId);
+ entry.itemType = c.getInt(indexItemType);
+ entry.cellX = c.getInt(indexCellX);
+ entry.cellY = c.getInt(indexCellY);
+ entry.spanX = c.getInt(indexSpanX);
+ entry.spanY = c.getInt(indexSpanY);
+ entry.screenId = screen;
+
+ try {
+ // calculate weight
+ switch (entry.itemType) {
+ case Favorites.ITEM_TYPE_SHORTCUT:
+ case Favorites.ITEM_TYPE_APPLICATION: {
+ verifyIntent(c.getString(indexIntent));
+ entry.weight = entry.itemType == Favorites.ITEM_TYPE_SHORTCUT
+ ? WT_SHORTCUT : WT_APPLICATION;
+ break;
+ }
+ case Favorites.ITEM_TYPE_APPWIDGET: {
+ String provider = c.getString(indexAppWidgetProvider);
+ ComponentName cn = ComponentName.unflattenFromString(provider);
+ verifyPackage(cn.getPackageName());
+ entry.weight = Math.max(WT_WIDGET_MIN, WT_WIDGET_FACTOR
+ * entry.spanX * entry.spanY);
+
+ // Migration happens for current user only.
+ LauncherAppWidgetProviderInfo pInfo = LauncherModel.getProviderInfo(
+ mContext, cn, UserHandleCompat.myUserHandle());
+ Point spans = pInfo == null ?
+ mWidgetMinSize.get(provider) : pInfo.getMinSpans(mIdp, mContext);
+ if (spans != null) {
+ entry.minSpanX = spans.x > 0 ? spans.x : entry.spanX;
+ entry.minSpanY = spans.y > 0 ? spans.y : entry.spanY;
+ } else {
+ // Assume that the widget be resized down to 2x2
+ entry.minSpanX = entry.minSpanY = 2;
+ }
+
+ if (entry.minSpanX > mTrgX || entry.minSpanY > mTrgY) {
+ throw new Exception("Widget can't be resized down to fit the grid");
+ }
+ break;
+ }
+ case Favorites.ITEM_TYPE_FOLDER: {
+ int total = getFolderItemsCount(entry.id);
+ if (total == 0) {
+ throw new Exception("Folder is empty");
+ }
+ entry.weight = WT_FOLDER_FACTOR * total;
+ break;
+ }
+ default:
+ throw new Exception("Invalid item type");
+ }
+ } catch (Exception e) {
+ if (DEBUG) {
+ Log.d(TAG, "Removing item " + entry.id, e);
+ }
+ mEntryToRemove.add(entry.id);
+ continue;
+ }
+
+ entries.add(entry);
+ }
+ return entries;
+ }
+
+ /**
+ * @return the number of valid items in the folder.
+ */
+ private int getFolderItemsCount(long folderId) {
+ Cursor c = mContext.getContentResolver().query(LauncherSettings.Favorites.CONTENT_URI,
+ new String[] {Favorites._ID, Favorites.INTENT},
+ Favorites.CONTAINER + " = " + folderId, null, null, null);
+
+ int total = 0;
+ while (c.moveToNext()) {
+ try {
+ verifyIntent(c.getString(1));
+ total++;
+ } catch (Exception e) {
+ mEntryToRemove.add(c.getLong(0));
+ }
+ }
+
+ return total;
+ }
+
+ /**
+ * Verifies if the intent should be restored.
+ */
+ private void verifyIntent(String intentStr) throws Exception {
+ Intent intent = Intent.parseUri(intentStr, 0);
+ if (intent.getComponent() != null) {
+ verifyPackage(intent.getComponent().getPackageName());
+ } else if (intent.getPackage() != null) {
+ // Only verify package if the component was null.
+ verifyPackage(intent.getPackage());
+ }
+ }
+
+ /**
+ * Verifies if the package should be restored
+ */
+ private void verifyPackage(String packageName) throws Exception {
+ if (!mValidPackages.contains(packageName)) {
+ throw new Exception("Package not available");
+ }
+ }
+
+ private static class DbEntry extends ItemInfo implements Comparable<DbEntry> {
+
+ public float weight;
+
+ public DbEntry() { }
+
+ public DbEntry copy() {
+ DbEntry entry = new DbEntry();
+ entry.copyFrom(this);
+ entry.weight = weight;
+ entry.minSpanX = minSpanX;
+ entry.minSpanY = minSpanY;
+ return entry;
+ }
+
+ /**
+ * Comparator such that larger widgets come first, followed by all 1x1 items
+ * based on their weights.
+ */
+ @Override
+ public int compareTo(DbEntry another) {
+ if (itemType == Favorites.ITEM_TYPE_APPWIDGET) {
+ if (another.itemType == Favorites.ITEM_TYPE_APPWIDGET) {
+ return another.spanY * another.spanX - spanX * spanY;
+ } else {
+ return -1;
+ }
+ } else if (another.itemType == Favorites.ITEM_TYPE_APPWIDGET) {
+ return 1;
+ } else {
+ // Place higher weight before lower weight.
+ return Float.compare(another.weight, weight);
+ }
+ }
+
+ public boolean columnsSame(DbEntry org) {
+ return org.cellX == cellX && org.cellY == cellY && org.spanX == spanX &&
+ org.spanY == spanY && org.screenId == screenId;
+ }
+
+ public void addToContentValues(ContentValues values) {
+ values.put(LauncherSettings.Favorites.SCREEN, screenId);
+ values.put(LauncherSettings.Favorites.CELLX, cellX);
+ values.put(LauncherSettings.Favorites.CELLY, cellY);
+ values.put(LauncherSettings.Favorites.SPANX, spanX);
+ values.put(LauncherSettings.Favorites.SPANY, spanY);
+ }
+ }
+
+ @Thunk static ArrayList<DbEntry> deepCopy(ArrayList<DbEntry> src) {
+ ArrayList<DbEntry> dup = new ArrayList<DbEntry>(src.size());
+ for (DbEntry e : src) {
+ dup.add(e.copy());
+ }
+ return dup;
+ }
+
+ private static Point parsePoint(String point) {
+ String[] split = point.split(",");
+ return new Point(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
+ }
+
+ public static void markForMigration(Context context, int srcX, int srcY,
+ HashSet<String> widgets) {
+ prefs(context).edit()
+ .putString(KEY_MIGRATION_SOURCE_SIZE, srcX + "," + srcY)
+ .putStringSet(KEY_MIGRATION_WIDGET_MINSIZE, widgets)
+ .apply();
+ }
+
+ public static boolean shouldRunTask(Context context) {
+ return !TextUtils.isEmpty(prefs(context).getString(KEY_MIGRATION_SOURCE_SIZE, ""));
+ }
+
+ public static void clearFlags(Context context) {
+ prefs(context).edit().remove(KEY_MIGRATION_SOURCE_SIZE)
+ .remove(KEY_MIGRATION_WIDGET_MINSIZE).commit();
+ }
+
+ private static SharedPreferences prefs(Context context) {
+ return context.getSharedPreferences(LauncherAppState.getSharedPreferencesKey(),
+ Context.MODE_PRIVATE);
+ }
+}