dream

-module(dream@router@trie).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/dream/router/trie.gleam").
-export([new/0, lookup/3, insert/4]).
-export_type([segment/0, trie_node/1, radix_trie/1, match/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(
    " Radix Trie - Fast route matching data structure\n"
    "\n"
    " Provides O(path depth) route lookup instead of O(number of routes) linear search.\n"
    " This is the core data structure used by Dream's router for efficient route matching.\n"
    "\n"
    " ## Performance Characteristics\n"
    "\n"
    " - **Insert**: O(segments in pattern) - typically 3-5 segments\n"
    " - **Lookup**: O(segments in path) - independent of total number of routes\n"
    " - **Memory**: O(total segments across all routes)\n"
    "\n"
    " ## How It Works\n"
    "\n"
    " The trie organizes routes as a tree where each level represents a path segment.\n"
    " Nodes are prioritized in this order:\n"
    " 1. Literal matches (exact string match)\n"
    " 2. Parameter matches (:id)\n"
    " 3. Single wildcards (*)\n"
    " 4. Extension patterns (*.jpg)\n"
    " 5. Multi-wildcards (**)\n"
    "\n"
    " This ensures the most specific route always wins when multiple routes could match.\n"
    "\n"
    " ## Example\n"
    "\n"
    " Routes: `/users/:id`, `/users/new`, `/files/**path`\n"
    "\n"
    " Tree structure:\n"
    " ```\n"
    " root\n"
    "   └─ users\n"
    "      ├─ new (literal - highest priority)\n"
    "      └─ :id (param - lower priority)\n"
    "   └─ files\n"
    "      └─ **path (multi-wildcard - lowest priority)\n"
    " ```\n"
    "\n"
    " Path `/users/new` matches the literal route, not `:id`.\n"
).

-type segment() :: {literal, binary()} |
    {param, binary()} |
    {single_wildcard, gleam@option:option(binary())} |
    {multi_wildcard, gleam@option:option(binary())} |
    {extension_pattern, list(binary())} |
    {literal_extension, binary(), list(binary())}.

-opaque trie_node(AFMN) :: {trie_node,
        gleam@dict:dict(binary(), AFMN),
        gleam@dict:dict(binary(), trie_node(AFMN)),
        list({binary(), list(binary()), trie_node(AFMN)}),
        gleam@option:option({binary(), trie_node(AFMN)}),
        gleam@option:option({gleam@option:option(binary()), trie_node(AFMN)}),
        gleam@option:option({gleam@option:option(binary()), trie_node(AFMN)}),
        list({list(binary()), trie_node(AFMN)})}.

-opaque radix_trie(AFMO) :: {radix_trie, trie_node(AFMO)}.

-type match(AFMP) :: {match, AFMP, list({binary(), binary()})}.

-file("src/dream/router/trie.gleam", 148).
?DOC(" Create an empty trie node with no routes or children\n").
-spec empty_node() -> trie_node(any()).
empty_node() ->
    {trie_node, maps:new(), maps:new(), [], none, none, none, []}.

-file("src/dream/router/trie.gleam", 143).
?DOC(
    " Create a new empty radix trie\n"
    "\n"
    " Returns a trie with no routes. Use `insert()` to add routes.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let trie = new()\n"
    " |> insert(\"GET\", [Literal(\"users\")], user_handler)\n"
    " ```\n"
).
-spec new() -> radix_trie(any()).
new() ->
    {radix_trie, empty_node()}.

-file("src/dream/router/trie.gleam", 214).
?DOC(" Store a route at the current node for a specific HTTP method\n").
-spec insert_route_at_node(trie_node(AFNC), binary(), AFNC) -> trie_node(AFNC).
insert_route_at_node(Node, Method, Route) ->
    Updated_routes = gleam@dict:insert(erlang:element(2, Node), Method, Route),
    {trie_node,
        Updated_routes,
        erlang:element(3, Node),
        erlang:element(4, Node),
        erlang:element(5, Node),
        erlang:element(6, Node),
        erlang:element(7, Node),
        erlang:element(8, Node)}.

-file("src/dream/router/trie.gleam", 273).
?DOC(" Find a literal extension child matching the given base and extensions\n").
-spec find_literal_extension_child(
    list({binary(), list(binary()), trie_node(AFNT)}),
    binary(),
    list(binary())
) -> gleam@option:option(trie_node(AFNT)).
find_literal_extension_child(Children, Base, Exts) ->
    case Children of
        [] ->
            none;

        [{Child_base, Child_exts, Child} | Rest_children] ->
            case (Child_base =:= Base) andalso (Child_exts =:= Exts) of
                true ->
                    {some, Child};

                false ->
                    find_literal_extension_child(Rest_children, Base, Exts)
            end
    end.

-file("src/dream/router/trie.gleam", 259).
?DOC(" Get existing literal extension child or create a new empty node\n").
-spec get_or_create_literal_extension_child(
    trie_node(AFNO),
    binary(),
    list(binary())
) -> trie_node(AFNO).
get_or_create_literal_extension_child(Node, Base, Exts) ->
    case find_literal_extension_child(erlang:element(4, Node), Base, Exts) of
        {some, Existing} ->
            Existing;

        none ->
            empty_node()
    end.

-file("src/dream/router/trie.gleam", 289).
?DOC(" Update or add a literal extension child in the children list\n").
-spec update_literal_extension_children(
    list({binary(), list(binary()), trie_node(AFOA)}),
    binary(),
    list(binary()),
    trie_node(AFOA)
) -> list({binary(), list(binary()), trie_node(AFOA)}).
update_literal_extension_children(Children, Base, Exts, New_child) ->
    case Children of
        [] ->
            [{Base, Exts, New_child}];

        [{Child_base, Child_exts, Child} | Rest_children] ->
            case (Child_base =:= Base) andalso (Child_exts =:= Exts) of
                true ->
                    [{Base, Exts, New_child} | Rest_children];

                false ->
                    [{Child_base, Child_exts, Child} |
                        update_literal_extension_children(
                            Rest_children,
                            Base,
                            Exts,
                            New_child
                        )]
            end
    end.

-file("src/dream/router/trie.gleam", 374).
?DOC(" Get existing literal child or create a new empty node\n").
-spec get_or_create_literal_child(trie_node(AFPB), binary()) -> trie_node(AFPB).
get_or_create_literal_child(Node, Name) ->
    case gleam_stdlib:map_get(erlang:element(3, Node), Name) of
        {ok, Existing} ->
            Existing;

        {error, _} ->
            empty_node()
    end.

-file("src/dream/router/trie.gleam", 385).
?DOC(" Get existing parameter child or create a new empty node\n").
-spec get_or_create_param_child(trie_node(AFPE)) -> trie_node(AFPE).
get_or_create_param_child(Node) ->
    case erlang:element(5, Node) of
        {some, {_, Existing}} ->
            Existing;

        none ->
            empty_node()
    end.

-file("src/dream/router/trie.gleam", 393).
?DOC(" Get existing wildcard child or create a new empty node\n").
-spec get_or_create_wildcard_child(trie_node(AFPH)) -> trie_node(AFPH).
get_or_create_wildcard_child(Node) ->
    case erlang:element(6, Node) of
        {some, {_, Existing}} ->
            Existing;

        none ->
            empty_node()
    end.

-file("src/dream/router/trie.gleam", 401).
?DOC(" Get existing multi-wildcard child or create a new empty node\n").
-spec get_or_create_multi_wildcard_child(trie_node(AFPK)) -> trie_node(AFPK).
get_or_create_multi_wildcard_child(Node) ->
    case erlang:element(7, Node) of
        {some, {_, Existing}} ->
            Existing;

        none ->
            empty_node()
    end.

-file("src/dream/router/trie.gleam", 420).
?DOC(" Find an extension child matching the given extension list\n").
-spec find_extension_child(
    list({list(binary()), trie_node(AFPS)}),
    list(binary())
) -> gleam@option:option(trie_node(AFPS)).
find_extension_child(Children, Exts) ->
    case Children of
        [] ->
            none;

        [{Child_exts, Child} | Rest] ->
            case Child_exts =:= Exts of
                true ->
                    {some, Child};

                false ->
                    find_extension_child(Rest, Exts)
            end
    end.

-file("src/dream/router/trie.gleam", 409).
?DOC(" Get existing extension child or create a new empty node\n").
-spec get_or_create_extension_child(trie_node(AFPN), list(binary())) -> trie_node(AFPN).
get_or_create_extension_child(Node, Exts) ->
    case find_extension_child(erlang:element(8, Node), Exts) of
        {some, Existing} ->
            Existing;

        none ->
            empty_node()
    end.

-file("src/dream/router/trie.gleam", 435).
?DOC(" Update or add an extension child in the children list\n").
-spec update_extension_children(
    list({list(binary()), trie_node(AFPZ)}),
    list(binary()),
    trie_node(AFPZ)
) -> list({list(binary()), trie_node(AFPZ)}).
update_extension_children(Children, Exts, New_child) ->
    case Children of
        [] ->
            [{Exts, New_child}];

        [{Child_exts, Child} | Rest] ->
            case Child_exts =:= Exts of
                true ->
                    [{Exts, New_child} | Rest];

                false ->
                    [{Child_exts, Child} |
                        update_extension_children(Rest, Exts, New_child)]
            end
    end.

-file("src/dream/router/trie.gleam", 538).
?DOC(" Try to find a route at the current node for the given method\n").
-spec lookup_route_at_node(
    trie_node(AFRC),
    binary(),
    list({binary(), binary()})
) -> gleam@option:option(match(AFRC)).
lookup_route_at_node(Node, Method, Params) ->
    case gleam_stdlib:map_get(erlang:element(2, Node), Method) of
        {ok, Route} ->
            {some, {match, Route, Params}};

        {error, _} ->
            none
    end.

-file("src/dream/router/trie.gleam", 522).
?DOC(" Try to match empty path with multi-wildcard (for routes like /public/**)\n").
-spec try_multi_wildcard_empty_path(
    trie_node(AFQX),
    binary(),
    list({binary(), binary()})
) -> gleam@option:option(match(AFQX)).
try_multi_wildcard_empty_path(Node, Method, Params) ->
    case erlang:element(7, Node) of
        {some, {Wildcard_name, Child}} ->
            Param_name = gleam@option:unwrap(Wildcard_name, <<"path"/utf8>>),
            Updated_params = [{Param_name, <<""/utf8>>} | Params],
            lookup_route_at_node(Child, Method, Updated_params);

        none ->
            none
    end.

-file("src/dream/router/trie.gleam", 509).
?DOC(" Look up route when path segments are exhausted\n").
-spec lookup_empty_path(trie_node(AFQS), binary(), list({binary(), binary()})) -> gleam@option:option(match(AFQS)).
lookup_empty_path(Node, Method, Params) ->
    Route_result = lookup_route_at_node(Node, Method, Params),
    case Route_result of
        {some, Match} ->
            {some, Match};

        none ->
            try_multi_wildcard_empty_path(Node, Method, Params)
    end.

-file("src/dream/router/trie.gleam", 653).
?DOC(
    " Strip extension from a segment if it has one\n"
    "\n"
    " Returns the base name without extension, or None if no extension found.\n"
    " Example: \"products.json\" -> Some(\"products\"), \"products\" -> None\n"
).
-spec strip_extension_from_segment(binary()) -> gleam@option:option(binary()).
strip_extension_from_segment(Segment) ->
    case gleam@string:split(Segment, <<"."/utf8>>) of
        [Base_name, _] ->
            {some, Base_name};

        _ ->
            none
    end.

-file("src/dream/router/trie.gleam", 782).
?DOC(
    " Check if a segment matches a literal+extension pattern\n"
    "\n"
    " Example: \"products.json\" matches base=\"products\" with exts=[\"json\", \"xml\"]\n"
).
-spec matches_literal_extension(binary(), binary(), list(binary())) -> boolean().
matches_literal_extension(Segment, Base, Extensions) ->
    Prefix = <<Base/binary, "."/utf8>>,
    case gleam_stdlib:string_starts_with(Segment, Prefix) of
        true ->
            Ext = gleam@string:drop_start(Segment, string:length(Prefix)),
            gleam@list:contains(Extensions, Ext);

        false ->
            false
    end.

-file("src/dream/router/trie.gleam", 823).
?DOC(
    " Check if a filename ends with a specific extension\n"
    "\n"
    " This is a named function to avoid anonymous functions in production code.\n"
).
-spec check_extension_match(binary(), binary()) -> boolean().
check_extension_match(Filename, Ext) ->
    gleam_stdlib:string_ends_with(Filename, <<"."/utf8, Ext/binary>>).

-file("src/dream/router/trie.gleam", 816).
?DOC(" Check if a filename matches any of the given extensions\n").
-spec matches_any_extension(binary(), list(binary())) -> boolean().
matches_any_extension(Filename, Extensions) ->
    gleam@list:any(
        Extensions,
        fun(_capture) -> check_extension_match(Filename, _capture) end
    ).

-file("src/dream/router/trie.gleam", 559).
?DOC(
    " Match a single path segment against the node's children\n"
    "\n"
    " Tries matches in priority order:\n"
    " 1. Literal (exact match)\n"
    " 2. Literal+extension pattern (products.{json,xml})\n"
    " 3. Extension pattern (*.jpg) - checked before extension stripping\n"
    " 4. Literal without extension (e.g., \"products.json\" -> \"products\")\n"
    " 5. Parameter (:id)\n"
    " 6. Single wildcard (*)\n"
    " 7. Multi-wildcard (**)\n"
).
-spec lookup_segment(
    trie_node(AFRH),
    binary(),
    binary(),
    list(binary()),
    list({binary(), binary()})
) -> gleam@option:option(match(AFRH)).
lookup_segment(Node, Method, Segment, Rest, Params) ->
    case gleam_stdlib:map_get(erlang:element(3, Node), Segment) of
        {ok, Child} ->
            lookup_in_node(Child, Method, Rest, Params);

        {error, _} ->
            Literal_ext_result = try_literal_extension_match(
                erlang:element(4, Node),
                Segment,
                Method,
                Rest,
                Params
            ),
            case Literal_ext_result of
                {some, Match} ->
                    {some, Match};

                none ->
                    Extension_result = try_extension_match(
                        erlang:element(8, Node),
                        Segment,
                        Method,
                        Rest,
                        Params
                    ),
                    case Extension_result of
                        {some, Match@1} ->
                            {some, Match@1};

                        none ->
                            try_literal_without_extension(
                                Node,
                                Method,
                                Segment,
                                Rest,
                                Params
                            )
                    end
            end
    end.

-file("src/dream/router/trie.gleam", 496).
?DOC(" Look up a route starting from a specific node\n").
-spec lookup_in_node(
    trie_node(AFQM),
    binary(),
    list(binary()),
    list({binary(), binary()})
) -> gleam@option:option(match(AFQM)).
lookup_in_node(Node, Method, Path_segments, Params) ->
    case Path_segments of
        [] ->
            lookup_empty_path(Node, Method, Params);

        [Segment | Rest] ->
            lookup_segment(Node, Method, Segment, Rest, Params)
    end.

-file("src/dream/router/trie.gleam", 487).
?DOC(
    " Look up a route in the trie\n"
    "\n"
    " Searches for a route matching the given HTTP method and path segments.\n"
    " Returns the matched route and extracted parameters, or None if no match.\n"
    "\n"
    " Lookup is O(path depth) - independent of the total number of routes in the trie.\n"
    "\n"
    " ## Parameters\n"
    "\n"
    " - `trie`: The trie to search\n"
    " - `method`: HTTP method as string (e.g., \"GET\", \"POST\")\n"
    " - `path_segments`: Path split into segments (e.g., [\"users\", \"123\"])\n"
    "\n"
    " ## Returns\n"
    "\n"
    " - `Some(Match)`: Contains the matched route and extracted parameters\n"
    " - `None`: No route matched the method and path\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let result = lookup(trie, \"GET\", [\"users\", \"123\"])\n"
    " case result {\n"
    "   Some(Match(route, params)) -> {\n"
    "     // params = [#(\"id\", \"123\")]\n"
    "     // route is the handler\n"
    "   }\n"
    "   None -> // No matching route\n"
    " }\n"
    " ```\n"
).
-spec lookup(radix_trie(AFQH), binary(), list(binary())) -> gleam@option:option(match(AFQH)).
lookup(Trie, Method, Path_segments) ->
    lookup_in_node(erlang:element(2, Trie), Method, Path_segments, []).

-file("src/dream/router/trie.gleam", 691).
?DOC(
    " Try to match segment as a parameter, using stripped segment for matching\n"
    " but preserving original segment in params for format detection\n"
    "\n"
    " This is used when extension stripping is applied - we match using the\n"
    " base name (e.g., \"1\" from \"1.json\") but store the original value\n"
    " (e.g., \"1.json\") in params so controllers can detect the format.\n"
    "\n"
    " Note: The stripped_segment parameter is not used directly, but the fact\n"
    " that we're calling this function indicates we've already verified the\n"
    " stripped segment doesn't match as a literal, so we proceed with param matching.\n"
).
-spec try_param_match_with_original(
    trie_node(AFSA),
    binary(),
    binary(),
    binary(),
    list(binary()),
    list({binary(), binary()})
) -> gleam@option:option(match(AFSA)).
try_param_match_with_original(Node, Method, _, Original_segment, Rest, Params) ->
    case erlang:element(5, Node) of
        {some, {Param_name, Child}} ->
            Updated_params = [{Param_name, Original_segment} | Params],
            lookup_in_node(Child, Method, Rest, Updated_params);

        none ->
            none
    end.

-file("src/dream/router/trie.gleam", 741).
?DOC(" Try to match segment as a multi-segment wildcard (captures remaining path)\n").
-spec try_multi_wildcard_match(
    trie_node(AFSS),
    binary(),
    binary(),
    list(binary()),
    list({binary(), binary()})
) -> gleam@option:option(match(AFSS)).
try_multi_wildcard_match(Node, Method, Segment, Rest, Params) ->
    case erlang:element(7, Node) of
        {some, {Wildcard_name, Child}} ->
            Param_name = gleam@option:unwrap(Wildcard_name, <<"path"/utf8>>),
            All_segments = [Segment | Rest],
            Captured = gleam@string:join(All_segments, <<"/"/utf8>>),
            Updated_params = [{Param_name, Captured} | Params],
            lookup_in_node(Child, Method, [], Updated_params);

        none ->
            none
    end.

-file("src/dream/router/trie.gleam", 730).
?DOC(" Try multi-wildcard match (extension patterns already checked earlier)\n").
-spec try_multi_wildcard_only(
    trie_node(AFSM),
    binary(),
    binary(),
    list(binary()),
    list({binary(), binary()})
) -> gleam@option:option(match(AFSM)).
try_multi_wildcard_only(Node, Method, Segment, Rest, Params) ->
    try_multi_wildcard_match(Node, Method, Segment, Rest, Params).

-file("src/dream/router/trie.gleam", 712).
?DOC(" Try to match segment as a single wildcard\n").
-spec try_wildcard_match(
    trie_node(AFSG),
    binary(),
    binary(),
    list(binary()),
    list({binary(), binary()})
) -> gleam@option:option(match(AFSG)).
try_wildcard_match(Node, Method, Segment, Rest, Params) ->
    case erlang:element(6, Node) of
        {some, {Wildcard_name, Child}} ->
            Param_name = gleam@option:unwrap(Wildcard_name, <<"wildcard"/utf8>>),
            Updated_params = [{Param_name, Segment} | Params],
            lookup_in_node(Child, Method, Rest, Updated_params);

        none ->
            try_multi_wildcard_only(Node, Method, Segment, Rest, Params)
    end.

-file("src/dream/router/trie.gleam", 664).
?DOC(
    " Try to match segment as a parameter\n"
    "\n"
    " Note: Parameters capture the full segment including extensions.\n"
    " Extension stripping only applies to literal matches.\n"
).
-spec try_param_match(
    trie_node(AFRU),
    binary(),
    binary(),
    list(binary()),
    list({binary(), binary()})
) -> gleam@option:option(match(AFRU)).
try_param_match(Node, Method, Segment, Rest, Params) ->
    case erlang:element(5, Node) of
        {some, {Param_name, Child}} ->
            Updated_params = [{Param_name, Segment} | Params],
            lookup_in_node(Child, Method, Rest, Updated_params);

        none ->
            try_wildcard_match(Node, Method, Segment, Rest, Params)
    end.

-file("src/dream/router/trie.gleam", 610).
?DOC(
    " Try matching segment without its extension (e.g., \"products.json\" -> \"products\")\n"
    "\n"
    " This allows routes like `/products` to match `/products.json`, enabling\n"
    " format detection in controllers without requiring extension pattern routes.\n"
    " Also handles parameter segments with extensions (e.g., \"1.json\" -> \"1\").\n"
    "\n"
    " Note: Extension stripping only applies to literal and parameter matches.\n"
    " Wildcards always capture the full segment including extensions.\n"
).
-spec try_literal_without_extension(
    trie_node(AFRN),
    binary(),
    binary(),
    list(binary()),
    list({binary(), binary()})
) -> gleam@option:option(match(AFRN)).
try_literal_without_extension(Node, Method, Segment, Rest, Params) ->
    Segment_without_ext = strip_extension_from_segment(Segment),
    case Segment_without_ext of
        {some, Base_name} ->
            case gleam_stdlib:map_get(erlang:element(3, Node), Base_name) of
                {ok, Child} ->
                    lookup_in_node(Child, Method, Rest, Params);

                {error, _} ->
                    case try_wildcard_match(Node, Method, Segment, Rest, Params) of
                        {some, Match} ->
                            {some, Match};

                        none ->
                            try_param_match_with_original(
                                Node,
                                Method,
                                Base_name,
                                Segment,
                                Rest,
                                Params
                            )
                    end
            end;

        none ->
            try_param_match(Node, Method, Segment, Rest, Params)
    end.

-file("src/dream/router/trie.gleam", 761).
?DOC(" Try to match segment against literal+extension patterns (products.{json,xml})\n").
-spec try_literal_extension_match(
    list({binary(), list(binary()), trie_node(AFSZ)}),
    binary(),
    binary(),
    list(binary()),
    list({binary(), binary()})
) -> gleam@option:option(match(AFSZ)).
try_literal_extension_match(Children, Segment, Method, Rest, Params) ->
    case Children of
        [] ->
            none;

        [{Base, Exts, Child} | Remaining] ->
            case matches_literal_extension(Segment, Base, Exts) of
                true ->
                    lookup_in_node(Child, Method, Rest, Params);

                false ->
                    try_literal_extension_match(
                        Remaining,
                        Segment,
                        Method,
                        Rest,
                        Params
                    )
            end
    end.

-file("src/dream/router/trie.gleam", 798).
?DOC(" Try to match segment against extension patterns\n").
-spec try_extension_match(
    list({list(binary()), trie_node(AFTI)}),
    binary(),
    binary(),
    list(binary()),
    list({binary(), binary()})
) -> gleam@option:option(match(AFTI)).
try_extension_match(Extension_children, Segment, Method, Rest, Params) ->
    case Extension_children of
        [] ->
            none;

        [{Exts, Child} | Remaining] ->
            case matches_any_extension(Segment, Exts) of
                true ->
                    lookup_in_node(Child, Method, Rest, Params);

                false ->
                    try_extension_match(
                        Remaining,
                        Segment,
                        Method,
                        Rest,
                        Params
                    )
            end
    end.

-file("src/dream/router/trie.gleam", 224).
?DOC(" Insert a literal segment and recurse into its child\n").
-spec insert_literal_segment(
    trie_node(AFNF),
    binary(),
    binary(),
    list(segment()),
    AFNF
) -> trie_node(AFNF).
insert_literal_segment(Node, Name, Method, Rest, Route) ->
    Child = get_or_create_literal_child(Node, Name),
    Updated_child = insert_into_node(Child, Method, Rest, Route),
    Updated_children = gleam@dict:insert(
        erlang:element(3, Node),
        Name,
        Updated_child
    ),
    {trie_node,
        erlang:element(2, Node),
        Updated_children,
        erlang:element(4, Node),
        erlang:element(5, Node),
        erlang:element(6, Node),
        erlang:element(7, Node),
        erlang:element(8, Node)}.

-file("src/dream/router/trie.gleam", 190).
?DOC(" Insert a route into a specific node, recursing through segments\n").
-spec insert_into_node(trie_node(AFMY), binary(), list(segment()), AFMY) -> trie_node(AFMY).
insert_into_node(Node, Method, Segments, Route) ->
    case Segments of
        [] ->
            insert_route_at_node(Node, Method, Route);

        [{literal, Name} | Rest] ->
            insert_literal_segment(Node, Name, Method, Rest, Route);

        [{literal_extension, Base, Exts} | Rest@1] ->
            insert_literal_extension_segment(
                Node,
                Base,
                Exts,
                Method,
                Rest@1,
                Route
            );

        [{param, Name@1} | Rest@2] ->
            insert_param_segment(Node, Name@1, Method, Rest@2, Route);

        [{single_wildcard, Name@2} | Rest@3] ->
            insert_wildcard_segment(Node, Name@2, Method, Rest@3, Route);

        [{multi_wildcard, Name@3} | Rest@4] ->
            insert_multi_wildcard_segment(Node, Name@3, Method, Rest@4, Route);

        [{extension_pattern, Exts@1} | Rest@5] ->
            insert_extension_segment(Node, Exts@1, Method, Rest@5, Route)
    end.

-file("src/dream/router/trie.gleam", 179).
?DOC(
    " Insert a route into the trie\n"
    "\n"
    " Adds a route at the path specified by the segments. If a route already\n"
    " exists for the same method and path, it is replaced.\n"
    "\n"
    " ## Parameters\n"
    "\n"
    " - `trie`: The trie to insert into\n"
    " - `method`: HTTP method as string (e.g., \"GET\", \"POST\")\n"
    " - `segments`: Path segments from pattern parser\n"
    " - `route`: The route handler to store\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let trie = new()\n"
    " |> insert(\"GET\", [Literal(\"users\"), Param(\"id\")], handler)\n"
    " |> insert(\"POST\", [Literal(\"users\")], create_handler)\n"
    " ```\n"
).
-spec insert(radix_trie(AFMU), binary(), list(segment()), AFMU) -> radix_trie(AFMU).
insert(Trie, Method, Segments, Route) ->
    Updated_root = insert_into_node(
        erlang:element(2, Trie),
        Method,
        Segments,
        Route
    ),
    {radix_trie, Updated_root}.

-file("src/dream/router/trie.gleam", 238).
?DOC(" Insert a literal+extension segment and recurse into its child\n").
-spec insert_literal_extension_segment(
    trie_node(AFNJ),
    binary(),
    list(binary()),
    binary(),
    list(segment()),
    AFNJ
) -> trie_node(AFNJ).
insert_literal_extension_segment(Node, Base, Exts, Method, Rest, Route) ->
    Child = get_or_create_literal_extension_child(Node, Base, Exts),
    Updated_child = insert_into_node(Child, Method, Rest, Route),
    Updated_children = update_literal_extension_children(
        erlang:element(4, Node),
        Base,
        Exts,
        Updated_child
    ),
    {trie_node,
        erlang:element(2, Node),
        erlang:element(3, Node),
        Updated_children,
        erlang:element(5, Node),
        erlang:element(6, Node),
        erlang:element(7, Node),
        erlang:element(8, Node)}.

-file("src/dream/router/trie.gleam", 314).
?DOC(" Insert a parameter segment and recurse into its child\n").
-spec insert_param_segment(
    trie_node(AFOI),
    binary(),
    binary(),
    list(segment()),
    AFOI
) -> trie_node(AFOI).
insert_param_segment(Node, Name, Method, Rest, Route) ->
    Param_name = case erlang:element(5, Node) of
        {some, {Existing_name, _}} ->
            Existing_name;

        none ->
            Name
    end,
    Child = get_or_create_param_child(Node),
    Updated_child = insert_into_node(Child, Method, Rest, Route),
    {trie_node,
        erlang:element(2, Node),
        erlang:element(3, Node),
        erlang:element(4, Node),
        {some, {Param_name, Updated_child}},
        erlang:element(6, Node),
        erlang:element(7, Node),
        erlang:element(8, Node)}.

-file("src/dream/router/trie.gleam", 333).
?DOC(" Insert a single wildcard segment and recurse into its child\n").
-spec insert_wildcard_segment(
    trie_node(AFOM),
    gleam@option:option(binary()),
    binary(),
    list(segment()),
    AFOM
) -> trie_node(AFOM).
insert_wildcard_segment(Node, Name, Method, Rest, Route) ->
    Child = get_or_create_wildcard_child(Node),
    Updated_child = insert_into_node(Child, Method, Rest, Route),
    {trie_node,
        erlang:element(2, Node),
        erlang:element(3, Node),
        erlang:element(4, Node),
        erlang:element(5, Node),
        {some, {Name, Updated_child}},
        erlang:element(7, Node),
        erlang:element(8, Node)}.

-file("src/dream/router/trie.gleam", 346).
?DOC(" Insert a multi-segment wildcard and recurse into its child\n").
-spec insert_multi_wildcard_segment(
    trie_node(AFOR),
    gleam@option:option(binary()),
    binary(),
    list(segment()),
    AFOR
) -> trie_node(AFOR).
insert_multi_wildcard_segment(Node, Name, Method, Rest, Route) ->
    Child = get_or_create_multi_wildcard_child(Node),
    Updated_child = insert_into_node(Child, Method, Rest, Route),
    {trie_node,
        erlang:element(2, Node),
        erlang:element(3, Node),
        erlang:element(4, Node),
        erlang:element(5, Node),
        erlang:element(6, Node),
        {some, {Name, Updated_child}},
        erlang:element(8, Node)}.

-file("src/dream/router/trie.gleam", 359).
?DOC(" Insert an extension pattern segment and recurse into its child\n").
-spec insert_extension_segment(
    trie_node(AFOW),
    list(binary()),
    binary(),
    list(segment()),
    AFOW
) -> trie_node(AFOW).
insert_extension_segment(Node, Exts, Method, Rest, Route) ->
    Child = get_or_create_extension_child(Node, Exts),
    Updated_child = insert_into_node(Child, Method, Rest, Route),
    Updated_children = update_extension_children(
        erlang:element(8, Node),
        Exts,
        Updated_child
    ),
    {trie_node,
        erlang:element(2, Node),
        erlang:element(3, Node),
        erlang:element(4, Node),
        erlang:element(5, Node),
        erlang:element(6, Node),
        erlang:element(7, Node),
        Updated_children}.