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 an element 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 UnsortedList
template <typename ItemType>
class UnsortedType
{
	private:
		NodeType<ItemType> *listData, *currentPos;
		int length;

	public:
		UnsortedType();
		~UnsortedType();
		bool isFull() const;
		int lengthIs() const; // Returns the length of the list
		void makeEmpty(); 
		void retrieveItem(ItemType& item, bool& found);
		void insertItem(ItemType item); // Assume item is not in 
list 
		void deleteItem(ItemType item); // Assume item is unique.
		void resetList();
		void getNextItem(ItemType& item);
		void printList() const;
		void printK(int k) const;
};


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

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

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


template <typename ItemType>
bool UnsortedType<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 UnsortedType<ItemType>::lengthIs() const
{
	return length;
}

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

template <typename ItemType>
void UnsortedType<ItemType>::retrieveItem(ItemType& item, bool& found)
{
	NodeType<ItemType> *location;
	location = listData;
	found = false;

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

template <typename ItemType>
void UnsortedType<ItemType>::insertItem(ItemType item)
{
	if (isFull())
		throw FullList();
	bool found;
	retrieveItem(item,found);
	if (found)
		throw InTheList();
	NodeType<ItemType> *location;
	location = new NodeType<ItemType>;
	location -> info = item;
	location -> next = listData;
	listData = location;
	length++;
}

template <typename ItemType>
void UnsortedType<ItemType>::deleteItem(ItemType item)
{
	bool found;
	retrieveItem(item,found);
	if (!found)
		throw NotFound();
	NodeType<ItemType> *location = listData;
	NodeType<ItemType> *tempLocation;
	if (item == listData -> info)
	{
		tempLocation = location;
		listData = listData -> next;
	}
	else
	{
		while (item != (location -> next) -> info)
			location = location -> next;
		tempLocation = location -> next;
		location -> next = (location -> next) -> next;
	}
	delete tempLocation;
	length--;
}

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

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

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

// In this method, we assume ItemType is a printable type.
template <typename ItemType>
void UnsortedType<ItemType>:: printList() const
{
	NodeType<ItemType>* location = listData;
	while (location != NULL)
	{
		cout << location -> info << "\t";
		location = location -> next;
	}
	cout << endl << endl;
}


template <typename ItemType>
void UnsortedType<ItemType>:: printK(int k) const
{
	if (k <= 0)
		print 
	else if (k > length)
	{
		cout << k << "  
	NodeType<ItemType>* location = listData;
	while (location != NULL)
	{
		cout << location -> info << "\t";
		location = location -> next;
	}
	cout << endl << endl;
	}
	else
	{
		print the first k elements
	}
}

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

int main()
{
	// Try to remove the try catch statements and see what will 
happen.
	int i, n;
	string s;
	char item;
	bool found;
    	UnsortedType<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. 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();

	cout << "Enter a pos integer: ";
	int k;
	cin >> k;
	list.printK(k);
	cout << endl << endl;
	return 0;
}