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 <set>
9#include <string>
10#include <vector>
11
12#include "chrome/browser/ui/app_list/search/chrome_search_result.h"
13#include "chrome/browser/ui/app_list/search/search_provider.h"
14
15namespace app_list {
16
17namespace {
18
19// Maximum number of results to show.
20const size_t kMaxResults = 6;
21const size_t kMaxMainGroupResults = 4;
22const size_t kMaxWebstoreResults = 2;
23
24// A value to indicate no max number of results limit.
25const size_t kNoMaxResultsLimit = 0;
26
27// Used for sorting and mixing results.
28struct SortData {
29  SortData()
30      : result(NULL),
31        score(0.0) {
32  }
33  SortData(ChromeSearchResult* result, double score)
34      : result(result),
35        score(score) {
36  }
37
38  bool operator<(const SortData& other) const {
39    // This data precedes (less than) |other| if it has higher score.
40    return score > other.score;
41  }
42
43  ChromeSearchResult* result;  // Not owned.
44  double score;
45};
46typedef std::vector<SortData> SortedResults;
47
48// Removes duplicates from |results|.
49void RemoveDuplicates(SortedResults* results) {
50  SortedResults final;
51  final.reserve(results->size());
52
53  std::set<std::string> id_set;
54  for (SortedResults::iterator it = results->begin();
55       it != results->end();
56       ++it) {
57    const std::string& id = it->result->id();
58    if (id_set.find(id) != id_set.end())
59      continue;
60
61    id_set.insert(id);
62    final.push_back(*it);
63  }
64
65  results->swap(final);
66}
67
68// Publishes the given |results| to |ui_results|. Reuse existing ones to avoid
69// flickering.
70void Publish(const SortedResults& results,
71             AppListModel::SearchResults* ui_results) {
72  for (size_t i = 0; i < results.size(); ++i) {
73    ChromeSearchResult* result = results[i].result;
74
75    ChromeSearchResult* ui_result = i < ui_results->item_count() ?
76        static_cast<ChromeSearchResult*>(ui_results->GetItemAt(i)) : NULL;
77    if (ui_result && ui_result->id() == result->id()) {
78      ui_result->set_title(result->title());
79      ui_result->set_title_tags(result->title_tags());
80      ui_result->set_details(result->details());
81      ui_result->set_details_tags(result->details_tags());
82      ui_results->NotifyItemsChanged(i, 1);
83    } else {
84      if (ui_result)
85        ui_results->DeleteAt(i);
86      ui_results->AddAt(i, result->Duplicate().release());
87    }
88  }
89
90  while (ui_results->item_count() > results.size())
91    ui_results->DeleteAt(ui_results->item_count() - 1);
92}
93
94}  // namespace
95
96// Used to group relevant providers together fox mixing their results.
97class Mixer::Group {
98 public:
99  Group(size_t max_results, double boost)
100      : max_results_(max_results),
101        boost_(boost) {
102  }
103  ~Group() {}
104
105  void AddProvider(SearchProvider* provider) {
106    providers_.push_back(provider);
107  }
108
109  void FetchResults(const KnownResults& known_results) {
110    results_.clear();
111
112    for (Providers::const_iterator provider_it = providers_.begin();
113         provider_it != providers_.end();
114         ++provider_it) {
115      for (SearchProvider::Results::const_iterator
116               result_it = (*provider_it)->results().begin();
117               result_it != (*provider_it)->results().end();
118               ++result_it) {
119        DCHECK_GE((*result_it)->relevance(), 0.0);
120        DCHECK_LE((*result_it)->relevance(), 1.0);
121        DCHECK(!(*result_it)->id().empty());
122
123        double boost = boost_;
124        KnownResults::const_iterator known_it =
125            known_results.find((*result_it)->id());
126        if (known_it != known_results.end()) {
127          switch (known_it->second) {
128            case PERFECT_PRIMARY:
129              boost = 4.0;
130              break;
131            case PREFIX_PRIMARY:
132              boost = 3.75;
133              break;
134            case PERFECT_SECONDARY:
135              boost = 3.25;
136              break;
137            case PREFIX_SECONDARY:
138              boost = 3.0;
139              break;
140            case UNKNOWN_RESULT:
141              NOTREACHED() << "Unknown result in KnownResults?";
142              break;
143          }
144        }
145
146        results_.push_back(
147            SortData(*result_it, (*result_it)->relevance() + boost));
148      }
149    }
150
151    std::sort(results_.begin(), results_.end());
152    if (max_results_ != kNoMaxResultsLimit && results_.size() > max_results_)
153      results_.resize(max_results_);
154  }
155
156  const SortedResults& results() const { return results_; }
157
158 private:
159  typedef std::vector<SearchProvider*> Providers;
160  const size_t max_results_;
161  const double boost_;
162
163  Providers providers_;  // Not owned.
164  SortedResults results_;
165
166  DISALLOW_COPY_AND_ASSIGN(Group);
167};
168
169Mixer::Mixer(AppListModel::SearchResults* ui_results)
170    : ui_results_(ui_results) {}
171Mixer::~Mixer() {}
172
173void Mixer::Init() {
174  groups_.push_back(new Group(kMaxMainGroupResults, 2.0));
175  groups_.push_back(new Group(kNoMaxResultsLimit, 1.0));
176  groups_.push_back(new Group(kMaxWebstoreResults, 0.0));
177}
178
179void Mixer::AddProviderToGroup(GroupId group, SearchProvider* provider) {
180  size_t group_index = static_cast<size_t>(group);
181  groups_[group_index]->AddProvider(provider);
182}
183
184void Mixer::MixAndPublish(const KnownResults& known_results) {
185  FetchResults(known_results);
186
187  SortedResults results;
188  results.reserve(kMaxResults);
189
190  // Adds main group and web store results first.
191  results.insert(results.end(),
192                 groups_[MAIN_GROUP]->results().begin(),
193                 groups_[MAIN_GROUP]->results().end());
194  results.insert(results.end(),
195                 groups_[WEBSTORE_GROUP]->results().begin(),
196                 groups_[WEBSTORE_GROUP]->results().end());
197
198  // Collapse duplicate apps from local and web store.
199  RemoveDuplicates(&results);
200
201  DCHECK_GE(kMaxResults, results.size());
202  size_t remaining_slots = kMaxResults - results.size();
203
204  // Reserves at least one slot for the omnibox result. If there is no available
205  // slot for omnibox results, removes the last one from web store.
206  const size_t omnibox_results = groups_[OMNIBOX_GROUP]->results().size();
207  if (!remaining_slots && omnibox_results)
208    results.pop_back();
209
210  remaining_slots = std::min(kMaxResults - results.size(), omnibox_results);
211  results.insert(results.end(),
212                 groups_[OMNIBOX_GROUP]->results().begin(),
213                 groups_[OMNIBOX_GROUP]->results().begin() + remaining_slots);
214
215  std::sort(results.begin(), results.end());
216  RemoveDuplicates(&results);
217  if (results.size() > kMaxResults)
218    results.resize(kMaxResults);
219
220  Publish(results, ui_results_);
221}
222
223void Mixer::FetchResults(const KnownResults& known_results) {
224  for (Groups::iterator group_it = groups_.begin();
225       group_it != groups_.end();
226       ++group_it) {
227    (*group_it)->FetchResults(known_results);
228  }
229}
230
231}  // namespace app_list
232