#ifndef MAP
#define MAP

#include "hash.h"
#include "vec.h"
#include <stddef.h>
#include <stdint.h>

#define DEFINE_MAP(TYPENAME, FN_PREFIX, KEY_TYPE, VALUE_TYPE, HASH_FN)         \
                                                                               \
    typedef struct {                                                           \
        uint64_t keyhash;                                                      \
        VALUE_TYPE value;                                                      \
    } _internal_TYPENAME##Entry;                                               \
                                                                               \
    DEFINE_VEC(_internal_TYPENAME##EntryVec,                                   \
        _internal_##FN_PREFIX##_entryvec,                                      \
        _internal_TYPENAME##Entry)                                             \
                                                                               \
    typedef struct {                                                           \
        _internal_TYPENAME##EntryVec entries;                                  \
    } TYPENAME;                                                                \
                                                                               \
    [[maybe_unused]] static void FN_PREFIX##_construct(TYPENAME* map)          \
    {                                                                          \
        *map = (TYPENAME) {};                                                  \
    }                                                                          \
                                                                               \
    [[maybe_unused]] static void FN_PREFIX##_destroy(TYPENAME* map)            \
    {                                                                          \
        _internal_##FN_PREFIX##_entryvec_destroy(&map->entries);               \
    }                                                                          \
                                                                               \
    [[maybe_unused]] static bool _internal_##FN_PREFIX##_find_entry_idx(       \
        TYPENAME* map,                                                         \
        size_t* target_idx,                                                    \
        uint64_t keyhash,                                                      \
        size_t begin,                                                          \
        size_t end)                                                            \
    {                                                                          \
        if (begin == end) {                                                    \
            *target_idx = begin;                                               \
            return false;                                                      \
        }                                                                      \
        size_t middle_idx = (end - begin) / 2 + begin;                         \
        _internal_TYPENAME##Entry* middle_entry                                \
            = &map->entries.data[middle_idx];                                  \
        if (keyhash < middle_entry->keyhash) {                                 \
            return _internal_##FN_PREFIX##_find_entry_idx(                     \
                map, target_idx, keyhash, begin, middle_idx);                  \
        } else if (keyhash > middle_entry->keyhash) {                          \
            return _internal_##FN_PREFIX##_find_entry_idx(                     \
                map, target_idx, keyhash, middle_idx + 1, end);                \
        } else {                                                               \
            *target_idx = middle_idx;                                          \
            return true;                                                       \
        }                                                                      \
    }                                                                          \
                                                                               \
    [[maybe_unused]] static void FN_PREFIX##_set(                              \
        TYPENAME* map, KEY_TYPE key, VALUE_TYPE value)                         \
    {                                                                          \
        Hasher hasher = {};                                                    \
        HASH_FN(&hasher, key);                                                 \
        uint64_t keyhash = hasher_finish(hasher);                              \
                                                                               \
        size_t target_idx;                                                     \
        bool exists = _internal_##FN_PREFIX##_find_entry_idx(                  \
            map, &target_idx, keyhash, 0, map->entries.size);                  \
                                                                               \
        if (exists) {                                                          \
            map->entries.data[target_idx].value = value;                       \
            return;                                                            \
        }                                                                      \
                                                                               \
        _internal_##FN_PREFIX##_entryvec_push(                                 \
            &map->entries, (_internal_TYPENAME##Entry) {});                    \
        for (size_t i = map->entries.size - 1; i > target_idx; --i) {          \
            map->entries.data[i] = map->entries.data[i - 1];                   \
        }                                                                      \
        map->entries.data[target_idx]                                          \
            = (_internal_TYPENAME##Entry) { keyhash, value };                  \
    }                                                                          \
                                                                               \
    [[maybe_unused]] static VALUE_TYPE* FN_PREFIX##_at(                        \
        TYPENAME* map, KEY_TYPE key)                                           \
    {                                                                          \
        Hasher hasher = {};                                                    \
        HASH_FN(&hasher, key);                                                 \
        uint64_t keyhash = hasher_finish(hasher);                              \
                                                                               \
        size_t target_idx;                                                     \
        bool exists = _internal_##FN_PREFIX##_find_entry_idx(                  \
            map, &target_idx, keyhash, 0, map->entries.size);                  \
                                                                               \
        if (!exists) {                                                         \
            return nullptr;                                                    \
        }                                                                      \
                                                                               \
        return &map->entries.data[target_idx].value;                           \
    }

#define DEFINE_STRINGMAP(TYPENAME, FN_PREFIX, VALUE_TYPE)                      \
    DEFINE_MAP(TYPENAME, FN_PREFIX, const char*, VALUE_TYPE, string_hash)

#endif