// Tiempo de insertar y de buscar n enteros, con y sin balance. -O2 y mediana de 3.
// Los tiempos dependen de la máquina: lo que importa es la razón entre columnas.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

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

namespace {

template <typename Tree>
double insert_time(const std::vector<int>& keys) {
    return median_seconds(3, [&] {
        Tree tree;
        for (int key : keys) {
            tree.insert(key);
        }
        keep(tree.size());
    });
}

template <typename Tree>
double search_time(const std::vector<int>& keys, const std::vector<int>& queries) {
    Tree tree;
    for (int key : keys) {
        tree.insert(key);
    }
    return median_seconds(3, [&] {
        long found = 0;
        for (int key : queries) {
            found += tree.contains(key) ? 1 : 0;
        }
        keep(found);
    });
}

}  // namespace

int main() {
    std::cout << "Claves ordenadas: insertar (s)\n";
    std::cout << std::setw(9) << "n" << std::setw(10) << "avl" << std::setw(10) << "sin.bal" << std::setw(9) << "x" << "\n";
    for (int n = 1000; n <= 16000; n *= 2) {
        std::vector<int> keys(n);
        std::iota(keys.begin(), keys.end(), 0);
        double plain = insert_time<PlainTree<int>>(keys);
        double avl = insert_time<AvlSet<int>>(keys);
        std::cout << std::setw(9) << n << std::fixed << std::setprecision(5) << std::setw(10) << avl
                  << std::setw(10) << plain << std::setprecision(1) << std::setw(9) << plain / avl << std::endl;
    }
    std::cout << "Claves al azar: insertar y buscar todas (s)\n";
    std::cout << std::setw(9) << "n" << std::setw(10) << "ins.avl" << std::setw(10) << "ins.sin" << std::setw(9) << "avl/sin"
              << std::setw(10) << "bus.avl" << std::setw(10) << "bus.sin" << std::setw(9) << "sin/avl" << "\n";
    std::mt19937 random(11);
    for (int n : {16000, 128000, 512000}) {
        std::vector<int> keys(n);
        std::iota(keys.begin(), keys.end(), 0);
        std::shuffle(keys.begin(), keys.end(), random);
        std::vector<int> queries = keys;
        std::shuffle(queries.begin(), queries.end(), random);
        double insert_plain = insert_time<PlainTree<int>>(keys);
        double insert_avl = insert_time<AvlSet<int>>(keys);
        double search_plain = search_time<PlainTree<int>>(keys, queries);
        double search_avl = search_time<AvlSet<int>>(keys, queries);
        std::cout << std::setw(9) << n << std::fixed << std::setprecision(5)
                  << std::setw(10) << insert_avl << std::setw(10) << insert_plain << std::setprecision(2) << std::setw(9) << insert_avl / insert_plain
                  << std::setprecision(5) << std::setw(10) << search_avl << std::setw(10) << search_plain << std::setprecision(2) << std::setw(9) << search_plain / search_avl << std::endl;
    }
    return 0;
}