/**
 *
 * Dijkstra's algorithm demo applet.
 * this applet requires.
 *
 * - Node.java
 * - Path.java
 * - BoxFilter.java
 *
 * BoxFilter.java is used in the applet to get smoothing effect
 * in the drawn nodes, lines, and texts. 
 * It can be removed without affecting the algorithm.
 *
 * www.tech-algorithm.com
 *
 */
import java.applet.Applet;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Image;
import java.awt.Point;
import java.awt.Toolkit;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.image.MemoryImageSource;
import java.awt.image.PixelGrabber;
import java.util.Iterator;
import java.util.LinkedList;

public class DijkstraDemo extends Applet implements MouseListener {

    // node data representing node names, position, and connections
    final static String nodeData = "a,109,15;b,209,65;c,262,185;d,130,211;e,28,164;f,17,63;g,130,116;h,200,145" ;
    final static String nodePaths = "a,b,1.0;a,f,1.0;a,e,2.0;b,c,2.0;b,g,1.0;c,d,1.0;d,e,1.0;d,g,2.0;d,h,0.5;e,f,2.0;g,h,0.5" ;
    
    // radius of node and arrow head length
    final int radius = 10 ;
    final int arrow = 7 ;
    
    LinkedList nodes, openlist, closedlist ;
    Image buffer ;
    Graphics graphics ;
    Dimension dim ;
    FontMetrics fm ;
    Node start ;
    
    Color 
            openColor = new Color(0xffc0ff),
            closedColor = new Color(0xc0c0c0),
            unseenColor = Color.WHITE ;
    
    // filtering related
    int[] pixels ;
    PixelGrabber pg ;
    
    public void init() {
        
        nodes = new LinkedList() ;
        closedlist = new LinkedList() ;
        openlist = new LinkedList() ;
              
        // parse nodeData
        String[] nodelist = nodeData.split(";") ;
        for (int i=0;i<nodelist.length;i++) {
            String[] items = nodelist[i].split(",") ;
            Node node = new Node(items[0]) ;
            node.setPoint(new Point(
                    Integer.valueOf(items[1]),
                    Integer.valueOf(items[2]))) ;
            nodes.add(node) ;
        }
        // start search at this node
        start = getNodeByName("g") ;
        
        // parse nodePaths
        String[] pathlist = nodePaths.split(";") ;
        for (int i=0;i<pathlist.length;i++) {
            String[] items = pathlist[i].split(",") ;
            getNodeByName(items[0]).connectNode(
                    getNodeByName(items[1]),
                    Float.valueOf(items[2])) ;
        }        
        dim = getSize() ;        
        pixels = new int[dim.width*dim.height] ;        
        setBackground(Color.WHITE) ;
        buffer = createImage(dim.width, dim.height) ;
        pg = new PixelGrabber(buffer,0,0,dim.width,dim.height,pixels,0,dim.width) ;
        graphics = buffer.getGraphics() ;
        fm = graphics.getFontMetrics() ;                
        
        addMouseListener(this) ;
        
        repaint() ;
    }

    public void mouseClicked(MouseEvent e) {        
        if (openlist.isEmpty()) {
            // reset nodes            
            Node node ;
            for (Iterator e2=nodes.iterator();e2.hasNext();) {
                node = (Node)e2.next() ;
                // reset nodes
                node.setClosed(false) ;
                node.setParent(null) ;
            }                
            
            // re/start search
            start.setOpen(true) ;
            openlist.add(start) ;            
        } else {
            stepSearch(e) ;
        }        
        repaint() ;        
    }

    public void mouseEntered(MouseEvent e) {
    }

    public void mouseExited(MouseEvent e) {
    }

    public void mousePressed(MouseEvent e) {
    }

    public void mouseReleased(MouseEvent e) {
    }  
      
    /** do step search */
    public void stepSearch(MouseEvent me) {
        
        // get best node from openlist
        Node[] fnodes = new Node[openlist.size()] ;
        fnodes = (Node[])openlist.toArray(fnodes) ;
        Node best = fnodes[0] ;
        for (int i=0;i<fnodes.length;i++)
            if (fnodes[i].getOverallCost()<best.getOverallCost())
                best = fnodes[i] ;
        
        // find all neighbors of best
        Path path ;
        for (Iterator e=best.getNeighbors();e.hasNext();) {
            path = (Path)e.next() ;
            Node node = path.getEndNode(best) ;
            // dont bother if node is already visited
            if (node.isClosed()) continue ;
            if (node.isOpen()) {
                if ((best.getOverallCost()+path.getCost())<node.getOverallCost()) {
                    // path improvement
                    node.setOverallCost(best.getOverallCost()+path.getCost()) ;
                    node.setParent(best) ;
                }
            } else {
                // never seen before node, add it to openlist
                node.setOpen(true) ;                
                node.setOverallCost(best.getOverallCost()+path.getCost()) ;
                node.setParent(best) ;
                openlist.add(node) ;
            }
        }
        
        // put best to tree and remove from openlist
        best.setOpen(false) ;
        best.setClosed(true) ;
        closedlist.add(best) ;
        openlist.remove(best) ;
        
    }
    
    /** find a node by name */
    public Node getNodeByName(String name) {
        name = name.trim() ;
        Node node ;
        for (Iterator e=nodes.iterator();e.hasNext();) {
            node = (Node)e.next() ;
            if (node.getName().equals(name))
                return node ;
        }
        return null ;
    }
    
    final double degreerad = 0.01746f ; // pi/180
    final double degree45 = 45*degreerad ;
    
    /** draw pointed line from (x,y) <- (x2,y2) */
    public void drawPointedLine(int x,int y,int x2,int y2,Color color) {
                        
        double w = x2-x ;
        double h = y2-y ;        
        double theta = Math.atan2(h,w) ;        
        x += (int)((radius+1) * Math.cos(theta)) ;
        y += (int)((radius+1) * Math.sin(theta)) ;
        
        graphics.setColor(color) ;
        graphics.drawLine(x,y,x2,y2) ;
        
        double theta2 = degree45 - theta ;
        double theta3 = theta + degree45 ;
        
        int x3 = (int)(arrow * Math.cos(theta3)) ;
        int x4 = (int)(arrow * Math.cos(theta2)) ;
        int y3 = (int)(arrow * Math.sin(theta3)) ;
        int y4 = (int)(arrow * Math.sin(theta2)) ;
        
        graphics.drawLine(x,y,x+x3,y+y3) ;
        graphics.drawLine(x,y,x+x4,y-y4) ;
    }
    
    /** draw the path from a to b */
    public void drawPath(Node a, Node b, Path p) {
        
        Color color ;
        if (a.isClosed() && b.isClosed()) {
            color = Color.BLACK ;
        } else {
            color = Color.RED ;
        }
        
        // draw the line        
        if (b.equals(a.getParent())) {
            drawPointedLine(b.getPoint().x,b.getPoint().y,
                    a.getPoint().x,a.getPoint().y,color) ;
        } else if (a.equals(b.getParent())) {
            drawPointedLine(a.getPoint().x, a.getPoint().y,
                    b.getPoint().x, b.getPoint().y,color) ;
        } else {
            graphics.setColor(Color.LIGHT_GRAY) ;
            graphics.drawLine(a.getPoint().x,a.getPoint().y,
                b.getPoint().x,b.getPoint().y) ;
        }
        
        // draw label
        String label ;
        if (p.getCost()!=(int)p.getCost()) {
            label = String.valueOf(p.getCost()) ;
        } else {
            label = String.valueOf((int)p.getCost()) ;
        }
        int w = fm.stringWidth(label) ;
        int h = fm.getAscent() ;
        int x = (a.getPoint().x+b.getPoint().x-w)>>1 ;
        int y = (a.getPoint().y+b.getPoint().y-h)>>1 ;                
        graphics.setColor(Color.WHITE) ;
        graphics.fillRect(x-1,y-1,w+2,h+2) ;
        graphics.setColor(Color.BLACK) ;
        graphics.drawString(label,x,y+h-1) ;
        
    }
    
    
    /** do some filtering. why? just for fun :) */
    public Image filterImage(Image image) {
        
        // soft smoothing filter kernel
        float[] kernel = {
           0, 0.5f, 0,
           0.5f, 2, 0.5f,
           0, 0.5f, 0
        } ;                
        PixelGrabber pg = new PixelGrabber(
                image,0,0,dim.width,dim.height,pixels,0,dim.width) ;        
        try {
            if (!pg.grabPixels())
                return image ;
        } catch (Exception e) {            
            return image ;
        }                
        pixels = BoxFilter.BoxFiltering(pixels,dim.width,dim.height,kernel) ;        
        return Toolkit.getDefaultToolkit().createImage(
                new MemoryImageSource(dim.width,dim.height,pixels,0,dim.width)) ;
    }

    public void paint(Graphics g) {
        
        if (graphics==null || fm==null) return ;
        
        graphics.setColor(Color.WHITE) ;
        graphics.fillRect(0,0,dim.width,dim.height) ;
                
        // draw all nodes
        LinkedList paths = new LinkedList() ;
        Node a, b ;        
        int x, y, w, h ;
        for (Iterator e=nodes.iterator();e.hasNext();) {
            a = (Node)e.next() ;
            
            // draw path from a to its neighbors if not already
            for (Iterator e2=a.getNeighbors();e2.hasNext();) {
                Path path = (Path)e2.next() ;                
                if (paths.contains(path)) 
                    continue ;  // path has been drawn                
                drawPath(a,path.getEndNode(a),path) ;
                paths.add(path) ;
            }
            
            // draw the node
            Point p = a.getPoint() ;
            x = p.x-radius ;
            y = p.y-radius ;
            w = radius<<1 ;
            h = radius<<1 ;
            if (a.isClosed()) {
                graphics.setColor(closedColor) ;
            } else if (a.isOpen()) {
                graphics.setColor(openColor);
            } else {
                graphics.setColor(unseenColor) ;
            }
            graphics.fillOval(x,y,w,h) ;
            graphics.setColor(Color.BLACK ) ;
            graphics.drawOval(x,y,w,h) ;                    
            graphics.drawString(
                    a.getName(),
                    p.x-(fm.stringWidth(a.getName())>>1),
                    p.y+(fm.getAscent()>>1));
        }                
        g.drawImage(
                filterImage(buffer), 0, 0, null) ;
    }
    
    /** overide to avoid flicker */
    public void update(Graphics g) {
        paint(g) ;
    }
    
}