// Una Swiss Table de juguete para la clase, escrita para contar y no para ser rápida. Sigue el
// diseño de los mapas de Go 1.24: grupos de 8 casillas, una palabra de control de 64 bits por
// grupo, y los 7 bits bajos del hash en el byte de cada casilla llena.
#ifndef MINI_SWISS_H
#define MINI_SWISS_H

#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>

#include "demo_tables.h"

constexpr std::uint64_t kLowBits = 0x0101010101010101ULL;
constexpr std::uint64_t kHighBits = 0x8080808080808080ULL;
constexpr unsigned char kCtrlEmpty = 0x80;    // 1000 0000
constexpr unsigned char kCtrlDeleted = 0xFE;  // 1111 1110

// Marca con el bit alto los bytes de la palabra que valen h2, sin revisar uno por uno.
// Puede dar falsos positivos raros, justo después de una coincidencia real, y nunca se pierde
// una: por eso siempre se compara la clave completa después.
inline std::uint64_t match_h2(std::uint64_t ctrl, unsigned char h2) {
    const std::uint64_t v = ctrl ^ (kLowBits * h2);
    return (v - kLowBits) & ~v & kHighBits;
}

// Marca los bytes vacíos: tienen el bit alto en 1 y el bit 1 en 0.
inline std::uint64_t match_empty(std::uint64_t ctrl) {
    return ctrl & ~(ctrl << 6) & kHighBits;
}

// Número de casilla (0 a 7) del primer byte marcado.
inline int first_marked(std::uint64_t marks) {
    return __builtin_ctzll(marks) / 8;
}

class MiniSwiss {
public:
    static constexpr std::size_t kGroupSlots = 8;

    // El total de casillas es group_count * 8, con group_count potencia de 2.
    explicit MiniSwiss(std::size_t group_count)
        : ctrl_(group_count, kLowBits * kCtrlEmpty), keys_(group_count * kGroupSlots), mask_(group_count - 1) {}

    void insert(const std::string& key) {
        const std::uint64_t hash = demo_hash(key);
        const unsigned char h2 = hash & 0x7F;
        std::uint64_t group = (hash >> 7) & mask_;
        std::uint64_t step = 0;
        while (match_empty(ctrl_[group]) == 0) {
            step++;
            group = (group + step) & mask_;  // quadratic probing entre grupos
        }
        const int slot = first_marked(match_empty(ctrl_[group]));
        set_byte(group, slot, h2);
        keys_[group * kGroupSlots + static_cast<std::size_t>(slot)] = key;
    }

    bool contains(const std::string& key) {
        const std::uint64_t hash = demo_hash(key);
        const unsigned char h2 = hash & 0x7F;
        std::uint64_t group = (hash >> 7) & mask_;
        std::uint64_t step = 0;
        while (true) {
            groups_read_++;
            std::uint64_t marks = match_h2(ctrl_[group], h2);
            while (marks != 0) {
                const int slot = first_marked(marks);
                comparisons_++;
                if (keys_[group * kGroupSlots + static_cast<std::size_t>(slot)] == key) {
                    return true;
                }
                marks &= marks - 1;
            }
            if (match_empty(ctrl_[group]) != 0) {
                return false;  // un grupo con una vacía termina la búsqueda
            }
            step++;
            group = (group + step) & mask_;
        }
    }

    std::uint64_t comparisons() const { return comparisons_; }
    std::uint64_t groups_read() const { return groups_read_; }
    void reset() {
        comparisons_ = 0;
        groups_read_ = 0;
    }

private:
    void set_byte(std::uint64_t group, int slot, unsigned char value) {
        const int shift = slot * 8;
        ctrl_[group] = (ctrl_[group] & ~(std::uint64_t{0xFF} << shift)) | (std::uint64_t{value} << shift);
    }

    std::vector<std::uint64_t> ctrl_;
    std::vector<std::string> keys_;
    std::uint64_t mask_;
    std::uint64_t comparisons_ = 0;
    std::uint64_t groups_read_ = 0;
};

#endif