C++ Programming. Please only answer if you can do the ENTIRE problem. DO NOT MAK

ID: 3869129 • Letter: C

Question

C++ Programming. 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 <iostream>

#include <cstdlib>

#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<TaskData, int, Less<int> > 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<DataType,KeyType,Comparator>::Heap ( int maxNumber = DEFAULT_MAX_HEAP_SIZE )

{

}

template < typename DataType, typename KeyType, typename Comparator >

Heap<DataType,KeyType,Comparator>::Heap ( const Heap& other )

{

}

template < typename DataType, typename KeyType, typename Comparator >

Heap<DataType,KeyType,Comparator>& Heap<DataType,KeyType,Comparator>::operator= ( const Heap& other )

{

}

template < typename DataType, typename KeyType, typename Comparator >

Heap<DataType,KeyType,Comparator>::~Heap ()

{

}

template < typename DataType, typename KeyType, typename Comparator >

void Heap<DataType,KeyType,Comparator>::insert ( const DataType &newDataItem )

throw ( logic_error )

{

}

template < typename DataType, typename KeyType, typename Comparator >

DataType Heap<DataType,KeyType,Comparator>::remove () throw ( logic_error )

{

DataType temp;

return temp;

}

template < typename DataType, typename KeyType, typename Comparator >

void Heap<DataType,KeyType,Comparator>::clear ()

{

}

template < typename DataType, typename KeyType, typename Comparator >

bool Heap<DataType,KeyType,Comparator>::isEmpty () const

{

return false;

}

template < typename DataType, typename KeyType, typename Comparator >

bool Heap<DataType,KeyType,Comparator>::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 <stdexcept>

#include <iostream>

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<KeyType> >

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<DataType,KeyType,Comparator>:: PriorityQueue ( int maxNumber )

// Creates an empty priority queue.

{}

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

template < typename DataType, typename KeyType, typename Comparator >

void PriorityQueue<DataType,KeyType,Comparator>:: enqueue ( const DataType &newDataItem )

// Inserts newDataItem into a priority queue.

{

}

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

template < typename DataType, typename KeyType, typename Comparator >

DataType PriorityQueue<DataType,KeyType,Comparator>:: 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 <stdexcept>
#include <iostream>

using namespace std;

#include "Heap.cpp"

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

template < typename DataType, typename KeyType=int, typename Comparator=Less<KeyType> >
class PriorityQueue : public Heap<DataType>
{
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<DataType,KeyType,Comparator>:: 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 << " ";
cout << endl;
for ( j = 0 ; j < size ; j++ )
cout << dataItems[j].getPriority() << " ";
cout << endl << endl;
showSubtree(0,0); // Output tree form
}
}

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

template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType,KeyType,Comparator>:: 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 << " ";
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 <iostream>

#include <string>

#include <cctype>

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<TestDataItem<int>, int, Greater<> > testHeap(8); // Test heap

TestDataItem<int> testDataItem; // Heap data item

int inputPty; // User input priority

char cmd; // Input command

printHelp();

{

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 <iostream>

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 <iostream>

#include <cctype>

#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<TestData> testQueue(8); // Test priority queue

TestData testData; // Queue data item

int inputPty; // User input priority

char cmd; // Input command

printHelp();

{

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;

}

Explanation / Answer

void moveDown ( DataType dataItems [], int root, int size )