graph

-module(graph@internal@heap).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/graph/internal/heap.gleam").
-export([new/1, min/1, add/2, pop_min/1]).
-export_type([heap/1, heap_repr/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(false).

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

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

-file("src/graph/internal/heap.gleam", 12).
?DOC(false).
-spec new(fun((ELC, ELC) -> gleam@order:order())) -> heap(ELC).
new(Compare) ->
    {heap, empty, Compare}.

-file("src/graph/internal/heap.gleam", 32).
?DOC(false).
-spec min(heap(ELM)) -> {ok, ELM} | {error, nil}.
min(Heap) ->
    case Heap of
        {heap, empty, _} ->
            {error, nil};

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

-file("src/graph/internal/heap.gleam", 39).
?DOC(false).
-spec merge(
    heap_repr(ELQ),
    heap_repr(ELQ),
    fun((ELQ, ELQ) -> gleam@order:order())
) -> heap_repr(ELQ).
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.

-file("src/graph/internal/heap.gleam", 16).
?DOC(false).
-spec add(heap(ELE), ELE) -> heap(ELE).
add(Heap, Item) ->
    {heap, Heap@1, Compare} = Heap,
    Heap@2 = merge(Heap@1, {cons, Item, []}, Compare),
    {heap, Heap@2, Compare}.

-file("src/graph/internal/heap.gleam", 54).
?DOC(false).
-spec merge_all(list(heap_repr(ELU)), fun((ELU, ELU) -> gleam@order:order())) -> heap_repr(ELU).
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.

-file("src/graph/internal/heap.gleam", 22).
?DOC(false).
-spec pop_min(heap(ELH)) -> {ok, {ELH, heap(ELH)}} | {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.