#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <list>
using namespace std;
typedef stack <string> wordStack;
/************************
* Function Prototypes	*
************************/
string findNextWord(string word);
void findNewWord();
/************************
* Global Variables	*
************************/
int dictIndex;
/********************************************************************************
*	class:		Dictionary						*
*	purpose:	To hold the word list in which to build the Ladder	*
********************************************************************************/	
class Dictionary
{
	private:
		vector <string> dictWords;
	public:
		Dictionary(){};
/********************************************************************************
*	function:	initVector						*
*	purpose:	fill a vector with all the valid words from the		*
* 			words.dat file						*
********************************************************************************/
		void initVector()
		{
			int		wordend=0;
			string		word;
			const string	letters = "abcdefghijklmnopqrstuvwxyz";
			
			ifstream textfile("words.dat");
		 	if(!textfile)
		 	{
				cerr << "Cannot open words.dat file\n";
				return;
		 	}
		 	while (!textfile.eof())
		 	{
				getline(textfile, word);
		 		wordend = word.find_first_not_of( letters, 0);
		 		if( (wordend < 0) || (wordend > 0) )
		 		{
		 			word=word.substr(0,wordend);
		 			dictWords.push_back(word);
		 		}
		 	}
		 }
/********************************************************************************
*	function:	BinSearch						*
*	purpose:	Search the dictionary vector for the appropriate	*
* 			word using a binary search algorithm			*
********************************************************************************/		    
		int BinSearch(string line)
		{
			int	First=0,last = this->size(),mid;
			int	origLast = last;
	 		string	midvalue;
	 		
	 		while(First < last)
	 		{
	 			mid = (First+last)/2;
	 			midvalue = dictWords[mid];
	 			if(line == midvalue) return mid;
	 			else if(line < midvalue) last = mid;
	 			else	First = mid+1;
	 		}
	 		return	origLast;
	 	}
/********************************************************************************
*	function:	getWord							*
*	purpose:	to return a word from within the dictionary vector	*
* 			using a given index					*
********************************************************************************/	
	 	string getWord(int a){	return dictWords[a];}
/********************************************************************************
*	function:	findWords						*
*	purpose:	to determine if selected words are present in the	*
* 			dictionary (returns 0 if word both words are present)	*
********************************************************************************/	
		int findWords(string a,string c)
		{
			try 
			{	if (a.length() != 5 || c.length() != 5) throw a;
			}
			catch (string a)
			{	cout << "\nThe words \"" <<a << "\" and \"" << c << "\" are not both ";
				cout << "legitimate 5-letter words from the dictionary.\n\nPlease try again..."<<endl;
				return 1;
			}
	 		try
	 		{
				int	b = this->BinSearch(a);
				if(b == this->size()) throw b;
				return 0;
			}
			catch(int b)
			{
				cout << a << " could not be found in the Dictionary!\n";
				return 1;
			}
			try
			{
				int	b = this->BinSearch(c);
				if(b == this->size()) throw b;
			}
			catch(int b)
			{
				cout << c << " could not be found in the Dictionary!\n";
				return 1;
			}
		}
/********************************************************************************
* 	function:	empty							*
* 	purpose:	returns true if the dictionary is empty			*
********************************************************************************/
		bool empty()
		{
			if (dictWords.empty())
				return	true;
			else
				return	false;
		}
/********************************************************************************
*	function:	size							*
*	purpose:	returns the size of the dictionary			*
********************************************************************************/
		int size(){ return dictWords.size(); }
/********************************************************************************
* 	function:	at							*
* 	purpose:	returns the element at the given index			*
********************************************************************************/
		string at(int index){ return dictWords[index]; }
};
// Variable to hold our dictionary which will be used throughout the program
Dictionary MyDictionary;
/********************************************************************************
*	function:	main							*
*	purpose:	The beginning of the program				*
********************************************************************************/
int main()
{
	string	start,final;
	MyDictionary.initVector();
	if(!MyDictionary.empty())
	{
		cout << "\nPlease enter the starting word (or STOP to quit the program):\n";
		cin >> start;
		cout << "Please enter the final word:\n";
		cin >> final;
		while(start != "STOP")
		{
			cout << "\nSearching for a word ladder...\n";
			if(!MyDictionary.findWords(start,final))
			{
   			//keeps track of words that have been used
   			list<string> usedWords;
   			list<string>::iterator p;
   			
   			wordStack tempStack;
   			queue <wordStack> stackQ;
   			tempStack.push(start);
   			usedWords.push_back(start);
   			stackQ.push(tempStack);
   			
   			while( stackQ.size() != 0 and (stackQ.front()).top() != final)
   			{	tempStack = stackQ.front();
   				stackQ.pop();
   				string wordFound = findNextWord(tempStack.top());
   				while (wordFound != "done")
   				{	p = find(usedWords.begin(), usedWords.end(), wordFound);
   					if (p == usedWords.end())  //Checks if the word has already been used
   					{	usedWords.push_back(wordFound);
   						//cout << wordFound << " has been used" << endl;
   						wordStack newStack = tempStack;
   						newStack.push(wordFound);
   						stackQ.push(newStack);	
   					} 
   					wordFound = findNextWord(tempStack.top());
   				}
   				findNewWord();
   			}
   			try
   			{	
   				if (stackQ.size() == 0)
   				{	
   					throw stackQ;
   				}
   				stack<string> leStack = stackQ.front();
				cout << "\nFor the input words "<< start << " and " << final;
				cout << " the following ladder was found.\n\n";
				//int wordLadderSize = wordLadder.size();
				//cout<< "word ladder size = " << wordLadderSize<<endl;
					
				stack<string> wordLadder;
				while (!leStack.empty())
				{	wordLadder.push(leStack.top());
					leStack.pop();
				} 
				while (!wordLadder.empty())
				{	cout << wordLadder.top() << "\n";
					wordLadder.pop();
				}
			}
			catch ( queue<wordStack> stackQ)
			{	cout<<"\n-- No word ladder exists for \""<<start<<"\" and \""<<final<<"\" --"<<endl;
			}
		    	cout<< endl;
		    }    		
			cout << "\nEnter starting word (or STOP to stop):\n";
			cin >> start;
			if (start == "STOP")
				continue;
			cout << "Enter ending word:\n";
			cin >> final;
		}
	}
	else
	{
		return 0;
	}
	// The user has entered the sentinel and the program will terminate
	cout << "\n**You have entered \"STOP\", the program will now terminate**\n";
	return	0;
}
/********************************************************************************
*	function:	findNextWord						*
*	purpose:	find the next word in the word ladder			*
********************************************************************************/
string findNextWord(string word)
{
	while(dictIndex < MyDictionary.size())
	{
		string temp = MyDictionary.at(dictIndex);
		int index1 = temp.find_first_not_of(word);
		int index2 = temp.find_last_not_of(word);
		if (index1 == index2 && index1 != -1)
		{
			if ((temp.substr(index1 + 1) == word.substr(index1+1))  &&
			 (temp.substr(0, index1) == word.substr(0, index1)))
			{
				dictIndex++;
				return temp;
			}
		}
		dictIndex++;
	}
	//cout<< " no words found" << endl;
	const string DONE = "done";
	return DONE;
}
/********************************************************************************
*	function:	findNewWord						*
*	purpose:	Resets the dictIndex					*
********************************************************************************/
void findNewWord(){ dictIndex = 0; }