1. [65%] The following abstract class Container is given: class Container { public: virtual void insert(int x) = 0; virtual int remove() = 0; virtual bool empty() const = 0; virtual ~Container(); }; where the virtual destructor has the trivial implementation: Container::~Container() { } The idea is that int items can be inserted into a container, and later retrieved by the remove function. The order in which the items will be retrieved depends on the implementation of subclasses. The header file and implementation file for the Container class can be found in: [container.h] [container.cpp]. You are NOT allowed to modify these files. Doing so will result in SEVERE mark deduction. Implement three concrete subclasses of Container: Queue This class implements a first-in-first-out retrieval strategy. Specifically, items are retrieved in the same order they are inserted. Items that are inserted early will be removed first. As for data representation, you want to reuse ManagedArray by composition. Items are always inserted to the end of the managed array, and removed from the front of the managed array. In this way, early arrivers will leave early. Stack This class implements a last-in-first-out retrieval strategy. Specifically, items are retrieved in an order opposite to the order in which they are inserted. That is, items that are inserted late will be removed first. Again, you want to reuse ManagedArray by composition. Items are always inserted to the end of the managed array, and removed from the end as well. Consequently, late arrivers will be removed first. PriorityQueue This class retrives elements in ascending order of their values. Specifically, items that are smaller in values are removed first. Yet again, you want to reuse ManagedArray by composition. Items in the managed array must be sorted at all time. Insertion must honor this class invariant. (In a sense, such a container is merely a simplified variant of a sorted list.) Items must be removed from the front of the managed array, so that the smallest item is always removed first. Put EACH of the classes into its own header (.h) and implementation (.cpp) files. The following code is provided to you. guarded_array.h guarded_array.cpp managed_array.h managed_array.cpp You are NOT allowed to modify these files. Violation of this requirement will result in SEVERE mark deduction. Before attempting this question, you probably want to review the following lecture notes. Object-Oriented Programming Inheritance / Dynamic Binding You do not need to worry about virtual destructor because ManagedArray manages its own memory. Don't even bother to override the virtual destructure in the three subclasses. 2. [35%] Consider the following function. void process_sequence(Container& c) { int x; // Read input sequence cin >> x; while (cin) { c.insert(x); cin >> x; } // Write output sequence while (! c.empty()) { cout << c.remove() << endl; } } The function reads integer entries from the standard input stream (i.e., cin), stores them in a container, and then prints the entries to the standard output stream (i.e., cout). The order in which the entries are printed depends on the actual type of the container that is passed in via parameter c. The header file and implementation file of the above function can be found in: [process.h] [process.cpp]. You are NOT allowed to modify these files. Doing so will result in SEVERE mark deduction. Reuse the above function to implement the following three (3) programs (i.e., write three main functions). Each of the program reads from the standard input stream a sequence of integers of arbitrary length, reorders the sequence, and then prints the reordered sequence to the standard output stream. sort The output sequence is a sorted in ascending order. reverse The output sequence is obtained by reversing the order of the input sequence. nop The output sequence is in the same order as the input sequence.