import java.util.Vector;
import java.util.Map;
import java.util.HashMap;

public class ImplicationChart
{
  // tableRef is simply a reference to the state table that this ImplicantChart
  // came from.
  StateTable tableRef;
  // The cells of the implication chart are stored in a 2D array of booleans.
  // False means the pair of states used to index into the array might be
  // mergeable (or are definitely mergeable, if we've reached the end of the
  // algorithm).  True means the pair of states is incompatible.
  // This array is wasteful in the sense that we only need 1/2 * (size^2) cells
  // to represent all possible pairs of states, but this array has size^2 cells.
  // For the purposes of this exercise, that waste is worth not having to code a
  // more complicated data structure.
  public boolean [][] cells;

  // Build an initialized implication chart from a state table.
  public ImplicationChart(StateTable t)
  {
    tableRef = t;

    // Notice the funny indexing here.  In my solution, I ensure that the first
    // index is always smaller than the second.  I did this so that my code
    // doesn't get confused between the two possible cells for the state pair
    // X,Y (cells[X][Y] and cells[Y][X]).
    cells = new boolean[t.size][t.size];
    for (int i = 0; i < t.size - 1; i++) {
      for (int j = t.size - 1; j > i; j--) {
        cells[i][j] = false;
      }
    }
  }

  // The main minimization method.
  public StateTable minimizeFSM()
  {
    System.out.println("Initial implication chart:\n"+this);
    markOutputMismatches();
    System.out.println("Implication chart after marking output incompatibilities:\n"+this);
    markNextStateMismatches();
    System.out.println("Implication chart after marking next state incompatibilities:\n"+this);
    StateTable s = buildNewStateTable();
    return s;
  }

  // This method finds all pairs of states with outputs that don't match, and
  // marks the appropriate cells.
  private void markOutputMismatches()
  {
    for (int sA = 0; sA < tableRef.size - 1; sA++) {
      StateTableRow stA = tableRef.rows[sA];
      for (int sB = tableRef.size - 1; sB > sA; sB--) {
        StateTableRow stB = tableRef.rows[sB];
        for (int i = 0; i < (tableRef.isMooreStyle ? 1 : tableRef.numInputs); i++) {
          if (!(stA.output[i] == stB.output[i])) {
            cells[sA][sB] = true;
            break;
          }
        }
      }
    }
  }

  
  // This method iteratively finds all pairs of states for which some input
  // value makes them transition to a pair of incompatible states, and marks
  // them as incompatible.
  private void markNextStateMismatches()
  {
    boolean changed;
    do {
      changed = false;
      for (int sA = 0; sA < tableRef.size - 1; sA++) {
        StateTableRow stA = tableRef.rows[sA];
        for (int sB = tableRef.size - 1; sB > sA; sB--) {
          if (cells[sA][sB])
            continue;

          StateTableRow stB = tableRef.rows[sB];
          boolean mismatch = false;
          for (int i = 0; i < tableRef.numInputs; i++) {
            int nsA = stA.nextState[i];
            int nsB = stB.nextState[i];
            if (nsA == nsB)
              continue;
            int ns0 = Math.min(nsA, nsB);
            int ns1 = Math.max(nsA, nsB);
            if (cells[ns0][ns1]) {
              mismatch = true;
              break;
            }
          }
          if (mismatch) {
            cells[sA][sB] = true;
            changed = true;
          }
        }
      }
    } while (changed);
  }

  private StateTable buildNewStateTable()
  {
    // After merging states, we will have fewer total states, so we have to
    // decide how to map state numbers from the old state table into state
    // numbers in the new state table.  The next chunk of code builds up one
    // reasonable mapping that you can use.
    int [] oldStateNewState = new int[tableRef.size];
    for (int s = 0; s < tableRef.size; s++)
      oldStateNewState[s] = s;
    int numMerged = 0;
    for (int sB = 1; sB < tableRef.size; sB++) {
      for (int sA = 0; sA < sB; sA++) {
        if (!cells[sA][sB]) {
          oldStateNewState[sB] = oldStateNewState[sA];
          numMerged++;
          break;
        }
      }
      if (oldStateNewState[sB] == sB) {
        oldStateNewState[sB] = sB - numMerged;
      }
      //System.out.println("osns "+sB+" "+oldStateNewState[sB]+" nm:"+numMerged);
    }

    int newSize = tableRef.size - numMerged;

    StateTable newFSM = new StateTable();
    newFSM.setSize(newSize);
    newFSM.isMooreStyle = tableRef.isMooreStyle;
    newFSM.numInputs    = tableRef.numInputs;
    newFSM.numOutputs   = tableRef.numOutputs;

    for (int s = 0, idx = 0; s < tableRef.size; s++) {
      if (oldStateNewState[s] >= idx) {
        StateTableRow oldRow = tableRef.rows[s];
        StateTableRow r = new StateTableRow(newFSM);
        for (int i = 0; i < newFSM.numInputs; i++) {
          r.nextState[i] = oldStateNewState[oldRow.nextState[i]];
        }
        for (int i = 0; i < (newFSM.isMooreStyle ? 1 : newFSM.numInputs); i++) {
          r.output[i] = oldRow.output[i];
        }
        newFSM.rows[idx] = r;
        idx++;
      }
    }

    return newFSM;
  }

  public String toString()
  {
    StringBuffer s = new StringBuffer();
    for (int sA = tableRef.size - 2; sA >= 0; sA--) {
      s.append("" + sA + " ");
      for (int sB = tableRef.size - 1; sB > sA; sB--) {
        s.append(cells[sA][sB] ? "X" : "O");
      }
      s.append("\n");
    }
    s.append("  ");
    for (int sB = tableRef.size - 1; sB > 0; sB--) {
      s.append(""+sB);
    }
    return s.toString();
  }
}