Question

Below is the given code of implementation:

#include <string>
#include <iostream>
#include <list>
#include <cassert>

using namespace std;

class List;
class Iterator;

class Node
 {
         public:
                 /*
                    Constructs a node with a given data value.
                    @param s the data to store in this node
                    */
                         Node(string s);
                         
                         /* Destructor */
                         ~Node() {}
                 private:
                         string data;
                         Node* previous;
                         Node* next;
                         friend class List;
                         friend class Iterator;
                         };

 class List
 {
         
         public:
                 /**
                   Constructs an empty list.
                   */
                         List();

                         /* Destructor. Deletes Nodes that are dynamically allocated */
                         ~List();

                 /**
                    Appends an element to the list.
                    @param data the value to append
                    */
                        void push_back(string data);
                /**
                 Inserts an element into the list.
                 @param iter the position before which to insert
                 @param s the value to append
                 */
                 void insert(Iterator iter, string s);
                 /**
                    Removes an element from the list.
                    @param iter the position to remove
                    @return an iterator pointing to the element after the
                    erased element
                    */
                         Iterator erase(Iterator iter);
                 /**
                    Gets the beginning position of the list.
                    @return an iterator pointing to the beginning of the list
                    */
                         Iterator begin();
                 /**
                    Gets the past-the-end position of the list.
                    @return an iterator pointing past the end of the list
                    */
                         Iterator end();

                         bool empty();

                 private:
                         Node* first;
                         Node* last;
                         friend class Iterator;
};

 class Iterator
 {
         public:
                 /**
                    Constructs an iterator that does not point into any list.
                    */
                         Iterator();
                         
                         /* Copy constructor */                  
                         Iterator(const Iterator & pos);
                 /**
                    Looks up the value at a position.
                    @return the value of the node to which the iterator points
                    */
                         string get() const;
                 /**
                    Advances the iterator to the next node.
                    */
                         void next();
                 /**
                    Moves the iterator to the previous node.
                    */
                         void previous();
                 /**
                    Compares two iterators.
                    @param b the iterator to compare with this iterator
                    @return true if this iterator and b are equal
                    */
                         bool equals(Iterator b) const;

                         /* Overloaded Operators */
                         bool operator==(const Iterator& b) const;
                         bool operator!=(const Iterator& b) const;
                         Iterator operator++(int unused); //postfix
                         Iterator& operator++(); //prefix
                         Iterator operator--(int unused); //postfix                      
                         Iterator& operator--(); //prefix
                         string operator*() const;
                         

private:
         Node* position;
         List* container;
         friend class List;
         };

 Node::Node(string s)
 {
        data = s;
        previous = NULL;
        next = NULL;
        }

List::List()
{
        first = NULL;
        last = NULL;
        }

List::~List()
{
        
        if (!empty()) // if the list is nonempty
        {                               

                Node* node = this->first;            

                while (node->next != NULL)
                {
                                node = node->next; // jump to the next one                           

                                delete node->previous; // deleting the memory for previous
                }

                if (node->next == NULL) // reaching the last node
                {
                        delete node;
                }
        }

}

bool List::empty()
{
        return (last == NULL);
}

void List::push_back(string data)
{
        Node* new_node = new Node(data);
        if (last == NULL) // List is empty
                {
                first = new_node;
                last = new_node;
                }
        else
                {
                new_node->previous = last;
                last->next = new_node;
                last = new_node;
                }
        }

void List::insert(Iterator iter, string s)
{
        if (iter.position == NULL)
                {
                push_back(s);
                return;
                }
        
        Node* after = iter.position;
        Node* before = after->previous;
        Node* new_node = new Node(s);
        new_node->previous = before;
        new_node->next = after;
        after->previous = new_node;
        if (before == NULL) // Insert at beginning
                first = new_node;
        else
                before->next = new_node;
        }

Iterator List::erase(Iterator iter)
{
        assert(iter.position != NULL);
        Node* remove = iter.position;
        Node* before = remove->previous;
        Node* after = remove->next;
        if (remove == first)
                first = after;
         else
                before->next = after;
                if (remove == last)
                last = before;
                else
                after->previous = before;
        delete remove;
        Iterator r;
        r.position = after;
        r.container = this;
        return r;
        }

Iterator List::begin()
{
        Iterator iter;
        iter.position = first;
        iter.container = this;
        return iter;
        }

Iterator List::end()
{
        Iterator iter;
        iter.position = NULL;
        iter.container = this;
        return iter;
        }


Iterator::Iterator()
{
        position = NULL;
        container = NULL;
        }

Iterator::Iterator(const Iterator & pos)
{
        (*this) = pos;
}

string Iterator::get() const
{
        assert(position != NULL);
        return position->data;
        }

void Iterator::next()
{
        assert(position != NULL);
        position = position->next;
}

void Iterator::previous()
{
        assert(position != container->first);
        if (position == NULL)
                position = container->last;
        else
                position = position->previous;
        }

bool Iterator::equals(Iterator b) const
{
        return position == b.position;
        }

bool Iterator::operator==(const Iterator& b) const
{
        return position == b.position;
}

bool Iterator::operator!=(const Iterator& b) const
{
        return position != b.position;
}

Iterator & Iterator::operator++() // prefix
{
        assert(position != NULL);
        position = position->next;
        return *this;
}

Iterator Iterator::operator++(int unused) // postfix
{
        assert(position != NULL);

        Iterator clone(*this);

        position = position->next;

        return clone;
}


Iterator & Iterator::operator--() //prefix
{

        assert(position != container->first);
        if (position == NULL)
                position = container->last;
        else
                position = position->previous;

        return *this;
}

Iterator Iterator::operator--(int unused)
{

        assert(position != container->first);

        Iterator clone(*this);
        
        if (position == NULL)
                position = container->last;
        else
                position = position->previous;

        return clone;
}



string Iterator::operator*() const
{
        assert(position != NULL);
        return position->data;
}

Answer 1

---------------------------------------------------------------------------------------------------------------

// C++ Code

#include<stdio.h>
#include<stdlib.h>
#include <string>
#include <iostream>
#include <list>
#include <cassert>
#include<fstream>
using namespace std;

class ListInt;
class Iterator;

class Node
{
public:
/*
Constructs a node with a given data value.
@param s the data to store in this node
*/
Node(int s);

/* Destructor */
~Node() {}
private:
int data;
Node* previous;
Node* next;
friend class ListInt;
friend class Iterator;
};

class ListInt
{

public:
/**
Constructs an empty list.
*/
ListInt();

/* Destructor. Deletes Nodes that are dynamically allocated */
~ListInt();

/**
Appends an element to the list.
@param data the value to append
*/
void push_back(int data);
/**
Inserts an element into the list.
@param iter the position before which to insert
@param s the value to append
*/
void insert(Iterator iter, int s);
/**
Swap the nodes pointed by it1 and it2
@param it1 and @param it2 are the positions which need to be swapped
*/
void swap_nodes(Iterator it1, Iterator it2);
/**
Sort the elements of the list using the Selection Sort algorithm
*/
void selection_sort();
/**
Prints the contents of the list
*/
void printListData();
/**
Removes an element from the list.
@param iter the position to remove
@return an iterator pointing to the element after the
erased element
*/
Iterator erase(Iterator iter);
/**
Gets the beginning position of the list.
@return an iterator pointing to the beginning of the list
*/
Iterator begin();
/**
Gets the past-the-end position of the list.
@return an iterator pointing past the end of the list
*/
Iterator end();

bool empty();

private:
Node* first;
Node* last;
friend class Iterator;
};

class Iterator
{
public:
/**
Constructs an iterator that does not point into any list.
*/
Iterator();

/* Copy constructor */
Iterator(const Iterator & pos);
/**
Looks up the value at a position.
@return the value of the node to which the iterator points
*/
int get() const;
/**
Advances the iterator to the next node.
*/
void next();
/**
Moves the iterator to the previous node.
*/
void previous();
/**
Compares two iterators.
@param b the iterator to compare with this iterator
@return true if this iterator and b are equal
*/
bool equals(Iterator b) const;

/* Overloaded Operators */
bool operator==(const Iterator& b) const;
bool operator!=(const Iterator& b) const;
Iterator operator++(int unused); //postfix
Iterator& operator++(); //prefix
Iterator operator--(int unused); //postfix
Iterator& operator--(); //prefix
int operator*() const;

private:
Node* position;
ListInt* container;
friend class ListInt;
};

Node::Node(int s)
{
data = s;
previous = NULL;
next = NULL;
}

ListInt::ListInt()
{
first = NULL;
last = NULL;
}

ListInt::~ListInt()
{

if (!empty()) // if the list is nonempty
{

Node* node = this->first;

while (node->next != NULL)
{
node = node->next; // jump to the next one

delete node->previous; // deleting the memory for previous
}

if (node->next == NULL) // reaching the last node
{
delete node;
}
}

}

bool ListInt::empty()
{
return (last == NULL);
}

void ListInt::push_back(int data)
{
Node* new_node = new Node(data);
if (last == NULL) // ListInt is empty
{
first = new_node;
last = new_node;
}
else
{
new_node->previous = last;
last->next = new_node;
last = new_node;
}
}

void ListInt::insert(Iterator iter, int s)
{
if (iter.position == NULL)
{
push_back(s);
return;
}

Node* after = iter.position;
Node* before = after->previous;
Node* new_node = new Node(s);
new_node->previous = before;
new_node->next = after;
after->previous = new_node;
if (before == NULL) // Insert at beginning
first = new_node;
else
before->next = new_node;
}

void ListInt::swap_nodes(Iterator it1,Iterator it2)
{
if(it1.position != NULL && it2.position != NULL && it1.position != it2.position){
if(it1.position->next == it2.position || it2.position->next == it1.position){
// it1 and it2 are adjacent
// if it2 comes before it1, move forward it2 by one node and move backwards it1 by one node
if(it2.position->next == it1.position){
it2.next();
it1.previous();
}
// Now we have a situation where it1 is always before it2
Node *i1 = it1.position;
Node *i2 = it2.position;
Node *i1before = i1->previous;
Node *i2after = i2->next;

i1->next = i2after;
i2->previous = i1before;
i1->previous = i2;
i2->next = i1;
if(i1before == NULL){
first = i2;
}else{
i1before->next = i2;
}

if(i2after == NULL){
last = i1;
}else{
i2after->previous = i1;
}

}else{
// there's at least 1 node between it1 and it2
Node *i1 = it1.position;
Node *i2 = it2.position;
Node *it1before = it1.position->previous;
Node *it1after = it1.position->next;
Node *it2before = it2.position->previous;
Node *it2after = it2.position->next;

i1->next = it2after;
i1->previous = it2before;
i2->next = it1after;
i2->previous = it1before;

if(it1before == NULL){
first = i2;
}else {
it1before->next = i2;
}

if(it2before == NULL){
first = i1;
}else{
it2before->next = i1;
}

if(it1after == NULL){
last = i2;
}else{
it1after->previous = i2;
}

if(it2after == NULL){
last = i1;
}else{
it2after->previous = i1;
}
}

}

}

void ListInt::selection_sort()
{
Iterator startIter = this->begin(),iter1,iter2,tempIter;
int cur, minElem;
//selection sort
while(startIter.position != NULL){
minElem = startIter.get();
iter1.position = startIter.position->next;
iter1.container = this;
iter2.position = NULL;
iter2.container = this;
while(iter1.position != NULL){
// find the position with the minimum element
cur = iter1.get();
if(cur < minElem){
minElem = cur;
iter2.position = iter1.position;
iter2.container = this;
}
iter1.next();
}
// now swap the nodes pointed to by startIter and iter2
if(iter2.position != NULL ){
tempIter.position = startIter.position->next;
tempIter.container = this;
swap_nodes(startIter,iter2);
startIter.position = tempIter.position;
}else{
startIter.next();
}
}

}

void ListInt::printListData()
{
Iterator start = this->begin();
if(start.position == NULL){
return;
}
while(start.position->next != NULL){
cout << start.get() << "->";
start.next();
}
cout << start.get() << endl;

}

Iterator ListInt::erase(Iterator iter)
{
assert(iter.position != NULL);
Node* remove = iter.position;
Node* before = remove->previous;
Node* after = remove->next;
if (remove == first)
first = after;
else
before->next = after;
if (remove == last)
last = before;
else
after->previous = before;
delete remove;
Iterator r;
r.position = after;
r.container = this;
return r;
}

Iterator ListInt::begin()
{
Iterator iter;
iter.position = first;
iter.container = this;
return iter;
}

Iterator ListInt::end()
{
Iterator iter;
iter.position = NULL;
iter.container = this;
return iter;
}

Iterator::Iterator()
{
position = NULL;
container = NULL;
}

Iterator::Iterator(const Iterator & pos)
{
(*this) = pos;
}

int Iterator::get() const
{
assert(position != NULL);
return position->data;
}

void Iterator::next()
{
assert(position != NULL);
position = position->next;
}

void Iterator::previous()
{
assert(position != container->first);
if (position == NULL)
position = container->last;
else
position = position->previous;
}

bool Iterator::equals(Iterator b) const
{
return position == b.position;
}

bool Iterator::operator==(const Iterator& b) const
{
return position == b.position;
}

bool Iterator::operator!=(const Iterator& b) const
{
return position != b.position;
}

Iterator & Iterator::operator++() // prefix
{
assert(position != NULL);
position = position->next;
return *this;
}

Iterator Iterator::operator++(int unused) // postfix
{
assert(position != NULL);

Iterator clone(*this);

position = position->next;

return clone;
}

Iterator & Iterator::operator--() //prefix
{

assert(position != container->first);
if (position == NULL)
position = container->last;
else
position = position->previous;

return *this;
}

Iterator Iterator::operator--(int unused)
{

assert(position != container->first);

Iterator clone(*this);

if (position == NULL)
position = container->last;
else
position = position->previous;

return clone;
}

int Iterator::operator*() const
{
assert(position != NULL);
return position->data;
}

int main(){
ifstream fin;
fin.open("data1.txt");
int data;
ListInt newList;
while(fin >> data){
newList.push_back(data);
}
//print the ListInt
cout << "Iterating through the list in data1.txt :" << endl;
newList.printListData();
//sort the ListInt
newList.selection_sort();
cout << endl << "Sorted List :" << endl;
newList.printListData();

}

--------------------------------------------------------------------------------------------------------------

// Data in Data1.txt

4
2
1
10
2
1
5
9
8
11
14
13
3
19
15

--------------------------------------------------------------------------------------------------------------

// ScreenShot of sample output

Iterating through the list in datal.txt: 4->2- >1->10- >2->1->5->9- >8->11-14- >13->3->19- >15 Sorted List 1->1->2->2->3-4-75->8-9-10-11->13- 14->15->19

--------------------------------------------------------------------------------------------------------------