class Compare
{
public:
 bool operator()(shared_ptr<Puzzle> puzzA, shared_ptr<Puzzle> puzzB)
 {
	 if (Search::F(puzzA) > Search::F(puzzB))
		return true;
	else
		return false;

 }
};

shared_ptr<Puzzle> Search::AStar(shared_ptr<Puzzle> puzzle)
{
	//Phase IV: A* Graph Search.
	shared_ptr<Puzzle> solution = shared_ptr<Puzzle>();
	priority_queue<shared_ptr<Puzzle>, vector<shared_ptr<Puzzle> >,Compare> fringe;
	set<string> closedlist;

	fringe.push(puzzle);
	while (!fringe.empty())
	{
		shared_ptr<Puzzle> current = fringe.top();
		fringe.pop();
		if (current->isSolved())
		{
			solution = current;
			break;
		}
		else
		{
			if (!closedlist.count(current->uniqueID())) //if not in closedlist
			{
				closedlist.insert(current->uniqueID());
				vector<shared_ptr<Puzzle> > successors = current->Successors();
				vector<shared_ptr<Puzzle> >::iterator it;
				for (it = successors.begin(); it != successors.end(); it++)
				{
					if (!closedlist.count((*it)->uniqueID()))
					{
						if ((*it)->isSolved())
							return (*it);
						else
							fringe.push((*it)); //add successor if not in closedlist
					}
				}
			}
		}
	}
	return solution;
}


int Search::heuristic(shared_ptr<Puzzle> puzzle)
{
	//h(n); Manhattan distance heuristic.
	int distance = 0;
	int counter = 1;
	for (int i = 1; i < puzzle->N+1; i++)
	{
		for (int j = 1; j < puzzle->N+1; j++)
		{
			//For each block in order:
			//Look at its coordinates.
			//What's the difference along each axis to the correct place?
			int diffx = abs(i - puzzle->index[counter]->posX);
			int diffy = abs(j - puzzle->index[counter]->posY);
			int manhattan = diffx + diffy;
			distance += manhattan;
			counter++;
		}
	}
	return distance;
}

int Search::pathCost(shared_ptr<Puzzle> puzzle)
{
	//g(n); Path cost function. Distance from initial to current state.
	//We count the number of moves made so far.
	return puzzle->moveQueue.size();
}

int Search::F(shared_ptr<Puzzle> puzzle)
{
	//f(n) Total cost; used by A*.
	//f(n) = g(n) + h(n)
	return pathCost(puzzle) + heuristic(puzzle);
}

shared_ptr<Puzzle> Search::IDAStar(shared_ptr<Puzzle> puzzle)
{
	//Phase IV Bonus: Iterative Deepening A* Graph Search.
	shared_ptr<Puzzle> solution = shared_ptr<Puzzle>();
	priority_queue<shared_ptr<Puzzle>, vector<shared_ptr<Puzzle> >,Compare> fringe;
	set<string> closedlist;

	int Flimit = 0;
	while (!solution)
	{
		Flimit++;
		//cout << "Current F limit: " <<Flimit <<endl;
		closedlist.clear();
		while (!fringe.empty())
			fringe.pop(); //empty the fringe
		fringe.push(puzzle);
		while (!fringe.empty())
		{
			shared_ptr<Puzzle> current = fringe.top();
			fringe.pop();
			if (current->isSolved())
			{
				solution = current;
				break;
			}
			else
			{
				if (!closedlist.count(current->uniqueID())) //if not in closedlist
				{
					closedlist.insert(current->uniqueID());
					if (F(current) < Flimit) //if within F limit
					{
						vector<shared_ptr<Puzzle> > successors = current->Successors();
						vector<shared_ptr<Puzzle> >::iterator it;
						for (it = successors.begin(); it != successors.end(); it++)
						{
							if (!closedlist.count((*it)->uniqueID()))
							{
								if ((*it)->isSolved())
									return (*it);
								else
									fringe.push((*it)); //add successor if not in closedlist
							}
						}
					}
				}
			}
		}
	}
	return solution;
}