Find the Min

gistfile1.cpp

/*
CC0 1.0 Universal (CC0 1.0) 
Public Domain
https://creativecommons.org/publicdomain/zero/1.0/
*/

#include <string>
#include <vector>
#include <iostream>
#include <fstream>
#include <stdexcept>
#include <sstream>
#include <cstdint>

#include <boost/fusion/tuple.hpp>
#include <boost/fusion/algorithm.hpp>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/identity.hpp>

namespace
{

/* m[] is in the field of r and 1 <= r <= 10^9
 * max(m[]) = max(r) - 1 = 2^x where x = ln (10^9 - 1) / ln (2) = <30
 * therefore 32bit signed ints are fine for m[i], and still allow us to use < 0 for junk.
 *
 * The prng [b * m[i-1] + c] cannot exceed ~2^60 so we'll use a 64bit signed int in the generator
 * without putting too much thought in to the mathematics.
 *
 * a, b, c, r, n, k will all be ap_int_t
 */
typedef int32_t ap_int_t;


struct array_prng_t
{
    array_prng_t (ap_int_t const a_, ap_int_t const b_, ap_int_t const c_, ap_int_t const r_)
        : a(a_), b(b_), c(c_), r(r_), value(a_) {}

    ap_int_t operator()()
    {
        ap_int_t const old_val = value;
        value = ((b * int64_t(value)) + c) % r;
        return old_val;
    }

    void reset()
    {
        value = a;
    }

    ap_int_t a, b, c, r;
    ap_int_t value;
};


struct array_problem_param_t
{
    array_problem_param_t (ap_int_t n_, ap_int_t k_): n(n_), k(k_) {}
    ap_int_t n, k;
};


struct array_problem_t
{
    array_problem_t (array_prng_t&& prng_, array_problem_param_t&& params_)
        : prng(prng_), params(params_) {}

    ap_int_t nth_element() const;

    array_prng_t          prng;
    array_problem_param_t params;
};


// Not strictly required, but op>> int will jump over new lines, whereas this'll blow up.
template <typename T, typename Tuple>
void
snort_line_of (std::istream& src_stream, Tuple&& dest)
{
    std::string line;
    std::getline (src_stream, line);
    std::istringstream line_iss (line);

    line_iss.exceptions (std::ios::failbit | std::ios::badbit);
    boost::fusion::for_each (std::forward<Tuple>(dest), [&line_iss](T& val) { line_iss >> val; });
}


std::vector<array_problem_t>
get_array_problem_vec
(
    std::istream& is,
    ap_int_t const n_array_problems
)
{
    std::vector<array_problem_t> array_problem_vec;

    if ((n_array_problems < 1) || (n_array_problems > 20))
        throw std::range_error ("Number of array problems out of range 5 <= m <= 20");

    array_problem_vec.reserve (n_array_problems);
    auto array_problem_inserter = std::back_inserter (array_problem_vec);

    std::generate_n (array_problem_inserter, n_array_problems,
        [&is]() {
            ap_int_t  n, k;
            ap_int_t  a, b, c, r;
            auto param_tuple = boost::fusion::tie(n, k);
            auto prng_tuple  = boost::fusion::tie(a, b, c, r);

            param_tuple = boost::fusion::make_tuple(-1, -1);
            prng_tuple  = boost::fusion::make_tuple(-1, -1,-1, -1);

            snort_line_of<ap_int_t> (is, param_tuple);
            snort_line_of<ap_int_t> (is, prng_tuple);
            return array_problem_t  (array_prng_t (a, b, c, r), array_problem_param_t (n, k));
        }
    );

    return array_problem_vec;
}


ap_int_t
array_problem_t::nth_element
() const
{
    struct in_gen_order {};
    struct in_order     {};

    array_prng_t prng (this->prng);
    prng.reset();

    boost::multi_index_container<ap_int_t,
        boost::multi_index::indexed_by<
            boost::multi_index::sequenced<boost::multi_index::tag<in_gen_order>>,
            boost::multi_index::ordered_non_unique<boost::multi_index::tag<in_order>,
                boost::multi_index::identity<ap_int_t>>
        > // Yeah, yeah...
    > num_array;

    std::generate_n (std::back_inserter(num_array), this->params.k, prng);
    auto const& in_order_index = num_array.get<in_order>();

    for (ap_int_t i = this->params.k; i < this->params.n; ++i)
    {
        ap_int_t min_missing = 0;

        auto gap_front = *in_order_index.begin();
        auto gap_end = in_order_index.upper_bound (gap_front);

        if (0 == gap_front) {
            while ((gap_end != in_order_index.end()) && (*gap_end <= (gap_front + 1))) {
                gap_front = *gap_end;
                gap_end   = in_order_index.upper_bound (gap_front);
            }
            min_missing = gap_front + 1;
        }

        // Simulate a circular buffer
        num_array.pop_front ();
        num_array.push_back (min_missing);
    }

    return num_array.back();
}


} // anonymous namespace


int main
(int const argc, char* argv[])
{
    std::ifstream src_file;
    unsigned n_array_problems = 0;

    if (argc < 2)
        return EXIT_FAILURE;

    src_file.exceptions (std::ios::failbit | std::ios::badbit);

    try {
        std::string n_array_problems_str;

        src_file.open   (argv[1]);
        std::getline    (src_file, n_array_problems_str);
        n_array_problems = std::stoul (n_array_problems_str);

        std::vector<array_problem_t>
            array_problem_vec = get_array_problem_vec (src_file, n_array_problems);

        uint32_t i = 1;
        std::for_each (array_problem_vec.begin(), array_problem_vec.end(),
            [&i](array_problem_t const& array_problem)
            { std::cout << "Case #" << i++ << ": " << array_problem.nth_element() << std::endl; });

        return EXIT_SUCCESS;
    }
    catch (std::exception& e) {
        std::cerr << "6 minutes should be enough for anyone." << std::endl;
        throw;
    }

    return EXIT_FAILURE;
}