Browse Files
      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
     57
     58
     59
     60
     61
     62
     63
     64
     65
     66
     67
#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