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
23 namespace rtc {
24
25 // Implements moving max: can add samples to it and calculate maximum over some
26 // fixed moving window.
27 //
28 // Window size is configured at constructor.
29 // Samples can be added with `Add()` and max over current window is returned by
30 // `MovingMax`. `current_time_ms` in successive calls to Add and MovingMax
31 // should never decrease as if it's a wallclock time.
32 template <class T>
33 class MovingMaxCounter {
34 public:
35 explicit MovingMaxCounter(int64_t window_length_ms);
36
37 MovingMaxCounter(const MovingMaxCounter&) = delete;
38 MovingMaxCounter& operator=(const MovingMaxCounter&) = delete;
39
40 // Advances the current time, and adds a new sample. The new current time must
41 // be at least as large as the old current time.
42 void Add(const T& sample, int64_t current_time_ms);
43 // Advances the current time, and returns the maximum sample in the time
44 // window ending at the current time. The new current time must be at least as
45 // large as the old current time.
46 absl::optional<T> Max(int64_t current_time_ms);
47 void Reset();
48
49 private:
50 // Throws out obsolete samples.
51 void RollWindow(int64_t new_time_ms);
52 const int64_t window_length_ms_;
53 // This deque stores (timestamp, sample) pairs in chronological order; new
54 // pairs are only ever added at the end. However, because they can't affect
55 // the Max() calculation, pairs older than window_length_ms_ are discarded,
56 // and if an older pair has a sample that's smaller than that of a younger
57 // pair, the older pair is discarded. As a result, the sequence of timestamps
58 // is strictly increasing, and the sequence of samples is strictly decreasing.
59 std::deque<std::pair<int64_t, T>> samples_;
60 #if RTC_DCHECK_IS_ON
61 int64_t last_call_time_ms_ = std::numeric_limits<int64_t>::min();
62 #endif
63 };
64
65 template <class T>
MovingMaxCounter(int64_t window_length_ms)66 MovingMaxCounter<T>::MovingMaxCounter(int64_t window_length_ms)
67 : window_length_ms_(window_length_ms) {}
68
69 template <class T>
Add(const T & sample,int64_t current_time_ms)70 void MovingMaxCounter<T>::Add(const T& sample, int64_t current_time_ms) {
71 RollWindow(current_time_ms);
72 // Remove samples that will never be maximum in any window: newly added sample
73 // will always be in all windows the previous samples are. Thus, smaller or
74 // equal samples could be removed. This will maintain the invariant - deque
75 // contains strictly decreasing sequence of values.
76 while (!samples_.empty() && samples_.back().second <= sample) {
77 samples_.pop_back();
78 }
79 // Add the new sample but only if there's no existing sample at the same time.
80 // Due to checks above, the already existing element will be larger, so the
81 // new sample will never be the maximum in any window.
82 if (samples_.empty() || samples_.back().first < current_time_ms) {
83 samples_.emplace_back(std::make_pair(current_time_ms, sample));
84 }
85 }
86
87 template <class T>
Max(int64_t current_time_ms)88 absl::optional<T> MovingMaxCounter<T>::Max(int64_t current_time_ms) {
89 RollWindow(current_time_ms);
90 absl::optional<T> res;
91 if (!samples_.empty()) {
92 res.emplace(samples_.front().second);
93 }
94 return res;
95 }
96
97 template <class T>
Reset()98 void MovingMaxCounter<T>::Reset() {
99 samples_.clear();
100 }
101
102 template <class T>
RollWindow(int64_t new_time_ms)103 void MovingMaxCounter<T>::RollWindow(int64_t new_time_ms) {
104 #if RTC_DCHECK_IS_ON
105 RTC_DCHECK_GE(new_time_ms, last_call_time_ms_);
106 last_call_time_ms_ = new_time_ms;
107 #endif
108 const int64_t window_begin_ms = new_time_ms - window_length_ms_;
109 auto it = samples_.begin();
110 while (it != samples_.end() && it->first < window_begin_ms) {
111 ++it;
112 }
113 samples_.erase(samples_.begin(), it);
114 }
115
116 } // namespace rtc
117
118 #endif // RTC_BASE_NUMERICS_MOVING_MAX_COUNTER_H_
119