ui/app_list/search/mixer.cc

   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 "ui/app_list/search/mixer.h"
   6
   7 #include <algorithm>
   8 #include <map>
   9 #include <set>
  10 #include <string>
  11 #include <vector>
  12
  13 #include "ui/app_list/search_provider.h"
  14 #include "ui/app_list/search_result.h"
  15
  16 namespace app_list {
  17
  18 namespace {
  19
  20 // Maximum number of results to show.
  21 const size_t kMaxResults = 6;
  22 const size_t kMaxMainGroupResults = 4;
  23 const size_t kMaxWebstoreResults = 2;
  24 const size_t kMaxPeopleResults = 2;
  25
  26 // A value to indicate no max number of results limit.
  27 const size_t kNoMaxResultsLimit = 0;
  28
  29 void UpdateResult(const SearchResult& source, SearchResult* target) {
  30   target->set_title(source.title());
  31   target->set_title_tags(source.title_tags());
  32   target->set_details(source.details());
  33   target->set_details_tags(source.details_tags());
  34 }
  35
  36 }  // namespace
  37
  38 Mixer::SortData::SortData() : result(NULL), score(0.0) {
  39 }
  40
  41 Mixer::SortData::SortData(SearchResult* result, double score)
  42     : result(result), score(score) {
  43 }
  44
  45 bool Mixer::SortData::operator<(const SortData& other) const {
  46   // This data precedes (less than) |other| if it has higher score.
  47   return score > other.score;
  48 }
  49
  50 // Used to group relevant providers together fox mixing their results.
  51 class Mixer::Group {
  52  public:
  53   Group(size_t max_results, double boost)
  54       : max_results_(max_results), boost_(boost) {}
  55   ~Group() {}
  56
  57   void AddProvider(SearchProvider* provider) { providers_.push_back(provider); }
  58
  59   void FetchResults(const KnownResults& known_results) {
  60     results_.clear();
  61
  62     for (Providers::const_iterator provider_it = providers_.begin();
  63          provider_it != providers_.end();
  64          ++provider_it) {
  65       for (SearchProvider::Results::const_iterator result_it =
  66                (*provider_it)->results().begin();
  67            result_it != (*provider_it)->results().end();
  68            ++result_it) {
  69         DCHECK_GE((*result_it)->relevance(), 0.0);
  70         DCHECK_LE((*result_it)->relevance(), 1.0);
  71         DCHECK(!(*result_it)->id().empty());
  72
  73         double boost = boost_;
  74         KnownResults::const_iterator known_it =
  75             known_results.find((*result_it)->id());
  76         if (known_it != known_results.end()) {
  77           switch (known_it->second) {
  78             case PERFECT_PRIMARY:
  79               boost = 4.0;
  80               break;
  81             case PREFIX_PRIMARY:
  82               boost = 3.75;
  83               break;
  84             case PERFECT_SECONDARY:
  85               boost = 3.25;
  86               break;
  87             case PREFIX_SECONDARY:
  88               boost = 3.0;
  89               break;
  90             case UNKNOWN_RESULT:
  91               NOTREACHED() << "Unknown result in KnownResults?";
  92               break;
  93           }
  94         }
  95
  96         results_.push_back(
  97             SortData(*result_it, (*result_it)->relevance() + boost));
  98       }
  99     }
 100
 101     std::sort(results_.begin(), results_.end());
 102     if (max_results_ != kNoMaxResultsLimit && results_.size() > max_results_)
 103       results_.resize(max_results_);
 104   }
 105
 106   const SortedResults& results() const { return results_; }
 107
 108  private:
 109   typedef std::vector<SearchProvider*> Providers;
 110   const size_t max_results_;
 111   const double boost_;
 112
 113   Providers providers_;  // Not owned.
 114   SortedResults results_;
 115
 116   DISALLOW_COPY_AND_ASSIGN(Group);
 117 };
 118
 119 Mixer::Mixer(AppListModel::SearchResults* ui_results)
 120     : ui_results_(ui_results) {
 121 }
 122 Mixer::~Mixer() {
 123 }
 124
 125 void Mixer::Init() {
 126   groups_[MAIN_GROUP].reset(new Group(kMaxMainGroupResults, 3.0));
 127   groups_[OMNIBOX_GROUP].reset(new Group(kNoMaxResultsLimit, 2.0));
 128   groups_[WEBSTORE_GROUP].reset(new Group(kMaxWebstoreResults, 1.0));
 129   groups_[PEOPLE_GROUP].reset(new Group(kMaxPeopleResults, 0.0));
 130 }
 131
 132 void Mixer::AddProviderToGroup(GroupId group, SearchProvider* provider) {
 133   groups_[group]->AddProvider(provider);
 134 }
 135
 136 void Mixer::MixAndPublish(const KnownResults& known_results) {
 137   FetchResults(known_results);
 138
 139   SortedResults results;
 140   results.reserve(kMaxResults);
 141
 142   const Group& main_group = *groups_[MAIN_GROUP];
 143   const Group& omnibox_group = *groups_[OMNIBOX_GROUP];
 144   const Group& webstore_group = *groups_[WEBSTORE_GROUP];
 145   const Group& people_group = *groups_[PEOPLE_GROUP];
 146
 147   // Adds main group and web store results first.
 148   results.insert(results.end(), main_group.results().begin(),
 149                  main_group.results().end());
 150   results.insert(results.end(), webstore_group.results().begin(),
 151                  webstore_group.results().end());
 152   results.insert(results.end(), people_group.results().begin(),
 153                  people_group.results().end());
 154
 155   // Collapse duplicate apps from local and web store.
 156   RemoveDuplicates(&results);
 157
 158   // Fill the remaining slots with omnibox results. Always add at least one
 159   // omnibox result (even if there are no more slots; if we over-fill the
 160   // vector, the web store and people results will be removed in a later step).
 161   const size_t omnibox_results =
 162       std::min(omnibox_group.results().size(),
 163                results.size() < kMaxResults ? kMaxResults - results.size() : 1);
 164   results.insert(results.end(), omnibox_group.results().begin(),
 165                  omnibox_group.results().begin() + omnibox_results);
 166
 167   std::sort(results.begin(), results.end());
 168   RemoveDuplicates(&results);
 169   if (results.size() > kMaxResults)
 170     results.resize(kMaxResults);
 171
 172   Publish(results, ui_results_);
 173 }
 174
 175 void Mixer::Publish(const SortedResults& new_results,
 176                     AppListModel::SearchResults* ui_results) {
 177   typedef std::map<std::string, SearchResult*> IdToResultMap;
 178
 179   // The following algorithm is used:
 180   // 1. Transform the |ui_results| list into an unordered map from result ID
 181   // to item.
 182   // 2. Use the order of items in |new_results| to build an ordered list. If the
 183   // result IDs exist in the map, update and use the item in the map and delete
 184   // it from the map afterwards. Otherwise, clone new items from |new_results|.
 185   // 3. Delete the objects remaining in the map as they are unused.
 186
 187   // A map of the items in |ui_results| that takes ownership of the items.
 188   IdToResultMap ui_results_map;
 189   for (size_t i = 0; i < ui_results->item_count(); ++i) {
 190     SearchResult* ui_result = ui_results->GetItemAt(i);
 191     ui_results_map[ui_result->id()] = ui_result;
 192   }
 193   // We have to erase all results at once so that observers are notified with
 194   // meaningful indexes.
 195   ui_results->RemoveAll();
 196
 197   // Add items back to |ui_results| in the order of |new_results|.
 198   for (size_t i = 0; i < new_results.size(); ++i) {
 199     SearchResult* new_result = new_results[i].result;
 200     IdToResultMap::const_iterator ui_result_it =
 201         ui_results_map.find(new_result->id());
 202     if (ui_result_it != ui_results_map.end()) {
 203       // Update and use the old result if it exists.
 204       SearchResult* ui_result = ui_result_it->second;
 205       UpdateResult(*new_result, ui_result);
 206
 207       // |ui_results| takes back ownership from |ui_results_map| here.
 208       ui_results->Add(ui_result);
 209
 210       // Remove the item from the map so that it ends up only with unused
 211       // results.
 212       ui_results_map.erase(ui_result->id());
 213     } else {
 214       // Copy the result from |new_results| otherwise.
 215       ui_results->Add(new_result->Duplicate().release());
 216     }
 217   }
 218
 219   // Delete the results remaining in the map as they are not in the new results.
 220   for (IdToResultMap::const_iterator ui_result_it = ui_results_map.begin();
 221        ui_result_it != ui_results_map.end();
 222        ++ui_result_it) {
 223     delete ui_result_it->second;
 224   }
 225 }
 226
 227 void Mixer::RemoveDuplicates(SortedResults* results) {
 228   SortedResults final;
 229   final.reserve(results->size());
 230
 231   std::set<std::string> id_set;
 232   for (SortedResults::iterator it = results->begin(); it != results->end();
 233        ++it) {
 234     const std::string& id = it->result->id();
 235     if (id_set.find(id) != id_set.end())
 236       continue;
 237
 238     id_set.insert(id);
 239     final.push_back(*it);
 240   }
 241
 242   results->swap(final);
 243 }
 244
 245 void Mixer::FetchResults(const KnownResults& known_results) {
 246   for (const auto& item : groups_)
 247     item.second->FetchResults(known_results);
 248 }
 249
 250 }  // namespace app_list