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|. |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.
| |
32 // decrease as if it's a current time. | |
33 // 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.
| |
34 template <class T> | |
35 class MovingMaxCounter { | |
36 public: | |
37 explicit MovingMaxCounter(int64_t window_length_ms); | |
38 // Adds new sample at a given current time. | |
39 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.
| |
40 // Returns max sample in window ending at a given current time. | |
41 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.
| |
42 void Reset(); | |
43 | |
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
| |
44 private: | |
45 // Throws out obsolete samples. Is |const| because it is always safe to throw | |
46 // out old elements as long as |time_ms| parameters to public methods are | |
47 // always increasing. | |
48 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.
| |
49 const int64_t window_length_ms_; | |
50 // Samples in the window are stored as pairs <time, sample> in this deque in | |
51 // chronological order. Samples what can't be maximum in any window are | |
52 // thrown out - deque always contains non-increasing sequence of samples. | |
53 // Is |mutable| because |MovingMax()| may be called on const instances yet it | |
54 // will remove obsolete samples to speed up consecutive calls. | |
55 mutable std::deque<std::pair<int64_t, T>> samples_; | |
56 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.
| |
57 | |
58 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.
| |
59 }; | |
60 | |
61 template <class T> | |
62 MovingMaxCounter<T>::MovingMaxCounter(int64_t window_length_ms) | |
63 : window_length_ms_(window_length_ms), | |
64 last_call_time_ms_(std::numeric_limits<int64_t>::min()) {} | |
65 | |
66 template <class T> | |
67 void MovingMaxCounter<T>::Add(const T& sample, int64_t time_ms) { | |
68 RTC_DCHECK_GE(time_ms, last_call_time_ms_); | |
69 last_call_time_ms_ = time_ms; | |
70 RollWindow(time_ms); | |
71 // Remove samples what will never be maximum in any window: newly added sample | |
72 // will always be in all windows the previous samples are. Thus, smaller | |
73 // samples could be removed. This will maintain the invariant - deque contains | |
74 // non-increasing sequence of values. | |
75 while (!samples_.empty() && samples_.back().second < sample) { | |
76 samples_.pop_back(); | |
77 } | |
78 // Add the new sample but only if there's no existing sample at the same time. | |
79 // Due to checks above, already existing element will be larger and new sample | |
80 // will never be a maximum in any window. | |
81 if (samples_.empty() || samples_.back().first < time_ms) { | |
82 samples_.emplace_back(std::make_pair(time_ms, sample)); | |
83 } | |
84 } | |
85 | |
86 template <class T> | |
87 rtc::Optional<T> MovingMaxCounter<T>::Max(int64_t time_ms) const { | |
88 RTC_DCHECK_GE(time_ms, last_call_time_ms_); | |
89 last_call_time_ms_ = time_ms; | |
90 RollWindow(time_ms); | |
91 rtc::Optional<T> res; | |
92 if (!samples_.empty()) { | |
93 res.emplace(samples_.front().second); | |
94 } | |
95 return res; | |
96 } | |
97 | |
98 template <class T> | |
99 void MovingMaxCounter<T>::Reset() { | |
100 samples_.clear(); | |
101 } | |
102 | |
103 template <class T> | |
104 void MovingMaxCounter<T>::RollWindow(int64_t time_ms) const { | |
105 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.
| |
106 while (!samples_.empty() && samples_.front().first < window_begin_ms) { | |
107 samples_.pop_front(); | |
108 } | |
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.
| |
109 } | |
110 | |
111 } // namespace rtc | |
112 | |
113 #endif // WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_ | |
OLD | NEW |