C++

For this computer assignment, you are to write a C++ program to sort items in several input files, using the heapsort technique. For each input file, your program first reads the items from the input file and builds a heap structure for these items. Then, it retrieves these items from the heap structure in order and prints them out on stdout. Full path names of the input files, certain constant definitions, and the prototypes of the function templates are included in the header file prog8.h,. Implement the following function templates in your program:

template < class T > void get_list ( vector < T >& v, const char* path ): It opens an input file for reading, then reads the items from the file and inserts them in a vector. Finally, it closes the input file. The first argument vto this function is the vector and the second argument path is the full path name of the input file.

template < class T, class P > void construct_heap ( vector < T >& v, P pred ): It constructs a heap structure from the items of vector v and uses the predicate pred to compare the items when building the heap. It calls the function make_heap ( ) to construct the heap and the function sort_heap ( ) to sort the items in the heap using the predicate pred. Both functions are from the STL.

The definition of the print_list class is included in the header file prog8.h. Implement its member functions (as templates) in your program:

template < class T > print_list < T > :: print_list ( const unsigned& s, const unsigned& w, const unsigned& l, const unsigned& c ): The constructor of the print_list class, where sis the heap size, w is the minimum number of chars written in printout, l is the maximum number of items printed in a single line, and cis used as a counter with the default value 0 that can be used to insert the newline characters in printout.

template < class T > void print_list < T > :: operator ( ) ( const T& x ): It can be used to print the item x of a heap on stdout. For proper printout, insert the following statements at the beginning of this function:

cout.width ( wid ); cout.precision ( 2 );

cout << fixed << showpoint;

The binary predicates greater < > ( ) and less < > ( ) (in STL) take two arguments and return a Boolean value to the calling routine. The call greater < T > ( x, y ) takes the arguments x and y as inputs, and if xis greater than y, it returns true; otherwise, it returns false; and the call less < T > ( x, y ) returns true if xis less than y; otherwise, it returns false. To build a heap, the driver program uses these two predicates.

The main ( ) routine for your program is given in the source file prog8main.cc, in the same directory with prog8.h. Copy this routine into your source file prog8.cc, and then add implementations of the subroutines defined above. This routine acts as a driver for your heap structure, where several vector objects are defined.

//prog8.h

#include

#include

#include

#include

#include

#include

using namespace std;

#ifndef H_PROG8

#define H_PROG8

#define INT_SZ 4 // width of integer

#define FLT_SZ 7 // width of floating-pt number

#define STR_SZ 12 // width of string

#define INT_LN 15 // no of integers in single line

#define FLT_LN 9 // no of floating-pt nums in single line

#define STR_LN 5 // no of strings in single line

// function and class prototypes

// stores items from input file into vector

template < class T >

void get_list(vector < T >&, const char*);

// construct heap from items in vector

template < class T, class P >

void construct_heap(vector < T >&, P);

// class to print heap items

template < class T >

class print_list {

unsigned sz, // heap size

wid, // min num of chars written in printout

len, // max num of items printed in single line

cnt; // counter for printout

public:

print_list(const unsigned& = 1, const unsigned& = 1,

const unsigned& = 1, const unsigned& = 0); // constructor

void operator ( ) (const T&);

};

#endif

//prog8-main.cc

#include"prog8.h"

int main()

{

vector < int > v1; // heap of integers

vector < float > v2; // heap of floating-pt nums

vector < string > v3; // heap of strings

// print header message

cout << "\t\t\t*** CSCI 340: Program 8 - Output *** ";

// first heap

cout << "first heap - ascending order: ";

get_list(v1, D1);

construct_heap(v1, less < int >());

print_list < int > print1(v1.size(), INT_SZ, INT_LN);

for_each(v1.begin(), v1.end(), print1);

cout << "first heap - descending order: ";

get_list(v1, D1);

construct_heap(v1, greater < int >());

for_each(v1.begin(), v1.end(), print1);

// second heap

cout << "second heap - ascending order: ";

get_list(v2, D2);

construct_heap(v2, less < float >());

print_list < float > print2(v2.size(), FLT_SZ, FLT_LN);

for_each(v2.begin(), v2.end(), print2);

cout << "second heap - descending order: ";

get_list(v2, D2);

construct_heap(v2, greater < float >());

for_each(v2.begin(), v2.end(), print2);

// third heap

cout << "third heap - ascending order: ";

get_list(v3, D3);

construct_heap(v3, less < string >());

print_list < string > print3(v3.size(), STR_SZ, STR_LN);

for_each(v3.begin(), v3.end(), print3);

cout << "third heap - descending order: ";

get_list(v3, D3);

construct_heap(v3, greater < string >());

for_each(v3.begin(), v3.end(), print3);

// print termination message

cout << "\t\t\t*** end of program execution *** ";

return 0;

}