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.
5 #include "ui/app_list/search/mixer.h"
13 #include "ui/app_list/search_provider.h"
14 #include "ui/app_list/search_result.h"
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 const size_t kMaxSuggestionsResults
= 6;
27 // A value to indicate no max number of results limit.
28 const size_t kNoMaxResultsLimit
= 0;
30 void UpdateResult(const SearchResult
& source
, SearchResult
* 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());
39 Mixer::SortData::SortData() : result(NULL
), score(0.0) {
42 Mixer::SortData::SortData(SearchResult
* result
, double score
)
43 : result(result
), score(score
) {
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
;
51 // Used to group relevant providers together fox mixing their results.
54 Group(size_t max_results
, double boost
)
55 : max_results_(max_results
), boost_(boost
) {}
58 void AddProvider(SearchProvider
* provider
) { providers_
.push_back(provider
); }
60 void FetchResults(bool is_voice_query
, const KnownResults
& known_results
) {
63 for (Providers::const_iterator provider_it
= providers_
.begin();
64 provider_it
!= providers_
.end();
66 for (SearchProvider::Results::const_iterator result_it
=
67 (*provider_it
)->results().begin();
68 result_it
!= (*provider_it
)->results().end();
70 DCHECK_GE((*result_it
)->relevance(), 0.0);
71 DCHECK_LE((*result_it
)->relevance(), 1.0);
72 DCHECK(!(*result_it
)->id().empty());
74 double boost
= boost_
;
75 KnownResults::const_iterator known_it
=
76 known_results
.find((*result_it
)->id());
77 if (known_it
!= known_results
.end()) {
78 switch (known_it
->second
) {
85 case PERFECT_SECONDARY
:
88 case PREFIX_SECONDARY
:
92 NOTREACHED() << "Unknown result in KnownResults?";
97 // If this is a voice query, voice results receive a massive boost.
98 if (is_voice_query
&& (*result_it
)->voice_result())
102 SortData(*result_it
, (*result_it
)->relevance() + boost
));
106 std::sort(results_
.begin(), results_
.end());
107 if (max_results_
!= kNoMaxResultsLimit
&& results_
.size() > max_results_
)
108 results_
.resize(max_results_
);
111 const SortedResults
& results() const { return results_
; }
114 typedef std::vector
<SearchProvider
*> Providers
;
115 const size_t max_results_
;
118 Providers providers_
; // Not owned.
119 SortedResults results_
;
121 DISALLOW_COPY_AND_ASSIGN(Group
);
124 Mixer::Mixer(AppListModel::SearchResults
* ui_results
)
125 : ui_results_(ui_results
) {
131 groups_
[MAIN_GROUP
].reset(new Group(kMaxMainGroupResults
, 3.0));
132 groups_
[OMNIBOX_GROUP
].reset(new Group(kNoMaxResultsLimit
, 2.0));
133 groups_
[WEBSTORE_GROUP
].reset(new Group(kMaxWebstoreResults
, 1.0));
134 groups_
[PEOPLE_GROUP
].reset(new Group(kMaxPeopleResults
, 0.0));
135 groups_
[SUGGESTIONS_GROUP
].reset(new Group(kMaxSuggestionsResults
, 3.0));
138 void Mixer::AddProviderToGroup(GroupId group
, SearchProvider
* provider
) {
139 groups_
[group
]->AddProvider(provider
);
142 void Mixer::MixAndPublish(bool is_voice_query
,
143 const KnownResults
& known_results
) {
144 FetchResults(is_voice_query
, known_results
);
146 SortedResults results
;
147 results
.reserve(kMaxResults
);
149 const Group
& main_group
= *groups_
[MAIN_GROUP
];
150 const Group
& omnibox_group
= *groups_
[OMNIBOX_GROUP
];
151 const Group
& webstore_group
= *groups_
[WEBSTORE_GROUP
];
152 const Group
& people_group
= *groups_
[PEOPLE_GROUP
];
153 const Group
& suggestions_group
= *groups_
[SUGGESTIONS_GROUP
];
155 // Adds main group and web store results first.
156 results
.insert(results
.end(), main_group
.results().begin(),
157 main_group
.results().end());
158 results
.insert(results
.end(), webstore_group
.results().begin(),
159 webstore_group
.results().end());
160 results
.insert(results
.end(), people_group
.results().begin(),
161 people_group
.results().end());
162 results
.insert(results
.end(), suggestions_group
.results().begin(),
163 suggestions_group
.results().end());
165 // Collapse duplicate apps from local and web store.
166 RemoveDuplicates(&results
);
168 // Fill the remaining slots with omnibox results. Always add at least one
169 // omnibox result (even if there are no more slots; if we over-fill the
170 // vector, the web store and people results will be removed in a later step).
171 const size_t omnibox_results
=
172 std::min(omnibox_group
.results().size(),
173 results
.size() < kMaxResults
? kMaxResults
- results
.size() : 1);
174 results
.insert(results
.end(), omnibox_group
.results().begin(),
175 omnibox_group
.results().begin() + omnibox_results
);
177 std::sort(results
.begin(), results
.end());
178 RemoveDuplicates(&results
);
179 if (results
.size() > kMaxResults
)
180 results
.resize(kMaxResults
);
182 Publish(results
, ui_results_
);
185 void Mixer::Publish(const SortedResults
& new_results
,
186 AppListModel::SearchResults
* ui_results
) {
187 typedef std::map
<std::string
, SearchResult
*> IdToResultMap
;
189 // The following algorithm is used:
190 // 1. Transform the |ui_results| list into an unordered map from result ID
192 // 2. Use the order of items in |new_results| to build an ordered list. If the
193 // result IDs exist in the map, update and use the item in the map and delete
194 // it from the map afterwards. Otherwise, clone new items from |new_results|.
195 // 3. Delete the objects remaining in the map as they are unused.
197 // A map of the items in |ui_results| that takes ownership of the items.
198 IdToResultMap ui_results_map
;
199 for (size_t i
= 0; i
< ui_results
->item_count(); ++i
) {
200 SearchResult
* ui_result
= ui_results
->GetItemAt(i
);
201 ui_results_map
[ui_result
->id()] = ui_result
;
203 // We have to erase all results at once so that observers are notified with
204 // meaningful indexes.
205 ui_results
->RemoveAll();
207 // Add items back to |ui_results| in the order of |new_results|.
208 for (size_t i
= 0; i
< new_results
.size(); ++i
) {
209 SearchResult
* new_result
= new_results
[i
].result
;
210 IdToResultMap::const_iterator ui_result_it
=
211 ui_results_map
.find(new_result
->id());
212 if (ui_result_it
!= ui_results_map
.end()) {
213 // Update and use the old result if it exists.
214 SearchResult
* ui_result
= ui_result_it
->second
;
215 UpdateResult(*new_result
, ui_result
);
217 // |ui_results| takes back ownership from |ui_results_map| here.
218 ui_results
->Add(ui_result
);
220 // Remove the item from the map so that it ends up only with unused
222 ui_results_map
.erase(ui_result
->id());
224 // Copy the result from |new_results| otherwise.
225 ui_results
->Add(new_result
->Duplicate().release());
229 // Delete the results remaining in the map as they are not in the new results.
230 for (IdToResultMap::const_iterator ui_result_it
= ui_results_map
.begin();
231 ui_result_it
!= ui_results_map
.end();
233 delete ui_result_it
->second
;
237 void Mixer::RemoveDuplicates(SortedResults
* results
) {
239 final
.reserve(results
->size());
241 std::set
<std::string
> id_set
;
242 for (SortedResults::iterator it
= results
->begin(); it
!= results
->end();
244 const std::string
& id
= it
->result
->id();
245 if (id_set
.find(id
) != id_set
.end())
249 final
.push_back(*it
);
252 results
->swap(final
);
255 void Mixer::FetchResults(bool is_voice_query
,
256 const KnownResults
& known_results
) {
257 for (const auto& item
: groups_
)
258 item
.second
->FetchResults(is_voice_query
, known_results
);
261 } // namespace app_list