#include "02Board.h"
#include <fstream.h>
#include <stdlib.h>

#include "02SolutionWindow.h"

Board::Board()
: itsSolutionWindow(NULL)
{
	int i=1;
	for(int y=0;y<4;y++)
		for(int x=0;x<4;x++)
			cards[x][y] = i++;
	cards[3][3] = 0;
}

Board::Board(const char *filename)
: itsSolutionWindow(NULL)
{
	ifstream in(filename,ios::in|ios::nocreate);

	bool cardPlaced[16];		// used to check for double
								// occurrences of one card.
	for(int i=0;i<16;i++)
		cardPlaced[i] = false;

	if(!in)
	{
		cerr << "Could not open file \"" << filename << "\".\n";
		exit(1);
	}

	for(int y=0;y<4;y++)
		for(int x=0;x<4;x++)
		{
			char c;

			in >> ws;
			if(!in)
			{
				cerr << "There is a problem at (" << x << ',' << y << ") in file \"" << filename << "\".\n";
				exit(1);
			}
			in >> c;

			int theCard;
			if(c == 'x' || c == 'X')
				theCard = kHole;
			else
			{
				in.putback(c);

				in >> theCard;
				if(!in)
				{
					cerr << "There is a problem at (" << x << ',' << y << ") in file \"" << filename << "\".\n";
					exit(1);
				}
			}

			if(theCard < 0 || theCard > 15)
			{
				cerr << "Card number out of range: " << theCard << endl;
				exit(1);
			}
			if(cardPlaced[theCard])
			{
				if(theCard == kHole)
					cerr << "\"X\"";
				else
					cerr << '"' << theCard << '"';
				cerr << " appears twice!\n";
				exit(1);
			}
			cardPlaced[theCard] = true;
			cards[x][y] = theCard;
		}
}


void Board::GetCardPosition(card c,int& x,int& y)
{
	for(x=0;x<4;x++)
		for(y=0;y<4;y++)
			if(cards[x][y] == c)
				return;
}

void Board::Move(int dx, int dy)
{
	int destX,destY;
	int srcX,srcY;
	GetCardPosition(kHole,destX,destY);

	srcX = destX-dx;
	srcY = destY-dy;

	if(itsSolutionWindow)
		itsSolutionWindow->DrawMove(cards[srcX][srcY],srcX,srcY,destX,destY);

	cards[destX][destY] = cards[srcX][srcY];
	cards[srcX][srcY] = kHole;
}

void Board::Move(int move)
{
	switch(move)
	{
		case kMoveUp:	Move(0,-1);
						break;
		case kMoveDown:	Move(0,1);
						break;
		case kMoveLeft:	Move(-1,0);
						break;
		case kMoveRight:Move(1,0);
						break;
	}
}


/////////////////////
//
// Board::IsSolvable
//
/////////////////////
//
// The algorithm is based on the fact that when the hole
// is at the same position is both start and final states,
// only an even number of "swaps" between any two cards
// can be performed.

bool Board::IsSolvable(Board *final)
{
	////// Step 1:
		// Create a temporary copy of this board, in case we want
		// to modify it (see step 2)
	Board tmp(*this);

	int x,y,x2,y2;

	////// Step 2:
		// Modify the temporary board so that its hole is at the
		// same position as that of the final board.
	tmp.GetCardPosition(kHole,x,y);
	final->GetCardPosition(kHole,x2,y2);

	while(x != x2)
	{
		if(x > x2)
		{
			tmp.Move(kMoveRight);
			x--;
		}
		else
		{
			tmp.Move(kMoveLeft);
			x++;
		}
	}
	while(y != y2)
	{
		if(y > y2)
		{
			tmp.Move(kMoveDown);
			y--;
		}
		else
		{
			tmp.Move(kMoveUp);
			y++;
		}
	}

	////// Step 3:
		// newX and newY are the final positions of all the cards.
		// (The index is the number on the card)
		// The boolean array "done", which will be used in step 4,
		// is initialized to false.

	int newX[16],newY[16];
	bool done[4][4];

	for(x=0;x<4;x++)
		for(y=0;y<4;y++)
		{
			newX[final->cards[x][y]] = x;
			newY[final->cards[x][y]] = y;
	
			done[x][y] = false;
		}
	
	////// Step 4:
		// Count the number of swaps that have to be done.
		// Starting from every card on the board, we look for
		// "cycles" of cards that are not on their final position.
		// A cycle length of 1 means that a card has been exchanged
		// with no other card and is on its final position.
		// Every cycle can be ordered with (cycle length - 1) swaps.

	int nSwaps = 0;
	for(x=0;x<4;x++)
		for(y=0;y<4;y++)
		{
			if(done[x][y])
				continue;
			
			x2 = x;
			y2 = y;

			int cycleSize = 0;
			do
			{
				card c = tmp.cards[x2][y2];
				x2 = newX[c];
				y2 = newY[c];

				done[x2][y2] = true;
				cycleSize++;
			} while((x2 != x) || (y2 != y));
			nSwaps += cycleSize -1;
		}

	////// Step 5:
		// return true if the number of swaps is even!
	return (nSwaps % 2) == 0;
}

void Board::ShowSolutionWindow()
{
	itsSolutionWindow = new SolutionWindow(this);
}