#include "../../include/mgl/graphics/font_char_map.h"
#include <stdlib.h>

/* Optimized div by sizeof(mgl_font_char_entry*) */
#if INTPTR_MAX == INT64_MAX
#define CAP_NUM_ENTRIES(cap) ((cap) >> 3)
#elif INTPTR_MAX == INT32_MAX
#define CAP_NUM_ENTRIES(cap) ((cap) >> 2)
#else
#error Unsupported system. Only systems where a pointer is 32-bits or 64-bits are supported.
#endif

#define HASH_TO_INDEX(hash) (hash & (CAP_NUM_ENTRIES(self->capacity)-1))

/* |align| should be a multiple of 2 */
static size_t align_to(size_t value, size_t align) {
    const size_t is_aligned = (value & (align - 1));
    if(is_aligned == 0) {
        return value;
    } else {
        return (value & ~(align - 1)) + align;
    }
}

static void mgl_font_char_entry_deinit(mgl_font_char_entry *self) {
    mgl_font_char_entry *next = self->next;
    while(next) {
        mgl_font_char_entry *next_next = next->next;
        free(next);
        next = next_next;
    }
}

static void mgl_font_char_map_insert_entry(mgl_font_char_map *self, size_t index, uint32_t key, const mgl_font_glyph *value, mgl_font_char_entry *entry) {
    entry->key = key;
    entry->value = *value;
    entry->next = self->entries[index];
    self->entries[index] = entry;
}

static void mgl_font_char_map_reorder_nodes(mgl_font_char_map *self, size_t prev_capacity) {
    for(size_t i = 0; i < CAP_NUM_ENTRIES(prev_capacity); ++i) {
        mgl_font_char_entry *entry = self->entries[i];
        if(!entry)
            continue;

        mgl_font_char_entry *prev_entry = NULL;
        while(entry) {
            const uint32_t hash = entry->key;
            const size_t index = HASH_TO_INDEX(hash);
            mgl_font_char_entry *next_entry = entry->next;

            if(index != i) {
                /* Remove entry by replacing this entry with the next entry */
                if(prev_entry)
                    prev_entry->next = next_entry;
                else
                    self->entries[i] = next_entry;

                /* Insert the entry at the new index */
                mgl_font_char_map_insert_entry(self, index, entry->key, &entry->value, entry);
            } else {
                prev_entry = entry;
            }

            entry = next_entry;
        }
    }
}

static int mgl_font_char_map_ensure_capacity(mgl_font_char_map *self, size_t target_capacity) {
    if(self->capacity >= target_capacity)
        return 0;

    size_t capacity = self->capacity;
    if(capacity == 0)
        capacity = 8;

    while(capacity < target_capacity) {
        capacity = capacity + (capacity >> 1); /* *= 1.5 */
    }

    capacity = align_to(capacity, sizeof(mgl_font_char_entry*));
    void *new_data = realloc(self->entries, capacity);
    if(!new_data)
        return -1;

    const size_t prev_capacity = self->capacity;
    self->entries = new_data;
    self->capacity = capacity;

    for(size_t i = CAP_NUM_ENTRIES(prev_capacity); i < CAP_NUM_ENTRIES(self->capacity); ++i) {
        self->entries[i] = NULL;
    }

    mgl_font_char_map_reorder_nodes(self, prev_capacity);
    return 0;
}

void mgl_font_char_map_init(mgl_font_char_map *self) {
    self->entries = NULL;
    self->size = 0;
    self->capacity = 0;
}

void mgl_font_char_map_deinit(mgl_font_char_map *self) {
    if(self->entries) {
        for(size_t i = 0; i < CAP_NUM_ENTRIES(self->capacity); ++i) {
            if(self->entries[i]) {
                mgl_font_char_entry_deinit(self->entries[i]);
                free(self->entries[i]);
            }
        }
        free(self->entries);
        self->entries = NULL;
    }
    self->size = 0;
    self->capacity = 0;
}

int mgl_font_char_map_insert(mgl_font_char_map *self, uint32_t key, const mgl_font_glyph *value, mgl_font_char_entry **inserted_entry) {
    if(mgl_font_char_map_ensure_capacity(self, (self->size + 1) * sizeof(mgl_font_char_entry*)) != 0)
        return -1;

    ++self->size;
    const uint32_t hash = key;
    const size_t index = HASH_TO_INDEX(hash);

    mgl_font_char_entry *entry = malloc(sizeof(mgl_font_char_entry));
    if(!entry)
        return -1;
    
    mgl_font_char_map_insert_entry(self, index, key, value, entry);
    entry->render_offset = (mgl_vec2i){ 0, 0 };
    entry->rendered = false;
    if(inserted_entry)
        *inserted_entry = entry;

    return 0;
}

mgl_font_char_entry* mgl_font_char_map_get(const mgl_font_char_map *self, uint32_t key) {
    if(self->capacity == 0)
        return NULL;

    const uint32_t hash = key;
    const size_t index = HASH_TO_INDEX(hash);

    mgl_font_char_entry *entry = self->entries[index];
    while(entry) {
        if(entry->key == key)
            return entry;
        entry = entry->next;
    }

    return NULL;
}

void mgl_font_char_map_clear_rendered(mgl_font_char_map *self) {
    if(!self->entries)
        return;

    for(size_t i = 0; i < CAP_NUM_ENTRIES(self->capacity); ++i) {
        mgl_font_char_entry *entry = self->entries[i];
        if(!entry)
            continue;
        
        while(entry) {
            entry->rendered = false;
            entry = entry->next;
        }
    }
}

mgl_font_char_iterator mgl_font_char_map_begin(mgl_font_char_map *self) {
    mgl_font_char_iterator it;
    it.char_map = self;
    it.index = 0;
    it.value = NULL;

    if(!self->entries)
        return it;

    for(size_t i = 0; i < CAP_NUM_ENTRIES(self->capacity); ++i) {
        mgl_font_char_entry *entry = self->entries[i];
        if(entry) {
            it.index = i;
            it.value = entry;
            break;
        }
    }

    return it;
}

void mgl_font_char_iterator_next(mgl_font_char_iterator *self) {
    if(!self->value)
        return;

    if(self->value->next) {
        self->value = self->value->next;
        return;
    }

    for(size_t i = self->index + 1; i < CAP_NUM_ENTRIES(self->char_map->capacity); ++i) {
        mgl_font_char_entry *entry = self->char_map->entries[i];
        if(entry) {
            self->index = i;
            self->value = entry;
            return;
        }
    }

    self->value = NULL;
}