// La altura de AVL y de rojinegro, con las mismas claves. Son conteos: no dependen de la máquina.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#include "avl_set.h"
#include "rb_set.h"

namespace {

struct Row {
    int avl_height = 0;
    int rb_height = 0;
    int blacks = 0;
    double avl_depth = 0;
    double rb_depth = 0;
};

Row measure(const std::vector<int>& keys) {
    AvlSet<int> avl;
    RedBlackSet<int> rb;
    for (int key : keys) {
        avl.insert(key);
        rb.insert(key);
    }
    double n = static_cast<double>(keys.size());
    return {avl.height(), rb.height(), rb.black_height(), avl.total_depth() / n, rb.total_depth() / n};
}

}  // namespace

int main() {
    std::cout << "Claves ordenadas, de menor a mayor\n";
    std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(7) << "cota" << std::setw(6) << "avl" << std::setw(6) << "rn"
              << std::setw(8) << "negros" << std::setw(10) << "prof.avl" << std::setw(9) << "prof.rn" << "\n";
    for (int n = 1000; n <= 1024000; n *= 4) {
        std::vector<int> keys(n);
        std::iota(keys.begin(), keys.end(), 0);
        Row row = measure(keys);
        std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << std::log2(n)
                  << std::setw(7) << 2 * std::log2(n + 1.0) - 1 << std::setw(6) << row.avl_height << std::setw(6) << row.rb_height
                  << std::setw(8) << row.blacks << std::setprecision(2) << std::setw(10) << row.avl_depth << std::setw(9) << row.rb_depth << "\n";
    }
    std::cout << "Claves al azar, tres semillas\n";
    std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(7) << "cota" << std::setw(5) << "a1" << std::setw(4) << "a2" << std::setw(4) << "a3"
              << std::setw(5) << "r1" << std::setw(4) << "r2" << std::setw(4) << "r3" << std::setw(10) << "prof.avl" << std::setw(9) << "prof.rn" << "\n";
    for (int n = 1000; n <= 1024000; n *= 4) {
        std::vector<int> keys(n);
        std::iota(keys.begin(), keys.end(), 0);
        std::vector<Row> rows;
        for (unsigned seed : {12u, 13u, 14u}) {
            std::mt19937 random(seed);
            std::shuffle(keys.begin(), keys.end(), random);
            rows.push_back(measure(keys));
        }
        std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << std::log2(n)
                  << std::setw(7) << 2 * std::log2(n + 1.0) - 1 << std::setw(5) << rows[0].avl_height << std::setw(4) << rows[1].avl_height
                  << std::setw(4) << rows[2].avl_height << std::setw(5) << rows[0].rb_height << std::setw(4) << rows[1].rb_height
                  << std::setw(4) << rows[2].rb_height << std::setprecision(2)
                  << std::setw(10) << (rows[0].avl_depth + rows[1].avl_depth + rows[2].avl_depth) / 3
                  << std::setw(9) << (rows[0].rb_depth + rows[1].rb_depth + rows[2].rb_depth) / 3 << "\n";
    }
    return 0;
}