package fr.inria.opengve.bridge.algorithms.common.shortestPath;

 import java.awt.Color;

 import java.util.HashSet;

 import java.util.Iterator;

 import java.util.NoSuchElementException;

 import fr.inria.opengve.bridge.abstractClasses.AbstractScalar;

 import fr.inria.opengve.bridge.interfaces.Graph;

 import fr.inria.opengve.bridge.interfaces.Link;

 import fr.inria.opengve.bridge.interfaces.Map;

 import fr.inria.opengve.tools.dataStructures.FibonacciHeap;

 /**

  * Provides a advanced algorithm to find all shortest paths from a vertex. You

  * must note that this algorithm doesn't work with negative distance you must

  * use {@link fr.inria.opengve.bridge.algorithms.common.shortestPath.BellmanFord}.

  * <p>

  * After constructing the dijkstra object, some steps are necessary to obtains

  * shortest paths or distances. </br>

  * <nl>

  * <li> Initialize Algorithm :

  * <ul>

  * <li> Set the {@link fr.inria.opengve.bridge.interfaces.Map} used to load edges distance :

  * {@link #setDistanceMap(Map)}

  * <li> Set the name of the distance value : {@link #setDistanceName(String)}

  * <li> Set the context of distance value : {@link #setDistanceContext(Object)}

  * <li> Set the {@link fr.inria.opengve.bridge.abstractClasses.AbstractScalar} corresponding to

  * infinity : {@link #setInfiniteDistance(AbstractScalar)}

  * </nl>

  * <p>

  * After initialisation call {@link #valuateFromSource(Object)} for shortest

  * path computation.

  * <p>

  * You can get result with two methods :

  * <nl>

  * <li> Get a shortest path to a given vertex :

  * {@link #getShortestPathTo(Object)}

  * <li> Get the distance to a given vertex : {@link #getDistanceTo(Object)}

  * </nl>

  * </p>

  * If you use the {@link #DijkstraAdvanced(Graph, boolean, Object)} constructor

  * the algorithm stop when the shortest path to the given vertice is found.

  * 

  * @param V

  *         the type of vertices.

  * @param E

  *         the type of edges.

  * @author fabrice.peix@sophia.inria.fr

  */

 public abstract class DijkstraAdvanced<V, E extends Link<V>, G extends Graph<V, E>>

     extends ShortestPathWithSingleOrigin<V, E, G>

 {

   /**

    * In optimized mode the vertex for which shortest path is computed.

    */

   private final V destination;

   /**

    * Classic Dijkstra constructor.

    * 

    * @param g

    *         the graph used by Dijkstra algorithm

    */

   public DijkstraAdvanced(G g) {

     this(g, false);

   }

   /**

    * This constructor permit to specify if algorithm must run in stepMode.

    * 

    * @param g

    *         the graph used by Dijkstra algorithm

    * @param stepMode

    *         The mode of the algorithms.

    */

   public DijkstraAdvanced(G g, boolean stepMode) {

     this(g, stepMode, null);

   }

   /**

    * This constructor is used to do optimized computation when you want to

    * compute shortest path between two vertices.

    * 

    * @param g

    *         The graph on which the algorithm is applied.

    * @param stepMode

    *         The mode of the algorithm.

    * @param destination

    *         The destination.

    */

   protected DijkstraAdvanced(G g, boolean stepMode, V destination) {

     super(g, stepMode);

     this.destination = destination;

   }

   /**

    * This method must not be call, use instead

    * {@link ShortestPathWithSingleOrigin#valuateFromSource(Object)}.

    */

   @Override

   public void run() {

     if (infiniteDistance == null)

       throw new RuntimeException("You must specify infiniteDistance with setInfiniteDistance method");

     // For Demo

     if (getDemoMode()) {

       pause();

     }

     AbstractScalar zero = infiniteDistance.zero();

     FibonacciHeap<V, AbstractScalar> nonComputedVertices = new FibonacciHeap<V, AbstractScalar>();

     HashSet<V> alreadyComputeVertices = new HashSet<V>();

     // Initialisation

     Initialize(zero);

     // Modify the source...

     nonComputedVertices.insert(start_, zero.clone());

     pause();

     while ( !nonComputedVertices.isEmpty()) {

       V minNode = null;

       try {

         minNode = nonComputedVertices.findMin();

         nonComputedVertices.deleteMin();

         if (getDemoMode())

           result.putString(minNode, "Color", "" + Color.green.getRGB());

       } catch (NoSuchElementException u) {

         System.err.println("findMin : fibonacci heap is empty");

       }

       pause();

       Iterator<? extends E> itMAJ = g_.outEdges(minNode).iterator();

       while (itMAJ.hasNext()) {

         E currentEdge2 = itMAJ.next();

         V currentNode2 = currentEdge2.getOpposite(minNode);

         // Don't test fixed node.

         if (alreadyComputeVertices.contains(currentNode2))

           continue;

         if (getDemoMode()) {

           // Pause in demo mode

           result.putString(currentEdge2, "Color", "" + Color.red.getRGB());

           pause();

         }

         // Update vertices connected to minNode

         if (updateVerticesDistance(minNode, currentNode2, currentEdge2)) {

           try {

             nonComputedVertices.FibHeapDecreaseKey(currentNode2, result

                 .getValue(currentNode2, VERTEX_DISTANCE, g_));

           } catch (IllegalArgumentException u) {

             System.err

                 .println("FibHeapDecreaseKey : New value greater than older");

           }

         }

       }

       // Add the node to fixedNode.

       alreadyComputeVertices.add(minNode);

       // When destination is set.

       if (destination != null && minNode == destination) {

         this.ends();

         return;

       }

       // For demo minNode is now red

       if (getDemoMode())

         result.putString(minNode, "Color", "" + Color.red.getRGB());

     }

     this.ends();

   }

 }