#include <fstream>
#include <iostream>
#include <string>

using namespace std;

class NODE
{
public:
    bool eow;
    NODE* ptrs[26];

    NODE()
    {
        eow = false;
        for (short j = 0; j < 26; ++j)
        {
            ptrs[j] = nullptr;
        }
    }

    ~NODE()
    {
        eow = true;
        for (int i = 0; i < 26; i++)
        {
            ptrs[i] = nullptr;
        }
    }
};

using TrieTree = NODE*;

void init(TrieTree t)
{
    t = nullptr;
}

void add(TrieTree& t, const string word, short i)
{
    if (!t)
    {
        t = new NODE;
    }
    if (static_cast<short>(word.length()) - 1 < i)
    {
        t->eow = true;
    }
    else
    {
        add(t->ptrs[word[i] - 'a'], word, i + 1);
    }
}

bool _all_ptrs_empty(TrieTree t)
{
    bool result = true;
    int i = 0;
    while (i < 26 && result)
    {
        if (t->ptrs[i])
        {
            result = false;
        }
        else
        {
            i++;
        }
    }
    return result;
}

bool del(TrieTree& t, const string word, short i) //сделать remove bool
{
    bool result = false;
    if (t)
    {
        if (i <= static_cast<short>(word.length() - 1))
        {
            result = del(t->ptrs[word[i] - 'a'], word, i + 1);
        }
        else
        {
            t->eow = false;
            if (_all_ptrs_empty(t))
            {
                delete t;
                t = nullptr;
            }
            result = true;
        }
    }
    return result;
}

void print(TrieTree t, string word)
{
    if (t->eow)
    {
        cout << word << endl;
    }
    for (int i = 0; i < 26; ++i)
    {
        if (t->ptrs[i])
        {
            print(t->ptrs[i], word + static_cast<char>(i + 'a'));
        }
    }
}
// node - узел, word - слово которое собирается в трай дереве, phrase - фраза которую ищем в начале, count - количество
// слов, которые имеют в начале себя phrase, phrasePos - позиция символа в phrase для сравнения с символами на разных узлах дерева
void task(TrieTree node, const string& word, const string& phrase, size_t& count, const size_t& phrasePos)
{
    // Если слово закончилось, и наша позиция перешла или равна длине фразы, то мы её содержим, а значит подсчитываем и выводим
    if (node->eow && phrasePos >= phrase.size())
    {
        count++;
        cout << word << endl;
    }
    // Бежим по всем символам
    for (int i = 0; i < 26; ++i)
    {
        // Если мы не пустые и ( либо позиция символа в фразе уже вышла за пределы длины [а значит слово уже входит], либо должны
        // совпасть символы)
        if (node->ptrs[i] && (phrasePos >= phrase.size() || static_cast<char>(i + 'a') == phrase[phrasePos]))
        {   // Запускаем рекурсию с позицией в фразе+1
            task(node->ptrs[i], word + static_cast<char>(i + 'a'), phrase, count, phrasePos + 1);
        }
    }
}

void clear(TrieTree& t)
{
    for (int i = 0; i < 26; ++i)
    {
        if (t->ptrs[i])
        {
            clear(t->ptrs[i]);
        }
    }
    delete t;
    t = nullptr;
}

class TRIE_tree
{
public:
    TrieTree root;
    TRIE_tree() { init(root); }

    TRIE_tree(string path)
    {
        init(root);
        ifstream i_file(path);
        string word = "";
        while (!i_file.eof())
        {
            getline(i_file, word);
            add_word(word);
        }
    }

    ~TRIE_tree();
    void add_word(string word);
    bool all_ptrs_empty(TrieTree t);
    bool tree_empty(TrieTree t);
    bool del_word(string word);
    void clear_tree();
    void print_tree();
};


int main()
{
    ifstream file("data_1.txt");
    if (!file)
    {
        cout << "Error!\n";
    }
    else
    {
        TrieTree t = nullptr;
        init(t);
        string word;
        while (!file.eof())
        {
            getline(file, word);
            if (word.length())
            {
                add(t, word, 0);
            }
        }
        print(t, "");
        cout << "--------\n";
        size_t counter = 0;
        task(t, "", "wo", counter, 0);
        cout << "Amount: " << counter << endl;
        //taskprint(t, "", false);
        clear(t);
    }
    return 0;
}