/* Copyright (C) 2002 J. M. Spivey */

import java.awt.Color;
import java.util.*;

/** Object able to carry out a shortest path search using Dijkstra's algorithm.
 *  
 *  Each search is carried out by a freshly-created object. */
class PathFinder extends Thread {
    private Map map;
        // The map to search in
    private Map.Town from, to;
        // Starting and finishing towns
    private boolean heur;
        // Whether to adjust distances heuristically to speed the search
    private boolean work;
        // Whether to show working
    private boolean cont = true;
    
    public SearchState state = new SearchState();
    
    public static final float INF = 1.0e6f;
        // That's near enough to infinity
    
    public PathFinder(Map map, Map.Town from, Map.Town to, 
		      boolean heur, boolean work) {
        this.map = map;
        this.from = from;
        this.to = to;
        this.heur = heur;
        this.work = work;
    }
    
    /** Change the colour of a town and notify the viewer */
    private void paint(ActiveTown t, Color color) {
        t.town.setColor(color);
        state.colourChange();
    }
    
    /** Change the colour of a road and notify the viewer */
    private void paint(Map.Road r, Color color) {
        r.setColor(color);
        state.colourChange();
    }
    
    public SearchState getStateObject() { return state; }
    
    /** Carry out the search */ 
    public void run() {
        for (Enumeration e = map.getTowns(); e.hasMoreElements(); ) {
            Map.Town t = (Map.Town) e.nextElement();
            t.setData(null);
        }           
        
        ActiveTown source = getActive(from);
        source.dist = 0.0f;
        source.known = true;
        source.prev = source;
        source.backlink = null;
        visitNeighbours(source);
        ActiveTown goal = getActive(to);
        
        // Loop until the shortest path to the finishing town is known
        while (!goal.known) {
            if (! cont) return;
            
            // Find the next town to visit
            ActiveTown t = findMin();
            if (t == null) {
                // Oops! No towns left to visit: that means there's no
                // feasible path
                state.setDistance(INF);
                state.setDone();
                state.notifyObservers();
                return; 
            }
            
            // Mark the town as known
            t.known = true;
            if (work) {
                paint(t.backlink, Color.blue);
                if (t.town != to) paint(t, Color.white);
            }
            
            // Update links for its neighbours
            visitNeighbours(t);
            
            if (work) {
                state.setDistance(t.dist);
                state.notifyObservers();
            }
        }

        // Paint the shortest path
        for (ActiveTown t = goal; t != source; t = t.prev)
            paint(t.backlink, Color.yellow);
        
        // Return the distance
        state.setDistance(heur ? goal.dist + from.distance(to) : goal.dist);
        state.setDone();
        state.notifyObservers();
    }
    
    /** Update links for the neighbours of a town */
    private void visitNeighbours(ActiveTown t) {
        // Loop over all neighbours
        for (Enumeration z = t.town.getArcs(); z.hasMoreElements(); ) {
            Map.Arc a = (Map.Arc) z.nextElement();
            ActiveTown u = getActive(a.getDest());
            
            // Compute distance of the path that reaches u via t
            float d = t.dist + a.getRoad().length;
            
            if (heur) {
                // Heuristic: reduce d by the distance made good
                // towards the destination
                d -= t.town.distance(to) - u.town.distance(to);
            }
            
            if (u.prev == null) {
                // First time we have seen u
                u.dist = d;
                u.backlink = a.getRoad();
                u.prev = t;
                if (work) {
                    if (u.town != to) paint(u, Color.gray);
                    paint(a.getRoad(), Color.green);
                }
            }
            else if (d < u.dist) {
                // The route via t improves on a previous path
                if (work) {
                    paint(u.backlink, Color.magenta);
                    paint(a.getRoad(), Color.green);
                }
                u.dist = d;
                u.backlink = a.getRoad();
                u.prev = t;
            }
        }
    }
        
    /** Find the next town to visit */
    private ActiveTown findMin() {
        // The desired town is the nearest among 
        // those not yet marked as known
        
        /* It would be good to use a priority queue here,
         * but for small maps, linear search is enough */
        ActiveTown min = null;
        for (Enumeration e = map.getTowns(); e.hasMoreElements();) {
            Map.Town t = (Map.Town) e.nextElement();
            ActiveTown a = (ActiveTown) t.getData();
            if (a != null && !a.known && a.backlink != null
                    && (min == null || a.dist < min.dist))
                min = a;
        }
        return min;
    }
    
    private ActiveTown getActive(Map.Town t) {
        ActiveTown a = (ActiveTown) t.getData();
        if (a == null) {
            a = new ActiveTown(t);
            t.setData(a);
        }
        return a;
    }
    
    public void kill() {
        cont = false;
        interrupt();
    }

    /** Data about a town during a search. */
    class ActiveTown {
	// These data members are public, because ActiveTowns are used only
	// in PathFinder, and accessor methods would be too clumsy.
    
	public Map.Town town;
        // The town this data is about
	public float dist = PathFinder.INF;
        // Best known distance to this town
	public boolean known = false;
        // Whether shortest path to this town is known
	public Map.Road backlink = null;
        // Final road on current best path
	public ActiveTown prev = null;
        // Previous town on current best path
    
	public ActiveTown(Map.Town town) {
	    this.town = town;
	}
    }
}