Modify ExtensionSorting Ordinal Map

The ordinal map in ExtensionSorting has been modified to be more useful.
Instead of just saying how many apps are on each page, each page has a map
of all the app launch ordinals on it, with the extension_id as well. This will 
make it easy to quickly find conflicts where two icons have the same page and
app launch ordinal.

BUG=61447
TEST=


Review URL: http://codereview.chromium.org/9215001

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@117856 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 177 insertions, 58 deletions

diff --git a/chrome/browser/extensions/extension_sorting.cc b/chrome/browser/extensions/extension_sorting.cc
index dc2851b..5ae1aa3 100644
--- a/chrome/browser/extensions/extension_sorting.cc
+++ b/chrome/browser/extensions/extension_sorting.cc
@@ -13,7 +13,7 @@ namespace {
 
 // The number of apps per page. This isn't a hard limit, but new apps installed
 // from the webstore will overflow onto a new page if this limit is reached.
-const int kNaturalAppPageSize = 18;
+const size_t kNaturalAppPageSize = 18;
 
 // A preference determining the order of which the apps appear on the NTP.
 const char kPrefAppLaunchIndexDeprecated[] = "app_launcher_index";
@@ -68,12 +68,13 @@ void ExtensionSorting::MigrateAppIndex(
       // to properly convert from integers and we are iterating though them in
       // no given order, we create earlier StringOrdinal values as required.
       // This should be filled in by the time we are done with this loop.
-      if (page_ordinal_map_.empty())
-        page_ordinal_map_[StringOrdinal::CreateInitialOrdinal()] = 0;
-      while (page_ordinal_map_.size() <= static_cast<size_t>(old_page_index)) {
+      if (ntp_ordinal_map_.empty())
+        ntp_ordinal_map_[StringOrdinal::CreateInitialOrdinal()];
+      while (ntp_ordinal_map_.size()
+             <= static_cast<size_t>(old_page_index)) {
         StringOrdinal earlier_page =
-            page_ordinal_map_.rbegin()->first.CreateAfter();
-        page_ordinal_map_[earlier_page] = 0;
+            ntp_ordinal_map_.rbegin()->first.CreateAfter();
+        ntp_ordinal_map_[earlier_page];
       }
 
       page = PageIntegerAsStringOrdinal(old_page_index);
@@ -103,12 +104,12 @@ void ExtensionSorting::MigrateAppIndex(
   // Remove any empty pages that may have been added. This shouldn't occur,
   // but double check here to prevent future problems with conversions between
   // integers and StringOrdinals.
-  for (PageOrdinalMap::iterator it = page_ordinal_map_.begin();
-       it != page_ordinal_map_.end();) {
-    if (it->second == 0) {
+  for (PageOrdinalMap::iterator it = ntp_ordinal_map_.begin();
+       it != ntp_ordinal_map_.end();) {
+    if (it->second.empty()) {
       PageOrdinalMap::iterator prev_it = it;
       ++it;
-      page_ordinal_map_.erase(prev_it);
+      ntp_ordinal_map_.erase(prev_it);
     } else {
       ++it;
     }
@@ -177,12 +178,18 @@ StringOrdinal ExtensionSorting::GetAppLaunchOrdinal(
   return StringOrdinal(raw_value);
 }
 
-void ExtensionSorting::SetAppLaunchOrdinal(const std::string& extension_id,
-                                         const StringOrdinal& ordinal) {
+void ExtensionSorting::SetAppLaunchOrdinal(
+    const std::string& extension_id,
+    const StringOrdinal& new_app_launch_ordinal) {
+  StringOrdinal page_ordinal = GetPageOrdinal(extension_id);
+  RemoveOrdinalMapping(
+      extension_id, page_ordinal, GetAppLaunchOrdinal(extension_id));
+  AddOrdinalMapping(extension_id, page_ordinal, new_app_launch_ordinal);
+
   extension_scoped_prefs_->UpdateExtensionPref(
       extension_id,
       kPrefAppLaunchOrdinal,
-      Value::CreateStringValue(ordinal.ToString()));
+      Value::CreateStringValue(new_app_launch_ordinal.ToString()));
 }
 
 StringOrdinal ExtensionSorting::CreateFirstAppLaunchOrdinal(
@@ -201,7 +208,7 @@ StringOrdinal ExtensionSorting::CreateNextAppLaunchOrdinal(
     const StringOrdinal& page_ordinal) const {
   const StringOrdinal& max_ordinal =
       GetMinOrMaxAppLaunchOrdinalsOnPage(page_ordinal,
-                                          ExtensionSorting::MAX_ORDINAL);
+                                         ExtensionSorting::MAX_ORDINAL);
 
   if (max_ordinal.IsValid())
     return max_ordinal.CreateAfter();
@@ -214,10 +221,10 @@ StringOrdinal ExtensionSorting::CreateFirstAppPageOrdinal() const {
           ExtensionPrefs::kExtensionsPref);
   CHECK(extensions);
 
-  if (page_ordinal_map_.empty())
+  if (ntp_ordinal_map_.empty())
     return StringOrdinal::CreateInitialOrdinal();
 
-  return page_ordinal_map_.begin()->first;
+  return ntp_ordinal_map_.begin()->first;
 }
 
 StringOrdinal ExtensionSorting::GetNaturalAppPageOrdinal() const {
@@ -225,17 +232,17 @@ StringOrdinal ExtensionSorting::GetNaturalAppPageOrdinal() const {
           ExtensionPrefs::kExtensionsPref);
   CHECK(extensions);
 
-  if (page_ordinal_map_.empty())
+  if (ntp_ordinal_map_.empty())
     return StringOrdinal::CreateInitialOrdinal();
 
-  for (PageOrdinalMap::const_iterator it = page_ordinal_map_.begin();
-       it != page_ordinal_map_.end(); ++it) {
-    if (it->second < kNaturalAppPageSize)
+  for (PageOrdinalMap::const_iterator it = ntp_ordinal_map_.begin();
+       it != ntp_ordinal_map_.end(); ++it) {
+    if (it->second.size() < kNaturalAppPageSize)
       return it->first;
   }
 
   // Add a new page as all existing pages are full.
-  StringOrdinal last_element = page_ordinal_map_.rbegin()->first;
+  StringOrdinal last_element = ntp_ordinal_map_.rbegin()->first;
   return last_element.CreateAfter();
 }
 
@@ -250,16 +257,23 @@ StringOrdinal ExtensionSorting::GetPageOrdinal(const std::string& extension_id)
 }
 
 void ExtensionSorting::SetPageOrdinal(const std::string& extension_id,
-                                    const StringOrdinal& page_ordinal) {
-  UpdatePageOrdinalMap(GetPageOrdinal(extension_id), page_ordinal);
+                                    const StringOrdinal& new_page_ordinal) {
+  StringOrdinal app_launch_ordinal = GetAppLaunchOrdinal(extension_id);
+  RemoveOrdinalMapping(
+      extension_id, GetPageOrdinal(extension_id), app_launch_ordinal);
+  AddOrdinalMapping(extension_id, new_page_ordinal, app_launch_ordinal);
+
   extension_scoped_prefs_->UpdateExtensionPref(
       extension_id,
       kPrefPageOrdinal,
-      Value::CreateStringValue(page_ordinal.ToString()));
+      Value::CreateStringValue(new_page_ordinal.ToString()));
 }
 
 void ExtensionSorting::ClearPageOrdinal(const std::string& extension_id) {
-  UpdatePageOrdinalMap(GetPageOrdinal(extension_id), StringOrdinal());
+  RemoveOrdinalMapping(extension_id,
+                       GetPageOrdinal(extension_id),
+                       GetAppLaunchOrdinal(extension_id));
+
   extension_scoped_prefs_->UpdateExtensionPref(
       extension_id, kPrefPageOrdinal, NULL);
 }
@@ -269,9 +283,9 @@ int ExtensionSorting::PageStringOrdinalAsInteger(
   if (!page_ordinal.IsValid())
     return -1;
 
-  PageOrdinalMap::const_iterator it = page_ordinal_map_.find(page_ordinal);
-  if (it != page_ordinal_map_.end()) {
-    return std::distance(page_ordinal_map_.begin(), it);
+  PageOrdinalMap::const_iterator it = ntp_ordinal_map_.find(page_ordinal);
+  if (it != ntp_ordinal_map_.end()) {
+    return std::distance(ntp_ordinal_map_.begin(), it);
   } else {
     return -1;
   }
@@ -281,24 +295,24 @@ StringOrdinal ExtensionSorting::PageIntegerAsStringOrdinal(size_t page_index)
     const {
   // We shouldn't have a page_index that is more than 1 position away from the
   // current end.
-  CHECK_LE(page_index, page_ordinal_map_.size());
+  CHECK_LE(page_index, ntp_ordinal_map_.size());
 
   const DictionaryValue* extensions = pref_service_->GetDictionary(
           ExtensionPrefs::kExtensionsPref);
   if (!extensions)
     return StringOrdinal();
 
-  if (page_index < page_ordinal_map_.size()) {
-    PageOrdinalMap::const_iterator it = page_ordinal_map_.begin();
+  if (page_index < ntp_ordinal_map_.size()) {
+    PageOrdinalMap::const_iterator it = ntp_ordinal_map_.begin();
     std::advance(it, page_index);
 
     return it->first;
 
   } else {
-    if (page_ordinal_map_.empty())
+    if (ntp_ordinal_map_.empty())
       return StringOrdinal::CreateInitialOrdinal();
     else
-      return page_ordinal_map_.rbegin()->first.CreateAfter();
+      return ntp_ordinal_map_.rbegin()->first.CreateAfter();
   }
 }
 
@@ -336,7 +350,9 @@ void ExtensionSorting::InitializePageOrdinalMap(
     const ExtensionPrefs::ExtensionIdSet& extension_ids) {
   for (ExtensionPrefs::ExtensionIdSet::const_iterator ext_it =
            extension_ids.begin(); ext_it != extension_ids.end(); ++ext_it) {
-    UpdatePageOrdinalMap(StringOrdinal(), GetPageOrdinal(*ext_it));
+    AddOrdinalMapping(*ext_it,
+                      GetPageOrdinal(*ext_it),
+                      GetAppLaunchOrdinal(*ext_it));
 
     // Ensure that the web store app still isn't found in this list, since
     // it is added after this loop.
@@ -346,15 +362,43 @@ void ExtensionSorting::InitializePageOrdinalMap(
   // Include the Web Store App since it is displayed on the NTP.
   StringOrdinal web_store_app_page =
       GetPageOrdinal(extension_misc::kWebStoreAppId);
-  if (web_store_app_page.IsValid())
-    UpdatePageOrdinalMap(StringOrdinal(), web_store_app_page);
+  if (web_store_app_page.IsValid()) {
+    AddOrdinalMapping(extension_misc::kWebStoreAppId,
+                      web_store_app_page,
+                      GetAppLaunchOrdinal(extension_misc::kWebStoreAppId));
+  }
 }
 
-void ExtensionSorting::UpdatePageOrdinalMap(const StringOrdinal& old_value,
-                                            const StringOrdinal& new_value) {
-  if (new_value.IsValid())
-    ++page_ordinal_map_[new_value];
+void ExtensionSorting::AddOrdinalMapping(
+    const std::string& extension_id,
+    const StringOrdinal& page_ordinal,
+    const StringOrdinal& app_launch_ordinal) {
+  if (!page_ordinal.IsValid() || !app_launch_ordinal.IsValid())
+    return;
+
+  ntp_ordinal_map_[page_ordinal].insert(
+      std::make_pair(app_launch_ordinal, extension_id));
+}
 
-  if (old_value.IsValid())
-    --page_ordinal_map_[old_value];
+void ExtensionSorting::RemoveOrdinalMapping(
+    const std::string& extension_id,
+    const StringOrdinal& page_ordinal,
+    const StringOrdinal& app_launch_ordinal) {
+  if (!page_ordinal.IsValid() || !app_launch_ordinal.IsValid())
+    return;
+
+  // Check that the page exists using find to prevent creating a new page
+  // if |page_ordinal| isn't a used page.
+  PageOrdinalMap::iterator page_map = ntp_ordinal_map_.find(page_ordinal);
+  if (page_map == ntp_ordinal_map_.end())
+    return;
+
+  for (AppLaunchOrdinalMap::iterator it =
+           page_map->second.find(app_launch_ordinal);
+       it != page_map->second.end(); ++it) {
+    if (it->second == extension_id) {
+      page_map->second.erase(it);
+      break;
+    }
+  }
 }
diff --git a/chrome/browser/extensions/extension_sorting.h b/chrome/browser/extensions/extension_sorting.h
index 0a7e397..098d10f 100644
--- a/chrome/browser/extensions/extension_sorting.h
+++ b/chrome/browser/extensions/extension_sorting.h
@@ -41,7 +41,7 @@ class ExtensionSorting {
 
   // Sets a specific launch ordinal for an app with |extension_id|.
   void SetAppLaunchOrdinal(const std::string& extension_id,
-                           const StringOrdinal& ordinal);
+                           const StringOrdinal& new_app_launch_ordinal);
 
   // Returns a StringOrdinal that is lower than any app launch ordinal for the
   // given page.
@@ -68,7 +68,7 @@ class ExtensionSorting {
 
   // Sets a specific page ordinal for an app with |extension_id|.
   void SetPageOrdinal(const std::string& extension_id,
-                      const StringOrdinal& ordinal);
+                      const StringOrdinal& new_page_ordinal);
 
   // Removes the page ordinal for an app.
   void ClearPageOrdinal(const std::string& extension_id);
@@ -82,8 +82,9 @@ class ExtensionSorting {
   StringOrdinal PageIntegerAsStringOrdinal(size_t page_index) const;
 
  private:
+  // Unit tests.
   friend class ExtensionSortingGetMinOrMaxAppLaunchOrdinalsOnPage;
-    // Unit test.
+  friend class ExtensionSortingPageOrdinalMapping;
 
   // An enum used by GetMinOrMaxAppLaunchOrdinalsOnPage to specify which
   // value should be returned.
@@ -103,23 +104,38 @@ class ExtensionSorting {
   void InitializePageOrdinalMap(
       const ExtensionPrefs::ExtensionIdSet& extension_ids);
 
-  // Called when an application changes the value of its page ordinal so that
-  // |page_ordinal_map_| is aware that |old_value| page ordinal has been
-  // replace by the |new_value| page ordinal and adjusts its mapping
-  // accordingly. This works with valid and invalid StringOrdinals.
-  void UpdatePageOrdinalMap(const StringOrdinal& old_value,
-                            const StringOrdinal& new_value);
+  // Called to add a new mapping value for |extension_id| with a page ordinal
+  // of |page_ordinal| and a app launch ordinal of |app_launch_ordinal|. This
+  // works with valid and invalid StringOrdinals.
+  void AddOrdinalMapping(const std::string& extension_id,
+                         const StringOrdinal& page_ordinal,
+                         const StringOrdinal& app_launch_ordinal);
+
+  // Removes the mapping for |extension_id| with a page ordinal of
+  // |page_ordinal| and a app launch ordinal of |app_launch_ordinal|. If there
+  // is not matching map, nothing happens. This works with valid and invalid
+  // StringOrdinals.
+  void RemoveOrdinalMapping(const std::string& extension_id,
+                            const StringOrdinal& page_ordinal,
+                            const StringOrdinal& app_launch_ordinal);
 
   ExtensionScopedPrefs* extension_scoped_prefs_;  // Weak, owns this instance.
   PrefService* pref_service_;  // Weak.
 
-  // A map of all the StringOrdinal page indices mapping to how often they are
-  // used, this is used for mapping the StringOrdinals to their integer
-  // equivalent as well as quick lookup of the sorted StringOrdinals.
-  // TODO(csharp) Convert this to a two-layer map to allow page ordinal lookup
-  // by id and vice versa.
-  typedef std::map<StringOrdinal, int, StringOrdinalLessThan> PageOrdinalMap;
-  PageOrdinalMap page_ordinal_map_;
+  // A map of all the StringOrdinal page ordinals mapping to the collections of
+  // app launch ordinals that exist on that page. This is used for mapping
+  // StringOrdinals to their Integer equivalent as well as quick lookup of the
+  // any collision of on the NTP (icons with the same page and same app launch
+  // ordinal).
+  // The StringOrdinal is the app launch ordinal and the string is the extension
+  // id.
+  typedef std::multimap<
+      StringOrdinal, std::string, StringOrdinalLessThan> AppLaunchOrdinalMap;
+  // The StringOrdinal is the page ordinal and the AppLaunchOrdinalMap is the
+  // contents of that page.
+  typedef std::map<
+      StringOrdinal, AppLaunchOrdinalMap, StringOrdinalLessThan> PageOrdinalMap;
+  PageOrdinalMap ntp_ordinal_map_;
 
   DISALLOW_COPY_AND_ASSIGN(ExtensionSorting);
 };
diff --git a/chrome/browser/extensions/extension_sorting_unittest.cc b/chrome/browser/extensions/extension_sorting_unittest.cc
index 6aa5764..568bc49 100644
--- a/chrome/browser/extensions/extension_sorting_unittest.cc
+++ b/chrome/browser/extensions/extension_sorting_unittest.cc
@@ -237,6 +237,65 @@ class ExtensionSortingMigrateAppIndexInvalid
 TEST_F(ExtensionSortingMigrateAppIndexInvalid,
        ExtensionSortingMigrateAppIndexInvalid) {}
 
+class ExtensionSortingPageOrdinalMapping :
+    public ExtensionPrefsPrepopulatedTest {
+ public:
+  ExtensionSortingPageOrdinalMapping() {}
+  virtual ~ExtensionSortingPageOrdinalMapping() {}
+  virtual void Initialize() {}
+
+  virtual void Verify() {
+    std::string ext_1 = "ext_1";
+    std::string ext_2 = "ext_2";
+
+    ExtensionSorting* extension_sorting = prefs()->extension_sorting();
+    StringOrdinal first_ordinal = StringOrdinal::CreateInitialOrdinal();
+
+    // Ensure attempting to removing a mapping with an invalid page doesn't
+    // modify the map.
+    EXPECT_TRUE(extension_sorting->ntp_ordinal_map_.empty());
+    extension_sorting->RemoveOrdinalMapping(
+        ext_1, first_ordinal, first_ordinal);
+    EXPECT_TRUE(extension_sorting->ntp_ordinal_map_.empty());
+
+    // Add new mappings.
+    extension_sorting->AddOrdinalMapping(ext_1, first_ordinal, first_ordinal);
+    extension_sorting->AddOrdinalMapping(ext_2, first_ordinal, first_ordinal);
+
+    EXPECT_EQ(1U, extension_sorting->ntp_ordinal_map_.size());
+    EXPECT_EQ(2U, extension_sorting->ntp_ordinal_map_[first_ordinal].size());
+
+    ExtensionSorting::AppLaunchOrdinalMap::iterator it =
+        extension_sorting->ntp_ordinal_map_[first_ordinal].find(first_ordinal);
+    EXPECT_EQ(ext_1, it->second);
+    ++it;
+    EXPECT_EQ(ext_2, it->second);
+
+    extension_sorting->RemoveOrdinalMapping(ext_1,
+                                            first_ordinal,
+                                            first_ordinal);
+    EXPECT_EQ(1U, extension_sorting->ntp_ordinal_map_.size());
+    EXPECT_EQ(1U, extension_sorting->ntp_ordinal_map_[first_ordinal].size());
+
+    it = extension_sorting->ntp_ordinal_map_[first_ordinal].find(
+        first_ordinal);
+    EXPECT_EQ(ext_2, it->second);
+
+    // Ensure that attempting to remove an extension with a valid page and app
+    // launch ordinals, but a unused id has no effect.
+    extension_sorting->RemoveOrdinalMapping(
+        "invalid_ext", first_ordinal, first_ordinal);
+    EXPECT_EQ(1U, extension_sorting->ntp_ordinal_map_.size());
+    EXPECT_EQ(1U, extension_sorting->ntp_ordinal_map_[first_ordinal].size());
+
+    it = extension_sorting->ntp_ordinal_map_[first_ordinal].find(
+        first_ordinal);
+    EXPECT_EQ(ext_2, it->second);
+  }
+};
+TEST_F(ExtensionSortingPageOrdinalMapping,
+       ExtensionSortingPageOrdinalMapping) {}
+
 class ExtensionSortingPreinstalledAppsBase :
     public ExtensionPrefsPrepopulatedTest {
  public: