1 // Copyright 2023 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifdef UNSAFE_BUFFERS_BUILD
6 // TODO(crbug.com/40284755): Remove this and spanify to fix the errors.
7 #pragma allow_unsafe_buffers
8 #endif
9
10 #include "base/moving_window.h"
11
12 #include "base/time/time.h"
13 #include "testing/gtest/include/gtest/gtest.h"
14
15 namespace base {
16
17 namespace {
18
19 constexpr int kTestValues[] = {
20 33, 1, 2, 7, 5, 2, 4, 45, 1000, 1, 100, 2, 200, 2, 2, 2, 300, 4, 1,
21 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1,
22 2, 1, 4, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1};
23
24 } // namespace
25
26 class MovingMaxTest : public testing::TestWithParam<unsigned int> {};
27
28 INSTANTIATE_TEST_SUITE_P(All,
29 MovingMaxTest,
30 testing::ValuesIn({1u, 2u, 3u, 4u, 5u, 6u, 7u, 8u, 9u,
31 10u, 17u, 20u, 100u}));
32
TEST_P(MovingMaxTest,BlanketTest)33 TEST_P(MovingMaxTest, BlanketTest) {
34 const size_t window_size = GetParam();
35 MovingMax<int> window(window_size);
36 for (size_t i = 0; i < std::size(kTestValues); ++i) {
37 window.AddSample(kTestValues[i]);
38 int slow_max = kTestValues[i];
39 for (size_t j = 1; j < window_size && j <= i; ++j) {
40 slow_max = std::max(slow_max, kTestValues[i - j]);
41 }
42 EXPECT_EQ(window.Max(), slow_max);
43 }
44 }
45
TEST(MovingMax,SingleElementWindow)46 TEST(MovingMax, SingleElementWindow) {
47 MovingMax<int> window(1u);
48 window.AddSample(100);
49 EXPECT_EQ(window.Max(), 100);
50 window.AddSample(1000);
51 EXPECT_EQ(window.Max(), 1000);
52 window.AddSample(1);
53 EXPECT_EQ(window.Max(), 1);
54 window.AddSample(3);
55 EXPECT_EQ(window.Max(), 3);
56 window.AddSample(4);
57 EXPECT_EQ(window.Max(), 4);
58 }
59
TEST(MovingMax,VeryLargeWindow)60 TEST(MovingMax, VeryLargeWindow) {
61 MovingMax<int> window(100u);
62 window.AddSample(100);
63 EXPECT_EQ(window.Max(), 100);
64 window.AddSample(1000);
65 EXPECT_EQ(window.Max(), 1000);
66 window.AddSample(1);
67 EXPECT_EQ(window.Max(), 1000);
68 window.AddSample(3);
69 EXPECT_EQ(window.Max(), 1000);
70 window.AddSample(4);
71 EXPECT_EQ(window.Max(), 1000);
72 }
73
TEST(MovingMax,Counts)74 TEST(MovingMax, Counts) {
75 MovingMax<int> window(3u);
76 EXPECT_EQ(window.Count(), 0u);
77 window.AddSample(100);
78 EXPECT_EQ(window.Count(), 1u);
79 window.AddSample(1000);
80 EXPECT_EQ(window.Count(), 2u);
81 window.AddSample(1);
82 EXPECT_EQ(window.Count(), 3u);
83 window.AddSample(3);
84 EXPECT_EQ(window.Count(), 4u);
85 window.AddSample(4);
86 EXPECT_EQ(window.Count(), 5u);
87 }
88
TEST(MovingAverage,Unrounded)89 TEST(MovingAverage, Unrounded) {
90 MovingAverage<int, int64_t> window(4u);
91 window.AddSample(1);
92 EXPECT_EQ(window.Mean<double>(), 1.0);
93 window.AddSample(2);
94 EXPECT_EQ(window.Mean<double>(), 1.5);
95 window.AddSample(3);
96 EXPECT_EQ(window.Mean<double>(), 2.0);
97 window.AddSample(4);
98 EXPECT_EQ(window.Mean<double>(), 2.5);
99 window.AddSample(101);
100 EXPECT_EQ(window.Mean<double>(), 27.5);
101 }
102
103 class MovingMinTest : public testing::TestWithParam<unsigned int> {};
104
105 INSTANTIATE_TEST_SUITE_P(All,
106 MovingMinTest,
107 testing::ValuesIn({1u, 2u, 3u, 4u, 5u, 6u, 7u, 8u, 9u,
108 10u, 17u, 20u, 100u}));
109
TEST_P(MovingMinTest,BlanketTest)110 TEST_P(MovingMinTest, BlanketTest) {
111 const size_t window_size = GetParam();
112 MovingMin<int> window(window_size);
113 for (int repeats = 0; repeats < 2; ++repeats) {
114 for (size_t i = 0; i < std::size(kTestValues); ++i) {
115 window.AddSample(kTestValues[i]);
116 int slow_min = kTestValues[i];
117 for (size_t j = 1; j < window_size && j <= i; ++j) {
118 slow_min = std::min(slow_min, kTestValues[i - j]);
119 }
120 EXPECT_EQ(window.Min(), slow_min);
121 }
122 window.Reset();
123 }
124 }
125
126 class MovingAverageTest : public testing::TestWithParam<unsigned int> {};
127
128 INSTANTIATE_TEST_SUITE_P(All,
129 MovingAverageTest,
130 testing::ValuesIn({1u, 2u, 3u, 4u, 5u, 6u, 7u, 8u, 9u,
131 10u, 17u, 20u, 100u}));
132
TEST_P(MovingAverageTest,BlanketTest)133 TEST_P(MovingAverageTest, BlanketTest) {
134 const size_t window_size = GetParam();
135 MovingAverage<int, int64_t> window(window_size);
136 for (int repeats = 0; repeats < 2; ++repeats) {
137 for (size_t i = 0; i < std::size(kTestValues); ++i) {
138 window.AddSample(kTestValues[i]);
139 int slow_mean = 0;
140 for (size_t j = 0; j < window_size && j <= i; ++j) {
141 slow_mean += kTestValues[i - j];
142 }
143 slow_mean /= std::min(window_size, i + 1);
144 EXPECT_EQ(window.Mean(), slow_mean);
145 }
146 window.Reset();
147 }
148 }
149
150 class MovingDeviationTest : public testing::TestWithParam<unsigned int> {};
151
152 INSTANTIATE_TEST_SUITE_P(All,
153 MovingDeviationTest,
154 testing::ValuesIn({1u, 2u, 3u, 4u, 5u, 6u, 7u, 8u, 9u,
155 10u, 17u, 20u, 100u}));
156
TEST_P(MovingDeviationTest,BlanketTest)157 TEST_P(MovingDeviationTest, BlanketTest) {
158 const size_t window_size = GetParam();
159 MovingAverageDeviation<double> window(window_size);
160 for (int repeats = 0; repeats < 2; ++repeats) {
161 for (size_t i = 0; i < std::size(kTestValues); ++i) {
162 window.AddSample(kTestValues[i]);
163 double slow_deviation = 0;
164 double mean = window.Mean();
165 for (size_t j = 0; j < window_size && j <= i; ++j) {
166 slow_deviation +=
167 (kTestValues[i - j] - mean) * (kTestValues[i - j] - mean);
168 }
169 slow_deviation /= std::min(window_size, i + 1);
170 slow_deviation = sqrt(slow_deviation);
171 double fast_deviation = window.Deviation();
172 EXPECT_TRUE(std::abs(fast_deviation - slow_deviation) < 1e-9);
173 }
174 window.Reset();
175 }
176 }
177
TEST(MovingWindowTest,Iteration)178 TEST(MovingWindowTest, Iteration) {
179 const size_t kWindowSize = 10;
180 MovingWindow<int, base::MovingWindowFeatures::Iteration> window(kWindowSize);
181 for (int repeats = 0; repeats < 2; ++repeats) {
182 for (size_t i = 0; i < std::size(kTestValues); ++i) {
183 window.AddSample(kTestValues[i]);
184 size_t j = 0;
185 const size_t in_window = std::min(i + 1, kWindowSize);
186 for (int value : window) {
187 ASSERT_LT(j, in_window);
188 EXPECT_EQ(value, kTestValues[i + j + 1 - in_window]);
189 ++j;
190 }
191 EXPECT_EQ(j, in_window);
192 }
193 window.Reset();
194 }
195 }
196
TEST(MovingMeanDeviation,WorksWithTimeDelta)197 TEST(MovingMeanDeviation, WorksWithTimeDelta) {
198 MovingAverageDeviation<base::TimeDelta> window(2);
199 window.AddSample(base::Milliseconds(400));
200 window.AddSample(base::Milliseconds(200));
201 EXPECT_EQ(window.Mean(), base::Milliseconds(300));
202 EXPECT_EQ(window.Deviation(), base::Milliseconds(100));
203 window.AddSample(base::Seconds(40));
204 window.AddSample(base::Seconds(20));
205 EXPECT_EQ(window.Mean(), base::Seconds(30));
206 EXPECT_EQ(window.Deviation(), base::Seconds(10));
207 }
208
209 } // namespace base
210