#
# LinearGraphTemplate.rb
#
# Copyright (C) 2010 GLAD!! (ITO Yoshiichi)
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND,
# either express or implied. See the License for the specific language
# governing permissions and limitations under the License.
#

require 'logger'
require 'LinearGraph'

class LinearGraphTemplate

  @@log = Logger.new(STDOUT)
  @@log.level = Logger::WARN
  @@log.formatter = proc {|s, d, p, m| sprintf("%-5s %s: %s\n", s, p, m) }

  class LevelCount

    attr_reader :level, :count
    
    def initialize(level, count)
      @level = level
      @count = count
    end

    def to_s
      "#{ level }^#{ count <= 0 ? 'n' : count }"
    end

    def inspect
      to_s
    end

  end

  attr_reader :size, :graphs, :levels

  def initialize(size, args = '')
    @size_x = log2(size)
    @size = 2 ** @size_x
    @safe_list = (0...@size_x).map {|x| 2 ** x }
    @graphs = make_graphs(LinearGraph.new([1]),
        (2...@size).to_a, make_hints(@size_x, args))
    @levels = make_levels(@graphs)
  end

  def make_hints(size_x, args)
    hints = args.split(',').map {|x|
      x =~ /(\d+)(?:\^(\d+))?/
      LevelCount.new(2 ** log2($1.to_i), $2.to_i)
    }
    if hints.empty?
      hints = [LevelCount.new(2 ** ((size_x + 1) / 2), 0)]
    end
    hints
  end

  def log2(x)
    x.to_s(2).size - 1
  end

  def make_graphs(graph, values, hints)
    @@log.info { "make_graphs(#{ graph.inspect }, " +
        "#{ values.inspect }, #{ hints.inspect })" }
    if values.empty?
      return [graph]
    end
    if hints.empty? || graph.level < hints[0].level
      points = values
      # 線点図の点が 2^n の場合、それ以外は検索しない。
      if @safe_list.include?(graph.points[0])
        points &= @safe_list
      end
      candiate = nil
      dejavu = []
      points.each {|x|
        if !dejavu.include?(x) && graph.points.last < x
          g = LinearGraph.new([x], graph)
          lines = g.lines - graph.lines
          dejavu += lines
          if lines.all? {|line| values.include?(line) }
            gs = make_graphs(g, values - g.values, hints)
            @@log.debug { "gs = #{ gs.inspect }" }
            # 線点図の点が 2^n の場合、検索を終了する。
            return gs if @safe_list.include?(g.points[0])
            # 最後のレベルが2より大きい場合、検索を終了する。
            return gs if gs.last.level > 2
            # 2回まで検索を行う。
            if !candiate
              candiate = gs
            else
              if gs.size < candiate.size
                candiate = gs
              end
              return candiate
            end
          end
        end
      }
      if candiate
        return candiate
      end
    end
    hints = next_hints(hints, graph)
    # レベルが2になったらすべて点で埋める。
    if !hints.empty? && hints[0].level == 2
      return [graph] + values.map {|x| LinearGraph.new([x]) }
    end
    [graph] + make_graphs(LinearGraph.new(values.take(1)), values.drop(1), hints)
  end

  def next_hints(hints, graph)
    hints = hints.drop_while {|x| graph.level < x.level }
    if hints.empty?
      return [LevelCount.new(graph.level, 0)]
    end
    if graph.level > hints[0].level || hints[0].count <= 0
      return hints
    end
    count = hints[0].count - 1
    if count > 0
      return [LevelCount.new(hints[0].level, count)] + hints.drop(1)
    end
    hints = hints.drop(1)
    if hints.empty?
      return [LevelCount.new(graph.level / 2, 0)]
    end
    hints
  end

  def make_levels(graphs)
    levels = []
    level = 0; count = 0
    graphs.each {|g|
      if level != g.level
        if count != 0
          levels << LevelCount.new(level, count)
        end
        level = g.level
        count = 1
      else
        count += 1
      end
    }
    if count != 0
      levels << LevelCount.new(level, count)
    end
    levels
  end

  def make_row(original)
    row = []
    graphs.each {|g|
      value = 0
      g.points.each {|x|
        value = value * 2 + original[x - 1]
      }
      row << value
    }
    row
  end

  def summary
    "L#{ size }: #{ levels.join(', ') }"
  end

  def to_s
    "L#{ size }: #{ graphs.join(', ') }"
  end

  def inspect
    to_s
  end

end