1// Copyright 2013 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "chrome/browser/extensions/chrome_app_sorting.h"
6
7#include <algorithm>
8#include <vector>
9
10#include "chrome/browser/chrome_notification_types.h"
11#include "chrome/browser/extensions/extension_sync_service.h"
12#include "chrome/common/extensions/extension_constants.h"
13#include "content/public/browser/notification_service.h"
14#include "extensions/browser/extension_scoped_prefs.h"
15#include "extensions/common/constants.h"
16#include "extensions/common/extension.h"
17
18#if defined(OS_CHROMEOS)
19#include "chrome/browser/chromeos/extensions/default_app_order.h"
20#endif
21
22namespace extensions {
23
24namespace {
25
26// The number of apps per page. This isn't a hard limit, but new apps installed
27// from the webstore will overflow onto a new page if this limit is reached.
28const size_t kNaturalAppPageSize = 18;
29
30// A preference determining the order of which the apps appear on the NTP.
31const char kPrefAppLaunchIndexDeprecated[] = "app_launcher_index";
32const char kPrefAppLaunchOrdinal[] = "app_launcher_ordinal";
33
34// A preference determining the page on which an app appears in the NTP.
35const char kPrefPageIndexDeprecated[] = "page_index";
36const char kPrefPageOrdinal[] = "page_ordinal";
37
38}  // namespace
39
40////////////////////////////////////////////////////////////////////////////////
41// ChromeAppSorting::AppOrdinals
42
43ChromeAppSorting::AppOrdinals::AppOrdinals() {}
44
45ChromeAppSorting::AppOrdinals::~AppOrdinals() {}
46
47////////////////////////////////////////////////////////////////////////////////
48// ChromeAppSorting
49
50ChromeAppSorting::ChromeAppSorting()
51    : extension_scoped_prefs_(NULL),
52      extension_sync_service_(NULL),
53      default_ordinals_created_(false) {
54}
55
56ChromeAppSorting::~ChromeAppSorting() {
57}
58
59void ChromeAppSorting::SetExtensionScopedPrefs(ExtensionScopedPrefs* prefs) {
60  extension_scoped_prefs_ = prefs;
61}
62
63void ChromeAppSorting::SetExtensionSyncService(
64    ExtensionSyncService* extension_sync_service) {
65  extension_sync_service_ = extension_sync_service;
66}
67
68void ChromeAppSorting::Initialize(
69    const extensions::ExtensionIdList& extension_ids) {
70  InitializePageOrdinalMap(extension_ids);
71
72  MigrateAppIndex(extension_ids);
73}
74
75void ChromeAppSorting::CreateOrdinalsIfNecessary(size_t minimum_size) {
76  // Create StringOrdinal values as required to ensure |ntp_ordinal_map_| has at
77  // least |minimum_size| entries.
78  if (ntp_ordinal_map_.empty() && minimum_size > 0)
79    ntp_ordinal_map_[syncer::StringOrdinal::CreateInitialOrdinal()];
80
81  while (ntp_ordinal_map_.size() < minimum_size) {
82    syncer::StringOrdinal filler =
83        ntp_ordinal_map_.rbegin()->first.CreateAfter();
84    AppLaunchOrdinalMap empty_ordinal_map;
85    ntp_ordinal_map_.insert(std::make_pair(filler, empty_ordinal_map));
86  }
87}
88
89void ChromeAppSorting::MigrateAppIndex(
90    const extensions::ExtensionIdList& extension_ids) {
91  if (extension_ids.empty())
92    return;
93
94  // Convert all the page index values to page ordinals. If there are any
95  // app launch values that need to be migrated, inserted them into a sorted
96  // set to be dealt with later.
97  typedef std::map<syncer::StringOrdinal, std::map<int, const std::string*>,
98                   syncer::StringOrdinal::LessThanFn> AppPositionToIdMapping;
99  AppPositionToIdMapping app_launches_to_convert;
100  for (extensions::ExtensionIdList::const_iterator ext_id =
101           extension_ids.begin(); ext_id != extension_ids.end(); ++ext_id) {
102    int old_page_index = 0;
103    syncer::StringOrdinal page = GetPageOrdinal(*ext_id);
104    if (extension_scoped_prefs_->ReadPrefAsInteger(
105            *ext_id,
106            kPrefPageIndexDeprecated,
107            &old_page_index)) {
108      // Some extensions have invalid page index, so we don't
109      // attempt to convert them.
110      if (old_page_index < 0) {
111        DLOG(WARNING) << "Extension " << *ext_id
112                      << " has an invalid page index " << old_page_index
113                      << ". Aborting attempt to convert its index.";
114        break;
115      }
116
117      CreateOrdinalsIfNecessary(static_cast<size_t>(old_page_index) + 1);
118
119      page = PageIntegerAsStringOrdinal(old_page_index);
120      SetPageOrdinal(*ext_id, page);
121      extension_scoped_prefs_->UpdateExtensionPref(
122          *ext_id, kPrefPageIndexDeprecated, NULL);
123    }
124
125    int old_app_launch_index = 0;
126    if (extension_scoped_prefs_->ReadPrefAsInteger(
127            *ext_id,
128            kPrefAppLaunchIndexDeprecated,
129            &old_app_launch_index)) {
130      // We can't update the app launch index value yet, because we use
131      // GetNextAppLaunchOrdinal to get the new ordinal value and it requires
132      // all the ordinals with lower values to have already been migrated.
133      // A valid page ordinal is also required because otherwise there is
134      // no page to add the app to.
135      if (page.IsValid())
136        app_launches_to_convert[page][old_app_launch_index] = &*ext_id;
137
138      extension_scoped_prefs_->UpdateExtensionPref(
139          *ext_id, kPrefAppLaunchIndexDeprecated, NULL);
140    }
141  }
142
143  // Remove any empty pages that may have been added. This shouldn't occur,
144  // but double check here to prevent future problems with conversions between
145  // integers and StringOrdinals.
146  for (PageOrdinalMap::iterator it = ntp_ordinal_map_.begin();
147       it != ntp_ordinal_map_.end();) {
148    if (it->second.empty()) {
149      PageOrdinalMap::iterator prev_it = it;
150      ++it;
151      ntp_ordinal_map_.erase(prev_it);
152    } else {
153      ++it;
154    }
155  }
156
157  if (app_launches_to_convert.empty())
158    return;
159
160  // Create the new app launch ordinals and remove the old preferences. Since
161  // the set is sorted, each time we migrate an apps index, we know that all of
162  // the remaining apps will appear further down the NTP than it or on a
163  // different page.
164  for (AppPositionToIdMapping::const_iterator page_it =
165           app_launches_to_convert.begin();
166       page_it != app_launches_to_convert.end(); ++page_it) {
167    syncer::StringOrdinal page = page_it->first;
168    for (std::map<int, const std::string*>::const_iterator launch_it =
169            page_it->second.begin(); launch_it != page_it->second.end();
170        ++launch_it) {
171      SetAppLaunchOrdinal(*(launch_it->second),
172                          CreateNextAppLaunchOrdinal(page));
173    }
174  }
175}
176
177void ChromeAppSorting::FixNTPOrdinalCollisions() {
178  for (PageOrdinalMap::iterator page_it = ntp_ordinal_map_.begin();
179       page_it != ntp_ordinal_map_.end(); ++page_it) {
180    AppLaunchOrdinalMap& page = page_it->second;
181
182    AppLaunchOrdinalMap::iterator app_launch_it = page.begin();
183    while (app_launch_it != page.end()) {
184      int app_count = page.count(app_launch_it->first);
185      if (app_count == 1) {
186        ++app_launch_it;
187        continue;
188      }
189
190      syncer::StringOrdinal repeated_ordinal = app_launch_it->first;
191
192      // Sort the conflicting keys by their extension id, this is how
193      // the order is decided.
194      std::vector<std::string> conflicting_ids;
195      for (int i = 0; i < app_count; ++i, ++app_launch_it)
196        conflicting_ids.push_back(app_launch_it->second);
197      std::sort(conflicting_ids.begin(), conflicting_ids.end());
198
199      syncer::StringOrdinal upper_bound_ordinal = app_launch_it == page.end() ?
200          syncer::StringOrdinal() :
201          app_launch_it->first;
202      syncer::StringOrdinal lower_bound_ordinal = repeated_ordinal;
203
204      // Start at position 1 because the first extension can keep the conflicted
205      // value.
206      for (int i = 1; i < app_count; ++i) {
207        syncer::StringOrdinal unique_app_launch;
208        if (upper_bound_ordinal.IsValid()) {
209          unique_app_launch =
210              lower_bound_ordinal.CreateBetween(upper_bound_ordinal);
211        } else {
212          unique_app_launch = lower_bound_ordinal.CreateAfter();
213        }
214
215        SetAppLaunchOrdinal(conflicting_ids[i], unique_app_launch);
216        lower_bound_ordinal = unique_app_launch;
217      }
218    }
219  }
220
221  content::NotificationService::current()->Notify(
222      chrome::NOTIFICATION_APP_LAUNCHER_REORDERED,
223      content::Source<ChromeAppSorting>(this),
224      content::NotificationService::NoDetails());
225}
226
227void ChromeAppSorting::EnsureValidOrdinals(
228    const std::string& extension_id,
229    const syncer::StringOrdinal& suggested_page) {
230  syncer::StringOrdinal page_ordinal = GetPageOrdinal(extension_id);
231  if (!page_ordinal.IsValid()) {
232    if (suggested_page.IsValid()) {
233      page_ordinal = suggested_page;
234    } else if (!GetDefaultOrdinals(extension_id, &page_ordinal, NULL) ||
235        !page_ordinal.IsValid()) {
236      page_ordinal = GetNaturalAppPageOrdinal();
237    }
238
239    SetPageOrdinal(extension_id, page_ordinal);
240  }
241
242  syncer::StringOrdinal app_launch_ordinal = GetAppLaunchOrdinal(extension_id);
243  if (!app_launch_ordinal.IsValid()) {
244    // If using default app launcher ordinal, make sure there is no collision.
245    if (GetDefaultOrdinals(extension_id, NULL, &app_launch_ordinal) &&
246        app_launch_ordinal.IsValid())
247      app_launch_ordinal = ResolveCollision(page_ordinal, app_launch_ordinal);
248    else
249      app_launch_ordinal = CreateNextAppLaunchOrdinal(page_ordinal);
250
251    SetAppLaunchOrdinal(extension_id, app_launch_ordinal);
252  }
253}
254
255void ChromeAppSorting::OnExtensionMoved(
256    const std::string& moved_extension_id,
257    const std::string& predecessor_extension_id,
258    const std::string& successor_extension_id) {
259  // We only need to change the StringOrdinal if there are neighbours.
260  if (!predecessor_extension_id.empty() || !successor_extension_id.empty()) {
261    if (predecessor_extension_id.empty()) {
262      // Only a successor.
263      SetAppLaunchOrdinal(
264          moved_extension_id,
265          GetAppLaunchOrdinal(successor_extension_id).CreateBefore());
266    } else if (successor_extension_id.empty()) {
267      // Only a predecessor.
268      SetAppLaunchOrdinal(
269          moved_extension_id,
270          GetAppLaunchOrdinal(predecessor_extension_id).CreateAfter());
271    } else {
272      // Both a successor and predecessor
273      const syncer::StringOrdinal& predecessor_ordinal =
274          GetAppLaunchOrdinal(predecessor_extension_id);
275      const syncer::StringOrdinal& successor_ordinal =
276          GetAppLaunchOrdinal(successor_extension_id);
277      SetAppLaunchOrdinal(moved_extension_id,
278                          predecessor_ordinal.CreateBetween(successor_ordinal));
279    }
280  }
281
282  SyncIfNeeded(moved_extension_id);
283
284  content::NotificationService::current()->Notify(
285      chrome::NOTIFICATION_APP_LAUNCHER_REORDERED,
286      content::Source<ChromeAppSorting>(this),
287      content::Details<const std::string>(&moved_extension_id));
288}
289
290
291syncer::StringOrdinal ChromeAppSorting::GetAppLaunchOrdinal(
292    const std::string& extension_id) const {
293  std::string raw_value;
294  // If the preference read fails then raw_value will still be unset and we
295  // will return an invalid StringOrdinal to signal that no app launch ordinal
296  // was found.
297  extension_scoped_prefs_->ReadPrefAsString(
298      extension_id, kPrefAppLaunchOrdinal, &raw_value);
299  return syncer::StringOrdinal(raw_value);
300}
301
302void ChromeAppSorting::SetAppLaunchOrdinal(
303    const std::string& extension_id,
304    const syncer::StringOrdinal& new_app_launch_ordinal) {
305  // No work is required if the old and new values are the same.
306  if (new_app_launch_ordinal.EqualsOrBothInvalid(
307          GetAppLaunchOrdinal(extension_id))) {
308    return;
309  }
310
311  syncer::StringOrdinal page_ordinal = GetPageOrdinal(extension_id);
312  RemoveOrdinalMapping(
313      extension_id, page_ordinal, GetAppLaunchOrdinal(extension_id));
314  AddOrdinalMapping(extension_id, page_ordinal, new_app_launch_ordinal);
315
316  base::Value* new_value = new_app_launch_ordinal.IsValid() ?
317      new base::StringValue(new_app_launch_ordinal.ToInternalValue()) :
318      NULL;
319
320  extension_scoped_prefs_->UpdateExtensionPref(
321      extension_id,
322      kPrefAppLaunchOrdinal,
323      new_value);
324  SyncIfNeeded(extension_id);
325}
326
327syncer::StringOrdinal ChromeAppSorting::CreateFirstAppLaunchOrdinal(
328    const syncer::StringOrdinal& page_ordinal) const {
329  const syncer::StringOrdinal& min_ordinal =
330      GetMinOrMaxAppLaunchOrdinalsOnPage(page_ordinal,
331                                         ChromeAppSorting::MIN_ORDINAL);
332
333  if (min_ordinal.IsValid())
334    return min_ordinal.CreateBefore();
335  else
336    return syncer::StringOrdinal::CreateInitialOrdinal();
337}
338
339syncer::StringOrdinal ChromeAppSorting::CreateNextAppLaunchOrdinal(
340    const syncer::StringOrdinal& page_ordinal) const {
341  const syncer::StringOrdinal& max_ordinal =
342      GetMinOrMaxAppLaunchOrdinalsOnPage(page_ordinal,
343                                         ChromeAppSorting::MAX_ORDINAL);
344
345  if (max_ordinal.IsValid())
346    return max_ordinal.CreateAfter();
347  else
348    return syncer::StringOrdinal::CreateInitialOrdinal();
349}
350
351syncer::StringOrdinal ChromeAppSorting::CreateFirstAppPageOrdinal() const {
352  if (ntp_ordinal_map_.empty())
353    return syncer::StringOrdinal::CreateInitialOrdinal();
354
355  return ntp_ordinal_map_.begin()->first;
356}
357
358syncer::StringOrdinal ChromeAppSorting::GetNaturalAppPageOrdinal() const {
359  if (ntp_ordinal_map_.empty())
360    return syncer::StringOrdinal::CreateInitialOrdinal();
361
362  for (PageOrdinalMap::const_iterator it = ntp_ordinal_map_.begin();
363       it != ntp_ordinal_map_.end(); ++it) {
364    if (CountItemsVisibleOnNtp(it->second) < kNaturalAppPageSize)
365      return it->first;
366  }
367
368  // Add a new page as all existing pages are full.
369  syncer::StringOrdinal last_element = ntp_ordinal_map_.rbegin()->first;
370  return last_element.CreateAfter();
371}
372
373syncer::StringOrdinal ChromeAppSorting::GetPageOrdinal(
374    const std::string& extension_id) const {
375  std::string raw_data;
376  // If the preference read fails then raw_data will still be unset and we will
377  // return an invalid StringOrdinal to signal that no page ordinal was found.
378  extension_scoped_prefs_->ReadPrefAsString(
379      extension_id, kPrefPageOrdinal, &raw_data);
380  return syncer::StringOrdinal(raw_data);
381}
382
383void ChromeAppSorting::SetPageOrdinal(
384    const std::string& extension_id,
385    const syncer::StringOrdinal& new_page_ordinal) {
386  // No work is required if the old and new values are the same.
387  if (new_page_ordinal.EqualsOrBothInvalid(GetPageOrdinal(extension_id)))
388    return;
389
390  syncer::StringOrdinal app_launch_ordinal = GetAppLaunchOrdinal(extension_id);
391  RemoveOrdinalMapping(
392      extension_id, GetPageOrdinal(extension_id), app_launch_ordinal);
393  AddOrdinalMapping(extension_id, new_page_ordinal, app_launch_ordinal);
394
395  base::Value* new_value = new_page_ordinal.IsValid() ?
396      new base::StringValue(new_page_ordinal.ToInternalValue()) :
397      NULL;
398
399  extension_scoped_prefs_->UpdateExtensionPref(
400      extension_id,
401      kPrefPageOrdinal,
402      new_value);
403  SyncIfNeeded(extension_id);
404}
405
406void ChromeAppSorting::ClearOrdinals(const std::string& extension_id) {
407  RemoveOrdinalMapping(extension_id,
408                       GetPageOrdinal(extension_id),
409                       GetAppLaunchOrdinal(extension_id));
410
411  extension_scoped_prefs_->UpdateExtensionPref(
412      extension_id, kPrefPageOrdinal, NULL);
413  extension_scoped_prefs_->UpdateExtensionPref(
414      extension_id, kPrefAppLaunchOrdinal, NULL);
415}
416
417int ChromeAppSorting::PageStringOrdinalAsInteger(
418    const syncer::StringOrdinal& page_ordinal) const {
419  if (!page_ordinal.IsValid())
420    return -1;
421
422  PageOrdinalMap::const_iterator it = ntp_ordinal_map_.find(page_ordinal);
423  return it != ntp_ordinal_map_.end() ?
424      std::distance(ntp_ordinal_map_.begin(), it) : -1;
425}
426
427syncer::StringOrdinal ChromeAppSorting::PageIntegerAsStringOrdinal(
428    size_t page_index) {
429  if (page_index < ntp_ordinal_map_.size()) {
430    PageOrdinalMap::const_iterator it = ntp_ordinal_map_.begin();
431    std::advance(it, page_index);
432    return it->first;
433  }
434
435  CreateOrdinalsIfNecessary(page_index + 1);
436  return ntp_ordinal_map_.rbegin()->first;
437}
438
439void ChromeAppSorting::SetExtensionVisible(const std::string& extension_id,
440                                           bool visible) {
441  if (visible)
442    ntp_hidden_extensions_.erase(extension_id);
443  else
444    ntp_hidden_extensions_.insert(extension_id);
445}
446
447syncer::StringOrdinal ChromeAppSorting::GetMinOrMaxAppLaunchOrdinalsOnPage(
448    const syncer::StringOrdinal& target_page_ordinal,
449    AppLaunchOrdinalReturn return_type) const {
450  CHECK(target_page_ordinal.IsValid());
451
452  syncer::StringOrdinal return_value;
453
454  PageOrdinalMap::const_iterator page =
455      ntp_ordinal_map_.find(target_page_ordinal);
456  if (page != ntp_ordinal_map_.end()) {
457    const AppLaunchOrdinalMap& app_list = page->second;
458
459    if (app_list.empty())
460      return syncer::StringOrdinal();
461
462    if (return_type == ChromeAppSorting::MAX_ORDINAL)
463      return_value = app_list.rbegin()->first;
464    else if (return_type == ChromeAppSorting::MIN_ORDINAL)
465      return_value = app_list.begin()->first;
466  }
467
468  return return_value;
469}
470
471void ChromeAppSorting::InitializePageOrdinalMap(
472    const extensions::ExtensionIdList& extension_ids) {
473  for (extensions::ExtensionIdList::const_iterator ext_it =
474           extension_ids.begin(); ext_it != extension_ids.end(); ++ext_it) {
475    AddOrdinalMapping(*ext_it,
476                      GetPageOrdinal(*ext_it),
477                      GetAppLaunchOrdinal(*ext_it));
478
479    // Ensure that the web store app still isn't found in this list, since
480    // it is added after this loop.
481    DCHECK(*ext_it != extensions::kWebStoreAppId);
482    DCHECK(*ext_it != extension_misc::kChromeAppId);
483  }
484
485  // Include the Web Store App since it is displayed on the NTP.
486  syncer::StringOrdinal web_store_app_page =
487      GetPageOrdinal(extensions::kWebStoreAppId);
488  if (web_store_app_page.IsValid()) {
489    AddOrdinalMapping(extensions::kWebStoreAppId,
490                      web_store_app_page,
491                      GetAppLaunchOrdinal(extensions::kWebStoreAppId));
492  }
493  // Include the Chrome App since it is displayed in the app launcher.
494  syncer::StringOrdinal chrome_app_page =
495      GetPageOrdinal(extension_misc::kChromeAppId);
496  if (chrome_app_page.IsValid()) {
497    AddOrdinalMapping(extension_misc::kChromeAppId,
498                      chrome_app_page,
499                      GetAppLaunchOrdinal(extension_misc::kChromeAppId));
500  }
501}
502
503void ChromeAppSorting::AddOrdinalMapping(
504    const std::string& extension_id,
505    const syncer::StringOrdinal& page_ordinal,
506    const syncer::StringOrdinal& app_launch_ordinal) {
507  if (!page_ordinal.IsValid() || !app_launch_ordinal.IsValid())
508    return;
509
510  ntp_ordinal_map_[page_ordinal].insert(
511      std::make_pair(app_launch_ordinal, extension_id));
512}
513
514void ChromeAppSorting::RemoveOrdinalMapping(
515    const std::string& extension_id,
516    const syncer::StringOrdinal& page_ordinal,
517    const syncer::StringOrdinal& app_launch_ordinal) {
518  if (!page_ordinal.IsValid() || !app_launch_ordinal.IsValid())
519    return;
520
521  // Check that the page exists using find to prevent creating a new page
522  // if |page_ordinal| isn't a used page.
523  PageOrdinalMap::iterator page_map = ntp_ordinal_map_.find(page_ordinal);
524  if (page_map == ntp_ordinal_map_.end())
525    return;
526
527  for (AppLaunchOrdinalMap::iterator it =
528           page_map->second.find(app_launch_ordinal);
529       it != page_map->second.end(); ++it) {
530    if (it->second == extension_id) {
531      page_map->second.erase(it);
532      break;
533    }
534  }
535}
536
537void ChromeAppSorting::SyncIfNeeded(const std::string& extension_id) {
538  if (extension_sync_service_)
539    extension_sync_service_->SyncOrderingChange(extension_id);
540}
541
542void ChromeAppSorting::CreateDefaultOrdinals() {
543  if (default_ordinals_created_)
544    return;
545  default_ordinals_created_ = true;
546
547  // The following defines the default order of apps.
548#if defined(OS_CHROMEOS)
549  std::vector<std::string> app_ids;
550  chromeos::default_app_order::Get(&app_ids);
551#else
552  const char* kDefaultAppOrder[] = {
553    extension_misc::kChromeAppId,
554    extensions::kWebStoreAppId,
555  };
556  const std::vector<const char*> app_ids(
557      kDefaultAppOrder, kDefaultAppOrder + arraysize(kDefaultAppOrder));
558#endif
559
560  syncer::StringOrdinal page_ordinal = CreateFirstAppPageOrdinal();
561  syncer::StringOrdinal app_launch_ordinal =
562      CreateFirstAppLaunchOrdinal(page_ordinal);
563  for (size_t i = 0; i < app_ids.size(); ++i) {
564    const std::string extension_id = app_ids[i];
565    default_ordinals_[extension_id].page_ordinal = page_ordinal;
566    default_ordinals_[extension_id].app_launch_ordinal = app_launch_ordinal;
567    app_launch_ordinal = app_launch_ordinal.CreateAfter();
568  }
569}
570
571bool ChromeAppSorting::GetDefaultOrdinals(
572    const std::string& extension_id,
573    syncer::StringOrdinal* page_ordinal,
574    syncer::StringOrdinal* app_launch_ordinal) {
575  CreateDefaultOrdinals();
576  AppOrdinalsMap::const_iterator it = default_ordinals_.find(extension_id);
577  if (it == default_ordinals_.end())
578    return false;
579
580  if (page_ordinal)
581    *page_ordinal = it->second.page_ordinal;
582  if (app_launch_ordinal)
583    *app_launch_ordinal = it->second.app_launch_ordinal;
584  return true;
585}
586
587syncer::StringOrdinal ChromeAppSorting::ResolveCollision(
588    const syncer::StringOrdinal& page_ordinal,
589    const syncer::StringOrdinal& app_launch_ordinal) const {
590  DCHECK(page_ordinal.IsValid() && app_launch_ordinal.IsValid());
591
592  PageOrdinalMap::const_iterator page_it = ntp_ordinal_map_.find(page_ordinal);
593  if (page_it == ntp_ordinal_map_.end())
594    return app_launch_ordinal;
595
596  const AppLaunchOrdinalMap& page = page_it->second;
597  AppLaunchOrdinalMap::const_iterator app_it = page.find(app_launch_ordinal);
598  if (app_it == page.end())
599    return app_launch_ordinal;
600
601  // Finds the next app launcher ordinal. This is done by the following loop
602  // because this function could be called before FixNTPOrdinalCollisions and
603  // thus |page| might contains multiple entries with the same app launch
604  // ordinal. See http://crbug.com/155603
605  while (app_it != page.end() && app_launch_ordinal.Equals(app_it->first))
606    ++app_it;
607
608  // If there is no next after the collision, returns the next ordinal.
609  if (app_it == page.end())
610    return app_launch_ordinal.CreateAfter();
611
612  // Otherwise, returns the ordinal between the collision and the next ordinal.
613  return app_launch_ordinal.CreateBetween(app_it->first);
614}
615
616size_t ChromeAppSorting::CountItemsVisibleOnNtp(
617    const AppLaunchOrdinalMap& m) const {
618  size_t result = 0;
619  for (AppLaunchOrdinalMap::const_iterator it = m.begin(); it != m.end();
620       ++it) {
621    const std::string& id = it->second;
622    if (ntp_hidden_extensions_.count(id) == 0)
623      result++;
624  }
625  return result;
626}
627
628}  // namespace extensions
629