package javakurs.uebung10;

import java.io.BufferedWriter;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import javakurs.musterloesung.uebung08.DirectedGraph;
import javakurs.musterloesung.uebung08.Edge;

/**
 * {@link FiniteAutomatonBase} represents a finite automaton. The underlying data
 * structure is a directed graph.
 *
 * @param <EdgeInfo>
 *          the kind of edge info used in the graph
 *
 * @author Bernd Kiefer, DFKI
 * @author Joerg Steffen, DFKI
 * @version $Id$
 */
public abstract class FiniteAutomatonBase<EdgeInfo> {

  /**
   * This contains the representation of an epsilon transition.
   */
  protected EdgeInfo epsilon = null;

  /**
   * This contains the underlying directed graph with which the automaton is
   * represented.
   */
  protected DirectedGraph<EdgeInfo> graph;

  /**
   * This contains the comparator to compare EdgeInfo, used in
   * determinization of the automaton.
   */
  protected Comparator<EdgeInfo> comp;

  /**
   * This contains the node representing the initial state of the automaton.
   */
  private int initialState;

  /**
   * This contains the collection of final states of the automaton.
   */
  private BitSet finalStates;

  /**
   * This contains the symbols of the input alphabet.
   */
  private Collection<EdgeInfo> alphabet;


  /**
   * This creates a new instance of {@link FiniteAutomatonBase} with no states.
   */
  public FiniteAutomatonBase() {

    // init directed graph
    this.graph = new DirectedGraph<EdgeInfo>();
    // init initial and final states
    this.initialState = -1;
    this.finalStates = new BitSet();
    // init alphabet
    this.setAlphabet(new HashSet<EdgeInfo>());
  }


  /**
   * This returns the initial state of the automaton.
   *
   * @return the initial state of the automaton
   */
  public int getInitialState() {

    return this.initialState;
  }

  /**
   * This sets the initial state to the given parameter.
   *
   * @param initialState
   *          the initial state of the automaton
   */
  protected void setInitialState(int initialState) {

    this.initialState = initialState;
  }


  /**
   * This marks the given state as a final state.
   *
   * @param finalState
   *          the state to be marked as final
   */
  protected void setFinalState(int finalState) {

    this.finalStates.set(finalState);
  }

  /**
   * This marks the given state as a non-final state.
   *
   * @param nonFinalState
   *          the state to be marked as non-final
   */
  protected void setNonFinalState(int nonFinalState) {

    this.finalStates.clear(nonFinalState);
  }

  /**
   * This checks if the given state is a final state.
   *
   * @param state
   *          the state to check
   * @return {@code true} if that is the case
   */
  public boolean isFinalState(int state) {

    return this.finalStates.get(state);
  }


  /**
   * This returns the symbols of the input alphabet.
   *
   * @return the symbols of the input alphabet
   */
  public Collection<EdgeInfo> getAlphabet() {

    return this.alphabet;
  }

  /**
   * This sets the input alphabet to the given parameter.
   *
   * @param alphabet
   *          the symbols of the input alphabet
   */
  private void setAlphabet(Collection<EdgeInfo> alphabet) {

    this.alphabet = alphabet;
  }


  /**
   * This sets the comparator to compare EdgeInfo to the given parameter.
   *
   * @param comp
   *          a comparator to compare {@code EdgeInfo}
   */
  protected void setComparator(Comparator<EdgeInfo> comp) {

    this.comp = comp;
  }


  /**
   * This creates a new state in the automaton.
   *
   * @return an int with the newly created state
   */
  public int createNewState() {

    return this.graph.newVertex();
  }


  /**
   * This creates a new transition in the automaton.
   *
   * @param transChar
   *          the alphabet symbol of the transition
   * @param startState
   *          the start state of the transition
   * @param endState
   *          the end state of the transition
   * @return an edge with the newly created transition
   */
  public Edge<EdgeInfo> createNewTransition(
      EdgeInfo transChar, int startState, int endState) {

    // only add transChar to alphabet if it is not Epsilon
    if (transChar != this.epsilon) {
      this.getAlphabet().add(transChar);
    }

    return this.graph.newEdge(transChar, startState, endState);
  }


  /**
   * This constructs an automaton that matches the given "character".
   *
   * @param edgeInfo
   *          the edge info with the character
   * @return the subautomaton matching the given character
   */
  protected abstract SubAutomaton newCharAutomaton(EdgeInfo edgeInfo);


  /**
   * This constructs an automaton that matches a set of "characters"
   *
   * @param chars
   *          a set of edge info with the respective characters
   * @return the subautomaton matching the given characters
   */
  protected abstract SubAutomaton newCharSetAutomaton(Set<EdgeInfo> chars);


  /**
   * This concatenates the given subautomatons. The first subautomaton is
   * modified so that it contains the resulting subautomaton.
   *
   * @param lhs
   *          the left hand side subautomaton
   * @param rhs
   *          the right hand side subautomaton to concatenate with the lhs
   *          subautomaton
   * @return the modified lhs subautomaton with the concatenated subautomatons
   */
  public abstract SubAutomaton concatenate(SubAutomaton lhs, SubAutomaton rhs);


  /**
   * This creates a subautomaton that matches the language of the given lhs
   * subautomaton or the the language of the given rhs subautomaton. To do this,
   * the lhs subautomaton is modified.
   *
   * @param lhs
   *          the subautomaton with the left hand side of the alternative
   * @param rhs
   *          the subautomaton with the right hand side of the alternative
   * @return the modified lhs subautomaton with the alternative subautomaton
   */
  public abstract SubAutomaton alternative(SubAutomaton lhs, SubAutomaton rhs);


  /**
   * This modifies the given subautomaton in a way that it matches an arbitrary
   * number (including zero) of the char sequences it matches now.
   *
   * @param sub
   *          a subautomaton to wrap with a kleene star
   * @return the modified subautomaton with the kleene
   */
  public abstract SubAutomaton kleene(SubAutomaton sub);


  /**
   * {@inheritDoc}
   */
  @Override
  public String toString() {

    String newline = System.getProperty("line.separator");

    StringBuilder strRep = new StringBuilder();

    strRep.append("alphabet: ").append(newline)
      .append(this.getAlphabet()).append(newline);
    strRep.append("initial state: ").append(newline)
      .append(this.getInitialState()).append(newline);

    List<Integer> fstates =
      new ArrayList<Integer>(this.finalStates.cardinality());
    for (int i = this.finalStates.nextSetBit(0); i >= 0;
        i = this.finalStates.nextSetBit(i + 1)) {
      fstates.add(i);
    }
    strRep.append("final states: ").append(newline);
    for (int oneNode : fstates) {
      strRep.append(oneNode).append(newline);
    }
    strRep.append("transitions: ").append(newline);

    for (int v = 0; v < this.graph.getNumberOfVertices(); ++v) {
      if (this.graph.isVertex(v)) {
        for (Edge<EdgeInfo> oneOutEdge : this.graph.getOutEdges(v)) {
          strRep.append(oneOutEdge.toString()).append(newline);
        }
      }
    }

    return strRep.toString();
  }


  /**
   * This writes this graph in vcg format to the given file so that it can be
   * processed with the VCG tool.
   * (http://rw4.cs.uni-sb.de/users/sander/html/gsvcg1.html)
   *
   * @param fileName
   *          the file name
   * @throws IOException
   *           if an error occurs when writing the file
   */
  public void vcgPrint(String fileName)
      throws IOException {

    PrintWriter out =
      new PrintWriter(
        new BufferedWriter(
          new OutputStreamWriter(
            new FileOutputStream(fileName))));
    out.println("graph: { orientation: left_to_right display_edge_labels: yes");

    for (int v = 0; v < this.graph.getNumberOfVertices(); ++v) {
      if (this.graph.isVertex(v)) {
        out.print("node: { title: \"" + v + "\" ");
        if (v == this.initialState) {
          out.print("color: green ");
        }
        if (this.isFinalState(v)) {
          out.print("bordercolor: red ");
        }
        out.println("}");
      }

      if (this.graph.getOutEdges(v) != null) {
        for (Edge<EdgeInfo> edge : this.graph.getOutEdges(v)) {
          EdgeInfo transChar = edge.getEdgeInfo();
          out.println("edge: { sourcename: \""
            + edge.getStartVertex()
            + "\" targetname: \""
            + edge.getEndVertex()
            + "\" label: ");
          if (transChar == this.epsilon) {
            out.println("\"e\" textcolor:red }");
          }
          else {
            out.println("\"" + edge.getEdgeInfo() + "\" }");
          }
        }
      }
    }

    out.println("}");
    out.close();
  }


  /**
   * This writes this graph in dot format to the given file so that it can be
   * processed with the graphviz tool. (http://www.graphviz.org/)
   *
   * @param fileName
   *          the file name
   * @throws IOException
   *           if an error occurs when writing the file
   */
  public void dotPrint(String fileName)
      throws IOException {

    PrintWriter out =
      new PrintWriter(
        new BufferedWriter(
          new OutputStreamWriter(
            new FileOutputStream(fileName))));
    out.println("digraph test { ");

    for (int v = 0; v < this.graph.getNumberOfVertices(); ++v) {
      if (this.graph.isVertex(v)) {
        out.print("n" + v);
        boolean started = false;
        if (v == this.initialState) {
          if (!started) {
            started = true;
            out.print("[");
          }
          out.print(" color=green ");
        }
        if (this.isFinalState(v)) {
          if (!started) {
            started = true;
            out.print("[");
          }
          else {
            out.print(",");
          }
          out.print(" fontcolor=red ");
        }
        if (started) {
          out.print("]");
        }
        out.println(";");
      }
    }

    for (int v = 0; v < this.graph.getNumberOfVertices(); ++v) {
      if (this.graph.isVertex(v) && this.graph.getOutEdges(v) != null) {
        for (Edge<EdgeInfo> edge : this.graph.getOutEdges(v)) {
          EdgeInfo transChar = edge.getEdgeInfo();
          out.print("n"
            + edge.getStartVertex()
            + " -> n"
            + edge.getEndVertex()
            + "[ label= ");
          if (transChar == this.epsilon) {
            out.println("\"eps\", fontcolor=red];");
          }
          else {
            out.println("\"" + edge.getEdgeInfo() + "\"];");
          }
        }
      }
    }
    out.println("}");
    out.close();
  }


  /**
   * This computes a deterministic automaton that accepts the same language as
   * this non-deterministic automaton. The given automaton will contain the
   * result DFA.
   *
   * @param detAutomaton
   *          a finite automaton that will hold the resulting DFA; must be a
   *          fresh automaton and is passed as parameter to make it possible to
   *          use this method for subclasses
   */
  protected abstract void determinize(
      FiniteAutomatonBase<EdgeInfo> detAutomaton);


  /**
   * {@link SubAutomaton} is a simple implementation of a subautomaton that only
   * manages a single initial and final state.
   */
  public class SubAutomaton {

    /**
     * This contains the initial state of the subautomaton.
     */
    private int iState;

    /**
     * This contains the single final state of the subautomaton
     */
    private int fState;


    /**
     * This creates a new instance of {@link SubAutomaton} where the initial
     * state is also the final state.
     */
    public SubAutomaton() {

      this.iState = FiniteAutomatonBase.this.createNewState();
      this.fState = this.iState;
    }


    /**
     * This returns the initial state.
     *
     * @return the initial state
     */
    public int getInitialState() {

      return this.iState;
    }


    /**
     * This sets the initial state to the given state
     *
     * @param newInitialState
     *          the initial state
     */
    public void setInitialState(int newInitialState) {

      this.iState = newInitialState;
    }


    /**
     * This returns the final state.
     *
     * @return the final state
     */
    public int getFinalState() {

      return this.fState;
    }


    /**
     * This sets the final state to the given state.
     *
     * @param newFinalState
     *          the final state
     */
    public void setFinalState(int newFinalState) {

      this.fState = newFinalState;
    }
  }
}
