280 lines
8.9 KiB
C++
280 lines
8.9 KiB
C++
/*
|
|
* This Source Code Form is subject to the terms of the Mozilla Public
|
|
* License, v. 2.0. If a copy of the MPL was not distributed with this
|
|
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
|
|
*
|
|
* Copyright 2016-2019 Danny Robson <danny@nerdcruft.net>
|
|
*/
|
|
|
|
#pragma once
|
|
|
|
#include "coord/traits.hpp"
|
|
#include "rand/generic.hpp"
|
|
#include "rand/distribution/uniform.hpp"
|
|
|
|
#include <algorithm>
|
|
#include <array>
|
|
#include <random>
|
|
#include <limits>
|
|
#include <type_traits>
|
|
|
|
#include <chrono>
|
|
|
|
|
|
namespace cruft::random {
|
|
template <typename T>
|
|
concept UniformRandomBitGenerator =
|
|
std::is_unsigned_v<typename T::result_type> and
|
|
std::is_integral_v<typename T::result_type> and
|
|
requires (T t)
|
|
{
|
|
typename T::result_type;
|
|
|
|
{ T::min () } -> std::same_as<typename T::result_type>;
|
|
{ T::max () } -> std::same_as<typename T::result_type>;
|
|
|
|
{ t () } -> std::same_as<typename T::result_type>;
|
|
};
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
/// Initialise and return a generator using random_device.
|
|
template <UniformRandomBitGenerator GeneratorT>
|
|
GeneratorT
|
|
initialise (void)
|
|
{
|
|
// Approximate the state size of the generator by its size in bytes.
|
|
std::array<unsigned,sizeof (GeneratorT) / sizeof (unsigned) + 1 + 1> seed;
|
|
std::generate_n (
|
|
seed.begin (),
|
|
seed.size () - 1,
|
|
std::random_device ()
|
|
);
|
|
|
|
// Append the current time with the highest resolution we have
|
|
// available. This defends against instances where the implementation
|
|
// of std::random_device is actually deterministic.
|
|
seed[seed.size () - 1] = static_cast<unsigned> (
|
|
std::chrono::high_resolution_clock::now ().time_since_epoch ().count ()
|
|
);
|
|
|
|
std::seed_seq seq (seed.begin (), seed.end ());
|
|
return GeneratorT (seq);
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
/// Returns a correctly pre-initialised reference to a thread-local
|
|
/// generator of an unspecified (but not entirely useless) type.
|
|
///
|
|
/// ie, not LCG.
|
|
inline auto&
|
|
generator (void)
|
|
{
|
|
using generator_t = cruft::rand::general_generator;
|
|
static thread_local auto gen = initialise<generator_t> ();
|
|
return gen;
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
/// A convenience typedef that selects between
|
|
/// std::uniform_real_distribution and std::uniform_int_distribution
|
|
/// depending on the supplied value type.
|
|
template <typename ValueT>
|
|
using uniform_distribution = std::conditional_t<
|
|
std::is_floating_point<ValueT>::value,
|
|
cruft::rand::distribution::uniform_real_distribution<ValueT>,
|
|
cruft::rand::distribution::uniform_int_distribution<ValueT>
|
|
>;
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
/// Returns a value chosen uniformly at random the supplied range.
|
|
///
|
|
/// This is primarily a convenience helper around the uniform_distribution
|
|
/// type. As such, the interval is the same as the std library; ie, closed
|
|
/// for integers, half-open for reals.
|
|
template <typename ValueT, typename GeneratorT>
|
|
requires (UniformRandomBitGenerator<std::remove_cvref_t<GeneratorT>>)
|
|
decltype(auto)
|
|
uniform (ValueT lo, ValueT hi, GeneratorT &&gen)
|
|
{
|
|
return uniform_distribution<ValueT> { lo, hi } (
|
|
std::forward<GeneratorT> (gen)
|
|
);
|
|
}
|
|
|
|
|
|
///------------------------------------------------------------------------
|
|
/// Return a value uniformly random chosen value between lo and hi.
|
|
///
|
|
/// Interval bounds are treated as per the standard Generator
|
|
/// implementations; ie, inclusive for integers, exclusive upper for reals.
|
|
template <typename T>
|
|
decltype(auto)
|
|
uniform (T lo, T hi)
|
|
{
|
|
return uniform<T> (lo, hi, generator ());
|
|
}
|
|
|
|
|
|
///------------------------------------------------------------------------
|
|
/// Return a value uniformly chosen between 0 and the given value.
|
|
///
|
|
/// Interval bounds are treated as per the standard Generator
|
|
/// implementations; ie, inclusive for integers, exclusive upper for reals.
|
|
template <typename T>
|
|
decltype(auto)
|
|
uniform (T hi)
|
|
{
|
|
return uniform<T> (T{0}, hi);
|
|
}
|
|
|
|
|
|
///------------------------------------------------------------------------
|
|
/// Return a value uniformly chosen between 0 and the given value.
|
|
///
|
|
/// Interval bounds are treated as per the standard Generator
|
|
/// implementations; ie, inclusive for integers, exclusive upper for reals.
|
|
template <typename T, typename GeneratorT>
|
|
requires (UniformRandomBitGenerator<std::remove_cvref_t<GeneratorT>>)
|
|
decltype(auto)
|
|
uniform (T hi, GeneratorT &&gen)
|
|
{
|
|
return uniform<T> (T{0}, hi, std::forward<GeneratorT> (gen));
|
|
}
|
|
|
|
|
|
///------------------------------------------------------------------------
|
|
/// Return a uniformly random value chosen on the interval [0,1)
|
|
template <
|
|
typename ValueT,
|
|
typename GeneratorT
|
|
>
|
|
requires (
|
|
std::is_floating_point_v<ValueT> and
|
|
UniformRandomBitGenerator<std::remove_cvref_t<GeneratorT>>
|
|
)
|
|
decltype(auto)
|
|
uniform (GeneratorT &&gen)
|
|
{
|
|
return uniform<ValueT> (ValueT{0}, ValueT{1}, std::forward<GeneratorT> (gen));
|
|
}
|
|
|
|
|
|
///------------------------------------------------------------------------
|
|
/// Return a uniformly random chosen value on the interval [0.f, 1.f)
|
|
template <
|
|
typename ValueT
|
|
>
|
|
requires (std::is_floating_point_v<ValueT>)
|
|
decltype(auto)
|
|
uniform (void)
|
|
{
|
|
return uniform<ValueT> (ValueT{0}, ValueT{1}, generator ());
|
|
}
|
|
|
|
|
|
///------------------------------------------------------------------------
|
|
/// Return a uniformly random chosen value over integral values in the type
|
|
template <typename T>
|
|
requires (std::is_integral_v<T>)
|
|
T
|
|
uniform (void)
|
|
{
|
|
return uniform<T> (
|
|
std::numeric_limits<T>::min (),
|
|
std::numeric_limits<T>::max ()
|
|
);
|
|
}
|
|
|
|
|
|
///------------------------------------------------------------------------
|
|
/// Return a uniformly random chosen value over integral values in the type
|
|
template <typename T, typename GeneratorT>
|
|
requires (std::is_integral_v<T> and UniformRandomBitGenerator<std::remove_cvref_t<GeneratorT>>)
|
|
T
|
|
uniform (GeneratorT &&gen)
|
|
{
|
|
return uniform<T> (
|
|
std::numeric_limits<T>::min (),
|
|
std::numeric_limits<T>::max (),
|
|
std::forward<GeneratorT> (gen)
|
|
);
|
|
}
|
|
|
|
|
|
///------------------------------------------------------------------------
|
|
/// Returns a uniformly random initialised coordinate type by value.
|
|
template <
|
|
typename ValueT,
|
|
typename = std::enable_if_t<
|
|
is_coord_v<ValueT> && std::is_floating_point_v<typename ValueT::value_type>
|
|
>
|
|
>
|
|
ValueT
|
|
uniform (void)
|
|
{
|
|
ValueT res;
|
|
for (auto &v: res)
|
|
v = uniform<typename ValueT::value_type> ();
|
|
return res;
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
/// Choose a value at random from an array
|
|
///
|
|
/// We return pointers (rather than values) so that we can return values
|
|
/// for empty containers without invalid dereferences.
|
|
///
|
|
/// \return A pointer to the chosen value.
|
|
template <typename T, size_t N>
|
|
T*
|
|
choose (T (&t)[N])
|
|
{
|
|
cruft::rand::distribution::uniform_int_distribution<size_t> dist (0, N - 1);
|
|
return &t[dist (generator ())];
|
|
}
|
|
|
|
|
|
///------------------------------------------------------------------------
|
|
/// Choose a value at random from a container.
|
|
///
|
|
/// We return iterators (rather than values) so that we can return values
|
|
/// for empty containers without invalid dereferences.
|
|
//
|
|
/// \return An iterator to the chosen value.
|
|
template <typename ContainerT, typename GeneratorT>
|
|
requires (UniformRandomBitGenerator<std::remove_cvref_t<GeneratorT>>)
|
|
decltype(auto)
|
|
choose (ContainerT &data, GeneratorT &&gen)
|
|
{
|
|
if (data.empty ())
|
|
return data.end ();
|
|
|
|
auto const offset = uniform (
|
|
typename ContainerT::size_type {0},
|
|
data.size () - 1,
|
|
gen
|
|
);
|
|
|
|
return std::next (data.begin (), offset);
|
|
}
|
|
|
|
|
|
///------------------------------------------------------------------------
|
|
/// Choose a value at random from a container.
|
|
///
|
|
/// We return iterators (rather than values) so that we can return values
|
|
/// for empty containers without invalid dereferences.
|
|
///
|
|
/// \return An iterator to the chosen value.
|
|
template <typename ContainerT>
|
|
decltype(auto)
|
|
choose (ContainerT &data)
|
|
{
|
|
return choose (data, generator ());
|
|
}
|
|
}
|