「CS61B」Note(8) Project3 BearMaps

public class Rasterer {
    public static final double ROOT_ULLAT = 37.892195547244356, ROOT_ULLON = -122.2998046875,
            ROOT_LRLAT = 37.82280243352756, ROOT_LRLON = -122.2119140625;
    public static final int TILE_SIZE = 256, MAX_LEVEL = 7;

    public Rasterer() {
    }

    public Map<String, Object> getMapRaster(Map<String, Double> params) {
        System.out.println(params);
        Map<String, Object> results = new HashMap<>();
        boolean query_success = true;
        double lrlon = params.get("lrlon");
        double ullon = params.get("ullon");
        double ullat = params.get("ullat");
        double lrlat = params.get("lrlat");
        double h = params.get("h");
        double w = params.get("w");
        if (ullon > lrlon || ullat < lrlat) {
            query_success = false;
            results.put("query_success", query_success);
            return results;
        }
        double root_lon_width = ROOT_LRLON - ROOT_ULLON;
        double root_lat_height = ROOT_LRLAT - ROOT_ULLAT;
        double LonDPP = (lrlon - ullon) / w;
        int depth = (int) Math.ceil(log(2, root_lon_width / LonDPP) - 8);
        if (depth > MAX_LEVEL) {
            depth = MAX_LEVEL;
        }
        double tile_lon_width = root_lon_width / Math.pow(2, depth);
        double tile_lat_height = root_lat_height / Math.pow(2, depth);
        int raster_ul_x = (int) Math.floor((ullon - ROOT_ULLON) / tile_lon_width);
        int raster_ul_y = (int) Math.floor((ullat - ROOT_ULLAT) / tile_lat_height);
        int raster_lr_x = (int) Math.floor((lrlon - ROOT_ULLON) / tile_lon_width);
        int raster_lr_y = (int) Math.floor((lrlat - ROOT_ULLAT) / tile_lat_height);

        if (checkQueryPosition(raster_ul_x, raster_ul_y, raster_lr_x, raster_lr_y, depth)) {
            Rectangle inter = getIntersection(raster_ul_x, raster_ul_y, raster_lr_x, raster_lr_y,
                    depth);
            raster_ul_x = inter.x;
            raster_ul_y = inter.y;
            raster_lr_x = inter.x + inter.width - 1;
            raster_lr_y = inter.y + inter.height - 1;
        } else {
            query_success = false;
            results.put("query_success", query_success);
            return results;
        }

        double raster_ul_lon = raster_ul_x * tile_lon_width + ROOT_ULLON;
        double raster_ul_lat = raster_ul_y * tile_lat_height + ROOT_ULLAT;
        double raster_lr_lon = (raster_lr_x + 1) * tile_lon_width + ROOT_ULLON;
        double raster_lr_lat = (raster_lr_y + 1) * tile_lat_height + ROOT_ULLAT;
        String[][] render_grid = getRenderGrid(raster_ul_x, raster_ul_y, raster_lr_x, raster_lr_y
                , depth);
        results.put("depth", depth);
        results.put("render_grid", render_grid);
        results.put("raster_ul_lon", raster_ul_lon);
        results.put("query_success", query_success);
        results.put("raster_ul_lat", raster_ul_lat);
        results.put("raster_lr_lon", raster_lr_lon);
        results.put("raster_lr_lat", raster_lr_lat);
//        System.out.println("Since you haven't implemented getMapRaster, nothing is displayed in "
//                           + "your browser.");
        return results;
    }

    private double log(int basement, double n) {
        return Math.log(n) / Math.log(basement);
    }

    private static String[][] getRenderGrid(int raster_ul_x, int raster_ul_y, int raster_lr_x,
                                            int raster_lr_y, int depth) {
        int width = raster_lr_x - raster_ul_x + 1;
        int height = raster_lr_y - raster_ul_y + 1;
        String[][] render_grid = new String[height][width];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                String fs = String.format("d%s_x%s_y%s.png", depth, raster_ul_x + j,
                        raster_ul_y + i);
                render_grid[i][j] = fs;
            }
        }
        return render_grid;
    }

    private boolean checkQueryPosition(int raster_ul_x, int raster_ul_y, int raster_lr_x,
                                       int raster_lr_y, int depth) {
        int m_x = Math.max(raster_ul_x, 0);
        int m_y = Math.max(raster_ul_y, 0);
        int n_x = Math.min(raster_lr_x, (int) Math.pow(2, depth) - 1);
        int n_y = Math.min(raster_lr_y, (int) Math.pow(2, depth) - 1);

        if (m_x <= n_x && m_y <= n_y) {
            return true;
        }
        return false;
    }

    private Rectangle getIntersection(int raster_ul_x, int raster_ul_y, int raster_lr_x,
                                      int raster_lr_y, int depth) {
        Rectangle re1 = new Rectangle(raster_ul_x, raster_ul_y, raster_lr_x - raster_ul_x + 1,
                raster_lr_y - raster_ul_y + 1);
        Rectangle re2 = new Rectangle(0, 0, (int) Math.pow(2, depth), (int) Math.pow(2, depth));
        return re1.intersection(re2);
    }

    public static void main(String[] args) {
        String[][] render_grid = getRenderGrid(0, 0, 2, 2, 2);
        for (String[] sl : render_grid) {
            for (String s : sl) {
                System.out.println(s);
            }
        }
    }
}

public class GraphDB {
    public GraphDB(String dbPath) {
        try {
            File inputFile = new File(dbPath);
            FileInputStream inputStream = new FileInputStream(inputFile);
            // GZIPInputStream stream = new GZIPInputStream(inputStream);

            SAXParserFactory factory = SAXParserFactory.newInstance();
            SAXParser saxParser = factory.newSAXParser();
            GraphBuildingHandler gbh = new GraphBuildingHandler(this);
            saxParser.parse(inputStream, gbh);
        } catch (ParserConfigurationException | SAXException | IOException e) {
            e.printStackTrace();
        }
        clean();
        buildCleanTrieAndCleanMap();
//        for (String l : getLocationsByPrefix("a")){
//            System.out.println(l);
//        }
    }

    private final Map<Long, Node> nodes = new HashMap<>();
    private final Map<Long, Node> nodesOriginal = new HashMap<>();
    private final Map<Long, Way> ways = new HashMap<>();
    private final Map<Long, Edge> edges = new HashMap<>();
    TrieTree locationTree = new TrieTree();
    Map<String, List<Long>> cleanNameMap = new HashMap<>();

    static class Node {
        Long id;
        double lon;
        double lat;
        LinkedList<Long> adj;
        LinkedList<Long> adjEdge;
        String name;

        Node(Long id, double lon, double lat) {
            this.id = id;
            this.lon = lon;
            this.lat = lat;
            this.adj = new LinkedList<>();
            this.name = null;
            this.adjEdge = new LinkedList<>();
        }
    }

    static class Edge {
        Long edgeId;
        Long wayId;
        Set<Long> points;
        String wayName;

        Edge(Long edgeId, Long wayId, Long from, Long to) {
            this.edgeId = edgeId;
            this.wayId = wayId;
            points = new HashSet<>();
            points.add(from);
            points.add(to);
            this.wayName = null;
        }
    }

    static class Way {
        Long id;
        LinkedList<Long> edges;
        String name;
        String maxSpeed;

        Way(Long id, LinkedList<Long> edges) {
            this.id = id;
            this.edges = edges;
            this.name = null;
            this.maxSpeed = "";
        }
    }

//    HashSet<HashSet<Long>> getConnections(long wayId) {
//        return ways.get(wayId).connections;
//    }

    long getNumberOfEdge() { return edges.size(); }

    String getWayName(long wayId) {
        return ways.get(wayId).name;
    }

    String getWayNameFromEdge(long edgeId) {
        return edges.get(edgeId).wayName;
    }

    LinkedList<Long> adjEdgeOfNode(long v) { return nodes.get(v).adjEdge; }

    Set<Long> getPointsOfEdge(long edgeId) { return edges.get(edgeId).points; }

    /**
     * Helper to process strings into their "cleaned" form, ignoring punctuation and capitalization.
     * @param s Input string.
     * @return Cleaned string.
     */
    static String cleanString(String s) {
        return s.replaceAll("[^a-zA-Z]", "").toLowerCase();
    }

    /**
     *  Remove nodes with no connections from the graph.
     *  While this does not guarantee that any two nodes in the remaining graph are connected,
     *  we can reasonably assume this since typically roads are connected.
     */
    private void clean() {
        // TODO: Your code here.
        for (long nodeId : nodes.keySet()) {
            nodesOriginal.put(nodeId, nodes.get(nodeId));
        }
        nodes.values().removeIf(n -> n.adj.isEmpty());
    }

    void buildCleanTrieAndCleanMap() {
        System.out.println(nodesOriginal.size());
        int s = 0;
        for (Node n : nodesOriginal.values()) {
            if (n.name != null) {
                s++;
                String cleanName = GraphDB.cleanString(n.name);
                this.locationTree.insert(cleanName);
                if (this.cleanNameMap.containsKey(cleanName)) {
                    this.cleanNameMap.get(cleanName).add(n.id);
                } else {
                    LinkedList<Long> nodeIdList = new LinkedList<>();
                    nodeIdList.add(n.id);
                    this.cleanNameMap.put(cleanName, nodeIdList);
                }
                System.out.println(cleanName);
            }
        }
        System.out.println(s);
    }

    /**
     * Returns an iterable of all vertex IDs in the graph.
     * @return An iterable of id's of all vertices in the graph.
     */
    Iterable<Long> vertices() {
        //YOUR CODE HERE, this currently returns only an empty list.
        return nodes.keySet();
    }

    Iterable<Long> ways() {
        //YOUR CODE HERE, this currently returns only an empty list.
        return ways.keySet();
    }

    /**
     * Returns ids of all vertices adjacent to v.
     * @param v The id of the vertex we are looking adjacent to.
     * @return An iterable of the ids of the neighbors of v.
     */
    Iterable<Long> adjacent(long v) {
        return nodes.get(v).adj;
    }

    /**
     * Returns the great-circle distance between vertices v and w in miles.
     * Assumes the lon/lat methods are implemented properly.
     * <a href="https://www.movable-type.co.uk/scripts/latlong.html">Source</a>.
     * @param v The id of the first vertex.
     * @param w The id of the second vertex.
     * @return The great-circle distance between the two locations from the graph.
     */
    double distance(long v, long w) {
        return distance(lon(v), lat(v), lon(w), lat(w));
    }

    static double distance(double lonV, double latV, double lonW, double latW) {
        double phi1 = Math.toRadians(latV);
        double phi2 = Math.toRadians(latW);
        double dphi = Math.toRadians(latW - latV);
        double dlambda = Math.toRadians(lonW - lonV);

        double a = Math.sin(dphi / 2.0) * Math.sin(dphi / 2.0);
        a += Math.cos(phi1) * Math.cos(phi2) * Math.sin(dlambda / 2.0) * Math.sin(dlambda / 2.0);
        double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
        return 3963 * c;
    }

    /**
     * Returns the initial bearing (angle) between vertices v and w in degrees.
     * The initial bearing is the angle that, if followed in a straight line
     * along a great-circle arc from the starting point, would take you to the
     * end point.
     * Assumes the lon/lat methods are implemented properly.
     * <a href="https://www.movable-type.co.uk/scripts/latlong.html">Source</a>.
     * @param v The id of the first vertex.
     * @param w The id of the second vertex.
     * @return The initial bearing between the vertices.
     */
    double bearing(long v, long w) {
        return bearing(lon(v), lat(v), lon(w), lat(w));
    }

    static double bearing(double lonV, double latV, double lonW, double latW) {
        double phi1 = Math.toRadians(latV);
        double phi2 = Math.toRadians(latW);
        double lambda1 = Math.toRadians(lonV);
        double lambda2 = Math.toRadians(lonW);

        double y = Math.sin(lambda2 - lambda1) * Math.cos(phi2);
        double x = Math.cos(phi1) * Math.sin(phi2);
        x -= Math.sin(phi1) * Math.cos(phi2) * Math.cos(lambda2 - lambda1);
        return Math.toDegrees(Math.atan2(y, x));
    }

    /**
     * Returns the vertex closest to the given longitude and latitude.
     * @param lon The target longitude.
     * @param lat The target latitude.
     * @return The id of the node in the graph closest to the target.
     */
    long closest(double lon, double lat) {
        long closestId = 0;
        double dMin = -1;
        double d = 0;
        for (Node n : nodes.values()) {
            d = distance(lon, lat, n.lon, n.lat);
            if (d < dMin || dMin == -1) {
                closestId = n.id;
                dMin = d;
            }
        }
        return closestId;
    }

    /**
     * Gets the longitude of a vertex.
     * @param v The id of the vertex.
     * @return The longitude of the vertex.
     */
    double lon(long v) {
        return nodes.get(v).lon;
    }

    /**
     * Gets the latitude of a vertex.
     * @param v The id of the vertex.
     * @return The latitude of the vertex.
     */
    double lat(long v) {
        return nodes.get(v).lat;
    }

    void addNode(Node n) {
        this.nodes.put(n.id, n);
//        if (n.name != null) { locationTree.insert(n.name); }
    }

    LinkedList<String> getLocationsByPrefix(String prefix) {
        LinkedList<String> locationList = new LinkedList<>();
        HashMap<String, Integer> prefixMap = locationTree.getWordsForPrefix(cleanString(prefix));
        if (prefixMap == null) { return null; }
        for (String cleanName : prefixMap.keySet()) {
            long nodeId = cleanNameMap.get(cleanName).get(0);
            locationList.add(nodesOriginal.get(nodeId).name);
        }
        return locationList;
    }

    List<Map<String, Object>> getLocations(String locationName) {
        String cleanName = cleanString(locationName);
        LinkedList<Map<String, Object>> locations = new LinkedList<>();
        if (cleanNameMap.containsKey(cleanName)) {
            for (long nodeId : cleanNameMap.get(cleanName)) {
                Node thisNode = nodesOriginal.get(nodeId);
                Map<String, Object> locationMap = new HashMap<>();
                locationMap.put("lon", thisNode.lon);
                locationMap.put("lat", thisNode.lat);
                locationMap.put("name", thisNode.name);
                locationMap.put("id", thisNode.id);
                locations.add(locationMap);
            }
            return locations;
        }
        return null;
    }

    void addWay(Way w, LinkedList<Long> nodesOfWay) {
        this.ways.put(w.id, w);
        int size = nodesOfWay.size();
        for (int i = 0; i < size - 1; i++) {
            Edge e = new Edge(getNumberOfEdge(), w.id, nodesOfWay.get(i), nodesOfWay.get(i + 1));
            e.wayName = w.name;
            addAdj(nodesOfWay.get(i), nodesOfWay.get(i + 1));
            nodes.get(nodesOfWay.get(i)).adjEdge.add(e.edgeId);
            nodes.get(nodesOfWay.get(i + 1)).adjEdge.add(e.edgeId);
            edges.put(e.edgeId, e);
            w.edges.add(e.edgeId);
        }
//        for (int i = 0; i <= w.nodesOfWay.size() - 2; i++) {
//            addEdge(w.nodesOfWay.get(i), w.nodesOfWay.get(i + 1));
//        }
    }
//    void addEdge(Edge e) {
//        this.edges.put(e.id, e);
//        nodes.get(e.from).adj.add(e.to);
//        nodes.get(e.to).adj.add(e.from);
//    }
    void addAdj(Long from, Long to) {
        nodes.get(from).adj.add(to);
        nodes.get(to).adj.add(from);
    }
}

import org.xml.sax.Attributes;
import org.xml.sax.SAXException;
import org.xml.sax.helpers.DefaultHandler;

import java.util.*;

public class GraphBuildingHandler extends DefaultHandler {

    private static final Set<String> ALLOWED_HIGHWAY_TYPES = new HashSet<>(Arrays.asList
            ("motorway", "trunk", "primary", "secondary", "tertiary", "unclassified",
                    "residential", "living_street", "motorway_link", "trunk_link", "primary_link",
                    "secondary_link", "tertiary_link"));
    private String activeState = "";
    private final GraphDB g;
    private LinkedList<Long> nodesOfWay;
    private boolean isWay;
    private GraphDB.Node lastNode;
    private GraphDB.Way lastWay;
    private int numberOfUnknownRoad = 0;
//    int indexOfNodeThisWay = 0;
//    long idOfLastNodeThisWay = 0;


    public GraphBuildingHandler(GraphDB g) {
        this.g = g;
        this.lastNode = null;
        this.isWay = false;
//        this.nodesOfWay = new LinkedList<Long>();
    }

    @Override
    public void startElement(String uri, String localName, String qName, Attributes attributes)
            throws SAXException {
        /* Some example code on how you might begin to parse XML files. */
        if (qName.equals("node")) {
            /* We encountered a new <node...> tag. */
            activeState = "node";
//            System.out.println("Node id: " + attributes.getValue("id"));
//            System.out.println("Node lon: " + attributes.getValue("lon"));
//            System.out.println("Node lat: " + attributes.getValue("lat"));

            /* TODO Use the above information to save a "node" to somewhere. */
            /* Hint: A graph-like structure would be nice. */
            GraphDB.Node n = new GraphDB.Node(Long.parseLong(attributes.getValue("id")),
                    Double.parseDouble(attributes.getValue("lon")),
                    Double.parseDouble(attributes.getValue("lat")));
            g.addNode(n);
            lastNode = n;
        } else if (qName.equals("way")) {
            /* We encountered a new <way...> tag. */
            activeState = "way";
            nodesOfWay = new LinkedList<>();
            isWay = false;
            lastWay = new GraphDB.Way(Long.parseLong(attributes.getValue("id")), new LinkedList<>());
//            System.out.println("Beginning a way...");
        } else if (activeState.equals("way") && qName.equals("nd")) {

            nodesOfWay.add(Long.parseLong(attributes.getValue("ref")));


        } else if (activeState.equals("way") && qName.equals("tag")) {
            /* While looking at a way, we found a <tag...> tag. */
            String k = attributes.getValue("k");
            String v = attributes.getValue("v");
            if (k.equals("maxspeed")) {
//                System.out.println("Max Speed: " + v);
                /* TODO set the max speed of the "current way" here. */
                lastWay.maxSpeed = v;
            } else if (k.equals("highway")) {
                //System.out.println("Highway type: " + v);
                /* TODO Figure out whether this way and its connections are valid. */
                /* Hint: Setting a "flag" is good enough! */
                isWay = ALLOWED_HIGHWAY_TYPES.contains(v);
            } else if (k.equals("name")) {
                //System.out.println("Way Name: " + v);
                lastWay.name = v;
            }
//            System.out.println("Tag with k=" + k + ", v=" + v + ".");
        } else if (activeState.equals("node") && qName.equals("tag") && attributes.getValue("k")
                .equals("name")) {
            /* While looking at a node, we found a <tag...> with k="name". */
            /* TODO Create a location. */
            /* Hint: Since we found this <tag...> INSIDE a node, we should probably remember which
            node this tag belongs to. Remember XML is parsed top-to-bottom, so probably it's the
            last node that you looked at (check the first if-case). */
//            System.out.println("Node's name: " + attributes.getValue("v"));
            lastNode.name = attributes.getValue("v");
//            System.out.println(GraphDB.cleanString(lastNode.name));
//            if (lastNode.name != null) {
//                String cleanName = GraphDB.cleanString(lastNode.name);
//                g.locationTree.insert(cleanName);
//                if (g.cleanNameMap.containsKey(cleanName)) {
//                    g.cleanNameMap.get(cleanName).add(lastNode.id);
//                } else {
//                    LinkedList<Long> nodeIdList = new LinkedList<>();
//                    nodeIdList.add(lastNode.id);
//                    g.cleanNameMap.put(cleanName, nodeIdList);
//                }
//            }
        }
    }

    @Override
    public void endElement(String uri, String localName, String qName) throws SAXException {
        if (qName.equals("way")) {
            /* We are done looking at a way. (We finished looking at the nodes, speeds, etc...)*/
            /* Hint1: If you have stored the possible connections for this way, here's your
            chance to actually connect the nodes together if the way is valid. */
//            System.out.println("Finishing a way...");
            if (isWay){
                if (lastWay.name == null) {
                    lastWay.name = String.format("unknown road %s",numberOfUnknownRoad);
                    numberOfUnknownRoad++;
                }
                g.addWay(lastWay, nodesOfWay);
//                for (int i = 0; i < lastWay.nodesOfWay.size() - 2; i++) {
//                    GraphDB.Edge e = new GraphDB.Edge(nodesOfWay.get(i), nodesOfWay.get(i + 1));
//                    g.addEdge(lastWay.nodesOfWay.get(i), lastWay.nodesOfWay.get(i + 1));
//                }
            }
        }
    }
}

    public static List<Long> shortestPath(GraphDB g, double stlon, double stlat,
                                          double destlon, double destlat) {
        PriorityQueue<SearchNode> pq = new PriorityQueue<>(new NodeComparator());
        SearchNode minSearchNode;
        long stNodeId = g.closest(stlon, stlat);
        long destNodeId = g.closest(destlon, destlat);
        Map<Long, Double> distTo = new LinkedHashMap<>();

        //insert an “initial search node” into the priority queue
        SearchNode initialSearchNode = new SearchNode(g, stNodeId, destNodeId, 0, null);
        pq.add(initialSearchNode);
        distTo.put(stNodeId, 0.0);
        //Remove the search node with minimum priority
        minSearchNode = pq.poll();
//        int j = 0;

        while (minSearchNode.nodeId != minSearchNode.destNodeId) {
//            if (j < 20) {
//                System.out.println("This node:" + minSearchNode.nodeId);
//            }
//            j++;
            for (long adjId : g.adjacent(minSearchNode.nodeId)) {
                if (!distTo.containsKey(adjId)) {
                    distTo.put(adjId, 200.0);
                }
                double distToAdj = minSearchNode.distanceFromStart + g.distance(minSearchNode.nodeId, adjId);
                //critical optimization : checks that no enqueued Node is its own grandparent
                if (minSearchNode.previousSearchNode == null ||
                        (adjId != minSearchNode.previousSearchNode.nodeId &&
                        distToAdj < distTo.get(adjId))) {
                    pq.add(new SearchNode(g, adjId, destNodeId, distToAdj, minSearchNode));
                    distTo.put(adjId, distToAdj);
//                    if (j < 20) {
//                        System.out.println("adj:" + adjId);
//                    }
                }
            }
            minSearchNode = pq.poll();
        }

//        Queue<Long> queue = new LinkedList<>();
//        SearchNode thisSearchNode = minSearchNode;
//        while (thisSearchNode != null) {
//            queue.add(thisSearchNode.nodeId);
//            thisSearchNode = thisSearchNode.previousSearchNode;
//        }
        Stack<Long> stack = new Stack<>();
        SearchNode thisSearchNode = minSearchNode;
        while (thisSearchNode != null) {
            stack.push(thisSearchNode.nodeId);
            thisSearchNode = thisSearchNode.previousSearchNode;
        }
        int size = stack.size();
        LinkedList<Long> list = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            list.add(i, stack.pop());
        }
        return list; // FIXME
    }

    private static class SearchNode{
//        GraphDB.Node node;
        long nodeId;
        long destNodeId;
        double distanceFromStart;
        SearchNode previousSearchNode;
        //second optimization : save estimatedDistanceToGoal of WorldState in an instance variable
        double estimatedDistanceToDest;

        public SearchNode(GraphDB g, long nodeId, long destNodeId, double dfs, SearchNode psn) {
            this.nodeId = nodeId;
            this.destNodeId = destNodeId;
            this.distanceFromStart = dfs;
            this.previousSearchNode = psn;
            this.estimatedDistanceToDest = g.distance(nodeId, destNodeId);
        }
    }

    private static class NodeComparator implements Comparator<SearchNode> {
        @Override
        public int compare(SearchNode sn1, SearchNode sn2) {
            int c = 0;
            if (sn1.distanceFromStart + sn1.estimatedDistanceToDest < sn2.distanceFromStart + sn2.estimatedDistanceToDest) {
                c = -1;
            } else if (sn1.distanceFromStart + sn1.estimatedDistanceToDest > sn2.distanceFromStart + sn2.estimatedDistanceToDest) {
                c = 1;
            }
            return c;
//            int c = (int)((sn1.distanceFromStart + sn1.estimatedDistanceToDest
//                    - (sn2.distanceFromStart + sn2.estimatedDistanceToDest)) * Math.pow(10, 8));
//            return c;
        }
    }

public static List<NavigationDirection> routeDirections(GraphDB g, List<Long> route) {
    List<NavigationDirection> listOfNavigationDirection = new LinkedList<>();
    LinkedList<String> listOfWay = new LinkedList<>();
    for (int i = 0; i < route.size() - 1; i++) {
        for (long edgeId : g.adjEdgeOfNode(route.get(i))) {
            if (g.getPointsOfEdge(edgeId).contains(route.get(i + 1))) {
                listOfWay.add(g.getWayNameFromEdge(edgeId));
            }
        }
    }
    NavigationDirection nd = new NavigationDirection();
    if (route.size() == 2) {
        nd.direction = 0;
        nd.distance = g.distance(route.get(0), route.get(1));
        nd.way = listOfWay.get(0);
        listOfNavigationDirection.add(nd);
        return listOfNavigationDirection;
    }
    for (int i = 1; i < route.size() - 1; i++) {
        long prevNodeId = route.get(i - 1);
        long currentNodeId = route.get(i);
        long nextNodeId = route.get(i + 1);
        nd.distance += g.distance(prevNodeId, currentNodeId);
        if (i == 1) {
            nd.direction = 0;
            if (listOfWay.get(0).contains("unknown road")) {
                nd.way = "";
            } else {
                nd.way = listOfWay.get(0);
            }
        }
        if (!listOfWay.get(i - 1).equals(listOfWay.get(i))){
            listOfNavigationDirection.add(nd);
            nd = new NavigationDirection();
            double bearing = g.bearing(currentNodeId, nextNodeId) - g.bearing(prevNodeId, currentNodeId);
            nd.direction = chooseDirection(bearing);
            if (listOfWay.get(i).contains("unknown road")) {
                nd.way = "";
            } else {
                nd.way = listOfWay.get(i);
            }
        }
        if (i == route.size() - 2) {
            nd.distance += g.distance(currentNodeId, nextNodeId);
            listOfNavigationDirection.add(nd);
        }
    }
    return listOfNavigationDirection; // FIXME
}

private static int chooseDirection(double bearing) {
    double absBearing = Math.abs(bearing);
    if (absBearing > 180) {
        absBearing = 360 - absBearing;
        bearing *= -1;
    }
    if (absBearing <= 15) {
        return 1;
    } else if (absBearing <= 30) {
        if (bearing < 0) {
            return 2;
        } else {
            return 3;
        }
    } else if (absBearing <= 100) {
        if (bearing < 0) {
            return 5;
        } else {
            return 4;
        }
    } else if (bearing < -100) {
        return 6;
    } else {
        return 7;
    }
}

    LinkedList<String> getLocationsByPrefix(String prefix) {
        LinkedList<String> locationList = new LinkedList<>();
        HashMap<String, Integer> prefixMap = locationTree.getWordsForPrefix(cleanString(prefix));
        if (prefixMap == null) { return null; }
        for (String cleanName : prefixMap.keySet()) {
            long nodeId = cleanNameMap.get(cleanName).get(0);
            locationList.add(nodesOriginal.get(nodeId).name);
        }
        return locationList;
    }

    List<Map<String, Object>> getLocations(String locationName) {
        String cleanName = cleanString(locationName);
        LinkedList<Map<String, Object>> locations = new LinkedList<>();
        if (cleanNameMap.containsKey(cleanName)) {
            for (long nodeId : cleanNameMap.get(cleanName)) {
                Node thisNode = nodesOriginal.get(nodeId);
                Map<String, Object> locationMap = new HashMap<>();
                locationMap.put("lon", thisNode.lon);
                locationMap.put("lat", thisNode.lat);
                locationMap.put("name", thisNode.name);
                locationMap.put("id", thisNode.id);
                locations.add(locationMap);
            }
            return locations;
        }
        return null;
    }

static class Node {
    Long id;  // node id
    double lon;  // location
    double lat;
    LinkedList<Long> adj;  // list of adjacent nodes
    LinkedList<Long> adjEdge; // list of linked edges
    String name;  // node name
}

static class Edge {
        Long edgeId;  // edge id
        Long wayId; // id of the way this edge belongs to
        Set<Long> points;  // set of start point and end point
        String wayName; // way name
}

static class Way {
        Long id; // way id
        LinkedList<Long> edges; // edges this way includes
        String name;  // way name
        String maxSpeed;  // max speed of this way
}

// cleaned nodes map, key: node id, value: Node instance
private final Map<Long, Node> nodes = new HashMap<>();

// original nodes map(for search), key: node id, value: Node instance
private final Map<Long, Node> nodesOriginal = new HashMap<>();

// ways map, key: way id, value: Way instance
private final Map<Long, Way> ways = new HashMap<>();

// edges map, key: edge id, value: Edge instance
private final Map<Long, Edge> edges = new HashMap<>();

// nodes TrieTree(for autocompletion)
TrieTree locationTree = new TrieTree();

// map of "cleaned" name of nodes(for search and autocompletion), key: cleaned name, value: list of nodes(there might be multiple nodes that share a same name)
// "clean" means throw away spaces and symbols and turn every character into lowercase
Map<String, List<Long>> cleanNameMap = new HashMap<>();