| 6.170 | Laboratory in Software Engineering
Spring 2001 Problem Set 4: Designing and Implementing Street Segments Due: Monday, March 12, 2001 at 5pm |
Quick links:
We recommend that you read the entire problem set before you begin work.
In this problem set, you will design and implement abstract data types for representing streets (StreetSegment and StreetNumberSet), you will read commands from a file to join these street segments into a graph, and you will create a new variety of Path that enables your previous PathFinder implementation to be used, without change, to find paths along streets. When you finish this problem set, you will have a complete, albeit rudimentary, version of MapQuick that can print directions between specified street segments. (In problem set 6 (problem set 5 will not include any programming), you will construct the street graph from the US Census Bureau database, look up which street segment contains a given address, refine the directions-finding algorithm, and provide a user interface.)
The StreetSegment class which you will define in this problem set builds on GeoSegment, adding some new functionality. Among other things, each StreetSegment has associated with it certain StreetNumberSet objects that indicate which addresses (building numbers) appear on the Segment. StreetNumberSet can be queried to see where a particular building number appears (for instance, how far from one end of the street that building stands).
This problem set requires you to do a fair amount of design. (Writing code to a careful specification is fairly easy; writing code to an incomplete specification is harder; and writing a specification is hardest of all. However, it can also be much more interesting, and MIT students are expected to be able to handle difficult problems, not just easy ones.) When you select a design, you should first sketch out the design space. Brainstorm all the different ways you might imagine satisfying the specification. (Some of these might seem silly, but don't reject them out of hand -- at least, not yet.) Almost every set of requirements has multiple designs with different properties, and the ones we give you are no exception. When you write up your design, talk about different designs, tradeoffs they make, in what circumstances each is good, and why you chose the one you did. There is no one correct answer, no one "perfect" design that the 6.170 staff is waiting for you to discover. Rather, we want you to think about the problem, consider the alternatives, and make a cogent case for the one that you choose.
A substantial part of your grade will be based on your writeup. (Your code makes up a minority of the points for this submission. Documentation, analysis, testing, and so forth are also important; in fact, code lacking those artifacts is generally useless, as it can't be reused, safely modified, or even understood.)
In Problem Set 2, you implemented GeoSegment, a class that represents a generic connection between two points on the surface of the earth. This problem set will ask you to extend GeoSegment to design and implement a StreetSegment representing a street in the real world.
Consider the following segment of a fictitious street:
Note that one side of the street is in Somerville, and the other is in Medford. The two sides of the street have disjoint numbers, as well as different ZIP codes. The street also has a classification: it is a local road. For street segments, we will only have four possible classifications: primary highway, secondary highway, local road, and unknown.
A typical street has even street numbers on one side and odd street numbers on the other side, and each side contains all of the (even or odd) street numbers in a range. However, this is not the case for all streets: one side of a street may contain both odd and even numbers and/or be missing some numbers in a range. For example, one side of a street might contain 2, 4, 6, 8, 10, 12, 14, 17, 18, 20, and 22.
StreetNumberSet represents an arbitrary set of integers, but should be optimized for memory usage when used to store street numbers. One useful observation about street number sets is that they often contain long sequences of same-parity numbers. For example, the sequence above contains even numbers from 2-14 and 18-22, and the odd number 17. More common cases will be a single range, such as even numbers from 22-140, or the empty set. For the purpose of storage space optimizations, you may assume that an input string like "1-3,5-7,9-11" is uncommon, and would instead be given as "1-11".
We do not provide you with a specification for StreetNumberSet. However, we require you to provide a specific public constructor and two methods, contains and orderStatistic, along with any others of your devising. The contains and orderStatistic methods will be needed in problem set 6; although they are not used in this problem set, you should still fully specify, document, and test them.
After testing, you may disable (e.g. comment out) any checkRep() calls if they create a severe and measurable performance hit. We still need to be able to see where you would have placed your calls, but if your program is unbearably slow, you may disable the checks. (Note, though, that if your ADT is not calling checkRep() for certain methods, then the test driver should call checkRep() while testing those methods because during testing, correctness is generally more important than speed.)
Your README file should state in which turned-in file each part of this problem can be found.
We do not provide you with a specification for StreetSegment. However, we require you to provide a specific public constructor, and a fractionDist method. We also recommend that you implement a reverse method which overrides GeoSegment.reverse, as you will need that method in problem set 6.
As you did for StreetNumberSet, complete the specification, testing, documentation, and implementation of StreetSegment.
Your README file should state in which turned-in file each part of this problem can be found.
Hints:
The elements in the CompositeRoutePath are GeoSegments, so the extend(Object) method should expect a GeoSegment as its argument, and the elements() method should return an Iterator whose elements are GeoSegments.
In the full MapQuick system of problem set 6, you will be using your PathFinder (from problem set 3) to find and return CompositeRoutePaths. You will need a way to take a CompositeRoutePath and produce directions from it. Be sure to consider this usage while designing your CompositeRoutePath.
The search algorithm of problem set 3 works not only if paths are sorted (in the priority queue) by their lengths so far, but also if paths are sorted by any value that is at least as large as the length of the path so far and no greater than the true total length of the path once it is extended to the goal. In other words, it works to use not the cost of the path so far, but an underestimate of the total cost of any goal-reaching path with the given path as a prefix. One simple way to do this is to add, to the length so far, the straight-line distance to the goal. (When there are multiple goals, choose the minimum straight-line distance to any of the goals.) Since any real path to the goal is at least as long as the straight-line distance, the this value falls between the distance so far and the actual distance.
For more details about A* search, see Artificial Intelligence, Third Edition, by Patrick Winston.
You can implement this heuristic very simply: instead of using the route length as the cost of the path, your CompositeRoutePath defines its cost to be the sum of the route length so far plus the distance remaining to the nearest goal. Note that this heuristic requires no changes to PathFinder; it is just an efficient definition of the cost function.
You should create a class named PS4TestDriver which runs tests in the same way that PS3TestDriver did in the last problem set. You have two choices as to your approach:
As one option, you may copy your ~/6.170/ps3/PS3TestDriver.java source file to ~/6.170/ps4/PS4TestDriver.java, change it to package ps4, and revise it to match this problem set's file format specification. This will cause duplicated code, between the two problem sets, but avoids some of the trick issues with subclassing.
Alternatively, you may choose to write a new PS4TestDriver class which extends the PS3TestDriver and reuses some of its code. Depending on the extensibility of your PS3TestDriver implementation, this approach may or may not be easier. (You may go back and edit your PS3TestDriver to make it more extensible, if you wish, as long as the PS3TestDriver still meets the requirements for ps3.)
In order to make PS3TestDriver more extensible, you will need to make some of its methods protected instead of private. Also, static methods may not have the inheritance properties you want. You may find it easiest to just copy the main method from PS3TestDriver, and change the references from PS3 to PS4. For a deeper understanding of inheritance and static methods, refer to the Java Q & A. (As of the time this problem set was posted, the Q & A does not yet have this information. Watch for an update soon.)
Once your test driver is ready, you should create one or more sets of
test cases, in files named
ps4*.test and provide their expected output in
ps4*.expected. In a separate file, include an
explanation your testing strategy and an argument for why you feel
that your tests are sufficient, but not excessive.
See the sample test section for an example of a test file.
Your README file should state in which turned-in file each part of this problem can be found.
README StreetNumberSet.java StreetSegment.java CompositeRoutePath.java PS4TestDriver.java [non-code files for problem 1] [non-code files for problem 2] [non-code files for problem 3]
You should also turnin a hardcopy of each of these files.
Each input file has one command per line, and each command consists of whitespace-separated words, the first of which is the command name and the remainder of which are arguments. Lines starting with # are considered comment lines and should be echoed to the output when running the test script. Lines which are blank should cause a blank line being printed to the output.
The test driver manages a collection of named Graphs; graph nodes are GeoSegments. Each GeoSegment is given a unique name to permit them to be connected to one another. Names of nodes and graphs contain only alphanumeric characters.
The following is a list of the valid commands, and the meaning of their arguments. The commands are similar to problem set 3, with the following exceptions: CreateNode is removed and replaced with CreateGeoNode; FindPath is removed and replaced with FindGeoPath; ListNodes and ListChildren are removed. (Therefore, CreateGraph, AddNode, and AddEdge are the same.) Each command has an associated output which should be printed to standard out.
CreateGraph graphName
Creates a new graph which shall be named
graphName. The graph is initially empty (has no nodes
and no edges). The command's output is
created graph graphName
CreateGeoNode nodeName lat1 long1 lat2 long2 segName
Creates a new GeoSegment with the specified arguments (the latitudes and
longitudes are in millionths of a degree), names it by nodeName, and
adds it to the graph. The node can be referred to by nodeName for the rest of the file.
The command's output is
created node nodeName: lat1 long1 lat2 long2 segName
AddNode graphName nodeName
Adds a node identified by the string nodeName to the graph named
graphName. The command's output is
added node nodeName to graphName
AddEdge graphName parentNode childNode
Creates an edge in graph graphName from
parentNode to childNode.
The command's output is
added edge from parentNode to childNode in graphNode
FindGeoPath graphName from1 [from2 [from3 ... ] ] -> to1 [ to2 [ to3 ... ] ]
Finds the shortest path amongst all of the possible paths from any of the
from nodes to any of the to nodes. The command's output starts with
shortest path in graphNameon a line by itself. Then the path should be printed according to the specification of Route.directions, using an using an initial heading of zero (0.0). If no path exists the standard prefix should be followed (on a separate line) by
no path found
The behavior of the testing driver on malformed input files is not defined; you may assume the input files are well-formed.
The expected output is posted in /mit/6.170/www/psets/ps4/campus.expected.
Then, write your implementation in that directory.mkdir ~/6.170/ps4 cp -p /mit/6.170/www/psets/ps4/ps4-spec/* ~/6.170/ps4
See the HTML specifications for the classes you will implement and those that are provided for you.
We recommend that you design all the classes first, rather than going class-by-class doing design, specification, testing, documentation, and implementation; similarly, you may find it helpful to write all the specifications before doing any testing or implementation, because you may find while writing the specifications that you need to make changes to your documentation.
You will need to implement the equals(Object) method for a number of classes. When you override Object.equals(Object), you usually need to override Object.hashCode() as well.
Because StreetNumberSet models a set, it should not contain duplicate street numbers.
You should not need to modify your PathFinder or Graph implementations. (In particular, they should not mention WeightedNode, StreetSegment, or the like. If you made an implementation error by including such references, remove them, but ensure that your PathFinder and Graph classes continue to work for problem set 3 as well as for problem set 4; both problem sets should use the same version of those classes.
For inspiration on how to incorporate the A* heuristic into your CompositeRoutePath without modifying PathFinder or the signature of the cost() method, you should read section 15.4 of the Liskov text, paying special attention to the clever trick involving "closures."
Abstraction functions and representation invariants are covered in lecture during the first week of March, and in the book reading you did before lecture on Tuesday, February 27.
This section details the changes made since the handout was posted to the website. You may use the version number at the bottom of your hardcopy to determine what has changed since you printed this handout.
| revision 1.65: | Clarify Problem 1 note about checkRep() to make clear when and how it should be disabled, and how this interacts with the testing driver. |
| revision 1.61: | We added a hint pointing to section 15.4 of the textbook for guidance on seamlessly incorporating the A* heuristic. |
| revision 1.59: | We have added a sentence to the CompositeRoutePath section to make it clear that you should include a rep invariant, an abstraction function, and a checkRep method. |
| revision 1.55: | We have changed the specificition for the required constructor of StreetNumberSet to allow for empty sets to be created. That is, the empty string "" is now a legal argument to the constructor. |
| revision 1.54: | Two new files, PublicTest and RudimentaryTest, have been added to the provided source code area. These are the tests which are run by validate6170 ps4; they provide only a minimal level of test coverage for your implementation. |
| revision 1.53: | The .test and .example files for the sample test are now available. |
| revision 1.50: |
The specification for the constructor of StreetNumberSet has
been changed. The requires clause is now stronger, to make
your implementation (potentially) easier.
|