get("#349") -- table functions
get("#121") -- compareTables
get("#348") -- bright and rgb

maxSize = {width=100, height=50}
minSize = {width=4, height=4}
threshold = 0.5
wandSize = 2 -- magic wand size

local rectangles, _img

function cloneRectangle(r)
  return newRectangle(r.x, r.y, r.width, r.height)
end

function newRectangle(x, y, w, h)
  return {x=x, y=y, width=w, height=h}
end

function contains(r, x, y)
  return x >= r.x and y >= r.y and x < r.x+r.width and y < r.y+r.width
end

function seen(x, y)
  for r, _ in pairs(rectangles) do
    if contains(r, x, y) then
      return true
    end
  end
return false
end

-- returns rectangle
function magicWand(image, x, y)
  if image ~= _img then
    _img, rectangles = image, {}
  end
  if seen(x, y) then return nil end
  local r = newRectangle(x, y, 1, 1)
  
  while true do
    local last = cloneRectangle(r)
    --expandLeft(image, r)
    --if tooLarge(r) then return nil end
    --expandTop(image, r)
    --if tooLarge(r) then return nil end
    expandRight(image, r)
    if tooLarge(r) then return nil end
    expandBottom(image, r)
    if tooLarge(r) then return nil end    
    if compareTables(last, r) then
      if r.width >= minSize.width and r.height >= minSize.width then
        rectangles[r] = true
        return r
      else
        return nil
      end
    end
  end
end

function tooLarge(r)
  return maxSize ~= nil and (r.width > maxSize.width or r.height > maxSize.height)
end

function expandLeft(image, r)
  local newX = math.max(r.x - wandSize, 0)
  if newX == r.x then return end
  newX = searchFromLeft(image, newRectangle(newX, r.y, r.x-newX, r.height))
  r.width = r.width+r.x-newX
  r.x = newX
end

function searchFromLeft(image, r)
  for x = r.x, r.x+r.width-1 do
    if regionNotEmpty(image, newRectangle(x, r.y, 1, r.height)) then
      return x
    end
  end
  return r.x+r.width
end

function expandRight(image, r)
  local newX = math.min(r.x + r.width + wandSize, image.width)
  if newX == r.x+r.width then return end
  newX = searchFromRight(image, newRectangle(r.x+r.width, r.y, newX-(r.x+r.width), r.height))
  r.width = newX-r.x
end

function searchFromRight(image, r)
  for x = r.x+r.width-1, r.x, -1 do
    if regionNotEmpty(image, newRectangle(x, r.y, 1, r.height)) then
      return x+1
    end
  end
  return r.x
end

function expandTop(image, r)
  local newY = math.max(r.y - wandSize, 0)
  if newY == r.y then return end
  newY = searchFromTop(image, newRectangle(r.x, newY, r.width, r.y-newY))
  r.height = r.height+r.y-newY
  r.y = newY
end

function searchFromTop(image, r)
  for y = r.y, r.y+r.height-1 do
    if regionNotEmpty(image, newRectangle(r.x, y, r.width, 1)) then
      return y
    end
  end
  return r.y+r.height
end

function expandBottom(image, r)
  local newY = math.min(r.y + r.height + wandSize, image.height)
  if newY == r.y+r.height then return end
  newY = searchFromBottom(image, newRectangle(r.x, r.y + r.height, r.width, newY-(r.y+r.height)))
  r.height = newY-r.y
end

function searchFromBottom(image, r)
  for y = r.y+r.height-1, r.y, -1 do
    if regionNotEmpty(image, newRectangle(r.x, y, r.width, 1)) then
      return y+1
    end
  end
  return r.y
end

-- we're looking for dark pixels this time
function regionNotEmpty(image, r)
  --return image.clip(rectangle).anyPixelBrighterThan(threshold)
  for y=r.y, r.y+r.height-1 do
    for x=r.x, r.x+r.width-1 do
      if bright(rgb(image.getInt(x, y))) < threshold then
        return true
      end
    end
  end
  return false
end


function recttostring(r)
  return r.x..", "..r.y..", "..r.x+r.width..", "..r.y+r.height
end

function magicWandAll(image)
  local allrects = {}

  for y = 0, image.height-1, 2 do
    for x = 0, image.width-1, 2 do
      local r = magicWand(image, x, y)
      
      if r then
        allrects[recttostring(r)] = true
      end
    end
  end
  
  return allrects
end

wandSize = 3
allrects = magicWandAll(img)
result = table.concat(keystolist(allrects), "|")
if result ~= '' then
  return "Magic Wand All (optimizing): "..result
end