Task Overview:
In brief, you will write a method for reading in a timetable - a description of routes and their services
- from a file, and you will write a method for finding a journey from one station to another using an algorithm that is specified below in this handout.
More specifically, you must code method read from the class TimetableReader and method findJourney from the class JourneyFinder that are available in the zip file that accompanies this handout, according to their specifications in those files.
You must complete these methods and classes as if other programmers were, at the same time, implementing classes that use it. Hence:
• Don't change the class names, specifications, or alter the method names, parameter types, return types, exceptions thrown or the packages to which the files belong.
• You are encouraged to use Java 7 SE classes, but no third party libraries should be used. (It is not necessary, and makes marking hard.)
• Don't write any code that is operating--system specific (e.g. by hard--coding in newline characters etc.), since we will batch test your code on a Unix machine.
• Any new methods or fields that you add to TimetableReader or JourneyFinder must be private (i.e. don't change the spec of these classes.)
• Your source file should be written using ASCII characters only.
Implement the classes as if other programmers are going to be using and maintaining them. Hence:
• Your code should follow accepted Java naming conventions, be consistently indented, readable, and use embedded whitespace consistently. Line length should not be over 80 characters. (Hint: if you are using Eclipse you might want to consider getting it to automatically format your code.)
• Any additional methods that you write, and fields that you introduce should be private to hide implementation details and protect invariants.
• Private methods that you write must be commented using preconditions and postconditions (require and ensures clauses). Informal description is OK.
• Fields and local variables (except for--loop variables) should have appropriate comments. Comments should also be used to describe any particularly tricky sections of code. However, you should also strive to make your code understandable without reference to comments; e.g. by choosing sensible method and variable names, and by coding in a straightforward way.
• The methods that you have to write must be decomposed into a clear and not overly complicated solution, using private methods to prevent any individual method from doing too much.
I recommend that you attempt to write loop invariants for all non--trivial while-- loops in your code, but this is not compulsory.
The Zip file for the assignment also includes some other code that you will need to compile your classes as well as some junit4 test classes to help you get started with testing your code.
Do not modify any of the files in package planner other than TimetableReader and JourneyFinder, since we will test your code using our original versions of these other files. Do not add any new files that your code for these classes depends upon, since you won't submit them and we won't be testing your code using them.
The junit4 test classes as provided in the package planner.test are not intended to be an exhaustive test for your code. Part of your task will be to expand on these tests to ensure that your code behaves as required by the javadoc comments.
We will test your code using our own extensive suite of junit test cases. (Once again, this is intended to mirror what happens in real life. You write your code according to the "spec", and test it, and then hand it over to other people ... who test and / or use it in ways that you may not have thought of.)
If you think there are things that are unclear about the problem, ask on the newsgroup, ask a tutor, or email the course coordinator to clarify the requirements. Real software projects have requirements that aren't entirely clear, too!
The algorithm for the JourneyFinder.findJourney method:
Given a timetable timetable satisfying the preconditions of the findJourney method as given in the JourneyFinder class, distinct start and end stations startStation and endStation, and a start time time, the following algorithm can be used to find a journey - if there is one - from the start to the end station that departs the start station no earlier than the start time and arrives at endStation no later than any other journey with those constraints.
In this algorithm we will classify stations to be either finalised or unfinalised. For each station we will also keep track of a fastestKnownJourney from startStation, departing startStation no earlier than time, to that station. The fastestKnownJourney to a station may be defined - if there is such a journey - or undefined if there is not.
For each station that is finalised, the fastestKnownJourney to that station is in fact a journey from startStation, departing startStation no sooner than time, to that station that arrives no later than any other such journey.
Initially each station is classified as being unfinalised, and the fastest Known Journey to each station other than startStation is set to be undefined. The fastest Known Journey to startStation is marked as being defined as the special empty journey that conceptually starts and ends at time.
while (there is at least one unfinalised station such that the fastestKnownJourney to that station is defined)
• let current be an unfinalised station that can be reached by its (defined) fastestKnownJourney sooner than any of the other unfinalised stations can be reached by theirs; then let currentJourney be the fastestKnownJourney to current and, currentTime be the time that journey ends at the current station
• mark current as being finalised
• if (current equals endStation) then return currentJourney - found it!
• for each route that stops at current such that current is not the last stop of the route, and there exists a service for route that will stop at current at a some time >= currentTime
o let station adjacent be the next stop on that route after current, and let service be the earliest service for route that departs current no earlier than currentTime
o (If adjacent has not been finalised and) if currentJourney extended by taking service to adjacent would arrive before the fastestKnownJourney to adjacent, or if fastestKnownJourney to adjacent is undefined, then update the fastestKnownJourney to adjacent to be defined as that one return null since we have found no journey from startStation to endStation that departs no sooner than time
Hints:
1. It may be easier to implement the TimetableReader.read method first first since you can use it to read in timetables to test the JourneyFinder.findJourney method.
2. Read the specification comments carefully. They have details that affect how you need to implement and test your solution.
Attachment:- assignment.zip