graph

-module(graph@internal@heap).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch]).

-export([new/1, min/1, add/2, pop_min/1]).
-export_type([heap/1, heap_repr/1]).

-opaque heap(GHV) :: {heap,
        heap_repr(GHV),
        fun((GHV, GHV) -> gleam@order:order())}.

-type heap_repr(GHW) :: empty | {cons, GHW, list(heap_repr(GHW))}.

-spec new(fun((GHX, GHX) -> gleam@order:order())) -> heap(GHX).
new(Compare) ->
    {heap, empty, Compare}.

-spec min(heap(GIH)) -> {ok, GIH} | {error, nil}.
min(Heap) ->
    case Heap of
        {heap, empty, _} ->
            {error, nil};

        {heap, {cons, Min, _}, _} ->
            {ok, Min}
    end.

-spec merge(
    heap_repr(GIL),
    heap_repr(GIL),
    fun((GIL, GIL) -> gleam@order:order())
) -> heap_repr(GIL).
merge(One, Other, Compare) ->
    case {One, Other} of
        {empty, Res} ->
            Res;

        {Res, empty} ->
            Res;

        {{cons, Min_one, Rest_one}, {cons, Min_other, Rest_other}} ->
            case Compare(Min_one, Min_other) of
                lt ->
                    {cons, Min_one, [Other | Rest_one]};

                eq ->
                    {cons, Min_one, [Other | Rest_one]};

                gt ->
                    {cons, Min_other, [One | Rest_other]}
            end
    end.

-spec add(heap(GHZ), GHZ) -> heap(GHZ).
add(Heap, Item) ->
    {heap, Heap@1, Compare} = Heap,
    Heap@2 = merge(Heap@1, {cons, Item, []}, Compare),
    {heap, Heap@2, Compare}.

-spec merge_all(list(heap_repr(GIP)), fun((GIP, GIP) -> gleam@order:order())) -> heap_repr(GIP).
merge_all(Heaps, Compare) ->
    case Heaps of
        [] ->
            empty;

        [Heap] ->
            Heap;

        [One_heap, Other_heap | Heaps@1] ->
            _pipe = merge(One_heap, Other_heap, Compare),
            merge(_pipe, merge_all(Heaps@1, Compare), Compare)
    end.

-spec pop_min(heap(GIC)) -> {ok, {GIC, heap(GIC)}} | {error, nil}.
pop_min(Heap) ->
    case Heap of
        {heap, empty, _} ->
            {error, nil};

        {heap, {cons, Min, Rest}, Compare} ->
            Remaining = merge_all(Rest, Compare),
            {ok, {Min, {heap, Remaining, Compare}}}
    end.