Quick links:
Contents:
We recommend that you read the entire problem set before you begin work.
In this assignment you will practice writing code that satisfies a given specification. You will submit your code, a suite of test cases (that exercises its functionality), documentation, and answers to several questions.
Problem sets 2 through 6 will address different aspects of the design, implementation, documentation, and testing of MapQuick, a Google Maps-like system for giving directions between locations in Boston and Cambridge. In this problem set you will build data abstractions that represent routes between two geographic points in the real world. In problem set 3, you will implement a generic graph datatype and shortest path finder. In problem set 4, you will implement data types to represent streets, and begin to integrate these with your graph from problem set 3. In problem set 5 you will formally analyze the code you wrote in problem sets 2-4. Finally, in problem set 6, you will integrate all of these parts to build a working system for giving directions between two addresses.
This problem set concerns routes. A route is an ordered sequence of steps that, collectively, take you from one location to another. The following classes will be used to represent routes in this assignment:
Note that a GeoFeature represents part of a path along a single geographic feature in the world. It doesn't necessarily represent the longest possible path along that feature, nor the only path. For example, imagine a Route traveling down Mass Ave for two blocks, and another Route traveling down Mass Ave for three blocks. The GeoFeature representing the path along Mass Ave in the first Route doesn't need to know or care about the GeoFeature representing the path along Mass Ave in the second Route. They are distinct GeoFeatures even though they have two GeoSegments and a name in common.
Also note that the same GeoSegment may be added twice to a Route (or GeoFeature) to represent driving around in a circle.
There are three additional classes that are used to generate human-readable directions for navigating along a Route:
computeDirections(), which takes a Route
object and a heading and returns a String containing
the directions.computeDirections()
generates walking directions.computeDirections() will be appropriate for
driving.Update the psets module in your CVS repository. This will create a psets/ps2 directory, and will also update various other files that you need. Then, work through the problems below. Use the provided specifications to help you fill in the missing methods.
You are free to work from home if that makes your life easier, but keep in mind that your final code must run correctly on Athena. Once everything is in order, commit your changes. You should also run ant validate (on Athena) as a double-check after committing.
These skeleton classes are provided to you to help get you started. You will need to implement them according to their Javadoc specifications in order to complete this problem set. Take a look at the Javadoc specifications for more information.
The following complete test cases are provided for you. You may consider these to be rigorous enough that you do not need to write your own tests for the associated classes. You will need to write your own tests for the remaining classes.
By the end of the problem set, you should have the following files committed to CVS in your ps2 directory:
You may find it easiest to do problems 1-3 on one class at a time in the following order: GeoPoint, GeoSegment, GeoFeature, Route, WalkingRouteFormatter, DrivingRouteFormatter.
It is good practice to write tests before you write your code. By writing your tests first it's easier to write them so that they test what the code is supposed to do rather than how you are doing it. This is known as specification or black box testing, where the goal is to ensure that the post-conditions for each method are met assuming the pre-conditions are.
For this problem you will use JUnit to write a test suite like the one that was given to you in problem set 1. We have provided skeleton test files for three classes: ps2.test.GeoSegmentTest, ps2.test.GeoFeatureTest, and ps2.test.RouteTest, and complete test cases for three classes: ps2.test.GeoPointTest, ps2.test.WalkingRouteFormatterTest and ps2.test.DrivingRouteFormatterTest; it will probably help you to study those before filling in the skeletons.
Please note that you should not edit the non-skeleton test
cases provided to you. Any changes you make will be ignored; your
code must pass GeoPointTest,
WalkingRouteFormatterTest, and
DrivingRouteFormatterTest in their original form.
To receive full credit, your program will need to pass all your test cases and all of the staff's internal test cases. However, if there are any known cases where your program fails, please indicate them in problem 4 question 1.
Create the representation invariant and abstraction function for GeoPoint,
GeoSegment, GeoFeature, and Route.
For each of those classes, define a checkRep() method that will
catch any violation of your representation constraints. Before moving
on to problem 3, insert calls to your checkRep() method
in the appropriate methods.
Implement the methods defined in the skeleton classes. The provided Javadocs are identical to the ones in the classes themselves. You might also want to read the specification handout for more info about the format of our specifications.
Put the answers to these questions in a plain-text file named answers/problem4.txt and make sure you add it to CVS and check it in along with your source code.
Explain any assumptions your program makes that aren't stated in the specifications. If there was anything you found unclear, please explain how you interpreted it and how alternate interpretations would have affected your code. If any of your test cases fail, use this section to explain why. You may write "No clarification necessary" here.
Route.addSegment() requires the GeoSegment
argument to be properly oriented (with respect to which end is
p1 and which end is p2). If this precondition
were replaced with the precondition below, how would the
implementation of these classes and their clients change? Explain
this in a sentence or two. Is the requires clause below stronger
or weaker than the original? Is the new specification stronger or
weaker?
@requires gs != null && (gs.p1 = this.end || gs.p2 = this.end)
In a paragraph or two explain what you regarded as the successes and failures of the development. Things to think about are unresolved design problems, potential performance issues, good or bad choices of representation, etc. If you think you did something particularly clever that you want us to notice, point it out here. Also describe what, if anything, you would do differently a second time around.
Please answer the following questions in a file named reflection.txt in your answers/ directory.
Please answer the following questions in a file named collaboration.txt in your answers/ directory.
The standard collaboration policy applies to this problem set.
State whether or not you collaborated with other students. If you did collaborate with other students, put their names and a brief description of how you collaborated.
After you receive your corrected problem set back from your TA, you will have several weeks before you have to resubmit it electronically. The procedure for this is detailed in the General Information document.
The due date for the returnin of this problem set is Oct 4, 2007 at 11:59 pm. Returnin will be enabled at 11:59 pm, Sep 27, 2007.
You will only receive credit if you pass all the tests, and you have a fixed number of trials without penalty. See the returnin6170 documentation for details.
See the problem set guidelines and advice.
You don't need to check the "nearby Boston" precondition. How close to Boston the locations should be depends on the precision required by the user of the code, something we have chosen not to explicitly address.
If you choose to implement your own hashCode() method, be
sure you preserve the hash code invariant. That is, if
a.equals(b) then a.hashCode() == b.hashCode() (the
converse is not necessarily true). Note that implementing
hashCode() is not required in this problem set but will
improve performance later on.
Floating point math can cause a lot of problems. The exact value of
Java's double type (double precision floating point number)
can not be guaranteed except within some epsilon. Because of this,
using doubles for the equals() and
hashCode() methods will lead to erroneous results. Do not
use floats or doubles for any computations in
hashCode(), equals(), or any other time exact values
are required. Exact values are not required for length and
distance computations.
Usually (i.e., for this problem set) you don't want to round floating point numbers. To learn how to print a decimal number to the appropriate precision for WalkingRouteFormatter and DrivingRouteFormattero you can read Sun's DecimalFormat tutorial. Tutorials like this one can be found at http://java.sun.com/learning/tutorial.
When implementing GeoPoint.headingTo(), keep in mind that in
the compass headings used in this problem set, north is at 0 degrees
and degrees increase in the clockwise direction. This is different
from mathematical convention in which "east" is 0 degrees and degrees
increase in the counterclockwise direction.
You may find the
Math.round(double) method or the DecimalFormat
class useful. Also see Math.atan2(double,
double) to help with GeoPoint.headingTo().
While writing your tests, you may find the JUnit API documentation useful, especially the Assert class.
Although you shouldn't need it for this problem set, a good introduction to Ant is here and its official website is here.
You may find this data, compiled by Eric G. Tung, useful.
To pass the test cases for directions, you will need to exactly match the format shown in the specification. This includes the number of decimal points and whitespace.
There is version of the assertEquals() method in JUnit's Assert
class that will tell you if two floating point values are equal to
within some epsilon. You will find this helpful when writing your
test cases.
The first error thrown or assertion failed will exit the current method in your test case, so break up your tests into multiple methods.
Keep in mind the difference between specification tests and implementation tests . Although you are not required to write ImplementationTests for this pset, it is strongly encouraged.
This section will list clarifications and answers to common questions about problem sets. We'll try to keep it as up-to-date as possible, so this should be the first place to look (after carefully re-reading the problem set handout and the specifications) when you have a problem.