C++ Programming Lab 11. Please only answer if you can do the ENTIRE problem. DO
ID: 3869313 • 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
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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.