yog_ex

defmodule Yog.PairingHeap do
  @moduledoc """
  A [Pairing Heap](https://en.wikipedia.org/wiki/Pairing_heap) implementation of a priority queue.

  This module provides a priority queue with support for custom comparison functions,
  making it suitable for various graph algorithms like Dijkstra's, Prim's, and A*.

  Implementation inspired by [Gleamy Structures](https://github.com/schurhammer/gleamy_structures/blob/main/src/gleamy/pairing_heap.gleam)
  and [ex_algo](https://github.com/code-shoily/ex_algo/blob/main/lib/ex_algo/heap/pairing_heap.ex)

  ## Features

  - O(1) insertion
  - O(1) find-min
  - O(log n) amortized delete-min
  - Custom comparison functions for flexible ordering
  - Functional/persistent data structure

  ## Examples

      # Min-priority queue (default)
      pq = Yog.PairingHeap.new()
      |> Yog.PairingHeap.push(5)
      |> Yog.PairingHeap.push(3)
      |> Yog.PairingHeap.push(7)

      {:ok, 3, pq} = Yog.PairingHeap.pop(pq)

      # Max-priority queue with custom comparator
      pq = Yog.PairingHeap.new(fn a, b -> a >= b end)
      |> Yog.PairingHeap.push({:node, 5})
      |> Yog.PairingHeap.push({:node, 10})

      {:ok, {:node, 10}, _} = Yog.PairingHeap.pop(pq)

      # Priority queue for Dijkstra's algorithm
      pq = Yog.PairingHeap.new(fn {dist1, _}, {dist2, _} -> dist1 <= dist2 end)
      |> Yog.PairingHeap.push({0, :start})
      |> Yog.PairingHeap.push({5, :a})
      |> Yog.PairingHeap.push({3, :b})

  ## Visual Representation

  <div class="graphviz">
  graph G {
    bgcolor="transparent";
    node [shape=circle, fontname="inherit", color="#6366f1", fontcolor="#6366f1", penwidth=2];
    edge [color="#94a3b8", penwidth=1.5];

    node3 [label="3", color="#6366f1", penwidth=2, style=bold];
    node4 [label="4"];
    node5 [label="5"];
    node6 [label="6"];
    node7 [label="7"];

    node3 -- node5;
    node3 -- node4;
    node3 -- node6;
    node5 -- node7;
  }
  </div>

      iex> alias Yog.PairingHeap
      iex> pq = PairingHeap.new()
      ...> |> PairingHeap.push(3)
      ...> |> PairingHeap.push(4)
      ...> |> PairingHeap.push(5)
      ...> |> PairingHeap.push(6)
      ...> |> PairingHeap.push(7)
      iex> PairingHeap.peek(pq)
      {:ok, 3}
      iex> PairingHeap.size(pq)
      5
  """

  defmodule Node do
    @moduledoc false
    defstruct [:value, :compare_fn, children: [], size: 1]
  end

  defmodule Empty do
    @moduledoc false
    defstruct [:compare_fn, size: 0]
  end

  @type compare_fn :: (any(), any() -> boolean())
  @type t :: %Node{} | %Empty{}

  @doc """
  Creates a new empty priority queue.

  By default, uses natural ordering (min-heap for numbers).

  ## Examples

      iex> pq = Yog.PairingHeap.new()
      iex> Yog.PairingHeap.empty?(pq)
      true

      iex> pq = Yog.PairingHeap.new(fn a, b -> a >= b end)  # max-heap
      iex> Yog.PairingHeap.empty?(pq)
      true
  """
  @spec new() :: t()
  def new, do: %Empty{compare_fn: fn a, b -> a <= b end, size: 0}

  @spec new(compare_fn()) :: t()
  def new(compare_fn), do: %Empty{compare_fn: compare_fn, size: 0}

  @doc """
  Checks if the priority queue is empty.

  ## Examples

      iex> Yog.PairingHeap.empty?(Yog.PairingHeap.new())
      true

      iex> Yog.PairingHeap.empty?(Yog.PairingHeap.new()
      ...> |> Yog.PairingHeap.push(1))
      false
  """
  @spec empty?(t()) :: boolean()
  def empty?(%Empty{}), do: true
  def empty?(%Node{}), do: false

  @doc """
  Inserts a value into the priority queue.

  ## Examples

      iex> pq =
      ...>   Yog.PairingHeap.new()
      ...>   |> Yog.PairingHeap.push(5)
      ...>   |> Yog.PairingHeap.push(3)
      iex> Yog.PairingHeap.peek(pq)
      {:ok, 3}
  """
  @spec push(t(), any()) :: t()
  def push(%Empty{compare_fn: cmp}, value),
    do: %Node{value: value, children: [], compare_fn: cmp, size: 1}

  def push(%Node{compare_fn: cmp} = heap, value) do
    merge(heap, %Node{value: value, children: [], compare_fn: cmp, size: 1}, cmp)
  end

  @doc """
  Returns the minimum element without removing it.

  Returns `{:ok, value}` if the queue is not empty, `:error` otherwise.

  ## Examples

      iex> pq = Yog.PairingHeap.new() |> Yog.PairingHeap.push(5) |> Yog.PairingHeap.push(3)
      iex> Yog.PairingHeap.peek(pq)
      {:ok, 3}

      iex> Yog.PairingHeap.peek(Yog.PairingHeap.new())
      :error
  """
  @spec peek(t()) :: {:ok, any()} | :error
  def peek(%Empty{}), do: :error
  def peek(%Node{value: v}), do: {:ok, v}

  @doc """
  Removes and returns the minimum element.

  Returns `{:ok, value, new_queue}` if the queue is not empty, `:error` otherwise.

  ## Examples

      iex> pq = Yog.PairingHeap.new() |> Yog.PairingHeap.push(5) |> Yog.PairingHeap.push(3) |> Yog.PairingHeap.push(7)
      iex> {:ok, min, pq} = Yog.PairingHeap.pop(pq)
      iex> min
      3
      iex> {:ok, next_min, _} = Yog.PairingHeap.pop(pq)
      iex> next_min
      5
  """
  @spec pop(t()) :: {:ok, any(), t()} | :error
  def pop(%Empty{}), do: :error

  def pop(%Node{value: v, children: c, compare_fn: cmp}) do
    {:ok, v, combine(c, cmp)}
  end

  @doc """
  Converts a list to a priority queue.

  ## Examples

      iex> pq = Yog.PairingHeap.from_list([3, 1, 4, 1, 5])
      iex> {:ok, min, _} = Yog.PairingHeap.pop(pq)
      iex> min
      1

      iex> pq = Yog.PairingHeap.from_list([3, 1, 4, 1, 5], &Kernel.>=/2)
      iex> {:ok, max, _} = Yog.PairingHeap.pop(pq)
      iex> max
      5
  """
  @spec from_list([any()]) :: t()
  def from_list(list), do: from_list(list, fn a, b -> a <= b end)

  @spec from_list([any()], compare_fn()) :: t()
  def from_list(list, compare_fn) do
    List.foldl(list, new(compare_fn), fn x, acc -> push(acc, x) end)
  end

  @doc """
  Converts the priority queue to a sorted list.

  ## Examples

      iex> Yog.PairingHeap.new()
      ...> |> Yog.PairingHeap.push(3)
      ...> |> Yog.PairingHeap.push(1)
      ...> |> Yog.PairingHeap.push(2)
      ...> |> Yog.PairingHeap.to_list()
      [1, 2, 3]
  """
  @spec to_list(t()) :: [any()]
  def to_list(pq), do: to_list(pq, [])

  defp to_list(%Empty{}, acc), do: Enum.reverse(acc)

  defp to_list(pq, acc) do
    {:ok, v, new_pq} = pop(pq)
    to_list(new_pq, [v | acc])
  end

  @doc """
  Returns the number of elements in the queue.

  ## Examples

      iex> Yog.PairingHeap.new()
      ...> |> Yog.PairingHeap.push(1)
      ...> |> Yog.PairingHeap.push(2)
      ...> |> Yog.PairingHeap.size()
      2
  """
  @spec size(t()) :: non_neg_integer()
  def size(%Empty{size: s}), do: s
  def size(%Node{size: s}), do: s

  @doc """
  Merges two priority queues.

  The combined queue will use the comparison function of the first queue.

  ## Examples

      iex> pq1 = Yog.PairingHeap.new() |> Yog.PairingHeap.push(3)
      iex> pq2 = Yog.PairingHeap.new() |> Yog.PairingHeap.push(1) |> Yog.PairingHeap.push(5)
      iex> pq = Yog.PairingHeap.merge(pq1, pq2)
      iex> Yog.PairingHeap.to_list(pq)
      [1, 3, 5]
  """
  @spec merge(t(), t()) :: t()
  def merge(%Empty{}, h2), do: h2
  def merge(h1, %Empty{}), do: h1

  def merge(%Node{compare_fn: cmp} = h1, %Node{} = h2) do
    merge(h1, h2, cmp)
  end

  # =============================================================================
  # Private Helper Functions
  # =============================================================================

  defp merge(h, %Empty{}, _cmp), do: h
  defp merge(%Empty{}, h, _cmp), do: h

  defp merge(
         %Node{value: v1, children: c1, compare_fn: cmp, size: s1} = h1,
         %Node{value: v2, children: c2, size: s2} = h2,
         cmp
       ) do
    if cmp.(v1, v2) do
      # v1 is new root, h2 becomes a child
      %Node{value: v1, children: [h2 | c1], compare_fn: cmp, size: s1 + s2}
    else
      # v2 is new root, h1 becomes a child
      %Node{value: v2, children: [h1 | c2], compare_fn: cmp, size: s1 + s2}
    end
  end

  defp combine([], cmp), do: %Empty{compare_fn: cmp, size: 0}
  defp combine([h], _cmp), do: h
  defp combine([h1, h2], cmp), do: merge(h1, h2, cmp)

  defp combine([h1, h2 | rest], cmp) do
    merge(merge(h1, h2, cmp), combine(rest, cmp), cmp)
  end
end

defimpl Inspect, for: Yog.PairingHeap.Node do
  import Inspect.Algebra

  def inspect(heap, opts) do
    {:ok, val} = Yog.PairingHeap.peek(heap)

    concat([
      "#Yog.PairingHeap<size: ",
      to_string(Yog.PairingHeap.size(heap)),
      ", peek: ",
      to_doc(val, opts),
      ">"
    ])
  end
end

defimpl Inspect, for: Yog.PairingHeap.Empty do
  def inspect(_heap, _opts) do
    "#Yog.PairingHeap<empty>"
  end
end