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 exercise 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.
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.
We plan to run each student's SpecificationTests
against each other
student's assignment; how you fare will determine part of your grade. For
instance, suppose that another student's code fails one of your tests. If
your test contradicts the specification, or if you miss real bugs, then you
will lose points. If your test has identified a real bug in the other
implementation, you will gain points. (It would not make sense for us to
do this cross-checking with ImplementationTests. If you
don't know why,
please review
the difference between the two varieties of tests until you
understand this point.)
Create the representation and abstraction function for each of the
non-test classes and 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.
It is easy to overlook a test that would assist you. Sometimes, tools can assist you. One such tool is Daikon, which you learned about in the Problem Set 1. (Time permitting, we may introduce other such tools.)
GeoSegment, GeoFeature, or Route). Compare your representation invariants to the
CLASS and OBJECT invariants that Daikon reports for
the class you have chosen. Does Daikon indicate anything that you forgot?
For instance, perhaps Daikon reports that a parameter or field must be
non-null, or perhaps it indicates some other relationship that is missing
from your representation invariant.
If so, write it in the answers/problem4.txt file (you won't lose any points for doing
so; the purpose is to help you!) and correct your code documentation.
If not, explain why Daikon was not helpful in this regard.
Compare Daikon's output to the written specs for some of the methods and constructors of the class you are examining. Recall that Daikon performs generalization (machine learning) over the values that your program computes, such as arguments a method is passed or return values. Find one property in Daikon's output that differs from your specification, where that difference indicates a deficient test suite.
Here is an example that you might have noticed from Problem Set 1:
numerator >= -1
This indicates that the test suite you were given is deficient: it never tested values like -2/3 (where the numerator is -2) and -3141592/3141593 (where the numerator is -3141592), though it did test values like -1/4, 2/3, and 271828/271829.
Copy the property that you found to your answers file (don't forget to indicate what class and method it is over). Now, add tests to your test suite to eliminate that spurious output. Copy those tests to your answers file (just the new ones), and explain why they eliminated the undesirable output.
It is highly unlikely that your tests are so good that Daikon does not find some deficiency in them. If you can't find one, ask an LA to help you examine the output.
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.
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 Friday, March 17, 2006 at 9pm. Returnin will be enabled at 9pm, March 10.
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.
When asked to return an Iterator<E>, consider using the iterator() method in the List interface. Two nice classes that implement the List interface are ArrayList and LinkedList.
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.
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().
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.
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.
GeoSegment.getHeading's behavior for zero-length
segments (where GeoSegment.p1.equals(GeoSegment.p2)) is
deliberately unspecified, as the @requires clause
indicates. Unfortunately, this means that the behavior of
GeoFeature.getStartHeading(),
GeoFeature.getEndHeading(),
Route.getStartHeading(), and
Route.getEndHeading() are not well-defined.
Please write reasonable specifications to clarify these cases, and
document it in Javadoc and in Problem 4.1. Note that zero-length
GeoSegments are not illegal. [The only APIs you
should alter should be for GeoFeature.getStartHeading(),
GeoFeature.getEndHeading(),
Route.getStartHeading(), and
Route.getEndHeading(); this is a special
exception to our usual policy that provided APIs should never be
changed.]
The @requires clause in
GeoSegment.getHeading() (and potentially, the
specification you wrote for
GeoFeature.getStartHeading() and friends)
gives you (as implementor)
flexibility with regard to how your code handles zero-length
GeoSegments. Remember, your code is allowed to do
absolutely anything when presented with inputs which violate the
@requires clause. Your actual implementation will
conform to a stronger specification which chooses one particular
behavior when given a zero-length GeoSegments.
Document the choices you have made in your implementation (again, as
part of Problem 4.1), and add tests to ImplementationTests
to verify that your code behaves as you expect. Do not
change the public APIs of methods to document your implementation
choices—this would expose your implementation and prevent
other implementers (including your future self) from making
different choices. You may wish to add non-Javadoc comments. (For
your own edification, consider how the use of interfaces rather than
classes could help avoid this confusion between specification and
privately-documented implemented behavior.)
The specification for GeoPoint we provided you
@requires that all latitude and longitude values must
near Boston. However, the test cases
WalkingRouteFormatterTest and
DrivingRouteFormatterTest violate this precondition by
using values that are not. We have strengthened the specification
for GeoPoint in the online Javadocs so that it now must be able to
represent any valid latitude and longitude values.
You are required to use the flat-surface assumption throughout this
problem set. The online Javadocs for GeoPoint.distanceTo()
and the GeoSegment class have
been updated to reflect this. Previously
GeoPoint.distanceTo() permitted but didn't require the
flat-earth assumption, and GeoSegment didn't address it
one way or the other.
The specifications for Route.addSegment()
and GeoFeature.getGeoSegments()
incorrectly used '==' instead of '=' (denoting mathematical equality).
The online Javadocs have been corrected.
Similarly, problem 4.3b in this problem set also used '==' instead of '='; it has been corrected above.
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 rereading the problem set handout and the specifications) when you have a problem.