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

public class PrimeImplicantChart
{
  List<List<Boolean>> chart;
  List<Integer> terms;
  List<Implicant> primes;

  /* Build a new prime implicant chart from the terms ts and the prime
   * implicants ps */
  public PrimeImplicantChart(List<Integer> ts, Set<Implicant> ps)
  {
    /* Create local copies of the lists */
    terms = new LinkedList<Integer>(ts);
    primes = new LinkedList<Implicant>(ps);

    int numTerms = terms.size();
    int numPrimes = primes.size();

    /* Sort the terms.  This sorted property could be useful, but is not used in
     * the baseline implementation. */
    Collections.sort(terms);

    chart = new Vector<List<Boolean>>();

    /* Mark the intersection in the chart where a given prime implicant covers a
     * given term. */
    for (Implicant imp : primes) {
      Vector<Boolean> row = new Vector<Boolean>();
      chart.add(row);
      for (Integer t : terms) {
        row.add(new Boolean(imp.covers(t.intValue())));
      }
    }
  }

  /* Find a minimum cover for the function that this prime implicant chart was
   * constructed for. */
  public Set<Implicant> minimumCover()
  {
    Set<Implicant> cover = new HashSet<Implicant>();
    return minCoverHelper(0, cover);
  }

  /* This min cover implementation is potentially very inefficient: it tries
   * every possible subset of the prime implicants.  In the worst case, this
   * algorithm takes time proportional to 2 to the number of prime implicants.
   * It will find the smallest set possible, though. */
  private Set<Implicant> minCoverHelper(int implicantIdx, Set<Implicant> candidateCover)
  {
    /* If we have found a subset of the prime implicants that cover the
     * function, return a copy of that subset. */
    if (setCovers(candidateCover)) {
      return new HashSet<Implicant>(candidateCover);
    }
    /* If we have reached the end of our prime implicants list without covring
     * the function, we have failed and return null. */
    if (implicantIdx >= primes.size()) {
      return null;
    }

    /* Get the prime implicant that is at "implicantIdx" in our list of prime
     * implicants, and try to find covers that either do not or do include this
     * prime. */
    Implicant thisPrime = primes.get(implicantIdx);
    Set<Implicant> cover0 = minCoverHelper(implicantIdx + 1, candidateCover);
    candidateCover.add(thisPrime);
    Set<Implicant> cover1 = minCoverHelper(implicantIdx + 1, candidateCover);
    candidateCover.remove(thisPrime);

    if (cover0 == null)
      return cover1;
    if (cover1 == null)
      return cover0;
    if (cover0.size() > cover1.size())
      return cover1;
    else
      return cover0;
  }

  /* This method determines whether a set of prime implicants covers the
   * function that this chart was built to implement. */
  private boolean setCovers(Set<Implicant> candidateCover)
  {
    /* For all terms ... */
    for (Integer t : terms) {
      /* ... does there exist a prime in the set that covers it? */
      boolean foundCover = false;
      for (Implicant imp : candidateCover) {
        if (imp.covers(t.intValue())) {
          foundCover = true;
          break;
        }
      }
      if (!foundCover)
        return false;
    }
    return true;
  }
}