// SearchApplet.java //
 // This class is an abstract class for defining search // algorithm classes. // // Copyright Mark Watson, 1998. Open Source and Open Content. // 
 import java.awt.*; 
 import java.awt.event.*; 
 import java.util.Vector;
 abstract public class SearchApplet extends java.applet.Applet { 
     public void init() { 
         String width = getParameter("pwidth"); 
         if (width == null) { 
             xSizePixels = 80; } 
             else { 
                 xSizePixels = Integer.valueOf(width).intValue(); 
                } 
                String height = getParameter("pheight"); 
                if (height == null) {
                    ySizePixels = 80; 
                } 
                else { 
                    ySizePixels = Integer.valueOf(height).intValue(); 
                } 
                System.out.println("width=" + xSizePixels + ", height=" + ySizePixels); setLayout(null); 
                startChoice = new Choice(); 
                goalChoice = new Choice(); 
                for (int i=0; i<numNodes; i++) { 
                    startChoice.add(nodeNames[i]); 
                    goalChoice.add(nodeNames[i]); } 
                    startChoice.select(0); 
                    goalChoice.select(numNodes - 1); 
                    Label l1 = new Label("Starting node:"); 
                    Label l2 = new Label("Goal node:"); 
                    l1.setBounds(5, 10, 90, 24); 
                    startChoice.setBounds(100, 10, 50, 30); 
                    l2.setBounds(5, 50, 90, 24); 
                    goalChoice.setBounds(100, 50, 50, 30); 
                    timeDelayChoice = new Choice(); 
                    timeDelayChoice.add("No plot time delay"); 
                    timeDelayChoice.add("Plot time delay"); 
                    timeDelayChoice.setBounds(160, 10, 90, 24); 
                    timeDelayChoice.select(1); add(l1); 
                    add(l2); 
                    add(startChoice); 
                    add(goalChoice); 
                    add(timeDelayChoice); 
                    Button b = new Button("Run"); 
                    b.setBounds(160, 50, 90, 32); 
                    add(b); 
                    b.addMouseListener(new java.awt.event.MouseAdapter() 
                    { public void mouseClicked(MouseEvent me) { 
                        int i1 = startChoice.getSelectedIndex(); 
                        int i2 = goalChoice.getSelectedIndex(); 
                        startNodeIndex = i1; 
                        goalNodeIndex = i2; 
                        System.out.println("mouse clicked " + i1 + " " + i2); 
                        findPath(i1, i2); } } ); 
                        canvas = new Canvas(); 
                        //
                       // Panel pp = new Panel(); 
                        add(canvas); 
                        canvas.setBounds(5, 80, xSizePixels + 20, ySizePixels + 20); 
                        add(canvas); repaintPath(null, 0); 
                        setBackground(Color.white); 
                    } 
                    protected Choice startChoice, goalChoice, timeDelayChoice; 
                    private Canvas canvas; 
                    private int goalNodeIndex = -1, 
                    startNodeIndex = -1; 
                    public void repaintPath(int [] path, int num) { 
                        System.out.print("repaintPath("); 
                        boolean time_delay = timeDelayChoice.getSelectedIndex() == 1; 
                        for (int i=0; i<num; i++) { 
                            System.out.print(path[i]); if (i < (num - 1)) System.out.print(", "); 
                        } System.out.println(")"); 
                        Graphics g = canvas.getGraphics(); 
                        g.setColor(Color.black); 
                        float x_scale = (float)xSizePixels / (x_max - x_min); 
                        float y_scale = (float)ySizePixels / (y_max - y_min); 
                        // start by plotting nodes and links: 
                        for (int i=0; i<numLinks; i++) { 
                            int i1 = link_1[i]; 
                            int i2 = link_2[i]; 
                            int x1 = (int)(node_x[i1] * x_scale); 
                            int x2 = (int)(node_x[i2] * x_scale); 
                            int y1 = (int)(node_y[i1] * y_scale); 
                            int y2 = (int)(node_y[i2] * y_scale); 
                            g.drawLine(x1 + 10, y1 + 10, x2 + 10, y2 + 10); 
                            g.drawLine(x1 + 10, y1 + 11, x2 + 10, y2 + 11); } 
                            for (int i=0; i<numNodes; i++) { 
                                int x1 = (int)(node_x[i] * x_scale); 
                                int y1 = (int)(node_y[i] * y_scale); 
                                if (i == startNodeIndex) 
                                g.setColor(Color.green); 
                                else if (i == goalNodeIndex) 
                                g.setColor(Color.blue); 
                                else g.setColor(Color.black); 
                                paintNode(g, nodeNames[i], x1 + 10, y1 + 10); } 
                                if (path == null) 
                                return; 
                                // set line color to red: 
                                g.setColor(Color.red); 
                                for (int i=0; i<num - 1; i += 2) { 
                                    int x1 = (int)(node_x[path[i]] * x_scale); 
                                    int x2 = (int)(node_x[path[i+1]] * x_scale); 
                                    int y1 = (int)(node_y[path[i]] * y_scale); 
                                    int y2 = (int)(node_y[path[i+1]] * y_scale); 
                                    g.drawLine(x1 + 10, y1 + 10, x2 + 10, y2 + 10); 
                                    g.drawLine(x1 + 10, y1 + 11, x2 + 10, y2 + 11); } 
                                    if (time_delay) { 
                                        try { 
                                            Thread.sleep(1000); 
                                        } catch (Exception e) { } }
                                    } 
                                    public void repaintPath(int [] path) { 
                                        repaintPath(path, path.length); 
                                    } 
                                    protected void paintNode(Graphics g, String name, int x, int y) { 
                                        int len = name.length() * 10 + 6; 
                                        int x1 = x - (len / 2); 
                                        int x2 = x + (len / 2); 
                                        int y1 = y - 10; 
                                        int y2 = y + 10; 
                                        g.setColor(Color.cyan); 
                                        g.fill3DRect(x1, y1, len, 20, true); 
                                        g.setColor(Color.black); 
                                        g.drawString(name, x1 + 4, y2 - 6); 
                                    } 
                                    public void paint(Graphics g) { 
                                        super.paint(g); 
                                        repaintPath(null, 0); 
                                    } 
                                    public void addNode(String name, float x, float y) { 
                                        System.out.println("Adding node: " + name + ", " + x + ", " + y); 
                                        nodeNames[numNodes] = name; 
                                        node_x[numNodes] = x; 
                                        node_y[numNodes] = y; 
                                        numNodes++;
                                        if (x < x_min) 
                                        x_min = x; 
                                        if (x > x_max) 
                                        x_max = x; 
                                        if (y < y_min) 
                                        y_min = y; 
                                        if (y > y_max) 
                                        y_max = y; 
                                    } 
                                    public String getNodeName(int index) 
                                    { 
                                        try { 
                                            return nodeNames[index]; 
                                        } catch (Exception e) 
                                        { System.out.println("Error in getNodeName: " + e); 
                                        } return "no name"; 
                                        // error condition 
                                    } 
                                    public float getNodeX(int index) 
                                    { 
                                        try { 
                                            return node_x[index]; } 
                                            catch (Exception e) {
                                                System.out.println("Error in getNodePosition: " + e); } 
                                                return 0.0f; 
                                                // error condition 
                                            } 
                                            public float getNodeY(int index) { 
                                                try { 
                                                    return node_y[index]; } 
                                                    catch (Exception e) 
                                                    { 
                                                        System.out.println("Error in getNodePosition: " + e); 
                                                    } return 0.0f; 
                                                    // error condition 
                                                } 
                                                public float getPathLength(int index) { 
                                                    // currently unsued - for adding heuristics 
                                                    return lengths[index]; } 
                                                    public void addLink(int node1, int node2) { 
                                                        link_1[numLinks] = node1; 
                                                        link_2[numLinks] = node2; 
                                                        float dist_squared = (node_x[node1] - node_x[node2]) * (node_x[node1] - node_x[node2]) + (node_y[node1] - node_y[node2]) * (node_y[node1] - node_y[node2]); 
                                                        lengths[numLinks] = (float)Math.sqrt(dist_squared);
                                                        numLinks++; } 
                                                        public void addLink(String name1, String name2) { 
                                                            int index1 = -1, index2 = -1; 
                                                            for (int i=0; i<numNodes; i++) { 
                                                                if (name1.equals(nodeNames[i])) 
                                                                index1 = i; 
                                                                if (name2.equals(nodeNames[i])) 
                                                                index2 = i; 
                                                            } 
                                                            if (index1 != -1 && index2 != -1) 
                                                            addLink(index1, index2); 
                                                        } 
                                                        /** findPath - abstract method that is defined in subclasses */ 
                                                        abstract public int [] findPath(int node_1, int node_2); 
                                                        // return an array of node indices 
                                                        protected int getNodeIndex(String name) { 
                                                            for (int i=0; i<numNodes; i++) { 
                                                                if (name.equals(nodeNames[i])) 
                                                                return i; 
                                                            } 
                                                            return -1; 
                                                            // error condition 
                                                        }
                                                        final public static int MAX = 50; 
                                                        // max number of nodes and max number of links // for nodes: 
                                                        private String [] nodeNames = new String[MAX]; 
                                                        private float [] node_x = new float[MAX]; 
                                                        private float [] node_y = new float[MAX]; 
                                                        // for links between nodes: 
                                                        protected int [] link_1 = new int[MAX]; 
                                                        protected int [] link_2 = new int[MAX]; 
                                                        private float [] lengths = new float[MAX]; 
                                                        protected int numNodes = 0; 
                                                        protected int numLinks = 0; 
                                                        // For optional display of search progress: 
                                                        private int xSizePixels = 0, ySizePixels = 0; 
                                                        private float x_min = 0.0f, x_max = 0.1f; 
                                                        private float y_min = 0.0f, y_max = 0.1f; 
                                                    }