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", 62).
-spec do_walk(
    yog@model:graph(any(), any()),
    list(integer()),
    gleam@set:set(integer()),
    list(integer()),
    order()
) -> list(integer()).
do_walk(Graph, Queue, Visited, Acc, Order) ->
    case Queue of
        [] ->
            lists:reverse(Acc);

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

                false ->
                    Next_nodes = yog@model:successor_ids(Graph, Head),
                    Next_queue = case Order of
                        breadth_first ->
                            lists:append(Tail, Next_nodes);

                        depth_first ->
                            lists:append(Next_nodes, Tail)
                    end,
                    do_walk(
                        Graph,
                        Next_queue,
                        gleam@set:insert(Visited, Head),
                        [Head | Acc],
                        Order
                    )
            end
    end.

-file("src/yog/traversal.gleam", 29).
?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) ->
    do_walk(Graph, [Start_id], gleam@set:new(), [], Order).

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

        [Head | Tail] ->
            case gleam@set:contains(Visited, Head) of
                true ->
                    do_walk_until(Graph, Tail, Visited, Acc, Order, 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 = case Order of
                                breadth_first ->
                                    lists:append(Tail, Next_nodes);

                                depth_first ->
                                    lists:append(Next_nodes, Tail)
                            end,
                            do_walk_until(
                                Graph,
                                Next_queue,
                                gleam@set:insert(Visited, Head),
                                Current_acc,
                                Order,
                                Should_stop
                            )
                    end
            end
    end.

-file("src/yog/traversal.gleam", 53).
?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) ->
    do_walk_until(Graph, [Start_id], gleam@set:new(), [], Order, Should_stop).