#include #include

using std::cin; using std::cout; using std::endl; using std::string; using std::stringstream;

//************************************************************************ //A class I designed to help keep track of how much memory you allocate //Do not modify, this is not part of your assignment, it just helps test it. //For this to work, a class needs to inherit off of this one. //Then this does the rest of the work, since it //overloads new, new[], delete, and delete[]. //************************************************************************ class ManageMemory { public:

static std::size_t getTotalSize() { std::size_t total = 0; std::map::iterator iter; for (iter = mapOfAllocations.begin(); iter != mapOfAllocations.end(); ++iter) { total += iter->second; } return total; }

//I overloaded the new and delete keywords so I could manually track allocated memory. void* operator new(std::size_t x){ void *ptr = ::operator new(x); mapOfAllocations[ptr] = x; return ptr; } void* operator new[](std::size_t x) { void *ptr = ::operator new[](x); mapOfAllocations[ptr] = x; return ptr; } void operator delete(void* x) { mapOfAllocations.erase(x); ::operator delete(x); } void operator delete[](void* x) { mapOfAllocations.erase(x); ::operator delete[](x); } private: static std::map mapOfAllocations; }; std::map ManageMemory::mapOfAllocations;

//****************** //The node class //****************** template class Node : public ManageMemory { public: T data; Node *link{ nullptr }; };

//****************** //The linked list base class //This contains within it a class declaration for an iterator //****************** template class SinglyLinkedList : public ManageMemory { public:

//public members of the SinglyLinkedList class ~SinglyLinkedList(); string getStringFromList();

void insertFront(const T&); void insertBack(const T&); T getAtIndex(const unsigned int index) const; //For your assignment T& operator[](const unsigned int index); //For your assignment void insertAtIndex(const unsigned int index, const T& value); //For your assignment void deleteAtIndex(const unsigned int index); //For your assignment void deleteAllInstances(const T& value); //For your assignment

protected:

Node *front{ nullptr }; Node *back{ nullptr }; int count{ 0 };

};

template // destructor SinglyLinkedList::~SinglyLinkedList() { Node *temp; while (front != nullptr) { temp = front; front = front->link; delete temp; } back = nullptr; count = 0; }

template void SinglyLinkedList::insertFront(const T& value) { Node *temp = new Node(); temp->data = value;

//empty list scenario if (front == nullptr) { back = temp; } else { temp->link = front; }

front = temp; count++; }

template void SinglyLinkedList::insertBack(const T& value) { Node *temp = new Node; temp->data = value;

if (front == nullptr) { front = temp; } else { //put it on back->link = temp; } back = temp; count++; }

//TODO: Complete this method template T SinglyLinkedList::getAtIndex(const unsigned int index) const { //This is not what you should return, but this just helps it compile T fakeDataToGetItToCompile{}; return fakeDataToGetItToCompile; }

//TODO: Complete this method template T& SinglyLinkedList::operator[](const unsigned int index) { //This is not what you should return, but this just helps it compile T fakeDataToGetItToCompile{}; return fakeDataToGetItToCompile; }

//TODO: Complete this method template void SinglyLinkedList::insertAtIndex(const unsigned int index, const T& value) {

}

//TODO: Complete this method template void SinglyLinkedList::deleteAtIndex(const unsigned int index) {

}

//TODO: Complete this method template void SinglyLinkedList::deleteAllInstances(const T& value) {

}

//This method helps return a string representation of all nodes in the linked list, do not modify. template string SinglyLinkedList::getStringFromList() { stringstream ss; if (front == nullptr) { ss

Node *currentNode = front; ss data; currentNode = currentNode->link;

while (currentNode != nullptr) { ss data; currentNode = currentNode->link; }; } return ss.str(); }

//This helps with testing, do not modify. bool checkTest(string testName, string whatItShouldBe, string whatItIs) {

if (whatItShouldBe == whatItIs) { cout

//This helps with testing, do not modify. bool checkTest(string testName, int whatItShouldBe, int whatItIs) {

if (whatItShouldBe == whatItIs) { cout

//This helps with testing, do not modify. bool checkTestMemory(string testName, int whatItShouldBe, int whatItIs) {

if (whatItShouldBe == whatItIs) { cout

//This helps with testing, do not modify. void testGetAtIndex() { SinglyLinkedList *d = new SinglyLinkedList; for (int i = 10; i insertBack(i); }

//Test just to make sure the data went in the list. checkTest("testGetAtIndex #1", "10 11 12 13 14 15 16 17 18 19", d->getStringFromList());

//Test retrieving items. int item = d->getAtIndex(0); checkTest("testGetAtIndex #2", 10, item);

item = d->getAtIndex(5); checkTest("testGetAtIndex #3", 15, item);

item = d->getAtIndex(9); checkTest("testGetAtIndex #4", 19, item);

//Make sure the list was undisturbed during this time checkTest("testGetAtIndex #5", "10 11 12 13 14 15 16 17 18 19", d->getStringFromList());

//Try to access out of bounds. string caughtError = ""; try { int item = d->getAtIndex(-1); } catch (int error) { caughtError = "caught"; } checkTest("testGetAtIndex #6", "caught", caughtError);

try { int item = d->getAtIndex(100); } catch (int error) { caughtError = "caught"; } checkTest("testGetAtIndex #7", "caught", caughtError);

delete d;

d = new SinglyLinkedList; d->insertBack(18); item = d->getAtIndex(0); checkTest("testGetAtIndex #8", 18, item); delete d; }

//This helps with testing, do not modify. void testSquareBrackets() { SinglyLinkedList d; for (int i = 10; i

//Test just to make sure the data went in the list. checkTest("testSquareBrackets #1", "10 11 12 13 14 15 16 17 18 19", d.getStringFromList());

//Test retrieving items. int item = d[0]; checkTest("testSquareBrackets #2", 10, item);

item = d[5]; checkTest("testSquareBrackets #3", 15, item);

item = d[9]; checkTest("testSquareBrackets #4", 19, item);

//Make sure the list was undisturbed during this time checkTest("testSquareBrackets #5", "10 11 12 13 14 15 16 17 18 19", d.getStringFromList());

/ow test the return by reference d[1] = 1000;

checkTest("testSquareBrackets #6", "10 1000 12 13 14 15 16 17 18 19", d.getStringFromList());

//Try to access out of bounds. string caughtError = ""; try { int item = d[-1]; } catch (int error) { caughtError = "caught"; } checkTest("testSquareBrackets #7", "caught", caughtError);

try { int item = d[100]; } catch (int error) { caughtError = "caught"; } checkTest("testSquareBrackets #8", "caught", caughtError);

}

//This helps with testing, do not modify. void testInsertAtIndex() { SinglyLinkedList *s = new SinglyLinkedList; for (int i = 10; i insertBack(i); }

//Test just to make sure the data went in the list. checkTest("testInsertAtIndex #1", "10 11 12 13 14 15 16 17 18 19", s->getStringFromList());

s->insertAtIndex(3, 33);

checkTest("testInsertAtIndex #2", "10 11 12 33 13 14 15 16 17 18 19", s->getStringFromList());

s->insertAtIndex(0, 9);

checkTest("testInsertAtIndex #3", "9 10 11 12 33 13 14 15 16 17 18 19", s->getStringFromList());

s->insertAtIndex(12, 20);

checkTest("testInsertAtIndex #4", "9 10 11 12 33 13 14 15 16 17 18 19 20", s->getStringFromList());

delete s;

s = new SinglyLinkedList;

s->insertAtIndex(0, 42); checkTest("testInsertAtIndex #5", "42", s->getStringFromList());

s->insertAtIndex(1, 82); checkTest("testInsertAtIndex #6", "42 82", s->getStringFromList());

delete s;

}

//This helps with testing, do not modify. void testDeleteAtIndex() { SinglyLinkedList *d = new SinglyLinkedList; for (int i = 10; i insertBack(i); }

//Test just to make sure the data went in the list. checkTest("testDeleteAtIndex #1", "10 11 12 13 14 15 16", d->getStringFromList());

//Test deleting front items. d->deleteAtIndex(0); checkTest("testDeleteAtIndex #2", "11 12 13 14 15 16", d->getStringFromList());

d->deleteAtIndex(0); checkTest("testDeleteAtIndex #3", "12 13 14 15 16", d->getStringFromList());

//Test deleting a middle item d->deleteAtIndex(2); checkTest("testDeleteAtIndex #4", "12 13 15 16", d->getStringFromList());

//Test deleting back itmes d->deleteAtIndex(3); checkTest("testDeleteAtIndex #5", "12 13 15", d->getStringFromList());

d->deleteAtIndex(2); checkTest("testDeleteAtIndex #6", "12 13", d->getStringFromList());

//Test deleting a Kth element that doesn't exist. d->deleteAtIndex(500); checkTest("testDeleteAtIndex #7", "12 13", d->getStringFromList());

//Test deleting a back item d->deleteAtIndex(1); checkTest("testDeleteAtIndex #8", "12", d->getStringFromList());

//Test deleting item that doesn't exist d->deleteAtIndex(1); checkTest("testDeleteAtIndex #9", "12", d->getStringFromList());

//Test deleting item on the front d->deleteAtIndex(0); checkTest("testDeleteAtIndex #10", "The list is empty.", d->getStringFromList());

//Test attempting to delete from an empty list d->deleteAtIndex(0); checkTest("testDeleteAtIndex #11", "The list is empty.", d->getStringFromList());

delete d; }

//This helps with testing, do not modify. void testdeleteAllInstances() {

SinglyLinkedList *d = new SinglyLinkedList;

d->insertBack(4); d->insertBack(2); d->insertBack(6); d->insertBack(5); d->insertBack(6); d->insertBack(9);

//Do a delete, test it. d->deleteAllInstances(6); checkTest("testdeleteAllInstances #1", "4 2 5 9", d->getStringFromList());

delete d; d = new SinglyLinkedList; d->insertBack(4); d->insertBack(2); d->insertBack(3); d->insertBack(4); d->insertBack(4); d->insertBack(4); d->insertBack(9); d->deleteAllInstances(4); checkTest("testdeleteAllInstances #2", "2 3 9", d->getStringFromList());

delete d; d = new SinglyLinkedList; d->insertBack(3); d->insertBack(3); d->insertBack(3); d->insertBack(8); d->insertBack(2); d->insertBack(3); d->insertBack(3); d->insertBack(3); d->deleteAllInstances(3); checkTest("testdeleteAllInstances #3", "8 2", d->getStringFromList());

delete d; d = new SinglyLinkedList; d->insertBack(9); d->insertBack(9); d->insertBack(4); d->insertBack(2); d->insertBack(9); d->insertBack(9); d->insertBack(5); d->insertBack(1); d->insertBack(9); d->insertBack(2); d->insertBack(9); d->insertBack(9);

//Do a delete, test it. d->deleteAllInstances(9); checkTest("testdeleteAllInstances #4", "4 2 5 1 2", d->getStringFromList());

//Test deleting something that doesn't exist d->deleteAllInstances(7); checkTest("testdeleteAllInstances #5", "4 2 5 1 2", d->getStringFromList());

//A few more tests d->deleteAllInstances(2); checkTest("testdeleteAllInstances #6", "4 5 1", d->getStringFromList());

d->deleteAllInstances(4); checkTest("testdeleteAllInstances #7", "5 1", d->getStringFromList());

d->deleteAllInstances(5); checkTest("testdeleteAllInstances #8", "1", d->getStringFromList());

d->deleteAllInstances(1); checkTest("testdeleteAllInstances #9", "The list is empty.", d->getStringFromList());

//retest deleting something that doesn't exist. d->deleteAllInstances(7); checkTest("testdeleteAllInstances #10", "The list is empty.", d->getStringFromList()); delete d;

//Now ramp it up and do some huge tests. Start by timing how long a smaller approach takes. d = new SinglyLinkedList; //Fill the list with a pattern of //1 2 2 3 3 3 4 4 4 4 1 2 2 3 3 3 4 4 4 4 ... cout insertBack(i % 4 + 1); } } cout deleteAllInstances(3); auto end = std::chrono::high_resolution_clock::now(); std::chrono::duration diff = end - start; double benchmarkTime = diff.count() / 1000.0; cout

cout ; //Fill the list with a pattern of //1 2 2 3 3 3 4 4 4 4 1 2 2 3 3 3 4 4 4 4 ... for (int i = 0; i insertBack(i % 4 + 1); } } cout deleteAllInstances(3); end = std::chrono::high_resolution_clock::now(); diff = end - start; double actualTime = diff.count() / 1000.0; if (actualTime

} else { cout

}

void pressAnyKeyToContinue() { cout

//Linux and Mac users with g++ don't need this //But everyone else will see this message. cin.get();

}

int main() {

//Each of these checks how many bytes you have used. checkTestMemory("Memory Leak/Allocation Test #1", 0, ManageMemory::getTotalSize());

//For your assignment, write the code to make these three methods work //You should not modify the code here in main. testGetAtIndex();

checkTestMemory("Memory Leak/Allocation Test #2", 0, ManageMemory::getTotalSize());

testSquareBrackets();

checkTestMemory("Memory Leak/Allocation Test #3", 0, ManageMemory::getTotalSize());

testInsertAtIndex();

checkTestMemory("Memory Leak/Allocation Test #4", 0, ManageMemory::getTotalSize());

testDeleteAtIndex();

checkTestMemory("Memory Leak/Allocation Test #5", 0, ManageMemory::getTotalSize());

testdeleteAllInstances();

checkTestMemory("Memory Leak/Allocation Test #6", 0, ManageMemory::getTotalSize());

pressAnyKeyToContinue();

return 0; }

In the following file, complete the following methods: T getAtIndex (const unsigned int index) const. This method accepts an integer. The method should then traverse to and return the kth node in the list. This is also zero based. It should throw int error (i.e. throw 1;) if the index is invalid T& operator[] (const unsigned int index) const. This is the overloaded 0 operator It is really just a method, don't let the syntax scare you. It's just a method that accepts an integer. This method is very similar to getValueAt. It should return the node's value by reference (not a copy of the value, but the node's value). It should throw int error (i.e. throw 1;) if the index is invalid void insertAtIndex (const unsigned int index, const T& value). This method accepts an integer and a value. The method will insert a new node at that index. Anything already at that index is shifted up by one. It can also insert at position 0 (before all nodes, and at a position just after the last node. This index is zero based, meaning it starts counting from zero. It cannot accept negative indexes or index past the end of the list void deleteAtIndex(const unsigned int index). This method accepts an integer. The method should then traverse to and delete the kth node in the list. This is zero based. Make sure you handle all scenarios (first, middle, last, single node list, and empty list.) void deleteAllInstances (const T& value). This method accepts an value. The method should then remove all instances of that value. It cannot loop more than once, or in other words, it must traverse while it deletes. It cannot loop which calls another method to loop and find a value to delete In the following file, complete the following methods: T getAtIndex (const unsigned int index) const. This method accepts an integer. The method should then traverse to and return the kth node in the list. This is also zero based. It should throw int error (i.e. throw 1;) if the index is invalid T& operator[] (const unsigned int index) const. This is the overloaded 0 operator It is really just a method, don't let the syntax scare you. It's just a method that accepts an integer. This method is very similar to getValueAt. It should return the node's value by reference (not a copy of the value, but the node's value). It should throw int error (i.e. throw 1;) if the index is invalid void insertAtIndex (const unsigned int index, const T& value). This method accepts an integer and a value. The method will insert a new node at that index. Anything already at that index is shifted up by one. It can also insert at position 0 (before all nodes, and at a position just after the last node. This index is zero based, meaning it starts counting from zero. It cannot accept negative indexes or index past the end of the list void deleteAtIndex(const unsigned int index). This method accepts an integer. The method should then traverse to and delete the kth node in the list. This is zero based. Make sure you handle all scenarios (first, middle, last, single node list, and empty list.) void deleteAllInstances (const T& value). This method accepts an value. The method should then remove all instances of that value. It cannot loop more than once, or in other words, it must traverse while it deletes. It cannot loop which calls another method to loop and find a value to delete