defmodule CPSolver.Examples.BinPacking.UpperBound do
  @moduledoc """
  Precompute upper bounds for bin packing instance
  based on heuristics.
  'First fit decreasing' is the one that is implemented
  """
  alias InPlace.Array

  def first_fit_decreasing(weights, capacity) do
    first_fit(Enum.sort(weights, :desc), capacity)
  end

  def first_fit(weights, capacity) do
    if hd(weights) > capacity do
      throw(:item_weight_over_capacity)
    end

    remaining_bin_space = Array.new(length(weights), capacity)

    Enum.reduce(weights, 1, fn w, count_acc ->
      if place_item(remaining_bin_space, w, count_acc) do
        count_acc
      else
        (count_acc + 1)
        |> tap(fn new_bin_idx ->
          Array.update(remaining_bin_space, new_bin_idx, fn val -> val - w end)
        end)
      end
    end)
  end

  defp place_item(bin_space, weight, bin_count) do
    Enum.reduce_while(1..bin_count, false, fn bin_idx, _acc ->
      if Array.get(bin_space, bin_idx) >= weight do
        ## Can place item to this bin
        Array.update(bin_space, bin_idx, fn val -> val - weight end)
        {:halt, true}
      else
        {:cont, false}
      end
    end)
  end
end