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
diff --git a/src/com/android/launcher3/Launcher.java b/src/com/android/launcher3/Launcher.java
index 3149ce4..40820fa 100644
--- a/src/com/android/launcher3/Launcher.java
+++ b/src/com/android/launcher3/Launcher.java
@@ -103,7 +103,8 @@
 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 @@
 
     // 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 @@
         }
     }
 
-    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 caf8870..55bd0a4 100644
--- a/src/com/android/launcher3/LauncherModel.java
+++ b/src/com/android/launcher3/LauncherModel.java
@@ -61,7 +61,9 @@
 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 @@
                 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 @@
         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 @@
         }
     }
 
-    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 @@
             @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 5a28e5c..8b7a6ba 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.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 @@
     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 AlphabeticalAppsList(Context context) {
         mLauncher = Launcher.getLauncher(context);
         mIndexer = new AlphabeticIndexCompat(context);
-        mAppNameComparator = new AppNameComparator(context);
+        mAppNameComparator = new AppInfoComparator(context);
     }
 
     /**
@@ -305,17 +305,16 @@
         // 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 @@
             }
 
             // Add each of the section apps to the list in order
-            List<AppInfo> allApps = new ArrayList<>(mApps.size());
-            for (Map.Entry<String, ArrayList<AppInfo>> entry : sectionMap.entrySet()) {
-                allApps.addAll(entry.getValue());
-            }
-
             mApps.clear();
-            mApps.addAll(allApps);
+            for (Map.Entry<String, ArrayList<AppInfo>> entry : sectionMap.entrySet()) {
+                mApps.addAll(entry.getValue());
+            }
         } 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
similarity index 61%
rename from src/com/android/launcher3/model/AbstractUserComparator.java
rename to src/com/android/launcher3/allapps/AppInfoComparator.java
index bd28560..1f5fece 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 5f80037..0000000
--- 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 c86ba86..00470e1 100644
--- a/src/com/android/launcher3/model/PackageItemInfo.java
+++ b/src/com/android/launcher3/model/PackageItemInfo.java
@@ -40,12 +40,6 @@
      */
     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 b2a94bb..3953f39 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.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 @@
     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<>();
+        mWidgetsList = new MultiHashMap<>();
     }
 
-    @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);
-    }
-
-    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 @@
                 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 @@
 
         // 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 @@
 
             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 0000000..5da9ddf
--- /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 0000000..b5aaeb9
--- /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 0000000..3e89eeb
--- /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 56702cc..2e12942 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.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 @@
     /**
      * 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 ed08708..a5846ec 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.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 @@
     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 @@
         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 @@
         }
 
         // 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 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 4b23ae0..e0a80c6 100644
--- a/src/com/android/launcher3/widget/WidgetsRecyclerView.java
+++ b/src/com/android/launcher3/widget/WidgetsRecyclerView.java
@@ -31,7 +31,7 @@
 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 @@
         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 @@
         // 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 @@
     @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