#!/usr/bin/env lua
editor_sprites=
{foliage={{sprite=192, height=2}, -- Regular European shrub 1
          {sprite=193, height=2}, -- Ground plant, green 1
          {sprite=194, height=2}, -- Bush
          {sprite=195, height=2}, -- Ground plant, red flowers
          {sprite=196, height=2}, -- Shrub
          {sprite=197, height=4}, -- Dead tree (very high)
          {sprite=198, height=2}, -- Low ground plant
          {sprite=199, height=2}, -- Regular European shrub 2
          {sprite=200, height=2}, -- Ground plant, flowers
          {sprite=201, height=1}, -- Flowerbed East/South
          {sprite=202, height=1}, -- Flowerbed West/South
          {sprite=203, height=1}, -- Flowerbed West/North
          {sprite=204, height=1}  -- Flowerbed North/South
         },
 hederow={{sprite=176, height=2}, -- Hedge West-North
          {sprite=177, height=2}, -- Hedge West-South
          {sprite=178, height=2}, -- Hedge East-South
          {sprite=179, height=2}, -- Hedge East-North
          {sprite=180, height=2}, -- Hedge West-East
          {sprite=181, height=2}, -- Hedge North-South
          {sprite=182, height=2}, -- Hedge East-West-South
          {sprite=183, height=2}, -- Hedge East-West-North
          {sprite=184, height=2}, -- Hedge West-North-South
          {sprite=185, height=2}, -- Hedge East-North-South
          {sprite=186, height=2}, -- Hedge East-West-North-South
          {sprite=187, height=2}, -- Hedge North-South with shrub
          {sprite=188, height=2}, -- Hedge North-South with holes
          {sprite=189, height=2}, -- Hedge East-West with shrub 1
          {sprite=190, height=2}, -- Hedge East-West with holes
          {sprite=191, height=2}, -- Hedge East-West with shrub 2
         },
 pond={{sprite= 60, height=1}, -- South edge of a pond
       {sprite= 65, height=1}, -- West edge of a pond
       {sprite= 68, height=1}, -- North edge of a pond
       {sprite= 78, height=1}, -- East edge of a pond
       {sprite= 59, height=1}, -- South-West corner of a pond
       {sprite= 77, height=1}, -- North-East corner of a pond
       {sprite= 79, height=1}, -- South-East corner of a pond
       {sprite= 80, height=1}, -- North-West corner of a pond
       {sprite= 69, height=1}, -- Water tile of a pond
       {sprite= 71, height=1}, -- Water tile of a pond with water lilies
       {sprite= 72, height=2}, -- Water tile of a pond with water plant 1
       {sprite= 73, height=2}  -- Water tile of a pond with water plant 2
      },
 inside={{sprite= 16, height=1}, -- Dark big checker pattern tile
         {sprite= 17, height=1}, -- Dark blue/purple carpet tile
         {sprite= 70, height=1}, -- Duplicate of 017
         {sprite= 18, height=1}, -- Red-Blue floor tile 1
         {sprite= 19, height=1}, -- Red-Blue floor tile 2
         {sprite= 23, height=1}, -- Red-Blue floor tile 3
         {sprite= 20, height=1}, -- Wooden floor tile
         {sprite= 21, height=1}, -- Small checker pattern tile
         {sprite= 22, height=1}, -- Big checker pattern tile
         {sprite= 66, height=1}, -- Floor tile with light center
         {sprite= 76, height=1}  -- Floor tile with light center and corners
        },
 outside={{sprite=  1, height=1}, -- Grass tile 1
          {sprite=  2, height=1}, -- Grass tile 2
          {sprite=  3, height=1}, -- Grass tile 3
          {sprite=  4, height=1}, -- Light concrete tile
          {sprite= 15, height=1}, -- Concrete tile
          {sprite=  5, height=1}, -- Dark concrete tile
          {sprite=  6, height=1}, -- Grass tile with South-East concrete corner
          {sprite=  8, height=1}, -- Grass tile with South-West concrete corner
          {sprite= 10, height=1}, -- Grass tile with North-West concrete corner
          {sprite= 12, height=1}, -- Grass tile with North-East concrete corner
          {sprite=  7, height=1}, -- Grass tile with South concrete edge
          {sprite=  9, height=1}, -- Grass tile with West concrete edge
          {sprite= 11, height=1}, -- Grass tile with North concrete edge
          {sprite= 13, height=1}, -- Grass tile with East concrete edge
          {sprite= 14, height=1}, -- Concrete tile with North-East grass corner
          {sprite= 61, height=1}, -- Concrete tile with South-West grass corner
          {sprite= 62, height=1}, -- Concrete tile with South-East grass corner
          {sprite= 63, height=1}, -- Concrete tile with North-West grass corner
          {sprite= 64, height=1}, -- Grass tile with rocks
          {sprite=205, height=1}, -- Fully cracked garden marble tile
          {sprite=206, height=1}, -- Broken garden marble tile
          {sprite=207, height=1}, -- Partially cracked garden marble tile
          {sprite=208, height=1}, -- Garden marble tile
          {sprite=209, height=2}, -- Lamp post pointing East
          {sprite=210, height=2}, -- Lamp post pointing South
         },
 road={{sprite= 41, height=1}, -- Road with white discontinuous line North-South
       {sprite= 42, height=1}, -- Road with double yellow lines at West with black orthogonal lines
       {sprite= 43, height=1}, -- Road with double yellow lines at West edge
       {sprite= 44, height=1}, -- Road with double yellow lines at West edge merging at North
       {sprite= 45, height=1}, -- Road with double yellow lines at West edge merging at South
       {sprite= 46, height=1}, -- Duplicate of 045
       {sprite= 47, height=1}, -- Road with red line at East linked to yellow discontinuous line at South
       {sprite= 48, height=1}, -- Road with red line at East linked to yellow discontinuous line at North
       {sprite= 49, height=1}, -- Road with red braking line at the East pointing to the West
       {sprite= 50, height=1}, -- Road with grey edge at the East
       {sprite= 51, height=1}, -- Road with double yellow lines at East edge
       {sprite= 52, height=1}, -- Road with double yellow lines at East with black orthogonal lines
       {sprite= 53, height=1}, -- Road with double yellow lines at East edge merging at the south
       {sprite= 54, height=1}, -- Duplicate of 052
       {sprite= 55, height=1}, -- Road with red braking line at the West pointing to the East
       {sprite= 56, height=1}, -- Road with red line at West linked to yellow discontinuous line at North
       {sprite= 57, height=1}, -- Road with red line at West linked to yellow discontinuous line at South
       {sprite= 58, height=1}, -- Road with grey edge at the West
      },
 ["north wall"]={{sprites={{sprite=159, xpos=1, ypos=1}, -- External doorway North outside left part
                           {sprite=157, xpos=3, ypos=1}, -- External doorway North outside right part
                          },
                  height=3},
                 {sprites={{sprite=163, xpos=1, ypos=1}, -- External doorway North inside left part
                           {sprite=161, xpos=3, ypos=1}, -- External doorway North inside right part
                          },
                  height=3},

                 {sprite=114, height=2}, -- External North wall outside
                 {sprite=116, height=2}, -- External North wall outside left part of window
                 {sprite=120, height=2}, -- External North wall with window glass
                 {sprite=118, height=2}, -- External North wall outside right part of window
                 {sprite=122, height=2}, -- External North wall inside
                 {sprite=124, height=2}, -- External North wall inside left part of window
                 {sprite=126, height=2}, -- External North wall inside right part of window
                },
 ["west wall"]={{sprites={{sprite=158, xpos=1, ypos=3}, -- External doorway West outside left part
                          {sprite=160, xpos=1, ypos=1}, -- External doorway West outside right part
                         },
                 height=3},
                {sprites={{sprite=162, xpos=1, ypos=3}, -- External doorway West inside left part
                          {sprite=164, xpos=1, ypos=1}, -- External doorway West inside right part
                         },
                 height=3},

                {sprite=115, height=2}, -- External West wall outside
                {sprite=119, height=2}, -- External West wall outside left part of window
                {sprite=121, height=2}, -- External West wall with window glass
                {sprite=117, height=2}, -- External West wall outside right part of window
                {sprite=123, height=2}, -- External West wall inside
                {sprite=127, height=2}, -- External West wall inside left part of window
                {sprite=125, height=2}, -- External West wall inside right part of window
               },
 helipad={{sprites={{sprite=5, xpos=1, ypos=1}, {sprite=5, xpos=2, ypos=1}, {sprite=5, xpos=3, ypos=1},
                    {sprite=5, xpos=4, ypos=1}, {sprite=5, xpos=5, ypos=1}, {sprite=5, xpos=1, ypos=2},
                    {sprite=5, xpos=1, ypos=3}, {sprite=5, xpos=1, ypos=4}, {sprite=5, xpos=1, ypos=5},
                    {sprite=5, xpos=2, ypos=5}, {sprite=5, xpos=3, ypos=5}, {sprite=5, xpos=4, ypos=5},
                    {sprite=5, xpos=5, ypos=5}, {sprite=5, xpos=5, ypos=2}, {sprite=5, xpos=5, ypos=3},
                    {sprite=5, xpos=5, ypos=4},
                    {sprite=5, xpos=3, ypos=2}, {sprite=5, xpos=3, ypos=4},

                    {sprite=4, xpos=2, ypos=2}, {sprite=4, xpos=2, ypos=3}, {sprite=4, xpos=2, ypos=4},
                    {sprite=4, xpos=4, ypos=2}, {sprite=4, xpos=4, ypos=3}, {sprite=4, xpos=4, ypos=4},
                    {sprite=4, xpos=3, ypos=3}
                   },
           height=3}
          }
}
local MAX_HEIGHT = 4 -- Biggest height in above sprites

--! Normalize the editor sprite in the table to always have a 'sprites' field, as well as have sizes and a column width (for the display).
--!param (table) Sprite from the editor_sprites table.
--!return (table 'sprites', 'xsize', 'ysize', 'width', and 'height')
function normalize_edit_sprite(spr)
  assert(MAX_HEIGHT >= spr.height) -- Verify that sprite fits in the maximum height.

  if spr.sprites == nil then -- {spritex=xxx, height=y} case
    return {sprites={sprite=spr.sprite, xpos=1, ypos=1},
            xsize=1,
            ysize=1,
            width=2,
            height=spr.height}
  else
    -- {sprites={...}, height=y} case, compute sizes, and width
    local xsize=1
    local ysize=1
    for _, sp in ipairs(spr.sprites) do
      if sp.xpos > xsize then xsize = sp.xpos end
      if sp.ypos > ysize then ysize = sp.ypos end
    end

    local width = xsize
    if width < ysize then width = ysize end

    return {sprites=spr.sprites,
            xsize=xsize,
            ysize=ysize,
            width = width + 1,
            height=spr.height}
  end
end


--!Decide the highest possible placement for 'width' columns.
--!param cols (list int) First available position in each column, higher number is lower.
--!param width (int) Required width as number of columns.
--!return (int, int) Starting column and placement height.
function get_highest_rowcol(cols, width)
  local best = cols[1] + 100000
  local best_col = 0

  for left = 1, #cols - width + 1 do -- Try starting in each column.
    if cols[left] < best then -- First column is potentially better.
      local top = cols[left]
      for i = 1, width - 1 do
        if top < cols[left + i] then
          top = cols[left + i]
          if top >= best then break end -- i-th column breaks improvement.
        end
      end
      if top < best then
        best = top
        best_col = left
      end
    end
  end
  return best_col, best
end

--! Layout buttons from a tab of editor sprites.
--!param esprs (list) Editor sprite tab to layout.
--!param num_cols (int) Number of columns available in the layout.
--!return (list) Sprites with button positions in ('column', 'row').
function layout_buttons(esprs, num_cols)
  local buttons = {}

  local cols = {}
  for i = 1, num_cols do
    cols[i] = 1
  end

  for hgt = MAX_HEIGHT, 1, -1 do -- Fit highest sprites first.
    for _, espr in ipairs(esprs) do
      espr = normalize_edit_sprite(espr)
      if espr.height == hgt then
        local spr_col, spr_height = get_highest_rowcol(cols, espr.width)
        buttons[#buttons + 1] = espr
        buttons[#buttons].column = spr_col
        buttons[#buttons].row = spr_height

        for i = spr_col, spr_col + espr.width - 1 do -- Update height in the affected columns
          assert(cols[i] <= spr_height)
          cols[i] = spr_height + hgt
        end

      end
    end
  end
  return buttons
end

for name, sprs in pairs(editor_sprites) do
  local buttons = layout_buttons(sprs, 6)
  print(name)
  for _, button in ipairs(buttons) do
    print("col " .. button.column .. " y " .. button.row .. " width " .. button.width .. " height " .. button.height)
  end
end