C++ Programming Lab 11. Please only answer if you can do the ENTIRE problem. DO NOT MAKE YOUR OWN CPP FILES, VARIABLES, ETC. UPLOAD ALL OF THE EXACT .CPP AND .H FILES AS I HAVE THEM JUST COMPLETED. Reattach all files I have below even if you didn't have to edit one. Program MUST compile and all these instructions followed in order for me to give a thumbs up, thank you :-)

Parts to complete:

- implement the Heap ADT (the declaration is given in Heap.h)(80 points)

- Programming Exercise 3 (20 points)

- implement the Heap ADT (the declaration is given in Heap.h)

- Programming Exercise 1 (50 points)

- Programming Exercise 2 (50 points)

heapsort.cs

//-------------------------------------------------------------------- // // Laboratory 11, Programming Exercise 2 heapsort.cs // // (Shell) heapSort() function // //--------------------------------------------------------------------

template < typename DataType > void moveDown ( DataType dataItems [], int root, int size )

// Restores the binary tree that is rooted at root to a heap by moving // dataItems[root] downward until the tree satisfies the heap property. // Parameter size is the number of data items in the array.

{ // Your code here

}

//--------------------------------------------------------------------

template < typename DataType > void heapSort ( DataType dataItems [], int size )

// Heap sort routine. Sorts the data items in the array in ascending // order based on priority.

{ DataType temp; // Temporary storage int j; // Loop counter

// Build successively larger heaps within the array until the // entire array is a heap.

for ( j = (size-1)/2 ; j >= 0 ; j-- ) moveDown(dataItems,j,size);

// Swap the root data item from each successively smaller heap with // the last unsorted data item in the array. Restore the heap after // each exchange.

for ( j = size-1 ; j > 0 ; j-- ) { temp = dataItems[j]; dataItems[j] = dataItems[0]; dataItems[0] = temp; moveDown(dataItems,0,j); } }

ossim.cs

//--------------------------------------------------------------------

//

// Laboratory 11, Programming Exercise 1 ossim.cs

//

// (Shell) Operating system task scheduling simulation

//

//--------------------------------------------------------------------

// Simulates an operating system's use of a priority queue to regulate

// access to a system resource (printer, disk, etc.).

#include

#include

#include "PriorityQueue.cpp"

using namespace std;

//--------------------------------------------------------------------

//

// Declaration for the task data struct

//

struct TaskData

{

int getPriority () const

{ return priority; } // Returns the priority. Needed by the heap.

int priority, // Task's priority

arrived; // Time when task was enqueued

};

//--------------------------------------------------------------------

int main ()

{

PriorityQueue > taskPQ; // Priority queue of tasks

TaskData task; // Task

int simLength, // Length of simulation (minutes)

minute, // Current minute

numPtyLevels, // Number of priority levels

numArrivals, // Number of new tasks arriving

j; // Loop counter

// Seed the random number generator

srand( (unsigned int) time( NULL ) );

cout << endl << "Enter the number of priority levels : ";

cin >> numPtyLevels;

cout << "Enter the length of time to run the simulator : ";

cin >> simLength;

for ( minute = 0 ; minute < simLength ; minute++ )

{

// Dequeue the first task in the queue (if any).

// Your code here

// Determine the number of new tasks and add them to

// the queue.

// Your code here

}

return 0;

}

config.h

/**

* Heap class configuration file.

* Activate test #N by defining the corresponding LAB11_TESTN to have the value 1.

*/

#define LAB11_TEST1 0 // Programming Exercise 3: writeLevels

Heap.cpp

#include "Heap.h"

template < typename DataType, typename KeyType, typename Comparator >

Heap::Heap ( int maxNumber = DEFAULT_MAX_HEAP_SIZE )

{

}

template < typename DataType, typename KeyType, typename Comparator >

Heap::Heap ( const Heap& other )

{

}

template < typename DataType, typename KeyType, typename Comparator >

Heap& Heap::operator= ( const Heap& other )

{

}

template < typename DataType, typename KeyType, typename Comparator >

Heap::~Heap ()

{

}

template < typename DataType, typename KeyType, typename Comparator >

void Heap::insert ( const DataType &newDataItem )

throw ( logic_error )

{

}

template < typename DataType, typename KeyType, typename Comparator >

DataType Heap::remove () throw ( logic_error )

{

DataType temp;

return temp;

}

template < typename DataType, typename KeyType, typename Comparator >

void Heap::clear ()

{

}

template < typename DataType, typename KeyType, typename Comparator >

bool Heap::isEmpty () const

{

return false;

}

template < typename DataType, typename KeyType, typename Comparator >

bool Heap::isFull () const

{

return false;

}

#include "show11.cpp"

Heap.h

//--------------------------------------------------------------------

//

// Laboratory 12 Heap.h

//

// Class declaration for the array implementation of the Heap ADataType

//

//--------------------------------------------------------------------

#ifndef HEAP_H

#define HEAP_H

#pragma warning( disable : 4290 )

#include

#include

using namespace std;

template < typename KeyType=int >

class Less {

public:

bool operator()(const KeyType &a, const KeyType &b) const { return a < b; }

};

template < typename DataType, typename KeyType=int, typename Comparator=Less >

class Heap

{

public:

static const int DEFAULT_MAX_HEAP_SIZE = 10; // Default maximum heap size

// Constructor

Heap ( int maxNumber = DEFAULT_MAX_HEAP_SIZE ); // Default constructor + basic constr

Heap ( const Heap& other ); // Copy constructor

Heap& operator= ( const Heap& other ); // Overloaded assignment operator

// Destructor

~Heap ();

// Heap manipulation operations

void insert ( const DataType &newDataItem ) // Insert a data item

throw ( logic_error );

DataType remove () throw ( logic_error ); // Remove max priority element

void clear (); // Clear heap

// Heap status operations

bool isEmpty () const; // Heap is empty

bool isFull () const; // Heap is full

// Output the heap structure -- used in testing/debugging

void showStructure () const;

// Programming exercise #3 operation

void writeLevels () const; // Output in level order

private:

// Recursive helper of the showStructure() function

void showSubtree ( int index, int level ) const;

// Data members

int maxSize, // Maximum number of elements in the heap

size; // Actual number of elements in the heap

DataType *dataItems; // Array containing the heap elements

Comparator comparator;

};

#endif //#ifndef HEAP_H

PriorityQueue.cpp

//--------------------------------------------------------------------

//

// Laboratory 11, Programming Exercise 1 PriorityQueue.cpp

//

// ** SOLUTION: Heap implementation of the Priority Queue ADT **

//

//--------------------------------------------------------------------

#ifndef PRIORITYQUEUE_CPP

#define PRIORITYQUEUE_CPP

using namespace std;

#include "PriorityQueue.h"

//--------------------------------------------------------------------

template < typename DataType, typename KeyType, typename Comparator >

PriorityQueue:: PriorityQueue ( int maxNumber )

// Creates an empty priority queue.

{}

//--------------------------------------------------------------------

template < typename DataType, typename KeyType, typename Comparator >

void PriorityQueue:: enqueue ( const DataType &newDataItem )

// Inserts newDataItem into a priority queue.

{

}

//--------------------------------------------------------------------

template < typename DataType, typename KeyType, typename Comparator >

DataType PriorityQueue:: dequeue ()

// Removes the least recently added (front) data item from a priority

// queue and returns it.

{

}

#endif // #ifndef PRIORITYQUEUE_CPP

PriorityQueue.h

//-------------------------------------------------------------------- // // Laboratory 12, Programming Exercise 1 PriorityQueue.h // // Class declaration for the heap implementation of the // Priority Queue ADT -- inherits the array implementation of the // Heap ADT // //--------------------------------------------------------------------

#ifndef PRIORITYQUEUE_H #define PRIORITYQUEUE_H

#include #include

using namespace std;

#include "Heap.cpp"

const int defMaxQueueSize = 10; // Default maximum queue size

template < typename DataType, typename KeyType=int, typename Comparator=Less > class PriorityQueue : public Heap { public:

// Constructor PriorityQueue ( int maxNumber = defMaxQueueSize );

// Queue manipulation operations void enqueue ( const DataType &newDataItem ); // Enqueue data element DataType dequeue (); // Dequeue data element };

#endif

show11.cpp

#include "heap.h"

//-------------------------------------------------------------------- // // Laboratory 11 show11.cpp // // Array implementation of the showStructure operation for the // Heap ADT // //--------------------------------------------------------------------

template < typename DataType, typename KeyType, typename Comparator > void Heap:: showStructure () const

// Outputs the priorities of the data items in a heap in both array // and tree form. If the heap is empty, outputs "Empty heap". This // operation is intended for testing/debugging purposes only.

{ int j; // Loop counter

cout << endl; if ( size == 0 ) cout << "Empty heap" << endl; else { cout << "size = " << size << endl; // Output array form for ( j = 0 ; j < maxSize ; j++ ) cout << j << "\t"; cout << endl; for ( j = 0 ; j < size ; j++ ) cout << dataItems[j].getPriority() << "\t"; cout << endl << endl; showSubtree(0,0); // Output tree form } }

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < typename DataType, typename KeyType, typename Comparator > void Heap:: showSubtree ( int index, int level ) const

// Helper function for the showStructure() function. Outputs the // subtree (subheap) whose root is stored in dataItems[index]. Argument // level is the level of this dataItems within the tree.

{ int j; // Loop counter

if ( index < size ) { showSubtree(2*index+2,level+1); // Output right subtree for ( j = 0 ; j < level ; j++ ) // Tab over to level cout << "\t"; cout << " " << dataItems[index].getPriority(); // Output dataItems's priority if ( 2*index+2 < size ) // Output "connector" cout << "<"; else if ( 2*index+1 < size ) cout << "\\"; cout << endl; showSubtree(2*index+1,level+1); // Output left subtree } }

test11.cpp

//--------------------------------------------------------------------

//

// Laboratory 11 test11.cpp

//

// Test program for the operations in the Heap ADT

//

//--------------------------------------------------------------------

#include

#include

#include

using namespace std;

#include "Heap.cpp"

#include "config.h"

//--------------------------------------------------------------------

// Prototypes

void printHelp();

//--------------------------------------------------------------------

//

// Declaration for the heap data item class

//

template < typename KeyType >

class TestDataItem

{

public:

TestDataItem ()

{ priority = -1; }

void setPriority ( KeyType newPty )

{ priority = newPty; } // Set the priority

KeyType getPriority () const

{ return priority; } // Returns the priority

private:

KeyType priority; // Priority for the data item

};

template < typename KeyType=int >

class Greater {

public:

bool operator()( const KeyType &a, const KeyType &b) const { return a > b; }

};

int main()

{

// Greater<> uses the default int type for its KeyType

Heap, int, Greater<> > testHeap(8); // Test heap

TestDataItem testDataItem; // Heap data item

int inputPty; // User input priority

char cmd; // Input command

printHelp();

do

{

testHeap.showStructure(); // Output heap

cout << endl << "Command: "; // Read command

cin >> cmd;

cmd = toupper( cmd ); // Upcase input

if ( cmd == '+' )

cin >> inputPty;

switch ( cmd )

{

case 'H' :

printHelp();

break;

case '+' : // insert

testDataItem.setPriority(inputPty);

cout << "Insert : priority = " << testDataItem.getPriority()

<< endl;

testHeap.insert(testDataItem);

break;

case '-' : // remove

testDataItem = testHeap.remove();

cout << "Removed data item : "

<< " priority = " << testDataItem.getPriority() << endl;

break;

case 'C' : // clear

cout << "Clear the heap" << endl;

testHeap.clear();

break;

case 'E' : // isEmpty

if ( testHeap.isEmpty() )

cout << "Heap is empty" << endl;

else

cout << "Heap is NOT empty" << endl;

break;

case 'F' : // isFull

if ( testHeap.isFull() )

cout << "Heap is full" << endl;

else

cout << "Heap is NOT full" << endl;

break;

#if LAB11_TEST1

case 'W' : // Programming Exercise 3

cout << "Levels :" << endl;

testHeap.writeLevels();

break;

#endif // LAB11_TEST1

case 'Q' : // Quit test program

break;

default : // Invalid command

cout << "Inactive or invalid command" << endl;

}

}

while ( cmd != 'Q' );

return 0;

}

//--------------------------------------------------------------------

void printHelp()

{

cout << endl << "Commands:" << endl;

cout << " H : Help (displays this message)" << endl;

cout << " +pty : Insert data item with priority pty" << endl;

cout << " - : Remove highest priority data item" << endl;

cout << " C : Clear the heap" << endl;

cout << " E : Empty heap?" << endl;

cout << " F : Full heap?" << endl;

cout << " W : Write levels ("

#if LAB11_TEST1

"Active "

#else

"Inactive "

#endif //LAB11_TEST1

<< ": Programming Exercise 3)" << endl;

cout << " Q : Quit the test program" << endl;

cout << endl;

}

test11hs.cpp

//-------------------------------------------------------------------- // // Laboratory 11, Programming Exercise 2 test11hs.cpp // // Test program for for the heapSort() function // //--------------------------------------------------------------------

#include

using namespace std;

#include "heapsort.cpp"

//--------------------------------------------------------------------

class TestData { public:

void setPriority ( int newPriority ) { priority = newPriority; } // Set the priority

int getPriority () const { return priority; } // Returns the priority

private:

int priority; // Priority for the data item };

//--------------------------------------------------------------------

const int MAX_NUM_DATA_ITEMS = 10;

int main () { TestData testList[MAX_NUM_DATA_ITEMS]; // Array int size, // Number of data items inputPty, // Input priority j; // Loop counter

// Read in the array.

cout << endl << "Enter up to " << MAX_NUM_DATA_ITEMS << " priorities (end with EOF) : "; size = 0; while ( size < MAX_NUM_DATA_ITEMS && cin >> inputPty ) testList[size++].setPriority(inputPty);

// Output the unsorted array.

cout << "Unsorted array :"; for ( j = 0 ; j < size ; j++ ) cout << " " << testList[j].getPriority(); cout << endl;

// Sort the array using heap sort.

heapSort(testList,size);

// Output the sorted array.

cout << "Sorted array :"; for ( j = 0 ; j < size ; j++ ) cout << " " << testList[j].getPriority(); cout << endl; return 0; }

test11pq.cpp

//--------------------------------------------------------------------

//

// Laboratory 11, Programming Exercise 1 test11pq.cpp

//

// Test program for the operations in the Priority Queue ADT

//

//--------------------------------------------------------------------

#include

#include

#include "PriorityQueue.cpp"

using namespace std;

void printHelp();

//--------------------------------------------------------------------

//

// Declaration for the priority queue data item class

//

class TestData

{

public:

void setPriority ( int newPriority )

{ priority = newPriority; } // Set the priority

int getPriority () const

{ return priority; } // Returns the priority

private:

int priority; // Priority for the data item

};

//--------------------------------------------------------------------

int main()

{

PriorityQueue testQueue(8); // Test priority queue

TestData testData; // Queue data item

int inputPty; // User input priority

char cmd; // Input command

printHelp();

do

{

testQueue.showStructure(); // Output queue

cout << endl << "Command (H for help): "; // Read command

cin >> cmd;

cmd = toupper( cmd ); // Normalize to uppercase

if ( ( cmd == '+' ) || ( cmd == '>' ) )

cin >> inputPty;

switch ( cmd )

{

case '+' : // enqueue

testData.setPriority(inputPty);

cout << "Enqueue : pty = " << testData.getPriority()

<< endl;

testQueue.enqueue(testData);

break;

case '-' : // dequeue

testData = testQueue.dequeue();

cout << "Dequeued : pty = " << testData.getPriority()

<< endl;

break;

case 'C' :

cout << "Clear the queue" << endl;

testQueue.clear();

break;

case 'E' : // isEmpty

if ( testQueue.isEmpty() )

cout << "Queue is empty" << endl;

else

cout << "Queue is NOT empty" << endl;

break;

case 'F' : // isFull

if ( testQueue.isFull() )

cout << "Queue is full" << endl;

else

cout << "Queue is NOT full" << endl;

break;

case 'H' : // Print out help menu

printHelp();

break;

case 'Q' : // Quit test program

break;

default : // Invalid command

cout << "Invalid command" << endl;

}

}

while ( cmd != 'Q' );

return 0;

}

void printHelp() {

cout << endl << "Commands:" << endl;

cout << " +x : Enqueue data item with priority x" << endl;

cout << " - : Dequeue data item" << endl;

cout << " C : Clear the queue" << endl;

cout << " E : Empty queue?" << endl;

cout << " F : Full queue?" << endl;

cout << " H : Print this help message" << endl;

cout << " Q : Quit the test program" << endl;

cout << endl;

}