// Rotaciones y recoloreos por inserción, en AVL y en rojinegro. Son conteos, con semilla fija.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

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

namespace {

void print_row(const std::string& name, const std::vector<int>& keys) {
    AvlSet<int> avl;
    RedBlackSet<int> rb;
    long max_rotations = 0;
    long max_recolors = 0;
    for (int key : keys) {
        avl.insert(key);
        long rotations = rb.rotations();
        long recolors = rb.recolors();
        rb.insert(key);
        max_rotations = std::max(max_rotations, rb.rotations() - rotations);
        max_recolors = std::max(max_recolors, rb.recolors() - recolors);
    }
    double n = static_cast<double>(keys.size());
    std::cout << std::setw(11) << name << std::setw(9) << keys.size() << std::fixed << std::setprecision(3)
              << std::setw(9) << avl.rotations() / n << std::setw(9) << rb.rotations() / n << std::setw(9) << rb.recolors() / n
              << std::setw(9) << max_rotations << std::setw(9) << max_recolors << "\n";
}

}  // namespace

int main() {
    std::cout << std::setw(11) << "claves" << std::setw(9) << "n" << std::setw(9) << "rot.avl" << std::setw(9) << "rot.rn"
              << std::setw(9) << "recol.rn" << std::setw(9) << "max.rot" << std::setw(9) << "max.rec" << "\n";
    for (int n : {1000, 32000, 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;
}