import java.util.*;

public class AdjMatrix{
  
  private int matrix[][];
  private SymbolTable symbolTable;
  protected TemporalTransTable transTable;
  private int size;

  public AdjMatrix(int initialSize){
    symbolTable = new SymbolTable();
    matrix = new int[initialSize][initialSize];
    transTable = new TemporalTransTable();
    size = initialSize;
  }       
  
  public void addNode(String symbol){
    if(symbolTable.size() == size)
      System.out.println("AdjMatrix.addNode: stackOverflow");
    else if(!symbolTable.contains(symbol)){
      symbolTable.addSymbol(symbol);
      
      for(int i = 0; i < symbolTable.size(); i++){
	matrix[symbolTable.size() - 1][i] = transTable.NOCONSTRAINTS;
	matrix[i][symbolTable.size() - 1] = transTable.NOCONSTRAINTS;
      }  
      Relation c = new Relation();
      c.i = symbolTable.size() - 1;
      c.j = symbolTable.size() - 1;
      c.r = transTable.EQUALS;
      toAdd(c);
    }
  }

  public void addEntry(String command){
    StringTokenizer tokens = new StringTokenizer(command);
    String x, y, list; 
    int n = tokens.countTokens();
    x = tokens.nextToken();
    n--;
    list = "";
    for(; n != 1; n--){
      list = tokens.nextToken() + " " + list;
    }
    y = tokens.nextToken();
    list = list.replace('(', ' ');
    list = list.replace(')', ' ');
    // System.out.println("x = " + x + ".");
    // System.out.println("y = " + y + ".");
    // System.out.println("r = " + list + ".");
    addEdge(x,y,list);
  }

    
  public void addEdge(String x, String y, String r){
    int e = parseString(r);
    // System.out.println("AdjMatrix.addEdge r = " +
    // 		       transTable.toString(e) + "| " + transTable.getIndex(e));
    addNode(x);
    addNode(y);
    int i = symbolTable.getIndex(x);
    int j = symbolTable.getIndex(y);
    Relation relation = new Relation();
    relation.i = i;
    relation.j = j;
    relation.r = e;
    // System.out.println("AdjMatrix.addEdge: Relation i = " + i + " j = " + j +
// " r = " + e);
    int s = transTable.intersection(relation.r, matrix[i][j]);
    if (isProperSubset(s, matrix[i][j])){
	relation.r = s;
       toAdd(relation);
    }
    Relation inverseRelation = new Relation();
    inverseRelation.i = j;
    inverseRelation.j = i;
    inverseRelation.r = getInverseConstraints(e);
    int t = transTable.intersection(inverseRelation.r, matrix[j][i]);
    if (isProperSubset(t, matrix[j][i])){
       inverseRelation.r = t;
       toAdd(inverseRelation);
    }
  }






  protected int parseString(String str){
    StringTokenizer tokens = new StringTokenizer(str);
    int returnValue = transTable.NOINFO;
    while(tokens.hasMoreTokens()){
      String s = tokens.nextToken();
      if(s.equalsIgnoreCase("equals") || s.equalsIgnoreCase("="))
	returnValue = returnValue | transTable.EQUALS;
      if(s.equalsIgnoreCase("before") || s.equalsIgnoreCase("<"))
	returnValue = returnValue | transTable.BEFORE;
      if(s.equalsIgnoreCase("after") || s.equalsIgnoreCase(">"))
	returnValue = returnValue | transTable.AFTER;
      if(s.equalsIgnoreCase("during") || s.equalsIgnoreCase("d"))
	returnValue = returnValue | transTable.DURING;
      if(s.equalsIgnoreCase("contains") || s.equalsIgnoreCase("di"))
	returnValue = returnValue | transTable.CONTAINS;
      if(s.equalsIgnoreCase("overlaps") || s.equalsIgnoreCase("o"))
	returnValue = returnValue | transTable.OVERLAPS;
      if(s.equalsIgnoreCase("overlappedby") || s.equalsIgnoreCase("oi"))
	returnValue = returnValue | transTable.OVERLAPPEDBY;
      if(s.equalsIgnoreCase("meets") || s.equalsIgnoreCase("m"))
	returnValue = returnValue | transTable.MEETS;
      if(s.equalsIgnoreCase("metby") || s.equalsIgnoreCase("mi"))
	returnValue = returnValue | transTable.METBY;
      if(s.equalsIgnoreCase("starts") || s.equalsIgnoreCase("s"))
	returnValue = returnValue | transTable.STARTS;
      if(s.equalsIgnoreCase("startedby") || s.equalsIgnoreCase("si"))
	returnValue = returnValue | transTable.STARTEDBY;
      if(s.equalsIgnoreCase("finishes") || s.equalsIgnoreCase("f"))
	returnValue = returnValue | transTable.FINISHES;
      if(s.equalsIgnoreCase("finishedby") || s.equalsIgnoreCase("fi"))
	returnValue = returnValue | transTable.FINISHEDBY;
    }
  return(returnValue);
  }      
	  

//   public void addConstraints(String s1, String s2, int constraints){
//     int i = symbolTable.getIndex(s1);
//     int j = symbolTable.getIndex(s2);
//     matrix[i][j] = transTable.intersection(matrix[i][j], constraints);
//     matrix[j][i] = transTable.intersection(matrix[j][i], getInverseConstraints(constraints)) ;// inverse relations...    
//   }
  
  private int getInverseConstraints(int r){
    IntVector v = getSeperateRelations(r);
    int returnValue = transTable.NOINFO;
    for(int i = 0; i < v.size(); i++)
      returnValue = returnValue + getInverseMaping(v.intAt(i));
    return(returnValue);
  }   

  private int getInverseMaping(int relation){
    if((relation & transTable.EQUALS) == transTable.EQUALS)
      return(transTable.EQUALS);
    if((relation & transTable.BEFORE) == transTable.BEFORE)
      return(transTable.AFTER);
    if((relation & transTable.AFTER) == transTable.AFTER)
      return(transTable.BEFORE);
    if((relation & transTable.DURING) == transTable.DURING)
      return(transTable.CONTAINS);
    if((relation & transTable.CONTAINS) == transTable.CONTAINS)
      return(transTable.DURING);
    if((relation & transTable.OVERLAPS) == transTable.OVERLAPS)
      return(transTable.OVERLAPPEDBY);
    if((relation & transTable.OVERLAPPEDBY) == transTable.OVERLAPPEDBY) 
      return(transTable.OVERLAPS);
    if((relation & transTable.MEETS) == transTable.MEETS)
      return(transTable.METBY);
    if((relation & transTable.METBY) == transTable.METBY)
      return(transTable.MEETS);
    if((relation & transTable.STARTS) == transTable.STARTS)
      return(transTable.STARTEDBY);
    if((relation & transTable.STARTEDBY) == transTable.STARTEDBY)
      return(transTable.STARTS);
    if((relation & transTable.FINISHES) == transTable.FINISHES)
      return(transTable.FINISHEDBY);
    if((relation & transTable.FINISHEDBY) == transTable.FINISHEDBY)
      return(transTable.FINISHES);
    else
      return(transTable.NOCONSTRAINTS);
  }
  protected int getTransitiveConstraints(int r1, int r2){
    // System.out.println("AdjMatrix.getTransitiveConstraints: called with: r1 = " + r1 + " r2 = " + r2);

    int returnValue = transTable.NOINFO;
    IntVector r = getSeperateRelations(r1);
    IntVector s = getSeperateRelations(r2);
    for(int i = 0; i < r.size(); i++)
      for(int j = 0; j < s.size(); j++){
	// System.out.println("AdjMatrix.getTransitiveConstraints: r = " + r.intAt(i) + " s = " + s.intAt(j));
	returnValue = transTable.union(
				       returnValue, 
				       transTable.getTemporalTransitiveRelation(
										r.intAt(i),
										s.intAt(j)));
      }
    return(returnValue);
  }
  
  private boolean comparable(int i, int j){
    return(true);
  }

  private boolean isProperSubset(int r, int s){
    IntVector i = getSeperateRelations(r);
    IntVector j = getSeperateRelations(s);
    if(i.size() < j.size() && i.size() != 0){
      for(int k = 0; k < i.size(); k++)
	if(!j.contains(i.elementAt(k))){
	  // System.out.println("AdjMatrix.isProperSubset: " + r + " IS NOT a
// subset of " + s);
	  return(false);
	}
      // System.out.println("AdjMatrix.isProperSubset: " + r + " IS a proper
// subset of " + s);

      return(true);
    }
    else{	 
      // System.out.println("AdjMatrix.isProperSubset: " + r + " IS NOT a proper
//subset of " + s);

      
      return(false);
    } }  
    
  public void toAdd(Relation relation){
    Vector toDo = new Vector(0, 1);
    toDo.addElement(relation);
    while(!toDo.isEmpty()){
      Relation r = (Relation)toDo.elementAt(0); 
      toDo.removeElementAt(0);
      int i = r.i;
      int j = r.j;
      int s = r.r;
      // System.out.println("AdjMatrix.toAdd: i = " + i + " j = " + j + " r = " +
// s);
      matrix[i][j] = s;
      matrix[j][i] = getInverseConstraints(s);
      for(int k = 0; k < symbolTable.size(); k++)
	if(comparable(k, j)){
	  // System.out.println("AdjMatrix.toAdd: first loop i,j,k = " + i + " "
// + j + " " + k);
	  Relation rPrime = new Relation();
	  rPrime.r = transTable.intersection(matrix[k][j],
					getTransitiveConstraints(
								 matrix[k][i], 
								 s));
	  rPrime.i = k;
	  rPrime.j = j;
	  if(isProperSubset(rPrime.r, 
			    matrix[k][j])){
	      //  System.out.println("AdjMatrix.toAdd: queue adding relation: i =
// " + rPrime.i + " j = " + rPrime.j + " r = " + rPrime.r); 
	      toDo.addElement(rPrime); 
	  }
	}
      for(int k = 0; k < symbolTable.size(); k++)
	if(comparable(i, k)){
	  // System.out.println("AdjMatrix.toAdd: second loop i,j,k = " + i + " "
// + j + " " + k);
	  Relation rPrime = new Relation();
	  rPrime.r = transTable.intersection(matrix[i][k],
					getTransitiveConstraints(
								 s,
								 matrix[j][k]));
	  rPrime.i = i;
	  rPrime.j = k;
	  if(isProperSubset(rPrime.r, matrix[i][k])){
	      	      // System.out.println("AdjMatrix.toAdd: queue adding
// relation: i = " + rPrime.i + " j = " + rPrime.j + " r = " + rPrime.r); 
		      toDo.addElement(rPrime);
	  }
	}
      // System.out.println("AdjMatrix.toAdd: Queue toDo.size = " + toDo.size());
    }
  }  
  
  private IntVector getSeperateRelations(int relation){
    IntVector returnValue = new IntVector();
    if((relation & transTable.EQUALS) == transTable.EQUALS)
      returnValue.addElement(transTable.EQUALS);
    if((relation & transTable.BEFORE) == transTable.BEFORE)
      returnValue.addElement(transTable.BEFORE);
    if((relation & transTable.AFTER) == transTable.AFTER)
      returnValue.addElement(transTable.AFTER);
    if((relation & transTable.DURING) == transTable.DURING)
      returnValue.addElement(transTable.DURING);
    if((relation & transTable.CONTAINS) == transTable.CONTAINS)
      returnValue.addElement(transTable.CONTAINS);
    if((relation & transTable.OVERLAPS) == transTable.OVERLAPS)
      returnValue.addElement(transTable.OVERLAPS);
    if((relation & transTable.OVERLAPPEDBY) == transTable.OVERLAPPEDBY) 
      returnValue.addElement(transTable.OVERLAPPEDBY);
    if((relation & transTable.MEETS) == transTable.MEETS)
      returnValue.addElement(transTable.MEETS);
    if((relation & transTable.METBY) == transTable.METBY)
      returnValue.addElement(transTable.METBY);
    if((relation & transTable.STARTS) == transTable.STARTS)
      returnValue.addElement(transTable.STARTS);
    if((relation & transTable.STARTEDBY) == transTable.STARTEDBY)
      returnValue.addElement(transTable.STARTEDBY);
    if((relation & transTable.FINISHES) == transTable.FINISHES)
      returnValue.addElement(transTable.FINISHES);
    if((relation & transTable.FINISHEDBY) == transTable.FINISHEDBY)
      returnValue.addElement(transTable.FINISHEDBY);
    // if((relation & transTable.NOINFO) == transTable.NOINFO)
    //  returnValue.addElement(transTable.NOINFO);
    return(returnValue);
  }

  public String toString(){
    String str = "Current Graph:\n\n";
    for(int i = 0; i < symbolTable.size(); i++)
      for(int j = 0; j < symbolTable.size(); j++)
	 str = str +
	   symbolTable.getSymbol(i) + 
	   " >--- " + 
	   transTable.toString(matrix[i][j]) +
	   " ---> " +
	   symbolTable.getSymbol(j) +
	   "\n";
    return(str);
  }
}