#include <iostream>
using namespace std;
#include <deque>

const int COORD_SIZE = 10;

struct coords
{
	int x;
	int y;
	coords* parent;
};// end struct

deque <coords*> openList;
deque <coords*> closedList;
coords* coord[COORD_SIZE];
coords* start;
coords* end;
coords* currentNode = new (coords);
coords* north = new (coords);
coords* south = new (coords);
coords* east = new (coords);
coords* west = new (coords);
coords* prior;
coords* path;
coords* node;

// function protoypes
void StartCoord();
void GoalCoord();
void AddNodeOpen(coords* node);
void AddNodeClosed(coords* node);
bool CheckEnd(coords* currentNode);
bool CheckNode(coords* node);
void DisplayOpen();
void DisplayClosed();

coords* CreateNorth(coords* currentNode);
coords* CreateEast(coords* currentNode);
coords* CreateSouth(coords* currentNode);
coords* CreateWest(coords* currentNode);

// main program
void main()
{		
	StartCoord();
	GoalCoord();

	// add start node to Open List
	AddNodeOpen(start);
	
	// check that the current node is not the goal node and node list is not empty
	while(currentNode != end || openList.empty())
	{
		// check is the openList is empty and break loop if true
		if(openList.empty())
		{
			cout<< "The list is empty!!"<< endl;
			break;
		}// end if
		
		//Pop the first element from the list and call it current
		currentNode = openList.front();
		openList.pop_front();

		//output current node!!!

		// check current node is goal node, break loop if true
		if(CheckEnd(currentNode))
		{
			cout<< "\nGoal co-ordinate found!!"<< endl;
			break;
		}// end if

		
		// create north node
		CreateNorth(currentNode);

		//create east node
		CreateEast(currentNode);

		//create south node
		CreateSouth(currentNode);

		// create west node
		CreateWest(currentNode);

		
		// check the list and add the new nodes if they are not already there
		if(CheckNode(north))			
		{
			AddNodeOpen(north);
		}// end if

		if(CheckNode(east))			
		{
			AddNodeOpen(east);
		}// end if

		if(CheckNode(south))			
		{
			AddNodeOpen(south);
		}// end if

		if(CheckNode(west))			
		{
			AddNodeOpen(west);
		}// end if

		// add current to closed list
		AddNodeClosed(currentNode);
		
		// display contents of list's
		DisplayOpen();
		DisplayClosed();

		system("pause");
	}// end while

	system("pause");
}//end main


// function that asks user for start co-ordinates
void StartCoord()
{
	int x, y;
	start = new (coords);
	cout<< "\nEnter start X co-ordinate: ";
	cin>> x;
	cout<< "\nEnter start Y co-ordinate: ";
	cin>> y;

	start->x = x;
	start->y = y;
	return;
}// end void StartCoord()


// function to ask user for goal co-ordinates
void GoalCoord()
{
	int x, y;
	end = new (coords);
	cout<< "\nEnter in destination X co-ordinate: ";
	cin>> x;
	cout<< "\nEnter in destination Y co-ordinate: ";
	cin>> y;

	end->x = x;
	end->y = y;
	return;
}// end void Goal Coord()


void AddNodeOpen(coords* node)
{
	node = new (coords);	
	openList.push_back(node);
}// end void addNodeOpen()


void AddNodeClosed(coords* node)
{
	node = new (coords);
	closedList.push_back(node);
}// end void addNodeClosed()


// function that checks if the current node is the goal co-ordinates
bool CheckEnd(coords* currentNode)
{
	if(currentNode == end)
	{
		return true;
	}else
	{
		return false;
	}
}// end bool check()


// function that checks if the node is in the OpenList already
bool CheckNode(coords* node)
{
	int x, y;
	x = node->x;
	y = node->y;

	// create lsit iterator
	deque <coords*>::iterator i;
	
	// assign iterator to start of openList
	i = openList.begin();

	// search through list untill the end,
	// and returns true if node is found
	while(i != openList.end())
	{
		if((*i)->x == x && (*i)->y == y)
		{
			return false;
		}
		i++;
	}
	return true;
}// end bool checkNode()


// function that creates a node north by 1
coords* CreateNorth(coords* currentNode)
{
	north->y = currentNode->y+1;
	north->x = currentNode->x;
	return north;	
}// end north()


// function that creates a node east by 1
coords* CreateEast(coords* currentNode)
{
	east->x = currentNode->x+1;
	east->y = currentNode->y;
	return east;
}// end east()


// function that creates a node south by 1
coords* CreateSouth(coords* currentNode)
{
	south->y = currentNode->y-1;
	south->x = currentNode->x;
	return south;
}// end south()


// function that creates a node west by 1
coords* CreateWest(coords* currentNode)
{
	west->x = currentNode->x-1;
	west->y = currentNode->y;
	return west;
}// end west()


void DisplayOpen()
{
	// create itterator
	deque <coords*>::iterator i;

	// asign iterator to start of open list
	i = openList.begin();
	
	cout<< "\nOpen list: "<< endl;
	// iterate through the list and display contents untill end of list
	while(i != openList.end())
	{
		cout<< (*i)->x<< " "<< (*i)->y<< endl;
		i++;
	}// end while
}// end void displayOpen()


void DisplayClosed()
{
	// create iterator
	deque <coords*>::iterator i;

	//asign iterator to start of closed list
	i = closedList.begin();

	cout<< "\nClosedList: "<< endl;
	// iterate through closed list adn display contents untill end of list
	while(i != closedList.end())
	{
		cout<< (*i)->x<< " "<< (*i)->y<< endl;
		i++;
	}// end while
}// end void displayClosed()

north->x = currentNode->x+1;north->y = currentNode->y;