1. (Carrano) Implement with SortedList, page 361 Chapter 12.

Two lists List1 and List2 ordered in ascending order.

Implement the mergeList function and get a new list3 ordered in a row List3.mergeList (List1, List2);

Codes:

main.cpp

#include

#include

#include "LinkedSorted.h"

using namespace std;

void mostrarLista(SortedListInterface* listaptr)

{

cout << "La lista contiene ";

for (int posi = 1; posi <= listaptr->getLength(); posi++)

{

cout << listaptr->getEntry(posi) << " ";

}

cout << endl;

}

void copyContructorTester()

{

cout << "Lista 1: " << endl;

LinkedSortedList lista1;

string *itemsptr = nullptr;

string items[] = { "8", "4", "2" };

for (int i = 0; i < 3; i++)

{

cout << "Anadir: " << items[i] << endl;

lista1.insertSorted(items[i]);

}

cout << " ";

cout << "Lista2: " << endl;

LinkedSortedList lista2;

string *items2ptr = nullptr;

string items2[] = { "5", "9", "3" };

for (int i = 0; i < 3; i++)

{

cout << "Anadir: " << items2[i] << endl;

lista2.insertSorted(items2[i]);

}

cout << " ";

cout << "Uniendo y sorting lista 1 y lista 2 con lista 3 ";

LinkedSortedList lista3;

lista3.unirLista(lista1, lista2);

cout << " Mostrar Lista 3: ";

mostrarLista(&lista3);

}

int main()

{

copyContructorTester();

return 0;

}

LinkedSorted.h

#ifndef _LINKED_SORTED_LIST

#define _LINKED_SORTED_LIST

#include "SortedListInterface.h"

#include "Node.h"

#include "PrecondViolatedExcep.h"

#include

using namespace std;

template

class LinkedSortedList : public SortedListInterface

{

private:

Node* headPtr;

int itemCount;

Node* getNodeBefore(const ItemType& anEntry) const;

Node* getNodeAt(int position) const;

Node* copyChain(const Node* origChainPtr);

public:

LinkedSortedList();

LinkedSortedList(const LinkedSortedList& aList);

virtual ~LinkedSortedList();

void unirLista(const LinkedSortedList& listA, const LinkedSortedList& listB);

void insertSorted(const ItemType& newEntry);

bool removeSorted(const ItemType& anEntry);

int getPosition(const ItemType& newEntry) const;

bool isEmpty() const;

int getLength() const;

bool remove(int position);

void clear();

ItemType getEntry(int position) const throw(PrecondViolatedExcep);

};

#include

template

LinkedSortedList::LinkedSortedList() : headPtr(nullptr), itemCount(0)

{

}

template

LinkedSortedList::LinkedSortedList(const LinkedSortedList& aList)

{

headPtr = copyChain(aList.headPtr);

itemCount = aList.itemCount;

}

template

Node* LinkedSortedList::copyChain(const Node* origChainPtr)

{

Node* copiedChainPtr = nullptr;

if (origChainPtr != nullptr)

{

copiedChainPtr = new Node(origChainPtr->getItem());

copiedChainPtr->setNext(copyChain(origChainPtr->getNext()));

}

return copiedChainPtr;

}

template

LinkedSortedList::~LinkedSortedList()

{

clear();

}

template

void LinkedSortedList::insertSorted(const ItemType& newEntry)

{

Node* newNodePtr = new Node(newEntry);

Node* prevPtr = getNodeBefore(newEntry);

if (isEmpty() || (prevPtr == nullptr))

{

newNodePtr->setNext(headPtr);

headPtr = newNodePtr;

}

else

{

Node* aftPtr = prevPtr->getNext();

newNodePtr->setNext(aftPtr);

prevPtr->setNext(newNodePtr);

}

itemCount++;

}

template

void LinkedSortedList::unirLista(const LinkedSortedList& listA, const LinkedSortedList& listB)

{

for (int pos = 1; pos <= listA.getLength(); pos++)

{

insertSorted(listA.getEntry(pos));

}

for (int pos = 1; pos <= listB.getLength(); pos++)

{

insertSorted(listB.getEntry(pos));

}

cout << endl;

}

template

bool LinkedSortedList::removeSorted(const ItemType& anEntry)

{

bool ableToDelete = false;

if (!isEmpty())

{

Node* nodeToRemovePtr = headPtr;

Node* prevPtr = getNodeBefore(anEntry);

if (prevPtr != nullptr)

nodeToRemovePtr = prevPtr->getNext();

ableToDelete = (nodeToRemovePtr != nullptr) &&

(anEntry == nodeToRemovePtr->getItem());

if (ableToDelete)

{

Node* aftPtr = nodeToRemovePtr->getNext();

if (nodeToRemovePtr == headPtr)

{

headPtr = aftPtr;

}

else

{

prevPtr->setNext(aftPtr);

}

nodeToRemovePtr->setNext(nullptr);

delete nodeToRemovePtr;

nodeToRemovePtr = nullptr;

itemCount--;

}

}

return ableToDelete;

}

template

int LinkedSortedList::getPosition(const ItemType& anEntry) const

{

int position = 1;

Node* curPtr = headPtr;

while ((curPtr != nullptr) && (anEntry > curPtr->getItem()))

{

curPtr = curPtr->getNext();

position++;

}

if ((curPtr == nullptr) || (anEntry != curPtr->getItem()))

position = -position;

return position;

}

template

bool LinkedSortedList::remove(int position)

{

bool ableToDelete = (position >= 1) && (position <= itemCount);

if (ableToDelete)

{

Node* curPtr = nullptr;

if (position == 1)

{

curPtr = headPtr;

headPtr = headPtr->getNext();

}

else

{

Node* prevPtr = getNodeAt(position - 1);

curPtr = prevPtr->getNext();

prevPtr->setNext(curPtr->getNext());

}

curPtr->setNext(nullptr);

delete curPtr;

curPtr = nullptr;

itemCount--;

}

return ableToDelete;

}

template

void LinkedSortedList::clear()

{

while (!isEmpty())

remove(1);

}

template

ItemType LinkedSortedList::getEntry(int position) const throw(PrecondViolatedExcep)

{

bool ableToGet = (position >= 1) && (position <= itemCount);

if (ableToGet)

{

Node* nodePtr = getNodeAt(position);

return nodePtr->getItem();

}

else

{

string message = "getEntry() called with an empty list or ";

message = message + "invalid position.";

throw(PrecondViolatedExcep(message));

}

}

template

bool LinkedSortedList::isEmpty() const

{

return itemCount == 0;

}

template

int LinkedSortedList::getLength() const

{

return itemCount;

}

template

Node* LinkedSortedList::getNodeBefore(const ItemType& anEntry) const

{

Node* curPtr = headPtr;

Node* prevPtr = nullptr;

while ((curPtr != nullptr) && (anEntry > curPtr->getItem()))

{

prevPtr = curPtr;

curPtr = curPtr->getNext();

}

return prevPtr;

}

template

Node* LinkedSortedList::getNodeAt(int position) const

{

assert((position >= 1) && (position <= itemCount));

Node* curPtr = headPtr;

for (int skip = 1; skip < position; skip++)

curPtr = curPtr->getNext();

return curPtr;

}

#endif

Node.h

#ifndef _NODE

#define _NODE

#include

template

class Node

{

private:

ItemType item;

Node* next;

public:

Node();

Node(const ItemType& anItem);

Node(const ItemType& anItem, Node* nextNodePtr);

void setItem(const ItemType& anItem);

void setNext(Node* nextNodePtr);

ItemType getItem() const;

Node* getNext() const;

};

template

Node::Node() : next(nullptr)

{}

template

Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)

{}

template

Node::Node(const ItemType& anItem, Node* nextNodePtr) :

item(anItem), next(nextNodePtr)

{}

template

void Node::setItem(const ItemType& anItem)

{

item = anItem;

}

template

void Node::setNext(Node* nextNodePtr)

{

next = nextNodePtr;

}

template

ItemType Node::getItem() const

{

return item;

}

template

Node* Node::getNext() const

{

return next;

}

#endif

PrecodViolatedExcept.h

#ifndef _PRECOND_VIOLATED_EXCEP

#define _PRECOND_VIOLATED_EXCEP

#include

#include

using namespace std;

class PrecondViolatedExcep : public logic_error

{

public:

PrecondViolatedExcep(const string& message = "");

};

PrecondViolatedExcep::PrecondViolatedExcep(const string& message) : logic_error("Precondition Violated Exception: " + message)

{}

#endif

SortedListInterface.h

#ifndef SORTED_LIST_INTERFACE

#define SORTED_LIST_INTERFACE

template

class SortedListInterface

{

public:

virtual void insertSorted(const ItemType& newEntry) = 0;

virtual bool removeSorted(const ItemType& anEntry) = 0;

virtual int getPosition(const ItemType& anEntry) const = 0;

virtual bool isEmpty() const = 0;

virtual int getLength() const = 0;

virtual bool remove(int position) = 0;

virtual void clear() = 0;

virtual ItemType getEntry(int position) const = 0;

};

#endif