Templatize percentile_filter.h and move it to base/analytics. BUG=None Review-Url: https://codereview.webrtc.org/2529063002 Cr-Commit-Position: refs/heads/master@{#15334}
diff --git a/webrtc/BUILD.gn b/webrtc/BUILD.gn index 0bae0aa..e5a6d4c 100644 --- a/webrtc/BUILD.gn +++ b/webrtc/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/webrtc/base/BUILD.gn b/webrtc/base/BUILD.gn index 5d19957..69ba772 100644 --- a/webrtc/base/BUILD.gn +++ b/webrtc/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/webrtc/base/analytics/percentile_filter.h b/webrtc/base/analytics/percentile_filter.h new file mode 100644 index 0000000..b3c8f8d --- /dev/null +++ b/webrtc/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/webrtc/modules/video_coding/percentile_filter_unittest.cc b/webrtc/base/analytics/percentile_filter_unittest.cc similarity index 74% rename from webrtc/modules/video_coding/percentile_filter_unittest.cc rename to webrtc/base/analytics/percentile_filter_unittest.cc index 56cd99b..98168fd 100644 --- a/webrtc/modules/video_coding/percentile_filter_unittest.cc +++ b/webrtc/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/webrtc/modules/BUILD.gn b/webrtc/modules/BUILD.gn index 3437e6e..1ac7d9d 100644 --- a/webrtc/modules/BUILD.gn +++ b/webrtc/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/webrtc/modules/video_coding/BUILD.gn b/webrtc/modules/video_coding/BUILD.gn index 378449f..c8f6404 100644 --- a/webrtc/modules/video_coding/BUILD.gn +++ b/webrtc/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/webrtc/modules/video_coding/codec_timer.h b/webrtc/modules/video_coding/codec_timer.h index 90ef6bb..1fabeb2 100644 --- a/webrtc/modules/video_coding/codec_timer.h +++ b/webrtc/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/webrtc/modules/video_coding/percentile_filter.cc b/webrtc/modules/video_coding/percentile_filter.cc deleted file mode 100644 index 6495567..0000000 --- a/webrtc/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/webrtc/modules/video_coding/percentile_filter.h b/webrtc/modules/video_coding/percentile_filter.h deleted file mode 100644 index 125a244..0000000 --- a/webrtc/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_