Handout P2

Quick links:

• Specifications: HTML Documentation, Starter code
• Provided source code
• Problem Set Submission

• Purpose
• Preamble
• Getting Started
• Problems
  • Problem 1: Implementation (40 points)
  • Problem 2: Testing (15 points)
  • Problem 3: Documentation (20 points)
    • Requirements
    • Design
    • Testing
    • Analysis
  • Returnin (25 points)
  • What to Turnin
• Hints
• Errata
• Q & A

We recommend that you read the entire problem set before you begin work.

Purpose

Preamble

In problem set 2, 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. 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 atomic steps are called GeoSegments. Their endpoints are GeoPoints, which represent locations on the earth. There are two different types of Routes. An ElementaryRoute follows a single geographic feature, possibly for many GeoSegments; for instance, it might represent the path of Massachusetts Avenue from Boston, through Cambridge, to Arlington. A CompositeRoute follows any number of geographic features, such as starting on Massachusetts Avenue in Boston, then turning east on Main Street to visit Technology Square.

Because the classes you define in this problem set will be used in later problem sets to complete the MapQuick system, it is important to consider how they will fit in while implementing them. CompositeRoute is used very extensively in the shortest path algorithm. Basically, the path finder will create new CompositeRoutes by adding segments to them, and it will also use the old ones. There may be a lot of them in memory at a time too. Try to find an efficient implementation of the CompositeRoute.addSegment method.

Getting Started

mkdir ~/6.170/ps2
cp -p /mit/6.170/www/psets/ps2/ps2-spec/* ~/6.170/ps2

See the Specifications handout for a more detailed description of how to read 6.170 specifications.

Problems

All work must be your own. you are permitted to discuss only background material. You should not discuss the problems or their solution. Do not refer to work or problem sets/solutions from previous terms ("bibles"). See the General Info Handout for details.

All code must be submitted both electronically as well as in hard copy. All documentation must be submitted in hardcopy, and may be submitted electronically as well. To submit files electronically, see the Problem Set Submission handout.

For this problem set only, you may add protected (as well as private) fields, methods, or constructors to the classes.

Problem 1: Implementation (40 points)

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.

Do not round numbers internally; they should only be rounded for the output of the directions method. Reporting a distance of 0.0 miles is acceptable. You may find the Math.round(double) method useful. Or not. Also see Math.atan2(double, double).

Problem 2: Testing (15 points)

While writing your tests, you may find the JUnit API documentation useful, especially the Assert class.

We have provided a test suite in PublicTest.java. This test suite uses the provided GeoSegmentTest class to test your implementation of GeoSegment. It also requires that you have a GeoPoint implemented, but does not exhaustively test GeoPoints. You should create new classes like GeoSegmentTest to test the remaining classes. Augment PublicTest to use your classes. You can run the given test suite with JUnit as you program and evaluate your progress and the correctness of your code.

To run the test suite, type the following command:

athena% java junit.swingui.TestRunner ps2.PublicTest

athena% java junit.textui.TestRunner ps2.PublicTest

Problem 3: Documentation (20 points)

Requirements

Design

In implementing CompositeRoute, 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 text (as a few sentences). Give one reason why your choice is preferable.

ElementaryRoute.addSegment() and CompositeRoute.addSegment() require the GeoSegment argument to be properly oriented (with respect to which end is p1 and which end is p2). If this precondition were eliminated, how would the implementation of these classes and their clients change? Explain this in a sentence or two.

Testing

To receive full credit, your program will need to pass all test your cases (as well as all of the staff's), but if there are any known cases where your program fails, please indicate what these are.

Analysis

Returnin (25 points)

The due date for the returnin of this problem set is 11:59pm on Tuesday, March 20th.

What to Turnin

CompositeRoute.java
ElementaryRoute.java
GeoPoint.java
GeoSegment.java
Route.java
problem3.txt or problem3.pdf

You should also turnin a hardcopy of each of these files.

Hints

For abstract classes, you may or may not have work to do. You may make any method of an abstract class abstract as well, at your discretion. If all methods are abstract, it's enough to put the provided code in an appropriately-named file (and adjust the declarations), in which case subclasses must implement the methods. Alternately, you might wish to implement some of the methods in the abstract class, so that you don't have to duplicate work in multiple subclasses.

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. The Eagle Geocoder and MapBlast convert addresses into latitudes and longitudes.

For some methods, you are asked to return an array. You may find the java.util.Vector.toArray method 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, whitespace etc.

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).

When implementing GeoPoint.headingTo, keep in mind that in our coordinate system, north is 0 degrees and degrees increase in the clockwise direction. In math, east is 0 degrees, with degrees increasing in the counterclockwise direction.

Errata

Sunday, February 17, 2001

Important changes:

• The specifications for the directions(double) method in both Route and ElementaryRoute have been rewritten to clarify their intended behavior.
• The specifications for the equals(Object) method in the Route, ElementaryRoute, and CompositeRoute classes have been rewritten to clarify their intent.
• We have added two new tests to the GeoSegmentTest tester. The first new test, named testEquals2, ensures that GeoSegment.equals checks value equality (as opposed to reference equality), and that the method does not make assumptions about its argument. The second test, testHashCode, tests that equal objects have the same hashCode.

Clarifications and typographical fixes:

• We have edited the first paragraph of the hints section to improve its relevance.
• We have removed the specification field cost from the CompositeRoute and GeoSegment classes. The field was never used in the description of the classes' behavior, so its removal does not affect your implementation.
• We have added a requires clause to the ElementaryRoute constructor which states that the argument may not be null.
• We have fixed the output of the GeoSegmentTest tester. Previously, the values given for "expected" and "actual" results were switched in the output.
• We neglected to provide you with a starter Manifest file. You may copy the starter Manifest now with this command:

  cp /mit/6.170/www/psets/ps2/ps2-spec/Manifest ~/6.170/ps2
  

Q & A

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.

Tuesday, February 20, 2001

Q: If I have two ElementaryRoutes with the same name, are they .equals() to each other?

A: Not necessarily. For two objects to be .equals() they must have the same values for all specification fields. This includes those inherited from their superclass, which is in this case Route.

Monday, February 19, 2001

Q: Can I add protected methods to my class? It would make my code a lot more clear.

A: Yes, for this problem set only, you may add protected fields, methods, or constructors to the classes. This does change the spec, but in a limited way. You should think about what the tradeoffs are in allowing this, and why we've decided to allow it for this problem set.