#include<iostream>
#include<vector>
#include<cstdlib>
#include<fstream>
#include<string.h>
#define ALPHABETS 26
#define MAX_WORD_SIZE 100
using namespace std;


class TrieTreeNode
{

public:

    TrieTreeNode* parent;

    TrieTreeNode* children[ALPHABETS];
    vector<int> occurrences;
};

class TrieTree
{

public:

    TrieTreeNode* root;
    TrieTree();
    void tree(char text[], int index);

    void PrintWord(TrieTreeNode* trie_tree, vector<char> printUtilVector);
    TrieTreeNode* searchWord(TrieTreeNode* trie_tree, char* text);
    void deleteWord(TrieTreeNode* trie_tree, char* word);



};

TrieTree::TrieTree()
{

    root = (TrieTreeNode*)calloc(1, sizeof(TrieTreeNode));

}

void TrieTree::tree(char text[], int index)
{

    vector<char> word(text, text + strlen(text));
    TrieTreeNode* temp = root;
    int i = 0;

    while (i < word.size())
    {

        if (temp->children[word[i] - 'a'] == NULL)
        {

            temp->children[word[i] - 'a'] = (TrieTreeNode*)calloc(1, sizeof(TrieTreeNode));

            temp->children[word[i] - 'a']->parent = temp;

        }

        temp = temp->children[word[i] - 'a'];

        ++i;

    }

    temp->occurrences.push_back(index);

}

void TrieTree::PrintWord(TrieTreeNode* trie_tree, vector<char>printUtil)
{

    int i, j;
    string inword;
    char AAA[1];

    bool noChild = true;

    vector<int>::iterator itr = trie_tree->occurrences.begin();

    for (i = 0; i < ALPHABETS; ++i)
    {

        if (trie_tree->children[i] == NULL)
        {

            continue;

        }

        else
        {

            noChild = false;

            printUtil.push_back('a' + i);
            PrintWord(trie_tree->children[i], printUtil);
            printUtil.pop_back();
        }

    }

    if (trie_tree->occurrences.size() != 0)
    {

        vector<char>::iterator itr = printUtil.begin();
        ofstream outputFile("tree.txt", ios::out);

        if (!outputFile)
        {

            cout << "Error !! some thing wrong during opening file:/" << endl;


        }

        while (itr != printUtil.end())
        {

            cout << *itr;

            ++itr;


        }

        outputFile << "*" << endl << "&";

        cout << "\n";

    }

    printUtil.pop_back();

}

TrieTreeNode* TrieTree::searchWord(TrieTreeNode* trie_tree, char* text)
{

    vector<char>word(text, text + strlen(text));
    TrieTreeNode* temp = trie_tree;

    while (word.size() != 0)
    {

        if (temp->children[word[0] - 'a'] != NULL)
        {

            temp = temp->children[word[0] - 'a'];
            word.erase(word.begin());
        }

        else

        {

            break;

        }

    }

    if (word.size() == 0 && temp->occurrences.size() != 0)
    {

        return temp;

    }

    else
    {

        return NULL;

    }

}

void TrieTree::deleteWord(TrieTreeNode* trie_tree, char* word)

{

    TrieTreeNode* temp = searchWord(trie_tree, word);

    if (temp == NULL)
    {

        cout << "not found\n";
        return;
    }

    temp->occurrences.pop_back();
    bool noChild = true;
    int childCount = 0; int i;

    for (i = 0; i < ALPHABETS; ++i)
    {

        if (temp->children[i] != NULL)
        {

            noChild = false;

            ++childCount;

        }

    }

    if (!noChild)
    {

        return;

    }

    TrieTreeNode* traverse;

    while (temp->occurrences.size() == 0 && temp->parent != NULL && childCount < 2)
    {

        traverse = temp->parent;

        for (i = 0; i < ALPHABETS; ++i)
        {

            if (temp == traverse->children[i])
            {

                traverse->children[i] = NULL;
                break;

            }

        }

        free(temp);
        temp = traverse;

        for (i = 0; i < ALPHABETS; ++i)
        {

            if (temp->children[i] != NULL)
            {

                ++childCount;

            }

        }

    }

}

int main()

{

    int number, i, j, n;

    char inword[1][MAX_WORD_SIZE];

    char words[6000][MAX_WORD_SIZE];
    char ensertword[1][MAX_WORD_SIZE];
    char wantedword[MAX_WORD_SIZE][MAX_WORD_SIZE];
    TrieTreeNode* temp;

    TrieTree trie;
    vector<char> util;
    ifstream inputFile("D:\\#DEVELOPING Home\\C++ PROJECTS\\Trie Tree\\wordsEn.txt", ios::in);
    if (!inputFile)
    {

        cout << "Error !! file not found :|" << endl;
        return 0;
    }

    for (i = 0; i < 6000; i++)
    {

        inputFile >> words[i];
        trie.tree(words[i], i + 1);
    }

    for (; 1 == 1;)
    {

        cout << "\nEXIT = 0\nINSERT = 1\nDELETE = 2\nSEARCH = 3\nPRINT = 4\nSPEEL_CHECHER = 5\n";
        cout << "\npleas enter number : ";
        cin >> number;

        if (number == 0)
        {

            cout << "\nEXIT\nGood Luck :)\n";

            break;

        }

        if (number == 1)
        {

            cout << "INSERT\npleas enter word : ";
            cin >> ensertword[0];
            trie.tree(ensertword[0], i + 1);
        }

        if (number == 2)
        {

            cout << "DELETE\npleas enter word : ";
            cin >> inword[0];
            trie.deleteWord(trie.root, inword[0]);
        }

        if (number == 3)
        {

            cout << "SEARCH\npleas enter word : ";
            cin >> inword[0];
            temp = trie.searchWord(trie.root, inword[0]);

            if (temp == NULL)
            {

                cout << "not found\n";

            }

            else
            {

                cout << "found\n";

            }

        }

        if (number == 4)
        {

            cout << "PRINT \n";
            trie.PrintWord(trie.root, util);
        }

        if (number == 5)
        {

            long start, ende;

            ifstream inputFile("wordsEn.txt", ios::in);

            if (!inputFile)
            {

                cout << "Error !! file not found :|" << endl;
                return 0;
            }

            cout << "enter number how much is word ? ";
            cin >> n;
            cout << "if your word is not found in txt show word in ()\n ";

            for (j = 0; j < n; j++)
            {

                inputFile >> wantedword[j];
                temp = trie.searchWord(trie.root, wantedword[j]);

                if (temp == NULL)
                {

                    cout << "(" << wantedword[j] << ")";

                }

                else
                {

                    cout << " " << wantedword[j] << " ";

                }

            }

        }

    }

    return 0;

}