#include <cstdlib>
#include <iostream>
#include <fstream>
#include <cassert>
#include <cstring>
#include <cctype>
using namespace std;


struct node{
      char letter;
      bool isWord;
      node* child;
      node* sibling;
};

struct Rhymes{
      char** words;
      int length;
};

char* removeFirstChar(char* word)
{
//	cout << word << endl;
      char* retWord = new char[strlen(word)];
      for(int i =1; i < strlen(word)+1; i++)
      {
            retWord[i-1] = word[i];
      }
//	  cout << retWord << endl;
      return retWord;
}

node* createChild(char letter, int length)
{
      node* child = new node;
      child->letter = letter;
      child->child = NULL;
      if(length > 1)
      {

            child->isWord = false;
      }
      else
      {
            child->isWord = true;
      }

}

void insertLetter(node* head, char* word, int length)
{

      if(head->child == NULL)
      {
			node* child = createChild(word[0], length);

            node* sibling = createChild('\0', 2);

            sibling->sibling = head;
            child->sibling = sibling;
            head->child = child;
            if(length > 1)
                  insertLetter(child,removeFirstChar(word), length-1);
      }
      else if(head->child->letter == word[0])
      {
            node* loc = head->child;
            if(length == 1)
            {
                  loc->isWord = true;
            }
            else
            {
                  insertLetter(loc, removeFirstChar(word), length-1);
            }
      }
      else
      {
            node* child = createChild(word[0], length);
            if(word[0] < head->child->letter)
            {
                  child->sibling = head->child;
                  head->child = child;
            }
            else
            {

			head = head->child;
			while(word[0] > head->sibling->letter && head->sibling->letter != '\0')
                {
                    head = head->sibling;
                }
              if(word[0] != head->sibling->letter)
              {
                      child->sibling = head->sibling;
                      head->sibling = child;
              }
            }
            if(length > 1)
                  insertLetter(child,removeFirstChar(word), length-1);

      }
}





void findWords(node* head, char* suffix, Rhymes &words, int length)
{
      char* tempSuffix = new char[25];
    while(head->letter != '\0')
    {
       words.words = (char **) realloc(words.words, sizeof(char **) * words.length+1);
       words.words[words.length] = (char *) malloc(25 * sizeof(char));

        if(head->isWord == true)
        {
            int i;
            for(i=0; i < length; i++)
            {
                  tempSuffix[i] = suffix[i];
            }
            tempSuffix[i+1] = head->letter;
            tempSuffix[i+2] = '\0';
            strcpy(words.words[words.length], tempSuffix);
			cout << words.words[words.length] << endl;
			words.length++;
		}
        if(head->child != NULL)
        {

            findWords(head->child, tempSuffix, words, length+1);
        }
        head = head->sibling;

    }
		cout << &words << endl;

 }
void locateRhyme(char* suffix, node* head, Rhymes &words)
{
      int length = strlen(suffix);
      int depth = 0;
      node* temp = new node;
      temp = head->child;
      while(depth != length)
      {
            if(suffix[depth] != temp->letter && temp->letter != '\0')
            {
                  temp = temp->sibling;
            }
            else if(temp->letter == '\0')
            {
                  cout << "There are no matching words" << endl;
                  break;

            }
            else
            {
                  depth++;
                  temp = temp->child;
            }
      }
	findWords(temp,suffix,words, length);


}


//-----------------------------------------------------------------------------------
// Convert word to lower case
void convertToLowerCase( char theWord[], const int size)
{
   // convert dictionary word to lower case
   for (int i=0; i<size; i++) {
      theWord[i] = tolower(theWord[i]);
   }
}


//-----------------------------------------------------------------------------------
// Reverses the string Note:changing the orginal string
char * strReverse(char *str)
{
      char *p1, *p2;

      if (! str || ! *str)
            return str;
      for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
      {
            *p1 ^= *p2;
            *p2 ^= *p1;
            *p1 ^= *p2;
      }
      return str;
}


//-----------------------------------------------------------------------------------
// Read from the dictionary file into an array, only keeping words that are the correct
// length.
void readDictionary( node* head )                 // pointer to dictionary
{
      ifstream inStream;                                 // input file stream
      char fileName[] = "dictionary.txt";      // Input file name
      char tempString[25];       // stores a single string
      int  size;                                // string size
		bool insert = true;
   inStream.open( fileName);
   assert( ! inStream.fail() );  // make sure file open was OK

      cout << "\n Reading dictionary file from " << fileName << "\n";
      int currentRow = 0;
          int i = 0;
      while ( inStream >> tempString ) {
            size = strlen( tempString);
            insert = true;
			while(tempString[i])
			{
				if(!isalpha(tempString[i]))
					insert = false;
				i++;
			}
			if(insert)
			{
                  convertToLowerCase( tempString, size);    // convert word to lower case
                  // Only store words that aren't too long or too short
                  strcpy( strReverse(tempString), tempString);
                  insertLetter(head,tempString,size);
            }
      }
            // Verify that we still have room in array

   inStream.close(); // close the input file stream

}


//-----------------------------------------------------------------------------------
// Display words within the boundaries of a certain size.
// This should only be used for debugging.
void displayWords(
    //  char theWords[][ MaxLength+1],      // array of dictionary words
      int limit)                          // number of words in dictionary
{
      int displaySizeMax;           // Max size string to display
      int displaySizeMin;           // Min size string to display
      int size;               // stores size of strings

   //cout << "(Stored words are of size " << MinLength << " to " << MaxLength << ")\n";
      cout << "Please enter min. and max. sizes of strings to display: ";
      cin >> displaySizeMin >> displaySizeMax;

      cout << "\nWords stored in array are: \n";
      for (int i=0; i<limit; i++) {
    //        size = strlen( theWords[ i]);
    //        if ( (size >= displaySizeMin) && (size <= displaySizeMax) )
      //            cout << theWords[ i] << " ";
      }
      cout << " \n";          // leave an extra line at the end
}


int main()
{
        int numberOfWords= 0;                         // number of dictionary words

        // Read words from input file into dictionary array
//      readDictionary( dictionary, numberOfWords);

        // Selectively display words from dictionary array
//      displayWords( dictionary, numberOfWords);

   // Lookup a word in the dictionary using binary search
   node* head = new node;
   head->letter = '\0';
   head->isWord = false;
   head->sibling = NULL;
   head->child = NULL;
   readDictionary( head );
   char aWord[ 25];
   string bWord;
   cout << "Enter a word for which to search.  (Max length is " << 25 << ")  ->";
   cin >> aWord;
   //strReverse(aWord); //String reversal nevermind!!!

   cout << aWord << endl;

   convertToLowerCase( aWord, strlen( aWord) );    // Ensure input is lower case
   strReverse(aWord);//reverses the c-string
   //string tmpStr(aWord);//Converts into string
   Rhymes words;
 		cout << &words << endl;
   words.length = 1;
     words.words = (char **) malloc(sizeof(char **) * 1);
     words.words[0] = (char *) malloc(25 * sizeof(char));

//	words.words = (char**)malloc()
 //display appropriate message depending on whether or not the word is found
   //bWord=tmpStr.substr(0,3);// takes in the first three letters of the reversed string...viz. the last three letters of the original string
   locateRhyme(aWord, head, words);
   cout << bWord << endl;
	for(int i = 0; i < words.length; i++)
	{
		cout << words.words[i] << endl;
	}
   return 0;
}