//****************************************************************************
//
// Function:   Checker
//
// Purpose:    C-tor
//
// Parameters: none
//
// Calls:      none
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


#include "checker.h"


Checker::Checker()
{
}


//****************************************************************************
//
// Function:   ~Checker
//
// Purpose:    X-tor
//
// Parameters: none
//
// Calls:      none
//
// Time Comp:  O(n) n = width of checker board
//
// Space Com:  O(1)
//
//****************************************************************************


Checker::~Checker()
{
   for(size_t i(0); i < size + 2; ++i)
   {
      if(i < size)
      {
         delete [] where_from[i];
      }
      delete [] payroll[i];
   }
   delete [] where_from;
   delete [] payroll;
}


//****************************************************************************
//
// Function:   get_data
//
// Purpose:    Get the size of checker board, and the values of the payoff
//             matrix.
//
// Parameters: none
//
// Calls:      getline, get, peek, new
//
// Time Comp:  O(n^2) n = size of checker board
//
// Space Com:  O(n^2) n = size of checker board
//
//****************************************************************************


void Checker::get_data()
{
   string comment;
   
   while(cin.peek() == '#')
   {  //get rid of comments
      getline(cin, comment);
   }
   
   cin >> size;  //the diminsion of the checker board
   cin.get();  //remove white space or end of line
   
   while(cin.peek() == '#')
   {  //get rid of commets
      getline(cin, comment);
   }

   payroll = new int* [size + 2];  //perimeter of -infinity to deal with edges
   where_from = new size_t* [size];
   
   for(size_t i(0); i < size + 2; ++i)  //O(n) n = size of board
   {  //create both 2d arrays
      if(i < size)
      {
         where_from[i] = new size_t [size];
      }
      payroll[i] = new int [size + 2];
   }
   
   for(size_t i(0); i < size + 2; ++i)
   {  //O(n)
      for(size_t j(0); j < size + 2; ++j)
      {  //O(n)
         if((i < size) && (j < size))
         {
            where_from[i][j] = 0;  //initualize to all zeros
         }
         if((i == 0) || (i == size + 1) || (j == 0) || (j == size + 1))
         {
            payroll[i][j] = INT_MIN;  //negative infinity
         }
         else
         {
            cin >> payroll[i][j];
         }
      }
   }
}


//****************************************************************************
//
// Function:   build_table
//
// Purpose:    Here we use dynamic programming to build the optimal solution
//             from previous solutions.
//
// Parameters: none
//
// Calls:      exit, break
//
// Time Comp:  O(n^2) n = width of the checker board
//
// Space Com:  O(1)
//
//****************************************************************************


void Checker::build_table()
{
   int max_num = INT_MIN;
   int k;

   for(size_t i(2); i < size + 1; ++i)
   {  //O(n)
      for(size_t j(1); j < size + 1; ++j)
      {  //O(n)

         k = -1;  //this is the last option
         if(payroll[i - 1][j + k] > max_num)
         {  //use which ever square gives the highest payoff
            max_num = payroll[i - 1][j + k];
            where_from[i - 1][j - 1] = 3;
         }
         k = 1;  //this is the middle option
         if(payroll[i - 1][j + k] >= max_num)
         {  //use which ever square gives the highest payoff
            max_num = payroll[i - 1][j + k];
            where_from[i - 1][j - 1] = 2;
         }
         k = 0;  //we want to go straight if we can
         if(payroll[i - 1][j + k] >= max_num)
         {  //use which ever square gives the highest payoff
            max_num = payroll[i - 1][j + k];
            where_from[i - 1][j - 1] = 1;
         }
         payroll[i][j] += max_num;
         max_num = INT_MIN;
      }
   }
}


//****************************************************************************
//
// Function:   find_max
//
// Purpose:    Search the top row to find the maximum payoff
//
// Parameters: none
//
// Calls:      none
//
// Time Comp:  O(n) n = width of checker board
//
// Space Com:  O(1)
//
//****************************************************************************


void Checker::find_max()
{
   int max_num = INT_MIN;
   for(size_t i(1); i < size + 1; ++i)
   {  //O(n)
      if(payroll[size][i] > max_num)
      {
         max_num = payroll[size][i];
         end_position = i;
      }
   }
}


//****************************************************************************
//
// Function:   output_path
//
// Purpose:    Calls recursive work horse function.
//
// Parameters: none
//
// Calls:      output_path
//
// Time Comp:  O(n) n = width of checker board
//
// Space Com:  O(n) n = width of checker board
//
//****************************************************************************


void Checker::output_path()
{
   output_path(size, end_position);
}


//****************************************************************************
//
// Function:   output_path
//
// Purpose:    Outputs the path that gives the highest payoff.
//
// Parameters: row - row of the checker board
//             col - column of the checker board
//
// Calls:      output_path
//
// Time Comp:  O(n) n = width of checker board
//
// Space Com:  O(n) n = width of checker board
//
//****************************************************************************


void Checker::output_path(size_t row, size_t col)
{
   if(where_from[row - 1][col - 1] == 0)  //this is the starting row, we
   {                                     //output it's info first and new line
      cout << col - 1 << endl;
   }
   else  //output the path from bottom up
   {
      switch(where_from[row - 1][col - 1])
      {
         case 1: output_path(row - 1, col); break;
         case 2: output_path(row - 1, col + 1); break;
         case 3: output_path(row - 1, col - 1); break;
         default: exit(EXIT_FAILURE); break;
      }
      cout << where_from[row - 1][col - 1];
      if(row != size)  //we don't want any extraneous characters
      {
         cout << ' ';
      }
   }
}


//****************************************************************************
//
// Function:   output_dollars
//
// Purpose:    Print out the total payoff.
//
// Parameters: none
//
// Calls:      none
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


void Checker::output_dollars()
{
   cout << endl << '$' << payroll[size][end_position];
}