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