/* Program.beh file created by Edward Wong, Patrick Tibbetts & Jackson Fong */

/* This behavior file implements the algorithm to calculate the subgraph of */
/*  the traversal specified */
/* At the end of the project, we should be reading in two inputs: the class */
/*  dictionary of the class graph drawn in the CD-Draw program and the */
/*  traversal specification(.input and .trav files respectively); we also */
/*  write to an output file that stores the list of UIDs that are in the */
/*  subgraph(this output file will be used by the GUI team to highlight */
/*  those elements with the corresponding UIDs in the CD-Draw program). */
/* NOTE: The list of UIDs in the output file are not in any particular order */
/* NOTE: We did not implement the knowledge path in our algorithm since we */
/*       assume that our inputs are flattened class dictionaries */

UGraph{

  /* Traversal fillTable traverses to all UVertex and UEdge objects */
  /*  with a visitor object, HashVisitor (hv), to put all vertices and edges */
  /*  into a hashtable; later on the algorithm can look them up w/a UID */  
  traversal fillTable(HashVisitor hv) {to {UVertex, UEdge}; }

  /* Traversal allPrint traverses to all UConstVertex, UAltVertex, */
  /*  UConstEdge and UAltEdge objects to print the UIDs that are in the */
  /*  subgraph rather than in class dictionary form (what the GUI team has */
  /*  requested) */
  /* In the before methods for UConstVertex, UAltVertex, UConstEdge, and */
  /*  UAltEdge objects, it checks to see if they were marked twice(included */
  /*  in the subgraph) before printing the UIDs to the output file */
  traversal allPrint(PrintingVisitor pv) {
    to {UConstVertex, UAltVertex, UConstEdge, UAltEdge}; }

  (@
  /* Method markSubgraph fills in all the UVertex and UEdge objects into */
  /*  the hashtable, stores all the proper target UIDs into a vector, stores */
  /*  all the proper bypassing UIDs into a vector, performs the forward */
  /*  depth-first search from the source vertex, does the backward */
  /*  depth-first search from all the target vertices and prints out all */
  /*  the vertices and edges that are marked twice (included in the */
  /*  subgraph); reads in an IndependentTraversal object that contains the */
  /*  UID of the source and target vertices of traversal and the UIDs to */ 
  /*  bypass in calculating the traversal */
  /* Marks each vertex and edge in the subgraph with the current traversal */
  /*  number */
  void markSubgraph(IndependentTraversal travinfo){
    SubgraphMarker.trav++; /* increments current traversal number */

    /* Initializes HashVisitor object and calls traversal fillTable to put */
    /*  all UVertex and UEdge objects into the hashtable using the integer */
    /*  value of the UID as the key */
    HashVisitor hv = new HashVisitor(new Hashtable());
    this.fillTable(hv);

    /* Copies the filled-in hashtable stored in the HashVisitor object into */
    /*  hashtab */    
    Hashtable hashtab = hv.get_htable();

    /* Puts the list of proper target UIDs into a vector */
    /* If a target is a terminal class, it will print out an error to the */
    /*  screen and not put it into the vector */
    travinfo.transferTargetList(hashtab);

    /* Puts the list of proper bypassing UIDs into a vector */
    /* If a bypassing element is a terminal class, it will print out an */
    /*  error to the screen and not put it into the vector */
    travinfo.transferBypassList(hashtab); 

    /* Gets the UID of source vertex and gets its corresponding UVertex */
    /*  object from the hashtable */
    UID source = travinfo.get_from().get_sourceid();
    UVertex uv = (UVertex)hashtab.get(source.get_id());

    /* If the source is a terminal class or there are no valid targets(all */
    /*  targets specified were terminal classes), then it will print out an */
    /*  error to the screen and prints nothing to the output file; otherwise */
    /*  it will continue the calculation of the subgraph algorithm */ 
    /* I think (uv.getClass().getName().compareTo("UTerm") != 0) violates */
    /*  the Law of Demeter */
    if ((uv.getClass().getName().compareTo("UTerm") != 0) && (travinfo.targetvect.size() != 0)){

      /* Calls markReachableForward on the source vertex */
      /* Does a forward depth-first search from the source vertex */
      uv.markReachableForward(travinfo, hashtab);

      /* For every target, it does a backward depth-first search from that */
      /*  specified target to all its reachable paths */
      /* Targetvect is the vector that stores all the integer values of the */
      /*  target UIDs */
      /* NOTE:  We did think about doing this with an Enumeration, but it */
      /*  would be much more inefficient since we know that the actual */
      /*  elements in targetvect will never change; Binoy also agreed with */
      /*  us and decided to use a for loop instead */
      for(int i = 0; i < travinfo.targetvect.size(); i++){

        /* Gets UID of a target vertex from the ith position in the vector */
        /*  and gets its corresponding UVertex object from the hashtable */    
        UID target = new UID (new Integer(((Integer)travinfo.targetvect.elementAt(i)).intValue()));
        UVertex uv2 = (UVertex)hashtab.get(target.get_id());

        /* Calls markReachableBackward on the target vertex */
        /* Does a backward depth-first search from the target vertex */
        uv2.markReachableBackward(travinfo, hashtab);

      }

    }

    else{

      /* Prints out an error message if the source vertex is a terminal */
      /*  class */ 
      /* I think (uv.getClass().getName().compareTo("UTerm") == 0) violates */
      /*  the Law of Demeter */
      if (uv.getClass().getName().compareTo("UTerm") == 0){
        System.err.println("UID #" + source.get_id().intValue() + 
			   " is an invalid" +
                           " source because it is a terminal class.");
      }

      /* Prints out an error message that the traversal specification is */
      /*  invalid; in turn, an empty output file should be generated */
      /* This is the case when the traversal specification has either only */
      /*  one source OR all targets that are terminal classes */
      System.err.println("Error:  Invalid traversal specification.  A " +
                         "terminal class, UTerm, cannot be the");
      System.err.println("only source or target in a traversal.");

    }

    /* Creates a PrintingVisitor and calls traversal allPrint that prints */
    /*  all the UIDs in the subgraph */
    PrintingVisitor pv = new PrintingVisitor();
    this.allPrint(pv);
    }

  @)
}


{UVertex, UEdge} {

  (@
    /* Two variables to keep track of whether or not the vertex or edge is */
    /*  marked twice; forw_trav for the forward depth-first search and */
    /*  back_trav for the backward depth-first search */
    int forw_trav, back_trav;

    /* Checks to see if the node or edge is marked twice, therefore */
    /* the node or edge is in the subgraph(returns true) */
    boolean is_in_trav() {
      return forw_trav == SubgraphMarker.trav
	  && back_trav == SubgraphMarker.trav;
    }
  @)
}

UVertex {

  /* Traversal allEdgesForward uses a ForwardMarker as a visitor object */
  /*  and traverses to all UID objects that are only in the outgoing edge */
  /*  list; in other words, goes to all outgoing edges from the source */
  /*  vertex since this is a forward depth-first search */
  traversal allEdgesForward (ForwardMarker f) { 
    bypassing { -> *, incoming, *,
	        -> *, vid, *}
    to UID; }

  /* Traversal allEdgesBack uses a BackwardMarker as a visitor object */
  /*  and traverses to all UID objects that are only in the incoming edge */
  /*  list; in other words, goes to all incoming edges from the target */
  /*  vertex since this is a backward depth-first search */
  traversal allEdgesBack (BackwardMarker b) {
    bypassing { -> *, outgoing, *,
                -> *, vid, *}
    to UID;}


  (@
    /* markReachableForward takes in the traversal information and the */
    /*  hashtable as arguments */
    /* Once it marks all the reachable paths from the source vertex, the */
    /*  depth-first search in the forward direction will end */
    void markReachableForward(IndependentTraversal travinfo, Hashtable htbl){

      /* Stops traversing any further if the node and all its subpaths has */
      /*  been marked already in the forward direction */
      /*                       OR                      */
      /* Stops traversing any further if this UVertex object is in the list */
      /*  of bypassing UIDs                                                 */
      if ((forw_trav == SubgraphMarker.trav) || (travinfo.in_bypass_list(this.get_vid()))) {
        return;
      }

      /* Marks node as visited in the forward direction */
      forw_trav = SubgraphMarker.trav;

      /* If the traversal specification has a to-stop clause and the visited */
      /*  vertex is a target, there is no need to traverse any further */
      if ((travinfo.stop) && (travinfo.is_target(this.get_vid()))){
        return; 
      } 

      /* Creates the ForwardMarker visitor and calls the traversal */
      /*  allEdgesForward to continue the depth-first search on all the */
      /*  outgoing edges of this marked vertex */
      ForwardMarker fmark = new ForwardMarker(travinfo, htbl);
      this.allEdgesForward(fmark);
    }
  @) 

  
  (@
    /* markReachableBackward takes in the traversal information and the */
    /*  hashtable as arguments */
    /* Once it marks all the reachable paths from the target vertex, the */
    /*  depth-first search in the backward direction will end */
    void markReachableBackward(IndependentTraversal travinfo, Hashtable htbl){

      /* Stops traversing any further if the node and all its subpaths has */
      /*  been marked already in the backward direction */
      /*                      OR                        */
      /* Stops traversing any further if the vertex is in the list of */
      /*  bypassing elements(A vertex is not marked if it's to be bypassed) */
      /* Bypassing is now checked during the backward depth-first search */
      /*  which fixes one of the bugs in Doug's previous subgraph algorithm */
      if ((back_trav == SubgraphMarker.trav) || (travinfo.in_bypass_list(this.get_vid()))) {
        return;
      }

      /* Marks node as visited in the backward direction */
      back_trav = SubgraphMarker.trav;

      /* Creates the BackwardMarker visitor and calls the traversal */
      /*  allEdgesBack to continue the backwards depth-first search on all */
      /*  the incoming edges of this marked vertex */
      BackwardMarker bmark = new BackwardMarker(travinfo, htbl);
      this.allEdgesBack(bmark);
    }    
  @)
}


UEdge {

  (@
    /* markReachableForward takes in the traversal information and the */
    /*  hashtable as arguments */
    void markReachableForward(IndependentTraversal travinfo, Hashtable htbl){

      /* Stops traversing any further if the edge is in the list of */
      /*  bypassing elements(An edge is not marked if it's to be bypassed) */
      if (travinfo.in_bypass_list(this.get_eid())){
        return;
      }

      /* Marks edge as visited in the forward direction */
      forw_trav = SubgraphMarker.trav;

      /* Takes the UID of the target vertex of the edge and uses it as a key */
      /*  to find its corresponding UVertex object in the hashtable */
      /* Using the UVertex object, it calls markReachableForward for that */
      /*  vertex                                                          */
      UVertex uv = (UVertex)htbl.get(this.get_toVertex().get_id());
      uv.markReachableForward(travinfo, htbl);

    }
  @) 

  (@
    /* markReachableBackward takes in the traversal information and the */
    /*  hashtable as arguments */
    void markReachableBackward(IndependentTraversal travinfo, Hashtable htbl){

      /* Stops traversing any further if the edge is in the list of */
      /*  bypassing elements(An edge is not marked if it's to be bypassed) */
      /* Bypassing is now checked during the backward depth-first search */
      /*  which fixes one of the bugs in Doug's previous subgraph algorithm */ 
      if (travinfo.in_bypass_list(this.get_eid())){
        return;
      }

      /* Marks edge as visited in the backward direction */
      back_trav = SubgraphMarker.trav;

      /* Takes the UID of the source vertex of the edge and uses it as a key */
      /*  to find its corresponding UVertex object in the hashtable */
      /* Using the UVertex object, it calls markReachableBackward for that */
      /*  vertex                                                           */
      UVertex uv2 = (UVertex)htbl.get(this.get_fromVertex().get_id());
      uv2.markReachableBackward(travinfo, htbl);
    }
  @)
}


ForwardMarker{

  before UID (@
    /* At every UID object of an outgoing edge, it takes that UID of the */
    /*  edge and uses it as a key to find its corresponding UEdge object */
    /*  in the hashtable */
    /* Using the UEdge object, it calls markReachableForward for that edge */
    UEdge ue = (UEdge)forhtable.get(host.get_id());
    ue.markReachableForward(travinfo, forhtable);
  @)
}

BackwardMarker{

  before UID (@
    /* At every UID object of an incoming edge, it takes that UID of the */
    /*  edge and uses it as a key to find its corresponding UEdge object */
    /*  in the hashtable */
    /* Using the UEdge object, it calls markReachableBackward for that edge */
    UEdge ue2 = (UEdge)backhtable.get(host.get_id());
    ue2.markReachableBackward(travinfo, backhtable);
  @)
}

SubgraphMarker {
  /* Static variable that keeps track of the current traversal number; */
  /* in other words, the marker used to mark the nodes and edges */
  (@ static int trav; @)
}

IndependentTraversal {

  /* Boolean used to find out whether the traversal specification has a to */
  /*  or to-stop clause; returns false if it's a from-to traversal, */
  /*  returns true if it's a from-toStop traversal */
  (@ boolean stop = false; @)

  /* Traversal traverseTargets goes to all UID objects in the target list */
  /* Using TargetVisitor as a visitor object, it traverses to each UID in */
  /*  the target list and stores the integer value of the UID in a vector */
  /* Later on, in markReachableForward, the algorithm will check to see if */
  /*  the current vertex is in the vector with the UIDs of target vertices */

  /* traversal traverseTargets does not include the source & bypassing UIDs */
  traversal traverseTargets(TargetVisitor tv){
    bypassing { -> *, from, *,
		-> *, bypass, *}
    to UID; }
  
  /* Traversal traverseBypass goes to all UID objects in the bypass list */
  /* Using BypassVisitor as a visitor object, it traverses to each UID in */
  /*  the bypass list and stores the integer value of the UID in a vector */
  /* Later on, in markReachableForward and in markReachableBackward, the */
  /*  algorithm will check to see if the current vertex or edge is in */
  /*  the vector(bypass list); in other words, the vector will be our */
  /*  "bypass list" */

  /* traversal traverseBypass does not include the source and target UIDs */
  traversal traverseBypass(BypassVisitor lv){
    bypassing { -> *, from, *,
 		-> *, target, *}
    to UID; }

  
  (@

  /* A local vector, targetvect, that will store the list of target UIDs */
  Vector targetvect = new Vector();

  /* A local vector, bypassvect, that will store the list of bypassing UIDs */
  Vector bypassvect = new Vector();

  /* Checks to see if the current UID of the corresponding vertex object */ 
  /*  is in the target vector; returns true if the current element is a 
  /*  target vertex */
  boolean is_target(UID id){
    return targetvect.contains(id.get_id());}

  /* Checks to see if the current UID of the corresponding vertex or edge */
  /*  object is in the vector; returns true if the current element should */
  /*  be bypassed(in other words, don't mark the element), otherwise false */
  boolean in_bypass_list(UID id){
    return bypassvect.contains(id.get_id());}

  /* function transferTargetList is called from markSubgraph in the UGraph */
  /*  class; takes in a hashtable as an argument; creates a TargetVisitor */
  /*  object that has a vector object that will store all the target UIDs */
  /*  and then it calls the traversal traverseTargets; finally, it */
  /*  will make a local copy of the constructed vector into targetvect and */
  /*  assign the status of stop(whether it's a to or to-stop traversal) */
  void transferTargetList(Hashtable htbl){
    TargetVisitor tv = new TargetVisitor(new Vector(), htbl);
    this.traverseTargets(tv);
    this.targetvect = tv.get_vect();
    this.stop = tv.stop;
  }

  /* function transferBypassList is called from markSubgraph in the UGraph */
  /*  class; takes in a hashtable as an argument; creates a BypassVisitor */
  /*  object that has a vector object that will store all the UIDs to */
  /*  bypass and then it calls the traversal traverseBypass; finally, it */
  /*  will make a local copy of the constructed vector into bypassvect */ 
  void transferBypassList(Hashtable htbl){
    BypassVisitor bv = new BypassVisitor(new Vector(), htbl);
    this.traverseBypass(bv);
    this.bypassvect = bv.get_vect();    
  }

  @)
}


HashVisitor{

  before UVertex (@
    /* Adds the UVertex object into the hashtable using the integer value of */
    /*  the UID as the key */
    htable.put(host.get_vid().get_id(), host); @)

  before UEdge (@
    /* Adds the UEdge object into the hashtable using the integer value of */
    /*  the UID as the key */
    htable.put(host.get_eid().get_id(), host); @)
}


TargetVisitor{

  /* Boolean that stores whether or not the traversal specification has */
  /*  a to or to-stop clause; true if it's a to-stop clause and false if */
  /*  it's a to clause; sends this result back to the boolean in the */
  /*  IndependentTraversal object */
  (@ boolean stop; @)

  /* A to clause exists in the traversal specification */
  before To (@ stop = false; @)

  /* A to-stop clause exists in the traversal specification */
  before ToStop (@ stop = true; @) 

  /* Using the integer value of the UID, it gets its corresponding UVertex */
  /*  object from the hashtable; if the target is a terminal class, it will */
  /*  print out an error and not put it into the vector; otherwise, the */
  /*  target UID is put into the vector */
  /* As a result, the vector will only have targets that are valid (none are */
  /*  terminal classes)                 */
  before UID(@
    UVertex uv = (UVertex)htable.get(host.get_id()); 

    /* Violating the Law of Demeter?? */
    if (uv.getClass().getName().compareTo("UTerm") == 0) {

      System.err.println("UID #" + host.get_id().intValue() + 
			 " is an invalid" +
                         " target because it is a terminal class.");
    }

    else{
      this.get_vect().addElement(host.get_id()); /* adds element to vector */
    }

  @)
}


BypassVisitor{

  /* Using the integer value of the UID, it gets its corresponding object */
  /*  from the hashtable; if the bypassing element is a terminal vertex, it */
  /*  will print out an error and not put it into the vector; otherwise, the */
  /*  bypassing UID is put into the vector */
  /* As a result, the vector will only have bypassing elements that are */
  /*  valid (none are terminal classes)    */
  before UID(@

    /* I think this statement violates the Law of Demeter because we first */
    /*  get the object from the hashtable and call successive methods on it */
    if (htable.get(host.get_id()).getClass().getName().compareTo("UTerm") == 0){
      System.err.println("UID #" + host.get_id().intValue() + 
			 " is an invalid element to bypass because a " +
   			 "terminal class cannot ");
      System.err.println("be bypassed.");
    }
    else{ 
      this.get_vect().addElement(host.get_id()); /* add element to vector */
    }

  @)

}


PrintingVisitor{

  /* The PrintingVisitor has drastically changed from phase II */
  /* Since Dave Mann(the GUI group of the visual-traverse team) wanted */
  /*  the output file to be just a list of UIDs, we have eliminated all */
  /*  the class dictionary syntax and components of the UVertex and UEdge */
  /*  objects and the PrintingListVisitor was also not needed anymore */
  /* In other words, the subgraph will not be printed in class dictionary */
  /*  form but in a list of UIDs that are in the subgraph */

  /* If the Vertex object is in the subgraph(marked twice), it will print */
  /*  its corresponding UID into the output file */
  before {UAltVertex, UConstVertex} (@
    if (host.is_in_trav()){
      Main.out.print(host.get_vid().get_id().intValue() + " "); } 
  @)

  /* If the Edge object is in the subgraph(marked twice), it will print */
  /*  its corresponding UID into the output file */
  before {UAltEdge, UConstEdge} (@
    if (host.is_in_trav()){
      Main.out.print(host.get_eid().get_id().intValue() + " "); }
  @)

}

Main{
  (@
  
  /* This is used to refer to the output file that the algorithm could write */
  /*  to using the command Main.out.println ... rather than */
  /*  System.out.println */
  static PrintStream out;

  static public void main (String args[]) throws Exception {

    /* Initializes all File objects */
    File inputfile = null, travfile = null, outputfile = null;

    /* The user can only input one argument, the prefix for the input and */
    /*  traversal files; For example, if the prefix is "prog", this program */
    /*  will expect to read in prog.input and prog.trav as the two input */
    /*  files and use prog.output as the output file(where the printing */
    /*  visitor does its job) */
    /* To run this program, the user must type: java Main [prefix] */
    /* If number of arguments is not equal to 1, an error message is shown */
    /*  on the screen and the subgraph algorithm is not run */
    if (args.length != 1){
      System.err.println("Invalid number of arguments.");
      System.err.println("You must specify only one argument."); 
      return;
    }
    else{ /* One argument(the prefix) */

      String name = args[0];  /* stores prefix into the variable, name */
     
      /* Creates the names of the two input files and output file using */
      /*  the prefix as the beginning of each of these filenames */
      inputfile = new File(name + ".input");
      travfile = new File(name + ".trav");
      outputfile = new File(name + ".output");

      /* Creates a new UGraph and IndependentTraversal object */
      UGraph graph = new UGraph();
      IndependentTraversal travinfo = new IndependentTraversal();

      /* Checks to see if the .input file and the .trav file are readable */
      /*  (in other words, if the files are in the current directory or */
      /*  if the files are not corrupt */
      if ((inputfile.canRead()) && (travfile.canRead())){

        /* Parses the two input files(.input and .trav files) into a UGraph */
        /*  and IndependentTraversal object respectively */
        graph = UGraph.parse(new FileInputStream(inputfile));
        travinfo = IndependentTraversal.parse(new FileInputStream(travfile));

        /* Uses [prefix].output as the name of the output file to print */
        /*  out all the syntax done by the printing visitor */
        out = new PrintStream(new FileOutputStream(outputfile));

        /* Calls the method markSubgraph on the UGraph object, graph, to */
        /*  start the algorithm to calculate the subgraph, using the */
        /*  IndependentTraversal object as an argument */
        graph.markSubgraph(travinfo);
      }
      else{
        /* Prints out an error to the screen saying that the input files */
        /*  (.input and/or .trav files) are unreadable; either they don't */
        /*  exist in the current directory or they are corrupt */
        /* Does not run the subgraph algorithm */
        System.err.println("The input files, " + inputfile + " and " +
                           travfile + ", are not readable.");
        return;
      }
    }
  }
  @)
}