#include "8-puzzle.h"
#include <iostream>
#include <limits>
#include <ios>
#include <list>

using namespace std;

typedef list<state> StateList;

bool isRepeat(char);
bool isSolvable(int **board);
void locateZeroPos(int &i, int &j, state&);
void swap(state&, int i1, int j1, int i2, int j2);
bool pushSuccessor(state&);
void printBoard(state&);
void printPath(state&);

// The two lists used for *A.
StateList OPEN, CLOSED;

// Loop counters.
int i, j;

int main(){
	
	// Print the goal state.
	cout << "Goal State:" << endl;
	for(i = 0; i < 3; i++){
		for(j = 0; j < 3; j++){
			if(goalState(i, j) == 0){
				cout << "  ";
			} else {
				cout << goalState(i, j) << " ";
			}
		}
		cout << endl;
	}
	cout << endl;

	while(true){
		// Prompt for input.
		cout << "Initial State (input): ";
	
		// Allocate memory for board.
		int **board = new int*[3];
		for (i = 0; i < 3; i++){
			board[i] = new int[3];
		}

		// Get input.
		char nextChar;
		bool isValidInput = true;
		for(i = 0; (i < 3) && isValidInput; i++){
			for(j = 0; (j < 3) && isValidInput; j++){
				cin >> nextChar;
				if(nextChar == 'E' || nextChar == 'e'){
					return 0;
				} else if (nextChar < '0' || nextChar > '8' || isRepeat(nextChar)){
					cout << "Incorrect input, you must input one of each number from 0 to 8.";
					cout << endl << "For example, the input '1 2 3 8 0 4 7 6 5' corresponds to the goal state.";
					cout << endl << endl;
					isValidInput = false;
				} else {
					board[i][j] = (nextChar - '0');
				}
			}
		}
		cout << endl;

		if(!isValidInput){
			// Ignore the rest of the characters in cin.
			cin.ignore(numeric_limits<streamsize>::max(), '\n');

			// Delete the board.
			for(int i = 0; i < 3; i++){
				delete[] board[i];
			}
			delete[] board;

			// Reset the static array in isRepeat.
			isRepeat('R');
			continue;
		}

		// Check solvability.
		if(!isSolvable(board)){
			cout << endl << "This initial state does not have a solution!" << endl << endl;

			// Delete the board.
			for(int i = 0; i < 3; i++){
				delete[] board[i];
			}
			delete[] board;

			// Reset the static array in isRepeat.
			isRepeat('R');
			continue;
		}
		
		// Two iterators used in A*.
		StateList::iterator iter;
		StateList::iterator minIter;

		// State pointer used for creating the successor states.
		state *toPush;

		// Repeats the A* algorithim once for each heuristic.
		for(int HTYPE = 1; HTYPE < 4; HTYPE++){
			cout << "Using Heuristic " << HTYPE << "..." << endl << endl;

			// (Step 1)
			// Set up initial state and put it on OPEN.
			state *initial = new state(board, NULL, 0);
			OPEN.push_back(*initial);

			// Print initial state.
			printBoard(*initial);

			// Repeat steps 2 through 5 until goal state is produced.
			while(true){
				// (Step 2)
				// If OPEN is empty, exit with failure.
				if(OPEN.empty()){
					cout << "Error";
					break;
				}

				// (Step 3)
				// Find the best state in OPEN and remove it.
				minIter = OPEN.begin();
				for(iter = ++(OPEN.begin()); iter != OPEN.end(); iter++){
					if((iter->f(HTYPE) < minIter->f(HTYPE)) || isGoalState(*iter)){
						minIter = iter;
					}
				}
				iter = minIter;
				CLOSED.splice(CLOSED.begin(), OPEN, minIter, ++iter);
				minIter = CLOSED.begin();
		
				// (Step 4)
				// If the goal state is found, success!
				if(isGoalState(*minIter)){
					printPath(*minIter);
					break;
				}
	
				// (Step 5)
				// Generate all possible successors and attempt to push them.
				locateZeroPos(i, j, *minIter);

				// If the zero space is not in the top row, 'DOWN' is a valid move.
				// Otherwise 'DOUBLE-UP' is a valid move.
				if(i != 0){
					toPush = new state(*minIter);
					swap(*toPush, i, j, i-1, j);
					toPush->setMove("DOWN");
					toPush->setAsSuccessorOf(*minIter);
					if(!pushSuccessor(*toPush)){delete toPush;}
				} else if(HTYPE == 3){
					toPush = new state(*minIter);
					swap(*toPush, i, j, i+1, j);
					swap(*toPush, i+1, j, i+2, j);
					toPush->setMove("DBL-UP");
					toPush->setAsSuccessorOf(*minIter);
					if(!pushSuccessor(*toPush)){delete toPush;}
				}
				
				// If the zero space is not in the bottom row, 'UP' is a valid move.
				// Otherwise 'DOUBLE-DOWN' is a valid move.
				if(i != 2){
					toPush = new state(*minIter);
					swap(*toPush, i, j, i+1, j);
					toPush->setMove("UP");
					toPush->setAsSuccessorOf(*minIter);
					if(!pushSuccessor(*toPush)){delete toPush;}
				} else if(HTYPE == 3){
					toPush = new state(*minIter);
					swap(*toPush, i, j, i-1, j);
					swap(*toPush, i-1, j, i-2, j);
					toPush->setMove("DBL-DOWN");
					toPush->setAsSuccessorOf(*minIter);
					if(!pushSuccessor(*toPush)){delete toPush;}
				}
	
				// If the zero space is not in the left column, 'RIGHT' is a valid move.
				// Otherwise 'DOUBLE-LEFT' is a valid move.
				if(j != 0){
					toPush = new state(*minIter);
					swap(*toPush, i, j, i, j-1);
					toPush->setMove("RIGHT");
					toPush->setAsSuccessorOf(*minIter);
					if(!pushSuccessor(*toPush)){delete toPush;}
				} else if(HTYPE == 3){
					toPush = new state(*minIter);
					swap(*toPush, i, j, i, j+1);
					swap(*toPush, i, j+1, i, j+2);
					toPush->setMove("DBL-LEFT");
					toPush->setAsSuccessorOf(*minIter);
					if(!pushSuccessor(*toPush)){delete toPush;}
				}

				// If the zero space is not in the right column, 'LEFT' is a valid move.
				// Otherwise 'DOUBLE-RIGHT' is a valid move.
				if(j != 2){
					toPush = new state(*minIter);
					swap(*toPush, i, j, i, j+1);
					toPush->setMove("LEFT");
					toPush->setAsSuccessorOf(*minIter);
					if(!pushSuccessor(*toPush)){delete toPush;}
				} else if(HTYPE == 3){
					toPush = new state(*minIter);
					swap(*toPush, i, j, i, j-1);
					swap(*toPush, i, j-1, i, j-2);
					toPush->setMove("DBL-RIGHT");
					toPush->setAsSuccessorOf(*minIter);
					if(!pushSuccessor(*toPush)){delete toPush;}
				}
			}

			// Clear the two lists.
			OPEN.clear();
			CLOSED.clear();
		}

		// Delete the board.
		for(int i = 0; i < 3; i++){
			delete[] board[i];
		}
		delete[] board;

		// Reset the static array in isRepeat.
		isRepeat('R');
	}

	return 0;
}

// Returns false if the function has not been called with
// the number (0-8) represented by toCheck since the last reset.
// Resets the static array when toCheck == 'R'.
bool isRepeat(char toCheck){
	static int notUsed[] = {0, 1, 2, 3, 4, 5, 6, 7, 8};

	if(toCheck == 'R'){
		for(int i = 0; i < 9; i++){notUsed[i] = i;}
		return true;
	} else if(notUsed[(toCheck - '0')] != -1){
		notUsed[(toCheck - '0')] = -1;
		return false;
	}

	return true;
}

// Returns true if the given board is solvable.
bool isSolvable(int **board){
	int numInversions = 0;
	for(int k = 0; k < 9; k++){
		int val = board[k/3][k%3];
		if(val == 0){continue;}
		for(int i = k/3; i < 3; i++){
			for(int j = (i == k/3 ? k%3 : 0); j < 3; j++){
				if(board[i][j] != 0){
					numInversions += val > board[i][j];
				}
			}
		}
	}
	return (numInversions % 2) == 1;
}

// Finds the zero position of st and stores it in i and j.
void locateZeroPos(int &i, int &j, state &st){
	for(i = 0; i < 3; i++){
		for(j = 0; j < 3; j++){
			if(st.getVal(i, j) == 0) return;
		}
	}
}

// Swaps two numbers in a state.
void swap(state &st, int i1, int j1, int i2, int j2){
	int temp = st.getVal(i1, j1);
	st.setVal(i1, j1, st.getVal(i2, j2));
	st.setVal(i2, j2, temp);
}

// Attempts to push the successor state 'st' onto OPEN.
// Returns false if st is not pushed.
bool pushSuccessor(state &st){
	StateList::iterator iter;

	// If st is in OPEN and st's f() value is less then the
	// existing f() value, erase the existing and push st on OPEN.
	for(iter = OPEN.begin(); iter != OPEN.end(); iter++){
		if(st == *iter){
			if(st.getG() < iter->getG()){
				OPEN.erase(iter);
				OPEN.push_back(st);
				return true;
			} else {
				return false;
			}
		}
	}

	// If st is in CLOSED and st's f() value is less then the
	// existing f() value, erase the existing and push st on OPEN.
	for(iter = CLOSED.begin(); iter != CLOSED.end(); iter++){
		if(st == *iter){
			if(st.getG() < iter->getG()){
				CLOSED.erase(iter);
				OPEN.push_back(st);
				return true;
			} else {
				return false;
			}
		}
	}

	// Push st on OPEN.
	OPEN.push_back(st);
	return true;
}

// Prints the board of the given state.
void printBoard(state &st){
	for(i = 0; i < 3; i++){
		for(j = 0; j < 3; j++){
			if(st.getVal(i, j) == 0){
				cout << "  ";
			} else {
				cout << st.getVal(i, j) << " ";
			}
		}
		cout << endl;
	}
}

// Prints the path of the given state all the way up to
// the initial state.
// The number of moves from the initial state to the
// given state is also printed.
void printPath(state &st){
	StateList path;
	state *cur = &st;

	while(cur->getParent() != NULL){
		path.push_front(*cur);
		cur = cur->getParent();
	}

	while(!path.empty()){
		cout << endl << path.front().getMove() << endl << endl;
		printBoard(path.front());
		path.pop_front();
	}

	cout << endl << st.getG() << " moves in total." << endl << endl << endl;
}