Question: The DoublyLinkedList begin() method: This should create a temporary iterator object. Then set the temp's atRightEnd to false (unless the list is empty, then set
The DoublyLinkedList begin() method: This should create a temporary iterator object. Then set the temp's atRightEnd to false (unless the list is empty, then set it to true), and temp's current should be assigned to the list's first. Then the temp object is returned.
The DoublyLinkedList end() method: This should create a temporary iterator object. Then set the temp's atRightEnd to true, and temp's current should be assigned to the list's last. Then the temp object is returned.
overloaded * operator: This just returns the data that is in the node that current is pointing to. A one-liner. Make sure the return type is a T& and not a T.
overloaded != operator: This checks to see if both objects have the same atRightEnd and the same current values. If both objects have the same values, then return false. Otherwise just return true.
overloaded ++ prefix operator: The return type needs to be Iterator. The iterator should be moved forward one node, if possible. If moving it forward would mean it would become empty/nullptr, don't move it forward, and instead set the boolean atRightEnd to true. If atRightEnd is already true, you don't need to do anything. You need a return type, you need to return a copy of the iterator, and you can do that with return *this.
overloaded ++ postfix operator: The return type needs to be Iterator. You can overload the postfix operator by having a single (int) in the parameter section. Very similar to the prefix operator with one change. You first must make a copy of itself (Iterator copy = *this;). Increment the object pointed to by this. Return the copy you previously made.
overloaded -- prefix operator: The return type needs to be Iterator. Somewhat like to the operator++ prefix, but going backwards. You need to return a copy of the iterator, and you can do that with return *this. Note that operator-- doesnt have any corresponding atLeftEnd. The behavior of going off the left side of the collection is undefined, or in other words, dont worry about supporting it.
You must also complete an ourSort() method. This method passes in two iterators. You may only use knowledge obtained from iterators to complete this section. The most helpful tool will be iter_swap() which takes any two iterators and swaps the values they point to. Along with iter_swap(), you will likely want to use prefix ++, prefix --, !=, and making temporary copies of iterators to complete your logic. You definitely can't use linked list methods or access Node data members in ourSort(), or in other words, you can't write code that attempts to move begin forward with begin = begin->forward, rather, you should use ++begin. The logic you can follow mirrors this follwing psuedo code:
if the collection isnt empty
make a curr which tracks the start of the list
make an ahead which is one item ahead of curr
create a finished boolean initialized to false
while finished is false
set finished to true (assume we are done, but we may find we are not done)
set curr at the start of the collection
set ahead to be one item ahead of curr
while ahead is still pointing to a valid item
if the data at ahead is less than the data at curr
swap the data values being pointed to by both ahead and curr
set finished to false (we made a swap, we arent done)
increment curr
increment ahead
// The rightmost item is sorted (of those values considered)
// You can move end back one item as this item is sorted and no longer needs
// to be checked again
Now here is the code created by the Instructor in which we need to finish his "TODO" sections and uncomment his tests and pass each test.
#include
#include
#include
#include
#include
#include
//To prevent those using g++ from trying to use a library
//they don't have
#ifndef __GNUC__
#include
#else
#include
#endif
#include
template
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::shared_ptr;
using std::make_shared;
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
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
};
std::map
//******************
//The node class
//******************
template
struct Node {
T data{};
shared_ptr< Node
shared_ptr< Node
};
//******************
//The Iterator class
//******************
template
class Iterator : public ManageMemory, public std::iterator
friend class DoublyLinkedList
public:
//TODO: Complete these operator overloads:
//operator*
//operator++ prefix return *this;
//operator++ postfix auto temp = *this; move the "this"...; return temp;
//operator-- prefix
//operator!=
//operator==
private:
//TODO: supply two data members
//You need a shared pointer to a node (if you want, an even better approach would be to use a weak pointer)
//You need a boolean atRightEnd (see lecture video)
};
//***********************************
//The Iterator class methods
//***********************************
//TODO, code the definitions for all the iterator methods.
//****************************
//The DoublyLinkedList class
//****************************
template
class DoublyLinkedList : public ManageMemory {
public:
//public members of the DoublyLinkedList class
DoublyLinkedList();
~DoublyLinkedList();
string getStringFromList();
void insertFirst(const T&);
void insertLast(const T&);
void deleteFirst();
void deleteLast();
//TODO: Implement a begin() and end() method with return types of Iterator
protected:
shared_ptr< Node
shared_ptr< Node
unsigned int count;
};
template
DoublyLinkedList
count = 0;
first = nullptr;
last = nullptr;
}
template
DoublyLinkedList
while (first) {
first->backward.reset();
first = first->forward;
}
last.reset();
}
template
void DoublyLinkedList
if (!first) {
//Scenario #1 - The list is empty
first = make_shared< Node
first->data = item;
last = first;
}
else {
//Scenario #2 - The list has at least one item
shared_ptr< Node
tempPtr->data = item;
last->forward = tempPtr;
tempPtr->backward = last;
last = tempPtr;
}
count++;
}
template
void DoublyLinkedList
if (!first) {
//Scenario #1 The list is empty
first = make_shared< Node
first->data = item;
last = first;
}
else {
//Scenario #2 The list has at least one item in it
shared_ptr< Node
tempPtr->data = item;
tempPtr->forward = first;
first->backward = tempPtr;
first = tempPtr;
}
count++;
}
template
void DoublyLinkedList
//Empty list
if (!first) {
cout << "List is already empty" << endl;
return;
}
//Scenario 1 or more nodes
first = first->forward;
if (!first) {
//Must have been only 1 node in the list
last.reset();
}
else {
//first->backward = nullptr;
first->backward.reset();
}
count--;
}
template
void DoublyLinkedList
if (!first) {
//empty list scenario
cout << "The list is empty" << endl;
}
else {
last = last->backward;
if (!last) {
//1 node scenario
first.reset();
}
else {
//2 or more node scenario
last->forward.reset();
}
count--;
}
}
//This method helps return a string representation of all nodes in the linked list
template
string DoublyLinkedList
stringstream ss;
if (first == nullptr) {
ss << "The list is empty.";
}
else {
shared_ptr< Node
ss << currentNode->data;
currentNode = currentNode->forward;
while (currentNode != nullptr) {
ss << " " << currentNode->data;
currentNode = currentNode->forward;
}
}
return ss.str();
}
//***********************************
//The DoublyLinkedList class methods
//***********************************
//TODO, implement the the definitions for the begin() and end() methods
//***********************************
// TODO, complete the ourSort function.
// Note that begin and end here are are iterators (The T is just saying it can be any kind of iterator).
// Our iterator tools are ***ONLY***
// ++, --, !=, *, ==.
// To create a copy of iterators:
// T copyOfBeging = begin;
// To swap the data being pointed at by two iterators:
// iter_swap(begin, end);
template
void ourSort(T begin, T end) {
}
//----------------------------------------------------------------------------------------------------------------------------------------
//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 << " There are " << whatItIs << " bytes of memory yet to be reclaimed!" << endl;
return false;
}
}
//This helps with testing, do not modify.
void testIteratorFundamentals() {
cout << "|||### You need to comment in testIteratorFundamentals() when it's ready and remove this###|||" << endl;
/*
DoublyLinkedList
//Our test data should have all even numbers from 2 to 20
for (int i = 2; i <= 20; i += 2) {
d.insertLast(i);
}
//Get an iterator which points at the beginning of the list
Iterator
//Test the operator* operator
checkTest("testIteratorFundamentals #1", 2, *iter);
//Test the ++ prefix increment opreator
++iter;
checkTest("testIteratorFundamentals #2", 4, *iter);
//Test the != operator
//reset them back to the start
iter = d.begin();
Iterator
if (iter != anotherIter) {
cout << "****** Failed testIteratorFundamentals #3 ****** " << endl << " The two iteraters held the same data." << endl;
}
else {
cout << "Passed testIteratorFundamentals #3" << endl;
}
//Again test the != operator
++iter;
if (iter != anotherIter) {
cout << "Passed testIteratorFundamentals #4" << endl;
}
else {
cout << "****** Failed testIteratorFundamentals #4 ****** " << endl << " The two iteraters held different data." << endl;
}
//Test the ++postfix increment
iter = d.begin(); //reset it back to the start
anotherIter = iter++; //anotherIter should be at the data 2
checkTest("testIteratorFundamentals #5", 4, *iter);
checkTest("testIteratorFundamentals #6", 2, *anotherIter);
checkTest("testIteratorFundamentals #7", "2 4 6 8 10 12 14 16 18 20", d.getStringFromList());
*/
}
//This helps with testing, do not modify.
void testIteratorIncrement() {
cout << "|||### You need to comment in testIteratorIncrement() when it's ready and remove this ###|||" << endl;
/* DoublyLinkedList
//Our test data should have all even numbers from 2 to 20
for (int i = 2; i <= 20; i += 2) {
d->insertLast(i);
}
//Get an iterator which points at the beginning of the list
Iterator
//Test that it does point to the first
checkTest("testIteratorsIncrement #1", 2, *iter);
//Test that our Iterator can move forward;
++iter; checkTest("testIteratorsIncrement #2", 4, *iter);
//Test that our Iterator can move forward again;
++iter;
checkTest("testIteratorsIncrement #3", 6, *iter);
//move it some more
for (int i = 0; i < 6; i++) {
++iter;
}
checkTest("testIteratorsIncrement #4", 18, *iter);
//Hit the end
++iter;
checkTest("testIteratorsIncrement #5", 20, *iter);
//Verify we move the iterator past the end without crashing
++iter;
checkTest("testIteratorsIncrement #6", "did not crash", "did not crash");
delete d;
*/
}
//This helps with testing, do not modify.
void testIteratorDecrement() {
cout << "|||### You need to comment in testIteratorDecrement() when it's ready and remove this###|||" << endl;
/*
DoublyLinkedList
//Our test data should have all even numbers from 2 to 20
for (int i = 2; i <= 20; i += 2) {
d->insertLast(i);
}
//Get an Iterator which points at the end of the list
Iterator
--iter; //We have to do a decrement otherwise it crashes
//Test that it does point to the first
checkTest("testIteratorsDecrement #1", 20, *iter);
//Test that our Iterator can move forward;
--iter;
checkTest("testIteratorsDecrement #2", 18, *iter);
//move it some more
for (int i = 0; i < 7; i++) {
--iter;
}
checkTest("testIteratorsDecrement #3", 4, *iter);
//Hit the end
--iter;
checkTest("testIteratorsDecrement #4", 2, *iter);
//Now go back forward
++iter;
checkTest("testIteratorsDecrement #5", 4, *iter);
delete d;
*/
}
//This helps with testing, do not modify.
void testIterationTricky() {
cout << "|||### You need to comment in testIterationTricky() when it's ready and remove this###|||" << endl;
/*
DoublyLinkedList
myListOneNode.insertLast(42);
cout << "TestIterationTricky test #1, the next line should display 42" << endl;
stringstream ss;
//see if we can just iterator through one item.
for (auto i : myListOneNode) {
cout << i << " ";
ss << i << " ";
}
cout << endl;
checkTest("TestIterationTricky test #1", "42 ", ss.str());
ss.str("");
DoublyLinkedList
cout << "TestIterationTricky test #2, the next line shouldn't display anything" << endl;
//see if we can just iterator through one item.
for (auto i : myListEmpty) {
cout << i << " ";
ss << i << " ";
}
cout << endl;
checkTest("TestIterationTricky test #2", "", ss.str());
ss.str("");
*/
}
//This helps with testing, do not modify.
void testAlgorithms() {
cout << "|||### You need to comment in testAlgorithms() when it's ready and remove this###|||" << endl;
/*
DoublyLinkedList
//Our test data should have all even numbers from 2 to 20
for (int i = 2; i <= 6; i += 2) {
myList.insertLast(i);
}
myList.insertLast(100);
for (int i = 8; i <= 12; i += 2) {
myList.insertLast(i);
}
myList.insertLast(100);
for (int i = 14; i <= 20; i += 2) {
myList.insertLast(i);
}
stringstream ss;
for (auto i : myList) {
ss << i << " ";
}
cout << endl;
checkTest("testAlgorithms test #1", "2 4 6 100 8 10 12 100 14 16 18 20 ", ss.str());
ss.str("");
//Now sort it using our algorithm
ourSort(myList.begin(), myList.end());
for (auto i : myList) {
ss << i << " ";
}
cout << endl;
checkTest("testAlgorithms test #2", "2 4 6 8 10 12 14 16 18 20 100 100 ", ss.str());
ss.str("");
DoublyLinkedList
manyNines.insertLast(9);
manyNines.insertLast(9);
manyNines.insertLast(4);
manyNines.insertLast(2);
manyNines.insertLast(9);
manyNines.insertLast(9);
manyNines.insertLast(5);
manyNines.insertLast(1);
manyNines.insertLast(9);
manyNines.insertLast(2);
manyNines.insertLast(9);
manyNines.insertLast(9);
ourSort(manyNines.begin(), manyNines.end());
for (auto i : manyNines) {
ss << i << " ";
}
cout << endl;
checkTest("testAlgorithms test #3", "1 2 2 4 5 9 9 9 9 9 9 9 ", ss.str());
ss.str("");
DoublyLinkedList
oneItem.insertLast(42);
ourSort(oneItem.begin(), oneItem.end());
for (auto i : oneItem) {
ss << i << " ";
}
cout << endl;
checkTest("testAlgorithms test #4", "42 ", ss.str());
ss.str("");
DoublyLinkedList
oneItem.insertLast(42);
ourSort(noItems.begin(), noItems.end());
for (auto i : noItems) {
ss << i << " ";
}
cout << endl;
checkTest("testAlgorithms test #5", "", ss.str());
ss.str("");
//while (beginIter != endIter) {
// cout << *beginIter << " ";
// ss << *beginIter << " ";
// ++beginIter;
//}
//cout << endl;
//checkTest("testAlgorithms test #6", "4 2 5 1 2 ", ss.str());
//ss.str("");
*/
}
void pressAnyKeyToContinue() {
cout << "Press any key to continue...";
//Linux and Mac users with g++ don't need this
//But everyone else will see this message.
#ifndef __GNUC__
_getch();
#else
int c;
fflush(stdout);
do c = getchar(); while ((c != ' ') && (c != EOF));
#endif
cout << endl;
}
int main() {
cout << "This first test can run forever until you get operators *, != and ++ implemented." << endl;
pressAnyKeyToContinue();
testIteratorFundamentals();
checkTestMemory("Memory Leak/Allocation Test #1", 0, ManageMemory::getTotalSize());
pressAnyKeyToContinue();
testIteratorIncrement();
checkTestMemory("Memory Leak/Allocation Test #2", 0, ManageMemory::getTotalSize());
pressAnyKeyToContinue();
testIteratorDecrement();
checkTestMemory("Memory Leak/Allocation Test #3", 0, ManageMemory::getTotalSize());
pressAnyKeyToContinue();
testIterationTricky();
checkTestMemory("Memory Leak/Allocation Test #4", 0, ManageMemory::getTotalSize());
pressAnyKeyToContinue();
testAlgorithms();
checkTestMemory("Memory Leak/Allocation Test #5", 0, ManageMemory::getTotalSize());
pressAnyKeyToContinue();
return 0;
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help