#include <iostream>
#include <cassert>
#include <String>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
 
template <class TYPE>
struct NODE
{
	TYPE data;											//Data Item
	NODE<TYPE> *next;									
};
 
template<class TYPE>
class multiword
{
protected:
	int count;											//Variable to store the values of the numbers
	NODE<TYPE> *first;									//pointer to the first NODE
public:	
	class NotFound {};
	void Initialize();									//Initialize the list with no values			
	bool Empty();										//Check if the list is empty
	void Destroy();
	void fillNames(ifstream& inFile, multiword<TYPE>& cList);		//Delete every value of the list
	int binarysearch(const TYPE& item);					//Binary search		
	void additem(const TYPE& add);						//Add a value
	void Insertion();									//Insertion
	void display();										//Display
	multiword();										//Constructor(no-arg)
	~multiword();										//Destructor
};
 
template<class TYPE>
void multiword<TYPE>::fillNames(ifstream& inFile, multiword<TYPE>& cList)
{
	string firstN;
	int i;
 
	TYPE temp;
	const int number = 10
 
	for(i = 0; i < number; i++)
	{
		inFile>>firstN;
		temp.setName(firstN);
		cList.insertAt(i, temp);
	}
}
 
template<class TYPE>									//Check if the list is empty
bool multiword<TYPE>::Empty()
{
	return(first == NULL);
}
 
template<class TYPE>									//Constructor
multiword<TYPE>::multiword()
{
	first = NULL;
	count = 0;
}
 
template<class TYPE>									//Destructor
multiword<TYPE>::~multiword()
{
	Destroy();
}
 
template<class TYPE>
void multiword<TYPE>::Insertion()
{
	nodeType<TYPE> *lastInOrder;
	nodeType<TYPE> *firstOutOfOrder;
	nodeType<TYPE> *current;
	nodeType<TYPE> *trailCurrent;
 
	lastInOrder = first;
 
	if(first = NULL)
		cerr << "Cannot sort an empty list." << endl;
	else
		if(first->link == NULL)
			cout << "The list of length1, it is already in order." << endl;
		else
			while(lastInOrder->link !=NULL)
			{
				firstOutOfOrder = lastInOrder->link;
				if(firstOutOfOrder->info < first->info)
				{
					lastInOrder->link = firstOutOfOrder->link;
					firstOutOfOrder->link = first;
					first = firstOutOfOrder;
				}
				else
				{
					trailCurrent = first;
					current = first->link;
					while(current->info < firstOutOfOrder->info)
					{
						trailCurrent = current;
						current = current ->link;
					}
 
					if(current != firstOutOfOrder)
					{
						lastInOrder->link = firstOutOfOrder->link;
						firstOutOfOrder->link = current;
						trailCurrent->link = firstOufOfOrder;
					}
					else
						lastInOrder = lastInOrder->link
				}
			}
}
 
 
template<class TYPE>
int multiword<TYPE>::binarysearch(const TYPE& item)
{
	int first = 0;
	int last = length -1;
	int mid;
 
	bool found = false;
 
	while(first <= last && !found)
	{
		mid = (first + last) / 2;
 
		if(list[mid] == item)
			found = true;
		else
			if(list[mid] > item)
				last = mid -1;
			else 
				first = mid + 1;
	}
	if(found)
		return mid;
	else 
		return -1;
}
 
template<class TYPE>									//Destroy every element on the list
void multiword<TYPE>::Destroy()
{
	NODE<TYPE> *temp;									//deallocates memory
	while(first != NULL)								//while there are value in the list
	{
		temp = first;									//set temp to the first value in the list
		first = first->next;							//put first to the next value
		delete temp;									//delete memory
	}
	count = 0;
}
 
template<class TYPE>									//Initialize the list
void multiword<TYPE>::Initialize()
{
	Destroy();											//If any values are found, remove them.
}