Vierter Schritt: Verbesserung der Datenstruktur
#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
#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