import java.util.Iterator;
import java.util.List;
import java.util.LinkedList;

/* An implicant is just an ordered list of bits, which can be "1", "0" or "-".
 * The length of the list is always equal to the number of variables in the
 * function */
public class Implicant
{
  private List<Bit> implicant;

  public List<Bit> bits() { return implicant; }

  /* Build an implicant that represent just one term. */
  public Implicant(int term, int numVars) {
    implicant = new LinkedList<Bit>();
    /* For each variable, decide whether it should be a zero or a one based on
     * one of the bits in the term. */
    for (int v = 0; v < numVars; v++) {
      int bit = term % 2;
      if (bit == 1)
        implicant.add(new BitOne());
      else
        implicant.add(new BitZero());
      term = term >> 1;
    }
  }

  /*
   * Build a new implicant by merging two implicants that are off by one
   */
  public Implicant(Implicant imp0, Implicant imp1)
  {
    implicant = new LinkedList<Bit>();

    Iterator<Bit> iter0 = imp0.implicant.iterator();
    Iterator<Bit> iter1 = imp1.implicant.iterator();

    while (iter0.hasNext() && iter1.hasNext()) {
      Bit bit0 = iter0.next();
      Bit bit1 = iter1.next();
      implicant.add(bit0.merge(bit1));
    }
  }

  /* Count the number of ones in this implicant */
  public int numOnes() {
    int ones = 0;

    for (Bit b : implicant) {
      if (b instanceof BitOne)
        ones++;
    }

    return ones;
  }

  /* Compare this implicant to another implicant, bit-by-bit, and decide if they
   * are "off by one" in the Quine-McCluskey sense. */
  public boolean offByOne(Implicant other)
  {
    Iterator<Bit> thisIter = implicant.iterator();
    Iterator<Bit> otherIter = other.implicant.iterator();

    int numOneZeros = 0;

    while (thisIter.hasNext() && otherIter.hasNext()) {
      Bit thisBit = thisIter.next();
      Bit otherBit = otherIter.next();
      /* If one of the bits is a "both bit" (-), then they both have to be. */
      if (thisBit.bothConflict(otherBit)) {
        return false;
      }
      if (thisBit.oneZero(otherBit))
        numOneZeros++;
    }
    if (thisIter.hasNext() || otherIter.hasNext())
      return false;
    return numOneZeros == 1;
  }

  /* One implicant is a subset of another implicant if wherever the other
   * implicant has a 1 or 0 bit, this implicant has the same bit, and wherever
   * the other implicant has a -, this implicant can have anything. */
  public boolean subset(Implicant other)
  {
    Iterator<Bit> thisIter = implicant.iterator();
    Iterator<Bit> otherIter = other.implicant.iterator();

    while (thisIter.hasNext() && otherIter.hasNext()) {
      Bit thisBit = thisIter.next();
      Bit otherBit = otherIter.next();
      if (!thisBit.subset(otherBit))
        return false;
    }
    if (thisIter.hasNext() || otherIter.hasNext())
      return false;
    return true;
  }

  /* Two implicant are equal if their bits match up perfectly, 0 with 0, 1 with
   * 1, and - with -. */
  public boolean equals(Implicant other) {
    Iterator<Bit> thisIter = implicant.iterator();
    Iterator<Bit> otherIter = other.implicant.iterator();

    while (thisIter.hasNext() && otherIter.hasNext()) {
      Bit thisBit = thisIter.next();
      Bit otherBit = thisIter.next();
      if (!thisBit.equals(otherBit))
        return false;
    }
    if (thisIter.hasNext() || otherIter.hasNext())
      return false;
    return true;
  }

  /*
   * covers returns true iff this implicant covers the term "term"
   */
  public boolean covers(int term) {
    for (Bit b : implicant) {
      if (!b.covers(term % 2))
        return false;
      term = term >> 1;
    }
    return true;
  }

  public String toString()
  {
    StringBuffer s = new StringBuffer();
    for (Bit b : implicant) {
      s.append(b.toString());
    }
    s.reverse();
    return s.toString();
  }
}