#ifndef TRIE_TRIE_HPP
#define TRIE_TRIE_HPP

#include <algorithm>
#include <cassert>
#include <string>
#include <iostream>

struct Key
{
    static constexpr size_t
    size()
    {
        return ('Z' - 'A' + 1) + ('z' - 'a' + 1);
    }

    static constexpr size_t
    map(char c)
    {
        assert(c>='a' && c<='z' || c>='A' && c<='Z');
        if (c>='a' && c<='z') {
            c = c - 'a' + 'A';
        }
        return c - 'A';
    }
};

template <typename Object>
class Trie
{
    public:
        Trie()
            : node{nullptr}, size_{0}
        {
        }

        // Done later ..
        Trie(const Trie &rhs) = delete;

        // Done later ..
        Trie(Trie &&trie) = delete;

        ~Trie()
        {
            delete node;
        }

        // Done later ..
        Trie &
        operator=(Trie rhs) = delete;

        Trie &
        insert(const std::string &key, const Object &obj)
        {
            recursive_insert(node, key.c_str(), obj);
            return *this;
        }

        std::size_t
        size() const
        {
            return size_;
        }

        // Done later ..
        template <typename Visitor>
        const Trie &
        visit(const std::string &key, const Visitor &visitor) const = delete;

    private:

        struct Node
        {
            Node(const Object *value= nullptr)
                : node{}, object{nullptr}
            {
                if (value) {
                    object = new Object(*value);
                }
            }

            // Done later ..
            Node(const Node &rhs) = delete;

            ~Node()
            {
                for (std::size_t i=0; i<Key::size(); ++i) {
                    delete node[i];
                }
                delete object;
            }

            Node    *node[Key::size()];
            Object  *object;
        };

        void
        recursive_insert(Node *&root, const char *c, const Object &value)
        {
            if (!root) {
                root = new Node();
            }

            if (*c) {
                std::size_t key = Key::map(*c);
                recursive_insert(root->node[key], c+1, value);
            } else {
                if (root->object) {
                    std::cout << "Remove old object!" << std::endl;
                    delete root->object;
                } else {
                    ++size_;
                }
                root->object = new Object(value);
            }
        }

        Node            *node;
        std::size_t     size_;
};

#endif // TRIE_TRIE_HPP