CMSC 341 Data Structures - Project 1: The Airplane Fuel System
Objectives
- Practice analyzing a project's requirements.
- Implementing a circular buffer using linked list.
- Implementing a singly linked list.
- Combining two data structures to satisfy a project's requirements.
- Practice C++ dynamic memory management, i.e. avoiding memory leaks, avoiding double free, protection against wrong accesses in memory (segmentation fault), etc.
- Practice writing test cases for a project.
Introduction
The airplane fuel system in a delta-wings airplane such as Concorde has three functions:
- to supply fuel to the engines,
- to control the position of the aircraft’s Centre of Gravity (CG),
- and to act as a heat sink to absorb kinetic heating from the structure and to dissipate heat generated by the air-conditioning and hydraulic systems.
A main job of the fuel system in such a design is transferring fuel across multiple tanks. Here is an explanation of this idea from the Concorde engineers:
Before Concorde takes-off, the flight engineer will start to move fuel from the forward trim tanks to the rear trim and collection tanks, this will continue during the acceleration through Mach 1 and onto eventual Mach 2. During this process around 20 tons of fuel is moved and this results in a shift of the CG by 6ft (2meters). This will neatly balance the change in the center lift of the aircraft.
Circular Linked List
A circular linked list is a linked list in which the last node points to the first node. To access the linked list we store the memory location for the last node in a pointer variable. This pointer variable in different applications is referred to by different names such as cursor or current. Generally the current pointer points to the latest node inserted into the list. Therefore, the next node of current is the first one inserted into the list. The circular linked list is commonly used to implement the queue ADT in which the dequeue happens at the next node of current.
Assignment
Your assignment is to implement a circular linked list data structure that stores the tanks information and provides the required functionality for the system. Since the number of tanks for different airplane designs would be different, using a linked list data structure makes this software module more general.
For this project, you are provided with the skeleton .h and .cpp files and a sample driver:
- fuel.h - Interface for the Tank, Pump, and FuelSys classes.
- fuel.cpp - This file will be completed and submitted.
- driver.cpp - A sample driver program showing the sample use of the FuelSys class.
- driver.txt - Sample 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 and configurations. Your submission will also be checked for memory leaks and memory errors.
Specifications
There are three classes in this project. The Tank class is a node in the linked list and it stores the information for a fuel tank. The Pump class is a node in a singly linked list and it stores the information for a pump that is installed in a tank. Every tank may have multiple fuel pumps installed. Every pump can transfer fuel from its parent tank to a specified target tank. The FuelSys class stores the information for the entire fuel system and it implements a circular linked list.
Class Tank
The implementation of this class is provided. You are not allowed to modify this class. The Tank 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. This pointer is stored in the m_next member variable. Every tank object has a unique ID number in this system. Moreover, every tank can have multiple fuel pumps. The pumps of a tank are stored in a singly linked list accessible through the head of the list that is stored in the member variable m_pumps. The member variable m_tankFuel stores the current amount of fuel in the tank. We can transfer part of the current fuel to another tank using one of the pumps installed in the tank.
Class Pump
The implementation of this class is provided. You are not allowed to modify this class. The Pump 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. This pointer is stored in the m_next member variable. Every pump object has a unique ID number in the context of its parent tank. Moreover, every pump has a target tank that can receive fuel from the pump. This tank ID is stored in the member variable m_target.
Class FuelSys
This class implements a circular linked list data structure. You need to implement the class. The Tank nodes are stored in the linked list which is presented by the pointer to its current node stored in the member variable m_current. Every tank has a unique ID number. The list does not hold duplicate tank IDs. The tank IDs are integer numbers greater than or equal to zero.
Additional Requirements
- The class declarations (Tank), (Pump) and (FuelSys) and provided function implementations in fuel.cpp may not be modified in any way. No additional libraries may be used in the project implementation. Private helper functions may be added but must be declared in the private section of the FuelSys class. There is a comment indicating where private helper function declarations should be written.
- No STL containers or additional libraries may be used except the ones that are already in the project files. STL containers or additional libraries may be used in your tests, i.e. mytest.cpp.
- Your code should not have any memory leaks or memory errors.
- Follow all coding standards as described on the C++ Coding Standards. In particular, indentations and meaningful comments are important.
Testing
You need to test your project and you need to submit your tests along with your project. Tests must be submitted in a file called mytest.cpp.
- 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 thoroughly 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.
- 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 FuelSys class:
- Test whether addTank() works correctly for a normal case, i.e. inserting multiple tanks. We check whether the function returns true for every insertion. And we check whether all nodes are inserted.
- Test whether addTank() works correctly for an error case. For example, for the error case of insertion we check that the tank with an ID less than zero is not inserted and the function returns false. Another error case would be inserting a duplicate ID.
- Test whether removeTank() works correctly for a normal case. Create an object with a decent number of tanks and remove all, then check if all are removed correctly and at every removal the function returns true.
- Test whether removeTank() works correctly for an error case which the removal request is for a non-existing tank.
- Test whether findTank() works correctly for a normal case. Create an object with a decent number of tanks and search for them, then check if the found tank is the next node of the current node in the list and at every search operation the function returns true.
- Test whether findTank() works correctly for an error case which the tank does not exist in the list.
- Test whether totalFuel() works correctly for a normal case. It returns the correct value.
- Test whether totalFuel() works correctly for an error case. It returns zero where there is no tank in the system.
- Test whether addPump() works correctly for a normal case. It adds multiple pumps to some of the tanks.
- Test whether addPump() works correctly for an error case. It does not add a duplicate pump ID to a tank. Another error case would be adding a pump to a tank that does not exist.
- Test whether removePump() works correctly for a normal case. It removes multiple pumps from some of the tanks.
- Test whether removePump() works correctly for an error case. That is trying to remove a non-existent pump or trying to remove a pump from a non-existent tank.
- Test whether drain() works correctly. It transfers the fuel from the source tank to the target tank correctly where the requested fuel is less than the empty space of the target tank. Another case would be when the amount of fuel is more than the empty space of the target tank.
- Test whether drain() works correctly for the error cases. For example, the source tank or the pump or the destination tank does not exist in the system.
- Test the overloaded assignment operator.
Memory leaks and 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 lines 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:
- fuel.h
- fuel.cpp
- mytest.cpp (Note: This file contains 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.)
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 fuel.h fuel.cpp mytest.cpp ~/cs341proj/proj1/
