legacy-libs/grpc/deps/grpc/third_party/abseil-cpp/absl/random/distributions.h

   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 // -----------------------------------------------------------------------------
  16 // File: distributions.h
  17 // -----------------------------------------------------------------------------
  18 //
  19 // This header defines functions representing distributions, which you use in
  20 // combination with an Abseil random bit generator to produce random values
  21 // according to the rules of that distribution.
  22 //
  23 // The Abseil random library defines the following distributions within this
  24 // file:
  25 //
  26 //   * `absl::Uniform` for uniform (constant) distributions having constant
  27 //     probability
  28 //   * `absl::Bernoulli` for discrete distributions having exactly two outcomes
  29 //   * `absl::Beta` for continuous distributions parameterized through two
  30 //     free parameters
  31 //   * `absl::Exponential` for discrete distributions of events occurring
  32 //     continuously and independently at a constant average rate
  33 //   * `absl::Gaussian` (also known as "normal distributions") for continuous
  34 //     distributions using an associated quadratic function
  35 //   * `absl::LogUniform` for continuous uniform distributions where the log
  36 //     to the given base of all values is uniform
  37 //   * `absl::Poisson` for discrete probability distributions that express the
  38 //     probability of a given number of events occurring within a fixed interval
  39 //   * `absl::Zipf` for discrete probability distributions commonly used for
  40 //     modelling of rare events
  41 //
  42 // Prefer use of these distribution function classes over manual construction of
  43 // your own distribution classes, as it allows library maintainers greater
  44 // flexibility to change the underlying implementation in the future.
  45
  46 #ifndef ABSL_RANDOM_DISTRIBUTIONS_H_
  47 #define ABSL_RANDOM_DISTRIBUTIONS_H_
  48
  49 #include <algorithm>
  50 #include <cmath>
  51 #include <limits>
  52 #include <random>
  53 #include <type_traits>
  54
  55 #include "absl/base/internal/inline_variable.h"
  56 #include "absl/random/bernoulli_distribution.h"
  57 #include "absl/random/beta_distribution.h"
  58 #include "absl/random/distribution_format_traits.h"
  59 #include "absl/random/exponential_distribution.h"
  60 #include "absl/random/gaussian_distribution.h"
  61 #include "absl/random/internal/distributions.h"  // IWYU pragma: export
  62 #include "absl/random/internal/uniform_helper.h"  // IWYU pragma: export
  63 #include "absl/random/log_uniform_int_distribution.h"
  64 #include "absl/random/poisson_distribution.h"
  65 #include "absl/random/uniform_int_distribution.h"
  66 #include "absl/random/uniform_real_distribution.h"
  67 #include "absl/random/zipf_distribution.h"
  68
  69 namespace absl {
  70
  71 ABSL_INTERNAL_INLINE_CONSTEXPR(random_internal::IntervalClosedClosedT,
  72                                IntervalClosedClosed, {});
  73 ABSL_INTERNAL_INLINE_CONSTEXPR(random_internal::IntervalClosedClosedT,
  74                                IntervalClosed, {});
  75 ABSL_INTERNAL_INLINE_CONSTEXPR(random_internal::IntervalClosedOpenT,
  76                                IntervalClosedOpen, {});
  77 ABSL_INTERNAL_INLINE_CONSTEXPR(random_internal::IntervalOpenOpenT,
  78                                IntervalOpenOpen, {});
  79 ABSL_INTERNAL_INLINE_CONSTEXPR(random_internal::IntervalOpenOpenT,
  80                                IntervalOpen, {});
  81 ABSL_INTERNAL_INLINE_CONSTEXPR(random_internal::IntervalOpenClosedT,
  82                                IntervalOpenClosed, {});
  83
  84 // -----------------------------------------------------------------------------
  85 // absl::Uniform<T>(tag, bitgen, lo, hi)
  86 // -----------------------------------------------------------------------------
  87 //
  88 // `absl::Uniform()` produces random values of type `T` uniformly distributed in
  89 // a defined interval {lo, hi}. The interval `tag` defines the type of interval
  90 // which should be one of the following possible values:
  91 //
  92 //   * `absl::IntervalOpenOpen`
  93 //   * `absl::IntervalOpenClosed`
  94 //   * `absl::IntervalClosedOpen`
  95 //   * `absl::IntervalClosedClosed`
  96 //
  97 // where "open" refers to an exclusive value (excluded) from the output, while
  98 // "closed" refers to an inclusive value (included) from the output.
  99 //
 100 // In the absence of an explicit return type `T`, `absl::Uniform()` will deduce
 101 // the return type based on the provided endpoint arguments {A lo, B hi}.
 102 // Given these endpoints, one of {A, B} will be chosen as the return type, if
 103 // a type can be implicitly converted into the other in a lossless way. The
 104 // lack of any such implcit conversion between {A, B} will produce a
 105 // compile-time error
 106 //
 107 // See https://en.wikipedia.org/wiki/Uniform_distribution_(continuous)
 108 //
 109 // Example:
 110 //
 111 //   absl::BitGen bitgen;
 112 //
 113 //   // Produce a random float value between 0.0 and 1.0, inclusive
 114 //   auto x = absl::Uniform(absl::IntervalClosedClosed, bitgen, 0.0f, 1.0f);
 115 //
 116 //   // The most common interval of `absl::IntervalClosedOpen` is available by
 117 //   // default:
 118 //
 119 //   auto x = absl::Uniform(bitgen, 0.0f, 1.0f);
 120 //
 121 //   // Return-types are typically inferred from the arguments, however callers
 122 //   // can optionally provide an explicit return-type to the template.
 123 //
 124 //   auto x = absl::Uniform<float>(bitgen, 0, 1);
 125 //
 126 template <typename R = void, typename TagType, typename URBG>
 127 typename absl::enable_if_t<!std::is_same<R, void>::value, R>  //
 128 Uniform(TagType tag,
 129         URBG&& urbg,  // NOLINT(runtime/references)
 130         R lo, R hi) {
 131   using gen_t = absl::decay_t<URBG>;
 132   return random_internal::UniformImpl<R, TagType, gen_t>(tag, urbg, lo, hi);
 133 }
 134
 135 // absl::Uniform<T>(bitgen, lo, hi)
 136 //
 137 // Overload of `Uniform()` using the default closed-open interval of [lo, hi),
 138 // and returning values of type `T`
 139 template <typename R = void, typename URBG>
 140 typename absl::enable_if_t<!std::is_same<R, void>::value, R>  //
 141 Uniform(URBG&& urbg,  // NOLINT(runtime/references)
 142         R lo, R hi) {
 143   constexpr auto tag = absl::IntervalClosedOpen;
 144   using tag_t = decltype(tag);
 145   using gen_t = absl::decay_t<URBG>;
 146
 147   return random_internal::UniformImpl<R, tag_t, gen_t>(tag, urbg, lo, hi);
 148 }
 149
 150 // absl::Uniform(tag, bitgen, lo, hi)
 151 //
 152 // Overload of `Uniform()` using different (but compatible) lo, hi types. Note
 153 // that a compile-error will result if the return type cannot be deduced
 154 // correctly from the passed types.
 155 template <typename R = void, typename TagType, typename URBG, typename A,
 156           typename B>
 157 typename absl::enable_if_t<std::is_same<R, void>::value,
 158                            random_internal::uniform_inferred_return_t<A, B>>
 159 Uniform(TagType tag,
 160         URBG&& urbg,  // NOLINT(runtime/references)
 161         A lo, B hi) {
 162   using gen_t = absl::decay_t<URBG>;
 163   using return_t = typename random_internal::uniform_inferred_return_t<A, B>;
 164
 165   return random_internal::UniformImpl<return_t, TagType, gen_t>(tag, urbg, lo,
 166                                                                 hi);
 167 }
 168
 169 // absl::Uniform(bitgen, lo, hi)
 170 //
 171 // Overload of `Uniform()` using different (but compatible) lo, hi types and the
 172 // default closed-open interval of [lo, hi). Note that a compile-error will
 173 // result if the return type cannot be deduced correctly from the passed types.
 174 template <typename R = void, typename URBG, typename A, typename B>
 175 typename absl::enable_if_t<std::is_same<R, void>::value,
 176                            random_internal::uniform_inferred_return_t<A, B>>
 177 Uniform(URBG&& urbg,  // NOLINT(runtime/references)
 178         A lo, B hi) {
 179   constexpr auto tag = absl::IntervalClosedOpen;
 180   using tag_t = decltype(tag);
 181   using gen_t = absl::decay_t<URBG>;
 182   using return_t = typename random_internal::uniform_inferred_return_t<A, B>;
 183
 184   return random_internal::UniformImpl<return_t, tag_t, gen_t>(tag, urbg, lo,
 185                                                               hi);
 186 }
 187
 188 // absl::Uniform<unsigned T>(bitgen)
 189 //
 190 // Overload of Uniform() using the minimum and maximum values of a given type
 191 // `T` (which must be unsigned), returning a value of type `unsigned T`
 192 template <typename R, typename URBG>
 193 typename absl::enable_if_t<!std::is_signed<R>::value, R>  //
 194 Uniform(URBG&& urbg) {  // NOLINT(runtime/references)
 195   constexpr auto tag = absl::IntervalClosedClosed;
 196   constexpr auto lo = std::numeric_limits<R>::lowest();
 197   constexpr auto hi = (std::numeric_limits<R>::max)();
 198   using tag_t = decltype(tag);
 199   using gen_t = absl::decay_t<URBG>;
 200
 201   return random_internal::UniformImpl<R, tag_t, gen_t>(tag, urbg, lo, hi);
 202 }
 203
 204 // -----------------------------------------------------------------------------
 205 // absl::Bernoulli(bitgen, p)
 206 // -----------------------------------------------------------------------------
 207 //
 208 // `absl::Bernoulli` produces a random boolean value, with probability `p`
 209 // (where 0.0 <= p <= 1.0) equaling `true`.
 210 //
 211 // Prefer `absl::Bernoulli` to produce boolean values over other alternatives
 212 // such as comparing an `absl::Uniform()` value to a specific output.
 213 //
 214 // See https://en.wikipedia.org/wiki/Bernoulli_distribution
 215 //
 216 // Example:
 217 //
 218 //   absl::BitGen bitgen;
 219 //   ...
 220 //   if (absl::Bernoulli(bitgen, 1.0/3721.0)) {
 221 //     std::cout << "Asteroid field navigation successful.";
 222 //   }
 223 //
 224 template <typename URBG>
 225 bool Bernoulli(URBG&& urbg,  // NOLINT(runtime/references)
 226                double p) {
 227   using gen_t = absl::decay_t<URBG>;
 228   using distribution_t = absl::bernoulli_distribution;
 229   using format_t = random_internal::DistributionFormatTraits<distribution_t>;
 230
 231   return random_internal::DistributionCaller<gen_t>::template Call<
 232       distribution_t, format_t>(&urbg, p);
 233 }
 234
 235 // -----------------------------------------------------------------------------
 236 // absl::Beta<T>(bitgen, alpha, beta)
 237 // -----------------------------------------------------------------------------
 238 //
 239 // `absl::Beta` produces a floating point number distributed in the closed
 240 // interval [0,1] and parameterized by two values `alpha` and `beta` as per a
 241 // Beta distribution. `T` must be a floating point type, but may be inferred
 242 // from the types of `alpha` and `beta`.
 243 //
 244 // See https://en.wikipedia.org/wiki/Beta_distribution.
 245 //
 246 // Example:
 247 //
 248 //   absl::BitGen bitgen;
 249 //   ...
 250 //   double sample = absl::Beta(bitgen, 3.0, 2.0);
 251 //
 252 template <typename RealType, typename URBG>
 253 RealType Beta(URBG&& urbg,  // NOLINT(runtime/references)
 254               RealType alpha, RealType beta) {
 255   static_assert(
 256       std::is_floating_point<RealType>::value,
 257       "Template-argument 'RealType' must be a floating-point type, in "
 258       "absl::Beta<RealType, URBG>(...)");
 259
 260   using gen_t = absl::decay_t<URBG>;
 261   using distribution_t = typename absl::beta_distribution<RealType>;
 262   using format_t = random_internal::DistributionFormatTraits<distribution_t>;
 263
 264   return random_internal::DistributionCaller<gen_t>::template Call<
 265       distribution_t, format_t>(&urbg, alpha, beta);
 266 }
 267
 268 // -----------------------------------------------------------------------------
 269 // absl::Exponential<T>(bitgen, lambda = 1)
 270 // -----------------------------------------------------------------------------
 271 //
 272 // `absl::Exponential` produces a floating point number for discrete
 273 // distributions of events occurring continuously and independently at a
 274 // constant average rate. `T` must be a floating point type, but may be inferred
 275 // from the type of `lambda`.
 276 //
 277 // See https://en.wikipedia.org/wiki/Exponential_distribution.
 278 //
 279 // Example:
 280 //
 281 //   absl::BitGen bitgen;
 282 //   ...
 283 //   double call_length = absl::Exponential(bitgen, 7.0);
 284 //
 285 template <typename RealType, typename URBG>
 286 RealType Exponential(URBG&& urbg,  // NOLINT(runtime/references)
 287                      RealType lambda = 1) {
 288   static_assert(
 289       std::is_floating_point<RealType>::value,
 290       "Template-argument 'RealType' must be a floating-point type, in "
 291       "absl::Exponential<RealType, URBG>(...)");
 292
 293   using gen_t = absl::decay_t<URBG>;
 294   using distribution_t = typename absl::exponential_distribution<RealType>;
 295   using format_t = random_internal::DistributionFormatTraits<distribution_t>;
 296
 297   return random_internal::DistributionCaller<gen_t>::template Call<
 298       distribution_t, format_t>(&urbg, lambda);
 299 }
 300
 301 // -----------------------------------------------------------------------------
 302 // absl::Gaussian<T>(bitgen, mean = 0, stddev = 1)
 303 // -----------------------------------------------------------------------------
 304 //
 305 // `absl::Gaussian` produces a floating point number selected from the Gaussian
 306 // (ie. "Normal") distribution. `T` must be a floating point type, but may be
 307 // inferred from the types of `mean` and `stddev`.
 308 //
 309 // See https://en.wikipedia.org/wiki/Normal_distribution
 310 //
 311 // Example:
 312 //
 313 //   absl::BitGen bitgen;
 314 //   ...
 315 //   double giraffe_height = absl::Gaussian(bitgen, 16.3, 3.3);
 316 //
 317 template <typename RealType, typename URBG>
 318 RealType Gaussian(URBG&& urbg,  // NOLINT(runtime/references)
 319                   RealType mean = 0, RealType stddev = 1) {
 320   static_assert(
 321       std::is_floating_point<RealType>::value,
 322       "Template-argument 'RealType' must be a floating-point type, in "
 323       "absl::Gaussian<RealType, URBG>(...)");
 324
 325   using gen_t = absl::decay_t<URBG>;
 326   using distribution_t = typename absl::gaussian_distribution<RealType>;
 327   using format_t = random_internal::DistributionFormatTraits<distribution_t>;
 328
 329   return random_internal::DistributionCaller<gen_t>::template Call<
 330       distribution_t, format_t>(&urbg, mean, stddev);
 331 }
 332
 333 // -----------------------------------------------------------------------------
 334 // absl::LogUniform<T>(bitgen, lo, hi, base = 2)
 335 // -----------------------------------------------------------------------------
 336 //
 337 // `absl::LogUniform` produces random values distributed where the log to a
 338 // given base of all values is uniform in a closed interval [lo, hi]. `T` must
 339 // be an integral type, but may be inferred from the types of `lo` and `hi`.
 340 //
 341 // I.e., `LogUniform(0, n, b)` is uniformly distributed across buckets
 342 // [0], [1, b-1], [b, b^2-1] .. [b^(k-1), (b^k)-1] .. [b^floor(log(n, b)), n]
 343 // and is uniformly distributed within each bucket.
 344 //
 345 // The resulting probability density is inversely related to bucket size, though
 346 // values in the final bucket may be more likely than previous values. (In the
 347 // extreme case where n = b^i the final value will be tied with zero as the most
 348 // probable result.
 349 //
 350 // If `lo` is nonzero then this distribution is shifted to the desired interval,
 351 // so LogUniform(lo, hi, b) is equivalent to LogUniform(0, hi-lo, b)+lo.
 352 //
 353 // See http://ecolego.facilia.se/ecolego/show/Log-Uniform%20Distribution
 354 //
 355 // Example:
 356 //
 357 //   absl::BitGen bitgen;
 358 //   ...
 359 //   int v = absl::LogUniform(bitgen, 0, 1000);
 360 //
 361 template <typename IntType, typename URBG>
 362 IntType LogUniform(URBG&& urbg,  // NOLINT(runtime/references)
 363                    IntType lo, IntType hi, IntType base = 2) {
 364   static_assert(std::is_integral<IntType>::value,
 365                 "Template-argument 'IntType' must be an integral type, in "
 366                 "absl::LogUniform<IntType, URBG>(...)");
 367
 368   using gen_t = absl::decay_t<URBG>;
 369   using distribution_t = typename absl::log_uniform_int_distribution<IntType>;
 370   using format_t = random_internal::DistributionFormatTraits<distribution_t>;
 371
 372   return random_internal::DistributionCaller<gen_t>::template Call<
 373       distribution_t, format_t>(&urbg, lo, hi, base);
 374 }
 375
 376 // -----------------------------------------------------------------------------
 377 // absl::Poisson<T>(bitgen, mean = 1)
 378 // -----------------------------------------------------------------------------
 379 //
 380 // `absl::Poisson` produces discrete probabilities for a given number of events
 381 // occurring within a fixed interval within the closed interval [0, max]. `T`
 382 // must be an integral type.
 383 //
 384 // See https://en.wikipedia.org/wiki/Poisson_distribution
 385 //
 386 // Example:
 387 //
 388 //   absl::BitGen bitgen;
 389 //   ...
 390 //   int requests_per_minute = absl::Poisson<int>(bitgen, 3.2);
 391 //
 392 template <typename IntType, typename URBG>
 393 IntType Poisson(URBG&& urbg,  // NOLINT(runtime/references)
 394                 double mean = 1.0) {
 395   static_assert(std::is_integral<IntType>::value,
 396                 "Template-argument 'IntType' must be an integral type, in "
 397                 "absl::Poisson<IntType, URBG>(...)");
 398
 399   using gen_t = absl::decay_t<URBG>;
 400   using distribution_t = typename absl::poisson_distribution<IntType>;
 401   using format_t = random_internal::DistributionFormatTraits<distribution_t>;
 402
 403   return random_internal::DistributionCaller<gen_t>::template Call<
 404       distribution_t, format_t>(&urbg, mean);
 405 }
 406
 407 // -----------------------------------------------------------------------------
 408 // absl::Zipf<T>(bitgen, hi = max, q = 2, v = 1)
 409 // -----------------------------------------------------------------------------
 410 //
 411 // `absl::Zipf` produces discrete probabilities commonly used for modelling of
 412 // rare events over the closed interval [0, hi]. The parameters `v` and `q`
 413 // determine the skew of the distribution. `T`  must be an integral type, but
 414 // may be inferred from the type of `hi`.
 415 //
 416 // See http://mathworld.wolfram.com/ZipfDistribution.html
 417 //
 418 // Example:
 419 //
 420 //   absl::BitGen bitgen;
 421 //   ...
 422 //   int term_rank = absl::Zipf<int>(bitgen);
 423 //
 424 template <typename IntType, typename URBG>
 425 IntType Zipf(URBG&& urbg,  // NOLINT(runtime/references)
 426              IntType hi = (std::numeric_limits<IntType>::max)(), double q = 2.0,
 427              double v = 1.0) {
 428   static_assert(std::is_integral<IntType>::value,
 429                 "Template-argument 'IntType' must be an integral type, in "
 430                 "absl::Zipf<IntType, URBG>(...)");
 431
 432   using gen_t = absl::decay_t<URBG>;
 433   using distribution_t = typename absl::zipf_distribution<IntType>;
 434   using format_t = random_internal::DistributionFormatTraits<distribution_t>;
 435
 436   return random_internal::DistributionCaller<gen_t>::template Call<
 437       distribution_t, format_t>(&urbg, hi, q, v);
 438 }
 439
 440 }  // namespace absl.
 441
 442 #endif  // ABSL_RANDOM_DISTRIBUTIONS_H_