[Solved]Template Deque Class C Assignment Use Given Test Menu Template Deque Class Linked List Bas Q37156825

Template Deque Class (C++)

In this assignment, we will use a given test menu for thetemplate Deque Class (a Linked List based Double Ended Queue,Deque) that you have put together.

Recommended Steps

testDeque.cpp :

// C++ implementation of doubly linked list Deque doubly linkedlist#include <bits/stdc++.h>using namespace std;class Timer {// To replace with the full timer class definition// inside this folder: LearnCpp9_18_timeSortArray.cpp};// Node of a doubly linked listtemplate<class T>class Node {public:T data;Node<T> *prev, *next;static Node<T>* getnode(int data) {Node<T>* n = new Node<T>;n->data = data;n->prev = n->next = nullptr;return n;}};// A doubly linked list dequetemplate<class T>class Deque {Node<T> *head, *tail, *copy;int size;// deep copy helpervoid deepCopy( const Deque<T> & rhs );public:Deque():head(nullptr), tail(nullptr), size(0) { }Deque( const Deque<T> & rhs ); // copyconstructorDeque( Deque<T> && rhs ); // moveconstructorDeque<T> & operator= ( Deque<T> & rhs ); //copy operator=Deque<T> & operator= ( Deque<T> && rhs); // move operator=// Operations on Dequevoid pushHead(T data);void pushTail(T data);void popHead();void popTail();void erase();T getFront();T getRear();int _size() { return size; }bool isEmpty() { return !head; }T& operator[] (const int &sub);};template<class T>void Deque<T>::deepCopy( const Deque<T> & rhs ){Node<T> *newNode = new Node<T>;Node<T> *current = rhs.head; //current points to the listto be copiedsize = rhs.size;//copy the head nodecopy = newNode; //create the nodecopy->data = current->data; //copy the infocopy->next = current->next; //set the link field of thenode to nullptrcopy->prev = current->prev;tail = head; //make tail point to the head nodecurrent = current->next; //make current point to the nextnode//copy the remaining listwhile (current != nullptr) {newNode = new Node<T>; //create a nodenewNode->data = current->data; //copy the infonewNode->next = current->next;newNode->prev = current->prev;tail->next = newNode;tail = newNode;current = current->next;}}// complete the rest of definitions below// Driver program to test the Link List Deque classint main() {Deque<int> dq;cout << “nInsert item ‘5’ at tail”;dq.pushTail(5);cout << “nInsert item ’10’ at tail”;dq.pushTail(10);cout << “nRear item: ” << dq.getRear();dq.popTail();cout << “nAfter deleting tail item, new tail is “<< dq.getRear();cout << “nInserting item ’15’ in head”;dq.pushHead(15);cout << “nFront item: ” << dq.getFront()<< “nNumber of items in Deque: ” <<dq._size();dq.popHead();cout << “nAfter deleting head item new head is “<< dq.getFront();dq.popHead();cout << “nAfter deleting head item new head is “<< dq.getFront();cout << “nInitializing a 10000 item Deque.”;Timer t1;for(int i=1; i<=10000; i++) dq.pushTail(i);cout << “nAdd 1~10000, dq now has “<< dq._size() << ” items.”;double run1 = t1.elapsed();cout << “nTime elipsed: ” << run1 << “seconds”;cout << “nDeep Copy construct dq2”;Timer t2;Deque<int> dq2( dq );double run2 = t2.elapsed();cout << “nTime elipsed: ” << run2 << “seconds”<< “ndq2 front to rear: ” << dq2.getFront()<< ” to ” << dq2.getRear();cout << “ndq2[0] is ” << dq2[0]<< “, dq2[1000] is ” << dq2[1000];cout << “nMove construct dq3”;Timer t3;Deque<int> dq3(std::move(dq));double run3 = t3.elapsed();cout << “nTime elipsed: ” << run3 << “seconds”<< “ndq3 front to rear: ” << dq3.getFront()<< ” to ” << dq3.getRear();cout << “ndq3[0] is ” << dq3[0]<< “, dq3[1000] is ” << dq3[1000];cout << “nAt this time, dq size is ” <<dq._size();}

LearnCpp8_16_timeSortArray.cpp:

#include <iostream>#include <array>#include <chrono> // for std::chrono functionsconst int g_arrayElements = 10000;class Timer{private:// Type aliases to make accessing nested type easierusing clock_t = std::chrono::high_resolution_clock;using second_t = std::chrono::duration<double,std::ratio<1> >;std::chrono::time_point<clock_t> m_beg;public:Timer() : m_beg(clock_t::now()) { }void reset() { m_beg = clock_t::now(); }double elapsed() const {returnstd::chrono::duration_cast<second_t>(clock_t::now() -m_beg).count();}};void sortArray(std::array<int, g_arrayElements>&array) {// Step through each element of the array// (except the last one, which will already be sorted by thetime we get there)for (int startIndex = 0; startIndex < g_arrayElements – 1;++startIndex){// smallestIndex is the index of the smallest element we’veencountered this iteration// Start by assuming the smallest element is the first elementof this iterationint smallestIndex = startIndex;// Then look for a smaller element in the rest of thearrayfor (int currentIndex = startIndex + 1; currentIndex <g_arrayElements; ++currentIndex){// If we’ve found an element that is smaller than ourpreviously found smallestif (array[currentIndex] < array[smallestIndex])// then keep track of itsmallestIndex = currentIndex;}// smallestIndex is now the smallest element in the remainingarray// swap our start element with our smallest element (this sortsit into the correct place)std::swap(array[startIndex], array[smallestIndex]);}}int main(){std::array<int, g_arrayElements> array;for (int i = 0; i < g_arrayElements; ++i)array[i] = g_arrayElements – i;Timer t;sortArray(array);std::cout << “Time taken: ” << t.elapsed() <<” secondsn”;return 0;}

Example Test Driver

Github/m10/as10_testDeque_starter.cpp

It is very easy to miss how to invoke a Move Constructor. Online # 132 above,

// <— this is how to enter the move argument Deque dq3(std::move(dq)); // < once dq is moved, it became empty!

the constructor is overloaded with the move argument!

Sample Test Run

Submit

1. AS10_testDeque.cpp
2. Deque.h and Timer.h
3. test (with the starter main ) and produce the correctvalidation

Recommended Steps Step 1. IntQ -> IntDeque 1. Bring up the starter, where the Node is a doubly Linked Node different from the AS9, a singly Linked Node 2. To move and adapt your AS9 IntLinkedQueue to AS10 as IntDeque where the Deque is a Double Ended Queue 3. Comment out all the auxiliary features in the main test driver 4. Add necessary test feature drivers, as you see fit. 5. Test to make sure all features are working correctly Step 2. Template the IntDeque -> Deque 1. Template the Class declaration and definition using proper template syntax 2. Test with two different primitive data types, and make sure all features are working correctly 3. Comment out, or remove the unused features in the main. 4. Test and verify Step 3. Subscript Operator (Lab 10A) 1. Create Overloading Operatorl 2. Test and verify the subscript operator [I directly in the test code (no user interface.) Step 4. Copy Constructor (Module 2) 1. Modify the Copy Constructor for this doubly linked list. 2. You may utilize the provided private helper deepCopy to make a local doubly linked list copy. Alternatively, challenge yourself to write your won! 3. Test and verify Step 5. Timer class (Lab 10B) 1. Add Timer class 2. You may use the provided private helper deepCopy0 is provided for making a duplicated Deque copy 3. Measure the Copy constructor (time) performance for creating a 10000 item Deque. The performance should be similar to the attached test output. Step 6. Move Constructor (Lab 10C) 1. Based on the Lab 10C, construct the Move Constructor per tutorials on the move semantics 2. Measure the Move constructor (time) performance for creating a 10000 item Deque Starter testDeque.cpp which contains 1. Timer class holder (you need to go through the LearnCpp Ch15 and import it in) 2. Node class 3. Deque class specification (you need to fill out the definition) Make sure you have implemented and validated the Stack/Queue member functions especially the following additional methods for AS9 subscription operator [] read and write (included instarter)I/ in assignment 10, your test driver main program shall access the operator[ directly, see the listing below subscription over the range exception (included in starter) Running/home/ubuntu/workspace/comsc200/w Insert item 5′ at tail Insert item ’10’ at tail Rear item: 10 After deleting tail item, new tail is 5 Inserting item ’15’ in head Front item: 15 Number of items in Deque: 2 After deleting head item new head is 5 After deleting head item new head is 0 Initializing a 10000 item Deque. Add 1~10000, dq now has 10000 items. Time elipsed: 0.000695639 seconds Deep Copy construct dq2 Time elipsed: 0.000772629 seconds dq2 front to rear: 1 to 10000 Move construct dq3 Time elipsed: q3 front to rear: 1 to dq3 [0] is 1, dq3 [1000] is 10 At this time, dq size is 0 Process exited with code: Show transcribed image text Recommended Steps Step 1. IntQ -> IntDeque 1. Bring up the starter, where the Node is a doubly Linked Node different from the AS9, a singly Linked Node 2. To move and adapt your AS9 IntLinkedQueue to AS10 as IntDeque where the Deque is a Double Ended Queue 3. Comment out all the auxiliary features in the main test driver 4. Add necessary test feature drivers, as you see fit. 5. Test to make sure all features are working correctly Step 2. Template the IntDeque -> Deque 1. Template the Class declaration and definition using proper template syntax 2. Test with two different primitive data types, and make sure all features are working correctly 3. Comment out, or remove the unused features in the main. 4. Test and verify Step 3. Subscript Operator (Lab 10A) 1. Create Overloading Operatorl 2. Test and verify the subscript operator [I directly in the test code (no user interface.) Step 4. Copy Constructor (Module 2) 1. Modify the Copy Constructor for this doubly linked list. 2. You may utilize the provided private helper deepCopy to make a local doubly linked list copy. Alternatively, challenge yourself to write your won! 3. Test and verify Step 5. Timer class (Lab 10B) 1. Add Timer class 2. You may use the provided private helper deepCopy0 is provided for making a duplicated Deque copy 3. Measure the Copy constructor (time) performance for creating a 10000 item Deque. The performance should be similar to the attached test output. Step 6. Move Constructor (Lab 10C) 1. Based on the Lab 10C, construct the Move Constructor per tutorials on the move semantics 2. Measure the Move constructor (time) performance for creating a 10000 item Deque Starter testDeque.cpp which contains 1. Timer class holder (you need to go through the LearnCpp Ch15 and import it in) 2. Node class 3. Deque class specification (you need to fill out the definition) Make sure you have implemented and validated the Stack/Queue member functions especially the following additional methods for AS9 subscription operator [] read and write (included instarter)I/ in assignment 10, your test driver main program shall access the operator[ directly, see the listing below subscription over the range exception (included in starter)
Running/home/ubuntu/workspace/comsc200/w Insert item 5′ at tail Insert item ’10’ at tail Rear item: 10 After deleting tail item, new tail is 5 Inserting item ’15’ in head Front item: 15 Number of items in Deque: 2 After deleting head item new head is 5 After deleting head item new head is 0 Initializing a 10000 item Deque. Add 1~10000, dq now has 10000 items. Time elipsed: 0.000695639 seconds Deep Copy construct dq2 Time elipsed: 0.000772629 seconds dq2 front to rear: 1 to 10000 Move construct dq3 Time elipsed: q3 front to rear: 1 to dq3 [0] is 1, dq3 [1000] is 10 At this time, dq size is 0 Process exited with code:

Expert Answer

---

Answer to Template Deque Class (C++) In this assignment, we will use a given test menu for the template Deque Class (a Linked Lis… . . .