// ***********************************************************
// *							     *
// *  main.C (mp10)					     *
// * 							     *
// *  MP10: Theseus and the Minotaur			     *
// *						  	     *
// *  Author: Mariusz Zaczek				     *
// *  Class:  CS225, Tu 11-1pm, Chad Pieper TA		     *
// *  Date:   May 5, 1999				     *
// *							     *
// ***********************************************************

// ***********************************************************
// *							     *
// *  Marks used to determine if the Minotaur or Theseus     *
// *   were in a particular cavern or passage                *
// *						             *
// *     0  = No one ever this passage or cavern before      *
// *     1  = Theseus was here before                        *
// *     2  = Minotaur was here before                       *
// *     3  = Both the Minotaur and Theseus were here before *
// *            (candle is lit in cavern)                    *
// *							     *
// ***********************************************************

#include <iostream.h>
#include <map>
#include "string.h"
#include "infograph.h"

// EdgeBetween()
//    - function to find the edge(Passage) given two 
//      vertices(Caverns)
//    - parameters: MAZE - a graph describing the Cavern maze
//                  SourceV - Source vertex of the edge
//                  TargetV - Target vertex of the edge
Edge EdgeBetween(InfoGraph<String,String> MAZE, 
		       Vertex SourceV, Vertex TargetV)
{
  Edge CurrentEdge;

  // Search through all departing edge of source vertex 
  //   starting with the first edge.
  CurrentEdge = MAZE.FirstDepartEdge(SourceV);
  
  // while the current edge's target vertex does not match 
  //   the input target then look through next departing edge.
  while ( !(MAZE.IsNil(CurrentEdge)) )
  {
    if( MAZE.Target(CurrentEdge) == TargetV )
      return CurrentEdge;
    else
      CurrentEdge = MAZE.NextDepartEdge(CurrentEdge);
  }
}


// NextRightEdge()
//    - function to find the next unmarked edge which Thesesus
//      can take
//    - parameters: MAZE - a graph describing the caverns
//                  CurEdge - the current edge Theseus is on
//                    prior to entering the cavern and searching
//                    for next available exit.
Edge NextRightEdge(InfoGraph<String,String> MAZE, Edge CurEdge)
{
  Edge NextEdge;
 
  // Find the departing edge that corresponds to the current edge
  //    that Theseus is on. 
  CurEdge = EdgeBetween( MAZE,MAZE.Target(CurEdge),
			      MAZE.Source(CurEdge) );
  
  // From this new current edge look at next departing edge.
  NextEdge = MAZE.NextDepartEdge(CurEdge);
  
  // If this new edge is NIL then start from the first departing 
  //   edge of the previous (CurEdge) edges source vertex
  if ( MAZE.IsNil(NextEdge) )
    NextEdge = MAZE.FirstDepartEdge(MAZE.Source(CurEdge));

  // Loop forever (Not really)
  while ( 1 )
  {
    // If the current edge Theseus is looking at has not been 
    //  marked by him then take it, otherwise look at next
    //  departing edge.
    if ( (MAZE.GetEdgeMark(NextEdge) == 0) || 
         (MAZE.GetEdgeMark(NextEdge) == 2) )
      return NextEdge;
    else
      NextEdge = MAZE.NextDepartEdge(NextEdge);
 
    if ( MAZE.IsNil(NextEdge) )
      NextEdge = MAZE.FirstDepartEdge(MAZE.Source(CurEdge));
  }
}    


// NextLeftEdge()  
//    - function to find the the first edge (CCW) that was 
//      taken by the Minotaur that Theseus can follow. 
//    - parameters: MAZE - a graph describing the caverns
//                  CurEdge - the current edge Theseus is on
Edge NextLeftEdge(InfoGraph<String,String> MAZE, Edge CurEdge)
{     
  Edge NextEdge;
    
  // Find the opposite edge of the current edge that Theseus is on
  CurEdge = EdgeBetween( MAZE,MAZE.Target(CurEdge),
                         MAZE.Source(CurEdge) );
  
  // Find the next departing edge of the new edge.
  NextEdge = MAZE.NextDepartEdge(CurEdge);
    
  // if this edge is NIL then start over at first departing edge.
  if ( MAZE.IsNil(NextEdge) )
    NextEdge = MAZE.FirstDepartEdge(MAZE.Source(CurEdge));
      
  // Loop forever (Not really)
  while ( 1 )
  {
    // If the current edge being looked at has been ever taken by the
    //   minotaur the take it else look at next right edge.
    if (( MAZE.GetEdgeMark(NextEdge) == 2 ) || 
        ( MAZE.GetEdgeMark(NextEdge) == 3 ))
      return NextEdge;
    else
      NextEdge = MAZE.NextDepartEdge(NextEdge);

    if ( MAZE.IsNil(NextEdge) )
      NextEdge = MAZE.FirstDepartEdge(MAZE.Source(CurEdge));
  }
} 



// MINNextLeftEdge()
//    - function to select the next left edge that the
//       Minotaur can take
//    - parameters: MAZE - a graph describing the caverns
//                  CurEdge - the current edge that the 
//                     Minotaur is on.
Edge MINNextLeftEdge(InfoGraph<String,String> MAZE, Edge CurEdge)	
{
  Edge PrevEdge;
  
  // Find the corresponding opposite going edge of the 
  //   current edge.
  CurEdge = EdgeBetween( MAZE,MAZE.Target(CurEdge),
			      MAZE.Source(CurEdge) );
  
  // Find the previous edge to the current edge.
  PrevEdge = MAZE.PrevDepartEdge(CurEdge);
  
  // If edge is NIL then go to last edge and work backwards
  //   through the edges again.
  if ( MAZE.IsNil(PrevEdge) )
    PrevEdge = MAZE.LastDepartEdge(MAZE.Source(CurEdge));
    
  // Loop forever (Not really)
  while ( 1 )
  {
    // If the edge being considered has never been
    //   taken by the Minotaur then take it else look
    //   at previous edge.
    if ( (MAZE.GetEdgeMark(PrevEdge) == 0) || 
         (MAZE.GetEdgeMark(PrevEdge) == 1) )
      return PrevEdge;
    else
      PrevEdge = MAZE.PrevDepartEdge(PrevEdge);

    if ( MAZE.IsNil(PrevEdge) )
      PrevEdge = MAZE.LastDepartEdge(MAZE.Source(CurEdge));
  }
}




// main()
//    - The main function where all steps of the Minotaur
//        and Theseus are investigated.
int main()
{
  char 	 input[100],     // Char values used for reading from
 	 input2[100];    //    cin
  char 	 ONE[100], 	 // Char input value used when "END"
	 TWO[100], 	 //  is reached when reading input file.
	 THREE[100], 	
	 FOUR[100];
  String S1, 		 // Strings corresponding to the ONE, TWO
	 S2,		 //   THREE and FOUR char values
	 S3,
	 S4;
  String FromC, 	 // String used as input values.
	 ToC, 
	 Value;
  Edge   THECurEdge,     // Theseus's Current Edge 
         MINCurEdge;     // Minotaur's Current Edge
  Vertex THECurVertex,   // Theseus's Current Vertex
         MINCurVertex;   // Minotaur's Current Vertex
 
  int 	 THEvert, 	 // integers to keep track of
	 MINvert,	 //   current vertices and passages
	 THEedge,	 //   of the Minotaur and Theseus
	 MINedge;

  InfoGraph<String,String> MAZE;  // MAZE graph through which
				  //  the Minotaur and Theseus
				  //  travel

  // The mapping of Strings to Vertices
  map<String,Vertex,less<String> > Cavern;  

  // The mapping of Strings to Passages
  map<String,Edge,less<String> > Passage; 


  // Begin to take input from the a file or from the keyboard
  //   - continue until no more input if available
  while ( cin >> input )
  {
    Value = input;
    
    // If the input value is "FROM" then read the next two
    //   input values and assign the first one to the starting
    //   vertex (Cavern)
    if ( Value == "FROM" )
    {
      cin >> input >> input2 ;
      FromC = input;

      // If the cavern has not been previously mapped then
      //   then map it
      if ( Cavern.find(FromC) == Cavern.end() )
      {
         Cavern[FromC] = MAZE.InsertVertex(FromC);
         MAZE.SetVertexMark(Cavern[FromC], 0);
      }
    }
    else if ( Value == "END" ) // if the current value is "END"
    {
      // Read the next four values which correspond to the
      //  passage vertices of the current locations of Theseus 
      //  and the Minotaur
      cin >> ONE >> TWO >> THREE >> FOUR;
      S1 = ONE; S2 = TWO; S3 = THREE; S4 = FOUR;

      // If the starting passages of the Minotaur and Theseus
      //   are the same than Theseus is killed.
      if ( ((S1+S2) == (S3+S4)) || ((S1+S2) == (S4+S3)) )
      {
         cout << "Theseus is killed between " << S1 
	      << " and " << S2 << endl;
         return 0;
      }

      // Assign Thesus to have marked the starting cavern
      THECurEdge = Passage[S1+S2];
        THECurVertex = Cavern[S1];
        MAZE.SetVertexMark(Cavern[S1],0);      

      // mark the passages
      MAZE.EdgeAssign(Passage[S1+S2],S1+S2);
        MAZE.SetEdgeMark(Passage[S1+S2],0);       
      MAZE.EdgeAssign(Passage[S2+S1],S2+S1);
        MAZE.SetEdgeMark(Passage[S2+S1],0);       

      // Assign Centaur to have marked starting cavern
      MINCurEdge = Passage[S3+S4];
        MINCurVertex = Cavern[S3];
        MAZE.SetVertexMark(Cavern[S3],0);      

      // mark the passages
      MAZE.EdgeAssign(Passage[S3+S4],S3+S4);
        MAZE.SetEdgeMark(Passage[S3+S4],0);    
      MAZE.EdgeAssign(Passage[S4+S3],S4+S3);
        MAZE.SetEdgeMark(Passage[S4+S3],0);      
    }
    else // else read the next vertices 
    {
      // These next vertices correspond to the Target vertices
      //   of departing edges with a source vertex of _FromC_
      ToC = input;

      // If the vertex(Cavern) has not been mapped before then
      //   map it.
      if ( Cavern.find(ToC) == Cavern.end() )
      {
         Cavern[ToC] = MAZE.InsertVertex(ToC);
           MAZE.SetVertexMark(Cavern[ToC],0);
      }
  
      // If the edge(Passage) has not been mapped before then
      //   map it.
      if (Passage.find(FromC+ToC) == Passage.end() )
      {
        Passage[FromC+ToC] = MAZE.InsertEdge(Cavern[FromC],
			      Cavern[ToC],FromC+ToC);
          MAZE.SetEdgeMark(Passage[FromC+ToC],0);
      }

    }  // ****  if (value == "FROM")
  } // ****  while ( cin >> input )



  // Start the motion of Theseus and the Minotaur
  while ( 1 )
  {
    // Keep track of the current marking of the Current vertices
    //  and edge of the Minotaur and Theseus
    THEvert = MAZE.GetVertexMark(THECurVertex);
    MINvert = MAZE.GetVertexMark(MINCurVertex); 
    THEedge = MAZE.GetEdgeMark(THECurEdge);
    MINedge = MAZE.GetEdgeMark(MINCurEdge);


    // If the Minotaur and Theseus are on the same edge(Passage)
    //   then Theseus dies.
    if ( (MAZE.VertexInfo(MAZE.Target(THECurEdge)) == 
	  MAZE.VertexInfo(MAZE.Source(MINCurEdge)))
                                                   &&   
         (MAZE.VertexInfo(MAZE.Source(THECurEdge)) == 
	  MAZE.VertexInfo(MAZE.Target(MINCurEdge))) )
    {
      cout << "Theseus is killed between " 
	   << MAZE.VertexInfo(MAZE.Source(THECurEdge)) 
           <<" and " << MAZE.VertexInfo(MAZE.Target(THECurEdge)) 
	   << endl;
      return 0;
    }
    else // else move them both to their target vertices
    {
      THECurVertex = MAZE.Target(THECurEdge);

      // Minotaur checks if candle is ahead in upcoming cavern (Vertex)
      if ( MAZE.GetVertexMark(MAZE.Target(MINCurEdge)) == 3 )
      {
        // If he sees the candle then he returns to starting vertex(cave)
        MINCurVertex = MAZE.Source(MINCurEdge);    
        MINCurEdge = EdgeBetween(MAZE, MAZE.Target(MINCurEdge), 
				       MAZE.Source(MINCurEdge) );
      }
      else // else he reaches intended cave
        MINCurVertex = MAZE.Target(MINCurEdge);    
    }


    // If the current caves of the Minotaur and Theseus are the
    //   same then the Minotaur gets killed
    if ( MAZE.Target(THECurEdge) == MAZE.Target(MINCurEdge) )
    {
      cout << "The Minotaur is slain in " 
	   << MAZE.VertexInfo(MAZE.Target(THECurEdge)) << endl;
      return 0;
    }

    // Update current positions and marks
    if ( (MAZE.GetVertexMark(THECurVertex) == 2 ) || 
	 (MAZE.GetVertexMark(THECurVertex) == 3 ))
      THEvert = 3;
    else
      THEvert = 0;

    if ( (MAZE.GetVertexMark(MINCurVertex) == 0 ) || 
	 (MAZE.GetVertexMark(MINCurVertex) == 2 ))
      MINvert = 2;

    MAZE.SetVertexMark(THECurVertex,THEvert);
    MAZE.SetVertexMark(MINCurVertex,MINvert);

  
    // If both are in same cavern then kill Minotaur
    if ( MAZE.VertexInfo(THECurVertex) == 
	 MAZE.VertexInfo(MINCurVertex) )
    {
      cout << "The Minotaur is slain in " 
	   << MAZE.VertexInfo(THECurVertex) << endl;
      return 0;
    }
    else
    {
       // *****************(      THESEUS       )******
       // If he never entered this cavern and no else did either 
       //   than take next right passage
       if ( MAZE.GetVertexMark(THECurVertex) == 0 )
       {   
         // Never been here before and neither has the Minotaur
         THECurEdge = NextRightEdge(MAZE, THECurEdge);
           
         // Update edge number later...
         if      ( MAZE.GetEdgeMark(THECurEdge) == 0 )
           THEedge = 1;
         else if ( MAZE.GetEdgeMark(THECurEdge) == 2 ) 
           THEedge = 3;
       }
       else
       if ( MAZE.GetVertexMark(THECurVertex) == 2 )
       {
         // else if the Minotaur was in the cave before
         //  then follow him by taking the first passage he
         //  taken by the Minotaur moving CCW

         // Minotaur was here... Light a candle and go left
         THEvert = 3;

         // Go left
         THECurEdge = NextLeftEdge(MAZE, THECurEdge);

         // Update edge number later...
         if ( MAZE.GetEdgeMark(THECurEdge) == 2 )
           THEedge = 3;
       }
       else
       if ( MAZE.GetVertexMark(THECurVertex) == 3 )
       {
         // Else if both he and the minotaur were here before 
         //   then still follow the Minotaur 
       
         // Go left
         THECurEdge = NextLeftEdge(MAZE, THECurEdge);
         
         // Update edge number later...
         if      ( MAZE.GetEdgeMark(THECurEdge) == 0 )
           THEedge = 1;
         else if ( MAZE.GetEdgeMark(THECurEdge) == 2 )
           THEedge = 3;
       }



       // *****************(      MINOTAUR       )**********

       // If no one was in this cavern before then take 
       //  first left passage
       if ( MAZE.GetVertexMark(MINCurVertex) == 0 ) 
       {
         // Mark the cavern
         MINvert = 2;

         // Take next left edge
         MINCurEdge = MINNextLeftEdge(MAZE,MINCurEdge);

         // Update edge
         if      ( MAZE.GetEdgeMark(MINCurEdge) == 0 )
           MINedge = 2;
         else if ( MAZE.GetEdgeMark(MINCurEdge) == 1 )
           MINedge = 3;
       }
       else
       if ( MAZE.GetVertexMark(MINCurVertex) == 2 )
       {
         // Been here before...Take next left edge
         MINCurEdge = MINNextLeftEdge(MAZE,MINCurEdge);
         
         // Update edge
         if      ( MAZE.GetEdgeMark(MINCurEdge) == 0 )
           MINedge = 2;
         else if ( MAZE.GetEdgeMark(MINCurEdge) == 1 )
           MINedge = 3;
       } 

    } // ****  else (not in same cavern)

    // Update marks
    MAZE.SetVertexMark(MINCurVertex, MINvert); 
    MAZE.SetVertexMark(THECurVertex, THEvert);
    MAZE.SetEdgeMark(MINCurEdge, MINedge);
    MAZE.SetEdgeMark(THECurEdge, THEedge);


  } // ****  while( 1 )


  return 0;

} // ****  int main()
   
