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 Husky Maps, a Google Maps-like system for giving directions in the Seattle area. 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 The Ave for two blocks, and another Route traveling down The Ave for three blocks. The GeoFeature representing the path along The Ave in the first Route doesn't need to know or care about the GeoFeature representing the path along The 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 cse331/src directory in your SVN repository. This will create a cse331/src/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 attu. Once everything is in order, commit your changes. You should also run ant validate (on attu) 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 SVN 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, then you will lose points. However,
if your test has identified a real bug in the other
implementation, you will gain points. Likewise if you miss real bugs, allowing
another student's buggy implementation to pass all your tests, you will lose 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 invariant and function (the abstraction) 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.
When it comes time to implement GeoSegment and GeoFeature, you may (and will after reading this) notice that the behavior of getStartHeading() and getEndHeading() for zero length segments is undefined. You are required to write and adhere to a sane specification for these methods. There may be more than one "right" (sane) answer. Pick one and stick to it. See the Implementation Hints for more information about this.
Put the answers to these questions in a plain-text file named answers/problem4.txt and make sure you add it to SVN 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 a TA 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?
@requires gs != null && (gs.p1 = this.end || gs.p2 = this.end)That is, what would the postcondition (the
@return
) be?
Explain in a sentence or two. Is this different precondition stronger
or weaker than the original? Is the new postcondition stronger or weaker?
Explain.
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 8pm, April 28. Returnin will be enabled at 8pm, April 21.
You will only receive credit if you pass all the tests, and you have a fixed number of trials without penalty. See the returnin331 documentation for details.
See the problem set guidelines and advice.
You don't need to check the "nearby Seattle" precondition. How close to Seattle 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()
.
Note that 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
GeoSegment
s 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
GeoSegment
s. 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 GeoSegment
s.
Document the choices you have made in your implementation (again, as
part of Problem 4.1). If you wish, you may 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.)
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.
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.
Note that tests of getHeading()
on zero-length GeoSegments
and friends should not be specification tests. Again, if you
don't know why, please review
the difference between the two varieties of tests.
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.