// Cuenta los saltos por parent de union-find, con y sin cada mejora. No mide tiempos.
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <random>
#include <string>
#include <vector>

#include "counting_forest.h"

namespace {

struct Result {
    std::int64_t hops;
    std::int64_t operations;
    int height;
};

// Une 0-1, 1-2, 2-3... y después pregunta por todos.
Result chain(int n, bool by_rank, bool compress) {
    CountingForest forest(n, by_rank, compress);
    std::int64_t operations = 0;
    for (int i = 0; i + 1 < n; i++) {
        forest.unite(i, i + 1);
        operations++;
    }
    int height = forest.height();
    for (int i = 0; i < n; i++) {
        forest.find(i);
        operations++;
    }
    return {forest.hops(), operations, height};
}

// 4n operaciones al azar: la mitad son unite y la mitad find.
Result random_work(int n, bool by_rank, bool compress) {
    CountingForest forest(n, by_rank, compress);
    std::mt19937 rng(14);
    std::int64_t operations = 4 * static_cast<std::int64_t>(n);
    for (std::int64_t i = 0; i < operations; i++) {
        int a = static_cast<int>(rng() % n);
        int b = static_cast<int>(rng() % n);
        if (i % 2 == 0) {
            forest.unite(a, b);
        } else {
            forest.find(a);
        }
    }
    return {forest.hops(), operations, forest.height()};
}

// Une árboles iguales: 2^k nodos con altura k, y el nodo más hondo es n - 1 en este armado.
CountingForest binomial(int n, bool compress) {
    CountingForest forest(n, true, compress);
    for (int size = 1; size < n; size *= 2) {
        for (int start = 0; start + size < n; start += 2 * size) {
            forest.unite(start, start + size);
        }
    }
    return forest;
}

void print_row(const std::string& name, int n, const Result& result) {
    std::cout << std::left << std::setw(26) << name << std::right << std::setw(9) << n << std::setw(8) << result.height
              << std::setw(13) << result.hops << std::setw(12) << std::fixed << std::setprecision(2)
              << static_cast<double>(result.hops) / static_cast<double>(result.operations) << "\n";
}

}  // namespace

int main() {
    std::cout << "Cadena 0-1, 1-2, 2-3...\n";
    std::cout << "variante                          n  altura       saltos  saltos/op\n";
    for (int n : {1 << 10, 1 << 14}) {
        print_row("sin mejoras", n, chain(n, false, false));
        print_row("solo rango", n, chain(n, true, false));
        print_row("solo compresion", n, chain(n, false, true));
        print_row("rango y compresion", n, chain(n, true, true));
    }
    std::cout << "\nAl azar, 4n operaciones\n";
    std::cout << "variante                          n  altura       saltos  saltos/op\n";
    for (int n : {1 << 10, 1 << 14, 1 << 18, 1 << 20}) {
        print_row("solo rango", n, random_work(n, true, false));
        print_row("rango y compresion", n, random_work(n, true, true));
    }

    std::cout << "\nUn solo find en el peor arbol, con las dos mejoras\n";
    std::cout << "        n  log2 n  primer find  segundo find\n";
    for (int exponent : {10, 14, 18, 20}) {
        int n = 1 << exponent;
        CountingForest forest = binomial(n, true);
        int deepest = 0;
        for (int x = 0; x < n; x++) {
            if (forest.depth(x) > forest.depth(deepest)) {
                deepest = x;
            }
        }
        std::int64_t start = forest.hops();
        forest.find(deepest);
        std::int64_t first = forest.hops() - start;
        start = forest.hops();
        forest.find(deepest);
        std::cout << std::setw(9) << n << std::setw(8) << exponent << std::setw(13) << first << std::setw(14)
                  << forest.hops() - start << "\n";
    }
    return 0;
}