1// Copyright (c) 2012 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/history/visit_filter.h"
6
7#include <math.h>
8
9#include <algorithm>
10
11#include "base/logging.h"
12#include "base/time/time.h"
13#include "components/history/core/browser/history_types.h"
14
15namespace history {
16
17const double kLn2 = 0.6931471805599453;
18
19VisitFilter::VisitFilter()
20    : day_(DAY_UNDEFINED),
21      max_results_(0),
22      sorting_order_(ORDER_BY_RECENCY) {
23}
24
25VisitFilter::~VisitFilter() {
26}
27
28void VisitFilter::SetFilterTime(const base::Time& filter_time) {
29  filter_time_ = filter_time;
30  UpdateTimeVector();
31}
32
33void VisitFilter::SetFilterWidth(const base::TimeDelta& filter_width) {
34  filter_width_ = filter_width;
35  UpdateTimeVector();
36}
37
38void VisitFilter::SetDayOfTheWeekFilter(int day) {
39  day_ = day;
40  UpdateTimeVector();
41}
42
43void VisitFilter::SetDayTypeFilter(bool workday) {
44  day_ = workday ? WORKDAY : HOLIDAY;
45  UpdateTimeVector();
46}
47
48void VisitFilter::ClearFilters() {
49  filter_time_ = base::Time();
50  filter_width_ = base::TimeDelta::FromHours(0);
51  day_ = DAY_UNDEFINED;
52  UpdateTimeVector();
53}
54
55bool VisitFilter::UpdateTimeVector() {
56
57  TimeVector days_of_the_week;
58  if (day_ >= 0 && day_ <= 6) {
59    GetTimesOnTheDayOfTheWeek(day_, filter_time_, max_results_,
60                              &days_of_the_week);
61  } else if (day_ == WORKDAY || day_ == HOLIDAY) {
62    GetTimesOnTheSameDayType(
63        (day_ == WORKDAY), filter_time_, max_results_, &days_of_the_week);
64  }
65
66  TimeVector times_of_the_day;
67  if (filter_width_ != base::TimeDelta::FromSeconds(0)) {
68    if (sorting_order_ == ORDER_BY_TIME_GAUSSIAN) {
69      // Limit queries to 5 standard deviations.
70      GetTimesInRange(filter_time_ - 5 * filter_width_,
71                      filter_time_ + 5 * filter_width_,
72                      max_results_, &times_of_the_day);
73    } else {
74      GetTimesInRange(filter_time_ - filter_width_,
75                      filter_time_ + filter_width_,
76                      max_results_, &times_of_the_day);
77    }
78  }
79
80  if (times_of_the_day.empty()) {
81    if (days_of_the_week.empty())
82      times_.clear();
83    else
84      times_.swap(days_of_the_week);
85  } else {
86    if (days_of_the_week.empty())
87      times_.swap(times_of_the_day);
88    else
89      IntersectTimeVectors(times_of_the_day, days_of_the_week, &times_);
90  }
91
92  return !times_.empty();
93}
94
95// static
96void VisitFilter::GetTimesInRange(base::Time begin_time_of_the_day,
97                                  base::Time end_time_of_the_day,
98                                  size_t max_results,
99                                  TimeVector* times) {
100  DCHECK(times);
101  times->clear();
102  times->reserve(max_results);
103  const size_t kMaxReturnedResults = 62;  // 2 months (<= 62 days).
104
105  if (!max_results)
106    max_results = kMaxReturnedResults;
107
108  // If range is more than 24 hours, return a contiguous interval covering
109  // |max_results| days.
110  base::TimeDelta one_day = base::TimeDelta::FromDays(1);
111  if (end_time_of_the_day - begin_time_of_the_day >= one_day) {
112    times->push_back(
113        std::make_pair(begin_time_of_the_day - one_day * (max_results - 1),
114                       end_time_of_the_day));
115    return;
116  }
117
118  for (size_t i = 0; i < max_results; ++i) {
119    times->push_back(
120        std::make_pair(begin_time_of_the_day - base::TimeDelta::FromDays(i),
121                       end_time_of_the_day - base::TimeDelta::FromDays(i)));
122  }
123}
124
125double VisitFilter::GetVisitScore(const VisitRow& visit) const {
126  // Decay score by half each week.
127  base::TimeDelta time_passed = filter_time_ - visit.visit_time;
128  // Clamp to 0 in case time jumps backwards (e.g. due to DST).
129  double decay_exponent = std::max(0.0, kLn2 * static_cast<double>(
130      time_passed.InMicroseconds()) / base::Time::kMicrosecondsPerWeek);
131  double staleness = 1.0 / exp(decay_exponent);
132
133  double score = 0;
134  switch (sorting_order()) {
135    case ORDER_BY_RECENCY:
136      score = 1.0;  // Let the staleness factor take care of it.
137      break;
138    case ORDER_BY_VISIT_COUNT:
139      score = 1.0;  // Every visit counts the same.
140      staleness = 1.0;  // No decay on this one.
141      break;
142    case ORDER_BY_TIME_GAUSSIAN: {
143      double offset =
144          GetTimeOfDayDifference(filter_time_,
145                                 visit.visit_time).InMicroseconds();
146      double sd = filter_width_.InMicroseconds();
147
148      // Calculate score using the normal distribution density function.
149      score = exp(-(offset * offset) / (2 * sd * sd));
150      break;
151    }
152    case ORDER_BY_TIME_LINEAR: {
153      base::TimeDelta offset = GetTimeOfDayDifference(filter_time_,
154                                                      visit.visit_time);
155      if (offset > filter_width_) {
156        score = 0;
157      } else {
158        score = 1 - offset.InMicroseconds() / static_cast<double>(
159            filter_width_.InMicroseconds());
160      }
161      break;
162    }
163    case ORDER_BY_DURATION_SPENT:
164    default:
165      NOTREACHED() << "Not implemented!";
166  }
167  return staleness * score;
168}
169
170base::TimeDelta
171VisitFilter::GetTimeOfDayDifference(base::Time t1, base::Time t2) {
172  base::TimeDelta time_of_day1 = t1 - t1.LocalMidnight();
173  base::TimeDelta time_of_day2 = t2 - t2.LocalMidnight();
174
175  base::TimeDelta difference;
176  if (time_of_day1 < time_of_day2)
177    difference = time_of_day2 - time_of_day1;
178  else
179    difference = time_of_day1 - time_of_day2;
180
181  // If the difference is more than 12 hours, we'll get closer by 'wrapping'
182  // around the day barrier.
183  if (difference > base::TimeDelta::FromHours(12))
184    difference = base::TimeDelta::FromHours(24) - difference;
185
186  return difference;
187}
188
189// static
190void VisitFilter::GetTimesOnTheDayOfTheWeek(int day,
191                                            base::Time week,
192                                            size_t max_results,
193                                            TimeVector* times) {
194  DCHECK(times);
195
196  base::Time::Exploded exploded_time;
197  if (week.is_null())
198    week = base::Time::Now();
199  week.LocalExplode(&exploded_time);
200  base::TimeDelta shift = base::TimeDelta::FromDays(
201      exploded_time.day_of_week - day);
202
203  base::Time day_base = week.LocalMidnight();
204  day_base -= shift;
205
206  times->clear();
207  times->reserve(max_results);
208
209  base::TimeDelta one_day = base::TimeDelta::FromDays(1);
210
211  const size_t kMaxReturnedResults = 9;  // 2 months (<= 9 weeks).
212
213  if (!max_results)
214    max_results = kMaxReturnedResults;
215
216  for (size_t i = 0; i < max_results; ++i) {
217    times->push_back(
218        std::make_pair(day_base - base::TimeDelta::FromDays(i * 7),
219                       day_base + one_day - base::TimeDelta::FromDays(i * 7)));
220  }
221}
222
223// static
224void VisitFilter::GetTimesOnTheSameDayType(bool workday,
225                                           base::Time week,
226                                           size_t max_results,
227                                           TimeVector* times) {
228  DCHECK(times);
229  if (week.is_null())
230    week = base::Time::Now();
231  // TODO(georgey): internationalize workdays/weekends/holidays.
232  if (!workday) {
233    TimeVector sunday;
234    TimeVector saturday;
235    base::Time::Exploded exploded_time;
236    week.LocalExplode(&exploded_time);
237
238    GetTimesOnTheDayOfTheWeek(exploded_time.day_of_week ? 7 : 0, week,
239                              max_results, &sunday);
240    GetTimesOnTheDayOfTheWeek(exploded_time.day_of_week ? 6 : -1, week,
241                              max_results, &saturday);
242    UniteTimeVectors(sunday, saturday, times);
243    if (max_results && times->size() > max_results)
244      times->resize(max_results);
245  } else {
246    TimeVector vectors[3];
247    GetTimesOnTheDayOfTheWeek(1, week, max_results, &vectors[0]);
248    for (size_t i = 2; i <= 5; ++i) {
249      GetTimesOnTheDayOfTheWeek(i, week, max_results, &vectors[(i - 1) % 3]);
250      UniteTimeVectors(vectors[(i - 2) % 3], vectors[(i - 1) % 3],
251                       &vectors[i % 3]);
252      if (max_results && vectors[i % 3].size() > max_results)
253        vectors[i % 3].resize(max_results);
254      vectors[i % 3].swap(vectors[(i - 1) % 3]);
255    }
256    // 1 == 5 - 1 % 3
257    times->swap(vectors[1]);
258  }
259}
260
261// static
262bool VisitFilter::UniteTimeVectors(const TimeVector& vector1,
263                                   const TimeVector& vector2,
264                                   TimeVector* result) {
265  // The vectors are sorted going back in time, but each pair has |first| as the
266  // beginning of time period and |second| as the end, for example:
267  // { 19:20, 20:00 } { 17:00, 18:10 } { 11:33, 11:35 }...
268  // The pairs in one vector are guaranteed not to intersect.
269  DCHECK(result);
270  result->clear();
271  result->reserve(vector1.size() + vector2.size());
272
273  size_t vi[2];
274  const TimeVector* vectors[2] = { &vector1, &vector2 };
275  for (vi[0] = 0, vi[1] = 0;
276       vi[0] < vectors[0]->size() && vi[1] < vectors[1]->size();) {
277    std::pair<base::Time, base::Time> united_timeslot;
278    // Check which element occurs later (for the following diagrams time is
279    // increasing to the right, 'f' means first, 's' means second).
280    // after the folowing 2 statements:
281    // vectors[iterator_index][vi[iterator_index]]           f---s
282    // vectors[1 - iterator_index][vi[1 - iterator_index]]  f---s
283    // united_timeslot                                       f---s
284    // or
285    // vectors[iterator_index][vi[iterator_index]]           f---s
286    // vectors[1 - iterator_index][vi[1 - iterator_index]]    f-s
287    // united_timeslot                                       f---s
288    size_t iterator_index =
289        ((*vectors[0])[vi[0]].second >= (*vectors[1])[vi[1]].second) ? 0 : 1;
290    united_timeslot = (*vectors[iterator_index])[vi[iterator_index]];
291    ++vi[iterator_index];
292    bool added_timeslot;
293    // Merge all timeslots intersecting with |united_timeslot|.
294    do {
295      added_timeslot = false;
296      for (size_t i = 0; i <= 1; ++i) {
297        if (vi[i] < vectors[i]->size() &&
298            (*vectors[i])[vi[i]].second >= united_timeslot.first) {
299          // vectors[i][vi[i]]           f---s
300          // united_timeslot               f---s
301          // or
302          // united_timeslot            f------s
303          added_timeslot = true;
304          if ((*vectors[i])[vi[i]].first < united_timeslot.first) {
305            // vectors[i][vi[i]]           f---s
306            // united_timeslot               f---s
307            // results in:
308            // united_timeslot             f-----s
309            united_timeslot.first = (*vectors[i])[vi[i]].first;
310          }
311          ++vi[i];
312        }
313      }
314    } while (added_timeslot);
315    result->push_back(united_timeslot);
316  }
317  for (size_t i = 0; i <= 1; ++i) {
318    for (; vi[i] < vectors[i]->size(); ++vi[i])
319      result->push_back((*vectors[i])[vi[i]]);
320  }
321  return !result->empty();
322}
323
324// static
325bool VisitFilter::IntersectTimeVectors(const TimeVector& vector1,
326                                       const TimeVector& vector2,
327                                       TimeVector* result) {
328  DCHECK(result);
329  result->clear();
330  result->reserve(std::max(vector1.size(), vector2.size()));
331
332  TimeVector::const_iterator vi[2];
333  for (vi[0] = vector1.begin(), vi[1] = vector2.begin();
334       vi[0] != vector1.end() && vi[1] != vector2.end();) {
335    size_t it_index = (vi[0]->second >= vi[1]->second) ? 0 : 1;
336    if (vi[it_index]->first >= vi[1 - it_index]->second) {
337      // vector 1    ++++
338      // vector 2 ++
339      ++vi[it_index];
340    } else if (vi[it_index]->first >= vi[1 - it_index]->first) {
341      // vector 1    ++++
342      // vector 2 +++++
343      result->push_back(std::make_pair(vi[it_index]->first,
344                                       vi[1 - it_index]->second));
345      ++vi[it_index];
346    } else {
347      // vector 1 ++++
348      // vector 2  ++
349      result->push_back(std::make_pair(vi[1 - it_index]->first,
350                                       vi[1 - it_index]->second));
351      ++vi[1 - it_index];
352    }
353  }
354
355  return !result->empty();
356}
357
358}  // namespace history
359