/* ShortestPathDijkstraAlgorithm - Decompiled by JODE
 * Visit http://jode.sourceforge.net/
 */
package salvo.jesus.graph.algorithm;
import java.util.Iterator;
import java.util.Vector;

import salvo.jesus.graph.Vertex;
import salvo.jesus.graph.WeightedEdge;
import salvo.jesus.graph.WeightedGraph;
import salvo.jesus.graph.WeightedGraphImpl;
import salvo.jesus.util.Heap;
import salvo.jesus.util.HeapNode;
import salvo.jesus.util.HeapNodeComparator;

public class ShortestPathDijkstraAlgorithm extends ShortestPathAlgorithm
{
    private Vector visited = new Vector();
    private Heap fringe;
    private WeightedGraph shortestpathtree;
    private HeapNodeComparator comparator;
    
    public ShortestPathDijkstraAlgorithm
	(WeightedGraph weightedgraph, HeapNodeComparator heapnodecomparator) {
	super(weightedgraph);
	comparator = heapnodecomparator;
	fringe = new Heap(new HeapNodeComparator(1));
    }
    
    public WeightedGraph shortestPath(Vertex vertex) {
	shortestpathtree = new WeightedGraphImpl();
	fringe.insert(new HeapNode(new FringeObject(vertex, null), 0.0));
	while (!fringe.isEmpty())
	    moveToVisited();
	visited.clear();
	fringe.clear();
	return shortestpathtree;
    }
    
    private void moveToVisited() {
	HeapNode heapnode = fringe.remove();
	FringeObject fringeobject = (FringeObject) heapnode.getObject();
	Vertex vertex = fringeobject.vertex;
	visited.add(vertex);
	if (fringeobject.edge != null)
	    shortestpathtree.addEdge(fringeobject.edge);
	moveAdjacentVerticesToFringe(heapnode);
    }
    
    private void moveAdjacentVerticesToFringe(HeapNode heapnode) {
	Vertex vertex = ((FringeObject) heapnode.getObject()).vertex;
	Vector vector = wgraph.getEdges(vertex);
	double d = heapnode.getPriority();
	Iterator iterator = vector.iterator();
	HeapNodeObjectComparator heapnodeobjectcomparator
	    = new HeapNodeObjectComparator();
	while (iterator.hasNext()) {
	    WeightedEdge weightededge = (WeightedEdge) iterator.next();
	    Vertex vertex_0_ = weightededge.getOppositeVertex(vertex);
	    if (!visited.contains(vertex_0_)) {
		HeapNode heapnode_1_
		    = fringe.contains(vertex_0_, heapnodeobjectcomparator);
		if (heapnode_1_ == null) {
		    double d_2_ = d + weightededge.getWeight();
		    heapnode_1_ = new HeapNode(new FringeObject(vertex_0_,
								weightededge),
					       d_2_);
		    fringe.insert(heapnode_1_);
		} else {
		    double d_3_ = d + weightededge.getWeight();
		    if (comparator.compare(new HeapNode(vertex_0_, d_3_),
					   heapnode_1_)
			< 0) {
			fringe.setPriority(heapnode_1_, d_3_);
			FringeObject fringeobject
			    = (FringeObject) heapnode_1_.getObject();
			fringeobject.edge = weightededge;
		    }
		}
	    }
	}
    }
}