This is a programming project, to be completed and graded on a Linux machine. You will perform modular design, provide a Makefile to compile various modules to generate the executable file named run. You need to have a module that provide the services including command line interpretation. You need to have a module that implement the min-heap data structure. You should use the C++ programming language, not any other programming language. Also, your program should be based on the g++ compiler. You need to define the following data types.

- ELEMENT is a data type that contains a field named key, which is of type int. Note that ELEMENT should not be of type int.

- HEAP is a data type that contains three fields named capacity (of type int), size (of type int), and H (an array of type ELEMENT with index ranging from 0 to capacity).

The functions that you are required to implement are

- Initialize(n) which returns an object of type HEAP with capacity n and size 0. This function requires you to perform dynamic memory allocation, given the demand.

- BuildHeap(heap, A), where heap is a HEAP object and A is an array of type ELEMENT. This function copies the elements in A into heap->H (starting from H[1] and uses the linear time build heap algorithm to obtain a min-heap of size from the given array A.

- Insert(heap, k, ag) which inserts an element with key equal to k into the min-heap heap. When ag=0, the function does not do any additional printing. When ag=1, the function prints out the heap content before the insertion, and the heap content after the insertion.

- DeleteMin(heap, ag) which deletes the element with minimum key and returns it to the caller. When ag=0, the function does not do any additional printing. When ag=1, the function prints out the heap content before the deletion, and the heap content after the deletion.

- DecreaseKey(heap, index, value, ag) which decreases the key field of the heap element pointed to by index to value, which should not be larger than the current value. Note that you have to make necessary adjustment to make sure that heap order is maintained. When ag=0, the function does not do any additional printing. When ag=1, the function prints out the heap content before the decrease key operation, and the heap content after the decrease key operation.

- printHeap(heap) which prints out the heap information, including capacity, size, and the key fields of the elements in the array with index going from 1 to size. You should implement a module that takes the following commands from the key-board and feed to the main program:

- S

- C n

- R

- W

- I k f

- D f

- K i v f

On reading S, the program stops.

On reading C n, the program creates an empty heap with capacity equal to n, and waits for the next command.

On reading R, the program reads in the array A from file HEAPinput.txt, calls the linear time build heap algorithm to build the min-heap based on A, and waits for the next command.

On reading W, the program writes the current heap information to the screen, and waits for the next command. The output should be in the same format as in the file HEAPinput.txt, proceeded by the heap capacity.

On reading I k f, the program inserts an element with key equal to k into the current heap with the corresponding ag set to f, and waits for the next command.

On reading D f, the program deletes the minimum element from the heap with the corresponding flag set to f, and prints the key field of the deleted element on the screen, it waits for the next command.

On reading K i v f, the program decreases the key of element with index i to v with the corresponding flag set to f.

The file HEAPinput.txt is a text file. The first line of the file contains an integer n, which indicates the number of array elements. The next n lines contain n integers, one integer per line. These integers are the key values of the n array elements, from the first element to the nth element.

As an aid, the following is a partial program for reading in the commands from the keyboard.

You need to understand it and to expand it.

#include "util.h"

//=============================================================================

int nextCommand(int *i, int *v, int *f)

{

char c;

while(1){

scanf("%c", &c);

if (c == ' ' || c == '\t' || c == ' '){

continue;

}

if (c == 'S' || c == 'R' || c == 'W'){

break;

}

if (c == 'K' || c == 'k'){

scanf("%d", i); scanf("%d", v); scanf("%d", v);

break;

}

if (...){

...

}

printf("Invalid Command ");

}

return c;

}

//=============================================================================

The following is a partial program that calls the above program.

//=============================================================================

#include

#include

#include "util.h"

int main()

{

// variables for the parser...

char c;

int i, v;

while(1){

c = nextCommand(&i, &v);

switch (c) {

case 's':

case 'S': printf("COMMAND: %c. ", c); exit(0);

case 'k':

case 'K': printf("COMMAND: %c %d %d. ", c, i, v); break;

default: break;

}

}

exit(0);

}

//=============================================================================

The following is a partial Make file.

EXEC = run

CC = g++

CFLAGS = -c -Wall

# $(EXEC) has the value of shell variable EXEC, which is run.

# run depends on the files main.o util.o heap.o

$(EXEC) :main.o util.o heap.o

# run is created by the command g++ -o run main.o util.o

# note that the TAB before $(CC) is REQUIRED...

$(CC) -o $(EXEC) main.o util.o heap.o

# main.o depends on the files main.h main.c

main.o:main.h main.cpp

# main.o is created by the command g++ -c -Wall main.cpp

# note that the TAB before $(CC) is REQUIRED...

$(CC) $(CFLAGS) main.cpp

util.o :util.h util.cpp

$(CC) $(CFLAGS) util.cpp

heap.o :heap.h heap.cpp

$(CC) $(CFLAGS) heap.cpp

clean :

rm *.o