School of Engineering and Computer Science

XMUT103
Assignment 2: Using Collections

Due 30 March , 19 pm

Download zip file of necessary code and data and extract it to an Assig2 folder (eg, in a COMP103 folder in your home folder). It should contain templates for the Java programs that will be marked.

Important note about the style of your code

To submit

• MilanoSubway.java
• Pencil.java, and any other classes you made for the Pencil program

Do not rename these files.

Remember to submit all of these files. When you have submitted them, check that you can read the files listed on the submission page, and complete the submission process.

Part 1: Milano Subway (Weight: 60%)

MilanoSubway is a program to answer queries about stations, lines and the timetables for the subway services on the Milan Metro subway system.

The Milan Metro has four intersecting lines, the Red line (M1), the Green line (M2), the Yellow line (M3) and the Violet line (M5).

The Milan system is large enough to be interesting but is less complex than many of the other subway systems in other big cities around the world.

The map above, which is what we will use for this assignment, is a slight simplification of the real map: it excludes the new M4 line, which isn't connected to the other lines yet, and also removes two of the little side-lines of the Green line.

You might want to look at the web page (and app) that is provided by the Milan Metro system that lets users find out about the system and plan journeys: https://metroguides.info/city/milan?ln=en#scheme/0/0

Stations, Lines, and Services:

Your program has to deal with three kinds of information: Stations, Lines, and Services:

• Stations: The stations are the stops along the lines. Each station has a unique name, a location and a set of subway lines that go through the station.
• Lines: Each line is a sequence of stations each at a specified distance along the line. To make things easier, we treat the two directions on a physical line as two separate lines. There is therefore an M5-north line that goes from San Siro Stadio to Bignami, and an M5-south line that goes in the reverse direction from Bignami to San Siro Stadio. They have the same stations, but in reverse order.
  Note: The Red line splits at Pagano and is therefore actually four lines: M1-east and M1-west (between Rho Fiera and Sesto I Maggio) and M1-north and M1-south (between Bisceglie and Sesto I Maggio).
  
• Services: a schedule/timetable for a particular subway train running on a given subway line.
  For example, the 05:30 subway train on the M5-south line that leaves Bignami station at 05:30, gets to Ponale at 05:31, ... and reaches the final station, San Siro Stadio, at 05:58.
  A 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.

Queries

The basic queries the program should be able to handle are the following:

1. List all the stations in the system
2. List all the stations in alphabetic order (by name).
3. List all the subway lines in the system, along with their first and last stations.
4. List the subway lines that go through a given station
5. List the stations along a given subway line
6. Check whether there is a subway line that goes from the current station to a given destination station, and print the subway line and the distance between the stations if there is one.
   (It should print a message if the stations are not on the same line.)
7. (Completion) Find the next subway service for each line at a station after the specified time
8. (Completion) Find a trip between two stations (on the same line), after the specified time.
   Find the subway line, the time that next service on that line will leave the current station, the time that the service will arrive at the destination station, and the distance travelled.
9. (Challenge:) More complex trips involve going from the first station to an exchange station on one subway line, then going from the exchange station to the second station on another subway line, (or even through a second exchange).
   Find the best trip (earliest arrival) between a starting station and a destination station. If the trip requires two or more subway lines, print out the starting time, all the stations and subway lines involved, the arriving and departing times times at each exchange station, and the arrival time at the destination.

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 and location on the map. eg
  Pero 101 352
  Note that there are no spaces in the station names - if the name has two parts, they are joined by a hyphen.
• data/subway-lines.data contains the names of all the subway lines, eg M1-north.
• For each subway line, there are two files:
  • a "stations" file with the sequence of stations on the subway line (eg data/M1-north-stations.data).
    Each line of a Mn-xxxx-stations.data has a station name and the distance to that station from the beginning of the line.
  • a "services" file with schedule/timetable information (eg data/M1-north-services.data)
    Each line of a Mn-xxxx-services.data file has a sequence of times for one service on the subway line. The times are given in 24 hour time, with no ':' in the middle eg, 1437 is 2:37pm.

Data Structures

Your MilanoSubway 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 SubwayLines (a Map, indexed by the names of the lines)

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

We have provided Java Classes for Station, SubwayLine, and LineService objects to store information about individual stations, subway lines, and subway 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.
Note that

• a SubwayLine contains inside it a collection of the LineServices on that line, as well as a List of Stations and a map of the distance of each station from the beginning of the line.
• A Station contains a collection of the SubwayLines that go through that station.

Template Code.

In addition to the Station.java, SubwayLine.java, and LineService.java classes, we have provided a MilanoSubway.java that contains just a few methods and fields. It contains a main method, a loadData method, a setupGUI method for creating a user interface and methods to let the user select the names of stations and a line. You do not need to use these methods if you want to do it a different way, but these methods should be helpful. The rest of the class is empty, and you will need to write the methods that do all the work.

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, indexed by the name of the Station
    (the Station objects won't have any SubwayLine information at this point)

To Create the Map of SubwayLines:

• Read the list of subway line names from "data/subway-lines.data"
• For each subway line name
  • Construct a SubwayLine object
  • Put the SubwayLine object into the Map of SubwayLines
  • For each station name in "data/Mn-xxxx-stations.data
    • Find the Station object in the Map of Stations,
    • Add the Station object to the stations in the SubwayLine object,
    • Add the SubwayLine object to the subway lines in the Station object

To load the Line Service (timetable) information: [Completion only]

• Read the list of subway line names from "data/subway-lines.data"
• For each subway line name
  • Read the file "data/Mn-xxxx-services.data"
  • For each line of the file (which has a sequence of times):
    • Construct a LineService object.
    • Add the LineService object to the SubwayLine object
    • For each time in the sequence of times,
      • Add the time to the LineService object.

Core:

For the Core, your program should

• Load the Station data and Subway Line data from the files into the data structures
• Be able to answer the first 6 queries above.
  Note that question 6 is a little bit tricky because it has to check that the first station comes before the destination station in the sequence of stations along the line.

Completion:

For the Completion, your program should also

• Load the Line Service (timetable) data from the files into the data structures.
• Be able to answer questions 7 and 8 above (both of which require the line service data).

Challenge:

For the Challenge, your program should also

• Be able to answer question 9 above - finding the best trip, even if it requires changing between two or more subway lines.
• Improve the interface and make the program better, eg by letting the user select stations and lines on the map, and displaying trips (queries 6 and 9) on the map.

Hints

• Look at the data files carefully so you know what is there.

• Read the Station.java, SubwayLine.java, and LineService.java classes carefully to make sure you know how to use them. You may want to use the Documentation view in BlueJ to help understand them.

• Sketch a diagram of the data structures, showing the Maps, a couple of Station objects, a couple of SubwayLine objects, and a LineService object (with all their fields), in order to make sure you know how they are all related.

Part 2: Pencil (Weight: 40%)

The Pencil program is a very simple drawing program that lets the user draw freehand lines on the graphics pane with a "pencil".

You are to add an undo and redo facility to Pencil. The undo button should remove strokes from the drawing, one at a time, from the most recently added back to the first stroke. The redo button should "undo the undo", by putting strokes back into the drawing after they have been undone. If the user draws a new stroke after doing an undo or redo, the program will "forget" all the strokes that have been undone.

This is similar to the Sokoban program in Assignment 1, but you will have to do more work than Sokoban to make the undo work. You will almost certainly need a class to represent strokes, and you may need to change the way the program works.

Core:

• Add the ability to undo the strokes

Completion:

• Add the ability to redo strokes that have been undone and then undo and redo them again (as long as no new strokes have been created since the undo action).

Challenge:

• Add the ability to change the colour and width of the pen, and ensure that undoing a stroke will take the colour and width back to what it was before that stroke was added. Eg, if the user draws three black strokes, then changes to red and draws two red strokes, then undoing the two red strokes will switch the colour back to black.