Handout P2

Quick links:

Contents:

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

Introduction

This assignment continues our focus on writing code that satisfies a given specification. You will submit your code, a suite of test cases, documentation, and answers to several questions.

Some of you will also use type-checking to prevent null pointer exceptions, because it is better to detect a bug at compile time than at run time.

Problem sets 2 through 6 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 ps2, 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.

Data structures

A route is an ordered sequence of steps that take you from one location to another. In this assignment, routes are represent as the following classes:

A GeoFeature represents part of some path along a single geographic feature: 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:

Getting Started

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. Use the provided specifications to help you fill in the missing methods.

Once everything is in order, commit your changes. You should also run ant validate (on attu) as a double-check after committing.

Provided code

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 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; the quality of the tests is important.

By the end of the problem set, you should have the following files committed to SVN in your ps2 directory:

Problems

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.

Problem 0: Setup (1 point)

Add the following line to your ~/.bashrc file: 

  export CHECKERS="/cse/courses/cse331/checkers"

After modifying your .bashrc file, you will need to re-login for the changes to take effect.

Problem 1: Testing (21 points)

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.

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.

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

Problem 2: Representation (21 points)

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. Insert calls to your checkRep() method in the appropriate methods.

Problem 3: Implementation (21 points)

Implement the methods defined in the skeleton classes. The provided Javadocs are identical to the ones in the classes themselves. The specification handout has more info about the format of our specifications.

When implementing GeoSegment and GeoFeature, note 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. There are even more "wrong" (insane) answers that make no sense in the real world and/or in your implementation. See the Implementation Hints for more information about this.

Preventing null pointer errors via type-checking

It is better to detect a bug at compile time than at run time. Java's type system prevents some errors, but permits others to persist until run time, such as null pointer errors. Some of you will get the opportunity to use a type-checking tool that prevents null pointer errors at compile time. That set of students is randomly chosen. The other students will get a different opportunity later in the quarter. To determine if you will be using the special type-checker on this problem set, do the following:

In the ps2/ directory of your working copy, run the command ant build on attu. This will kick off your build as normal, but it will also output one of two new messages:

The second message indicates that you will be using the special type-checker.

If you are not using the special type-checker, then you may proceed to Problem 4.

If you are using the special type-checker, called the Nullness Checker, then here are some more details. Using the Nullness Checker, you will strengthen your understanding of type systems, and come to appreciate the strengths and weaknesses of ones that are stronger than Java's. You will be exposed to a cutting-edge research tool and will get an early view of (one aspect of) the future evolution of the Java language. And, you may avoid some errors that would otherwise cost you points on your problem set.

Your goal is to eliminate all possible null pointer errors from your code. You will write /*@Nullable*/ to indicate which variable might be null; you may also use other annotations supported by the Nullness Checker, if needed. Then, you will run the Nullness Checker. The Nullness Checker will warn you about places where the annotations are incorrect, or where a null pointer exception may occur. When you hand in your code, the Nullness Checker should issue no errors, and ant validate will check this.

You do not have to do anything special to run the Nullness Checker; it will be run automatically whenever you compile your code using the Ant target. Eclipse, on the other hand, will ignore the annotations you write. Therefore, you should either compile frequently using the Ant target, or you should use the Eclipse plugin for the Checker Framework. The plugin gives you the ability to run the Nullness Checker directly from Eclipse, rather than having to compile via Ant.

You need to add just the right number of annotations. The final annotations must be consistent with one another — for example, a possibly-null value must never be assigned to a non-null variable. The annotations must also be consistent with your code: any dereference such as x.field or x.method() may only be performed on a non-null variable. If you add too many or too few annotations, then one or the other of these properties will be violated, and the Nullness Checker will issue an error.

Before starting to implement PS2, read the CSE 331 Checker Framework handout, and also the relevant portions of the Checker Framework manual that are referenced from that handout.

Problem 4: Questions (12 points)

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

1. Assumptions

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.

2. Improving your tests

It is easy to overlook a test that would assist you. Sometimes, tools can assist you. One such tool is Daikon. (Time permitting, we may introduce other such tools.)

  1. Run Daikon on your problem set using ant daikon. (Don't do this until ant test passes without any errors!)

    Examine the output for a class for which you wrote tests (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.

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

  3. Every tool has its strong and weak points. Explain (in 2-5 sentences total) in what ways Daikon was helpful in improving your specification and code, and in what ways it could be further improved to be more helpful. Give an example of an inaccurate Daikon property which is not easily fixed by adding more tests.

3. Design

  1. In implementing Route and GeoFeature, you chose a representation for each class: an implementation of the abstract specification using fields of particular types. In a few sentences, describe your choice of implementation for each class and a different choice that you might have made. Give a scenario where your choice of implementation is superior and a scenario where your choice is inferior. Here is an example: a graph could be represented by a vertex connectivity matrix, a VxV array; a list of edges, with an E-length array storing the 2 vertices of each edge; as a list of nodes, each of which has a list of adjacent nodes; and in many other manners. Give similar alternatives for the classes you implemented. Do not simply suggest replacing one implementation of List by another (say, LinkedList by ArrayList). We are looking for a change of representation that is more significant than that.
  2. 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.
  3. Using the concept of behavioral subtypes discussed in class, explain why Route is not a true subtype of GeoFeature and why GeoFeature is not a true subtype of Route.
  4. Describe a format for printing a Route that would be easy to implement within the RouteFormatter hierarchy (e.g., something that could easily be written as a subclass of RouteFormatter). Describe another format that would be difficult to implement within this hierarchy.

4. Postmortem

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.

Reflection (1 point)

Please answer the following questions in a file named reflection.txt in your answers/ directory.

  1. How many hours did you spend on each problem of this problem set? (Only include time when you are completely focused on CSE 331. For example, if you worked an hour in your noisy dorm lounge, or you were periodically reading email or IMs, don't count that hour.)
  2. In retrospect, how could you have reduced the time you spent solving this problem set?
  3. What could the CSE 331 staff have done to improve your learning experience in this problem set?
  4. What do you know now that you wish you had known before beginning the problem set?

Collaboration (1 point)

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.

Returnin (25 points)

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 February 9, 8pm Returnin will be enabled at 8pm, February 2.

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.

Implementation Hints

Miscellaneous

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). 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 DrivingRouteFormatter you can read Sun's DecimalFormat tutorial. Tutorials like this one can be found at http://java.sun.com/learning/tutorial.

GeoPoint Headings

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

GeoSegment Headings

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

Testing hints

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 you may want to 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.

If your implementation fails a test, and you can't figure out why (or you think there is a bug in the staff tests), then convert the degrees to miles using the static constants in GeoPoint and draw a picture of the tests. And, see the hints about headings.

Errata

None yet.

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 re-reading the problem set handout and the specifications) when you have a problem.