C++ Programming Lab 11. Please only answer if you can do the ENTIRE problem. DO
ID: 3869314 • Letter: C
Question
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 <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();
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 <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();
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;
}
Explanation / Answer
Heap.cpp
------------------------------------
#ifndef HEAP_CPP
#define HEAP_CPP
#include <iostream>
#include <stdexcept>
#include "Heap.h"
using namespace std;
/** Default constructor
* instantiates an empty heap
*
* @param maxNumber maximum capacity of the Heap. Defined in Heap.h
*/
template< typename DataType, typename KeyType, typename Comparator>
Heap<DataType, KeyType, Comparator>::Heap(int maxNumber)
{
maxSize = maxNumber;
size = 0;
dataItems = new DataType[maxSize];
}
/** Copy constructor
* instantiates a new heap that is a clone of &other parameter
*
* @param other the heap that is to be cloned to *this heap
*/
template< typename DataType, typename KeyType, typename Comparator>
Heap<DataType, KeyType, Comparator>:: Heap(const Heap& other)
{
maxSize = 0;
size = 0;
dataItems = NULL;
*this = other;
}
/** Overloaded assignment operator
* clones the parameter other to *this heap
*
* @param other the heap whose data will be cloned
* @return *this the heap that is cloned from &other
*/
template< typename DataType, typename KeyType, typename Comparator>
Heap<DataType, KeyType, Comparator>& Heap<DataType, KeyType, Comparator>::
operator= (const Heap<DataType, KeyType, Comparator>& other)
{
// case *this is already the same as &other
if (this == &other)
{
// return *this
return *this;
}
// case not the same, utilize copy constructor
else {
Heap(&other);
}
}
/** Destructor
* calls clear() and deletes the conents
*
*/
template <typename DataType, typename KeyType, typename Comparator>
Heap <DataType, KeyType, Comparator>:: ~Heap()
{
clear();
}
/** Insert
* inserts new items into heap at appropriate locatoin. Item will have a lesser priority then any given
* parent, and will throw a logic error if full.
*
* @param newDataItem new dataItem to be inserted
*/
template <typename DataType, typename KeyType, typename Comparator>
void Heap <DataType, KeyType, Comparator>::insert(const DataType &newDataItem) throw (logic_error)
{
int tIndex = size; // temp index
int pIndex = size; // parent index location
bool heapify = true;
DataType temp;
// case heap is not full
if (size < maxSize)
{
dataItems[tIndex] = newDataItem;
size++;
// heapify till item is in proper locatoin
while (heapify)
{
//reset flag
heapify = false;
// case not root
if (tIndex > 0)
{
// parent location
pIndex = (tIndex - 1) / 2;
// case dataItem is greater then parent
if (comparator(dataItems[tIndex].getPriority(),
dataItems[pIndex].getPriority()))
{
// swap new item with parent
temp = dataItems[tIndex];
dataItems[tIndex] = dataItems[pIndex];
dataItems[pIndex] = temp;
// udpate new item
tIndex = pIndex;
// test again
heapify = true;
}
}
}
}
// case heap is full
else
{
throw logic_error("Error: Heap is full. ");
}
}
/** Remove
* removes the root item from the heap, and rebuilds the heaps priority.
*
* @return returnData the element that was at the root index of the heap.
*/
template <typename DataType, typename KeyType, typename Comparator>
DataType Heap <DataType, KeyType, Comparator>::remove() throw (logic_error)
{
// case heap is empty
if (isEmpty())
{
throw logic_error("Error: Heap is empty");
}
size--;
// store the root element in returnData of DataType
DataType returnData = dataItems[0];
// set root index to last element in heap
dataItems[0] = dataItems[size];
// establish relationships
int index = 0,
left = ((index * 2) + 1),
right = ((index * 2) + 2);
// case not at end of heap
while (index < size)
{
Comparator compare;
// case there is another right child remaining
if (right <= size)
{
// case index is greater than both childs
if (compare(dataItems[index].getPriority(), dataItems[left].getPriority()) &&
compare(dataItems[index].getPriority(), dataItems[right].getPriority()))
{
return returnData;
}
// case right child is greater then left child
else if (compare(dataItems[right].getPriority(), dataItems[left].getPriority()))
{
// swap index with right child
DataType temp = dataItems[index];
dataItems[index] = dataItems[right];
dataItems[right] = temp;
index = right;
}
else
{
// swap index with left child
DataType temp = dataItems[index];
dataItems[index] = dataItems[left];
dataItems[left] = temp;
index = left;
}
}
// case there remains a left child
else if (left <= size)
{
// case left child is greater then index
if (compare(dataItems[left].getPriority(), dataItems[index].getPriority()))
{
// swap index with left child
DataType temp = dataItems[index];
dataItems[index] = dataItems[left];
dataItems[left] = temp;
index = left;
}
// return removed element
else
{
return returnData;
}
}
else
{
return returnData;
}
}
return returnData;
}
/** clear
* empties the heap by setting the size to zero
*
*/
template <typename DataType, typename KeyType, typename Comparator>
void Heap <DataType, KeyType, Comparator>:: clear()
{
size = 0;
}
/** isEmpty
* indicates whether the heap has any elements by returning true if it does not,
* and false if it does
*
* @return bool true if empty
*/
template <typename DataType, typename KeyType, typename Comparator>
bool Heap <DataType, KeyType, Comparator>::isEmpty() const
{
// size = 0 when empty
return (size == 0);
}
/** isFull
* indicates whether the heap has any room left by returning true if it does not,
* and false if it does
*
* @return bool true if full
*/
template <typename DataType, typename KeyType, typename Comparator>
bool Heap <DataType, KeyType, Comparator>:: isFull() const
{
// size = maxSize when full
return (size == maxSize);
}
/** showStructure
* output the heap structure -- used in testing/debugging*
*/
template <typename datatype, typename keytype, typename comparator>
void Heap <datatype, keytype, comparator>:: showStructure() const
{
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
}
}
/** writeLevels
* Program 3 Exercise
*/
template <typename DataType, typename KeyType, typename Comparator>
void Heap <DataType, KeyType, Comparator>::writeLevels() const
{
int level = 1,
print = 0;
for (int i = 0; i < size; i++, print++)
{
if (print == level)
{
cout << endl;
print = 0;
level *= 2;
}
cout << dataItems[i].getPriority() << " ";
}
cout << endl;
}
/** showSubtree
* helper function for showStructure() function
*/
template <typename DataType, typename KeyType, typename Comparator>
void Heap<DataType, KeyType, Comparator>::showSubtree(int index,
int level) const
{
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();//OutputdataItem'spriority
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
}
}
#endif
----------------------------------------
Heap.h
---------------------
#ifndef HEAP_H
#define HEAP_H
#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
-----------------------------
#include "PriorityQueue.h"
#include <iostream>
#include <stdexcept>
using namespace std;
/** PriorityQueue
* default constructor for the PriorityQueue.
*
*/
template< typename DataType, typename KeyType, typename Comparator>
PriorityQueue< DataType, KeyType, Comparator>:: PriorityQueue(int maxNumber)
{}
/** enqueue
* inserts the data item into the PriorityQueue. Position depends on priority.
*
* Utilizes the Heap insert function, which will throw error if heap is full
*
* @param newDataItem the element to be enqueued into the PriorityQueue
*/
template< typename DataType, typename KeyType, typename Comparator>
void PriorityQueue< DataType, KeyType, Comparator>::enqueue(const DataType& newDataItem)
{
Heap<DataType, KeyType, Comparator>::insert(newDataItem);
}
/** dequeue
* removes the highest priority element in the PriorityQueue.
*
* Utilizes the Heap remove function, which will throw an error if array is empty
*
* @return item at the top of the PriorityQueue
*/
template< typename DataType, typename KeyType, typename Comparator>
DataType PriorityQueue< DataType, KeyType, Comparator>::dequeue()
{
return Heap<DataType>::remove();
}
-----------------------------------------------------------
PriorityQueue.h
-------------------------------
#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
--------------------------------------------------
config.h
---------------
#define LAB11_TEST1 0
-------------------------------------------
ossim.cpp
---------------------
#include <iostream>
#include <cstdlib>
#include <time.h>
#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;
cout << endl;
// run the simulation for simLength minutes
for ( minute = 0; minute < simLength; minute++ )
{
// Dequeue the first task in the queue (if any).
if (!taskPQ.isEmpty())
{
task = taskPQ.dequeue();
// output the informatoin
cout << "At " << minute << " Dequed Priority: " << task.getPriority()
<< " Arrived at: " << task.arrived << " Duration: " << (minute - task.arrived)
<< endl;
}
// Determine the number of new tasks and add them to
// the queue.
switch (rand() % 4)
{
case 1:
if (!taskPQ.isFull())
{
task.priority = rand() % numPtyLevels;
task.arrived = minute;
taskPQ.enqueue(task);
}
break;
case 2:
for (j = 0; j < 2 && !taskPQ.isFull(); j++)
{
task.priority = rand() % numPtyLevels;
task.arrived = minute;
taskPQ.enqueue(task);
}
break;
}
}
cin.get();
return 0;
}
-----------------------------------------------------
test11.cpp
----------------------------
#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();
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
----------------------------
#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
---------------------------------------
#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();
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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.