import java.util.*;

class AStar
{
	public AState search(AState start)
	{
		PriorityQueue<Entry> queue = new PriorityQueue<Entry>();
		TreeSet<AState> visited = new TreeSet<AState>();

		queue.add(new Entry(start));
		while(!queue.isEmpty())
		{
			Entry e = queue.poll();
			AState s = e.state;

			if (!visited.contains(s))
			{
				visited.add(s);

				if (s.isGoal()) return s;

				LinkedList<AState> next=
					new LinkedList<AState>();

				s.getNext(next);

				for(AState a : next)
				{
					queue.add(new Entry(a));
				}

			}

		}


		return null;
	}



	class Entry implements Comparable<Entry>
	{
		double cost;
		AState state;

		Entry(AState s)
		{
			cost = s.getCost() + s.getHeur();
			state = s;
		}

		public int compareTo(Entry e)
		{
			if (cost < e.cost) return -1;
			if (cost > e.cost) return 1;
			return 0;
			
		}


	}


}

abstract class AState implements Comparable<AState>
{
	/* the cost to get to this state */
	abstract double getCost();

	/* override iff you want to use a heuristic */
	double getHeur()
	{
		return 0.0;
	}

	abstract boolean isGoal();

	/* add potential next states to this list */
	abstract void getNext(LinkedList<AState> q);
	
	/* compare for visited list  */
	abstract public int compareTo(AState o);

}