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/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_
diff --git a/webrtc/modules/video_coding/percentile_filter_unittest.cc b/webrtc/modules/video_coding/percentile_filter_unittest.cc
deleted file mode 100644
index 56cd99b..0000000
--- a/webrtc/modules/video_coding/percentile_filter_unittest.cc
+++ /dev/null
@@ -1,104 +0,0 @@
-/*
- * Copyright 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 <algorithm>
-
-#include "webrtc/base/constructormagic.h"
-#include "webrtc/modules/video_coding/percentile_filter.h"
-#include "webrtc/test/gtest.h"
-
-namespace webrtc {
-
-class PercentileFilterTest : public ::testing::TestWithParam<float> {
- public:
- PercentileFilterTest() : filter_(GetParam()) {
- // Make sure the tests are deterministic by seeding with a constant.
- srand(42);
- }
-
- protected:
- PercentileFilter filter_;
-
- private:
- RTC_DISALLOW_COPY_AND_ASSIGN(PercentileFilterTest);
-};
-
-INSTANTIATE_TEST_CASE_P(PercentileFilterTests,
- PercentileFilterTest,
- ::testing::Values(0.0f, 0.1f, 0.5f, 0.9f, 1.0f));
-
-TEST(PercentileFilterTest, MinFilter) {
- PercentileFilter filter(0.0f);
- filter.Insert(4);
- EXPECT_EQ(4, filter.GetPercentileValue());
- filter.Insert(3);
- EXPECT_EQ(3, filter.GetPercentileValue());
-}
-
-TEST(PercentileFilterTest, MaxFilter) {
- PercentileFilter filter(1.0f);
- filter.Insert(3);
- EXPECT_EQ(3, filter.GetPercentileValue());
- filter.Insert(4);
- EXPECT_EQ(4, filter.GetPercentileValue());
-}
-
-TEST_P(PercentileFilterTest, EmptyFilter) {
- EXPECT_EQ(0, filter_.GetPercentileValue());
- filter_.Insert(3);
- filter_.Erase(3);
- EXPECT_EQ(0, filter_.GetPercentileValue());
-}
-
-TEST_P(PercentileFilterTest, EraseNonExistingElement) {
- filter_.Erase(3);
- EXPECT_EQ(0, filter_.GetPercentileValue());
- filter_.Insert(4);
- filter_.Erase(3);
- EXPECT_EQ(4, filter_.GetPercentileValue());
-}
-
-TEST_P(PercentileFilterTest, DuplicateElements) {
- filter_.Insert(3);
- filter_.Insert(3);
- filter_.Erase(3);
- EXPECT_EQ(3, filter_.GetPercentileValue());
-}
-
-TEST_P(PercentileFilterTest, InsertAndEraseTenValuesInRandomOrder) {
- int64_t zero_to_nine[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
- // The percentile value of the ten values above.
- const int64_t expected_value = static_cast<int64_t>(GetParam() * 9);
-
- // Insert two sets of |zero_to_nine| in random order.
- for (int i = 0; i < 2; ++i) {
- std::random_shuffle(zero_to_nine, zero_to_nine + 10);
- for (int64_t value : zero_to_nine)
- filter_.Insert(value);
- // After inserting a full set of |zero_to_nine|, the percentile should
- // stay constant.
- EXPECT_EQ(expected_value, filter_.GetPercentileValue());
- }
-
- // Insert and erase sets of |zero_to_nine| in random order a few times.
- for (int i = 0; i < 3; ++i) {
- std::random_shuffle(zero_to_nine, zero_to_nine + 10);
- for (int64_t value : zero_to_nine)
- filter_.Erase(value);
- EXPECT_EQ(expected_value, filter_.GetPercentileValue());
-
- std::random_shuffle(zero_to_nine, zero_to_nine + 10);
- for (int64_t value : zero_to_nine)
- filter_.Insert(value);
- EXPECT_EQ(expected_value, filter_.GetPercentileValue());
- }
-}
-
-} // namespace webrtc