Dritter Schritt: Schlüssel-Klasse als Template-Parameter
#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(const Object *value= nullptr)
: node{}, object{nullptr}
{
if (value) {
object = new Object(*value);
}
}
Node(const Node &rhs)
: object{nullptr}
{
if (rhs.object) {
object = new Object(*rhs.object);
}
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];
}
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) {
delete root->object;
} else {
++size;
}
root->object = new Object(value);
}
}
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->object) {
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
#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(const Object *value= nullptr)
: node{}, object{nullptr}
{
if (value) {
object = new Object(*value);
}
}
Node(const Node &rhs)
: object{nullptr}
{
if (rhs.object) {
object = new Object(*rhs.object);
}
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];
}
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) {
delete root->object;
} else {
++size;
}
root->object = new Object(value);
}
}
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->object) {
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