package edu.neu.ccs.demeter;
import java.util.*;
import edu.neu.ccs.demeter.Ident;
import java.io.*;

/** Utility class for TAO. */
public class Graph {
  public Graph(Hashtable t) {graph = t;}
  public Graph() {graph= new Hashtable();}
  
  private Hashtable graph = new Hashtable();

  public static Graph fromString(String str) {
    return fromString(new StreamTokenizer(new StringReader(str)));
  }
  public static Graph fromString(StreamTokenizer instr) {
    instr.lowerCaseMode(false);
    instr.wordChars('_','_');
    instr.ordinaryChar('.');

    Hashtable g= new Hashtable();
    Ident cn,pn,pc;
    Object[] em;
    try {
      instr.nextToken();
      while ((instr.ttype != '.')&&(instr.ttype != -1)) { // for each class
	cn = new Ident(instr.sval);
//	System.out.print("\n"+cn);
	instr.nextToken(); // the open paren

	
	if (instr.ttype != '(') {System.out.println("Confused"); System.exit(1);}
	instr.nextToken(); 
	
	int numparts = (int) instr.nval;
	instr.nextToken();

	em = new Object[2*numparts+1];
	g.put(cn,em);

	int partcount =1;

	while (instr.ttype != ')') { // for each edge
	  pn = new Ident(instr.sval); // part name
//	  System.out.print(" <"+pn+"> ");
	  instr.nextToken();

	  pc = new Ident(instr.sval); // and class
//	  System.out.print(pc);
	  instr.nextToken();

	  em[2*partcount-1]=pn;
	  em[2*partcount  ]=pc;
	  partcount++;
	}
	instr.nextToken();
      }

    } catch (IOException e) {
      System.err.println(e);
      System.exit(1);
    }

    return new Graph(g);
  }
 
  public String toString() {
    String str = "";
    for(Enumeration e = graph.keys(); e.hasMoreElements();) {
      Ident key = (Ident) e.nextElement();
      str = str+key+" ( ";
      Object[] parts = (Object[]) graph.get(key);
      int numparts=(parts.length-1)/2;
      str = str + numparts +" ";
      for (int i =1;i <= numparts;i++) {
	Ident pn = (Ident) parts[2*i-1];
	Ident pc = (Ident) parts[2*i];
	str=str+pn+" "+pc+" ";
      }
      str = str + " ) ";
    }
    return str+" .";
  }

  public Enumeration nodes() {
    return graph.keys();
  }

  public boolean nodeexists(Ident node) {
    return graph.containsKey(node);
  }

  public boolean edgeexists(Ident from, Ident name) {
    if (! nodeexists(from)) return false;
    Object[] parts = edgesfrom(from);
    int numparts=(parts.length-1)/2;
    for  (int i =1;i <= numparts;i++) {
      if (name.equals((Ident) parts[2*i-1])) return true;
    } 
    return false;

  }

  public Object[] edgesfrom(Ident node) {
    if (nodeexists(node)) {
      return (Object[]) graph.get(node);
    } else {
      Object[] e = new Object[1]; 
      graph.put(node,e);
      return e;
    }
  }

  public Object getdestnode(Ident node, Ident edgename) {
    Object[] parts = edgesfrom(node);
    for (int numparts=(parts.length -1)/2; numparts >0; numparts--) {
      if (((Ident)parts[numparts*2-1])==edgename) return parts[numparts*2];
    }
    return null;
  }

  public void makeedge(Ident from, Ident edgename, Ident to) {
    Object[] parts = edgesfrom(from);
    Object[] newparts = new Object[parts.length +2];
    // assume the part does not exist
    newparts[0]=parts[0];
    newparts[parts.length]=edgename;
    newparts[parts.length+1]=to;
    graph.put(from,newparts);

    for (int numparts=(parts.length -1)/2; numparts >0; numparts--) {
      // if the assumption was wrong, undo the damage
      if (((Ident) parts[numparts*2-1])==edgename) {
	parts[numparts*2]=to;
	graph.put(from,parts);
	break;
      } else {
	newparts[numparts*2-1]=parts[numparts*2-1];
	newparts[numparts*2]=parts[numparts*2];
      }
    }
  }

  public void clearnode(Ident from) {
    graph.put(from, new Object[1]);
  }

  public void removeincoming(Ident to) {
    Enumeration thenodes = nodes();
    while (thenodes.hasMoreElements()) { 
      Ident cn = (Ident) thenodes.nextElement();
      Object[] parts = edgesfrom(cn);
      if (parts.length < 3) continue;
      Object[] newparts = new Object[parts.length-2];
      int numparts = (parts.length-1)/2;
      int partcount=1;
      while ((partcount<numparts)&&(((Ident)parts[2*partcount-1])!=to)) {
	newparts[partcount]=parts[partcount];
	partcount++;
      }
      if (((Ident)parts[2*partcount-1])==to) {
	graph.put(cn,newparts);
	while (partcount<numparts) {
	  newparts[partcount]=parts[partcount+2];
	  partcount++;
	}
      } 
    }
  }    

  public Graph reversegraph() {
    Graph g = new Graph(); 

    for (Enumeration thenodes = nodes(); thenodes.hasMoreElements();) {
      Ident node = (Ident) thenodes.nextElement();
//    System.out.println("reversing from "+node);
      Object[] edges = edgesfrom(node);
      int numparts=(edges.length-1)/2;
      for (int i =1; i <=numparts;i++) {
	Ident edgename = (Ident) edges[2*i-1];

	// since several edges of the same label may point to one
	// class, the reverse class must be able to store several
	// outgoing edges of the same name. This is not a problem
	// since the names, for the reverse graph, of the edeges are
	// not important. Thus, we make each name unique by appending
	// the dest class to the edge name.

	Ident edgeto = (Ident) edges[2*i];
	edgename = new Ident(edgename.toString()+node.toString()); 
	g.makeedge(edgeto,edgename,node); 
	
      }
    }

    return g;  
  }

  public void marknode(Ident node, String mark) {
    if (edgesfrom(node)[0]==null) edgesfrom(node)[0]= new Vector();

    ((Vector) edgesfrom(node)[0]).addElement(mark);
  }

  public boolean nodehasmark(Ident node, String mark) {
    return (((edgesfrom(node)[0]!=null))&&(((Vector) edgesfrom(node)[0]).contains(mark)));
  }

  public void clearmark(String mark) {
    for (Enumeration thenodes= nodes(); thenodes.hasMoreElements();) {
      Ident node = (Ident) thenodes.nextElement();
      if (edgesfrom(node)[0]!=null)
	((Vector) edgesfrom(node)[0]).removeElement(mark);
    }
  }

  public Graph deepcopy() {
    Graph g = new Graph();
    for (Enumeration thenodes = nodes(); thenodes.hasMoreElements();) {
      Ident node = (Ident) thenodes.nextElement();
      g.graph.put(node,edgesfrom(node).clone());
    }
    return g; 
  }
    
  public void dfs(Ident from,String mark) {
    if (nodehasmark(from,mark))  return;
    marknode(from,mark);
    Object[] edges= edgesfrom(from);
    int partcount =1;
    int numparts= (edges.length-1)/2;
    while (partcount<=numparts) 
      dfs((Ident) edges[2*partcount++],mark);
  }
  /*
  public static void main( String[] args) {
    System.out.println(Graph.fromString("SummingVisitor ( 1 total Integer  ) Traversal ( 3 path TAO_TravList label TAO_TravLabel fromclasses TAO_ClassNames_Alternation  ) UniversalVisitor_Alternation ( 5 tracevisitor TraceVisitor copyvisitor CopyVisitor displayvisitor DisplayVisitor printvisitor PrintVisitor equalvisitor EqualVisitor  ) TAO_TravList ( 3 next TAO_NextTrav bypass TAO_Bypass too TAO_ClassNames_Alternation  ) Example ( 1 tree Tree  ) TAO_NextClassGlob ( 1 classgloblist TAO_ClassGlobList  ) TAOVisitor_Alternation ( 1 summingvisitor SummingVisitor  ) RTree ( 1 tree Tree  ) TAO_ClassGlob_Alternation ( 2 tao_anyclass TAO_AnyClass tao_classname TAO_ClassName  ) Tree ( 3 left LTree l Label right RTree  ) TAO_ClassGlobList ( 2 next TAO_NextClassGlob classglob TAO_ClassGlob_Alternation  ) TAO_OneClassGlob ( 1 classglob TAO_ClassGlob_Alternation  ) TAO_Bypass ( 1 bypass TAO_ClassNames_Alternation  ) TAO_TravLabel ( 1 travlab Ident  ) LTree ( 1 tree Tree  ) TAO_ClassGlobSet ( 1 classglobs TAO_ClassGlobList  ) TAO_ClassName ( 1 name Ident  ) TAO_ClassNames_Alternation ( 2 tao_oneclassglob TAO_OneClassGlob tao_classglobset TAO_ClassGlobSet  ) TAO_NextTrav ( 1 trav TAO_TravList  ) Label ( 1 v Integer  ) ."));
  }
  */
/*    
  public void dfstop(Ident from,Ident to, String mark) {
    if (nodehasmark(from,mark))  return;
    marknode(from,mark);
    if (from == to) return;
      
    Enumeration edgenames= edgesfrom(from).names();
    for (; edgenames.hasMoreElements();) {
      Ident edge = (Ident) edgenames.nextElement();
      if (edge != markident)
        dfstop(edgesfrom(from).getdest(edge),to,mark);
    }
  }
*/

}