/**
 * Created by Josh Max on 10/12/18
 */

#include <cmath>
#include <iostream>
#include <vector>
#include <sched.h>
#include <chrono>
#include <map>

#define FIRST_NUM 8 // The first number for us to start at
#define INC_NUM 20 // The amount to increment n by each time in graph mode

#ifdef HASPLOTLIBS
#include "matplotlibcpp.h"
namespace plt = matplotlibcpp;

/**
 * Initialize the plotting subsystem.
 *
 * @param n_max The maximum x value for the graph
 */
inline void plot_init(int n_max)
{
    // Set the size of output image to 1200x780 pixels
    plt::figure_size(1200, 780);

    // Set x-axis to interval [FIRST_PRIME, N_MAX]
    plt::xlim(FIRST_NUM, n_max);

    // Add the graph title
    plt::title("Euclid Algorithm Complexity");
}
#endif

/**
 * Perform Euclid's algorithm to determine the GCD of two integers.
 *
 * @param a The first number
 * @param b The second number
 * @param outres A variable to hold the calculated GCD
 * @return The number of modulo operations necessary to find the GCD
 */
inline int gcd(int a, int b, int &outres)
{
    int mod_oper = 0;
    int temp;
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
        mod_oper++;
    }

    outres = a; // Place the result of our GCD
    return mod_oper; // Return the number of modulo operations
}

/**
 * Iterate through the GCDs of a series of integer pairs below n and determine the one with the most
 * modulo operations required to get its result.
 *
 * @param timing_ref The timing data for each loop
 * @param complx_ref The complexity data for each loop
 * @param n The maximum number to iterate to. Should be > 8
 */
void do_euclid(std::map<int, int>& timing_ref, std::map<int, int>& complx_ref, int n)
{
    // Use the std::chrono high resolution clock instead of the POSIX-y, non-portable gettimeofday()
    std::chrono::high_resolution_clock::time_point start_time = std::chrono::high_resolution_clock::now();

    int mod_max = 0;
    int a = FIRST_NUM;
    int a_max = a;
    int b = FIRST_NUM;
    int b_max = b;
    int val_gcd = 0;
    for (; a < n; a++) // Iterate through all n - 1
    {
        for (b = FIRST_NUM; b <= n; b++) // We add 1 to a because a = n - 1
        {
            int gcd_res;
            int rc = gcd(a, b, gcd_res);
            if (rc > mod_max) {
                a_max = a;
                b_max = b;
                val_gcd = gcd_res;
                mod_max = rc;
            }
        }
    }

    // Get the ending time for our function
    std::chrono::high_resolution_clock::time_point end_time = std::chrono::high_resolution_clock::now();
    int duration = (int) std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time).count();

    // Save the timing data
    timing_ref[n] = duration;

    // Add to our discovered complexity vector
    complx_ref[n] = mod_max;

    // Print!
    std::cout << "gcd(" << a_max << ", " << b_max << ") = " << val_gcd << " took "
        << mod_max << " modulus operations ...time required = " << duration << "us" << std::endl;
}

int main(int argc, char** argv)
{
    // Plotting stuff
    std::vector<double> x_val,
        complexity_iters,
        gcd_iters,
        timing_iters;

    // Create a map to hold our complexity data
    std::map<int, int> timing_data,
        calculated_complexity;

    // Get the maximum n value from the user
    int n_max;
    std::cout << "Enter max n: ";
    std::cin >> n_max;

    /**
     * Set the default scheduler to maximum priority.
     *
     * Since essentially all modern kernels are preemptable,
     * By default there is a high degree of process jitter based
     * On the default scheduler settings, so we set our nice value
     * To SCHED_MAX. This also prevents automatic scheduler niceness
     * Adjustment on some kernels. NOTE: To reduce latency even further,
     * SCHED_RR or SCHED_FIFO can be used on Linux kernels with PREEMPT_RT.
     */
    struct sched_param s_param;
    s_param.sched_priority = sched_get_priority_max(SCHED_OTHER);

    if (sched_setscheduler(0, SCHED_OTHER, &s_param) == -1)
        std::cout << "sched_setscheduler() failed" << std::endl;

    int n = n_max;
#ifdef HASPLOTLIBS
    // We're going to plot this data, so we should loop through all n below n_max
    for (n = FIRST_NUM; n <= n_max; n += INC_NUM)
    {
#endif
        do_euclid(timing_data, calculated_complexity, n);
#ifdef HASPLOTLIBS
    }
#endif

#ifdef HASPLOTLIBS
    // Loop through every n increment to build the graph data
    for (unsigned long i = FIRST_NUM; i <= n_max; i += INC_NUM)
    {
        x_val.push_back(i);
        complexity_iters.push_back(log((double) 2 / 3 * i) / log((double) 3 / 2));
        gcd_iters.push_back(calculated_complexity[i]);
        timing_iters.push_back((double) timing_data[i] / (i * i)); // Use O(n^2)
    }

    // Init the plotting library
    plot_init(n_max); // We only want to go to n

    // Name it
    plt::named_plot("log_(3/2)(2n/3)", x_val, complexity_iters);
    plt::named_plot("gcd(a,b)", x_val, gcd_iters);
    plt::named_plot("T(n)/F(n)", x_val, timing_iters);

    // Enable legend
    plt::legend();

    // Show the generated graph
    plt::show();
#endif
}