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/history_data.h"
6
7#include <algorithm>
8#include <vector>
9
10#include "base/bind.h"
11#include "chrome/browser/ui/app_list/search/history_data_observer.h"
12#include "chrome/browser/ui/app_list/search/history_data_store.h"
13
14namespace app_list {
15
16namespace {
17
18// A struct used to sort query entries by time.
19struct EntrySortData {
20  EntrySortData() : query(NULL), update_time(NULL) {}
21  EntrySortData(const std::string* query,
22                const base::Time* update_time)
23      : query(query),
24        update_time(update_time) {
25  }
26
27  const std::string* query;
28  const base::Time* update_time;
29};
30
31bool EntrySortByTimeAscending(const EntrySortData& entry1,
32                              const EntrySortData& entry2) {
33  return *entry1.update_time < *entry2.update_time;
34}
35
36}  // namespace
37
38HistoryData::Data::Data() {}
39HistoryData::Data::~Data() {}
40
41HistoryData::HistoryData(HistoryDataStore* store,
42                         size_t max_primary,
43                         size_t max_secondary)
44    : store_(store),
45      max_primary_(max_primary),
46      max_secondary_(max_secondary) {
47  store_->Load(base::Bind(&HistoryData::OnStoreLoaded, AsWeakPtr()));
48}
49
50HistoryData::~HistoryData() {}
51
52void HistoryData::Add(const std::string& query, const std::string& result_id) {
53  Associations::iterator assoc_it = associations_.find(query);
54
55  // Creates a primary association if query is seen for the first time.
56  if (assoc_it == associations_.end()) {
57    Data& data = associations_[query];
58    data.primary = result_id;
59    data.update_time = base::Time::Now();
60
61    store_->SetPrimary(query, result_id);
62    store_->SetUpdateTime(query, data.update_time);
63
64    TrimEntries();
65    return;
66  }
67
68  Data& data = assoc_it->second;
69  data.update_time = base::Time::Now();
70  store_->SetUpdateTime(query, data.update_time);
71
72  SecondaryDeque& secondary = data.secondary;
73  if (!secondary.empty() && secondary.back() == result_id) {
74    // Nothing to do if the last secondary is the current primary.
75    if (data.primary == result_id)
76      return;
77
78    // If |result_id| is the last (the most recent) secondary and it's not the
79    // current primary, promote it and demote the primary.
80    secondary.pop_back();
81    secondary.push_back(data.primary);
82    data.primary = result_id;
83
84    store_->SetPrimary(query, result_id);
85    store_->SetSecondary(query, secondary);
86    return;
87  }
88
89  // Otherwise, append to secondary list.
90  SecondaryDeque::iterator secondary_it =
91      std::find(secondary.begin(), secondary.end(), result_id);
92  if (secondary_it != secondary.end())
93    secondary.erase(secondary_it);
94
95  secondary.push_back(result_id);
96  if (secondary.size() > max_secondary_)
97    secondary.pop_front();
98  store_->SetSecondary(query, secondary);
99}
100
101scoped_ptr<KnownResults> HistoryData::GetKnownResults(
102    const std::string& query) const {
103  scoped_ptr<KnownResults> results(new KnownResults);
104  for (Associations::const_iterator assoc_it =
105           associations_.lower_bound(query);
106       assoc_it != associations_.end();
107       ++assoc_it) {
108    // Break out of the loop if |query| is no longer a prefix.
109    if (assoc_it->first.size() < query.size() ||
110        strncmp(assoc_it->first.c_str(),
111                query.c_str(),
112                query.length()) != 0) {
113      break;
114    }
115
116    const bool perfect = assoc_it->first == query;
117    // Primary match should always be returned.
118    (*results)[assoc_it->second.primary] =
119        perfect ? PERFECT_PRIMARY : PREFIX_PRIMARY;
120
121    const KnownResultType secondary_type =
122        perfect ? PERFECT_SECONDARY : PREFIX_SECONDARY;
123    const HistoryData::SecondaryDeque& secondary = assoc_it->second.secondary;
124    for (HistoryData::SecondaryDeque::const_iterator secondary_it =
125             secondary.begin();
126         secondary_it != secondary.end();
127         ++secondary_it) {
128      const std::string& secondary_result_id = (*secondary_it);
129
130      // Secondary match only gets added if there there is no primary match.
131      if (results->find(secondary_result_id) != results->end())
132        continue;
133      (*results)[secondary_result_id] = secondary_type;
134    }
135  }
136
137  return results.Pass();
138}
139
140void HistoryData::AddObserver(HistoryDataObserver* observer) {
141  observers_.AddObserver(observer);
142}
143
144void HistoryData::RemoveObserver(HistoryDataObserver* observer) {
145  observers_.RemoveObserver(observer);
146}
147
148void HistoryData::OnStoreLoaded(scoped_ptr<Associations> loaded_data) {
149  if (loaded_data)
150    loaded_data->swap(associations_);
151
152  FOR_EACH_OBSERVER(HistoryDataObserver, observers_,
153                    OnHistoryDataLoadedFromStore());
154}
155
156void HistoryData::TrimEntries() {
157  if (associations_.size() <= max_primary_)
158    return;
159
160  std::vector<EntrySortData> entries;
161  for (Associations::const_iterator it = associations_.begin();
162       it != associations_.end(); ++it) {
163    entries.push_back(EntrySortData(&it->first, &it->second.update_time));
164  }
165
166  const size_t entries_to_remove = associations_.size() - max_primary_;
167  std::partial_sort(entries.begin(),
168                    entries.begin() + entries_to_remove,
169                    entries.end(),
170                    &EntrySortByTimeAscending);
171
172  for (size_t i = 0; i < entries_to_remove; ++i) {
173    const std::string& query = *entries[i].query;
174    store_->Delete(query);
175    associations_.erase(query);
176  }
177}
178
179}  // namespace app_list
180