defmodule Runbox.Utils.TopologySort do
  @moduledoc """
  Provides topology sorting capabilities.
  """

  @doc """
  Sort the given network by its topology.

  The network is given in the form of a list with elements `{node, subs}` where subs is a list of
  nodes the node is connected to. The function returns list of nodes sorted by the topology.

  The sort is stable - original ordering of the elements is maintained where possible.
  """
  @spec sort(network :: [{node, [id]}], id_fun :: (node -> id)) ::
          {:ok, sorted_network :: [node]} | {:error, :loop}
        when node: var, id: var
  def sort(network, id_fun \\ & &1) do
    network = Enum.map(network, fn {node, subs} -> {id_fun.(node), node, subs} end)
    do_sort(network, [])
  end

  # based on Kahn's algorithm
  defp do_sort([], result) do
    {:ok, Enum.reverse(result)}
  end

  defp do_sort(network, result) do
    # we must do this one by one to maintain the stability of the given order
    index = Enum.find_index(network, fn {_, _, subs} -> subs == [] end)

    if index do
      {{node_id, node, []}, network} = List.pop_at(network, index)
      network = Enum.map(network, fn {id, comp, subs} -> {id, comp, subs -- [node_id]} end)
      do_sort(network, [node | result])
    else
      {:error, :loop}
    end
  end
end