Untitled

require 'logger'
require 'pp'

$log = Logger.new(STDOUT)
$log.level = Logger::DEBUG

class Image
  attr_accessor :width, :height, :pixels

  def initialize(width, height)
    @width = width
    @height = height
    @pixels = Array.new(@width * @height)
  end

  def getPixel(x, y)
    @pixels[y * @width + x]
  end

  def setPixel(x, y, color)
    @pixels[y * @width + x] = color
  end

  def setPixels(pixels)
    @pixels = pixels
  end

  def dump_pixels
    result = "image#dump_pixels\n"
    for y in 0...@height
      line = []
      format = ""
      for x in 0...@width
        line.push(@pixels[y * @width + x])
        format += "%02s "
      end
      result += format % line + "\n"
    end
    result
  end
end

class Point
  attr_accessor :x, :y

  def initialize(x, y)
    @x = x
    @y = y
  end
end

# scan line and fill algorithm
# via http://www40.atwiki.jp/spellbound/pages/315.html
module Painter
  class << self
    def fill(image, x, y, fill_color)
      width = image.width
      height = image.height
      index = y * width + x
      return if image.pixels[index] == fill_color

      color = image.pixels[index]
      buffer = []
      buffer.push(Point.new(x, y))

      while buffer.length > 0
        point = buffer.shift()
        next if image.pixels[point.y * width + point.x] == fill_color

        left = point.x
        while 0 < left
          break if image.pixels[point.y * width + left - 1] != color
          left = left - 1
        end
        right = point.x
        while right < width
          break if image.pixels[point.y * width + right + 1] != color
          right = right + 1
        end

        # fill color
        for x in left..right
          image.pixels[point.y * width + x] = fill_color
        end

        if point.y + 1 < height
          scan_line(image, left, right, point.y + 1, color, buffer)
        end
        if 0 <= point.y - 1
          scan_line(image, left, right, point.y - 1, color, buffer)
        end
      end
    end

    private
    def scan_line(image, left, right, y, color, buffer)
      width = image.width
      height = image.height
      while left <= right
        while left <= right
          break if image.pixels[y * width + left] == color
          left = left + 1
        end
        break if right < left
        while left <= right
          break if image.pixels[y * width + left] != color
          left = left + 1
        end
        buffer.push(Point.new(left - 1, y))
      end
    end
  end
end

module Grouper
  class << self
    def analyze_image(image)
      groups = grouping(image)
      width = image.width
      height = image.height
      result = {}
      for y in 0...height
        for x in 0...width
          index = y * width + x
          group = image.pixels[index]
          if result[group] == nil
            result[group] = []
          end
          result[group].push([x,y])
        end
      end
      result
    end

    def grouping(image)
      width = image.width
      height = image.height
      initial_groups = groups_in_image(image)
      $log.debug initial_groups

      group_id = 'a'
      x = 0
      y = 0
      dbg_step = 0
      dbg_stop_step = 10
      loop do
        index = y * width + x
        color = image.pixels[index]
        $log.debug "----------------------------------------"
        $log.debug "(#{x}:#{y}) = #{color}, #{group_id}"

        _dbg=<<DBG
        $log.debug "[dbg_step:#{dbg_step}, dbg_stop_step:#{dbg_stop_step}]"
        if dbg_step == dbg_stop_step
          break
        end
        dbg_step = dbg_step + 1
        #$log.debug image.dump_pixels
DBG

        return if index >= width * height
        groups = groups_in_image(image)
        $log.debug groups
        has_initial_groups = initial_groups.inject(false) {|r,ig| r || groups.include?(ig)}
        $log.debug "# has_initial_groups = #{has_initial_groups}"
        return groups_in_image(image) unless has_initial_groups
        if has_initial_groups
          is_initial_color = initial_groups.inject(false) {|r,ig| r || (ig == color)}
          $log.debug "# is_initial_color = #{is_initial_color}"
          if is_initial_color
            $log.debug "# (#{x}, #{y}) #{group_id}"
            Painter.fill(image, x, y, group_id)
            $log.debug image.dump_pixels
            #group_id.succ!
            group_id = group_id.succ
          end
          if x < width
            x = x + 1
          else
            if y < height
              x = 0
              y = y + 1
            end
          end
        end
      end
    end

    private
    def groups_in_image(image)
      groups = []
      for y in 0...image.height
        for x in 0...image.width
          color = image.pixels[y * image.width + x]
          groups.push(color) unless groups.include? color
        end
      end
      groups
    end
  end
end


image = Image.new(11, 10)
_test_data_a = [
  -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1,
]
_test_data_b = [
  -1, -1, -1, 1, 1, 1, 1, -1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1, -1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1, -1,-1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1,  1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1,  1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1,  1, 1, -1, -1,
  -1, -1, -1, 1, 1, 1, 1,  1, 1, -1, -1,
  -1,  1, -1, 1, 1, 1, 1,  1, 1, -1, -1,
  -1,  1, -1, 1, 1, 1, 1,  1, 1, -1, -1,
  -1,  1, -1, 1, 1, 1, 1,  1, 1, -1, -1,
]
image.setPixels(_test_data_b)

puts "[initial data] ----------"
puts image.dump_pixels

_fill_test =<<FILL_TEST
puts "[result 1] ----------"
Painter.fill(image, 0, 0, 'a')
image.dump_pixels

#puts "[result 2] ----------"
#Painter.fill(image, 5, 3, 'b')
#image.dump_pixels

puts "[result 3] ----------"
Painter.fill(image, 10, 8, 'c')
image.dump_pixels
FILL_TEST

puts "[result 1] ----------"
#Painter.fill(image, 0, 0, 'a')
#image.dump_pixels
#Painter.fill(image, 3, 0, 'b')
#image.dump_pixels

#groups = Grouper.grouping(image)
#pp groups

result = Grouper.analyze_image(image)
pp result