mixer.cc revision 116680a4aac90f2aa7413d9095a592090648e557 
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
16namespace app_list {
17
18namespace {
19
20// Maximum number of results to show.
21const size_t kMaxResults = 6;
22const size_t kMaxMainGroupResults = 4;
23const size_t kMaxWebstoreResults = 2;
24const size_t kMaxPeopleResults = 2;
25
26// A value to indicate no max number of results limit.
27const size_t kNoMaxResultsLimit = 0;
28
29void 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
39Mixer::SortData::SortData() : result(NULL), score(0.0) {
40}
41
42Mixer::SortData::SortData(ChromeSearchResult* result, double score)
43    : result(result), score(score) {
44}
45
46bool 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.
52class 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
125Mixer::Mixer(AppListModel::SearchResults* ui_results)
126    : ui_results_(ui_results) {}
127Mixer::~Mixer() {}
128
129void 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
136void Mixer::AddProviderToGroup(GroupId group, SearchProvider* provider) {
137  size_t group_index = static_cast<size_t>(group);
138  groups_[group_index]->AddProvider(provider);
139}
140
141void 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
183void 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
236void 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
254void 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