Electroneum
rolling_median.cpp
Go to the documentation of this file.
1 // Copyright (c) 2019, The Monero Project
2 //
3 // All rights reserved.
4 //
5 // Redistribution and use in source and binary forms, with or without modification, are
6 // permitted provided that the following conditions are met:
7 //
8 // 1. Redistributions of source code must retain the above copyright notice, this list of
9 // conditions and the following disclaimer.
10 //
11 // 2. Redistributions in binary form must reproduce the above copyright notice, this list
12 // of conditions and the following disclaimer in the documentation and/or other
13 // materials provided with the distribution.
14 //
15 // 3. Neither the name of the copyright holder nor the names of its contributors may be
16 // used to endorse or promote products derived from this software without specific
17 // prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
20 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
21 // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
22 // THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
26 // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
27 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 
29 #include <random>
30 #include "gtest/gtest.h"
31 #include "misc_language.h"
32 #include "rolling_median.h"
33 #include "crypto/crypto.h"
34 
35 TEST(rolling_median, one)
36 {
38  m.insert(42);
39  ASSERT_EQ(m.median(), 42);
40  m.insert(18);
41  ASSERT_EQ(m.median(), 18);
42  m.insert(7483);
43  ASSERT_EQ(m.median(), 7483);
44 }
45 
46 TEST(rolling_median, two)
47 {
49  m.insert(42);
50  ASSERT_EQ(m.median(), 42);
51  m.insert(45);
52  ASSERT_EQ(m.median(), 43);
53  m.insert(49);
54  ASSERT_EQ(m.median(), 47);
55  m.insert(41);
56  ASSERT_EQ(m.median(), 45);
57  m.insert(43);
58  ASSERT_EQ(m.median(), 42);
59  m.insert(40);
60  ASSERT_EQ(m.median(), 41);
61  m.insert(41);
62  ASSERT_EQ(m.median(), 40);
63 }
64 
65 TEST(rolling_median, series)
66 {
68  std::vector<uint64_t> v;
69  v.reserve(100);
70  for (int i = 0; i < 10000; ++i)
71  {
72  uint64_t r = rand();
73  v.push_back(r);
74  if (v.size() > 100)
75  v.erase(v.begin());
76  m.insert(r);
77  std::vector<uint64_t> vcopy = v;
79  }
80 }
81 
82 TEST(rolling_median, clear_whole)
83 {
85  std::vector<uint64_t> random, median;
86  random.reserve(10000);
87  median.reserve(10000);
88  for (int i = 0; i < 10000; ++i)
89  {
90  random.push_back(rand());
91  m.insert(random.back());
92  median.push_back(m.median());
93  }
94  m.clear();
95  for (int i = 0; i < 10000; ++i)
96  {
97  m.insert(random[i]);
98  ASSERT_EQ(median[i], m.median());
99  }
100 }
101 
102 TEST(rolling_median, clear_partway)
103 {
105  std::vector<uint64_t> random, median;
106  random.reserve(10000);
107  median.reserve(10000);
108  for (int i = 0; i < 10000; ++i)
109  {
110  random.push_back(rand());
111  m.insert(random.back());
112  median.push_back(m.median());
113  }
114  m.clear();
115  for (int i = 10000 - 100; i < 10000; ++i)
116  {
117  m.insert(random[i]);
118  }
119  ASSERT_EQ(median[10000-1], m.median());
120 }
121 
122 TEST(rolling_median, order)
123 {
125  std::vector<uint64_t> random;
126  random.reserve(1000);
127  for (int i = 0; i < 1000; ++i)
128  {
129  random.push_back(rand());
130  m.insert(random.back());
131  }
132  const uint64_t med = m.median();
133 
134  std::sort(random.begin(), random.end(), [](uint64_t a, uint64_t b) { return a < b; });
135  m.clear();
136  for (int i = 0; i < 1000; ++i)
137  m.insert(random[i]);
138  ASSERT_EQ(med, m.median());
139 
140  std::sort(random.begin(), random.end(), [](uint64_t a, uint64_t b) { return a > b; });
141  m.clear();
142  for (int i = 0; i < 1000; ++i)
143  m.insert(random[i]);
144  ASSERT_EQ(med, m.median());
145 
146  std::shuffle(random.begin(), random.end(), std::default_random_engine(crypto::rand<unsigned>()));
147  m.clear();
148  for (int i = 0; i < 1000; ++i)
149  m.insert(random[i]);
150  ASSERT_EQ(med, m.median());
151 }
152 
153 TEST(rolling_median, history_blind)
154 {
156 
157  uint64_t median = 0;
158  for (int i = 0; i < 1000; ++i)
159  {
160  m.clear();
161  int history_length = 743723 % (i+1);
162  while (history_length--)
163  m.insert(743284 % (i+1));
164  for (int j = 0; j < 10; ++j)
165  m.insert(8924829384 % (j+1));
166  if (i == 0)
167  median = m.median();
168  else
169  ASSERT_EQ(median, m.median());
170  }
171 }
172 
173 TEST(rolling_median, size)
174 {
176 
177  ASSERT_EQ(m.size(), 0);
178  m.insert(1);
179  ASSERT_EQ(m.size(), 1);
180  m.insert(2);
181  ASSERT_EQ(m.size(), 2);
182  m.clear();
183  ASSERT_EQ(m.size(), 0);
184  for (int i = 0; i < 10; ++i)
185  {
186  m.insert(80 % (i + 1));
187  ASSERT_EQ(m.size(), i + 1);
188  }
189  m.insert(1);
190  ASSERT_EQ(m.size(), 10);
191  m.insert(2);
192  ASSERT_EQ(m.size(), 10);
193  m.clear();
194  ASSERT_EQ(m.size(), 0);
195  m.insert(4);
196  ASSERT_EQ(m.size(), 1);
197  for (int i = 0; i < 1000; ++i)
198  {
199  m.insert(80 % (i + 1));
200  ASSERT_EQ(m.size(), std::min<int>(10, i + 2));
201  }
202 }
#define ASSERT_EQ(val1, val2)
Definition: gtest.h:1956
void rand(size_t N, uint8_t *bytes)
Definition: crypto.h:209
unsigned __int64 uint64_t
Definition: stdint.h:136
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
type_vec_type median(std::vector< type_vec_type > &v)
TEST(rolling_median, one)
uint64_t random(const uint64_t max_value)