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