module EasyBoxPacker

# File easy-box-packer.rb, line 71
def find_smallest_container(items:)
  possible_containers = []
  invalid_containers  = []

  min_vol = items.map { |h| h[:dimensions].inject(&:*) }.inject(&:+)
  # order items from biggest to smallest
  sorted_items = items.sort_by { |h| h[:dimensions].sort }.reverse

  # base_container = sorted_items.first
  based_container = sorted_items.first

  if sorted_items.size == 1
    return based_container[:dimensions]
  end

  find_possible_container(
    possible_containers: possible_containers,
    invalid_containers: invalid_containers,
    container: based_container[:dimensions],
    items: sorted_items.map {|i| i[:dimensions]},
    item_index: 1,
    min_vol: min_vol)

  select_container = possible_containers.map { |a| a.sort }.sort_by { |a| [a.inject(&:*), a.inject(&:+)] }.each do |c|
    packing = pack(
      container: { dimensions: c },
      items: items)
    break c if packing[:packings].size == 1 && packing[:errors].size == 0
  end
  check_container_is_bigger_than_greedy_box({dimensions: select_container}, items) ? item_greedy_box(items) : select_container
end

# File easy-box-packer.rb, line 3
def pack(container:, items:)
  packings = []
  errors   = []
  # pack from biggest to smallest
  items.sort_by { |h| h[:dimensions].sort.reverse }.reverse.each do |item|
    # If the item is just too big for the container lets give up on this
    if item[:weight].to_f > container[:weight_limit].to_f
      errors << "Item: #{item} is too heavy for container"
      next
    end

    # Need a bool so we can break out nested loops once it's been packed
    item_has_been_packed = false

    packings.each do |packing|
      # If this packings going to be too big with this
      # item as well then skip on to the next packing
      next if packing[:weight].to_f + item[:weight].to_f > container[:weight_limit].to_f

      # remove volume size = 0 (not possible to pack)
      packing[:spaces].reject! { |space| space[:dimensions].inject(:*) == 0 }
      # try minimum space first
      packing[:spaces].sort_by { |h| h[:dimensions].sort }.each do |space|
        # Try placing the item in this space,
        # if it doesn't fit skip on the next space
        next unless placement = place(item, space)
        # Add the item to the packing and
        # break up the surrounding spaces
        packing[:placements] += [placement]
        packing[:weight] += item[:weight].to_f
        packing[:spaces] -= [space]
        packing[:spaces] += break_up_space(space, placement)
        item_has_been_packed = true
        break
      end
      break if item_has_been_packed
    end
    next if item_has_been_packed
    # Can't fit in any of the spaces for the current packings
    # so lets try a new space the size of the container
    space = {
      dimensions: container[:dimensions].sort.reverse,
      position: [0, 0, 0]
    }
    placement = place(item, space)

    # If it can't be placed in this space, then it's just
    # too big for the container and we should abandon hope
    unless placement
      errors << "Item: #{item} cannot be placed in container"
      next
    end
    # Otherwise lets put the item in a new packing
    # and break up the remaing free space around it
    packings += [{
      placements: [placement],
      weight: item[:weight].to_f,
      spaces: break_up_space(space, placement)
    }]
  end

  if packings.size > 1 && check_container_is_bigger_than_greedy_box(container, items)
    { packings: generate_packing_for_greedy_box(items), errors: [] }
  else
    { packings: packings, errors: errors }
  end
end

# File easy-box-packer.rb, line 193
def break_up_space(space, placement)
  return_possible_spaces = [
    # HEIGHT SPACE => WIDTH  => LENGTH
    [
      {
        dimensions: [
          space[:dimensions][0],
          space[:dimensions][1],
          space[:dimensions][2] - placement[:dimensions][2]
        ],
        position: [
          space[:position][0],
          space[:position][1],
          space[:position][2] + placement[:dimensions][2]
        ]
      },
      {
        dimensions: [
          space[:dimensions][0],
          space[:dimensions][1] - placement[:dimensions][1],
          placement[:dimensions][2]
        ],
        position: [
          space[:position][0],
          space[:position][1] + placement[:dimensions][1],
          space[:position][2]
        ]
      },
      {
        dimensions: [
          space[:dimensions][0] - placement[:dimensions][0],
          placement[:dimensions][1],
          placement[:dimensions][2]
        ],
        position: [
          space[:position][0] + placement[:dimensions][0],
          space[:position][1],
          space[:position][2]
        ]
      }
    ],
    # HEIGHT SPACE => LENGTH => WIDTH
    [
      {
        dimensions: [
          space[:dimensions][0],
          space[:dimensions][1],
          space[:dimensions][2] - placement[:dimensions][2]
        ],
        position: [
          space[:position][0],
          space[:position][1],
          space[:position][2] + placement[:dimensions][2]
        ]
      },
      {
        dimensions: [
          space[:dimensions][0] - placement[:dimensions][0],
          space[:dimensions][1],
          placement[:dimensions][2]
        ],
        position: [
          space[:position][0] + placement[:dimensions][0],
          space[:position][1],
          space[:position][2]
        ]
      },
      {
        dimensions: [
          placement[:dimensions][0],
          space[:dimensions][1] - placement[:dimensions][1],
          placement[:dimensions][2]
        ],
        position: [
          space[:position][0],
          space[:position][1] + placement[:dimensions][1],
          space[:position][2]
        ]
      }
    ],
    # LENGTH SPACE => HEIGHT => WIDTH
    [
      {
        dimensions: [
          space[:dimensions][0] - placement[:dimensions][0],
          space[:dimensions][1],
          space[:dimensions][2]
        ],
        position: [
          space[:position][0] + placement[:dimensions][0],
          space[:position][1],
          space[:position][2]
        ]
      },
      {
        dimensions: [
          placement[:dimensions][0],
          space[:dimensions][1],
          space[:dimensions][2] - placement[:dimensions][2]
        ],
        position: [
          space[:position][0],
          space[:position][1],
          space[:position][2] + placement[:dimensions][2]
        ]
      },
      {
        dimensions: [
          placement[:dimensions][0],
          space[:dimensions][1] - placement[:dimensions][1],
          placement[:dimensions][2]
        ],
        position: [
          space[:position][0],
          space[:position][1] + placement[:dimensions][1],
          space[:position][2]
        ]
      }
    ],
    # LENGTH SPACE => WIDTH  => HEIGHT
    [
      {
        dimensions: [
          space[:dimensions][0] - placement[:dimensions][0],
          space[:dimensions][1],
          space[:dimensions][2]
        ],
        position: [
          space[:position][0] + placement[:dimensions][0],
          space[:position][1],
          space[:position][2]
        ]
      },
      {
        dimensions: [
          placement[:dimensions][0],
          space[:dimensions][1] - placement[:dimensions][1],
          space[:dimensions][2]
        ],
        position: [
          space[:position][0],
          space[:position][1] + placement[:dimensions][1],
          space[:position][2]
        ]
      },
      {
        dimensions: [
          placement[:dimensions][0],
          placement[:dimensions][1],
          space[:dimensions][2] - placement[:dimensions][2]
        ],
        position: [
          space[:position][0],
          space[:position][1],
          space[:position][2] + placement[:dimensions][2]
        ]
      }
    ],
    # WIDTH SPACE  => LENGTH => HEIGHT
    [
      {
        dimensions: [
          space[:dimensions][0],
          space[:dimensions][1] - placement[:dimensions][1],
          space[:dimensions][2]
        ],
        position: [
          space[:position][0],
          space[:position][1] + placement[:dimensions][1],
          space[:position][2]
        ]
      },
      {
        dimensions: [
          space[:dimensions][0] - placement[:dimensions][0],
          placement[:dimensions][1],
          space[:dimensions][2]
        ],
        position: [
          space[:position][0] + placement[:dimensions][0],
          space[:position][1],
          space[:position][2]
        ]
      },
      {
        dimensions: [
          placement[:dimensions][0],
          placement[:dimensions][1],
          space[:dimensions][2] - placement[:dimensions][2]
        ],
        position: [
          space[:position][0],
          space[:position][1],
          space[:position][2] + placement[:dimensions][2]
        ]
      }
    ],
    # WIDTH SPACE  => HEIGHT => LENGTH
    [
      {
        dimensions: [
          space[:dimensions][0],
          space[:dimensions][1] - placement[:dimensions][1],
          space[:dimensions][2]
        ],
        position: [
          space[:position][0],
          space[:position][1] + placement[:dimensions][1],
          space[:position][2]
        ]
      },
      {
        dimensions: [
          space[:dimensions][0],
          placement[:dimensions][1],
          space[:dimensions][2] - placement[:dimensions][2]
        ],
        position: [
          space[:position][0],
          space[:position][1],
          space[:position][2] + placement[:dimensions][2]
        ]
      },
      {
        dimensions: [
          space[:dimensions][0] - placement[:dimensions][0],
          placement[:dimensions][1],
          placement[:dimensions][2]
        ],
        position: [
          space[:position][0] + placement[:dimensions][0],
          space[:position][1],
          space[:position][2]
        ]
      }
    ]
  ]
  # PICK biggest
  return_possible_spaces.sort_by { |a| a.map {|aa| aa[:dimensions].sort}}.last
end

# File easy-box-packer.rb, line 442
def check_container_is_bigger_than_greedy_box(container, items)
  c = container[:dimensions].sort.reverse
  greedy_box = item_greedy_box(items)
  c[0] >= greedy_box[0] && c[1] >= greedy_box[1] && c[2] >= greedy_box[2] && container[:weight_limit].to_f >= items.inject(0) { |sum, i| sum += i[:weight].to_f }
end

# File easy-box-packer.rb, line 113
def find_possible_container(possible_containers:,invalid_containers:,container:, items:, item_index:, min_vol:)
  return unless items[item_index]
  c_length, c_width, c_height = container.sort.reverse
  b_length, b_width, b_height = items[item_index].sort.reverse
  c_permutations = [
    [c_width,  c_height, c_length],
    [c_length, c_width,  c_height],
    [c_length, c_height, c_width]
  ]
  b_permutations = [
    [b_width,  b_height, b_length],
    [b_length, b_width,  b_height],
    [b_length, b_height, b_width]
  ]

  tmp_possible_containers = []
  # (1) loops base_container 3 rotations
  c_permutations.each do |c_perm|
    # (2) try to puts items to 3 points, then it will create 3 different possible containers
    b_permutations.each do |b_perm|
      tmp_possible_containers << [  c_perm[0] + b_perm[0],     [c_perm[1], b_perm[1]].max, [c_perm[2], b_perm[2]].max]
      tmp_possible_containers << [ [c_perm[0], b_perm[0]].max,  c_perm[1] + b_perm[1],     [c_perm[2], b_perm[2]].max]
      tmp_possible_containers << [ [c_perm[0], b_perm[0]].max, [c_perm[1], b_perm[1]].max,  c_perm[2]+ b_perm[2]]
    end
  end
  removed_tried_container = tmp_possible_containers.map { |a| a.sort }.uniq - possible_containers - invalid_containers

  return unless removed_tried_container.any?
  # (3) loop all container from smallest spaces to biggest space
  removed_tried_container.sort_by { |a| [a.inject(&:*), a.inject(&:+)] }.each do |cont|
    # (4) next unless l * w * h >= minimum_space
    if cont.inject(&:*) >= min_vol
      possible_containers << cont
    # else
      # puts "invalid: #{cont}"
      # invalid_containers << cont
      # find_possible_container(possible_containers: possible_containers, invalid_containers: invalid_containers, container: cont, items: items, item_index: item_index + 1, min_vol: min_vol)
    end
  end
  # minimum_space = (removed_tried_container).sort_by { |a| [a.inject(&:*), a.inject(&:+)] }.first
  minimum_std = removed_tried_container.sort_by { |a| [std(a), a.inject(&:*), a.inject(&:+)] }.first
  [minimum_std].uniq.compact.each do |cont|
    find_possible_container(possible_containers: possible_containers, invalid_containers: invalid_containers, container: cont, items: items, item_index: item_index + 1, min_vol: min_vol)
  end
end

# File easy-box-packer.rb, line 448
def generate_packing_for_greedy_box(items)
  return_h = {placements: [], weight: 0, spaces: []}
  height   = 0
  items.each do |i|
    return_h[:placements] << { dimensions: i[:dimensions], :position=>[0, 0, height], weight: i[:weight].to_f }
    return_h[:weight] += i[:weight].to_f
    height += i[:dimensions].sort.first.to_f
  end
  [return_h]
end

# File easy-box-packer.rb, line 434
def item_greedy_box(items)
  array_of_lwh            = items.map { |i| i[:dimensions].sort.reverse }
  items_max_length        = array_of_lwh.max { |x, y| x[0] <=> y[0] }[0]
  items_max_width         = array_of_lwh.max { |x, y| x[1] <=> y[1] }[1]
  items_total_height      = array_of_lwh.inject(0) { |sum, x| sum+=x[2] }.round(1)
  [items_max_length, items_max_width, items_total_height]
end

# File easy-box-packer.rb, line 159
def place(item, space)
  item_length, item_width, item_height = item[:dimensions].sort.reverse

  permutations = [
    [item_width, item_height, item_length],
    [item_width, item_length, item_height],
    [item_height, item_width, item_length],
    [item_height, item_length, item_width],
    [item_length, item_width, item_height],
    [item_length, item_height, item_width]
  ]

  possible_rotations_and_margins = []

  permutations.each do |perm|
    # Skip if the item does not fit with this orientation
    next unless perm[0] <= space[:dimensions][0] &&
      perm[1] <= space[:dimensions][1] &&
      perm[2] <= space[:dimensions][2]

    possible_margin   = [space[:dimensions][0] - perm[0], space[:dimensions][1] - perm[1], space[:dimensions][2] - perm[2]]
    possible_rotations_and_margins << { margin: possible_margin, rotation: perm }
  end

  # select rotation with smallest margin
  final = possible_rotations_and_margins.sort_by { |a| a[:margin].sort }.first
  return unless final
  return {
    dimensions: final[:rotation],
    position: space[:position],
    weight: item[:weight].to_f
  }
end

# File easy-box-packer.rb, line 105
def std(contents)
  n = contents.size
  contents.map!(&:to_f)
  mean = contents.reduce(&:+)/n
  sum_sqr = contents.map {|x| x * x}.reduce(&:+)
  Math.sqrt(((sum_sqr - n * mean * mean)/(n-1)).abs)
end