priorityq

-module(priorityq).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch]).

-export([new/1, is_empty/1, size/1, peek/1, push/2, from_list/2, pop/1]).
-export_type([priority_queue/1, pairing_heap/1, pairing_tree/1]).

-opaque priority_queue(FLP) :: {priority_queue,
        pairing_heap(FLP),
        fun((FLP, FLP) -> gleam@order:order())}.

-type pairing_heap(FLQ) :: empty | {non_empty, pairing_tree(FLQ)}.

-type pairing_tree(FLR) :: {pairing_tree,
        FLR,
        list(pairing_tree(FLR)),
        integer()}.

-spec new(fun((FLT, FLT) -> gleam@order:order())) -> priority_queue(FLT).
new(Cmp) ->
    {priority_queue, empty, Cmp}.

-spec from_pairing_tree(
    pairing_tree(FMA),
    fun((FMA, FMA) -> gleam@order:order())
) -> priority_queue(FMA).
from_pairing_tree(Tree, Cmp) ->
    {priority_queue, {non_empty, Tree}, Cmp}.

-spec one(FME, fun((FME, FME) -> gleam@order:order())) -> priority_queue(FME).
one(Val, Cmp) ->
    {priority_queue, {non_empty, {pairing_tree, Val, [], 1}}, Cmp}.

-spec is_empty(priority_queue(any())) -> boolean().
is_empty(Pq) ->
    erlang:element(2, Pq) =:= empty.

-spec size(priority_queue(any())) -> integer().
size(Pq) ->
    case erlang:element(2, Pq) of
        empty ->
            0;

        {non_empty, Tree} ->
            erlang:element(4, Tree)
    end.

-spec peek(priority_queue(FML)) -> gleam@option:option(FML).
peek(Pq) ->
    case erlang:element(2, Pq) of
        empty ->
            none;

        {non_empty, Tree} ->
            {some, erlang:element(2, Tree)}
    end.

-spec merge(priority_queue(FMO), priority_queue(FMO)) -> priority_queue(FMO).
merge(Pq1, Pq2) ->
    case erlang:element(3, Pq1) =:= erlang:element(3, Pq2) of
        false ->
            erlang:error(#{gleam_error => panic,
                    message => <<"inconsistent cmp function"/utf8>>,
                    module => <<"priorityq"/utf8>>,
                    function => <<"merge"/utf8>>,
                    line => 118});

        true ->
            case {erlang:element(2, Pq1), erlang:element(2, Pq2)} of
                {empty, _} ->
                    Pq2;

                {_, empty} ->
                    Pq1;

                {{non_empty, Tree1}, {non_empty, Tree2}} ->
                    New_size = erlang:element(4, Tree1) + erlang:element(
                        4,
                        Tree2
                    ),
                    case (erlang:element(3, Pq1))(
                        erlang:element(2, Tree1),
                        erlang:element(2, Tree2)
                    ) of
                        gt ->
                            {priority_queue,
                                {non_empty,
                                    {pairing_tree,
                                        erlang:element(2, Tree1),
                                        [Tree2 | erlang:element(3, Tree1)],
                                        New_size}},
                                erlang:element(3, Pq1)};

                        _ ->
                            {priority_queue,
                                {non_empty,
                                    {pairing_tree,
                                        erlang:element(2, Tree2),
                                        [Tree1 | erlang:element(3, Tree2)],
                                        New_size}},
                                erlang:element(3, Pq1)}
                    end
            end
    end.

-spec push(priority_queue(FMS), FMS) -> priority_queue(FMS).
push(Pq, Val) ->
    merge(one(Val, erlang:element(3, Pq)), Pq).

-spec from_list(list(FLW), fun((FLW, FLW) -> gleam@order:order())) -> priority_queue(FLW).
from_list(Ls, Cmp) ->
    _pipe = new(Cmp),
    gleam@list:fold(Ls, _pipe, fun push/2).

-spec merge_pairs(
    list(pairing_tree(FMY)),
    fun((FMY, FMY) -> gleam@order:order())
) -> priority_queue(FMY).
merge_pairs(Trees, Cmp) ->
    case Trees of
        [] ->
            {priority_queue, empty, Cmp};

        [Tree] ->
            from_pairing_tree(Tree, Cmp);

        [Tree1, Tree2 | Rest] ->
            _pipe = merge(
                from_pairing_tree(Tree1, Cmp),
                from_pairing_tree(Tree2, Cmp)
            ),
            merge(_pipe, merge_pairs(Rest, Cmp))
    end.

-spec pop(priority_queue(FMV)) -> priority_queue(FMV).
pop(Pq) ->
    case erlang:element(2, Pq) of
        empty ->
            Pq;

        {non_empty, Tree} ->
            merge_pairs(erlang:element(3, Tree), erlang:element(3, Pq))
    end.