This part of the assignment is an exercise in implementing the list ADT using a doubly-linked list. You will need to write a template structure to represent a list node, and a template class to represent the list. The setup is essentially similar to Assignment 7 all of the code will be placed in a single header file (List.h), the overloaded stream insertion operator will need to be forward declared, etc. A driver program is available to test your implementation: /home/turing/t90kjm1/CS241/Code/Spring2018/Honors10/assign10.cpp

The driver program contains code to test all three parts of the assignment. During your development process, simply comment out any code that references classes or methods you have not written yet.

Program struct Node Data members This template structure should have three data members: a member of the template parameter type to store a data item to be inserted into the list, a pointer to the previous Node in the list, and a pointer to the next Node in the list.

Methods Constructor The structure should have a constructor that can be used to initialize the data members of the list node.

class List Data members This class should have three data members. The first should be a pointer to a Node which will point to the front node in the list. The second should be a pointer to a Node which will point to the back node in the list. The third should be a size_t or unsigned integer that will be used to store the list size, the number of items currently stored in the list.

Methods and associated functions The List class should implement the following methods and functions. (Most of these are very similar to methods from the Queue class on Assignment 7.) template List::List() The class should have a default constructor that sets both pointer data members of the list to nullptr and the list size to 0

. template List::~List() The class should have a destructor. The destructor can simply call the clear() method.

template List::List(const List& other) The class should have a proper copy constructor. If you choose to make a copy of the linked list by using the push_back() method, make sure you set both the list front and list back pointers for the new list to nullptr and the list size to 0 before you attempt to insert any nodes into it.

template List& List::operator=(const List& other) The assignment operator should be properly overloaded.

template void List::clear() This method should properly set the list back to the empty state, deleting all of the nodes in the list.

template size_t List::size() const Returns the list size.

template bool List::empty() const Returns true if the list size is 0; otherwise, returns false.

template const T& List::front() const This method should return the data of the front node in the list. You may assume that it will not be called if the list is empty. template T& List::front() This method should return the data of the front node in the list. You may assume that it will not be called if the list is empty.

template const T& List::back() const This method should return the data of the back node in the list. You may assume that it will not be called if the list is empty.

template T& List::back() This method should return the data of the back node in the list. You may assume that it will not be called if the list is empty.

template void List::push_front(const T& val) This method should insert an item at the front of the list. See the Implementation Hints below for help on writing this method.

template void List::push_back(const T& val) This method should insert an item at the back of the list. See the Implementation Hints below for help on writing this method.

template void List::pop_front() This method should remove the item at the front of the list. You may assume it will not be called if the list is empty. See the Implementation Hints below for help on writing this method.

template void List::pop_back() This method should remove the item at the back of the list. You may assume it will not be called if the list is empty. See the Implementation Hints below for help on writing this method.

template bool List::operator==(const List& rhs) const The equality operator should be overloaded to allow the comparison of two List objects. This method returns true if 1) the two lists contain the same number of nodes, and 2) if each data element of the left list is equal to the corresponding element of the right list. Otherwise the method returns false. (This is similar in principal to the overloaded equality operator you wrote for Assignment 5.)

template bool List::operator<(const List& rhs) const The less than operator should be overloaded to allow the comparison of two List objects. This method will perform a lexicographical comparison of the two lists. Lexicographical comparison means dictionary (element-by-element) ordering. That is, list1 is less than list2 if the first data element of list1 is less than the first data element of list2, and greater if the first data element of list1 is greater than the first data element of list2. If the two first data elements are equivalent then the method compares the two second data elements, and so on. The first list is also considered to be less than the second if every data element in the first list is equal to the corresponding data element in the second but the second list contains more data elements.

template std::ostream& operator<<(std::ostream& lhs, const List& rhs) The output operator should be overloaded so that an entire List object can be sent to the standard output. As usual, this function will need to be a friend rather than a method.

Implementation Hints For some hints on implementing push_back(), push_front(), pop_back(), and pop_front(), see the Notes on Doubly-Linked List Insertion and Deletion on the course web site.

Other Notes In the interest of saving time, you do not need to write any documentation for any of the parts of this assignment (unless you want to). A makefile is required as usual. You do not need to submit the three parts of the assignment separately, just your finished version.

Driver Code :

#include #include #include #include "List.h"

using std::cout; using std::endl; using std::make_pair; using std::pair; using std::string;

int main() { //********// // PART 1 // //********//

cout << "===== PART 1 ===== ";

cout << "*** Testing default constructor *** ";

List l1;

cout << "*** Testing size(), operator<<(), and empty() with empty list *** ";

cout << "l1 (size " << l1.size() << "): " << l1 << endl; cout << "l1 is " << ((l1.empty()) ? "empty " : "not empty ");

cout << "*** Testing push_back() into empty list *** ";

l1.push_back(40);

cout << "*** Testing size(), operator<<(), and empty() with non-empty list *** ";

cout << "l1 (size " << l1.size() << "): " << l1 << endl; cout << "l1 is " << ((l1.empty()) ? "empty " : "not empty ");

cout << "*** Testing push_back() into non-empty list *** ";

l1.push_back(50); l1.push_back(60);

cout << "l1 (size " << l1.size() << "): " << l1 << endl << endl;

List l2;

cout << "*** Testing push_front() into empty list *** ";//

l2.push_front('c');

cout << "l2 (size " << l2.size() << "): " << l2 << endl << endl;

cout << "*** Testing push_front() into non-empty list *** ";

l2.push_front('b'); l2.push_front('a');

cout << "l2 (size " << l2.size() << "): " << l2 << endl << endl;

cout << "*** Testing push_front() and push_back() *** ";

l1.push_front(30); l1.push_front(20); l1.push_front(10);

l2.push_back('d'); l2.push_back('e'); l2.push_back('f');

cout << "l1 (size " << l1.size() << "): " << l1 << endl; cout << "l2 (size " << l2.size() << "): " << l2 << endl << endl;

cout << "*** Testing read version of front() and back() *** ";

cout << "l1 front: " << l1.front() << endl; cout << "l1 back: " << l1.back() << endl << endl;

cout << "*** Testing write version of front() and back() *** ";

l1.front() = 5; l1.back() = 65;

cout << "l1 front: " << l1.front() << endl; cout << "l1 back: " << l1.back() << endl << endl;

cout << "*** Testing pop_back() *** ";

l2.pop_back(); l2.pop_back();

cout << "l2 (size " << l2.size() << "): " << l2 << endl << endl;

cout << "*** Testing pop_front() *** ";

l2.pop_front(); l2.pop_front();

cout << "l2 (size " << l2.size() << "): " << l2 << endl << endl;

cout << "*** Testing pop to empty *** ";

l2.pop_back(); l2.pop_front();

cout << "l2 (size " << l2.size() << "): " << l2 << endl << endl;

cout << "*** Testing copy constructor *** ";

List l3 = l1;

cout << "l1 (size " << l1.size() << "): " << l1 << endl; cout << "l3 (size " << l3.size() << "): " << l3 << endl << endl;

cout << "*** Testing for shallow copy *** ";

l1.front() = 10; l1.back() = 60;

cout << "l1 (size " << l1.size() << "): " << l1 << endl; cout << "l3 (size " << l3.size() << "): " << l3 << endl << endl;

cout << "*** Testing copy assignment operator *** ";

l1.push_back(70); l1.push_back(80);

l3 = l1;

cout << "l1 (size " << l1.size() << "): " << l1 << endl; cout << "l3 (size " << l3.size() << "): " << l3 << endl << endl;

cout << "*** Testing for shallow copy *** ";

l1.push_back(90); l3.pop_front();

cout << "l1 (size " << l1.size() << "): " << l1 << endl; cout << "l3 (size " << l3.size() << "): " << l3 << endl << endl;

cout << "*** Testing self-assignment *** ";

l1 = l1;

cout << "l1 (size " << l1.size() << "): " << l1 << endl << endl;

cout << "*** Testing chained assignment *** ";

List l4;

l4 = l3 = l1;

cout << "l1 (size " << l1.size() << "): " << l1 << endl; cout << "l3 (size " << l3.size() << "): " << l3 << endl; cout << "l4 (size " << l4.size() << "): " << l4 << endl << endl;

cout << "*** Testing equality operator *** ";

cout << "l1 and l4 are " << ((l1 == l4) ? "equal " : "not equal ");

l3.back() = -8;

cout << "l1 and l3 are " << ((l1 == l3) ? "equal " : "not equal ");

l4.pop_front();

cout << "l1 and l4 are " << ((l1 == l4) ? "equal " : "not equal ");

cout << "*** Testing less than operator *** ";

cout << "l1 is " << ((l1 < l4) ? "less than" : "not less than") << " l4 "; cout << "l4 is " << ((l4 < l1) ? "less than" : "not less than") << " l1 "; cout << "l1 is " << ((l1 < l1) ? "less than" : "not less than") << " l1 "; cout << "l1 is " << ((l1 < l3) ? "less than" : "not less than") << " l3 "; cout << "l3 is " << ((l3 < l1) ? "less than" : "not less than") << " l1 ";

l3.pop_back();

cout << "l1 is " << ((l1 < l3) ? "less than" : "not less than") << " l3 "; cout << "l3 is " << ((l3 < l1) ? "less than" : "not less than") << " l1 ";

cout << "*** Testing clear() *** ";

l1.clear();

cout << "l1 (size " << l1.size() << "): " << l1 << endl << endl;

cout << "*** Testing for const correctness *** ";

List& r4 = l4;

cout << "l4 (size " << r4.size() << "): " << r4 << endl; cout << "l4 is " << ((r4.empty()) ? "empty " : "not empty "); cout << "l4 front: " << r4.front() << endl; cout << "l4 back: " << r4.back() << endl; cout << "l4 and l1 are " << ((r4 == l1) ? "equal " : "not equal "); cout << "l4 is " << ((r4 < l3) ? "less than" : "not less than") << " l3 "; cout << "l4 is " << ((r4 < l1) ? "less than" : "not less than") << " l1 "; cout << "l1 is " << ((l1 < r4) ? "less than" : "not less than") << " l4 ";

//********// // PART 2 // //********// /* cout << "===== PART 2 ===== ";

for (int i = 15; i < 90; i += 10) l1.push_back(i);

cout << "l1 (size " << l1.size() << "): " << l1 << endl << endl;

cout << "*** Testing default constructor and begin() *** ";

Iterator itr1;

itr1 = l1.begin();

cout << "*** Testing operator*() *** ";

cout << "First list element: " << *itr1 << endl << endl;

cout << "*** Testing prefix form of operator++() *** ";

cout << "Second list element: " << *(++itr1) << endl << endl;

cout << "*** Testing postfix form of operator++() *** ";

cout << "Second list element: " << *(itr1++) << endl; cout << "Third list element: " << *itr1 << endl << endl;

cout << "*** Testing prefix form of operator--() *** ";

cout << "Second list element: " << *(--itr1) << endl << endl;

cout << "*** Testing postfix form of operator--() *** ";

cout << "Second list element: " << *(itr1--) << endl; cout << "First list element: " << *itr1 << endl << endl;

cout << "*** Testing alternate constructor *** ";

Iterator itr2(nullptr);

cout << "*** Testing operator==() *** ";

cout << "itr1 and l1.begin() are " << ((itr1 == l1.begin()) ? "equal " : "not equal "); cout << "itr1 and l1.end() are " << ((itr1 == l1.end()) ? "equal " : "not equal "); cout << "itr2 and l1.end() are " << ((itr2 == l1.end()) ? "equal " : "not equal "); cout << "itr1 and itr2() are " << ((itr1 == itr2) ? "equal " : "not equal ");

cout << "*** Testing operator!=() *** ";

cout << "itr1 and l1.begin() are " << ((itr1 != l1.begin()) ? "not equal " : "equal "); cout << "itr1 and l1.end() are " << ((itr1 != l1.end()) ? "not equal " : "equal "); cout << "itr2 and l1.end() are " << ((itr2 != l1.end()) ? "not equal " : "equal "); cout << "itr1 and itr2() are " << ((itr1 != itr2) ? "not equal " : "equal ");

cout << "*** Testing begin(), end(), and operator->() *** ";

List > l5;

l5.push_back(make_pair("Joe Murphy", 3.75)); l5.push_back(make_pair("Sam Melton", 3.87)); l5.push_back(make_pair("Carl Miller", 2.63)); l5.push_back(make_pair("Mike Piazza", 2.59)); l5.push_back(make_pair("John Deberge", 3.52));

for (Iterator > itr = l5.begin(); itr != l5.end(); ++itr) cout << itr->first << ", " << itr->second << endl;

cout << endl;

//********/// // PART 3 // //********// /* cout << "===== PART 3 ===== ";

l1.clear();

cout << "*** Testing insert() at beginning of empty list *** ";

itr1 = l1.insert(l1.begin(), 28); cout << "l1 (size " << l1.size() << "): " << l1 << endl << endl;

cout << "*** Testing insert() at beginning of non-empty list *** ";

l1.insert(itr1, 17); cout << "l1 (size " << l1.size() << "): " << l1 << endl << endl;

cout << "*** Testing insert() at end of list *** ";

itr1 = l1.insert(l1.end(), 47); cout << "l1 (size " << l1.size() << "): " << l1 << endl << endl;

cout << "*** Testing insert() in middle of non-empty list *** ";

l1.insert(itr1, 35); cout << "l1 (size " << l1.size() << "): " << l1 << endl << endl;

l1.push_back(53); l1.push_back(61);

cout << "*** Testing erase() at front of list *** ";

itr1 = l1.begin(); itr1 = l1.erase(itr1); cout << "l1 (size " << l1.size() << "): " << l1 << endl; cout << "Iterator now points to: " << *itr1<< endl << endl;

cout << "*** Testing erase() in middle of list *** ";

++itr1; ++itr1;

itr1 = l1.erase(itr1); cout << "l1 (size " << l1.size() << "): " << l1 << endl; cout << "Iterator now points to: " << *itr1<< endl << endl;

cout << "*** Testing erase() at back of list *** ";

++itr1;

l1.erase(itr1); cout << "l1 (size " << l1.size() << "): " << l1 << endl << endl;

cout << "*** Testing remove(10) on empty list *** ";

l1.clear(); l1.remove(10); cout << "l1 (size " << l1.size() << "): " << l1 << endl << endl;

cout << "*** Testing remove(10) on non-empty list *** ";

int array1[] = {10, 62, 25, 10, 32, 58, 10, 16, 10, 43, 10};

for (int i = 0; i < 11; ++i) l1.push_back(array1[i]);

cout << "Before - l1 (size " << l1.size() << "): " << l1 << endl; l1.remove(10); cout << "After - l1 (size " << l1.size() << "): " << l1 << endl << endl;

//**************/// // EXTRA CREDIT // //**************// /* cout << "===== EXTRA CREDIT ===== ";

cout << "*** Testing splice() of empty list into non-empty list *** ";

l3.clear();

cout << "Before: " << " l1 (size " << l1.size() << "): " << l1 << endl << " l3 (size " << l3.size() << "): " << l3 << endl;

l1.splice(l1.begin(), l3);

cout << "After: " << " l1 (size " << l1.size() << "): " << l1 << endl << " l3 (size " << l3.size() << "): " << l3 << endl << endl;

cout << "*** Testing splice() of non-empty list into empty list *** ";

cout << "Before: " << " l1 (size " << l1.size() << "): " << l1 << endl << " l3 (size " << l3.size() << "): " << l3 << endl;

l3.splice(l3.begin(), l1);

cout << "After: " << " l1 (size " << l1.size() << "): " << l1 << endl << " l3 (size " << l3.size() << "): " << l3 << endl << endl;

cout << "*** Testing splice() at end of list *** ";

int array2[] = {11, 13, 15};

for (int i = 0; i < 3; ++i) l1.push_back(array2[i]);

cout << "Before: " << " l1 (size " << l1.size() << "): " << l1 << endl << " l3 (size " << l3.size() << "): " << l3 << endl;

l3.splice(l3.end(), l1);

cout << "After: " << " l1 (size " << l1.size() << "): " << l1 << endl << " l3 (size " << l3.size() << "): " << l3 << endl << endl;

cout << "*** Testing splice() at beginning of list *** ";

int array3[] = {12, 14, 16};

for (int i = 0; i < 3; ++i) l1.push_back(array3[i]);

cout << "Before: " << " l1 (size " << l1.size() << "): " << l1 << endl << " l3 (size " << l3.size() << "): " << l3 << endl;

l3.splice(l3.begin(), l1);

cout << "After: " << " l1 (size " << l1.size() << "): " << l1 << endl << " l3 (size " << l3.size() << "): " << l3 << endl << endl;

cout << "*** Testing splice() before 5th element in list *** ";

int array4[] = {-1, -2, -3};

for (int i = 0; i < 3; ++i) l1.push_back(array4[i]);

itr1 = l3.begin(); for (int i = 0; i < 4; ++i) ++itr1;

cout << "Before: " << " l1 (size " << l1.size() << "): " << l1 << endl << " l3 (size " << l3.size() << "): " << l3 << endl;

l3.splice(itr1, l1);

cout << "After: " << " l1 (size " << l1.size() << "): " << l1 << endl << " l3 (size " << l3.size() << "): " << l3 << endl; */

return 0; }