EECS281 Project 2- “Star Wars: Episode X - A New Heap” Solution

 Important Note: There are two parts to this project. In your IDE, make a separate “IDE Project” for each part. If you try to create a single project, you run into a problem of having two copies of main() , which wonʼt compile, etc.
Part A: Galactic Warfare Simulation

Overview

A war over the galaxy has broken out between the Jedi and the Sith. There are many planets in the galaxy, and generals will be deploying Jedi and Sith battalions to attack and defend them. The Sith are ruthless and vicious, and vehemently oppose the peacekeeping forces of the Jedi. When battles occur, they are always initiated by the Sith, who will send their strongest battalion to fight the weakest Jedi battalion on any given planet. Battalion strength is measured by the average Force-sensitivity of the troops in the battalion, but even the worst pitched battles will always result an equal number of troops lost on both sides.
Learning Objectives

Identify the broadest range of Force-sensitivity that could theoretically be encountered in a battle
Command Line Options

Your program, galaxy , should take the following case-sensitive command-line options that will determine which types of output to generate. See Output Details for information about each output mode.
-v , --verbose
A command line option that indicates verbose output should be generated.
-m , --median
A command line option that indicates median output should be generated.
-g , --general-eval
A command line option that indicates that the general evaluation output should be generated.
-w , --watcher
A command line option that indicates that movie watcher output should be generated.
Legal Command Lines

./galaxy < infile.txt > outfile.txt
Read deployments from infile.txt and write output to outfile.txt , using default output options.
./galaxy -v < infile.txt > outfile.txt
Same, but with verbose output messages. ./galaxy --verbose --general-eval > outfile.txt < infile.txt Run with verbose output and print a general evaluation at the end.
./galaxy --median < infile.txt
Calculate and print the median number of troops lost in battles.
./galaxy --watcher < infile.txt Show “movie watcher” output.
./galaxy -vmgw < infile.txt
Run with all output options enabled.
Battle Simulation

As you read each battalion deployment from input, your program should see if the new battalion can be matched with a battalion previously deployed on the planet. If a match occurs, then the two battalions engage in warfare. A new battalion can be matched with a previously deployed battalion if:
Both deployments are on the same planet
The troops deployed were on opposite sides of the Force: one deployment was a Jedi deployment and the other was a Sith deployment
The Jedi Force-sensitivity is less than or equal to the Sith Force-sensitivity.
Other considerations:
The Sith always instigate fights, and they only fight battalions with Force-sensitivity which they are confident that they can overcome
When a Sith battalion is deployed and starts a battle with a Jedi battalion already on the planet, this is referred to as an “attack”
When a Jedi battalion is deployed and a Sith battalion already on the planet starts a battle with it, this is referred to as an “ambush”
If the newly arriving battalion is a Sith battalion, it will always choose to attack the least Forcesensitive Jedi battalion on the planet, given that there is a Jedi battalion with lesser Forcesensitivity. If the newly arriving battalion is a Jedi battalion, it will always be ambushed by the most Force-sensitive Sith battalion on the planet, given that there is a Sith battalion with greater
Force-sensitivity. In the event of a tie in Force-sensitivity, the battalion that was deployed first (came first in the input file) will be sent to battle first.
When a battle occurs, the battalions trade troops one-for-one, regardless of their Forcesensitivity. That is to say that an equal number of troops from both battalions are eliminated. That number is always equal to the number of troops in the smaller battalion. If one of the battalions survives, it remains on the planet for future possible battles. For example, if a Sith battalion with 20 troops battles a Jedi battalion of 30 troops, the Sith battalion is eradicated and the Jedi battalion remains with 10 troops.
Input

Your program will receive as input a series of “battalion deployments,” or placements of troops on a certain planet. A battalion deployment consists of the following information:
Timestamp — the time that this deployment order is issued
General ID — the general who is issuing the deployment order
Planet ID — the planet which the troops are being deployed to
Jedi or Sith — Whether the troops being deployed are Jedi or Sith (Flavor note: in Star Wars, the Jedi are the good team using the Light side of the Force, and the Sith are the bad team on the Dark side of the Force. Click the link below for more info on The Force) Force-sensitivity — the average Force-sensitivity of the troops being deployed Quantity — the number of troops being deployed
Input will arrive from standard input (cin). There are two input formats, deployment list (DL) and pseudorandom (PR). All inputs tested the autograder will be correct and properly formed. Input File Header

The header is the first four lines of any valid input file will always be in the following format:

<COMMENT> is a string terminated by a newline, which should be ignored. (You should comment your test files to explain their purpose.)
<INPUT_MODE> will either be the string "DL" or "PR" . DL indicates that the rest of input will be in the deployment list format, and PR indicates that the rest of input will be in pseudorandom format. Details for these input formats will be explained below.
<NUM_GENERALS> and <NUM_PLANETS> , respectively, will tell you how many generals and planets will exist. These values will be positive integer values that can be read and stored in an unsigned integer type.
Deployment List Input

In Deployment List mode, the remainder of the input file will be a series of lines with each line representing a unique deployment. DL input files will not specify the number of deployments in the file. Each line will be in the following format:
<TIMESTAMP> <SITH/JEDI> G<GENERAL_ID> P<PLANET_NUM> F<FORCE_SENSITIVITY> #
<NUM_TROOPS> The line:
0 JEDI G0 P1 F100 #44 Can be translated as:
“At timestamp 0, General 0 deploys 44 Jedi troops with Force-sensitivity 100 to Planet 1.”
DL Input Error Checking

To detect corrupt deployment orders, you must check for each of the following:
The <GENERAL_ID> and <PLANET_ID> integers are in ranges [0, <NUM_GENERALS>) and [0,
<NUM_PLANETS>) , respectively
e.g. if <NUM_GENERALS> is 5, then valid general IDs are 0, 1, 2, 3, 4
<FORCE_SENSITIVITY> and <NUM_TROOPS> are greater than 0
Timestamps are non-decreasing
e.g. 0 cannot come after 1, but there can be multiple deployments with the same timestamp
If you detect invalid input at any time during the program, print a helpful message to cerr and exit(1) . You do not need to check for input errors not explicitly mentioned here.
Pseudorandom Input

In pseudorandom mode, the file header is followed by exactly three lines, which specify values that are used to create deployments using a pseudorandom number generator (PRNG). Lines 5-7
will be in the following format:


<SEED> is an integer used to initialize the random seed.
<NUM_DEPLOYMENTS> is the number of deployment orders to generate. This value will be a nonnegative integer.
Generating deployments with P2random.h

Psuedorandom input is generated using the P2random class in the included P2random.h file. After initializing the P2random object with the seed, number of deployments, and arrival rate found in lines 5-7 of the input file, a stringstream object is filled with the randomly generated deployments. A solution that can read both DL and PR input files will choose to read deployments from the stringstream object for PR or from cin for DL.
Details for how to use the P2random class are provided below, with the full implementation available in P2random.h . This file is included to make pseudo-random generation uniform across platforms.
PR input will always be correctly formatted
The P2random class is initialized with the following function:
P2random::PR_init() function declaration from P2random.h
1 void P2random::PR_init(std::stringstream &ss, uint32_t seed,
2 uint32_t num_generals, uint32_t num_planets,3 uint32_t num_deployments, uint32_t arrival_rate);
P2random::PR_init(...) will fill the stringstream argument, ss , with deployments, so that it can later be used with the stream extraction operator >> similar to how cin is used.
The following C++ code is helpful in reducing code duplication:

4 if (inputMode == "PR") { // inputMode is read from line 2 of the header
5 // TODO: include number of generals and number of planets read from lines
6 // 3-4 of the header and add code to read random seed, number of
7 // deployments, and arrival rate from lines 5-7 of the input file
8 P2random::PR_init(ss, seed, num_gen, num_planets, num_deploys, rate);
9 } // if ..inputMode
10
11 // Create a reference variable that is ALWAYS used for reading input.
12 // If PR mode is on, refer to the stringstream. Otherwise, refer to cin.
13 // This is a place where the ternary operator must be used: an equivalent
14 // if/else is impossible because reference variables must be initialized 15 // when they are created.
16 istream &inputStream = inputMode == "PR" ? ss : cin;
17
18 // Make sure to read an entire deployment in the while statement
19 while (inputStream >> var1 >> var2 ...) {
20 // Process this deployment, use PQs, initiate battles (if possible), etc.21 } // while ..inputStream
DL & PR Comparison

The following two input files are in different modes, but generate the same deployments when


Simple Example

Consider the following series of deployments from an input file in DL mode:

Here is what should happen when these deployments are processed:
. General 1 deploys battalion 1 with Force-sensitivity 100 on Planet 2 with 10 Sith troops There are no other battalions on the planet yet, so they remain on standby 10 Sith troops are on Planet 2
. General 2 deploys battalion 2 with Force-sensitivity 10 on Planet 2 with 20 Jedi troops Jedi battalion 2 encounters Sith battalion 1: the Sith battalion has a higher Forcesensitivity, so it instigates a fight with (ambushes) the Jedi battalion 2
They do battle and both lose 10 troops, since battles exchange troops one-for-one 10 Jedi troops remain on Planet 2
. General 3 deploys battalion 3 with Force-sensitivity 1 on Planet 2 with 10 Sith troops Sith battalion 3 encounters Jedi battalion 2: the Sith battalion has a lower Forcesensitivity, so it avoids the fight and remains on standby
10 Jedi troops remain on Planet 2, 10 Sith troops remain on Planet 2
Output Details

The output generated by your program will depend on the command line options specified at runtime. With the exception of startup output and the summary output, all output is optional and should not be generated unless the corresponding command line option is specified.
Startup Output

Your program should always print the following line before reading any deployments:
Deploying troops...
Summary Output

After all input has been read and all possible battles have been fought, the following output should always be printed:

<NUM_BATTLES> is the total number of battles that have happened over the course of the day.
Verbose Output

If and only if the --verbose/-v option is specified on the command line (see above), whenever a battle is completed you should print on a single line:
General <GENERAL_A_NUM>'s battalion attacked <GENERAL_B_NUM>'s battalion on planet <PLANET_NUM>. <NUM_TROOPS_LOST> troops were lost.
<GENERAL_A_NUM> is the number of the general who deployed the Sith troops
<GENERAL_B_NUM> is the number of the general who deployed the Jedi troops
<NUM_TROOPS_LOST> is defined to be the total number of troops lost from both sides, or the number of Jedi troops lost + the number of Sith troops lost.
Example:
Given the following list of deployments:

No battles are possible until the 5th battalion is deployed. When the 5th battalion is deployed and a battle occurs, you should print:
General 5's battalion attacked General 4's battalion on planet 0. 8 troops were lost.
Median Output

If and only if the --median/-m option is specified on the command line, whenever there is a change in timestamp your program should print the current median troops lost in a battle for each planet, in ascending order, by planet ID. If no battles have occurred on a specific planet, do not print the median message for that planet. In the case that battles have occurred, you should print:
Median troops lost on planet <PLANET_ID> at time <TIMESTAMP> is <MED_TROOPS_LOST>.
<PLANET_ID> is the number of the planet that is being summarized
<TIMESTAMP> is the timestamp that has just closed, ie. as soon as the first deployment from timestamp 5 arrives, you should print the median through timestamp 4, if there have ever been any battles on that planet
<MED_TROOPS_LOST> is the median number of troops lost in all battles on that planet since the beginning of the day, up to and including the timestamp that has just closed
If an even number of battles occur on a planet, take the average of the middlemost two to compute the median. There will always be an even number of troops lost in a battle (the same number of troops from both sides), so the result will always be an integer, even when divided by two.
Example
Given the following battles:
General 5's battalion attacked General 4's battalion on planet 9. 8 troops were lost.
General 2's battalion attacked General 7's battalion on planet 9. 2 troops were lost.
The median lost troops for planet 9 after these two battles is ((2 + 8)/2) = 5. If the timestamp changed, and the --median option was specified, your program should print:
Median troops lost on planet 9 at time 0 is 5.
General Evaluation Output

If and only if the --general-eval/-g option is specified on the command line, following the summary output, you should print the following line without any preceding newlines:

Followed by lines in the following format for every general in ascending order (0, 1, 2, etc.), even if they did not engage in any battles:
General <GENERAL_ID> deployed <NUM_JEDI> Jedi troops and <NUM_SITH> Sith troops, and <NUM_SURVIVORS>/<NUM_DEPLOYED> troops survived.
These numbers are troops across all planets. Example:
1 ---General Evaluation---
2 General 0 deployed 40 Jedi troops and 0 Sith troops, and 20/40 troops survived.
3 General 1 deployed 0 Jedi troops and 0 Sith troops, and 0/0 troops survived.
4 General 2 deployed 60 Jedi troops and 30 Sith troops, and 44/90 troops survived.
Movie-Watcher Output

As a fervent Star Wars fan, you want to find which pairs of battling Jedi and Sith deployments would have made for a maximally-exciting movie. For each planet, your job is to find the pairs of Jedi and Sith deployments that would have had the most “exciting” battles. The most “exciting” battle is one that has the greatest difference in Force-sensitivity between the battling parties. A battle can only happen if the Jedi Force-sensitivity is less than or equal to the Sith Forcesensitivity.
You want to find the most exciting possible Sith attack and Sith ambush for each planet. A Sith attack occurs when the Jedi are deployed to the planet first, and the Sith are deployed to that planet afterward to attack the Jedi. A Sith ambush occurs when the Sith are deployed to the planet first, and they surprise Jedi that land on the planet afterward. One deployment comes “after”another one if it appears later in the file, even if the timestamps for the two deployments are the same.
For example, suppose you had these deployments:

Then the most exciting Sith attack on planet 0 would be the Sith with Force-sensitivity 40 attacking the Jedi with Force-sensitivity 10, but there would be no most-exciting Sith ambush because itʼs not possible for a the Sith deployment to be paired against a Jedi deployment that came later.
Notice that an actual battle need not happen. In this output, the first and second deployments would be paired in the regular output, not the first and the fourth. You should report only the most exciting hypothetical battle, regardless of which battles actually occurred.
If and only if the --watcher/-w option is specified on the command line, you should print the following line without any preceding newlines once at the very end of the program:

Followed by a pair of movie watcherʼs output lines for every planet in ascending order in the following format:
1 A movie watcher would enjoy an ambush on planet <PLANET_ID> with Sith at time <TIMESTAMP1> and Jedi at time <TIMESTAMP2> with a force difference of <NUM>.
2 A movie watcher would enjoy an attack on planet <PLANET_ID> with Jedi at time <TIMESTAMP1> and Sith at time <TIMESTAMP2> with a force difference of <NUM>.
When finding exciting battles, the number of troops is not taken into consideration. If there would be more than one battle with the maximal level of excitement (i.e., difference in Force-sensitivity), you should prefer the battle with the lower <TIMESTAMP2> . If the second timestamps are equal, then use the lower <TIMESTAMP1> .
If there are no exciting battles (there are no pairs of Jedi/Sith deployments on a given planet, or none result in the Jedi Force-sensitivity being less than or equal to the Sith Force-sensitivity) you should print a message like one of the following, as appropriate:
1 A movie watcher would not see an interesting ambush on planet <PLANET_ID>.
2 A movie watcher would not see an interesting attack on planet <PLANET_ID>. Detailed Simulation Algorithm

Following these steps in order will help guarantee that your program prints the correct output at the proper times.
The CURRENT_TIMESTAMP starts at 0, and is maintained throughout the run of the program.
. Print program startup output
. Read the next deployment from input
. If the new deploymentʼs TIMESTAMP is not the CURRENT_TIMESTAMP
a. If the --median/-m option is specified, print the median information b. Set CURRENT_TIMESTAMP to be the new deploymentʼs TIMESTAMP .
. Instigate all possible fights between the Jedi and Sith battalions
i. If the --verbose/-v option is specified, you should print the details of each completed
battle to stdout/cout
. Repeat steps 2-4 until there are no more deployments to be made.
. Output median information again if the --median option was specified. . Print end-of-day summary output.
. Output the general evaluation if the --general-eval option was specified. . Output the movie-watcherʼs output if the --watcher option was specified.
Full Example


11 Median troops lost on planet 0 at time 4 is 30.
12 Median troops lost on planet 1 at time 4 is 38.
13 ---End of Day---
14 Battles: 5
15 ---General Evaluation---
16 General 0 deployed 185 Jedi troops and 69 Sith troops, and 127/254 troops survived.
17 General 1 deployed 19 Jedi troops and 0 Sith troops, and 0/19 troops survived.
18 General 2 deployed 111 Jedi troops and 24 Sith troops, and 95/135 troops survived.
19 ---Movie Watcher---
20 A movie watcher would enjoy an ambush on planet 0 with Sith at time 2 and Jedi at time 3 with a force difference of 43.
21 A movie watcher would enjoy an attack on planet 0 with Jedi at time 2 and Sith at time 2 with a force difference of 29.
22 A movie watcher would enjoy an ambush on planet 1 with Sith at time 2 and Jedi at time 3 with a force difference of 31.
23 A movie watcher would enjoy an attack on planet 1 with Jedi at time 1 and Sith at time 2 with a force difference of 17.
The std::priority_queue<>

The STL std::priority_queue<> data structure is an efficient implementation of the binary heap which you will code in Part B. To declare a std::priority_queue<> you need to state either one or three types:
. The data type to be stored in the container. If this type has a natural sort order that meets your needs, this is the only type required.
. The underlying container to use, usually just a vector<> of the first type.
. The comparator to use to define what is considered the highest priority element.
If the type that you store in the container has a natural sort order (i.e. it supports operator<() ), the priority_queue<> will be a max-heap of the declared type. For example, if you just want to store integers, and have the largest integer be the highest priority:

When you declare this, by default the underlying storage type is vector<int> and the default comparator is less<int> . If you want the smallest integer to be the highest priority:
priority_queue<int, vector<int>, greater<int>> pqMin;
If you want to store something other than integers, define a custom comparator.
About Comparators

The functor must accept two of whatever is stored in your priority queue: if your PQ stores integers, the functor would accept two integers. If your PQ stores pointers to units, your functor would accept two pointers to orders (actually two const pointers, since you donʼt have to modify units to compare them).
Your functor receives two parameters, letʼs call them a and b. It must always answer the following question: is the priority of a less than the priority of b? What does lower priority mean? It depends on your application. For example, refer back to Battle Simulation if you have multiple Jedi deployed on the same planet, which Jedi has the highest priority if a Sith arrives? In the same way, Sith have a different way of determining the highest priority. This means you will need at least two different functors: one for a priority queue containing Jedi and a different functor for a priority queue containing Sith.
When you would have wanted to write a comparison, such as:

You would instead write:

Your priority queues must work in general. In general, a priority queue has no idea what kind of data is inside of it. Thatʼs why it uses this->compare instead of < . What if you wanted to perform the comparison if (data[i] > data[j]) ? Use the following:

Submitting your solution

Project Identifier

You MUST include the project identifier at the top of all source and header files that you submit:
// Project Identifier: AD48FB4835AF347EB0CA8009E24C3B13F8519882
Do all of your work (with all needed files, as well as test files) in some directory other than your home directory. This will be your “submit directory”. )
Libraries and Restrictions

We highly encourage the use of the STL for part A, with the exception of these prohibited features:
The thread/atomics libraries (e.g., boost, pthreads, etc) which spoil runtime measurements.
Smart pointers (both unique and shared).
Testing and Debugging

Part of this project is to prepare several test files that expose defects in a solution. Each test file is an input file. We will give your test files as input to intentionally buggy solutions and compare the output to that of a correct project solution. You will receive points depending on how many buggy implementations your test files expose. The autograder will also tell you if one of your test files exposes bugs in your solution. For the first such file that the autograder finds, it will give you the correct output and the output of your program.
Test File Details

Test files should be named in the following format: test-<N>-<OPTION>.txt
<N> is an integer in the range [0,9]
<OPTION> is one (and only one) of the following characters v , m , g , or w .
This tells the autograder which command-line option to test with.
For example, test-0-w.txt and test-5-v.txt are both valid test file names.
The tests on which the autograder runs your solution are NOT limited to 30 deployments in a file; your solution should not impose any size limits (as long as memory is available)
Submitting to the Autograder

Do all of your work (with all needed files, as well as test files) in some directory other than your home directory. This will be your “submit directory” Before you turn in your code, be sure that:
Every source code and header file contains the following project identifier in a comment at the top of the file:
// Project Identifier: AD48FB4835AF347EB0CA8009E24C3B13F8519882 The Makefile must also have this identifier (in the first TODO block).
DO NOT copy the above identifier from the PDF! It might contain hidden characters. Copy it from the README file from Canvas instead.
Your makefile is called Makefile . Typing make -R -r builds your code without errors and generates an executable file called galaxy . (The command-line options -R and -r disable automatic build rules; these automatic rules do not exist on the autograder).
Your Makefile specifies that you are compiling with the gcc optimization option -O3 . This is extremely important for getting all of the performance points, as -O3 can speed up code by an order of magnitude.
The total size of your program and test files does not exceed 2MB.
You donʼt have any unnecessary files (including temporary files created by your text editor and compiler, etc) or subdirectories in your submit directory (e.g., the .git folder used by git source code management).
Your code compiles and runs correctly using the g++ compiler. This is available on the CAEN Linux systems (that you can access via login.engin.umich.edu. Even if everything seems to work on another operating system or with different versions of GCC, the course staff will not support anything other than GCC running on CAEN Linux. At the moment, the default version installed on CAEN is 4.8.5, however we want you to use version 6.2.0 (available on CAEN with a command and/or Makefile); this version is also installed on the autograder machines.
For Part A (galactic combat simulation), turn in all of the following files:
All your .h(pp) and or .cpp files for the project (NOT including your priority queue implementations) Your Makefile
Your test files
For Part B (priority queues), turn in all of the following files:
Your priority queue implementations: SortedPQ.h, BinaryPQ.h, PairingPQ.h
Your Makefile (actually optional, it includes itself, but weʼll replace this with our Makefile )
If any of your submitted priority queue files do not compile, no unit testing (Part B) can be performed.
You must prepare a compressed tar archive (.tar.gz file) of all of your files to submit to the autograder. One way to do this is to have all of your files for submission (and nothing else) in one directory. Our Makefile provides the command make fullsubmit . Alternately you can go into this directory and run this command:
dos2unix *; tar czf ./submit.tar.gz *.cpp *.h *.hpp Makefile test*.txt This will prepare a suitable file in your working directory.
Submit your project files directly to either of the two autograders at:
Please make sure that you read all messages shown at the top section of your autograder results! These messages often help explain some of the issues you are having (such as losing points for having a bad Makefile or why you are segfaulting). Also be sure to check whether the autograder shows that one of your own test files exposes a bug in your solution.
Grading
60 pts total for part A (all your code, using the STL, but not using your priority queues)
45 pts — correctness & performance
5 pts — no memory leaks
10 pts — student-provided test files to find bugs in our code (and yours!)
40 pts total for part B (our main, your priority queues)
20 pts — pairing heap correctness & performance
5 pts — pairing heap has no memory leaks
10 pts — binary heap correctness & performance
5 pts — sorted heap correctness & performance
In your autograder output for Part A, the section named “Scoring student test files” will tell you how many bugs exist, how many are needed to start earning points, earn full points, and earn an extra submit per day (for Part A).
Part B: Priority Queues

The Part B Spec is in a separate document. The solution to Part B will be submitted separately from Part A, and should be developed separately in your development environment, with the files from both solutions stored in separate directories.
Final Notes

If youʼre asked about “cool projects” in an interview, note that this is simply a different wrapper on a more “marketable” project: stock market simulation. Sith and Jedi are like buyers and sellers, planets are commodities, and generals are stock market traders!
The “movie watcher mode” is a particular type of algorithm called a “streaming algorithm” where we can only look at each input once, and cannot make a copy of all the input. This is similar to a stock market simulation also, where if we could go back in time, we could determine the optimal point at which to buy and then later sell the same commodity (planet) to achieve the highest profit margin.