HuskyMaps Server

Large-scale integration and closed-form solutions.¹

Learning Goals

• Extending a large, existing code base.

  We’ve actually already built most of the components for HuskyMaps. Unlike prior homeworks, this one starts with a gigantic code base that somebody else wrote. This is typical in the real-world as we often won’t have the luxury and freedom that comes with starting from totally blank files. As a result, you should expect to spend some time getting to know the provided code and APIs. Part of the experience is just figuring out what code needs to change.

• Wrangling slightly messy real-world datasets into useful data structures.

  Data structures exist to manage big data. But, in the real-world, big data is often noisy, incomplete, and biased. While these are problems with the data source (and perhaps a job for the data scientist to wrangle), they also will concern us because we interact with this data to make computations that ultimately affect real, human decisionmaking.

• Implementing an algorithm based on closed-form expressions.

  The fastest data structure is no data structure at all. Closed-form expressions are constant-time solutions to many categories of problems in mathematics and computer science. They have applications even in real-world programs like HuskyMaps where we use a closed-form expression to find the upper-left and lower-right coordinates for the map tiles that intersect your web browser’s viewport.

Table of contents

1. Getting Started
2. Rastering
   1. Bounding Boxes
   2. Edge Cases
   3. Runtime
   4. Testing
3. Street Map Graph
4. Routing
5. Optional Extensions
   1. Heroku Deployment
   2. Map Customization
   3. Turn-By-Turn Navigation
6. Submission

Getting Started

Pull the skeleton repository to get the server assignment. After you update the skeleton code, right-click on the data/ folder, and find the Pull option in the Git drilldown. Do the same for library/. This will download the files needed to run a full web server on your computer.

Once this is done, in the File menu, go to Project Structure, Libraries, +, and add the library/server/ folder.

To verify that everything is working correctly, run the huskymaps.server.MapServer class. If everything is set up correctly, you should see some of the following diagnostic messages appear in your IntelliJ Console.

[Thread-0] INFO org.eclipse.jetty.util.log - Logging initialized @1869ms to org.eclipse.jetty.util.log.Slf4jLog
[Thread-0] WARN org.eclipse.jetty.server.AbstractConnector - Ignoring deprecated socket close linger time
[Thread-0] INFO spark.webserver.JettySparkServer - == Spark has ignited ...
[Thread-0] INFO spark.webserver.JettySparkServer - >> Listening on 0.0.0.0:8080
[Thread-0] INFO org.eclipse.jetty.server.Server - jetty-9.4.15.v20190215; built: 2019-02-15T16:53:49.381Z; git: eb70b240169fcf1abbd86af36482d1c49826fa0b; jvm 11.0.2+9-LTS
[Thread-0] INFO org.eclipse.jetty.server.session - DefaultSessionIdManager workerName=node0
[Thread-0] INFO org.eclipse.jetty.server.session - No SessionScavenger set, using defaults
[Thread-0] INFO org.eclipse.jetty.server.session - node0 Scavenging every 660000ms
[Thread-0] INFO org.eclipse.jetty.server.AbstractConnector - Started ServerConnector@3405d917{HTTP/1.1,[http/1.1]}{0.0.0.0:8080}
[Thread-0] INFO org.eclipse.jetty.server.Server - Started @2235ms

Note

If you’re using Windows, a popup might appear saying “Windows Defender Firewall has blocked some features of this app.” If this happens, you should allow access.

What’s happening here is that your computer is now acting as a web server with your Java code ready to respond to web requests. The web server will continue running in IntelliJ: you can think of it as if there’s an infinite loop waiting until someone loads the map.

Let’s see it in action. In a new web browser tab, enter the following address to connect to your running web server. Upon visiting this page, your web browser sends a request to the Java web server asking for the map image. Since you haven’t implemented the backend, this data will never arrive. Poor web browser.

http://localhost:8080/map.html

If the Java web server received the request from the browser, you should see the following message show in your IntelliJ Console.

Since you haven't implemented rasterizeMap, nothing is displayed in your browser.

If you set a breakpoint in huskymaps.server.logic.Rasterer.rasterizeMap, you’ll be able to inspect the request sent from the web browser! In this homework, we’ll be making changes to the logic for HuskyMaps so that it’ll be able to handle requests from a web browser.

By the end of this homework, with a little extra work, you can even host your application as a publicly-available web app.

Rastering

Rastering is the job of converting information into a pixel-by-pixel image. Given the coordinates of a rectangular region of the world and a requested depth, provide images of the appropriate resolution that cover that region.

Implement Rasterer.rasterizeMap which takes a RasterRequest and returns a RasterResult. As specific example (taken from testSmallDepth7.html), the web browser might make the following RasterRequest.

RasterRequest{ullat=47.655195, ullon=-122.309108, lrlat=47.651298, lrlon=-122.301519, depth=7}

This means that the browser wants the area of Seattle delineated by the rectangle between longitudes -122.309108 (left edge, ullon) and -122.301519 (right edge, lrlon), latitudes 47.655195 (upper edge, ullat) and 47.651298 (lower edge, lrlat), and map tile depth 7 for the most detailed map tiles. We call this entire request for the desired display location the query box.

Note

The left edge longitude is more negative than the right edge longitude since Seattle is to the left of the prime meridian. Conversely, the upper edge latitude is more positive than the lower edge latitude since Seattle is above the equator.

To display the requested information, you need street map tiles, which we have provided in data/tiles. Each map tile is a 256x256 pixel image at various different zoom levels. The more zoomed in, the more individual road labels are visible. For example, the files d0_x0_y0.jpg and d0_x1_y0.jpg represent the entire map region. Note that our map is rectangular! The files d1_x0_y0.jpg, d1_x0_y1.jpg, … are also the entire map, but at double the resolution. d1_x0_y0.jpg is the northwest corner of the map whereas d1_x3_y1.jpg is the southeast corner of the map.

More generally, at depth D, there are 2 * 4^D images with names ranging from dD_x0_y0 to dD_xk_yj, where k is 2^{D + 1} - 1 and j is 2^D - 1 because our map is rectangular. As x increases from 0 to k, we move eastwards. As y increases from 0 to j, we move southwards. In total, there are 43,690 unique map tiles.

Our task is to figure out which of these 43,690 tiles to display. For the example above, your implementation of rasterizeMap should compute the following 2-D array of strings.

[["d7_x140_y53.jpg", "d7_x141_y53.jpg", "d7_x142_y53.jpg", "d7_x143_y53.jpg"],
 ["d7_x140_y54.jpg", "d7_x141_y54.jpg", "d7_x142_y54.jpg", "d7_x143_y54.jpg"],
 ["d7_x140_y55.jpg", "d7_x141_y55.jpg", "d7_x142_y55.jpg", "d7_x143_y55.jpg"]]

This means that the browser should display d7_x140_y53.jpg in the top left, then d7_x141_y53.jpg to its right, and so forth. For this query box, our rastered image is a combination of 12 images arranged in 3 rows of 4 images each. The provided starter code in RasterAPIHandler will stitch these 12 individual images into the following 1024x768 pixel result.

Bounding Boxes

In huskymaps.utils.Constants, there are four constants that define the coordinates of the entire visible map region.

ROOT_ULLAT

Latitude of the upper edge of the map.

ROOT_ULLON

Longitude of the left edge of the map.

ROOT_LRLAT

Latitude of the lower edge of the map.

ROOT_LRLON

Longitude of the right edge of the map.

All of the coordinates covered by a given tile are called the bounding box of that tile. As a result, bounding boxes are laid out on a grid since each image is a 256x256 perfect square. The depth 0 images d0_x0_y0.jpg and d0_x1_y0.jpg cover the coordinates given by ROOT_ULLAT, ROOT_ULLON, ROOT_LRLAT, and ROOT_LRLON. The 8 depth 1 images also cover the same coordinates but at double the detail level and resolution.

How do we know there are 8 depth 1 images? We can use the formula derived earlier, or look at the constants NUM_X_TILES_AT_DEPTH and NUM_Y_TILES_AT_DEPTH. At depth 1, there are 4 x-tiles and 2 y-tiles, hence there are 8 depth 1 images.

The bounding box for any particular tile can be computed using the LON_PER_TILE and LAT_PER_TILE which gives longitudinal and latitudinal distance spanned by each tile on a given depth level. For example, we can figure out the upper-left corner of d7_x140_y53.jpg with the following computation.

double lat = ROOT_ULLAT - (LAT_PER_TILE[7] * 53);
double lon = ROOT_ULLON + (LON_PER_TILE[7] * 140);

Note

The latitude uses subtraction while the longitude uses addition because of Seattle’s location relative to the prime meridian and the equator.

With just these constants, we actually know enough to determine the resulting bounding for any requested query box in constant time!

Warning

You will very likely get latitude and longitude or x and y mixed up at least once. You may also likely mix up which way is up vs. down for y. Make sure to check for that!

Edge Cases

For some queries, it may not be possible to find images to cover the entire query box. This can occur under two scenarios.

• If the browser goes to the edge of the map beyond where data is available.
• If the query box is so zoomed out that it includes the entire dataset.

In these cases, return what data you do have available.

You can also imagine that the browser might request a query box for a location that is completely outside of the Seattle map region. RasterResult will still expect your grid to have data, so you cannot return a 0-by-0 grid directly. In this case, you can return an arbitrary tile. The user should still correctly not see anything on their screen, as their query box would be out of the coordinates covered by this RasterResult.

Runtime

Rasterer.rasterizeMap should take time linear in the number of tiles that match the query.

You should not iterate through / explore all tiles to search for intersections with the query box. Suppose there are k tiles intersecting a query box, and N tiles total. Your entire query should run in O(k) time, not Θ(N) time.

Testing

huskymaps.tests.TestRasterer will run 10 tests that we precomputed on the staff solution. These tests are to help save you time. In an ideal world, we’d have more time to get you to write these tests yourself so that you’d deeply understand them, but we’re giving them to you for free. You should avoid leaning too heavily on these tests unless you really understand them! The staff will not explain individual test failures that are covered elsewhere in the spec, and you are expected to be able to resolve test failures using the skills you’ve been learning to effectively debug.

Poor strategies for debugging. Running the JUnit tests over and over again while making small changes each time and glancing at the error messages without reading the message and working to understand it.

Effective strategies for debugging. Using the debugger, reproducing buggy inputs in a simpler test that you write yourself, rubber duck debugging, and visually comparing the results with map testing.

It can be hard to use the HuskyMaps web app to debug since it involves user input and has a lot of moving parts. We’ve provided two map test files in the static/simple folder named testFullDepth1.html and testSmallDepth7.html. These special test files make the same call to your server each time a web browser visits the file so that errors can be easily reproduced.

To debug with these tests, you may find your browser’s JavaScript console handy. In Chrome on Windows, press F12 to open up the developer tools and tap the Network tab. All browser requests will be listed under type XHR. You can also see the results returned by your rasterizeMap method in the Console tab.

Street Map Graph

huskymaps.StreetMapGraph is an implementation of AStarGraph<Long>. Each vertex of the graph is represented as a Node corresponding to a real, physical location in Seattle with a specific long id. Each Node has a latitude, longitude, and, optionally, a name. They represents both named places (such as the “University of Washington” light rail station) as well as spots along a road (which can be unnamed). Many vertices don’t have edges, specifically those that correspond to places rather than spots along a road.

Implement the following three methods in the StreetMapGraph class.

• public long closest(double lon, double lat)
• public List<String> getLocationsByPrefix(String prefix)
• public List<Location> getLocations(String locationName)

StreetMapGraph.closest will find the vertex nearest to where a user double-clicks on the map. Since closest will be used for finding street routes, only consider vertices that have neighbors. Solve this problem in O(log N) time with a KdTree, but make sure to first project the map data down from a spherical model of the Earth to a flattened 2-D map (Euclidean geometry). Use the projectToX and projectToY methods in huskymaps.utils.Spatial to convert spherical coordinates to x-y points. This ensures that your k-d tree won’t be affected by the spherical curvature of the Earth.

Note

While this approach is accurate for small areas of Earth, it doesn’t scale well outside of the Seattle geographic region because the projection gets increasingly distorted. For a more general solution, the common recommendation is to convert the coordinate points to points in 3-dimensional space with the origin centered on Earth, but this requires a more complex k-d tree implementation.

For getLocationsByPrefix, use your BinaryRangeSearch implementation to return autocomplete results in O(log N + k log k) time where N is the total number of locations and k is the number of results.

Implement getLocations which returns a list of locations that match the given locationName in O(k) time where k is the number of results.

Note

While we have timing requirements, there are no timing-specific tests for this assignment. So long as your implementation does not take unreasonably long to run on the autograder, it should pass even if it’s not the most efficient way to solve the problem.

Routing

Implement Router.shortestPath. This will be very easy. Simply uncomment the given lines.

To test your implementation, try running the TestRouterTiny first. This is a tiny graph that you can work out by hand. Each edge represents a different way (colors picked such that they should appear distinct, so long as you are not 100% achromatopsic). Open the tiny.osm file in the data folder of your repository for more details. We’ve also included a suite of full integration tests in TestRouter.

Optional Extensions

Heroku Deployment

Optionally, you can deploy your HuskyMaps project to the web for free. Make sure that you’ve submitted the project first and have received full credit on Gradescope as we’ll be making changes that are incompatible with the Gradescope autograder.

An easy way to deploy apps to the web is by distributing them as a JAR with dependencies in IntelliJ. A JAR with dependencies is a type of Java ARchive that includes all your code as well as the external libraries (dependencies) used in the project. A JAR with dependencies is a useful way to distribute code that can run anyone else’s machine even without setting up IntelliJ like we did in the first homework. We need to package all the resources, including all 43,690 map tiles, into a single file.

1. From the File menu, tap Project Structure, Artifacts, +, JAR, From modules with dependencies. Your current “module” (your personal repository) will be selected. In the Main Class field, tap on the folder icon on the right end and select the MapServer class.
2. In the Project tool window, open huskymaps.utils.Constants. Make sure that the OSM_DB_PATH is set to seattle-small.osm.gz since the Heroku free instance does not have enough memory to load the full graph. Then, set the HEROKU_DEPLOYMENT boolean flag to true.
3. Build your JAR. From the Build menu, Build Artifacts… This will create your JAR with dependencies in out/artifacts.

Test your JAR by running it from the terminal. In a terminal window, navigate to out/artifacts and run java -jar with the name of your JAR file. Without configuring anything else, the MapServer will run just as it did in IntelliJ!

Once you have a runnable JAR file, set up the Heroku Command Line Interface and create a Heroku app.

1. Create a free Heroku account.
2. Set up Heroku Command Line Interface.
3. In your terminal, navigate to your personal repository and login to Heroku CLI with heroku login.
4. Run heroku create huskymaps-YOUR_UW_NETID. This will create a Heroku app with the name huskymaps-YOUR_UW_NETID visible in your Heroku Dashboard.

Finally, deploy your JAR to your Heroku app.

heroku deploy:jar PATH_TO_JAR.jar --app huskymaps-YOUR_UW_NETID --jdk 11

Check the status of your deployment in the Heroku Dashboard. Your app will be deployed at https://huskymaps-YOUR_UW_NETID.herokuapp.com. On the first use, it typically takes about 10–20 seconds for the Java server to start up and load the OSM database file.

Map Customization

The map tiles for HuskyMaps are provided by MapBox, an open source mapping platform for custom designed maps. Our beautiful map tileset is the “Ice Cream” style by Maya Gao available from the public MapBox Gallery. You can also create your own custom map style in MapBox Studio and download the tileset to your computer for free.

1. Create a free MapBox account and save the access token to a file called token. Make sure the token is not in your personal repository.
2. Choose an existing style from the MapBox Gallery or create your own style in MapBox Studio.
3. Download get_mapbox_tiles.py and config.py to the same directory containing the token. Install Python 3 if it isn’t already installed.
4. From a terminal window, execute the following command, substituting in USERNAME and STYLE for your username and style ID from MapBox Studio. This command will download 43,690 tiles from the MapBox API and place them in a (new) folder called out.

   python3 get_mapbox_tiles.py --username=USERNAME --style=STYLE token out
   

Since it costs MapBox money to run this service, free accounts have a monthly limit. get_mapbox_tiles.py uses the Static Tiles API, which currently allows up to 200,000 monthly tile requests for free. You don’t need to share any payment information with MapBox to use a free account.

Turn-By-Turn Navigation

Optionally, you can also implement turn-by-turn navigation directions by completing the Router.routeDirections method. This is totally optional, not worth any points, but it is awfully cool. We will provide no guidance for this part, but see the NavigationDirection class if you’re interested.

Submission

Commit and push your changes to GitLab before submitting your homework to Gradescope.

Note

We have your repository configured to avoid pushing all of the extra data files that will slow down the autograder. Don’t commit or submit any xml.gz, json, or jpg files. Doing so may waste your internet bandwidth, slow down the autograder, or even crash your computer.