yog

-module(yog@traversal).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/traversal.gleam").
-export([walk/3, walk_until/4]).
-export_type([order/0]).

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

-type order() :: breadth_first | depth_first.

-file("src/yog/traversal.gleam", 79).
-spec do_walk_bfs(
    yog@model:graph(any(), any()),
    yog@internal@queue:queue(integer()),
    gleam@set:set(integer()),
    list(integer())
) -> list(integer()).
do_walk_bfs(Graph, Q, Visited, Acc) ->
    case yog@internal@queue:pop(Q) of
        {error, nil} ->
            lists:reverse(Acc);

        {ok, {Head, Rest}} ->
            case gleam@set:contains(Visited, Head) of
                true ->
                    do_walk_bfs(Graph, Rest, Visited, Acc);

                false ->
                    Next_nodes = yog@model:successor_ids(Graph, Head),
                    Next_queue = yog@internal@queue:push_list(Rest, Next_nodes),
                    do_walk_bfs(
                        Graph,
                        Next_queue,
                        gleam@set:insert(Visited, Head),
                        [Head | Acc]
                    )
            end
    end.

-file("src/yog/traversal.gleam", 105).
-spec do_walk_dfs(
    yog@model:graph(any(), any()),
    list(integer()),
    gleam@set:set(integer()),
    list(integer())
) -> list(integer()).
do_walk_dfs(Graph, Stack, Visited, Acc) ->
    case Stack of
        [] ->
            lists:reverse(Acc);

        [Head | Tail] ->
            case gleam@set:contains(Visited, Head) of
                true ->
                    do_walk_dfs(Graph, Tail, Visited, Acc);

                false ->
                    Next_nodes = yog@model:successor_ids(Graph, Head),
                    Next_stack = lists:append(Next_nodes, Tail),
                    do_walk_dfs(
                        Graph,
                        Next_stack,
                        gleam@set:insert(Visited, Head),
                        [Head | Acc]
                    )
            end
    end.

-file("src/yog/traversal.gleam", 30).
?DOC(
    " Walks the graph starting from the given node, visiting all reachable nodes.\n"
    "\n"
    " Returns a list of NodeIds in the order they were visited.\n"
    " Uses successors to follow directed paths.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // BFS traversal\n"
    " traversal.walk(from: 1, in: graph, using: BreadthFirst)\n"
    " // => [1, 2, 3, 4, 5]\n"
    "\n"
    " // DFS traversal\n"
    " traversal.walk(from: 1, in: graph, using: DepthFirst)\n"
    " // => [1, 2, 4, 5, 3]\n"
    " ```\n"
).
-spec walk(integer(), yog@model:graph(any(), any()), order()) -> list(integer()).
walk(Start_id, Graph, Order) ->
    case Order of
        breadth_first ->
            do_walk_bfs(
                Graph,
                begin
                    _pipe = yog@internal@queue:new(),
                    yog@internal@queue:push(_pipe, Start_id)
                end,
                gleam@set:new(),
                []
            );

        depth_first ->
            do_walk_dfs(Graph, [Start_id], gleam@set:new(), [])
    end.

-file("src/yog/traversal.gleam", 131).
-spec do_walk_until_bfs(
    yog@model:graph(any(), any()),
    yog@internal@queue:queue(integer()),
    gleam@set:set(integer()),
    list(integer()),
    fun((integer()) -> boolean())
) -> list(integer()).
do_walk_until_bfs(Graph, Q, Visited, Acc, Should_stop) ->
    case yog@internal@queue:pop(Q) of
        {error, nil} ->
            lists:reverse(Acc);

        {ok, {Head, Rest}} ->
            case gleam@set:contains(Visited, Head) of
                true ->
                    do_walk_until_bfs(Graph, Rest, Visited, Acc, Should_stop);

                false ->
                    Current_acc = [Head | Acc],
                    case Should_stop(Head) of
                        true ->
                            lists:reverse(Current_acc);

                        false ->
                            Next_nodes = yog@model:successor_ids(Graph, Head),
                            Next_queue = yog@internal@queue:push_list(
                                Rest,
                                Next_nodes
                            ),
                            do_walk_until_bfs(
                                Graph,
                                Next_queue,
                                gleam@set:insert(Visited, Head),
                                Current_acc,
                                Should_stop
                            )
                    end
            end
    end.

-file("src/yog/traversal.gleam", 168).
-spec do_walk_until_dfs(
    yog@model:graph(any(), any()),
    list(integer()),
    gleam@set:set(integer()),
    list(integer()),
    fun((integer()) -> boolean())
) -> list(integer()).
do_walk_until_dfs(Graph, Stack, Visited, Acc, Should_stop) ->
    case Stack of
        [] ->
            lists:reverse(Acc);

        [Head | Tail] ->
            case gleam@set:contains(Visited, Head) of
                true ->
                    do_walk_until_dfs(Graph, Tail, Visited, Acc, Should_stop);

                false ->
                    Current_acc = [Head | Acc],
                    case Should_stop(Head) of
                        true ->
                            lists:reverse(Current_acc);

                        false ->
                            Next_nodes = yog@model:successor_ids(Graph, Head),
                            Next_stack = lists:append(Next_nodes, Tail),
                            do_walk_until_dfs(
                                Graph,
                                Next_stack,
                                gleam@set:insert(Visited, Head),
                                Current_acc,
                                Should_stop
                            )
                    end
            end
    end.

-file("src/yog/traversal.gleam", 58).
?DOC(
    " Walks the graph but stops early when a condition is met.\n"
    "\n"
    " Traverses the graph until `should_stop` returns True for a node.\n"
    " Returns all nodes visited including the one that stopped traversal.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Stop when we find node 5\n"
    " traversal.walk_until(\n"
    "   from: 1,\n"
    "   in: graph,\n"
    "   using: BreadthFirst,\n"
    "   until: fn(node) { node == 5 }\n"
    " )\n"
    " ```\n"
).
-spec walk_until(
    integer(),
    yog@model:graph(any(), any()),
    order(),
    fun((integer()) -> boolean())
) -> list(integer()).
walk_until(Start_id, Graph, Order, Should_stop) ->
    case Order of
        breadth_first ->
            do_walk_until_bfs(
                Graph,
                begin
                    _pipe = yog@internal@queue:new(),
                    yog@internal@queue:push(_pipe, Start_id)
                end,
                gleam@set:new(),
                [],
                Should_stop
            );

        depth_first ->
            do_walk_until_dfs(
                Graph,
                [Start_id],
                gleam@set:new(),
                [],
                Should_stop
            )
    end.