package jimDij;

import java.util.*;

/***
 * Dijekstra finds the minimum paths through a graph.
 * This is a demo for both the intro programming and the
 * algorithms classes.
 *
 * @author  Jim Mahoney (mahoney@marlboro.edu)
 * @version 0.1 Nov 25 2002
 ***/

public class Dijkstra {

    private static Graph theGraph;
    private static final String dataFile   = "g5.obj";
    private static final String startPlace = "Tokushima";

    /***
     * What program would be complete without a main() method?
     ***/
    public static void main(String[] args){
        
        println("");
        print(" Reading data from '" + dataFile + "' ... ");
        theGraph = ReadData.initData(dataFile, startPlace);
        println(" done.");

        println("");
        print(" Building search tree ... ");
        doDijekstraSearch(true);                // true => verbose
        println(" done.");

        println("");
        println(" Here's the final data structure : ");
        theGraph.displayAsText();

        println("");
        println(" And here are the paths: ");
        theGraph.displayAllPaths();
    }

    // ------- The core of the algorithm -----------------------

    /*****
     * Finds the shortest paths from the starting 
     * node to every other node.  The answer is stored within then
     * Nodes, in the parent and pathDistance instance variables.
     *
     * The data structure should be set up before this is called.
     *
     * @param verbose    "true" means  print out the details of the search
     *****/
    public static void doDijekstraSearch(boolean verbose){
        int count=0;
        final int ITERATION_LIMIT = 1000;
        if (verbose){ println(""); }

        // When the algorithm starts, all the nodes are colored white
        // (which means we haven't looked at any of them), and 
        // all the total distance guess (pathDistance) in the nodes
        // are set to very large numbers - except
        // for the starting node, which is set to pathDistance zero.

        // Loop over all white nodes.
        while (true){

            // Count is only for safety, to catch infinite loops.
            count++;
            if (verbose) { println("-- loop "+count+" --"); }
            if (count>ITERATION_LIMIT){
                println(" +++ OOPS - HIT ITERATION LIMIT +++");
                return;
            }

            // (1) Get the next Node that we haven't done (a white one).
            Node currentNode = theGraph.getSmallestWhiteNode();
            if (currentNode==null){
                return;                 // We're finished if we can't
            }                           // find a white one.

            if (verbose) {
                println("");
                println("New white: ");
                currentNode.displayAsText();
            }
            
            // (2) Mark the current node as being finished (i.e. black).
            currentNode.setColor(Node.BLACK);

            // (3) Loop over all the edges that lead out from this Node.
            Iterator e = currentNode.edgeIterator();
            while (e.hasNext()){
                Edge edge = (Edge)e.next();
                Node neighbor = edge.getToNode();

                // Examine only neighbors which are not black.
                if (neighbor.isBlack()){
                    continue;
                }
                if (verbose){
                    print(" Looking at ");
                    neighbor.displayAsText();
                }

                // (4) Find the total distance to the neighbors
                //     using a path through the current node.
                int throughHere = currentNode.getPathDistance() 
                    + edge.getDistance();
                if (verbose) {println(" throughHere = "+throughHere);}

                //     If that's shorter than our best guess
                //     so far to that node, then
                //     remember the current node as its parent
                //     and the distance through this node as our
                //     best guess so far.
                if (neighbor.getPathDistance() > throughHere) {
                    neighbor.setPathDistance(throughHere);
                    neighbor.setParent(currentNode);
                }

                if (verbose){
                    print(" Leaving ");
                    neighbor.displayAsText();
                }
            }
            if (verbose){ println(""); }
        }
    }

    // -----  a few utility routines ----------------------------

    /***
     * Shorthand for System.out.println(String s).
     * Prints out its argument followed by a new line.
     * @param String s   what to print
     **/
    public static void println(String s){
        System.out.println(s);
    }

    /***
     * Shorthand for System.out.print(String s)
     * @param String s what to print
     **/
    public static void print(String s){
        System.out.print(s);
    }


}