#include <map>
#include <string>
#include <vector>
#include <iostream>

struct Node {
    std::map<std::string, Node> children;
};

class Tree {
private:
    Node root;

public:
    bool Has(const std::vector<std::string> &node) const;

    void Insert(const std::vector<std::string> &node);

    void Delete(const std::vector<std::string> &node);

    void print(Node &cur);

    Node & getroot() {
        return root;
    }
};

bool Tree::Has(const std::vector<std::string> &node) const {
    auto it = node.begin();
    Node cur = this->root;
/*
    for (auto& [key, val] : cur.children)
        std::cerr << key << ' ';
*/
    for (; it != node.end() && cur.children.find(*it) != cur.children.end();
           cur = cur.children[*it]) {}
    return it == node.end();
}

void Tree::Insert(const std::vector<std::string> &node) {
    if (Has(node))
        return;

    auto it = node.begin();
    Node cur = this->root;
    for (; it != node.end(); ++it) {
        if (cur.children.find(*it) == cur.children.end())
            cur.children[*it] = Node();
        // std::cerr << (cur.children.find(*it) != cur.children.end()) << std::endl;
        // for (auto& [key, val] : cur.children)
            // std::cerr << key << ' ';
        cur = cur.children[*it];
    }
}

void Tree::Delete(const std::vector<std::string> &node) {
    if (!Has(node))
        return;

    auto it = node.begin();
    Node cur = this->root;

    uint32_t counter = 0;
    for (; it != node.end() && cur.children.find(*it) != cur.children.end(); ++counter) {
        if (counter + 1 == node.size())
            cur.children.erase(*it);
        else
            cur = cur.children[*it];
    }
}

void Tree::print(Node &cur) {
    for (auto& [key, val] : cur.children)
        std::cout << key << ' ';
    std::cout << std::endl;
    for (auto& [key, val] : cur.children)
        print(val);
}

int main() {

    std::vector<std::string> one = {"hello", "world", "world", "kek", "lol"};
    std::vector<std::string> two = {"hello", "world", "world"};
    std::vector<std::string> three = {"hello", "world", "world", "kek", "lol", "bye"};
    std::vector<std::string> four = {"hello", "world", "world", "bye"};

    Tree t;
    std::cout << t.Has(one) << std::endl;
    t.Insert(one);
    // t.print(t.getroot());
    std::cout << t.Has(one) << ' ' << t.Has(two) <<  ' ' << t.Has(three) << std::endl;
    t.Insert(four);
    // t.print(t.getroot());
}