fixpoint

defmodule CPSolver.Propagator.AllDifferent.Utils do
  alias CPSolver.ValueGraph
  alias CPSolver.Variable.Interface
  alias CPSolver.Propagator.Variable, as: PropagatorVariable
  alias CPSolver.Propagator
  import CPSolver.Utils

  ## Splits graph into SCCs,
  ## and removes cross-edges.
  ## `vertices` is a subset of graph vertices
  ## that DFS will be run on.
  ## This means the split will be made on parts of the graph that
  ## are reachable from these vertices.
  ## `remove_edge_fun/3` is a function
  ## fn(graph, from_vertex, to_vertex)
  ## that returns (possibly modified) graph.
  ##
  ## Returns tuple {sccs, reduced_graph}
  def split_to_sccs(
        graph,
        vertices,
        remove_edge_fun \\ fn graph, from, to -> BitGraph.delete_edge(graph, from, to) end
      ) do
    BitGraph.Algorithms.strong_components(graph,
      vertices: vertices,
      component_handler:
        {fn component, acc -> scc_component_handler(component, remove_edge_fun, acc) end,
         {MapSet.new(), graph}},
      algorithm: :tarjan
    )
  end

  def scc_component_handler(component, remove_edge_fun, {component_acc, graph_acc} = _current_acc) do
    {variable_vertices, updated_graph} =
      Enum.reduce(component, {MapSet.new(), graph_acc},
        fn vertex_index, {vertices_acc, g_acc} = acc ->
          cond do
            ValueGraph.vertex_type(g_acc, vertex_index) == :variable ->
            ## We only need to remove out-edges from 'variable' vertices
            ## that cross to other SCCS
              cross_neighbors = BitGraph.V.out_neighbors(graph_acc, vertex_index)
              variable_id = vertex_index - 1
              {
                MapSet.put(vertices_acc, variable_id),
                remove_cross_edges(
                  g_acc,
                  vertex_index,
                  cross_neighbors,
                  component,
                  remove_edge_fun
                )
              }

            true ->
              acc
          end
        end
      )

    ## drop 1-vertex sccs
    updated_components =
      (MapSet.size(variable_vertices) > 1 && MapSet.put(component_acc, variable_vertices)) ||
        component_acc

    {updated_components, updated_graph}
  end

  defp remove_cross_edges(graph, variable_vertex_index, neighbors, component, remove_edge_fun) do
    ## Note: neighbors of 'variable' vertex are 'value' vertices
    iterate(neighbors, graph, fn neighbor, acc ->
      if neighbor in component do
        {:cont, acc}
      else
        {:cont, remove_edge_fun.(acc, variable_vertex_index, ValueGraph.get_value(graph, neighbor))}
      end
    end)
  end

  def default_remove_edge_fun(vars) do
    fn graph, var_vertex_index, value ->
      var_index = var_vertex_index - 1
      var = ValueGraph.get_variable(vars, var_index)

      if Interface.fixed?(var) do
        (Interface.min(var) == value && graph) || throw(:fail)
      else
        ValueGraph.delete_edge(graph, var_index, value, vars)
      end
    end
  end

  ## Forward checking (FWC)
  ## `unfixed_indices` is the list of indexes for yet (known) unfixed variables.
  ## We will be checking if they are really unfixed anyway.
  def forward_checking(variables) do
    forward_checking(variables,
      MapSet.new(0..(Propagator.arg_size(variables) - 1)),
      MapSet.new())
  end

  def forward_checking(variables, unfixed_indices, fixed_values) do
    case fwc_impl(variables, unfixed_indices, fixed_values) do
      {unfixed, fixed_values, true} ->
        forward_checking(variables, unfixed, fixed_values)

      {unfixed, fixed_values, false} ->
        {unfixed, fixed_values}
    end
  end

  def fwc_impl(variables, unfixed_indices, fixed_values) do
    iterate(
      unfixed_indices,
      {unfixed_indices, fixed_values, false},
      fn unfixed_idx,
         {u_acc, f_acc, _new_fixes?} =
           acc ->
        var = Propagator.arg_at(variables, unfixed_idx)
        {:cont,
         if PropagatorVariable.fixed?(var) do
           update_new_fixed(PropagatorVariable.min(var), unfixed_idx, u_acc, f_acc)
         else
           ## Go over all fixed values
           iterate(f_acc, acc, fn fixed_value, {u_acc2, f_acc2, _} = acc2 ->
             {:cont,
              if PropagatorVariable.remove(var, fixed_value) == :fixed do
                update_new_fixed(PropagatorVariable.min(var), unfixed_idx, u_acc2, f_acc2)
              else
                acc2
              end}
           end)
         end}
      end
    )
  end

  defp update_new_fixed(new_fixed_value, var_idx, current_unfixed, current_fixed) do
    if new_fixed_value in current_fixed, do: fail()
    {MapSet.delete(current_unfixed, var_idx), MapSet.put(current_fixed, new_fixed_value), true}
  end

  #### Component locator.
  ### This is the structure to (quickly) locate the component the verex belongs to.
  ### Given the list of disjoint sets (of vertices), and an element (vertex):
  ### what set (component) the element (vertex) belongs to?
  ### Motivation: to be able to pick out components for the reduction, based on domain changes.
  ### That is, if we get the {0, domain_change}, what component is to process?
  ###
  def build_component_locator(vertices, components) do
    # Build an array with size equal to number of variables
    array_ref = :atomics.new(
      Enum.reduce(vertices, 0, fn index, max_acc -> index > max_acc && index || max_acc end) + 1, signed: true)
    Enum.each(components, fn c -> build_component_locator_impl(array_ref, c) end)

    array_ref
  end

  ## Mind 1-based (indices in component finder) vs. 0-based (variable indices in the component)
  ##
  def build_component_locator_impl(component_finder, component) do
    {first, last} =
      Enum.reduce(component, {nil, nil}, fn el, {first, prev} ->
        if first do
          :atomics.put(component_finder, prev, el + 1)
          {first, el + 1}
        else
          {el + 1, el + 1}
        end
      end)

    :atomics.put(component_finder, last, first)
  end

  ## Retrieve component vertices the variable given by it's idex
  ## belongs to.
  def get_component(component_locator, var_index) do
    base1_index = var_index + 1

    if :atomics.info(component_locator)[:size] < base1_index do
      nil
    else
      case :atomics.get(component_locator, base1_index) do
        0 ->
          nil

        next ->
          get_component_impl(
            component_locator,
            base1_index,
            next,
            MapSet.new([var_index, next - 1])
          )
      end
    end
  end

  defp get_component_impl(component_locator, first_index, current_index, acc) do
    next_index = :atomics.get(component_locator, current_index)

    (next_index == first_index && acc) ||
      get_component_impl(
        component_locator,
        first_index,
        next_index,
        MapSet.put(acc, next_index - 1)
      )
  end


  defp fail() do
    throw(:fail)
  end
end