HuskyMaps Server

Large-scale integration and closed-form solutions.1

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. Optional Extensions
    1. Turn-By-Turn Navigation
    2. Heroku Deployment
    3. Map Customization
  5. 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. Then, add the server library to your module dependencies.

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
[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]}{}
[Thread-0] INFO org.eclipse.jetty.server.Server - Started @2235ms
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.


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.


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.

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 * 4D images with names ranging from dD_x0_y0 to dD_xk_yj, where k is 2D + 1 - 1 and j is 2D - 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 tiles.

[["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.

testSmallDepth7 Result

Bounding Boxes

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

Latitude of the upper edge of the map.
Longitude of the left edge of the map.
Latitude of the lower edge of the map.
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);
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!

Rastering Example

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.


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

You should not 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.


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. Nodes and edges are added to the graph by the OSMGraphHandler class, which reads data from an OpenStreetMap dataset.

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 your KDTreePointSet.

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. Make sure that there are no duplicate terms. The importance of a term such as “University of Washington” is the same for all nodes that share the same name.

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

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.

Optional Extensions

Turn-By-Turn Navigation

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

Heroku Deployment

Optionally, you can deploy your HuskyMaps project to the web for free.

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. This process with 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. 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_CSE_NETID. This will create a Heroku app with the name huskymaps-YOUR_CSE_NETID visible in your Heroku Dashboard.

Finally, deploy your JAR to your Heroku app. If you’re using a different JDK version, change the JDK flag accordingly.

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

Check the status of your deployment in the Heroku Dashboard. 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 and 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 --username=USERNAME --style=STYLE token out

Since it costs MapBox money to run this service, free accounts have a monthly limit. 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.


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

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.
  1. © Mapbox, © OpenStreetMap, Improve this map. Data available under the Open Database License.

    Components include the JavaSpark web framework and Google Gson library. Alan Yao for creating the original version of this project. Colby Yuan and Eli Lipsitz for substantial refactoring of the front end. Rahul Nangia for substantial refactoring of the back end.

    Josh Hug. 2018. Bear Maps: Creating Routes with Open Street Maps. In Nifty Assignments 2018.