// Arreglo ordenado con búsqueda binaria contra std::unordered_map, sobre el mismo diccionario.
// Uso: lookup_bench archivo_de_palabras_ordenado
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <new>
#include <random>
#include <string>
#include <unordered_map>
#include <vector>

#include "bench.h"
#include "word_file.h"

namespace {
std::size_t live_bytes = 0;
// Cada bloque guarda su tamaño al inicio, para restarlo al liberarlo.
const std::size_t HEADER = 16;
}

// Cuenta los bytes reservados y todavía sin liberar, para comparar lo que ocupa cada estructura.
void* operator new(std::size_t size) {
    void* block = std::malloc(size + HEADER);
    if (block == nullptr) {
        throw std::bad_alloc();
    }
    *static_cast<std::size_t*>(block) = size;
    live_bytes += size;
    return static_cast<char*>(block) + HEADER;
}

void operator delete(void* pointer) noexcept {
    if (pointer != nullptr) {
        void* block = static_cast<char*>(pointer) - HEADER;
        live_bytes -= *static_cast<std::size_t*>(block);
        std::free(block);
    }
}

void operator delete(void* pointer, std::size_t) noexcept {
    operator delete(pointer);
}

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: lookup_bench archivo_de_palabras_ordenado\n";
        return 1;
    }
    std::size_t before = live_bytes;
    const std::vector<std::string> words = read_words(argv[1]);
    std::size_t vector_bytes = live_bytes - before;
    if (!std::is_sorted(words.begin(), words.end())) {
        std::cerr << "el archivo debe estar ordenado por bytes\n";
        return 1;
    }

    before = live_bytes;
    std::unordered_map<std::string, int> table;
    double build_seconds = median_seconds(1, [&] {
        for (std::size_t i = 0; i < words.size(); i++) {
            table[words[i]] = static_cast<int>(i);
        }
    });
    std::size_t table_bytes = live_bytes - before;

    // Mismas consultas para las dos, en un orden que no favorece a ninguna.
    std::mt19937 rng(5);
    std::uniform_int_distribution<std::size_t> pick(0, words.size() - 1);
    std::vector<std::string> queries;
    for (int i = 0; i < 200000; i++) {
        queries.push_back(words[pick(rng)]);
    }

    double sorted_seconds = median_seconds(5, [&] {
        std::size_t hits = 0;
        for (const std::string& query : queries) {
            auto it = std::lower_bound(words.begin(), words.end(), query);
            hits += (it != words.end() && *it == query) ? 1 : 0;
        }
        keep(hits);
    });
    double table_seconds = median_seconds(5, [&] {
        std::size_t hits = 0;
        for (const std::string& query : queries) {
            hits += table.contains(query) ? 1 : 0;
        }
        keep(hits);
    });

    std::size_t comparisons = 0;
    for (const std::string& query : queries) {
        auto it = std::lower_bound(words.begin(), words.end(), query, [&](const std::string& a, const std::string& b) {
            comparisons++;
            return a < b;
        });
        keep(it == words.end());
    }
    double chain_cost = 0;
    for (std::size_t b = 0; b < table.bucket_count(); b++) {
        double length = static_cast<double>(table.bucket_size(b));
        chain_cost += length * (length + 1) / 2;
    }

    double count = static_cast<double>(queries.size());
    std::printf("%zu palabras, %zu consultas\n", words.size(), queries.size());
    std::printf("%-22s %12s %16s %10s\n", "", "ns/consulta", "comparaciones", "MB");
    std::printf("%-22s %12.0f %16.1f %10.1f\n", "arreglo ordenado", sorted_seconds * 1e9 / count,
                static_cast<double>(comparisons) / count, static_cast<double>(vector_bytes) / 1e6);
    std::printf("%-22s %12.0f %16.1f %10.1f\n", "std::unordered_map", table_seconds * 1e9 / count,
                chain_cost / static_cast<double>(words.size()), static_cast<double>(table_bytes) / 1e6);
    std::printf("construir la tabla: %.0f ms\n", build_seconds * 1000);

    // Lo que la tabla no sabe hacer: un rango de claves.
    auto first = std::lower_bound(words.begin(), words.end(), std::string("cas"));
    auto last = std::lower_bound(words.begin(), words.end(), std::string("cat"));
    std::printf("empiezan con cas: %td, de %s a %s\n", last - first, first->c_str(), (last - 1)->c_str());
    std::size_t scanned = 0;
    for (const auto& entry : table) {
        scanned += entry.first.starts_with("cas") ? 1 : 0;
    }
    std::printf("la tabla debe revisar %zu claves para hallar las mismas %zu\n", table.size(), scanned);

    // El orden es por bytes: las palabras con tilde inicial quedan después de la z.
    auto a_accent = std::lower_bound(words.begin(), words.end(), std::string("á"));
    auto b_start = std::lower_bound(words.begin(), words.end(), std::string("b"));
    std::printf("antes de la primera b: %s; ultima antes de la primera con a acentuada: %s; primera: %s\n",
                (b_start - 1)->c_str(), (a_accent - 1)->c_str(), a_accent->c_str());
}