#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>


class Trie
{
private:
    struct Node {
        bool end_node = false; 
        std::unordered_map<char, Node*> children;
    };

private:
    void remove_trie(Node* node) 
    {
        for (auto [_, child] : node->children) {
            remove_trie(child);
        }
        delete node;
    }


public:
    Trie() 
        : m_trie(new Node())
    { }

    void add(const std::string &key)
    {
        auto trie = m_trie;

        for (auto c : key) {
            if (trie->children.find(c) == trie->children.end()) {
                trie->children[c] = new Node();
            }
            trie = trie->children[c];
        }

        trie->end_node = true;
    }

    bool find(const std::string &key)
    {
        auto trie = m_trie;

        for (auto c : key) {
            if (trie->children.find(c) == trie->children.end()) {
                return false;
            }
            trie = trie->children[c];
        }

        return trie->end_node;
    }

    void autocomplete(const std::string &prefix)
    {
        auto trie = m_trie;

        for (auto c : prefix) {
            if (trie->children.find(c) == trie->children.end()) {
                std::cout << "None found!" << std::endl;
                return;
            }

            trie = trie->children[c];
        }

        std::vector<std::string> words;
        get_words(trie, words);

        std::cout << prefix << std::endl;
        for (auto word : words) {
            std::cout << "|->" << prefix + word << std::endl;
        }
    }

    ~Trie() 
    {
        remove_trie(m_trie);
    }

private:
    void get_words(Node *node, std::vector<std::string> &words)
    {
        static std::string word;

        if (node->end_node) {
            words.push_back(word);
        }

        for (auto [c, child] : node->children) {
            word.push_back(c);
            get_words(child, words);
            word.pop_back();
        }
    }

private:
    Node *m_trie;
};

int main(void)
{
    std::vector<std::string> words = { "cod", "coder", "coding", "codecs" };

    auto trie = new Trie();

    for (auto word : words) {
        trie->add(word);
    }

    trie->autocomplete("co");

    delete trie;
    
    return 0;
}