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 |