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

// Given two vertices & the Maze...find the edge between them.
Edge EdgeBetween(InfoGraph<String,String> MAZE, Vertex SourceV, Vertex TargetV)
{
  Edge CurrentEdge;
  CurrentEdge = MAZE.FirstDepartEdge(SourceV);
  
  while ( !(MAZE.IsNil(CurrentEdge)) )
  {
    if( MAZE.Target(CurrentEdge) == TargetV )
      return CurrentEdge;
    else
      CurrentEdge = MAZE.NextDepartEdge(CurrentEdge);
  }
    
  cout << "(1)ERROR...Never should have made it this far!" << endl;
}


// Next DEPARTING edge when being given an INCOMING edge....
// THESEUS ************ ONLY
Edge NextRightEdge(InfoGraph<String,String> MAZE, Edge CurEdge)
{
  Edge NextEdge;
 
  CurEdge = EdgeBetween( MAZE,MAZE.Target(CurEdge),MAZE.Source(CurEdge) );
  
  NextEdge = MAZE.NextDepartEdge(CurEdge);
  
  if ( MAZE.IsNil(NextEdge) )
    NextEdge = MAZE.FirstDepartEdge(MAZE.Source(CurEdge));

  while ( !(MAZE.IsNil(NextEdge)) )
  {
    if ( (MAZE.GetEdgeMark(NextEdge) == 0) || (MAZE.GetEdgeMark(NextEdge) == 2) )
      return NextEdge;
    else
      NextEdge = MAZE.NextDepartEdge(NextEdge);
  }
  cout << "(2)ERROR.............all edges taken...should not happen" << endl;
}    



// Used by the THESEUS ONLY*********************
// Next Left Departing Edge when given an incoming one.
//Edge NextLeftEdge(InfoGraph<String,String> MAZE, Edge CurEdge)
//{
//  Edge PrevEdge;   
//
//  CurEdge = EdgeBetween( MAZE,MAZE.Target(CurEdge),MAZE.Source(CurEdge) );
//
//  PrevEdge = MAZE.PrevDepartEdge(CurEdge); 
//
//  if ( MAZE.IsNil(PrevEdge) )
//    PrevEdge = MAZE.LastDepartEdge(MAZE.Source(CurEdge));
//
//
// Take left if Minotaur took this exit.
//  while ( !(MAZE.IsNil(PrevEdge)) )
//  {
//    if ( (MAZE.GetEdgeMark(PrevEdge) == 0) || (MAZE.GetEdgeMark(PrevEdge) == 2) )
//      return PrevEdge;
//    else
//      PrevEdge = MAZE.PrevDepartEdge(PrevEdge);
//  }
//  cout << "(3)ERROR....all edges taken...should not happen" << endl;
//} 



// Used by the THESEUS ONLY*********************
// Next Left ...go right and find first edge soiled by Minotaur
Edge NextLeftEdge(InfoGraph<String,String> MAZE, Edge CurEdge)
{     
  Edge NextEdge;
    
  CurEdge = EdgeBetween( MAZE,MAZE.Target(CurEdge),MAZE.Source(CurEdge) );
  
  NextEdge = MAZE.NextDepartEdge(CurEdge);
    
  if ( MAZE.IsNil(NextEdge) )
    NextEdge = MAZE.FirstDepartEdge(MAZE.Source(CurEdge));
      
  
  // Take left if Minotaur took this exit.
  while ( !(MAZE.IsNil(NextEdge)) )
  {
    if ( (MAZE.GetEdgeMark(NextEdge) == 3) || (MAZE.GetEdgeMark(NextEdge) == 2) )
      return NextEdge;
    else
      NextEdge = MAZE.PrevDepartEdge(NextEdge);
  }
  cout << "(3)ERROR....all edges taken...should not happen" << endl;
} 





// Used by the MIN ONLY*********************
Edge MINNextLeftEdge(InfoGraph<String,String> MAZE, Edge CurEdge)	
{
  Edge PrevEdge;
  
  CurEdge = EdgeBetween( MAZE,MAZE.Target(CurEdge),MAZE.Source(CurEdge) );
  
  PrevEdge = MAZE.PrevDepartEdge(CurEdge);
  
  if ( MAZE.IsNil(PrevEdge) )
    PrevEdge = MAZE.LastDepartEdge(MAZE.Source(CurEdge));
    
  while ( !(MAZE.IsNil(PrevEdge)) )
  {
    if ( (MAZE.GetEdgeMark(PrevEdge) == 0) || (MAZE.GetEdgeMark(PrevEdge) == 1) )
      return PrevEdge;
    else
      PrevEdge = MAZE.PrevDepartEdge(PrevEdge);
  }
  cout << "(4)ERROR.............all edges taken...should not happen" << endl;
}


//***************************************************************************
int main()
{
  int NotDead = 1;
  char input[100], input2[100], input3[4]; 
  String Sinput, Sinput2; 
  char ONE[100], TWO[100], THREE[100], FOUR[100];
  String S1,S2,S3,S4;
  String FromC, 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 test=0;
  int THEvert,MINvert,THEedge,MINedge;

  InfoGraph<String,String> MAZE;     // For now assign INT values to vertexes & edges

  map<String,Vertex,less<String> > Cavern;
  map<String,Edge,less<String> > Passage; 

  while ( cin >> input )
  {
    Value = input;
    
    if ( Value == "FROM" )
    {
      cin >> input >> input2 ;
      FromC = input;

      if ( Cavern.find(FromC) == Cavern.end() )
      {
         Cavern[FromC] = MAZE.InsertVertex(FromC);
         MAZE.SetVertexMark(Cavern[FromC], 0);
      }
    }
    else if ( Value == "END" )
    {
      cin >> ONE >> TWO >> THREE >> FOUR;
      S1 = ONE; S2 = TWO; S3 = THREE; S4 = FOUR;

      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);

      MAZE.EdgeAssign(Passage[S1+S2],S1+S2);
        MAZE.SetEdgeMark(Passage[S1+S2],1);
      MAZE.EdgeAssign(Passage[S2+S1],S2+S1);
        MAZE.SetEdgeMark(Passage[S2+S1],1);

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

      MAZE.EdgeAssign(Passage[S3+S4],S3+S4);
        MAZE.SetEdgeMark(Passage[S3+S4],2); 

      MAZE.EdgeAssign(Passage[S4+S3],S4+S3);
        MAZE.SetEdgeMark(Passage[S4+S3],2);      
 
      cout << "\n START THROUGH MAZE " << endl;
    }
    else
    {
      ToC = input;

      if ( Cavern.find(ToC) == Cavern.end() )
      {
         Cavern[ToC] = MAZE.InsertVertex(ToC);
           MAZE.SetVertexMark(Cavern[ToC],0);
      }

      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 )


// **************************************************************************
/*
  cout << MAZE.EdgeInfo(EdgeBetween(MAZE,Cavern[S1],Cavern[S2])) << endl;
  cout << MAZE.EdgeInfo(NextRightEdge(MAZE,Passage[S1+S2])) << endl;
  cout << MAZE.EdgeInfo(EdgeBetween(MAZE,Cavern[S2],Cavern[S1])) << endl;
  cout << MAZE.EdgeInfo(NextRightEdge(MAZE,Passage[S2+S1])) << endl;
  cout << endl;
  cout << MAZE.EdgeInfo(NextRightEdge(MAZE,NextRightEdge(MAZE,Passage[S2+S1]))) << endl;
  cout << MAZE.EdgeInfo(NextRightEdge(MAZE,Passage["AcavernDcavern"])) << endl;
  cout << "Info D->B  " << MAZE.GetEdgeMark(Passage["DcavernCcavern"]) << endl;
  cout << "   First = " << MAZE.EdgeInfo(MAZE.FirstDepartEdge(Cavern["Dcavern"])) 
       << "   NEXT  = " << MAZE.EdgeInfo(MAZE.NextDepartEdge(MAZE.FirstDepartEdge(Cavern["Dcavern"])))
       << "   Last  = " << MAZE.EdgeInfo(MAZE.LastDepartEdge(Cavern["Dcavern"])) << endl;
  cout << " NextLeft  " << MAZE.EdgeInfo(NextLeftEdge(MAZE,Passage["BcavernDcavern"])) << endl;
*/
// ***************************************************************************



  while ( NotDead )
  {
    THEvert = MAZE.GetVertexMark(THECurVertex);
    MINvert = MAZE.GetVertexMark(MINCurVertex); 
    THEedge = MAZE.GetEdgeMark(THECurEdge);
    MINedge = MAZE.GetEdgeMark(MINCurEdge);


    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
    {
      THECurVertex = MAZE.Target(THECurEdge);

      // Minotaur checks if candle is ahead in upcoming cavern (Vertex)
      if ( MAZE.GetVertexMark(MAZE.Target(MINCurEdge)) == 3 )
        MINCurVertex = MAZE.Source(MINCurEdge);    // Sees candle ... returns to original Cavern 
      else
        MINCurVertex = MAZE.Target(MINCurEdge);    // NO candle ... keep walking to intended Cavern
    }

    // Update current positions and marks
// **************
    if ( MAZE.GetVertexMark(THECurVertex) == 2 )
    {
      MAZE.SetVertexMark(THECurVertex, 3);
      THEvert = 3;
    }

    if ( MAZE.GetVertexMark(MINCurVertex) == 0 )
    {
      MAZE.SetVertexMark(MINCurVertex, 2);
      MINvert = 2;
    }
// *************

  
// Now select an edge  
    // 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 ( MAZE.GetVertexMark(THECurVertex) == 0 )
       {   
         // Never been here before and neither has the Minotaur  --> Next Right
         THECurEdge = NextRightEdge(MAZE, THECurEdge);
           
         // Update edge number later...
         if      ( MAZE.GetEdgeMark(THECurEdge) == 0 )
           THEedge = 1;
         else if ( MAZE.GetEdgeMark(THECurEdge) == 1 )
           cout << "( 1 )Error: Should have never entered this edge" << endl;
         else if ( MAZE.GetEdgeMark(THECurEdge) == 2 ) 
           THEedge = 3;
         else if ( MAZE.GetEdgeMark(THECurEdge) == 3 )
           cout << "( 2 )Error: Should have never entered this edge" << endl;
         else
           cout << "( 3 )Error: No choice worked " << endl;
       }
       else
       if ( MAZE.GetVertexMark(THECurVertex) == 1 )
       {
         cout << "( 4 )Error: Cavern Marked 1" << endl;
       }
       else
       if ( MAZE.GetVertexMark(THECurVertex) == 2 )
       {
         // 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) == 0 )
           THEedge = 1;
         else if ( MAZE.GetEdgeMark(THECurEdge) == 1 )
           cout << "( 5 )Error: Should have never entered this edge" << endl;
         else if ( MAZE.GetEdgeMark(THECurEdge) == 2 )
           THEedge = 3;
         else if ( MAZE.GetEdgeMark(THECurEdge) == 3 )
           cout << "( 6 )Error: Should have never entered this edge" << endl;
         else
           cout << "( 7 )Error: No choice worked " << endl;
       }
       else
       if ( MAZE.GetVertexMark(THECurVertex) == 3 )
       {
         // I THINK since the Minotaur was once here, even though a candle is lit,
         //  then you should still follow next left passage. 
       
         // Go left
         THECurEdge = NextLeftEdge(MAZE, THECurEdge);
         
         // Update edge number later...
         if      ( MAZE.GetEdgeMark(THECurEdge) == 0 )
           THEedge = 1;
         else if ( MAZE.GetEdgeMark(THECurEdge) == 1 )
           cout << "( 5 )Error: Should have never entered this edge" << endl;
         else if ( MAZE.GetEdgeMark(THECurEdge) == 2 )
           THEedge = 3;
         else if ( MAZE.GetEdgeMark(THECurEdge) == 3 )
           cout << "( 6 )Error: Should have never entered this edge" << endl;
         else
           cout << "( 7 )Error: No choice worked " << endl;
       }



       // *****************(      MINOTAUR       )*********************
       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.GetEdgeMark(MINCurEdge) == 2 )
           cout << "( 8 )Error: Never should have entered" << endl;
         else if ( MAZE.GetEdgeMark(MINCurEdge) == 3 )
           cout << "( 9 )Error: Never should have entered" << endl;
         else
           cout << "( 10 )Error: No choice worked " << endl;
       }
       if ( MAZE.GetVertexMark(MINCurVertex) == 1 )
       {
         cout << "( 11 )Error: This situation does not exist" << endl;
       } 
       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 if ( MAZE.GetEdgeMark(MINCurEdge) == 2 )
           cout << "( 12 )Error: Never should have entered" << endl;
         else if ( MAZE.GetEdgeMark(MINCurEdge) == 3 )
           cout << "( 13 )Error: Never should have entered" << endl;          
         else
           cout << "( 14 )Error: No choice worked " << endl;
       } 
       if ( MAZE.GetVertexMark(MINCurVertex) == 3 )
       {
           cout << "( 15 )Error: candle was lit...should have never entered " << endl;
       }

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



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



  } // ****  while( NotDead )

} // ****  int main()
   
