Question

Template Deque Class (C++)

In this assignment, we will use a given test menu for the template 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 linked list
	#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 list
	template<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 deque
	template<class T>
	class Deque {
	Node<T> *head, *tail, *copy;
	int size;
	// deep copy helper
	void deepCopy( const Deque<T> & rhs );
	public:
	Deque():head(nullptr), tail(nullptr), size(0) { }
	Deque( const Deque<T> & rhs ); // copy constructor
	Deque( Deque<T> && rhs ); // move constructor
	Deque<T> & operator= ( Deque<T> & rhs ); // copy operator=
	Deque<T> & operator= ( Deque<T> && rhs ); // move operator=
	// Operations on Deque
	void 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 list to be copied
	size = rhs.size;//copy the head node
	copy = newNode; //create the node
	copy->data = current->data; //copy the info
	copy->next = current->next; //set the link field of the node to nullptr
	copy->prev = current->prev;
	tail = head; //make tail point to the head node
	current = current->next; //make current point to the next node
	//copy the remaining list
	while (current != nullptr) {
	newNode = new Node<T>; //create a node
	newNode->data = current->data; //copy the info
	newNode->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 class
	int 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 functions
	const int g_arrayElements = 10000;
	class Timer
	{
	private:
	// Type aliases to make accessing nested type easier
	using 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 {
	return std::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 the time we get there)
	for (int startIndex = 0; startIndex < g_arrayElements - 1; ++startIndex)
	{
	// smallestIndex is the index of the smallest element we’ve encountered this iteration
	// Start by assuming the smallest element is the first element of this iteration
	int smallestIndex = startIndex;
	// Then look for a smaller element in the rest of the array
	for (int currentIndex = startIndex + 1; currentIndex < g_arrayElements; ++currentIndex)
	{
	// If we've found an element that is smaller than our previously found smallest
	if (array[currentIndex] < array[smallestIndex])
	// then keep track of it
	smallestIndex = currentIndex;
	}
	// smallestIndex is now the smallest element in the remaining array
	// swap our start element with our smallest element (this sorts it 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() << " seconds\n";
	return 0;
	}

Example Test Driver

Github/m10/as10_testDeque_starter.cpp

It is very easy to miss how to invoke a Move Constructor. On line # 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 correct validation

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:

Answer 1

//insertion at head

void pushHead(T data)

{

Node *newnode=getnode(data);

if(newnode==NULL)

cout<<" deque overflow";

else

if(head==NULL)

tail=head=newnode;

else

{

newnode->next=head;

head->prev=newnode;

head=newnode;

}

}

//insertion at tail

void pushTail(T data)

{

Node *newnode=getnode(data);

if(newnode==NULL)

cout<<" deque overflow";

else

if(tail==NULL)

head=tail=newnode;

else

{

newnode->prev=tail;

tail->next=newnode;

tail=newnode;

}

}

//deletion from head

void popHead()

{

if(head==NULL)

cout<<"underflow";

else

{

temp=head;

head=head->next;

if(head==NULL)

tail=NULL;

else

head->prev=NULL;

}

//deletion from tail

void popTail()

{

if(tail==NULL)

cout<<"underflow";

else

{

temp=tail;

tail=taill->prev;

if(tail==NULL)

head=NULL;

else

tail->next=NULL;

}