// Paso 4: cuenta rotaciones y recoloreos de su mapa, frente a las rotaciones del AVL.
// Son conteos: no dependen de la máquina. Compilar con -O2 y sin sanitizers.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

#include "avl_map.h"
#include "red_black_map.h"

namespace {

void print_row(const std::string& name, const std::vector<int>& keys) {
    AvlMap<int, int> avl;
    RedBlackMap<int, int> red_black;
    for (int key : keys) {
        avl.insert(key, key);
        red_black.insert(key, key);
    }
    double n = static_cast<double>(keys.size());
    std::cout << std::setw(13) << name << std::setw(9) << keys.size() << std::fixed << std::setprecision(3)
              << std::setw(9) << avl.rotations() / n << std::setw(9) << red_black.rotations() / n
              << std::setw(10) << red_black.recolors() / n << std::setw(7) << avl.height() << std::setw(7) << red_black.height()
              << std::setw(8) << red_black.black_height() << "\n";
}

}  // namespace

int main() {
    std::cout << std::setw(13) << "claves" << std::setw(9) << "n" << std::setw(9) << "rot.avl" << std::setw(9) << "rot.rn"
              << std::setw(10) << "recol.rn" << std::setw(7) << "h.avl" << std::setw(7) << "h.rn" << std::setw(8) << "negros" << "\n";
    for (int n : {1000, 16000, 256000, 1024000}) {
        std::vector<int> keys(n);
        std::iota(keys.begin(), keys.end(), 0);
        print_row("crecientes", keys);
        std::reverse(keys.begin(), keys.end());
        print_row("decrecientes", keys);
        std::mt19937 random(12);
        std::shuffle(keys.begin(), keys.end(), random);
        print_row("azar", keys);
    }
    return 0;
}