gleamy_structures

-module(gleamy@pairing_heap).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch]).

-export([new/1, find_min/1, insert/2, merge/2, delete_min/1]).
-export_type([tree/1, heap/1]).

-type tree(HKH) :: empty | {tree, HKH, list(tree(HKH))}.

-opaque heap(HKI) :: {heap, tree(HKI), fun((HKI, HKI) -> gleam@order:order())}.

-file("/home/julian/projects/gleamy_structures/src/gleamy/pairing_heap.gleam", 18).
-spec new(fun((HKJ, HKJ) -> gleam@order:order())) -> heap(HKJ).
new(Compare) ->
    {heap, empty, Compare}.

-file("/home/julian/projects/gleamy_structures/src/gleamy/pairing_heap.gleam", 30).
-spec find_min(heap(HKO)) -> {ok, HKO} | {error, nil}.
find_min(Heap) ->
    case erlang:element(2, Heap) of
        {tree, X, _} ->
            {ok, X};

        empty ->
            {error, nil}
    end.

-file("/home/julian/projects/gleamy_structures/src/gleamy/pairing_heap.gleam", 56).
-spec merge_trees(tree(HLB), tree(HLB), fun((HLB, HLB) -> gleam@order:order())) -> tree(HLB).
merge_trees(X, Y, Compare) ->
    case {X, Y} of
        {X@1, empty} ->
            X@1;

        {empty, Y@1} ->
            Y@1;

        {{tree, Xk, Xs}, {tree, Yk, Ys}} ->
            case Compare(Xk, Yk) of
                gt ->
                    {tree, Yk, [X | Ys]};

                _ ->
                    {tree, Xk, [Y | Xs]}
            end
    end.

-file("/home/julian/projects/gleamy_structures/src/gleamy/pairing_heap.gleam", 24).
-spec insert(heap(HKL), HKL) -> heap(HKL).
insert(Heap, Key) ->
    {heap,
        merge_trees(
            {tree, Key, []},
            erlang:element(2, Heap),
            erlang:element(3, Heap)
        ),
        erlang:element(3, Heap)}.

-file("/home/julian/projects/gleamy_structures/src/gleamy/pairing_heap.gleam", 51).
-spec merge(heap(HKX), heap(HKX)) -> heap(HKX).
merge(Heap1, Heap2) ->
    Compare = erlang:element(3, Heap1),
    {heap,
        merge_trees(erlang:element(2, Heap1), erlang:element(2, Heap2), Compare),
        Compare}.

-file("/home/julian/projects/gleamy_structures/src/gleamy/pairing_heap.gleam", 68).
-spec merge_pairs(list(tree(HLF)), fun((HLF, HLF) -> gleam@order:order())) -> tree(HLF).
merge_pairs(L, Compare) ->
    case L of
        [] ->
            empty;

        [H] ->
            H;

        [H1, H2 | Hs] ->
            merge_trees(
                merge_trees(H1, H2, Compare),
                merge_pairs(Hs, Compare),
                Compare
            )
    end.

-file("/home/julian/projects/gleamy_structures/src/gleamy/pairing_heap.gleam", 40).
-spec delete_min(heap(HKS)) -> {ok, {HKS, heap(HKS)}} | {error, nil}.
delete_min(Heap) ->
    case erlang:element(2, Heap) of
        {tree, X, Xs} ->
            {ok,
                {X,
                    {heap,
                        merge_pairs(Xs, erlang:element(3, Heap)),
                        erlang:element(3, Heap)}}};

        empty ->
            {error, nil}
    end.