defmodule PairingHeap do
  @readme "README.md"
  @external_resource @readme
  @moduledoc_readme @readme
                    |> File.read!()
                    |> String.split("<!-- END HEADER -->")
                    |> Enum.fetch!(1)
                    |> String.trim()

  @moduledoc """
  #{@moduledoc_readme}
  """

  defstruct root: :empty, size: 0, mode: nil, ordered?: nil

  alias PairingHeap.Node

  @type key() :: any()
  @type value() :: any()
  @type pair() :: {key(), value()}
  @type mode() :: :min | :max | {:min, module()} | {:max, module()}

  @type t :: %PairingHeap{
          root: :empty | Node.t(),
          size: non_neg_integer(),
          mode: mode(),
          ordered?: Node.ordered_fn()
        }

  @doc """
  Return an empty heap with the given `mode`.

  The `mode` can be one of

    * `:min` - a _min-heap_, where keys are compared with `&<=/2`
    * `:max` - a _max-heap_, where keys are compared with `&>=/2`
    * `{:min | :max, module}` - a min or max heap, where the `module` must
      implement a `compare` funciton with signature `(any, any -> :lt | :eq | :gt)`

  ## Examples

      iex> PairingHeap.new(:min)
      #PairingHeap<root: :empty, size: 0, mode: :min>
  """
  @spec new(mode()) :: t()
  def new(mode) do
    %PairingHeap{
      root: :empty,
      size: 0,
      mode: mode,
      ordered?: to_ordered_fn(mode)
    }
  end

  @doc """
  Return a heap with the given `mode` and insert each key-value pair in the
  given `list`.

  The `mode` can be one of

    * `:min` - a _min-heap_, where keys are compared with `&<=/2`
    * `:max` - a _max-heap_, where keys are compared with `&>=/2`
    * `{:min | :max, module}` - a min or max heap, where the `module` must
      implement a `compare` funciton with signature `(any, any -> :lt | :eq | :gt)`

  ## Examples

      iex> PairingHeap.new(:min, [{2, :b}, {1, :a}])
      #PairingHeap<root: {1, :a}, size: 2, mode: :min>
  """
  @spec new(mode(), [pair()]) :: t
  def new(mode, []), do: new(mode)

  def new(mode, [{_, _} | _] = list) do
    Enum.reduce(list, new(mode), fn {key, value}, heap ->
      put(heap, key, value)
    end)
  end

  # Generates the `ordered?` function. If `ordered?.(key1, key2)` is true,
  # then the heap property is satisfied if a node with key `key1` is a parent of
  # a ndoe with key `key2`.
  @spec to_ordered_fn(mode()) :: Node.ordered_fn()
  defp to_ordered_fn(:min), do: to_node_fn(&<=/2)
  defp to_ordered_fn(:max), do: to_node_fn(&>=/2)

  defp to_ordered_fn({:min, module}) when is_atom(module),
    do: to_node_fn(&(module.compare(&1, &2) != :gt))

  defp to_ordered_fn({:min, module}) when is_atom(module),
    do: to_node_fn(&(module.compare(&1, &2) != :lt))

  # Lift a function of two key to a function of two Nodes.
  @spec to_node_fn((key(), key() -> boolean())) :: Node.ordered_fn()
  defp to_node_fn(key_fn) do
    fn %Node{item: {key1, _}}, %Node{item: {key2, _}} ->
      key_fn.(key1, key2)
    end
  end

  @doc """
  Return `true` if the heap is empty, and `false` otherwise.

  ## Examples

      iex> PairingHeap.new(:min) |> PairingHeap.empty?()
      true
  """
  @spec empty?(t()) :: boolean()
  def empty?(%PairingHeap{root: :empty} = _heap), do: true
  def empty?(%PairingHeap{root: %PairingHeap.Node{}} = _heap), do: false

  @doc """
  Insert a new key and value to the heap and return the updated heap.

  ## Examples

      iex> PairingHeap.new(:min) |> PairingHeap.put(1, :a)
      #PairingHeap<root: {1, :a}, size: 1, mode: :min>
  """
  @spec put(t(), key(), value()) :: t()
  def put(%PairingHeap{root: :empty, size: 0} = heap, key, value) do
    %{heap | root: Node.new({key, value}, []), size: 1}
  end

  def put(
        %PairingHeap{root: %Node{} = node, size: size, ordered?: ordered?} = heap,
        key,
        value
      ) do
    %{
      heap
      | root: Node.merge(Node.new({key, value}, []), node, ordered?),
        size: size + 1
    }
  end

  @doc """
  Return the root key-value pair in the heap without modifying the heap.

  If the heap is non-empty, this returns `{:ok, {key, value}}`. If the heap is empty,
  `:error` is returned.

  ## Examples

      iex> PairingHeap.new(:min, [{1, :a}]) |> PairingHeap.peek()
      {:ok, {1, :a}}
  """
  @spec peek(t()) :: {:ok, pair()} | :error
  def peek(%PairingHeap{root: :empty} = _heap), do: :error
  def peek(%PairingHeap{root: %Node{item: {key, value}}} = _heap), do: {:ok, {key, value}}

  @doc """
  Return the root key-value pair in the heap, as well as the updated heap after
  the root is removed.

  If the heap is non-empty, this returns `{:ok, {key, value}, heap}`. If the heap
  is empty, `:error` is returned.

  ## Examples

      iex> {:ok, {key, value}, heap} =
      ...>   PairingHeap.new(:min, [{1, :a}])
      ...>   |> PairingHeap.pop()
      iex> {key, value}
      {1, :a}
      iex> heap
      #PairingHeap<root: :empty, size: 0, mode: :min>
  """
  @spec pop(t()) :: {:ok, pair(), t()} | :error
  def pop(%PairingHeap{root: :empty}), do: :error

  def pop(
        %PairingHeap{
          root: %Node{item: {key, value}, children: children},
          size: size,
          ordered?: ordered?
        } = heap
      ) do
    heap =
      case children do
        [] -> %{heap | root: :empty, size: 0}
        [_ | _] -> %{heap | root: Node.merge(children, ordered?), size: size - 1}
      end

    {:ok, {key, value}, heap}
  end

  @doc """
  Return the size of the heap, the total number of nodes.

  ## Examples

      iex> PairingHeap.new(:min, [{1, :a}]) |> PairingHeap.size()
      1
  """
  @spec size(t()) :: non_neg_integer()
  def size(%PairingHeap{size: size} = _heap), do: size

  @doc """
  Return the first `n` key-value pairs from the heap and the final state of the heap.

  If the heap `size` is less than `n`, all key-value pairs are returned along with
  an empty heap.

  ## Examples

      iex> {pairs, heap} =
      ...>   PairingHeap.new(:min, [{3, :c}, {1, :a}, {2, :b}])
      ...>   |> PairingHeap.pull(2)
      iex> pairs
      [{1, :a}, {2, :b}]
      iex> heap
      #PairingHeap<root: {3, :c}, size: 1, mode: :min>
  """
  @spec pull(t(), non_neg_integer()) :: {[pair()], t()}
  def pull(heap, n) when is_integer(n) and n >= 0 do
    {data, heap} = pull(heap, n, [])
    {Enum.reverse(data), heap}
  end

  defp pull(heap, 0, acc), do: {acc, heap}

  defp pull(%PairingHeap{} = heap, n, acc) do
    case pop(heap) do
      {:ok, {key, value}, heap} ->
        pull(heap, n - 1, [{key, value} | acc])

      :error ->
        {acc, heap}
    end
  end

  @doc """
  Merge two heaps into a single heap.

  An exception will be raised if the modes of the two heaps are not identical.

  ## Examples

      iex> PairingHeap.merge(
      ...>   PairingHeap.new(:min, [{1, :a}]),
      ...>   PairingHeap.new(:min, [{2, :b}])
      ...> )
      #PairingHeap<root: {1, :a}, size: 2, mode: :min>
  """
  @spec merge(t(), t()) :: t()
  def merge(%PairingHeap{mode: m1}, %PairingHeap{mode: m2}) when m1 != m2 do
    # TODO: Improve this error message
    raise ArgumentError, message: "when merging heaps, the modes must match"
  end

  def merge(%PairingHeap{root: :empty} = heap, %PairingHeap{root: :empty}), do: heap
  def merge(%PairingHeap{root: %Node{}} = heap, %PairingHeap{root: :emtpy}), do: heap
  def merge(%PairingHeap{root: :empty}, %PairingHeap{root: %Node{}} = heap), do: heap

  def merge(
        %PairingHeap{root: node1, size: size1, ordered?: ordered?} = heap,
        %PairingHeap{root: node2, size: size2}
      ) do
    %{heap | root: Node.merge([node1, node2], ordered?), size: size1 + size2}
  end

  @doc """
  Merge a list of one or more heaps into a single heap.

  An exception will be raised if the modes of the heaps are not identical.

  ## Examples

      iex> PairingHeap.merge([
      ...>   PairingHeap.new(:min, [{1, :a}]),
      ...>   PairingHeap.new(:min, [{2, :b}])
      ...> ])
      #PairingHeap<root: {1, :a}, size: 2, mode: :min>
  """
  @spec merge([t]) :: t
  def merge([heap] = _heaps), do: heap
  def merge([heap1, heap2]), do: merge(heap1, heap2)
  def merge([heap1, heap2 | rest]), do: merge(merge(heap1, heap2), merge(rest))

  @doc """
  Retrun `true` if the `heap` contains the key-value `pair`, and `false`
  otherwise.

  ## Examples

      iex> heap = PairingHeap.new(:min, [{3, :c}, {1, :a}, {2, :b}])
      iex> heap |> PairingHeap.member?({2, :b})
      true
  """
  @spec member?(t(), pair()) :: boolean()
  def member?(%PairingHeap{root: :empty} = _heap, _pair), do: false

  def member?(
        %PairingHeap{root: %Node{} = node, ordered?: ordered?} = _heap,
        {_, _} = pair
      ) do
    Node.member?(node, pair, ordered?)
  end

  @doc """
  Return the list of items in the heap.

  While the head of the list will be the item in the root node of the heap,
  there is not guarantee that the remaining items will be in key order. This
  funciton runs in `O(n)` time and is faster than repeatedly calling `pop/1`.

  ## Examples

      iex> heap = PairingHeap.new(:min, [{3, :c}, {1, :a}, {2, :b}])
      iex> PairingHeap.dump(heap)
      [{1, :a}, {2, :b}, {3, :c}]
  """
  @spec dump(t()) :: [pair()]
  def dump(%PairingHeap{root: :empty}), do: []
  def dump(%PairingHeap{root: %Node{} = node}), do: Node.dump(node)
end