Project 1: Railroad Network Controller - Fall 2025

Due: Tuesday Sep 30, before 9:00 pm

Objectives

  • Implementing a linked list data structure.
  • Using auxiliary data structures to implement the requirements.
  • Practice C++ dynamic memory management, i.e. avoiding memory leaks, avoiding double free, protection against wrong accesses in memory (segmentation fault), etc.
  • To practice writing unit tests.
  • To practice working in a Linux environment.
  • To practice analyzing and understanding a project requirements.

Introduction

A railroad control system is a system that is used for monitoring, analyzing, controlling and supervising railroad operations. Such a system collects data and provides data to the operators for the following purposes:

  • Enhancing the operations of the railroad network,
  • Ensuring the safe operations of the railroad,
  • Scheduling and initiating the required maintenance operations,
  • Collaborating with first responders during incidents.

A railroad company hired an engineering firm to update their control system. You are assigned a task to develop the data structure that holds the information about the railroad network including the information about routes, train stations, etc. The design document specifies that the data structure would be a doubly linked list.

The linked list contains all stations. Moreover we can define routes by linking the nodes in different directions. The following figure presents a route from node 2 to node 8. In this route from node 2 we move north to the node 5 and from node 5 we move south to the node 8. The route ends at the node 8.

Assignment

Your assignment is to implement the core class (Railroad) of controller software which consist of a doubly linked list.

For this project, you are provided with the skeleton .h and .cpp files and a sample driver:

  • railroad.h - Interface for the Railroad and Station classes.
  • railroad.cpp - It will be completed.
  • driver.cpp - A sample driver program showing the sample use of the Railroad class.
  • driver.txt - It contains the output from the sample driver.cpp.

Additionally, you are responsible for thoroughly testing your program. Your test program, mytest.cpp, must be submitted along with other files. For grading purposes, your implementation will be tested on input data of varying sizes, including very large data. Your submission will also be checked for memory leaks and memory errors.

Specifications

There are two classes in this project. The Station class is a node in the linked list and it stores the information for a Station. The Railroad class stores the information for a railroad network and it implements a doubly linked list.

Class Station

The implementation of this class is provided. You are not allowed to modify this class. The Station class implements a node that can be used in a linked list. Every node has a pointer to the next node in the linked list and a pointer to the previous node in the list. These pointers are stored in the m_next and m_previous member variables. Every station has a unique ID which is specified by the member variable m_code. The station ID must be greater than 0.

Class Railroad

This class implements the linked list data structure. You need to implement the class. The Station nodes are stored in the linked list which is presented by the pointer to its first node and its last node. The pointer to the first node is stored in the m_head member variable and the pointer to the last node is stored in the m_tail member variable. Every Station has a unique integer code. The list does not hold duplicate station codes. The station codes are integer numbers greater than zero.

Railroad::Railroad()
Default constructor creates an empty object and initializes member variables.
Railroad::~Railroad()
Destructor deallocates all memory and reinitializes member variables.
void Railroad::clearNetwork()
This public function deallocates all memory and reinitializes member variables.
bool Railroad::extendAtHead(int newCode, int passengers)
This function creates and inserts a new Station object at the head of the list. If the insertion is successful the function returns true, otherwise it returns false. Since the station codes must be unique in the list this function will not insert the station if it already exists.
bool Railroad::extendAtTail(int newCode, int passengers)
This function creates and inserts a new Station object at the tail of the list. If the insertion is successful the function returns true, otherwise it returns false. Since the station codes must be unique in the list this function will not insert the station if it already exists.
bool Railroad::makeRoute(list < pair < int,DIRECTION > > route)
This function allows for creating a route. The route parameter is a list of pair objects which are inserted in the order that defines the route. Every pair contains a station code and a direction, e.g. (2, NORTH) indicates that the route continues from station 2 in the north direction to the next station in route. If the provided route is invalid the function returns false and the linked list remains unchanged. If the route is valid and it is created successfully the function returns true. The route is considered invalid in the following cases:
  • If the first node of the route does not exist in the linked list.
  • If the route tries to modify an existing link from a node to another node.
If the provided list contains a valid route, we start from the first station in the list and set the links between stations. For example, if in the list we have (2, NORTH) followed by (5, SOUTH), the north direction of station 2 should point to the station 5 (for making links we use the pointers from the linked list, we do not create new pointers for making the links). We continue setting all links specified by the route. If a station in the route does not exist in the linked list, first we insert it as a new node in the linked list at tail (we create a new node in the linked list) then we set the link to it.
int Railroad::travel(list < pair < int,DIRECTION > > route)
This function receives a list of pair objects. Every pair defines a station code and a direction. This function starts from the first station in the parameter route and follows all links to the next stations in the specified directions. If all links specified in the parameter route are valid the function returns the total number of passengers in all stations of the route. If any station in the route does not exist in the linked list or a link in the specified direction is not defined the function fails and returns -1 indicating an invalid route.
bool Railroad::setNumPassengers(int code, int passengers)
This function allows for setting the number of passengers in a specific station indicated by code.
bool Railroad::removeStation(int aCode)
This function removes the node aCode from the linked list. If there is any link (as in a route) from another station to the removed one the link must be removed (reset). If removal is successful the function returns true otherwise it returns false. If the node does not exist the function returns false.
void Railroad::clearAllRoutes()
This function clears all routes that have been created previously.
void Railroad::dump()
This function prints out the list of stations along with the number of passengers at the station to the standard output. If there is a link from the station to any other station in any of north, south, east, or west direction the code of the linked station will be printed to the output. A value of -1 means there is no link at that direction. The implementation of this function is provided for the debugging purposes.
Railroad::Railroad(const Railroad & rhs)
The copy constructor creates a deep copy of rhs.
const Railroad & Railroad::operator=(const Railroad & rhs)
The assignment operator, creates a deep copy of rhs. Reminder: a deep copy means the current object has the same information as rhs object, however, it has its own memory allocated. Moreover, an assignment operator needs protection against self-assignment.

Additional Requirements

  • The class declarations (Railroad and Station) and provided function implementations in railroad.cpp may not be modified in any way. You are not allowed to add a member variable. No additional libraries may be used.
  • You are not allowed to use STL template containers in the project classes except the ones that are already in the project files.
  • You are allowed to use STL template containers in your test functions.
  • The class functions must be written in railroad.cpp; in particular, they must not be written “in-line.”
  • Private helper functions may be added to the Railroad class, but must be declared in the private section of the project class. There is a comment indicating where private helper function declarations should be written.

Testing

  • The test file name must be mytest.cpp; the file name must be in lower case, a file name like myTest.cpp is not acceptable.
  • The test file must contain the declaration and implementation of your Tester class and the main() function as well as all your test cases, i.e. calls to your test functions.
  • You are responsible for adequately testing your work before submission. The following section presents a non-exhaustive list of tests to perform on your implementation.
  • You must write a separate function for every test case.
  • Every test function must return true/false depending on passing or failing the test. Visual outputs are not accepted as test results.
  • The dump() function should not be called in the test functions. The dump() function is only provided to facilitate debugging.
  • Tests cannot be interactive. The test file mytest.cpp must compile and run to completion.
  • An example of declaring, implementing, and calling a test function, and outputting the test results was provided in the driver.cpp file of project 0.
  • The testing guidelines page provides information that helps you to write more effective test cases.

Note: Testing incrementally makes finding bugs easier. Once you finish a function and it is testable, make sure it is working correctly.

Testing Railroad Class

  • Test whether extendAtHead() works correctly for a normal case. The insertion for the normal case should be tested with a decent number of stations,e.g. 300 stations. We check whether the function returns true for every insertion. And we check whether all nodes are inserted.
  • Test whether extendAtHead() works correctly for an error case. For the error case of insertion we check that the station with a code less than one is not inserted and the function returns false.
  • Test whether extendAtTail() works correctly for a normal case.
  • Test whether extendAtTail() works correctly for an error case.
  • Test whether removeStation() works correctly for a normal case. Create an object with a decent number of stations and remove all, then check if all are removed correctly and at every removal the function returns true.
  • Test whether removeStation() works correctly for an error case which the removal request is for a non-existing station.
  • Test whether removeStation() works correctly for a normal case which all the links to the removed station are removed.
  • Test the Railroad class assignment operator for a normal case. Your test should check whether a deep copy is created. You can compare the list pointers, they should not match. Then, you compare all values in the corresponding nodes, all values should match.
  • Test the Railroad class assignment operator for edge cases. The edge cases would be a railroad with one station and two stations.
  • Test the Railroad class copy constructor for a normal case. Your test should check whether a deep copy is created.
  • Test the Railroad class copy constructor for edge cases.
  • Test whether makeRoute() returns false if the start station in the route does not exist in the linked list. This is an error case.
  • Test whether makeRoute() returns false if an entry in the route tries to overwrite an existing link. This is an error case.
  • Test whether travel() returns a correct value for a normal case, i.e. a valid route that has been created previously.
  • Test whether travel() returns the error value for an error case, i.e. the route is invalid.

Testing For Memory Leaks / Memory Errors

  • Run your test program in valgrind; check that there are no memory leaks or errors.
    Note: If valgrind finds memory errors, compile your code with the -g option to enable debugging support and then re-run valgrind with the -s and --track-origins=yes options. valgrind will show you the line numbers where the errors are detected and can usually tell you which line is causing the error.
  • Never ignore warnings. They are a major source of errors in a program.

What to Submit

You must submit the following files to the proj1 submit directory:

  • railroad.h
  • railroad.cpp
  • mytest.cpp (Note: This file contains the declaration and implementation of your Tester class as well as all your test cases.)

If you followed the instructions in the Project Submission page to set up your directories, you can submit your code using the following command: 

   cp railroad.h railroad.cpp mytest.cpp ~/cs341proj/proj1/

Grading Rubric

For details of grading rubric please refer to Project Grading Policy