src/MySearcher.java

   1 import java.io.File;
   2 import java.io.IOException;
   3 import java.util.Iterator;
   4 import java.util.List;
   5 import java.util.Hashtable;
   6 import java.util.Enumeration;
   7 import org.jdom.*;
   8
   9 /**
  10  * Beskrivning av klassen.
  11  */
  12 public class MySearcher extends MapSearcher {
  13     private Graph map;
  14
  15    /**
  16     * Skapar en ny MySearcher-instans.
  17     */
  18    public MySearcher () {
  19       super ();
  20    }
  21
  22    /**
  23     * Specificerar kartan.
  24     *
  25     * @param map Den XML-fil som representerar kartan.
  26     *
  27     * @TODO fixa this.map.insertEdge() för alla noder.
  28     */
  29    public void setMap(File mapFile) {
  30       Document doc;
  31       List<Element> cityElements;
  32       try {
  33          doc = loadXmlMap(mapFile);
  34          //System.out.println(doc.getRootElement().toString());
  35          cityElements = doc.getRootElement().getChildren();
  36          map = new Graph(cityElements.size(), 5);
  37          // Iterate through cityElements
  38          for (Element cityElement: cityElements) {
  39             // Prints names of cities
  40             String cityName = cityElement.getAttributeValue("id");
  41             int cityX = Integer.parseInt(cityElement.getAttributeValue("x"));
  42             int cityY = Integer.parseInt(cityElement.getAttributeValue("y"));
  43             GraphNode cityNode = map.insertNode(cityName, cityX, cityY);
  44             //System.out.println(cityName + " at position (" + cityX + ", " + cityY + ")");
  45
  46             List<Element> roadElements = cityElement.getChildren();
  47             // Iterate through roadElements
  48             for (Element roadElement: roadElements) {
  49                String roadTo = roadElement.getAttributeValue("to");
  50                Double roadSpeed = Double.parseDouble(roadElement.getAttributeValue("speed"));
  51                // Prints all roads connected to the current cityElement
  52                //System.out.println("    road to -> " + roadElement.getAttributeValue("to"));
  53                Double time = 1.0;
  54                if (map.isInGraph(roadTo)) { // @FIX declare var in if condition
  55                   GraphNode roadToNode = map.getNode(roadTo);
  56                   Double distance = Math.hypot((cityNode.getX() - roadToNode.getX()),
  57                                                (cityNode.getY() - roadToNode.getY()));
  58                   time = distance / (roadSpeed / 3.6);
  59                }
  60                map.insertEdge(cityName, roadTo, time);
  61                // @FIX change roadSpeed to time
  62             }
  63          }
  64       }
  65       catch (IOException e) {
  66          System.err.println ("Could not read/find file.");
  67          System.exit(1);
  68       } catch (JDOMException e) {
  69          System.err.println ("File is not in valid XML format?");
  70          System.exit(1);
  71       } catch (NumberFormatException e) {
  72          System.err.println ("Coordinates cannot be parsed.");
  73       }
  74    }
  75
  76    /**
  77     * Utför sökning med Greedy Search.
  78     *
  79     * @param from Den plats sökningen börjar från.
  80     * @param to Den plats sökningen avslutas på.
  81     */
  82    public String greedySearch (String from, String to) {
  83       /*
  84        * implementation av greedySearch.
  85        */
  86       return "";
  87    }
  88
  89    /**
  90     * Utför sökning med A*.
  91     *
  92     * @param from Den plats sökningen börjar från.
  93     * @param to Den plats sökningen avslutas på.
  94     * @param fastest Om <code>true</code>, hitta snabbaste vägen,
  95     * annars den kortaste.
  96     */
  97    public String aStar (String from, String to, boolean fastest) {
  98        // skapa en tabell över hur långt det är från alla platser på
  99        // kartan till målet för sökningen
 100        Hashtable<String, Double> targetDistTable =
 101            new Hashtable<String, Double>(map.size());
 102        // spara ned målnoden
 103        GraphNode targetLocation = map.getNode(to);
 104        GraphNode tempNode;
 105        Enumeration e;
 106        // för alla noder
 107        for (e = map.getNodes(),
 108                 tempNode = (GraphNode) e.nextElement();
 109             e.hasMoreElements(); // medan e har element
 110             tempNode = (GraphNode) e.nextElement()) {
 111            // spara avståndet till målnoden för varje nod
 112            targetDistTable.put(tempNode.getName(),
 113                             Math.hypot(targetLocation.getX()-tempNode.getX(),
 114                                        targetLocation.getY()-tempNode.getY()));
 115        }
 116        /*
 117         * implementation av aStar.
 118         */
 119        return "";
 120    }
 121
 122    /**
 123     * Utför bredden-förstsökning.
 124     *
 125     * @param from Den plats sökningen börjar från.
 126     * @param to Den plats sökningen avslutas på.
 127     */
 128    public String breadthFirst (String from, String to) {
 129       /*
 130        * implementation av breadthFirst.
 131        */
 132       return "";
 133    }
 134
 135    /**
 136     * Utför djupet-förstsökning.
 137     *
 138     * @param from Den plats sökningen börjar från.
 139     * @param to Den plats sökningen avslutas på.
 140     */
 141    public String depthFirst (String from, String to) {
 142       /*
 143        * implementation av depthFirst.
 144        */
 145       return "";
 146    }
 147
 148    public String toString() {
 149       return map.toString();
 150    }
 151 }