-module(trie).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/trie.gleam").
-export([fold/3, get/2, has_path/2, map/2, new/0, delete/2, insert/3, from_list/1, paths/1, singleton/2, size/1, is_empty/1, subtrie/2, to_list/1, update/3, values/1]).
-export_type([trie/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.

-opaque trie(HRQ, HRR) :: {trie,
        gleam@option:option(HRR),
        gleam@dict:dict(HRQ, trie(HRQ, HRR))}.

-file("src/trie.gleam", 43).
?DOC(
    " Exactly same behaviour as delete but returns `None` if the tree is empty as a\n"
    " result of the deletion.\n"
).
-spec do_delete(trie(HRZ, HSA), list(HRZ)) -> gleam@option:option(trie(HRZ, HSA)).
do_delete(Trie, Path) ->
    case {Path, Trie} of
        {[], {trie, _, Children_map}} ->
            case maps:size(Children_map) of
                0 ->
                    none;

                _ ->
                    {some, {trie, none, Children_map}}
            end;

        {[First | Rest], {trie, Entry, Children_map@1}} ->
            New_children = case gleam_stdlib:map_get(Children_map@1, First) of
                {error, _} ->
                    Children_map@1;

                {ok, Child} ->
                    case do_delete(Child, Rest) of
                        none ->
                            gleam@dict:delete(Children_map@1, First);

                        {some, Trie@1} ->
                            gleam@dict:insert(Children_map@1, First, Trie@1)
                    end
            end,
            case {Entry, maps:size(New_children)} of
                {none, 0} ->
                    none;

                {_, _} ->
                    {some, {trie, Entry, New_children}}
            end
    end.

-file("src/trie.gleam", 80).
?DOC(
    " Combines all the trie's values into a single one by calling a given function on each one.\n"
    "\n"
    " The function takes as input the accumulator, the path of a value and the corresponding value.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > [#([1, 2], 10), #([1], 1)]\n"
    " > |> from_list\n"
    " > |> fold(from: 0, with: fn(sum, _, value) { sum + value })\n"
    " 11\n"
    " ```\n"
).
-spec fold(trie(HSH, HSI), HSL, fun((HSL, list(HSH), HSI) -> HSL)) -> HSL.
fold(Trie, Initial, Fun) ->
    gleam@dict:fold(
        erlang:element(3, Trie),
        begin
            _pipe = erlang:element(2, Trie),
            _pipe@1 = gleam@option:map(
                _pipe,
                fun(_capture) -> Fun(Initial, [], _capture) end
            ),
            gleam@option:unwrap(_pipe@1, Initial)
        end,
        fun(Acc, First, Trie@1) ->
            fold(
                Trie@1,
                Acc,
                fun(Acc@1, Rest, Value) -> Fun(Acc@1, [First | Rest], Value) end
            )
        end
    ).

-file("src/trie.gleam", 133).
?DOC(
    " Fetches a value from a trie for a given path.\n"
    " If a value is present at the given path it returns it wrapped in an `Ok`,\n"
    " otherwise it returns `Error(Nil)`.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > new()\n"
    " > |> get(at: [1, 2])\n"
    " Result(Nil)\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " > singleton([1, 2], \"a\")\n"
    " > |> get(at: [1, 2])\n"
    " Ok(\"a\")\n"
    " ```\n"
).
-spec get(trie(HST, HSU), list(HST)) -> {ok, HSU} | {error, nil}.
get(From, Path) ->
    case {Path, From} of
        {[], {trie, none, _}} ->
            {error, nil};

        {[], {trie, {some, Value}, _}} ->
            {ok, Value};

        {[First | Rest], {trie, _, Children_map}} ->
            _pipe = Children_map,
            _pipe@1 = gleam_stdlib:map_get(_pipe, First),
            case _pipe@1 of
                {ok, X} ->
                    get(X, Rest);

                {error, E} ->
                    {error, E}
            end
    end.

-file("src/trie.gleam", 160).
?DOC(
    " Determines wether a trie contains a value associated with the given path.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > singleton([1, 2], \"a\")\n"
    " > |> has_path([1, 2])\n"
    " True\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " > singleton([1, 2], \"a\")\n"
    " > |> has_path([1])\n"
    " False\n"
    " ```\n"
).
-spec has_path(trie(HTA, any()), list(HTA)) -> boolean().
has_path(Trie, Path) ->
    case get(Trie, Path) of
        {ok, _} ->
            true;

        {error, _} ->
            false
    end.

-file("src/trie.gleam", 237).
?DOC(
    " Updates all the values in a given trie by calling a function on each value.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > [#([1, 2], \"a\"), #([1], \"b\")]\n"
    " > |> from_list\n"
    " > |> map(fn(s) { s <> \"!\" })\n"
    " > |> to_list\n"
    " [#([1, 2], \"a!\"), #([1], \"b!\")]\n"
    " ```\n"
).
-spec map(trie(HTQ, HTR), fun((HTR) -> HTU)) -> trie(HTQ, HTU).
map(Trie, Fun) ->
    {trie,
        gleam@option:map(erlang:element(2, Trie), Fun),
        gleam@dict:map_values(
            erlang:element(3, Trie),
            fun(_, T) -> map(T, Fun) end
        )}.

-file("src/trie.gleam", 254).
?DOC(
    " Creates a new empty trie.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > new()\n"
    " > |> to_list\n"
    " []\n"
    " ```\n"
).
-spec new() -> trie(any(), any()).
new() ->
    {trie, none, maps:new()}.

-file("src/trie.gleam", 35).
?DOC(
    " Deletes from a trie the value associated with a given path.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > [#([1, 2], \"a\"), #([1], \"b\")]\n"
    " > |> from_list\n"
    " > |> delete(at: [1, 2])\n"
    " > |> to_list\n"
    " [#([1], \"b\")]\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " > new()\n"
    " > |> delete(at: [1, 2])\n"
    " > |> to_list\n"
    " []\n"
    " ```\n"
).
-spec delete(trie(HRS, HRT), list(HRS)) -> trie(HRS, HRT).
delete(Trie, Path) ->
    _pipe = do_delete(Trie, Path),
    gleam@option:unwrap(_pipe, new()).

-file("src/trie.gleam", 188).
?DOC(
    " Inserts a value in a trie at a given path. If there already is a value\n"
    " at the given path it is replaced by the new one.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > new()\n"
    " > |> insert(at: [1, 2], value: \"a\")\n"
    " > |> insert(at: [1], value: \"b\")\n"
    " > |> to_list\n"
    " [#([1, 2], \"a\"), #([1], \"b\")]\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " > new()\n"
    " > |> insert(at: [1, 2], value: \"a\")\n"
    " > |> insert(at: [1, 2], value: \"b\")\n"
    " > |> to_list\n"
    " [#([1, 2], \"b\")]\n"
    " ```\n"
).
-spec insert(trie(HTF, HTG), list(HTF), HTG) -> trie(HTF, HTG).
insert(Trie, Path, Value) ->
    case {Path, Trie} of
        {[], {trie, _, Children_map}} ->
            {trie, {some, Value}, Children_map};

        {[First | Rest], {trie, Entry, Children_map@1}} ->
            _pipe = gleam_stdlib:map_get(Children_map@1, First),
            _pipe@1 = gleam@result:unwrap(_pipe, new()),
            _pipe@2 = insert(_pipe@1, Rest, Value),
            _pipe@3 = gleam@dict:insert(Children_map@1, First, _pipe@2),
            {trie, Entry, _pipe@3}
    end.

-file("src/trie.gleam", 109).
?DOC(
    " Creates a new trie from a list of path-value pairs.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > [#([1, 2], \"a\"), #([1], \"b\")]\n"
    " > |> from_list\n"
    " > |> to_list\n"
    " [#([1, 2], \"a\"), #([1], \"b\")]\n"
    " ```\n"
).
-spec from_list(list({list(HSN), HSP})) -> trie(HSN, HSP).
from_list(List) ->
    gleam@list:fold(
        List,
        new(),
        fun(Trie, Pair) ->
            insert(Trie, erlang:element(1, Pair), erlang:element(2, Pair))
        end
    ).

-file("src/trie.gleam", 278).
?DOC(
    " Gets a list of all the valid paths in the trie. That is all the paths associated with a value.\n"
    "\n"
    " Tries are not ordered so the paths are not returned in any specific order.\n"
    " Do not write code that relies on the order paths are returned by this function\n"
    " as it may change in later versions of the library.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > [#([1, 2], \"a\"), #([1], \"b\")]\n"
    " > |> from_list\n"
    " > |> paths\n"
    " [[1, 2], [1]]\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " > new()\n"
    " > |> paths\n"
    " []\n"
    " ```\n"
).
-spec paths(trie(HUB, any())) -> list(list(HUB)).
paths(Trie) ->
    fold(Trie, [], fun(Rest, Path, _) -> [Path | Rest] end).

-file("src/trie.gleam", 292).
?DOC(
    " Creates a new trie with a single value associated to the given path.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > singleton([1, 2], \"a\")\n"
    " > |> to_list\n"
    " [#([1, 2], \"a\")]\n"
    " ```\n"
).
-spec singleton(list(HUH), HUJ) -> trie(HUH, HUJ).
singleton(Path, Value) ->
    insert(new(), Path, Value).

-file("src/trie.gleam", 307).
?DOC(
    " Gets the number of elements in the trie.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > [#([1, 2], \"a\"), #([1], \"b\")]\n"
    " > |> from_list\n"
    " > |> size\n"
    " 2\n"
    " ```\n"
).
-spec size(trie(any(), any())) -> integer().
size(Trie) ->
    fold(Trie, 0, fun(Acc, _, _) -> Acc + 1 end).

-file("src/trie.gleam", 221).
?DOC(
    " Determines wether or not the trie is empty.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > new()\n"
    " > |> is_empty\n"
    " True\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " > singleton([1, 2], \"a\")\n"
    " > |> is_empty\n"
    " False\n"
    " ```\n"
).
-spec is_empty(trie(any(), any())) -> boolean().
is_empty(Trie) ->
    size(Trie) =:= 0.

-file("src/trie.gleam", 323).
?DOC(
    " Gets the subtrie whose elements all share a common given prefix.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > [#([1, 2, 3], \"a\"), #([1, 2, 4, 5], \"b\"), #([3, 4], \"c\")]\n"
    " > |> from_list\n"
    " > |> subtrie(at: [1, 2])\n"
    " > |> to_list\n"
    " [#([1, 2, 3], \"a\"), #([1, 2, 4, 5], \"b\")]\n"
    " ```\n"
).
-spec subtrie(trie(HUQ, HUR), list(HUQ)) -> {ok, trie(HUQ, HUR)} | {error, nil}.
subtrie(Trie, Prefix) ->
    case {Prefix, Trie} of
        {[], _} ->
            {ok, Trie};

        {[First | Rest], {trie, _, Children_map}} ->
            _pipe = Children_map,
            _pipe@1 = gleam_stdlib:map_get(_pipe, First),
            _pipe@2 = case _pipe@1 of
                {ok, X} ->
                    subtrie(X, Rest);

                {error, E} ->
                    {error, E}
            end,
            case _pipe@2 of
                {ok, X@1} ->
                    {ok,
                        begin
                            _pipe@3 = maps:new(),
                            _pipe@4 = gleam@dict:insert(_pipe@3, First, X@1),
                            {trie, none, _pipe@4}
                        end};

                {error, E@1} ->
                    {error, E@1}
            end
    end.

-file("src/trie.gleam", 354).
?DOC(
    " Turns a trie into a list of path-value pairs.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > singleton([1, 2], \"a\")\n"
    " > |> to_list\n"
    " [#([1, 2], \"a\")]\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " > new()\n"
    " > |> to_list\n"
    " []\n"
    " ```\n"
).
-spec to_list(trie(HUZ, HVA)) -> list({list(HUZ), HVA}).
to_list(Trie) ->
    fold(Trie, [], fun(Rest, Path, Value) -> [{Path, Value} | Rest] end).

-file("src/trie.gleam", 401).
?DOC(
    " Exactly same behaviour as update but returns `None` if the tree is empty as a\n"
    " result of the (possible) deletion.\n"
).
-spec do_update(
    trie(HVO, HVP),
    list(HVO),
    fun((gleam@option:option(HVP)) -> gleam@option:option(HVP))
) -> gleam@option:option(trie(HVO, HVP)).
do_update(Trie, Path, Fun) ->
    case {Path, Trie} of
        {[], {trie, Entry, Children_map}} ->
            case {Fun(Entry), maps:size(Children_map)} of
                {none, 0} ->
                    none;

                {New_entry, _} ->
                    {some, {trie, New_entry, Children_map}}
            end;

        {[First | Rest], {trie, Entry@1, Children_map@1}} ->
            New_children = case gleam_stdlib:map_get(Children_map@1, First) of
                {ok, Child} ->
                    case do_update(Child, Rest, Fun) of
                        none ->
                            gleam@dict:delete(Children_map@1, First);

                        {some, New_child} ->
                            gleam@dict:insert(Children_map@1, First, New_child)
                    end;

                {error, _} ->
                    case Fun(none) of
                        none ->
                            Children_map@1;

                        {some, Value} ->
                            gleam@dict:insert(
                                Children_map@1,
                                First,
                                singleton(Rest, Value)
                            )
                    end
            end,
            case {Entry@1, maps:size(New_children)} of
                {none, 0} ->
                    none;

                {_, _} ->
                    {some, {trie, Entry@1, New_children}}
            end
    end.

-file("src/trie.gleam", 389).
?DOC(
    " Updates the value associated with a path applying it the given function.\n"
    " If there is no value associated with the given path the function is passed `None`.\n"
    "\n"
    " If the function returns `None` any value associated with the path is deleted from the trie.\n"
    " If the function returns `Some(value)` then the new value is associated to the given path.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > singleton([1, 2], \"a\")\n"
    " > |> update(at: [1, 2], with: fn(n) { n |> option.map(fn(_) { \"b\" }) })\n"
    " > |> to_list\n"
    " [#([1, 2], \"b\")]\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " > singleton([1, 2], \"a\")\n"
    " > |> update(at: [1, 2], with: fn(_) { None })\n"
    " > |> to_list\n"
    " []\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " > singleton([1, 2], \"a\")\n"
    " > |> update(at: [1], with: fn(_) { Some(\"b\") })\n"
    " > |> to_list\n"
    " [#([1, 2], \"a\"), #([1], \"b\")]\n"
    " ```\n"
).
-spec update(
    trie(HVF, HVG),
    list(HVF),
    fun((gleam@option:option(HVG)) -> gleam@option:option(HVG))
) -> trie(HVF, HVG).
update(Trie, Path, Fun) ->
    _pipe = do_update(Trie, Path, Fun),
    gleam@option:unwrap(_pipe, new()).

-file("src/trie.gleam", 458).
?DOC(
    " Gets a list of all the values in a given trie.\n"
    "\n"
    " Tries are not ordered so the values are not returned in any specific order.\n"
    " Do not write code that relies on the order values are returned by this function\n"
    " as it may change in later versions of the library.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " > [#([1, 2], \"a\"), #([1], \"b\")]\n"
    " > |> from_list\n"
    " > |> values\n"
    " [\"a\", \"b\"]\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " > new()\n"
    " > |> values\n"
    " []\n"
    " ```\n"
).
-spec values(trie(any(), HVZ)) -> list(HVZ).
values(Trie) ->
    fold(Trie, [], fun(Values, _, Value) -> [Value | Values] end).