class FullList
{
	// An exception class for the case when the list is full.
	// This class is used by insertItem.
};
class NotFound
{
	// An exception class for the case when the item to be deleted is not in the list.
	// This class is used by deleteItem.
};
class InTheList
{
	// An exception class for the case when the item to be inserted is already there.
	// This class is used by insertItem.
};

class LastElement
{
	// An exception class for the case when the element at currentPos is the last element in the list.
	// This class is used by getNextItem.
};

// Declaration of struct NodeType
template <typename ItemType>
struct NodeType;

// Specification part of class SortedList
template <typename ItemType>
class SortedType
{
	private:
		NodeType<ItemType> *listData, *currentPos;
		int length;

	public:
		SortedType();
		~SortedType();
		bool isFull() const;
		int lengthIs() const; // Returns the length of the list
		void makeEmpty(); 
		void retrieveItem(ItemType& item, bool& found);
		void insertItem(ItemType item);
		void deleteItem(ItemType item);
		void resetList();
		void getNextItem(ItemType& item);
		void printList() const;
		void printFirstLast() const;
};


// Definition of struct NodeType
template <typename ItemType>
struct NodeType
{
	ItemType info;
	NodeType *next;
};

// Implementation part of class SortedList
#include <new>
#include <cstdlib>

template <typename ItemType>
void SortedType<ItemType>:: printList() const
{
	NodeType<ItemType>* location = listData;
	while (location != NULL)
	{
		cout << location -> info << "\t";
		location = location -> next;
	}
	cout << endl << endl;
}


template <typename ItemType>
SortedType<ItemType>::SortedType()
{
	length = 0;
	listData = NULL;
}

template <typename ItemType>
bool SortedType<ItemType>::isFull() const
{
	NodeType<ItemType> *location;
	try
	{
		location = new NodeType<ItemType>;
		delete location;
		return false;
	}
	catch(bad_alloc exception)
	{
		return true;
	}
}
template <typename ItemType>
int SortedType<ItemType>::lengthIs() const
{
	return length;
}

template <typename ItemType>
void SortedType<ItemType>::makeEmpty()
{
	NodeType<ItemType> *tempPtr;
	while (listData != NULL)
	{
		tempPtr = listData;
		listData = listData -> next;
		delete tempPtr;
	}
	length = 0;
}

template <typename ItemType>
void SortedType<ItemType>::retrieveItem(ItemType& item, bool& found)
{
	bool moreToSearch;
NodeType<ItemType> *location;

	location = listData;
	found = false;
	moreToSearch = (location != NULL);

	while ( moreToSearch && !found)
	{
		if (location -> info < item)
		{
			location = location -> next;
			moreToSearch = (location != NULL);
		}
		else if (item == location -> info)
		{
			found = true;
			item = location -> info;
		}
		else
			moreToSearch = false;
	}
}











template <typename ItemType>
void SortedType<ItemType>::insertItem(ItemType item)
{
	if (isFull())
		throw FullList();
	bool found;
	retrieveItem(item,found);
	if (found)
		throw InTheList();
NodeType<ItemType> *newNode; // Pointer to the node being inserted.
NodeType<ItemType> *previous; // Trailing pointer
	NodeType<ItemType> *location; // Travelling pointer
	bool moreToSearch;

	location = listData;
	previous = NULL;
	moreToSearch = (location != NULL);
	// Find the insertion location.
	while (moreToSearch)
	{	
		if (location -> info < item)
		{
			previous = location;
			location = location -> next;
			moreToSearch = (location != NULL);
		}
		else
			moreToSearch = false;
	}
	newNode = new NodeType<ItemType>;
	newNode -> info = item;
	// Insert newNode
	if (previous == NULL)
	{
		newNode -> next = listData;
		listData = newNode;
	}
	else
	{
		newNode -> next = location;
		previous -> next = newNode;
	}
	length++;
}

template <typename ItemType>
void SortedType<ItemType>::deleteItem(ItemType item)
{
	bool found;
	retrieveItem(item,found);
	if (!found)
		throw NotFound();
	NodeType<ItemType> *previous; // Trailing pointer
	NodeType<ItemType> *location; // Travelling pointer
	bool moreToSearch;
	location = listData;
	previous = NULL;
	moreToSearch = (location != NULL);
	// Find the node containing item
	while (moreToSearch)
	{	
		if (location -> info < item)
		{
			previous = location;
			location = location -> next;
			moreToSearch = (location != NULL);
		}
		else
			moreToSearch = false;
	}
	//Prepare to delete the node at location
	if (previous == NULL)
	{
		listData = listData -> next;
	}
	else
	{
		previous -> next = location -> next;
	}

	// Delete the node at location
delete location;
	length--;
}

template <typename ItemType>
void SortedType<ItemType>::resetList()
{
	currentPos = NULL;
}

template <typename ItemType>
void SortedType<ItemType>::getNextItem(ItemType& item)
{
	if  ( (listData == NULL) || (currentPos -> next == NULL) )
		throw LastElement();
	if (currentPos == NULL)
		currentPos = listData;
	else
		currentPos = currentPos -> next;
	item = currentPos -> info;
}

template <typename ItemType>
SortedType<ItemType>::~SortedType()
{
	NodeType<ItemType> *tempPtr;
	while (listData != NULL)
	{
		tempPtr = listData;
		listData = listData -> next;
		delete tempPtr;
	}
}

// Driver Program

#include <iostream>
#include <string>
//#include "SortedType.h"
using namespace std;

int main()
{
	// Try to remove the try catch statements and see what will happen.
	int i, n;
	string s;
    SortedType<char> list;
	cout << "\tEnter a string: " << endl;
	getline(cin,s);
	n = s.size();
	for (i = 0; i < n; i++)
		try
		{
        			list.insertItem(s[i]);
		}
		catch(FullList)
		{
			cout << "The list is full. The insertion failed.\n";
		}
		catch (InTheList)
		{
			cout << "The element is in the list. "
				<< "Insertion failed.\n";
		}

    cout << "\tThe list now stores " << list.lengthIs() 
		<< " items. They are\n\n";
	list.printList();
	list.printFirstLast();

	
	return 0;
}