class Journey::NFA::TransitionTable

# File lib/journey/nfa/transition_table.rb, line 11
def initialize
  @table     = Hash.new { |h,f| h[f] = {} }
  @memos     = {}
  @accepting = nil
  @inverted  = nil
end

# File lib/journey/nfa/transition_table.rb, line 34
def []= i, f, s
  @table[f][i] = s
end

# File lib/journey/nfa/transition_table.rb, line 18
def accepting? state
  accepting == state
end

# File lib/journey/nfa/transition_table.rb, line 22
def accepting_states
  [accepting]
end

# File lib/journey/nfa/transition_table.rb, line 26
def add_memo idx, memo
  @memos[idx] = memo
end

# File lib/journey/nfa/transition_table.rb, line 111
def alphabet
  inverted.values.map(&:keys).flatten.compact.uniq.sort_by { |x| x.to_s }
end

# File lib/journey/nfa/transition_table.rb, line 118
def eclosure t
  stack = Array(t)
  seen  = {}
  children = []

  until stack.empty?
    s = stack.pop
    next if seen[s]

    seen[s] = true
    children << s

    stack.concat inverted[s][nil]
  end

  children.uniq
end

# File lib/journey/nfa/transition_table.rb, line 96
def following_states t, a
  Array(t).map { |s| inverted[s][a] }.flatten.uniq
end

# File lib/journey/nfa/transition_table.rb, line 52
def generalized_table
  gt       = GTG::TransitionTable.new
  marked   = {}
  state_id = Hash.new { |h,k| h[k] = h.length }
  alphabet = self.alphabet

  stack = [eclosure(0)]

  until stack.empty?
    state = stack.pop
    next if marked[state] || state.empty?

    marked[state] = true

    alphabet.each do |alpha|
      next_state = eclosure(following_states(state, alpha))
      next if next_state.empty?

      gt[state_id[state], state_id[next_state]] = alpha
      stack << next_state
    end
  end

  final_groups = state_id.keys.find_all { |s|
    s.sort.last == accepting
  }

  final_groups.each do |states|
    id = state_id[states]

    gt.add_accepting id
    save = states.find { |s|
      @memos.key?(s) && eclosure(s).sort.last == accepting
    }

    gt.add_memo id, memo(save)
  end

  gt
end

# File lib/journey/nfa/transition_table.rb, line 30
def memo idx
  @memos[idx]
end

# File lib/journey/nfa/transition_table.rb, line 38
def merge left, right
  @memos[right] = @memos.delete left
  @table[right] = @table.delete(left)
end

# File lib/journey/nfa/transition_table.rb, line 103
def move t, a
  Array(t).map { |s|
    inverted[s].keys.compact.find_all { |sym|
      sym === a
    }.map { |sym| inverted[s][sym] }
  }.flatten.uniq
end

# File lib/journey/nfa/transition_table.rb, line 43
def states
  (@table.keys + @table.values.map(&:keys).flatten).uniq
end

# File lib/journey/nfa/transition_table.rb, line 136
def transitions
  @table.map { |to, hash|
    hash.map { |from, sym| [from, sym, to] }
  }.flatten(1)
end