1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/random/internal/uniform_helper.h"
16
17 #include <cmath>
18 #include <cstdint>
19 #include <random>
20
21 #include "gtest/gtest.h"
22
23 namespace {
24
25 using absl::IntervalClosedClosedTag;
26 using absl::IntervalClosedOpenTag;
27 using absl::IntervalOpenClosedTag;
28 using absl::IntervalOpenOpenTag;
29 using absl::random_internal::uniform_inferred_return_t;
30 using absl::random_internal::uniform_lower_bound;
31 using absl::random_internal::uniform_upper_bound;
32
33 class UniformHelperTest : public testing::Test {};
34
TEST_F(UniformHelperTest,UniformBoundFunctionsGeneral)35 TEST_F(UniformHelperTest, UniformBoundFunctionsGeneral) {
36 constexpr IntervalClosedClosedTag IntervalClosedClosed;
37 constexpr IntervalClosedOpenTag IntervalClosedOpen;
38 constexpr IntervalOpenClosedTag IntervalOpenClosed;
39 constexpr IntervalOpenOpenTag IntervalOpenOpen;
40
41 // absl::uniform_int_distribution natively assumes IntervalClosedClosed
42 // absl::uniform_real_distribution natively assumes IntervalClosedOpen
43
44 EXPECT_EQ(uniform_lower_bound(IntervalOpenClosed, 0, 100), 1);
45 EXPECT_EQ(uniform_lower_bound(IntervalOpenOpen, 0, 100), 1);
46 EXPECT_GT(uniform_lower_bound<float>(IntervalOpenClosed, 0, 1.0), 0);
47 EXPECT_GT(uniform_lower_bound<float>(IntervalOpenOpen, 0, 1.0), 0);
48 EXPECT_GT(uniform_lower_bound<double>(IntervalOpenClosed, 0, 1.0), 0);
49 EXPECT_GT(uniform_lower_bound<double>(IntervalOpenOpen, 0, 1.0), 0);
50
51 EXPECT_EQ(uniform_lower_bound(IntervalClosedClosed, 0, 100), 0);
52 EXPECT_EQ(uniform_lower_bound(IntervalClosedOpen, 0, 100), 0);
53 EXPECT_EQ(uniform_lower_bound<float>(IntervalClosedClosed, 0, 1.0), 0);
54 EXPECT_EQ(uniform_lower_bound<float>(IntervalClosedOpen, 0, 1.0), 0);
55 EXPECT_EQ(uniform_lower_bound<double>(IntervalClosedClosed, 0, 1.0), 0);
56 EXPECT_EQ(uniform_lower_bound<double>(IntervalClosedOpen, 0, 1.0), 0);
57
58 EXPECT_EQ(uniform_upper_bound(IntervalOpenOpen, 0, 100), 99);
59 EXPECT_EQ(uniform_upper_bound(IntervalClosedOpen, 0, 100), 99);
60 EXPECT_EQ(uniform_upper_bound<float>(IntervalOpenOpen, 0, 1.0), 1.0);
61 EXPECT_EQ(uniform_upper_bound<float>(IntervalClosedOpen, 0, 1.0), 1.0);
62 EXPECT_EQ(uniform_upper_bound<double>(IntervalOpenOpen, 0, 1.0), 1.0);
63 EXPECT_EQ(uniform_upper_bound<double>(IntervalClosedOpen, 0, 1.0), 1.0);
64
65 EXPECT_EQ(uniform_upper_bound(IntervalOpenClosed, 0, 100), 100);
66 EXPECT_EQ(uniform_upper_bound(IntervalClosedClosed, 0, 100), 100);
67 EXPECT_GT(uniform_upper_bound<float>(IntervalOpenClosed, 0, 1.0), 1.0);
68 EXPECT_GT(uniform_upper_bound<float>(IntervalClosedClosed, 0, 1.0), 1.0);
69 EXPECT_GT(uniform_upper_bound<double>(IntervalOpenClosed, 0, 1.0), 1.0);
70 EXPECT_GT(uniform_upper_bound<double>(IntervalClosedClosed, 0, 1.0), 1.0);
71
72 // Negative value tests
73 EXPECT_EQ(uniform_lower_bound(IntervalOpenClosed, -100, -1), -99);
74 EXPECT_EQ(uniform_lower_bound(IntervalOpenOpen, -100, -1), -99);
75 EXPECT_GT(uniform_lower_bound<float>(IntervalOpenClosed, -2.0, -1.0), -2.0);
76 EXPECT_GT(uniform_lower_bound<float>(IntervalOpenOpen, -2.0, -1.0), -2.0);
77 EXPECT_GT(uniform_lower_bound<double>(IntervalOpenClosed, -2.0, -1.0), -2.0);
78 EXPECT_GT(uniform_lower_bound<double>(IntervalOpenOpen, -2.0, -1.0), -2.0);
79
80 EXPECT_EQ(uniform_lower_bound(IntervalClosedClosed, -100, -1), -100);
81 EXPECT_EQ(uniform_lower_bound(IntervalClosedOpen, -100, -1), -100);
82 EXPECT_EQ(uniform_lower_bound<float>(IntervalClosedClosed, -2.0, -1.0), -2.0);
83 EXPECT_EQ(uniform_lower_bound<float>(IntervalClosedOpen, -2.0, -1.0), -2.0);
84 EXPECT_EQ(uniform_lower_bound<double>(IntervalClosedClosed, -2.0, -1.0),
85 -2.0);
86 EXPECT_EQ(uniform_lower_bound<double>(IntervalClosedOpen, -2.0, -1.0), -2.0);
87
88 EXPECT_EQ(uniform_upper_bound(IntervalOpenOpen, -100, -1), -2);
89 EXPECT_EQ(uniform_upper_bound(IntervalClosedOpen, -100, -1), -2);
90 EXPECT_EQ(uniform_upper_bound<float>(IntervalOpenOpen, -2.0, -1.0), -1.0);
91 EXPECT_EQ(uniform_upper_bound<float>(IntervalClosedOpen, -2.0, -1.0), -1.0);
92 EXPECT_EQ(uniform_upper_bound<double>(IntervalOpenOpen, -2.0, -1.0), -1.0);
93 EXPECT_EQ(uniform_upper_bound<double>(IntervalClosedOpen, -2.0, -1.0), -1.0);
94
95 EXPECT_EQ(uniform_upper_bound(IntervalOpenClosed, -100, -1), -1);
96 EXPECT_EQ(uniform_upper_bound(IntervalClosedClosed, -100, -1), -1);
97 EXPECT_GT(uniform_upper_bound<float>(IntervalOpenClosed, -2.0, -1.0), -1.0);
98 EXPECT_GT(uniform_upper_bound<float>(IntervalClosedClosed, -2.0, -1.0), -1.0);
99 EXPECT_GT(uniform_upper_bound<double>(IntervalOpenClosed, -2.0, -1.0), -1.0);
100 EXPECT_GT(uniform_upper_bound<double>(IntervalClosedClosed, -2.0, -1.0),
101 -1.0);
102
103 EXPECT_GT(uniform_lower_bound(IntervalOpenClosed, 1.0, 2.0), 1.0);
104 EXPECT_LT(uniform_lower_bound(IntervalOpenClosed, 1.0, +0.0), 1.0);
105 EXPECT_LT(uniform_lower_bound(IntervalOpenClosed, 1.0, -0.0), 1.0);
106 EXPECT_LT(uniform_lower_bound(IntervalOpenClosed, 1.0, -1.0), 1.0);
107 }
108
TEST_F(UniformHelperTest,UniformBoundFunctionsIntBounds)109 TEST_F(UniformHelperTest, UniformBoundFunctionsIntBounds) {
110 // Verifies the saturating nature of uniform_lower_bound and
111 // uniform_upper_bound
112 constexpr IntervalOpenOpenTag IntervalOpenOpen;
113
114 // uint max.
115 constexpr auto m = (std::numeric_limits<uint64_t>::max)();
116
117 EXPECT_EQ(1, uniform_lower_bound(IntervalOpenOpen, 0u, 0u));
118 EXPECT_EQ(m, uniform_lower_bound(IntervalOpenOpen, m, m));
119 EXPECT_EQ(m, uniform_lower_bound(IntervalOpenOpen, m - 1, m - 1));
120 EXPECT_EQ(0, uniform_upper_bound(IntervalOpenOpen, 0u, 0u));
121 EXPECT_EQ(m - 1, uniform_upper_bound(IntervalOpenOpen, m, m));
122
123 // int min/max
124 constexpr auto l = (std::numeric_limits<int64_t>::min)();
125 constexpr auto r = (std::numeric_limits<int64_t>::max)();
126 EXPECT_EQ(1, uniform_lower_bound(IntervalOpenOpen, 0, 0));
127 EXPECT_EQ(l + 1, uniform_lower_bound(IntervalOpenOpen, l, l));
128 EXPECT_EQ(r, uniform_lower_bound(IntervalOpenOpen, r - 1, r - 1));
129 EXPECT_EQ(r, uniform_lower_bound(IntervalOpenOpen, r, r));
130 EXPECT_EQ(-1, uniform_upper_bound(IntervalOpenOpen, 0, 0));
131 EXPECT_EQ(l, uniform_upper_bound(IntervalOpenOpen, l, l));
132 EXPECT_EQ(r - 1, uniform_upper_bound(IntervalOpenOpen, r, r));
133 }
134
TEST_F(UniformHelperTest,UniformBoundFunctionsRealBounds)135 TEST_F(UniformHelperTest, UniformBoundFunctionsRealBounds) {
136 // absl::uniform_real_distribution natively assumes IntervalClosedOpen;
137 // use the inverse here so each bound has to change.
138 constexpr IntervalOpenClosedTag IntervalOpenClosed;
139
140 // Edge cases: the next value toward itself is itself.
141 EXPECT_EQ(1.0, uniform_lower_bound(IntervalOpenClosed, 1.0, 1.0));
142 EXPECT_EQ(1.0f, uniform_lower_bound(IntervalOpenClosed, 1.0f, 1.0f));
143
144 // rightmost and leftmost finite values.
145 constexpr auto r = (std::numeric_limits<double>::max)();
146 const auto re = std::nexttoward(r, 0.0);
147 constexpr auto l = -r;
148 const auto le = std::nexttoward(l, 0.0);
149
150 EXPECT_EQ(l, uniform_lower_bound(IntervalOpenClosed, l, l)); // (l,l)
151 EXPECT_EQ(r, uniform_lower_bound(IntervalOpenClosed, r, r)); // (r,r)
152 EXPECT_EQ(le, uniform_lower_bound(IntervalOpenClosed, l, r)); // (l,r)
153 EXPECT_EQ(le, uniform_lower_bound(IntervalOpenClosed, l, 0.0)); // (l, 0)
154 EXPECT_EQ(le, uniform_lower_bound(IntervalOpenClosed, l, le)); // (l, le)
155 EXPECT_EQ(r, uniform_lower_bound(IntervalOpenClosed, re, r)); // (re, r)
156
157 EXPECT_EQ(le, uniform_upper_bound(IntervalOpenClosed, l, l)); // (l,l)
158 EXPECT_EQ(r, uniform_upper_bound(IntervalOpenClosed, r, r)); // (r,r)
159 EXPECT_EQ(r, uniform_upper_bound(IntervalOpenClosed, l, r)); // (l,r)
160 EXPECT_EQ(r, uniform_upper_bound(IntervalOpenClosed, l, re)); // (l,re)
161 EXPECT_EQ(r, uniform_upper_bound(IntervalOpenClosed, 0.0, r)); // (0, r)
162 EXPECT_EQ(r, uniform_upper_bound(IntervalOpenClosed, re, r)); // (re, r)
163 EXPECT_EQ(r, uniform_upper_bound(IntervalOpenClosed, le, re)); // (le, re)
164
165 const double e = std::nextafter(1.0, 2.0); // 1 + epsilon
166 const double f = std::nextafter(1.0, 0.0); // 1 - epsilon
167
168 // (1.0, 1.0 + epsilon)
169 EXPECT_EQ(e, uniform_lower_bound(IntervalOpenClosed, 1.0, e));
170 EXPECT_EQ(std::nextafter(e, 2.0),
171 uniform_upper_bound(IntervalOpenClosed, 1.0, e));
172
173 // (1.0-epsilon, 1.0)
174 EXPECT_EQ(1.0, uniform_lower_bound(IntervalOpenClosed, f, 1.0));
175 EXPECT_EQ(e, uniform_upper_bound(IntervalOpenClosed, f, 1.0));
176
177 // denorm cases.
178 const double g = std::numeric_limits<double>::denorm_min();
179 const double h = std::nextafter(g, 1.0);
180
181 // (0, denorm_min)
182 EXPECT_EQ(g, uniform_lower_bound(IntervalOpenClosed, 0.0, g));
183 EXPECT_EQ(h, uniform_upper_bound(IntervalOpenClosed, 0.0, g));
184
185 // (denorm_min, 1.0)
186 EXPECT_EQ(h, uniform_lower_bound(IntervalOpenClosed, g, 1.0));
187 EXPECT_EQ(e, uniform_upper_bound(IntervalOpenClosed, g, 1.0));
188
189 // Edge cases: invalid bounds.
190 EXPECT_EQ(f, uniform_lower_bound(IntervalOpenClosed, 1.0, -1.0));
191 }
192
193 struct Invalid {};
194
195 template <typename A, typename B>
196 auto InferredUniformReturnT(int) -> uniform_inferred_return_t<A, B>;
197
198 template <typename, typename>
199 Invalid InferredUniformReturnT(...);
200
201 // Given types <A, B, Expect>, CheckArgsInferType() verifies that
202 //
203 // uniform_inferred_return_t<A, B> and
204 // uniform_inferred_return_t<B, A>
205 //
206 // returns the type "Expect".
207 //
208 // This interface can also be used to assert that a given inferred return types
209 // are invalid. Writing:
210 //
211 // CheckArgsInferType<float, int, Invalid>()
212 //
213 // will assert that this overload does not exist.
214 template <typename A, typename B, typename Expect>
CheckArgsInferType()215 void CheckArgsInferType() {
216 static_assert(
217 absl::conjunction<
218 std::is_same<Expect, decltype(InferredUniformReturnT<A, B>(0))>,
219 std::is_same<Expect,
220 decltype(InferredUniformReturnT<B, A>(0))>>::value,
221 "");
222 }
223
TEST_F(UniformHelperTest,UniformTypeInference)224 TEST_F(UniformHelperTest, UniformTypeInference) {
225 // Infers common types.
226 CheckArgsInferType<uint16_t, uint16_t, uint16_t>();
227 CheckArgsInferType<uint32_t, uint32_t, uint32_t>();
228 CheckArgsInferType<uint64_t, uint64_t, uint64_t>();
229 CheckArgsInferType<int16_t, int16_t, int16_t>();
230 CheckArgsInferType<int32_t, int32_t, int32_t>();
231 CheckArgsInferType<int64_t, int64_t, int64_t>();
232 CheckArgsInferType<float, float, float>();
233 CheckArgsInferType<double, double, double>();
234
235 // Properly promotes uint16_t.
236 CheckArgsInferType<uint16_t, uint32_t, uint32_t>();
237 CheckArgsInferType<uint16_t, uint64_t, uint64_t>();
238 CheckArgsInferType<uint16_t, int32_t, int32_t>();
239 CheckArgsInferType<uint16_t, int64_t, int64_t>();
240 CheckArgsInferType<uint16_t, float, float>();
241 CheckArgsInferType<uint16_t, double, double>();
242
243 // Properly promotes int16_t.
244 CheckArgsInferType<int16_t, int32_t, int32_t>();
245 CheckArgsInferType<int16_t, int64_t, int64_t>();
246 CheckArgsInferType<int16_t, float, float>();
247 CheckArgsInferType<int16_t, double, double>();
248
249 // Invalid (u)int16_t-pairings do not compile.
250 // See "CheckArgsInferType" comments above, for how this is achieved.
251 CheckArgsInferType<uint16_t, int16_t, Invalid>();
252 CheckArgsInferType<int16_t, uint32_t, Invalid>();
253 CheckArgsInferType<int16_t, uint64_t, Invalid>();
254
255 // Properly promotes uint32_t.
256 CheckArgsInferType<uint32_t, uint64_t, uint64_t>();
257 CheckArgsInferType<uint32_t, int64_t, int64_t>();
258 CheckArgsInferType<uint32_t, double, double>();
259
260 // Properly promotes int32_t.
261 CheckArgsInferType<int32_t, int64_t, int64_t>();
262 CheckArgsInferType<int32_t, double, double>();
263
264 // Invalid (u)int32_t-pairings do not compile.
265 CheckArgsInferType<uint32_t, int32_t, Invalid>();
266 CheckArgsInferType<int32_t, uint64_t, Invalid>();
267 CheckArgsInferType<int32_t, float, Invalid>();
268 CheckArgsInferType<uint32_t, float, Invalid>();
269
270 // Invalid (u)int64_t-pairings do not compile.
271 CheckArgsInferType<uint64_t, int64_t, Invalid>();
272 CheckArgsInferType<int64_t, float, Invalid>();
273 CheckArgsInferType<int64_t, double, Invalid>();
274
275 // Properly promotes float.
276 CheckArgsInferType<float, double, double>();
277 }
278
279 } // namespace
280