#include <iostream>
#include <fstream>
#include "stack.h"
using namespace std;
typedef NodeType* NodePtr;
 
struct NodeType
{
    ItemType x;
    ItemType y;
    ItemType check;
    NodePtr  next;
};
 
Stack::Stack()
{
  stackPtr = NULL;
  length = 0;
}
int Stack::topX()
{
  return stackPtr->x;
}
int Stack::topY()
{
  return stackPtr->y;
}
int Stack::topCheck()
{
  return stackPtr->check;
}
 
void Stack::push(ItemType x, ItemType y, ItemType check)
{
  NodePtr ptr;
  ptr = new NodeType;
  ptr->x = x;
  ptr->y = y;
  ptr->check = check;
  ptr->next = stackPtr;
  stackPtr = ptr;
  length++;
  print();
}
 
void Stack::pop()
{
  NodeType *tempPtr;
  tempPtr = stackPtr;
  stackPtr = stackPtr->next;
  delete tempPtr;
  length--;
  print();
}
 
bool Stack::isThere(ItemType x, ItemType y)
{
  NodeType *Ptr;
  int q=0;
  Ptr = stackPtr;
  while((Ptr->x != x) && (Ptr->y != y))
    {
      if(Ptr == NULL)
        return 0;
      if(length == q)
        return 0;
      Ptr= Ptr->next;
      q++;
    }
   return 1;
}
 
void  Stack::print() const
// Post: Items on the list are printed on the screen.
{
    if (stackPtr == NULL)
      cout << "List is empty\n";
    else
    {
      NodeType *ptr;
      ptr = stackPtr;
      while(ptr != NULL)
       {
          cout << "PRINT\n";
          cout << "X: " << ptr->x << endl;
          cout << "y: " << ptr->y << endl;
          cout << "Check: " << ptr->check << endl << endl;
          ptr = ptr->next;
        }
    }
}
 
//********************//
//*End Implementation*//
//********************//
 
 
void getData(int**,int&,int&);
void print(int**,int,int);
bool Check(Stack&,int**,int&,int&,int&,int,int,int&);
void Solve(Stack&,int**,int&,int&,int&,int,int,int&);
 
int main()
{
  int **array;
  int row, column;
  int x=0,y=0,check=0,old=0;
  Stack myStack;
  myStack.push(x,y,check);
  string fileName;
  ifstream data;  
 
  ///////////////
  ////GetData////
  ///////////////
  cout << "Enter File Name\n";
  getline(cin, fileName);
  data.open(fileName.c_str());
  if (!data.is_open())
    cout << "Error opening file\n";
  else
    {
      data >> row >> column;
      array = new int*[column]; //Allocates memory for the array
      for (int q = 0; q < column; ++q)
        array[q] = new int[row];
      for(int y=0; y < row; y++)
        {
          for(int x=0; x < column; x++)
            {
              data >> array[y][x];
            }
        }
    }
  data.close();
  ///////////////
  //End GetData//
  ///////////////
 
  print(array,row,column); //Before
  Solve(myStack,array,x,y,check,column,row,old);
  print(array,row,column); //After
 
  system("PAUSE");
  return 0;
}
 
void Solve(Stack &myStack,int **array,int &x,int &y,int &check,int column,int row,int &old)
{
  if((y > column)&&(x > row))
    return;
  if((Check(myStack,array,x,y,check,column,row,old))== 0)
    {
      cout << "IF\n";      
      check = myStack.topCheck();
      myStack.pop();
      x = myStack.topX();
      y = myStack.topY();
      old = check;
    }
  else
    {
      cout << "ELSE\n";
      myStack.push(x,y,check);
      switch(check)
        {
          case 1: old = 3;
            break;
          case 2: old = 4;
            break;
          case 3: old = 1;
            break;
          case 4: old = 2;
            break; 
        }
      check = 1;
    }
  Solve(myStack,array,x,y,check,column,row,old);
}
 
bool Check(Stack &myStack,int **array,int &x,int &y,int &check,int column,int row,int &old)
{
  cout << "IN Check: ";
  cout << check << endl;
 
  if(check > 4)
    {
      cout << "Return to solve\n";
      return 0;
    }
  if(check == old)
    check++;
  switch(check)
    {
      //Check Right
      case 1: 
          if(((x+1) > column)||((array[y][x+1]) == 1))
            {
              check++;
            }
          else
            {
              //myStack.push((x+1),y,check);
              x++;
              cout << "return 1" << endl;
              return 1;                
            }
        break;
      //Check Down
      case 2:
          if(((y+1) > row)||((array[y+1][x]) == 1))
            {
              check++;
            }
          else
            {
              //myStack.push(x,y,check);
              y++;
              cout << "return 1" << endl;
              return 1;                 
            }
        break;
      //Check Left
      case 3:
          if(((x-1) < 0)||((array[y][x-1]) == 1))
            {
              check++;
            }
          else
            {
              //myStack.push((x-1),y,check);
              x--;
              cout << "return 1" << endl;
              return 1; 
            }
        break;
      //Check Up
      case 4:
          if(((y-1) < 0)||((array[y-1][x]) == 1))
            {
              check++;
            }
          else
            {
              //myStack.push(x,(y-1),check);
              y--;
              cout << "return 1" << endl;              
 
              return 1;                
            }
        break;
    }
  Check(myStack,array,x,y,check,column,row,old);    
} 
 
void print(int **array, int row, int column)
{
  for(int y=0; y < row; y++)
    {
      cout << endl;
      for(int x=0; x < column; x++)
        {
          if(array[y][x] == 2)
            cout << "* ";
          else
            cout << array[y][x] << " ";
        }
    }
  cout << endl;
}