import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.LinkedList;

public class ImplicationTable
{
  private List<Column> table;
  public int numVars;

  /*
   * Build the implication table by creating the first column from the minterms
   * and don't cares, and then creating subsequent columns from previous columns
   */
  public ImplicationTable(int nv, List<Integer> terms)
  {
    table = new LinkedList<Column>();
    numVars = nv;
    /* Call the Column constructor with the initial set of terms */
    table.add(new Column(terms, this));
    /* Add each subsequent column to the table.  Since the number of groups
     * decreases by 1 as we move to the right in the table, we can be sure that
     * there will be at most numVars + 1 columns in the table. */
    for (int i = 0; i < numVars; i++) {
      table.add(new Column(table.get(i)));
    }
  }

  /* This method scans through a built implication tables, looking for prime
   * implicants. */
  public Set<Implicant> getPrimeImplicants()
  {
    Set<Implicant> primes = new HashSet<Implicant>();
    // reverse the table, so we get the right-most column first
    LinkedList<Column> revTable = new LinkedList<Column>();
    for (Column c : table) {
      revTable.addFirst(c);
    }
    // Traverse the table from right to left, adding each implicant to our set
    // of primes only if there is not already an implicant that is strictly
    // larger than it in the primes set already
    for (Column c : revTable) {
      for (Group g : c.groups()) {
        for (Implicant candidate : g.implicants()) {
          boolean addCandidate = true;
          for (Implicant prime : primes) {
            if (candidate.subset(prime)) {
              addCandidate = false;
              break;
            }
          }
          if (addCandidate)
            primes.add(candidate);
        }
      }
    }
    return primes;
  }
}