import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

public class ucs1 {

	public static void main(String[] args) {

		//Node assignments
		Node n1 = new Node("Manchester");
		Node n2 = new Node("Birmingham");
		Node n3 = new Node("Bristol");
		Node n4 = new Node("London");

		Node n5 = new Node("Luebeck");
		Node n6 = new Node("Hamburg");
		Node n7 = new Node("Bremen");
		Node n8 = new Node("Berlin");
		Node n9 = new Node("Hannover");
		Node n10 = new Node("Magdeburg");
		Node n11 = new Node("Leipzig");
		Node n12 = new Node("Dresden");
		Node n13 = new Node("Dortmund");
		Node n14 = new Node("Kassel");
		Node n15 = new Node("Nuremberg");
		Node n16 = new Node("Frankfurt");
		Node n17 = new Node("Duesseldorf");
		Node n18 = new Node("Saarburcken");
		Node n19 = new Node("Karlsruhe");
		Node n20 = new Node("Stuttgart");
		Node n21 = new Node("Munich");

		//Initialize Edges for Map 1
		n1.adjacencies = new Edge[]
				{
					new Edge(n2,84)
				};
		n2.adjacencies = new Edge[]
				{
					new Edge(n1, 84),
					new Edge(n3, 85),
					new Edge(n4, 117)
				};
		n3.adjacencies = new Edge[]
				{
					new Edge(n2, 85)
				};
		n4.adjacencies = new Edge[]
				{
					new Edge(n2, 117)
				};

		//Initialize Edges for Map 2
		n5.adjacencies = new Edge[]
				{
					new Edge(n6, 63)
				};
		n6.adjacencies = new Edge[]
				{
					new Edge(n5, 63),
					new Edge(n7, 116),
					new Edge(n8, 291),
					new Edge(n9, 153)
				};
		n7.adjacencies = new Edge[]
				{
					new Edge(n6, 116),
					new Edge(n9, 132),
					new Edge(n13, 234)
				};
		n8.adjacencies = new Edge[]
				{
					new Edge(n6, 291),
					new Edge(n10, 166),
					new Edge(n12, 204)
				};
		n9.adjacencies = new Edge[]
				{
					new Edge(n6, 153),
					new Edge(n7, 132),
					new Edge(n10, 148),
					new Edge(n14, 165)
				};
		n10.adjacencies = new Edge[]
				{
					new Edge(n9, 148),
					new Edge(n8, 166),
					new Edge(n11, 125)
				};
		n11.adjacencies = new Edge[]
				{
					new Edge(n10, 125),
					new Edge(n12, 119),
					new Edge(n15, 263)
				};
		n12.adjacencies = new Edge[]
				{
					new Edge(n11, 119),
					new Edge(n8, 204)
				};
		n13.adjacencies = new Edge[]
				{
					new Edge(n7, 234),
					new Edge(n16, 221),
					new Edge(n17, 69),
					new Edge(n18, 350)
				};
		n14.adjacencies = new Edge[]
				{
					new Edge(n9, 165),
					new Edge(n16, 185)
				};
		n15.adjacencies = new Edge[]
				{
					new Edge(n11, 263),
					new Edge(n16, 222),
					new Edge(n20, 207),
					new Edge(n21, 171)
				};
		n16.adjacencies = new Edge[]
				{
					new Edge(n13, 221),
					new Edge(n14, 185),
					new Edge(n15, 222),
					new Edge(n20, 200),
					new Edge(n18, 177)
				};
		n17.adjacencies = new Edge[]
				{
					new Edge(n13, 69)
				};
		n18.adjacencies = new Edge[]
				{
					new Edge(n13, 350),
					new Edge(n16, 177),
					new Edge(n19, 143)
				};
		n19.adjacencies = new Edge[]
				{
					new Edge(n18, 143),
					new Edge(n20, 71)
				};
		n20.adjacencies = new Edge[]
				{
					new Edge(n19, 71),
					new Edge(n16, 200),
					new Edge(n15, 207),
					new Edge(n21, 215)
				};
		n21.adjacencies = new Edge[]
				{
					new Edge(n15, 171),
					new Edge(n20, 215)
				};

		UCS(n6,n17);

		List<Node> path = printPath(n17);

		System.out.println("Path: " + path);


	}

	//Search Algorithm
	public static void UCS(Node source, Node goal)
	{
		source.pathCost = 0;

		PriorityQueue<Node> queue = new PriorityQueue<Node>(20,
				new Comparator<Node>()
					{
						public int compare(Node i, Node j)
						{
							if(i.pathCost > j.pathCost) {
								return 1;
							}

							else if(i.pathCost < j.pathCost)
							{
								return -1;
							}

							else
							{
								return 0;
							}
						}
					}
		);

		queue.add(source);
		Set<Node> explored = new HashSet<Node>();
		boolean found = false;

		do
		{
			Node current = queue.poll();
			explored.add(current);

			if(current.value.equals(goal.value))
			{
				found = true;
			}

			for(Edge e: current.adjacencies)
			{
				Node child = e.target;
				double cost = e.cost;
				child.pathCost = current.pathCost + cost;

				if(!explored.contains(child) && !queue.contains(child))
				{
					child.parent = current;
					queue.add(child);

					System.out.println(child);
					System.out.println(queue);
					System.out.println();
				}
				else if(queue.contains(child) && (child.pathCost>current.pathCost))
				{
					child.parent = current;

					queue.remove(child);
					queue.add(child);
				}
			}

		}while(!queue.isEmpty());
	}

	public static List<Node> printPath(Node target)
	{
		List<Node> path = new ArrayList<Node>();

		for(Node node = target; node!=null; node = node.parent)
		{
			path.add(node);
		}

		Collections.reverse(path);

		return path;
	}

}

class Node{

	public final String value;
	public double pathCost;
	public Edge[] adjacencies;
	public Node parent;

	public Node(String val)
	{
		value = val;
	}

	public String toString()
	{
		return value;
	}

}

class Edge{

	public final double cost;
	public final Node target;

	public Edge(Node targetNode, double costVal)
	{
		cost = costVal;
		target = targetNode;
	}
}