Fixing static instance of Indexer being created in the model

Indexer depends on the locale and should be created when ever the config
changes. Moving the widget indexing to the adapter (similar to allApps)
which gets created whenever the activity is recreated.
This fixes the bug where widgets indexing breaks if locale changes while launcher
process is alive
Also fixing the bug in widget model cloning where the HashMap was not cloning
the underlying ArrayList

Change-Id: I7dbe6290e73299c4c07aa7fa564077a2649e1a4c

13 files changed, 279 insertions, 252 deletions

diff --git a/src/com/android/launcher3/Launcher.java b/src/com/android/launcher3/Launcher.java
index 3149ce44c..40820fa9a 100644
--- a/src/com/android/launcher3/Launcher.java
+++ b/src/com/android/launcher3/Launcher.java
@@ -103,7 +103,8 @@ import com.android.launcher3.keyboard.CustomActionsPopup;
 import com.android.launcher3.keyboard.ViewGroupFocusHelper;
 import com.android.launcher3.logging.FileLog;
 import com.android.launcher3.logging.UserEventDispatcher;
-import com.android.launcher3.model.WidgetsModel;
+import com.android.launcher3.model.PackageItemInfo;
+import com.android.launcher3.model.WidgetItem;
 import com.android.launcher3.pageindicators.PageIndicator;
 import com.android.launcher3.shortcuts.DeepShortcutManager;
 import com.android.launcher3.shortcuts.DeepShortcutsContainer;
@@ -229,7 +230,7 @@ public class Launcher extends Activity
 
     // Main container view and the model for the widget tray screen.
     @Thunk WidgetsContainerView mWidgetsView;
-    @Thunk WidgetsModel mWidgetsModel;
+    @Thunk MultiHashMap<PackageItemInfo, WidgetItem> mAllWidgets;
 
     // We set the state in both onCreate and then onNewIntent in some cases, which causes both
     // scroll issues (because the workspace may not have been measured yet) and extra work.
@@ -3836,22 +3837,22 @@ public class Launcher extends Activity
         }
     }
 
-    private Runnable mBindWidgetModelRunnable = new Runnable() {
+    private Runnable mBindAllWidgetsRunnable = new Runnable() {
             public void run() {
-                bindWidgetsModel(mWidgetsModel);
+                bindAllWidgets(mAllWidgets);
             }
         };
 
     @Override
-    public void bindWidgetsModel(WidgetsModel model) {
-        if (waitUntilResume(mBindWidgetModelRunnable, true)) {
-            mWidgetsModel = model;
+    public void bindAllWidgets(MultiHashMap<PackageItemInfo, WidgetItem> allWidgets) {
+        if (waitUntilResume(mBindAllWidgetsRunnable, true)) {
+            mAllWidgets = allWidgets;
             return;
         }
 
-        if (mWidgetsView != null && model != null) {
-            mWidgetsView.addWidgets(model);
-            mWidgetsModel = null;
+        if (mWidgetsView != null && allWidgets != null) {
+            mWidgetsView.setWidgets(allWidgets);
+            mAllWidgets = null;
         }
     }
 
diff --git a/src/com/android/launcher3/LauncherModel.java b/src/com/android/launcher3/LauncherModel.java
index caf8870c2..55bd0a45a 100644
--- a/src/com/android/launcher3/LauncherModel.java
+++ b/src/com/android/launcher3/LauncherModel.java
@@ -61,7 +61,9 @@ import com.android.launcher3.graphics.LauncherIcons;
 import com.android.launcher3.logging.FileLog;
 import com.android.launcher3.model.BgDataModel;
 import com.android.launcher3.model.GridSizeMigrationTask;
+import com.android.launcher3.model.PackageItemInfo;
 import com.android.launcher3.model.SdCardAvailableReceiver;
+import com.android.launcher3.model.WidgetItem;
 import com.android.launcher3.model.WidgetsModel;
 import com.android.launcher3.provider.ImportDataTask;
 import com.android.launcher3.provider.LauncherDbUtils;
@@ -198,7 +200,7 @@ public class LauncherModel extends BroadcastReceiver
                 UserHandleCompat user);
         public void bindAppInfosRemoved(ArrayList<AppInfo> appInfos);
         public void notifyWidgetProvidersChanged();
-        public void bindWidgetsModel(WidgetsModel model);
+        public void bindAllWidgets(MultiHashMap<PackageItemInfo, WidgetItem> widgets);
         public void onPageBoundSynchronously(int page);
         public void executeOnNextDraw(ViewOnDrawExecutor executor);
         public void bindDeepShortcutMap(MultiHashMap<ComponentKey, String> deepShortcutMap);
@@ -209,7 +211,7 @@ public class LauncherModel extends BroadcastReceiver
         Context context = app.getContext();
         mApp = app;
         mBgAllAppsList = new AllAppsList(iconCache, appFilter);
-        mBgWidgetsModel = new WidgetsModel(context, iconCache, appFilter);
+        mBgWidgetsModel = new WidgetsModel(iconCache, appFilter);
         mIconCache = iconCache;
         mDeepShortcutManager = deepShortcutManager;
 
@@ -3263,13 +3265,15 @@ public class LauncherModel extends BroadcastReceiver
         }
     }
 
-    private void bindWidgetsModel(final Callbacks callbacks, final WidgetsModel model) {
+    private void bindWidgetsModel(final Callbacks callbacks) {
+        final MultiHashMap<PackageItemInfo, WidgetItem> widgets
+                = mBgWidgetsModel.getWidgetsMap().clone();
         mHandler.post(new Runnable() {
             @Override
             public void run() {
                 Callbacks cb = getCallback();
                 if (callbacks == cb && cb != null) {
-                    callbacks.bindWidgetsModel(model);
+                    callbacks.bindAllWidgets(widgets);
                 }
             }
         });
@@ -3281,13 +3285,13 @@ public class LauncherModel extends BroadcastReceiver
             @Override
             public void run() {
                 if (bindFirst && !mBgWidgetsModel.isEmpty()) {
-                    bindWidgetsModel(callbacks, mBgWidgetsModel.clone());
+                    bindWidgetsModel(callbacks);
                 }
-                final WidgetsModel model = mBgWidgetsModel.updateAndClone(mApp.getContext());
-                bindWidgetsModel(callbacks, model);
+                ArrayList<WidgetItem> allWidgets = mBgWidgetsModel.update(mApp.getContext());
+                bindWidgetsModel(callbacks);
+
                 // update the Widget entries inside DB on the worker thread.
-                LauncherAppState.getInstance().getWidgetCache().removeObsoletePreviews(
-                        model.getRawList());
+                LauncherAppState.getInstance().getWidgetCache().removeObsoletePreviews(allWidgets);
             }
         });
     }
diff --git a/src/com/android/launcher3/allapps/AlphabeticalAppsList.java b/src/com/android/launcher3/allapps/AlphabeticalAppsList.java
index 5a28e5c01..8b7a6ba4d 100644
--- a/src/com/android/launcher3/allapps/AlphabeticalAppsList.java
+++ b/src/com/android/launcher3/allapps/AlphabeticalAppsList.java
@@ -23,8 +23,8 @@ import com.android.launcher3.Launcher;
 import com.android.launcher3.compat.AlphabeticIndexCompat;
 import com.android.launcher3.compat.UserHandleCompat;
 import com.android.launcher3.config.ProviderConfig;
-import com.android.launcher3.model.AppNameComparator;
 import com.android.launcher3.util.ComponentKey;
+import com.android.launcher3.util.LabelComparator;
 
 import java.util.ArrayList;
 import java.util.Collections;
@@ -163,7 +163,7 @@ public class AlphabeticalAppsList {
     private HashMap<CharSequence, String> mCachedSectionNames = new HashMap<>();
     private AllAppsGridAdapter mAdapter;
     private AlphabeticIndexCompat mIndexer;
-    private AppNameComparator mAppNameComparator;
+    private AppInfoComparator mAppNameComparator;
     private int mNumAppsPerRow;
     private int mNumPredictedAppsPerRow;
     private int mNumAppRowsInAdapter;
@@ -171,7 +171,7 @@ public class AlphabeticalAppsList {
     public AlphabeticalAppsList(Context context) {
         mLauncher = Launcher.getLauncher(context);
         mIndexer = new AlphabeticIndexCompat(context);
-        mAppNameComparator = new AppNameComparator(context);
+        mAppNameComparator = new AppInfoComparator(context);
     }
 
     /**
@@ -305,17 +305,16 @@ public class AlphabeticalAppsList {
         // Sort the list of apps
         mApps.clear();
         mApps.addAll(mComponentToAppMap.values());
-        Collections.sort(mApps, mAppNameComparator.getAppInfoComparator());
+        Collections.sort(mApps, mAppNameComparator);
 
         // As a special case for some languages (currently only Simplified Chinese), we may need to
         // coalesce sections
         Locale curLocale = mLauncher.getResources().getConfiguration().locale;
-        TreeMap<String, ArrayList<AppInfo>> sectionMap = null;
         boolean localeRequiresSectionSorting = curLocale.equals(Locale.SIMPLIFIED_CHINESE);
         if (localeRequiresSectionSorting) {
-            // Compute the section headers.  We use a TreeMap with the section name comparator to
+            // Compute the section headers. We use a TreeMap with the section name comparator to
             // ensure that the sections are ordered when we iterate over it later
-            sectionMap = new TreeMap<>(mAppNameComparator.getSectionNameComparator());
+            TreeMap<String, ArrayList<AppInfo>> sectionMap = new TreeMap<>(new LabelComparator());
             for (AppInfo info : mApps) {
                 // Add the section to the cache
                 String sectionName = getAndUpdateCachedSectionName(info.title);
@@ -330,13 +329,10 @@ public class AlphabeticalAppsList {
             }
 
             // Add each of the section apps to the list in order
-            List<AppInfo> allApps = new ArrayList<>(mApps.size());
+            mApps.clear();
             for (Map.Entry<String, ArrayList<AppInfo>> entry : sectionMap.entrySet()) {
-                allApps.addAll(entry.getValue());
+                mApps.addAll(entry.getValue());
             }
-
-            mApps.clear();
-            mApps.addAll(allApps);
         } else {
             // Just compute the section headers for use below
             for (AppInfo info : mApps) {
diff --git a/src/com/android/launcher3/model/AbstractUserComparator.java b/src/com/android/launcher3/allapps/AppInfoComparator.java
index bd28560f3..1f5fece5f 100644
--- a/src/com/android/launcher3/model/AbstractUserComparator.java
+++ b/src/com/android/launcher3/allapps/AppInfoComparator.java
@@ -13,36 +13,51 @@
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
-package com.android.launcher3.model;
+package com.android.launcher3.allapps;
 
 import android.content.Context;
 
-import com.android.launcher3.ItemInfo;
+import com.android.launcher3.AppInfo;
 import com.android.launcher3.compat.UserHandleCompat;
 import com.android.launcher3.compat.UserManagerCompat;
+import com.android.launcher3.util.LabelComparator;
 
 import java.util.Comparator;
 
 /**
  * A comparator to arrange items based on user profiles.
  */
-public abstract class AbstractUserComparator<T extends ItemInfo> implements Comparator<T> {
+public class AppInfoComparator implements Comparator<AppInfo> {
 
     private final UserManagerCompat mUserManager;
     private final UserHandleCompat mMyUser;
+    private final LabelComparator mLabelComparator;
 
-    public AbstractUserComparator(Context context) {
+    public AppInfoComparator(Context context) {
         mUserManager = UserManagerCompat.getInstance(context);
         mMyUser = UserHandleCompat.myUserHandle();
+        mLabelComparator = new LabelComparator();
     }
 
     @Override
-    public int compare(T lhs, T rhs) {
-        if (mMyUser.equals(lhs.user)) {
+    public int compare(AppInfo a, AppInfo b) {
+        // Order by the title in the current locale
+        int result = mLabelComparator.compare(a.title.toString(), b.title.toString());
+        if (result != 0) {
+            return result;
+        }
+
+        // If labels are same, compare component names
+        result = a.componentName.compareTo(b.componentName);
+        if (result != 0) {
+            return result;
+        }
+
+        if (mMyUser.equals(a.user)) {
             return -1;
         } else {
-            Long aUserSerial = mUserManager.getSerialNumberForUser(lhs.user);
-            Long bUserSerial = mUserManager.getSerialNumberForUser(rhs.user);
+            Long aUserSerial = mUserManager.getSerialNumberForUser(a.user);
+            Long bUserSerial = mUserManager.getSerialNumberForUser(b.user);
             return aUserSerial.compareTo(bUserSerial);
         }
     }
diff --git a/src/com/android/launcher3/model/AppNameComparator.java b/src/com/android/launcher3/model/AppNameComparator.java
deleted file mode 100644
index 5f80037dc..000000000
--- a/src/com/android/launcher3/model/AppNameComparator.java
+++ /dev/null
@@ -1,99 +0,0 @@
-/*
- * Copyright (C) 2015 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.model;
-
-import android.content.Context;
-
-import com.android.launcher3.AppInfo;
-import com.android.launcher3.ItemInfo;
-import com.android.launcher3.util.Thunk;
-
-import java.text.Collator;
-import java.util.Comparator;
-
-/**
- * Class to manage access to an app name comparator.
- * <p>
- * Used to sort application name in all apps view and widget tray view.
- */
-public class AppNameComparator {
-    private final Collator mCollator;
-    private final AbstractUserComparator<ItemInfo> mAppInfoComparator;
-    private final Comparator<String> mSectionNameComparator;
-
-    public AppNameComparator(Context context) {
-        mCollator = Collator.getInstance();
-        mAppInfoComparator = new AbstractUserComparator<ItemInfo>(context) {
-
-            @Override
-            public final int compare(ItemInfo a, ItemInfo b) {
-                // Order by the title in the current locale
-                int result = compareTitles(a.title.toString(), b.title.toString());
-                if (result == 0 && a instanceof AppInfo && b instanceof AppInfo) {
-                    AppInfo aAppInfo = (AppInfo) a;
-                    AppInfo bAppInfo = (AppInfo) b;
-                    // If two apps have the same title, then order by the component name
-                    result = aAppInfo.componentName.compareTo(bAppInfo.componentName);
-                    if (result == 0) {
-                        // If the two apps are the same component, then prioritize by the order that
-                        // the app user was created (prioritizing the main user's apps)
-                        return super.compare(a, b);
-                    }
-                }
-                return result;
-            }
-        };
-        mSectionNameComparator = new Comparator<String>() {
-            @Override
-            public int compare(String o1, String o2) {
-                return compareTitles(o1, o2);
-            }
-        };
-    }
-
-    /**
-     * Returns a locale-aware comparator that will alphabetically order a list of applications.
-     */
-    public Comparator<ItemInfo> getAppInfoComparator() {
-        return mAppInfoComparator;
-    }
-
-    /**
-     * Returns a locale-aware comparator that will alphabetically order a list of section names.
-     */
-    public Comparator<String> getSectionNameComparator() {
-        return mSectionNameComparator;
-    }
-
-    /**
-     * Compares two titles with the same return value semantics as Comparator.
-     */
-    @Thunk int compareTitles(String titleA, String titleB) {
-        // Ensure that we de-prioritize any titles that don't start with a linguistic letter or digit
-        boolean aStartsWithLetter = (titleA.length() > 0) &&
-                Character.isLetterOrDigit(titleA.codePointAt(0));
-        boolean bStartsWithLetter = (titleB.length() > 0) &&
-                Character.isLetterOrDigit(titleB.codePointAt(0));
-        if (aStartsWithLetter && !bStartsWithLetter) {
-            return -1;
-        } else if (!aStartsWithLetter && bStartsWithLetter) {
-            return 1;
-        }
-
-        // Order by the title in the current locale
-        return mCollator.compare(titleA, titleB);
-    }
-}
diff --git a/src/com/android/launcher3/model/PackageItemInfo.java b/src/com/android/launcher3/model/PackageItemInfo.java
index c86ba86fd..00470e1ea 100644
--- a/src/com/android/launcher3/model/PackageItemInfo.java
+++ b/src/com/android/launcher3/model/PackageItemInfo.java
@@ -40,12 +40,6 @@ public class PackageItemInfo extends ItemInfo {
      */
     public String packageName;
 
-    /**
-     * Character that is used as a section name for the {@link ItemInfo#title}.
-     * (e.g., "G" will be stored if title is "Google")
-     */
-    public String titleSectionName;
-
     PackageItemInfo(String packageName) {
         this.packageName = packageName;
     }
diff --git a/src/com/android/launcher3/model/WidgetsModel.java b/src/com/android/launcher3/model/WidgetsModel.java
index b2a94bb34..3953f3964 100644
--- a/src/com/android/launcher3/model/WidgetsModel.java
+++ b/src/com/android/launcher3/model/WidgetsModel.java
@@ -18,7 +18,9 @@ import com.android.launcher3.LauncherAppState;
 import com.android.launcher3.LauncherAppWidgetProviderInfo;
 import com.android.launcher3.compat.AlphabeticIndexCompat;
 import com.android.launcher3.compat.AppWidgetManagerCompat;
+import com.android.launcher3.compat.UserHandleCompat;
 import com.android.launcher3.config.ProviderConfig;
+import com.android.launcher3.util.MultiHashMap;
 import com.android.launcher3.util.Preconditions;
 
 import java.util.ArrayList;
@@ -37,74 +39,31 @@ public class WidgetsModel {
     private static final String TAG = "WidgetsModel";
     private static final boolean DEBUG = false;
 
-    /* List of packages that is tracked by this model. */
-    private final ArrayList<PackageItemInfo> mPackageItemInfos;
-
     /* Map of widgets and shortcuts that are tracked per package. */
-    private final HashMap<PackageItemInfo, ArrayList<WidgetItem>> mWidgetsList;
+    private final MultiHashMap<PackageItemInfo, WidgetItem> mWidgetsList;
 
-    private final AppWidgetManagerCompat mAppWidgetMgr;
-    private final Comparator<ItemInfo> mAppNameComparator;
     private final IconCache mIconCache;
     private final AppFilter mAppFilter;
-    private final AlphabeticIndexCompat mIndexer;
-
-    private ArrayList<WidgetItem> mRawList;
 
-    public WidgetsModel(Context context,  IconCache iconCache, AppFilter appFilter) {
-        mAppWidgetMgr = AppWidgetManagerCompat.getInstance(context);
-        mAppNameComparator = (new AppNameComparator(context)).getAppInfoComparator();
+    public WidgetsModel(IconCache iconCache, AppFilter appFilter) {
         mIconCache = iconCache;
         mAppFilter = appFilter;
-        mIndexer = new AlphabeticIndexCompat(context);
-        mPackageItemInfos = new ArrayList<>();
-        mWidgetsList = new HashMap<>();
-
-        mRawList = new ArrayList<>();
-    }
-
-    @SuppressWarnings("unchecked")
-    private WidgetsModel(WidgetsModel model) {
-        mAppWidgetMgr = model.mAppWidgetMgr;
-        mPackageItemInfos = (ArrayList<PackageItemInfo>) model.mPackageItemInfos.clone();
-        mWidgetsList = (HashMap<PackageItemInfo, ArrayList<WidgetItem>>) model.mWidgetsList.clone();
-        mAppNameComparator = model.mAppNameComparator;
-        mIconCache = model.mIconCache;
-        mAppFilter = model.mAppFilter;
-        mIndexer = model.mIndexer;
-        mRawList = (ArrayList<WidgetItem>) model.mRawList.clone();
-    }
-
-    // Access methods that may be deleted if the private fields are made package-private.
-    public int getPackageSize() {
-        return mPackageItemInfos.size();
-    }
-
-    // Access methods that may be deleted if the private fields are made package-private.
-    public PackageItemInfo getPackageItemInfo(int pos) {
-        if (pos >= mPackageItemInfos.size() || pos < 0) {
-            return null;
-        }
-        return mPackageItemInfos.get(pos);
+        mWidgetsList = new MultiHashMap<>();
     }
 
-    public List<WidgetItem> getSortedWidgets(int pos) {
-        return mWidgetsList.get(mPackageItemInfos.get(pos));
-    }
-
-    public ArrayList<WidgetItem> getRawList() {
-        return mRawList;
+    public MultiHashMap<PackageItemInfo, WidgetItem> getWidgetsMap() {
+        return mWidgetsList;
     }
 
     public boolean isEmpty() {
-        return mRawList.isEmpty();
+        return mWidgetsList.isEmpty();
     }
 
-    public WidgetsModel updateAndClone(Context context) {
+    public ArrayList<WidgetItem> update(Context context) {
         Preconditions.assertWorkerThread();
 
+        final ArrayList<WidgetItem> widgetsAndShortcuts = new ArrayList<>();
         try {
-            final ArrayList<WidgetItem> widgetsAndShortcuts = new ArrayList<>();
             // Widgets
             AppWidgetManagerCompat widgetManager = AppWidgetManagerCompat.getInstance(context);
             for (AppWidgetProviderInfo widgetInfo : widgetManager.getAllProviders()) {
@@ -132,11 +91,10 @@ public class WidgetsModel {
                 throw e;
             }
         }
-        return clone();
+        return widgetsAndShortcuts;
     }
 
     private void setWidgetsAndShortcuts(ArrayList<WidgetItem> rawWidgetsShortcuts) {
-        mRawList = rawWidgetsShortcuts;
         if (DEBUG) {
             Log.d(TAG, "addWidgetsAndShortcuts, widgetsShortcuts#=" + rawWidgetsShortcuts.size());
         }
@@ -147,9 +105,9 @@ public class WidgetsModel {
 
         // clear the lists.
         mWidgetsList.clear();
-        mPackageItemInfos.clear();
 
         InvariantDeviceProfile idp = LauncherAppState.getInstance().getInvariantDeviceProfile();
+        UserHandleCompat myUser = UserHandleCompat.myUserHandle();
 
         // add and update.
         for (WidgetItem item: rawWidgetsShortcuts) {
@@ -177,43 +135,20 @@ public class WidgetsModel {
 
             String packageName = item.componentName.getPackageName();
             PackageItemInfo pInfo = tmpPackageItemInfos.get(packageName);
-            ArrayList<WidgetItem> widgetsShortcutsList = mWidgetsList.get(pInfo);
-
-            if (widgetsShortcutsList == null) {
-                widgetsShortcutsList = new ArrayList<>();
-
+            if (pInfo == null) {
                 pInfo = new PackageItemInfo(packageName);
+                pInfo.user = item.user;
                 tmpPackageItemInfos.put(packageName,  pInfo);
-
-                mPackageItemInfos.add(pInfo);
-                mWidgetsList.put(pInfo, widgetsShortcutsList);
+            } else if (!myUser.equals(pInfo.user)) {
+                // Keep updating the user, until we get the primary user.
+                pInfo.user = item.user;
             }
-
-            widgetsShortcutsList.add(item);
+            mWidgetsList.addToList(pInfo, item);
         }
 
         // Update each package entry
-        for (PackageItemInfo p : mPackageItemInfos) {
-            ArrayList<WidgetItem> widgetsShortcutsList = mWidgetsList.get(p);
-            Collections.sort(widgetsShortcutsList);
-
-            // Update the package entry based on the first item.
-            p.user = widgetsShortcutsList.get(0).user;
+        for (PackageItemInfo p : tmpPackageItemInfos.values()) {
             mIconCache.getTitleAndIconForApp(p, true /* userLowResIcon */);
-            p.titleSectionName = mIndexer.computeSectionName(p.title);
         }
-
-        // sort the package entries.
-        Collections.sort(mPackageItemInfos, mAppNameComparator);
-    }
-
-    /**
-     * Create a snapshot of the widgets model.
-     * <p>
-     * Usage case: view binding without being modified from package updates.
-     */
-    @Override
-    public WidgetsModel clone(){
-        return new WidgetsModel(this);
     }
 }
\ No newline at end of file
diff --git a/src/com/android/launcher3/util/LabelComparator.java b/src/com/android/launcher3/util/LabelComparator.java
new file mode 100644
index 000000000..5da9ddfda
--- /dev/null
+++ b/src/com/android/launcher3/util/LabelComparator.java
@@ -0,0 +1,46 @@
+/*
+ * Copyright (C) 2016 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.util;
+
+import java.text.Collator;
+import java.util.Comparator;
+
+/**
+ * Extension of {@link java.text.Collator} with special handling for digits. Used for comparing
+ * user visible labels.
+ */
+public class LabelComparator implements Comparator<String> {
+
+    private final Collator mCollator = Collator.getInstance();
+
+    @Override
+    public int compare(String titleA, String titleB) {
+        // Ensure that we de-prioritize any titles that don't start with a
+        // linguistic letter or digit
+        boolean aStartsWithLetter = (titleA.length() > 0) &&
+                Character.isLetterOrDigit(titleA.codePointAt(0));
+        boolean bStartsWithLetter = (titleB.length() > 0) &&
+                Character.isLetterOrDigit(titleB.codePointAt(0));
+        if (aStartsWithLetter && !bStartsWithLetter) {
+            return -1;
+        } else if (!aStartsWithLetter && bStartsWithLetter) {
+            return 1;
+        }
+
+        // Order by the title in the current locale
+        return mCollator.compare(titleA, titleB);
+    }
+}
diff --git a/src/com/android/launcher3/widget/WidgetItemComparator.java b/src/com/android/launcher3/widget/WidgetItemComparator.java
new file mode 100644
index 000000000..b5aaeb9fe
--- /dev/null
+++ b/src/com/android/launcher3/widget/WidgetItemComparator.java
@@ -0,0 +1,55 @@
+/*
+ * Copyright (C) 2016 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.widget;
+
+import com.android.launcher3.compat.UserHandleCompat;
+import com.android.launcher3.model.WidgetItem;
+
+import java.text.Collator;
+import java.util.Comparator;
+
+/**
+ * Comparator for sorting WidgetItem based on their user, title and size.
+ */
+public class WidgetItemComparator implements Comparator<WidgetItem> {
+
+    private final UserHandleCompat mMyUserHandle = UserHandleCompat.myUserHandle();
+    private final Collator mCollator = Collator.getInstance();
+
+    @Override
+    public int compare(WidgetItem a, WidgetItem b) {
+        // Independent of how the labels compare, if only one of the two widget info belongs to
+        // work profile, put that one in the back.
+        boolean thisWorkProfile = !mMyUserHandle.equals(a.user);
+        boolean otherWorkProfile = !mMyUserHandle.equals(b.user);
+        if (thisWorkProfile ^ otherWorkProfile) {
+            return thisWorkProfile ? 1 : -1;
+        }
+
+        int labelCompare = mCollator.compare(a.label, b.label);
+        if (labelCompare != 0) {
+            return labelCompare;
+        }
+
+        // If the label is same, put the smaller widget before the larger widget. If the area is
+        // also same, put the widget with smaller height before.
+        int thisArea = a.spanX * a.spanY;
+        int otherArea = b.spanX * b.spanY;
+        return thisArea == otherArea
+                ? Integer.compare(a.spanY, b.spanY)
+                : Integer.compare(thisArea, otherArea);
+    }
+}
diff --git a/src/com/android/launcher3/widget/WidgetListRowEntry.java b/src/com/android/launcher3/widget/WidgetListRowEntry.java
new file mode 100644
index 000000000..3e89eeb9b
--- /dev/null
+++ b/src/com/android/launcher3/widget/WidgetListRowEntry.java
@@ -0,0 +1,44 @@
+/*
+ * Copyright (C) 2016 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.widget;
+
+import com.android.launcher3.ItemInfo;
+import com.android.launcher3.model.PackageItemInfo;
+import com.android.launcher3.model.WidgetItem;
+
+import java.util.ArrayList;
+
+/**
+ * Holder class to store all the information related to a single row in the widget list
+ */
+public class WidgetListRowEntry {
+
+    public final PackageItemInfo pkgItem;
+
+    public final ArrayList<WidgetItem> widgets;
+
+    /**
+     * Character that is used as a section name for the {@link ItemInfo#title}.
+     * (e.g., "G" will be stored if title is "Google")
+     */
+    public String titleSectionName;
+
+    public WidgetListRowEntry(PackageItemInfo pkgItem, ArrayList<WidgetItem> items) {
+        this.pkgItem = pkgItem;
+        this.widgets = items;
+    }
+
+}
diff --git a/src/com/android/launcher3/widget/WidgetsContainerView.java b/src/com/android/launcher3/widget/WidgetsContainerView.java
index 56702cc25..2e1294251 100644
--- a/src/com/android/launcher3/widget/WidgetsContainerView.java
+++ b/src/com/android/launcher3/widget/WidgetsContainerView.java
@@ -43,9 +43,12 @@ import com.android.launcher3.Utilities;
 import com.android.launcher3.WidgetPreviewLoader;
 import com.android.launcher3.dragndrop.DragController;
 import com.android.launcher3.graphics.LauncherIcons;
+import com.android.launcher3.model.PackageItemInfo;
+import com.android.launcher3.model.WidgetItem;
 import com.android.launcher3.model.WidgetsModel;
 import com.android.launcher3.userevent.nano.LauncherLogProto;
 import com.android.launcher3.userevent.nano.LauncherLogProto.Target;
+import com.android.launcher3.util.MultiHashMap;
 import com.android.launcher3.util.Thunk;
 
 /**
@@ -297,9 +300,8 @@ public class WidgetsContainerView extends BaseContainerView
     /**
      * Initialize the widget data model.
      */
-    public void addWidgets(WidgetsModel model) {
-        mRecyclerView.setWidgets(model);
-        mAdapter.setWidgetsModel(model);
+    public void setWidgets(MultiHashMap<PackageItemInfo, WidgetItem> model) {
+        mAdapter.setWidgets(model);
         mAdapter.notifyDataSetChanged();
 
         View loader = getContentView().findViewById(R.id.loader);
diff --git a/src/com/android/launcher3/widget/WidgetsListAdapter.java b/src/com/android/launcher3/widget/WidgetsListAdapter.java
index ed0870811..a5846ec33 100644
--- a/src/com/android/launcher3/widget/WidgetsListAdapter.java
+++ b/src/com/android/launcher3/widget/WidgetsListAdapter.java
@@ -31,10 +31,17 @@ import com.android.launcher3.LauncherAppState;
 import com.android.launcher3.R;
 import com.android.launcher3.Utilities;
 import com.android.launcher3.WidgetPreviewLoader;
+import com.android.launcher3.compat.AlphabeticIndexCompat;
+import com.android.launcher3.model.PackageItemInfo;
 import com.android.launcher3.model.WidgetItem;
-import com.android.launcher3.model.WidgetsModel;
+import com.android.launcher3.util.LabelComparator;
+import com.android.launcher3.util.MultiHashMap;
 
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
 import java.util.List;
+import java.util.Map;
 
 /**
  * List view adapter for the widget tray.
@@ -55,7 +62,8 @@ public class WidgetsListAdapter extends Adapter<WidgetsRowViewHolder> {
     private final View.OnClickListener mIconClickListener;
     private final View.OnLongClickListener mIconLongClickListener;
 
-    private WidgetsModel mWidgetsModel;
+    private final ArrayList<WidgetListRowEntry> mEntries = new ArrayList<>();
+    private final AlphabeticIndexCompat mIndexer;
 
     private final int mIndent;
 
@@ -65,26 +73,40 @@ public class WidgetsListAdapter extends Adapter<WidgetsRowViewHolder> {
         mLayoutInflater = LayoutInflater.from(context);
         mWidgetPreviewLoader = LauncherAppState.getInstance().getWidgetCache();
 
+        mIndexer = new AlphabeticIndexCompat(context);
+
         mIconClickListener = iconClickListener;
         mIconLongClickListener = iconLongClickListener;
         mIndent = context.getResources().getDimensionPixelSize(R.dimen.widget_section_indent);
     }
 
-    public void setWidgetsModel(WidgetsModel w) {
-        mWidgetsModel = w;
+    public void setWidgets(MultiHashMap<PackageItemInfo, WidgetItem> widgets) {
+        mEntries.clear();
+        WidgetItemComparator widgetComparator = new WidgetItemComparator();
+
+        for (Map.Entry<PackageItemInfo, ArrayList<WidgetItem>> entry : widgets.entrySet()) {
+            WidgetListRowEntry row = new WidgetListRowEntry(entry.getKey(), entry.getValue());
+            row.titleSectionName = mIndexer.computeSectionName(row.pkgItem.title);
+            Collections.sort(row.widgets, widgetComparator);
+            mEntries.add(row);
+        }
+
+        Collections.sort(mEntries, new WidgetListRowEntryComparator());
     }
 
     @Override
     public int getItemCount() {
-        if (mWidgetsModel == null) {
-            return 0;
-        }
-        return mWidgetsModel.getPackageSize();
+        return mEntries.size();
+    }
+
+    public String getSectionName(int pos) {
+        return mEntries.get(pos).titleSectionName;
     }
 
     @Override
     public void onBindViewHolder(WidgetsRowViewHolder holder, int pos) {
-        List<WidgetItem> infoList = mWidgetsModel.getSortedWidgets(pos);
+        WidgetListRowEntry entry = mEntries.get(pos);
+        List<WidgetItem> infoList = entry.widgets;
 
         ViewGroup row = holder.cellContainer;
         if (DEBUG) {
@@ -119,7 +141,7 @@ public class WidgetsListAdapter extends Adapter<WidgetsRowViewHolder> {
         }
 
         // Bind the views in the application info section.
-        holder.title.applyFromPackageItemInfo(mWidgetsModel.getPackageItemInfo(pos));
+        holder.title.applyFromPackageItemInfo(entry.pkgItem);
 
         // Bind the view in the widget horizontal tray region.
         for (int i=0; i < infoList.size(); i++) {
@@ -173,4 +195,18 @@ public class WidgetsListAdapter extends Adapter<WidgetsRowViewHolder> {
     public long getItemId(int pos) {
         return pos;
     }
+
+    /**
+     * Comparator for sorting WidgetListRowEntry based on package title
+     */
+    public static class WidgetListRowEntryComparator implements Comparator<WidgetListRowEntry> {
+
+        private final LabelComparator mComparator = new LabelComparator();
+
+        @Override
+        public int compare(WidgetListRowEntry a, WidgetListRowEntry b) {
+            return mComparator.compare(a.pkgItem.title.toString(), b.pkgItem.title.toString());
+        }
+    }
+
 }
diff --git a/src/com/android/launcher3/widget/WidgetsRecyclerView.java b/src/com/android/launcher3/widget/WidgetsRecyclerView.java
index 4b23ae088..e0a80c679 100644
--- a/src/com/android/launcher3/widget/WidgetsRecyclerView.java
+++ b/src/com/android/launcher3/widget/WidgetsRecyclerView.java
@@ -31,7 +31,7 @@ import com.android.launcher3.model.WidgetsModel;
 public class WidgetsRecyclerView extends BaseRecyclerView {
 
     private static final String TAG = "WidgetsRecyclerView";
-    private WidgetsModel mWidgets;
+    private WidgetsListAdapter mAdapter;
 
     public WidgetsRecyclerView(Context context) {
         this(context, null);
@@ -64,11 +64,10 @@ public class WidgetsRecyclerView extends BaseRecyclerView {
         return Color.WHITE;
     }
 
-    /**
-     * Sets the widget model in this view, used to determine the fast scroll position.
-     */
-    public void setWidgets(WidgetsModel widgets) {
-        mWidgets = widgets;
+    @Override
+    public void setAdapter(Adapter adapter) {
+        super.setAdapter(adapter);
+        mAdapter = (WidgetsListAdapter) adapter;
     }
 
     /**
@@ -84,15 +83,14 @@ public class WidgetsRecyclerView extends BaseRecyclerView {
         // Stop the scroller if it is scrolling
         stopScroll();
 
-        int rowCount = mWidgets.getPackageSize();
+        int rowCount = mAdapter.getItemCount();
         float pos = rowCount * touchFraction;
         int availableScrollHeight = getAvailableScrollHeight();
         LinearLayoutManager layoutManager = ((LinearLayoutManager) getLayoutManager());
         layoutManager.scrollToPositionWithOffset(0, (int) -(availableScrollHeight * touchFraction));
 
         int posInt = (int) ((touchFraction == 1)? pos -1 : pos);
-        PackageItemInfo p = mWidgets.getPackageItemInfo(posInt);
-        return p.titleSectionName;
+        return mAdapter.getSectionName(posInt);
     }
 
     /**
@@ -137,13 +135,13 @@ public class WidgetsRecyclerView extends BaseRecyclerView {
     @Override
     protected int getAvailableScrollHeight() {
         View child = getChildAt(0);
-        int height = child.getMeasuredHeight() * mWidgets.getPackageSize();
+        int height = child.getMeasuredHeight() * mAdapter.getItemCount();
         int totalHeight = getPaddingTop() + height + getPaddingBottom();
         int availableScrollHeight = totalHeight - getScrollbarTrackHeight();
         return availableScrollHeight;
     }
 
     private boolean isModelNotReady() {
-        return mWidgets == null || mWidgets.getPackageSize() == 0;
+        return mAdapter.getItemCount() == 0;
     }
 }
\ No newline at end of file