trie.hpp (cpp-lecture/trie/step01/trie.hpp)

       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
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
     100
     101
     102
     103
     104
     105
     106
     107
     108
     109
     110
     111
     112
     113
     114
     115
     116
     117
     118
     119
     120
     121
     122

#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