package jimDij;

import java.util.*;

/*****
 * The Graph object stores 
 *    an array of Nodes, and
 *    the starting Node for the search.<p>
 *
 * Besides the methods to get and set its variables, 
 * it can print the whole graph to the screen,
 * as well as return the smallest white node.<p>
 *
 * (The current implementation does not do this in a particularly
 *  clever way.)
 * 
 * @author Jim Mahoney (mahoney@marlboro.edu)
 * @version 0.1 Nov 25 2002
 ***/

public class Graph {

    private ArrayList nodes;
    private Node startNode;

    Graph(){
        nodes = new ArrayList(100);
    }
    Graph(int initNodeSize){
        nodes = new ArrayList(initNodeSize);
    }

    public Node getStartNode(){
        return startNode;
    }
    public void setStartNode(Node n){
        startNode = n;
        n.setPathDistance(0);
    }

    public void displayAllPaths(){
        Iterator i = nodes.iterator();
        while (i.hasNext()){
            displayShortestPath((Node)i.next());
        }
    }

    // Tell the user what the path from startNode to a given one is.
    public void displayShortestPath(Node n){
        System.out.println(" Distance to '" + n.getName() + "' = " + 
                           n.getPathDistance());
        System.out.print(" Path: " + n.getName() );
        Node p = n.getParent();
        int count=0;
        while ( p != null && count<20){
            count++;
            System.out.print(" <- " + p.getName() );
            p = p.getParent();
        }
        System.out.println("");
        System.out.println("");
    }

    // This is a linear search through the list for the smallest.
    // The program could be made faster by using a priority que
    // or similar structure which always has the smallest white node
    // accessible.  The Node.setColor and Node.setDistance routines
    // would then have to update the appropriate structure.
    public Node getSmallestWhiteNode(){
        Iterator i = nodes.iterator();
        Node smallest = (Node)i.next();
        while (smallest.isBlack() && i.hasNext()){
            smallest = (Node)i.next();
        }
        if (smallest.isBlack()){
            return null;
        }
        while (i.hasNext()){
            Node n = (Node)i.next();
            if (n.isBlack()){
                continue;
            }
            if (n.getPathDistance() < smallest.getPathDistance()){
                smallest = n;
            }
        }
        return smallest;
    }

    // Print out a summary of the graph,
    // including each Node and each Edge starting at that node,
    public void displayAsText(){
        System.out.println(" Graph " + this);
        for (Iterator i = nodes.iterator(); i.hasNext(); ){
            Node n=(Node)i.next();
            n.displayAsText();
        }
    }

    public void addNode(Node n){
        nodes.add(n);
    }
    public Node getNode(int n){
        return (Node)nodes.get(n);
    }
    public Node getNode(String s){
        for (Iterator i = nodes.iterator(); i.hasNext();){
            Node n=(Node)i.next();
            if (n.getName().equals(s)){
                return n;
            }
        }
        return null;
    }
}