/* SwitchCointsLinkedList.cpp - Coins swapping program, using linked list to undo moves.

    The playing board is 5 squares.  Think of one coin each on the two left-most squares, 
    with "heads" shown on those coins.  The middle square is blank, and the two right-most
    squares each have a coin, with "tails" shown.  The object is to swap the coins.  
  
    For the sake of the program, we will represent "heads" as 'X', "tails" as 'O', and
    use an underscore '_' for a blank. The starting board configuration is then:
       XX_OO
    and the final board configuration is:
       OO_XX
    
    An X can only move to the right, and an O can only move to the left.  On each move you
    can move any piece into an adjacent square, or you can jump over an opposite piece into
    a blank square.  Thus an X can jump an O, but an X cannot jump another X (and similarly 
    from the perspective of O).
      
*/


#include <iostream>
using namespace std;

//------------------------------------------------------------------------------
// global constants and variables
//
const int BOARD_SIZE = 5;        // size of the board
char theBoard[ BOARD_SIZE] = {'X','X','_','O','O'};  // initial board configuration

// Declare node structure for linked list
struct Node {
       char theBoard[ BOARD_SIZE];        // copy of move number
       int moveNumber;                    // move number
       Node *pNext;                       // pointer to next node
};

//------------------------------------------------------------------------------
// displayIDinformation() - display identifying information
//
void displayIDinformation()
{
   cout<< "Name: Dale Reed\n"
       << "Date... etc. \n";
}//end displayIDinformation

    
//------------------------------------------------------------------------------
// displayInstructions()
// 
void displayInstructions()
{
	cout<< "Welcome to the coin swap program.  'X' represents heads, 'O'\n"
       << "represents tails.  To make a move, simply enter the number of \n"
       << "the square of the piece you wish to move or -1 to exit.\n"
       << "\n";
}//end displayInstructions()

         
//------------------------------------------------------------------------------
// displayBoard
//
void displayBoard( char theBoard[ ])
{
     cout << "1 2 3 4 5\n";
     for( int i=0; i<BOARD_SIZE; i++) {
          cout << theBoard[ i] << " ";    
     }
   cout << endl;
}// end displayBoard()


//-------------------------------------------------------------------------------------
// displayLinkedList()
//     display some of the entries from linked list, for debugging.
//
void displayLinkedList( Node *pHead)
{
     cout << "---- List ----" << endl;
     // traverse list, displaying some contents from each node as we go
     while( pHead != NULL) {
            // display contents
            cout << pHead->moveNumber << ". " << endl;
            displayBoard( pHead->theBoard);
            // advance head pointer to next node
            pHead = pHead->pNext;       
     } 
         
     cout << "------------" << endl << endl;     
}    

//-------------------------------------------------------------------------------------
// storeMoveOnList
//      Store the current move at the front of the linked list
//
void storeMoveOnList( Node * &pHead,        // head of list, Reference parm so changes are reflected back
                      int moveNumber)       // used to store current move number on the list
{
     Node *pOldHead = pHead;   // store old head of the list, since we are changing it
                               // but need new node to point to it.
                           
     pHead = new Node;         // allocate a new blank node
     pHead->pNext = pOldHead;  // points to previous node on list (or NULL if list is empty the first time)
     
     // duplicate the board into the node's copy of the board
     for( int i=0; i<BOARD_SIZE; i++) {
          pHead->theBoard[ i] = theBoard[ i];     
     }        
     // add the move number to the node
     pHead->moveNumber = moveNumber;
     
}//end storeMoveOnList


//-------------------------------------------------------------------------------------
//  undoMove( )
//     If there is more than 1 node on the list, remove the front-most node and
//     make the board and the robot locations look like the following node on the list,
//     which represents the previous move.
//
void undoMove( Node * &pHead,             // head of list, gets changed and returned
               int &moveNumber)           // move number, which gets decremented
{          
     // head node should always exist when we get here.  Perform sanity check
     if( pHead == NULL) {
         cout << "Error in program, pHead is NULL.  Exiting..." << endl;    
     }
     // verify that there is in fact a next move to use in the undo
     if( pHead->pNext != NULL) {
         // undo the move by removing the front node from the list, and restoring theBoard
         Node *pOldHead = pHead;      // store old head of list so we can free up the memory later
         pHead = pHead->pNext;        // advance the head pointer on the list, to retrieve its values
         
         // extract the board from the node, reflecting the previous move
         for( int i=0; i<BOARD_SIZE; i++) {
              theBoard[i] = pHead->theBoard[i];        
         }      
         
         // extract the move number from the one stored for this node
         moveNumber = pHead->moveNumber;
         
         delete( pOldHead);             // free up the memory from the old head of list node
     }      
     else {
         cout << "*** Can't undo past the beginning of the game.  Please retry. " << endl << endl;     
     }   
}//end undoMove()

 
//------------------------------------------------------------------------------
// Prompt for and get the position of the piece to move
// 
void promptAndGetPieceToMove(int &pieceToMove)
{
      cout << "Enter the square of the piece to move, or -1 to exit: ";
      cin >> pieceToMove;
      // See if -1 was entered to exit the program.  
      if (pieceToMove == -1) {
         cout << "Thanks for playing, goodbye. \n\n";
         exit( 0);
      }
      cout<< "You selected to move from square " << pieceToMove << "\n\n";
      pieceToMove--;       // subtract 1, since array indices start at 0, not 1
}//end promptAndGetPieceToMove()


//------------------------------------------------------------------------------
// Move the piece     
//   
void moveThePiece(int pieceToMove)
{
    // local variables
    char neighbor;          // character stored in neighbor, in direction to move
    char jumpDestination;   // character stored in destination if a jump is made
    int destination;        // destination square number for move
    int direction = 0;     // direction of moving: 1 is right, -1 is left

    // Find what direction we're moving.  Assume piece to move is not a blank,
    //     i.e. perfect input
    if( theBoard[ pieceToMove]=='X') {
       direction = 1;      // 'X' always moves right
    }
    else {
       // piece at that spot on board is 'O'
       direction = -1;     // 'O' always moves left
    } 
   
   // Using direction, find neighbor and destination position 
   destination = pieceToMove + direction;
   neighbor = theBoard[ destination];
   
   // if neighbor is occupied, we'll have to jump it, so find new destination
   if ( neighbor != '_') {
      // find destination when jumping, by moving TWO squares in the correct direction
      destination = pieceToMove + (direction*2);
      jumpDestination = theBoard[  destination];
   }   
    
   // Make the move
   char pieceBeingMoved;   // piece to move character
   // set the type of piece to be moved
   if ( direction == 1) {
      pieceBeingMoved = 'X';
   }
   else {
      pieceBeingMoved = 'O';
   }
   
   // store the piece being moved into new location
   theBoard[ destination] = pieceBeingMoved;
   // clear out the pieceToMove from the square it came from
   theBoard[ pieceToMove] = '_';
}//end moveThePiece()

        
//------------------------------------------------------------------------------
// See if we're done yet
//
bool seeIfWereDoneYet()
{
     bool returnValue = true;   // default value of true means we're not done yet
     
      if ( (theBoard[ 0]=='O') && (theBoard[ 1]=='O') && (theBoard[ 2] == '_') &&
           (theBoard[ 3]=='X') && (theBoard[ 4] == 'X')) {
         // We ARE done
         returnValue = false;   // notDone is false, since we ARE done
         cout<< "Congratulations, you did it!\n\n";
      }
      
      return returnValue;     
}//end seeIfWereDoneYet


//------------------------------------------------------------------------------
// main()
//
int main()
{	
   // declare variables
   bool notDone = true;    // flag telling whether or not the game is done
   int pieceToMove = -1;   // location of piece to be moved
   char userInput;         // userinput
   int moveNumber = 1;          // track how many moves have been made
   Node *pHead = NULL;          // initialize head of list pointer.  Very important to initialize this!
   
   // display identifying information
   displayIDinformation();
    
   // display instructions
   displayInstructions();

   // create the initial node on the list, containing the blank board
   storeMoveOnList( pHead, moveNumber);
    
   while ( notDone) {
      
      // display board
      displayBoard( theBoard);
      
      // Prompt for and get the position of the piece to move
      cout << "Enter the square of the piece to move, or x to exit: ";
      cin >> userInput;
      // See if 'x' was entered to exit the program.  
      if( userInput == 'x') {
         cout << "Thanks for playing, goodbye. \n\n";
         exit( 0);
      }
      // See if 'u' to undo was entered
      if( userInput == 'u') {
          // undo the move              
          undoMove( pHead, moveNumber);
          continue;     // go back up to back a move again
      }
      // input was a number, convert from character to numerical value.
      // subtract 1, since array indices start at 0, not 1
      pieceToMove = userInput - '0';
      pieceToMove--;       // subtract 1, since array indices start at 0, not 1
       
      // Move the piece, assuming it is a valid move
      moveThePiece( pieceToMove);
      
      // Store new move on linked list
      storeMoveOnList( pHead, moveNumber);
      
      // See if we're done yet
      notDone = seeIfWereDoneYet( ); 
   }

   return 0;
}