Templatize percentile_filter.h and move it to base/analytics.
BUG=None
Review-Url: https://codereview.webrtc.org/2529063002
Cr-Original-Commit-Position: refs/heads/master@{#15334}
Cr-Mirrored-From: https://chromium.googlesource.com/external/webrtc
Cr-Mirrored-Commit: cb861e074a1988715b5d84511fecdc52b7d7091c
diff --git a/BUILD.gn b/BUILD.gn
index 0bae0aa..e5a6d4c 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -370,6 +370,7 @@
sources = [
"api/fakemetricsobserver.cc",
"base/analytics/exp_filter_unittest.cc",
+ "base/analytics/percentile_filter_unittest.cc",
"base/array_view_unittest.cc",
"base/atomicops_unittest.cc",
"base/autodetectproxy_unittest.cc",
diff --git a/base/BUILD.gn b/base/BUILD.gn
index 5d19957..69ba772 100644
--- a/base/BUILD.gn
+++ b/base/BUILD.gn
@@ -340,6 +340,10 @@
sources = [
"analytics/exp_filter.cc",
"analytics/exp_filter.h",
+ "analytics/percentile_filter.h",
+ ]
+ deps = [
+ ":rtc_base_approved",
]
}
diff --git a/base/analytics/percentile_filter.h b/base/analytics/percentile_filter.h
new file mode 100644
index 0000000..b3c8f8d
--- /dev/null
+++ b/base/analytics/percentile_filter.h
@@ -0,0 +1,113 @@
+/*
+ * Copyright (c) 2016 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_BASE_ANALYTICS_PERCENTILE_FILTER_H_
+#define WEBRTC_BASE_ANALYTICS_PERCENTILE_FILTER_H_
+
+#include <stdint.h>
+
+#include <iterator>
+#include <set>
+
+#include "webrtc/base/checks.h"
+
+namespace webrtc {
+
+// Class to efficiently get the percentile value from a group of observations.
+// The percentile is the value below which a given percentage of the
+// observations fall.
+template <typename T>
+class PercentileFilter {
+ public:
+ // Construct filter. |percentile| should be between 0 and 1.
+ explicit PercentileFilter(float percentile);
+
+ // Insert one observation. The complexity of this operation is logarithmic in
+ // the size of the container.
+ void Insert(const T& value);
+
+ // Remove one observation. The complexity of this operation is logarithmic in
+ // the size of the container.
+ void Erase(const T& value);
+
+ // Get the percentile value. The complexity of this operation is constant.
+ T GetPercentileValue() const;
+
+ private:
+ // Update iterator and index to point at target percentile value.
+ void UpdatePercentileIterator();
+
+ const float percentile_;
+ std::multiset<T> set_;
+ // Maintain iterator and index of current target percentile value.
+ typename std::multiset<T>::iterator percentile_it_;
+ int64_t percentile_index_;
+};
+
+template <typename T>
+PercentileFilter<T>::PercentileFilter(float percentile)
+ : percentile_(percentile),
+ percentile_it_(set_.begin()),
+ percentile_index_(0) {
+ RTC_CHECK_GE(percentile, 0.0f);
+ RTC_CHECK_LE(percentile, 1.0f);
+}
+
+template <typename T>
+void PercentileFilter<T>::Insert(const T& value) {
+ // Insert element at the upper bound.
+ set_.insert(value);
+ if (set_.size() == 1u) {
+ // First element inserted - initialize percentile iterator and index.
+ percentile_it_ = set_.begin();
+ percentile_index_ = 0;
+ } else if (value < *percentile_it_) {
+ // If new element is before us, increment |percentile_index_|.
+ ++percentile_index_;
+ }
+ UpdatePercentileIterator();
+}
+
+template <typename T>
+void PercentileFilter<T>::Erase(const T& value) {
+ typename std::multiset<T>::const_iterator it = set_.lower_bound(value);
+ // Ignore erase operation if the element is not present in the current set.
+ if (it == set_.end() || *it != value)
+ return;
+ if (it == percentile_it_) {
+ // If same iterator, update to the following element. Index is not
+ // affected.
+ percentile_it_ = set_.erase(it);
+ } else {
+ set_.erase(it);
+ // If erased element was before us, decrement |percentile_index_|.
+ if (value <= *percentile_it_)
+ --percentile_index_;
+ }
+ UpdatePercentileIterator();
+}
+
+template <typename T>
+void PercentileFilter<T>::UpdatePercentileIterator() {
+ if (set_.empty())
+ return;
+ const int64_t index = static_cast<int64_t>(percentile_ * (set_.size() - 1));
+ std::advance(percentile_it_, index - percentile_index_);
+ percentile_index_ = index;
+}
+
+template <typename T>
+T PercentileFilter<T>::GetPercentileValue() const {
+ return set_.empty() ? 0 : *percentile_it_;
+}
+
+} // namespace webrtc
+
+#endif // WEBRTC_BASE_ANALYTICS_PERCENTILE_FILTER_H_
diff --git a/modules/video_coding/percentile_filter_unittest.cc b/base/analytics/percentile_filter_unittest.cc
similarity index 74%
rename from modules/video_coding/percentile_filter_unittest.cc
rename to base/analytics/percentile_filter_unittest.cc
index 56cd99b..98168fd 100644
--- a/modules/video_coding/percentile_filter_unittest.cc
+++ b/base/analytics/percentile_filter_unittest.cc
@@ -9,9 +9,10 @@
*/
#include <algorithm>
+#include <climits>
+#include "webrtc/base/analytics/percentile_filter.h"
#include "webrtc/base/constructormagic.h"
-#include "webrtc/modules/video_coding/percentile_filter.h"
#include "webrtc/test/gtest.h"
namespace webrtc {
@@ -24,7 +25,7 @@
}
protected:
- PercentileFilter filter_;
+ PercentileFilter<int64_t> filter_;
private:
RTC_DISALLOW_COPY_AND_ASSIGN(PercentileFilterTest);
@@ -35,7 +36,7 @@
::testing::Values(0.0f, 0.1f, 0.5f, 0.9f, 1.0f));
TEST(PercentileFilterTest, MinFilter) {
- PercentileFilter filter(0.0f);
+ PercentileFilter<int64_t> filter(0.0f);
filter.Insert(4);
EXPECT_EQ(4, filter.GetPercentileValue());
filter.Insert(3);
@@ -43,13 +44,43 @@
}
TEST(PercentileFilterTest, MaxFilter) {
- PercentileFilter filter(1.0f);
+ PercentileFilter<int64_t> filter(1.0f);
filter.Insert(3);
EXPECT_EQ(3, filter.GetPercentileValue());
filter.Insert(4);
EXPECT_EQ(4, filter.GetPercentileValue());
}
+TEST(PercentileFilterTest, MedianFilterDouble) {
+ PercentileFilter<double> filter(0.5f);
+ filter.Insert(2.71828);
+ filter.Insert(3.14159);
+ filter.Insert(1.41421);
+ EXPECT_EQ(2.71828, filter.GetPercentileValue());
+}
+
+TEST(PercentileFilterTest, MedianFilterInt) {
+ PercentileFilter<int> filter(0.5f);
+ filter.Insert(INT_MIN);
+ filter.Insert(1);
+ filter.Insert(2);
+ EXPECT_EQ(1, filter.GetPercentileValue());
+ filter.Insert(INT_MAX);
+ filter.Erase(INT_MIN);
+ EXPECT_EQ(2, filter.GetPercentileValue());
+}
+
+TEST(PercentileFilterTest, MedianFilterUnsigned) {
+ PercentileFilter<unsigned> filter(0.5f);
+ filter.Insert(UINT_MAX);
+ filter.Insert(2u);
+ filter.Insert(1u);
+ EXPECT_EQ(2u, filter.GetPercentileValue());
+ filter.Insert(0u);
+ filter.Erase(UINT_MAX);
+ EXPECT_EQ(1u, filter.GetPercentileValue());
+}
+
TEST_P(PercentileFilterTest, EmptyFilter) {
EXPECT_EQ(0, filter_.GetPercentileValue());
filter_.Insert(3);
diff --git a/modules/BUILD.gn b/modules/BUILD.gn
index 3437e6e..1ac7d9d 100644
--- a/modules/BUILD.gn
+++ b/modules/BUILD.gn
@@ -503,7 +503,6 @@
"video_coding/jitter_buffer_unittest.cc",
"video_coding/jitter_estimator_tests.cc",
"video_coding/nack_module_unittest.cc",
- "video_coding/percentile_filter_unittest.cc",
"video_coding/protection_bitrate_calculator_unittest.cc",
"video_coding/receiver_unittest.cc",
"video_coding/rtp_frame_reference_finder_unittest.cc",
diff --git a/modules/video_coding/BUILD.gn b/modules/video_coding/BUILD.gn
index 378449f..c8f6404 100644
--- a/modules/video_coding/BUILD.gn
+++ b/modules/video_coding/BUILD.gn
@@ -55,8 +55,6 @@
"packet.h",
"packet_buffer.cc",
"packet_buffer.h",
- "percentile_filter.cc",
- "percentile_filter.h",
"protection_bitrate_calculator.cc",
"protection_bitrate_calculator.h",
"receiver.cc",
diff --git a/modules/video_coding/codec_timer.h b/modules/video_coding/codec_timer.h
index 90ef6bb..1fabeb2 100644
--- a/modules/video_coding/codec_timer.h
+++ b/modules/video_coding/codec_timer.h
@@ -13,8 +13,8 @@
#include <queue>
+#include "webrtc/base/analytics/percentile_filter.h"
#include "webrtc/modules/include/module_common_types.h"
-#include "webrtc/modules/video_coding/percentile_filter.h"
#include "webrtc/typedefs.h"
namespace webrtc {
@@ -43,7 +43,7 @@
std::queue<Sample> history_;
// |filter_| contains the same values as |history_|, but in a data structure
// that allows efficient retrieval of the percentile value.
- PercentileFilter filter_;
+ PercentileFilter<int64_t> filter_;
};
} // namespace webrtc
diff --git a/modules/video_coding/percentile_filter.cc b/modules/video_coding/percentile_filter.cc
deleted file mode 100644
index 6495567..0000000
--- a/modules/video_coding/percentile_filter.cc
+++ /dev/null
@@ -1,70 +0,0 @@
-/*
- * Copyright (c) 2016 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.
- */
-
-#include "webrtc/modules/video_coding/percentile_filter.h"
-
-#include <iterator>
-
-#include "webrtc/base/checks.h"
-
-namespace webrtc {
-
-PercentileFilter::PercentileFilter(float percentile)
- : percentile_(percentile),
- percentile_it_(set_.begin()),
- percentile_index_(0) {
- RTC_CHECK_GE(percentile, 0.0f);
- RTC_CHECK_LE(percentile, 1.0f);
-}
-
-void PercentileFilter::Insert(const int64_t& value) {
- // Insert element at the upper bound.
- set_.insert(value);
- if (set_.size() == 1u) {
- // First element inserted - initialize percentile iterator and index.
- percentile_it_ = set_.begin();
- percentile_index_ = 0;
- } else if (value < *percentile_it_) {
- // If new element is before us, increment |percentile_index_|.
- ++percentile_index_;
- }
- UpdatePercentileIterator();
-}
-
-void PercentileFilter::Erase(const int64_t& value) {
- std::multiset<int64_t>::const_iterator it = set_.lower_bound(value);
- // Ignore erase operation if the element is not present in the current set.
- if (it == set_.end() || *it != value)
- return;
- if (it == percentile_it_) {
- // If same iterator, update to the following element. Index is not affected.
- percentile_it_ = set_.erase(it);
- } else {
- set_.erase(it);
- // If erased element was before us, decrement |percentile_index_|.
- if (value <= *percentile_it_)
- --percentile_index_;
- }
- UpdatePercentileIterator();
-}
-
-void PercentileFilter::UpdatePercentileIterator() {
- if (set_.empty())
- return;
- const int64_t index = static_cast<int64_t>(percentile_ * (set_.size() - 1));
- std::advance(percentile_it_, index - percentile_index_);
- percentile_index_ = index;
-}
-
-int64_t PercentileFilter::GetPercentileValue() const {
- return set_.empty() ? 0 : *percentile_it_;
-}
-
-} // namespace webrtc
diff --git a/modules/video_coding/percentile_filter.h b/modules/video_coding/percentile_filter.h
deleted file mode 100644
index 125a244..0000000
--- a/modules/video_coding/percentile_filter.h
+++ /dev/null
@@ -1,50 +0,0 @@
-/*
- * Copyright (c) 2016 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_MODULES_VIDEO_CODING_PERCENTILE_FILTER_H_
-#define WEBRTC_MODULES_VIDEO_CODING_PERCENTILE_FILTER_H_
-
-#include <stdint.h>
-
-#include <set>
-
-namespace webrtc {
-
-// Class to efficiently get the percentile value from a group of observations.
-// The percentile is the value below which a given percentage of the
-// observations fall.
-class PercentileFilter {
- public:
- // Construct filter. |percentile| should be between 0 and 1.
- explicit PercentileFilter(float percentile);
-
- // Insert one observation. The complexity of this operation is logarithmic in
- // the size of the container.
- void Insert(const int64_t& value);
- // Remove one observation. The complexity of this operation is logarithmic in
- // the size of the container.
- void Erase(const int64_t& value);
- // Get the percentile value. The complexity of this operation is constant.
- int64_t GetPercentileValue() const;
-
- private:
- // Update iterator and index to point at target percentile value.
- void UpdatePercentileIterator();
-
- const float percentile_;
- std::multiset<int64_t> set_;
- // Maintain iterator and index of current target percentile value.
- std::multiset<int64_t>::iterator percentile_it_;
- int64_t percentile_index_;
-};
-
-} // namespace webrtc
-
-#endif // WEBRTC_MODULES_VIDEO_CODING_PERCENTILE_FILTER_H_
