Question

I've posted 3 classes after the instruction that were given at start

You will implement and test a PriorityQueue class, where the items of the priority queue are stored on a linked list. The material from Ch1 ~ 8 of the textbook can help you tremendously. You can get a lot of good information about implementing this assignment from chapter 8.

There are couple notes about this assignment. 1. Using structure Node with a pointer point to Node structure to create a linked list, the definition of the Note structure is in the priority queue header file (pqueue1.h). 2. Using a typedef statement to define the underlying data type, we can easily change to a new data type on all the typedef data type by change one statement. 3. Abandoning the usage of linked list toolkit, all the needed function will be implemented in the class.

I want to mention it again you that you are welcome to use more advance skills than the techniques introduce in the textbook to do the assignment. But the implemented class needs to pass the examining file to get credit.

Following is an introduction to some files in this program.

pqueue1.h is the headers file for this first version of the PriorityQueue class. You can start from this version and add your name and other documentation information at the top. Please look into and understand the structure Note. Without understanding this, you will have tough time to finish this project. Reading through this file carefully you need to know what functions you need to implement and the preconditions and postcondition of each function. This file should be a good guide to your implementation of the class. By the way if a member function of a class is an inline function, it is implemented in this file. You don’t need to redo it in the implementation file which is pqueue1.cpp.

pqueue1.cpp is the implementation file for the PriorityQueue class. You need to create this file and implement all the function defined in the pqueue1.cpp. I want to bring to you attention that the PriorityQueue's linked list consists of allocating memory. So we have to define a copy constructor, an assignment operator, and also a destructor to cope with the demand of dynamic memories allocation.

pqtest.cpp is the same style interactive test program that you used in the previous assignments. You can open it with your editor or import it to a compiler project to run with the pqueue1.cpp and pqueue1.h.

pqexam1.cpp is the same style non-interactive examine program as you use in the previous assignment. You can add this file to a compiler to run with the pqueue1.cpp and pqueue1.h to grade your pqueue1.cpp implementation.

CISP430V4A4Exam.exe is an executable file which you can generate this file by compiling and running the pqexam1.cpp, pqueue1.cpp (proper implemented) and pqueue1.h. When you click it you can see the following results.

file one (pqexam1.cpp)

#include <string.h> // Provides memcpy.

#include <stdlib.h> // Provides size_t.

#include "pqueue1.h" // Provides the PriorityQueue class.

#include <iostream>

using std::cout;

using std::cin;

using std::endl;

using std::flush;

// Descriptions and points for each of the tests:

const size_t MANY_TESTS = 4;

const int POINTS[MANY_TESTS+1] = {

200, // Total points for all tests.

100, // Test 1 points

   50, // Test 2 points

   25, // Test 3 points

   25 // Test 4 points

};

const char DESCRIPTION[MANY_TESTS+1][256] = {

"tests for the PriorityQueue class",

"simple tests of insert and get_front",

"Testing for possible heap leaks",

"Testing the copy constructor",

"Testing the assignment operator"

};

// **************************************************************************

// Replacements for new and delete:

// The next two functions replace the new and delete operators. Any code

// that is linked with this .cxx file will use these replacements instead

// of the standard new and delete. The replacements provide three features:

// 1. The global variable memory_used_now keeps track of how much memory has

// been allocated by calls to new. (The global variable is static so that

// it cannot be accessed outside of this .cxx file.)

// 2. The new operator fills all newly allocated memory with a GARBAGE char.

// 3. Each block of newly allocated memory is preceeded and followed by a

// border of BORDER_SIZE characters. The first part of the front border

// contains a copy of the size of the allocated memory. The rest of the

// border contains a BORDER char.

// During any delete operation, the border characters are checked. If any

// border character has been changed from BORDER to something else, then an

// error message is printed and the program is halted. This stops most

// cases of writing beyond the ends of the allocated memory.

// **************************************************************************

const size_t BORDER_SIZE = 2*sizeof(double);

const char GARBAGE = 'g';

const char BORDER = 'b';

static size_t memory_used_now = 0;

void* operator new(size_t size)

{

char *whole_block; // Pointer to the entire block that we get from heap

size_t *size_spot; // Spot in the block where to store a copy of size

char *front_border; // The border bytes in front of the user's memory

char *middle; // The memory to be given to the calling program

char *back_border; // The border bytes at the back of the user's memory

size_t i; // Loop control variable

// Allocate the block of memory for the user and for the two borders.

whole_block = (char *) malloc(2*BORDER_SIZE + size);

if (whole_block == NULL)

{

cout << "Insufficient memory for a call to the new operator." << endl;

exit(0);

}

// Figure out the start points of the various pieces of the block.

size_spot = (size_t *) whole_block;

front_border = (char *) (whole_block + sizeof(size_t));

middle = (char *) (whole_block + BORDER_SIZE);

back_border = middle + size;

// Put a copy of the size at the start of the block.

*size_spot = size;

// Fill the borders and the middle section.

for (i = 0; i < BORDER_SIZE - sizeof(size_t); i++)

front_border[i] = BORDER;

for (i = 0; i < size; i++)

middle[i] = GARBAGE;

for (i = 0; i < BORDER_SIZE; i++)

back_border[i] = BORDER;

// Update the global static variable showing how much memory is now used.

memory_used_now += size;

  

return middle;

}

void operator delete(void* p)

{

char *whole_block; // Pointer to the entire block that we get from heap

size_t *size_spot; // Spot in the block where to store a copy of size

char *front_border; // The border bytes in front of the user's memory

char *middle; // The memory to be given to the calling program

char *back_border; // The border bytes at the back of the user's memory

size_t i; // Loop control variable

size_t size; // Size of the block being returned

bool corrupt; // Set to true if the border was corrupted

// Figure out the start of the pieces of the block, and the size.

whole_block = ((char *) (p)) - BORDER_SIZE;

size_spot = (size_t *) whole_block;

size = *size_spot;

front_border = (char *) (whole_block + sizeof(size_t));

middle = (char *) (whole_block + BORDER_SIZE);

back_border = middle + size;

// Check the borders for the BORDER character.

corrupt = false;

for (i = 0; i < BORDER_SIZE - sizeof(size_t); i++)

if (front_border[i] != BORDER)

corrupt = true;

for (i = 0; i < BORDER_SIZE; i++)

if (back_border[i] != BORDER)

corrupt = true;

if (corrupt)

{

cout << "The delete operator has detected that the program wrote\n";

cout << "beyond the ends of a block of memory that was allocated\n";

cout << "by the new operator. Program will be halted." << endl;

exit(0);

}

else

{

// Fill memory with garbage in case program tries to use it

// even after the delete.

for (i = 0; i < size + 2*BORDER_SIZE; i++)

whole_block[i] = GARBAGE;

free(whole_block);

memory_used_now -= size;

}

  

}

// **************************************************************************

// bool correct(PriorityQueue& test, size_t n, int items[])

// Postcondition: Some tests have been run on the test priority queue.

// If this priority queue has n items, and these items are items[0]

// through items[n-1] (in that order), then the function has printed

// "Test passed." to cout and returned true. Otherwise the function

// has printed "Test failed." to cout and returned false.

// NOTE: If all tests were passed, then the test PriorityQueue has

// also been emptied.

// **************************************************************************

bool correct(PriorityQueue& test, size_t n, int items[])

// Postcondition: Some tests have been run on the test priority queue.

// If this priority queue has n items, and these items are items[0]

// through items[n-1] (in that order), then the function has printed

// "Test passed." to cout and returned true. Otherwise the function

// has printed "Test failed." to cout and returned false.

// NOTE: If all tests were passed, then the test PriorityQueue has

// also been emptied.

{

size_t i;

bool answer = true;

if (test.size( ) != n)

answer = false;

else if (test.is_empty( ) != (n == 0))

answer = false;

else

for (i = 0; answer && (i < n); i++)

if (items[i] != test.get_front( ))

answer = false;

cout << (answer ? "Test passed.\n" : "Test failed.\n") << endl;

return answer;

}

int test1( )

// Postcondition: A handful of simple tests have been run on the

// PriorityQueue data type. If all tests are passed, then the function

// returns POINTS[1]. Otherwise the function returns zero.

{

// A random test will be done with TEST_SIZE elements. Each

// element will have a priority below PRIORITY_LIMIT.

const size_t TEST_SIZE = 400;

const unsigned int PRIORITY_LIMIT = 100;

  

PriorityQueue test;

int items[8] = { 100, 200, 3, 4, 5, 6, 8, 7 };

int occurs[PRIORITY_LIMIT];

int rand_items[TEST_SIZE];

char test_letter = 'A';

int i;

unsigned int priority;

cout << test_letter++ << ". ";

cout << "Testing size and is_empty for an empty priority queue.";

cout << endl;

if (!correct(test, 0, items)) return 0;

cout << test_letter++ << ". ";

cout << "Adding one item to the queue, and then testing\n";

cout << " is_empty, size, and get_front.";

cout << endl;

test.insert(100, 1);

if (!correct(test, 1, items)) return 0;

cout << test_letter++ << ". ";

cout << "Inserting two items (first has higher priority).\n";

cout << " Then checking that both items come out correctly.";

cout << endl;

test.insert(100, 10);

test.insert(200, 5);

if (!correct(test, 2, items)) return 0;

cout << test_letter++ << ". ";

cout << "Inserting two items (second has higher priority).\n";

cout << " Then checking that both items come out correctly.";

cout << endl;

test.insert(200, 5);

test.insert(100, 10);

if (!correct(test, 2, items)) return 0;

cout << test_letter++ << ". ";

cout << "Inserting eight items with priorities of\n";

cout << " 8, 10, 3, 3, 8, 6, 10, 6 (in that order)\n";

cout << " Then checking that all items come out correctly.";

cout << endl;

test.insert(3, 8);

test.insert(100, 10);

test.insert(8, 3);

test.insert(7, 3);

test.insert(4, 8);

test.insert(5, 6);

test.insert(200, 10);

test.insert(6, 6);

if (!correct(test, 8, items)) return 0;

cout << test_letter++ << ". ";

cout << "Inserting " << TEST_SIZE << " random items with random\n";

cout << " priorities, and checking that all items come out right.";

cout << endl;

for (priority = 0; priority < PRIORITY_LIMIT; priority++)

occurs[priority] = 0;

for (i = 0; i < TEST_SIZE; i++)

{

// Insert a bunch of random items, using items themselves as priorities

priority = (unsigned) (rand( ) % 100);

test.insert((int) priority, priority);

occurs[priority]++;

}

priority = PRIORITY_LIMIT-1;

for (i = 0; i < TEST_SIZE; i++)

{

while (occurs[priority] == 0)

priority--;

rand_items[i] = (int) priority;

occurs[priority]--;

}

if (!correct(test, TEST_SIZE, rand_items)) return 0;

return POINTS[1];

}

  

// **************************************************************************

// int test2( )

// Tries to find a heap leak in the assignment operator or the

// destructor.

// Returns POINTS[2] if no leaks are found. Otherwise returns 0.

// **************************************************************************

int test2( )

{

const size_t TEST_SIZE = 200;

PriorityQueue test, empty;

PriorityQueue* pq_ptr;

size_t base_usage;

int i;

int next;

cout << "Checking for possible heap leak." << endl;

cout << "This could occur if the assignment operator, get_front, or\n";

cout << "the destructor does not correctly release memory.\n";

// Test get_front for a heap leak

cout << "Testing for heap leak in get_front..." << flush;

base_usage = memory_used_now;

for (i = 0; i < TEST_SIZE; i++)

test.insert(i, unsigned(i));

for (i = 0; i < TEST_SIZE; i++)

next = test.get_front( );

if (memory_used_now != base_usage)

{

cout << "\n Test failed. Probable heap leak in get_front." << endl;

return 0;

}

else

cout << "passed." << endl;

// Test for heap leak in destructor.

cout << "Testing for heap leak in destructor ... " << flush;

pq_ptr = new PriorityQueue;

for (i = 0; i < TEST_SIZE; i++)

pq_ptr->insert(i, unsigned(i));

delete pq_ptr;

if (memory_used_now != base_usage)

{

cout << "\n Test failed. Possible heap leak in copy constructor." << endl;

return 0;

}

else

cout << "passed." << endl;

// Test for heap leak in assignment operator.

cout << "Testing for heap leak in assignment operator ... " << flush;

for (i = 0; i < TEST_SIZE; i++)

test.insert(i, unsigned(i));

test = empty; // Should return test's list to the heap

if (memory_used_now != base_usage)

{

cout << "\n Test failed. Possible heap leak in assignment operator." << endl;

return 0;

}

else

cout << "passed." << endl;

cout << "No heap leaks found." << endl;

return POINTS[2];

}

int test3( )

// Postcondition: The PriorityQueue's copy constructor has been tested.

// The return value is 10 if the test was passed. Otherwise the return

// value is zero.

{

PriorityQueue test;

int items[4] = { 1, 2, 3, 4 };

cout << "A. Testing that copy constructor works okay for empty queue...";

cout << flush;

PriorityQueue copy1(test);

if (!correct(copy1, 0, items)) return 0;

cout << "B. Testing copy constructor with 4-item queue...";

cout << flush;

test.insert(1, 100);

test.insert(2, 50);

test.insert(3, 25);

test.insert(4, 10);

PriorityQueue copy2(test);

test.insert(5, 80); // Alter the original, but not the copy

if (!correct(copy2, 4, items)) return 0;

cout << "Copy constructor seems okay." << endl;

return POINTS[3];

}

int test4( )

// Postcondition: The PriorityQueue's assignment operator has been tested.

// The return value is 10 if the test was passed. Otherwise the return

// value is zero.

{

PriorityQueue test;

int items[4] = { 1, 2, 3, 4 };

char *oldbytes = new char[sizeof(PriorityQueue)];

char *newbytes = new char[sizeof(PriorityQueue)];

int i;

cout << "A. Testing that assignment operator works okay for empty queue...";

cout << flush;

PriorityQueue copy1;

copy1.insert(1,1);

copy1 = test;

if (!correct(copy1, 0, items)) return 0;

cout << "B. Testing assignment operator with 4-item queue...";

cout << flush;

test.insert(1, 100);

test.insert(2, 50);

test.insert(3, 25);

test.insert(4, 10);

PriorityQueue copy2;

copy2 = test;

test.insert(5, 80); // Alter the original, but not the copy

if (!correct(copy2, 4, items)) return 0;

cout << "C. Testing assignment operator for a self-assignment...";

cout << flush;

memcpy(oldbytes, &test, sizeof(PriorityQueue));

test = test;

memcpy(newbytes, &test, sizeof(PriorityQueue));

for (i=0; i < sizeof(PriorityQueue); i++)

if (oldbytes[i] != newbytes[i])

{

cout << "failed." << endl;

return 0;

}

cout << "passed.\n";

  

cout << "Assignment operator seems okay." << endl;

return POINTS[4];

}

int run_a_test(int number, const char message[], int test_function( ), int max)

{

int result;

  

cout << endl << "START OF TEST " << number << ":" << endl;

cout << message << " (" << max << " points)." << endl;

result = test_function( );

if (result > 0)

{

cout << "Test " << number << " got " << result << " points";

cout << " out of a possible " << max << "." << endl;

}

else

cout << "Test " << number << " failed." << endl;

cout << "END OF TEST " << number << "." << endl << endl;

  

return result;

}

// **************************************************************************

// int main( )

// The main program calls all tests and prints the sum of all points

// earned from the tests.

// **************************************************************************

int main( )

{

int sum = 0;

  

cout << "Running " << DESCRIPTION[0] << endl;

sum += run_a_test(1, DESCRIPTION[1], test1, POINTS[1]);

sum += run_a_test(2, DESCRIPTION[2], test2, POINTS[2]);

sum += run_a_test(3, DESCRIPTION[3], test3, POINTS[3]);

sum += run_a_test(4, DESCRIPTION[4], test4, POINTS[4]);

cout << "If you submit this PriorityQueue now, you will have\n";

cout << sum << " points out of the " << POINTS[0];

cout << " points from this test program.\n";

  

   system("PAUSE");

return EXIT_SUCCESS;

}

FILE TWO (pqtest.cpp)

// FILE: pqtest.cpp

// An interactive test program for the new List ADT.

#include <ctype.h> // Provides toupper

//#include <iostream.h> // Provides cout and cin

#include <stdlib.h> // Provides EXIT_SUCCESS and size_t

#include "pqueue1.h" // With Item defined as int

#include <iostream>

using std::cout;

using std::cin;

using std::endl;

// using std::flush;

// PROTOTYPES for functions used by this test program:

void print_menu( );

// Postcondition: A menu of choices for this program has been written to cout.

char get_user_command( );

// Postcondition: The user has been prompted to enter a one character command.

// The next character has been read (skipping blanks and newline characters),

// and this character has been returned.

int get_number(const char message[ ]);

// Postcondition: The user has been prompted to enter an integer. The

// number has been read, echoed to the screen, and returned by the function.

int main( )

{

PriorityQueue test; // A PriorityQueue that we'll perform tests on

char choice; // A command character entered by the user

  

cout << "I have initialized an empty Priority Queue." << endl;

cout << "The data entered into this Priority Queue will be integers,\n";

cout << "and each item also has an unsigned int for its priority." << endl;

do

{

print_menu( );

choice = toupper(get_user_command( ));

switch (choice)

{

case 'E': if (test.is_empty( ))

          cout << "The Priority Queue is empty." << endl;

else

              cout << "The Priority Queue is not empty." << endl;

      break;

case 'G': if (!test.is_empty( ))

   cout << "Front item is: " << test.get_front( ) << endl;

else

   cout << "There is no current item." << endl;

break;

case 'I': test.insert(

get_number("Please enter the next item: "),

(unsigned int) get_number("The item's priority: ")

);

break;

case 'S': cout << "The size is " << test.size( ) << endl;

break;

case 'Q': cout << "Ridicule is the best test of truth." << endl;

break;

default: cout << choice << " is invalid. Sorry." << endl;

}

}

while ((choice != 'Q'));

return EXIT_SUCCESS;

}

void print_menu( )

// Library facilities used: iostream.h

{

cout << endl; // Print blank line before the menu

cout << "The following choices are available: " << endl;

cout << " E Print the result from the is_empty( ) function" << endl;

cout << " G Print the result from the get_front( ) function" << endl;

cout << " I Insert a new item with the insert(...) function" << endl;

cout << " S Print the result from the size( ) function" << endl;

cout << " Q Quit this test program" << endl;

}

char get_user_command( )

// Library facilities used: iostream.h

{

char command;

cout << "Enter choice: ";

cin >> command; // Input of characters skips blanks and newline character

return command;

}

int get_number(const char message[ ])

// Library facilities used: iostream.h

{

int result;

  

cout << message << endl;

cin >> result;

cout << result << " has been read." << endl;

return result;

}

FILE THREE (pqueue1.h)

#ifndef PQUEUE_H

#define PQUEUE_H

#include <stdlib.h> // Provides size_t

struct Node; // This will be completely defined below.

class PriorityQueue

{

public:

typedef int Item;

PriorityQueue( );

PriorityQueue(const PriorityQueue& source);

~PriorityQueue( );

void operator =(const PriorityQueue& source);

size_t size( ) const { return many_nodes; }

void insert(const Item& entry, unsigned int priority);

Item get_front( );

bool is_empty( ) const { return many_nodes == 0; }

private:

// Note: head_ptr is the head pointer for a linked list that

// contains the items along with their priorities. These nodes are

// kept in order from highest priority (at the head of the list)

// to lowest priority (at the tail of the list). The private member

// variable, many_nodes, indicates how many nodes are on the list.

// The data type Node is completely defined below.

Node* head_ptr;

   size_t many_nodes;

};

struct Node

{ // Node for a linked list

PriorityQueue::Item data;

unsigned int priority;

Node *link;

};

#endif

Answer 1

1. CLASS PROVIDED: PriorityQueue (a priority queue of items)

2. //

3. // TYPEDEF for the PriorityQueue class:

4. // typedef _____ Item

5. // The type Item is the data type of the items in the Priority Queue.

6. // It may be any of the C++ built-in types (int, char, etc.), or a class

7. // with a default constructor, a copy constructor, and assignment operator.

8. //

9. // CONSTRUCTOR for the PriorityQueue class:

10. // PriorityQueue( )

11. // Postcondition: The PriorityQueue has been initialized with no Items.

12. //

13. // MODIFICATION MEMBER FUNCTIONS for the PriorityQueue class:

14. // void insert(const Item& entry, unsigned int priority)

15. // Postcondition: A new copy of entry has been inserted with the specified

16. // priority.

17. //

18. // Item get_front( )

19. // Precondition: size( ) > 0.

20. // Postcondition: The highest priority item has been returned and has been

21. // removed from the PriorityQueue. (If several items have equal priority,

22. // then the one that entered first will come out first.)

23. //

24. // CONSTANT MEMBER FUNCTIONS for the PriorityQueue class:

25. // size_t size( ) const

26. // Postcondition: Return value is the total number of items in the

27. // PriorityQueue.

28. //

29. // bool is_empty( ) const

30. // Postcondition: Return value is true if the PriorityQueue is empty.

31. //

32. // VALUE SEMANTICS for the PriorityQueue class:

33. // Assignments and the copy constructor may be used with

34. // PriorityQueue objects

35. #ifndef PQUEUE_H

36. #define PQUEUE_H

37. #include <stdlib.h> // Provides size_t

38.   struct Node; // This will be completely defined below.

39.   class PriorityQueue

40.   {

41.   public:

42.   typedef int Item;

43. PriorityQueue( );

44. PriorityQueue(const PriorityQueue& source);

45. ~PriorityQueue( );

46.   void operator =(const PriorityQueue& source);

47.   size_t size( ) const { return many_nodes; }

48.   void insert(const Item& entry, unsigned int priority);

49. Item get_front( );

50.   bool is_empty( ) const { return many_nodes == 0; }

51.   private:

52.   // Note: head_ptr is the head pointer for a linked list that

53.   // contains the items along with their priorities. These nodes are

54.   // kept in order from highest priority (at the head of the list)

55.   // to lowest priority (at the tail of the list). The private member

56.   // variable, many_nodes, indicates how many nodes are on the list.

57.   // The data type Node is completely defined below.

58. Node* head_ptr; // head pointer for a linked list

59.   size_t many_nodes;   // how many nodes are on teh list.

60.   };

61.   // the node has

62.   // priorityQueue

63.   // unsigned int

64.   // Node (which is array stuff)

65.   struct Node

66.   {   // Node for a linked list

67. PriorityQueue::Item data;  

68.   unsigned int priority;

69. Node *link;  

70.   };

71. #endif