// La altura con y sin balance: conteos, no tiempos. Semillas fijas.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#include "avl_set.h"
#include "plain_tree.h"

namespace {

std::vector<int> ascending(int n) {
    std::vector<int> keys(n);
    std::iota(keys.begin(), keys.end(), 0);
    return keys;
}

int avl_height(const std::vector<int>& keys, double* mean_depth = nullptr) {
    AvlSet<int> tree;
    for (int key : keys) {
        tree.insert(key);
    }
    if (mean_depth != nullptr) {
        *mean_depth = static_cast<double>(tree.total_depth()) / keys.size();
    }
    return tree.height();
}

}  // namespace

int main() {
    std::cout << "Claves ordenadas\n";
    std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(8) << "1.44log"
              << std::setw(6) << "avl" << std::setw(9) << "sin.bal" << "\n";
    for (int n = 1000; n <= 1024000; n *= 4) {
        std::vector<int> keys = ascending(n);
        double log_n = std::log2(n);
        std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << log_n
                  << std::setw(8) << 1.44 * log_n << std::setw(6) << avl_height(keys);
        if (n <= 16000) {
            PlainTree<int> plain;
            for (int key : keys) {
                plain.insert(key);
            }
            std::cout << std::setw(9) << plain.height();
        } else {
            std::cout << std::setw(9) << "-";
        }
        std::cout << "\n";
    }
    std::cout << "Claves al azar, tres semillas\n";
    std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(8) << "1.44log"
              << std::setw(5) << "a1" << std::setw(5) << "a2" << std::setw(5) << "a3" << std::setw(9) << "prof.avl"
              << std::setw(5) << "s1" << std::setw(5) << "s2" << std::setw(5) << "s3" << std::setw(9) << "prof.sin" << "\n";
    for (int n = 1000; n <= 1024000; n *= 4) {
        double log_n = std::log2(n);
        std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << log_n
                  << std::setw(8) << 1.44 * log_n;
        int avl_heights[3];
        int plain_heights[3];
        double avl_depth = 0;
        double plain_depth = 0;
        for (int seed = 0; seed < 3; seed++) {
            std::vector<int> keys = ascending(n);
            std::mt19937 random(11 + seed);
            std::shuffle(keys.begin(), keys.end(), random);
            double depth = 0;
            avl_heights[seed] = avl_height(keys, &depth);
            avl_depth += depth / 3;
            PlainTree<int> plain;
            for (int key : keys) {
                plain.insert(key);
            }
            auto [height, sum] = plain.height_and_depth();
            plain_heights[seed] = height;
            plain_depth += static_cast<double>(sum) / n / 3;
        }
        for (int height : avl_heights) {
            std::cout << std::setw(5) << height;
        }
        std::cout << std::setprecision(2) << std::setw(9) << avl_depth;
        for (int height : plain_heights) {
            std::cout << std::setw(5) << height;
        }
        std::cout << std::setw(9) << plain_depth << "\n";
    }
    return 0;
}