Index: webrtc/rtc_base/moving_max_counter.h |
diff --git a/webrtc/rtc_base/moving_max_counter.h b/webrtc/rtc_base/moving_max_counter.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..296d264af6b690c38615805aea028b5d1bc9c153 |
--- /dev/null |
+++ b/webrtc/rtc_base/moving_max_counter.h |
@@ -0,0 +1,113 @@ |
+/* |
+ * Copyright (c) 2017 The WebRTC project authors. All Rights Reserved. |
+ * |
+ * Use of this source code is governed by a BSD-style license |
+ * that can be found in the LICENSE file in the root of the source |
+ * tree. An additional intellectual property rights grant can be found |
+ * in the file PATENTS. All contributing project authors may |
+ * be found in the AUTHORS file in the root of the source tree. |
+ */ |
+ |
+#ifndef WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_ |
+#define WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_ |
+ |
+#include <stdint.h> |
+ |
+#include <deque> |
+#include <limits> |
+#include <utility> |
+ |
+#include "webrtc/rtc_base/checks.h" |
+#include "webrtc/rtc_base/constructormagic.h" |
+#include "webrtc/rtc_base/optional.h" |
+ |
+namespace rtc { |
+ |
+// Implements moving max: can add samples to it and calculate maximum over some |
+// fixed moving window. |
+// |
+// Window size is configured at constructor. |
+// Samples can be added with |Add()| and max over current window is returned by |
+// |MovingMax|. |time_ms| in consecutive calls to Add and MovingMax should never |
kwiberg-webrtc
2017/08/22 11:13:30
consecutive -> successive
ilnik
2017/08/22 12:03:56
Done.
|
+// decrease as if it's a current time. |
+// Not thread-safe. |
kwiberg-webrtc
2017/08/22 11:13:30
Specifically, "Not thread-safe even if you only ca
ilnik
2017/08/22 12:03:56
Done.
|
+template <class T> |
+class MovingMaxCounter { |
+ public: |
+ explicit MovingMaxCounter(int64_t window_length_ms); |
+ // Adds new sample at a given current time. |
+ void Add(const T& sample, int64_t time_ms); |
kwiberg-webrtc
2017/08/22 11:13:30
"Advances the current time, and adds a new sample.
ilnik
2017/08/22 12:03:56
Advancing a current time is internal logic, not im
kwiberg-webrtc
2017/08/22 12:35:37
The reason I suggested mentioning it here, or even
ilnik
2017/08/22 13:04:38
Ok, I agree, This has to be mentioned here.
|
+ // Returns max sample in window ending at a given current time. |
+ rtc::Optional<T> Max(int64_t time_ms) const; |
kwiberg-webrtc
2017/08/22 11:13:29
"Advances the current time, and returns the maximu
ilnik
2017/08/22 12:03:56
Ditto.
|
+ void Reset(); |
+ |
kwiberg-webrtc
2017/08/22 11:13:30
Hmm. It's slightly difficult to document Add() and
ilnik
2017/08/22 12:03:56
The time advancement is an internal thing only. Th
kwiberg-webrtc
2017/08/22 12:35:38
Well, you can say that it's "internal" and "implem
ilnik
2017/08/22 13:04:38
Callers need to be aware only of one condition: ti
kwiberg-webrtc
2017/08/22 13:28:40
OK, so no separate AdvanceTime() method---that's f
ilnik
2017/08/22 14:11:34
It may be quite bad. I don't like that It complete
kwiberg-webrtc
2017/08/22 21:40:46
Hmm. None of the options are particularly appealin
ilnik
2017/08/23 07:46:50
Yes, I'll try to make it non const. Instead, as in
|
+ private: |
+ // Throws out obsolete samples. Is |const| because it is always safe to throw |
+ // out old elements as long as |time_ms| parameters to public methods are |
+ // always increasing. |
+ void RollWindow(int64_t time_ms) const; |
kwiberg-webrtc
2017/08/22 11:13:30
I don't really like that this is const---conceptua
ilnik
2017/08/22 12:03:56
The problem is that Max() is assumed to be const i
kwiberg-webrtc
2017/08/22 12:35:37
This is not true. Consider
c.Add(1, 1);
Foo(&
ilnik
2017/08/22 13:04:38
Yes, it's hard to reflect the realtime-clock prope
kwiberg-webrtc
2017/08/22 13:28:41
I agree.
|
+ const int64_t window_length_ms_; |
+ // Samples in the window are stored as pairs <time, sample> in this deque in |
+ // chronological order. Samples what can't be maximum in any window are |
+ // thrown out - deque always contains non-increasing sequence of samples. |
+ // Is |mutable| because |MovingMax()| may be called on const instances yet it |
+ // will remove obsolete samples to speed up consecutive calls. |
+ mutable std::deque<std::pair<int64_t, T>> samples_; |
+ mutable int64_t last_call_time_ms_; |
kwiberg-webrtc
2017/08/22 11:13:30
Is last_call_time_ms_ necessary? Couldn't you just
ilnik
2017/08/22 12:03:56
It's necessary. We also need Max() to be called in
kwiberg-webrtc
2017/08/22 12:35:38
If Max() is in fact called in the correct temporal
ilnik
2017/08/22 13:04:38
Done.
|
+ |
+ RTC_DISALLOW_COPY_AND_ASSIGN(MovingMaxCounter); |
kwiberg-webrtc
2017/08/22 11:13:30
Why? Copying a MovingMaxCounter should not be prob
ilnik
2017/08/22 12:03:56
It doesn't introduce any problems, only if the rea
kwiberg-webrtc
2017/08/22 12:35:37
OK. Keep this as-is for now.
|
+}; |
+ |
+template <class T> |
+MovingMaxCounter<T>::MovingMaxCounter(int64_t window_length_ms) |
+ : window_length_ms_(window_length_ms), |
+ last_call_time_ms_(std::numeric_limits<int64_t>::min()) {} |
+ |
+template <class T> |
+void MovingMaxCounter<T>::Add(const T& sample, int64_t time_ms) { |
+ RTC_DCHECK_GE(time_ms, last_call_time_ms_); |
+ last_call_time_ms_ = time_ms; |
+ RollWindow(time_ms); |
+ // Remove samples what will never be maximum in any window: newly added sample |
+ // will always be in all windows the previous samples are. Thus, smaller |
+ // samples could be removed. This will maintain the invariant - deque contains |
+ // non-increasing sequence of values. |
+ while (!samples_.empty() && samples_.back().second < sample) { |
+ samples_.pop_back(); |
+ } |
+ // Add the new sample but only if there's no existing sample at the same time. |
+ // Due to checks above, already existing element will be larger and new sample |
+ // will never be a maximum in any window. |
+ if (samples_.empty() || samples_.back().first < time_ms) { |
+ samples_.emplace_back(std::make_pair(time_ms, sample)); |
+ } |
+} |
+ |
+template <class T> |
+rtc::Optional<T> MovingMaxCounter<T>::Max(int64_t time_ms) const { |
+ RTC_DCHECK_GE(time_ms, last_call_time_ms_); |
+ last_call_time_ms_ = time_ms; |
+ RollWindow(time_ms); |
+ rtc::Optional<T> res; |
+ if (!samples_.empty()) { |
+ res.emplace(samples_.front().second); |
+ } |
+ return res; |
+} |
+ |
+template <class T> |
+void MovingMaxCounter<T>::Reset() { |
+ samples_.clear(); |
+} |
+ |
+template <class T> |
+void MovingMaxCounter<T>::RollWindow(int64_t time_ms) const { |
+ int64_t window_begin_ms = time_ms - window_length_ms_; |
kwiberg-webrtc
2017/08/22 11:13:30
const
ilnik
2017/08/22 12:03:56
Done.
|
+ while (!samples_.empty() && samples_.front().first < window_begin_ms) { |
+ samples_.pop_front(); |
+ } |
kwiberg-webrtc
2017/08/22 11:13:30
I'm guessing it'll be faster (but not by a huge ma
ilnik
2017/08/22 12:03:56
Done.
|
+} |
+ |
+} // namespace rtc |
+ |
+#endif // WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_ |