Help with C++ getting all tests to work. 95% complete. Only change where it says do code above and below here.

#include

#include

#include

#include

using std::cin;

using std::cout;

using std::cerr;

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 *forward{ nullptr };

Node *backward{ nullptr };

};

//******************

// The linked list base class

//******************

template

class LinkedListBase : public ManageMemory {

public:

string getStringFromList();

string getStringBackwardsFromList();

T getFifthElement() const { cerr << "Error: You didn't override this base class method yet" << endl; T temp{}; return temp; }

void insertNewFifthElement(const T& value) { cerr << "Error: You didn't override this base class method yet" << endl; }

void deleteFifthElement() { cerr << "Error: You didn't override this base class method yet" << endl; }

protected:

Node *front{ nullptr };

Node *back{ nullptr };

int currentSize{ 0 };

};

//This method helps return a string representation of all nodes in the linked list, do not modify.

template

string LinkedListBase::getStringFromList() {

stringstream ss;

if (!front) {

ss << "The list is empty.";

}

else {

Node *currentNode = front;

ss << currentNode->data;

currentNode = currentNode->forward;

while (currentNode) {

ss << " " << currentNode->data;

currentNode = currentNode->forward;

};

}

return ss.str();

}

//This method helps return a string representation of all nodes in the linked list, do not modify.

template

string LinkedListBase::getStringBackwardsFromList() {

stringstream ss;

if (!front) {

ss << "The list is empty.";

}

else {

Node *currentNode = back;

ss << currentNode->data;

currentNode = currentNode->backward;

while (currentNode) {

ss << " " << currentNode->data;

currentNode = currentNode->backward;

};

}

return ss.str();

}

//******************

//The singly linked list base class

//******************

template

class SinglyLinkedListBase : public LinkedListBase {

public:

//public members of the SinglyLinkedList class

~SinglyLinkedListBase();

void insertFront(const T&);

void insertBack(const T&);

};

template // destructor

SinglyLinkedListBase::~SinglyLinkedListBase() {

Node *temp;

while (this->front) {

temp = this->front;

this->front = this->front->forward;

delete temp;

}

this->back = nullptr;

this->currentSize = 0;

}

template

void SinglyLinkedListBase::insertFront(const T& value) {

Node *temp = new Node();

temp->data = value;

if (!this->front) {

temp->forward = this->front;

}

else {

this->back = temp;

}

this->front = temp;

this->currentSize++;

}

template

void SinglyLinkedListBase::insertBack(const T& value) {

Node* temp = new Node;

temp->data = value;

if (!this->front) {

this->front = temp;

}

else {

this->back->forward = temp;

}

this->back = temp;

this->currentSize++;

}

//******************

//The double linked list base class

//******************

template

class DoublyLinkedListBase : public LinkedListBase {

public:

//public members of the SinglyLinkedList class

~DoublyLinkedListBase();

void insertFront(const T&);

void insertBack(const T&);

};

template // destructor

DoublyLinkedListBase::~DoublyLinkedListBase() {

Node *temp;

while (this->front) {

temp = this->front;

this->front = this->front->forward;

delete temp;

}

this->back = nullptr;

this->currentSize = 0;

}

template

void DoublyLinkedListBase::insertFront(const T& value) {

Node *temp = new Node();

temp->data = value;

if (!this->front) {

this->front->backward = temp;

temp->forward = this->front;

}

else {

this->back = temp;

}

this->front = temp;

this->currentSize++;

}

template

void DoublyLinkedListBase::insertBack(const T& value) {

Node* temp = new Node;

temp->data = value;

if (!this->front) {

this->front = temp;

}

else {

this->back->forward = temp;

temp->backward = this->back;

}

this->back = temp;

this->currentSize++;

}

//**********************************

//Write your code below here

//**********************************

template

class SinglyLinkedList : public SinglyLinkedListBase {

public:

T getFifthElement() const;

void insertNewfifthElement(const T& value);

void deleteFifthElement();

//TODO: Declare your methods here.

};

template

T SinglyLinkedList::getFifthElement() const {

Node* currentNode = this->front;

int currentNodeNum = 1;

while (currentNodeNum < 5) {

currentNode = currentNode->forward;

currentNodeNum++;

}

if (currentNode == nullptr)

throw 1;

return currentNode->data;

}

template

void SinglyLinkedList::insertNewfifthElement(const T& value) {

Node* temp = new Node;

temp->data = value;

Node* currentNode = this->front;

int currentNodeNum = 1;

while (currentNodeNum < 4) {

currentNode = currentNode->forward;

currentNodeNum++;

}

if (currentNode->forward == nullptr) {

temp->forward = currentNode->forward;

currentNode->forward == temp;

this->back = temp;

}

else {

temp->forward = currentNode->forward;

currentNode->foward = temp;

}

//inserts a node containing value between 4th and 5th

//original 5th now becomes 6th

}

template

void SinglyLinkedList::deleteFifthElement() {

Node* currentNode = this->front;

int currentNodeNum = 1;

if (!this->front) {

cout << "This list is already empty" << endl;

return;

}

while (currentNodeNum < 4) {

currentNode = currentNode->forward;

currentNodeNum++;

}

Node* temp = currentNode->forward;

currentNode->forward = temp->forward;

if (temp == this->back) {

this->back = currentNode;

}

delete temp;

}

template

class DoublyLinkedList : public DoublyLinkedListBase {

public:

T getFifthElement() const;

void insertNewfifthElement(const T& value);

void deleteFifthElement();

};

template

T DoublyLinkedList::getFifthElement() const {

Node* currentNode = this->front;

int currentNodeNum = 1;

while (currentNodeNum < 5) {

currentNode = currentNode->forward;

currentNodeNum++;

}

if (currentNode == nullptr)

throw 1;

return currentNode->data;

}

template

void DoublyLinkedList::insertNewfifthElement(const T& value) {

Node* temp = new Node;

Node* currentNode = this->front;

temp->data = value;

int currentNodeNum = 1;

while (currentNodeNum < 5) {

currentNode = currentNode->forward;

currentNodeNum++;

}

if (currentNode == nullptr) {

throw 1;

}

else if (currentNode->forward == nullptr) {

currentNode->backward->forward = temp;

temp->backward = currentNode->backward;

back = temp;

}

else {

currentNode->backward->forward = temp;

temp->forward = currentNode;

temp->backward = currentNode->backward;

currentNode->backward = temp;

}

}

template

void DoublyLinkedList::deleteFifthElement() {

Node* currentNode = this->front;

int currentNodeNum = 1;

while (currentNodeNum < 5) {

currentNode = currentNode->forward;

currentNodeNum++;

}

if (currentNode->forward == nullptr) {

this->back = currentNode;

currentNode->backward->forward = currentNode->backward;

}

else {

currentNode->backward->forward = currentNode->forward;

currentNode->forward->backward = currentNode->backward;

}

delete currentNode;

}

//**********************************

//Write your code above here

//**********************************

//This helps with testing, do not modify.

bool checkTest(string testName, string whatItShouldBe, string whatItIs) {

if (whatItShouldBe == whatItIs) {

cout << "Passed " << testName << endl;

return true;

}

else {

cout << "****** Failed test " << testName << " ****** " << endl << " Output was " << whatItIs << endl << " Output should have been " << whatItShouldBe << endl;

return false;

}

}

//This helps with testing, do not modify.

bool checkTest(string testName, int whatItShouldBe, int whatItIs) {

if (whatItShouldBe == whatItIs) {

cout << "Passed " << testName << endl;

return true;

}

else {

cout << "****** Failed test " << testName << " ****** " << endl << " Output was " << whatItIs << endl << " Output should have been " << whatItShouldBe << endl;

return false;

}

}

//This helps with testing, do not modify.

bool checkTestMemory(string testName, int whatItShouldBe, int whatItIs) {

if (whatItShouldBe == whatItIs) {

cout << "Passed " << testName << endl;

return true;

}

else {

cout << "***Failed test " << testName << " *** " << endl << " You lost track of " << whatItIs << " bytes in memory!" << endl;

return false;

}

}

//This helps with testing, do not modify.

void testGetFifthElement() {

SinglyLinkedList *si = new SinglyLinkedList;

for (int i = 10; i < 20; i++) {

si->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testgetFifthElement #1", "10 11 12 13 14 15 16 17 18 19", si->getStringFromList());

//Test retrieving item.

int item = si->getFifthElement();

checkTest("testgetFifthElement #2", 14, item);

delete si;

si = new SinglyLinkedList;

for (int i = 10; i < 15; i++) {

si->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testgetFifthElement #3", "10 11 12 13 14", si->getStringFromList());

//Test retrieving item.

item = si->getFifthElement();

checkTest("testgetFifthElement #4", 14, item);

delete si;

si = new SinglyLinkedList;

for (int i = 10; i < 14; i++) {

si->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testgetFifthElement #5", "10 11 12 13", si->getStringFromList());

//Try to access out of bounds.

string caughtError = "";

try {

item = si->getFifthElement();

}

catch (int) {

caughtError = "caught";

}

checkTest("testgetFifthElement #6", "caught", caughtError);

delete si;

SinglyLinkedList *ss = new SinglyLinkedList;

ss->insertBack("Multi Pass");

ss->insertBack("Lelu Dallas");

ss->insertBack("BIG BADA BOOM");

ss->insertBack("Bruce Willis");

ss->insertBack("Fried Chicken");

ss->insertBack("EEEAAAAAAAeeeaaaaaEEeeAAAEEaaaaAA");

checkTest("testgetFifthElement #7", "Fried Chicken", ss->getFifthElement());

delete ss;

DoublyLinkedList *di = new DoublyLinkedList;

for (int i = 10; i < 20; i++) {

di->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testgetFifthElement #8", "10 11 12 13 14 15 16 17 18 19", di->getStringFromList());

//Test retrieving item.

item = di->getFifthElement();

checkTest("testgetFifthElement #9", 14, item);

delete di;

di = new DoublyLinkedList;

for (int i = 10; i < 15; i++) {

di->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testgetFifthElement #10", "10 11 12 13 14", di->getStringFromList());

//Test retrieving item.

item = di->getFifthElement();

checkTest("testgetFifthElement #11", 14, item);

delete di;

di = new DoublyLinkedList;

for (int i = 10; i < 14; i++) {

di->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testgetFifthElement #12", "10 11 12 13", di->getStringFromList());

//Try to access out of bounds.

caughtError = "";

try {

item = di->getFifthElement();

}

catch (int) {

caughtError = "caught";

}

checkTest("testgetFifthElement #13", "caught", caughtError);

delete di;

SinglyLinkedList *ds = new SinglyLinkedList;

ds->insertBack("Multi Pass");

ds->insertBack("Lelu Dallas");

ds->insertBack("BIG BADA BOOM");

ds->insertBack("Bruce Willis");

ds->insertBack("Fried Chicken");

ds->insertBack("EEEAAAAAAAeeeaaaaaEEeeAAAEEaaaaAA");

checkTest("testgetFifthElement #14", "Fried Chicken", ds->getFifthElement());

delete ds;

}

//This helps with testing, do not modify.

void testInsertNewFifthElement() {

SinglyLinkedList *si = new SinglyLinkedList;

for (int i = 10; i < 20; i++) {

si->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testInsertNewFifthElement #1", "10 11 12 13 14 15 16 17 18 19", si->getStringFromList());

//Test inserting an item

si->insertNewFifthElement(97);

checkTest("testInsertNewFifthElement #2", "10 11 12 13 97 14 15 16 17 18 19", si->getStringFromList());

delete si;

si = new SinglyLinkedList;

for (int i = 10; i < 15; i++) {

si->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testInsertNewFifthElement #3", "10 11 12 13 14", si->getStringFromList());

//Test inserting an item

si->insertNewFifthElement(97);

checkTest("testInsertNewFifthElement #4", "10 11 12 13 97 14", si->getStringFromList());

delete si;

si = new SinglyLinkedList;

for (int i = 10; i < 14; i++) {

si->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testInsertNewFifthElement #5", "10 11 12 13", si->getStringFromList());

//Test inserting an item

si->insertNewFifthElement(97);

checkTest("testInsertNewFifthElement #6", "10 11 12 13 97", si->getStringFromList());

delete si;

DoublyLinkedList *di = new DoublyLinkedList;

for (int i = 10; i < 20; i++) {

di->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testInsertNewFifthElement #7", "10 11 12 13 14 15 16 17 18 19", di->getStringFromList());

checkTest("testInsertNewFifthElement #8", "19 18 17 16 15 14 13 12 11 10", di->getStringBackwardsFromList());

//Test inserting an item

di->insertNewFifthElement(97);

checkTest("testInsertNewFifthElement #9", "10 11 12 13 97 14 15 16 17 18 19", di->getStringFromList());

checkTest("testInsertNewFifthElement #10", "19 18 17 16 15 14 97 13 12 11 10", di->getStringBackwardsFromList());

delete di;

di = new DoublyLinkedList;

for (int i = 10; i < 15; i++) {

di->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testInsertNewFifthElement #11", "10 11 12 13 14", di->getStringFromList());

//Test inserting an item

di->insertNewFifthElement(97);

checkTest("testInsertNewFifthElement #12", "10 11 12 13 97 14", di->getStringFromList());

checkTest("testInsertNewFifthElement #13", "14 97 13 12 11 10", di->getStringBackwardsFromList());

delete di;

di = new DoublyLinkedList;

for (int i = 10; i < 14; i++) {

di->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testInsertNewFifthElement #14", "10 11 12 13", di->getStringFromList());

//Test inserting an item

di->insertNewFifthElement(97);

checkTest("testInsertNewFifthElement #15", "10 11 12 13 97", di->getStringFromList());

checkTest("testInsertNewFifthElement #16", "97 13 12 11 10", di->getStringBackwardsFromList());

delete di;

}

//This helps with testing, do not modify.

void testDeleteFifthElement() {

// Note from the instructor: Please do not delete the actual movie. It's very good and shouldn't be removed.

SinglyLinkedList *si = new SinglyLinkedList;

for (int i = 10; i < 20; i++) {

si->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testDeleteFifthElement #1", "10 11 12 13 14 15 16 17 18 19", si->getStringFromList());

//Test deleting an item

si->deleteFifthElement();

checkTest("testDeleteFifthElement #2", "10 11 12 13 15 16 17 18 19", si->getStringFromList());

delete si;

si = new SinglyLinkedList;

for (int i = 10; i < 16; i++) {

si->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testDeleteFifthElement #3", "10 11 12 13 14 15", si->getStringFromList());

//Test deleting an item

si->deleteFifthElement();

checkTest("testDeleteFifthElement #4", "10 11 12 13 15", si->getStringFromList());

delete si;

si = new SinglyLinkedList;

for (int i = 10; i < 15; i++) {

si->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testDeleteFifthElement #5", "10 11 12 13 14", si->getStringFromList());

//Test deleting an item

si->deleteFifthElement();

checkTest("testDeleteFifthElement #6", "10 11 12 13", si->getStringFromList());

delete si;

DoublyLinkedList *di = new DoublyLinkedList;

for (int i = 10; i < 20; i++) {

di->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testDeleteFifthElement #7", "10 11 12 13 14 15 16 17 18 19", di->getStringFromList());

checkTest("testDeleteFifthElement #8", "19 18 17 16 15 14 13 12 11 10", di->getStringBackwardsFromList());

//Test deleting an item

di->deleteFifthElement();

checkTest("testDeleteFifthElement #9", "10 11 12 13 15 16 17 18 19", di->getStringFromList());

checkTest("testDeleteFifthElement #10", "19 18 17 16 15 13 12 11 10", di->getStringBackwardsFromList());

delete di;

di = new DoublyLinkedList;

for (int i = 10; i < 16; i++) {

di->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testDeleteFifthElement #11", "10 11 12 13 14 15", di->getStringFromList());

//Test deleting an item

di->deleteFifthElement();

checkTest("testDeleteFifthElement #12", "10 11 12 13 15", di->getStringFromList());

checkTest("testDeleteFifthElement #13", "15 13 12 11 10", di->getStringBackwardsFromList());

delete di;

di = new DoublyLinkedList;

for (int i = 10; i < 15; i++) {

di->insertBack(i);

}

//Test just to make sure the data went in the list.

checkTest("testDeleteFifthElement #14", "10 11 12 13 14", di->getStringFromList());

//Test deleting an item

di->deleteFifthElement();

checkTest("testDeleteFifthElement #15", "10 11 12 13", di->getStringFromList());

checkTest("testDeleteFifthElement #16", "13 12 11 10", di->getStringBackwardsFromList());

delete di;

}

void pressAnyKeyToContinue() {

cout << "Press enter to continue...";

//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.

testGetFifthElement();

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

testInsertNewFifthElement();

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

testDeleteFifthElement();

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

pressAnyKeyToContinue();

return 0;

}