Introduction to Data Structures and Algorithms
Assignment 2 Part A: Using Collections

  • Due 6 May , 7pm

What To Hand In

  • WellingtonTrains.java

Do not rename this file and do not rename any other files provided in the Template.

When you have submitted it, check that you can read the file listed on the submission page, and complete the submission process.

Wellington Trains (Weight: 2/3)

WellingtonTrains is a program to answer queries about Wellington train stations, train lines and the timetables for the train services on those lines.

(See https://www.metlink.org.nz/#plan for Metlink's equivalent program for the whole of the Wellington Regional Transport system. Your program is not web-based, and doesn't need such a fancy interface.)

system-map.png

Stations, Lines, and Services:

Your program has to deal with three kinds of information:
  • Train Stations
  • Train Lines: a sequence of stations. For example, the Wellington_Johnsonville line, which starts at Wellington station, and ends at Johnsonville station, with 7 stations in between. To make things easier, we treat the inbound and outbound as two separate train lines, so the Wellington_Melling line is different from the Melling_Wellington line. (They have the same stations, but the sequence in one is the reverse of the sequence in the other.)
  • Train Service: a schedule/timetable for a particular train running on a given train line. For example, the 11:32 train on the Wellington_Johnsonville line that leaves Wellington station at 11:32, leaves Crofton-Downs at 11:40, ... gets in to Johnsonville at 11:55.
    A Train Service is specified by a sequence of times - the time that the train leaves the first station, followed by the times that the train gets to each of the remaining stations on the line. Note that some train services don't stop at every station on the line. If a train doesn't stop at a station, the corresponding time will be -1.

Queries

The basic queries the program should be able to handle are the following:
  1. List all the stations in the region.
  2. List all the train lines in the region
  3. List the train lines that go through a given station
  4. List the stations along a given train line
  5. Print the name of a train line that goes from a station to a destination station. (The train line must go the correct direction.)
  6. (Completion) Find the next train service for each line at a station after the specified time
  7. (Completion) Find a trip between two stations (on the same line), after the specified time.
    Find the train line, the time that next service on that line will leave the first station, the time that the service will arrive at the destination station, and the number of fare zones the trip goes through.
  8. (Challenge:) More complex trips involve going from the first station to an exchange station on one train line, then going from the exchange station to the second station on another train line. (In larger cities, trips might require more than 2 train lines, but the Wellington region has a central hub, so you never need more than two segments for a trip.)
    Find the best trip (earliest arrival) between a starting station and a destination station. If the trip requires two train lines, print out the starting time, the first train line, the exchange station, the arriving and departing times at the exchange station, the second train line, and the arrival time at the destination, and the total number of fare zones.

Data Files

There are a set of data files in the data sub directory that contain the information that your program needs to load and then use.
  • data/stations.data contains one line of information about each station in the system: name, fare zone, and distance from the hub station. eg
    Crofton-Downs 3 4.9
    Note that there are no spaces in the station names - if the name has two parts, they are joined by a hyphen.
  • data/train-lines.data contains the names of all the train lines, eg Melling_Wellington. Each line is named by the station at the beginning of the line and the station at the end of the line, joined by an underscore.
  • For each train line, there are two files:
    • one with the sequence of stations on the train line (eg data/Wellington_Johnsonville-stations.data)
    • one with services (timetable) information (eg data/Wellington_Johnsonville-services.data)
      Each line of a XXX_YYY-services.data file has a sequence of times for one train service on the train line. The times are given in 24 hour time, with no ':' in the middle eg, 1437 is 2:37pm.

Data Structures

Your WellingtonTrains program will need to load the data from the files into data structures inside the program. A sensible way of organising the data inside your program will be to have
  • a collection of Stations (a Map, indexed by the names of the stations)
  • a collection of TrainLines (a Map, indexed by the names of the TrainLines)

For the Core of the assignment, you do not have to worry about the Train Services - just the Stations and TrainLines.

We have provided Java Classes for Station, TrainLine, and TrainService objects to store information about individual stations, train lines, and train services. Make sure that you read these classes carefully and work out how to use them. They each have constructors, and methods to add data to the object, and methods for accessing data in the object and a toString() method to return a string representation of the object. Note that a TrainLine contains inside it a collection of the TrainServices on that line, as well as a List of Stations, and a Station contains a collection of the TrainLines that go through that station.

Template Code.

In addition to the Station.java, TrainLine.java, and TrainService.java classes, we have provided a WellingtonTrains.java that contains just a few methods and fields. It contains a main method, a doLoadData method, and a setupGUI method for creating a user interface.

You will need to provide the methods invoked by the setGUI method.

It is very important that you do not rename these methods

Suggested Algorithms for loading the data

To Create the Map of Stations:
  • Read the data from "data/stations.data"
  • For each line of the data,
    • construct a Station object using the data on the line
    • put the Station into the Map of Stations (the Station objects won't have any TrainLine information at this point)

To Create the Map of TrainLines:
  • Read the list of train line names from "data/train-lines.data"
  • For each train line name
    • Construct a TrainLine object
    • Put the TrainLine object into the Map of TrainLines
    • For each station name in "data/XXX_YYY-stations.data
      • Look up the Station object in the Map of Stations,
      • Add the Station object to the stations in the TrainLine object,
      • Add the TrainLine object to the train lines in the Station object

To load the Train Service (timetable) information: [Completion only]
  • Read the list of train line names from "data/train-lines.data"
  • For each train line name
    • For each line (containing a list of times) in "data/XXX_YYY-services.data"
      • Construct a TrainService object
      • Add the TrainService object to the TrainLine object
      • For each time in the list of times,
        • Add the time to the TrainService object.

Core:

For the Core, your program should
  • Load the Station and Train Line data from the files into data structures. Methods to implement are loadStationData and loadTrainLineData.
  • Be able to answer the following queries. Please follow these instructions carefully as we use automatic marking for marking your WellingtonTrains program
    • List all the stations in the region by writing a listAllStations method that only prints each station using UI.println(station).
    • List all the train lines in the region by writing a listAllTrainLines method that only prints each train lines using UI.println(line)
    • List the train lines that go through a given station by writing a listLinesOfStation method that only prints each train line using UI.println(line)
    • List the stations along a given train line by writing a listStationsOnLine method that only prints each station using UI.println(station)
    • Print the name of a train line that goes from a station to a destination station. (The train line must go the correct direction.) Write a checkConnected method. The output should prints the name of the line followed by the number of fare zones, if there is a line connecting the two stations, or "No train line found" if the two stations are not connected. Note that this question is a bit tricky because it has to check that the first station comes before the destination station in the sequence of stations along the line.
      Please match the formt of the output.

checkConnected
Naenae and Woburn Naenae and Melling
checkConnected-naenae-woburn.png checkConnected-naenae-melling.png

Completion:

For the Completion, your program should also
  • Load the Train Service (timetable) data from the files into the data structures by implementing the loadTrainServicesData method
  • Be able to answer the following queries. Please follow these instructions carefully as we use automatic marking for marking your WellingtonTrains program
    • Find the next train service for each line at a station after the specified time by writing a findNextServices method. Follow the given format for your output as given in the example below, displaying the next train services from Waterloo after 9AM.

findNextServices-waterloo-900.png

    • Find a trip between two stations (on the same line), after the specified time by writing a findTrip method .
      Find the train line, the time that next service on that line will leave the first station, the time that the service will arrive at the destination station, and the number of fare zones the trip goes through. Follow the given format for your output.

findTrip
from Porirua to Wellington after 10AM from Porirua to Petone after 10AM
findTrip-porirua-wellington-1000.png findTrip-porirua-petone-1000.png

Challenge:

For the Challenge, your program should also
  • Be able to answer question 8 above - finding the best trip, even if it requires an exchange between two train lines.
  • Improve the interface and make the program better, eg by showing the stations and the lines on a map (there are two png files with maps of the system that you can use).

Hints
  • Look at the data files carefully so you know what is there. The data is all from the www.metlink.org.nz site (but cleaned up); looking at the site may help you understand the data better.

  • Read the Station.java, TrainLine.java, and TrainService.java classes carefully to make sure you know how to use them.

  • Sketch a diagram of the data structures, showing the Maps, a couple of Stations, a couple of TrainLines, and a TrainService, in order to make sure you know how they are all related.