yog

-module(yog@builder@grid).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/builder/grid.gleam").
-export([rook/0, bishop/0, queen/0, knight/0, coord_to_id/3, from_2d_list_with_topology/4, from_2d_list/3, id_to_coord/2, get_cell/3, to_graph/1, manhattan_distance/3, find_node/2, avoiding/1, walkable/1, always/0]).
-export_type([grid/2]).

-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(
    " A builder for creating graphs from 2D grids.\n"
    "\n"
    " This module provides convenient ways to convert 2D grids (like heightmaps,\n"
    " mazes, or game boards) into graphs for pathfinding and traversal algorithms.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " import yog/builder/grid\n"
    " import yog/model.{Directed}\n"
    " import yog/traversal.{BreadthFirst}\n"
    "\n"
    " pub fn main() {\n"
    "   // A simple heightmap where you can only climb up by 1\n"
    "   let heightmap = [\n"
    "     [1, 2, 3],\n"
    "     [4, 5, 6],\n"
    "     [7, 8, 9]\n"
    "   ]\n"
    "\n"
    "   // Build a graph where edges exist only if height diff <= 1\n"
    "   let grid = grid.from_2d_list(\n"
    "     heightmap,\n"
    "     Directed,\n"
    "     can_move: fn(from_height, to_height) {\n"
    "       to_height - from_height <= 1\n"
    "     }\n"
    "   )\n"
    "\n"
    "   // Convert to graph and use with algorithms\n"
    "   let graph = grid.to_graph(grid)\n"
    "   let start = grid.coord_to_id(0, 0, grid.cols)\n"
    "   let goal = grid.coord_to_id(2, 2, grid.cols)\n"
    "\n"
    "   traversal.walk_until(\n"
    "     from: start,\n"
    "     in: graph,\n"
    "     using: BreadthFirst,\n"
    "     until: fn(node) { node == goal }\n"
    "   )\n"
    " }\n"
    " ```\n"
).

-type grid(KLW, KLX) :: {grid, yog@model:graph(KLW, KLX), integer(), integer()}.

-file("src/yog/builder/grid.gleam", 205).
?DOC(
    " Cardinal (4-way) movement: up, down, left, right.\n"
    "\n"
    " Named after the rook in chess, which moves along ranks and files.\n"
    " This is the default topology used by `from_2d_list`.\n"
    "\n"
    " ```\n"
    " . ↑ .\n"
    " ← · →\n"
    " . ↓ .\n"
    " ```\n"
).
-spec rook() -> list({integer(), integer()}).
rook() ->
    [{-1, 0}, {1, 0}, {0, -1}, {0, 1}].

-file("src/yog/builder/grid.gleam", 218).
?DOC(
    " Diagonal (4-way) movement: the four diagonal directions.\n"
    "\n"
    " Named after the bishop in chess, which moves along diagonals.\n"
    "\n"
    " ```\n"
    " ↖ . ↗\n"
    " . · .\n"
    " ↙ . ↘\n"
    " ```\n"
).
-spec bishop() -> list({integer(), integer()}).
bishop() ->
    [{-1, -1}, {-1, 1}, {1, -1}, {1, 1}].

-file("src/yog/builder/grid.gleam", 231).
?DOC(
    " All 8 surrounding directions: cardinal + diagonal.\n"
    "\n"
    " Named after the queen in chess, which combines rook and bishop movement.\n"
    "\n"
    " ```\n"
    " ↖ ↑ ↗\n"
    " ← · →\n"
    " ↙ ↓ ↘\n"
    " ```\n"
).
-spec queen() -> list({integer(), integer()}).
queen() ->
    [{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}].

-file("src/yog/builder/grid.gleam", 247).
?DOC(
    " L-shaped jumps in all 8 orientations.\n"
    "\n"
    " Named after the knight in chess, which jumps in an L-shape\n"
    " (2 squares in one direction, 1 square perpendicular).\n"
    "\n"
    " ```\n"
    " . ♞ . ♞ .\n"
    " ♞ . . . ♞\n"
    " . . · . .\n"
    " ♞ . . . ♞\n"
    " . ♞ . ♞ .\n"
    " ```\n"
).
-spec knight() -> list({integer(), integer()}).
knight() ->
    [{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}].

-file("src/yog/builder/grid.gleam", 271).
?DOC(
    " Converts grid coordinates (row, col) to a node ID.\n"
    "\n"
    " Uses row-major ordering: id = row * cols + col\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " grid.coord_to_id(0, 0, 3)  // => 0\n"
    " grid.coord_to_id(1, 2, 3)  // => 5\n"
    " grid.coord_to_id(2, 1, 3)  // => 7\n"
    " ```\n"
).
-spec coord_to_id(integer(), integer(), integer()) -> integer().
coord_to_id(Row, Col, Cols) ->
    (Row * Cols) + Col.

-file("src/yog/builder/grid.gleam", 130).
?DOC(
    " Creates a graph from a 2D list using a custom movement topology.\n"
    "\n"
    " The `topology` parameter is a list of `#(row_delta, col_delta)` offsets\n"
    " that define which neighbors each cell can reach. Use the built-in\n"
    " presets — `rook()`, `bishop()`, `queen()`, `knight()` — or define\n"
    " your own.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // 8-way movement (queen topology) on a maze\n"
    " let maze = [[\".\", \"#\", \".\"], [\".\", \".\", \".\"], [\"#\", \".\", \".\"]]\n"
    "\n"
    " let g = grid.from_2d_list_with_topology(\n"
    "   maze,\n"
    "   model.Directed,\n"
    "   grid.queen(),\n"
    "   can_move: grid.avoiding(\"#\"),\n"
    " )\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " // Knight jumps on a chessboard\n"
    " let board = [\n"
    "   [0, 0, 0, 0, 0],\n"
    "   [0, 0, 0, 0, 0],\n"
    "   [0, 0, 0, 0, 0],\n"
    "   [0, 0, 0, 0, 0],\n"
    "   [0, 0, 0, 0, 0],\n"
    " ]\n"
    "\n"
    " let g = grid.from_2d_list_with_topology(\n"
    "   board,\n"
    "   model.Directed,\n"
    "   grid.knight(),\n"
    "   can_move: grid.always(),\n"
    " )\n"
    " ```\n"
    "\n"
    " **Time Complexity:** O(rows × cols × |topology|)\n"
).
-spec from_2d_list_with_topology(
    list(list(KMD)),
    yog@model:graph_type(),
    list({integer(), integer()}),
    fun((KMD, KMD) -> boolean())
) -> grid(KMD, integer()).
from_2d_list_with_topology(Grid_data, Graph_type, Topology, Can_move) ->
    Rows = erlang:length(Grid_data),
    Cols = case Grid_data of
        [First_row | _] ->
            erlang:length(First_row);

        [] ->
            0
    end,
    Mut_graph = yog@model:new(Graph_type),
    Cells = begin
        _pipe = Grid_data,
        _pipe@2 = gleam@list:index_map(
            _pipe,
            fun(Row, Row_idx) -> _pipe@1 = Row,
                gleam@list:index_map(
                    _pipe@1,
                    fun(Cell, Col_idx) -> {Row_idx, Col_idx, Cell} end
                ) end
        ),
        lists:append(_pipe@2)
    end,
    Graph_with_nodes = begin
        _pipe@3 = Cells,
        gleam@list:fold(
            _pipe@3,
            Mut_graph,
            fun(G, Cell@1) ->
                {Row@1, Col, Data} = Cell@1,
                Id = coord_to_id(Row@1, Col, Cols),
                yog@model:add_node(G, Id, Data)
            end
        )
    end,
    Graph_with_edges = begin
        _pipe@4 = Cells,
        gleam@list:fold(
            _pipe@4,
            Graph_with_nodes,
            fun(G@1, Cell@2) ->
                {Row@2, Col@1, From_data} = Cell@2,
                From_id = coord_to_id(Row@2, Col@1, Cols),
                _pipe@5 = Topology,
                gleam@list:fold(
                    _pipe@5,
                    G@1,
                    fun(Acc_g, Delta) ->
                        {D_row, D_col} = Delta,
                        N_row = Row@2 + D_row,
                        N_col = Col@1 + D_col,
                        case (((N_row >= 0) andalso (N_row < Rows)) andalso (N_col
                        >= 0))
                        andalso (N_col < Cols) of
                            false ->
                                Acc_g;

                            true ->
                                To_id = coord_to_id(N_row, N_col, Cols),
                                case gleam_stdlib:map_get(
                                    erlang:element(3, Graph_with_nodes),
                                    To_id
                                ) of
                                    {ok, To_data} ->
                                        case Can_move(From_data, To_data) of
                                            true ->
                                                yog@model:add_edge(
                                                    Acc_g,
                                                    From_id,
                                                    To_id,
                                                    1
                                                );

                                            false ->
                                                Acc_g
                                        end;

                                    {error, _} ->
                                        Acc_g
                                end
                        end
                    end
                )
            end
        )
    end,
    {grid, Graph_with_edges, Rows, Cols}.

-file("src/yog/builder/grid.gleam", 82).
?DOC(
    " Creates a graph from a 2D list using 4-directional (rook) movement.\n"
    "\n"
    " Each cell becomes a node, and edges are added between adjacent cells\n"
    " (up/down/left/right) if the `can_move` predicate returns True.\n"
    " This is equivalent to `from_2d_list_with_topology` with `rook()`.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let heightmap = [[1, 2, 3], [2, 3, 4], [3, 4, 5]]\n"
    "\n"
    " let g = grid.from_2d_list(\n"
    "   heightmap,\n"
    "   model.Directed,\n"
    "   can_move: fn(from, to) { to - from <= 1 },\n"
    " )\n"
    " ```\n"
    "\n"
    " **Time Complexity:** O(rows × cols)\n"
).
-spec from_2d_list(
    list(list(KLY)),
    yog@model:graph_type(),
    fun((KLY, KLY) -> boolean())
) -> grid(KLY, integer()).
from_2d_list(Grid_data, Graph_type, Can_move) ->
    from_2d_list_with_topology(Grid_data, Graph_type, rook(), Can_move).

-file("src/yog/builder/grid.gleam", 284).
?DOC(
    " Converts a node ID back to grid coordinates (row, col).\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " grid.id_to_coord(0, 3)  // => #(0, 0)\n"
    " grid.id_to_coord(5, 3)  // => #(1, 2)\n"
    " grid.id_to_coord(7, 3)  // => #(2, 1)\n"
    " ```\n"
).
-spec id_to_coord(integer(), integer()) -> {integer(), integer()}.
id_to_coord(Id, Cols) ->
    {case Cols of
            0 -> 0;
            Gleam@denominator -> Id div Gleam@denominator
        end, case Cols of
            0 -> 0;
            Gleam@denominator@1 -> Id rem Gleam@denominator@1
        end}.

-file("src/yog/builder/grid.gleam", 300).
?DOC(
    " Gets the cell data at the specified grid coordinate.\n"
    "\n"
    " Returns `Ok(cell_data)` if the coordinate is valid, `Error(Nil)` otherwise.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " case grid.get_cell(grid, 1, 2) {\n"
    "   Ok(cell) -> // Use cell data\n"
    "   Error(_) -> // Out of bounds\n"
    " }\n"
    " ```\n"
).
-spec get_cell(grid(KMN, any()), integer(), integer()) -> {ok, KMN} |
    {error, nil}.
get_cell(Grid, Row, Col) ->
    case (((Row >= 0) andalso (Row < erlang:element(3, Grid))) andalso (Col >= 0))
    andalso (Col < erlang:element(4, Grid)) of
        false ->
            {error, nil};

        true ->
            Id = coord_to_id(Row, Col, erlang:element(4, Grid)),
            gleam_stdlib:map_get(erlang:element(3, erlang:element(2, Grid)), Id)
    end.

-file("src/yog/builder/grid.gleam", 324).
?DOC(
    " Converts the grid to a standard `Graph`.\n"
    "\n"
    " The resulting graph can be used with all yog algorithms.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph = grid.to_graph(grid)\n"
    " // Now use with pathfinding, traversal, etc.\n"
    " ```\n"
).
-spec to_graph(grid(KMT, KMU)) -> yog@model:graph(KMT, KMU).
to_graph(Grid) ->
    erlang:element(2, Grid).

-file("src/yog/builder/grid.gleam", 342).
?DOC(
    " Calculates the Manhattan distance between two node IDs.\n"
    "\n"
    " This is useful as a heuristic for A* pathfinding on grids.\n"
    " Manhattan distance is the sum of absolute differences in coordinates:\n"
    " |x1 - x2| + |y1 - y2|\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let start = grid.coord_to_id(0, 0, 10)\n"
    " let goal = grid.coord_to_id(3, 4, 10)\n"
    " let distance = grid.manhattan_distance(start, goal, 10)\n"
    " // => 7 (3 + 4)\n"
    " ```\n"
).
-spec manhattan_distance(integer(), integer(), integer()) -> integer().
manhattan_distance(From_id, To_id, Cols) ->
    {From_row, From_col} = id_to_coord(From_id, Cols),
    {To_row, To_col} = id_to_coord(To_id, Cols),
    Row_diff = case From_row > To_row of
        true ->
            From_row - To_row;

        false ->
            To_row - From_row
    end,
    Col_diff = case From_col > To_col of
        true ->
            From_col - To_col;

        false ->
            To_col - From_col
    end,
    Row_diff + Col_diff.

-file("src/yog/builder/grid.gleam", 372).
?DOC(
    " Finds a node in the grid where the cell data matches a predicate.\n"
    "\n"
    " Returns the node ID of the first matching cell, or Error(Nil) if not found.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Find the starting position marked with 'S'\n"
    " case grid.find_node(grid, fn(cell) { cell == \"S\" }) {\n"
    "   Ok(start_id) -> // Use start_id\n"
    "   Error(_) -> // Not found\n"
    " }\n"
    " ```\n"
).
-spec find_node(grid(KMZ, any()), fun((KMZ) -> boolean())) -> {ok, integer()} |
    {error, nil}.
find_node(Grid, Predicate) ->
    Max_id = (erlang:element(3, Grid) * erlang:element(4, Grid)) - 1,
    _pipe = yog@internal@utils:range(0, Max_id),
    gleam@list:find_map(
        _pipe,
        fun(Id) ->
            case gleam_stdlib:map_get(
                erlang:element(3, erlang:element(2, Grid)),
                Id
            ) of
                {ok, Data} ->
                    case Predicate(Data) of
                        true ->
                            {ok, Id};

                        false ->
                            {error, nil}
                    end;

                {error, _} ->
                    {error, nil}
            end
        end
    ).

-file("src/yog/builder/grid.gleam", 408).
?DOC(
    " Allows movement into any cell except the specified wall value.\n"
    "\n"
    " Useful for maze-style grids where `\"#\"` or similar marks a wall.\n"
    " The `from` cell is ignored — only the destination is checked.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Maze where \"#\" is impassable\n"
    " let maze = [\n"
    "   [\".\", \"#\", \".\"],\n"
    "   [\".\", \".\", \".\"],\n"
    "   [\"#\", \"#\", \".\"],\n"
    " ]\n"
    "\n"
    " let g = grid.from_2d_list(maze, model.Directed, can_move: grid.avoiding(\"#\"))\n"
    " // Edges only connect non-wall cells\n"
    " ```\n"
).
-spec avoiding(KNF) -> fun((KNF, KNF) -> boolean()).
avoiding(Wall_value) ->
    fun(_, To) -> To /= Wall_value end.

-file("src/yog/builder/grid.gleam", 431).
?DOC(
    " Allows movement only into cells matching the specified value.\n"
    "\n"
    " The inverse of `avoiding` — instead of blacklisting one value,\n"
    " this whitelists exactly one value. Useful when the grid has many\n"
    " different cell types but only one is traversable.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Grid with varied terrain — only \".\" is walkable\n"
    " let terrain = [\n"
    "   [\".\", \"~\", \"^\"],\n"
    "   [\".\", \".\", \"^\"],\n"
    "   [\"~\", \".\", \".\"],\n"
    " ]\n"
    "\n"
    " let g = grid.from_2d_list(terrain, model.Directed, can_move: grid.walkable(\".\"))\n"
    " // Only \".\" → \".\" edges exist\n"
    " ```\n"
).
-spec walkable(KNG) -> fun((KNG, KNG) -> boolean()).
walkable(Valid_value) ->
    fun(_, To) -> To =:= Valid_value end.

-file("src/yog/builder/grid.gleam", 449).
?DOC(
    " Always allows movement between adjacent cells.\n"
    "\n"
    " Every 4-directional neighbor pair gets an edge regardless of cell data.\n"
    " Useful for fully connected grids or when the cell data is purely\n"
    " informational (e.g., storing coordinates or labels).\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let labels = [[\"A\", \"B\"], [\"C\", \"D\"]]\n"
    "\n"
    " let g = grid.from_2d_list(labels, model.Undirected, can_move: grid.always())\n"
    " // All adjacent cells are connected\n"
    " ```\n"
).
-spec always() -> fun((KNH, KNH) -> boolean()).
always() ->
    fun(_, _) -> true end.