Use a Binary Search Tree to implement Sorted List class. The sorted list class

should have all the functionalities of a regular sorted list class.

In the driver file, create Sorted List object, insert a few items in it and finally print the List.

#ifndef SORTEDTYPE_H_INCLUDED

#define SORTEDTYPE_H_INCLUDED

template

class SortedType

{

struct NodeType

{

ItemType info;

NodeType* next;

};

public:

SortedType();

~SortedType();

bool IsFull();

int LengthIs();

void MakeEmpty();

bool RetrieveItem(ItemType&);

bool InsertItem(ItemType);

bool DeleteItem(ItemType);

void ResetList();

bool GetNextItem(ItemType&);

private:

int length;

NodeType* listData;

NodeType* currentPos;

};

#include "sortedtype.tpp"

#endif // SORTEDTYPE_H_INCLUDED

#include "sortedtype.h"

#include

using namespace std;

template

SortedType::SortedType()

{

length = 0;

listData = NULL;

currentPos = NULL;

}

template

int SortedType::LengthIs()

{

return length;

}

template

bool SortedType::IsFull()

{

NodeType* location;

try

{

location = new NodeType;

delete location;

return false;

}

catch(bad_alloc& exception)

{

return true;

}

}

template

bool SortedType::InsertItem(ItemType item)

{

if(IsFull())

return false;

NodeType* newNode;

newNode = new NodeType;

newNode->info = item;

NodeType* predLoc = NULL;

NodeType* location = listData;

bool moreToSearch;

//location = listData;

//predLoc = NULL;

moreToSearch = (location != NULL);

while (moreToSearch)

{

if (location->info < item)

{

predLoc = location;

location = location->next;

moreToSearch = (location != NULL);

}

else

moreToSearch = false;

}

if (predLoc == NULL)// when the item is inserted at the front of the list

{

newNode->next = listData;

listData = newNode;

}

else

{

newNode->next = location;

predLoc->next = newNode;

}

length++;

return true;

}

template

bool SortedType::DeleteItem(ItemType item)

{

NodeType* location = listData;

NodeType* tempLocation;

if (item == listData->info)

{

tempLocation = location;

listData = listData->next;

}

else

{

while (!(item==(location->next)->info)){

location = location->next;

if(location->next == NULL)

return false;

}

tempLocation = location->next;

location->next = (location->next)->next;

}

delete tempLocation;

length--;

return true;

}

template

bool SortedType::RetrieveItem(ItemType& item)

{

NodeType* location = listData;

bool moreToSearch = (location != NULL);

bool found = false;

while (moreToSearch && !found)

{

if (item == location->info){

found = true;

item = location->info;

}

else if (item > location->info)

{

location = location->next;

moreToSearch = (location != NULL);

}

else

moreToSearch = false;

}

return found;

}

template

void SortedType::MakeEmpty()

{

NodeType* tempPtr;

while (listData != NULL)

{

tempPtr = listData;

listData = listData->next;

delete tempPtr;

}

length = 0;

}

template

SortedType::~SortedType()

{

MakeEmpty();

}

template

void SortedType::ResetList()

{

currentPos = NULL;

}

template

bool SortedType::GetNextItem(ItemType& item)

{

if (currentPos == NULL)

currentPos = listData;

else

currentPos = currentPos->next;

if(currentPos == NULL)

return false;

item = currentPos->info;

return true;

}