In C++

CMPT 225 Assignment 2 - Queue You are to implement and test a Queue template class. The class should use a linked list as its underlying representation. This assignment is worth 6% of your grade. Please read the requirements carefully, paying particular attention to the names and input and output requirements of the class and its methods. We will be testing your class in our program, so if you do not follow the requirements the test program will not compile and will not be marked. Queue Class Class Description Your class should be named QueueT and should support these operations: Creating an empty queue Inserting a value Removing a value Finding the size of the queue Printing the contents of the queue . Adding the contents of one queue to the end of another . Merging the contents of two queues into a third, new, queue Class Attributes Your class should be implemented using a linked list and should have the following private member variables . A pointer to a NodeT that represents the front of the queue . A pointer to a NodeT that represents the back of the queue . An int that records the current size of the queue (i.e. the number of values in the queue) Queue Public Methods You must implement a QueueT template class to store data of any type. The queue must be implemented using a singly linked list of Nodes, where NodeT is a class that you also implement. Note that the enqeue and degeue methods should be implemented in constant time. The Queuet class should implement the following public methods: constructor - creates an empty queue copy constructor - a constructor that creates a deep copy of its constant QueueT reference parameter destructor - deallocates dynamic memory allocated by the queue operator= - overloads the assignment operator for QueueT - (deep) copies its constant Queue T reference parameter into the calling object and returns a reference to the calling object after de-allocating any dynamic memory associated with the original contents of the calling object; if the calling object is equal to the parameter the operator should not copy it enqueue - inserts its template type parameter at the back of the queue dequeue - removes and returns the value at the front of the queue; if the queue is empty throws a runtime_error (this error class is defined in the stdexcept library file) print - prints the contents of the queue, one value per line, from front to back empty-returns true if the queue is empty, false otherwise size - returns the number of items stored in the queue concatenate - has two parameters, a QueueT reference and an integer (referred to as n in this description) adds the first n values stored in its QueueT parameter to the end of the calling object, the resulting queue therefore contains its original contents-order unchanged - followed by the first n values of the parameter queue in their original order; the values added to the calling object should be removed from the parameter; both queue's sizes should be adjusted as appropriate; if n is greater than the size of the parameter a runtime_error should be thrown and no changes made to either queue merge - returns a Queuet object that contains the contents of the calling object and its constant QueueT reference parameter, the resulting queue should start with the first value in the calling object, followed by the first value in the parameter, subsequent values should be copied - in order - from the two queues alternating between them; no changes should be made to either the calling object or the parameter; example: calling object = {a,b,c,d,e}, parameter = {r,s,t}, result = {a,r,b,s,c,t,d,e} getFront - returns a pointer to the node at the front of the queue. This method is provided to you here: NodeT* getFront() { return front; }; Its purpose is to allow us to directly access your queue's linked list for testing. It is not something a working class should include since allowing access to the internal structure of a class is not good design. Note that if you called your pointer to the node at the front of the queue something other than "front" you will need to change the method given above to return the correct attribute Additional Notes The calling object should be made constant for any method where the calling object's attribute values should not change You may implement helper methods if you wish (for example, you might want to implement a deep copy method that can be used by the copy constructor and the overloaded assignment operator) . Your class may include other private attributes that you deem necessary Method parameters and return values are noted (and highlighted) in the method descriptions - you must not add additional parameters to the methods; if the method description does not mention a parameter it does not have one, similarly if no return value is mentioned the method is void (or a constructor or destructor) The parameter type for enqeue and the return type of deqeue should be your template variable - see the implementation notes near the end of this document NodeT Class The Nodel class should have a template type attribute for its data and a pointer to the next NodeT in the list. These attributes must be made public and must be named data and next. The class should have constructors as you see fit - I would suggest one with two parameters that sets the data and next Node (pointer) to the parameter values and one with a single template type parameter that sets its next pointer to a nullptr. Your Node T class must be written in your Queue T.h file, above and outside the Queuet class definition. Your Node constructors should be written in the Node T class definition, and not in a separate NodeT.cpp file. Implementation Notes The way I would suggest approaching writing the assignment is something like this: 1. Create a new project with a file that contains a main function that you will use for testing; add a new QueueT class to the project; then compile and run your project to make sure it is set up correctly 2. Write your NodeT and Queuet classes as regular (non-template) classes that store a base type, like an int, testing methods as you implement them 3. Write, and thoroughly test, one or two functions at a time. 4. Once your class is working perfectly convert it into a template class Note that Bjarne Stroustrup recommends implementing template classes by first implementing a non-template class version - and I suspect his advice is worth following! File Structure Template classes are often contained in a single .h file as there are compilation issues with breaking them down into separate files, and this is what I want you to do for this assignment. I still want you to keep the implementation separate from the interface as much as possible within this structure, so your method implementations should appear below your Queuet class definition. Your .h file will therefore have this general structure. //include statements class NodeT{ //... includes constructor definitions ... class QueueT{ //QueueT method implementations QueueT::QueueT() Simple Test Below is a main function that you can use as a very simple and incomplete test of each of the methods that you are to implement. To reiterate - this is not an adequate test of your class! However, if you can't compile and run this simple test you know that your assignment is not ready for submission. int main() QueueT 91; 91. enqueue (2); 41. enqueue (4); 91. enqueue (6); cout 42(91); Queue Txint> q3; 93 = 91; 91. dequeue(); cout 94; 94. enqueue (5); QueueT 95(91.merge (94)); cout * front = 91.getFront(); cout next->data: 6 = " next->data; return ; Main Function You should write a main function in a separate file from your Queuet class, use your main function (and other test functions) to test your class methods. You should not submit the file containing the main function. I would strongly suggest compiling and running your program after you complete each method (or couple of methods), do not try to complete the entire class before testing it as this will almost certainly end up being considerably more work. Assessment The assignment is out of 67. Class definition - 4 marks Node class - 4 marks Methods - default constructor, print, empty, size - 2 marks (8); copy constructor, destructor, ops, enqueue, dequeue, concatenate, merge - 28 marks (); total - 36 Comments - 5 marks Naming - 5 marks Indentation - 3 marks Template - 5 marks Memory management -5 Compilation We will test your projects in Linux and use the g++ compiler with the -std=C++11 flag to compile them. While you are welcome to develop your solution in whatever environment you prefer you should make sure it can be compiled and run as described above. Solutions that cannot be compiled will not be marked. If you are unable to write a method, write a stub function for it. If you are unable to complete a method, comment out the non-functional sections of the method so that you receive marks for any test cases the method is able to pass. Memory Management We will run your program using valgrind. If your program shows memory errors, you will lose the five marks allocated to memory management. CMPT 225 Assignment 2 - Queue You are to implement and test a Queue template class. The class should use a linked list as its underlying representation. This assignment is worth 6% of your grade. Please read the requirements carefully, paying particular attention to the names and input and output requirements of the class and its methods. We will be testing your class in our program, so if you do not follow the requirements the test program will not compile and will not be marked. Queue Class Class Description Your class should be named QueueT and should support these operations: Creating an empty queue Inserting a value Removing a value Finding the size of the queue Printing the contents of the queue . Adding the contents of one queue to the end of another . Merging the contents of two queues into a third, new, queue Class Attributes Your class should be implemented using a linked list and should have the following private member variables . A pointer to a NodeT that represents the front of the queue . A pointer to a NodeT that represents the back of the queue . An int that records the current size of the queue (i.e. the number of values in the queue) Queue Public Methods You must implement a QueueT template class to store data of any type. The queue must be implemented using a singly linked list of Nodes, where NodeT is a class that you also implement. Note that the enqeue and degeue methods should be implemented in constant time. The Queuet class should implement the following public methods: constructor - creates an empty queue copy constructor - a constructor that creates a deep copy of its constant QueueT reference parameter destructor - deallocates dynamic memory allocated by the queue operator= - overloads the assignment operator for QueueT - (deep) copies its constant Queue T reference parameter into the calling object and returns a reference to the calling object after de-allocating any dynamic memory associated with the original contents of the calling object; if the calling object is equal to the parameter the operator should not copy it enqueue - inserts its template type parameter at the back of the queue dequeue - removes and returns the value at the front of the queue; if the queue is empty throws a runtime_error (this error class is defined in the stdexcept library file) print - prints the contents of the queue, one value per line, from front to back empty-returns true if the queue is empty, false otherwise size - returns the number of items stored in the queue concatenate - has two parameters, a QueueT reference and an integer (referred to as n in this description) adds the first n values stored in its QueueT parameter to the end of the calling object, the resulting queue therefore contains its original contents-order unchanged - followed by the first n values of the parameter queue in their original order; the values added to the calling object should be removed from the parameter; both queue's sizes should be adjusted as appropriate; if n is greater than the size of the parameter a runtime_error should be thrown and no changes made to either queue merge - returns a Queuet object that contains the contents of the calling object and its constant QueueT reference parameter, the resulting queue should start with the first value in the calling object, followed by the first value in the parameter, subsequent values should be copied - in order - from the two queues alternating between them; no changes should be made to either the calling object or the parameter; example: calling object = {a,b,c,d,e}, parameter = {r,s,t}, result = {a,r,b,s,c,t,d,e} getFront - returns a pointer to the node at the front of the queue. This method is provided to you here: NodeT* getFront() { return front; }; Its purpose is to allow us to directly access your queue's linked list for testing. It is not something a working class should include since allowing access to the internal structure of a class is not good design. Note that if you called your pointer to the node at the front of the queue something other than "front" you will need to change the method given above to return the correct attribute Additional Notes The calling object should be made constant for any method where the calling object's attribute values should not change You may implement helper methods if you wish (for example, you might want to implement a deep copy method that can be used by the copy constructor and the overloaded assignment operator) . Your class may include other private attributes that you deem necessary Method parameters and return values are noted (and highlighted) in the method descriptions - you must not add additional parameters to the methods; if the method description does not mention a parameter it does not have one, similarly if no return value is mentioned the method is void (or a constructor or destructor) The parameter type for enqeue and the return type of deqeue should be your template variable - see the implementation notes near the end of this document NodeT Class The Nodel class should have a template type attribute for its data and a pointer to the next NodeT in the list. These attributes must be made public and must be named data and next. The class should have constructors as you see fit - I would suggest one with two parameters that sets the data and next Node (pointer) to the parameter values and one with a single template type parameter that sets its next pointer to a nullptr. Your Node T class must be written in your Queue T.h file, above and outside the Queuet class definition. Your Node constructors should be written in the Node T class definition, and not in a separate NodeT.cpp file. Implementation Notes The way I would suggest approaching writing the assignment is something like this: 1. Create a new project with a file that contains a main function that you will use for testing; add a new QueueT class to the project; then compile and run your project to make sure it is set up correctly 2. Write your NodeT and Queuet classes as regular (non-template) classes that store a base type, like an int, testing methods as you implement them 3. Write, and thoroughly test, one or two functions at a time. 4. Once your class is working perfectly convert it into a template class Note that Bjarne Stroustrup recommends implementing template classes by first implementing a non-template class version - and I suspect his advice is worth following! File Structure Template classes are often contained in a single .h file as there are compilation issues with breaking them down into separate files, and this is what I want you to do for this assignment. I still want you to keep the implementation separate from the interface as much as possible within this structure, so your method implementations should appear below your Queuet class definition. Your .h file will therefore have this general structure. //include statements class NodeT{ //... includes constructor definitions ... class QueueT{ //QueueT method implementations QueueT::QueueT() Simple Test Below is a main function that you can use as a very simple and incomplete test of each of the methods that you are to implement. To reiterate - this is not an adequate test of your class! However, if you can't compile and run this simple test you know that your assignment is not ready for submission. int main() QueueT 91; 91. enqueue (2); 41. enqueue (4); 91. enqueue (6); cout 42(91); Queue Txint> q3; 93 = 91; 91. dequeue(); cout 94; 94. enqueue (5); QueueT 95(91.merge (94)); cout * front = 91.getFront(); cout next->data: 6 = " next->data; return ; Main Function You should write a main function in a separate file from your Queuet class, use your main function (and other test functions) to test your class methods. You should not submit the file containing the main function. I would strongly suggest compiling and running your program after you complete each method (or couple of methods), do not try to complete the entire class before testing it as this will almost certainly end up being considerably more work. Assessment The assignment is out of 67. Class definition - 4 marks Node class - 4 marks Methods - default constructor, print, empty, size - 2 marks (8); copy constructor, destructor, ops, enqueue, dequeue, concatenate, merge - 28 marks (); total - 36 Comments - 5 marks Naming - 5 marks Indentation - 3 marks Template - 5 marks Memory management -5 Compilation We will test your projects in Linux and use the g++ compiler with the -std=C++11 flag to compile them. While you are welcome to develop your solution in whatever environment you prefer you should make sure it can be compiled and run as described above. Solutions that cannot be compiled will not be marked. If you are unable to write a method, write a stub function for it. If you are unable to complete a method, comment out the non-functional sections of the method so that you receive marks for any test cases the method is able to pass. Memory Management We will run your program using valgrind. If your program shows memory errors, you will lose the five marks allocated to memory management