The eight sectors for classifying directions.
Contents:
It is sometimes difficult to navigate the 643 acres of the UW campus. To address this problem, UW Marketing has commissioned you to build a route-finding tool. It will take the names of two buildings and generate directions for the shortest walking route between them, using your graph ADT to represent buildings and pathways on campus. For now you will provide a simple text interface, and on the next homework you will write a graphical user interface (GUI). Unlike in previous assignments, you will be writing a complete application runnable through a main method.
In this assignment, you will continue to practice modular design and writing code for reuse. As before, you get to choose what classes to write and what data and methods each should have. You will also get experience using the model-view-controller design pattern, and in Homework 8 you will reuse your model with a more sophisticated view.
For organization, this assignment contains one "problem" for each logical component you will write. The order of the problems is not meant to suggest an order of implementation. You will certainly want to design the whole system before attempting to implement any part. As always, you should also develop incrementally, which may mean repeatedly writing a bit of all the parts and verifying that they work together.
You will design your application according to the model-view-controller (MVC) design pattern described in section and below.
As you design and implement your solution, please list which parts of your code belong to the model, the view, the controller, or none of the above in hw7/answers/mvc.txt. Often this can be on a per-class level, but when a class implements both the view and controller, you must indicate which methods or lines logically represent the view and which represent the controller.
In general, functionality of a model includes:
Does the user interact with a text interface or a GUI? What does the user type and/or click to get directions from CSE to Odegaard? How are those directions formatted for display? What message does the user see upon requesting directions to an unknown building? These are questions the view answers.
For a simple interface like in this assignment, the view and controller may be intermingled somewhat in code. Don't worry too much about the separation there; the key point for now is that the model is cleanly separated and reusable.
In general, avoid the temptation to create an oversized "god class" that does everything for the model. The model may contain multiple classes, and the view can interact with multiple classes in the model. Most of the time, any class that exists solely to represent data is part of the model. For this assignment, you will likely choose to have one central model class that manages the graph and does most of the heavy lifting, but you will likely also want some smaller objects that encapsulate related data. Some of these objects might be returned to the view so it can access their data directly, avoiding the "god class" scenario; others might be used only internally within the model.
Your model should be completely independent of the view (UI), which means it shouldn't know or decide how data is displayed. The model does know something about what data and operations the application needs, and it should provide methods to access them; however, it shouldn't return strings tailored to a particular view and definitely shouldn't contain printlns. Imagine replacing your text UI with a GUI or a Spanish/Mandarin/Klingon text UI (but with the same English building names) and ask yourself: is my model reusable with this new view?
On the flip side, a client (such as the view) doesn't know anything about how the model stores data internally. Someone writing a view for your application should only know that the model somehow stores buildings and paths on campus and should only interact with the data at this level. In other words, the public interface of the model should give no indication that this data is represented internally as a graph. That level of detail is irrelevant to the view, and revealing it publicly means the model can no longer change its implementation without potentially breaking view code.
We have added four files to the hw7/data directory of your repository: two plain-text data files to be parsed by your application, campus_buildings.dat and campus_paths.dat, and two images depicting the data from these files, campus_map.jpg and campus_routes.jpg. The .dat files are plain-text files that can be opened in any text editor, like marvel.tsv. Their format is described in more detail below. The image campus_map.jpg is a standard map of campus, while campus_routes.jpg is an image with the same proportions but containing only lines for walking paths and labels for some buildings. You will not directly use these images in your program; they are provided as an optional reference to help you understand what the data represents and verify your path output.
Your program can use relative filenames such as src/hw7/data/campus_buildings.dat. Your project has been configured so this relative path will be found correctly whether you run your program through Eclipse or at the command line with Ant.
You will write a parser to load the data from these files into memory. You may use MarvelParser.java as a general example of how to read and parse a file, keeping in mind that the campus data files are structured differently from the Marvel data file.
The file campus_buildings.dat lists all known buildings on campus. Each line has four tab-separated fields:
shortName longName x y
where shortName is the abbreviated name of a building, longName is the full name of a building, and (x,y) is the location of the building's entrance in pixels on campus_map.jpg. Some buildings have two entrances, which are listed as separate entries with unique abbreviated and full names.
The file campus_paths.dat defines straight-line segments of walking paths. For each endpoint of a path segment, there is a line in the file listing the pixel coordinates of that point in campus_map.jpg, followed by a tab-indented line for each endpoint to which it is connected with a path segment. Each indented line lists the coordinates of the other endpoint and the distance of the segment between them in feet. Thus, the structure is as follows:
x1,y1 x2,y2: distance12 x3,y3: distance13 ...
Some endpoints are building entrances and will match the coordinates of an entry in campus_buildings.txt, but most are not. The dataset only lists outdoor paths, to ensure (for example) that the paths work even if it's midnight, all the buildings are locked, and you're being chased by a zombie so you really need the shortest path.
As described above, the model handles the data and contains the major logic and computation of your program. For this assignment, a key function of the model will be finding the shortest walking route between buildings. This can be accomplished by using Dijkstra's algorithm to find a shortest path in the graph, where edge weights represent the physical length of a route segment.
Any model classes written specifically for Homework 7 that represent an ADT in some form should include an abstraction function, representation invariant, and checkRep(). If you have some model classes that contain only static methods and are never constructed, they do not represent an ADT and thus should not have these components, but you must explicitly state this in a comment at the top of the class where you would normally place the abstraction function and representation invariant.
On this homework, you will write a simple text interface. When the program is launched through the main method, it repeatedly prompts the user for one of the following one-character commands:
To support the test scripts you will write later, your program should simply echo empty lines or lines beginning with # to System.out. It should not attempt to process these lines as commands and should not reprint the usual prompt for a command after printing the line.
Otherwise, when an unknown command is received the program prints the line
Unknown option
We have provided the output from a sample run of our solution in the file hw7/sample_output.txt. This file reflects the exact appearance of the console window after running the program, and includes both user input and program output. If you run your program with the user input in the file, the state of the console should match the file contents exactly (including whitespace). The sample file and the descriptions below, taken together, should completely specify the output format of your program. Correction: in the sample output file, the header of the second path should read "Music Building (Northwest Entrance)" where it currently reads "Music."
Route directions start with
Path from Building 1 to Building 2:
where Building 1 and Building 2 are the full names of the two buildings specified by the user. Route directions are then printed with one line per path segment. Each line is indented with a single tab and reads:
Walk dist feet direction to (x, y)
where dist is the length of that segment in feet, direction is a compass direction, and (x, y) are the pixel coordinates of the segment endpoint. Finally, the route directions end with
Total distance: x feet
where x is the sum of the (non-rounded) distances of the individual route segments.
Distances and coordinates should be rounded to the nearest integer. As in Homework 6, we recommend the use of format strings.
Each compass direction is one of N, E, S, W, NE, SE, NW, or SW and can be determined by comparing the coordinates of the start and end points. Pixel (0,0) is at the top-left corner of the image, and the direction is selected according the eight sectors shown below. Each sector has the same angle. Points that fall exactly on a boundary between sectors should be classified as a single-letter direction (N, E, S, or W). (Hint: the function Math.atan2 and the constant Math.PI are helpful for determining which sector a route segment falls into. When using Math.atan2, think very carefully about the directions in which pixels increase as compared to the Cartesian coordinate plane.)
Finally, if one of the two buildings in a route is not in the dataset, the program prints the line
Unknown building: [name]
If neither building is in the dataset, the program prints the line twice, once for the first building and then for the second building. You may assume there is a route between every pair of buildings in the dataset; if not, the behavior is undefined.
For this assignment, the logical view and controller may be part of the same class. In this case you must clarify which parts of the class are the view and which are the controller in answers/mvc.txt, as described above. Do so by method — or even by line, if needed, though we recommend against having a single method contain parts of the view and of the controller.
As usual, your tests should be organized into specification and implementation tests. Unlike in previous assignments, the specification is based solely on the output of the complete application, as invoked through the main method. An automated specification tests must redirect System.in and System.out so that the program reads to and writes from files instead of the console.
To this end, we have provided a class HW7TestDriver that looks very different from your test drivers for past assignments. The runTests method accepts the names of two files, one for input and one for output, and temporarily points System.in and System.out to these files while it runs your main program. The result is that commands are read from the input file and output is printed to the output file. For your tests to run, you simply need to add one line to HW7TestDriver to invoke your main method.
As usual, you will specify the commands for your tests to run in *.test files. These files simply contain the series of input a user would have entered at the command line as the program was running. Recall from Problem 3 that you can also include blank lines or comment lines (starting with #) for readability and documentation, and your controller should simply echo these lines to the output. For each test, a corresponding .expected file should contain the output your program is expected to print if a user entered that input. As usual, the provided ScriptFileTests class will find all the .test files in the hw7/test directory, use the test driver to run each test with a 30-second timeout, print its output to a .actual file, and compare the output against the corresponding .expected file.
Note: if a test fails, it is often helpful to look at the .actual file. These files are written to the bin/hw7/test directory under your cse331 project. This directory is not visible through Eclipse, but you can navigate directly there through the file system or at the command line.
Additionally, you should write implementation tests for each of your model classes and add the test class names to ImplementationTests.java. If you choose to write new data (*.dat) files for testing, place these in your repository under hw7/test. Your implementation tests can use a relative path such as src/hw7/test/YourFileName.dat. Your project has been configured so that your tests will find the file correctly whether they are run through Eclipse or Ant. This eliminates the need for a helper method such as the getAbsoluteFileName() method provided in past test drivers.
You may not need implementation tests for the view and controller. One reason is that they typically have very little functionality — they act as glue between the UI (which is hard to test programmatically) and the model. Furthermore, end-to-end behavior of your application is tested through the specification tests. You may write additional tests for your view and controller if you feel there are important cases not covered by your specification tests, but avoid creating unnecessary work for yourself by duplicating tests.
Please answer the following questions in a file named reflection.txt in your answers/ directory.
Please answer the following questions in a file named collaboration.txt in your answers/ directory.
The standard collaboration policy applies to this assignment.
State whether or not you collaborated with other students. If you did collaborate with other students, state their names and a brief description of how you collaborated.
After you receive your corrected assignment back from your TA, you will need to resubmit a corrected version of the code. You will have until Wednesday, May 30 at 11pm to returnin your code. The returnin script will be enabled a week earlier, at 11pm Wednesday, May 30.
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.
As explained in Homework 6, Eclipse's built-in compiler sometimes handles generics differently from javac, the standard command-line compiler. This means code that compiles in Eclipse may not compile when we run our grading scripts, leaving us unable to test your code and significantly impacting your grade. You must periodically make sure your code compiles (builds) with javac by running ant build from the hw7 directory (which will also build hw4, hw5, and hw6 automatically). You can do this in one of two ways:
Remember to practice good procedural decomposition: each method should be short and represent a single logical operation or common task. In particular, it can be tempting to implement your entire view and controller as one long method, but strive to keep each method short by factoring operations into small helper methods.
Store your data in appropriate types/classes. In particular, you should not pack together data into a String and then later parse the String to extract the components.
You should add and commit the following files to SVN:
Additionally, be sure to commit any updates you make to the following files, as well as any files in hw4, hw5, or hw6:
Finally, remember to run ant validate to verify that you have submitted all files and that your code compiles and runs correctly when compiled with javac on attu (which sometimes behaves differently from the Eclipse compiler).
Clarification on the behavior for empty lines and comments (lines beginning with #): your program should simply echo these lines to System.out. It should not attempt to process these lines as commands and should not reprint the usual prompt for a command after printing the line.
In the sample_output.txt file in your repository, the header of the second path should read "Music Building (Northwest Entrance)" where it currently reads "Music" and "Mary Gates Hall (North Entrance)" where it currently reads "Mary Gates Hall."
If some of your model classes have only static methods, they do not represent an ADT and thus should not have an abstraction function, representation invariant, or checkRep(), but you must explicitly state this in a comment at the top of the class where you would normally place the AF and RI.
None yet!