package javakurs.musterloesung.uebung10;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import javakurs.musterloesung.uebung08.Edge;


/**
 * {@link FiniteAutomaton} implements the abstract methods of
 * {@link FiniteAutomatonBase}.
 *
 * @param <EdgeInfo>
 *          the kind of edge info used in the graph
 *
 * @author Joerg Steffen, DFKI
 * @version $Id: FiniteAutomaton.java,v 1.3 2011/01/26 15:49:05 steffen Exp $
 */
public class FiniteAutomaton<EdgeInfo> extends FiniteAutomatonBase<EdgeInfo> {

  /**
   * {@inheritDoc}
   */
  @Override
  protected SubAutomaton newCharAutomaton(EdgeInfo edgeInfo) {

    SubAutomaton subAuto = new SubAutomaton();
    // create a new state
    int newState = this.createNewState();
    // connect the new state and the initial state
    this.createNewTransition(edgeInfo, subAuto.getInitialState(), newState);
    // the new state is the new final state of the subautomaton
    subAuto.setFinalState(newState);

    return subAuto;
  }


  /**
   * {@inheritDoc}
   */
  @Override
  protected SubAutomaton newCharSetAutomaton(Set<EdgeInfo> chars) {

    SubAutomaton subAuto = new SubAutomaton();
    // create a new state
    int newState = this.createNewState();
    // get initial state
    int initState = subAuto.getInitialState();
    // connect the new state and the initial state
    for (EdgeInfo c : chars) {
      // link states according to slides
      this.createNewTransition(c, initState, newState);
    }
    // the new state is the new final state
    subAuto.setFinalState(newState);

    return subAuto;
  }


  /**
   * {@inheritDoc}
   */
  @Override
  public SubAutomaton concatenate(SubAutomaton lhs, SubAutomaton rhs) {

    // merge the final state of the first automaton with the initial state of
    // the second automaton:
    // all outgoing edges of the initial state of the second automaton must
    // start at the final state of the first automaton

    // copy list to avoid ConcurrentModificationException
    List<Edge<EdgeInfo>> rhsOutEdges =
      new ArrayList<Edge<EdgeInfo>>(
          this.graph.getOutEdges(rhs.getInitialState()));
    for (Edge<EdgeInfo> edge : rhsOutEdges) {
      this.graph.changeStartVertex(edge, lhs.getFinalState());
    }
    // delete old initial state
    this.graph.removeVertex(rhs.getInitialState());
    // update final state
    lhs.setFinalState(rhs.getFinalState());

    // make sure rhs is empty now
    rhs.setInitialState(-1);
    rhs.setFinalState(-1);

    return lhs;
  }


  /**
   * {@inheritDoc}
   */
  @Override
  public SubAutomaton alternative(SubAutomaton lhs, SubAutomaton rhs) {

    // created new initial and final state
    int newInitialState = this.createNewState();
    int newFinalState = this.createNewState();

    // link states according to slides
    this.createNewTransition(
      this.epsilon, newInitialState, lhs.getInitialState());
    this.createNewTransition(
      this.epsilon, newInitialState, rhs.getInitialState());
    this.createNewTransition(
      this.epsilon, lhs.getFinalState(), newFinalState);
    this.createNewTransition(
      this.epsilon, rhs.getFinalState(), newFinalState);

    // define new initial and final state in the result automaton
    lhs.setInitialState(newInitialState);
    lhs.setFinalState(newFinalState);

    // make sure rhs is empty now
    rhs.setInitialState(-1);
    rhs.setFinalState(-1);

    return lhs;
  }


  /**
   * {@inheritDoc}
   */
  @Override
  public SubAutomaton kleene(SubAutomaton sub) {

    // create new initial and final states
    int newInitialState = this.createNewState();
    int newFinalState = this.createNewState();

    // connect new initial and final state with an epsilon transition
    this.createNewTransition(
      this.epsilon, newInitialState, newFinalState);
    // connect the old final and initial state with an epsilon transition
    this.createNewTransition(
      this.epsilon, sub.getFinalState(), sub.getInitialState());
    // connect the new states to the former initial and final state
    this.createNewTransition(
      this.epsilon, newInitialState, sub.getInitialState());
    this.createNewTransition(
      this.epsilon, sub.getFinalState(), newFinalState);

    // update initial state and final state
    sub.setInitialState(newInitialState);
    sub.setFinalState(newFinalState);

    return sub;
  }


  /**
   * This expands the given set of states of the non-deterministic automaton
   * with all states that can be reached via epsilon transitions.
   *
   * @param nfaStateSet
   *          a set of states of the non-deterministic automaton
   */
  private void expandWithEpsilonClosure(Set<Integer> nfaStateSet) {

    // store all states to process in a queue
    Queue<Integer> toCheck = new LinkedList<Integer>(nfaStateSet);

    // loop until the queue is empty
    while (!(toCheck.size() == 0)) {
      // get top element from queue
      int currentState = toCheck.remove();
      // get all states that can be reached via epsilon transition
      Collection<Edge<EdgeInfo>> epsilonEdges =
        this.graph.findEdges(currentState, this.epsilon, this.comp);
      // expand state set and update toCheck
      for (Edge<EdgeInfo> oneEdge : epsilonEdges) {
        int targetState =  oneEdge.getEndVertex();
        if (!nfaStateSet.contains(targetState)) {
          nfaStateSet.add(targetState);
          toCheck.add(targetState);
        }
      }
    }
  }


  /**
   * This returns the set of states of the non-deterministic automaton that can
   * be reached from the given states via the given transition character.
   *
   * @param nfaStateSet
   *          a set of states of the non-deterministic automaton
   * @param transChar
   *          the transition character
   * @return a set of reachable states
   */
  private Set<Integer> move(Set<Integer> nfaStateSet, EdgeInfo transChar) {

    // init result set
    Set<Integer> targetStates = new HashSet<Integer>();

    for (int oneState : nfaStateSet) {
      // get all edges with the transition character
      Collection<Edge<EdgeInfo>> outEdges =
        this.graph.findEdges(oneState, transChar, this.comp);
      // add target states of these edges to result
      for (Edge<EdgeInfo> oneEdge : outEdges) {
        targetStates.add(oneEdge.getEndVertex());
      }
    }

    return targetStates;
  }


  /**
   * This checks if the given set of states of the non-deterministic automaton
   * contains any final state.
   *
   * @param nfaStateSet
   *          a set of states of the non-deterministic automaton
   * @return a flag indicating if any final state is found
   */
  private boolean containsFinal(Set<Integer> nfaStateSet) {

    for (int oneState : nfaStateSet) {
      if (this.isFinalState(oneState)) {
        return true;
      }
    }
    return false;
  }


  /**
   * This initializes the queue of unmarked DFA states, represented by sets of
   * NFA states.
   *
   * @param nfa2dfaStates
   *          a map that maps NFA state sets to a single state of the DFA
   * @param detAutomaton
   *          a finite automaton with the deterministic automaton
   * @return a queue with a single unmarked DFA state that is the initial state
   */
  private Queue<Set<Integer>> initUnmarkedStates(
      Map<Set<Integer>, Integer> nfa2dfaStates,
      FiniteAutomatonBase<EdgeInfo> detAutomaton) {

    // init
    Queue<Set<Integer>> unmarkedStates = new LinkedList<Set<Integer>>();

    // get epsilon closure of initial NFA state; this corresponds to the initial
    // state of the DFA
    Set<Integer> initialEpsClosure = new HashSet<Integer>();
    initialEpsClosure.add(this.getInitialState());
    this.expandWithEpsilonClosure(initialEpsClosure);

    // take the initial DFA state and map it to the epsilon closure of the
    // NFA initial state
    int dfaInitState = detAutomaton.createNewState();
    detAutomaton.setInitialState(dfaInitState);
    nfa2dfaStates.put(initialEpsClosure, dfaInitState);

    // add the initial DFA state to the final states if the NFA state set
    // contains a final state
    if (this.containsFinal(initialEpsClosure)) {
      detAutomaton.setFinalState(dfaInitState);
    }

    // add the state to unmarked: since every new DFA state will only be marked
    // once, we implement this using a queue of states; marking will then be
    // equivalent to removing the state from the unmarked state queue
    // marked states of the DFA are represented by the corresponding set of NFA
    // states
    unmarkedStates.add(initialEpsClosure);

    return unmarkedStates;
  }


  /**
   * {@inheritDoc}
   */
  @Override
  protected void determinize(FiniteAutomatonBase<EdgeInfo> detAutomaton) {

    // this maps NFA state sets to a single state of the DFA
    Map<Set<Integer>, Integer> nfa2dfaStates =
      new HashMap<Set<Integer>, Integer>();

    // this contains the set of unmarked DFA states, represented by the
    // corresponding NFA state sets
    Queue<Set<Integer>> unmarkedStates =
      this.initUnmarkedStates(nfa2dfaStates, detAutomaton);

    // is there still a new DFA state we have to handle?
    while (!unmarkedStates.isEmpty()) {

      // this set of NFA states represents a single DFA state
      Set<Integer> nfaStateSet = unmarkedStates.remove();
      // this is the corresponding DFA state
      int dfaState = nfa2dfaStates.get(nfaStateSet);

      // iterate over every transition character used in this automaton
      for (EdgeInfo oneChar : this.getAlphabet()) {
        // compute the set of states that can be reached from the NFA states in
        // nfaStateSet over a transition with character oneChar
        Set<Integer> transNfaStateSet = this.move(nfaStateSet, oneChar);
        // and do the epsilon closure of this set
        this.expandWithEpsilonClosure(transNfaStateSet);
        // if no state can be reached, we just continue
        if (transNfaStateSet.isEmpty()) {
          continue;
        }

        // this new subset of NFA states is either a known or a new state
        // of the DFA
        Integer transDfaState = nfa2dfaStates.get(transNfaStateSet);
        if (transDfaState == null) {
          // this subset represents a new DFA node, add a new node to the
          // deterministic automaton
          transDfaState = detAutomaton.createNewState();
          // add the new state to the final states if the NFA state set
          // contains a final state
          if (this.containsFinal(transNfaStateSet)) {
            detAutomaton.setFinalState(transDfaState);
          }
          // created mapping from NFA state set to DFA state
          nfa2dfaStates.put(transNfaStateSet, transDfaState);
          // this node still has to be handled, so add it to the "unmarked" list
          unmarkedStates.add(transNfaStateSet);
        }
        // add the newly computed transition to the resulting DFA
        detAutomaton.createNewTransition(oneChar, dfaState, transDfaState);
      }
    }
  }
}
