#ifndef TRIE_TRIE_HPP
#define TRIE_TRIE_HPP

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

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

        Trie(const Trie &rhs)
            : node(rhs.node ? new Node(*rhs.node)
                            : nullptr),
              size{rhs.size}
        {
        }

        Trie(Trie &&trie)
            : Trie()
        {
            swap(*this, trie);
        }

        friend void
        swap(Trie &lhs, Trie &rhs)
        {
	    using std::swap;
            swap(lhs.node, rhs.node);
            swap(lhs.size, rhs.size);
        }

        ~Trie()
        {
            delete node;
        }

        Trie &
        operator=(Trie rhs)
        {
            swap(*this, rhs);
            return *this;
        }

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

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

        template <typename Visitor>
        const Trie &
        visit(const std::string &key, const Visitor &visitor) const
        {
            recursive_visit(node, key.c_str(), visitor);
            return *this;
        }

    private:

        struct Node
        {
            Node()
                : node{}, object{}, hasObject{false}
            {
            }

            Node(const Object &value)
                : node{}, object{value}, hasObject{true}
            {
            }

            Node(const Node &rhs)
                : object{rhs.object}, hasObject{rhs.hasObject}
            {
                for (std::size_t i=0; i<Key::size(); ++i) {
                    node[i] = (rhs.node[i]) ? new Node(*rhs.node[i])
                                            : nullptr;
                }
            }

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

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

        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->hasObject) {
                    ++size;
                }
                root->object    = value;
                root->hasObject = true;
            }
        }

        template <typename Visitor>
        void
        recursive_visit(Node *root, const char *c, const Visitor &visitor) const
        {
            if (!root) {
                return;
            }

            if (c && *c) {
                std::size_t key = Key::map(*c);
                recursive_visit(root->node[key], c+1, visitor);
            } else {
                if (root->hasObject) {
                    visitor(root->object);
                }
                for (std::size_t i=0; i<Key::size(); ++i) {
                    recursive_visit(root->node[i], nullptr, visitor);
                }
            }
        }

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

#endif // TRIE_TRIE_HPP