class Kleene::MultiMatchDFA

def create_composite_nfa(nfas)
  nfa = union!(nfas)
  # add epsilon transitions from all the states except the start state back to the start state
  nfa.states.each do |state|
    if state != nfa.start_state
      nfa.add_transition(NFATransition::Epsilon, state, nfa.start_state)
    end
  end
  nfa.update_final_states
  nfa
end

def initialize(nfas)
  composite_alphabet = nfas.reduce(Set.new) {|memo, nfa| memo | nfa.alphabet }
  @original_nfas = nfas
  @nfas_with_err_state = nfas.map {|nfa| with_err_dead_end(nfa, composite_alphabet) }     # copy NFAs and add dead-end error states to each of them
  dfas = @original_nfas.map(&:to_dfa)
  @nfa_to_index = @original_nfas.map.with_index {|nfa, index| [nfa, index] }.to_h
  @nfa_with_dead_err_to_index = @nfas_with_err_state.map.with_index {|nfa, index| [nfa, index] }.to_h
  @dfa_to_index = dfas.map.with_index {|dfa, index| [dfa, index] }.to_h
  @machines_by_index = @original_nfas.zip(nfas_with_err_state, dfas).map.with_index {|tuple, index| nfa, nfa_with_dead_err, dfa = tuple; [index, MachineTuple.new(nfa, nfa_with_dead_err, dfa)] }.to_h
  # build a mapping of (state -> nfa) pairs that capture which nfa owns each state
  @dead_end_nfa_state_to_dead_end_nfa = Hash.new
  @nfas_with_err_state.each do |nfa_with_dead_err|
    nfa_with_dead_err.states.each do |state|
      @dead_end_nfa_state_to_dead_end_nfa[state] = nfa_with_dead_err
    end
  end
  # create a composite NFA as the union of all the NFAs with epsilon transitions from every NFA state back to the union NFA's start state
  @composite_nfa = create_composite_nfa(@nfas_with_err_state)
  @composite_dfa = @composite_nfa.to_dfa
end

def machines_from_dfa(dfa) # : MachineTuple
  machines_by_index[dfa_to_index[dfa]]
end

def machines_from_nfa(nfa) # : MachineTuple
  machines_by_index[nfa_to_index[nfa]]
end

def machines_from_nfa_with_dead_err(nfa_with_dead_err) # : MachineTuple
  machines_by_index[nfa_with_dead_err_to_index[nfa_with_dead_err]]
end