base/moving_window_unittest.cc

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