| 6.170 | Laboratory in Software Engineering Spring 2004 Problem Set 3: Implementing Routes and Cars Due: Thursday, February 26, 2004 at 9pm |
Quick links:
We recommend that you read the entire problem set before you begin work.
When you complete the assignment, make sure to log onto athena and
run:
athena% validate6170 ps3
Read the output message carefully!
In problem set 3, you will build data abstractions that represent routes between two geographic points in the real world and cars travelling along routes. In problem set 4, you will implement a generic graph datatype and a generic pipe-and-filter simulator. In problem set 5, you will implement data types to represent the behavior of parts of the road system, such as stop signs and traffic lights, and integrate these with your generic simulator from problem set 4. Finally, in problem set 6, you will integrate all of these parts to build a working system that simulates the behavior of traffic in Boston and Cambridge.
This problem set primarily concerns two data types: routes and cars.
A Route is an ordered sequence
of steps that, collectively, take you from one location to another. A
Route follows any number of streets, such as starting on
Massachusetts Avenue in Boston, then turning east on Main Street to
visit
Technology Square. The atomic steps of a
Route are called RoadSegments. Their endpoints are
GeoPoints, which represent locations on the earth.
A Car represents a
vehicle driving along a Route.
A Car has a current speed
and a current position along its route. A Car drives along its route,
step by step, until it reaches the end of the route.
Because the classes you define in this problem set will be used in later problem sets to complete the Traffic system, it is important to consider how they will fit in while implementing them. There will be many Cars in the traffic simulator, each moving on an individual Route around the road system. Try to find efficient, O(1) implementations of Car's methods.
Make sure you have followed the instructions on the tools handout relevant to
intitial setup before you
begin development. Furthermore, be sure you have read the
You can get the source files for problem set 3 by using CVS. Follow
the problem set checkout
instructions and checkout the Your code MUST work on Athena, so if you choose to work on a
non-Athena machine, please take a few minutes before submitting your
solution to ensure that it runs correctly on Athena. Once everything
is in order, read the
problem set
submission instructions for how to run a final check of your code
and turn it in.
You should use JUnit as you did for problem sets 1 and 2. We have
provided a RoadSegmentTest class to test your implementation
of RoadSegment, and a GeoPointTest class to test
your implementation of GeoPoint. RoadSegmentTest
requires that you have a GeoPoint implemented, but does not
exhaustively test GeoPoints. You should create two new
classes RouteTest and CarTest to test your
implementation of Route and Car. The validation
and autograding scripts will be looking specifically for these
classes. Please make sure to add all new files that you create to CVS!
While
writing your tests, you may find the JUnit API documentation useful,
especially the Assert
class.
You may also find the following site useful: Maps On Us. This site
allows you to locate the coordinates, in degrees, of points in the
US. Use the menu to locate a map of an address, and then click on that
map to get the coordinates of the center. These coordinates will be
displayed at the bottom of the image. Implement the classes in the provided specification. The
specification is available in HTML
form, or as individual Java
files. To complete your implementation you may add private fields
and methods to the skeleton classes. You may also add and modify
import statements at the beginning of each file.
You may find it easiest to implement the classes in the following
order: GeoPoint, RoadSegment, Route, Car. You should run the tests you wrote in Problem 1
as you program and evaluate your progress and the correctness of your
code. For each class, remember to write a proper abstraction function and
representation invariant as a comment in your code. You should also
implement a checkRep() method. This will help in finding errors in
your implementation.
Doubles and floating point math can cause a lot of problems. The
exact value of a double can not be guaranteed except within some
epsilon. Because of this using doubles for the equals and
hashCode methods can have 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.) Because
of this, you should consider using ints for your internal
representation of GeoPoint.
1. In implementing Route, you
chose a representation: that is, an implementation of the inner
structure of the object using fields of particular types. Describe
your choice of implementation, and a different choice that you might
have made, in a few sentences. Give a scenario where your choice of
implementation is superior, and give a scenario where your choice of
implementation is inferior.
2. Route.addSegment() requires the RoadSegment
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?
3. Suppose you construct two Routes consisting of the same RoadSegments. Should the Routes be judged equal by their
equals method? Why
or why not? 4. Suppose you construct two Cars with the same name, color,
and Route, and test them
for equality immediately using the equals method. Should the
Cars be judged equal by
their equals
method? Why or why not?
To receive full credit, your program will need to pass all your
test cases and all of the staff's test cases. In the Testing section
of your documentation, indicate whether you passed all of your own and
the staff tests. If your code fails any of these tests, indicate which
ones and why they are failing.ps3 module from your
repository.
Problems
Problem 1: Test Cases (20 points)
Before you begin coding, you should prepare black-box test cases for
all your classes. You should base your tests on the specifications
that we provided. The specification is available in HTML form, or as individual Java files. (You might want
to read the specification
handout for more information about the format of our
specifications.)
Problem 2: Implementation (45 points)
Problem 3: Documentation (35 points)
The documentation for this problem set will be a smaller version of
what will be expected for later problem sets. You will submit
electronic versions of your documentation alongside your source, in a
plain text file called ps3.txt.
Requirements
The purpose of this section is for you to explain all of the
assumptions your program makes. This includes specifying what the
desired input and output are. For this problem set, we have specified
all of the inputs and outputs for your program in the specifications
we provided. If there is anything which you found unclear in the
specifications, please state what assumptions you had to make, and
clarify the problem. If you found nothing unclear, then you may simply
write "No clarification necessary."
Design
In future problem sets, you will be asked to give a detailed account
of the design decisions you made in your program. For this problem
set, we only ask you to answer four questions about the design of a
few classes: @requires gs != null && (gs.p1 == this.end || gs.p2 == this.end)
Testing
Briefly discuss your testing strategy. Do you consider
your tests to be sufficient
without being excessive? Why? Did you depend on the results from previous
unit tests to design later unit tests? If so, how did you depend on or
re-use these previous tests?
Analysis
In a paragraph or two explain what you regarded as the successes and
failures of the development: unresolved design problems, performance
problems, etc. Also describe what lessons you learned from the
experience, how you might do it differently a second time around and
how the faults of the design and implementation may be corrected.
What to Turnin
You should commit the following files to your CVS repository:
GeoPoint.java
RoadSegment.java
Route.java
Car.java
CarTest.java
RouteTest.java
ps3.txt
JUnit is integrated with Eclipse, so you can run the test suite from within the IDE as you did in the previous problem sets.
RoadSegment,
you should select RoadSegmentTest from the ps3 classes.Since you are going to develop multiple test files to test all your data types, you may want to run all the tests in your project at once. To do this,
If you are not using Eclipse, you can invoke JUnit from the command
line. To run the RoadSegmentTest test suite, type the following
command:
athena% java junit.swingui.TestRunner ps2.RoadSegmentTest
For a non-graphical alternative method of running JUnit, use junit.textui.TestRunner
instead of junit.swingui.TestRunner.
Remember that in order for this to work, junit.jar and
the directory containing your class files must all be in the Java VM's
classpath (i.e. part of the CLASSPATH environment variable or you may
need to explicity use the -classpath parameter for the
Java VM).
Since you are going to develop multiple test files to test all your data types, you may want to run all the tests in your project at once. To do this, type the following command:
athena% ant testAnt will automatically find all files ending with
*Test.java and
run the test suits defined within. The output of each test will be printed on
standard output.
When asked to return an Iterator,
consider using the iterator()
method in the List
interface. Two nice classes that
implement the List interface are ArrayList
and
LinkedList.
Be careful, however! The iterators returned by these classes implement
the remove() method, which may
lead to rep exposure if you're not careful.
Do not bother to check the "nearby Boston" preconditions. 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.
You may wish to use points in the real world to sanity-check your
code. Maps On Us
allows you to locate the coordinates, in degrees, of points in the
US. Use the menu to locate a map of an address, and then click on that
map to get the coordinates of the center. These coordinates will be
displayed at the bottom of the image.
This list of MIT campus locations,
contributed by Eric G Tung may also be helpful for testing.
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 at this point, but will improve performance later on.
See Math.atan2(double, double) to help with GeoPoint.headingTo(). Keep in mind that in our coordinate system, north is 0 degrees and degrees increase in the clockwise direction. By mathematical convention, however, "east" is 0 degrees, and degrees increase in the counterclockwise direction.
Car.drive has an error in
its modifies clause. The specification reads:@modifies this.fraction this.location@modifies this.fractionCar used to have a derived field, location, which
we removed).
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.