/* randuint32.hpp
   ==============

   Interface definition for the RandUInt32 class, which provides a simple
   way to get random numbers.

   This file is provided as part of CS 70, but may be used in other
   code.
*/

#ifndef RANDUINT32_HPP_INCLUDED
#define RANDUINT32_HPP_INCLUDED

#include <iostream>
#include <cstdint>
#include "jsf.hpp"

/**
 * \class RandUInt32
 * \brief Provides a simplified way to get random numbers.
 *
 * \details
 * Contains a C++-style a random number engine as a data member that it
 * uses to produce the numbers.
 *
 */

class RandUInt32 {
 public:
    /**
     * \brief Initializes a RandUInt32 object with a random seed from
     *        system entropy.
     */
    RandUInt32();

    /**
     * \brief Initializes a RandUInt32 object with user-provided seed.
     * \param seedval  the seed
     */
    RandUInt32(uint64_t seedval);

    /**
     * \brief Get a random value in the range [0,max) (i.e., not including
     *        max).
     * \param max  the past-the-end value
     */
    uint32_t get(size_t max);

    /**
     * \brief Get a 32-bit integer.
     * \warning Do not run `mygen.get() % range`, use `mygen.get(range)`
     *          instead.  The former is both slower and also biased.
     */
    uint32_t get();

 private:
    typedef jsf32 rng_type;  // Can be swapped out for another C++-style PRNG
    rng_type rng_;           // The size of this type depends on this data
                             // member.
};

#endif

/* randuint32.cpp
   ==============

   Implementation of the RandUInt32 class, which provides a simple way
   to get random numbers.

   This file is provided as part of CS 70, but may be used in other
   code.
*/

#include "randuint32.hpp"
#include <chrono>
#include <random>

/*
 * \brief Generates 64 bits of system entropy, based on the two calls to
 *        the random device and one to the high-resolution clock.
 *        64 bits is about the bare minimum for a generic random seed.
 *
 * \note  More about seeding can be found at
 *            https://www.pcg-random.org/categories/seeding.html
 */
static uint64_t systemEntropy() {
    // Set up 64-bits of randomness from the random device.
    std::random_device rdev;
    uint64_t pool = rdev();
    pool <<= 32;
    pool |= rdev();

    // Xor in more entropy from the system clock, in case std::random_device
    // doesn't actually produce system entropy (it's not required to!!).
    // See https://www.pcg-random.org/posts/cpps-random_device.html
    pool ^=
        std::chrono::high_resolution_clock::now().time_since_epoch().count();
    return pool;
}

RandUInt32::RandUInt32() : rng_(systemEntropy()) {
    // Nothing (else) to do.
}

RandUInt32::RandUInt32(uint64_t seedval) : rng_(seedval) {
    // Nothing (else) to do.
}

uint32_t RandUInt32::get(size_t max) {
    std::uniform_int_distribution<uint32_t> udist(0, max - 1);
    return udist(rng_);
}

uint32_t RandUInt32::get() {
    std::uniform_int_distribution<uint32_t> udist(0, UINT32_MAX);
    return udist(rng_);
}

/* randuint32.cpp
   ==============

   Implementation of the RandUInt32 class, which provides a simple way
   to get random numbers.

   This file is provided as part of CS 70, but may be used in other
   code.
*/

#include "randuint32.hpp"
#include <chrono>
#include <random>
#include <limits>

/*
 * \brief Generates 64 bits of system entropy, based on the two calls to
 *        the random device and one to the high-resolution clock.
 *        64 bits is about the bare minimum for a generic random seed.
 *
 * \note  More about seeding can be found at
 *            https://www.pcg-random.org/categories/seeding.html
 */
static uint64_t systemEntropy() {
    // Set up 64-bits of randomness from the random device.
    std::random_device rdev;
    uint64_t pool = rdev();
    pool <<= 32;
    pool |= rdev();

    // Xor in more entropy from the system clock, in case std::random_device
    // doesn't actually produce system entropy (it's not required to!!).
    // See https://www.pcg-random.org/posts/cpps-random_device.html
    pool ^=
        std::chrono::high_resolution_clock::now().time_since_epoch().count();
    return pool;
}

/*
 * \brief C++ allows PRNGs to have completely arbitrary output ranges, for
 *        example, you could have one that outputs only 7 distinct values.
 *        This code provides a compile-time test to make sure the PRNG output
 *        uses the full range of the type and at least 32-bits.
 *        Modern PRNGs are all full-range.
 */
template <typename PRNG>
static constexpr bool is_fullwidth_prng =
    PRNG::min() == 0 && PRNG::max() >= std::numeric_limits<uint32_t>::max() &&
    PRNG::max() == ~(typename PRNG::result_type(0));

RandUInt32::RandUInt32() : rng_(systemEntropy()) {
    // Nothing (else) to do.
}

RandUInt32::RandUInt32(uint64_t seedval) : rng_(seedval) {
    // Nothing (else) to do.
}

uint32_t RandUInt32::get(size_t max) {
    // The downside of using std::uniform_int_distribution is that
    //   a) It's super generic, it can even work with a PRNG that only outputs
    //      random numbers in the range 42 to 56.  That makes it a bit slow.
    //   b) The implementation is up to the standard library, so different
    //      standard libraries produce different outputs.  For portable
    //      reproducibility, we need to write our own.
    // So we avoid it if we can.

    // static_assert(is_fullwidth_prng<rng_type>, "PRNG is not full-width");
    // ^-- uncomment this line to ensure only full-width PRNGs may be used

    if constexpr (is_fullwidth_prng<rng_type>) {
        // This code is rom https://www.pcg-random.org/posts/bounded-rands.html
        // It's the fastest known algorithm for unbiased random numbers in a
        // range.  It's a little more complex than other techniques.
        uint32_t x = rng_();
        uint64_t m = uint64_t(x) * uint64_t(max);
        uint32_t l = uint32_t(m);
        if (l < max) {
            uint32_t t = -max;
            if (t >= max) {
                t -= max;
                if (t >= max) {
                    t %= max;
                }
            }
            while (l < t) {
                x = rng_();
                m = uint64_t(x) * uint64_t(max);
                l = uint32_t(m);
            }
        }
        return m >> 32;
    } else {
        std::uniform_int_distribution<uint32_t> udist(0, max - 1);
        return udist(rng_);
    }
}

uint32_t RandUInt32::get() {
    if constexpr (is_fullwidth_prng<rng_type>) {
        // If so, we don't need to do anything to the result.
        return rng_();
    } else {
        std::uniform_int_distribution<uint32_t> udist(
            0, std::numeric_limits<uint32_t>::max());
        return udist(rng_);
    }
}