spatial

-module(spatial@grid).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/spatial/grid.gleam").
-export([new/2, query_all/1, count/1, bounds/1, cell_size/1, cell_count/1, insert/3, remove/3, query_radius/3, 'query'/2]).
-export_type([grid/1]).

-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.

?MODULEDOC(
    " Hash Grid spatial partitioning data structure.\n"
    "\n"
    " Uses Erlang maps (HAMT with branching factor 32) providing O(log₃₂ n) operations,\n"
    " which is effectively O(1) in practice. At 1 million cells, operations take only\n"
    " ~5 steps. Excellent for uniformly distributed objects like particles or crowds.\n"
).

-opaque grid(KRP) :: {grid,
        float(),
        spatial@collider:internal_collider(),
        gleam@dict:dict({integer(), integer(), integer()}, list({vec@vec3:vec3(float()),
            KRP}))}.

-file("src/spatial/grid.gleam", 42).
?DOC(
    " Create a new empty hash grid.\n"
    "\n"
    " ## Parameters\n"
    " - `cell_size`: Size of each grid cell (should match typical object size)\n"
    " - `bounds`: The spatial region this grid covers\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " let bounds = collider.box(\n"
    "   min: vec3.Vec3(-100.0, -100.0, -100.0),\n"
    "   max: vec3.Vec3(100.0, 100.0, 100.0),\n"
    " )\n"
    " let grid = grid.new(cell_size: 10.0, bounds: bounds)\n"
    " ```\n"
).
-spec new(float(), spatial@collider:internal_collider()) -> grid(any()).
new(Cell_size, Bounds) ->
    {grid, Cell_size, Bounds, maps:new()}.

-file("src/spatial/grid.gleam", 156).
?DOC(
    " Query all items in the grid (useful for iteration).\n"
    "\n"
    " **Time Complexity**: O(n) where n is the total number of items.\n"
).
-spec query_all(grid(KSJ)) -> list({vec@vec3:vec3(float()), KSJ}).
query_all(Grid) ->
    _pipe = maps:values(erlang:element(4, Grid)),
    lists:append(_pipe).

-file("src/spatial/grid.gleam", 164).
?DOC(
    " Count total items in the grid.\n"
    "\n"
    " **Time Complexity**: O(m) where m is the number of occupied cells.\n"
).
-spec count(grid(any())) -> integer().
count(Grid) ->
    gleam@dict:fold(
        erlang:element(4, Grid),
        0,
        fun(Acc, _, Items) -> Acc + erlang:length(Items) end
    ).

-file("src/spatial/grid.gleam", 169).
?DOC(" Get the bounds of the grid.\n").
-spec bounds(grid(any())) -> spatial@collider:internal_collider().
bounds(Grid) ->
    erlang:element(3, Grid).

-file("src/spatial/grid.gleam", 174).
?DOC(" Get the cell size of the grid.\n").
-spec cell_size(grid(any())) -> float().
cell_size(Grid) ->
    erlang:element(2, Grid).

-file("src/spatial/grid.gleam", 179).
?DOC(" Get the number of non-empty cells.\n").
-spec cell_count(grid(any())) -> integer().
cell_count(Grid) ->
    maps:size(erlang:element(4, Grid)).

-file("src/spatial/grid.gleam", 185).
-spec position_to_cell(vec@vec3:vec3(float()), float()) -> {integer(),
    integer(),
    integer()}.
position_to_cell(Position, Cell_size) ->
    X = begin
        _pipe = math:floor(case Cell_size of
                +0.0 -> +0.0;
                -0.0 -> -0.0;
                Gleam@denominator -> erlang:element(2, Position) / Gleam@denominator
            end),
        erlang:round(_pipe)
    end,
    Y = begin
        _pipe@1 = math:floor(case Cell_size of
                +0.0 -> +0.0;
                -0.0 -> -0.0;
                Gleam@denominator@1 -> erlang:element(3, Position) / Gleam@denominator@1
            end),
        erlang:round(_pipe@1)
    end,
    Z = begin
        _pipe@2 = math:floor(case Cell_size of
                +0.0 -> +0.0;
                -0.0 -> -0.0;
                Gleam@denominator@2 -> erlang:element(4, Position) / Gleam@denominator@2
            end),
        erlang:round(_pipe@2)
    end,
    {X, Y, Z}.

-file("src/spatial/grid.gleam", 50).
?DOC(
    " Insert an item at a position into the grid.\n"
    "\n"
    " **Time Complexity**: O(log₃₂ n) where n is the number of occupied cells,\n"
    " effectively O(1) in practice. Faster than octree for uniform distributions.\n"
).
-spec insert(grid(KRS), vec@vec3:vec3(float()), KRS) -> grid(KRS).
insert(Grid, Position, Item) ->
    case spatial@collider:contains_point(erlang:element(3, Grid), Position) of
        false ->
            Grid;

        true ->
            Cell_key = position_to_cell(Position, erlang:element(2, Grid)),
            Current_items = begin
                _pipe = gleam_stdlib:map_get(erlang:element(4, Grid), Cell_key),
                gleam@result:unwrap(_pipe, [])
            end,
            Updated_items = [{Position, Item} | Current_items],
            Updated_cells = gleam@dict:insert(
                erlang:element(4, Grid),
                Cell_key,
                Updated_items
            ),
            {grid,
                erlang:element(2, Grid),
                erlang:element(3, Grid),
                Updated_cells}
    end.

-file("src/spatial/grid.gleam", 67).
?DOC(
    " Remove an item from the grid.\n"
    "\n"
    " **Time Complexity**: O(log₃₂ n) cell lookup + O(k) filtering where n is the\n"
    " number of occupied cells and k is items in that cell. Effectively O(k) in practice.\n"
).
-spec remove(grid(KRW), vec@vec3:vec3(float()), fun((KRW) -> boolean())) -> grid(KRW).
remove(Grid, Position, Predicate) ->
    case spatial@collider:contains_point(erlang:element(3, Grid), Position) of
        false ->
            Grid;

        true ->
            Cell_key = position_to_cell(Position, erlang:element(2, Grid)),
            case gleam_stdlib:map_get(erlang:element(4, Grid), Cell_key) of
                {error, _} ->
                    Grid;

                {ok, Items} ->
                    Filtered_items = gleam@list:filter(
                        Items,
                        fun(Item_pair) ->
                            {Pos, Item} = Item_pair,
                            Is_at_position = vec@vec3f:distance(Pos, Position) < 0.0001,
                            Matches_predicate = Predicate(Item),
                            not (Is_at_position andalso Matches_predicate)
                        end
                    ),
                    Updated_cells = case Filtered_items of
                        [] ->
                            gleam@dict:delete(erlang:element(4, Grid), Cell_key);

                        _ ->
                            gleam@dict:insert(
                                erlang:element(4, Grid),
                                Cell_key,
                                Filtered_items
                            )
                    end,
                    {grid,
                        erlang:element(2, Grid),
                        erlang:element(3, Grid),
                        Updated_cells}
            end
    end.

-file("src/spatial/grid.gleam", 192).
-spec get_cells_in_radius(vec@vec3:vec3(float()), float(), float()) -> list({integer(),
    integer(),
    integer()}).
get_cells_in_radius(Center, Radius, Cell_size) ->
    Center_cell = position_to_cell(Center, Cell_size),
    Cell_radius = begin
        _pipe = math:ceil(case Cell_size of
                +0.0 -> +0.0;
                -0.0 -> -0.0;
                Gleam@denominator -> Radius / Gleam@denominator
            end),
        erlang:round(_pipe)
    end,
    Range_x = gleam@list:range(
        erlang:element(1, Center_cell) - Cell_radius,
        erlang:element(1, Center_cell) + Cell_radius
    ),
    Range_y = gleam@list:range(
        erlang:element(2, Center_cell) - Cell_radius,
        erlang:element(2, Center_cell) + Cell_radius
    ),
    Range_z = gleam@list:range(
        erlang:element(3, Center_cell) - Cell_radius,
        erlang:element(3, Center_cell) + Cell_radius
    ),
    gleam@list:flat_map(
        Range_x,
        fun(X) ->
            gleam@list:flat_map(
                Range_y,
                fun(Y) -> gleam@list:map(Range_z, fun(Z) -> {X, Y, Z} end) end
            )
        end
    ).

-file("src/spatial/grid.gleam", 128).
?DOC(
    " Query all items within a radius of a point.\n"
    "\n"
    " Extremely fast for uniform distributions - only checks nearby cells.\n"
    "\n"
    " **Time Complexity**: O(c·log₃₂ m + k) where c is cells checked, m is occupied\n"
    " cells, and k is results. Effectively O(c + k) in practice.\n"
).
-spec query_radius(grid(KSE), vec@vec3:vec3(float()), float()) -> list({vec@vec3:vec3(float()),
    KSE}).
query_radius(Grid, Center, Radius) ->
    Cells_to_check = get_cells_in_radius(
        Center,
        Radius,
        erlang:element(2, Grid)
    ),
    Radius_sq = Radius * Radius,
    gleam@list:fold(
        Cells_to_check,
        [],
        fun(Acc, Cell_key) ->
            case gleam_stdlib:map_get(erlang:element(4, Grid), Cell_key) of
                {error, _} ->
                    Acc;

                {ok, Items} ->
                    gleam@list:fold(
                        Items,
                        Acc,
                        fun(Acc_inner, Item_pair) ->
                            {Pos, _} = Item_pair,
                            case spatial_ffi:distance_squared(Center, Pos) =< Radius_sq of
                                true ->
                                    [Item_pair | Acc_inner];

                                false ->
                                    Acc_inner
                            end
                        end
                    )
            end
        end
    ).

-file("src/spatial/grid.gleam", 212).
-spec get_cells_in_bounds(spatial@collider:internal_collider(), float()) -> list({integer(),
    integer(),
    integer()}).
get_cells_in_bounds(Bounds, Cell_size) ->
    Center = spatial@collider:center(Bounds),
    Size = spatial@collider:size(Bounds),
    Radius = gleam@float:max(
        erlang:element(2, Size),
        gleam@float:max(erlang:element(3, Size), erlang:element(4, Size))
    )
    / 2.0,
    get_cells_in_radius(Center, Radius, Cell_size).

-file("src/spatial/grid.gleam", 104).
?DOC(
    " Query all items within a collider region.\n"
    "\n"
    " More efficient than octree for uniform distributions.\n"
    "\n"
    " **Time Complexity**: O(c·log₃₂ m + k) where c is cells checked, m is occupied\n"
    " cells, and k is results. Effectively O(c + k) in practice.\n"
).
-spec 'query'(grid(KSA), spatial@collider:internal_collider()) -> list({vec@vec3:vec3(float()),
    KSA}).
'query'(Grid, Query_bounds) ->
    Cells_to_check = get_cells_in_bounds(Query_bounds, erlang:element(2, Grid)),
    gleam@list:fold(
        Cells_to_check,
        [],
        fun(Acc, Cell_key) ->
            case gleam_stdlib:map_get(erlang:element(4, Grid), Cell_key) of
                {error, _} ->
                    Acc;

                {ok, Items} ->
                    gleam@list:fold(
                        Items,
                        Acc,
                        fun(Acc_inner, Item_pair) ->
                            {Pos, _} = Item_pair,
                            case spatial@collider:contains_point(
                                Query_bounds,
                                Pos
                            ) of
                                true ->
                                    [Item_pair | Acc_inner];

                                false ->
                                    Acc_inner
                            end
                        end
                    )
            end
        end
    ).