/*-------------------------------------------------------------
 * Program 5: Rhymes With
 *
 * Class: CS 251, Fall 2014.
 * System: Xcode on Mac OSX
 * Author: Laith Sarhan, Dale Reed (various use of sample codes)
 *
 * This program
 * -------------------------------------------------------------
 */
/*  Running this program looks like
 Author:  Laith Sarhan
 Lab:     Thursday 12 pm
 Program: #3, Display Tree (BINARY HEAP VERSION)
 Starting Heap program

 Exiting program...

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


// read in words from dictinary, character by character, DFS

// define global constants and structures
#define MAX_SIZE 1000+1    // Add 1 because we start at position 1, not 0


// struct to hold nodes
struct node{
    char c;
    node  *letters[26];
    bool isWord;
    int vertex;
    node *pLink;
};

// Function prototypes
void progInfo();

char convert(int i)
{
    return (i%26) + 'a';
}

// Depending on the computer, if the values below are too large,
//   your program will cause a "segmentation fault."  I suggest
//   you make the value of MaxLength something smaller in this case.
const int MinLength = 3;      // minimum word size
const int MaxLength = 10;     // maximum word size
const int Rows = 260000;       // max array size to handle all words on Unix system

//-----------------------------------------------------------------------------------
// 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;
}


void init(node *&head){
    head = new node();
    head->c = '\0';
    head->isWord = false;

}

void insert (node *&head, char word[]){
    node *current = head;

    for(int i = 0; i < strlen(word); i++){
        int pos = (int)word[i] - (int)'a';

        if (current -> letters[pos] == NULL){
            current->letters[pos] = new node();

//            current ->letters[pos]->c = word[i];
//            current =current->letters[pos];
//            break;
        }

        current ->letters[pos]->c = word[i];
        current =current->letters[pos];
    }


    current-> isWord = true;

}



bool search (node  *&head, char word[]){
    node *current = head;
    for (int i = 0; i < strlen(word); i++){
        if(current->letters[((int)word[i] - (int)'a')] == NULL){
            return false;
        }

        current = current->letters[((int)word[i] - (int)'a')];
    }
    return current->isWord;
}

////Function to visit nodes in Preorder
void dfs( node *&rot){//, char word[]) {
      static int counter = 0;
    static char tempString[50];
    tempString[counter + 1] = '\0';
    cout << "root is: " << rot->c <<endl;
    tempString[counter] = rot->c;

    node *current = rot;


    for (int i = 0; i < 26; i++){
         if(current->letters[i] != NULL){

            if (current ->isWord == true){
                cout << "the word is: " << strReverse(tempString) << "eed" << endl;
                strReverse(tempString);
            }


            counter++;

            dfs(current->letters[i]);
            counter--;
        }

    }
}




void searchNprint (node  *&head, char word[]){
    node *current = head;
    char tempString[50];
    for (int i = 0; i < strlen(word); i++){
        // int letter = (int)word[i] - (int)'a';
        if(current->letters[((int)word[i] - (int)'a')] == NULL){
            cout << "You hit a null brehh.." << endl;
            return;
        }

        cout << convert((int)word[i] - (int)'a') << endl;
        tempString[i] = convert((int)word[i] - (int)'a');

        //if (i != strlen(word)-1)
        //{
        //cout << "current is at: " << current->c << endl;
        current = current->letters[((int)word[i] - (int)'a')];
        //}

    }

   // cout << " the full word is " << strReverse(tempString) << endl;
    cout << "passing in : " << current->c << endl;
    //do dfs for all children of suffix
    dfs(current);
}

//-----------------------------------------------------------------------------------
// Read from the dictionary file into an array, only keeping words that are the correct
// length.
void readDictionary(
                    char words[][ MaxLength+1], 	// array of dictionary words
                    int &currentRow, node *& head)			   // number of words in dictionary
{
    ifstream inStream; 					   // input file stream
    char fileName[] = "dictionary.txt";	// Input file name
    char tempString[MaxLength+1];	      // stores a single string
    int  size;
    int counter = 0;
    int alphaCheck = 0; // string size

    inStream.open( fileName);
    assert( ! inStream.fail() );  // make sure file open was OK

    cout << "\n Reading dictionary file from " << fileName << "\n";
    currentRow = 0;



    while ( inStream >> tempString ) {
        size = strlen( tempString);
        convertToLowerCase( tempString, size);

        for (int i = 0; i < size; i++){
            if(isalpha(tempString[i])){
                alphaCheck = 1;
            }
            else{
                alphaCheck = 0;
                break;
            }
        }

        if (alphaCheck == 1){
            // Only store words that aren't too long or too short
            //  if ( (size <= MaxLength ) && (size >= MinLength) ) {
            insert(head, strReverse(tempString));
            //  strcpy( strReverse(words[ currentRow++]), tempString);
            // }
            counter++;
        }

        // Verify that we still have room in array
        if (currentRow >= Rows) {
            cout << "*** Error, just read word " << tempString
            << " and currentRow is now at: " << currentRow
            << endl;
        }
        assert( currentRow < Rows);   // halt program if error
    }





    inStream.close(); // close the input file stream
    cout << " the number of valid words are: " << counter << endl;
}


//-----------------------------------------------------------------------------------
// 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 << "\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
}


//-----------------------------------------------------------------------------------
// Look up the word in the dictionary array, returning true if found, false otherwise
bool wordWasFound(
                  char pWord[],                      // the word for which we are searching
                  char dictionary[][ MaxLength + 1], // dictionary array
                  int numberOfDictionaryWords)       // number of words in dictionary array
{
    printf("\nWord that I am about to compare %s\n", pWord);
    for (int i=0; i< numberOfDictionaryWords; i++)
    {
        //printf("Dictionary[%d] = %s BEFORE strncmp\n", i, dictionary[i]);//EDIT THIS CODE
        if( strncmp( pWord, strReverse(dictionary[i]), 3) == 0)
        {
            strReverse(dictionary[i]); //Reverse word back to original
            // printf("Dictionary[%d] = %s AFTER strncmp\n", i, dictionary[i]);
            cout << dictionary[i]<< "  is rhyming with the given word. \n";
            //  return true;    // Found the word!
        }
    }
    return false;       // Did not find the word

    //cout<< "word wasnt found. \n";
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
// Perform a depth-first search (DFS)
void depthFirstSearch(int currentVertex, node *graph[], int visited[ ])
{
    node * pTemp;
    visited[ currentVertex] = 1;   // set visited value to true for this vertex

    cout << currentVertex << " ";  // display vertex being visited

    // Examine in turn each vertex on adjacency list
    for (pTemp = graph[ currentVertex]; pTemp!=NULL; pTemp = pTemp->pLink) {
        // If it hasn't already been visited, recursively visit it
        if( !visited[ pTemp->vertex]) {
            depthFirstSearch( pTemp->vertex, graph, visited);
        }
    }//end for( pTemp = ...

}//end depthFirstSearch(...


// Main function of program that takes user's input as queue for a binary heap,
// inserts and sorts it in a min heap, than displays the levels as a tree in
// ascii characters
int main() {
    // Clears console screen, not necessary/used for tidiness
    system("clear");

    // Author & program info
    progInfo();

    node *head = NULL;
    int visited[ Rows];   // Which nodes have been visited so far on traversal

    init(head);

    char dictionary[ Rows][MaxLength+1];  // array of dictionary words
    int numberOfWords= 0;			      // number of dictionary words

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

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

    // Lookup a word in the dictionary using binary search
    char aWord[ MaxLength];
    cout << "Enter a word for which to search.  (Max length is " << MaxLength << ")  ->";
    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

    //display appropriate message depending on whether or not the word is found
    //    if ( wordWasFound( aWord, dictionary, numberOfWords) ) {
    //        cout << "This  rhyming word IS in the dictionary. \n";
    //    }
    //    else {
    //        cout << "This rhyming word is NOT in the dictionary. \n";
    //    }

    //searchNprint(head, aWord);


    // dfs(head, aWord);
    //    if( search(head, aWord) == true){
    //        cout << "This word IS in the trie. \n";
    //    }
    //    else {
    //       cout << "This word is NOT in the trie. \n";
    //    }



    // Do a depth-first search (DFS).
    //
    // First initialize visited[] array to all 0s.  Once visited, elements
    // are set to 1.
    //for( int i=0; i<Rows; i++) {
    //  visited[ i] = 0;
    //}
    //cout << "Depth First Search gives: ";
    //depthFirstSearch( 1, head, visited);   // start at node 1.  0 is unused.
    //cout << endl;

    searchNprint(head, aWord);

    cout << "\n\nExiting program...\n";
    return 0;
}

// This function displays author of program, lab time, and program name
void progInfo()
{
    cout<<"Author:  Laith Sarhan\n"
    "Lab:     Thursday 12 pm\n"
    "Program: #5, Rhymes With\n"
    ;

}