1 /*
2 * Copyright (c) 2017 The WebRTC project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #ifndef RTC_BASE_NUMERICS_MOVING_MAX_COUNTER_H_
12 #define RTC_BASE_NUMERICS_MOVING_MAX_COUNTER_H_
13
14 #include <stdint.h>
15
16 #include <deque>
17 #include <limits>
18 #include <utility>
19
20 #include "absl/types/optional.h"
21 #include "rtc_base/checks.h"
22 #include "rtc_base/constructor_magic.h"
23
24 namespace rtc {
25
26 // Implements moving max: can add samples to it and calculate maximum over some
27 // fixed moving window.
28 //
29 // Window size is configured at constructor.
30 // Samples can be added with |Add()| and max over current window is returned by
31 // |MovingMax|. |current_time_ms| in successive calls to Add and MovingMax
32 // should never decrease as if it's a wallclock time.
33 template <class T>
34 class MovingMaxCounter {
35 public:
36 explicit MovingMaxCounter(int64_t window_length_ms);
37 // Advances the current time, and adds a new sample. The new current time must
38 // be at least as large as the old current time.
39 void Add(const T& sample, int64_t current_time_ms);
40 // Advances the current time, and returns the maximum sample in the time
41 // window ending at the current time. The new current time must be at least as
42 // large as the old current time.
43 absl::optional<T> Max(int64_t current_time_ms);
44 void Reset();
45
46 private:
47 // Throws out obsolete samples.
48 void RollWindow(int64_t new_time_ms);
49 const int64_t window_length_ms_;
50 // This deque stores (timestamp, sample) pairs in chronological order; new
51 // pairs are only ever added at the end. However, because they can't affect
52 // the Max() calculation, pairs older than window_length_ms_ are discarded,
53 // and if an older pair has a sample that's smaller than that of a younger
54 // pair, the older pair is discarded. As a result, the sequence of timestamps
55 // is strictly increasing, and the sequence of samples is strictly decreasing.
56 std::deque<std::pair<int64_t, T>> samples_;
57 #if RTC_DCHECK_IS_ON
58 int64_t last_call_time_ms_ = std::numeric_limits<int64_t>::min();
59 #endif
60 RTC_DISALLOW_COPY_AND_ASSIGN(MovingMaxCounter);
61 };
62
63 template <class T>
MovingMaxCounter(int64_t window_length_ms)64 MovingMaxCounter<T>::MovingMaxCounter(int64_t window_length_ms)
65 : window_length_ms_(window_length_ms) {}
66
67 template <class T>
Add(const T & sample,int64_t current_time_ms)68 void MovingMaxCounter<T>::Add(const T& sample, int64_t current_time_ms) {
69 RollWindow(current_time_ms);
70 // Remove samples that will never be maximum in any window: newly added sample
71 // will always be in all windows the previous samples are. Thus, smaller or
72 // equal samples could be removed. This will maintain the invariant - deque
73 // contains strictly decreasing sequence of values.
74 while (!samples_.empty() && samples_.back().second <= sample) {
75 samples_.pop_back();
76 }
77 // Add the new sample but only if there's no existing sample at the same time.
78 // Due to checks above, the already existing element will be larger, so the
79 // new sample will never be the maximum in any window.
80 if (samples_.empty() || samples_.back().first < current_time_ms) {
81 samples_.emplace_back(std::make_pair(current_time_ms, sample));
82 }
83 }
84
85 template <class T>
Max(int64_t current_time_ms)86 absl::optional<T> MovingMaxCounter<T>::Max(int64_t current_time_ms) {
87 RollWindow(current_time_ms);
88 absl::optional<T> res;
89 if (!samples_.empty()) {
90 res.emplace(samples_.front().second);
91 }
92 return res;
93 }
94
95 template <class T>
Reset()96 void MovingMaxCounter<T>::Reset() {
97 samples_.clear();
98 }
99
100 template <class T>
RollWindow(int64_t new_time_ms)101 void MovingMaxCounter<T>::RollWindow(int64_t new_time_ms) {
102 #if RTC_DCHECK_IS_ON
103 RTC_DCHECK_GE(new_time_ms, last_call_time_ms_);
104 last_call_time_ms_ = new_time_ms;
105 #endif
106 const int64_t window_begin_ms = new_time_ms - window_length_ms_;
107 auto it = samples_.begin();
108 while (it != samples_.end() && it->first < window_begin_ms) {
109 ++it;
110 }
111 samples_.erase(samples_.begin(), it);
112 }
113
114 } // namespace rtc
115
116 #endif // RTC_BASE_NUMERICS_MOVING_MAX_COUNTER_H_
117