#ifndef TRIE_TRIE_HPP
#define TRIE_TRIE_HPP

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

struct Key
{
    static constexpr size_t
    size();

    static constexpr size_t
    map(char c);
};

template <typename Object>
class Trie
{
    public:
        Trie();

        Trie(const Trie &rhs);

        Trie(Trie &&trie);

        ~Trie();

        Trie &
        operator=(Trie rhs);

        Trie &
        insert(const std::string &key, const Object &obj);

        std::size_t
        size() const;

        template <typename Visitor>
        const Trie &
        visit(const std::string &key, const Visitor &visitor);

    private:

        struct Node
        {
            Node(const Object *value= nullptr);

            Node(const Node &rhs);

            ~Node();

            Node    *node[KeyMap::numKeys()];
            Object  *object;
        };

        void
        recursive_insert(Node *&root, const char *c, const Object &value);

        template <typename Visitor>
        void
        recursive_visit(Node *root, const char *c, const Visitor &visitor) const;

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

#endif // TRIE_TRIE_HPP