// std::map frente a std::unordered_map con palabras reales. Compilar con -O2 y sin sanitizers.
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <unordered_map>
#include <vector>

#include "bench.h"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: map_vs_unordered palabras.txt\n";
        return 2;
    }
    std::ifstream file(argv[1]);
    if (!file) {
        std::cerr << "no se pudo abrir " << argv[1] << "\n";
        return 2;
    }
    std::vector<std::string> words;
    std::string word;
    while (std::getline(file, word)) {
        words.push_back(word);
    }
    std::mt19937 random(10);
    std::shuffle(words.begin(), words.end(), random);

    std::cout << "  (tiempo por palabra, en ns; mediana de 3)\n";
    std::cout << std::setw(9) << "n" << std::setw(10) << "ins.map" << std::setw(10) << "ins.hash" << std::setw(7) << "x"
              << std::setw(10) << "bus.map" << std::setw(10) << "bus.hash" << std::setw(7) << "x"
              << std::setw(10) << "ord.map" << std::setw(10) << "ord.hash" << std::setw(7) << "x" << "\n";
    for (std::size_t n : {std::size_t{10000}, std::size_t{100000}, words.size()}) {
        std::vector<std::string> keys(words.begin(), words.begin() + n);
        std::vector<std::string> queries = keys;
        std::shuffle(queries.begin(), queries.end(), random);
        double per_key = 1e9 / n;

        double insert_map = per_key * median_seconds(3, [&] {
            std::map<std::string, int> map;
            for (const std::string& key : keys) {
                map[key] = 1;
            }
            keep(map.size());
        });
        double insert_hash = per_key * median_seconds(3, [&] {
            std::unordered_map<std::string, int> map;
            for (const std::string& key : keys) {
                map[key] = 1;
            }
            keep(map.size());
        });

        std::map<std::string, int> ordered;
        std::unordered_map<std::string, int> hashed;
        for (const std::string& key : keys) {
            ordered[key] = 1;
            hashed[key] = 1;
        }
        double find_map = per_key * median_seconds(3, [&] {
            long found = 0;
            for (const std::string& key : queries) {
                found += ordered.count(key);
            }
            keep(found);
        });
        double find_hash = per_key * median_seconds(3, [&] {
            long found = 0;
            for (const std::string& key : queries) {
                found += hashed.count(key);
            }
            keep(found);
        });
        // Sacar todas las claves en orden: el mapa solo las recorre, y la tabla tiene que ordenarlas.
        double sorted_map = per_key * median_seconds(3, [&] {
            std::size_t bytes = 0;
            for (const auto& [key, value] : ordered) {
                bytes += key.size() + value;
            }
            keep(bytes);
        });
        double sorted_hash = per_key * median_seconds(3, [&] {
            std::vector<const std::string*> pointers;
            pointers.reserve(hashed.size());
            for (const auto& [key, value] : hashed) {
                pointers.push_back(&key);
            }
            std::sort(pointers.begin(), pointers.end(),
                      [](const std::string* a, const std::string* b) { return *a < *b; });
            std::size_t bytes = 0;
            for (const std::string* key : pointers) {
                bytes += key->size();
            }
            keep(bytes);
        });

        std::cout << std::setw(9) << n << std::fixed << std::setprecision(0) << std::setw(10) << insert_map
                  << std::setw(10) << insert_hash << std::setprecision(1) << std::setw(7) << insert_map / insert_hash
                  << std::setprecision(0) << std::setw(10) << find_map << std::setw(10) << find_hash
                  << std::setprecision(1) << std::setw(7) << find_map / find_hash
                  << std::setprecision(0) << std::setw(10) << sorted_map << std::setw(10) << sorted_hash
                  << std::setprecision(1) << std::setw(7) << sorted_hash / sorted_map << "\n";
    }
    return 0;
}