Answer Happy

//modify and submit this file only
#include "pa3.h"
#include
using namespace std;
//you are NOT allowed to include any additional library; see
FAQ
TrainCar* createTrainHead()
{
}
bool addCar(TrainCar* head, int position, CarType type, int
maxLoad)
{
}
bool deleteCar(TrainCar* head, int position)
{
}
bool swapCar(TrainCar* head, int a, int b)
{
}
void sortTrain(TrainCar* head, bool ascending)
{
}
bool load(TrainCar* head, CarType type, int amount)
{
}
bool unload(TrainCar* head, CarType type, int amount)
{
}
void printCargoStats(const TrainCar* head)
{
}
void divide(const TrainCar* head, TrainCar*
results[CARGO_TYPE_COUNT])
{
}
TrainCar* optimizeForMaximumPossibleCargos(const TrainCar* head,
int upperBound)
{
}
void deallocateTrain(TrainCar* head)
{
}
Other programme if you need
: https://drive.google.com/drive/folders/ ... sp=sharing
Functions to Implement This section describes the functions that you need to implement for this assignment in todo.cpp. While we try to be as detailed as possible in the following description, you should check the given test cases in main and the corresponding sample output to verify your understanding, especially if you cannot understand the requirements completely just by reading the webpage description alone. TrainCar* createTrainHead(); Dynamically create and return a train head car node. As it is currently the only car in the train, set both the prev and next pointers to nullptr. Friendly reminder: check the test cases. For this function, you may refer to the very first test case. bool addCar(TrainCar* head, int position, CarType cargoType, int maxLoad); Attempt to dynamically create and insert a new train car node of the specific cargoType with O current load and the specified maxLoad to an existing train headed by the specified head at the specified position (refer to the following examples to see how the position is used). It should return true if the addition is successful. The addition only fails when the given cargoType is HEAD because we would never add a train head with this function, or the given position is not larger than 0 because we won't be adding a new car before the train head, or the given position is larger than the length of the train (see examples below), or the given maxLoad is zero or negative. When it fails, do nothing to the train and simply return false. However, in this and all other functions that you need to implement, you can assume the head parameter given always points to a valid train head node of a valid existing train in all our test cases.

Example 1: • Original train which has its train head node pointed by train (which will be passed to the function as parameter head): [HEAD] In reverse: [HEAD] • After calling addCar(train, 1, OIL, 100) which returns true: [HEAD] -> [OIL: 0/100] In reverse: [OIL: 0/100] <- [HEAD] Example 2: • Original train which has its train head node pointed by train: [HEAD] -> [OIL:0/100] In reverse: [OIL: 0/100] <- [HEAD] • addCar(train, 0, SUGAR, 200) should simply return false. • addCar(train, 3, SUGAR, 200) should simply return false. (length of the train is 2, and 3 is larger than that) • addCar(train, 1, SUGAR, O) should simply return false. • After calling addCar(train, 1, SUGAR, 200) which returns true: [HEAD] -> [SUGAR:0/200] -> [OIL: 0/100] In reverse: [OIL:0/100] <- [SUGAR:0/200] <- [HEAD]

Example 3: • Original train which has its train head node pointed by train: [HEAD] -> [OIL: 0/100] In reverse: [OIL: 0/100] <- [HEAD] • After calling addCar(train, 2, SUGAR, 200) which returns true: [HEAD] -> [OIL:0/100] -> [SUGAR:0/200] In reverse: (SUGAR:0/200] <- [OIL: 0/100] <- [HEAD] bool deleteCar(TrainCar* head, int position); Attempt to remove a car node at the specified position. It should return true if the deletion is successful. The deletion only fails when the given position is invalid (less than 1 or not larger than the car length, see examples below). When it fails, do nothing to the train and simply return false. It should go without saying that you need to release any dynamically allocated memory allocated to the car node removed. Example 1: • Original train which has its train head node pointed by train: [HEAD] -> [OIL: 0/100] -> [SUGAR:0/200] In reverse: [SUGAR:0/200] <- [OIL: 0/100] <- [HEAD]

• deleteCar(train, O) should simply return false. We won't delete the train head with this function. • deleteCar(train, 3) should simply return false. The length of the train is 3, so there is no node to delete at position 3. After calling deleteCar(train, 1) which returns true: [HEAD] -> [SUGAR:0/200] In reverse: [SUGAR:0/200] <- [HEAD] Example 2: • Original train which has its train head node pointed by train: [HEAD] -> [OIL:0/100] -> [SUGAR:0/200] In reverse: [SUGAR:0/200] [OIL: 0/100] <- [HEAD] <- • After calling deleteCar(train, 2) which returns true: [HEAD] -> [OIL:0/100] In reverse: [OIL: 0/100] <- [HEAD] bool swapCar (TrainCar* head, int a, int b b); Swap train cars at the given positions a and b. It should return true if the swap is successful. The swap only fails when any of the given positions is invalid, just like the deleteCar function. When it fails, do nothing to the train and simply return false. Swap can also be successfully performed if a is the same as b as long as they are valid positions, although the train won't apparently change.

Example 1: Original train which has its train head node pointed by train: [HEAD] -> [OIL: 0/100] -> [SUGAR:0/200] In reverse: [SUGAR:0/200] <- [OIL: 0/100] <- [HEAD] • swapCar(train, 0, 1) should simply return false. • swapCar(train, 1, 3) should simply return false. • After calling swapCar(train, 1, 2) which returns true: [HEAD] -> [SUGAR:0/200] -> [OIL:0/100] In reverse: [OIL: 0/100] <- [SUGAR:0/200] <- [HEAD] Note that calling swapCar(train, 2, 1) would have the same effect. void sortTrain(TrainCar* head, bool ascending); Sort the cargo train cars by their current loads ascendingly if ascending is true or descendingly if ascending is false. The train head should not be included in the sorting as the train head must always be at position 0. For simplicity, assume no two cargo cars in the same train have the same current load in all test cases that test this function. Example 1: • Original train which has its train head node pointed by train:

[HEAD] -> [SUGAR: 30/400] -> [OIL:10/100] -> [COAL:40/200] -> [STEEL: 20/300] -> [COAL:5/500] In reverse: [COAL:5/500] <- [STEEL: 20/300] <- [COAL:40/200] <- [OIL:10/100] <- [SUGAR: 30/400] <- [HEAD] • After calling sortTrain(train, true): [HEAD] -> [COAL:5/500] -> [OIL:10/100] -> [STEEL: 20/300] -> [SUGAR: 30/400] -> [COAL:40/200] In reverse: [COAL: 40/200] <- [SUGAR: 30/400] <- (STEEL: 20/300] <- [OIL:10/100] <- [COAL: 5/500] <- [HEAD] • After calling sortTrain(train, false): [HEAD] -> [COAL: 40/200] -> [SUGAR: 30/400] -> [STEEL:20/300] -> [OIL:10/100] -> [COAL: 5/500] In reverse: [COAL:5/500] <- [OIL: 10/100] <- [STEEL: 20/300] <- [SUGAR: 30/400] <- [COAL:40/200] <- [HEAD] bool load (TrainCar* head, CarType type, int amount); Attempt to load the specified amount of cargo of the specified type for the train (i.e. add new cargo to the train). It should return true if the loading is successful. The loading only fails if there is not enough free space for the specified cargo type in the train. When it fails, do nothing to the train and simply return false. When there are multiple cars of that cargo type, the loading always tries to fill the cargo cars that are closer to the train head first. Refer to the examples below. You can assume the amount is always positive and the type won't be HEAD. (i.e. no checking of those parameters is needed) Example 1: O Original train which has its train head node pointed by train: [HEAD] -> [SUGAR: 30/400] -> [OIL:10/100] -> [COAL:40/200] -> [STEEL: 20/300] -> [COAL:5/500] In reverse: [COAL:5/500] < (STEEL: 20/300] <- [COAL:40/200] <- [OIL:10/100] <- [SUGAR: 30/400] <- [HEAD]

• load(train, WOOD, 1) should simply return false because the train doesn't even have any WOOD cargo car. • load(train, SUGAR, 380) should simply return false because the train can only carry at most 370 additional units of SUGAR. • After calling load(train, SUGAR, 300) which returns true: [HEAD] -> [SUGAR: 330/400] -> [OIL:10/100] -> [COAL:40/200] -> [STEEL: 20/300] -> [COAL:5/500] In reverse: [COAL: 5/500] <- [STEEL: 20/300] <- [COAL:40/200] <- [OIL:10/100] <- [SUGAR:330/400] <- [HEAD] Example 2: . Original train which has its train head node pointed by train: [HEAD] -> [SUGAR: 30/400] -> [OIL:10/100] -> [COAL: 40/200] -> [STEEL: 20/300] -> [COAL:5/500] In reverse: [COAL:5/500] <- [STEEL: 20/300] <- [COAL:40/200] <- [OIL:10/100] <- [SUGAR: 30/400] <- [HEAD] • After calling load(train, COAL, 510) which returns true: [HEAD] -> [SUGAR: 30/400] -> [OIL:10/100] -> [COAL:200/200] -> [STEEL: 20/300] -> [COAL: 355/500] In reverse: [COAL: 355/500] <- (STEEL: 20/300] <- [COAL: 200/200] <- [OIL:10/100] <- [SUGAR: 30/400] <- [HEAD] In this example, the first COAL car is filled with 160 units of additional COAL first, then the second COAL car is filled with the remaining 350 units of COAL. bool unload (TrainCar* head, CarType type, int amount); Attempt to unload the specified amount of cargo of the specified type for the train (i.e. remove cargo from the train). It should return true if the unloading is successful. The unloading only fails if there is not enough cargo to remove for the specified cargo type in the train. When it fails, do nothing to the train and simply return false. When there are multiple cars of that cargo type, the unloading always tries to unload the cargo cars that are closer to the train tail first. Refer to the examples below. You can assume the amount is always positive and the type won't be HEAD.

Example 1: • Original train which has its train head node pointed by train: [HEAD] -> [SUGAR: 30/400] -> [OIL:10/100] -> [COAL: 40/200] -> [STEEL: 20/300] -> [COAL:5/500] In reverse: [COAL: 5/500] <- [STEEL: 20/300] <- [COAL:40/200] <- [OIL:10/100] <- [SUGAR:30/400] <- [HEAD] • unload(train, WOOD, 1) should simply return false because the train doesn't even have any WOOD cargo car. • unload(train, SUGAR, 31) should simply return false because the train only has 30 units of SUGAR. • After calling unload(train, SUGAR, 29) which returns true: [HEAD] -> [SUGAR:1/400] -> [OIL:10/100] -> [COAL: 40/200] -> [STEEL: 20/300] -> [COAL: 5/500] In reverse: [COAL: 5/500] <- [STEEL: 20/300] <- [COAL: 40/200] <- [OIL:10/100] <- [SUGAR:1/400] <- [HEAD] Example 2: • Original train which has its train head node pointed by train: [HEAD] -> [SUGAR: 30/400] -> [OIL:10/100] -> [COAL:40/200] -> [STEEL: 20/300] -> [COAL:5/500) In reverse: [COAL:5/500] < (STEEL: 20/300] <- [COAL:40/200] <- [OIL:10/100] <- [SUGAR: 30/400] <- [HEAD] • After calling unload(train, COAL, 15) which returns true: [HEAD] -> [SUGAR: 30/400] -> [OIL:10/100] -> [COAL: 30/200] -> [STEEL: 20/300] -> [COAL:0/500] In reverse: [COAL:0/500] <- [STEEL: 20/300] <- [COAL: 30/200] <- [OIL:10/100] <- [SUGAR: 30/400] <- [HEAD] In this example, 5 units of COAL are removed from the the last COAL car first, then 10 units of COAL are remove from the second last COAL car.

void printCargoStats(const TrainCar* head); Print the one-line cargo stats to the console terminal with cout. The exact format required will be explained with the following example. You can assume the train has at least one cargo car in all the test cases that test this function. Example 1: . Original train which has its train head node pointed by train: [HEAD] -> [SUGAR: 30/400] -> [OIL:10/100] -> [COAL: 40/200] -> [STEEL: 0/300] -> [COAL: 5/500] In reverse: [COAL:5/500] <- [STEEL: 0/300] <- [COAL: 40/200] <- [OIL:10/100] <- [SUGAR: 30/400] <- [HEAD] • printCargoStats (train) should print the following line to the console terminal with cout: SUGAR: 30/400,OIL:10/100,COAL:45/700, STEEL: 0/300 As you can see, it simply tells the user, for each cargo type that exists in the train, the total current load and the total maximum load. For example, there are in total 45 units of COAL while at most 700 units can be carried, hence we have "COAL:45/700". The printing order of the cargo types depend on their first appearances in the train. In this example, since the SUGAR car appears first, the stats for SUGAR are printed first. The stats for OIL are printed second as OIL appears the second in the train. Finally, because COAL first appears earlier than STEEL in the train, the stats for COAL are printed before STEEL. Stats for WOOD are not printed because there is no WOOD car at all in this example. The stats for different cargo types are separated by exactly one comma",". There should be no empty spaces at all in the whole line. There is also exactly one new-line character endl at the end of the line. Following all the rules listed above, there can only be one version of the printed line. Any difference in your output will be considered as incorrect. Since all grading will be automatically done by output comparison and we will not allow any student to modify their submitted code after the submission deadline, please check carefully if your

code can output the stats with the exact format as described. You can compare your output with our sample output for the given test cases which test this function, or run them on ZINC to make sure (friendly reminder: ZINC server will be very busy when the deadline approaches, please do not expect you can get the grading reports for checking quickly during that time; probably you will need to manually compare your output with our sample output carefully then if you start late). void divide (const TrainCar* head, TrainCar* results[CARGO_TYPE_COUNT]); Create new trains of single cargo types from the given train. The cars in the new trains must be dynamically created. (i.e. in the new trains, do not just put/point to any existing cars of the given train - you need to create new copies of the cars) The original train should not be modified. We will use the following examples to explain what you need to do. You can assume the train has at least one cargo car in all the test cases that test this function. Example 1: • Original train which has its train head node pointed by train: [HEAD] -> [SUGAR: 30/400] -> [OIL:10/100] -> [COAL:40/200] -> [STEEL: 0/300] -> [COAL:5/500] In reverse: [COAL:5/500] <- [STEEL: 0/300] <- [COAL:40/200] <- [OIL:10/100] <- [SUGAR: 30/400] <- [HEAD] • divide(train, results) will perform the following: 1. Find out how many cargo types there are in total for this train. For this example, there are 4, in this order according to their first appearances in the train: SUGAR, OIL, COAL, STEEL 2. Generate a new train for each of the cargo types, in the order determined in the previous step. Therefore, for this example, there should be 4 new trains created for this example: a SUGAR train first, then an OIL train, then a COAL train, and finally a STEEL train. 3. For the SUGAR (the first cargo type) train, you will need to create a new train head, and then add a new SUGAR car of the same load and maximum load as the only SUGAR car we have in the given train: [HEAD] -> [SUGAR: 30/400] In reverse: [SUGAR: 30/400] <- [HEAD ]

Make the first result pointer (results[0]) point to the head car node of it. 4. For the OIL (the second cargo type) train, you will need to create a new train head, and then add a new OIL car of the same load and maximum load as the only OIL car we have in the given train: [HEAD] -> [OIL:10/100] In reverse: [OIL: 10/100] <- [HEAD] Make the second result pointer (results[1]) point to the head car node of it. 5. For the COAL (the third cargo type) train, you will need to create a new train head, and then add two new COAL cars of the same loads and maximum loads as the two OIL cars we have in the given train. Note that we keep their relative ordering in the new train as you can see: [HEAD] -> [COAL:40/200] -> [COAL:5/500] In reverse: [COAL:5/500] <- [COAL:40/200] <- [HEAD] Make the third result pointer (results[2]) point to the head car node of it. 6. For the STEEL (the fourth cargo type) train, you will need to create a new train head, and then add a new STEEL car of the same load and maximum load as the only STEEL car we have in the given train: [HEAD] -> [STEEL: 0/300] In reverse: [STEEL: 0/300] <- [HEAD] Make the fourth result pointer (results[3]) point to the head car node of it. 7. Set all the remaining result pointers to nullptr. Since there are only 4 new trains created in this example, only the first 4 result pointers will point to the new trains, you should therefore set results[4] to nullptr. (note: CARGO_TYPE_COUNT is 5, so there are only 5 results pointers) • If we print the results array with the following code which is also used in our test cases as you can see in main.cpp:

cout << "Divide results:" << endl; for(int i=0; i<CARGO_TYPE_COUNT; i++) { cout << "results[" «< i < "]:" << endl; if(results == nullptr) cout << "nullptr" << endl; else printTrain(results); } The following would be the output: Divide results: results[0]: [HEAD] -> [SUGAR: 30/400] In reverse: [SUGAR: 30/400] <- [HEAD] results[1]: [HEAD] -> [OIL:10/100] In reverse: [OIL:10/100] <- [HEAD] results[2]: [HEAD] -> [COAL: 40/200] -> [COAL:5/500] In reverse: [COAL: 5/500] <- [COAL:40/200] <- [HEAD] results [3]: [HEAD] -> [STEEL: 0/300] In reverse: [STEEL:0/300] <- [HEAD] results[4]: nullptr

As usual, you may use the other examples in the given test cases in main.cpp to verify/help with your understanding. TrainCar* optimizeForMaximumPossibleCargos (const TrainCar* head, int upperBound); Find a subset of the cargo cars which can carry the maximum amount of cargo (type doesn't matter for this part) that is not more than the given upperBound, then create a new train with those cargo cars and return it. The cars the returned train must be dynamically created. (i.e. in the returned train, do not just put/point to any existing cars of the given train - you need to create new copies of the cars) The original train should not be modified. We will use the following examples to explain what you need to do. You can assume the train has at least one cargo car in all the test cases that test this function. For simplicity, you can assume there will only be exactly one solution in each of the test cases for this function. Example 1: • Original train which has its train head node pointed by train: [HEAD] -> [SUGAR: 30/400] -> [COAL: 10/100] -> [COAL: 25/200] In reverse: [COAL: 25/200] <- [COAL: 10/100] <- [SUGAR: 30/400] <- [HEAD] • There are 8 possible trains that can be generated with those cargo cars (we always keep the same relative ordering among them, so there can only be exactly 8 of them in this example): 1. [HEAD] -> [SUGAR: 30/400] -> [COAL: 10/100] -> [COAL: 25/200] In reverse: [COAL: 25/200] <- [COAL: 10/100] <- [SUGAR: 30/400] <- [HEAD] which carries 65 units of cargo in total.

2. [HEAD] -> [SUGAR: 30/400] -> [COAL: 10/100] In reverse: [COAL: 10/100] <- [SUGAR: 30/400] <- [HEAD] which carries 40 units of cargo in total. 3. [HEAD] -> [SUGAR: 30/400] -> [COAL: 25/200] In reverse: [COAL: 25/200] <- [SUGAR: 30/400] <- [HEAD] which carries 55 units of cargo in total. 4. [HEAD] -> [COAL: 10/100] -> [COAL: 25/200] In reverse: [COAL: 25/200] <- [COAL: 10/100] <- [HEAD] which carries 35 units of cargo in total. 5. [HEAD] -> [SUGAR: 30/400] In reverse: [SUGAR: 30/400] <- [HEAD] which carries 30 units of cargo in total. 6. [HEAD] -> [COAL: 10/100] In reverse: [COAL: 10/100] <- [HEAD] which carries 10 units of cargo in total.

7. [HEAD] -> [COAL: 25/200] In reverse: [COAL: 25/200] <- [HEAD] which carries 25 units of cargo in total. 8. [HEAD] In reverse: [HEAD] which carries 0 unit of cargo in total. • optimizeForMaximumPossibleCargos (train, 100) should create and return a new train: [HEAD] -> [SUGAR:30/400] -> [COAL: 10/100] -> [COAL: 25/200] In reverse: [COAL: 25/200] <- [COAL: 10/100] <- [SUGAR: 30/400 <- which carries 65 units of cargo in total. • optimizeForMaximumPossibleCargos (train, 35) should create and return a new train: [HEAD] -> [COAL: 10/100] -> [COAL: 25/200] In reverse: [COAL: 25/200] <- [COAL: 10/100] <- [HEAD] which carries 35 units of cargo in total. . optimizeForMaximumPossibleCargos (train, 36) should create and return a new train: [HEAD] -> [COAL: 10/100] -> [COAL: 25/200] In reverse: [COAL: 25/200] <- [COAL: 10/100] <- [HEAD]

which carries 35 units of cargo in total. • optimizeForMaximumPossibleCargos (train, 40) should create and return a new train: [HEAD] -> [SUGAR: 30/400] -> [COAL: 10/100] In reverse: [COAL: 10/100] <- [SUGAR:30/400] <- [HEAD] which carries 40 units of cargo in total. • optimizeForMaximumPossibleCargos (train, 5) should create and return a new train: [HEAD] In reverse: [HEAD] which carries 0 unit of cargo in total. Note that you should not assume the maximum number of cars the given train can have, since the train is a linked list. void deallocateTrain(TrainCar* head); Release/deallocate all the memory allocated for all the cars in the given train. Tip: If this function is crashing your program for all the test cases on ZINC, you may consider leaving its implementation empty so that you can get the majority of points from test cases that don't check for memory leak.