class Dijkstra {

	public static ArrayList<MapNode> bidirectional(MapGraph graph, int startnode, int endnode) throws Exception{
		
		if (graph == null) throw new EmptyInputException("Leerer Graph uebergeben");
		//Hier breche ich immer wieder ab, was echt bloed ist und mich nervt das langsam echt!
		if (graph.getNode(startnode) == null || graph.getNode(endnode) == null || startnode == endnode) return new ArrayList<MapNode>();
		
		HashMap<Integer,Vertex> nodes1 = new HashMap<Integer,Vertex>(); // In einzelnen Listen wird gespeichert welcher Knoten.
		HashMap<Integer,Vertex> nodes2 = new HashMap<Integer,Vertex>(); //von welcher Richtung aus schon besucht worden ist.
		
		PrQueue forward = new PrQueue(); //Priority Queue, die alle erreichbaren Knoten enthaelt
		PrQueue backward = new PrQueue(); //Priority Queue, die alle erreichbaren Knoten enthaelt
		
		Vertex start = new Vertex(graph.getNode(startnode),0,0); //Vertex ist die Hilfsklasse, in der zusaetzliche Infos ueber Knoten gespeichert werden.
		Vertex end = new Vertex(graph.getNode(endnode),0,0); //Vertex ist die Hilfsklasse, in der zusaetzliche Infos ueber Knoten gespeichert werden.
		
		nodes1.put(startnode,start); 
		nodes2.put(endnode,end);
		
		forward.insert(start);
		backward.insert(end);
        
		while (forward.getSize() != 0 && backward.getSize() != 0){ //Wenn beide Queues leer, Abbruch
			boolean abort;
			abort = handleQueues(nodes1,forward,graph,nodes2,backward,true); //Berechne vorwaerts
			if(abort) break;
			abort = handleQueues(nodes1,forward,graph,nodes2,backward,false); //Berechne rueckwaerts
			if(abort) break;
		}
		
		long distance = -1;
		Vertex meet = null;
		
		
		//Wir suchen den Punkt ueber den der kuerzeste Weg verlueuft
		for (Vertex currentNode : nodes1.values()){
			
			//ueber pruefe ob Node in beiden Listen vorhanden ist
			
			int ID = currentNode.node.getUID();
			if (nodes2.containsKey(ID) == false){
				continue;  //node noch nicht von anderer Seite ueberprueft => liegt nicht auf kuerzestem Weg
			}
			
			if (distance == -1) {
				distance = nodes1.get(ID).getDist() + nodes2.get(ID).getDist();
				meet = nodes1.get(ID);
				

			}else{
				long newDist = nodes1.get(ID).getDist() + nodes2.get(ID).getDist();
				if (distance > newDist){
					distance = nodes1.get(ID).getDist() + nodes2.get(ID).getDist();
					meet = nodes1.get(ID);
				}
			}
		}
		
		
		if (meet == null) return new ArrayList<MapNode>();
		
		ArrayList<MapNode> route = new ArrayList<MapNode>();

		route.add(graph.getNode(meet.node.getUID() ) );
		Vertex pos = meet;
		
		while (pos.getPredecessor() != 0){ //Ermittle alle Knoten, die vor meet besucht wurden
			Vertex parent = nodes1.get(pos.getPredecessor());
			route.add(0, graph.getNode(parent.node.getUID()));
			pos = parent;
		}
		
		pos = nodes2.get( meet.node.getUID());
		
		while (pos.getPredecessor() != 0){ //Ermittle alle Knoten die nach meet besucht wurden 
			Vertex parent = nodes2.get(pos.getPredecessor());
			route.add(graph.getNode(parent.node.getUID()));
			pos = parent;
		}		
		
		if(debug){ 
			logger.log("Dijkstra.biderectional","Vom Startknoten aus evaluiert: "+nodes1.values().size());
			logger.log("Dijkstra.biderectional","Vom Zielknoten aus evaluiert: "+nodes2.values().size());
			logger.log("Dijkstra.biderectional","Knoten auf der Route: "+route.size());
		}
		
		return route; //gib die Liste zurueck
	}

}