1#pragma once23#include "common.h"4#include "pattern.h"56#include <algorithm>7#include <cmath>8#include <cstdlib>9#include <iterator>10#include <limits>11#include <random>12#include <string>13#include <type_traits>14#include <utility>15#include <vector>1617namespace jngen {1819void assertRandomEngineConsistency();20void assertIntegerSizes();21void registerGen(int argc, char *argv[], int version = 1);2223class Random;2425class BaseTypedRandom {26public:27    BaseTypedRandom(Random& random) : random(random) {}2829protected:30    Random& random;31};3233template<typename T>34struct TypedRandom;3536uint64_t maskForBound(uint64_t bound);3738template<typename Result, typename Source>39Result uniformRandom(Result bound, Random& random, Source (Random::*method)()) {40    static_assert(sizeof(Result) <= sizeof(Source),41        "uniformRandom: Source type must be at least as large as Result type");42#ifdef JNGEN_FAST_RANDOM43    return (random.*method)() % bound;44#else45    Source mask = maskForBound(bound);46    while (true) {47        Source outcome = (random.*method)() & mask;48        if (outcome < static_cast<Source>(bound)) {49            return outcome;50        }51    }52#endif53}5455class Random {56public:57    Random() {58        assertRandomEngineConsistency();59        assertIntegerSizes();60        std::vector<uint32_t> seedSeq;61        // 4 random_device calls is enough for everyone62        std::random_device rd;63        for (size_t i = 0; i < 4; ++i) {64            seedSeq.push_back(rd());65        }66        seed(seedSeq);6768    }6970    void seed(uint32_t val);71    void seed(const std::vector<uint32_t>& seed);7273    uint32_t next();74    uint64_t next64();75    double nextf();7677    int next(int n);78    long long next(long long n);79    size_t next(size_t n);80    double next(double n);8182    int next(int l, int r);83    long long next(long long l, long long r);84    size_t next(size_t l, size_t r);85    double next(double l, double r);8687    int wnext(int n, int w);88    long long wnext(long long n, int w);89    size_t wnext(size_t n, int w);90    double wnext(double n, int w);9192    int wnext(int l, int r, int w);93    long long wnext(long long l, long long r, int w);94    size_t wnext(size_t l, size_t r, int w);95    double wnext(double l, double r, int w);9697    std::string next(const std::string& pattern);9899    template<typename ... Args>100    std::string next(const std::string& pattern, Args... args) {101        return next(format(pattern, args...));102    }103104    template<typename T, typename ... Args>105    T tnext(Args... args) {106        return TypedRandom<T>{*this}.next(args...);107    }108109    template<typename ... Args>110    std::pair<int, int> nextp(Args... args) {111        return tnext<std::pair<int, int>>(args...);112    }113114    template<typename Iterator>115    auto choice(Iterator begin, Iterator end)116            -> typename std::iterator_traits<Iterator>::value_type117    {118        auto length = std::distance(begin, end);119        ensure(length > 0, "Cannot select from a range of negative length");120        size_t index = tnext<size_t>(length);121        std::advance(begin, index);122        return *begin;123    }124125    template<typename Container>126    typename Container::value_type choice(const Container& container) {127        ensure(!container.empty(), "Cannot select from an empty container");128        return choice(container.begin(), container.end());129    }130131    template<typename T>132    T choice(const std::initializer_list<T>& ilist) {133        return choice(ilist.begin(), ilist.end());134    }135136    template<typename Numeric>137    size_t nextByDistribution(const std::vector<Numeric>& distribution) {138        ensure(!distribution.empty(), "Cannot sample by empty distribution");139        Numeric sum = std::accumulate(140                distribution.begin(), distribution.end(), Numeric(0));141        auto x = next(sum);142        for (size_t i = 0; i < distribution.size(); ++i) {143            if (x < distribution[i]) {144                return i;145            }146            x -= distribution[i];147        }148        return distribution.size() - 1;149    }150151    template<typename Numeric>152    size_t nextByDistribution(const std::initializer_list<Numeric>& ilist) {153        // TODO: looks suboptimal154        return nextByDistribution(std::vector<Numeric>(ilist));155    }156157private:158    template<typename T, typename ...Args>159    T smallWnext(int w, Args... args) {160        ENSURE(std::abs(w) <= WNEXT_LIMIT);161        T result = next(args...);162        while (w > 0) {163            result = std::max(result, next(args...));164            --w;165        }166        while (w < 0) {167            result = std::min(result, next(args...));168            ++w;169        }170        return result;171    }172173    double realWnext(int w) {174        if (w == 0) {175            return nextf();176        } else if (w > 0) {177            return std::pow(nextf(), 1.0 / (w + 1));178        } else {179            return 1.0 - std::pow(nextf(), 1.0 / (-w + 1));180        }181    }182183    std::mt19937 randomEngine_;184    constexpr static int WNEXT_LIMIT = 8;185};186187JNGEN_EXTERN Random rnd;188189template<>190struct TypedRandom<int> : public BaseTypedRandom {191    using BaseTypedRandom::BaseTypedRandom;192    int next(int n) { return random.next(n); }193    int next(int l, int r) { return random.next(l, r); }194};195196template<>197struct TypedRandom<double> : public BaseTypedRandom {198    using BaseTypedRandom::BaseTypedRandom;199    double next(double n) { return random.next(n); }200    double next(double l, double r) { return random.next(l, r); }201};202203template<>204struct TypedRandom<long double> : public BaseTypedRandom {205    using BaseTypedRandom::BaseTypedRandom;206    double next(double n) { return random.next(n); }207    double next(double l, double r) { return random.next(l, r); }208};209210template<>211struct TypedRandom<long long> : public BaseTypedRandom {212    using BaseTypedRandom::BaseTypedRandom;213    long long next(long long n) { return random.next(n); }214    long long next(long long l, long long r) { return random.next(l, r); }215};216217template<>218struct TypedRandom<size_t> : public BaseTypedRandom {219    using BaseTypedRandom::BaseTypedRandom;220    size_t next(size_t n) { return random.next(n); }221    size_t next(size_t l, size_t r) { return random.next(l, r); }222};223224template<>225struct TypedRandom<char> : public BaseTypedRandom {226    using BaseTypedRandom::BaseTypedRandom;227    char next(char n) { return random.next(n); }228    char next(char l, char r) { return random.next(l, r); }229};230231template<typename T>232struct TypedRandom : public BaseTypedRandom {233    using BaseTypedRandom::BaseTypedRandom;234    template<typename ... Args>235    T next(Args... args) { return random.next(args...); }236};237238struct RandomPairTraits {239    const bool ordered;240    const bool distinct;241};242243#ifdef JNGEN_DECLARE_ONLY244extern RandomPairTraits opair, dpair, odpair, dopair;245#else246RandomPairTraits opair{true, false};247RandomPairTraits dpair{false, true};248RandomPairTraits odpair{true, true};249RandomPairTraits dopair{true, true};250#endif251252template<>253struct TypedRandom<std::pair<int, int>> : public BaseTypedRandom {254    using BaseTypedRandom::BaseTypedRandom;255256    std::pair<int, int> next(int n) {257        return next(n, {false, false});258    }259    std::pair<int, int> next(int l, int r) {260        return next(l, r, {false, false});261    }262263    std::pair<int, int> next(int n, RandomPairTraits traits) {264        int first = rnd.next(n);265        int second;266        do {267            second = rnd.next(n);268        } while (traits.distinct && first == second);269        if (traits.ordered && first > second) {270            std::swap(first, second);271        }272        return {first, second};273    }274    std::pair<int, int> next(int l, int r, RandomPairTraits traits) {275        auto res = next(r-l+1, traits);276        res.first += l;277        res.second += l;278        return res;279    }280281private:282    std::pair<int, int> ordered(std::pair<int, int> pair) const {283        if (pair.first > pair.second) {284            std::swap(pair.first, pair.second);285        }286        return pair;287    }288};289290} // namespace jngen291292using jngen::Random;293294using jngen::rnd;295using jngen::opair;296using jngen::dpair;297using jngen::dopair;298using jngen::odpair;299300using jngen::registerGen;301302#ifndef JNGEN_DECLARE_ONLY303#define JNGEN_INCLUDE_RANDOM_INL_H304#include "impl/random_inl.h"305#undef JNGEN_INCLUDE_RANDOM_INL_H306#endif // JNGEN_DECLARE_ONLY