OLD | NEW |
(Empty) | |
| 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 WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_ |
| 12 #define WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_ |
| 13 |
| 14 #include <stdint.h> |
| 15 |
| 16 #include <deque> |
| 17 #include <limits> |
| 18 #include <utility> |
| 19 |
| 20 #include "webrtc/rtc_base/checks.h" |
| 21 #include "webrtc/rtc_base/constructormagic.h" |
| 22 #include "webrtc/rtc_base/optional.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 rtc::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> |
| 64 MovingMaxCounter<T>::MovingMaxCounter(int64_t window_length_ms) |
| 65 : window_length_ms_(window_length_ms) {} |
| 66 |
| 67 template <class T> |
| 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> |
| 86 rtc::Optional<T> MovingMaxCounter<T>::Max(int64_t current_time_ms) { |
| 87 RollWindow(current_time_ms); |
| 88 rtc::Optional<T> res; |
| 89 if (!samples_.empty()) { |
| 90 res.emplace(samples_.front().second); |
| 91 } |
| 92 return res; |
| 93 } |
| 94 |
| 95 template <class T> |
| 96 void MovingMaxCounter<T>::Reset() { |
| 97 samples_.clear(); |
| 98 } |
| 99 |
| 100 template <class T> |
| 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 // WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_ |
OLD | NEW |