Problem Set 1: Around the World

To get started,

1. Ask Didit to create a remote psets/ps1 repository for you on Athena.
2. Pull the repo from Athena using Git:

If you need a refresher on how to create, clone, and import your repository, see Problem Set 0.

The theme of this problem set is to build a toolbox of methods for working with geographic points of interest located with latitude and longitude. You can read the Javadoc documentation for all classes in the problem set, generated from the .java source files.

Since we are doing test-first programming, your workflow for each method should be (in this order)…

1. Study the specification of the method carefully.
2. Write JUnit tests for the method according to the spec.
3. Implement the method according to the spec.
4. Revise your implementation and improve your test cases until your implementation passes all your tests.

On Problem Set 0, we graded only your method implementations. On this problem set, we will also grade the tests you write. In particular:

• Your test cases should be chosen using the input/output-space partitioning approach. This approach is explained in the reading about testing.
• Include a comment at the top of each test suite class describing your testing strategy – how you partitioned the input/output space of each method, and then how you decided which test cases to choose for each partition.
• Your test cases should be small and well-chosen. Don’t use a large set of data for each test. Instead, create inputs carefully chosen to test the partition you’re trying to test.
• Your tests should find bugs. We will grade your test cases in part by running them against buggy implementations and seeing if your tests catch the bugs. So consider ways an implementation might inadvertently fail to meet the spec, and choose tests that will expose those bugs.
• Your tests must be legal clients of the spec. We will also run your test cases against legal, variant implementations that still strictly satisfy the specs, and your test cases should not complain for these good implementations. That means that your test cases can’t make extra assumptions that are only true for your own implementation.
• Put each test case in its own JUnit method. This will be far more useful than a single large test method, since it pinpoints where the problem areas lie in the implementation.
• Again, keep your tests small. Don’t use unreasonable amounts of resources (such as MAX_INT size lists). We won’t expect your test suite to catch bugs related to running out of resources; every program fails when it runs out of resources.

You should also keep in mind these facts about specifications:

• Preconditions. Some of the specs have preconditions. Recall from the specs reading that when preconditions are violated by the client, the behavior of the method is completely unspecified.
• Underdetermined postconditions. Some of the specs have underdetermined postconditions, allowing a range of behavior. When you’re implementing such a method, the exact behavior of your method within that range is up to you to decide. When you’re writing a test case for the method, you must allow the implementation you’re testing to have the full range of variation, because otherwise your test case is not a legal client of the spec as required above.

Finally, in order for your overall program to meet the specification of this problem set, you are required to keep some things unchanged:

• Don’t change these classes at all: the classes Angle, CardinalDirection, and PointOfInterest should not be modified at all.
• Don’t change these class names: the classes Angular, Bounds, Search, AngularTest, BoundsTest, and SearchTest must use those names and remain in the geo package.
• Don’t change the method signatures and specifications: The public methods provided for you to implement in Angular, Bounds, Search must use the method signatures and the specifications that we provided.
• Don’t include illegal test cases: the tests you implement in AngularTest, BoundsTest, and SearchTest must respect the specifications that we provided for the methods you are testing.

Aside from these requirements, however, you are free to add new public and private methods and new public or private classes if you wish. In particular, if you wish to write test cases that test a stronger spec than we provide, you should put those tests in a separate JUnit test class, so that we don’t try to run them on staff implementations that only satisfy the weaker spec. We suggest naming those test classes MyAngularTest, MyBoundsTest, MySearchTest, and we suggest putting them in the geo package in the test folder alongside the other JUnit test classes.

In this problem, you will test and implement the methods in Angular.java.

You’ll find Angular.java in the src folder, and a JUnit test class AngularTest.java in the test folder. Separating implementation code from test code is a common practice in development projects. It makes the implementation code easier to understand, uncluttered by tests, and easier to package up for release.

Read the specs. Before you start, read the specs in Angle.java and Angular.java. Since the spec for displacement() includes images, you may find it easier to view the generated Javadoc documentation. You can also play around with latitudes, longitudes, and displacements to understand these specs better.

Test. Create tests for toDegrees() and displacement(), and put them in AngularTest.java. You should partition both functions, write down your partitions in a testing strategy comment, and choose test cases to cover the partitions.

Be careful that your test cases for both methods respect their underdetermined postconditions.

For this problem and all other problems on this problem set, you are free to rename, rewrite, replace, or remove the provided example tests and their assertions.

Commit. Commit your tests for this problem to git, with a good commit message. Committing frequently – whenever you’ve written some tests, fixed a bug, or added a new feature – is a good way to use version control, and will be a good habit to have for your team projects.

Implement. Implement toDegrees() and displacement() in Angular.java. Revise your implementation and your tests until all your tests pass.

Commit and push. Commit again, and this time push your commits to Athena so that Didit can compile them.

Run. You can run Main.java to apply these methods to some example points of interest provided by the staff. Main.java will not be used in grading, and you are free to edit it as you wish.

In this problem, you will test and implement the methods in Bounds.java. The latitudeRange() and longitudeRange() methods find a range of latitudes or longitudes that bound a set of points.

Read the specs. Before you start, read the specs in Bounds.java. You can also play around with latitudes, longitudes, and displacements to understand these specs better.

Test. Create tests for latitudeRange() and longitudeRange(), and put them in BoundsTest.java. Partition both functions, write down your partitions in a testing strategy comment, and choose test cases to cover the partitions.

Writing small helper methods in your test classes can help DRY up the tests, make them easier to read, and prevent copy-and-paste bugs. For helper methods that you add to Bounds, be sure to write specs for them, and remember to test those methods in your own MyBoundsTest class, not in BoundsTest.

For this problem and all other problems on this problem set, you are free to rename, rewrite, replace, or remove the provided example tests and their assertions.

Implement. Implement latitudeRange() and longitudeRange() in Bounds.java. Revise your implementation and your tests until all your tests pass.

Run. Run Main.java to apply these methods to some example points of interest.

In this problem, you will test and implement the methods in Search.java, which we could use to build a search engine from raw point-of-interest data.

Read the specs. Before you start, read the specs in Search.java.

PointOfInterest northPole1 = new PointOfInterest(
                               new Angle(90, 0, 0, CardinalDirection.NORTH),
                               new Angle(0, 0, 0, CardinalDirection.EAST),
                               "North Pole",
                               "admire the aurora borealis");
PointOfInterest northPole2 = new PointOfInterest(
                               new Angle(90, 0, 0, CardinalDirection.NORTH),
                               new Angle(35, 0, 0, CardinalDirection.WEST),
                               "North Pole",
                               "beware the polar bear");

PointOfInterest northPole1 = new PointOfInterest(
                               new Angle(90, 0, 0, CardinalDirection.NORTH),
                               new Angle(0, 0, 0, CardinalDirection.EAST),
                               "North Pole",
                               "admire the aurora borealis");
PointOfInterest northPole2 = new PointOfInterest(
                               new Angle(90, 0, 0, CardinalDirection.NORTH),
                               new Angle(35, 0, 0, CardinalDirection.WEST),
                               "North Pole",
                               "beware the polar bear");

Test. Create tests for reduceDuplicates() and search(), and put them in SearchTest.java. Partition both functions, write down your partitions in a testing strategy comment, and choose test cases to cover the partitions.

As in previous problems, be careful that your test cases for reduceDuplicates() respect its underdetermined postcondition.

Implement. Implement reduceDuplicates() and search() in Search.java. For now, implement only the minimum required behavior for reduceDuplicates(), which infers that two points of interest are duplicates if they have exactly the same latitude, longitude, and name.

Run. Run Main.java to apply these methods to some example points of interest. Edit the file example-points.csv to add, remove, or change the examples.

In this problem, you will implement one additional kind of evidence in reduceDuplicates(). Many companies that provide mapping services do so by aggregating information from multiple sources, and de-duplicating the data is an important problem.

Here are some ideas for evidence of duplication. Feel free to experiment with your own.

• Similar location. Points of interest are not really zero-dimensional points, and different data sources might place them at slightly different locations. So you could implement a tolerance for two locations to be considered close enough. Relating latitude-longitude and physical location is complicated, since the earth is not a sphere, continents drift, etc. As a start, note that one second of longitude equals between 0 and about 100 feet, depending on latitude.

• Similar names. Names with small string edit distance might simply contain typos. Names with larger differences might still point to the same place, for example The Grind Café vs. Cafe Grind. You could be smarter about tolerating differences in names.

• Missing data. Many real-word systems use magic numbers for location when the exact position of a place is unknown. For example, the geographic center of a country or state if that’s all the data source knows; or 0°N 0°E if there’s no information at all. If one point of interest seems to be missing its position in this way, you could consider it as having no information about its position.

Keep in mind that whatever additional evidence you implement, your reduceDuplicates() must still obey the spec. To test your specific implementation, make sure you put test cases in your own MySearchTest class rather than the SearchTest class that we will run against staff implementations. Your work on this problem will be judged by the clarity of the code you wrote to implement it and the test cases you wrote to test it.

Make sure you commit AND push your work to your repository on Athena. We will use the state of your repository on Athena as of 10:00pm on the deadline date. When you git push, the continuous build system attempts to compile your code and run a subset of the autograder tests. You can always review your build results at didit.csail.mit.edu.

Didit feedback is provided on a best-effort basis:

• There is no guarantee that Didit tests will run within any particular timeframe, or at all. If you push code close to the deadline, the large number of submissions will slow the turnaround time before your code is examined.
• If you commit and push right before the deadline, the Didit build does not have to complete in order for that commit to be graded.
• Passing some or all of the public tests on Didit is no guarantee that you will pass the full battery of autograding tests — but failing them is almost sure to mean lost points on the problem set.