1 /*
2 * Copyright 2016 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 #include "rtc_base/numerics/percentile_filter.h"
12
13 #include <stdlib.h>
14
15 #include <array>
16 #include <climits>
17 #include <cstdint>
18 #include <random>
19
20 #include "absl/algorithm/container.h"
21 #include "rtc_base/constructor_magic.h"
22 #include "test/gtest.h"
23
24 namespace webrtc {
25
26 class PercentileFilterTest : public ::testing::TestWithParam<float> {
27 public:
PercentileFilterTest()28 PercentileFilterTest() : filter_(GetParam()) {
29 // Make sure the tests are deterministic by seeding with a constant.
30 srand(42);
31 }
32
33 protected:
34 PercentileFilter<int64_t> filter_;
35
36 private:
37 RTC_DISALLOW_COPY_AND_ASSIGN(PercentileFilterTest);
38 };
39
40 INSTANTIATE_TEST_SUITE_P(PercentileFilterTests,
41 PercentileFilterTest,
42 ::testing::Values(0.0f, 0.1f, 0.5f, 0.9f, 1.0f));
43
TEST(PercentileFilterTest,MinFilter)44 TEST(PercentileFilterTest, MinFilter) {
45 PercentileFilter<int64_t> filter(0.0f);
46 filter.Insert(4);
47 EXPECT_EQ(4, filter.GetPercentileValue());
48 filter.Insert(3);
49 EXPECT_EQ(3, filter.GetPercentileValue());
50 }
51
TEST(PercentileFilterTest,MaxFilter)52 TEST(PercentileFilterTest, MaxFilter) {
53 PercentileFilter<int64_t> filter(1.0f);
54 filter.Insert(3);
55 EXPECT_EQ(3, filter.GetPercentileValue());
56 filter.Insert(4);
57 EXPECT_EQ(4, filter.GetPercentileValue());
58 }
59
TEST(PercentileFilterTest,MedianFilterDouble)60 TEST(PercentileFilterTest, MedianFilterDouble) {
61 PercentileFilter<double> filter(0.5f);
62 filter.Insert(2.71828);
63 filter.Insert(3.14159);
64 filter.Insert(1.41421);
65 EXPECT_EQ(2.71828, filter.GetPercentileValue());
66 }
67
TEST(PercentileFilterTest,MedianFilterInt)68 TEST(PercentileFilterTest, MedianFilterInt) {
69 PercentileFilter<int> filter(0.5f);
70 filter.Insert(INT_MIN);
71 filter.Insert(1);
72 filter.Insert(2);
73 EXPECT_EQ(1, filter.GetPercentileValue());
74 filter.Insert(INT_MAX);
75 filter.Erase(INT_MIN);
76 EXPECT_EQ(2, filter.GetPercentileValue());
77 }
78
TEST(PercentileFilterTest,MedianFilterUnsigned)79 TEST(PercentileFilterTest, MedianFilterUnsigned) {
80 PercentileFilter<unsigned> filter(0.5f);
81 filter.Insert(UINT_MAX);
82 filter.Insert(2u);
83 filter.Insert(1u);
84 EXPECT_EQ(2u, filter.GetPercentileValue());
85 filter.Insert(0u);
86 filter.Erase(UINT_MAX);
87 EXPECT_EQ(1u, filter.GetPercentileValue());
88 }
89
TEST_P(PercentileFilterTest,EmptyFilter)90 TEST_P(PercentileFilterTest, EmptyFilter) {
91 EXPECT_EQ(0, filter_.GetPercentileValue());
92 filter_.Insert(3);
93 bool success = filter_.Erase(3);
94 EXPECT_TRUE(success);
95 EXPECT_EQ(0, filter_.GetPercentileValue());
96 }
97
TEST_P(PercentileFilterTest,EraseNonExistingElement)98 TEST_P(PercentileFilterTest, EraseNonExistingElement) {
99 bool success = filter_.Erase(3);
100 EXPECT_FALSE(success);
101 EXPECT_EQ(0, filter_.GetPercentileValue());
102 filter_.Insert(4);
103 success = filter_.Erase(3);
104 EXPECT_FALSE(success);
105 EXPECT_EQ(4, filter_.GetPercentileValue());
106 }
107
TEST_P(PercentileFilterTest,DuplicateElements)108 TEST_P(PercentileFilterTest, DuplicateElements) {
109 filter_.Insert(3);
110 filter_.Insert(3);
111 filter_.Erase(3);
112 EXPECT_EQ(3, filter_.GetPercentileValue());
113 }
114
TEST_P(PercentileFilterTest,InsertAndEraseTenValuesInRandomOrder)115 TEST_P(PercentileFilterTest, InsertAndEraseTenValuesInRandomOrder) {
116 std::array<int64_t, 10> zero_to_nine = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
117 // The percentile value of the ten values above.
118 const int64_t expected_value = static_cast<int64_t>(GetParam() * 9);
119
120 // Insert two sets of |zero_to_nine| in random order.
121 for (int i = 0; i < 2; ++i) {
122 absl::c_shuffle(zero_to_nine, std::mt19937(std::random_device()()));
123 for (int64_t value : zero_to_nine)
124 filter_.Insert(value);
125 // After inserting a full set of |zero_to_nine|, the percentile should
126 // stay constant.
127 EXPECT_EQ(expected_value, filter_.GetPercentileValue());
128 }
129
130 // Insert and erase sets of |zero_to_nine| in random order a few times.
131 for (int i = 0; i < 3; ++i) {
132 absl::c_shuffle(zero_to_nine, std::mt19937(std::random_device()()));
133 for (int64_t value : zero_to_nine)
134 filter_.Erase(value);
135 EXPECT_EQ(expected_value, filter_.GetPercentileValue());
136 absl::c_shuffle(zero_to_nine, std::mt19937(std::random_device()()));
137 for (int64_t value : zero_to_nine)
138 filter_.Insert(value);
139 EXPECT_EQ(expected_value, filter_.GetPercentileValue());
140 }
141 }
142
143 } // namespace webrtc
144