/* ------------------------------------------------
 * Basic Calculator with + - / *
 *
 * Class: CS 251, Fall 2014.  Thur 10 am lab.
 * System: Xcode on Mac OSX
 * Author: Quan Zheng
 *
 * ToDo: Program 5 Rhymes With
 * -------------------------------------------------
 */
#include <iostream>
#include <fstream>
#include <cassert>
#include <cctype>
#include <stdlib.h>
using namespace std;
const int Max_letter = 27; // Constant 26 letters
struct Node{
    char c;
    int isWord;
    Node *letter[27];
};
int Get_Char_Pos(char c)
{
    int temp = c;
    if(temp == '\'')
        return 27;
    else
    return c - 97;
}
//reverse the array
void reverse_a(char x[], char *&y)
{
    int count = 0;
    for(int i = 0; i < 26; i++)
    {
        count++;
        //int temp = x[i];
        if(x[i] == '\0')
        {
            break;
        }
    }
    y = new char[count-1];

    for(int i = 0; i <= count; i++)
    {
        y[i] = x[count-i-2];
    }
}
void reverse_b(char x[], char *&y,int count)
{

    y = new char[count-1];

    for(int i = 0; i <= count; i++)
    {
        y[i] = x[count-i-2];
    }
}
int Get_Char_Len(char *x)
{
    int count = 0;
    for(int i = 0; i <26; i++)
    {
        //int temp = x[i];
        if(x[i] == '\0')
        {
            break;
        }
        count++;
    }
    return count;
}
//No string
void insertNode(Node *&pHead,char c, int isWord)
{
    Node *pTemp = new Node;

    pTemp->c = c;
    if(isWord == 1)
        pTemp->isWord = 1;
    pTemp->letter[Get_Char_Pos(c)] = NULL;

    // Reset pointers depending if this is the first node
    if( pHead != NULL) {
        pTemp->letter[Get_Char_Pos(c)] = pHead;  // Connect into list
    }
    // Reset head pointer
    pHead = pTemp;
}
//put words into array of linkedList
void insertLinkedList(Node **&dictionary,char temp[])
{
    int len = 100;
    int pos = Get_Char_Pos(temp[0]);
    insertNode(dictionary[pos],temp[0],1);
    int i;
    for(i = 1; i <len; i++)
    {
        if(temp[i] > 96 && temp[i] < 123)
        insertNode(dictionary[pos],temp[i],0);
        else if(temp[i] == 39)
            insertNode(dictionary[27],temp[i],0);
        else
            break;
    }
}
void readDictionary(Node **&dictionary)
{
    ifstream inStream; 					   // input file stream
    char fileName[] = "dictionary.txt";	// Input file name
    char tempString[100];	      // stores a single string
    inStream.open( fileName);
    assert( ! inStream.fail() );  // make sure file open was OK
    while ( inStream >> tempString ) {
        insertLinkedList(dictionary,tempString);
    }
    inStream.close(); // close the input file stream
}
void Menu()
{
    cout<< "Program 5 : Rhymes With "<<endl;
    cout<< "\t Using a trie to find rhyming words."<<endl;
    cout<< "Autho: Quan Zheng " <<endl;
    cout<< "Class: CS 251, Fall 2014"<<endl;
    cout<< "System: Xcode on MacBook Pro"<<endl<<endl;
    cout<< "Enter the suffix to find rhyming words[max = 25]: ";
}
void displayList( Node* pHead, char *word, int *number_of_word)
{
    char iWord[26];
    int len = Get_Char_Len(word);
    char *temp = new char[26];
    int is_equal = 0;
    int count = 0;
    while( pHead != NULL) {
        temp[count] = pHead->c;
        count++;
        int is = pHead->isWord;
        if(is)
        {
            //cout<<"*";
            for(int i = 0 ; i < len ;i ++)
            {
                if(temp[i] == word[i])
                    is_equal = 1;
                else{
                    is_equal=0;
                break;
                }
            //    cout<<" "<<temp[i];
            }

            if(is_equal ==1)
            {
                for(int i = 1 ; i <=count ; i++)
                {
                    cout<<temp[count-i];
                }
                //cout<<t;
                delete(temp);
                cout<<endl;
                *number_of_word +=1;
            }

            count = 0;
            temp = new char[26];
        }
        char temp_c = pHead->c;
        int i = Get_Char_Pos(temp_c);
        if(i <0)
            i = 0;
            //cout<<i<<endl;
        pHead = pHead->letter[i];

    }
}
int main()
{
    int a = '\'';
    cout << a <<endl;
    int count = 0;
    Node **dictionary;
    char iWord[26];
    char *iWord_rev = new char[26];
    //string iWord,iWord_rev; //get word & reverse word
    Menu();
    //allocate dynamic array for size of 26 linkedlist
    dictionary =(Node**)malloc(sizeof(Node*)* Max_letter);
    for(int i = 0; i < Max_letter ; i++)
        dictionary[i] = (Node*)malloc(sizeof(Node));

    //End of allocating,, dictionary[1] is not allocated in loop
    readDictionary(dictionary);
    cin >>iWord;  //get word
    reverse_a(iWord,iWord_rev);
    //cout<<iWord_rev<<endl;
    int c = 0;
    for(int i = 0 ; i < Max_letter ; i++)
    {
        displayList(dictionary[i],iWord_rev, &c);
    }
    cout<<"Found "<<c<<" words which are above:"<<endl;
    cout<<endl<<endl;
    cout<<"Exiting program..."<<endl;
    return 0;
}