Erster Schritt: Einfügen von Objekten
Zunächst soll nur der Default-Konstruktor, der Destruktor und die insert-Methode implementiert werden. Ein Test-Programm könnte dazu so aussehen:
#include "trie.hpp"
#include <iostream>
int
main()
{
Trie<double> trie;
trie.insert("Lehn", 42);
std::cout << "trie.size() = " << trie.size() << std::endl;
trie.insert("lehn", 42);
std::cout << "trie.size() = " << trie.size() << std::endl;
trie.insert("lehr", 42);
std::cout << "trie.size() = " << trie.size() << std::endl;
trie.insert("le", 42);
std::cout << "trie.size() = " << trie.size() << std::endl;
}
#include <iostream>
int
main()
{
Trie<double> trie;
trie.insert("Lehn", 42);
std::cout << "trie.size() = " << trie.size() << std::endl;
trie.insert("lehn", 42);
std::cout << "trie.size() = " << trie.size() << std::endl;
trie.insert("lehr", 42);
std::cout << "trie.size() = " << trie.size() << std::endl;
trie.insert("le", 42);
std::cout << "trie.size() = " << trie.size() << std::endl;
}
Zu beachten ist, dass wir hier ein paar C++14 Features benutzen und entsprechend übersetzen müssen:
$shell> g++ -Wall -std=c++14 testit.cpp $shell>
In der Implementierung sind vorerst noch Ausgaben eingefügt, so dass wir erkennen, wenn beispielsweise beim Einfügen ein bereits eingetragenes Objekt verdrängt wird:
$shell> ./a.out trie.size() = 1 Remove old object! trie.size() = 1 trie.size() = 2 trie.size() = 3 $shell>
Spannend ist natürlich, wie die Implementierung der Trie-Klasse aussieht:
#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
#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