#pragma once

#include <cstdint>
#include <cstring>
#include <cmath>
#include <algorithm>

namespace FreeExile {

constexpr int32_t SPATIAL_HASH_SIZE = 65536;

/**
 * High-performance Flat Spatial Hash Grid.
 * Zero-allocation: uses pre-allocated linked-list nodes inside contiguous array.
 */
class FlatSpatialGrid {
public:
    float cell_size;
    int32_t cell_heads[SPATIAL_HASH_SIZE];

    explicit FlatSpatialGrid(float size = 64.0f) : cell_size(size > 0.0f ? size : 64.0f) {
        clear();
    }

    void clear() {
        std::memset(cell_heads, -1, sizeof(cell_heads));
    }

    inline int32_t hash_coords(int32_t cx, int32_t cy) const {
        uint32_t h = (uint32_t)cx * 73856093u ^ (uint32_t)cy * 19349663u;
        return (int32_t)(h & (SPATIAL_HASH_SIZE - 1));
    }

    inline void get_cell_coords(float x, float y, int32_t& cx, int32_t& cy) const {
        if (std::isnan(x) || std::isinf(x)) x = 0.0f;
        if (std::isnan(y) || std::isinf(y)) y = 0.0f;
        cx = static_cast<int32_t>(std::floor(x / cell_size));
        cy = static_cast<int32_t>(std::floor(y / cell_size));
    }

    void insert_entity(int32_t entity_idx, float x, float y, int32_t* next_in_cell) {
        int32_t cx, cy;
        get_cell_coords(x, y, cx, cy);
        int32_t bucket = hash_coords(cx, cy);

        next_in_cell[entity_idx] = cell_heads[bucket];
        cell_heads[bucket] = entity_idx;
    }

    int32_t query_aoi(
        float center_x,
        float center_y,
        int32_t radius_cells,
        const int32_t* next_in_cell,
        const int32_t* entity_ids,
        int32_t* out_results,
        int32_t max_results
    ) const {
        if (!out_results || max_results <= 0 || !next_in_cell || !entity_ids) return 0;
        if (radius_cells < 0) return 0;
        if (radius_cells > 8) radius_cells = 8; // Bounds clamp to protect against DOS freeze

        int32_t cx, cy;
        get_cell_coords(center_x, center_y, cx, cy);
        int32_t count = 0;

        constexpr int32_t MAX_VISITED = 289; // (2*8 + 1)^2
        int32_t visited_buckets[MAX_VISITED];
        int32_t num_visited = 0;

        for (int32_t dx = -radius_cells; dx <= radius_cells && count < max_results; ++dx) {
            for (int32_t dy = -radius_cells; dy <= radius_cells && count < max_results; ++dy) {
                int32_t bucket = hash_coords(cx + dx, cy + dy);

                // Deduplicate visited buckets to prevent hash collisions returning duplicate entity IDs
                bool seen = false;
                for (int32_t v = 0; v < num_visited; ++v) {
                    if (visited_buckets[v] == bucket) {
                        seen = true;
                        break;
                    }
                }
                if (seen) continue;
                visited_buckets[num_visited++] = bucket;

                int32_t curr = cell_heads[bucket];
                while (curr != -1 && count < max_results) {
                    out_results[count++] = entity_ids[curr];
                    curr = next_in_cell[curr];
                }
            }
        }
        return count;
    }
};

} // namespace FreeExile