class Journey::GTG::Builder

# File lib/journey/gtg/builder.rb, line 10
def initialize root
  @root         = root
  @ast          = Nodes::Cat.new root, DUMMY
  @followpos    = nil
end

# File lib/journey/gtg/builder.rb, line 81
def firstpos node
  case node
  when Nodes::Star
    firstpos(node.left)
  when Nodes::Cat
    if nullable? node.left
      firstpos(node.left) | firstpos(node.right)
    else
      firstpos(node.left)
    end
  when Nodes::Or
    node.children.map { |c| firstpos(c) }.flatten.uniq
  when Nodes::Unary
    firstpos(node.left)
  when Nodes::Terminal
    nullable?(node) ? [] : [node]
  else
    raise ArgumentError, 'unknown firstpos: %s' % node.class.name
  end
end

# File lib/journey/gtg/builder.rb, line 123
def followpos node
  followpos_table[node]
end

# File lib/journey/gtg/builder.rb, line 102
def lastpos node
  case node
  when Nodes::Star
    firstpos(node.left)
  when Nodes::Or
    node.children.map { |c| lastpos(c) }.flatten.uniq
  when Nodes::Cat
    if nullable? node.right
      lastpos(node.left) | lastpos(node.right)
    else
      lastpos(node.right)
    end
  when Nodes::Terminal
    nullable?(node) ? [] : [node]
  when Nodes::Unary
    lastpos(node.left)
  else
    raise ArgumentError, 'unknown lastpos: %s' % node.class.name
  end
end

# File lib/journey/gtg/builder.rb, line 62
def nullable? node
  case node
  when Nodes::Group
    true
  when Nodes::Star
    true
  when Nodes::Or
    node.children.any? { |c| nullable?(c) }
  when Nodes::Cat
    nullable?(node.left) && nullable?(node.right)
  when Nodes::Terminal
    !node.left
  when Nodes::Unary
    nullable? node.left
  else
    raise ArgumentError, 'unknown nullable: %s' % node.class.name
  end
end

# File lib/journey/gtg/builder.rb, line 16
def transition_table
  dtrans   = TransitionTable.new
  marked   = {}
  state_id = Hash.new { |h,k| h[k] = h.length }

  start   = firstpos(root)
  dstates = [start]
  until dstates.empty?
    s = dstates.shift
    next if marked[s]
    marked[s] = true # mark s

    s.group_by { |state| symbol(state) }.each do |sym, ps|
      u = ps.map { |l| followpos(l) }.flatten
      next if u.empty?

      if u.uniq == [DUMMY]
        from = state_id[s]
        to   = state_id[Object.new]
        dtrans[from, to] = sym

        dtrans.add_accepting to
        ps.each { |state| dtrans.add_memo to, state.memo }
      else
        dtrans[state_id[s], state_id[u]] = sym

        if u.include? DUMMY
          to = state_id[u]

          accepting = ps.find_all { |l| followpos(l).include? DUMMY }

          accepting.each { |accepting_state|
            dtrans.add_memo to, accepting_state.memo
          }

          dtrans.add_accepting state_id[u]
        end
      end

      dstates << u
    end
  end

  dtrans
end