/**
 * ============================================================
 *   ANALISIS KOMPLEKSITAS WAKTU - ALGORITMA PENGURUTAN
 * ============================================================
 * Algoritma  : Bubble Sort, Selection Sort, Merge Sort, Quick Sort
 * Kasus      : Best Case, Worst Case, Average Case
 * Kompilasi  : g++ -O0 -std=c++11 -o sort_benchmark sort_benchmark.cpp
 * ============================================================
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
#include <iomanip>
#include <string>
#include <sstream>
#include <map>

using namespace std;
using namespace std::chrono;

// ============================================================
//  KONFIGURASI
// ============================================================

const int SIZES[]      = { 10000, 20000, 100000, 200000, 1000000, 2000000 };
const int SIZES_COUNT  = 6;

const bool RUN_BUBBLE    = true;
const bool RUN_SELECTION = true;
const bool RUN_MERGE     = true;
const bool RUN_QUICK     = true;

const bool RUN_BEST    = true;   // sudah terurut naik
const bool RUN_WORST   = true;   // terurut terbalik
const bool RUN_AVERAGE = true;   // acak

// Seed random (0 = acak setiap run)
const unsigned int RANDOM_SEED = 42;

// O(n^2) di-skip jika N melebihi ini
const int O2_LIMIT = 200000;

// Lebar bar chart
const int BAR_WIDTH = 40;

// Batas total waktu program (menit). Set 0 untuk nonaktifkan.
const double OVERTIME_MINUTES = 30.0;

// ============================================================
//  SENTINEL
//  -1 = skipped (N > O2_LIMIT)
//  -2 = overtime
// ============================================================
const double VAL_SKIP = -1.0;
const double VAL_OT   = -2.0;

// ============================================================
//  GENERATOR
// ============================================================

vector<int> genBest(int n) {
    vector<int> d(n);
    for (int i = 0; i < n; i++) d[i] = i + 1;
    return d;
}

vector<int> genWorst(int n) {
    vector<int> d(n);
    for (int i = 0; i < n; i++) d[i] = n - i;
    return d;
}

vector<int> genAverage(int n) {
    vector<int> d(n);
    for (int i = 0; i < n; i++) d[i] = i + 1;
    mt19937 rng(RANDOM_SEED == 0 ? (unsigned int)random_device{}() : RANDOM_SEED);
    shuffle(d.begin(), d.end(), rng);
    return d;
}

// ============================================================
//  ALGORITMA
// ============================================================

void bubbleSort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++)
            if (a[j] > a[j+1]) { swap(a[j], a[j+1]); swapped = true; }
        if (!swapped) break;
    }
}

void selectionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        int m = i;
        for (int j = i + 1; j < n; j++) if (a[j] < a[m]) m = j;
        if (m != i) swap(a[i], a[m]);
    }
}

void mergeHelp(vector<int>& a, int l, int mid, int r) {
    int n1 = mid-l+1, n2 = r-mid;
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) L[i] = a[l+i];
    for (int j = 0; j < n2; j++) R[j] = a[mid+1+j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) a[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) a[k++] = L[i++];
    while (j < n2) a[k++] = R[j++];
}

void mergeRec(vector<int>& a, int l, int r) {
    if (l < r) {
        int m = l + (r-l)/2;
        mergeRec(a, l, m); mergeRec(a, m+1, r);
        mergeHelp(a, l, m, r);
    }
}

void mergeSort(vector<int>& a) { mergeRec(a, 0, (int)a.size()-1); }

int qpartition(vector<int>& a, int lo, int hi) {
    int mid = lo + (hi-lo)/2;
    if (a[lo] > a[mid])  swap(a[lo], a[mid]);
    if (a[lo] > a[hi])   swap(a[lo], a[hi]);
    if (a[mid] > a[hi])  swap(a[mid], a[hi]);
    swap(a[mid], a[hi-1]);
    int pivot = a[hi-1], i = lo-1;
    for (int j = lo; j < hi-1; j++) if (a[j] <= pivot) swap(a[++i], a[j]);
    swap(a[i+1], a[hi-1]);
    return i+1;
}

void quickRec(vector<int>& a, int lo, int hi) {
    if (lo < hi) { int p = qpartition(a,lo,hi); quickRec(a,lo,p-1); quickRec(a,p+1,hi); }
}

void quickSort(vector<int>& a) { if (a.size() > 1) quickRec(a, 0, (int)a.size()-1); }

// ============================================================
//  TIMER
// ============================================================

typedef time_point<high_resolution_clock> TimePoint;

double measure(void (*fn)(vector<int>&), vector<int> data) {
    TimePoint s = high_resolution_clock::now();
    fn(data);
    TimePoint e = high_resolution_clock::now();
    return duration<double, milli>(e - s).count();
}

double elapsed(const TimePoint& start) {
    return duration<double, milli>(high_resolution_clock::now() - start).count();
}

bool overtime(const TimePoint& start) {
    return OVERTIME_MINUTES > 0 && elapsed(start) >= OVERTIME_MINUTES * 60000.0;
}

// ============================================================
//  FORMAT
// ============================================================

string fmtN(int n) {
    if (n >= 1000000) return to_string(n/1000000) + ".000.000";
    if (n >= 1000)    return to_string(n/1000) + ".000";
    return to_string(n);
}

string fmtT(double ms) {
    if (ms == VAL_OT)   return "  OVERTIME";
    if (ms == VAL_SKIP) return "   SKIPPED";
    ostringstream o; o << fixed << setprecision(2) << ms << " ms";
    return o.str();
}

string makeBar(double ms, double maxVal) {
    if (ms == VAL_SKIP) {
        return string(BAR_WIDTH, ' ') + "  (skipped)";
    }
    if (ms == VAL_OT) {
        string b;
        for (int i = 0; i < BAR_WIDTH; i++) b += "\xe2\x96\x91"; // ░
        return b + "  OVERTIME";
    }
    int fill = (maxVal > 0) ? (int)((ms / maxVal) * BAR_WIDTH) : 0;
    if (fill == 0 && ms > 0) fill = 1;
    string b;
    for (int i = 0; i < fill; i++)       b += "\xe2\x96\x88"; // █
    for (int i = fill; i < BAR_WIDTH; i++) b += " ";
    return b;
}

void sep2(int w=72) { cout << string(w,'=') << "\n"; }
void sep1(int w=72) { cout << string(w,'-') << "\n"; }

// ============================================================
//  STRUKTUR HASIL
// ============================================================

struct Result {
    double best, worst, avg;
    Result() : best(VAL_SKIP), worst(VAL_SKIP), avg(VAL_SKIP) {}
};

// ============================================================
//  CHART PER KASUS
// ============================================================

struct AlgoEntry {
    string name;
    bool   enabled;
    void (*fn)(vector<int>&);
};

void printChart(
    const string& label,
    const vector<AlgoEntry>& algos,
    const map<string, map<int,Result> >& res,
    int caseIdx   // 0=best 1=worst 2=avg
) {
    // Cari max (nilai nyata saja)
    double maxVal = 0;
    for (int a = 0; a < (int)algos.size(); a++) {
        if (!algos[a].enabled) continue;
        for (int i = 0; i < SIZES_COUNT; i++) {
            const Result& r = res.at(algos[a].name).at(SIZES[i]);
            double v = (caseIdx==0)?r.best:(caseIdx==1)?r.worst:r.avg;
            if (v > 0 && v > maxVal) maxVal = v;
        }
    }

    cout << "\n"; sep2();
    cout << "  " << label << "\n"; sep2();

    for (int a = 0; a < (int)algos.size(); a++) {
        if (!algos[a].enabled) continue;
        cout << "\n  " << algos[a].name << "\n"; sep1();
        for (int i = 0; i < SIZES_COUNT; i++) {
            const Result& r = res.at(algos[a].name).at(SIZES[i]);
            double v = (caseIdx==0)?r.best:(caseIdx==1)?r.worst:r.avg;
            cout << "  " << setw(10) << left << fmtN(SIZES[i])
                 << " | " << makeBar(v, maxVal) << "\n";
        }
        cout << "\n";
    }
}

// ============================================================
//  TABEL RINGKASAN
// ============================================================

void printTable(
    const vector<AlgoEntry>& algos,
    const map<string, map<int,Result> >& res
) {
    cout << "\n"; sep2();
    cout << "  TABEL RINGKASAN WAKTU (ms)\n"; sep2();
    cout << left
         << setw(14) << "Algoritma"
         << setw(12) << "N"
         << setw(18) << "Best Case"
         << setw(18) << "Worst Case"
         << setw(18) << "Avg Case"
         << "\n";
    sep1();
    for (int a = 0; a < (int)algos.size(); a++) {
        if (!algos[a].enabled) continue;
        bool first = true;
        for (int i = 0; i < SIZES_COUNT; i++) {
            const Result& r = res.at(algos[a].name).at(SIZES[i]);
            cout << left
                 << setw(14) << (first ? algos[a].name : "")
                 << setw(12) << fmtN(SIZES[i])
                 << setw(18) << fmtT(r.best)
                 << setw(18) << fmtT(r.worst)
                 << setw(18) << fmtT(r.avg)
                 << "\n";
            first = false;
        }
        sep1();
    }
}

// ============================================================
//  MAIN
// ============================================================

int main() {
    vector<AlgoEntry> algos;
    AlgoEntry e;

    e.name="BubbleSort"; e.enabled=RUN_BUBBLE;    e.fn=bubbleSort;    algos.push_back(e);
    e.name="SelectSort"; e.enabled=RUN_SELECTION; e.fn=selectionSort; algos.push_back(e);
    e.name="MergeSort";  e.enabled=RUN_MERGE;     e.fn=mergeSort;     algos.push_back(e);
    e.name="QuickSort";  e.enabled=RUN_QUICK;     e.fn=quickSort;     algos.push_back(e);

    // Inisialisasi hasil
    map<string, map<int,Result> > results;
    for (int a = 0; a < (int)algos.size(); a++)
        for (int i = 0; i < SIZES_COUNT; i++)
            results[algos[a].name][SIZES[i]] = Result();

    // ── Phase 1: Benchmark ─────────────────────────────────────
    TimePoint prog_start = high_resolution_clock::now();
    bool ot = false;

    cout << "\n"; sep2();
    cout << "  BENCHMARK SEDANG BERJALAN...\n";
    if (OVERTIME_MINUTES > 0)
        cout << "  Batas waktu : " << OVERTIME_MINUTES << " menit\n";
    sep2(); cout << "\n";

    for (int a = 0; a < (int)algos.size(); a++) {
        if (!algos[a].enabled) continue;
        const string& name = algos[a].name;

        for (int i = 0; i < SIZES_COUNT; i++) {
            int n = SIZES[i];
            bool sizeSkip = (name=="BubbleSort"||name=="SelectSort") && n > O2_LIMIT;
            Result r;

            if (sizeSkip) {
                cout << "  [--]  " << setw(12) << name
                     << " N=" << setw(10) << fmtN(n)
                     << " | skipped (N > " << fmtN(O2_LIMIT) << ")\n";
                cout.flush();
                results[name][n] = r;
                continue;
            }

            // Best
            if (RUN_BEST) {
                if (ot) {
                    r.best = VAL_OT;
                    cout << "  [!!]  " << setw(12) << name << " N=" << setw(10) << fmtN(n) << " | Best    = OVERTIME\n";
                } else {
                    r.best = measure(algos[a].fn, genBest(n));
                    cout << "  [OK]  " << setw(12) << name << " N=" << setw(10) << fmtN(n) << " | Best    = " << fmtT(r.best) << "\n";
                    if (overtime(prog_start)) {
                        ot = true;
                        cout << "\n  [!!] OVERTIME — " << fixed << setprecision(1)
                             << elapsed(prog_start)/60000.0 << " menit"
                             << " (batas: " << OVERTIME_MINUTES << " menit)\n"
                             << "  [!!] Sisa run ditandai OVERTIME.\n\n";
                    }
                }
            }

            // Worst
            if (RUN_WORST) {
                if (ot) {
                    r.worst = VAL_OT;
                    cout << "  [!!]  " << setw(12) << name << " N=" << setw(10) << fmtN(n) << " | Worst   = OVERTIME\n";
                } else {
                    r.worst = measure(algos[a].fn, genWorst(n));
                    cout << "  [OK]  " << setw(12) << name << " N=" << setw(10) << fmtN(n) << " | Worst   = " << fmtT(r.worst) << "\n";
                    if (overtime(prog_start)) {
                        ot = true;
                        cout << "\n  [!!] OVERTIME — " << fixed << setprecision(1)
                             << elapsed(prog_start)/60000.0 << " menit"
                             << " (batas: " << OVERTIME_MINUTES << " menit)\n"
                             << "  [!!] Sisa run ditandai OVERTIME.\n\n";
                    }
                }
            }

            // Average
            if (RUN_AVERAGE) {
                if (ot) {
                    r.avg = VAL_OT;
                    cout << "  [!!]  " << setw(12) << name << " N=" << setw(10) << fmtN(n) << " | Average = OVERTIME\n";
                } else {
                    r.avg = measure(algos[a].fn, genAverage(n));
                    cout << "  [OK]  " << setw(12) << name << " N=" << setw(10) << fmtN(n) << " | Average = " << fmtT(r.avg) << "\n";
                    if (overtime(prog_start)) {
                        ot = true;
                        cout << "\n  [!!] OVERTIME — " << fixed << setprecision(1)
                             << elapsed(prog_start)/60000.0 << " menit"
                             << " (batas: " << OVERTIME_MINUTES << " menit)\n"
                             << "  [!!] Sisa run ditandai OVERTIME.\n\n";
                    }
                }
            }

            results[name][n] = r;
            cout.flush();
        }
        cout << "\n";
    }

    // ── Phase 2: Chart per kasus ───────────────────────────────
    if (RUN_BEST)    printChart("BEST CASE    (array sudah terurut naik)", algos, results, 0);
    if (RUN_WORST)   printChart("WORST CASE   (array terurut terbalik)",   algos, results, 1);
    if (RUN_AVERAGE) printChart("AVERAGE CASE (array acak / random)",      algos, results, 2);

    // ── Phase 3: Tabel ─────────────────────────────────────────
    printTable(algos, results);

    // ── Footer ─────────────────────────────────────────────────
    double total = elapsed(prog_start);
    cout << "\n"; sep2();
    if (ot) cout << "  [!!] BENCHMARK DIHENTIKAN KARENA OVERTIME\n";
    cout << "  Total waktu : " << fixed << setprecision(2)
         << total/1000.0 << " detik (" << total/60000.0 << " menit)\n";
    cout << "  Bar : \xe2\x96\x88 = normal   \xe2\x96\x91 = OVERTIME   (skipped) = N > batas\n";
    sep2(); cout << "\n";

    return 0;
}