/**
 * Original version by Jaymin Patel
 * This version by Peter McBrien
 */
class Difference {
  public static Table execDiff(Table A, Table B) {
    Table R = new Table(); /* output table */
    boolean format = AuxFuncs.sameFormat( A.getCol(), B.getCol() );
    //System.out.println("format="+format);
    if (format)
      R = execute(A, B);
    else {
      CatchErr.formatErr("MINUS");
      R=A;
    }
    
    return R;
  }

  public static Table execute(Table A, Table B) {
    /* We assume that tables A and B are of same format i.e have the same columns */

    Table R = new Table(); /* output table */

    R.setCol(A.getCol()); /* set R's column information to that of A's */
    
    /* sort the the two tables */
    int[] colIndex = AuxFuncs.givenIndex(A.getNoCols());
    AuxFuncs.quicksort( A, 0, A.getNoRowSet()-1, colIndex );
    AuxFuncs.quicksort( B, 0, B.getNoRowSet()-1, colIndex );

    // PJM Rewrite to make more efficient; by having no inner loop looking at B
    int j=0; /* counter to go through rows in table B */
    Row Bj=B.getRow(j++);
    int i=0;
    Row Ai=A.getRow(i++);
    
    while (Ai!=null) {
      boolean addA=false; // set true if A can be added to R, 
      boolean nextA=false; // set true if A if just ignored 
      boolean nextB=false; // set true next B must be inspected
				
      // If no more B, just add A 
      if (Bj==null)
	addA=true;
      // the row in A is greater than the row in B, move and compare next row in B 
      else {
	/* when comparing Rows, do not compare the time components */
	int cmpRows=AuxFuncs.compareRows(Ai, Bj, false, colIndex);
	//System.out.print("Ai="+Ai);
	//System.out.println(" Bj="+Bj);

	if (cmpRows>0)
	  nextB=true;
	else if (cmpRows<0)
	  addA=true;
	else { // They are the same nontemporal attributes, do they overlap?
	  // If A completely after B, need to look at the next B
	  if (Ai.getRow_st()>Bj.getRow_et())
	    nextB=true;

	  // If A completely before B, just add A since don't overlap
	  if (Ai.getRow_et()<Bj.getRow_st())
	    addA=true;

	  // If B is completely inside A, generate two outputs
	  if (Ai.getRow_st()<Bj.getRow_st() && Ai.getRow_et()>Bj.getRow_et()) {
	    int oldet=Ai.getRow_et();

	    // Add the part of A before B
	    Ai.setRow_et(Bj.getRow_st()-1);
	    R.addRow(Ai);

	    Ai.setRow_st(Bj.getRow_et()+1);
	    Ai.setRow_et(oldet);
	    nextB=true;
	  }

	  // If A starts before B and ends during it, add truncated A
	  if (Ai.getRow_st()<Bj.getRow_st() && Bj.getRow_st()<=Ai.getRow_et()
	      && Ai.getRow_et()<Bj.getRow_et()) {
	    Ai.setRow_et(Bj.getRow_st()-1);
	    addA=true;
	  }

	  // If A starts during B and ends after it, truncate A and look
	  // at next B
	  if (Ai.getRow_st()>=Bj.getRow_st() && Bj.getRow_et()<Ai.getRow_et()) {
	    Ai.setRow_st(Bj.getRow_et()+1);
	    nextB=true;
	  }

	  // If A is inside B, just ignore it
	  if (Ai.getRow_st()>=Bj.getRow_st() && Ai.getRow_et()<=Bj.getRow_et()) 
	    nextA=true;
	}
      }

      if (addA)
	R.addRow(Ai);

      if (addA || nextA)
	Ai=A.getRow(i++);
 
      if (nextB)
	Bj=B.getRow(j++);

      // System.out.println("addA="+addA+" nextA="+nextA+" nextB="+nextB);

      if (!addA && !nextA && !nextB) {
	System.out.println("Internal error in Difference i="+i+" j="+j);
	return R;
      }
    }
    
    return R;
  }
}
