Skip to content

Instantly share code, notes, and snippets.

@ayah527
Created May 8, 2021
Embed
What would you like to do?
package bearmaps.server.handler;
import com.google.gson.Gson;
import spark.Request;
import spark.Response;
import spark.Route;
import java.util.HashMap;
import java.util.Set;
import static spark.Spark.halt;
/**
* This is the base class that defines the procedure for handling an API request
* The process is defined as such that first the request parameters are read, then
* request is process based on those parameters and finally the response is built.
*
* Created by rahul
*/
public abstract class APIRouteHandler<Req, Res> implements Route {
/** HTTP failed response. */
private static final int HALT_RESPONSE = 403;
private Gson gson;
public APIRouteHandler() {
gson = new Gson();
}
@Override
public Object handle(Request request, Response response) throws Exception {
Req requestParams = parseRequestParams(request);
Res result = processRequest(requestParams, response);
return buildJsonResponse(result);
}
/**
* Defines how to parse and extract the request parameters from request
* @param request the request object received
* @return extracted request parameters
*/
protected abstract Req parseRequestParams(Request request);
/**
* Process the request using the given parameters
* @param requestParams request parameters
* @param response response object
* @return the result computed after processing request
*/
protected abstract Res processRequest(Req requestParams, Response response);
/**
* Builds a JSON response to return from the result object
* @param result
* @return
*/
protected Object buildJsonResponse(Res result){
return gson.toJson(result);
}
/**
* Validate & return a parameter map of the required request parameters.
* Requires that all input parameters are doubles.
* @param req HTTP Request.
* @param requiredParams TestParams to validate.
* @return A populated map of input parameter to it's numerical value.
*/
protected HashMap<String, Double> getRequestParams(
spark.Request req, String[] requiredParams) {
Set<String> reqParams = req.queryParams();
HashMap<String, Double> params = new HashMap<>();
for (String param : requiredParams) {
if (!reqParams.contains(param)) {
halt(HALT_RESPONSE, "Request failed - parameters missing.");
} else {
try {
params.put(param, Double.parseDouble(req.queryParams(param)));
} catch (NumberFormatException e) {
e.printStackTrace();
halt(HALT_RESPONSE, "Incorrect parameters - provide numbers.");
}
}
}
return params;
}
}
package bearmaps;
import bearmaps.utils.Constants;
import bearmaps.utils.graph.streetmap.Node;
import bearmaps.utils.graph.streetmap.StreetMapGraph;
import bearmaps.utils.ps.KDTree;
import bearmaps.utils.ps.Point;
<<<<<<< HEAD
=======
import javax.print.attribute.HashAttributeSet;
>>>>>>> 8754ac84b4a3355d3ed50251df68961ab9c2a017
import java.util.*;
/**
* An augmented graph that is more powerful that a standard StreetMapGraph.
* Specifically, it supports the following additional operations:
*
* @author Alan Yao, Josh Hug, Ayah Abushama
*/
public class AugmentedStreetMapGraph extends StreetMapGraph {
public KDTree tree;
// For EC.
public MyTrieSet berkeleyLocations;
public HashMap<String, HashSet<Node>> nameToNodes;
public HashMap<String, HashSet<String>> nameToFull;
//To find closest & map the KD tree.
public HashMap<Point, Long> pointToID; // Point object & its ID.
public HashMap<Point, Node> pointToNode;
public List<Point> berkeleyIntersections; // Reference: Josh Hug video.
/**
* Constructor that uses two hashmaps to keep
* track of & create the new KDTree that will be used in closest
*/
public AugmentedStreetMapGraph(String dbPath) {
super(dbPath);
List<Node> nodes = this.getNodes();
pointToID = new HashMap<>();
pointToNode = new HashMap<>();
berkeleyIntersections = new ArrayList<>();
berkeleyLocations = new MyTrieSet();
nameToNodes = new HashMap<>();
nameToFull = new HashMap<>();
for (Node n : nodes) {
Long nodeID = n.id();
double x = projectToX(n.lon(), n.lat());
double y = projectToY(n.lon(), n.lat());
Point curr = new Point(x, y);
pointToID.put(curr, nodeID);
pointToNode.put(curr, n);
if (!neighbors(nodeID).isEmpty()) {
berkeleyIntersections.add(curr);
}
}
tree = new KDTree(berkeleyIntersections);
for (Node n : getAllNodes()) {
if (n.name() == null) {
continue;
}
HashSet<Node> currNameToNodes;
String clearedString = cleanString(n.name());
berkeleyLocations.add(clearedString);
if (!nameToNodes.containsKey(clearedString)) {
currNameToNodes = new HashSet<>();
currNameToNodes.add(n);
nameToNodes.put(clearedString, currNameToNodes);
} else {
currNameToNodes = nameToNodes.get(clearedString);
currNameToNodes.add(n);
nameToNodes.replace(clearedString, currNameToNodes);
}
HashSet<String> currNameToFull;
if (!nameToFull.containsKey(clearedString)) {
currNameToFull = new HashSet<>();
currNameToFull.add(n.name());
nameToFull.put(clearedString, currNameToFull);
} else {
currNameToFull = nameToFull.get(clearedString);
currNameToFull.add(n.name());
nameToFull.replace(clearedString, currNameToFull);
}
}
}
/**
* For Project Part III
* 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.
*/
public long closest(double lon, double lat) {
double x = projectToX(lon, lat);
double y = projectToY(lon, lat);
return pointToID.get(tree.nearest(x, y));
}
/**
* Return the Euclidean x-value for some point, p, in Berkeley. Found by computing the
* Transverse Mercator projection centered at Berkeley.
*
* @param lon The longitude for p.
* @param lat The latitude for p.
* @return The flattened, Euclidean x-value for p.
* @source https://en.wikipedia.org/wiki/Transverse_Mercator_projection
*/
static double projectToX(double lon, double lat) {
double dlon = Math.toRadians(lon - ROOT_LON);
double phi = Math.toRadians(lat);
double b = Math.sin(dlon) * Math.cos(phi);
return (K0 / 2) * Math.log((1 + b) / (1 - b));
}
/**
* Return the Euclidean y-value for some point, p, in Berkeley. Found by computing the
* Transverse Mercator projection centered at Berkeley.
*
* @param lon The longitude for p.
* @param lat The latitude for p.
* @return The flattened, Euclidean y-value for p.
* @source https://en.wikipedia.org/wiki/Transverse_Mercator_projection
*/
static double projectToY(double lon, double lat) {
double dlon = Math.toRadians(lon - ROOT_LON);
double phi = Math.toRadians(lat);
double con = Math.atan(Math.tan(phi) / Math.cos(dlon));
return K0 * (con - Math.toRadians(ROOT_LAT));
}
/**
* For Project Part IV (extra credit)
* In linear time, collect all the names of OSM locations that prefix-match the query string.
*
* @param prefix Prefix string to be searched for. Could be any case, with our without
* punctuation.
* @return A <code>List</code> of the full names of locations whose cleaned name matches the
* cleaned <code>prefix</code>.
*/
public List<String> getLocationsByPrefix(String prefix) {
prefix = cleanString(prefix);
List<String> result = new ArrayList<>();
Iterable<String> locations = berkeleyLocations.keysWithPrefix(prefix);
for (String l : locations) {
if (nameToFull.get(l) == null) {
continue;
}
result.addAll(nameToFull.get(l));
}
return result;
}
/**
* For Project Part IV (extra credit)
* Collect all locations that match a cleaned <code>locationName</code>, and return
* information about each node that matches.
*
* @param locationName A full name of a location searched for.
* @return A list of locations whose cleaned name matches the
* cleaned <code>locationName</code>, and each location is a map of parameters for the Json
* response as specified: <br>
* "lat" -> Number, The latitude of the node. <br>
* "lon" -> Number, The longitude of the node. <br>
* "name" -> String, The actual name of the node. <br>
* "id" -> Number, The id of the node. <br>
*/
public List<Map<String, Object>> getLocations(String locationName) {
HashSet<Node> currNodes = nameToNodes.get(cleanString(locationName));
List<Map<String, Object>> currFinal = new ArrayList<>();
if (currNodes == null) {
return currFinal;
}
for (Node n : currNodes) {
Map<String, Object> currChild = new HashMap<>();
currChild.put("lat", n.lat());
currChild.put("lon", n.lon());
currChild.put("name", n.name());
currChild.put("id", n.id());
currFinal.add(currChild);
}
return currFinal;
}
/**
* Useful for Part III. Do not modify.
* Helper to process strings into their "cleaned" form, ignoring punctuation and capitalization.
*
* @param s Input string.
* @return Cleaned string.
*/
private static String cleanString(String s) {
return s.replaceAll("[^a-zA-Z ]", "").toLowerCase();
}
/**
* Scale factor at the natural origin, Berkeley. Prefer to use 1 instead of 0.9996 as in UTM.
*
* @source https://gis.stackexchange.com/a/7298
*/
private static final double K0 = 1.0;
/**
* Latitude centered on Berkeley.
*/
private static final double ROOT_LAT = (Constants.ROOT_ULLAT + Constants.ROOT_LRLAT) / 2;
/**
* Longitude centered on Berkeley.
*/
private static final double ROOT_LON = (Constants.ROOT_ULLON + Constants.ROOT_LRLON) / 2;
}
package bearmaps;
import bearmaps.server.handler.APIRouteHandler;
import bearmaps.utils.Constants;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import static spark.Spark.*;
/**
* Created by rahul
*/
public class MapServerInitializer {
/**
* Place any initialization statements that will be run before the server main loop here.
* Do not place it in the main function. Do not place initialization code anywhere else.
**/
public static void initializeServer(Map<String, APIRouteHandler> apiHandlers){
port(getHerokuAssignedPort());
Constants.SEMANTIC_STREET_GRAPH = new AugmentedStreetMapGraph(Constants.OSM_DB_PATH);
staticFileLocation("/page");
/* Allow for all origin requests (since this is not an authenticated server, we do not
* care about CSRF). */
before((request, response) -> {
response.header("Access-Control-Allow-Origin", "*");
response.header("Access-Control-Request-Method", "*");
response.header("Access-Control-Allow-Headers", "*");
});
Set<String> paths = new HashSet<>();
for(Map.Entry<String, APIRouteHandler> apiRoute: apiHandlers.entrySet()){
if(paths.contains(apiRoute.getKey())){
throw new RuntimeException("Duplicate API Path found");
}
get("/"+apiRoute.getKey(), apiRoute.getValue());
paths.add(apiRoute.getKey());
}
}
private static int getHerokuAssignedPort() {
ProcessBuilder processBuilder = new ProcessBuilder();
if (processBuilder.environment().get("PORT") != null) {
return Integer.parseInt(processBuilder.environment().get("PORT"));
}
return 4567; //return default port if heroku-port isn't set (i.e. on localhost)
}
}
package bearmaps;
import bearmaps.utils.graph.AStarSolver;
import java.util.List;
import java.util.Objects;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* This class acts as a helper for the RoutingAPIHandler.
* @author Josh Hug, ______
*/
public class Router {
/**
* Overloaded method for shortestPath that has flexibility to specify a solver
* and returns a List of longs representing the shortest path from the node
* closest to a start location and the node closest to the destination location.
* @param g The graph to use.
* @param stlon The longitude of the start location.
* @param stlat The latitude of the start location.
* @param destlon The longitude of the destination location.
* @param destlat The latitude of the destination location.
* @return A list of node id's in the order visited on the shortest path.
*/
public static List<Long> shortestPath(AugmentedStreetMapGraph g, double stlon, double stlat,
double destlon, double destlat) {
long src = g.closest(stlon, stlat);
long dest = g.closest(destlon, destlat);
return new AStarSolver<>(g, src, dest, 20).solution();
}
/**
* Create the list of directions corresponding to a route on the graph.
* @param g The graph to use.
* @param route The route to translate into directions. Each element
* corresponds to a node from the graph in the route.
* @return A list of NavigatiionDirection objects corresponding to the input
* route.
*/
public static List<NavigationDirection> routeDirections(AugmentedStreetMapGraph g,
List<Long> route) {
/* fill in for part IV */
return null;
}
/**
* Class to represent a navigation direction, which consists of 3 attributes:
* a direction to go, a way, and the distance to travel for. This is only
* useful for Part IV of the project.
*/
public static class NavigationDirection {
/** Integer constants representing directions. */
public static final int START = 0;
public static final int STRAIGHT = 1;
public static final int SLIGHT_LEFT = 2;
public static final int SLIGHT_RIGHT = 3;
public static final int RIGHT = 4;
public static final int LEFT = 5;
public static final int SHARP_LEFT = 6;
public static final int SHARP_RIGHT = 7;
/** Number of directions supported. */
public static final int NUM_DIRECTIONS = 8;
/** A mapping of integer values to directions.*/
public static final String[] DIRECTIONS = new String[NUM_DIRECTIONS];
/** Default name for an unknown way. */
public static final String UNKNOWN_ROAD = "unknown road";
/** Static initializer. */
static {
DIRECTIONS[START] = "Start";
DIRECTIONS[STRAIGHT] = "Go straight";
DIRECTIONS[SLIGHT_LEFT] = "Slight left";
DIRECTIONS[SLIGHT_RIGHT] = "Slight right";
DIRECTIONS[LEFT] = "Turn left";
DIRECTIONS[RIGHT] = "Turn right";
DIRECTIONS[SHARP_LEFT] = "Sharp left";
DIRECTIONS[SHARP_RIGHT] = "Sharp right";
}
/** The direction a given NavigationDirection represents.*/
int direction;
/** The name of the way I represent. */
String way;
/** The distance along this way I represent. */
double distance;
/**
* Create a default, anonymous NavigationDirection.
*/
public NavigationDirection() {
this.direction = STRAIGHT;
this.way = UNKNOWN_ROAD;
this.distance = 0.0;
}
public String toString() {
return String.format("%s on %s and continue for %.3f miles.",
DIRECTIONS[direction], way, distance);
}
/**
* Takes the string representation of a navigation direction and converts it into
* a Navigation Direction object.
* @param dirAsString The string representation of the NavigationDirection.
* @return A NavigationDirection object representing the input string.
*/
public static NavigationDirection fromString(String dirAsString) {
String regex = "([a-zA-Z\\s]+) on ([\\w\\s]*) and continue for ([0-9\\.]+) miles\\.";
Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(dirAsString);
NavigationDirection nd = new NavigationDirection();
if (m.matches()) {
String direction = m.group(1);
if (direction.equals("Start")) {
nd.direction = NavigationDirection.START;
} else if (direction.equals("Go straight")) {
nd.direction = NavigationDirection.STRAIGHT;
} else if (direction.equals("Slight left")) {
nd.direction = NavigationDirection.SLIGHT_LEFT;
} else if (direction.equals("Slight right")) {
nd.direction = NavigationDirection.SLIGHT_RIGHT;
} else if (direction.equals("Turn right")) {
nd.direction = NavigationDirection.RIGHT;
} else if (direction.equals("Turn left")) {
nd.direction = NavigationDirection.LEFT;
} else if (direction.equals("Sharp left")) {
nd.direction = NavigationDirection.SHARP_LEFT;
} else if (direction.equals("Sharp right")) {
nd.direction = NavigationDirection.SHARP_RIGHT;
} else {
return null;
}
nd.way = m.group(2);
try {
nd.distance = Double.parseDouble(m.group(3));
} catch (NumberFormatException e) {
return null;
}
return nd;
} else {
// not a valid nd
return null;
}
}
/** Checks that a value is between the given ranges.*/
private static boolean numInRange(double value, double from, double to) {
return value >= from && value <= to;
}
/**
* Calculates what direction we are going based on the two bearings, which
* are the angles from true north. We compare the angles to see whether
* we are making a left turn or right turn. Then we can just use the absolute value of the
* difference to give us the degree of turn (straight, sharp, left, or right).
* @param prevBearing A double in [0, 360.0]
* @param currBearing A double in [0, 360.0]
* @return the Navigation Direction type
*/
private static int getDirection(double prevBearing, double currBearing) {
double absDiff = Math.abs(currBearing - prevBearing);
if (numInRange(absDiff, 0.0, 15.0)) {
return NavigationDirection.STRAIGHT;
}
if ((currBearing > prevBearing && absDiff < 180.0)
|| (currBearing < prevBearing && absDiff > 180.0)) {
// we're going right
if (numInRange(absDiff, 15.0, 30.0) || absDiff > 330.0) {
// bearmaps.proj2c.example of high abs diff is prev = 355 and curr = 2
return NavigationDirection.SLIGHT_RIGHT;
} else if (numInRange(absDiff, 30.0, 100.0) || absDiff > 260.0) {
return NavigationDirection.RIGHT;
} else {
return NavigationDirection.SHARP_RIGHT;
}
} else {
// we're going left
if (numInRange(absDiff, 15.0, 30.0) || absDiff > 330.0) {
return NavigationDirection.SLIGHT_LEFT;
} else if (numInRange(absDiff, 30.0, 100.0) || absDiff > 260.0) {
return NavigationDirection.LEFT;
} else {
return NavigationDirection.SHARP_LEFT;
}
}
}
@Override
public boolean equals(Object o) {
if (o instanceof NavigationDirection) {
return direction == ((NavigationDirection) o).direction
&& way.equals(((NavigationDirection) o).way)
&& distance == ((NavigationDirection) o).distance;
}
return false;
}
@Override
public int hashCode() {
return Objects.hash(direction, way, distance);
}
/**
* 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 lonV The longitude of the first vertex.
* @param latV The latitude of the first vertex.
* @param lonW The longitude of the second vertex.
* @param latW The latitude of the second vertex.
* @return The initial bearing between the vertices.
*/
public static double bearing(double lonV, double lonW, double latV, 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));
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment