// Altura y comparaciones al insertar n claves, al azar y ordenadas. Todo son conteos, no tiempos.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#include "bst_set.h"
#include "counted_key.h"

int main() {
    std::cout << "Claves al azar, tres semillas\n";
    std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(6) << "h1" << std::setw(6) << "h2"
              << std::setw(6) << "h3" << std::setw(9) << "h/log2n" << std::setw(11) << "prof.media"
              << std::setw(10) << "prof/log" << "\n";
    for (int n = 1000; n <= 1024000; n *= 4) {
        std::vector<int> keys(n);
        std::iota(keys.begin(), keys.end(), 0);
        double log_n = std::log2(n);
        int heights[3];
        double mean_depth = 0;
        for (int seed = 0; seed < 3; seed++) {
            std::mt19937 random(seed + 1);
            std::shuffle(keys.begin(), keys.end(), random);
            BstSet<int> tree;
            for (int key : keys) {
                tree.insert(key);
            }
            heights[seed] = tree.height();
            mean_depth += static_cast<double>(tree.total_depth()) / n / 3;
        }
        double mean_height = (heights[0] + heights[1] + heights[2]) / 3.0;
        std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << log_n
                  << std::setw(6) << heights[0] << std::setw(6) << heights[1] << std::setw(6) << heights[2]
                  << std::setprecision(2) << std::setw(9) << mean_height / log_n << std::setw(11) << mean_depth
                  << std::setw(10) << mean_depth / log_n << "\n";
    }

    std::cout << "Claves ordenadas\n";
    std::cout << std::setw(9) << "n" << std::setw(9) << "altura" << std::setw(15) << "comparaciones"
              << std::setw(15) << "n(n-1)" << "\n";
    for (int n = 1000; n <= 16000; n *= 2) {
        BstSet<CountedKey> tree;
        CountedKey::comparisons = 0;
        for (int key = 0; key < n; key++) {
            tree.insert(CountedKey{key});
        }
        std::cout << std::setw(9) << n << std::setw(9) << tree.height() << std::setw(15) << CountedKey::comparisons
                  << std::setw(15) << static_cast<long>(n) * (n - 1) << "\n";
    }
    return 0;
}