#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

// Modified Quicksort with three element rule
// Contact Email [email protected]
// Created by I.A

// Configuration Constants
const int NUM_ELEMENTS = 1000000; // 1 million elements
const int NUM_TRIALS = 100;     // 1000 trials

/**
 * Applies the specific rule requested for subarrays of size 3.
 *
 * There are 6 possible orderings:
 * 1 2 3 -> 2 1 3
 * 1 3 2 -> 3 1 2
 * 2 1 3 -> 1 2 3
 * 2 3 1 -> 1 2 3
 * 3 1 2 -> 2 3 1
 * 3 2 1 -> 1 3 2
 *
 * In two cases, this will produce the correct order. In one case, it will disorder the correct order.
 * In the remaining three cases, it changes the order, but whether that is beneficial or not is not clear.
 */
template <class T>
void apply_three_element_rule(std::vector<T>& arr, int low, int high) {
    // Corrected condition: size 3 implies high - low == 2 (e.g., indices 0, 1, 2)
    if (high - low == 2) {
        // a (pivot) b c
        T const& pivot = arr[low];      // First number as pivot
        T const& third_num = arr[high]; // Third number to compare

        // if c < a
        if (third_num <= pivot) {
            // Swap all 3 to make pivot middle, third_num first
            T temp_mid = arr[low + 1];
            // c a b
            arr[high] = temp_mid;
            arr[low + 1] = pivot;
            arr[low] = third_num;
        }
        else {
            // Swap first two
            T temp_mid = arr[low + 1];

            // b a c
            arr[low] = temp_mid;
            arr[low + 1] = pivot;
        }
    }
}

// Standard Hoare partition scheme
template <class T>
int partition(std::vector<T>& arr, int low, int high) {
    T pivot = arr[low];
    int i = low - 1;
    int j = high + 1;

    while (true) {
        do {
            i++;
        } while (arr[i] < pivot);

        do {
            j--;
        } while (arr[j] > pivot);

        if (i >= j)
            return j;

        std::swap(arr[i], arr[j]);
    }
}

/**
 * Quicksort implementation.
 * Integrates the apply_three_element_rule when the subarray size is 3.
 */
static const bool MONTY_SORT = true;
template <class T, bool MS>
void quickSort(std::vector<T>& arr, int low, int high) {
    if (low < high) {
        // Check for specific 3-element case
        if (MONTY_SORT && high - low == 2) {
            apply_three_element_rule(arr, low, high);
        }

        // Partition the array
        int p = partition(arr, low, high);

        // Recursively sort elements before and after partition
        quickSort<T, MS>(arr, low, p);
        quickSort<T, MS>(arr, p + 1, high);
    }
}

/**
 * Quicksort implementation.
 * Integrates the apply_three_element_rule when the subarray size is 3.
 */
bool const OPTIMIZE_2 = true;
bool const OPTIMIZE_3 = true;
template <class T>
void quickSort2(std::vector<T>& arr, int low, int high) {
    int size = high - low;
    if (size <= 0) return;
    if (OPTIMIZE_2 && size == 1) {
        if (arr[high] < arr[low]) std::swap(arr[low], arr[high]);
        return;
    }
    if (OPTIMIZE_3 && size == 2) {
        T const& a = arr[low];
        T const& b = arr[low + 1];
        T const& c = arr[low + 2];
        if (b < a) {            // b < a
            if (c < b) {        // a b c -> c b a
                std::swap(arr[low], arr[high]);
            }
            else if (c < a) {   // a b c -> b c a
                T a = arr[low];
                arr[low] = arr[low + 1];
                arr[low + 1] = arr[high];
                arr[high] = a;
            }
            else {              // a b c -> b a c
                std::swap(arr[low], arr[low + 1]);
            }
        }
        else {                  // a is <= b
            if (c < a) {        // a b c -> c a b
                T c = arr[high];
                arr[high] = arr[low + 1];
                arr[low + 1] = a;
                arr[low] = c;
            }
            else if (c < b) {   // a b c -> a c b
                std::swap(arr[low + 1], arr[high]);
            }
        }
        return;
    }

    // Partition the array
    int p = partition(arr, low, high);

    // Recursively sort elements before and after partition
    quickSort2(arr, low, p);
    quickSort2(arr, p + 1, high);
}

std::string generate_string() {
    static constexpr auto CHARS =
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "abcdefghijklmnopqrstuvwxyz";
    thread_local std::random_device rd;
    thread_local std::mt19937 gen(rd());
    thread_local std::uniform_int_distribution<> dist(0u, std::strlen(CHARS) - 1u);

    std::string::size_type length = dist(gen);
    std::string result(length, '\0');
    std::generate_n(result.begin(), length, [&]() { return CHARS[dist(gen)]; });
    return result;
}

int main() {
    std::cout << "Starting Benchmark..." << std::endl;
    std::cout << "Elements per array: " << NUM_ELEMENTS << std::endl;
    std::cout << "Total Trials: " << NUM_TRIALS << std::endl;

    // Setup random number generation
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> distrib(1, 10000000);

    // Pre-allocate vector
    std::vector<std::string> unsorted(NUM_ELEMENTS);

    // Variable to hold ONLY the time spent sorting
    std::chrono::duration<double> quicksort_time(0);
    std::chrono::duration<double> montysort_time(0);
    std::chrono::duration<double> stdsort_time(0);

    for (int t = 1; t <= NUM_TRIALS; ++t) {
//        std::generate(data.begin(), data.end(), [&distrib, &gen]() { return distrib(gen); });
        std::generate(unsorted.begin(), unsorted.end(), generate_string);

        auto data = unsorted;
        auto start = std::chrono::high_resolution_clock::now();
        quickSort<std::string, false>(data, 0, NUM_ELEMENTS - 1);
        auto end = std::chrono::high_resolution_clock::now();
        quicksort_time += (end - start);

        data = unsorted;
        start = std::chrono::high_resolution_clock::now();
        quickSort<std::string, true>(data, 0, NUM_ELEMENTS - 1);
        end = std::chrono::high_resolution_clock::now();
        montysort_time += (end - start);

        data = unsorted;
        start = std::chrono::high_resolution_clock::now();
        std::sort(data.begin(), data.end());
        end = std::chrono::high_resolution_clock::now();
        stdsort_time += (end - start);

        // Optional: Simple check to ensure sorted (checks only first trial)
        if (t == 1) {
            if (!std::is_sorted(data.begin(), data.end())) {
                std::cerr << "Error: Array not sorted on trial 1!" << std::endl;
                return 1;
            }
        }

        // Progress logging
        if (t % 1 == 0 || t == NUM_TRIALS) {
            std::cout << "Completed Trial " << t << "/" << NUM_TRIALS << "\r" << std::flush;
        }
    }

    std::cout << "\n\nBenchmark Complete." << std::endl;

    // Output stats based on the accumulated sort duration
    std::cout << "Quicksort Time: " << quicksort_time.count() << " seconds" << std::endl;
    std::cout << "MontySort Time: " << montysort_time.count() << " seconds" << std::endl;
    std::cout << "std::sort Time: " << stdsort_time.count() << " seconds" << std::endl;

    return 0;
}