COMPUTER SCIENCE 21A (FALL, 2023)
DATA STRUCTURES AND ALGORITHMS
PROGRAMMING ASSIGNMENT 1 – MBTA RED LINE
Overview:
You have been tasked to run a simulation of the Red Line for the MBTA. This will entail
populating the stations with trains and passengers from text files, run the simulation, and print
out a log that includes the status of the railway’s stations and the movement of trains and
passengers.
Basic Idea:
You will be given three text files from which you will create the stations, the trains, and the
passengers. Each station will maintain queues for passengers who are waiting to travel. Since a
station can load and unload passengers onto only 1 train at a time, it will also have queues for
any additional trains who have arrived at the station. Trains can hold a limited number of
passengers and can only travel in one direction at a time.
Implementation Details:
The provided zip file on LATTE contains 13 files:
• 3 data structures related classes (Node.java, Queue.java, and DoubleLinkedList.java)
• 5 MBTA related classes (Rider.java, Train.java, Station.java, Railway.java, and
MBTA.java)
• 2 JUnit test files for you to write tests for your implementations of a queue and doubly
linked list.
• 3 Provided JUnit test files that include basic tests for your MBTA classes.
The 3 data structures classes and 5 MBTA related classes are described in detail below. You
must implement the following methods following these exact signatures. Furthermore, some
of these classes include specific fields. You must also include these in your implementation
and leave them as public.
Queue.java
This class provides the implementation of a generic circular first-in-first-out queue. In your
implementation, you must use the following 4 public fields:
public T[] q – generic array to store the contents of the queue.
public int head – index of the front of the queue, from which you should dequeue.
public int tail – index of where the next element will be enqueued.
public int numEntries – number of entries stored in the queue.
public Queue(int capacity) – constructs an empty queue that can hold a specified
number of elements. You will find that one line of this method has been provided in the skeleton
code. It is how you create a generic array in Java.
public void enqueue(T element) – adds an element at the tail of the queue.
public void dequeue() – removes the element at the head of the queue. If there is no
such element, you must throw a NoSuchElementException.
public T front() – returns the element at the head of the queue without removing it. If
there is no such element, you must throw a NoSuchElementException.
public int size() – return the number of elements in the queue.
public String toString() – return a String representation of the queue’s elements.
Node.java
This class provides the implementation of a doubly linked list node. These nodes should have a
pointer to the next node, a pointer to the previous node, and data.
public Node(T data) – constructs a doubly linked list node that holds a data field but
does not point to any other nodes.
public void setData(T data) – sets the data field of this node.
public void setNext(Node next) – sets the next pointer of this node.
public void setPrev(Node prev) – sets the previous pointer of this node.
public T getData() – returns the data stored in this node.
public Node getNext() – returns the pointer to the next node or null if one does
not exist.
public Node getPrev() – returns the pointer to the previous node or null if one
does not exist.
public String toString() – returns the String representation of this node’s element.
DoubleLinkedList.java
This class provides the implementation of a generic non-circular doubly linked list.
public DoubleLinkedList() – initializes a doubly linked list to have 0 elements.
public Node getFirst() – gets the first node in the list or null if one does not exist.
public void insert(T element) – adds an element to the end of this list.
public T delete(T key) – deletes the first element from this list that matches the
provided key. If the provided key does not exist in the list, return null.
public T get(T key) – returns the first element in the list that matches the provided key
or null if one cannot be found.
public int size() – returns the number of elements in the list.
public String toString() – returns a String representation of this list’s elements.
Rider.java
This class represents a Rider on the red line. A rider should have an ID, starting station,
destination station, and a direction.
public Rider(String riderID, String startingStation, String
destinationStation) – this should construct a Rider with an ID as well as starting and
ending stations. A Rider must start by travelling south. You may assume that a Rider will be
travelling at least 1 Station.
public String getStarting() – returns the name of this Rider’s starting station.
public String getDestination() – returns the name of this Rider’s ending station.
public String getRiderID() – returns this Rider’s ID.
public boolean goingNorth() – returns true if this Rider is northbound. Else, false.
public void swapDirection() – swaps the Rider’s current direction.
public String toString() – returns a String representation of this Rider.
public boolean equals(Object o) – checks if this Rider is equal to another Object
based on ID.
Train.java
This class represents a Train on the red line. All Trains hold a specified number of passengers in
an array, the current number of passengers, the current Station where the Train is, and the Train’s
current direction. You must use the following 3 public fields:
public static final int TOTAL_PASSENGERS - the # of passengers that the train
can hold, the default is 10 passengers
public Rider[] passengers – the Train’s passengers.
public int passengerIndex – tracks the number of passengers currently in the Train.
public Train(String currentStation, int direction) – constructs an
empty Train at a given Station going either south (1) or north (0).
public boolean goingNorth() – returns true if this Train is northbound. Else, return
false.
public void swapDirection() – swaps the Train’s direction.
public String currentPassengers() – returns a String of the current passengers
on the Train. For instance, one could return:
7SG7IE6K7J7TZLHCHTZW, Porter
0W3E3HYLZ67MQCA6ACQ8, Porter
3A56AC65CK7D12UCE55Y, Porter
public boolean addPassenger(Rider r) – adds a passenger to the Train as long
as (i) the Rider is at the correct Station to enter the Train, (ii) the Train is going in the appropriate
direction, and (iii) there is space on the Train. Return true if the addition was completed. Else,
return false.
public boolean hasSpaceForPassengers() – returns true if the Train has space
for additional passengers.
public String disembarkPassengers() – This should remove all of the
passengers who should be exiting the Train at the Train’s current station. It should also return a
String of the removed passengers. For instance, one could return:
7SG7IE6K7J7TZLHCHTZW, Porter
0W3E3HYLZ67MQCA6ACQ8, Porter
3A56AC65CK7D12UCE55Y, Porter
If there are no passengers to remove, return an empty String.
public void updateStation(String s) – Updates the name of this Train’s current
station to be the name of another station.
public String getStation() – returns the name of the Train’s current Station.
public String toString() – returns a String representation of this Train.
Station.java
This class represents a Station on the red line. A Station should track which Trains and Riders
are waiting to go north or south. You must use the following 4 public fields:
public Queue northBoundRiders – queue for riders waiting to go north
public Queue southBoundRiders – queue for riders waiting to go south
public Queue
northBoundTrains – queue for trains waiting to go north
public Queue
southBoundTrains – queue for trains waiting to go south
public Station(String name) – constructs an empty Station with a given name.
public boolean addRider(Rider r) – adds a Rider to the appropriate Queue,
depending on the Rider’s direction, as long as they should be in this Station. Return true if this is
possible and false otherwise.
public String addTrain(Train t) – moves a Train into this Station, removes all of
the passengers who are meant to disembark at this Station, and places the Train in the
appropriate Queue depending on its direction. This method should return a String that includes
that some passengers were removed at this Station. For instance, one could return:
Quincy Adams Disembarking Passengers:
FVPRE0BX09L3OMS2VR87
public Train southBoardTrain() – This method will prepare a southbound Train of
passengers by performing the following steps:
1) Dequeuing a train from the southbound train queue.
2) Adding as many southbound Riders to the Train as possible.
3) Return the train that has been filled or null if there are no waiting southbound
Trains.
public Train northBoardTrain() – This method will prepare a northbound Train of
passengers by performing the following steps:
1) Dequeuing a train from the northbound train queue.
2) Adding as many northbound Riders to the Train as possible.
3) Return the train that has been filled or null if there are no waiting northbound
Trains.
public void moveTrainNorthToSouth() – changes the direction of the first waiting
northbound Train and moves it to the southbound queue. You may assume that the Train will not
have any Riders.
public void moveTrainSouthToNorth() – changes the direction of the first waiting
southbound Train and moves it to the northbound queue. You may assume that the Train will not
have any Riders.
public String stationName() – returns the name of this Station
public String toString() – this should return the name and status of the station. For
instance, one could return:
Station: Alewife
1 north-bound trains waiting
0 south-bound trains waiting
0 north-bound passengers waiting
1 south-bound passengers waiting
public boolean equals(Object o) – Checks if a Station is equal to some object
based on name.
Railway.java
This class represents the red line railway and is made up of a list of Stations. You must use the
following 2 public fields:
public DoubleLinkedList railway – a list of the Railway’s Stations.
public String[] stationNames – the names of the Stations on the Railway. This
will contain a maximum of 18 entries corresponding to the 18 stations listed in redLine.txt.
public Railway() – constructs an empty Railway.
public void addStation(Station s) – adds a Station to the Railway.
public void addRider(Rider r) – (i) sets a Rider’s direction based on the order of
the Stations in the Railway and (ii) adds the Rider to the appropriate Station in the Railway.
public void addTrain(Train t) – adds a Train to the appropriate Station in this
Railway.
public void setRiderDirection(Rider r) – sets a Rider’s direction based on
the Rider’s starting and ending Stations.
public String simulate() – This method will execute one simulation of the Railway.
You should log the events that occur in the process of your simulation such as the status of each
Station, where Trains and Riders are, and when Riders exit a Train. This log should be returned
by this method for use in the main class MBTA.java.
During this method, you should traverse the Stations in the Railway north to south and perform
the following steps at each Station in this order:
1. Board a (southbound/northbound) train with as many passengers as possible unless the
Station is (Braintree/Alewife).
2. Move the boarded trains to their next Stations.
3. Disembark any passengers who are meant to get off at the Stations that the trains were
moved to.
4. If the current Station is (Braintree/Alewife) then you should move a (southbound train to
go north/northbound train to go south).
Note: you should never have a train switch direction and move from that Station in a single call
to this method.
public String toString() – returns the Stations list’s String representation.
MBTA.java
This class contains your program’s main method and should run a simulation of a Railway. The
class contains the following 4 fields:
public static final int NORTHBOUND – value of the northbound direction (0).
public static final int SOUTHBOUND - value of the southbound direction (1).
static final int TIMES – the number of times you will run Railway’s simulate()
in the method below runSimulation()
static final Railway r – the Railway that will be used in the simulation.
public static void main(String[] args) – The main method should construct
the Railway with the Stations, Riders, and Trains loaded from the provided text files and then run
the simulation.
public static void runSimulation() – This method runs the simulation using
TIMES and Railway’s simulate().
public static void initTrains(String trainsFile) - constructs Trains
from an input file and adds them to the Railway.
public static void initRiders(String ridersFile) - constructs Riders
from an input file and adds them to the Railway.
public static void initStations(String stationsFile) - constructs
Stations from an input file and adds them to the Railway.
Provided Text Files
You have been provided three text files. Feel free to change them to test your code’s functionality.
The format for the redLine.txt file is a list of the 18 unique stations. You are to read them one by
one and generate the corresponding Stations and place them within the Railway.
The format for the riders.txt file is:
DPK6S7FCGATASW1B02WP //riderID
Alewife //Start station
Park Street //Destination station
Notes:
• Riders will have unique IDs.
• Riders will only have starting and destination stations listed in redLine.txt
The format for the trains.txt file is:
Harvard //Train starts at this station
1 //Train direction (1=south, 0=north)
Sample Output
In addition to this file and the assignment’s skeleton, you will find a text file containing some
sample output for the first 3 cycles of the simulation if it was run on the provided input files.
Your output may differ because of where in simulate() you log a Station’s status and
whether you move north or south trains first.
JUnit Tests
In this assignment, it will be very important to be rigorously testing the functionality of your data
structures. We have provided some basic tests for your MBTA classes, but you must write your
own tests for the data structures in the provided JUnit test files.
IMPORTANT NOTES
• For the classes in which specific fields are included, you must be using these fields and
leaving them as public.
• Due to the nature of the Railway traversal, in one call of simulate(), your southbound
trains that start further north should pass freely all the way down until the southernmost
station as long as there are no trains in the other stations’ southbound train queues. On the
other hand, northbound trains that start further south will move only 1 stop in each call of
simulate() even if there are no other trains in other stations’ northbound train queues.
This behavior is expected.
• There will be no more than 20 people/trains queued for each station in either direction.
• Your toString() methods should be written in so that the final output contains a
readable log of the flow of passengers and trains between the stations.
• You are not allowed to use any Java provided data structures except arrays.
• You cannot import any Java libraries other than those that are needed to read text
files and to throw exceptions in the Queue class: java.util.Scanner,
java.io.File, java.io.FileNotFoundException,
java.util.NoSuchElementException
Submission Details
• For every non-test method you write, you must provide a proper JavaDoc comment using
@param, @return, etc.
• In addition to regular JavaDoc information, please include each non-test method’s runtime.
• At the top of every file that you submit please leave a comment with the following format.
Make sure to include each of these 6 items.
/**
*
* Known Bugs:
*
* @author Firstname Lastname
*
*
* COSI 21A PA1
*/
>Start of your class here<
• Use the provided skeleton Eclipse project.
• Submit your assignment via Latte as a .zip file by the due date. It should contain your
solution in an Eclipse project.
• Your Eclipse project should be named LastnameFirstname-PA1. To rename a project in
Eclipse, right-click on it and choose Refactor > Rename.
• Name your .zip file LastnameFirstname-PA1.zip
• Late submissions will not receive credit.